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