Issue 6437 - Skip elements not affected by DOM mutations

lib/content/elemHideEmulation.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";
 
 const {textToRegExp, filterToRegExp, splitSelector} = require("../common");
+const {indexOf} = require("../coreUtils");
 
 let MIN_INVOCATION_INTERVAL = 3000;
 const MAX_SYNCHRONOUS_PROCESSING_TIME = 50;
 const abpSelectorRegexp = /:-abp-([\w-]+)\(/i;
+
+let testInfo = null;
+
+function setTestMode()
+{
+  testInfo = {
+    lastProcessedElements: new Set()
+  };
+}
+
+exports.setTestMode = setTestMode;
+
+function getTestInfo()
+{
+  return testInfo;
+}
+
+exports.getTestInfo = getTestInfo;

[hub, 2018/05/24 19:19:09]

I'm a bit skeptical with that way or test, including leaving unused code in the
release.

Sadly we don't have spies in our test framework (maybe we should).

[Manish Jethani, 2018/05/25 07:21:25]

We can work on improving our test framework, but for now this is what we have.
Between not having this testing code at all and having it as "dead code" in
production, I'd still go with the latter. At least we're checking our
assumptions in the tests and making sure nothing breaks.

 
 function getCachedPropertyValue(object, name, defaultValueFunc = () => {})
 {
   let value = object[name];
   if (typeof value == "undefined")
     Object.defineProperty(object, name, {value: value = defaultValueFunc()});
   return value;
 }
 
 /** Return position of node from parent.
  * @param {Node} node the node to find the position of.
  * @return {number} One-based index like for :nth-child(), or 0 on error.
  */
 function positionInParent(node)
 {
-  let {children} = node.parentNode;
-  for (let i = 0; i < children.length; i++)
-    if (children[i] == node)
-      return i + 1;
-  return 0;
-}
-
-function makeSelector(node, selector)
+  return indexOf(node.parentNode.children, node) + 1;
+}
+
+function makeSelector(node, selector = "")
 {
   if (node == null)
     return null;
   if (!node.parentElement)
   {
     let newSelector = ":root";
     if (selector)
       newSelector += " > " + selector;
     return newSelector;
   }
@@ skipping 114 matching lines @@
   }
   return all ? subtree.querySelectorAll(selector) :
     subtree.querySelector(selector);
 }
 
 function scopedQuerySelectorAll(subtree, selector)
 {
   return scopedQuerySelector(subtree, selector, true);
 }
 
