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");
+const {normalizeHostname, domainSuffixes} = require("./url");
+const {Cache} = require("./caching");
 
 /**
  * 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 text by domain.
- * (Only contains text for filters that aren't unconditionally matched for all
- * domains.)
- * @type {Map.<string,Map.<string,boolean>>}
+ * Lookup table, selector by filter text by domain.
+ * (Only contains filter text for filters that aren't unconditionally matched
+ * for all domains.)
+ * @type {Map.<string,Map.<string,string>>}
  */
 let filterTextByDomain = new Map();
 
 /**
  * Lookup table, filter text by selector. (Only used for selectors that are
  * unconditionally matched for all domains.)
  * @type {Map.<string,string>}
  */
 let filterTextBySelector = new Map();
 
@@ skipping 15 matching lines @@
 /**
  * The common style sheet that applies on all unknown domains. This is a
  * concatenation of the default style sheet and an additional style sheet based
  * on selectors from all generic filters that are not in the
  * <code>{@link unconditionalSelectors}</code> list.
  * @type {?string}
  */
 let commonStyleSheet = null;
 
 /**
+ * Cache of generated domain-specific style sheets. This contains entries for
+ * only known domains. If a domain is unknown, it gets
+ * <code>{@link commonStyleSheet}</code>.
+ * @type {Cache.<string, string>}
+ */
+let styleSheetCache = new Cache(100);
+
+/**
  * 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 the text of known element hiding filters
+ * Set containing text of known element hiding filters
  * @type {Set.<string>}
  */
 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 && !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 filter text by domain.
