pkalinnikov | ea35060 | 2016-06-24 11:22:15 | [diff] [blame] | 1 | // Copyright 2016 The Chromium Authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
| 4 | |
Pavel Kalinnikov | d797063 | 2017-06-20 09:07:34 | [diff] [blame] | 5 | #include "components/url_pattern_index/fuzzy_pattern_matching.h" |
pkalinnikov | ea35060 | 2016-06-24 11:22:15 | [diff] [blame] | 6 | |
pkalinnikov | 35d1881 | 2017-04-05 17:28:18 | [diff] [blame] | 7 | #include <algorithm> |
| 8 | |
Pavel Kalinnikov | d797063 | 2017-06-20 09:07:34 | [diff] [blame] | 9 | namespace url_pattern_index { |
pkalinnikov | ea35060 | 2016-06-24 11:22:15 | [diff] [blame] | 10 | |
| 11 | namespace { |
| 12 | |
| 13 | bool StartsWithFuzzyImpl(base::StringPiece text, base::StringPiece subpattern) { |
| 14 | DCHECK_LE(subpattern.size(), text.size()); |
| 15 | |
| 16 | for (size_t i = 0; i != subpattern.size(); ++i) { |
| 17 | const char text_char = text[i]; |
| 18 | const char pattern_char = subpattern[i]; |
| 19 | if (text_char != pattern_char && |
| 20 | (pattern_char != kSeparatorPlaceholder || !IsSeparator(text_char))) { |
| 21 | return false; |
| 22 | } |
| 23 | } |
| 24 | return true; |
| 25 | } |
| 26 | |
| 27 | } // namespace |
| 28 | |
pkalinnikov | ea35060 | 2016-06-24 11:22:15 | [diff] [blame] | 29 | bool StartsWithFuzzy(base::StringPiece text, base::StringPiece subpattern) { |
pkalinnikov | 854818d6 | 2016-07-22 11:55:10 | [diff] [blame] | 30 | return subpattern.size() <= text.size() && |
| 31 | StartsWithFuzzyImpl(text, subpattern); |
pkalinnikov | ea35060 | 2016-06-24 11:22:15 | [diff] [blame] | 32 | } |
| 33 | |
| 34 | bool EndsWithFuzzy(base::StringPiece text, base::StringPiece subpattern) { |
pkalinnikov | 854818d6 | 2016-07-22 11:55:10 | [diff] [blame] | 35 | return subpattern.size() <= text.size() && |
| 36 | StartsWithFuzzyImpl(text.substr(text.size() - subpattern.size()), |
| 37 | subpattern); |
pkalinnikov | ea35060 | 2016-06-24 11:22:15 | [diff] [blame] | 38 | } |
| 39 | |
pkalinnikov | 35d1881 | 2017-04-05 17:28:18 | [diff] [blame] | 40 | size_t FindFuzzy(base::StringPiece text, |
| 41 | base::StringPiece subpattern, |
| 42 | size_t from) { |
| 43 | if (from > text.size()) |
| 44 | return base::StringPiece::npos; |
| 45 | if (subpattern.empty()) |
| 46 | return from; |
| 47 | |
| 48 | auto fuzzy_compare = [](char text_char, char subpattern_char) { |
| 49 | return text_char == subpattern_char || |
| 50 | (subpattern_char == kSeparatorPlaceholder && IsSeparator(text_char)); |
| 51 | }; |
| 52 | |
| 53 | base::StringPiece::const_iterator found = |
| 54 | std::search(text.begin() + from, text.end(), subpattern.begin(), |
| 55 | subpattern.end(), fuzzy_compare); |
| 56 | return found == text.end() ? base::StringPiece::npos : found - text.begin(); |
| 57 | } |
| 58 | |
Pavel Kalinnikov | d797063 | 2017-06-20 09:07:34 | [diff] [blame] | 59 | } // namespace url_pattern_index |