👨‍🦱

RustでTOMLパーサーを実装してみる

2023/05/15に公開

概要

Rustの勉強をしていると、Cargo.tomlというファイルをよく目にすることになります。
このファイルはTOMLという形式で書かれた設定ファイルなのですが、個人的にRustを学び始めるまでこの形式にはあまり馴染みがありませんでした。

そこで、この記事では勉強も兼ねてRustでTOMLパーサーを実装してみることにします。
Rustの勉強をしつつTOMLへの理解を深めることが出来るので一石二鳥ですね。
また、パーサーの実装というのはスキルとしての汎用性が高いので、簡単なパーサーを実装できるようになっておくと後々色々出来そうです。

TOMLパーサーの実装にはnomというRust製のパーサーコンビネーターライブラリを使いました。
このライブラリは、2023年5月現在Rustのパーサーコンビネーターライブラリーの中で最も有名なもののようなのですが、初心者的には分かりにくい部分もあったのでその点についても出来る範囲で解説します。

本記事の構成は以下の通りです。

  1. TOMLとは何か
  2. パーサーコンビネーターとは何か
  3. nomについて
  4. nomを用いたTOMLパーサーの実装

想定読者

  • Rust勉強用の手ごろな題材を探している人
  • パーサーコンビネーターについて知りたい人
  • nomについて知りたい人
  • TOMLについて知りたい人

TOMLとは何か

TOMLというのはどのような形式なのか、ひとまず公式リポジトリのREADME.mdから重要そうな部分だけを抜粋してみます。

  • ミニマルで読みやすい設定ファイルフォーマットである
  • 曖昧さなしに連想配列[1]に変換できるように設計されている
  • あくまでも設定ファイルフォーマットであって、データのシリアライゼーションのためのものではない

このうち、「読みやすい設定ファイルフォーマット」という点については「まあそうだろうな」という感想ですが、「連想配列に変換できるように設計されている」のは個人的には「そうだったのか...」と思った部分でした。

連想配列に変換できるという部分について具体的に考えてみましょう。例えば以下のようなTOMLファイルがあったとします。

Cargo.toml
[package]
name = "toml_parser"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
nom = "7.1.3"
chrono = "0.4"
maplit = "1.0"

このファイルの内容を対応する連想配列で表すと以下のようになります。

{
    "package": {
        "name": "toml_parser",
        "version": "0.1.0",
        "edition": "2021",
    },
    "dependencies": {
        "nom": "7.1.3",
        "chrono": "0.4",
        "maplit": "1.0",
    },
}

なお、上の例では連想配列のValueとして文字列 ("toml_parser", "0.1.0"など) が使われていますが、TOMLでは他にも様々な型の値をValueとして扱うこともできます。

より詳しく知りたい方には、TOMLの公式ドキュメントを読むことをおすすめします。日本語版もあり、分量的にも短くて読みやすいです。

https://toml.io/ja/v1.0.0-rc.2

パーサーコンビネーターとは何か

言葉の定義

「パーサーコンビネーター」とは何か、広く認められたフォーマルな定義があるかどうかがよく分かっていないのですが、軽く調べた感じでは以下のどちらかの意味合いで使われることが多いのかなと思いました。

  • 1つ以上のパーサーを受け取って、それらを組み合わせたり変換したりした新しいパーサーを返す高階関数
  • 単純なパーサーを高階関数(パーサーコンビネーター)で組み合わせることで複雑なパーサーを作る仕組み

ただ、調べた印象としては「単純なパーサーを高階関数(パーサーコンビネーター)で組み合わせて複雑なパーサーを作る仕組み」の方を指していることの方が多いのかなと思ったので、本記事では前者を指して「コンビネーター」、後者を指して「パーサーコンビネーター」と呼ぶことにしています。[2]

ちなみに、「パーサー」についてですが、本記事では「文字列を受け取って、それをパース(構文解析)した結果を返す関数」のことを指してパーサーと呼ぶことにしています。[3]
パーサーがパースの結果として出力するものは文脈により様々のようですが、本記事ではRustでパーサーを実装するので、何らかのRustの値を出力することになります。

例1: keyとvalueのペアが=で区切られている文字列をパースする

抽象的な話だけでは分かりにくいので、パーサーコンビネーターの働きについて具体的に考えてみましょう。
例えば、以下のような文字列をパースする場合を考えます。

a=1

この文字列はaというkeyと1というvalueのペアを表しています。
この文字列をパースして、keyとvalueのペアを取得するパーサーをnomで実装すると以下のようになります。[4]

