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)
-{
-  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;

[Sebastian Noack, 2017/10/19 00:43:08]

Why don't you just keep track of redundant nodes in the first place? Or just
remove them right away (using a for(;;) loop, updating the loop index), here?

[Manish Jethani, 2017/10/19 02:13:44]

You mean "node.redundant = true" rather than "nodeInfo.redundant = true"? I did
not want to modify an object passed in by the browser.
As I've tried to explain in the comment, we could just delete the node right
away from the Set object instead of setting the redundant property first and
then later filtering it out, but then we'd have to walk up the tree for each
node. When a node's parent is redundant, the node is redundant too. This is an
important optimization given the kind of data we're going to get here.

Take this:

  <div id="a">
    <div id="b">
      <div id="c">
      </div>
    </div>
  </div>

Now suppose this was built incrementally. We'll get all three nodes. If we
remove "b" right away, when we're looking at "c" we'll have to go all the way up
to "a" to find out that "c" is redundant. By keeping "b" but simply marking it
as redundant, we only climb one level until we know that "c" is redundant. This
saves a lot of iterations. It cut execution time in half for the TechCrunch home
page where I was testing it.

[Manish Jethani, 2017/10/19 02:19:06]

By setting a redundant flag we don't just avoid walking all the way up to the
root, we also avoid doing lookups in the Set object.

[Sebastian Noack, 2017/10/19 03:51:01]

How about using a Set() object containing only redundant nodes, instead an array
of objects holding each node and the information whether they are redundant?

[Manish Jethani, 2017/10/19 09:57:14]

How do you do lookups efficiently in an array?

Perhaps I'm misunderstanding, could you explain?

[Sebastian Noack, 2017/10/19 18:35:39]

I was basically talking about what lainverse is suggesting above. Perhaps, a Set
isn't even necessary.

[Manish Jethani, 2017/10/19 23:14:58]

OK, I did not realize Node.contains was so efficient.

Done.

-        break;
+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;
       }
     }
   }
-
-  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);
     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);

[Sebastian Noack, 2017/10/19 00:43:08]

Don't you have to terminate the loop here?

[Manish Jethani, 2017/10/19 02:13:44]

Right, I forgot to terminate it.

Done.

+        return;
+      }
     }
   };
 
   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 = [];
   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",

[Sebastian Noack, 2017/10/19 00:43:08]

So I assume you still intend to patch attachShadow() in order to dispatch this
event? If we don't have any better idea, we should at least randomize the event
name, so that web pages cannot listen to it.

[Manish Jethani, 2017/10/19 02:13:44]

Ack.

Web pages won't get the event because we're calling
Event.stopImmediatePropagation, and we're the first to get the message.

But it could happen that web pages message with us by dispatching the event.
I'll try to come up with something, probably a randomized event name.

-                                   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;