blob: 01a8220801c159be170f233394958a14aec6e98c [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
Marcel van Lohuizenb9b62d32019-03-14 23:50:15 +010084 case *ast.Attribute:
85 // nothing to do
86
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +010087 case *ast.Field:
88 walk(v, n.Label)
89 if n.Value != nil {
90 walk(v, n.Value)
91 }
Marcel van Lohuizenb9b62d32019-03-14 23:50:15 +010092 for _, a := range n.Attrs {
93 walk(v, a)
94 }
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +010095
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +010096 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
Marcel van Lohuizend96ad3d2018-12-10 15:30:20 +0100113 case *ast.ListLit:
114 walkExprList(v, n.Elts)
115 if n.Type != nil {
116 walk(v, n.Type)
117 }
118
119 case *ast.ParenExpr:
120 walk(v, n.X)
121
122 case *ast.SelectorExpr:
123 walk(v, n.X)
124 walk(v, n.Sel)
125
126 case *ast.IndexExpr:
127 walk(v, n.X)
128 walk(v, n.Index)
129
130 case *ast.SliceExpr:
131 walk(v, n.X)
132 if n.Low != nil {
133 walk(v, n.Low)
134 }
135 if n.High != nil {
136 walk(v, n.High)
137 }
138
139 case *ast.CallExpr:
140 walk(v, n.Fun)
141 walkExprList(v, n.Args)
142
143 case *ast.UnaryExpr:
144 walk(v, n.X)
145
146 case *ast.BinaryExpr:
147 walk(v, n.X)
148 walk(v, n.Y)
149
150 // Declarations
151 case *ast.ImportSpec:
152 if n.Name != nil {
153 walk(v, n.Name)
154 }
155 walk(v, n.Path)
156
157 case *ast.BadDecl:
158 // nothing to do
159
160 case *ast.ImportDecl:
161 for _, s := range n.Specs {
162 walk(v, s)
163 }
164
165 case *ast.EmitDecl:
166 walk(v, n.Expr)
167
168 case *ast.Alias:
169 walk(v, n.Ident)
170 walk(v, n.Expr)
171
172 case *ast.ComprehensionDecl:
173 walk(v, n.Field)
174 for _, c := range n.Clauses {
175 walk(v, c)
176 }
177
178 // Files and packages
179 case *ast.File:
180 if n.Name != nil {
181 walk(v, n.Name)
182 }
183 walkDeclList(v, n.Decls)
184 // don't walk n.Comments - they have been
185 // visited already through the individual
186 // nodes
187
188 case *ast.ListComprehension:
189 walk(v, n.Expr)
190 for _, c := range n.Clauses {
191 walk(v, c)
192 }
193
194 case *ast.ForClause:
195 if n.Key != nil {
196 walk(v, n.Key)
197 }
198 walk(v, n.Value)
199 walk(v, n.Source)
200
201 case *ast.IfClause:
202 walk(v, n.Condition)
203
204 default:
205 panic(fmt.Sprintf("Walk: unexpected node type %T", n))
206 }
207
208 v.After(node)
209}
210
211type inspector struct {
212 before func(ast.Node) bool
213 after func(ast.Node)
214
215 commentStack []commentFrame
216 current commentFrame
217}
218
219type commentFrame struct {
220 cg []*ast.CommentGroup
221 pos int8
222}
223
224func (f *inspector) Before(node ast.Node) visitor {
225 if f.before == nil || f.before(node) {
226 f.commentStack = append(f.commentStack, f.current)
227 f.current = commentFrame{cg: node.Comments()}
228 f.visitComments(f.current.pos)
229 return f
230 }
231 return nil
232}
233
234func (f *inspector) After(node ast.Node) {
235 f.visitComments(127)
236 p := len(f.commentStack) - 1
237 f.current = f.commentStack[p]
238 f.commentStack = f.commentStack[:p]
239 f.current.pos++
240 if f.after != nil {
241 f.after(node)
242 }
243}
244
245func (f *inspector) Token(t token.Token) {
246 f.current.pos++
247}
248
249func (f *inspector) setPos(i int8) {
250 f.current.pos = i
251}
252
253func (f *inspector) visitComments(pos int8) {
254 c := &f.current
255 for ; len(c.cg) > 0; c.cg = c.cg[1:] {
256 cg := c.cg[0]
257 if cg.Position == pos {
258 continue
259 }
260 if f.before == nil || f.before(cg) {
261 for _, c := range cg.List {
262 if f.before == nil || f.before(c) {
263 if f.after != nil {
264 f.after(c)
265 }
266 }
267 }
268 if f.after != nil {
269 f.after(cg)
270 }
271 }
272 }
273}