1// Copyright 2009 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 types
6
7import (
8	"bytes"
9	"encoding/binary"
10	"fmt"
11	"strconv"
12	"sync"
13
14	"cmd/compile/internal/base"
15	"cmd/internal/notsha256"
16)
17
18// BuiltinPkg is a fake package that declares the universe block.
19var BuiltinPkg *Pkg
20
21// LocalPkg is the package being compiled.
22var LocalPkg *Pkg
23
24// UnsafePkg is package unsafe.
25var UnsafePkg *Pkg
26
27// BlankSym is the blank (_) symbol.
28var BlankSym *Sym
29
30// numImport tracks how often a package with a given name is imported.
31// It is used to provide a better error message (by using the package
32// path to disambiguate) if a package that appears multiple times with
33// the same name appears in an error message.
34var NumImport = make(map[string]int)
35
36// fmtMode represents the kind of printing being done.
37// The default is regular Go syntax (fmtGo).
38// fmtDebug is like fmtGo but for debugging dumps and prints the type kind too.
39// fmtTypeID and fmtTypeIDName are for generating various unique representations
40// of types used in hashes, the linker, and function/method instantiations.
41type fmtMode int
42
43const (
44	fmtGo fmtMode = iota
45	fmtDebug
46	fmtTypeID
47	fmtTypeIDName
48)
49
50// Sym
51
52// Format implements formatting for a Sym.
53// The valid formats are:
54//
55//	%v	Go syntax: Name for symbols in the local package, PkgName.Name for imported symbols.
56//	%+v	Debug syntax: always include PkgName. prefix even for local names.
57//	%S	Short syntax: Name only, no matter what.
58func (s *Sym) Format(f fmt.State, verb rune) {
59	mode := fmtGo
60	switch verb {
61	case 'v', 'S':
62		if verb == 'v' && f.Flag('+') {
63			mode = fmtDebug
64		}
65		fmt.Fprint(f, sconv(s, verb, mode))
66
67	default:
68		fmt.Fprintf(f, "%%!%c(*types.Sym=%p)", verb, s)
69	}
70}
71
72func (s *Sym) String() string {
73	return sconv(s, 0, fmtGo)
74}
75
76// See #16897 for details about performance implications
77// before changing the implementation of sconv.
78func sconv(s *Sym, verb rune, mode fmtMode) string {
79	if verb == 'L' {
80		panic("linksymfmt")
81	}
82
83	if s == nil {
84		return "<S>"
85	}
86
87	q := pkgqual(s.Pkg, verb, mode)
88	if q == "" {
89		return s.Name
90	}
91
92	buf := fmtBufferPool.Get().(*bytes.Buffer)
93	buf.Reset()
94	defer fmtBufferPool.Put(buf)
95
96	buf.WriteString(q)
97	buf.WriteByte('.')
98	buf.WriteString(s.Name)
99	return InternString(buf.Bytes())
100}
101
102func sconv2(b *bytes.Buffer, s *Sym, verb rune, mode fmtMode) {
103	if verb == 'L' {
104		panic("linksymfmt")
105	}
106	if s == nil {
107		b.WriteString("<S>")
108		return
109	}
110
111	symfmt(b, s, verb, mode)
112}
113
114func symfmt(b *bytes.Buffer, s *Sym, verb rune, mode fmtMode) {
115	name := s.Name
116	if q := pkgqual(s.Pkg, verb, mode); q != "" {
117		b.WriteString(q)
118		b.WriteByte('.')
119	}
120	b.WriteString(name)
121}
122
123// pkgqual returns the qualifier that should be used for printing
124// symbols from the given package in the given mode.
125// If it returns the empty string, no qualification is needed.
126func pkgqual(pkg *Pkg, verb rune, mode fmtMode) string {
127	if pkg == nil {
128		return ""
129	}
130	if verb != 'S' {
131		switch mode {
132		case fmtGo: // This is for the user
133			if pkg == BuiltinPkg || pkg == LocalPkg {
134				return ""
135			}
136
137			// If the name was used by multiple packages, display the full path,
138			if pkg.Name != "" && NumImport[pkg.Name] > 1 {
139				return strconv.Quote(pkg.Path)
140			}
141			return pkg.Name
142
143		case fmtDebug:
144			return pkg.Name
145
146		case fmtTypeIDName:
147			// dcommontype, typehash
148			return pkg.Name
149
150		case fmtTypeID:
151			// (methodsym), typesym, weaksym
152			return pkg.Prefix
153		}
154	}
155
156	return ""
157}
158
159// Type
160
161var BasicTypeNames = []string{
162	TINT:        "int",
163	TUINT:       "uint",
164	TINT8:       "int8",
165	TUINT8:      "uint8",
166	TINT16:      "int16",
167	TUINT16:     "uint16",
168	TINT32:      "int32",
169	TUINT32:     "uint32",
170	TINT64:      "int64",
171	TUINT64:     "uint64",
172	TUINTPTR:    "uintptr",
173	TFLOAT32:    "float32",
174	TFLOAT64:    "float64",
175	TCOMPLEX64:  "complex64",
176	TCOMPLEX128: "complex128",
177	TBOOL:       "bool",
178	TANY:        "any",
179	TSTRING:     "string",
180	TNIL:        "nil",
181	TIDEAL:      "untyped number",
182	TBLANK:      "blank",
183}
184
185var fmtBufferPool = sync.Pool{
186	New: func() interface{} {
187		return new(bytes.Buffer)
188	},
189}
190
191// Format implements formatting for a Type.
192// The valid formats are:
193//
194//	%v	Go syntax
195//	%+v	Debug syntax: Go syntax with a KIND- prefix for all but builtins.
196//	%L	Go syntax for underlying type if t is named
197//	%S	short Go syntax: drop leading "func" in function type
198//	%-S	special case for method receiver symbol
199func (t *Type) Format(s fmt.State, verb rune) {
200	mode := fmtGo
201	switch verb {
202	case 'v', 'S', 'L':
203		if verb == 'v' && s.Flag('+') { // %+v is debug format
204			mode = fmtDebug
205		}
206		if verb == 'S' && s.Flag('-') { // %-S is special case for receiver - short typeid format
207			mode = fmtTypeID
208		}
209		fmt.Fprint(s, tconv(t, verb, mode))
210	default:
211		fmt.Fprintf(s, "%%!%c(*Type=%p)", verb, t)
212	}
213}
214
215// String returns the Go syntax for the type t.
216func (t *Type) String() string {
217	return tconv(t, 0, fmtGo)
218}
219
220// LinkString returns a string description of t, suitable for use in
221// link symbols.
222//
223// The description corresponds to type identity. That is, for any pair
224// of types t1 and t2, Identical(t1, t2) == (t1.LinkString() ==
225// t2.LinkString()) is true. Thus it's safe to use as a map key to
226// implement a type-identity-keyed map.
227func (t *Type) LinkString() string {
228	return tconv(t, 0, fmtTypeID)
229}
230
231// NameString generates a user-readable, mostly unique string
232// description of t. NameString always returns the same description
233// for identical types, even across compilation units.
234//
235// NameString qualifies identifiers by package name, so it has
236// collisions when different packages share the same names and
237// identifiers. It also does not distinguish function-scope defined
238// types from package-scoped defined types or from each other.
239func (t *Type) NameString() string {
240	return tconv(t, 0, fmtTypeIDName)
241}
242
243func tconv(t *Type, verb rune, mode fmtMode) string {
244	buf := fmtBufferPool.Get().(*bytes.Buffer)
245	buf.Reset()
246	defer fmtBufferPool.Put(buf)
247
248	tconv2(buf, t, verb, mode, nil)
249	return InternString(buf.Bytes())
250}
251
252// tconv2 writes a string representation of t to b.
253// flag and mode control exactly what is printed.
254// Any types x that are already in the visited map get printed as @%d where %d=visited[x].
255// See #16897 before changing the implementation of tconv.
256func tconv2(b *bytes.Buffer, t *Type, verb rune, mode fmtMode, visited map[*Type]int) {
257	if off, ok := visited[t]; ok {
258		// We've seen this type before, so we're trying to print it recursively.
259		// Print a reference to it instead.
260		fmt.Fprintf(b, "@%d", off)
261		return
262	}
263	if t == nil {
264		b.WriteString("<T>")
265		return
266	}
267	if t.Kind() == TSSA {
268		b.WriteString(t.extra.(string))
269		return
270	}
271	if t.Kind() == TTUPLE {
272		b.WriteString(t.FieldType(0).String())
273		b.WriteByte(',')
274		b.WriteString(t.FieldType(1).String())
275		return
276	}
277
278	if t.Kind() == TRESULTS {
279		tys := t.extra.(*Results).Types
280		for i, et := range tys {
281			if i > 0 {
282				b.WriteByte(',')
283			}
284			b.WriteString(et.String())
285		}
286		return
287	}
288
289	if t == AnyType || t == ByteType || t == RuneType {
290		// in %-T mode collapse predeclared aliases with their originals.
291		switch mode {
292		case fmtTypeIDName, fmtTypeID:
293			t = Types[t.Kind()]
294		default:
295			sconv2(b, t.Sym(), 'S', mode)
296			return
297		}
298	}
299	if t == ErrorType {
300		b.WriteString("error")
301		return
302	}
303
304	// Unless the 'L' flag was specified, if the type has a name, just print that name.
305	if verb != 'L' && t.Sym() != nil && t != Types[t.Kind()] {
306		// Default to 'v' if verb is invalid.
307		if verb != 'S' {
308			verb = 'v'
309		}
310
311		// In unified IR, function-scope defined types will have a ·N
312		// suffix embedded directly in their Name. Trim this off for
313		// non-fmtTypeID modes.
314		sym := t.Sym()
315		if mode != fmtTypeID {
316			base, _ := SplitVargenSuffix(sym.Name)
317			if len(base) < len(sym.Name) {
318				sym = &Sym{Pkg: sym.Pkg, Name: base}
319			}
320		}
321		sconv2(b, sym, verb, mode)
322		return
323	}
324
325	if int(t.Kind()) < len(BasicTypeNames) && BasicTypeNames[t.Kind()] != "" {
326		var name string
327		switch t {
328		case UntypedBool:
329			name = "untyped bool"
330		case UntypedString:
331			name = "untyped string"
332		case UntypedInt:
333			name = "untyped int"
334		case UntypedRune:
335			name = "untyped rune"
336		case UntypedFloat:
337			name = "untyped float"
338		case UntypedComplex:
339			name = "untyped complex"
340		default:
341			name = BasicTypeNames[t.Kind()]
342		}
343		b.WriteString(name)
344		return
345	}
346
347	if mode == fmtDebug {
348		b.WriteString(t.Kind().String())
349		b.WriteByte('-')
350		tconv2(b, t, 'v', fmtGo, visited)
351		return
352	}
353
354	// At this point, we might call tconv2 recursively. Add the current type to the visited list so we don't
355	// try to print it recursively.
356	// We record the offset in the result buffer where the type's text starts. This offset serves as a reference
357	// point for any later references to the same type.
358	// Note that we remove the type from the visited map as soon as the recursive call is done.
359	// This prevents encoding types like map[*int]*int as map[*int]@4. (That encoding would work,
360	// but I'd like to use the @ notation only when strictly necessary.)
361	if visited == nil {
362		visited = map[*Type]int{}
363	}
364	visited[t] = b.Len()
365	defer delete(visited, t)
366
367	switch t.Kind() {
368	case TPTR:
369		b.WriteByte('*')
370		switch mode {
371		case fmtTypeID, fmtTypeIDName:
372			if verb == 'S' {
373				tconv2(b, t.Elem(), 'S', mode, visited)
374				return
375			}
376		}
377		tconv2(b, t.Elem(), 'v', mode, visited)
378
379	case TARRAY:
380		b.WriteByte('[')
381		b.WriteString(strconv.FormatInt(t.NumElem(), 10))
382		b.WriteByte(']')
383		tconv2(b, t.Elem(), 0, mode, visited)
384
385	case TSLICE:
386		b.WriteString("[]")
387		tconv2(b, t.Elem(), 0, mode, visited)
388
389	case TCHAN:
390		switch t.ChanDir() {
391		case Crecv:
392			b.WriteString("<-chan ")
393			tconv2(b, t.Elem(), 0, mode, visited)
394		case Csend:
395			b.WriteString("chan<- ")
396			tconv2(b, t.Elem(), 0, mode, visited)
397		default:
398			b.WriteString("chan ")
399			if t.Elem() != nil && t.Elem().IsChan() && t.Elem().Sym() == nil && t.Elem().ChanDir() == Crecv {
400				b.WriteByte('(')
401				tconv2(b, t.Elem(), 0, mode, visited)
402				b.WriteByte(')')
403			} else {
404				tconv2(b, t.Elem(), 0, mode, visited)
405			}
406		}
407
408	case TMAP:
409		b.WriteString("map[")
410		tconv2(b, t.Key(), 0, mode, visited)
411		b.WriteByte(']')
412		tconv2(b, t.Elem(), 0, mode, visited)
413
414	case TINTER:
415		if t.IsEmptyInterface() {
416			b.WriteString("interface {}")
417			break
418		}
419		b.WriteString("interface {")
420		for i, f := range t.AllMethods() {
421			if i != 0 {
422				b.WriteByte(';')
423			}
424			b.WriteByte(' ')
425			switch {
426			case f.Sym == nil:
427				// Check first that a symbol is defined for this type.
428				// Wrong interface definitions may have types lacking a symbol.
429				break
430			case IsExported(f.Sym.Name):
431				sconv2(b, f.Sym, 'S', mode)
432			default:
433				if mode != fmtTypeIDName {
434					mode = fmtTypeID
435				}
436				sconv2(b, f.Sym, 'v', mode)
437			}
438			tconv2(b, f.Type, 'S', mode, visited)
439		}
440		if len(t.AllMethods()) != 0 {
441			b.WriteByte(' ')
442		}
443		b.WriteByte('}')
444
445	case TFUNC:
446		if verb == 'S' {
447			// no leading func
448		} else {
449			if t.Recv() != nil {
450				b.WriteString("method")
451				formatParams(b, t.Recvs(), mode, visited)
452				b.WriteByte(' ')
453			}
454			b.WriteString("func")
455		}
456		formatParams(b, t.Params(), mode, visited)
457
458		switch t.NumResults() {
459		case 0:
460			// nothing to do
461
462		case 1:
463			b.WriteByte(' ')
464			tconv2(b, t.Result(0).Type, 0, mode, visited) // struct->field->field's type
465
466		default:
467			b.WriteByte(' ')
468			formatParams(b, t.Results(), mode, visited)
469		}
470
471	case TSTRUCT:
472		if m := t.StructType().Map; m != nil {
473			mt := m.MapType()
474			// Format the bucket struct for map[x]y as map.bucket[x]y.
475			// This avoids a recursive print that generates very long names.
476			switch t {
477			case mt.Bucket:
478				b.WriteString("map.bucket[")
479			default:
480				base.Fatalf("unknown internal map type")
481			}
482			tconv2(b, m.Key(), 0, mode, visited)
483			b.WriteByte(']')
484			tconv2(b, m.Elem(), 0, mode, visited)
485			break
486		}
487
488		b.WriteString("struct {")
489		for i, f := range t.Fields() {
490			if i != 0 {
491				b.WriteByte(';')
492			}
493			b.WriteByte(' ')
494			fldconv(b, f, 'L', mode, visited, false)
495		}
496		if t.NumFields() != 0 {
497			b.WriteByte(' ')
498		}
499		b.WriteByte('}')
500
501	case TFORW:
502		b.WriteString("undefined")
503		if t.Sym() != nil {
504			b.WriteByte(' ')
505			sconv2(b, t.Sym(), 'v', mode)
506		}
507
508	case TUNSAFEPTR:
509		b.WriteString("unsafe.Pointer")
510
511	case Txxx:
512		b.WriteString("Txxx")
513
514	default:
515		// Don't know how to handle - fall back to detailed prints
516		b.WriteString(t.Kind().String())
517		b.WriteString(" <")
518		sconv2(b, t.Sym(), 'v', mode)
519		b.WriteString(">")
520
521	}
522}
523
524func formatParams(b *bytes.Buffer, params []*Field, mode fmtMode, visited map[*Type]int) {
525	b.WriteByte('(')
526	fieldVerb := 'v'
527	switch mode {
528	case fmtTypeID, fmtTypeIDName, fmtGo:
529		// no argument names on function signature, and no "noescape"/"nosplit" tags
530		fieldVerb = 'S'
531	}
532	for i, param := range params {
533		if i != 0 {
534			b.WriteString(", ")
535		}
536		fldconv(b, param, fieldVerb, mode, visited, true)
537	}
538	b.WriteByte(')')
539}
540
541func fldconv(b *bytes.Buffer, f *Field, verb rune, mode fmtMode, visited map[*Type]int, isParam bool) {
542	if f == nil {
543		b.WriteString("<T>")
544		return
545	}
546
547	var name string
548	nameSep := " "
549	if verb != 'S' {
550		s := f.Sym
551
552		// Using type aliases and embedded fields, it's possible to
553		// construct types that can't be directly represented as a
554		// type literal. For example, given "type Int = int" (#50190),
555		// it would be incorrect to format "struct{ Int }" as either
556		// "struct{ int }" or "struct{ Int int }", because those each
557		// represent other, distinct types.
558		//
559		// So for the purpose of LinkString (i.e., fmtTypeID), we use
560		// the non-standard syntax "struct{ Int = int }" to represent
561		// embedded fields that have been renamed through the use of
562		// type aliases.
563		if f.Embedded != 0 {
564			if mode == fmtTypeID {
565				nameSep = " = "
566
567				// Compute tsym, the symbol that would normally be used as
568				// the field name when embedding f.Type.
569				// TODO(mdempsky): Check for other occurrences of this logic
570				// and deduplicate.
571				typ := f.Type
572				if typ.IsPtr() {
573					base.Assertf(typ.Sym() == nil, "embedded pointer type has name: %L", typ)
574					typ = typ.Elem()
575				}
576				tsym := typ.Sym()
577
578				// If the field name matches the embedded type's name, then
579				// suppress printing of the field name. For example, format
580				// "struct{ T }" as simply that instead of "struct{ T = T }".
581				if tsym != nil && (s == tsym || IsExported(tsym.Name) && s.Name == tsym.Name) {
582					s = nil
583				}
584			} else {
585				// Suppress the field name for embedded fields for
586				// non-LinkString formats, to match historical behavior.
587				// TODO(mdempsky): Re-evaluate this.
588				s = nil
589			}
590		}
591
592		if s != nil {
593			if isParam {
594				name = fmt.Sprint(f.Nname)
595			} else if verb == 'L' {
596				name = s.Name
597				if !IsExported(name) && mode != fmtTypeIDName {
598					name = sconv(s, 0, mode) // qualify non-exported names (used on structs, not on funarg)
599				}
600			} else {
601				name = sconv(s, 0, mode)
602			}
603		}
604	}
605
606	if name != "" {
607		b.WriteString(name)
608		b.WriteString(nameSep)
609	}
610
611	if f.IsDDD() {
612		var et *Type
613		if f.Type != nil {
614			et = f.Type.Elem()
615		}
616		b.WriteString("...")
617		tconv2(b, et, 0, mode, visited)
618	} else {
619		tconv2(b, f.Type, 0, mode, visited)
620	}
621
622	if verb != 'S' && !isParam && f.Note != "" {
623		b.WriteString(" ")
624		b.WriteString(strconv.Quote(f.Note))
625	}
626}
627
628// SplitVargenSuffix returns name split into a base string and a ·N
629// suffix, if any.
630func SplitVargenSuffix(name string) (base, suffix string) {
631	i := len(name)
632	for i > 0 && name[i-1] >= '0' && name[i-1] <= '9' {
633		i--
634	}
635	const dot = "·"
636	if i >= len(dot) && name[i-len(dot):i] == dot {
637		i -= len(dot)
638		return name[:i], name[i:]
639	}
640	return name, ""
641}
642
643// TypeHash computes a hash value for type t to use in type switch statements.
644func TypeHash(t *Type) uint32 {
645	p := t.LinkString()
646
647	// Using SHA256 is overkill, but reduces accidental collisions.
648	h := notsha256.Sum256([]byte(p))
649	return binary.LittleEndian.Uint32(h[:4])
650}
651