1// Copyright 2018 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 import.
6// See cmd/compile/internal/gc/iexport.go for the export data format.
7
8package gcimporter
9
10import (
11	"bufio"
12	"bytes"
13	"encoding/binary"
14	"fmt"
15	"go/constant"
16	"go/token"
17	"go/types"
18	"io"
19	"math/big"
20	"sort"
21	"strings"
22)
23
24type intReader struct {
25	*bufio.Reader
26	path string
27}
28
29func (r *intReader) int64() int64 {
30	i, err := binary.ReadVarint(r.Reader)
31	if err != nil {
32		errorf("import %q: read varint error: %v", r.path, err)
33	}
34	return i
35}
36
37func (r *intReader) uint64() uint64 {
38	i, err := binary.ReadUvarint(r.Reader)
39	if err != nil {
40		errorf("import %q: read varint error: %v", r.path, err)
41	}
42	return i
43}
44
45// Keep this in sync with constants in iexport.go.
46const (
47	iexportVersionGo1_11   = 0
48	iexportVersionPosCol   = 1
49	iexportVersionGenerics = 2
50	iexportVersionGo1_18   = 2
51
52	iexportVersionCurrent = 2
53)
54
55type ident struct {
56	pkg  string
57	name string
58}
59
60const predeclReserved = 32
61
62type itag uint64
63
64const (
65	// Types
66	definedType itag = iota
67	pointerType
68	sliceType
69	arrayType
70	chanType
71	mapType
72	signatureType
73	structType
74	interfaceType
75	typeParamType
76	instanceType
77	unionType
78)
79
80// iImportData imports a package from the serialized package data
81// and returns the number of bytes consumed and a reference to the package.
82// If the export data version is not recognized or the format is otherwise
83// compromised, an error is returned.
84func iImportData(fset *token.FileSet, imports map[string]*types.Package, dataReader *bufio.Reader, path string) (pkg *types.Package, err error) {
85	const currentVersion = iexportVersionCurrent
86	version := int64(-1)
87	defer func() {
88		if e := recover(); e != nil {
89			if version > currentVersion {
90				err = fmt.Errorf("cannot import %q (%v), export data is newer version - update tool", path, e)
91			} else {
92				err = fmt.Errorf("cannot import %q (%v), possibly version skew - reinstall package", path, e)
93			}
94		}
95	}()
96
97	r := &intReader{dataReader, path}
98
99	version = int64(r.uint64())
100	switch version {
101	case iexportVersionGo1_18, iexportVersionPosCol, iexportVersionGo1_11:
102	default:
103		errorf("unknown iexport format version %d", version)
104	}
105
106	sLen := int64(r.uint64())
107	dLen := int64(r.uint64())
108
109	data := make([]byte, sLen+dLen)
110	if _, err := io.ReadFull(r, data); err != nil {
111		errorf("cannot read %d bytes of stringData and declData: %s", len(data), err)
112	}
113	stringData := data[:sLen]
114	declData := data[sLen:]
115
116	p := iimporter{
117		exportVersion: version,
118		ipath:         path,
119		version:       int(version),
120
121		stringData:  stringData,
122		stringCache: make(map[uint64]string),
123		pkgCache:    make(map[uint64]*types.Package),
124
125		declData: declData,
126		pkgIndex: make(map[*types.Package]map[string]uint64),
127		typCache: make(map[uint64]types.Type),
128		// Separate map for typeparams, keyed by their package and unique
129		// name (name with subscript).
130		tparamIndex: make(map[ident]types.Type),
131
132		fake: fakeFileSet{
133			fset:  fset,
134			files: make(map[string]*fileInfo),
135		},
136	}
137	defer p.fake.setLines() // set lines for files in fset
138
139	for i, pt := range predeclared {
140		p.typCache[uint64(i)] = pt
141	}
142
143	pkgList := make([]*types.Package, r.uint64())
144	for i := range pkgList {
145		pkgPathOff := r.uint64()
146		pkgPath := p.stringAt(pkgPathOff)
147		pkgName := p.stringAt(r.uint64())
148		_ = r.uint64() // package height; unused by go/types
149
150		if pkgPath == "" {
151			pkgPath = path
152		}
153		pkg := imports[pkgPath]
154		if pkg == nil {
155			pkg = types.NewPackage(pkgPath, pkgName)
156			imports[pkgPath] = pkg
157		} else if pkg.Name() != pkgName {
158			errorf("conflicting names %s and %s for package %q", pkg.Name(), pkgName, path)
159		}
160
161		p.pkgCache[pkgPathOff] = pkg
162
163		nameIndex := make(map[string]uint64)
164		for nSyms := r.uint64(); nSyms > 0; nSyms-- {
165			name := p.stringAt(r.uint64())
166			nameIndex[name] = r.uint64()
167		}
168
169		p.pkgIndex[pkg] = nameIndex
170		pkgList[i] = pkg
171	}
172
173	localpkg := pkgList[0]
174
175	names := make([]string, 0, len(p.pkgIndex[localpkg]))
176	for name := range p.pkgIndex[localpkg] {
177		names = append(names, name)
178	}
179	sort.Strings(names)
180	for _, name := range names {
181		p.doDecl(localpkg, name)
182	}
183
184	for _, typ := range p.interfaceList {
185		typ.Complete()
186	}
187
188	// record all referenced packages as imports
189	list := append(([]*types.Package)(nil), pkgList[1:]...)
190	sort.Sort(byPath(list))
191	localpkg.SetImports(list)
192
193	// package was imported completely and without errors
194	localpkg.MarkComplete()
195	return localpkg, nil
196}
197
198type iimporter struct {
199	exportVersion int64
200	ipath         string
201	version       int
202
203	stringData  []byte
204	stringCache map[uint64]string
205	pkgCache    map[uint64]*types.Package
206
207	declData    []byte
208	pkgIndex    map[*types.Package]map[string]uint64
209	typCache    map[uint64]types.Type
210	tparamIndex map[ident]types.Type
211
212	fake          fakeFileSet
213	interfaceList []*types.Interface
214}
215
216func (p *iimporter) doDecl(pkg *types.Package, name string) {
217	// See if we've already imported this declaration.
218	if obj := pkg.Scope().Lookup(name); obj != nil {
219		return
220	}
221
222	off, ok := p.pkgIndex[pkg][name]
223	if !ok {
224		errorf("%v.%v not in index", pkg, name)
225	}
226
227	r := &importReader{p: p, currPkg: pkg}
228	r.declReader.Reset(p.declData[off:])
229
230	r.obj(name)
231}
232
233func (p *iimporter) stringAt(off uint64) string {
234	if s, ok := p.stringCache[off]; ok {
235		return s
236	}
237
238	slen, n := binary.Uvarint(p.stringData[off:])
239	if n <= 0 {
240		errorf("varint failed")
241	}
242	spos := off + uint64(n)
243	s := string(p.stringData[spos : spos+slen])
244	p.stringCache[off] = s
245	return s
246}
247
248func (p *iimporter) pkgAt(off uint64) *types.Package {
249	if pkg, ok := p.pkgCache[off]; ok {
250		return pkg
251	}
252	path := p.stringAt(off)
253	errorf("missing package %q in %q", path, p.ipath)
254	return nil
255}
256
257func (p *iimporter) typAt(off uint64, base *types.Named) types.Type {
258	if t, ok := p.typCache[off]; ok && canReuse(base, t) {
259		return t
260	}
261
262	if off < predeclReserved {
263		errorf("predeclared type missing from cache: %v", off)
264	}
265
266	r := &importReader{p: p}
267	r.declReader.Reset(p.declData[off-predeclReserved:])
268	t := r.doType(base)
269
270	if canReuse(base, t) {
271		p.typCache[off] = t
272	}
273	return t
274}
275
276// canReuse reports whether the type rhs on the RHS of the declaration for def
277// may be re-used.
278//
279// Specifically, if def is non-nil and rhs is an interface type with methods, it
280// may not be re-used because we have a convention of setting the receiver type
281// for interface methods to def.
282func canReuse(def *types.Named, rhs types.Type) bool {
283	if def == nil {
284		return true
285	}
286	iface, _ := rhs.(*types.Interface)
287	if iface == nil {
288		return true
289	}
290	// Don't use iface.Empty() here as iface may not be complete.
291	return iface.NumEmbeddeds() == 0 && iface.NumExplicitMethods() == 0
292}
293
294type importReader struct {
295	p          *iimporter
296	declReader bytes.Reader
297	currPkg    *types.Package
298	prevFile   string
299	prevLine   int64
300	prevColumn int64
301}
302
303func (r *importReader) obj(name string) {
304	tag := r.byte()
305	pos := r.pos()
306
307	switch tag {
308	case 'A':
309		typ := r.typ()
310
311		r.declare(types.NewTypeName(pos, r.currPkg, name, typ))
312
313	case 'C':
314		typ, val := r.value()
315
316		r.declare(types.NewConst(pos, r.currPkg, name, typ, val))
317
318	case 'F', 'G':
319		var tparams []*types.TypeParam
320		if tag == 'G' {
321			tparams = r.tparamList()
322		}
323		sig := r.signature(nil, nil, tparams)
324		r.declare(types.NewFunc(pos, r.currPkg, name, sig))
325
326	case 'T', 'U':
327		// Types can be recursive. We need to setup a stub
328		// declaration before recursing.
329		obj := types.NewTypeName(pos, r.currPkg, name, nil)
330		named := types.NewNamed(obj, nil, nil)
331		// Declare obj before calling r.tparamList, so the new type name is recognized
332		// if used in the constraint of one of its own typeparams (see #48280).
333		r.declare(obj)
334		if tag == 'U' {
335			tparams := r.tparamList()
336			named.SetTypeParams(tparams)
337		}
338
339		underlying := r.p.typAt(r.uint64(), named).Underlying()
340		named.SetUnderlying(underlying)
341
342		if !isInterface(underlying) {
343			for n := r.uint64(); n > 0; n-- {
344				mpos := r.pos()
345				mname := r.ident()
346				recv := r.param()
347
348				// If the receiver has any targs, set those as the
349				// rparams of the method (since those are the
350				// typeparams being used in the method sig/body).
351				targs := baseType(recv.Type()).TypeArgs()
352				var rparams []*types.TypeParam
353				if targs.Len() > 0 {
354					rparams = make([]*types.TypeParam, targs.Len())
355					for i := range rparams {
356						rparams[i], _ = targs.At(i).(*types.TypeParam)
357					}
358				}
359				msig := r.signature(recv, rparams, nil)
360
361				named.AddMethod(types.NewFunc(mpos, r.currPkg, mname, msig))
362			}
363		}
364
365	case 'P':
366		// We need to "declare" a typeparam in order to have a name that
367		// can be referenced recursively (if needed) in the type param's
368		// bound.
369		if r.p.exportVersion < iexportVersionGenerics {
370			errorf("unexpected type param type")
371		}
372		// Remove the "path" from the type param name that makes it unique
373		ix := strings.LastIndex(name, ".")
374		if ix < 0 {
375			errorf("missing path for type param")
376		}
377		tn := types.NewTypeName(pos, r.currPkg, name[ix+1:], nil)
378		t := types.NewTypeParam(tn, nil)
379		// To handle recursive references to the typeparam within its
380		// bound, save the partial type in tparamIndex before reading the bounds.
381		id := ident{r.currPkg.Name(), name}
382		r.p.tparamIndex[id] = t
383
384		var implicit bool
385		if r.p.exportVersion >= iexportVersionGo1_18 {
386			implicit = r.bool()
387		}
388		constraint := r.typ()
389		if implicit {
390			iface, _ := constraint.(*types.Interface)
391			if iface == nil {
392				errorf("non-interface constraint marked implicit")
393			}
394			iface.MarkImplicit()
395		}
396		t.SetConstraint(constraint)
397
398	case 'V':
399		typ := r.typ()
400
401		r.declare(types.NewVar(pos, r.currPkg, name, typ))
402
403	default:
404		errorf("unexpected tag: %v", tag)
405	}
406}
407
408func (r *importReader) declare(obj types.Object) {
409	obj.Pkg().Scope().Insert(obj)
410}
411
412func (r *importReader) value() (typ types.Type, val constant.Value) {
413	typ = r.typ()
414	if r.p.exportVersion >= iexportVersionGo1_18 {
415		// TODO: add support for using the kind
416		_ = constant.Kind(r.int64())
417	}
418
419	switch b := typ.Underlying().(*types.Basic); b.Info() & types.IsConstType {
420	case types.IsBoolean:
421		val = constant.MakeBool(r.bool())
422
423	case types.IsString:
424		val = constant.MakeString(r.string())
425
426	case types.IsInteger:
427		var x big.Int
428		r.mpint(&x, b)
429		val = constant.Make(&x)
430
431	case types.IsFloat:
432		val = r.mpfloat(b)
433
434	case types.IsComplex:
435		re := r.mpfloat(b)
436		im := r.mpfloat(b)
437		val = constant.BinaryOp(re, token.ADD, constant.MakeImag(im))
438
439	default:
440		errorf("unexpected type %v", typ) // panics
441		panic("unreachable")
442	}
443
444	return
445}
446
447func intSize(b *types.Basic) (signed bool, maxBytes uint) {
448	if (b.Info() & types.IsUntyped) != 0 {
449		return true, 64
450	}
451
452	switch b.Kind() {
453	case types.Float32, types.Complex64:
454		return true, 3
455	case types.Float64, types.Complex128:
456		return true, 7
457	}
458
459	signed = (b.Info() & types.IsUnsigned) == 0
460	switch b.Kind() {
461	case types.Int8, types.Uint8:
462		maxBytes = 1
463	case types.Int16, types.Uint16:
464		maxBytes = 2
465	case types.Int32, types.Uint32:
466		maxBytes = 4
467	default:
468		maxBytes = 8
469	}
470
471	return
472}
473
474func (r *importReader) mpint(x *big.Int, typ *types.Basic) {
475	signed, maxBytes := intSize(typ)
476
477	maxSmall := 256 - maxBytes
478	if signed {
479		maxSmall = 256 - 2*maxBytes
480	}
481	if maxBytes == 1 {
482		maxSmall = 256
483	}
484
485	n, _ := r.declReader.ReadByte()
486	if uint(n) < maxSmall {
487		v := int64(n)
488		if signed {
489			v >>= 1
490			if n&1 != 0 {
491				v = ^v
492			}
493		}
494		x.SetInt64(v)
495		return
496	}
497
498	v := -n
499	if signed {
500		v = -(n &^ 1) >> 1
501	}
502	if v < 1 || uint(v) > maxBytes {
503		errorf("weird decoding: %v, %v => %v", n, signed, v)
504	}
505	b := make([]byte, v)
506	io.ReadFull(&r.declReader, b)
507	x.SetBytes(b)
508	if signed && n&1 != 0 {
509		x.Neg(x)
510	}
511}
512
513func (r *importReader) mpfloat(typ *types.Basic) constant.Value {
514	var mant big.Int
515	r.mpint(&mant, typ)
516	var f big.Float
517	f.SetInt(&mant)
518	if f.Sign() != 0 {
519		f.SetMantExp(&f, int(r.int64()))
520	}
521	return constant.Make(&f)
522}
523
524func (r *importReader) ident() string {
525	return r.string()
526}
527
528func (r *importReader) qualifiedIdent() (*types.Package, string) {
529	name := r.string()
530	pkg := r.pkg()
531	return pkg, name
532}
533
534func (r *importReader) pos() token.Pos {
535	if r.p.version >= 1 {
536		r.posv1()
537	} else {
538		r.posv0()
539	}
540
541	if r.prevFile == "" && r.prevLine == 0 && r.prevColumn == 0 {
542		return token.NoPos
543	}
544	return r.p.fake.pos(r.prevFile, int(r.prevLine), int(r.prevColumn))
545}
546
547func (r *importReader) posv0() {
548	delta := r.int64()
549	if delta != deltaNewFile {
550		r.prevLine += delta
551	} else if l := r.int64(); l == -1 {
552		r.prevLine += deltaNewFile
553	} else {
554		r.prevFile = r.string()
555		r.prevLine = l
556	}
557}
558
559func (r *importReader) posv1() {
560	delta := r.int64()
561	r.prevColumn += delta >> 1
562	if delta&1 != 0 {
563		delta = r.int64()
564		r.prevLine += delta >> 1
565		if delta&1 != 0 {
566			r.prevFile = r.string()
567		}
568	}
569}
570
571func (r *importReader) typ() types.Type {
572	return r.p.typAt(r.uint64(), nil)
573}
574
575func isInterface(t types.Type) bool {
576	_, ok := t.(*types.Interface)
577	return ok
578}
579
580func (r *importReader) pkg() *types.Package { return r.p.pkgAt(r.uint64()) }
581func (r *importReader) string() string      { return r.p.stringAt(r.uint64()) }
582
583func (r *importReader) doType(base *types.Named) types.Type {
584	switch k := r.kind(); k {
585	default:
586		errorf("unexpected kind tag in %q: %v", r.p.ipath, k)
587		return nil
588
589	case definedType:
590		pkg, name := r.qualifiedIdent()
591		r.p.doDecl(pkg, name)
592		return pkg.Scope().Lookup(name).(*types.TypeName).Type()
593	case pointerType:
594		return types.NewPointer(r.typ())
595	case sliceType:
596		return types.NewSlice(r.typ())
597	case arrayType:
598		n := r.uint64()
599		return types.NewArray(r.typ(), int64(n))
600	case chanType:
601		dir := chanDir(int(r.uint64()))
602		return types.NewChan(dir, r.typ())
603	case mapType:
604		return types.NewMap(r.typ(), r.typ())
605	case signatureType:
606		r.currPkg = r.pkg()
607		return r.signature(nil, nil, nil)
608
609	case structType:
610		r.currPkg = r.pkg()
611
612		fields := make([]*types.Var, r.uint64())
613		tags := make([]string, len(fields))
614		for i := range fields {
615			fpos := r.pos()
616			fname := r.ident()
617			ftyp := r.typ()
618			emb := r.bool()
619			tag := r.string()
620
621			fields[i] = types.NewField(fpos, r.currPkg, fname, ftyp, emb)
622			tags[i] = tag
623		}
624		return types.NewStruct(fields, tags)
625
626	case interfaceType:
627		r.currPkg = r.pkg()
628
629		embeddeds := make([]types.Type, r.uint64())
630		for i := range embeddeds {
631			_ = r.pos()
632			embeddeds[i] = r.typ()
633		}
634
635		methods := make([]*types.Func, r.uint64())
636		for i := range methods {
637			mpos := r.pos()
638			mname := r.ident()
639
640			// TODO(mdempsky): Matches bimport.go, but I
641			// don't agree with this.
642			var recv *types.Var
643			if base != nil {
644				recv = types.NewVar(token.NoPos, r.currPkg, "", base)
645			}
646
647			msig := r.signature(recv, nil, nil)
648			methods[i] = types.NewFunc(mpos, r.currPkg, mname, msig)
649		}
650
651		typ := types.NewInterfaceType(methods, embeddeds)
652		r.p.interfaceList = append(r.p.interfaceList, typ)
653		return typ
654
655	case typeParamType:
656		if r.p.exportVersion < iexportVersionGenerics {
657			errorf("unexpected type param type")
658		}
659		pkg, name := r.qualifiedIdent()
660		id := ident{pkg.Name(), name}
661		if t, ok := r.p.tparamIndex[id]; ok {
662			// We're already in the process of importing this typeparam.
663			return t
664		}
665		// Otherwise, import the definition of the typeparam now.
666		r.p.doDecl(pkg, name)
667		return r.p.tparamIndex[id]
668
669	case instanceType:
670		if r.p.exportVersion < iexportVersionGenerics {
671			errorf("unexpected instantiation type")
672		}
673		// pos does not matter for instances: they are positioned on the original
674		// type.
675		_ = r.pos()
676		len := r.uint64()
677		targs := make([]types.Type, len)
678		for i := range targs {
679			targs[i] = r.typ()
680		}
681		baseType := r.typ()
682		// The imported instantiated type doesn't include any methods, so
683		// we must always use the methods of the base (orig) type.
684		// TODO provide a non-nil *Context
685		t, _ := types.Instantiate(nil, baseType, targs, false)
686		return t
687
688	case unionType:
689		if r.p.exportVersion < iexportVersionGenerics {
690			errorf("unexpected instantiation type")
691		}
692		terms := make([]*types.Term, r.uint64())
693		for i := range terms {
694			terms[i] = types.NewTerm(r.bool(), r.typ())
695		}
696		return types.NewUnion(terms)
697	}
698}
699
700func (r *importReader) kind() itag {
701	return itag(r.uint64())
702}
703
704func (r *importReader) signature(recv *types.Var, rparams, tparams []*types.TypeParam) *types.Signature {
705	params := r.paramList()
706	results := r.paramList()
707	variadic := params.Len() > 0 && r.bool()
708	return types.NewSignatureType(recv, rparams, tparams, params, results, variadic)
709}
710
711func (r *importReader) tparamList() []*types.TypeParam {
712	n := r.uint64()
713	if n == 0 {
714		return nil
715	}
716	xs := make([]*types.TypeParam, n)
717	for i := range xs {
718		xs[i], _ = r.typ().(*types.TypeParam)
719	}
720	return xs
721}
722
723func (r *importReader) paramList() *types.Tuple {
724	xs := make([]*types.Var, r.uint64())
725	for i := range xs {
726		xs[i] = r.param()
727	}
728	return types.NewTuple(xs...)
729}
730
731func (r *importReader) param() *types.Var {
732	pos := r.pos()
733	name := r.ident()
734	typ := r.typ()
735	return types.NewParam(pos, r.currPkg, name, typ)
736}
737
738func (r *importReader) bool() bool {
739	return r.uint64() != 0
740}
741
742func (r *importReader) int64() int64 {
743	n, err := binary.ReadVarint(&r.declReader)
744	if err != nil {
745		errorf("readVarint: %v", err)
746	}
747	return n
748}
749
750func (r *importReader) uint64() uint64 {
751	n, err := binary.ReadUvarint(&r.declReader)
752	if err != nil {
753		errorf("readUvarint: %v", err)
754	}
755	return n
756}
757
758func (r *importReader) byte() byte {
759	x, err := r.declReader.ReadByte()
760	if err != nil {
761		errorf("declReader.ReadByte: %v", err)
762	}
763	return x
764}
765
766func baseType(typ types.Type) *types.Named {
767	// pointer receivers are never types.Named types
768	if p, _ := typ.(*types.Pointer); p != nil {
769		typ = p.Elem()
770	}
771	// receiver base types are always (possibly generic) types.Named types
772	n, _ := typ.(*types.Named)
773	return n
774}
775