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"
 
-const size_t CombinedMatcher::MAX_CACHE_ENTRIES = 1000;
-
-OwnedString CombinedMatcher::FindKeyword(const FilterPtr& filter)

[sergei, 2017/10/02 12:02:35]

It's not important but still it would be better to keep the order more or less
similar to the order in the headers, at least for classes, firstly Matcher and
then CombinedMatcher.

[sergei, 2017/10/02 12:02:36]

the method should be const.

[hub, 2017/10/03 19:33:13]

Done.

[hub, 2017/10/03 19:33:13]

Done.

-{
-  if (filter->mType == Filter::Type::WHITELIST)

[sergei, 2017/10/02 12:02:33]

What do you think about having an inline function
Matcher& CombinedMatcher::GetMatcher(const Filter& filter)
{
  return filter.mType == Filter::Type::WHITELIST ? mWhitelist : mBlacklist;
}
and using of it everywhere below?

[hub, 2017/10/03 19:33:11]

Done.

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

I meant that the code of CombinedMatcher::SomeMethod(Filter& filter) would be
{
  return GetMatcher(filter).SomeMethod(filter).
}

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

Done.

-    return mWhitelist.FindKeyword(filter);
-  return mBlacklist.FindKeyword(filter);
-}
-
-void CombinedMatcher::ResetCache()
-{
-  mResultCache.clear();
-}
-
-void CombinedMatcher::Add(const FilterPtr& filter)

[sergei, 2017/10/02 12:02:36]

Should the argument be `Filter&`?

[hub, 2017/10/03 19:33:11]

Done.

-{
-  if (filter->mType == Filter::Type::WHITELIST)
-    mWhitelist.Add(filter);
-  else
-    mBlacklist.Add(filter);
-
-  ResetCache();
-}
-
-void CombinedMatcher::Remove(const FilterPtr& filter)

[sergei, 2017/10/02 12:02:37]

Should the argument be `const Filter&`?

[hub, 2017/10/03 19:33:09]

Done.

-{
-  if (filter->mType == Filter::Type::WHITELIST)
-    mWhitelist.Remove(filter);
-  else
-    mBlacklist.Remove(filter);
-
-  ResetCache();
-}
-
-void CombinedMatcher::Clear()
-{
-  mBlacklist.Clear();
-  mWhitelist.Clear();
-  ResetCache();
-}
-
-bool CombinedMatcher::HasFilter(const FilterPtr& filter) const

[sergei, 2017/10/02 12:02:34]

Should the argument be `const Filter&`?

[hub, 2017/10/03 19:33:11]

Done.

-{
-  if (filter->mType == Filter::Type::WHITELIST)
-    return mWhitelist.HasFilter(filter);
-  return mBlacklist.HasFilter(filter);
-}
-
-const String& CombinedMatcher::GetKeywordForFilter(const FilterPtr& filter)

[sergei, 2017/10/02 12:02:35]

Should the argument be `const Filter&`?

[sergei, 2017/10/02 12:02:36]

the method should be const.

[hub, 2017/10/03 19:33:11]

Done.

[hub, 2017/10/03 19:33:12]

Done.

-{
-  if (filter->mType == Filter::Type::WHITELIST)
-    return mWhitelist.GetKeywordForFilter(filter);
-  return mBlacklist.GetKeywordForFilter(filter);
-}
-
-FilterPtr CombinedMatcher::MatchesAnyInternal(const String& location,

[sergei, 2017/10/02 12:02:34]

the method should be const if it's possible.

[hub, 2017/10/03 19:33:10]

Done.

-  int typeMask, DependentString& docDomain, bool thirdParty,
-  const String& sitekey, bool specificOnly)
-{
-  ReMatchResults reResult;
-  OwnedString text(location);
-  text.toLower();
-  auto match_re_id = GenerateRegExp(u"[a-z0-9%]{3,}"_str, true, true);

[sergei, 2017/10/02 12:02:36]

It should be in anonymous namespace, otherwise a new regexp is generated on each
call of the method, isn't it?

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

This is not addressed.

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

Done.

-  text.match(match_re_id, &reResult);

[sergei, 2017/10/02 12:02:35]

Although it seems it does work here, I think for present we should avoid
instantiation of ref_counted on the stack, therefore I would recommend to use
intrusive_ptr<ReMatchResults> and pass a pointer to the object on heap to
text.match.
However, I'm fine if a third opinion is to keep it on the stack in this
particular case.

[hub, 2017/10/03 19:33:12]

Done.

-
-  auto& candidates = reResult.candidates;
-  candidates.push_back(OwnedString());
-
-  FilterPtr blacklistHit;
-  for (auto substr : candidates)
-  {
-    if (mWhitelist.mFilterByKeyword.find(substr))

[sergei, 2017/10/02 12:02:36]

It's already changed in the master, do you mind to change it here accordingly?

[hub, 2017/10/03 19:33:13]

Done.

-    {
-      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);
-    }
-  }
-  return blacklistHit;
-}
-
-Filter* CombinedMatcher::MatchesAny(const String& location,
-  int typeMask, DependentString& docDomain, bool thirdParty,
-  const String& sitekey, bool specificOnly)

