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 13 matching lines @@
         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>}>}
+ * @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 from a given list of
  * filters
  * @param {string} [domain]
- * @param {Array.<{domain: string, filters: ?Map.<Filter,boolean>}>} filtersList
+ * @param {Array.<?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];
+    let filters = filtersList[i];
     if (filters)
     {
       for (let [filter, isIncluded] of filters)
       {
         if (!isIncluded)
+        {
           excludeSet.add(filter);
-        else if (doesFilterApply(filter, domain, excludeSet))
+        }
+        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 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;
@@ skipping 30 matching lines @@
  * @class
  */
 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 55 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 = getConditionalSelectorsForDomain(domain, specificOnly);
-
-    if (!specificOnly)
-      selectors = getUnconditionalSelectors().concat(selectors);
-
-    return selectors;
+    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));
   }
 };