go.mod, vendor: update (#3358)

* go.mod, vendor: remove unnecessary dependencies

Commands:
1. go mod tidy
2. go mod vendor

* go.mod, vendor: update cloud.google.com/go

Commands:
1. go get -u cloud.google.com/go
2. go mod tidy
3. go mod vendor

* go.mod, vendor: update cloud.google.com/*

Commands:
1. go get -u cloud.google.com/storage cloud.google.com/logging
2. go mod tidy
3. go mod vendor

* go.mod, .golangci.yml, vendor: update *lint*

Commands:
1. go get -u golang.org/x/tools github.com/golangci/golangci-lint@v1.47.0
2. go mod tidy
3. go mod vendor
4. edit .golangci.yml to suppress new errors (resolved in the same PR later)

* all: fix lint errors

hash.go: copy() recommended by gosimple
parse.go: ent is never nil
verifier.go: signal.Notify() with unbuffered channel is bad. Have no idea why.

* .golangci.yml: adjust godot rules

check-all is deprecated, but still work
if you're hesitating too - I'll remove this commit

14 files changed, 206 insertions, 72 deletions

diff --git a/vendor/github.com/google/go-cmp/cmp/compare.go b/vendor/github.com/google/go-cmp/cmp/compare.go
index 86d0903b8..fd2b3a42b 100644
--- a/vendor/github.com/google/go-cmp/cmp/compare.go
+++ b/vendor/github.com/google/go-cmp/cmp/compare.go
@@ -36,11 +36,12 @@ import (
 	"strings"
 
 	"github.com/google/go-cmp/cmp/internal/diff"
-	"github.com/google/go-cmp/cmp/internal/flags"
 	"github.com/google/go-cmp/cmp/internal/function"
 	"github.com/google/go-cmp/cmp/internal/value"
 )
 
+// TODO(≥go1.18): Use any instead of interface{}.
+
 // Equal reports whether x and y are equal by recursively applying the
 // following rules in the given order to x and y and all of their sub-values:
 //
@@ -319,7 +320,6 @@ func (s *state) tryMethod(t reflect.Type, vx, vy reflect.Value) bool {
 }
 
 func (s *state) callTRFunc(f, v reflect.Value, step Transform) reflect.Value {
-	v = sanitizeValue(v, f.Type().In(0))
 	if !s.dynChecker.Next() {
 		return f.Call([]reflect.Value{v})[0]
 	}
@@ -343,8 +343,6 @@ func (s *state) callTRFunc(f, v reflect.Value, step Transform) reflect.Value {
 }
 
 func (s *state) callTTBFunc(f, x, y reflect.Value) bool {
-	x = sanitizeValue(x, f.Type().In(0))
-	y = sanitizeValue(y, f.Type().In(1))
 	if !s.dynChecker.Next() {
 		return f.Call([]reflect.Value{x, y})[0].Bool()
 	}
@@ -372,19 +370,6 @@ func detectRaces(c chan<- reflect.Value, f reflect.Value, vs ...reflect.Value) {
 	ret = f.Call(vs)[0]
 }
 
-// sanitizeValue converts nil interfaces of type T to those of type R,
-// assuming that T is assignable to R.
-// Otherwise, it returns the input value as is.
-func sanitizeValue(v reflect.Value, t reflect.Type) reflect.Value {
-	// TODO(≥go1.10): Workaround for reflect bug (https://golang.org/issue/22143).
-	if !flags.AtLeastGo110 {
-		if v.Kind() == reflect.Interface && v.IsNil() && v.Type() != t {
-			return reflect.New(t).Elem()
-		}
-	}
-	return v
-}
-
 func (s *state) compareStruct(t reflect.Type, vx, vy reflect.Value) {
 	var addr bool
 	var vax, vay reflect.Value // Addressable versions of vx and vy
diff --git a/vendor/github.com/google/go-cmp/cmp/export_panic.go b/vendor/github.com/google/go-cmp/cmp/export_panic.go
index 5ff0b4218..ae851fe53 100644
--- a/vendor/github.com/google/go-cmp/cmp/export_panic.go
+++ b/vendor/github.com/google/go-cmp/cmp/export_panic.go
@@ -2,6 +2,7 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
+//go:build purego
 // +build purego
 
 package cmp
diff --git a/vendor/github.com/google/go-cmp/cmp/export_unsafe.go b/vendor/github.com/google/go-cmp/cmp/export_unsafe.go
index 21eb54858..e2c0f74e8 100644
--- a/vendor/github.com/google/go-cmp/cmp/export_unsafe.go
+++ b/vendor/github.com/google/go-cmp/cmp/export_unsafe.go
@@ -2,6 +2,7 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
+//go:build !purego
 // +build !purego
 
 package cmp
diff --git a/vendor/github.com/google/go-cmp/cmp/internal/diff/debug_disable.go b/vendor/github.com/google/go-cmp/cmp/internal/diff/debug_disable.go
index 1daaaacc5..36062a604 100644
--- a/vendor/github.com/google/go-cmp/cmp/internal/diff/debug_disable.go
+++ b/vendor/github.com/google/go-cmp/cmp/internal/diff/debug_disable.go
@@ -2,6 +2,7 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
+//go:build !cmp_debug
 // +build !cmp_debug
 
 package diff
diff --git a/vendor/github.com/google/go-cmp/cmp/internal/diff/debug_enable.go b/vendor/github.com/google/go-cmp/cmp/internal/diff/debug_enable.go
index 4b91dbcac..a3b97a1ad 100644
--- a/vendor/github.com/google/go-cmp/cmp/internal/diff/debug_enable.go
+++ b/vendor/github.com/google/go-cmp/cmp/internal/diff/debug_enable.go
@@ -2,6 +2,7 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
+//go:build cmp_debug
 // +build cmp_debug
 
 package diff
diff --git a/vendor/github.com/google/go-cmp/cmp/internal/flags/toolchain_legacy.go b/vendor/github.com/google/go-cmp/cmp/internal/flags/toolchain_legacy.go
deleted file mode 100644
index 82d1d7fbf..000000000
--- a/vendor/github.com/google/go-cmp/cmp/internal/flags/toolchain_legacy.go
+++ /dev/null
@@ -1,10 +0,0 @@
-// Copyright 2019, 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.
-
-// +build !go1.10
-
-package flags
-
-// AtLeastGo110 reports whether the Go toolchain is at least Go 1.10.
-const AtLeastGo110 = false
diff --git a/vendor/github.com/google/go-cmp/cmp/internal/flags/toolchain_recent.go b/vendor/github.com/google/go-cmp/cmp/internal/flags/toolchain_recent.go
deleted file mode 100644
index 8646f0529..000000000
--- a/vendor/github.com/google/go-cmp/cmp/internal/flags/toolchain_recent.go
+++ /dev/null
@@ -1,10 +0,0 @@
-// Copyright 2019, 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.
-
-// +build go1.10
-
-package flags
-
-// AtLeastGo110 reports whether the Go toolchain is at least Go 1.10.
-const AtLeastGo110 = true
diff --git a/vendor/github.com/google/go-cmp/cmp/internal/value/name.go b/vendor/github.com/google/go-cmp/cmp/internal/value/name.go
index b6c12cefb..7b498bb2c 100644
--- a/vendor/github.com/google/go-cmp/cmp/internal/value/name.go
+++ b/vendor/github.com/google/go-cmp/cmp/internal/value/name.go
@@ -9,6 +9,8 @@ import (
 	"strconv"
 )
 
+var anyType = reflect.TypeOf((*interface{})(nil)).Elem()
+
 // TypeString is nearly identical to reflect.Type.String,
 // but has an additional option to specify that full type names be used.
 func TypeString(t reflect.Type, qualified bool) string {
@@ -20,6 +22,11 @@ func appendTypeName(b []byte, t reflect.Type, qualified, elideFunc bool) []byte
 	// of the same name and within the same package,
 	// but declared within the namespace of different functions.
 
+	// Use the "any" alias instead of "interface{}" for better readability.
+	if t == anyType {
+		return append(b, "any"...)
+	}
+
 	// Named type.
 	if t.Name() != "" {
 		if qualified && t.PkgPath() != "" {
diff --git a/vendor/github.com/google/go-cmp/cmp/internal/value/pointer_purego.go b/vendor/github.com/google/go-cmp/cmp/internal/value/pointer_purego.go
index 44f4a5afd..1a71bfcbd 100644
--- a/vendor/github.com/google/go-cmp/cmp/internal/value/pointer_purego.go
+++ b/vendor/github.com/google/go-cmp/cmp/internal/value/pointer_purego.go
@@ -2,6 +2,7 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
+//go:build purego
 // +build purego
 
 package value
diff --git a/vendor/github.com/google/go-cmp/cmp/internal/value/pointer_unsafe.go b/vendor/github.com/google/go-cmp/cmp/internal/value/pointer_unsafe.go
index a605953d4..16e6860af 100644
--- a/vendor/github.com/google/go-cmp/cmp/internal/value/pointer_unsafe.go
+++ b/vendor/github.com/google/go-cmp/cmp/internal/value/pointer_unsafe.go
@@ -2,6 +2,7 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
+//go:build !purego
 // +build !purego
 
 package value
diff --git a/vendor/github.com/google/go-cmp/cmp/path.go b/vendor/github.com/google/go-cmp/cmp/path.go
index 3d45c1a47..c71003463 100644
--- a/vendor/github.com/google/go-cmp/cmp/path.go
+++ b/vendor/github.com/google/go-cmp/cmp/path.go
@@ -178,7 +178,7 @@ type structField struct {
 	unexported bool
 	mayForce   bool                // Forcibly allow visibility
 	paddr      bool                // Was parent addressable?
-	pvx, pvy   reflect.Value       // Parent values (always addressible)
+	pvx, pvy   reflect.Value       // Parent values (always addressable)
 	field      reflect.StructField // Field information
 }
 
@@ -315,7 +315,7 @@ func (tf Transform) Option() Option { return tf.trans }
 // pops the address from the stack. Thus, when traversing into a pointer from
 // reflect.Ptr, reflect.Slice element, or reflect.Map, we can detect cycles
 // by checking whether the pointer has already been visited. The cycle detection
-// uses a seperate stack for the x and y values.
+// uses a separate stack for the x and y values.
 //
 // If a cycle is detected we need to determine whether the two pointers
 // should be considered equal. The definition of equality chosen by Equal
diff --git a/vendor/github.com/google/go-cmp/cmp/report_compare.go b/vendor/github.com/google/go-cmp/cmp/report_compare.go
index 104bb3053..1ef65ac1d 100644
--- a/vendor/github.com/google/go-cmp/cmp/report_compare.go
+++ b/vendor/github.com/google/go-cmp/cmp/report_compare.go
@@ -116,7 +116,10 @@ func (opts formatOptions) FormatDiff(v *valueNode, ptrs *pointerReferences) (out
 	}
 
 	// For leaf nodes, format the value based on the reflect.Values alone.
-	if v.MaxDepth == 0 {
+	// As a special case, treat equal []byte as a leaf nodes.
+	isBytes := v.Type.Kind() == reflect.Slice && v.Type.Elem() == reflect.TypeOf(byte(0))
+	isEqualBytes := isBytes && v.NumDiff+v.NumIgnored+v.NumTransformed == 0
+	if v.MaxDepth == 0 || isEqualBytes {
 		switch opts.DiffMode {
 		case diffUnknown, diffIdentical:
 			// Format Equal.
diff --git a/vendor/github.com/google/go-cmp/cmp/report_reflect.go b/vendor/github.com/google/go-cmp/cmp/report_reflect.go
index 33f03577f..287b89358 100644
--- a/vendor/github.com/google/go-cmp/cmp/report_reflect.go
+++ b/vendor/github.com/google/go-cmp/cmp/report_reflect.go
@@ -207,10 +207,11 @@ func (opts formatOptions) FormatValue(v reflect.Value, parentKind reflect.Kind,
 		// Check whether this is a []byte of text data.
 		if t.Elem() == reflect.TypeOf(byte(0)) {
 			b := v.Bytes()
-			isPrintSpace := func(r rune) bool { return unicode.IsPrint(r) && unicode.IsSpace(r) }
+			isPrintSpace := func(r rune) bool { return unicode.IsPrint(r) || unicode.IsSpace(r) }
 			if len(b) > 0 && utf8.Valid(b) && len(bytes.TrimFunc(b, isPrintSpace)) == 0 {
 				out = opts.formatString("", string(b))
-				return opts.WithTypeMode(emitType).FormatType(t, out)
+				skipType = true
+				return opts.FormatType(t, out)
 			}
 		}
 
@@ -281,7 +282,12 @@ func (opts formatOptions) FormatValue(v reflect.Value, parentKind reflect.Kind,
 		}
 		defer ptrs.Pop()
 
-		skipType = true // Let the underlying value print the type instead
+		// Skip the name only if this is an unnamed pointer type.
+		// Otherwise taking the address of a value does not reproduce
+		// the named pointer type.
+		if v.Type().Name() == "" {
+			skipType = true // Let the underlying value print the type instead
+		}
 		out = opts.FormatValue(v.Elem(), t.Kind(), ptrs)
 		out = wrapTrunkReference(ptrRef, opts.PrintAddresses, out)
 		out = &textWrap{Prefix: "&", Value: out}
@@ -292,7 +298,6 @@ func (opts formatOptions) FormatValue(v reflect.Value, parentKind reflect.Kind,
 		}
 		// Interfaces accept different concrete types,
 		// so configure the underlying value to explicitly print the type.
-		skipType = true // Print the concrete type instead
 		return opts.WithTypeMode(emitType).FormatValue(v.Elem(), t.Kind(), ptrs)
 	default:
 		panic(fmt.Sprintf("%v kind not handled", v.Kind()))
diff --git a/vendor/github.com/google/go-cmp/cmp/report_slices.go b/vendor/github.com/google/go-cmp/cmp/report_slices.go
index 168f92f3c..68b5c1ae1 100644
--- a/vendor/github.com/google/go-cmp/cmp/report_slices.go
+++ b/vendor/github.com/google/go-cmp/cmp/report_slices.go
@@ -7,6 +7,7 @@ package cmp
 import (
 	"bytes"
 	"fmt"
+	"math"
 	"reflect"
 	"strconv"
 	"strings"
@@ -79,7 +80,7 @@ func (opts formatOptions) CanFormatDiffSlice(v *valueNode) bool {
 	}
 
 	// Use specialized string diffing for longer slices or strings.
-	const minLength = 64
+	const minLength = 32
 	return vx.Len() >= minLength && vy.Len() >= minLength
 }
 
@@ -96,15 +97,16 @@ func (opts formatOptions) FormatDiffSlice(v *valueNode) textNode {
 	}
 
 	// Auto-detect the type of the data.
-	var isLinedText, isText, isBinary bool
 	var sx, sy string
+	var ssx, ssy []string
+	var isString, isMostlyText, isPureLinedText, isBinary bool
 	switch {
 	case t.Kind() == reflect.String:
 		sx, sy = vx.String(), vy.String()
-		isText = true // Initial estimate, verify later
+		isString = true
 	case t.Kind() == reflect.Slice && t.Elem() == reflect.TypeOf(byte(0)):
 		sx, sy = string(vx.Bytes()), string(vy.Bytes())
-		isBinary = true // Initial estimate, verify later
+		isString = true
 	case t.Kind() == reflect.Array:
 		// Arrays need to be addressable for slice operations to work.
 		vx2, vy2 := reflect.New(t).Elem(), reflect.New(t).Elem()
@@ -112,13 +114,12 @@ func (opts formatOptions) FormatDiffSlice(v *valueNode) textNode {
 		vy2.Set(vy)
 		vx, vy = vx2, vy2
 	}
-	if isText || isBinary {
-		var numLines, lastLineIdx, maxLineLen int
-		isBinary = !utf8.ValidString(sx) || !utf8.ValidString(sy)
+	if isString {
+		var numTotalRunes, numValidRunes, numLines, lastLineIdx, maxLineLen int
 		for i, r := range sx + sy {
-			if !(unicode.IsPrint(r) || unicode.IsSpace(r)) || r == utf8.RuneError {
-				isBinary = true
-				break
+			numTotalRunes++
+			if (unicode.IsPrint(r) || unicode.IsSpace(r)) && r != utf8.RuneError {
+				numValidRunes++
 			}
 			if r == '\n' {
 				if maxLineLen < i-lastLineIdx {
@@ -128,8 +129,26 @@ func (opts formatOptions) FormatDiffSlice(v *valueNode) textNode {
 				numLines++
 			}
 		}
-		isText = !isBinary
-		isLinedText = isText && numLines >= 4 && maxLineLen <= 1024
+		isPureText := numValidRunes == numTotalRunes
+		isMostlyText = float64(numValidRunes) > math.Floor(0.90*float64(numTotalRunes))
+		isPureLinedText = isPureText && numLines >= 4 && maxLineLen <= 1024
+		isBinary = !isMostlyText
+
+		// Avoid diffing by lines if it produces a significantly more complex
+		// edit script than diffing by bytes.
+		if isPureLinedText {
+			ssx = strings.Split(sx, "\n")
+			ssy = strings.Split(sy, "\n")
+			esLines := diff.Difference(len(ssx), len(ssy), func(ix, iy int) diff.Result {
+				return diff.BoolResult(ssx[ix] == ssy[iy])
+			})
+			esBytes := diff.Difference(len(sx), len(sy), func(ix, iy int) diff.Result {
+				return diff.BoolResult(sx[ix] == sy[iy])
+			})
+			efficiencyLines := float64(esLines.Dist()) / float64(len(esLines))
+			efficiencyBytes := float64(esBytes.Dist()) / float64(len(esBytes))
+			isPureLinedText = efficiencyLines < 4*efficiencyBytes
+		}
 	}
 
 	// Format the string into printable records.
@@ -138,9 +157,7 @@ func (opts formatOptions) FormatDiffSlice(v *valueNode) textNode {
 	switch {
 	// If the text appears to be multi-lined text,
 	// then perform differencing across individual lines.
-	case isLinedText:
-		ssx := strings.Split(sx, "\n")
-		ssy := strings.Split(sy, "\n")
+	case isPureLinedText:
 		list = opts.formatDiffSlice(
 			reflect.ValueOf(ssx), reflect.ValueOf(ssy), 1, "line",
 			func(v reflect.Value, d diffMode) textRecord {
@@ -229,7 +246,7 @@ func (opts formatOptions) FormatDiffSlice(v *valueNode) textNode {
 	// If the text appears to be single-lined text,
 	// then perform differencing in approximately fixed-sized chunks.
 	// The output is printed as quoted strings.
-	case isText:
+	case isMostlyText:
 		list = opts.formatDiffSlice(
 			reflect.ValueOf(sx), reflect.ValueOf(sy), 64, "byte",
 			func(v reflect.Value, d diffMode) textRecord {
@@ -237,7 +254,6 @@ func (opts formatOptions) FormatDiffSlice(v *valueNode) textNode {
 				return textRecord{Diff: d, Value: textLine(s)}
 			},
 		)
-		delim = ""
 
 	// If the text appears to be binary data,
 	// then perform differencing in approximately fixed-sized chunks.
@@ -299,7 +315,7 @@ func (opts formatOptions) FormatDiffSlice(v *valueNode) textNode {
 
 	// Wrap the output with appropriate type information.
 	var out textNode = &textWrap{Prefix: "{", Value: list, Suffix: "}"}
-	if !isText {
+	if !isMostlyText {
 		// The "{...}" byte-sequence literal is not valid Go syntax for strings.
 		// Emit the type for extra clarity (e.g. "string{...}").
 		if t.Kind() == reflect.String {
@@ -338,8 +354,11 @@ func (opts formatOptions) formatDiffSlice(
 	vx, vy reflect.Value, chunkSize int, name string,
 	makeRec func(reflect.Value, diffMode) textRecord,
 ) (list textList) {
-	es := diff.Difference(vx.Len(), vy.Len(), func(ix int, iy int) diff.Result {
-		return diff.BoolResult(vx.Index(ix).Interface() == vy.Index(iy).Interface())
+	eq := func(ix, iy int) bool {
+		return vx.Index(ix).Interface() == vy.Index(iy).Interface()
+	}
+	es := diff.Difference(vx.Len(), vy.Len(), func(ix, iy int) diff.Result {
+		return diff.BoolResult(eq(ix, iy))
 	})
 
 	appendChunks := func(v reflect.Value, d diffMode) int {
@@ -364,6 +383,7 @@ func (opts formatOptions) formatDiffSlice(
 
 	groups := coalesceAdjacentEdits(name, es)
 	groups = coalesceInterveningIdentical(groups, chunkSize/4)
+	groups = cleanupSurroundingIdentical(groups, eq)
 	maxGroup := diffStats{Name: name}
 	for i, ds := range groups {
 		if maxLen >= 0 && numDiffs >= maxLen {
@@ -416,25 +436,36 @@ func (opts formatOptions) formatDiffSlice(
 
 // coalesceAdjacentEdits coalesces the list of edits into groups of adjacent
 // equal or unequal counts.
+//
+// Example:
+//
+//	Input:  "..XXY...Y"
+//	Output: [
+//		{NumIdentical: 2},
+//		{NumRemoved: 2, NumInserted 1},
+//		{NumIdentical: 3},
+//		{NumInserted: 1},
+//	]
+//
 func coalesceAdjacentEdits(name string, es diff.EditScript) (groups []diffStats) {
-	var prevCase int // Arbitrary index into which case last occurred
-	lastStats := func(i int) *diffStats {
-		if prevCase != i {
+	var prevMode byte
+	lastStats := func(mode byte) *diffStats {
+		if prevMode != mode {
 			groups = append(groups, diffStats{Name: name})
-			prevCase = i
+			prevMode = mode
 		}
 		return &groups[len(groups)-1]
 	}
 	for _, e := range es {
 		switch e {
 		case diff.Identity:
-			lastStats(1).NumIdentical++
+			lastStats('=').NumIdentical++
 		case diff.UniqueX:
-			lastStats(2).NumRemoved++
+			lastStats('!').NumRemoved++
 		case diff.UniqueY:
-			lastStats(2).NumInserted++
+			lastStats('!').NumInserted++
 		case diff.Modified:
-			lastStats(2).NumModified++
+			lastStats('!').NumModified++
 		}
 	}
 	return groups
@@ -444,6 +475,35 @@ func coalesceAdjacentEdits(name string, es diff.EditScript) (groups []diffStats)
 // equal groups into adjacent unequal groups that currently result in a
 // dual inserted/removed printout. This acts as a high-pass filter to smooth
 // out high-frequency changes within the windowSize.
+//
+// Example:
+//
+//	WindowSize: 16,
+//	Input: [
+//		{NumIdentical: 61},              // group 0
+//		{NumRemoved: 3, NumInserted: 1}, // group 1
+//		{NumIdentical: 6},               // ├── coalesce
+//		{NumInserted: 2},                // ├── coalesce
+//		{NumIdentical: 1},               // ├── coalesce
+//		{NumRemoved: 9},                 // └── coalesce
+//		{NumIdentical: 64},              // group 2
+//		{NumRemoved: 3, NumInserted: 1}, // group 3
+//		{NumIdentical: 6},               // ├── coalesce
+//		{NumInserted: 2},                // ├── coalesce
+//		{NumIdentical: 1},               // ├── coalesce
+//		{NumRemoved: 7},                 // ├── coalesce
+//		{NumIdentical: 1},               // ├── coalesce
+//		{NumRemoved: 2},                 // └── coalesce
+//		{NumIdentical: 63},              // group 4
+//	]
+//	Output: [
+//		{NumIdentical: 61},
+//		{NumIdentical: 7, NumRemoved: 12, NumInserted: 3},
+//		{NumIdentical: 64},
+//		{NumIdentical: 8, NumRemoved: 12, NumInserted: 3},
+//		{NumIdentical: 63},
+//	]
+//
 func coalesceInterveningIdentical(groups []diffStats, windowSize int) []diffStats {
 	groups, groupsOrig := groups[:0], groups
 	for i, ds := range groupsOrig {
@@ -463,3 +523,91 @@ func coalesceInterveningIdentical(groups []diffStats, windowSize int) []diffStat
 	}
 	return groups
 }
+
+// cleanupSurroundingIdentical scans through all unequal groups, and
+// moves any leading sequence of equal elements to the preceding equal group and
+// moves and trailing sequence of equal elements to the succeeding equal group.
+//
+// This is necessary since coalesceInterveningIdentical may coalesce edit groups
+// together such that leading/trailing spans of equal elements becomes possible.
+// Note that this can occur even with an optimal diffing algorithm.
+//
+// Example:
+//
+//	Input: [
+//		{NumIdentical: 61},
+//		{NumIdentical: 1 , NumRemoved: 11, NumInserted: 2}, // assume 3 leading identical elements
+//		{NumIdentical: 67},
+//		{NumIdentical: 7, NumRemoved: 12, NumInserted: 3},  // assume 10 trailing identical elements
+//		{NumIdentical: 54},
+//	]
+//	Output: [
+//		{NumIdentical: 64}, // incremented by 3
+//		{NumRemoved: 9},
+//		{NumIdentical: 67},
+//		{NumRemoved: 9},
+//		{NumIdentical: 64}, // incremented by 10
+//	]
+//
+func cleanupSurroundingIdentical(groups []diffStats, eq func(i, j int) bool) []diffStats {
+	var ix, iy int // indexes into sequence x and y
+	for i, ds := range groups {
+		// Handle equal group.
+		if ds.NumDiff() == 0 {
+			ix += ds.NumIdentical
+			iy += ds.NumIdentical
+			continue
+		}
+
+		// Handle unequal group.
+		nx := ds.NumIdentical + ds.NumRemoved + ds.NumModified
+		ny := ds.NumIdentical + ds.NumInserted + ds.NumModified
+		var numLeadingIdentical, numTrailingIdentical int
+		for j := 0; j < nx && j < ny && eq(ix+j, iy+j); j++ {
+			numLeadingIdentical++
+		}
+		for j := 0; j < nx && j < ny && eq(ix+nx-1-j, iy+ny-1-j); j++ {
+			numTrailingIdentical++
+		}
+		if numIdentical := numLeadingIdentical + numTrailingIdentical; numIdentical > 0 {
+			if numLeadingIdentical > 0 {
+				// Remove leading identical span from this group and
+				// insert it into the preceding group.
+				if i-1 >= 0 {
+					groups[i-1].NumIdentical += numLeadingIdentical
+				} else {
+					// No preceding group exists, so prepend a new group,
+					// but do so after we finish iterating over all groups.
+					defer func() {
+						groups = append([]diffStats{{Name: groups[0].Name, NumIdentical: numLeadingIdentical}}, groups...)
+					}()
+				}
+				// Increment indexes since the preceding group would have handled this.
+				ix += numLeadingIdentical
+				iy += numLeadingIdentical
+			}
+			if numTrailingIdentical > 0 {
+				// Remove trailing identical span from this group and
+				// insert it into the succeeding group.
+				if i+1 < len(groups) {
+					groups[i+1].NumIdentical += numTrailingIdentical
+				} else {
+					// No succeeding group exists, so append a new group,
+					// but do so after we finish iterating over all groups.
+					defer func() {
+						groups = append(groups, diffStats{Name: groups[len(groups)-1].Name, NumIdentical: numTrailingIdentical})
+					}()
+				}
+				// Do not increment indexes since the succeeding group will handle this.
+			}
+
+			// Update this group since some identical elements were removed.
+			nx -= numIdentical
+			ny -= numIdentical
+			groups[i] = diffStats{Name: ds.Name, NumRemoved: nx, NumInserted: ny}
+		}
+		ix += nx
+		iy += ny
+	}
+	return groups
+}