.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/go/internal/gcimporter/gcimporter.go

   1 // Copyright 2011 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 // This file is a modified copy of $GOROOT/src/go/internal/gcimporter/gcimporter.go,
   6 // but it also contains the original source-based importer code for Go1.6.
   7 // Once we stop supporting 1.6, we can remove that code.
   8
   9 // Package gcimporter provides various functions for reading
  10 // gc-generated object files that can be used to implement the
  11 // Importer interface defined by the Go 1.5 standard library package.
  12 package gcimporter // import "golang.org/x/tools/go/internal/gcimporter"
  13
  14 import (
  15         "bufio"
  16         "errors"
  17         "fmt"
  18         "go/build"
  19         "go/constant"
  20         "go/token"
  21         "go/types"
  22         "io"
  23         "io/ioutil"
  24         "os"
  25         "path/filepath"
  26         "sort"
  27         "strconv"
  28         "strings"
  29         "text/scanner"
  30 )
  31
  32 // debugging/development support
  33 const debug = false
  34
  35 var pkgExts = [...]string{".a", ".o"}
  36
  37 // FindPkg returns the filename and unique package id for an import
  38 // path based on package information provided by build.Import (using
  39 // the build.Default build.Context). A relative srcDir is interpreted
  40 // relative to the current working directory.
  41 // If no file was found, an empty filename is returned.
  42 //
  43 func FindPkg(path, srcDir string) (filename, id string) {
  44         if path == "" {
  45                 return
  46         }
  47
  48         var noext string
  49         switch {
  50         default:
  51                 // "x" -> "$GOPATH/pkg/$GOOS_$GOARCH/x.ext", "x"
  52                 // Don't require the source files to be present.
  53                 if abs, err := filepath.Abs(srcDir); err == nil { // see issue 14282
  54                         srcDir = abs
  55                 }
  56                 bp, _ := build.Import(path, srcDir, build.FindOnly|build.AllowBinary)
  57                 if bp.PkgObj == "" {
  58                         id = path // make sure we have an id to print in error message
  59                         return
  60                 }
  61                 noext = strings.TrimSuffix(bp.PkgObj, ".a")
  62                 id = bp.ImportPath
  63
  64         case build.IsLocalImport(path):
  65                 // "./x" -> "/this/directory/x.ext", "/this/directory/x"
  66                 noext = filepath.Join(srcDir, path)
  67                 id = noext
  68
  69         case filepath.IsAbs(path):
  70                 // for completeness only - go/build.Import
  71                 // does not support absolute imports
  72                 // "/x" -> "/x.ext", "/x"
  73                 noext = path
  74                 id = path
  75         }
  76
  77         if false { // for debugging
  78                 if path != id {
  79                         fmt.Printf("%s -> %s\n", path, id)
  80                 }
  81         }
  82
  83         // try extensions
  84         for _, ext := range pkgExts {
  85                 filename = noext + ext
  86                 if f, err := os.Stat(filename); err == nil && !f.IsDir() {
  87                         return
  88                 }
  89         }
  90
  91         filename = "" // not found
  92         return
  93 }
  94
  95 // ImportData imports a package by reading the gc-generated export data,
  96 // adds the corresponding package object to the packages map indexed by id,
  97 // and returns the object.
  98 //
  99 // The packages map must contains all packages already imported. The data
 100 // reader position must be the beginning of the export data section. The
 101 // filename is only used in error messages.
 102 //
 103 // If packages[id] contains the completely imported package, that package
 104 // can be used directly, and there is no need to call this function (but
 105 // there is also no harm but for extra time used).
 106 //
 107 func ImportData(packages map[string]*types.Package, filename, id string, data io.Reader) (pkg *types.Package, err error) {
 108         // support for parser error handling
 109         defer func() {
 110                 switch r := recover().(type) {
 111                 case nil:
 112                         // nothing to do
 113                 case importError:
 114                         err = r
 115                 default:
 116                         panic(r) // internal error
 117                 }
 118         }()
 119
 120         var p parser
 121         p.init(filename, id, data, packages)
 122         pkg = p.parseExport()
 123
 124         return
 125 }
 126
 127 // Import imports a gc-generated package given its import path and srcDir, adds
 128 // the corresponding package object to the packages map, and returns the object.
 129 // The packages map must contain all packages already imported.
 130 //
 131 func Import(packages map[string]*types.Package, path, srcDir string, lookup func(path string) (io.ReadCloser, error)) (pkg *types.Package, err error) {
 132         var rc io.ReadCloser
 133         var filename, id string
 134         if lookup != nil {
 135                 // With custom lookup specified, assume that caller has
 136                 // converted path to a canonical import path for use in the map.
 137                 if path == "unsafe" {
 138                         return types.Unsafe, nil
 139                 }
 140                 id = path
 141
 142                 // No need to re-import if the package was imported completely before.
 143                 if pkg = packages[id]; pkg != nil && pkg.Complete() {
 144                         return
 145                 }
 146                 f, err := lookup(path)
 147                 if err != nil {
 148                         return nil, err
 149                 }
 150                 rc = f
 151         } else {
 152                 filename, id = FindPkg(path, srcDir)
 153                 if filename == "" {
 154                         if path == "unsafe" {
 155                                 return types.Unsafe, nil
 156                         }
 157                         return nil, fmt.Errorf("can't find import: %q", id)
 158                 }
 159
 160                 // no need to re-import if the package was imported completely before
 161                 if pkg = packages[id]; pkg != nil && pkg.Complete() {
 162                         return
 163                 }
 164
 165                 // open file
 166                 f, err := os.Open(filename)
 167                 if err != nil {
 168                         return nil, err
 169                 }
 170                 defer func() {
 171                         if err != nil {
 172                                 // add file name to error
 173                                 err = fmt.Errorf("%s: %v", filename, err)
 174                         }
 175                 }()
 176                 rc = f
 177         }
 178         defer rc.Close()
 179
 180         var hdr string
 181         buf := bufio.NewReader(rc)
 182         if hdr, err = FindExportData(buf); err != nil {
 183                 return
 184         }
 185
 186         switch hdr {
 187         case "$$\n":
 188                 // Work-around if we don't have a filename; happens only if lookup != nil.
 189                 // Either way, the filename is only needed for importer error messages, so
 190                 // this is fine.
 191                 if filename == "" {
 192                         filename = path
 193                 }
 194                 return ImportData(packages, filename, id, buf)
 195
 196         case "$$B\n":
 197                 var data []byte
 198                 data, err = ioutil.ReadAll(buf)
 199                 if err != nil {
 200                         break
 201                 }
 202
 203                 // TODO(gri): allow clients of go/importer to provide a FileSet.
 204                 // Or, define a new standard go/types/gcexportdata package.
 205                 fset := token.NewFileSet()
 206
 207                 // The indexed export format starts with an 'i'; the older
 208                 // binary export format starts with a 'c', 'd', or 'v'
 209                 // (from "version"). Select appropriate importer.
 210                 if len(data) > 0 && data[0] == 'i' {
 211                         _, pkg, err = IImportData(fset, packages, data[1:], id)
 212                 } else {
 213                         _, pkg, err = BImportData(fset, packages, data, id)
 214                 }
 215
 216         default:
 217                 err = fmt.Errorf("unknown export data header: %q", hdr)
 218         }
 219
 220         return
 221 }
 222
 223 // ----------------------------------------------------------------------------
 224 // Parser
 225
 226 // TODO(gri) Imported objects don't have position information.
 227 //           Ideally use the debug table line info; alternatively
 228 //           create some fake position (or the position of the
 229 //           import). That way error messages referring to imported
 230 //           objects can print meaningful information.
 231
 232 // parser parses the exports inside a gc compiler-produced
 233 // object/archive file and populates its scope with the results.
 234 type parser struct {
 235         scanner    scanner.Scanner
 236         tok        rune                      // current token
 237         lit        string                    // literal string; only valid for Ident, Int, String tokens
 238         id         string                    // package id of imported package
 239         sharedPkgs map[string]*types.Package // package id -> package object (across importer)
 240         localPkgs  map[string]*types.Package // package id -> package object (just this package)
 241 }
 242
 243 func (p *parser) init(filename, id string, src io.Reader, packages map[string]*types.Package) {
 244         p.scanner.Init(src)
 245         p.scanner.Error = func(_ *scanner.Scanner, msg string) { p.error(msg) }
 246         p.scanner.Mode = scanner.ScanIdents | scanner.ScanInts | scanner.ScanChars | scanner.ScanStrings | scanner.ScanComments | scanner.SkipComments
 247         p.scanner.Whitespace = 1<<'\t' | 1<<' '
 248         p.scanner.Filename = filename // for good error messages
 249         p.next()
 250         p.id = id
 251         p.sharedPkgs = packages
 252         if debug {
 253                 // check consistency of packages map
 254                 for _, pkg := range packages {
 255                         if pkg.Name() == "" {
 256                                 fmt.Printf("no package name for %s\n", pkg.Path())
 257                         }
 258                 }
 259         }
 260 }
 261
 262 func (p *parser) next() {
 263         p.tok = p.scanner.Scan()
 264         switch p.tok {
 265         case scanner.Ident, scanner.Int, scanner.Char, scanner.String, '·':
 266                 p.lit = p.scanner.TokenText()
 267         default:
 268                 p.lit = ""
 269         }
 270         if debug {
 271                 fmt.Printf("%s: %q -> %q\n", scanner.TokenString(p.tok), p.scanner.TokenText(), p.lit)
 272         }
 273 }
 274
 275 func declTypeName(pkg *types.Package, name string) *types.TypeName {
 276         scope := pkg.Scope()
 277         if obj := scope.Lookup(name); obj != nil {
 278                 return obj.(*types.TypeName)
 279         }
 280         obj := types.NewTypeName(token.NoPos, pkg, name, nil)
 281         // a named type may be referred to before the underlying type
 282         // is known - set it up
 283         types.NewNamed(obj, nil, nil)
 284         scope.Insert(obj)
 285         return obj
 286 }
 287
 288 // ----------------------------------------------------------------------------
 289 // Error handling
 290
 291 // Internal errors are boxed as importErrors.
 292 type importError struct {
 293         pos scanner.Position
 294         err error
 295 }
 296
 297 func (e importError) Error() string {
 298         return fmt.Sprintf("import error %s (byte offset = %d): %s", e.pos, e.pos.Offset, e.err)
 299 }
 300
 301 func (p *parser) error(err interface{}) {
 302         if s, ok := err.(string); ok {
 303                 err = errors.New(s)
 304         }
 305         // panic with a runtime.Error if err is not an error
 306         panic(importError{p.scanner.Pos(), err.(error)})
 307 }
 308
 309 func (p *parser) errorf(format string, args ...interface{}) {
 310         p.error(fmt.Sprintf(format, args...))
 311 }
 312
 313 func (p *parser) expect(tok rune) string {
 314         lit := p.lit
 315         if p.tok != tok {
 316                 p.errorf("expected %s, got %s (%s)", scanner.TokenString(tok), scanner.TokenString(p.tok), lit)
 317         }
 318         p.next()
 319         return lit
 320 }
 321
 322 func (p *parser) expectSpecial(tok string) {
 323         sep := 'x' // not white space
 324         i := 0
 325         for i < len(tok) && p.tok == rune(tok[i]) && sep > ' ' {
 326                 sep = p.scanner.Peek() // if sep <= ' ', there is white space before the next token
 327                 p.next()
 328                 i++
 329         }
 330         if i < len(tok) {
 331                 p.errorf("expected %q, got %q", tok, tok[0:i])
 332         }
 333 }
 334
 335 func (p *parser) expectKeyword(keyword string) {
 336         lit := p.expect(scanner.Ident)
 337         if lit != keyword {
 338                 p.errorf("expected keyword %s, got %q", keyword, lit)
 339         }
 340 }
 341
 342 // ----------------------------------------------------------------------------
 343 // Qualified and unqualified names
 344
 345 // PackageId = string_lit .
 346 //
 347 func (p *parser) parsePackageID() string {
 348         id, err := strconv.Unquote(p.expect(scanner.String))
 349         if err != nil {
 350                 p.error(err)
 351         }
 352         // id == "" stands for the imported package id
 353         // (only known at time of package installation)
 354         if id == "" {
 355                 id = p.id
 356         }
 357         return id
 358 }
 359
 360 // PackageName = ident .
 361 //
 362 func (p *parser) parsePackageName() string {
 363         return p.expect(scanner.Ident)
 364 }
 365
 366 // dotIdentifier = ( ident | '·' ) { ident | int | '·' } .
 367 func (p *parser) parseDotIdent() string {
 368         ident := ""
 369         if p.tok != scanner.Int {
 370                 sep := 'x' // not white space
 371                 for (p.tok == scanner.Ident || p.tok == scanner.Int || p.tok == '·') && sep > ' ' {
 372                         ident += p.lit
 373                         sep = p.scanner.Peek() // if sep <= ' ', there is white space before the next token
 374                         p.next()
 375                 }
 376         }
 377         if ident == "" {
 378                 p.expect(scanner.Ident) // use expect() for error handling
 379         }
 380         return ident
 381 }
 382
 383 // QualifiedName = "@" PackageId "." ( "?" | dotIdentifier ) .
 384 //
 385 func (p *parser) parseQualifiedName() (id, name string) {
 386         p.expect('@')
 387         id = p.parsePackageID()
 388         p.expect('.')
 389         // Per rev f280b8a485fd (10/2/2013), qualified names may be used for anonymous fields.
 390         if p.tok == '?' {
 391                 p.next()
 392         } else {
 393                 name = p.parseDotIdent()
 394         }
 395         return
 396 }
 397
 398 // getPkg returns the package for a given id. If the package is
 399 // not found, create the package and add it to the p.localPkgs
 400 // and p.sharedPkgs maps. name is the (expected) name of the
 401 // package. If name == "", the package name is expected to be
 402 // set later via an import clause in the export data.
 403 //
 404 // id identifies a package, usually by a canonical package path like
 405 // "encoding/json" but possibly by a non-canonical import path like
 406 // "./json".
 407 //
 408 func (p *parser) getPkg(id, name string) *types.Package {
 409         // package unsafe is not in the packages maps - handle explicitly
 410         if id == "unsafe" {
 411                 return types.Unsafe
 412         }
 413
 414         pkg := p.localPkgs[id]
 415         if pkg == nil {
 416                 // first import of id from this package
 417                 pkg = p.sharedPkgs[id]
 418                 if pkg == nil {
 419                         // first import of id by this importer;
 420                         // add (possibly unnamed) pkg to shared packages
 421                         pkg = types.NewPackage(id, name)
 422                         p.sharedPkgs[id] = pkg
 423                 }
 424                 // add (possibly unnamed) pkg to local packages
 425                 if p.localPkgs == nil {
 426                         p.localPkgs = make(map[string]*types.Package)
 427                 }
 428                 p.localPkgs[id] = pkg
 429         } else if name != "" {
 430                 // package exists already and we have an expected package name;
 431                 // make sure names match or set package name if necessary
 432                 if pname := pkg.Name(); pname == "" {
 433                         pkg.SetName(name)
 434                 } else if pname != name {
 435                         p.errorf("%s package name mismatch: %s (given) vs %s (expected)", id, pname, name)
 436                 }
 437         }
 438         return pkg
 439 }
 440
 441 // parseExportedName is like parseQualifiedName, but
 442 // the package id is resolved to an imported *types.Package.
 443 //
 444 func (p *parser) parseExportedName() (pkg *types.Package, name string) {
 445         id, name := p.parseQualifiedName()
 446         pkg = p.getPkg(id, "")
 447         return
 448 }
 449
 450 // ----------------------------------------------------------------------------
 451 // Types
 452
 453 // BasicType = identifier .
 454 //
 455 func (p *parser) parseBasicType() types.Type {
 456         id := p.expect(scanner.Ident)
 457         obj := types.Universe.Lookup(id)
 458         if obj, ok := obj.(*types.TypeName); ok {
 459                 return obj.Type()
 460         }
 461         p.errorf("not a basic type: %s", id)
 462         return nil
 463 }
 464
 465 // ArrayType = "[" int_lit "]" Type .
 466 //
 467 func (p *parser) parseArrayType(parent *types.Package) types.Type {
 468         // "[" already consumed and lookahead known not to be "]"
 469         lit := p.expect(scanner.Int)
 470         p.expect(']')
 471         elem := p.parseType(parent)
 472         n, err := strconv.ParseInt(lit, 10, 64)
 473         if err != nil {
 474                 p.error(err)
 475         }
 476         return types.NewArray(elem, n)
 477 }
 478
 479 // MapType = "map" "[" Type "]" Type .
 480 //
 481 func (p *parser) parseMapType(parent *types.Package) types.Type {
 482         p.expectKeyword("map")
 483         p.expect('[')
 484         key := p.parseType(parent)
 485         p.expect(']')
 486         elem := p.parseType(parent)
 487         return types.NewMap(key, elem)
 488 }
 489
 490 // Name = identifier | "?" | QualifiedName .
 491 //
 492 // For unqualified and anonymous names, the returned package is the parent
 493 // package unless parent == nil, in which case the returned package is the
 494 // package being imported. (The parent package is not nil if the name
 495 // is an unqualified struct field or interface method name belonging to a
 496 // type declared in another package.)
 497 //
 498 // For qualified names, the returned package is nil (and not created if
 499 // it doesn't exist yet) unless materializePkg is set (which creates an
 500 // unnamed package with valid package path). In the latter case, a
 501 // subsequent import clause is expected to provide a name for the package.
 502 //
 503 func (p *parser) parseName(parent *types.Package, materializePkg bool) (pkg *types.Package, name string) {
 504         pkg = parent
 505         if pkg == nil {
 506                 pkg = p.sharedPkgs[p.id]
 507         }
 508         switch p.tok {
 509         case scanner.Ident:
 510                 name = p.lit
 511                 p.next()
 512         case '?':
 513                 // anonymous
 514                 p.next()
 515         case '@':
 516                 // exported name prefixed with package path
 517                 pkg = nil
 518                 var id string
 519                 id, name = p.parseQualifiedName()
 520                 if materializePkg {
 521                         pkg = p.getPkg(id, "")
 522                 }
 523         default:
 524                 p.error("name expected")
 525         }
 526         return
 527 }
 528
 529 func deref(typ types.Type) types.Type {
 530         if p, _ := typ.(*types.Pointer); p != nil {
 531                 return p.Elem()
 532         }
 533         return typ
 534 }
 535
 536 // Field = Name Type [ string_lit ] .
 537 //
 538 func (p *parser) parseField(parent *types.Package) (*types.Var, string) {
 539         pkg, name := p.parseName(parent, true)
 540
 541         if name == "_" {
 542                 // Blank fields should be package-qualified because they
 543                 // are unexported identifiers, but gc does not qualify them.
 544                 // Assuming that the ident belongs to the current package
 545                 // causes types to change during re-exporting, leading
 546                 // to spurious "can't assign A to B" errors from go/types.
 547                 // As a workaround, pretend all blank fields belong
 548                 // to the same unique dummy package.
 549                 const blankpkg = "<_>"
 550                 pkg = p.getPkg(blankpkg, blankpkg)
 551         }
 552
 553         typ := p.parseType(parent)
 554         anonymous := false
 555         if name == "" {
 556                 // anonymous field - typ must be T or *T and T must be a type name
 557                 switch typ := deref(typ).(type) {
 558                 case *types.Basic: // basic types are named types
 559                         pkg = nil // objects defined in Universe scope have no package
 560                         name = typ.Name()
 561                 case *types.Named:
 562                         name = typ.Obj().Name()
 563                 default:
 564                         p.errorf("anonymous field expected")
 565                 }
 566                 anonymous = true
 567         }
 568         tag := ""
 569         if p.tok == scanner.String {
 570                 s := p.expect(scanner.String)
 571                 var err error
 572                 tag, err = strconv.Unquote(s)
 573                 if err != nil {
 574                         p.errorf("invalid struct tag %s: %s", s, err)
 575                 }
 576         }
 577         return types.NewField(token.NoPos, pkg, name, typ, anonymous), tag
 578 }
 579
 580 // StructType = "struct" "{" [ FieldList ] "}" .
 581 // FieldList  = Field { ";" Field } .
 582 //
 583 func (p *parser) parseStructType(parent *types.Package) types.Type {
 584         var fields []*types.Var
 585         var tags []string
 586
 587         p.expectKeyword("struct")
 588         p.expect('{')
 589         for i := 0; p.tok != '}' && p.tok != scanner.EOF; i++ {
 590                 if i > 0 {
 591                         p.expect(';')
 592                 }
 593                 fld, tag := p.parseField(parent)
 594                 if tag != "" && tags == nil {
 595                         tags = make([]string, i)
 596                 }
 597                 if tags != nil {
 598                         tags = append(tags, tag)
 599                 }
 600                 fields = append(fields, fld)
 601         }
 602         p.expect('}')
 603
 604         return types.NewStruct(fields, tags)
 605 }
 606
 607 // Parameter = ( identifier | "?" ) [ "..." ] Type [ string_lit ] .
 608 //
 609 func (p *parser) parseParameter() (par *types.Var, isVariadic bool) {
 610         _, name := p.parseName(nil, false)
 611         // remove gc-specific parameter numbering
 612         if i := strings.Index(name, "·"); i >= 0 {
 613                 name = name[:i]
 614         }
 615         if p.tok == '.' {
 616                 p.expectSpecial("...")
 617                 isVariadic = true
 618         }
 619         typ := p.parseType(nil)
 620         if isVariadic {
 621                 typ = types.NewSlice(typ)
 622         }
 623         // ignore argument tag (e.g. "noescape")
 624         if p.tok == scanner.String {
 625                 p.next()
 626         }
 627         // TODO(gri) should we provide a package?
 628         par = types.NewVar(token.NoPos, nil, name, typ)
 629         return
 630 }
 631
 632 // Parameters    = "(" [ ParameterList ] ")" .
 633 // ParameterList = { Parameter "," } Parameter .
 634 //
 635 func (p *parser) parseParameters() (list []*types.Var, isVariadic bool) {
 636         p.expect('(')
 637         for p.tok != ')' && p.tok != scanner.EOF {
 638                 if len(list) > 0 {
 639                         p.expect(',')
 640                 }
 641                 par, variadic := p.parseParameter()
 642                 list = append(list, par)
 643                 if variadic {
 644                         if isVariadic {
 645                                 p.error("... not on final argument")
 646                         }
 647                         isVariadic = true
 648                 }
 649         }
 650         p.expect(')')
 651
 652         return
 653 }
 654
 655 // Signature = Parameters [ Result ] .
 656 // Result    = Type | Parameters .
 657 //
 658 func (p *parser) parseSignature(recv *types.Var) *types.Signature {
 659         params, isVariadic := p.parseParameters()
 660
 661         // optional result type
 662         var results []*types.Var
 663         if p.tok == '(' {
 664                 var variadic bool
 665                 results, variadic = p.parseParameters()
 666                 if variadic {
 667                         p.error("... not permitted on result type")
 668                 }
 669         }
 670
 671         return types.NewSignature(recv, types.NewTuple(params...), types.NewTuple(results...), isVariadic)
 672 }
 673
 674 // InterfaceType = "interface" "{" [ MethodList ] "}" .
 675 // MethodList    = Method { ";" Method } .
 676 // Method        = Name Signature .
 677 //
 678 // The methods of embedded interfaces are always "inlined"
 679 // by the compiler and thus embedded interfaces are never
 680 // visible in the export data.
 681 //
 682 func (p *parser) parseInterfaceType(parent *types.Package) types.Type {
 683         var methods []*types.Func
 684
 685         p.expectKeyword("interface")
 686         p.expect('{')
 687         for i := 0; p.tok != '}' && p.tok != scanner.EOF; i++ {
 688                 if i > 0 {
 689                         p.expect(';')
 690                 }
 691                 pkg, name := p.parseName(parent, true)
 692                 sig := p.parseSignature(nil)
 693                 methods = append(methods, types.NewFunc(token.NoPos, pkg, name, sig))
 694         }
 695         p.expect('}')
 696
 697         // Complete requires the type's embedded interfaces to be fully defined,
 698         // but we do not define any
 699         return newInterface(methods, nil).Complete()
 700 }
 701
 702 // ChanType = ( "chan" [ "<-" ] | "<-" "chan" ) Type .
 703 //
 704 func (p *parser) parseChanType(parent *types.Package) types.Type {
 705         dir := types.SendRecv
 706         if p.tok == scanner.Ident {
 707                 p.expectKeyword("chan")
 708                 if p.tok == '<' {
 709                         p.expectSpecial("<-")
 710                         dir = types.SendOnly
 711                 }
 712         } else {
 713                 p.expectSpecial("<-")
 714                 p.expectKeyword("chan")
 715                 dir = types.RecvOnly
 716         }
 717         elem := p.parseType(parent)
 718         return types.NewChan(dir, elem)
 719 }
 720
 721 // Type =
 722 //      BasicType | TypeName | ArrayType | SliceType | StructType |
 723 //      PointerType | FuncType | InterfaceType | MapType | ChanType |
 724 //      "(" Type ")" .
 725 //
 726 // BasicType   = ident .
 727 // TypeName    = ExportedName .
 728 // SliceType   = "[" "]" Type .
 729 // PointerType = "*" Type .
 730 // FuncType    = "func" Signature .
 731 //
 732 func (p *parser) parseType(parent *types.Package) types.Type {
 733         switch p.tok {
 734         case scanner.Ident:
 735                 switch p.lit {
 736                 default:
 737                         return p.parseBasicType()
 738                 case "struct":
 739                         return p.parseStructType(parent)
 740                 case "func":
 741                         // FuncType
 742                         p.next()
 743                         return p.parseSignature(nil)
 744                 case "interface":
 745                         return p.parseInterfaceType(parent)
 746                 case "map":
 747                         return p.parseMapType(parent)
 748                 case "chan":
 749                         return p.parseChanType(parent)
 750                 }
 751         case '@':
 752                 // TypeName
 753                 pkg, name := p.parseExportedName()
 754                 return declTypeName(pkg, name).Type()
 755         case '[':
 756                 p.next() // look ahead
 757                 if p.tok == ']' {
 758                         // SliceType
 759                         p.next()
 760                         return types.NewSlice(p.parseType(parent))
 761                 }
 762                 return p.parseArrayType(parent)
 763         case '*':
 764                 // PointerType
 765                 p.next()
 766                 return types.NewPointer(p.parseType(parent))
 767         case '<':
 768                 return p.parseChanType(parent)
 769         case '(':
 770                 // "(" Type ")"
 771                 p.next()
 772                 typ := p.parseType(parent)
 773                 p.expect(')')
 774                 return typ
 775         }
 776         p.errorf("expected type, got %s (%q)", scanner.TokenString(p.tok), p.lit)
 777         return nil
 778 }
 779
 780 // ----------------------------------------------------------------------------
 781 // Declarations
 782
 783 // ImportDecl = "import" PackageName PackageId .
 784 //
 785 func (p *parser) parseImportDecl() {
 786         p.expectKeyword("import")
 787         name := p.parsePackageName()
 788         p.getPkg(p.parsePackageID(), name)
 789 }
 790
 791 // int_lit = [ "+" | "-" ] { "0" ... "9" } .
 792 //
 793 func (p *parser) parseInt() string {
 794         s := ""
 795         switch p.tok {
 796         case '-':
 797                 s = "-"
 798                 p.next()
 799         case '+':
 800                 p.next()
 801         }
 802         return s + p.expect(scanner.Int)
 803 }
 804
 805 // number = int_lit [ "p" int_lit ] .
 806 //
 807 func (p *parser) parseNumber() (typ *types.Basic, val constant.Value) {
 808         // mantissa
 809         mant := constant.MakeFromLiteral(p.parseInt(), token.INT, 0)
 810         if mant == nil {
 811                 panic("invalid mantissa")
 812         }
 813
 814         if p.lit == "p" {
 815                 // exponent (base 2)
 816                 p.next()
 817                 exp, err := strconv.ParseInt(p.parseInt(), 10, 0)
 818                 if err != nil {
 819                         p.error(err)
 820                 }
 821                 if exp < 0 {
 822                         denom := constant.MakeInt64(1)
 823                         denom = constant.Shift(denom, token.SHL, uint(-exp))
 824                         typ = types.Typ[types.UntypedFloat]
 825                         val = constant.BinaryOp(mant, token.QUO, denom)
 826                         return
 827                 }
 828                 if exp > 0 {
 829                         mant = constant.Shift(mant, token.SHL, uint(exp))
 830                 }
 831                 typ = types.Typ[types.UntypedFloat]
 832                 val = mant
 833                 return
 834         }
 835
 836         typ = types.Typ[types.UntypedInt]
 837         val = mant
 838         return
 839 }
 840
 841 // ConstDecl   = "const" ExportedName [ Type ] "=" Literal .
 842 // Literal     = bool_lit | int_lit | float_lit | complex_lit | rune_lit | string_lit .
 843 // bool_lit    = "true" | "false" .
 844 // complex_lit = "(" float_lit "+" float_lit "i" ")" .
 845 // rune_lit    = "(" int_lit "+" int_lit ")" .
 846 // string_lit  = `"` { unicode_char } `"` .
 847 //
 848 func (p *parser) parseConstDecl() {
 849         p.expectKeyword("const")
 850         pkg, name := p.parseExportedName()
 851
 852         var typ0 types.Type
 853         if p.tok != '=' {
 854                 // constant types are never structured - no need for parent type
 855                 typ0 = p.parseType(nil)
 856         }
 857
 858         p.expect('=')
 859         var typ types.Type
 860         var val constant.Value
 861         switch p.tok {
 862         case scanner.Ident:
 863                 // bool_lit
 864                 if p.lit != "true" && p.lit != "false" {
 865                         p.error("expected true or false")
 866                 }
 867                 typ = types.Typ[types.UntypedBool]
 868                 val = constant.MakeBool(p.lit == "true")
 869                 p.next()
 870
 871         case '-', scanner.Int:
 872                 // int_lit
 873                 typ, val = p.parseNumber()
 874
 875         case '(':
 876                 // complex_lit or rune_lit
 877                 p.next()
 878                 if p.tok == scanner.Char {
 879                         p.next()
 880                         p.expect('+')
 881                         typ = types.Typ[types.UntypedRune]
 882                         _, val = p.parseNumber()
 883                         p.expect(')')
 884                         break
 885                 }
 886                 _, re := p.parseNumber()
 887                 p.expect('+')
 888                 _, im := p.parseNumber()
 889                 p.expectKeyword("i")
 890                 p.expect(')')
 891                 typ = types.Typ[types.UntypedComplex]
 892                 val = constant.BinaryOp(re, token.ADD, constant.MakeImag(im))
 893
 894         case scanner.Char:
 895                 // rune_lit
 896                 typ = types.Typ[types.UntypedRune]
 897                 val = constant.MakeFromLiteral(p.lit, token.CHAR, 0)
 898                 p.next()
 899
 900         case scanner.String:
 901                 // string_lit
 902                 typ = types.Typ[types.UntypedString]
 903                 val = constant.MakeFromLiteral(p.lit, token.STRING, 0)
 904                 p.next()
 905
 906         default:
 907                 p.errorf("expected literal got %s", scanner.TokenString(p.tok))
 908         }
 909
 910         if typ0 == nil {
 911                 typ0 = typ
 912         }
 913
 914         pkg.Scope().Insert(types.NewConst(token.NoPos, pkg, name, typ0, val))
 915 }
 916
 917 // TypeDecl = "type" ExportedName Type .
 918 //
 919 func (p *parser) parseTypeDecl() {
 920         p.expectKeyword("type")
 921         pkg, name := p.parseExportedName()
 922         obj := declTypeName(pkg, name)
 923
 924         // The type object may have been imported before and thus already
 925         // have a type associated with it. We still need to parse the type
 926         // structure, but throw it away if the object already has a type.
 927         // This ensures that all imports refer to the same type object for
 928         // a given type declaration.
 929         typ := p.parseType(pkg)
 930
 931         if name := obj.Type().(*types.Named); name.Underlying() == nil {
 932                 name.SetUnderlying(typ)
 933         }
 934 }
 935
 936 // VarDecl = "var" ExportedName Type .
 937 //
 938 func (p *parser) parseVarDecl() {
 939         p.expectKeyword("var")
 940         pkg, name := p.parseExportedName()
 941         typ := p.parseType(pkg)
 942         pkg.Scope().Insert(types.NewVar(token.NoPos, pkg, name, typ))
 943 }
 944
 945 // Func = Signature [ Body ] .
 946 // Body = "{" ... "}" .
 947 //
 948 func (p *parser) parseFunc(recv *types.Var) *types.Signature {
 949         sig := p.parseSignature(recv)
 950         if p.tok == '{' {
 951                 p.next()
 952                 for i := 1; i > 0; p.next() {
 953                         switch p.tok {
 954                         case '{':
 955                                 i++
 956                         case '}':
 957                                 i--
 958                         }
 959                 }
 960         }
 961         return sig
 962 }
 963
 964 // MethodDecl = "func" Receiver Name Func .
 965 // Receiver   = "(" ( identifier | "?" ) [ "*" ] ExportedName ")" .
 966 //
 967 func (p *parser) parseMethodDecl() {
 968         // "func" already consumed
 969         p.expect('(')
 970         recv, _ := p.parseParameter() // receiver
 971         p.expect(')')
 972
 973         // determine receiver base type object
 974         base := deref(recv.Type()).(*types.Named)
 975
 976         // parse method name, signature, and possibly inlined body
 977         _, name := p.parseName(nil, false)
 978         sig := p.parseFunc(recv)
 979
 980         // methods always belong to the same package as the base type object
 981         pkg := base.Obj().Pkg()
 982
 983         // add method to type unless type was imported before
 984         // and method exists already
 985         // TODO(gri) This leads to a quadratic algorithm - ok for now because method counts are small.
 986         base.AddMethod(types.NewFunc(token.NoPos, pkg, name, sig))
 987 }
 988
 989 // FuncDecl = "func" ExportedName Func .
 990 //
 991 func (p *parser) parseFuncDecl() {
 992         // "func" already consumed
 993         pkg, name := p.parseExportedName()
 994         typ := p.parseFunc(nil)
 995         pkg.Scope().Insert(types.NewFunc(token.NoPos, pkg, name, typ))
 996 }
 997
 998 // Decl = [ ImportDecl | ConstDecl | TypeDecl | VarDecl | FuncDecl | MethodDecl ] "\n" .
 999 //
