src/cmd/compile/internal/syntax/parser.go

   1 // Copyright 2016 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 package syntax
   6
   7 import (
   8         "fmt"
   9         "go/build/constraint"
  10         "io"
  11         "strconv"
  12         "strings"
  13 )
  14
  15 const debug = false
  16 const trace = false
  17
  18 type parser struct {
  19         file  *PosBase
  20         errh  ErrorHandler
  21         mode  Mode
  22         pragh PragmaHandler
  23         scanner
  24
  25         base      *PosBase // current position base
  26         first     error    // first error encountered
  27         errcnt    int      // number of errors encountered
  28         pragma    Pragma   // pragmas
  29         goVersion string   // Go version from //go:build line
  30
  31         top    bool   // in top of file (before package clause)
  32         fnest  int    // function nesting level (for error handling)
  33         xnest  int    // expression nesting level (for complit ambiguity resolution)
  34         indent []byte // tracing support
  35 }
  36
  37 func (p *parser) init(file *PosBase, r io.Reader, errh ErrorHandler, pragh PragmaHandler, mode Mode) {
  38         p.top = true
  39         p.file = file
  40         p.errh = errh
  41         p.mode = mode
  42         p.pragh = pragh
  43         p.scanner.init(
  44                 r,
  45                 // Error and directive handler for scanner.
  46                 // Because the (line, col) positions passed to the
  47                 // handler is always at or after the current reading
  48                 // position, it is safe to use the most recent position
  49                 // base to compute the corresponding Pos value.
  50                 func(line, col uint, msg string) {
  51                         if msg[0] != '/' {
  52                                 p.errorAt(p.posAt(line, col), msg)
  53                                 return
  54                         }
  55
  56                         // otherwise it must be a comment containing a line or go: directive.
  57                         // //line directives must be at the start of the line (column colbase).
  58                         // /*line*/ directives can be anywhere in the line.
  59                         text := commentText(msg)
  60                         if (col == colbase || msg[1] == '*') && strings.HasPrefix(text, "line ") {
  61                                 var pos Pos // position immediately following the comment
  62                                 if msg[1] == '/' {
  63                                         // line comment (newline is part of the comment)
  64                                         pos = MakePos(p.file, line+1, colbase)
  65                                 } else {
  66                                         // regular comment
  67                                         // (if the comment spans multiple lines it's not
  68                                         // a valid line directive and will be discarded
  69                                         // by updateBase)
  70                                         pos = MakePos(p.file, line, col+uint(len(msg)))
  71                                 }
  72                                 p.updateBase(pos, line, col+2+5, text[5:]) // +2 to skip over // or /*
  73                                 return
  74                         }
  75
  76                         // go: directive (but be conservative and test)
  77                         if strings.HasPrefix(text, "go:") {
  78                                 if p.top && strings.HasPrefix(msg, "//go:build") {
  79                                         if x, err := constraint.Parse(msg); err == nil {
  80                                                 p.goVersion = constraint.GoVersion(x)
  81                                         }
  82                                 }
  83                                 if pragh != nil {
  84                                         p.pragma = pragh(p.posAt(line, col+2), p.scanner.blank, text, p.pragma) // +2 to skip over // or /*
  85                                 }
  86                         }
  87                 },
  88                 directives,
  89         )
  90
  91         p.base = file
  92         p.first = nil
  93         p.errcnt = 0
  94         p.pragma = nil
  95
  96         p.fnest = 0
  97         p.xnest = 0
  98         p.indent = nil
  99 }
 100
 101 // takePragma returns the current parsed pragmas
 102 // and clears them from the parser state.
 103 func (p *parser) takePragma() Pragma {
 104         prag := p.pragma
 105         p.pragma = nil
 106         return prag
 107 }
 108
 109 // clearPragma is called at the end of a statement or
 110 // other Go form that does NOT accept a pragma.
 111 // It sends the pragma back to the pragma handler
 112 // to be reported as unused.
 113 func (p *parser) clearPragma() {
 114         if p.pragma != nil {
 115                 p.pragh(p.pos(), p.scanner.blank, "", p.pragma)
 116                 p.pragma = nil
 117         }
 118 }
 119
 120 // updateBase sets the current position base to a new line base at pos.
 121 // The base's filename, line, and column values are extracted from text
 122 // which is positioned at (tline, tcol) (only needed for error messages).
 123 func (p *parser) updateBase(pos Pos, tline, tcol uint, text string) {
 124         i, n, ok := trailingDigits(text)
 125         if i == 0 {
 126                 return // ignore (not a line directive)
 127         }
 128         // i > 0
 129
 130         if !ok {
 131                 // text has a suffix :xxx but xxx is not a number
 132                 p.errorAt(p.posAt(tline, tcol+i), "invalid line number: "+text[i:])
 133                 return
 134         }
 135
 136         var line, col uint
 137         i2, n2, ok2 := trailingDigits(text[:i-1])
 138         if ok2 {
 139                 //line filename:line:col
 140                 i, i2 = i2, i
 141                 line, col = n2, n
 142                 if col == 0 || col > PosMax {
 143                         p.errorAt(p.posAt(tline, tcol+i2), "invalid column number: "+text[i2:])
 144                         return
 145                 }
 146                 text = text[:i2-1] // lop off ":col"
 147         } else {
 148                 //line filename:line
 149                 line = n
 150         }
 151
 152         if line == 0 || line > PosMax {
 153                 p.errorAt(p.posAt(tline, tcol+i), "invalid line number: "+text[i:])
 154                 return
 155         }
 156
 157         // If we have a column (//line filename:line:col form),
 158         // an empty filename means to use the previous filename.
 159         filename := text[:i-1] // lop off ":line"
 160         trimmed := false
 161         if filename == "" && ok2 {
 162                 filename = p.base.Filename()
 163                 trimmed = p.base.Trimmed()
 164         }
 165
 166         p.base = NewLineBase(pos, filename, trimmed, line, col)
 167 }
 168
 169 func commentText(s string) string {
 170         if s[:2] == "/*" {
 171                 return s[2 : len(s)-2] // lop off /* and */
 172         }
 173
 174         // line comment (does not include newline)
 175         // (on Windows, the line comment may end in \r\n)
 176         i := len(s)
 177         if s[i-1] == '\r' {
 178                 i--
 179         }
 180         return s[2:i] // lop off //, and \r at end, if any
 181 }
 182
 183 func trailingDigits(text string) (uint, uint, bool) {
 184         i := strings.LastIndexByte(text, ':') // look from right (Windows filenames may contain ':')
 185         if i < 0 {
 186                 return 0, 0, false // no ':'
 187         }
 188         // i >= 0
 189         n, err := strconv.ParseUint(text[i+1:], 10, 0)
 190         return uint(i + 1), uint(n), err == nil
 191 }
 192
 193 func (p *parser) got(tok token) bool {
 194         if p.tok == tok {
 195                 p.next()
 196                 return true
 197         }
 198         return false
 199 }
 200
 201 func (p *parser) want(tok token) {
 202         if !p.got(tok) {
 203                 p.syntaxError("expected " + tokstring(tok))
 204                 p.advance()
 205         }
 206 }
 207
 208 // gotAssign is like got(_Assign) but it also accepts ":="
 209 // (and reports an error) for better parser error recovery.
 210 func (p *parser) gotAssign() bool {
 211         switch p.tok {
 212         case _Define:
 213                 p.syntaxError("expected =")
 214                 fallthrough
 215         case _Assign:
 216                 p.next()
 217                 return true
 218         }
 219         return false
 220 }
 221
 222 // ----------------------------------------------------------------------------
 223 // Error handling
 224
 225 // posAt returns the Pos value for (line, col) and the current position base.
 226 func (p *parser) posAt(line, col uint) Pos {
 227         return MakePos(p.base, line, col)
 228 }
 229
 230 // errorAt reports an error at the given position.
 231 func (p *parser) errorAt(pos Pos, msg string) {
 232         err := Error{pos, msg}
 233         if p.first == nil {
 234                 p.first = err
 235         }
 236         p.errcnt++
 237         if p.errh == nil {
 238                 panic(p.first)
 239         }
 240         p.errh(err)
 241 }
 242
 243 // syntaxErrorAt reports a syntax error at the given position.
 244 func (p *parser) syntaxErrorAt(pos Pos, msg string) {
 245         if trace {
 246                 p.print("syntax error: " + msg)
 247         }
 248
 249         if p.tok == _EOF && p.first != nil {
 250                 return // avoid meaningless follow-up errors
 251         }
 252
 253         // add punctuation etc. as needed to msg
 254         switch {
 255         case msg == "":
 256                 // nothing to do
 257         case strings.HasPrefix(msg, "in "), strings.HasPrefix(msg, "at "), strings.HasPrefix(msg, "after "):
 258                 msg = " " + msg
 259         case strings.HasPrefix(msg, "expected "):
 260                 msg = ", " + msg
 261         default:
 262                 // plain error - we don't care about current token
 263                 p.errorAt(pos, "syntax error: "+msg)
 264                 return
 265         }
 266
 267         // determine token string
 268         var tok string
 269         switch p.tok {
 270         case _Name, _Semi:
 271                 tok = p.lit
 272         case _Literal:
 273                 tok = "literal " + p.lit
 274         case _Operator:
 275                 tok = p.op.String()
 276         case _AssignOp:
 277                 tok = p.op.String() + "="
 278         case _IncOp:
 279                 tok = p.op.String()
 280                 tok += tok
 281         default:
 282                 tok = tokstring(p.tok)
 283         }
 284
 285         // TODO(gri) This may print "unexpected X, expected Y".
 286         //           Consider "got X, expected Y" in this case.
 287         p.errorAt(pos, "syntax error: unexpected "+tok+msg)
 288 }
 289
 290 // tokstring returns the English word for selected punctuation tokens
 291 // for more readable error messages. Use tokstring (not tok.String())
 292 // for user-facing (error) messages; use tok.String() for debugging
 293 // output.
 294 func tokstring(tok token) string {
 295         switch tok {
 296         case _Comma:
 297                 return "comma"
 298         case _Semi:
 299                 return "semicolon or newline"
 300         }
 301         return tok.String()
 302 }
 303
 304 // Convenience methods using the current token position.
 305 func (p *parser) pos() Pos               { return p.posAt(p.line, p.col) }
 306 func (p *parser) error(msg string)       { p.errorAt(p.pos(), msg) }
 307 func (p *parser) syntaxError(msg string) { p.syntaxErrorAt(p.pos(), msg) }
 308
 309 // The stopset contains keywords that start a statement.
 310 // They are good synchronization points in case of syntax
 311 // errors and (usually) shouldn't be skipped over.
 312 const stopset uint64 = 1<<_Break |
 313         1<<_Const |
 314         1<<_Continue |
 315         1<<_Defer |
 316         1<<_Fallthrough |
 317         1<<_For |
 318         1<<_Go |
 319         1<<_Goto |
 320         1<<_If |
 321         1<<_Return |
 322         1<<_Select |
 323         1<<_Switch |
 324         1<<_Type |
 325         1<<_Var
 326
 327 // advance consumes tokens until it finds a token of the stopset or followlist.
 328 // The stopset is only considered if we are inside a function (p.fnest > 0).
 329 // The followlist is the list of valid tokens that can follow a production;
 330 // if it is empty, exactly one (non-EOF) token is consumed to ensure progress.
 331 func (p *parser) advance(followlist ...token) {
 332         if trace {
 333                 p.print(fmt.Sprintf("advance %s", followlist))
 334         }
 335
 336         // compute follow set
 337         // (not speed critical, advance is only called in error situations)
 338         var followset uint64 = 1 << _EOF // don't skip over EOF
 339         if len(followlist) > 0 {
 340                 if p.fnest > 0 {
 341                         followset |= stopset
 342                 }
 343                 for _, tok := range followlist {
 344                         followset |= 1 << tok
 345                 }
 346         }
 347
 348         for !contains(followset, p.tok) {
 349                 if trace {
 350                         p.print("skip " + p.tok.String())
 351                 }
 352                 p.next()
 353                 if len(followlist) == 0 {
 354                         break
 355                 }
 356         }
 357
 358         if trace {
 359                 p.print("next " + p.tok.String())
 360         }
 361 }
 362
 363 // usage: defer p.trace(msg)()
 364 func (p *parser) trace(msg string) func() {
 365         p.print(msg + " (")
 366         const tab = ". "
 367         p.indent = append(p.indent, tab...)
 368         return func() {
 369                 p.indent = p.indent[:len(p.indent)-len(tab)]
 370                 if x := recover(); x != nil {
 371                         panic(x) // skip print_trace
 372                 }
 373                 p.print(")")
 374         }
 375 }
 376
 377 func (p *parser) print(msg string) {
 378         fmt.Printf("%5d: %s%s\n", p.line, p.indent, msg)
 379 }
 380
 381 // ----------------------------------------------------------------------------
 382 // Package files
 383 //
 384 // Parse methods are annotated with matching Go productions as appropriate.
 385 // The annotations are intended as guidelines only since a single Go grammar
 386 // rule may be covered by multiple parse methods and vice versa.
 387 //
 388 // Excluding methods returning slices, parse methods named xOrNil may return
 389 // nil; all others are expected to return a valid non-nil node.
 390
 391 // SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" } .
 392 func (p *parser) fileOrNil() *File {
 393         if trace {
 394                 defer p.trace("file")()
 395         }
 396
 397         f := new(File)
 398         f.pos = p.pos()
 399
 400         // PackageClause
 401         f.GoVersion = p.goVersion
 402         p.top = false
 403         if !p.got(_Package) {
 404                 p.syntaxError("package statement must be first")
 405                 return nil
 406         }
 407         f.Pragma = p.takePragma()
 408         f.PkgName = p.name()
 409         p.want(_Semi)
 410
 411         // don't bother continuing if package clause has errors
 412         if p.first != nil {
 413                 return nil
 414         }
 415
 416         // Accept import declarations anywhere for error tolerance, but complain.
 417         // { ( ImportDecl | TopLevelDecl ) ";" }
 418         prev := _Import
 419         for p.tok != _EOF {
 420                 if p.tok == _Import && prev != _Import {
 421                         p.syntaxError("imports must appear before other declarations")
 422                 }
 423                 prev = p.tok
 424
 425                 switch p.tok {
 426                 case _Import:
 427                         p.next()
 428                         f.DeclList = p.appendGroup(f.DeclList, p.importDecl)
 429
 430                 case _Const:
 431                         p.next()
 432                         f.DeclList = p.appendGroup(f.DeclList, p.constDecl)
 433
 434                 case _Type:
 435                         p.next()
 436                         f.DeclList = p.appendGroup(f.DeclList, p.typeDecl)
 437
 438                 case _Var:
 439                         p.next()
 440                         f.DeclList = p.appendGroup(f.DeclList, p.varDecl)
 441
 442                 case _Func:
 443                         p.next()
 444                         if d := p.funcDeclOrNil(); d != nil {
 445                                 f.DeclList = append(f.DeclList, d)
 446                         }
 447
 448                 default:
 449                         if p.tok == _Lbrace && len(f.DeclList) > 0 && isEmptyFuncDecl(f.DeclList[len(f.DeclList)-1]) {
 450                                 // opening { of function declaration on next line
 451                                 p.syntaxError("unexpected semicolon or newline before {")
 452                         } else {
 453                                 p.syntaxError("non-declaration statement outside function body")
 454                         }
 455                         p.advance(_Import, _Const, _Type, _Var, _Func)
 456                         continue
 457                 }
 458
 459                 // Reset p.pragma BEFORE advancing to the next token (consuming ';')
 460                 // since comments before may set pragmas for the next function decl.
 461                 p.clearPragma()
 462
 463                 if p.tok != _EOF && !p.got(_Semi) {
 464                         p.syntaxError("after top level declaration")
 465                         p.advance(_Import, _Const, _Type, _Var, _Func)
 466                 }
 467         }
 468         // p.tok == _EOF
 469
 470         p.clearPragma()
 471         f.EOF = p.pos()
 472
 473         return f
 474 }
 475
 476 func isEmptyFuncDecl(dcl Decl) bool {
 477         f, ok := dcl.(*FuncDecl)
 478         return ok && f.Body == nil
 479 }
 480
 481 // ----------------------------------------------------------------------------
 482 // Declarations
 483
 484 // list parses a possibly empty, sep-separated list of elements, optionally
 485 // followed by sep, and closed by close (or EOF). sep must be one of _Comma
 486 // or _Semi, and close must be one of _Rparen, _Rbrace, or _Rbrack.
 487 //
 488 // For each list element, f is called. Specifically, unless we're at close
 489 // (or EOF), f is called at least once. After f returns true, no more list
 490 // elements are accepted. list returns the position of the closing token.
 491 //
 492 // list = [ f { sep f } [sep] ] close .
 493 func (p *parser) list(context string, sep, close token, f func() bool) Pos {
 494         if debug && (sep != _Comma && sep != _Semi || close != _Rparen && close != _Rbrace && close != _Rbrack) {
 495                 panic("invalid sep or close argument for list")
 496         }
 497
 498         done := false
 499         for p.tok != _EOF && p.tok != close && !done {
 500                 done = f()
 501                 // sep is optional before close
 502                 if !p.got(sep) && p.tok != close {
 503                         p.syntaxError(fmt.Sprintf("in %s; possibly missing %s or %s", context, tokstring(sep), tokstring(close)))
 504                         p.advance(_Rparen, _Rbrack, _Rbrace)
 505                         if p.tok != close {
 506                                 // position could be better but we had an error so we don't care
 507                                 return p.pos()
 508                         }
 509                 }
 510         }
 511
 512         pos := p.pos()
 513         p.want(close)
 514         return pos
 515 }
 516
 517 // appendGroup(f) = f | "(" { f ";" } ")" . // ";" is optional before ")"
 518 func (p *parser) appendGroup(list []Decl, f func(*Group) Decl) []Decl {
 519         if p.tok == _Lparen {
 520                 g := new(Group)
 521                 p.clearPragma()
 522                 p.next() // must consume "(" after calling clearPragma!
 523                 p.list("grouped declaration", _Semi, _Rparen, func() bool {
 524                         if x := f(g); x != nil {
 525                                 list = append(list, x)
 526                         }
 527                         return false
 528                 })
 529         } else {
 530                 if x := f(nil); x != nil {
 531                         list = append(list, x)
 532                 }
 533         }
 534         return list
 535 }
 536
 537 // ImportSpec = [ "." | PackageName ] ImportPath .
 538 // ImportPath = string_lit .
 539 func (p *parser) importDecl(group *Group) Decl {
 540         if trace {
 541                 defer p.trace("importDecl")()
 542         }
 543
 544         d := new(ImportDecl)
 545         d.pos = p.pos()
 546         d.Group = group
 547         d.Pragma = p.takePragma()
 548
 549         switch p.tok {
 550         case _Name:
 551                 d.LocalPkgName = p.name()
 552         case _Dot:
 553                 d.LocalPkgName = NewName(p.pos(), ".")
 554                 p.next()
 555         }
 556         d.Path = p.oliteral()
 557         if d.Path == nil {
 558                 p.syntaxError("missing import path")
 559                 p.advance(_Semi, _Rparen)
 560                 return d
 561         }
 562         if !d.Path.Bad && d.Path.Kind != StringLit {
 563                 p.syntaxErrorAt(d.Path.Pos(), "import path must be a string")
 564                 d.Path.Bad = true
 565         }
 566         // d.Path.Bad || d.Path.Kind == StringLit
 567
 568         return d
 569 }
 570
 571 // ConstSpec = IdentifierList [ [ Type ] "=" ExpressionList ] .
 572 func (p *parser) constDecl(group *Group) Decl {
 573         if trace {
 574                 defer p.trace("constDecl")()
 575         }
 576
 577         d := new(ConstDecl)
 578         d.pos = p.pos()
 579         d.Group = group
 580         d.Pragma = p.takePragma()
 581
 582         d.NameList = p.nameList(p.name())
 583         if p.tok != _EOF && p.tok != _Semi && p.tok != _Rparen {
 584                 d.Type = p.typeOrNil()
 585                 if p.gotAssign() {
 586                         d.Values = p.exprList()
 587                 }
 588         }
 589
 590         return d
 591 }
 592
 593 // TypeSpec = identifier [ TypeParams ] [ "=" ] Type .
 594 func (p *parser) typeDecl(group *Group) Decl {
 595         if trace {
 596                 defer p.trace("typeDecl")()
 597         }
 598
 599         d := new(TypeDecl)
 600         d.pos = p.pos()
 601         d.Group = group
 602         d.Pragma = p.takePragma()
 603
 604         d.Name = p.name()
 605         if p.tok == _Lbrack {
 606                 // d.Name "[" ...
 607                 // array/slice type or type parameter list
 608                 pos := p.pos()
 609                 p.next()
 610                 switch p.tok {
 611                 case _Name:
 612                         // We may have an array type or a type parameter list.
 613                         // In either case we expect an expression x (which may
 614                         // just be a name, or a more complex expression) which
 615                         // we can analyze further.
 616                         //
 617                         // A type parameter list may have a type bound starting
 618                         // with a "[" as in: P []E. In that case, simply parsing
 619                         // an expression would lead to an error: P[] is invalid.
 620                         // But since index or slice expressions are never constant
 621                         // and thus invalid array length expressions, if the name
 622                         // is followed by "[" it must be the start of an array or
 623                         // slice constraint. Only if we don't see a "[" do we
 624                         // need to parse a full expression. Notably, name <- x
 625                         // is not a concern because name <- x is a statement and
 626                         // not an expression.
 627                         var x Expr = p.name()
 628                         if p.tok != _Lbrack {
 629                                 // To parse the expression starting with name, expand
 630                                 // the call sequence we would get by passing in name
 631                                 // to parser.expr, and pass in name to parser.pexpr.
 632                                 p.xnest++
 633                                 x = p.binaryExpr(p.pexpr(x, false), 0)
 634                                 p.xnest--
 635                         }
 636                         // Analyze expression x. If we can split x into a type parameter
 637                         // name, possibly followed by a type parameter type, we consider
 638                         // this the start of a type parameter list, with some caveats:
 639                         // a single name followed by "]" tilts the decision towards an
 640                         // array declaration; a type parameter type that could also be
 641                         // an ordinary expression but which is followed by a comma tilts
 642                         // the decision towards a type parameter list.
 643                         if pname, ptype := extractName(x, p.tok == _Comma); pname != nil && (ptype != nil || p.tok != _Rbrack) {
 644                                 // d.Name "[" pname ...
 645                                 // d.Name "[" pname ptype ...
 646                                 // d.Name "[" pname ptype "," ...
 647                                 d.TParamList = p.paramList(pname, ptype, _Rbrack, true) // ptype may be nil
 648                                 d.Alias = p.gotAssign()
 649                                 d.Type = p.typeOrNil()
 650                         } else {
 651                                 // d.Name "[" pname "]" ...
 652                                 // d.Name "[" x ...
 653                                 d.Type = p.arrayType(pos, x)
 654                         }
 655                 case _Rbrack:
 656                         // d.Name "[" "]" ...
 657                         p.next()
 658                         d.Type = p.sliceType(pos)
 659                 default:
 660                         // d.Name "[" ...
 661                         d.Type = p.arrayType(pos, nil)
 662                 }
 663         } else {
 664                 d.Alias = p.gotAssign()
 665                 d.Type = p.typeOrNil()
 666         }
 667
 668         if d.Type == nil {
 669                 d.Type = p.badExpr()
 670                 p.syntaxError("in type declaration")
 671                 p.advance(_Semi, _Rparen)
 672         }
 673
 674         return d
 675 }
 676
 677 // extractName splits the expression x into (name, expr) if syntactically
 678 // x can be written as name expr. The split only happens if expr is a type
 679 // element (per the isTypeElem predicate) or if force is set.
 680 // If x is just a name, the result is (name, nil). If the split succeeds,
 681 // the result is (name, expr). Otherwise the result is (nil, x).
 682 // Examples:
 683 //
 684 //      x           force    name    expr
 685 //      ------------------------------------
 686 //      P*[]int     T/F      P       *[]int
 687 //      P*E         T        P       *E
 688 //      P*E         F        nil     P*E
 689 //      P([]int)    T/F      P       []int
 690 //      P(E)        T        P       E
 691 //      P(E)        F        nil     P(E)
 692 //      P*E|F|~G    T/F      P       *E|F|~G
 693 //      P*E|F|G     T        P       *E|F|G
 694 //      P*E|F|G     F        nil     P*E|F|G
 695 func extractName(x Expr, force bool) (*Name, Expr) {
 696         switch x := x.(type) {
 697         case *Name:
 698                 return x, nil
 699         case *Operation:
 700                 if x.Y == nil {
 701                         break // unary expr
 702                 }
 703                 switch x.Op {
 704                 case Mul:
 705                         if name, _ := x.X.(*Name); name != nil && (force || isTypeElem(x.Y)) {
 706                                 // x = name *x.Y
 707                                 op := *x
 708                                 op.X, op.Y = op.Y, nil // change op into unary *op.Y
 709                                 return name, &op
 710                         }
 711                 case Or:
 712                         if name, lhs := extractName(x.X, force || isTypeElem(x.Y)); name != nil && lhs != nil {
 713                                 // x = name lhs|x.Y
 714                                 op := *x
 715                                 op.X = lhs
 716                                 return name, &op
 717                         }
 718                 }
 719         case *CallExpr:
 720                 if name, _ := x.Fun.(*Name); name != nil {
 721                         if len(x.ArgList) == 1 && !x.HasDots && (force || isTypeElem(x.ArgList[0])) {
 722                                 // x = name "(" x.ArgList[0] ")"
 723                                 return name, x.ArgList[0]
 724                         }
 725                 }
 726         }
 727         return nil, x
 728 }
 729
 730 // isTypeElem reports whether x is a (possibly parenthesized) type element expression.
 731 // The result is false if x could be a type element OR an ordinary (value) expression.
 732 func isTypeElem(x Expr) bool {
 733         switch x := x.(type) {
 734         case *ArrayType, *StructType, *FuncType, *InterfaceType, *SliceType, *MapType, *ChanType:
 735                 return true
 736         case *Operation:
 737                 return isTypeElem(x.X) || (x.Y != nil && isTypeElem(x.Y)) || x.Op == Tilde
 738         case *ParenExpr:
 739                 return isTypeElem(x.X)
 740         }
 741         return false
 742 }
 743
 744 // VarSpec = IdentifierList ( Type [ "=" ExpressionList ] | "=" ExpressionList ) .
 745 func (p *parser) varDecl(group *Group) Decl {
 746         if trace {
 747                 defer p.trace("varDecl")()
 748         }
 749
 750         d := new(VarDecl)
 751         d.pos = p.pos()
 752         d.Group = group
 753         d.Pragma = p.takePragma()
 754
 755         d.NameList = p.nameList(p.name())
 756         if p.gotAssign() {
 757                 d.Values = p.exprList()
 758         } else {
 759                 d.Type = p.type_()
 760                 if p.gotAssign() {
 761                         d.Values = p.exprList()
 762                 }
 763         }
 764
 765         return d
 766 }
 767
 768 // FunctionDecl = "func" FunctionName [ TypeParams ] ( Function | Signature ) .
 769 // FunctionName = identifier .
 770 // Function     = Signature FunctionBody .
 771 // MethodDecl   = "func" Receiver MethodName ( Function | Signature ) .
 772 // Receiver     = Parameters .
 773 func (p *parser) funcDeclOrNil() *FuncDecl {
 774         if trace {
 775                 defer p.trace("funcDecl")()
 776         }
 777
 778         f := new(FuncDecl)
 779         f.pos = p.pos()
 780         f.Pragma = p.takePragma()
 781
 782         var context string
 783         if p.got(_Lparen) {
 784                 context = "method"
 785                 rcvr := p.paramList(nil, nil, _Rparen, false)
 786                 switch len(rcvr) {
 787                 case 0:
 788                         p.error("method has no receiver")
 789                 default:
 790                         p.error("method has multiple receivers")
 791                         fallthrough
 792                 case 1:
 793                         f.Recv = rcvr[0]
 794                 }
 795         }
 796
 797         if p.tok == _Name {
 798                 f.Name = p.name()
 799                 f.TParamList, f.Type = p.funcType(context)
 800         } else {
 801                 f.Name = NewName(p.pos(), "_")
 802                 f.Type = new(FuncType)
 803                 f.Type.pos = p.pos()
 804                 msg := "expected name or ("
 805                 if context != "" {
 806                         msg = "expected name"
 807                 }
 808                 p.syntaxError(msg)
 809                 p.advance(_Lbrace, _Semi)
 810         }
 811
 812         if p.tok == _Lbrace {
 813                 f.Body = p.funcBody()
 814         }
 815
 816         return f
 817 }
 818
 819 func (p *parser) funcBody() *BlockStmt {
 820         p.fnest++
 821         errcnt := p.errcnt
 822         body := p.blockStmt("")
 823         p.fnest--
 824
 825         // Don't check branches if there were syntax errors in the function
 826         // as it may lead to spurious errors (e.g., see test/switch2.go) or
 827         // possibly crashes due to incomplete syntax trees.
 828         if p.mode&CheckBranches != 0 && errcnt == p.errcnt {
 829                 checkBranches(body, p.errh)
 830         }
 831
 832         return body
 833 }
 834
 835 // ----------------------------------------------------------------------------
 836 // Expressions
 837
 838 func (p *parser) expr() Expr {
 839         if trace {
 840                 defer p.trace("expr")()
 841         }
 842
 843         return p.binaryExpr(nil, 0)
 844 }
 845
 846 // Expression = UnaryExpr | Expression binary_op Expression .
 847 func (p *parser) binaryExpr(x Expr, prec int) Expr {
 848         // don't trace binaryExpr - only leads to overly nested trace output
 849
 850         if x == nil {
 851                 x = p.unaryExpr()
 852         }
 853         for (p.tok == _Operator || p.tok == _Star) && p.prec > prec {
 854                 t := new(Operation)
 855                 t.pos = p.pos()
 856                 t.Op = p.op
 857                 tprec := p.prec
 858                 p.next()
 859                 t.X = x
 860                 t.Y = p.binaryExpr(nil, tprec)
 861                 x = t
 862         }
 863         return x
 864 }
 865
 866 // UnaryExpr = PrimaryExpr | unary_op UnaryExpr .
 867 func (p *parser) unaryExpr() Expr {
 868         if trace {
 869                 defer p.trace("unaryExpr")()
 870         }
 871
 872         switch p.tok {
 873         case _Operator, _Star:
 874                 switch p.op {
 875                 case Mul, Add, Sub, Not, Xor, Tilde:
 876                         x := new(Operation)
 877                         x.pos = p.pos()
 878                         x.Op = p.op
 879                         p.next()
 880                         x.X = p.unaryExpr()
 881                         return x
 882
 883                 case And:
 884                         x := new(Operation)
 885                         x.pos = p.pos()
 886                         x.Op = And
 887                         p.next()
 888                         // unaryExpr may have returned a parenthesized composite literal
 889                         // (see comment in operand) - remove parentheses if any
 890                         x.X = Unparen(p.unaryExpr())
 891                         return x
 892                 }
 893
 894         case _Arrow:
 895                 // receive op (<-x) or receive-only channel (<-chan E)
 896                 pos := p.pos()
 897                 p.next()
 898
 899                 // If the next token is _Chan we still don't know if it is
 900                 // a channel (<-chan int) or a receive op (<-chan int(ch)).
 901                 // We only know once we have found the end of the unaryExpr.
 902
 903                 x := p.unaryExpr()
 904
 905                 // There are two cases:
 906                 //
 907                 //   <-chan...  => <-x is a channel type
 908                 //   <-x        => <-x is a receive operation
 909                 //
 910                 // In the first case, <- must be re-associated with
 911                 // the channel type parsed already:
 912                 //
 913                 //   <-(chan E)   =>  (<-chan E)
 914                 //   <-(chan<-E)  =>  (<-chan (<-E))
 915
 916                 if _, ok := x.(*ChanType); ok {
 917                         // x is a channel type => re-associate <-
 918                         dir := SendOnly
 919                         t := x
 920                         for dir == SendOnly {
 921                                 c, ok := t.(*ChanType)
 922                                 if !ok {
 923                                         break
 924                                 }
 925                                 dir = c.Dir
 926                                 if dir == RecvOnly {
 927                                         // t is type <-chan E but <-<-chan E is not permitted
 928                                         // (report same error as for "type _ <-<-chan E")
 929                                         p.syntaxError("unexpected <-, expected chan")
 930                                         // already progressed, no need to advance
 931                                 }
 932                                 c.Dir = RecvOnly
 933                                 t = c.Elem
 934                         }
 935                         if dir == SendOnly {
 936                                 // channel dir is <- but channel element E is not a channel
 937                                 // (report same error as for "type _ <-chan<-E")
 938                                 p.syntaxError(fmt.Sprintf("unexpected %s, expected chan", String(t)))
 939                                 // already progressed, no need to advance
 940                         }
 941                         return x
 942                 }
 943
 944                 // x is not a channel type => we have a receive op
 945                 o := new(Operation)
 946                 o.pos = pos
 947                 o.Op = Recv
 948                 o.X = x
 949                 return o
 950         }
 951
 952         // TODO(mdempsky): We need parens here so we can report an
 953         // error for "(x) := true". It should be possible to detect
 954         // and reject that more efficiently though.
 955         return p.pexpr(nil, true)
 956 }
 957
 958 // callStmt parses call-like statements that can be preceded by 'defer' and 'go'.
 959 func (p *parser) callStmt() *CallStmt {
 960         if trace {
 961                 defer p.trace("callStmt")()
 962         }
 963
 964         s := new(CallStmt)
 965         s.pos = p.pos()
 966         s.Tok = p.tok // _Defer or _Go
 967         p.next()
 968
 969         x := p.pexpr(nil, p.tok == _Lparen) // keep_parens so we can report error below
 970         if t := Unparen(x); t != x {
 971                 p.errorAt(x.Pos(), fmt.Sprintf("expression in %s must not be parenthesized", s.Tok))
 972                 // already progressed, no need to advance
 973                 x = t
 974         }
 975
 976         s.Call = x
 977         return s
 978 }
 979
 980 // Operand     = Literal | OperandName | MethodExpr | "(" Expression ")" .
 981 // Literal     = BasicLit | CompositeLit | FunctionLit .
 982 // BasicLit    = int_lit | float_lit | imaginary_lit | rune_lit | string_lit .
 983 // OperandName = identifier | QualifiedIdent.
 984 func (p *parser) operand(keep_parens bool) Expr {
 985         if trace {
 986                 defer p.trace("operand " + p.tok.String())()
 987         }
 988
 989         switch p.tok {
 990         case _Name:
 991                 return p.name()
 992
 993         case _Literal:
 994                 return p.oliteral()
 995
 996         case _Lparen:
 997                 pos := p.pos()
 998                 p.next()
 999                 p.xnest++
1000                 x := p.expr()
1001                 p.xnest--
1002                 p.want(_Rparen)
1003
1004                 // Optimization: Record presence of ()'s only where needed
1005                 // for error reporting. Don't bother in other cases; it is
1006                 // just a waste of memory and time.
1007                 //
1008                 // Parentheses are not permitted around T in a composite
1009                 // literal T{}. If the next token is a {, assume x is a
1010                 // composite literal type T (it may not be, { could be
1011                 // the opening brace of a block, but we don't know yet).
1012                 if p.tok == _Lbrace {
1013                         keep_parens = true
1014                 }
1015
1016                 // Parentheses are also not permitted around the expression
1017                 // in a go/defer statement. In that case, operand is called
1018                 // with keep_parens set.
1019                 if keep_parens {
1020                         px := new(ParenExpr)
1021                         px.pos = pos
1022                         px.X = x
1023                         x = px
1024                 }
1025                 return x
1026
1027         case _Func:
1028                 pos := p.pos()
1029                 p.next()
1030                 _, ftyp := p.funcType("function type")
1031                 if p.tok == _Lbrace {
1032                         p.xnest++
1033
1034                         f := new(FuncLit)
1035                         f.pos = pos
1036                         f.Type = ftyp
1037                         f.Body = p.funcBody()
1038
1039                         p.xnest--
1040                         return f
1041                 }
1042                 return ftyp
1043
1044         case _Lbrack, _Chan, _Map, _Struct, _Interface:
1045                 return p.type_() // othertype
1046
1047         default:
1048                 x := p.badExpr()
1049                 p.syntaxError("expected expression")
1050                 p.advance(_Rparen, _Rbrack, _Rbrace)
1051                 return x
1052         }
1053
1054         // Syntactically, composite literals are operands. Because a complit
1055         // type may be a qualified identifier which is handled by pexpr
1056         // (together with selector expressions), complits are parsed there
1057         // as well (operand is only called from pexpr).
1058 }
1059
1060 // pexpr parses a PrimaryExpr.
1061 //
1062 //      PrimaryExpr =
1063 //              Operand |
1064 //              Conversion |
1065 //              PrimaryExpr Selector |
1066 //              PrimaryExpr Index |
1067 //              PrimaryExpr Slice |
1068 //              PrimaryExpr TypeAssertion |
1069 //              PrimaryExpr Arguments .
1070 //
1071 //      Selector       = "." identifier .
1072 //      Index          = "[" Expression "]" .
1073 //      Slice          = "[" ( [ Expression ] ":" [ Expression ] ) |
1074 //                           ( [ Expression ] ":" Expression ":" Expression )
1075 //                       "]" .
1076 //      TypeAssertion  = "." "(" Type ")" .
1077 //      Arguments      = "(" [ ( ExpressionList | Type [ "," ExpressionList ] ) [ "..." ] [ "," ] ] ")" .
1078 func (p *parser) pexpr(x Expr, keep_parens bool) Expr {
1079         if trace {
1080                 defer p.trace("pexpr")()
1081         }
1082
1083         if x == nil {
1084                 x = p.operand(keep_parens)
1085         }
1086
1087 loop:
1088         for {
1089                 pos := p.pos()
1090                 switch p.tok {
1091                 case _Dot:
1092                         p.next()
1093                         switch p.tok {
1094                         case _Name:
1095                                 // pexpr '.' sym
1096                                 t := new(SelectorExpr)
1097                                 t.pos = pos
1098                                 t.X = x
1099                                 t.Sel = p.name()
1100                                 x = t
1101
1102                         case _Lparen:
1103                                 p.next()
1104                                 if p.got(_Type) {
1105                                         t := new(TypeSwitchGuard)
1106                                         // t.Lhs is filled in by parser.simpleStmt
1107                                         t.pos = pos
1108                                         t.X = x
1109                                         x = t
1110                                 } else {
1111                                         t := new(AssertExpr)
1112                                         t.pos = pos
1113                                         t.X = x
1114                                         t.Type = p.type_()
1115                                         x = t
1116                                 }
1117                                 p.want(_Rparen)
1118
1119                         default:
1120                                 p.syntaxError("expected name or (")
1121                                 p.advance(_Semi, _Rparen)
1122                         }
1123
1124                 case _Lbrack:
1125                         p.next()
1126
1127                         var i Expr
1128                         if p.tok != _Colon {
1129                                 var comma bool
1130                                 if p.tok == _Rbrack {
1131                                         // invalid empty instance, slice or index expression; accept but complain
1132                                         p.syntaxError("expected operand")
1133                                         i = p.badExpr()
1134                                 } else {
1135                                         i, comma = p.typeList(false)
1136                                 }
1137                                 if comma || p.tok == _Rbrack {
1138                                         p.want(_Rbrack)
1139                                         // x[], x[i,] or x[i, j, ...]
1140                                         t := new(IndexExpr)
1141                                         t.pos = pos
1142                                         t.X = x
1143                                         t.Index = i
1144                                         x = t
1145                                         break
1146                                 }
1147                         }
1148
1149                         // x[i:...
1150                         // For better error message, don't simply use p.want(_Colon) here (issue #47704).
1151                         if !p.got(_Colon) {
1152                                 p.syntaxError("expected comma, : or ]")
1153                                 p.advance(_Comma, _Colon, _Rbrack)
1154                         }
1155                         p.xnest++
1156                         t := new(SliceExpr)
1157                         t.pos = pos
1158                         t.X = x
1159                         t.Index[0] = i
1160                         if p.tok != _Colon && p.tok != _Rbrack {
1161                                 // x[i:j...
1162                                 t.Index[1] = p.expr()
1163                         }
1164                         if p.tok == _Colon {
1165                                 t.Full = true
1166                                 // x[i:j:...]
1167                                 if t.Index[1] == nil {
1168                                         p.error("middle index required in 3-index slice")
1169                                         t.Index[1] = p.badExpr()
1170                                 }
1171                                 p.next()
1172                                 if p.tok != _Rbrack {
1173                                         // x[i:j:k...
1174                                         t.Index[2] = p.expr()
1175                                 } else {
1176                                         p.error("final index required in 3-index slice")
1177                                         t.Index[2] = p.badExpr()
1178                                 }
1179                         }
1180                         p.xnest--
1181                         p.want(_Rbrack)
1182                         x = t
1183
1184                 case _Lparen:
1185                         t := new(CallExpr)
1186                         t.pos = pos
1187                         p.next()
1188                         t.Fun = x
1189                         t.ArgList, t.HasDots = p.argList()
1190                         x = t
1191
1192                 case _Lbrace:
1193                         // operand may have returned a parenthesized complit
1194                         // type; accept it but complain if we have a complit
1195                         t := Unparen(x)
1196                         // determine if '{' belongs to a composite literal or a block statement
1197                         complit_ok := false
1198                         switch t.(type) {
1199                         case *Name, *SelectorExpr:
1200                                 if p.xnest >= 0 {
1201                                         // x is possibly a composite literal type
1202                                         complit_ok = true
1203                                 }
1204                         case *IndexExpr:
1205                                 if p.xnest >= 0 && !isValue(t) {
1206                                         // x is possibly a composite literal type
1207                                         complit_ok = true
1208                                 }
1209                         case *ArrayType, *SliceType, *StructType, *MapType:
1210                                 // x is a comptype
1211                                 complit_ok = true
1212                         }
1213                         if !complit_ok {
1214                                 break loop
1215                         }
1216                         if t != x {
1217                                 p.syntaxError("cannot parenthesize type in composite literal")
1218                                 // already progressed, no need to advance
1219                         }
1220                         n := p.complitexpr()
1221                         n.Type = x
1222                         x = n
1223
1224                 default:
1225                         break loop
1226                 }
1227         }
1228
1229         return x
1230 }
1231
1232 // isValue reports whether x syntactically must be a value (and not a type) expression.
1233 func isValue(x Expr) bool {
1234         switch x := x.(type) {
1235         case *BasicLit, *CompositeLit, *FuncLit, *SliceExpr, *AssertExpr, *TypeSwitchGuard, *CallExpr:
1236                 return true
1237         case *Operation:
1238                 return x.Op != Mul || x.Y != nil // *T may be a type
1239         case *ParenExpr:
1240                 return isValue(x.X)
1241         case *IndexExpr:
1242                 return isValue(x.X) || isValue(x.Index)
1243         }
1244         return false
1245 }
1246
1247 // Element = Expression | LiteralValue .
1248 func (p *parser) bare_complitexpr() Expr {
1249         if trace {
1250                 defer p.trace("bare_complitexpr")()
1251         }
1252
1253         if p.tok == _Lbrace {
1254                 // '{' start_complit braced_keyval_list '}'
1255                 return p.complitexpr()
1256         }
1257
1258         return p.expr()
1259 }
1260
1261 // LiteralValue = "{" [ ElementList [ "," ] ] "}" .
1262 func (p *parser) complitexpr() *CompositeLit {
1263         if trace {
1264                 defer p.trace("complitexpr")()
1265         }
1266
1267         x := new(CompositeLit)
1268         x.pos = p.pos()
1269
1270         p.xnest++
1271         p.want(_Lbrace)
1272         x.Rbrace = p.list("composite literal", _Comma, _Rbrace, func() bool {
1273                 // value
1274                 e := p.bare_complitexpr()
1275                 if p.tok == _Colon {
1276                         // key ':' value
1277                         l := new(KeyValueExpr)
1278                         l.pos = p.pos()
1279                         p.next()
1280                         l.Key = e
1281                         l.Value = p.bare_complitexpr()
1282                         e = l
1283                         x.NKeys++
1284                 }
1285                 x.ElemList = append(x.ElemList, e)
1286                 return false
1287         })
1288         p.xnest--
1289
1290         return x
1291 }
1292
1293 // ----------------------------------------------------------------------------
1294 // Types
1295
1296 func (p *parser) type_() Expr {
1297         if trace {
1298                 defer p.trace("type_")()
1299         }
1300
1301         typ := p.typeOrNil()
1302         if typ == nil {
1303                 typ = p.badExpr()
1304                 p.syntaxError("expected type")
1305                 p.advance(_Comma, _Colon, _Semi, _Rparen, _Rbrack, _Rbrace)
1306         }
1307
1308         return typ
1309 }
1310
1311 func newIndirect(pos Pos, typ Expr) Expr {
1312         o := new(Operation)
1313         o.pos = pos
1314         o.Op = Mul
1315         o.X = typ
1316         return o
1317 }
1318
1319 // typeOrNil is like type_ but it returns nil if there was no type
1320 // instead of reporting an error.
1321 //
1322 //      Type     = TypeName | TypeLit | "(" Type ")" .
1323 //      TypeName = identifier | QualifiedIdent .
1324 //      TypeLit  = ArrayType | StructType | PointerType | FunctionType | InterfaceType |
1325 //                    SliceType | MapType | Channel_Type .
1326 func (p *parser) typeOrNil() Expr {
1327         if trace {
1328                 defer p.trace("typeOrNil")()
1329         }
1330
1331         pos := p.pos()
1332         switch p.tok {
1333         case _Star:
1334                 // ptrtype
1335                 p.next()
1336                 return newIndirect(pos, p.type_())
1337
1338         case _Arrow:
1339                 // recvchantype
1340                 p.next()
1341                 p.want(_Chan)
1342                 t := new(ChanType)
1343                 t.pos = pos
1344                 t.Dir = RecvOnly
1345                 t.Elem = p.chanElem()
1346                 return t
1347
1348         case _Func:
1349                 // fntype
1350                 p.next()
1351                 _, t := p.funcType("function type")
1352                 return t
1353
1354         case _Lbrack:
1355                 // '[' oexpr ']' ntype
1356                 // '[' _DotDotDot ']' ntype
1357                 p.next()
1358                 if p.got(_Rbrack) {
1359                         return p.sliceType(pos)
1360                 }
1361                 return p.arrayType(pos, nil)
1362
1363         case _Chan:
1364                 // _Chan non_recvchantype
1365                 // _Chan _Comm ntype
1366                 p.next()
1367                 t := new(ChanType)
1368                 t.pos = pos
1369                 if p.got(_Arrow) {
1370                         t.Dir = SendOnly
1371                 }
1372                 t.Elem = p.chanElem()
1373                 return t
1374
1375         case _Map:
1376                 // _Map '[' ntype ']' ntype
1377                 p.next()
1378                 p.want(_Lbrack)
1379                 t := new(MapType)
1380                 t.pos = pos
1381                 t.Key = p.type_()
1382                 p.want(_Rbrack)
1383                 t.Value = p.type_()
1384                 return t
1385
1386         case _Struct:
1387                 return p.structType()
1388
1389         case _Interface:
1390                 return p.interfaceType()
1391
1392         case _Name:
1393                 return p.qualifiedName(nil)
1394
1395         case _Lparen:
1396                 p.next()
1397                 t := p.type_()
1398                 p.want(_Rparen)
1399                 return t
1400         }
1401
1402         return nil
1403 }
1404
1405 func (p *parser) typeInstance(typ Expr) Expr {
1406         if trace {
1407                 defer p.trace("typeInstance")()
1408         }
1409
1410         pos := p.pos()
1411         p.want(_Lbrack)
1412         x := new(IndexExpr)
1413         x.pos = pos
1414         x.X = typ
1415         if p.tok == _Rbrack {
1416                 p.syntaxError("expected type argument list")
1417                 x.Index = p.badExpr()
1418         } else {
1419                 x.Index, _ = p.typeList(true)
1420         }
1421         p.want(_Rbrack)
1422         return x
1423 }
1424
1425 // If context != "", type parameters are not permitted.
1426 func (p *parser) funcType(context string) ([]*Field, *FuncType) {
1427         if trace {
1428                 defer p.trace("funcType")()
1429         }
1430
1431         typ := new(FuncType)
1432         typ.pos = p.pos()
1433
1434         var tparamList []*Field
1435         if p.got(_Lbrack) {
1436                 if context != "" {
1437                         // accept but complain
1438                         p.syntaxErrorAt(typ.pos, context+" must have no type parameters")
1439                 }
1440                 if p.tok == _Rbrack {
1441                         p.syntaxError("empty type parameter list")
1442                         p.next()
1443                 } else {
1444                         tparamList = p.paramList(nil, nil, _Rbrack, true)
1445                 }
1446         }
1447
1448         p.want(_Lparen)
1449         typ.ParamList = p.paramList(nil, nil, _Rparen, false)
1450         typ.ResultList = p.funcResult()
1451
1452         return tparamList, typ
1453 }
1454
1455 // "[" has already been consumed, and pos is its position.
1456 // If len != nil it is the already consumed array length.
1457 func (p *parser) arrayType(pos Pos, len Expr) Expr {
1458         if trace {
1459                 defer p.trace("arrayType")()
1460         }
1461
1462         if len == nil && !p.got(_DotDotDot) {
1463                 p.xnest++
1464                 len = p.expr()
1465                 p.xnest--
1466         }
1467         if p.tok == _Comma {
1468                 // Trailing commas are accepted in type parameter
1469                 // lists but not in array type declarations.
1470                 // Accept for better error handling but complain.
1471                 p.syntaxError("unexpected comma; expected ]")
1472                 p.next()
1473         }
1474         p.want(_Rbrack)
1475         t := new(ArrayType)
1476         t.pos = pos
1477         t.Len = len
1478         t.Elem = p.type_()
1479         return t
1480 }
1481
1482 // "[" and "]" have already been consumed, and pos is the position of "[".
1483 func (p *parser) sliceType(pos Pos) Expr {
1484         t := new(SliceType)
1485         t.pos = pos
1486         t.Elem = p.type_()
1487         return t
1488 }
1489
1490 func (p *parser) chanElem() Expr {
1491         if trace {
1492                 defer p.trace("chanElem")()
1493         }
1494
1495         typ := p.typeOrNil()
1496         if typ == nil {
1497                 typ = p.badExpr()
1498                 p.syntaxError("missing channel element type")
1499                 // assume element type is simply absent - don't advance
1500         }
1501
1502         return typ
1503 }
1504
1505 // StructType = "struct" "{" { FieldDecl ";" } "}" .
1506 func (p *parser) structType() *StructType {
1507         if trace {
1508                 defer p.trace("structType")()
1509         }
1510
1511         typ := new(StructType)
1512         typ.pos = p.pos()
1513
1514         p.want(_Struct)
1515         p.want(_Lbrace)
1516         p.list("struct type", _Semi, _Rbrace, func() bool {
1517                 p.fieldDecl(typ)
1518                 return false
1519         })
1520
1521         return typ
1522 }
1523
1524 // InterfaceType = "interface" "{" { ( MethodDecl | EmbeddedElem ) ";" } "}" .
1525 func (p *parser) interfaceType() *InterfaceType {
1526         if trace {
1527                 defer p.trace("interfaceType")()
1528         }
1529
1530         typ := new(InterfaceType)
1531         typ.pos = p.pos()
1532
1533         p.want(_Interface)
1534         p.want(_Lbrace)
1535         p.list("interface type", _Semi, _Rbrace, func() bool {
1536                 var f *Field
1537                 if p.tok == _Name {
1538                         f = p.methodDecl()
1539                 }
1540                 if f == nil || f.Name == nil {
1541                         f = p.embeddedElem(f)
1542                 }
1543                 typ.MethodList = append(typ.MethodList, f)
1544                 return false
1545         })
1546
1547         return typ
1548 }
1549
1550 // Result = Parameters | Type .
1551 func (p *parser) funcResult() []*Field {
1552         if trace {
1553                 defer p.trace("funcResult")()
1554         }
1555
1556         if p.got(_Lparen) {
1557                 return p.paramList(nil, nil, _Rparen, false)
1558         }
1559
1560         pos := p.pos()
1561         if typ := p.typeOrNil(); typ != nil {
1562                 f := new(Field)
1563                 f.pos = pos
1564                 f.Type = typ
1565                 return []*Field{f}
1566         }
1567
1568         return nil
1569 }
1570
1571 func (p *parser) addField(styp *StructType, pos Pos, name *Name, typ Expr, tag *BasicLit) {
1572         if tag != nil {
1573                 for i := len(styp.FieldList) - len(styp.TagList); i > 0; i-- {
1574                         styp.TagList = append(styp.TagList, nil)
1575                 }
1576                 styp.TagList = append(styp.TagList, tag)
1577         }
1578
1579         f := new(Field)
1580         f.pos = pos
1581         f.Name = name
1582         f.Type = typ
1583         styp.FieldList = append(styp.FieldList, f)
1584
1585         if debug && tag != nil && len(styp.FieldList) != len(styp.TagList) {
1586                 panic("inconsistent struct field list")
1587         }
1588 }
1589
1590 // FieldDecl      = (IdentifierList Type | AnonymousField) [ Tag ] .
1591 // AnonymousField = [ "*" ] TypeName .
1592 // Tag            = string_lit .
1593 func (p *parser) fieldDecl(styp *StructType) {
1594         if trace {
1595                 defer p.trace("fieldDecl")()
1596         }
1597
1598         pos := p.pos()
1599         switch p.tok {
1600         case _Name:
1601                 name := p.name()
1602                 if p.tok == _Dot || p.tok == _Literal || p.tok == _Semi || p.tok == _Rbrace {
1603                         // embedded type
1604                         typ := p.qualifiedName(name)
1605                         tag := p.oliteral()
1606                         p.addField(styp, pos, nil, typ, tag)
1607                         break
1608                 }
1609
1610                 // name1, name2, ... Type [ tag ]
1611                 names := p.nameList(name)
1612                 var typ Expr
1613
1614                 // Careful dance: We don't know if we have an embedded instantiated
1615                 // type T[P1, P2, ...] or a field T of array/slice type [P]E or []E.
1616                 if len(names) == 1 && p.tok == _Lbrack {
1617                         typ = p.arrayOrTArgs()
1618                         if typ, ok := typ.(*IndexExpr); ok {
1619                                 // embedded type T[P1, P2, ...]
1620                                 typ.X = name // name == names[0]
1621                                 tag := p.oliteral()
1622                                 p.addField(styp, pos, nil, typ, tag)
1623                                 break
1624                         }
1625                 } else {
1626                         // T P
1627                         typ = p.type_()
1628                 }
1629
1630                 tag := p.oliteral()
1631
1632                 for _, name := range names {
1633                         p.addField(styp, name.Pos(), name, typ, tag)
1634                 }
1635
1636         case _Star:
1637                 p.next()
1638                 var typ Expr
1639                 if p.tok == _Lparen {
1640                         // *(T)
1641                         p.syntaxError("cannot parenthesize embedded type")
1642                         p.next()
1643                         typ = p.qualifiedName(nil)
1644                         p.got(_Rparen) // no need to complain if missing
1645                 } else {
1646                         // *T
1647                         typ = p.qualifiedName(nil)
1648                 }
1649                 tag := p.oliteral()
1650                 p.addField(styp, pos, nil, newIndirect(pos, typ), tag)
1651
1652         case _Lparen:
1653                 p.syntaxError("cannot parenthesize embedded type")
1654                 p.next()
1655                 var typ Expr
1656                 if p.tok == _Star {
1657                         // (*T)
1658                         pos := p.pos()
1659                         p.next()
1660                         typ = newIndirect(pos, p.qualifiedName(nil))
1661                 } else {
1662                         // (T)
1663                         typ = p.qualifiedName(nil)
1664                 }
1665                 p.got(_Rparen) // no need to complain if missing
1666                 tag := p.oliteral()
1667                 p.addField(styp, pos, nil, typ, tag)
1668
1669         default:
1670                 p.syntaxError("expected field name or embedded type")
1671                 p.advance(_Semi, _Rbrace)
1672         }
1673 }
1674
1675 func (p *parser) arrayOrTArgs() Expr {
1676         if trace {
1677                 defer p.trace("arrayOrTArgs")()
1678         }
1679
1680         pos := p.pos()
1681         p.want(_Lbrack)
1682         if p.got(_Rbrack) {
1683                 return p.sliceType(pos)
1684         }
1685
1686         // x [n]E or x[n,], x[n1, n2], ...
1687         n, comma := p.typeList(false)
1688         p.want(_Rbrack)
1689         if !comma {
1690                 if elem := p.typeOrNil(); elem != nil {
1691                         // x [n]E
1692                         t := new(ArrayType)
1693                         t.pos = pos
1694                         t.Len = n
1695                         t.Elem = elem
1696                         return t
1697                 }
1698         }
1699
1700         // x[n,], x[n1, n2], ...
1701         t := new(IndexExpr)
1702         t.pos = pos
1703         // t.X will be filled in by caller
1704         t.Index = n
1705         return t
1706 }
1707
1708 func (p *parser) oliteral() *BasicLit {
1709         if p.tok == _Literal {
1710                 b := new(BasicLit)
1711                 b.pos = p.pos()
1712                 b.Value = p.lit
1713                 b.Kind = p.kind
1714                 b.Bad = p.bad
1715                 p.next()
1716                 return b
1717         }
1718         return nil
1719 }
1720
1721 // MethodSpec        = MethodName Signature | InterfaceTypeName .
1722 // MethodName        = identifier .
1723 // InterfaceTypeName = TypeName .
1724 func (p *parser) methodDecl() *Field {
1725         if trace {
1726                 defer p.trace("methodDecl")()
1727         }
1728
1729         f := new(Field)
1730         f.pos = p.pos()
1731         name := p.name()
1732
1733         const context = "interface method"
1734
1735         switch p.tok {
1736         case _Lparen:
1737                 // method
1738                 f.Name = name
1739                 _, f.Type = p.funcType(context)
1740
1741         case _Lbrack:
1742                 // Careful dance: We don't know if we have a generic method m[T C](x T)
1743                 // or an embedded instantiated type T[P1, P2] (we accept generic methods
1744                 // for generality and robustness of parsing but complain with an error).
1745                 pos := p.pos()
1746                 p.next()
1747
1748                 // Empty type parameter or argument lists are not permitted.
1749                 // Treat as if [] were absent.
1750                 if p.tok == _Rbrack {
1751                         // name[]
1752                         pos := p.pos()
1753                         p.next()
1754                         if p.tok == _Lparen {
1755                                 // name[](
1756                                 p.errorAt(pos, "empty type parameter list")
1757                                 f.Name = name
1758                                 _, f.Type = p.funcType(context)
1759                         } else {
1760                                 p.errorAt(pos, "empty type argument list")
1761                                 f.Type = name
1762                         }
1763                         break
1764                 }
1765
1766                 // A type argument list looks like a parameter list with only
1767                 // types. Parse a parameter list and decide afterwards.
1768                 list := p.paramList(nil, nil, _Rbrack, false)
1769                 if len(list) == 0 {
1770                         // The type parameter list is not [] but we got nothing
1771                         // due to other errors (reported by paramList). Treat
1772                         // as if [] were absent.
1773                         if p.tok == _Lparen {
1774                                 f.Name = name
1775                                 _, f.Type = p.funcType(context)
1776                         } else {
1777                                 f.Type = name
1778                         }
1779                         break
1780                 }
1781
1782                 // len(list) > 0
1783                 if list[0].Name != nil {
1784                         // generic method
1785                         f.Name = name
1786                         _, f.Type = p.funcType(context)
1787                         p.errorAt(pos, "interface method must have no type parameters")
1788                         break
1789                 }
1790
1791                 // embedded instantiated type
1792                 t := new(IndexExpr)
1793                 t.pos = pos
1794                 t.X = name
1795                 if len(list) == 1 {
1796                         t.Index = list[0].Type
1797                 } else {
1798                         // len(list) > 1
1799                         l := new(ListExpr)
1800                         l.pos = list[0].Pos()
1801                         l.ElemList = make([]Expr, len(list))
1802                         for i := range list {
1803                                 l.ElemList[i] = list[i].Type
1804                         }
1805                         t.Index = l
1806                 }
1807                 f.Type = t
1808
1809         default:
1810                 // embedded type
1811                 f.Type = p.qualifiedName(name)
1812         }
1813
1814         return f
1815 }
1816
1817 // EmbeddedElem = MethodSpec | EmbeddedTerm { "|" EmbeddedTerm } .
1818 func (p *parser) embeddedElem(f *Field) *Field {
1819         if trace {
1820                 defer p.trace("embeddedElem")()
1821         }
1822
1823         if f == nil {
1824                 f = new(Field)
1825                 f.pos = p.pos()
1826                 f.Type = p.embeddedTerm()
1827         }
1828
1829         for p.tok == _Operator && p.op == Or {
1830                 t := new(Operation)
1831                 t.pos = p.pos()
1832                 t.Op = Or
1833                 p.next()
1834                 t.X = f.Type
1835                 t.Y = p.embeddedTerm()
1836                 f.Type = t
1837         }
1838
1839         return f
1840 }
1841
1842 // EmbeddedTerm = [ "~" ] Type .
1843 func (p *parser) embeddedTerm() Expr {
1844         if trace {
1845                 defer p.trace("embeddedTerm")()
1846         }
1847
1848         if p.tok == _Operator && p.op == Tilde {
1849                 t := new(Operation)
1850                 t.pos = p.pos()
1851                 t.Op = Tilde
1852                 p.next()
1853                 t.X = p.type_()
1854                 return t
1855         }
1856
1857         t := p.typeOrNil()
1858         if t == nil {
1859                 t = p.badExpr()
1860                 p.syntaxError("expected ~ term or type")
1861                 p.advance(_Operator, _Semi, _Rparen, _Rbrack, _Rbrace)
1862         }
1863
1864         return t
1865 }
1866
1867 // ParameterDecl = [ IdentifierList ] [ "..." ] Type .
1868 func (p *parser) paramDeclOrNil(name *Name, follow token) *Field {
1869         if trace {
1870                 defer p.trace("paramDeclOrNil")()
1871         }
1872
1873         // type set notation is ok in type parameter lists
1874         typeSetsOk := follow == _Rbrack
1875
1876         pos := p.pos()
1877         if name != nil {
1878                 pos = name.pos
1879         } else if typeSetsOk && p.tok == _Operator && p.op == Tilde {
1880                 // "~" ...
1881                 return p.embeddedElem(nil)
1882         }
1883
1884         f := new(Field)
1885         f.pos = pos
1886
1887         if p.tok == _Name || name != nil {
1888                 // name
1889                 if name == nil {
1890                         name = p.name()
1891                 }
1892
1893                 if p.tok == _Lbrack {
1894                         // name "[" ...
1895                         f.Type = p.arrayOrTArgs()
1896                         if typ, ok := f.Type.(*IndexExpr); ok {
1897                                 // name "[" ... "]"
1898                                 typ.X = name
1899                         } else {
1900                                 // name "[" n "]" E
1901                                 f.Name = name
1902                         }
1903                         if typeSetsOk && p.tok == _Operator && p.op == Or {
1904                                 // name "[" ... "]" "|" ...
1905                                 // name "[" n "]" E "|" ...
1906                                 f = p.embeddedElem(f)
1907                         }
1908                         return f
1909                 }
1910
1911                 if p.tok == _Dot {
1912                         // name "." ...
1913                         f.Type = p.qualifiedName(name)
1914                         if typeSetsOk && p.tok == _Operator && p.op == Or {
1915                                 // name "." name "|" ...
1916                                 f = p.embeddedElem(f)
1917                         }
1918                         return f
1919                 }
1920
1921                 if typeSetsOk && p.tok == _Operator && p.op == Or {
1922                         // name "|" ...
1923                         f.Type = name
1924                         return p.embeddedElem(f)
1925                 }
1926
1927                 f.Name = name
1928         }
1929
1930         if p.tok == _DotDotDot {
1931                 // [name] "..." ...
1932                 t := new(DotsType)
1933                 t.pos = p.pos()
1934                 p.next()
1935                 t.Elem = p.typeOrNil()
1936                 if t.Elem == nil {
1937                         t.Elem = p.badExpr()
1938                         p.syntaxError("... is missing type")
1939                 }
1940                 f.Type = t
1941                 return f
1942         }
1943
1944         if typeSetsOk && p.tok == _Operator && p.op == Tilde {
1945                 // [name] "~" ...
1946                 f.Type = p.embeddedElem(nil).Type
1947                 return f
1948         }
1949
1950         f.Type = p.typeOrNil()
1951         if typeSetsOk && p.tok == _Operator && p.op == Or && f.Type != nil {
1952                 // [name] type "|"
1953                 f = p.embeddedElem(f)
1954         }
1955         if f.Name != nil || f.Type != nil {
1956                 return f
1957         }
1958
1959         p.syntaxError("expected " + tokstring(follow))
1960         p.advance(_Comma, follow)
1961         return nil
1962 }
1963
1964 // Parameters    = "(" [ ParameterList [ "," ] ] ")" .
1965 // ParameterList = ParameterDecl { "," ParameterDecl } .
1966 // "(" or "[" has already been consumed.
1967 // If name != nil, it is the first name after "(" or "[".
1968 // If typ != nil, name must be != nil, and (name, typ) is the first field in the list.
1969 // In the result list, either all fields have a name, or no field has a name.
1970 func (p *parser) paramList(name *Name, typ Expr, close token, requireNames bool) (list []*Field) {
1971         if trace {
1972                 defer p.trace("paramList")()
1973         }
1974
1975         // p.list won't invoke its function argument if we're at the end of the
1976         // parameter list. If we have a complete field, handle this case here.
1977         if name != nil && typ != nil && p.tok == close {
1978                 p.next()
1979                 par := new(Field)
1980                 par.pos = name.pos
1981                 par.Name = name
1982                 par.Type = typ
1983                 return []*Field{par}
1984         }
1985
1986         var named int // number of parameters that have an explicit name and type
1987         var typed int // number of parameters that have an explicit type
1988         end := p.list("parameter list", _Comma, close, func() bool {
1989                 var par *Field
1990                 if typ != nil {
1991                         if debug && name == nil {
1992                                 panic("initial type provided without name")
1993                         }
1994                         par = new(Field)
1995                         par.pos = name.pos
1996                         par.Name = name
1997                         par.Type = typ
1998                 } else {
1999                         par = p.paramDeclOrNil(name, close)
2000                 }
2001                 name = nil // 1st name was consumed if present
2002                 typ = nil  // 1st type was consumed if present
2003                 if par != nil {
2004                         if debug && par.Name == nil && par.Type == nil {
2005                                 panic("parameter without name or type")
2006                         }
2007                         if par.Name != nil && par.Type != nil {
2008                                 named++
2009                         }
2010                         if par.Type != nil {
2011                                 typed++
2012                         }
2013                         list = append(list, par)
2014                 }
2015                 return false
2016         })
2017
2018         if len(list) == 0 {
2019                 return
2020         }
2021
2022         // distribute parameter types (len(list) > 0)
2023         if named == 0 && !requireNames {
2024                 // all unnamed => found names are named types
2025                 for _, par := range list {
2026                         if typ := par.Name; typ != nil {
2027                                 par.Type = typ
2028                                 par.Name = nil
2029                         }
2030                 }
2031         } else if named != len(list) {
2032                 // some named => all must have names and types
2033                 var pos Pos  // left-most error position (or unknown)
2034                 var typ Expr // current type (from right to left)
2035                 for i := len(list) - 1; i >= 0; i-- {
2036                         par := list[i]
2037                         if par.Type != nil {
2038                                 typ = par.Type
2039                                 if par.Name == nil {
2040                                         pos = StartPos(typ)
2041                                         par.Name = NewName(pos, "_")
2042                                 }
2043                         } else if typ != nil {
2044                                 par.Type = typ
2045                         } else {
2046                                 // par.Type == nil && typ == nil => we only have a par.Name
2047                                 pos = par.Name.Pos()
2048                                 t := p.badExpr()
2049                                 t.pos = pos // correct position
2050                                 par.Type = t
2051                         }
2052                 }
2053                 if pos.IsKnown() {
2054                         var msg string
2055                         if requireNames {
2056                                 if named == typed {
2057                                         pos = end // position error at closing ]
2058                                         msg = "missing type constraint"
2059                                 } else {
2060                                         msg = "type parameters must be named"
2061                                 }
2062                         } else {
2063                                 msg = "mixed named and unnamed parameters"
2064                         }
2065                         p.syntaxErrorAt(pos, msg)
2066                 }
2067         }
2068
2069         return
2070 }
2071
2072 func (p *parser) badExpr() *BadExpr {
2073         b := new(BadExpr)
2074         b.pos = p.pos()
2075         return b
2076 }
2077
2078 // ----------------------------------------------------------------------------
2079 // Statements
2080
2081 // SimpleStmt = EmptyStmt | ExpressionStmt | SendStmt | IncDecStmt | Assignment | ShortVarDecl .
2082 func (p *parser) simpleStmt(lhs Expr, keyword token) SimpleStmt {
2083         if trace {
2084                 defer p.trace("simpleStmt")()
2085         }
2086
2087         if keyword == _For && p.tok == _Range {
2088                 // _Range expr
2089                 if debug && lhs != nil {
2090                         panic("invalid call of simpleStmt")
2091                 }
2092                 return p.newRangeClause(nil, false)
2093         }
2094
2095         if lhs == nil {
2096                 lhs = p.exprList()
2097         }
2098
2099         if _, ok := lhs.(*ListExpr); !ok && p.tok != _Assign && p.tok != _Define {
2100                 // expr
2101                 pos := p.pos()
2102                 switch p.tok {
2103                 case _AssignOp:
2104                         // lhs op= rhs
2105                         op := p.op
2106                         p.next()
2107                         return p.newAssignStmt(pos, op, lhs, p.expr())
2108
2109                 case _IncOp:
2110                         // lhs++ or lhs--
2111                         op := p.op
2112                         p.next()
2113                         return p.newAssignStmt(pos, op, lhs, nil)
2114
2115                 case _Arrow:
2116                         // lhs <- rhs
2117                         s := new(SendStmt)
2118                         s.pos = pos
2119                         p.next()
2120                         s.Chan = lhs
2121                         s.Value = p.expr()
2122                         return s
2123
2124                 default:
2125                         // expr
2126                         s := new(ExprStmt)
2127                         s.pos = lhs.Pos()
2128                         s.X = lhs
2129                         return s
2130                 }
2131         }
2132
2133         // expr_list
2134         switch p.tok {
2135         case _Assign, _Define:
2136                 pos := p.pos()
2137                 var op Operator
2138                 if p.tok == _Define {
2139                         op = Def
2140                 }
2141                 p.next()
2142
2143                 if keyword == _For && p.tok == _Range {
2144                         // expr_list op= _Range expr
2145                         return p.newRangeClause(lhs, op == Def)
2146                 }
2147
2148                 // expr_list op= expr_list
2149                 rhs := p.exprList()
2150
2151                 if x, ok := rhs.(*TypeSwitchGuard); ok && keyword == _Switch && op == Def {
2152                         if lhs, ok := lhs.(*Name); ok {
2153                                 // switch … lhs := rhs.(type)
2154                                 x.Lhs = lhs
2155                                 s := new(ExprStmt)
2156                                 s.pos = x.Pos()
2157                                 s.X = x
2158                                 return s
2159                         }
2160                 }
2161
2162                 return p.newAssignStmt(pos, op, lhs, rhs)
2163
2164         default:
2165                 p.syntaxError("expected := or = or comma")
2166                 p.advance(_Semi, _Rbrace)
2167                 // make the best of what we have
2168                 if x, ok := lhs.(*ListExpr); ok {
2169                         lhs = x.ElemList[0]
2170                 }
2171                 s := new(ExprStmt)
2172                 s.pos = lhs.Pos()
2173                 s.X = lhs
2174                 return s
2175         }
2176 }
2177
2178 func (p *parser) newRangeClause(lhs Expr, def bool) *RangeClause {
2179         r := new(RangeClause)
2180         r.pos = p.pos()
2181         p.next() // consume _Range
2182         r.Lhs = lhs
2183         r.Def = def
2184         r.X = p.expr()
2185         return r
2186 }
2187
2188 func (p *parser) newAssignStmt(pos Pos, op Operator, lhs, rhs Expr) *AssignStmt {
2189         a := new(AssignStmt)
2190         a.pos = pos
2191         a.Op = op
2192         a.Lhs = lhs
2193         a.Rhs = rhs
2194         return a
2195 }
2196
2197 func (p *parser) labeledStmtOrNil(label *Name) Stmt {
2198         if trace {
2199                 defer p.trace("labeledStmt")()
2200         }
2201
2202         s := new(LabeledStmt)
2203         s.pos = p.pos()
2204         s.Label = label
2205
2206         p.want(_Colon)
2207
2208         if p.tok == _Rbrace {
2209                 // We expect a statement (incl. an empty statement), which must be
2210                 // terminated by a semicolon. Because semicolons may be omitted before
2211                 // an _Rbrace, seeing an _Rbrace implies an empty statement.
2212                 e := new(EmptyStmt)
2213                 e.pos = p.pos()
2214                 s.Stmt = e
2215                 return s
2216         }
2217
2218         s.Stmt = p.stmtOrNil()
2219         if s.Stmt != nil {
2220                 return s
2221         }
2222
2223         // report error at line of ':' token
2224         p.syntaxErrorAt(s.pos, "missing statement after label")
2225         // we are already at the end of the labeled statement - no need to advance
2226         return nil // avoids follow-on errors (see e.g., fixedbugs/bug274.go)
2227 }
2228
2229 // context must be a non-empty string unless we know that p.tok == _Lbrace.
2230 func (p *parser) blockStmt(context string) *BlockStmt {
2231         if trace {
2232                 defer p.trace("blockStmt")()
2233         }
2234
2235         s := new(BlockStmt)
2236         s.pos = p.pos()
2237
2238         // people coming from C may forget that braces are mandatory in Go
2239         if !p.got(_Lbrace) {
2240                 p.syntaxError("expected { after " + context)
2241                 p.advance(_Name, _Rbrace)
2242                 s.Rbrace = p.pos() // in case we found "}"
2243                 if p.got(_Rbrace) {
2244                         return s
2245                 }
2246         }
2247
2248         s.List = p.stmtList()
2249         s.Rbrace = p.pos()
2250         p.want(_Rbrace)
2251
2252         return s
2253 }
2254
2255 func (p *parser) declStmt(f func(*Group) Decl) *DeclStmt {
2256         if trace {
2257                 defer p.trace("declStmt")()
2258         }
2259
2260         s := new(DeclStmt)
2261         s.pos = p.pos()
2262
2263         p.next() // _Const, _Type, or _Var
2264         s.DeclList = p.appendGroup(nil, f)
2265
2266         return s
2267 }
2268
2269 func (p *parser) forStmt() Stmt {
2270         if trace {
2271                 defer p.trace("forStmt")()
2272         }
2273
2274         s := new(ForStmt)
2275         s.pos = p.pos()
2276
2277         s.Init, s.Cond, s.Post = p.header(_For)
2278         s.Body = p.blockStmt("for clause")
2279
2280         return s
2281 }
2282
2283 func (p *parser) header(keyword token) (init SimpleStmt, cond Expr, post SimpleStmt) {
2284         p.want(keyword)
2285
2286         if p.tok == _Lbrace {
2287                 if keyword == _If {
2288                         p.syntaxError("missing condition in if statement")
2289                         cond = p.badExpr()
2290                 }
2291                 return
2292         }
2293         // p.tok != _Lbrace
2294
2295         outer := p.xnest
2296         p.xnest = -1
2297
2298         if p.tok != _Semi {
2299                 // accept potential varDecl but complain
2300                 if p.got(_Var) {
2301                         p.syntaxError(fmt.Sprintf("var declaration not allowed in %s initializer", tokstring(keyword)))
2302                 }
2303                 init = p.simpleStmt(nil, keyword)
2304                 // If we have a range clause, we are done (can only happen for keyword == _For).
2305                 if _, ok := init.(*RangeClause); ok {
2306                         p.xnest = outer
2307                         return
2308                 }
2309         }
2310
2311         var condStmt SimpleStmt
2312         var semi struct {
2313                 pos Pos
2314                 lit string // valid if pos.IsKnown()
2315         }
2316         if p.tok != _Lbrace {
2317                 if p.tok == _Semi {
2318                         semi.pos = p.pos()
2319                         semi.lit = p.lit
2320                         p.next()
2321                 } else {
2322                         // asking for a '{' rather than a ';' here leads to a better error message
2323                         p.want(_Lbrace)
2324                         if p.tok != _Lbrace {
2325                                 p.advance(_Lbrace, _Rbrace) // for better synchronization (e.g., issue #22581)
2326                         }
2327                 }
2328                 if keyword == _For {
2329                         if p.tok != _Semi {
2330                                 if p.tok == _Lbrace {
2331                                         p.syntaxError("expected for loop condition")
2332                                         goto done
2333                                 }
2334                                 condStmt = p.simpleStmt(nil, 0 /* range not permitted */)
2335                         }
2336                         p.want(_Semi)
2337                         if p.tok != _Lbrace {
2338                                 post = p.simpleStmt(nil, 0 /* range not permitted */)
2339                                 if a, _ := post.(*AssignStmt); a != nil && a.Op == Def {
2340                                         p.syntaxErrorAt(a.Pos(), "cannot declare in post statement of for loop")
2341                                 }
2342                         }
2343                 } else if p.tok != _Lbrace {
2344                         condStmt = p.simpleStmt(nil, keyword)
2345                 }
2346         } else {
2347                 condStmt = init
2348                 init = nil
2349         }
2350
2351 done:
2352         // unpack condStmt
2353         switch s := condStmt.(type) {
2354         case nil:
2355                 if keyword == _If && semi.pos.IsKnown() {
2356                         if semi.lit != "semicolon" {
2357                                 p.syntaxErrorAt(semi.pos, fmt.Sprintf("unexpected %s, expected { after if clause", semi.lit))
2358                         } else {
2359                                 p.syntaxErrorAt(semi.pos, "missing condition in if statement")
2360                         }
2361                         b := new(BadExpr)
2362                         b.pos = semi.pos
2363                         cond = b
2364                 }
2365         case *ExprStmt:
2366                 cond = s.X
2367         default:
2368                 // A common syntax error is to write '=' instead of '==',
2369                 // which turns an expression into an assignment. Provide
2370                 // a more explicit error message in that case to prevent
2371                 // further confusion.
2372                 var str string
2373                 if as, ok := s.(*AssignStmt); ok && as.Op == 0 {
2374                         // Emphasize complex Lhs and Rhs of assignment with parentheses to highlight '='.
2375                         str = "assignment " + emphasize(as.Lhs) + " = " + emphasize(as.Rhs)
2376                 } else {
2377                         str = String(s)
2378                 }
2379                 p.syntaxErrorAt(s.Pos(), fmt.Sprintf("cannot use %s as value", str))
2380         }
2381
2382         p.xnest = outer
2383         return
2384 }
2385
2386 // emphasize returns a string representation of x, with (top-level)
2387 // binary expressions emphasized by enclosing them in parentheses.
2388 func emphasize(x Expr) string {
2389         s := String(x)
2390         if op, _ := x.(*Operation); op != nil && op.Y != nil {
2391                 // binary expression
2392                 return "(" + s + ")"
2393         }
2394         return s
2395 }
2396
2397 func (p *parser) ifStmt() *IfStmt {
2398         if trace {
2399                 defer p.trace("ifStmt")()
2400         }
2401
2402         s := new(IfStmt)
2403         s.pos = p.pos()
2404
2405         s.Init, s.Cond, _ = p.header(_If)
2406         s.Then = p.blockStmt("if clause")
2407
2408         if p.got(_Else) {
2409                 switch p.tok {
2410                 case _If:
2411                         s.Else = p.ifStmt()
2412                 case _Lbrace:
2413                         s.Else = p.blockStmt("")
2414                 default:
2415                         p.syntaxError("else must be followed by if or statement block")
2416                         p.advance(_Name, _Rbrace)
2417                 }
2418         }
2419
2420         return s
2421 }
2422
2423 func (p *parser) switchStmt() *SwitchStmt {
2424         if trace {
2425                 defer p.trace("switchStmt")()
2426         }
2427
2428         s := new(SwitchStmt)
2429         s.pos = p.pos()
2430
2431         s.Init, s.Tag, _ = p.header(_Switch)
2432
2433         if !p.got(_Lbrace) {
2434                 p.syntaxError("missing { after switch clause")
2435                 p.advance(_Case, _Default, _Rbrace)
2436         }
2437         for p.tok != _EOF && p.tok != _Rbrace {
2438                 s.Body = append(s.Body, p.caseClause())
2439         }
2440         s.Rbrace = p.pos()
2441         p.want(_Rbrace)
2442
2443         return s
2444 }
2445
2446 func (p *parser) selectStmt() *SelectStmt {
2447         if trace {
2448                 defer p.trace("selectStmt")()
2449         }
2450
2451         s := new(SelectStmt)
2452         s.pos = p.pos()
2453
2454         p.want(_Select)
2455         if !p.got(_Lbrace) {
2456                 p.syntaxError("missing { after select clause")
2457                 p.advance(_Case, _Default, _Rbrace)
2458         }
2459         for p.tok != _EOF && p.tok != _Rbrace {
2460                 s.Body = append(s.Body, p.commClause())
2461         }
2462         s.Rbrace = p.pos()
2463         p.want(_Rbrace)
2464
2465         return s
2466 }
2467
2468 func (p *parser) caseClause() *CaseClause {
2469         if trace {
2470                 defer p.trace("caseClause")()
2471         }
2472
2473         c := new(CaseClause)
2474         c.pos = p.pos()
2475
2476         switch p.tok {
2477         case _Case:
2478                 p.next()
2479                 c.Cases = p.exprList()
2480
2481         case _Default:
2482                 p.next()
2483
2484         default:
2485                 p.syntaxError("expected case or default or }")
2486                 p.advance(_Colon, _Case, _Default, _Rbrace)
2487         }
2488
2489         c.Colon = p.pos()
2490         p.want(_Colon)
2491         c.Body = p.stmtList()
2492
2493         return c
2494 }
2495
2496 func (p *parser) commClause() *CommClause {
2497         if trace {
2498                 defer p.trace("commClause")()
2499         }
2500
2501         c := new(CommClause)
2502         c.pos = p.pos()
2503
2504         switch p.tok {
2505         case _Case:
2506                 p.next()
2507                 c.Comm = p.simpleStmt(nil, 0)
2508
2509                 // The syntax restricts the possible simple statements here to:
2510                 //
2511                 //     lhs <- x (send statement)
2512                 //     <-x
2513                 //     lhs = <-x
2514                 //     lhs := <-x
2515                 //
2516                 // All these (and more) are recognized by simpleStmt and invalid
2517                 // syntax trees are flagged later, during type checking.
2518
2519         case _Default:
2520                 p.next()
2521
2522         default:
2523                 p.syntaxError("expected case or default or }")
2524                 p.advance(_Colon, _Case, _Default, _Rbrace)
2525         }
2526
2527         c.Colon = p.pos()
2528         p.want(_Colon)
2529         c.Body = p.stmtList()
2530
2531         return c
2532 }
2533
2534 // stmtOrNil parses a statement if one is present, or else returns nil.
2535 //
2536 //      Statement =
2537 //              Declaration | LabeledStmt | SimpleStmt |
2538 //              GoStmt | ReturnStmt | BreakStmt | ContinueStmt | GotoStmt |
2539 //              FallthroughStmt | Block | IfStmt | SwitchStmt | SelectStmt | ForStmt |
2540 //              DeferStmt .
2541 func (p *parser) stmtOrNil() Stmt {
2542         if trace {
2543                 defer p.trace("stmt " + p.tok.String())()
2544         }
2545
2546         // Most statements (assignments) start with an identifier;
2547         // look for it first before doing anything more expensive.
2548         if p.tok == _Name {
2549                 p.clearPragma()
2550                 lhs := p.exprList()
2551                 if label, ok := lhs.(*Name); ok && p.tok == _Colon {
2552                         return p.labeledStmtOrNil(label)
2553                 }
2554                 return p.simpleStmt(lhs, 0)
2555         }
2556
2557         switch p.tok {
2558         case _Var:
2559                 return p.declStmt(p.varDecl)
2560
2561         case _Const:
2562                 return p.declStmt(p.constDecl)
2563
2564         case _Type:
2565                 return p.declStmt(p.typeDecl)
2566         }
2567
2568         p.clearPragma()
2569
2570         switch p.tok {
2571         case _Lbrace:
2572                 return p.blockStmt("")
2573
2574         case _Operator, _Star:
2575                 switch p.op {
2576                 case Add, Sub, Mul, And, Xor, Not:
2577                         return p.simpleStmt(nil, 0) // unary operators
2578                 }
2579
2580         case _Literal, _Func, _Lparen, // operands
2581                 _Lbrack, _Struct, _Map, _Chan, _Interface, // composite types
2582                 _Arrow: // receive operator
2583                 return p.simpleStmt(nil, 0)
2584
2585         case _For:
2586                 return p.forStmt()
2587
2588         case _Switch:
2589                 return p.switchStmt()
2590
2591         case _Select:
2592                 return p.selectStmt()
2593
2594         case _If:
2595                 return p.ifStmt()
2596
2597         case _Fallthrough:
2598                 s := new(BranchStmt)
2599                 s.pos = p.pos()
2600                 p.next()
2601                 s.Tok = _Fallthrough
2602                 return s
2603
2604         case _Break, _Continue:
2605                 s := new(BranchStmt)
2606                 s.pos = p.pos()
2607                 s.Tok = p.tok
2608                 p.next()
2609                 if p.tok == _Name {
2610                         s.Label = p.name()
2611                 }
2612                 return s
2613
2614         case _Go, _Defer:
2615                 return p.callStmt()
2616
2617         case _Goto:
2618                 s := new(BranchStmt)
2619                 s.pos = p.pos()
2620                 s.Tok = _Goto
2621                 p.next()
2622                 s.Label = p.name()
2623                 return s
2624
2625         case _Return:
2626                 s := new(ReturnStmt)
2627                 s.pos = p.pos()
2628                 p.next()
2629                 if p.tok != _Semi && p.tok != _Rbrace {
2630                         s.Results = p.exprList()
2631                 }
2632                 return s
2633
2634         case _Semi:
2635                 s := new(EmptyStmt)
2636                 s.pos = p.pos()
2637                 return s
2638         }
2639
2640         return nil
2641 }
2642
2643 // StatementList = { Statement ";" } .
2644 func (p *parser) stmtList() (l []Stmt) {
2645         if trace {
2646                 defer p.trace("stmtList")()
2647         }
2648
2649         for p.tok != _EOF && p.tok != _Rbrace && p.tok != _Case && p.tok != _Default {
2650                 s := p.stmtOrNil()
2651                 p.clearPragma()
2652                 if s == nil {
2653                         break
2654                 }
2655                 l = append(l, s)
2656                 // ";" is optional before "}"
2657                 if !p.got(_Semi) && p.tok != _Rbrace {
2658                         p.syntaxError("at end of statement")
2659                         p.advance(_Semi, _Rbrace, _Case, _Default)
2660                         p.got(_Semi) // avoid spurious empty statement
2661                 }
2662         }
2663         return
2664 }
2665
2666 // argList parses a possibly empty, comma-separated list of arguments,
2667 // optionally followed by a comma (if not empty), and closed by ")".
2668 // The last argument may be followed by "...".
2669 //
2670 // argList = [ arg { "," arg } [ "..." ] [ "," ] ] ")" .
2671 func (p *parser) argList() (list []Expr, hasDots bool) {
2672         if trace {
2673                 defer p.trace("argList")()
2674         }
2675
2676         p.xnest++
2677         p.list("argument list", _Comma, _Rparen, func() bool {
2678                 list = append(list, p.expr())
2679                 hasDots = p.got(_DotDotDot)
2680                 return hasDots
2681         })
2682         p.xnest--
2683
2684         return
2685 }
2686
2687 // ----------------------------------------------------------------------------
2688 // Common productions
2689
2690 func (p *parser) name() *Name {
2691         // no tracing to avoid overly verbose output
2692
2693         if p.tok == _Name {
2694                 n := NewName(p.pos(), p.lit)
2695                 p.next()
2696                 return n
2697         }
2698
2699         n := NewName(p.pos(), "_")
2700         p.syntaxError("expected name")
2701         p.advance()
2702         return n
2703 }
2704
2705 // IdentifierList = identifier { "," identifier } .
2706 // The first name must be provided.
2707 func (p *parser) nameList(first *Name) []*Name {
2708         if trace {
2709                 defer p.trace("nameList")()
2710         }
2711
2712         if debug && first == nil {
2713                 panic("first name not provided")
2714         }
2715
2716         l := []*Name{first}
2717         for p.got(_Comma) {
2718                 l = append(l, p.name())
2719         }
2720
2721         return l
2722 }
2723
2724 // The first name may be provided, or nil.
2725 func (p *parser) qualifiedName(name *Name) Expr {
2726         if trace {
2727                 defer p.trace("qualifiedName")()
2728         }
2729
2730         var x Expr
2731         switch {
2732         case name != nil:
2733                 x = name
2734         case p.tok == _Name:
2735                 x = p.name()
2736         default:
2737                 x = NewName(p.pos(), "_")
2738                 p.syntaxError("expected name")
2739                 p.advance(_Dot, _Semi, _Rbrace)
2740         }
2741
2742         if p.tok == _Dot {
2743                 s := new(SelectorExpr)
2744                 s.pos = p.pos()
2745                 p.next()
2746                 s.X = x
2747                 s.Sel = p.name()
2748                 x = s
2749         }
2750
2751         if p.tok == _Lbrack {
2752                 x = p.typeInstance(x)
2753         }
2754
2755         return x
2756 }
2757
2758 // ExpressionList = Expression { "," Expression } .
2759 func (p *parser) exprList() Expr {
2760         if trace {
2761                 defer p.trace("exprList")()
2762         }
2763
2764         x := p.expr()
2765         if p.got(_Comma) {
2766                 list := []Expr{x, p.expr()}
2767                 for p.got(_Comma) {
2768                         list = append(list, p.expr())
2769                 }
2770                 t := new(ListExpr)
2771                 t.pos = x.Pos()
2772                 t.ElemList = list
2773                 x = t
2774         }
2775         return x
2776 }
2777
2778 // typeList parses a non-empty, comma-separated list of types,
2779 // optionally followed by a comma. If strict is set to false,
2780 // the first element may also be a (non-type) expression.
2781 // If there is more than one argument, the result is a *ListExpr.
2782 // The comma result indicates whether there was a (separating or
2783 // trailing) comma.
2784 //
2785 // typeList = arg { "," arg } [ "," ] .
2786 func (p *parser) typeList(strict bool) (x Expr, comma bool) {
2787         if trace {
2788                 defer p.trace("typeList")()
2789         }
2790
2791         p.xnest++
2792         if strict {
2793                 x = p.type_()
2794         } else {
2795                 x = p.expr()
2796         }
2797         if p.got(_Comma) {
2798                 comma = true
2799                 if t := p.typeOrNil(); t != nil {
2800                         list := []Expr{x, t}
2801                         for p.got(_Comma) {
2802                                 if t = p.typeOrNil(); t == nil {
2803                                         break
2804                                 }
2805                                 list = append(list, t)
2806                         }
2807                         l := new(ListExpr)
2808                         l.pos = x.Pos() // == list[0].Pos()
2809                         l.ElemList = list
2810                         x = l
2811                 }
2812         }
2813         p.xnest--
2814         return
2815 }
2816
2817 // Unparen returns e with any enclosing parentheses stripped.
2818 func Unparen(x Expr) Expr {
2819         for {
2820                 p, ok := x.(*ParenExpr)
2821                 if !ok {
2822                         break
2823                 }
2824                 x = p.X
2825         }
2826         return x
2827 }
2828
2829 // UnpackListExpr unpacks a *ListExpr into a []Expr.
2830 func UnpackListExpr(x Expr) []Expr {
2831         switch x := x.(type) {
2832         case nil:
2833                 return nil
2834         case *ListExpr:
2835                 return x.ElemList
2836         default:
2837                 return []Expr{x}
2838         }
2839 }