`compareTypes2(t1, t2)` does not always equal `-compareTypes2(t2, t1)`

[jakebailey]

Replace CompareTypes with:

func CompareTypes(t1, t2 *Type) int {
	return -compareTypes2(t2, t1)
}

func compareTypes2(t1, t2 *Type) int {
	if t1 == t2 {
		return 0
	}
	// ...

And then tests say:

✖  internal/testrunner (12.194s)

=== Failed
=== FAIL: internal/testrunner TestSubmodule/dynamicImportsDeclaration.ts/output (0.01s)
    baseline.go:202: the baseline file /home/jabaile/work/TypeScript-go/testdata/baselines/reference/submodule/compiler/dynamicImportsDeclaration.js has changed. (Run `hereby baseline-accept` if the new baseline is correct.)
    baseline.go:202: the baseline file /home/jabaile/work/TypeScript-go/testdata/baselines/reference/submodule/compiler/dynamicImportsDeclaration.js.diff has changed. (Run `hereby baseline-accept` if the new baseline is correct.)

=== FAIL: internal/testrunner TestSubmodule/dynamicImportsDeclaration.ts/type (0.00s)
    baseline.go:202: the baseline file /home/jabaile/work/TypeScript-go/testdata/baselines/reference/submodule/compiler/dynamicImportsDeclaration.types has changed. (Run `hereby baseline-accept` if the new baseline is correct.)
    baseline.go:197: new baseline created at /home/jabaile/work/TypeScript-go/testdata/baselines/local/submodule/compiler/dynamicImportsDeclaration.types.diff.

=== FAIL: internal/testrunner TestSubmodule/dynamicImportsDeclaration.ts (0.01s)

=== FAIL: internal/testrunner TestSubmodule/instantiationExpressions.ts/type (0.01s)
    baseline.go:202: the baseline file /home/jabaile/work/TypeScript-go/testdata/baselines/reference/submodule/conformance/instantiationExpressions.types has changed. (Run `hereby baseline-accept` if the new baseline is correct.)
    baseline.go:202: the baseline file /home/jabaile/work/TypeScript-go/testdata/baselines/reference/submodule/conformance/instantiationExpressions.types.diff has changed. (Run `hereby baseline-accept` if the new baseline is correct.)

=== FAIL: internal/testrunner TestSubmodule/instantiationExpressions.ts (0.17s)

=== FAIL: internal/testrunner TestSubmodule (1.16s)

So, there's something not quite right in the type comparison algorithm.

Noticed this while trying to cache these comparisons in Strada's version of this (doing the common trick of using a canonical ordering for the cache key to halve its size).

[jakebailey]

Seemingly these also break, but in different ways.

This breaks lots of tests across the board with what appears to be a stack overflow.

func (c *Checker) compareNodes(n1, n2 *ast.Node) int {
	return -c.compareNodes(n2, n1)
}

func (c *Checker) compareNodes2(n1, n2 *ast.Node) int {

runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0xc070cec398 stack=[0xc070cec000, 0xc090cec000]
fatal error: stack overflow

runtime stack:
runtime.throw({0x12a6449?, 0x200000008?})
        /usr/local/go/src/runtime/panic.go:1094 +0x48 fp=0xc000a15e98 sp=0xc000a15e68 pc=0x480688
runtime.newstack()
        /usr/local/go/src/runtime/stack.go:1159 +0x5bd fp=0xc000a15fc8 sp=0xc000a15e98 pc=0x46431d
runtime.morestack()
        /usr/local/go/src/runtime/asm_amd64.s:620 +0x7d fp=0xc000a15fd0 sp=0xc000a15fc8 pc=0x48661d

goroutine 1713 gp=0xc0097b2540 m=17 mp=0xc000681008 [running]:
github.com/microsoft/typescript-go/internal/checker.(*Checker).compareNodes(0xc00481c008?, 0xc0047d5688?, 0xc0047d5748?)
        /home/jabaile/work/TypeScript-go/internal/checker/utilities.go:457 +0x2d fp=0xc070cec3a8 sp=0xc070cec3a0 pc=0xf248cd
github.com/microsoft/typescript-go/internal/checker.(*Checker).compareNodes(...)
        /home/jabaile/work/TypeScript-go/internal/checker/utilities.go:458
github.com/microsoft/typescript-go/internal/checker.(*Checker).compareNodes(0x0?, 0x0?, 0x0?)
        /home/jabaile/work/TypeScript-go/internal/checker/utilities.go:458 +0x13 fp=0xc070cec3d0 sp=0xc070cec3a8 pc=0xf248b3
github.com/microsoft/typescript-go/internal/checker.(*Checker).compareNodes(...)
        /home/jabaile/work/TypeScript-go/internal/checker/utilities.go:458

Doing it to symbols appears to reproduce the same bug as comparing types, so that's probably a key factor:

func (c *Checker) compareSymbolsWorker(s1, s2 *ast.Symbol) int {
	return -c.compareSymbolsWorker2(s2, s1)
}

func (c *Checker) compareSymbolsWorker2(s1, s2 *ast.Symbol) int {

I bet this has something to do with how we lazily allocate IDs for things, making the comparison inconsistent depending on the order in which we get there (that would be ironic).

[ahejlsberg]

I bet this has something to do with how we lazily allocate IDs for things...

Yes, we still use lazily allocated IDs as a fallback when nothing else differs. I'll see if we can make the comparisons more specific.

The stack overflow is surprising.

[jakebailey]

I had wanted to make the IDs eager, but I'm not sure how much that would help other than make the problem harder to detect.

[ahejlsberg]

The type ordering logic in Corsa alleviates type/symbol ID ordering dependencies enough that subsequent compilations of the same program with the same number of checkers produces stable results. However, as we discussed, our dependence on lazily assigned symbol IDs is unavoidable in a number of cases, for example because we can't resolve members during type comparisons. This in particular means that instantiations of the same object type will be compared by their type or symbol ID.