go.mod: switch to modules for dependency management

Godep is long deprecated and modules is the future.
Updating dependencies with godep is painful and non-transparent.
This will hopefully help to create custom golangci-lint linters.
The change was created with:

go mod init
rm -rf vendor
go mod vendor

Fixes #1247

1 files changed, 61 insertions, 22 deletions

diff --git a/vendor/github.com/google/go-cmp/cmp/compare.go b/vendor/github.com/google/go-cmp/cmp/compare.go
index 2133562b0..c9a63ceda 100644
--- a/vendor/github.com/google/go-cmp/cmp/compare.go
+++ b/vendor/github.com/google/go-cmp/cmp/compare.go
@@ -22,8 +22,8 @@
 // equality is determined by recursively comparing the primitive kinds on both
 // values, much like reflect.DeepEqual. Unlike reflect.DeepEqual, unexported
 // fields are not compared by default; they result in panics unless suppressed
-// by using an Ignore option (see cmpopts.IgnoreUnexported) or explicitly compared
-// using the AllowUnexported option.
+// by using an Ignore option (see cmpopts.IgnoreUnexported) or explicitly
+// compared using the Exporter option.
 package cmp
 
 import (
@@ -62,8 +62,8 @@ import (
 //
 // Structs are equal if recursively calling Equal on all fields report equal.
 // If a struct contains unexported fields, Equal panics unless an Ignore option
-// (e.g., cmpopts.IgnoreUnexported) ignores that field or the AllowUnexported
-// option explicitly permits comparing the unexported field.
+// (e.g., cmpopts.IgnoreUnexported) ignores that field or the Exporter option
+// explicitly permits comparing the unexported field.
 //
 // Slices are equal if they are both nil or both non-nil, where recursively
 // calling Equal on all non-ignored slice or array elements report equal.
@@ -80,6 +80,11 @@ import (
 // Pointers and interfaces are equal if they are both nil or both non-nil,
 // where they have the same underlying concrete type and recursively
 // calling Equal on the underlying values reports equal.
+//
+// Before recursing into a pointer, slice element, or map, the current path
+// is checked to detect whether the address has already been visited.
+// If there is a cycle, then the pointed at values are considered equal
+// only if both addresses were previously visited in the same path step.
 func Equal(x, y interface{}, opts ...Option) bool {
 	vx := reflect.ValueOf(x)
 	vy := reflect.ValueOf(y)
@@ -137,6 +142,7 @@ type state struct {
 	// Calling statelessCompare must not result in observable changes to these.
 	result    diff.Result // The current result of comparison
 	curPath   Path        // The current path in the value tree
+	curPtrs   pointerPath // The current set of visited pointers
 	reporters []reporter  // Optional reporters
 
 	// recChecker checks for infinite cycles applying the same set of
@@ -148,13 +154,14 @@ type state struct {
 	dynChecker dynChecker
 
 	// These fields, once set by processOption, will not change.
-	exporters map[reflect.Type]bool // Set of structs with unexported field visibility
-	opts      Options               // List of all fundamental and filter options
+	exporters []exporter // List of exporters for structs with unexported fields
+	opts      Options    // List of all fundamental and filter options
 }
 
 func newState(opts []Option) *state {
 	// Always ensure a validator option exists to validate the inputs.
 	s := &state{opts: Options{validator{}}}
+	s.curPtrs.Init()
 	s.processOption(Options(opts))
 	return s
 }
@@ -174,13 +181,8 @@ func (s *state) processOption(opt Option) {
 			panic(fmt.Sprintf("cannot use an unfiltered option: %v", opt))
 		}
 		s.opts = append(s.opts, opt)
-	case visibleStructs:
-		if s.exporters == nil {
-			s.exporters = make(map[reflect.Type]bool)
-		}
-		for t := range opt {
-			s.exporters[t] = true
-		}
+	case exporter:
+		s.exporters = append(s.exporters, opt)
 	case reporter:
 		s.reporters = append(s.reporters, opt)
 	default:
@@ -192,9 +194,9 @@ func (s *state) processOption(opt Option) {
 // This function is stateless in that it does not alter the current result,
 // or output to any registered reporters.
 func (s *state) statelessCompare(step PathStep) diff.Result {
-	// We do not save and restore the curPath because all of the compareX
-	// methods should properly push and pop from the path.
-	// It is an implementation bug if the contents of curPath differs from
+	// We do not save and restore curPath and curPtrs because all of the
+	// compareX methods should properly push and pop from them.
+	// It is an implementation bug if the contents of the paths differ from
 	// when calling this function to when returning from it.
 
 	oldResult, oldReporters := s.result, s.reporters
@@ -216,9 +218,17 @@ func (s *state) compareAny(step PathStep) {
 	}
 	s.recChecker.Check(s.curPath)
 
-	// Obtain the current type and values.
+	// Cycle-detection for slice elements (see NOTE in compareSlice).
 	t := step.Type()
 	vx, vy := step.Values()
+	if si, ok := step.(SliceIndex); ok && si.isSlice && vx.IsValid() && vy.IsValid() {
+		px, py := vx.Addr(), vy.Addr()
+		if eq, visited := s.curPtrs.Push(px, py); visited {
+			s.report(eq, reportByCycle)
+			return
+		}
+		defer s.curPtrs.Pop(px, py)
+	}
 
 	// Rule 1: Check whether an option applies on this node in the value tree.
 	if s.tryOptions(t, vx, vy) {
@@ -354,6 +364,7 @@ func sanitizeValue(v reflect.Value, t reflect.Type) reflect.Value {
 func (s *state) compareStruct(t reflect.Type, vx, vy reflect.Value) {
 	var vax, vay reflect.Value // Addressable versions of vx and vy
 
+	var mayForce, mayForceInit bool
 	step := StructField{&structField{}}
 	for i := 0; i < t.NumField(); i++ {
 		step.typ = t.Field(i).Type
@@ -375,7 +386,13 @@ func (s *state) compareStruct(t reflect.Type, vx, vy reflect.Value) {
 				vax = makeAddressable(vx)
 				vay = makeAddressable(vy)
 			}
-			step.mayForce = s.exporters[t]
+			if !mayForceInit {
+				for _, xf := range s.exporters {
+					mayForce = mayForce || xf(t)
+				}
+				mayForceInit = true
+			}
+			step.mayForce = mayForce
 			step.pvx = vax
 			step.pvy = vay
 			step.field = t.Field(i)
@@ -391,9 +408,21 @@ func (s *state) compareSlice(t reflect.Type, vx, vy reflect.Value) {
 		return
 	}
 
-	// TODO: Support cyclic data structures.
+	// NOTE: It is incorrect to call curPtrs.Push on the slice header pointer
+	// since slices represents a list of pointers, rather than a single pointer.
+	// The pointer checking logic must be handled on a per-element basis
+	// in compareAny.
+	//
+	// A slice header (see reflect.SliceHeader) in Go is a tuple of a starting
+	// pointer P, a length N, and a capacity C. Supposing each slice element has
+	// a memory size of M, then the slice is equivalent to the list of pointers:
+	//	[P+i*M for i in range(N)]
+	//
+	// For example, v[:0] and v[:1] are slices with the same starting pointer,
+	// but they are clearly different values. Using the slice pointer alone
+	// violates the assumption that equal pointers implies equal values.
 
-	step := SliceIndex{&sliceIndex{pathStep: pathStep{typ: t.Elem()}}}
+	step := SliceIndex{&sliceIndex{pathStep: pathStep{typ: t.Elem()}, isSlice: isSlice}}
 	withIndexes := func(ix, iy int) SliceIndex {
 		if ix >= 0 {
 			step.vx, step.xkey = vx.Index(ix), ix
@@ -470,7 +499,12 @@ func (s *state) compareMap(t reflect.Type, vx, vy reflect.Value) {
 		return
 	}
 
-	// TODO: Support cyclic data structures.
+	// Cycle-detection for maps.
+	if eq, visited := s.curPtrs.Push(vx, vy); visited {
+		s.report(eq, reportByCycle)
+		return
+	}
+	defer s.curPtrs.Pop(vx, vy)
 
 	// We combine and sort the two map keys so that we can perform the
 	// comparisons in a deterministic order.
@@ -507,7 +541,12 @@ func (s *state) comparePtr(t reflect.Type, vx, vy reflect.Value) {
 		return
 	}
 
-	// TODO: Support cyclic data structures.
+	// Cycle-detection for pointers.
+	if eq, visited := s.curPtrs.Push(vx, vy); visited {
+		s.report(eq, reportByCycle)
+		return
+	}
+	defer s.curPtrs.Pop(vx, vy)
 
 	vx, vy = vx.Elem(), vy.Elem()
 	s.compareAny(Indirect{&indirect{pathStep{t.Elem(), vx, vy}}})