use nom::bytes::complete::tag;
use nom::character::complete::{alpha1, digit1};
use nom::sequence::separated_pair;
use nom::IResult;

fn parse_keyval(input: &str) -> IResult<&str, (&str, &str)> {
    separated_pair(alpha1, tag("="), digit1)(input)
}

fn main() {
    let input = "a=1";
    println!("{:?}", parse_keyval(input)); // Ok(("", ("a", "1")))
}

parse_keyvalという関数が今回作ったパーサーで、"a=1"という文字列に適用したときの返り値はOk(("", ("a", "1")))になっています。
Ok(("", ("a", "1")))という返り値の詳細については後ほど説明しますが、とりあえず今はOkの内側の("a", "1")がパーサーの出力であることだけを知っておけば大丈夫です。

よって、parse_keyvalというパーサーを使うことで"a=1"という文字列から、("a", "1")というkeyとvalueのペアを取得することが出来ました。

parse_keyvalを構成する部品について見ていきましょう。
このパーサーは、以下の3つのパーサーをseparated_pairというコンビネーターで組み合わせることで作られています。

  • alpha1: 1文字以上のアルファベットをパースするパーサー
  • tag("="): =をパースするパーサー
  • digit1: 1文字以上の数字をパースするパーサー

separated_pairは、3つのパーサーを受け取って、1つ目と3つ目のパーサーの出力をタプルで返すパーサーを作るコンビネーターです。

例2: 複数のkeyとvalueのペアをパースする

上の例だけだとちょっと単純すぎてイメージが掴みにくいので、もう少し複雑な例を考えてみましょう。
以下のように、keyとvalueのペアが複数個書かれている文字列をパースしたいとします。

a=1
b=2
c=3

ペアの1つ1つは先ほどの例と同じ形式なので、parse_keyvalを部品として流用して以下のように書くことが出来ます。

use nom::bytes::complete::tag;
use nom::character::complete::{alpha1, digit1, line_ending};
use nom::multi::many0;
use nom::sequence::{separated_pair, terminated};
use nom::IResult;

fn parse_multiple_keyval(input: &str) -> IResult<&str, Vec<(&str, &str)>> {
    many0(terminated(parse_keyval, line_ending))(input)
}

fn parse_keyval(input: &str) -> IResult<&str, (&str, &str)> {
    separated_pair(alpha1, tag("="), digit1)(input)
}

fn main() {
    let input = "a=1\nb=2\nc=3\n";
    println!("{:?}", parse_multiple_keyval(input)); // Ok(("", [("a", "1"), ("b", "2"), ("c", "3")]))
}

parse_multiple_keyvalというのがここで新しく作られたパーサーです。
上の例ではペアが1つしかなかったので(&str, &str)というタプルを出力しましたが、今回はペアが複数あるのでVec<(&str, &str)>というベクターを出力しています。
出力の中身を見ると[("a", "1"), ("b", "2"), ("c", "3")]のように複数のkeyとvalueのペアを取得することが出来ています。

parse_multiple_keyvalの実装のために新たに追加された部品は以下の通りです。

  • many0: 0回以上の繰り返しをパースするパーサーを作るコンビネーター
  • terminated: 2つのパーサーを受け取って順番に適用し、1つ目のパーサーの出力だけを返すパーサーを作るコンビネーター
  • line_ending: 改行文字をパースするパーサー

これでもまだ例が単純すぎる気はしますが、単純なパーサーを組み合わせて複雑なパーサーを作っていくというイメージは伝わったのではないでしょうか。

nomについて

既に上でも軽く触れましたが、nomはRust製のパーサーコンビネーターライブラリです。
様々なパーサーやコンビネーターが用意されていて、これらを組み合わせることで各自の用途に応じた複雑なパーサーを作ることが出来ます。

「コンビネーターを使ってパーサーを組み立てていく」というイメージが分かってしまえば基本的な使い方についてはそれ以上説明が必要なことはあまりなく、あとは自分の用途に応じて適切な部品を組み合わせていくだけだと感じています。
ただ、基本的な使い方が分かっても実際にパーサーを作るとなると簡単ではないと感じる場面が多々あるでしょう。

以下では、nomを使う上で初心者が困りそうな点[5]について簡単に説明していきます。

  • どのようなコンビネーターを使っていいか分からない
  • パーサーの返り値とエラーについて

どのようなコンビネーターを使っていいか分からない

