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 53 matching lines @@
 class Matcher
 {
   constructor()
   {
     /**
      * Lookup table for filters by their associated keyword
      * @type {Map.<string,(Filter|Set.<Filter>)>}
      * @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._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}
    * @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)
     {
       if (specificOnly && filter.isGeneric() &&
           !(filter instanceof WhitelistFilter))
         continue;
 
       if (filter.matches(location, typeMask, docDomain, thirdParty, sitekey))
         return filter;
     }
@@ skipping 199 matching lines @@
 
 exports.CombinedMatcher = CombinedMatcher;
 
 /**
  * Shared {@link CombinedMatcher} instance that should usually be used.
  * @type {CombinedMatcher}
  */
 let defaultMatcher = new CombinedMatcher();
 
 exports.defaultMatcher = defaultMatcher;