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