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

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

このコミットは、Go言語のコンパイラ（cmd/gc）に、スライス操作の新しい構文 x[i:j:k] (3インデックススライス) のサポートを追加するものです。この機能は、スライスの長さだけでなく、その容量も明示的に制御できるようにすることを目的としています。Go 1.2の実験的機能として導入され、リリース版では利用できないように制限がかけられています。

コミット

  • コミットハッシュ: b4e92cee97b968f1799be27bed8cec62ae403725
  • Author: Russ Cox rsc@golang.org
  • Date: Mon Jul 1 20:32:36 2013 -0400

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

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

元コミット内容

cmd/gc: support x[i:j:k]

Design doc at golang.org/s/go12slice.
This is an experimental feature and may not be included in the release.

R=golang-dev, r
CC=golang-dev
https://golang.org/cl/10743046

変更の背景

Go言語のスライスは、配列の一部を参照するための強力なデータ構造です。既存の2インデックススライス s[low:high] は、low から high-1 までの要素を含む新しいスライスを作成し、その長さは high - low となります。しかし、このスライスの容量は、元のスライスの容量から low を引いたものに自動的に設定されるため、元の配列の残りの部分全体を参照できてしまいます。

例えば、arr := [10]int{...} という配列があり、s := arr[2:5] というスライスを作成した場合、s の長さは3ですが、容量は 10 - 2 = 8 となります。これにより、s = append(s, ...) のように要素を追加していくと、元の配列 arr の arr[5] 以降の要素にもアクセスできてしまいます。

特定のユースケースでは、スライスの容量を明示的に制限したい場合があります。例えば、ある関数にスライスを渡す際に、その関数が元の配列の特定の範囲外にアクセスすることを防ぎたい場合などです。これまでは、このような容量の制限を厳密に行うには、unsafe パッケージを使用するなどの回避策が必要でした。

このコミットは、Go 1.2のリリースに向けて検討されたスライス機能の拡張の一環として、3インデックススライス s[low:high:max] を導入することで、この課題を解決しようとしました。max インデックスを指定することで、新しいスライスの容量を max - low に制限し、より安全で意図通りのスライス操作を可能にすることが目的です。

前提知識の解説

Go言語のスライス

Go言語のスライスは、内部的に以下の3つの要素を持つ構造体として表現されます。

  1. ポインタ (Pointer): スライスが参照する基底配列の先頭要素へのポインタ。
  2. 長さ (Length): スライスに含まれる要素の数。len(s) で取得。
  3. 容量 (Capacity): スライスの基底配列の先頭から、スライスが拡張できる最大の要素数。cap(s) で取得。

スライス操作 s[low:high] は、s の基底配列の low から high-1 までの要素を参照する新しいスライスを作成します。

  • 新しいスライスの長さ: high - low
  • 新しいスライスの容量: cap(s) - low

Goコンパイラ (cmd/gc) の構造

Goコンパイラ cmd/gc は、Goソースコードを機械語に変換する主要なツールです。その処理は複数のフェーズに分かれており、このコミットで変更されている主なファイルは以下の役割を担っています。

  • go.y (Yacc/Bison 文法定義): Go言語の構文規則を定義するファイルです。パーサーがソースコードを解析し、抽象構文木 (AST) を構築する際に使用されます。新しい構文 x[i:j:k] を認識するために変更が必要です。
  • go.h (ヘッダーファイル): コンパイラ内部で使用されるデータ構造や定数、列挙型などが定義されています。新しいASTノードタイプ (OSLICE3, OSLICE3ARR) を追加するために変更が必要です。
  • typecheck.c (型チェッカー): ASTの各ノードの型をチェックし、型の一貫性や正当性を検証します。新しいスライス構文のインデックスが正しい型（整数）であるか、範囲が有効であるか（low <= high <= max、負の値でないかなど）を検証するロジックが追加されます。
  • walk.c (ASTウォーカー/変換): 型チェック後のASTを走査し、最適化や高レベルな操作を低レベルな操作に変換します。3インデックススライスを、実行時に長さと容量を計算し、必要に応じてパニックを発生させるチェックコードを挿入するような内部表現に変換します。
  • cgen.c, 5g/cgen.c, 6g/cgen.c, 8g/cgen.c (コードジェネレーター): 各アーキテクチャ（5gはARM、6gはx86-64、8gはx86）向けのコード生成を担当します。新しいスライス操作に対応するために、ASTノードの処理が追加されます。
  • esc.c (エスケープ解析): 変数がヒープに割り当てられるべきか、スタックに割り当てられるべきかを決定するエスケープ解析を行います。スライス操作がポインタのエスケープに影響を与える可能性があるため、関連する変更が行われます。
  • fmt.c (フォーマッター): ASTノードを文字列として表現するためのフォーマット関数が含まれます。デバッグ出力などで新しいスライスノードを正しく表示するために変更されます。
  • racewalk.c (データ競合検出): データ競合検出のためのコードを挿入する際にASTを走査します。新しいスライス操作が競合検出に影響を与える可能性があるため、関連する変更が行われます。

