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

このコミットは、Go言語の標準ライブラリにvectorパッケージを導入し、既存のarrayパッケージを非推奨にする変更を含んでいます。vectorパッケージは、動的な配列（ベクター）の機能を提供し、ジェネリックなElementインターフェースと、特定の型（この場合はint）に特化したIntVectorを提供します。

コミット

commit 127526649f68b8fc8ea1ab041d6a01c0fd23b7e0
Author: Robert Griesemer <gri@golang.org>
Date:   Fri Feb 13 15:07:56 2009 -0800

    - vector package (identical to array except for names)
    - updated some file (but not all - left array package in place for now)
    
    R=rsc
    DELTA=530  (483 added, 0 deleted, 47 changed)
    OCL=25025
    CL=25025

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

https://github.com/golang/go/commit/127526649f68b8fc8ea1ab041d6a01c0fd23b7e0

元コミット内容

このコミットの元の内容は以下の通りです。

vectorパッケージの導入（名前を除いてarrayパッケージと同一）。
一部のファイルが更新された（ただし、全てではなく、arrayパッケージは当面残された）。

変更の背景

このコミットが行われた2009年2月は、Go言語がまだ一般に公開される前の初期開発段階にありました。Go言語の設計思想の一つに「シンプルさ」と「実用性」があり、標準ライブラリの設計もその原則に従っていました。

初期のGo言語には、動的なコレクションを扱うためのarrayパッケージが存在していましたが、その命名やインターフェースが、より一般的な「ベクター」という概念に合致するように見直されたと考えられます。arrayという名前は、固定長配列を想起させる可能性があり、動的な要素の追加・削除が可能なデータ構造にはvectorという名前の方が適切であるという判断があったと推測されます。

また、Go言語の初期にはジェネリクス（総称型）が導入されていなかったため、様々な型の要素を扱えるようにするためにinterface{}（空インターフェース）を使用し、特定の型に特化した実装（例: IntVector）を別途提供するというパターンが採用されていました。これは、ジェネリクスがないGo言語で汎用的なデータ構造を実装するための一般的なアプローチでした。

この変更は、Go言語の標準ライブラリにおけるデータ構造の命名規則と設計の一貫性を向上させるための初期の取り組みの一環であると言えます。

Go言語は、その設計当初からシンプルさを重視しており、C++やJavaのような複雑なジェネリクス（総称型）は採用していませんでした。そのため、様々な型のデータを格納できる汎用的なコンテナ（リスト、マップなど）を実装する際には、interface{}型が用いられました。interface{}はGo言語における任意の型を表すことができ、これにより異なる型の値を一つのコレクションに格納することが可能になります。

しかし、interface{}を使用すると、コレクションから値を取り出す際に型アサーション（例: value.(int)）が必要となり、実行時エラーのリスクや、型安全性の低下、パフォーマンスのオーバーヘッドが発生する可能性があります。このため、特定のプリミティブ型（例: int, string）に特化したコンテナが必要な場合には、その型専用のコンテナを別途実装するというパターンがよく見られました。このコミットで導入されるIntVectorはその典型例です。

動的配列（ベクター）の概念

動的配列（またはベクター）は、要素の追加や削除によってサイズが動的に変化する配列のようなデータ構造です。内部的には固定長配列で実装されることが多く、容量が不足した場合にはより大きな新しい配列を確保し、既存の要素をコピーするという操作が行われます。これにより、プログラマは固定長配列のサイズ管理を意識することなく、柔軟に要素を扱えます。

Go言語の`Makefile`

Go言語の初期のビルドシステムは、現在のようなgo buildコマンドが主流になる前は、Makefileが広く使われていました。このコミットでもsrc/lib/container/Makefileが追加されており、vectorパッケージのビルド、テスト、インストールに関するルールが定義されています。

GC, CC, AS, AR: Goコンパイラ、Cコンパイラ、アセンブラ、アーカイバを指します。
packages: vector.a（アーカイブファイル）をビルドするターゲット。
install: ビルドされたvector.aを$(GOROOT)/pkg/vector.aにコピーするターゲット。

技術的詳細

このコミットの主要な技術的変更点は、arrayパッケージからvectorパッケージへの移行です。

`vector`パッケージの設計

src/lib/container/vector.goで定義されているvectorパッケージは、以下の主要な要素で構成されています。

