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 6 // interact with generic Go code, as introduced with Go 1.18. It 7 // supplements the standard library APIs. Notably, the StructuralTerms 8 // API computes a minimal representation of the structural 9 // restrictions on a type parameter. 10 // 11 // An external version of these APIs is available in the 12 // golang.org/x/exp/typeparams module. 13 package typeparams 14 15 import ( 16 "go/ast" 17 "go/token" 18 "go/types" 19 20 "golang.org/x/tools/internal/aliases" 21 ) 22 23 // UnpackIndexExpr extracts data from AST nodes that represent index 24 // expressions. 25 // 26 // For an ast.IndexExpr, the resulting indices slice will contain exactly one 27 // index expression. For an ast.IndexListExpr (go1.18+), it may have a variable 28 // number of index expressions. 29 // 30 // For nodes that don't represent index expressions, the first return value of 31 // UnpackIndexExpr will be nil. 32 func UnpackIndexExpr(n ast.Node) (x ast.Expr, lbrack token.Pos, indices []ast.Expr, rbrack token.Pos) { 33 switch e := n.(type) { 34 case *ast.IndexExpr: 35 return e.X, e.Lbrack, []ast.Expr{e.Index}, e.Rbrack 36 case *ast.IndexListExpr: 37 return e.X, e.Lbrack, e.Indices, e.Rbrack 38 } 39 return nil, token.NoPos, nil, token.NoPos 40 } 41 42 // PackIndexExpr returns an *ast.IndexExpr or *ast.IndexListExpr, depending on 43 // the cardinality of indices. Calling PackIndexExpr with len(indices) == 0 44 // will panic. 45 func PackIndexExpr(x ast.Expr, lbrack token.Pos, indices []ast.Expr, rbrack token.Pos) ast.Expr { 46 switch len(indices) { 47 case 0: 48 panic("empty indices") 49 case 1: 50 return &ast.IndexExpr{ 51 X: x, 52 Lbrack: lbrack, 53 Index: indices[0], 54 Rbrack: rbrack, 55 } 56 default: 57 return &ast.IndexListExpr{ 58 X: x, 59 Lbrack: lbrack, 60 Indices: indices, 61 Rbrack: rbrack, 62 } 63 } 64 } 65 66 // IsTypeParam reports whether t is a type parameter (or an alias of one). 67 func IsTypeParam(t types.Type) bool { 68 _, ok := aliases.Unalias(t).(*types.TypeParam) 69 return ok 70 } 71 72 // GenericAssignableTo is a generalization of types.AssignableTo that 73 // implements the following rule for uninstantiated generic types: 74 // 75 // If V and T are generic named types, then V is considered assignable to T if, 76 // for every possible instantiation of V[A_1, ..., A_N], the instantiation 77 // T[A_1, ..., A_N] is valid and V[A_1, ..., A_N] implements T[A_1, ..., A_N]. 78 // 79 // If T has structural constraints, they must be satisfied by V. 80 // 81 // For example, consider the following type declarations: 82 // 83 // type Interface[T any] interface { 84 // Accept(T) 85 // } 86 // 87 // type Container[T any] struct { 88 // Element T 89 // } 90 // 91 // func (c Container[T]) Accept(t T) { c.Element = t } 92 // 93 // In this case, GenericAssignableTo reports that instantiations of Container 94 // are assignable to the corresponding instantiation of Interface. 95 func GenericAssignableTo(ctxt *types.Context, V, T types.Type) bool { 96 V = aliases.Unalias(V) 97 T = aliases.Unalias(T) 98 99 // If V and T are not both named, or do not have matching non-empty type 100 // parameter lists, fall back on types.AssignableTo. 101 102 VN, Vnamed := V.(*types.Named) 103 TN, Tnamed := T.(*types.Named) 104 if !Vnamed || !Tnamed { 105 return types.AssignableTo(V, T) 106 } 107 108 vtparams := VN.TypeParams() 109 ttparams := TN.TypeParams() 110 if vtparams.Len() == 0 || vtparams.Len() != ttparams.Len() || VN.TypeArgs().Len() != 0 || TN.TypeArgs().Len() != 0 { 111 return types.AssignableTo(V, T) 112 } 113 114 // V and T have the same (non-zero) number of type params. Instantiate both 115 // with the type parameters of V. This must always succeed for V, and will 116 // succeed for T if and only if the type set of each type parameter of V is a 117 // subset of the type set of the corresponding type parameter of T, meaning 118 // that every instantiation of V corresponds to a valid instantiation of T. 119 120 // Minor optimization: ensure we share a context across the two 121 // instantiations below. 122 if ctxt == nil { 123 ctxt = types.NewContext() 124 } 125 126 var targs []types.Type 127 for i := 0; i < vtparams.Len(); i++ { 128 targs = append(targs, vtparams.At(i)) 129 } 130 131 vinst, err := types.Instantiate(ctxt, V, targs, true) 132 if err != nil { 133 panic("type parameters should satisfy their own constraints") 134 } 135 136 tinst, err := types.Instantiate(ctxt, T, targs, true) 137 if err != nil { 138 return false 139 } 140 141 return types.AssignableTo(vinst, tinst) 142 } 143