1// Copyright 2013 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// This file implements printing of types.
6
7package types2
8
9import (
10	"bytes"
11	"fmt"
12	"sort"
13	"strconv"
14	"strings"
15	"unicode/utf8"
16)
17
18// A Qualifier controls how named package-level objects are printed in
19// calls to TypeString, ObjectString, and SelectionString.
20//
21// These three formatting routines call the Qualifier for each
22// package-level object O, and if the Qualifier returns a non-empty
23// string p, the object is printed in the form p.O.
24// If it returns an empty string, only the object name O is printed.
25//
26// Using a nil Qualifier is equivalent to using (*Package).Path: the
27// object is qualified by the import path, e.g., "encoding/json.Marshal".
28//
29type Qualifier func(*Package) string
30
31// RelativeTo returns a Qualifier that fully qualifies members of
32// all packages other than pkg.
33func RelativeTo(pkg *Package) Qualifier {
34	if pkg == nil {
35		return nil
36	}
37	return func(other *Package) string {
38		if pkg == other {
39			return "" // same package; unqualified
40		}
41		return other.Path()
42	}
43}
44
45// TypeString returns the string representation of typ.
46// The Qualifier controls the printing of
47// package-level objects, and may be nil.
48func TypeString(typ Type, qf Qualifier) string {
49	return typeString(typ, qf, false)
50}
51
52func typeString(typ Type, qf Qualifier, debug bool) string {
53	var buf bytes.Buffer
54	w := newTypeWriter(&buf, qf)
55	w.debug = debug
56	w.typ(typ)
57	return buf.String()
58}
59
60// WriteType writes the string representation of typ to buf.
61// The Qualifier controls the printing of
62// package-level objects, and may be nil.
63func WriteType(buf *bytes.Buffer, typ Type, qf Qualifier) {
64	newTypeWriter(buf, qf).typ(typ)
65}
66
67// WriteSignature writes the representation of the signature sig to buf,
68// without a leading "func" keyword.
69// The Qualifier controls the printing of
70// package-level objects, and may be nil.
71func WriteSignature(buf *bytes.Buffer, sig *Signature, qf Qualifier) {
72	newTypeWriter(buf, qf).signature(sig)
73}
74
75type typeWriter struct {
76	buf     *bytes.Buffer
77	seen    map[Type]bool
78	qf      Qualifier
79	ctxt    *Context       // if non-nil, we are type hashing
80	tparams *TypeParamList // local type parameters
81	debug   bool           // if true, write debug annotations
82}
83
84func newTypeWriter(buf *bytes.Buffer, qf Qualifier) *typeWriter {
85	return &typeWriter{buf, make(map[Type]bool), qf, nil, nil, false}
86}
87
88func newTypeHasher(buf *bytes.Buffer, ctxt *Context) *typeWriter {
89	assert(ctxt != nil)
90	return &typeWriter{buf, make(map[Type]bool), nil, ctxt, nil, false}
91}
92
93func (w *typeWriter) byte(b byte) {
94	if w.ctxt != nil {
95		if b == ' ' {
96			b = '#'
97		}
98		w.buf.WriteByte(b)
99		return
100	}
101	w.buf.WriteByte(b)
102	if b == ',' || b == ';' {
103		w.buf.WriteByte(' ')
104	}
105}
106
107func (w *typeWriter) string(s string) {
108	w.buf.WriteString(s)
109}
110
111func (w *typeWriter) error(msg string) {
112	if w.ctxt != nil {
113		panic(msg)
114	}
115	w.buf.WriteString("<" + msg + ">")
116}
117
118func (w *typeWriter) typ(typ Type) {
119	if w.seen[typ] {
120		w.error("cycle to " + goTypeName(typ))
121		return
122	}
123	w.seen[typ] = true
124	defer delete(w.seen, typ)
125
126	switch t := typ.(type) {
127	case nil:
128		w.error("nil")
129
130	case *Basic:
131		// exported basic types go into package unsafe
132		// (currently this is just unsafe.Pointer)
133		if isExported(t.name) {
134			if obj, _ := Unsafe.scope.Lookup(t.name).(*TypeName); obj != nil {
135				w.typeName(obj)
136				break
137			}
138		}
139		w.string(t.name)
140
141	case *Array:
142		w.byte('[')
143		w.string(strconv.FormatInt(t.len, 10))
144		w.byte(']')
145		w.typ(t.elem)
146
147	case *Slice:
148		w.string("[]")
149		w.typ(t.elem)
150
151	case *Struct:
152		w.string("struct{")
153		for i, f := range t.fields {
154			if i > 0 {
155				w.byte(';')
156			}
157			// This doesn't do the right thing for embedded type
158			// aliases where we should print the alias name, not
159			// the aliased type (see issue #44410).
160			if !f.embedded {
161				w.string(f.name)
162				w.byte(' ')
163			}
164			w.typ(f.typ)
165			if tag := t.Tag(i); tag != "" {
166				w.byte(' ')
167				// TODO(gri) If tag contains blanks, replacing them with '#'
168				//           in Context.TypeHash may produce another tag
169				//           accidentally.
170				w.string(strconv.Quote(tag))
171			}
172		}
173		w.byte('}')
174
175	case *Pointer:
176		w.byte('*')
177		w.typ(t.base)
178
179	case *Tuple:
180		w.tuple(t, false)
181
182	case *Signature:
183		w.string("func")
184		w.signature(t)
185
186	case *Union:
187		// Unions only appear as (syntactic) embedded elements
188		// in interfaces and syntactically cannot be empty.
189		if t.Len() == 0 {
190			w.error("empty union")
191			break
192		}
193		for i, t := range t.terms {
194			if i > 0 {
195				w.byte('|')
196			}
197			if t.tilde {
198				w.byte('~')
199			}
200			w.typ(t.typ)
201		}
202
203	case *Interface:
204		if t == universeAny.Type() && w.ctxt == nil {
205			// When not hashing, we can try to improve type strings by writing "any"
206			// for a type that is pointer-identical to universeAny. This logic should
207			// be deprecated by more robust handling for aliases.
208			w.string("any")
209			break
210		}
211		if t.implicit {
212			if len(t.methods) == 0 && len(t.embeddeds) == 1 {
213				w.typ(t.embeddeds[0])
214				break
215			}
216			// Something's wrong with the implicit interface.
217			// Print it as such and continue.
218			w.string("/* implicit */ ")
219		}
220		w.string("interface{")
221		first := true
222		if w.ctxt != nil {
223			w.typeSet(t.typeSet())
224		} else {
225			for _, m := range t.methods {
226				if !first {
227					w.byte(';')
228				}
229				first = false
230				w.string(m.name)
231				w.signature(m.typ.(*Signature))
232			}
233			for _, typ := range t.embeddeds {
234				if !first {
235					w.byte(';')
236				}
237				first = false
238				w.typ(typ)
239			}
240		}
241		w.byte('}')
242
243	case *Map:
244		w.string("map[")
245		w.typ(t.key)
246		w.byte(']')
247		w.typ(t.elem)
248
249	case *Chan:
250		var s string
251		var parens bool
252		switch t.dir {
253		case SendRecv:
254			s = "chan "
255			// chan (<-chan T) requires parentheses
256			if c, _ := t.elem.(*Chan); c != nil && c.dir == RecvOnly {
257				parens = true
258			}
259		case SendOnly:
260			s = "chan<- "
261		case RecvOnly:
262			s = "<-chan "
263		default:
264			w.error("unknown channel direction")
265		}
266		w.string(s)
267		if parens {
268			w.byte('(')
269		}
270		w.typ(t.elem)
271		if parens {
272			w.byte(')')
273		}
274
275	case *Named:
276		// If hashing, write a unique prefix for t to represent its identity, since
277		// named type identity is pointer identity.
278		if w.ctxt != nil {
279			w.string(strconv.Itoa(w.ctxt.getID(t)))
280		}
281		w.typeName(t.obj) // when hashing written for readability of the hash only
282		if t.targs != nil {
283			// instantiated type
284			w.typeList(t.targs.list())
285		} else if w.ctxt == nil && t.TypeParams().Len() != 0 { // For type hashing, don't need to format the TypeParams
286			// parameterized type
287			w.tParamList(t.TypeParams().list())
288		}
289
290	case *TypeParam:
291		if t.obj == nil {
292			w.error("unnamed type parameter")
293			break
294		}
295		if i := tparamIndex(w.tparams.list(), t); i >= 0 {
296			// The names of type parameters that are declared by the type being
297			// hashed are not part of the type identity. Replace them with a
298			// placeholder indicating their index.
299			w.string(fmt.Sprintf("$%d", i))
300		} else {
301			w.string(t.obj.name)
302			if w.debug || w.ctxt != nil {
303				w.string(subscript(t.id))
304			}
305		}
306
307	default:
308		// For externally defined implementations of Type.
309		// Note: In this case cycles won't be caught.
310		w.string(t.String())
311	}
312}
313
314// typeSet writes a canonical hash for an interface type set.
315func (w *typeWriter) typeSet(s *_TypeSet) {
316	assert(w.ctxt != nil)
317	first := true
318	for _, m := range s.methods {
319		if !first {
320			w.byte(';')
321		}
322		first = false
323		w.string(m.name)
324		w.signature(m.typ.(*Signature))
325	}
326	switch {
327	case s.terms.isAll():
328		// nothing to do
329	case s.terms.isEmpty():
330		w.string(s.terms.String())
331	default:
332		var termHashes []string
333		for _, term := range s.terms {
334			// terms are not canonically sorted, so we sort their hashes instead.
335			var buf bytes.Buffer
336			if term.tilde {
337				buf.WriteByte('~')
338			}
339			newTypeHasher(&buf, w.ctxt).typ(term.typ)
340			termHashes = append(termHashes, buf.String())
341		}
342		sort.Strings(termHashes)
343		if !first {
344			w.byte(';')
345		}
346		w.string(strings.Join(termHashes, "|"))
347	}
348}
349
350func (w *typeWriter) typeList(list []Type) {
351	w.byte('[')
352	for i, typ := range list {
353		if i > 0 {
354			w.byte(',')
355		}
356		w.typ(typ)
357	}
358	w.byte(']')
359}
360
361func (w *typeWriter) tParamList(list []*TypeParam) {
362	w.byte('[')
363	var prev Type
364	for i, tpar := range list {
365		// Determine the type parameter and its constraint.
366		// list is expected to hold type parameter names,
367		// but don't crash if that's not the case.
368		if tpar == nil {
369			w.error("nil type parameter")
370			continue
371		}
372		if i > 0 {
373			if tpar.bound != prev {
374				// bound changed - write previous one before advancing
375				w.byte(' ')
376				w.typ(prev)
377			}
378			w.byte(',')
379		}
380		prev = tpar.bound
381		w.typ(tpar)
382	}
383	if prev != nil {
384		w.byte(' ')
385		w.typ(prev)
386	}
387	w.byte(']')
388}
389
390func (w *typeWriter) typeName(obj *TypeName) {
391	if obj.pkg != nil {
392		writePackage(w.buf, obj.pkg, w.qf)
393	}
394	w.string(obj.name)
395}
396
397func (w *typeWriter) tuple(tup *Tuple, variadic bool) {
398	w.byte('(')
399	if tup != nil {
400		for i, v := range tup.vars {
401			if i > 0 {
402				w.byte(',')
403			}
404			// parameter names are ignored for type identity and thus type hashes
405			if w.ctxt == nil && v.name != "" {
406				w.string(v.name)
407				w.byte(' ')
408			}
409			typ := v.typ
410			if variadic && i == len(tup.vars)-1 {
411				if s, ok := typ.(*Slice); ok {
412					w.string("...")
413					typ = s.elem
414				} else {
415					// special case:
416					// append(s, "foo"...) leads to signature func([]byte, string...)
417					if t, _ := under(typ).(*Basic); t == nil || t.kind != String {
418						w.error("expected string type")
419						continue
420					}
421					w.typ(typ)
422					w.string("...")
423					continue
424				}
425			}
426			w.typ(typ)
427		}
428	}
429	w.byte(')')
430}
431
432func (w *typeWriter) signature(sig *Signature) {
433	if sig.TypeParams().Len() != 0 {
434		if w.ctxt != nil {
435			assert(w.tparams == nil)
436			w.tparams = sig.TypeParams()
437			defer func() {
438				w.tparams = nil
439			}()
440		}
441		w.tParamList(sig.TypeParams().list())
442	}
443
444	w.tuple(sig.params, sig.variadic)
445
446	n := sig.results.Len()
447	if n == 0 {
448		// no result
449		return
450	}
451
452	w.byte(' ')
453	if n == 1 && (w.ctxt != nil || sig.results.vars[0].name == "") {
454		// single unnamed result (if type hashing, name must be ignored)
455		w.typ(sig.results.vars[0].typ)
456		return
457	}
458
459	// multiple or named result(s)
460	w.tuple(sig.results, false)
461}
462
463// subscript returns the decimal (utf8) representation of x using subscript digits.
464func subscript(x uint64) string {
465	const w = len("₀") // all digits 0...9 have the same utf8 width
466	var buf [32 * w]byte
467	i := len(buf)
468	for {
469		i -= w
470		utf8.EncodeRune(buf[i:], '₀'+rune(x%10)) // '₀' == U+2080
471		x /= 10
472		if x == 0 {
473			break
474		}
475	}
476	return string(buf[i:])
477}
478