Rust で nom を使って Pseudo-Boolean のインスタンスファイルのパーサーを作ってみた

# はじめに

　初めて nom を使ってみて最初の数時間ほどは何もわからず戸惑ってしまったので，同じく初めて使う方の参考になればと記事にしてみました．
　以下では，適当にごまかしつつ部分的に細かい解説もしていますが，とりあえず
 
:::note
BNF 等のフォーマットの定義をほぼそのままコードとして書くだけでパーサーを実装することができる
:::

という雰囲気が伝われば幸いです．

## nom について

　パーサーコンビネータというものだそうで，その名の通り，パーサーを組み合わせて複雑なパーサーを作ることができます．

## OPB フォーマットについて

　Pseudo-Boolean のインスタンスを記述するためのフォーマットです．

https://www.cril.univ-artois.fr/PB24/OPBgeneral.pdf

**例** (適当に持ってきた例があまり良くなかったが，係数は 1, -1 以外も可)
```
* hello world
1 x1 +1 x2 >= 1 ;
-1 x2 +1 x4 +1 x5 >= 0 ;
1 x3 -1 x4 +1 x5 >= 0 ;
1 x4 -1 x5 >= 0 ;
-1 x4 -1 x5 >= -1 ;
```

# パーサーの実装

　nom では ```Parser``` トレイトを実装している型がパーサーとして扱われます．最も基本的なパーサーは関数オブジェクトで，例えば
```rust
fn f(input: &str) -> IResult<&str, usize>
```
のように，文字列(```&str```型)を受け取って，その結果(ここでは仮に ```usize``` 型)と残りの文字列(```&str```型)とを ```IResult``` 型として返す関数はパーサーになります．

　以下では， BNF によるフォーマットの定義と対応するパーサーの実装とを併記しながらパーサーの各要素を紹介します．

<details><summary><b>【細かい前提】</b></summary>

* OPB フォーマットの仕様のうち，線形制約の充足可能性問題を扱うための最小限のものだけを実装しています
* BNF での定義に微妙なところもあるのですが，基本的には定義に忠実な実装としています
* 文字列をパースすると同時にオブジェクトを構築する設計になっています
    * 文字列のパースと型変換を分離するという考え方もあるかもしれません
* ```&str``` をパースします
* エラーハンドリングはしません
* nom のバージョンは 8.0.0 を想定しています

</details>

## unsigned_integer

　数字の 1 回以上の繰り返しで，符号なし整数を表します．

```
<unsigned_integer> ::= <digit> | <digit> <unsigned_integer>
```

　整数型を返すパーサーを実装します．

```rust
fn unsigined_integer<UIntT: Integer + FromStr>(input: &str) -> IResult<&str, UIntT> {
    map_res(
        digit1,
        str::parse
    ).parse(input)
}
```

* ```digit1``` は数字の 1 回以上の繰り返しにマッチするパーサーで，マッチした部分文字列を返します
* ```str::parse``` は Rust の標準ライブラリの関数で， ```str``` を ```UInt``` に変換します
    * 文字型から整数型への変換では失敗する可能性があるため，```str::parse``` が返す型は ```UInt``` ではなく ```Result``` です
* ```map_res``` は，第一引数のパーサーの結果に第二引数の関数を適用します
    * 関数が ```Result``` 型を返す場合に使用するのが ```map_res``` で，そうでない場合（例えば ```UInt``` 型を返す場合）には ```map``` を使います

## integer

　符号（"+" または "-"）と 1 回以上の数字の繰り返しで，符号付き整数を表します．

```
<integer> ::= <unsigned_integer> | "+" <unsigned_integer> | "-" <unsigned_integer>
```

　符号付き整数型を返すパーサーを実装します．なお， BNF では \<unsigned_integer\> を使って定義していますが，実装では ```unsigned_integer``` を使っていません．（逆に面倒になるので）

```rust
fn integer<IntT: Signed + FromStr>(input: &str) -> IResult<&str, IntT> {
    map_res(
        alt((
            digit1,
            recognize((tag("+"), digit1)),
            recognize((tag("-"), digit1)),
        )),
        str::parse
    ).parse(input)
}
```

* ```tag``` は，引数で与えられた特定の文字列にマッチするパーサーです
* ```recognize``` は，入力された文字列が，引数で与えられたパーサーに順にマッチすればマッチした部分文字列を返すパーサーです
* ```alt``` は，引数で与えられたいずれかのパーサーがマッチすればその結果を返します


