go/types: initialization cycle errors are non-deterministic

[mateusz834]

Type-checking such code:

package p

const (
	B = A + B
	A = A + B
)

leads to non-deterministic errors, either:

initialization_cycle.go:4:2: no error expected: "initialization cycle for B"
initialization_cycle.go:5:2: no error expected: "initialization cycle: A refers to itself"
initialization_cycle.go:4:2: no error expected: "initialization cycle for B"
initialization_cycle.go:5:2: no error expected: "initialization cycle: A refers to itself"

or

initialization_cycle.go:4:2: no error expected: "initialization cycle for B"
initialization_cycle.go:5:2: no error expected: "initialization cycle: A refers to itself"
initialization_cycle.go:4:2: no error expected: "initialization cycle for B"
initialization_cycle.go:5:2: no error expected: "initialization cycle for A"

or

initialization_cycle.go:4:2: no error expected: "initialization cycle for B"
initialization_cycle.go:5:2: no error expected: "initialization cycle: A refers to itself"
initialization_cycle.go:4:2: no error expected: "initialization cycle: B refers to itself"
initialization_cycle.go:5:2: no error expected: "initialization cycle: A refers to itself"

It would be nice if go/types always returned the same error for the same input. I am not sure whether this is something that go/types should guarantee, feel free to close this issue, if that is fine.

CC @adonovan @griesemer

[adonovan]

It would be nice if go/types always returned the same error for the same input. I am not sure whether this is something that go/types should guarantee.

We may not have written it down (and perhaps we should) but, I think all the go/types maintainers agree that it should be deterministic, even if it requires extra logic and computation to (e.g.) iterate over graphs in a particular order. This property is invaluable for debugging and well worth the effort.

[gabyhelp]

Related Issues

• go/types: when reporting cycles, be more faithful to source code (UX improvement) #34771 (closed)
• gccgo: internal compiler error with simple recursive type declaration #25320 (closed)
• cmd/compile: "invalid recursive type" error is not as helpful as go/types #41575 (closed)
• go/types: missing type information in cycle detection #41669
• cmd/compile: failure to reject initialization loop #21752 (closed)

Related Code Changes

• go/types: fix cycle detection
• go/types: fix computation of initialization order

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[findleyr]

I would go so far as to consider this a bug: type checking should be entirely deterministic.

[wingrez]

// findPath returns the (reversed) list of objects []Object{to, ... from}
// such that there is a path of object dependencies from 'from' to 'to'.
// If there is no such path, the result is nil.
func findPath(objMap map[Object]*declInfo, from, to Object, seen map[Object]bool) []Object {
	if seen[from] {
		return nil
	}
	seen[from] = true

	for d := range objMap[from].deps {
		if d == to {
			return []Object{d}
		}
		if P := findPath(objMap, d, to, seen); P != nil {
			return append(P, d)
		}
	}

	return nil
}

The problem is that the objMap[from].deps traversal in findPath is out of order, which leads to different results.
If that's acceptable, I would like to submit a patch.

[griesemer]

@wingrez Feel free to submit a CL for review; I expect this to be a very simple change. Thanks.

[gopherbot]

Change https://go.dev/cl/642396 mentions this issue: types2: ensure that the reportCycle has a deterministic output