| 159 | } |
| 160 | |
| 161 | constexpr bool StringMatchImpl(std::string_view pattern, std::string_view string, bool ignore_case, |
| 162 | bool *skip_longer_matches, size_t recursion_depth = 0) { |
| 163 | // If we want to ignore case, this is equivalent to converting both the pattern and the string to lowercase |
| 164 | const auto canonicalize = [ignore_case](unsigned char c) -> unsigned char { |
| 165 | return ignore_case ? static_cast<unsigned char>(std::tolower(c)) : c; |
| 166 | }; |
| 167 | |
| 168 | if (recursion_depth > 1000) return false; |
| 169 | |
| 170 | while (!pattern.empty() && !string.empty()) { |
| 171 | switch (pattern[0]) { |
| 172 | case '*': |
| 173 | // Optimization: collapse multiple * into one |
| 174 | while (pattern.size() >= 2 && pattern[1] == '*') { |
| 175 | pattern.remove_prefix(1); |
| 176 | } |
| 177 | // Optimization: If the '*' is the last character in the pattern, it can match anything |
| 178 | if (pattern.length() == 1) return true; |
| 179 | while (!string.empty()) { |
| 180 | if (StringMatchImpl(pattern.substr(1), string, ignore_case, skip_longer_matches, recursion_depth + 1)) |
| 181 | return true; |
| 182 | if (*skip_longer_matches) return false; |
| 183 | string.remove_prefix(1); |
| 184 | } |
| 185 | // There was no match for the rest of the pattern starting |
| 186 | // from anywhere in the rest of the string. If there were |
| 187 | // any '*' earlier in the pattern, we can terminate the |
| 188 | // search early without trying to match them to longer |
| 189 | // substrings. This is because a longer match for the |
| 190 | // earlier part of the pattern would require the rest of the |
| 191 | // pattern to match starting later in the string, and we |
| 192 | // have just determined that there is no match for the rest |
| 193 | // of the pattern starting from anywhere in the current |
| 194 | // string. |
| 195 | *skip_longer_matches = true; |
| 196 | return false; |
| 197 | case '?': |
| 198 | if (string.empty()) return false; |
| 199 | string.remove_prefix(1); |
| 200 | break; |
| 201 | case '[': { |
| 202 | pattern.remove_prefix(1); |
| 203 | const bool invert = pattern[0] == '^'; |
| 204 | if (invert) pattern.remove_prefix(1); |
| 205 | |
| 206 | bool match = false; |
| 207 | while (true) { |
| 208 | if (pattern.empty()) { |
| 209 | // unterminated [ group: reject invalid pattern |
| 210 | return false; |
| 211 | } else if (pattern[0] == ']') { |
| 212 | break; |
| 213 | } else if (pattern.length() >= 2 && pattern[0] == '\\') { |
| 214 | pattern.remove_prefix(1); |
| 215 | if (pattern[0] == string[0]) match = true; |
| 216 | } else if (pattern.length() >= 3 && pattern[1] == '-') { |
| 217 | unsigned char start = canonicalize(pattern[0]); |
| 218 | unsigned char end = canonicalize(pattern[2]); |
no test coverage detected