図書館にビューティフルコードが置いてあったので借りて読んでいるのだけれど、1章で Rob Pike が C で書いた数十行の正規表現マッチャが紹介されていた。| は使えないものの . や * はサポートされており、また普通 NFA やらを構築してつくるものだと思っていたので、再帰使えばこんなにシンプルに正規表現マッチャを書けるのかと驚いた。

いつも通り Rust で書き直した。サポートされている記法は以下の通り。

fn main() {
    println!("Hello, world!");
}

fn regexmatch(regexp: String, text: String) -> bool {
    let regexp = regexp.chars().collect::<Vec<char>>();
    let text = text.chars().collect::<Vec<char>>();

    if regexp[0] == '^' {
        return matchhere(&regexp[1..], &text[..]);
    }

    let mut i = 0;
    loop {
        if matchhere(&regexp[..], &text[i..]) {
            return true;
        }

        i += 1;
        if i == text.len() {
            break;
        }
    }

    false
}

fn matchhere(regexp: &[char], text: &[char]) -> bool {
    if regexp.is_empty() {
        return true;
    }
    if regexp.len() > 1 && regexp[1] == '*' {
        return matchstar(regexp[0], &regexp[2..], text);
    }
    if regexp[0] == '$' && regexp.len() == 1 {
        return text.is_empty();
    }
    if !text.is_empty() && (regexp[0] == '.' || regexp[0] == text[0]) {
        return matchhere(&regexp[1..], &text[1..]);
    }

    false
}

fn matchstar(c: char, regexp: &[char], text: &[char]) -> bool {
    let mut i = 0;

    loop {
        if matchhere(regexp, &text[i..]) {
            return true;
        }

        if text[i..].is_empty() {
            break;
        }

        if c != text[i] && c != '.' {
            break;
        }

        if c == text[i] || c == '.' {
            i += 1;
            continue;
        }

        break;
    }

    false
}

mod test {
    use super::*;

    #[test]
    fn regexmatch_test() {
        assert!(regexmatch("abc".to_string(), "abc".to_string()));
        assert!(regexmatch("cd".to_string(), "abcde".to_string()));
        assert!(!regexmatch("cd".to_string(), "edcba".to_string()));

        assert!(regexmatch("^abc".to_string(), "abcc".to_string()));
        assert!(!regexmatch("^abc".to_string(), "babc".to_string()));

        assert!(regexmatch("a.c".to_string(), "abc".to_string()));
        assert!(!regexmatch("a.c".to_string(), "abd".to_string()));

        assert!(regexmatch("bc$".to_string(), "abc".to_string()));
        assert!(!regexmatch("bc$".to_string(), "abcd".to_string()));

        assert!(regexmatch("a*c".to_string(), "aaac".to_string()));
        assert!(regexmatch("a.*c".to_string(), "abbbbbc".to_string()));

        assert!(regexmatch(
            "a.*a.*a.*a.a".to_string(),
            "abbbbbbbbbbbbabbbbbbbbbbbbbbabbbbbbbbbbbbbbbaba".to_string()
        ));
    }
}