Issue 5141 - [emscripten] Convert filter matcher to C++

These changes rely on code currently under review in https://codereview.adblockplus.org/29574591/, https://codereview.adblockplus.org/29581588/ and https://codereview.adblockplus.org/29572731/.

COLLABORATOR=sergei@adblockplus.org

[Wladimir Palant, 2017-10-17 12:51:22]

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/filter/Reg...
File compiled/filter/RegExpFilter.h (left):

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/filter/Reg...
compiled/filter/RegExpFilter.h:33: };
The matcher might need to access the pattern part of the filter even after the
regexp has been generated, so this cannot be a union.

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
File compiled/matcher/Matcher.cpp (right):

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.cpp:48: mResult ^= Rotate(mCurrentChars[pos],
SUBSTRING_LENGTH);
Normally, one wouldn't use the char value directly but rather use some hash
function on it. This implementation is rather suboptimal, in particular the
resulting hash values will use at most 24 bits (typically no more than 16 bits
however). I would like to measure the performance of this implementation first
however, so that we have a baseline to compare to. We can then improve later.

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.cpp:55: }
This goal of this method is to avoid exposing SUBSTRING_LENGTH to the callers.
Let me know if you think that the caller should just do the necessary
calculations itself.

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.cpp:59: return mResult & 0x7FFFFFFF;
We cut off the top bit because key values 0xFFFFFFFF and 0xFFFFFFFE are reserved
in Uint32Map.

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
File compiled/matcher/Matcher.h (right):

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.h:41: const String& siteKey, bool specificOnly);
Would be nice if this method could be const, it cannot return a non-const
pointer then however. And returning a const pointer would be wrong, the calling
JS code will likely modify it.

https://codereview.adblockplus.org/29581602/diff/29581603/test/matcher.js
File test/matcher.js (right):

https://codereview.adblockplus.org/29581602/diff/29581603/test/matcher.js#new...
test/matcher.js:18: "use strict";
This test has been taken from the master branch and adapted slightly:

* Testing internals (keywords and caching) has been removed.
* checkMatch() function has been adapted to API changes and rewritten somewhat
to be more concise.
* Some of the tests had multiple potentially matching filters and relied on
internals to determine which one will actually match. These internals are no
longer valid, the matching filter depends in particular on the blacklisting vs.
whitelisting scenario. So I had to adjust these tests to remove the ambiguity.

https://codereview.adblockplus.org/29581602/diff/29581603/test/matcher.js#new...
test/matcher.js:137: checkMatch(test, ["abc$domain=foo.com",
"abc$domain=bar.com", "abc$domain=~foo.com|~bar.com"], "http://abc/def",
"IMAGE", "foo.com", false, null, false, "abc$domain=foo.com");
This test and a few similar ones are currently failing. I still need to
investigate this, the failure might be caused by code not touched here.

[Felix Dahlke, 2017-10-17 13:42:02]

It looks like you've also based this on
https://codereview.adblockplus.org/29527808/ (introducing Meson). I don't think
we should rush our new build system, so can you base these changes on the
current one?

Having said that, moving myself back to CC.

[Wladimir Palant, 2017-10-17 14:35:23]

On 2017/10/17 13:42:02, Felix Dahlke wrote:
> It looks like you've also based this on
> https://codereview.adblockplus.org/29527808/ (introducing Meson).

That's a local change, Meson is simply more convenient to use. I don't intend to
push it for this change.

[sergei, 2017-10-18 10:58:44]

I have not tried it yet but in general good, merely some thought regarding the
code style.

It would be good to profile and see at least how good the hash function is, in
particular how many filters go into the nonoptimized bucket and and how many
iterations are in the implementation of Uint32Set in order to put and find an
entry.

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/filter/Reg...
File compiled/filter/RegExpFilter.cpp (right):

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/filter/Reg...
compiled/filter/RegExpFilter.cpp:395: const OwnedString
pattern(mData.GetRegExpSource(mText));
BTW, `pattern` should be a DependentString there is no need in additional
copying of it, GetRegExpSource returns DependentString.

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
File compiled/matcher/Matcher.cpp (right):

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.cpp:32: result_type Rotate(result_type value, uint32_t
bits)
should it be static?

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.cpp:34: return value << bits | value >> (VALUE_SIZE -
bits);
Mind adding static_assert(std::is_unsigned<result_type>::value)? Signed left and
right shifts have edge cases with undefined and implementation-defined behavior.

In addition maybe add static_assert that bits is less than 32 (which is BTW
std::numeric_limits<result_type>::digits) because otherwise it's UB. It's called
only with two different values for bits argument, 1 and SUBSTRING_LENGTH, and is
likely inlined, so one could make bits a template value parameter in order to be
able to use static_assert.

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.cpp:34: return value << bits | value >> (VALUE_SIZE -
bits);
I wonder whether our compilers are smart enough to replace this function by the
corresponding rotate instruction in the native code, and what happens while JS
is generated, how it finally looks in JS.

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.cpp:47: if (mCount > SUBSTRING_LENGTH)
Do we really need this condition?
Can we rather set the initial value of mResult to the hash of
"\0\0\0\0\0\0\0\0", which is currently zero, and initialize mCurrentChars to
that string of zero characters?

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.cpp:55: }
On 2017/10/17 12:51:22, Wladimir Palant wrote:
> This goal of this method is to avoid exposing SUBSTRING_LENGTH to the callers.
> Let me know if you think that the caller should just do the necessary
> calculations itself.

IMO not only the caller should do the calculation but also that SUBSTRING_LENGTH
should be defined outside RollingHash, e.g. as template value parameter, but for
the sake of simplicity it can be in the anonymous namespace in this file.

