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[]>}
  */
 let exceptions = new Map();
 
-/*
+/**
  * Lookup table, lists of generic element hiding exceptions by selector
  * @type {Map.<string,Filter[]>}
  */
 let genericExceptions = new Map();

[Manish Jethani, 2018/05/09 21:35:44]

This needs to be a map actually, because we want to delete individual filters
from this and only remove the key when the last filter been removed.

 
 /**
- * Checks whether a filter has an exception
+ * 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
- * @param {string} [domain]
- * @returns {boolean}
- */
-function hasException(filter, domain)
+ */
+function addToFiltersByDomain(filter)
 {
-  if (!domain)
-    return genericExceptions.has(filter.selector);
-
-  return !!ElemHide.getException(filter, domain);
+  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} genericOnly
+ * @param {Set.<Filter>} excludeSet
  * @returns {string[]}
  */
-function getConditionalSelectorsForDomain(domain, filtersList, genericOnly)
+function matchSelectors(domain, filtersList, excludeSet)
 {
-  let selectors = [];
-
-  let excluded = !genericOnly ? new Set() : null;
-  let domainForExceptionCheck = !genericOnly ? domain : null;
+  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 || excluded.size == 0 || !excluded.has(filter)) &&
-               !hasException(filter, domainForExceptionCheck))
-      {
-        selectors.push(filter.selector);
-      }
-    }
-  }
-
-  return selectors;
+    }
+  }
+
+  return matches;
+}
+
+/**
+ * Returns a list of selectors that apply on any unknown domain
+ * @returns {string[]}
+ */
+function getConditionalGenericSelectors()
+{
+  if (conditionalGenericSelectors)
+    return conditionalGenericSelectors;
+
+  conditionalGenericSelectors = [];
+
+  let filters = filtersByDomain.get("");
+  if (!filters)
+    return conditionalGenericSelectors;
+
+  for (let {selector} of filters.keys())
+  {
+    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,
                             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())
       {
         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())
       {
         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 10 matching lines @@
     }
 
     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)
-  {
-    if (typeof criteria == "undefined")
-      criteria = ElemHide.ALL_MATCHING;
-
-    let specificOnly = criteria >= ElemHide.SPECIFIC_ONLY;
-    let filtersList = getSpecificFiltersForDomain(domain);
-
-    let genericOnly = filtersList.length == 0;
-
-    if (!specificOnly)
-      filtersList.push(filtersByDomain.get(""));
-
-    let selectors = getConditionalSelectorsForDomain(domain, filtersList,
-                                                     genericOnly);
-
-    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));
   }
 };