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

compiled/matcher/Matcher.cpp

+/*
+ * 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/>.
+ */
+
+#include "Matcher.h"
+#include "../filter/WhitelistFilter.h"
+
+class RollingHash
+{
+private:
+  static const String::size_type SUBSTRING_LENGTH = 8;
+  static const uint32_t VALUE_SIZE = 32;
+  typedef uint32_t result_type;
+  String::size_type mCount;
+  result_type mResult;
+  String::value_type mCurrentChars[SUBSTRING_LENGTH];
+
+private:
+  result_type Rotate(result_type value, uint32_t bits)

[sergei, 2017/10/18 10:58:43]

should it be static?

+  {
+    return value << bits | value >> (VALUE_SIZE - bits);

[sergei, 2017/10/18 10:58:42]

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.

[sergei, 2017/10/18 10:58:42]

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.

+  }
+
+public:
+  RollingHash()
+      : mCount(0), mResult(0)
+  {
+  }
+
+  void Advance(String::value_type newChar)
+  {
+    auto pos = mCount++ % SUBSTRING_LENGTH;
+    mResult = Rotate(mResult, 1) ^ newChar;
+    if (mCount > SUBSTRING_LENGTH)

[sergei, 2017/10/18 10:58:43]

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?

+      mResult ^= Rotate(mCurrentChars[pos], SUBSTRING_LENGTH);

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

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.

+    mCurrentChars[pos] = newChar;
+  }
+
+  int32_t PrefixLength()

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

IMHO this should be const method.

+  {
+    return static_cast<int32_t>(mCount) - SUBSTRING_LENGTH;
+  }

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

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.

[sergei, 2017/10/18 10:58:43]

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).

+
+  result_type GetResult()

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

and const method here too.

+  {
+    return mResult & 0x7FFFFFFF;

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

We cut off the top bit because key values 0xFFFFFFFF and 0xFFFFFFFE are reserved
in Uint32Map.

[sergei, 2017/10/18 10:58:42]

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?

+  }
+};
+
+Matcher* Matcher::Create()
+{
+  return new Matcher();
+}
+
+void Matcher::Add(Filter& filter)
+{
+  RegExpFilter* regExpFilter = filter.As<RegExpFilter>();
+  if (!regExpFilter)
+    return;
+
+  RollingHash hash;
+  DependentString str(regExpFilter->GetRegExpSource());
+  int32_t minPrefixLength = 0;
+  for (auto i = 0; i < str.length(); i++)

[sergei, 2017/10/18 10:58:43]

Here auto resolves into `int`, but should be String::size_type. The same for
other places.

+  {
+    auto currentChar = str[i];
+    if (currentChar == u'*' || currentChar == u'^' || currentChar == u'|')
+      minPrefixLength = i + 1;
+    hash.Advance(currentChar);
+    if (hash.PrefixLength() >= minPrefixLength)
+    {
+      auto candidate = hash.GetResult();
+      auto entry = mFilters.find(candidate);
+      if (!entry)
+      {
+        entry.assign(candidate, RegExpFilterPtr(regExpFilter));
+        return;
+      }
+    }
+  }
+
+  mUnoptimizedFilters.push_back(RegExpFilterPtr(regExpFilter));
+}
+
+void Matcher::Remove(const Filter& filter)
+{
+  const RegExpFilter* regExpFilter = filter.As<RegExpFilter>();
+  if (!regExpFilter)
+    return;
+
+  RollingHash hash;
+  DependentString str(regExpFilter->GetRegExpSource());
+  String::size_type minPrefixLength = 0;
+  for (auto i = 0; i < str.length(); i++)
+  {
+    auto currentChar = str[i];
+    if (currentChar == u'*' || currentChar == u'^' || currentChar == u'|')

[sergei, 2017/10/18 10:58:43]

What about putting this condition into an inline function?

+      minPrefixLength = i + 1;
+    hash.Advance(currentChar);
+    if (hash.PrefixLength() >= minPrefixLength)
+    {
+      auto candidate = hash.GetResult();
+      auto entry = mFilters.find(candidate);
+      if (entry && entry->second == &filter)

[sergei, 2017/10/18 10:58:43]

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.

+      {
+        mFilters.erase(candidate);
+        return;
+      }
+    }
+  }
+
+  for (auto ptr : mUnoptimizedFilters)
+    if (ptr == &filter)
+      ptr.reset();
+}
+
+RegExpFilter* Matcher::MatchesAny(const String& location, int typeMask,
+    DependentString& docDomain, bool thirdParty, const String& siteKey,
+    bool specificOnly)
+{
+  RegExpFilterPtr result;
+
+  RollingHash hash;
+  for (auto i = 0; i < location.length(); i++)
+  {
+    hash.Advance(location[i]);
+    if (hash.PrefixLength() >= 0)
+    {
+      auto entry = mFilters.find(hash.GetResult());
+      if (!entry)
+        continue;
+
+      if (specificOnly && !entry->second->As<WhitelistFilter>() && entry->second->IsGeneric())
+        continue;
+
+      if (!entry->second->Matches(location, typeMask, docDomain, thirdParty, siteKey))
+        continue;
+
+      result.reset(entry->second.get());
+      if (result->As<WhitelistFilter>())
+        return result.release();
+    }
+  }
+
+  for (auto ptr : mUnoptimizedFilters)
+  {
+    if (!ptr)
+      continue;
+
+    if (specificOnly && !ptr->As<WhitelistFilter>() && ptr->IsGeneric())
+      continue;
+
+    if (!ptr->Matches(location, typeMask, docDomain, thirdParty, siteKey))
+      continue;
+
+    result.reset(ptr.get());
+    if (result->As<WhitelistFilter>())
+      return result.release();
+  }
+
+  return result.release();
+}