Issue 5650 - Apply emulation filters to shadow DOMs

lib/content/elemHideEmulation.js

Index: lib/content/elemHideEmulation.js
===================================================================
--- a/lib/content/elemHideEmulation.js
+++ b/lib/content/elemHideEmulation.js
@@ -35,30 +35,33 @@
       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;
@@ -138,16 +141,77 @@
       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
@@ -297,22 +361,32 @@
 };
 
 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;
@@ -404,17 +478,17 @@
 
     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;
 
@@ -454,30 +528,30 @@
 
         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)
         {
@@ -555,46 +629,101 @@
     {
       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)
+    {
+      this.patterns = patterns;
+    }
+    else
     {
-      let selectors = this.parseSelector(pattern.selector);
-      if (selectors != null && selectors.length > 0)
-        this.patterns.push({selectors, text: pattern.text});
+      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;