Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 1461] ファイルの概要

このコミットは、Go言語の初期開発段階におけるprettyパッケージ（おそらくはGoコードの整形や解析に関連するツール群）に対する重要なリファクタリングと機能追加の準備を含んでいます。主な目的は、抽象構文木（AST）に型情報を追加するための基盤を整備すること、ファイル構造の整理、そしてコメント内のタブを含むファイルでより冪等な出力（何度実行しても同じ結果が得られること）を生成するための改善です。

コミット

commit c620dd9759f0fe06bf88a0c25a29f510250ab96d
Author: Robert Griesemer <gri@golang.org>
Date:   Fri Jan 9 16:28:09 2009 -0800

    - preparation to add type info to ast
    - consolidation of files, cleanup
    - more success producing idempotent output for some files with comments
      containing tabs
    - snapshot of the day
    
    R=r
    OCL=22474
    CL=22474

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/c620dd9759f0fe06bf88a0c25a29f510250ab96d

元コミット内容

- preparation to add type info to ast
- consolidation of files, cleanup
- more success producing idempotent output for some files with comments
  containing tabs
- snapshot of the day

変更の背景

このコミットは、Go言語のコンパイラまたはツールチェインの初期段階において、AST（抽象構文木）のセマンティックな情報を強化するための重要なステップです。当時のGo言語のprettyパッケージは、コードの解析、整形、おそらくは基本的な型チェックの機能を提供していたと考えられます。

変更の背景には以下の点が挙げられます。

  1. ASTへの型情報付与の必要性: プログラミング言語のコンパイラにおいて、ASTはソースコードの構造を表現する中心的なデータ構造です。しかし、単なる構文情報だけでなく、各ノードがどのような型を持つか（例: 変数の型、関数の戻り値の型、式の評価結果の型など）といったセマンティックな情報を持つことが、型チェック、最適化、コード生成といった後続のフェーズで不可欠となります。このコミットは、そのための「準備」と明記されており、ASTのノードに直接型情報を関連付けられるようにデータ構造を再設計する意図があります。
  2. ファイル構造の整理とクリーンアップ: 以前はglobals.goやobject.go、type.goといったファイルに分散していたObject（識別子や定数などの言語要素）やType（型定義）に関する定義が、ast.goに統合されています。これは、関連する定義をASTのコア部分に集約することで、コードの凝集度を高め、依存関係を単純化し、全体的な保守性を向上させることを目的としています。
  3. 整形出力の冪等性向上: prettyパッケージはコード整形機能も持っていたため、コメント内のタブ文字の扱いが問題となっていたようです。タブ文字の解釈や表示方法の違いによって、同じ入力コードから異なる整形結果が生成される「非冪等性」の問題があったと考えられます。このコミットでは、Untabify関数の導入などにより、この問題を解決し、より安定した整形出力を実現しようとしています。

これらの変更は、Go言語のコンパイラがより堅牢な型システムをサポートし、より正確なコード解析と整形を行えるようにするための、基盤固めの作業であったと言えます。

前提知識の解説

