AST設計とエラー復旧

構文木は、フロントエンドと後続の解析フェーズ間の契約である。それは正しいプログラムの構造を表現するだけでなく、途中での編集されたソースコードの保存方法、エラーの特定方法、および糖衣除去されたノードの起源を追跡する方法を決定する必要がある。最適化器に適した木とフォーマッターに適した木は、しばしば異なるレベルの情報を保持する。

AST、CST、損失なき構文木

ASTは、後続の処理に直接関与する必要のない文法の詳細を省略する。例えば 1 + (2 * 3) の括弧は木構造のネストで表現でき、括弧自体を独立したノードとして保持する必要はない。

構文木（CST）はより多くの文法構造を保持するが、「CST」という名称自体がすべての空白やコメントの保持を保証するものではない。⁠損失なき構文木は、トリビア（空白やコメント）、エラートークンなど、完全な原文を復元できることを明確に要求する。レキサによって破棄された情報は、木がCSTと呼ばれているからといって自動的に戻ってくるわけではない。

rust-analyzerの構文層は損失なき木を採用し、型付きアクセス層を提供している。これは、統一された基盤ノードと専用のASTインターフェースを組み合わせることが可能であり、排他的な選択ではないことを示している。rust-analyzer構文設計

RustcのAST、HIR、およびGHCのCoreは異なるコンパイルフェーズの表現であり、それらを「まずCST、その後で真のAST」というように統一して記述することはできない。AST自体がマクロ呼び出しや括弧などの高レベル情報を保持することができ、抽象化の程度は設計上の選択である。

専用型と統一ノード

専用ノードは、enumやクラス階層を通じて構造制約を表現する。以下のRustの定義は、二項演算子が2つのオペランドを持つことを明確にし、欠落した入力に対する出口を残している：

#[derive(Clone, Copy)]
struct Span { start: usize, end: usize }

enum BinaryOp { Add, Multiply }
struct Expr { kind: ExprKind, span: Span }
enum ExprKind {
    Number(i64),
    Binary { op: BinaryOp, left: Box<Expr>, right: Box<Expr> },
    Missing,
    Invalid,
}

実際のSpanにはファイルとバージョンをバインドするか、所属する構文木からスナップショットアイデンティティを取得する必要がある。Boxを使用するのは最も直感的な再帰的な所有関係である。arenaにExprIdを追加することで、集中割り当てが可能になり傍表の構築が容易になるが、IDがarenaやバージョンを跨いで混用されないように注意する必要がある。共有不変木は構造の再利用に適しているが、親ノードやコンテキストを別途表現する必要がある。

統一ノードは、kind、children、およびトークンリストを使用して構造を表現し、単純なトラバーサルと拡張の容易さを提供する。その代償として、「何番目の子供が何であるか」を制約するために実行時チェックまたは型付きラッパーが必要になる。enumを使用しても、名前がバインドされているか、型が正しいかなどの意味的不変条件が自動的に保証されるわけではない。

解析結果は傍表に配置できる。例えば、ExprIdから型、シンボル、定数値へのマッピングなど。これにより、異なるフェーズで同じ汎用ノードを絶えず修正する必要がなくなり、依存関係の無効化に基づいたキャッシュが容易になる。

Spanとソースマッピング

半開バイト区間はスライスに適しているが、対応するソースコードのスナップショットに対してのみ有効である。マクロ展開には複数のソースが含まれる可能性がある：呼び出し箇所、マクロ定義位置、引数の断片。糖衣除去やインライン化により、独立したソーステキストを持たないノードが生成される場合もある。この場合、source mapやソースチェーンを保持する必要があり、単純にすべての子ノードの最小起点と最大終点を取ることはできない。

「ノード全体の範囲」と「主要な診断の強調表示範囲」が異なる場合もある。二項演算子は式全体を覆うspanを持つことができ、同時に演算子の位置を個別に保存することで、「この演算子は型をサポートしていない」というエラーをプラス記号に正確に指向させることができる。

欠落したトークンは、挿入を提案するゼロ幅区間でマークできる。無効なトークンは、実際に占める範囲を保持する。バイトスライスが有効なのは、境界が正しいエンコーディング位置にあることを保証した場合のみである。行・列の変換についてはレキサ設計を参照。

Lowering：後続フェーズがより単純な意味論と向き合うようにする

例えば、forループをイテレータの初期化、次の要素の繰り返し取得、条件分岐、およびループ本体に降格させることで、後続のフェーズが処理する必要がある文法の種類を減らすことができる。ただし、初期化が1回だけ実行されること、評価順序が正しいこと、breakとcontinueが正しいターゲットを指していること、そしてスコープとリソース解放の規則に従うことを維持する必要がある。

