Issue 6562 - Remove filter keys from the element hiding code

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

[kzar, 2018/04/20 18:52:38]

I am unsure about this one. Previously we needed the layer of indirection since
we needed a filter key to get to the filter anyway. But now we don't any more,
so I wonder if we could avoid the nested maps, while still supporting element
hiding filters which specifically don't apply to a domain.

One idea I had was to instead have two lookups, filtersByDomain and
filtersByDomainExcluded or something like that. What do you guys think? Any
ideas?

[Manish Jethani, 2018/04/21 11:11:57]

Unless I'm missing something, filtersByDomain is only needed in
_addToFiltersByDomain, and that function is only interested in the "included"
filters. Then perhaps we could skip the excluded ones and make this a
Map.<string,Set.<Filter>> instead?

[kzar, 2018/04/21 12:01:00]

On 2018/04/21 11:11:57, Manish Jethani wrote: 
It's also needed by getSelectorsForDomain, which is actually the whole reason
why we maintain it.
I don't think we can skip the exlucded ones, but we could potentially have two
lookups like you suggest, one for included and one for excluded.

[Manish Jethani, 2018/04/22 11:35:42]

Sorry, I meant getSelectorForDomain there. getSelectorsForDomain is only
interested in the "included" filters, 
so it could just be a Set of those filters?

[kzar, 2018/04/26 12:04:18]

OK, I read back through the old discussions to refresh my memory. Take the
example filter ~foo.example.com,example.com##foo , if we call
getSelectorsForDomain for foo.example.com we'll first find the excluded filter
for foo.example.com, then the included filter for example.com. The included
filter is (rightly) ignored since we already saw it without using it earlier.

If we didn't keep track of the excluded filter for foo.example.com we'd only
find the included filter for example.com and so that filter would have (wrongly)
been used.

I had a think about this for a while and can't see much of a better way to do
it.

  */
 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();
 
 /**
  * This array caches the keys of filterBySelector table (selectors
  * which unconditionally apply on all domains). It will be null if the
  * cache needs to be rebuilt.
  */
 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 exceptions
- * @type {Set.<string>}
- */
-let knownExceptions = new Set();
+ * 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>}
  */
 let exceptions = new Map();
 
 /**
  * Container for element hiding filters
  * @class
  */
 let ElemHide = exports.ElemHide = {
   /**
    * Removes all known filters
    */
   clear()
   {
     for (let collection of [filtersByDomain, filterBySelector,
-                            knownExceptions, exceptions])
+                            knownFilters, exceptions])
     {
       collection.clear();
     }
     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 = new Map());
       filters.set(filter, isIncluded);
     }
   },
 
   /**
    * Add a new element hiding filter
-   * @param {ElemHideFilter} filter
+   * @param {ElemHideBase} filter
    */
   add(filter)
   {
+    if (knownFilters.has(filter))
+      return;
+
     if (filter instanceof ElemHideException)
     {
-      if (knownExceptions.has(filter.text))
-        return;
-
       let {selector} = filter;
       let list = exceptions.get(selector);
       if (list)
         list.push(filter);
       else
         exceptions.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)
       {
         this._addToFiltersByDomain(unconditionalFilterForSelector);
         filterBySelector.delete(selector);
         unconditionalSelectors = null;
       }
-
-      knownExceptions.add(filter.text);
     }
     else if (!(filter.domains || exceptions.has(filter.selector)))
     {
       // The new filter's selector is unconditionally applied to all domains
       filterBySelector.set(filter.selector, filter);
       unconditionalSelectors = null;
     }
     else
     {
       // 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)
     {
-      if (!knownExceptions.has(filter.text))
-        return;
-
       let list = exceptions.get(filter.selector);
       let index = list.indexOf(filter);
       if (index >= 0)
         list.splice(index, 1);
-      knownExceptions.delete(filter.text);
-    }
+    }
+    // Unconditially applied element hiding filters
+    else if (filterBySelector.get(filter.selector) == filter)
+    {
+      filterBySelector.delete(filter.selector);
+      unconditionalSelectors = null;
+    }
+    // Conditionally applied element hiding filters
     else
     {
-      if (filterBySelector.get(filter.selector) === filter)
-      {
-        filterBySelector.delete(filter.selector);
-        unconditionalSelectors = null;
-        return;

[kzar, 2018/04/26 12:04:18]

Note: I think this was a bug, we wouldn't emit the "elemhideupdate" event when
removing unconditionally applied hiding filters.

-      }
-
-      // We haven't found this filter in unconditional filters, look in
-      // filtersByDomain.
       let domains = filter.domains || defaultDomains;
       for (let domain of domains.keys())
       {
         let filters = filtersByDomain.get(domain);
         if (filters)
           filters.delete(filter);
       }
     }
 
+    knownFilters.delete(filter);
     FilterNotifier.emit("elemhideupdate");
   },
 
   /**
    * Checks whether an exception rule is registered for a filter on a particular
    * domain.
    * @param {Filter} filter
    * @param {string} docDomain
    * @return {ElemHideException}
    */
@@ skipping 54 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 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 == "")
         break;
 
       let filters = filtersByDomain.get(currentDomain);
       if (filters)
       {
         for (let [filter, isIncluded] of filters)
         {
-          if (seenFilters.has(filter))
-            continue;
-          seenFilters.add(filter);
-
-          if (isIncluded && !this.getException(filter, domain))
+          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);
     }
 
     return selectors;
   }
 };