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 debugInfo = null;
+
+function setDebugMode()
+{
+  debugInfo = {
+    lastProcessedElements: new Set()
+  };
+}
+
+exports.setDebugMode = setDebugMode;
+
+function getDebugInfo()
+{
+  return debugInfo;
+}
+
+exports.getDebugInfo = getDebugInfo;
+
 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 (debugInfo)
+          debugInfo.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 (debugInfo)
+          debugInfo.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 (debugInfo)
+      debugInfo.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 (debugInfo)
+    {
+      // In debug 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.
+      //
+      // Note: This also creates the potential for "heisenbugs", but as long as
+      // this is the only instance it should be manageable.
+      mutations = mutations.filter(
+        ({type, attributeName, target: {style: newValue}, oldValue}) =>
+        !(type == "attributes" && attributeName == "style" &&
+          newValue.display == "none" && oldValue.display != "none")
+      );
+
+      if (mutations.length == 0)
+        return;
+    }
+
     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;