OSDN Git Service

Update to current Go library.
[pf3gnuchains/gcc-fork.git] / libgo / go / go / parser / parser.go
1 // Copyright 2009 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 // A parser for Go source files. Input may be provided in a variety of
6 // forms (see the various Parse* functions); the output is an abstract
7 // syntax tree (AST) representing the Go source. The parser is invoked
8 // through one of the Parse* functions.
9 //
10 package parser
11
12 import (
13         "fmt"
14         "go/ast"
15         "go/scanner"
16         "go/token"
17 )
18
19
20 // The mode parameter to the Parse* functions is a set of flags (or 0).
21 // They control the amount of source code parsed and other optional
22 // parser functionality.
23 //
24 const (
25         PackageClauseOnly uint = 1 << iota // parsing stops after package clause
26         ImportsOnly                        // parsing stops after import declarations
27         ParseComments                      // parse comments and add them to AST
28         Trace                              // print a trace of parsed productions
29         DeclarationErrors                  // report declaration errors
30 )
31
32
33 // The parser structure holds the parser's internal state.
34 type parser struct {
35         file *token.File
36         scanner.ErrorVector
37         scanner scanner.Scanner
38
39         // Tracing/debugging
40         mode   uint // parsing mode
41         trace  bool // == (mode & Trace != 0)
42         indent uint // indentation used for tracing output
43
44         // Comments
45         comments    []*ast.CommentGroup
46         leadComment *ast.CommentGroup // last lead comment
47         lineComment *ast.CommentGroup // last line comment
48
49         // Next token
50         pos token.Pos   // token position
51         tok token.Token // one token look-ahead
52         lit string      // token literal
53
54         // Non-syntactic parser control
55         exprLev int // < 0: in control clause, >= 0: in expression
56
57         // Ordinary identifer scopes
58         pkgScope   *ast.Scope        // pkgScope.Outer == nil
59         topScope   *ast.Scope        // top-most scope; may be pkgScope
60         unresolved []*ast.Ident      // unresolved identifiers
61         imports    []*ast.ImportSpec // list of imports
62
63         // Label scope
64         // (maintained by open/close LabelScope)
65         labelScope  *ast.Scope     // label scope for current function
66         targetStack [][]*ast.Ident // stack of unresolved labels
67 }
68
69
70 // scannerMode returns the scanner mode bits given the parser's mode bits.
71 func scannerMode(mode uint) uint {
72         var m uint = scanner.InsertSemis
73         if mode&ParseComments != 0 {
74                 m |= scanner.ScanComments
75         }
76         return m
77 }
78
79
80 func (p *parser) init(fset *token.FileSet, filename string, src []byte, mode uint) {
81         p.file = fset.AddFile(filename, fset.Base(), len(src))
82         p.scanner.Init(p.file, src, p, scannerMode(mode))
83
84         p.mode = mode
85         p.trace = mode&Trace != 0 // for convenience (p.trace is used frequently)
86
87         p.next()
88
89         // set up the pkgScope here (as opposed to in parseFile) because
90         // there are other parser entry points (ParseExpr, etc.)
91         p.openScope()
92         p.pkgScope = p.topScope
93
94         // for the same reason, set up a label scope
95         p.openLabelScope()
96 }
97
98
99 // ----------------------------------------------------------------------------
100 // Scoping support
101
102 func (p *parser) openScope() {
103         p.topScope = ast.NewScope(p.topScope)
104 }
105
106
107 func (p *parser) closeScope() {
108         p.topScope = p.topScope.Outer
109 }
110
111
112 func (p *parser) openLabelScope() {
113         p.labelScope = ast.NewScope(p.labelScope)
114         p.targetStack = append(p.targetStack, nil)
115 }
116
117
118 func (p *parser) closeLabelScope() {
119         // resolve labels
120         n := len(p.targetStack) - 1
121         scope := p.labelScope
122         for _, ident := range p.targetStack[n] {
123                 ident.Obj = scope.Lookup(ident.Name)
124                 if ident.Obj == nil && p.mode&DeclarationErrors != 0 {
125                         p.error(ident.Pos(), fmt.Sprintf("label %s undefined", ident.Name))
126                 }
127         }
128         // pop label scope
129         p.targetStack = p.targetStack[0:n]
130         p.labelScope = p.labelScope.Outer
131 }
132
133
134 func (p *parser) declare(decl interface{}, scope *ast.Scope, kind ast.ObjKind, idents ...*ast.Ident) {
135         for _, ident := range idents {
136                 assert(ident.Obj == nil, "identifier already declared or resolved")
137                 if ident.Name != "_" {
138                         obj := ast.NewObj(kind, ident.Name)
139                         // remember the corresponding declaration for redeclaration
140                         // errors and global variable resolution/typechecking phase
141                         obj.Decl = decl
142                         if alt := scope.Insert(obj); alt != nil && p.mode&DeclarationErrors != 0 {
143                                 prevDecl := ""
144                                 if pos := alt.Pos(); pos.IsValid() {
145                                         prevDecl = fmt.Sprintf("\n\tprevious declaration at %s", p.file.Position(pos))
146                                 }
147                                 p.error(ident.Pos(), fmt.Sprintf("%s redeclared in this block%s", ident.Name, prevDecl))
148                         }
149                         ident.Obj = obj
150                 }
151         }
152 }
153
154
155 func (p *parser) shortVarDecl(idents []*ast.Ident) {
156         // Go spec: A short variable declaration may redeclare variables
157         // provided they were originally declared in the same block with
158         // the same type, and at least one of the non-blank variables is new.
159         n := 0 // number of new variables
160         for _, ident := range idents {
161                 assert(ident.Obj == nil, "identifier already declared or resolved")
162                 if ident.Name != "_" {
163                         obj := ast.NewObj(ast.Var, ident.Name)
164                         // short var declarations cannot have redeclaration errors
165                         // and are not global => no need to remember the respective
166                         // declaration
167                         alt := p.topScope.Insert(obj)
168                         if alt == nil {
169                                 n++ // new declaration
170                                 alt = obj
171                         }
172                         ident.Obj = alt
173                 }
174         }
175         if n == 0 && p.mode&DeclarationErrors != 0 {
176                 p.error(idents[0].Pos(), "no new variables on left side of :=")
177         }
178 }
179
180
181 // The unresolved object is a sentinel to mark identifiers that have been added
182 // to the list of unresolved identifiers. The sentinel is only used for verifying
183 // internal consistency.
184 var unresolved = new(ast.Object)
185
186
187 func (p *parser) resolve(x ast.Expr) {
188         // nothing to do if x is not an identifier or the blank identifier
189         ident, _ := x.(*ast.Ident)
190         if ident == nil {
191                 return
192         }
193         assert(ident.Obj == nil, "identifier already declared or resolved")
194         if ident.Name == "_" {
195                 return
196         }
197         // try to resolve the identifier
198         for s := p.topScope; s != nil; s = s.Outer {
199                 if obj := s.Lookup(ident.Name); obj != nil {
200                         ident.Obj = obj
201                         return
202                 }
203         }
204         // all local scopes are known, so any unresolved identifier
205         // must be found either in the file scope, package scope
206         // (perhaps in another file), or universe scope --- collect
207         // them so that they can be resolved later
208         ident.Obj = unresolved
209         p.unresolved = append(p.unresolved, ident)
210 }
211
212
213 // ----------------------------------------------------------------------------
214 // Parsing support
215
216 func (p *parser) printTrace(a ...interface{}) {
217         const dots = ". . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . " +
218                 ". . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . "
219         const n = uint(len(dots))
220         pos := p.file.Position(p.pos)
221         fmt.Printf("%5d:%3d: ", pos.Line, pos.Column)
222         i := 2 * p.indent
223         for ; i > n; i -= n {
224                 fmt.Print(dots)
225         }
226         fmt.Print(dots[0:i])
227         fmt.Println(a...)
228 }
229
230
231 func trace(p *parser, msg string) *parser {
232         p.printTrace(msg, "(")
233         p.indent++
234         return p
235 }
236
237
238 // Usage pattern: defer un(trace(p, "..."));
239 func un(p *parser) {
240         p.indent--
241         p.printTrace(")")
242 }
243
244
245 // Advance to the next token.
246 func (p *parser) next0() {
247         // Because of one-token look-ahead, print the previous token
248         // when tracing as it provides a more readable output. The
249         // very first token (!p.pos.IsValid()) is not initialized
250         // (it is token.ILLEGAL), so don't print it .
251         if p.trace && p.pos.IsValid() {
252                 s := p.tok.String()
253                 switch {
254                 case p.tok.IsLiteral():
255                         p.printTrace(s, p.lit)
256                 case p.tok.IsOperator(), p.tok.IsKeyword():
257                         p.printTrace("\"" + s + "\"")
258                 default:
259                         p.printTrace(s)
260                 }
261         }
262
263         p.pos, p.tok, p.lit = p.scanner.Scan()
264 }
265
266 // Consume a comment and return it and the line on which it ends.
267 func (p *parser) consumeComment() (comment *ast.Comment, endline int) {
268         // /*-style comments may end on a different line than where they start.
269         // Scan the comment for '\n' chars and adjust endline accordingly.
270         endline = p.file.Line(p.pos)
271         if p.lit[1] == '*' {
272                 // don't use range here - no need to decode Unicode code points
273                 for i := 0; i < len(p.lit); i++ {
274                         if p.lit[i] == '\n' {
275                                 endline++
276                         }
277                 }
278         }
279
280         comment = &ast.Comment{p.pos, p.lit}
281         p.next0()
282
283         return
284 }
285
286
287 // Consume a group of adjacent comments, add it to the parser's
288 // comments list, and return it together with the line at which
289 // the last comment in the group ends. An empty line or non-comment
290 // token terminates a comment group.
291 //
292 func (p *parser) consumeCommentGroup() (comments *ast.CommentGroup, endline int) {
293         var list []*ast.Comment
294         endline = p.file.Line(p.pos)
295         for p.tok == token.COMMENT && endline+1 >= p.file.Line(p.pos) {
296                 var comment *ast.Comment
297                 comment, endline = p.consumeComment()
298                 list = append(list, comment)
299         }
300
301         // add comment group to the comments list
302         comments = &ast.CommentGroup{list}
303         p.comments = append(p.comments, comments)
304
305         return
306 }
307
308
309 // Advance to the next non-comment token. In the process, collect
310 // any comment groups encountered, and remember the last lead and
311 // and line comments.
312 //
313 // A lead comment is a comment group that starts and ends in a
314 // line without any other tokens and that is followed by a non-comment
315 // token on the line immediately after the comment group.
316 //
317 // A line comment is a comment group that follows a non-comment
318 // token on the same line, and that has no tokens after it on the line
319 // where it ends.
320 //
321 // Lead and line comments may be considered documentation that is
322 // stored in the AST.
323 //
324 func (p *parser) next() {
325         p.leadComment = nil
326         p.lineComment = nil
327         line := p.file.Line(p.pos) // current line
328         p.next0()
329
330         if p.tok == token.COMMENT {
331                 var comment *ast.CommentGroup
332                 var endline int
333
334                 if p.file.Line(p.pos) == line {
335                         // The comment is on same line as previous token; it
336                         // cannot be a lead comment but may be a line comment.
337                         comment, endline = p.consumeCommentGroup()
338                         if p.file.Line(p.pos) != endline {
339                                 // The next token is on a different line, thus
340                                 // the last comment group is a line comment.
341                                 p.lineComment = comment
342                         }
343                 }
344
345                 // consume successor comments, if any
346                 endline = -1
347                 for p.tok == token.COMMENT {
348                         comment, endline = p.consumeCommentGroup()
349                 }
350
351                 if endline+1 == p.file.Line(p.pos) {
352                         // The next token is following on the line immediately after the
353                         // comment group, thus the last comment group is a lead comment.
354                         p.leadComment = comment
355                 }
356         }
357 }
358
359
360 func (p *parser) error(pos token.Pos, msg string) {
361         p.Error(p.file.Position(pos), msg)
362 }
363
364
365 func (p *parser) errorExpected(pos token.Pos, msg string) {
366         msg = "expected " + msg
367         if pos == p.pos {
368                 // the error happened at the current position;
369                 // make the error message more specific
370                 if p.tok == token.SEMICOLON && p.lit[0] == '\n' {
371                         msg += ", found newline"
372                 } else {
373                         msg += ", found '" + p.tok.String() + "'"
374                         if p.tok.IsLiteral() {
375                                 msg += " " + p.lit
376                         }
377                 }
378         }
379         p.error(pos, msg)
380 }
381
382
383 func (p *parser) expect(tok token.Token) token.Pos {
384         pos := p.pos
385         if p.tok != tok {
386                 p.errorExpected(pos, "'"+tok.String()+"'")
387         }
388         p.next() // make progress
389         return pos
390 }
391
392
393 func (p *parser) expectSemi() {
394         if p.tok != token.RPAREN && p.tok != token.RBRACE {
395                 p.expect(token.SEMICOLON)
396         }
397 }
398
399
400 func assert(cond bool, msg string) {
401         if !cond {
402                 panic("go/parser internal error: " + msg)
403         }
404 }
405
406
407 // ----------------------------------------------------------------------------
408 // Identifiers
409
410 func (p *parser) parseIdent() *ast.Ident {
411         pos := p.pos
412         name := "_"
413         if p.tok == token.IDENT {
414                 name = p.lit
415                 p.next()
416         } else {
417                 p.expect(token.IDENT) // use expect() error handling
418         }
419         return &ast.Ident{pos, name, nil}
420 }
421
422
423 func (p *parser) parseIdentList() (list []*ast.Ident) {
424         if p.trace {
425                 defer un(trace(p, "IdentList"))
426         }
427
428         list = append(list, p.parseIdent())
429         for p.tok == token.COMMA {
430                 p.next()
431                 list = append(list, p.parseIdent())
432         }
433
434         return
435 }
436
437
438 // ----------------------------------------------------------------------------
439 // Common productions
440
441 // If lhs is set, result list elements which are identifiers are not resolved.
442 func (p *parser) parseExprList(lhs bool) (list []ast.Expr) {
443         if p.trace {
444                 defer un(trace(p, "ExpressionList"))
445         }
446
447         list = append(list, p.parseExpr(lhs))
448         for p.tok == token.COMMA {
449                 p.next()
450                 list = append(list, p.parseExpr(lhs))
451         }
452
453         return
454 }
455
456
457 func (p *parser) parseLhsList() []ast.Expr {
458         list := p.parseExprList(true)
459         switch p.tok {
460         case token.DEFINE:
461                 // lhs of a short variable declaration
462                 p.shortVarDecl(p.makeIdentList(list))
463         case token.COLON:
464                 // lhs of a label declaration or a communication clause of a select
465                 // statement (parseLhsList is not called when parsing the case clause
466                 // of a switch statement):
467                 // - labels are declared by the caller of parseLhsList
468                 // - for communication clauses, if there is a stand-alone identifier
469                 //   followed by a colon, we have a syntax error; there is no need
470                 //   to resolve the identifier in that case
471         default:
472                 // identifiers must be declared elsewhere
473                 for _, x := range list {
474                         p.resolve(x)
475                 }
476         }
477         return list
478 }
479
480
481 func (p *parser) parseRhsList() []ast.Expr {
482         return p.parseExprList(false)
483 }
484
485
486 // ----------------------------------------------------------------------------
487 // Types
488
489 func (p *parser) parseType() ast.Expr {
490         if p.trace {
491                 defer un(trace(p, "Type"))
492         }
493
494         typ := p.tryType()
495
496         if typ == nil {
497                 pos := p.pos
498                 p.errorExpected(pos, "type")
499                 p.next() // make progress
500                 return &ast.BadExpr{pos, p.pos}
501         }
502
503         return typ
504 }
505
506
507 // If the result is an identifier, it is not resolved.
508 func (p *parser) parseTypeName() ast.Expr {
509         if p.trace {
510                 defer un(trace(p, "TypeName"))
511         }
512
513         ident := p.parseIdent()
514         // don't resolve ident yet - it may be a parameter or field name
515
516         if p.tok == token.PERIOD {
517                 // ident is a package name
518                 p.next()
519                 p.resolve(ident)
520                 sel := p.parseIdent()
521                 return &ast.SelectorExpr{ident, sel}
522         }
523
524         return ident
525 }
526
527
528 func (p *parser) parseArrayType(ellipsisOk bool) ast.Expr {
529         if p.trace {
530                 defer un(trace(p, "ArrayType"))
531         }
532
533         lbrack := p.expect(token.LBRACK)
534         var len ast.Expr
535         if ellipsisOk && p.tok == token.ELLIPSIS {
536                 len = &ast.Ellipsis{p.pos, nil}
537                 p.next()
538         } else if p.tok != token.RBRACK {
539                 len = p.parseRhs()
540         }
541         p.expect(token.RBRACK)
542         elt := p.parseType()
543
544         return &ast.ArrayType{lbrack, len, elt}
545 }
546
547
548 func (p *parser) makeIdentList(list []ast.Expr) []*ast.Ident {
549         idents := make([]*ast.Ident, len(list))
550         for i, x := range list {
551                 ident, isIdent := x.(*ast.Ident)
552                 if !isIdent {
553                         pos := x.(ast.Expr).Pos()
554                         p.errorExpected(pos, "identifier")
555                         ident = &ast.Ident{pos, "_", nil}
556                 }
557                 idents[i] = ident
558         }
559         return idents
560 }
561
562
563 func (p *parser) parseFieldDecl(scope *ast.Scope) *ast.Field {
564         if p.trace {
565                 defer un(trace(p, "FieldDecl"))
566         }
567
568         doc := p.leadComment
569
570         // fields
571         list, typ := p.parseVarList(false)
572
573         // optional tag
574         var tag *ast.BasicLit
575         if p.tok == token.STRING {
576                 tag = &ast.BasicLit{p.pos, p.tok, p.lit}
577                 p.next()
578         }
579
580         // analyze case
581         var idents []*ast.Ident
582         if typ != nil {
583                 // IdentifierList Type
584                 idents = p.makeIdentList(list)
585         } else {
586                 // ["*"] TypeName (AnonymousField)
587                 typ = list[0] // we always have at least one element
588                 p.resolve(typ)
589                 if n := len(list); n > 1 || !isTypeName(deref(typ)) {
590                         pos := typ.Pos()
591                         p.errorExpected(pos, "anonymous field")
592                         typ = &ast.BadExpr{pos, list[n-1].End()}
593                 }
594         }
595
596         p.expectSemi() // call before accessing p.linecomment
597
598         field := &ast.Field{doc, idents, typ, tag, p.lineComment}
599         p.declare(field, scope, ast.Var, idents...)
600
601         return field
602 }
603
604
605 func (p *parser) parseStructType() *ast.StructType {
606         if p.trace {
607                 defer un(trace(p, "StructType"))
608         }
609
610         pos := p.expect(token.STRUCT)
611         lbrace := p.expect(token.LBRACE)
612         scope := ast.NewScope(nil) // struct scope
613         var list []*ast.Field
614         for p.tok == token.IDENT || p.tok == token.MUL || p.tok == token.LPAREN {
615                 // a field declaration cannot start with a '(' but we accept
616                 // it here for more robust parsing and better error messages
617                 // (parseFieldDecl will check and complain if necessary)
618                 list = append(list, p.parseFieldDecl(scope))
619         }
620         rbrace := p.expect(token.RBRACE)
621
622         // TODO(gri): store struct scope in AST
623         return &ast.StructType{pos, &ast.FieldList{lbrace, list, rbrace}, false}
624 }
625
626
627 func (p *parser) parsePointerType() *ast.StarExpr {
628         if p.trace {
629                 defer un(trace(p, "PointerType"))
630         }
631
632         star := p.expect(token.MUL)
633         base := p.parseType()
634
635         return &ast.StarExpr{star, base}
636 }
637
638
639 func (p *parser) tryVarType(isParam bool) ast.Expr {
640         if isParam && p.tok == token.ELLIPSIS {
641                 pos := p.pos
642                 p.next()
643                 typ := p.tryIdentOrType(isParam) // don't use parseType so we can provide better error message
644                 if typ == nil {
645                         p.error(pos, "'...' parameter is missing type")
646                         typ = &ast.BadExpr{pos, p.pos}
647                 }
648                 if p.tok != token.RPAREN {
649                         p.error(pos, "can use '...' with last parameter type only")
650                 }
651                 return &ast.Ellipsis{pos, typ}
652         }
653         return p.tryIdentOrType(false)
654 }
655
656
657 func (p *parser) parseVarType(isParam bool) ast.Expr {
658         typ := p.tryVarType(isParam)
659         if typ == nil {
660                 pos := p.pos
661                 p.errorExpected(pos, "type")
662                 p.next() // make progress
663                 typ = &ast.BadExpr{pos, p.pos}
664         }
665         return typ
666 }
667
668
669 func (p *parser) parseVarList(isParam bool) (list []ast.Expr, typ ast.Expr) {
670         if p.trace {
671                 defer un(trace(p, "VarList"))
672         }
673
674         // a list of identifiers looks like a list of type names
675         for {
676                 // parseVarType accepts any type (including parenthesized ones)
677                 // even though the syntax does not permit them here: we
678                 // accept them all for more robust parsing and complain
679                 // afterwards
680                 list = append(list, p.parseVarType(isParam))
681                 if p.tok != token.COMMA {
682                         break
683                 }
684                 p.next()
685         }
686
687         // if we had a list of identifiers, it must be followed by a type
688         typ = p.tryVarType(isParam)
689         if typ != nil {
690                 p.resolve(typ)
691         }
692
693         return
694 }
695
696
697 func (p *parser) parseParameterList(scope *ast.Scope, ellipsisOk bool) (params []*ast.Field) {
698         if p.trace {
699                 defer un(trace(p, "ParameterList"))
700         }
701
702         list, typ := p.parseVarList(ellipsisOk)
703         if typ != nil {
704                 // IdentifierList Type
705                 idents := p.makeIdentList(list)
706                 field := &ast.Field{nil, idents, typ, nil, nil}
707                 params = append(params, field)
708                 // Go spec: The scope of an identifier denoting a function
709                 // parameter or result variable is the function body.
710                 p.declare(field, scope, ast.Var, idents...)
711                 if p.tok == token.COMMA {
712                         p.next()
713                 }
714
715                 for p.tok != token.RPAREN && p.tok != token.EOF {
716                         idents := p.parseIdentList()
717                         typ := p.parseVarType(ellipsisOk)
718                         field := &ast.Field{nil, idents, typ, nil, nil}
719                         params = append(params, field)
720                         // Go spec: The scope of an identifier denoting a function
721                         // parameter or result variable is the function body.
722                         p.declare(field, scope, ast.Var, idents...)
723                         if p.tok != token.COMMA {
724                                 break
725                         }
726                         p.next()
727                 }
728
729         } else {
730                 // Type { "," Type } (anonymous parameters)
731                 params = make([]*ast.Field, len(list))
732                 for i, x := range list {
733                         p.resolve(x)
734                         params[i] = &ast.Field{Type: x}
735                 }
736         }
737
738         return
739 }
740
741
742 func (p *parser) parseParameters(scope *ast.Scope, ellipsisOk bool) *ast.FieldList {
743         if p.trace {
744                 defer un(trace(p, "Parameters"))
745         }
746
747         var params []*ast.Field
748         lparen := p.expect(token.LPAREN)
749         if p.tok != token.RPAREN {
750                 params = p.parseParameterList(scope, ellipsisOk)
751         }
752         rparen := p.expect(token.RPAREN)
753
754         return &ast.FieldList{lparen, params, rparen}
755 }
756
757
758 func (p *parser) parseResult(scope *ast.Scope) *ast.FieldList {
759         if p.trace {
760                 defer un(trace(p, "Result"))
761         }
762
763         if p.tok == token.LPAREN {
764                 return p.parseParameters(scope, false)
765         }
766
767         typ := p.tryType()
768         if typ != nil {
769                 list := make([]*ast.Field, 1)
770                 list[0] = &ast.Field{Type: typ}
771                 return &ast.FieldList{List: list}
772         }
773
774         return nil
775 }
776
777
778 func (p *parser) parseSignature(scope *ast.Scope) (params, results *ast.FieldList) {
779         if p.trace {
780                 defer un(trace(p, "Signature"))
781         }
782
783         params = p.parseParameters(scope, true)
784         results = p.parseResult(scope)
785
786         return
787 }
788
789
790 func (p *parser) parseFuncType() (*ast.FuncType, *ast.Scope) {
791         if p.trace {
792                 defer un(trace(p, "FuncType"))
793         }
794
795         pos := p.expect(token.FUNC)
796         scope := ast.NewScope(p.topScope) // function scope
797         params, results := p.parseSignature(scope)
798
799         return &ast.FuncType{pos, params, results}, scope
800 }
801
802
803 func (p *parser) parseMethodSpec(scope *ast.Scope) *ast.Field {
804         if p.trace {
805                 defer un(trace(p, "MethodSpec"))
806         }
807
808         doc := p.leadComment
809         var idents []*ast.Ident
810         var typ ast.Expr
811         x := p.parseTypeName()
812         if ident, isIdent := x.(*ast.Ident); isIdent && p.tok == token.LPAREN {
813                 // method
814                 idents = []*ast.Ident{ident}
815                 scope := ast.NewScope(nil) // method scope
816                 params, results := p.parseSignature(scope)
817                 typ = &ast.FuncType{token.NoPos, params, results}
818         } else {
819                 // embedded interface
820                 typ = x
821         }
822         p.expectSemi() // call before accessing p.linecomment
823
824         spec := &ast.Field{doc, idents, typ, nil, p.lineComment}
825         p.declare(spec, scope, ast.Fun, idents...)
826
827         return spec
828 }
829
830
831 func (p *parser) parseInterfaceType() *ast.InterfaceType {
832         if p.trace {
833                 defer un(trace(p, "InterfaceType"))
834         }
835
836         pos := p.expect(token.INTERFACE)
837         lbrace := p.expect(token.LBRACE)
838         scope := ast.NewScope(nil) // interface scope
839         var list []*ast.Field
840         for p.tok == token.IDENT {
841                 list = append(list, p.parseMethodSpec(scope))
842         }
843         rbrace := p.expect(token.RBRACE)
844
845         // TODO(gri): store interface scope in AST
846         return &ast.InterfaceType{pos, &ast.FieldList{lbrace, list, rbrace}, false}
847 }
848
849
850 func (p *parser) parseMapType() *ast.MapType {
851         if p.trace {
852                 defer un(trace(p, "MapType"))
853         }
854
855         pos := p.expect(token.MAP)
856         p.expect(token.LBRACK)
857         key := p.parseType()
858         p.expect(token.RBRACK)
859         value := p.parseType()
860
861         return &ast.MapType{pos, key, value}
862 }
863
864
865 func (p *parser) parseChanType() *ast.ChanType {
866         if p.trace {
867                 defer un(trace(p, "ChanType"))
868         }
869
870         pos := p.pos
871         dir := ast.SEND | ast.RECV
872         if p.tok == token.CHAN {
873                 p.next()
874                 if p.tok == token.ARROW {
875                         p.next()
876                         dir = ast.SEND
877                 }
878         } else {
879                 p.expect(token.ARROW)
880                 p.expect(token.CHAN)
881                 dir = ast.RECV
882         }
883         value := p.parseType()
884
885         return &ast.ChanType{pos, dir, value}
886 }
887
888
889 // If the result is an identifier, it is not resolved.
890 func (p *parser) tryIdentOrType(ellipsisOk bool) ast.Expr {
891         switch p.tok {
892         case token.IDENT:
893                 return p.parseTypeName()
894         case token.LBRACK:
895                 return p.parseArrayType(ellipsisOk)
896         case token.STRUCT:
897                 return p.parseStructType()
898         case token.MUL:
899                 return p.parsePointerType()
900         case token.FUNC:
901                 typ, _ := p.parseFuncType()
902                 return typ
903         case token.INTERFACE:
904                 return p.parseInterfaceType()
905         case token.MAP:
906                 return p.parseMapType()
907         case token.CHAN, token.ARROW:
908                 return p.parseChanType()
909         case token.LPAREN:
910                 lparen := p.pos
911                 p.next()
912                 typ := p.parseType()
913                 rparen := p.expect(token.RPAREN)
914                 return &ast.ParenExpr{lparen, typ, rparen}
915         }
916
917         // no type found
918         return nil
919 }
920
921
922 func (p *parser) tryType() ast.Expr {
923         typ := p.tryIdentOrType(false)
924         if typ != nil {
925                 p.resolve(typ)
926         }
927         return typ
928 }
929
930
931 // ----------------------------------------------------------------------------
932 // Blocks
933
934 func (p *parser) parseStmtList() (list []ast.Stmt) {
935         if p.trace {
936                 defer un(trace(p, "StatementList"))
937         }
938
939         for p.tok != token.CASE && p.tok != token.DEFAULT && p.tok != token.RBRACE && p.tok != token.EOF {
940                 list = append(list, p.parseStmt())
941         }
942
943         return
944 }
945
946
947 func (p *parser) parseBody(scope *ast.Scope) *ast.BlockStmt {
948         if p.trace {
949                 defer un(trace(p, "Body"))
950         }
951
952         lbrace := p.expect(token.LBRACE)
953         p.topScope = scope // open function scope
954         p.openLabelScope()
955         list := p.parseStmtList()
956         p.closeLabelScope()
957         p.closeScope()
958         rbrace := p.expect(token.RBRACE)
959
960         return &ast.BlockStmt{lbrace, list, rbrace}
961 }
962
963
964 func (p *parser) parseBlockStmt() *ast.BlockStmt {
965         if p.trace {
966                 defer un(trace(p, "BlockStmt"))
967         }
968
969         lbrace := p.expect(token.LBRACE)
970         p.openScope()
971         list := p.parseStmtList()
972         p.closeScope()
973         rbrace := p.expect(token.RBRACE)
974
975         return &ast.BlockStmt{lbrace, list, rbrace}
976 }
977
978
979 // ----------------------------------------------------------------------------
980 // Expressions
981
982 func (p *parser) parseFuncTypeOrLit() ast.Expr {
983         if p.trace {
984                 defer un(trace(p, "FuncTypeOrLit"))
985         }
986
987         typ, scope := p.parseFuncType()
988         if p.tok != token.LBRACE {
989                 // function type only
990                 return typ
991         }
992
993         p.exprLev++
994         body := p.parseBody(scope)
995         p.exprLev--
996
997         return &ast.FuncLit{typ, body}
998 }
999
1000
1001 // parseOperand may return an expression or a raw type (incl. array
1002 // types of the form [...]T. Callers must verify the result.
1003 // If lhs is set and the result is an identifier, it is not resolved.
1004 //
1005 func (p *parser) parseOperand(lhs bool) ast.Expr {
1006         if p.trace {
1007                 defer un(trace(p, "Operand"))
1008         }
1009
1010         switch p.tok {
1011         case token.IDENT:
1012                 x := p.parseIdent()
1013                 if !lhs {
1014                         p.resolve(x)
1015                 }
1016                 return x
1017
1018         case token.INT, token.FLOAT, token.IMAG, token.CHAR, token.STRING:
1019                 x := &ast.BasicLit{p.pos, p.tok, p.lit}
1020                 p.next()
1021                 return x
1022
1023         case token.LPAREN:
1024                 lparen := p.pos
1025                 p.next()
1026                 p.exprLev++
1027                 x := p.parseRhs()
1028                 p.exprLev--
1029                 rparen := p.expect(token.RPAREN)
1030                 return &ast.ParenExpr{lparen, x, rparen}
1031
1032         case token.FUNC:
1033                 return p.parseFuncTypeOrLit()
1034
1035         default:
1036                 if typ := p.tryIdentOrType(true); typ != nil {
1037                         // could be type for composite literal or conversion
1038                         _, isIdent := typ.(*ast.Ident)
1039                         assert(!isIdent, "type cannot be identifier")
1040                         return typ
1041                 }
1042         }
1043
1044         pos := p.pos
1045         p.errorExpected(pos, "operand")
1046         p.next() // make progress
1047         return &ast.BadExpr{pos, p.pos}
1048 }
1049
1050
1051 func (p *parser) parseSelector(x ast.Expr) ast.Expr {
1052         if p.trace {
1053                 defer un(trace(p, "Selector"))
1054         }
1055
1056         sel := p.parseIdent()
1057
1058         return &ast.SelectorExpr{x, sel}
1059 }
1060
1061
1062 func (p *parser) parseTypeAssertion(x ast.Expr) ast.Expr {
1063         if p.trace {
1064                 defer un(trace(p, "TypeAssertion"))
1065         }
1066
1067         p.expect(token.LPAREN)
1068         var typ ast.Expr
1069         if p.tok == token.TYPE {
1070                 // type switch: typ == nil
1071                 p.next()
1072         } else {
1073                 typ = p.parseType()
1074         }
1075         p.expect(token.RPAREN)
1076
1077         return &ast.TypeAssertExpr{x, typ}
1078 }
1079
1080
1081 func (p *parser) parseIndexOrSlice(x ast.Expr) ast.Expr {
1082         if p.trace {
1083                 defer un(trace(p, "IndexOrSlice"))
1084         }
1085
1086         lbrack := p.expect(token.LBRACK)
1087         p.exprLev++
1088         var low, high ast.Expr
1089         isSlice := false
1090         if p.tok != token.COLON {
1091                 low = p.parseRhs()
1092         }
1093         if p.tok == token.COLON {
1094                 isSlice = true
1095                 p.next()
1096                 if p.tok != token.RBRACK {
1097                         high = p.parseRhs()
1098                 }
1099         }
1100         p.exprLev--
1101         rbrack := p.expect(token.RBRACK)
1102
1103         if isSlice {
1104                 return &ast.SliceExpr{x, lbrack, low, high, rbrack}
1105         }
1106         return &ast.IndexExpr{x, lbrack, low, rbrack}
1107 }
1108
1109
1110 func (p *parser) parseCallOrConversion(fun ast.Expr) *ast.CallExpr {
1111         if p.trace {
1112                 defer un(trace(p, "CallOrConversion"))
1113         }
1114
1115         lparen := p.expect(token.LPAREN)
1116         p.exprLev++
1117         var list []ast.Expr
1118         var ellipsis token.Pos
1119         for p.tok != token.RPAREN && p.tok != token.EOF && !ellipsis.IsValid() {
1120                 list = append(list, p.parseRhs())
1121                 if p.tok == token.ELLIPSIS {
1122                         ellipsis = p.pos
1123                         p.next()
1124                 }
1125                 if p.tok != token.COMMA {
1126                         break
1127                 }
1128                 p.next()
1129         }
1130         p.exprLev--
1131         rparen := p.expect(token.RPAREN)
1132
1133         return &ast.CallExpr{fun, lparen, list, ellipsis, rparen}
1134 }
1135
1136
1137 func (p *parser) parseElement(keyOk bool) ast.Expr {
1138         if p.trace {
1139                 defer un(trace(p, "Element"))
1140         }
1141
1142         if p.tok == token.LBRACE {
1143                 return p.parseLiteralValue(nil)
1144         }
1145
1146         x := p.parseExpr(keyOk) // don't resolve if map key
1147         if keyOk {
1148                 if p.tok == token.COLON {
1149                         colon := p.pos
1150                         p.next()
1151                         return &ast.KeyValueExpr{x, colon, p.parseElement(false)}
1152                 }
1153                 p.resolve(x) // not a map key
1154         }
1155
1156         return x
1157 }
1158
1159
1160 func (p *parser) parseElementList() (list []ast.Expr) {
1161         if p.trace {
1162                 defer un(trace(p, "ElementList"))
1163         }
1164
1165         for p.tok != token.RBRACE && p.tok != token.EOF {
1166                 list = append(list, p.parseElement(true))
1167                 if p.tok != token.COMMA {
1168                         break
1169                 }
1170                 p.next()
1171         }
1172
1173         return
1174 }
1175
1176
1177 func (p *parser) parseLiteralValue(typ ast.Expr) ast.Expr {
1178         if p.trace {
1179                 defer un(trace(p, "LiteralValue"))
1180         }
1181
1182         lbrace := p.expect(token.LBRACE)
1183         var elts []ast.Expr
1184         p.exprLev++
1185         if p.tok != token.RBRACE {
1186                 elts = p.parseElementList()
1187         }
1188         p.exprLev--
1189         rbrace := p.expect(token.RBRACE)
1190         return &ast.CompositeLit{typ, lbrace, elts, rbrace}
1191 }
1192
1193
1194 // checkExpr checks that x is an expression (and not a type).
1195 func (p *parser) checkExpr(x ast.Expr) ast.Expr {
1196         switch t := unparen(x).(type) {
1197         case *ast.BadExpr:
1198         case *ast.Ident:
1199         case *ast.BasicLit:
1200         case *ast.FuncLit:
1201         case *ast.CompositeLit:
1202         case *ast.ParenExpr:
1203                 panic("unreachable")
1204         case *ast.SelectorExpr:
1205         case *ast.IndexExpr:
1206         case *ast.SliceExpr:
1207         case *ast.TypeAssertExpr:
1208                 if t.Type == nil {
1209                         // the form X.(type) is only allowed in type switch expressions
1210                         p.errorExpected(x.Pos(), "expression")
1211                         x = &ast.BadExpr{x.Pos(), x.End()}
1212                 }
1213         case *ast.CallExpr:
1214         case *ast.StarExpr:
1215         case *ast.UnaryExpr:
1216                 if t.Op == token.RANGE {
1217                         // the range operator is only allowed at the top of a for statement
1218                         p.errorExpected(x.Pos(), "expression")
1219                         x = &ast.BadExpr{x.Pos(), x.End()}
1220                 }
1221         case *ast.BinaryExpr:
1222         default:
1223                 // all other nodes are not proper expressions
1224                 p.errorExpected(x.Pos(), "expression")
1225                 x = &ast.BadExpr{x.Pos(), x.End()}
1226         }
1227         return x
1228 }
1229
1230
1231 // isTypeName returns true iff x is a (qualified) TypeName.
1232 func isTypeName(x ast.Expr) bool {
1233         switch t := x.(type) {
1234         case *ast.BadExpr:
1235         case *ast.Ident:
1236         case *ast.SelectorExpr:
1237                 _, isIdent := t.X.(*ast.Ident)
1238                 return isIdent
1239         default:
1240                 return false // all other nodes are not type names
1241         }
1242         return true
1243 }
1244
1245
1246 // isLiteralType returns true iff x is a legal composite literal type.
1247 func isLiteralType(x ast.Expr) bool {
1248         switch t := x.(type) {
1249         case *ast.BadExpr:
1250         case *ast.Ident:
1251         case *ast.SelectorExpr:
1252                 _, isIdent := t.X.(*ast.Ident)
1253                 return isIdent
1254         case *ast.ArrayType:
1255         case *ast.StructType:
1256         case *ast.MapType:
1257         default:
1258                 return false // all other nodes are not legal composite literal types
1259         }
1260         return true
1261 }
1262
1263
1264 // If x is of the form *T, deref returns T, otherwise it returns x.
1265 func deref(x ast.Expr) ast.Expr {
1266         if p, isPtr := x.(*ast.StarExpr); isPtr {
1267                 x = p.X
1268         }
1269         return x
1270 }
1271
1272
1273 // If x is of the form (T), unparen returns unparen(T), otherwise it returns x.
1274 func unparen(x ast.Expr) ast.Expr {
1275         if p, isParen := x.(*ast.ParenExpr); isParen {
1276                 x = unparen(p.X)
1277         }
1278         return x
1279 }
1280
1281
1282 // checkExprOrType checks that x is an expression or a type
1283 // (and not a raw type such as [...]T).
1284 //
1285 func (p *parser) checkExprOrType(x ast.Expr) ast.Expr {
1286         switch t := unparen(x).(type) {
1287         case *ast.ParenExpr:
1288                 panic("unreachable")
1289         case *ast.UnaryExpr:
1290                 if t.Op == token.RANGE {
1291                         // the range operator is only allowed at the top of a for statement
1292                         p.errorExpected(x.Pos(), "expression")
1293                         x = &ast.BadExpr{x.Pos(), x.End()}
1294                 }
1295         case *ast.ArrayType:
1296                 if len, isEllipsis := t.Len.(*ast.Ellipsis); isEllipsis {
1297                         p.error(len.Pos(), "expected array length, found '...'")
1298                         x = &ast.BadExpr{x.Pos(), x.End()}
1299                 }
1300         }
1301
1302         // all other nodes are expressions or types
1303         return x
1304 }
1305
1306
1307 // If lhs is set and the result is an identifier, it is not resolved.
1308 func (p *parser) parsePrimaryExpr(lhs bool) ast.Expr {
1309         if p.trace {
1310                 defer un(trace(p, "PrimaryExpr"))
1311         }
1312
1313         x := p.parseOperand(lhs)
1314 L:
1315         for {
1316                 switch p.tok {
1317                 case token.PERIOD:
1318                         p.next()
1319                         if lhs {
1320                                 p.resolve(x)
1321                         }
1322                         switch p.tok {
1323                         case token.IDENT:
1324                                 x = p.parseSelector(p.checkExpr(x))
1325                         case token.LPAREN:
1326                                 x = p.parseTypeAssertion(p.checkExpr(x))
1327                         default:
1328                                 pos := p.pos
1329                                 p.next() // make progress
1330                                 p.errorExpected(pos, "selector or type assertion")
1331                                 x = &ast.BadExpr{pos, p.pos}
1332                         }
1333                 case token.LBRACK:
1334                         if lhs {
1335                                 p.resolve(x)
1336                         }
1337                         x = p.parseIndexOrSlice(p.checkExpr(x))
1338                 case token.LPAREN:
1339                         if lhs {
1340                                 p.resolve(x)
1341                         }
1342                         x = p.parseCallOrConversion(p.checkExprOrType(x))
1343                 case token.LBRACE:
1344                         if isLiteralType(x) && (p.exprLev >= 0 || !isTypeName(x)) {
1345                                 if lhs {
1346                                         p.resolve(x)
1347                                 }
1348                                 x = p.parseLiteralValue(x)
1349                         } else {
1350                                 break L
1351                         }
1352                 default:
1353                         break L
1354                 }
1355                 lhs = false // no need to try to resolve again
1356         }
1357
1358         return x
1359 }
1360
1361
1362 // If lhs is set and the result is an identifier, it is not resolved.
1363 func (p *parser) parseUnaryExpr(lhs bool) ast.Expr {
1364         if p.trace {
1365                 defer un(trace(p, "UnaryExpr"))
1366         }
1367
1368         switch p.tok {
1369         case token.ADD, token.SUB, token.NOT, token.XOR, token.AND, token.RANGE:
1370                 pos, op := p.pos, p.tok
1371                 p.next()
1372                 x := p.parseUnaryExpr(false)
1373                 return &ast.UnaryExpr{pos, op, p.checkExpr(x)}
1374
1375         case token.ARROW:
1376                 // channel type or receive expression
1377                 pos := p.pos
1378                 p.next()
1379                 if p.tok == token.CHAN {
1380                         p.next()
1381                         value := p.parseType()
1382                         return &ast.ChanType{pos, ast.RECV, value}
1383                 }
1384
1385                 x := p.parseUnaryExpr(false)
1386                 return &ast.UnaryExpr{pos, token.ARROW, p.checkExpr(x)}
1387
1388         case token.MUL:
1389                 // pointer type or unary "*" expression
1390                 pos := p.pos
1391                 p.next()
1392                 x := p.parseUnaryExpr(false)
1393                 return &ast.StarExpr{pos, p.checkExprOrType(x)}
1394         }
1395
1396         return p.parsePrimaryExpr(lhs)
1397 }
1398
1399
1400 // If lhs is set and the result is an identifier, it is not resolved.
1401 func (p *parser) parseBinaryExpr(lhs bool, prec1 int) ast.Expr {
1402         if p.trace {
1403                 defer un(trace(p, "BinaryExpr"))
1404         }
1405
1406         x := p.parseUnaryExpr(lhs)
1407         for prec := p.tok.Precedence(); prec >= prec1; prec-- {
1408                 for p.tok.Precedence() == prec {
1409                         pos, op := p.pos, p.tok
1410                         p.next()
1411                         if lhs {
1412                                 p.resolve(x)
1413                                 lhs = false
1414                         }
1415                         y := p.parseBinaryExpr(false, prec+1)
1416                         x = &ast.BinaryExpr{p.checkExpr(x), pos, op, p.checkExpr(y)}
1417                 }
1418         }
1419
1420         return x
1421 }
1422
1423
1424 // If lhs is set and the result is an identifier, it is not resolved.
1425 // TODO(gri): parseExpr may return a type or even a raw type ([..]int) -
1426 //            should reject when a type/raw type is obviously not allowed
1427 func (p *parser) parseExpr(lhs bool) ast.Expr {
1428         if p.trace {
1429                 defer un(trace(p, "Expression"))
1430         }
1431
1432         return p.parseBinaryExpr(lhs, token.LowestPrec+1)
1433 }
1434
1435
1436 func (p *parser) parseRhs() ast.Expr {
1437         return p.parseExpr(false)
1438 }
1439
1440
1441 // ----------------------------------------------------------------------------
1442 // Statements
1443
1444 func (p *parser) parseSimpleStmt(labelOk bool) ast.Stmt {
1445         if p.trace {
1446                 defer un(trace(p, "SimpleStmt"))
1447         }
1448
1449         x := p.parseLhsList()
1450
1451         switch p.tok {
1452         case
1453                 token.DEFINE, token.ASSIGN, token.ADD_ASSIGN,
1454                 token.SUB_ASSIGN, token.MUL_ASSIGN, token.QUO_ASSIGN,
1455                 token.REM_ASSIGN, token.AND_ASSIGN, token.OR_ASSIGN,
1456                 token.XOR_ASSIGN, token.SHL_ASSIGN, token.SHR_ASSIGN, token.AND_NOT_ASSIGN:
1457                 // assignment statement
1458                 pos, tok := p.pos, p.tok
1459                 p.next()
1460                 y := p.parseRhsList()
1461                 return &ast.AssignStmt{x, pos, tok, y}
1462         }
1463
1464         if len(x) > 1 {
1465                 p.errorExpected(x[0].Pos(), "1 expression")
1466                 // continue with first expression
1467         }
1468
1469         switch p.tok {
1470         case token.COLON:
1471                 // labeled statement
1472                 colon := p.pos
1473                 p.next()
1474                 if label, isIdent := x[0].(*ast.Ident); labelOk && isIdent {
1475                         // Go spec: The scope of a label is the body of the function
1476                         // in which it is declared and excludes the body of any nested
1477                         // function.
1478                         stmt := &ast.LabeledStmt{label, colon, p.parseStmt()}
1479                         p.declare(stmt, p.labelScope, ast.Lbl, label)
1480                         return stmt
1481                 }
1482                 p.error(x[0].Pos(), "illegal label declaration")
1483                 return &ast.BadStmt{x[0].Pos(), colon + 1}
1484
1485         case token.ARROW:
1486                 // send statement
1487                 arrow := p.pos
1488                 p.next() // consume "<-"
1489                 y := p.parseRhs()
1490                 return &ast.SendStmt{x[0], arrow, y}
1491
1492         case token.INC, token.DEC:
1493                 // increment or decrement
1494                 s := &ast.IncDecStmt{x[0], p.pos, p.tok}
1495                 p.next() // consume "++" or "--"
1496                 return s
1497         }
1498
1499         // expression
1500         return &ast.ExprStmt{x[0]}
1501 }
1502
1503
1504 func (p *parser) parseCallExpr() *ast.CallExpr {
1505         x := p.parseRhs()
1506         if call, isCall := x.(*ast.CallExpr); isCall {
1507                 return call
1508         }
1509         p.errorExpected(x.Pos(), "function/method call")
1510         return nil
1511 }
1512
1513
1514 func (p *parser) parseGoStmt() ast.Stmt {
1515         if p.trace {
1516                 defer un(trace(p, "GoStmt"))
1517         }
1518
1519         pos := p.expect(token.GO)
1520         call := p.parseCallExpr()
1521         p.expectSemi()
1522         if call == nil {
1523                 return &ast.BadStmt{pos, pos + 2} // len("go")
1524         }
1525
1526         return &ast.GoStmt{pos, call}
1527 }
1528
1529
1530 func (p *parser) parseDeferStmt() ast.Stmt {
1531         if p.trace {
1532                 defer un(trace(p, "DeferStmt"))
1533         }
1534
1535         pos := p.expect(token.DEFER)
1536         call := p.parseCallExpr()
1537         p.expectSemi()
1538         if call == nil {
1539                 return &ast.BadStmt{pos, pos + 5} // len("defer")
1540         }
1541
1542         return &ast.DeferStmt{pos, call}
1543 }
1544
1545
1546 func (p *parser) parseReturnStmt() *ast.ReturnStmt {
1547         if p.trace {
1548                 defer un(trace(p, "ReturnStmt"))
1549         }
1550
1551         pos := p.pos
1552         p.expect(token.RETURN)
1553         var x []ast.Expr
1554         if p.tok != token.SEMICOLON && p.tok != token.RBRACE {
1555                 x = p.parseRhsList()
1556         }
1557         p.expectSemi()
1558
1559         return &ast.ReturnStmt{pos, x}
1560 }
1561
1562
1563 func (p *parser) parseBranchStmt(tok token.Token) *ast.BranchStmt {
1564         if p.trace {
1565                 defer un(trace(p, "BranchStmt"))
1566         }
1567
1568         pos := p.expect(tok)
1569         var label *ast.Ident
1570         if tok != token.FALLTHROUGH && p.tok == token.IDENT {
1571                 label = p.parseIdent()
1572                 // add to list of unresolved targets
1573                 n := len(p.targetStack) - 1
1574                 p.targetStack[n] = append(p.targetStack[n], label)
1575         }
1576         p.expectSemi()
1577
1578         return &ast.BranchStmt{pos, tok, label}
1579 }
1580
1581
1582 func (p *parser) makeExpr(s ast.Stmt) ast.Expr {
1583         if s == nil {
1584                 return nil
1585         }
1586         if es, isExpr := s.(*ast.ExprStmt); isExpr {
1587                 return p.checkExpr(es.X)
1588         }
1589         p.error(s.Pos(), "expected condition, found simple statement")
1590         return &ast.BadExpr{s.Pos(), s.End()}
1591 }
1592
1593
1594 func (p *parser) parseIfStmt() *ast.IfStmt {
1595         if p.trace {
1596                 defer un(trace(p, "IfStmt"))
1597         }
1598
1599         pos := p.expect(token.IF)
1600         p.openScope()
1601         defer p.closeScope()
1602
1603         var s ast.Stmt
1604         var x ast.Expr
1605         {
1606                 prevLev := p.exprLev
1607                 p.exprLev = -1
1608                 if p.tok == token.SEMICOLON {
1609                         p.next()
1610                         x = p.parseRhs()
1611                 } else {
1612                         s = p.parseSimpleStmt(false)
1613                         if p.tok == token.SEMICOLON {
1614                                 p.next()
1615                                 x = p.parseRhs()
1616                         } else {
1617                                 x = p.makeExpr(s)
1618                                 s = nil
1619                         }
1620                 }
1621                 p.exprLev = prevLev
1622         }
1623
1624         body := p.parseBlockStmt()
1625         var else_ ast.Stmt
1626         if p.tok == token.ELSE {
1627                 p.next()
1628                 else_ = p.parseStmt()
1629         } else {
1630                 p.expectSemi()
1631         }
1632
1633         return &ast.IfStmt{pos, s, x, body, else_}
1634 }
1635
1636
1637 func (p *parser) parseTypeList() (list []ast.Expr) {
1638         if p.trace {
1639                 defer un(trace(p, "TypeList"))
1640         }
1641
1642         list = append(list, p.parseType())
1643         for p.tok == token.COMMA {
1644                 p.next()
1645                 list = append(list, p.parseType())
1646         }
1647
1648         return
1649 }
1650
1651
1652 func (p *parser) parseCaseClause(exprSwitch bool) *ast.CaseClause {
1653         if p.trace {
1654                 defer un(trace(p, "CaseClause"))
1655         }
1656
1657         pos := p.pos
1658         var list []ast.Expr
1659         if p.tok == token.CASE {
1660                 p.next()
1661                 if exprSwitch {
1662                         list = p.parseRhsList()
1663                 } else {
1664                         list = p.parseTypeList()
1665                 }
1666         } else {
1667                 p.expect(token.DEFAULT)
1668         }
1669
1670         colon := p.expect(token.COLON)
1671         p.openScope()
1672         body := p.parseStmtList()
1673         p.closeScope()
1674
1675         return &ast.CaseClause{pos, list, colon, body}
1676 }
1677
1678
1679 func isExprSwitch(s ast.Stmt) bool {
1680         if s == nil {
1681                 return true
1682         }
1683         if e, ok := s.(*ast.ExprStmt); ok {
1684                 if a, ok := e.X.(*ast.TypeAssertExpr); ok {
1685                         return a.Type != nil // regular type assertion
1686                 }
1687                 return true
1688         }
1689         return false
1690 }
1691
1692
1693 func (p *parser) parseSwitchStmt() ast.Stmt {
1694         if p.trace {
1695                 defer un(trace(p, "SwitchStmt"))
1696         }
1697
1698         pos := p.expect(token.SWITCH)
1699         p.openScope()
1700         defer p.closeScope()
1701
1702         var s1, s2 ast.Stmt
1703         if p.tok != token.LBRACE {
1704                 prevLev := p.exprLev
1705                 p.exprLev = -1
1706                 if p.tok != token.SEMICOLON {
1707                         s2 = p.parseSimpleStmt(false)
1708                 }
1709                 if p.tok == token.SEMICOLON {
1710                         p.next()
1711                         s1 = s2
1712                         s2 = nil
1713                         if p.tok != token.LBRACE {
1714                                 s2 = p.parseSimpleStmt(false)
1715                         }
1716                 }
1717                 p.exprLev = prevLev
1718         }
1719
1720         exprSwitch := isExprSwitch(s2)
1721         lbrace := p.expect(token.LBRACE)
1722         var list []ast.Stmt
1723         for p.tok == token.CASE || p.tok == token.DEFAULT {
1724                 list = append(list, p.parseCaseClause(exprSwitch))
1725         }
1726         rbrace := p.expect(token.RBRACE)
1727         p.expectSemi()
1728         body := &ast.BlockStmt{lbrace, list, rbrace}
1729
1730         if exprSwitch {
1731                 return &ast.SwitchStmt{pos, s1, p.makeExpr(s2), body}
1732         }
1733         // type switch
1734         // TODO(gri): do all the checks!
1735         return &ast.TypeSwitchStmt{pos, s1, s2, body}
1736 }
1737
1738
1739 func (p *parser) parseCommClause() *ast.CommClause {
1740         if p.trace {
1741                 defer un(trace(p, "CommClause"))
1742         }
1743
1744         p.openScope()
1745         pos := p.pos
1746         var comm ast.Stmt
1747         if p.tok == token.CASE {
1748                 p.next()
1749                 lhs := p.parseLhsList()
1750                 if p.tok == token.ARROW {
1751                         // SendStmt
1752                         if len(lhs) > 1 {
1753                                 p.errorExpected(lhs[0].Pos(), "1 expression")
1754                                 // continue with first expression
1755                         }
1756                         arrow := p.pos
1757                         p.next()
1758                         rhs := p.parseRhs()
1759                         comm = &ast.SendStmt{lhs[0], arrow, rhs}
1760                 } else {
1761                         // RecvStmt
1762                         pos := p.pos
1763                         tok := p.tok
1764                         var rhs ast.Expr
1765                         if tok == token.ASSIGN || tok == token.DEFINE {
1766                                 // RecvStmt with assignment
1767                                 if len(lhs) > 2 {
1768                                         p.errorExpected(lhs[0].Pos(), "1 or 2 expressions")
1769                                         // continue with first two expressions
1770                                         lhs = lhs[0:2]
1771                                 }
1772                                 p.next()
1773                                 rhs = p.parseRhs()
1774                         } else {
1775                                 // rhs must be single receive operation
1776                                 if len(lhs) > 1 {
1777                                         p.errorExpected(lhs[0].Pos(), "1 expression")
1778                                         // continue with first expression
1779                                 }
1780                                 rhs = lhs[0]
1781                                 lhs = nil // there is no lhs
1782                         }
1783                         if x, isUnary := rhs.(*ast.UnaryExpr); !isUnary || x.Op != token.ARROW {
1784                                 p.errorExpected(rhs.Pos(), "send or receive operation")
1785                                 rhs = &ast.BadExpr{rhs.Pos(), rhs.End()}
1786                         }
1787                         if lhs != nil {
1788                                 comm = &ast.AssignStmt{lhs, pos, tok, []ast.Expr{rhs}}
1789                         } else {
1790                                 comm = &ast.ExprStmt{rhs}
1791                         }
1792                 }
1793         } else {
1794                 p.expect(token.DEFAULT)
1795         }
1796
1797         colon := p.expect(token.COLON)
1798         body := p.parseStmtList()
1799         p.closeScope()
1800
1801         return &ast.CommClause{pos, comm, colon, body}
1802 }
1803
1804
1805 func (p *parser) parseSelectStmt() *ast.SelectStmt {
1806         if p.trace {
1807                 defer un(trace(p, "SelectStmt"))
1808         }
1809
1810         pos := p.expect(token.SELECT)
1811         lbrace := p.expect(token.LBRACE)
1812         var list []ast.Stmt
1813         for p.tok == token.CASE || p.tok == token.DEFAULT {
1814                 list = append(list, p.parseCommClause())
1815         }
1816         rbrace := p.expect(token.RBRACE)
1817         p.expectSemi()
1818         body := &ast.BlockStmt{lbrace, list, rbrace}
1819
1820         return &ast.SelectStmt{pos, body}
1821 }
1822
1823
1824 func (p *parser) parseForStmt() ast.Stmt {
1825         if p.trace {
1826                 defer un(trace(p, "ForStmt"))
1827         }
1828
1829         pos := p.expect(token.FOR)
1830         p.openScope()
1831         defer p.closeScope()
1832
1833         var s1, s2, s3 ast.Stmt
1834         if p.tok != token.LBRACE {
1835                 prevLev := p.exprLev
1836                 p.exprLev = -1
1837                 if p.tok != token.SEMICOLON {
1838                         s2 = p.parseSimpleStmt(false)
1839                 }
1840                 if p.tok == token.SEMICOLON {
1841                         p.next()
1842                         s1 = s2
1843                         s2 = nil
1844                         if p.tok != token.SEMICOLON {
1845                                 s2 = p.parseSimpleStmt(false)
1846                         }
1847                         p.expectSemi()
1848                         if p.tok != token.LBRACE {
1849                                 s3 = p.parseSimpleStmt(false)
1850                         }
1851                 }
1852                 p.exprLev = prevLev
1853         }
1854
1855         body := p.parseBlockStmt()
1856         p.expectSemi()
1857
1858         if as, isAssign := s2.(*ast.AssignStmt); isAssign {
1859                 // possibly a for statement with a range clause; check assignment operator
1860                 if as.Tok != token.ASSIGN && as.Tok != token.DEFINE {
1861                         p.errorExpected(as.TokPos, "'=' or ':='")
1862                         return &ast.BadStmt{pos, body.End()}
1863                 }
1864                 // check lhs
1865                 var key, value ast.Expr
1866                 switch len(as.Lhs) {
1867                 case 2:
1868                         key, value = as.Lhs[0], as.Lhs[1]
1869                 case 1:
1870                         key = as.Lhs[0]
1871                 default:
1872                         p.errorExpected(as.Lhs[0].Pos(), "1 or 2 expressions")
1873                         return &ast.BadStmt{pos, body.End()}
1874                 }
1875                 // check rhs
1876                 if len(as.Rhs) != 1 {
1877                         p.errorExpected(as.Rhs[0].Pos(), "1 expression")
1878                         return &ast.BadStmt{pos, body.End()}
1879                 }
1880                 if rhs, isUnary := as.Rhs[0].(*ast.UnaryExpr); isUnary && rhs.Op == token.RANGE {
1881                         // rhs is range expression
1882                         // (any short variable declaration was handled by parseSimpleStat above)
1883                         return &ast.RangeStmt{pos, key, value, as.TokPos, as.Tok, rhs.X, body}
1884                 }
1885                 p.errorExpected(s2.Pos(), "range clause")
1886                 return &ast.BadStmt{pos, body.End()}
1887         }
1888
1889         // regular for statement
1890         return &ast.ForStmt{pos, s1, p.makeExpr(s2), s3, body}
1891 }
1892
1893
1894 func (p *parser) parseStmt() (s ast.Stmt) {
1895         if p.trace {
1896                 defer un(trace(p, "Statement"))
1897         }
1898
1899         switch p.tok {
1900         case token.CONST, token.TYPE, token.VAR:
1901                 s = &ast.DeclStmt{p.parseDecl()}
1902         case
1903                 // tokens that may start a top-level expression
1904                 token.IDENT, token.INT, token.FLOAT, token.CHAR, token.STRING, token.FUNC, token.LPAREN, // operand
1905                 token.LBRACK, token.STRUCT, // composite type
1906                 token.MUL, token.AND, token.ARROW, token.ADD, token.SUB, token.XOR: // unary operators
1907                 s = p.parseSimpleStmt(true)
1908                 // because of the required look-ahead, labeled statements are
1909                 // parsed by parseSimpleStmt - don't expect a semicolon after
1910                 // them
1911                 if _, isLabeledStmt := s.(*ast.LabeledStmt); !isLabeledStmt {
1912                         p.expectSemi()
1913                 }
1914         case token.GO:
1915                 s = p.parseGoStmt()
1916         case token.DEFER:
1917                 s = p.parseDeferStmt()
1918         case token.RETURN:
1919                 s = p.parseReturnStmt()
1920         case token.BREAK, token.CONTINUE, token.GOTO, token.FALLTHROUGH:
1921                 s = p.parseBranchStmt(p.tok)
1922         case token.LBRACE:
1923                 s = p.parseBlockStmt()
1924                 p.expectSemi()
1925         case token.IF:
1926                 s = p.parseIfStmt()
1927         case token.SWITCH:
1928                 s = p.parseSwitchStmt()
1929         case token.SELECT:
1930                 s = p.parseSelectStmt()
1931         case token.FOR:
1932                 s = p.parseForStmt()
1933         case token.SEMICOLON:
1934                 s = &ast.EmptyStmt{p.pos}
1935                 p.next()
1936         case token.RBRACE:
1937                 // a semicolon may be omitted before a closing "}"
1938                 s = &ast.EmptyStmt{p.pos}
1939         default:
1940                 // no statement found
1941                 pos := p.pos
1942                 p.errorExpected(pos, "statement")
1943                 p.next() // make progress
1944                 s = &ast.BadStmt{pos, p.pos}
1945         }
1946
1947         return
1948 }
1949
1950
1951 // ----------------------------------------------------------------------------
1952 // Declarations
1953
1954 type parseSpecFunction func(p *parser, doc *ast.CommentGroup, iota int) ast.Spec
1955
1956
1957 func parseImportSpec(p *parser, doc *ast.CommentGroup, _ int) ast.Spec {
1958         if p.trace {
1959                 defer un(trace(p, "ImportSpec"))
1960         }
1961
1962         var ident *ast.Ident
1963         switch p.tok {
1964         case token.PERIOD:
1965                 ident = &ast.Ident{p.pos, ".", nil}
1966                 p.next()
1967         case token.IDENT:
1968                 ident = p.parseIdent()
1969         }
1970
1971         var path *ast.BasicLit
1972         if p.tok == token.STRING {
1973                 path = &ast.BasicLit{p.pos, p.tok, p.lit}
1974                 p.next()
1975         } else {
1976                 p.expect(token.STRING) // use expect() error handling
1977         }
1978         p.expectSemi() // call before accessing p.linecomment
1979
1980         // collect imports
1981         spec := &ast.ImportSpec{doc, ident, path, p.lineComment}
1982         p.imports = append(p.imports, spec)
1983
1984         return spec
1985 }
1986
1987
1988 func parseConstSpec(p *parser, doc *ast.CommentGroup, iota int) ast.Spec {
1989         if p.trace {
1990                 defer un(trace(p, "ConstSpec"))
1991         }
1992
1993         idents := p.parseIdentList()
1994         typ := p.tryType()
1995         var values []ast.Expr
1996         if typ != nil || p.tok == token.ASSIGN || iota == 0 {
1997                 p.expect(token.ASSIGN)
1998                 values = p.parseRhsList()
1999         }
2000         p.expectSemi() // call before accessing p.linecomment
2001
2002         // Go spec: The scope of a constant or variable identifier declared inside
2003         // a function begins at the end of the ConstSpec or VarSpec and ends at
2004         // the end of the innermost containing block.
2005         // (Global identifiers are resolved in a separate phase after parsing.)
2006         spec := &ast.ValueSpec{doc, idents, typ, values, p.lineComment}
2007         p.declare(spec, p.topScope, ast.Con, idents...)
2008
2009         return spec
2010 }
2011
2012
2013 func parseTypeSpec(p *parser, doc *ast.CommentGroup, _ int) ast.Spec {
2014         if p.trace {
2015                 defer un(trace(p, "TypeSpec"))
2016         }
2017
2018         ident := p.parseIdent()
2019         typ := p.parseType()
2020         p.expectSemi() // call before accessing p.linecomment
2021
2022         // Go spec: The scope of a type identifier declared inside a function begins
2023         // at the identifier in the TypeSpec and ends at the end of the innermost
2024         // containing block.
2025         // (Global identifiers are resolved in a separate phase after parsing.)
2026         spec := &ast.TypeSpec{doc, ident, typ, p.lineComment}
2027         p.declare(spec, p.topScope, ast.Typ, ident)
2028
2029         return spec
2030 }
2031
2032
2033 func parseVarSpec(p *parser, doc *ast.CommentGroup, _ int) ast.Spec {
2034         if p.trace {
2035                 defer un(trace(p, "VarSpec"))
2036         }
2037
2038         idents := p.parseIdentList()
2039         typ := p.tryType()
2040         var values []ast.Expr
2041         if typ == nil || p.tok == token.ASSIGN {
2042                 p.expect(token.ASSIGN)
2043                 values = p.parseRhsList()
2044         }
2045         p.expectSemi() // call before accessing p.linecomment
2046
2047         // Go spec: The scope of a constant or variable identifier declared inside
2048         // a function begins at the end of the ConstSpec or VarSpec and ends at
2049         // the end of the innermost containing block.
2050         // (Global identifiers are resolved in a separate phase after parsing.)
2051         spec := &ast.ValueSpec{doc, idents, typ, values, p.lineComment}
2052         p.declare(spec, p.topScope, ast.Var, idents...)
2053
2054         return spec
2055 }
2056
2057
2058 func (p *parser) parseGenDecl(keyword token.Token, f parseSpecFunction) *ast.GenDecl {
2059         if p.trace {
2060                 defer un(trace(p, "GenDecl("+keyword.String()+")"))
2061         }
2062
2063         doc := p.leadComment
2064         pos := p.expect(keyword)
2065         var lparen, rparen token.Pos
2066         var list []ast.Spec
2067         if p.tok == token.LPAREN {
2068                 lparen = p.pos
2069                 p.next()
2070                 for iota := 0; p.tok != token.RPAREN && p.tok != token.EOF; iota++ {
2071                         list = append(list, f(p, p.leadComment, iota))
2072                 }
2073                 rparen = p.expect(token.RPAREN)
2074                 p.expectSemi()
2075         } else {
2076                 list = append(list, f(p, nil, 0))
2077         }
2078
2079         return &ast.GenDecl{doc, pos, keyword, lparen, list, rparen}
2080 }
2081
2082
2083 func (p *parser) parseReceiver(scope *ast.Scope) *ast.FieldList {
2084         if p.trace {
2085                 defer un(trace(p, "Receiver"))
2086         }
2087
2088         pos := p.pos
2089         par := p.parseParameters(scope, false)
2090
2091         // must have exactly one receiver
2092         if par.NumFields() != 1 {
2093                 p.errorExpected(pos, "exactly one receiver")
2094                 // TODO determine a better range for BadExpr below
2095                 par.List = []*ast.Field{&ast.Field{Type: &ast.BadExpr{pos, pos}}}
2096                 return par
2097         }
2098
2099         // recv type must be of the form ["*"] identifier
2100         recv := par.List[0]
2101         base := deref(recv.Type)
2102         if _, isIdent := base.(*ast.Ident); !isIdent {
2103                 p.errorExpected(base.Pos(), "(unqualified) identifier")
2104                 par.List = []*ast.Field{&ast.Field{Type: &ast.BadExpr{recv.Pos(), recv.End()}}}
2105         }
2106
2107         return par
2108 }
2109
2110
2111 func (p *parser) parseFuncDecl() *ast.FuncDecl {
2112         if p.trace {
2113                 defer un(trace(p, "FunctionDecl"))
2114         }
2115
2116         doc := p.leadComment
2117         pos := p.expect(token.FUNC)
2118         scope := ast.NewScope(p.topScope) // function scope
2119
2120         var recv *ast.FieldList
2121         if p.tok == token.LPAREN {
2122                 recv = p.parseReceiver(scope)
2123         }
2124
2125         ident := p.parseIdent()
2126
2127         params, results := p.parseSignature(scope)
2128
2129         var body *ast.BlockStmt
2130         if p.tok == token.LBRACE {
2131                 body = p.parseBody(scope)
2132         }
2133         p.expectSemi()
2134
2135         decl := &ast.FuncDecl{doc, recv, ident, &ast.FuncType{pos, params, results}, body}
2136         if recv == nil {
2137                 // Go spec: The scope of an identifier denoting a constant, type,
2138                 // variable, or function (but not method) declared at top level
2139                 // (outside any function) is the package block.
2140                 //
2141                 // init() functions cannot be referred to and there may
2142                 // be more than one - don't put them in the pkgScope
2143                 if ident.Name != "init" {
2144                         p.declare(decl, p.pkgScope, ast.Fun, ident)
2145                 }
2146         }
2147
2148         return decl
2149 }
2150
2151
2152 func (p *parser) parseDecl() ast.Decl {
2153         if p.trace {
2154                 defer un(trace(p, "Declaration"))
2155         }
2156
2157         var f parseSpecFunction
2158         switch p.tok {
2159         case token.CONST:
2160                 f = parseConstSpec
2161
2162         case token.TYPE:
2163                 f = parseTypeSpec
2164
2165         case token.VAR:
2166                 f = parseVarSpec
2167
2168         case token.FUNC:
2169                 return p.parseFuncDecl()
2170
2171         default:
2172                 pos := p.pos
2173                 p.errorExpected(pos, "declaration")
2174                 p.next() // make progress
2175                 decl := &ast.BadDecl{pos, p.pos}
2176                 return decl
2177         }
2178
2179         return p.parseGenDecl(p.tok, f)
2180 }
2181
2182
2183 func (p *parser) parseDeclList() (list []ast.Decl) {
2184         if p.trace {
2185                 defer un(trace(p, "DeclList"))
2186         }
2187
2188         for p.tok != token.EOF {
2189                 list = append(list, p.parseDecl())
2190         }
2191
2192         return
2193 }
2194
2195
2196 // ----------------------------------------------------------------------------
2197 // Source files
2198
2199 func (p *parser) parseFile() *ast.File {
2200         if p.trace {
2201                 defer un(trace(p, "File"))
2202         }
2203
2204         // package clause
2205         doc := p.leadComment
2206         pos := p.expect(token.PACKAGE)
2207         // Go spec: The package clause is not a declaration;
2208         // the package name does not appear in any scope.
2209         ident := p.parseIdent()
2210         p.expectSemi()
2211
2212         var decls []ast.Decl
2213
2214         // Don't bother parsing the rest if we had errors already.
2215         // Likely not a Go source file at all.
2216
2217         if p.ErrorCount() == 0 && p.mode&PackageClauseOnly == 0 {
2218                 // import decls
2219                 for p.tok == token.IMPORT {
2220                         decls = append(decls, p.parseGenDecl(token.IMPORT, parseImportSpec))
2221                 }
2222
2223                 if p.mode&ImportsOnly == 0 {
2224                         // rest of package body
2225                         for p.tok != token.EOF {
2226                                 decls = append(decls, p.parseDecl())
2227                         }
2228                 }
2229         }
2230
2231         assert(p.topScope == p.pkgScope, "imbalanced scopes")
2232
2233         // resolve global identifiers within the same file
2234         i := 0
2235         for _, ident := range p.unresolved {
2236                 // i <= index for current ident
2237                 assert(ident.Obj == unresolved, "object already resolved")
2238                 ident.Obj = p.pkgScope.Lookup(ident.Name) // also removes unresolved sentinel
2239                 if ident.Obj == nil {
2240                         p.unresolved[i] = ident
2241                         i++
2242                 }
2243         }
2244
2245         // TODO(gri): store p.imports in AST
2246         return &ast.File{doc, pos, ident, decls, p.pkgScope, p.imports, p.unresolved[0:i], p.comments}
2247 }