Issue 6994 - Use shortcut matching for location only filters

lib/filterClasses.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
  * 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/>.
  */
 
 "use strict";
 
 /**
  * @fileOverview Definition of Filter class and its subclasses.
  */
 
 const {filterNotifier} = require("./filterNotifier");
 const {extend} = require("./coreUtils");
 const {filterToRegExp} = require("./common");
 
 /**
+ * Regular expression used to match the <code>||</code> prefix in an otherwise
+ * literal pattern.
+ * @type {RegExp}
+ */
+let doubleAnchorRegExp = new RegExp(filterToRegExp("||") + "$");
+
+/**
  * All known unique domain sources mapped to their parsed values.
  * @type {Map.<string,Map.<string,boolean>>}
  */
 let knownDomainMaps = new Map();
+
+/**
+ * Checks whether the given pattern is a string of literal characters with no
+ * wildcards or any other special characters. If the pattern is prefixed with a
+ * <code>||</code> but otherwise contains no special characters, it is still
+ * considered to be a literal pattern.
+ * @param {string} pattern
+ * @returns {boolean}
+ */
+function isLiteralPattern(pattern)
+{
+  return !/[*^|]/.test(pattern.replace(/^\|{2}/, ""));
+}
 
 /**
  * Abstract base class for filters
  *
  * @param {string} text   string representation of the filter
  * @constructor
  */
 function Filter(text)
 {
   this.text = text;
@@ skipping 93 matching lines @@
           this._subscriptions = [...this._subscriptions][0];
       }
       else if (subscription == this._subscriptions)
       {
         this._subscriptions = null;
       }
     }
   },
 
   /**
-   * Serializes the filter to an array of strings for writing out on the disk.
-   * @param {string[]} buffer  buffer to push the serialization results into
-   */
-  serialize(buffer)
-  {
-    buffer.push("[Filter]");
-    buffer.push("text=" + this.text);
+   * Serializes the filter for writing out on disk.
+   * @yields {string}
+   */
+  *serialize()
+  {
+    let {text} = this;
+
+    yield "[Filter]";
+    yield "text=" + text;
   },
 
   toString()
   {
     return this.text;
   }
 };
 
 /**
  * Cache for known filters, maps string representation to filter objects.
@@ skipping 156 matching lines @@
   /**
    * Reason why this filter is invalid
    * @type {string}
    */
   reason: null,
 
   /**
    * See Filter.serialize()
    * @inheritdoc
    */
-  serialize(buffer) {}
+  *serialize() {}
 });
 
 /**
  * Class for comments
  * @param {string} text see {@link Filter Filter()}
  * @constructor
  * @augments Filter
  */
 function CommentFilter(text)
 {
   Filter.call(this, text);
 }
 exports.CommentFilter = CommentFilter;
 
 CommentFilter.prototype = extend(Filter, {
   type: "comment",
 
   /**
    * See Filter.serialize()
    * @inheritdoc
    */
-  serialize(buffer) {}
+  *serialize() {}
 });
 
 /**
  * Abstract base class for filters that can get hits
  * @param {string} text
  *   see {@link Filter Filter()}
  * @param {string} [domains]
  *   Domains that the filter is restricted to separated by domainSeparator
  *   e.g. "foo.com|bar.com|~baz.com"
  * @constructor
@@ skipping 262 matching lines @@
   {
     let {sitekeys, domains} = this;
 
     return !(sitekeys && sitekeys.length) && (!domains || domains.get(""));
   },
 
   /**
    * See Filter.serialize()
    * @inheritdoc
    */
