Issue 7452 - Do not cache element hiding filter objects by default

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 {Filter} = require("./filterClasses");
 const {ElemHideExceptions} = require("./elemHideExceptions");
 const {filterNotifier} = require("./filterNotifier");
 
 /**
  * The maximum number of selectors in a CSS rule. This is used by
  * <code>{@link createStyleSheet}</code> to split up a long list of selectors
  * into multiple rules.
  * @const {number}
  * @default
  */
 const selectorGroupSize = 1024;
 
 /**
- * Lookup table, active flag, by filter by domain.
- * (Only contains filters that aren't unconditionally matched for all domains.)
- * @type {Map.<string,Map.<Filter,boolean>>}
+ * Lookup table, active flag, by filter text by domain.
+ * (Only contains text for filters that aren't unconditionally matched for all
+ * domains.)
+ * @type {Map.<string,Map.<string,boolean>>}
  */
-let filtersByDomain = new Map();
+let filterTextByDomain = new Map();
 
 /**
- * Lookup table, filter by selector. (Only used for selectors that are
+ * Lookup table, filter text by selector. (Only used for selectors that are
  * unconditionally matched for all domains.)
- * @type {Map.<string,Filter>}
+ * @type {Map.<string,string>}
  */
-let filterBySelector = new Map();
+let filterTextBySelector = new Map();
 
 /**
- * This array caches the keys of filterBySelector table (selectors
+ * This array caches the keys of filterTextBySelector table (selectors
  * which unconditionally apply on all domains). It will be null if the
  * cache needs to be rebuilt.
  * @type {?string[]}
  */
 let unconditionalSelectors = null;
 
 /**
  * The default style sheet that applies on all domains. This is based on the
  * value of <code>{@link unconditionalSelectors}</code>.
  * @type {?string}
@@ skipping 10 matching lines @@
 let commonStyleSheet = null;
 
 /**
  * Map to be used instead when a filter has a blank domains property.
  * @type {Map.<string,boolean>}
  * @const
  */
 let defaultDomains = new Map([["", true]]);
 
 /**
- * Set containing known element hiding filters
- * @type {Set.<ElemHideFilter>}
+ * Set containing the text of known element hiding filters
+ * @type {Set.<string>}
  */
-let knownFilters = new Set();
+let knownFilterText = new Set();
 
 /**
  * All domains known to occur in exceptions
  * @type {Set.<string>}
  */
 let knownExceptionDomains = new Set();
 
 /**
  * Returns the suffix of the given domain that is known. If no suffix is known,
  * an empty string is returned.
  * @param {?string} domain
  * @returns {string}
  */
 function getKnownSuffix(domain)
 {
-  while (domain && !filtersByDomain.has(domain) &&
+  while (domain && !filterTextByDomain.has(domain) &&
          !knownExceptionDomains.has(domain))
   {
     let index = domain.indexOf(".");
     domain = index == -1 ? "" : domain.substring(index + 1);
   }
 
   return domain;
 }
 
 /**
- * Adds a filter to the lookup table of filters by domain.
+ * Adds a filter to the lookup table of filter text by domain.
  * @param {Filter} filter
  * @param {?Map.<string,boolean>} [domains]
  */
 function addToFiltersByDomain(filter, domains = filter.domains)
 {
   for (let [domain, isIncluded] of domains || defaultDomains)
   {
     // 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(filter, isIncluded);
+    let map = filterTextByDomain.get(domain);
+    if (!map)
+      filterTextByDomain.set(domain, map = new Map());
+    map.set(filter.text, isIncluded ? filter.selector : null);
   }
 }
 
 /**
  * Returns a list of selectors that apply on each website unconditionally.
  * @returns {string[]}
  */
 function getUnconditionalSelectors()
 {
   if (!unconditionalSelectors)
-    unconditionalSelectors = [...filterBySelector.keys()];
+    unconditionalSelectors = [...filterTextBySelector.keys()];
 
   return unconditionalSelectors;
 }
 
 /**
  * Returns the list of selectors that apply on a given domain from the subset
  * of filters that do not apply unconditionally on all domains.
  *
  * @param {string} domain The domain.
  * @param {boolean} specificOnly Whether selectors from generic filters should
  *   be included.
  *
  * @returns {Array.<string>} The list of selectors.
  */
 function getConditionalSelectors(domain, specificOnly)
 {
   let selectors = [];
 
   let excluded = new Set();
   let currentDomain = domain;
 
   // 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 == "")
       break;
 
-    let filters = filtersByDomain.get(currentDomain);
-    if (filters)
+    let map = filterTextByDomain.get(currentDomain);
+    if (map)
     {
-      for (let [filter, isIncluded] of filters)
+      for (let [text, selector] of map)
       {
-        if (!isIncluded)
+        if (selector == null)
         {
-          excluded.add(filter);
+          excluded.add(text);
         }
-        else
+        else if ((excluded.size == 0 || !excluded.has(text)) &&
+                 !ElemHideExceptions.getException(selector, domain))
         {
-          let {selector} = filter;
-          if ((excluded.size == 0 || !excluded.has(filter)) &&
-              !ElemHideExceptions.getException(selector, domain))
-          {
-            selectors.push(selector);
-          }
+          selectors.push(selector);
         }
       }
     }
 
     if (currentDomain == "")
       break;
 
     let nextDot = currentDomain.indexOf(".");
     currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
   }
@@ skipping 39 matching lines @@
       // Note: Once an exception domain is known it never becomes unknown, even
       // when all the exceptions containing that domain are removed. This is a
       // best-case optimization.
       if (domain != "")
         knownExceptionDomains.add(domain);
     }
   }
 
   // If this is the first exception for a previously unconditionally applied
   // element hiding selector we need to take care to update the lookups.
