1 // Copyright 2021 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 // Package typeparams contains common utilities for writing tools that interact 6 // with generic Go code, as introduced with Go 1.18. 7 // 8 // Many of the types and functions in this package are proxies for the new APIs 9 // introduced in the standard library with Go 1.18. For example, the 10 // typeparams.Union type is an alias for go/types.Union, and the ForTypeSpec 11 // function returns the value of the go/ast.TypeSpec.TypeParams field. At Go 12 // versions older than 1.18 these helpers are implemented as stubs, allowing 13 // users of this package to write code that handles generic constructs inline, 14 // even if the Go version being used to compile does not support generics. 15 // 16 // Additionally, this package contains common utilities for working with the 17 // new generic constructs, to supplement the standard library APIs. Notably, 18 // the StructuralTerms API computes a minimal representation of the structural 19 // restrictions on a type parameter. 20 // 21 // An external version of these APIs is available in the 22 // golang.org/x/exp/typeparams module. 23 package typeparams 24 25 import ( 26 "go/ast" 27 "go/token" 28 "go/types" 29 ) 30 31 // UnpackIndexExpr extracts data from AST nodes that represent index 32 // expressions. 33 // 34 // For an ast.IndexExpr, the resulting indices slice will contain exactly one 35 // index expression. For an ast.IndexListExpr (go1.18+), it may have a variable 36 // number of index expressions. 37 // 38 // For nodes that don't represent index expressions, the first return value of 39 // UnpackIndexExpr will be nil. 40 func UnpackIndexExpr(n ast.Node) (x ast.Expr, lbrack token.Pos, indices []ast.Expr, rbrack token.Pos) { 41 switch e := n.(type) { 42 case *ast.IndexExpr: 43 return e.X, e.Lbrack, []ast.Expr{e.Index}, e.Rbrack 44 case *IndexListExpr: 45 return e.X, e.Lbrack, e.Indices, e.Rbrack 46 } 47 return nil, token.NoPos, nil, token.NoPos 48 } 49 50 // PackIndexExpr returns an *ast.IndexExpr or *ast.IndexListExpr, depending on 51 // the cardinality of indices. Calling PackIndexExpr with len(indices) == 0 52 // will panic. 53 func PackIndexExpr(x ast.Expr, lbrack token.Pos, indices []ast.Expr, rbrack token.Pos) ast.Expr { 54 switch len(indices) { 55 case 0: 56 panic("empty indices") 57 case 1: 58 return &ast.IndexExpr{ 59 X: x, 60 Lbrack: lbrack, 61 Index: indices[0], 62 Rbrack: rbrack, 63 } 64 default: 65 return &IndexListExpr{ 66 X: x, 67 Lbrack: lbrack, 68 Indices: indices, 69 Rbrack: rbrack, 70 } 71 } 72 } 73 74 // IsTypeParam reports whether t is a type parameter. 75 func IsTypeParam(t types.Type) bool { 76 _, ok := t.(*TypeParam) 77 return ok 78 } 79 80 // OriginMethod returns the origin method associated with the method fn. 81 // For methods on a non-generic receiver base type, this is just 82 // fn. However, for methods with a generic receiver, OriginMethod returns the 83 // corresponding method in the method set of the origin type. 84 // 85 // As a special case, if fn is not a method (has no receiver), OriginMethod 86 // returns fn. 87 func OriginMethod(fn *types.Func) *types.Func { 88 recv := fn.Type().(*types.Signature).Recv() 89 if recv == nil { 90 91 return fn 92 } 93 base := recv.Type() 94 p, isPtr := base.(*types.Pointer) 95 if isPtr { 96 base = p.Elem() 97 } 98 named, isNamed := base.(*types.Named) 99 if !isNamed { 100 // Receiver is a *types.Interface. 101 return fn 102 } 103 if ForNamed(named).Len() == 0 { 104 // Receiver base has no type parameters, so we can avoid the lookup below. 105 return fn 106 } 107 orig := NamedTypeOrigin(named) 108 gfn, _, _ := types.LookupFieldOrMethod(orig, true, fn.Pkg(), fn.Name()) 109 return gfn.(*types.Func) 110 } 111 112 // GenericAssignableTo is a generalization of types.AssignableTo that 113 // implements the following rule for uninstantiated generic types: 114 // 115 // If V and T are generic named types, then V is considered assignable to T if, 116 // for every possible instantation of V[A_1, ..., A_N], the instantiation 117 // T[A_1, ..., A_N] is valid and V[A_1, ..., A_N] implements T[A_1, ..., A_N]. 118 // 119 // If T has structural constraints, they must be satisfied by V. 120 // 121 // For example, consider the following type declarations: 122 // 123 // type Interface[T any] interface { 124 // Accept(T) 125 // } 126 // 127 // type Container[T any] struct { 128 // Element T 129 // } 130 // 131 // func (c Container[T]) Accept(t T) { c.Element = t } 132 // 133 // In this case, GenericAssignableTo reports that instantiations of Container 134 // are assignable to the corresponding instantiation of Interface. 135 func GenericAssignableTo(ctxt *Context, V, T types.Type) bool { 136 // If V and T are not both named, or do not have matching non-empty type 137 // parameter lists, fall back on types.AssignableTo. 138 139 VN, Vnamed := V.(*types.Named) 140 TN, Tnamed := T.(*types.Named) 141 if !Vnamed || !Tnamed { 142 return types.AssignableTo(V, T) 143 } 144 145 vtparams := ForNamed(VN) 146 ttparams := ForNamed(TN) 147 if vtparams.Len() == 0 || vtparams.Len() != ttparams.Len() || NamedTypeArgs(VN).Len() != 0 || NamedTypeArgs(TN).Len() != 0 { 148 return types.AssignableTo(V, T) 149 } 150 151 // V and T have the same (non-zero) number of type params. Instantiate both 152 // with the type parameters of V. This must always succeed for V, and will 153 // succeed for T if and only if the type set of each type parameter of V is a 154 // subset of the type set of the corresponding type parameter of T, meaning 155 // that every instantiation of V corresponds to a valid instantiation of T. 156 157 // Minor optimization: ensure we share a context across the two 158 // instantiations below. 159 if ctxt == nil { 160 ctxt = NewContext() 161 } 162 163 var targs []types.Type 164 for i := 0; i < vtparams.Len(); i++ { 165 targs = append(targs, vtparams.At(i)) 166 } 167 168 vinst, err := Instantiate(ctxt, V, targs, true) 169 if err != nil { 170 panic("type parameters should satisfy their own constraints") 171 } 172 173 tinst, err := Instantiate(ctxt, T, targs, true) 174 if err != nil { 175 return false 176 } 177 178 return types.AssignableTo(vinst, tinst) 179 } 180