blob: 91c9dcb532c183dd5eda1777cefeefa52b81bfaf [file] [log] [blame]
Marcel van Lohuizenda386112018-12-10 15:27:50 +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
15// Package ast declares the types used to represent syntax trees for CUE
16// packages.
17package ast // import "cuelang.org/go/cue/ast"
18
19import (
20 "strconv"
21 "strings"
22
23 "cuelang.org/go/cue/token"
24)
25
26// ----------------------------------------------------------------------------
27// Interfaces
28//
29// There are two main classes of nodes: expressions, clauses, and declaration
30// nodes. The node names usually match the corresponding CUE spec production
31// names to which they correspond. The node fields correspond to the individual
32// parts of the respective productions.
33//
34// All nodes contain position information marking the beginning of the
35// corresponding source text segment; it is accessible via the Pos accessor
36// method. Nodes may contain additional position info for language constructs
37// where comments may be found between parts of the construct (typically any
38// larger, parenthesized subpart). That position information is needed to
39// properly position comments when printing the construct.
40
41// A Node represents any node in the abstract syntax tree.
42type Node interface {
43 Pos() token.Pos // position of first character belonging to the node
44 End() token.Pos // position of first character immediately after the node
45
46 // TODO: SetPos(p token.RelPos)
47
48 Comments() []*CommentGroup
49 AddComment(*CommentGroup)
50}
51
52// An Expr is implemented by all expression nodes.
53type Expr interface {
54 Node
55 exprNode()
56}
57
58func (*BadExpr) exprNode() {}
59func (*Ident) exprNode() {}
60func (*Ellipsis) exprNode() {}
61func (*BasicLit) exprNode() {}
62func (*Interpolation) exprNode() {}
63func (*StructLit) exprNode() {}
64func (*ListLit) exprNode() {}
Marcel van Lohuizenda386112018-12-10 15:27:50 +010065
66// func (*StructComprehension) exprNode() {}
67func (*ListComprehension) exprNode() {}
68func (*ParenExpr) exprNode() {}
69func (*SelectorExpr) exprNode() {}
70func (*IndexExpr) exprNode() {}
71func (*SliceExpr) exprNode() {}
72func (*CallExpr) exprNode() {}
73func (*UnaryExpr) exprNode() {}
74func (*BinaryExpr) exprNode() {}
75func (*BottomLit) exprNode() {}
76
77// A Decl node is implemented by all declarations.
78type Decl interface {
79 Node
80 declNode()
81}
82
83func (*Field) declNode() {}
84func (*ComprehensionDecl) declNode() {}
85func (*ImportDecl) declNode() {}
86func (*BadDecl) declNode() {}
87func (*EmitDecl) declNode() {}
88func (*Alias) declNode() {}
89
90// A Label is any prduction that can be used as a LHS label.
91type Label interface {
92 Node
93 labelName() (name string, isIdent bool)
94}
95
96func (n *Ident) labelName() (string, bool) {
97 return n.Name, true
98}
99
100func (n *BasicLit) labelName() (string, bool) {
101 switch n.Kind {
102 case token.STRING:
103 // Use strconv to only allow double-quoted, single-line strings.
104 if str, err := strconv.Unquote(n.Value); err == nil {
105 return str, true
106 }
107 case token.NULL, token.TRUE, token.FALSE:
108 return n.Value, true
109
110 // TODO: allow numbers to be fields?
111 }
112 return "", false
113}
114
115func (n *TemplateLabel) labelName() (string, bool) {
116 return n.Ident.Name, false
117}
118
119func (n *Interpolation) labelName() (string, bool) {
120 return "", false
121}
Marcel van Lohuizenda386112018-12-10 15:27:50 +0100122
123// LabelName reports the name of a label, if known, and whether it is valid.
124func LabelName(x Label) (name string, ok bool) {
125 return x.labelName()
126}
127
Marcel van Lohuizenda386112018-12-10 15:27:50 +0100128// Clause nodes are part of comprehensions.
129type Clause interface {
130 Node
131 clauseNode()
132}
133
134func (x *ForClause) clauseNode() {}
135func (x *IfClause) clauseNode() {}
136func (x *Alias) clauseNode() {}
137
138// Comments
139
140type comments struct {
141 groups *[]*CommentGroup
142}
143
144func (c *comments) Comments() []*CommentGroup {
145 if c.groups == nil {
146 return []*CommentGroup{}
147 }
148 return *c.groups
149}
150
151// // AddComment adds the given comments to the fields.
152// // If line is true the comment is inserted at the preceding token.
153
154func (c *comments) AddComment(cg *CommentGroup) {
155 if cg == nil {
156 return
157 }
158 if c.groups == nil {
159 a := []*CommentGroup{cg}
160 c.groups = &a
161 return
162 }
163 *c.groups = append(*c.groups, cg)
164}
165
166// A Comment node represents a single //-style or /*-style comment.
167type Comment struct {
168 Slash token.Pos // position of "/" starting the comment
169 Text string // comment text (excluding '\n' for //-style comments)
170}
171
172func (g *Comment) Comments() []*CommentGroup { return nil }
173func (g *Comment) AddComment(*CommentGroup) {}
174
175func (c *Comment) Pos() token.Pos { return c.Slash }
176func (c *Comment) End() token.Pos { return c.Slash.Add(len(c.Text)) }
177
178// A CommentGroup represents a sequence of comments
179// with no other tokens and no empty lines between.
180type CommentGroup struct {
181 // TODO: remove and use the token position of the first commment.
182 Doc bool
183 Line bool // true if it is on the same line as the node's end pos.
184
185 // Position indicates where a comment should be attached if a node has
186 // multiple tokens. 0 means before the first token, 1 means before the
187 // second, etc. For instance, for a field, the positions are:
188 // <0> Label <1> ":" <2> Expr <3> "," <4>
189 Position int8
190 List []*Comment // len(List) > 0
191}
192
193func (g *CommentGroup) Pos() token.Pos { return g.List[0].Pos() }
194func (g *CommentGroup) End() token.Pos { return g.List[len(g.List)-1].End() }
195
196func (g *CommentGroup) Comments() []*CommentGroup { return nil }
197func (g *CommentGroup) AddComment(*CommentGroup) {}
198
199func isWhitespace(ch byte) bool { return ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r' }
200
201func stripTrailingWhitespace(s string) string {
202 i := len(s)
203 for i > 0 && isWhitespace(s[i-1]) {
204 i--
205 }
206 return s[0:i]
207}
208
209// Text returns the text of the comment.
210// Comment markers (//, /*, and */), the first space of a line comment, and
211// leading and trailing empty lines are removed. Multiple empty lines are
212// reduced to one, and trailing space on lines is trimmed. Unless the result
213// is empty, it is newline-terminated.
214func (g *CommentGroup) Text() string {
215 if g == nil {
216 return ""
217 }
218 comments := make([]string, len(g.List))
219 for i, c := range g.List {
220 comments[i] = c.Text
221 }
222
223 lines := make([]string, 0, 10) // most comments are less than 10 lines
224 for _, c := range comments {
225 // Remove comment markers.
226 // The parser has given us exactly the comment text.
227 switch c[1] {
228 case '/':
229 //-style comment (no newline at the end)
230 c = c[2:]
231 // strip first space - required for Example tests
232 if len(c) > 0 && c[0] == ' ' {
233 c = c[1:]
234 }
235 case '*':
236 /*-style comment */
237 c = c[2 : len(c)-2]
238 }
239
240 // Split on newlines.
241 cl := strings.Split(c, "\n")
242
243 // Walk lines, stripping trailing white space and adding to list.
244 for _, l := range cl {
245 lines = append(lines, stripTrailingWhitespace(l))
246 }
247 }
248
249 // Remove leading blank lines; convert runs of
250 // interior blank lines to a single blank line.
251 n := 0
252 for _, line := range lines {
253 if line != "" || n > 0 && lines[n-1] != "" {
254 lines[n] = line
255 n++
256 }
257 }
258 lines = lines[0:n]
259
260 // Add final "" entry to get trailing newline from Join.
261 if n > 0 && lines[n-1] != "" {
262 lines = append(lines, "")
263 }
264
265 return strings.Join(lines, "\n")
266}
267
268// A Field represents a field declaration in a struct.
269type Field struct {
270 comments
271 Label Label // must have at least one element.
272
Marcel van Lohuizen2bf066f2018-12-16 11:43:49 +0100273 // No colon: Value must be an StructLit with one field.
Marcel van Lohuizenda386112018-12-10 15:27:50 +0100274 Colon token.Pos
275 Value Expr // the value associated with this field.
276}
277
278func (d *Field) Pos() token.Pos { return d.Label.Pos() }
279func (d *Field) End() token.Pos { return d.Value.End() }
280
281// An Alias binds another field to the alias name in the current struct.
282type Alias struct {
283 comments
284 Ident *Ident // field name, always an Ident
285 Equal token.Pos // position of "="
286 Expr Expr // An Ident or SelectorExpr
287}
288
289func (a *Alias) Pos() token.Pos { return a.Ident.Pos() }
290func (a *Alias) End() token.Pos { return a.Expr.End() }
291
292// A ComprehensionDecl node represents a field comprehension.
293type ComprehensionDecl struct {
294 comments
295 Field *Field
296 Select token.Pos
297 Clauses []Clause
298}
299
300func (x *ComprehensionDecl) Pos() token.Pos { return x.Field.Pos() }
301func (x *ComprehensionDecl) End() token.Pos {
302 if len(x.Clauses) > 0 {
303 return x.Clauses[len(x.Clauses)-1].End()
304 }
305 return x.Select
306}
307
308// ----------------------------------------------------------------------------
309// Expressions and types
310//
311// An expression is represented by a tree consisting of one
312// or more of the following concrete expression nodes.
313
Marcel van Lohuizenda386112018-12-10 15:27:50 +0100314// A BadExpr node is a placeholder for expressions containing
315// syntax errors for which no correct expression nodes can be
316// created. This is different from an ErrorExpr which represents
317// an explicitly marked error in the source.
318type BadExpr struct {
319 comments
320 From, To token.Pos // position range of bad expression
321}
322
323// A BottomLit indicates an error.
324type BottomLit struct {
325 comments
326 Bottom token.Pos
327}
328
329// An Ident node represents an left-hand side identifier.
330type Ident struct {
331 comments
332 NamePos token.Pos // identifier position
333
334 // This LHS path element may be an identifier. Possible forms:
335 // foo: a normal identifier
336 // "foo": JSON compatible
337 // <foo>: a template shorthand
338 Name string
339
340 Scope Node // scope in which node was found or nil if referring directly
341 Node Node
342}
343
344// A TemplateLabel represents a field template declaration in a struct.
345type TemplateLabel struct {
346 comments
347 Langle token.Pos
348 Ident *Ident
349 Rangle token.Pos
350}
351
Marcel van Lohuizenda386112018-12-10 15:27:50 +0100352// An Ellipsis node stands for the "..." type in a
353// parameter list or the "..." length in an array type.
354type Ellipsis struct {
355 comments
356 Ellipsis token.Pos // position of "..."
357 Elt Expr // ellipsis element type (parameter lists only); or nil
358}
359
360// A BasicLit node represents a literal of basic type.
361type BasicLit struct {
362 comments
363 ValuePos token.Pos // literal position
364 Kind token.Token // INT, FLOAT, DURATION, or STRING
365 Value string // literal string; e.g. 42, 0x7f, 3.14, 1_234_567, 1e-9, 2.4i, 'a', '\x7f', "foo", or '\m\n\o'
366}
367
368// A Interpolation node represents a string or bytes interpolation.
369type Interpolation struct { // TODO: rename to TemplateLit
370 comments
371 Elts []Expr // interleaving of strings and expressions.
372}
373
374// A StructLit node represents a literal struct.
375type StructLit struct {
376 comments
377 Lbrace token.Pos // position of "{"
378 Elts []Decl // list of elements; or nil
379 Rbrace token.Pos // position of "}"
380}
381
382// A ListLit node represents a literal list.
383type ListLit struct {
384 comments
385 Lbrack token.Pos // position of "["
386 Elts []Expr // list of composite elements; or nil
387 Ellipsis token.Pos // open list if set
388 Type Expr // type for the remaining elements
389 Rbrack token.Pos // position of "]"
390}
391
392// A ListComprehension node represents as list comprehension.
393type ListComprehension struct {
394 comments
395 Lbrack token.Pos // position of "["
396 Expr Expr
397 Clauses []Clause // Feed or Guard (TODO let)
398 Rbrack token.Pos // position of "]"
399}
400
401// A ForClause node represents a for clause in a comprehension.
402type ForClause struct {
403 comments
404 For token.Pos
405 Key *Ident // allow pattern matching?
406 Colon token.Pos
407 Value *Ident // allow pattern matching?
408 In token.Pos
409 Source Expr
410}
411
412// A IfClause node represents an if guard clause in a comprehension.
413type IfClause struct {
414 comments
415 If token.Pos
416 Condition Expr
417}
418
419// A ParenExpr node represents a parenthesized expression.
420type ParenExpr struct {
421 comments
422 Lparen token.Pos // position of "("
423 X Expr // parenthesized expression
424 Rparen token.Pos // position of ")"
425}
426
427// A SelectorExpr node represents an expression followed by a selector.
428type SelectorExpr struct {
429 comments
430 X Expr // expression
431 Sel *Ident // field selector
432}
433
434// An IndexExpr node represents an expression followed by an index.
435type IndexExpr struct {
436 comments
437 X Expr // expression
438 Lbrack token.Pos // position of "["
439 Index Expr // index expression
440 Rbrack token.Pos // position of "]"
441}
442
443// An SliceExpr node represents an expression followed by slice indices.
444type SliceExpr struct {
445 comments
446 X Expr // expression
447 Lbrack token.Pos // position of "["
448 Low Expr // begin of slice range; or nil
449 High Expr // end of slice range; or nil
450 Rbrack token.Pos // position of "]"
451}
452
453// A CallExpr node represents an expression followed by an argument list.
454type CallExpr struct {
455 comments
456 Fun Expr // function expression
457 Lparen token.Pos // position of "("
458 Args []Expr // function arguments; or nil
459 Rparen token.Pos // position of ")"
460}
461
462// A UnaryExpr node represents a unary expression.
463type UnaryExpr struct {
464 comments
465 OpPos token.Pos // position of Op
466 Op token.Token // operator
467 X Expr // operand
468}
469
470// A BinaryExpr node represents a binary expression.
471type BinaryExpr struct {
472 comments
473 X Expr // left operand
474 OpPos token.Pos // position of Op
475 Op token.Token // operator
476 Y Expr // right operand
477}
478
479// token.Pos and End implementations for expression/type nodes.
480
481func (x *BadExpr) Pos() token.Pos { return x.From }
482func (x *Ident) Pos() token.Pos { return x.NamePos }
483func (x *TemplateLabel) Pos() token.Pos { return x.Langle }
Marcel van Lohuizenda386112018-12-10 15:27:50 +0100484func (x *Ellipsis) Pos() token.Pos { return x.Ellipsis }
485func (x *BasicLit) Pos() token.Pos { return x.ValuePos }
486func (x *Interpolation) Pos() token.Pos { return x.Elts[0].Pos() }
487func (x *StructLit) Pos() token.Pos {
488 if x.Lbrace == token.NoPos && len(x.Elts) > 0 {
489 return x.Elts[0].Pos()
490 }
491 return x.Lbrace
492}
493
494func (x *ListLit) Pos() token.Pos { return x.Lbrack }
495func (x *ListComprehension) Pos() token.Pos { return x.Lbrack }
496func (x *ForClause) Pos() token.Pos { return x.For }
497func (x *IfClause) Pos() token.Pos { return x.If }
498func (x *ParenExpr) Pos() token.Pos { return x.Lparen }
499func (x *SelectorExpr) Pos() token.Pos { return x.X.Pos() }
500func (x *IndexExpr) Pos() token.Pos { return x.X.Pos() }
501func (x *SliceExpr) Pos() token.Pos { return x.X.Pos() }
502func (x *CallExpr) Pos() token.Pos { return x.Fun.Pos() }
503func (x *UnaryExpr) Pos() token.Pos { return x.OpPos }
504func (x *BinaryExpr) Pos() token.Pos { return x.X.Pos() }
505func (x *BottomLit) Pos() token.Pos { return x.Bottom }
506
507func (x *BadExpr) End() token.Pos { return x.To }
508func (x *Ident) End() token.Pos {
509 return x.NamePos.Add(len(x.Name))
510}
511func (x *TemplateLabel) End() token.Pos { return x.Rangle }
Marcel van Lohuizenda386112018-12-10 15:27:50 +0100512func (x *Ellipsis) End() token.Pos {
513 if x.Elt != nil {
514 return x.Elt.End()
515 }
516 return x.Ellipsis + 3 // len("...")
517}
518func (x *BasicLit) End() token.Pos { return token.Pos(int(x.ValuePos) + len(x.Value)) }
519func (x *Interpolation) End() token.Pos { return x.Elts[len(x.Elts)-1].Pos() }
520func (x *StructLit) End() token.Pos {
521 if x.Rbrace == token.NoPos && len(x.Elts) > 0 {
522 return x.Elts[len(x.Elts)-1].Pos()
523 }
524 return x.Rbrace.Add(1)
525}
526func (x *ListLit) End() token.Pos { return x.Rbrack.Add(1) }
527func (x *ListComprehension) End() token.Pos { return x.Rbrack }
528func (x *ForClause) End() token.Pos { return x.Source.End() }
529func (x *IfClause) End() token.Pos { return x.Condition.End() }
530func (x *ParenExpr) End() token.Pos { return x.Rparen.Add(1) }
531func (x *SelectorExpr) End() token.Pos { return x.Sel.End() }
532func (x *IndexExpr) End() token.Pos { return x.Rbrack.Add(1) }
533func (x *SliceExpr) End() token.Pos { return x.Rbrack.Add(1) }
534func (x *CallExpr) End() token.Pos { return x.Rparen.Add(1) }
535func (x *UnaryExpr) End() token.Pos { return x.X.End() }
536func (x *BinaryExpr) End() token.Pos { return x.Y.End() }
537func (x *BottomLit) End() token.Pos { return x.Bottom.Add(1) }
538
539// ----------------------------------------------------------------------------
540// Convenience functions for Idents
541
542// NewIdent creates a new Ident without position.
543// Useful for ASTs generated by code other than the Go
544func NewIdent(name string) *Ident {
545 return &Ident{comments{}, token.NoPos, name, nil, nil}
546}
547
548func (id *Ident) String() string {
549 if id != nil {
550 return id.Name
551 }
552 return "<nil>"
553}
554
555// ----------------------------------------------------------------------------
556// Declarations
557
558// An ImportSpec node represents a single package import.
559type ImportSpec struct {
560 comments
561 Name *Ident // local package name (including "."); or nil
562 Path *BasicLit // import path
563 EndPos token.Pos // end of spec (overrides Path.Pos if nonzero)
564}
565
566// Pos and End implementations for spec nodes.
567
568func (s *ImportSpec) Pos() token.Pos {
569 if s.Name != nil {
570 return s.Name.Pos()
571 }
572 return s.Path.Pos()
573}
574
575// func (s *AliasSpec) Pos() token.Pos { return s.Name.Pos() }
576// func (s *ValueSpec) Pos() token.Pos { return s.Names[0].Pos() }
577// func (s *TypeSpec) Pos() token.Pos { return s.Name.Pos() }
578
579func (s *ImportSpec) End() token.Pos {
580 if s.EndPos != 0 {
581 return s.EndPos
582 }
583 return s.Path.End()
584}
585
586// specNode() ensures that only spec nodes can be assigned to a Spec.
587func (*ImportSpec) specNode() {}
588
589// A declaration is represented by one of the following declaration nodes.
590type (
591 // A BadDecl node is a placeholder for declarations containing
592 // syntax errors for which no correct declaration nodes can be
593 // created.
594 BadDecl struct {
595 comments
596 From, To token.Pos // position range of bad declaration
597 }
598
599 // A ImportDecl node represents a series of import declarations. A valid
600 // Lparen position (Lparen.Line > 0) indicates a parenthesized declaration.
601 ImportDecl struct {
602 comments
603 Import token.Pos
604 Lparen token.Pos // position of '(', if any
605 Specs []*ImportSpec
606 Rparen token.Pos // position of ')', if any
607 }
608
609 // An EmitDecl node represents a single expression used as a declaration.
610 // The expressions in this declaration is what will be emitted as
611 // configuration output.
612 //
613 // An EmitDecl may only appear at the top level.
614 EmitDecl struct {
615 comments
616 Expr Expr
617 }
618)
619
620// Pos and End implementations for declaration nodes.
621
622func (d *BadDecl) Pos() token.Pos { return d.From }
623func (d *ImportDecl) Pos() token.Pos { return d.Import }
624func (d *EmitDecl) Pos() token.Pos { return d.Expr.Pos() }
625
626func (d *BadDecl) End() token.Pos { return d.To }
627func (d *ImportDecl) End() token.Pos {
628 if d.Rparen.IsValid() {
629 return d.Rparen.Add(1)
630 }
631 return d.Specs[0].End()
632}
633func (d *EmitDecl) End() token.Pos { return d.Expr.End() }
634
635// ----------------------------------------------------------------------------
636// Files and packages
637
638// A File node represents a Go source file.
639//
640// The Comments list contains all comments in the source file in order of
641// appearance, including the comments that are pointed to from other nodes
642// via Doc and Comment fields.
643type File struct {
644 Filename string
645 comments
646 Package token.Pos // position of "package" pseudo-keyword
647 Name *Ident // package names
648 // TODO: Change Expr to Decl?
649 Imports []*ImportSpec // imports in this file
650 Decls []Decl // top-level declarations; or nil
651 Unresolved []*Ident // unresolved identifiers in this file
652}
653
654func (f *File) Pos() token.Pos {
655 if f.Package != token.NoPos {
656 return f.Package
657 }
658 if len(f.Decls) > 0 {
659 return f.Decls[0].Pos()
660 }
661 return token.NoPos
662}
663func (f *File) End() token.Pos {
664 if n := len(f.Decls); n > 0 {
665 return f.Decls[n-1].End()
666 }
667 if f.Name != nil {
668 return f.Name.End()
669 }
670 return token.NoPos
671}