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 binary package export. 6// This file was derived from $GOROOT/src/cmd/compile/internal/gc/iexport.go; 7// see that file for specification of the format. 8 9package gcimporter 10 11import ( 12 "bytes" 13 "encoding/binary" 14 "go/ast" 15 "go/constant" 16 "go/token" 17 "go/types" 18 "io" 19 "math/big" 20 "reflect" 21 "sort" 22) 23 24// Current indexed export format version. Increase with each format change. 25// 0: Go1.11 encoding 26const iexportVersion = 0 27 28// IExportData returns the binary export data for pkg. 29// 30// If no file set is provided, position info will be missing. 31// The package path of the top-level package will not be recorded, 32// so that calls to IImportData can override with a provided package path. 33func IExportData(fset *token.FileSet, pkg *types.Package) (b []byte, err error) { 34 defer func() { 35 if e := recover(); e != nil { 36 if ierr, ok := e.(internalError); ok { 37 err = ierr 38 return 39 } 40 // Not an internal error; panic again. 41 panic(e) 42 } 43 }() 44 45 p := iexporter{ 46 out: bytes.NewBuffer(nil), 47 fset: fset, 48 allPkgs: map[*types.Package]bool{}, 49 stringIndex: map[string]uint64{}, 50 declIndex: map[types.Object]uint64{}, 51 typIndex: map[types.Type]uint64{}, 52 localpkg: pkg, 53 } 54 55 for i, pt := range predeclared() { 56 p.typIndex[pt] = uint64(i) 57 } 58 if len(p.typIndex) > predeclReserved { 59 panic(internalErrorf("too many predeclared types: %d > %d", len(p.typIndex), predeclReserved)) 60 } 61 62 // Initialize work queue with exported declarations. 63 scope := pkg.Scope() 64 for _, name := range scope.Names() { 65 if ast.IsExported(name) { 66 p.pushDecl(scope.Lookup(name)) 67 } 68 } 69 70 // Loop until no more work. 71 for !p.declTodo.empty() { 72 p.doDecl(p.declTodo.popHead()) 73 } 74 75 // Append indices to data0 section. 76 dataLen := uint64(p.data0.Len()) 77 w := p.newWriter() 78 w.writeIndex(p.declIndex) 79 w.flush() 80 81 // Assemble header. 82 var hdr intWriter 83 hdr.WriteByte('i') 84 hdr.uint64(iexportVersion) 85 hdr.uint64(uint64(p.strings.Len())) 86 hdr.uint64(dataLen) 87 88 // Flush output. 89 io.Copy(p.out, &hdr) 90 io.Copy(p.out, &p.strings) 91 io.Copy(p.out, &p.data0) 92 93 return p.out.Bytes(), nil 94} 95 96// writeIndex writes out an object index. mainIndex indicates whether 97// we're writing out the main index, which is also read by 98// non-compiler tools and includes a complete package description 99// (i.e., name and height). 100func (w *exportWriter) writeIndex(index map[types.Object]uint64) { 101 // Build a map from packages to objects from that package. 102 pkgObjs := map[*types.Package][]types.Object{} 103 104 // For the main index, make sure to include every package that 105 // we reference, even if we're not exporting (or reexporting) 106 // any symbols from it. 107 pkgObjs[w.p.localpkg] = nil 108 for pkg := range w.p.allPkgs { 109 pkgObjs[pkg] = nil 110 } 111 112 for obj := range index { 113 pkgObjs[obj.Pkg()] = append(pkgObjs[obj.Pkg()], obj) 114 } 115 116 var pkgs []*types.Package 117 for pkg, objs := range pkgObjs { 118 pkgs = append(pkgs, pkg) 119 120 sort.Slice(objs, func(i, j int) bool { 121 return objs[i].Name() < objs[j].Name() 122 }) 123 } 124 125 sort.Slice(pkgs, func(i, j int) bool { 126 return w.exportPath(pkgs[i]) < w.exportPath(pkgs[j]) 127 }) 128 129 w.uint64(uint64(len(pkgs))) 130 for _, pkg := range pkgs { 131 w.string(w.exportPath(pkg)) 132 w.string(pkg.Name()) 133 w.uint64(uint64(0)) // package height is not needed for go/types 134 135 objs := pkgObjs[pkg] 136 w.uint64(uint64(len(objs))) 137 for _, obj := range objs { 138 w.string(obj.Name()) 139 w.uint64(index[obj]) 140 } 141 } 142} 143 144type iexporter struct { 145 fset *token.FileSet 146 out *bytes.Buffer 147 148 localpkg *types.Package 149 150 // allPkgs tracks all packages that have been referenced by 151 // the export data, so we can ensure to include them in the 152 // main index. 153 allPkgs map[*types.Package]bool 154 155 declTodo objQueue 156 157 strings intWriter 158 stringIndex map[string]uint64 159 160 data0 intWriter 161 declIndex map[types.Object]uint64 162 typIndex map[types.Type]uint64 163} 164 165// stringOff returns the offset of s within the string section. 166// If not already present, it's added to the end. 167func (p *iexporter) stringOff(s string) uint64 { 168 off, ok := p.stringIndex[s] 169 if !ok { 170 off = uint64(p.strings.Len()) 171 p.stringIndex[s] = off 172 173 p.strings.uint64(uint64(len(s))) 174 p.strings.WriteString(s) 175 } 176 return off 177} 178 179// pushDecl adds n to the declaration work queue, if not already present. 180func (p *iexporter) pushDecl(obj types.Object) { 181 // Package unsafe is known to the compiler and predeclared. 182 assert(obj.Pkg() != types.Unsafe) 183 184 if _, ok := p.declIndex[obj]; ok { 185 return 186 } 187 188 p.declIndex[obj] = ^uint64(0) // mark n present in work queue 189 p.declTodo.pushTail(obj) 190} 191 192// exportWriter handles writing out individual data section chunks. 193type exportWriter struct { 194 p *iexporter 195 196 data intWriter 197 currPkg *types.Package 198 prevFile string 199 prevLine int64 200} 201 202func (w *exportWriter) exportPath(pkg *types.Package) string { 203 if pkg == w.p.localpkg { 204 return "" 205 } 206 return pkg.Path() 207} 208 209func (p *iexporter) doDecl(obj types.Object) { 210 w := p.newWriter() 211 w.setPkg(obj.Pkg(), false) 212 213 switch obj := obj.(type) { 214 case *types.Var: 215 w.tag('V') 216 w.pos(obj.Pos()) 217 w.typ(obj.Type(), obj.Pkg()) 218 219 case *types.Func: 220 sig, _ := obj.Type().(*types.Signature) 221 if sig.Recv() != nil { 222 panic(internalErrorf("unexpected method: %v", sig)) 223 } 224 w.tag('F') 225 w.pos(obj.Pos()) 226 w.signature(sig) 227 228 case *types.Const: 229 w.tag('C') 230 w.pos(obj.Pos()) 231 w.value(obj.Type(), obj.Val()) 232 233 case *types.TypeName: 234 if obj.IsAlias() { 235 w.tag('A') 236 w.pos(obj.Pos()) 237 w.typ(obj.Type(), obj.Pkg()) 238 break 239 } 240 241 // Defined type. 242 w.tag('T') 243 w.pos(obj.Pos()) 244 245 underlying := obj.Type().Underlying() 246 w.typ(underlying, obj.Pkg()) 247 248 t := obj.Type() 249 if types.IsInterface(t) { 250 break 251 } 252 253 named, ok := t.(*types.Named) 254 if !ok { 255 panic(internalErrorf("%s is not a defined type", t)) 256 } 257 258 n := named.NumMethods() 259 w.uint64(uint64(n)) 260 for i := 0; i < n; i++ { 261 m := named.Method(i) 262 w.pos(m.Pos()) 263 w.string(m.Name()) 264 sig, _ := m.Type().(*types.Signature) 265 w.param(sig.Recv()) 266 w.signature(sig) 267 } 268 269 default: 270 panic(internalErrorf("unexpected object: %v", obj)) 271 } 272 273 p.declIndex[obj] = w.flush() 274} 275 276func (w *exportWriter) tag(tag byte) { 277 w.data.WriteByte(tag) 278} 279 280func (w *exportWriter) pos(pos token.Pos) { 281 if w.p.fset == nil { 282 w.int64(0) 283 return 284 } 285 286 p := w.p.fset.Position(pos) 287 file := p.Filename 288 line := int64(p.Line) 289 290 // When file is the same as the last position (common case), 291 // we can save a few bytes by delta encoding just the line 292 // number. 293 // 294 // Note: Because data objects may be read out of order (or not 295 // at all), we can only apply delta encoding within a single 296 // object. This is handled implicitly by tracking prevFile and 297 // prevLine as fields of exportWriter. 298 299 if file == w.prevFile { 300 delta := line - w.prevLine 301 w.int64(delta) 302 if delta == deltaNewFile { 303 w.int64(-1) 304 } 305 } else { 306 w.int64(deltaNewFile) 307 w.int64(line) // line >= 0 308 w.string(file) 309 w.prevFile = file 310 } 311 w.prevLine = line 312} 313 314func (w *exportWriter) pkg(pkg *types.Package) { 315 // Ensure any referenced packages are declared in the main index. 316 w.p.allPkgs[pkg] = true 317 318 w.string(w.exportPath(pkg)) 319} 320 321func (w *exportWriter) qualifiedIdent(obj types.Object) { 322 // Ensure any referenced declarations are written out too. 323 w.p.pushDecl(obj) 324 325 w.string(obj.Name()) 326 w.pkg(obj.Pkg()) 327} 328 329func (w *exportWriter) typ(t types.Type, pkg *types.Package) { 330 w.data.uint64(w.p.typOff(t, pkg)) 331} 332 333func (p *iexporter) newWriter() *exportWriter { 334 return &exportWriter{p: p} 335} 336 337func (w *exportWriter) flush() uint64 { 338 off := uint64(w.p.data0.Len()) 339 io.Copy(&w.p.data0, &w.data) 340 return off 341} 342 343func (p *iexporter) typOff(t types.Type, pkg *types.Package) uint64 { 344 off, ok := p.typIndex[t] 345 if !ok { 346 w := p.newWriter() 347 w.doTyp(t, pkg) 348 off = predeclReserved + w.flush() 349 p.typIndex[t] = off 350 } 351 return off 352} 353 354func (w *exportWriter) startType(k itag) { 355 w.data.uint64(uint64(k)) 356} 357 358func (w *exportWriter) doTyp(t types.Type, pkg *types.Package) { 359 switch t := t.(type) { 360 case *types.Named: 361 w.startType(definedType) 362 w.qualifiedIdent(t.Obj()) 363 364 case *types.Pointer: 365 w.startType(pointerType) 366 w.typ(t.Elem(), pkg) 367 368 case *types.Slice: 369 w.startType(sliceType) 370 w.typ(t.Elem(), pkg) 371 372 case *types.Array: 373 w.startType(arrayType) 374 w.uint64(uint64(t.Len())) 375 w.typ(t.Elem(), pkg) 376 377 case *types.Chan: 378 w.startType(chanType) 379 // 1 RecvOnly; 2 SendOnly; 3 SendRecv 380 var dir uint64 381 switch t.Dir() { 382 case types.RecvOnly: 383 dir = 1 384 case types.SendOnly: 385 dir = 2 386 case types.SendRecv: 387 dir = 3 388 } 389 w.uint64(dir) 390 w.typ(t.Elem(), pkg) 391 392 case *types.Map: 393 w.startType(mapType) 394 w.typ(t.Key(), pkg) 395 w.typ(t.Elem(), pkg) 396 397 case *types.Signature: 398 w.startType(signatureType) 399 w.setPkg(pkg, true) 400 w.signature(t) 401 402 case *types.Struct: 403 w.startType(structType) 404 w.setPkg(pkg, true) 405 406 n := t.NumFields() 407 w.uint64(uint64(n)) 408 for i := 0; i < n; i++ { 409 f := t.Field(i) 410 w.pos(f.Pos()) 411 w.string(f.Name()) 412 w.typ(f.Type(), pkg) 413 w.bool(f.Anonymous()) 414 w.string(t.Tag(i)) // note (or tag) 415 } 416 417 case *types.Interface: 418 w.startType(interfaceType) 419 w.setPkg(pkg, true) 420 421 n := t.NumEmbeddeds() 422 w.uint64(uint64(n)) 423 for i := 0; i < n; i++ { 424 f := t.Embedded(i) 425 w.pos(f.Obj().Pos()) 426 w.typ(f.Obj().Type(), f.Obj().Pkg()) 427 } 428 429 n = t.NumExplicitMethods() 430 w.uint64(uint64(n)) 431 for i := 0; i < n; i++ { 432 m := t.ExplicitMethod(i) 433 w.pos(m.Pos()) 434 w.string(m.Name()) 435 sig, _ := m.Type().(*types.Signature) 436 w.signature(sig) 437 } 438 439 default: 440 panic(internalErrorf("unexpected type: %v, %v", t, reflect.TypeOf(t))) 441 } 442} 443 444func (w *exportWriter) setPkg(pkg *types.Package, write bool) { 445 if write { 446 w.pkg(pkg) 447 } 448 449 w.currPkg = pkg 450} 451 452func (w *exportWriter) signature(sig *types.Signature) { 453 w.paramList(sig.Params()) 454 w.paramList(sig.Results()) 455 if sig.Params().Len() > 0 { 456 w.bool(sig.Variadic()) 457 } 458} 459 460func (w *exportWriter) paramList(tup *types.Tuple) { 461 n := tup.Len() 462 w.uint64(uint64(n)) 463 for i := 0; i < n; i++ { 464 w.param(tup.At(i)) 465 } 466} 467 468func (w *exportWriter) param(obj types.Object) { 469 w.pos(obj.Pos()) 470 w.localIdent(obj) 471 w.typ(obj.Type(), obj.Pkg()) 472} 473 474func (w *exportWriter) value(typ types.Type, v constant.Value) { 475 w.typ(typ, nil) 476 477 switch v.Kind() { 478 case constant.Bool: 479 w.bool(constant.BoolVal(v)) 480 case constant.Int: 481 var i big.Int 482 if i64, exact := constant.Int64Val(v); exact { 483 i.SetInt64(i64) 484 } else if ui64, exact := constant.Uint64Val(v); exact { 485 i.SetUint64(ui64) 486 } else { 487 i.SetString(v.ExactString(), 10) 488 } 489 w.mpint(&i, typ) 490 case constant.Float: 491 f := constantToFloat(v) 492 w.mpfloat(f, typ) 493 case constant.Complex: 494 w.mpfloat(constantToFloat(constant.Real(v)), typ) 495 w.mpfloat(constantToFloat(constant.Imag(v)), typ) 496 case constant.String: 497 w.string(constant.StringVal(v)) 498 case constant.Unknown: 499 // package contains type errors 500 default: 501 panic(internalErrorf("unexpected value %v (%T)", v, v)) 502 } 503} 504 505// constantToFloat converts a constant.Value with kind constant.Float to a 506// big.Float. 507func constantToFloat(x constant.Value) *big.Float { 508 assert(x.Kind() == constant.Float) 509 // Use the same floating-point precision (512) as cmd/compile 510 // (see Mpprec in cmd/compile/internal/gc/mpfloat.go). 511 const mpprec = 512 512 var f big.Float 513 f.SetPrec(mpprec) 514 if v, exact := constant.Float64Val(x); exact { 515 // float64 516 f.SetFloat64(v) 517 } else if num, denom := constant.Num(x), constant.Denom(x); num.Kind() == constant.Int { 518 // TODO(gri): add big.Rat accessor to constant.Value. 519 n := valueToRat(num) 520 d := valueToRat(denom) 521 f.SetRat(n.Quo(n, d)) 522 } else { 523 // Value too large to represent as a fraction => inaccessible. 524 // TODO(gri): add big.Float accessor to constant.Value. 525 _, ok := f.SetString(x.ExactString()) 526 assert(ok) 527 } 528 return &f 529} 530 531// mpint exports a multi-precision integer. 532// 533// For unsigned types, small values are written out as a single 534// byte. Larger values are written out as a length-prefixed big-endian 535// byte string, where the length prefix is encoded as its complement. 536// For example, bytes 0, 1, and 2 directly represent the integer 537// values 0, 1, and 2; while bytes 255, 254, and 253 indicate a 1-, 538// 2-, and 3-byte big-endian string follow. 539// 540// Encoding for signed types use the same general approach as for 541// unsigned types, except small values use zig-zag encoding and the 542// bottom bit of length prefix byte for large values is reserved as a 543// sign bit. 544// 545// The exact boundary between small and large encodings varies 546// according to the maximum number of bytes needed to encode a value 547// of type typ. As a special case, 8-bit types are always encoded as a 548// single byte. 549// 550// TODO(mdempsky): Is this level of complexity really worthwhile? 551func (w *exportWriter) mpint(x *big.Int, typ types.Type) { 552 basic, ok := typ.Underlying().(*types.Basic) 553 if !ok { 554 panic(internalErrorf("unexpected type %v (%T)", typ.Underlying(), typ.Underlying())) 555 } 556 557 signed, maxBytes := intSize(basic) 558 559 negative := x.Sign() < 0 560 if !signed && negative { 561 panic(internalErrorf("negative unsigned integer; type %v, value %v", typ, x)) 562 } 563 564 b := x.Bytes() 565 if len(b) > 0 && b[0] == 0 { 566 panic(internalErrorf("leading zeros")) 567 } 568 if uint(len(b)) > maxBytes { 569 panic(internalErrorf("bad mpint length: %d > %d (type %v, value %v)", len(b), maxBytes, typ, x)) 570 } 571 572 maxSmall := 256 - maxBytes 573 if signed { 574 maxSmall = 256 - 2*maxBytes 575 } 576 if maxBytes == 1 { 577 maxSmall = 256 578 } 579 580 // Check if x can use small value encoding. 581 if len(b) <= 1 { 582 var ux uint 583 if len(b) == 1 { 584 ux = uint(b[0]) 585 } 586 if signed { 587 ux <<= 1 588 if negative { 589 ux-- 590 } 591 } 592 if ux < maxSmall { 593 w.data.WriteByte(byte(ux)) 594 return 595 } 596 } 597 598 n := 256 - uint(len(b)) 599 if signed { 600 n = 256 - 2*uint(len(b)) 601 if negative { 602 n |= 1 603 } 604 } 605 if n < maxSmall || n >= 256 { 606 panic(internalErrorf("encoding mistake: %d, %v, %v => %d", len(b), signed, negative, n)) 607 } 608 609 w.data.WriteByte(byte(n)) 610 w.data.Write(b) 611} 612 613// mpfloat exports a multi-precision floating point number. 614// 615// The number's value is decomposed into mantissa × 2**exponent, where 616// mantissa is an integer. The value is written out as mantissa (as a 617// multi-precision integer) and then the exponent, except exponent is 618// omitted if mantissa is zero. 619func (w *exportWriter) mpfloat(f *big.Float, typ types.Type) { 620 if f.IsInf() { 621 panic("infinite constant") 622 } 623 624 // Break into f = mant × 2**exp, with 0.5 <= mant < 1. 625 var mant big.Float 626 exp := int64(f.MantExp(&mant)) 627 628 // Scale so that mant is an integer. 629 prec := mant.MinPrec() 630 mant.SetMantExp(&mant, int(prec)) 631 exp -= int64(prec) 632 633 manti, acc := mant.Int(nil) 634 if acc != big.Exact { 635 panic(internalErrorf("mantissa scaling failed for %f (%s)", f, acc)) 636 } 637 w.mpint(manti, typ) 638 if manti.Sign() != 0 { 639 w.int64(exp) 640 } 641} 642 643func (w *exportWriter) bool(b bool) bool { 644 var x uint64 645 if b { 646 x = 1 647 } 648 w.uint64(x) 649 return b 650} 651 652func (w *exportWriter) int64(x int64) { w.data.int64(x) } 653func (w *exportWriter) uint64(x uint64) { w.data.uint64(x) } 654func (w *exportWriter) string(s string) { w.uint64(w.p.stringOff(s)) } 655 656func (w *exportWriter) localIdent(obj types.Object) { 657 // Anonymous parameters. 658 if obj == nil { 659 w.string("") 660 return 661 } 662 663 name := obj.Name() 664 if name == "_" { 665 w.string("_") 666 return 667 } 668 669 w.string(name) 670} 671 672type intWriter struct { 673 bytes.Buffer 674} 675 676func (w *intWriter) int64(x int64) { 677 var buf [binary.MaxVarintLen64]byte 678 n := binary.PutVarint(buf[:], x) 679 w.Write(buf[:n]) 680} 681 682func (w *intWriter) uint64(x uint64) { 683 var buf [binary.MaxVarintLen64]byte 684 n := binary.PutUvarint(buf[:], x) 685 w.Write(buf[:n]) 686} 687 688func assert(cond bool) { 689 if !cond { 690 panic("internal error: assertion failed") 691 } 692} 693 694// The below is copied from go/src/cmd/compile/internal/gc/syntax.go. 695 696// objQueue is a FIFO queue of types.Object. The zero value of objQueue is 697// a ready-to-use empty queue. 698type objQueue struct { 699 ring []types.Object 700 head, tail int 701} 702 703// empty returns true if q contains no Nodes. 704func (q *objQueue) empty() bool { 705 return q.head == q.tail 706} 707 708// pushTail appends n to the tail of the queue. 709func (q *objQueue) pushTail(obj types.Object) { 710 if len(q.ring) == 0 { 711 q.ring = make([]types.Object, 16) 712 } else if q.head+len(q.ring) == q.tail { 713 // Grow the ring. 714 nring := make([]types.Object, len(q.ring)*2) 715 // Copy the old elements. 716 part := q.ring[q.head%len(q.ring):] 717 if q.tail-q.head <= len(part) { 718 part = part[:q.tail-q.head] 719 copy(nring, part) 720 } else { 721 pos := copy(nring, part) 722 copy(nring[pos:], q.ring[:q.tail%len(q.ring)]) 723 } 724 q.ring, q.head, q.tail = nring, 0, q.tail-q.head 725 } 726 727 q.ring[q.tail%len(q.ring)] = obj 728 q.tail++ 729} 730 731// popHead pops a node from the head of the queue. It panics if q is empty. 732func (q *objQueue) popHead() types.Object { 733 if q.empty() { 734 panic("dequeue empty") 735 } 736 obj := q.ring[q.head%len(q.ring)] 737 q.head++ 738 return obj 739} 740