[sergei, 2017/10/02 12:02:34]

The method should be const if it's possible.

[hub, 2017/10/03 19:33:11]

sadly the use of the cache makes it non-const. I could eventually mark
mResultCache as mutable.

-{
-  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;
-  else
-  {
-    result = MatchesAnyInternal(location, typeMask, docDomain,
-                                thirdParty, sitekey, specificOnly);
-
-    if (mResultCache.size() >= MAX_CACHE_ENTRIES)
-      ResetCache();
-
-    mResultCache[key] = result;
-  }
-
-  result->AddRef();
-  return result.get();

[sergei, 2017/10/02 12:02:34]

It would be better to `return result.release();`.

[hub, 2017/10/03 19:33:10]

Done.

-}
-
 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;
-}
-
-OwnedString Matcher::FindKeyword(const FilterPtr& filter)

[sergei, 2017/10/02 12:02:34]

Should the argument be `const Filter&`?

[sergei, 2017/10/02 12:02:36]

should it be a const method?

[hub, 2017/10/03 19:33:11]

Done.

[hub, 2017/10/03 19:33:12]

Done.

-{
-  OwnedString result(u""_str);
-  OwnedString text(filter->GetText());
-  auto re_id = GenerateRegExp(DependentString(regexpRegExp), true, false);

[sergei, 2017/10/02 12:02:37]

It and all other regexps below should be in the anonymous namespace because we
should not create them on each call of the current method.

[hub, 2017/10/03 19:33:14]

The mistake here is that a create a new DependentString from a
DependentString().

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

Each call of GenerateRegExp increases global _regexp_counter and calls
`_regexp_data[id] = new RegExp(readString(source), flag);`, so it creates a new
regexp each time and stores it in _regexp_data, it's a sort of memory leak.

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

Done.

-  if (TestRegExp(re_id, text))
+  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());
+    for (auto candidate : candidates)
+    {
+      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;
+  OwnedString text(filter.GetText());
+  if (TestRegExp(mReId, text))
     return result;
 
   // Remove options
-  auto options_re_id = GenerateRegExp(DependentString(optionsRegExp), true, false);
-  auto index = ExecRegExp(options_re_id, text);
-  if (index != -1)

[sergei, 2017/10/02 12:02:34]

It would be better to use String::npos than -1.

[hub, 2017/10/03 19:33:13]

Done.

-    text = text.substr(0, index);
+  auto index = ExecRegExp(mOptionsReId, text);
+  if (index != String::npos)
+    text = DependentString(text, 0, index);
 
   // Remove whitelist marker
-  if (text[0] == '@' && text[1] == '@')

[sergei, 2017/10/02 12:02:37]

Firstly we should check the length of the `text`.

[hub, 2017/10/03 19:33:11]

Done.

-    text = text.substr(2);
+  if (text.length() >= 2 && text[0] == '@' && text[1] == '@')
+    text = DependentString(text, 2);
 
   text.toLower();
-  ReMatchResults keywords;
-  auto candidates_re_id = GenerateRegExp(candidateRegExp, true, true);
-  auto match = text.match(candidates_re_id, &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);

[sergei, 2017/10/02 12:02:35]

Basically braces are not needed here.

[sergei, 2017/10/02 12:02:37]

It seems it could be optimized by
auto ii_hash = hash.find(candidate);
auto count = ii_hash ? ii_hash->second->size() : 0;

[hub, 2017/10/03 19:33:12]

I have to do that for to make the function `const` since StringMap<>::operator[]
isn't.

[hub, 2017/10/03 19:33:13]

Done.

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

It's just a side effect of the present code, there could be a const version of
StringMap<>::operator[], the optimization is in the elimination of the double
look up, firstly in find and secondly in operator[].

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

I addressed that. Just as I said making this const prevent from using operator[]
which is gone at that point.
I don't see a reasonable way to implement operator[] on a const.

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

[sergei, 2017/10/02 12:02:36]

What about passing `Filter&`?

[hub, 2017/10/03 19:33:10]

Done.

-{
-  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);

[sergei, 2017/10/02 12:02:37]

StringMap::operator[](const String& key) creates an entry if it does not exists,
so, it seems more efficient to be just
mFilterByKeyword[keyword].push_back(filter);

[hub, 2017/10/03 19:33:09]

Done.

-  mKeywordByFilter[filter->GetText()] = keyword;

[sergei, 2017/10/02 12:02:34]

mKeywordByFilter stores DependentString, what if the `filter` is deleted?
I would not like to rely on the fact that we can remove the entry when a filter
is removed, I would prefer to have something more reliable. BTW, in the current
master the filter object is used as a key, I wonder whether it's somehow
possible here as well.
For instance without digging into a new hash structure, I can propose a bit
hacky approach by replacing `first` member of the StringMapEntry by a getter and
probably extending it with is_invalid and having hash object storing FilterPtr
and using its text property to calculate the hash. It all will be based on
templates and all methods are inlined, so there should not be any degradation or
difference in the compiled code for already existing `StringMap`s. I think we
should try it in a separate codereview.

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

What about having some
struct FilterKeyword
{
  FilterKeyword(OwnedString&& keyword, Filter& filter)
  : keyword(std::move(keyword)), filter(&filter)
  {}
  explicit operator const String&() const
  {
    return keyword;
  }
private:
  OwnedString keyword;
  FilterPtr filter;
}

and declaring StringMap<FilterKeyword> mKeywordByFilter;?

BTW, taking into account that the keyword is just a substring, we could save the
memory here by a custom implementation of the regular expression and storing the
keyword as DependentString but in another commit.

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

Sounds like a good idea. Done.

-}
-
-void Matcher::Remove(const FilterPtr& filter)

