Issue 7260 - Internalize third-party request check in matcher

lib/matcher.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 Matcher class implementing matching addresses against
  *               a list of filters.
  */
 
 const {RegExpFilter, WhitelistFilter} = require("./filterClasses");
+const {isThirdParty} = require("./domain");
 
 /**
  * Regular expression for matching a keyword in a filter.
  * @type {RegExp}
  */
 const keywordRegExp = /[^a-z0-9%*][a-z0-9%]{3,}(?=[^a-z0-9%*])/;
 
 /**
  * Regular expression for matching all keywords in a filter.
  * @type {RegExp}
@@ skipping 333 matching lines @@
           collection.push(filter);
         }
       }
     }
 
     return null;
   }
 
   /**
    * Tests whether the URL matches any of the known filters
-   * @param {string} location
+   * @param {URL|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
    * @param {boolean} [specificOnly]
    *   should be <code>true</code> if generic matches should be ignored
    * @returns {?RegExpFilter}
    *   matching filter or <code>null</code>
    */
-  matchesAny(location, typeMask, docDomain, thirdParty, sitekey, specificOnly)
+  matchesAny(location, typeMask, docDomain, sitekey, specificOnly)
   {
+    let thirdParty = docDomain && isThirdParty(location, docDomain);

[Sebastian Noack, 2019/02/05 04:32:53]

As discussed on IRC, how about only calling isThirdParty() if we found a filter
with a non-null `thirdParty` property?

[Manish Jethani, 2019/02/05 05:07:28]

I tried this but it actually seemed to be more expensive. This makes sense: only
about 5% of all requests are blocked. I have not analyzed why it was more
expensive (maybe there is a single filter in EasyList with the flag set that
applies to most requests?), and maybe we can look into it later. It does seem
like a good idea on the surface.

Since more than 80% of the requests are going to be in the 10,000-entry cache
now, and since isThirdParty is super optimized anyway, it's not worth much
trying avoid calling it.

[Sebastian Noack, 2019/02/05 05:21:16]

Sure, if you just call isThridParty() as we perform third-party checks
currently, this might cause isThirdParty() being called several times while
matching a single URL:

  matches(location, typeMask, docDomain, thirdParty, sitekey)
  {
    return (this.contentType & typeMask) != 0 &&
           (this.thirdParty == null || this.thirdParty == thirdParty) &&
           this.isActiveOnDomain(docDomain, sitekey) &&
           this.matchesLocation(location);
  }

Did you try moving the third party check to the bottom?
I'm not too happy about this change, and while it might help to cheat your
benchmark, I wonder how great an improvement this is in practice. IMO, a proper
LRU cache would be rather in order, as I commented on the issue, or even better
improving the matching as much that caching becomes redundant.

[Manish Jethani, 2019/02/05 05:42:23]

Yes, I know what you mean. I put the isThirdParty call in checkEntryMatch, which
means it would get called for every keyword in the URL.

Anyway, this is a lot of work to find out how to minimize the calls to
isThirdParty. First we need to look at the filter list data to see if it makes
sense. Then we need to think about where to position that call. Some refactoring
may be involved. I really don't want to go there right now, at least for this
release.
The purpose of this change should be not to optimize but rather to move the
calls into Core now so they can be optimized in whatever way later.

Leaving aside performance (let's say there is zero improvement here), would you
still rather leave the check for third-party request status in
adblockpluschrome?

This is of course also a question for libadblockplus and all of its clients. The
more things stay in Core the better it is for everyone.

[Sebastian Noack, 2019/02/05 05:54:45]

Fair enough, for not further optimizing this here. But I'd still want to revisit
https://issues.adblockplus.org/ticket/7254#comment:11 before updating the
dependency for the release, this however, is unrelated of the changes here.

+
+    if (typeof location != "string")
+      location = location + "";
+
     let candidates = location.toLowerCase().match(/[a-z0-9%]{3,}/g);
     if (candidates === null)
       candidates = [];
     candidates.push("");
+
     for (let i = 0, l = candidates.length; i < l; i++)
     {
       let result = this.checkEntryMatch(candidates[i], location, typeMask,
                                         docDomain, thirdParty, sitekey,
                                         specificOnly);
       if (result)
         return result;
     }
 
     return null;
@@ skipping 90 matching lines @@
   }
 
   /**
    * Optimized filter matching testing both whitelist and blacklist matchers
    * simultaneously. For parameters see
      {@link Matcher#matchesAny Matcher.matchesAny()}.
    * @see Matcher#matchesAny
    * @inheritdoc
    * @private
    */
-  _matchesAnyInternal(location, typeMask, docDomain, thirdParty, sitekey,
-                      specificOnly)
+  _matchesAnyInternal(location, typeMask, docDomain, sitekey, specificOnly)
   {
+    let thirdParty = docDomain && isThirdParty(location, docDomain);
+
+    if (typeof location != "string")
+      location = location + "";
+
     let candidates = location.toLowerCase().match(/[a-z0-9%]{3,}/g);
     if (candidates === null)
       candidates = [];
 
     // The first keyword in a URL is the protocol (usually "https" or "http").
     // This is an outlier: it has hundreds of filters typically, yet it rarely
     // ever has a match. We cut down the amount of processing for blocked URLs
     // significantly by moving it to the end of the list.
     if (candidates.length > 1)
       candidates.push(candidates.shift());
@@ skipping 24 matching lines @@
       {
         whitelistHit = this._whitelist.checkEntryMatch(candidates[i], location,
                                                        typeMask, docDomain,
                                                        thirdParty, sitekey);
       }
     }
 
     return whitelistHit || blacklistHit;
   }
 
