Create a separate component for UrlPatternIndex.
Bug: 713774
Change-Id: I12a70bc0b5caa37470ecf53568d90304c05095eb
Reviewed-on: https://chromium-review.googlesource.com/527445
Commit-Queue: Pavel Kalinnikov <[email protected]>
Reviewed-by: Jochen Eisinger <[email protected]>
Reviewed-by: Charlie Harrison <[email protected]>
Cr-Commit-Position: refs/heads/master@{#481360}diff --git a/components/url_pattern_index/fuzzy_pattern_matching.cc b/components/url_pattern_index/fuzzy_pattern_matching.cc
new file mode 100644
index 0000000..92b6032
--- /dev/null
+++ b/components/url_pattern_index/fuzzy_pattern_matching.cc
@@ -0,0 +1,59 @@
+// 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/url_pattern_index/fuzzy_pattern_matching.h"
+
+#include <algorithm>
+
+namespace url_pattern_index {
+
+namespace {
+
+bool StartsWithFuzzyImpl(base::StringPiece text, base::StringPiece subpattern) {
+ DCHECK_LE(subpattern.size(), text.size());
+
+ for (size_t i = 0; i != subpattern.size(); ++i) {
+ const char text_char = text[i];
+ const char pattern_char = subpattern[i];
+ if (text_char != pattern_char &&
+ (pattern_char != kSeparatorPlaceholder || !IsSeparator(text_char))) {
+ return false;
+ }
+ }
+ return true;
+}
+
+} // namespace
+
+bool StartsWithFuzzy(base::StringPiece text, base::StringPiece subpattern) {
+ return subpattern.size() <= text.size() &&
+ StartsWithFuzzyImpl(text, subpattern);
+}
+
+bool EndsWithFuzzy(base::StringPiece text, base::StringPiece subpattern) {
+ return subpattern.size() <= text.size() &&
+ StartsWithFuzzyImpl(text.substr(text.size() - subpattern.size()),
+ subpattern);
+}
+
+size_t FindFuzzy(base::StringPiece text,
+ base::StringPiece subpattern,
+ size_t from) {
+ if (from > text.size())
+ return base::StringPiece::npos;
+ if (subpattern.empty())
+ return from;
+
+ auto fuzzy_compare = [](char text_char, char subpattern_char) {
+ return text_char == subpattern_char ||
+ (subpattern_char == kSeparatorPlaceholder && IsSeparator(text_char));
+ };
+
+ base::StringPiece::const_iterator found =
+ std::search(text.begin() + from, text.end(), subpattern.begin(),
+ subpattern.end(), fuzzy_compare);
+ return found == text.end() ? base::StringPiece::npos : found - text.begin();
+}
+
+} // namespace url_pattern_index
