Noissue - Use two sets for excluded and included filters by domain

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 34 matching lines @@
  */
 let unconditionalSelectors = null;
 
 /**
  * Map to be used instead when a filter has a blank domains property.
  */
 let defaultDomains = new Map([["", true]]);
 
 /**
  * Set containing known element hiding and exception filters
- * @type {Set.<string>}
+ * @type {Set.<ElemHideBase>}
  */
 let knownFilters = new Set();
 
 /**
  * Lookup table, lists of element hiding exceptions by selector
  * @type {Map.<string,Filter>}
  */
 let exceptions = new Map();
 
 /**
@@ skipping 13 matching lines @@
     }
     unconditionalSelectors = null;
     FilterNotifier.emit("elemhideupdate");
   },
 
   _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;
+
       let filters = filtersByDomain.get(domain);
       if (!filters)
         filtersByDomain.set(domain, filters = []);
 
       let setIndex = +isIncluded;

[Manish Jethani, 2018/04/28 16:35:35]

Conveniently boolean converted to number gives us the index of the set we're
looking for.

       if (!filters[setIndex])

[Manish Jethani, 2018/04/28 16:35:35]

The number of entries is the same as before. If there are only inclusions or
only exclusions then there is only one Set object.

         filters[setIndex] = new Set();
 
       filters[setIndex].add(filter);
     }
   },
 
   /**
    * Add a new element hiding filter
-   * @param {ElemHideFilter} filter
+   * @param {ElemHideBase} filter
    */
   add(filter)
   {
     if (knownFilters.has(filter))
       return;
 
     if (filter instanceof ElemHideException)
     {
       let {selector} = filter;
       let list = exceptions.get(selector);
@@ skipping 24 matching lines @@
       // The new filter's selector only applies to some domains
       this._addToFiltersByDomain(filter);
     }
 
     knownFilters.add(filter);
     FilterNotifier.emit("elemhideupdate");
   },
 
   /**
    * Removes an element hiding filter
-   * @param {ElemHideFilter} filter
+   * @param {ElemHideBase} filter
    */
   remove(filter)
   {
     if (!knownFilters.has(filter))
       return;
 
     // Whitelisting filters
     if (filter instanceof ElemHideException)
     {
       let list = exceptions.get(filter.selector);
       let index = list.indexOf(filter);
       if (index >= 0)
         list.splice(index, 1);
     }
     // Unconditially applied element hiding filters
     else if (filterBySelector.get(filter.selector) === filter)
     {
       filterBySelector.delete(filter.selector);
       unconditionalSelectors = null;
     }
     // Conditionally applied element hiding filters
     else
     {
       let domains = filter.domains || defaultDomains;
       for (let domain of domains.keys())
       {
-        for (let set of filtersByDomain.get(domain) || [])
+        let filters = filtersByDomain.get(domain) || [];
+        for (let i = 0; i < filters.length; i++)
         {
-          if (set)
-            set.delete(filter);
+          if (!filters[i])
+            continue;
+
+          filters[i].delete(filter);
+
+          if (filters[i].size == 0)
+            delete filters[i];
         }
       }
     }
 
     knownFilters.delete(filter);
     FilterNotifier.emit("elemhideupdate");
   },
 
   /**
    * Checks whether an exception rule is registered for a filter on a particular
@@ skipping 59 matching lines @@
   getSelectorsForDomain(domain, criteria)
   {
     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 seenFilters = [];

[Manish Jethani, 2018/04/28 16:35:35]

This is now an array of sets. The maximum number of entries in this array will
be the number of domain parts. e.g. for cool.example.com there will be at most 3
entries. An entry is added only if there are exclusions for the corresponding
domain part.

+    let excludedFilters = [];
+
     let currentDomain = domain ? domain.toUpperCase() : "";
+    let currentDomainIsGeneric = currentDomain == "";
+
+    // 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 == "")
+      if (specificOnly && currentDomainIsGeneric)
         break;
 
       let [excluded, included] = filtersByDomain.get(currentDomain) || [];
+
       if (excluded)
-        seenFilters.push(excluded);
-
-      for (let filter of included || [])
+        excludedFilters.push(excluded);
+
+      if (included)
       {
-        for (let set of seenFilters)

[Manish Jethani, 2018/04/28 18:47:06]

By the way, in case it isn't clear, the reason this performs better is that
we're not constructing a new set like before, instead we're adding previously
constructed sets to an array. Lookup in this array of sets might be slower in
theory, but typically for a domain like "foo.example.com" there's only at most
one set in the array anyway, so there's only one lookup. For a domain that has
no exception subdomains (which is most domains actually), there will be no
lookups either.

+        for (let filter of included)
         {

[Manish Jethani, 2018/04/28 18:47:06]

Note that as a side effect of this change a filter like
"foo.example.com,example.com##bar" will appear twice (hence the selector "bar"
will be added twice to the result). This is unfortunate but I don't think it is
worth doing anything about, because in practice I'm not sure why a filter author
would write a filter like that. If there are two filters "foo.example.com##bar"
and "example.com##bar", which is more likely to happen in practice anyway (the
author did not check that there's already a filter that applies), we don't
filter out duplicates in such a case; then it doesn't makes that we should care
about duplicates at all. It does mean unfortunately that this.getException would
get called twice for the same filter, but I don't think this matters in
practice.

-          if (set.has(filter))
+          for (let i = 0; i < excludedFilters.length; i++)
           {
-            filter = null;
-            break;
+            if (excludedFilters[i].has(filter))
+            {
+              filter = null;
+              break;
+            }
           }
+
+          if (filter && !this.getException(filter, domain))
+            selectors.push(filter.selector);
         }
-
-        if (filter && !this.getException(filter, domain))
-          selectors.push(filter.selector);
       }
 
-      if (currentDomain == "")
+      if (currentDomainIsGeneric)
         break;
 
       let nextDot = currentDomain.indexOf(".");
-      currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
+      if (nextDot == -1)
+      {
+        currentDomain = "";
+        currentDomainIsGeneric = true;
+      }
+      else
+        currentDomain = currentDomain.substr(nextDot + 1);
     }
 
     return selectors;
   }
 };