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.
13package typeparams
14
15import (
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.
32func 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.
45func 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).
67func 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.
95func 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