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,

[Manish Jethani, 2018/03/21 04:45:44]

Hopefully the inline comments are helpful.

-                                    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 targetted 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();

[Manish Jethani, 2018/03/21 04:45:44]

selectorSet here is mainly for faster lookups and such.

selectors and selectorFilters exist because the content script doesn't support
append-only and delete-only modes. Ideally addSelectorsFunc would only add new
selectors, and there would be a corresponding removeSelectorsFunc that would
remove existing selectors. Then we could call them only when there are changes
to be made.

-  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 78 matching lines @@
    *    made reprocessing necessary. This parameter shouldn't be passed in for
    *    the initial processing, the entire document will be considered
    *    then and all rules, including the ones not dependent on the DOM.
    * @param {function} [done]
    *    Callback to call when done.
    */
   _addSelectors(stylesheets, mutations, done)
   {
     let patterns = filterPatterns(this.patterns, {stylesheets, mutations});
 
     if (patterns.length == 0)

[Manish Jethani, 2018/03/21 04:45:44]

Minor optimization, definitely don't need to proceed if there are no patterns to
process.

       return;
 
     let selectors = [];
     let selectorFilters = [];
 
     let elements = [];
     let elementFilters = [];
 
     let cssStyles = [];
 
@@ skipping 37 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))

[Manish Jethani, 2018/03/21 04:45:44]

The reason we need this Set object is that we don't want to add the same
selector twice, which would happen if we're traversing the DOM in response to a
mutation and finding the same selectors again. We cannot prevent that in all
cases, but we can avoid duplicating selectors.

+            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)

[Manish Jethani, 2018/03/21 04:45:44]

Call addSelectorsFunc immediately so the UI is updated ASAP, otherwise elements
have moved so the existing selectors that exist in the document may end up
targeting the wrong elements, at least until the new selectors are found via DOM
traversal.

That's one reason for this change, the other reason is that we want to keep
trying to avoid DOM traversal wherever possible, so we shouldn't have to do it
just to update the selectors.

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