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

このコミットは、Go言語の標準ライブラリ container/list パッケージにおける予期せぬパニック（panic）の問題を修正するものです。具体的には、リストに属していない Element に対して Next() または Prev() メソッドが呼び出された際に発生するパニックを解消し、ドキュメントに記載されている通りの nil を返す挙動に戻します。

コミット

commit 7adb42eee479382018621eb24c665cf83f3a73f7
Author: Richard Eric Gavaletz <gavaletz@gmail.com>
Date:   Mon Sep 9 15:41:36 2013 -0700

    container/list: unexpected panic if Next/Prev called outside of list.
    
    Before CL 7065067 calling Next on an element returned either the
    next/prev element or nil was returned.  After the CL if an element
    was not part of a list e.Next() and e.Prev() will panic.  This CL
    returns to the documented behavior, that Next/Prev returns the
    next/prev list element or nil.
    
    Fixes #6349.
    
    R=golang-dev, gri
    CC=golang-dev
    https://golang.org/cl/13234051

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

https://github.com/golang/go/commit/7adb42eee479382018621eb24c665cf83f3a73f7

このコミットの元の内容は、container/list パッケージの Element 型の Next() および Prev() メソッドが、要素がリストの一部ではない場合にパニックを引き起こすという問題に対処しています。以前の変更 (CL 7065067) によって、これらのメソッドの挙動が変更され、ドキュメントに記載されている nil を返す代わりにパニックが発生するようになっていました。このコミットは、この挙動を修正し、ドキュメント通りの nil を返すように戻すことを目的としています。

変更の背景

Go言語の container/list パッケージは、二重リンクリストの実装を提供します。このリストの Element 型には、リスト内の次の要素 (Next()) や前の要素 (Prev()) を取得するためのメソッドが用意されています。これらのメソッドは、要素がリストの末尾にある場合や、リストから削除された場合など、有効な次の/前の要素が存在しない場合には nil を返すことがドキュメントで保証されていました。

しかし、以前の変更セット (CL 7065067) によって、この挙動が意図せず変更されました。具体的には、リストから削除された Element に対して Next() や Prev() を呼び出すと、内部的なリストのルート要素へのポインタが不正な状態になり、結果としてパニックが発生するようになりました。これは、ユーザーが期待する挙動と異なり、アプリケーションのクラッシュを引き起こす可能性がありました。

このコミットは、この予期せぬパニックを修正し、container/list パッケージの Next() および Prev() メソッドが、要素がリストに属していない場合や、有効な次の/前の要素が存在しない場合に、ドキュメント通りに nil を返すようにするためのものです。これは、Go言語の安定性と予測可能性を維持するために重要な修正でした。

前提知識の解説

Go言語の `container/list` パッケージ

container/list パッケージは、Go言語の標準ライブラリの一部であり、二重リンクリスト（doubly linked list）の実装を提供します。二重リンクリストは、各ノードが前のノードと次のノードの両方への参照を持つデータ構造です。これにより、リスト内を前方にも後方にも効率的に移動できます。

List 型: リスト全体を表す構造体です。リストの先頭 (Front()) と末尾 (Back()) の要素へのポインタを持ちます。
Element 型: リスト内の個々の要素を表す構造体です。以下のフィールドを持ちます。
- Value interface{}: 要素が保持する実際のデータ。interface{} 型なので、任意の型の値を格納できます。
- next *Element: リスト内の次の要素へのポインタ。
- prev *Element: リスト内の前の要素へのポインタ。
- list *List: この要素が属するリストへのポインタ。

`Next()` と `Prev()` メソッド

Element 型には、リスト内を移動するための以下のメソッドがあります。

func (e *Element) Next() *Element: e の次の要素を返します。e がリストの末尾である場合や、e がリストに属していない場合は nil を返します。
func (e *Element) Prev() *Element: e の前の要素を返します。e がリストの先頭である場合や、e がリストに属していない場合は nil を返します。

パニック (Panic)

Go言語におけるパニックは、プログラムの実行中に回復不可能なエラーが発生したことを示すメカニズムです。パニックが発生すると、通常のプログラムフローは中断され、遅延関数（defer）が実行された後、プログラムはクラッシュします。パニックは通常、プログラマーの論理エラーや、予期せぬ不正な状態に陥った場合に発生します。

CL (Change List)

Go言語の開発では、変更は「Change List (CL)」として管理されます。これは、特定の変更セットを識別するための番号であり、コードレビューシステム（Gerritなど）で使われます。コミットメッセージに記載されている CL 7065067 は、このコミットの前に container/list の挙動を変更した特定の変更セットを指します。

Issue (問題)

GitHubやGoのIssueトラッカーにおける「Issue」は、バグ報告、機能リクエスト、または一般的な議論のための項目です。Fixes #6349 は、このコミットがGoのIssueトラッカーで報告された6349番の問題を修正することを示しています。

技術的詳細

このコミットの技術的な核心は、Element の Next() および Prev() メソッドの内部ロジックに e.list != nil という条件を追加することです。

元の実装では、e.next または e.prev が e.list.root と等しくない場合にのみ、次の/前の要素を返していました。ここで e.list.root は、リストの内部的なダミー要素であり、リストの先頭と末尾をつなぐ役割を果たします。

問題は、Element がリストから削除された場合、その e.list フィールドが nil に設定されるにもかかわらず、e.next や e.prev は以前のリストの要素を指したままになる可能性がある点でした。この状態で e.list.root にアクセスしようとすると、nil ポインタに対するデリファレンスが発生し、パニックを引き起こしていました。

このコミットでは、e.list != nil というチェックを追加することで、この問題を解決しています。

