🙂

[Go] strings.Builderの内部仕様を見ていこう！

2024/12/19に公開

string

tech

概要

私はよくGoのstrings.Builderをよく使うのですが、
中身がどうなっているのかふと気になったので調べてみました。
コードはGo公式のリポジトリから引用します。

基礎知識

そもそもstrings.Builderというのは、stringsパッケージに定義されている文字列を扱うための構造体で、
内部でバッファを持っているためメモリコピーが最小限に抑えられている。
なのでこれを使えば += などを使うよりかなり高速に文字列を連結できる。
さらにstring型だけでなくrune型やbyte型からも文字列を連結し生成できる優れものとなっています。

strings.Builder構造体

何はともあれ見ていきましょう。

import (
    "strings"
)

func main() {
    var sb strings.Builder
}

まずstrings.Builderを使うときに上記のように変数をstrings.Builder型で定義することになると思います。

この構造体の内部はこのようになっています。

go/src/strings/builder.go

type Builder struct {
	addr *Builder
	buf []byte
}

addrフィールドは自分自身のポインタ型で定義されています。

bufフィールドはただのbyte型のスライスになっていて
詳しくは後述しますがstring型またはrune型で入ってきた値はbyte型にキャストされこのbufにappend関数で格納されているようです。

次からはメソッド及びそれに関係する関数を見ていきます。

WriteString

WriteStringは引数の文字列をバフに格納するメソッド。
例

import (
    "strings"
)

func main() {
    var sb strings.Builder
    sb.WriteString("バフに格納される文字列")
}

内部は全然難しくなくシンプルになっています。

go/src/strings/builder.go

