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

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

このコミットは、Go言語の標準ライブラリであるtext/templateパッケージにおけるrangeアクションの挙動を改善するものです。具体的には、マップをrangeする際に、キーが基本的な型（整数、浮動小数点数、文字列など）で順序付けが可能な場合、そのキーをソートしてからイテレーションを行うように変更されました。これにより、テンプレートの出力がより決定論的で一貫性のあるものになります。

変更されたファイルは以下の通りです。

  • src/pkg/text/template/doc.go: text/templateパッケージのドキュメントファイル。rangeアクションのマップに対する新しい挙動（キーのソート）に関する説明が追加されました。
  • src/pkg/text/template/exec.go: text/templateパッケージの実行エンジンの中核をなすファイル。マップのキーをソートするための新しいロジックと、そのソートされたキーを使ってイテレーションを行うための変更が加えられました。
  • src/pkg/text/template/exec_test.go: text/templateパッケージのテストファイル。マップのrangeに関する既存のテストケースが、新しいソート挙動に合わせて更新されました。

コミット

commit a5950df89e129e93f76aa8391f84beb460ef82be
Author: Rob Pike <r@golang.org>
Date:   Fri Jan 13 14:09:13 2012 -0800

    template: for range on a map, sort the keys if feasible.
    Fixes #2696.
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/5543055

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

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

元コミット内容

template: for range on a map, sort the keys if feasible. Fixes #2696.

変更の背景

Go言語の組み込み型であるmapは、その設計上、要素の順序が保証されません。これは、mapをイテレートする際の順序が、実行ごとに異なる可能性があることを意味します。この非決定的な挙動は、Goのtext/templateパッケージでマップをrangeアクションで処理する際に問題を引き起こすことがありました。

具体的には、テンプレートの出力がmapのイテレーション順序に依存する場合、同じテンプレートとデータを与えても、実行するたびに出力が変わってしまう可能性がありました。これは、特に自動テストの再現性を損なったり、ユーザーが期待する一貫したレポートや表示が得られなかったりする原因となります。

このコミットは、この非決定性の問題を解決するために導入されました。mapのキーが整数、浮動小数点数、文字列といった順序付けが可能な基本的な型である場合に、イテレーションの前にキーをソートすることで、rangeアクションの出力を安定させ、予測可能で一貫性のあるものにすることを目的としています。コミットメッセージにあるFixes #2696は、この変更が特定のバグ報告や機能要望に対応するものであることを示しています。

前提知識の解説

Go言語のmap

Go言語のmapは、キーと値のペアを格納するハッシュテーブル（連想配列）です。Goの仕様では、mapのイテレーション順序は定義されておらず、実行ごとに異なる可能性があります。これは意図的な設計であり、開発者が順序に依存しないコードを書くことを促すため、また、ハッシュ衝突攻撃を防ぐためにイテレーション順序をランダム化するためでもあります。

text/templateパッケージ

text/templateは、Goの標準ライブラリの一部であり、テキストベースのテンプレートを生成するためのパッケージです。HTML、XML、プレーンテキストなど、様々な形式のテキスト出力を生成するのに使用されます。テンプレートは、データ構造（Goの構造体、マップ、スライスなど）と組み合わせて使用され、データの値に基づいて動的にテキストを生成します。

rangeアクション

text/templateにおける主要な制御構造の一つで、配列、スライス、またはマップの要素を反復処理するために使用されます。構文は{{range pipeline}} T1 {{end}}の形式で、pipelineの評価結果が配列、スライス、またはマップである場合、その各要素に対してT1（テンプレートのブロック）が実行されます。マップの場合、dot（現在のコンテキスト）は各イテレーションでマップの値に設定されます。

reflectパッケージ

Goの標準ライブラリの一部で、実行時に型情報を検査したり、値の操作を行ったりするための機能を提供します。このコミットでは、テンプレートに渡されたマップのキーがどのような型であるかを動的に判断し、それに基づいてソート処理を適用するためにreflect.Valueが使用されています。

sortパッケージ

Goの標準ライブラリの一部で、スライスやユーザー定義のコレクションをソートするためのインターフェースとアルゴリズムを提供します。sort.Interfaceインターフェース（Len(), Less(i, j int), Swap(i, j int)の3つのメソッドを持つ）を実装することで、任意の型のスライスをソートできます。このコミットでは、reflect.Valueのスライスをソートするために、このインターフェースを実装したカスタム型が定義されています。

