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

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

このコミットは、Go言語の型チェッカー（go/typesパッケージ）におけるシフト演算子の型チェックの挙動を根本的に見直すものです。特に、型なし定数（untyped constant）がシフト演算子の左オペランド（LHS）として使用される場合の型推論とチェックのロジックを改善し、既存の標準ライブラリパッケージで発生していた型チェックエラーを解消することを目的としています。

コミット

commit 3a9fcc45f6938e2198d748a78f7c8b9c26692fad
Author: Robert Griesemer <gri@golang.org>
Date:   Thu Feb 28 15:27:52 2013 -0800

    go/types: fix type-checking of shift expressions
    
    Completely rethought shift expression type checking.
    Instead of attempting to type-check them eagerly, now
    delay the checking of untyped constant lhs in non-
    constant shifts until the final expression type
    becomes clear. Once it is clear, update the respective
    expression tree with the final (not untyped) type and
    check respective shift lhs' where necessary.
    
    This also cleans up another conundrum: How to report
    the type of untyped constants as it changes from
    untyped to typed. Now, Context.Expr is only called
    for an expresion x once x has received its final
    (not untyped) type (for constant initializers, the
    final type may still be untyped).
    
    With this CL all remaining std lib packages that
    did not typecheck due to shift errors pass now.
    
    TODO: There's a lot of residual stuff that needs
    to be cleaned up but with this CL all tests pass
    now.
    
    R=adonovan, axwalk
    CC=golang-dev
    https://golang.org/cl/7381052

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

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

元コミット内容

go/types: fix type-checking of shift expressions

Completely rethought shift expression type checking.
Instead of attempting to type-check them eagerly, now
delay the checking of untyped constant lhs in non-
constant shifts until the final expression type
becomes clear. Once it is clear, update the respective
expression tree with the final (not untyped) type and
check respective shift lhs' where necessary.

This also cleans up another conundrum: How to report
the type of untyped constants as it changes from
untyped to typed. Now, Context.Expr is only called
for an expresion x once x has received its final
(not untyped) type (for constant initializers, the
final type may still be untyped).

With this CL all remaining std lib packages that
did not typecheck due to shift errors pass now.

TODO: There's a lot of residual stuff that needs
to be cleaned up but with this CL all tests pass
now.

R=adonovan, axwalk
CC=golang-dev
https://golang.org/cl/7381052

変更の背景

Go言語の型システムでは、数値リテラルなどの「型なし定数（untyped constant）」が存在し、これらは文脈に応じて適切な型に推論されます。しかし、従来の型チェッカーでは、シフト演算子（<<, >>）の左オペランド（LHS）が型なし定数である場合に、その型チェックが「 eagerly（即座に）」行われていました。

この即座な型チェックのアプローチは、特に非定数シフト（右オペランドが定数ではないシフト）の場合に問題を引き起こしていました。Goの仕様では、シフト演算のLHSが型なし定数である場合、その型はシフト式全体の文脈によって決定されるべきです。しかし、即座に型チェックを行うと、文脈がまだ不明確な段階でLHSの型を決定しようとし、誤った型推論や不必要なエラーが発生する可能性がありました。

具体的には、標準ライブラリのいくつかのパッケージ（例: compress/lzw, debug/dwarf, encoding/asn1, math/big, net, runtime, strconv, syscall, text/scanner）で、このシフト演算子の型チェックの不備が原因で型チェックエラーが発生していました。これらのエラーは、コンパイラがGoの言語仕様に厳密に従って型推論を行えていないことを示しており、修正が必要でした。

また、Context.Expr コールバックの挙動も課題でした。このコールバックは、式が型チェックされた際にその型をクライアントに通知するために使用されますが、型なし定数が型なしから型付きに変化する過程で、いつ、どのような型で通知すべきかという「難問」がありました。このコミットは、この通知タイミングも整理し、より一貫性のある挙動を実現しています。

前提知識の解説

