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
- * @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
  * @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)
     {
+      // 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(key, isIncluded ? filter : false);
+      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 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
+   * @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");
   },
 
   /**
    * 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 21 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 excludedFilters = new Set();
+
     let currentDomain = domain ? domain.toUpperCase() : "";
+    let currentDomainIsGeneric = currentDomain == "";

[Manish Jethani, 2018/05/02 18:11:40]

Comparison with an empty string really should not need to be cached, it's
probably superoptimized by the JS engine anyway. I would drop this. Also see
below.

[kzar, 2018/05/03 15:36:00]

OK, Done.

+
+    // 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 == "")
+      if (specificOnly && currentDomainIsGeneric)
         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 (excludedFilters.size > 0 && excludedFilters.has(filter))

[Manish Jethani, 2018/05/02 18:11:40]

We only need to do this check for included filters, so it should be inside the
if block.

[kzar, 2018/05/03 15:36:01]

Good point, Done.

             continue;
-          seenFilters.add(filterKey);
 
-          if (filter && !this.getException(filter, domain))
-            selectors.push(filter.selector);
+          if (isIncluded)
+          {
+            if (!this.getException(filter, domain))
+              selectors.push(filter.selector);
+          }
+          else if (!currentDomainIsGeneric)

[Manish Jethani, 2018/05/02 18:11:40]

currentDomain will always be non-empty if the filter is excluded, we made sure
of that while populating filtersByDomain (which is why I did not mention this
when I thought we would just not add the included filters to the set).

So I think it comes down to this:

    if (!isIncluded)
    {
      excludedFilters.add(filter);
    }
    else if ((excludedFilters.size == 0 || !excludedFilters.has(filter)) &&
             !this.getException(filter, domain))
    {
      selectors.push(filter.selector);
    }

Note there's no check for currentDomain now, I think we can drop all the related
changes there.

[kzar, 2018/05/03 15:36:00]

OK, Done.
Well there still are a couple of checks for currentDomain elsewhere.

+            excludedFilters.add(filter);
         }
       }
 
-      if (currentDomain == "")
+      if (currentDomainIsGeneric)
         break;
 
       let nextDot = currentDomain.indexOf(".");
-      currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
+      if (nextDot == -1)
+      {
+        currentDomain = "";
+        currentDomainIsGeneric = true;
+      }
+      else
+        currentDomain = currentDomain.substr(nextDot + 1);
     }
 
     return selectors;
   }
 };