このコミットを理解するためには、以下の概念に関する知識が役立ちます。

  1. 抽象構文木 (Abstract Syntax Tree, AST):

    • コンパイラのフロントエンドがソースコードを解析（パース）して生成する、プログラムの構造を木構造で表現したものです。
    • ソースコードの各要素（変数宣言、関数呼び出し、演算子など）がノードとして表現され、それらの関係が親子関係で示されます。
    • ASTは、その後のセマンティック解析（意味解析）、型チェック、最適化、コード生成などのフェーズで利用されます。

  2. 型システム (Type System):

    • プログラミング言語において、値や変数が持つデータの種類（型）を定義し、それらの型の互換性や操作の正当性を規定する規則の集合です。
    • 型システムは、プログラムの安全性（例: 整数と文字列の不正な加算を防ぐ）や、コンパイラがメモリ割り当てや命令生成を行う際の情報を与えます。
    • 静的型付け言語（Goなど）では、コンパイル時に型チェックが行われます。

  3. セマンティック解析 (Semantic Analysis):

    • ASTが生成された後に行われるコンパイラのフェーズの一つです。
    • プログラムの意味的な正当性を検証します。例えば、変数が宣言されているか、型が正しく使われているか、関数呼び出しの引数の数が合っているかなどをチェックします。
    • このフェーズで、ASTノードに型情報などのセマンティックな属性が付与されることが一般的です。

  4. 識別子 (Identifier) と オブジェクト (Object):

    • 識別子: プログラム中で名前を付けるために使われる文字列（例: 変数名、関数名、型名）。
    • オブジェクト: 識別子が参照する実体。例えば、変数、定数、型、関数、パッケージなど、言語の構成要素となるエンティティを指します。コンパイラ内部では、これらのオブジェクトに関する情報（名前、型、スコープ、値など）が管理されます。

  5. スコープ (Scope):

    • プログラム中で識別子が有効な範囲を定義する規則です。
    • ローカルスコープ、グローバルスコープ、パッケージスコープなどがあり、識別子の可視性やライフタイムを決定します。
    • コンパイラは、スコープツリーを構築し、識別子の解決（どの識別子がどのオブジェクトを指すかを決定するプロセス）を行います。

  6. 冪等性 (Idempotence):

    • ある操作を複数回実行しても、1回実行した場合と同じ結果が得られる性質を指します。
    • コード整形ツールにおいては、同じソースコードを何度整形しても、常に同じ整形済みコードが出力されることが望ましいです。これにより、バージョン管理システムでの不要な差分発生を防ぎ、ツールの信頼性を高めます。

  7. Go言語の初期開発:

    • このコミットは2009年1月のものであり、Go言語がオープンソースとして公開される前の非常に初期の段階です。
    • 当時のGo言語の構文や内部構造は、現在の安定版とは異なる部分が多く、活発な実験と変更が行われていました。
    • usr/gri/prettyというパスは、Robert Griesemer氏（Go言語の共同設計者の一人）が担当していたprettyパッケージであることを示唆しています。

技術的詳細

このコミットの技術的詳細は、主にASTのデータ構造の再定義と、それに伴うパーサー、プリンター、型チェッカー、ユニバース（組み込みオブジェクトや型の集合）の変更に集約されます。

1. ast.goにおけるObjectとTypeの統合と再定義

  • Object構造体の導入:

    • 以前はobject.goにあったと思われるObject構造体と関連する定数（BADOBJ, CONST, TYPE, VAR, FUNCなど）がast.goに移動・定義されました。
    • Objectは、識別子（変数名、関数名など）が参照する実体（定数、型、変数、関数など）を表現します。
    • Object構造体は、id（ユニークID）、pos（ソースコード上の位置）、kind（オブジェクトの種類）、ident（識別子名）、typ（オブジェクトの型）、pnolev（パッケージ番号または関数ネストレベル）などのフィールドを持ちます。
    • NewObject関数が導入され、新しいObjectインスタンスを生成する際にユニークIDを割り振るようになりました。

  • Scope構造体の導入:

    • 以前はglobals.goにあったと思われるScope構造体と関連するメソッド（NewScope, LookupLocal, Lookup, Add, Insert, InsertImport）がast.goに移動・定義されました。
    • Scopeは、識別子とその識別子が参照するObjectのマッピングを管理し、スコープの階層構造（parentフィールド）を表現します。これにより、識別子の解決（どの識別子がどのオブジェクトを指すかを決定するプロセス）が可能になります。

  • Type構造体の拡張と定数の導入:

    • 以前はtype.goにあったと思われるType構造体と関連する定数（VOID, BADTYPE, BOOL, INT, ARRAY, STRUCT, FUNCTIONなど）がast.goに移動・定義されました。
    • Type構造体は、id（ユニークID）、ref（エクスポート用参照）、form（型の形式、例: 基本型、配列型、構造体型）、size（バイト単位のサイズ）、obj（プライマリ型オブジェクト）、scope（前方参照、構造体、インターフェース、関数用スコープ）、pos（ソースコード上の位置）、expr（型名、配列長）、mode（チャネルモード）、key（レシーバ型、マップキー）、elt（要素型）、list（構造体フィールド、インターフェースメソッド、関数パラメータ）などのフィールドを持ちます。
    • NewType関数が導入され、新しいTypeインスタンスを生成する際にユニークIDを割り振るようになりました。
    • Typeの形式を表す新しい定数群（UNDEF, VOID, BADTYPE, FORWARD, TUPLE, NIL, TYPENAME, BOOL, UINT, INT, FLOAT, STRING, INTEGER, ALIAS, ARRAY, STRUCT, INTERFACE, MAP, CHANNEL, FUNCTION, METHOD, POINTER, ELLIPSIS）が導入され、型の種類をより明確に区別できるようになりました。これは、以前はScannerのトークン（例: Scanner.IDENT、Scanner.LBRACK）で型の種類を表現していた箇所を置き換えるものです。

