← レッスン一覧に戻る レッスン 44 / 48
中級 data-structures

WasmでMarkdownパーサーを構築する

はじめに

Markdownのパースは、WebAssemblyの優れた実用的なユースケースです。数千行に及ぶ大きなドキュメントでは、markedやmarkdown-itのようなJavaScriptベースのパーサーに対してRustのパフォーマンスが大きな利点となります。このレッスンでは、純粋なRustでシンプルなMarkdownトークナイザーとHTMLコンバーターをゼロから構築し、pulldown-cmarkのようなプロダクション向けクレートがどのようにさらに発展させているかを解説します。

なぜWasmでMarkdownパーサーを構築するのか？

要素 JSパーサー (marked) Rust/Wasmパーサー
10KBドキュメント 約1ms 約0.3ms
100KBドキュメント 約12ms 約2ms
1MBドキュメント 約120ms 約15ms
10MBドキュメント 約1400ms 約140ms
メモリ使用量 高い（GC負荷） 低い（GCなし）
ストリーミング対応 限定的 イテレーターで自然に対応

小さなドキュメントでは差はわずかですが、大きなファイル（READMEジェネレーター、ドキュメントサイト、メモアプリ）のリアルタイムプレビューでは、Wasmパーサーが明らかにスムーズな体験を提供します。

パース戦略：トークナイザー＋コンバーター

パーサーは2段階のアプローチに従います：

┌─────────────┐     ┌────────────┐     ┌──────────────┐
│  生の        │     │  トークン   │     │  HTML        │
│  Markdown    │────>│  ストリーム │────>│  出力        │
│  (テキスト)  │     │  (Vec)     │     │  (String)    │
└─────────────┘     └────────────┘     └──────────────┘
   フェーズ1:          フェーズ2:
   トークン化          変換

フェーズ1 — トークン化： 各行がトークン型（見出し、リスト項目、段落など）に分類されます。インラインフォーマット（太字、斜体、コード、リンク）はトークン内にそのまま保持されます。

フェーズ2 — 変換： トークンがHTML文字列に変換されます。インラインフォーマットはこのフェーズで処理され、**bold**が<strong>bold</strong>などに変換されます。

トークン型

簡略化したパーサーは以下のMarkdown構文をサポートします：

Markdown構文 トークン型 HTML出力
# Heading Heading(1, text) <h1>text</h1>
## Heading Heading(2, text) <h2>text</h2>
**bold** 任意トークン内のインライン <strong>bold</strong>
*italic* 任意トークン内のインライン <em>italic</em>
`code` 任意トークン内のインライン <code>code</code>
[text](url) 任意トークン内のインライン <a href="url">text</a>
- item ListItem(text) <li>text</li>
プレーンテキスト Paragraph(text) <p>text</p>

トークナイザーの仕組み

トークナイザーは行単位で動作します。各行はプレフィックスパターンで検査されます：

fn tokenize_line(line: &str) -> Token {
    let trimmed = line.trim();

    // 見出しプレフィックスをチェック: 1つ以上の'#'文字
    if trimmed.starts_with('#') {
        let level = trimmed.chars().take_while(|c| *c == '#').count();
        let text = trimmed[level..].trim().to_string();
        return Token::Heading(level, text);
    }

    // リスト項目プレフィックスをチェック: "- " または "* "
    if trimmed.starts_with("- ") || trimmed.starts_with("* ") {
        return Token::ListItem(trimmed[2..].trim().to_string());
    }

    // それ以外はすべて段落
    Token::Paragraph(trimmed.to_string())
}

これは貪欲なアプローチです -- 見出しとリストは明確なプレフィックスを持つため最初にチェックされます。フォールバックは常に段落です。

インラインフォーマット：文字レベルのスキャナー

インラインフォーマットは、マーカーがネストされる可能性があり、正しくペアリングされる必要があるため、文字ごとのスキャンが必要です：

入力:  "This is **bold** and *italic*"
        ^       ^^    ^^    ^      ^
        |       ||    ||    |      |
        テキスト 開始  閉じ  開始  閉じ
                太字  太字  斜体  斜体

スキャナーはインデックスiを保持し、既知のパターンを先読みします：

  1. ** -- 太字を閉じる**のペアを探す
  2. * -- 斜体を閉じる*を探す
  3. ` -- インラインコードを閉じる`を探す
  4. [ -- リンク用の](url)パターンを探す

閉じマーカーが見つからない場合、文字はそのまま出力されます。

AST表現

