aboutsummaryrefslogtreecommitdiffstats
path: root/vendor/github.com/google/go-cmp/cmp/internal
diff options
context:
space:
mode:
authorDmitry Vyukov <dvyukov@google.com>2021-02-22 20:37:25 +0100
committerDmitry Vyukov <dvyukov@google.com>2021-02-22 21:02:12 +0100
commitfcc6d71be2c3ce7d9305c04fc2e87af554571bac (patch)
treeb01dbb3d1e2988e28ea158d2d543d603ec0b9569 /vendor/github.com/google/go-cmp/cmp/internal
parent8f23c528ad5a943b9ffec5dcaf332fd0f614006e (diff)
go.mod: update golangci-lint to v1.37
Diffstat (limited to 'vendor/github.com/google/go-cmp/cmp/internal')
-rw-r--r--vendor/github.com/google/go-cmp/cmp/internal/diff/debug_disable.go2
-rw-r--r--vendor/github.com/google/go-cmp/cmp/internal/diff/debug_enable.go2
-rw-r--r--vendor/github.com/google/go-cmp/cmp/internal/diff/diff.go50
-rw-r--r--vendor/github.com/google/go-cmp/cmp/internal/flags/flags.go2
-rw-r--r--vendor/github.com/google/go-cmp/cmp/internal/flags/toolchain_legacy.go2
-rw-r--r--vendor/github.com/google/go-cmp/cmp/internal/flags/toolchain_recent.go2
-rw-r--r--vendor/github.com/google/go-cmp/cmp/internal/function/func.go2
-rw-r--r--vendor/github.com/google/go-cmp/cmp/internal/value/name.go2
-rw-r--r--vendor/github.com/google/go-cmp/cmp/internal/value/pointer_purego.go2
-rw-r--r--vendor/github.com/google/go-cmp/cmp/internal/value/pointer_unsafe.go2
-rw-r--r--vendor/github.com/google/go-cmp/cmp/internal/value/sort.go2
-rw-r--r--vendor/github.com/google/go-cmp/cmp/internal/value/zero.go2
12 files changed, 39 insertions, 33 deletions
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 fe98dcc67..1daaaacc5 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
@@ -1,6 +1,6 @@
// 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.md file.
+// license that can be found in the LICENSE file.
// +build !cmp_debug
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 597b6ae56..4b91dbcac 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
@@ -1,6 +1,6 @@
// 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.md file.
+// license that can be found in the LICENSE file.
// +build cmp_debug
diff --git a/vendor/github.com/google/go-cmp/cmp/internal/diff/diff.go b/vendor/github.com/google/go-cmp/cmp/internal/diff/diff.go
index 730e223ee..bc196b16c 100644
--- a/vendor/github.com/google/go-cmp/cmp/internal/diff/diff.go
+++ b/vendor/github.com/google/go-cmp/cmp/internal/diff/diff.go
@@ -1,6 +1,6 @@
// 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.md file.
+// license that can be found in the LICENSE file.
// Package diff implements an algorithm for producing edit-scripts.
// The edit-script is a sequence of operations needed to transform one list
@@ -119,7 +119,7 @@ func (r Result) Similar() bool {
return r.NumSame+1 >= r.NumDiff
}
-var randInt = rand.New(rand.NewSource(time.Now().Unix())).Intn(2)
+var randBool = rand.New(rand.NewSource(time.Now().Unix())).Intn(2) == 0
// Difference reports whether two lists of lengths nx and ny are equal
// given the definition of equality provided as f.
@@ -168,17 +168,6 @@ func Difference(nx, ny int, f EqualFunc) (es EditScript) {
// A vertical edge is equivalent to inserting a symbol from list Y.
// A diagonal edge is equivalent to a matching symbol between both X and Y.
- // To ensure flexibility in changing the algorithm in the future,
- // introduce some degree of deliberate instability.
- // This is achieved by fiddling the zigzag iterator to start searching
- // the graph starting from the bottom-right versus than the top-left.
- // The result may differ depending on the starting search location,
- // but still produces a valid edit script.
- zigzagInit := randInt // either 0 or 1
- if flags.Deterministic {
- zigzagInit = 0
- }
-
// Invariants:
// • 0 ≤ fwdPath.X ≤ (fwdFrontier.X, revFrontier.X) ≤ revPath.X ≤ nx
// • 0 ≤ fwdPath.Y ≤ (fwdFrontier.Y, revFrontier.Y) ≤ revPath.Y ≤ ny
@@ -197,6 +186,11 @@ func Difference(nx, ny int, f EqualFunc) (es EditScript) {
// approximately the square-root of the search budget.
searchBudget := 4 * (nx + ny) // O(n)
+ // Running the tests with the "cmp_debug" build tag prints a visualization
+ // of the algorithm running in real-time. This is educational for
+ // understanding how the algorithm works. See debug_enable.go.
+ f = debug.Begin(nx, ny, f, &fwdPath.es, &revPath.es)
+
// The algorithm below is a greedy, meet-in-the-middle algorithm for
// computing sub-optimal edit-scripts between two lists.
//
@@ -214,22 +208,28 @@ func Difference(nx, ny int, f EqualFunc) (es EditScript) {
// frontier towards the opposite corner.
// • This algorithm terminates when either the X coordinates or the
// Y coordinates of the forward and reverse frontier points ever intersect.
- //
+
// This algorithm is correct even if searching only in the forward direction
// or in the reverse direction. We do both because it is commonly observed
// that two lists commonly differ because elements were added to the front
// or end of the other list.
//
- // Running the tests with the "cmp_debug" build tag prints a visualization
- // of the algorithm running in real-time. This is educational for
- // understanding how the algorithm works. See debug_enable.go.
- f = debug.Begin(nx, ny, f, &fwdPath.es, &revPath.es)
- for {
+ // Non-deterministically start with either the forward or reverse direction
+ // to introduce some deliberate instability so that we have the flexibility
+ // to change this algorithm in the future.
+ if flags.Deterministic || randBool {
+ goto forwardSearch
+ } else {
+ goto reverseSearch
+ }
+
+forwardSearch:
+ {
// Forward search from the beginning.
if fwdFrontier.X >= revFrontier.X || fwdFrontier.Y >= revFrontier.Y || searchBudget == 0 {
- break
+ goto finishSearch
}
- for stop1, stop2, i := false, false, zigzagInit; !(stop1 && stop2) && searchBudget > 0; i++ {
+ for stop1, stop2, i := false, false, 0; !(stop1 && stop2) && searchBudget > 0; i++ {
// Search in a diagonal pattern for a match.
z := zigzag(i)
p := point{fwdFrontier.X + z, fwdFrontier.Y - z}
@@ -262,10 +262,14 @@ func Difference(nx, ny int, f EqualFunc) (es EditScript) {
} else {
fwdFrontier.Y++
}
+ goto reverseSearch
+ }
+reverseSearch:
+ {
// Reverse search from the end.
if fwdFrontier.X >= revFrontier.X || fwdFrontier.Y >= revFrontier.Y || searchBudget == 0 {
- break
+ goto finishSearch
}
for stop1, stop2, i := false, false, 0; !(stop1 && stop2) && searchBudget > 0; i++ {
// Search in a diagonal pattern for a match.
@@ -300,8 +304,10 @@ func Difference(nx, ny int, f EqualFunc) (es EditScript) {
} else {
revFrontier.Y--
}
+ goto forwardSearch
}
+finishSearch:
// Join the forward and reverse paths and then append the reverse path.
fwdPath.connect(revPath.point, f)
for i := len(revPath.es) - 1; i >= 0; i-- {
diff --git a/vendor/github.com/google/go-cmp/cmp/internal/flags/flags.go b/vendor/github.com/google/go-cmp/cmp/internal/flags/flags.go
index a9e7fc0b5..d8e459c9b 100644
--- a/vendor/github.com/google/go-cmp/cmp/internal/flags/flags.go
+++ b/vendor/github.com/google/go-cmp/cmp/internal/flags/flags.go
@@ -1,6 +1,6 @@
// 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.md file.
+// license that can be found in the LICENSE file.
package flags
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
index 01aed0a15..82d1d7fbf 100644
--- 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
@@ -1,6 +1,6 @@
// 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.md file.
+// license that can be found in the LICENSE file.
// +build !go1.10
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
index c0b667f58..8646f0529 100644
--- 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
@@ -1,6 +1,6 @@
// 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.md file.
+// license that can be found in the LICENSE file.
// +build go1.10
diff --git a/vendor/github.com/google/go-cmp/cmp/internal/function/func.go b/vendor/github.com/google/go-cmp/cmp/internal/function/func.go
index ace1dbe86..d127d4362 100644
--- a/vendor/github.com/google/go-cmp/cmp/internal/function/func.go
+++ b/vendor/github.com/google/go-cmp/cmp/internal/function/func.go
@@ -1,6 +1,6 @@
// 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.md file.
+// license that can be found in the LICENSE file.
// Package function provides functionality for identifying function types.
package function
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 8228e7d51..b6c12cefb 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
@@ -1,6 +1,6 @@
// Copyright 2020, 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.md file.
+// license that can be found in the LICENSE file.
package value
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 e9e384a1c..44f4a5afd 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
@@ -1,6 +1,6 @@
// Copyright 2018, 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.md file.
+// license that can be found in the LICENSE file.
// +build purego
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 b50c17ec7..a605953d4 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
@@ -1,6 +1,6 @@
// Copyright 2018, 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.md file.
+// license that can be found in the LICENSE file.
// +build !purego
diff --git a/vendor/github.com/google/go-cmp/cmp/internal/value/sort.go b/vendor/github.com/google/go-cmp/cmp/internal/value/sort.go
index 24fbae6e3..98533b036 100644
--- a/vendor/github.com/google/go-cmp/cmp/internal/value/sort.go
+++ b/vendor/github.com/google/go-cmp/cmp/internal/value/sort.go
@@ -1,6 +1,6 @@
// 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.md file.
+// license that can be found in the LICENSE file.
package value
diff --git a/vendor/github.com/google/go-cmp/cmp/internal/value/zero.go b/vendor/github.com/google/go-cmp/cmp/internal/value/zero.go
index 06a8ffd03..9147a2997 100644
--- a/vendor/github.com/google/go-cmp/cmp/internal/value/zero.go
+++ b/vendor/github.com/google/go-cmp/cmp/internal/value/zero.go
@@ -1,6 +1,6 @@
// 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.md file.
+// license that can be found in the LICENSE file.
package value