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
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 "use strict";
 
 /**
  * @fileOverview Element hiding implementation.
  */
 
 const {ElemHideException} = require("./filterClasses");
 const {FilterNotifier} = require("./filterNotifier");
 
 /**
  * Lookup table, active flag, by filter by domain.
  * (Only contains filters that aren't unconditionally matched for all domains.)
- * @type {Map.<string,Map.<Filter,boolean>>}
+ * @type {Map.<string,?Map.<Filter,boolean>>}
  */
 let filtersByDomain = new Map();
 
 /**
  * Lookup table, filter by selector. (Only used for selectors that are
  * unconditionally matched for all domains.)
  * @type {Map.<string,Filter>}
  */
 let filterBySelector = new Map();
 
@@ skipping 13 matching lines @@
 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();
 
 /**
+ * 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;
+
+/**
+ * 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;
-  for (let [domain, isIncluded] of domains)
+  if (filter instanceof ElemHideException)
   {
-    // There's no need to note that a filter is generically disabled.
-    if (!isIncluded && domain == "")
+    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
+ * @param {string} [domain]
+ * @param {Array.<?Map.<Filter,boolean>>} filtersList
+ * @param {boolean} specificOnly
+ * @returns {string[]}
+ */
+function getConditionalSelectorsForDomain(domain, filtersList, specificOnly)
+{
+  let selectors = [];
+
+  let genericFilters = !specificOnly ? filtersList.pop() : null;
+  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.
+  for (let i = 0; i < filtersList.length; i++)
+  {
+    if (!filtersList[i])
       continue;
 
-    let filters = filtersByDomain.get(domain);
-    if (!filters)
-      filtersByDomain.set(domain, filters = new Map());
-    filters.set(filter, isIncluded);
+    for (let [filter, isIncluded] of filtersList[i])
+    {
+      if (!isIncluded)
+      {
+        excluded.add(filter);
+      }
+      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)
+  {
+    if (genericFriendlyDomains.size >= 1000)
+      genericFriendlyDomains.clear();
+
+    genericFriendlyDomains.add(domain);
+  }
+
+  return selectors.concat(genericSelectors);
+}
+
+/**
+ * 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 = {
   /**
    * Removes all known filters
    */
   clear()
   {
     for (let collection of [filtersByDomain, filterBySelector,
-                            knownFilters, exceptions])
+                            knownFilters, exceptions,
+                            genericExceptions, genericFriendlyDomains])
     {
       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} = filter;
+      let {selector, domains} = filter;
+
       let list = exceptions.get(selector);
       if (list)
         list.push(filter);
       else
         exceptions.set(selector, [filter]);
 
+      if (domains)
+        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)
       {
         addToFiltersByDomain(unconditionalFilterForSelector);
         filterBySelector.delete(selector);
         unconditionalSelectors = null;
       }
@@ skipping 16 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())
+      {
+        list = genericExceptions.get(filter.selector);
+        index = list.indexOf(filter);
+        if (index >= 0)
+          list.splice(index, 1);
+
+        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
     {
@@ skipping 63 matching lines @@
    * @param {number} [criteria]
    *   One of the following: ElemHide.ALL_MATCHING, ElemHide.NO_UNCONDITIONAL or
    *                         ElemHide.SPECIFIC_ONLY.
    * @returns {string[]}
    *   List of selectors.
    */
   getSelectorsForDomain(domain, criteria = ElemHide.ALL_MATCHING)
   {
     let selectors = [];
 
-    let specificOnly = (criteria >= ElemHide.SPECIFIC_ONLY);
-    let excluded = new Set();
-    let currentDomain = domain ? domain.toUpperCase() : "";
+    let specificOnly = criteria >= ElemHide.SPECIFIC_ONLY;
+    let filtersList = getSpecificFiltersForDomain(domain);
 
-    // 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 (filtersList.length > 0)
     {
-      if (specificOnly && currentDomain == "")
-        break;
+      if (!specificOnly)
+        filtersList.push(filtersByDomain.get(""));
 
-      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);
+      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;
   }
 };