Issue 7089 - Match filters by type for non-default types

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 19 matching lines @@
  */
 const keywordRegExp = /[^a-z0-9%*][a-z0-9%]{3,}(?=[^a-z0-9%*])/;
 
 /**
  * Regular expression for matching all keywords in a filter.
  * @type {RegExp}
  */
 const allKeywordsRegExp = new RegExp(keywordRegExp, "g");
 
 /**
+ * Bitmask for content types that are implied by default in a filter, like
+ * <code>$script</code>, <code>$image</code>, <code>$stylesheet</code>, and so
+ * on.
+ * @type {number}
+ */
+const DEFAULT_TYPES = RegExpFilter.prototype.contentType;
+
+/**
+ * Bitmask for "types" that must always be specified in a filter explicitly,
+ * like <code>$csp</code>, <code>$popup</code>, <code>$elemhide</code>, and so
+ * on.
+ * @type {number}
+ */
+const NON_DEFAULT_TYPES = ~DEFAULT_TYPES;
+
+/**
  * Bitmask for "types" that are for exception rules only, like
  * <code>$document</code>, <code>$elemhide</code>, and so on.
  * @type {number}
  */
 const WHITELIST_ONLY_TYPES = RegExpFilter.typeMap.DOCUMENT |
                              RegExpFilter.typeMap.ELEMHIDE |
                              RegExpFilter.typeMap.GENERICHIDE |
                              RegExpFilter.typeMap.GENERICBLOCK;
 
 /**
+ * Yields individual non-default types from a filter's type mask.
+ * @param {number} contentType A filter's type mask.
+ * @yields {number}
+ */
+function* nonDefaultTypes(contentType)

[Manish Jethani, 2018/11/02 00:33:47]

For a filter like `foo$script,image,popup`, this function will yield the value
of `RegExpFilter.typeMap.POPUP` (currently 0x10000000).

+{
+  for (let mask = contentType & NON_DEFAULT_TYPES, bitIndex = 0;
+       mask != 0; mask >>>= 1, bitIndex++)
+  {
+    if ((mask & 1) != 0)
+    {
+      // Note: The zero-fill right shift by zero is necessary for dropping the
+      // sign.
+      yield 1 << bitIndex >>> 0;
+    }
+  }
+}
+
+/**
+ * Adds a filter by a given keyword to a map.
+ * @param {RegExpFilter} filter
+ * @param {string} keyword
+ * @param {Map.<string,(RegExpFilter|Set.<RegExpFilter>)>} map
+ */
+function addFilterByKeyword(filter, keyword, map)
+{
+  let set = map.get(keyword);

[Manish Jethani, 2018/11/02 00:33:47]

This has been copied and pasted from the add and remove functions (respectively)
with no changes to the logic.

+  if (typeof set == "undefined")
+  {
+    map.set(keyword, filter);
+  }
+  else if (set.size == 1)
+  {
+    if (filter != set)
+      map.set(keyword, new Set([set, filter]));
+  }
+  else
+  {
+    set.add(filter);
+  }
+}
+
+/**
+ * Removes a filter by a given keyword from a map.
+ * @param {RegExpFilter} filter
+ * @param {string} keyword
+ * @param {Map.<string,(RegExpFilter|Set.<RegExpFilter>)>} map
+ */
+function removeFilterByKeyword(filter, keyword, map)
+{
+  let set = map.get(keyword);
+  if (typeof set == "undefined")
+    return;
+
+  if (set.size == 1)
+  {
+    if (filter == set)
+      map.delete(keyword);
+  }
+  else
+  {
+    set.delete(filter);
+
+    if (set.size == 1)
+      map.set(keyword, [...set][0]);
+  }
+}
+
+/**
  * Checks whether a particular filter is slow.
  * @param {RegExpFilter} filter
  * @returns {boolean}
  */
 function isSlowFilter(filter)
 {
   return !filter.pattern || !keywordRegExp.test(filter.pattern);
 }
 
 exports.isSlowFilter = isSlowFilter;
@@ skipping 11 matching lines @@
      * @private
      */
     this._simpleFiltersByKeyword = new Map();
 
     /**
      * Lookup table for complex filters by their associated keyword
      * @type {Map.<string,(RegExpFilter|Set.<RegExpFilter>)>}
      * @private
      */
     this._complexFiltersByKeyword = new Map();
