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

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

[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>}>}
+ */
+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 (!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>}>}
+ * @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;
+    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();

[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;
+
+  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);
+
+        // 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 61 matching lines @@
    * 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.
    */
   getSelectorsForDomain(domain, criteria = ElemHide.ALL_MATCHING)
   {
-    let selectors = [];
-
-    let specificOnly = (criteria >= ElemHide.SPECIFIC_ONLY);
-    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 == "")

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

Why don't we instead keep track of if filtersByDomain.has(currentDomain) (for
non "") is ever true here. If it wasn't we could cache the result of the
selectors which applied for "", or reuse the cached value. It seems to me that
would be a simpler way to use your insight about known/unknown domains without
adding as much complexity.

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

filtersByDomain.has(domain) will be true for ~11,000 domains. The optimization
in question still applies to ~9,500 out of those ~11,000 domains, but for that
we need to know specifically if there are any domain-specific exceptions (for
the domain in question) for any generic filters.

What you're suggesting works for unknown domains, not for known domains.

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

Alright, how about this, perhaps a dumb idea but hear me out...

- We no longer store null for exception filters in filtersByDomain.
- We keep a lookup of exception domains, whenever we add an exception we add the
(non-generic) domains to that.
- We keep a cache of the generic selectors that generally match for domains.

Then
- If the domain is found in the exceptions lookup we just do things the slow
way.
- Otherwise if the domain is found in filtersByDomain we do things the slow way
for the domain, but concatinate the generic selectors cache to that.
- Otherwise we just return the generic selectors cache.

Basically I think your insight about generally being able to return the
generically applied selectors is good, but I think your changes so far are quite
sweeping and add a lot of complexity. I'd like to see if we could get most of
the performance benefit from your insight without such a large change that adds
so much complexity.

[Manish Jethani, 2018/05/18 17:18:26]

If I understanding the suggestion correctly, you're saying that instead of
putting the domains with only exceptions in the filtersByDomain map but with the
value set to null, we put them in a separate set. This would work, it would just
mean two lookups instead of one (which is probably OK).

But ...
In order to make sure that we're not talking past each other, let's use the
terminology used in the patch.

Selectors fall into three categories:

 (1) unconditional selectors: apply on all domains (e.g. "##.ad" with no
domain-specific exceptions)

 (2) conditional generic selectors: generally apply on all domains, except for
domains with domain-specific exceptions (or those excluded in the filter itself)
for some generic selectors (e.g. "~no-foo.example.com###foo" does not apply on
no-foo.example.com, and if there's an exception like "bar.com#@##foo" then it
does not apply on bar.com either, but will still apply on all other domains)

 (3) domain-specific selectors: apply on specific domains (e.g.
"bar.example.com##div[data-bar]" applies only on bar.example.com)

If you're suggesting that we merge the caches of unconditional selectors and
conditional generic selectors into a single cache, that would be OK for most
domains, but it won't be good for the ~9,500 domains in EasyList+AA that have no
domain-specific exceptions for generic selectors; for those cases then, we'd
have to generate the list of unconditional selectors (~18,000 selectors in
EasyList+AA) (while we're currently caching this list) as well as the list of
conditional generic selectors. In the current patch, for such domains, we only
generate the list of conditional generic selectors.

So if we really want to do this in the best way then we need two caches.
This is what the patch did initially (see Patch Set 1) before I realized that
even most known domains could benefit from this optimization.

Also, as you pointed out in the initial comments, if we were going to extract
all the subdomains of a domain to check if any of the subdomains was in the set
of known domains (for foo.example.com we need to look for foo.example.com,
example.com, and com in the filtersByDomain map), why not get the filters for
those subdomains as well, since we need the filters for specific selector
matching anyway? This is why there's a getSpecificFiltersForDomain function now.
If there are no specific filters for a domain or any of its subdomains, clearly
then we can just return the cached list of generic selectors.
This would not work for ~1,500 domains out of ~11,000 domains in EasyList+AA, it
would yield incorrect results, because these domains have domain-specific
exceptions for some generic selectors.
So I think the problem is complex and the solution must necessarily reflect some
of that complexity if we want to optimize maximally for every case.

In general I'n not concerned about complexity as long as it yields correct
results and does it efficiently, but of course the more complex the logic
becomes the harder it becomes to maintain, so there's a good case for keeping
things simple. We have a 100+ million user base though, if I understand
correctly, and given that this code runs on every single HTML document
(including on mobile), I'm still very much in favor of optimizing this as much
as possible. If it becomes too complex, we can address that with abstractions
(i.e. separate things into into functions that do certain well-defined and
documented things) and add unit tests for those abstractions.

I'm OK with splitting this patch up into two though, so that one iteration only
optimizes for unknown domains while the second one takes the optimization to
most known domains (again, this is ~9500 domains out of ~11,000 domains in
EasyList+AA) and their subdomains. I still think it works best as a single patch
though, as it allows us to look at the bigger picture and take everything into
consideration at once. There are pros and cons.

What do you think?

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