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.
@@ skipping 155 matching lines @@
   try
   {
     return new RegExp(pattern, flags);
   }
   catch (e)
   {
   }
   return null;
 }
 
-function* evaluate(chain, index, prefix, subtree, styles)
+function* evaluate(chain, index, prefix, subtree, styles, targets)
 {
   if (index >= chain.length)
   {
     yield prefix;
     return;
   }
   for (let [selector, element] of
-       chain[index].getSelectors(prefix, subtree, styles))
+       chain[index].getSelectors(prefix, subtree, styles, targets))
   {
     if (selector == null)
       yield null;
     else
-      yield* evaluate(chain, index + 1, selector, element, styles);
+      yield* evaluate(chain, index + 1, selector, element, styles, targets);
   }
   // 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)
+  *getSelectors(prefix, subtree, styles, targets)
   {
     yield [prefix + this._selector, subtree];
   }
 };
 
 const incompletePrefixRegexp = /[\s>+~]$/;
 
 function HasSelector(selectors)
 {
   this._innerSelectors = selectors;
@@ skipping 14 matching lines @@
     );
   },
 
   get maybeDependsOnAttributes()
   {
     return this._innerSelectors.some(
       selector => selector.maybeDependsOnAttributes
     );
   },
 
-  *getSelectors(prefix, subtree, styles)
+  *getSelectors(prefix, subtree, styles, targets)
   {
-    for (let element of this.getElements(prefix, subtree, styles))
+    for (let element of this.getElements(prefix, subtree, styles, targets))
       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)
+  *getElements(prefix, subtree, styles, targets)
   {
     let actualPrefix = (!prefix || incompletePrefixRegexp.test(prefix)) ?
         prefix + "*" : prefix;
     let elements = scopedQuerySelectorAll(subtree, actualPrefix);
     if (elements)
     {
       for (let element of elements)
       {
-        let iter = evaluate(this._innerSelectors, 0, "", element, styles);
+        // If the element is neither an ancestor nor a descendant of one of the
+        // targets, we can skip it.
+        if (targets && !targets.some(target => element.contains(target) ||
+                                               target.contains(element)))
+        {
+          yield null;
+          continue;
+        }
+
+        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 = {
   dependsOnDOM: true,
   dependsOnCharacterData: true,
 
-  *getSelectors(prefix, subtree, styles)
+  *getSelectors(prefix, subtree, styles, targets)
   {
-    for (let element of this.getElements(prefix, subtree, styles))
+    for (let element of this.getElements(prefix, subtree, styles, targets))
       yield [makeSelector(element), subtree];
   },
 
-  *getElements(prefix, subtree, styles)
+  *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) ||
+                                               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] == "/")
@@ skipping 21 matching lines @@
           {
             subSelector = subSelector.substr(1);
           }
           let idx = subSelector.lastIndexOf("::");
           if (idx != -1)
             subSelector = subSelector.substr(0, idx);
           yield prefix + subSelector;
         }
   },
 
-  *getSelectors(prefix, subtree, styles)
+  *getSelectors(prefix, subtree, styles, targets)
   {
     for (let selector of this.findPropsSelectors(styles, prefix, this._regexp))
       yield [selector, subtree];
   }
 };
 
 function Pattern(selectors, text)
 {
   this.selectors = selectors;
   this.text = text;
@@ skipping 45 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]
@@ skipping 20 matching lines @@
 
     // 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);
+    }
+    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 &&
@@ skipping 107 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 37 matching lines @@
 
       for (let rule of rules)
       {
         if (rule.type != rule.STYLE_RULE)
           continue;
 
         cssStyles.push(stringifyStyle(rule));
       }
     }
 
+    let targets = extractMutationTargets(mutations);
+
     let pattern = null;
     let generator = null;
 
     let processPatterns = () =>
     {
       let cycleStart = performance.now();
 
       if (!pattern)
       {
         if (!patterns.length)
         {
           if (selectors.length > 0)
             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);
+                             this.document, cssStyles, evaluationTargets);
       }
       for (let selector of generator)
       {
         if (selector != null)
         {
           if (!this.useInlineStyles)
           {
             selectors.push(selector);
             selectorFilters.push(pattern.text);
           }
@@ skipping 119 matching lines @@
 
   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;