技術的詳細

このコミットの主要な目的は、text/templateにおけるマップのrangeアクションの非決定的なイテレーション順序を、可能な限り決定論的なものにすることです。

  1. 非決定的なマップイテレーションの課題: Goのmapの特性により、text/templateでマップをrangeする際、キーの順序が保証されないため、テンプレートの出力が非決定的なものになっていました。これは、特にテストの再現性や、一貫した出力が求められる場面で問題となります。

  2. ソートの導入: この変更では、mapのキーがGoの基本的な型（int, float, string, uintなど）であり、かつ順序付けが可能である場合に、イテレーションの前にキーをソートするロジックが導入されました。これにより、テンプレートの出力がキーの順序に基づいて一貫するようになります。

  3. reflect.Valueとソート: text/templateは、テンプレートに渡されたデータをreflect.Valueとして内部的に扱います。マップのキーもreflect.Valueのスライスとして取得されるため、これをソートするためには、reflect.Valueを直接扱うカスタムソートロジックが必要となります。

  4. sortKeys関数の追加とソートヘルパー型:

    • src/pkg/text/template/exec.goにsortKeysという新しい関数が追加されました。この関数は[]reflect.Value（マップのキーのスライス）を受け取ります。
    • sortKeys関数は、スライスが空であるか、要素が1つ以下である場合はソートせずにそのまま返します。
    • それ以外の場合、最初の要素のKind()（型）を検査し、その型に基づいて適切なソートアルゴリズムを適用します。
      • reflect.Float32, reflect.Float64の場合、rvFloats型を使用してソートします。
      • reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64の場合、rvInts型を使用してソートします。
      • reflect.Stringの場合、rvStrings型を使用してソートします。
      • reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptrの場合、rvUints型を使用してソートします。
    • これらのrvInts, rvUints, rvFloats, rvStrings型は、[]reflect.Valueをラップするrvs型を埋め込んでおり、sort.Interfaceインターフェース（Len(), Less(i, j int), Swap(i, j int)）を実装しています。これにより、Goの標準sortパッケージのsort.Sort関数を使用して、reflect.Valueのスライスをソートすることが可能になります。Less()メソッドは、それぞれの型に応じたreflect.Valueの比較（例: Int(), Uint(), Float(), String()）を行います。

  5. walkRange関数の変更: src/pkg/text/template/exec.go内のwalkRange関数（rangeアクションの実行を担当する部分）において、マップのキーを取得するval.MapKeys()の戻り値が、新しく追加されたsortKeys関数に渡されるようになりました。これにより、マップのキーがイテレーションの前にソートされ、結果としてテンプレートの出力順序が安定します。

  6. ドキュメントの更新: src/pkg/text/template/doc.goのrangeアクションに関する説明が更新され、マップのキーが基本的な型で順序付け可能な場合、要素がソートされたキー順で訪問されることが明記されました。これは、この変更の挙動をユーザーに明確に伝えるための重要な変更です。

  7. テストの変更: src/pkg/text/template/exec_test.goでは、マップのrangeに関する既存のテストケースが修正されました。以前は、テストの安定性を確保するためにMSortというヘルパー関数を使って明示的にマップのキーをソートしていましたが、テンプレートエンジン自体がソートを行うようになったため、MSortの呼び出しが削除されました。また、期待される出力も、ソートされたキーの順序を反映するように修正されました。

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