2. Makefileの変更

  • ast.6, parser.6, printer.6, typechecker.6, universe.6の依存関係から、globals.6, object.6, type.6が削除されました。これは、これらのファイルで定義されていた内容がast.goに統合されたことを反映しています。
  • universe.6の依存関係にast.6が追加されました。これは、universe.goがast.goで定義されたObjectやType、Scopeを使用するようになったためです。

3. parser.goの変更

  • globals, objectパッケージのインポートが削除され、代わりにastパッケージがインポートされました。
  • Parser構造体のtop_scopeフィールドの型がGlobals.ScopeからAST.Scopeに変更されました。
  • OpenScope関数内でGlobals.NewScopeの呼び出しがAST.NewScopeに変更されました。
  • Lookup関数（グローバルスコープ検索）が削除されました。これは、AST.ScopeにLookupメソッドが導入されたため、パーサーが直接AST.Scopeのメソッドを呼び出すようになったためです。
  • DeclareInScope関数において、obj.kindの比較がObject.NONEからAST.NONEに変更されました。また、scope.Lookupの呼び出しがscope.LookupLocalに変更され、ローカルスコープでの重複宣言チェックがより明確になりました。
  • ExprType関数やParseIdent関数、各種Parse*Type関数（ParseTypeName, ParseArrayType, ParseChannelTypeなど）において、AST.NewTypeの呼び出しで渡す引数がScannerのトークンから、ASTパッケージで定義された新しい型形式定数（AST.TYPENAME, AST.ARRAY, AST.CHANNELなど）に変更されました。これにより、型の種類をよりセマンティックに表現できるようになりました。
  • NewLit関数やParseFunctionLit関数、ParseImportSpec関数、ParseConstSpec関数、ParseVarSpec関数において、Globals.NewObjectの呼び出しがAST.NewObjectに変更され、Object.NONE, Object.PACKAGE, Object.CONST, Object.VARといった定数がAST.NONE, AST.PACKAGE, AST.CONST, AST.VARに変更されました。

4. printer.goの変更

  • globals, objectパッケージのインポートが削除されました。
  • Untabify関数が新しく追加されました。この関数は、文字列内の連続するタブ文字を単一のタブ文字に削減することで、コメント内のタブ文字の扱いを標準化し、整形出力の冪等性を向上させます。
  • Printf関数内でコメントテキストを出力する際に、HtmlEscapeに加えてUntabifyが適用されるようになりました。
  • HtmlIdentifier関数において、obj.kindの比較がObject.NONEからAST.NONEに変更されました。
  • Typeメソッドにおいて、t.tok（Scannerトークン）によるswitch文がt.form（AST型形式定数）によるswitch文に置き換えられました。これにより、型の種類に応じた出力ロジックが、よりセマンティックな型形式に基づいて行われるようになりました。

5. scanner.goの変更

  • コメントをスキップする際のgoto Lがgoto loopに変更されました。これは機能的な変更ではなく、ラベル名の変更によるものです。

6. test.shの変更

  • テストスクリプトにおいて、エラーを含む既知のファイル（method1.go, selftest1.goなど）をスキップするリストが更新されました。これは、進行中の開発や既知のバグによる一時的な措置と考えられます。

7. typechecker.goとuniverse.goの変更

  • 両ファイルからglobals, object, typeパッケージのインポートが削除されました。
  • universe.goでは、scope変数の型がGlobals.ScopeからAST.Scopeに変更されました。
  • DeclObj, DeclType, Register関数およびinit関数内で、Globals.NewObject, Globals.NewType, Globals.Universe_void_typといった呼び出しがAST.NewObject, AST.NewType, AST.Universe_void_typに変更されました。
  • Objectの種類やTypeの形式を表す定数も、Object.TYPE, Type.VOID, Type.BOOLなどからAST.TYPE, AST.VOID, AST.BOOLなどに変更されました。