このコミットの理解には、以下のGo言語の概念と型チェックのメカニズムに関する知識が役立ちます。

  1. Go言語の型システム:

    • Goは静的型付け言語であり、変数は使用前に型が宣言されるか、型推論によって決定されます。
    • Goの型システムは比較的シンプルで、型変換（キャスト）は明示的に行う必要があります。
    • 型なし定数 (Untyped Constants): Goには、数値リテラル（例: 1, 3.14, 1i）や真偽値リテラル（true, false）、文字列リテラル（"hello"）など、特定の型を持たない「型なし定数」が存在します。これらは、使用される文脈（例: 変数への代入、演算、関数の引数）によって適切なデフォルト型（例: int, float64, complex128, bool, string）に推論されるか、明示的な型変換によって型が決定されます。これにより、柔軟な数値演算が可能になります。

  2. シフト演算子 (Shift Expressions):

    • Goにはビットシフト演算子 << (左シフト) と >> (右シフト) があります。
    • オペランドの型:
      • 左オペランド（LHS）は整数型である必要があります。
      • 右オペランド（RHS）は符号なし整数型である必要があります。
    • 型なし定数LHSの特殊な挙動: Goの仕様では、シフト演算のLHSが型なし定数である場合、その型はシフト式全体の文脈によって決定されます。例えば、1 << s の 1 は、s が非定数である場合、最終的にシフト結果が代入される変数の型や、式が使用される文脈によって型が決定されます。これが、即座な型チェックでは対応しきれない複雑さの原因でした。

  3. 型チェック (Type Checking):

    • コンパイラの重要なフェーズの一つで、プログラムが言語の型規則に準拠しているかを検証します。
    • Goコンパイラでは、go/types パッケージがこの型チェックの主要な役割を担っています。このパッケージは、抽象構文木（AST）を走査し、各式の型を決定し、型の一貫性を検証します。
    • checker 構造体: go/types パッケージの中心的な構造体で、型チェックの状態（スコープ、定義済みオブジェクト、エラーなど）を管理します。
    • operand 構造体: 型チェック中に式の値や型を一時的に保持するために使用される構造体です。mode フィールドは、式が定数、変数、型式など、どのような種類の値であるかを示します。

  4. 抽象構文木 (Abstract Syntax Tree - AST):

    • ソースコードを解析して得られる、プログラムの構造を木構造で表現したものです。型チェッカーはASTを走査して型情報を付与したり、エラーを検出したりします。

技術的詳細

このコミットの核心は、シフト演算子の型チェックにおける「遅延評価」の導入と、それに伴う型チェッカー内部の状態管理の改善です。

1. 遅延型チェックの導入

  • 問題点: 従来の型チェッカーは、シフト演算の左オペランド（LHS）が型なし定数である場合、その型を即座に決定しようとしていました。しかし、Goの仕様では、非定数シフトの場合、LHSの型はシフト式全体の文脈（最終的に代入される変数の型など）によって決定されるべきです。
  • 解決策: このコミットでは、LHSが型なし定数である非定数シフト式の場合、LHSの型チェックを「遅延」させます。LHSの型は、式全体の型が最終的に確定するまで決定されません。型が確定した時点で、LHSの型もその文脈に合わせて更新され、必要なチェックが行われます。

2. checker 構造体の拡張と状態管理

型チェックの遅延と、型なし定数の型変化を適切に管理するために、src/pkg/go/types/check.go の checker 構造体に以下の新しいマップが追加されました。

  • untyped map[ast.Expr]*Basic: 型なしの式（ast.Expr）とその現在の基本型（*Basic）をマッピングします。これは、型なしの式が最終的に型付けされるまで、その状態を追跡するために使用されます。
  • constants map[ast.Expr]interface{}: 型なし定数式（ast.Expr）とその値（interface{}）をマッピングします。untyped マップのキーとしても存在します。
  • shiftOps map[ast.Expr]bool: 型チェックが遅延されたシフト演算のLHS式（ast.Expr）を保持するセット（マップの値をboolとして使用）。これにより、後でこれらの式に対して特別な処理を行う必要が生じた際に、効率的に識別できます。

これらのマップは、check 関数の開始時に初期化され、型チェックの過程で更新されます。check 関数の終了時には、untyped マップに残っているすべての式に対して、Context.Expr コールバックを通じてクライアントに通知が行われます。

3. updateExprType 関数の導入

