実装して理解するスライス #golang

## はじめに

この記事は[Goアドベントカレンダー](https://qiita.com/advent-calendar/2018/go)の1日目の記事です。

## スライスの実態

[runtimeのコード](https://github.com/golang/go/blob/release-branch.go1.11/src/runtime/slice.go#L12-L16)をみるとGoのスライスは以下のように定義されています。

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

reflectパッケージの[SliceHeader](https://golang.org/pkg/reflect/#SliceHeader)を見ても次のような定義になっています。

```go
type SliceHeader struct {
        Data uintptr
        Len  int
        Cap  int
}
```

つまり、Goのスライスは次の図のように、配列へのポインタと長さと容量を持った値として表現されています。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/14952/3dd01697-9e62-6d22-92b2-3d6559c2391c.png)

runtimeと`reflect`パッケージでポインタが`unsafe.Pointer`と`uintptr`で表現方法は違いますが、どちらもポインタを表す値です。

`unsafe.Pointer`は任意型のポインタと相互変換可能な型です。一方で、`uintptr`は整数型で`unsafe.Pointer`に変換が可能な型です。`uintptr`は整数型の1つなので、`int`型などと同様に四則演算が可能です。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/14952/dbdea551-dec4-b712-0494-72020124087e.png)


次のように、`[]int`型を`reflect.SliceHeader`型として解釈してみます。
まず、`[]int`型の変数である`ns`のポインタを取り、`unsafe.Pointer`型に変換します。
変換した値は`ptr`という変数に入れています。
次に、`ptr`を`*reflect.Slice`型にキャストし、そのポインタが指す先の値を`reflect.SliceHeader`型の変数`s`に代入しています。

```go
package main

import (
	"fmt"
	"reflect"
	"unsafe"
)

func main() {
	ns := []int{10, 20, 30}
	// nsをunsafe.Pointerに変換する
	ptr := unsafe.Pointer(&ns)
	// ptrを*reflect.SliceHeaderにキャストして、それが指す値をsにいれる
	s := *(*reflect.SliceHeader)(ptr)
	fmt.Printf("%#v\n", s)
}
```

## 要素へのアクセス

`reflect.SliceHeader`を用いて`i`番目のスライスの要素にアクセス方法を考えて見ましょう。`reflect.SliceHeader`はスライスが参照している配列へのポインタを持っています。そのポインタは、スライスの0番目の要素を指すポインタです。

そのため、次の`at`関数のように、先頭へポインタから要素`i`個分のポインタを進めた場所が`i`番目の要素のポインタとなります。要素の型によって、1要素あたりどのくらいポインタを進めれば良いのかは違うため、次の例では`int`型の場合に限定しています。任意の型のサイズを取得するには、`unsafe.Sizeof`を用います。

```go
package main

import (
	"fmt"
	"reflect"
	"unsafe"
)

func at(s reflect.SliceHeader, i int) unsafe.Pointer {
	// 先頭ポインタ + インデックス * int型のサイズ
	return unsafe.Pointer(s.Data + uintptr(i)*unsafe.Sizeof(int(0)))
}

func main() {
	a := [...]int{10, 20, 30}
	s := reflect.SliceHeader{Data: uintptr(unsafe.Pointer(&a[0])), Len: 2, Cap: len(a)}
	*(*int)(at(s, 0)) = 100 // unsafe.Pointerを*intに変換して代入している
	fmt.Println(a)
}
```

## 要素の追加

ここで`append`関数のような機能を実装してみたいと思います。
`append`は追加する際に、スライスが参照している配列の容量が足りている場合と足りたない場合で挙動が異なるため、それぞれ考えてみます。

### 容量が足りる場合

容量が足りる場合は、単純に次の手順で要素の追加を行います。

* 新しい要素をコピーする
* 長さを更新する

```go
package main

import (
	"fmt"
	"reflect"
	"unsafe"
)

func at(s reflect.SliceHeader, i int) unsafe.Pointer {
	// 先頭ポインタ + インデックス * int型のサイズ
	return unsafe.Pointer(s.Data + uintptr(i)*unsafe.Sizeof(int(0)))
}

func myAppend(s reflect.SliceHeader, vs ...int) reflect.SliceHeader {
	// 新しい要素の追加
	for i := 0; i < len(vs); i++ {
		*((*int)(at(s, s.Len+i))) = vs[i]
	}
	return reflect.SliceHeader{Data: s.Data, Len: s.Len + len(vs), Cap: s.Cap}
}

func main() {
	a := [...]int{10, 20, 30}
	// s := a[0:2] -> [10 20]
	s := reflect.SliceHeader{Data: uintptr(unsafe.Pointer(&a[0])), Len: 2, Cap: len(a)}
	s = myAppend(s, 400)

	var ns []int
	*(*reflect.SliceHeader)(unsafe.Pointer(&ns)) = s
	fmt.Println(ns)
}
```

### 容量が足りない場合

一方で、容量が足りない場合は、次のように配列の再確保を行う必要があります。

* 元のおよそ2倍の容量を確保しなおす
* 配列へのポインタを貼り直す
* 元の配列から要素をコピーする
* 新しい要素をコピーする
* 長さと容量を更新する

この手順でスライスのサイズを拡張するための関数`growslice`を実装すると次のようになります。そして、`myAppend`内で容量が足りない場合に`growslice`を呼んでやることでスライスを拡張してやることができます。

```go
package main

import (
	"fmt"
	"reflect"
	"unsafe"
)

func at(s reflect.SliceHeader, i int) unsafe.Pointer {
	// 先頭ポインタ + インデックス * int型のサイズ
	return unsafe.Pointer(s.Data + uintptr(i)*unsafe.Sizeof(int(0)))
}

func myAppend(s reflect.SliceHeader, vs ...int) reflect.SliceHeader {
	// 容量が足りない場合
	if s.Len+len(vs) > s.Cap {
		s = growslice(s, s.Len+len(vs))
	}

	// 新しい要素の追加
	for i := 0; i < len(vs); i++ {
		*((*int)(at(s, s.Len+i))) = vs[i]
	}
	return reflect.SliceHeader{Data: s.Data, Len: s.Len + len(vs), Cap: s.Cap}
}

func growslice(old reflect.SliceHeader, cap int) reflect.SliceHeader {
	newcap := cap
	doublecap := old.Cap + old.Cap
	if cap < doublecap {
		newcap = doublecap
	}

	s := make([]int, old.Len, newcap)
	newslice := *(*reflect.SliceHeader)(unsafe.Pointer(&s))

	// 古いスライスから要素のコピー
	for i := 0; i < old.Len; i++ {
		*((*int)(at(newslice, i))) = *((*int)(at(old, i)))
	}

	return newslice
}

func main() {
	a := [...]int{10, 20, 30}
	// s := a[0:2] -> [10 20]
	s := reflect.SliceHeader{Data: uintptr(unsafe.Pointer(&a[0])), Len: 2, Cap: len(a)}
	s = myAppend(s, 400, 500) // 溢れる

	var ns []int
	*(*reflect.SliceHeader)(unsafe.Pointer(&ns)) = s
	fmt.Println(ns)
}
```

ここで注意したいのは、`myAppend`の戻り値が`reflect.SliceHeader`という点です。要素の追加が行われた場合、少なくとも長さは更新されるため、戻り値として返す必要があります。

これは`reflect.SliceHeader`型は構造体のため、引数で受け取った値のフィールドをいくら変更しても呼び出し元に影響がないからです。例えば、次の例を見てみると`s2.Len`を変更しても`s1.Len`に影響がないことが分かります。

```go
func main() {
	a := [...]int{10, 20, 30}
	s1 := reflect.SliceHeader{Data: uintptr(unsafe.Pointer(&a[0])), Len: 2, Cap: len(a)}
	s2 := s1
	s2.Len = 3 // s1には影響ない

	fmt.Println(s1) // {4310908 2 3}
	fmt.Println(s2) // {4310908 3 3}
}
```

## おわりに

この記事では、スライスがどのように表現されているかを調べ、スライスに関数する処理を実際に実装するとことで、スライスを理解することを試みました。

なお、ここで扱った`unsafe.Pointer`は次の例のように扱い方を間違えると大変危険なので、ご注意ください。

```go
func main() {
	v := struct {
		a [5]int
		b [2]int
	}{
		a: [...]int{10, 20, 30, 40, 50},
		b: [...]int{100, 200},
	}
	
	// capがlen(a)より大きい
	s := reflect.SliceHeader{Data: uintptr(unsafe.Pointer(&v.a[1])), Len: 2, Cap: 6}
	var ns []int
	*(*reflect.SliceHeader)(unsafe.Pointer(&ns)) = s

	// aを超えてappend
	ns = append(ns, 60, 70, 80)
	fmt.Println(ns, v.a, v.b)
}
```