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