1000 func (p *parser) parseDecl() {
1001         if p.tok == scanner.Ident {
1002                 switch p.lit {
1003                 case "import":
1004                         p.parseImportDecl()
1005                 case "const":
1006                         p.parseConstDecl()
1007                 case "type":
1008                         p.parseTypeDecl()
1009                 case "var":
1010                         p.parseVarDecl()
1011                 case "func":
1012                         p.next() // look ahead
1013                         if p.tok == '(' {
1014                                 p.parseMethodDecl()
1015                         } else {
1016                                 p.parseFuncDecl()
1017                         }
1018                 }
1019         }
1020         p.expect('\n')
1021 }
1022
1023 // ----------------------------------------------------------------------------
1024 // Export
1025
1026 // Export        = "PackageClause { Decl } "$$" .
1027 // PackageClause = "package" PackageName [ "safe" ] "\n" .
1028 //
1029 func (p *parser) parseExport() *types.Package {
1030         p.expectKeyword("package")
1031         name := p.parsePackageName()
1032         if p.tok == scanner.Ident && p.lit == "safe" {
1033                 // package was compiled with -u option - ignore
1034                 p.next()
1035         }
1036         p.expect('\n')
1037
1038         pkg := p.getPkg(p.id, name)
1039
1040         for p.tok != '$' && p.tok != scanner.EOF {
1041                 p.parseDecl()
1042         }
1043
1044         if ch := p.scanner.Peek(); p.tok != '$' || ch != '$' {
1045                 // don't call next()/expect() since reading past the
1046                 // export data may cause scanner errors (e.g. NUL chars)
1047                 p.errorf("expected '$$', got %s %c", scanner.TokenString(p.tok), ch)
1048         }
1049
1050         if n := p.scanner.ErrorCount; n != 0 {
1051                 p.errorf("expected no scanner errors, got %d", n)
1052         }
1053
1054         // Record all locally referenced packages as imports.
1055         var imports []*types.Package
1056         for id, pkg2 := range p.localPkgs {
1057                 if pkg2.Name() == "" {
1058                         p.errorf("%s package has no name", id)
1059                 }
1060                 if id == p.id {
1061                         continue // avoid self-edge
1062                 }
1063                 imports = append(imports, pkg2)
1064         }
1065         sort.Sort(byPath(imports))
1066         pkg.SetImports(imports)
1067
1068         // package was imported completely and without errors
1069         pkg.MarkComplete()
1070
1071         return pkg
1072 }
1073
1074 type byPath []*types.Package
1075
1076 func (a byPath) Len() int           { return len(a) }
1077 func (a byPath) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
1078 func (a byPath) Less(i, j int) bool { return a[i].Path() < a[j].Path() }