blob: 1765ee8335aba55ab51bd066eb17463375d1bf7e [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
20 "cuelang.org/go/cue/ast"
21 "cuelang.org/go/cue/token"
22)
23
24// TODO: use ast.Walk or adopt that version to allow visitors.
25
26// A visitor's before method is invoked for each node encountered by Walk.
27// If the result visitor w is not nil, Walk visits each of the children
28// of node with the visitor w, followed by a call of w.After.
29type visitor interface {
30 Before(node ast.Node) (w visitor)
31 After(node ast.Node)
32}
33
34// Helper functions for common node lists. They may be empty.
35
36func walkIdentList(v visitor, list []*ast.Ident) {
37 for _, x := range list {
38 walk(v, x)
39 }
40}
41
42func walkExprList(v visitor, list []ast.Expr) {
43 for _, x := range list {
44 walk(v, x)
45 }
46}
47
48func walkDeclList(v visitor, list []ast.Decl) {
49 for _, x := range list {
50 walk(v, x)
51 }
52}
53
54// walk traverses an AST in depth-first order: It starts by calling
55// v.Visit(node); node must not be nil. If the visitor w returned by
56// v.Visit(node) is not nil, walk is invoked recursively with visitor
57// w for each of the non-nil children of node, followed by a call of
58// w.Visit(nil).
59//
60func walk(v visitor, node ast.Node) {
61 if v = v.Before(node); v == nil {
62 return
63 }
64
65 // TODO: record the comment groups and interleave with the values like for
66 // parsing and printing?
67 for _, c := range node.Comments() {
68 walk(v, c)
69 }
70
71 // walk children
72 // (the order of the cases matches the order
73 // of the corresponding node types in go)
74 switch n := node.(type) {
75 // Comments and fields
76 case *ast.Comment:
77 // nothing to do
78
79 case *ast.CommentGroup:
80 for _, c := range n.List {
81 walk(v, c)
82 }
83
84 case *ast.Field:
85 walk(v, n.Label)
86 if n.Value != nil {
87 walk(v, n.Value)
88 }
89
90 case *ast.LambdaExpr:
91 for _, p := range n.Params {
92 walk(v, p)
93 }
94 walk(v, n.Expr)
95
96 case *ast.StructLit:
97 for _, f := range n.Elts {
98 walk(v, f)
99 }
100
101 // Expressions
102 case *ast.BottomLit, *ast.BadExpr, *ast.Ident, *ast.BasicLit:
103 // nothing to do
104
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +0100105 case *ast.TemplateLabel:
106 walk(v, n.Ident)
107
108 case *ast.Interpolation:
109 for _, e := range n.Elts {
110 walk(v, e)
111 }
112
113 case *ast.Ellipsis:
114 if n.Elt != nil {
115 walk(v, n.Elt)
116 }
117
118 case *ast.ListLit:
119 walkExprList(v, n.Elts)
120 if n.Type != nil {
121 walk(v, n.Type)
122 }
123
124 case *ast.ParenExpr:
125 walk(v, n.X)
126
127 case *ast.SelectorExpr:
128 walk(v, n.X)
129 walk(v, n.Sel)
130
131 case *ast.IndexExpr:
132 walk(v, n.X)
133 walk(v, n.Index)
134
135 case *ast.SliceExpr:
136 walk(v, n.X)
137 if n.Low != nil {
138 walk(v, n.Low)
139 }
140 if n.High != nil {
141 walk(v, n.High)
142 }
143
144 case *ast.CallExpr:
145 walk(v, n.Fun)
146 walkExprList(v, n.Args)
147
148 case *ast.UnaryExpr:
149 walk(v, n.X)
150
151 case *ast.BinaryExpr:
152 walk(v, n.X)
153 walk(v, n.Y)
154
155 // Declarations
156 case *ast.ImportSpec:
157 if n.Name != nil {
158 walk(v, n.Name)
159 }
160 walk(v, n.Path)
161
162 case *ast.BadDecl:
163 // nothing to do
164
165 case *ast.ImportDecl:
166 for _, s := range n.Specs {
167 walk(v, s)
168 }
169
170 case *ast.EmitDecl:
171 walk(v, n.Expr)
172
173 case *ast.Alias:
174 walk(v, n.Ident)
175 walk(v, n.Expr)
176
177 case *ast.ComprehensionDecl:
178 walk(v, n.Field)
179 for _, c := range n.Clauses {
180 walk(v, c)
181 }
182
183 // Files and packages
184 case *ast.File:
185 if n.Name != nil {
186 walk(v, n.Name)
187 }
188 walkDeclList(v, n.Decls)
189 // don't walk n.Comments - they have been
190 // visited already through the individual
191 // nodes
192
193 case *ast.ListComprehension:
194 walk(v, n.Expr)
195 for _, c := range n.Clauses {
196 walk(v, c)
197 }
198
199 case *ast.ForClause:
200 if n.Key != nil {
201 walk(v, n.Key)
202 }
203 walk(v, n.Value)
204 walk(v, n.Source)
205
206 case *ast.IfClause:
207 walk(v, n.Condition)
208
209 default:
210 panic(fmt.Sprintf("Walk: unexpected node type %T", n))
211 }
212
213 v.After(node)
214}
215
216type inspector struct {
217 before func(ast.Node) bool
218 after func(ast.Node)
219
220 commentStack []commentFrame
221 current commentFrame
222}
223
224type commentFrame struct {
225 cg []*ast.CommentGroup
226 pos int8
227}
228
229func (f *inspector) Before(node ast.Node) visitor {
230 if f.before == nil || f.before(node) {
231 f.commentStack = append(f.commentStack, f.current)
232 f.current = commentFrame{cg: node.Comments()}
233 f.visitComments(f.current.pos)
234 return f
235 }
236 return nil
237}
238
239func (f *inspector) After(node ast.Node) {
240 f.visitComments(127)
241 p := len(f.commentStack) - 1
242 f.current = f.commentStack[p]
243 f.commentStack = f.commentStack[:p]
244 f.current.pos++
245 if f.after != nil {
246 f.after(node)
247 }
248}
249
250func (f *inspector) Token(t token.Token) {
251 f.current.pos++
252}
253
254func (f *inspector) setPos(i int8) {
255 f.current.pos = i
256}
257
258func (f *inspector) visitComments(pos int8) {
259 c := &f.current
260 for ; len(c.cg) > 0; c.cg = c.cg[1:] {
261 cg := c.cg[0]
262 if cg.Position == pos {
263 continue
264 }
265 if f.before == nil || f.before(cg) {
266 for _, c := range cg.List {
267 if f.before == nil || f.before(c) {
268 if f.after != nil {
269 f.after(c)
270 }
271 }
272 }
273 if f.after != nil {
274 f.after(cg)
275 }
276 }
277 }
278}