技術的詳細

このコミットの主要な技術的変更点は、Go言語のパーサー、型チェッカー、およびAST変換器に3インデックススライス x[i:j:k] のサポートを追加することです。

  1. 新しいASTノードの導入: src/cmd/gc/go.h に、新しいASTノードタイプ OSLICE3 と OSLICE3ARR が追加されました。

    • OSLICE3: v[1:2:3] のような一般的な3インデックススライスを表します。型チェック時に OSLICE3ARR に変換される可能性があります。
    • OSLICE3ARR: 配列に対する3インデックススライス a[1:2:3] を表します。

  2. 文法定義の変更 (src/cmd/gc/go.y): Go言語の文法を定義する go.y ファイルに、3インデックススライスの新しい規則が追加されました。

    --- a/src/cmd/gc/go.y
+++ b/src/cmd/gc/go.y
@@ -950,6 +952,21 @@ pexpr_no_paren:
 	{
 		$$ = nod(OSLICE, $1, nod(OKEY, $3, $5));
 	}
+|\tpexpr '[' oexpr ':' oexpr ':' oexpr ']'
+|\t{
+|\t\t// Make sure we don't accidentally release this experimental feature.
+|\t\t// http://golang.org/s/go12slice.
+|\t\tif(isrelease < 0)
+|\t\t\tisrelease = strstr(getgoversion(), "release") != nil;
+|\t\tif(isrelease)
+|\t\t\tyyerror("3-index slice not available in release");
+|\
+|\t\tif($5 == N)
+|\t\t\tyyerror("middle index required in 3-index slice");
+|\t\tif($7 == N)
+|\t\t\tyyerror("final index required in 3-index slice");
+|\t\t$$ = nod(OSLICE3, $1, nod(OKEY, $3, nod(OKEY, $5, $7)));
+|\t}
 |\tpseudocall
 |\tconvtype '(' expr ocomma ')'
 	{

    この変更により、パーサーは expr[low:high:max] 形式の構文を認識し、OSLICE3 ノードとしてASTを構築できるようになります。 注目すべきは、この機能が実験的であるため、isrelease フラグをチェックし、リリース版のコンパイラでこの構文が使用された場合にはエラー ("3-index slice not available in release") を発生させるガードが追加されている点です。また、high と max インデックスが省略できないという制約もここでチェックされます。

  3. 型チェックロジックの追加 (src/cmd/gc/typecheck.c): typecheck.c には、新しい OSLICE3 ノードに対する型チェックロジックが追加されました。

    • スライスされる対象 (n->left) が配列またはスライスであるかを確認します。文字列に対する3インデックススライスは許可されません。
    • low, high, max の各インデックスが整数型であるかを確認します。
    • 新しいヘルパー関数 checksliceindex と checksliceconst が導入され、インデックスが負でないこと、基底配列の境界を超えないこと、low <= high <= max の関係が保たれていることなどの実行時チェックが挿入されます。
    • 配列に対する3インデックススライスの場合、OSLICE3 ノードは OSLICE3ARR に変換されます。

  4. AST変換ロジックの追加 (src/cmd/gc/walk.c): walk.c の sliceany 関数が拡張され、OSLICE3 および OSLICE3ARR ノードの処理が追加されました。

    • low, high, max の各インデックスが評価され、必要に応じて一時変数に格納されます。
    • 実行時にパニックを発生させるための境界チェックコードが生成されます。具体的には、max が基底配列の容量を超えていないか、low <= high <= max の関係が保たれているかを確認する if 文と panicslice() の呼び出しが挿入されます。
    • 新しいスライスの長さ (high - low) と容量 (max - low) を計算するコードが生成されます。

  5. コード生成器の更新 (src/cmd/5g/cgen.c, src/cmd/6g/cgen.c, src/cmd/8g/cgen.c): 各アーキテクチャのコード生成器に、OSLICE3 および OSLICE3ARR ノードを処理するための case 文が追加されました。これにより、コンパイラはこれらの新しいASTノードを正しく機械語に変換できるようになります。

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

src/cmd/gc/go.h

新しいASTノードの定義:

enum
	OSLICE,	// v[1:2], typechecking may convert to a more specfic OSLICEXXX.
	OSLICEARR,	// a[1:2]
	OSLICESTR,	// s[1:2]
	OSLICE3,	// v[1:2:3], typechecking may convert to OSLICE3ARR.
	OSLICE3ARR,	// a[1:2:3]
	ORECOVER,	// recover
	ORECV,	// <-c
	ORUNESTR,	// string(i)

src/cmd/gc/go.y

3インデックススライスの文法規則と実験的機能のチェック:

pexpr_no_paren:
	pexpr '[' oexpr ':' oexpr ']'
	{
		$$ = nod(OSLICE, $1, nod(OKEY, $3, $5));
	}
|	pexpr '[' oexpr ':' oexpr ':' oexpr ']'
	{
		// Make sure we don't accidentally release this experimental feature.
		// http://golang.org/s/go12slice.
		if(isrelease < 0)
			isrelease = strstr(getgoversion(), "release") != nil;
		if(isrelease)
			yyerror("3-index slice not available in release");

		if($5 == N)
			yyerror("middle index required in 3-index slice");
		if($7 == N)
			yyerror("final index required in 3-index slice");
		$$ = nod(OSLICE3, $1, nod(OKEY, $3, nod(OKEY, $5, $7)));
	}
|	pseudocall
|	convtype '(' expr ocomma ')'
	{

src/cmd/gc/typecheck.c

typecheck1 関数内の OSLICE3 の処理と、新しいヘルパー関数 checksliceindex, checksliceconst:

// typecheck1 関数内 (抜粋)
	case OSLICE3:
		ok |= Erv;
		typecheck(&n->left, top);
		typecheck(&n->right->left, Erv);
		typecheck(&n->right->right->left, Erv);
		typecheck(&n->right->right->right, Erv);
		defaultlit(&n->left, T);
		indexlit(&n->right->left);
		indexlit(&n->right->right->left);
		indexlit(&n->right->right->right);
		l = n->left;
		if(isfixedarray(l->type)) {
			if(!islvalue(n->left)) {
				yyerror("invalid operation %N (slice of unaddressable value)", n);
				goto error;
			}
			n->left = nod(OADDR, n->left, N);
			n->left->implicit = 1;
			typecheck(&n->left, Erv);
			l = n->left;
		}
		if((t = l->type) == T)
			goto error;
		tp = nil;
		if(istype(t, TSTRING)) {
			yyerror("invalid operation %N (3-index slice of string)", n);
			goto error;
		}
		if(isptr[t->etype] && isfixedarray(t->type)) {
			tp = t->type;
			n->type = typ(TARRAY);
			n->type->type = tp->type;
			n->type->bound = -1;
			dowidth(n->type);
			n->op = OSLICE3ARR;
		} else if(isslice(t)) {
			n->type = t;
		} else {
			yyerror("cannot slice %N (type %T)", l, t);
			goto error;
		}
		if((lo = n->right->left) != N && checksliceindex(lo, tp) < 0)
			goto error;
		if((mid = n->right->right->left) != N && checksliceindex(mid, tp) < 0)
			goto error;
		if((hi = n->right->right->right) != N && checksliceindex(hi, tp) < 0)
			goto error;
		if(checksliceconst(lo, hi) < 0 || checksliceconst(lo, mid) < 0 || checksliceconst(mid, hi) < 0)
			goto error;
		goto ret;

// 新しいヘルパー関数
static int
checksliceindex(Node *r, Type *tp)
{
	Type *t;

	if((t = r->type) == T)
		return -1;
	if(!isint[t->etype]) {
		yyerror("invalid slice index %N (type %T)", r, t);
		return -1;
	}
	if(r->op == OLITERAL) {
		if(mpgetfix(r->val.u.xval) < 0) {
			yyerror("invalid slice index %N (index must be non-negative)", r);
			return -1;
		} else if(tp != nil && tp->bound > 0 && mpgetfix(r->val.u.xval) > tp->bound) {
			yyerror("invalid slice index %N (out of bounds for %d-element array)", r, tp->bound);
			return -1;
		} else if(mpcmpfixfix(r->val.u.xval, maxintval[TINT]) > 0) {
			yyerror("invalid slice index %N (index too large)", r);
			return -1;
		}
	}
	return 0;
}

static int
checksliceconst(Node *lo, Node *hi)
{
	if(lo != N && hi != N && lo->op == OLITERAL && hi->op == OLITERAL
	   && mpcmpfixfix(lo->val.u.xval, hi->val.u.xval) > 0) {
		yyerror("invalid slice index: %N > %N", lo, hi);
		return -1;
	}
	return 0;
}

src/cmd/gc/walk.c

sliceany 関数内の3インデックススライス処理の追加:

// Generate frontend part for OSLICE[3][ARR|STR]
//
static	Node*
sliceany(Node* n, NodeList **init)
{
	int bounded, slice3;
	Node *src, *lb, *hb, *cb, *bound, *chk, *chk0, *chk1, *chk2;
	int64 lbv, hbv, cbv, bv, w;
	Type *bt;

//	print("before sliceany: %+N\n", n);

	src = n->left;
	lb = n->right->left;
	slice3 = n->op == OSLICE3 || n->op == OSLICE3ARR;
	if(slice3) {
		hb = n->right->right->left;
		cb = n->right->right->right;
	} else {
		hb = n->right->right;
		cb = hb;
	}

	bounded = n->etype;

	// ... (既存の2インデックススライス処理の続き)

	if(isconst(cb, CTINT)) {
		cbv = mpgetfix(cb->val.u.xval);
		if(cbv < 0 || cbv > bv) {
			yyerror("slice index out of bounds");
			cbv = -1;
		}
	}
	// ... (hbの定数チェック)

	// generate
	//     if hb > bound || lb > hb { panicslice() }
	//     if cb > bound || hb > cb { panicslice() } (for 3-index slice)
	chk = N;
	chk0 = N; // for cb > bound
	chk1 = N; // for hb > bound or hb > cb
	chk2 = N; // for lb > hb

	bt = types[simtype[TUINT]];
	if(cb != N && cb->type->width > 4)
		bt = types[TUINT64];
	if(hb != N && hb->type->width > 4)
		bt = types[TUINT64];
	if(lb != N && lb->type->width > 4)
		bt = types[TUINT64];

	bound = cheapexpr(conv(bound, bt), init);

	if(cb != N) {
		cb = cheapexpr(conv(cb, bt), init);
		if(!bounded)
			chk0 = nod(OLT, bound, cb);
	} else if(slice3) {
		// When we figure out what this means, implement it.
		fatal("slice3 with cb == N"); // rejected by parser
	}
		
	if(hb != N) {
		hb = cheapexpr(conv(hb, bt), init);
		if(!bounded) {
			if(cb != N)
				chk1 = nod(OLT, cb, hb); // hb > cb
			else
				chk1 = nod(OLT, bound, hb); // hb > bound
		}
	} else if(slice3) {
		// When we figure out what this means, implement it.
		fatal("slice3 with hb == N"); // rejected by parser
	} else if(n->op == OSLICEARR) {
		hb = bound;
	} else {
		// ... (既存のhb == Nの処理)
	}

	if(lb != N) {
		lb = cheapexpr(conv(lb, bt), init);
		if(!bounded)
			chk2 = nod(OLT, hb, lb);
	}

	if(chk0 != N || chk1 != N || chk2 != N) {
		chk = nod(OIF, N, N);
		chk->nbody = list1(mkcall("panicslice", T, init));
		if(chk0 != N)
			chk->ntest = chk0;
		if(chk1 != N) {
			if(chk->ntest == N)
				chk->ntest = chk1;
			else
				chk->ntest = nod(OOROR, chk->ntest, chk1);
		}
		if(chk2 != N) {
			if(chk->ntest == N)
				chk->ntest = chk2;
			else
				chk->ntest = nod(OOROR, chk->ntest, chk2);
		}
		addstmt(init, chk);
	}

	// ... (長さと容量の計算)
	// cap = bound [ - lo ]
	n->right = N;
	n->list = nil;
	if(!slice3)
		cb = bound; // 2-index slice: cap is bound
	if(lb == N)
		bound = conv(cb, types[simtype[TUINT]]); // cap = cb
	else
		bound = nod(OSUB, conv(cb, types[simtype[TUINT]]), conv(lb, types[simtype[TUINT]])); // cap = cb - lo
	typecheck(&bound, Erv);
	walkexpr(&bound, init);
	n->list = list(n->list, bound);
	// ... (長さの計算)
}

コアとなるコードの解説

src/cmd/gc/go.h

OSLICE3 と OSLICE3ARR は、Goコンパイラが3インデックススライスを内部的に表現するための新しいノードタイプです。これにより、パーサーは新しい構文を認識し、型チェッカーやコードジェネレーターがそれらを適切に処理できるようになります。

src/cmd/gc/go.y

この変更は、Go言語の文法に [low:high:max] 形式のスライス構文を追加します。

  • $1 はスライスされる元の式（配列、スライスなど）。
  • $3 は low インデックス。
  • $5 は high インデックス。
  • $7 は max インデックス。 これらのインデックスは OKEY ノードとしてネストされ、OSLICE3 ノードの right フィールドに格納されます。

isrelease フラグによるチェックは、この機能がGo 1.2のリリース版には含まれない実験的なものであることを示しています。これは、新機能の導入前にコミュニティからのフィードバックを収集し、安定性や設計の最終決定を行うための一般的なアプローチです。 また、high ($5) と max ($7) が省略できないという制約は、3インデックススライスの意味論を明確に保つために重要です。

src/cmd/gc/typecheck.c

typecheck1 関数内の OSLICE3 の処理は、3インデックススライスに対する厳密な型チェックとセマンティックチェックを行います。

  • アドレス可能性のチェック: 配列を3インデックススライスする場合、その配列がアドレス可能である（つまり、lvalueである）必要があります。これは、スライスが基底配列へのポインタを含むため、そのポインタが有効なメモリ位置を指す必要があるためです。
  • 文字列の禁止: 文字列は不変であり、バイトのシーケンスとして扱われるため、3インデックススライス（特に容量の概念）は適用できません。そのため、文字列に対する3インデックススライスはエラーとなります。
  • 配列から OSLICE3ARR への変換: ポインタ型（isptr）で固定長配列（isfixedarray）を指す場合、OSLICE3 は OSLICE3ARR に変換されます。これは、配列とスライスで内部的な表現や処理が異なるため、コンパイラが適切なコードを生成できるようにするためです。
  • インデックスの検証: checksliceindex と checksliceconst ヘルパー関数が呼び出され、low, high, max の各インデックスが以下の条件を満たすことを確認します。
    • 整数型であること: スライスインデックスは整数でなければなりません。
    • 非負であること: インデックスは0以上でなければなりません。
    • 境界内であること: インデックスが基底配列の境界を超えていないこと。
    • 順序の検証: low <= high <= max の関係が保たれていること。この順序が崩れている場合（例: low > high や high > max）、エラーとなります。

src/cmd/gc/walk.c

sliceany 関数は、スライス操作のASTノードを、実行時に必要なチェックと計算を行う低レベルなASTノードに変換します。

  • slice3 フラグ: n->op が OSLICE3 または OSLICE3ARR であるかを確認し、slice3 フラグを設定します。これにより、2インデックススライスと3インデックススライスの処理を分岐させます。
  • インデックスの取得: lb (low), hb (high), cb (max/cap) の各インデックスノードを取得します。3インデックススライスの場合、hb は n->right->right->left、cb は n->right->right->right から取得されます。
  • 定数インデックスのチェック: isconst を使用して、インデックスが定数である場合にその値を評価し、コンパイル時に境界チェックを行います。これにより、実行時パニックを減らすことができます。
  • 実行時境界チェックの生成: chk0, chk1, chk2 というノードを使用して、以下の条件をチェックする if 文を生成します。
    • chk0: max が基底配列の容量を超えていないか (bound < cb)。
    • chk1: high が max を超えていないか (cb < hb)。2インデックススライスの場合、high が基底配列の容量を超えていないか (bound < hb)。
    • chk2: low が high を超えていないか (hb < lb)。 これらのチェックのいずれかが真の場合、panicslice() 関数が呼び出され、実行時パニックが発生します。OOROR (論理OR) を使用して、複数のチェック条件を結合します。
  • 長さと容量の計算:
    • 新しいスライスの容量は max - low (cb - lb) として計算されます。
    • 新しいスライスの長さは high - low (hb - lb) として計算されます。 これらの計算結果は、新しいスライスの内部表現に設定されます。

これらの変更により、Goコンパイラは x[i:j:k] 構文を正しく解析し、型チェックを行い、実行時に安全なコードを生成できるようになります。

関連リンク

参考にした情報源リンク