Element interface {}: 任意の型の要素を格納するためのインターフェース。Go言語にジェネリクスがなかったため、この型が汎用的な要素型として使用されます。
Vector struct { a []Element }: vectorの基盤となる構造体で、内部的にはElement型のスライスaを保持します。
Init(initial_len int) *Vector: Vectorを初期化するメソッド。指定された初期長で内部スライスを準備します。容量が不足する場合は、既存の容量の2倍に拡張するか、必要な長さに合わせて拡張します。
New(len int) *Vector: Vectorの新しいインスタンスを作成し、初期化するコンビニエンス関数。
Len() int: Vectorの現在の要素数を返します。
At(i int) Element: 指定されたインデックスiの要素を返します。
Set(i int, x Element): 指定されたインデックスiに要素xを設定します。
Last() Element: Vectorの最後の要素を返します。
Insert(i int, x Element): 指定されたインデックスiに要素xを挿入します。内部的にはexpand関数を呼び出してスライスの容量を調整し、要素を移動させます。
Delete(i int) Element: 指定されたインデックスiの要素を削除します。要素を削除した後、スライスを縮小し、GCのために削除された要素の参照をnilにします。
InsertVector(i int, x *Vector): 別のVectorの全要素を指定されたインデックスに挿入します。
Cut(i, j int): インデックスiからj-1までの要素を削除します。
Slice(i, j int) *Vector: インデックスiからj-1までの要素を含む新しいVectorを返します。
Do(f func(elem Element)): Vectorの各要素に対して指定された関数fを実行します。
Push(x Element): Vectorの末尾に要素を追加します（Insertのラッパー）。
Pop() Element: Vectorの末尾から要素を削除し、返します（Deleteのラッパー）。
AppendVector(x *Vector): 別のVectorの全要素を現在のVectorの末尾に追加します。
Less(i, j int) bool: sort.Sortインターフェースの一部として、インデックスiの要素がインデックスjの要素より小さいかどうかを比較します。このメソッドはLessInterfaceというカスタムインターフェースに依存しています。
Swap(i, j int): sort.Sortインターフェースの一部として、インデックスiとjの要素を交換します。

`IntVector`パッケージの設計

src/lib/container/intvector.goで定義されているIntVectorは、vector.Vectorを埋め込み（composition）によって拡張し、int型に特化したメソッドを提供します。これにより、型アサーションの記述を減らし、より型安全な操作を可能にしています。

type IntVector struct { vector.Vector; }: vector.Vectorを匿名フィールドとして埋め込んでいます。これにより、IntVectorのインスタンスはvector.Vectorのすべてのメソッドを直接呼び出すことができます。
Init(len int) *IntVector: vector.VectorのInitメソッドを呼び出し、IntVector自身を返します。
NewIntVector(len int) *IntVector: IntVectorの新しいインスタンスを作成し、初期化するコンビニエンス関数。
At(i int) int: vector.Vector.At(i)の結果をint型に型アサーションして返します。
Set(i int, x int): vector.Vector.Set(i, x)を呼び出します。
Last() int: vector.Vector.Last()の結果をint型に型アサーションして返します。
Insert(i int, x int): vector.Vector.Insert(i, x)を呼び出します。
Delete(i int) int: vector.Vector.Delete(i)の結果をint型に型アサーションして返します。
Push(x int): vector.Vector.Push(x)を呼び出します。
Pop() int: vector.Vector.Pop()の結果をint型に型アサーションして返します。
Less(i, j int) bool: sort.Sortインターフェースの一部として、int型の要素を直接比較します。

`array`パッケージの非推奨化

src/lib/container/array/array.goとsrc/lib/container/array/intarray.goには、以下のコメントが追加され、arrayパッケージが非推奨であることが明示されています。

//
// *** DEPRECATED PACKAGE - USE package vector INSTEAD ***
//

これは、将来的にarrayパッケージが削除されるか、あるいはvectorパッケージに完全に置き換えられることを示唆しています。

既存コードの更新

tabwriter, test/vectors.go, usr/gri/pretty/ast.go, usr/gri/pretty/compilation.go, usr/gri/pretty/parser.go, usr/gri/pretty/printer.go, usr/gri/pretty/symboltable.goなど、既存の複数のファイルでarrayパッケージへの参照がvectorパッケージへの参照に置き換えられています。これは、新しいvectorパッケージへの移行が既に始まっていることを示しています。

特に、tabwriterパッケージでは、内部で使用していたarray.Arrayやarray.IntArrayがvector.Vectorやvector.IntVectorに置き換えられています。

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

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

