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

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

このコミットは、Go言語の初期段階における抽象構文木（AST）の重要なリファクタリングを記録しています。特に、コンマ区切りのリストの表現方法の変更と、様々な言語構造に対する明示的なASTノードの導入に焦点を当てています。これにより、ASTの可読性と操作性が向上し、後のコンパイラやツール開発の基盤が強化されました。

コミット

commit 3cfd91f85b1ef367238d0b67b5836f78bc7a1774
Author: Robert Griesemer <gri@golang.org>
Date:   Mon Mar 16 20:29:31 2009 -0700

    daily snapshot:
    - use explicit expression lists instead of binary trees to represent lists of the form a, b, c
    (per discussion w/ Russ)
    - use explicit nodes for various language constructs for better readability
    - various adjustments in parsing and printing
    
    next steps:
    - clean up AST fully so it can be checked in as library
    
    R=r
    OCL=26371
    CL=26371

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

https://github.com/golang/go/commit/3cfd91f85b1ef367238d0b67b5836f78bc7a1774

元コミット内容

このコミットの元のメッセージは以下の通りです。

  • コンマ区切りのリスト（例: a, b, c）を、二分木ではなく明示的な式リストで表現するように変更しました（Russとの議論に基づく）。
  • 可読性向上のため、様々な言語構造に明示的なノードを使用するようにしました。
  • パースと出力（pretty printing）において様々な調整を行いました。

次のステップとして、ASTを完全にクリーンアップし、ライブラリとしてチェックインできるようにすることが挙げられています。

変更の背景

Go言語のコンパイラやツールチェーンを開発する上で、プログラムの構造を表現する抽象構文木（AST）の設計は極めて重要です。初期のAST設計では、コンマ区切りの式リスト（例: a, b, c）がBinaryExprノードの二分木として表現されていました。これは一般的なパース手法の一つですが、ASTを走査したり、特定の要素にアクセスしたりする際に、ツリー構造を再帰的に辿る必要があり、コードが複雑になりがちでした。

このコミットの背景には、ASTのセマンティックな明確さと操作性の向上という目的があります。二分木表現から明示的なリスト表現への移行は、ASTの構造をより直感的にし、コンパイラや静的解析ツールがコードの意図をより容易に理解し、処理できるようにするためです。また、様々な言語構造（代入、インクリメント/デクリメント、for-range、type switch、selectのcaseなど）に対して専用のASTノードを導入することで、ASTが言語のセマンティクスをより忠実に反映するようになり、コードの生成や変換がより堅牢になります。

Robert GriesemerとRuss Coxの間での議論があったと明記されており、これはGo言語の設計初期段階における重要な設計判断の一つであったことが伺えます。ASTの設計は、言語の進化とツールの開発に長期的な影響を与えるため、このような基盤的なリファクタリングは非常に価値があります。

前提知識の解説

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

  1. 抽象構文木 (Abstract Syntax Tree, AST): コンパイラやインタプリタがソースコードを解析する際に生成する、プログラムの構造を抽象的に表現した木構造のデータ構造です。ソースコードの各要素（変数、式、文、関数など）がノードとして表現され、それらの関係がエッジで示されます。ASTは、コードのセマンティックな意味を捉えるために使用され、その後の最適化、コード生成、静的解析などのフェーズで利用されます。

  2. Go言語の構文とセマンティクス:

    • 式リスト: Go言語では、複数の値を返す関数呼び出しや、多重代入などでコンマ区切りの式リストが頻繁に登場します（例: x, y = f()）。
    • 代入文: x = yのような単純な代入だけでなく、x, y := 1, 2のような短い変数宣言と多重代入、x += 1のような複合代入演算子も存在します。
    • インクリメント/デクリメント文: i++やj--のような単項演算子によるインクリメント/デクリメントは、Goでは式ではなく文として扱われます。
    • for文: for文には、C言語スタイルのループ（for init; cond; post {}）、条件のみのループ（for cond {}）、無限ループ（for {}）、そしてfor rangeによるイテレーションがあります。
    • switch文: switch文には、式スイッチと型スイッチ（switch x.(type)）の2種類があります。
    • select文: ゴルーチン間の通信を多重化するための文で、case句にはチャネル送受信操作が含まれます。

  3. パーサー (Parser): 字句解析器（Lexer/Scanner）によって生成されたトークン列を入力として受け取り、言語の文法規則に従って構文木（この場合はAST）を構築するコンパイラのフェーズです。

  4. プリティプリンター (Pretty Printer): ASTなどの内部表現を受け取り、整形されたソースコードを出力するツールです。コードのフォーマットを統一したり、ASTのデバッグ表示を行ったりするのに使われます。

  5. tokenパッケージ: Go言語の字句解析器が使用するトークン（識別子、キーワード、演算子など）を定義するパッケージです。

  6. scannerパッケージ: Go言語の字句解析器を提供するパッケージで、ソースコードをトークンに分割し、各トークンの位置情報（行番号、列番号など）を提供します。

