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 18 matching lines @@
  */
 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 isShadowRoot(node)
+{
+  return typeof ShadowRoot != "undefined" && node instanceof ShadowRoot;
+}
+
 function makeSelector(node, selector)
 {
   if (node == null)
     return null;
 
   // 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 = node instanceof ShadowRoot ? ":host" : ":root";
+  if (!node.parentElement && !isShadowRoot(node.parentNode))
+  {
+    let newSelector = isShadowRoot(node) ? ":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;
@@ skipping 80 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 = [];
+function isDescendantOf(node, subtrees)
+{
+  return subtrees.some(subtree => subtree.contains(node));
+}
+
+function* extractAddedSubtrees(mutations)
+{
+  let knownSubtrees = [];
+
+  for (let mutation of mutations)
+  {
+    for (let node of mutation.addedNodes)
+    {
+      if (node instanceof Element && !isDescendantOf(node, knownSubtrees))
+      {
+        knownSubtrees.push(node);
+        yield node;
+      }
+    }
+  }
+}
+
+function* traverse(nodes)
+{
   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;
+    yield* traverse(node.children);
+    yield node;
+  }
+}
+
+function niceLoop(iterator, callback)
+{
+  let loop = () =>
+  {
+    let cycleStart = performance.now();
+
+    for (let next = iterator.next(); !next.done; next = iterator.next())
+    {
+      callback(next.value);
+
+      if (performance.now() - cycleStart > MAX_SYNCHRONOUS_PROCESSING_TIME)
+      {
+        setTimeout(loop, 0);
+        return;
       }
-    }
-  }
-
-  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;
 }
@@ skipping 145 matching lines @@
       yield [selector, subtree];
   }
 };
 
 function isSelectorHidingOnlyPattern(pattern)
 {
   return pattern.selectors.some(s => s.preferHideWithSelector) &&
     !pattern.selectors.some(s => s.requiresHiding);
 }
 
-function ElemHideEmulation(document, root, addSelectorsFunc, hideElemsFunc)
+function ElemHideEmulation(document, root, addSelectorsFunc, hideElemsFunc,
+                           shadowAttachedEventType)
 {
   this.document = document;
   this.root = root || document;
   this.addSelectorsFunc = addSelectorsFunc;
   this.hideElemsFunc = hideElemsFunc;
+  this.shadowAttachedEventType = shadowAttachedEventType;
   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 (shadowAttachedEventType)
+  {
+    this.root.addEventListener(shadowAttachedEventType,
+                               this.onShadowAttached.bind(this), true);
+  }
+
   if (this.root == this.document)
-  {
     this.document.addEventListener("load", this.onLoad.bind(this), true);
-    this.document.addEventListener("shadowAttached",
-                                   this.onShadowAttached.bind(this), true);
-  }
+  else
+    this.findShadowRoots(this.root.children);
 }
 
 ElemHideEmulation.prototype = {
   isSameOrigin(stylesheet)
   {
     try
     {
       return new URL(stylesheet.href).origin == this.document.location.origin;
     }
     catch (e)
@@ skipping 232 matching lines @@
     }
     else
     {
       this._filteringInProgress = true;
       this._addSelectors(stylesheets, completion);
     }
   },
 
   onLoad(event)
   {
+    this.findShadowRoots(this.root.children);
+
     if (this.patterns.length == 0)
       return;
 
     let stylesheet = event.target.sheet;
     if (stylesheet)
       this.queueFiltering([stylesheet]);
   },
 
   onShadowAttached(event)
   {
@@ skipping 10 matching lines @@
     this.addShadowRoot(shadowRoot);
   },
 
   addShadowRoot(shadowRoot)
   {
     if (!this.shadowEmulations.has(shadowRoot))
     {
       let emulation = new ElemHideEmulation(this.document,
                                             shadowRoot,
                                             this.addSelectorsFunc,
-                                            this.hideElemsFunc);
+                                            this.hideElemsFunc,
+                                            this.shadowAttachedEventType);
       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 =>
+  findShadowRoots(nodes)
+  {
+    niceLoop(traverse(nodes), node =>
     {
       let shadowRoot = node.shadowRoot;
       if (shadowRoot)
         this.addShadowRoot(shadowRoot);
     });
+  },
+
+  observe(mutations)
+  {
+    if (typeof ShadowRoot != "undefined")
+    {
+      // Find any preattached shadows.
+      this.findShadowRoots(extractAddedSubtrees(mutations));
+    }
 
     this.queueFiltering();
   },
 
   apply(patterns, parsed)
   {
     if (parsed)
     {
       this.patterns = patterns;
     }
@@ skipping 18 matching lines @@
           attributes: true,
           characterData: true,
           subtree: true
         }
       );
     }
   }
 };
 
 exports.ElemHideEmulation = ElemHideEmulation;