src/pkg/go/types/expr.go に新しく updateExprType 関数が追加されました。この関数は、式ツリーを再帰的に走査し、型なしのノードの型を最終的な型に更新する役割を担います。

  • 機能:
    • 引数 x ast.Expr で指定された式のASTノードと、その最終的な型 typ Type を受け取ります。
    • x が untyped マップに存在し、かつ typ が型なしではない場合、x の型が確定したと判断し、untyped および constants マップから x を削除します。
    • Context.Expr コールバックが設定されている場合、x の最終的な型をクライアントに通知します。
    • 特に、shiftOp フラグが true で、かつ x が shiftOps マップに存在する場合（つまり、型チェックが遅延されていたシフト演算のLHSである場合）、typ が整数型であるかをチェックします。整数型でない場合はエラーを報告し、shiftOps マップから x を削除します。
    • ast.ParenExpr (括弧式)、ast.UnaryExpr (単項演算式)、ast.BinaryExpr (二項演算式) の場合、再帰的にその子ノードに対しても updateExprType を呼び出し、式ツリー全体に型情報を伝播させます。

4. shift 関数の再設計

src/pkg/go/types/expr.go の shift 関数は、シフト演算子の型チェックロジックの大部分を担っており、このコミットで大幅に再設計されました。

  • 定数シフトの処理:
    • 右オペランド（RHS）が定数である場合、LHSが型なし定数であれば、それが整数として表現可能かをチェックし、UntypedInt 型に設定します。
    • RHSの値が妥当な範囲内にあることを確認し、LHSが定数であれば実際にシフト演算を実行し、結果をLHSの val に格納します。
  • 非定数シフトと型なしLHSの遅延処理:
    • RHSが非定数であり、LHSが型なし定数である場合、LHSの型チェックを遅延させます。具体的には、LHSの式を check.shiftOps マップに追加し、x.mode を value に設定して、後で updateExprType が処理できるようにします。
    • これにより、LHSの型が文脈によって決定されるまで、具体的な型チェックを待つことができます。
  • 一般的な非定数シフトの処理:
    • LHSが整数型であることを確認します。整数型でない場合はエラーを報告します。

5. Context.Expr コールバックの挙動変更

src/pkg/go/types/api.go の Context.Expr のドキュメントが更新され、その挙動が明確化されました。

  • 変更前: 各式が型チェックされた際に呼び出される可能性がありました。
  • 変更後: 式 x が最終的な（型なしではない）型を受け取った場合にのみ、正確に一度だけ呼び出されるようになりました。これにより、型なし定数が型なしから型付きに変化する過程での通知タイミングが整理され、クライアントは確定した型情報のみを受け取ることができます。

6. assignment 関数の導入と割り当てロジックの一元化

src/pkg/go/types/stmt.go に assignment という新しいヘルパー関数が導入されました。

  • 機能:
    • オペランド x が特定の型 to に割り当て可能であるかをチェックします。
    • 必要に応じて、型なしの値を適切な型に変換しようと試みます（convertUntyped を呼び出す）。
    • 割り当てが成功したか、またはエラーが報告されたかを示すブール値を返します。
  • 影響: これまで assignOperand という関数で行われていた割り当てロジックが assignment に集約され、assign1to1 やその他の割り当て関連の場所でこの新しい関数が使用されるようになりました。これにより、割り当ての型チェックロジックが一貫性を持つようになりました。