-  serialize(buffer)
-  {
-    if (this._disabled || this._hitCount || this._lastHit)
-    {
-      Filter.prototype.serialize.call(this, buffer);
-      if (this._disabled)
-        buffer.push("disabled=true");
-      if (this._hitCount)
-        buffer.push("hitCount=" + this._hitCount);
-      if (this._lastHit)
-        buffer.push("lastHit=" + this._lastHit);
+  *serialize()
+  {
+    let {_disabled, _hitCount, _lastHit} = this;
+
+    if (_disabled || _hitCount || _lastHit)
+    {
+      yield* Filter.prototype.serialize.call(this);
+      if (_disabled)
+        yield "disabled=true";
+      if (_hitCount)
+        yield "hitCount=" + _hitCount;
+      if (_lastHit)
+        yield "lastHit=" + _lastHit;
     }
   }
 });
 
 /**
  * Abstract base class for RegExp-based filters
  * @param {string} text see {@link Filter Filter()}
  * @param {string} regexpSource
  *   filter part that the regular expression should be build from
  * @param {number} [contentType]
@@ skipping 31 matching lines @@
       regexpSource[regexpSource.length - 1] == "/")
   {
     // The filter is a regular expression - convert it immediately to
     // catch syntax errors
     let regexp = new RegExp(regexpSource.substr(1, regexpSource.length - 2),
                             this.matchCase ? "" : "i");
     Object.defineProperty(this, "regexp", {value: regexp});
   }
   else
   {
+    if (!this.matchCase && isLiteralPattern(regexpSource))
+      regexpSource = regexpSource.toLowerCase();
+
     // No need to convert this filter to regular expression yet, do it on demand
     this.pattern = regexpSource;
   }
 }
 exports.RegExpFilter = RegExpFilter;
 
 RegExpFilter.prototype = extend(ActiveFilter, {
   /**
    * Number of filters contained, will always be 1 (required to
    * optimize {@link Matcher}).
@@ skipping 11 matching lines @@
    * for delayed creation of the regexp property
    * @type {?string}
    */
   pattern: null,
   /**
    * Regular expression to be used when testing against this filter
    * @type {RegExp}
    */
   get regexp()
   {
-    let source = filterToRegExp(this.pattern, this.rewrite != null);
-    let regexp = new RegExp(source, this.matchCase ? "" : "i");
-    Object.defineProperty(this, "regexp", {value: regexp});
-    return regexp;
+    let value = null;
+
+    let {pattern, rewrite} = this;
+    if (rewrite != null || !isLiteralPattern(pattern))
+    {
+      value = new RegExp(filterToRegExp(pattern, rewrite != null),
+                         this.matchCase ? "" : "i");
+    }
+
+    Object.defineProperty(this, "regexp", {value});
+    return value;
   },
   /**
    * Content types the filter applies to, combination of values from
    * RegExpFilter.typeMap
    * @type {number}
    */
   contentType: 0x7FFFFFFF,
   /**
    * Defines whether the filter should distinguish between lower and
    * upper case letters
@@ skipping 24 matching lines @@
     {
       sitekeys = this.sitekeySource.split("|");
       this.sitekeySource = null;
     }
 
     Object.defineProperty(
       this, "sitekeys", {value: sitekeys, enumerable: true}
     );
     return this.sitekeys;
   },
-  /**
-   * Tests whether the filter only has location.
-   */
-  get isLocationOnly()

[Manish Jethani, 2018/10/21 16:06:52]

Let's make this a function rather than a property. i.e. no get

[Jon Sonesen, 2018/10/23 17:36:32]

Acknowledged.

+
+  /**
+   * Tests whether the filter only has a location.
+   * @return {boolean}
+   */
+  isLocationOnly()
   {
     return this.contentType == RegExpFilter.prototype.contentType &&

[Manish Jethani, 2018/10/24 21:35:28]

I haven't run this code, but I'm pretty sure that this would cause the initial
memory footprint to go up, because we would end up creating the domain maps for
all the blocking/whitelist filters.

We could change the check to this:

  return this.contentType == RegExpFilter.prototype.contentType &&
         this.thirdParty == null && !this.domainSource && !this.sitekeySource &&
         !this.domains && !this.sitekeys;

For filters that do have domains, it would short-circuit at `!this.domainSource`
and thus avoid the creation of the domain map. If the domain map has already
been created, it would fail at `!this.domains`. For filters that do not have
domains, both tests would pass.

[Jon Sonesen, 2018/10/24 21:46:51]

Ah, I see what you mean there. I didn't look deep enough in the docs/source to
properly see or understand domainSource and sitekeySource

            this.thirdParty == null && !this.domains && !this.sitekeys;
   },
 
   /**
    * Tests whether the URL matches this filter
    * @param {string} location URL to be tested
    * @param {number} typeMask bitmask of content / request types to match
    * @param {string} [docDomain] domain name of the document that loads the URL
    * @param {boolean} [thirdParty] should be true if the URL is a third-party
    *                               request
    * @param {string} [sitekey] public key provided by the document
    * @return {boolean} true in case of a match
    */
   matches(location, typeMask, docDomain, thirdParty, sitekey)
   {
     return (this.contentType & typeMask) != 0 &&
            (this.thirdParty == null || this.thirdParty == thirdParty) &&
            this.isActiveOnDomain(docDomain, sitekey) &&
-           this.regexp.test(location);
-  },
+           this.matchesLocation(location);
+  },
+
+  /**
+   * Checks whether the given URL matches this filter's pattern.
+   * @param {string} location The URL to check.
+   * @returns {boolean} <code>true</code> if the URL matches.
+   */
   matchesLocation(location)
   {
-    return this.regexp.test(location);
+    let {regexp} = this;
+
+    if (regexp)
+      return regexp.test(location);
+
+    if (!this.matchCase)
+      location = location.toLowerCase();
+
+    let {pattern} = this;
+
+    if (pattern[0] == "|" && pattern[1] == "|")
+    {
+      let index = location.indexOf(pattern.substring(2));
+
+      // The "||" prefix requires that the text that follows does not start
+      // with a forward slash.
+      return index != -1 && location[index] != "/" &&
+             doubleAnchorRegExp.test(location.substring(0, index));
+    }
+
+    return location.includes(pattern);
   }
 });
 
 /**
  * Yields the filter itself (required to optimize {@link Matcher}).
  * @yields {RegExpFilter}
  */
 RegExpFilter.prototype[Symbol.iterator] = function*()
 {
   yield this;
@@ skipping 474 matching lines @@
 
   /**
    * Script that should be executed
    * @type {string}
    */
   get script()
   {
     return this.body;
   }
 });