-  _searchInternal(location, typeMask, docDomain, thirdParty, sitekey,
-                  specificOnly, filterType)
+  _searchInternal(location, typeMask, docDomain, sitekey, specificOnly,
+                  filterType)
   {
     let hits = {};
 
     let searchBlocking = filterType == "blocking" || filterType == "all";
     let searchWhitelist = filterType == "whitelist" || filterType == "all";
 
     if (searchBlocking)
       hits.blocking = [];
 
     if (searchWhitelist)
       hits.whitelist = [];
 
     // If the type mask includes no types other than whitelist-only types, we
     // can skip the blacklist.
     if ((typeMask & ~WHITELIST_ONLY_TYPES) == 0)
       searchBlocking = false;
 
+    let thirdParty = docDomain && isThirdParty(location, docDomain);
+
+    if (typeof location != "string")
+      location = location + "";
+
     let candidates = location.toLowerCase().match(/[a-z0-9%]{3,}/g);
     if (candidates === null)
       candidates = [];
     candidates.push("");
 
     for (let i = 0, l = candidates.length; i < l; i++)
     {
       if (searchBlocking)
       {
         this._blacklist.checkEntryMatch(candidates[i], location, typeMask,
                                         docDomain, thirdParty, sitekey,
                                         specificOnly, hits.blocking);
       }
 
       if (searchWhitelist)
       {
         this._whitelist.checkEntryMatch(candidates[i], location, typeMask,
                                         docDomain, thirdParty, sitekey,
                                         false, hits.whitelist);
       }
     }
 
     return hits;
   }
 
   /**
    * @see Matcher#matchesAny
    * @inheritdoc
    */
-  matchesAny(location, typeMask, docDomain, thirdParty, sitekey, specificOnly)
+  matchesAny(location, typeMask, docDomain, sitekey, specificOnly)
   {
-    let key = location + " " + typeMask + " " + docDomain + " " + thirdParty +
-      " " + sitekey + " " + specificOnly;
+    let key = location + " " + typeMask + " " + docDomain + " " + sitekey +
+              " " + specificOnly;
 
     let result = this._resultCache.get(key);
     if (typeof result != "undefined")
       return result;
 
     result = this._matchesAnyInternal(location, typeMask, docDomain,
-                                      thirdParty, sitekey, specificOnly);
+                                      sitekey, specificOnly);
 
     if (this._resultCache.size >= this.maxCacheEntries)
       this._resultCache.clear();
 
     this._resultCache.set(key, result);
 
     return result;
   }
 
   /**
    * @typedef {object} MatcherSearchResults
    * @property {Array.<BlockingFilter>} [blocking] List of blocking filters
    *   found.
    * @property {Array.<WhitelistFilter>} [whitelist] List of whitelist filters
    *   found.
    */
 
   /**
    * Searches all blocking and whitelist filters and returns results matching
    * the given parameters.
    *
-   * @param {string} location
+   * @param {URL|string} location
    * @param {number} typeMask
    * @param {string} [docDomain]
-   * @param {boolean} [thirdParty]
    * @param {string} [sitekey]
    * @param {boolean} [specificOnly]
    * @param {string} [filterType] The types of filters to look for. This can be
    *   <code>"blocking"</code>, <code>"whitelist"</code>, or
    *   <code>"all"</code> (default).
    *
    * @returns {MatcherSearchResults}
    */
-  search(location, typeMask, docDomain, thirdParty, sitekey, specificOnly,
+  search(location, typeMask, docDomain, sitekey, specificOnly,
          filterType = "all")
   {
     let key = "* " + location + " " + typeMask + " " + docDomain + " " +
-              thirdParty + " " + sitekey + " " + specificOnly + " " +
-              filterType;
+              sitekey + " " + specificOnly + " " + filterType;
 
     let result = this._resultCache.get(key);
     if (typeof result != "undefined")
       return result;
 
-    result = this._searchInternal(location, typeMask, docDomain, thirdParty,
-                                  sitekey, specificOnly, filterType);
+    result = this._searchInternal(location, typeMask, docDomain, sitekey,
+                                  specificOnly, filterType);
 
     if (this._resultCache.size >= this.maxCacheEntries)
       this._resultCache.clear();
 
     this._resultCache.set(key, result);
 
     return result;
   }
 
   /**
    * Tests whether the URL is whitelisted
    * @see Matcher#matchesAny
    * @inheritdoc
    * @returns {boolean}
    */
-  isWhitelisted(location, typeMask, docDomain, thirdParty, sitekey,
-                specificOnly)
+  isWhitelisted(location, typeMask, docDomain, sitekey, specificOnly)
   {
-    return !!this._whitelist.matchesAny(location, typeMask, docDomain,
-                                        thirdParty, sitekey, specificOnly);
+    return !!this._whitelist.matchesAny(location, typeMask, docDomain, sitekey,
+                                        specificOnly);
   }
 }
 
 exports.CombinedMatcher = CombinedMatcher;
 
 /**
  * Shared {@link CombinedMatcher} instance that should usually be used.
  * @type {CombinedMatcher}
  */
 let defaultMatcher = new CombinedMatcher();
 
 exports.defaultMatcher = defaultMatcher;