nomの中には様々なパーサーやコンビネーターが含まれています。
「コンビネーターを使ってパーサーを組み立てていく」という考え方は理解しやすいものですが、どのような場面でどのようなコンビネーターを使うべきか最初はすぐには思いつかないでしょう。
ということで、自分でも色々と試しつつ、実際の使用例などを見ながらどういう場合にどういうコンビネーターが使われているのかを学んでいくのが良い勉強法だろうと思いました。

nomを勉強するにあたり、役に立った資料を幾つか紹介します。

索引として使うと便利な資料

参考になる実装例

例えば、実装例の資料を読みながらそこで出てきたコンビネーターなどを公式ドキュメントで検索して1つ1つ理解していくとかなり勉強になると思います。
nomの公式ドキュメントは、各コンビネーターに対して具体的な実行例などがしっかりと書かれているのでとても勉強しやすいと感じました。
例として、上の例でも使用したseparated_pairのドキュメントを以下に示します。
https://docs.rs/nom/latest/nom/sequence/fn.separated_pair.html

パーサーの返り値とエラーについて

nomを使い始めて、最初少し分かりづらいと思ったのはパーサーの出力とエラーについてです。
具体的に見ていきましょう。以下は上でも示したkeyとvalueのペアをパースするparse_keyvalの実装です。

use nom::bytes::complete::tag;
use nom::character::complete::{alpha1, digit1};
use nom::sequence::separated_pair;
use nom::IResult;

fn parse_keyval(input: &str) -> IResult<&str, (&str, &str)> {
    separated_pair(alpha1, tag("="), digit1)(input)
}

fn main() {
    let input = "a=1";
    println!("{:?}", parse_keyval(input)); // Ok(("", ("a", "1")))
}

出力の型はIResultという型になっています。これは実はResult型の型エイリアスで、以下のように定義されています。

pub type IResult<I, O, E = error::Error<I>> = Result<(I, O), Err<E>>;

つまり、パースが成功した場合はOk((I, O))を返し、失敗した場合はErr(Err<E>)を返します。

Ok((I, O)): パースが成功した場合

まず成功した場合についてですが、Iは入力データの型(上の例だと&str)、Oはパース結果の型(上の例だと(&str, &str))になります。
Oにはこれまでも説明した通りパース結果が入るのですが、Iには何が入るのでしょうか?

具体例を見てみましょう。次のコードは、parse_keyvalを呼んだときにseparated_pairの内部で実行されているであろう処理を展開したものです。
parse_keyvalで受け取った引数のinputに対して、alpha1, tag("="), digit1の順にパーサーを実行しています。

use nom::bytes::complete::tag;
use nom::character::complete::{alpha1, digit1};

fn parse_keyval(input: &str) -> IResult<&str, (&str, &str)> {
    let (input, key) = alpha1(input)?;
    println!("input: {:?}, key: {:?}", input, key); // input: "=1", key: "a"

    let (input, sep) = tag("=")(input)?;
    println!("input: {:?}, sep: {:?}", input, sep); // input: "1", sep: "="

    let (input, val) = digit1(input)?;
    println!("input: {:?}, val: {:?}", input, val); // input: "", val: "1"

    Ok((input, (key, val)))
}

fn main() {
    let input = "a=1";
    println!("{:?}", parse_keyval(input)); // Ok(("", ("a", "1")))
}

各パーサーも当然IResultを返すので、返ってきたIの値をprintln!でそれぞれ確認してみます。
すると、alpha1"=1"tag("=")"1"digit1""を返しているようです。
つまり、以下のように1個前のパーサーが読み残した部分を次のパーサーが受け取って処理するという仕組みになっていることが分かります。

  1. alpha1は文字列の先頭からアルファベットで構成されている部分を読む。
  2. alpha1が読み残した部分をtag("=")が読む。
  3. tag("=")が読み残した部分をdigit1が読む。

このような順序で処理を行う仕組みになっているので、入力データの読み残しを返す必要があるわけですね。

Err(Err<E>): パースが失敗した場合

失敗した場合の返り値Err(Err<E>)は初見だとちょっと難しく感じるかもしれません。
Err(Err<E>)は、エラーを表す型が3重に重なった構造になってます。

  • 1番外側のErrはRustの標準のResult型のErr
  • 2番目のErrnom::Errで、パーサーエラーが以下の3種類のどれなのかを示すためのもの
    • Incompleteは入力が足りないことを示す[6]
    • Errorは回復可能なエラー
    • Failureは回復不能なエラー
  • 3番目のEはエラーのより具体的な内容を示すために使われます。
    デフォルトではnom::error::Error<I>型が使われますが、これは入力文字列のどこでエラーがあったかと、エラーコードだけを保持するような単純なエラー型です。[7]

