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 78 matching lines @@
   {
     if (selector == null)
       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 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)
+  {
+    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;
+      }
+    }
+  };
+
+  loop();
 }
 
 function PlainSelector(selector)
 {
   this._selector = selector;
 }
 
 PlainSelector.prototype = {
   /**
    * Generator function returning a pair of selector
@@ skipping 141 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)

[Manish Jethani, 2017/09/30 12:29:01]

It's best to pass these in the constructor as we need them early.

+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 = [];
   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)

[Manish Jethani, 2017/09/30 12:29:01]

We have to listen for these events as early as possible, before any of the
site's code has had a chance to run. If not, the author code can simply add a
listener and call Event.stopPropagation on the event object. We're even
listening in capture mode so we get the event first, no matter what.

-  {
     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)
   {
     event.stopImmediatePropagation();

[Manish Jethani, 2017/09/30 12:29:01]

Prevent any author code from detecting even the presence of this event.

[lainverse, 2017/10/02 14:11:55]

What will stop page from sending own events with the same name and custom (and
potentially malicious) event.target?

Why do we even use event with predictable name in the firs place?

[Manish Jethani, 2017/10/02 14:28:11]

That's a good point, but the event would have to be dispatched off a DOM node
for it to be caught by us, and the node would have to have a shadowRoot
property. If it does, we only do something if we haven't already seen the same
shadow root.
We could namespace it, like "org.adblockplus::shadowAttached", so that there is
no unintentional conflict with the author's code, but I don't see why anyone
would deliberately degrade their site's performance when it has no actual effect
(the event would be a no-op if the target doesn't have a shadow root or if we've
already seen the shadow root).

But we could just add a random component to the name, I suppose, just to be
safe.

[lainverse, 2017/10/02 16:05:39]

What about a proper DOM element with Proxy with getter in place of shadowRoot
property? Even if event name would be random I'd recommend to use actual
shadowRoot getter instead of event.target.shadowRoot since any attempt to access
anything within it will trigger code in that getter. As I udnerstand event's
code might be postponed a bit and site may redefine shadowRoot with proxy or
just null.

[Manish Jethani, 2017/10/02 16:12:31]

A content script has its own copy of these APIs, a site cannot override these.
When we access event.target.shadowRoot, for example, our own wrapper for
Element.shadowRoot in the page does not get called, because that is a different
context.

 
     if (this.patterns.length == 0)
       return;
 
-    // The shadow root won't be available if it's a closed shadow root. Even
-    // though we override Element.attachShadow to create an open shadow root,
-    // it is possible that some other extension has overridden it before us to
-    // create a closed shadow root.
+    // 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.hideElemsFunc,
+                                            this.shadowAttachedEventType);
       this.shadowEmulations.set(shadowRoot, emulation);
       emulation.apply(this.patterns, true);
     }
   },
 
-  findShadowRoots(node)
-  {
-    let shadowRoot = node.shadowRoot;
-    if (shadowRoot)
-      this.addShadowRoot(shadowRoot);
-
-    for (let child of node.children)
-      this.findShadowRoots(child);
+  findShadowRoots(nodes)
+  {
+    niceLoop(traverse(nodes), node =>
+    {
+      let shadowRoot = node.shadowRoot;
+      if (shadowRoot)
+        this.addShadowRoot(shadowRoot);
+    });
   },
 
   observe(mutations)
   {
-    for (let mutation of mutations)
+    if (typeof ShadowRoot != "undefined")
     {
       // Find any preattached shadows.
-      for (let node of mutation.addedNodes)
-        this.findShadowRoots(node);
+      this.findShadowRoots(extractAddedSubtrees(mutations));
     }
 
     this.queueFiltering();
   },
 
   apply(patterns, parsed)
   {
     if (parsed)
     {
       this.patterns = patterns;
@@ skipping 19 matching lines @@
           attributes: true,
           characterData: true,
           subtree: true
         }
       );
     }
   }
 };
 
 exports.ElemHideEmulation = ElemHideEmulation;