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
@@ skipping 24 matching lines @@
  * 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
  * @returns {string[]}
  */
 function getConditionalGenericSelectors()
 {
-  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.size == 0 ||

[Manish Jethani, 2018/05/07 16:15:08]

Right now some selectors are disabled on all domains if AA is enabled. There's
no other way to do this. But in case in the future the size comes down to 0, it
should help.

-        !genericExceptionSelectors.has(selector))
-    {
-      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))
-          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)
-        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);
 
       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))

[kzar, 2018/05/08 13:46:47]

I don't quite understand how your change speeds things up. Aren't we pretty much
doing the same check in isDomainKnown as we were before (checking if the domain
part is present in filtersByDomain)? 

If calling .has instead of .get or similar is helping couldn't we add that check
into this loop instead of having a duplicate loop out in the isDomainKnown
function?

[Manish Jethani, 2018/05/08 14:20:43]

Let me come back with an answer after investigating this a little more.

[Manish Jethani, 2018/05/08 15:49:00]

Alright, I checked.

Fifty percent of the speedup is owning to the fact that it's a separate
function. This means we could start by separating out the existing while loop
into its own function. I'll make a patch for that.

The remaining is mainly owing to the fact that we don't call this.getException
for unknown domains, because we already know that there are no domain-specific
exceptions; instead we just do a lookup in the genericExceptionSelectors set for
the filter's selector, which is much, much faster. Other minor things are that
we don't create a set object and access its size property and "potentially" (but
never in fact because it's an unknown domain, but the JS runtime doesn't know
this) its has method.

Another factor might be that we only get the keys of the filters map, whereas in
the case of known domains we also get the values (isIncluded), which might be
slower. I haven't checked specifically for this though.

So we might end up with two functions, for known and unknown domains
respectively:

  getConditionalSelectorsForDomain(domain, specificOnly)
  getConditionalGenericSelectors()

We might be able to combine these into one function (if there's no domain
specified then it's the same as the second case?), depending on how much cleaner
it is and how much it affects performance.

[kzar, 2018/05/08 17:13:43]

Interesting, I wonder why that is. Is something in this function causing it to
deoptimise?
I wonder why getException is slower than your new logic. In other words I wonder
if we could make use of your tweak to filtersByDomain (storing null for
exceptions) in the getException function instead.

[Manish Jethani, 2018/05/08 17:37:13]

Yes, I found out:

https://codereview.adblockplus.org/29774573/

See the first comment on that patch. It was that we were modifying the
unconditional selectors array. My suggestion is to use concatenation of two
arrays.
Let me look into that.

[Manish Jethani, 2018/05/08 17:49:30]

getException should really be called hasException and return boolean. If the
domain is unknown (has no entry in filtersByDomain), it should check
genericExceptionSelectors instead of doing the usual stuff.

Or the caller could take care of this, either way.

Anyway I have something in mind here so I'll update the patch tomorrow after
rebasing on #29774573. We should land that one first since the benefits are more
obvious.

-    {
-      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());

[kzar, 2018/05/08 13:46:47]

Won't selectors always be [] here? I wonder why we concat the two lists together
instead of just returning getConditionalGenericSelectors().

[Manish Jethani, 2018/05/08 14:20:43]

No, the selectors array will contain the unconditional selectors, which is
actually most selectors.

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

[kzar, 2018/05/08 17:13:44]

Ah yea, gotya.

-    }
-
-    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));
   }
 };