Issue 6504, 6458, 6446 - Update selectors based on DOM mutations

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 456 matching lines @@
 function shouldObserveAttributes(patterns)
 {
   return patterns.some(pattern => pattern.maybeDependsOnAttributes);
 }
 
 function shouldObserveCharacterData(patterns)
 {
   return patterns.some(pattern => pattern.dependsOnCharacterData);
 }
 
-function updateSelectorsForMutation(mutation, selectorSet, selectors,
-                                    selectorFilters, root)
-{
-  let {target} = mutation;
-
-  // Existing selectors aren't affected by non-childList mutations.
-  if (mutation.type != "childList" || !root.contains(target))
-    return false;
-
-  // Find the mutation index, i.e. the index in the parent element where the
-  // mutation has occurred.
-  let index = 0;
-  let ref = mutation.previousSibling;
-  if (ref)
-  {
-    if (!(ref instanceof Element))
-      ref = ref.previousElementSibling;
-
+function CSSSelectorManager(root)
+{
+  this._root = root;
+
+  this.selectors = [];
+  this.filters = [];
+
+  this._lookup = new Set();
+
+  this._extended = false;
+}
+
+CSSSelectorManager.prototype = {
+  add(selectors, filters)
+  {
+    for (let i = 0; i < selectors.length; i++)
+    {
+      this.selectors.push(selectors[i]);
+      this.filters.push(filters[i]);
+
+      this._lookup.add(selectors[i]);
+
+      if (!this._extended && selectors[i].startsWith(":root > "))
+        this._extended = true;
+    }
+  },
+
+  has(selector)
+  {
+    return this._lookup.has(selector);
+  },
+
+  setAt(index, selector)
+  {
+    this._lookup.delete(this.selectors[index]);
+    this._lookup.add(selector);
+
+    this.selectors[index] = selector;
+  },
+
+  deleteAt(index)
+  {
+    this._lookup.delete(this.selectors[index]);
+
+    this.selectors.splice(index, 1);
+    this.filters.splice(index, 1);
+  },
+
+  update(mutations)
+  {
+    // If there are no extended CSS selectors (i.e. :-abp-*), there's nothing
+    // to update.
+    if (!this._extended || this.selectors.length == 0)

[Manish Jethani, 2018/03/21 15:35:26]

This is useful. In EasyList the number of sites with emulation filters is 45:

  grep '#?#' easylist.txt | cut -f1 -d'#' | sort -u | tr ',' "\n" | wc -l

While the number of sites with extended CSS selector syntax is only 4:

  grep '#?#.*-abp' easylist.txt | cut -f1 -d'#' | sort -u | tr ',' "\n" | wc -l

If a site doesn't use :-abp-* there won't be any path-based selectors (those
starting with ":root > ") and there's no need to update anything.

Also if there are no selectors, which is true for facebook.com when the page is
loading (but not true afterwards), we can skip all the unnecessary code.

+      return false;
+
+    let changed = false;
+
+    for (let mutation of mutations)
+    {
+      if (this._updateForMutation(mutation))
+        changed = true;
+    }
+
+    return changed;
+  },
+
+  _updateForMutation(mutation)
+  {
+    let {target} = mutation;
+
+    // Existing selectors aren't affected by non-childList mutations.
+    if (mutation.type != "childList" || !this._root.contains(target))
+      return false;
+
+    // Find the mutation index, i.e. the index in the parent element where the
+    // mutation has occurred.
+    let index = 0;
+    let ref = mutation.previousSibling;
     if (ref)
-      index = indexOf(ref.parentNode.children, ref) + 1;
-  }
-
-  // Count the number of elements added and removed. Both can be non-zero in
-  // some cases, e.g. when Element.innerHTML is set on the parent element to
-  // overwrite all the existing child nodes.
-  let numAddedElements = 0;
-  let numRemovedElements = 0;
-
-  for (let node of mutation.addedNodes)
-  {
-    if (node instanceof Element)
-      numAddedElements++;
-  }
-
-  for (let node of mutation.removedNodes)
-  {
-    if (node instanceof Element)
-      numRemovedElements++;
-  }
-
-  let changed = false;
-
-  // Go through all the selectors and find any that match the mutation target.
-  let targetSelector = makeSelector(target) + " > ";
-  for (let i = 0; i < selectors.length; i++)
-  {
-    let selector = selectors[i];
-    if (selector.startsWith(targetSelector))
-    {
-      // If there's a match, extract the one-based child index.
-      let subSelector = selector.substring(targetSelector.length);
-      let match = /^[^:]*:nth-child\((\d+)\)/.exec(subSelector);
-      let nthIndex = match ? +match[1] : 0;
-
-      // If the child being targeted by the selector is before the mutation
-      // index (i.e. the one-based child index is not affected), do nothing.
-      if (nthIndex <= index)
-        continue;
-
-      nthIndex -= numRemovedElements;
-
-      // After adjusting for the number of removed elements, if the one-based
-      // child index appears to be lower than the mutation index, it means the
-      // child got removed. In that case we must delete the selector.
-      if (nthIndex <= index)
-      {
-        selectorSet.delete(selector);
-
-        selectors.splice(i, 1);
-        selectorFilters.splice(i, 1);
-        i--;
-
-        changed = true;
-
-        continue;
+    {
+      if (!(ref instanceof Element))
+        ref = ref.previousElementSibling;
+
+      if (ref)
+        index = positionInParent(ref);
+    }
+
+    // Count the number of elements added and removed. Both can be non-zero in
+    // some cases, e.g. when Element.innerHTML is set on the parent element to
+    // overwrite all the existing child nodes.
+    let numAddedElements = 0;
+    let numRemovedElements = 0;
+
+    for (let node of mutation.addedNodes)
+    {
+      if (node instanceof Element)
+        numAddedElements++;
+    }
+
+    for (let node of mutation.removedNodes)
+    {
+      if (node instanceof Element)
+        numRemovedElements++;
+    }
+
+    let changed = false;
+
+    // Go through all the selectors and find any that match the mutation target.
+    let targetSelector = makeSelector(target) + " > ";
+    for (let i = 0; i < this.selectors.length; i++)
+    {
+      let selector = this.selectors[i];
+      if (selector.startsWith(targetSelector))
+      {
+        // If there's a match, extract the one-based child index.
+        let subSelector = selector.substring(targetSelector.length);
+        let match = /^[^:]*:nth-child\((\d+)\)/.exec(subSelector);
+        let nthIndex = match ? +match[1] : 0;
+
+        // If the child being targeted by the selector is before the mutation
+        // index (i.e. the one-based child index is not affected), do nothing.
+        if (nthIndex <= index)
+          continue;
+
+        nthIndex -= numRemovedElements;
+
+        // After adjusting for the number of removed elements, if the one-based
+        // child index appears to be lower than the mutation index, it means the
+        // child got removed. In that case we must delete the selector.
+        if (nthIndex <= index)
+        {
+          this.deleteAt(i--);
+          changed = true;
+          continue;
+        }
+
+        nthIndex += numAddedElements;
+
+        // If the one-based child index has changed, we must update the
+        // selector.
+        if (nthIndex != +match[1])
+        {
+          this.setAt(i, targetSelector +
+                        subSelector.replace(match[1], nthIndex));
+          changed = true;
+        }
       }
-
-      nthIndex += numAddedElements;
-
-      // If the one-based child index has changed, we must update the selector.
-      if (nthIndex != +match[1])
-      {
-        selectorSet.delete(selector);
-        selector = targetSelector + subSelector.replace(match[1], nthIndex);
-        selectorSet.add(selector);
-        selectors[i] = selector;
-
-        changed = true;
-      }
-    }
-  }
-
-  return changed;
-}
+    }
+
+    return changed;
+  }
+};
 
 function ElemHideEmulation(addSelectorsFunc, hideElemsFunc)
 {
   this.document = document;
   this.addSelectorsFunc = addSelectorsFunc;
   this.hideElemsFunc = hideElemsFunc;
   this.observer = new MutationObserver(this.observe.bind(this));
   this.useInlineStyles = true;
-  this.selectorSet = new Set();
-  this.selectors = [];
-  this.selectorFilters = [];
+  this.css = new CSSSelectorManager(this.document);
 }
 
 ElemHideEmulation.prototype = {
   isSameOrigin(stylesheet)
   {
     try
     {
       return new URL(stylesheet.href).origin == this.document.location.origin;
     }
     catch (e)
@@ skipping 136 matching lines @@
     let processPatterns = () =>
     {
       let cycleStart = performance.now();
 
       if (!pattern)
       {
         if (!patterns.length)
         {
           if (selectors.length > 0)
           {
-            for (let selector of selectors)
-              this.selectorSet.add(selector);
-
-            this.selectors.push(...selectors);
-            this.selectorFilters.push(...selectorFilters);
-
-            this.addSelectorsFunc(this.selectors,
-                                  this.selectorFilters);
+            this.css.add(selectors, selectorFilters);
+            this.addSelectorsFunc(this.css.selectors, this.css.filters);
           }
 
           if (elements.length > 0)
             this.hideElemsFunc(elements, elementFilters);
 
           if (typeof done == "function")
             done();
           return;
         }
 
         pattern = patterns.shift();
 
         generator = evaluate(pattern.selectors, 0, "",
                              this.document, cssStyles);
       }
       for (let selector of generator)
       {
         if (selector != null)
         {
           if (!this.useInlineStyles ||
               pattern.isSelectorHidingOnlyPattern())
           {
-            if (!this.selectorSet.has(selector))
+            if (!this.css.has(selector))
             {
               selectors.push(selector);
               selectorFilters.push(pattern.text);
             }
           }
           else
           {
             for (let element of this.document.querySelectorAll(selector))
             {
               elements.push(element);
@@ skipping 113 matching lines @@
 
   onLoad(event)
   {
     let stylesheet = event.target.sheet;
     if (stylesheet)
       this.queueFiltering([stylesheet]);
   },
 
   observe(mutations)
   {
-    let selectorsChanged = false;
-    for (let mutation of mutations)
-    {
-      if (updateSelectorsForMutation(mutation, this.selectorSet, this.selectors,
-                                     this.selectorFilters, this.document))
-      {
-        selectorsChanged = true;
-      }
-    }
-
-    if (selectorsChanged)
-      this.addSelectorsFunc(this.selectors, this.selectorFilters);
+    if (this.css.update(mutations))
+      this.addSelectorsFunc(this.css.selectors, this.css.filters);

[hub, 2018/03/23 15:54:25]

My concern here is that the intent of queueFiltering was to have 
addSelectorsFunc() run asynchronously. This here throw it off a bit.

[Manish Jethani, 2018/03/23 16:55:33]

The thing is that I'm trying to avoid running full filtering on every DOM
mutation, but at the same time we have to keep the selectors up to date
(otherwise they hide the wrong elements, i.e. false positives and false
negatives). I thought about making this asynchronous, but I wonder if it's
necessary. MutationObserver events are already asynchronous (multiple mutations
are batched together). But I'll see if I can throw in a bit of asynchronicity
here.

 
     this.queueFiltering(null, mutations);
   },
 
   apply(patterns)
   {
     this.patterns = [];
     for (let pattern of patterns)
     {
       let selectors = this.parseSelector(pattern.selector);
@@ skipping 12 matching lines @@
           characterData: shouldObserveCharacterData(this.patterns),
           subtree: true
         }
       );
       this.document.addEventListener("load", this.onLoad.bind(this), true);
     }
   }
 };
 
 exports.ElemHideEmulation = ElemHideEmulation;