Markdown パーサを書きたい！～パーサを作る編～

# Markdown パーサを書きたい！～パーサを作る編～

この記事は[某企業 2024 年度新卒 Advent Calender 2024](https://adventar.org/calendars/10291) 10 日目の記事です。

[前回の記事](https://qiita.com/keiwa-tech/items/7dfa9b9a7e9f362eaf45)ではパーサコンビネータを作りました。
今回はこれらを使って実際に Markdown パーサを作ってみます。

## 今回のゴール

パーサは文字列から何らかの構造に変換するものでした。
Markdown パーサにおいて、この何らかの構造は**抽象構文木**になります。
抽象構文木は[wiki](https://ja.wikipedia.org/wiki/%E6%8A%BD%E8%B1%A1%E6%A7%8B%E6%96%87%E6%9C%A8)によると

> 抽象構文木（ちゅうしょうこうぶんぎ、英: abstract syntax tree、AST）は、通常の構文木（具象構文木あるいは解析木とも言う）から、言語の意味に関係ない情報を取り除き、意味に関係ある情報のみを取り出した（抽象した）木構造の木である。

と説明されています。
ちょっと意味がわからないので以降の説明を見ると

> 抽象構文木は具象構文木とは異なり、プログラムの意味に関係ない部分を省略する。そのような省略の例としては括弧の省略があげられる。抽象構文木では、その自然な木構造によって結合は自明であるから、グループ化のための括弧などは意味的に不要である。変数名などの名前なども、識別できればよいので何らかの ID のようなもので構わない。

とあります。
つまり、Markdown において抽象構文木は文章構造から本質的に意味のある部分を抽出して、木構造にしたものということですかね。
イメージにするとこんな感じでしょうか。

![パースのイメージ](./images/ADT.drawio.png)

抽象構文木はある種の中間表現で、この木を使ってレンダリングすることで HTML にしたり、あるいは JSON にしたりといった事ができるようになっています。

今回の記事はこの抽象構文木を Markdown テキストから作るのがゴールです。
作る時間の関係で対応していない構文やバグがありますが許してください。
~~決して面倒だからではありません~~

## 抽象構文木の定義

ではまず、抽象構文木を定義していきます。
抽象構文木はその名と通り木構造です。
なのでこのような形で定義してみます。

```rust
#[derive(Debug, PartialEq, Clone)]
struct Token {
    element: MDElement,
    children: Vec<Token>,
}
```

`Token`は木構造の各ノードを表しています。
`element`はヘッダーや強調などの要素を表すもので、`children`は`element`にぶら下がるノードのリストという感じで、再帰的な定義になっています。
では次に、`MDElement`を定義します。

```rust
#[derive(Debug, PartialEq, Clone)]
enum MDElement {
    Root,
    LineBreak,
    HorizontalRule,
    Header1(String),
    Header2(String),
    Header3(String),
    Header4(String),
    Header5(String),
    Header6(String),
    Paragraph(String),
    Span(String),
    Blockquote(String),
    CodeBlock(String),
    Emphasis(String),
    Strong(String),
    Strikethrough(String),
    OrderedListItem(usize, String),
    UnorderedListItem(usize, String),
    Link(String, String),
    Image(String, String),
}
```

`Header1`や`Link`などの定義されている要素は、レンダリングするときに必要な中身（テキストやリンクさきなど）を保有しています。
この`MDElement`に値を詰めて、`Token`で木を作るといった感じでやっていきます。

## 必要な関数の定義

パーサを作る前に必要な関数を作ります。

### 文字関係

Markdown で使用する文字について定義します。
この文字の定義は[Rust でパーサコンビネータを作ってみる (後編)](https://zenn.dev/nojima/articles/e597d22660205d)を参考にさせていただいております。

```rust
fn characters_trim() -> impl Parser<String> {
    trim_ws(characters())
}

fn characters() -> impl Parser<String> {
    many1(all_character).map(|chars| chars.into_iter().collect())
}

fn all_character(s: &str) -> Option<(char, &str)> {
    regex!(r#"^[^\\[:cntrl:]]"#, |s| s.chars().next())
        .or(unicode)
        .or(escaped_character)(s)
}

fn unicode(s: &str) -> Option<(char, &str)> {
    regex!(r#"^\\u[0-9a-fA-F]{4}"#, hex_code)(s)
}

fn escaped_character(s: &str) -> Option<(char, &str)> {
    regex!(r#"^\\."#, _escape)(s)
}

fn hex_code(code: &str) -> Option<char> {
    code.strip_prefix("\\u")
        .and_then(|code| u32::from_str_radix(code, 16).ok())
        .and_then(std::char::from_u32)
}

fn _escape(s: &str) -> Option<char> {
    match s {
        "\\\\" => Some('\\'),
        "\\#" => Some('#'),
        "\\*" => Some('*'),
        "\\_" => Some('_'),
        "\\/" => Some('/'),
        "\\[" => Some('['),
        "\\]" => Some(']'),
        "\\(" => Some('('),
        "\\)" => Some(')'),
        "\\`" => Some('`'),
        "\\!" => Some('!'),
        "\\|" => Some('|'),
        "\\-" => Some('-'),
        "\\." => Some('.'),
        "\\>" => Some('>'),
        "\\b" => Some('\x08'),
        "\\f" => Some('\x0C'),
        "\\n" => Some('\n'),
        "\\r" => Some('\r'),
        "\\t" => Some('\t'),
        _ => None,
    }
}
```

文字は基本的に全て使えて、Markdown に使われるマーカーはエスケープするとそのまま使えるという感じです。
基本的に文字列がほしいときは、前の空白を取り除いたあとの文字列をとれる`characters_trim`を使います。

### surrounded

Markdown のパーサでは何かしらのマーカーに囲まれた文字を取得するということが割とあります。
パーサを`and`でつなげるのもいいのですが、出力に括弧がいっぱい出てきたりして非常に見づらいです。
なので、`surrounded`という関数を定義します。

```rust
fn surrounded<A, T, B>(
    open: impl Parser<A>,
    parser: impl Parser<T>,
    close: impl Parser<B>,
) -> impl Parser<T> {
    open.and(parser).and(close).map(|((_, t), _)| t)
}

#[test]
fn test_surrounded() {
    let parser = surrounded(character('('), trim_ws(digits()), character(')'));

    assert_eq!(parser("(123)"), Some((123, "")));
    assert_eq!(parser("(123abc"), None);
    assert_eq!(parser("123)"), None);
    assert_eq!(parser("123"), None);
}
```

`open`と`close`に挟まれたパーサ(`parser`)の出力だけを取り出すといった関数です。
テストを見ると()に囲まれた数値を取り出すことができていることがわかります（`digits`は数値をパースするパーサ）。

### take_until

`surrounded`を使うとき、閉じるマーカー（`close`）でマッチする文字列以外の文字まで読むパーサを`parser`にしたいときがあります。
なので、その関数`take_until`を作ります。

```rust
fn take_until<'a, T>(s: &'a str, f: impl Fn(&str) -> Option<T> + 'a) -> impl Parser<T> + 'a {
    move |input: &str| {
        input
            .find(s)
            .and_then(|i| f(&input[..i]).map(|t| (t, &input[i..])))
    }
}

#[test]
fn test_take_until() {
    let parser = take_until("abc", |s| Some(s.to_string()));

    assert_eq!(parser("123abc"), Some(("123".to_string(), "abc")));
    assert_eq!(parser("abc"), Some(("".to_string(), "abc")));
    assert_eq!(parser(""), None);
}
```

`take_until`はマーカーとなる文字列とそれが見つかったときに適用する関数を取ります。
こうなっているのは前回の記事の`regex`関数と似たような感じで、文字列を`&str`で持ち回りたくないという理由です。
動作はテストで見れるとおりですが、あるマーカーまでの文字列を取得する感じになっています。

### lb!

テキスト 1 行に含まれる改行を読み飛ばしたい場合が多いです。
しかし、テキストの最後など改行がつかない場合もあり、単にパーサの最後に`string("\n")`をつけると改行がない場合マッチしません。
なので、正規表現の?のようなものを作ります。

```rust
macro_rules! lb {
    ($parser:expr) => {
        $parser.and(string("\n")).map(|(t, _)| t).or($parser)
    };
}

#[test]
fn test_lb() {
    let parser = lb!(string("hello, world!"));
    assert_eq!(parser("hello, world!\n"), Some(((), "")));
    assert_eq!(parser("hello, world!"), Some(((), "")));
}
```

`Parser<T>`のクローンが作れないので、lb はマクロで定義しています。
`and`や`or`の戻り値に`Clone`をつけた構造体を返すようにするとできるっぽい（？）のですが、まだそこら辺が勉強不足なので、一旦こんな感じにしています。
テストを見ると改行がつく、つかない場合どちらにもマッチしていることがわかります。

## Markdown パーサのパーツを作る

長かったですが、ようやく Markdown パーサを作っていきます。
パーサコンビネータは小さなパーサを作って、大きなパーサを作るものでしたね。
なので、Markdown の要素ごとにパーサを作っていきます。

### Header

最初に Header 要素のパーサを作ってみます。
なお、ここからは記事が長くなってしまうので、テスト部分は省略します。

```rust
fn header(s: &str) -> Option<(MDElement, &str)> {
    let header1 =
        lb!(string("# ").and(characters_trim())).map(|(_, text)| MDElement::Header1(text));
    let header2 =
        lb!(string("## ").and(characters_trim())).map(|(_, text)| MDElement::Header2(text));
    let header3 =
        lb!(string("### ").and(characters_trim())).map(|(_, text)| MDElement::Header3(text));
    let header4 =
        lb!(string("#### ").and(characters_trim())).map(|(_, text)| MDElement::Header4(text));
    let header5 =
        lb!(string("##### ").and(characters_trim())).map(|(_, text)| MDElement::Header5(text));
    let header6 =
        lb!(string("###### ").and(characters_trim())).map(|(_, text)| MDElement::Header6(text));

    header1
        .or(header2)
        .or(header3)
        .or(header4)
        .or(header5)
        .or(header6)(s)
}
```

パーサコンビネータは宣言的なので非常に見やすいと思います。
`# `があって、文字列あるものがヘッダーですよといった感じです。
こういった感じでどんどん作っていきましょう。

### Paragraph

```rust
fn paragraph(s: &str) -> Option<(MDElement, &str)> {
    character('\n')
        .and(many1(characters_trim().and(character('\n'))))
        .and(character('\n'))(s)
    .map(|(((_, text), _), rest)| {
        (
            MDElement::Paragraph(
                text.into_iter()
                    .map(|(text, _)| text)
                    .collect::<Vec<String>>()
                    .join("\n"),
            ),
            rest,
        )
    })
}
```

空白行に囲まれた部分が段落という定義です。
Markdown の仕様を調べずに作っているので怪しいですが、俺俺パーサということで許してももらいましょう。

### Blockquote

```rust
fn blockquote(s: &str) -> Option<(MDElement, &str)> {
    lb!(string(">").and(characters_trim()))(s)
        .map(|((_, text), rest)| (MDElement::Blockquote(text), rest))
}
```

引用です。引用は`>>`のような感じでネストできるらしいので、`> `のように空白を入れないようにしています。

### Emphasis, Strong, Strikethrough

```rust
fn emphasis(s: &str) -> Option<(MDElement, &str)> {
    let asterisk = lb!(surrounded(
        string("*"),
        take_until("*", |s| Some(s.to_owned())),
        string("*")
    ));
    let underscore = lb!(surrounded(
        string("_"),
        take_until("_", |s| Some(s.to_owned())),
        string("_")
    ));

    asterisk.or(underscore)(s).map(|(text, rest)| (MDElement::Emphasis(text), rest))
}

fn strong(s: &str) -> Option<(MDElement, &str)> {
    let asterisk = lb!(surrounded(
        string("**"),
        take_until("**", |s| Some(s.to_owned())),
        string("**")
    ));
    let underscore = lb!(surrounded(
        string("__"),
        take_until("__", |s| Some(s.to_owned())),
        string("__"),
    ));

    asterisk.or(underscore)(s).map(|(text, rest)| (MDElement::Strong(text), rest))
}

fn strikethrough(s: &str) -> Option<(MDElement, &str)> {
    lb!(surrounded(
        string("~~"),
        take_until("~~", |s| Some(s.to_owned())),
        string("~~")
    ))(s)
    .map(|(text, rest)| (MDElement::Strikethrough(text), rest))
}
```

強調と取り消し線です。構造はどれもマーカに囲まれた文字を取り出す感じなので一緒に紹介しています。
あまり特筆することもないですね。

### CodeBlock

````rust
fn code_block(s: &str) -> Option<(MDElement, &str)> {
    surrounded(
        lb!(string("```")),
        lb!(take_until("```", |s| Some(s.to_owned()))),
        lb!(string("```")),
    )(s)
    .map(|(text, rest)| (MDElement::CodeBlock(text), rest))
}
````

コードブロックです。\`\`\`に囲まれた文字を取り出します。
\`\`\`のあとに改行があってもいいように`lb!`をつけています。
\`\`\`rust のような言語を指定するのは一旦なしにしています。

### Image, Link

```rust
fn link(s: &str) -> Option<(MDElement, &str)> {
    let text = surrounded(
        string("["),
        take_until("]", |s| Some(s.to_owned())),
        string("]"),
    );
    let url = lb!(surrounded(
        string("("),
        take_until(")", |s| Some(s.to_owned())),
        string(")")
    ));

    text(s).and_then(|(t, r)| url(r).map(|(u, rest)| (MDElement::Link(t, u), rest)))
}

fn image(s: &str) -> Option<(MDElement, &str)> {
    let text = surrounded(
        string("!["),
        take_until("]", |s| Some(s.to_owned())),
        string("]"),
    );
    let url = lb!(surrounded(
        string("("),
        take_until(")", |s| Some(s.to_owned())),
        string(")")
    ));

    text(s).and_then(|(t, r)| url(r).map(|(u, rest)| (MDElement::Image(t, u), rest)))
}
```

リンクと画像です。
この 2 つは 2 箇所囲まれたところがあり、それらのパーサを`and_then`でつないでる感じです。

### OrderedList, UnorderedList

```rust
fn indent() -> impl Parser<usize> {
    |input: &str| {
        let (indent, rest) = many(character(' '))(input)?;
        let indent = indent.len();
        Some((indent / INDENT_SIZE, rest))
    }
}

fn ordered_list_item(s: &str) -> Option<(MDElement, &str)> {
    lb!(indent()
        .and(digits())
        .and(string(". "))
        .and(characters_trim()))
    .map(|(((level, _), _), text)| MDElement::OrderedListItem(level, text))(s)
}

fn unordered_list_item(s: &str) -> Option<(MDElement, &str)> {
    lb!(indent().and(string("- ")).and(characters_trim()))
        .map(|((level, _), text)| MDElement::UnorderedListItem(level, text))(s)
}
```

箇条書きの 2 つです。
箇条書きは順序付きとそうでないのが 2 つあります。
また、インデントによって箇条書きのレベルが変わります。
インデントは`INDENT_SIZE`に設定した空白の数で判定しています。
そして、判定したインデントのレベルを`MDElement`に詰めています。

### HorizontalRule

```rust
fn horizontal_rule(s: &str) -> Option<(MDElement, &str)> {
    lb!(string("---").or(string("***")))(s).map(|(_, rest)| (MDElement::HorizontalRule, rest))
}
```

水平線です。特筆すべきことはありません。

### Span

ここまでの要素は比較的かんたんに作れるのですが、`text*emphasis*text2`のように途中に要素が存在する場合に最初の`text`を抽出するパーサは少し考える必要があります。
正規表現ならば先読みを使って抽出できますが、今使っている regex クレートが先読みに対応してませんでした。
なので自力で作ります。

```rust
fn span(s: &str) -> Option<(MDElement, &str)> {
    ((take_until("**", |s| Some(s.to_owned()))(s)
        .and_then(|(text, rest)| strong(rest).map(|(_, _)| (MDElement::Span(text), rest))))
    .or(take_until("__", |s| Some(s.to_owned()))(s)
        .and_then(|(text, rest)| strong(rest).map(|(_, _)| (MDElement::Span(text), rest))))
    .or(take_until("*", |s| Some(s.to_owned()))(s)
        .and_then(|(text, rest)| emphasis(rest).map(|(_, _)| (MDElement::Span(text), rest))))
    .or(take_until("_", |s| Some(s.to_owned()))(s)
        .and_then(|(text, rest)| emphasis(rest).map(|(_, _)| (MDElement::Span(text), rest))))
    .or(take_until("~~", |s| Some(s.to_owned()))(s)
        .and_then(|(text, rest)| strikethrough(rest).map(|(_, _)| (MDElement::Span(text), rest))))
    .or(take_until("[", |s| Some(s.to_owned()))(s)
        .and_then(|(text, rest)| link(rest).map(|(_, _)| (MDElement::Span(text), rest))))
    .or(take_until("![", |s| Some(s.to_owned()))(s)
        .and_then(|(text, rest)| image(rest).map(|(_, _)| (MDElement::Span(text), rest)))))
    .or(lb!(characters_trim())(s).map(|(text, rest)| (MDElement::Span(text), rest)))
}
```

ちょっと美しくはないですがこんな感じになりました。
やっていることは、`**`のようなマーカまで`take_until`で読んで、それに対応するパーサ`strong`がマッチしたら`take_until`の出力を返すといった流れです。
これを要素分やっています。
テキストに要素がない場合は最後の行でテキストすべて Span 要素に詰めています。
この実装だとエスケープした文字に対応していませんが...まぁ...いいでしょう。
俺俺パーサなのでね。

これで今回対応する要素のパーサは作りました。
あとはこれでパースする関数を作るだけです。

## Markdown パーサを使ってパースする

パースするということでパースする関数を作ります。
パースは`# **Header**`のような入れ子構造のものもパースできるようにするため、再帰関数になるようにします。
再帰的にパースしていくために中身のテキストを取得する必要があります。
なので以下のような関数を作っておきます。

```rust
pub fn get_inner_text(md_type: &MDElement) -> Option<&str> {
    match md_type {
        MDElement::Header1(text) => Some(text.as_str()),
        MDElement::Header2(text) => Some(text.as_str()),
        MDElement::Header3(text) => Some(text.as_str()),
        MDElement::Header4(text) => Some(text.as_str()),
        MDElement::Header5(text) => Some(text.as_str()),
        MDElement::Header6(text) => Some(text.as_str()),
        MDElement::Paragraph(text) => Some(text.as_str()),
        MDElement::Span(text) => Some(text.as_str()),
        MDElement::Blockquote(text) => Some(text.as_str()),
        MDElement::CodeBlock(text) => Some(text.as_str()),
        MDElement::Emphasis(text) => Some(text.as_str()),
        MDElement::Strong(text) => Some(text.as_str()),
        MDElement::Strikethrough(text) => Some(text.as_str()),
        MDElement::OrderedListItem(_, text) => Some(text.as_str()),
        MDElement::UnorderedListItem(_, text) => Some(text.as_str()),
        _ => None,
    }
}
```

また、再帰関数ということで停止条件が必要になり、1 つ目は残りのテキストがない場合、2 つ目はテキストがプレーンテキストである場合です。
後者のプレーンテキストである場合というのがまだ判定できないので、定義します。

```rust
fn contain_element(s: &str) -> bool {
    vec![
        regex!(r#"\*.*\*"#, |_| Some(()))(s).is_some(),
        regex!(r#"_.*_"#, |_| Some(()))(s).is_some(),
        regex!(r#"\*\*.*\*\*"#, |_| Some(()))(s).is_some(),
        regex!(r#"__.*__"#, |_| Some(()))(s).is_some(),
        regex!(r#"~~.*~~"#, |_| Some(()))(s).is_some(),
        regex!(r#"\[.*\]\(.*\)"#, |_| Some(()))(s).is_some(),
        regex!(r#"!\[.*\]\(.*\)"#, |_| Some(()))(s).is_some(),
        regex!(r#"^>"#, |_| Some(()))(s).is_some(),
    ]
    .into_iter()
    .any(|b| b)
}
```

Span 要素と同じような感じですが、含まれるかどうかの判定だけなので正規表現でやっています。
そしてこれらを使いパースする関数を作ります。

```rust
pub fn parse(s: &str) -> Token {
    Token {
        children: tokenize(s),
        element: MDElement::Root,
    }
}

fn tokenize(mut s: &str) -> Vec<Token> {
    let parser = header
        .or(horizontal_rule)
        .or(blockquote)
        .or(strong)
        .or(emphasis)
        .or(strikethrough)
        .or(image)
        .or(link)
        .or(code_block)
        .or(ordered_list_item)
        .or(unordered_list_item)
        .or(paragraph)
        .or(span)
        .or(line_break);

    let mut tokens = vec![];

    while let Some((md_type, rest)) = parser(s) {
        let inner_text = get_inner_text(&md_type);
        let token = Token {
            children: inner_text
                .map(|text| {
                    if contain_element(text) {
                        tokenize(text)
                    } else {
                        vec![]
                    }
                })
                .unwrap_or(vec![]),
            element: md_type,
        };
        tokens.push(token);

        s = rest;
    }

    tokens
}
```

`tokenize`関数が再帰的にパースする関数です。
while 文ではパーサが成功する限り、つまり文字列が空になるまで回します。
ループ内ではまず、マッチした要素のテキストを`get_inner_text`で取得し、そのテキストが存在する、かつテキスト中に要素が存在するとき、再帰的に`tokenize`関数を呼び出します。
`tokenize`はパースしたトークンのリストを返すのでそれが親の子どもとなります。
そして`parse`で Root 要素の子どもに`tokenize`の結果を詰めて返します。

以上でパースする関数ができました。
最後に`parse`関数を使ってテストしてみます。

```rust
#[test]
fn test_tokenize() {
    assert_eq!(
        parse("# *hello, world!*\n\ntext*emphasis*text2\n\n"),
        Token {
            element: MDElement::Root,
            children: vec![
                Token {
                    element: MDElement::Header1("*hello, world!*".to_string()),
                    children: vec![Token {
                        element: MDElement::Emphasis("hello, world!".to_string()),
                        children: vec![],
                    }],
                },
                Token {
                    element: MDElement::Paragraph("text*emphasis*text2".to_string()),
                    children: vec![
                        Token {
                            element: MDElement::Span("text".to_string()),
                            children: vec![],
                        },
                        Token {
                            element: MDElement::Emphasis("emphasis".to_string()),
                            children: vec![],
                        },
                        Token {
                            element: MDElement::Span("text2".to_string()),
                            children: vec![],
                        },
                    ],
                },
            ],
        }
    );
}
```

このテストは通ります。

## おわりに

今回の記事はパーサコンビネータを使って実際に Markdown パーサを作ってみました。
複雑に見えるパーサもパーサコンビネータを使うと可読性が高く、直感的にかけました。
また、小さいパーサを組み合わせていくということで、テストがしやすくテスト駆動開発とも相性が良いと感じました。

Markdown パーサを作ったのでこの記事の目標は達成ですが、レンダリングしないと抽象構文木も意味がないので、次回レンダリング編を書こうと思います。
それでは。

## 参考文献

- [抽象構文木](https://ja.wikipedia.org/wiki/%E6%8A%BD%E8%B1%A1%E6%A7%8B%E6%96%87%E6%9C%A8)
- [Rust でパーサコンビネータを作ってみる (後編)](https://zenn.dev/nojima/articles/e597d22660205d)


## 2024/12/15 追記

レンダラを書こうとしたら、パーサのリストの部分が貧弱だったので書けませんでした()。
なので、その部分を強化します。

現状はリストの要素をただ`MDElement`に落とし込んだだけで、きちんとレンダリングするには入れ子構造に沿って構築しなければなりません。
入れ子構造にするためには、リストの要素の前後関係を調べる必要があり、今の仕組みではできません。
そこで方針をこのように設定します。

- HTMLの要素`<ol>`, `<ul>`を`MDElement::OrderedList`, `MDElement::UnorderedList`として表現する
- つながっているリストを`MDElement::ListItems(Vec<MDElement>)`として取り出す
- `ListItems(Vec<MDElement>)`をなんとかして`OrderedList`, `UnorderedList`, `OrderedListItem`, `UnorderedListItem`の入れ子構造として表現する

1つ目と2つ目については以下のように`MDElement`に要素を追加します。

```rust
#[derive(Debug, PartialEq, Clone)]
pub enum MDElement {
    // その他要素は省略
    OrderedList,
    OrderedListItem(usize, String),
    UnorderedList,
    UnorderedListItem(usize, String),
    ListItems(Vec<MDElement>),
}
```

2つ目の`ListItems`を作る部分については、すでに作ってある`ordered_list_item`と`unordered_list_item`を使って以下のパーサを作ります。

```rust
fn list_items(s: &str) -> Option<(MDElement, &str)> {
    many1(ordered_list_item.or(unordered_list_item))(s)
        .map(|(items, rest)| (MDElement::ListItems(items), rest))
}
```

ここまではいいですね。楽勝です。
さて、3つ目ですが...これが厄介な感じです。
かなりアルゴリズム的なやつです。
私はアルゴリズムを組むのが苦手なので一旦方針を書いてみます。

まず、表記としてインデントレベル$I$の`OrderedListItem`を$I^o$、`UnorderedListItem`を$I^u$とします。
このとき、以下のリストを考えます。


$$
[1^o, 1^o, 2^u, 2^u, 3^u, 1^u, 1^u] 
$$

これを以下のような構造にしたいです。

$$
[1^o, 1^o, [2^u, 2^u, [3^u]]], [1^u, 1^u]
$$

これはインデントレベルによって木構造を作るといった感じです。
ただ、一点違うのは同じインデントレベルの異なるタイプは木構造が別となる点です。
それが $[1^o, 1^o, [2^u, 2^u, [3^u]]]$ と $[1^u, 1^u]$ に別れている理由です。
この処理をする関数を考えるのですが、もう少し詳細に方針を書きます。

$$
\begin{align*}
[1^o, 1^o, 2^u, 2^u, 3^u, 1^u, 1^u] \\
\rightarrow [1^o, 1^o, 2^u, 2^u, 3^u], [1^u, 1^u]\\
\rightarrow [1^o, 1^o, [2^u, 2^u, 3^u]], [1^u, 1^u] \\
\rightarrow [1^o, 1^o, [2^u, 2^u, [3^u]]], [1^u, 1^u] \\
\end{align*}
$$

各ステップは、インデントレベルを1ずつ上げてインデントレベルに対応した要素を処理しています。
この方針に従って書いたものがこちらです。

```rust
fn tokenize_list_items(items: &Vec<MDElement>) -> Vec<Token> {
    let content = items
        .iter()
        .map(|item| {
            if let MDElement::OrderedListItem(_, _) | MDElement::UnorderedListItem(_, _) = item {
                Token {
                    children: tokenize_children(&item),
                    element: item.clone(),
                }
            } else {
                panic!("Invalid list item");
            }
        })
        .collect::<Vec<Token>>();

    _tokenize_list_items(0, content)
}

fn _tokenize_list_items(level: usize, items: Vec<Token>) -> Vec<Token> {
    if items
        .iter()
        .filter(|&item| match item.element {
            MDElement::OrderedListItem(l, _) => l >= level,
            MDElement::UnorderedListItem(l, _) => l >= level,
            _ => false,
        })
        .count()
        == 0
        || level > 5
    {
        return items;
    }

    let mut item_type = items
        .first()
        .map(|item| match item.element {
            MDElement::OrderedListItem(_, _) => "ordered",
            MDElement::UnorderedListItem(_, _) => "unordered",
            _ => panic!("Invalid list item"),
        })
        .unwrap_or("ordered");
    let mut tokens = vec![];
    let mut buffer = vec![];

    for item in items {
        let (l, t) = match item.element {
            MDElement::OrderedListItem(l, _) => (l, "ordered"),
            MDElement::UnorderedListItem(l, _) => (l, "unordered"),
            _ => panic!("Invalid list item"),
        };

        if l == level && item_type != t {
            if !buffer.is_empty() {
                tokens.push(Token {
                    element: if item_type == "ordered" {
                        MDElement::OrderedList
                    } else {
                        MDElement::UnorderedList
                    },
                    children: _tokenize_list_items(level + 1, buffer.clone()),
                });
            }
            buffer = vec![item];
            item_type = t;
        } else if l >= level {
            buffer.push(item);
        } else {
            tokens.push(item);
        }
    }

    if !buffer.is_empty() {
        tokens.push(Token {
            element: if item_type == "ordered" {
                MDElement::OrderedList
            } else {
                MDElement::UnorderedList
            },
            children: _tokenize_list_items(level + 1, buffer),
        });
    }

    tokens
}
```

色々汚いですね。これくらいしか私の脳からは出力できませんでした。
少し説明すると、`tokenize_list_items`が`MDElement::ListItems`の中身`items`を`Vec<Token>`に変換し、再帰処理を行う`_tokenize_list_items`に渡しています。
`_tokenize_list_items`は上で説明した方針に従って再帰処理を行うといった感じです。
詳しい説明は~~面倒なので~~省略します。

この関数をパースする大本の関数`tokenize`に組み込むと

```rust
fn tokenize(mut s: &str) -> Vec<Token> {
    let parser = header
        .or(horizontal_rule)
        .or(blockquote)
        .or(strong)
        .or(emphasis)
        .or(strikethrough)
        .or(image)
        .or(link)
        .or(code_block)
        .or(list_items)
        .or(paragraph)
        .or(span)
        .or(line_break);

    let mut tokens = vec![];

    while let Some((md_elm, rest)) = parser(s) {
        if let MDElement::ListItems(items) = &md_elm {
            tokens = [tokens, tokenize_list_items(items)].concat();
        } else {
            let token = Token {
                children: tokenize_children(&md_elm),
                element: md_elm,
            };
            tokens.push(token);
        };

        s = rest;
    }

    tokens
}
```

となります。`ListItems`だけ特別処理する形となっています。
そして最後にこれを使ってテストします。
以下のテストは通ります。

```rust
#[test]
fn test_tokenize_complex_list() {
    let expected = Token {
        element: MDElement::Root,
        children: vec![
            Token {
                element: MDElement::UnorderedList,
                children: vec![
                    Token {
                        element: MDElement::UnorderedListItem(
                            0,
                            "**hello, world!**".to_string(),
                        ),
                        children: vec![Token {
                            element: MDElement::Strong("hello, world!".to_string()),
                            children: vec![],
                        }],
                    },
                    Token {
                        element: MDElement::UnorderedList,
                        children: vec![Token {
                            element: MDElement::UnorderedListItem(
                                1,
                                "*hello, world2!*".to_string(),
                            ),
                            children: vec![Token {
                                element: MDElement::Emphasis("hello, world2!".to_string()),
                                children: vec![],
                            }],
                        }],
                    },
                ],
            },
            Token {
                element: MDElement::OrderedList,
                children: vec![
                    Token {
                        element: MDElement::OrderedListItem(0, "hello, world3!".to_string()),
                        children: vec![],
                    },
                    Token {
                        element: MDElement::OrderedListItem(0, "hello, world4!".to_string()),
                        children: vec![],
                    },
                ],
            },
        ],
    };

    assert_eq!(
        parse(
            "- **hello, world!**\n    - *hello, world2!*\n1. hello, world3!\n2. hello, world4!"
        ),
        expected
    );
}
```