【Go】appendの罠

AtCoder風Introduction

hoge.txtというファイルの中身のN文字目以降に文字列Sを挿入したものを出力してください。

hoge.txt

Hello, World!

N, Sはコマンドライン引数から

N S

という形で渡されます。

とりあえずばーっとコードを書いてみました。
見やすさの関係上エラーハンドリングは省略してます。許してください！

main.go

package main

import (
	"flag"
	"fmt"
	"io"
	"os"
	"strconv"
)

func main() {
	flag.Parse()
	nStr := flag.Arg(0)
	n, _ := strconv.Atoi(nStr)
	s := flag.Arg(1)

	f, _ := os.Open("./hoge.txt")
	defer f.Close()

	content, _ := io.ReadAll(f)
	result := append(content[:n], []byte(s)...)
	result = append(result, content[n:]...)

	fmt.Println(string(result))
}

試しに以下のような入力を与えてみました。

go run main.go 5 ", yuzuy"

どのような値が出力されたでしょうか？
直感的には

stdout

Hello, yuzuy, World!

という値が出力されると想像すると思います。
ですが実際には

stdout

Hello, yuzuy, yuzuy!

という結果が得られます。

実際に動かしてみてもわかると思います(Playground用に一部改変しています)。
https://play.golang.org/p/jls_jl0Vgnw

反直感的ですね！ 面白くなってきました、早速デバッグを始めましょう。

デバッグ

手っ取り早くprintデバッグをしてみましょう。
こんな感じで出力するようにしました。

main.go

content, _ := io.ReadAll(f)
fmt.Println("content: " + string(content))
result := append(content[:n], []byte(s)...)
fmt.Println("result: " + string(result))
fmt.Println("content: " + string(content))
fmt.Println("content[n:]: " + string(content[n:]))
result = append(result, content[n:]...)

stdout

content: Hello, World!
result: Hello, yuzuy
content: Hello, yuzuy!
content[n:]: , yuzuy!
Hello, yuzuy, yuzuy!

content[n:]が期待している", World!"ではなく", yuzuy!"にcontentが"Hello, World!"ではなく"Hello, yuzuy!"に書き換わっていることがわかりました。

appendしただけでなぜでSliceの中身が書き換わってしまったのでしょうか？

appendの不思議な挙動の正体

Sliceの内部実装・仕様の簡単な説明

この現象を説明するにはSliceの内部実装を知る必要があります。

内部実装に関してはtenntennさんの実装して理解するスライス #golangという記事がわかりやすいのでこれを参照することをおすすめします。

Sliceは固定長配列(Array)の参照型です。参照型というよりWrapperという言い方のほうがわかりやすいかもしれません。
Sliceの内部実装は以下のようになっています。

slice.go

type slice struct {
	array unsafe.Pointer
	len   int
	cap   int
}

ref: https://github.com/golang/go/blob/master/src/runtime/slice.go

arrayというフィールドには基底配列と呼ばれるSliceの元となるArrayのポインタが入っています。
lenはSliceの、capは基底配列の要素数です。
以下のようなコードでSliceから基底配列を取得することができます。

https://play.golang.org/p/3pn53WOu0IR

func main() {
	slice := []int{1, 2, 3}
	sliceHeader := (*reflect.SliceHeader)(unsafe.Pointer(&slice))
	// reflect.SliceHeaderはruntimeパッケージのsliceの内部構造を表現するため型で
	// slice.array -> SliceHeader.Data
	// slice.len   -> SliceHeader.Len
	// slice.cap   -> SliceHeader.Cap
	// という対応になっています。
	fmt.Printf("%#v\n", sliceHeader)

	underlyingArray := (*[3]int)(unsafe.Pointer(sliceHeader.Data))
	fmt.Printf("基底配列: %#v\n", underlyingArray)
}

上記のコードではSliceを[]int{}のように初期化すると要素数と同じ長さの基底配列が作られ、slice.arrayにそのポインタが格納されることがわかると思います。

Slicing

一番最初のコードではbyte列を分割するのにSlicingを使っていました。
content[:n]やcontent[n:]ですね。

Slicingを使うとSliceやArrayから範囲を指定して切り出すことができますが、切り出されたSliceの基底配列は切り出し元のSliceのものと同じになります。

なので切り出されたSliceの要素に代入すると切り出し元のSliceの要素にも影響を及ぼします。

https://play.golang.org/p/q3HQHi1KAg6

func main() {
	slice := []int{1, 2, 3}
	slice2 := slice[1:]
	slice2[0] = 9
	fmt.Println(slice)  // [1, 9, 3]
	fmt.Println(slice2) // [9, 3]
}

appendの仕様

