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 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)
+    {
+      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;
+        }
+      }
+    }
+
+    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.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)
+      return;
+
     let selectors = [];
     let selectorFilters = [];
 
     let elements = [];
     let elementFilters = [];
 
     let cssStyles = [];
 
     // If neither any style sheets nor any DOM mutations have been specified,
     // do full processing.
@@ skipping 34 matching lines @@
 
     let processPatterns = () =>
     {
       let cycleStart = performance.now();
 
       if (!pattern)
       {
         if (!patterns.length)
         {
           if (selectors.length > 0)
-            this.addSelectorsFunc(selectors, 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())
           {
-            selectors.push(selector);
-            selectorFilters.push(pattern.text);
+            if (!this.css.has(selector))
+            {
+              selectors.push(selector);
+              selectorFilters.push(pattern.text);
+            }
           }
           else
           {
             for (let element of this.document.querySelectorAll(selector))
             {
               elements.push(element);
               elementFilters.push(pattern.text);
             }
           }
         }
@@ skipping 109 matching lines @@
 
   onLoad(event)
   {
     let stylesheet = event.target.sheet;
     if (stylesheet)
       this.queueFiltering([stylesheet]);
   },
 
   observe(mutations)
   {
+    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);
       if (selectors != null && selectors.length > 0)
@@ skipping 11 matching lines @@
           characterData: shouldObserveCharacterData(this.patterns),
           subtree: true
         }
       );
       this.document.addEventListener("load", this.onLoad.bind(this), true);
     }
   }
 };
 
 exports.ElemHideEmulation = ElemHideEmulation;