自作のマークアップ言語が作りたくなってしまったので、Typstを参考にしようとコードを読んでいたときの話です。

TypstのSyntaxNode（AST）にはソースコード上の位置を表すSpanという構造体があります。ところで、速いと噂のOXCというRustで書かれたJavaScriptパーサーのASTも同じ名前の構造体を持っています。私はどちらも同じものだと思っていましたが違いがあって面白かったのでメモを残します。

OXC ​

OXCにおけるSpanは単一ソースファイル上のトークンの位置を表すものです。

// oxc/crates/oxc_span/src/span/types.rs
pub struct Span {
    pub start: u32,
    pub end: u32,
}

ちなみに、この記事を書くために調べていたところSpanの元ネタはRust analyzerのTextRangeのようです。

Typst ​

一方のTypstは

pub struct Span(NonZeroU64);

このように一つの数で表されています。

この数字はSyntaxNodeで構成されたツリーに対して、子は親より大きい数字になるように、兄弟では弟のほうが兄より数字が大きくなるように振られています。

これは文章の末尾ではない箇所が変更された場合に、Spanの変更箇所が少なくなるというメリットがあります。TypstタイプのSpanではあらかじめ先頭は最小の数、末尾は最大の数が割り当てられており、その間で変更した場合は使われていない中間の数を割り当てるだけで済みます。一方で、OXCタイプでは先頭からの位置に依存しているため、変更箇所以降のすべての位置情報が芋づる式にずれていきます。そのため基本的には変更ごとに全体をパースすることになります。

実際に調査したわけではありませんが、Spanの実装を含めTypstのASTはBiomeなどで使われているRed Green Treeの雰囲気を感じました。そこら辺についてもいつか調べてみたいと思います。