# String Pattern

今日は文字列が一致しているか調べる関数について呼ぶ。

[MatchPattern](https://source.chromium.org/chromium/chromium/src/+/main:base/strings/pattern.h;l=18-19;drc=e4622aaeccea84652488d1822c28c78b7115684f) は`string`がワイルドカードを含む`pattern`とマッチするをか調べる。

## APIの概要
以下のようなMatchPatternの関数が定義されている。

BASE_EXPORT bool MatchPattern(StringPiece string, StringPiece pattern);
BASE_EXPORT bool MatchPattern(StringPiece16 string, StringPiece16 pattern);

`pattern`は`\*`や`\?`（ワイルドカードと呼ぶ）を含める。`\`は`*`と`?`のエスケープに使われ、`*`は0文字以上の任意のstringに、`?`は0-1文字の任意の文字に一致する。

## 実装
MatchPatternの中身は以下のような感じでループを回している。
大まかに言うと、ワイルドカードごとに進めて確認していって一致しないことが確定したら失敗、最後まで失敗しなければ成功。

template <typename CHAR, typename NEXT>
constexpr bool MatchPatternT(const CHAR* eval,
                             const CHAR* eval_end,
                             const CHAR* pattern,
                             const CHAR* pattern_end,
                             NEXT next) {
  do {
    int maximum_wildcard_length = EatWildcards(&pattern, pattern_end, next);
    if (!SearchForChars(&pattern, pattern_end, &eval, eval_end,
                        maximum_wildcard_length, next)) {
      return false;
    }
  } while (pattern != pattern_end);
  return true;
}

まず[EatWildcards](https://source.chromium.org/chromium/chromium/src/+/main:base/strings/pattern.cc;l=90;drc=353683321da2061bb47d7655d4b3fc04c1540ed3)で`?, *`を確認。
連続で何文字分のワイルドカードがあるかを計算して返す。`*`が入ったら何文字でもよいため、`-1`を返して表現する。なお`?`は0文字でもよいため、`*`が入った時点で無視して良い。

この文字数を`maximum_distance`としながら[SearchForChars](https://source.chromium.org/chromium/chromium/src/+/main:base/strings/pattern.cc;l=22;drc=353683321da2061bb47d7655d4b3fc04c1540ed3)を呼ぶ。

ここでも`string`をインクリメントしながらマッチを調べる。
もしpatternとstringの次の文字が同じならOK。patternとstringを両方インクリメントして次のループへGO。
あとは`maximum_distance`分でマッチできるかを確認する。
`maximum_distance`をデクリメントして不一致１文字分を許して、stringだけインクリメントする。もしすでに`maximum_distance`が0ならマッチ不能なので失敗、終了。
なお`*`が含まれている時`-1`がセットされているが、デクリメントしても一生0にはならないのでOK（一応オーバーフローすると困るがそのサイズの文字列はそもそも扱えない）。

このループを文字列最後までいけたらクリア、成功として返す。
その前に新たなワイルドカードとぶつかったら、一旦ここまでは成功として返して、MatchPatternTの中のループをまた回して次のワイルドカード軍団についてSearchForCharsをやる。

`string`の最後まで到達して一度も失敗しなければ成功を返して成功。

## Next について
文字列のインクリメントは[CBU8_NEXT](https://source.chromium.org/chromium/chromium/src/+/main:base/third_party/icu/icu_utf.h;l=237;drc=353683321da2061bb47d7655d4b3fc04c1540ed3)が使われている。
ICUはthird partyのライブラリで、文字列をいい感じに扱ってくれるやつ。

[ICU: International Components for Unicode](https://icu.unicode.org/)