blob: 9869e5dbb5e2bd3629ff574cab9fbb80a68efbb5 [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
Marcel van Lohuizenda386112018-12-10 15:27:50 +010096 case *StructLit:
97 for _, f := range n.Elts {
98 walk(v, f)
99 }
100
101 // Expressions
102 case *BottomLit, *BadExpr, *Ident, *BasicLit:
103 // nothing to do
104
Marcel van Lohuizenda386112018-12-10 15:27:50 +0100105 case *TemplateLabel:
106 walk(v, n.Ident)
107
108 case *Interpolation:
109 for _, e := range n.Elts {
110 walk(v, e)
111 }
112
113 case *Ellipsis:
114 if n.Elt != nil {
115 walk(v, n.Elt)
116 }
117
118 case *ListLit:
119 walkExprList(v, n.Elts)
120 if n.Type != nil {
121 walk(v, n.Type)
122 }
123
124 case *ParenExpr:
125 walk(v, n.X)
126
127 case *SelectorExpr:
128 walk(v, n.X)
129 walk(v, n.Sel)
130
131 case *IndexExpr:
132 walk(v, n.X)
133 walk(v, n.Index)
134
135 case *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 *CallExpr:
145 walk(v, n.Fun)
146 walkExprList(v, n.Args)
147
148 case *UnaryExpr:
149 walk(v, n.X)
150
151 case *BinaryExpr:
152 walk(v, n.X)
153 walk(v, n.Y)
154
155 // Declarations
156 case *ImportSpec:
157 if n.Name != nil {
158 walk(v, n.Name)
159 }
160 walk(v, n.Path)
161
162 case *BadDecl:
163 // nothing to do
164
165 case *ImportDecl:
166 for _, s := range n.Specs {
167 walk(v, s)
168 }
169
170 case *EmitDecl:
171 walk(v, n.Expr)
172
173 case *Alias:
174 walk(v, n.Ident)
175 walk(v, n.Expr)
176
177 case *ComprehensionDecl:
178 walk(v, n.Field)
179 for _, c := range n.Clauses {
180 walk(v, c)
181 }
182
183 // Files and packages
184 case *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 *ListComprehension:
194 walk(v, n.Expr)
195 for _, c := range n.Clauses {
196 walk(v, c)
197 }
198
199 case *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 *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(Node) bool
218 after func(Node)
219
220 commentStack []commentFrame
221 current commentFrame
222}
223
224type commentFrame struct {
225 cg []*CommentGroup
226 pos int8
227}
228
229func (f *inspector) Before(node 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 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}