cmd/bpa-operator/vendor/golang.org/x/tools/go/internal/gcimporter/iexport.go

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