gopls/internal/lsp/source/methodsets/methodsets.go - tools - Git at Google

 // Copyright 2023 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 // Package methodsets defines an incremental, serializable index of
 // method-set information that allows efficient 'implements' queries
 // across packages of the workspace without using the type checker.
 //
 // This package provides only the "global" (all workspace) search; the
 // "local" search within a given package uses a different
 // implementation based on type-checker data structures for a single
 // package plus variants; see ../implementation2.go.
 // The local algorithm is more precise as it tests function-local types too.
 //
 // A global index of function-local types is challenging since they
 // may reference other local types, for which we would need to invent
 // stable names, an unsolved problem described in passing in Go issue
 // 57497. The global algorithm also does not index anonymous interface
 // types, even outside function bodies.
 //
 // Consequently, global results are not symmetric: applying the
 // operation twice may not get you back where you started.
 package methodsets

 // DESIGN
 //
 // See https://go.dev/cl/452060 for a minimal exposition of the algorithm.
 //
 // For each method, we compute a fingerprint: a string representing
 // the method name and type such that equal fingerprint strings mean
 // identical method types.
 //
 // For efficiency, the fingerprint is reduced to a single bit
 // of a uint64, so that the method set can be represented as
 // the union of those method bits (a uint64 bitmask).
 // Assignability thus reduces to a subset check on bitmasks
 // followed by equality checks on fingerprints.
 //
 // In earlier experiments, using 128-bit masks instead of 64 reduced
 // the number of candidates by about 2x. Using (like a Bloom filter) a
 // different hash function to compute a second 64-bit mask and
 // performing a second mask test reduced it by about 4x.
 // Neither had much effect on the running time, presumably because a
 // single 64-bit mask is quite effective. See CL 452060 for details.

 import (
 	"fmt"
 	"go/token"
 	"go/types"
 	"hash/crc32"
 	"strconv"
 	"strings"

 	"golang.org/x/tools/gopls/internal/lsp/safetoken"
 	"golang.org/x/tools/internal/typeparams"
 )

 // An Index records the non-empty method sets of all package-level
 // types in a package in a form that permits assignability queries
 // without the type checker.
 type Index struct {
 	pkg gobPackage
 }

 // NewIndex returns a new index of method-set information for all
 // package-level types in the specified package.
 func NewIndex(fset *token.FileSet, pkg *types.Package) *Index {
 	return new(indexBuilder).build(fset, pkg)
 }

 // A Location records the extent of an identifier in byte-offset form.
 //
 // Conversion to protocol (UTF-16) form is done by the caller after a
 // search, not during index construction.
 // TODO(adonovan): opt: reconsider this choice, if FileHandles, not
 // ParsedGoFiles were to provide ColumnMapper-like functionality.
 // (Column mapping is currently associated with parsing,
 // but non-parsed and even non-Go files need it too.)
 // Since type checking requires reading (but not parsing) all
 // dependencies' Go files, we could do the conversion at type-checking
 // time at little extra cost in that case.
 type Location struct {
 	Filename   string
 	Start, End int // byte offsets
 }

 // A Key represents the method set of a given type in a form suitable
 // to pass to the (*Index).Search method of many different Indexes.
 type Key struct {
 	mset gobMethodSet // note: lacks position information
 }

 // KeyOf returns the search key for the method sets of a given type.
 // It returns false if the type has no methods.
 func KeyOf(t types.Type) (Key, bool) {
 	mset := methodSetInfo(func(types.Object) (_ gobPosition) { return }, t, gobPosition{})
 	if mset.Mask == 0 {
 		return Key{}, false // no methods
 	}
 	return Key{mset}, true
 }

 // Search reports each type that implements (or is implemented by) the
 // type that produced the search key. If methodID is nonempty, only
 // that method of each type is reported.
 // The result is the location of each type or method.
 func (index *Index) Search(key Key, methodID string) []Location {
 	var locs []Location
 	for _, candidate := range index.pkg.MethodSets {
 		// Traditionally this feature doesn't report
 		// interface/interface elements of the relation.
 		// I think that's a mistake.
 		// TODO(adonovan): UX: change it, here and in the local implementation.
 		if candidate.IsInterface && key.mset.IsInterface {
 			continue
 		}
 		if !satisfies(candidate, key.mset) && !satisfies(key.mset, candidate) {
 			continue
 		}

 		if candidate.Tricky {
 			// If any interface method is tricky then extra
 			// checking may be needed to eliminate a false positive.
 			// TODO(adonovan): implement it.
 		}

 		if methodID == "" {
 			locs = append(locs, index.location(candidate.Posn))
 		} else {
 			for _, m := range candidate.Methods {
 				// Here we exploit knowledge of the shape of the fingerprint string.
 				if strings.HasPrefix(m.Fingerprint, methodID) &&
 					m.Fingerprint[len(methodID)] == '(' {
 					locs = append(locs, index.location(m.Posn))
 					break
 				}
 			}
 		}
 	}
 	return locs
 }

 // satisfies does a fast check for whether x satisfies y.
 func satisfies(x, y gobMethodSet) bool {
 	return y.IsInterface && x.Mask&y.Mask == y.Mask && subset(y, x)
 }

 // subset reports whether method set x is a subset of y.
 func subset(x, y gobMethodSet) bool {
 outer:
 	for _, mx := range x.Methods {
 		for _, my := range y.Methods {
 			if mx.Sum == my.Sum && mx.Fingerprint == my.Fingerprint {
 				continue outer // found; try next x method
 			}
 		}
 		return false // method of x not found in y
 	}
 	return true // all methods of x found in y
 }

 func (index *Index) location(posn gobPosition) Location {
 	return Location{
 		Filename: index.pkg.Filenames[posn.File],
 		Start:    posn.Offset,
 		End:      posn.Offset + posn.Len,
 	}
 }

 // An indexBuilder builds an index for a single package.
 type indexBuilder struct {
 	gobPackage
 	filenameIndex map[string]int
 }

 // build adds to the index all package-level named types of the specified package.
 func (b *indexBuilder) build(fset *token.FileSet, pkg *types.Package) *Index {
 	// We ignore aliases, though in principle they could define a
 	// struct{...}  or interface{...} type, or an instantiation of
 	// a generic, that has a novel method set.
 	scope := pkg.Scope()
 	for _, name := range scope.Names() {
 		if tname, ok := scope.Lookup(name).(*types.TypeName); ok && !tname.IsAlias() {
 			b.add(fset, tname)
 		}
 	}

 	return &Index{pkg: b.gobPackage}
 }

 func (b *indexBuilder) add(fset *token.FileSet, tname *types.TypeName) {
 	objectPos := func(obj types.Object) gobPosition {
 		posn := safetoken.StartPosition(fset, obj.Pos())
 		return gobPosition{b.fileIndex(posn.Filename), posn.Offset, len(obj.Name())}
 	}
 	if mset := methodSetInfo(objectPos, tname.Type(), objectPos(tname)); mset.Mask != 0 {
 		// Only record types with non-trivial method sets.
 		b.MethodSets = append(b.MethodSets, mset)
 	}
 }

 // fileIndex returns a small integer that encodes the file name.
 func (b *indexBuilder) fileIndex(filename string) int {
 	i, ok := b.filenameIndex[filename]
 	if !ok {
 		i = len(b.Filenames)
 		if b.filenameIndex == nil {
 			b.filenameIndex = make(map[string]int)
 		}
 		b.filenameIndex[filename] = i
 		b.Filenames = append(b.Filenames, filename)
 	}
 	return i
 }

 // methodSetInfo returns the method-set fingerprint
 // of a type and records its position (typePosn)
 // and the position of each of its methods m,
 // as provided by objectPos(m).
 func methodSetInfo(objectPos func(types.Object) gobPosition, t types.Type, typePosn gobPosition) gobMethodSet {
 	// For non-interface types, use *T
 	// (if T is not already a pointer)
 	// since it may have more methods.
 	mset := types.NewMethodSet(EnsurePointer(t))

 	// Convert the method set into a compact summary.
 	var mask uint64
 	tricky := false
 	methods := make([]gobMethod, mset.Len())
 	for i := 0; i < mset.Len(); i++ {
 		m := mset.At(i).Obj().(*types.Func)
 		fp, isTricky := fingerprint(m)
 		if isTricky {
 			tricky = true
 		}
 		sum := crc32.ChecksumIEEE([]byte(fp))
 		methods[i] = gobMethod{fp, sum, objectPos(m)}
 		mask |= 1 << uint64(((sum>>24)^(sum>>16)^(sum>>8)^sum)&0x3f)
 	}
 	return gobMethodSet{typePosn, types.IsInterface(t), tricky, mask, methods}
 }

 // EnsurePointer wraps T in a types.Pointer if T is a named, non-interface type.
 // This is useful to make sure you consider a named type's full method set.
 func EnsurePointer(T types.Type) types.Type {
 	if _, ok := T.(*types.Named); ok && !types.IsInterface(T) {
 		return types.NewPointer(T)
 	}

 	return T
 }

 // fingerprint returns an encoding of a method signature such that two
 // methods with equal encodings have identical types, except for a few
 // tricky types whose encodings may spuriously match and whose exact
 // identity computation requires the type checker to eliminate false
 // positives (which are rare). The boolean result indicates whether
 // the result was one of these tricky types.
 //
 // In the standard library, 99.8% of package-level types have a
 // non-tricky method-set.  The most common exceptions are due to type
 // parameters.
 //
 // The fingerprint string starts with method.Id() + "(".
 func fingerprint(method *types.Func) (string, bool) {
 	var buf strings.Builder
 	tricky := false
 	var fprint func(t types.Type)
 	fprint = func(t types.Type) {
 		switch t := t.(type) {
 		case *types.Named:
 			tname := t.Obj()
 			if tname.Pkg() != nil {
 				buf.WriteString(strconv.Quote(tname.Pkg().Path()))
 				buf.WriteByte('.')
 			} else if tname.Name() != "error" {
 				panic(tname) // error is the only named type with no package
 			}
 			buf.WriteString(tname.Name())

 		case *types.Array:
 			fmt.Fprintf(&buf, "[%d]", t.Len())
 			fprint(t.Elem())

 		case *types.Slice:
 			buf.WriteString("[]")
 			fprint(t.Elem())

 		case *types.Pointer:
 			buf.WriteByte('*')
 			fprint(t.Elem())

 		case *types.Map:
 			buf.WriteString("map[")
 			fprint(t.Key())
 			buf.WriteByte(']')
 			fprint(t.Elem())

 		case *types.Chan:
 			switch t.Dir() {
 			case types.SendRecv:
 				buf.WriteString("chan ")
 			case types.SendOnly:
 				buf.WriteString("<-chan ")
 			case types.RecvOnly:
 				buf.WriteString("chan<- ")
 			}
 			fprint(t.Elem())

 		case *types.Tuple:
 			buf.WriteByte('(')
 			for i := 0; i < t.Len(); i++ {
 				if i > 0 {
 					buf.WriteByte(',')
 				}
 				fprint(t.At(i).Type())
 			}
 			buf.WriteByte(')')

 		case *types.Basic:
 			// Use canonical names for uint8 and int32 aliases.
 			switch t.Kind() {
 			case types.Byte:
 				buf.WriteString("byte")
 			case types.Rune:
 				buf.WriteString("rune")
 			default:
 				buf.WriteString(t.String())
 			}

 		case *types.Signature:
 			buf.WriteString("func")
 			fprint(t.Params())
 			if t.Variadic() {
 				buf.WriteString("...") // not quite Go syntax
 			}
 			fprint(t.Results())

 		case *types.Struct:
 			// Non-empty unnamed struct types in method
 			// signatures are vanishingly rare.
 			buf.WriteString("struct{")
 			for i := 0; i < t.NumFields(); i++ {
 				if i > 0 {
 					buf.WriteByte(';')
 				}
 				f := t.Field(i)
 				// This isn't quite right for embedded type aliases.
 				// (See types.TypeString(StructType) and #44410 for context.)
 				// But this is vanishingly rare.
 				if !f.Embedded() {
 					buf.WriteString(f.Id())
 					buf.WriteByte(' ')
 				}
 				fprint(f.Type())
 				if tag := t.Tag(i); tag != "" {
 					buf.WriteByte(' ')
 					buf.WriteString(strconv.Quote(tag))
 				}
 			}
 			buf.WriteString("}")

 		case *types.Interface:
 			if t.NumMethods() == 0 {
 				buf.WriteString("any") // common case
 			} else {
 				// Interface assignability is particularly
 				// tricky due to the possibility of recursion.
 				tricky = true
 				// We could still give more disambiguating precision
 				// than "..." if we wanted to.
 				buf.WriteString("interface{...}")
 			}

 		case *typeparams.TypeParam:
 			tricky = true
 			// TODO(adonovan): refine this by adding a numeric suffix
 			// indicating the index among the receiver type's parameters.
 			buf.WriteByte('?')

 		default: // incl. *types.Union
 			panic(t)
 		}
 	}

 	buf.WriteString(method.Id()) // e.g. "pkg.Type"
 	sig := method.Type().(*types.Signature)
 	fprint(sig.Params())
 	fprint(sig.Results())
 	return buf.String(), tricky
 }

 // -- serial format of index --

 // The cost of gob encoding and decoding for most packages in x/tools
 // is under 50us, with occasional peaks of around 1-3ms.
 // The encoded indexes are around 1KB-50KB.

 // A gobPackage records the method set of each package-level type for a single package.
 type gobPackage struct {
 	Filenames  []string // see gobPosition.File
 	MethodSets []gobMethodSet
 }

 // A gobMethodSet records the method set of a single type.
 type gobMethodSet struct {
 	Posn        gobPosition
 	IsInterface bool
 	Tricky      bool   // at least one method is tricky; assignability requires go/types
 	Mask        uint64 // mask with 1 bit from each of methods[*].sum
 	Methods     []gobMethod
 }

 // A gobMethod records the name, type, and position of a single method.
 type gobMethod struct {
 	Fingerprint string      // string of form "methodID(params...)(results)"
 	Sum         uint32      // checksum of fingerprint
 	Posn        gobPosition // location of method declaration
 }

 // A gobPosition records the file, offset, and length of an identifier.
 type gobPosition struct {
 	File        int // index into Index.filenames
 	Offset, Len int // in bytes
 }
	// Copyright 2023 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	// Package methodsets defines an incremental, serializable index of
	// method-set information that allows efficient 'implements' queries
	// across packages of the workspace without using the type checker.
	//
	// This package provides only the "global" (all workspace) search; the
	// "local" search within a given package uses a different
	// implementation based on type-checker data structures for a single
	// package plus variants; see ../implementation2.go.
	// The local algorithm is more precise as it tests function-local types too.
	//
	// A global index of function-local types is challenging since they
	// may reference other local types, for which we would need to invent
	// stable names, an unsolved problem described in passing in Go issue
	// 57497. The global algorithm also does not index anonymous interface
	// types, even outside function bodies.
	//
	// Consequently, global results are not symmetric: applying the
	// operation twice may not get you back where you started.
	package methodsets

	// DESIGN
	//
	// See https://go.dev/cl/452060 for a minimal exposition of the algorithm.
	//
	// For each method, we compute a fingerprint: a string representing
	// the method name and type such that equal fingerprint strings mean
	// identical method types.
	//
	// For efficiency, the fingerprint is reduced to a single bit
	// of a uint64, so that the method set can be represented as
	// the union of those method bits (a uint64 bitmask).
	// Assignability thus reduces to a subset check on bitmasks
	// followed by equality checks on fingerprints.
	//
	// In earlier experiments, using 128-bit masks instead of 64 reduced
	// the number of candidates by about 2x. Using (like a Bloom filter) a
	// different hash function to compute a second 64-bit mask and
	// performing a second mask test reduced it by about 4x.
	// Neither had much effect on the running time, presumably because a
	// single 64-bit mask is quite effective. See CL 452060 for details.

	import (
	"fmt"
	"go/token"
	"go/types"
	"hash/crc32"
	"strconv"
	"strings"

	"golang.org/x/tools/gopls/internal/lsp/safetoken"
	"golang.org/x/tools/internal/typeparams"
	)

	// An Index records the non-empty method sets of all package-level
	// types in a package in a form that permits assignability queries
	// without the type checker.
	type Index struct {
	pkg gobPackage
	}

	// NewIndex returns a new index of method-set information for all
	// package-level types in the specified package.
	func NewIndex(fset token.FileSet, pkg types.Package) *Index {
	return new(indexBuilder).build(fset, pkg)
	}

	// A Location records the extent of an identifier in byte-offset form.
	//
	// Conversion to protocol (UTF-16) form is done by the caller after a
	// search, not during index construction.
	// TODO(adonovan): opt: reconsider this choice, if FileHandles, not
	// ParsedGoFiles were to provide ColumnMapper-like functionality.
	// (Column mapping is currently associated with parsing,
	// but non-parsed and even non-Go files need it too.)
	// Since type checking requires reading (but not parsing) all
	// dependencies' Go files, we could do the conversion at type-checking
	// time at little extra cost in that case.
	type Location struct {
	Filename string
	Start, End int // byte offsets
	}

	// A Key represents the method set of a given type in a form suitable
	// to pass to the (*Index).Search method of many different Indexes.
	type Key struct {
	mset gobMethodSet // note: lacks position information
	}

	// KeyOf returns the search key for the method sets of a given type.
	// It returns false if the type has no methods.
	func KeyOf(t types.Type) (Key, bool) {
	mset := methodSetInfo(func(types.Object) (_ gobPosition) { return }, t, gobPosition{})
	if mset.Mask == 0 {
	return Key{}, false // no methods
	}
	return Key{mset}, true
	}

	// Search reports each type that implements (or is implemented by) the
	// type that produced the search key. If methodID is nonempty, only
	// that method of each type is reported.
	// The result is the location of each type or method.
	func (index *Index) Search(key Key, methodID string) []Location {
	var locs []Location
	for _, candidate := range index.pkg.MethodSets {
	// Traditionally this feature doesn't report
	// interface/interface elements of the relation.
	// I think that's a mistake.
	// TODO(adonovan): UX: change it, here and in the local implementation.
	if candidate.IsInterface && key.mset.IsInterface {
	continue
	}
	if !satisfies(candidate, key.mset) && !satisfies(key.mset, candidate) {
	continue
	}

	if candidate.Tricky {
	// If any interface method is tricky then extra
	// checking may be needed to eliminate a false positive.
	// TODO(adonovan): implement it.
	}

	if methodID == "" {
	locs = append(locs, index.location(candidate.Posn))
	} else {
	for _, m := range candidate.Methods {
	// Here we exploit knowledge of the shape of the fingerprint string.
	if strings.HasPrefix(m.Fingerprint, methodID) &&
	m.Fingerprint[len(methodID)] == '(' {
	locs = append(locs, index.location(m.Posn))
	break
	}
	}
	}
	}
	return locs
	}

	// satisfies does a fast check for whether x satisfies y.
	func satisfies(x, y gobMethodSet) bool {
	return y.IsInterface && x.Mask&y.Mask == y.Mask && subset(y, x)
	}

	// subset reports whether method set x is a subset of y.
	func subset(x, y gobMethodSet) bool {
	outer:
	for _, mx := range x.Methods {
	for _, my := range y.Methods {
	if mx.Sum == my.Sum && mx.Fingerprint == my.Fingerprint {
	continue outer // found; try next x method
	}
	}
	return false // method of x not found in y
	}
	return true // all methods of x found in y
	}

	func (index *Index) location(posn gobPosition) Location {
	return Location{
	Filename: index.pkg.Filenames[posn.File],
	Start: posn.Offset,
	End: posn.Offset + posn.Len,
	}
	}

	// An indexBuilder builds an index for a single package.
	type indexBuilder struct {
	gobPackage
	filenameIndex map[string]int
	}

	// build adds to the index all package-level named types of the specified package.
	func (b indexBuilder) build(fset token.FileSet, pkg types.Package) Index {
	// We ignore aliases, though in principle they could define a
	// struct{...} or interface{...} type, or an instantiation of
	// a generic, that has a novel method set.
	scope := pkg.Scope()
	for _, name := range scope.Names() {
	if tname, ok := scope.Lookup(name).(*types.TypeName); ok && !tname.IsAlias() {
	b.add(fset, tname)
	}
	}

	return &Index{pkg: b.gobPackage}
	}

	func (b indexBuilder) add(fset token.FileSet, tname *types.TypeName) {
	objectPos := func(obj types.Object) gobPosition {
	posn := safetoken.StartPosition(fset, obj.Pos())
	return gobPosition{b.fileIndex(posn.Filename), posn.Offset, len(obj.Name())}
	}
	if mset := methodSetInfo(objectPos, tname.Type(), objectPos(tname)); mset.Mask != 0 {
	// Only record types with non-trivial method sets.
	b.MethodSets = append(b.MethodSets, mset)
	}
	}

	// fileIndex returns a small integer that encodes the file name.
	func (b *indexBuilder) fileIndex(filename string) int {
	i, ok := b.filenameIndex[filename]
	if !ok {
	i = len(b.Filenames)
	if b.filenameIndex == nil {
	b.filenameIndex = make(map[string]int)
	}
	b.filenameIndex[filename] = i
	b.Filenames = append(b.Filenames, filename)
	}
	return i
	}

	// methodSetInfo returns the method-set fingerprint
	// of a type and records its position (typePosn)
	// and the position of each of its methods m,
	// as provided by objectPos(m).
	func methodSetInfo(objectPos func(types.Object) gobPosition, t types.Type, typePosn gobPosition) gobMethodSet {
	// For non-interface types, use *T
	// (if T is not already a pointer)
	// since it may have more methods.
	mset := types.NewMethodSet(EnsurePointer(t))

	// Convert the method set into a compact summary.
	var mask uint64
	tricky := false
	methods := make([]gobMethod, mset.Len())
	for i := 0; i < mset.Len(); i++ {
	m := mset.At(i).Obj().(*types.Func)
	fp, isTricky := fingerprint(m)
	if isTricky {
	tricky = true
	}
	sum := crc32.ChecksumIEEE([]byte(fp))
	methods[i] = gobMethod{fp, sum, objectPos(m)}
	mask \|= 1 << uint64(((sum>>24)^(sum>>16)^(sum>>8)^sum)&0x3f)
	}
	return gobMethodSet{typePosn, types.IsInterface(t), tricky, mask, methods}
	}

	// EnsurePointer wraps T in a types.Pointer if T is a named, non-interface type.
	// This is useful to make sure you consider a named type's full method set.
	func EnsurePointer(T types.Type) types.Type {
	if _, ok := T.(*types.Named); ok && !types.IsInterface(T) {
	return types.NewPointer(T)
	}

	return T
	}

	// fingerprint returns an encoding of a method signature such that two
	// methods with equal encodings have identical types, except for a few
	// tricky types whose encodings may spuriously match and whose exact
	// identity computation requires the type checker to eliminate false
	// positives (which are rare). The boolean result indicates whether
	// the result was one of these tricky types.
	//
	// In the standard library, 99.8% of package-level types have a
	// non-tricky method-set. The most common exceptions are due to type
	// parameters.
	//
	// The fingerprint string starts with method.Id() + "(".
	func fingerprint(method *types.Func) (string, bool) {
	var buf strings.Builder
	tricky := false
	var fprint func(t types.Type)
	fprint = func(t types.Type) {
	switch t := t.(type) {
	case *types.Named:
	tname := t.Obj()
	if tname.Pkg() != nil {
	buf.WriteString(strconv.Quote(tname.Pkg().Path()))
	buf.WriteByte('.')
	} else if tname.Name() != "error" {
	panic(tname) // error is the only named type with no package
	}
	buf.WriteString(tname.Name())

	case *types.Array:
	fmt.Fprintf(&buf, "[%d]", t.Len())
	fprint(t.Elem())

	case *types.Slice:
	buf.WriteString("[]")
	fprint(t.Elem())

	case *types.Pointer:
	buf.WriteByte('*')
	fprint(t.Elem())

	case *types.Map:
	buf.WriteString("map[")
	fprint(t.Key())
	buf.WriteByte(']')
	fprint(t.Elem())

	case *types.Chan:
	switch t.Dir() {
	case types.SendRecv:
	buf.WriteString("chan ")
	case types.SendOnly:
	buf.WriteString("<-chan ")
	case types.RecvOnly:
	buf.WriteString("chan<- ")
	}
	fprint(t.Elem())

	case *types.Tuple:
	buf.WriteByte('(')
	for i := 0; i < t.Len(); i++ {
	if i > 0 {
	buf.WriteByte(',')
	}
	fprint(t.At(i).Type())
	}
	buf.WriteByte(')')

	case *types.Basic:
	// Use canonical names for uint8 and int32 aliases.
	switch t.Kind() {
	case types.Byte:
	buf.WriteString("byte")
	case types.Rune:
	buf.WriteString("rune")
	default:
	buf.WriteString(t.String())
	}

	case *types.Signature:
	buf.WriteString("func")
	fprint(t.Params())
	if t.Variadic() {
	buf.WriteString("...") // not quite Go syntax
	}
	fprint(t.Results())

	case *types.Struct:
	// Non-empty unnamed struct types in method
	// signatures are vanishingly rare.
	buf.WriteString("struct{")
	for i := 0; i < t.NumFields(); i++ {
	if i > 0 {
	buf.WriteByte(';')
	}
	f := t.Field(i)
	// This isn't quite right for embedded type aliases.
	// (See types.TypeString(StructType) and #44410 for context.)
	// But this is vanishingly rare.
	if !f.Embedded() {
	buf.WriteString(f.Id())
	buf.WriteByte(' ')
	}
	fprint(f.Type())
	if tag := t.Tag(i); tag != "" {
	buf.WriteByte(' ')
	buf.WriteString(strconv.Quote(tag))
	}
	}
	buf.WriteString("}")

	case *types.Interface:
	if t.NumMethods() == 0 {
	buf.WriteString("any") // common case
	} else {
	// Interface assignability is particularly
	// tricky due to the possibility of recursion.
	tricky = true
	// We could still give more disambiguating precision
	// than "..." if we wanted to.
	buf.WriteString("interface{...}")
	}

	case *typeparams.TypeParam:
	tricky = true
	// TODO(adonovan): refine this by adding a numeric suffix
	// indicating the index among the receiver type's parameters.
	buf.WriteByte('?')

	default: // incl. *types.Union
	panic(t)
	}
	}

	buf.WriteString(method.Id()) // e.g. "pkg.Type"
	sig := method.Type().(*types.Signature)
	fprint(sig.Params())
	fprint(sig.Results())
	return buf.String(), tricky
	}

	// -- serial format of index --

	// The cost of gob encoding and decoding for most packages in x/tools
	// is under 50us, with occasional peaks of around 1-3ms.
	// The encoded indexes are around 1KB-50KB.

	// A gobPackage records the method set of each package-level type for a single package.
	type gobPackage struct {
	Filenames []string // see gobPosition.File
	MethodSets []gobMethodSet
	}

	// A gobMethodSet records the method set of a single type.
	type gobMethodSet struct {
	Posn gobPosition
	IsInterface bool
	Tricky bool // at least one method is tricky; assignability requires go/types
	Mask uint64 // mask with 1 bit from each of methods[*].sum
	Methods []gobMethod
	}

	// A gobMethod records the name, type, and position of a single method.
	type gobMethod struct {
	Fingerprint string // string of form "methodID(params...)(results)"
	Sum uint32 // checksum of fingerprint
	Posn gobPosition // location of method declaration
	}

	// A gobPosition records the file, offset, and length of an identifier.
	type gobPosition struct {
	File int // index into Index.filenames
	Offset, Len int // in bytes
	}