fuzzy_pattern_matching.cc 1.8 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061
  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. #include "components/url_pattern_index/fuzzy_pattern_matching.h"
  5. #include <algorithm>
  6. #include "base/check_op.h"
  7. namespace url_pattern_index {
  8. namespace {
  9. bool StartsWithFuzzyImpl(base::StringPiece text, base::StringPiece subpattern) {
  10. DCHECK_LE(subpattern.size(), text.size());
  11. for (size_t i = 0; i != subpattern.size(); ++i) {
  12. const char text_char = text[i];
  13. const char pattern_char = subpattern[i];
  14. if (text_char != pattern_char &&
  15. (pattern_char != kSeparatorPlaceholder || !IsSeparator(text_char))) {
  16. return false;
  17. }
  18. }
  19. return true;
  20. }
  21. } // namespace
  22. bool StartsWithFuzzy(base::StringPiece text, base::StringPiece subpattern) {
  23. return subpattern.size() <= text.size() &&
  24. StartsWithFuzzyImpl(text, subpattern);
  25. }
  26. bool EndsWithFuzzy(base::StringPiece text, base::StringPiece subpattern) {
  27. return subpattern.size() <= text.size() &&
  28. StartsWithFuzzyImpl(text.substr(text.size() - subpattern.size()),
  29. subpattern);
  30. }
  31. size_t FindFuzzy(base::StringPiece text,
  32. base::StringPiece subpattern,
  33. size_t from) {
  34. if (from > text.size())
  35. return base::StringPiece::npos;
  36. if (subpattern.empty())
  37. return from;
  38. auto fuzzy_compare = [](char text_char, char subpattern_char) {
  39. return text_char == subpattern_char ||
  40. (subpattern_char == kSeparatorPlaceholder && IsSeparator(text_char));
  41. };
  42. base::StringPiece::const_iterator found =
  43. std::search(text.begin() + from, text.end(), subpattern.begin(),
  44. subpattern.end(), fuzzy_compare);
  45. return found == text.end() ? base::StringPiece::npos : found - text.begin();
  46. }
  47. } // namespace url_pattern_index