Issue 6652 - Implement fast selector lookups for unknown domains

lib/elemHide.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 Element hiding implementation.
  */
 
 const {ElemHideException} = require("./filterClasses");
 const {FilterNotifier} = require("./filterNotifier");
 
 /**
  * Lookup table, active flag, by filter by domain.
  * (Only contains filters that aren't unconditionally matched for all domains.)
  * @type {Map.<string,?Map.<Filter,boolean>>}

[Manish Jethani, 2018/05/07 16:03:02]

The value here can now be null.

  */
 let filtersByDomain = new Map();
 
 /**
  * Lookup table, filter by selector. (Only used for selectors that are
  * unconditionally matched for all domains.)
  * @type {Map.<string,Filter>}
  */
 let filterBySelector = new Map();
 
 /**
  * This array caches the keys of filterBySelector table (selectors
  * which unconditionally apply on all domains). It will be null if the
  * cache needs to be rebuilt.
+ * @type {?string[]}
  */
 let unconditionalSelectors = null;
 
 /**
  * Map to be used instead when a filter has a blank domains property.
+ * @type {Map.<string,boolean>}
+ * @const
  */
 let defaultDomains = new Map([["", true]]);
 
 /**
  * Set containing known element hiding and exception filters
  * @type {Set.<ElemHideBase>}
  */
 let knownFilters = new Set();
 
 /**
  * Lookup table, lists of element hiding exceptions by selector
- * @type {Map.<string,Filter>}
+ * @type {Map.<string,Filter[]>}
  */
 let exceptions = new Map();
 
-/*
- * Set containing selectors with generic exceptions
- * @type {Set.<string>}
- */
-let genericExceptionSelectors = new Set();
-
-/*
- * Checks if a domain is known
- * @param {string} domain
- * @returns {boolean}
- */
-function isDomainKnown(domain)
+/**
+ * Lookup table, lists of generic element hiding exceptions by selector
+ * @type {Map.<string,Filter[]>}
+ */
+let genericExceptions = new Map();
+
+/**
+ * List of selectors that apply on any unknown domain
+ * @type {?string[]}
+ */
+let conditionalGenericSelectors = null;
+
+/**
+ * Adds a filter to the lookup table of filters by domain.
+ * @param {Filter} filter
+ */
+function addToFiltersByDomain(filter)
 {
+  let domains = filter.domains || defaultDomains;
+  if (filter instanceof ElemHideException)
+  {
+    for (let domain of domains.keys())
+    {
+      // Add an entry for each domain, but without any filters. This makes
+      // the domain "known" and helps us avoid certain optimizations that
+      // would otherwise yield incorrect results.
+      if (domain != "" && !filtersByDomain.has(domain))
+        filtersByDomain.set(domain, null);
+    }
+  }
+  else
+  {
+    for (let [domain, isIncluded] of domains)
+    {
+      // There's no need to note that a filter is generically disabled.
+      if (!isIncluded && domain == "")
+        continue;
+
+      let filters = filtersByDomain.get(domain);
+      if (!filters)
+        filtersByDomain.set(domain, filters = new Map());
+      filters.set(filter, isIncluded);
+    }
+  }
+}
+
+/**
+ * Returns a list of domain-specific filters matching a domain
+ * @param {string} [domain]
+ * @returns {Array.<?Map.<Filter,boolean>>}
+ */
+function getSpecificFiltersForDomain(domain)
+{
+  let filtersList = [];
+
+  if (domain)
+    domain = domain.toUpperCase();
+
   while (domain)
   {
-    // A domain is "known" if we have seen any filters that would apply to it.
-    // For example, given the filters "##foo" and "example.com#@#foo",
-    // example.com is a known domain, as is mail.example.com and any other
-    // subdomains of example.com.
-    if (filtersByDomain.has(domain))
-      return true;
+    let filters = filtersByDomain.get(domain);
+    if (typeof filters != "undefined")
+      filtersList.push(filters);
 
     let nextDot = domain.indexOf(".");
     domain = nextDot == -1 ? null : domain.substring(nextDot + 1);
   }
 
-  return false;
+  return filtersList;
 }
 
