diff options
Diffstat (limited to 'src/bytes')
| -rw-r--r-- | src/bytes/boundary_test.go | 100 | ||||
| -rw-r--r-- | src/bytes/buffer.go | 473 | ||||
| -rw-r--r-- | src/bytes/buffer_test.go | 689 | ||||
| -rw-r--r-- | src/bytes/bytes.go | 1381 | ||||
| -rw-r--r-- | src/bytes/bytes_test.go | 2217 | ||||
| -rw-r--r-- | src/bytes/compare_test.go | 271 | ||||
| -rw-r--r-- | src/bytes/example_test.go | 547 | ||||
| -rw-r--r-- | src/bytes/export_test.go | 8 | ||||
| -rw-r--r-- | src/bytes/reader.go | 159 | ||||
| -rw-r--r-- | src/bytes/reader_test.go | 319 |
10 files changed, 6164 insertions, 0 deletions
diff --git a/src/bytes/boundary_test.go b/src/bytes/boundary_test.go new file mode 100644 index 0000000..f9855fc --- /dev/null +++ b/src/bytes/boundary_test.go @@ -0,0 +1,100 @@ +// 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. +// +//go:build linux + +package bytes_test + +import ( + . "bytes" + "syscall" + "testing" +) + +// This file tests the situation where byte operations are checking +// data very near to a page boundary. We want to make sure those +// operations do not read across the boundary and cause a page +// fault where they shouldn't. + +// These tests run only on linux. The code being tested is +// not OS-specific, so it does not need to be tested on all +// operating systems. + +// dangerousSlice returns a slice which is immediately +// preceded and followed by a faulting page. +func dangerousSlice(t *testing.T) []byte { + pagesize := syscall.Getpagesize() + b, err := syscall.Mmap(0, 0, 3*pagesize, syscall.PROT_READ|syscall.PROT_WRITE, syscall.MAP_ANONYMOUS|syscall.MAP_PRIVATE) + if err != nil { + t.Fatalf("mmap failed %s", err) + } + err = syscall.Mprotect(b[:pagesize], syscall.PROT_NONE) + if err != nil { + t.Fatalf("mprotect low failed %s\n", err) + } + err = syscall.Mprotect(b[2*pagesize:], syscall.PROT_NONE) + if err != nil { + t.Fatalf("mprotect high failed %s\n", err) + } + return b[pagesize : 2*pagesize] +} + +func TestEqualNearPageBoundary(t *testing.T) { + t.Parallel() + b := dangerousSlice(t) + for i := range b { + b[i] = 'A' + } + for i := 0; i <= len(b); i++ { + Equal(b[:i], b[len(b)-i:]) + Equal(b[len(b)-i:], b[:i]) + } +} + +func TestIndexByteNearPageBoundary(t *testing.T) { + t.Parallel() + b := dangerousSlice(t) + for i := range b { + idx := IndexByte(b[i:], 1) + if idx != -1 { + t.Fatalf("IndexByte(b[%d:])=%d, want -1\n", i, idx) + } + } +} + +func TestIndexNearPageBoundary(t *testing.T) { + t.Parallel() + q := dangerousSlice(t) + if len(q) > 64 { + // Only worry about when we're near the end of a page. + q = q[len(q)-64:] + } + b := dangerousSlice(t) + if len(b) > 256 { + // Only worry about when we're near the end of a page. + b = b[len(b)-256:] + } + for j := 1; j < len(q); j++ { + q[j-1] = 1 // difference is only found on the last byte + for i := range b { + idx := Index(b[i:], q[:j]) + if idx != -1 { + t.Fatalf("Index(b[%d:], q[:%d])=%d, want -1\n", i, j, idx) + } + } + q[j-1] = 0 + } + + // Test differing alignments and sizes of q which always end on a page boundary. + q[len(q)-1] = 1 // difference is only found on the last byte + for j := 0; j < len(q); j++ { + for i := range b { + idx := Index(b[i:], q[j:]) + if idx != -1 { + t.Fatalf("Index(b[%d:], q[%d:])=%d, want -1\n", i, j, idx) + } + } + } + q[len(q)-1] = 0 +} diff --git a/src/bytes/buffer.go b/src/bytes/buffer.go new file mode 100644 index 0000000..ee83fd8 --- /dev/null +++ b/src/bytes/buffer.go @@ -0,0 +1,473 @@ +// Copyright 2009 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 bytes + +// Simple byte buffer for marshaling data. + +import ( + "errors" + "io" + "unicode/utf8" +) + +// smallBufferSize is an initial allocation minimal capacity. +const smallBufferSize = 64 + +// A Buffer is a variable-sized buffer of bytes with Read and Write methods. +// The zero value for Buffer is an empty buffer ready to use. +type Buffer struct { + buf []byte // contents are the bytes buf[off : len(buf)] + off int // read at &buf[off], write at &buf[len(buf)] + lastRead readOp // last read operation, so that Unread* can work correctly. +} + +// The readOp constants describe the last action performed on +// the buffer, so that UnreadRune and UnreadByte can check for +// invalid usage. opReadRuneX constants are chosen such that +// converted to int they correspond to the rune size that was read. +type readOp int8 + +// Don't use iota for these, as the values need to correspond with the +// names and comments, which is easier to see when being explicit. +const ( + opRead readOp = -1 // Any other read operation. + opInvalid readOp = 0 // Non-read operation. + opReadRune1 readOp = 1 // Read rune of size 1. + opReadRune2 readOp = 2 // Read rune of size 2. + opReadRune3 readOp = 3 // Read rune of size 3. + opReadRune4 readOp = 4 // Read rune of size 4. +) + +// ErrTooLarge is passed to panic if memory cannot be allocated to store data in a buffer. +var ErrTooLarge = errors.New("bytes.Buffer: too large") +var errNegativeRead = errors.New("bytes.Buffer: reader returned negative count from Read") + +const maxInt = int(^uint(0) >> 1) + +// Bytes returns a slice of length b.Len() holding the unread portion of the buffer. +// The slice is valid for use only until the next buffer modification (that is, +// only until the next call to a method like Read, Write, Reset, or Truncate). +// The slice aliases the buffer content at least until the next buffer modification, +// so immediate changes to the slice will affect the result of future reads. +func (b *Buffer) Bytes() []byte { return b.buf[b.off:] } + +// String returns the contents of the unread portion of the buffer +// as a string. If the Buffer is a nil pointer, it returns "<nil>". +// +// To build strings more efficiently, see the strings.Builder type. +func (b *Buffer) String() string { + if b == nil { + // Special case, useful in debugging. + return "<nil>" + } + return string(b.buf[b.off:]) +} + +// empty reports whether the unread portion of the buffer is empty. +func (b *Buffer) empty() bool { return len(b.buf) <= b.off } + +// Len returns the number of bytes of the unread portion of the buffer; +// b.Len() == len(b.Bytes()). +func (b *Buffer) Len() int { return len(b.buf) - b.off } + +// Cap returns the capacity of the buffer's underlying byte slice, that is, the +// total space allocated for the buffer's data. +func (b *Buffer) Cap() int { return cap(b.buf) } + +// Truncate discards all but the first n unread bytes from the buffer +// but continues to use the same allocated storage. +// It panics if n is negative or greater than the length of the buffer. +func (b *Buffer) Truncate(n int) { + if n == 0 { + b.Reset() + return + } + b.lastRead = opInvalid + if n < 0 || n > b.Len() { + panic("bytes.Buffer: truncation out of range") + } + b.buf = b.buf[:b.off+n] +} + +// Reset resets the buffer to be empty, +// but it retains the underlying storage for use by future writes. +// Reset is the same as Truncate(0). +func (b *Buffer) Reset() { + b.buf = b.buf[:0] + b.off = 0 + b.lastRead = opInvalid +} + +// tryGrowByReslice is a inlineable version of grow for the fast-case where the +// internal buffer only needs to be resliced. +// It returns the index where bytes should be written and whether it succeeded. +func (b *Buffer) tryGrowByReslice(n int) (int, bool) { + if l := len(b.buf); n <= cap(b.buf)-l { + b.buf = b.buf[:l+n] + return l, true + } + return 0, false +} + +// grow grows the buffer to guarantee space for n more bytes. +// It returns the index where bytes should be written. +// If the buffer can't grow it will panic with ErrTooLarge. +func (b *Buffer) grow(n int) int { + m := b.Len() + // If buffer is empty, reset to recover space. + if m == 0 && b.off != 0 { + b.Reset() + } + // Try to grow by means of a reslice. + if i, ok := b.tryGrowByReslice(n); ok { + return i + } + if b.buf == nil && n <= smallBufferSize { + b.buf = make([]byte, n, smallBufferSize) + return 0 + } + c := cap(b.buf) + if n <= c/2-m { + // We can slide things down instead of allocating a new + // slice. We only need m+n <= c to slide, but + // we instead let capacity get twice as large so we + // don't spend all our time copying. + copy(b.buf, b.buf[b.off:]) + } else if c > maxInt-c-n { + panic(ErrTooLarge) + } else { + // Add b.off to account for b.buf[:b.off] being sliced off the front. + b.buf = growSlice(b.buf[b.off:], b.off+n) + } + // Restore b.off and len(b.buf). + b.off = 0 + b.buf = b.buf[:m+n] + return m +} + +// Grow grows the buffer's capacity, if necessary, to guarantee space for +// another n bytes. After Grow(n), at least n bytes can be written to the +// buffer without another allocation. +// If n is negative, Grow will panic. +// If the buffer can't grow it will panic with ErrTooLarge. +func (b *Buffer) Grow(n int) { + if n < 0 { + panic("bytes.Buffer.Grow: negative count") + } + m := b.grow(n) + b.buf = b.buf[:m] +} + +// Write appends the contents of p to the buffer, growing the buffer as +// needed. The return value n is the length of p; err is always nil. If the +// buffer becomes too large, Write will panic with ErrTooLarge. +func (b *Buffer) Write(p []byte) (n int, err error) { + b.lastRead = opInvalid + m, ok := b.tryGrowByReslice(len(p)) + if !ok { + m = b.grow(len(p)) + } + return copy(b.buf[m:], p), nil +} + +// WriteString appends the contents of s to the buffer, growing the buffer as +// needed. The return value n is the length of s; err is always nil. If the +// buffer becomes too large, WriteString will panic with ErrTooLarge. +func (b *Buffer) WriteString(s string) (n int, err error) { + b.lastRead = opInvalid + m, ok := b.tryGrowByReslice(len(s)) + if !ok { + m = b.grow(len(s)) + } + return copy(b.buf[m:], s), nil +} + +// MinRead is the minimum slice size passed to a Read call by +// Buffer.ReadFrom. As long as the Buffer has at least MinRead bytes beyond +// what is required to hold the contents of r, ReadFrom will not grow the +// underlying buffer. +const MinRead = 512 + +// ReadFrom reads data from r until EOF and appends it to the buffer, growing +// the buffer as needed. The return value n is the number of bytes read. Any +// error except io.EOF encountered during the read is also returned. If the +// buffer becomes too large, ReadFrom will panic with ErrTooLarge. +func (b *Buffer) ReadFrom(r io.Reader) (n int64, err error) { + b.lastRead = opInvalid + for { + i := b.grow(MinRead) + b.buf = b.buf[:i] + m, e := r.Read(b.buf[i:cap(b.buf)]) + if m < 0 { + panic(errNegativeRead) + } + + b.buf = b.buf[:i+m] + n += int64(m) + if e == io.EOF { + return n, nil // e is EOF, so return nil explicitly + } + if e != nil { + return n, e + } + } +} + +// growSlice grows b by n, preserving the original content of b. +// If the allocation fails, it panics with ErrTooLarge. +func growSlice(b []byte, n int) []byte { + defer func() { + if recover() != nil { + panic(ErrTooLarge) + } + }() + // TODO(http://golang.org/issue/51462): We should rely on the append-make + // pattern so that the compiler can call runtime.growslice. For example: + // return append(b, make([]byte, n)...) + // This avoids unnecessary zero-ing of the first len(b) bytes of the + // allocated slice, but this pattern causes b to escape onto the heap. + // + // Instead use the append-make pattern with a nil slice to ensure that + // we allocate buffers rounded up to the closest size class. + c := len(b) + n // ensure enough space for n elements + if c < 2*cap(b) { + // The growth rate has historically always been 2x. In the future, + // we could rely purely on append to determine the growth rate. + c = 2 * cap(b) + } + b2 := append([]byte(nil), make([]byte, c)...) + copy(b2, b) + return b2[:len(b)] +} + +// WriteTo writes data to w until the buffer is drained or an error occurs. +// The return value n is the number of bytes written; it always fits into an +// int, but it is int64 to match the io.WriterTo interface. Any error +// encountered during the write is also returned. +func (b *Buffer) WriteTo(w io.Writer) (n int64, err error) { + b.lastRead = opInvalid + if nBytes := b.Len(); nBytes > 0 { + m, e := w.Write(b.buf[b.off:]) + if m > nBytes { + panic("bytes.Buffer.WriteTo: invalid Write count") + } + b.off += m + n = int64(m) + if e != nil { + return n, e + } + // all bytes should have been written, by definition of + // Write method in io.Writer + if m != nBytes { + return n, io.ErrShortWrite + } + } + // Buffer is now empty; reset. + b.Reset() + return n, nil +} + +// WriteByte appends the byte c to the buffer, growing the buffer as needed. +// The returned error is always nil, but is included to match bufio.Writer's +// WriteByte. If the buffer becomes too large, WriteByte will panic with +// ErrTooLarge. +func (b *Buffer) WriteByte(c byte) error { + b.lastRead = opInvalid + m, ok := b.tryGrowByReslice(1) + if !ok { + m = b.grow(1) + } + b.buf[m] = c + return nil +} + +// WriteRune appends the UTF-8 encoding of Unicode code point r to the +// buffer, returning its length and an error, which is always nil but is +// included to match bufio.Writer's WriteRune. The buffer is grown as needed; +// if it becomes too large, WriteRune will panic with ErrTooLarge. +func (b *Buffer) WriteRune(r rune) (n int, err error) { + // Compare as uint32 to correctly handle negative runes. + if uint32(r) < utf8.RuneSelf { + b.WriteByte(byte(r)) + return 1, nil + } + b.lastRead = opInvalid + m, ok := b.tryGrowByReslice(utf8.UTFMax) + if !ok { + m = b.grow(utf8.UTFMax) + } + b.buf = utf8.AppendRune(b.buf[:m], r) + return len(b.buf) - m, nil +} + +// Read reads the next len(p) bytes from the buffer or until the buffer +// is drained. The return value n is the number of bytes read. If the +// buffer has no data to return, err is io.EOF (unless len(p) is zero); +// otherwise it is nil. +func (b *Buffer) Read(p []byte) (n int, err error) { + b.lastRead = opInvalid + if b.empty() { + // Buffer is empty, reset to recover space. + b.Reset() + if len(p) == 0 { + return 0, nil + } + return 0, io.EOF + } + n = copy(p, b.buf[b.off:]) + b.off += n + if n > 0 { + b.lastRead = opRead + } + return n, nil +} + +// Next returns a slice containing the next n bytes from the buffer, +// advancing the buffer as if the bytes had been returned by Read. +// If there are fewer than n bytes in the buffer, Next returns the entire buffer. +// The slice is only valid until the next call to a read or write method. +func (b *Buffer) Next(n int) []byte { + b.lastRead = opInvalid + m := b.Len() + if n > m { + n = m + } + data := b.buf[b.off : b.off+n] + b.off += n + if n > 0 { + b.lastRead = opRead + } + return data +} + +// ReadByte reads and returns the next byte from the buffer. +// If no byte is available, it returns error io.EOF. +func (b *Buffer) ReadByte() (byte, error) { + if b.empty() { + // Buffer is empty, reset to recover space. + b.Reset() + return 0, io.EOF + } + c := b.buf[b.off] + b.off++ + b.lastRead = opRead + return c, nil +} + +// ReadRune reads and returns the next UTF-8-encoded +// Unicode code point from the buffer. +// If no bytes are available, the error returned is io.EOF. +// If the bytes are an erroneous UTF-8 encoding, it +// consumes one byte and returns U+FFFD, 1. +func (b *Buffer) ReadRune() (r rune, size int, err error) { + if b.empty() { + // Buffer is empty, reset to recover space. + b.Reset() + return 0, 0, io.EOF + } + c := b.buf[b.off] + if c < utf8.RuneSelf { + b.off++ + b.lastRead = opReadRune1 + return rune(c), 1, nil + } + r, n := utf8.DecodeRune(b.buf[b.off:]) + b.off += n + b.lastRead = readOp(n) + return r, n, nil +} + +// UnreadRune unreads the last rune returned by ReadRune. +// If the most recent read or write operation on the buffer was +// not a successful ReadRune, UnreadRune returns an error. (In this regard +// it is stricter than UnreadByte, which will unread the last byte +// from any read operation.) +func (b *Buffer) UnreadRune() error { + if b.lastRead <= opInvalid { + return errors.New("bytes.Buffer: UnreadRune: previous operation was not a successful ReadRune") + } + if b.off >= int(b.lastRead) { + b.off -= int(b.lastRead) + } + b.lastRead = opInvalid + return nil +} + +var errUnreadByte = errors.New("bytes.Buffer: UnreadByte: previous operation was not a successful read") + +// UnreadByte unreads the last byte returned by the most recent successful +// read operation that read at least one byte. If a write has happened since +// the last read, if the last read returned an error, or if the read read zero +// bytes, UnreadByte returns an error. +func (b *Buffer) UnreadByte() error { + if b.lastRead == opInvalid { + return errUnreadByte + } + b.lastRead = opInvalid + if b.off > 0 { + b.off-- + } + return nil +} + +// ReadBytes reads until the first occurrence of delim in the input, +// returning a slice containing the data up to and including the delimiter. +// If ReadBytes encounters an error before finding a delimiter, +// it returns the data read before the error and the error itself (often io.EOF). +// ReadBytes returns err != nil if and only if the returned data does not end in +// delim. +func (b *Buffer) ReadBytes(delim byte) (line []byte, err error) { + slice, err := b.readSlice(delim) + // return a copy of slice. The buffer's backing array may + // be overwritten by later calls. + line = append(line, slice...) + return line, err +} + +// readSlice is like ReadBytes but returns a reference to internal buffer data. +func (b *Buffer) readSlice(delim byte) (line []byte, err error) { + i := IndexByte(b.buf[b.off:], delim) + end := b.off + i + 1 + if i < 0 { + end = len(b.buf) + err = io.EOF + } + line = b.buf[b.off:end] + b.off = end + b.lastRead = opRead + return line, err +} + +// ReadString reads until the first occurrence of delim in the input, +// returning a string containing the data up to and including the delimiter. +// If ReadString encounters an error before finding a delimiter, +// it returns the data read before the error and the error itself (often io.EOF). +// ReadString returns err != nil if and only if the returned data does not end +// in delim. +func (b *Buffer) ReadString(delim byte) (line string, err error) { + slice, err := b.readSlice(delim) + return string(slice), err +} + +// NewBuffer creates and initializes a new Buffer using buf as its +// initial contents. The new Buffer takes ownership of buf, and the +// caller should not use buf after this call. NewBuffer is intended to +// prepare a Buffer to read existing data. It can also be used to set +// the initial size of the internal buffer for writing. To do that, +// buf should have the desired capacity but a length of zero. +// +// In most cases, new(Buffer) (or just declaring a Buffer variable) is +// sufficient to initialize a Buffer. +func NewBuffer(buf []byte) *Buffer { return &Buffer{buf: buf} } + +// NewBufferString creates and initializes a new Buffer using string s as its +// initial contents. It is intended to prepare a buffer to read an existing +// string. +// +// In most cases, new(Buffer) (or just declaring a Buffer variable) is +// sufficient to initialize a Buffer. +func NewBufferString(s string) *Buffer { + return &Buffer{buf: []byte(s)} +} diff --git a/src/bytes/buffer_test.go b/src/bytes/buffer_test.go new file mode 100644 index 0000000..c085500 --- /dev/null +++ b/src/bytes/buffer_test.go @@ -0,0 +1,689 @@ +// Copyright 2009 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 bytes_test + +import ( + . "bytes" + "fmt" + "io" + "math/rand" + "testing" + "unicode/utf8" +) + +const N = 10000 // make this bigger for a larger (and slower) test +var testString string // test data for write tests +var testBytes []byte // test data; same as testString but as a slice. + +type negativeReader struct{} + +func (r *negativeReader) Read([]byte) (int, error) { return -1, nil } + +func init() { + testBytes = make([]byte, N) + for i := 0; i < N; i++ { + testBytes[i] = 'a' + byte(i%26) + } + testString = string(testBytes) +} + +// Verify that contents of buf match the string s. +func check(t *testing.T, testname string, buf *Buffer, s string) { + bytes := buf.Bytes() + str := buf.String() + if buf.Len() != len(bytes) { + t.Errorf("%s: buf.Len() == %d, len(buf.Bytes()) == %d", testname, buf.Len(), len(bytes)) + } + + if buf.Len() != len(str) { + t.Errorf("%s: buf.Len() == %d, len(buf.String()) == %d", testname, buf.Len(), len(str)) + } + + if buf.Len() != len(s) { + t.Errorf("%s: buf.Len() == %d, len(s) == %d", testname, buf.Len(), len(s)) + } + + if string(bytes) != s { + t.Errorf("%s: string(buf.Bytes()) == %q, s == %q", testname, string(bytes), s) + } +} + +// Fill buf through n writes of string fus. +// The initial contents of buf corresponds to the string s; +// the result is the final contents of buf returned as a string. +func fillString(t *testing.T, testname string, buf *Buffer, s string, n int, fus string) string { + check(t, testname+" (fill 1)", buf, s) + for ; n > 0; n-- { + m, err := buf.WriteString(fus) + if m != len(fus) { + t.Errorf(testname+" (fill 2): m == %d, expected %d", m, len(fus)) + } + if err != nil { + t.Errorf(testname+" (fill 3): err should always be nil, found err == %s", err) + } + s += fus + check(t, testname+" (fill 4)", buf, s) + } + return s +} + +// Fill buf through n writes of byte slice fub. +// The initial contents of buf corresponds to the string s; +// the result is the final contents of buf returned as a string. +func fillBytes(t *testing.T, testname string, buf *Buffer, s string, n int, fub []byte) string { + check(t, testname+" (fill 1)", buf, s) + for ; n > 0; n-- { + m, err := buf.Write(fub) + if m != len(fub) { + t.Errorf(testname+" (fill 2): m == %d, expected %d", m, len(fub)) + } + if err != nil { + t.Errorf(testname+" (fill 3): err should always be nil, found err == %s", err) + } + s += string(fub) + check(t, testname+" (fill 4)", buf, s) + } + return s +} + +func TestNewBuffer(t *testing.T) { + buf := NewBuffer(testBytes) + check(t, "NewBuffer", buf, testString) +} + +func TestNewBufferString(t *testing.T) { + buf := NewBufferString(testString) + check(t, "NewBufferString", buf, testString) +} + +// Empty buf through repeated reads into fub. +// The initial contents of buf corresponds to the string s. +func empty(t *testing.T, testname string, buf *Buffer, s string, fub []byte) { + check(t, testname+" (empty 1)", buf, s) + + for { + n, err := buf.Read(fub) + if n == 0 { + break + } + if err != nil { + t.Errorf(testname+" (empty 2): err should always be nil, found err == %s", err) + } + s = s[n:] + check(t, testname+" (empty 3)", buf, s) + } + + check(t, testname+" (empty 4)", buf, "") +} + +func TestBasicOperations(t *testing.T) { + var buf Buffer + + for i := 0; i < 5; i++ { + check(t, "TestBasicOperations (1)", &buf, "") + + buf.Reset() + check(t, "TestBasicOperations (2)", &buf, "") + + buf.Truncate(0) + check(t, "TestBasicOperations (3)", &buf, "") + + n, err := buf.Write(testBytes[0:1]) + if want := 1; err != nil || n != want { + t.Errorf("Write: got (%d, %v), want (%d, %v)", n, err, want, nil) + } + check(t, "TestBasicOperations (4)", &buf, "a") + + buf.WriteByte(testString[1]) + check(t, "TestBasicOperations (5)", &buf, "ab") + + n, err = buf.Write(testBytes[2:26]) + if want := 24; err != nil || n != want { + t.Errorf("Write: got (%d, %v), want (%d, %v)", n, err, want, nil) + } + check(t, "TestBasicOperations (6)", &buf, testString[0:26]) + + buf.Truncate(26) + check(t, "TestBasicOperations (7)", &buf, testString[0:26]) + + buf.Truncate(20) + check(t, "TestBasicOperations (8)", &buf, testString[0:20]) + + empty(t, "TestBasicOperations (9)", &buf, testString[0:20], make([]byte, 5)) + empty(t, "TestBasicOperations (10)", &buf, "", make([]byte, 100)) + + buf.WriteByte(testString[1]) + c, err := buf.ReadByte() + if want := testString[1]; err != nil || c != want { + t.Errorf("ReadByte: got (%q, %v), want (%q, %v)", c, err, want, nil) + } + c, err = buf.ReadByte() + if err != io.EOF { + t.Errorf("ReadByte: got (%q, %v), want (%q, %v)", c, err, byte(0), io.EOF) + } + } +} + +func TestLargeStringWrites(t *testing.T) { + var buf Buffer + limit := 30 + if testing.Short() { + limit = 9 + } + for i := 3; i < limit; i += 3 { + s := fillString(t, "TestLargeWrites (1)", &buf, "", 5, testString) + empty(t, "TestLargeStringWrites (2)", &buf, s, make([]byte, len(testString)/i)) + } + check(t, "TestLargeStringWrites (3)", &buf, "") +} + +func TestLargeByteWrites(t *testing.T) { + var buf Buffer + limit := 30 + if testing.Short() { + limit = 9 + } + for i := 3; i < limit; i += 3 { + s := fillBytes(t, "TestLargeWrites (1)", &buf, "", 5, testBytes) + empty(t, "TestLargeByteWrites (2)", &buf, s, make([]byte, len(testString)/i)) + } + check(t, "TestLargeByteWrites (3)", &buf, "") +} + +func TestLargeStringReads(t *testing.T) { + var buf Buffer + for i := 3; i < 30; i += 3 { + s := fillString(t, "TestLargeReads (1)", &buf, "", 5, testString[0:len(testString)/i]) + empty(t, "TestLargeReads (2)", &buf, s, make([]byte, len(testString))) + } + check(t, "TestLargeStringReads (3)", &buf, "") +} + +func TestLargeByteReads(t *testing.T) { + var buf Buffer + for i := 3; i < 30; i += 3 { + s := fillBytes(t, "TestLargeReads (1)", &buf, "", 5, testBytes[0:len(testBytes)/i]) + empty(t, "TestLargeReads (2)", &buf, s, make([]byte, len(testString))) + } + check(t, "TestLargeByteReads (3)", &buf, "") +} + +func TestMixedReadsAndWrites(t *testing.T) { + var buf Buffer + s := "" + for i := 0; i < 50; i++ { + wlen := rand.Intn(len(testString)) + if i%2 == 0 { + s = fillString(t, "TestMixedReadsAndWrites (1)", &buf, s, 1, testString[0:wlen]) + } else { + s = fillBytes(t, "TestMixedReadsAndWrites (1)", &buf, s, 1, testBytes[0:wlen]) + } + + rlen := rand.Intn(len(testString)) + fub := make([]byte, rlen) + n, _ := buf.Read(fub) + s = s[n:] + } + empty(t, "TestMixedReadsAndWrites (2)", &buf, s, make([]byte, buf.Len())) +} + +func TestCapWithPreallocatedSlice(t *testing.T) { + buf := NewBuffer(make([]byte, 10)) + n := buf.Cap() + if n != 10 { + t.Errorf("expected 10, got %d", n) + } +} + +func TestCapWithSliceAndWrittenData(t *testing.T) { + buf := NewBuffer(make([]byte, 0, 10)) + buf.Write([]byte("test")) + n := buf.Cap() + if n != 10 { + t.Errorf("expected 10, got %d", n) + } +} + +func TestNil(t *testing.T) { + var b *Buffer + if b.String() != "<nil>" { + t.Errorf("expected <nil>; got %q", b.String()) + } +} + +func TestReadFrom(t *testing.T) { + var buf Buffer + for i := 3; i < 30; i += 3 { + s := fillBytes(t, "TestReadFrom (1)", &buf, "", 5, testBytes[0:len(testBytes)/i]) + var b Buffer + b.ReadFrom(&buf) + empty(t, "TestReadFrom (2)", &b, s, make([]byte, len(testString))) + } +} + +type panicReader struct{ panic bool } + +func (r panicReader) Read(p []byte) (int, error) { + if r.panic { + panic(nil) + } + return 0, io.EOF +} + +// Make sure that an empty Buffer remains empty when +// it is "grown" before a Read that panics +func TestReadFromPanicReader(t *testing.T) { + + // First verify non-panic behaviour + var buf Buffer + i, err := buf.ReadFrom(panicReader{}) + if err != nil { + t.Fatal(err) + } + if i != 0 { + t.Fatalf("unexpected return from bytes.ReadFrom (1): got: %d, want %d", i, 0) + } + check(t, "TestReadFromPanicReader (1)", &buf, "") + + // Confirm that when Reader panics, the empty buffer remains empty + var buf2 Buffer + defer func() { + recover() + check(t, "TestReadFromPanicReader (2)", &buf2, "") + }() + buf2.ReadFrom(panicReader{panic: true}) +} + +func TestReadFromNegativeReader(t *testing.T) { + var b Buffer + defer func() { + switch err := recover().(type) { + case nil: + t.Fatal("bytes.Buffer.ReadFrom didn't panic") + case error: + // this is the error string of errNegativeRead + wantError := "bytes.Buffer: reader returned negative count from Read" + if err.Error() != wantError { + t.Fatalf("recovered panic: got %v, want %v", err.Error(), wantError) + } + default: + t.Fatalf("unexpected panic value: %#v", err) + } + }() + + b.ReadFrom(new(negativeReader)) +} + +func TestWriteTo(t *testing.T) { + var buf Buffer + for i := 3; i < 30; i += 3 { + s := fillBytes(t, "TestWriteTo (1)", &buf, "", 5, testBytes[0:len(testBytes)/i]) + var b Buffer + buf.WriteTo(&b) + empty(t, "TestWriteTo (2)", &b, s, make([]byte, len(testString))) + } +} + +func TestRuneIO(t *testing.T) { + const NRune = 1000 + // Built a test slice while we write the data + b := make([]byte, utf8.UTFMax*NRune) + var buf Buffer + n := 0 + for r := rune(0); r < NRune; r++ { + size := utf8.EncodeRune(b[n:], r) + nbytes, err := buf.WriteRune(r) + if err != nil { + t.Fatalf("WriteRune(%U) error: %s", r, err) + } + if nbytes != size { + t.Fatalf("WriteRune(%U) expected %d, got %d", r, size, nbytes) + } + n += size + } + b = b[0:n] + + // Check the resulting bytes + if !Equal(buf.Bytes(), b) { + t.Fatalf("incorrect result from WriteRune: %q not %q", buf.Bytes(), b) + } + + p := make([]byte, utf8.UTFMax) + // Read it back with ReadRune + for r := rune(0); r < NRune; r++ { + size := utf8.EncodeRune(p, r) + nr, nbytes, err := buf.ReadRune() + if nr != r || nbytes != size || err != nil { + t.Fatalf("ReadRune(%U) got %U,%d not %U,%d (err=%s)", r, nr, nbytes, r, size, err) + } + } + + // Check that UnreadRune works + buf.Reset() + + // check at EOF + if err := buf.UnreadRune(); err == nil { + t.Fatal("UnreadRune at EOF: got no error") + } + if _, _, err := buf.ReadRune(); err == nil { + t.Fatal("ReadRune at EOF: got no error") + } + if err := buf.UnreadRune(); err == nil { + t.Fatal("UnreadRune after ReadRune at EOF: got no error") + } + + // check not at EOF + buf.Write(b) + for r := rune(0); r < NRune; r++ { + r1, size, _ := buf.ReadRune() + if err := buf.UnreadRune(); err != nil { + t.Fatalf("UnreadRune(%U) got error %q", r, err) + } + r2, nbytes, err := buf.ReadRune() + if r1 != r2 || r1 != r || nbytes != size || err != nil { + t.Fatalf("ReadRune(%U) after UnreadRune got %U,%d not %U,%d (err=%s)", r, r2, nbytes, r, size, err) + } + } +} + +func TestWriteInvalidRune(t *testing.T) { + // Invalid runes, including negative ones, should be written as + // utf8.RuneError. + for _, r := range []rune{-1, utf8.MaxRune + 1} { + var buf Buffer + buf.WriteRune(r) + check(t, fmt.Sprintf("TestWriteInvalidRune (%d)", r), &buf, "\uFFFD") + } +} + +func TestNext(t *testing.T) { + b := []byte{0, 1, 2, 3, 4} + tmp := make([]byte, 5) + for i := 0; i <= 5; i++ { + for j := i; j <= 5; j++ { + for k := 0; k <= 6; k++ { + // 0 <= i <= j <= 5; 0 <= k <= 6 + // Check that if we start with a buffer + // of length j at offset i and ask for + // Next(k), we get the right bytes. + buf := NewBuffer(b[0:j]) + n, _ := buf.Read(tmp[0:i]) + if n != i { + t.Fatalf("Read %d returned %d", i, n) + } + bb := buf.Next(k) + want := k + if want > j-i { + want = j - i + } + if len(bb) != want { + t.Fatalf("in %d,%d: len(Next(%d)) == %d", i, j, k, len(bb)) + } + for l, v := range bb { + if v != byte(l+i) { + t.Fatalf("in %d,%d: Next(%d)[%d] = %d, want %d", i, j, k, l, v, l+i) + } + } + } + } + } +} + +var readBytesTests = []struct { + buffer string + delim byte + expected []string + err error +}{ + {"", 0, []string{""}, io.EOF}, + {"a\x00", 0, []string{"a\x00"}, nil}, + {"abbbaaaba", 'b', []string{"ab", "b", "b", "aaab"}, nil}, + {"hello\x01world", 1, []string{"hello\x01"}, nil}, + {"foo\nbar", 0, []string{"foo\nbar"}, io.EOF}, + {"alpha\nbeta\ngamma\n", '\n', []string{"alpha\n", "beta\n", "gamma\n"}, nil}, + {"alpha\nbeta\ngamma", '\n', []string{"alpha\n", "beta\n", "gamma"}, io.EOF}, +} + +func TestReadBytes(t *testing.T) { + for _, test := range readBytesTests { + buf := NewBufferString(test.buffer) + var err error + for _, expected := range test.expected { + var bytes []byte + bytes, err = buf.ReadBytes(test.delim) + if string(bytes) != expected { + t.Errorf("expected %q, got %q", expected, bytes) + } + if err != nil { + break + } + } + if err != test.err { + t.Errorf("expected error %v, got %v", test.err, err) + } + } +} + +func TestReadString(t *testing.T) { + for _, test := range readBytesTests { + buf := NewBufferString(test.buffer) + var err error + for _, expected := range test.expected { + var s string + s, err = buf.ReadString(test.delim) + if s != expected { + t.Errorf("expected %q, got %q", expected, s) + } + if err != nil { + break + } + } + if err != test.err { + t.Errorf("expected error %v, got %v", test.err, err) + } + } +} + +func BenchmarkReadString(b *testing.B) { + const n = 32 << 10 + + data := make([]byte, n) + data[n-1] = 'x' + b.SetBytes(int64(n)) + for i := 0; i < b.N; i++ { + buf := NewBuffer(data) + _, err := buf.ReadString('x') + if err != nil { + b.Fatal(err) + } + } +} + +func TestGrow(t *testing.T) { + x := []byte{'x'} + y := []byte{'y'} + tmp := make([]byte, 72) + for _, growLen := range []int{0, 100, 1000, 10000, 100000} { + for _, startLen := range []int{0, 100, 1000, 10000, 100000} { + xBytes := Repeat(x, startLen) + + buf := NewBuffer(xBytes) + // If we read, this affects buf.off, which is good to test. + readBytes, _ := buf.Read(tmp) + yBytes := Repeat(y, growLen) + allocs := testing.AllocsPerRun(100, func() { + buf.Grow(growLen) + buf.Write(yBytes) + }) + // Check no allocation occurs in write, as long as we're single-threaded. + if allocs != 0 { + t.Errorf("allocation occurred during write") + } + // Check that buffer has correct data. + if !Equal(buf.Bytes()[0:startLen-readBytes], xBytes[readBytes:]) { + t.Errorf("bad initial data at %d %d", startLen, growLen) + } + if !Equal(buf.Bytes()[startLen-readBytes:startLen-readBytes+growLen], yBytes) { + t.Errorf("bad written data at %d %d", startLen, growLen) + } + } + } +} + +func TestGrowOverflow(t *testing.T) { + defer func() { + if err := recover(); err != ErrTooLarge { + t.Errorf("after too-large Grow, recover() = %v; want %v", err, ErrTooLarge) + } + }() + + buf := NewBuffer(make([]byte, 1)) + const maxInt = int(^uint(0) >> 1) + buf.Grow(maxInt) +} + +// Was a bug: used to give EOF reading empty slice at EOF. +func TestReadEmptyAtEOF(t *testing.T) { + b := new(Buffer) + slice := make([]byte, 0) + n, err := b.Read(slice) + if err != nil { + t.Errorf("read error: %v", err) + } + if n != 0 { + t.Errorf("wrong count; got %d want 0", n) + } +} + +func TestUnreadByte(t *testing.T) { + b := new(Buffer) + + // check at EOF + if err := b.UnreadByte(); err == nil { + t.Fatal("UnreadByte at EOF: got no error") + } + if _, err := b.ReadByte(); err == nil { + t.Fatal("ReadByte at EOF: got no error") + } + if err := b.UnreadByte(); err == nil { + t.Fatal("UnreadByte after ReadByte at EOF: got no error") + } + + // check not at EOF + b.WriteString("abcdefghijklmnopqrstuvwxyz") + + // after unsuccessful read + if n, err := b.Read(nil); n != 0 || err != nil { + t.Fatalf("Read(nil) = %d,%v; want 0,nil", n, err) + } + if err := b.UnreadByte(); err == nil { + t.Fatal("UnreadByte after Read(nil): got no error") + } + + // after successful read + if _, err := b.ReadBytes('m'); err != nil { + t.Fatalf("ReadBytes: %v", err) + } + if err := b.UnreadByte(); err != nil { + t.Fatalf("UnreadByte: %v", err) + } + c, err := b.ReadByte() + if err != nil { + t.Fatalf("ReadByte: %v", err) + } + if c != 'm' { + t.Errorf("ReadByte = %q; want %q", c, 'm') + } +} + +// Tests that we occasionally compact. Issue 5154. +func TestBufferGrowth(t *testing.T) { + var b Buffer + buf := make([]byte, 1024) + b.Write(buf[0:1]) + var cap0 int + for i := 0; i < 5<<10; i++ { + b.Write(buf) + b.Read(buf) + if i == 0 { + cap0 = b.Cap() + } + } + cap1 := b.Cap() + // (*Buffer).grow allows for 2x capacity slop before sliding, + // so set our error threshold at 3x. + if cap1 > cap0*3 { + t.Errorf("buffer cap = %d; too big (grew from %d)", cap1, cap0) + } +} + +func BenchmarkWriteByte(b *testing.B) { + const n = 4 << 10 + b.SetBytes(n) + buf := NewBuffer(make([]byte, n)) + for i := 0; i < b.N; i++ { + buf.Reset() + for i := 0; i < n; i++ { + buf.WriteByte('x') + } + } +} + +func BenchmarkWriteRune(b *testing.B) { + const n = 4 << 10 + const r = '☺' + b.SetBytes(int64(n * utf8.RuneLen(r))) + buf := NewBuffer(make([]byte, n*utf8.UTFMax)) + for i := 0; i < b.N; i++ { + buf.Reset() + for i := 0; i < n; i++ { + buf.WriteRune(r) + } + } +} + +// From Issue 5154. +func BenchmarkBufferNotEmptyWriteRead(b *testing.B) { + buf := make([]byte, 1024) + for i := 0; i < b.N; i++ { + var b Buffer + b.Write(buf[0:1]) + for i := 0; i < 5<<10; i++ { + b.Write(buf) + b.Read(buf) + } + } +} + +// Check that we don't compact too often. From Issue 5154. +func BenchmarkBufferFullSmallReads(b *testing.B) { + buf := make([]byte, 1024) + for i := 0; i < b.N; i++ { + var b Buffer + b.Write(buf) + for b.Len()+20 < b.Cap() { + b.Write(buf[:10]) + } + for i := 0; i < 5<<10; i++ { + b.Read(buf[:1]) + b.Write(buf[:1]) + } + } +} + +func BenchmarkBufferWriteBlock(b *testing.B) { + block := make([]byte, 1024) + for _, n := range []int{1 << 12, 1 << 16, 1 << 20} { + b.Run(fmt.Sprintf("N%d", n), func(b *testing.B) { + b.ReportAllocs() + for i := 0; i < b.N; i++ { + var bb Buffer + for bb.Len() < n { + bb.Write(block) + } + } + }) + } +} diff --git a/src/bytes/bytes.go b/src/bytes/bytes.go new file mode 100644 index 0000000..e2e5d5f --- /dev/null +++ b/src/bytes/bytes.go @@ -0,0 +1,1381 @@ +// Copyright 2009 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 bytes implements functions for the manipulation of byte slices. +// It is analogous to the facilities of the strings package. +package bytes + +import ( + "internal/bytealg" + "unicode" + "unicode/utf8" +) + +// Equal reports whether a and b +// are the same length and contain the same bytes. +// A nil argument is equivalent to an empty slice. +func Equal(a, b []byte) bool { + // Neither cmd/compile nor gccgo allocates for these string conversions. + return string(a) == string(b) +} + +// Compare returns an integer comparing two byte slices lexicographically. +// The result will be 0 if a == b, -1 if a < b, and +1 if a > b. +// A nil argument is equivalent to an empty slice. +func Compare(a, b []byte) int { + return bytealg.Compare(a, b) +} + +// explode splits s into a slice of UTF-8 sequences, one per Unicode code point (still slices of bytes), +// up to a maximum of n byte slices. Invalid UTF-8 sequences are chopped into individual bytes. +func explode(s []byte, n int) [][]byte { + if n <= 0 || n > len(s) { + n = len(s) + } + a := make([][]byte, n) + var size int + na := 0 + for len(s) > 0 { + if na+1 >= n { + a[na] = s + na++ + break + } + _, size = utf8.DecodeRune(s) + a[na] = s[0:size:size] + s = s[size:] + na++ + } + return a[0:na] +} + +// Count counts the number of non-overlapping instances of sep in s. +// If sep is an empty slice, Count returns 1 + the number of UTF-8-encoded code points in s. +func Count(s, sep []byte) int { + // special case + if len(sep) == 0 { + return utf8.RuneCount(s) + 1 + } + if len(sep) == 1 { + return bytealg.Count(s, sep[0]) + } + n := 0 + for { + i := Index(s, sep) + if i == -1 { + return n + } + n++ + s = s[i+len(sep):] + } +} + +// Contains reports whether subslice is within b. +func Contains(b, subslice []byte) bool { + return Index(b, subslice) != -1 +} + +// ContainsAny reports whether any of the UTF-8-encoded code points in chars are within b. +func ContainsAny(b []byte, chars string) bool { + return IndexAny(b, chars) >= 0 +} + +// ContainsRune reports whether the rune is contained in the UTF-8-encoded byte slice b. +func ContainsRune(b []byte, r rune) bool { + return IndexRune(b, r) >= 0 +} + +// IndexByte returns the index of the first instance of c in b, or -1 if c is not present in b. +func IndexByte(b []byte, c byte) int { + return bytealg.IndexByte(b, c) +} + +func indexBytePortable(s []byte, c byte) int { + for i, b := range s { + if b == c { + return i + } + } + return -1 +} + +// LastIndex returns the index of the last instance of sep in s, or -1 if sep is not present in s. +func LastIndex(s, sep []byte) int { + n := len(sep) + switch { + case n == 0: + return len(s) + case n == 1: + return LastIndexByte(s, sep[0]) + case n == len(s): + if Equal(s, sep) { + return 0 + } + return -1 + case n > len(s): + return -1 + } + // Rabin-Karp search from the end of the string + hashss, pow := bytealg.HashStrRevBytes(sep) + last := len(s) - n + var h uint32 + for i := len(s) - 1; i >= last; i-- { + h = h*bytealg.PrimeRK + uint32(s[i]) + } + if h == hashss && Equal(s[last:], sep) { + return last + } + for i := last - 1; i >= 0; i-- { + h *= bytealg.PrimeRK + h += uint32(s[i]) + h -= pow * uint32(s[i+n]) + if h == hashss && Equal(s[i:i+n], sep) { + return i + } + } + return -1 +} + +// LastIndexByte returns the index of the last instance of c in s, or -1 if c is not present in s. +func LastIndexByte(s []byte, c byte) int { + for i := len(s) - 1; i >= 0; i-- { + if s[i] == c { + return i + } + } + return -1 +} + +// IndexRune interprets s as a sequence of UTF-8-encoded code points. +// It returns the byte index of the first occurrence in s of the given rune. +// It returns -1 if rune is not present in s. +// If r is utf8.RuneError, it returns the first instance of any +// invalid UTF-8 byte sequence. +func IndexRune(s []byte, r rune) int { + switch { + case 0 <= r && r < utf8.RuneSelf: + return IndexByte(s, byte(r)) + case r == utf8.RuneError: + for i := 0; i < len(s); { + r1, n := utf8.DecodeRune(s[i:]) + if r1 == utf8.RuneError { + return i + } + i += n + } + return -1 + case !utf8.ValidRune(r): + return -1 + default: + var b [utf8.UTFMax]byte + n := utf8.EncodeRune(b[:], r) + return Index(s, b[:n]) + } +} + +// IndexAny interprets s as a sequence of UTF-8-encoded Unicode code points. +// It returns the byte index of the first occurrence in s of any of the Unicode +// code points in chars. It returns -1 if chars is empty or if there is no code +// point in common. +func IndexAny(s []byte, chars string) int { + if chars == "" { + // Avoid scanning all of s. + return -1 + } + if len(s) == 1 { + r := rune(s[0]) + if r >= utf8.RuneSelf { + // search utf8.RuneError. + for _, r = range chars { + if r == utf8.RuneError { + return 0 + } + } + return -1 + } + if bytealg.IndexByteString(chars, s[0]) >= 0 { + return 0 + } + return -1 + } + if len(chars) == 1 { + r := rune(chars[0]) + if r >= utf8.RuneSelf { + r = utf8.RuneError + } + return IndexRune(s, r) + } + if len(s) > 8 { + if as, isASCII := makeASCIISet(chars); isASCII { + for i, c := range s { + if as.contains(c) { + return i + } + } + return -1 + } + } + var width int + for i := 0; i < len(s); i += width { + r := rune(s[i]) + if r < utf8.RuneSelf { + if bytealg.IndexByteString(chars, s[i]) >= 0 { + return i + } + width = 1 + continue + } + r, width = utf8.DecodeRune(s[i:]) + if r != utf8.RuneError { + // r is 2 to 4 bytes + if len(chars) == width { + if chars == string(r) { + return i + } + continue + } + // Use bytealg.IndexString for performance if available. + if bytealg.MaxLen >= width { + if bytealg.IndexString(chars, string(r)) >= 0 { + return i + } + continue + } + } + for _, ch := range chars { + if r == ch { + return i + } + } + } + return -1 +} + +// LastIndexAny interprets s as a sequence of UTF-8-encoded Unicode code +// points. It returns the byte index of the last occurrence in s of any of +// the Unicode code points in chars. It returns -1 if chars is empty or if +// there is no code point in common. +func LastIndexAny(s []byte, chars string) int { + if chars == "" { + // Avoid scanning all of s. + return -1 + } + if len(s) > 8 { + if as, isASCII := makeASCIISet(chars); isASCII { + for i := len(s) - 1; i >= 0; i-- { + if as.contains(s[i]) { + return i + } + } + return -1 + } + } + if len(s) == 1 { + r := rune(s[0]) + if r >= utf8.RuneSelf { + for _, r = range chars { + if r == utf8.RuneError { + return 0 + } + } + return -1 + } + if bytealg.IndexByteString(chars, s[0]) >= 0 { + return 0 + } + return -1 + } + if len(chars) == 1 { + cr := rune(chars[0]) + if cr >= utf8.RuneSelf { + cr = utf8.RuneError + } + for i := len(s); i > 0; { + r, size := utf8.DecodeLastRune(s[:i]) + i -= size + if r == cr { + return i + } + } + return -1 + } + for i := len(s); i > 0; { + r := rune(s[i-1]) + if r < utf8.RuneSelf { + if bytealg.IndexByteString(chars, s[i-1]) >= 0 { + return i - 1 + } + i-- + continue + } + r, size := utf8.DecodeLastRune(s[:i]) + i -= size + if r != utf8.RuneError { + // r is 2 to 4 bytes + if len(chars) == size { + if chars == string(r) { + return i + } + continue + } + // Use bytealg.IndexString for performance if available. + if bytealg.MaxLen >= size { + if bytealg.IndexString(chars, string(r)) >= 0 { + return i + } + continue + } + } + for _, ch := range chars { + if r == ch { + return i + } + } + } + return -1 +} + +// Generic split: splits after each instance of sep, +// including sepSave bytes of sep in the subslices. +func genSplit(s, sep []byte, sepSave, n int) [][]byte { + if n == 0 { + return nil + } + if len(sep) == 0 { + return explode(s, n) + } + if n < 0 { + n = Count(s, sep) + 1 + } + if n > len(s)+1 { + n = len(s) + 1 + } + + a := make([][]byte, n) + n-- + i := 0 + for i < n { + m := Index(s, sep) + if m < 0 { + break + } + a[i] = s[: m+sepSave : m+sepSave] + s = s[m+len(sep):] + i++ + } + a[i] = s + return a[:i+1] +} + +// SplitN slices s into subslices separated by sep and returns a slice of +// the subslices between those separators. +// If sep is empty, SplitN splits after each UTF-8 sequence. +// The count determines the number of subslices to return: +// +// n > 0: at most n subslices; the last subslice will be the unsplit remainder. +// n == 0: the result is nil (zero subslices) +// n < 0: all subslices +// +// To split around the first instance of a separator, see Cut. +func SplitN(s, sep []byte, n int) [][]byte { return genSplit(s, sep, 0, n) } + +// SplitAfterN slices s into subslices after each instance of sep and +// returns a slice of those subslices. +// If sep is empty, SplitAfterN splits after each UTF-8 sequence. +// The count determines the number of subslices to return: +// +// n > 0: at most n subslices; the last subslice will be the unsplit remainder. +// n == 0: the result is nil (zero subslices) +// n < 0: all subslices +func SplitAfterN(s, sep []byte, n int) [][]byte { + return genSplit(s, sep, len(sep), n) +} + +// Split slices s into all subslices separated by sep and returns a slice of +// the subslices between those separators. +// If sep is empty, Split splits after each UTF-8 sequence. +// It is equivalent to SplitN with a count of -1. +// +// To split around the first instance of a separator, see Cut. +func Split(s, sep []byte) [][]byte { return genSplit(s, sep, 0, -1) } + +// SplitAfter slices s into all subslices after each instance of sep and +// returns a slice of those subslices. +// If sep is empty, SplitAfter splits after each UTF-8 sequence. +// It is equivalent to SplitAfterN with a count of -1. +func SplitAfter(s, sep []byte) [][]byte { + return genSplit(s, sep, len(sep), -1) +} + +var asciiSpace = [256]uint8{'\t': 1, '\n': 1, '\v': 1, '\f': 1, '\r': 1, ' ': 1} + +// Fields interprets s as a sequence of UTF-8-encoded code points. +// It splits the slice s around each instance of one or more consecutive white space +// characters, as defined by unicode.IsSpace, returning a slice of subslices of s or an +// empty slice if s contains only white space. +func Fields(s []byte) [][]byte { + // First count the fields. + // This is an exact count if s is ASCII, otherwise it is an approximation. + n := 0 + wasSpace := 1 + // setBits is used to track which bits are set in the bytes of s. + setBits := uint8(0) + for i := 0; i < len(s); i++ { + r := s[i] + setBits |= r + isSpace := int(asciiSpace[r]) + n += wasSpace & ^isSpace + wasSpace = isSpace + } + + if setBits >= utf8.RuneSelf { + // Some runes in the input slice are not ASCII. + return FieldsFunc(s, unicode.IsSpace) + } + + // ASCII fast path + a := make([][]byte, n) + na := 0 + fieldStart := 0 + i := 0 + // Skip spaces in the front of the input. + for i < len(s) && asciiSpace[s[i]] != 0 { + i++ + } + fieldStart = i + for i < len(s) { + if asciiSpace[s[i]] == 0 { + i++ + continue + } + a[na] = s[fieldStart:i:i] + na++ + i++ + // Skip spaces in between fields. + for i < len(s) && asciiSpace[s[i]] != 0 { + i++ + } + fieldStart = i + } + if fieldStart < len(s) { // Last field might end at EOF. + a[na] = s[fieldStart:len(s):len(s)] + } + return a +} + +// FieldsFunc interprets s as a sequence of UTF-8-encoded code points. +// It splits the slice s at each run of code points c satisfying f(c) and +// returns a slice of subslices of s. If all code points in s satisfy f(c), or +// len(s) == 0, an empty slice is returned. +// +// FieldsFunc makes no guarantees about the order in which it calls f(c) +// and assumes that f always returns the same value for a given c. +func FieldsFunc(s []byte, f func(rune) bool) [][]byte { + // A span is used to record a slice of s of the form s[start:end]. + // The start index is inclusive and the end index is exclusive. + type span struct { + start int + end int + } + spans := make([]span, 0, 32) + + // Find the field start and end indices. + // Doing this in a separate pass (rather than slicing the string s + // and collecting the result substrings right away) is significantly + // more efficient, possibly due to cache effects. + start := -1 // valid span start if >= 0 + for i := 0; i < len(s); { + size := 1 + r := rune(s[i]) + if r >= utf8.RuneSelf { + r, size = utf8.DecodeRune(s[i:]) + } + if f(r) { + if start >= 0 { + spans = append(spans, span{start, i}) + start = -1 + } + } else { + if start < 0 { + start = i + } + } + i += size + } + + // Last field might end at EOF. + if start >= 0 { + spans = append(spans, span{start, len(s)}) + } + + // Create subslices from recorded field indices. + a := make([][]byte, len(spans)) + for i, span := range spans { + a[i] = s[span.start:span.end:span.end] + } + + return a +} + +// Join concatenates the elements of s to create a new byte slice. The separator +// sep is placed between elements in the resulting slice. +func Join(s [][]byte, sep []byte) []byte { + if len(s) == 0 { + return []byte{} + } + if len(s) == 1 { + // Just return a copy. + return append([]byte(nil), s[0]...) + } + n := len(sep) * (len(s) - 1) + for _, v := range s { + n += len(v) + } + + b := make([]byte, n) + bp := copy(b, s[0]) + for _, v := range s[1:] { + bp += copy(b[bp:], sep) + bp += copy(b[bp:], v) + } + return b +} + +// HasPrefix tests whether the byte slice s begins with prefix. +func HasPrefix(s, prefix []byte) bool { + return len(s) >= len(prefix) && Equal(s[0:len(prefix)], prefix) +} + +// HasSuffix tests whether the byte slice s ends with suffix. +func HasSuffix(s, suffix []byte) bool { + return len(s) >= len(suffix) && Equal(s[len(s)-len(suffix):], suffix) +} + +// Map returns a copy of the byte slice s with all its characters modified +// according to the mapping function. If mapping returns a negative value, the character is +// dropped from the byte slice with no replacement. The characters in s and the +// output are interpreted as UTF-8-encoded code points. +func Map(mapping func(r rune) rune, s []byte) []byte { + // In the worst case, the slice can grow when mapped, making + // things unpleasant. But it's so rare we barge in assuming it's + // fine. It could also shrink but that falls out naturally. + b := make([]byte, 0, len(s)) + for i := 0; i < len(s); { + wid := 1 + r := rune(s[i]) + if r >= utf8.RuneSelf { + r, wid = utf8.DecodeRune(s[i:]) + } + r = mapping(r) + if r >= 0 { + b = utf8.AppendRune(b, r) + } + i += wid + } + return b +} + +// Repeat returns a new byte slice consisting of count copies of b. +// +// It panics if count is negative or if the result of (len(b) * count) +// overflows. +func Repeat(b []byte, count int) []byte { + if count == 0 { + return []byte{} + } + // Since we cannot return an error on overflow, + // we should panic if the repeat will generate + // an overflow. + // See golang.org/issue/16237. + if count < 0 { + panic("bytes: negative Repeat count") + } else if len(b)*count/count != len(b) { + panic("bytes: Repeat count causes overflow") + } + + if len(b) == 0 { + return []byte{} + } + + n := len(b) * count + + // Past a certain chunk size it is counterproductive to use + // larger chunks as the source of the write, as when the source + // is too large we are basically just thrashing the CPU D-cache. + // So if the result length is larger than an empirically-found + // limit (8KB), we stop growing the source string once the limit + // is reached and keep reusing the same source string - that + // should therefore be always resident in the L1 cache - until we + // have completed the construction of the result. + // This yields significant speedups (up to +100%) in cases where + // the result length is large (roughly, over L2 cache size). + const chunkLimit = 8 * 1024 + chunkMax := n + if chunkMax > chunkLimit { + chunkMax = chunkLimit / len(b) * len(b) + if chunkMax == 0 { + chunkMax = len(b) + } + } + nb := make([]byte, n) + bp := copy(nb, b) + for bp < len(nb) { + chunk := bp + if chunk > chunkMax { + chunk = chunkMax + } + bp += copy(nb[bp:], nb[:chunk]) + } + return nb +} + +// ToUpper returns a copy of the byte slice s with all Unicode letters mapped to +// their upper case. +func ToUpper(s []byte) []byte { + isASCII, hasLower := true, false + for i := 0; i < len(s); i++ { + c := s[i] + if c >= utf8.RuneSelf { + isASCII = false + break + } + hasLower = hasLower || ('a' <= c && c <= 'z') + } + + if isASCII { // optimize for ASCII-only byte slices. + if !hasLower { + // Just return a copy. + return append([]byte(""), s...) + } + b := make([]byte, len(s)) + for i := 0; i < len(s); i++ { + c := s[i] + if 'a' <= c && c <= 'z' { + c -= 'a' - 'A' + } + b[i] = c + } + return b + } + return Map(unicode.ToUpper, s) +} + +// ToLower returns a copy of the byte slice s with all Unicode letters mapped to +// their lower case. +func ToLower(s []byte) []byte { + isASCII, hasUpper := true, false + for i := 0; i < len(s); i++ { + c := s[i] + if c >= utf8.RuneSelf { + isASCII = false + break + } + hasUpper = hasUpper || ('A' <= c && c <= 'Z') + } + + if isASCII { // optimize for ASCII-only byte slices. + if !hasUpper { + return append([]byte(""), s...) + } + b := make([]byte, len(s)) + for i := 0; i < len(s); i++ { + c := s[i] + if 'A' <= c && c <= 'Z' { + c += 'a' - 'A' + } + b[i] = c + } + return b + } + return Map(unicode.ToLower, s) +} + +// ToTitle treats s as UTF-8-encoded bytes and returns a copy with all the Unicode letters mapped to their title case. +func ToTitle(s []byte) []byte { return Map(unicode.ToTitle, s) } + +// ToUpperSpecial treats s as UTF-8-encoded bytes and returns a copy with all the Unicode letters mapped to their +// upper case, giving priority to the special casing rules. +func ToUpperSpecial(c unicode.SpecialCase, s []byte) []byte { + return Map(c.ToUpper, s) +} + +// ToLowerSpecial treats s as UTF-8-encoded bytes and returns a copy with all the Unicode letters mapped to their +// lower case, giving priority to the special casing rules. +func ToLowerSpecial(c unicode.SpecialCase, s []byte) []byte { + return Map(c.ToLower, s) +} + +// ToTitleSpecial treats s as UTF-8-encoded bytes and returns a copy with all the Unicode letters mapped to their +// title case, giving priority to the special casing rules. +func ToTitleSpecial(c unicode.SpecialCase, s []byte) []byte { + return Map(c.ToTitle, s) +} + +// ToValidUTF8 treats s as UTF-8-encoded bytes and returns a copy with each run of bytes +// representing invalid UTF-8 replaced with the bytes in replacement, which may be empty. +func ToValidUTF8(s, replacement []byte) []byte { + b := make([]byte, 0, len(s)+len(replacement)) + invalid := false // previous byte was from an invalid UTF-8 sequence + for i := 0; i < len(s); { + c := s[i] + if c < utf8.RuneSelf { + i++ + invalid = false + b = append(b, c) + continue + } + _, wid := utf8.DecodeRune(s[i:]) + if wid == 1 { + i++ + if !invalid { + invalid = true + b = append(b, replacement...) + } + continue + } + invalid = false + b = append(b, s[i:i+wid]...) + i += wid + } + return b +} + +// isSeparator reports whether the rune could mark a word boundary. +// TODO: update when package unicode captures more of the properties. +func isSeparator(r rune) bool { + // ASCII alphanumerics and underscore are not separators + if r <= 0x7F { + switch { + case '0' <= r && r <= '9': + return false + case 'a' <= r && r <= 'z': + return false + case 'A' <= r && r <= 'Z': + return false + case r == '_': + return false + } + return true + } + // Letters and digits are not separators + if unicode.IsLetter(r) || unicode.IsDigit(r) { + return false + } + // Otherwise, all we can do for now is treat spaces as separators. + return unicode.IsSpace(r) +} + +// Title treats s as UTF-8-encoded bytes and returns a copy with all Unicode letters that begin +// words mapped to their title case. +// +// Deprecated: The rule Title uses for word boundaries does not handle Unicode +// punctuation properly. Use golang.org/x/text/cases instead. +func Title(s []byte) []byte { + // Use a closure here to remember state. + // Hackish but effective. Depends on Map scanning in order and calling + // the closure once per rune. + prev := ' ' + return Map( + func(r rune) rune { + if isSeparator(prev) { + prev = r + return unicode.ToTitle(r) + } + prev = r + return r + }, + s) +} + +// TrimLeftFunc treats s as UTF-8-encoded bytes and returns a subslice of s by slicing off +// all leading UTF-8-encoded code points c that satisfy f(c). +func TrimLeftFunc(s []byte, f func(r rune) bool) []byte { + i := indexFunc(s, f, false) + if i == -1 { + return nil + } + return s[i:] +} + +// TrimRightFunc returns a subslice of s by slicing off all trailing +// UTF-8-encoded code points c that satisfy f(c). +func TrimRightFunc(s []byte, f func(r rune) bool) []byte { + i := lastIndexFunc(s, f, false) + if i >= 0 && s[i] >= utf8.RuneSelf { + _, wid := utf8.DecodeRune(s[i:]) + i += wid + } else { + i++ + } + return s[0:i] +} + +// TrimFunc returns a subslice of s by slicing off all leading and trailing +// UTF-8-encoded code points c that satisfy f(c). +func TrimFunc(s []byte, f func(r rune) bool) []byte { + return TrimRightFunc(TrimLeftFunc(s, f), f) +} + +// TrimPrefix returns s without the provided leading prefix string. +// If s doesn't start with prefix, s is returned unchanged. +func TrimPrefix(s, prefix []byte) []byte { + if HasPrefix(s, prefix) { + return s[len(prefix):] + } + return s +} + +// TrimSuffix returns s without the provided trailing suffix string. +// If s doesn't end with suffix, s is returned unchanged. +func TrimSuffix(s, suffix []byte) []byte { + if HasSuffix(s, suffix) { + return s[:len(s)-len(suffix)] + } + return s +} + +// IndexFunc interprets s as a sequence of UTF-8-encoded code points. +// It returns the byte index in s of the first Unicode +// code point satisfying f(c), or -1 if none do. +func IndexFunc(s []byte, f func(r rune) bool) int { + return indexFunc(s, f, true) +} + +// LastIndexFunc interprets s as a sequence of UTF-8-encoded code points. +// It returns the byte index in s of the last Unicode +// code point satisfying f(c), or -1 if none do. +func LastIndexFunc(s []byte, f func(r rune) bool) int { + return lastIndexFunc(s, f, true) +} + +// indexFunc is the same as IndexFunc except that if +// truth==false, the sense of the predicate function is +// inverted. +func indexFunc(s []byte, f func(r rune) bool, truth bool) int { + start := 0 + for start < len(s) { + wid := 1 + r := rune(s[start]) + if r >= utf8.RuneSelf { + r, wid = utf8.DecodeRune(s[start:]) + } + if f(r) == truth { + return start + } + start += wid + } + return -1 +} + +// lastIndexFunc is the same as LastIndexFunc except that if +// truth==false, the sense of the predicate function is +// inverted. +func lastIndexFunc(s []byte, f func(r rune) bool, truth bool) int { + for i := len(s); i > 0; { + r, size := rune(s[i-1]), 1 + if r >= utf8.RuneSelf { + r, size = utf8.DecodeLastRune(s[0:i]) + } + i -= size + if f(r) == truth { + return i + } + } + return -1 +} + +// asciiSet is a 32-byte value, where each bit represents the presence of a +// given ASCII character in the set. The 128-bits of the lower 16 bytes, +// starting with the least-significant bit of the lowest word to the +// most-significant bit of the highest word, map to the full range of all +// 128 ASCII characters. The 128-bits of the upper 16 bytes will be zeroed, +// ensuring that any non-ASCII character will be reported as not in the set. +// This allocates a total of 32 bytes even though the upper half +// is unused to avoid bounds checks in asciiSet.contains. +type asciiSet [8]uint32 + +// makeASCIISet creates a set of ASCII characters and reports whether all +// characters in chars are ASCII. +func makeASCIISet(chars string) (as asciiSet, ok bool) { + for i := 0; i < len(chars); i++ { + c := chars[i] + if c >= utf8.RuneSelf { + return as, false + } + as[c/32] |= 1 << (c % 32) + } + return as, true +} + +// contains reports whether c is inside the set. +func (as *asciiSet) contains(c byte) bool { + return (as[c/32] & (1 << (c % 32))) != 0 +} + +// containsRune is a simplified version of strings.ContainsRune +// to avoid importing the strings package. +// We avoid bytes.ContainsRune to avoid allocating a temporary copy of s. +func containsRune(s string, r rune) bool { + for _, c := range s { + if c == r { + return true + } + } + return false +} + +// Trim returns a subslice of s by slicing off all leading and +// trailing UTF-8-encoded code points contained in cutset. +func Trim(s []byte, cutset string) []byte { + if len(s) == 0 { + // This is what we've historically done. + return nil + } + if cutset == "" { + return s + } + if len(cutset) == 1 && cutset[0] < utf8.RuneSelf { + return trimLeftByte(trimRightByte(s, cutset[0]), cutset[0]) + } + if as, ok := makeASCIISet(cutset); ok { + return trimLeftASCII(trimRightASCII(s, &as), &as) + } + return trimLeftUnicode(trimRightUnicode(s, cutset), cutset) +} + +// TrimLeft returns a subslice of s by slicing off all leading +// UTF-8-encoded code points contained in cutset. +func TrimLeft(s []byte, cutset string) []byte { + if len(s) == 0 { + // This is what we've historically done. + return nil + } + if cutset == "" { + return s + } + if len(cutset) == 1 && cutset[0] < utf8.RuneSelf { + return trimLeftByte(s, cutset[0]) + } + if as, ok := makeASCIISet(cutset); ok { + return trimLeftASCII(s, &as) + } + return trimLeftUnicode(s, cutset) +} + +func trimLeftByte(s []byte, c byte) []byte { + for len(s) > 0 && s[0] == c { + s = s[1:] + } + if len(s) == 0 { + // This is what we've historically done. + return nil + } + return s +} + +func trimLeftASCII(s []byte, as *asciiSet) []byte { + for len(s) > 0 { + if !as.contains(s[0]) { + break + } + s = s[1:] + } + if len(s) == 0 { + // This is what we've historically done. + return nil + } + return s +} + +func trimLeftUnicode(s []byte, cutset string) []byte { + for len(s) > 0 { + r, n := rune(s[0]), 1 + if r >= utf8.RuneSelf { + r, n = utf8.DecodeRune(s) + } + if !containsRune(cutset, r) { + break + } + s = s[n:] + } + if len(s) == 0 { + // This is what we've historically done. + return nil + } + return s +} + +// TrimRight returns a subslice of s by slicing off all trailing +// UTF-8-encoded code points that are contained in cutset. +func TrimRight(s []byte, cutset string) []byte { + if len(s) == 0 || cutset == "" { + return s + } + if len(cutset) == 1 && cutset[0] < utf8.RuneSelf { + return trimRightByte(s, cutset[0]) + } + if as, ok := makeASCIISet(cutset); ok { + return trimRightASCII(s, &as) + } + return trimRightUnicode(s, cutset) +} + +func trimRightByte(s []byte, c byte) []byte { + for len(s) > 0 && s[len(s)-1] == c { + s = s[:len(s)-1] + } + return s +} + +func trimRightASCII(s []byte, as *asciiSet) []byte { + for len(s) > 0 { + if !as.contains(s[len(s)-1]) { + break + } + s = s[:len(s)-1] + } + return s +} + +func trimRightUnicode(s []byte, cutset string) []byte { + for len(s) > 0 { + r, n := rune(s[len(s)-1]), 1 + if r >= utf8.RuneSelf { + r, n = utf8.DecodeLastRune(s) + } + if !containsRune(cutset, r) { + break + } + s = s[:len(s)-n] + } + return s +} + +// TrimSpace returns a subslice of s by slicing off all leading and +// trailing white space, as defined by Unicode. +func TrimSpace(s []byte) []byte { + // Fast path for ASCII: look for the first ASCII non-space byte + start := 0 + for ; start < len(s); start++ { + c := s[start] + if c >= utf8.RuneSelf { + // If we run into a non-ASCII byte, fall back to the + // slower unicode-aware method on the remaining bytes + return TrimFunc(s[start:], unicode.IsSpace) + } + if asciiSpace[c] == 0 { + break + } + } + + // Now look for the first ASCII non-space byte from the end + stop := len(s) + for ; stop > start; stop-- { + c := s[stop-1] + if c >= utf8.RuneSelf { + return TrimFunc(s[start:stop], unicode.IsSpace) + } + if asciiSpace[c] == 0 { + break + } + } + + // At this point s[start:stop] starts and ends with an ASCII + // non-space bytes, so we're done. Non-ASCII cases have already + // been handled above. + if start == stop { + // Special case to preserve previous TrimLeftFunc behavior, + // returning nil instead of empty slice if all spaces. + return nil + } + return s[start:stop] +} + +// Runes interprets s as a sequence of UTF-8-encoded code points. +// It returns a slice of runes (Unicode code points) equivalent to s. +func Runes(s []byte) []rune { + t := make([]rune, utf8.RuneCount(s)) + i := 0 + for len(s) > 0 { + r, l := utf8.DecodeRune(s) + t[i] = r + i++ + s = s[l:] + } + return t +} + +// Replace returns a copy of the slice s with the first n +// non-overlapping instances of old replaced by new. +// If old is empty, it matches at the beginning of the slice +// and after each UTF-8 sequence, yielding up to k+1 replacements +// for a k-rune slice. +// If n < 0, there is no limit on the number of replacements. +func Replace(s, old, new []byte, n int) []byte { + m := 0 + if n != 0 { + // Compute number of replacements. + m = Count(s, old) + } + if m == 0 { + // Just return a copy. + return append([]byte(nil), s...) + } + if n < 0 || m < n { + n = m + } + + // Apply replacements to buffer. + t := make([]byte, len(s)+n*(len(new)-len(old))) + w := 0 + start := 0 + for i := 0; i < n; i++ { + j := start + if len(old) == 0 { + if i > 0 { + _, wid := utf8.DecodeRune(s[start:]) + j += wid + } + } else { + j += Index(s[start:], old) + } + w += copy(t[w:], s[start:j]) + w += copy(t[w:], new) + start = j + len(old) + } + w += copy(t[w:], s[start:]) + return t[0:w] +} + +// ReplaceAll returns a copy of the slice s with all +// non-overlapping instances of old replaced by new. +// If old is empty, it matches at the beginning of the slice +// and after each UTF-8 sequence, yielding up to k+1 replacements +// for a k-rune slice. +func ReplaceAll(s, old, new []byte) []byte { + return Replace(s, old, new, -1) +} + +// EqualFold reports whether s and t, interpreted as UTF-8 strings, +// are equal under simple Unicode case-folding, which is a more general +// form of case-insensitivity. +func EqualFold(s, t []byte) bool { + // ASCII fast path + i := 0 + for ; i < len(s) && i < len(t); i++ { + sr := s[i] + tr := t[i] + if sr|tr >= utf8.RuneSelf { + goto hasUnicode + } + + // Easy case. + if tr == sr { + continue + } + + // Make sr < tr to simplify what follows. + if tr < sr { + tr, sr = sr, tr + } + // ASCII only, sr/tr must be upper/lower case + if 'A' <= sr && sr <= 'Z' && tr == sr+'a'-'A' { + continue + } + return false + } + // Check if we've exhausted both strings. + return len(s) == len(t) + +hasUnicode: + s = s[i:] + t = t[i:] + for len(s) != 0 && len(t) != 0 { + // Extract first rune from each. + var sr, tr rune + if s[0] < utf8.RuneSelf { + sr, s = rune(s[0]), s[1:] + } else { + r, size := utf8.DecodeRune(s) + sr, s = r, s[size:] + } + if t[0] < utf8.RuneSelf { + tr, t = rune(t[0]), t[1:] + } else { + r, size := utf8.DecodeRune(t) + tr, t = r, t[size:] + } + + // If they match, keep going; if not, return false. + + // Easy case. + if tr == sr { + continue + } + + // Make sr < tr to simplify what follows. + if tr < sr { + tr, sr = sr, tr + } + // Fast check for ASCII. + if tr < utf8.RuneSelf { + // ASCII only, sr/tr must be upper/lower case + if 'A' <= sr && sr <= 'Z' && tr == sr+'a'-'A' { + continue + } + return false + } + + // General case. SimpleFold(x) returns the next equivalent rune > x + // or wraps around to smaller values. + r := unicode.SimpleFold(sr) + for r != sr && r < tr { + r = unicode.SimpleFold(r) + } + if r == tr { + continue + } + return false + } + + // One string is empty. Are both? + return len(s) == len(t) +} + +// Index returns the index of the first instance of sep in s, or -1 if sep is not present in s. +func Index(s, sep []byte) int { + n := len(sep) + switch { + case n == 0: + return 0 + case n == 1: + return IndexByte(s, sep[0]) + case n == len(s): + if Equal(sep, s) { + return 0 + } + return -1 + case n > len(s): + return -1 + case n <= bytealg.MaxLen: + // Use brute force when s and sep both are small + if len(s) <= bytealg.MaxBruteForce { + return bytealg.Index(s, sep) + } + c0 := sep[0] + c1 := sep[1] + i := 0 + t := len(s) - n + 1 + fails := 0 + for i < t { + if s[i] != c0 { + // IndexByte is faster than bytealg.Index, so use it as long as + // we're not getting lots of false positives. + o := IndexByte(s[i+1:t], c0) + if o < 0 { + return -1 + } + i += o + 1 + } + if s[i+1] == c1 && Equal(s[i:i+n], sep) { + return i + } + fails++ + i++ + // Switch to bytealg.Index when IndexByte produces too many false positives. + if fails > bytealg.Cutover(i) { + r := bytealg.Index(s[i:], sep) + if r >= 0 { + return r + i + } + return -1 + } + } + return -1 + } + c0 := sep[0] + c1 := sep[1] + i := 0 + fails := 0 + t := len(s) - n + 1 + for i < t { + if s[i] != c0 { + o := IndexByte(s[i+1:t], c0) + if o < 0 { + break + } + i += o + 1 + } + if s[i+1] == c1 && Equal(s[i:i+n], sep) { + return i + } + i++ + fails++ + if fails >= 4+i>>4 && i < t { + // Give up on IndexByte, it isn't skipping ahead + // far enough to be better than Rabin-Karp. + // Experiments (using IndexPeriodic) suggest + // the cutover is about 16 byte skips. + // TODO: if large prefixes of sep are matching + // we should cutover at even larger average skips, + // because Equal becomes that much more expensive. + // This code does not take that effect into account. + j := bytealg.IndexRabinKarpBytes(s[i:], sep) + if j < 0 { + return -1 + } + return i + j + } + } + return -1 +} + +// Cut slices s around the first instance of sep, +// returning the text before and after sep. +// The found result reports whether sep appears in s. +// If sep does not appear in s, cut returns s, nil, false. +// +// Cut returns slices of the original slice s, not copies. +func Cut(s, sep []byte) (before, after []byte, found bool) { + if i := Index(s, sep); i >= 0 { + return s[:i], s[i+len(sep):], true + } + return s, nil, false +} + +// Clone returns a copy of b[:len(b)]. +// The result may have additional unused capacity. +// Clone(nil) returns nil. +func Clone(b []byte) []byte { + if b == nil { + return nil + } + return append([]byte{}, b...) +} + +// CutPrefix returns s without the provided leading prefix byte slice +// and reports whether it found the prefix. +// If s doesn't start with prefix, CutPrefix returns s, false. +// If prefix is the empty byte slice, CutPrefix returns s, true. +// +// CutPrefix returns slices of the original slice s, not copies. +func CutPrefix(s, prefix []byte) (after []byte, found bool) { + if !HasPrefix(s, prefix) { + return s, false + } + return s[len(prefix):], true +} + +// CutSuffix returns s without the provided ending suffix byte slice +// and reports whether it found the suffix. +// If s doesn't end with suffix, CutSuffix returns s, false. +// If suffix is the empty byte slice, CutSuffix returns s, true. +// +// CutSuffix returns slices of the original slice s, not copies. +func CutSuffix(s, suffix []byte) (before []byte, found bool) { + if !HasSuffix(s, suffix) { + return s, false + } + return s[:len(s)-len(suffix)], true +} diff --git a/src/bytes/bytes_test.go b/src/bytes/bytes_test.go new file mode 100644 index 0000000..f58f18c --- /dev/null +++ b/src/bytes/bytes_test.go @@ -0,0 +1,2217 @@ +// Copyright 2009 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 bytes_test + +import ( + . "bytes" + "fmt" + "internal/testenv" + "math" + "math/rand" + "reflect" + "strings" + "testing" + "unicode" + "unicode/utf8" + "unsafe" +) + +func eq(a, b []string) bool { + if len(a) != len(b) { + return false + } + for i := 0; i < len(a); i++ { + if a[i] != b[i] { + return false + } + } + return true +} + +func sliceOfString(s [][]byte) []string { + result := make([]string, len(s)) + for i, v := range s { + result[i] = string(v) + } + return result +} + +// For ease of reading, the test cases use strings that are converted to byte +// slices before invoking the functions. + +var abcd = "abcd" +var faces = "☺☻☹" +var commas = "1,2,3,4" +var dots = "1....2....3....4" + +type BinOpTest struct { + a string + b string + i int +} + +func TestEqual(t *testing.T) { + // Run the tests and check for allocation at the same time. + allocs := testing.AllocsPerRun(10, func() { + for _, tt := range compareTests { + eql := Equal(tt.a, tt.b) + if eql != (tt.i == 0) { + t.Errorf(`Equal(%q, %q) = %v`, tt.a, tt.b, eql) + } + } + }) + if allocs > 0 { + t.Errorf("Equal allocated %v times", allocs) + } +} + +func TestEqualExhaustive(t *testing.T) { + var size = 128 + if testing.Short() { + size = 32 + } + a := make([]byte, size) + b := make([]byte, size) + b_init := make([]byte, size) + // randomish but deterministic data + for i := 0; i < size; i++ { + a[i] = byte(17 * i) + b_init[i] = byte(23*i + 100) + } + + for len := 0; len <= size; len++ { + for x := 0; x <= size-len; x++ { + for y := 0; y <= size-len; y++ { + copy(b, b_init) + copy(b[y:y+len], a[x:x+len]) + if !Equal(a[x:x+len], b[y:y+len]) || !Equal(b[y:y+len], a[x:x+len]) { + t.Errorf("Equal(%d, %d, %d) = false", len, x, y) + } + } + } + } +} + +// make sure Equal returns false for minimally different strings. The data +// is all zeros except for a single one in one location. +func TestNotEqual(t *testing.T) { + var size = 128 + if testing.Short() { + size = 32 + } + a := make([]byte, size) + b := make([]byte, size) + + for len := 0; len <= size; len++ { + for x := 0; x <= size-len; x++ { + for y := 0; y <= size-len; y++ { + for diffpos := x; diffpos < x+len; diffpos++ { + a[diffpos] = 1 + if Equal(a[x:x+len], b[y:y+len]) || Equal(b[y:y+len], a[x:x+len]) { + t.Errorf("NotEqual(%d, %d, %d, %d) = true", len, x, y, diffpos) + } + a[diffpos] = 0 + } + } + } + } +} + +var indexTests = []BinOpTest{ + {"", "", 0}, + {"", "a", -1}, + {"", "foo", -1}, + {"fo", "foo", -1}, + {"foo", "baz", -1}, + {"foo", "foo", 0}, + {"oofofoofooo", "f", 2}, + {"oofofoofooo", "foo", 4}, + {"barfoobarfoo", "foo", 3}, + {"foo", "", 0}, + {"foo", "o", 1}, + {"abcABCabc", "A", 3}, + // cases with one byte strings - test IndexByte and special case in Index() + {"", "a", -1}, + {"x", "a", -1}, + {"x", "x", 0}, + {"abc", "a", 0}, + {"abc", "b", 1}, + {"abc", "c", 2}, + {"abc", "x", -1}, + {"barfoobarfooyyyzzzyyyzzzyyyzzzyyyxxxzzzyyy", "x", 33}, + {"fofofofooofoboo", "oo", 7}, + {"fofofofofofoboo", "ob", 11}, + {"fofofofofofoboo", "boo", 12}, + {"fofofofofofoboo", "oboo", 11}, + {"fofofofofoooboo", "fooo", 8}, + {"fofofofofofoboo", "foboo", 10}, + {"fofofofofofoboo", "fofob", 8}, + {"fofofofofofofoffofoobarfoo", "foffof", 12}, + {"fofofofofoofofoffofoobarfoo", "foffof", 13}, + {"fofofofofofofoffofoobarfoo", "foffofo", 12}, + {"fofofofofoofofoffofoobarfoo", "foffofo", 13}, + {"fofofofofoofofoffofoobarfoo", "foffofoo", 13}, + {"fofofofofofofoffofoobarfoo", "foffofoo", 12}, + {"fofofofofoofofoffofoobarfoo", "foffofoob", 13}, + {"fofofofofofofoffofoobarfoo", "foffofoob", 12}, + {"fofofofofoofofoffofoobarfoo", "foffofooba", 13}, + {"fofofofofofofoffofoobarfoo", "foffofooba", 12}, + {"fofofofofoofofoffofoobarfoo", "foffofoobar", 13}, + {"fofofofofofofoffofoobarfoo", "foffofoobar", 12}, + {"fofofofofoofofoffofoobarfoo", "foffofoobarf", 13}, + {"fofofofofofofoffofoobarfoo", "foffofoobarf", 12}, + {"fofofofofoofofoffofoobarfoo", "foffofoobarfo", 13}, + {"fofofofofofofoffofoobarfoo", "foffofoobarfo", 12}, + {"fofofofofoofofoffofoobarfoo", "foffofoobarfoo", 13}, + {"fofofofofofofoffofoobarfoo", "foffofoobarfoo", 12}, + {"fofofofofoofofoffofoobarfoo", "ofoffofoobarfoo", 12}, + {"fofofofofofofoffofoobarfoo", "ofoffofoobarfoo", 11}, + {"fofofofofoofofoffofoobarfoo", "fofoffofoobarfoo", 11}, + {"fofofofofofofoffofoobarfoo", "fofoffofoobarfoo", 10}, + {"fofofofofoofofoffofoobarfoo", "foobars", -1}, + {"foofyfoobarfoobar", "y", 4}, + {"oooooooooooooooooooooo", "r", -1}, + {"oxoxoxoxoxoxoxoxoxoxoxoy", "oy", 22}, + {"oxoxoxoxoxoxoxoxoxoxoxox", "oy", -1}, + // test fallback to Rabin-Karp. + {"000000000000000000000000000000000000000000000000000000000000000000000001", "0000000000000000000000000000000000000000000000000000000000000000001", 5}, +} + +var lastIndexTests = []BinOpTest{ + {"", "", 0}, + {"", "a", -1}, + {"", "foo", -1}, + {"fo", "foo", -1}, + {"foo", "foo", 0}, + {"foo", "f", 0}, + {"oofofoofooo", "f", 7}, + {"oofofoofooo", "foo", 7}, + {"barfoobarfoo", "foo", 9}, + {"foo", "", 3}, + {"foo", "o", 2}, + {"abcABCabc", "A", 3}, + {"abcABCabc", "a", 6}, +} + +var indexAnyTests = []BinOpTest{ + {"", "", -1}, + {"", "a", -1}, + {"", "abc", -1}, + {"a", "", -1}, + {"a", "a", 0}, + {"\x80", "\xffb", 0}, + {"aaa", "a", 0}, + {"abc", "xyz", -1}, + {"abc", "xcz", 2}, + {"ab☺c", "x☺yz", 2}, + {"a☺b☻c☹d", "cx", len("a☺b☻")}, + {"a☺b☻c☹d", "uvw☻xyz", len("a☺b")}, + {"aRegExp*", ".(|)*+?^$[]", 7}, + {dots + dots + dots, " ", -1}, + {"012abcba210", "\xffb", 4}, + {"012\x80bcb\x80210", "\xffb", 3}, + {"0123456\xcf\x80abc", "\xcfb\x80", 10}, +} + +var lastIndexAnyTests = []BinOpTest{ + {"", "", -1}, + {"", "a", -1}, + {"", "abc", -1}, + {"a", "", -1}, + {"a", "a", 0}, + {"\x80", "\xffb", 0}, + {"aaa", "a", 2}, + {"abc", "xyz", -1}, + {"abc", "ab", 1}, + {"ab☺c", "x☺yz", 2}, + {"a☺b☻c☹d", "cx", len("a☺b☻")}, + {"a☺b☻c☹d", "uvw☻xyz", len("a☺b")}, + {"a.RegExp*", ".(|)*+?^$[]", 8}, + {dots + dots + dots, " ", -1}, + {"012abcba210", "\xffb", 6}, + {"012\x80bcb\x80210", "\xffb", 7}, + {"0123456\xcf\x80abc", "\xcfb\x80", 10}, +} + +// Execute f on each test case. funcName should be the name of f; it's used +// in failure reports. +func runIndexTests(t *testing.T, f func(s, sep []byte) int, funcName string, testCases []BinOpTest) { + for _, test := range testCases { + a := []byte(test.a) + b := []byte(test.b) + actual := f(a, b) + if actual != test.i { + t.Errorf("%s(%q,%q) = %v; want %v", funcName, a, b, actual, test.i) + } + } + var allocTests = []struct { + a []byte + b []byte + i int + }{ + // case for function Index. + {[]byte("000000000000000000000000000000000000000000000000000000000000000000000001"), []byte("0000000000000000000000000000000000000000000000000000000000000000001"), 5}, + // case for function LastIndex. + {[]byte("000000000000000000000000000000000000000000000000000000000000000010000"), []byte("00000000000000000000000000000000000000000000000000000000000001"), 3}, + } + allocs := testing.AllocsPerRun(100, func() { + if i := Index(allocTests[1].a, allocTests[1].b); i != allocTests[1].i { + t.Errorf("Index([]byte(%q), []byte(%q)) = %v; want %v", allocTests[1].a, allocTests[1].b, i, allocTests[1].i) + } + if i := LastIndex(allocTests[0].a, allocTests[0].b); i != allocTests[0].i { + t.Errorf("LastIndex([]byte(%q), []byte(%q)) = %v; want %v", allocTests[0].a, allocTests[0].b, i, allocTests[0].i) + } + }) + if allocs != 0 { + t.Errorf("expected no allocations, got %f", allocs) + } +} + +func runIndexAnyTests(t *testing.T, f func(s []byte, chars string) int, funcName string, testCases []BinOpTest) { + for _, test := range testCases { + a := []byte(test.a) + actual := f(a, test.b) + if actual != test.i { + t.Errorf("%s(%q,%q) = %v; want %v", funcName, a, test.b, actual, test.i) + } + } +} + +func TestIndex(t *testing.T) { runIndexTests(t, Index, "Index", indexTests) } +func TestLastIndex(t *testing.T) { runIndexTests(t, LastIndex, "LastIndex", lastIndexTests) } +func TestIndexAny(t *testing.T) { runIndexAnyTests(t, IndexAny, "IndexAny", indexAnyTests) } +func TestLastIndexAny(t *testing.T) { + runIndexAnyTests(t, LastIndexAny, "LastIndexAny", lastIndexAnyTests) +} + +func TestIndexByte(t *testing.T) { + for _, tt := range indexTests { + if len(tt.b) != 1 { + continue + } + a := []byte(tt.a) + b := tt.b[0] + pos := IndexByte(a, b) + if pos != tt.i { + t.Errorf(`IndexByte(%q, '%c') = %v`, tt.a, b, pos) + } + posp := IndexBytePortable(a, b) + if posp != tt.i { + t.Errorf(`indexBytePortable(%q, '%c') = %v`, tt.a, b, posp) + } + } +} + +func TestLastIndexByte(t *testing.T) { + testCases := []BinOpTest{ + {"", "q", -1}, + {"abcdef", "q", -1}, + {"abcdefabcdef", "a", len("abcdef")}, // something in the middle + {"abcdefabcdef", "f", len("abcdefabcde")}, // last byte + {"zabcdefabcdef", "z", 0}, // first byte + {"a☺b☻c☹d", "b", len("a☺")}, // non-ascii + } + for _, test := range testCases { + actual := LastIndexByte([]byte(test.a), test.b[0]) + if actual != test.i { + t.Errorf("LastIndexByte(%q,%c) = %v; want %v", test.a, test.b[0], actual, test.i) + } + } +} + +// test a larger buffer with different sizes and alignments +func TestIndexByteBig(t *testing.T) { + var n = 1024 + if testing.Short() { + n = 128 + } + b := make([]byte, n) + for i := 0; i < n; i++ { + // different start alignments + b1 := b[i:] + for j := 0; j < len(b1); j++ { + b1[j] = 'x' + pos := IndexByte(b1, 'x') + if pos != j { + t.Errorf("IndexByte(%q, 'x') = %v", b1, pos) + } + b1[j] = 0 + pos = IndexByte(b1, 'x') + if pos != -1 { + t.Errorf("IndexByte(%q, 'x') = %v", b1, pos) + } + } + // different end alignments + b1 = b[:i] + for j := 0; j < len(b1); j++ { + b1[j] = 'x' + pos := IndexByte(b1, 'x') + if pos != j { + t.Errorf("IndexByte(%q, 'x') = %v", b1, pos) + } + b1[j] = 0 + pos = IndexByte(b1, 'x') + if pos != -1 { + t.Errorf("IndexByte(%q, 'x') = %v", b1, pos) + } + } + // different start and end alignments + b1 = b[i/2 : n-(i+1)/2] + for j := 0; j < len(b1); j++ { + b1[j] = 'x' + pos := IndexByte(b1, 'x') + if pos != j { + t.Errorf("IndexByte(%q, 'x') = %v", b1, pos) + } + b1[j] = 0 + pos = IndexByte(b1, 'x') + if pos != -1 { + t.Errorf("IndexByte(%q, 'x') = %v", b1, pos) + } + } + } +} + +// test a small index across all page offsets +func TestIndexByteSmall(t *testing.T) { + b := make([]byte, 5015) // bigger than a page + // Make sure we find the correct byte even when straddling a page. + for i := 0; i <= len(b)-15; i++ { + for j := 0; j < 15; j++ { + b[i+j] = byte(100 + j) + } + for j := 0; j < 15; j++ { + p := IndexByte(b[i:i+15], byte(100+j)) + if p != j { + t.Errorf("IndexByte(%q, %d) = %d", b[i:i+15], 100+j, p) + } + } + for j := 0; j < 15; j++ { + b[i+j] = 0 + } + } + // Make sure matches outside the slice never trigger. + for i := 0; i <= len(b)-15; i++ { + for j := 0; j < 15; j++ { + b[i+j] = 1 + } + for j := 0; j < 15; j++ { + p := IndexByte(b[i:i+15], byte(0)) + if p != -1 { + t.Errorf("IndexByte(%q, %d) = %d", b[i:i+15], 0, p) + } + } + for j := 0; j < 15; j++ { + b[i+j] = 0 + } + } +} + +func TestIndexRune(t *testing.T) { + tests := []struct { + in string + rune rune + want int + }{ + {"", 'a', -1}, + {"", '☺', -1}, + {"foo", '☹', -1}, + {"foo", 'o', 1}, + {"foo☺bar", '☺', 3}, + {"foo☺☻☹bar", '☹', 9}, + {"a A x", 'A', 2}, + {"some_text=some_value", '=', 9}, + {"☺a", 'a', 3}, + {"a☻☺b", '☺', 4}, + + // RuneError should match any invalid UTF-8 byte sequence. + {"�", '�', 0}, + {"\xff", '�', 0}, + {"☻x�", '�', len("☻x")}, + {"☻x\xe2\x98", '�', len("☻x")}, + {"☻x\xe2\x98�", '�', len("☻x")}, + {"☻x\xe2\x98x", '�', len("☻x")}, + + // Invalid rune values should never match. + {"a☺b☻c☹d\xe2\x98�\xff�\xed\xa0\x80", -1, -1}, + {"a☺b☻c☹d\xe2\x98�\xff�\xed\xa0\x80", 0xD800, -1}, // Surrogate pair + {"a☺b☻c☹d\xe2\x98�\xff�\xed\xa0\x80", utf8.MaxRune + 1, -1}, + } + for _, tt := range tests { + if got := IndexRune([]byte(tt.in), tt.rune); got != tt.want { + t.Errorf("IndexRune(%q, %d) = %v; want %v", tt.in, tt.rune, got, tt.want) + } + } + + haystack := []byte("test世界") + allocs := testing.AllocsPerRun(1000, func() { + if i := IndexRune(haystack, 's'); i != 2 { + t.Fatalf("'s' at %d; want 2", i) + } + if i := IndexRune(haystack, '世'); i != 4 { + t.Fatalf("'世' at %d; want 4", i) + } + }) + if allocs != 0 { + t.Errorf("expected no allocations, got %f", allocs) + } +} + +// test count of a single byte across page offsets +func TestCountByte(t *testing.T) { + b := make([]byte, 5015) // bigger than a page + windows := []int{1, 2, 3, 4, 15, 16, 17, 31, 32, 33, 63, 64, 65, 128} + testCountWindow := func(i, window int) { + for j := 0; j < window; j++ { + b[i+j] = byte(100) + p := Count(b[i:i+window], []byte{100}) + if p != j+1 { + t.Errorf("TestCountByte.Count(%q, 100) = %d", b[i:i+window], p) + } + } + } + + maxWnd := windows[len(windows)-1] + + for i := 0; i <= 2*maxWnd; i++ { + for _, window := range windows { + if window > len(b[i:]) { + window = len(b[i:]) + } + testCountWindow(i, window) + for j := 0; j < window; j++ { + b[i+j] = byte(0) + } + } + } + for i := 4096 - (maxWnd + 1); i < len(b); i++ { + for _, window := range windows { + if window > len(b[i:]) { + window = len(b[i:]) + } + testCountWindow(i, window) + for j := 0; j < window; j++ { + b[i+j] = byte(0) + } + } + } +} + +// Make sure we don't count bytes outside our window +func TestCountByteNoMatch(t *testing.T) { + b := make([]byte, 5015) + windows := []int{1, 2, 3, 4, 15, 16, 17, 31, 32, 33, 63, 64, 65, 128} + for i := 0; i <= len(b); i++ { + for _, window := range windows { + if window > len(b[i:]) { + window = len(b[i:]) + } + // Fill the window with non-match + for j := 0; j < window; j++ { + b[i+j] = byte(100) + } + // Try to find something that doesn't exist + p := Count(b[i:i+window], []byte{0}) + if p != 0 { + t.Errorf("TestCountByteNoMatch(%q, 0) = %d", b[i:i+window], p) + } + for j := 0; j < window; j++ { + b[i+j] = byte(0) + } + } + } +} + +var bmbuf []byte + +func valName(x int) string { + if s := x >> 20; s<<20 == x { + return fmt.Sprintf("%dM", s) + } + if s := x >> 10; s<<10 == x { + return fmt.Sprintf("%dK", s) + } + return fmt.Sprint(x) +} + +func benchBytes(b *testing.B, sizes []int, f func(b *testing.B, n int)) { + for _, n := range sizes { + if isRaceBuilder && n > 4<<10 { + continue + } + b.Run(valName(n), func(b *testing.B) { + if len(bmbuf) < n { + bmbuf = make([]byte, n) + } + b.SetBytes(int64(n)) + f(b, n) + }) + } +} + +var indexSizes = []int{10, 32, 4 << 10, 4 << 20, 64 << 20} + +var isRaceBuilder = strings.HasSuffix(testenv.Builder(), "-race") + +func BenchmarkIndexByte(b *testing.B) { + benchBytes(b, indexSizes, bmIndexByte(IndexByte)) +} + +func BenchmarkIndexBytePortable(b *testing.B) { + benchBytes(b, indexSizes, bmIndexByte(IndexBytePortable)) +} + +func bmIndexByte(index func([]byte, byte) int) func(b *testing.B, n int) { + return func(b *testing.B, n int) { + buf := bmbuf[0:n] + buf[n-1] = 'x' + for i := 0; i < b.N; i++ { + j := index(buf, 'x') + if j != n-1 { + b.Fatal("bad index", j) + } + } + buf[n-1] = '\x00' + } +} + +func BenchmarkIndexRune(b *testing.B) { + benchBytes(b, indexSizes, bmIndexRune(IndexRune)) +} + +func BenchmarkIndexRuneASCII(b *testing.B) { + benchBytes(b, indexSizes, bmIndexRuneASCII(IndexRune)) +} + +func bmIndexRuneASCII(index func([]byte, rune) int) func(b *testing.B, n int) { + return func(b *testing.B, n int) { + buf := bmbuf[0:n] + buf[n-1] = 'x' + for i := 0; i < b.N; i++ { + j := index(buf, 'x') + if j != n-1 { + b.Fatal("bad index", j) + } + } + buf[n-1] = '\x00' + } +} + +func bmIndexRune(index func([]byte, rune) int) func(b *testing.B, n int) { + return func(b *testing.B, n int) { + buf := bmbuf[0:n] + utf8.EncodeRune(buf[n-3:], '世') + for i := 0; i < b.N; i++ { + j := index(buf, '世') + if j != n-3 { + b.Fatal("bad index", j) + } + } + buf[n-3] = '\x00' + buf[n-2] = '\x00' + buf[n-1] = '\x00' + } +} + +func BenchmarkEqual(b *testing.B) { + b.Run("0", func(b *testing.B) { + var buf [4]byte + buf1 := buf[0:0] + buf2 := buf[1:1] + for i := 0; i < b.N; i++ { + eq := Equal(buf1, buf2) + if !eq { + b.Fatal("bad equal") + } + } + }) + + sizes := []int{1, 6, 9, 15, 16, 20, 32, 4 << 10, 4 << 20, 64 << 20} + benchBytes(b, sizes, bmEqual(Equal)) +} + +func bmEqual(equal func([]byte, []byte) bool) func(b *testing.B, n int) { + return func(b *testing.B, n int) { + if len(bmbuf) < 2*n { + bmbuf = make([]byte, 2*n) + } + buf1 := bmbuf[0:n] + buf2 := bmbuf[n : 2*n] + buf1[n-1] = 'x' + buf2[n-1] = 'x' + for i := 0; i < b.N; i++ { + eq := equal(buf1, buf2) + if !eq { + b.Fatal("bad equal") + } + } + buf1[n-1] = '\x00' + buf2[n-1] = '\x00' + } +} + +func BenchmarkIndex(b *testing.B) { + benchBytes(b, indexSizes, func(b *testing.B, n int) { + buf := bmbuf[0:n] + buf[n-1] = 'x' + for i := 0; i < b.N; i++ { + j := Index(buf, buf[n-7:]) + if j != n-7 { + b.Fatal("bad index", j) + } + } + buf[n-1] = '\x00' + }) +} + +func BenchmarkIndexEasy(b *testing.B) { + benchBytes(b, indexSizes, func(b *testing.B, n int) { + buf := bmbuf[0:n] + buf[n-1] = 'x' + buf[n-7] = 'x' + for i := 0; i < b.N; i++ { + j := Index(buf, buf[n-7:]) + if j != n-7 { + b.Fatal("bad index", j) + } + } + buf[n-1] = '\x00' + buf[n-7] = '\x00' + }) +} + +func BenchmarkCount(b *testing.B) { + benchBytes(b, indexSizes, func(b *testing.B, n int) { + buf := bmbuf[0:n] + buf[n-1] = 'x' + for i := 0; i < b.N; i++ { + j := Count(buf, buf[n-7:]) + if j != 1 { + b.Fatal("bad count", j) + } + } + buf[n-1] = '\x00' + }) +} + +func BenchmarkCountEasy(b *testing.B) { + benchBytes(b, indexSizes, func(b *testing.B, n int) { + buf := bmbuf[0:n] + buf[n-1] = 'x' + buf[n-7] = 'x' + for i := 0; i < b.N; i++ { + j := Count(buf, buf[n-7:]) + if j != 1 { + b.Fatal("bad count", j) + } + } + buf[n-1] = '\x00' + buf[n-7] = '\x00' + }) +} + +func BenchmarkCountSingle(b *testing.B) { + benchBytes(b, indexSizes, func(b *testing.B, n int) { + buf := bmbuf[0:n] + step := 8 + for i := 0; i < len(buf); i += step { + buf[i] = 1 + } + expect := (len(buf) + (step - 1)) / step + for i := 0; i < b.N; i++ { + j := Count(buf, []byte{1}) + if j != expect { + b.Fatal("bad count", j, expect) + } + } + for i := 0; i < len(buf); i++ { + buf[i] = 0 + } + }) +} + +type SplitTest struct { + s string + sep string + n int + a []string +} + +var splittests = []SplitTest{ + {"", "", -1, []string{}}, + {abcd, "a", 0, nil}, + {abcd, "", 2, []string{"a", "bcd"}}, + {abcd, "a", -1, []string{"", "bcd"}}, + {abcd, "z", -1, []string{"abcd"}}, + {abcd, "", -1, []string{"a", "b", "c", "d"}}, + {commas, ",", -1, []string{"1", "2", "3", "4"}}, + {dots, "...", -1, []string{"1", ".2", ".3", ".4"}}, + {faces, "☹", -1, []string{"☺☻", ""}}, + {faces, "~", -1, []string{faces}}, + {faces, "", -1, []string{"☺", "☻", "☹"}}, + {"1 2 3 4", " ", 3, []string{"1", "2", "3 4"}}, + {"1 2", " ", 3, []string{"1", "2"}}, + {"123", "", 2, []string{"1", "23"}}, + {"123", "", 17, []string{"1", "2", "3"}}, + {"bT", "T", math.MaxInt / 4, []string{"b", ""}}, + {"\xff-\xff", "", -1, []string{"\xff", "-", "\xff"}}, + {"\xff-\xff", "-", -1, []string{"\xff", "\xff"}}, +} + +func TestSplit(t *testing.T) { + for _, tt := range splittests { + a := SplitN([]byte(tt.s), []byte(tt.sep), tt.n) + + // Appending to the results should not change future results. + var x []byte + for _, v := range a { + x = append(v, 'z') + } + + result := sliceOfString(a) + if !eq(result, tt.a) { + t.Errorf(`Split(%q, %q, %d) = %v; want %v`, tt.s, tt.sep, tt.n, result, tt.a) + continue + } + if tt.n == 0 || len(a) == 0 { + continue + } + + if want := tt.a[len(tt.a)-1] + "z"; string(x) != want { + t.Errorf("last appended result was %s; want %s", x, want) + } + + s := Join(a, []byte(tt.sep)) + if string(s) != tt.s { + t.Errorf(`Join(Split(%q, %q, %d), %q) = %q`, tt.s, tt.sep, tt.n, tt.sep, s) + } + if tt.n < 0 { + b := Split([]byte(tt.s), []byte(tt.sep)) + if !reflect.DeepEqual(a, b) { + t.Errorf("Split disagrees withSplitN(%q, %q, %d) = %v; want %v", tt.s, tt.sep, tt.n, b, a) + } + } + if len(a) > 0 { + in, out := a[0], s + if cap(in) == cap(out) && &in[:1][0] == &out[:1][0] { + t.Errorf("Join(%#v, %q) didn't copy", a, tt.sep) + } + } + } +} + +var splitaftertests = []SplitTest{ + {abcd, "a", -1, []string{"a", "bcd"}}, + {abcd, "z", -1, []string{"abcd"}}, + {abcd, "", -1, []string{"a", "b", "c", "d"}}, + {commas, ",", -1, []string{"1,", "2,", "3,", "4"}}, + {dots, "...", -1, []string{"1...", ".2...", ".3...", ".4"}}, + {faces, "☹", -1, []string{"☺☻☹", ""}}, + {faces, "~", -1, []string{faces}}, + {faces, "", -1, []string{"☺", "☻", "☹"}}, + {"1 2 3 4", " ", 3, []string{"1 ", "2 ", "3 4"}}, + {"1 2 3", " ", 3, []string{"1 ", "2 ", "3"}}, + {"1 2", " ", 3, []string{"1 ", "2"}}, + {"123", "", 2, []string{"1", "23"}}, + {"123", "", 17, []string{"1", "2", "3"}}, +} + +func TestSplitAfter(t *testing.T) { + for _, tt := range splitaftertests { + a := SplitAfterN([]byte(tt.s), []byte(tt.sep), tt.n) + + // Appending to the results should not change future results. + var x []byte + for _, v := range a { + x = append(v, 'z') + } + + result := sliceOfString(a) + if !eq(result, tt.a) { + t.Errorf(`Split(%q, %q, %d) = %v; want %v`, tt.s, tt.sep, tt.n, result, tt.a) + continue + } + + if want := tt.a[len(tt.a)-1] + "z"; string(x) != want { + t.Errorf("last appended result was %s; want %s", x, want) + } + + s := Join(a, nil) + if string(s) != tt.s { + t.Errorf(`Join(Split(%q, %q, %d), %q) = %q`, tt.s, tt.sep, tt.n, tt.sep, s) + } + if tt.n < 0 { + b := SplitAfter([]byte(tt.s), []byte(tt.sep)) + if !reflect.DeepEqual(a, b) { + t.Errorf("SplitAfter disagrees withSplitAfterN(%q, %q, %d) = %v; want %v", tt.s, tt.sep, tt.n, b, a) + } + } + } +} + +type FieldsTest struct { + s string + a []string +} + +var fieldstests = []FieldsTest{ + {"", []string{}}, + {" ", []string{}}, + {" \t ", []string{}}, + {" abc ", []string{"abc"}}, + {"1 2 3 4", []string{"1", "2", "3", "4"}}, + {"1 2 3 4", []string{"1", "2", "3", "4"}}, + {"1\t\t2\t\t3\t4", []string{"1", "2", "3", "4"}}, + {"1\u20002\u20013\u20024", []string{"1", "2", "3", "4"}}, + {"\u2000\u2001\u2002", []string{}}, + {"\n™\t™\n", []string{"™", "™"}}, + {faces, []string{faces}}, +} + +func TestFields(t *testing.T) { + for _, tt := range fieldstests { + b := []byte(tt.s) + a := Fields(b) + + // Appending to the results should not change future results. + var x []byte + for _, v := range a { + x = append(v, 'z') + } + + result := sliceOfString(a) + if !eq(result, tt.a) { + t.Errorf("Fields(%q) = %v; want %v", tt.s, a, tt.a) + continue + } + + if string(b) != tt.s { + t.Errorf("slice changed to %s; want %s", string(b), tt.s) + } + if len(tt.a) > 0 { + if want := tt.a[len(tt.a)-1] + "z"; string(x) != want { + t.Errorf("last appended result was %s; want %s", x, want) + } + } + } +} + +func TestFieldsFunc(t *testing.T) { + for _, tt := range fieldstests { + a := FieldsFunc([]byte(tt.s), unicode.IsSpace) + result := sliceOfString(a) + if !eq(result, tt.a) { + t.Errorf("FieldsFunc(%q, unicode.IsSpace) = %v; want %v", tt.s, a, tt.a) + continue + } + } + pred := func(c rune) bool { return c == 'X' } + var fieldsFuncTests = []FieldsTest{ + {"", []string{}}, + {"XX", []string{}}, + {"XXhiXXX", []string{"hi"}}, + {"aXXbXXXcX", []string{"a", "b", "c"}}, + } + for _, tt := range fieldsFuncTests { + b := []byte(tt.s) + a := FieldsFunc(b, pred) + + // Appending to the results should not change future results. + var x []byte + for _, v := range a { + x = append(v, 'z') + } + + result := sliceOfString(a) + if !eq(result, tt.a) { + t.Errorf("FieldsFunc(%q) = %v, want %v", tt.s, a, tt.a) + } + + if string(b) != tt.s { + t.Errorf("slice changed to %s; want %s", b, tt.s) + } + if len(tt.a) > 0 { + if want := tt.a[len(tt.a)-1] + "z"; string(x) != want { + t.Errorf("last appended result was %s; want %s", x, want) + } + } + } +} + +// Test case for any function which accepts and returns a byte slice. +// For ease of creation, we write the input byte slice as a string. +type StringTest struct { + in string + out []byte +} + +var upperTests = []StringTest{ + {"", []byte("")}, + {"ONLYUPPER", []byte("ONLYUPPER")}, + {"abc", []byte("ABC")}, + {"AbC123", []byte("ABC123")}, + {"azAZ09_", []byte("AZAZ09_")}, + {"longStrinGwitHmixofsmaLLandcAps", []byte("LONGSTRINGWITHMIXOFSMALLANDCAPS")}, + {"long\u0250string\u0250with\u0250nonascii\u2C6Fchars", []byte("LONG\u2C6FSTRING\u2C6FWITH\u2C6FNONASCII\u2C6FCHARS")}, + {"\u0250\u0250\u0250\u0250\u0250", []byte("\u2C6F\u2C6F\u2C6F\u2C6F\u2C6F")}, // grows one byte per char + {"a\u0080\U0010FFFF", []byte("A\u0080\U0010FFFF")}, // test utf8.RuneSelf and utf8.MaxRune +} + +var lowerTests = []StringTest{ + {"", []byte("")}, + {"abc", []byte("abc")}, + {"AbC123", []byte("abc123")}, + {"azAZ09_", []byte("azaz09_")}, + {"longStrinGwitHmixofsmaLLandcAps", []byte("longstringwithmixofsmallandcaps")}, + {"LONG\u2C6FSTRING\u2C6FWITH\u2C6FNONASCII\u2C6FCHARS", []byte("long\u0250string\u0250with\u0250nonascii\u0250chars")}, + {"\u2C6D\u2C6D\u2C6D\u2C6D\u2C6D", []byte("\u0251\u0251\u0251\u0251\u0251")}, // shrinks one byte per char + {"A\u0080\U0010FFFF", []byte("a\u0080\U0010FFFF")}, // test utf8.RuneSelf and utf8.MaxRune +} + +const space = "\t\v\r\f\n\u0085\u00a0\u2000\u3000" + +var trimSpaceTests = []StringTest{ + {"", nil}, + {" a", []byte("a")}, + {"b ", []byte("b")}, + {"abc", []byte("abc")}, + {space + "abc" + space, []byte("abc")}, + {" ", nil}, + {"\u3000 ", nil}, + {" \u3000", nil}, + {" \t\r\n \t\t\r\r\n\n ", nil}, + {" \t\r\n x\t\t\r\r\n\n ", []byte("x")}, + {" \u2000\t\r\n x\t\t\r\r\ny\n \u3000", []byte("x\t\t\r\r\ny")}, + {"1 \t\r\n2", []byte("1 \t\r\n2")}, + {" x\x80", []byte("x\x80")}, + {" x\xc0", []byte("x\xc0")}, + {"x \xc0\xc0 ", []byte("x \xc0\xc0")}, + {"x \xc0", []byte("x \xc0")}, + {"x \xc0 ", []byte("x \xc0")}, + {"x \xc0\xc0 ", []byte("x \xc0\xc0")}, + {"x ☺\xc0\xc0 ", []byte("x ☺\xc0\xc0")}, + {"x ☺ ", []byte("x ☺")}, +} + +// Execute f on each test case. funcName should be the name of f; it's used +// in failure reports. +func runStringTests(t *testing.T, f func([]byte) []byte, funcName string, testCases []StringTest) { + for _, tc := range testCases { + actual := f([]byte(tc.in)) + if actual == nil && tc.out != nil { + t.Errorf("%s(%q) = nil; want %q", funcName, tc.in, tc.out) + } + if actual != nil && tc.out == nil { + t.Errorf("%s(%q) = %q; want nil", funcName, tc.in, actual) + } + if !Equal(actual, tc.out) { + t.Errorf("%s(%q) = %q; want %q", funcName, tc.in, actual, tc.out) + } + } +} + +func tenRunes(r rune) string { + runes := make([]rune, 10) + for i := range runes { + runes[i] = r + } + return string(runes) +} + +// User-defined self-inverse mapping function +func rot13(r rune) rune { + const step = 13 + if r >= 'a' && r <= 'z' { + return ((r - 'a' + step) % 26) + 'a' + } + if r >= 'A' && r <= 'Z' { + return ((r - 'A' + step) % 26) + 'A' + } + return r +} + +func TestMap(t *testing.T) { + // Run a couple of awful growth/shrinkage tests + a := tenRunes('a') + + // 1. Grow. This triggers two reallocations in Map. + maxRune := func(r rune) rune { return unicode.MaxRune } + m := Map(maxRune, []byte(a)) + expect := tenRunes(unicode.MaxRune) + if string(m) != expect { + t.Errorf("growing: expected %q got %q", expect, m) + } + + // 2. Shrink + minRune := func(r rune) rune { return 'a' } + m = Map(minRune, []byte(tenRunes(unicode.MaxRune))) + expect = a + if string(m) != expect { + t.Errorf("shrinking: expected %q got %q", expect, m) + } + + // 3. Rot13 + m = Map(rot13, []byte("a to zed")) + expect = "n gb mrq" + if string(m) != expect { + t.Errorf("rot13: expected %q got %q", expect, m) + } + + // 4. Rot13^2 + m = Map(rot13, Map(rot13, []byte("a to zed"))) + expect = "a to zed" + if string(m) != expect { + t.Errorf("rot13: expected %q got %q", expect, m) + } + + // 5. Drop + dropNotLatin := func(r rune) rune { + if unicode.Is(unicode.Latin, r) { + return r + } + return -1 + } + m = Map(dropNotLatin, []byte("Hello, 세계")) + expect = "Hello" + if string(m) != expect { + t.Errorf("drop: expected %q got %q", expect, m) + } + + // 6. Invalid rune + invalidRune := func(r rune) rune { + return utf8.MaxRune + 1 + } + m = Map(invalidRune, []byte("x")) + expect = "\uFFFD" + if string(m) != expect { + t.Errorf("invalidRune: expected %q got %q", expect, m) + } +} + +func TestToUpper(t *testing.T) { runStringTests(t, ToUpper, "ToUpper", upperTests) } + +func TestToLower(t *testing.T) { runStringTests(t, ToLower, "ToLower", lowerTests) } + +func BenchmarkToUpper(b *testing.B) { + for _, tc := range upperTests { + tin := []byte(tc.in) + b.Run(tc.in, func(b *testing.B) { + for i := 0; i < b.N; i++ { + actual := ToUpper(tin) + if !Equal(actual, tc.out) { + b.Errorf("ToUpper(%q) = %q; want %q", tc.in, actual, tc.out) + } + } + }) + } +} + +func BenchmarkToLower(b *testing.B) { + for _, tc := range lowerTests { + tin := []byte(tc.in) + b.Run(tc.in, func(b *testing.B) { + for i := 0; i < b.N; i++ { + actual := ToLower(tin) + if !Equal(actual, tc.out) { + b.Errorf("ToLower(%q) = %q; want %q", tc.in, actual, tc.out) + } + } + }) + } +} + +var toValidUTF8Tests = []struct { + in string + repl string + out string +}{ + {"", "\uFFFD", ""}, + {"abc", "\uFFFD", "abc"}, + {"\uFDDD", "\uFFFD", "\uFDDD"}, + {"a\xffb", "\uFFFD", "a\uFFFDb"}, + {"a\xffb\uFFFD", "X", "aXb\uFFFD"}, + {"a☺\xffb☺\xC0\xAFc☺\xff", "", "a☺b☺c☺"}, + {"a☺\xffb☺\xC0\xAFc☺\xff", "日本語", "a☺日本語b☺日本語c☺日本語"}, + {"\xC0\xAF", "\uFFFD", "\uFFFD"}, + {"\xE0\x80\xAF", "\uFFFD", "\uFFFD"}, + {"\xed\xa0\x80", "abc", "abc"}, + {"\xed\xbf\xbf", "\uFFFD", "\uFFFD"}, + {"\xF0\x80\x80\xaf", "☺", "☺"}, + {"\xF8\x80\x80\x80\xAF", "\uFFFD", "\uFFFD"}, + {"\xFC\x80\x80\x80\x80\xAF", "\uFFFD", "\uFFFD"}, +} + +func TestToValidUTF8(t *testing.T) { + for _, tc := range toValidUTF8Tests { + got := ToValidUTF8([]byte(tc.in), []byte(tc.repl)) + if !Equal(got, []byte(tc.out)) { + t.Errorf("ToValidUTF8(%q, %q) = %q; want %q", tc.in, tc.repl, got, tc.out) + } + } +} + +func TestTrimSpace(t *testing.T) { runStringTests(t, TrimSpace, "TrimSpace", trimSpaceTests) } + +type RepeatTest struct { + in, out string + count int +} + +var longString = "a" + string(make([]byte, 1<<16)) + "z" + +var RepeatTests = []RepeatTest{ + {"", "", 0}, + {"", "", 1}, + {"", "", 2}, + {"-", "", 0}, + {"-", "-", 1}, + {"-", "----------", 10}, + {"abc ", "abc abc abc ", 3}, + // Tests for results over the chunkLimit + {string(rune(0)), string(make([]byte, 1<<16)), 1 << 16}, + {longString, longString + longString, 2}, +} + +func TestRepeat(t *testing.T) { + for _, tt := range RepeatTests { + tin := []byte(tt.in) + tout := []byte(tt.out) + a := Repeat(tin, tt.count) + if !Equal(a, tout) { + t.Errorf("Repeat(%q, %d) = %q; want %q", tin, tt.count, a, tout) + continue + } + } +} + +func repeat(b []byte, count int) (err error) { + defer func() { + if r := recover(); r != nil { + switch v := r.(type) { + case error: + err = v + default: + err = fmt.Errorf("%s", v) + } + } + }() + + Repeat(b, count) + + return +} + +// See Issue golang.org/issue/16237 +func TestRepeatCatchesOverflow(t *testing.T) { + tests := [...]struct { + s string + count int + errStr string + }{ + 0: {"--", -2147483647, "negative"}, + 1: {"", int(^uint(0) >> 1), ""}, + 2: {"-", 10, ""}, + 3: {"gopher", 0, ""}, + 4: {"-", -1, "negative"}, + 5: {"--", -102, "negative"}, + 6: {string(make([]byte, 255)), int((^uint(0))/255 + 1), "overflow"}, + } + + for i, tt := range tests { + err := repeat([]byte(tt.s), tt.count) + if tt.errStr == "" { + if err != nil { + t.Errorf("#%d panicked %v", i, err) + } + continue + } + + if err == nil || !strings.Contains(err.Error(), tt.errStr) { + t.Errorf("#%d expected %q got %q", i, tt.errStr, err) + } + } +} + +func runesEqual(a, b []rune) bool { + if len(a) != len(b) { + return false + } + for i, r := range a { + if r != b[i] { + return false + } + } + return true +} + +type RunesTest struct { + in string + out []rune + lossy bool +} + +var RunesTests = []RunesTest{ + {"", []rune{}, false}, + {" ", []rune{32}, false}, + {"ABC", []rune{65, 66, 67}, false}, + {"abc", []rune{97, 98, 99}, false}, + {"\u65e5\u672c\u8a9e", []rune{26085, 26412, 35486}, false}, + {"ab\x80c", []rune{97, 98, 0xFFFD, 99}, true}, + {"ab\xc0c", []rune{97, 98, 0xFFFD, 99}, true}, +} + +func TestRunes(t *testing.T) { + for _, tt := range RunesTests { + tin := []byte(tt.in) + a := Runes(tin) + if !runesEqual(a, tt.out) { + t.Errorf("Runes(%q) = %v; want %v", tin, a, tt.out) + continue + } + if !tt.lossy { + // can only test reassembly if we didn't lose information + s := string(a) + if s != tt.in { + t.Errorf("string(Runes(%q)) = %x; want %x", tin, s, tin) + } + } + } +} + +type TrimTest struct { + f string + in, arg, out string +} + +var trimTests = []TrimTest{ + {"Trim", "abba", "a", "bb"}, + {"Trim", "abba", "ab", ""}, + {"TrimLeft", "abba", "ab", ""}, + {"TrimRight", "abba", "ab", ""}, + {"TrimLeft", "abba", "a", "bba"}, + {"TrimLeft", "abba", "b", "abba"}, + {"TrimRight", "abba", "a", "abb"}, + {"TrimRight", "abba", "b", "abba"}, + {"Trim", "<tag>", "<>", "tag"}, + {"Trim", "* listitem", " *", "listitem"}, + {"Trim", `"quote"`, `"`, "quote"}, + {"Trim", "\u2C6F\u2C6F\u0250\u0250\u2C6F\u2C6F", "\u2C6F", "\u0250\u0250"}, + {"Trim", "\x80test\xff", "\xff", "test"}, + {"Trim", " Ġ ", " ", "Ġ"}, + {"Trim", " Ġİ0", "0 ", "Ġİ"}, + //empty string tests + {"Trim", "abba", "", "abba"}, + {"Trim", "", "123", ""}, + {"Trim", "", "", ""}, + {"TrimLeft", "abba", "", "abba"}, + {"TrimLeft", "", "123", ""}, + {"TrimLeft", "", "", ""}, + {"TrimRight", "abba", "", "abba"}, + {"TrimRight", "", "123", ""}, + {"TrimRight", "", "", ""}, + {"TrimRight", "☺\xc0", "☺", "☺\xc0"}, + {"TrimPrefix", "aabb", "a", "abb"}, + {"TrimPrefix", "aabb", "b", "aabb"}, + {"TrimSuffix", "aabb", "a", "aabb"}, + {"TrimSuffix", "aabb", "b", "aab"}, +} + +type TrimNilTest struct { + f string + in []byte + arg string + out []byte +} + +var trimNilTests = []TrimNilTest{ + {"Trim", nil, "", nil}, + {"Trim", []byte{}, "", nil}, + {"Trim", []byte{'a'}, "a", nil}, + {"Trim", []byte{'a', 'a'}, "a", nil}, + {"Trim", []byte{'a'}, "ab", nil}, + {"Trim", []byte{'a', 'b'}, "ab", nil}, + {"Trim", []byte("☺"), "☺", nil}, + {"TrimLeft", nil, "", nil}, + {"TrimLeft", []byte{}, "", nil}, + {"TrimLeft", []byte{'a'}, "a", nil}, + {"TrimLeft", []byte{'a', 'a'}, "a", nil}, + {"TrimLeft", []byte{'a'}, "ab", nil}, + {"TrimLeft", []byte{'a', 'b'}, "ab", nil}, + {"TrimLeft", []byte("☺"), "☺", nil}, + {"TrimRight", nil, "", nil}, + {"TrimRight", []byte{}, "", []byte{}}, + {"TrimRight", []byte{'a'}, "a", []byte{}}, + {"TrimRight", []byte{'a', 'a'}, "a", []byte{}}, + {"TrimRight", []byte{'a'}, "ab", []byte{}}, + {"TrimRight", []byte{'a', 'b'}, "ab", []byte{}}, + {"TrimRight", []byte("☺"), "☺", []byte{}}, + {"TrimPrefix", nil, "", nil}, + {"TrimPrefix", []byte{}, "", []byte{}}, + {"TrimPrefix", []byte{'a'}, "a", []byte{}}, + {"TrimPrefix", []byte("☺"), "☺", []byte{}}, + {"TrimSuffix", nil, "", nil}, + {"TrimSuffix", []byte{}, "", []byte{}}, + {"TrimSuffix", []byte{'a'}, "a", []byte{}}, + {"TrimSuffix", []byte("☺"), "☺", []byte{}}, +} + +func TestTrim(t *testing.T) { + toFn := func(name string) (func([]byte, string) []byte, func([]byte, []byte) []byte) { + switch name { + case "Trim": + return Trim, nil + case "TrimLeft": + return TrimLeft, nil + case "TrimRight": + return TrimRight, nil + case "TrimPrefix": + return nil, TrimPrefix + case "TrimSuffix": + return nil, TrimSuffix + default: + t.Errorf("Undefined trim function %s", name) + return nil, nil + } + } + + for _, tc := range trimTests { + name := tc.f + f, fb := toFn(name) + if f == nil && fb == nil { + continue + } + var actual string + if f != nil { + actual = string(f([]byte(tc.in), tc.arg)) + } else { + actual = string(fb([]byte(tc.in), []byte(tc.arg))) + } + if actual != tc.out { + t.Errorf("%s(%q, %q) = %q; want %q", name, tc.in, tc.arg, actual, tc.out) + } + } + + for _, tc := range trimNilTests { + name := tc.f + f, fb := toFn(name) + if f == nil && fb == nil { + continue + } + var actual []byte + if f != nil { + actual = f(tc.in, tc.arg) + } else { + actual = fb(tc.in, []byte(tc.arg)) + } + report := func(s []byte) string { + if s == nil { + return "nil" + } else { + return fmt.Sprintf("%q", s) + } + } + if len(actual) != 0 { + t.Errorf("%s(%s, %q) returned non-empty value", name, report(tc.in), tc.arg) + } else { + actualNil := actual == nil + outNil := tc.out == nil + if actualNil != outNil { + t.Errorf("%s(%s, %q) got nil %t; want nil %t", name, report(tc.in), tc.arg, actualNil, outNil) + } + } + } +} + +type predicate struct { + f func(r rune) bool + name string +} + +var isSpace = predicate{unicode.IsSpace, "IsSpace"} +var isDigit = predicate{unicode.IsDigit, "IsDigit"} +var isUpper = predicate{unicode.IsUpper, "IsUpper"} +var isValidRune = predicate{ + func(r rune) bool { + return r != utf8.RuneError + }, + "IsValidRune", +} + +type TrimFuncTest struct { + f predicate + in string + trimOut []byte + leftOut []byte + rightOut []byte +} + +func not(p predicate) predicate { + return predicate{ + func(r rune) bool { + return !p.f(r) + }, + "not " + p.name, + } +} + +var trimFuncTests = []TrimFuncTest{ + {isSpace, space + " hello " + space, + []byte("hello"), + []byte("hello " + space), + []byte(space + " hello")}, + {isDigit, "\u0e50\u0e5212hello34\u0e50\u0e51", + []byte("hello"), + []byte("hello34\u0e50\u0e51"), + []byte("\u0e50\u0e5212hello")}, + {isUpper, "\u2C6F\u2C6F\u2C6F\u2C6FABCDhelloEF\u2C6F\u2C6FGH\u2C6F\u2C6F", + []byte("hello"), + []byte("helloEF\u2C6F\u2C6FGH\u2C6F\u2C6F"), + []byte("\u2C6F\u2C6F\u2C6F\u2C6FABCDhello")}, + {not(isSpace), "hello" + space + "hello", + []byte(space), + []byte(space + "hello"), + []byte("hello" + space)}, + {not(isDigit), "hello\u0e50\u0e521234\u0e50\u0e51helo", + []byte("\u0e50\u0e521234\u0e50\u0e51"), + []byte("\u0e50\u0e521234\u0e50\u0e51helo"), + []byte("hello\u0e50\u0e521234\u0e50\u0e51")}, + {isValidRune, "ab\xc0a\xc0cd", + []byte("\xc0a\xc0"), + []byte("\xc0a\xc0cd"), + []byte("ab\xc0a\xc0")}, + {not(isValidRune), "\xc0a\xc0", + []byte("a"), + []byte("a\xc0"), + []byte("\xc0a")}, + // The nils returned by TrimLeftFunc are odd behavior, but we need + // to preserve backwards compatibility. + {isSpace, "", + nil, + nil, + []byte("")}, + {isSpace, " ", + nil, + nil, + []byte("")}, +} + +func TestTrimFunc(t *testing.T) { + for _, tc := range trimFuncTests { + trimmers := []struct { + name string + trim func(s []byte, f func(r rune) bool) []byte + out []byte + }{ + {"TrimFunc", TrimFunc, tc.trimOut}, + {"TrimLeftFunc", TrimLeftFunc, tc.leftOut}, + {"TrimRightFunc", TrimRightFunc, tc.rightOut}, + } + for _, trimmer := range trimmers { + actual := trimmer.trim([]byte(tc.in), tc.f.f) + if actual == nil && trimmer.out != nil { + t.Errorf("%s(%q, %q) = nil; want %q", trimmer.name, tc.in, tc.f.name, trimmer.out) + } + if actual != nil && trimmer.out == nil { + t.Errorf("%s(%q, %q) = %q; want nil", trimmer.name, tc.in, tc.f.name, actual) + } + if !Equal(actual, trimmer.out) { + t.Errorf("%s(%q, %q) = %q; want %q", trimmer.name, tc.in, tc.f.name, actual, trimmer.out) + } + } + } +} + +type IndexFuncTest struct { + in string + f predicate + first, last int +} + +var indexFuncTests = []IndexFuncTest{ + {"", isValidRune, -1, -1}, + {"abc", isDigit, -1, -1}, + {"0123", isDigit, 0, 3}, + {"a1b", isDigit, 1, 1}, + {space, isSpace, 0, len(space) - 3}, // last rune in space is 3 bytes + {"\u0e50\u0e5212hello34\u0e50\u0e51", isDigit, 0, 18}, + {"\u2C6F\u2C6F\u2C6F\u2C6FABCDhelloEF\u2C6F\u2C6FGH\u2C6F\u2C6F", isUpper, 0, 34}, + {"12\u0e50\u0e52hello34\u0e50\u0e51", not(isDigit), 8, 12}, + + // tests of invalid UTF-8 + {"\x801", isDigit, 1, 1}, + {"\x80abc", isDigit, -1, -1}, + {"\xc0a\xc0", isValidRune, 1, 1}, + {"\xc0a\xc0", not(isValidRune), 0, 2}, + {"\xc0☺\xc0", not(isValidRune), 0, 4}, + {"\xc0☺\xc0\xc0", not(isValidRune), 0, 5}, + {"ab\xc0a\xc0cd", not(isValidRune), 2, 4}, + {"a\xe0\x80cd", not(isValidRune), 1, 2}, +} + +func TestIndexFunc(t *testing.T) { + for _, tc := range indexFuncTests { + first := IndexFunc([]byte(tc.in), tc.f.f) + if first != tc.first { + t.Errorf("IndexFunc(%q, %s) = %d; want %d", tc.in, tc.f.name, first, tc.first) + } + last := LastIndexFunc([]byte(tc.in), tc.f.f) + if last != tc.last { + t.Errorf("LastIndexFunc(%q, %s) = %d; want %d", tc.in, tc.f.name, last, tc.last) + } + } +} + +type ReplaceTest struct { + in string + old, new string + n int + out string +} + +var ReplaceTests = []ReplaceTest{ + {"hello", "l", "L", 0, "hello"}, + {"hello", "l", "L", -1, "heLLo"}, + {"hello", "x", "X", -1, "hello"}, + {"", "x", "X", -1, ""}, + {"radar", "r", "<r>", -1, "<r>ada<r>"}, + {"", "", "<>", -1, "<>"}, + {"banana", "a", "<>", -1, "b<>n<>n<>"}, + {"banana", "a", "<>", 1, "b<>nana"}, + {"banana", "a", "<>", 1000, "b<>n<>n<>"}, + {"banana", "an", "<>", -1, "b<><>a"}, + {"banana", "ana", "<>", -1, "b<>na"}, + {"banana", "", "<>", -1, "<>b<>a<>n<>a<>n<>a<>"}, + {"banana", "", "<>", 10, "<>b<>a<>n<>a<>n<>a<>"}, + {"banana", "", "<>", 6, "<>b<>a<>n<>a<>n<>a"}, + {"banana", "", "<>", 5, "<>b<>a<>n<>a<>na"}, + {"banana", "", "<>", 1, "<>banana"}, + {"banana", "a", "a", -1, "banana"}, + {"banana", "a", "a", 1, "banana"}, + {"☺☻☹", "", "<>", -1, "<>☺<>☻<>☹<>"}, +} + +func TestReplace(t *testing.T) { + for _, tt := range ReplaceTests { + in := append([]byte(tt.in), "<spare>"...) + in = in[:len(tt.in)] + out := Replace(in, []byte(tt.old), []byte(tt.new), tt.n) + if s := string(out); s != tt.out { + t.Errorf("Replace(%q, %q, %q, %d) = %q, want %q", tt.in, tt.old, tt.new, tt.n, s, tt.out) + } + if cap(in) == cap(out) && &in[:1][0] == &out[:1][0] { + t.Errorf("Replace(%q, %q, %q, %d) didn't copy", tt.in, tt.old, tt.new, tt.n) + } + if tt.n == -1 { + out := ReplaceAll(in, []byte(tt.old), []byte(tt.new)) + if s := string(out); s != tt.out { + t.Errorf("ReplaceAll(%q, %q, %q) = %q, want %q", tt.in, tt.old, tt.new, s, tt.out) + } + } + } +} + +type TitleTest struct { + in, out string +} + +var TitleTests = []TitleTest{ + {"", ""}, + {"a", "A"}, + {" aaa aaa aaa ", " Aaa Aaa Aaa "}, + {" Aaa Aaa Aaa ", " Aaa Aaa Aaa "}, + {"123a456", "123a456"}, + {"double-blind", "Double-Blind"}, + {"ÿøû", "Ÿøû"}, + {"with_underscore", "With_underscore"}, + {"unicode \xe2\x80\xa8 line separator", "Unicode \xe2\x80\xa8 Line Separator"}, +} + +func TestTitle(t *testing.T) { + for _, tt := range TitleTests { + if s := string(Title([]byte(tt.in))); s != tt.out { + t.Errorf("Title(%q) = %q, want %q", tt.in, s, tt.out) + } + } +} + +var ToTitleTests = []TitleTest{ + {"", ""}, + {"a", "A"}, + {" aaa aaa aaa ", " AAA AAA AAA "}, + {" Aaa Aaa Aaa ", " AAA AAA AAA "}, + {"123a456", "123A456"}, + {"double-blind", "DOUBLE-BLIND"}, + {"ÿøû", "ŸØÛ"}, +} + +func TestToTitle(t *testing.T) { + for _, tt := range ToTitleTests { + if s := string(ToTitle([]byte(tt.in))); s != tt.out { + t.Errorf("ToTitle(%q) = %q, want %q", tt.in, s, tt.out) + } + } +} + +var EqualFoldTests = []struct { + s, t string + out bool +}{ + {"abc", "abc", true}, + {"ABcd", "ABcd", true}, + {"123abc", "123ABC", true}, + {"αβδ", "ΑΒΔ", true}, + {"abc", "xyz", false}, + {"abc", "XYZ", false}, + {"abcdefghijk", "abcdefghijX", false}, + {"abcdefghijk", "abcdefghij\u212A", true}, + {"abcdefghijK", "abcdefghij\u212A", true}, + {"abcdefghijkz", "abcdefghij\u212Ay", false}, + {"abcdefghijKz", "abcdefghij\u212Ay", false}, +} + +func TestEqualFold(t *testing.T) { + for _, tt := range EqualFoldTests { + if out := EqualFold([]byte(tt.s), []byte(tt.t)); out != tt.out { + t.Errorf("EqualFold(%#q, %#q) = %v, want %v", tt.s, tt.t, out, tt.out) + } + if out := EqualFold([]byte(tt.t), []byte(tt.s)); out != tt.out { + t.Errorf("EqualFold(%#q, %#q) = %v, want %v", tt.t, tt.s, out, tt.out) + } + } +} + +var cutTests = []struct { + s, sep string + before, after string + found bool +}{ + {"abc", "b", "a", "c", true}, + {"abc", "a", "", "bc", true}, + {"abc", "c", "ab", "", true}, + {"abc", "abc", "", "", true}, + {"abc", "", "", "abc", true}, + {"abc", "d", "abc", "", false}, + {"", "d", "", "", false}, + {"", "", "", "", true}, +} + +func TestCut(t *testing.T) { + for _, tt := range cutTests { + if before, after, found := Cut([]byte(tt.s), []byte(tt.sep)); string(before) != tt.before || string(after) != tt.after || found != tt.found { + t.Errorf("Cut(%q, %q) = %q, %q, %v, want %q, %q, %v", tt.s, tt.sep, before, after, found, tt.before, tt.after, tt.found) + } + } +} + +var cutPrefixTests = []struct { + s, sep string + after string + found bool +}{ + {"abc", "a", "bc", true}, + {"abc", "abc", "", true}, + {"abc", "", "abc", true}, + {"abc", "d", "abc", false}, + {"", "d", "", false}, + {"", "", "", true}, +} + +func TestCutPrefix(t *testing.T) { + for _, tt := range cutPrefixTests { + if after, found := CutPrefix([]byte(tt.s), []byte(tt.sep)); string(after) != tt.after || found != tt.found { + t.Errorf("CutPrefix(%q, %q) = %q, %v, want %q, %v", tt.s, tt.sep, after, found, tt.after, tt.found) + } + } +} + +var cutSuffixTests = []struct { + s, sep string + after string + found bool +}{ + {"abc", "bc", "a", true}, + {"abc", "abc", "", true}, + {"abc", "", "abc", true}, + {"abc", "d", "abc", false}, + {"", "d", "", false}, + {"", "", "", true}, +} + +func TestCutSuffix(t *testing.T) { + for _, tt := range cutSuffixTests { + if after, found := CutSuffix([]byte(tt.s), []byte(tt.sep)); string(after) != tt.after || found != tt.found { + t.Errorf("CutSuffix(%q, %q) = %q, %v, want %q, %v", tt.s, tt.sep, after, found, tt.after, tt.found) + } + } +} + +func TestBufferGrowNegative(t *testing.T) { + defer func() { + if err := recover(); err == nil { + t.Fatal("Grow(-1) should have panicked") + } + }() + var b Buffer + b.Grow(-1) +} + +func TestBufferTruncateNegative(t *testing.T) { + defer func() { + if err := recover(); err == nil { + t.Fatal("Truncate(-1) should have panicked") + } + }() + var b Buffer + b.Truncate(-1) +} + +func TestBufferTruncateOutOfRange(t *testing.T) { + defer func() { + if err := recover(); err == nil { + t.Fatal("Truncate(20) should have panicked") + } + }() + var b Buffer + b.Write(make([]byte, 10)) + b.Truncate(20) +} + +var containsTests = []struct { + b, subslice []byte + want bool +}{ + {[]byte("hello"), []byte("hel"), true}, + {[]byte("日本語"), []byte("日本"), true}, + {[]byte("hello"), []byte("Hello, world"), false}, + {[]byte("東京"), []byte("京東"), false}, +} + +func TestContains(t *testing.T) { + for _, tt := range containsTests { + if got := Contains(tt.b, tt.subslice); got != tt.want { + t.Errorf("Contains(%q, %q) = %v, want %v", tt.b, tt.subslice, got, tt.want) + } + } +} + +var ContainsAnyTests = []struct { + b []byte + substr string + expected bool +}{ + {[]byte(""), "", false}, + {[]byte(""), "a", false}, + {[]byte(""), "abc", false}, + {[]byte("a"), "", false}, + {[]byte("a"), "a", true}, + {[]byte("aaa"), "a", true}, + {[]byte("abc"), "xyz", false}, + {[]byte("abc"), "xcz", true}, + {[]byte("a☺b☻c☹d"), "uvw☻xyz", true}, + {[]byte("aRegExp*"), ".(|)*+?^$[]", true}, + {[]byte(dots + dots + dots), " ", false}, +} + +func TestContainsAny(t *testing.T) { + for _, ct := range ContainsAnyTests { + if ContainsAny(ct.b, ct.substr) != ct.expected { + t.Errorf("ContainsAny(%s, %s) = %v, want %v", + ct.b, ct.substr, !ct.expected, ct.expected) + } + } +} + +var ContainsRuneTests = []struct { + b []byte + r rune + expected bool +}{ + {[]byte(""), 'a', false}, + {[]byte("a"), 'a', true}, + {[]byte("aaa"), 'a', true}, + {[]byte("abc"), 'y', false}, + {[]byte("abc"), 'c', true}, + {[]byte("a☺b☻c☹d"), 'x', false}, + {[]byte("a☺b☻c☹d"), '☻', true}, + {[]byte("aRegExp*"), '*', true}, +} + +func TestContainsRune(t *testing.T) { + for _, ct := range ContainsRuneTests { + if ContainsRune(ct.b, ct.r) != ct.expected { + t.Errorf("ContainsRune(%q, %q) = %v, want %v", + ct.b, ct.r, !ct.expected, ct.expected) + } + } +} + +var makeFieldsInput = func() []byte { + x := make([]byte, 1<<20) + // Input is ~10% space, ~10% 2-byte UTF-8, rest ASCII non-space. + for i := range x { + switch rand.Intn(10) { + case 0: + x[i] = ' ' + case 1: + if i > 0 && x[i-1] == 'x' { + copy(x[i-1:], "χ") + break + } + fallthrough + default: + x[i] = 'x' + } + } + return x +} + +var makeFieldsInputASCII = func() []byte { + x := make([]byte, 1<<20) + // Input is ~10% space, rest ASCII non-space. + for i := range x { + if rand.Intn(10) == 0 { + x[i] = ' ' + } else { + x[i] = 'x' + } + } + return x +} + +var bytesdata = []struct { + name string + data []byte +}{ + {"ASCII", makeFieldsInputASCII()}, + {"Mixed", makeFieldsInput()}, +} + +func BenchmarkFields(b *testing.B) { + for _, sd := range bytesdata { + b.Run(sd.name, func(b *testing.B) { + for j := 1 << 4; j <= 1<<20; j <<= 4 { + b.Run(fmt.Sprintf("%d", j), func(b *testing.B) { + b.ReportAllocs() + b.SetBytes(int64(j)) + data := sd.data[:j] + for i := 0; i < b.N; i++ { + Fields(data) + } + }) + } + }) + } +} + +func BenchmarkFieldsFunc(b *testing.B) { + for _, sd := range bytesdata { + b.Run(sd.name, func(b *testing.B) { + for j := 1 << 4; j <= 1<<20; j <<= 4 { + b.Run(fmt.Sprintf("%d", j), func(b *testing.B) { + b.ReportAllocs() + b.SetBytes(int64(j)) + data := sd.data[:j] + for i := 0; i < b.N; i++ { + FieldsFunc(data, unicode.IsSpace) + } + }) + } + }) + } +} + +func BenchmarkTrimSpace(b *testing.B) { + tests := []struct { + name string + input []byte + }{ + {"NoTrim", []byte("typical")}, + {"ASCII", []byte(" foo bar ")}, + {"SomeNonASCII", []byte(" \u2000\t\r\n x\t\t\r\r\ny\n \u3000 ")}, + {"JustNonASCII", []byte("\u2000\u2000\u2000☺☺☺☺\u3000\u3000\u3000")}, + } + for _, test := range tests { + b.Run(test.name, func(b *testing.B) { + for i := 0; i < b.N; i++ { + TrimSpace(test.input) + } + }) + } +} + +func BenchmarkToValidUTF8(b *testing.B) { + tests := []struct { + name string + input []byte + }{ + {"Valid", []byte("typical")}, + {"InvalidASCII", []byte("foo\xffbar")}, + {"InvalidNonASCII", []byte("日本語\xff日本語")}, + } + replacement := []byte("\uFFFD") + b.ResetTimer() + for _, test := range tests { + b.Run(test.name, func(b *testing.B) { + for i := 0; i < b.N; i++ { + ToValidUTF8(test.input, replacement) + } + }) + } +} + +func makeBenchInputHard() []byte { + tokens := [...]string{ + "<a>", "<p>", "<b>", "<strong>", + "</a>", "</p>", "</b>", "</strong>", + "hello", "world", + } + x := make([]byte, 0, 1<<20) + for { + i := rand.Intn(len(tokens)) + if len(x)+len(tokens[i]) >= 1<<20 { + break + } + x = append(x, tokens[i]...) + } + return x +} + +var benchInputHard = makeBenchInputHard() + +func benchmarkIndexHard(b *testing.B, sep []byte) { + for i := 0; i < b.N; i++ { + Index(benchInputHard, sep) + } +} + +func benchmarkLastIndexHard(b *testing.B, sep []byte) { + for i := 0; i < b.N; i++ { + LastIndex(benchInputHard, sep) + } +} + +func benchmarkCountHard(b *testing.B, sep []byte) { + for i := 0; i < b.N; i++ { + Count(benchInputHard, sep) + } +} + +func BenchmarkIndexHard1(b *testing.B) { benchmarkIndexHard(b, []byte("<>")) } +func BenchmarkIndexHard2(b *testing.B) { benchmarkIndexHard(b, []byte("</pre>")) } +func BenchmarkIndexHard3(b *testing.B) { benchmarkIndexHard(b, []byte("<b>hello world</b>")) } +func BenchmarkIndexHard4(b *testing.B) { + benchmarkIndexHard(b, []byte("<pre><b>hello</b><strong>world</strong></pre>")) +} + +func BenchmarkLastIndexHard1(b *testing.B) { benchmarkLastIndexHard(b, []byte("<>")) } +func BenchmarkLastIndexHard2(b *testing.B) { benchmarkLastIndexHard(b, []byte("</pre>")) } +func BenchmarkLastIndexHard3(b *testing.B) { benchmarkLastIndexHard(b, []byte("<b>hello world</b>")) } + +func BenchmarkCountHard1(b *testing.B) { benchmarkCountHard(b, []byte("<>")) } +func BenchmarkCountHard2(b *testing.B) { benchmarkCountHard(b, []byte("</pre>")) } +func BenchmarkCountHard3(b *testing.B) { benchmarkCountHard(b, []byte("<b>hello world</b>")) } + +func BenchmarkSplitEmptySeparator(b *testing.B) { + for i := 0; i < b.N; i++ { + Split(benchInputHard, nil) + } +} + +func BenchmarkSplitSingleByteSeparator(b *testing.B) { + sep := []byte("/") + for i := 0; i < b.N; i++ { + Split(benchInputHard, sep) + } +} + +func BenchmarkSplitMultiByteSeparator(b *testing.B) { + sep := []byte("hello") + for i := 0; i < b.N; i++ { + Split(benchInputHard, sep) + } +} + +func BenchmarkSplitNSingleByteSeparator(b *testing.B) { + sep := []byte("/") + for i := 0; i < b.N; i++ { + SplitN(benchInputHard, sep, 10) + } +} + +func BenchmarkSplitNMultiByteSeparator(b *testing.B) { + sep := []byte("hello") + for i := 0; i < b.N; i++ { + SplitN(benchInputHard, sep, 10) + } +} + +func BenchmarkRepeat(b *testing.B) { + for i := 0; i < b.N; i++ { + Repeat([]byte("-"), 80) + } +} + +func BenchmarkRepeatLarge(b *testing.B) { + s := Repeat([]byte("@"), 8*1024) + for j := 8; j <= 30; j++ { + for _, k := range []int{1, 16, 4097} { + s := s[:k] + n := (1 << j) / k + if n == 0 { + continue + } + b.Run(fmt.Sprintf("%d/%d", 1<<j, k), func(b *testing.B) { + for i := 0; i < b.N; i++ { + Repeat(s, n) + } + b.SetBytes(int64(n * len(s))) + }) + } + } +} + +func BenchmarkBytesCompare(b *testing.B) { + for n := 1; n <= 2048; n <<= 1 { + b.Run(fmt.Sprint(n), func(b *testing.B) { + var x = make([]byte, n) + var y = make([]byte, n) + + for i := 0; i < n; i++ { + x[i] = 'a' + } + + for i := 0; i < n; i++ { + y[i] = 'a' + } + + b.ResetTimer() + for i := 0; i < b.N; i++ { + Compare(x, y) + } + }) + } +} + +func BenchmarkIndexAnyASCII(b *testing.B) { + x := Repeat([]byte{'#'}, 2048) // Never matches set + cs := "0123456789abcdefghijklmnopqrstuvwxyz0123456789abcdefghijklmnopqrstuvwxyz" + for k := 1; k <= 2048; k <<= 4 { + for j := 1; j <= 64; j <<= 1 { + b.Run(fmt.Sprintf("%d:%d", k, j), func(b *testing.B) { + for i := 0; i < b.N; i++ { + IndexAny(x[:k], cs[:j]) + } + }) + } + } +} + +func BenchmarkIndexAnyUTF8(b *testing.B) { + x := Repeat([]byte{'#'}, 2048) // Never matches set + cs := "你好世界, hello world. 你好世界, hello world. 你好世界, hello world." + for k := 1; k <= 2048; k <<= 4 { + for j := 1; j <= 64; j <<= 1 { + b.Run(fmt.Sprintf("%d:%d", k, j), func(b *testing.B) { + for i := 0; i < b.N; i++ { + IndexAny(x[:k], cs[:j]) + } + }) + } + } +} + +func BenchmarkLastIndexAnyASCII(b *testing.B) { + x := Repeat([]byte{'#'}, 2048) // Never matches set + cs := "0123456789abcdefghijklmnopqrstuvwxyz0123456789abcdefghijklmnopqrstuvwxyz" + for k := 1; k <= 2048; k <<= 4 { + for j := 1; j <= 64; j <<= 1 { + b.Run(fmt.Sprintf("%d:%d", k, j), func(b *testing.B) { + for i := 0; i < b.N; i++ { + LastIndexAny(x[:k], cs[:j]) + } + }) + } + } +} + +func BenchmarkLastIndexAnyUTF8(b *testing.B) { + x := Repeat([]byte{'#'}, 2048) // Never matches set + cs := "你好世界, hello world. 你好世界, hello world. 你好世界, hello world." + for k := 1; k <= 2048; k <<= 4 { + for j := 1; j <= 64; j <<= 1 { + b.Run(fmt.Sprintf("%d:%d", k, j), func(b *testing.B) { + for i := 0; i < b.N; i++ { + LastIndexAny(x[:k], cs[:j]) + } + }) + } + } +} + +func BenchmarkTrimASCII(b *testing.B) { + cs := "0123456789abcdef" + for k := 1; k <= 4096; k <<= 4 { + for j := 1; j <= 16; j <<= 1 { + b.Run(fmt.Sprintf("%d:%d", k, j), func(b *testing.B) { + x := Repeat([]byte(cs[:j]), k) // Always matches set + for i := 0; i < b.N; i++ { + Trim(x[:k], cs[:j]) + } + }) + } + } +} + +func BenchmarkTrimByte(b *testing.B) { + x := []byte(" the quick brown fox ") + for i := 0; i < b.N; i++ { + Trim(x, " ") + } +} + +func BenchmarkIndexPeriodic(b *testing.B) { + key := []byte{1, 1} + for _, skip := range [...]int{2, 4, 8, 16, 32, 64} { + b.Run(fmt.Sprintf("IndexPeriodic%d", skip), func(b *testing.B) { + buf := make([]byte, 1<<16) + for i := 0; i < len(buf); i += skip { + buf[i] = 1 + } + for i := 0; i < b.N; i++ { + Index(buf, key) + } + }) + } +} + +func TestClone(t *testing.T) { + var cloneTests = [][]byte{ + []byte(nil), + []byte{}, + Clone([]byte{}), + []byte(strings.Repeat("a", 42))[:0], + []byte(strings.Repeat("a", 42))[:0:0], + []byte("short"), + []byte(strings.Repeat("a", 42)), + } + for _, input := range cloneTests { + clone := Clone(input) + if !Equal(clone, input) { + t.Errorf("Clone(%q) = %q; want %q", input, clone, input) + } + + if input == nil && clone != nil { + t.Errorf("Clone(%#v) return value should be equal to nil slice.", input) + } + + if input != nil && clone == nil { + t.Errorf("Clone(%#v) return value should not be equal to nil slice.", input) + } + + if cap(input) != 0 && unsafe.SliceData(input) == unsafe.SliceData(clone) { + t.Errorf("Clone(%q) return value should not reference inputs backing memory.", input) + } + } +} diff --git a/src/bytes/compare_test.go b/src/bytes/compare_test.go new file mode 100644 index 0000000..a0150ab --- /dev/null +++ b/src/bytes/compare_test.go @@ -0,0 +1,271 @@ +// Copyright 2013 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 bytes_test + +import ( + . "bytes" + "fmt" + "internal/testenv" + "testing" +) + +var compareTests = []struct { + a, b []byte + i int +}{ + {[]byte(""), []byte(""), 0}, + {[]byte("a"), []byte(""), 1}, + {[]byte(""), []byte("a"), -1}, + {[]byte("abc"), []byte("abc"), 0}, + {[]byte("abd"), []byte("abc"), 1}, + {[]byte("abc"), []byte("abd"), -1}, + {[]byte("ab"), []byte("abc"), -1}, + {[]byte("abc"), []byte("ab"), 1}, + {[]byte("x"), []byte("ab"), 1}, + {[]byte("ab"), []byte("x"), -1}, + {[]byte("x"), []byte("a"), 1}, + {[]byte("b"), []byte("x"), -1}, + // test runtime·memeq's chunked implementation + {[]byte("abcdefgh"), []byte("abcdefgh"), 0}, + {[]byte("abcdefghi"), []byte("abcdefghi"), 0}, + {[]byte("abcdefghi"), []byte("abcdefghj"), -1}, + {[]byte("abcdefghj"), []byte("abcdefghi"), 1}, + // nil tests + {nil, nil, 0}, + {[]byte(""), nil, 0}, + {nil, []byte(""), 0}, + {[]byte("a"), nil, 1}, + {nil, []byte("a"), -1}, +} + +func TestCompare(t *testing.T) { + for _, tt := range compareTests { + numShifts := 16 + buffer := make([]byte, len(tt.b)+numShifts) + // vary the input alignment of tt.b + for offset := 0; offset <= numShifts; offset++ { + shiftedB := buffer[offset : len(tt.b)+offset] + copy(shiftedB, tt.b) + cmp := Compare(tt.a, shiftedB) + if cmp != tt.i { + t.Errorf(`Compare(%q, %q), offset %d = %v; want %v`, tt.a, tt.b, offset, cmp, tt.i) + } + } + } +} + +func TestCompareIdenticalSlice(t *testing.T) { + var b = []byte("Hello Gophers!") + if Compare(b, b) != 0 { + t.Error("b != b") + } + if Compare(b, b[:1]) != 1 { + t.Error("b > b[:1] failed") + } +} + +func TestCompareBytes(t *testing.T) { + lengths := make([]int, 0) // lengths to test in ascending order + for i := 0; i <= 128; i++ { + lengths = append(lengths, i) + } + lengths = append(lengths, 256, 512, 1024, 1333, 4095, 4096, 4097) + + if !testing.Short() || testenv.Builder() != "" { + lengths = append(lengths, 65535, 65536, 65537, 99999) + } + + n := lengths[len(lengths)-1] + a := make([]byte, n+1) + b := make([]byte, n+1) + for _, len := range lengths { + // randomish but deterministic data. No 0 or 255. + for i := 0; i < len; i++ { + a[i] = byte(1 + 31*i%254) + b[i] = byte(1 + 31*i%254) + } + // data past the end is different + for i := len; i <= n; i++ { + a[i] = 8 + b[i] = 9 + } + cmp := Compare(a[:len], b[:len]) + if cmp != 0 { + t.Errorf(`CompareIdentical(%d) = %d`, len, cmp) + } + if len > 0 { + cmp = Compare(a[:len-1], b[:len]) + if cmp != -1 { + t.Errorf(`CompareAshorter(%d) = %d`, len, cmp) + } + cmp = Compare(a[:len], b[:len-1]) + if cmp != 1 { + t.Errorf(`CompareBshorter(%d) = %d`, len, cmp) + } + } + for k := 0; k < len; k++ { + b[k] = a[k] - 1 + cmp = Compare(a[:len], b[:len]) + if cmp != 1 { + t.Errorf(`CompareAbigger(%d,%d) = %d`, len, k, cmp) + } + b[k] = a[k] + 1 + cmp = Compare(a[:len], b[:len]) + if cmp != -1 { + t.Errorf(`CompareBbigger(%d,%d) = %d`, len, k, cmp) + } + b[k] = a[k] + } + } +} + +func TestEndianBaseCompare(t *testing.T) { + // This test compares byte slices that are almost identical, except one + // difference that for some j, a[j]>b[j] and a[j+1]<b[j+1]. If the implementation + // compares large chunks with wrong endianness, it gets wrong result. + // no vector register is larger than 512 bytes for now + const maxLength = 512 + a := make([]byte, maxLength) + b := make([]byte, maxLength) + // randomish but deterministic data. No 0 or 255. + for i := 0; i < maxLength; i++ { + a[i] = byte(1 + 31*i%254) + b[i] = byte(1 + 31*i%254) + } + for i := 2; i <= maxLength; i <<= 1 { + for j := 0; j < i-1; j++ { + a[j] = b[j] - 1 + a[j+1] = b[j+1] + 1 + cmp := Compare(a[:i], b[:i]) + if cmp != -1 { + t.Errorf(`CompareBbigger(%d,%d) = %d`, i, j, cmp) + } + a[j] = b[j] + 1 + a[j+1] = b[j+1] - 1 + cmp = Compare(a[:i], b[:i]) + if cmp != 1 { + t.Errorf(`CompareAbigger(%d,%d) = %d`, i, j, cmp) + } + a[j] = b[j] + a[j+1] = b[j+1] + } + } +} + +func BenchmarkCompareBytesEqual(b *testing.B) { + b1 := []byte("Hello Gophers!") + b2 := []byte("Hello Gophers!") + for i := 0; i < b.N; i++ { + if Compare(b1, b2) != 0 { + b.Fatal("b1 != b2") + } + } +} + +func BenchmarkCompareBytesToNil(b *testing.B) { + b1 := []byte("Hello Gophers!") + var b2 []byte + for i := 0; i < b.N; i++ { + if Compare(b1, b2) != 1 { + b.Fatal("b1 > b2 failed") + } + } +} + +func BenchmarkCompareBytesEmpty(b *testing.B) { + b1 := []byte("") + b2 := b1 + for i := 0; i < b.N; i++ { + if Compare(b1, b2) != 0 { + b.Fatal("b1 != b2") + } + } +} + +func BenchmarkCompareBytesIdentical(b *testing.B) { + b1 := []byte("Hello Gophers!") + b2 := b1 + for i := 0; i < b.N; i++ { + if Compare(b1, b2) != 0 { + b.Fatal("b1 != b2") + } + } +} + +func BenchmarkCompareBytesSameLength(b *testing.B) { + b1 := []byte("Hello Gophers!") + b2 := []byte("Hello, Gophers") + for i := 0; i < b.N; i++ { + if Compare(b1, b2) != -1 { + b.Fatal("b1 < b2 failed") + } + } +} + +func BenchmarkCompareBytesDifferentLength(b *testing.B) { + b1 := []byte("Hello Gophers!") + b2 := []byte("Hello, Gophers!") + for i := 0; i < b.N; i++ { + if Compare(b1, b2) != -1 { + b.Fatal("b1 < b2 failed") + } + } +} + +func benchmarkCompareBytesBigUnaligned(b *testing.B, offset int) { + b.StopTimer() + b1 := make([]byte, 0, 1<<20) + for len(b1) < 1<<20 { + b1 = append(b1, "Hello Gophers!"...) + } + b2 := append([]byte("12345678")[:offset], b1...) + b.StartTimer() + for j := 0; j < b.N; j++ { + if Compare(b1, b2[offset:]) != 0 { + b.Fatal("b1 != b2") + } + } + b.SetBytes(int64(len(b1))) +} + +func BenchmarkCompareBytesBigUnaligned(b *testing.B) { + for i := 1; i < 8; i++ { + b.Run(fmt.Sprintf("offset=%d", i), func(b *testing.B) { + benchmarkCompareBytesBigUnaligned(b, i) + }) + } +} + +func BenchmarkCompareBytesBig(b *testing.B) { + b.StopTimer() + b1 := make([]byte, 0, 1<<20) + for len(b1) < 1<<20 { + b1 = append(b1, "Hello Gophers!"...) + } + b2 := append([]byte{}, b1...) + b.StartTimer() + for i := 0; i < b.N; i++ { + if Compare(b1, b2) != 0 { + b.Fatal("b1 != b2") + } + } + b.SetBytes(int64(len(b1))) +} + +func BenchmarkCompareBytesBigIdentical(b *testing.B) { + b.StopTimer() + b1 := make([]byte, 0, 1<<20) + for len(b1) < 1<<20 { + b1 = append(b1, "Hello Gophers!"...) + } + b2 := b1 + b.StartTimer() + for i := 0; i < b.N; i++ { + if Compare(b1, b2) != 0 { + b.Fatal("b1 != b2") + } + } + b.SetBytes(int64(len(b1))) +} diff --git a/src/bytes/example_test.go b/src/bytes/example_test.go new file mode 100644 index 0000000..54a7aa6 --- /dev/null +++ b/src/bytes/example_test.go @@ -0,0 +1,547 @@ +// Copyright 2011 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 bytes_test + +import ( + "bytes" + "encoding/base64" + "fmt" + "io" + "os" + "sort" + "unicode" +) + +func ExampleBuffer() { + var b bytes.Buffer // A Buffer needs no initialization. + b.Write([]byte("Hello ")) + fmt.Fprintf(&b, "world!") + b.WriteTo(os.Stdout) + // Output: Hello world! +} + +func ExampleBuffer_reader() { + // A Buffer can turn a string or a []byte into an io.Reader. + buf := bytes.NewBufferString("R29waGVycyBydWxlIQ==") + dec := base64.NewDecoder(base64.StdEncoding, buf) + io.Copy(os.Stdout, dec) + // Output: Gophers rule! +} + +func ExampleBuffer_Bytes() { + buf := bytes.Buffer{} + buf.Write([]byte{'h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd'}) + os.Stdout.Write(buf.Bytes()) + // Output: hello world +} + +func ExampleBuffer_Cap() { + buf1 := bytes.NewBuffer(make([]byte, 10)) + buf2 := bytes.NewBuffer(make([]byte, 0, 10)) + fmt.Println(buf1.Cap()) + fmt.Println(buf2.Cap()) + // Output: + // 10 + // 10 +} + +func ExampleBuffer_Grow() { + var b bytes.Buffer + b.Grow(64) + bb := b.Bytes() + b.Write([]byte("64 bytes or fewer")) + fmt.Printf("%q", bb[:b.Len()]) + // Output: "64 bytes or fewer" +} + +func ExampleBuffer_Len() { + var b bytes.Buffer + b.Grow(64) + b.Write([]byte("abcde")) + fmt.Printf("%d", b.Len()) + // Output: 5 +} + +func ExampleBuffer_Next() { + var b bytes.Buffer + b.Grow(64) + b.Write([]byte("abcde")) + fmt.Printf("%s\n", string(b.Next(2))) + fmt.Printf("%s\n", string(b.Next(2))) + fmt.Printf("%s", string(b.Next(2))) + // Output: + // ab + // cd + // e +} + +func ExampleBuffer_Read() { + var b bytes.Buffer + b.Grow(64) + b.Write([]byte("abcde")) + rdbuf := make([]byte, 1) + n, err := b.Read(rdbuf) + if err != nil { + panic(err) + } + fmt.Println(n) + fmt.Println(b.String()) + fmt.Println(string(rdbuf)) + // Output + // 1 + // bcde + // a +} + +func ExampleBuffer_ReadByte() { + var b bytes.Buffer + b.Grow(64) + b.Write([]byte("abcde")) + c, err := b.ReadByte() + if err != nil { + panic(err) + } + fmt.Println(c) + fmt.Println(b.String()) + // Output + // 97 + // bcde +} + +func ExampleCompare() { + // Interpret Compare's result by comparing it to zero. + var a, b []byte + if bytes.Compare(a, b) < 0 { + // a less b + } + if bytes.Compare(a, b) <= 0 { + // a less or equal b + } + if bytes.Compare(a, b) > 0 { + // a greater b + } + if bytes.Compare(a, b) >= 0 { + // a greater or equal b + } + + // Prefer Equal to Compare for equality comparisons. + if bytes.Equal(a, b) { + // a equal b + } + if !bytes.Equal(a, b) { + // a not equal b + } +} + +func ExampleCompare_search() { + // Binary search to find a matching byte slice. + var needle []byte + var haystack [][]byte // Assume sorted + i := sort.Search(len(haystack), func(i int) bool { + // Return haystack[i] >= needle. + return bytes.Compare(haystack[i], needle) >= 0 + }) + if i < len(haystack) && bytes.Equal(haystack[i], needle) { + // Found it! + } +} + +func ExampleContains() { + fmt.Println(bytes.Contains([]byte("seafood"), []byte("foo"))) + fmt.Println(bytes.Contains([]byte("seafood"), []byte("bar"))) + fmt.Println(bytes.Contains([]byte("seafood"), []byte(""))) + fmt.Println(bytes.Contains([]byte(""), []byte(""))) + // Output: + // true + // false + // true + // true +} + +func ExampleContainsAny() { + fmt.Println(bytes.ContainsAny([]byte("I like seafood."), "fÄo!")) + fmt.Println(bytes.ContainsAny([]byte("I like seafood."), "去是伟大的.")) + fmt.Println(bytes.ContainsAny([]byte("I like seafood."), "")) + fmt.Println(bytes.ContainsAny([]byte(""), "")) + // Output: + // true + // true + // false + // false +} + +func ExampleContainsRune() { + fmt.Println(bytes.ContainsRune([]byte("I like seafood."), 'f')) + fmt.Println(bytes.ContainsRune([]byte("I like seafood."), 'ö')) + fmt.Println(bytes.ContainsRune([]byte("去是伟大的!"), '大')) + fmt.Println(bytes.ContainsRune([]byte("去是伟大的!"), '!')) + fmt.Println(bytes.ContainsRune([]byte(""), '@')) + // Output: + // true + // false + // true + // true + // false +} + +func ExampleCount() { + fmt.Println(bytes.Count([]byte("cheese"), []byte("e"))) + fmt.Println(bytes.Count([]byte("five"), []byte(""))) // before & after each rune + // Output: + // 3 + // 5 +} + +func ExampleCut() { + show := func(s, sep string) { + before, after, found := bytes.Cut([]byte(s), []byte(sep)) + fmt.Printf("Cut(%q, %q) = %q, %q, %v\n", s, sep, before, after, found) + } + show("Gopher", "Go") + show("Gopher", "ph") + show("Gopher", "er") + show("Gopher", "Badger") + // Output: + // Cut("Gopher", "Go") = "", "pher", true + // Cut("Gopher", "ph") = "Go", "er", true + // Cut("Gopher", "er") = "Goph", "", true + // Cut("Gopher", "Badger") = "Gopher", "", false +} + +func ExampleEqual() { + fmt.Println(bytes.Equal([]byte("Go"), []byte("Go"))) + fmt.Println(bytes.Equal([]byte("Go"), []byte("C++"))) + // Output: + // true + // false +} + +func ExampleEqualFold() { + fmt.Println(bytes.EqualFold([]byte("Go"), []byte("go"))) + // Output: true +} + +func ExampleFields() { + fmt.Printf("Fields are: %q", bytes.Fields([]byte(" foo bar baz "))) + // Output: Fields are: ["foo" "bar" "baz"] +} + +func ExampleFieldsFunc() { + f := func(c rune) bool { + return !unicode.IsLetter(c) && !unicode.IsNumber(c) + } + fmt.Printf("Fields are: %q", bytes.FieldsFunc([]byte(" foo1;bar2,baz3..."), f)) + // Output: Fields are: ["foo1" "bar2" "baz3"] +} + +func ExampleHasPrefix() { + fmt.Println(bytes.HasPrefix([]byte("Gopher"), []byte("Go"))) + fmt.Println(bytes.HasPrefix([]byte("Gopher"), []byte("C"))) + fmt.Println(bytes.HasPrefix([]byte("Gopher"), []byte(""))) + // Output: + // true + // false + // true +} + +func ExampleHasSuffix() { + fmt.Println(bytes.HasSuffix([]byte("Amigo"), []byte("go"))) + fmt.Println(bytes.HasSuffix([]byte("Amigo"), []byte("O"))) + fmt.Println(bytes.HasSuffix([]byte("Amigo"), []byte("Ami"))) + fmt.Println(bytes.HasSuffix([]byte("Amigo"), []byte(""))) + // Output: + // true + // false + // false + // true +} + +func ExampleIndex() { + fmt.Println(bytes.Index([]byte("chicken"), []byte("ken"))) + fmt.Println(bytes.Index([]byte("chicken"), []byte("dmr"))) + // Output: + // 4 + // -1 +} + +func ExampleIndexByte() { + fmt.Println(bytes.IndexByte([]byte("chicken"), byte('k'))) + fmt.Println(bytes.IndexByte([]byte("chicken"), byte('g'))) + // Output: + // 4 + // -1 +} + +func ExampleIndexFunc() { + f := func(c rune) bool { + return unicode.Is(unicode.Han, c) + } + fmt.Println(bytes.IndexFunc([]byte("Hello, 世界"), f)) + fmt.Println(bytes.IndexFunc([]byte("Hello, world"), f)) + // Output: + // 7 + // -1 +} + +func ExampleIndexAny() { + fmt.Println(bytes.IndexAny([]byte("chicken"), "aeiouy")) + fmt.Println(bytes.IndexAny([]byte("crwth"), "aeiouy")) + // Output: + // 2 + // -1 +} + +func ExampleIndexRune() { + fmt.Println(bytes.IndexRune([]byte("chicken"), 'k')) + fmt.Println(bytes.IndexRune([]byte("chicken"), 'd')) + // Output: + // 4 + // -1 +} + +func ExampleJoin() { + s := [][]byte{[]byte("foo"), []byte("bar"), []byte("baz")} + fmt.Printf("%s", bytes.Join(s, []byte(", "))) + // Output: foo, bar, baz +} + +func ExampleLastIndex() { + fmt.Println(bytes.Index([]byte("go gopher"), []byte("go"))) + fmt.Println(bytes.LastIndex([]byte("go gopher"), []byte("go"))) + fmt.Println(bytes.LastIndex([]byte("go gopher"), []byte("rodent"))) + // Output: + // 0 + // 3 + // -1 +} + +func ExampleLastIndexAny() { + fmt.Println(bytes.LastIndexAny([]byte("go gopher"), "MüQp")) + fmt.Println(bytes.LastIndexAny([]byte("go 地鼠"), "地大")) + fmt.Println(bytes.LastIndexAny([]byte("go gopher"), "z,!.")) + // Output: + // 5 + // 3 + // -1 +} + +func ExampleLastIndexByte() { + fmt.Println(bytes.LastIndexByte([]byte("go gopher"), byte('g'))) + fmt.Println(bytes.LastIndexByte([]byte("go gopher"), byte('r'))) + fmt.Println(bytes.LastIndexByte([]byte("go gopher"), byte('z'))) + // Output: + // 3 + // 8 + // -1 +} + +func ExampleLastIndexFunc() { + fmt.Println(bytes.LastIndexFunc([]byte("go gopher!"), unicode.IsLetter)) + fmt.Println(bytes.LastIndexFunc([]byte("go gopher!"), unicode.IsPunct)) + fmt.Println(bytes.LastIndexFunc([]byte("go gopher!"), unicode.IsNumber)) + // Output: + // 8 + // 9 + // -1 +} + +func ExampleReader_Len() { + fmt.Println(bytes.NewReader([]byte("Hi!")).Len()) + fmt.Println(bytes.NewReader([]byte("こんにちは!")).Len()) + // Output: + // 3 + // 16 +} + +func ExampleRepeat() { + fmt.Printf("ba%s", bytes.Repeat([]byte("na"), 2)) + // Output: banana +} + +func ExampleReplace() { + fmt.Printf("%s\n", bytes.Replace([]byte("oink oink oink"), []byte("k"), []byte("ky"), 2)) + fmt.Printf("%s\n", bytes.Replace([]byte("oink oink oink"), []byte("oink"), []byte("moo"), -1)) + // Output: + // oinky oinky oink + // moo moo moo +} + +func ExampleReplaceAll() { + fmt.Printf("%s\n", bytes.ReplaceAll([]byte("oink oink oink"), []byte("oink"), []byte("moo"))) + // Output: + // moo moo moo +} + +func ExampleRunes() { + rs := bytes.Runes([]byte("go gopher")) + for _, r := range rs { + fmt.Printf("%#U\n", r) + } + // Output: + // U+0067 'g' + // U+006F 'o' + // U+0020 ' ' + // U+0067 'g' + // U+006F 'o' + // U+0070 'p' + // U+0068 'h' + // U+0065 'e' + // U+0072 'r' +} + +func ExampleSplit() { + fmt.Printf("%q\n", bytes.Split([]byte("a,b,c"), []byte(","))) + fmt.Printf("%q\n", bytes.Split([]byte("a man a plan a canal panama"), []byte("a "))) + fmt.Printf("%q\n", bytes.Split([]byte(" xyz "), []byte(""))) + fmt.Printf("%q\n", bytes.Split([]byte(""), []byte("Bernardo O'Higgins"))) + // Output: + // ["a" "b" "c"] + // ["" "man " "plan " "canal panama"] + // [" " "x" "y" "z" " "] + // [""] +} + +func ExampleSplitN() { + fmt.Printf("%q\n", bytes.SplitN([]byte("a,b,c"), []byte(","), 2)) + z := bytes.SplitN([]byte("a,b,c"), []byte(","), 0) + fmt.Printf("%q (nil = %v)\n", z, z == nil) + // Output: + // ["a" "b,c"] + // [] (nil = true) +} + +func ExampleSplitAfter() { + fmt.Printf("%q\n", bytes.SplitAfter([]byte("a,b,c"), []byte(","))) + // Output: ["a," "b," "c"] +} + +func ExampleSplitAfterN() { + fmt.Printf("%q\n", bytes.SplitAfterN([]byte("a,b,c"), []byte(","), 2)) + // Output: ["a," "b,c"] +} + +func ExampleTitle() { + fmt.Printf("%s", bytes.Title([]byte("her royal highness"))) + // Output: Her Royal Highness +} + +func ExampleToTitle() { + fmt.Printf("%s\n", bytes.ToTitle([]byte("loud noises"))) + fmt.Printf("%s\n", bytes.ToTitle([]byte("хлеб"))) + // Output: + // LOUD NOISES + // ХЛЕБ +} + +func ExampleToTitleSpecial() { + str := []byte("ahoj vývojári golang") + totitle := bytes.ToTitleSpecial(unicode.AzeriCase, str) + fmt.Println("Original : " + string(str)) + fmt.Println("ToTitle : " + string(totitle)) + // Output: + // Original : ahoj vývojári golang + // ToTitle : AHOJ VÝVOJÁRİ GOLANG +} + +func ExampleTrim() { + fmt.Printf("[%q]", bytes.Trim([]byte(" !!! Achtung! Achtung! !!! "), "! ")) + // Output: ["Achtung! Achtung"] +} + +func ExampleTrimFunc() { + fmt.Println(string(bytes.TrimFunc([]byte("go-gopher!"), unicode.IsLetter))) + fmt.Println(string(bytes.TrimFunc([]byte("\"go-gopher!\""), unicode.IsLetter))) + fmt.Println(string(bytes.TrimFunc([]byte("go-gopher!"), unicode.IsPunct))) + fmt.Println(string(bytes.TrimFunc([]byte("1234go-gopher!567"), unicode.IsNumber))) + // Output: + // -gopher! + // "go-gopher!" + // go-gopher + // go-gopher! +} + +func ExampleTrimLeft() { + fmt.Print(string(bytes.TrimLeft([]byte("453gopher8257"), "0123456789"))) + // Output: + // gopher8257 +} + +func ExampleTrimLeftFunc() { + fmt.Println(string(bytes.TrimLeftFunc([]byte("go-gopher"), unicode.IsLetter))) + fmt.Println(string(bytes.TrimLeftFunc([]byte("go-gopher!"), unicode.IsPunct))) + fmt.Println(string(bytes.TrimLeftFunc([]byte("1234go-gopher!567"), unicode.IsNumber))) + // Output: + // -gopher + // go-gopher! + // go-gopher!567 +} + +func ExampleTrimPrefix() { + var b = []byte("Goodbye,, world!") + b = bytes.TrimPrefix(b, []byte("Goodbye,")) + b = bytes.TrimPrefix(b, []byte("See ya,")) + fmt.Printf("Hello%s", b) + // Output: Hello, world! +} + +func ExampleTrimSpace() { + fmt.Printf("%s", bytes.TrimSpace([]byte(" \t\n a lone gopher \n\t\r\n"))) + // Output: a lone gopher +} + +func ExampleTrimSuffix() { + var b = []byte("Hello, goodbye, etc!") + b = bytes.TrimSuffix(b, []byte("goodbye, etc!")) + b = bytes.TrimSuffix(b, []byte("gopher")) + b = append(b, bytes.TrimSuffix([]byte("world!"), []byte("x!"))...) + os.Stdout.Write(b) + // Output: Hello, world! +} + +func ExampleTrimRight() { + fmt.Print(string(bytes.TrimRight([]byte("453gopher8257"), "0123456789"))) + // Output: + // 453gopher +} + +func ExampleTrimRightFunc() { + fmt.Println(string(bytes.TrimRightFunc([]byte("go-gopher"), unicode.IsLetter))) + fmt.Println(string(bytes.TrimRightFunc([]byte("go-gopher!"), unicode.IsPunct))) + fmt.Println(string(bytes.TrimRightFunc([]byte("1234go-gopher!567"), unicode.IsNumber))) + // Output: + // go- + // go-gopher + // 1234go-gopher! +} + +func ExampleToLower() { + fmt.Printf("%s", bytes.ToLower([]byte("Gopher"))) + // Output: gopher +} + +func ExampleToLowerSpecial() { + str := []byte("AHOJ VÝVOJÁRİ GOLANG") + totitle := bytes.ToLowerSpecial(unicode.AzeriCase, str) + fmt.Println("Original : " + string(str)) + fmt.Println("ToLower : " + string(totitle)) + // Output: + // Original : AHOJ VÝVOJÁRİ GOLANG + // ToLower : ahoj vývojári golang +} + +func ExampleToUpper() { + fmt.Printf("%s", bytes.ToUpper([]byte("Gopher"))) + // Output: GOPHER +} + +func ExampleToUpperSpecial() { + str := []byte("ahoj vývojári golang") + totitle := bytes.ToUpperSpecial(unicode.AzeriCase, str) + fmt.Println("Original : " + string(str)) + fmt.Println("ToUpper : " + string(totitle)) + // Output: + // Original : ahoj vývojári golang + // ToUpper : AHOJ VÝVOJÁRİ GOLANG +} diff --git a/src/bytes/export_test.go b/src/bytes/export_test.go new file mode 100644 index 0000000..b65428d --- /dev/null +++ b/src/bytes/export_test.go @@ -0,0 +1,8 @@ +// Copyright 2009 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 bytes + +// Export func for testing +var IndexBytePortable = indexBytePortable diff --git a/src/bytes/reader.go b/src/bytes/reader.go new file mode 100644 index 0000000..81c22aa --- /dev/null +++ b/src/bytes/reader.go @@ -0,0 +1,159 @@ +// Copyright 2012 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 bytes + +import ( + "errors" + "io" + "unicode/utf8" +) + +// A Reader implements the io.Reader, io.ReaderAt, io.WriterTo, io.Seeker, +// io.ByteScanner, and io.RuneScanner interfaces by reading from +// a byte slice. +// Unlike a Buffer, a Reader is read-only and supports seeking. +// The zero value for Reader operates like a Reader of an empty slice. +type Reader struct { + s []byte + i int64 // current reading index + prevRune int // index of previous rune; or < 0 +} + +// Len returns the number of bytes of the unread portion of the +// slice. +func (r *Reader) Len() int { + if r.i >= int64(len(r.s)) { + return 0 + } + return int(int64(len(r.s)) - r.i) +} + +// Size returns the original length of the underlying byte slice. +// Size is the number of bytes available for reading via ReadAt. +// The result is unaffected by any method calls except Reset. +func (r *Reader) Size() int64 { return int64(len(r.s)) } + +// Read implements the io.Reader interface. +func (r *Reader) Read(b []byte) (n int, err error) { + if r.i >= int64(len(r.s)) { + return 0, io.EOF + } + r.prevRune = -1 + n = copy(b, r.s[r.i:]) + r.i += int64(n) + return +} + +// ReadAt implements the io.ReaderAt interface. +func (r *Reader) ReadAt(b []byte, off int64) (n int, err error) { + // cannot modify state - see io.ReaderAt + if off < 0 { + return 0, errors.New("bytes.Reader.ReadAt: negative offset") + } + if off >= int64(len(r.s)) { + return 0, io.EOF + } + n = copy(b, r.s[off:]) + if n < len(b) { + err = io.EOF + } + return +} + +// ReadByte implements the io.ByteReader interface. +func (r *Reader) ReadByte() (byte, error) { + r.prevRune = -1 + if r.i >= int64(len(r.s)) { + return 0, io.EOF + } + b := r.s[r.i] + r.i++ + return b, nil +} + +// UnreadByte complements ReadByte in implementing the io.ByteScanner interface. +func (r *Reader) UnreadByte() error { + if r.i <= 0 { + return errors.New("bytes.Reader.UnreadByte: at beginning of slice") + } + r.prevRune = -1 + r.i-- + return nil +} + +// ReadRune implements the io.RuneReader interface. +func (r *Reader) ReadRune() (ch rune, size int, err error) { + if r.i >= int64(len(r.s)) { + r.prevRune = -1 + return 0, 0, io.EOF + } + r.prevRune = int(r.i) + if c := r.s[r.i]; c < utf8.RuneSelf { + r.i++ + return rune(c), 1, nil + } + ch, size = utf8.DecodeRune(r.s[r.i:]) + r.i += int64(size) + return +} + +// UnreadRune complements ReadRune in implementing the io.RuneScanner interface. +func (r *Reader) UnreadRune() error { + if r.i <= 0 { + return errors.New("bytes.Reader.UnreadRune: at beginning of slice") + } + if r.prevRune < 0 { + return errors.New("bytes.Reader.UnreadRune: previous operation was not ReadRune") + } + r.i = int64(r.prevRune) + r.prevRune = -1 + return nil +} + +// Seek implements the io.Seeker interface. +func (r *Reader) Seek(offset int64, whence int) (int64, error) { + r.prevRune = -1 + var abs int64 + switch whence { + case io.SeekStart: + abs = offset + case io.SeekCurrent: + abs = r.i + offset + case io.SeekEnd: + abs = int64(len(r.s)) + offset + default: + return 0, errors.New("bytes.Reader.Seek: invalid whence") + } + if abs < 0 { + return 0, errors.New("bytes.Reader.Seek: negative position") + } + r.i = abs + return abs, nil +} + +// WriteTo implements the io.WriterTo interface. +func (r *Reader) WriteTo(w io.Writer) (n int64, err error) { + r.prevRune = -1 + if r.i >= int64(len(r.s)) { + return 0, nil + } + b := r.s[r.i:] + m, err := w.Write(b) + if m > len(b) { + panic("bytes.Reader.WriteTo: invalid Write count") + } + r.i += int64(m) + n = int64(m) + if m != len(b) && err == nil { + err = io.ErrShortWrite + } + return +} + +// Reset resets the Reader to be reading from b. +func (r *Reader) Reset(b []byte) { *r = Reader{b, 0, -1} } + +// NewReader returns a new Reader reading from b. +func NewReader(b []byte) *Reader { return &Reader{b, 0, -1} } diff --git a/src/bytes/reader_test.go b/src/bytes/reader_test.go new file mode 100644 index 0000000..9119c94 --- /dev/null +++ b/src/bytes/reader_test.go @@ -0,0 +1,319 @@ +// Copyright 2012 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 bytes_test + +import ( + . "bytes" + "fmt" + "io" + "sync" + "testing" +) + +func TestReader(t *testing.T) { + r := NewReader([]byte("0123456789")) + tests := []struct { + off int64 + seek int + n int + want string + wantpos int64 + readerr error + seekerr string + }{ + {seek: io.SeekStart, off: 0, n: 20, want: "0123456789"}, + {seek: io.SeekStart, off: 1, n: 1, want: "1"}, + {seek: io.SeekCurrent, off: 1, wantpos: 3, n: 2, want: "34"}, + {seek: io.SeekStart, off: -1, seekerr: "bytes.Reader.Seek: negative position"}, + {seek: io.SeekStart, off: 1 << 33, wantpos: 1 << 33, readerr: io.EOF}, + {seek: io.SeekCurrent, off: 1, wantpos: 1<<33 + 1, readerr: io.EOF}, + {seek: io.SeekStart, n: 5, want: "01234"}, + {seek: io.SeekCurrent, n: 5, want: "56789"}, + {seek: io.SeekEnd, off: -1, n: 1, wantpos: 9, want: "9"}, + } + + for i, tt := range tests { + pos, err := r.Seek(tt.off, tt.seek) + if err == nil && tt.seekerr != "" { + t.Errorf("%d. want seek error %q", i, tt.seekerr) + continue + } + if err != nil && err.Error() != tt.seekerr { + t.Errorf("%d. seek error = %q; want %q", i, err.Error(), tt.seekerr) + continue + } + if tt.wantpos != 0 && tt.wantpos != pos { + t.Errorf("%d. pos = %d, want %d", i, pos, tt.wantpos) + } + buf := make([]byte, tt.n) + n, err := r.Read(buf) + if err != tt.readerr { + t.Errorf("%d. read = %v; want %v", i, err, tt.readerr) + continue + } + got := string(buf[:n]) + if got != tt.want { + t.Errorf("%d. got %q; want %q", i, got, tt.want) + } + } +} + +func TestReadAfterBigSeek(t *testing.T) { + r := NewReader([]byte("0123456789")) + if _, err := r.Seek(1<<31+5, io.SeekStart); err != nil { + t.Fatal(err) + } + if n, err := r.Read(make([]byte, 10)); n != 0 || err != io.EOF { + t.Errorf("Read = %d, %v; want 0, EOF", n, err) + } +} + +func TestReaderAt(t *testing.T) { + r := NewReader([]byte("0123456789")) + tests := []struct { + off int64 + n int + want string + wanterr any + }{ + {0, 10, "0123456789", nil}, + {1, 10, "123456789", io.EOF}, + {1, 9, "123456789", nil}, + {11, 10, "", io.EOF}, + {0, 0, "", nil}, + {-1, 0, "", "bytes.Reader.ReadAt: negative offset"}, + } + for i, tt := range tests { + b := make([]byte, tt.n) + rn, err := r.ReadAt(b, tt.off) + got := string(b[:rn]) + if got != tt.want { + t.Errorf("%d. got %q; want %q", i, got, tt.want) + } + if fmt.Sprintf("%v", err) != fmt.Sprintf("%v", tt.wanterr) { + t.Errorf("%d. got error = %v; want %v", i, err, tt.wanterr) + } + } +} + +func TestReaderAtConcurrent(t *testing.T) { + // Test for the race detector, to verify ReadAt doesn't mutate + // any state. + r := NewReader([]byte("0123456789")) + var wg sync.WaitGroup + for i := 0; i < 5; i++ { + wg.Add(1) + go func(i int) { + defer wg.Done() + var buf [1]byte + r.ReadAt(buf[:], int64(i)) + }(i) + } + wg.Wait() +} + +func TestEmptyReaderConcurrent(t *testing.T) { + // Test for the race detector, to verify a Read that doesn't yield any bytes + // is okay to use from multiple goroutines. This was our historic behavior. + // See golang.org/issue/7856 + r := NewReader([]byte{}) + var wg sync.WaitGroup + for i := 0; i < 5; i++ { + wg.Add(2) + go func() { + defer wg.Done() + var buf [1]byte + r.Read(buf[:]) + }() + go func() { + defer wg.Done() + r.Read(nil) + }() + } + wg.Wait() +} + +func TestReaderWriteTo(t *testing.T) { + for i := 0; i < 30; i += 3 { + var l int + if i > 0 { + l = len(testString) / i + } + s := testString[:l] + r := NewReader(testBytes[:l]) + var b Buffer + n, err := r.WriteTo(&b) + if expect := int64(len(s)); n != expect { + t.Errorf("got %v; want %v", n, expect) + } + if err != nil { + t.Errorf("for length %d: got error = %v; want nil", l, err) + } + if b.String() != s { + t.Errorf("got string %q; want %q", b.String(), s) + } + if r.Len() != 0 { + t.Errorf("reader contains %v bytes; want 0", r.Len()) + } + } +} + +func TestReaderLen(t *testing.T) { + const data = "hello world" + r := NewReader([]byte(data)) + if got, want := r.Len(), 11; got != want { + t.Errorf("r.Len(): got %d, want %d", got, want) + } + if n, err := r.Read(make([]byte, 10)); err != nil || n != 10 { + t.Errorf("Read failed: read %d %v", n, err) + } + if got, want := r.Len(), 1; got != want { + t.Errorf("r.Len(): got %d, want %d", got, want) + } + if n, err := r.Read(make([]byte, 1)); err != nil || n != 1 { + t.Errorf("Read failed: read %d %v; want 1, nil", n, err) + } + if got, want := r.Len(), 0; got != want { + t.Errorf("r.Len(): got %d, want %d", got, want) + } +} + +var UnreadRuneErrorTests = []struct { + name string + f func(*Reader) +}{ + {"Read", func(r *Reader) { r.Read([]byte{0}) }}, + {"ReadByte", func(r *Reader) { r.ReadByte() }}, + {"UnreadRune", func(r *Reader) { r.UnreadRune() }}, + {"Seek", func(r *Reader) { r.Seek(0, io.SeekCurrent) }}, + {"WriteTo", func(r *Reader) { r.WriteTo(&Buffer{}) }}, +} + +func TestUnreadRuneError(t *testing.T) { + for _, tt := range UnreadRuneErrorTests { + reader := NewReader([]byte("0123456789")) + if _, _, err := reader.ReadRune(); err != nil { + // should not happen + t.Fatal(err) + } + tt.f(reader) + err := reader.UnreadRune() + if err == nil { + t.Errorf("Unreading after %s: expected error", tt.name) + } + } +} + +func TestReaderDoubleUnreadRune(t *testing.T) { + buf := NewBuffer([]byte("groucho")) + if _, _, err := buf.ReadRune(); err != nil { + // should not happen + t.Fatal(err) + } + if err := buf.UnreadByte(); err != nil { + // should not happen + t.Fatal(err) + } + if err := buf.UnreadByte(); err == nil { + t.Fatal("UnreadByte: expected error, got nil") + } +} + +// verify that copying from an empty reader always has the same results, +// regardless of the presence of a WriteTo method. +func TestReaderCopyNothing(t *testing.T) { + type nErr struct { + n int64 + err error + } + type justReader struct { + io.Reader + } + type justWriter struct { + io.Writer + } + discard := justWriter{io.Discard} // hide ReadFrom + + var with, withOut nErr + with.n, with.err = io.Copy(discard, NewReader(nil)) + withOut.n, withOut.err = io.Copy(discard, justReader{NewReader(nil)}) + if with != withOut { + t.Errorf("behavior differs: with = %#v; without: %#v", with, withOut) + } +} + +// tests that Len is affected by reads, but Size is not. +func TestReaderLenSize(t *testing.T) { + r := NewReader([]byte("abc")) + io.CopyN(io.Discard, r, 1) + if r.Len() != 2 { + t.Errorf("Len = %d; want 2", r.Len()) + } + if r.Size() != 3 { + t.Errorf("Size = %d; want 3", r.Size()) + } +} + +func TestReaderReset(t *testing.T) { + r := NewReader([]byte("世界")) + if _, _, err := r.ReadRune(); err != nil { + t.Errorf("ReadRune: unexpected error: %v", err) + } + + const want = "abcdef" + r.Reset([]byte(want)) + if err := r.UnreadRune(); err == nil { + t.Errorf("UnreadRune: expected error, got nil") + } + buf, err := io.ReadAll(r) + if err != nil { + t.Errorf("ReadAll: unexpected error: %v", err) + } + if got := string(buf); got != want { + t.Errorf("ReadAll: got %q, want %q", got, want) + } +} + +func TestReaderZero(t *testing.T) { + if l := (&Reader{}).Len(); l != 0 { + t.Errorf("Len: got %d, want 0", l) + } + + if n, err := (&Reader{}).Read(nil); n != 0 || err != io.EOF { + t.Errorf("Read: got %d, %v; want 0, io.EOF", n, err) + } + + if n, err := (&Reader{}).ReadAt(nil, 11); n != 0 || err != io.EOF { + t.Errorf("ReadAt: got %d, %v; want 0, io.EOF", n, err) + } + + if b, err := (&Reader{}).ReadByte(); b != 0 || err != io.EOF { + t.Errorf("ReadByte: got %d, %v; want 0, io.EOF", b, err) + } + + if ch, size, err := (&Reader{}).ReadRune(); ch != 0 || size != 0 || err != io.EOF { + t.Errorf("ReadRune: got %d, %d, %v; want 0, 0, io.EOF", ch, size, err) + } + + if offset, err := (&Reader{}).Seek(11, io.SeekStart); offset != 11 || err != nil { + t.Errorf("Seek: got %d, %v; want 11, nil", offset, err) + } + + if s := (&Reader{}).Size(); s != 0 { + t.Errorf("Size: got %d, want 0", s) + } + + if (&Reader{}).UnreadByte() == nil { + t.Errorf("UnreadByte: got nil, want error") + } + + if (&Reader{}).UnreadRune() == nil { + t.Errorf("UnreadRune: got nil, want error") + } + + if n, err := (&Reader{}).WriteTo(io.Discard); n != 0 || err != nil { + t.Errorf("WriteTo: got %d, %v; want 0, nil", n, err) + } +} |