<details><summary><b>【別の書き方】</b></summary>

　上記の例では ```alt``` の結果を ```map_res``` に渡していますが，逆にすることも可能です．

```rust
fn integer1<IntT: Signed + FromStr>(input: &str) -> IResult<&str, IntT> {
    alt((
        map_res(digit1, str::parse),
        map_res(recognize((tag("+"), digit1)), str::parse),
        map_res(recognize((tag("-"), digit1)), str::parse),
    ))
    .parse(input)
}
```

　また，あるフォーマットの BNF による表現は必ずしも一意ではなく，\<integer\> を以下のように定義することも可能です．
```
<integer> ::= ["+" | "-"] <unsigned_integer>
```

　この定義どおりに実装すると以下のようになります．

```rust
fn integer2<IntT: Signed + FromStr>(input: &str) -> IResult<&str, IntT> {
    map_res(
        recognize((opt(alt((tag("+"), tag("-")))), digit1)),
        str::parse,
    ).parse(input)
}
```

</details>

## variable
　"x"のあとに 1 回以上の数字の繰り返しで，変数の識別子を表します．

```
<variableName> ::= "x" <unsigned_integer>
```

　先程実装した ```unsigned_integer``` を使って， ```Variable``` という構造体を返すパーサーを実装します． 

```rust
pub struct Variable {
    pub index: usize,
}

fn variable(input: &str) -> IResult<&str, Variable> {
    map(
        (tag("x"), unsigined_integer),
        |(_, index)| Variable { index }
    ).parse(input)
}
```

* ```map``` の第一引数はタプルです
    * nom ではパーサーのタプルはパーサーになります
        * 以前はタプルをパーサーに変換するための ```tuple``` という関数があったようですが，8.0.0 から廃止されています． 
    * 1つ目のパーサーを呼び出して，マッチすれば残りの文字列で 2 つ目のパーサーを呼び出し...ということを繰り返して，すべてのパーサーにマッチすればそれらの結果をタプルで返します
    * ```recognize((f, g))```と```(f, g)```の違いは，f と g に順にマッチしたときに，部分文字列を返すのか，f と g の結果をタプルで返すのかになります
* ```map``` の第二引数はクロージャーです
    * ```tag("x")``` の結果(常に```"x"```)は使わないので ```_``` とし，```unsigned_integer``` の結果を ```index``` として受け取って ```Variable``` 型のインスタンスを構築します

## weighted_term
　\<integer\> と \<variableName\> の組で，項（定数×変数）を表します．

```
<weightedterm> ::= <integer> <oneOrMoreSpace> <term> <oneOrMoreSpace>
<term> ::= <variableName>    ; for linear constraint
```

　```integer``` と ```variable``` を使って， ```WeightedTerm``` という構造体を返すパーサーを実装します．
　OPB フォーマットでは，線形制約の場合の \<term\> と \<variableName\> は同じとされているため， ```WeightedTerm``` のフィールドの名前は ```term``` ですが，型を ```Variable``` としています．

```rust
pub struct WeightedTerm {
    pub weight: i64,
    pub term: Variable,
}

fn weighted_term(sinput: &str) -> IResult<&str, WeightedTerm> {
    map(
        (integer, space1, variable, space1),
        |(weight, _, term, _)| WeightedTerm { weight, term },
    ).parse(input)
}
```

　使っている機能はこれまでに紹介したものだけです．

<details><summary><b>【余談】preceded, terminated, delimited を使わない理由</b></summary>

　以下のように，クロージャーの引数を実際に使うものだけにする（```_``` を使わない）ことも可能なのですが，「複数の書き方があるが，どの書き方にも必然性がない」のが気持ち悪くて使っていません．

```rust
    map(
        (terminated(integer, space1), terminated(variable_name, space1)),
        |(weight, term)| WeightedTerm { weight, term },
    ).parse(input)
```

```rust
    map(
        (terminated((terminated(integer, space1), variable_name), space1)),
        |(weight, term)| WeightedTerm { weight, term },
    ).parse(input)
```

```rust
    map(
        (integer, delimited(space1, variable_name, space1)),
        |(weight, term)| WeightedTerm { weight, term },
    ).parse(input)
```
</details>

## sum
　\<weightedterm\> の 1 回以上の繰り返しで，変数の線型結合を表します．

```
<sum> ::= <weightedterm> | <weightedterm> <sum>
```

