Rustでワイルドカードを実装してみよう

前回、ワイルドカードのパターン検索に対応したファイル検索ツールを作ってみました。その際、wildcard_exというクレートでファイル名のマッチングを行いました。今回は、自力でワイルドカードの実装に挑戦してみましょう。

• ワイルドカードの関数を作ってみよう

ワイルドカードとは

正規表現を知らない人でも、ワイルドカードなら分かるという方は多くいます。ファイルやデータベースの検索をする際、ワイルドカードであれば、あまり考える事なく気軽に検索に利用できます。今回は、Rustでワイルドカードを実装してみましょう。

そもそも、「ワイルドカード(Wildcard)」とは、検索を行う時、コンピュータで特定の文字や文字列の代わりに使える記号のことです。「*」や「?」などの特殊記号を利用して、特別なパターンを表現できます。一般的なファイル検索で使えるワイルドカードには「*」と「?」があります。

例えば、「*」は任意の0文字以上の文字列を表します。「*.txt」でファイル検索したとき、拡張子「.txt」の全てのファイル「abc.txt」や「書類.txt」、「202408.txt」などのファイルを検索できなす。

「*」は任意の0文字以上の文字列を表し「?」は任意の1文字を表します。「test-?.xlsx」と指定すれば「test-1.xlsx」「test-2.xlsx」「test-a.xlsx」などのファイルを検索できます。

ワイルドカードをどのように実装したら良いか？

それでは、具体的にワイルドカードをどのように実装したら良いのか考えてみましょう。

まず、ワイルドカード関係なく、ただの文字列パターンが、文字列1と一致するかどうかを確認する場合には、次の図のように先頭の文字から1文字ずつそれぞれが一致するかを末尾まで確認することになります。

• パターンと文字列を1文字ずつ確認

ワイルドカードを実装する場合でも、基本的に同じです。ワイルドカードの「?」は任意の1文字のみを確認するので、「?」の部分にはどんな文字でも合致することにして確認すれば良いのです。

• ワイルドカードの場合も同じ - パターンと文字列を1文字ずつ確認

次に、ワイルドカード「*」を考えてみましょう。「*」は0文字以上の任意の文字を表します。そのため、次の図のように、文字列2とパターンが合致するかは、「*」のワイルドカードの部分を1文字ずつ飛ばして確認して、ワイルドカードの後から末尾が合致するかを確かめることになります。

• ワイルドカードの場合も同じ - パターンと文字列を1文字ずつ確認

つまり、「ab*.txt」というパターンに対して、文字列2「abcde.txt」がマッチするかを確認するには、パターンの3文字目の「*」を見つけた時点で、「cde.txt」がパターンの残りの部分「.txt」と合致するのかを検証します。そのために、「*」が0文字の任意文字だった場合、1文字の任意文字だった場合、2文字の任意文字だった場合…と検証していきます。

Rustで実装してみよう

Rustで実装する場合、少しコツが必要です。まず、日本語などの多バイト文字列(Unicode)に対応するために文字列(String)を1文字ずつに分割して、Vec<char>に変換します。その上で、文字列がパターンに合致するのか1文字ずつ確認します。

いきなりワイルドカードの「?」と「*」を実装してしまうと混乱してしまいそうです。そこで、まずは、「?」だけを実装してみましょう。

最初にRustのプロジェクトを作成しましょう。ターミナル(WindowsならPowerShell、macOSならターミナル.app)を起動して、下記のコマンドを実行しましょう。

mkdir wildcard_simple
cd wildcard_simple
cargo init

