pattern.cc 5.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155
  1. // Copyright 2015 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 "base/strings/pattern.h"
  5. #include "base/third_party/icu/icu_utf.h"
  6. namespace base {
  7. namespace {
  8. constexpr bool IsWildcard(base_icu::UChar32 character) {
  9. return character == '*' || character == '?';
  10. }
  11. // Searches for the next subpattern of |pattern| in |string|, up to the given
  12. // |maximum_distance|. The subpattern extends from the start of |pattern| up to
  13. // the first wildcard character (or the end of the string). If the value of
  14. // |maximum_distance| is negative, the maximum distance is considered infinite.
  15. template <typename CHAR, typename NEXT>
  16. constexpr bool SearchForChars(const CHAR** pattern,
  17. const CHAR* pattern_end,
  18. const CHAR** string,
  19. const CHAR* string_end,
  20. int maximum_distance,
  21. NEXT next) {
  22. const CHAR* pattern_start = *pattern;
  23. const CHAR* string_start = *string;
  24. bool escape = false;
  25. while (true) {
  26. if (*pattern == pattern_end) {
  27. // If this is the end of the pattern, only accept the end of the string;
  28. // anything else falls through to the mismatch case.
  29. if (*string == string_end)
  30. return true;
  31. } else {
  32. // If we have found a wildcard, we're done.
  33. if (!escape && IsWildcard(**pattern))
  34. return true;
  35. // Check if the escape character is found. If so, skip it and move to the
  36. // next character.
  37. if (!escape && **pattern == '\\') {
  38. escape = true;
  39. next(pattern, pattern_end);
  40. continue;
  41. }
  42. escape = false;
  43. if (*string == string_end)
  44. return false;
  45. // Check if the chars match, if so, increment the ptrs.
  46. const CHAR* pattern_next = *pattern;
  47. const CHAR* string_next = *string;
  48. base_icu::UChar32 pattern_char = next(&pattern_next, pattern_end);
  49. if (pattern_char == next(&string_next, string_end) &&
  50. pattern_char != CBU_SENTINEL) {
  51. *pattern = pattern_next;
  52. *string = string_next;
  53. continue;
  54. }
  55. }
  56. // Mismatch. If we have reached the maximum distance, return false,
  57. // otherwise restart at the beginning of the pattern with the next character
  58. // in the string.
  59. // TODO(bauerb): This is a naive implementation of substring search, which
  60. // could be implemented with a more efficient algorithm, e.g.
  61. // Knuth-Morris-Pratt (at the expense of requiring preprocessing).
  62. if (maximum_distance == 0)
  63. return false;
  64. // Because unlimited distance is represented as -1, this will never reach 0
  65. // and therefore fail the match above.
  66. maximum_distance--;
  67. *pattern = pattern_start;
  68. next(&string_start, string_end);
  69. *string = string_start;
  70. }
  71. }
  72. // Consumes consecutive wildcard characters (? or *). Returns the maximum number
  73. // of characters matched by the sequence of wildcards, or -1 if the wildcards
  74. // match an arbitrary number of characters (which is the case if it contains at
  75. // least one *).
  76. template <typename CHAR, typename NEXT>
  77. constexpr int EatWildcards(const CHAR** pattern, const CHAR* end, NEXT next) {
  78. int num_question_marks = 0;
  79. bool has_asterisk = false;
  80. while (*pattern != end) {
  81. if (**pattern == '?') {
  82. num_question_marks++;
  83. } else if (**pattern == '*') {
  84. has_asterisk = true;
  85. } else {
  86. break;
  87. }
  88. next(pattern, end);
  89. }
  90. return has_asterisk ? -1 : num_question_marks;
  91. }
  92. template <typename CHAR, typename NEXT>
  93. constexpr bool MatchPatternT(const CHAR* eval,
  94. const CHAR* eval_end,
  95. const CHAR* pattern,
  96. const CHAR* pattern_end,
  97. NEXT next) {
  98. do {
  99. int maximum_wildcard_length = EatWildcards(&pattern, pattern_end, next);
  100. if (!SearchForChars(&pattern, pattern_end, &eval, eval_end,
  101. maximum_wildcard_length, next)) {
  102. return false;
  103. }
  104. } while (pattern != pattern_end);
  105. return true;
  106. }
  107. struct NextCharUTF8 {
  108. base_icu::UChar32 operator()(const char** p, const char* end) {
  109. base_icu::UChar32 c;
  110. int offset = 0;
  111. CBU8_NEXT(reinterpret_cast<const uint8_t*>(*p), offset, end - *p, c);
  112. *p += offset;
  113. return c;
  114. }
  115. };
  116. struct NextCharUTF16 {
  117. base_icu::UChar32 operator()(const char16_t** p, const char16_t* end) {
  118. base_icu::UChar32 c;
  119. int offset = 0;
  120. CBU16_NEXT(*p, offset, end - *p, c);
  121. *p += offset;
  122. return c;
  123. }
  124. };
  125. } // namespace
  126. bool MatchPattern(StringPiece eval, StringPiece pattern) {
  127. return MatchPatternT(eval.data(), eval.data() + eval.size(), pattern.data(),
  128. pattern.data() + pattern.size(), NextCharUTF8());
  129. }
  130. bool MatchPattern(StringPiece16 eval, StringPiece16 pattern) {
  131. return MatchPatternT(eval.data(), eval.data() + eval.size(), pattern.data(),
  132. pattern.data() + pattern.size(), NextCharUTF16());
  133. }
  134. } // namespace base