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