Markdown パーサを書きたい！～パーサを作る編～
この記事は某企業 2024 年度新卒 Advent Calender 2024 10 日目の記事です。
前回の記事ではパーサコンビネータを作りました。
今回はこれらを使って実際に Markdown パーサを作ってみます。
今回のゴール
パーサは文字列から何らかの構造に変換するものでした。
Markdown パーサにおいて、この何らかの構造は抽象構文木になります。
抽象構文木はwikiによると
抽象構文木（ちゅうしょうこうぶんぎ、英: abstract syntax tree、AST）は、通常の構文木（具象構文木あるいは解析木とも言う）から、言語の意味に関係ない情報を取り除き、意味に関係ある情報のみを取り出した（抽象した）木構造の木である。
と説明されています。
ちょっと意味がわからないので以降の説明を見ると
抽象構文木は具象構文木とは異なり、プログラムの意味に関係ない部分を省略する。そのような省略の例としては括弧の省略があげられる。抽象構文木では、その自然な木構造によって結合は自明であるから、グループ化のための括弧などは意味的に不要である。変数名などの名前なども、識別できればよいので何らかの ID のようなもので構わない。
とあります。
つまり、Markdown において抽象構文木は文章構造から本質的に意味のある部分を抽出して、木構造にしたものということですかね。
イメージにするとこんな感じでしょうか。
抽象構文木はある種の中間表現で、この木を使ってレンダリングすることで HTML にしたり、あるいは JSON にしたりといった事ができるようになっています。
今回の記事はこの抽象構文木を Markdown テキストから作るのがゴールです。
作る時間の関係で対応していない構文やバグがありますが許してください。
決して面倒だからではありません
抽象構文木の定義
ではまず、抽象構文木を定義していきます。
抽象構文木はその名と通り木構造です。
なのでこのような形で定義してみます。
#[derive(Debug, PartialEq, Clone)]
struct Token {
element: MDElement,
children: Vec<Token>,
}
Tokenは木構造の各ノードを表しています。
elementはヘッダーや強調などの要素を表すもので、childrenはelementにぶら下がるノードのリストという感じで、再帰的な定義になっています。
では次に、MDElementを定義します。
#[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 でパーサコンビネータを作ってみる (後編)を参考にさせていただいております。
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という関数を定義します。
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を作ります。
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")をつけると改行がない場合マッチしません。
なので、正規表現の?のようなものを作ります。
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 要素のパーサを作ってみます。
なお、ここからは記事が長くなってしまうので、テスト部分は省略します。
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
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
fn blockquote(s: &str) -> Option<(MDElement, &str)> {
lb!(string(">").and(characters_trim()))(s)
.map(|((_, text), rest)| (MDElement::Blockquote(text), rest))
}
引用です。引用は>>のような感じでネストできるらしいので、> のように空白を入れないようにしています。
Emphasis, Strong, Strikethrough
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
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
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
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
fn horizontal_rule(s: &str) -> Option<(MDElement, &str)> {
lb!(string("---").or(string("***")))(s).map(|(_, rest)| (MDElement::HorizontalRule, rest))
}
水平線です。特筆すべきことはありません。
Span
ここまでの要素は比較的かんたんに作れるのですが、text*emphasis*text2のように途中に要素が存在する場合に最初のtextを抽出するパーサは少し考える必要があります。
正規表現ならば先読みを使って抽出できますが、今使っている regex クレートが先読みに対応してませんでした。
なので自力で作ります。
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**のような入れ子構造のものもパースできるようにするため、再帰関数になるようにします。
再帰的にパースしていくために中身のテキストを取得する必要があります。
なので以下のような関数を作っておきます。
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 つ目はテキストがプレーンテキストである場合です。
後者のプレーンテキストである場合というのがまだ判定できないので、定義します。
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 要素と同じような感じですが、含まれるかどうかの判定だけなので正規表現でやっています。
そしてこれらを使いパースする関数を作ります。
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関数を使ってテストしてみます。
#[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 パーサを作ったのでこの記事の目標は達成ですが、レンダリングしないと抽象構文木も意味がないので、次回レンダリング編を書こうと思います。
それでは。
参考文献
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に要素を追加します。
#[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を使って以下のパーサを作ります。
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ずつ上げてインデントレベルに対応した要素を処理しています。
この方針に従って書いたものがこちらです。
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に組み込むと
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だけ特別処理する形となっています。
そして最後にこれを使ってテストします。
以下のテストは通ります。
#[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
);
}