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())
     {
@@ skipping 14 matching lines @@
 
       let filters = filtersByDomain.get(domain);
       if (!filters)
         filtersByDomain.set(domain, filters = new Map());
       filters.set(filter, isIncluded);
     }
   }
 }
 
 /**
- * Checks whether a filter applies on a domain
- * @param {Filter} filter
- * @param {string} [domain]
- * @param {Set.<Filter>} excludeSet
- * @returns {boolean}
- */
-function doesFilterApply(filter, domain, excludeSet)
-{
-  return (excludeSet.size == 0 || !excludeSet.has(filter)) &&
-         !ElemHide.getException(filter, domain);
-}
-
-/**
  * Returns a list of domain-specific filters matching a domain
  * @param {string} [domain]
- * @returns {Array.<{domain: string, filters: ?Map.<Filter,boolean>}>}
+ * @returns {Array.<?Map.<Filter,boolean>>}
  */
 function getSpecificFiltersForDomain(domain)
 {
   let filtersList = [];
 
   if (domain)
     domain = domain.toUpperCase();
 
   while (domain)
   {
     let filters = filtersByDomain.get(domain);
     if (typeof filters != "undefined")
-      filtersList.push({domain, filters});
+      filtersList.push(filters);
 
     let nextDot = domain.indexOf(".");
     domain = nextDot == -1 ? null : domain.substring(nextDot + 1);
   }
 
   return filtersList;
 }
 
 /**
- * Returns a list of selectors 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 {boolean} specificOnly
+ * @param {Array.<?Map.<Filter,boolean>>} filtersList
+ * @param {Set.<Filter>} excludeSet
  * @returns {string[]}
  */
-function getConditionalSelectorsForDomain(domain, specificOnly)
+function matchSelectors(domain, filtersList, excludeSet)
 {
-  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 ? [] : getConditionalGenericSelectors();
-
-  let specificSelectors = [];
-
-  let excludeSet = 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 < specificFilters.length; i++)
-  {
-    for (let [filter, isIncluded] of specificFilters[i].filters || [])
-    {
-      if (!isIncluded)
-        excludeSet.add(filter);
-      else if (doesFilterApply(filter, domain, excludeSet))
-        specificSelectors.push(filter.selector);
-    }
-  }
-
-  if (specificOnly)
-    return specificSelectors;
-
-  // We use the longest subdomain of this domain found in our data structures
-  // as the key to check if the domain is "generic friendly." For example,
-  // given foo.example.com, there may be an entry for example.com in our data
-  // structures (e.g. "example.com###foo"), so we use that subdomain as the
-  // key. This way we make only one entry and it works for all subdomains of
-  // example.com, except those that have specific entries
-  // (e.g. "~bar.example.com##.no-bar").
-  let domainKey = specificFilters[0].domain;
-
-  if (genericFriendlyDomains.has(domainKey))
-    return specificSelectors.concat(getConditionalGenericSelectors());
-
-  let genericFilters = filtersByDomain.get("");
-  if (!genericFilters)
-    return specificSelectors;
-
-  let genericSelectors = [];
-
-  for (let filter of genericFilters.keys())
-  {
-    if (doesFilterApply(filter, domain, excludeSet))
-      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" (i.e. all generic filters apply, except those
-  // with generic exceptions). In that case, we mark it is as such for faster
-  // lookups.
-  if (genericSelectors.length == (conditionalGenericSelectors || {}).length)
-    genericFriendlyDomains.add(domainKey);
-
-  return specificSelectors.concat(genericSelectors);
+  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()
 {
   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");
   },
 
   /**
    * 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]);
@@ skipping 40 matching lines @@
   /**
    * 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())
@@ skipping 47 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 specificOnly = criteria >= ElemHide.SPECIFIC_ONLY;
-    let selectors = getConditionalSelectorsForDomain(domain, specificOnly);
-
-    if (criteria < ElemHide.NO_UNCONDITIONAL)
-      selectors = getUnconditionalSelectors().concat(selectors);
-    else if (criteria == ElemHide.NO_UNCONDITIONAL)
-      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));
   }
 };