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;
+}
+
+void Matcher::Add(Filter& filter)
+{
+  if (mKeywordByFilter.find(filter.GetText()))
+    return;
+
+  auto keyword = FindKeyword(filter);
+
+  mFilterByKeyword[keyword].push_back(FilterPtr(&filter));
+  mKeywordByFilter[filter.GetText()] = keyword;
+}
+
+void Matcher::Remove(Filter& filter)
+{
+  auto entry = mKeywordByFilter.find(filter.GetText());
+  if (!entry)
+    return;
+
+  auto keyword = 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 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))
+    {
+      auto result = CheckEntryMatch(substr, location, typeMask, docDomain,
+                                    thirdParty, sitekey, specificOnly);
+      if (result)
+        return result.release();
+    }
+  }
+  return nullptr;
+}
+
+OwnedString Matcher::FindKeyword(const Filter& filter) const
+{
+  OwnedString result(u""_str);
+  OwnedString text(filter.GetText());
+  auto re_id = GenerateRegExp(regexpRegExp, true, false);
+  if (TestRegExp(re_id, text))
+    return result;
+
+  // Remove options
+  auto options_re_id = GenerateRegExp(optionsRegExp, true, false);
+  auto index = ExecRegExp(options_re_id, text);
+  if (index != String::npos)
+    text = text.substr(0, index);
+
+  // Remove whitelist marker
+  if (text.length() >= 2 && text[0] == '@' && text[1] == '@')
+    text = text.substr(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());
+  if (!match)
+    return result;
+
+  auto& candidates = keywords->candidates;
+
+  auto& hash = mFilterByKeyword;
+  uint32_t resultCount = 0xffffffff;
+  uint32_t resultLength = 0;
+  for (auto substr : candidates)
+  {
+    if (substr.empty())
+      continue;
+
+    auto candidate = substr.substr(1);
+    auto entry = hash.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;
+    }
+  }
+  return FilterPtr();
+}
+
+const size_t CombinedMatcher::MAX_CACHE_ENTRIES = 1000;
+
+void CombinedMatcher::Add(Filter& filter)
+{
+  if (filter.mType == Filter::Type::WHITELIST)
+    mWhitelist.Add(filter);
+  else
+    mBlacklist.Add(filter);
+
+  ResetCache();
+}
+
+void CombinedMatcher::Remove(Filter& filter)
+{
+  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 Filter& filter) const
+{
+  return filter.mType == Filter::Type::WHITELIST ?
+    mWhitelist.HasFilter(filter) : mBlacklist.HasFilter(filter);
+}
+
+const String& CombinedMatcher::GetKeywordForFilter(const Filter& filter) const
+{
+  return filter.mType == Filter::Type::WHITELIST ?
+    mWhitelist.GetKeywordForFilter(filter) : mBlacklist.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;
+  else
+  {
+    result = MatchesAnyInternal(location, typeMask, docDomain,
+                                thirdParty, sitekey, specificOnly);
+
+    if (mResultCache.size() >= MAX_CACHE_ENTRIES)
+      ResetCache();
+
+    mResultCache[key] = result;
+  }
+
+  return result.release();
+}
+
+OwnedString CombinedMatcher::FindKeyword(const Filter& filter) const
+{
+  return filter.mType == Filter::Type::WHITELIST ?
+    mWhitelist.FindKeyword(filter) : mBlacklist.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());
+
+  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);
+    if (result)
+      return result;
+
+    if (!blacklistHit)
+      blacklistHit = mBlacklist.CheckEntryMatch(
+        substr, location, typeMask, docDomain, thirdParty, sitekey,
+        specificOnly);
+  }
+  return blacklistHit;
+}