シンボルテーブルとスコープ

名前解決は、ソースコード中の名前使用を宣言または候補宣言に関連付けます。シンボルテーブルはこれらのアイデンティティと関連情報を保持し、後の型チェック、キャプチャ解析、コード生成がこれに依存します。複雑な言語では、これらのフェーズが交差することがあり、すべての名前が型情報なしで一度に解決されるとは限りません。

最も重要な区別は、スペル（綴り）とアイデンティティです：どちらも x と呼ばれる変数は異なるシンボルである可能性があり、同じシンボルもエイリアスや修飾パスを通じてアクセスできる場合があります。

スコープが名前の可視性を決定する

レキシカルスコープは、プログラムの構造に基づいてルックアップ環境を決定します。言語が内側が外側をシャドーイングすることを許可していると仮定すると、内側に入ると内側の宣言が優先して見つかり、外に出ると外側の環境が復元されます。

宣言がいつ可視になるかは言語によって規定されます。関数が前方参照を許可するかどうか、ローカル変数が自身の初期化子内で可視かどうか、同じブロック内での再宣言がエラーかどうかは、「定義に出会ったらテーブルに置く」という単純なルールでは仕様を代替できません。

例えば let x = x + 1 において、ある言語では右辺が前の x を指すことを許可しますが、他のルールでは新しい宣言が未初期化の状態に置かれる可能性があります。実装は、宣言、初期化、読み取り可能状態を区別する必要があります。

簡潔なレキシカル環境の実装

各スコープは、名前を SymbolId にマッピングするマップと parent を保持します。insert は現在のスコープでの重複ルールのみをチェックします。lookup は現在の環境から親チェーンをたどって検索します。lookup_current は、現在の層のみを検索する必要があるシナリオで使用されます。

ハッシュテーブルでの各層のクエリは通常 O(1) が期待されますが、親チェーンの検索は深さに依存します。名前ごとのバインドスタック、アンドゥログ、または永続マップを使用して実装することもでき、「スコープスタックを採用しなければ正しくない」という唯一のデータ構造は存在しません。

解析が終了した後、AST や IDE インデックスが SymbolId を参照している場合、シンボルレコードは存続し続けなければなりません。現在アクティブなスコープをポップすることは、後続のフェーズで参照される宣言データをすべて削除することを意味しません。一時的なトラバーススタックと長期的なシンボルストレージを分離することで、ダングリングインデックスを回避できます。

アクティブな環境は退出できるが、解決済みの参照は消えてはいけない

以下に、教育用言語のルールを定義します：同じ層での同名宣言はエラーとなり、内側ではシャドーイングが許可されます。値の名前のみを処理し、インポートやオーバーロードはサポートしません。シンボルレコードは今回の解析用の arena に保存され、スコープはレコードのインデックスのみを保持します。この整数 ID は現在の解析内では安定していますが、ファイル編集をまたいで自然に安定するグローバル ID ではありません。

from dataclasses import dataclass

@dataclass(frozen=True)
class Symbol:
    name: str
    declaration: str

class Scope:
    def __init__(self, parent=None):
        self.parent = parent
        self.names = {}

    def declare(self, arena, name, location):
        if name in self.names:
            raise ValueError(f"duplicate {name}: {location}")
        identity = len(arena)
        arena.append(Symbol(name, location))
        self.names[name] = identity
        return identity

    def lookup(self, name):
        current = self
        while current is not None:
            if name in current.names:
                return current.names[name]
            current = current.parent
        raise NameError(name)

arena = []
outer = Scope()
a = outer.declare(arena, "x", "line 1")
inner = Scope(outer)
assert inner.lookup("x") == a  # 内側の宣言が登場する前
b = inner.declare(arena, "x", "line 3")
resolved_use = inner.lookup("x")
assert resolved_use == b and a != b
try:
    inner.declare(arena, "x", "line 4")
except ValueError:
    pass
else:
    raise AssertionError("duplicate accepted")
assert len(arena) == 2  # 失敗した挿入は幽霊レコードを残さない
active = outer
assert active.lookup("x") == a
assert arena[resolved_use].declaration == "line 3"
try:
    active.lookup("missing")
except NameError:
    pass
else:
    raise AssertionError("unresolved name accepted")

arena の最後の読み取りについて：内側を退出した後でも、解決済みの使用箇所は依然として内側の宣言を指しています。コード生成や「定義へのジャンプ」は、現在の外側の環境から lookup("x") を再実行してはいけません。そうしないと、内側の参照が誤って外側に再バインドされてしまいます。

同じブロック内での連続するシャドーイングをサポートするには、各宣言の後に新しい可視性層を作成するか、バインドスタックのルールを調整する必要があります。この例の「同じ層での重複はエラー」という方針を採用しながら、Rust の let ルールを完全に実装したと主張することはできません。rustc のスコープ層

スコープを離れると、古い参照は再バインドされるのか？

使用箇所を宣言 ID に接続することは、x に単に同じ色を塗るよりも正確です。内側に入ると新しいルックアップで S1 が得られ、退出すると S0 が得られるかもしれませんが、以前に記録された参照が現在の環境の x に再解決されることはありません。クロージャの使用箇所にも独自のバインド根拠があります。以下のスイッチは新しいソースコード解析を再構築し、宣言の削除や変更をランタイムでの変数再バインドと誤解しないようにします。

シンボルレコードはどのような情報を保持すべきか

名前空間も言語によって規定されます。C では、tag 名と通常の識別子は異なる名前空間に属します。ラベルには独自のスコープがあります。すべてのスペルを分類のない単一のテーブルに置くと、重複の誤検知や定義の誤検索を招きます。

