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

はじめに

　初めて nom を使ってみて最初の数時間ほどは何もわからず戸惑ってしまったので，同じく初めて使う方の参考になればと記事にしてみました．
　以下では，適当にごまかしつつ部分的に細かい解説もしていますが，とりあえず

BNF 等のフォーマットの定義をほぼそのままコードとして書くだけでパーサーを実装することができる

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

nom について

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

OPB フォーマットについて

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

例 (適当に持ってきた例があまり良くなかったが，係数は 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 トレイトを実装している型がパーサーとして扱われます．最も基本的なパーサーは関数オブジェクトで，例えば

fn f(input: &str) -> IResult<&str, usize>

のように，文字列(&str型)を受け取って，その結果(ここでは仮に usize 型)と残りの文字列(&str型)とを IResult 型として返す関数はパーサーになります．

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

【細かい前提】

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

unsigned_integer

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

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

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

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 を使っていません．（逆に面倒になるので）

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 は，引数で与えられたいずれかのパーサーがマッチすればその結果を返します

【別の書き方】

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

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>

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

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

variable

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

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

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

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 としています．

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)
}

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

【余談】preceded, terminated, delimited を使わない理由

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

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

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

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

sum

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

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

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

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

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

relational_operator

　等号または不等号です．

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

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

pub enum RelationalOperator {
    Equal,
    GreaterOrEqual,
}

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

【別の書き方】

　以下のような書き方も可能ですが， enum に変換するなら上記の書き方が綺麗だと思います．

    map(
        alt((tag("="), tag(">="))),
        |s| match s {
            "=" => RelationalOperator::Equal,
            ">=" => RelationalOperator::GreaterOrEqual,
            _ => unreachable!(),
        },
    ).parse(input)

constraint

　<sum> と <relational_operator> と <integer> の組で制約条件を表します．¹

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

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

comment

　省略

comment_or_constraint

　省略

sequence_of_comment_or_constraint

　省略

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

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

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 };
}

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

コード全体

read_opb.rs

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());
    }
}

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