+
+    /**
+     * Lookup table of type-specific lookup tables for complex filters by their
+     * associated keyword
+     * @type {Map.<string,Map.<string,(RegExpFilter|Set.<RegExpFilter>)>>}
+     * @private
+     */
+    this._filterMapsByType = new Map();
   }
 
   /**
    * Removes all known filters
    */
   clear()
   {
     this._simpleFiltersByKeyword.clear();
     this._complexFiltersByKeyword.clear();
+    this._filterMapsByType.clear();
   }
 
   /**
    * Adds a filter to the matcher
    * @param {RegExpFilter} filter
    */
   add(filter)
   {
-    let filtersByKeyword = filter.isLocationOnly() ?
-                             this._simpleFiltersByKeyword :
-                             this._complexFiltersByKeyword;
     // Look for a suitable keyword
     let keyword = this.findKeyword(filter);
-    let set = filtersByKeyword.get(keyword);
-    if (typeof set == "undefined")
+    let locationOnly = filter.isLocationOnly();
+
+    addFilterByKeyword(filter, keyword,
+                       locationOnly ? this._simpleFiltersByKeyword :
+                         this._complexFiltersByKeyword);
+
+    if (locationOnly)
+      return;
+
+    for (let type of nonDefaultTypes(filter.contentType))
     {
-      filtersByKeyword.set(keyword, filter);
-    }
-    else if (set.size == 1)
-    {
-      if (filter != set)
-        filtersByKeyword.set(keyword, new Set([set, filter]));
-    }
-    else
-    {
-      set.add(filter);
+      let map = this._filterMapsByType.get(type);
+      if (!map)
+        this._filterMapsByType.set(type, map = new Map());
+
+      addFilterByKeyword(filter, keyword, map);
     }
   }
 
   /**
    * 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 = filtersByKeyword.get(keyword);
-    if (typeof set == "undefined")
+    let locationOnly = filter.isLocationOnly();
+
+    removeFilterByKeyword(filter, keyword,
+                          locationOnly ? this._simpleFiltersByKeyword :
+                            this._complexFiltersByKeyword);
+
+    if (locationOnly)
       return;
 
-    if (set.size == 1)
+    for (let type of nonDefaultTypes(filter.contentType))
     {
-      if (filter == set)
-        filtersByKeyword.delete(keyword);
-    }
-    else
-    {
-      set.delete(filter);
-
-      if (set.size == 1)
-        filtersByKeyword.set(keyword, [...set][0]);
+      let map = this._filterMapsByType.get(type);
+      if (map)
+        removeFilterByKeyword(filter, keyword, map);
     }
   }
 
   /**
    * 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)
@@ skipping 39 matching lines @@
    * @param {string} [sitekey]
    * @param {boolean} [specificOnly]
    * @returns {?Filter}
    * @protected
    */
   checkEntryMatch(keyword, location, typeMask, docDomain, thirdParty, sitekey,
                   specificOnly)
   {
     // We need to skip the simple (location-only) filters if the type mask does
     // not contain any default content types.
-    if ((typeMask & RegExpFilter.prototype.contentType) != 0)
+    if ((typeMask & DEFAULT_TYPES) != 0)
     {
       let simpleSet = this._simpleFiltersByKeyword.get(keyword);
       if (simpleSet)
       {
         for (let filter of simpleSet)
         {
           if (specificOnly && !(filter instanceof WhitelistFilter))
             continue;
 
           if (filter.matchesLocation(location))
             return filter;
         }
       }
     }
 
-    let complexSet = this._complexFiltersByKeyword.get(keyword);
+    let complexSet = null;
+
+    // If the type mask contains a non-default type (first condition) and it is
+    // the only type in the mask (second condition), we can use the
+    // type-specific map, which typically contains a lot fewer filters. This
+    // enables faster lookups for whitelisting types like $document, $elemhide,
+    // and so on, as well as other special types like $csp.
+    if ((typeMask & NON_DEFAULT_TYPES) != 0 && (typeMask & typeMask - 1) == 0)

[Manish Jethani, 2018/11/02 00:33:47]

The second condition here basically checks if the type mask has only a single
bit set.

[hub, 2018/12/11 15:34:59]

What throw me off here is the evaluation order of `typeMask & typeMask - 1`. But
I get it.

+    {
+      let map = this._filterMapsByType.get(typeMask);
+      if (map)
+        complexSet = map.get(keyword);
+    }
+    else
+    {
+      complexSet = this._complexFiltersByKeyword.get(keyword);
+    }
+
     if (complexSet)
     {
       for (let filter of complexSet)
       {
         if (specificOnly && filter.isGeneric() &&
             !(filter instanceof WhitelistFilter))
           continue;
 
         if (filter.matches(location, typeMask, docDomain, thirdParty, sitekey))
           return filter;
@@ skipping 202 matching lines @@
 
 exports.CombinedMatcher = CombinedMatcher;
 
 /**
  * Shared {@link CombinedMatcher} instance that should usually be used.
  * @type {CombinedMatcher}
  */
 let defaultMatcher = new CombinedMatcher();
 
 exports.defaultMatcher = defaultMatcher;