Issue 3143 - Filter elements with :-abp-has()

chrome/content/elemHideEmulation.js

-// We are currently limited to ECMAScript 5 in this file, because it is being
-// used in the browser tests. See https://issues.adblockplus.org/ticket/4796
-
-var propertySelectorRegExp = /\[\-abp\-properties=(["'])([^"']+)\1\]/;
-var pseudoClassHasSelectorRegExp = /:has\((.*)\)/;
+/*
+ * This file is part of Adblock Plus <https://adblockplus.org/>,
+ * Copyright (C) 2006-2017 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
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/* globals filterToRegExp */
+
+"use strict";
+
+const abpSelectorRegexp = /:-abp-([\w-]+)\(/i;
+
+let reportError = () => {};
 
 function splitSelector(selector)
 {
   if (selector.indexOf(",") == -1)
     return [selector];
 
-  var selectors = [];
-  var start = 0;
-  var level = 0;
-  var sep = "";
-
-  for (var i = 0; i < selector.length; i++)
-  {
-    var chr = selector[i];
+  let selectors = [];
+  let start = 0;
+  let level = 0;
+  let sep = "";
+
+  for (let i = 0; i < selector.length; i++)
+  {
+    let chr = selector[i];
 
     if (chr == "\\")        // ignore escaped characters
       i++;
     else if (chr == sep)    // don't split within quoted text
       sep = "";             // e.g. [attr=","]
     else if (sep == "")
     {
       if (chr == '"' || chr == "'")
         sep = chr;
       else if (chr == "(")  // don't split between parentheses
         level++;            // e.g. :matches(div,span)
       else if (chr == ")")
         level = Math.max(0, level - 1);
       else if (chr == "," && level == 0)
       {
         selectors.push(selector.substring(start, i));
         start = i + 1;
       }
     }
   }
 
   selectors.push(selector.substring(start));
   return selectors;
 }
 
-const ABP_ATTR = "abp-0ac791f0-a03b-4f2c-a935-a285bc2e668e";
-const ABP_ATTR_SEL = "[" + ABP_ATTR + "] ";
-
-function matchChildren(e, selector)
-{
-  var subElement;
-  var newSelector = ABP_ATTR_SEL + selector;
-  var parentNode = e.parentNode || document;
-
-  e.setAttribute(ABP_ATTR, "");
-  subElement = parentNode.querySelector(newSelector);
-  e.removeAttribute(ABP_ATTR);
-
-  return subElement != null;
-}
-
-function selectChildren(e, selector)
-{
-  var subElements;
-  var newSelector = ABP_ATTR_SEL + selector;
-  var parentNode = e.parentNode || document;
-
-  e.setAttribute(ABP_ATTR, "");
-  subElements = parentNode.querySelectorAll(newSelector);
-  e.removeAttribute(ABP_ATTR);
-
-  return subElements;
-}
-
-function parsePattern(pattern)
-{
-  // we should catch the :has() pseudo class first.
-  var match = pseudoClassHasSelectorRegExp.exec(pattern.selector);
-  if (match)
-  {
-    return {
-      type: "has",
-      text: pattern.text,
-      elementMatcher: new PseudoHasMatcher(match[1]),
-      prefix: pattern.selector.substr(0, match.index).trim(),
-      suffix: pattern.selector.substr(match.index + match[0].length).trim()
-    };
-  }
-
-  match = propertySelectorRegExp.exec(pattern.selector);
-  if (match)
-  {
-    var regexpString;
-    var propertyExpression = match[2];
-    if (propertyExpression.length >= 2 && propertyExpression[0] == "/" &&
-        propertyExpression[propertyExpression.length - 1] == "/")
-      regexpString = propertyExpression.slice(1, -1)
+/** Return position of node from parent.
+ * @param {Node} node the node to find the position of.
+ * @return {number} One-based index like for :nth-child(), or 0 on error.
+ */
+function positionInParent(node)
+{
+  let {children} = node.parentNode;
+  for (let i = 0; i < children.length; i++)
+    if (children[i] == node)
+      return i + 1;
+  return 0;
+}
+
+function makeSelector(node, selector)
+{
+  if (!node.parentElement)
+  {
+    let newSelector = ":root";
+    if (selector)
+      newSelector += " > " + selector;
+    return newSelector;
+  }
+  let idx = positionInParent(node);
+  if (idx > 0)
+  {
+    let newSelector = `${node.tagName}:nth-child(${idx})`;
+    if (selector)
+      newSelector += " > " + selector;
+    return makeSelector(node.parentElement, newSelector);
+  }
+
+  return selector;
+}
+
+function parseSelectorContent(content, startIndex)
+{
+  let parens = 1;
+  let quote = null;
+  let i = startIndex;
+  for (; i < content.length; i++)
+  {
+    let c = content[i];
+    if (c == "\\")
+    {
+      // Ignore escaped characters
+      i++;
+    }
+    else if (quote)
+    {
+      if (c == quote)
+        quote = null;
+    }
+    else if (c == "'" || c == '"')
+      quote = c;
+    else if (c == "(")
+      parens++;
+    else if (c == ")")
+    {
+      parens--;
+      if (parens == 0)
+        break;
+    }
+  }
+
+  if (parens > 0)
+    return null;
+  return {text: content.substring(startIndex, i), end: i};
+}
+
+/** Parse the selector
+ * @param {string} selector the selector to parse
+ * @return {Object} selectors is an array of objects,
+ * or null in case of errors. hide is true if we'll hide
+ * elements instead of styles..
+ */
+function parseSelector(selector)
+{
+  if (selector.length == 0)
+    return [];
+
+  let match = abpSelectorRegexp.exec(selector);
+  if (!match)
+    return [new PlainSelector(selector)];
+
+  let selectors = [];
+  if (match.index > 0)
+    selectors.push(new PlainSelector(selector.substr(0, match.index)));
+
+  let startIndex = match.index + match[0].length;
+  let content = parseSelectorContent(selector, startIndex);
+  if (!content)
+  {
+    reportError(new SyntaxError("Failed to parse Adblock Plus " +
+                                `selector ${selector}, ` +
+                                "due to unmatched parentheses."));
+    return null;
+  }
+  if (match[1] == "properties")
+    selectors.push(new PropsSelector(content.text));
+  else if (match[1] == "has")
+  {
+    let hasSelector = new HasSelector(content.text);
+    if (!hasSelector.valid())
+      return null;
+    selectors.push(hasSelector);
+  }
+  else
+  {
+    // this is an error, can't parse selector.
+    reportError(new SyntaxError("Failed to parse Adblock Plus " +
+                                `selector ${selector}, invalid ` +
+                                `pseudo-class :-abp-${match[1]}().`));
+    return null;
+  }
+
+  let suffix = parseSelector(selector.substr(content.end + 1));
+  if (suffix == null)
+    return null;
+
+  selectors.push(...suffix);
+
+  return selectors;
+}
+
+/** Stringified style objects
+ * @typedef {Object} StringifiedStyle
+ * @property {string} style CSS style represented by a string.
+ * @property {string[]} subSelectors selectors the CSS properties apply to.
+ */
+
+/**
+ * Produce a string representation of the stylesheet entry.
+ * @param {CSSStyleRule} rule the CSS style rule.
+ * @return {StringifiedStyle} the stringified style.
+ */
+function stringifyStyle(rule)
+{
+  let styles = [];
+  for (let i = 0; i < rule.style.length; i++)
+  {
+    let property = rule.style.item(i);
+    let value = rule.style.getPropertyValue(property);
+    let priority = rule.style.getPropertyPriority(property);
+    styles.push(`${property}: ${value}${priority ? " !" + priority : ""};`);
+  }
+  styles.sort();
+  return {
+    style: styles.join(" "),
+    subSelectors: splitSelector(rule.selectorText)
+  };
+}
+
+function* evaluate(chain, index, prefix, subtree, styles)
+{
+  if (index >= chain.length)
+  {
+    yield prefix;
+    return;
+  }
+  for (let [selector, element] of
+       chain[index].getSelectors(prefix, subtree, styles))
+    yield* evaluate(chain, index + 1, selector, element, styles);
+}
+
+function PlainSelector(selector)
+{
+  this._selector = selector;
+}
+
+PlainSelector.prototype = {
+  /**
+   * Generator function returning a pair of selector
+   * string and subtree.
+   * @param {string} prefix the prefix for the selector.
+   * @param {Node} subtree the subtree we work on.
+   * @param {StringifiedStyle[]} styles the stringified style objects.
+   */
+  *getSelectors(prefix, subtree, styles)
+  {
+    yield [prefix + this._selector, subtree];
+  }
+};
+
+const incompletePrefixRegexp = /[\s>+~]$/;
+
+function HasSelector(selector)
+{
+  this._innerSelectors = parseSelector(selector);
+}
+
+HasSelector.prototype = {
+  requiresHiding: true,
+
+  valid()
+  {
+    return this._innerSelectors != null;
+  },
+
+  *getSelectors(prefix, subtree, styles)
+  {
+    for (let element of this.getElements(prefix, subtree, styles))
+      yield [makeSelector(element, ""), element];
+  },
+
+  /**
+   * Generator function returning selected elements.
+   * @param {string} prefix the prefix for the selector.
+   * @param {Node} subtree the subtree we work on.
+   * @param {StringifiedStyle[]} styles the stringified style objects.
+   */
+  *getElements(prefix, subtree, styles)
+  {
+    let actualPrefix = (!prefix || incompletePrefixRegexp.test(prefix)) ?
+        prefix + "*" : prefix;
+    let elements = subtree.querySelectorAll(actualPrefix);
+    for (let element of elements)
+    {
+      let newPrefix = makeSelector(element, "");
+      let iter = evaluate(this._innerSelectors, 0, newPrefix + " ",
+                          element, styles);
+      for (let selector of iter)
+        // we insert a space between the two. It becomes a no-op if selector
+        // doesn't have a combinator
+        if (subtree.querySelector(selector))
+          yield element;
+    }
+  }
+};
+
+function PropsSelector(propertyExpression)
+{
+  let regexpString;
+  if (propertyExpression.length >= 2 && propertyExpression[0] == "/" &&
+      propertyExpression[propertyExpression.length - 1] == "/")
+  {
+    regexpString = propertyExpression.slice(1, -1)
       .replace("\\x7B ", "{").replace("\\x7D ", "}");
-    else
-      regexpString = filterToRegExp(propertyExpression);
-    return {
-      type: "props",
-      text: pattern.text,
-      regexp: new RegExp(regexpString, "i"),
-      prefix: pattern.selector.substr(0, match.index),
-      suffix: pattern.selector.substr(match.index + match[0].length)
-    };
-  }
-}
-
-function matchStyleProps(style, rule, pattern, selectors, filters)
-{
-  if (pattern.regexp.test(style))
-  {
-    var subSelectors = splitSelector(rule.selectorText);
-    for (var i = 0; i < subSelectors.length; i++)
-    {
-      var subSelector = subSelectors[i];
-      selectors.push(pattern.prefix + subSelector + pattern.suffix);
-      filters.push(pattern.text);
-    }
-  }
-}
-
-function findPropsSelectors(stylesheet, patterns, selectors, filters)
-{
-  var rules = stylesheet.cssRules;
-  if (!rules)
-    return;
-
-  for (var i = 0; i < rules.length; i++)
-  {
-    var rule = rules[i];
-    if (rule.type != rule.STYLE_RULE)
-      continue;
-
-    var style = stringifyStyle(rule.style);
-    for (var j = 0; j < patterns.length; j++)
-    {
-      matchStyleProps(style, rule, patterns[j], selectors, filters);
-    }
-  }
-}
-
-/**
- * Match the selector @pattern containing :has() starting from @node.
- */
-function pseudoClassHasMatch(pattern, node, stylesheets, elements, filters)
-{
-  // select element for the prefix pattern. Or just use node.
-  var haveEl = pattern.prefix ? node.querySelectorAll(pattern.prefix) : [ node ];
-  for (var j = 0; j < haveEl.length; j++)
-  {
-    var matched = pattern.elementMatcher.match(haveEl[j], stylesheets);
-    if (!matched)
-      continue;
-
-    if (pattern.suffix)
-    {
-      var subElements = selectChildren(haveEl[j], pattern.suffix);
-      if (subElements)
-      {
-        for (var k = 0; k < subElements.length; k++)
-        {
-          elements.push(subElements[k]);
-          filters.push(pattern.text);
-        }
-      }
-    }
-    else
-    {
-      elements.push(haveEl[j]);
-      filters.push(pattern.text);
-    }
-  }
-}
-
-function stringifyStyle(style)
-{
-  var styles = [];
-  for (var i = 0; i < style.length; i++)
-  {
-    var property = style.item(i);
-    var value    = style.getPropertyValue(property);
-    var priority = style.getPropertyPriority(property);
-    styles.push(property + ": " + value + (priority ? " !" + priority : "") + ";");
-  }
-  styles.sort();
-  return styles.join(" ");
-}
-
-// matcher for the pseudo CSS4 class :has
-// For those browser that don't have it yet.
-function PseudoHasMatcher(selector)
-{
-  this.hasSelector = selector;
-  this.parsed = parsePattern({ selector: this.hasSelector });
-}
-
-PseudoHasMatcher.prototype = {
-  match: function(elem, stylesheets)
-  {
-    var selectors = [];
-
-    if (this.parsed)
-    {
-      var filters = []; // don't need this, we have a partial filter.
-      if (this.parsed.type == "has")
-      {
-        var child = elem.firstChild;
-        while (child)
-        {
-          if (child.nodeType === Node.ELEMENT_NODE)
-          {
-            var matches = [];
-            pseudoClassHasMatch(this.parsed, child, stylesheets, matches, filters)
-            if (matches.length > 0)
-              return true;
-          }
-          child = child.nextSibling;
-        }
-        return false;
-      }
-      if (this.parsed.type == "props")
-      {
-        for (var i = 0; i  < stylesheets.length; i++)
-          findPropsSelectors(stylesheets[i], [this.parsed], selectors, filters);
-      }
-    }
-    else
-    {
-      selectors = [this.hasSelector];
-    }
-
-    var matched = false;
-    // look up for all elements that match the :has().
-    for (var k = 0; k < selectors.length; k++)
-    {
-      try
-      {
-        matched = matchChildren(elem, selectors[k]);
-        if (matched)
-          break;
-      }
-      catch(e)
-      {
-        console.error("Exception with querySelector()", selectors[k], e);
-      }
-    }
-    return matched;
+  }
+  else
+    regexpString = filterToRegExp(propertyExpression);
+
+  this._regexp = new RegExp(regexpString, "i");
+}
+
+PropsSelector.prototype = {
+  *findPropsSelectors(styles, prefix, regexp)
+  {
+    for (let style of styles)
+      if (regexp.test(style.style))
+        for (let subSelector of style.subSelectors)
+          yield prefix + subSelector;
+  },
+
+  *getSelectors(prefix, subtree, styles)
+  {
+    for (let selector of this.findPropsSelectors(styles, prefix, this._regexp))
+      yield [selector, subtree];
   }
 };
 
-function ElemHideEmulation(window, getFiltersFunc, addSelectorsFunc, hideElementsFunc)
+function ElemHideEmulation(window, getFiltersFunc, addSelectorsFunc,
+                           hideElemsFunc)
 {
   this.window = window;
   this.getFiltersFunc = getFiltersFunc;
   this.addSelectorsFunc = addSelectorsFunc;
-  this.hideElementsFunc = hideElementsFunc;
+  this.hideElemsFunc = hideElemsFunc;
 }
 
 ElemHideEmulation.prototype = {
-
-  isSameOrigin: function(stylesheet)
+  isSameOrigin(stylesheet)
   {
     try
     {
       return new URL(stylesheet.href).origin == this.window.location.origin;
     }
     catch (e)
     {
       // Invalid URL, assume that it is first-party.
       return true;
     }
   },
 
-  findPseudoClassHasElements: function(node, stylesheets, elements, filters)
-  {
-    for (var i = 0; i < this.pseudoHasPatterns.length; i++)
-    {
-      pseudoClassHasMatch(this.pseudoHasPatterns[i], node, stylesheets, elements, filters);
-    }
-  },
-
-  addSelectors: function(stylesheets)
-  {
-    var selectors = [];
-    var filters = [];
-    for (var i = 0; i < stylesheets.length; i++)
+  addSelectors(stylesheets)
+  {
+    let selectors = [];
+    let selectorFilters = [];
+
+    let elements = [];
+    let elementFilters = [];
+
+    let cssStyles = [];
+
+    for (let stylesheet of stylesheets)
     {
       // Explicitly ignore third-party stylesheets to ensure consistent behavior
       // between Firefox and Chrome.
-      if (!this.isSameOrigin(stylesheets[i]))
+      if (!this.isSameOrigin(stylesheet))
         continue;
-      findPropsSelectors(stylesheets[i], this.propSelPatterns, selectors, filters);
-    }
-    this.addSelectorsFunc(selectors, filters);
-  },
-
-  hideElements: function(stylesheets)
-  {
-    var elements = [];
-    var filters = [];
-    this.findPseudoClassHasElements(document, stylesheets, elements, filters);
-    this.hideElementsFunc(elements, filters);
-  },
-
-  onLoad: function(event)
-  {
-    var stylesheet = event.target.sheet;
+
+      let rules = stylesheet.cssRules;
+      if (!rules)
+        continue;
+
+      for (let rule of rules)
+      {
+        if (rule.type != rule.STYLE_RULE)
+          continue;
+
+        cssStyles.push(stringifyStyle(rule));
+      }
+    }
+
+    let {document} = this.window;
+    for (let pattern of this.patterns)
+    {
+      for (let selector of evaluate(pattern.selectors,
+                                    0, "", document, cssStyles))
+      {
+        if (!pattern.selectors.some(s => s.requiresHiding))
+        {
+          selectors.push(selector);
+          selectorFilters.push(pattern.text);
+        }
+        else
+        {
+          for (let element of document.querySelectorAll(selector))
+          {
+            elements.push(element);
+            elementFilters.push(pattern.text);
+          }
+        }
+      }
+    }
+
+    this.addSelectorsFunc(selectors, selectorFilters);
+    this.hideElemsFunc(elements, elementFilters);
+  },
+
+  onLoad(event)
+  {
+    let stylesheet = event.target.sheet;
     if (stylesheet)
       this.addSelectors([stylesheet]);
-    this.hideElements([stylesheet]);
-  },
-
-  apply: function()
-  {
-    this.getFiltersFunc(function(patterns)
-    {
-      this.propSelPatterns = [];
-      this.pseudoHasPatterns = [];
-      for (var i = 0; i < patterns.length; i++)
+  },
+
+  apply()
+  {
+    this.getFiltersFunc(patterns =>
+    {
+      let oldReportError = reportError;
+      reportError = error => this.window.console.error(error);
+
+      this.patterns = [];
+      for (let pattern of patterns)
       {
-        var pattern = patterns[i];
-        var parsed = parsePattern(pattern);
-        if (parsed == undefined)
-          continue;
-        if (parsed.type == "props")
-        {
-          this.propSelPatterns.push(parsed);
-        }
-        else if (parsed.type == "has")
-        {
-          this.pseudoHasPatterns.push(parsed);
-        }
+        let selectors = parseSelector(pattern.selector);
+        if (selectors != null && selectors.length > 0)
+          this.patterns.push({selectors, text: pattern.text});
       }
 
-      if (this.pseudoHasPatterns.length > 0 || this.propSelPatterns.length > 0)
+      if (this.patterns.length > 0)
       {
-        var document = this.window.document;
+        let {document} = this.window;
         this.addSelectors(document.styleSheets);
-        this.hideElements(document.styleSheets);
         document.addEventListener("load", this.onLoad.bind(this), true);
       }
-    }.bind(this));
+      reportError = oldReportError;
+    });
   }
 };