loweringでは、一時変数や新しいノードアイデンティティを導入できる。これらはユーザーのソースコードにマッピングできる必要がある。そうしないと、診断が内部の一時変数名を露出したり、複数の糖衣除去されたノードのエラーが同じ位置に重複して報告されたりする可能性がある。名前解決とloweringの順序は言語に依存し、すべての実装が同じフェーズでバインディングを完了することを要求することはできない。

エラー復旧：既知の構造を保持し、合法なプログラムとして偽装しない

let x = 1 + ; let y = 2; を考える。パーサは加法の左側が1であることを確定したが、右側が欠落している。セミコロンの前にMissingExprを挿入し、欠落したノードを含むBinaryを返すことで、文レベルがセミコロンを消費し、次の宣言に進むことができる。

このような木は「データ構造が後続のトラバーサル可能である」という規約を満たすが、元のプログラムが文法的または型論理的に正しいことを意味しない。バッチコンパイラはエラーを報告した後にコード生成を停止できる。IDEは、有効な局所部分に対して緩やかな解析を続ける。すべてのツールがファイルの末尾まで復元することを要求することはできず、エラープレースホルダーが実行可能な正常な値にこっそり変化するのを許してはならない。

欠落した式を文レベルに戻し、次の宣言を解析可能にする

ここでは、事前にトークン化された let name = number [+ number ...] ; のみを処理する。ブロック、括弧、または任意の式は含まない。位置はトークンインデックスで表され、ソースコードのバイトspanを装わない。欠落したオペランドはゼロ幅区間で、無効なオペランドは1つの実際のトークンを占める。

class RecoveringParser:
    def __init__(self, tokens):
        self.tokens = list(tokens)
        self.pos = 0
        self.errors = []

    def peek(self):
        return self.tokens[self.pos] if self.pos < len(self.tokens) else None

    def atom(self):
        token, start = self.peek(), self.pos
        if token is None or token == ";":
            self.errors.append((start, "missing expression"))
            return ("Missing", start, start)  # 文の境界を飲み込まない
        self.pos += 1
        if token.isascii() and token.isdecimal():
            return ("Number", int(token), start, self.pos)
        self.errors.append((start, "invalid expression"))
        return ("Invalid", start, self.pos)

    def expr(self):
        left = self.atom()
        while self.peek() == "+":
            self.pos += 1
            left = ("Add", left, self.atom())
        return left

    def parse(self):
        nodes = []
        while self.peek() is not None:
            start = self.pos
            head = self.tokens[self.pos:self.pos + 3]
            if (len(head) == 3 and head[0] == "let" and head[2] == "="
                    and head[1].isascii() and head[1].isalpha() and head[1] != "let"):
                self.pos += 3
                node = ("Let", head[1], self.expr())
            else:
                self.errors.append((start, "invalid declaration"))
                node = ("InvalidDeclaration", start)
            if self.peek() != ";":
                self.errors.append((self.pos, "expected semicolon"))
                while self.peek() not in (None, ";"):
                    self.pos += 1
            if self.peek() == ";":
                self.pos += 1
            nodes.append(node)
            assert self.pos > start  # 外側のループでは必ず入力を消費する
        return nodes


parser = RecoveringParser(["let", "x", "=", "1", "+", ";", "let", "y", "=", "2", ";"])
nodes = parser.parse()
assert nodes[0][2] == ("Add", ("Number", 1, 3, 4), ("Missing", 5, 5))
assert nodes[1] == ("Let", "y", ("Number", 2, 9, 10))
assert parser.errors == [(5, "missing expression")]
assert parser.pos == 11
for tokens in ([], [";"], ["@"], ["let", "x", "="], ["let", "x", "=", "1", "+"]):
    p = RecoveringParser(tokens)
    p.parse()
    assert p.pos == len(tokens)

exprは5番目のトークンのセミコロンの前にMissingを返し、文レベルはそのセミコロンを消費し、外側はyの解析を続ける。atom自体は進まない可能性がある。それは境界を前進できる呼び出し元に渡すからである。「各関数が毎回トークンを消費する」と要求すると、外側が必要とする区切り文字を飲み込んでしまう可能性がある。

この例では単純な同期戦略を採用しており、セミコロンがない場合、後続の宣言をスキップする可能性があり、診断の完全な重複排除も行われていない。復旧の品質を高めるには、次の宣言の開始などのコンテキスト境界を追加し、ブロックをサポートした後に } をブロックパーサに戻す必要がある。ここで示しているのは、局所的な欠落復旧と進捗契約であり、汎用のIDEパーサではない。

オペランドが1つ足りない場合、なぜセミコロンを飲み込んではいけないのか？

欠落と無効という2つのエラータイプを比較することで、復旧ノードが異なる範囲を必要とする理由が見えてくる。セミコロンの前のMissingには原文がないが、@ に対応するInvalidは実際のトークンを1つ占める。復旧は木に欠陥を記録し、文レベルが続行できるようにするだけであり、Missingを自動的に0に補完することも、yが解析できるからといってプログラム全体が有効であると主張することもできない。下の図は、原文の保持と意味木構築を分離して表示している。