1番外側のErrは見慣れたResult型の値なので、2番目と3番目の型について簡単に説明します。

nom::Errについて

nom::Errは、IncompleteErrorFailureの3種類の値を取ります。
このうちIncompleteは、本記事の内容とは関係ないので、ここではErrorFailureについて説明します。

ErrorFailureの違いは一言で言うと回復可能なエラーかどうかということです。
Errorは回復可能なエラーで、Failureは回復不能なエラーを意味します。

両者の違いについて、具体例で考えてみましょう。
例えば先ほどの例で、valueとして整数値しか取れなかったのを、以下のように文字列も取れるように修正したとします。

a=1
b="hoge"

この場合、元々のパーサーを修正して、=の次に整数もしくは文字列を取れるようにします。

このようなパーサーは内部的には、

  1. =まで読み込んだ後で、
  2. まず整数をパースしてみて、
  3. 整数のパースでエラーが出たら文字列をパースしてみる、

というような処理を行うことになります。

この整数のパースの時に発生したエラーが回復可能なエラーの例になります。
整数のパースに失敗しても、まだ文字列の可能性もあるのでそれで終わりではないからです。

一方、回復不能なエラーの例としては、例えば以下のようなものが考えられます。

a=1
b=

この例では、bの後に何も値がなく構文として間違ったものになっています。
これ以上このファイルのパースを続けても仕方ないので、このようなエラーが起きた場合は回復不能なエラーとしてここでパースを終了することになります。

Eについて

続いて、Err(Err<E>)Eについて説明します。
このEは主にパーサーの利用者である人間にエラーの内容がどうだったかを説明する役割を担っていると考えられます。[8]

以下の例は、先ほども出てきたkey=valueの形式の文字列をパースするパーサーです。
この例では「keyはアルファベットのみで構成される」ということが前提になっているのですが、ここで入力のkeyを数字を含む不正な形(a1)に変えた場合にどうなるか見てみましょう。

use nom::bytes::complete::tag;
use nom::character::complete::{alpha1, digit1};
use nom::sequence::separated_pair;
use nom::IResult;

fn parse_keyval(input: &str) -> IResult<&str, (&str, &str)> {
    separated_pair(alpha1, tag("="), digit1)(input)
}

fn main() {
    let input = "a1=1";
    println!("{:?}", parse_keyval(input)); // Err(Error(Error { input: "1=1", code: Tag }))
}

これは当然パースには失敗して、Err(Error(Error { input: "1=1", code: Tag }))という結果が返ってきています。
これまで説明した通り3重構造のエラーになっていて、1番内側のError { input: "1=1", code: Tag }が今説明しているEに対応します。[9]

これはnomのデフォルトのエラー型のnom::error::Errorで、inputはパースに失敗した位置、codeはどのパーサーの実行時にエラーが発生したかを表しています。
上の例であれば、最初にalpha1を使ってa1=1をパースして、次にtag("=")を使って1=1をパースしようと思ったところで数字が来ていてエラーになったという意味で、inputには1=1が、codeにはTagが入っています。

ただ、inputcodeだけ示すというのはエラーメッセージとしては最低限という感じで、もっと詳しいエラーメッセージを表示したいということもあると思います。
その場合どうするか、色々な選択肢がありそうですが、本記事では自分でエラー型を定義する方法を採用したのでそれを紹介します。

以下に示すのは、nomのリポジトリ内にあるexamples/custom_error.rsの内容です。
この例では、CustomErrorというエラー型を定義して、ParseErrorトレイトを実装しています。

https://github.com/rust-bakery/nom/blob/1309141ae58265ccbbc330b46233076feb6ff98b/examples/custom_error.rs

このようにして定義したエラー型を、IResult<&str, &str, CustomError<&str>>のようにIResultの第3引数に指定することで、自分でカスタムしたエラー型を使うことが出来ます。

エラーについての説明は以上です。より詳しく知りたいという方は、公式ドキュメントのError managementをまずは読んでみることをおすすめします。

nomを用いたTOMLパーサーの実装

では、TOMLパーサーの実装について見ていきます。
実装の詳細について見ていく前に、まずは具体的な使用例を見てみましょう。
以下のコードのparse_tomlという関数が今回実装したTOMLパーサーです。

main.rs
use toml_parser::parse_toml;