func (e *Element) Next() *Element の変更:
- 変更前: if p := e.next; p != &e.list.root { ... }
- 変更後: if p := e.next; e.list != nil && p != &e.list.root { ... }
func (e *Element) Prev() *Element の変更:
- 変更前: if p := e.prev; p != &e.list.root { ... }
- 変更後: if p := e.prev; e.list != nil && p != &e.list.root { ... }

この変更により、e.list が nil の場合（つまり、要素がどのリストにも属していない場合）は、p != &e.list.root の評価が行われる前に false となり、Next() や Prev() は安全に nil を返すようになります。これにより、ドキュメントに記載されている挙動が保証され、予期せぬパニックが回避されます。

また、このコミットには、修正が正しく機能することを確認するためのテストケース TestIssue6349 が追加されています。このテストでは、要素をリストに追加し、その後リストから削除し、削除された要素に対して Next() と Prev() を呼び出して、両方が nil を返すことを確認しています。

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

`src/pkg/container/list/list.go`

--- a/src/pkg/container/list/list.go
+++ b/src/pkg/container/list/list.go
@@ -29,7 +29,7 @@ type Element struct {
 
 // Next returns the next list element or nil.
 func (e *Element) Next() *Element {
-	if p := e.next; p != &e.list.root {
+	if p := e.next; e.list != nil && p != &e.list.root {
 		return p
 	}
 	return nil
@@ -37,7 +37,7 @@ func (e *Element) Next() *Element {
 
 // Prev returns the previous list element or nil.
 func (e *Element) Prev() *Element {
-	if p := e.prev; p != &e.list.root {
+	if p := e.prev; e.list != nil && p != &e.list.root {
 		return p
 	}
 	return nil

`src/pkg/container/list/list_test.go`

--- a/src/pkg/container/list/list_test.go
+++ b/src/pkg/container/list/list_test.go
@@ -234,6 +234,24 @@ func TestIssue4103(t *testing.T) {
 	}
 }
 
+func TestIssue6349(t *testing.T) {
+	l := New()
+	l.PushBack(1)
+	l.PushBack(2)
+
+	e := l.Front()
+	l.Remove(e)
+	if e.Value != 1 {
+		t.Errorf("e.value = %d, want 1", e.Value)
+	}
+	if e.Next() != nil {
+		t.Errorf("e.Next() != nil")
+	}
+	if e.Prev() != nil {
+		t.Errorf("e.Prev() != nil")
+	}
+}
+
 func TestMove(t *testing.T) {
 	l := New()
 	e1 := l.PushBack(1)

コアとなるコードの解説

`list.go` の変更

list.go の変更は非常にシンプルですが、その影響は大きいです。

Next() メソッド:
- if p := e.next; p != &e.list.root { が if p := e.next; e.list != nil && p != &e.list.root { に変更されました。
- e.list != nil という条件が追加されたことで、e.list が nil（つまり、Element がどのリストにも属していない状態）の場合には、後続の p != &e.list.root の評価が行われる前に条件全体が false となります。これにより、nil ポインタ e.list の root フィールドにアクセスしようとしてパニックが発生するのを防ぎます。
- もし e.list が nil であれば、Next() メソッドは nil を返し、これはドキュメントに記載されている正しい挙動です。
Prev() メソッド:
- Next() メソッドと同様に、if p := e.prev; p != &e.list.root { が if p := e.prev; e.list != nil && p != &e.list.root { に変更されました。
- これもまた、e.list が nil の場合に安全に nil を返すようにするための変更です。

この変更は、Element がリストから削除された後もその Element オブジェクト自体はメモリ上に存在し続ける可能性があるというGoのガベージコレクションの特性と、container/list の内部実装（特に Element が list フィールドを持つこと）を考慮したものです。要素がリストから削除されると、Element.list フィールドは nil に設定されますが、Element.next や Element.prev は以前のリストの要素を指したままになることがあります。この状態でのアクセスは危険であり、このコミットはそれを防ぎます。

`list_test.go` の変更

list_test.go に追加された TestIssue6349 は、この修正の有効性を検証するための重要なテストケースです。

l := New(): 新しい空のリストを作成します。
l.PushBack(1) と l.PushBack(2): リストに2つの要素（値が1と2）を追加します。
e := l.Front(): リストの先頭要素（値が1の要素）を取得します。
l.Remove(e): 取得した要素 e をリストから削除します。この時点で、e はもはやリストの一部ではありません。
if e.Value != 1 { ... }: 削除された要素 e の値が期待通り1であることを確認します。これは、要素が正しく取得され、削除されたことを確認するためです。
if e.Next() != nil { t.Errorf("e.Next() != nil") }: ここが最も重要なテストポイントです。 リストから削除された e に対して Next() を呼び出し、その結果が nil であることを確認します。もし修正が適用されていなければ、ここでパニックが発生するか、あるいは nil 以外の不正な値が返される可能性があります。
if e.Prev() != nil { t.Errorf("e.Prev() != nil") }: 同様に、リストから削除された e に対して Prev() を呼び出し、その結果が nil であることを確認します。

このテストケースは、まさにこのコミットが修正しようとしているシナリオ（リストから削除された要素に対する Next()/Prev() 呼び出し）を再現し、期待される nil 挙動が正しく実装されていることを保証します。

参考にした情報源リンク

Go言語の公式ドキュメント: container/list パッケージ
Go言語のソースコード: src/pkg/container/list/list.go および src/pkg/container/list/list_test.go
Go Issue Tracker: Issue 6349
Go Code Review Dashboard (Gerrit): CL 13234051
一般的なデータ構造としての二重リンクリストに関する情報
Go言語におけるパニックとエラーハンドリングに関する情報

comemo