-/*
+/**
+ * Returns a list of selectors that apply on a domain from a given list of
+ * filters
+ * @param {string} [domain]
+ * @param {Array.<?Map.<Filter,boolean>>} filtersList
+ * @param {Set.<Filter>} excludeSet
+ * @returns {string[]}
+ */
+function matchSelectors(domain, filtersList, excludeSet)
+{
+  let matches = [];
+
+  // This code is a performance hot-spot, which is why we've made certain
+  // micro-optimisations. Please be careful before making changes.
+  for (let i = 0; i < filtersList.length; i++)
+  {
+    let filters = filtersList[i];
+    if (filters)
+    {
+      for (let [filter, isIncluded] of filters)
+      {
+        if (!isIncluded)
+        {
+          excludeSet.add(filter);
+        }
+        else if ((excludeSet.size == 0 || !excludeSet.has(filter)) &&
+                  !exports.ElemHide.getException(filter, domain))
+        {
+          matches.push(filter.selector);
+        }
+      }
+    }
+  }
+
+  return matches;
+}
+
+/**
  * Returns a list of selectors that apply on any unknown domain

[Manish Jethani, 2018/05/07 16:03:02]

There are generic selectors that are "conditional" (don't apply on all domains)
that would still apply on any unknown domain. For example,
"~foo.example.com##foo" would apply on all but foo.example.com, but if the
domain we're looking up for is example.com ("unknown" domain) then it's as good
as unconditional.

  * @returns {string[]}
  */
 function getConditionalGenericSelectors()

[Manish Jethani, 2018/05/07 16:10:33]

To give you some numbers, there are 18,300 unconditional selectors, 1,095
conditional generic selectors, and 16 generic exceptions in  in EasyList+AA.

So when you call ElemHide.getSelectorsForDomain on x4aabd7c0ddcd (unknown
domain), first the list is populated with 18,300 selectors right away, then
1,095 selectors are added to it, after filtering out 16 generic exceptions from
the actual 1,111 selectors.

 {
-  let selectors = [];
+  if (conditionalGenericSelectors)
+    return conditionalGenericSelectors;
+
+  conditionalGenericSelectors = [];
 
   let filters = filtersByDomain.get("");
   if (!filters)
-    return selectors;
+    return conditionalGenericSelectors;
 
   for (let {selector} of filters.keys())
   {
-    if (!genericExceptionSelectors.has(selector))

[Manish Jethani, 2018/05/07 16:03:02]

Here we have to check for generic exceptions like "#@#foo", which would disable
"~foo.example.com##foo"  on all domains (known or unknown).

There are 16 such generic exceptions in EasyList+AA.

-      selectors.push(selector);
-  }
-
-  return selectors;
+    if (genericExceptions.size == 0 || !genericExceptions.has(selector))
+      conditionalGenericSelectors.push(selector);
+  }
+
+  return conditionalGenericSelectors;
+}
+
+/**
+ * Returns a list of selectors that apply on each website unconditionally.
+ * @returns {string[]}
+ */
+function getUnconditionalSelectors()
+{
+  if (!unconditionalSelectors)
+    unconditionalSelectors = [...filterBySelector.keys()];
+
+  return unconditionalSelectors;
 }
 
 /**
  * Container for element hiding filters
  * @class
  */
