Add support for comparing graphs (#85)
Previously, trying to call Equal on a graph would result in a stack-overflow
due to infinite recursion traversing cycles on a graph.
While a vast majority of Go values are trees or acyclic graphs, there exist
a small number of cases where graph equality is required.
As such, we add cycle detection to Equal and define what it means for two graphs
to be equal. Contrary to reflect.DeepEqual, which declares two graphs to be
equal so long any cycle were encountered, we require two graphs to have
equivalent graph structures.
Mathematically speaking, a graph G is a tuple (V, E) consisting of the set of
vertices and edges in that graph. Graphs G1 and G2 are equal if V1 == V2,
E1 == E2, and both have the same root vertex (entry point into the graph).
When traversing G1 and G2, we remember a stack of previously visited edges
ES1 and ES2. If the current edge e1 is in ES1 or e2 is in ES2, then we know that
a cycle exists. The graphs have the same structure when the previously
encountered edge ep1 and ep2 were encountered together.
Note that edges and vertices unreachable from the root vertex are ignored.
Appreciation goes to Eyal Posener (@posener), who proposed a different
(but semantically equivalent) approach in #79, which served as inspiration.
Fixes #74
diff --git a/cmp/compare.go b/cmp/compare.go
index 8419fcc..c9a63ce 100644
--- a/cmp/compare.go
+++ b/cmp/compare.go
@@ -80,6 +80,11 @@
// 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 @@
// 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
@@ -155,6 +161,7 @@
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
}
@@ -187,9 +194,9 @@
// 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
@@ -211,9 +218,17 @@
}
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) {
@@ -393,9 +408,21 @@
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
@@ -472,7 +499,12 @@
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.
@@ -509,7 +541,12 @@
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}}})
diff --git a/cmp/compare_test.go b/cmp/compare_test.go
index 5a74e9a..e910bd1 100644
--- a/cmp/compare_test.go
+++ b/cmp/compare_test.go
@@ -52,6 +52,7 @@
tests = append(tests, transformerTests()...)
tests = append(tests, embeddedTests()...)
tests = append(tests, methodTests()...)
+ tests = append(tests, cycleTests()...)
tests = append(tests, project1Tests()...)
tests = append(tests, project2Tests()...)
tests = append(tests, project3Tests()...)
@@ -2234,6 +2235,444 @@
}}
}
+type (
+ CycleAlpha struct {
+ Name string
+ Bravos map[string]*CycleBravo
+ }
+ CycleBravo struct {
+ ID int
+ Name string
+ Mods int
+ Alphas map[string]*CycleAlpha
+ }
+)
+
+func cycleTests() []test {
+ const label = "Cycle"
+
+ type (
+ P *P
+ S []S
+ M map[int]M
+ )
+
+ makeGraph := func() map[string]*CycleAlpha {
+ v := map[string]*CycleAlpha{
+ "Foo": &CycleAlpha{
+ Name: "Foo",
+ Bravos: map[string]*CycleBravo{
+ "FooBravo": &CycleBravo{
+ Name: "FooBravo",
+ ID: 101,
+ Mods: 100,
+ Alphas: map[string]*CycleAlpha{
+ "Foo": nil, // cyclic reference
+ },
+ },
+ },
+ },
+ "Bar": &CycleAlpha{
+ Name: "Bar",
+ Bravos: map[string]*CycleBravo{
+ "BarBuzzBravo": &CycleBravo{
+ Name: "BarBuzzBravo",
+ ID: 102,
+ Mods: 2,
+ Alphas: map[string]*CycleAlpha{
+ "Bar": nil, // cyclic reference
+ "Buzz": nil, // cyclic reference
+ },
+ },
+ "BuzzBarBravo": &CycleBravo{
+ Name: "BuzzBarBravo",
+ ID: 103,
+ Mods: 0,
+ Alphas: map[string]*CycleAlpha{
+ "Bar": nil, // cyclic reference
+ "Buzz": nil, // cyclic reference
+ },
+ },
+ },
+ },
+ "Buzz": &CycleAlpha{
+ Name: "Buzz",
+ Bravos: map[string]*CycleBravo{
+ "BarBuzzBravo": nil, // cyclic reference
+ "BuzzBarBravo": nil, // cyclic reference
+ },
+ },
+ }
+ v["Foo"].Bravos["FooBravo"].Alphas["Foo"] = v["Foo"]
+ v["Bar"].Bravos["BarBuzzBravo"].Alphas["Bar"] = v["Bar"]
+ v["Bar"].Bravos["BarBuzzBravo"].Alphas["Buzz"] = v["Buzz"]
+ v["Bar"].Bravos["BuzzBarBravo"].Alphas["Bar"] = v["Bar"]
+ v["Bar"].Bravos["BuzzBarBravo"].Alphas["Buzz"] = v["Buzz"]
+ v["Buzz"].Bravos["BarBuzzBravo"] = v["Bar"].Bravos["BarBuzzBravo"]
+ v["Buzz"].Bravos["BuzzBarBravo"] = v["Bar"].Bravos["BuzzBarBravo"]
+ return v
+ }
+
+ var tests []test
+ type XY struct{ x, y interface{} }
+ for _, tt := range []struct {
+ in XY
+ wantDiff string
+ reason string
+ }{{
+ in: func() XY {
+ x := new(P)
+ *x = x
+ y := new(P)
+ *y = y
+ return XY{x, y}
+ }(),
+ }, {
+ in: func() XY {
+ x := new(P)
+ *x = x
+ y1, y2 := new(P), new(P)
+ *y1 = y2
+ *y2 = y1
+ return XY{x, y1}
+ }(),
+ wantDiff: `
+ &&cmp_test.P(
+- &⟪0xdeadf00f⟫,
++ &&⟪0xdeadf00f⟫,
+ )
+`,
+ }, {
+ in: func() XY {
+ x := S{nil}
+ x[0] = x
+ y := S{nil}
+ y[0] = y
+ return XY{x, y}
+ }(),
+ }, {
+ in: func() XY {
+ x := S{nil}
+ x[0] = x
+ y1, y2 := S{nil}, S{nil}
+ y1[0] = y2
+ y2[0] = y1
+ return XY{x, y1}
+ }(),
+ wantDiff: `
+ cmp_test.S{
+- {{{*(*cmp_test.S)(⟪0xdeadf00f⟫)}}},
++ {{{{*(*cmp_test.S)(⟪0xdeadf00f⟫)}}}},
+ }
+`,
+ }, {
+ in: func() XY {
+ x := M{0: nil}
+ x[0] = x
+ y := M{0: nil}
+ y[0] = y
+ return XY{x, y}
+ }(),
+ }, {
+ in: func() XY {
+ x := M{0: nil}
+ x[0] = x
+ y1, y2 := M{0: nil}, M{0: nil}
+ y1[0] = y2
+ y2[0] = y1
+ return XY{x, y1}
+ }(),
+ wantDiff: `
+ cmp_test.M{
+- 0: {0: ⟪0xdeadf00f⟫},
++ 0: {0: {0: ⟪0xdeadf00f⟫}},
+ }
+`,
+ }, {
+ in: XY{makeGraph(), makeGraph()},
+ }, {
+ in: func() XY {
+ x := makeGraph()
+ y := makeGraph()
+ y["Foo"].Bravos["FooBravo"].ID = 0
+ y["Bar"].Bravos["BarBuzzBravo"].ID = 0
+ y["Bar"].Bravos["BuzzBarBravo"].ID = 0
+ return XY{x, y}
+ }(),
+ wantDiff: `
+ map[string]*cmp_test.CycleAlpha{
+ "Bar": &{
+ Name: "Bar",
+ Bravos: map[string]*cmp_test.CycleBravo{
+ "BarBuzzBravo": &{
+- ID: 102,
++ ID: 0,
+ Name: "BarBuzzBravo",
+ Mods: 2,
+ Alphas: map[string]*cmp_test.CycleAlpha{
+ "Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}},
+ "Buzz": &{
+ Name: "Buzz",
+ Bravos: map[string]*cmp_test.CycleBravo{
+ "BarBuzzBravo": &{Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": ⟪0xdeadf00f⟫}}}}}}, "Buzz": ⟪0xdeadf00f⟫}},
+ "BuzzBarBravo": &{
+- ID: 103,
++ ID: 0,
+ Name: "BuzzBarBravo",
+ Mods: 0,
+ Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}}, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}, "Buzz": ⟪0xdeadf00f⟫}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}}},
+ },
+ },
+ },
+ },
+ },
+ "BuzzBarBravo": &{
+- ID: 103,
++ ID: 0,
+ Name: "BuzzBarBravo",
+ Mods: 0,
+ Alphas: map[string]*cmp_test.CycleAlpha{
+ "Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}},
+ "Buzz": &{
+ Name: "Buzz",
+ Bravos: map[string]*cmp_test.CycleBravo{
+ "BarBuzzBravo": &{
+- ID: 102,
++ ID: 0,
+ Name: "BarBuzzBravo",
+ Mods: 2,
+ Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}}, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}, "Buzz": ⟪0xdeadf00f⟫}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}}},
+ },
+ "BuzzBarBravo": &{Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": ⟪0xdeadf00f⟫}}}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}}, "Buzz": ⟪0xdeadf00f⟫}},
+ },
+ },
+ },
+ },
+ },
+ },
+ "Buzz": &{
+ Name: "Buzz",
+ Bravos: map[string]*cmp_test.CycleBravo{
+ "BarBuzzBravo": &{
+- ID: 102,
++ ID: 0,
+ Name: "BarBuzzBravo",
+ Mods: 2,
+ Alphas: map[string]*cmp_test.CycleAlpha{
+ "Bar": &{
+ Name: "Bar",
+ Bravos: map[string]*cmp_test.CycleBravo{
+ "BarBuzzBravo": &{Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": ⟪0xdeadf00f⟫}}}}}}, "Buzz": ⟪0xdeadf00f⟫}},
+ "BuzzBarBravo": &{
+- ID: 103,
++ ID: 0,
+ Name: "BuzzBarBravo",
+ Mods: 0,
+ Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}}, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}, "Buzz": ⟪0xdeadf00f⟫}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}}},
+ },
+ },
+ },
+ "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}, "Buzz": ⟪0xdeadf00f⟫}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}},
+ },
+ },
+ "BuzzBarBravo": &{
+- ID: 103,
++ ID: 0,
+ Name: "BuzzBarBravo",
+ Mods: 0,
+ Alphas: map[string]*cmp_test.CycleAlpha{
+ "Bar": &{
+ Name: "Bar",
+ Bravos: map[string]*cmp_test.CycleBravo{
+ "BarBuzzBravo": &{
+- ID: 102,
++ ID: 0,
+ Name: "BarBuzzBravo",
+ Mods: 2,
+ Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}}, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}, "Buzz": ⟪0xdeadf00f⟫}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}}},
+ },
+ "BuzzBarBravo": &{Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": ⟪0xdeadf00f⟫}}}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}}, "Buzz": ⟪0xdeadf00f⟫}},
+ },
+ },
+ "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}, "Buzz": ⟪0xdeadf00f⟫}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}},
+ },
+ },
+ },
+ },
+ "Foo": &{
+ Name: "Foo",
+ Bravos: map[string]*cmp_test.CycleBravo{
+ "FooBravo": &{
+- ID: 101,
++ ID: 0,
+ Name: "FooBravo",
+ Mods: 100,
+ Alphas: map[string]*cmp_test.CycleAlpha{"Foo": &{Name: "Foo", Bravos: map[string]*cmp_test.CycleBravo{"FooBravo": &{Name: "FooBravo", Mods: 100, Alphas: map[string]*cmp_test.CycleAlpha{"Foo": ⟪0xdeadf00f⟫}}}}},
+ },
+ },
+ },
+ }
+`,
+ }, {
+ in: func() XY {
+ x := makeGraph()
+ y := makeGraph()
+ x["Buzz"].Bravos["BuzzBarBravo"] = &CycleBravo{
+ Name: "BuzzBarBravo",
+ ID: 103,
+ }
+ return XY{x, y}
+ }(),
+ wantDiff: `
+ map[string]*cmp_test.CycleAlpha{
+ "Bar": &{
+ Name: "Bar",
+ Bravos: map[string]*cmp_test.CycleBravo{
+ "BarBuzzBravo": &{
+ ID: 102,
+ Name: "BarBuzzBravo",
+ Mods: 2,
+ Alphas: map[string]*cmp_test.CycleAlpha{
+ "Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{ID: 102, Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{ID: 103, Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}},
+ "Buzz": &{
+ Name: "Buzz",
+ Bravos: map[string]*cmp_test.CycleBravo{
+ "BarBuzzBravo": &{ID: 102, Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{ID: 103, Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": ⟪0xdeadf00f⟫}}}}}}, "Buzz": ⟪0xdeadf00f⟫}},
+ "BuzzBarBravo": &{
+ ID: 103,
+ Name: "BuzzBarBravo",
+ Mods: 0,
+- Alphas: nil,
++ Alphas: map[string]*cmp_test.CycleAlpha{
++ "Bar": &{
++ Name: "Bar",
++ Bravos: map[string]*cmp_test.CycleBravo{
++ "BarBuzzBravo": &{
++ ID: 102,
++ Name: "BarBuzzBravo",
++ Mods: 2,
++ Alphas: map[string]*cmp_test.CycleAlpha{
++ "Bar": ⟪0xdeadf00f⟫,
++ "Buzz": &{
++ Name: "Buzz",
++ Bravos: map[string]*cmp_test.CycleBravo{
++ "BarBuzzBravo": ⟪0xdeadf00f⟫,
++ "BuzzBarBravo": &{
++ ID: 103,
++ Name: "BuzzBarBravo",
++ Alphas: map[string]*cmp_test.CycleAlpha(⟪0xdeadf00f⟫),
++ },
++ },
++ },
++ },
++ },
++ "BuzzBarBravo": ⟪0xdeadf00f⟫,
++ },
++ },
++ "Buzz": ⟪0xdeadf00f⟫,
++ },
+ },
+ },
+ },
+ },
+ },
+ "BuzzBarBravo": &{
+ ID: 103,
+ Name: "BuzzBarBravo",
+ Mods: 0,
+ Alphas: map[string]*cmp_test.CycleAlpha{
+ "Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{ID: 102, Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{ID: 103, Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}},
+ "Buzz": &{
+ Name: "Buzz",
+ Bravos: map[string]*cmp_test.CycleBravo{
+ "BarBuzzBravo": &{ID: 102, Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{ID: 102, Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{ID: 103, Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}}, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{ID: 102, Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{ID: 103, Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}, "Buzz": ⟪0xdeadf00f⟫}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}}}},
+- "BuzzBarBravo": &{ID: 103, Name: "BuzzBarBravo"},
++ "BuzzBarBravo": &{
++ ID: 103,
++ Name: "BuzzBarBravo",
++ Alphas: map[string]*cmp_test.CycleAlpha{
++ "Bar": &{
++ Name: "Bar",
++ Bravos: map[string]*cmp_test.CycleBravo{
++ "BarBuzzBravo": &{
++ ID: 102,
++ Name: "BarBuzzBravo",
++ Mods: 2,
++ Alphas: map[string]*cmp_test.CycleAlpha{
++ "Bar": ⟪0xdeadf00f⟫,
++ "Buzz": &{
++ Name: "Buzz",
++ Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": ⟪0xdeadf00f⟫},
++ },
++ },
++ },
++ "BuzzBarBravo": ⟪0xdeadf00f⟫,
++ },
++ },
++ "Buzz": ⟪0xdeadf00f⟫,
++ },
++ },
+ },
+ },
+ },
+ },
+ },
+ },
+ "Buzz": &{
+ Name: "Buzz",
+ Bravos: map[string]*cmp_test.CycleBravo{
+ "BarBuzzBravo": &{ID: 102, Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{ID: 102, Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{ID: 103, Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": ⟪0xdeadf00f⟫}}}}}}, "Buzz": ⟪0xdeadf00f⟫}}, "BuzzBarBravo": &{ID: 103, Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{ID: 102, Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{ID: 103, Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}}, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{ID: 102, Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{ID: 103, Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}, "Buzz": ⟪0xdeadf00f⟫}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}}}}}}, "Buzz": &{Name: "Buzz", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": &{ID: 102, Name: "BarBuzzBravo", Mods: 2, Alphas: map[string]*cmp_test.CycleAlpha{"Bar": &{Name: "Bar", Bravos: map[string]*cmp_test.CycleBravo{"BarBuzzBravo": ⟪0xdeadf00f⟫, "BuzzBarBravo": &{ID: 103, Name: "BuzzBarBravo", Alphas: map[string]*cmp_test.CycleAlpha{"Bar": ⟪0xdeadf00f⟫, "Buzz": ⟪0xdeadf00f⟫}}}}, "Buzz": ⟪0xdeadf00f⟫}}, "BuzzBarBravo": ⟪0xdeadf00f⟫}}}},
+ "BuzzBarBravo": &{
+ ID: 103,
+ Name: "BuzzBarBravo",
+ Mods: 0,
+- Alphas: nil,
++ Alphas: map[string]*cmp_test.CycleAlpha{
++ "Bar": &{
++ Name: "Bar",
++ Bravos: map[string]*cmp_test.CycleBravo{
++ "BarBuzzBravo": &{
++ ID: 102,
++ Name: "BarBuzzBravo",
++ Mods: 2,
++ Alphas: map[string]*cmp_test.CycleAlpha{
++ "Bar": ⟪0xdeadf00f⟫,
++ "Buzz": &{
++ Name: "Buzz",
++ Bravos: map[string]*cmp_test.CycleBravo{
++ "BarBuzzBravo": ⟪0xdeadf00f⟫,
++ "BuzzBarBravo": &{
++ ID: 103,
++ Name: "BuzzBarBravo",
++ Alphas: map[string]*cmp_test.CycleAlpha(⟪0xdeadf00f⟫),
++ },
++ },
++ },
++ },
++ },
++ "BuzzBarBravo": ⟪0xdeadf00f⟫,
++ },
++ },
++ "Buzz": ⟪0xdeadf00f⟫,
++ },
+ },
+ },
+ },
+ "Foo": &{Name: "Foo", Bravos: map[string]*cmp_test.CycleBravo{"FooBravo": &{ID: 101, Name: "FooBravo", Mods: 100, Alphas: map[string]*cmp_test.CycleAlpha{"Foo": &{Name: "Foo", Bravos: map[string]*cmp_test.CycleBravo{"FooBravo": &{ID: 101, Name: "FooBravo", Mods: 100, Alphas: map[string]*cmp_test.CycleAlpha{"Foo": ⟪0xdeadf00f⟫}}}}}}}},
+ }
+`,
+ }} {
+ tests = append(tests, test{
+ label: label,
+ x: tt.in.x,
+ y: tt.in.y,
+ wantDiff: tt.wantDiff,
+ reason: tt.reason,
+ })
+ }
+ return tests
+}
+
func project1Tests() []test {
const label = "Project1"
diff --git a/cmp/options.go b/cmp/options.go
index 409e803..abbd2a6 100644
--- a/cmp/options.go
+++ b/cmp/options.go
@@ -455,6 +455,11 @@
return r.flags&reportByFunc != 0
}
+// ByCycle reports whether a reference cycle was detected.
+func (r Result) ByCycle() bool {
+ return r.flags&reportByCycle != 0
+}
+
type resultFlags uint
const (
@@ -465,6 +470,7 @@
reportByIgnore
reportByMethod
reportByFunc
+ reportByCycle
)
// Reporter is an Option that can be passed to Equal. When Equal traverses
diff --git a/cmp/path.go b/cmp/path.go
index d7a420d..509d6b8 100644
--- a/cmp/path.go
+++ b/cmp/path.go
@@ -10,6 +10,8 @@
"strings"
"unicode"
"unicode/utf8"
+
+ "github.com/google/go-cmp/cmp/internal/value"
)
// Path is a list of PathSteps describing the sequence of operations to get
@@ -207,6 +209,7 @@
type sliceIndex struct {
pathStep
xkey, ykey int
+ isSlice bool // False for reflect.Array
}
func (si SliceIndex) Type() reflect.Type { return si.typ }
@@ -301,6 +304,72 @@
// The == operator can be used to detect the exact option used.
func (tf Transform) Option() Option { return tf.trans }
+// pointerPath represents a dual-stack of pointers encountered when
+// recursively traversing the x and y values. This data structure supports
+// detection of cycles and determining whether the cycles are equal.
+// In Go, cycles can occur via pointers, slices, and maps.
+//
+// The pointerPath uses a map to represent a stack; where descension into a
+// pointer pushes the address onto the stack, and ascension from a pointer
+// 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.
+//
+// If a cycle is detected we need to determine whether the two pointers
+// should be considered equal. The definition of equality chosen by Equal
+// requires two graphs to have the same structure. To determine this, both the
+// x and y values must have a cycle where the previous pointers were also
+// encountered together as a pair.
+//
+// Semantically, this is equivalent to augmenting Indirect, SliceIndex, and
+// MapIndex with pointer information for the x and y values.
+// Suppose px and py are two pointers to compare, we then search the
+// Path for whether px was ever encountered in the Path history of x, and
+// similarly so with py. If either side has a cycle, the comparison is only
+// equal if both px and py have a cycle resulting from the same PathStep.
+//
+// Using a map as a stack is more performant as we can perform cycle detection
+// in O(1) instead of O(N) where N is len(Path).
+type pointerPath struct {
+ // mx is keyed by x pointers, where the value is the associated y pointer.
+ mx map[value.Pointer]value.Pointer
+ // my is keyed by y pointers, where the value is the associated x pointer.
+ my map[value.Pointer]value.Pointer
+}
+
+func (p *pointerPath) Init() {
+ p.mx = make(map[value.Pointer]value.Pointer)
+ p.my = make(map[value.Pointer]value.Pointer)
+}
+
+// Push indicates intent to descend into pointers vx and vy where
+// visited reports whether either has been seen before. If visited before,
+// equal reports whether both pointers were encountered together.
+// Pop must be called if and only if the pointers were never visited.
+//
+// The pointers vx and vy must be a reflect.Ptr, reflect.Slice, or reflect.Map
+// and be non-nil.
+func (p pointerPath) Push(vx, vy reflect.Value) (equal, visited bool) {
+ px := value.PointerOf(vx)
+ py := value.PointerOf(vy)
+ _, ok1 := p.mx[px]
+ _, ok2 := p.my[py]
+ if ok1 || ok2 {
+ equal = p.mx[px] == py && p.my[py] == px // Pointers paired together
+ return equal, true
+ }
+ p.mx[px] = py
+ p.my[py] = px
+ return false, false
+}
+
+// Pop ascends from pointers vx and vy.
+func (p pointerPath) Pop(vx, vy reflect.Value) {
+ delete(p.mx, value.PointerOf(vx))
+ delete(p.my, value.PointerOf(vy))
+}
+
// isExported reports whether the identifier is exported.
func isExported(id string) bool {
r, _ := utf8.DecodeRuneInString(id)