これらの変更は、Go言語のコンパイラがASTを介して型情報をより効率的かつ一貫して管理できるようにするための、根本的なアーキテクチャの改善を示しています。特に、ObjectとTypeの定義をast.goに集約したことは、ASTが単なる構文木ではなく、セマンティックな情報（型やスコープ）を内包する中心的なデータ構造としての役割を強化するものです。

コアとなるコードの変更箇所

このコミットのコアとなる変更は、usr/gri/pretty/ast.goファイルに集中しています。

usr/gri/pretty/ast.go

  • Object構造体と関連定数・関数の追加:

    type (
	Object struct;
	Type struct;
	// ...
)

// Object represents a language object, such as a constant, variable, type, etc.
export const /* kind */ (
	BADOBJ = iota;  // error handling
	NONE;  // kind unknown
	CONST; TYPE; VAR; FIELD; FUNC; BUILTIN; PACKAGE; LABEL;
	END;  // end of scope (import/export only)
)

export func KindStr(kind int) string { ... }

export type Object struct {
	id int;  // unique id
	pos int;  // source position (< 0 if unknown position)
	kind int;  // object kind
	ident string;
	typ *Type;  // nil for packages
	pnolev int;  // >= 0: package no., <= 0: function nesting level, 0: global level
	// attached values
	block *array.Array; end int;  // stats for function literals; end of block pos
}

export var Universe_void_typ *Type
var ObjectId int;

export func NewObject(pos, kind int, ident string) *Object { ... }

  • Scope構造体と関連関数の追加:

    // ----------------------------------------------------------------------------
// Scopes

export type Scope struct {
	parent *Scope;
	entries map[string] *Object;
}

export func NewScope(parent *Scope) *Scope { ... }
func (scope *Scope) LookupLocal(ident string) *Object { ... }
func (scope *Scope) Lookup(ident string) *Object { ... }
func (scope *Scope) Add(obj* Object) { ... }
func (scope *Scope) Insert(obj *Object) { ... }
func (scope *Scope) InsertImport(obj *Object) *Object { ... }
func (scope *Scope) Print() { ... }

  • Expr構造体の変更:

    export type Expr struct {
	Node;
	x, y *Expr;  // binary (x, y) and unary (y) expressions
	obj *Object; // Globals.Object から AST.Object へ変更
	t *Type;  // type expressions, function literal types
}

  • NewLit関数の変更:

    export func NewLit(pos, tok int, obj *Object) *Expr { // Globals.Object から AST.Object へ変更
	e := new(Expr);
	e.pos, e.tok, e.obj = pos, tok, obj;
	return e;
}

  • Type構造体と関連定数・関数の追加/変更:

    // ----------------------------------------------------------------------------
// Types

export const /* form */ (
	// internal types
	UNDEF = iota;
	VOID;
	BADTYPE;
	FORWARD;
	TUPLE;
	NIL;
	TYPENAME;
	// basic types
	BOOL; UINT; INT; FLOAT; STRING; INTEGER;
	// composite types
	ALIAS; ARRAY; STRUCT; INTERFACE; MAP; CHANNEL; FUNCTION; METHOD; POINTER;
	// open-ended parameter type
	ELLIPSIS
)

export func FormStr(form int) string { ... }

export type Type struct {
	id int;  // unique id
	ref int;  // for exporting only: >= 0 means already exported
	form int;  // type form (新しく追加)
	size int;  // size in bytes
	obj *Object;  // primary type object or NULL
	scope *Scope;  // forwards, structs, interfaces, functions
	pos int;  // source position (< 0 if unknown position)
	expr *Expr;  // type name, array length
	mode int;  // channel mode
	key *Type;  // receiver type or map key
	elt *Type;  // array, map, channel or pointer element type, function result type
	list *array.Array; end int;  // struct fields, interface methods, function parameters
}

var TypeId int;

