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

このコミットは、Go言語の初期段階において、より完全な動的配列（ベクター）ライブラリを導入するものです。既存のvector実装を置き換えることを目的としており、汎用的なArray型と、整数に特化したIntArray型を提供します。

コミット

commit b548e7346092383aec5176121ea9d6459963c6b2
Author: Robert Griesemer <gri@golang.org>
Date:   Wed Nov 19 14:05:21 2008 -0800

    - array lib (essentially vector, more complete)
    - TODO replace vector
    
    R=r
    DELTA=314  (313 added, 0 deleted, 1 changed)
    OCL=19592
    CL=19609

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

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

元コミット内容

このコミットの目的は、Go言語の標準ライブラリに新しいarrayライブラリを導入することです。このライブラリは、既存のvector実装よりも機能が豊富で、将来的にはvectorを置き換えることを意図しています。

変更の背景

Go言語は2009年に一般公開されましたが、このコミットはそれ以前の2008年11月に行われています。この時期はGo言語の設計と標準ライブラリの基盤が構築されていた非常に初期の段階にあたります。動的配列（可変長配列）は、多くのプログラミング言語において基本的なデータ構造であり、効率的なデータ管理のために不可欠です。

コミットメッセージにある「TODO replace vector」という記述から、当時すでに何らかのvector実装が存在していたものの、それが不十分であるか、あるいはより堅牢で汎用的な実装が必要とされていたことが伺えます。この新しいarrayライブラリは、そのニーズに応えるために導入されました。特に、Go言語の初期にはジェネリクス（総称型）がなかったため、汎用的なデータ構造を実装するには、interface{}型（現在のany型に相当）を使用するか、特定の型に特化した実装を別途提供する必要がありました。このコミットでは、interface{}を用いた汎用的なArrayと、intに特化したIntArrayの両方が提供されており、当時のGo言語の設計思想が反映されています。

前提知識の解説

• 動的配列（Dynamic Array / Vector）: 配列は固定長ですが、動的配列は要素の追加や削除に応じてサイズが自動的に調整されるデータ構造です。内部的には固定長の配列を使用し、容量が不足した際にはより大きな新しい配列を確保して要素をコピーすることで、動的なサイズ変更を実現します。Go言語では、スライス（[]T）がこの動的配列の概念を抽象化したものです。
• Go言語の初期の型システム: このコミットが行われた2008年当時、Go言語にはまだジェネリクスが導入されていませんでした。そのため、異なる型の要素を格納できる汎用的なデータ構造を実装するには、interface{}型（任意の型を保持できる空のインターフェース）を使用する必要がありました。しかし、interface{}型を使用すると、要素を取り出す際に型アサーション（例: x.(int)）が必要となり、実行時エラーのリスクやパフォーマンスのオーバーヘッドが発生する可能性がありました。このため、特定の型に特化した実装（例: IntArray）も同時に提供されることが一般的でした。
• exportキーワード: Go言語の非常に初期のバージョンでは、識別子を外部に公開するためにexportキーワードが使用されていました。しかし、これはすぐに廃止され、現在のGo言語のように、識別子の最初の文字を大文字にすることで公開されるというシンプルなルールに変更されました。このコミットのコードにはexportキーワードが残っており、Go言語の歴史的な変遷を垣間見ることができます。
• Go言語のビルドシステム: Makefileは、Go言語の初期のビルドプロセスにおいて重要な役割を果たしていました。gobuildやgotestといったツールが使用されており、現在のgo buildやgo testコマンドが統合される前の状態を示しています。

技術的詳細

このコミットで導入されたarrayパッケージは、以下の主要なコンポーネントで構成されています。

