Issue 6994 - Use shortcut matching for location only filters

lib/matcher.js

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-present eyeo GmbH
  *
  * Adblock Plus is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 3 as
  * published by the Free Software Foundation.
  *
  * Adblock Plus is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
@@ skipping 42 matching lines @@
  */
 class Matcher
 {
   constructor()
   {
     /**
      * Lookup table for filters by their associated keyword
      * @type {Map.<string,(Filter|Set.<Filter>)>}
      */
     this.filterByKeyword = new Map();
+
+    /**
+     * Lookup table for location only filters by their associated keyword
+     * for shortcut matching.
+     * @private
+     * @type {Map.<string,(Filter|Set.<Filter>)>}
+     */
+    this._fastFilterByKeyword = new Map();
   }
 
   /**
    * Removes all known filters
    */
   clear()
   {
     this.filterByKeyword.clear();
+    this._fastFilterByKeyword.clear();
   }
 
   /**
    * Adds a filter to the matcher
    * @param {RegExpFilter} filter
    */
   add(filter)
   {
     // Look for a suitable keyword
     let keyword = this.findKeyword(filter);
-    let set = this.filterByKeyword.get(keyword);
+    let filterMap = filter.isLocationOnly ? this._fastFilterByKeyword :
+      this.filterByKeyword;
+    let set = filterMap.get(keyword);
+
     if (typeof set == "undefined")
     {
-      this.filterByKeyword.set(keyword, filter);
+      filterMap.set(keyword, filter);
     }
     else if (set.size == 1)
     {
       if (filter != set)
-        this.filterByKeyword.set(keyword, new Set([set, filter]));
+        filterMap.set(keyword, new Set([set, filter]));
     }
     else
     {
       set.add(filter);
     }
   }
 
   /**
    * Removes a filter from the matcher
    * @param {RegExpFilter} filter
    */
   remove(filter)
   {
     let keyword = this.findKeyword(filter);
-    let set = this.filterByKeyword.get(keyword);
+    let filterMap = filter.isLocationOnly ? this._fastFilterByKeyword :
+      this.filterByKeyword;
+    let set = filterMap.get(keyword);
+
     if (typeof set == "undefined")
       return;
 
     if (set.size == 1)
     {
       if (filter == set)
-        this.filterByKeyword.delete(keyword);
+        filterMap.delete(keyword);
     }
     else
     {
       set.delete(filter);
 
       if (set.size == 1)
-        this.filterByKeyword.set(keyword, [...set][0]);
+        filterMap.set(keyword, [...set][0]);
     }
   }
 
   /**
    * Chooses a keyword to be associated with the filter
    * @param {Filter} filter
    * @returns {string} keyword or an empty string if no keyword could be found
    */
   findKeyword(filter)
   {
     let result = "";
     let {pattern} = filter;
     if (pattern == null)
       return result;
 
     let candidates = pattern.toLowerCase().match(allKeywordsRegExp);
     if (!candidates)
       return result;
 
-    let hash = this.filterByKeyword;
+    let hash = filter.isLocationOnly ? this._fastFilterByKeyword :
+      this.filterByKeyword;

[Jon Sonesen, 2018/10/21 17:29:51]

In the tests this fails on the last test of extractKeyword and compareKeyword

     let resultCount = 0xFFFFFF;
     let resultLength = 0;
     for (let i = 0, l = candidates.length; i < l; i++)
     {
       let candidate = candidates[i].substr(1);
       let filters = hash.get(candidate);
       let count = typeof filters != "undefined" ? filters.size : 0;
       if (count < resultCount ||
           (count == resultCount && candidate.length > resultLength))
       {
@@ skipping 14 matching lines @@
    * @param {boolean} [thirdParty]
    * @param {string} [sitekey]
    * @param {boolean} [specificOnly]
    * @returns {?Filter}
    */
   _checkEntryMatch(keyword, location, typeMask, docDomain, thirdParty, sitekey,
                    specificOnly)
   {
     let set = this.filterByKeyword.get(keyword);
     if (typeof set == "undefined")
+    {
+      let fastSet = this._fastFilterByKeyword.get(keyword);
+      if (typeof fastSet == "undefined")
+        return null;
+
+      for (let filter of fastSet)
+      {
+        if (specificOnly && filter.isGeneric() &&
+            !(filter instanceof WhitelistFilter))
+          continue;
+
+        if (filter.matches(location, typeMask, docDomain, thirdParty, sitekey))
+          return filter;
+      }
       return null;
+    }
 
     for (let filter of set)
     {
       if (specificOnly && filter.isGeneric() &&
           !(filter instanceof WhitelistFilter))
         continue;
 
       if (filter.matches(location, typeMask, docDomain, thirdParty, sitekey))
         return filter;
     }
@@ skipping 183 matching lines @@
 
 exports.CombinedMatcher = CombinedMatcher;
 
 /**
  * Shared {@link CombinedMatcher} instance that should usually be used.
  * @type {CombinedMatcher}
  */
 let defaultMatcher = new CombinedMatcher();
 
 exports.defaultMatcher = defaultMatcher;