Recursive output poorly reported

[ajpetersons]

We have a case where we have a linked datastructure pointing to both children and parent nodes. Due to a bug in our test implementation we were getting a result that seems like a false-positive, but in fact cmp hides the actual difference under ref#0. This occurrs because the data structure has the same values, but different pointer addresses. See the simplified example input and output below:

func Test_demo(t *testing.T) {
	type node struct {
		parent *node
		child  *node
	}

	t2 := &node{}
	t1 := &node{child: t2}
	t2.parent = t1

	t3 := &node{child: t2}
	t2.parent = t3

	if diff := cmp.Diff(t1, t3, cmp.AllowUnexported(node{})); diff != "" {
		t.Errorf("node mismatch (-want +got):\n%s", diff)
	}
}

which produces the following output:

    demo_test.go:20: node mismatch (-want +got):
          &⟪ref#0⟫demo.node{
                parent: nil,
                child: &demo.node{
        -               parent: &⟪ref#0: 0x0140004009b0⟫(...),
        +               parent: &⟪ref#0: 0x0140004009b0⟫(...),
                        child:  nil,
                },
          }

The example code is obviously flawed, but in our case that was hidden among 100 other lines before it was distilled to these lines

[dsnet]

Ugh gross. I don't think this is a false positive (i.e., it looks like a true positive, but with bad reporting output).

The graph you have constructed looks as follows:

Note that t2's parent is t3 and not t1 since it is replaced later on. The two nodes being compared are highlighted in yellow.

The graphs starting with t1 or t3 are different:

• From t1's perspective, this is a graph with 3 nodes.
• From t3's perspective there are only 2 nodes). Note that t1 is not visible from t3.

Therefore cmp.Diff should at least report that they are different. However, the reporting is flawed since it reports the starting node as both being ref#0, when they are in fact different.

Perhaps a more correct reporting output would look like:

  &⟪ref#0, ref#1⟫demo.node{
        parent: nil,
        child: &demo.node{
-               parent: &⟪ref#1: 0x0140004009b0⟫(...),
+               parent: &⟪ref#1: 0x0140004009b0⟫(...),
                child:  nil,
        },
  }

This would at least indicate that the ref#1 only refers to the right argument and not the left.

I'm open to suggestions for alternative ways to format this difference in a textual representation. Formatting cyclic graphs as textual lines is hard.

[ajpetersons]

I agree, I don't think this is a false positive - the graph structure differs, as you have illustrated.

It might be worth considering if ref#1 has a place in this line: + parent: &⟪ref#1: 0x0140004009b0⟫(...),. While the value points to the same variable as ref#1, it is a part of different variable (ref#1 was part of the expectation variable)

[dsnet]

It might be worth considering if ref#1 has a place in this line: + parent: &⟪ref#1: 0x0140004009b0⟫(...),. While the value points to the same variable as ref#1, it is a part of different variable (ref#1 was part of the expectation variable)

I'm not sure I follow. Can you provide an example reporter output that you feel would better illustrate what exactly is different? Thanks!

[ajpetersons]

I was thinking something like this:

 &⟪ref#0, ref#1⟫demo.node{
        parent: nil,
        child: &demo.node{
-               parent: &⟪ref#0: 0x0140004009b0⟫(...),
+               parent: &⟪0x0140004009b0⟫(...),
                child:  nil,
        },
  }

The point I'm trying to make with this is that ref#1 references a pointer in a different variable - from t1s perspective ref#1 isn't yet defined at this level, it's defined in the scope of t3.

Now that I think more about this, maybe even this could make sense (maybe extending the difference to top level, so that ref#0 is only defined in the scope of -want lines):

  &⟪ref#0⟫demo.node{
      parent: nil,
-     child: &demo.node{
-         parent: &⟪ref#0: 0x0140004009b0⟫(...),
-         child:  nil,
-     }
+     child: &⟪ref#1⟫demo.node{
+             parent: &demo.node{
+                 parent: nil,
+                 child:  &⟪ref#1: 0x0140004009b0⟫(...),
+             },
+             child:  nil,
+     },
  }

[ysmood]

Here's another approach that might give you some inspiration about how to print it:

package main

import (
	"testing"

	"github.com/ysmood/got/lib/diff"
	"github.com/ysmood/got/lib/gop"
)

func Test(t *testing.T) {
	type node struct {
		parent *node
		child  *node
	}

	t2 := &node{}
	t1 := &node{child: t2}
	t2.parent = t1

	t3 := &node{child: t2}
	t2.parent = t3

	if df := diff.Diff(gop.F(t1), gop.F(t3)); df != "" {
		t.Error(df)
	}
}

• gop: https://github.com/ysmood/got/tree/master/lib/gop
• gop.Circular: https://pkg.go.dev/github.com/ysmood/got@v0.28.0/lib/gop#Circular