[sergei, 2017/10/02 12:02:37]

It seems the argument can be a const reference.

[hub, 2017/10/03 19:33:09]

Done.

-{
-  if (!mKeywordByFilter.find(filter->GetText()))
-    return;
-
-  auto keyword = mKeywordByFilter[filter->GetText()];

[sergei, 2017/10/02 12:02:37]

There is also no need for double looking up.

[hub, 2017/10/03 19:33:12]

Done.

-  auto list = mFilterByKeyword[keyword];
-  if (list.size() == 1)
-    mFilterByKeyword.erase(keyword);
-  else
-  {
-    auto iter = std::find(list.cbegin(), list.cend(), filter);
-    list.erase(iter);

[sergei, 2017/10/02 12:02:35]

It can be one line but it does not matter.

[hub, 2017/10/03 19:33:10]

Done.

-  }
-  mKeywordByFilter.erase(filter->GetText());
-}
-
-void Matcher::Clear()
-{
-  mFilterByKeyword.clear();
-  mKeywordByFilter.clear();
-}
-
-bool Matcher::HasFilter(const FilterPtr& filter) const

[sergei, 2017/10/02 12:02:35]

the argument should be a const reference.

[hub, 2017/10/03 19:33:09]

Done.

-{
-  return mKeywordByFilter.find(filter->GetText());
-}
-
-static DependentString emptyString = u""_str;

[sergei, 2017/10/02 12:02:37]

Although static in the compilation unit achieves the goal, I think we should
rather use anonymous namespaces.

[hub, 2017/10/03 19:33:10]

Done.

-
-const String& Matcher::GetKeywordForFilter(const FilterPtr& filter)

[sergei, 2017/10/02 12:02:36]

the argument should be a const reference and the method should be const because
it does not modify mKeywordByFilter.

[hub, 2017/10/03 19:33:12]

Done.

-{
-  if (mKeywordByFilter.find(filter->GetText()))
-    return mKeywordByFilter[filter->GetText()];
-  return emptyString;

[sergei, 2017/10/02 12:02:37]

There is also no need for double looking up.

[hub, 2017/10/03 19:33:13]

Done (needed for making the method `const`)

 }
 
 FilterPtr Matcher::CheckEntryMatch(const String& keyword,
   const String& location,
   int typeMask, DependentString& docDomain, bool thirdParty,
-  const String& sitekey, bool specificOnly)

[sergei, 2017/10/02 12:02:34]

basically this method and the one below do not modify the state, so I would
propose to make them const if it's possible.

[hub, 2017/10/03 19:33:10]

Done.

-{
-  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());

[sergei, 2017/10/02 12:02:35]

opening brace { should be on the new line.

[hub, 2017/10/03 19:33:14]

Done.

     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;
   }
+
   return FilterPtr();
 }
 
-Filter* Matcher::MatchesAny(const String& location,
+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.get();

[sergei, 2017/10/02 12:02:36]

just return `result.release();`

[hub, 2017/10/03 19:33:12]

Done.

-      }
-    }
-
-  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;
+}