import (
"bytes"
"fmt"
+ "sort"
+ "strconv"
+ "strings"
"unicode/utf8"
)
//
// Using a nil Qualifier is equivalent to using (*Package).Path: the
// object is qualified by the import path, e.g., "encoding/json.Marshal".
-//
type Qualifier func(*Package) string
// RelativeTo returns a Qualifier that fully qualifies members of
}
}
-// If gcCompatibilityMode is set, printing of types is modified
-// to match the representation of some types in the gc compiler:
-//
-// - byte and rune lose their alias name and simply stand for
-// uint8 and int32 respectively
-// - embedded interfaces get flattened (the embedding info is lost,
-// and certain recursive interface types cannot be printed anymore)
-//
-// This makes it easier to compare packages computed with the type-
-// checker vs packages imported from gc export data.
-//
-// Caution: This flag affects all uses of WriteType, globally.
-// It is only provided for testing in conjunction with
-// gc-generated data.
-//
-// This flag is exported in the x/tools/go/types package. We don't
-// need it at the moment in the std repo and so we don't export it
-// anymore. We should eventually try to remove it altogether.
-// TODO(gri) remove this
-var gcCompatibilityMode bool
-
// TypeString returns the string representation of typ.
// The Qualifier controls the printing of
// package-level objects, and may be nil.
// The Qualifier controls the printing of
// package-level objects, and may be nil.
func WriteType(buf *bytes.Buffer, typ Type, qf Qualifier) {
- writeType(buf, typ, qf, make([]Type, 0, 8))
+ newTypeWriter(buf, qf).typ(typ)
+}
+
+// WriteSignature writes the representation of the signature sig to buf,
+// without a leading "func" keyword. The Qualifier controls the printing
+// of package-level objects, and may be nil.
+func WriteSignature(buf *bytes.Buffer, sig *Signature, qf Qualifier) {
+ newTypeWriter(buf, qf).signature(sig)
}
-// instanceMarker is the prefix for an instantiated type
-// in "non-evaluated" instance form.
-const instanceMarker = '#'
-
-func writeType(buf *bytes.Buffer, typ Type, qf Qualifier, visited []Type) {
- // Theoretically, this is a quadratic lookup algorithm, but in
- // practice deeply nested composite types with unnamed component
- // types are uncommon. This code is likely more efficient than
- // using a map.
- for _, t := range visited {
- if t == typ {
- fmt.Fprintf(buf, "○%T", goTypeName(typ)) // cycle to typ
- return
+type typeWriter struct {
+ buf *bytes.Buffer
+ seen map[Type]bool
+ qf Qualifier
+ ctxt *Context // if non-nil, we are type hashing
+ tparams *TypeParamList // local type parameters
+ paramNames bool // if set, write function parameter names, otherwise, write types only
+ tpSubscripts bool // if set, write type parameter indices as subscripts
+ pkgInfo bool // package-annotate first unexported-type field to avoid confusing type description
+}
+
+func newTypeWriter(buf *bytes.Buffer, qf Qualifier) *typeWriter {
+ return &typeWriter{buf, make(map[Type]bool), qf, nil, nil, true, false, false}
+}
+
+func newTypeHasher(buf *bytes.Buffer, ctxt *Context) *typeWriter {
+ assert(ctxt != nil)
+ return &typeWriter{buf, make(map[Type]bool), nil, ctxt, nil, false, false, false}
+}
+
+func (w *typeWriter) byte(b byte) {
+ if w.ctxt != nil {
+ if b == ' ' {
+ b = '#'
}
+ w.buf.WriteByte(b)
+ return
+ }
+ w.buf.WriteByte(b)
+ if b == ',' || b == ';' {
+ w.buf.WriteByte(' ')
+ }
+}
+
+func (w *typeWriter) string(s string) {
+ w.buf.WriteString(s)
+}
+
+func (w *typeWriter) error(msg string) {
+ if w.ctxt != nil {
+ panic(msg)
+ }
+ w.buf.WriteString("<" + msg + ">")
+}
+
+func (w *typeWriter) typ(typ Type) {
+ if w.seen[typ] {
+ w.error("cycle to " + goTypeName(typ))
+ return
}
- visited = append(visited, typ)
+ w.seen[typ] = true
+ defer delete(w.seen, typ)
switch t := typ.(type) {
case nil:
- buf.WriteString("<nil>")
+ w.error("nil")
case *Basic:
// exported basic types go into package unsafe
// (currently this is just unsafe.Pointer)
if isExported(t.name) {
if obj, _ := Unsafe.scope.Lookup(t.name).(*TypeName); obj != nil {
- writeTypeName(buf, obj, qf)
+ w.typeName(obj)
break
}
}
-
- if gcCompatibilityMode {
- // forget the alias names
- switch t.kind {
- case Byte:
- t = Typ[Uint8]
- case Rune:
- t = Typ[Int32]
- }
- }
- buf.WriteString(t.name)
+ w.string(t.name)
case *Array:
- fmt.Fprintf(buf, "[%d]", t.len)
- writeType(buf, t.elem, qf, visited)
+ w.byte('[')
+ w.string(strconv.FormatInt(t.len, 10))
+ w.byte(']')
+ w.typ(t.elem)
case *Slice:
- buf.WriteString("[]")
- writeType(buf, t.elem, qf, visited)
+ w.string("[]")
+ w.typ(t.elem)
case *Struct:
- buf.WriteString("struct{")
+ w.string("struct{")
for i, f := range t.fields {
if i > 0 {
- buf.WriteString("; ")
+ w.byte(';')
}
+
+ // If disambiguating one struct for another, look for the first unexported field.
+ // Do this first in case of nested structs; tag the first-outermost field.
+ pkgAnnotate := false
+ if w.qf == nil && w.pkgInfo && !isExported(f.name) {
+ // note for embedded types, type name is field name, and "string" etc are lower case hence unexported.
+ pkgAnnotate = true
+ w.pkgInfo = false // only tag once
+ }
+
// This doesn't do the right thing for embedded type
// aliases where we should print the alias name, not
- // the aliased type (see issue #44410).
+ // the aliased type (see go.dev/issue/44410).
if !f.embedded {
- buf.WriteString(f.name)
- buf.WriteByte(' ')
+ w.string(f.name)
+ w.byte(' ')
+ }
+ w.typ(f.typ)
+ if pkgAnnotate {
+ w.string(" /* package ")
+ w.string(f.pkg.Path())
+ w.string(" */ ")
}
- writeType(buf, f.typ, qf, visited)
if tag := t.Tag(i); tag != "" {
- fmt.Fprintf(buf, " %q", tag)
+ w.byte(' ')
+ // TODO(gri) If tag contains blanks, replacing them with '#'
+ // in Context.TypeHash may produce another tag
+ // accidentally.
+ w.string(strconv.Quote(tag))
}
}
- buf.WriteByte('}')
+ w.byte('}')
case *Pointer:
- buf.WriteByte('*')
- writeType(buf, t.base, qf, visited)
+ w.byte('*')
+ w.typ(t.base)
case *Tuple:
- writeTuple(buf, t, false, qf, visited)
+ w.tuple(t, false)
case *Signature:
- buf.WriteString("func")
- writeSignature(buf, t, qf, visited)
-
- case *Sum:
- for i, t := range t.types {
+ w.string("func")
+ w.signature(t)
+
+ case *Union:
+ // Unions only appear as (syntactic) embedded elements
+ // in interfaces and syntactically cannot be empty.
+ if t.Len() == 0 {
+ w.error("empty union")
+ break
+ }
+ for i, t := range t.terms {
if i > 0 {
- buf.WriteString(", ")
+ w.string(termSep)
+ }
+ if t.tilde {
+ w.byte('~')
}
- writeType(buf, t, qf, visited)
+ w.typ(t.typ)
}
case *Interface:
- // We write the source-level methods and embedded types rather
- // than the actual method set since resolved method signatures
- // may have non-printable cycles if parameters have embedded
- // interface types that (directly or indirectly) embed the
- // current interface. For instance, consider the result type
- // of m:
- //
- // type T interface{
- // m() interface{ T }
- // }
- //
- buf.WriteString("interface{")
- empty := true
- if gcCompatibilityMode {
- // print flattened interface
- // (useful to compare against gc-generated interfaces)
- for i, m := range t.allMethods {
- if i > 0 {
- buf.WriteString("; ")
- }
- buf.WriteString(m.name)
- writeSignature(buf, m.typ.(*Signature), qf, visited)
- empty = false
+ if w.ctxt == nil {
+ if t == universeAny.Type() {
+ // When not hashing, we can try to improve type strings by writing "any"
+ // for a type that is pointer-identical to universeAny. This logic should
+ // be deprecated by more robust handling for aliases.
+ w.string("any")
+ break
}
- if !empty && t.allTypes != nil {
- buf.WriteString("; ")
+ if t == asNamed(universeComparable.Type()).underlying {
+ w.string("interface{comparable}")
+ break
}
- if t.allTypes != nil {
- buf.WriteString("type ")
- writeType(buf, t.allTypes, qf, visited)
+ }
+ if t.implicit {
+ if len(t.methods) == 0 && len(t.embeddeds) == 1 {
+ w.typ(t.embeddeds[0])
+ break
}
+ // Something's wrong with the implicit interface.
+ // Print it as such and continue.
+ w.string("/* implicit */ ")
+ }
+ w.string("interface{")
+ first := true
+ if w.ctxt != nil {
+ w.typeSet(t.typeSet())
} else {
- // print explicit interface methods and embedded types
- for i, m := range t.methods {
- if i > 0 {
- buf.WriteString("; ")
+ for _, m := range t.methods {
+ if !first {
+ w.byte(';')
}
- buf.WriteString(m.name)
- writeSignature(buf, m.typ.(*Signature), qf, visited)
- empty = false
- }
- if !empty && t.types != nil {
- buf.WriteString("; ")
+ first = false
+ w.string(m.name)
+ w.signature(m.typ.(*Signature))
}
- if t.types != nil {
- buf.WriteString("type ")
- writeType(buf, t.types, qf, visited)
- empty = false
- }
- if !empty && len(t.embeddeds) > 0 {
- buf.WriteString("; ")
- }
- for i, typ := range t.embeddeds {
- if i > 0 {
- buf.WriteString("; ")
+ for _, typ := range t.embeddeds {
+ if !first {
+ w.byte(';')
}
- writeType(buf, typ, qf, visited)
- empty = false
+ first = false
+ w.typ(typ)
}
}
- if debug && (t.allMethods == nil || len(t.methods) > len(t.allMethods)) {
- if !empty {
- buf.WriteByte(' ')
- }
- buf.WriteString("/* incomplete */")
- }
- buf.WriteByte('}')
+ w.byte('}')
case *Map:
- buf.WriteString("map[")
- writeType(buf, t.key, qf, visited)
- buf.WriteByte(']')
- writeType(buf, t.elem, qf, visited)
+ w.string("map[")
+ w.typ(t.key)
+ w.byte(']')
+ w.typ(t.elem)
case *Chan:
var s string
case RecvOnly:
s = "<-chan "
default:
- panic("unreachable")
+ w.error("unknown channel direction")
}
- buf.WriteString(s)
+ w.string(s)
if parens {
- buf.WriteByte('(')
+ w.byte('(')
}
- writeType(buf, t.elem, qf, visited)
+ w.typ(t.elem)
if parens {
- buf.WriteByte(')')
+ w.byte(')')
}
case *Named:
- writeTypeName(buf, t.obj, qf)
- if t.targs != nil {
+ // If hashing, write a unique prefix for t to represent its identity, since
+ // named type identity is pointer identity.
+ if w.ctxt != nil {
+ w.string(strconv.Itoa(w.ctxt.getID(t)))
+ }
+ w.typeName(t.obj) // when hashing written for readability of the hash only
+ if t.inst != nil {
// instantiated type
- buf.WriteByte('[')
- writeTypeList(buf, t.targs, qf, visited)
- buf.WriteByte(']')
- } else if t.tparams != nil {
+ w.typeList(t.inst.targs.list())
+ } else if w.ctxt == nil && t.TypeParams().Len() != 0 { // For type hashing, don't need to format the TypeParams
// parameterized type
- writeTParamList(buf, t.tparams, qf, visited)
+ w.tParamList(t.TypeParams().list())
}
case *TypeParam:
- s := "?"
- if t.obj != nil {
- // Optionally write out package for typeparams (like Named).
- // TODO(danscales): this is required for import/export, so
- // we maybe need a separate function that won't be changed
- // for debugging purposes.
- if t.obj.pkg != nil {
- writePackage(buf, t.obj.pkg, qf)
+ if t.obj == nil {
+ w.error("unnamed type parameter")
+ break
+ }
+ if i := tparamIndex(w.tparams.list(), t); i >= 0 {
+ // The names of type parameters that are declared by the type being
+ // hashed are not part of the type identity. Replace them with a
+ // placeholder indicating their index.
+ w.string(fmt.Sprintf("$%d", i))
+ } else {
+ w.string(t.obj.name)
+ if w.tpSubscripts || w.ctxt != nil {
+ w.string(subscript(t.id))
+ }
+ // If the type parameter name is the same as a predeclared object
+ // (say int), point out where it is declared to avoid confusing
+ // error messages. This doesn't need to be super-elegant; we just
+ // need a clear indication that this is not a predeclared name.
+ if w.ctxt == nil && Universe.Lookup(t.obj.name) != nil {
+ w.string(fmt.Sprintf(" /* with %s declared at %s */", t.obj.name, t.obj.Pos()))
}
- s = t.obj.name
}
- buf.WriteString(s + subscript(t.id))
-
- case *instance:
- buf.WriteByte(instanceMarker) // indicate "non-evaluated" syntactic instance
- writeTypeName(buf, t.base.obj, qf)
- buf.WriteByte('[')
- writeTypeList(buf, t.targs, qf, visited)
- buf.WriteByte(']')
- case *bottom:
- buf.WriteString("⊥")
-
- case *top:
- buf.WriteString("⊤")
+ case *_Alias:
+ w.typeName(t.obj)
+ if w.ctxt != nil {
+ // TODO(gri) do we need to print the alias type name, too?
+ w.typ(_Unalias(t.obj.typ))
+ } else {
+ w.string(fmt.Sprintf(" /* = %s */", _Unalias(t.obj.typ)))
+ }
default:
// For externally defined implementations of Type.
- buf.WriteString(t.String())
+ // Note: In this case cycles won't be caught.
+ w.string(t.String())
}
}
-func writeTypeList(buf *bytes.Buffer, list []Type, qf Qualifier, visited []Type) {
+// typeSet writes a canonical hash for an interface type set.
+func (w *typeWriter) typeSet(s *_TypeSet) {
+ assert(w.ctxt != nil)
+ first := true
+ for _, m := range s.methods {
+ if !first {
+ w.byte(';')
+ }
+ first = false
+ w.string(m.name)
+ w.signature(m.typ.(*Signature))
+ }
+ switch {
+ case s.terms.isAll():
+ // nothing to do
+ case s.terms.isEmpty():
+ w.string(s.terms.String())
+ default:
+ var termHashes []string
+ for _, term := range s.terms {
+ // terms are not canonically sorted, so we sort their hashes instead.
+ var buf bytes.Buffer
+ if term.tilde {
+ buf.WriteByte('~')
+ }
+ newTypeHasher(&buf, w.ctxt).typ(term.typ)
+ termHashes = append(termHashes, buf.String())
+ }
+ sort.Strings(termHashes)
+ if !first {
+ w.byte(';')
+ }
+ w.string(strings.Join(termHashes, "|"))
+ }
+}
+
+func (w *typeWriter) typeList(list []Type) {
+ w.byte('[')
for i, typ := range list {
if i > 0 {
- buf.WriteString(", ")
+ w.byte(',')
}
- writeType(buf, typ, qf, visited)
+ w.typ(typ)
}
+ w.byte(']')
}
-func writeTParamList(buf *bytes.Buffer, list []*TypeName, qf Qualifier, visited []Type) {
- buf.WriteString("[")
+func (w *typeWriter) tParamList(list []*TypeParam) {
+ w.byte('[')
var prev Type
- for i, p := range list {
- // TODO(gri) support 'any' sugar here.
- var b Type = &emptyInterface
- if t, _ := p.typ.(*TypeParam); t != nil && t.bound != nil {
- b = t.bound
+ for i, tpar := range list {
+ // Determine the type parameter and its constraint.
+ // list is expected to hold type parameter names,
+ // but don't crash if that's not the case.
+ if tpar == nil {
+ w.error("nil type parameter")
+ continue
}
if i > 0 {
- if b != prev {
- // type bound changed - write previous one before advancing
- buf.WriteByte(' ')
- writeType(buf, prev, qf, visited)
+ if tpar.bound != prev {
+ // bound changed - write previous one before advancing
+ w.byte(' ')
+ w.typ(prev)
}
- buf.WriteString(", ")
- }
- prev = b
-
- if t, _ := p.typ.(*TypeParam); t != nil {
- writeType(buf, t, qf, visited)
- } else {
- buf.WriteString(p.name)
+ w.byte(',')
}
+ prev = tpar.bound
+ w.typ(tpar)
}
if prev != nil {
- buf.WriteByte(' ')
- writeType(buf, prev, qf, visited)
+ w.byte(' ')
+ w.typ(prev)
}
- buf.WriteByte(']')
+ w.byte(']')
}
-func writeTypeName(buf *bytes.Buffer, obj *TypeName, qf Qualifier) {
- s := "<Named w/o object>"
- if obj != nil {
- if obj.pkg != nil {
- writePackage(buf, obj.pkg, qf)
- }
- // TODO(gri): function-local named types should be displayed
- // differently from named types at package level to avoid
- // ambiguity.
- s = obj.name
- }
- buf.WriteString(s)
+func (w *typeWriter) typeName(obj *TypeName) {
+ w.string(packagePrefix(obj.pkg, w.qf))
+ w.string(obj.name)
}
-func writeTuple(buf *bytes.Buffer, tup *Tuple, variadic bool, qf Qualifier, visited []Type) {
- buf.WriteByte('(')
+func (w *typeWriter) tuple(tup *Tuple, variadic bool) {
+ w.byte('(')
if tup != nil {
for i, v := range tup.vars {
if i > 0 {
- buf.WriteString(", ")
+ w.byte(',')
}
- if v.name != "" {
- buf.WriteString(v.name)
- buf.WriteByte(' ')
+ // parameter names are ignored for type identity and thus type hashes
+ if w.ctxt == nil && v.name != "" && w.paramNames {
+ w.string(v.name)
+ w.byte(' ')
}
typ := v.typ
if variadic && i == len(tup.vars)-1 {
if s, ok := typ.(*Slice); ok {
- buf.WriteString("...")
+ w.string("...")
typ = s.elem
} else {
// special case:
// append(s, "foo"...) leads to signature func([]byte, string...)
- if t := asBasic(typ); t == nil || t.kind != String {
- panic("internal error: string type expected")
+ if t, _ := under(typ).(*Basic); t == nil || t.kind != String {
+ w.error("expected string type")
+ continue
}
- writeType(buf, typ, qf, visited)
- buf.WriteString("...")
+ w.typ(typ)
+ w.string("...")
continue
}
}
- writeType(buf, typ, qf, visited)
+ w.typ(typ)
}
}
- buf.WriteByte(')')
+ w.byte(')')
}
-// WriteSignature writes the representation of the signature sig to buf,
-// without a leading "func" keyword.
-// The Qualifier controls the printing of
-// package-level objects, and may be nil.
-func WriteSignature(buf *bytes.Buffer, sig *Signature, qf Qualifier) {
- writeSignature(buf, sig, qf, make([]Type, 0, 8))
-}
-
-func writeSignature(buf *bytes.Buffer, sig *Signature, qf Qualifier, visited []Type) {
- if sig.tparams != nil {
- writeTParamList(buf, sig.tparams, qf, visited)
+func (w *typeWriter) signature(sig *Signature) {
+ if sig.TypeParams().Len() != 0 {
+ if w.ctxt != nil {
+ assert(w.tparams == nil)
+ w.tparams = sig.TypeParams()
+ defer func() {
+ w.tparams = nil
+ }()
+ }
+ w.tParamList(sig.TypeParams().list())
}
- writeTuple(buf, sig.params, sig.variadic, qf, visited)
+ w.tuple(sig.params, sig.variadic)
n := sig.results.Len()
if n == 0 {
return
}
- buf.WriteByte(' ')
- if n == 1 && sig.results.vars[0].name == "" {
- // single unnamed result
- writeType(buf, sig.results.vars[0].typ, qf, visited)
+ w.byte(' ')
+ if n == 1 && (w.ctxt != nil || sig.results.vars[0].name == "") {
+ // single unnamed result (if type hashing, name must be ignored)
+ w.typ(sig.results.vars[0].typ)
return
}
// multiple or named result(s)
- writeTuple(buf, sig.results, false, qf, visited)
+ w.tuple(sig.results, false)
}
// subscript returns the decimal (utf8) representation of x using subscript digits.