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();
+}
+
+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]);
+    }
+  },
+
+  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)
+  {
+    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);
+
     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;