これらの変更により、Goの型チェッカーはシフト演算子の型推論において、よりGoの言語仕様に忠実で、堅牢な挙動を示すようになりました。特に、型なし定数のLHSを持つ非定数シフトのケースが正確に処理されるようになり、標準ライブラリの既存の型チェックエラーが解消されました。

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

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

  • src/pkg/go/types/check.go:
    • checker 構造体に untyped, constants, shiftOps の3つのマップが追加されました。
    • check 関数内でこれらのマップが初期化され、型チェックの最後に残った型なし式を処理するロジックが追加されました。
  • src/pkg/go/types/expr.go:
    • updateExprType 関数が新規に実装されました。これは、式ツリー内の型なしノードの型を更新し、遅延されたシフトオペランドのチェックを行う中心的な役割を担います。
    • shift 関数が大幅に書き換えられ、シフト演算の型チェックロジックが根本的に見直されました。特に、型なし定数LHSを持つ非定数シフトの遅延処理が導入されました。
    • convertUntyped 関数が updateExprType を呼び出すように変更されました。
    • binary, callExpr, rawExpr 関数内で、型チェックのロジックや Context.Expr の呼び出しタイミングが調整されました。
  • src/pkg/go/types/stmt.go:
    • assignment 関数が新規に実装されました。これは、値の割り当て可能性をチェックし、型なし値の変換を行うための汎用的なヘルパー関数です。
    • assignOperand 関数が削除され、そのロジックが assignment に統合されました。
    • assign1to1 およびその他のステートメント処理関数（send、inc/dec、assign）が、新しい assignment 関数と調整された binary 関数を使用するように変更されました。
  • src/pkg/exp/gotype/gotype_test.go:
    • テストスイートで、これまでコメントアウトされていた標準ライブラリのパッケージ（compress/lzw, debug/dwarf, encoding/asn1, math/big, net, runtime, strconv, syscall, text/scanner）の型チェックテストが有効化されました。これは、このコミットによってこれらのパッケージのシフト演算子関連の型チェックエラーが解消されたことを示しています。
  • src/pkg/go/types/api.go:
    • Context.Expr フィールドのコメントが更新され、その呼び出しタイミング（式が最終的な型を受け取ったときのみ）が明確化されました。
  • src/pkg/go/types/testdata/expr3.src:
    • シフト演算子に関する多数の新しいテストケースが追加されました。これには、Goの仕様からの例や、標準ライブラリで問題となっていたパターンが含まれており、新しい型チェックロジックの正確性を検証します。

コアとなるコードの解説

src/pkg/go/types/check.go における状態管理の強化

type checker struct {
	// ... 既存のフィールド ...

	// untyped expressions
	untyped   map[ast.Expr]*Basic      // map of expressions of untyped type
	constants map[ast.Expr]interface{} // map of untyped constant expressions; each key also appears in untyped
	shiftOps  map[ast.Expr]bool        // map of lhs shift operands with delayed type-checking

	// ... 既存のフィールド ...
}

func check(ctxt *Context, fset *token.FileSet, files []*ast.File) (pkg *Package, err error) {
	check := &checker{
		// ... 既存の初期化 ...
		untyped:     make(map[ast.Expr]*Basic),
		constants:   make(map[ast.Expr]interface{}),
		shiftOps:    make(map[ast.Expr]bool),
	}

	// ... 型チェックの主要ロジック ...

	// remaining untyped expressions must indeed be untyped
	// ... デバッグ用チェック ...

	// notify client of any untyped types left
	if ctxt.Expr != nil {
		for x, typ := range check.untyped {
			ctxt.Expr(x, typ, check.constants[x])
		}
	}

	return
}

checker 構造体に導入された3つのマップは、型なし定数や遅延型チェックの必要なシフト演算子のLHSの状態を追跡するために不可欠です。

  • untyped は、まだ型が確定していない式を管理し、その現在の型なしの基本型を保持します。
  • constants は、型なし定数式の具体的な値を保持します。
  • shiftOps は、非定数シフトのLHSで、型が確定するまでチェックを遅延させる必要がある式をマークします。

check 関数の最後で untyped マップを走査し、残っている型なし式について Context.Expr を呼び出すことで、型チェックの最終段階でクライアントにすべての型情報を確実に通知します。

src/pkg/go/types/expr.go における型伝播とシフト演算の再構築

updateExprType 関数

func (check *checker) updateExprType(x ast.Expr, typ Type, shiftOp bool) {
	// ... switch文でxのASTノードの種類に応じて再帰的に子ノードを処理 ...

	if t := check.untyped[x]; t != nil {
		if isUntyped(typ) {
			// typがまだ型なしの場合、untypedマップを更新
			check.untyped[x] = typ.(*Basic)
		} else {
			// typが型付きになった場合、untypedとconstantsマップから削除し、クライアントに通知
			if f := check.ctxt.Expr; f != nil {
				f(x, typ, check.constants[x])
			}
			delete(check.untyped, x)
			delete(check.constants, x)

			// 遅延されたシフトオペランドのチェック
			if shiftOp && check.shiftOps[x] {
				if !isInteger(typ) {
					check.invalidOp(x.Pos(), "shifted operand %s (type %s) must be integer", x, typ)
				}
				delete(check.shiftOps, x)
			}
		}
	}
}