モジュールインポート：候補のソースとアクセス権限

モジュールパス、明示的インポート、ワイルドカードインポート、エイリアス、組み込み名の間には、優先順位が異なります。シンボルテーブルは候補のソースを保持し、「2つのインポートがどちらもこの名前を提供している」という曖昧さを報告しやすくする必要があります。最後に挿入された方を任意に選ぶのではなくです。

宣言が1つ見つかることと、現在の位置からアクセスできることは別の問題です。可視性チェックは、モジュール階層、パッケージ、または他の言語ルールに依存する可能性があり、単に public/private の2値だけではありません。

モジュールの循環も必ずしも違法ではありません。ある言語では、宣言を先に収集してから関数本体を解析するか、強連結成分を処理することを許可します。他の言語では特定の種類の依存関係の循環を禁止します。再帰的なインポートに遭遇した場合は無限解析を防ぐ必要がありますが、すべての循環に対して無条件にエラーを報告してはいけません。Rust の名前解決は、マクロ展開や異なる名前空間とも連携します。rustc の名前解決

オーバーロード：候補のルックアップとターゲットの選択は段階的に行える

オーバーロードがある言語では、まず名前とスコープに基づいて候補集合を取得し、その後、引数の数、型、暗黙的変換、ジェネリクス制約を組み合わせて呼び出し可能なターゲットを選択します。メンバーのルックアップはレシーバーの型にも依存します。

したがって、「lookup が1つのシンボルを返す」のは単純な言語のインターフェースにすぎません。複雑な実装では、候補、遅延解決項目、またはエラープレースホルダーを返し、診断用のソース情報を保持できます。

クロージャのキャプチャ：名前解決は最初のステップのみ完了

クロージャが外側のローカル変数を参照する場合、パーサーはそれがどの外部バインドを指しているかを理解する必要があります。キャプチャ方法、環境レイアウト、エスケープは、クロージャがその値をどのように使用するかと言語の所有権ルールを分析する必要があります。

fn main() {
    let values = vec![2, 4, 6];
    let length = || values.len();
    assert_eq!(length(), 3);
    assert_eq!(values[0], 2);
}

ここでは Vec の長さを取得するには共有借用だけでよく、Vec が Copy でないからといって自動的に所有権がムーブされるわけではありません。move キャプチャも、クロージャが1回しか呼び出せないことを意味しません。Fn、FnMut、FnOnce は、クロージャが呼び出されるときにキャプチャ値をどのように使用するかによって決まります。Rust クロージャの説明

キャプチャされたからといって、必ずヒープ割り当てが必要になるわけではありません。エスケープしないクロージャはスタック環境を使用する可能性があり、値によるキャプチャでデータをクロージャオブジェクトに配置できます。最適化により環境が削除されることもあります。真に必要なことは、キャプチャされた値が必要な期間中有効であることです。借用、コピー、ムーブ、ボックス化、または upvalue は、異なる実装手段です。

クロージャでも、呼び出し時に同名の変数で再検索することはできない

レキシカルバインドが確定した後、その後の同名宣言は、既存のクロージャを新しい宣言に再接続しません。以下の Rust の例では、クロージャは常に最初の value を参照します。2番目の value は、その後に直接使用される名前をシャドーイングしているだけです。両方のバインドは必要な期間中有効です。

fn main() {
    let value = 10;
    let read_old = || value;
    let value = 20;
    assert_eq!(read_old(), 10);
    assert_eq!(value, 20);
    assert_eq!(read_old(), 10);
}

これは「キャプチャが値によるか参照によるか」という2つの次元とは異なります。まず、どのバインドを参照しているかを決定し、次にそのバインドをクロージャにどのように提供するかを決定します。言語が参照された同じバインドの変更を許可している場合、その後の読み取りでは新しい値が観察される可能性があります。しかし、別の同名バインドに切り替えることは、元のバインドを変更したことにはなりません。

ジェネリクスインスタンス：ソースシンボルとバックエンドインスタンスは別々に管理

1つのジェネリック宣言には安定したアイデンティティがあり、具体的な型引数がインスタンス化コンテキストを構成します。バックエンドは、「宣言アイデンティティ + 置換引数」などのキーでインスタンスをキャッシュでき、毎回ソース言語のスコープシンボルをコピーする必要はありません。

コード生成で単一化するか、共有実装を使用するか、辞書渡しかは後続の戦略です。異なる型引数でも、最終的に異なるマシンコードが必ず残るとは限りません。最適化、インライン展開、リンク時の重複削除が生成物に影響を与えます。

バッチコンパイルから IDE へ

バッチトラバースではアクティブな環境スタックを使用できますが、インタラクティブシステムでは、変更されたシンボルアイデンティティ、依存関係の有効期限切れ、古い位置マッピングを処理する必要があります。1つの関数本体の編集が、理由もなくプロジェクト全体のすべてのシンボルアイデンティティを変更すべきではありません。公共的な宣言の変化では、依存関係の再チェックが必要になる可能性があります。

診断では、使用箇所、候補宣言、具体的な失敗ルールを同時に指摘するのが望ましいです。例えば、「この名前はプライベートモジュールから来る」または「2つのワイルドカードインポートが曖昧さを生んでいる」などとし、すべてを「シンボルが見つからない」に変換してはいけません。

参考

• rustc Name Resolution。
• Rust Closures。
• 型システム、LSP。

Keywords: symbol table, SymbolId, lexical scope, shadowing, namespace, visibility, overload, closure capture, lifetime