fn main() {
    let input = r#"
    [package]
    name = "toml_parser"
    version = "0.1.0"
    edition = "2021"

    # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

    [dependencies]
    nom = "7.1.3"
    chrono = "0.4"
    maplit = "1.0"
    "#;

    let result = parse_toml(input);
    println!("{:#?}", result);
}

出力は以下のようになります。ちゃんと入力したTOMLの文字列が表したかった連想配列らしきものになっていることが分かります。

Ok(
    (
        "",
        {
            "dependencies": Table(
                {
                    "nom": String(
                        "7.1.3",
                    ),
                    "chrono": String(
                        "0.4",
                    ),
                    "maplit": String(
                        "1.0",
                    ),
                },
            ),
            "package": Table(
                {
                    "version": String(
                        "0.1.0",
                    ),
                    "name": String(
                        "toml_parser",
                    ),
                    "edition": String(
                        "2021",
                    ),
                },
            ),
        },
    ),
)

parse_tomlのシグネチャは以下の通りです。

pub fn parse_toml(input: &str) -> MyResult<&str, HashMap<String, TomlValue>>

つまり、入力のTOMLファイルの内容を&strとして受け取り、HashMap<String, TomlValue>を返すパーサーになっています。

MyResultIResultの型エイリアスで、自分で定義したエラー型をエラーとして使うようにしたものです。
TomlValueは結果として得られる連想配列のvalueに対応する列挙型です。それぞれ以下のように定義されています。

#[derive(Debug, PartialEq)]
pub enum TomlParserError {
    NomError(String, nom::error::ErrorKind),
    DuplicationError(String),
    InvalidTomlError(String),
}

impl ParseError<&str> for TomlParserError {
    fn from_error_kind(input: &str, kind: ErrorKind) -> Self {
        TomlParserError::NomError(input.to_string(), kind)
    }

    fn append(_: &str, _: ErrorKind, other: Self) -> Self {
        other
    }
}

type MyResult<I, O> = IResult<I, O, TomlParserError>;

pub enum TomlValue {
    String(String),
    Integer(i64),
    Float(f64),
    Boolean(bool),
    OffsetDateTime(DateTime<chrono::offset::FixedOffset>),
    LocalDateTime(NaiveDateTime),
    LocalDate(NaiveDate),
    LocalTime(NaiveTime),
    Array(Vec<TomlValue>),
    InlineTable(HashMap<String, TomlValue>),
    Table(HashMap<String, TomlValue>),
    ArrayTable(Vec<HashMap<String, TomlValue>>),
}

なお、TomlParserErrorは上で説明した方法によって自作したエラー型です。
以下で説明するように、パースしたTOML内でkeyが重複している場合は形式的には正しくてもエラーにしなければいけないのですが、デフォルトのエラー型ではこのようなエラーを表現することが出来ないため、自分でエラー型を定義することにしました。

実装する上で参考にした資料

実装する上で参考にした資料は以下の2つのみです。

基本的にはこの2つの資料にパーサーを作るために必要な情報は全て含まれていると思っているのでこれだけ見ておけば何も問題はないはずです。
ただ、1つ後から気付いたこととしては、日本語版のドキュメントはv1.0.0-rc.2なのに対し、公式リポジトリのABNFはそれよりももっと新しいリビジョン[10]のものだということです。

実際に、v1.0.0-rc.2のドキュメントの内容とABNFの内容で異なる部分が少しあると後から気付いてしまったのですが、その場合はABNFの内容を優先しました。
他にも気付いていない違いが何かあるかもしれませんが、とりあえず実装したTOMLパーサーはそれらしく動いているので良しとしています...。

実装

大分遠回りしましたが、今回作成したTOMLパーサーの実装を紹介します。
なお、実装に使用したRustのバージョンは 1.66.1 でした。

まず以下のようなCargo.tomlを作成します。

Cargo.toml
[package]
name = "toml_parser"
version = "0.1.0"
edition = "2021"

[dependencies]
nom = "7.1.3"
chrono = "0.4"
maplit = "1.0"

本プロジェクトでは、nomに加え、chronomaplitを依存関係に追加しています。それぞれの用途は以下の通りです。

  • chrono: 日時関連の型を表すのに使用
  • maplit: テストケースにおいて、HashMapを簡潔に書くために使用

TOMLパーサーの本体とテストケースはsrc/lib.rsに書いています。

https://github.com/skwbc/toml_parser/blob/3e43727a19491a34a4260fc598f76bc917f0b72c/src/lib.rs