　新しい構造体を定義することはせず，単に ```Vec<WeightedTerm>``` を返すパーサーを実装します．

```rust
fn sum(input: &str) -> IResult<&str, Vec<WeightedTerm>> {
    many1(weighted_term).parse(input)
}
```

* ```many1``` は，入力された文字列を，引数で与えたパーサーに繰り返し入力し，その結果を ```Vec``` に格納して返します

## relational_operator
　等号または不等号です．

```
<relational_operator> ::= "=" | ">="
```

　enum を返すパーサーを実装します．

```rust
pub enum RelationalOperator {
    Equal,
    GreaterOrEqual,
}

fn relational_operator(input: &str) -> IResult<&str, RelationalOperator> {
    alt((
        map(tag("="), |_| RelationalOperator::Equal),
        map(tag(">="), |_| RelationalOperator::GreaterOrEqual),
    )).parse(input)
}
```

<details><summary><b>【別の書き方】</b></summary>

　以下のような書き方も可能ですが， enum に変換するなら上記の書き方が綺麗だと思います．
```rust
    map(
        alt((tag("="), tag(">="))),
        |s| match s {
            "=" => RelationalOperator::Equal,
            ">=" => RelationalOperator::GreaterOrEqual,
            _ => unreachable!(),
        },
    ).parse(input)
```

</details>

## constraint
　\<sum\> と \<relational_operator\> と \<integer\> の組で制約条件を表します．[^constraint_bug]
[^constraint_bug]:もとの定義には [\<EOL\>] がないのですが，実際のデータでは ";" のあとに改行が存在しているので追加しています．なお，OPB フォーマットのドキュメントの \<comment\> の定義に合わせて， \<constraint\> の末尾に改行を設定していますが，繰り返し(\<sequence_of_comment_or_constraint\>)の定義の中で区切り文字を定義した方が綺麗になるのではないかと思っています．

```
<constraint>::= <sum> <relational_operator> <zeroOrMoreSpace> <integer> <zeroOrMoreSpace> ";" [<EOL>]
```

　実装はこれまで紹介した機能しか使っていないので省略します．

## comment
　省略

## comment_or_constraint
　省略

## sequence_of_comment_or_constraint
　省略

# OPB フォーマットの読み込み処理の実装

　コメントと制約条件をパースする ```sequence_of_comment_or_constraint``` というパーサーを作ったので，これを使って実際に文字列をパースし，```PBProblem``` という構造体を返す関数を実装します．


```rust
pub struct PBProblem {
    pub constraints: Vec<Constraint>,
}

pub fn read_opb(input: &str) -> PBProblem {
    // パース
    let (residual, sequence_of_comment_or_constraint) =
        sequence_of_comment_or_constraint(input).unwrap();

    // 最後まで解釈できたかをチェック(今回はエラーハンドリングなし)
    assert!(residual == "", "{}", residual);

    // Constraint だけを抽出
    let constraints = sequence_of_comment_or_constraint
        .into_iter()
        .filter_map(|record| match record {
            CommentOrConstraint::Comment(..) => None,
            CommentOrConstraint::Constraint(constraint) => Some(constraint),
        })
        .collect();

    // PBProblem を構築して返す
    return PBProblem { constraints };
}
```

　なお，今回はファイル全体をまとめてパースする，大きいパーサーを実装しましたが，行のパースと行の中のパースを分けて，エラーが発生した際には行番号をユーザーに知らせるようにした方が実用的かもしれません．

# コード全体

<details><summary>read_opb.rs</summary>

