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"
 
 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()] = keyword;
+  mKeywordByFilter[filter.GetText()] =
+    FilterKeyword(std::move(keyword), filter);
 }
 
 void Matcher::Remove(Filter& filter)
 {
   auto entry = mKeywordByFilter.find(filter.GetText());
   if (!entry)
     return;
 
-  auto keyword = entry->second;
+  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 entry->second;
+    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
 {
-  auto re_id = GenerateRegExp(u"[a-z0-9%]{3,}"_str, true, true);
   OwnedString text(location);
   text.toLower();
   intrusive_ptr<ReMatchResults> reResult(new ReMatchResults, false);
-  MatchRegExp(re_id, text, reResult.get());
-  auto& candidates = reResult->candidates;
-  candidates.push_back(OwnedString());
-  for (auto substr : candidates)
-  {
-    if (mFilterByKeyword.find(substr))
+  if (text.match(mMatchReId, *reResult))
+  {
+    auto& candidates = reResult->candidates;
+    candidates.push_back(OwnedString());
+    for (auto candidate : candidates)
     {
-      auto result = CheckEntryMatch(substr, location, typeMask, docDomain,
+      auto result = CheckEntryMatch(candidate, location, typeMask, docDomain,
                                     thirdParty, sitekey, specificOnly);
       if (result)
         return result.release();
     }
   }

[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(u""_str);
+  OwnedString result;
   OwnedString text(filter.GetText());
-  auto re_id = GenerateRegExp(regexpRegExp, true, false);
-  if (TestRegExp(re_id, text))
+  if (TestRegExp(mReId, text))
     return result;
 
   // Remove options
-  auto options_re_id = GenerateRegExp(optionsRegExp, true, false);
-  auto index = ExecRegExp(options_re_id, text);
+  auto index = ExecRegExp(mOptionsReId, text);
   if (index != String::npos)
-    text = text.substr(0, index);
+    text = DependentString(text, 0, index);
 
   // Remove whitelist marker
   if (text.length() >= 2 && text[0] == '@' && text[1] == '@')
-    text = text.substr(2);
+    text = DependentString(text, 2);
 
   text.toLower();
   intrusive_ptr<ReMatchResults> keywords(new ReMatchResults, false);
-  auto candidates_re_id = GenerateRegExp(candidateRegExp, true, true);
-  auto match = text.match(candidates_re_id, keywords.get());
+  auto match = text.match(mCandidatesReId, *keywords);
   if (!match)
     return result;
 
   auto& candidates = keywords->candidates;
 
-  auto& hash = mFilterByKeyword;
-  uint32_t resultCount = 0xffffffff;
+  uint32_t resultCount = 0xffffff;
   uint32_t resultLength = 0;
   for (auto substr : candidates)
   {
     if (substr.empty())
       continue;
 
-    auto candidate = substr.substr(1);
-    auto entry = hash.find(candidate);
+    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;
 }
 
 FilterPtr Matcher::CheckEntryMatch(const String& keyword,
   const String& location,
   int typeMask, DependentString& docDomain, bool thirdParty,
   const String& sitekey, bool specificOnly) const
 {
   auto entry = mFilterByKeyword.find(keyword);
-  if (entry)
-  {

[sergei, 2017/10/04 08:54:33]

Earlier return would be better here, in my opinion.

[hub, 2017/10/06 13:49:19]

Done.

-    auto list = entry->second;
-    for (auto filter : list)
-    {
-      auto activeFilter = static_cast<ActiveFilter*>(filter.get());
-      if (specificOnly && activeFilter->IsGeneric() &&
-          !(activeFilter->mType != Filter::Type::WHITELIST))
-        continue;
-
-      auto reFilter = static_cast<RegExpFilter*>(activeFilter);
-      if (reFilter->Matches(location, typeMask, docDomain, thirdParty, sitekey))
-        return filter;
-    }
-  }
+  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))
+      continue;
+
+    auto reFilter = static_cast<RegExpFilter*>(activeFilter);
+    if (reFilter->Matches(location, typeMask, docDomain, thirdParty, sitekey))
+      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)
 {
-  if (filter.mType == Filter::Type::WHITELIST)
-    mWhitelist.Add(filter);
-  else
-    mBlacklist.Add(filter);
-
+  GetMatcher(filter).Add(filter);
   ResetCache();
 }
 
 void CombinedMatcher::Remove(Filter& filter)
 {
-  if (filter.mType == Filter::Type::WHITELIST)
-    mWhitelist.Remove(filter);
-  else
-    mBlacklist.Remove(filter);
-
+  GetMatcher(filter).Remove(filter);
   ResetCache();
 }
 
 void CombinedMatcher::Clear()
 {
   mBlacklist.Clear();
   mWhitelist.Clear();
   ResetCache();
 }
 
 bool CombinedMatcher::HasFilter(const Filter& filter) const
 {
-  return filter.mType == Filter::Type::WHITELIST ?
-    mWhitelist.HasFilter(filter) : mBlacklist.HasFilter(filter);
+  return GetMatcher(filter).HasFilter(filter);
 }
 
 const String& CombinedMatcher::GetKeywordForFilter(const Filter& filter) const
 {
-  return filter.mType == Filter::Type::WHITELIST ?
-    mWhitelist.GetKeywordForFilter(filter) : mBlacklist.GetKeywordForFilter(filter);
+  return GetMatcher(filter).GetKeywordForFilter(filter);
 }
 
 Filter* CombinedMatcher::MatchesAny(const String& location,
   int typeMask, DependentString& docDomain, bool thirdParty,
   const String& sitekey, bool specificOnly)
 {
   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;
+    result = cachedResult->second.filter();
   else
   {
     result = MatchesAnyInternal(location, typeMask, docDomain,
                                 thirdParty, sitekey, specificOnly);
 
     if (mResultCache.size() >= MAX_CACHE_ENTRIES)
       ResetCache();
 
-    mResultCache[key] = result;
+    CacheEntry cache(std::move(key), result);
+    mResultCache[cache.key()] = cache;
   }
 
   return result.release();
 }
 
 OwnedString CombinedMatcher::FindKeyword(const Filter& filter) const
 {
-  return filter.mType == Filter::Type::WHITELIST ?
-    mWhitelist.FindKeyword(filter) : mBlacklist.FindKeyword(filter);
+  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();
-  auto match_re_id = GenerateRegExp(u"[a-z0-9%]{3,}"_str, true, true);
   intrusive_ptr<ReMatchResults> reResult(new ReMatchResults, false);
-  text.match(match_re_id, reResult.get());
+  text.match(mMatchReId, *reResult);
 
   auto& candidates = reResult->candidates;
   candidates.push_back(OwnedString());
 
   FilterPtr blacklistHit;
   for (auto substr : candidates)
   {
     auto result = mWhitelist.CheckEntryMatch(
-      substr, location, typeMask, docDomain, thirdParty, sitekey, specificOnly);
+      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;
 }