In this case minPrefixLength should be initialized to SUBSTRING_LENGTH, can be
unsigned integer and renamed to something like nextCandidateEnd, so when a
special character is encountered nextCandidateEnd is set to `i +
SUBSTRING_LENGTH - 1` and we compare i and nextCandidateEnd (no subtraction on
each loop step, BTW).

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.cpp:59: return mResult & 0x7FFFFFFF;
On 2017/10/17 12:51:22, Wladimir Palant wrote:
> We cut off the top bit because key values 0xFFFFFFFF and 0xFFFFFFFE are
reserved
> in Uint32Map.

Maybe put a special const value masking the range of values without special
values as the member of Uint32SetEntry and use it here as
Uint32Map::entry_type::user_key_values_range?

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.cpp:77: for (auto i = 0; i < str.length(); i++)
Here auto resolves into `int`, but should be String::size_type. The same for
other places.

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.cpp:110: if (currentChar == u'*' || currentChar == u'^'
|| currentChar == u'|')
What about putting this condition into an inline function?

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.cpp:117: if (entry && entry->second == &filter)
The type of second is RegExpFilterPtr, so finally we compare RegExpFilter* and
Filter*, although it does work with the current code and will likely work in the
future, it would be better to compare pointers to the same types, either to
Filter* or to RegExpFilter*, so here it would be better to compare second with
regExpFilter, IMO.

The same for `if (ptr == &filter)` below.

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
File compiled/matcher/Matcher.h (right):

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.h:32: std::vector<RegExpFilterPtr> mUnoptimizedFilters;
IMO, prefix Non would be better in comparison with Un because there is just an
absence of an optimization.

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.h:37: void BINDINGS_EXPORTED Add(Filter& filter);
Since Matcher works only with RegExpFilter-based filters should it accept here
RegExpFilter& and not Filter&?
I wonder whether moving that check out the method can even result in the
optimization, because anyway we sort filters out Matcher, ElemHide and
ElemHideEmulation.

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.h:40: int typeMask, DependentString& docDomain, bool
thirdParty,
Just for reference, I see how docDomain is used internally and understand that
it's an optimization but it's still looks questionable to have it not as `const
String&`.

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.h:41: const String& siteKey, bool specificOnly);
On 2017/10/17 12:51:22, Wladimir Palant wrote:
> Would be nice if this method could be const, it cannot return a non-const
> pointer then however. And returning a const pointer would be wrong, the
calling
> JS code will likely modify it.

Yeah, since ref_counted is non-const it cannot be a const method.

BTW, I would propose to think about properties behind SetHitCount and SetLastHit
because IMO they should not be members of the filter object because they carry
information how a filter object is used and not about the filter itself, e.g. we
are not adding matcherHash property or subscriptions property to a filter
object.

https://codereview.adblockplus.org/29581602/diff/29581603/lib/matcher.js
File lib/matcher.js (right):

https://codereview.adblockplus.org/29581602/diff/29581603/lib/matcher.js#newc...
lib/matcher.js:22: exports.defaultMatcher = Matcher.create();
BTW, just for reference, currently it's not deleted.

https://codereview.adblockplus.org/29581602/diff/29581603/test/matcher.js
File test/matcher.js (right):

https://codereview.adblockplus.org/29581602/diff/29581603/test/matcher.js#new...
test/matcher.js:32: {defaultMatcher, Matcher} =
sandboxedRequire("../lib/matcher")
What about deletion of defaultMatcher in tearDown?

https://codereview.adblockplus.org/29581602/diff/29581603/test/matcher.js#new...
test/matcher.js:47: let matcher = Matcher.create();
matcher is not deleted.

[sergei, 2017-11-20 16:30:50]

https://codereview.adblockplus.org/29581602/diff/29581603/test/matcher.js
File test/matcher.js (right):

https://codereview.adblockplus.org/29581602/diff/29581603/test/matcher.js#new...
test/matcher.js:137: checkMatch(test, ["abc$domain=foo.com",
"abc$domain=bar.com", "abc$domain=~foo.com|~bar.com"], "http://abc/def",
"IMAGE", "foo.com", false, null, false, "abc$domain=foo.com");
On 2017/10/17 12:51:22, Wladimir Palant wrote:
> This test and a few similar ones are currently failing. I still need to
> investigate this, the failure might be caused by code not touched here.

I think it is because of mutable docDomain. docDomain is passed by reference and
when it checks whether the data matches the second filter its value gets "com",
so when it reaches the third filter it matches too. I think Hubert meant or
observed the same in
https://codereview.adblockplus.org/29594607/diff/29594608/compiled/ElemHideEm....

I would propose to consider passing of DependentString by value, though bindings
generator should be aware about it.

PS: I have to say that debugging is not trivial at all, we should discuss it
separately.

[hub, 2017-11-20 17:38:33]

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
File compiled/matcher/Matcher.cpp (right):

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.cpp:52: int32_t PrefixLength()
IMHO this should be const method.

https://codereview.adblockplus.org/29581602/diff/29581603/compiled/matcher/Ma...
compiled/matcher/Matcher.cpp:57: result_type GetResult()
and const method here too.

[sergei, 2017-12-20 09:23:23]

https://codereview.adblockplus.org/29581602/diff/29581603/lib/matcher.js
File lib/matcher.js (right):

https://codereview.adblockplus.org/29581602/diff/29581603/lib/matcher.js#newc...
lib/matcher.js:21: exports.Matcher = Matcher;
this Matcher is used in lib/notifications.js, so that file should be adjusted
too.

[Wladimir Palant, 2017-12-21 10:57:00]

Since I won't finish this change, I've added Sergei as collaborator - this
should allow you to update this review if necessary.