Alternative to reflect.DeepEqual that considers "shape" of cycles?

[Julian Andres Klode]

Is there an existing alternative to reflect.DeepEqual() that also respects the shape of the arguments? For example, the following tests fail:

type List struct {
next *List
}

func TestList(t *testing.T) {
a := &List{}
a.next = a
b := &List{a}
if reflect.DeepEqual(a, b) {
t.Error("Lists are equal")
}
}

Basically, it should also check if cycles occur in the same places (essentially just mapping pointer addresses to a counter and checking if the value (the counter) is the same on both sides when seeing a pointer).

[Jan Mercl]

On Wed, Jul 26, 2017 at 6:37 PM Julian Andres Klode <j...@jak-linux.org> wrote:

> Is there an existing alternative to reflect.DeepEqual() that also respects the shape of the arguments? For example, the following tests fail:

a and b _are_ of equal shape and contain equal values: https://play.golang.org/p/Uam97DXOTy

--

-j

[Julian Andres Klode]

The structs themselves are, yes. But the entire graph is
different (obviously).

A ----- B \
|-/

vs. B \
|-/

Or 2 nodes with 2 edges vs 1 node and 1 edge. There is basically
no practical difference here, but my goal is testing: I have code
that recursively rebuilds some structures (adding more information),
I want to ensure that the resulting graph has the same shape or
structure in my test case, not that they are practically equivalent.

--
Debian Developer - deb.li/jak | jak-linux.org - free software dev
| Ubuntu Core Developer |
When replying, only quote what is necessary, and write each reply
directly below the part(s) it pertains to ('inline'). Thank you.

[howar...@gmail.com]

https://golang.org/pkg/reflect/#DeepEqual

"Pointer values are deeply equal if they are equal using Go's == operator or if they point to deeply equal values."

By the rules described here, the fact that both pointers have the same value means it does not even NEED to check what they point to, so I don't think it ever even sees the cycle.

So yeah, you would have to write your own implementation, or find one.

https://github.com/google/go-cmp is an example of a custom DeepEqual implementation that allows overriding of the comparison basis by implementing an interface (it was designed for equality testing in tests).

From a programmatic perspective, there are two basic ways of comparing two objects for equality - you either walk both objects, returning false the first time you find a mismatch; or you render both objects into a more directly comparable form, and then compare those.

For objects that contain directed or cyclic graphs, going the latter route (which *must* include cycle-breaking to avoid infinite loops) provides the opportunity of applying a 'canonicalization' pass on the intermediate form before the comparison. As an example, if you had two List pointers of the sort you used in your example, that *did* have the same structure, they would be unequal under DeepEqual (if they carried any comparable, non-equal information *aside* from the next pointer), but if canonicalized in a consistent manner that rotated each cycle to have the same starting point in a resulting acyclic graph subsequent to cycle-breaking, could then be compared equal. This requires general graph manipulations, though, and could greatly increase the cost to compare on complicated objects. (After all, it is effectively the same as asking whether two mathematical objects share the same topology, and that is the sort of question that can provide someone a PHD thesis!) But while a *general* solution may be quite expensive, for a specific case where you have control over the objects, it could be as simple as always walking a list until you find the node marked with a head flag before comparing them.

[Julian Andres Klode]

On Thu, Jul 27, 2017 at 09:36:31AM -0700, howar...@gmail.com wrote:
> https://golang.org/pkg/reflect/#DeepEqual
>
> "Pointer values are deeply equal if they are equal using Go's == operator
> or if they point to deeply equal values."
>
> By the rules described here, the fact that both pointers have the same
> value means it does not even NEED to check what they point to, so I don't
> think it ever even sees the cycle.

You are right about that, but that's a vastly simplified example
to show the basic idea of what I'm talking about. In reality, there
are no common components.

>
> So yeah, you would have to write your own implementation, or find one.

It's actually easy to do: You simply number the nodes, or well, the
memory locations being pointed to:

type state struct {
lhsm, rhsm map[interface{}] int
lhsc, rhsc int
}

Algorithm for comparing two pointers.

if lhsm[left side pointer] == 0 {
lhsc++ // First counter is 1.
lhsm[left side pointer] = lhsc
}
... same for right ...
return lhsm[left side ptr] == rhsm[right side ptr]

Obviously you still have to do the recursion.

I guess I should try to write that.