-  let unconditionalFilterForSelector = filterBySelector.get(selector);
-  if (unconditionalFilterForSelector)
+  let unconditionalFilterTextForSelector = filterTextBySelector.get(selector);
+  if (unconditionalFilterTextForSelector)
   {
-    addToFiltersByDomain(unconditionalFilterForSelector);
-    filterBySelector.delete(selector);
+    addToFiltersByDomain(Filter.fromText(unconditionalFilterTextForSelector));

[hub, 2018/11/28 23:21:31]

So here, we call Filter.fromText() while before we didn't.

[Manish Jethani, 2019/04/07 18:05:09]

Yes, unfortunately this is the price.

I looked at how many times this has to be done: EasyList: 637; EasyList+AA:
1,230. For comparison, there are 32,156 element hiding filters in EasyList+AA. I
think it's worth it. The filter text itself is `##<selector>` so it should be
relatively quick to parse (and if it isn't then we should optimize for that
case).

[Manish Jethani, 2019/04/07 18:55:11]

OK, so I looked into this [1], and parsing of generic element hiding filters is
already as fast as it can be. Maybe you want to take another look sometime.

[1]: https://issues.adblockplus.org/ticket/7445

+    filterTextBySelector.delete(selector);
     unconditionalSelectors = null;
     defaultStyleSheet = null;
   }
 });
 
 /**
  * Container for element hiding filters
  * @class
  */
 exports.ElemHide = {
   /**
    * Removes all known filters
    */
   clear()
   {
     commonStyleSheet = null;
 
-    for (let collection of [filtersByDomain, filterBySelector, knownFilters,
-                            knownExceptionDomains])
+    for (let collection of [filterTextByDomain, filterTextBySelector,
+                            knownFilterText, knownExceptionDomains])
     {
       collection.clear();
     }
 
     unconditionalSelectors = null;
     defaultStyleSheet = null;
 
     filterNotifier.emit("elemhideupdate");
   },
 
   /**
    * Add a new element hiding filter
    * @param {ElemHideFilter} filter
    */
   add(filter)
   {
-    if (knownFilters.has(filter))
+    let {text} = filter;
+
+    if (knownFilterText.has(text))
       return;
 
     commonStyleSheet = null;
 
     let {domains, selector} = filter;
 
     if (!(domains || ElemHideExceptions.hasExceptions(selector)))
     {
       // The new filter's selector is unconditionally applied to all domains
-      filterBySelector.set(selector, filter);
+      filterTextBySelector.set(selector, text);
       unconditionalSelectors = null;
       defaultStyleSheet = null;
     }
     else
     {
       // The new filter's selector only applies to some domains
       addToFiltersByDomain(filter, domains);
     }
 
-    knownFilters.add(filter);
+    knownFilterText.add(text);
     filterNotifier.emit("elemhideupdate");
   },
 
   /**
    * Removes an element hiding filter
    * @param {ElemHideFilter} filter
    */
   remove(filter)
   {
-    if (!knownFilters.has(filter))
+    let {text} = filter;
+
+    if (!knownFilterText.has(text))
       return;
 
     commonStyleSheet = null;
 
     let {selector} = filter;
 
     // Unconditially applied element hiding filters
-    if (filterBySelector.get(selector) == filter)
+    if (filterTextBySelector.get(selector) == text)
     {
-      filterBySelector.delete(selector);
+      filterTextBySelector.delete(selector);
       unconditionalSelectors = null;
       defaultStyleSheet = null;
     }
     // Conditionally applied element hiding filters
     else
     {
       let domains = filter.domains || defaultDomains;
       for (let domain of domains.keys())
       {
-        let filters = filtersByDomain.get(domain);
-        if (filters)
+        let map = filterTextByDomain.get(domain);
+        if (map)
         {
-          filters.delete(filter);
+          map.delete(text);
 
-          if (filters.size == 0)
-            filtersByDomain.delete(domain);
+          if (map.size == 0)
+            filterTextByDomain.delete(domain);
         }
       }
     }
 
-    knownFilters.delete(filter);
+    knownFilterText.delete(text);
     filterNotifier.emit("elemhideupdate");
   },
 
   /**
    * @typedef {object} ElemHideStyleSheet
    * @property {string} code CSS code.
    * @property {Array.<string>} selectors List of selectors.
    */
 
   /**
@@ skipping 124 matching lines @@
 {
   let styleSheet = "";
 
   for (let selectorGroup of splitSelectors(selectors))
     styleSheet += createRule(selectorGroup);
 
   return styleSheet;
 }
 
 exports.createStyleSheet = createStyleSheet;