Issue 6652 - Implement fast selector lookups for unknown domains

lib/elemHide.js

Index: lib/elemHide.js
===================================================================
--- a/lib/elemHide.js
+++ b/lib/elemHide.js
@@ -22,17 +22,17 @@
  */
 
 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>>}

[Manish Jethani, 2018/05/07 16:03:02]

The value here can now be null.

  */
 let filtersByDomain = new Map();
 
 /**
  * Lookup table, filter by selector. (Only used for selectors that are
  * unconditionally matched for all domains.)
  * @type {Map.<string,Filter>}
  */
@@ -57,69 +57,141 @@
 let knownFilters = new Set();
 
 /**
  * Lookup table, lists of element hiding exceptions by selector
  * @type {Map.<string,Filter>}
  */
 let exceptions = new Map();
 
+/*
+ * Set containing selectors with generic exceptions
+ * @type {Set.<string>}
+ */
+let genericExceptionSelectors = new Set();
+
+/*
+ * Checks if a domain is known
+ * @param {string} domain
+ * @returns {boolean}
+ */
+function isDomainKnown(domain)
+{
+  while (domain)
+  {
+    // A domain is "known" if we have seen any filters that would apply to it.
+    // For example, given the filters "##foo" and "example.com#@#foo",
+    // example.com is a known domain, as is mail.example.com and any other
+    // subdomains of example.com.
+    if (filtersByDomain.has(domain))
+      return true;
+
+    let nextDot = domain.indexOf(".");
+    domain = nextDot == -1 ? null : domain.substring(nextDot + 1);
+  }
+
+  return false;
+}
+
+/*
+ * Returns a list of selectors that apply on any unknown domain

[Manish Jethani, 2018/05/07 16:03:02]

There are generic selectors that are "conditional" (don't apply on all domains)
that would still apply on any unknown domain. For example,
"~foo.example.com##foo" would apply on all but foo.example.com, but if the
domain we're looking up for is example.com ("unknown" domain) then it's as good
as unconditional.

+ * @returns {string[]}
+ */
+function getConditionalGenericSelectors()

[Manish Jethani, 2018/05/07 16:10:33]

To give you some numbers, there are 18,300 unconditional selectors, 1,095
conditional generic selectors, and 16 generic exceptions in  in EasyList+AA.

So when you call ElemHide.getSelectorsForDomain on x4aabd7c0ddcd (unknown
domain), first the list is populated with 18,300 selectors right away, then
1,095 selectors are added to it, after filtering out 16 generic exceptions from
the actual 1,111 selectors.

+{
+  let selectors = [];
+
+  let filters = filtersByDomain.get("");
+  if (!filters)
+    return selectors;
+
+  for (let {selector} of filters.keys())
+  {
+    if (!genericExceptionSelectors.has(selector))

[Manish Jethani, 2018/05/07 16:03:02]

Here we have to check for generic exceptions like "#@#foo", which would disable
"~foo.example.com##foo"  on all domains (known or unknown).

There are 16 such generic exceptions in EasyList+AA.

+      selectors.push(selector);
+  }
+
+  return selectors;
+}
+
 /**
  * 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,
+                            genericExceptionSelectors])
     {
       collection.clear();
     }
     unconditionalSelectors = null;
     FilterNotifier.emit("elemhideupdate");
   },
 
   _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 == "")
-        continue;
+      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 the optimized path (which
+        // would give incorrect results).
+        if (domain != "" && !filtersByDomain.has(domain))

[Manish Jethani, 2018/05/07 16:03:02]

We could have had a separate knownExceptionDomains set. I'm not sure it's worth
it though, it's just easier to add a null entry here in filtersByDomain. Less
maintenance.

+          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);
+        let filters = filtersByDomain.get(domain);
+        if (!filters)
+          filtersByDomain.set(domain, filters = new Map());
+        filters.set(filter, isIncluded);
+      }
     }
   },
 
   /**
    * Add a new element hiding filter
    * @param {ElemHideBase} filter
    */
   add(filter)
   {
     if (knownFilters.has(filter))
       return;
 
     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)

