Issue 5141 - Convert filter match to C++

compiled/filter/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 "RegExpFilter.h"
 #include "../library.h"
 
-class CombinedMatcher : public MatcherBase
-{
-private:
-  StringMap<Filter*> mResultCache;
-  static const size_t MAX_CACHE_ENTRIES = 1000;
-  int mMatchReId;
-  Matcher mBlacklist;
-  Matcher mWhitelist;
-
-protected:
-  OwnedString FindKeyword(const FilterPtr& filter) override
-  {
-    if (filter->mType == Filter::Type::WHITELIST)
-      return mWhitelist.FindKeyword(filter);
-    return mBlacklist.FindKeyword(filter);
-  }
-
-public:
-  CombinedMatcher()
-    : mMatchReId(GenerateRegExp(u"[a-z0-9%]{3,}"_str, true, true))
-  {
-  }
-
-  ~CombinedMatcher()
-  {
-    DeleteRegExp(mMatchReId);
-  }
-
-  void ResetCache()
-  {
-    for (auto filter : mResultCache)
-      filter.second->ReleaseRef();
-    mResultCache.clear();
-  }
-
-  void Add(const FilterPtr& filter) override
-  {
-    if (filter->mType == Filter::Type::WHITELIST)
-      mWhitelist.Add(filter);
-    else
-      mBlacklist.Add(filter);
-
-    ResetCache();
-  }
-
-  void Remove(const FilterPtr& filter) override
-  {
-    if (filter->mType == Filter::Type::WHITELIST)
-      mWhitelist.Remove(filter);
-    else
-      mBlacklist.Remove(filter);
-
-    ResetCache();
-  }
-
-  void Clear() override
-  {
-    mBlacklist.Clear();
-    mWhitelist.Clear();
-    ResetCache();
-  }
-
-  bool HasFilter(const FilterPtr& filter) const override
-  {
-    if (filter->mType == Filter::Type::WHITELIST)
-      return mWhitelist.HasFilter(filter);
-    return mBlacklist.HasFilter(filter);
-  }
-
-  const String& GetKeywordForFilter(const FilterPtr& filter) override
-  {
-    if (filter->mType == Filter::Type::WHITELIST)
-      return mWhitelist.GetKeywordForFilter(filter);
-    return mBlacklist.GetKeywordForFilter(filter);
-  }
-
-private:
-  Filter* MatchesAnyInternal(const String& location,
-    int typeMask, DependentString& docDomain, bool thirdParty,
-    const String& sitekey, bool specificOnly)
-  {
-    ReMatchResults reResult;
-    OwnedString text(location);
-    text.toLower();
-    text.match(mMatchReId, &reResult);
-
-    auto& candidates = reResult.candidates;
+namespace {
+  const DependentString regexpRegExp =
+    u"^(@@)?/.*/(?:\\$~?[\\w-]+(?:=[^,\\s]+)?(?:,~?[\\w-]+(?:=[^,\\s]+)?)*)?$"_str;
+  const DependentString optionsRegExp =
+    u"\\$(~?[\\w-]+(?:=[^,\\s]+)?(?:,~?[\\w-]+(?:=[^,\\s]+)?)*)$"_str;
+  const DependentString candidateRegExp =
+    u"[^a-z0-9%*][a-z0-9%]{3,}(?=[^a-z0-9%*])"_str;
+  const DependentString matchRegExp = u"[a-z0-9%]{3,}"_str;
+}
+
+Matcher::Matcher()
+  : mFilterByKeyword(1024), mKeywordByFilter(1024),
+    mReId(-1), mOptionsReId(-1), mCandidatesReId(-1)
+{
+  mReId = GenerateRegExp(regexpRegExp, true, false);
+  mOptionsReId = GenerateRegExp(optionsRegExp, true, false);
+  mCandidatesReId = GenerateRegExp(candidateRegExp, true, true);
+  mMatchReId = GenerateRegExp(matchRegExp, true, true);
+}
+
+void Matcher::Add(Filter& filter)
+{
+  if (mKeywordByFilter.find(filter.GetText()))
+    return;
+
+  auto keyword = FindKeyword(filter);
+
+  mFilterByKeyword[keyword].push_back(FilterPtr(&filter));

[sergei, 2017/10/11 09:55:16]

Although the review is already closed I think it's important to let everyone
know that here is a bug in this line to avoid it in a future.
The type of key of StringMap is DependentString, the type of keyword is
OwnedString, so after exiting of the scope of this method the stored
DependentString points to a removed string.

+  mKeywordByFilter[filter.GetText()] =
+    FilterKeyword(std::move(keyword), filter);
+}
+
+void Matcher::Remove(Filter& filter)
+{
+  auto entry = mKeywordByFilter.find(filter.GetText());
+  if (!entry)
+    return;
+
+  auto& keyword = static_cast<const String&>(entry->second);
+  auto list = mFilterByKeyword[keyword];
+  if (list.size() == 1)
+    mFilterByKeyword.erase(keyword);
+  else
+    list.erase(std::find(list.cbegin(), list.cend(), FilterPtr(&filter)));
+
+  mKeywordByFilter.erase(filter.GetText());
+}
+
+void Matcher::Clear()
+{
+  mFilterByKeyword.clear();
+  mKeywordByFilter.clear();
+}
+
+bool Matcher::HasFilter(const Filter& filter) const
+{
+  return mKeywordByFilter.find(filter.GetText());
+}
+
+namespace
+{
+  DependentString emptyString = u""_str;
+}
+
+const String& Matcher::GetKeywordForFilter(const Filter& filter) const
+{
+  auto entry = mKeywordByFilter.find(filter.GetText());
+  if (entry)
+    return static_cast<const String&>(entry->second);
+  return emptyString;
+}
+
+Filter* Matcher::MatchesAny(const String& location,
+  int typeMask, DependentString& docDomain, bool thirdParty,
+  const String& sitekey, bool specificOnly) const
+{
+  OwnedString text(location);
+  text.toLower();
+  intrusive_ptr<ReMatchResults> reResult(new ReMatchResults, false);
+  if (text.match(mMatchReId, *reResult))
+  {
+    auto& candidates = reResult->candidates;
     candidates.push_back(OwnedString());
-
-    Filter* blacklistHit = nullptr;
-    for (auto substr : candidates)
+    for (auto candidate : candidates)
     {
-      if (mWhitelist.mFilterByKeyword.find(substr))
-      {
-        auto result = mWhitelist.CheckEntryMatch(
-          substr, location, typeMask, docDomain, thirdParty, sitekey, specificOnly);
-        if (result)
-          return result;
-      }
-      if (mBlacklist.mFilterByKeyword.find(substr) && !blacklistHit)
-      {
-        blacklistHit = mBlacklist.CheckEntryMatch(
-          substr, location, typeMask, docDomain, thirdParty, sitekey,
-          specificOnly);
-      }
+      auto result = CheckEntryMatch(candidate, location, typeMask, docDomain,
+                                    thirdParty, sitekey, specificOnly);
+      if (result)
+        return result.release();
     }
-    return blacklistHit;
-  }
-
-public:
-  Filter* MatchesAny(const String& location,
-    int typeMask, DependentString& docDomain, bool thirdParty,
-    const String& sitekey, bool specificOnly) override
-  {
-    OwnedString key(location);
-    key.append(u" "_str);
-    key.append(typeMask);
-    key.append(u" "_str);
-    key.append(docDomain);
-    key.append(u" "_str);
-    key.append(thirdParty);
-    key.append(u" "_str);
-    key.append(sitekey);
-    key.append(u" "_str);
-    key.append(specificOnly);
-
-    auto cachedResult = mResultCache.find(key);
-    if (cachedResult)
-    {
-      cachedResult->second->AddRef();
-      return cachedResult->second;
-    }
-
-    Filter* result = MatchesAnyInternal(location, typeMask, docDomain,
-                                          thirdParty, sitekey, specificOnly);
-
-    if (mResultCache.size() >= MAX_CACHE_ENTRIES)
-      ResetCache();
-
-    result->AddRef();
-    mResultCache[key] = result;
-
-    result->AddRef();
-    return result;
-  }
-};
-
-MatcherBase* MatcherBase::mInstance = new CombinedMatcher;
-
-Matcher::Matcher()
-  : mFilterReId(GenerateRegExp(DependentString(Filter::regexpRegExp), true, false))
-  , mOptionsReId(GenerateRegExp(DependentString(Filter::optionsRegExp), true, false))
-  , mCandidatesReId(GenerateRegExp(u"[^a-z0-9%*][a-z0-9%]{3,}(?=[^a-z0-9%*])"_str, true, true))
-{
-}
-
-Matcher::~Matcher()
-{
-  DeleteRegExp(mFilterReId);
-  DeleteRegExp(mOptionsReId);
-  DeleteRegExp(mCandidatesReId);
-}
-
-OwnedString Matcher::FindKeyword(const FilterPtr& filter)
-{
-  OwnedString result(u""_str);
-  OwnedString text(filter->GetText());
-  if (TestRegExp(mFilterReId, text))
+  }

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

As mentioned in the issue description, we should not reuse the algorithm
currently implemented in JavaScript - we only chose that one because it would
run efficiently in JavaScript. C++ allows using better algorithms however, with
Rabin-Karp most likely being the best choice here.

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

Although it merely converts the existing JS code and approaches to C++, I would
like to have it landed because of the following reasons. It already provides
with the C++ API of the matcher and corresponding tests, though in JS. We know
that the existing approach does work in JS, so it should work in C++ and should
not show worse results (I'm actually afraid of a lot of C++<>JS string
conversions, but anyway it should work). Having it in C++ now will allow to
compare the performance (speed and especially the memory usage) of the existing
approach and a new one later. This change is already pretty huge and the change
of only the implementation, which is BTW pretty well localized, especially
involving some algorithmic work, is better to review and commit separately. BTW,
right now some dependencies required to implement the proposed approach are
missing and there are actually some questions.

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

I strongly disagree. Landing crappy code is always a bad idea. Landing crappy
code that actually works is even worse, because nobody will have a strong
incentive to replace it once it landed, and it will stay around as a maintenance
burden way too long. As it is now, this code is way too complicated  for the job
that it is doing. It also overspends memory, introduces unnecessary allocations
and wastes performance for no good reason on every corner. Comparing
well-optimized JavaScript code with badly optimized C++ code is *not* useful.
The matcher is where we can really make a difference performance-wise, but not
with this approach. I can tell you already that the overhead introduced here
will make this code perform considerably worse than our current JavaScript code.

+  return nullptr;
+}
+
+OwnedString Matcher::FindKeyword(const Filter& filter) const
+{
+  OwnedString result;
+  OwnedString text(filter.GetText());
+  if (TestRegExp(mReId, text))
     return result;
 
   // Remove options
   auto index = ExecRegExp(mOptionsReId, text);
-  if (index != -1)
-    text = text.substr(0, index);
+  if (index != String::npos)
+    text = DependentString(text, 0, index);
 
   // Remove whitelist marker
-  if (text[0] == '@' && text[1] == '@')
-    text = text.substr(2);
+  if (text.length() >= 2 && text[0] == '@' && text[1] == '@')
+    text = DependentString(text, 2);
 
   text.toLower();
-  ReMatchResults keywords;
-  auto match = text.match(mCandidatesReId, &keywords);
+  intrusive_ptr<ReMatchResults> keywords(new ReMatchResults, false);
+  auto match = text.match(mCandidatesReId, *keywords);
   if (!match)
     return result;
 
-  auto& candidates = keywords.candidates;
-
-  auto& hash = mFilterByKeyword;
-  uint32_t resultCount = 0xffffffff;
+  auto& candidates = keywords->candidates;
+
+  uint32_t resultCount = 0xffffff;
   uint32_t resultLength = 0;
   for (auto substr : candidates)
   {
-    auto candidate = DependentString(substr).substr(1);
-    auto count = (hash.find(candidate) ? hash[candidate].size() : 0);
+    if (substr.empty())
+      continue;
+
+    auto candidate = DependentString(substr, 1);
+    auto entry = mFilterByKeyword.find(candidate);
+    auto count = entry ? entry->second.size() : 0;
     if (count < resultCount ||
       (count == resultCount && candidate.length() > resultLength))
     {
       result = candidate;
       resultCount = count;
       resultLength = candidate.length();
     }
   }
-
   return result;
 }
 
-void Matcher::Add(const FilterPtr& filter)
-{
-  if (mKeywordByFilter.find(filter->GetText()))
-    return;
-
-  auto keyword = FindKeyword(filter);
-  auto oldEntry = mFilterByKeyword.find(keyword);
-  if (!oldEntry)
-    mFilterByKeyword[keyword] = std::vector<FilterPtr>{filter};
-  else
-    mFilterByKeyword[keyword].push_back(filter);
-  mKeywordByFilter[filter->GetText()] = keyword;
-}
-
-void Matcher::Remove(const FilterPtr& filter)
-{
-  if (!mKeywordByFilter.find(filter->GetText()))
-    return;
-
-  auto keyword = mKeywordByFilter[filter->GetText()];
-  auto list = mFilterByKeyword[keyword];
-  if (list.size() == 1)
-    mFilterByKeyword.erase(keyword);
-  else
-  {
-    auto iter = std::find(list.cbegin(), list.cend(), filter);
-    list.erase(iter);
-  }
-  mKeywordByFilter.erase(filter->GetText());
-}
-
-void Matcher::Clear()
-{
-  mFilterByKeyword.clear();
-  mKeywordByFilter.clear();
-}
-
-bool Matcher::HasFilter(const FilterPtr& filter) const
-{
-  return mKeywordByFilter.find(filter->GetText());
-}
-
-static DependentString emptyString = u""_str;
-
-const String& Matcher::GetKeywordForFilter(const FilterPtr& filter)
-{
-  if (mKeywordByFilter.find(filter->GetText()))
-    return mKeywordByFilter[filter->GetText()];
-  return emptyString;
-}
-
-Filter* Matcher::CheckEntryMatch(const String& keyword,
+FilterPtr Matcher::CheckEntryMatch(const String& keyword,
   const String& location,
   int typeMask, DependentString& docDomain, bool thirdParty,
-  const String& sitekey, bool specificOnly)
-{
-  auto list = mFilterByKeyword[keyword];
-  for (auto filter : list) {
+  const String& sitekey, bool specificOnly) const
+{
+  auto entry = mFilterByKeyword.find(keyword);
+  if (!entry)
+    return FilterPtr();
+
+  auto filters = entry->second;
+  for (auto filter : filters)
+  {
     auto activeFilter = static_cast<ActiveFilter*>(filter.get());
     if (specificOnly && activeFilter->IsGeneric() &&
-        !(activeFilter->mType != Filter::Type::WHITELIST))
+        (activeFilter->mType != Filter::Type::WHITELIST))
       continue;
 
     auto reFilter = static_cast<RegExpFilter*>(activeFilter);
     if (reFilter->Matches(location, typeMask, docDomain, thirdParty, sitekey))
-      return filter.get();
-  }
-  return nullptr;
-}
-
-Filter* Matcher::MatchesAny(const String& location,
+      return filter;
+  }
+
+  return FilterPtr();
+}
+
+const size_t CombinedMatcher::MAX_CACHE_ENTRIES = 1000;
+
+CombinedMatcher::CombinedMatcher()
+  : mResultCache(1024), mMatchReId(-1)
+{
+  mMatchReId = GenerateRegExp(matchRegExp, true, true);
+}
+
+void CombinedMatcher::Add(Filter& filter)
+{
+  GetMatcher(filter).Add(filter);
+  ResetCache();
+}
+
+void CombinedMatcher::Remove(Filter& filter)
+{
+  GetMatcher(filter).Remove(filter);
+  ResetCache();
+}
+
+void CombinedMatcher::Clear()
+{
+  mBlacklist.Clear();
+  mWhitelist.Clear();
+  ResetCache();
+}
+
+bool CombinedMatcher::HasFilter(const Filter& filter) const
+{
+  return GetMatcher(filter).HasFilter(filter);
+}
+
+const String& CombinedMatcher::GetKeywordForFilter(const Filter& filter) const
+{
+  return GetMatcher(filter).GetKeywordForFilter(filter);
+}
+
+Filter* CombinedMatcher::MatchesAny(const String& location,
   int typeMask, DependentString& docDomain, bool thirdParty,
   const String& sitekey, bool specificOnly)
 {
-  ReMatchResults reResult;
-  auto re_id = GenerateRegExp(u"[a-z0-9%]{3,}"_str, true, true);
+  OwnedString key(location);
+  key.append(u" "_str);
+  key.append(typeMask);
+  key.append(u" "_str);
+  key.append(docDomain);
+  key.append(u" "_str);
+  key.append(thirdParty);
+  key.append(u" "_str);
+  key.append(sitekey);
+  key.append(u" "_str);
+  key.append(specificOnly);
+
+  FilterPtr result;
+
+  auto cachedResult = mResultCache.find(key);
+  if (cachedResult)
+    result = cachedResult->second.filter();
+  else
+  {
+    result = MatchesAnyInternal(location, typeMask, docDomain,
+                                thirdParty, sitekey, specificOnly);
+
+    if (mResultCache.size() >= MAX_CACHE_ENTRIES)
+      ResetCache();
+
+    CacheEntry cache(std::move(key), result);
+    mResultCache[cache.key()] = cache;
+  }
+
+  return result.release();
+}
+
+OwnedString CombinedMatcher::FindKeyword(const Filter& filter) const
+{
+  return GetMatcher(filter).FindKeyword(filter);
+}
+
+void CombinedMatcher::ResetCache()
+{
+  mResultCache.clear();
+}
+
+FilterPtr CombinedMatcher::MatchesAnyInternal(const String& location,
+  int typeMask, DependentString& docDomain, bool thirdParty,
+  const String& sitekey, bool specificOnly) const
+{
   OwnedString text(location);
   text.toLower();
-  MatchRegExp(re_id, text, &reResult);
-  auto& candidates = reResult.candidates;
+  intrusive_ptr<ReMatchResults> reResult(new ReMatchResults, false);
+  text.match(mMatchReId, *reResult);
+
+  auto& candidates = reResult->candidates;
   candidates.push_back(OwnedString());
+
+  FilterPtr blacklistHit;
   for (auto substr : candidates)
-    if (mFilterByKeyword.find(substr))
-    {
-      auto result = CheckEntryMatch(substr, location, typeMask, docDomain, 
-                                    thirdParty, sitekey, specificOnly);
-      if (result)
-      {
-        result->AddRef();
-        return result;
-      }
-    }
-
-  return nullptr;
-}
+  {
+    auto result = mWhitelist.CheckEntryMatch(
+      substr, location, typeMask, docDomain, thirdParty, sitekey, false);
+    if (result)
+      return result;
+
+    if (!blacklistHit)
+      blacklistHit = mBlacklist.CheckEntryMatch(
+        substr, location, typeMask, docDomain, thirdParty, sitekey,
+        specificOnly);
+  }
+  return blacklistHit;
+}