技術的詳細

このコミットの技術的詳細は、主にGo言語のAST (ast.go)、パーサー (parser.go)、およびプリティプリンター (printer.go) の変更に集約されます。

1. コンマ区切りリストの表現変更

  • ast.go:

    • 以前はExprLenとExprAtというヘルパー関数が存在し、BinaryExprの二分木として表現された式リストの長さを計算したり、特定のインデックスの要素を取得したりしていました。これらの関数は、新しい明示的なリスト表現の導入に伴い削除されました。
    • ConstDeclとVarDecl構造体内のValsフィールドがValues []Expr（式のスライス）に変更されました。これにより、定数や変数の複数値初期化がより直接的に表現されます。
    • CaseClause構造体内のExprフィールドがValues []Exprに変更され、switch文のcase句で複数の値を指定できるようになりました。
    • ReturnStat構造体が新設され、Results []Exprフィールドを持つことで、return文が返す複数の値を明示的に保持できるようになりました。

  • parser.go:

    • parseIdentList関数が、以前はast.Expr（二分木のルート）を返していたのに対し、[]*ast.Ident（識別子のスライス）を返すように変更されました。これにより、識別子のリストが直接的なスライスとしてパースされます。
    • parseExpressionList関数も同様に、ast.Exprを返していたのが[]ast.Expr（式のスライス）を返すように変更されました。これにより、コンマ区切りの式リストがスライスとしてパースされます。
    • これらの変更に伴い、parseParameterList、parseMethodSpec、parseConstSpec、parseVarSpecなど、リストをパースする他の関数も新しいparseIdentListやparseExpressionListのシグネチャに合わせて更新されました。

  • printer.go:

    • Exprsという新しいヘルパー関数が追加されました。これは[]ast.Exprを受け取り、コンマで区切って各式を整形出力します。
    • DoConstDecl、DoVarDecl、DoCaseClauseなどの関数が、新しいValues []ExprフィールドをExprs関数を使って出力するように変更されました。

2. 明示的なASTノードの導入

  • ast.go:

    • 以下の新しいStat（文）型が導入されました。
      • AssignmentStat: 単一の代入文（例: x = 1）。
      • TupleAssignStat: タプル代入文（例: x, y = 1, 2）。
      • IncDecStat: インクリメント/デクリメント文（例: i++）。
      • RangeClause: for ... range文のrange句。
      • TypeSwitchClause: 型スイッチ文のswitch x.(type)部分。
      • CommClause: select文のcase句（チャネル通信）。
      • ReturnStat: return文。
    • StatVisitorインターフェースと、各新しいStat型に対応するVisitメソッドが追加され、ASTの走査メカニズムが拡張されました。

  • parser.go:

    • parseSimpleStat関数が大幅にリファクタリングされました。
      • 代入演算子（=, :=, +=など）を検出した場合、左辺と右辺の式の数に応じてAssignmentStatまたはTupleAssignStatを生成するように変更されました。
      • rangeキーワードを検出した場合、RangeClauseを生成するように変更されました。
      • ++または--を検出した場合、IncDecStatを生成するように変更されました。
      • ラベル付き文（label:）のパースロジックも更新されました。
    • parseReturnStat関数が、新しいReturnStatノードを生成するように変更されました。
    • parseSwitchStat関数内で、型スイッチの検出ロジックが追加され、TypeSwitchClauseを生成するようになりました。
    • parseCommClause関数が、新しいCommClauseノードを生成するように変更されました。これにより、select文のcase句におけるチャネル送受信操作がより詳細に表現されます。

  • printer.go:

    • 新しいASTノード型に対応するDoAssignmentStat、DoTupleAssignStat、DoIncDecStat、DoRangeClause、DoTypeSwitchClause、DoCommClause、DoReturnStatなどのPrinterメソッドが追加されました。これらのメソッドは、それぞれのASTノードの構造に基づいて、対応するGoコードを整形出力します。
    • ControlClause関数（ifやforなどの制御構造の条件部分を処理）が、RangeClauseやTypeSwitchClauseを特別に処理するように更新されました。

