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..240cbddc4589aa7643ffd5685bd3b7a923d4a07e 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
- * @type {Set.<string>}
+ * Set containing known element hiding and exception filters
+ * @type {Set.<ElemHideBase>}
  */
-let knownExceptions = new Set();
+let knownFilters = new Set();
 
 /**
  * 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,21 +89,21 @@ 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);

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

I think we should change this to:

  if (domain || isIncluded)
    filters.set(filter, isIncluded);

I don't see why we would add an entry if the key is an empty string and the
value is false. It is not necessary, it doesn't do anything.

[kzar, 2018/05/01 16:13:59]

Good point, you're right and I checked and this applies to quite a lot of
filters in practice. Done, except I've made it explicit + avoided a pointless
filtersByDomain lookup.

     }
   },
 
   /**
    * 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)
@@ -127,88 +114,66 @@ 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");
   },
 
   /**
    * 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
     {
-      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/30 17:55:21]

So your comment about included vs excluded filters makes me wonder why we should
add included filters to the seenFilters set. Isn't it really just about keeping
track of exceptions on a subdomain? e.g. ~no.example.com,example.com##foo.
Should we really care if there's a filter like cool.example.com,example.com##foo
and it ends up causing the function to slow down and have the selector included
more than once?

I think maybe it's a good idea to change it to this:

  for (let [filter, isIncluded] of filters)
  {
    if (!isIncluded)
    {
      seenFilters.add(filter);
    }
    else if (!seenFilters.has(filter) &&
             !this.getException(filter, domain))
    {
      selectors.push(filter.selector);
    }
  }

Can you think of a case where this would break?

[kzar, 2018/05/01 16:13:59]

This is pretty much the same point you made on your review[1]. It's interesting,
but I'm not sure either way about it yet. Regardless I don't see the point of
making this change here, I'd rather save that discussion for your review.

[1] -
https://codereview.adblockplus.org/29764555/diff/29764556/lib/elemHide.js#new...

[Manish Jethani, 2018/05/02 12:28:11]

Fair enough.

In that case, do you think it makes sense to check if currentDomain is non-empty
before adding the filter to the seenFilters set?

  if (currentDomain != "")
    seenFilters.add(filter);

Adding to a set also has some cost, we're not going to look up those entries
since we'll be exiting the loop. Since there are so many generic filters
typically, it should help if we skipped that operation for generic filters. It
might also make the lookup faster. Think about it, for a random domain there are
no domain-specific filters and no exceptions, it's just a bunch of generic
filters. A lookup in an empty set should be instantaneous.

[Manish Jethani, 2018/05/02 12:57:34]

I just checked here and with just EasyList enabled the set is populated with
~1,100 entries that are then never looked up. By adding that check we reduce the
size of the set to 0.

I also checked if it helps to check the size before doing a lookup:

  (function ()
  {
    let set = new Set();

    let count = 0;
    let start = Date.now();

    for (let i = 0; i < 10000000; i++)
    {
      if (set.size > 0 && set.has("foo"))
        count++;

      //if (Math.random() < .01)
      //  set.add("foo");
    }

    console.log("time:", Date.now() - start);
    console.log("count:", count);
  })();

The performance improves drastically if we check the value of the size property
before doing a lookup, if the set is empty. If the set is not empty, the
performance doesn't seem to degrade if we check the size property (uncomment the
two lines so the set gets populated).

So I think our checks should be:

  if (seenFilters.size > 0 && seenFilters.has(filter))
    continue;

  if (currentDomain != "")
    seenFilters.add(filter);

[kzar, 2018/05/02 16:45:38]

You make some good points and I think on reflection you're probably right about
there not being much use in ignoring filters that were previously included.
Done.

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