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
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 "use strict";
 
 /**
  * @fileOverview Matcher class implementing matching addresses against
  *               a list of filters.
  */
 
-const {WhitelistFilter} = require("./filterClasses");
+const {RegExpFilter, WhitelistFilter} = require("./filterClasses");
 
 /**
  * Regular expression for matching a keyword in a filter.
  * @type {RegExp}
  */
 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 "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;
 
 /**
  * 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;
 
 /**
  * Blacklist/whitelist filter matching
  */
 class Matcher
 {
   constructor()
   {
     /**
      * Lookup table for filters by their associated keyword
      * @type {Map.<string,(Filter|Set.<Filter>)>}
-     */
-    this.filterByKeyword = new Map();
+     * @private
+     */
+    this._filterByKeyword = new Map();
+
+    /**
+     * Lookup table for location only filters by their associated keyword

[Manish Jethani, 2018/10/24 21:35:28]

Nit: I don't know if this is right, but I would have spelt it "location-only"
(with a hyphen).

[Jon Sonesen, 2018/10/24 21:46:51]

Acknowledged.

+     * for shortcut matching.
+     * @private

[Manish Jethani, 2018/10/24 21:35:28]

Let's put @private last.

[Jon Sonesen, 2018/10/24 21:46:52]

Acknowledged.

+     * @type {Map.<string,(Filter|Set.<Filter>)>}
+     */
+    this._fastFilterByKeyword = new Map();

[Manish Jethani, 2018/10/24 21:35:28]

I'm thinking about the nomenclature here, about how to distinguish the two
filter types. What do you think about "simple" filters and "complex" filters?
Then we can rename `_filterByKeyword` to `_complexFiltersByKeyword` and this one
to `_simpleFiltersByKeyword` (note: I also made filters plural here, which is
how it should have been from the beginning).

[Jon Sonesen, 2018/10/24 21:46:52]

I like this, it makes more sense from a reader's perspective IMHO 

   }
 
   /**
    * Removes all known filters
    */
   clear()
   {
-    this.filterByKeyword.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
+   * @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 hash = filter.isLocationOnly() ? this._fastFilterByKeyword :
+      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;

[Manish Jethani, 2018/10/25 00:49:42]

We need `count` to be the sum of `this._simpleFiltersByKeyword(candidate).size`
and `this._complexFiltersByKeyword(candidate).size` to get the most optimal
results here (basically keep it semantically equivalent to the current version
of this function).

       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}
-   */
-  _checkEntryMatch(keyword, location, typeMask, docDomain, thirdParty, sitekey,
-                   specificOnly)
-  {
-    let set = this.filterByKeyword.get(keyword);
+   * @protected
+   */
+  checkEntryMatch(keyword, location, typeMask, docDomain, thirdParty, sitekey,
+                  specificOnly)
+  {
+    let set = this._filterByKeyword.get(keyword);
     if (typeof set == "undefined")

[Manish Jethani, 2018/10/25 00:49:41]

This is clearly wrong. We want to check all filters that match the keyword. Here
the code only checks the simple filters if there are no complex filters.

We have to do the simple filters first, so let's do this:

  let set = this._simpleFiltersByKeyword(keyword);

  if (set)
  {
    for (let filter of set)
    {
      if (specificOnly && !(filter instanceof WhitelistFilter))
        continue;

      if (filter.matchesLocation(location))
        return filter;
    }
  }

  set = this._complexFiltersByKeyword(keyword);

  ...

Note that we don't have to call `filter.isGeneric()` because by definition the
simple filters have neither any domains nor any sitekeys so they are generic.

+    {
+      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.matchesLocation(location))
+          return filter;
+      }
       return null;
+    }
 
     for (let filter of set)

[Manish Jethani, 2018/10/13 13:28:45]

The idea was to have two loops, one for the location-only filters and one for
the regular filters. For this, we would have to maintain the location-only
filters in a separate set, per keyword.

I would start by adding the following method to the `RegExpFilter` class:

  isLocationOnly()
  {
    return this.contentType == RegExpFilter.prototype.contentType &&
           this.thirdParty == null && !this.domains && !this.sitekeys;
  }

[Jon Sonesen, 2018/10/20 23:07:55]

Ack

     {
-      if (typeMask == 0)
-        continue;
-
       if (specificOnly && filter.isGeneric() &&
           !(filter instanceof WhitelistFilter))
         continue;
-
-      if (!sitekey || !docDomain || !thirdParty)
-      {

[Manish Jethani, 2018/10/13 13:28:45]

This seems wrong.

[Jon Sonesen, 2018/10/20 23:07:55]

Yeah, super wrong. My bad

-        if (filter.matches(location))
-          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
@@ skipping 12 matching lines @@
    *   matching filter or <code>null</code>
    */
   matchesAny(location, typeMask, docDomain, thirdParty, sitekey, specificOnly)
   {
     let candidates = location.toLowerCase().match(/[a-z0-9%]{3,}/g);
     if (candidates === null)
       candidates = [];
     candidates.push("");
     for (let i = 0, l = candidates.length; i < l; i++)
     {
-      let result = this._checkEntryMatch(candidates[i], location, typeMask,
-                                         docDomain, thirdParty, sitekey,
-                                         specificOnly);
+      let result = this.checkEntryMatch(candidates[i], location, typeMask,
+                                        docDomain, thirdParty, sitekey,
+                                        specificOnly);
       if (result)
         return result;
     }
 
     return null;
   }
 }
 
 exports.Matcher = Matcher;
 
 /**
  * Combines a matcher for blocking and exception rules, automatically sorts
  * rules into two {@link Matcher} instances.
  */
 class CombinedMatcher
 {
   constructor()
   {
     /**
      * Maximal number of matching cache entries to be kept
      * @type {number}
      */
     this.maxCacheEntries = 1000;
 
     /**
      * Matcher for blocking rules.
      * @type {Matcher}
-     */
-    this.blacklist = new Matcher();
+     * @private
+     */
+    this._blacklist = new Matcher();
 
     /**
      * Matcher for exception rules.
      * @type {Matcher}
-     */
-    this.whitelist = new Matcher();
+     * @private
+     */
+    this._whitelist = new Matcher();
 
     /**
      * Lookup table of previous {@link Matcher#matchesAny} results
      * @type {Map.<string,Filter>}
-     */
-    this.resultCache = new Map();
+     * @private
+     */
+    this._resultCache = new Map();
   }
 
   /**
    * @see Matcher#clear
    */
   clear()
   {
-    this.blacklist.clear();
-    this.whitelist.clear();
-    this.resultCache.clear();
+    this._blacklist.clear();
+    this._whitelist.clear();
+    this._resultCache.clear();
   }
 
   /**
    * @see Matcher#add
    * @param {Filter} filter
    */
   add(filter)
   {
     if (filter instanceof WhitelistFilter)
-      this.whitelist.add(filter);
+      this._whitelist.add(filter);
     else
-      this.blacklist.add(filter);
-
-    this.resultCache.clear();
+      this._blacklist.add(filter);
+
+    this._resultCache.clear();
   }
 
   /**
    * @see Matcher#remove
    * @param {Filter} filter
    */
   remove(filter)
   {
     if (filter instanceof WhitelistFilter)
-      this.whitelist.remove(filter);
+      this._whitelist.remove(filter);
     else
-      this.blacklist.remove(filter);
-
-    this.resultCache.clear();
+      this._blacklist.remove(filter);
+
+    this._resultCache.clear();
   }
 
   /**
    * @see Matcher#findKeyword
    * @param {Filter} filter
    * @returns {string} keyword
+   * @protected
    */
   findKeyword(filter)
   {
     if (filter instanceof WhitelistFilter)
-      return this.whitelist.findKeyword(filter);
-    return this.blacklist.findKeyword(filter);
+      return this._whitelist.findKeyword(filter);
+    return this._blacklist.findKeyword(filter);
   }
 
   /**
    * Optimized filter matching testing both whitelist and blacklist matchers
    * simultaneously. For parameters see
      {@link Matcher#matchesAny Matcher.matchesAny()}.
    * @see Matcher#matchesAny
    * @inheritdoc
-   */
-  matchesAnyInternal(location, typeMask, docDomain, thirdParty, sitekey,
-                     specificOnly)
+   * @private
+   */
+  _matchesAnyInternal(location, typeMask, docDomain, thirdParty, sitekey,
+                      specificOnly)
   {
     let candidates = location.toLowerCase().match(/[a-z0-9%]{3,}/g);
     if (candidates === null)
       candidates = [];
     candidates.push("");
 
+    let whitelistHit = null;
     let blacklistHit = null;
-    for (let i = 0, l = candidates.length; i < l; i++)
-    {
-      let substr = candidates[i];
-      let result = this.whitelist._checkEntryMatch(
-        substr, location, typeMask, docDomain, thirdParty, sitekey
-      );
-      if (result)
-        return result;
-      if (blacklistHit === null)
+
+    // If the type mask includes no types other than whitelist-only types, we
+    // can skip the blacklist.
+    if ((typeMask & ~WHITELIST_ONLY_TYPES) != 0)
+    {
+      for (let i = 0, l = candidates.length; !blacklistHit && i < l; i++)
       {
-        blacklistHit = this.blacklist._checkEntryMatch(
-          substr, location, typeMask, docDomain, thirdParty, sitekey,
-          specificOnly
-        );
+        blacklistHit = this._blacklist.checkEntryMatch(candidates[i], location,
+                                                       typeMask, docDomain,
+                                                       thirdParty, sitekey,
+                                                       specificOnly);
       }
     }
-    return blacklistHit;
+
+    // If the type mask includes any whitelist-only types, we need to check the
+    // whitelist.
+    if (blacklistHit || (typeMask & WHITELIST_ONLY_TYPES) != 0)
+    {
+      for (let i = 0, l = candidates.length; !whitelistHit && i < l; i++)
+      {
+        whitelistHit = this._whitelist.checkEntryMatch(candidates[i], location,
+                                                       typeMask, docDomain,
+                                                       thirdParty, sitekey);
+      }
+    }
+
+    return whitelistHit || blacklistHit;
   }
 
   /**
    * @see Matcher#matchesAny
    * @inheritdoc
    */
   matchesAny(location, typeMask, docDomain, thirdParty, sitekey, specificOnly)
   {
     let key = location + " " + typeMask + " " + docDomain + " " + thirdParty +
       " " + sitekey + " " + specificOnly;
 
-    let result = this.resultCache.get(key);
+    let result = this._resultCache.get(key);
     if (typeof result != "undefined")
       return result;
 
-    result = this.matchesAnyInternal(location, typeMask, docDomain,
-                                     thirdParty, sitekey, specificOnly);
-
-    if (this.resultCache.size >= this.maxCacheEntries)
-      this.resultCache.clear();
-
-    this.resultCache.set(key, result);
+    result = this._matchesAnyInternal(location, typeMask, docDomain,
+                                      thirdParty, sitekey, specificOnly);
+
+    if (this._resultCache.size >= this.maxCacheEntries)
+      this._resultCache.clear();
+
+    this._resultCache.set(key, result);
 
     return result;
   }
 }
 
 exports.CombinedMatcher = CombinedMatcher;
 
 /**
  * Shared {@link CombinedMatcher} instance that should usually be used.
  * @type {CombinedMatcher}
  */
 let defaultMatcher = new CombinedMatcher();
 
 exports.defaultMatcher = defaultMatcher;