Issue 5650 - Apply emulation filters to shadow DOMs

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 22 matching lines @@
   for (let i = 0; i < children.length; i++)
     if (children[i] == node)
       return i + 1;
   return 0;
 }
 
 function makeSelector(node, selector)
 {
   if (node == null)
     return null;
-  if (!node.parentElement)
+
+  // If this is the topmost element in a shadow DOM, climb up one more level
+  // and then use a ":host" prefix.
+  if (!node.parentElement && !(node.parentNode instanceof ShadowRoot))
   {
-    let newSelector = ":root";
+    let newSelector = node instanceof ShadowRoot ? ":host" : ":root";
     if (selector)
       newSelector += " > " + selector;
     return newSelector;
   }
   let idx = positionInParent(node);
   if (idx > 0)
   {
     let newSelector = `${node.tagName}:nth-child(${idx})`;
     if (selector)
       newSelector += " > " + selector;
-    return makeSelector(node.parentElement, newSelector);
+    return makeSelector(node.parentElement || node.parentNode, newSelector);
   }
 
   return selector;
 }
 
 function parseSelectorContent(content, startIndex)
 {
   let parens = 1;
   let quote = null;
   let i = startIndex;
@@ skipping 69 matching lines @@
       yield null;
     else
       yield* evaluate(chain, index + 1, selector, element, styles);
   }
   // 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 removeRedundantNodes(nodes)

[Manish Jethani, 2017/10/18 23:07:59]

We have to do this, because often (too often) when the DOM is constructed
programmatically, multiple levels of nodes are added at once, then we get
multiple mutations at once. We are only interested in the most common ancestors.

For example, on the TechCrunch home page I'm getting 31 nodes added. They all
have one common ancestor. If we don't remove all the others from the list, we
end up checking 261 nodes for shadow roots. On the other hand, when we do remove
all but the common ancestor, we do only 31 checks.

This algorithm is the most efficient I could come up with. There's a comment in
there about an optimization.

+{
+  let nodesInfo = [];
+  for (let node of nodes)
+  {
+    let nodeInfo = {node};
+    nodesInfo.push(nodeInfo);
+
+    let link = node;
+    while (link = link.parentNode)
+    {
+      // Since a node's ancestors are always added to the DOM before it, they
+      // will likely also appear before it in the list (at least on Chromium).
+      // If we encounter an ancestor here that has already been marked
+      // redundant, we can mark this node redundant too. This is an
+      // optimization that saves us having to do a lookup in the set and keep
+      // walking up the tree.
+      if (link.redundant || nodes.has(link))
+      {
+        nodeInfo.redundant = true;
+        break;
+      }
+    }
+  }
+
+  for (let nodeInfo of nodesInfo)
+  {
+    if (nodeInfo.redundant)
+      nodes.delete(nodeInfo.node);
+  }
+
+  return nodes;
+}
+
+function* traverse(nodes)
+{
+  for (let node of nodes)
+  {
+    yield* traverse(node.children, node);
+    yield node;
+  }
+}
+
+function niceLoop(iterator, callback)

[Manish Jethani, 2017/10/18 23:07:59]

This is basically an abstraction of what is happening elsewhere in the code. It
iterates over the iterator and calls the callback for each item, taking a break
every once in a while.