-let ElemHide = exports.ElemHide = {
+exports.ElemHide = {
   /**
    * Removes all known filters
    */
   clear()
   {
     for (let collection of [filtersByDomain, filterBySelector,
                             knownFilters, exceptions,
-                            genericExceptionSelectors])
+                            genericExceptions])
     {
       collection.clear();
     }
     unconditionalSelectors = null;
+    conditionalGenericSelectors = null;
     FilterNotifier.emit("elemhideupdate");
-  },
-
-  _addToFiltersByDomain(filter)
-  {
-    let domains = filter.domains || defaultDomains;
-    if (filter instanceof ElemHideException)
-    {
-      for (let domain of domains.keys())
-      {
-        // Add an entry for each domain, but without any filters. This makes
-        // the domain "known" and helps us avoid the optimized path (which
-        // would give incorrect results).
-        if (domain != "" && !filtersByDomain.has(domain))

[Manish Jethani, 2018/05/07 16:03:02]

We could have had a separate knownExceptionDomains set. I'm not sure it's worth
it though, it's just easier to add a null entry here in filtersByDomain. Less
maintenance.

-          filtersByDomain.set(domain, null);
-      }
-    }
-    else
-    {
-      for (let [domain, isIncluded] of domains)
-      {
-        // There's no need to note that a filter is generically disabled.
-        if (!isIncluded && domain == "")
-          continue;
-
-        let filters = filtersByDomain.get(domain);
-        if (!filters)
-          filtersByDomain.set(domain, filters = new Map());
-        filters.set(filter, isIncluded);
-      }
-    }
   },
 
   /**
    * Add a new element hiding filter
    * @param {ElemHideBase} filter
    */
   add(filter)
   {
     if (knownFilters.has(filter))
       return;
 
+    conditionalGenericSelectors = null;
+
     if (filter instanceof ElemHideException)
     {
       let {selector, domains} = filter;
 
       let list = exceptions.get(selector);
       if (list)
         list.push(filter);
       else
         exceptions.set(selector, [filter]);
 
       if (domains)

[Manish Jethani, 2018/05/07 16:03:02]

For exceptions too we should remember the domains, otherwise an exception like
"foo.example.com#@#foo" will not be taken into account and the generic filter
"##foo" will be applied to "foo.example.com" (since it would be considered to be
an unknown domain). In this example we have to make sure that "foo.example.com"
is a known domain.

I've also updated the tests to check for this.

-        this._addToFiltersByDomain(filter);
+        addToFiltersByDomain(filter);
 
       if (filter.isGeneric())
-        genericExceptionSelectors.add(filter.selector);
+      {
+        list = genericExceptions.get(selector);
+        if (list)
+          list.push(filter);
+        else
+          genericExceptions.set(selector, [filter]);
+      }
 
       // If this is the first exception for a previously unconditionally
       // applied element hiding selector we need to take care to update the
       // lookups.
       let unconditionalFilterForSelector = filterBySelector.get(selector);
       if (unconditionalFilterForSelector)
       {
-        this._addToFiltersByDomain(unconditionalFilterForSelector);
+        addToFiltersByDomain(unconditionalFilterForSelector);
         filterBySelector.delete(selector);
         unconditionalSelectors = null;
       }
     }
     else if (!(filter.domains || exceptions.has(filter.selector)))
     {
       // The new filter's selector is unconditionally applied to all domains
       filterBySelector.set(filter.selector, filter);
       unconditionalSelectors = null;
     }
     else
     {
       // The new filter's selector only applies to some domains
-      this._addToFiltersByDomain(filter);
+      addToFiltersByDomain(filter);
     }
 
     knownFilters.add(filter);
     FilterNotifier.emit("elemhideupdate");
   },
 
   /**
    * Removes an element hiding filter
    * @param {ElemHideBase} filter
    */
   remove(filter)
   {
     if (!knownFilters.has(filter))
       return;
 
+    conditionalGenericSelectors = null;
+
     // Whitelisting filters
     if (filter instanceof ElemHideException)
     {
       let list = exceptions.get(filter.selector);
       let index = list.indexOf(filter);
       if (index >= 0)
         list.splice(index, 1);
 

[Manish Jethani, 2018/05/07 16:03:02]

Note that we don't bother "unknowing" a domain once we know it. It's OK, this is
an optimization anyway. It will still work for most domains out there.

       if (filter.isGeneric())
-        genericExceptionSelectors.delete(filter.selector);
+      {
+        list = genericExceptions.get(filter.selector);
+        index = list.indexOf(filter);
+        if (index >= 0)
+          list.splice(index, 1);
+
+        // It's important to delete the entry here so the selector no longer
+        // appears to have any generic exceptions.
+        if (list.length == 0)
+          genericExceptions.delete(filter.selector);
+      }
     }
     // Unconditially applied element hiding filters
     else if (filterBySelector.get(filter.selector) == filter)
     {
       filterBySelector.delete(filter.selector);
       unconditionalSelectors = null;
     }
     // Conditionally applied element hiding filters
     else
     {
       let domains = filter.domains || defaultDomains;
       for (let domain of domains.keys())
       {
         let filters = filtersByDomain.get(domain);
         if (filters)
           filters.delete(filter);
       }
     }
 
     knownFilters.delete(filter);
     FilterNotifier.emit("elemhideupdate");
   },
 
   /**
    * Checks whether an exception rule is registered for a filter on a particular
    * domain.
    * @param {Filter} filter
-   * @param {string} docDomain
-   * @return {ElemHideException}
+   * @param {?string} docDomain
+   * @return {?ElemHideException}
    */
   getException(filter, docDomain)
   {
     let list = exceptions.get(filter.selector);
     if (!list)
       return null;
 
     for (let i = list.length - 1; i >= 0; i--)
     {
       if (list[i].isActiveOnDomain(docDomain))
         return list[i];
     }
 
     return null;
   },
