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
  * 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,Array.<Set.<Filter>>>}
  */
 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 40 matching lines @@
     FilterNotifier.emit("elemhideupdate");
   },
 
   _addToFiltersByDomain(filter)
   {
     let domains = filter.domains || defaultDomains;
     for (let [domain, isIncluded] of domains)
     {
       let filters = filtersByDomain.get(domain);
       if (!filters)
-        filtersByDomain.set(domain, filters = new Map());
-      filters.set(filter, isIncluded);
+        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
    */
   add(filter)
   {
     if (knownFilters.has(filter))
@@ skipping 57 matching lines @@
     {
       filterBySelector.delete(filter.selector);
       unconditionalSelectors = null;
     }
     // Conditionally applied element hiding filters
     else
     {
       let domains = filter.domains || defaultDomains;
       for (let domain of domains.keys())
       {
-        let filters = filtersByDomain.get(domain);
-        if (filters)
-          filters.delete(filter);
+        for (let set of filtersByDomain.get(domain) || [])
+        {
+          if (set)
+            set.delete(filter);
+        }
       }
     }
 
     knownFilters.delete(filter);
     FilterNotifier.emit("elemhideupdate");
   },
 
   /**
    * Checks whether an exception rule is registered for a filter on a particular
    * domain.
@@ skipping 58 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 = new Set();
+    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 currentDomain = domain ? domain.toUpperCase() : "";
     while (true)
     {
       if (specificOnly && currentDomain == "")
         break;
 
-      let filters = filtersByDomain.get(currentDomain);
-      if (filters)
+      let [excluded, included] = filtersByDomain.get(currentDomain) || [];
+      if (excluded)
+        seenFilters.push(excluded);
+
+      for (let filter of included || [])
       {
-        for (let [filter, isIncluded] of filters)
+        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.

         {

[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 (seenFilters.has(filter))
-            continue;
-          seenFilters.add(filter);
+          if (set.has(filter))
+          {
+            filter = null;
+            break;
+          }
+        }
 
-          if (isIncluded && !this.getException(filter, domain))
-            selectors.push(filter.selector);
-        }
+        if (filter && !this.getException(filter, domain))
+          selectors.push(filter.selector);
       }
 
       if (currentDomain == "")
         break;
 
       let nextDot = currentDomain.indexOf(".");
       currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
     }
 
     return selectors;
   }
 };