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
@@ skipping 181 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;
       }
     }
   }
 };
 
 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;
       }
     }
   }
 };
 
 function PropsSelector(propertyExpression)
@@ skipping 25 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 164 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;
+
         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 150 matching lines @@
           characterData: shouldObserveCharacterData(this.patterns),
           subtree: true
         }
       );
       this.document.addEventListener("load", this.onLoad.bind(this), true);
     }
   }
 };
 
 exports.ElemHideEmulation = ElemHideEmulation;