脚注機能の実装に関するメモ

最近、このブログを作ってくれている Markdownパーサである almo ^[1] に脚注を実装しました。
(まさに今つかったこれです)

脚注は、 Common Mark ^[2] でも GFM ^[3]　でも定められていない構文ですが、長いドキュメントを書くときには結構欲しくなります。

ところで、脚注はパーサを書くことを考えると他の構文と比べてやや異質な存在です。
そのため実装の仕方に割と幅があります。　
この記事では almo の脚注の実装方法とどうしてそうなったか、というのを日記がてら振り返りたいと思います。

脚注の何が特別なのか？

そもそもたいていの md2html な処理系たちはたいてい次のようなフローで処理を行います。

Markdown をパースして AST に変換
AST を走査して HTML に変換

almo も同様です。

例えば

# Heading  1

**~~To be or not to be~~**

- list1
- list2
  - list3
  - list4

のような md ファイルを almo に渡して、

import almo

md = """
# Heading  1

**~~To be or not to be~~**

- list1
- list2
  - list3
  - list4
"""

ast = almo.parse(md)

ast.to_dot() してみると

という結果が吐かれてます。

ここから HTML に変換するわけです。

ここで、パースするとき・この AST から HTML を生成するとき　のうれしい性質として、「各ノードは独立に考えてもいい」というのがあります。

例えば HTML に変換するときは、それぞれのノードは (他のノードが valid な出力をしてくれているという前提に立って)、　自分が正しい出力をすれば良いだけです。

しかし、脚注は違います。

脚注は以下のような性質があります:

定義は末尾に生成される
番号を振る
未定義な脚注がないかチェックする

したがって、 AST 全体にわたるグローバルな状態を検査する必要があります。
これが脚注の他の構文との違いです。

どう実装するのか？

最初に自分が提案したのは、パースをする際に使う Reader にグローバルな状態を持たせてパースさせていくことでした。

というのも、実は類似の仕組みがすでに実装されていたためです。
これは almo 特有の事情ですが、Pyodide をロードするのは非常にコストがかかるので、不要ならこれをスキップするために「Pyodide が必要か？」というのを調べるために Reader クラスに情報を持たせる仕組みがすでにありました。

そのため、自分は当初これと同様の実装を提案しましたが、一緒に開発している友人から別の仕組みを提案されました。

そもそも、 Reader クラスにあまり情報を持たせるのはうれしくありません。この手の構文が増えるたびに肥大化していくのが目に見えています。

そこで、脚注の実装を AST に対する後処理として行うことを提案されました。

つまり、 (第一段階の) AST を作る段階では末尾に移動させる、正しい脚注定義がなされているかをチェックする、などの処理は行わず、 AST が完成した後に走査・操作を行なって所望の結果を得る、というものです。

この実装で統一することで「Pyodide が必要か？」という処理も単に特定のノードが含まれるかを最後にチェックするだけに書き直して、割とスッキリした実装になりました。

実装

実際の実装　では、

void move_footnote_to_end(Markdown& ast) {
    std::vector<std::shared_ptr<ASTNode>> footnote_defs =
        ast.nodes_byclass("FootnoteDefinition");

    std::shared_ptr<DivBlock> footnote_div =
        std::make_shared<DivBlock>("footnote");

    ast.pushback_child(footnote_div);

    for (auto node : footnote_defs) {
        ast.move_node(node, footnote_div);
    }
}

という感じで、脚注のノードを末尾に移動させる処理を行っています。　便利！

感想

こんな感じの流れでこういう実装にしたんだよね、という話を同じく自分のブログのためにマークアップ言語を作っている別の友人に話したら、「全く同じ議論で全く同じ方式に行き着いた」と言われてびっくりしました。　
おもしろいもんですね 🤗

今日の一曲

最近雨やばいですよね

[1] https://github.com/abap34/almo [2] https://spec.commonmark.org/ [3] https://github.github.com/gfm/

記事一覧
ホーム

RSS

@abap34

abap0002@gmail.com