src/lib/container/Makefile: vectorパッケージのビルド設定が追加されました。
src/lib/container/intvector.go: IntVector構造体とそのメソッドが新規追加されました。
src/lib/container/vector.go: Vector構造体とそのメソッドが新規追加されました。
src/lib/container/vector_test.go: vectorパッケージのテストコードが新規追加されました。
src/lib/container/array/array.go: arrayパッケージが非推奨であることを示すコメントが追加されました。
src/lib/container/array/intarray.go: intarrayパッケージが非推奨であることを示すコメントが追加されました。
src/lib/tabwriter/tabwriter.go: arrayパッケージからvectorパッケージへの依存関係が変更されました。
test/vectors.go: arrayパッケージからvectorパッケージへの依存関係が変更されました。
usr/gri/pretty/*.go: arrayパッケージからvectorパッケージへの依存関係が変更されました。

コアとなるコードの解説

`src/lib/container/vector.go`

このファイルは、Go言語における汎用的な動的配列であるVectorの基盤を定義しています。

package vector

type (
	Element interface {}; // 任意の型を格納するためのインターフェース
	Vector struct {
		a []Element // 内部的にはElement型のスライスを保持
	}
)

// 要素をコピーするヘルパー関数
func copy(dst, src []Element) {
	for i := 0; i < len(src); i++ {
		dst[i] = src[i]
	}
}

// n個の要素を位置iに挿入するためにスライスを拡張する
func expand(a []Element, i, n int) []Element {
	len0 := len(a);
	len1 := len0 + n;
	if len1 < cap(a) {
		// 十分な容量がある場合、スライスを拡張する
		a = a[0 : len1]
	} else {
		// 容量が不足する場合、容量を倍にするか、必要な長さに拡張する
		capb := cap(a)*2;
		if capb < len1 {
			capb = len1
		}
		b := make([]Element, len1, capb);
		copy(b, a); // 既存の要素を新しいスライスにコピー
		a = b
	}

	// 挿入位置に穴を開けるために要素を移動
	for j := len0-1; j >= i ; j-- {
		a[j+n] = a[j]
	}
	return a
}

// Vectorを初期化する
func (p *Vector) Init(initial_len int) *Vector {
	a := p.a;
	if cap(a) == 0 || cap(a) < initial_len {
		n := 8;  // 初期容量
		if initial_len > n {
			n = initial_len
		}
		a = make([]Element, n);
	} else {
		// 既存のエントリをnilにする（GCを助けるため）
		for j := len(a) - 1; j >= 0; j-- {
			a[j] = nil
		}
	}
	p.a = a[0 : initial_len];
	return p
}

// 新しいVectorを作成する
func New(len int) *Vector {
	return new(Vector).Init(len)
}

// ... その他のメソッド（Len, At, Set, Last, Insert, Delete, Cut, Slice, Do, Push, Pop, AppendVector, Less, Swap）

expand関数は、Vectorの動的なサイズ変更の核心部分です。要素を挿入する際に、内部スライスの容量が足りなければ、新しいより大きなスライスを作成し、既存の要素をコピーします。その後、挿入位置に「穴」を開けるために、既存の要素を後方に移動させます。

`src/lib/container/intvector.go`

このファイルは、vector.Vectorを基盤として、int型に特化したIntVectorを実装しています。

package vector

import "vector" // 同じパッケージ名だが、これはvector.goで定義されたvectorパッケージを指す

type IntVector struct {
	// TODO do not export field
	vector.Vector; // vector.Vectorを埋め込み
}

// IntVectorを初期化する
func (p *IntVector) Init(len int) *IntVector {
	p.Vector.Init(len); // 基盤のVectorのInitを呼び出す
	return p;
}

// 新しいIntVectorを作成する
func NewIntVector(len int) *IntVector {
	return new(IntVector).Init(len)
}

// 指定されたインデックスのint要素を返す
func (p *IntVector) At(i int) int {
	return p.Vector.At(i).(int) // 型アサーション
}

// 指定されたインデックスにint要素を設定する
func (p *IntVector) Set(i int, x int) {
	p.Vector.Set(i, x)
}

// ... その他のint型に特化したメソッド（Last, Insert, Delete, Push, Pop, Less）

IntVectorはvector.Vectorを埋め込むことで、vector.Vectorのすべてのメソッドを自動的に継承します。そして、At, Set, Push, Popなどのメソッドをint型に特化して再定義することで、利用者が型アサーションを明示的に記述する必要がなくなります。これは、ジェネリクスがないGo言語で型安全性を高めるための一般的なパターンでした。

参考にした情報源リンク

Go言語のGitHubリポジトリ: https://github.com/golang/go
Go言語の初期のコミットログ
Go言語の設計に関するブログ記事や論文 (特にジェネリクスに関する初期の議論)
Go言語のinterface{}型と型アサーションに関する一般的な解説
動的配列（ベクター）のデータ構造に関する一般的な情報