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, filters by their associated key
- * @type {Filter[]}
- */
-let filterByKey = [];
-
-/**
- * Lookup table, keys of the filters by filter
- * @type {Map.<Filter,number>}
- */
-let keyByFilter = new Map();
-
-/**
- * Nested lookup table, filter (or false if inactive) by filter key by domain.
+ * Lookup table, active flag, by filter by domain.
  * (Only contains filters that aren't unconditionally matched for all domains.)
- * @type {Map.<string,Map.<number,(Filter|boolean)>>}
+ * @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 key by selector. (Only used for selectors that are
+ * Lookup table, filter by selector. (Only used for selectors that are
  * unconditionally matched for all domains.)
- * @type {Map.<string,number>}
+ * @type {Map.<string,Filter>}
  */
-let filterKeyBySelector = new Map();
+let filterBySelector = new Map();
 
 /**
- * This array caches the keys of filterKeyBySelector table (selectors which
- * unconditionally apply on all domains). It will be null if the cache needs to
- * be rebuilt.
+ * 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;
 
 /**
- * Object to be used instead when a filter has a blank domains property.
+ * 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();
 
 /**
  * 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 [keyByFilter, filtersByDomain, filterKeyBySelector,
+    for (let collection of [filtersByDomain, filterBySelector,
                             knownExceptions, exceptions])
     {
       collection.clear();
     }
-    filterByKey = [];
     unconditionalSelectors = null;
     FilterNotifier.emit("elemhideupdate");
   },
 
-  _addToFiltersByDomain(key, filter)
+  _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(key, isIncluded ? filter : false);
+      filters.set(filter, isIncluded);
     }
   },
 
   /**
    * Add a new element hiding filter
    * @param {ElemHideFilter} filter
    */
   add(filter)
   {
     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 filterKey = filterKeyBySelector.get(selector);
-      if (typeof filterKey != "undefined")
+      let unconditionalFilterForSelector = filterBySelector.get(selector);
+      if (unconditionalFilterForSelector)
       {
-        this._addToFiltersByDomain(filterKey, filterByKey[filterKey]);
-        filterKeyBySelector.delete(selector);
+        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
     {
-      if (keyByFilter.has(filter))

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

If we already have the filter, we don't add it again. The same is done for
exceptions above (knownExceptions). So I think we should keep this, perhaps
combine the two so that now we simply have a "knownFilters" and we skip this
entire function is knownFilters contains the filter.

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

Yea, I think you're right. I've gone back through some of the early commits and
it seems like the intention was always to avoid adding duplicate hiding or
exception filters here. Done.

-        return;
-
-      let key = filterByKey.push(filter) - 1;
-      keyByFilter.set(filter, key);
-
-      if (!(filter.domains || exceptions.has(filter.selector)))
-      {
-        // The new filter's selector is unconditionally applied to all domains
-        filterKeyBySelector.set(filter.selector, key);
-        unconditionalSelectors = null;
-      }
-      else
-      {
-        // The new filter's selector only applies to some domains
-        this._addToFiltersByDomain(key, filter);
-      }
+      // The new filter's selector only applies to some domains
+      this._addToFiltersByDomain(filter);
     }
 
     FilterNotifier.emit("elemhideupdate");
   },
 
-  _removeFilterKey(key, filter)
-  {
-    if (filterKeyBySelector.get(filter.selector) == key)
-    {
-      filterKeyBySelector.delete(filter.selector);
-      unconditionalSelectors = null;
-      return;
-    }
-
-    // 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(key);
-    }
-  },
-
   /**
    * Removes an element hiding filter
    * @param {ElemHideFilter} filter
    */
   remove(filter)
   {
     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);
     }
     else
     {
-      let key = keyByFilter.get(filter);
-      if (typeof key == "undefined")
+      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.

+      }
 
-      delete filterByKey[key];
-      keyByFilter.delete(filter);
-      this._removeFilterKey(key, filter);
+      // 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);
+      }
     }
 
     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}
    */
   getException(filter, docDomain)
   {
     let list = exceptions.get(filter.selector);
     if (!list)
       return null;
 
     for (let i = list.length - 1; i >= 0; i--)
     {
       if (list[i].isActiveOnDomain(docDomain))
         return list[i];
     }
 
     return null;
   },
 
   /**
-   * Retrieves an element hiding filter by the corresponding protocol key
-   * @param {number} key
-   * @return {Filter}
-   */
-  getFilterByKey(key)
-  {
-    return (key in filterByKey ? filterByKey[key] : null);
-  },
-
-  /**
    * Returns a list of selectors that apply on each website unconditionally.
    * @returns {string[]}
    */
   getUnconditionalSelectors()
   {
     if (!unconditionalSelectors)
-      unconditionalSelectors = [...filterKeyBySelector.keys()];
+      unconditionalSelectors = [...filterBySelector.keys()];
     return unconditionalSelectors.slice();
   },
 
   /**
    * Constant used by getSelectorsForDomain to return all selectors applying to
    * a particular hostname.
    */
   ALL_MATCHING: 0,
 
   /**
@@ skipping 31 matching lines @@
     let seenFilters = new Set();
     let currentDomain = domain ? domain.toUpperCase() : "";
     while (true)
     {
       if (specificOnly && currentDomain == "")
         break;
 
       let filters = filtersByDomain.get(currentDomain);
       if (filters)
       {
-        for (let [filterKey, filter] of filters)
+        for (let [filter, isIncluded] of filters)
         {
-          if (seenFilters.has(filterKey))
+          if (seenFilters.has(filter))
             continue;
-          seenFilters.add(filterKey);
+          seenFilters.add(filter);
 
-          if (filter && !this.getException(filter, domain))
+          if (isIncluded && !this.getException(filter, domain))
             selectors.push(filter.selector);
         }
       }
 
       if (currentDomain == "")
         break;
 
       let nextDot = currentDomain.indexOf(".");
       currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
     }
 
     return selectors;
   }
 };