diff --git a/src/pkg/text/template/doc.go b/src/pkg/text/template/doc.go
index 4208d53a0a..3be1ec44e6 100644
--- a/src/pkg/text/template/doc.go
+++ b/src/pkg/text/template/doc.go
@@ -50,7 +50,9 @@ data, defined in detail below.\n 		The value of the pipeline must be an array, slice, or map. If\n 		the value of the pipeline has length zero, nothing is output;\n 		otherwise, dot is set to the successive elements of the array,\n-\t\tslice, or map and T1 is executed.\n+\t\tslice, or map and T1 is executed. If the value is a map and the\n+\t\tkeys are of basic type with a defined order (\"comparable\"), the\n+\t\telements will be visited in sorted key order.\n \n \t{{range pipeline}} T1 {{else}} T0 {{end}}\n \t\tThe value of the pipeline must be an array, slice, or map. If\ndiff --git a/src/pkg/text/template/exec.go b/src/pkg/text/template/exec.go
index 2171b279be..973189a8a6 100644
--- a/src/pkg/text/template/exec.go
+++ b/src/pkg/text/template/exec.go
@@ -9,6 +9,7 @@ import (\n 	"io"\n 	"reflect"\n 	"runtime"\n+	"sort"\n 	"strings"\n 	"text/template/parse"\n )\n@@ -234,7 +235,7 @@ func (s *state) walkRange(dot reflect.Value, r *parse.RangeNode) {\n \t\tif val.Len() == 0 {\n \t\t\tbreak\n \t\t}\n-\t\tfor _, key := range val.MapKeys() {\n+\t\tfor _, key := range sortKeys(val.MapKeys()) {\n \t\t\toneIteration(key, val.MapIndex(key))\n \t\t}\n \t\treturn\n@@ -676,3 +677,44 @@ func (s *state) printValue(n parse.Node, v reflect.Value) {\n \t}\n \tfmt.Fprint(s.wr, v.Interface())\n }\n+\n+// Types to help sort the keys in a map for reproducible output.\n+\n+type rvs []reflect.Value\n+\n+func (x rvs) Len() int      { return len(x) }\n+func (x rvs) Swap(i, j int) { x[i], x[j] = x[j], x[i] }\n+\n+type rvInts struct{ rvs }\n+\n+func (x rvInts) Less(i, j int) bool { return x.rvs[i].Int() < x.rvs[j].Int() }\n+\n+type rvUints struct{ rvs }\n+\n+func (x rvUints) Less(i, j int) bool { return x.rvs[i].Uint() < x.rvs[j].Uint() }\n+\n+type rvFloats struct{ rvs }\n+\n+func (x rvFloats) Less(i, j int) bool { return x.rvs[i].Float() < x.rvs[j].Float() }\n+\n+type rvStrings struct{ rvs }\n+\n+func (x rvStrings) Less(i, j int) bool { return x.rvs[i].String() < x.rvs[j].String() }\n+\n+// sortKeys sorts (if it can) the slice of reflect.Values, which is a slice of map keys.\n+func sortKeys(v []reflect.Value) []reflect.Value {\n+\tif len(v) <= 1 {\n+\t\treturn v\n+\t}\n+\tswitch v[0].Kind() {\n+\tcase reflect.Float32, reflect.Float64:\n+\t\tsort.Sort(rvFloats{v})\n+\tcase reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:\n+\t\tsort.Sort(rvInts{v})\n+\tcase reflect.String:\n+\t\tsort.Sort(rvStrings{v})\n+\tcase reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:\n+\t\tsort.Sort(rvUints{v})\n+\t}\n+\treturn v\n+}\ndiff --git a/src/pkg/text/template/exec_test.go b/src/pkg/text/template/exec_test.go
index e33988b86c..2070cefde7 100644
--- a/src/pkg/text/template/exec_test.go
+++ b/src/pkg/text/template/exec_test.go
@@ -11,7 +11,6 @@ import (\n 	"fmt"\n 	"os"\n 	"reflect"\n-\t"sort"\n 	"strings"\n 	"testing"\n )\n@@ -169,18 +168,6 @@ func (t *T) MAdd(a int, b []int) []int {\n 	return v\n }\n \n-// MSort is used to sort map keys for stable output. (Nice trick!)\n-func (t *T) MSort(m map[string]int) []string {\n-\tkeys := make([]string, len(m))\n-\ti := 0\n-\tfor k := range m {\n-\t\tkeys[i] = k\n-\t\ti++\n-\t}\n-\tsort.Strings(keys)\n-\treturn keys\n-}\n-\n // EPERM returns a value and an error according to its argument.\n func (t *T) EPERM(error bool) (bool, error) {\n \tif error {\n@@ -410,9 +397,9 @@ var execTests = []execTest{\n \t{\"range empty else\", \"{{range .SIEmpty}}-{{.}}-{{else}}EMPTY{{end}}\", \"EMPTY\", tVal, true},\n \t{\"range []bool\", \"{{range .SB}}-{{.}}-{{end}}\", \"-true--false-\", tVal, true},\n \t{\"range []int method\", \"{{range .SI | .MAdd .I}}-{{.}}-{{end}}\", \"-20--21--22-\", tVal, true},\n-\t{\"range map\", \"{{range .MSI | .MSort}}-{{.}}-{{end}}\", \"-one--three--two-\", tVal, true},\n+\t{\"range map\", \"{{range .MSI}}-{{.}}-{{end}}\", \"-1--3--2-\", tVal, true},\n \t{\"range empty map no else\", \"{{range .MSIEmpty}}-{{.}}-{{end}}\", \"\", tVal, true},\n-\t{\"range map else\", \"{{range .MSI | .MSort}}-{{.}}-{{else}}EMPTY{{end}}\", \"-one--three--two-\", tVal, true},\n+\t{\"range map else\", \"{{range .MSI}}-{{.}}-{{else}}EMPTY{{end}}\", \"-1--3--2-\", tVal, true},\n \t{\"range empty map else\", \"{{range .MSIEmpty}}-{{.}}-{{else}}EMPTY{{end}}\", \"EMPTY\", tVal, true},\n \t{\"range empty interface\", \"{{range .Empty3}}-{{.}}-{{else}}EMPTY{{end}}\", \"-7--8-\", tVal, true},\n \t{\"range empty nil\", \"{{range .Empty0}}-{{.}}-{{end}}\", \"\", tVal, true},\n```

## コアとなるコードの解説

### `src/pkg/text/template/doc.go`の変更

*   **ドキュメントの更新**: `range`アクションの説明に、以下の文言が追加されました。
    ```
    If the value is a map and the keys are of basic type with a defined order ("comparable"), the elements will be visited in sorted key order.
    ```
    これは、「もし値がマップであり、キーが定義された順序を持つ基本型（"comparable"）である場合、要素はソートされたキー順で訪問される」という意味です。これにより、ユーザーは`range`がマップに対してどのように動作するか、特に順序に関する新しい挙動を理解できます。

### `src/pkg/text/template/exec.go`の変更

*   **`import "sort"`の追加**:
    マップのキーをソートするために、Goの標準ライブラリである`sort`パッケージがインポートされました。

*   **`walkRange`関数の変更**:
    `walkRange`関数は、テンプレートの`range`アクションの実行を担当します。この関数内で、マップのキーを取得する`val.MapKeys()`の戻り値が、直接イテレートされるのではなく、新しく追加された`sortKeys`関数に渡されるようになりました。
    ```go
    -		for _, key := range val.MapKeys() {
    +		for _, key := range sortKeys(val.MapKeys()) {
    			oneIteration(key, val.MapIndex(key))
    		}
    ```
    この変更により、マップのキーが`sortKeys`関数によってソートされてからループ処理が行われるようになり、結果としてイテレーションの順序が安定します。

*   **ソートヘルパー型と`sortKeys`関数の追加**:
    マップのキー（`reflect.Value`のスライス）をソートするために、以下の新しい型と関数が追加されました。

    *   **`rvs`型**:
        ```go
        type rvs []reflect.Value

        func (x rvs) Len() int      { return len(x) }
        func (x rvs) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
        ```
        この型は`[]reflect.Value`をラップし、`sort.Interface`インターフェースの`Len()`と`Swap()`メソッドを実装しています。これにより、`rvs`型のスライスは`sort.Sort`関数でソート可能になります。

    *   **`rvInts`, `rvUints`, `rvFloats`, `rvStrings`型**:
        ```go
        type rvInts struct{ rvs }
        func (x rvInts) Less(i, j int) bool { return x.rvs[i].Int() < x.rvs[j].Int() }

        type rvUints struct{ rvs }
        func (x rvUints) Less(i, j int) bool { return x.rvs[i].Uint() < x.rvs[j].Uint() }

        type rvFloats struct{ rvs }
        func (x rvFloats) Less(i, j int) bool { return x.rvs[i].Float() < x.rvs[j].Float() }

        type rvStrings struct{ rvs }
        func (x rvStrings) Less(i, j int) bool { return x.rvs[i].String() < x.rvs[j].String() }
        ```
        これらの型は、それぞれ`rvs`を埋め込み、特定のGoの基本型（整数、符号なし整数、浮動小数点数、文字列）の`reflect.Value`を比較するための`Less()`メソッドを実装しています。これにより、`sort.Sort`関数がこれらの型をソートする際に、`reflect.Value`から実際の値を取り出して比較を行うことができます。

    *   **`sortKeys`関数**:
        ```go
        func sortKeys(v []reflect.Value) []reflect.Value {
        	if len(v) <= 1 {
        		return v
        	}
        	switch v[0].Kind() {
        	case reflect.Float32, reflect.Float64:
        		sort.Sort(rvFloats{v})
        	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
        		sort.Sort(rvInts{v})
        	case reflect.String:
        		sort.Sort(rvStrings{v})
        	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
        		sort.Sort(rvUints{v})
        	}
        	return v
        }
        ```
        この関数は、`[]reflect.Value`（マップのキーのスライス）を受け取ります。
        *   スライスが空であるか、要素が1つ以下である場合は、ソートの必要がないため、元のスライスをそのまま返します。
        *   それ以外の場合、スライスの最初の要素の`Kind()`（型）を検査します。
        *   `switch`文を使って、キーの型が浮動小数点数、整数、文字列、符号なし整数のいずれかであるかを判断し、それぞれに対応するソートヘルパー型（`rvFloats`, `rvInts`, `rvStrings`, `rvUints`）のインスタンスを作成し、`sort.Sort`関数に渡してソートを実行します。
        *   ソートが完了したスライスを返します。これにより、マップのキーが型に応じて適切にソートされます。

### `src/pkg/text/template/exec_test.go`の変更

*   **`import "sort"`の削除**:
    テストファイルから`sort`パッケージのインポートが削除されました。これは、テスト内で明示的にマップのキーをソートする必要がなくなったためです。

*   **`MSort`ヘルパー関数の削除**:
    ```go
    -// MSort is used to sort map keys for stable output. (Nice trick!)
    -func (t *T) MSort(m map[string]int) []string {
    -...
    -}
    ```
    `MSort`というヘルパー関数が削除されました。この関数は、以前はテストの安定性を確保するためにマップのキーをソートしていましたが、テンプレートエンジン自体がソートを行うようになったため、不要になりました。

*   **`execTests`内のテストケースの修正**:
    マップの`range`に関するテストケースの期待値が変更されました。
    ```go
    -	{"range map", "{{range .MSI | .MSort}}-{{.}}-{{end}}", "-one--three--two-", tVal, true},
    +	{"range map", "{{range .MSI}}-{{.}}-{{end}}", "-1--3--2-", tVal, true},
    ...
    -	{"range map else", "{{range .MSI | .MSort}}-{{.}}-{{else}}EMPTY{{end}}", "-one--three--two-", tVal, true},
    +	{"range map else", "{{range .MSI}}-{{.}}-{{else}}EMPTY{{end}}", "-1--3--2-", tVal, true},
    ```
    以前は`MSort`によってソートされた文字列キーの順序（例: `-one--three--two-`）を期待していましたが、変更後はテンプレートエンジンが数値キーをソートするようになったため、数値キーのソートされた順序（例: `-1--3--2-`）を期待するように修正されました。これは、テンプレートエンジンが数値キーをソートするようになったことを反映しています。

## 関連リンク

*   Go Gerrit Change: [https://golang.org/cl/5543055](https://golang.org/cl/5543055)
*   Go Issue 2696 (推定): このコミットが修正したとされる問題の詳細は、当時のGoのIssueトラッカー（Google Codeなど）に存在した可能性があります。直接的なリンクは現在のGoのIssueトラッカーでは見つかりませんが、この変更はマップのイテレーション順序の非決定性による問題を解決することを目的としていました。

## 参考にした情報源リンク

*   Go言語の`map`に関する公式ドキュメントやブログ記事（Goの`map`の順序が保証されないことについて解説しているもの）。
*   Go `reflect`パッケージのドキュメント: [https://pkg.go.dev/reflect](https://pkg.go.dev/reflect)
*   Go `sort`パッケージのドキュメント: [https://pkg.go.dev/sort](https://pkg.go.dev/sort)
*   Go `text/template`パッケージのドキュメント: [https://pkg.go.dev/text/template](https://pkg.go.dev/text/template)