iexport.go

     1  // Copyright 2019 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Indexed package export.
     6  //
     7  // The indexed export data format is an evolution of the previous
     8  // binary export data format. Its chief contribution is introducing an
     9  // index table, which allows efficient random access of individual
    10  // declarations and inline function bodies. In turn, this allows
    11  // avoiding unnecessary work for compilation units that import large
    12  // packages.
    13  //
    14  //
    15  // The top-level data format is structured as:
    16  //
    17  //     Header struct {
    18  //         Tag        byte   // 'i'
    19  //         Version    uvarint
    20  //         StringSize uvarint
    21  //         DataSize   uvarint
    22  //     }
    23  //
    24  //     Strings [StringSize]byte
    25  //     Data    [DataSize]byte
    26  //
    27  //     MainIndex []struct{
    28  //         PkgPath   stringOff
    29  //         PkgName   stringOff
    30  //         PkgHeight uvarint
    31  //
    32  //         Decls []struct{
    33  //             Name   stringOff
    34  //             Offset declOff
    35  //         }
    36  //     }
    37  //
    38  //     Fingerprint [8]byte
    39  //
    40  // uvarint means a uint64 written out using uvarint encoding.
    41  //
    42  // []T means a uvarint followed by that many T objects. In other
    43  // words:
    44  //
    45  //     Len   uvarint
    46  //     Elems [Len]T
    47  //
    48  // stringOff means a uvarint that indicates an offset within the
    49  // Strings section. At that offset is another uvarint, followed by
    50  // that many bytes, which form the string value.
    51  //
    52  // declOff means a uvarint that indicates an offset within the Data
    53  // section where the associated declaration can be found.
    54  //
    55  //
    56  // There are five kinds of declarations, distinguished by their first
    57  // byte:
    58  //
    59  //     type Var struct {
    60  //         Tag  byte // 'V'
    61  //         Pos  Pos
    62  //         Type typeOff
    63  //     }
    64  //
    65  //     type Func struct {
    66  //         Tag       byte // 'F' or 'G'
    67  //         Pos       Pos
    68  //         TypeParams []typeOff  // only present if Tag == 'G'
    69  //         Signature Signature
    70  //     }
    71  //
    72  //     type Const struct {
    73  //         Tag   byte // 'C'
    74  //         Pos   Pos
    75  //         Value Value
    76  //     }
    77  //
    78  //     type Type struct {
    79  //         Tag        byte // 'T' or 'U'
    80  //         Pos        Pos
    81  //         TypeParams []typeOff  // only present if Tag == 'U'
    82  //         Underlying typeOff
    83  //
    84  //         Methods []struct{  // omitted if Underlying is an interface type
    85  //             Pos       Pos
    86  //             Name      stringOff
    87  //             Recv      Param
    88  //             Signature Signature
    89  //         }
    90  //     }
    91  //
    92  //     type Alias struct {
    93  //         Tag  byte // 'A' or 'B'
    94  //         Pos  Pos
    95  //         TypeParams []typeOff  // only present if Tag == 'B'
    96  //         Type typeOff
    97  //     }
    98  //
    99  //     // "Automatic" declaration of each typeparam
   100  //     type TypeParam struct {
   101  //         Tag        byte // 'P'
   102  //         Pos        Pos
   103  //         Implicit   bool
   104  //         Constraint typeOff
   105  //     }
   106  //
   107  // typeOff means a uvarint that either indicates a predeclared type,
   108  // or an offset into the Data section. If the uvarint is less than
   109  // predeclReserved, then it indicates the index into the predeclared
   110  // types list (see predeclared in bexport.go for order). Otherwise,
   111  // subtracting predeclReserved yields the offset of a type descriptor.
   112  //
   113  // Value means a type, kind, and type-specific value. See
   114  // (*exportWriter).value for details.
   115  //
   116  //
   117  // There are twelve kinds of type descriptors, distinguished by an itag:
   118  //
   119  //     type DefinedType struct {
   120  //         Tag     itag // definedType
   121  //         Name    stringOff
   122  //         PkgPath stringOff
   123  //     }
   124  //
   125  //     type PointerType struct {
   126  //         Tag  itag // pointerType
   127  //         Elem typeOff
   128  //     }
   129  //
   130  //     type SliceType struct {
   131  //         Tag  itag // sliceType
   132  //         Elem typeOff
   133  //     }
   134  //
   135  //     type ArrayType struct {
   136  //         Tag  itag // arrayType
   137  //         Len  uint64
   138  //         Elem typeOff
   139  //     }
   140  //
   141  //     type ChanType struct {
   142  //         Tag  itag   // chanType
   143  //         Dir  uint64 // 1 RecvOnly; 2 SendOnly; 3 SendRecv
   144  //         Elem typeOff
   145  //     }
   146  //
   147  //     type MapType struct {
   148  //         Tag  itag // mapType
   149  //         Key  typeOff
   150  //         Elem typeOff
   151  //     }
   152  //
   153  //     type FuncType struct {
   154  //         Tag       itag // signatureType
   155  //         PkgPath   stringOff
   156  //         Signature Signature
   157  //     }
   158  //
   159  //     type StructType struct {
   160  //         Tag     itag // structType
   161  //         PkgPath stringOff
   162  //         Fields []struct {
   163  //             Pos      Pos
   164  //             Name     stringOff
   165  //             Type     typeOff
   166  //             Embedded bool
   167  //             Note     stringOff
   168  //         }
   169  //     }
   170  //
   171  //     type InterfaceType struct {
   172  //         Tag     itag // interfaceType
   173  //         PkgPath stringOff
   174  //         Embeddeds []struct {
   175  //             Pos  Pos
   176  //             Type typeOff
   177  //         }
   178  //         Methods []struct {
   179  //             Pos       Pos
   180  //             Name      stringOff
   181  //             Signature Signature
   182  //         }
   183  //     }
   184  //
   185  //     // Reference to a type param declaration
   186  //     type TypeParamType struct {
   187  //         Tag     itag // typeParamType
   188  //         Name    stringOff
   189  //         PkgPath stringOff
   190  //     }
   191  //
   192  //     // Instantiation of a generic type (like List[T2] or List[int])
   193  //     type InstanceType struct {
   194  //         Tag     itag // instanceType
   195  //         Pos     pos
   196  //         TypeArgs []typeOff
   197  //         BaseType typeOff
   198  //     }
   199  //
   200  //     type UnionType struct {
   201  //         Tag     itag // interfaceType
   202  //         Terms   []struct {
   203  //             tilde bool
   204  //             Type  typeOff
   205  //         }
   206  //     }
   207  //
   208  //
   209  //
   210  //     type Signature struct {
   211  //         Params   []Param
   212  //         Results  []Param
   213  //         Variadic bool  // omitted if Results is empty
   214  //     }
   215  //
   216  //     type Param struct {
   217  //         Pos  Pos
   218  //         Name stringOff
   219  //         Type typOff
   220  //     }
   221  //
   222  //
   223  // Pos encodes a file:line:column triple, incorporating a simple delta
   224  // encoding scheme within a data object. See exportWriter.pos for
   225  // details.
   226  
   227  package gcimporter
   228  
   229  import (
   230  	"bytes"
   231  	"encoding/binary"
   232  	"fmt"
   233  	"go/constant"
   234  	"go/token"
   235  	"go/types"
   236  	"io"
   237  	"math/big"
   238  	"reflect"
   239  	"slices"
   240  	"sort"
   241  	"strconv"
   242  	"strings"
   243  
   244  	"golang.org/x/tools/go/types/objectpath"
   245  )
   246  
   247  // IExportShallow encodes "shallow" export data for the specified package.
   248  //
   249  // For types, we use "shallow" export data. Historically, the Go
   250  // compiler always produced a summary of the types for a given package
   251  // that included types from other packages that it indirectly
   252  // referenced: "deep" export data. This had the advantage that the
   253  // compiler (and analogous tools such as gopls) need only load one
   254  // file per direct import.  However, it meant that the files tended to
   255  // get larger based on the level of the package in the import
   256  // graph. For example, higher-level packages in the kubernetes module
   257  // have over 1MB of "deep" export data, even when they have almost no
   258  // content of their own, merely because they mention a major type that
   259  // references many others. In pathological cases the export data was
   260  // 300x larger than the source for a package due to this quadratic
   261  // growth.
   262  //
   263  // "Shallow" export data means that the serialized types describe only
   264  // a single package. If those types mention types from other packages,
   265  // the type checker may need to request additional packages beyond
   266  // just the direct imports. Type information for the entire transitive
   267  // closure of imports is provided (lazily) by the DAG.
   268  //
   269  // No promises are made about the encoding other than that it can be decoded by
   270  // the same version of IIExportShallow. If you plan to save export data in the
   271  // file system, be sure to include a cryptographic digest of the executable in
   272  // the key to avoid version skew.
   273  //
   274  // If the provided reportf func is non-nil, it is used for reporting
   275  // bugs (e.g. recovered panics) encountered during export, enabling us
   276  // to obtain via telemetry the stack that would otherwise be lost by
   277  // merely returning an error.
   278  func IExportShallow(fset *token.FileSet, pkg *types.Package, reportf ReportFunc) ([]byte, error) {
   279  	// In principle this operation can only fail if out.Write fails,
   280  	// but that's impossible for bytes.Buffer---and as a matter of
   281  	// fact iexportCommon doesn't even check for I/O errors.
   282  	// TODO(adonovan): handle I/O errors properly.
   283  	// TODO(adonovan): use byte slices throughout, avoiding copying.
   284  	const bundle, shallow = false, true
   285  	var out bytes.Buffer
   286  	err := iexportCommon(&out, fset, bundle, shallow, iexportVersion, []*types.Package{pkg}, reportf)
   287  	return out.Bytes(), err
   288  }
   289  
   290  // IImportShallow decodes "shallow" types.Package data encoded by
   291  // [IExportShallow] in the same executable. This function cannot import data
   292  // from cmd/compile or gcexportdata.Write.
   293  //
   294  // The importer calls getPackages to obtain package symbols for all
   295  // packages mentioned in the export data, including the one being
   296  // decoded.
   297  //
   298  // If the provided reportf func is non-nil, it will be used for reporting bugs
   299  // encountered during import.
   300  // TODO(rfindley): remove reportf when we are confident enough in the new
   301  // objectpath encoding.
   302  func IImportShallow(fset *token.FileSet, getPackages GetPackagesFunc, data []byte, path string, reportf ReportFunc) (*types.Package, error) {
   303  	const bundle = false
   304  	const shallow = true
   305  	pkgs, err := iimportCommon(fset, getPackages, data, bundle, path, shallow, reportf)
   306  	if err != nil {
   307  		return nil, err
   308  	}
   309  	return pkgs[0], nil
   310  }
   311  
   312  // ReportFunc is the type of a function used to report formatted bugs.
   313  type ReportFunc = func(string, ...any)
   314  
   315  // Current bundled export format version. Increase with each format change.
   316  // 0: initial implementation
   317  const bundleVersion = 0
   318  
   319  // IExportData writes indexed export data for pkg to out.
   320  //
   321  // If no file set is provided, position info will be missing.
   322  // The package path of the top-level package will not be recorded,
   323  // so that calls to IImportData can override with a provided package path.
   324  func IExportData(out io.Writer, fset *token.FileSet, pkg *types.Package) error {
   325  	const bundle, shallow = false, false
   326  	return iexportCommon(out, fset, bundle, shallow, iexportVersion, []*types.Package{pkg}, nil)
   327  }
   328  
   329  // IExportBundle writes an indexed export bundle for pkgs to out.
   330  func IExportBundle(out io.Writer, fset *token.FileSet, pkgs []*types.Package) error {
   331  	const bundle, shallow = true, false
   332  	return iexportCommon(out, fset, bundle, shallow, iexportVersion, pkgs, nil)
   333  }
   334  
   335  func iexportCommon(out io.Writer, fset *token.FileSet, bundle, shallow bool, version int, pkgs []*types.Package, reportf ReportFunc) (err error) {
   336  	if !debug {
   337  		defer func() {
   338  			if e := recover(); e != nil {
   339  				// Report the stack via telemetry (see #71067).
   340  				if reportf != nil {
   341  					reportf("panic in exporter")
   342  				}
   343  				if ierr, ok := e.(internalError); ok {
   344  					// internalError usually means we exported a
   345  					// bad go/types data structure: a violation
   346  					// of an implicit precondition of Export.
   347  					err = ierr
   348  					return
   349  				}
   350  				// Not an internal error; panic again.
   351  				panic(e)
   352  			}
   353  		}()
   354  	}
   355  
   356  	p := iexporter{
   357  		fset:        fset,
   358  		version:     version,
   359  		shallow:     shallow,
   360  		allPkgs:     map[*types.Package]bool{},
   361  		stringIndex: map[string]uint64{},
   362  		declIndex:   map[types.Object]uint64{},
   363  		tparamNames: map[types.Object]string{},
   364  		typIndex:    map[types.Type]uint64{},
   365  	}
   366  	if !bundle {
   367  		p.localpkg = pkgs[0]
   368  	}
   369  
   370  	for i, pt := range predeclared() {
   371  		p.typIndex[pt] = uint64(i)
   372  	}
   373  	if len(p.typIndex) > predeclReserved {
   374  		panic(internalErrorf("too many predeclared types: %d > %d", len(p.typIndex), predeclReserved))
   375  	}
   376  
   377  	// Initialize work queue with exported declarations.
   378  	for _, pkg := range pkgs {
   379  		scope := pkg.Scope()
   380  		for _, name := range scope.Names() {
   381  			if token.IsExported(name) {
   382  				p.pushDecl(scope.Lookup(name))
   383  			}
   384  		}
   385  
   386  		if bundle {
   387  			// Ensure pkg and its imports are included in the index.
   388  			p.allPkgs[pkg] = true
   389  			for _, imp := range pkg.Imports() {
   390  				p.allPkgs[imp] = true
   391  			}
   392  		}
   393  	}
   394  
   395  	// Loop until no more work.
   396  	for !p.declTodo.empty() {
   397  		p.doDecl(p.declTodo.popHead())
   398  	}
   399  
   400  	// Produce index of offset of each file record in files.
   401  	var files intWriter
   402  	var fileOffset []uint64 // fileOffset[i] is offset in files of file encoded as i
   403  	if p.shallow {
   404  		fileOffset = make([]uint64, len(p.fileInfos))
   405  		for i, info := range p.fileInfos {
   406  			fileOffset[i] = uint64(files.Len())
   407  			p.encodeFile(&files, info.file, info.needed)
   408  		}
   409  	}
   410  
   411  	// Append indices to data0 section.
   412  	dataLen := uint64(p.data0.Len())
   413  	w := p.newWriter()
   414  	w.writeIndex(p.declIndex)
   415  
   416  	if bundle {
   417  		w.uint64(uint64(len(pkgs)))
   418  		for _, pkg := range pkgs {
   419  			w.pkg(pkg)
   420  			imps := pkg.Imports()
   421  			w.uint64(uint64(len(imps)))
   422  			for _, imp := range imps {
   423  				w.pkg(imp)
   424  			}
   425  		}
   426  	}
   427  	w.flush()
   428  
   429  	// Assemble header.
   430  	var hdr intWriter
   431  	if bundle {
   432  		hdr.uint64(bundleVersion)
   433  	}
   434  	hdr.uint64(uint64(p.version))
   435  	hdr.uint64(uint64(p.strings.Len()))
   436  	if p.shallow {
   437  		hdr.uint64(uint64(files.Len()))
   438  		hdr.uint64(uint64(len(fileOffset)))
   439  		for _, offset := range fileOffset {
   440  			hdr.uint64(offset)
   441  		}
   442  	}
   443  	hdr.uint64(dataLen)
   444  
   445  	// Flush output.
   446  	io.Copy(out, &hdr)
   447  	io.Copy(out, &p.strings)
   448  	if p.shallow {
   449  		io.Copy(out, &files)
   450  	}
   451  	io.Copy(out, &p.data0)
   452  
   453  	return nil
   454  }
   455  
   456  // encodeFile writes to w a representation of the file sufficient to
   457  // faithfully restore position information about all needed offsets.
   458  // Mutates the needed array.
   459  func (p *iexporter) encodeFile(w *intWriter, file *token.File, needed []uint64) {
   460  	_ = needed[0] // precondition: needed is non-empty
   461  
   462  	w.uint64(p.stringOff(file.Name()))
   463  
   464  	size := uint64(file.Size())
   465  	w.uint64(size)
   466  
   467  	// Sort the set of needed offsets. Duplicates are harmless.
   468  	slices.Sort(needed)
   469  
   470  	lines := file.Lines() // byte offset of each line start
   471  	w.uint64(uint64(len(lines)))
   472  
   473  	// Rather than record the entire array of line start offsets,
   474  	// we save only a sparse list of (index, offset) pairs for
   475  	// the start of each line that contains a needed position.
   476  	var sparse [][2]int // (index, offset) pairs
   477  outer:
   478  	for i, lineStart := range lines {
   479  		lineEnd := size
   480  		if i < len(lines)-1 {
   481  			lineEnd = uint64(lines[i+1])
   482  		}
   483  		// Does this line contains a needed offset?
   484  		if needed[0] < lineEnd {
   485  			sparse = append(sparse, [2]int{i, lineStart})
   486  			for needed[0] < lineEnd {
   487  				needed = needed[1:]
   488  				if len(needed) == 0 {
   489  					break outer
   490  				}
   491  			}
   492  		}
   493  	}
   494  
   495  	// Delta-encode the columns.
   496  	w.uint64(uint64(len(sparse)))
   497  	var prev [2]int
   498  	for _, pair := range sparse {
   499  		w.uint64(uint64(pair[0] - prev[0]))
   500  		w.uint64(uint64(pair[1] - prev[1]))
   501  		prev = pair
   502  	}
   503  }
   504  
   505  // writeIndex writes out an object index. mainIndex indicates whether
   506  // we're writing out the main index, which is also read by
   507  // non-compiler tools and includes a complete package description
   508  // (i.e., name and height).
   509  func (w *exportWriter) writeIndex(index map[types.Object]uint64) {
   510  	type pkgObj struct {
   511  		obj  types.Object
   512  		name string // qualified name; differs from obj.Name for type params
   513  	}
   514  	// Build a map from packages to objects from that package.
   515  	pkgObjs := map[*types.Package][]pkgObj{}
   516  
   517  	// For the main index, make sure to include every package that
   518  	// we reference, even if we're not exporting (or reexporting)
   519  	// any symbols from it.
   520  	if w.p.localpkg != nil {
   521  		pkgObjs[w.p.localpkg] = nil
   522  	}
   523  	for pkg := range w.p.allPkgs {
   524  		pkgObjs[pkg] = nil
   525  	}
   526  
   527  	for obj := range index {
   528  		name := w.p.exportName(obj)
   529  		pkgObjs[obj.Pkg()] = append(pkgObjs[obj.Pkg()], pkgObj{obj, name})
   530  	}
   531  
   532  	var pkgs []*types.Package
   533  	for pkg, objs := range pkgObjs {
   534  		pkgs = append(pkgs, pkg)
   535  
   536  		sort.Slice(objs, func(i, j int) bool {
   537  			return objs[i].name < objs[j].name
   538  		})
   539  	}
   540  
   541  	sort.Slice(pkgs, func(i, j int) bool {
   542  		return w.exportPath(pkgs[i]) < w.exportPath(pkgs[j])
   543  	})
   544  
   545  	w.uint64(uint64(len(pkgs)))
   546  	for _, pkg := range pkgs {
   547  		w.string(w.exportPath(pkg))
   548  		w.string(pkg.Name())
   549  		w.uint64(uint64(0)) // package height is not needed for go/types
   550  
   551  		objs := pkgObjs[pkg]
   552  		w.uint64(uint64(len(objs)))
   553  		for _, obj := range objs {
   554  			w.string(obj.name)
   555  			w.uint64(index[obj.obj])
   556  		}
   557  	}
   558  }
   559  
   560  // exportName returns the 'exported' name of an object. It differs from
   561  // obj.Name() only for type parameters (see tparamExportName for details).
   562  func (p *iexporter) exportName(obj types.Object) (res string) {
   563  	if name := p.tparamNames[obj]; name != "" {
   564  		return name
   565  	}
   566  	return obj.Name()
   567  }
   568  
   569  type iexporter struct {
   570  	fset    *token.FileSet
   571  	version int
   572  
   573  	shallow    bool                // don't put types from other packages in the index
   574  	objEncoder *objectpath.Encoder // encodes objects from other packages in shallow mode; lazily allocated
   575  	localpkg   *types.Package      // (nil in bundle mode)
   576  
   577  	// allPkgs tracks all packages that have been referenced by
   578  	// the export data, so we can ensure to include them in the
   579  	// main index.
   580  	allPkgs map[*types.Package]bool
   581  
   582  	declTodo objQueue
   583  
   584  	strings     intWriter
   585  	stringIndex map[string]uint64
   586  
   587  	// In shallow mode, object positions are encoded as (file, offset).
   588  	// Each file is recorded as a line-number table.
   589  	// Only the lines of needed positions are saved faithfully.
   590  	fileInfo  map[*token.File]uint64 // value is index in fileInfos
   591  	fileInfos []*filePositions
   592  
   593  	data0       intWriter
   594  	declIndex   map[types.Object]uint64
   595  	tparamNames map[types.Object]string // typeparam->exported name
   596  	typIndex    map[types.Type]uint64
   597  
   598  	indent int // for tracing support
   599  }
   600  
   601  type filePositions struct {
   602  	file   *token.File
   603  	needed []uint64 // unordered list of needed file offsets
   604  }
   605  
   606  func (p *iexporter) trace(format string, args ...any) {
   607  	if !trace {
   608  		// Call sites should also be guarded, but having this check here allows
   609  		// easily enabling/disabling debug trace statements.
   610  		return
   611  	}
   612  	fmt.Printf(strings.Repeat("..", p.indent)+format+"\n", args...)
   613  }
   614  
   615  // objectpathEncoder returns the lazily allocated objectpath.Encoder to use
   616  // when encoding objects in other packages during shallow export.
   617  //
   618  // Using a shared Encoder amortizes some of cost of objectpath search.
   619  func (p *iexporter) objectpathEncoder() *objectpath.Encoder {
   620  	if p.objEncoder == nil {
   621  		p.objEncoder = new(objectpath.Encoder)
   622  	}
   623  	return p.objEncoder
   624  }
   625  
   626  // stringOff returns the offset of s within the string section.
   627  // If not already present, it's added to the end.
   628  func (p *iexporter) stringOff(s string) uint64 {
   629  	off, ok := p.stringIndex[s]
   630  	if !ok {
   631  		off = uint64(p.strings.Len())
   632  		p.stringIndex[s] = off
   633  
   634  		p.strings.uint64(uint64(len(s)))
   635  		p.strings.WriteString(s)
   636  	}
   637  	return off
   638  }
   639  
   640  // fileIndexAndOffset returns the index of the token.File and the byte offset of pos within it.
   641  func (p *iexporter) fileIndexAndOffset(file *token.File, pos token.Pos) (uint64, uint64) {
   642  	index, ok := p.fileInfo[file]
   643  	if !ok {
   644  		index = uint64(len(p.fileInfo))
   645  		p.fileInfos = append(p.fileInfos, &filePositions{file: file})
   646  		if p.fileInfo == nil {
   647  			p.fileInfo = make(map[*token.File]uint64)
   648  		}
   649  		p.fileInfo[file] = index
   650  	}
   651  	// Record each needed offset.
   652  	info := p.fileInfos[index]
   653  	offset := uint64(file.Offset(pos))
   654  	info.needed = append(info.needed, offset)
   655  
   656  	return index, offset
   657  }
   658  
   659  // pushDecl adds n to the declaration work queue, if not already present.
   660  func (p *iexporter) pushDecl(obj types.Object) {
   661  	// Package unsafe is known to the compiler and predeclared.
   662  	// Caller should not ask us to do export it.
   663  	if obj.Pkg() == types.Unsafe {
   664  		panic("cannot export package unsafe")
   665  	}
   666  
   667  	// Shallow export data: don't index decls from other packages.
   668  	if p.shallow && obj.Pkg() != p.localpkg {
   669  		return
   670  	}
   671  
   672  	if _, ok := p.declIndex[obj]; ok {
   673  		return
   674  	}
   675  
   676  	p.declIndex[obj] = ^uint64(0) // mark obj present in work queue
   677  	p.declTodo.pushTail(obj)
   678  }
   679  
   680  // exportWriter handles writing out individual data section chunks.
   681  type exportWriter struct {
   682  	p *iexporter
   683  
   684  	data       intWriter
   685  	prevFile   string
   686  	prevLine   int64
   687  	prevColumn int64
   688  }
   689  
   690  func (w *exportWriter) exportPath(pkg *types.Package) string {
   691  	if pkg == w.p.localpkg {
   692  		return ""
   693  	}
   694  	return pkg.Path()
   695  }
   696  
   697  func (p *iexporter) doDecl(obj types.Object) {
   698  	if trace {
   699  		p.trace("exporting decl %v (%T)", obj, obj)
   700  		p.indent++
   701  		defer func() {
   702  			p.indent--
   703  			p.trace("=> %s", obj)
   704  		}()
   705  	}
   706  	w := p.newWriter()
   707  
   708  	switch obj := obj.(type) {
   709  	case *types.Var:
   710  		w.tag(varTag)
   711  		w.pos(obj.Pos())
   712  		w.typ(obj.Type(), obj.Pkg())
   713  
   714  	case *types.Func:
   715  		sig, _ := obj.Type().(*types.Signature)
   716  		if sig.Recv() != nil {
   717  			// We shouldn't see methods in the package scope,
   718  			// but the type checker may repair "func () F() {}"
   719  			// to "func (Invalid) F()" and then treat it like "func F()",
   720  			// so allow that. See golang/go#57729.
   721  			if sig.Recv().Type() != types.Typ[types.Invalid] {
   722  				panic(internalErrorf("unexpected method: %v", sig))
   723  			}
   724  		}
   725  
   726  		// Function.
   727  		if sig.TypeParams().Len() == 0 {
   728  			w.tag(funcTag)
   729  		} else {
   730  			w.tag(genericFuncTag)
   731  		}
   732  		w.pos(obj.Pos())
   733  		// The tparam list of the function type is the declaration of the type
   734  		// params. So, write out the type params right now. Then those type params
   735  		// will be referenced via their type offset (via typOff) in all other
   736  		// places in the signature and function where they are used.
   737  		//
   738  		// While importing the type parameters, tparamList computes and records
   739  		// their export name, so that it can be later used when writing the index.
   740  		if tparams := sig.TypeParams(); tparams.Len() > 0 {
   741  			w.tparamList(obj.Name(), tparams, obj.Pkg())
   742  		}
   743  		w.signature(sig)
   744  
   745  	case *types.Const:
   746  		w.tag(constTag)
   747  		w.pos(obj.Pos())
   748  		w.value(obj.Type(), obj.Val())
   749  
   750  	case *types.TypeName:
   751  		t := obj.Type()
   752  
   753  		if tparam, ok := types.Unalias(t).(*types.TypeParam); ok {
   754  			w.tag(typeParamTag)
   755  			w.pos(obj.Pos())
   756  			constraint := tparam.Constraint()
   757  			if p.version >= iexportVersionGo1_18 {
   758  				implicit := false
   759  				if iface, _ := types.Unalias(constraint).(*types.Interface); iface != nil {
   760  					implicit = iface.IsImplicit()
   761  				}
   762  				w.bool(implicit)
   763  			}
   764  			w.typ(constraint, obj.Pkg())
   765  			break
   766  		}
   767  
   768  		if obj.IsAlias() {
   769  			alias, materialized := t.(*types.Alias) // perhaps false for certain built-ins?
   770  
   771  			var tparams *types.TypeParamList
   772  			if materialized {
   773  				tparams = alias.TypeParams()
   774  			}
   775  			if tparams.Len() == 0 {
   776  				w.tag(aliasTag)
   777  			} else {
   778  				w.tag(genericAliasTag)
   779  			}
   780  			w.pos(obj.Pos())
   781  			if tparams.Len() > 0 {
   782  				w.tparamList(obj.Name(), tparams, obj.Pkg())
   783  			}
   784  			if materialized {
   785  				// Preserve materialized aliases,
   786  				// even of non-exported types.
   787  				t = alias.Rhs()
   788  			}
   789  			w.typ(t, obj.Pkg())
   790  			break
   791  		}
   792  
   793  		// Defined type.
   794  		named, ok := t.(*types.Named)
   795  		if !ok {
   796  			panic(internalErrorf("%s is not a defined type", t))
   797  		}
   798  
   799  		if named.TypeParams().Len() == 0 {
   800  			w.tag(typeTag)
   801  		} else {
   802  			w.tag(genericTypeTag)
   803  		}
   804  		w.pos(obj.Pos())
   805  
   806  		if named.TypeParams().Len() > 0 {
   807  			// While importing the type parameters, tparamList computes and records
   808  			// their export name, so that it can be later used when writing the index.
   809  			w.tparamList(obj.Name(), named.TypeParams(), obj.Pkg())
   810  		}
   811  
   812  		underlying := named.Underlying()
   813  		w.typ(underlying, obj.Pkg())
   814  
   815  		if types.IsInterface(t) {
   816  			break
   817  		}
   818  
   819  		n := named.NumMethods()
   820  		w.uint64(uint64(n))
   821  		for i := range n {
   822  			m := named.Method(i)
   823  			w.pos(m.Pos())
   824  			w.string(m.Name())
   825  			sig, _ := m.Type().(*types.Signature)
   826  			if w.p.version >= iexportVersionGenericMethods && w.bool(sig.TypeParams().Len() > 0) {
   827  				w.tparamList(obj.Name()+"."+m.Name(), sig.TypeParams(), obj.Pkg())
   828  			}
   829  
   830  			// Receiver type parameters are type arguments of the receiver type, so
   831  			// their name must be qualified before exporting recv.
   832  			if rparams := sig.RecvTypeParams(); rparams.Len() > 0 {
   833  				prefix := obj.Name() + "." + m.Name()
   834  				for rparam := range rparams.TypeParams() {
   835  					name := tparamExportName(prefix, rparam)
   836  					w.p.tparamNames[rparam.Obj()] = name
   837  				}
   838  			}
   839  			w.param(sig.Recv())
   840  			w.signature(sig)
   841  		}
   842  
   843  	default:
   844  		panic(internalErrorf("unexpected object: %v", obj))
   845  	}
   846  
   847  	p.declIndex[obj] = w.flush()
   848  }
   849  
   850  func (w *exportWriter) tag(tag byte) {
   851  	w.data.WriteByte(tag)
   852  }
   853  
   854  func (w *exportWriter) pos(pos token.Pos) {
   855  	if w.p.shallow {
   856  		w.posV2(pos)
   857  	} else if w.p.version >= iexportVersionPosCol {
   858  		w.posV1(pos)
   859  	} else {
   860  		w.posV0(pos)
   861  	}
   862  }
   863  
   864  // posV2 encoding (used only in shallow mode) records positions as
   865  // (file, offset), where file is the index in the token.File table
   866  // (which records the file name and newline offsets) and offset is a
   867  // byte offset. It effectively ignores //line directives.
   868  func (w *exportWriter) posV2(pos token.Pos) {
   869  	if pos == token.NoPos {
   870  		w.uint64(0)
   871  		return
   872  	}
   873  	file := w.p.fset.File(pos) // fset must be non-nil
   874  	index, offset := w.p.fileIndexAndOffset(file, pos)
   875  	w.uint64(1 + index)
   876  	w.uint64(offset)
   877  }
   878  
   879  func (w *exportWriter) posV1(pos token.Pos) {
   880  	if w.p.fset == nil {
   881  		w.int64(0)
   882  		return
   883  	}
   884  
   885  	p := w.p.fset.Position(pos)
   886  	file := p.Filename
   887  	line := int64(p.Line)
   888  	column := int64(p.Column)
   889  
   890  	deltaColumn := (column - w.prevColumn) << 1
   891  	deltaLine := (line - w.prevLine) << 1
   892  
   893  	if file != w.prevFile {
   894  		deltaLine |= 1
   895  	}
   896  	if deltaLine != 0 {
   897  		deltaColumn |= 1
   898  	}
   899  
   900  	w.int64(deltaColumn)
   901  	if deltaColumn&1 != 0 {
   902  		w.int64(deltaLine)
   903  		if deltaLine&1 != 0 {
   904  			w.string(file)
   905  		}
   906  	}
   907  
   908  	w.prevFile = file
   909  	w.prevLine = line
   910  	w.prevColumn = column
   911  }
   912  
   913  func (w *exportWriter) posV0(pos token.Pos) {
   914  	if w.p.fset == nil {
   915  		w.int64(0)
   916  		return
   917  	}
   918  
   919  	p := w.p.fset.Position(pos)
   920  	file := p.Filename
   921  	line := int64(p.Line)
   922  
   923  	// When file is the same as the last position (common case),
   924  	// we can save a few bytes by delta encoding just the line
   925  	// number.
   926  	//
   927  	// Note: Because data objects may be read out of order (or not
   928  	// at all), we can only apply delta encoding within a single
   929  	// object. This is handled implicitly by tracking prevFile and
   930  	// prevLine as fields of exportWriter.
   931  
   932  	if file == w.prevFile {
   933  		delta := line - w.prevLine
   934  		w.int64(delta)
   935  		if delta == deltaNewFile {
   936  			w.int64(-1)
   937  		}
   938  	} else {
   939  		w.int64(deltaNewFile)
   940  		w.int64(line) // line >= 0
   941  		w.string(file)
   942  		w.prevFile = file
   943  	}
   944  	w.prevLine = line
   945  }
   946  
   947  func (w *exportWriter) pkg(pkg *types.Package) {
   948  	if pkg == nil {
   949  		// [exportWriter.typ] accepts a nil pkg only for types
   950  		// of constants, which cannot contain named objects
   951  		// such as fields or methods and thus should never
   952  		// reach this method (#76222).
   953  		panic("nil package")
   954  	}
   955  	// Ensure any referenced packages are declared in the main index.
   956  	w.p.allPkgs[pkg] = true
   957  
   958  	w.string(w.exportPath(pkg))
   959  }
   960  
   961  func (w *exportWriter) qualifiedType(obj *types.TypeName) {
   962  	name := w.p.exportName(obj)
   963  
   964  	// Ensure any referenced declarations are written out too.
   965  	w.p.pushDecl(obj)
   966  	w.string(name)
   967  	w.pkg(obj.Pkg())
   968  }
   969  
   970  // typ emits the specified type.
   971  //
   972  // Objects within the type (struct fields and interface methods) are
   973  // qualified by pkg. It may be nil if the type cannot contain objects,
   974  // such as the type of a constant.
   975  func (w *exportWriter) typ(t types.Type, pkg *types.Package) {
   976  	w.data.uint64(w.p.typOff(t, pkg))
   977  }
   978  
   979  func (p *iexporter) newWriter() *exportWriter {
   980  	return &exportWriter{p: p}
   981  }
   982  
   983  func (w *exportWriter) flush() uint64 {
   984  	off := uint64(w.p.data0.Len())
   985  	io.Copy(&w.p.data0, &w.data)
   986  	return off
   987  }
   988  
   989  func (p *iexporter) typOff(t types.Type, pkg *types.Package) uint64 {
   990  	off, ok := p.typIndex[t]
   991  	if !ok {
   992  		w := p.newWriter()
   993  		w.doTyp(t, pkg)
   994  		off = predeclReserved + w.flush()
   995  		p.typIndex[t] = off
   996  	}
   997  	return off
   998  }
   999  
  1000  func (w *exportWriter) startType(k itag) {
  1001  	w.data.uint64(uint64(k))
  1002  }
  1003  
  1004  // doTyp is the implementation of [exportWriter.typ].
  1005  func (w *exportWriter) doTyp(t types.Type, pkg *types.Package) {
  1006  	if trace {
  1007  		w.p.trace("exporting type %s (%T)", t, t)
  1008  		w.p.indent++
  1009  		defer func() {
  1010  			w.p.indent--
  1011  			w.p.trace("=> %s", t)
  1012  		}()
  1013  	}
  1014  	switch t := t.(type) {
  1015  	case *types.Alias:
  1016  		if targs := t.TypeArgs(); targs.Len() > 0 {
  1017  			w.startType(instanceType)
  1018  			w.pos(t.Obj().Pos())
  1019  			w.typeList(targs, pkg)
  1020  			w.typ(t.Origin(), pkg)
  1021  			return
  1022  		}
  1023  		w.startType(aliasType)
  1024  		w.qualifiedType(t.Obj())
  1025  
  1026  	case *types.Named:
  1027  		if targs := t.TypeArgs(); targs.Len() > 0 {
  1028  			w.startType(instanceType)
  1029  			// TODO(rfindley): investigate if this position is correct, and if it
  1030  			// matters.
  1031  			w.pos(t.Obj().Pos())
  1032  			w.typeList(targs, pkg)
  1033  			w.typ(t.Origin(), pkg)
  1034  			return
  1035  		}
  1036  		w.startType(definedType)
  1037  		w.qualifiedType(t.Obj())
  1038  
  1039  	case *types.TypeParam:
  1040  		w.startType(typeParamType)
  1041  		w.qualifiedType(t.Obj())
  1042  
  1043  	case *types.Pointer:
  1044  		w.startType(pointerType)
  1045  		w.typ(t.Elem(), pkg)
  1046  
  1047  	case *types.Slice:
  1048  		w.startType(sliceType)
  1049  		w.typ(t.Elem(), pkg)
  1050  
  1051  	case *types.Array:
  1052  		w.startType(arrayType)
  1053  		w.uint64(uint64(t.Len()))
  1054  		w.typ(t.Elem(), pkg)
  1055  
  1056  	case *types.Chan:
  1057  		w.startType(chanType)
  1058  		// 1 RecvOnly; 2 SendOnly; 3 SendRecv
  1059  		var dir uint64
  1060  		switch t.Dir() {
  1061  		case types.RecvOnly:
  1062  			dir = 1
  1063  		case types.SendOnly:
  1064  			dir = 2
  1065  		case types.SendRecv:
  1066  			dir = 3
  1067  		}
  1068  		w.uint64(dir)
  1069  		w.typ(t.Elem(), pkg)
  1070  
  1071  	case *types.Map:
  1072  		w.startType(mapType)
  1073  		w.typ(t.Key(), pkg)
  1074  		w.typ(t.Elem(), pkg)
  1075  
  1076  	case *types.Signature:
  1077  		w.startType(signatureType)
  1078  		w.pkg(pkg) // qualifies param/result vars
  1079  		w.signature(t)
  1080  
  1081  	case *types.Struct:
  1082  		w.startType(structType)
  1083  		n := t.NumFields()
  1084  		// Even for struct{} we must emit some qualifying package, because that's
  1085  		// what the compiler does, and thus that's what the importer expects.
  1086  		fieldPkg := pkg
  1087  		if n > 0 {
  1088  			fieldPkg = t.Field(0).Pkg()
  1089  		}
  1090  		if fieldPkg == nil {
  1091  			// TODO(rfindley): improve this very hacky logic.
  1092  			//
  1093  			// The importer expects a package to be set for all struct types, even
  1094  			// those with no fields. A better encoding might be to set NumFields
  1095  			// before pkg. setPkg panics with a nil package, which may be possible
  1096  			// to reach with invalid packages (and perhaps valid packages, too?), so
  1097  			// (arbitrarily) set the localpkg if available.
  1098  			//
  1099  			// Alternatively, we may be able to simply guarantee that pkg != nil, by
  1100  			// reconsidering the encoding of constant values.
  1101  			if w.p.shallow {
  1102  				fieldPkg = w.p.localpkg
  1103  			} else {
  1104  				panic(internalErrorf("no package to set for empty struct"))
  1105  			}
  1106  		}
  1107  		w.pkg(fieldPkg)
  1108  		w.uint64(uint64(n))
  1109  
  1110  		for i := range n {
  1111  			f := t.Field(i)
  1112  			if w.p.shallow {
  1113  				w.objectPath(f)
  1114  			}
  1115  			w.pos(f.Pos())
  1116  			w.string(f.Name()) // unexported fields implicitly qualified by prior setPkg
  1117  			w.typ(f.Type(), fieldPkg)
  1118  			w.bool(f.Anonymous())
  1119  			w.string(t.Tag(i)) // note (or tag)
  1120  		}
  1121  
  1122  	case *types.Interface:
  1123  		w.startType(interfaceType)
  1124  		w.pkg(pkg) // qualifies unexported method funcs
  1125  
  1126  		n := t.NumEmbeddeds()
  1127  		w.uint64(uint64(n))
  1128  		for i := 0; i < n; i++ {
  1129  			ft := t.EmbeddedType(i)
  1130  			if named, _ := types.Unalias(ft).(*types.Named); named != nil {
  1131  				w.pos(named.Obj().Pos())
  1132  			} else {
  1133  				// e.g. ~int
  1134  				w.pos(token.NoPos)
  1135  			}
  1136  			w.typ(ft, pkg)
  1137  		}
  1138  
  1139  		// See comment for struct fields. In shallow mode we change the encoding
  1140  		// for interface methods that are promoted from other packages.
  1141  
  1142  		n = t.NumExplicitMethods()
  1143  		w.uint64(uint64(n))
  1144  		for i := 0; i < n; i++ {
  1145  			m := t.ExplicitMethod(i)
  1146  			if w.p.shallow {
  1147  				w.objectPath(m)
  1148  			}
  1149  			w.pos(m.Pos())
  1150  			w.string(m.Name())
  1151  			sig, _ := m.Type().(*types.Signature)
  1152  			w.signature(sig)
  1153  		}
  1154  
  1155  	case *types.Union:
  1156  		w.startType(unionType)
  1157  		nt := t.Len()
  1158  		w.uint64(uint64(nt))
  1159  		for i := range nt {
  1160  			term := t.Term(i)
  1161  			w.bool(term.Tilde())
  1162  			w.typ(term.Type(), pkg)
  1163  		}
  1164  
  1165  	default:
  1166  		panic(internalErrorf("unexpected type: %v, %v", t, reflect.TypeOf(t)))
  1167  	}
  1168  }
  1169  
  1170  // objectPath writes the package and objectPath to use to look up obj in a
  1171  // different package, when encoding in "shallow" mode.
  1172  //
  1173  // When doing a shallow import, the importer creates only the local package,
  1174  // and requests package symbols for dependencies from the client.
  1175  // However, certain types defined in the local package may hold objects defined
  1176  // (perhaps deeply) within another package.
  1177  //
  1178  // For example, consider the following:
  1179  //
  1180  //	package a
  1181  //	func F() chan * map[string] struct { X int }
  1182  //
  1183  //	package b
  1184  //	import "a"
  1185  //	var B = a.F()
  1186  //
  1187  // In this example, the type of b.B holds fields defined in package a.
  1188  // In order to have the correct canonical objects for the field defined in the
  1189  // type of B, they are encoded as objectPaths and later looked up in the
  1190  // importer. The same problem applies to interface methods.
  1191  func (w *exportWriter) objectPath(obj types.Object) {
  1192  	if obj.Pkg() == nil || obj.Pkg() == w.p.localpkg {
  1193  		// obj.Pkg() may be nil for the builtin error.Error.
  1194  		// In this case, or if obj is declared in the local package, no need to
  1195  		// encode.
  1196  		w.string("")
  1197  		return
  1198  	}
  1199  	objectPath, err := w.p.objectpathEncoder().For(obj)
  1200  	if err != nil {
  1201  		// Fall back to the empty string, which will cause the importer to create a
  1202  		// new object, which matches earlier behavior. Creating a new object is
  1203  		// sufficient for many purposes (such as type checking), but causes certain
  1204  		// references algorithms to fail (golang/go#60819). However, we didn't
  1205  		// notice this problem during months of gopls@v0.12.0 testing.
  1206  		//
  1207  		// TODO(golang/go#61674): this workaround is insufficient, as in the case
  1208  		// where the field forwarded from an instantiated type that may not appear
  1209  		// in the export data of the original package:
  1210  		//
  1211  		//  // package a
  1212  		//  type A[P any] struct{ F P }
  1213  		//
  1214  		//  // package b
  1215  		//  type B a.A[int]
  1216  		//
  1217  		// We need to update references algorithms not to depend on this
  1218  		// de-duplication, at which point we may want to simply remove the
  1219  		// workaround here.
  1220  		w.string("")
  1221  		return
  1222  	}
  1223  	w.string(string(objectPath))
  1224  	w.pkg(obj.Pkg())
  1225  }
  1226  
  1227  func (w *exportWriter) signature(sig *types.Signature) {
  1228  	w.paramList(sig.Params())
  1229  	w.paramList(sig.Results())
  1230  	if sig.Params().Len() > 0 {
  1231  		w.bool(sig.Variadic())
  1232  	}
  1233  }
  1234  
  1235  func (w *exportWriter) typeList(ts *types.TypeList, pkg *types.Package) {
  1236  	w.uint64(uint64(ts.Len()))
  1237  	for t := range ts.Types() {
  1238  		w.typ(t, pkg)
  1239  	}
  1240  }
  1241  
  1242  func (w *exportWriter) tparamList(prefix string, list *types.TypeParamList, pkg *types.Package) {
  1243  	ll := uint64(list.Len())
  1244  	w.uint64(ll)
  1245  	for tparam := range list.TypeParams() {
  1246  		// Set the type parameter exportName before exporting its type.
  1247  		exportName := tparamExportName(prefix, tparam)
  1248  		w.p.tparamNames[tparam.Obj()] = exportName
  1249  		w.typ(tparam, pkg)
  1250  	}
  1251  }
  1252  
  1253  const blankMarker = "$"
  1254  
  1255  // tparamExportName returns the 'exported' name of a type parameter, which
  1256  // differs from its actual object name: it is prefixed with a qualifier, and
  1257  // blank type parameter names are disambiguated by their index in the type
  1258  // parameter list.
  1259  func tparamExportName(prefix string, tparam *types.TypeParam) string {
  1260  	assert(prefix != "")
  1261  	name := tparam.Obj().Name()
  1262  	if name == "_" {
  1263  		name = blankMarker + strconv.Itoa(tparam.Index())
  1264  	}
  1265  	return prefix + "." + name
  1266  }
  1267  
  1268  // tparamName returns the real name of a type parameter, after stripping its
  1269  // qualifying prefix and reverting blank-name encoding. See tparamExportName
  1270  // for details.
  1271  func tparamName(exportName string) string {
  1272  	// Remove the "path" from the type param name that makes it unique.
  1273  	ix := strings.LastIndex(exportName, ".")
  1274  	if ix < 0 {
  1275  		errorf("malformed type parameter export name %s: missing prefix", exportName)
  1276  	}
  1277  	name := exportName[ix+1:]
  1278  	if strings.HasPrefix(name, blankMarker) {
  1279  		return "_"
  1280  	}
  1281  	return name
  1282  }
  1283  
  1284  func (w *exportWriter) paramList(tup *types.Tuple) {
  1285  	n := tup.Len()
  1286  	w.uint64(uint64(n))
  1287  	for i := range n {
  1288  		w.param(tup.At(i))
  1289  	}
  1290  }
  1291  
  1292  func (w *exportWriter) param(obj types.Object) {
  1293  	w.pos(obj.Pos())
  1294  	w.localIdent(obj)
  1295  	w.typ(obj.Type(), obj.Pkg())
  1296  }
  1297  
  1298  func (w *exportWriter) value(typ types.Type, v constant.Value) {
  1299  	w.typ(typ, nil)
  1300  	if w.p.version >= iexportVersionGo1_18 {
  1301  		w.int64(int64(v.Kind()))
  1302  	}
  1303  
  1304  	if v.Kind() == constant.Unknown {
  1305  		// golang/go#60605: treat unknown constant values as if they have invalid type
  1306  		//
  1307  		// This loses some fidelity over the package type-checked from source, but that
  1308  		// is acceptable.
  1309  		//
  1310  		// TODO(rfindley): we should switch on the recorded constant kind rather
  1311  		// than the constant type
  1312  		return
  1313  	}
  1314  
  1315  	switch b := typ.Underlying().(*types.Basic); b.Info() & types.IsConstType {
  1316  	case types.IsBoolean:
  1317  		w.bool(constant.BoolVal(v))
  1318  	case types.IsInteger:
  1319  		var i big.Int
  1320  		if i64, exact := constant.Int64Val(v); exact {
  1321  			i.SetInt64(i64)
  1322  		} else if ui64, exact := constant.Uint64Val(v); exact {
  1323  			i.SetUint64(ui64)
  1324  		} else {
  1325  			i.SetString(v.ExactString(), 10)
  1326  		}
  1327  		w.mpint(&i, typ)
  1328  	case types.IsFloat:
  1329  		f := constantToFloat(v)
  1330  		w.mpfloat(f, typ)
  1331  	case types.IsComplex:
  1332  		w.mpfloat(constantToFloat(constant.Real(v)), typ)
  1333  		w.mpfloat(constantToFloat(constant.Imag(v)), typ)
  1334  	case types.IsString:
  1335  		w.string(constant.StringVal(v))
  1336  	default:
  1337  		if b.Kind() == types.Invalid {
  1338  			// package contains type errors
  1339  			break
  1340  		}
  1341  		panic(internalErrorf("unexpected type %v (%v)", typ, typ.Underlying()))
  1342  	}
  1343  }
  1344  
  1345  // constantToFloat converts a constant.Value with kind constant.Float to a
  1346  // big.Float.
  1347  func constantToFloat(x constant.Value) *big.Float {
  1348  	x = constant.ToFloat(x)
  1349  	// Use the same floating-point precision (512) as cmd/compile
  1350  	// (see Mpprec in cmd/compile/internal/gc/mpfloat.go).
  1351  	const mpprec = 512
  1352  	var f big.Float
  1353  	f.SetPrec(mpprec)
  1354  	if v, exact := constant.Float64Val(x); exact {
  1355  		// float64
  1356  		f.SetFloat64(v)
  1357  	} else if num, denom := constant.Num(x), constant.Denom(x); num.Kind() == constant.Int {
  1358  		// TODO(gri): add big.Rat accessor to constant.Value.
  1359  		n := valueToRat(num)
  1360  		d := valueToRat(denom)
  1361  		f.SetRat(n.Quo(n, d))
  1362  	} else {
  1363  		// Value too large to represent as a fraction => inaccessible.
  1364  		// TODO(gri): add big.Float accessor to constant.Value.
  1365  		_, ok := f.SetString(x.ExactString())
  1366  		assert(ok)
  1367  	}
  1368  	return &f
  1369  }
  1370  
  1371  func valueToRat(x constant.Value) *big.Rat {
  1372  	// Convert little-endian to big-endian.
  1373  	// I can't believe this is necessary.
  1374  	bytes := constant.Bytes(x)
  1375  	for i := 0; i < len(bytes)/2; i++ {
  1376  		bytes[i], bytes[len(bytes)-1-i] = bytes[len(bytes)-1-i], bytes[i]
  1377  	}
  1378  	return new(big.Rat).SetInt(new(big.Int).SetBytes(bytes))
  1379  }
  1380  
  1381  // mpint exports a multi-precision integer.
  1382  //
  1383  // For unsigned types, small values are written out as a single
  1384  // byte. Larger values are written out as a length-prefixed big-endian
  1385  // byte string, where the length prefix is encoded as its complement.
  1386  // For example, bytes 0, 1, and 2 directly represent the integer
  1387  // values 0, 1, and 2; while bytes 255, 254, and 253 indicate a 1-,
  1388  // 2-, and 3-byte big-endian string follow.
  1389  //
  1390  // Encoding for signed types use the same general approach as for
  1391  // unsigned types, except small values use zig-zag encoding and the
  1392  // bottom bit of length prefix byte for large values is reserved as a
  1393  // sign bit.
  1394  //
  1395  // The exact boundary between small and large encodings varies
  1396  // according to the maximum number of bytes needed to encode a value
  1397  // of type typ. As a special case, 8-bit types are always encoded as a
  1398  // single byte.
  1399  //
  1400  // TODO(mdempsky): Is this level of complexity really worthwhile?
  1401  func (w *exportWriter) mpint(x *big.Int, typ types.Type) {
  1402  	basic, ok := typ.Underlying().(*types.Basic)
  1403  	if !ok {
  1404  		panic(internalErrorf("unexpected type %v (%T)", typ.Underlying(), typ.Underlying()))
  1405  	}
  1406  
  1407  	signed, maxBytes := intSize(basic)
  1408  
  1409  	negative := x.Sign() < 0
  1410  	if !signed && negative {
  1411  		panic(internalErrorf("negative unsigned integer; type %v, value %v", typ, x))
  1412  	}
  1413  
  1414  	b := x.Bytes()
  1415  	if len(b) > 0 && b[0] == 0 {
  1416  		panic(internalErrorf("leading zeros"))
  1417  	}
  1418  	if uint(len(b)) > maxBytes {
  1419  		panic(internalErrorf("bad mpint length: %d > %d (type %v, value %v)", len(b), maxBytes, typ, x))
  1420  	}
  1421  
  1422  	maxSmall := 256 - maxBytes
  1423  	if signed {
  1424  		maxSmall = 256 - 2*maxBytes
  1425  	}
  1426  	if maxBytes == 1 {
  1427  		maxSmall = 256
  1428  	}
  1429  
  1430  	// Check if x can use small value encoding.
  1431  	if len(b) <= 1 {
  1432  		var ux uint
  1433  		if len(b) == 1 {
  1434  			ux = uint(b[0])
  1435  		}
  1436  		if signed {
  1437  			ux <<= 1
  1438  			if negative {
  1439  				ux--
  1440  			}
  1441  		}
  1442  		if ux < maxSmall {
  1443  			w.data.WriteByte(byte(ux))
  1444  			return
  1445  		}
  1446  	}
  1447  
  1448  	n := 256 - uint(len(b))
  1449  	if signed {
  1450  		n = 256 - 2*uint(len(b))
  1451  		if negative {
  1452  			n |= 1
  1453  		}
  1454  	}
  1455  	if n < maxSmall || n >= 256 {
  1456  		panic(internalErrorf("encoding mistake: %d, %v, %v => %d", len(b), signed, negative, n))
  1457  	}
  1458  
  1459  	w.data.WriteByte(byte(n))
  1460  	w.data.Write(b)
  1461  }
  1462  
  1463  // mpfloat exports a multi-precision floating point number.
  1464  //
  1465  // The number's value is decomposed into mantissa × 2**exponent, where
  1466  // mantissa is an integer. The value is written out as mantissa (as a
  1467  // multi-precision integer) and then the exponent, except exponent is
  1468  // omitted if mantissa is zero.
  1469  func (w *exportWriter) mpfloat(f *big.Float, typ types.Type) {
  1470  	if f.IsInf() {
  1471  		panic("infinite constant")
  1472  	}
  1473  
  1474  	// Break into f = mant × 2**exp, with 0.5 <= mant < 1.
  1475  	var mant big.Float
  1476  	exp := int64(f.MantExp(&mant))
  1477  
  1478  	// Scale so that mant is an integer.
  1479  	prec := mant.MinPrec()
  1480  	mant.SetMantExp(&mant, int(prec))
  1481  	exp -= int64(prec)
  1482  
  1483  	manti, acc := mant.Int(nil)
  1484  	if acc != big.Exact {
  1485  		panic(internalErrorf("mantissa scaling failed for %f (%s)", f, acc))
  1486  	}
  1487  	w.mpint(manti, typ)
  1488  	if manti.Sign() != 0 {
  1489  		w.int64(exp)
  1490  	}
  1491  }
  1492  
  1493  func (w *exportWriter) bool(b bool) bool {
  1494  	var x uint64
  1495  	if b {
  1496  		x = 1
  1497  	}
  1498  	w.uint64(x)
  1499  	return b
  1500  }
  1501  
  1502  func (w *exportWriter) int64(x int64)   { w.data.int64(x) }
  1503  func (w *exportWriter) uint64(x uint64) { w.data.uint64(x) }
  1504  func (w *exportWriter) string(s string) { w.uint64(w.p.stringOff(s)) }
  1505  
  1506  func (w *exportWriter) localIdent(obj types.Object) {
  1507  	// Anonymous parameters.
  1508  	if obj == nil {
  1509  		w.string("")
  1510  		return
  1511  	}
  1512  
  1513  	name := obj.Name()
  1514  	if name == "_" {
  1515  		w.string("_")
  1516  		return
  1517  	}
  1518  
  1519  	w.string(name)
  1520  }
  1521  
  1522  type intWriter struct {
  1523  	bytes.Buffer
  1524  }
  1525  
  1526  func (w *intWriter) int64(x int64) {
  1527  	var buf [binary.MaxVarintLen64]byte
  1528  	n := binary.PutVarint(buf[:], x)
  1529  	w.Write(buf[:n])
  1530  }
  1531  
  1532  func (w *intWriter) uint64(x uint64) {
  1533  	var buf [binary.MaxVarintLen64]byte
  1534  	n := binary.PutUvarint(buf[:], x)
  1535  	w.Write(buf[:n])
  1536  }
  1537  
  1538  func assert(cond bool) {
  1539  	if !cond {
  1540  		panic("internal error: assertion failed")
  1541  	}
  1542  }
  1543  
  1544  // The below is copied from go/src/cmd/compile/internal/gc/syntax.go.
  1545  
  1546  // objQueue is a FIFO queue of types.Object. The zero value of objQueue is
  1547  // a ready-to-use empty queue.
  1548  type objQueue struct {
  1549  	ring       []types.Object
  1550  	head, tail int
  1551  }
  1552  
  1553  // empty returns true if q contains no Nodes.
  1554  func (q *objQueue) empty() bool {
  1555  	return q.head == q.tail
  1556  }
  1557  
  1558  // pushTail appends n to the tail of the queue.
  1559  func (q *objQueue) pushTail(obj types.Object) {
  1560  	if len(q.ring) == 0 {
  1561  		q.ring = make([]types.Object, 16)
  1562  	} else if q.head+len(q.ring) == q.tail {
  1563  		// Grow the ring.
  1564  		nring := make([]types.Object, len(q.ring)*2)
  1565  		// Copy the old elements.
  1566  		part := q.ring[q.head%len(q.ring):]
  1567  		if q.tail-q.head <= len(part) {
  1568  			part = part[:q.tail-q.head]
  1569  			copy(nring, part)
  1570  		} else {
  1571  			pos := copy(nring, part)
  1572  			copy(nring[pos:], q.ring[:q.tail%len(q.ring)])
  1573  		}
  1574  		q.ring, q.head, q.tail = nring, 0, q.tail-q.head
  1575  	}
  1576  
  1577  	q.ring[q.tail%len(q.ring)] = obj
  1578  	q.tail++
  1579  }
  1580  
  1581  // popHead pops a node from the head of the queue. It panics if q is empty.
  1582  func (q *objQueue) popHead() types.Object {
  1583  	if q.empty() {
  1584  		panic("dequeue empty")
  1585  	}
  1586  	obj := q.ring[q.head%len(q.ring)]
  1587  	q.head++
  1588  	return obj
  1589  }
  1590  
  1591  // internalError represents an error generated inside this package.
  1592  type internalError string
  1593  
  1594  func (e internalError) Error() string { return "gcimporter: " + string(e) }
  1595  
  1596  // TODO(adonovan): make this call panic, so that it's symmetric with errorf.
  1597  // Otherwise it's easy to forget to do anything with the error.
  1598  //
  1599  // TODO(adonovan): also, consider switching the names "errorf" and
  1600  // "internalErrorf" as the former is used for bugs, whose cause is
  1601  // internal inconsistency, whereas the latter is used for ordinary
  1602  // situations like bad input, whose cause is external.
  1603  func internalErrorf(format string, args ...any) error {
  1604  	return internalError(fmt.Sprintf(format, args...))
  1605  }
  1606
View as plain text