proposal: go/types: add Info.ImplicitConversions mapping

[adonovan]

Background: One of the many tricky subtasks of the type checker is to compute the conversions implicitly applied to an expression that is used on the right-hand side of an assignment (or passed as an argument, etc), arithmetic, and shifts. This information is hard to compute and useful to clients. Our refactoring tools have needed this information on several occasions.

For example:

• The golang.org/x/tools/refactor/satisfy package tries to find all conversions to an interface type by reimplementing the logic from the type checker. This is necessary so that the renaming tool can detect when a method renaming would cause a type to no longer implement an interface that is necessary for compilation to succeed.
• The inliner needs to know about implicit conversions in several places. For instance, it needs to know, in a call f(x) to func f(y Y) { g(y) }, whether it is safe to elide the implicit conversion Y(x), and this depends on both the implicit conversion from x to Y and on the implicit conversion from y to g's parameter type. Ascertaining that x and y are both subject to implicit conversions in general requires logic of many cases (duplicating the type checker), and is further complicated by the loss of untyped type information when x is a constant.

Proposal: We add a new field to types.Info to record all implicit conversions.

package types

type Info struct {
    // ImplicitConversions records, for an expression appearing in (say) an assignment
    // context, any implicit conversion applied to it.
    ImplicitConversions map[ast.Expr]ImplicitConversion
}

type ImplicitConversion struct {
    // From records the original type of the expression, and To records the type of the "hole".
    // (For historical reasons [1], 'from' is not necessarily the same as the type recorded
    // Info.Types for the expression: the latter includes untyped-to-typed conversions.)
    From, To types.Type
}

[1] historical reasons

Related:

• go/types: expose interface satisfaction constraints #8970: essentially the same idea, from 10 years ago
• go/types,cmd/compile/internal/types2: extend types.Info with implicit conversions from assignability #47151: the current issue is essentially a dup of "idea 1" in the earlier issue. @mdempsky makes a good point about tuples.

@findleyr @timothy-king @griesemer

[gabyhelp]

Related Issues

• go/types,cmd/compile/internal/types2: extend types.Info with implicit conversions from assignability #47151
• x/tools/internal/refactor/inline: some implicit conversions are undetectable using go/types #63193 (closed)

Related Code Changes

• go/types: factor out usage of implicit type

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

[findleyr]

I think this would simplify quite a bit of reverse-engineering in tools.

Nits:

• from, to should be exported.
• This is not limited to assignment. Untyped conversion can occur in arithmetic expressions, for example, and the type of shift expressions is notoriously complicated.

[griesemer]

Does this primarily apply to expressions of untyped constants? Assignments of values to interfaces? Something else? The proposal should be a bit more specific and perhaps provides some concrete examples.

[adonovan]

Does this primarily apply to expressions of untyped constants?

The satisfy package cares only about concrete-to-interface and interface-to-interface conversions. The inliner cares about all kinds of implicit conversions (untyped-to-typed; unnamed-to-named and vice versa; concrete-to-interface and interface-to-interface; and even channel direction restrictions).

I elaborated the examples a little.

[gopherbot]

Change https://go.dev/cl/632935 mentions this issue: internal/refactor/inline: more precise redundant conversion detection

[gopherbot]

Change https://go.dev/cl/633711 mentions this issue: internal/refactor/inline: more precise redundant conversion detection

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

[findleyr]

Not to bikeshed, but we may also want to include some helper functions on types.Info with this proposal.

Sometimes we want to know the type of an expression, absent its syntactic context. Other times, we want to know the type of the hole the expression fills. Unfortunately the type checker is inconsistent in how it records this information. For example, the type checker updates untyped expression types once their effective type is computed, except for untyped nil.

How about

func (info *Info) InitialTypeOf(ast.Expr) types.Type
func (info *Info) EffectiveTypeOf(ast.Expr) types.Type

(suggestions for better names are welcome). I'd love to just make TypeOf be InitialTypeOf, but I'm afraid that't not a compatible change.

[adonovan]

func (info *Info) InitialTypeOf(ast.Expr) types.Type
func (info *Info) EffectiveTypeOf(ast.Expr) types.Type

Three *TypeOf functions seems like at least two too many. What would the doc comments and implementations of these functions look like?

[findleyr]

Three *TypeOf functions seems like at least two too many

I think it's one too many. If you're reacting to the names, I agree they are not great :)

The implementation(s) would go like this:

// InitialTypeOf returns the type of expr, before any implicit conversions have been applied.
func (info *Info) InitialTypeOf(expr ast.Expr) types.Type {
  if imp, ok := info.ImplicitConversions[expr]; ok {
    return imp.From
  }
  return info.TypeOf(expr)
}

The problem is that TypeOf is ill-defined and inconsistent. I will rescind my bikeshedding though: let's focus on recording the information in go/types.Info, and we can worry about APIs (if any) later.

[adonovan]

OK, that function looks useful. I don't like the name InitialTypeOf because it suggests a temporal dimension that isn't there. ExplicitTypeOf is better because it stands in opposition to ImplicitConversions; however, the type isn't actually explicit in the syntax of expr. I agree it would have been nice to be able to rename TypeOf.

