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 48 matching lines @@
 exports.isSlowFilter = isSlowFilter;
 
 /**
  * Blacklist/whitelist filter matching
  */
 class Matcher
 {
   constructor()
   {
     /**
-     * Lookup table for filters by their associated keyword
-     * @type {Map.<string,(Filter|Set.<Filter>)>}
+     * Lookup table for simple filters by their associated keyword
+     * @type {Map.<string,(RegExpFilter|Set.<RegExpFilter>)>}

[Manish Jethani, 2018/10/25 21:24:10]

Unrelated documentation update, but these can only be RegExpFilter objects.

      * @private
      */
-    this._filterByKeyword = new Map();
+    this._simpleFiltersByKeyword = new Map();
+
+    /**
+     * Lookup table for complex filters by their associated keyword
+     * @type {Map.<string,(RegExpFilter|Set.<RegExpFilter>)>}
+     * @private
+     */
+    this._complexFiltersByKeyword = new Map();
   }
 
   /**
    * Removes all known filters
    */
   clear()
   {
-    this._filterByKeyword.clear();
+    this._simpleFiltersByKeyword.clear();
+    this._complexFiltersByKeyword.clear();
   }
 
   /**
    * Adds a filter to the matcher
    * @param {RegExpFilter} filter
    */
   add(filter)
   {
+    let filtersByKeyword = filter.isLocationOnly() ?

[Manish Jethani, 2018/10/25 21:24:10]

The filter goes into one of the two maps, depending on whether it's a
location-only filter or not.

+                             this._simpleFiltersByKeyword :
+                             this._complexFiltersByKeyword;
     // Look for a suitable keyword
     let keyword = this.findKeyword(filter);
-    let set = this._filterByKeyword.get(keyword);
+    let set = filtersByKeyword.get(keyword);
     if (typeof set == "undefined")
     {
-      this._filterByKeyword.set(keyword, filter);
+      filtersByKeyword.set(keyword, filter);
     }
     else if (set.size == 1)
     {
       if (filter != set)
-        this._filterByKeyword.set(keyword, new Set([set, filter]));
+        filtersByKeyword.set(keyword, new Set([set, filter]));
     }
     else
     {
       set.add(filter);
     }
   }
 
   /**
    * Removes a filter from the matcher
    * @param {RegExpFilter} filter
    */
   remove(filter)
   {
+    let filtersByKeyword = filter.isLocationOnly() ?
+                             this._simpleFiltersByKeyword :
+                             this._complexFiltersByKeyword;
     let keyword = this.findKeyword(filter);
-    let set = this._filterByKeyword.get(keyword);
+    let set = filtersByKeyword.get(keyword);
     if (typeof set == "undefined")
       return;
 
     if (set.size == 1)
     {
       if (filter == set)
-        this._filterByKeyword.delete(keyword);
+        filtersByKeyword.delete(keyword);
     }
     else
     {
       set.delete(filter);
 
       if (set.size == 1)
-        this._filterByKeyword.set(keyword, [...set][0]);
+        filtersByKeyword.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
    * @protected
    */
   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 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;
+      let simpleFilters = this._simpleFiltersByKeyword.get(candidate);
+      let complexFilters = this._complexFiltersByKeyword.get(candidate);
+      let count = (typeof simpleFilters != "undefined" ?

[Manish Jethani, 2018/10/25 21:24:10]

Now count needs to be the sum of the sizes of the two sets.

+                     simpleFilters.size : 0) +
+                  (typeof complexFilters != "undefined" ?
+                     complexFilters.size : 0);
       if (count < resultCount ||
           (count == resultCount && candidate.length > resultLength))
       {
         result = candidate;
         resultCount = count;
         resultLength = candidate.length;
       }
     }
     return result;
   }
 
   /**
    * Checks whether the entries for a particular keyword match a URL
    * @param {string} keyword
    * @param {string} location
    * @param {number} typeMask
    * @param {string} [docDomain]
    * @param {boolean} [thirdParty]
    * @param {string} [sitekey]
    * @param {boolean} [specificOnly]
    * @returns {?Filter}
    * @protected
    */
   checkEntryMatch(keyword, location, typeMask, docDomain, thirdParty, sitekey,
                   specificOnly)
   {
-    let set = this._filterByKeyword.get(keyword);
-    if (typeof set == "undefined")
-      return null;
+    // We need to skip the simple (location-only) filters if the type mask does
+    // not contain any non-default content types like $document, $elemhide,
+    // $csp, and so on.
+    if ((typeMask & RegExpFilter.prototype.contentType) != 0)
+    {
+      let simpleSet = this._simpleFiltersByKeyword.get(keyword);
+      if (simpleSet)
+      {
+        for (let filter of simpleSet)
+        {
+          if ((!specificOnly || filter instanceof WhitelistFilter) &&
+              filter.matchesLocation(location))

[Manish Jethani, 2018/10/25 21:24:10]

For these filters, we only match the location. We know that the content type
matches (from the check above), we know that the third-party flag is irrelevant,
and we know also that `docDomain` and `sitekey` are irrelevant (because the
filter doesn't have anything to match these against).

+          {
+            return filter;
+          }
+        }
+      }
+    }
 
-    for (let filter of set)
+    let complexSet = this._complexFiltersByKeyword.get(keyword);
+    if (complexSet)
     {
-      if (specificOnly && filter.isGeneric() &&
-          !(filter instanceof WhitelistFilter))
-        continue;
+      for (let filter of complexSet)
+      {
+        if (specificOnly && filter.isGeneric() &&
+            !(filter instanceof WhitelistFilter))
+          continue;
 
-      if (filter.matches(location, typeMask, docDomain, thirdParty, sitekey))
-        return filter;
+        if (filter.matches(location, typeMask, docDomain, thirdParty, sitekey))
+          return filter;
+      }
     }
+
     return null;
   }
 
   /**
    * Tests whether the URL matches any of the known filters
    * @param {string} location
    *   URL to be tested
    * @param {number} typeMask
    *   bitmask of content / request types to match
    * @param {string} [docDomain]
@@ skipping 189 matching lines @@
 
 exports.CombinedMatcher = CombinedMatcher;
 
 /**
  * Shared {@link CombinedMatcher} instance that should usually be used.
  * @type {CombinedMatcher}
  */
 let defaultMatcher = new CombinedMatcher();
 
 exports.defaultMatcher = defaultMatcher;