これらの変更により、Go言語のASTはより表現豊かになり、言語のセマンティクスをより正確に捉えることができるようになりました。これは、コンパイラの正確性向上、エラー検出の改善、そして将来的な言語機能の追加に対する柔軟性の向上に寄与します。

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

このコミットにおけるコアとなるコードの変更は、主に以下の3つのファイルに集中しています。

  1. usr/gri/pretty/ast.go:

    • ExprLenとExprAt関数の削除。
    • AssignmentStat, TupleAssignStat, IncDecStat, RangeClause, TypeSwitchClause, CommClause, ReturnStatといった新しいStat（文）構造体の追加。
    • ConstDeclとVarDeclのValsフィールドがValues []Exprに変更。
    • CaseClauseのExprフィールドがValues []Exprに変更。
    • StatVisitorインターフェースと、新しいStat型に対応するVisitメソッドの追加。

  2. usr/gri/pretty/parser.go:

    • parseIdentListとparseExpressionListが、二分木ではなくスライスを返すように変更。
    • parseSimpleStat関数が、新しい代入、インクリメント/デクリメント、range句、ラベル付き文のパースロジックを統合。
    • parseReturnStatがReturnStatノードを生成するように変更。
    • parseCaseClauseがValues []Exprを扱うように変更。
    • parseCommClauseがCommClauseノードを生成するように変更。
    • parseConstSpecとparseVarSpecがValues []Exprを扱うように変更。

  3. usr/gri/pretty/printer.go:

    • Exprsヘルパー関数の追加。
    • DoAssignmentStat, DoTupleAssignStat, DoIncDecStat, DoRangeClause, DoTypeSwitchClause, DoCommClause, DoReturnStatといった新しいStat型に対応するPrinterメソッドの追加。
    • 既存のPrinterメソッド（DoConstDecl, DoVarDecl, DoCaseClauseなど）が、新しいスライスベースの表現を扱うように更新。

これらの変更は、Go言語のASTの根本的な構造と、それを構築・出力するロジックに影響を与えています。

コアとなるコードの解説

usr/gri/pretty/ast.go

// 削除されたコード
// func ExprLen(x Expr) int { ... }
// func ExprAt(x Expr, i int) Expr { ... }

// 新しく追加された文の型
type (
	AssignmentStat struct {
		Loc scanner.Location;  // location of Tok
		Tok int;  // assignment token
		Lhs, Rhs Expr;
	};

	TupleAssignStat struct {
		Loc scanner.Location;  // location of Tok
		Tok int;  // assignment token
		Lhs, Rhs []Expr;
	};

	IncDecStat struct {
		Loc scanner.Location;  // location of '++' or '--'
		Tok int;  // token.INC or token.DEC
		Expr Expr;
	};

	RangeClause struct {  // appears only as Init stat in a ForStat
		Loc scanner.Location;  // location of "=" or ":="
		Tok int;  // token.ASSIGN or token.DEFINE
		Lhs []Expr;
		Rhs Expr;
	};

	TypeSwitchClause struct {  // appears only as Init stat in a SwitchStat
		Loc scanner.Location;  // location of ":="
		Lhs *Ident;
		Rhs Expr;
	};

	CommClause struct {
		Loc scanner.Location;  // location of "case" or "default"
		Tok int;  // token.ASSIGN, token.DEFINE (valid only if Lhs != nil)
		Lhs, Rhs Expr;  // Rhs == nil means default case
		Body *Block;
	};

	ReturnStat struct {
		Loc scanner.Location;  // location of "return"
		Results []Expr;
	};
)

// 既存の構造体のフィールド変更
type (
	ConstDecl struct {
		// ...
		Values []Expr; // Vals Expr から変更
		// ...
	};

	VarDecl struct {
		// ...
		Values []Expr; // Vals Expr から変更
		// ...
	};

	CaseClause struct {
		// ...
		Values []Expr; // Expr Expr から変更
		// ...
	};
)

// StatVisitor インターフェースと Visit メソッドの更新
// 新しい文の型に対応するメソッドが追加されている