すると、プロジェクトのひな形が作成されます。そこで、src/main.rsを開いて、次のように編集してみましょう。(こちらにもアップしています - https://gist.github.com/kujirahand/e97ad3fd090ebd96619be18aaae30e11)

fn main() {
    // 「ab?.txt」が「abc.txt」にマッチするか --- (*1)
    println!("{}", is_match("ab?.txt", "abc.txt")); // true
}

// ワイルドカードのパターン「?」を使った文字列マッチング --- (*2)
fn is_match(pattern: &str, target: &str) -> bool {
    // &strをVec<char>に変換してis_match_sliceを呼び出す
    let pattern: Vec<char> = pattern.chars().collect();
    let target: Vec<char> = target.chars().collect();
    is_match_slice(&pattern, &target)
}

// ワイルドカードのパターン「?」を使った文字列マッチング --- (*3)
fn is_match_slice(pattern: &[char], target: &[char]) -> bool {
    let mut ip = 0;
    let mut it = 0;
    // 1文字ずつ順に比較していく --- (*4)
    while ip < pattern.len() && it < target.len() {
        if pattern[ip] == '?' { // 任意の1文字にマッチ --- (*5)
            ip += 1;
            it += 1;
        } else if pattern[ip] == target[it] { // 文字が一致 --- (*6)
            ip += 1;
            it += 1;
        } else {
            return false; // マッチしない
        }
    }
    // パターンも対象も末尾まで到達した場合にtrueを返す --- (*7)
    ip == pattern.len() && it == target.len()
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test() {
        // いろいろなパターンを試してみる --- (*8)
        assert_eq!(is_match("ab?.txt", "abc.txt"), true);
        assert_eq!(is_match("a??.txt", "abc.txt"), true);
        assert_eq!(is_match("?", "abc.txt"), false);
        assert_eq!(is_match("a?.txt", "abc.txt"), false);
        assert_eq!(is_match("????.txt", "test.txt"), true);
    }
}

プログラムを実行するには、ターミナルで下記のコマンドを実行しましょう。

cargo run

プログラムが正しく動けば、trueと表示されます。

• 正常に実行できた時、何も表示しない

また、プログラムの末尾にテストを記述しました。下記のコマンドを実行することで、テストだけを実行して動作を確認できます。

cargo test

正しくテストが実行されると、「test result: ok. 1 passed; 0 failed; ...」と表示されます。もし、テストに書いたassert_eq!が失敗すると、どのテストで失敗したかを表示します。

• テストを実行したところ

プログラムを確認してみましょう。(＊1)では、関数is_matchを記述しています。(＊2)では、&strをVec<char>に変換して関数is_match_sliceを呼び出します。これにより、日本語のような多バイト文字列に変換します。

(＊3)ではパターンマッチを行う関数is_match_sliceを記述します。(＊4)では基本的に1文字ずつ引数patternとtargetを付き合わせていきます。(＊5)ではワイルドカードの「?」を確認します。これは、任意の1文字にマッチするものなので、patternとtargetの確認位置のカーソルipとitを1ずつ進めるだけです。(＊6)では、文字が一致するかどうかを確認して、カーソルを進めます。そして、(＊7)では、カーソルが共に末尾に達しているかどうかを確認します。文字列の長さが異なる場合、関数の戻り値はfalseとなります。

(＊8)ではテストを記述します。#[cfg(test)] mod tests { ... } のように書く事で、テストであることを明示できて、コマンド「cargo test」でテストを実行できるようになります。

ワイルドカードの「*」にも対応しよう

続いて、ワイルドカードのパターン「*」にも対応するように、プログラムを改良してみまししょう。次のように修正しましょう。(こちらにもアップロードしています - https://gist.github.com/kujirahand/843c34e789af18551c01f22f6cdfab90)

fn main() {
    // 「ab?.txt」が「abc.txt」にマッチするか --- (*1)
    println!("{}", is_match("ab?.txt", "abc.txt")); // true
}

// ワイルドカードのパターン「?」を使った文字列マッチング --- (*2)
fn is_match(pattern: &str, target: &str) -> bool {
    // &strをVec<char>に変換してis_match_sliceを呼び出す
    let pattern: Vec<char> = pattern.chars().collect();
    let target: Vec<char> = target.chars().collect();
    is_match_slice(&pattern, &target)
}

// ワイルドカードのパターンを使った文字列マッチング --- (*3)
fn is_match_slice(pattern: &[char], target: &[char]) -> bool {
    let mut ip = 0;
    let mut it = 0;
    // 1文字ずつ順に比較していく --- (*4)
    while ip < pattern.len() && it < target.len() {
        if pattern[ip] == '*' { // 0文字以上の任意文字にマッチ --- (*5)
            ip += 1; // ワイルドカードをスキップ
            // ワイルドカードの次の文字が一致するまで繰り返す
            for i in it..target.len() {
                // 新たなスライスを作って再帰的にマッチングを行う
                let sub_pattern = &pattern[ip..];
                let sub_target = &target[i..];
                if is_match_slice(sub_pattern, sub_target) {
                    return true;
                }
            }
            continue;
        }
        if pattern[ip] == '?' { // 任意の1文字にマッチ --- (*6)
            ip += 1;
            it += 1;
            continue;
        }
        if pattern[ip] == target[it] { // 文字が一致 --- (*7)
            ip += 1;
            it += 1;
            continue;
        }
        return false; // マッチしない
    }
    // パターンも対象も末尾まで到達した場合にtrueを返す --- (*8)
    ip == pattern.len() && it == target.len()
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test() {
        // いろいろなパターンを試してみる --- (*9)
        assert_eq!(is_match("ab?.txt", "abc.txt"), true);
        assert_eq!(is_match("a*.txt", "abc.txt"), true);
        assert_eq!(is_match("*.txt", "abc.txt"), true);
        assert_eq!(is_match("a?g.txt", "abcdefg.txt"), false);
        assert_eq!(is_match("a*g.txt", "abcdefg.txt"), true);
        assert_eq!(is_match("a*b*g.txt", "abcdefg.txt"), true);
        assert_eq!(is_match("*efg.txt", "abcdefg.txt"), true);
    }
}

プログラムを書き換えたら、改めてテストしてみましょう。「test result: ok. 1 passed;...」のように表示されたら成功です。

cargo test

プログラムを確認してみましょう。(＊1)と(＊2)の部分は何も変更していません。&strをVec<char>に変換して、is_match_slice関数を呼び出します。(＊3)の関数is_match_sliceでは、ワイルドカードのパターン「*」と「?」を利用したパターンマッチを行います。(＊4)では、先ほどのプログラムと同じように1文字ずつ文字を突き合わせてマッチするかを確認します。

ポイントとなるのが(＊5)のパターン「*」です。カーソルを1文字ずつ進めながら、マッチするかどうか関数is_match_sliceを再帰的に呼び出して確認します。カーソルを1文字分ずらしたスライスを作って、関数is_match_sliceを呼び出します。

(＊6)ではパターン「?」をマッチするか確認し、(＊7)ではワイルドカード以外のパターンを確認します。(＊8)ではパターンも対象文字列もカーソルが末尾に達したかを確認します。

(＊9)ではテストを記述します。ワイルドカードの「*」と「?」が正しく使えるかをテストするものです。

前回のファイル再帰検索で使ってみよう

それでは、前回作ったファイルの再帰検索プログラムで、自作のワイルドカードのライブラリを使うように改造してみましょう。ちょっと長くなってしまったので、プログラム全体をこちら(https://gist.github.com/kujirahand/45ecf1d475535187b1d7fc2cb0863253)にアップロードしました。