blob: f6ed64b169d0c89d86805a7bf96fafad00c1164d [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()
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +0100545 p.exprLev++
546 p.openList()
547 x := p.parseRHS() // types may be parenthesized: (some type)
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +0100548 p.closeList()
549 p.exprLev--
550 rparen := p.expect(token.RPAREN)
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +0100551 return &ast.ParenExpr{
552 Lparen: lparen,
553 X: x,
554 Rparen: rparen}
555 }
556
557 // we have an error
558 c := p.openComments()
559 pos := p.pos
560 p.errorExpected(pos, "operand")
561 syncExpr(p)
562 return c.closeExpr(p, &ast.BadExpr{From: pos, To: p.pos})
563}
564
565func (p *parser) parseParams(ident *ast.Ident, follow token.Token) (params []*ast.Field) {
566 for {
567 c := p.openComments()
568 if ident == nil {
569 ident = p.parseIdent()
570 }
571 m := &ast.Field{Label: ident}
572 if p.tok == token.COLON {
573 m.Colon = p.expect(token.COLON)
574 m.Value = p.parseRHS()
575 }
576 hasComma := p.tok == token.COMMA
577 if hasComma {
578 p.expect(token.COMMA)
579 }
580 c.closeNode(p, m)
581 params = append(params, m)
582 if !hasComma || p.tok == follow || p.tok == token.EOF {
583 break
584 }
585 ident = nil
586 }
587 return params
588}
589
590func (p *parser) parseIndexOrSlice(x ast.Expr) (expr ast.Expr) {
591 if p.trace {
592 defer un(trace(p, "IndexOrSlice"))
593 }
594
595 c := p.openComments()
596 defer func() { c.closeNode(p, expr) }()
597 c.pos = 1
598
599 const N = 2
600 lbrack := p.expect(token.LBRACK)
601
602 p.exprLev++
603 var index [N]ast.Expr
604 var colons [N - 1]token.Pos
605 if p.tok != token.COLON {
606 index[0] = p.parseRHS()
607 }
608 nColons := 0
609 for p.tok == token.COLON && nColons < len(colons) {
610 colons[nColons] = p.pos
611 nColons++
612 p.next()
613 if p.tok != token.COLON && p.tok != token.RBRACK && p.tok != token.EOF {
614 index[nColons] = p.parseRHS()
615 }
616 }
617 p.exprLev--
618 rbrack := p.expect(token.RBRACK)
619
620 if nColons > 0 {
621 return &ast.SliceExpr{
622 X: x,
623 Lbrack: lbrack,
624 Low: index[0],
625 High: index[1],
626 Rbrack: rbrack}
627 }
628
629 return &ast.IndexExpr{
630 X: x,
631 Lbrack: lbrack,
632 Index: index[0],
633 Rbrack: rbrack}
634}
635
636func (p *parser) parseCallOrConversion(fun ast.Expr) (expr *ast.CallExpr) {
637 if p.trace {
638 defer un(trace(p, "CallOrConversion"))
639 }
640 c := p.openComments()
641 defer func() { c.closeNode(p, expr) }()
642
643 lparen := p.expect(token.LPAREN)
644 p.exprLev++
645 var list []ast.Expr
646 for p.tok != token.RPAREN && p.tok != token.EOF {
647 list = append(list, p.parseRHS()) // builtins may expect a type: make(some type, ...)
648 if !p.atComma("argument list", token.RPAREN) {
649 break
650 }
651 p.next()
652 }
653 p.exprLev--
654 rparen := p.expectClosing(token.RPAREN, "argument list")
655
656 return &ast.CallExpr{
657 Fun: fun,
658 Lparen: lparen,
659 Args: list,
660 Rparen: rparen}
661}
662
663func (p *parser) parseFieldList(allowEmit bool) (list []ast.Decl) {
664 if p.trace {
665 defer un(trace(p, "FieldList"))
666 }
667 origEmit := allowEmit
668 p.openList()
669 defer p.closeList()
670
671 for p.tok != token.RBRACE && p.tok != token.EOF {
672 d := p.parseField(allowEmit)
673 if e, ok := d.(*ast.EmitDecl); ok {
674 if origEmit && !allowEmit {
675 p.error(p.pos, "only one emit allowed at top level")
676 }
677 if !origEmit || !allowEmit {
678 d = &ast.BadDecl{From: e.Pos(), To: e.End()}
679 for _, cg := range e.Comments() {
680 d.AddComment(cg)
681 }
682 }
683 // uncomment to only allow one emit per top-level
684 // allowEmit = false
685 }
686 list = append(list, d)
687 }
688 return
689}
690func (p *parser) parseField(allowEmit bool) (decl ast.Decl) {
691 if p.trace {
692 defer un(trace(p, "Field"))
693 }
694
695 c := p.openComments()
696 defer func() { c.closeNode(p, decl) }()
697
698 pos := p.pos
699
700 this := &ast.Field{Label: nil}
701 m := this
702
703 for i := 0; ; i++ {
704 tok := p.tok
705
706 expr, ok := p.parseLabel(m)
707
708 if !ok {
709 if !allowEmit {
710 p.error(pos, "expected label, found "+tok.String())
711 }
712 if expr == nil {
713 expr = p.parseExpr()
714 }
715 e := &ast.EmitDecl{Expr: expr}
716 if p.atComma("file", token.RBRACE) {
717 p.next()
718 }
719 return e
720 }
721
722 if i == 0 && tok == token.IDENT {
723 ident := expr.(*ast.Ident)
724 switch p.tok {
725 case token.BIND:
726 pos := p.pos
727 p.expect(token.BIND)
728 ref := p.parseRHS()
729 if p.atComma("struct literal", token.RBRACE) { // TODO: may be EOF
730 p.next()
731 }
732 return &ast.Alias{Ident: ident, Equal: pos, Expr: ref}
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +0100733 }
734 }
735
736 if p.tok == token.COLON {
737 break
738 }
739
740 switch p.tok {
741 default:
742 if !allowEmit || p.tok != token.COMMA {
743 p.errorExpected(p.pos, "label or ':'")
744 }
745 switch tok {
746 case token.IDENT, token.LBRACK, token.STRING, token.INTERPOLATION, token.NULL, token.TRUE, token.FALSE:
747 if p.tok == token.COMMA {
748 p.expectComma()
749 return &ast.EmitDecl{Expr: expr}
750 }
751 }
752 return &ast.BadDecl{From: pos, To: p.pos}
753
754 case token.IDENT, token.STRING, token.LSS, token.INTERPOLATION, token.LBRACK:
755 field := &ast.Field{}
756 m.Value = &ast.StructLit{Elts: []ast.Decl{field}}
757 m = field
758 }
759
760 allowEmit = false
761 }
762
763 this.Colon = p.pos
764 p.expect(token.COLON)
765 m.Value = p.parseRHS()
766
767 decl = this
768 var arrow token.Pos
769 switch p.tok {
770 case token.ARROW:
771 arrow = p.expect(token.ARROW)
772 fallthrough
773
774 case token.FOR, token.IF:
775 clauses := p.parseComprehensionClauses()
776 return &ast.ComprehensionDecl{
777 Field: this,
778 Select: arrow,
779 Clauses: clauses,
780 }
781 }
782
783 if p.atComma("struct literal", token.RBRACE) { // TODO: may be EOF
784 p.next()
785 }
786
787 return decl
788}
789
790func (p *parser) parseLabel(f *ast.Field) (expr ast.Expr, ok bool) {
791 switch p.tok {
792 case token.IDENT:
793 ident := p.parseIdent()
794 f.Label = ident
795 expr = ident
796
797 case token.STRING:
798 // JSON compatibility.
799
800 expr = p.parseOperand()
801 f.Label = expr.(ast.Label)
802
803 case token.INTERPOLATION:
804 expr = p.parseInterpolation()
805 f.Label = expr.(ast.Label)
806
807 case token.NULL, token.TRUE, token.FALSE:
808 // Keywords that represent operands.
809
810 // Allowing keywords to be used as a labels should not interfere with
811 // generating good errors: any keyword can only appear on the RHS of a
812 // field (after a ':'), whereas labels always appear on the LHS.
813 ident := &ast.BasicLit{
814 Kind: p.tok,
815 ValuePos: p.pos,
816 Value: p.lit,
817 }
818 p.next()
819 f.Label = ident
820 expr = ident
821
822 case token.IF, token.FOR, token.IN, token.LET:
823 // Keywords representing clauses.
824 f.Label = &ast.Ident{
825 NamePos: p.pos,
826 Name: p.lit,
827 }
828 p.next()
829
830 case token.LSS: // element templates
831 pos := p.pos
832 c := p.openComments()
833 p.next()
834 ident := p.parseIdent()
835 gtr := p.pos
836 if p.tok != token.GTR {
837 p.expect(token.GTR)
838 }
839 p.next()
840 label := &ast.TemplateLabel{Langle: pos, Ident: ident, Rangle: gtr}
841 c.closeNode(p, label)
842 f.Label = label
843
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +0100844 default:
845 return expr, false
846 }
847 return expr, true
848}
849
850func (p *parser) parseStruct() (expr ast.Expr) {
851 c := p.openComments()
852 defer func() { c.closeNode(p, expr) }()
853
854 lbrace := p.expect(token.LBRACE)
855
856 if p.trace {
857 defer un(trace(p, "StructLit"))
858 }
859
860 elts := p.parseStructBody()
861 rbrace := p.expectClosing(token.RBRACE, "struct literal")
862 return &ast.StructLit{
863 Lbrace: lbrace,
864 Elts: elts,
865 Rbrace: rbrace,
866 }
867}
868
869func (p *parser) parseStructBody() []ast.Decl {
870 if p.trace {
871 defer un(trace(p, "StructBody"))
872 }
873
874 p.exprLev++
875 var elts []ast.Decl
876 if p.tok != token.RBRACE {
877 elts = p.parseFieldList(false)
878 }
879 p.exprLev--
880
881 return elts
882}
883
884func isClauseStart(tok token.Token) bool {
885 return tok == token.FOR || tok == token.IF // || tok == LET
886}
887
888func (p *parser) parseComprehensionClauses() (clauses []ast.Clause) {
889 // TODO: reuse Template spec, which is possible if it doesn't check the
890 // first is an identifier.
891 for {
892 if p.tok == token.COMMA {
893 p.next()
894 }
895 switch p.tok {
896 case token.FOR:
897 c := p.openComments()
898 forPos := p.expect(token.FOR)
899 var key, value *ast.Ident
900 var colon token.Pos
901 value = p.parseIdent()
902 if p.tok == token.COMMA {
903 colon = p.expect(token.COMMA)
904 key = value
905 value = p.parseIdent()
906 }
907 c.pos = 4
908 // params := p.parseParams(nil, ARROW)
909 clauses = append(clauses, c.closeClause(p, &ast.ForClause{
910 For: forPos,
911 Key: key,
912 Colon: colon,
913 Value: value,
914 In: p.expect(token.IN),
915 Source: p.parseExpr(),
916 }))
917
918 case token.IF:
919 c := p.openComments()
920 clauses = append(clauses, c.closeClause(p, &ast.IfClause{
921 If: p.expect(token.IF),
922 Condition: p.parseExpr(),
923 }))
924
925 // TODO: case LET:
926 default:
927 return clauses
928 }
929 }
930}
931
932func (p *parser) parseList() (expr ast.Expr) {
933 c := p.openComments()
934 defer func() { c.closeNode(p, expr) }()
935
936 lbrack := p.expect(token.LBRACK)
937
938 if p.trace {
939 defer un(trace(p, "ListLiteral"))
940 }
941
942 elts := p.parseListElements()
943
944 if clauses := p.parseComprehensionClauses(); clauses != nil {
945 var expr ast.Expr
946 if len(elts) != 1 {
947 p.error(lbrack+1, "list comprehension must have exactly one element")
948 }
949 if len(elts) > 0 {
950 expr = elts[0]
951 }
952 rbrack := p.expectClosing(token.RBRACK, "list comprehension")
953
954 return &ast.ListComprehension{
955 Lbrack: lbrack,
956 Expr: expr,
957 Clauses: clauses,
958 Rbrack: rbrack,
959 }
960 }
961
962 ellipsis := token.NoPos
963 typ := ast.Expr(nil)
964 if p.tok == token.ELLIPSIS {
965 ellipsis = p.pos
966 p.next()
967 if p.tok != token.COMMA && p.tok != token.RBRACK {
968 typ = p.parseRHS()
969 }
970 if p.atComma("list literal", token.RBRACK) {
971 p.next()
972 }
973 }
974
975 rbrack := p.expectClosing(token.RBRACK, "list literal")
976 return &ast.ListLit{
977 Lbrack: lbrack,
978 Elts: elts,
979 Ellipsis: ellipsis,
980 Type: typ,
981 Rbrack: rbrack}
982}
983
984func (p *parser) parseListElements() (list []ast.Expr) {
985 if p.trace {
986 defer un(trace(p, "ListElements"))
987 }
988 p.openList()
989 defer p.closeList()
990
991 for p.tok != token.RBRACK && p.tok != token.ELLIPSIS && p.tok != token.EOF {
992 list = append(list, p.parseListElement())
993 // Enforce there is an explicit comma. We could also allow the
994 // omission of commas in lists, but this gives rise to some ambiguities
995 // with list comprehensions.
996 if p.tok == token.COMMA && p.lit != "," {
997 p.next()
998 // Allow missing comma for last element, though, to be compliant
999 // with JSON.
1000 if p.tok == token.RBRACK || p.tok == token.FOR || p.tok == token.IF {
1001 break
1002 }
1003 p.error(p.pos, "missing ',' before newline in list literal")
1004 } else if !p.atComma("list literal", token.RBRACK, token.FOR, token.IF) {
1005 break
1006 }
1007 p.next()
1008 }
1009
1010 return
1011}
1012
1013func (p *parser) parseListElement() (expr ast.Expr) {
1014 if p.trace {
1015 defer un(trace(p, "ListElement"))
1016 }
1017 c := p.openComments()
1018 defer func() { c.closeNode(p, expr) }()
1019
1020 e := p.parseRHS()
1021 switch p.tok {
1022 case token.ELLIPSIS:
1023 return &ast.Ellipsis{Ellipsis: p.expect(token.ELLIPSIS), Elt: e}
1024 }
1025 return e
1026}
1027
1028// checkExpr checks that x is an expression (and not a type).
1029func (p *parser) checkExpr(x ast.Expr) ast.Expr {
1030 switch unparen(x).(type) {
1031 case *ast.BadExpr:
1032 case *ast.BottomLit:
1033 case *ast.Ident:
1034 case *ast.BasicLit:
1035 case *ast.Interpolation:
1036 case *ast.StructLit:
1037 case *ast.ListLit:
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +01001038 case *ast.ListComprehension:
1039 case *ast.ParenExpr:
1040 panic("unreachable")
1041 case *ast.SelectorExpr:
1042 case *ast.IndexExpr:
1043 case *ast.SliceExpr:
1044 case *ast.CallExpr:
1045 case *ast.UnaryExpr:
1046 case *ast.BinaryExpr:
1047 default:
1048 // all other nodes are not proper expressions
1049 p.errorExpected(x.Pos(), "expression")
1050 x = &ast.BadExpr{
1051 From: x.Pos(), To: p.safePos(x.End()),
1052 }
1053 }
1054 return x
1055}
1056
1057// If x is of the form (T), unparen returns unparen(T), otherwise it returns x.
1058func unparen(x ast.Expr) ast.Expr {
1059 if p, isParen := x.(*ast.ParenExpr); isParen {
1060 x = unparen(p.X)
1061 }
1062 return x
1063}
1064
1065// If lhs is set and the result is an identifier, it is not resolved.
1066func (p *parser) parsePrimaryExpr() ast.Expr {
1067 if p.trace {
1068 defer un(trace(p, "PrimaryExpr"))
1069 }
1070
1071 x := p.parseOperand()
1072
1073L:
1074 for {
1075 switch p.tok {
1076 case token.PERIOD:
1077 c := p.openComments()
1078 c.pos = 1
1079 p.next()
1080 switch p.tok {
1081 case token.IDENT:
1082 x = &ast.SelectorExpr{
1083 X: p.checkExpr(x),
1084 Sel: p.parseIdent(),
1085 }
1086 default:
1087 pos := p.pos
1088 p.errorExpected(pos, "selector")
1089 p.next() // make progress
1090 x = &ast.SelectorExpr{X: x, Sel: &ast.Ident{NamePos: pos, Name: "_"}}
1091 }
1092 c.closeNode(p, x)
1093 case token.LBRACK:
1094 x = p.parseIndexOrSlice(p.checkExpr(x))
1095 case token.LPAREN:
1096 x = p.parseCallOrConversion(p.checkExpr(x))
1097 default:
1098 break L
1099 }
1100 }
1101
1102 return x
1103}
1104
1105// If lhs is set and the result is an identifier, it is not resolved.
1106func (p *parser) parseUnaryExpr() ast.Expr {
1107 if p.trace {
1108 defer un(trace(p, "UnaryExpr"))
1109 }
1110
1111 switch p.tok {
1112 case token.ADD, token.SUB, token.NOT:
1113 pos, op := p.pos, p.tok
1114 c := p.openComments()
1115 p.next()
1116 return c.closeExpr(p, &ast.UnaryExpr{
1117 OpPos: pos,
1118 Op: op,
1119 X: p.checkExpr(p.parseUnaryExpr()),
1120 })
1121 }
1122
1123 return p.parsePrimaryExpr()
1124}
1125
1126func (p *parser) tokPrec() (token.Token, int) {
1127 tok := p.tok
1128 if tok == token.IDENT {
1129 switch p.lit {
1130 case "quo":
1131 return token.IQUO, 7
1132 case "rem":
1133 return token.IREM, 7
1134 case "div":
1135 return token.IDIV, 7
1136 case "mod":
1137 return token.IMOD, 7
1138 default:
1139 return tok, 0
1140 }
1141 }
1142 return tok, tok.Precedence()
1143}
1144
1145// If lhs is set and the result is an identifier, it is not resolved.
1146func (p *parser) parseBinaryExpr(prec1 int) ast.Expr {
1147 if p.trace {
1148 defer un(trace(p, "BinaryExpr"))
1149 }
1150 p.openList()
1151 defer p.closeList()
1152
1153 x := p.parseUnaryExpr()
1154
1155 for {
1156 op, prec := p.tokPrec()
1157 if prec < prec1 {
1158 return x
1159 }
1160 c := p.openComments()
1161 c.pos = 1
1162 pos := p.expect(p.tok)
1163 x = c.closeExpr(p, &ast.BinaryExpr{
1164 X: p.checkExpr(x),
1165 OpPos: pos,
1166 Op: op,
1167 Y: p.checkExpr(p.parseBinaryExpr(prec + 1))})
1168 }
1169}
1170
1171func (p *parser) parseInterpolation() (expr ast.Expr) {
1172 c := p.openComments()
1173 defer func() { c.closeNode(p, expr) }()
1174
1175 p.openList()
1176 defer p.closeList()
1177
1178 cc := p.openComments()
1179
1180 lit := p.lit
Marcel van Lohuizen76b92b52018-12-16 10:47:03 +01001181 pos := p.pos
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +01001182 p.next()
Marcel van Lohuizen76b92b52018-12-16 10:47:03 +01001183 last := &ast.BasicLit{ValuePos: pos, Kind: token.STRING, Value: lit}
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +01001184 exprs := []ast.Expr{last}
1185
1186 quote := rune(lit[0])
1187 numQuotes := 1
1188 if len(lit) > 2 && lit[0] == lit[1] {
1189 numQuotes = 3
1190 }
1191
1192 for p.tok == token.LPAREN {
1193 c.pos = 1
1194 p.expect(token.LPAREN)
1195 cc.closeExpr(p, last)
1196
1197 exprs = append(exprs, p.parseExpr())
1198
1199 cc = p.openComments()
1200 if p.tok != token.RPAREN {
1201 p.error(p.pos, "expected ')' for string interpolation")
1202 }
1203 lit = p.scanner.ResumeInterpolation(quote, numQuotes)
Marcel van Lohuizen76b92b52018-12-16 10:47:03 +01001204 pos = p.pos
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +01001205 p.next()
1206 last = &ast.BasicLit{
Marcel van Lohuizen76b92b52018-12-16 10:47:03 +01001207 ValuePos: pos,
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +01001208 Kind: token.STRING,
1209 Value: lit,
1210 }
1211 exprs = append(exprs, last)
1212 }
1213 cc.closeExpr(p, last)
1214 return &ast.Interpolation{Elts: exprs}
1215}
1216
1217// Callers must check the result (using checkExpr), depending on context.
1218func (p *parser) parseExpr() ast.Expr {
1219 if p.trace {
1220 defer un(trace(p, "Expression"))
1221 }
1222
1223 return p.parseBinaryExpr(token.LowestPrec + 1)
1224}
1225
1226func (p *parser) parseRHS() ast.Expr {
1227 x := p.checkExpr(p.parseExpr())
1228 return x
1229}
1230
1231func (p *parser) parseCallExpr(callType string) *ast.CallExpr {
1232 x := p.parseRHS() // could be a conversion: (some type)(x)
1233 if call, isCall := x.(*ast.CallExpr); isCall {
1234 return call
1235 }
1236 if _, isBad := x.(*ast.BadExpr); !isBad {
1237 // only report error if it's a new one
1238 p.error(p.safePos(x.End()), fmt.Sprintf("function must be invoked in %s statement", callType))
1239 }
1240 return nil
1241}
1242
1243// ----------------------------------------------------------------------------
1244// Declarations
1245
1246type parseSpecFunction func(iota int) *ast.ImportSpec
1247
1248func isValidImport(lit string) bool {
1249 const illegalChars = `!"#$%&'()*,:;<=>?[\]^{|}` + "`\uFFFD"
1250 s, _ := strconv.Unquote(lit) // go/scanner returns a legal string literal
1251 for _, r := range s {
1252 if !unicode.IsGraphic(r) || unicode.IsSpace(r) || strings.ContainsRune(illegalChars, r) {
1253 return false
1254 }
1255 }
1256 return s != ""
1257}
1258
1259func (p *parser) parseImportSpec(_ int) *ast.ImportSpec {
1260 if p.trace {
1261 defer un(trace(p, "ImportSpec"))
1262 }
1263
1264 c := p.openComments()
1265
1266 var ident *ast.Ident
1267 switch p.tok {
1268 case token.PERIOD:
1269 ident = &ast.Ident{NamePos: p.pos, Name: "."}
1270 p.next()
1271 case token.IDENT:
1272 ident = p.parseIdent()
1273 }
1274
1275 pos := p.pos
1276 var path string
1277 if p.tok == token.STRING {
1278 path = p.lit
1279 if !isValidImport(path) {
1280 p.error(pos, "invalid import path: "+path)
1281 }
1282 p.next()
1283 p.expectComma() // call before accessing p.linecomment
1284 } else {
1285 p.expect(token.STRING) // use expect() error handling
1286 if p.tok == token.COMMA {
1287 p.expectComma() // call before accessing p.linecomment
1288 }
1289 }
1290 // collect imports
1291 spec := &ast.ImportSpec{
1292 Name: ident,
1293 Path: &ast.BasicLit{ValuePos: pos, Kind: token.STRING, Value: path},
1294 }
1295 c.closeNode(p, spec)
1296 p.imports = append(p.imports, spec)
1297
1298 return spec
1299}
1300
1301func (p *parser) parseImports() *ast.ImportDecl {
1302 if p.trace {
1303 defer un(trace(p, "Imports"))
1304 }
1305 c := p.openComments()
1306
1307 ident := p.parseIdent()
1308 var lparen, rparen token.Pos
1309 var list []*ast.ImportSpec
1310 if p.tok == token.LPAREN {
1311 lparen = p.pos
1312 p.next()
1313 p.openList()
1314 for iota := 0; p.tok != token.RPAREN && p.tok != token.EOF; iota++ {
1315 list = append(list, p.parseImportSpec(iota))
1316 }
1317 p.closeList()
1318 rparen = p.expect(token.RPAREN)
1319 p.expectComma()
1320 } else {
1321 list = append(list, p.parseImportSpec(0))
1322 }
1323
1324 d := &ast.ImportDecl{
1325 Import: ident.Pos(),
1326 Lparen: lparen,
1327 Specs: list,
1328 Rparen: rparen,
1329 }
1330 c.closeNode(p, d)
1331 return d
1332}
1333
1334// ----------------------------------------------------------------------------
1335// Source files
1336
1337func (p *parser) parseFile() *ast.File {
1338 if p.trace {
1339 defer un(trace(p, "File"))
1340 }
1341
1342 c := p.comments
1343
1344 // Don't bother parsing the rest if we had errors scanning the first
1345 // Likely not a Go source file at all.
1346 if p.errors.Len() != 0 {
1347 return nil
1348 }
1349
1350 // The package clause is not a declaration: it does not appear in any
1351 // scope.
1352 pos := p.pos
1353 var name *ast.Ident
1354 if p.tok == token.IDENT && p.lit == "package" {
1355 p.expect(token.IDENT)
1356 name = p.parseIdent()
1357 if name.Name == "_" && p.mode&declarationErrorsMode != 0 {
1358 p.error(p.pos, "invalid package name _")
1359 }
1360 p.expectComma()
1361 } else {
1362 pos = token.NoPos
1363 }
1364 c.pos = 3
1365
1366 p.openList()
1367 var decls []ast.Decl
1368 if p.mode&packageClauseOnlyMode == 0 {
1369 // import decls
1370 for p.tok == token.IDENT && p.lit == "import" {
1371 decls = append(decls, p.parseImports())
1372 }
1373
1374 if p.mode&importsOnlyMode == 0 {
1375 // rest of package decls
1376 // TODO: loop and allow multiple expressions.
1377 decls = append(decls, p.parseFieldList(true)...)
1378 p.expect(token.EOF)
1379 }
1380 }
1381 p.closeList()
1382
1383 f := &ast.File{
1384 Package: pos,
1385 Name: name,
1386 Imports: p.imports,
1387 Decls: decls,
1388 }
1389 c.closeNode(p, f)
1390 return f
1391}