パーサコンビネータcombine を使ってみる

[Marwes/combine](https://github.com/Marwes/combine): A parser combinator library for Rust

Parsecに影響を受けて作られたパーサコンビネータだそうです。
Rustでパーサコンビネータといえばnomといった風潮ですが、combineはトレイトを中心にしたRustらしい実装であり、マクロでパーサを記述するnomと違ってRustのシンタックスで書けます。

この記事では設定ファイル記述言語である[TOML](https://github.com/toml-lang/toml)で定義されているリテラル数値・文字列の文法を例にパーサを書いてみます。
なお、以下のようなものを自力で実装する必要はあまり無くて、言語実装に必要なパーサは[combine-language](https://github.com/Marwes/combine-language)というクレートでもっと網羅的に提供されています。

# Parserトレイト

combineでは、パーサは[`Parser`](https://docs.rs/combine/*/combine/trait.Parser.html)トレイトを実装した型として表され、コンビネータで`Parser`を組み合わせていくことで大きなパーサを作っていくことができます。`Parser`トレイトは入力、出力の型を関連型として持っており、`parse`メソッドに入力を渡すと`Ok((出力, 入力の残り))`あるいは`Err(パースエラー)`が返るようになっています。

例えば数値のパーサなら、`"123"`という文字列を`parse`メソッドに渡すと`Ok((123, ""))`を返すわけです。

```rust
pub trait Parser {
    type Input: Stream;
    type Output;

    // fn (入力) -> Result<(出力, 入力の残り), パースエラー>
    fn parse(&mut self, input: Self::Input)
        -> Result<(Self::Output, Self::Input), ParseError<Self::Input>>;
    
    // 他のparse_*はここでは気にしない

    // コンビネータやエラー処理のためのメソッドが続く
    // and, or, map, with, skip, ...
    // message, expected, ...
    ...
}
```

この`Parser`トレイトを中心に、処理の組み合わせを`Map` `And`などのアダプタ型で表す、[`Iterator`](https://doc.rust-lang.org/std/iter/trait.Iterator.html)や[`Future`](https://docs.rs/futures/*/futures/future/trait.Future.html)などと同じようなデザインです。

パーサの入力型として使えるものは文字列`&str`やスライス`&[T]`、[`IteratorStream`](https://docs.rs/combine/*/combine/primitives/struct.IteratorStream.html)などです。また文字列(あるいはバイト列`&[u8]`)を[`State`](https://docs.rs/combine/*/combine/struct.State.html)でラップしたものも入力として使え、オーバーヘッドが増える代わりにパーサ内から行・桁(バイト列の場合はバイトオフセット)の取得が可能になり、エラー発生時にはエラー位置がそれで表示されるようになります。

# 整数リテラルをパースしてみる

TOMLの整数リテラルは符号付き64bit整数だそうです。文字列を入力すると`i64`を出力するパーサを作ります。

ここでは分かりやすいように個別にインポートしていますが、普通に`use combine::*;`してしまえば良いかと思います。

## 符号

まずは数字の前に付く符号のパーサから。`combine::token`は引数で与えられた1要素にマッチして、それをそのまま出力するパーサです。文字列を入力とするパーサでは1要素=1文字(`char`)です。

また、`+`と`-`の2通りの可能性を`Parser::or`で振り分けます。`or`は「このパーサが失敗したら別のパーサを試す」というパーサを返します。
当然ですが、両方のパーサの出力が同じ型である必要があります。

```rust
use combine::{Parser, token};

let sign = token('+').or(token('-'));
// Output = char
```

これで`+`か`-`にマッチし、マッチした文字を返すというパーサになっています。

`or`は以下のような感じで繋げていけば、1が失敗したら2、2も失敗したら3というパーサを作ることができます。

```rust
parser1.or(parser2).or(prser3)
```

任意の数のパーサから選択したい場合は、パーサの配列を受け取る`combine::choice`が使えます。

### 注意点

ここで注意が必要なのが、パフォーマンスの向上をはかるため、`LL(1)`でない、つまり1文字以上の先読みが必要な文法をパースするには`try`コンビネータ[^try]が必要となっている点です。`a.or(b)`などとしていてaが複数の文字を読んでから失敗すると、失敗した時点で残っている入力が後続のパーサに渡されることになります。`try(a).or(b)`のように`try`で包めばよしなにしてくれます。

[^try]: 標準ライブラリのtryマクロとは別物です。マクロと関数は名前空間が分かれているので衝突することはありません。

## 数字列

次に数字列のパーサ。

```rust
use combine::{Parser, many1};
use combine::char::digit;

let number = many1::<Vec<char>, _>(digit())
// Output = Vec<char>
```

`many1`に型引数を与えていますが(他の箇所から推論できるなら不要)、これは`many1`に渡したパーサを複数回適用した結果を格納するためのコレクション型です。`FromIterator<char>`を実装していれば何でも構わないので、`Vec<char>`、`String`、`HashSet<char>`などが使えます。イテレータの`.collect()`と同じですね。

次に、各桁の数字が入った`Vec<char>`を`i64`に変換する関数を`map`します。これで符号のない整数のパーサができました。

```rust
let number = many1::<Vec<char>, _>(digit())
    .map(|ds| {
        ds.into_iter()
            .map(|c| c.to_digit(10).unwrap() as i64)
            .fold(0, |acc, x| acc * 10 + x)
    });
// Output = i64
```

この2つのパーサを合体して、符号付き整数のパーサを作ります。符号は省略できるので、`optional`を適用しておきましょう。パーサがパースに失敗する場合でも、`optional`で包めば失敗する代わりに`None`が出力されます。

```rust
use combine::optional;

(optional(sign), number)
// Output = (Option<char>, i64)
```

`Parser`トレイトはパーサのタプルに対しても実装されています。各要素のパーサを順番に適用し、それぞれの結果をまたタプルにして返すパーサになります。

`Parser::and`を使うこともできます(2要素のタプルと同じです)。

```rust
optional(sign).and(number)
// Output = (Option<char>, i64)
```

あとは、符号`Option<char>`を見て`i64`の符号を反転させる関数を`map`すればおしまい。

```rust
use combine::optional;

let signed_number = (optional(sign), number)
    .map(|(s, num)| {
        match s {
            None | Some('+') => num,
            Some('-') => -num,
            _ => unreachable!(),
        }
    });
```

## 試してみる

ここまでで作った符号付き整数パーサを試してみましょう。

```rust
extern crate combine;

use combine::{Parser, token, optional, many1};
use combine::char::digit;

fn main() {  
    let sign = optional(token('+').or(token('-')));

    let number = many1::<Vec<char>, _>(digit())
        .map(|ds| {
            ds.into_iter()
                .map(|c| c.to_digit(10).unwrap() as i64)
                .fold(0, |acc, x| acc * 10 + x)
        });

    let mut signed_number = (sign, number)
        .map(|(s, num)| {
            match s {
                None | Some('+') => num,
                Some('-') => -num,
                _ => unreachable!(),
            }
        });

    println!("{:?}", signed_number.parse("-1024"));
}
```

`Parser::parse`を呼ぶにはmutでなくてはならないことに注意してください。普通はパーサの状態は変化しませんが、エラー処理に必要だったり、状態を持つパーサを作りたい場合があったりするためです(ドキュメントに[string interiningを行う例](https://docs.rs/combine/2.1.0/combine/combinator/fn.env_parser.html)が載っています)。

```:出力結果
Ok((-1024, ""))
```

パースに成功して、結果と残りの文字列が出てきました。次は、わざとパースエラーを発生させてみましょう。`ParseError`は[`Display`](https://doc.rust-lang.org/nightly/std/fmt/trait.Display.html)を実装しているので、`unwrap_err`でエラーを取り出して表示してみます。

```rust
println!("{}", signed_number.parse("abc").unwrap_err());
```

```:出力結果
Parse error at 94543405371245
Unexpected `a`
Expected `digit`
```

なんとポインタでエラー発生位置が表示されました。前述した`State`を使えば実行時コストと引き換えに行・桁でエラー位置を教えてもらうことができます。

```rust
println!("{}", signed_number.parse(State::new("abc")).unwrap_err());
```

```
Parse error at line: 1, column: 1
Unexpected `a`
Expected `digit`
```

## 1\_234\_567

TOMLでは、長い数値リテラルをわかりやすくするため桁の間に`_`を挿入することを許しています。ただし`_`が連続してはいけません。これをcombineで実装してみます。

正規表現で考えると`\d+(_\d+)*`という感じでしょうか。これをcombineのコンビネータで表現すれば

```rust
use combine::{Parser, many1, many};
use combine::char::{char, digit};
use std::iter;

many1(digit())
    .and(many(token('_').with(many1(digit()))))
// Output = (Vec<char>, Vec<Vec<char>>)
```

となります。`Parser::with`メソッドはそのパーサの結果を捨て、引数にとったパーサの出力を最終的な出力とするパーサを返します。

この結果を数値に変換する関数を`map`して完成です。

```rust
let number = many1(digit())
    .and(many(token('_').with(many1(digit()))))
    .map(|(a, b): (Vec<_>, Vec<Vec<_>>)| {
        a.into_iter()
            .chain(b.into_iter().flat_map(|x| x))
            .map(|x: char| x.to_digit(10).unwrap() as i64)
            .fold(0, |acc, x| acc * 10 + x)
    });
```

`.flat_map(|x| x)`は`Vec<Vec<char>>`と二重になったものからフラットなイテレータ(`Iterator<Item=char>`)を作るために使っています。
よく使う処理なので、わざわざid関数を渡すのが面倒な人は、[`itertools`](https://docs.rs/itertools/*/itertools/index.html)クレートが追加する[`flatten`メソッド](https://docs.rs/itertools/*/itertools/trait.Itertools.html#method.flatten)を使うとよいです。

# 文字列リテラルをパースしてみる

文字列のパースは結構複雑になりそうです。
パースしたいものが何かの間に挟まっていることを確認できる[`between`](https://docs.rs/combine/2.1.0/combine/fn.between.html)、
要素をクロージャ受け取ってマッチするか否かを決められる[`satisfy`](https://docs.rs/combine/2.1.0/combine/fn.satisfy.html)を使えば、
ダブルクオーテーションの中身を取り出すパーサは`between(token('"'), token('"'), many::<String, _>(satisfy(|c| c != '"'))`と書けます。
しかし、文字列リテラルにおいてはエスケープシーケンスなどを考慮する必要があるため、これでは不十分です。

またTOMLでは文字列リテラルが数種類あり、

```
"he\"llo"

"he\"\
 llo"

"""
h\
   e"llo"""

'he"llo'

'''
he"llo'''
```

以上は全て`he"llo`という等しい文字列リテラルとして解釈しなければなりません。

## エスケープシーケンス処理

`between(token('"'), token('"'), *ここ*)`に、`\`が来たら余分に1文字読み込んでエスケープシーケンスを処理するというパーサを書けばいけそうです。
標準のコンビネータでは処理しきれない細かい動作ですが、
`Parser::then`を使うとパーサ出力に応じて次に行う動作を変えることができます。

`then`に渡すクロージャはパーサ出力を受け取りパーサを返す必要があります。
カスタムパーサを作る手っ取り早い方法は`combine::parser`関数です。これは入力を受け取り`ParserResult`を返す関数を`Parser`に変換する関数です。
エスケープシーケンスが始まったら、これに渡す関数のなかでさらにパースを1文字進めます。

```rust
use combine::{Parser, any, satisfy, parser};
use combine::primitives::Consumed;

satisfy(|c| c != '"')
    .then(|c| {
        parser(move |input| {
            if c == '\\' {
                any()
                    .map(|d| match d {
                        '\\' => '\\',
                        '"' => '"',
                        'n' => '\n',
                        _ => unimplemented!(),
                    })
                    .parse_stream(input)
            } else {
                Ok((c, Consumed::Empty(input)))
            }
        })
    })
```

`ParserResult`を返すのは`Parser::parse_stream`なのですが、今まで使ってきた`Parser::parse`の返り値と異なって「パーサが入力を消費したか」という情報が含まれています。この情報が必要となるパース処理の途中に使われるものだと思われます(今ひとつよく分かってません)。

実際に文字列リテラルをパースしてみます。

```rust
extern crate combine;
use combine::{Parser, any, token, between, many, satisfy, parser};
use combine::primitives::Consumed;

fn main() {
    let quoted = many::<String, _>(satisfy(|s| s != '"').then(|c| {
        parser(move |input| if c == '\\' {
            any()
                .map(|d| match d {
                    '\\' => '\\',
                    '"' => '"',
                    'n' => '\n',
                    _ => unimplemented!(),
                })
                .parse_stream(input)
        } else {
            Ok((c, Consumed::Empty(input)))
        })
    }));

    let mut string = between(token('"'), token('"'), quoted);

    assert_eq!(string.parse("\"hello\"").unwrap().0, "hello");
    assert_eq!(string.parse("\"he\\\"llo\"").unwrap().0, "he\"llo");
}
```

combineのドキュメントには[別のやり方](https://docs.rs/combine/2.1.0/combine/primitives/enum.Consumed.html#method.combine)も書かれています。
こちらは作るパーサに`satisfy`を含めている例ですね。

数値リテラルに`_`が含まれている場合のパースは単純なので既存のコンビネータを使って実装しましたが、同じように`then`を使って読み飛ばす実装でも出来そうです。

## 複数行文字列(`"""`)

TOMLにおける複数行文字列はこんな感じです。

```
"""
he\
    llo"""

# => "\"hello\""
```

* `\`および制御文字のみエスケープが要る、`"`はそのまま書ける(`"""`という並びが出来ると文字列が閉じられるので、その場合はエスケープする)
* 開始側`"""`直後の改行は無視される
* `\`+改行 以降のホワイトスペース(改行含む)が無視される

というものです。

エスケープ処理は前節と同様です。クオーテーションが`"""`と3文字あるため先読みを行う必要があります。

```rust
use combine::{Parser, any, parser, not_followed_by, many};
use combine::char::string;
use combine::primitives::Consumed;

// クオート内の各文字のパーサ
let maybe_escaped = any().then(|c| {
    parser(move |input| if c == '\\' {
        any()
            .map(|d| match d {
                '\\' => '\\',
                '"' => '"',
                _ => unimplemented!(),
            })
            .parse_stream(input)
    } else {
        Ok((c, Consumed::Empty(input)))
    })
});
// Output = char

// クオート内のパーサ
let quoted = many::<String, _>(try(
        not_followed_by(string("\"\"\"")).with(maybe_escaped)
    ));
// Output = String
```

`not_followed_by`は与えられたパーサがパースに成功しなかった場合にのみ成功するパーサです。`try`と同様、任意の長さの先読みが可能です。

ここに、`\\`+改行+空白を無視する(`s/\\\n\s*//`)という処理を追加します。まず、このパターンにマッチするパーサを書きます。

```rust
use combine::{Parser, token, skip_many, satisfy};
use combine::char::newline;

let space_skip = (token('\\'), newline(), skip_many(satisfy(|c| c == ' ' || c == '\t' || c == '\n' || c == '\r')));
```

このパーサが失敗しても文字列のパース自体が失敗する必要はないので`optional`で包みます。また、このパーサは先読みが必要(`\`の次に改行が来るか否かを判定する必要がある)ため`try`を使います。以上でできたものを`Parser::skip`で飛ばします。


```rust
let quoted = optional(newline()).with(many::<String, _>(try(not_followed_by(string("\"\"\""))
    .skip(optional(try(space_skip)))
    .with(maybe_escaped))));
// Output = String

let mut multiline_string = between(string(r#"""""#), string(r#"""""#), inquote);
// Output = String

assert_eq!(string.parse(State::new(r#""""
h""e\\ll\
   o""""#)).unwrap().0,
           r#"h""e\llo"#);
```

複数行文字列のパーサが出来ました!

## リテラル文字列 (`'`)

リテラル文字列(`'`で囲ったもの)はエスケープが無いため、`between(token('\''), token('\''), satisfy(|c| c != '\''))`で済みますね。リテラル複数行文字列もエスケープと行末`\`による空白のスキップが無いだけで同様です。

# パーサを返す関数を作る

ここまではコンビネータで作ったパーサを`let`で変数に束縛していましたが、実際に使うときはパーサを返す関数を用意しておく(combineの組み込みパーサがそうなっているように)と便利そうですね。

```rust
struct IntegerLiteral<I>(PhantomData<fn(I) -> I>);

impl<I: Stream<Item = char>> Parser for IntegerLiteral<I> {
    type Input = I;
    type Output = i64;

    fn parse_stream(&mut self, input: I) -> ParseResult<i64, I> {
        let sign = optional(token('+').or(token('-')));

        let number = many1::<Vec<char>, _>(digit())
            .map(|ds| {
                ds.into_iter()
                    .map(|c| c.to_digit(10).unwrap() as i64)
                    .fold(0, |acc, x| acc * 10 + x)
            });

        let mut signed_number = (sign, number)
            .map(|(s, num)| {
                match s {
                    None | Some('+') => num,
                    Some('-') => -num,
                    _ => unreachable!(),
                }
            });

        signed_number.parse_stream(input)
    }
}

fn integer_literal<I: Stream<Item=char>>() -> IntegerLiteral<I> {
    IntegerLiteral(PhantomData)
}
```

パーサ型を定義して、`Parser`を実装しています。いちいち型を定義するのが面倒だという場合は、作ったパーサをそのまま返す関数を作ることもできます。

```rust
fn integer_literal<I: 'static + Stream<Item=char>>() -> Box<Parser<Input = I, Output = i64>> {
    let sign = optional(token('+').or(token('-')));

    let number = many1::<Vec<char>, _>(digit())
        .map(|ds| {
            ds.into_iter()
                .map(|c| c.to_digit(10).unwrap() as i64)
                .fold(0, |acc, x| acc * 10 + x)
        });

    let signed_number = (sign, number)
        .map(|(s, num)| {
            match s {
                None | Some('+') => num,
                Some('-') => -num,
                _ => unreachable!(),
            }
        });

    Box::new(signed_number)
}
```

パーサを返すにはイテレータを返す際と同種の問題があります。パーサの型は複雑で[^type]、型を書くのが大変です。しかもこの場合`map`によるクロージャを含んでいるため記述できないので`Box`化するか`impl Trait`を使う必要があります。

[^type]: `signed_number`の型は`combine::combinator::Map<(combine::combinator::Optional<combine::combinator::Or<combine::combinator::Token<I>, combine::combinator::Token<I>>>, combine::combinator::Map<combine::combinator::Many1<std::vec::Vec<char>, combine::char::Digit<I>>, [closure@src/main.rs:41:14: 45:10]>), [closure@src/main.rs:48:14: 54:6]>`となっています。

`Parser::parse_stream`相当の関数を単体で用意することでもパーサを表現することもできます。使うときは文字列のパースで使った`parser`関数を通すことで`Parser`になります。

```rust
fn main() {
    assert_eq!(parser(integer_literal).parse("1234").unwrap(),
               1234);
}

fn integer_literal<I: Stream<Item=char>>(input: I) -> ParseResult<i64, I> {
    ...
    
    (sign, number)
        .map(|(s, num)| {
            match s {
                None | Some('+') => num,
                Some('-') => -num,
                _ => unreachable!(),
            }
    }).parse_stream(input)
}
```

# おわりに

combineはデザインも綺麗で個人的にはけっこう好きなライブラリです。[ドキュメント](https://docs.rs/combine/)が充実しているのも有り難いです。