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 43 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[]>}

[kzar, 2018/05/15 13:26:31]

I guess you need to rebase again.

[Manish Jethani, 2018/05/15 16:00:08]

Done.

  */
 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;

[kzar, 2018/05/15 13:26:31]

I think this cache is probably a good idea. I figure it should have a name more
like unknownDomainSelectors though. Also I wonder if we could avoid duplicating
what's already cached in unconditionalSelectors?

[Manish Jethani, 2018/05/15 16:00:07]

It also applies to known domains (see my other comment as well as the patch
description); these are generic selectors that apply to most domains but not all
domains.
This cache does not include those selectors, it only has "conditional generic"
selectors. The criterion for a selector to be in this cache is that it should
apply on most domains, even most "known" domains, but it would still have
exceptions for some domains. e.g. ~example.com###foo", or "##foo" and then
"example.com#@##foo" (separate filter list like AA).

Also see this comment for numbers:

https://codereview.adblockplus.org/29773570#msg3

 
 /**
- * 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())
     {
       // 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);

[kzar, 2018/05/15 13:26:30]

Am I missing something or do we never remove the domain from filtersByDomain
again? I guess previously it wasn't significant if a domain was left with an
empty Map entry, but now it means something if filtersByDomain.has(domain).

Anyway, I like this part of your change, reusing filtersByDomain for the
unknown/known domain check seems like a good idea.

[Manish Jethani, 2018/05/15 16:00:08]

You're right, we never remove a domain like that from filtersByDomain. This
means that if a domain was previously known, it never becomes unknown. That's
fine, it would still end up in the genericFriendlyDomains set because no
domain-specific exceptions would apply, so the performance would be the same for
generic filters. Part of the optimization would be disabled for such a domain
because we would still go looking for domain-specific filters (and we might find
none). I think that's OK. Otherwise we would have to do more bookkeeping and I
don't think it's worth it.

In a typical browsing sessions you're not going add and remove individual filter
lists anyway. I'm guessing when filters lists are downloaded the clear method is
called and everything is repopulated again anyway. Correct me if I'm wrong.

[kzar, 2018/05/18 14:34:53]

Acknowledged.

     }
   }
   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)) &&
-         !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)

[Manish Jethani, 2018/05/15 16:20:59]

Note: getSpecificFiltersForDomain could be reused by ElemHideEmulation with
minor modifications here and elsewhere (mainly checking for the type property of
the Filter object).

[kzar, 2018/05/18 14:34:53]

Acknowledged.

 {
   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>}>}
+ * @param {Array.<?Map.<Filter,boolean>>} filtersList
  * @param {Set.<Filter>} excludeSet
  * @returns {string[]}
  */
 function matchSelectors(domain, filtersList, excludeSet)

[Manish Jethani, 2018/05/15 16:20:59]

Note: matchSelectors could be reused by ElemHideEmulation.

We could export these functions.

 {
   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].filters;
+    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();

[kzar, 2018/05/18 14:34:53]

Nit: Seems a waste to create a new empty Array when we already know we have one.

-
-  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 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);

[kzar, 2018/05/15 13:26:31]

I feel like some of these changes (like this one, moving the logic of
getSelectorsForDomain out into a different function) are just made for the sake
of it. I'd rather you only changed what was necessary.

[Manish Jethani, 2018/05/15 16:00:08]

Yeah this patch has been updated a lot. Now the function is almost empty.
Anyway, my rationale for doing it this way was that selectors is a combination
of unconditional and conditional selectors, there's already a dedicate function
for unconditional selectors. Let me inline getConditionalSelectorsForDomain in
my next update.

[Manish Jethani, 2018/05/15 16:16:15]

Actually there are three return statements (out of four) in
getConditionalGenericSelectors that would require a call to
getUnconditionalSelectors, because we need to concatenate that list as well.
Isn't that code duplication? This seems much cleaner to me. Otherwise we have to
make sure there's only one return statement, but then we would be adding
additional indentation and additional if-else logic just so we have only one
call to getUnconditionalSelectors at the end of the function.

What do you think?

[Manish Jethani, 2018/05/15 16:20:59]

I meant getConditionalSelectorsForDomain of course.

-
-    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));
   }
 };