実装については以上です。ちょっと長いので、どのように実装されているのか気になる方は見てみて下さい。
以下では、実装上のポイントなどについて簡単に説明していきます。

実装の方針

基本的には、ABNFの内容を出来るだけそのまま実装するように努めました。
なので、一部を除き全体的に結構分かりやすいコードになっているという気はしています。

例1: valueの実装

以下のコードは key-value の value[11] の部分をパースするパーサーの実装です。

/// val = string / boolean / array / inline-table / date-time / float / integer
fn parse_val(input: &str) -> MyResult<&str, TomlValue> {
    alt((
        parse_string,
        parse_boolean,
        parse_array,
        parse_inline_table,
        parse_date_time,
        parse_float,
        parse_integer,
    ))(input)
}

TOMLでは、valueとして string, boolean, array, inline-table, date-time, float, integer のいずれかが認められています。
したがって、素直な実装としてはこれらに対応するパーサーを各々実装し、それをaltでつなげれば良いです。
ちなみに、altは与えられた複数のパーサーを1つ1つ適用していき最初に成功したものの結果を返すというコンビネーターです。

altの中に入っているパーサーも同じようにABNFを見ながら実装すればOKです。
例えば、最も簡単な boolean のパーサーは以下のように実装しました。

/// boolean = true / false
/// true    = %x74.72.75.65     ; true
/// false   = %x66.61.6C.73.65  ; false
fn parse_boolean(input: &str) -> MyResult<&str, TomlValue> {
    let (input, value) = alt((tag("true"), tag("false")))(input)?;
    Ok((input, TomlValue::Boolean(value == "true")))
}

boolean 以外のパーサーの実装はもう少し難しいので説明は省略しますが、興味があれば見てみて下さい。

例2: commentの実装

もう1つ特徴的な例として、commentの実装について説明したいと思います。

TOMLにおいて#から始まる部分は行末までコメントとして扱われます。
例えば、Rustユーザーなら見慣れている以下のメッセージはコメントです。
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

このコメントですが、形式的には以下のように定義されています。

comment = comment-start-symbol *allowed-comment-char
comment-start-symbol = %x23 ; #
allowed-comment-char = %x01-09 / %x0E-7F / non-ascii
non-ascii = %x80-D7FF / %xE000-10FFFF

#以降、allowed-comment-charに含まれる文字が続く限りコメントとして扱われます。
allowed-comment-charは、Unicode code point により定義されているようで、改行など一部の例外[12]を除く文字全体がコメントに使えるようになっています。

この定義は以下のように実装することが出来ます。

/// comment = comment-start-symbol *allowed-comment-char
/// comment-start-symbol = %x23 ; #
/// allowed-comment-char = %x01-09 / %x0E-7F / non-ascii
/// non-ascii = %x80-D7FF / %xE000-10FFFF
fn parse_comment(input: &str) -> MyResult<&str, &str> {
    recognize(tuple((
        tag("#"),
        take_while(
            |c| matches!(c, '\u{01}'..='\u{09}' | '\u{0E}'..='\u{7F}' | '\u{80}'..='\u{D7FF}' | '\u{E000}'..='\u{10FFFF}'),
        ),
    )))(input)
}

ポイントはtake_whileのところです。Rustではcharの値は Unicode scalar value[13]を表すので、allowed-comment-charの定義をそのまま書き写す感じで簡単に実装が出来ています。

実装上難しかったところ

実装する上で最も苦労したのは、パーサーそのものではなく、パーサーにより得られた値を1つの連想配列にまとめる部分でした。

tomlは、形式的には以下のようにexpressionを改行で区切ったものとして定義されています。

;; Overall Structure

toml = expression *( newline expression )

expression =  ws [ comment ]
expression =/ ws keyval ws [ comment ]
expression =/ ws table ws [ comment ]

上の実装では、expressionを1つ1つパースしていき、得られた結果を順次HashMapに反映していくという処理になっているのですが、この処理を実装するにあたり以下の点で苦労しました。

  • keyが重複していたらエラーにする必要があるが、その判定がなかなか複雑であること
  • mutable borrow が2つ以上同時に作れない中で、連想配列に値を追加していくコードを書くこと

keyの重複判定について

TOMLパーサーでは基本的にkeyが重複していた場合は不正な入力として扱う必要があります。
このkeyの重複判定が結構ややこしく、場合分けをしっかりと考えるのに苦労しました。

どう複雑なのか、具体的に見ていきましょう。
まず最も簡単な重複の例は、以下のようなケースです。

