OSDN Git Service

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