ast.goでは、コンマ区切りリストを二分木として扱うためのExprLenとExprAtが削除され、代わりにAssignmentStat、TupleAssignStat、IncDecStat、RangeClause、TypeSwitchClause、CommClause、ReturnStatといった、よりセマンティックな意味を持つ文の型が導入されました。これにより、ASTがGo言語の構文要素をより直接的に表現できるようになります。また、ConstDecl、VarDecl、CaseClauseのフィールドが単一の式から式のスライス（[]Expr）に変更され、複数値のリストをより自然に扱えるようになりました。

usr/gri/pretty/parser.go

// parseIdentList の変更 (ast.Expr を返す -> []*ast.Ident を返す)
func (P *Parser) parseIdentList(x ast.Expr) []*ast.Ident {
	// ...
	list := vector.New(0);
	if x == nil {
		x = P.parseIdent();
	}
	list.Push(x);
	for P.tok == token.COMMA {
		P.next();
		list.Push(P.parseIdent());
	}
	// vector を []*ast.Ident に変換して返す
	// ...
}

// parseExpressionList の変更 (ast.Expr を返す -> []ast.Expr を返す)
func (P *Parser) parseExpressionList() []ast.Expr {
	// ...
	list := vector.New(0);
	list.Push(P.parseExpression(1));
	for P.tok == token.COMMA {
		P.next();
		list.Push(P.parseExpression(1));
	}
	// vector を []ast.Expr に変換して返す
	// ...
}

// parseSimpleStat の変更 (代入、インクリメント/デクリメント、range 句の処理)
func (P *Parser) parseSimpleStat(mode int) ast.Stat {
	// ...
	x := P.parseExpressionList(); // 式リストをパース

	switch P.tok {
	case token.COLON: // ラベル付き文
		// ...
	case token.ASSIGN, token.DEFINE, /* その他の複合代入演算子 */ : // 代入文または range 句
		loc, tok := P.loc, P.tok;
		P.next();
		if mode & range_ok != 0 && P.tok == token.RANGE { // range 句
			// ... RangeClause を生成
			return &ast.RangeClause{loc, tok, x, y};
		} else { // 代入文
			y := P.parseExpressionList();
			xl, yl := len(x), len(y);
			if xl == 1 && yl == 1 { // 単純な代入
				return &ast.AssignmentStat{loc, tok, x[0], y[0]};
			} else { // タプル代入
				return &ast.TupleAssignStat{loc, tok, x, y};
			}
		}
	default:
		if len(x) != 1 { // 式が1つでない場合はエラー
			P.error(loc, "only one expression allowed");
		}
		if P.tok == token.INC || P.tok == token.DEC { // インクリメント/デクリメント
			return &ast.IncDecStat{P.loc, P.tok, x[0]};
		}
		// ... ExpressionStat を生成
	}
	// ...
}

// parseReturnStat の変更 (ReturnStat を生成)
func (P *Parser) parseReturnStat() *ast.ReturnStat {
	// ...
	P.expect(token.RETURN);
	var x []ast.Expr;
	if P.tok != token.SEMICOLON && P.tok != token.RBRACE {
		x = P.parseExpressionList(); // 戻り値を式リストとしてパース
	}
	return &ast.ReturnStat{loc, x};
}

// parseCommClause の変更 (CommClause を生成)
func (P *Parser) parseCommClause() *ast.CommClause {
	// ...
	if P.tok == token.CASE {
		P.next();
		// ... チャネル送受信操作のパースロジック ...
		return &ast.CommClause{loc, tok, lhs, rhs, P.parseBlock(token.COLON)};
	} else {
		P.expect(token.DEFAULT);
	}
	return &ast.CommClause{loc, tok, lhs, rhs, P.parseBlock(token.COLON)};
}

parser.goでは、parseIdentListとparseExpressionListが、コンマ区切りの要素を直接スライスとして収集するように変更されました。これにより、ASTの構築がより効率的かつ直感的になります。parseSimpleStatは、代入、インクリメント/デクリメント、for-rangeの初期化句といった多様な文を、新しく導入された専用のASTノードにマッピングするように大幅に改修されました。parseReturnStatとparseCommClauseも、それぞれの文に対応する新しいASTノードを生成するように更新されています。

usr/gri/pretty/printer.go

