Issue 7265 - Orgnanize request blocking filters by domain

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 {RegExpFilter, WhitelistFilter} = require("./filterClasses");
+const {suffixes} = require("./domain");
 
 /**
  * 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}
@@ skipping 20 matching lines @@
  * 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;
 
 /**
+ * Map to be used instead when a filter has a blank <code>domains</code>
+ * property.
+ * @type {Map.<string, boolean>}
+ */
+let defaultDomains = new Map([["", true]]);
+
+/**
  * Yields individual non-default types from a filter's type mask.
  * @param {number} contentType A filter's type mask.
  * @yields {number}
  */
 function* nonDefaultTypes(contentType)
 {
   for (let mask = contentType & NON_DEFAULT_TYPES, bitIndex = 0;
        mask != 0; mask >>>= 1, bitIndex++)
   {
     if ((mask & 1) != 0)
@@ skipping 89 matching lines @@
     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 domain maps for complex filters by their associated
+     * keyword
+     * @type {Map.<string,Map.<string,(RegExpFilter|
+     *                                 Map.<RegExpFilter,boolean>)>>}
+     * @private
+     */
+    this._filterDomainMapsByKeyword = 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._keywordByFilter.clear();
     this._simpleFiltersByKeyword.clear();
     this._complexFiltersByKeyword.clear();
+    this._filterDomainMapsByKeyword.clear();
     this._filterMapsByType.clear();
   }
 
   /**
    * Adds a filter to the matcher
    * @param {RegExpFilter} filter
    */
   add(filter)
   {
     if (this._keywordByFilter.has(filter))
@@ skipping 13 matching lines @@
       return;
 
     for (let type of nonDefaultTypes(filter.contentType))
     {
       let map = this._filterMapsByType.get(type);
       if (!map)
         this._filterMapsByType.set(type, map = new Map());
 
       addFilterByKeyword(filter, keyword, map);
     }
+
+    let filtersByDomain = this._filterDomainMapsByKeyword.get(keyword);
+    if (!filtersByDomain)
+      this._filterDomainMapsByKeyword.set(keyword, filtersByDomain = new Map());
+
+    for (let [domain, include] of filter.domains || defaultDomains)
+    {
+      if (!include && domain == "")
+        continue;
+
+      let map = filtersByDomain.get(domain);
+      if (!map)
+      {
+        filtersByDomain.set(domain, include ? filter :
+                              map = new Map([[filter, false]]));
+      }
+      else if (map.size == 1 && !(map instanceof Map))
+      {
+        if (filter != map)
+        {
+          filtersByDomain.set(domain, new Map([[map, true],
+                                               [filter, include]]));
+        }
+      }
+      else
+      {
+        map.set(filter, include);
+      }
+    }
   }
 
   /**
    * Removes a filter from the matcher
    * @param {RegExpFilter} filter
    */
   remove(filter)
   {
     let keyword = this._keywordByFilter.get(filter);
     if (typeof keyword == "undefined")
       return;
 
     let locationOnly = filter.isLocationOnly();
 
     removeFilterByKeyword(filter, keyword,
                           locationOnly ? this._simpleFiltersByKeyword :
                             this._complexFiltersByKeyword);
 
     this._keywordByFilter.delete(filter);
 
     if (locationOnly)
       return;
 
     for (let type of nonDefaultTypes(filter.contentType))
     {
       let map = this._filterMapsByType.get(type);
       if (map)
         removeFilterByKeyword(filter, keyword, map);
     }
+
+    let filtersByDomain = this._filterDomainMapsByKeyword.get(keyword);
+    if (filtersByDomain)
+    {
+      let domains = filter.domains || defaultDomains;
+      for (let domain of domains.keys())
+      {
+        let map = filtersByDomain.get(domain);
+        if (map)
+        {
+          if (map.size > 1 || map instanceof Map)

[Sebastian Noack, 2019/02/06 16:30:58]

In which scenario would "map" not be a Map object, and wouldn't the size
property doesn't exist either then?

[Manish Jethani, 2019/02/06 19:25:05]

It's a hack.

The filter object doubles up as a fake Map object. This way we don't have to
keep a map with only the filter as the key and true as the value (a very common
case). Without this hack, it would take 10 MB more for EasyList.

+          {
+            map.delete(filter);
+
+            if (map.size == 0)
+              filtersByDomain.delete(domain);
+          }
+          else if (filter == map)
+          {
+            filtersByDomain.delete(domain);
+          }
+        }
+      }
+    }
   }
 
   /**
    * 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 21 matching lines @@
           (count == resultCount && candidate.length > resultLength))
       {
         result = candidate;
         resultCount = count;
         resultLength = candidate.length;
       }
     }
     return result;
   }
 
+  _checkEntryMatchSimple(keyword, location, typeMask, docDomain, thirdParty,
+                         sitekey, specificOnly, collection)
+  {
+    let filters = this._simpleFiltersByKeyword.get(keyword);
+    if (filters)
+    {
+      let lowerCaseLocation = location.toLowerCase();
+
+      for (let filter of filters)
+      {
+        if (specificOnly && !(filter instanceof WhitelistFilter))
+          continue;
+
+        if (filter.matchesLocation(location, lowerCaseLocation))
+        {
+          if (!collection)
+            return filter;
+
+          collection.push(filter);
+        }
+      }
+    }
+
+    return null;
+  }
+
+  _checkEntryMatchForType(keyword, location, typeMask, docDomain, thirdParty,
+                          sitekey, specificOnly, collection)
+  {
+    let filtersForType = this._filterMapsByType.get(typeMask);
+    if (filtersForType)
+    {
+      let filters = filtersForType.get(keyword);
+      if (filters)
+      {
+        for (let filter of filters)
+        {
+          if (specificOnly && filter.isGeneric() &&
+              !(filter instanceof WhitelistFilter))
+            continue;
+
+          if (filter.matches(location, typeMask, docDomain, thirdParty,
+                             sitekey))
+          {
+            if (!collection)
+              return filter;
+
+            collection.push(filter);
+          }
+        }
+      }
+    }
+
+    return null;
+  }
+
+  _checkEntryMatchByDomain(keyword, location, typeMask, docDomain, thirdParty,
+                           sitekey, specificOnly, collection)
+  {
+    let filtersByDomain = this._filterDomainMapsByKeyword.get(keyword);
+    if (filtersByDomain)
+    {
+      // The code in this block is similar to the generateStyleSheetForDomain
+      // function in lib/elemHide.js.
+
+      if (docDomain)
+      {
+        if (docDomain[docDomain.length - 1] == ".")
+          docDomain = docDomain.replace(/\.+$/, "");
+
+        docDomain = docDomain.toLowerCase();
+      }
+
+      let excluded = new Set();
+
+      for (let suffix of suffixes(docDomain || "", !specificOnly))
+      {
+        let filters = filtersByDomain.get(suffix);
+        if (filters)
+        {
+          for (let [filter, include] of filters.entries())
+          {
+            if (!include)
+            {
+              excluded.add(filter);
+            }
+            else if ((excluded.size == 0 || !excluded.has(filter)) &&
+                     filter.matchesWithoutDomain(location, typeMask,
+                                                 thirdParty, sitekey))
+            {
+              if (!collection)
+                return filter;
+
+              collection.push(filter);
+            }
+          }
+        }
+      }
+    }
+
+    return null;
+  }
+
   /**
    * 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]
    * @param {?Array.<Filter>} [collection] An optional list of filters to which
    *   to append any results. If specified, the function adds <em>all</em>
    *   matching filters to the list; if omitted, the function directly returns
    *   the first matching filter.
    * @returns {?Filter}
    * @protected
    */
   checkEntryMatch(keyword, location, typeMask, docDomain, thirdParty, sitekey,
                   specificOnly, collection)
   {
     // We need to skip the simple (location-only) filters if the type mask does
     // not contain any default content types.
     if ((typeMask & DEFAULT_TYPES) != 0)
     {
-      let simpleSet = this._simpleFiltersByKeyword.get(keyword);
-      if (simpleSet)
-      {
-        let lowerCaseLocation = location.toLowerCase();
-
-        for (let filter of simpleSet)
-        {
-          if (specificOnly && !(filter instanceof WhitelistFilter))
-            continue;
-
-          if (filter.matchesLocation(location, lowerCaseLocation))
-          {
-            if (!collection)
-              return filter;
-
-            collection.push(filter);
-          }
-        }
-      }
+      let filter = this._checkEntryMatchSimple(keyword, location, typeMask,
+                                               docDomain, thirdParty, sitekey,
+                                               specificOnly, collection);
+      if (filter)
+        return filter;
     }
 
-    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)
     {
-      let map = this._filterMapsByType.get(typeMask);
-      if (map)
-        complexSet = map.get(keyword);
-    }
-    else
-    {
-      complexSet = this._complexFiltersByKeyword.get(keyword);
+      return this._checkEntryMatchForType(keyword, location, typeMask,
+                                          docDomain, thirdParty, sitekey,
+                                          specificOnly, collection);
     }
 
-    if (complexSet)
-    {
-      for (let filter of complexSet)
-      {
-        if (specificOnly && filter.isGeneric() &&
-            !(filter instanceof WhitelistFilter))
-          continue;
-
-        if (filter.matches(location, typeMask, docDomain, thirdParty, sitekey))
-        {
-          if (!collection)
-            return filter;
-
-          collection.push(filter);
-        }
-      }
-    }
-
-    return null;
+    return this._checkEntryMatchByDomain(keyword, location, typeMask,
+                                         docDomain, thirdParty, sitekey,
+                                         specificOnly, collection);
   }
 
   /**
    * 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]
    *   domain name of the document that loads the URL
@@ skipping 299 matching lines @@
 
 exports.CombinedMatcher = CombinedMatcher;
 
 /**
  * Shared {@link CombinedMatcher} instance that should usually be used.
  * @type {CombinedMatcher}
  */
 let defaultMatcher = new CombinedMatcher();
 
 exports.defaultMatcher = defaultMatcher;