x/tools/internal/refactor/inline: replacing a variable by a constant may cause type error

[adonovan]

The inliner replaces parameters by their arguments when possible. If the argument is a constant, then certain expressions that were statically valid (but would panic if evaluated) before are now statically invalid. For example, attempting to slice an empty string:

func _() {
    const s = ""
    f(s)
}
func (s string) { _ = s[:1] } // error: cannot slice empty string

or negating minint:

func _() {
    const x = -0x80000000
    f(x)
}
func f(x int32) { var _ int32 = -x } // error: - -0x80000000 overflows int32

In general I suspect such errors cannot be detected without executing the type checker on the result, which is not something that can be done by the inliner itself. Sigh.

@findleyr @timothy-king

[adonovan]

... which is not something that can be done by the inliner itself.

but it could be if we had an API something like types.CheckNodeInEnv(ast.Node, env map[string]Object, *Info) []error that would type-check a declaration, statement, or expression within the provided environment, optionally populate the Info, and return any errors. (The environment could alternatively be provided in the form of a *Scope.)

The inliner would create an environment mapping containing all the context surrounding the modified call (imports, all package-level decls, and even local variables) then call this function.

Obviously there are limits on what the type-checker can do with a piece of a package: given a method decl, for example, it can't very well add methods to an existing named type, but it might still be able to record the correct types for self-recursive method calls. Seems like a useful thing to prototype. @griesemer @mdempsky

[adonovan]

Unfortunately CheckNodeInEnv cannot be implemented using the current go/types API. You can get close, for example by walking up the scope tree, gathering objects, inserting them all into a "flat" Package Scope and calling types.CheckExpr. You have to wrap decls in statements and statements in function literals (with the correct results tuple) to make them into expressions. Free control constructs are tricky, so statements must be wrapped in something like { goto label; label: for { S } } so that forward and backward gotos and labelled and unlabelled break and continue all work and no label is unreferenced.

But there are irreducible problems: CheckExpr asserts (in Checker.selector) that PkgName objects in the Package Scope belong to that package, so you have to use the original Package; but we need to populate this Package Scope (see above) with the computed "flat" environment, as it's the only way to pass the environment to CheckExpr. So it's a destructive operation on a Package. I think go/types should expose a cleaner separation of concepts for "piecemeal" type checking.

All that said, there's a more fundamental obstacle for our inliner. In general, when inlining a call in package 'a' to a method b.B, all we have is the summary of b.B, not a complete types.Package. So if b imports c, and inlining would cause 'a' to import c, we have no way to construct a functioning types.PkgName for the new import that we can insert in the environment for CheckExpr.

One solution would be to somehow allow the summary of b.B to describe everything it depends on about package c: in other words, to serialize a symbol or type (or a handful of them) as deep export data. (This would require new APIs for "slices" of export data.) The code that calls CheckExpr could rehydrate this information into a types.Package containing just the necessary symbols. Of course deep export data doesn't scale very well, but perhaps it's acceptable.

Another approach is to reimplement all the type-checker logic for deciding when a constant value is illegal in a context where a var of the same type would be legal, to serialize these constraints in the callee summary, and disallow parameter elimination in those cases. That sounds like a lot of work.

[timothy-king]

I have not looked into this, but how far could we get by making the translation from f(x) to be as if it was f(int32(x)), and then at each substitution location we could try to check whether int32(x) can be safely replaced by x? This would only be needed if x has undergone an implicit assignment that changes its type. IIRC this can be determined from go/types. I think we can always 'give up' and apply this approach for constants. [Not very confident though.]

Another possible translation is to try to make the argument a variable via an explicit assignment:

  const x = -0x80000000
  var arg int32 = x
  var _ int32 = -arg 

This could be employed when there is an implicit type change when applying the function argument. An obvious disadvantage is that this is even further from the user's code.

[adonovan]

int32(x) doesn't remove the const-ness of x, so it is still subject to compile-time checks such as negation of minint32.

I think the solution is to enumerate the set of all constant-fallible operations:

//    - switch z { case x: case y } 	// duplicate cases
//    - s[i], s[i:j], s[i:j:k]		// index out of bounds (0 <= i <= j <= k <= len(s))
//    - T{x: 0}				// array/slice index out of bounds
//    - x/y, x%y			// integer division by zero
//    - x<<y				// shift out of range
//    - -x				// negation of minint

and then find out which parameters are used as inputs to these operations, possibly nested in constant-propagatable subexpressions, and then disable parameter substitution of these parameters when their arguments are constant. (The inliner will then resort to the use of a parameter binding var decl, which is non-constant.)

[timothy-king]

Good point. Playground examples showing that the int32(x) substitution does not work: https://go.dev/play/p/06qkn-ZlPqh.

[gopherbot]

Change https://go.dev/cl/531456 mentions this issue: internal/refactor/inline: tweak everything test for cgo

[gopherbot]

Change https://go.dev/cl/531695 mentions this issue: internal/refactor/inline: fallible constant analysis