Repository: go
Issue: proposal: go/types: define identity of package-level Named types in terms of Package.Path equality
Labels: Proposal

(Status: half-baked food for thought.)

Currently, the types.Identity function applied to two *Named types tests that they point to the same variable. This is the classic symbolic programming approach used in compilers since early Lisp days. However it makes for an inflexible library package interface because it requires that all possible pairs of Named types that might need to be compared for equality belong to the same "realm" of objects, where a realm is essentially the map used by a types.Importer that defines the canonical mapping of package paths to package objects.

Consider an application that wishes to type check hundreds of source packages, in parallel, using export data, and then perform assignability tests on pairs of types from different packages. Each source package has its own importer, and thus its own realm of Named objects, so it is not possible to intermingle objects from these realms correctly. For example, you can't ask whether a concrete type in one realm satisfies an interface type from another realm because, even though they might both possess a method f(*bytes.Buffer), they would not agree that the two Buffer types are the same.

This means that various relations that could easily be well defined over go/types data structures, including `types.Identity`, `types.Assignable`, and `types.MissingMethod`, and `types.LookupFieldOrMethod`, don't work as expected. The application described above must either load all packages of interest in a single realm (entailing redundant work, reduced parallelism, and increased peak memory usage), or find another way to encode the query without using go/types predicates.

Is this restriction essential? I wonder whether we could relax the notion of type identity used by the predicates mentioned above so that they work naturally across realms. Two Named types declared at package level would instead be considered identical iff their names are identical and the Paths of the Packages to which they belong are equal. Pointer identity would just be a fast special case.

Named types local to a function are trickier since there's no obviously ideal way to express the correspondence of the same declaration encountered by the type checker at two different times. Using source positions seems fragile. Perhaps something analogous to [DeBruijn indices](https://en.wikipedia.org/wiki/De_Bruijn_index) could work: a computed name for each local type based on the path up the scope tree to the top-level enclosing function, which of course has an Object.Id that is valid across realms.

Though local types are trickier, they are also less important, as the need to apply predicates (e.g. IsAssignable) to a pair of local types from different packages is rare--though nonetheless conceivably useful in a whole-program analysis.

It's worth noting that if we ignore local types for now, the four predicates above could probably be implemented as described entirely outside go/types, if we were to fork them and edit the object identity comparison.

@griesemer @findleyr @mdempsky @timothy-king @zpavlinovic @dominikh