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>>}
  */
 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
  * @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,
-                            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)
     {
       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

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

This is really {ElemHideBase}

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

Well spotted, Done.

    */
   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 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))
-        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);
     }
 
+    knownFilters.add(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

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

This is really {ElemHideBase}

    */
   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");
   },
 
   /**
    * 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)

[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);
         }
       }
 
       if (currentDomain == "")
         break;
 
       let nextDot = currentDomain.indexOf(".");
       currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
     }
 
     return selectors;
   }
 };