Fix pointer cycle detection

[adutra]

The current detection mechanism is very naive and is returning false positives:

func TestCycle(t *testing.T) {
	type node struct {
		Next *node
	}
	c := &node{}
	b := &node{Next: c}
	a1 := &node{Next: b}
	a2 := &node{Next: b}
	coalescer := NewCoalescer(WithErrorOnCycle())
	got, err := coalescer(reflect.ValueOf(a1), reflect.ValueOf(a2))
	require.NoError(t, err)
	assert.Equal(t, a2, got.Interface())
}

The above object graphs have no cycles, and yet an error is being returned. The trick is that b is a node used in both object graphs a1 and a2.

I think we'd need to implement a proper cycle detection algorithm, probably Floyd's "tortoise and hare", or Brent's variant.

[adutra]

In fact the "cycle" detection mechanism simply detects whether a given address has been seen already or not. But an address can appear many times in an object graph without necessarily creating a cycle.

[Miles-Garnsey]

probably Floyd's "tortoise and hare"

This is the "two pointer" solution used to detect a cycle in a linked list isn't it? I was going to ask about that when I saw your original cycle detection approach, but I didn't want to clutter the conversation.

There are probably Go implementations of this that we can cut and paste (the best form of software engineering). I will look into this if you'd like.

[adutra]

This is the "two pointer" solution used to detect a cycle in a linked list isn't it? I was going to ask about that when I saw your original cycle detection approach, but I didn't want to clutter the conversation.

Yes that. Although it's made for linked lists, not for directed graphs.

There are probably Go implementations of this that we can cut and paste (the best form of software engineering). I will look into this if you'd like.

Please go ahead.

A quick search brought this up: https://github.com/joeycumines/go-detect-cycle.

[adutra]

We might actually go the opposite direction and simply acknowledge that the cycle detection feature is not a full-blown one, but just a naive heuristic. It's better than nothing. In this case it would be enough to simply introduce a feature to disable cycle detection completely.

[Miles-Garnsey]

We might actually go the opposite direction and simply acknowledge that the cycle detection feature is not a full-blown one, but just a naive heuristic. It's better than nothing. In this case it would be enough to simply introduce a feature to disable cycle detection completely.

I support this as a short term way to move forward. This flaw will not affect K8s APIs as far as I can tell, because cycles would rarely (never?) appear there. If we ignore cycles, can you implement the DeepCopy logic we need to get the library to always return a newly allocated object?

Please leave this open and I'll do further work as I have time.