diff options
Diffstat (limited to 'vendor/golang.org/x/tools')
18 files changed, 1034 insertions, 257 deletions
diff --git a/vendor/golang.org/x/tools/go/gcexportdata/gcexportdata.go b/vendor/golang.org/x/tools/go/gcexportdata/gcexportdata.go index fc8beea5..cec819d6 100644 --- a/vendor/golang.org/x/tools/go/gcexportdata/gcexportdata.go +++ b/vendor/golang.org/x/tools/go/gcexportdata/gcexportdata.go @@ -50,11 +50,24 @@ func Find(importPath, srcDir string) (filename, path string) { // additional trailing data beyond the end of the export data. func NewReader(r io.Reader) (io.Reader, error) { buf := bufio.NewReader(r) - _, err := gcimporter.FindExportData(buf) - // If we ever switch to a zip-like archive format with the ToC - // at the end, we can return the correct portion of export data, - // but for now we must return the entire rest of the file. - return buf, err + _, size, err := gcimporter.FindExportData(buf) + if err != nil { + return nil, err + } + + if size >= 0 { + // We were given an archive and found the __.PKGDEF in it. + // This tells us the size of the export data, and we don't + // need to return the entire file. + return &io.LimitedReader{ + R: buf, + N: size, + }, nil + } else { + // We were given an object file. As such, we don't know how large + // the export data is and must return the entire file. + return buf, nil + } } // Read reads export data from in, decodes it, and returns type diff --git a/vendor/golang.org/x/tools/go/internal/gcimporter/bexport.go b/vendor/golang.org/x/tools/go/internal/gcimporter/bexport.go index 072005af..0a3cdb9a 100644 --- a/vendor/golang.org/x/tools/go/internal/gcimporter/bexport.go +++ b/vendor/golang.org/x/tools/go/internal/gcimporter/bexport.go @@ -34,9 +34,6 @@ import ( // (suspected) format errors, and whenever a change is made to the format. const debugFormat = false // default: false -// If trace is set, debugging output is printed to std out. -const trace = false // default: false - // Current export format version. Increase with each format change. // Note: The latest binary (non-indexed) export format is at version 6. // This exporter is still at level 4, but it doesn't matter since diff --git a/vendor/golang.org/x/tools/go/internal/gcimporter/bimport.go b/vendor/golang.org/x/tools/go/internal/gcimporter/bimport.go index b0231200..b85de014 100644 --- a/vendor/golang.org/x/tools/go/internal/gcimporter/bimport.go +++ b/vendor/golang.org/x/tools/go/internal/gcimporter/bimport.go @@ -74,9 +74,10 @@ func BImportData(fset *token.FileSet, imports map[string]*types.Package, data [] pathList: []string{""}, // empty string is mapped to 0 fake: fakeFileSet{ fset: fset, - files: make(map[string]*token.File), + files: make(map[string]*fileInfo), }, } + defer p.fake.setLines() // set lines for files in fset // read version info var versionstr string @@ -338,37 +339,49 @@ func (p *importer) pos() token.Pos { // Synthesize a token.Pos type fakeFileSet struct { fset *token.FileSet - files map[string]*token.File + files map[string]*fileInfo } +type fileInfo struct { + file *token.File + lastline int +} + +const maxlines = 64 * 1024 + func (s *fakeFileSet) pos(file string, line, column int) token.Pos { // TODO(mdempsky): Make use of column. - // Since we don't know the set of needed file positions, we - // reserve maxlines positions per file. - const maxlines = 64 * 1024 + // Since we don't know the set of needed file positions, we reserve maxlines + // positions per file. We delay calling token.File.SetLines until all + // positions have been calculated (by way of fakeFileSet.setLines), so that + // we can avoid setting unnecessary lines. See also golang/go#46586. f := s.files[file] if f == nil { - f = s.fset.AddFile(file, -1, maxlines) + f = &fileInfo{file: s.fset.AddFile(file, -1, maxlines)} s.files[file] = f - // Allocate the fake linebreak indices on first use. - // TODO(adonovan): opt: save ~512KB using a more complex scheme? - fakeLinesOnce.Do(func() { - fakeLines = make([]int, maxlines) - for i := range fakeLines { - fakeLines[i] = i - } - }) - f.SetLines(fakeLines) } - if line > maxlines { line = 1 } + if line > f.lastline { + f.lastline = line + } - // Treat the file as if it contained only newlines - // and column=1: use the line number as the offset. - return f.Pos(line - 1) + // Return a fake position assuming that f.file consists only of newlines. + return token.Pos(f.file.Base() + line - 1) +} + +func (s *fakeFileSet) setLines() { + fakeLinesOnce.Do(func() { + fakeLines = make([]int, maxlines) + for i := range fakeLines { + fakeLines[i] = i + } + }) + for _, f := range s.files { + f.file.SetLines(fakeLines[:f.lastline]) + } } var ( diff --git a/vendor/golang.org/x/tools/go/internal/gcimporter/exportdata.go b/vendor/golang.org/x/tools/go/internal/gcimporter/exportdata.go index f33dc561..f6437feb 100644 --- a/vendor/golang.org/x/tools/go/internal/gcimporter/exportdata.go +++ b/vendor/golang.org/x/tools/go/internal/gcimporter/exportdata.go @@ -16,7 +16,7 @@ import ( "strings" ) -func readGopackHeader(r *bufio.Reader) (name string, size int, err error) { +func readGopackHeader(r *bufio.Reader) (name string, size int64, err error) { // See $GOROOT/include/ar.h. hdr := make([]byte, 16+12+6+6+8+10+2) _, err = io.ReadFull(r, hdr) @@ -28,7 +28,8 @@ func readGopackHeader(r *bufio.Reader) (name string, size int, err error) { fmt.Printf("header: %s", hdr) } s := strings.TrimSpace(string(hdr[16+12+6+6+8:][:10])) - size, err = strconv.Atoi(s) + length, err := strconv.Atoi(s) + size = int64(length) if err != nil || hdr[len(hdr)-2] != '`' || hdr[len(hdr)-1] != '\n' { err = fmt.Errorf("invalid archive header") return @@ -42,8 +43,8 @@ func readGopackHeader(r *bufio.Reader) (name string, size int, err error) { // file by reading from it. The reader must be positioned at the // start of the file before calling this function. The hdr result // is the string before the export data, either "$$" or "$$B". -// -func FindExportData(r *bufio.Reader) (hdr string, err error) { +// The size result is the length of the export data in bytes, or -1 if not known. +func FindExportData(r *bufio.Reader) (hdr string, size int64, err error) { // Read first line to make sure this is an object file. line, err := r.ReadSlice('\n') if err != nil { @@ -54,7 +55,7 @@ func FindExportData(r *bufio.Reader) (hdr string, err error) { if string(line) == "!<arch>\n" { // Archive file. Scan to __.PKGDEF. var name string - if name, _, err = readGopackHeader(r); err != nil { + if name, size, err = readGopackHeader(r); err != nil { return } @@ -70,6 +71,7 @@ func FindExportData(r *bufio.Reader) (hdr string, err error) { err = fmt.Errorf("can't find export data (%v)", err) return } + size -= int64(len(line)) } // Now at __.PKGDEF in archive or still at beginning of file. @@ -86,8 +88,12 @@ func FindExportData(r *bufio.Reader) (hdr string, err error) { err = fmt.Errorf("can't find export data (%v)", err) return } + size -= int64(len(line)) } hdr = string(line) + if size < 0 { + size = -1 + } return } diff --git a/vendor/golang.org/x/tools/go/internal/gcimporter/gcimporter.go b/vendor/golang.org/x/tools/go/internal/gcimporter/gcimporter.go index e8cba6b2..3ab66830 100644 --- a/vendor/golang.org/x/tools/go/internal/gcimporter/gcimporter.go +++ b/vendor/golang.org/x/tools/go/internal/gcimporter/gcimporter.go @@ -29,8 +29,14 @@ import ( "text/scanner" ) -// debugging/development support -const debug = false +const ( + // Enable debug during development: it adds some additional checks, and + // prevents errors from being recovered. + debug = false + + // If trace is set, debugging output is printed to std out. + trace = false +) var pkgExts = [...]string{".a", ".o"} @@ -179,7 +185,7 @@ func Import(packages map[string]*types.Package, path, srcDir string, lookup func var hdr string buf := bufio.NewReader(rc) - if hdr, err = FindExportData(buf); err != nil { + if hdr, _, err = FindExportData(buf); err != nil { return } diff --git a/vendor/golang.org/x/tools/go/internal/gcimporter/iexport.go b/vendor/golang.org/x/tools/go/internal/gcimporter/iexport.go index be8b7459..20955340 100644 --- a/vendor/golang.org/x/tools/go/internal/gcimporter/iexport.go +++ b/vendor/golang.org/x/tools/go/internal/gcimporter/iexport.go @@ -11,6 +11,7 @@ package gcimporter import ( "bytes" "encoding/binary" + "fmt" "go/ast" "go/constant" "go/token" @@ -19,6 +20,8 @@ import ( "math/big" "reflect" "sort" + "strconv" + "strings" "golang.org/x/tools/internal/typeparams" ) @@ -33,15 +36,15 @@ const bundleVersion = 0 // The package path of the top-level package will not be recorded, // so that calls to IImportData can override with a provided package path. func IExportData(out io.Writer, fset *token.FileSet, pkg *types.Package) error { - return iexportCommon(out, fset, false, []*types.Package{pkg}) + return iexportCommon(out, fset, false, iexportVersion, []*types.Package{pkg}) } // IExportBundle writes an indexed export bundle for pkgs to out. func IExportBundle(out io.Writer, fset *token.FileSet, pkgs []*types.Package) error { - return iexportCommon(out, fset, true, pkgs) + return iexportCommon(out, fset, true, iexportVersion, pkgs) } -func iexportCommon(out io.Writer, fset *token.FileSet, bundle bool, pkgs []*types.Package) (err error) { +func iexportCommon(out io.Writer, fset *token.FileSet, bundle bool, version int, pkgs []*types.Package) (err error) { if !debug { defer func() { if e := recover(); e != nil { @@ -57,9 +60,11 @@ func iexportCommon(out io.Writer, fset *token.FileSet, bundle bool, pkgs []*type p := iexporter{ fset: fset, + version: version, allPkgs: map[*types.Package]bool{}, stringIndex: map[string]uint64{}, declIndex: map[types.Object]uint64{}, + tparamNames: map[types.Object]string{}, typIndex: map[types.Type]uint64{}, } if !bundle { @@ -119,7 +124,7 @@ func iexportCommon(out io.Writer, fset *token.FileSet, bundle bool, pkgs []*type if bundle { hdr.uint64(bundleVersion) } - hdr.uint64(iexportVersion) + hdr.uint64(uint64(p.version)) hdr.uint64(uint64(p.strings.Len())) hdr.uint64(dataLen) @@ -136,8 +141,12 @@ func iexportCommon(out io.Writer, fset *token.FileSet, bundle bool, pkgs []*type // non-compiler tools and includes a complete package description // (i.e., name and height). func (w *exportWriter) writeIndex(index map[types.Object]uint64) { + type pkgObj struct { + obj types.Object + name string // qualified name; differs from obj.Name for type params + } // Build a map from packages to objects from that package. - pkgObjs := map[*types.Package][]types.Object{} + pkgObjs := map[*types.Package][]pkgObj{} // For the main index, make sure to include every package that // we reference, even if we're not exporting (or reexporting) @@ -150,7 +159,8 @@ func (w *exportWriter) writeIndex(index map[types.Object]uint64) { } for obj := range index { - pkgObjs[obj.Pkg()] = append(pkgObjs[obj.Pkg()], obj) + name := w.p.exportName(obj) + pkgObjs[obj.Pkg()] = append(pkgObjs[obj.Pkg()], pkgObj{obj, name}) } var pkgs []*types.Package @@ -158,7 +168,7 @@ func (w *exportWriter) writeIndex(index map[types.Object]uint64) { pkgs = append(pkgs, pkg) sort.Slice(objs, func(i, j int) bool { - return indexName(objs[i]) < indexName(objs[j]) + return objs[i].name < objs[j].name }) } @@ -175,29 +185,25 @@ func (w *exportWriter) writeIndex(index map[types.Object]uint64) { objs := pkgObjs[pkg] w.uint64(uint64(len(objs))) for _, obj := range objs { - w.string(indexName(obj)) - w.uint64(index[obj]) + w.string(obj.name) + w.uint64(index[obj.obj]) } } } -// indexName returns the 'indexed' name of an object. It differs from -// obj.Name() only for type parameter names, where we include the subscripted -// type parameter ID. -// -// TODO(rfindley): remove this once we no longer need subscripts. -func indexName(obj types.Object) (res string) { - if _, ok := obj.(*types.TypeName); ok { - if tparam, ok := obj.Type().(*typeparams.TypeParam); ok { - return types.TypeString(tparam, func(*types.Package) string { return "" }) - } +// exportName returns the 'exported' name of an object. It differs from +// obj.Name() only for type parameters (see tparamExportName for details). +func (p *iexporter) exportName(obj types.Object) (res string) { + if name := p.tparamNames[obj]; name != "" { + return name } return obj.Name() } type iexporter struct { - fset *token.FileSet - out *bytes.Buffer + fset *token.FileSet + out *bytes.Buffer + version int localpkg *types.Package @@ -211,9 +217,21 @@ type iexporter struct { strings intWriter stringIndex map[string]uint64 - data0 intWriter - declIndex map[types.Object]uint64 - typIndex map[types.Type]uint64 + data0 intWriter + declIndex map[types.Object]uint64 + tparamNames map[types.Object]string // typeparam->exported name + typIndex map[types.Type]uint64 + + indent int // for tracing support +} + +func (p *iexporter) trace(format string, args ...interface{}) { + if !trace { + // Call sites should also be guarded, but having this check here allows + // easily enabling/disabling debug trace statements. + return + } + fmt.Printf(strings.Repeat("..", p.indent)+format+"\n", args...) } // stringOff returns the offset of s within the string section. @@ -239,7 +257,7 @@ func (p *iexporter) pushDecl(obj types.Object) { return } - p.declIndex[obj] = ^uint64(0) // mark n present in work queue + p.declIndex[obj] = ^uint64(0) // mark obj present in work queue p.declTodo.pushTail(obj) } @@ -262,6 +280,14 @@ func (w *exportWriter) exportPath(pkg *types.Package) string { } func (p *iexporter) doDecl(obj types.Object) { + if trace { + p.trace("exporting decl %v (%T)", obj, obj) + p.indent++ + defer func() { + p.indent-- + p.trace("=> %s", obj) + }() + } w := p.newWriter() w.setPkg(obj.Pkg(), false) @@ -284,14 +310,15 @@ func (p *iexporter) doDecl(obj types.Object) { w.tag('G') } w.pos(obj.Pos()) - // The tparam list of the function type is the - // declaration of the type params. So, write out the type - // params right now. Then those type params will be - // referenced via their type offset (via typOff) in all - // other places in the signature and function that they - // are used. + // The tparam list of the function type is the declaration of the type + // params. So, write out the type params right now. Then those type params + // will be referenced via their type offset (via typOff) in all other + // places in the signature and function where they are used. + // + // While importing the type parameters, tparamList computes and records + // their export name, so that it can be later used when writing the index. if tparams := typeparams.ForSignature(sig); tparams.Len() > 0 { - w.tparamList(tparams, obj.Pkg()) + w.tparamList(obj.Name(), tparams, obj.Pkg()) } w.signature(sig) @@ -306,7 +333,15 @@ func (p *iexporter) doDecl(obj types.Object) { if tparam, ok := t.(*typeparams.TypeParam); ok { w.tag('P') w.pos(obj.Pos()) - w.typ(tparam.Constraint(), obj.Pkg()) + constraint := tparam.Constraint() + if p.version >= iexportVersionGo1_18 { + implicit := false + if iface, _ := constraint.(*types.Interface); iface != nil { + implicit = typeparams.IsImplicit(iface) + } + w.bool(implicit) + } + w.typ(constraint, obj.Pkg()) break } @@ -331,7 +366,9 @@ func (p *iexporter) doDecl(obj types.Object) { w.pos(obj.Pos()) if typeparams.ForNamed(named).Len() > 0 { - w.tparamList(typeparams.ForNamed(named), obj.Pkg()) + // While importing the type parameters, tparamList computes and records + // their export name, so that it can be later used when writing the index. + w.tparamList(obj.Name(), typeparams.ForNamed(named), obj.Pkg()) } underlying := obj.Type().Underlying() @@ -348,6 +385,17 @@ func (p *iexporter) doDecl(obj types.Object) { w.pos(m.Pos()) w.string(m.Name()) sig, _ := m.Type().(*types.Signature) + + // Receiver type parameters are type arguments of the receiver type, so + // their name must be qualified before exporting recv. + if rparams := typeparams.RecvTypeParams(sig); rparams.Len() > 0 { + prefix := obj.Name() + "." + m.Name() + for i := 0; i < rparams.Len(); i++ { + rparam := rparams.At(i) + name := tparamExportName(prefix, rparam) + w.p.tparamNames[rparam.Obj()] = name + } + } w.param(sig.Recv()) w.signature(sig) } @@ -364,7 +412,7 @@ func (w *exportWriter) tag(tag byte) { } func (w *exportWriter) pos(pos token.Pos) { - if iexportVersion >= iexportVersionPosCol { + if w.p.version >= iexportVersionPosCol { w.posV1(pos) } else { w.posV0(pos) @@ -447,9 +495,11 @@ func (w *exportWriter) pkg(pkg *types.Package) { } func (w *exportWriter) qualifiedIdent(obj types.Object) { + name := w.p.exportName(obj) + // Ensure any referenced declarations are written out too. w.p.pushDecl(obj) - w.string(indexName(obj)) + w.string(name) w.pkg(obj.Pkg()) } @@ -483,6 +533,14 @@ func (w *exportWriter) startType(k itag) { } func (w *exportWriter) doTyp(t types.Type, pkg *types.Package) { + if trace { + w.p.trace("exporting type %s (%T)", t, t) + w.p.indent++ + defer func() { + w.p.indent-- + w.p.trace("=> %s", t) + }() + } switch t := t.(type) { case *types.Named: if targs := typeparams.NamedTypeArgs(t); targs.Len() > 0 { @@ -619,14 +677,49 @@ func (w *exportWriter) typeList(ts *typeparams.TypeList, pkg *types.Package) { } } -func (w *exportWriter) tparamList(list *typeparams.TypeParamList, pkg *types.Package) { +func (w *exportWriter) tparamList(prefix string, list *typeparams.TypeParamList, pkg *types.Package) { ll := uint64(list.Len()) w.uint64(ll) for i := 0; i < list.Len(); i++ { + tparam := list.At(i) + // Set the type parameter exportName before exporting its type. + exportName := tparamExportName(prefix, tparam) + w.p.tparamNames[tparam.Obj()] = exportName w.typ(list.At(i), pkg) } } +const blankMarker = "$" + +// tparamExportName returns the 'exported' name of a type parameter, which +// differs from its actual object name: it is prefixed with a qualifier, and +// blank type parameter names are disambiguated by their index in the type +// parameter list. +func tparamExportName(prefix string, tparam *typeparams.TypeParam) string { + assert(prefix != "") + name := tparam.Obj().Name() + if name == "_" { + name = blankMarker + strconv.Itoa(tparam.Index()) + } + return prefix + "." + name +} + +// tparamName returns the real name of a type parameter, after stripping its +// qualifying prefix and reverting blank-name encoding. See tparamExportName +// for details. +func tparamName(exportName string) string { + // Remove the "path" from the type param name that makes it unique. + ix := strings.LastIndex(exportName, ".") + if ix < 0 { + errorf("malformed type parameter export name %s: missing prefix", exportName) + } + name := exportName[ix+1:] + if strings.HasPrefix(name, blankMarker) { + return "_" + } + return name +} + func (w *exportWriter) paramList(tup *types.Tuple) { n := tup.Len() w.uint64(uint64(n)) @@ -643,6 +736,9 @@ func (w *exportWriter) param(obj types.Object) { func (w *exportWriter) value(typ types.Type, v constant.Value) { w.typ(typ, nil) + if w.p.version >= iexportVersionGo1_18 { + w.int64(int64(v.Kind())) + } switch b := typ.Underlying().(*types.Basic); b.Info() & types.IsConstType { case types.IsBoolean: @@ -832,7 +928,7 @@ func (w *exportWriter) localIdent(obj types.Object) { return } - name := indexName(obj) + name := obj.Name() if name == "_" { w.string("_") return diff --git a/vendor/golang.org/x/tools/go/internal/gcimporter/iimport.go b/vendor/golang.org/x/tools/go/internal/gcimporter/iimport.go index 1fcc87e5..1a33cd5c 100644 --- a/vendor/golang.org/x/tools/go/internal/gcimporter/iimport.go +++ b/vendor/golang.org/x/tools/go/internal/gcimporter/iimport.go @@ -18,6 +18,7 @@ import ( "go/types" "io" "sort" + "strings" "golang.org/x/tools/internal/typeparams" ) @@ -45,12 +46,10 @@ func (r *intReader) uint64() uint64 { // Keep this in sync with constants in iexport.go. const ( - iexportVersionGo1_11 = 0 - iexportVersionPosCol = 1 - // TODO: before release, change this back to 2. - iexportVersionGenerics = iexportVersionPosCol - - iexportVersionCurrent = iexportVersionGenerics + iexportVersionGo1_11 = 0 + iexportVersionPosCol = 1 + iexportVersionGo1_18 = 2 + iexportVersionGenerics = 2 ) type ident struct { @@ -123,9 +122,9 @@ func iimportCommon(fset *token.FileSet, imports map[string]*types.Package, data version = int64(r.uint64()) switch version { - case /* iexportVersionGenerics, */ iexportVersionPosCol, iexportVersionGo1_11: + case iexportVersionGo1_18, iexportVersionPosCol, iexportVersionGo1_11: default: - if version > iexportVersionGenerics { + if version > iexportVersionGo1_18 { errorf("unstable iexport format version %d, just rebuild compiler and std library", version) } else { errorf("unknown iexport format version %d", version) @@ -141,9 +140,8 @@ func iimportCommon(fset *token.FileSet, imports map[string]*types.Package, data r.Seek(sLen+dLen, io.SeekCurrent) p := iimporter{ - exportVersion: version, - ipath: path, - version: int(version), + version: int(version), + ipath: path, stringData: stringData, stringCache: make(map[uint64]string), @@ -153,14 +151,15 @@ func iimportCommon(fset *token.FileSet, imports map[string]*types.Package, data pkgIndex: make(map[*types.Package]map[string]uint64), typCache: make(map[uint64]types.Type), // Separate map for typeparams, keyed by their package and unique - // name (name with subscript). + // name. tparamIndex: make(map[ident]types.Type), fake: fakeFileSet{ fset: fset, - files: make(map[string]*token.File), + files: make(map[string]*fileInfo), }, } + defer p.fake.setLines() // set lines for files in fset for i, pt := range predeclared() { p.typCache[uint64(i)] = pt @@ -246,9 +245,8 @@ func iimportCommon(fset *token.FileSet, imports map[string]*types.Package, data } type iimporter struct { - exportVersion int64 - ipath string - version int + version int + ipath string stringData []byte stringCache map[uint64]string @@ -261,9 +259,28 @@ type iimporter struct { fake fakeFileSet interfaceList []*types.Interface + + indent int // for tracing support +} + +func (p *iimporter) trace(format string, args ...interface{}) { + if !trace { + // Call sites should also be guarded, but having this check here allows + // easily enabling/disabling debug trace statements. + return + } + fmt.Printf(strings.Repeat("..", p.indent)+format+"\n", args...) } func (p *iimporter) doDecl(pkg *types.Package, name string) { + if debug { + p.trace("import decl %s", name) + p.indent++ + defer func() { + p.indent-- + p.trace("=> %s", name) + }() + } // See if we've already imported this declaration. if obj := pkg.Scope().Lookup(name); obj != nil { return @@ -305,7 +322,7 @@ func (p *iimporter) pkgAt(off uint64) *types.Package { } func (p *iimporter) typAt(off uint64, base *types.Named) types.Type { - if t, ok := p.typCache[off]; ok && (base == nil || !isInterface(t)) { + if t, ok := p.typCache[off]; ok && canReuse(base, t) { return t } @@ -317,12 +334,30 @@ func (p *iimporter) typAt(off uint64, base *types.Named) types.Type { r.declReader.Reset(p.declData[off-predeclReserved:]) t := r.doType(base) - if base == nil || !isInterface(t) { + if canReuse(base, t) { p.typCache[off] = t } return t } +// canReuse reports whether the type rhs on the RHS of the declaration for def +// may be re-used. +// +// Specifically, if def is non-nil and rhs is an interface type with methods, it +// may not be re-used because we have a convention of setting the receiver type +// for interface methods to def. +func canReuse(def *types.Named, rhs types.Type) bool { + if def == nil { + return true + } + iface, _ := rhs.(*types.Interface) + if iface == nil { + return true + } + // Don't use iface.Empty() here as iface may not be complete. + return iface.NumEmbeddeds() == 0 && iface.NumExplicitMethods() == 0 +} + type importReader struct { p *iimporter declReader bytes.Reader @@ -352,8 +387,7 @@ func (r *importReader) obj(name string) { if tag == 'G' { tparams = r.tparamList() } - sig := r.signature(nil) - typeparams.SetForSignature(sig, tparams) + sig := r.signature(nil, nil, tparams) r.declare(types.NewFunc(pos, r.currPkg, name, sig)) case 'T', 'U': @@ -377,23 +411,21 @@ func (r *importReader) obj(name string) { mpos := r.pos() mname := r.ident() recv := r.param() - msig := r.signature(recv) // If the receiver has any targs, set those as the // rparams of the method (since those are the // typeparams being used in the method sig/body). - targs := typeparams.NamedTypeArgs(baseType(msig.Recv().Type())) + base := baseType(recv.Type()) + assert(base != nil) + targs := typeparams.NamedTypeArgs(base) + var rparams []*typeparams.TypeParam if targs.Len() > 0 { - rparams := make([]*typeparams.TypeParam, targs.Len()) + rparams = make([]*typeparams.TypeParam, targs.Len()) for i := range rparams { - // TODO(rfindley): this is less tolerant than the standard library - // go/internal/gcimporter, which calls under(...) and is tolerant - // of nil rparams. Bring them in sync by making the standard - // library importer stricter. rparams[i] = targs.At(i).(*typeparams.TypeParam) } - typeparams.SetRecvTypeParams(msig, rparams) } + msig := r.signature(recv, rparams, nil) named.AddMethod(types.NewFunc(mpos, r.currPkg, mname, msig)) } @@ -403,25 +435,30 @@ func (r *importReader) obj(name string) { // We need to "declare" a typeparam in order to have a name that // can be referenced recursively (if needed) in the type param's // bound. - if r.p.exportVersion < iexportVersionGenerics { + if r.p.version < iexportVersionGenerics { errorf("unexpected type param type") } - name0, sub := parseSubscript(name) + name0 := tparamName(name) tn := types.NewTypeName(pos, r.currPkg, name0, nil) t := typeparams.NewTypeParam(tn, nil) - if sub == 0 { - errorf("name %q missing subscript", name) - } - - // TODO(rfindley): can we use a different, stable ID? - // t.SetId(sub) // To handle recursive references to the typeparam within its // bound, save the partial type in tparamIndex before reading the bounds. id := ident{r.currPkg.Name(), name} r.p.tparamIndex[id] = t - - typeparams.SetTypeParamConstraint(t, r.typ()) + var implicit bool + if r.p.version >= iexportVersionGo1_18 { + implicit = r.bool() + } + constraint := r.typ() + if implicit { + iface, _ := constraint.(*types.Interface) + if iface == nil { + errorf("non-interface constraint marked implicit") + } + typeparams.MarkImplicit(iface) + } + typeparams.SetTypeParamConstraint(t, constraint) case 'V': typ := r.typ() @@ -439,6 +476,10 @@ func (r *importReader) declare(obj types.Object) { func (r *importReader) value() (typ types.Type, val constant.Value) { typ = r.typ() + if r.p.version >= iexportVersionGo1_18 { + // TODO: add support for using the kind. + _ = constant.Kind(r.int64()) + } switch b := typ.Underlying().(*types.Basic); b.Info() & types.IsConstType { case types.IsBoolean: @@ -581,7 +622,7 @@ func (r *importReader) qualifiedIdent() (*types.Package, string) { } func (r *importReader) pos() token.Pos { - if r.p.exportVersion >= iexportVersionPosCol { + if r.p.version >= iexportVersionPosCol { r.posv1() } else { r.posv0() @@ -629,8 +670,17 @@ func isInterface(t types.Type) bool { func (r *importReader) pkg() *types.Package { return r.p.pkgAt(r.uint64()) } func (r *importReader) string() string { return r.p.stringAt(r.uint64()) } -func (r *importReader) doType(base *types.Named) types.Type { - switch k := r.kind(); k { +func (r *importReader) doType(base *types.Named) (res types.Type) { + k := r.kind() + if debug { + r.p.trace("importing type %d (base: %s)", k, base) + r.p.indent++ + defer func() { + r.p.indent-- + r.p.trace("=> %s", res) + }() + } + switch k { default: errorf("unexpected kind tag in %q: %v", r.p.ipath, k) return nil @@ -653,7 +703,7 @@ func (r *importReader) doType(base *types.Named) types.Type { return types.NewMap(r.typ(), r.typ()) case signatureType: r.currPkg = r.pkg() - return r.signature(nil) + return r.signature(nil, nil, nil) case structType: r.currPkg = r.pkg() @@ -693,7 +743,7 @@ func (r *importReader) doType(base *types.Named) types.Type { recv = types.NewVar(token.NoPos, r.currPkg, "", base) } - msig := r.signature(recv) + msig := r.signature(recv, nil, nil) methods[i] = types.NewFunc(mpos, r.currPkg, mname, msig) } @@ -702,7 +752,7 @@ func (r *importReader) doType(base *types.Named) types.Type { return typ case typeParamType: - if r.p.exportVersion < iexportVersionGenerics { + if r.p.version < iexportVersionGenerics { errorf("unexpected type param type") } pkg, name := r.qualifiedIdent() @@ -716,7 +766,7 @@ func (r *importReader) doType(base *types.Named) types.Type { return r.p.tparamIndex[id] case instanceType: - if r.p.exportVersion < iexportVersionGenerics { + if r.p.version < iexportVersionGenerics { errorf("unexpected instantiation type") } // pos does not matter for instances: they are positioned on the original @@ -735,7 +785,7 @@ func (r *importReader) doType(base *types.Named) types.Type { return t case unionType: - if r.p.exportVersion < iexportVersionGenerics { + if r.p.version < iexportVersionGenerics { errorf("unexpected instantiation type") } terms := make([]*typeparams.Term, r.uint64()) @@ -750,11 +800,11 @@ func (r *importReader) kind() itag { return itag(r.uint64()) } -func (r *importReader) signature(recv *types.Var) *types.Signature { +func (r *importReader) signature(recv *types.Var, rparams []*typeparams.TypeParam, tparams []*typeparams.TypeParam) *types.Signature { params := r.paramList() results := r.paramList() variadic := params.Len() > 0 && r.bool() - return types.NewSignature(recv, params, results, variadic) + return typeparams.NewSignatureType(recv, rparams, tparams, params, results, variadic) } func (r *importReader) tparamList() []*typeparams.TypeParam { @@ -823,23 +873,3 @@ func baseType(typ types.Type) *types.Named { n, _ := typ.(*types.Named) return n } - -func parseSubscript(name string) (string, uint64) { - // Extract the subscript value from the type param name. We export - // and import the subscript value, so that all type params have - // unique names. - sub := uint64(0) - startsub := -1 - for i, r := range name { - if '₀' <= r && r < '₀'+10 { - if startsub == -1 { - startsub = i - } - sub = sub*10 + uint64(r-'₀') - } - } - if startsub >= 0 { - name = name[:startsub] - } - return name, sub -} diff --git a/vendor/golang.org/x/tools/go/internal/gcimporter/support_go117.go b/vendor/golang.org/x/tools/go/internal/gcimporter/support_go117.go index 817a147e..d892273e 100644 --- a/vendor/golang.org/x/tools/go/internal/gcimporter/support_go117.go +++ b/vendor/golang.org/x/tools/go/internal/gcimporter/support_go117.go @@ -2,8 +2,8 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -//go:build !typeparams || !go1.18 -// +build !typeparams !go1.18 +//go:build !go1.18 +// +build !go1.18 package gcimporter diff --git a/vendor/golang.org/x/tools/go/internal/gcimporter/support_go118.go b/vendor/golang.org/x/tools/go/internal/gcimporter/support_go118.go index e6b81fc5..a9938432 100644 --- a/vendor/golang.org/x/tools/go/internal/gcimporter/support_go118.go +++ b/vendor/golang.org/x/tools/go/internal/gcimporter/support_go118.go @@ -2,8 +2,8 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -//go:build typeparams && go1.18 -// +build typeparams,go1.18 +//go:build go1.18 +// +build go1.18 package gcimporter @@ -16,5 +16,8 @@ func additionalPredeclared() []types.Type { return []types.Type{ // comparable types.Universe.Lookup("comparable").Type(), + + // any + types.Universe.Lookup("any").Type(), } } diff --git a/vendor/golang.org/x/tools/go/packages/packages.go b/vendor/golang.org/x/tools/go/packages/packages.go index 8a1a2d68..1b5424e7 100644 --- a/vendor/golang.org/x/tools/go/packages/packages.go +++ b/vendor/golang.org/x/tools/go/packages/packages.go @@ -26,6 +26,7 @@ import ( "golang.org/x/tools/go/gcexportdata" "golang.org/x/tools/internal/gocommand" "golang.org/x/tools/internal/packagesinternal" + "golang.org/x/tools/internal/typeparams" "golang.org/x/tools/internal/typesinternal" ) @@ -327,6 +328,9 @@ type Package struct { // The NeedSyntax LoadMode bit populates this field for packages matching the patterns. // If NeedDeps and NeedImports are also set, this field will also be populated // for dependencies. + // + // Syntax is kept in the same order as CompiledGoFiles, with the caveat that nils are + // removed. If parsing returned nil, Syntax may be shorter than CompiledGoFiles. Syntax []*ast.File // TypesInfo provides type information about the package's syntax trees. @@ -910,6 +914,7 @@ func (ld *loader) loadPackage(lpkg *loaderPackage) { Scopes: make(map[ast.Node]*types.Scope), Selections: make(map[*ast.SelectorExpr]*types.Selection), } + typeparams.InitInstanceInfo(lpkg.TypesInfo) lpkg.TypesSizes = ld.sizes importer := importerFunc(func(path string) (*types.Package, error) { diff --git a/vendor/golang.org/x/tools/internal/typeparams/common.go b/vendor/golang.org/x/tools/internal/typeparams/common.go index 9fc6b4be..1222764b 100644 --- a/vendor/golang.org/x/tools/internal/typeparams/common.go +++ b/vendor/golang.org/x/tools/internal/typeparams/common.go @@ -2,24 +2,78 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -// Package typeparams provides functions to work indirectly with type parameter -// data stored in go/ast and go/types objects, while these API are guarded by a -// build constraint. +// Package typeparams contains common utilities for writing tools that interact +// with generic Go code, as introduced with Go 1.18. // -// This package exists to make it easier for tools to work with generic code, -// while also compiling against older Go versions. +// Many of the types and functions in this package are proxies for the new APIs +// introduced in the standard library with Go 1.18. For example, the +// typeparams.Union type is an alias for go/types.Union, and the ForTypeSpec +// function returns the value of the go/ast.TypeSpec.TypeParams field. At Go +// versions older than 1.18 these helpers are implemented as stubs, allowing +// users of this package to write code that handles generic constructs inline, +// even if the Go version being used to compile does not support generics. +// +// Additionally, this package contains common utilities for working with the +// new generic constructs, to supplement the standard library APIs. Notably, +// the StructuralTerms API computes a minimal representation of the structural +// restrictions on a type parameter. In the future, this API may be available +// from go/types. +// +// See the example/README.md for a more detailed guide on how to update tools +// to support generics. package typeparams import ( "go/ast" "go/token" + "go/types" ) -// A IndexExprData holds data from both ast.IndexExpr and the new -// ast.MultiIndexExpr, which was introduced in Go 1.18. -type IndexExprData struct { - X ast.Expr // expression - Lbrack token.Pos // position of "[" - Indices []ast.Expr // index expressions - Rbrack token.Pos // position of "]" +// UnpackIndexExpr extracts data from AST nodes that represent index +// expressions. +// +// For an ast.IndexExpr, the resulting indices slice will contain exactly one +// index expression. For an ast.IndexListExpr (go1.18+), it may have a variable +// number of index expressions. +// +// For nodes that don't represent index expressions, the first return value of +// UnpackIndexExpr will be nil. +func UnpackIndexExpr(n ast.Node) (x ast.Expr, lbrack token.Pos, indices []ast.Expr, rbrack token.Pos) { + switch e := n.(type) { + case *ast.IndexExpr: + return e.X, e.Lbrack, []ast.Expr{e.Index}, e.Rbrack + case *IndexListExpr: + return e.X, e.Lbrack, e.Indices, e.Rbrack + } + return nil, token.NoPos, nil, token.NoPos +} + +// PackIndexExpr returns an *ast.IndexExpr or *ast.IndexListExpr, depending on +// the cardinality of indices. Calling PackIndexExpr with len(indices) == 0 +// will panic. +func PackIndexExpr(x ast.Expr, lbrack token.Pos, indices []ast.Expr, rbrack token.Pos) ast.Expr { + switch len(indices) { + case 0: + panic("empty indices") + case 1: + return &ast.IndexExpr{ + X: x, + Lbrack: lbrack, + Index: indices[0], + Rbrack: rbrack, + } + default: + return &IndexListExpr{ + X: x, + Lbrack: lbrack, + Indices: indices, + Rbrack: rbrack, + } + } +} + +// IsTypeParam reports whether t is a type parameter. +func IsTypeParam(t types.Type) bool { + _, ok := t.(*TypeParam) + return ok } diff --git a/vendor/golang.org/x/tools/internal/typeparams/enabled_go117.go b/vendor/golang.org/x/tools/internal/typeparams/enabled_go117.go index 72d010e5..18212390 100644 --- a/vendor/golang.org/x/tools/internal/typeparams/enabled_go117.go +++ b/vendor/golang.org/x/tools/internal/typeparams/enabled_go117.go @@ -2,8 +2,8 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -//go:build !typeparams || !go1.18 -// +build !typeparams !go1.18 +//go:build !go1.18 +// +build !go1.18 package typeparams diff --git a/vendor/golang.org/x/tools/internal/typeparams/enabled_go118.go b/vendor/golang.org/x/tools/internal/typeparams/enabled_go118.go index 642fc8ee..d6714882 100644 --- a/vendor/golang.org/x/tools/internal/typeparams/enabled_go118.go +++ b/vendor/golang.org/x/tools/internal/typeparams/enabled_go118.go @@ -2,8 +2,8 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -//go:build typeparams && go1.18 -// +build typeparams,go1.18 +//go:build go1.18 +// +build go1.18 package typeparams diff --git a/vendor/golang.org/x/tools/internal/typeparams/normalize.go b/vendor/golang.org/x/tools/internal/typeparams/normalize.go new file mode 100644 index 00000000..090f142a --- /dev/null +++ b/vendor/golang.org/x/tools/internal/typeparams/normalize.go @@ -0,0 +1,216 @@ +// Copyright 2021 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 typeparams + +import ( + "errors" + "fmt" + "go/types" + "os" + "strings" +) + +//go:generate go run copytermlist.go + +const debug = false + +var ErrEmptyTypeSet = errors.New("empty type set") + +// StructuralTerms returns a slice of terms representing the normalized +// structural type restrictions of a type parameter, if any. +// +// Structural type restrictions of a type parameter are created via +// non-interface types embedded in its constraint interface (directly, or via a +// chain of interface embeddings). For example, in the declaration +// type T[P interface{~int; m()}] int +// the structural restriction of the type parameter P is ~int. +// +// With interface embedding and unions, the specification of structural type +// restrictions may be arbitrarily complex. For example, consider the +// following: +// +// type A interface{ ~string|~[]byte } +// +// type B interface{ int|string } +// +// type C interface { ~string|~int } +// +// type T[P interface{ A|B; C }] int +// +// In this example, the structural type restriction of P is ~string|int: A|B +// expands to ~string|~[]byte|int|string, which reduces to ~string|~[]byte|int, +// which when intersected with C (~string|~int) yields ~string|int. +// +// StructuralTerms computes these expansions and reductions, producing a +// "normalized" form of the embeddings. A structural restriction is normalized +// if it is a single union containing no interface terms, and is minimal in the +// sense that removing any term changes the set of types satisfying the +// constraint. It is left as a proof for the reader that, modulo sorting, there +// is exactly one such normalized form. +// +// Because the minimal representation always takes this form, StructuralTerms +// returns a slice of tilde terms corresponding to the terms of the union in +// the normalized structural restriction. An error is returned if the +// constraint interface is invalid, exceeds complexity bounds, or has an empty +// type set. In the latter case, StructuralTerms returns ErrEmptyTypeSet. +// +// StructuralTerms makes no guarantees about the order of terms, except that it +// is deterministic. +func StructuralTerms(tparam *TypeParam) ([]*Term, error) { + constraint := tparam.Constraint() + if constraint == nil { + return nil, fmt.Errorf("%s has nil constraint", tparam) + } + iface, _ := constraint.Underlying().(*types.Interface) + if iface == nil { + return nil, fmt.Errorf("constraint is %T, not *types.Interface", constraint.Underlying()) + } + return InterfaceTermSet(iface) +} + +// InterfaceTermSet computes the normalized terms for a constraint interface, +// returning an error if the term set cannot be computed or is empty. In the +// latter case, the error will be ErrEmptyTypeSet. +// +// See the documentation of StructuralTerms for more information on +// normalization. +func InterfaceTermSet(iface *types.Interface) ([]*Term, error) { + return computeTermSet(iface) +} + +// UnionTermSet computes the normalized terms for a union, returning an error +// if the term set cannot be computed or is empty. In the latter case, the +// error will be ErrEmptyTypeSet. +// +// See the documentation of StructuralTerms for more information on +// normalization. +func UnionTermSet(union *Union) ([]*Term, error) { + return computeTermSet(union) +} + +func computeTermSet(typ types.Type) ([]*Term, error) { + tset, err := computeTermSetInternal(typ, make(map[types.Type]*termSet), 0) + if err != nil { + return nil, err + } + if tset.terms.isEmpty() { + return nil, ErrEmptyTypeSet + } + if tset.terms.isAll() { + return nil, nil + } + var terms []*Term + for _, term := range tset.terms { + terms = append(terms, NewTerm(term.tilde, term.typ)) + } + return terms, nil +} + +// A termSet holds the normalized set of terms for a given type. +// +// The name termSet is intentionally distinct from 'type set': a type set is +// all types that implement a type (and includes method restrictions), whereas +// a term set just represents the structural restrictions on a type. +type termSet struct { + complete bool + terms termlist +} + +func indentf(depth int, format string, args ...interface{}) { + fmt.Fprintf(os.Stderr, strings.Repeat(".", depth)+format+"\n", args...) +} + +func computeTermSetInternal(t types.Type, seen map[types.Type]*termSet, depth int) (res *termSet, err error) { + if t == nil { + panic("nil type") + } + + if debug { + indentf(depth, "%s", t.String()) + defer func() { + if err != nil { + indentf(depth, "=> %s", err) + } else { + indentf(depth, "=> %s", res.terms.String()) + } + }() + } + + const maxTermCount = 100 + if tset, ok := seen[t]; ok { + if !tset.complete { + return nil, fmt.Errorf("cycle detected in the declaration of %s", t) + } + return tset, nil + } + + // Mark the current type as seen to avoid infinite recursion. + tset := new(termSet) + defer func() { + tset.complete = true + }() + seen[t] = tset + + switch u := t.Underlying().(type) { + case *types.Interface: + // The term set of an interface is the intersection of the term sets of its + // embedded types. + tset.terms = allTermlist + for i := 0; i < u.NumEmbeddeds(); i++ { + embedded := u.EmbeddedType(i) + if _, ok := embedded.Underlying().(*TypeParam); ok { + return nil, fmt.Errorf("invalid embedded type %T", embedded) + } + tset2, err := computeTermSetInternal(embedded, seen, depth+1) + if err != nil { + return nil, err + } + tset.terms = tset.terms.intersect(tset2.terms) + } + case *Union: + // The term set of a union is the union of term sets of its terms. + tset.terms = nil + for i := 0; i < u.Len(); i++ { + t := u.Term(i) + var terms termlist + switch t.Type().Underlying().(type) { + case *types.Interface: + tset2, err := computeTermSetInternal(t.Type(), seen, depth+1) + if err != nil { + return nil, err + } + terms = tset2.terms + case *TypeParam, *Union: + // A stand-alone type parameter or union is not permitted as union + // term. + return nil, fmt.Errorf("invalid union term %T", t) + default: + if t.Type() == types.Typ[types.Invalid] { + continue + } + terms = termlist{{t.Tilde(), t.Type()}} + } + tset.terms = tset.terms.union(terms) + if len(tset.terms) > maxTermCount { + return nil, fmt.Errorf("exceeded max term count %d", maxTermCount) + } + } + case *TypeParam: + panic("unreachable") + default: + // For all other types, the term set is just a single non-tilde term + // holding the type itself. + if u != types.Typ[types.Invalid] { + tset.terms = termlist{{false, t}} + } + } + return tset, nil +} + +// under is a facade for the go/types internal function of the same name. It is +// used by typeterm.go. +func under(t types.Type) types.Type { + return t.Underlying() +} diff --git a/vendor/golang.org/x/tools/internal/typeparams/termlist.go b/vendor/golang.org/x/tools/internal/typeparams/termlist.go new file mode 100644 index 00000000..10857d50 --- /dev/null +++ b/vendor/golang.org/x/tools/internal/typeparams/termlist.go @@ -0,0 +1,172 @@ +// Copyright 2021 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. + +// Code generated by copytermlist.go DO NOT EDIT. + +package typeparams + +import ( + "bytes" + "go/types" +) + +// A termlist represents the type set represented by the union +// t1 ∪ y2 ∪ ... tn of the type sets of the terms t1 to tn. +// A termlist is in normal form if all terms are disjoint. +// termlist operations don't require the operands to be in +// normal form. +type termlist []*term + +// allTermlist represents the set of all types. +// It is in normal form. +var allTermlist = termlist{new(term)} + +// String prints the termlist exactly (without normalization). +func (xl termlist) String() string { + if len(xl) == 0 { + return "∅" + } + var buf bytes.Buffer + for i, x := range xl { + if i > 0 { + buf.WriteString(" ∪ ") + } + buf.WriteString(x.String()) + } + return buf.String() +} + +// isEmpty reports whether the termlist xl represents the empty set of types. +func (xl termlist) isEmpty() bool { + // If there's a non-nil term, the entire list is not empty. + // If the termlist is in normal form, this requires at most + // one iteration. + for _, x := range xl { + if x != nil { + return false + } + } + return true +} + +// isAll reports whether the termlist xl represents the set of all types. +func (xl termlist) isAll() bool { + // If there's a 𝓤 term, the entire list is 𝓤. + // If the termlist is in normal form, this requires at most + // one iteration. + for _, x := range xl { + if x != nil && x.typ == nil { + return true + } + } + return false +} + +// norm returns the normal form of xl. +func (xl termlist) norm() termlist { + // Quadratic algorithm, but good enough for now. + // TODO(gri) fix asymptotic performance + used := make([]bool, len(xl)) + var rl termlist + for i, xi := range xl { + if xi == nil || used[i] { + continue + } + for j := i + 1; j < len(xl); j++ { + xj := xl[j] + if xj == nil || used[j] { + continue + } + if u1, u2 := xi.union(xj); u2 == nil { + // If we encounter a 𝓤 term, the entire list is 𝓤. + // Exit early. + // (Note that this is not just an optimization; + // if we continue, we may end up with a 𝓤 term + // and other terms and the result would not be + // in normal form.) + if u1.typ == nil { + return allTermlist + } + xi = u1 + used[j] = true // xj is now unioned into xi - ignore it in future iterations + } + } + rl = append(rl, xi) + } + return rl +} + +// If the type set represented by xl is specified by a single (non-𝓤) term, +// structuralType returns that type. Otherwise it returns nil. +func (xl termlist) structuralType() types.Type { + if nl := xl.norm(); len(nl) == 1 { + return nl[0].typ // if nl.isAll() then typ is nil, which is ok + } + return nil +} + +// union returns the union xl ∪ yl. +func (xl termlist) union(yl termlist) termlist { + return append(xl, yl...).norm() +} + +// intersect returns the intersection xl ∩ yl. +func (xl termlist) intersect(yl termlist) termlist { + if xl.isEmpty() || yl.isEmpty() { + return nil + } + + // Quadratic algorithm, but good enough for now. + // TODO(gri) fix asymptotic performance + var rl termlist + for _, x := range xl { + for _, y := range yl { + if r := x.intersect(y); r != nil { + rl = append(rl, r) + } + } + } + return rl.norm() +} + +// equal reports whether xl and yl represent the same type set. +func (xl termlist) equal(yl termlist) bool { + // TODO(gri) this should be more efficient + return xl.subsetOf(yl) && yl.subsetOf(xl) +} + +// includes reports whether t ∈ xl. +func (xl termlist) includes(t types.Type) bool { + for _, x := range xl { + if x.includes(t) { + return true + } + } + return false +} + +// supersetOf reports whether y ⊆ xl. +func (xl termlist) supersetOf(y *term) bool { + for _, x := range xl { + if y.subsetOf(x) { + return true + } + } + return false +} + +// subsetOf reports whether xl ⊆ yl. +func (xl termlist) subsetOf(yl termlist) bool { + if yl.isEmpty() { + return xl.isEmpty() + } + + // each term x of xl must be a subset of yl + for _, x := range xl { + if !yl.supersetOf(x) { + return false // x is not a subset yl + } + } + return true +} diff --git a/vendor/golang.org/x/tools/internal/typeparams/typeparams_go117.go b/vendor/golang.org/x/tools/internal/typeparams/typeparams_go117.go index 12817af8..5fd3fc35 100644 --- a/vendor/golang.org/x/tools/internal/typeparams/typeparams_go117.go +++ b/vendor/golang.org/x/tools/internal/typeparams/typeparams_go117.go @@ -2,13 +2,14 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -//go:build !typeparams || !go1.18 -// +build !typeparams !go1.18 +//go:build !go1.18 +// +build !go1.18 package typeparams import ( "go/ast" + "go/token" "go/types" ) @@ -16,18 +17,14 @@ func unsupported() { panic("type parameters are unsupported at this go version") } -// GetIndexExprData extracts data from *ast.IndexExpr nodes. -// For other nodes, GetIndexExprData returns nil. -func GetIndexExprData(n ast.Node) *IndexExprData { - if e, _ := n.(*ast.IndexExpr); e != nil { - return &IndexExprData{ - X: e.X, - Lbrack: e.Lbrack, - Indices: []ast.Expr{e.Index}, - Rbrack: e.Rbrack, - } - } - return nil +// IndexListExpr is a placeholder type, as type parameters are not supported at +// this Go version. Its methods panic on use. +type IndexListExpr struct { + ast.Expr + X ast.Expr // expression + Lbrack token.Pos // position of "[" + Indices []ast.Expr // index expressions + Rbrack token.Pos // position of "]" } // ForTypeSpec returns an empty field list, as type parameters on not supported @@ -46,6 +43,7 @@ func ForFuncType(*ast.FuncType) *ast.FieldList { // this Go version. Its methods panic on use. type TypeParam struct{ types.Type } +func (*TypeParam) Index() int { unsupported(); return 0 } func (*TypeParam) Constraint() types.Type { unsupported(); return nil } func (*TypeParam) Obj() *types.TypeName { unsupported(); return nil } @@ -72,42 +70,46 @@ func SetTypeParamConstraint(tparam *TypeParam, constraint types.Type) { unsupported() } +// NewSignatureType calls types.NewSignature, panicking if recvTypeParams or +// typeParams is non-empty. +func NewSignatureType(recv *types.Var, recvTypeParams, typeParams []*TypeParam, params, results *types.Tuple, variadic bool) *types.Signature { + if len(recvTypeParams) != 0 || len(typeParams) != 0 { + panic("signatures cannot have type parameters at this Go version") + } + return types.NewSignature(recv, params, results, variadic) +} + // ForSignature returns an empty slice. func ForSignature(*types.Signature) *TypeParamList { return nil } -// SetForSignature panics if tparams is non-empty. -func SetForSignature(_ *types.Signature, tparams []*TypeParam) { - if len(tparams) > 0 { - unsupported() - } -} - // RecvTypeParams returns a nil slice. func RecvTypeParams(sig *types.Signature) *TypeParamList { return nil } -// SetRecvTypeParams panics if rparams is non-empty. -func SetRecvTypeParams(sig *types.Signature, rparams []*TypeParam) { - if len(rparams) > 0 { - unsupported() - } -} - // IsComparable returns false, as no interfaces are type-restricted at this Go // version. func IsComparable(*types.Interface) bool { return false } -// IsConstraint returns false, as no interfaces are type-restricted at this Go +// IsMethodSet returns true, as no interfaces are type-restricted at this Go // version. -func IsConstraint(*types.Interface) bool { +func IsMethodSet(*types.Interface) bool { + return true +} + +// IsImplicit returns false, as no interfaces are implicit at this Go version. +func IsImplicit(*types.Interface) bool { return false } +// MarkImplicit does nothing, because this Go version does not have implicit +// interfaces. +func MarkImplicit(*types.Interface) {} + // ForNamed returns an empty type parameter list, as type parameters are not // supported at this Go version. func ForNamed(*types.Named) *TypeParamList { @@ -131,19 +133,25 @@ func NamedTypeOrigin(named *types.Named) types.Type { return named } -// Term is a placeholder type, as type parameters are not supported at this Go -// version. Its methods panic on use. -type Term struct{} +// Term holds information about a structural type restriction. +type Term struct { + tilde bool + typ types.Type +} -func (*Term) Tilde() bool { unsupported(); return false } -func (*Term) Type() types.Type { unsupported(); return nil } -func (*Term) String() string { unsupported(); return "" } -func (*Term) Underlying() types.Type { unsupported(); return nil } +func (m *Term) Tilde() bool { return m.tilde } +func (m *Term) Type() types.Type { return m.typ } +func (m *Term) String() string { + pre := "" + if m.tilde { + pre = "~" + } + return pre + m.typ.String() +} // NewTerm is unsupported at this Go version, and panics. func NewTerm(tilde bool, typ types.Type) *Term { - unsupported() - return nil + return &Term{tilde, typ} } // Union is a placeholder type, as type parameters are not supported at this Go @@ -162,16 +170,23 @@ func NewUnion(terms []*Term) *Union { // InitInstanceInfo is a noop at this Go version. func InitInstanceInfo(*types.Info) {} -// GetInstance returns nothing, as type parameters are not supported at this Go -// version. -func GetInstance(*types.Info, *ast.Ident) (*TypeList, types.Type) { return nil, nil } +// Instance is a placeholder type, as type parameters are not supported at this +// Go version. +type Instance struct { + TypeArgs *TypeList + Type types.Type +} + +// GetInstances returns a nil map, as type parameters are not supported at this +// Go version. +func GetInstances(info *types.Info) map[*ast.Ident]Instance { return nil } -// Environment is a placeholder type, as type parameters are not supported at +// Context is a placeholder type, as type parameters are not supported at // this Go version. -type Environment struct{} +type Context struct{} // Instantiate is unsupported on this Go version, and panics. -func Instantiate(env *Environment, typ types.Type, targs []types.Type, validate bool) (types.Type, error) { +func Instantiate(ctxt *Context, typ types.Type, targs []types.Type, validate bool) (types.Type, error) { unsupported() return nil, nil } diff --git a/vendor/golang.org/x/tools/internal/typeparams/typeparams_go118.go b/vendor/golang.org/x/tools/internal/typeparams/typeparams_go118.go index 8ab17b77..7470aed8 100644 --- a/vendor/golang.org/x/tools/internal/typeparams/typeparams_go118.go +++ b/vendor/golang.org/x/tools/internal/typeparams/typeparams_go118.go @@ -2,8 +2,8 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -//go:build typeparams && go1.18 -// +build typeparams,go1.18 +//go:build go1.18 +// +build go1.18 package typeparams @@ -12,29 +12,8 @@ import ( "go/types" ) -// GetIndexExprData extracts data from AST nodes that represent index -// expressions. -// -// For an ast.IndexExpr, the resulting IndexExprData will have exactly one -// index expression. For an ast.IndexListExpr (go1.18+), it may have a -// variable number of index expressions. -// -// For nodes that don't represent index expressions, GetIndexExprData returns -// nil. -func GetIndexExprData(n ast.Node) *IndexExprData { - switch e := n.(type) { - case *ast.IndexExpr: - return &IndexExprData{ - X: e.X, - Lbrack: e.Lbrack, - Indices: []ast.Expr{e.Index}, - Rbrack: e.Rbrack, - } - case *ast.IndexListExpr: - return (*IndexExprData)(e) - } - return nil -} +// IndexListExpr is an alias for ast.IndexListExpr. +type IndexListExpr = ast.IndexListExpr // ForTypeSpec returns n.TypeParams. func ForTypeSpec(n *ast.TypeSpec) *ast.FieldList { @@ -71,34 +50,39 @@ func SetTypeParamConstraint(tparam *TypeParam, constraint types.Type) { tparam.SetConstraint(constraint) } +// NewSignatureType calls types.NewSignatureType. +func NewSignatureType(recv *types.Var, recvTypeParams, typeParams []*TypeParam, params, results *types.Tuple, variadic bool) *types.Signature { + return types.NewSignatureType(recv, recvTypeParams, typeParams, params, results, variadic) +} + // ForSignature returns sig.TypeParams() func ForSignature(sig *types.Signature) *TypeParamList { return sig.TypeParams() } -// SetForSignature calls sig.SetTypeParams(tparams) -func SetForSignature(sig *types.Signature, tparams []*TypeParam) { - sig.SetTypeParams(tparams) -} - // RecvTypeParams returns sig.RecvTypeParams(). func RecvTypeParams(sig *types.Signature) *TypeParamList { return sig.RecvTypeParams() } -// SetRecvTypeParams calls sig.SetRecvTypeParams(rparams). -func SetRecvTypeParams(sig *types.Signature, rparams []*TypeParam) { - sig.SetRecvTypeParams(rparams) -} - // IsComparable calls iface.IsComparable(). func IsComparable(iface *types.Interface) bool { return iface.IsComparable() } -// IsConstraint calls iface.IsConstraint(). -func IsConstraint(iface *types.Interface) bool { - return iface.IsConstraint() +// IsMethodSet calls iface.IsMethodSet(). +func IsMethodSet(iface *types.Interface) bool { + return iface.IsMethodSet() +} + +// IsImplicit calls iface.IsImplicit(). +func IsImplicit(iface *types.Interface) bool { + return iface.IsImplicit() +} + +// MarkImplicit calls iface.MarkImplicit(). +func MarkImplicit(iface *types.Interface) { + iface.MarkImplicit() } // ForNamed extracts the (possibly empty) type parameter object list from @@ -145,21 +129,18 @@ func InitInstanceInfo(info *types.Info) { info.Instances = make(map[*ast.Ident]types.Instance) } -// GetInstance extracts information about the instantiation occurring at the -// identifier id. id should be the identifier denoting a parameterized type or -// function in an instantiation expression or function call. -func GetInstance(info *types.Info, id *ast.Ident) (*TypeList, types.Type) { - if info.Instances != nil { - inf := info.Instances[id] - return inf.TypeArgs, inf.Type - } - return nil, nil +// Instance is an alias for types.Instance. +type Instance = types.Instance + +// GetInstances returns info.Instances. +func GetInstances(info *types.Info) map[*ast.Ident]Instance { + return info.Instances } -// Environment is an alias for types.Environment. -type Environment = types.Environment +// Context is an alias for types.Context. +type Context = types.Context // Instantiate calls types.Instantiate. -func Instantiate(env *Environment, typ types.Type, targs []types.Type, validate bool) (types.Type, error) { - return types.Instantiate(env, typ, targs, validate) +func Instantiate(ctxt *Context, typ types.Type, targs []types.Type, validate bool) (types.Type, error) { + return types.Instantiate(ctxt, typ, targs, validate) } diff --git a/vendor/golang.org/x/tools/internal/typeparams/typeterm.go b/vendor/golang.org/x/tools/internal/typeparams/typeterm.go new file mode 100644 index 00000000..7ddee28d --- /dev/null +++ b/vendor/golang.org/x/tools/internal/typeparams/typeterm.go @@ -0,0 +1,170 @@ +// Copyright 2021 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. + +// Code generated by copytermlist.go DO NOT EDIT. + +package typeparams + +import "go/types" + +// A term describes elementary type sets: +// +// ∅: (*term)(nil) == ∅ // set of no types (empty set) +// 𝓤: &term{} == 𝓤 // set of all types (𝓤niverse) +// T: &term{false, T} == {T} // set of type T +// ~t: &term{true, t} == {t' | under(t') == t} // set of types with underlying type t +// +type term struct { + tilde bool // valid if typ != nil + typ types.Type +} + +func (x *term) String() string { + switch { + case x == nil: + return "∅" + case x.typ == nil: + return "𝓤" + case x.tilde: + return "~" + x.typ.String() + default: + return x.typ.String() + } +} + +// equal reports whether x and y represent the same type set. +func (x *term) equal(y *term) bool { + // easy cases + switch { + case x == nil || y == nil: + return x == y + case x.typ == nil || y.typ == nil: + return x.typ == y.typ + } + // ∅ ⊂ x, y ⊂ 𝓤 + + return x.tilde == y.tilde && types.Identical(x.typ, y.typ) +} + +// union returns the union x ∪ y: zero, one, or two non-nil terms. +func (x *term) union(y *term) (_, _ *term) { + // easy cases + switch { + case x == nil && y == nil: + return nil, nil // ∅ ∪ ∅ == ∅ + case x == nil: + return y, nil // ∅ ∪ y == y + case y == nil: + return x, nil // x ∪ ∅ == x + case x.typ == nil: + return x, nil // 𝓤 ∪ y == 𝓤 + case y.typ == nil: + return y, nil // x ∪ 𝓤 == 𝓤 + } + // ∅ ⊂ x, y ⊂ 𝓤 + + if x.disjoint(y) { + return x, y // x ∪ y == (x, y) if x ∩ y == ∅ + } + // x.typ == y.typ + + // ~t ∪ ~t == ~t + // ~t ∪ T == ~t + // T ∪ ~t == ~t + // T ∪ T == T + if x.tilde || !y.tilde { + return x, nil + } + return y, nil +} + +// intersect returns the intersection x ∩ y. +func (x *term) intersect(y *term) *term { + // easy cases + switch { + case x == nil || y == nil: + return nil // ∅ ∩ y == ∅ and ∩ ∅ == ∅ + case x.typ == nil: + return y // 𝓤 ∩ y == y + case y.typ == nil: + return x // x ∩ 𝓤 == x + } + // ∅ ⊂ x, y ⊂ 𝓤 + + if x.disjoint(y) { + return nil // x ∩ y == ∅ if x ∩ y == ∅ + } + // x.typ == y.typ + + // ~t ∩ ~t == ~t + // ~t ∩ T == T + // T ∩ ~t == T + // T ∩ T == T + if !x.tilde || y.tilde { + return x + } + return y +} + +// includes reports whether t ∈ x. +func (x *term) includes(t types.Type) bool { + // easy cases + switch { + case x == nil: + return false // t ∈ ∅ == false + case x.typ == nil: + return true // t ∈ 𝓤 == true + } + // ∅ ⊂ x ⊂ 𝓤 + + u := t + if x.tilde { + u = under(u) + } + return types.Identical(x.typ, u) +} + +// subsetOf reports whether x ⊆ y. +func (x *term) subsetOf(y *term) bool { + // easy cases + switch { + case x == nil: + return true // ∅ ⊆ y == true + case y == nil: + return false // x ⊆ ∅ == false since x != ∅ + case y.typ == nil: + return true // x ⊆ 𝓤 == true + case x.typ == nil: + return false // 𝓤 ⊆ y == false since y != 𝓤 + } + // ∅ ⊂ x, y ⊂ 𝓤 + + if x.disjoint(y) { + return false // x ⊆ y == false if x ∩ y == ∅ + } + // x.typ == y.typ + + // ~t ⊆ ~t == true + // ~t ⊆ T == false + // T ⊆ ~t == true + // T ⊆ T == true + return !x.tilde || y.tilde +} + +// disjoint reports whether x ∩ y == ∅. +// x.typ and y.typ must not be nil. +func (x *term) disjoint(y *term) bool { + if debug && (x.typ == nil || y.typ == nil) { + panic("invalid argument(s)") + } + ux := x.typ + if y.tilde { + ux = under(ux) + } + uy := y.typ + if x.tilde { + uy = under(uy) + } + return !types.Identical(ux, uy) +} |