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 60 matching lines @@
  */
 let genericExceptions = new Map();
 
 /**
  * List of selectors that apply on any unknown domain
  * @type {?string[]}
  */
 let conditionalGenericSelectors = null;
 
 /**
- * Domains that are known not to be specifically excluded from any generic
- * filters
- * @type {Set.<string>}
- */
-let genericFriendlyDomains = new Set();
+ * 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)
   {
-    // Note that we also push null values into the list, because
-    // ElemHide.getSelectorsForDomain still needs to know if there are any
-    // entries for the domain.
     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 filtersList;
 }
 
 /**
- * Returns a list of selectors from a given list of filters that apply on a
- * domain
+ * 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 {boolean} specificOnly
+ * @param {Set.<Filter>} excludeSet
  * @returns {string[]}
  */
-function getConditionalSelectorsForDomain(domain, filtersList, specificOnly)
+function matchSelectors(domain, filtersList, excludeSet)
 {
-  let selectors = [];
-
-  let genericFilters = !specificOnly ? filtersList.pop() : null;
-  let excluded = new Set();
+  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++)
   {
-    if (!filtersList[i])
-      continue;
-
-    for (let [filter, isIncluded] of filtersList[i])
-    {
-      if (!isIncluded)
+    let filters = filtersList[i];
+    if (filters)
+    {
+      for (let [filter, isIncluded] of filters)
       {
-        excluded.add(filter);
+        if (!isIncluded)
+        {
+          excludeSet.add(filter);
+        }
+        else if ((excludeSet.size == 0 || !excludeSet.has(filter)) &&
+                  !exports.ElemHide.getException(filter, domain))
+        {
+          matches.push(filter.selector);
+        }
       }
-      else if ((excluded.size == 0 || !excluded.has(filter)) &&
-               !ElemHide.getException(filter, domain))
-      {
-        selectors.push(filter.selector);
-      }
-    }
-  }
-
-  if (!genericFilters)
-    return selectors;
-
-  if (genericFriendlyDomains.has(domain))
-    return selectors.concat(getConditionalGenericSelectors());
-
-  let genericSelectors = [];
-
-  for (let filter of genericFilters.keys())
-  {
-    if ((excluded.size == 0 || !excluded.has(filter)) &&
-        !ElemHide.getException(filter, domain))
-    {
-      genericSelectors.push(filter.selector);
-    }
-  }
-
-  // If the number of conditional generic selectors that apply on this domain
-  // is the same as the total number of conditional generic selectors, the
-  // domain is "generic friendly". In that case, we mark it is as such for
-  // faster lookups.
-  if (conditionalGenericSelectors &&
-      genericSelectors.length == conditionalGenericSelectors.length)
-  {
-    genericFriendlyDomains.add(domain);

[Manish Jethani, 2018/05/11 10:00:32]

Most domains will fall in this category.

We might have to limit the size of this set, but then again this can only be a
domain that occurs specifically in a subscription or a subdomain of such a
domain.

[Manish Jethani, 2018/05/11 10:09:09]

Done.

-  }
-
-  return selectors.concat(genericSelectors);
+    }
+  }
+
+  return matches;
 }
 
 /**
  * Returns a list of selectors that apply on any unknown domain
  * @returns {string[]}
  */
 function getConditionalGenericSelectors()
 {
   if (conditionalGenericSelectors)
     return conditionalGenericSelectors;
@@ skipping 22 matching lines @@
   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,
-                            genericExceptions, genericFriendlyDomains])
+                            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 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);
-      }
-    }
   },
 
   /**
    * Add a new element hiding filter
    * @param {ElemHideBase} filter
    */
   add(filter)
   {
     if (knownFilters.has(filter))
       return;
 
     conditionalGenericSelectors = null;
-    genericFriendlyDomains.clear();
 
     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())
       {
         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;
-    genericFriendlyDomains.clear();
 
     // 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())
       {
         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;
     }
@@ skipping 29 matching lines @@
     for (let i = list.length - 1; i >= 0; i--)
     {
       if (list[i].isActiveOnDomain(docDomain))
         return list[i];
     }
 
     return null;
   },
 
   /**
-   * Constant used by getSelectorsForDomain to return all selectors applying to
-   * a particular hostname.
-   * @type {number}
-   * @const
-   */
-  ALL_MATCHING: 0,
-
-  /**
-   * Constant used by getSelectorsForDomain to exclude selectors which apply to
-   * all websites without exception.
-   * @type {number}
-   * @const
-   */
-  NO_UNCONDITIONAL: 1,
-
-  /**
-   * Constant used by getSelectorsForDomain to return only selectors for filters
-   * which specifically match the given host name.
-   * @type {number}
-   * @const
-   */
-  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 = ElemHide.ALL_MATCHING)
-  {
-    let selectors = [];
-
-    let specificOnly = criteria >= ElemHide.SPECIFIC_ONLY;
-    let filtersList = getSpecificFiltersForDomain(domain);
-
-    if (filtersList.length > 0)
-    {
-      if (!specificOnly)
-        filtersList.push(filtersByDomain.get(""));
-
-      selectors = getConditionalSelectorsForDomain(domain, filtersList,
-                                                   specificOnly);
-    }
-    else if (!specificOnly)
-    {
-      selectors = getConditionalGenericSelectors();
-    }
-
-    if (criteria < ElemHide.NO_UNCONDITIONAL)
-      selectors = getUnconditionalSelectors().concat(selectors);
-
-    // If the above logic leaves us with a reference to our internal cache of
-    // selectors, we make a copy here.
-    if (selectors == conditionalGenericSelectors)
-      selectors = selectors.slice();
-
-    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));
   }
 };