-const regexpRegexp = /^\/(.*)\/([im]*)$/;
+const regexpRegexp = /^\/(.*)\/([imu]*)$/;
 
 /**
  * Make a regular expression from a text argument. If it can be parsed as a
  * regular expression, parse it and the flags.
  * @param {string} text the text argument.
  * @return {?RegExp} a RegExp object or null in case of error.
  */
 function makeRegExpParameter(text)
 {
   let [, pattern, flags] =
@@ skipping 27 matching lines @@
   // Just in case the getSelectors() generator above had to run some heavy
   // document.querySelectorAll() call which didn't produce any results, make
   // sure there is at least one point where execution can pause.
   yield null;
 }
 
 function PlainSelector(selector)
 {
   this._selector = selector;
   this.maybeDependsOnAttributes = /[#.]|\[.+\]/.test(selector);
+  this.dependsOnDOM = this.maybeDependsOnAttributes;
+  this.maybeContainsSiblingCombinators = /[~+]/.test(selector);
 }
 
 PlainSelector.prototype = {
   /**
    * Generator function returning a pair of selector
    * string and subtree.
    * @param {string} prefix the prefix for the selector.
    * @param {Node} subtree the subtree we work on.
    * @param {StringifiedStyle[]} styles the stringified style objects.
    * @param {Node[]} [targets] the nodes we are interested in.
    */
   *getSelectors(prefix, subtree, styles, targets)
   {
     yield [prefix + this._selector, subtree];
   }
 };
 
 const incompletePrefixRegexp = /[\s>+~]$/;
 
 function HasSelector(selectors)
 {
   this._innerSelectors = selectors;
 }
 
 HasSelector.prototype = {
-  requiresHiding: true,
   dependsOnDOM: true,
 
   get dependsOnStyles()
   {
     return this._innerSelectors.some(selector => selector.dependsOnStyles);
   },
 
   get dependsOnCharacterData()
   {
     return this._innerSelectors.some(
       selector => selector.dependsOnCharacterData
     );
   },
 
   get maybeDependsOnAttributes()
   {
     return this._innerSelectors.some(
       selector => selector.maybeDependsOnAttributes
     );
   },
 
   *getSelectors(prefix, subtree, styles, targets)
   {
     for (let element of this.getElements(prefix, subtree, styles, targets))
-      yield [makeSelector(element, ""), element];
+      yield [makeSelector(element), element];
   },
 
   /**
    * Generator function returning selected elements.
    * @param {string} prefix the prefix for the selector.
    * @param {Node} subtree the subtree we work on.
    * @param {StringifiedStyle[]} styles the stringified style objects.
    * @param {Node[]} [targets] the nodes we are interested in.
    */
   *getElements(prefix, subtree, styles, targets)
@@ skipping 17 matching lines @@
         let iter = evaluate(this._innerSelectors, 0, "", element, styles,
                             targets);
         for (let selector of iter)
         {
           if (selector == null)
             yield null;
           else if (scopedQuerySelector(element, selector))
             yield element;
         }
         yield null;
+
+        if (testInfo)
+          testInfo.lastProcessedElements.add(element);
       }
     }
   }
 };
 
 function ContainsSelector(textContent)
 {
   this._regexp = makeRegExpParameter(textContent);
 }
 
 ContainsSelector.prototype = {
-  requiresHiding: true,
   dependsOnDOM: true,
   dependsOnCharacterData: true,
 
   *getSelectors(prefix, subtree, styles, targets)
   {
     for (let element of this.getElements(prefix, subtree, styles, targets))
-      yield [makeSelector(element, ""), subtree];
+      yield [makeSelector(element), subtree];
   },
 
   *getElements(prefix, subtree, styles, targets)
   {
     let actualPrefix = (!prefix || incompletePrefixRegexp.test(prefix)) ?
         prefix + "*" : prefix;
 
     let elements = scopedQuerySelectorAll(subtree, actualPrefix);
+
     if (elements)
     {
+      let lastRoot = null;
       for (let element of elements)
       {
+        // For a filter like div:-abp-contains(Hello) and a subtree like
+        // <div id="a"><div id="b"><div id="c">Hello</div></div></div>
+        // we're only interested in div#a
+        if (lastRoot && lastRoot.contains(element))
+        {
+          yield null;
+          continue;
+        }
+
+        lastRoot = element;
+
         if (targets && !targets.some(target => element.contains(target) ||

[Manish Jethani, 2018/03/20 10:21:57]

By the way this may not seem like such a great idea until you realize how slow
Element.textContent is. The element has to collect text from all of its
children.

                                                target.contains(element)))
         {
           yield null;
           continue;
         }
 
         if (this._regexp && this._regexp.test(element.textContent))
           yield element;
         else
           yield null;
+
+        if (testInfo)
+          testInfo.lastProcessedElements.add(element);
       }
     }
   }
 };
 
 function PropsSelector(propertyExpression)
 {
   let regexpString;
   if (propertyExpression.length >= 2 && propertyExpression[0] == "/" &&
       propertyExpression[propertyExpression.length - 1] == "/")
   {
     regexpString = propertyExpression.slice(1, -1)
       .replace("\\7B ", "{").replace("\\7D ", "}");
   }
   else
     regexpString = filterToRegExp(propertyExpression);
 
   this._regexp = new RegExp(regexpString, "i");
 }
 
 PropsSelector.prototype = {
-  preferHideWithSelector: true,
   dependsOnStyles: true,
 
   *findPropsSelectors(styles, prefix, regexp)
   {
     for (let style of styles)
       if (regexp.test(style.style))
         for (let subSelector of style.subSelectors)
         {
           if (subSelector.startsWith("*") &&
               !incompletePrefixRegexp.test(prefix))
@@ skipping 14 matching lines @@
   }
 };
 
 function Pattern(selectors, text)
 {
   this.selectors = selectors;
   this.text = text;
 }
 
 Pattern.prototype = {
-  isSelectorHidingOnlyPattern()
-  {
-    return getCachedPropertyValue(
-      this, "_selectorHidingOnlyPattern",
-      () => this.selectors.some(selector => selector.preferHideWithSelector) &&
-            !this.selectors.some(selector => selector.requiresHiding)
-    );
-  },
-
   get dependsOnStyles()
   {
     return getCachedPropertyValue(
       this, "_dependsOnStyles",
       () => this.selectors.some(selector => selector.dependsOnStyles)
     );
   },
 
   get dependsOnDOM()
   {
@@ skipping 30 matching lines @@
   },
 
   get dependsOnCharacterData()
   {
     // Observe changes to character data only if there's a contains selector in
     // one of the patterns.
     return getCachedPropertyValue(
       this, "_dependsOnCharacterData",
       () => this.selectors.some(selector => selector.dependsOnCharacterData)
     );
+  },
+
+  get maybeContainsSiblingCombinators()
+  {
+    return getCachedPropertyValue(
+      this, "_maybeContainsSiblingCombinators",
+      () => this.selectors.some(selector =>
+                                selector.maybeContainsSiblingCombinators)
+    );
+  },
+
+  matchesMutationTypes(mutationTypes)
+  {
+    let mutationTypeMatchMap = getCachedPropertyValue(
+      this, "_mutationTypeMatchMap",
+      () => new Map([
+        // All types of DOM-dependent patterns are affected by mutations of
+        // type "childList".
+        ["childList", true],
+        ["attributes", this.maybeDependsOnAttributes],
+        ["characterData", this.dependsOnCharacterData]
+      ])
+    );
+
+    for (let mutationType of mutationTypes)
+    {
+      if (mutationTypeMatchMap.get(mutationType))
+        return true;
+    }
+
+    return false;
   }
 };
+
+function extractMutationTypes(mutations)
+{
+  let types = new Set();
+
+  for (let mutation of mutations)
+  {
+    types.add(mutation.type);
+
+    // There are only 3 types of mutations: "attributes", "characterData", and
+    // "childList".
+    if (types.size == 3)
+      break;
+  }
+
+  return types;
+}
 
 function extractMutationTargets(mutations)
 {
   if (!mutations)
     return null;
 
   let targets = new Set();
 
   for (let mutation of mutations)
   {
     if (mutation.type == "childList")
     {
       // When new nodes are added, we're interested in the added nodes rather
       // than the parent.
       for (let node of mutation.addedNodes)
         targets.add(node);
-
-      // Ideally we would also be interested in removed nodes, but since we
-      // never unhide an element once hidden we can simply ignore any removed
-      // nodes. Note that this will change once we start using CSS selectors
-      // for -abp-has and -abp-contains, i.e. we'll have to remove the
-      // selectors for any removed nodes.
     }
     else
     {
       targets.add(mutation.target);
     }
   }
 
   return [...targets];
 }
 
 function filterPatterns(patterns, {stylesheets, mutations})
 {
   if (!stylesheets && !mutations)
     return patterns.slice();
 
+  let mutationTypes = mutations ? extractMutationTypes(mutations) : null;
+
   return patterns.filter(
     pattern => (stylesheets && pattern.dependsOnStyles) ||
-               (mutations && pattern.dependsOnDOM)
+               (mutations && pattern.dependsOnDOM &&
+                pattern.matchesMutationTypes(mutationTypes))
   );
 }
 
 function shouldObserveAttributes(patterns)
 {
   return patterns.some(pattern => pattern.maybeDependsOnAttributes);
 }
 
 function shouldObserveCharacterData(patterns)
 {
   return patterns.some(pattern => pattern.dependsOnCharacterData);
 }
 
 function ElemHideEmulation(addSelectorsFunc, hideElemsFunc)
 {
   this.document = document;
   this.addSelectorsFunc = addSelectorsFunc;
   this.hideElemsFunc = hideElemsFunc;
   this.observer = new MutationObserver(this.observe.bind(this));
+  this.useInlineStyles = true;
 }
 
 ElemHideEmulation.prototype = {
   isSameOrigin(stylesheet)
   {
     try
     {
       return new URL(stylesheet.href).origin == this.document.location.origin;
     }
     catch (e)
@@ skipping 76 matching lines @@
    * @param {MutationRecord[]} [mutations]
    *    The list of DOM mutations that have been applied to the document and
    *    made reprocessing necessary. This parameter shouldn't be passed in for
    *    the initial processing, the entire document will be considered
    *    then and all rules, including the ones not dependent on the DOM.
    * @param {function} [done]
    *    Callback to call when done.
    */
   _addSelectors(stylesheets, mutations, done)
   {
+    if (testInfo)
+      testInfo.lastProcessedElements.clear();
+
     let patterns = filterPatterns(this.patterns, {stylesheets, mutations});
 
     let selectors = [];
     let selectorFilters = [];
 
     let elements = [];
     let elementFilters = [];
 
     let cssStyles = [];
 
@@ skipping 11 matching lines @@
     if (mutations && patterns.some(pattern => pattern.dependsOnStylesAndDOM))
       stylesheets = this.document.styleSheets;
 
     for (let stylesheet of stylesheets || [])
     {
       // Explicitly ignore third-party stylesheets to ensure consistent behavior
       // between Firefox and Chrome.
       if (!this.isSameOrigin(stylesheet))
         continue;
 
-      let rules = stylesheet.cssRules;
+      let rules;
+      try
+      {
+        rules = stylesheet.cssRules;
+      }
+      catch (e)
+      {
+        // On Firefox, there is a chance that an InvalidAccessError
+        // get thrown when accessing cssRules. Just skip the stylesheet
+        // in that case.
+        // See https://searchfox.org/mozilla-central/rev/f65d7528e34ef1a7665b4a1a7b7cdb1388fcd3aa/layout/style/StyleSheet.cpp#699
+        continue;
+      }
+
       if (!rules)
         continue;
 
       for (let rule of rules)
       {
         if (rule.type != rule.STYLE_RULE)
           continue;
 
         cssStyles.push(stringifyStyle(rule));
       }
@@ skipping 16 matching lines @@
             this.addSelectorsFunc(selectors, selectorFilters);
           if (elements.length > 0)
             this.hideElemsFunc(elements, elementFilters);
           if (typeof done == "function")
             done();
           return;
         }
 
         pattern = patterns.shift();
 
+        let evaluationTargets = targets;
+
+        // If the pattern appears to contain any sibling combinators, we can't
+        // easily optimize based on the mutation targets. Since this is a
+        // special case, skip the optimization. By setting it to null here we
+        // make sure we process the entire DOM.
+        if (pattern.maybeContainsSiblingCombinators)
+          evaluationTargets = null;
+
+        // Ignore mutation targets when using style sheets, because we may have
+        // to update all the CSS selectors.
+        if (!this.useInlineStyles)
+          evaluationTargets = null;
+
         generator = evaluate(pattern.selectors, 0, "",
-                             this.document, cssStyles, targets);
+                             this.document, cssStyles, evaluationTargets);
       }
       for (let selector of generator)
       {
         if (selector != null)
         {
-          if (pattern.isSelectorHidingOnlyPattern())
+          if (!this.useInlineStyles)
           {
             selectors.push(selector);
             selectorFilters.push(pattern.text);
           }
           else
           {
             for (let element of this.document.querySelectorAll(selector))
             {
               elements.push(element);
               elementFilters.push(pattern.text);
@@ skipping 51 matching lines @@
         this.queueFiltering(params.stylesheets, params.mutations);
       }
     };
 
     if (this._scheduledProcessing)
     {
       if (!stylesheets && !mutations)
       {
         this._scheduledProcessing = {};
       }
-      else
+      else if (this._scheduledProcessing.stylesheets ||
+               this._scheduledProcessing.mutations)
       {
         if (stylesheets)
         {
           if (!this._scheduledProcessing.stylesheets)
             this._scheduledProcessing.stylesheets = [];
           this._scheduledProcessing.stylesheets.push(...stylesheets);
         }
         if (mutations)
         {
           if (!this._scheduledProcessing.mutations)
@@ skipping 16 matching lines @@
         this._scheduledProcessing = null;
         this._addSelectors(params.stylesheets, params.mutations, completion);
       },
       MIN_INVOCATION_INTERVAL - (performance.now() - this._lastInvocation));
     }
     else if (this.document.readyState == "loading")
     {
       this._scheduledProcessing = {stylesheets, mutations};
       let handler = () =>
       {
-        document.removeEventListener("DOMContentLoaded", handler);
+        this.document.removeEventListener("DOMContentLoaded", handler);
         let params = Object.assign({}, this._scheduledProcessing);
         this._filteringInProgress = true;
         this._scheduledProcessing = null;
         this._addSelectors(params.stylesheets, params.mutations, completion);
       };
-      document.addEventListener("DOMContentLoaded", handler);
+      this.document.addEventListener("DOMContentLoaded", handler);
     }
     else
     {
       this._filteringInProgress = true;
       this._addSelectors(stylesheets, mutations, completion);
     }
   },
 
   onLoad(event)
   {
     let stylesheet = event.target.sheet;
     if (stylesheet)
       this.queueFiltering([stylesheet]);
   },
 
   observe(mutations)
   {
+    if (testInfo)
+    {
+      // In test mode, filter out any mutations likely done by us
+      // (i.e. style="display: none !important"). This makes it easier to
+      // observe how the code responds to DOM mutations.
+      mutations = mutations.filter(
+        ({type, attributeName, target: {style: newValue}, oldValue}) =>
+        !(type == "attributes" && attributeName == "style" &&
+          newValue.display == "none" && oldValue.display != "none")
+      );
+
+      if (mutations.length == 0)
+        return;
+    }

[hub, 2018/05/24 19:19:09]

... and this :-/

There should be a better way to go at this.

[Manish Jethani, 2018/05/25 07:21:25]

OK, do you have any suggestions? This is only done in test mode, so it's
literally dead code otherwise. We don't have preprocessing or we could have
stripped it out.

+
     this.queueFiltering(null, mutations);
   },
 
   apply(patterns)
   {
     this.patterns = [];
     for (let pattern of patterns)
     {
       let selectors = this.parseSelector(pattern.selector);
       if (selectors != null && selectors.length > 0)
@@ skipping 11 matching lines @@
           characterData: shouldObserveCharacterData(this.patterns),
           subtree: true
         }
       );
       this.document.addEventListener("load", this.onLoad.bind(this), true);
     }
   }
 };
 
 exports.ElemHideEmulation = ElemHideEmulation;