3つの一般的な復旧手法は組み合わせ可能

部分的修復は、証拠が十分にある場合に欠落したトークンを挿入するか、明らかに不要なトークンを削除することである。例えば、呼び出し実引数と外側のセミコロンが見えている場合、右括弧の補完を提案する可能性がある。修復の回数とコストを制限し、一連の推測が実際の構造を隠蔽しないようにする必要がある。

同期復旧は、セミコロン、閉じ括弧、次の宣言の開始などの境界にジャンプする。境界は現在の文法コンテキストによって決定される： } に遭遇した場合、無条件に消費するのではなく、外側のブロックパーサに返すのが一般的であり、そうしないと正しいブロック終了を飲み込んでしまう。スキャン時には括弧のネストも考慮する必要があり、内側の任意のセミコロンで停止してはならない。

明示的なエラールールは、特定の例外パスに定義された意味論的結果を与える。Bisonの error は特殊な復旧シンボルであり、スタックのポップと入力の破棄に関与し、任意のトークンにマッチする通常の字句ワイルドカードではない。詳細なプロセスはLR解析を参照。

これらの手法はすべてエラーノードを生成でき、スキップされたトークンを損失なき木に保存することもできる。「パニックモードは必ず原文のすべてを捨てる」というのは、メカニズム自体の要件ではない。

2つの実装不変条件

第一に、⁠復旧は進捗を保証しなければならない⁠：入力を消費し、現在の層を退出して境界を処理できる呼び出し元に任せる、またはEOFで終了する。ゼロ幅の欠落ノードが、同じループ内で同じ位置で継続的にエラーを生成してはならない。

第二に、⁠エラー値には伝播ルールがなければならない⁠：例えば、型チェックでMissingExprに遭遇した場合、専用のエラー型を返し、それによって派生する演算子の不一致診断を抑制しつつ、無関係な兄弟ノードのチェックは継続する。エラー型は通常の任意の型ではなく、ファイル全体をスキップできることを意味するものでもない。

診断はノードの保存とは独立して行うのが良く、エラーの種類、主要な位置、関連する位置、および修復提案を記録する。ノードはErrorIdまたは軽量な状態を保持するだけでよく、木の中に大量の重複するエラー文字列を保持する必要はなく、再解析後に診断を置き換えることも容易になる。

損失なき保存と意味的なプレースホルダーはそれぞれの責任を担う

復旧木内のMissingExprは合成構造であり、対応する原文を持たない。フォーマッターがこれをトラバーサルする際に自動的に0を出力すると、エラーのあるプログラムが別の合法なプログラムに変更されてしまう。Invalidノードの元のトークンを無視すると、ユーザーの入力が失われる。損失なき層は元の断片を保持し、修復提案は独立した編集操作として行うべきである。

以下は、トークン/トリビア層の往復保持のみのデモであり、コメント、空白、無効な文字 @ を含む。これは完全な損失なき木ではない。原文は再構築可能だが、パーサは同時に @ が無効であると報告できる。

import re
source = "let x = 1 + @; // keep this\n"
parts = re.findall(r"//[^\n]*|\s+|[A-Za-z_][A-Za-z_0-9]*|[0-9]+|.", source)
assert "".join(parts) == source
assert "@" in parts and "// keep this" in parts

後続の型チェックでは、Missingに対してErrorId付きのエラー結果を返し、「Intと欠落した型を加算できない」などの派生診断を発生させないようにする。ただし、同じ宣言以外の独立したエラーは引き続き報告されるべきである。コード生成では、ブロックするエラーが存在するかチェックする必要があり、木トラバーサルが成功したからといって、プレースホルダノードを任意の合法値として扱ってはならない。

復旧の品質をどう測定するか

有効なプログラムが正しい木を得られるかどうかに加えて、以下もチェックする必要がある：括弧を1つ削除した後、次の関数を保持できるか。欠落した式の後、関連するエラーが少量のみ報告されるか。EOFと深いネストで終了するか。損失なき木がエラー範囲を含む原文を再構築できるか。

増分システムでは、再利用された部分木の字句コンテキストとバージョンも確認する必要がある。1回の編集で文字列の閉じ方が変わるかどうかは、遠くにあるトークンに影響を与える可能性がある。テキスト領域が変更されていないからといって、必ずしも古い解析結果をそのまま再利用できるわけではない。

後続の意味解析は、シンボルテーブルとスコープ から続き、木上の名前がどのように安定した宣言アイデンティティを得るかを理解する。

Keywords: AST, CST, lossless syntax tree, trivia, arena, node identity, span, source map, lowering, missing node, error recovery, incremental parsing