export func NewType(pos, form int) *Type { // 引数に form が追加
	typ := new(Type);
	typ.id = TypeId;
	TypeId++;
	typ.ref = -1;
	typ.pos = pos;
	typ.form = form; // form を設定
	return typ;
}

// NewType(pos, tok int) から NewType(pos, form int) に変更され、
// 以前の NewType(pos, tok int) は削除された。
// NewTypeExpr は Type.pos を使用するように変更された。

これらの変更により、ast.goはGo言語のASTにおけるオブジェクト、スコープ、型の定義を一元的に管理する中心的なファイルとなりました。

コアとなるコードの解説

ast.goにおける変更は、Go言語のコンパイラがソースコードを解析し、その意味を理解するための基盤を大きく強化するものです。

  1. ObjectとScopeの統合:

    • 以前は別々のファイルに存在していたObject（識別子が参照する実体）とScope（識別子の有効範囲）の定義がast.goに移動されました。これにより、ASTのノードが直接、それが参照するオブジェクトや、そのノードが属するスコープに関する情報を持つことができるようになりました。
    • Object構造体は、識別子の種類（定数、変数、関数など）や、その識別子が持つ型（typ *Type）を保持します。これは、ASTノードが単なる構文情報だけでなく、セマンティックな情報（意味的な情報）を持つための重要なステップです。
    • Scope構造体は、識別子からObjectへのマッピング（entries map[string] *Object）と、親スコープへの参照（parent *Scope）を持ちます。これにより、コンパイラはソースコード中の任意の場所で識別子が何を指すのかを正確に解決できるようになります。Lookupメソッドは、現在のスコープから親スコープへと遡って識別子を検索する機能を提供します。

  2. Type構造体の拡張と型形式の導入:

    • Type構造体は、Go言語のあらゆる型（基本型、配列、構造体、関数など）を表現するための中心的なデータ構造です。
    • 最も重要な変更は、form intフィールドの導入と、それに対応する新しい型形式定数（AST.TYPENAME, AST.ARRAY, AST.STRUCT, AST.FUNCTIONなど）の定義です。以前は、型の種類をScannerのトークン（例: Scanner.LBRACKが配列型を示す）で表現していましたが、これは構文解析器の内部的な表現であり、型のセマンティックな意味を直接的に示すものではありませんでした。
    • 新しいformフィールドと型形式定数により、Type構造体自体がその型の「種類」を明確に表現できるようになりました。これにより、型チェックやコード生成のフェーズで、型の種類に応じた処理をより直感的かつ堅牢に行うことができます。例えば、t.form == AST.ARRAYであれば、そのTypeが配列型であることが一目で分かり、配列の要素型（t.elt）や長さ（t.expr）にアクセスするといった処理が可能になります。
    • Type構造体には、obj *Objectフィールドも追加され、型が名前付きの型（例: type MyInt intのMyInt）である場合に、その型を定義するObjectへの参照を持つことができるようになりました。

  3. Expr構造体とNewLit関数の変更:

    • Expr構造体（式を表すASTノード）のobjフィールドの型が、Globals.ObjectからAST.Objectに変更されました。これにより、式が参照する識別子（例: 変数名、定数名）のObject情報を直接ASTノードに保持できるようになります。
    • NewLit関数（リテラルを表す式ノードを生成）も、AST.Objectを引数に取るように変更されました。これにより、数値リテラルや文字列リテラルなどが、対応するObject（例: 整数定数オブジェクト）を持つことができるようになります。

これらの変更は、Go言語のコンパイラがソースコードの構文だけでなく、その意味（セマンティクス）をより深く理解し、表現するための基盤を構築するものです。ASTが型情報やスコープ情報を直接保持することで、型チェックの精度向上、エラー検出能力の強化、そして最終的なコード生成の効率化に繋がります。

関連リンク

参考にした情報源リンク

  • Go言語のコミット履歴 (GitHub): https://github.com/golang/go/commits/master
  • コンパイラの設計に関する一般的な情報源（例: Dragon Book - Compilers: Principles, Techniques, and Tools）
  • プログラミング言語の型システムに関する一般的な情報源
  • 抽象構文木 (AST) に関する一般的な情報源
  • Go言語の初期開発に関するブログ記事やメーリングリストのアーカイブ（もし公開されていれば）