appendはSliceに要素を追加するための組み込み関数です。
Sliceは固定長配列の参照型ですがappendはどのようにして実装されているのでしょうか。

slice := []int{1, 2, 3}
// @1
slice = append(slice, 4)
// @2

というコードがある場合
@1ではsliceのlen,capはともに3ですが、@2ではlenが4、capが6となっています。

appendするとsliceの要素数は4となり要素数3の固定長配列である基底配列に入り切らなくなってしまいます。
なのでGoは新たに4より長い固定長配列を作ってSliceの参照する基底配列のポインタを入れ替えるという処理を行います。
以下のコードを実行すればポインタが変わっていることがわかると思います。

https://play.golang.org/p/BiOa1onRqxH

func main() {
	slice := []int{1, 2, 3}
	sliceHeader := (*reflect.SliceHeader)(unsafe.Pointer(&slice))
	fmt.Printf("%#v\n", sliceHeader)

	slice2 := append(slice, 4)
	sliceHeader = (*reflect.SliceHeader)(unsafe.Pointer(&slice2))
	fmt.Printf("%#v\n", sliceHeader)

	// 基底配列が違うのでsliceには影響がない	
	slice2[0] = 0
	fmt.Println(slice)
}

capが6になっているのはメモリを確保する回数を減らすためで、元のcapが1024未満だと元のcap*2が、1024以上だと元のcapにその1/4を加算した分が新規capとして確保されます。

capが足りている場合は基底配列は再作成されず、基底配列の要素に代入される形になります。
例えば上記のmain関数の末尾に

slice = append(slice, 5)
sliceHeader = (*reflect.SliceHeader)(unsafe.Pointer(&slice))
fmt.Printf("%#v\n", sliceHeader)

というコードを追加しても2番目と3番目に出力されるSliceHeader.Dataの値は変わらないです。

サンプルコード
https://play.golang.org/p/rI_EnTkvZMl

つまりappendを一言で表すならば「基底配列に代入する場所あったら代入するけどなかったら新しく基底配列つくるよくん」です。

仕様を知ると見えてくるバグの正体

このバグは

• Slicingで切り出したSliceの基底配列は切り出し元と同じ
• appendは基底配列に代入する場所あったら代入するけどなかったら新しく基底配列つくる

という2つの仕様と

• コマンドライン引数で渡されたN+Sの長さがcontentの基底配列の長さより短かった

という状況が重なり合って起きました。

---

main.go

// n = 5
// s = ", yuzuy"
content, _ := io.ReadAll(f)
result := append(content[:n], []byte(s)...)
result = append(result, content[n:]...)

まず1つ目のappendではcontent[:n]の後に代入できる場所があるかどうか調べます。

io.ReadAllの直後にcap(content)を出力するとcontentの基底配列の長さは512だということがわかります。
sを代入するための十分な場所があります。

appendはその場所に値が入っているとか関係なしに容赦なく代入します。
"Hello, World!"の5文字目以降、7文字分", World"が上書かれ、contentが"Hello, yuzuy!"に変わります。

そしてcontent[n:]ではcontentの5文字目以降が切り出されるので", yuzuy!"。
resultは"Hello, yuzuy, yuzuy!"となるわけです。

このバグの注意すべき点

注意すべきなのはNとSの長さを足した値が挿入する対象のバイト列のcap以上だった場合、新たに基底配列が作られるためこのバグが発生しないという点です。

今回の例ではio.ReadAllを使ったためcapが最低でも512は確保されていましたが、単純に文字列"Hello, World!"をバイト列化した場合は13しかcapが確保されずバグが見落とされやすいです。

バグが発生しないケース
https://play.golang.org/p/n0ZcLhJZriQ

対処法

実は公式Wikiに答えが書いてありました(教えてくださったbudougumi0617さんに感謝)。

https://play.golang.org/p/CuVwXjuXBUA

result := append(content[:n], append([]byte(s), content[n:]...)...)

のようにすることで回避することができます。
append完全理解した読者のみなさんならなぜこれで回避できるのかわかるはずです！

あとがき

筆者もSliceがArrayの参照であるというのは知っていましたが、このバグは反直感的というかappendの挙動が予想外で原因を特定するのに少し時間がかかってしまいました(その分とても勉強になったので結果オーライというやつです)。

筆者自身そこまでGoの内部実装等に詳しくないので間違っているところがあれば指摘していただけると幸いです。

この記事で少しでも皆さんのデバッグ時間削減に貢献できたら嬉しいです。

今後も技術発信していくのでよければTwitterフォローお願いします！

参考

• The Go Programming Language Specification
• SliceTricks · golang/go Wiki
• 実装して理解するスライス #golang
• 【Go】appendで新しく配列が割り当てられる際にどれくらいcapが確保されるか知っていますか？