Issue 5141 - Convert filter match to C++

compiled/filter/Matcher.h

Index: compiled/filter/Matcher.h
===================================================================
new file mode 100644
--- /dev/null
+++ b/compiled/filter/Matcher.h
@@ -0,0 +1,153 @@
+/*
+ * 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/>.
+ */
+
+#pragma once
+
+#include <vector>
+
+#include "../debug.h"
+#include "../bindings/runtime.h"
+#include "../StringMap.h"
+#include "Filter.h"
+
+struct FilterKeyword
+{
+  FilterKeyword()
+  {}
+  FilterKeyword(OwnedString&& keyword, Filter& filter)
+    : mKeyword(std::move(keyword)), mFilter(&filter)
+  {
+  }
+
+  explicit operator const String&() const
+  {
+    return mKeyword;
+  }
+private:
+  OwnedString mKeyword;

[Wladimir Palant, 2017/10/09 08:39:47]

A "keyword" is a substring of a filter text, so it can be a dependent string -
no need for an additional allocation here. Note how we keep a reference to the
filter here, so the filter cannot be garbage collected before the keyword is.

[sergei, 2017/10/09 15:27:53]

The current way of obtaining of the keyword string is actually C++ String -> JS
string -> JS regexp -> JS string -> C++ OwnedString, so it cannot be the
DependentString, so far.

+  FilterPtr mFilter;
+};
+
+class Matcher : public ref_counted
+{
+private:
+  friend class CombinedMatcher;
+  StringMap<std::vector<FilterPtr>> mFilterByKeyword;
+  StringMap<FilterKeyword> mKeywordByFilter;
+  int mReId;
+  int mOptionsReId;
+  int mCandidatesReId;
+  int mMatchReId;
+public:
+  static Matcher* BINDINGS_EXPORTED Create()
+  {
+    return new Matcher;
+  }
+  Matcher();
+  ~Matcher()
+  {
+    DeleteRegExp(mReId);
+    DeleteRegExp(mOptionsReId);
+    DeleteRegExp(mCandidatesReId);
+    DeleteRegExp(mMatchReId);
+  }
+
+  void BINDINGS_EXPORTED Add(Filter&);
+  void BINDINGS_EXPORTED Remove(Filter&);
+  void BINDINGS_EXPORTED Clear() ;
+  bool BINDINGS_EXPORTED HasFilter(const Filter&) const;
+  const String& BINDINGS_EXPORTED GetKeywordForFilter(const Filter& filter) const;
+  Filter* BINDINGS_EXPORTED MatchesAny(const String& location,
+    int typeMask, DependentString& docDomain, bool thirdParty,
+    const String& sitekey, bool specificOnly) const;
+  OwnedString BINDINGS_EXPORTED FindKeyword(const Filter&) const;
+
+private:
+  FilterPtr CheckEntryMatch(const String& keyword,
+    const String& location,
+    int typeMask, DependentString& docDomain, bool thirdParty,
+    const String& sitekey, bool specificOnly) const;
+};
+
+// only needed because StringMap uses DependentString as keys.
+struct CacheEntry
+{
+  CacheEntry()
+  {}
+  CacheEntry(OwnedString&& key, FilterPtr filter)
+    : mKey(std::move(key)), mFilter(filter)
+  {}
+
+  const String& key() const
+  {
+    return mKey;
+  }
+  FilterPtr filter() const
+  {
+    return mFilter;
+  }
+private:
+  OwnedString mKey;
+  FilterPtr mFilter;
+};
+
+class CombinedMatcher : public ref_counted
+{
+private:
+  static const size_t MAX_CACHE_ENTRIES;
+  StringMap<CacheEntry> mResultCache;

[Wladimir Palant, 2017/10/09 08:39:47]

Before we copy the caching approach from the JS code, we should be certain that
caching is still worth doing. At the very least, 1024 cache entries are
definitely pointless, a small circular buffer (8 entries?) should do the job if
necessary - this would also make concatenating strings unnecessary.

[sergei, 2017/10/09 15:27:53]

It seems not trivial because it requires at least certain measurements to
estimate whether that caching is still worth, and it also depends on the actual
implementation (the proposed Rabin-Karp is not implemented yet, maybe we could
even use a modified version of the Bloom filter) and its tweaks. So, could you
please file a separate issue for the evaluation and proper implementation in
case of necessity of the caching here?
Taking into account that a single visit of a web-page results in at least around
100 requests thus ~100 calls of the "MatchesAny" method with different
parameters and that the cache likely has a hit on the second visit of the same
web site, it seems that the size of cache should be rather at least 100. If it's
a circular buffer with a dozen of entries then they will be never hit. So, the
cache with ~1000 entries looks reasonable.

The cache structure should indeed behave like circular buffer, but there is no
such functionality yet, so I would propose to keep the current approach and
change it in another commit. I would rather encapsulate the combined matcher in
a caching matcher and keep the interface in order to simplify possible usage and
profiling of the matcher with different caching approaches and without any
caching, but for the present it's fine.

[Wladimir Palant, 2017/10/10 07:39:05]

You are getting it backwards. The caching shouldn't be implemented here in the
first place. We need a separate issue for evaluating the necessity of caching
and implementing it if necessary.
That's unlikely. A cache needs to introduce less overhead due to storing values
and lookups than one saves by not redoing certain calculations. With a
sufficiently efficient matching algorithm (and that's what we are aiming for
here), caching results between different requests shouldn't be worth it. The
cache should only be useful if a website requests the same resource all the time
in quick succession.

+  Matcher mBlacklist;
+  Matcher mWhitelist;
+  int mMatchReId;
+
+public:
+  static CombinedMatcher* BINDINGS_EXPORTED Create()
+  {
+    return new CombinedMatcher;
+  }
+
+  BINDINGS_EXPORTED CombinedMatcher();
+  ~CombinedMatcher()
+  {
+    DeleteRegExp(mMatchReId);
+  }
+
+  void BINDINGS_EXPORTED Add(Filter& filter);
+  void BINDINGS_EXPORTED Remove(Filter& filter);
+  void BINDINGS_EXPORTED Clear();
+  bool BINDINGS_EXPORTED HasFilter(const Filter& filter) const;
+  const String& BINDINGS_EXPORTED GetKeywordForFilter(const Filter& filter) const;
+  Filter* BINDINGS_EXPORTED MatchesAny(const String& location,
+    int typeMask, DependentString& docDomain, bool thirdParty,
+    const String& sitekey, bool specificOnly);
+  OwnedString BINDINGS_EXPORTED FindKeyword(const Filter& filter) const;
+
+private:
+  Matcher& GetMatcher(const Filter& filter)
+  {
+    return filter.mType == Filter::Type::WHITELIST ? mWhitelist : mBlacklist;
+  }
+  const Matcher& GetMatcher(const Filter& filter) const
+  {
+    return filter.mType == Filter::Type::WHITELIST ? mWhitelist : mBlacklist;
+  }
+  void ResetCache();
+  FilterPtr MatchesAnyInternal(const String& location,
+    int typeMask, DependentString& docDomain, bool thirdParty,
+    const String& sitekey, bool specificOnly) const;
+};
+