GoのHTTP実装を読んだ知見をまとめる~Slice編~

# はじめに
業務での調査がきっかけにGoの[HTTP実装](https://github.com/golang/go/tree/master/src/net/http)を最近読み続けていて、やっとhttp実装の流れが大まかに理解できるようになった。

割と勉強になったことが多いのでその知見を複数回に分けて知見をまとめていく。
HTTP実装自体は意外にもかなり複雑なものとなっており、文面で説明づらいので、どちらかというと実装を理解した知見を汎化して書きたい。HTTP実装も紹介しやすい部分は適宜書きたい。

GoのHTTP実装とは、クライアントとサーバ両方含む。
TLS関連の処理やHTTP/2の実装は完全に読み飛ばしているので全く理解していない。HTTP1.0、HTTP1.1を対象とする。

初回はスライスである。

# GoのSlice

GoのSliceはゼロ値がnilなので内部構造としてはポインタであるように思いがちであるが、**構造体**である。以下がその定義である。

[定義](https://github.com/golang/go/blob/59bfc18e3441d9cd0b1b2f302935403bbf52ac8b/src/runtime/slice.go#L13-L17)

```golang

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

要するに、sliceは

* len
* cap
* 配列のポインタ

の３組からなる。
これは図で理解するのが良いが、[既に丁寧な説明や解説がある](
https://qiita.com/tenntenn/items/5229bce80ddb688a708a)ので、そちらを参照してここでは省略する。

大事なことは、「sliceはポインタでなく構造体だ」と理解するのではなく、sliceはsliceであり、既出の3組からなることをちゃんと覚えておかないといけないということだ。

例えば、以下の挙動はsliceをちゃんと理解していない人には不思議な挙動になると思う。

最初の`s = append(s, 4)`のちに明示的に`s = append(s, 4)`しなくてはいけないのを簡単に説明すると、appendした直後のsmap["a"]の構造体は以下のようになっているためである。

* len = 3 (4ではない)
* cap = 4
* 配列のポインタは「1,2,3,4」をさす

mapのvalueとしてsliceがある場合は常に明示的にvalueを更新しないといけない。

```golang

package main

import "fmt"

func main() {
	// len=0 cap=4
	s := make([]int, 0, 4)
	s = append(s, 1, 2, 3)

	smap := map[string][]int{
		"a": s,
	}
	// 	1,2,3
	fmt.Println(smap["a"])

	s = append(s, 4)

	// 	1,2,3
	fmt.Println(smap["a"])

	// We must write explicitly
	smap["a"] = s
	// 	1,2,3,4
	fmt.Println(smap["a"])

	s[0] = 0
	// 0,2,3,4
	// We write implicitly
	fmt.Println(smap["a"])

	s = s[:1]
	// 0,2,3,4
	fmt.Println(smap["a"])

	// We must write explicitly
	smap["a"] = s
	// 0
	fmt.Println(smap["a"])
}
```

# HTTP実装

上記のmapの説明の元ネタは実は
[src/net/http/transport.goでmapのvalueであるキューを更新するときのコメント](https://github.com/golang/go/blob/59bfc18e3441d9cd0b1b2f302935403bbf52ac8b/src/net/http/transport.go#L1488-L1490)である。

繰り返しになるが、mapのvalueがsliceの場合は更新した場合は明示的に上書きしなければいけない。なお、このconnsPerHostWaitのキューの実装は興味深いので別記事で紹介する。


```golang


			// q is a value (like a slice), so we have to store
			// the updated q back into the map.
			t.connsPerHostWait[key] = q

```

ここではさらに、Chunked_transfer_encodingのReadの実装を参考にする。なお、Chunked_transfer_encoding自体の説明はここでは省略するが、実装の流れを掴むためにも[wikiepediaの例](https://en.wikipedia.org/wiki/Chunked_transfer_encoding)を引用する。

>Encoded data
In the following example, three chunks of length 4, 6 and 14 (hexadecimal "E") are shown. The chunk size is transferred as a hexadecimal number followed by \r\n as a line separator, followed by a chunk of data of the given size.

```

4\r\n (bytes to send)
Wiki\r\n (data)

6\r\n (bytes to send)
pedia \r\n (data)

E\r\n (bytes to send)
in \r\n
\r\n
chunks.\r\n (data)

0\r\n (final byte - 0)
\r\n (end message)
```

>Decoded data

```
Wikipedia in

chunks.
```


https://github.com/golang/go/blob/59bfc18e3441d9cd0b1b2f302935403bbf52ac8b/src/net/http/internal/chunked.go#L23-L115
に実装があります。以下、適宜コメントを追記します。


```golang

func NewChunkedReader(r io.Reader) io.Reader {
	br, ok := r.(*bufio.Reader)
	if !ok {
		br = bufio.NewReader(r)
	}
	return &chunkedReader{r: br}
}

type chunkedReader struct {
	r        *bufio.Reader
	n        uint64 // unread bytes in chunk
	err      error
	buf      [2]byte
	checkEnd bool // whether need to check for \r\n chunk footer
}

// beginChunkは例での
// 4\r\n (bytes to send)
// を読み込む部分です
func (cr *chunkedReader) beginChunk() {
	// chunk-size CRLF
	var line []byte
    // readChunkLineは引数の*bufio.Readerから\nまで読みます
	line, cr.err = readChunkLine(cr.r)
	if cr.err != nil {
		return
	}
    // 例でいうところの4
	cr.n, cr.err = parseHexUint(line)
	if cr.err != nil {
		return
	}
    // 終わりを意味する
	if cr.n == 0 {
		cr.err = io.EOF
	}
}

// バッファに既にあり、\nが含まれている場合のみtrueを返却します
func (cr *chunkedReader) chunkHeaderAvailable() bool {
	n := cr.r.Buffered()
	if n > 0 {
		peek, _ := cr.r.Peek(n)
		return bytes.IndexByte(peek, '\n') >= 0
	}
	return false
}

func (cr *chunkedReader) Read(b []uint8) (n int, err error) {
	for cr.err == nil {
		if cr.checkEnd {
			if n > 0 && cr.r.Buffered() < 2 {
				// We have some data. Return early (per the io.Reader
				// contract) instead of potentially blocking while
				// reading more.
				break
			}
            // 例でいうと、Wiki\r\nの\r\nを読もうとします 
			if _, cr.err = io.ReadFull(cr.r, cr.buf[:2]); cr.err == nil {
				if string(cr.buf[:]) != "\r\n" {
					cr.err = errors.New("malformed chunked encoding")
					break
				}
			}
			cr.checkEnd = false
		}
		if cr.n == 0 {
            // 呼び出すとblockされそうであれば追加でreadせずに結果を返してしまいます。
			if n > 0 && !cr.chunkHeaderAvailable() {
				// We've read enough. Don't potentially block
				// reading a new chunk header.
				break
			}
			cr.beginChunk()
			continue
		}
		if len(b) == 0 {
			break
		}
		rbuf := b
		if uint64(len(rbuf)) > cr.n {
			rbuf = rbuf[:cr.n]
		}
		var n0 int
        // 例でいうと、rbufにWikiだけが格納されるように調整されてます
		n0, cr.err = cr.r.Read(rbuf)
		n += n0
        // rbufにデータが格納されますが、bと配列のポインタを共有しているため、結果的に引数のbにもデータが格納されています
		b = b[n0:]
		cr.n -= uint64(n0)
		// If we're at the end of a chunk, read the next two
		// bytes to verify they are "\r\n".
		if cr.n == 0 && cr.err == nil {
			cr.checkEnd = true
		}
	}
	return n, cr.err
}
```

Sliceとは関係ないですが、blockされそうであれば無理に読まずにReturnしてしまう工夫が面白いですね。Chunked_transfer_encodingの場合はチャンクとチャンクの間(例えばWikiとpedia)に受信のタイムラグがあることもあるでしょう。

Slice関連でいうと、この実装を初見でちゃんと動いていると理解するのは慣れが必要な気がします。`cr.r.Read(rbuf)`のように長さを期待するものに調整したものにするのも参考になりますね。

改めて思いましたが、Readのinterfaceがそもそも引数にデータを格納する形となるので`p`がポインタのように思ってしまうのも無理もないですね。


```golang

type Reader interface {
	Read(p []byte) (n int, err error)
}
```


# おわりに
SliceはGoの中で一番使いこなすのが難しいと思ってます。
さらなる説明としては以下が参考になるかと思います。


* [Arrays, slices (and strings): The mechanics of 'append'](https://blog.golang.org/slices)
* [SliceTricks](https://github.com/golang/go/wiki/SliceTricks)