nomでPackrat Parsing

# はじめに
nomはRustのパーサコンビネータライブラリです。このライブラリで作ったパーサは素朴なバックトラックありの再帰降下パーサになっていて、その計算量は最悪で指数時間になります。
これを解決する手法がPackrat Parsingです。この手法は構文解析の途中結果をメモ化しておくもので、計算量を線型に抑えることができます。（その代わりメモ化のための記憶領域を必要とするので、時間計算量を空間計算量に転換している感じです）
今回はnomをPackrat Parsingに対応させる拡張ライブラリを作りました。

対応するnomのバージョンは5.0.0です。バージョン5でデフォルトになった関数形式のパーサのみ対応し、バージョン4以前のマクロ形式はサポートしません。

リポジトリは以下になります。

https://github.com/dalance/nom-packrat

# 使い方

まずdependencesに追加します。

```toml:Cargo.toml
[dependencies]
nom-packrat = "0.1.0"
```

次に`storage!`マクロをクレートルート（main.rsかlib.rs）で宣言します。これはメモ化領域を確保するもので、マクロの引数はPackrat Parsingに対応させたいパーサの出力型です。

```rust
// Declare storage used by packrat_parser
storage!(String);
```

さらにPackrat Parsingに対応させたいパーサに`#[packrat_parser]`を付けます。

```rust
// Apply packrat_parser by custom attribute
#[packrat_parser]
pub fn parser(s: &str) -> IResult<&str, String> {
    let (s, x) = char('a')(s)?;
    Ok((s, x.to_string()))
}
```

最後にパーサを呼ぶ前に`init!()`を呼んでメモ化領域を初期化します。
（初回は初期化しなくても動きますが、複数回実行したときに前回のメモ化結果を使ってしまう可能性があるため初期化が必要です。）

```rust
fn main() {
    let input = "a";

    // Initialize before parsing
    init!();
    let result = parser(input);

    println!("{:?}", result);
}
```

# 注意点

最初に書いた通り、Packrat Parsingは解析結果のメモ化を行うので二点ほど注意点があります。

一つはパーサの出力型が`Clone`かつlifetimeを持たない必要があることです。これはメモ化のためにパーサ外部に結果を持ち出す必要があるためで、パース結果として`&str`などをそのまま持つことはできません。
`&str`の代替案としてはオリジナルの文字列に対するpositionとlengthのような形で持つことが考えられます。

二つ目はこのマクロを付けるべきパーサを選ぶ必要がある、ということです。全てに付けてもいいのですが、その分メモ化領域と余計な処理が発生します。
Packrat Parsingを適用したいということは複雑な文法でパフォーマンスを重視したい、ということのはずなので、速度とメモリのバランスを考える必要があります。
基本的には頻繁に呼ばれるパーサに適用するのがいいと思います。

# パフォーマンス

よく見かける括弧の個数で指数関数的に処理時間が延びるケースを測定しました。
文法はこんな感じです。

```
<S> ::= <T> + <S> | <T> - <S> | <T>
<T> ::= ( <S> ) | a
```

これにこのような入力を括弧の数を変えながら与えます。

```
a
(a)
((a))
(((a)))
((((a))))
(((((a)))))
((((((a))))))
(((((((a)))))))
```

結果はこの通りです。originalが括弧の数に対して指数関数的に処理時間が伸びているのに対して、Packrat Parsingを適用することで大きく改善しています。

![speed.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/84296/b4ac7f4e-0e77-a920-edcf-7cd389175e28.png)

一方メモリ使用量はこんな感じです。当然メモ化領域分の消費があるのでPackrat Parsingを適用した方が増えます。

![memory.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/84296/f356ae84-43b8-7370-d162-239115e3cc04.png)

グラフ中のpackrat_optは最も呼び出し回数の多い`<T>`だけにPackrat Parsingを適用した結果です。
1か所適用するだけでも処理時間は線形になり、メモリ使用量もそこまで増えないので、この文法に関してはこれが良さそうです。


# 仕組み

まず`storage!`マクロがメモ化領域を作成します。これはスレッドローカルストレージに置かれた`HashMap`で、キーは`&'static str`と`*const u8`のタプルです。`&'static str`はパーサの関数名、`*const u8`は入力スライスのポインタです。また`HashMap`の値は`Option<(O, usize)>`です。
（関数名をキーにするのはちょっといまいちなのですが、現状各procedural macroにユニークなIDを振る確実な方法がなさそうなのでこうしています）

```rust
thread_local!(
    pub static PACKRAT_STORAGE: core::cell::RefCell<
        std::collections::HashMap<(&'static str, *const u8), Option<(#t, usize)>>
    > = {
        core::cell::RefCell::new(std::collections::HashMap::new())
    }
);
```

この`HashMap`にどのパーサが入力スライスのどの位置でどういう結果を返したかを記録します。パース成功時は`Some((O, usize))`（この`usize`は成功時に消費する入力の長さ）、失敗時は`None`です。

そしてcustom attributeの`#[packrat_parser]`が各パーサにメモ化領域のチェックと結果の格納を行うコードを挿入します。

元のパーサがこのような場合、

```rust
#[packrat_parser]
pub fn parser(s: &str) -> IResult<&str, String> {
    let (s, x) = char('a')(s)?;
    Ok((s, x.to_string()))
}
```

マクロ展開後はこのようになります。
かなり長いですが、最初のif文がメモ化領域のチェック、途中の`let body_ret =`がパーサ本体の実行、最後のブロックが結果の格納です。

```rust
pub fn parser(s: &str) -> IResult<&str, String> {
    let org_input = if let Some(x) = crate::PACKRAT_STORAGE.with(|storage| {
        if let Some(x) = storage.borrow_mut().get(&("parser", s.as_bytes().as_ptr())) {
            if let Some((x, y)) = x {
                return Some(Some((x.clone(), *y)));
            } else {
                return Some(None);
            }
        } else {
            return None;
        }
    }) {
        if let Some((x, y)) = x {
            use nom::InputTake;
            let (s, _) = s.take_split(y);
            return Ok((s, x));
        } else {
            return Err(nom::Err::Error(nom::error::make_error(
                s,
                nom::error::ErrorKind::Fix,
            )));
        }
    } else {
        s
    };
    let body_ret = {
        {
            let (s, x) = char('a')(s)?;
            Ok((s, x.to_string()))
        }
    };
    {
        let ptr = org_input.as_bytes().as_ptr();
        if let Ok((s, x)) = &body_ret {
            use nom::Offset;
            let len = org_input.offset(&s);
            crate::PACKRAT_STORAGE.with(|storage| {
                storage
                    .borrow_mut()
                    .insert(("parser", ptr), Some((x.clone(), len)));
            });
        } else {
            crate::PACKRAT_STORAGE.with(|storage| {
                storage.borrow_mut().insert(("parser", ptr), None);
            });
        }
        body_ret
    }
}
```