[subresource_filter] Replace KMP by std::search.

components/subresource_filter/core/common/indexed_ruleset.cc

 // Copyright 2016 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "components/subresource_filter/core/common/indexed_ruleset.h"
 
 #include <algorithm>
 #include <limits>
 #include <string>
 
 #include "base/logging.h"
 #include "base/numerics/safe_conversions.h"
 #include "components/subresource_filter/core/common/first_party_origin.h"
 #include "components/subresource_filter/core/common/ngram_extractor.h"
 #include "components/subresource_filter/core/common/url_pattern.h"
-#include "components/subresource_filter/core/common/url_pattern_matching.h"
 #include "third_party/flatbuffers/src/include/flatbuffers/flatbuffers.h"
 
 namespace subresource_filter {
 
 namespace {
 
 using FlatStringOffset = flatbuffers::Offset<flatbuffers::String>;
 
 // Checks whether a URL |rule| can be converted to its FlatBuffers equivalent,
 // and performs the actual conversion.
@@ skipping 30 matching lines @@
         if (domain_list_item.exclude())
           domain += '~';
         domain += domain_list_item.domain();
         domains.push_back(builder->CreateSharedString(domain));
       }
       domains_offset = builder->CreateVector(domains);
     }
 
     auto url_pattern_offset = builder->CreateString(rule_.url_pattern());
 
-    std::vector<uint8_t> failure_function;
-    BuildFailureFunction(UrlPattern(rule_), &failure_function);
-    auto failure_function_offset =
-        builder->CreateVector(failure_function.data(), failure_function.size());
-
     return flat::CreateUrlRule(*builder, options_, element_types_,
                                activation_types_, url_pattern_type_,
                                anchor_left_, anchor_right_, domains_offset,
-                               url_pattern_offset, failure_function_offset);
+                               url_pattern_offset);
   }
 
  private:
   static bool ConvertAnchorType(proto::AnchorType anchor_type,
                                 flat::AnchorType* result) {
     switch (anchor_type) {
       case proto::ANCHOR_TYPE_NONE:
         *result = flat::AnchorType_NONE;
         break;
       case proto::ANCHOR_TYPE_BOUNDARY:
@@ skipping 58 matching lines @@
         "Activation types can not be stored in uint8_t.");
     if ((rule_.activation_types() & proto::ACTIVATION_TYPE_ALL) !=
         rule_.activation_types()) {
       return false;  // Unsupported activation types.
     }
     activation_types_ = static_cast<uint8_t>(rule_.activation_types());
     return true;
   }
 
   bool InitializeUrlPattern() {
-    if (rule_.url_pattern().size() >
-        static_cast<size_t>(std::numeric_limits<uint8_t>::max())) {
-      // Failure function can not always be stored as an array of uint8_t in
-      // case the pattern's length exceeds 255.
-      return false;
-    }
-
     switch (rule_.url_pattern_type()) {
       case proto::URL_PATTERN_TYPE_SUBSTRING:
         url_pattern_type_ = flat::UrlPatternType_SUBSTRING;
         break;
       case proto::URL_PATTERN_TYPE_WILDCARDED:
         url_pattern_type_ = flat::UrlPatternType_WILDCARDED;
         break;
+
+      // TODO(pkalinnikov): Implement REGEXP rules matching.
       case proto::URL_PATTERN_TYPE_REGEXP:
-        url_pattern_type_ = flat::UrlPatternType_REGEXP;
-        break;
-
       default:
         return false;  // Unsupported URL pattern type.
     }
 
     if (!ConvertAnchorType(rule_.anchor_left(), &anchor_left_) ||
         !ConvertAnchorType(rule_.anchor_right(), &anchor_right_)) {
       return false;
     }
     if (anchor_right_ == flat::AnchorType_SUBDOMAIN)
       return false;  // Unsupported right anchor.
@@ skipping 11 matching lines @@
   flat::AnchorType anchor_right_ = flat::AnchorType_NONE;
 
   bool is_convertible_ = true;
 };
 
 }  // namespace
 
 // RulesetIndexer --------------------------------------------------------------
 
 // static
-const int RulesetIndexer::kIndexedFormatVersion = 12;
+const int RulesetIndexer::kIndexedFormatVersion = 13;
 
 RulesetIndexer::MutableUrlPatternIndex::MutableUrlPatternIndex() = default;
 RulesetIndexer::MutableUrlPatternIndex::~MutableUrlPatternIndex() = default;
 
 RulesetIndexer::RulesetIndexer() = default;
 RulesetIndexer::~RulesetIndexer() = default;
 
 bool RulesetIndexer::AddUrlRule(const proto::UrlRule& rule) {
   UrlRuleFlatBufferConverter converter(rule);
   if (!converter.is_convertible())
     return false;
   auto rule_offset = converter.SerializeConvertedRule(&builder_);
 
   MutableUrlPatternIndex* index_part =
       (rule.semantics() == proto::RULE_SEMANTICS_BLACKLIST ? &blacklist_
                                                            : &whitelist_);
 
-  NGram ngram = 0;
-  if (rule.url_pattern_type() != proto::URL_PATTERN_TYPE_REGEXP) {
-    ngram =
-        GetMostDistinctiveNGram(index_part->ngram_index, rule.url_pattern());
-  }
+  DCHECK_NE(rule.url_pattern_type(), proto::URL_PATTERN_TYPE_REGEXP);
+  NGram ngram =
+      GetMostDistinctiveNGram(index_part->ngram_index, rule.url_pattern());
 
   if (ngram) {
     index_part->ngram_index[ngram].push_back(rule_offset);
   } else {
     // TODO(pkalinnikov): Index fallback rules as well.
     index_part->fallback_rules.push_back(rule_offset);
   }
 
   return true;
 }
@@ skipping 162 matching lines @@
                 const GURL& url,
                 const url::Origin& initiator,
                 proto::ElementType element_type,
                 proto::ActivationType activation_type,
                 bool is_third_party,
                 bool disable_generic_rules) {
   if (!rules)
     return false;
   for (const flat::UrlRule* rule : *rules) {
     DCHECK_NE(rule, nullptr);
-
-    if (rule->url_pattern_type() != flat::UrlPatternType_REGEXP) {
-      const uint8_t* begin = rule->failure_function()->data();
-      const uint8_t* end = begin + rule->failure_function()->size();
-      if (!IsUrlPatternMatch(url, UrlPattern(*rule), begin, end))
-        continue;
-    } else {
-      // TODO(pkalinnikov): Implement REGEXP rules matching.
+    DCHECK_NE(rule->url_pattern_type(), flat::UrlPatternType_REGEXP);
+    if (!UrlPattern(*rule).MatchesUrl(url))
       continue;
-    }
 
     // TODO(pkalinnikov): Match the medatada before the URL pattern, but maybe
     // excluding the domain list.
     if (DoesRuleMetadataMatch(*rule, initiator, element_type, activation_type,
                               is_third_party, disable_generic_rules)) {
       return true;
     }
   }
 
   return false;
@@ skipping 83 matching lines @@
   const bool is_third_party = first_party.IsThirdParty(url);
   return IsMatch(root_->blacklist_index(), url, first_party.origin(),
                  element_type, proto::ACTIVATION_TYPE_UNSPECIFIED,
                  is_third_party, disable_generic_rules) &&
          !IsMatch(root_->whitelist_index(), url, first_party.origin(),
                   element_type, proto::ACTIVATION_TYPE_UNSPECIFIED,
                   is_third_party, disable_generic_rules);
 }
 
 }  // namespace subresource_filter