a = 1
a = 2

この場合、aというkeyが重複しているので不正な入力としてエラーを返します。

もう少しTOMLらしい(?)例を出しますと、例えば以下のようにテーブルのkeyが重複している場合もエラーになります。

[a]
b = 1

[a]
c = 2

一方で、かなり似たような見た目ですが、以下のケースはエラーではありません。

[[a]]
b = 1

[[a]]
c = 2

この2重の角括弧で囲まれたテーブルのようなものはarray-table(テーブルの配列)と呼ばれます。
これは以下のように配列の中にテーブルが含まれた構造を表現するために使われるものです。
従って、array-tableのkeyが重複した場合はエラーにするのではなく、配列に新たなテーブルを追加するという処理を行う必要があります。

{
    "a": [
        { "b": 1 },
        { "c": 2 }
    ]
}

また、keyにはsimple-keydotted-keyという区分があり、dotted-keyが出てくるとまた判定が複雑になります。
dotted-keyとは以下のようなものです。

a.b.c = 1

これは以下のような入れ子になった構造を表しています。

{
    "a": {
        "b": {
            "c": 1
        }
    }
}

dotted-keyの場合、以下のように完全に同じkeyが出てきた場合はエラーになりますが、

a.b.c = 1
a.b.c = 2

以下のようなケースはエラーではありません。

a.b.c = 1
a.b.d = 2

ちなみに、上のケースをJSONで表すと下のような感じになります。

{
    "a": {
        "b": {
            "c": 1,
            "d": 2
        }
    }
}

この他にも、例えば以下のようなことについて考える必要があり、まとめるのに苦労しました。

  • テーブルやテーブルの配列の中にdotted-keyが出てきた場合の処理
  • インラインテーブルや普通の配列の場合は、普通のテーブルやテーブルの配列とは重複判定の仕方が異なる

ただ、ちょっと細かすぎる話になるので、詳細について気になる方は実装を見てみてください。

連想配列に値を追加していく処理

これはRust初心者あるあるなのかもしれませんが、パースの結果として最終的に作成されるHashMapに値を追加していくのを、mutable borrowを持ちまわしていく感じで実装したのでコンパイルを通すのが大変でした。

典型的な例は、以下のadd_keyval_to_tomlという関数の実装です。

fn add_keyval_to_toml(
    toml: &mut HashMap<String, TomlValue>,
    key: TomlKey,
    value: TomlValue,
) -> Result<&mut HashMap<String, TomlValue>, nom::Err<TomlParserError>> {
    let allow_array_table = matches!(value, TomlValue::Table(_) | TomlValue::ArrayTable(_));
    match key {
        TomlKey::SimpleKey(key) => add_simple_keyval_to_toml(toml, key, value),
        TomlKey::DottedKey(keys) => {
            let mut current = toml;
            let mut subkey = Vec::new();
            for k in keys[..keys.len() - 1].iter() {
                subkey.push(k.clone());
                current
                    .entry(k.clone())
                    .or_insert_with(|| TomlValue::Table(HashMap::new()));
                current = match current.get_mut(k) {
                    Some(TomlValue::Table(t)) => t,
                    Some(TomlValue::ArrayTable(v)) if allow_array_table => v.last_mut().unwrap(),
                    _ => {
                        return Err(nom::Err::Failure(TomlParserError::DuplicationError(
                            format!("key {} is already defined", subkey.join(".")),
                        )));
                    }
                };
            }
            match add_simple_keyval_to_toml(current, keys.last().unwrap().clone(), value) {
                Ok(t) => Ok(t),
                Err(_) => Err(nom::Err::Failure(TomlParserError::DuplicationError(
                    format!("key {} is already defined", keys.join(".")),
                ))),
            }
        }
    }
}

これは、toml: &mut HashMap<String, TomlValue>に対して、key: TomlKeyvalue: TomlValueのペアを追加するという処理です。
TomlKeyはその名の通りTOMLのkeyを表す列挙型で、SimpleKeyもしくはDottedKeyのいずれかの値をとります。
これがSimpleKeyだった場合は割と単純にHashMapkeyvalueを追加すれば良い[14]のですが、DottedKeyだった場合は入れ子になったHashMapを作っていく必要があります。

この例では、currentという名前の変数に入れ子になった内側のHashMapを入れながら掘り進んで行く感じの実装になっています。
そうすると必然的にmutable borrowを作りまくる感じの実装になってしまうのですが、一歩足を踏み外すとコンパイルエラーが出てしまうのでかなり苦労しました。[15]

