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
5package noder
6
7import (
8	"cmd/compile/internal/base"
9	"cmd/compile/internal/ir"
10	"cmd/compile/internal/typecheck"
11	"cmd/compile/internal/types"
12	"cmd/compile/internal/types2"
13	"cmd/internal/src"
14	"strings"
15)
16
17func (g *irgen) pkg(pkg *types2.Package) *types.Pkg {
18	switch pkg {
19	case nil:
20		return types.BuiltinPkg
21	case g.self:
22		return types.LocalPkg
23	case types2.Unsafe:
24		return types.UnsafePkg
25	}
26	return types.NewPkg(pkg.Path(), pkg.Name())
27}
28
29var universeAny = types2.Universe.Lookup("any").Type()
30
31// typ converts a types2.Type to a types.Type, including caching of previously
32// translated types.
33func (g *irgen) typ(typ types2.Type) *types.Type {
34	// Defer the CheckSize calls until we have fully-defined a
35	// (possibly-recursive) top-level type.
36	types.DeferCheckSize()
37	res := g.typ1(typ)
38	types.ResumeCheckSize()
39
40	// Finish up any types on typesToFinalize, now that we are at the top of a
41	// fully-defined (possibly recursive) type. fillinMethods could create more
42	// types to finalize.
43	for len(g.typesToFinalize) > 0 {
44		l := len(g.typesToFinalize)
45		info := g.typesToFinalize[l-1]
46		g.typesToFinalize = g.typesToFinalize[:l-1]
47		types.DeferCheckSize()
48		g.fillinMethods(info.typ, info.ntyp)
49		types.ResumeCheckSize()
50	}
51	return res
52}
53
54// typ1 is like typ, but doesn't call CheckSize, since it may have only
55// constructed part of a recursive type. Should not be called from outside this
56// file (g.typ is the "external" entry point).
57func (g *irgen) typ1(typ types2.Type) *types.Type {
58	// See issue 49583: the type checker has trouble keeping track of aliases,
59	// but for such a common alias as any we can improve things by preserving a
60	// pointer identity that can be checked when formatting type strings.
61	if typ == universeAny {
62		return types.AnyType
63	}
64	// Cache type2-to-type mappings. Important so that each defined generic
65	// type (instantiated or not) has a single types.Type representation.
66	// Also saves a lot of computation and memory by avoiding re-translating
67	// types2 types repeatedly.
68	res, ok := g.typs[typ]
69	if !ok {
70		res = g.typ0(typ)
71		// Calculate the size for all concrete types seen by the frontend.
72		// This is the replacement for the CheckSize() calls in the types1
73		// typechecker. These will be deferred until the top-level g.typ().
74		if res != nil && !res.IsUntyped() && !res.IsFuncArgStruct() && !res.HasTParam() {
75			types.CheckSize(res)
76		}
77		g.typs[typ] = res
78	}
79	return res
80}
81
82// instTypeName2 creates a name for an instantiated type, base on the type args
83// (given as types2 types).
84func (g *irgen) instTypeName2(name string, targs *types2.TypeList) string {
85	rparams := make([]*types.Type, targs.Len())
86	for i := range rparams {
87		rparams[i] = g.typ(targs.At(i))
88	}
89	return typecheck.InstTypeName(name, rparams)
90}
91
92// typ0 converts a types2.Type to a types.Type, but doesn't do the caching check
93// at the top level.
94func (g *irgen) typ0(typ types2.Type) *types.Type {
95	switch typ := typ.(type) {
96	case *types2.Basic:
97		return g.basic(typ)
98	case *types2.Named:
99		// If tparams is set, but targs is not, typ is a base generic
100		// type. typ is appearing as part of the source type of an alias,
101		// since that is the only use of a generic type that doesn't
102		// involve instantiation. We just translate the named type in the
103		// normal way below using g.obj().
104		if typ.TypeParams() != nil && typ.TypeArgs() != nil {
105			// typ is an instantiation of a defined (named) generic type.
106			// This instantiation should also be a defined (named) type.
107			// types2 gives us the substituted type in t.Underlying()
108			// The substituted type may or may not still have type
109			// params. We might, for example, be substituting one type
110			// param for another type param.
111			//
112			// When converted to types.Type, typ has a unique name,
113			// based on the names of the type arguments.
114			instName := g.instTypeName2(typ.Obj().Name(), typ.TypeArgs())
115			s := g.pkg(typ.Obj().Pkg()).Lookup(instName)
116			if s.Def != nil {
117				// We have already encountered this instantiation.
118				// Use the type we previously created, since there
119				// must be exactly one instance of a defined type.
120				return s.Def.Type()
121			}
122
123			// Make sure the base generic type exists in type1 (it may
124			// not yet if we are referecing an imported generic type, as
125			// opposed to a generic type declared in this package).
126			_ = g.obj(typ.Origin().Obj())
127
128			// Create a forwarding type first and put it in the g.typs
129			// map, in order to deal with recursive generic types
130			// (including via method signatures). Set up the extra
131			// ntyp information (Def, RParams, which may set
132			// HasTParam) before translating the underlying type
133			// itself, so we handle recursion correctly.
134			ntyp := typecheck.NewIncompleteNamedType(g.pos(typ.Obj().Pos()), s)
135			g.typs[typ] = ntyp
136
137			// If ntyp still has type params, then we must be
138			// referencing something like 'value[T2]', as when
139			// specifying the generic receiver of a method, where
140			// value was defined as "type value[T any] ...". Save the
141			// type args, which will now be the new typeparams of the
142			// current type.
143			//
144			// If ntyp does not have type params, we are saving the
145			// non-generic types used to instantiate this type. We'll
146			// use these when instantiating the methods of the
147			// instantiated type.
148			targs := typ.TypeArgs()
149			rparams := make([]*types.Type, targs.Len())
150			for i := range rparams {
151				rparams[i] = g.typ1(targs.At(i))
152			}
153			ntyp.SetRParams(rparams)
154			//fmt.Printf("Saw new type %v %v\n", instName, ntyp.HasTParam())
155
156			// Save the symbol for the base generic type.
157			ntyp.SetOrigSym(g.pkg(typ.Obj().Pkg()).Lookup(typ.Obj().Name()))
158			ntyp.SetUnderlying(g.typ1(typ.Underlying()))
159			if typ.NumMethods() != 0 {
160				// Save a delayed call to g.fillinMethods() (once
161				// potentially recursive types have been fully
162				// resolved).
163				g.typesToFinalize = append(g.typesToFinalize,
164					&typeDelayInfo{
165						typ:  typ,
166						ntyp: ntyp,
167					})
168			}
169			return ntyp
170		}
171		obj := g.obj(typ.Obj())
172		if obj.Op() != ir.OTYPE {
173			base.FatalfAt(obj.Pos(), "expected type: %L", obj)
174		}
175		return obj.Type()
176
177	case *types2.Array:
178		return types.NewArray(g.typ1(typ.Elem()), typ.Len())
179	case *types2.Chan:
180		return types.NewChan(g.typ1(typ.Elem()), dirs[typ.Dir()])
181	case *types2.Map:
182		return types.NewMap(g.typ1(typ.Key()), g.typ1(typ.Elem()))
183	case *types2.Pointer:
184		return types.NewPtr(g.typ1(typ.Elem()))
185	case *types2.Signature:
186		return g.signature(nil, typ)
187	case *types2.Slice:
188		return types.NewSlice(g.typ1(typ.Elem()))
189
190	case *types2.Struct:
191		fields := make([]*types.Field, typ.NumFields())
192		for i := range fields {
193			v := typ.Field(i)
194			f := types.NewField(g.pos(v), g.selector(v), g.typ1(v.Type()))
195			f.Note = typ.Tag(i)
196			if v.Embedded() {
197				f.Embedded = 1
198			}
199			fields[i] = f
200		}
201		return types.NewStruct(g.tpkg(typ), fields)
202
203	case *types2.Interface:
204		embeddeds := make([]*types.Field, typ.NumEmbeddeds())
205		j := 0
206		for i := range embeddeds {
207			// TODO(mdempsky): Get embedding position.
208			e := typ.EmbeddedType(i)
209
210			// With Go 1.18, an embedded element can be any type, not
211			// just an interface.
212			embeddeds[j] = types.NewField(src.NoXPos, nil, g.typ1(e))
213			j++
214		}
215		embeddeds = embeddeds[:j]
216
217		methods := make([]*types.Field, typ.NumExplicitMethods())
218		for i := range methods {
219			m := typ.ExplicitMethod(i)
220			mtyp := g.signature(types.FakeRecv(), m.Type().(*types2.Signature))
221			methods[i] = types.NewField(g.pos(m), g.selector(m), mtyp)
222		}
223
224		return types.NewInterface(g.tpkg(typ), append(embeddeds, methods...), typ.IsImplicit())
225
226	case *types2.TypeParam:
227		// Save the name of the type parameter in the sym of the type.
228		// Include the types2 subscript in the sym name
229		pkg := g.tpkg(typ)
230		// Create the unique types1 name for a type param, using its context with a
231		// function, type, or method declaration.
232		assert(g.curDecl != "")
233		nm := g.curDecl + "." + typ.Obj().Name()
234		sym := pkg.Lookup(nm)
235		if sym.Def != nil {
236			// Make sure we use the same type param type for the same
237			// name, whether it is created during types1-import or
238			// this types2-to-types1 translation.
239			return sym.Def.Type()
240		}
241		tp := types.NewTypeParam(sym, typ.Index())
242		nname := ir.NewDeclNameAt(g.pos(typ.Obj().Pos()), ir.OTYPE, sym)
243		sym.Def = nname
244		nname.SetType(tp)
245		tp.SetNod(nname)
246		// Set g.typs[typ] in case the bound methods reference typ.
247		g.typs[typ] = tp
248
249		bound := g.typ1(typ.Constraint())
250		tp.SetBound(bound)
251		return tp
252
253	case *types2.Union:
254		nt := typ.Len()
255		tlist := make([]*types.Type, nt)
256		tildes := make([]bool, nt)
257		for i := range tlist {
258			t := typ.Term(i)
259			tlist[i] = g.typ1(t.Type())
260			tildes[i] = t.Tilde()
261		}
262		return types.NewUnion(tlist, tildes)
263
264	case *types2.Tuple:
265		// Tuples are used for the type of a function call (i.e. the
266		// return value of the function).
267		if typ == nil {
268			return (*types.Type)(nil)
269		}
270		fields := make([]*types.Field, typ.Len())
271		for i := range fields {
272			fields[i] = g.param(typ.At(i))
273		}
274		t := types.NewStruct(types.LocalPkg, fields)
275		t.StructType().Funarg = types.FunargResults
276		return t
277
278	default:
279		base.FatalfAt(src.NoXPos, "unhandled type: %v (%T)", typ, typ)
280		panic("unreachable")
281	}
282}
283
284// fillinMethods fills in the method name nodes and types for a defined type with at
285// least one method. This is needed for later typechecking when looking up methods of
286// instantiated types, and for actually generating the methods for instantiated
287// types.
288func (g *irgen) fillinMethods(typ *types2.Named, ntyp *types.Type) {
289	targs2 := typ.TypeArgs()
290	targs := make([]*types.Type, targs2.Len())
291	for i := range targs {
292		targs[i] = g.typ1(targs2.At(i))
293	}
294
295	methods := make([]*types.Field, typ.NumMethods())
296	for i := range methods {
297		m := typ.Method(i)
298		recvType := deref2(types2.AsSignature(m.Type()).Recv().Type())
299		var meth *ir.Name
300		imported := false
301		if m.Pkg() != g.self {
302			// Imported methods cannot be loaded by name (what
303			// g.obj() does) - they must be loaded via their
304			// type.
305			meth = g.obj(recvType.(*types2.Named).Obj()).Type().Methods().Index(i).Nname.(*ir.Name)
306			// XXX Because Obj() returns the object of the base generic
307			// type, we have to still do the method translation below.
308			imported = true
309		} else {
310			meth = g.obj(m)
311		}
312		assert(recvType == types2.Type(typ))
313		if imported {
314			// Unfortunately, meth is the type of the method of the
315			// generic type, so we have to do a substitution to get
316			// the name/type of the method of the instantiated type,
317			// using m.Type().RParams() and typ.TArgs()
318			inst2 := g.instTypeName2("", typ.TypeArgs())
319			name := meth.Sym().Name
320			i1 := strings.Index(name, "[")
321			i2 := strings.Index(name[i1:], "]")
322			assert(i1 >= 0 && i2 >= 0)
323			// Generate the name of the instantiated method.
324			name = name[0:i1] + inst2 + name[i1+i2+1:]
325			newsym := meth.Sym().Pkg.Lookup(name)
326			var meth2 *ir.Name
327			if newsym.Def != nil {
328				meth2 = newsym.Def.(*ir.Name)
329			} else {
330				meth2 = ir.NewNameAt(meth.Pos(), newsym)
331				rparams := types2.AsSignature(m.Type()).RecvTypeParams()
332				tparams := make([]*types.Type, rparams.Len())
333				// Set g.curDecl to be the method context, so type
334				// params in the receiver of the method that we are
335				// translating gets the right unique name. We could
336				// be in a top-level typeDecl, so save and restore
337				// the current contents of g.curDecl.
338				savedCurDecl := g.curDecl
339				g.curDecl = typ.Obj().Name() + "." + m.Name()
340				for i := range tparams {
341					tparams[i] = g.typ1(rparams.At(i))
342				}
343				g.curDecl = savedCurDecl
344				assert(len(tparams) == len(targs))
345				ts := typecheck.Tsubster{
346					Tparams: tparams,
347					Targs:   targs,
348				}
349				// Do the substitution of the type
350				meth2.SetType(ts.Typ(meth.Type()))
351				newsym.Def = meth2
352			}
353			meth = meth2
354		}
355		methods[i] = types.NewField(meth.Pos(), g.selector(m), meth.Type())
356		methods[i].Nname = meth
357	}
358	ntyp.Methods().Set(methods)
359	if !ntyp.HasTParam() && !ntyp.HasShape() {
360		// Generate all the methods for a new fully-instantiated type.
361		typecheck.NeedInstType(ntyp)
362	}
363}
364
365func (g *irgen) signature(recv *types.Field, sig *types2.Signature) *types.Type {
366	tparams2 := sig.TypeParams()
367	tparams := make([]*types.Field, tparams2.Len())
368	for i := range tparams {
369		tp := tparams2.At(i).Obj()
370		tparams[i] = types.NewField(g.pos(tp), g.sym(tp), g.typ1(tp.Type()))
371	}
372
373	do := func(typ *types2.Tuple) []*types.Field {
374		fields := make([]*types.Field, typ.Len())
375		for i := range fields {
376			fields[i] = g.param(typ.At(i))
377		}
378		return fields
379	}
380	params := do(sig.Params())
381	results := do(sig.Results())
382	if sig.Variadic() {
383		params[len(params)-1].SetIsDDD(true)
384	}
385
386	return types.NewSignature(g.tpkg(sig), recv, tparams, params, results)
387}
388
389func (g *irgen) param(v *types2.Var) *types.Field {
390	return types.NewField(g.pos(v), g.sym(v), g.typ1(v.Type()))
391}
392
393func (g *irgen) sym(obj types2.Object) *types.Sym {
394	if name := obj.Name(); name != "" {
395		return g.pkg(obj.Pkg()).Lookup(obj.Name())
396	}
397	return nil
398}
399
400func (g *irgen) selector(obj types2.Object) *types.Sym {
401	pkg, name := g.pkg(obj.Pkg()), obj.Name()
402	if types.IsExported(name) {
403		pkg = types.LocalPkg
404	}
405	return pkg.Lookup(name)
406}
407
408// tpkg returns the package that a function, interface, struct, or typeparam type
409// expression appeared in.
410//
411// Caveat: For the degenerate types "func()", "interface{}", and
412// "struct{}", tpkg always returns LocalPkg. However, we only need the
413// package information so that go/types can report it via its API, and
414// the reason we fail to return the original package for these
415// particular types is because go/types does *not* report it for
416// them. So in practice this limitation is probably moot.
417func (g *irgen) tpkg(typ types2.Type) *types.Pkg {
418	if obj := anyObj(typ); obj != nil {
419		return g.pkg(obj.Pkg())
420	}
421	return types.LocalPkg
422}
423
424// anyObj returns some object accessible from typ, if any.
425func anyObj(typ types2.Type) types2.Object {
426	switch typ := typ.(type) {
427	case *types2.Signature:
428		if recv := typ.Recv(); recv != nil {
429			return recv
430		}
431		if params := typ.Params(); params.Len() > 0 {
432			return params.At(0)
433		}
434		if results := typ.Results(); results.Len() > 0 {
435			return results.At(0)
436		}
437	case *types2.Struct:
438		if typ.NumFields() > 0 {
439			return typ.Field(0)
440		}
441	case *types2.Interface:
442		if typ.NumExplicitMethods() > 0 {
443			return typ.ExplicitMethod(0)
444		}
445	case *types2.TypeParam:
446		return typ.Obj()
447	}
448	return nil
449}
450
451func (g *irgen) basic(typ *types2.Basic) *types.Type {
452	switch typ.Name() {
453	case "byte":
454		return types.ByteType
455	case "rune":
456		return types.RuneType
457	}
458	return *basics[typ.Kind()]
459}
460
461var basics = [...]**types.Type{
462	types2.Invalid:        new(*types.Type),
463	types2.Bool:           &types.Types[types.TBOOL],
464	types2.Int:            &types.Types[types.TINT],
465	types2.Int8:           &types.Types[types.TINT8],
466	types2.Int16:          &types.Types[types.TINT16],
467	types2.Int32:          &types.Types[types.TINT32],
468	types2.Int64:          &types.Types[types.TINT64],
469	types2.Uint:           &types.Types[types.TUINT],
470	types2.Uint8:          &types.Types[types.TUINT8],
471	types2.Uint16:         &types.Types[types.TUINT16],
472	types2.Uint32:         &types.Types[types.TUINT32],
473	types2.Uint64:         &types.Types[types.TUINT64],
474	types2.Uintptr:        &types.Types[types.TUINTPTR],
475	types2.Float32:        &types.Types[types.TFLOAT32],
476	types2.Float64:        &types.Types[types.TFLOAT64],
477	types2.Complex64:      &types.Types[types.TCOMPLEX64],
478	types2.Complex128:     &types.Types[types.TCOMPLEX128],
479	types2.String:         &types.Types[types.TSTRING],
480	types2.UnsafePointer:  &types.Types[types.TUNSAFEPTR],
481	types2.UntypedBool:    &types.UntypedBool,
482	types2.UntypedInt:     &types.UntypedInt,
483	types2.UntypedRune:    &types.UntypedRune,
484	types2.UntypedFloat:   &types.UntypedFloat,
485	types2.UntypedComplex: &types.UntypedComplex,
486	types2.UntypedString:  &types.UntypedString,
487	types2.UntypedNil:     &types.Types[types.TNIL],
488}
489
490var dirs = [...]types.ChanDir{
491	types2.SendRecv: types.Cboth,
492	types2.SendOnly: types.Csend,
493	types2.RecvOnly: types.Crecv,
494}
495
496// deref2 does a single deref of types2 type t, if it is a pointer type.
497func deref2(t types2.Type) types2.Type {
498	if ptr := types2.AsPointer(t); ptr != nil {
499		t = ptr.Elem()
500	}
501	return t
502}
503