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 18 matching lines @@
  */
 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();
+
+/**
+ * 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)
-  {
-    // There's no need to note that a filter is generically disabled.
-    if (!isIncluded && domain == "")
-      continue;
-
+  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);
+    }
+  }
+}
+
+
+/**
+ * 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)) &&
+         !exports.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>}>}
+ */
+function getSpecificFiltersForDomain(domain)
+{
+  let filtersList = [];
+
+  if (domain)
+    domain = domain.toUpperCase();
+
+  while (domain)
+  {
     let filters = filtersByDomain.get(domain);
-    if (!filters)
-      filtersByDomain.set(domain, filters = new Map());
-    filters.set(filter, isIncluded);
-  }
+    if (typeof filters != "undefined")
+      filtersList.push({domain, 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 from a given list of
+ * filters
+ * @param {string} [domain]
+ * @param {Array.<{domain: string, filters: ?Map.<Filter,boolean>}>} filtersList
+ * @param {Set.<Filter>} excludeSet
+ * @returns {string[]}
+ */
+function matchSelectors(domain, filtersList, excludeSet)
+{
+  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++)
+  {
+    let {filters} = filtersList[i];
+    if (filters)
+    {
+      for (let [filter, isIncluded] of filters)
+      {
+        if (!isIncluded)
+          excludeSet.add(filter);
+        else if (doesFilterApply(filter, domain, excludeSet))
+          matches.push(filter.selector);
+      }
+    }
+  }
+
+  return matches;
+}
+
+/**
+ * Returns a list of selectors that apply on a domain
+ * @param {string} [domain]
+ * @param {boolean} specificOnly
+ * @returns {string[]}
+ */
+function getConditionalSelectorsForDomain(domain, specificOnly)
+{
+  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 excludeSet = new Set();
+  let specificSelectors = matchSelectors(domain, specificFilters, excludeSet);
+
+  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 = [{filters: filtersByDomain.get("")}];
+  let genericSelectors = matchSelectors(domain, genericFilters, excludeSet);
+
+  // 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);
+}
+
+/**
+ * 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
  */
 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);
+
+        // 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
     {
@@ skipping 34 matching lines @@
 
   /**
    * Determines from the current filter list which selectors should be applied
    * on a particular host name.
    * @param {string} domain
    * @param {boolean} [specificOnly] true if generic filters should not apply.
    * @returns {string[]} List of selectors.
    */
   getSelectorsForDomain(domain, specificOnly = false)
   {
-    let selectors = [];
-
-    let excluded = new Set();
-    let currentDomain = domain ? domain.toUpperCase() : "";
-
-    // 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 (specificOnly && currentDomain == "")
-        break;
-
-      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);
-    }
+    let selectors = getConditionalSelectorsForDomain(domain, specificOnly);
 
     if (!specificOnly)
       selectors = getUnconditionalSelectors().concat(selectors);
 
     return selectors;
   }
 };