Golang x/tools/go/ssa: incomplete type parameter substitution causing panics

Hello!

When x/tools/go/ssa is instantiating generic functions, it seems that the type parameter substitution algorithm does not successfully substitute all instances of the function's parameters when there are other parameterized types involved in an expression. This is easier to explain with two examples.

In this example, the panic occurs while processing the expression B[rune](s) while instantiating S[int].M. The type argument for B is unimportant as it's not used, but the presence of the type parameter prevents the type substitution algorithm from rewriting the underlying type of B[rune] from struct{a T} to struct{a int}, and ssa generation for the conversion subsequently panics.

convert.go
package main

type S[T any] struct {
        a T
}

func (s S[T]) M() {
        type A S[T]
        type B[U any] A
        _ = B[rune](s)
}

func main() {
        S[int]{}.M()
}

$ go install golang.org/x/tools/cmd/ssadump@latest 
$ ssadump -build=G convert.go 
panic: in (command-line-arguments.S[int]).M[int]: cannot convert term *t0 (command-line-arguments.S[int] [within struct{a int}]) to type command-line-arguments.B[rune] [within struct{a T}]
...

In this second example, the panic occurs while processing the method expression i.M while instantiating the function foo[int]. Here golang.org/x/tools/go/ssa.(*subster).typ panics; it seems that it cannot perform chains of substitutions through a parameterized named type to get from I2[int] to I1[int] to interface { M(int) }.

method-expression.go:
package main

type I1[T any] interface {
        M(T)
}

type I2[T any] I1[T]

func foo[T any](i I2[T]) {
        _ = i.M
}

type S[T any] struct{}

func (s S[T]) M(t T) {}

func main() {
        foo[int](I2[int](S[int]{}))
}

$ ssadump -build=G method-expression.go 
panic: type param without replacement encountered
...

Comment From: jcd2

@adonovan @timothy-king

Comment From: cagedmantis

cc @findleyr

Comment From: timothy-king

The first example requires supporting local types with type parameters. This will take some thought.

Related to #58573 and #65152.

Comment From: gopherbot

Change https://go.dev/cl/581835 mentions this issue: go/ssa: fixing Named type substitution