+ * Adds a filter to the lookup table of filters 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 map = filterTextByDomain.get(domain);
-    if (!map)
-      filterTextByDomain.set(domain, map = new Map());
-    map.set(filter.text, isIncluded ? filter.selector : null);
+    let filters = filterTextByDomain.get(domain);
+    if (!filters)
+      filterTextByDomain.set(domain, filters = new Map());
+    filters.set(filter.text, isIncluded ? filter.selector : null);
   }
 }
 
 /**
  * Returns a list of selectors that apply on each website unconditionally.
  * @returns {string[]}
  */
 function getUnconditionalSelectors()
 {
   if (!unconditionalSelectors)
@@ skipping 10 matching lines @@
  * @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 map = filterTextByDomain.get(currentDomain);
-    if (map)
-    {
-      for (let [text, selector] of map)
-      {
-        if (selector == null)
+
+  for (let currentDomain of domainSuffixes(domain, !specificOnly))
+  {
+    let filters = filterTextByDomain.get(currentDomain);
+    if (filters)
+    {
+      for (let [text, selector] of filters)
+      {
+        if (!selector)
         {
           excluded.add(text);
         }
         else if ((excluded.size == 0 || !excluded.has(text)) &&
                  !ElemHideExceptions.getException(selector, domain))
         {
           selectors.push(selector);
         }
       }
     }
-
-    if (currentDomain == "")
-      break;
-
-    let nextDot = currentDomain.indexOf(".");
-    currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
   }
 
   return selectors;
+}
+
+/**
+ * Returns the list of selectors and the list of exceptions 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 {{selectors: Array.<string>, exceptions: Array.<ElemHideException>}}
+ *   An object containing the lists of selectors and exceptions.
+ */
+function getConditionalSelectorsWithExceptions(domain, specificOnly)
+{
+  let selectors = [];
+  let exceptions = [];
+
+  let excluded = new Set();
+
+  for (let currentDomain of domainSuffixes(domain, !specificOnly))
+  {
+    let filters = filterTextByDomain.get(currentDomain);
+    if (filters)
+    {
+      for (let [text, selector] of filters)
+      {
+        if (!selector)
+        {
+          excluded.add(text);
+        }
+        else if (excluded.size == 0 || !excluded.has(text))
+        {
+          let exception = ElemHideExceptions.getException(selector, domain);
+
+          if (exception)
+            exceptions.push(exception);
+          else
+            selectors.push(selector);
+        }
+      }
+    }
+  }
+
+  return {selectors, exceptions};
 }
 
 /**
  * Returns the default style sheet that applies on all domains.
  * @returns {string}
  */
 function getDefaultStyleSheet()
 {
   if (!defaultStyleSheet)
     defaultStyleSheet = createStyleSheet(getUnconditionalSelectors());
 
   return defaultStyleSheet;
 }
 
 /**
  * Returns the common style sheet that applies on all unknown domains.
  * @returns {string}
  */
 function getCommonStyleSheet()
 {
   if (!commonStyleSheet)
   {
     commonStyleSheet = getDefaultStyleSheet() +
                        createStyleSheet(getConditionalSelectors("", false));
   }
 
   return commonStyleSheet;
 }
 
+/**
+ * Returns the domain-specific style sheet that applies on a given domain.
+ * @param {string} domain
+ * @returns {string}
+ */
+function getDomainSpecificStyleSheet(domain)
+{
+  let styleSheet = styleSheetCache.get(domain);
+
+  if (typeof styleSheet == "undefined")
+  {
+    styleSheet = createStyleSheet(getConditionalSelectors(domain, false));
+    styleSheetCache.set(domain, styleSheet);
+  }
+
+  return styleSheet;
+}
+
 ElemHideExceptions.on("added", ({domains, selector}) =>
 {
+  styleSheetCache.clear();
   commonStyleSheet = null;
 
   if (domains)
   {
     for (let domain of domains.keys())
     {
       // 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 unconditionalFilterTextForSelector = filterTextBySelector.get(selector);
-  if (unconditionalFilterTextForSelector)
-  {
-    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

+  let unconditionalFilterForSelector = filterTextBySelector.get(selector);
+  if (unconditionalFilterForSelector)
+  {
+    addToFiltersByDomain(Filter.fromText(unconditionalFilterForSelector,
+                                         false));
     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 [filterTextByDomain, filterTextBySelector,
-                            knownFilterText, knownExceptionDomains])
+    for (let collection of [styleSheetCache, filterTextByDomain,
+                            filterTextBySelector, knownFilterText,
+                            knownExceptionDomains])
     {
       collection.clear();
     }
 
     unconditionalSelectors = null;
     defaultStyleSheet = null;
 
     filterNotifier.emit("elemhideupdate");
   },
 
   /**
    * Add a new element hiding filter
    * @param {ElemHideFilter} filter
    */
   add(filter)
   {
     let {text} = filter;
 
     if (knownFilterText.has(text))
       return;
 
+    styleSheetCache.clear();
     commonStyleSheet = null;
 
     let {domains, selector} = filter;
 
     if (!(domains || ElemHideExceptions.hasExceptions(selector)))
     {
       // The new filter's selector is unconditionally applied to all domains
       filterTextBySelector.set(selector, text);
       unconditionalSelectors = null;
       defaultStyleSheet = null;
@@ skipping 12 matching lines @@
    * Removes an element hiding filter
    * @param {ElemHideFilter} filter
    */
   remove(filter)
   {
     let {text} = filter;
 
     if (!knownFilterText.has(text))
       return;
 
+    styleSheetCache.clear();
     commonStyleSheet = null;
 
     let {selector} = filter;
 
     // Unconditially applied element hiding filters
     if (filterTextBySelector.get(selector) == text)
     {
       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 map = filterTextByDomain.get(domain);
-        if (map)
+        let filters = filterTextByDomain.get(domain);
+        if (filters)
         {
-          map.delete(text);
-
-          if (map.size == 0)
+          filters.delete(text);
+
+          if (filters.size == 0)
             filterTextByDomain.delete(domain);
         }
       }
     }
 
     knownFilterText.delete(text);
     filterNotifier.emit("elemhideupdate");
   },
 
   /**
    * @typedef {object} ElemHideStyleSheet
    * @property {string} code CSS code.
    * @property {Array.<string>} selectors List of selectors.
    */
 
   /**
    * Generates a style sheet for a given domain based on the current set of
    * filters.
    *
    * @param {string} domain The domain.
    * @param {boolean} [specificOnly=false] Whether selectors from generic
    *   filters should be included.
    * @param {boolean} [includeSelectors=false] Whether the return value should
    *   include a separate list of selectors.
+   * @param {boolean} [includeExceptions=false] Whether the return value should
+   *   include a separate list of exceptions.
    *
    * @returns {ElemHideStyleSheet} An object containing the CSS code and the
    *   list of selectors.
    */
   generateStyleSheetForDomain(domain, specificOnly = false,
-                              includeSelectors = false)
+                              includeSelectors = false,
+                              includeExceptions = false)
   {
     let code = null;
     let selectors = null;
-
-    if (domain[domain.length - 1] == ".")
-      domain = domain.replace(/\.+$/, "");
-
-    domain = domain.toLowerCase();
+    let exceptions = null;
+
+    domain = normalizeHostname(domain);
 
     if (specificOnly)
     {
-      selectors = getConditionalSelectors(domain, true);
+      if (includeExceptions)
+      {
+        let selectorsAndExceptions =
+          getConditionalSelectorsWithExceptions(domain, true);
+
+        selectors = selectorsAndExceptions.selectors;
+        exceptions = selectorsAndExceptions.exceptions;
+      }
+      else
+      {
+        selectors = getConditionalSelectors(domain, true);
+      }
+
       code = createStyleSheet(selectors);
     }
     else
     {
       let knownSuffix = getKnownSuffix(domain);
 
-      if (includeSelectors)
-      {
-        selectors = getConditionalSelectors(knownSuffix, false);
+      if (includeSelectors || includeExceptions)
+      {
+        let selectorsAndExceptions =
+          getConditionalSelectorsWithExceptions(knownSuffix, false);
+
+        selectors = selectorsAndExceptions.selectors;
+        exceptions = selectorsAndExceptions.exceptions;
         code = knownSuffix == "" ? getCommonStyleSheet() :
                  (getDefaultStyleSheet() + createStyleSheet(selectors));
 
         selectors = getUnconditionalSelectors().concat(selectors);
       }
       else
       {
         code = knownSuffix == "" ? getCommonStyleSheet() :
                  (getDefaultStyleSheet() +
-                  createStyleSheet(getConditionalSelectors(knownSuffix,
-                                                           false)));
-      }
-    }
-
-    return {code, selectors: includeSelectors ? selectors : null};
+                  getDomainSpecificStyleSheet(knownSuffix));
+      }
+    }
+
+    return {
+      code,
+      selectors: includeSelectors ? selectors : null,
+      exceptions: includeExceptions ? exceptions : null
+    };
   }
 };
 
 /**
  * Yields rules from a style sheet returned by
  * <code>{@link createStyleSheet}</code>.
  *
  * @param {string} styleSheet A style sheet returned by
  *   <code>{@link createStyleSheet}</code>. If the given style sheet is
  *   <em>not</em> a value previously returned by a call to
@@ skipping 31 matching lines @@
   // calculate the sizes of the selectors and divide them up accordingly, but
   // this approach is more efficient and has worked well in practice. In theory
   // this could still lead to some selectors not working on Chromium, but it is
   // highly unlikely.
   // See issue #6298 and https://crbug.com/804179
   for (let i = 0; i < selectors.length; i += selectorGroupSize)
     yield selectors.slice(i, i + selectorGroupSize);
 }
 
 /**
+ * Escapes curly braces to prevent CSS rule injection.
+ *
+ * @param {string} selector
+ * @returns {string}
+ */
+function escapeSelector(selector)
+{
+  return selector.replace("{", "\\7B ").replace("}", "\\7D ");
+}
+
+/**
  * Creates an element hiding CSS rule for a given list of selectors.
  *
  * @param {Array.<string>} selectors
  * @returns {string}
  */
 function createRule(selectors)
 {
   let rule = "";
 
   for (let i = 0; i < selectors.length - 1; i++)
-    rule += selectors[i] + ", ";
-
-  rule += selectors[selectors.length - 1] + " {display: none !important;}\n";
+    rule += escapeSelector(selectors[i]) + ", ";
+
+  rule += escapeSelector(selectors[selectors.length - 1]) +
+          " {display: none !important;}\n";
 
   return rule;
 }
 
 /**
  * Creates an element hiding CSS style sheet from a given list of selectors.
  * @param {Array.<string>} selectors
  * @returns {string}
  */
 function createStyleSheet(selectors)
 {
   let styleSheet = "";
 
   for (let selectorGroup of splitSelectors(selectors))
     styleSheet += createRule(selectorGroup);
 
   return styleSheet;
 }
 
 exports.createStyleSheet = createStyleSheet;