updateExprType は、型なしの式が最終的な型を受け取ったときに、その型を式ツリー全体に伝播させるための重要な関数です。特に、shiftOp フラグと check.shiftOps マップを連携させることで、遅延されていたシフト演算のLHSが整数型であるかどうかのチェックを、型が確定したタイミングで正確に行うことができます。これにより、Goのシフト演算の仕様（LHSは整数型である必要がある）が厳密に適用されます。

shift 関数

func (check *checker) shift(x, y *operand, op token.Token) {
	// ... RHSが符号なし整数型であることのチェック ...

	if x.mode == constant {
		if y.mode == constant {
			// 定数シフト: LHSが整数として表現可能かチェックし、実際にシフト演算を実行
			if isUntyped(x.typ) {
				if !isRepresentableConst(x.val, check.ctxt, UntypedInt) {
					check.invalidOp(x.pos(), "shifted operand %s must be integer", x)
					x.mode = invalid
					return
				}
				x.typ = Typ[UntypedInt]
			}
			// ... シフト値の妥当性チェック ...
			x.val = shiftConst(x.val, uint(s), op)
			return
		}

		// 非定数シフトでLHSが定数
		if isUntyped(x.typ) {
			// 型なしLHSの型チェックを遅延
			check.shiftOps[x.expr] = true
			x.mode = value // 値モードに設定し、後でupdateExprTypeで処理されるようにする
			return
		}
	}

	// 非定数シフト: LHSが整数型であることのチェック
	if !isInteger(x.typ) {
		check.invalidOp(x.pos(), "shifted operand %s must be integer", x)
		x.mode = invalid
		return
	}

	x.mode = value
}

shift 関数は、シフト演算子の型チェックロジックの核心です。この関数は、右オペランドが定数か非定数か、左オペランドが型なし定数かによって、異なるパスで処理を行います。

  • 定数シフトの場合、LHSが整数として表現可能であれば、即座にシフト演算を実行し、結果を定数として扱います。
  • 非定数シフトでLHSが型なし定数の場合、LHSの型チェックを check.shiftOps マップに登録することで遅延させます。これにより、LHSの型が文脈によって決定されるまで待つことができ、不正確な型推論を防ぎます。
  • 一般的な非定数シフトの場合、LHSが既に型付きであれば、それが整数型であることを確認します。

この遅延評価のメカニズムが、標準ライブラリで発生していたシフト演算子関連の型チェックエラーを解決する鍵となります。

src/pkg/go/types/stmt.go における割り当てロジックの統一

assignment 関数

func (check *checker) assignment(x *operand, to Type) bool {
	// ... 複数値の式が単一値として使用された場合のエラーチェック ...

	check.convertUntyped(x, to) // 型なし値をターゲット型に変換を試みる

	// 変換後、xがinvalidでなく、かつto型に割り当て可能であればtrue
	return x.mode != invalid && x.isAssignable(check.ctxt, to)
}

assignment 関数は、Goの割り当て規則をカプセル化し、型なし値の変換と割り当て可能性のチェックを一元的に行います。これにより、型チェッカー全体で割り当てのロジックが統一され、コードの保守性が向上します。特に、convertUntyped を呼び出すことで、型なし定数が割り当ての文脈で適切な型に推論されることを保証します。

これらの変更は、Goの型チェッカーが言語仕様にさらに厳密に準拠し、より正確で堅牢な型推論とエラー報告を行うための重要なステップです。

関連リンク

参考にした情報源リンク

  • Goの公式リポジトリのコミット履歴: https://github.com/golang/go
  • Gerrit Code Review (CL 7381052): https://golang.org/cl/7381052 (コミットメッセージに記載されているリンク)
  • Go言語の型なし定数に関する一般的な情報源（Web検索結果に基づく）
  • Go言語のシフト演算子に関する一般的な情報源（Web検索結果に基づく）