Re: [go-nuts] Alternative to reflect.DeepEqual that considers "shape" of cycles?

[Julian Andres Klode]

On Thu, Jul 27, 2017 at 09:36:31AM -0700, howardcs...@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.
-- 
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.

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [go-nuts] Alternative to reflect.DeepEqual that considers "shape" of cycles?

[howardcshaw]

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.

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [go-nuts] Alternative to reflect.DeepEqual that considers "shape" of cycles?

[Julian Andres Klode]

On Wed, Jul 26, 2017 at 04:55:39PM +, Jan Mercl wrote:
> On Wed, Jul 26, 2017 at 6:37 PM Julian Andres Klode 
> 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

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.

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [go-nuts] Alternative to reflect.DeepEqual that considers "shape" of cycles?

[Jan Mercl]

On Wed, Jul 26, 2017 at 6:37 PM Julian Andres Klode 
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

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.