// Exprs ヘルパー関数の追加
func (P *Printer) Exprs(list []ast.Expr) {
	for i, x := range list {
		if i > 0 {
			P.Token(noloc, token.COMMA);
			P.separator = blank;
			P.state = inside_list;
		}
		P.Expr(x);
	}
}

// 新しい文の型に対応する Do*Stat メソッドの追加
func (P *Printer) DoAssignmentStat(s *ast.AssignmentStat) {
	P.Expr(s.Lhs);
	P.separator = blank;
	P.Token(s.Loc, s.Tok);
	P.separator = blank;
	P.Expr(s.Rhs);
}

func (P *Printer) DoTupleAssignStat(s *ast.TupleAssignStat) {
	P.Exprs(s.Lhs); // Lhs がスライスになった
	P.separator = blank;
	P.Token(s.Loc, s.Tok);
	P.separator = blank;
	P.Exprs(s.Rhs); // Rhs がスライスになった
}

func (P *Printer) DoIncDecStat(s *ast.IncDecStat) {
	P.Expr(s.Expr);
	P.Token(s.Loc, s.Tok);
}

func (P *Printer) DoRangeClause(s *ast.RangeClause) {
	P.Exprs(s.Lhs); // Lhs がスライスになった
	P.separator = blank;
	P.Token(s.Loc, s.Tok);
	P.separator = blank;
	P.Token(noloc, token.RANGE);
	P.separator = blank;
	P.Expr(s.Rhs);
}

func (P *Printer) DoTypeSwitchClause(s *ast.TypeSwitchClause) {
	P.Expr(s.Lhs);
	P.separator = blank;
	P.Token(s.Loc, token.DEFINE);
	P.separator = blank;
	P.Expr(s.Rhs);
	P.Token(s.Loc, token.PERIOD);
	P.Token(s.Loc, token.LPAREN);
	P.Token(s.Loc, token.TYPE);
	P.Token(s.Loc, token.RPAREN);
}

func (P *Printer) DoCommClause(s *ast.CommClause) {
	// ... CommClause の出力ロジック ...
}

func (P *Printer) DoReturnStat(s *ast.ReturnStat) {
	P.Token(s.Loc, token.RETURN);
	P.separator = blank;
	P.Exprs(s.Results); // Results がスライスになった
}

// 既存のメソッドの更新
func (P *Printer) DoCaseClause(s *ast.CaseClause) {
	if s.Values != nil { // Expr から Values に変更
		P.Token(s.Loc, token.CASE);
		P.separator = blank;
		P.Exprs(s.Values); // Exprs ヘルパー関数を使用
	} else {
		P.Token(s.Loc, token.DEFAULT);
	}
	// ...
}

func (P *Printer) DoConstDecl(d *ast.ConstDecl) {
	// ...
	if d.Values != nil { // Vals から Values に変更
		P.separator = tab;
		P.Token(noloc, token.ASSIGN);
		P.separator = blank;
		P.Exprs(d.Values); // Exprs ヘルパー関数を使用
	}
	// ...
}

func (P *Printer) DoVarDecl(d *ast.VarDecl) {
	// ...
	if d.Values != nil { // Vals から Values に変更
		P.separator = tab;
		P.Token(noloc, token.ASSIGN);
		P.separator = blank;
		P.Exprs(d.Values); // Exprs ヘルパー関数を使用
	}
	// ...
}

printer.goでは、新しく導入されたExprsヘルパー関数が、式のスライスをコンマ区切りで整形出力するために使用されます。また、ast.goで定義された新しい文の型に対応するDo*Statメソッドが多数追加され、それぞれのASTノードをGoコードとして正しく出力するロジックが実装されました。既存のDoCaseClause、DoConstDecl、DoVarDeclなども、フィールド名の変更とExprs関数の利用に合わせて更新されています。これらの変更により、ASTの構造変更がソースコードの整形出力に正確に反映されるようになります。

関連リンク

参考にした情報源リンク

  • Go言語のソースコードリポジトリ: https://github.com/golang/go
  • Go言語のコミット履歴: https://github.com/golang/go/commits/master
  • Go言語の初期の設計に関する議論（Go Mailing Listなど）: 2009年当時のメーリングリストのアーカイブを検索することで、Russ Coxとの議論の詳細が見つかる可能性があります。
  • コンパイラの設計に関する一般的な書籍やオンラインリソース（例: Dragon Book）
  • 抽象構文木に関する一般的な情報