[Manish Jethani, 2018/05/07 16:03:02]

For exceptions too we should remember the domains, otherwise an exception like
"foo.example.com#@#foo" will not be taken into account and the generic filter
"##foo" will be applied to "foo.example.com" (since it would be considered to be
an unknown domain). In this example we have to make sure that "foo.example.com"
is a known domain.

I've also updated the tests to check for this.

+        this._addToFiltersByDomain(filter);
+
+      if (filter.isGeneric())
+        genericExceptionSelectors.add(filter.selector);
+
       // 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)
       {
         this._addToFiltersByDomain(unconditionalFilterForSelector);
         filterBySelector.delete(selector);
@@ -153,16 +225,19 @@
 
     // Whitelisting filters
     if (filter instanceof ElemHideException)
     {
       let list = exceptions.get(filter.selector);
       let index = list.indexOf(filter);
       if (index >= 0)
         list.splice(index, 1);
+

[Manish Jethani, 2018/05/07 16:03:02]

Note that we don't bother "unknowing" a domain once we know it. It's OK, this is
an optimization anyway. It will still work for most domains out there.

+      if (filter.isGeneric())
+        genericExceptionSelectors.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
@@ -247,45 +322,53 @@
     let selectors = [];
 
     if (typeof criteria == "undefined")
       criteria = ElemHide.ALL_MATCHING;
     if (criteria < ElemHide.NO_UNCONDITIONAL)
       selectors = this.getUnconditionalSelectors();
 
     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 (isDomainKnown(currentDomain))

[Manish Jethani, 2018/05/07 16:03:02]

The call to isDomainKnown is the only additional cost now for known domains;
otherwise, for a known domain, the code is the same.

Based on my tests this call is not too expensive. We can also optimize it
further, for example by adding the looked up domain once we've determined it to
be known (e.g. when we look up "foo.example.com" and only "example.com" is in
the filtersByDomain map, we can add "foo.example.com" so it's looked up faster
next time).

     {
-      if (specificOnly && currentDomain == "")
-        break;
+      let excluded = new Set();
 
-      let filters = filtersByDomain.get(currentDomain);
-      if (filters)
+      // This code is a performance hot-spot, which is why we've made certain
+      // micro-optimisations. Please be careful before making changes.
+      while (true)
       {
-        for (let [filter, isIncluded] of filters)
+        if (specificOnly && currentDomain == "")
+          break;
+
+        let filters = filtersByDomain.get(currentDomain);
+        if (filters)
         {
-          if (!isIncluded)
+          for (let [filter, isIncluded] of filters)
           {
-            excluded.add(filter);
-          }
-          else if ((excluded.size == 0 || !excluded.has(filter)) &&
-                   !this.getException(filter, domain))
-          {
-            selectors.push(filter.selector);
+            if (!isIncluded)
+            {
+              excluded.add(filter);
+            }
+            else if ((excluded.size == 0 || !excluded.has(filter)) &&
+                     !this.getException(filter, domain))
+            {
+              selectors.push(filter.selector);
+            }
           }
         }
-      }
+
+        if (currentDomain == "")
+          break;
 
-      if (currentDomain == "")
-        break;
-
-      let nextDot = currentDomain.indexOf(".");
-      currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
+        let nextDot = currentDomain.indexOf(".");
+        currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
+      }
+    }
+    else if (!specificOnly)
+    {
+      selectors = selectors.concat(getConditionalGenericSelectors());

[Manish Jethani, 2018/05/07 16:03:02]

We might want to cache the value returned by getConditionalGenericSelectors,
since it's the same each time (unless filters are added or removed), but I
decided to avoid the additional bookkeeping for now. We can investigate this
separately. I also have other ideas for efficiently caching results.

     }
 
     return selectors;
   }
 };