```rust
use std::str::FromStr;

use nom::{
    IResult, Parser,
    branch::alt,
    bytes::complete::tag,
    character::{
        complete::{digit1, newline, not_line_ending, space1},
        streaming::space0,
    },
    combinator::{map, map_res, opt, recognize},
    multi::many1,
};
use num::{Integer, Signed};

#[derive(Clone, Debug)]
pub struct PBProblem {
    pub constraints: Vec<Constraint>,
}

#[derive(Clone, Debug)]
pub enum CommentOrConstraint {
    Comment(String),
    Constraint(Constraint),
}

#[derive(Clone, Debug)]
pub struct Constraint {
    pub sum: Vec<WeightedTerm>,
    pub relational_operator: RelationalOperator,
    pub rhs: i64,
}

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum RelationalOperator {
    Equal,
    GreaterOrEqual,
}

#[derive(Clone, Debug)]
pub struct WeightedTerm {
    pub weight: i64,
    pub term: Term,
}

pub type Term = Variable;

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct Variable {
    pub index: usize,
}

pub fn read_opb(input: &str) -> PBProblem {
    // パース
    let (residual, sequence_of_comment_or_constraint) =
        sequence_of_comment_or_constraint(input).unwrap();

    // 最後まで解釈できたかをチェック(今回はエラーハンドリングなし)
    assert!(residual == "", "{}", residual);

    // Constraint だけを抽出
    let constraints = sequence_of_comment_or_constraint
        .into_iter()
        .filter_map(|record| match record {
            CommentOrConstraint::Comment(..) => None,
            CommentOrConstraint::Constraint(constraint) => Some(constraint),
        })
        .collect();

    // PBProblem を構築して返す
    return PBProblem { constraints };
}

fn sequence_of_comment_or_constraint(input: &str) -> IResult<&str, Vec<CommentOrConstraint>> {
    // <sequence_of_comments_or_constraints> ::= <comment_or_constraint> [<sequence_of_comments_or_constraints>]
    many1(comment_or_constraint).parse(input)
}

fn comment_or_constraint(input: &str) -> IResult<&str, CommentOrConstraint> {
    // <comment_or_constraint> ::= <comment> | <constraint>
    alt((
        map(comment, CommentOrConstraint::Comment),
        map(constraint, CommentOrConstraint::Constraint),
    ))
    .parse(input)
}

fn comment(input: &str) -> IResult<&str, String> {
    // <comment> ::= "*" <any_sequence_of_characters_other_than_EOL> <EOL>
    map((tag("*"), not_line_ending, newline), |(_, comment, _)| {
        str::to_string(comment)
    })
    .parse(input)
}

fn constraint(input: &str) -> IResult<&str, Constraint> {
    // <constraint>::= <sum> <relational_operator> <zeroOrMoreSpace> <integer> <zeroOrMoreSpace> ";"
    // ↑おそらく定義のミスで，実際のデータでは";"の後に改行がある
    map(
        (
            sum,
            relational_operator,
            space0,
            integer,
            space0,
            tag(";"),
            opt(newline),
        ),
        |(sum, relational_operator, _, rhs, _, _, _)| Constraint {
            sum,
            relational_operator,
            rhs,
        },
    )
    .parse(input)
}

fn relational_operator(input: &str) -> IResult<&str, RelationalOperator> {
    // <relational_operator> ::= "=" | ">="
    alt((
        map(tag("="), |_| RelationalOperator::Equal),
        map(tag(">="), |_| RelationalOperator::GreaterOrEqual),
    ))
    .parse(input)
}

fn sum(input: &str) -> IResult<&str, Vec<WeightedTerm>> {
    // <sum> ::= <weightedterm> | <weightedterm> <sum>
    many1(weighted_term).parse(input)
}

fn weighted_term(input: &str) -> IResult<&str, WeightedTerm> {
    // <weightedterm> ::= <integer> <oneOrMoreSpace> <term> <oneOrMoreSpace>
    // <term>::=<variableName>  # for linear instances
    map(
        (integer, space1, variable_name, space1),
        |(weight, _, term, _)| WeightedTerm { weight, term },
    )
    .parse(input)
}

fn variable_name(input: &str) -> IResult<&str, Variable> {
    // <variableName> ::= "x" <unsigned_integer>
    map((tag("x"), unsigined_integer), |(_, index)| Variable {
        index,
    })
    .parse(input)
}

fn integer<IntT: Signed + FromStr>(input: &str) -> IResult<&str, IntT> {
    // <integer> ::= <unsigned_integer> | "+" <unsigned_integer> | "-" <unsigned_integer>
    map_res(
        alt((
            digit1,
            recognize((tag("+"), digit1)),
            recognize((tag("-"), digit1)),
        )),
        str::parse,
    )
    .parse(input)
}

fn unsigined_integer<UIntT: Integer + FromStr>(input: &str) -> IResult<&str, UIntT> {
    // <unsigned_integer> ::= <digit> | <digit><unsigned_integer>
    map_res(digit1, str::parse).parse(input)
}

// 別の実装

#[cfg(test)]
fn integer1<IntT: Signed + FromStr>(input: &str) -> IResult<&str, IntT> {
    // integer の別の実装 1
    // <integer> ::= <unsigned_integer> | "+" <unsigned_integer> | "-" <unsigned_integer>
    alt((
        map_res(digit1, str::parse),
        map_res(recognize((tag("+"), digit1)), str::parse),
        map_res(recognize((tag("-"), digit1)), str::parse),
    ))
    .parse(input)
}

#[cfg(test)]
fn integer2<IntT: Signed + FromStr>(input: &str) -> IResult<&str, IntT> {
    // integer の別の実装 2
    // <integer> ::= ["+" | "-"] <unsigned_integer>
    map_res(
        recognize((opt(alt((tag("+"), tag("-")))), digit1)),
        str::parse,
    )
    .parse(input)
}

#[cfg(test)]
mod test {

    use std::{fmt::Debug, str::FromStr};

    use nom::IResult;
    use num::{Integer, Signed};

    use crate::read_opb::{integer1, unsigined_integer};

    use super::{Variable, integer, integer2, read_opb};

    #[test]
    fn test_unsigined_integer() {
        fn run<UIntT: Integer + FromStr + Copy + Debug + TryFrom<i32>>(
            integer: impl Fn(&str) -> IResult<&str, UIntT>,
        ) where
            <UIntT as TryFrom<i32>>::Error: Debug,
        {
            let v = 123.try_into().unwrap();
            assert_eq!(integer("123"), Ok(("", v)));
            assert_eq!(integer("123x"), Ok(("x", v)));
            assert_eq!(integer("123.45"), Ok((".45", v)));

            assert!(integer("").is_err());
            assert!(integer("+").is_err());
            assert!(integer("-").is_err());
            assert!(integer("+123").is_err());
            assert!(integer("-123").is_err());
            assert!(integer("+ 123").is_err());
            assert!(integer("- 123").is_err());
        }

        run(unsigined_integer::<i64>);
        run(unsigined_integer::<u64>);
        run(unsigined_integer::<isize>);
        run(unsigined_integer::<usize>);
    }

    #[test]
    fn test_integer() {
        fn run<IntT: Signed + FromStr + Copy + Debug + TryFrom<i32>>(
            integer: impl Fn(&str) -> IResult<&str, IntT>,
        ) where
            <IntT as TryFrom<i32>>::Error: Debug,
        {
            let v = 123.try_into().unwrap();
            assert_eq!(integer("123"), Ok(("", v)));
            assert_eq!(integer("123x"), Ok(("x", v)));
            assert_eq!(integer("+123"), Ok(("", v)));
            assert_eq!(integer("-123"), Ok(("", -v)));
            assert_eq!(integer("123.45"), Ok((".45", v)));

            assert!(integer("").is_err());
            assert!(integer("+").is_err());
            assert!(integer("-").is_err());
            assert!(integer("+ 123").is_err());
            assert!(integer("- 123").is_err());
        }

        run(integer::<i64>);
        run(integer::<isize>);
        run(integer1::<i64>);
        run(integer1::<isize>);
        run(integer2::<i64>);
        run(integer2::<isize>);
    }

    #[test]
    fn test_variable() {
        use super::variable_name;
        assert_eq!(variable_name("x1"), Ok(("", Variable { index: 1 })));
        assert_eq!(
            variable_name("x123456789"),
            Ok(("", Variable { index: 123456789 }))
        );
        assert!(variable_name("").is_err());
        assert!(variable_name("12").is_err());
        assert!(variable_name("y123").is_err());
        assert!(variable_name("x").is_err());
    }

    #[test]
    fn test_weighted_term() {
        use super::weighted_term;

        let (s, t) = weighted_term("3 x1 ").unwrap();
        assert!(s == "");
        assert!(t.weight == 3);
        assert!(t.term.index == 1);

        let (s, t) = weighted_term("-3 x1 ").unwrap();
        assert!(s == "");
        assert!(t.weight == -3);
        assert!(t.term.index == 1);

        assert!(weighted_term("3 x1").is_err());
        assert!(weighted_term("3x1").is_err());
        assert!(weighted_term("x1 ").is_err());
        assert!(weighted_term("x1").is_err());
    }

    #[test]
    fn test_opb() {
        let input = r"* comment
1 x1 +1 x2 >= 1 ;
-1 x2 +1 x4 +1 x5 >= 0 ;
1 x3 -1 x4 +1 x5 >= 0 ;
1 x4 -1 x5 >= 0 ;
-1 x4 -1 x5 >= -1 ;
";
        let result = read_opb(input);
        eprintln!("{:?}", result);
        assert!(result.is_ok());
    }
}
```

</details>