1. array.go: 汎用的な動的配列であるArray型を定義しています。

   • export type Element interface {}: Arrayが格納できる要素の型を定義しています。ジェネリクスがないため、interface{}が使用されています。
   • export type Array struct { a *[]Element }: 内部的には[]Element型のスライス（ポインタ）を保持しています。TODO do not export fieldというコメントがあり、フィールドが外部に公開されていることに対する懸念が示されています。
   • Init(initial_len int) *Array: Arrayを初期化し、指定された初期長を持つスライスを割り当てます。容量が不足している場合は、新しいスライスを倍のサイズで作成します。
   • export func New(len int) *Array: Arrayの新しいインスタンスを作成するヘルパー関数です。
   • Len() int: 配列の現在の長さを返します。
   • At(i int) Element: 指定されたインデックスの要素を返します。戻り値はElement型（interface{}）なので、使用する側で型アサーションが必要です。
   • Set(i int, x Element): 指定されたインデックスに要素を設定します。
   • Last() Element: 配列の最後の要素を返します。
   • Insert(i int, x Element): 指定されたインデックスに要素を挿入します。容量が不足している場合は、内部スライスの容量を倍に拡張します。
   • Remove(i int) Element: 指定されたインデックスの要素を削除し、その要素を返します。削除された要素はGCのためにnilに設定されます。
   • Push(x Element): 配列の末尾に要素を追加します。
   • Pop() Element: 配列の末尾から要素を削除し、その要素を返します。
   • Swap(i, j int): 指定された2つのインデックスの要素を交換します。これはソートインターフェースの一部として提供されています。

2. intarray.go: int型に特化した動的配列であるIntArray型を定義しています。

   • export type IntArray struct { array.Array; }: array.Arrayを埋め込むことで、Arrayの機能を再利用しています。
   • Init(len int) *IntArray: IntArrayを初期化します。内部でArrayのInitを呼び出します。
   • export func NewIntArray(len int) *IntArray: IntArrayの新しいインスタンスを作成するヘルパー関数です。
   • At(i int) int, Set(i int, x int), Last() int, Insert(i int, x int), Remove(i int) int, Push(x int), Pop() int: これらはArrayの対応するメソッドをラップし、int型に特化した型アサーションを内部で行うことで、外部からはint型として直接扱えるようにしています。
   • Less(i, j int) bool: ソートインターフェースの一部として、2つの要素の比較を提供します。

3. testarray.go: arrayパッケージのテストコードが含まれています。

   • TestInit() bool, TestNew() bool, TestAccess() bool, TestInsertRemoveClear() bool: これらの関数は、ArrayおよびIntArrayの基本的な操作が正しく機能するかを検証します。Go言語の初期のテストフレームワークの形式を示しています。

4. Makefile: src/lib/container/arrayディレクトリに新しく追加されたMakefileは、arrayパッケージのビルド方法を定義しています。

   • GC, CC, AS, AR: Goコンパイラ、Cコンパイラ、アセンブラ、アーカイバのコマンドを定義しています。
   • default, clean, test, coverage, install: ビルド、クリーンアップ、テスト、カバレッジ測定、インストールなどのターゲットを定義しています。
   • array.a: arrayパッケージのアーカイブファイル（ライブラリファイル）を生成します。

5. src/lib/make.bash: Go言語の標準ライブラリ全体のビルドスクリプトです。

   • このコミットでは、新しく追加されたcontainer/arrayパッケージがビルド対象のディレクトリリストに追加されています。これにより、arrayパッケージがGo言語のビルドシステムに組み込まれ、他のライブラリから利用可能になります。

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

このコミットでは、主に以下のファイルが新規追加または変更されています。

• src/lib/container/array/Makefile (新規追加)
• src/lib/container/array/array.go (新規追加)
• src/lib/container/array/intarray.go (新規追加)
• src/lib/container/array/testarray.go (新規追加)
• src/lib/make.bash (変更)

特に、array.goとintarray.goがこのコミットのコアとなる新しい機能を提供しています。

コアとなるコードの解説

src/lib/container/array/array.go

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

package array

export type Element interface {
}

export type Array struct {
	// TODO do not export field
	a *[]Element
}

