From 37b056948d058679efa4e87fb6c9b2a2ddfa31a3 Mon Sep 17 00:00:00 2001 From: Caleb Spare Date: Tue, 31 Oct 2017 16:51:21 -0700 Subject: [PATCH] strings: add Builder This is like a write-only subset of bytes.Buffer with an allocation-free String method. Fixes #18990. Change-Id: Icdf7240f4309a52924dc3af04a39ecd737a210f4 Reviewed-on: https://go-review.googlesource.com/74931 Run-TryBot: Caleb Spare TryBot-Result: Gobot Gobot Reviewed-by: Brad Fitzpatrick --- src/strings/builder.go | 120 +++++++++++++++ src/strings/builder_test.go | 282 ++++++++++++++++++++++++++++++++++++ src/strings/example_test.go | 11 ++ 3 files changed, 413 insertions(+) create mode 100644 src/strings/builder.go create mode 100644 src/strings/builder_test.go diff --git a/src/strings/builder.go b/src/strings/builder.go new file mode 100644 index 0000000000..594f3db513 --- /dev/null +++ b/src/strings/builder.go @@ -0,0 +1,120 @@ +// Copyright 2017 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package strings + +import ( + "errors" + "io" + "unicode/utf8" + "unsafe" +) + +// A Builder is used to efficiently build a string using Write methods. +// It minimizes memory copying. The zero value is ready to use. +type Builder struct { + buf []byte +} + +// String returns the accumulated string. +func (b *Builder) String() string { + return *(*string)(unsafe.Pointer(&b.buf)) +} + +// Len returns the number of accumulated bytes; b.Len() == len(b.String()). +func (b *Builder) Len() int { return len(b.buf) } + +// Reset resets the Builder to be empty. +func (b *Builder) Reset() { b.buf = nil } + +const maxInt = int(^uint(0) >> 1) + +// grow copies the buffer to a new, larger buffer so that there are at least n +// bytes of capacity beyond len(b.buf). +func (b *Builder) grow(n int) { + buf := make([]byte, len(b.buf), 2*cap(b.buf)+n) + copy(buf, b.buf) + b.buf = buf +} + +// Grow grows b's capacity, if necessary, to guarantee space for +// another n bytes. After Grow(n), at least n bytes can be written to b +// without another allocation. If n is negative, Grow panics. +func (b *Builder) Grow(n int) { + if n < 0 { + panic("strings.Builder.Grow: negative count") + } + if cap(b.buf)-len(b.buf) < n { + b.grow(n) + } +} + +// Write appends the contents of p to b's buffer. +// Write always returns len(p), nil. +func (b *Builder) Write(p []byte) (int, error) { + b.buf = append(b.buf, p...) + return len(p), nil +} + +// WriteByte appends the byte c to b's buffer. +// The returned error is always nil. +func (b *Builder) WriteByte(c byte) error { + b.buf = append(b.buf, c) + return nil +} + +// WriteRune appends the UTF-8 encoding of Unicode code point r to b's buffer. +// It returns the length of r and a nil error. +func (b *Builder) WriteRune(r rune) (int, error) { + if r < utf8.RuneSelf { + b.buf = append(b.buf, byte(r)) + return 1, nil + } + l := len(b.buf) + if cap(b.buf)-l < utf8.UTFMax { + b.grow(utf8.UTFMax) + } + n := utf8.EncodeRune(b.buf[l:l+utf8.UTFMax], r) + b.buf = b.buf[:l+n] + return n, nil +} + +// WriteString appends the contents of s to b's buffer. +// It returns the length of s and a nil error. +func (b *Builder) WriteString(s string) (int, error) { + b.buf = append(b.buf, s...) + return len(s), nil +} + +// minRead is the minimum slice passed to a Read call by Builder.ReadFrom. +// It is the same as bytes.MinRead. +const minRead = 512 + +// errNegativeRead is the panic value if the reader passed to Builder.ReadFrom +// returns a negative count. +var errNegativeRead = errors.New("strings.Builder: reader returned negative count from Read") + +// ReadFrom reads data from r until EOF and appends it to b's buffer. +// The return value n is the number of bytes read. +// Any error except io.EOF encountered during the read is also returned. +func (b *Builder) ReadFrom(r io.Reader) (n int64, err error) { + for { + l := len(b.buf) + if cap(b.buf)-l < minRead { + b.grow(minRead) + } + m, e := r.Read(b.buf[l:cap(b.buf)]) + if m < 0 { + panic(errNegativeRead) + } + b.buf = b.buf[:l+m] + n += int64(m) + if e == io.EOF { + return n, nil + } + if e != nil { + return n, e + } + } +} diff --git a/src/strings/builder_test.go b/src/strings/builder_test.go new file mode 100644 index 0000000000..df557082a7 --- /dev/null +++ b/src/strings/builder_test.go @@ -0,0 +1,282 @@ +// Copyright 2017 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package strings_test + +import ( + "bytes" + "errors" + "io" + "runtime" + . "strings" + "testing" + "testing/iotest" +) + +func check(t *testing.T, b *Builder, want string) { + t.Helper() + got := b.String() + if got != want { + t.Errorf("String: got %#q; want %#q", got, want) + return + } + if n := b.Len(); n != len(got) { + t.Errorf("Len: got %d; but len(String()) is %d", n, len(got)) + } +} + +func TestBuilder(t *testing.T) { + var b Builder + check(t, &b, "") + n, err := b.WriteString("hello") + if err != nil || n != 5 { + t.Errorf("WriteString: got %d,%s; want 5,nil", n, err) + } + check(t, &b, "hello") + if err = b.WriteByte(' '); err != nil { + t.Errorf("WriteByte: %s", err) + } + check(t, &b, "hello ") + n, err = b.WriteString("world") + if err != nil || n != 5 { + t.Errorf("WriteString: got %d,%s; want 5,nil", n, err) + } + check(t, &b, "hello world") +} + +func TestBuilderString(t *testing.T) { + var b Builder + b.WriteString("alpha") + check(t, &b, "alpha") + s1 := b.String() + b.WriteString("beta") + check(t, &b, "alphabeta") + s2 := b.String() + b.WriteString("gamma") + check(t, &b, "alphabetagamma") + s3 := b.String() + + // Check that subsequent operations didn't change the returned strings. + if want := "alpha"; s1 != want { + t.Errorf("first String result is now %q; want %q", s1, want) + } + if want := "alphabeta"; s2 != want { + t.Errorf("second String result is now %q; want %q", s2, want) + } + if want := "alphabetagamma"; s3 != want { + t.Errorf("third String result is now %q; want %q", s3, want) + } +} + +func TestBuilderReset(t *testing.T) { + var b Builder + check(t, &b, "") + b.WriteString("aaa") + s := b.String() + check(t, &b, "aaa") + b.Reset() + check(t, &b, "") + + // Ensure that writing after Reset doesn't alter + // previously returned strings. + b.WriteString("bbb") + check(t, &b, "bbb") + if want := "aaa"; s != want { + t.Errorf("previous String result changed after Reset: got %q; want %q", s, want) + } +} + +func TestBuilderGrow(t *testing.T) { + for _, growLen := range []int{0, 100, 1000, 10000, 100000} { + var b Builder + b.Grow(growLen) + p := bytes.Repeat([]byte{'a'}, growLen) + allocs := numAllocs(func() { b.Write(p) }) + if allocs > 0 { + t.Errorf("growLen=%d: allocation occurred during write", growLen) + } + if b.String() != string(p) { + t.Errorf("growLen=%d: bad data written after Grow", growLen) + } + } +} + +func TestBuilderWrite2(t *testing.T) { + const s0 = "hello 世界" + for _, tt := range []struct { + name string + fn func(b *Builder) (int, error) + n int + want string + }{ + { + "Write", + func(b *Builder) (int, error) { return b.Write([]byte(s0)) }, + len(s0), + s0, + }, + { + "WriteRune", + func(b *Builder) (int, error) { return b.WriteRune('a') }, + 1, + "a", + }, + { + "WriteRuneWide", + func(b *Builder) (int, error) { return b.WriteRune('世') }, + 3, + "世", + }, + { + "WriteString", + func(b *Builder) (int, error) { return b.WriteString(s0) }, + len(s0), + s0, + }, + } { + t.Run(tt.name, func(t *testing.T) { + var b Builder + n, err := tt.fn(&b) + if err != nil { + t.Fatalf("first call: got %s", err) + } + if n != tt.n { + t.Errorf("first call: got n=%d; want %d", n, tt.n) + } + check(t, &b, tt.want) + + n, err = tt.fn(&b) + if err != nil { + t.Fatalf("second call: got %s", err) + } + if n != tt.n { + t.Errorf("second call: got n=%d; want %d", n, tt.n) + } + check(t, &b, tt.want+tt.want) + }) + } +} + +func TestBuilderWriteByte(t *testing.T) { + var b Builder + if err := b.WriteByte('a'); err != nil { + t.Error(err) + } + if err := b.WriteByte(0); err != nil { + t.Error(err) + } + check(t, &b, "a\x00") +} + +func TestBuilderReadFrom(t *testing.T) { + for _, tt := range []struct { + name string + fn func(io.Reader) io.Reader + }{ + {"Reader", func(r io.Reader) io.Reader { return r }}, + {"DataErrReader", iotest.DataErrReader}, + {"OneByteReader", iotest.OneByteReader}, + } { + t.Run(tt.name, func(t *testing.T) { + var b Builder + + r := tt.fn(NewReader("hello")) + n, err := b.ReadFrom(r) + if err != nil { + t.Fatalf("first call: got %s", err) + } + if n != 5 { + t.Errorf("first call: got n=%d; want 5", n) + } + check(t, &b, "hello") + + r = tt.fn(NewReader(" world")) + n, err = b.ReadFrom(r) + if err != nil { + t.Fatalf("first call: got %s", err) + } + if n != 6 { + t.Errorf("first call: got n=%d; want 6", n) + } + check(t, &b, "hello world") + }) + } +} + +var errRead = errors.New("boom") + +// errorReader sends reads to the underlying reader +// but returns errRead instead of io.EOF. +type errorReader struct { + r io.Reader +} + +func (r errorReader) Read(b []byte) (int, error) { + n, err := r.r.Read(b) + if err == io.EOF { + err = errRead + } + return n, err +} + +func TestBuilderReadFromError(t *testing.T) { + var b Builder + r := errorReader{NewReader("hello")} + n, err := b.ReadFrom(r) + if n != 5 { + t.Errorf("got n=%d; want 5", n) + } + if err != errRead { + t.Errorf("got err=%q; want %q", err, errRead) + } + check(t, &b, "hello") +} + +type negativeReader struct{} + +func (r negativeReader) Read([]byte) (int, error) { return -1, nil } + +func TestBuilderReadFromNegativeReader(t *testing.T) { + var b Builder + defer func() { + switch err := recover().(type) { + case nil: + t.Fatal("ReadFrom didn't panic") + case error: + wantErr := "strings.Builder: reader returned negative count from Read" + if err.Error() != wantErr { + t.Fatalf("recovered panic: got %v; want %v", err.Error(), wantErr) + } + default: + t.Fatalf("unexpected panic value: %#v", err) + } + }() + + b.ReadFrom(negativeReader{}) +} + +func TestBuilderAllocs(t *testing.T) { + var b Builder + b.Grow(5) + var s string + allocs := numAllocs(func() { + b.WriteString("hello") + s = b.String() + }) + if want := "hello"; s != want { + t.Errorf("String: got %#q; want %#q", s, want) + } + if allocs > 0 { + t.Fatalf("got %d alloc(s); want 0", allocs) + } +} + +func numAllocs(fn func()) uint64 { + defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(1)) + var m1, m2 runtime.MemStats + runtime.ReadMemStats(&m1) + fn() + runtime.ReadMemStats(&m2) + return m2.Mallocs - m1.Mallocs +} diff --git a/src/strings/example_test.go b/src/strings/example_test.go index f7a78b4385..607e4a0a70 100644 --- a/src/strings/example_test.go +++ b/src/strings/example_test.go @@ -351,3 +351,14 @@ func ExampleTrimRightFunc() { })) // Output: ¡¡¡Hello, Gophers } + +func ExampleBuilder() { + var b strings.Builder + for i := 3; i >= 1; i-- { + fmt.Fprintf(&b, "%d...", i) + } + b.WriteString("ignition") + fmt.Println(b.String()) + + // Output: 3...2...1...ignition +} -- 2.48.1