blob: 52a7fcb1daca44031c8b69801b8f1aaec61de253 [file] [log] [blame]
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +01001// Copyright 2018 The CUE Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package parser
16
17import (
18 "fmt"
19 "strconv"
20 "strings"
21 "unicode"
22
23 "cuelang.org/go/cue/ast"
24 "cuelang.org/go/cue/errors"
25 "cuelang.org/go/cue/scanner"
26 "cuelang.org/go/cue/token"
27)
28
29// The parser structure holds the parser's internal state.
30type parser struct {
31 file *token.File
32 errors errors.List
33 scanner scanner.Scanner
34
35 // Tracing/debugging
36 mode mode // parsing mode
37 trace bool // == (mode & Trace != 0)
38 indent int // indentation used for tracing output
39
40 // Comments
41 leadComment *ast.CommentGroup
42 comments *commentState
43
44 // Next token
45 pos token.Pos // token position
46 tok token.Token // one token look-ahead
47 lit string // token literal
48
49 // Error recovery
50 // (used to limit the number of calls to syncXXX functions
51 // w/o making scanning progress - avoids potential endless
52 // loops across multiple parser functions during error recovery)
53 syncPos token.Pos // last synchronization position
54 syncCnt int // number of calls to syncXXX without progress
55
56 // Non-syntactic parser control
57 exprLev int // < 0: in control clause, >= 0: in expression
58
59 imports []*ast.ImportSpec // list of imports
60
61}
62
63func (p *parser) init(fset *token.FileSet, filename string, src []byte, mode []Option) {
64 p.file = fset.AddFile(filename, -1, len(src))
65 for _, f := range mode {
66 f(p)
67 }
68 var m scanner.Mode
69 if p.mode&parseCommentsMode != 0 {
70 m = scanner.ScanComments
71 }
72 eh := func(pos token.Position, msg string) { p.errors.AddNew(pos, msg) }
73 p.scanner.Init(p.file, src, eh, m)
74
75 p.trace = p.mode&traceMode != 0 // for convenience (p.trace is used frequently)
76
77 p.comments = &commentState{pos: -1}
78
79 p.next()
80}
81
82type commentList struct {
83 taken bool // for validation
84 attachTail bool
85 head *ast.CommentGroup
86 last *ast.CommentGroup
87}
88
89type commentState struct {
90 parent *commentState
91 pos int8
92 groups []*ast.CommentGroup
93
94 // lists are not attached to nodes themselves. Enclosed expressions may
95 // miss a comment due to commas and line termination. closeLists ensures
96 // that comments will be passed to someone.
97 isList int
98 lastChild ast.Node
99 lastPos int8
100}
101
102// openComments reserves the next doc comment for the caller and flushes
103func (p *parser) openComments() *commentState {
104 if c := p.comments; c != nil && c.isList > 0 {
105 if c.lastChild != nil {
106 for _, cg := range c.groups {
107 cg.Position = c.lastPos
108 c.lastChild.AddComment(cg)
109 }
110 c.groups = nil
111 }
112 c.lastChild = nil
113 }
114 c := &commentState{
115 parent: p.comments,
116 groups: []*ast.CommentGroup{p.leadComment},
117 }
118 p.comments = c
119 p.leadComment = nil
120 return c
121}
122
123// openList is used to treat a list of comments as a single comment
124// position in a production.
125func (p *parser) openList() {
126 if p.comments.isList > 0 {
127 p.comments.isList++
128 return
129 }
130 c := &commentState{
131 parent: p.comments,
132 isList: 1,
133 }
134 p.comments = c
135}
136
137func (c *commentState) add(g *ast.CommentGroup) {
138 g.Position = c.pos
139 c.groups = append(c.groups, g)
140}
141
142func (p *parser) closeList() {
143 c := p.comments
144 if c.lastChild != nil {
145 for _, cg := range c.groups {
146 cg.Position = c.lastPos
147 c.lastChild.AddComment(cg)
148 }
149 c.groups = nil
150 }
151 switch c.isList--; {
152 case c.isList < 0:
153 panic("unmatched close list")
154 case c.isList == 0:
155 parent := c.parent
156 parent.groups = append(parent.groups, c.groups...)
157 parent.pos++
158 p.comments = parent
159 }
160}
161
162func (c *commentState) closeNode(p *parser, n ast.Node) ast.Node {
163 if p.comments != c {
164 panic("unmatched comments")
165 }
166 p.comments = c.parent
167 if c.parent != nil {
168 c.parent.lastChild = n
169 c.parent.lastPos = c.pos
170 c.parent.pos++
171 }
172 for _, cg := range c.groups {
173 if n != nil {
174 n.AddComment(cg)
175 }
176 }
177 c.groups = nil
178 return n
179}
180
181func (c *commentState) closeExpr(p *parser, n ast.Expr) ast.Expr {
182 c.closeNode(p, n)
183 return n
184}
185
186func (c *commentState) closeClause(p *parser, n ast.Clause) ast.Clause {
187 c.closeNode(p, n)
188 return n
189}
190
191// ----------------------------------------------------------------------------
192// Parsing support
193
194func (p *parser) printTrace(a ...interface{}) {
195 const dots = ". . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . "
196 const n = len(dots)
197 pos := p.file.Position(p.pos)
198 fmt.Printf("%5d:%3d: ", pos.Line, pos.Column)
199 i := 2 * p.indent
200 for i > n {
201 fmt.Print(dots)
202 i -= n
203 }
204 // i <= n
205 fmt.Print(dots[0:i])
206 fmt.Println(a...)
207}
208
209func trace(p *parser, msg string) *parser {
210 p.printTrace(msg, "(")
211 p.indent++
212 return p
213}
214
215// Usage pattern: defer un(trace(p, "..."))
216func un(p *parser) {
217 p.indent--
218 p.printTrace(")")
219}
220
221// Advance to the next
222func (p *parser) next0() {
223 // Because of one-token look-ahead, print the previous token
224 // when tracing as it provides a more readable output. The
225 // very first token (!p.pos.IsValid()) is not initialized
226 // (it is ILLEGAL), so don't print it .
227 if p.trace && p.pos.IsValid() {
228 s := p.tok.String()
229 switch {
230 case p.tok.IsLiteral():
231 p.printTrace(s, p.lit)
232 case p.tok.IsOperator(), p.tok.IsKeyword():
233 p.printTrace("\"" + s + "\"")
234 default:
235 p.printTrace(s)
236 }
237 }
238
239 p.pos, p.tok, p.lit = p.scanner.Scan()
240}
241
242// Consume a comment and return it and the line on which it ends.
243func (p *parser) consumeComment() (comment *ast.Comment, endline int) {
244 // /*-style comments may end on a different line than where they start.
245 // Scan the comment for '\n' chars and adjust endline accordingly.
246 endline = p.file.Line(p.pos)
247 if p.lit[1] == '*' {
248 // don't use range here - no need to decode Unicode code points
249 for i := 0; i < len(p.lit); i++ {
250 if p.lit[i] == '\n' {
251 endline++
252 }
253 }
254 }
255
256 comment = &ast.Comment{Slash: p.pos, Text: p.lit}
257 p.next0()
258
259 return
260}
261
262// Consume a group of adjacent comments, add it to the parser's
263// comments list, and return it together with the line at which
264// the last comment in the group ends. A non-comment token or n
265// empty lines terminate a comment group.
266func (p *parser) consumeCommentGroup(n int) (comments *ast.CommentGroup, endline int) {
267 var list []*ast.Comment
268 endline = p.file.Line(p.pos)
269 for p.tok == token.COMMENT && p.file.Line(p.pos) <= endline+n {
270 var comment *ast.Comment
271 comment, endline = p.consumeComment()
272 list = append(list, comment)
273 }
274
275 cg := &ast.CommentGroup{List: list}
276 comments = cg
277 return
278}
279
280// Advance to the next non-comment In the process, collect
281// any comment groups encountered, and refield the last lead and
282// and line comments.
283//
284// A lead comment is a comment group that starts and ends in a
285// line without any other tokens and that is followed by a non-comment
286// token on the line immediately after the comment group.
287//
288// A line comment is a comment group that follows a non-comment
289// token on the same line, and that has no tokens after it on the line
290// where it ends.
291//
292// Lead and line comments may be considered documentation that is
293// stored in the AST.
294func (p *parser) next() {
295 // A leadComment may not be consumed if it leads an inner token of a node.
296 if p.leadComment != nil {
297 p.comments.add(p.leadComment)
298 }
299 p.leadComment = nil
300 prev := p.pos
301 p.next0()
302 p.comments.pos++
303
304 if p.tok == token.COMMENT {
305 var comment *ast.CommentGroup
306 var endline int
307
308 if p.file.Line(p.pos) == p.file.Line(prev) {
309 // The comment is on same line as the previous token; it
310 // cannot be a lead comment but may be a line comment.
311 comment, endline = p.consumeCommentGroup(0)
312 if p.file.Line(p.pos) != endline {
313 // The next token is on a different line, thus
314 // the last comment group is a line comment.
315 comment.Line = true
316 }
317 }
318
319 // consume successor comments, if any
320 endline = -1
321 for p.tok == token.COMMENT {
322 if comment != nil {
323 p.comments.add(comment)
324 }
325 comment, endline = p.consumeCommentGroup(1)
326 }
327
328 if endline+1 == p.file.Line(p.pos) && p.tok != token.EOF {
329 // The next token is following on the line immediately after the
330 // comment group, thus the last comment group is a lead comment.
331 comment.Doc = true
332 p.leadComment = comment
333 } else {
334 p.comments.add(comment)
335 }
336 }
337}
338
339// A bailout panic is raised to indicate early termination.
340type bailout struct{}
341
342func (p *parser) error(pos token.Pos, msg string) {
343 ePos := p.file.Position(pos)
344
345 // If AllErrors is not set, discard errors reported on the same line
346 // as the last recorded error and stop parsing if there are more than
347 // 10 errors.
348 if p.mode&allErrorsMode == 0 {
349 n := len(p.errors)
350 if n > 0 && p.errors[n-1].Position().Line == ePos.Line {
351 return // discard - likely a spurious error
352 }
353 if n > 10 {
354 panic(bailout{})
355 }
356 }
357
358 p.errors.AddNew(ePos, msg)
359}
360
361func (p *parser) errorExpected(pos token.Pos, msg string) {
362 msg = "expected " + msg
363 if pos == p.pos {
364 // the error happened at the current position;
365 // make the error message more specific
366 if p.tok == token.COMMA && p.lit == "\n" {
367 msg += ", found newline"
368 } else {
369 msg += ", found '" + p.tok.String() + "'"
370 if p.tok.IsLiteral() {
371 msg += " " + p.lit
372 }
373 }
374 }
375 p.error(pos, msg)
376}
377
378func (p *parser) expect(tok token.Token) token.Pos {
379 pos := p.pos
380 if p.tok != tok {
381 p.errorExpected(pos, "'"+tok.String()+"'")
382 }
383 p.next() // make progress
384 return pos
385}
386
387// expectClosing is like expect but provides a better error message
388// for the common case of a missing comma before a newline.
389func (p *parser) expectClosing(tok token.Token, context string) token.Pos {
390 if p.tok != tok && p.tok == token.COMMA && p.lit == "\n" {
391 p.error(p.pos, "missing ',' before newline in "+context)
392 p.next()
393 }
394 return p.expect(tok)
395}
396
397func (p *parser) expectComma() {
398 // semicolon is optional before a closing ')', ']', '}', or newline
399 if p.tok != token.RPAREN && p.tok != token.RBRACE && p.tok != token.EOF {
400 switch p.tok {
401 case token.COMMA:
402 p.next()
403 default:
404 p.errorExpected(p.pos, "','")
405 syncExpr(p)
406 }
407 }
408}
409
410func (p *parser) atComma(context string, follow ...token.Token) bool {
411 if p.tok == token.COMMA {
412 return true
413 }
414 for _, t := range follow {
415 if p.tok == t {
416 return false
417 }
418 }
419 msg := "missing ','"
420 // TODO: find a way to detect crossing lines now we don't have a semi.
421 if p.lit == "\n" {
422 msg += " before newline"
423 }
424 p.error(p.pos, msg+" in "+context)
425 return true // "insert" comma and continue
426}
427
428func assert(cond bool, msg string) {
429 if !cond {
430 panic("lacelang/parser internal error: " + msg)
431 }
432}
433
434// syncExpr advances to the next field in a field list.
435// Used for synchronization after an error.
436func syncExpr(p *parser) {
437 for {
438 switch p.tok {
439 case token.COMMA:
440 // Return only if parser made some progress since last
441 // sync or if it has not reached 10 sync calls without
442 // progress. Otherwise consume at least one token to
443 // avoid an endless parser loop (it is possible that
444 // both parseOperand and parseStmt call syncStmt and
445 // correctly do not advance, thus the need for the
446 // invocation limit p.syncCnt).
447 if p.pos == p.syncPos && p.syncCnt < 10 {
448 p.syncCnt++
449 return
450 }
451 if p.pos > p.syncPos {
452 p.syncPos = p.pos
453 p.syncCnt = 0
454 return
455 }
456 // Reaching here indicates a parser bug, likely an
457 // incorrect token list in this function, but it only
458 // leads to skipping of possibly correct code if a
459 // previous error is present, and thus is preferred
460 // over a non-terminating parse.
461 case token.EOF:
462 return
463 }
464 p.next()
465 }
466}
467
468// safePos returns a valid file position for a given position: If pos
469// is valid to begin with, safePos returns pos. If pos is out-of-range,
470// safePos returns the EOF position.
471//
472// This is hack to work around "artificial" end positions in the AST which
473// are computed by adding 1 to (presumably valid) token positions. If the
474// token positions are invalid due to parse errors, the resulting end position
475// may be past the file's EOF position, which would lead to panics if used
476// later on.
477func (p *parser) safePos(pos token.Pos) (res token.Pos) {
478 defer func() {
479 if recover() != nil {
480 res = token.Pos(p.file.Base() + p.file.Size()) // EOF position
481 }
482 }()
483 _ = p.file.Offset(pos) // trigger a panic if position is out-of-range
484 return pos
485}
486
487// ----------------------------------------------------------------------------
488// Identifiers
489
490func (p *parser) parseIdent() *ast.Ident {
491 c := p.openComments()
492 pos := p.pos
493 name := "_"
494 if p.tok == token.IDENT {
495 name = p.lit
496 p.next()
497 } else {
498 p.expect(token.IDENT) // use expect() error handling
499 }
500 ident := &ast.Ident{NamePos: pos, Name: name}
501 c.closeNode(p, ident)
502 return ident
503}
504
505// ----------------------------------------------------------------------------
506// Expressions
507
508// parseOperand returns an expression.
509// Callers must verify the result.
510func (p *parser) parseOperand() (expr ast.Expr) {
511 if p.trace {
512 defer un(trace(p, "Operand"))
513 }
514
515 switch p.tok {
516 case token.IDENT:
517 return p.parseIdent()
518
519 case token.LBRACE:
520 return p.parseStruct()
521
522 case token.LBRACK:
523 return p.parseList()
524
525 case token.BOTTOM:
526 c := p.openComments()
527 x := &ast.BottomLit{Bottom: p.pos}
528 p.next()
529 return c.closeExpr(p, x)
530
531 case token.NULL, token.TRUE, token.FALSE, token.INT, token.FLOAT, token.STRING:
532 c := p.openComments()
533 x := &ast.BasicLit{ValuePos: p.pos, Kind: p.tok, Value: p.lit}
534 p.next()
535 return c.closeExpr(p, x)
536
537 case token.INTERPOLATION:
538 return p.parseInterpolation()
539
540 case token.LPAREN:
541 c := p.openComments()
542 defer func() { c.closeNode(p, expr) }()
543 lparen := p.pos
544 p.next()
545 if p.tok == token.RPAREN && p.mode&parseLambdasMode != 0 {
546 c.pos = 2
547 rparen := p.expect(token.RPAREN)
548 p.expect(token.LAMBDA)
549 return &ast.LambdaExpr{
550 Lparen: lparen,
551 Rparen: rparen,
552 Expr: p.parseRHS(),
553 }
554 }
555 p.exprLev++
556 p.openList()
557 x := p.parseRHS() // types may be parenthesized: (some type)
558 var params []*ast.Field
559 ident, ok := x.(*ast.Ident)
560 if ok && (p.tok == token.COLON || p.tok == token.COMMA) && p.mode&parseLambdasMode != 0 {
561 params = p.parseParams(ident, token.RPAREN)
562 }
563 p.closeList()
564 p.exprLev--
565 rparen := p.expect(token.RPAREN)
566 if p.tok == token.LAMBDA || params != nil && p.mode&parseLambdasMode != 0 {
567 p.expect(token.LAMBDA)
568 if params == nil {
569 m := &ast.Field{Label: ident}
570 params = append(params, m)
571 }
572 return &ast.LambdaExpr{
573 Lparen: lparen,
574 Params: params,
575 Rparen: rparen,
576 Expr: p.parseRHS(),
577 }
578 }
579 return &ast.ParenExpr{
580 Lparen: lparen,
581 X: x,
582 Rparen: rparen}
583 }
584
585 // we have an error
586 c := p.openComments()
587 pos := p.pos
588 p.errorExpected(pos, "operand")
589 syncExpr(p)
590 return c.closeExpr(p, &ast.BadExpr{From: pos, To: p.pos})
591}
592
593func (p *parser) parseParams(ident *ast.Ident, follow token.Token) (params []*ast.Field) {
594 for {
595 c := p.openComments()
596 if ident == nil {
597 ident = p.parseIdent()
598 }
599 m := &ast.Field{Label: ident}
600 if p.tok == token.COLON {
601 m.Colon = p.expect(token.COLON)
602 m.Value = p.parseRHS()
603 }
604 hasComma := p.tok == token.COMMA
605 if hasComma {
606 p.expect(token.COMMA)
607 }
608 c.closeNode(p, m)
609 params = append(params, m)
610 if !hasComma || p.tok == follow || p.tok == token.EOF {
611 break
612 }
613 ident = nil
614 }
615 return params
616}
617
618func (p *parser) parseIndexOrSlice(x ast.Expr) (expr ast.Expr) {
619 if p.trace {
620 defer un(trace(p, "IndexOrSlice"))
621 }
622
623 c := p.openComments()
624 defer func() { c.closeNode(p, expr) }()
625 c.pos = 1
626
627 const N = 2
628 lbrack := p.expect(token.LBRACK)
629
630 p.exprLev++
631 var index [N]ast.Expr
632 var colons [N - 1]token.Pos
633 if p.tok != token.COLON {
634 index[0] = p.parseRHS()
635 }
636 nColons := 0
637 for p.tok == token.COLON && nColons < len(colons) {
638 colons[nColons] = p.pos
639 nColons++
640 p.next()
641 if p.tok != token.COLON && p.tok != token.RBRACK && p.tok != token.EOF {
642 index[nColons] = p.parseRHS()
643 }
644 }
645 p.exprLev--
646 rbrack := p.expect(token.RBRACK)
647
648 if nColons > 0 {
649 return &ast.SliceExpr{
650 X: x,
651 Lbrack: lbrack,
652 Low: index[0],
653 High: index[1],
654 Rbrack: rbrack}
655 }
656
657 return &ast.IndexExpr{
658 X: x,
659 Lbrack: lbrack,
660 Index: index[0],
661 Rbrack: rbrack}
662}
663
664func (p *parser) parseCallOrConversion(fun ast.Expr) (expr *ast.CallExpr) {
665 if p.trace {
666 defer un(trace(p, "CallOrConversion"))
667 }
668 c := p.openComments()
669 defer func() { c.closeNode(p, expr) }()
670
671 lparen := p.expect(token.LPAREN)
672 p.exprLev++
673 var list []ast.Expr
674 for p.tok != token.RPAREN && p.tok != token.EOF {
675 list = append(list, p.parseRHS()) // builtins may expect a type: make(some type, ...)
676 if !p.atComma("argument list", token.RPAREN) {
677 break
678 }
679 p.next()
680 }
681 p.exprLev--
682 rparen := p.expectClosing(token.RPAREN, "argument list")
683
684 return &ast.CallExpr{
685 Fun: fun,
686 Lparen: lparen,
687 Args: list,
688 Rparen: rparen}
689}
690
691func (p *parser) parseFieldList(allowEmit bool) (list []ast.Decl) {
692 if p.trace {
693 defer un(trace(p, "FieldList"))
694 }
695 origEmit := allowEmit
696 p.openList()
697 defer p.closeList()
698
699 for p.tok != token.RBRACE && p.tok != token.EOF {
700 d := p.parseField(allowEmit)
701 if e, ok := d.(*ast.EmitDecl); ok {
702 if origEmit && !allowEmit {
703 p.error(p.pos, "only one emit allowed at top level")
704 }
705 if !origEmit || !allowEmit {
706 d = &ast.BadDecl{From: e.Pos(), To: e.End()}
707 for _, cg := range e.Comments() {
708 d.AddComment(cg)
709 }
710 }
711 // uncomment to only allow one emit per top-level
712 // allowEmit = false
713 }
714 list = append(list, d)
715 }
716 return
717}
718func (p *parser) parseField(allowEmit bool) (decl ast.Decl) {
719 if p.trace {
720 defer un(trace(p, "Field"))
721 }
722
723 c := p.openComments()
724 defer func() { c.closeNode(p, decl) }()
725
726 pos := p.pos
727
728 this := &ast.Field{Label: nil}
729 m := this
730
731 for i := 0; ; i++ {
732 tok := p.tok
733
734 expr, ok := p.parseLabel(m)
735
736 if !ok {
737 if !allowEmit {
738 p.error(pos, "expected label, found "+tok.String())
739 }
740 if expr == nil {
741 expr = p.parseExpr()
742 }
743 e := &ast.EmitDecl{Expr: expr}
744 if p.atComma("file", token.RBRACE) {
745 p.next()
746 }
747 return e
748 }
749
750 if i == 0 && tok == token.IDENT {
751 ident := expr.(*ast.Ident)
752 switch p.tok {
753 case token.BIND:
754 pos := p.pos
755 p.expect(token.BIND)
756 ref := p.parseRHS()
757 if p.atComma("struct literal", token.RBRACE) { // TODO: may be EOF
758 p.next()
759 }
760 return &ast.Alias{Ident: ident, Equal: pos, Expr: ref}
761
762 case token.LPAREN:
763 var value ast.Expr
764 if p.mode&parseLambdasMode != 0 {
765 c.pos = 2
766 // TODO: Only allow LambdaExpr after non-quoted identifier.
767 value = p.parseOperand()
768 if _, ok := unparen(value).(*ast.LambdaExpr); !ok {
769 p.error(value.Pos(), "expected lambda expression")
770 }
771 }
772 if p.atComma("struct literal", token.RBRACE) { // TODO: may be EOF
773 p.next()
774 }
775 return &ast.Field{Label: ident, Value: value}
776 }
777 }
778
779 if p.tok == token.COLON {
780 break
781 }
782
783 switch p.tok {
784 default:
785 if !allowEmit || p.tok != token.COMMA {
786 p.errorExpected(p.pos, "label or ':'")
787 }
788 switch tok {
789 case token.IDENT, token.LBRACK, token.STRING, token.INTERPOLATION, token.NULL, token.TRUE, token.FALSE:
790 if p.tok == token.COMMA {
791 p.expectComma()
792 return &ast.EmitDecl{Expr: expr}
793 }
794 }
795 return &ast.BadDecl{From: pos, To: p.pos}
796
797 case token.IDENT, token.STRING, token.LSS, token.INTERPOLATION, token.LBRACK:
798 field := &ast.Field{}
799 m.Value = &ast.StructLit{Elts: []ast.Decl{field}}
800 m = field
801 }
802
803 allowEmit = false
804 }
805
806 this.Colon = p.pos
807 p.expect(token.COLON)
808 m.Value = p.parseRHS()
809
810 decl = this
811 var arrow token.Pos
812 switch p.tok {
813 case token.ARROW:
814 arrow = p.expect(token.ARROW)
815 fallthrough
816
817 case token.FOR, token.IF:
818 clauses := p.parseComprehensionClauses()
819 return &ast.ComprehensionDecl{
820 Field: this,
821 Select: arrow,
822 Clauses: clauses,
823 }
824 }
825
826 if p.atComma("struct literal", token.RBRACE) { // TODO: may be EOF
827 p.next()
828 }
829
830 return decl
831}
832
833func (p *parser) parseLabel(f *ast.Field) (expr ast.Expr, ok bool) {
834 switch p.tok {
835 case token.IDENT:
836 ident := p.parseIdent()
837 f.Label = ident
838 expr = ident
839
840 case token.STRING:
841 // JSON compatibility.
842
843 expr = p.parseOperand()
844 f.Label = expr.(ast.Label)
845
846 case token.INTERPOLATION:
847 expr = p.parseInterpolation()
848 f.Label = expr.(ast.Label)
849
850 case token.NULL, token.TRUE, token.FALSE:
851 // Keywords that represent operands.
852
853 // Allowing keywords to be used as a labels should not interfere with
854 // generating good errors: any keyword can only appear on the RHS of a
855 // field (after a ':'), whereas labels always appear on the LHS.
856 ident := &ast.BasicLit{
857 Kind: p.tok,
858 ValuePos: p.pos,
859 Value: p.lit,
860 }
861 p.next()
862 f.Label = ident
863 expr = ident
864
865 case token.IF, token.FOR, token.IN, token.LET:
866 // Keywords representing clauses.
867 f.Label = &ast.Ident{
868 NamePos: p.pos,
869 Name: p.lit,
870 }
871 p.next()
872
873 case token.LSS: // element templates
874 pos := p.pos
875 c := p.openComments()
876 p.next()
877 ident := p.parseIdent()
878 gtr := p.pos
879 if p.tok != token.GTR {
880 p.expect(token.GTR)
881 }
882 p.next()
883 label := &ast.TemplateLabel{Langle: pos, Ident: ident, Rangle: gtr}
884 c.closeNode(p, label)
885 f.Label = label
886
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +0100887 default:
888 return expr, false
889 }
890 return expr, true
891}
892
893func (p *parser) parseStruct() (expr ast.Expr) {
894 c := p.openComments()
895 defer func() { c.closeNode(p, expr) }()
896
897 lbrace := p.expect(token.LBRACE)
898
899 if p.trace {
900 defer un(trace(p, "StructLit"))
901 }
902
903 elts := p.parseStructBody()
904 rbrace := p.expectClosing(token.RBRACE, "struct literal")
905 return &ast.StructLit{
906 Lbrace: lbrace,
907 Elts: elts,
908 Rbrace: rbrace,
909 }
910}
911
912func (p *parser) parseStructBody() []ast.Decl {
913 if p.trace {
914 defer un(trace(p, "StructBody"))
915 }
916
917 p.exprLev++
918 var elts []ast.Decl
919 if p.tok != token.RBRACE {
920 elts = p.parseFieldList(false)
921 }
922 p.exprLev--
923
924 return elts
925}
926
927func isClauseStart(tok token.Token) bool {
928 return tok == token.FOR || tok == token.IF // || tok == LET
929}
930
931func (p *parser) parseComprehensionClauses() (clauses []ast.Clause) {
932 // TODO: reuse Template spec, which is possible if it doesn't check the
933 // first is an identifier.
934 for {
935 if p.tok == token.COMMA {
936 p.next()
937 }
938 switch p.tok {
939 case token.FOR:
940 c := p.openComments()
941 forPos := p.expect(token.FOR)
942 var key, value *ast.Ident
943 var colon token.Pos
944 value = p.parseIdent()
945 if p.tok == token.COMMA {
946 colon = p.expect(token.COMMA)
947 key = value
948 value = p.parseIdent()
949 }
950 c.pos = 4
951 // params := p.parseParams(nil, ARROW)
952 clauses = append(clauses, c.closeClause(p, &ast.ForClause{
953 For: forPos,
954 Key: key,
955 Colon: colon,
956 Value: value,
957 In: p.expect(token.IN),
958 Source: p.parseExpr(),
959 }))
960
961 case token.IF:
962 c := p.openComments()
963 clauses = append(clauses, c.closeClause(p, &ast.IfClause{
964 If: p.expect(token.IF),
965 Condition: p.parseExpr(),
966 }))
967
968 // TODO: case LET:
969 default:
970 return clauses
971 }
972 }
973}
974
975func (p *parser) parseList() (expr ast.Expr) {
976 c := p.openComments()
977 defer func() { c.closeNode(p, expr) }()
978
979 lbrack := p.expect(token.LBRACK)
980
981 if p.trace {
982 defer un(trace(p, "ListLiteral"))
983 }
984
985 elts := p.parseListElements()
986
987 if clauses := p.parseComprehensionClauses(); clauses != nil {
988 var expr ast.Expr
989 if len(elts) != 1 {
990 p.error(lbrack+1, "list comprehension must have exactly one element")
991 }
992 if len(elts) > 0 {
993 expr = elts[0]
994 }
995 rbrack := p.expectClosing(token.RBRACK, "list comprehension")
996
997 return &ast.ListComprehension{
998 Lbrack: lbrack,
999 Expr: expr,
1000 Clauses: clauses,
1001 Rbrack: rbrack,
1002 }
1003 }
1004
1005 ellipsis := token.NoPos
1006 typ := ast.Expr(nil)
1007 if p.tok == token.ELLIPSIS {
1008 ellipsis = p.pos
1009 p.next()
1010 if p.tok != token.COMMA && p.tok != token.RBRACK {
1011 typ = p.parseRHS()
1012 }
1013 if p.atComma("list literal", token.RBRACK) {
1014 p.next()
1015 }
1016 }
1017
1018 rbrack := p.expectClosing(token.RBRACK, "list literal")
1019 return &ast.ListLit{
1020 Lbrack: lbrack,
1021 Elts: elts,
1022 Ellipsis: ellipsis,
1023 Type: typ,
1024 Rbrack: rbrack}
1025}
1026
1027func (p *parser) parseListElements() (list []ast.Expr) {
1028 if p.trace {
1029 defer un(trace(p, "ListElements"))
1030 }
1031 p.openList()
1032 defer p.closeList()
1033
1034 for p.tok != token.RBRACK && p.tok != token.ELLIPSIS && p.tok != token.EOF {
1035 list = append(list, p.parseListElement())
1036 // Enforce there is an explicit comma. We could also allow the
1037 // omission of commas in lists, but this gives rise to some ambiguities
1038 // with list comprehensions.
1039 if p.tok == token.COMMA && p.lit != "," {
1040 p.next()
1041 // Allow missing comma for last element, though, to be compliant
1042 // with JSON.
1043 if p.tok == token.RBRACK || p.tok == token.FOR || p.tok == token.IF {
1044 break
1045 }
1046 p.error(p.pos, "missing ',' before newline in list literal")
1047 } else if !p.atComma("list literal", token.RBRACK, token.FOR, token.IF) {
1048 break
1049 }
1050 p.next()
1051 }
1052
1053 return
1054}
1055
1056func (p *parser) parseListElement() (expr ast.Expr) {
1057 if p.trace {
1058 defer un(trace(p, "ListElement"))
1059 }
1060 c := p.openComments()
1061 defer func() { c.closeNode(p, expr) }()
1062
1063 e := p.parseRHS()
1064 switch p.tok {
1065 case token.ELLIPSIS:
1066 return &ast.Ellipsis{Ellipsis: p.expect(token.ELLIPSIS), Elt: e}
1067 }
1068 return e
1069}
1070
1071// checkExpr checks that x is an expression (and not a type).
1072func (p *parser) checkExpr(x ast.Expr) ast.Expr {
1073 switch unparen(x).(type) {
1074 case *ast.BadExpr:
1075 case *ast.BottomLit:
1076 case *ast.Ident:
1077 case *ast.BasicLit:
1078 case *ast.Interpolation:
1079 case *ast.StructLit:
1080 case *ast.ListLit:
1081 case *ast.LambdaExpr:
1082 case *ast.ListComprehension:
1083 case *ast.ParenExpr:
1084 panic("unreachable")
1085 case *ast.SelectorExpr:
1086 case *ast.IndexExpr:
1087 case *ast.SliceExpr:
1088 case *ast.CallExpr:
1089 case *ast.UnaryExpr:
1090 case *ast.BinaryExpr:
1091 default:
1092 // all other nodes are not proper expressions
1093 p.errorExpected(x.Pos(), "expression")
1094 x = &ast.BadExpr{
1095 From: x.Pos(), To: p.safePos(x.End()),
1096 }
1097 }
1098 return x
1099}
1100
1101// If x is of the form (T), unparen returns unparen(T), otherwise it returns x.
1102func unparen(x ast.Expr) ast.Expr {
1103 if p, isParen := x.(*ast.ParenExpr); isParen {
1104 x = unparen(p.X)
1105 }
1106 return x
1107}
1108
1109// If lhs is set and the result is an identifier, it is not resolved.
1110func (p *parser) parsePrimaryExpr() ast.Expr {
1111 if p.trace {
1112 defer un(trace(p, "PrimaryExpr"))
1113 }
1114
1115 x := p.parseOperand()
1116
1117L:
1118 for {
1119 switch p.tok {
1120 case token.PERIOD:
1121 c := p.openComments()
1122 c.pos = 1
1123 p.next()
1124 switch p.tok {
1125 case token.IDENT:
1126 x = &ast.SelectorExpr{
1127 X: p.checkExpr(x),
1128 Sel: p.parseIdent(),
1129 }
1130 default:
1131 pos := p.pos
1132 p.errorExpected(pos, "selector")
1133 p.next() // make progress
1134 x = &ast.SelectorExpr{X: x, Sel: &ast.Ident{NamePos: pos, Name: "_"}}
1135 }
1136 c.closeNode(p, x)
1137 case token.LBRACK:
1138 x = p.parseIndexOrSlice(p.checkExpr(x))
1139 case token.LPAREN:
1140 x = p.parseCallOrConversion(p.checkExpr(x))
1141 default:
1142 break L
1143 }
1144 }
1145
1146 return x
1147}
1148
1149// If lhs is set and the result is an identifier, it is not resolved.
1150func (p *parser) parseUnaryExpr() ast.Expr {
1151 if p.trace {
1152 defer un(trace(p, "UnaryExpr"))
1153 }
1154
1155 switch p.tok {
1156 case token.ADD, token.SUB, token.NOT:
1157 pos, op := p.pos, p.tok
1158 c := p.openComments()
1159 p.next()
1160 return c.closeExpr(p, &ast.UnaryExpr{
1161 OpPos: pos,
1162 Op: op,
1163 X: p.checkExpr(p.parseUnaryExpr()),
1164 })
1165 }
1166
1167 return p.parsePrimaryExpr()
1168}
1169
1170func (p *parser) tokPrec() (token.Token, int) {
1171 tok := p.tok
1172 if tok == token.IDENT {
1173 switch p.lit {
1174 case "quo":
1175 return token.IQUO, 7
1176 case "rem":
1177 return token.IREM, 7
1178 case "div":
1179 return token.IDIV, 7
1180 case "mod":
1181 return token.IMOD, 7
1182 default:
1183 return tok, 0
1184 }
1185 }
1186 return tok, tok.Precedence()
1187}
1188
1189// If lhs is set and the result is an identifier, it is not resolved.
1190func (p *parser) parseBinaryExpr(prec1 int) ast.Expr {
1191 if p.trace {
1192 defer un(trace(p, "BinaryExpr"))
1193 }
1194 p.openList()
1195 defer p.closeList()
1196
1197 x := p.parseUnaryExpr()
1198
1199 for {
1200 op, prec := p.tokPrec()
1201 if prec < prec1 {
1202 return x
1203 }
1204 c := p.openComments()
1205 c.pos = 1
1206 pos := p.expect(p.tok)
1207 x = c.closeExpr(p, &ast.BinaryExpr{
1208 X: p.checkExpr(x),
1209 OpPos: pos,
1210 Op: op,
1211 Y: p.checkExpr(p.parseBinaryExpr(prec + 1))})
1212 }
1213}
1214
1215func (p *parser) parseInterpolation() (expr ast.Expr) {
1216 c := p.openComments()
1217 defer func() { c.closeNode(p, expr) }()
1218
1219 p.openList()
1220 defer p.closeList()
1221
1222 cc := p.openComments()
1223
1224 lit := p.lit
Marcel van Lohuizen76b92b52018-12-16 10:47:03 +01001225 pos := p.pos
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +01001226 p.next()
Marcel van Lohuizen76b92b52018-12-16 10:47:03 +01001227 last := &ast.BasicLit{ValuePos: pos, Kind: token.STRING, Value: lit}
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +01001228 exprs := []ast.Expr{last}
1229
1230 quote := rune(lit[0])
1231 numQuotes := 1
1232 if len(lit) > 2 && lit[0] == lit[1] {
1233 numQuotes = 3
1234 }
1235
1236 for p.tok == token.LPAREN {
1237 c.pos = 1
1238 p.expect(token.LPAREN)
1239 cc.closeExpr(p, last)
1240
1241 exprs = append(exprs, p.parseExpr())
1242
1243 cc = p.openComments()
1244 if p.tok != token.RPAREN {
1245 p.error(p.pos, "expected ')' for string interpolation")
1246 }
1247 lit = p.scanner.ResumeInterpolation(quote, numQuotes)
Marcel van Lohuizen76b92b52018-12-16 10:47:03 +01001248 pos = p.pos
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +01001249 p.next()
1250 last = &ast.BasicLit{
Marcel van Lohuizen76b92b52018-12-16 10:47:03 +01001251 ValuePos: pos,
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +01001252 Kind: token.STRING,
1253 Value: lit,
1254 }
1255 exprs = append(exprs, last)
1256 }
1257 cc.closeExpr(p, last)
1258 return &ast.Interpolation{Elts: exprs}
1259}
1260
1261// Callers must check the result (using checkExpr), depending on context.
1262func (p *parser) parseExpr() ast.Expr {
1263 if p.trace {
1264 defer un(trace(p, "Expression"))
1265 }
1266
1267 return p.parseBinaryExpr(token.LowestPrec + 1)
1268}
1269
1270func (p *parser) parseRHS() ast.Expr {
1271 x := p.checkExpr(p.parseExpr())
1272 return x
1273}
1274
1275func (p *parser) parseCallExpr(callType string) *ast.CallExpr {
1276 x := p.parseRHS() // could be a conversion: (some type)(x)
1277 if call, isCall := x.(*ast.CallExpr); isCall {
1278 return call
1279 }
1280 if _, isBad := x.(*ast.BadExpr); !isBad {
1281 // only report error if it's a new one
1282 p.error(p.safePos(x.End()), fmt.Sprintf("function must be invoked in %s statement", callType))
1283 }
1284 return nil
1285}
1286
1287// ----------------------------------------------------------------------------
1288// Declarations
1289
1290type parseSpecFunction func(iota int) *ast.ImportSpec
1291
1292func isValidImport(lit string) bool {
1293 const illegalChars = `!"#$%&'()*,:;<=>?[\]^{|}` + "`\uFFFD"
1294 s, _ := strconv.Unquote(lit) // go/scanner returns a legal string literal
1295 for _, r := range s {
1296 if !unicode.IsGraphic(r) || unicode.IsSpace(r) || strings.ContainsRune(illegalChars, r) {
1297 return false
1298 }
1299 }
1300 return s != ""
1301}
1302
1303func (p *parser) parseImportSpec(_ int) *ast.ImportSpec {
1304 if p.trace {
1305 defer un(trace(p, "ImportSpec"))
1306 }
1307
1308 c := p.openComments()
1309
1310 var ident *ast.Ident
1311 switch p.tok {
1312 case token.PERIOD:
1313 ident = &ast.Ident{NamePos: p.pos, Name: "."}
1314 p.next()
1315 case token.IDENT:
1316 ident = p.parseIdent()
1317 }
1318
1319 pos := p.pos
1320 var path string
1321 if p.tok == token.STRING {
1322 path = p.lit
1323 if !isValidImport(path) {
1324 p.error(pos, "invalid import path: "+path)
1325 }
1326 p.next()
1327 p.expectComma() // call before accessing p.linecomment
1328 } else {
1329 p.expect(token.STRING) // use expect() error handling
1330 if p.tok == token.COMMA {
1331 p.expectComma() // call before accessing p.linecomment
1332 }
1333 }
1334 // collect imports
1335 spec := &ast.ImportSpec{
1336 Name: ident,
1337 Path: &ast.BasicLit{ValuePos: pos, Kind: token.STRING, Value: path},
1338 }
1339 c.closeNode(p, spec)
1340 p.imports = append(p.imports, spec)
1341
1342 return spec
1343}
1344
1345func (p *parser) parseImports() *ast.ImportDecl {
1346 if p.trace {
1347 defer un(trace(p, "Imports"))
1348 }
1349 c := p.openComments()
1350
1351 ident := p.parseIdent()
1352 var lparen, rparen token.Pos
1353 var list []*ast.ImportSpec
1354 if p.tok == token.LPAREN {
1355 lparen = p.pos
1356 p.next()
1357 p.openList()
1358 for iota := 0; p.tok != token.RPAREN && p.tok != token.EOF; iota++ {
1359 list = append(list, p.parseImportSpec(iota))
1360 }
1361 p.closeList()
1362 rparen = p.expect(token.RPAREN)
1363 p.expectComma()
1364 } else {
1365 list = append(list, p.parseImportSpec(0))
1366 }
1367
1368 d := &ast.ImportDecl{
1369 Import: ident.Pos(),
1370 Lparen: lparen,
1371 Specs: list,
1372 Rparen: rparen,
1373 }
1374 c.closeNode(p, d)
1375 return d
1376}
1377
1378// ----------------------------------------------------------------------------
1379// Source files
1380
1381func (p *parser) parseFile() *ast.File {
1382 if p.trace {
1383 defer un(trace(p, "File"))
1384 }
1385
1386 c := p.comments
1387
1388 // Don't bother parsing the rest if we had errors scanning the first
1389 // Likely not a Go source file at all.
1390 if p.errors.Len() != 0 {
1391 return nil
1392 }
1393
1394 // The package clause is not a declaration: it does not appear in any
1395 // scope.
1396 pos := p.pos
1397 var name *ast.Ident
1398 if p.tok == token.IDENT && p.lit == "package" {
1399 p.expect(token.IDENT)
1400 name = p.parseIdent()
1401 if name.Name == "_" && p.mode&declarationErrorsMode != 0 {
1402 p.error(p.pos, "invalid package name _")
1403 }
1404 p.expectComma()
1405 } else {
1406 pos = token.NoPos
1407 }
1408 c.pos = 3
1409
1410 p.openList()
1411 var decls []ast.Decl
1412 if p.mode&packageClauseOnlyMode == 0 {
1413 // import decls
1414 for p.tok == token.IDENT && p.lit == "import" {
1415 decls = append(decls, p.parseImports())
1416 }
1417
1418 if p.mode&importsOnlyMode == 0 {
1419 // rest of package decls
1420 // TODO: loop and allow multiple expressions.
1421 decls = append(decls, p.parseFieldList(true)...)
1422 p.expect(token.EOF)
1423 }
1424 }
1425 p.closeList()
1426
1427 f := &ast.File{
1428 Package: pos,
1429 Name: name,
1430 Imports: p.imports,
1431 Decls: decls,
1432 }
1433 c.closeNode(p, f)
1434 return f
1435}