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