func (b *Builder) WriteString(s string) (int, error) {
	b.copyCheck()
	b.buf = append(b.buf, s...)
	return len(s), nil

まずcopyCheckメソッドが動き(後述)引数で渡されたstring型のsが...でアンパックされビルトイン関数のappendを使ってBuilder構造体で定義されたbufに格納されていて、
そんでもってsの長さとnilを返しています。
※ちなみに文字列は後置...演算子をつけると[]byte型にキャストされる

Write

例

import (
    "strings"
)

func main() {
    var sb strings.Builder
    byteSlice := []byte("byte")
    sb.Write(byteSlice)
}

WriteStringメソッドとあまり変わりません。

go/src/strings/builder.go

func (b *Builder) Write(p []byte) (int, error) {
	b.copyCheck()
	b.buf = append(b.buf, p...)
	return len(p), nil
}

ここのの
copyCheckメソッドが動き、引数で渡された[]byte型のpが...でアンパックされappendを使ってbufに格納されていて、
そんでもってpの長さとnilを返しています。

WriteByte

例

import (
    "strings"
)

func main() {
    var sb strings.Builder
	var b byte = 115
	sb.WriteByte(b)
}

これもあまり変わりません

go/src/strings/builder.go

func (b *Builder) WriteByte(c byte) error {
	b.copyCheck()
	b.buf = append(b.buf, c)
	return nil
}

入力する引数が[]byte型ではなくbyte型単体になっています。
スライスではないので戻り値に引数の長さも返さなくなっている。

WriteRune

やっと少し変化が出てくる。
このメソッドはrube型の文字をbufに格納する。
例

import (
    "strings"
)

func main() {
    var sb strings.Builder
	var r rune = 'a'
	sb.WriteRune(r)
}

※シングルクオーテーション[']で囲むと文字はrune型になる。

go/src/strings/builder.go

func (b *Builder) WriteRune(r rune) (int, error) {
	b.copyCheck()
	n := len(b.buf)
	b.buf = utf8.AppendRune(b.buf, r)
	return len(b.buf) - n, nil
}

まずcopyCheck()メソッドが動きbufの長さをnに格納、その次にunicode/utf8パッケージのAppendRune関数が使われています。
戻り値としては最終的なbufのバイト数からruneをappendする前のbufバイト数を引いたもの、
つまり入力したruneのみのバイト数を返しています。
それとnil。
utf8.AppendRuneの内部実装は本記事の趣旨から少し外れるので
興味のない方は飛ばしてください。

utf8.AppendRuneの内部実装

utf8.AppendRuneはunicode/utf8パッケージのutf8.goに定義されている関数です。
中身としてはこのようになっています。

go/src/unicode/utf8/utf8.go

func AppendRune(p []byte, r rune) []byte {	
	if uint32(r) <= rune1Max {
		return append(p, byte(r))
	}
	return appendRuneNonASCII(p, r)
}

rune型は文字を10進数のUnicodeのコードポイント^[1]で表します。

用語	解説
Unicode	文字からコードポイントにする対応表
コードポイント	文字それぞれに割り当てられた番号
UTF-8	コードポイントから符号化する方式の一つ(SHIFT-JISなどもそう)
符号化	コンピューターが理解できる数字に変換すること

そのrune型のrがif文の条件式の中でuint32にキャストされています。
uint32は32ビットの符号なし整数^[2]を表しているので、
ここで負数かどうか判定しているのでしょう(Unicodeのコードポイントに負数はない)。
そして第二引数の変数rをrune1Maxとかいうものと比較していますがこれは定数で下記のように定義されています。

const rune1Max = 1<<7 - 1

これは整数1を7ビット左シフトしてその答えを-1して127となるので、
このif式はrが0~127の間、つまりASCII文字であればtrueとします^[3]。
それから変数rをbyte型にキャストして第一引数の[]byte型の変数pにappend関数で格納しています。
falseであれば何やら謎のappendRuneNonASCII()とかいう関数に飛んでいます。

appendRuneNonASCII

名前の通りASCII文字ではない入力を判定する関数です。
中身は下記のような感じです。

go/src/unicode/utf8/utf8.go

func appendRuneNonASCII(p []byte, r rune) []byte {
	switch i := uint32(r); {
	case i <= rune2Max:
		return append(p, t2|byte(r>>6), tx|byte(r)&maskx)
	case i > MaxRune, surrogateMin <= i && i <= surrogateMax:
		r = RuneError
		fallthrough
	case i <= rune3Max:
		return append(p, t3|byte(r>>12), tx|byte(r>>6)&maskx, tx|byte(r)&maskx)
	default:
		return append(p, t4|byte(r>>18), tx|byte(r>>12)&maskx, tx|byte(r>>6)&maskx, tx|byte(r)&maskx)
	}
}

まず第二引数の変数rをuint32型にし符号なし整数にして変数iに格納しrune2Maxなるものと比較しています。
これもお察しの通り定数で下記のように定義されています。

go/src/unicode/utf8/utf8.go

const rune2Max = 1<<11 - 1

1を11ビット左シフトして-1すると2047となります。
Unicode文字はコードポイントが128~2047までは2バイト文字となるのでその判定のためでしょう。
つまり引数rが128~2047までの間だったら条件の範囲内となっています。
その次に何やら謎の値をappendしています。

go/src/unicode/utf8/utf8.go

case i <= rune2Max:
	return append(p, t2|byte(r>>6), tx|byte(r)&maskx)

このappendの第二引数第三引数にt2, 論理和計算したものをいう謎の変数がありますが、これらはunicode/utf8のファイル内で下記のようバイトスライスにして

go/src/unicode/utf8/utf8.go

const (
	t1 = 0b00000000
	tx = 0b10000000
	t2 = 0b11000000
	t3 = 0b11100000
	t4 = 0b11110000
	t5 = 0b11111000

	maskx = 0b00111111
	mask2 = 0b00011111
	mask3 = 0b00001111
	mask4 = 0b00000111
)

まず変数t2には0b11000000と格納されています・
0bという接頭辞は二進数を表すので、t2は二進数11000000となります。
そのt2とbyte型に変換した引数rを右に6ビットシフトしたものの論理和を計算しています。
第三引数ではtxとbyte型のrを論理和計算したものをmaskxと論理積計算しています。
こうすることで二バイト文字がrune型で入ってきたときに正しく二つのバイトスライスに変換して
[]byte型の引数pにappendすることができます。
検証としてこのようなコードを書きました。

main.go

var bs []byte
twoByteRune := 'ߐ'
bs = utf8.AppendRune(bs, twoByteRune)
fmt.Println("original string:", string(bs), "string to []byte:", []byte("ߐ"),"use AppendRune:", bs)

実行してみます。

bash

$ go run main.go
original string: ߐ string to []byte: [223 144] use AppendRune: [223 144]

上記のようにAppendRuneで[]byte型の変数に格納したものと、直接[]byte()関数でキャストしたもののバイト列が同じになっています。

2つ目のcaseは下記のようになっています。

go/src/unicode/utf8/utf8.go

case i > MaxRune, surrogateMin <= i && i <= surrogateMax:
	r = RuneError
	fallthrough

これはまず入力された文字がMaxRuneより大きい、もしくはsurrogateMinより同じか大きいかつsurrogateMaxより同じか小さければRuneErrorをrに格納しfallthroughで一つ下のcaseに移動しています。
MaxRuneなどは下記の様に定義されています。
※他にも定義されている定数はありますが今回の話題と関係ないので敢えて載せていません。

go/src/unicode/utf8/utf8.go

const (
	RuneError = '\uFFFD'     // the "error" Rune or "Unicode replacement character"
	MaxRune   = '\U0010FFFF' // Maximum valid Unicode code point.
)

const (
	surrogateMin = 0xD800
	surrogateMax = 0xDFFF
)

定数RuneErrorに格納されている'\uFFFD'は有効Unicode範囲外の文字を表すのに使われます。
定数MaxRuneは有効Unicodeコードポイントの最大値です。

その下のsurrogateMinとsurrogateMaxはサロゲートペアと呼ばれるものの最大値と最小値で
詳しくは長くなってしまうので控えますが簡単に書くと後々追加された文字のことです(Zennの記事のアイコンのような絵文字など)。

それらのエラー処理を回避した後

go/src/unicode/utf8/utf8.go

case i <= rune3Max:
return append(p, t3|byte(r>>12), tx|byte(r>>6)&maskx, tx|byte(r)&maskx)

先ほどの2バイト文字と同じように3バイトをappendしています。

どの条件にも満たなかった場合(4バイト文字であった場合)下記のような条件で評価されます。

go/src/unicode/utf8/utf8.go

default:
    return append(p, t4|byte(r>>18), tx|byte(r>>12)&maskx, tx|byte(r>>6)&maskx, tx|byte(r)&maskx)

これも先ほどの2バイト、3バイト文字のような方法でappendされています。

utf8.AppendRuneはこのような実装がされていました。

copyCheck

先ほどから出ているcopyCheck関数ですが、下記の様な実装になっています。

go/src/strings/builder.go

func (b *Builder) copyCheck() {
	if b.addr == nil {
		b.addr = (*Builder)(abi.NoEscape(unsafe.Pointer(b)))
	} else if b.addr != b {
		panic("strings: illegal use of non-zero Builder copied by value")
	}
}

まずBuilder構造体のaddrフィールドがnil、つまりメソッドの引数がの値がなかったら、unsafe.Pointerで*Builder型のアドレスを直接読み込みabi.NoEscape関数を使ってポインタの不変性を維持して、それからBuilder型のポインタ型にキャストしています。

unsafeパッケージはとても高速ですがポインタを直接読み込むなど危険な処理をするので慎重な運用が推奨されるパッケージです。

abiパッケージはinternalなのでローカルのgoプログラムにはimportできません
importしようとすると"use of internal package internal/bytealg not allowed"というエラーが発生します。(裏技的な方法でimportする方法があった気もしますが忘れました)

Len Cap

Lenメソッドの例

var sb strings.Builder
sb.WriteString("sb")
fmt.Println(sb.Len())// output: 2
}

Lenメソッドの内部は下記のようになっています・

go/src/strings/builder.go

func (b *Builder) Len() int { return len(b.buf) }

かなり短いですね、
LenメソッドはWrite**メソッドによってBuilder構造体のbufフィールドに格納された値のバイト数を返しています。

Capメソッドの例

var sb strings.Builder
sb.WriteString("s")
fmt.Println(sb.Cap())// output: 8

Capメソッドの内部は下記のようになっています・

go/src/strings/builder.go

func (b *Builder) Cap() int { return cap(b.buf) }

これもかなり短いですね、
CapメソッドはWrite**メソッドによってBuilder構造体のbufフィールドに格納された値の容量を返しています。
最初の容量は0次に8,16,32,64と倍増していきます。

Reset

Resetメソッドの例

import (
    "strings"
    "fmt"
)
func main() {
    var sb strings.Builder
    sb.WriteString("a")
    fmt.Println(sb.String())// output: a
    sb.Reset()
    fmt.Println(sb.String()) // output: ""(空文字列)
}

Resetメソッドの内部は下記のようになっています。

go/src/strings/builder.go

func (b *Builder) Reset() {
	b.addr = nil
	b.buf = nil
}

Builder構造体のフィールドaddrとbufにnilを格納しているだけです。

Grow

Growメソッドは引数の数値分bufにメモリを割り当てるメソッドです。
make関数に少し似ていますね。
Growメソッドの例

import (
    "strings"
    "fmt"
)
func main() {
    var sb strings.Builder
    sb.Grow(2)
    fmt.Println(sb.Cap())// output: 8
}

※2しか追加していないのに容量が8になっているのは、内部のbufが[]byte型なので最初は容量が8追加されてそれから倍ずつ増えていきます。
Growメソッドの内部は下記のようになっています。

go/src/strings/builder.go

func (b *Builder) Grow(n int) {
	b.copyCheck()
	if n < 0 {
		panic("strings.Builder.Grow: negative count")
	}
	if cap(b.buf)-len(b.buf) < n {
		b.grow(n)
	}
}

まずcopyCheck関数が動いたあと引数が負数かどうか判定し負数だったらpanicを起こします。

その後元々持っていた容量から元々の長さを引いたものが引数nより小さかったらgrowメソッドが動きます。

grow

この関数はprivateなためstringsパッケージをimportしても使うことはできないメソッドです。

内部は下記のようになっています。

go/src/strings/builder.go

func (b *Builder) grow(n int) {
	buf := bytealg.MakeNoZero(2*cap(b.buf) + n)[:len(b.buf)]
	copy(buf, b.buf)
	b.buf = buf
}

internalのbytealgパッケージのMakeNoZero関数を使って現在のbufの2倍の容量と引数nのスライスを作成、その後bufの長さ分の容量を作成しています。
そして作成したスライスにbufの要素をコピーした後bufに代入することで新しく作成したスライスの容量と要素にbufを置き換えています。

コード引用

脚注

コードポイントは文字それぞれに割り当てられた番号のこと ↩︎
32ビット符号なし整数は0~4294967295まで ↩︎
コードポイントが0~127なのはASCII文字 ↩︎

概要

基礎知識

strings.Builder構造体

WriteString

Write

WriteByte

WriteRune

appendRuneNonASCII

copyCheck

Len Cap

Reset

Grow

grow

コード引用

Discussion