[aclements]

An alternative approach I just wanted to throw out there is exposing the algorithm rather than its conclusions (or maybe both). Are there cases where tools need to "speculatively" ask about implicit conversions in an expression/statement? Or would that require fully type-checking a complete snippet anyway, so it doesn't really help?

[adonovan]

An alternative approach I just wanted to throw out there is exposing the algorithm rather than its conclusions (or maybe both). Are there cases where tools need to "speculatively" ask about implicit conversions in an expression/statement? Or would that require fully type-checking a complete snippet anyway, so it doesn't really help?

The algorithm is really no less than full type checking. One might well want to query ImplicitConversions for a given expression, but the CheckExpr API is too limited to allow that; one would need to create a bogus package p; var _ = EXPR around it.

[aclements]

It sounds like we're going to focus on the new map in types.Info. Maybe we add helper functions later.

type ImplicitConversion struct {
    // From records the original type of the expression, and To records the type of the "hole".
    // (For historical reasons [1], 'from' is not necessarily the same as the type recorded
    // Info.Types for the expression: the latter includes untyped-to-typed conversions.)
    From, To types.Type
}

Given that 2/3rds of the documentation here is a parenthetical explaining a subtle caveat, is this an opportunity to fix that caveat or lift it to a non-parenthetical level? Could we have a third field? E.g., Untyped, From, To types.Type?

[adonovan]

We can certainly lift the doc:

type Info struct {
    // ImplicitConversions records, for an expression appearing in (say) an assignment
    // context, any implicit conversion applied to it.
    //
    // For historical reasons, ImplicitConversions[e].From is not necessarily identical to
    // Types[e].Type for a constant expression e, as the latter may reflect an implicit
    // untyped-to-typed conversion.
    ImplicitConversions map[ast.Expr]ImplicitConversion
}

// An ImplicitConversion records, for an expression appearing in (say) an assignment
// context, an implicit conversion applied to it. See notes at Info.ImplicitConversions.
type ImplicitConversion struct {
    From, To types.Type
}

I'll have a think about adding an Untyped field. FWIW, I think the proposed API provides all the necessary information (in both senses: commentary and computed data).

[aclements]

In proposal review, a question arose about whether "From" is actually necessary since it only differs from Info.Types for untyped constants. If we drop that, the map value will be half the size, but also the map will have far fewer entries. How useful is "From"? Can you infer the untyped type from other information? Should we provide another map for untyped-to-typed conversions?

[adonovan]

After discussion, @griesemer and I agreed that--name bike-shedding aside--the following would be a better interface:

 package types

 type TypeAndValue struct { ... }

 // AssignedTo returns, for a corresponding expression subject to an assignment conversion
 // such as the right side of an assignment lhs = rhs, the type of the variable lhs on the left side.
 // For all other expressions it returns nil.
+ func (TypeAndValue) AssignedTo() Type 

// Untyped reports whether the corresponding expression has an "untyped" constant type.
//
// For unfortunate historical reasons, TypeAndValue.Type reports the [Default] type of
// the corresponding expression when it is the immediate right-hand operand of an assignment.
// For example, given var x any = 1 + 2, the types of 1, 2, and 1+2 are all 'untyped int',
// but TypeAndValue.Type reports 'int' for 1 + 2. The Untyped method returns true for all three.
+ func (TypeAndValue) Untyped() bool

The implementation requires an extra (optional) Type field within TypeAndValue for AssignedTo, plus an additional bit to record Untyped. Fortunately this should not bump TypeAndValue to a larger size class.

AssignedTo is a method, not a field, as we have finally learned our lesson in go/types about painting ourselves into a corner by exposing representation details.

[aclements]

func (TypeAndValue) AssignedTo() Type

Just to be clear that this isn't only for lhs = rhs, give a second example in the docs of something that counts as an "assignment conversion."

func (TypeAndValue) Untyped() bool

I'd suggest that this should return a bool and the untyped Type so the caller doesn't have to then figure that out.

[aclements]

Based on the discussion above, this proposal seems like a likely accept.
— aclements for the proposal review group

The proposal is to add the following to package types:

package types

// AssignedTo returns, for a corresponding expression subject to an assignment conversion
// such as the right side of an assignment lhs = rhs, the type of the variable lhs on the left side.
// For all other expressions it returns nil.
func (TypeAndValue) AssignedTo() Type 

// Untyped returns the "untyped" constant type of this expression, or nil if this expression
// does not have an untyped constant type.
//
// For unfortunate historical reasons, TypeAndValue.Type reports the [Default] type of
// the corresponding expression when it is the immediate right-hand operand of an assignment.
// For example, given var x any = 1 + 2, the types of 1, 2, and 1+2 are all 'untyped int',
// but TypeAndValue.Type reports 'int' for 1 + 2. The Untyped method returns
// [UntypedInt], true for all three.
func (TypeAndValue) Untyped() Type

(The documentation of the Untyped method could definitely use some word-smithing!)