+{
+  let loop = () =>
+  {
+    let cycleStart = performance.now();
+
+    for (let next = iterator.next(); !next.done; next = iterator.next())

[Manish Jethani, 2017/10/18 23:07:59]

We cannot simply do "for (let item of iterator) ..." here, it does not work with
yield* for some reason. I'm pretty sure it's broken elsewhere in the code as
well. I'll take a look.

+    {
+      callback(next.value);
+
+      if (performance.now() - cycleStart > MAX_SYNCHRONOUS_PROCESSING_TIME)
+        setTimeout(loop, 0);
+    }
+  };
+
+  loop();
+}
+
 function PlainSelector(selector)
 {
   this._selector = selector;
 }
 
 PlainSelector.prototype = {
   /**
    * Generator function returning a pair of selector
    * string and subtree.
    * @param {string} prefix the prefix for the selector.
@@ skipping 139 matching lines @@
       yield [selector, subtree];
   }
 };
 
 function isSelectorHidingOnlyPattern(pattern)
 {
   return pattern.selectors.some(s => s.preferHideWithSelector) &&
     !pattern.selectors.some(s => s.requiresHiding);
 }
 
-function ElemHideEmulation(addSelectorsFunc, hideElemsFunc)
+function ElemHideEmulation(document, root, addSelectorsFunc, hideElemsFunc)
 {
   this.document = document;
+  this.root = root || document;
   this.addSelectorsFunc = addSelectorsFunc;
   this.hideElemsFunc = hideElemsFunc;
+  this.patterns = [];

[Manish Jethani, 2017/10/18 23:07:59]

This needs to be initialized.

   this.observer = new MutationObserver(this.observe.bind(this));
+  this.shadowEmulations = new WeakMap();
+
+  if (this.root == this.document)
+  {
+    this.document.addEventListener("load", this.onLoad.bind(this), true);
+    this.document.addEventListener("shadowAttached",
+                                   this.onShadowAttached.bind(this), true);
+  }
 }
 
 ElemHideEmulation.prototype = {
   isSameOrigin(stylesheet)
   {
     try
     {
       return new URL(stylesheet.href).origin == this.document.location.origin;
     }
     catch (e)
@@ skipping 81 matching lines @@
     let selectors = [];
     let selectorFilters = [];
 
     let elements = [];
     let elementFilters = [];
 
     let cssStyles = [];
 
     let stylesheetOnlyChange = !!stylesheets;
     if (!stylesheets)
-      stylesheets = this.document.styleSheets;
+      stylesheets = this.root.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;
       if (!rules)
@@ skipping 29 matching lines @@
 
         pattern = patterns.shift();
 
         if (stylesheetOnlyChange &&
             !pattern.selectors.some(selector => selector.dependsOnStyles))
         {
           pattern = null;
           return processPatterns();
         }
         generator = evaluate(pattern.selectors, 0, "",
-                             this.document, cssStyles);
+                             this.root, cssStyles);
       }
       for (let selector of generator)
       {
         if (selector != null)
         {
           if (isSelectorHidingOnlyPattern(pattern))
           {
             selectors.push(selector);
             selectorFilters.push(pattern.text);
           }
           else
           {
-            for (let element of this.document.querySelectorAll(selector))
+            for (let element of this.root.querySelectorAll(selector))
             {
               elements.push(element);
               elementFilters.push(pattern.text);
             }
           }
         }
         if (performance.now() - cycleStart > MAX_SYNCHRONOUS_PROCESSING_TIME)
         {
           setTimeout(processPatterns, 0);
           return;
@@ skipping 67 matching lines @@
     }
     else
     {
       this._filteringInProgress = true;
       this._addSelectors(stylesheets, completion);
     }
   },
 
   onLoad(event)
   {
+    if (this.patterns.length == 0)
+      return;
+
     let stylesheet = event.target.sheet;
     if (stylesheet)
       this.queueFiltering([stylesheet]);
   },
 
+  onShadowAttached(event)
+  {
+    event.stopImmediatePropagation();
+
+    if (this.patterns.length == 0)
+      return;
+
+    // The shadow root may not be available if it's a closed shadow root.
+    let shadowRoot = event.target.shadowRoot;
+    if (!shadowRoot)
+      return;
+
+    this.addShadowRoot(shadowRoot);
+  },
+
+  addShadowRoot(shadowRoot)
+  {
+    if (!this.shadowEmulations.has(shadowRoot))
+    {
+      let emulation = new ElemHideEmulation(this.document,
+                                            shadowRoot,
+                                            this.addSelectorsFunc,
+                                            this.hideElemsFunc);
+      this.shadowEmulations.set(shadowRoot, emulation);
+      emulation.apply(this.patterns, true);
+    }
+  },
+
   observe(mutations)
   {
+    let allAddedElements = new Set();
+    for (let mutation of mutations)
+    {
+      for (let node of mutation.addedNodes)
+      {
+        if (node instanceof Element)
+          allAddedElements.add(node);
+      }
+    }
+
+    // Find any preattached shadows.
+    niceLoop(traverse(removeRedundantNodes(allAddedElements)), node =>
+    {
+      let shadowRoot = node.shadowRoot;
+      if (shadowRoot)
+        this.addShadowRoot(shadowRoot);
+    });
+
     this.queueFiltering();
   },
 
-  apply(patterns)
+  apply(patterns, parsed)
   {
-    this.patterns = [];
-    for (let pattern of patterns)
+    if (parsed)
     {
-      let selectors = this.parseSelector(pattern.selector);
-      if (selectors != null && selectors.length > 0)
-        this.patterns.push({selectors, text: pattern.text});
+      this.patterns = patterns;
+    }
+    else
+    {
+      this.patterns = [];
+      for (let pattern of patterns)
+      {
+        let selectors = this.parseSelector(pattern.selector);
+        if (selectors != null && selectors.length > 0)
+          this.patterns.push({selectors, text: pattern.text});
+      }
     }
 
     if (this.patterns.length > 0)
     {
       this.queueFiltering();
       this.observer.observe(
-        this.document,
+        this.root,
         {
           childList: true,
           attributes: true,
           characterData: true,
           subtree: true
         }
       );
-      this.document.addEventListener("load", this.onLoad.bind(this), true);
     }
   }
 };
 
 exports.ElemHideEmulation = ElemHideEmulation;