-
-  /**
-   * Returns a list of selectors that apply on each website unconditionally.
-   * @returns {string[]}
-   */
-  getUnconditionalSelectors()
-  {
-    if (!unconditionalSelectors)
-      unconditionalSelectors = [...filterBySelector.keys()];
-    return unconditionalSelectors.slice();
-  },
-
-  /**
-   * Constant used by getSelectorsForDomain to return all selectors applying to
-   * a particular hostname.
-   */
-  ALL_MATCHING: 0,
-
-  /**
-   * Constant used by getSelectorsForDomain to exclude selectors which apply to
-   * all websites without exception.
-   */
-  NO_UNCONDITIONAL: 1,
-
-  /**
-   * Constant used by getSelectorsForDomain to return only selectors for filters
-   * which specifically match the given host name.
-   */
-  SPECIFIC_ONLY: 2,
 
   /**
    * Determines from the current filter list which selectors should be applied
    * on a particular host name.
    * @param {string} domain
-   * @param {number} [criteria]
-   *   One of the following: ElemHide.ALL_MATCHING, ElemHide.NO_UNCONDITIONAL or
-   *                         ElemHide.SPECIFIC_ONLY.
-   * @returns {string[]}
-   *   List of selectors.
+   * @param {boolean} [specificOnly] true if generic filters should not apply.
+   * @returns {string[]} List of selectors.
    */
-  getSelectorsForDomain(domain, criteria)
-  {
-    let selectors = [];
-
-    if (typeof criteria == "undefined")
-      criteria = ElemHide.ALL_MATCHING;
-    if (criteria < ElemHide.NO_UNCONDITIONAL)
-      selectors = this.getUnconditionalSelectors();
-
-    let specificOnly = (criteria >= ElemHide.SPECIFIC_ONLY);
-    let currentDomain = domain ? domain.toUpperCase() : "";
-
-    if (isDomainKnown(currentDomain))

[Manish Jethani, 2018/05/07 16:03:02]

The call to isDomainKnown is the only additional cost now for known domains;
otherwise, for a known domain, the code is the same.

Based on my tests this call is not too expensive. We can also optimize it
further, for example by adding the looked up domain once we've determined it to
be known (e.g. when we look up "foo.example.com" and only "example.com" is in
the filtersByDomain map, we can add "foo.example.com" so it's looked up faster
next time).

-    {
-      let excluded = new Set();
-
-      // This code is a performance hot-spot, which is why we've made certain
-      // micro-optimisations. Please be careful before making changes.
-      while (true)
-      {
-        if (specificOnly && currentDomain == "")
-          break;
-
-        let filters = filtersByDomain.get(currentDomain);
-        if (filters)
-        {
-          for (let [filter, isIncluded] of filters)
-          {
-            if (!isIncluded)
-            {
-              excluded.add(filter);
-            }
-            else if ((excluded.size == 0 || !excluded.has(filter)) &&
-                     !this.getException(filter, domain))
-            {
-              selectors.push(filter.selector);
-            }
-          }
-        }
-
-        if (currentDomain == "")
-          break;
-
-        let nextDot = currentDomain.indexOf(".");
-        currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
-      }
-    }
-    else if (!specificOnly)
-    {
-      selectors = selectors.concat(getConditionalGenericSelectors());

[Manish Jethani, 2018/05/07 16:03:02]

We might want to cache the value returned by getConditionalGenericSelectors,
since it's the same each time (unless filters are added or removed), but I
decided to avoid the additional bookkeeping for now. We can investigate this
separately. I also have other ideas for efficiently caching results.

-    }
-
-    return selectors;
+  getSelectorsForDomain(domain, specificOnly = false)
+  {
+    let specificFilters = getSpecificFiltersForDomain(domain);
+
+    // If there are no specific filters (nor any specific exceptions), we can
+    // just return the selectors from all the generic filters modulo any
+    // generic exceptions.
+    if (specificFilters.length == 0)
+    {
+      return specificOnly ? [] :
+               getUnconditionalSelectors()
+               .concat(getConditionalGenericSelectors());
+    }
+
+    let excluded = new Set();
+    let selectors = matchSelectors(domain, specificFilters, excluded);
+
+    if (specificOnly)
+      return selectors;
+
+    return getUnconditionalSelectors()
+           .concat(selectors,
+                   matchSelectors(domain, [filtersByDomain.get("")],
+                                  excluded));
   }
 };