[dev.boringcrypto] all: merge master into dev.boringcrypto

Change-Id: Ia8ddd4e52dcfe87f9daef2edd37c8155fcae7f5a

7 files changed, 148 insertions, 66 deletions

diff --git a/src/strings/builder.go b/src/strings/builder.go
index ac58f34e1d..3f33a87508 100644
--- a/src/strings/builder.go
+++ b/src/strings/builder.go
@@ -50,6 +50,11 @@ func (b *Builder) String() string {
 // Len returns the number of accumulated bytes; b.Len() == len(b.String()).
 func (b *Builder) Len() int { return len(b.buf) }
 
+// Cap returns the capacity of the builder's underlying byte slice. It is the
+// total space allocated for the string being built and includes any bytes
+// already written.
+func (b *Builder) Cap() int { return cap(b.buf) }
+
 // Reset resets the Builder to be empty.
 func (b *Builder) Reset() {
 	b.addr = nil
diff --git a/src/strings/builder_test.go b/src/strings/builder_test.go
index 949f214619..9e597015d8 100644
--- a/src/strings/builder_test.go
+++ b/src/strings/builder_test.go
@@ -20,6 +20,9 @@ func check(t *testing.T, b *Builder, want string) {
 	if n := b.Len(); n != len(got) {
 		t.Errorf("Len: got %d; but len(String()) is %d", n, len(got))
 	}
+	if n := b.Cap(); n < len(got) {
+		t.Errorf("Cap: got %d; but len(String()) is %d", n, len(got))
+	}
 }
 
 func TestBuilder(t *testing.T) {
@@ -89,6 +92,9 @@ func TestBuilderGrow(t *testing.T) {
 		allocs := testing.AllocsPerRun(100, func() {
 			var b Builder
 			b.Grow(growLen) // should be only alloc, when growLen > 0
+			if b.Cap() < growLen {
+				t.Fatalf("growLen=%d: Cap() is lower than growLen", growLen)
+			}
 			b.Write(p)
 			if b.String() != string(p) {
 				t.Fatalf("growLen=%d: bad data written after Grow", growLen)
@@ -227,6 +233,16 @@ func TestBuilderCopyPanic(t *testing.T) {
 			},
 		},
 		{
+			name:      "Cap",
+			wantPanic: false,
+			fn: func() {
+				var a Builder
+				a.WriteByte('x')
+				b := a
+				b.Cap()
+			},
+		},
+		{
 			name:      "Reset",
 			wantPanic: false,
 			fn: func() {
diff --git a/src/strings/compare_test.go b/src/strings/compare_test.go
index bc12e421b0..5d5334461c 100644
--- a/src/strings/compare_test.go
+++ b/src/strings/compare_test.go
@@ -8,6 +8,7 @@ package strings_test
 // Benchmarks omitted since the underlying implementation is identical.
 
 import (
+	"internal/testenv"
 	. "strings"
 	"testing"
 )
@@ -52,10 +53,21 @@ func TestCompareIdenticalString(t *testing.T) {
 }
 
 func TestCompareStrings(t *testing.T) {
-	n := 128
+	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 := 0; len < 128; len++ {
+	lastLen := 0
+	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)
@@ -67,21 +79,22 @@ func TestCompareStrings(t *testing.T) {
 			b[i] = 9
 		}
 
-		cmp := Compare(string(a[:len]), string(b[:len]))
+		sa, sb := string(a), string(b)
+		cmp := Compare(sa[:len], sb[:len])
 		if cmp != 0 {
 			t.Errorf(`CompareIdentical(%d) = %d`, len, cmp)
 		}
 		if len > 0 {
-			cmp = Compare(string(a[:len-1]), string(b[:len]))
+			cmp = Compare(sa[:len-1], sb[:len])
 			if cmp != -1 {
 				t.Errorf(`CompareAshorter(%d) = %d`, len, cmp)
 			}
-			cmp = Compare(string(a[:len]), string(b[:len-1]))
+			cmp = Compare(sa[:len], sb[:len-1])
 			if cmp != 1 {
 				t.Errorf(`CompareBshorter(%d) = %d`, len, cmp)
 			}
 		}
-		for k := 0; k < len; k++ {
+		for k := lastLen; k < len; k++ {
 			b[k] = a[k] - 1
 			cmp = Compare(string(a[:len]), string(b[:len]))
 			if cmp != 1 {
@@ -94,5 +107,6 @@ func TestCompareStrings(t *testing.T) {
 			}
 			b[k] = a[k]
 		}
+		lastLen = len
 	}
 }
diff --git a/src/strings/export_test.go b/src/strings/export_test.go
index 17c806aa56..b39cee6b1d 100644
--- a/src/strings/export_test.go
+++ b/src/strings/export_test.go
@@ -5,10 +5,12 @@
 package strings
 
 func (r *Replacer) Replacer() interface{} {
+	r.once.Do(r.buildOnce)
 	return r.r
 }
 
 func (r *Replacer) PrintTrie() string {
+	r.once.Do(r.buildOnce)
 	gen := r.r.(*genericReplacer)
 	return gen.printNode(&gen.root, 0)
 }
diff --git a/src/strings/replace.go b/src/strings/replace.go
index 58a11a63db..dbda950194 100644
--- a/src/strings/replace.go
+++ b/src/strings/replace.go
@@ -4,12 +4,17 @@
 
 package strings
 
-import "io"
+import (
+	"io"
+	"sync"
+)
 
 // Replacer replaces a list of strings with replacements.
 // It is safe for concurrent use by multiple goroutines.
 type Replacer struct {
-	r replacer
+	once   sync.Once // guards buildOnce method
+	r      replacer
+	oldnew []string
 }
 
 // replacer is the interface that a replacement algorithm needs to implement.
@@ -25,15 +30,24 @@ func NewReplacer(oldnew ...string) *Replacer {
 	if len(oldnew)%2 == 1 {
 		panic("strings.NewReplacer: odd argument count")
 	}
+	return &Replacer{oldnew: append([]string(nil), oldnew...)}
+}
+
+func (r *Replacer) buildOnce() {
+	r.r = r.build()
+	r.oldnew = nil
+}
 
+func (b *Replacer) build() replacer {
+	oldnew := b.oldnew
 	if len(oldnew) == 2 && len(oldnew[0]) > 1 {
-		return &Replacer{r: makeSingleStringReplacer(oldnew[0], oldnew[1])}
+		return makeSingleStringReplacer(oldnew[0], oldnew[1])
 	}
 
 	allNewBytes := true
 	for i := 0; i < len(oldnew); i += 2 {
 		if len(oldnew[i]) != 1 {
-			return &Replacer{r: makeGenericReplacer(oldnew)}
+			return makeGenericReplacer(oldnew)
 		}
 		if len(oldnew[i+1]) != 1 {
 			allNewBytes = false
@@ -52,7 +66,7 @@ func NewReplacer(oldnew ...string) *Replacer {
 			n := oldnew[i+1][0]
 			r[o] = n
 		}
-		return &Replacer{r: &r}
+		return &r
 	}
 
 	r := byteStringReplacer{toReplace: make([]string, 0, len(oldnew)/2)}
@@ -71,16 +85,18 @@ func NewReplacer(oldnew ...string) *Replacer {
 		r.replacements[o] = []byte(n)
 
 	}
-	return &Replacer{r: &r}
+	return &r
 }
 
 // Replace returns a copy of s with all replacements performed.
 func (r *Replacer) Replace(s string) string {
+	r.once.Do(r.buildOnce)
 	return r.r.Replace(s)
 }
 
 // WriteString writes s to w with all replacements performed.
 func (r *Replacer) WriteString(w io.Writer, s string) (n int, err error) {
+	r.once.Do(r.buildOnce)
 	return r.r.WriteString(w, s)
 }
 
diff --git a/src/strings/strings.go b/src/strings/strings.go
index adbbe742fc..df95715ec8 100644
--- a/src/strings/strings.go
+++ b/src/strings/strings.go
@@ -423,27 +423,20 @@ func Join(a []string, sep string) string {
 		return ""
 	case 1:
 		return a[0]
-	case 2:
-		// Special case for common small values.
-		// Remove if golang.org/issue/6714 is fixed
-		return a[0] + sep + a[1]
-	case 3:
-		// Special case for common small values.
-		// Remove if golang.org/issue/6714 is fixed
-		return a[0] + sep + a[1] + sep + a[2]
 	}
 	n := len(sep) * (len(a) - 1)
 	for i := 0; i < len(a); i++ {
 		n += len(a[i])
 	}
 
-	b := make([]byte, n)
-	bp := copy(b, a[0])
+	var b Builder
+	b.Grow(n)
+	b.WriteString(a[0])
 	for _, s := range a[1:] {
-		bp += copy(b[bp:], sep)
-		bp += copy(b[bp:], s)
+		b.WriteString(sep)
+		b.WriteString(s)
 	}
-	return string(b)
+	return b.String()
 }
 
 // HasPrefix tests whether the string s begins with prefix.
@@ -466,9 +459,7 @@ func Map(mapping func(rune) rune, s string) string {
 
 	// The output buffer b is initialized on demand, the first
 	// time a character differs.
-	var b []byte
-	// nbytes is the number of bytes encoded in b.
-	var nbytes int
+	var b Builder
 
 	for i, c := range s {
 		r := mapping(c)
@@ -476,15 +467,10 @@ func Map(mapping func(rune) rune, s string) string {
 			continue
 		}
 
-		b = make([]byte, len(s)+utf8.UTFMax)
-		nbytes = copy(b, s[:i])
+		b.Grow(len(s) + utf8.UTFMax)
+		b.WriteString(s[:i])
 		if r >= 0 {
-			if r < utf8.RuneSelf {
-				b[nbytes] = byte(r)
-				nbytes++
-			} else {
-				nbytes += utf8.EncodeRune(b[nbytes:], r)
-			}
+			b.WriteRune(r)
 		}
 
 		if c == utf8.RuneError {
@@ -501,33 +487,28 @@ func Map(mapping func(rune) rune, s string) string {
 		break
 	}
 
-	if b == nil {
+	// Fast path for unchanged input
+	if b.Cap() == 0 { // didn't call b.Grow above
 		return s
 	}
 
 	for _, c := range s {
 		r := mapping(c)
 
-		// common case
-		if (0 <= r && r < utf8.RuneSelf) && nbytes < len(b) {
-			b[nbytes] = byte(r)
-			nbytes++
-			continue
-		}
-
-		// b is not big enough or r is not a ASCII rune.
 		if r >= 0 {
-			if nbytes+utf8.UTFMax >= len(b) {
-				// Grow the buffer.
-				nb := make([]byte, 2*len(b))
-				copy(nb, b[:nbytes])
-				b = nb
+			// common case
+			// Due to inlining, it is more performant to determine if WriteByte should be
+			// invoked rather than always call WriteRune
+			if r < utf8.RuneSelf {
+				b.WriteByte(byte(r))
+			} else {
+				// r is not a ASCII rune.
+				b.WriteRune(r)
 			}
-			nbytes += utf8.EncodeRune(b[nbytes:], r)
 		}
 	}
 
-	return string(b[:nbytes])
+	return b.String()
 }
 
 // Repeat returns a new string consisting of count copies of the string s.
@@ -535,23 +516,33 @@ func Map(mapping func(rune) rune, s string) string {
 // It panics if count is negative or if
 // the result of (len(s) * count) overflows.
 func Repeat(s string, count int) string {
+	if count == 0 {
+		return ""
+	}
+
 	// Since we cannot return an error on overflow,
 	// we should panic if the repeat will generate
 	// an overflow.
 	// See Issue golang.org/issue/16237
 	if count < 0 {
 		panic("strings: negative Repeat count")
-	} else if count > 0 && len(s)*count/count != len(s) {
+	} else if len(s)*count/count != len(s) {
 		panic("strings: Repeat count causes overflow")
 	}
 
-	b := make([]byte, len(s)*count)
-	bp := copy(b, s)
-	for bp < len(b) {
-		copy(b[bp:], b[:bp])
-		bp *= 2
+	n := len(s) * count
+	var b Builder
+	b.Grow(n)
+	b.WriteString(s)
+	for b.Len() < n {
+		if b.Len() <= n/2 {
+			b.WriteString(b.String())
+		} else {
+			b.WriteString(b.String()[:n-b.Len()])
+			break
+		}
 	}
-	return string(b)
+	return b.String()
 }
 
 // ToUpper returns a copy of the string s with all Unicode letters mapped to their upper case.
@@ -616,21 +607,21 @@ func ToLower(s string) string {
 func ToTitle(s string) string { return Map(unicode.ToTitle, s) }
 
 // ToUpperSpecial returns a copy of the string s with all Unicode letters mapped to their
-// upper case, giving priority to the special casing rules.
+// upper case using the case mapping specified by c.
 func ToUpperSpecial(c unicode.SpecialCase, s string) string {
-	return Map(func(r rune) rune { return c.ToUpper(r) }, s)
+	return Map(c.ToUpper, s)
 }
 
 // ToLowerSpecial returns a copy of the string s with all Unicode letters mapped to their
-// lower case, giving priority to the special casing rules.
+// lower case using the case mapping specified by c.
 func ToLowerSpecial(c unicode.SpecialCase, s string) string {
-	return Map(func(r rune) rune { return c.ToLower(r) }, s)
+	return Map(c.ToLower, s)
 }
 
 // ToTitleSpecial returns a copy of the string s with all Unicode letters mapped to their
 // title case, giving priority to the special casing rules.
 func ToTitleSpecial(c unicode.SpecialCase, s string) string {
-	return Map(func(r rune) rune { return c.ToTitle(r) }, s)
+	return Map(c.ToTitle, s)
 }
 
 // isSeparator reports whether the rune could mark a word boundary.
@@ -797,6 +788,8 @@ func Trim(s string, cutset string) string {
 
 // TrimLeft returns a slice of the string s with all leading
 // Unicode code points contained in cutset removed.
+//
+// To remove a prefix, use TrimPrefix instead.
 func TrimLeft(s string, cutset string) string {
 	if s == "" || cutset == "" {
 		return s
@@ -806,6 +799,8 @@ func TrimLeft(s string, cutset string) string {
 
 // TrimRight returns a slice of the string s, with all trailing
 // Unicode code points contained in cutset removed.
+//
+// To remove a suffix, use TrimSuffix instead.
 func TrimRight(s string, cutset string) string {
 	if s == "" || cutset == "" {
 		return s
diff --git a/src/strings/strings_test.go b/src/strings/strings_test.go
index 78bc573e5f..20bc484f39 100644
--- a/src/strings/strings_test.go
+++ b/src/strings/strings_test.go
@@ -10,6 +10,7 @@ import (
 	"io"
 	"math/rand"
 	"reflect"
+	"strconv"
 	. "strings"
 	"testing"
 	"unicode"
@@ -673,6 +674,19 @@ func TestMap(t *testing.T) {
 	if m != s {
 		t.Errorf("encoding not handled correctly: expected %q got %q", s, m)
 	}
+
+	// 9. Check mapping occurs in the front, middle and back
+	trimSpaces := func(r rune) rune {
+		if unicode.IsSpace(r) {
+			return -1
+		}
+		return r
+	}
+	m = Map(trimSpaces, "   abc    123   ")
+	expect = "abc123"
+	if m != expect {
+		t.Errorf("trimSpaces: expected %q got %q", expect, m)
+	}
 }
 
 func TestToUpper(t *testing.T) { runStringTests(t, ToUpper, "ToUpper", upperTests) }
@@ -1647,8 +1661,15 @@ func BenchmarkSplitNMultiByteSeparator(b *testing.B) {
 }
 
 func BenchmarkRepeat(b *testing.B) {
-	for i := 0; i < b.N; i++ {
-		Repeat("-", 80)
+	s := "0123456789"
+	for _, n := range []int{5, 10} {
+		for _, c := range []int{1, 2, 6} {
+			b.Run(fmt.Sprintf("%dx%d", n, c), func(b *testing.B) {
+				for i := 0; i < b.N; i++ {
+					Repeat(s[:n], c)
+				}
+			})
+		}
 	}
 }
 
@@ -1691,3 +1712,16 @@ func BenchmarkIndexPeriodic(b *testing.B) {
 		})
 	}
 }
+
+func BenchmarkJoin(b *testing.B) {
+	vals := []string{"red", "yellow", "pink", "green", "purple", "orange", "blue"}
+	for l := 0; l <= len(vals); l++ {
+		b.Run(strconv.Itoa(l), func(b *testing.B) {
+			b.ReportAllocs()
+			vals := vals[:l]
+			for i := 0; i < b.N; i++ {
+				Join(vals, " and ")
+			}
+		})
+	}
+}