go/types: guarantee sorting of named type methods

[findleyr]

Certain libraries such as x/tools/go/types/objectpath rely on a well-defined sorting of methods on Named types. To enforce this definition, the objectpath package sorts, but as seen in #58668 (comment) that can be quite expensive.

We can fix that particular issue outside of go/types, but it would be nice to commit to a fixed ordering of methods in the go/types API. IIRC the ordering is currently deterministic and in source order (as defined by the input file slice), but this is not documented. We should document and preserve this behavior, or pick a different stable sort.

CC @griesemer @adonovan

[adonovan]

Strictly speaking, all that objectpath needs is that the type checker uses a deterministic ordering of Named.Methods, and that the export/import process preserves that. So either of source order and Id order would be fine, but we should at a minimum commit to determinism (in go/types) and order preservation (in gcexportdata).

[dominikh]

Related: #44195

[griesemer]

Maybe we need both, a "fast" version that doesn't guarantee an ordering, and a "stable" version that guarantees an ordering.

Right now we have sorting, but I don't think we rely on it in the type checker (and maybe we could use a map internally).

[gopherbot]

This issue is currently labeled as early-in-cycle for Go 1.23.
That time is now, so a friendly reminder to look at it again.

[griesemer]

@findleyr Is this still something we'd like to have, and if so, what exactly should we guarantee?

[adonovan]

Yes, I think this is valuable. The obvious order is the lexical order, and that appears to be what's currently implemented:

func Test(t *testing.T) {
	const src = `package p

type T int

func (T) B(){}
func (T) A(){}
`
	dir := t.TempDir()
	cfg := &packages.Config{
		Dir:  dir,
		Mode: packages.LoadSyntax,
		Overlay: map[string][]byte{
			filepath.Join(dir, "p.go"): []byte(src),
		},
	}
	initial, err := packages.Load(cfg, "./p.go")
	if err != nil {
		t.Fatal(err)
	}
	if packages.PrintErrors(initial) > 0 {
		t.Fatal("packages contain errors")
	}
	T := initial[0].Types.Scope().Lookup("T").Type().(*types.Named)
	t.Error(T.Method(0)) // func (command-line-arguments.T).B()
	t.Error(T.Method(1)) // func (command-line-arguments.T).A()
}

[findleyr]

The only objection to lexical ordering, I think, would be that it depends on the ordering of the input file slice. But IIRC last time we discussed this it was pointed out that other things in the go/types API are affected by the ordering of the input slice (such as initialization order), and so it is reasonable that the ordering of methods also depends on input order.

Therefore, I think it would be fine to simply document the current behavior and close this issue. I think we don't even need to commit to lexical ordering: we can just say that the order is deterministic based on the inputs. That is all the objectpath library needs, so I don't see a reason to guarantee more than that.

Perhaps we can simply guarantee determinism in go/types on the whole?

[griesemer]

@findleyr I would think that go/types is deterministic given deterministic (order of) inputs. The only place where non-determinism can come in is via maps, which are a) exported and so we know what we have, or b) if they are internal, we sort before we do any kind of access that might depend on an index order.

That said, I'll keep the documentation local to this issue for now.

[gopherbot]

Change https://go.dev/cl/562347 mentions this issue: go/types, types2: document deterministic method index order and add test