func (p *Array) Init(initial_len int) *Array {
	a := p.a;

	if a == nil || cap(a) < initial_len {
		n := 8;  // initial capacity
		if initial_len > n {
			n = initial_len
		}
		a = new([]Element, n); // 新しいスライスを割り当て
	} else {
		// nil out entries
		for j := len(a) - 1; j >= 0; j-- {
			a[j] = nil // 既存の要素をnilでクリア
		}
	}

	p.a = a[0 : initial_len]; // 長さを設定
	return p
}

// ... (他のメソッド)

func (p *Array) Insert(i int, x Element) {
	a := p.a;
	n := len(a);

	// grow array by doubling its capacity
	if n == cap(a) { // 容量が不足している場合
		b := new([]Element, 2*n); // 容量を倍にした新しいスライスを作成
		for j := n-1; j >= 0; j-- {
			b[j] = a[j]; // 要素をコピー
		}
		a = b
	}

	// make a hole
	a = a[0 : n+1]; // 長さを1増やす
	for j := n; j > i; j-- {
		a[j] = a[j-1] // 挿入位置より後ろの要素を1つずらす
	}

	a[i] = x; // 要素を挿入
	p.a = a
}

func (p *Array) Remove(i int) Element {
	a := p.a;
	n := len(a);

	x := a[i]; // 削除する要素を保持
	for j := i+1; j < n; j++ {
		a[j-1] = a[j] // 削除位置より後ろの要素を1つ前にずらす
	}

	a[n-1] = nil;  // support GC, nil out entry // 最後の要素をnilにしてGCを助ける
	p.a = a[0 : n-1]; // 長さを1減らす

	return x
}

Array型は、内部に*[]Element（interface{}型のスライスへのポインタ）を保持することで、任意の型の要素を格納できるようにしています。Initメソッドでは、初期容量が不足している場合に内部スライスを倍のサイズに拡張するロジックが含まれています。InsertやRemoveメソッドでは、要素の挿入・削除に伴うスライスの要素の移動や容量の調整が行われています。特にInsertでは、容量が足りない場合に新しいスライスを確保して要素をコピーする「倍々成長」戦略が採用されています。Removeでは、削除された要素がガベージコレクションの対象となるようにnilに設定する配慮が見られます。

src/lib/container/array/intarray.go

このファイルは、array.Arrayを基盤として、int型に特化した動的配列を提供します。

package array

import "array" // 同じパッケージ内だが、当時のGoではこのようにimportしていた可能性

export type IntArray struct {
	// TODO do not export field
	array.Array; // array.Arrayを埋め込み
}

// ... (Init, NewIntArray)

func (p *IntArray) At(i int) int {
	return p.Array.At(i).(int) // 型アサーションでint型に変換
}

func (p *IntArray) Set(i int, x int) {
	p.Array.Set(i, x) // int型をElement型として設定
}

// ... (他のメソッド)

func (p *IntArray) Less(i, j int) bool {
	return p.At(i) < p.At(j) // int型として比較
}

IntArrayはarray.Arrayを埋め込むことで、そのメソッドを継承しつつ、At, Setなどのメソッドをオーバーライド（Goではメソッドの埋め込みと呼び出し）しています。これにより、int型に特化したインターフェースを提供し、利用者が明示的な型アサーションを行う手間を省いています。これは、ジェネリクスがない時代のGo言語で、型安全性を保ちつつ汎用的なデータ構造を特定の型で使いやすくするための一般的なパターンでした。

関連リンク

• Go言語の公式ドキュメント (現在のバージョン): https://go.dev/doc/
• Go言語の初期の歴史に関する情報 (例: Go言語のブログ記事やカンファレンス発表など)

参考にした情報源リンク

• Go言語のソースコード (このコミットの前後): https://github.com/golang/go
• Go言語の歴史に関する一般的な知識
• 動的配列（ベクター）のデータ構造に関する一般的な知識