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

[hub, 2017/10/20 15:37:57]

In Firefox Nightly 

`document.querySelector("div") instanceof ShadowRoot` cause an exception
"ReferenceError" because ShadowRoot is not defined.

In Chrome it returns `false` which is expected (or `true` if it really is)

[Manish Jethani, 2017/10/20 16:16:41]

Done.

     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 extractSubtrees(nodes)
+{
+  return nodes.filter(
+    (node, index) => !nodes.some(
+      // The index comparison is based on the fact that a node always appears
+      // in the list before any of its descendants.
+      (otherNode, otherIndex) => otherIndex < index && otherNode.contains(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
    * 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,
+                           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);
+  else
+    this.findShadowRoots(this.root.children);
 }
 
 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)
   {
+    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();
+
+    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.shadowAttachedEventType);
+      this.shadowEmulations.set(shadowRoot, emulation);
+      emulation.apply(this.patterns, true);
+    }
+  },
+
+  findShadowRoots(nodes)
+  {
+    niceLoop(traverse(nodes), node =>
+    {
+      let shadowRoot = node.shadowRoot;
+      if (shadowRoot)
+        this.addShadowRoot(shadowRoot);
+    });
+  },
+
   observe(mutations)
   {
+    let allAddedElements = [];
+    for (let mutation of mutations)
+    {
+      for (let node of mutation.addedNodes)
+      {
+        if (node instanceof Element)

[lainverse, 2017/10/20 15:37:07]

Actually if nodes are always added in parent -> child order then why not check
does last node in the list contains current one?

Something like:
node instanceof Element && !elements.some(other => other.contains(node))

Then extractSubtrees won't be needed at all.

[Manish Jethani, 2017/10/20 16:16:41]

That's a very good point!

While it is better in theory, I tried it out and it seems to run slightly slower
for whatever reason. Maybe it's because extractSubtrees is a pure function and
it always runs on the same unmodified array object in both the outer and inner
loops.

I've left it as it is for now.

[lainverse, 2017/10/20 17:37:36]

Most likely that's because arrow function were defined within a loop. It may
create a new instance every time it runs. Try to move it out of the loop.

let elements = [];
let isRoot = node => node instanceof Element && !elements.some(other =>
other.contains(node));
// as I understand 'let node' within a loop creates new one each time
let mutation, node;
for (mutation of mutations)
    for (node of mutation.addedNodes)
        if (isRoot(node))
            elements.push(node);

[Manish Jethani, 2017/10/22 20:01:34]

Simply moving the array function out of the loop did not help. But I tried
moving it out entirely to make it a pure function with no reference to the
surrounding scope, and that helped. Then I moved the entire loop out into its
own pure function, that helped more. Finally I thought why not make it a
generator, that way it can participate in niceLoop's niceness.

Done.

+          allAddedElements.push(node);
+      }
+    }
+
+    // Find any preattached shadows.
+    this.findShadowRoots(extractSubtrees(allAddedElements));
+
     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;