Issue 6562 - Remove filter keys from the element hiding code

lib/elemHide.js

Index: lib/elemHide.js
diff --git a/lib/elemHide.js b/lib/elemHide.js
index 9aa1ae3948540af980eda636d9530464c6951aa6..c493cc2ca9144a3058524adc4a2d568eccea5e5e 100644
--- a/lib/elemHide.js
+++ b/lib/elemHide.js
@@ -25,48 +25,36 @@ 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>>}
  */
 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
+ * Set containing known element hiding and exception filters
  * @type {Set.<string>}

[Manish Jethani, 2018/04/27 12:39:36]

This is really {Set.<ElemHideBase>}

[kzar, 2018/04/30 10:11:46]

Done.

  */
-let knownExceptions = new Set();
+let knownFilters = new Set();

[Manish Jethani, 2018/04/27 12:39:36]

I wonder if we should make this a WeakSet since we never need to iterate over
it. We are holding on to the filter references elsewhere?

[kzar, 2018/04/30 10:11:46]

I considered that as well but we keep a reference to exceptions in the
exceptions lookup, the rest in filtersByDomain and filtersBySelector anyway. If
we remove the filter from those lookups but not from this one then we've got a
bug.

(We do iterate over this in the tests, not that that's a good reason to avoid
making this a WeakSet.)

 
 /**
  * Lookup table, lists of element hiding exceptions by selector
@@ -84,17 +72,16 @@ let ElemHide = exports.ElemHide = {
    */
   clear()
   {
-    for (let collection of [keyByFilter, filtersByDomain, filterKeyBySelector,
-                            knownExceptions, exceptions])
+    for (let collection of [filtersByDomain, filterBySelector,
+                            knownFilters, 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)
@@ -102,7 +89,7 @@ let ElemHide = exports.ElemHide = {
       let filters = filtersByDomain.get(domain);
       if (!filters)
         filtersByDomain.set(domain, filters = new Map());
-      filters.set(key, isIncluded ? filter : false);
+      filters.set(filter, isIncluded);
     }
   },
 
@@ -112,11 +99,11 @@ let ElemHide = exports.ElemHide = {
    */
   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)
@@ -127,58 +114,28 @@ let ElemHide = exports.ElemHide = {
       // 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
+    else if (!(filter.domains || exceptions.has(filter.selector)))
     {
-      if (keyByFilter.has(filter))
-        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);
-      }
-    }
-
-    FilterNotifier.emit("elemhideupdate");
-  },
-
-  _removeFilterKey(key, filter)
-  {
-    if (filterKeyBySelector.get(filter.selector) == key)
-    {
-      filterKeyBySelector.delete(filter.selector);
+      // The new filter's selector is unconditionally applied to all domains
+      filterBySelector.set(filter.selector, filter);
       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())
+    else
     {
-      let filters = filtersByDomain.get(domain);
-      if (filters)
-        filters.delete(key);
+      // The new filter's selector only applies to some domains
+      this._addToFiltersByDomain(filter);
     }
+
+    knownFilters.add(filter);
+    FilterNotifier.emit("elemhideupdate");
   },
 
   /**
@@ -187,28 +144,36 @@ let ElemHide = exports.ElemHide = {
    */
   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
     {
-      let key = keyByFilter.get(filter);
-      if (typeof key == "undefined")
-        return;
-
-      delete filterByKey[key];
-      keyByFilter.delete(filter);
-      this._removeFilterKey(key, filter);
+      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");
   },
 
@@ -234,16 +199,6 @@ let ElemHide = exports.ElemHide = {
     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[]}
@@ -251,7 +206,7 @@ let ElemHide = exports.ElemHide = {
   getUnconditionalSelectors()
   {
     if (!unconditionalSelectors)
-      unconditionalSelectors = [...filterKeyBySelector.keys()];
+      unconditionalSelectors = [...filterBySelector.keys()];
     return unconditionalSelectors.slice();
   },
 
@@ -303,13 +258,13 @@ let ElemHide = exports.ElemHide = {
       let filters = filtersByDomain.get(currentDomain);
       if (filters)
       {
-        for (let [filterKey, filter] of filters)
+        for (let [filter, isIncluded] of filters)

[Manish Jethani, 2018/04/27 12:39:36]

Just a thought, but I wonder if we could do this (I haven't thought this
through):

  let excludedFilterSets = [];
  while (true)
  {
    excludedFilterSets.push(excludedFiltersByDomain.get(currentDomain));

    for (let filter of includedFiltersByDomain.get(currentDomain))
    {
      for (let set of excludedFilterSets)
      {
        if (set.has(filter))
        {
          filter = null;
          break;
        }
      }

      if (filter && !this.getException(filter, domain))
        selectors.push(filter.selector);
    }

    ...
  }

So I think this is the idea you were toying with, I see it now. We could have
two sets, one for excluded and one for included. I'm not sure if this is better
though. It would mean fewer iterations but more set lookups. Ultimately it
depends on the kinds of filters we have.

[Manish Jethani, 2018/04/27 12:41:58]

Anyway, I'm all for not changing things here as part of this patch.

[kzar, 2018/04/27 17:01:50]

On 2018/04/27 12:39:36, Manish Jethani wrote: 
Exactly, that's what I was playing with. Except perhaps we would have to keep
track of the already seen included filters as well if we want to keep behaviour
the same... but not sure it matters.

I'm also not clear this is a change worth making, I could see aspects of both
which are nicer. Maintaining two sets would also have (even) more complexity for
the filter adding and removing code.
Yea, I don't want to do it for now I think. Well unless I can be convinced it's
clearly better! What do you think?

[Manish Jethani, 2018/04/28 16:22:17]

That's what excludedFilterSets in the above code snippet was.

Anyway, I did some tests, the performance seems to improve for EasyList. Here's
the patch I tested:

https://codereview.adblockplus.org/29764555/
So I think filter adding and removing happens less often than lookups for
filters by domain, which means the lookup code should perform better.
It seems to be better. Let's take this discussion to the other patch that I've
uploaded. This one can focus on the original issue.

[kzar, 2018/04/30 10:11:46]

Well no, excludedFilterSets contained the excluded filters so far. I was talking
about the included filters so far.
 
Thanks for looking into it some more. You mention the performance improving,
could you share how you tested and the numbers?
 
Interesting insight.

[Manish Jethani, 2018/04/30 17:55:21]

Let's do that as part of the other patch.

         {
-          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);
         }
       }