妥協したところ

実装する上で妥協したところというのもあって、個人的に最も気になっているのは回復不能なエラーをちゃんと使えていないという点です。
例えば以下のようなTOMLをパースする場合、aというテーブルの閉じ括弧がないのでその時点で回復不能なエラーを発生させるのが適切だと思います。

[ a 
b = 1
c = 2

現状の実装でも回復不能なエラーを返すことは出来ているのですが、ちょっとどうなのと思う方法[16]で実現しているので、もっとnomらしい方法で実現できればと思っています。

ちなみに、「nomらしい方法」と言っているのは、以下のcutというコンビネータを使う方法です。

https://docs.rs/nom/latest/nom/combinator/fn.cut.html

これは、cutで包んだパーサーがエラーを返した場合、そのエラーを回復不能なエラーに変換するコンビネーターです。
上で紹介したJSONパーサーの実装例などでもこのcutが適切に使用されています。

妥協した理由としては、「疲れてしまって直す元気がない」というのが正直なところですが、自分がこのパーサーのユーザーだったとして、現状のエラーメッセージでも十分満足できるなとも思ったので妥協することにしました。[17]

感想

最初TOMLのABNFを見つけたとき、正直な話をすると「結構簡単そうだな」と思ったのですが、実際に実装してみるとなかなか大変でした。
ただ、おかげでnomについて基本的な使い方は大体理解できましたし、TOMLについては分からないところはほぼ無いというくらい理解できたのではないかと思っています。

Rustについてはまだ基本的な部分ですら理解が怪しいところが色々とあり、rust-analyzerに言われるがまま何とか実装しているという感じなので、自信を持って使うためにはまだまだ勉強が必要だなと感じました。

脚注
  1. 公式ドキュメント(英語版)には連想配列ではなくhash tableと書かれているのですが、ハッシュテーブルに限定する意味はないと思うので、日本語版ドキュメントと同様に連想配列と言い換えています。(日本語版には連想配列と書かれている。) ↩︎

  2. この呼び分けが適切なのかどうかよく分かりません。あくまでもこの記事内ではそうするというだけの話です。 ↩︎

  3. nom的には、入力は必ずしも文字列でなくても良いのですが、説明を単純化するために本記事では文字列を構文解析するパーサーのみを考えます。 ↩︎

  4. なお、話を簡単にするために、この例ではkeyはアルファベットのみ、valueは数字のみであると仮定しています。 ↩︎

  5. 「初心者(自分)が実際に困った点」と言ったほうが正確ですが。 ↩︎

  6. 入力がストリームの場合や、データがすごく大きいので部分的に読み込んでパースしていく場合などに使われるもの。今回のTOMLパーサーの実装はどちらにも当てはまらないので関係なし。 ↩︎

  7. もうちょっとリッチなエラー情報が欲しい場合は別のエラー型を使う必要があります。 ↩︎

  8. 別にこのエラーの内容に応じて処理が分岐するプログラムとかを書いても良いわけですが、想定外の使い方という感じはしています。 ↩︎

  9. 紛らわしいのですが、2番目のErrornom::Err::Errorで、上で説明した回復可能なエラーであることを示しています。 ↩︎

  10. 2023年5月時点での最新版 ↩︎

  11. 上のCargo.tomlで言うと、"toml_parser"とか"0.1.0"とかの部分がvalueに相当します。 ↩︎

  12. U+0A: LINE FEED, U+0B: LINE TABULATION, U+0C: FORM FEED, U+0D: CARRIAGE RETURN, U+D800-U+DFFF: Surrogate Code Point ↩︎

  13. Unicode code point から surrogate code point を除いたもの。詳細が気になる方はcharのドキュメントを読んでみて下さい。https://doc.rust-lang.org/std/primitive.char.html ↩︎

  14. 実際はこれも言うほど単純ではなく、結構色々と場合分けする必要があります。 ↩︎

  15. これは純粋に自分のRust理解度が低いことから生じたトラブルなので「もっと勉強しろ」という話でしかないのですが、Rust以外の言語なら簡単だったなという感想は持ちました。正直な話。 ↩︎

  16. parse_tomlの返り値Ok((I, O))Iが空白文字列になっていない場合は形式的に不正であると断定できるので、その時点で回復不能なエラーを返すようにしている。 ↩︎

  17. 今回はあくまでも勉強目的なので、次回以降ちゃんと出来れば良いかなと気楽に考えています。 ↩︎

Discussion