Issue 7089 - Match filters by type for non-default types

Memory impact:
 -  Uses ~200 KB more for EasyList+AA

Performance impact:
 -  Loading of the default subscriptions may be slightly slower, though I couldn't discern any noticeable/measurable slowdown
 -  No performance impact on filter matching for default types like $script, $image, and so on
 -  Filter matching for non-default types like $elemhide and $csp is about twice as fast now

[Manish Jethani, 2018-11-02 00:33:47]

Patch Set 1

https://codereview.adblockplus.org/29933592/diff/29933593/lib/matcher.js
File lib/matcher.js (right):

https://codereview.adblockplus.org/29933592/diff/29933593/lib/matcher.js#newc...
lib/matcher.js:70: function* nonDefaultTypes(contentType)
For a filter like `foo$script,image,popup`, this function will yield the value
of `RegExpFilter.typeMap.POPUP` (currently 0x10000000).

https://codereview.adblockplus.org/29933592/diff/29933593/lib/matcher.js#newc...
lib/matcher.js:92: let set = map.get(keyword);
This has been copied and pasted from the add and remove functions (respectively)
with no changes to the logic.

https://codereview.adblockplus.org/29933592/diff/29933593/lib/matcher.js#newc...
lib/matcher.js:316: if ((typeMask & NON_DEFAULT_TYPES) != 0 && (typeMask &
typeMask - 1) == 0)
The second condition here basically checks if the type mask has only a single
bit set.

https://codereview.adblockplus.org/29933592/diff/29933593/test/matcher.js
File test/matcher.js (right):

https://codereview.adblockplus.org/29933592/diff/29933593/test/matcher.js#new...
test/matcher.js:206: checkMatch(test, ["@@foo.com$document"],
"http://foo.com/bar", "DOCUMENT", "foo.com", false, null, false,
"@@foo.com$document");
Tests for $document and $elemhide

https://codereview.adblockplus.org/29933592/diff/29933593/test/matcher.js#new...
test/matcher.js:219: checkMatch(test, ["||foo.com^$popup"],
"http://foo.com/bar", "POPUP", "foo.com", false, null, false,
"||foo.com^$popup");
Tests for $popup and $csp

[Manish Jethani, 2018-11-02 00:38:15]

For testing this, you could add the following at the end of `lib/matcher.js`
along with a custom filter `^index^`, then build and reload the extension and
observe the background page console:

  setTimeout(() =>
  {
    let startTime = performance.now();
    let blocked = 0;
    for (let type in RegExpFilter.typeMap)
    {
      if (RegExpFilter.typeMap[type] & RegExpFilter.prototype.contentType)
        continue;

      for (let i = 0; i < 10000; i++)
      {
        let url = "http://example.com/iny6703v26m/evnuqh1a4ak/qicz2zyn47/" +
                  "doubleclick/300x500/ads?";
        if (i < 50)
          url += "index=" + i;
        else
          url += "noindex=" + i;
        let filter = defaultMatcher.matchesAny(url, RegExpFilter.typeMap[type],
                                               "example.com", false, null,
false);
        if (filter && filter.type == "blocking")
          blocked++;
      }
    }
    console.log(blocked + " blocked in " +
                ((performance.now() - startTime) | 0));
  },
  3000);

[Manish Jethani, 2018-11-30 07:33:05]

We should prioritize this one over the patches for #7094, #7096, and #7097.

Reason: Those changes are going to be controversial and will require some
discussion/understanding, but the change here is relatively simple. According to
my tests above, this one also has a significant impact on performance while only
raising the memory footprint a little bit.

[hub, 2018-12-11 15:34:59]

LGTM

https://codereview.adblockplus.org/29933592/diff/29933593/lib/matcher.js
File lib/matcher.js (right):

https://codereview.adblockplus.org/29933592/diff/29933593/lib/matcher.js#newc...
lib/matcher.js:316: if ((typeMask & NON_DEFAULT_TYPES) != 0 && (typeMask &
typeMask - 1) == 0)
On 2018/11/02 00:33:47, Manish Jethani wrote:
> The second condition here basically checks if the type mask has only a single
> bit set.

What throw me off here is the evaluation order of `typeMask & typeMask - 1`. But
I get it.