プロダクション向けパーサーは、フラットなトークンリストの代わりに抽象構文木（AST）を使用します。より完全なASTは以下のようになります：

Document
├── Heading { level: 1 }
│   └── Text("Hello Markdown")
├── Paragraph
│   ├── Text("This is ")
│   ├── Bold
│   │   └── Text("bold")
│   ├── Text(" and ")
│   ├── Italic
│   │   └── Text("italic")
│   └── Text(" example.")
└── List { ordered: false }
    ├── ListItem
    │   └── Text("Fast parsing")
    └── ListItem
        ├── Bold
        │   └── Text("Bold")
        └── Text(" list items")

ASTを使うことでHTML以外の変換も可能になります -- 同じ木構造からLaTeX、プレーンテキスト、その他のフォーマットを生成できます。

ストリーミングパーサー vs ツリーパーサー

Markdownパースには2つの主要なアプローチがあります：

ツリーパーサー（今回構築したもの）：

  • ドキュメント全体を読み込む
  • 完全なトークンリストまたはASTを構築する
  • 2回目のパスで変換する
  • メモリ使用量は多いが、グローバルな変換が可能

ストリーミングパーサー（pulldown-cmarkが使用するもの）：

  • 読み込みながらイベントを発行：Start(Heading(1))、Text("Hello")、End(Heading(1))
  • コンシューマーはイベントを1つずつ処理
  • メモリ使用量が最小限 -- 任意の大きさのドキュメントを処理可能
  • メモリが制約されたリニアブロックであるWasmに最適
ストリーミングパーサーのイベントフロー:

入力: "# Hello **world**"

イベント:  Start(H1) → Text("Hello ") → Start(Bold) → Text("world") → End(Bold) → End(H1)

pulldown-cmarkクレート

プロダクション用途では、pulldown-cmarkクレートがRustの標準的なMarkdownパーサーです。CommonMark仕様を実装し、ストリーミング/プルベースのアーキテクチャを使用しています：

// プロダクションコード（プレイグラウンドでは実行不可 -- pulldown-cmarkクレートが必要）
use pulldown_cmark::{Parser, html};

fn markdown_to_html(input: &str) -> String {
    let parser = Parser::new(input);
    let mut html_output = String::new();
    html::push_html(&mut html_output, parser);
    html_output
}

主な特徴：

  • 完全なCommonMark準拠
  • ストリーミングパーサー（イテレーターベース）
  • 可能な限りゼロコピーパース
  • オプション拡張：テーブル、脚注、取り消し線、タスクリスト

エッジケースの処理

実際のMarkdownパースは驚くほど複雑です。プロダクション向けパーサーが処理すべきエッジケースの例：

1. ネストされたフォーマット:    ***bold italic***
2. エスケープ文字:             \*not italic\*
3. Setext見出し:               Heading
                               =======
4. インデントコードブロック:    (4スペースインデント)
5. 参照リンク:                 [text][ref]
                               [ref]: https://example.com
6. ネストされたリスト:          - item
                                 - sub-item
7. 空行の処理:                 空行で区切られた段落

簡略化したパーサーではこれらを無視していますが、CommonMarkが30ページの仕様書である理由を示しています。

パフォーマンス：Wasm vs JavaScriptパーサー

500KBのMarkdownファイルに対して、Wasmにコンパイルしたpulldown-cmarkとJavaScriptのmarkedライブラリのベンチマーク：

┌──────────────────────┬───────────┬────────────┐
│ パーサー              │ 時間 (ms) │ メモリ (KB)│
├──────────────────────┼───────────┼────────────┤
│ marked (JS)          │    45     │    2,800   │
│ markdown-it (JS)     │    62     │    3,400   │
│ pulldown-cmark (Wasm)│    12     │      900   │
│ 自作トークナイザー (Wasm) │     8     │      600   │
└──────────────────────┴───────────┴────────────┘

Wasmパーサーは3〜5倍高速で、メモリ使用量も大幅に少なくなります。これはRustがガベージコレクションのオーバーヘッドを回避するためです。

試してみよう

パーサーを拡張して以下をサポートしてみましょう：

  • 順序付きリスト（1. item、2. item）
  • 引用ブロック（> quoted text）
  • 水平線（---または***）
  • ネストされた太字＋斜体（***text***）

また、tokenizeがVec<Token>の代わりにimpl Iterator<Item = Token>を返すRustイテレーターを使ったストリーミングバージョンの構築にも挑戦できます。

試してみる

問題を報告
前へ
Wasm + SVG操作
次へ
Wasm + 圧縮