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();
-
-/*
+/**
+ * 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)
   {
-    // 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 {Set.<Filter>} excludeSet
  * @returns {string[]}
  */
-function getConditionalSelectorsForDomain(domain, filtersList)
+function matchSelectors(domain, filtersList, excludeSet)
 {
-  let selectors = [];
-
-  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);
-      }
-    }
-  }
-
-  return selectors;
+    }
+  }
+
+  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 ||
-        !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 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;
+
     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;
   },
-
-  /**
-   * 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;
-
-    let specificOnly = criteria >= ElemHide.SPECIFIC_ONLY;
-    let filtersList = getSpecificFiltersForDomain(domain);
-
-    if (filtersList.length > 0)
-    {
-      // We only got domain-specific filters, now add the generic filters.
-      if (!specificOnly)
-        filtersList.push(filtersByDomain.get(""));
-
-      selectors = getConditionalSelectorsForDomain(domain, filtersList);
-    }
-    else if (!specificOnly)
-    {
-      // Since there are no domain-specific filters matching this domain, we
-      // can follow an optimized code path where we only check for generic
-      // filters and generic exceptions.
-      selectors = getConditionalGenericSelectors();
-    }
-
-    if (criteria < ElemHide.NO_UNCONDITIONAL)
-      selectors = getUnconditionalSelectors().concat(selectors);
-
-    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));
   }
 };