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;
+
+    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;
+      }
+
+      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;
+}
+
 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 = [];
 }
 
 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 = [];
 
     // 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);
+          {
+            for (let selector of selectors)
+              this.selectorSet.add(selector);
+
+            this.selectors.push(...selectors);
+            this.selectorFilters.push(...selectorFilters);
+
+            this.addSelectorsFunc(this.selectors,
+                                  this.selectorFilters);
+          }
+
           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.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.

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