/
ast.go
430 lines (370 loc) · 15.9 KB
/
ast.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
// Mgmt
// Copyright (C) 2013-2024+ James Shubin and the project contributors
// Written by James Shubin <james@shubin.ca> and the project contributors
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <https://www.gnu.org/licenses/>.
//
// Additional permission under GNU GPL version 3 section 7
//
// If you modify this program, or any covered work, by linking or combining it
// with embedded mcl code and modules (and that the embedded mcl code and
// modules which link with this program, contain a copy of their source code in
// the authoritative form) containing parts covered by the terms of any other
// license, the licensors of this program grant you additional permission to
// convey the resulting work. Furthermore, the licensors of this program grant
// the original author, James Shubin, additional permission to update this
// additional permission if he deems it necessary to achieve the goals of this
// additional permission.
package interfaces
import (
"fmt"
"io"
"sort"
"github.com/purpleidea/mgmt/engine"
"github.com/purpleidea/mgmt/lang/types"
"github.com/purpleidea/mgmt/pgraph"
"github.com/purpleidea/mgmt/util/errwrap"
)
// Node represents either a Stmt or an Expr. It contains the minimum set of
// methods that they must both implement. In practice it is not used especially
// often since we usually know which kind of node we want.
type Node interface {
//fmt.Stringer // already provided by pgraph.Vertex
pgraph.Vertex // must implement this since we store these in our graphs
// Apply is a general purpose iterator method that operates on any node.
Apply(fn func(Node) error) error
//Parent() Node // TODO: should we implement this?
}
// Stmt represents a statement node in the language. A stmt could be a resource,
// a `bind` statement, or even an `if` statement. (Different from an `if`
// expression.)
type Stmt interface {
Node
// Init initializes the populated node and does some basic validation.
Init(*Data) error
// Interpolate returns an expanded form of the AST as a new AST. It does
// a recursive interpolate (copy) of all members in the AST.
Interpolate() (Stmt, error) // return expanded form of AST as a new AST
// Copy returns a light copy of the struct. Anything static will not be
// copied. For a full recursive copy consider using Interpolate instead.
// TODO: do we need an error in the signature?
Copy() (Stmt, error)
// Ordering returns a graph of the scope ordering that represents the
// data flow. This can be used in SetScope so that it knows the correct
// order to run it in.
Ordering(map[string]Node) (*pgraph.Graph, map[Node]string, error)
// SetScope sets the scope here and propagates it downwards.
SetScope(*Scope) error
// Unify returns the list of invariants that this node produces. It does
// so recursively on any children elements that exist in the AST, and
// returns the collection to the caller.
Unify() ([]Invariant, error)
// Graph returns the reactive function graph expressed by this node.
Graph() (*pgraph.Graph, error)
// Output returns the output that this "program" produces. This output
// is what is used to build the output graph. It requires the input
// table of values that are used to populate each function.
Output(map[Func]types.Value) (*Output, error)
}
// Expr represents an expression in the language. Expr implementations must have
// their method receivers implemented as pointer receivers so that they can be
// easily copied and moved around. Expr also implements pgraph.Vertex so that
// these can be stored as pointers in our graph data structure.
type Expr interface {
Node
// Init initializes the populated node and does some basic validation.
Init(*Data) error
// Interpolate returns an expanded form of the AST as a new AST. It does
// a recursive interpolate (copy) of all members in the AST. For a light
// copy use Copy.
Interpolate() (Expr, error)
// Copy returns a light copy of the struct. Anything static will not be
// copied. For a full recursive copy consider using Interpolate instead.
// TODO: do we need an error in the signature?
Copy() (Expr, error)
// Ordering returns a graph of the scope ordering that represents the
// data flow. This can be used in SetScope so that it knows the correct
// order to run it in.
Ordering(map[string]Node) (*pgraph.Graph, map[Node]string, error)
// SetScope sets the scope here and propagates it downwards.
SetScope(*Scope, map[string]Expr) error
// SetType sets the type definitively, and errors if it is incompatible.
SetType(*types.Type) error
// Type returns the type of this expression. It may speculate if it can
// determine it statically. This errors if it is not yet known.
Type() (*types.Type, error)
// Unify returns the list of invariants that this node produces. It does
// so recursively on any children elements that exist in the AST, and
// returns the collection to the caller.
Unify() ([]Invariant, error)
// Graph returns the reactive function graph expressed by this node. It
// takes in the environment of any functions in scope. It also returns
// the function for this node.
Graph(env map[string]Func) (*pgraph.Graph, Func, error)
// SetValue stores the result of the last computation of this expression
// node.
SetValue(types.Value) error
// Value returns the value of this expression in our type system.
Value() (types.Value, error)
}
// ScopeGrapher adds a method to turn an AST (Expr or Stmt) into a graph so that
// we can debug the SetScope compilation phase.
type ScopeGrapher interface {
Node
// ScopeGraph adds nodes and vertices to the supplied graph.
ScopeGraph(g *pgraph.Graph)
}
// Data provides some data to the node that could be useful during its lifetime.
type Data struct {
// Fs represents a handle to the filesystem that we're running on. This
// is necessary for opening files if needed by import statements. The
// file() paths used to get templates or other files from our deploys
// come from here, this is *not* used to interact with the host file
// system to manage file resources or other aspects.
Fs engine.Fs
// FsURI is the fs URI of the active filesystem. This is useful to pass
// to the engine.World API for further consumption.
FsURI string
// Base directory (absolute path) that the running code is in. If an
// import is found, that's a recursive addition, and naturally for that
// run, this value would be different in the recursion.
Base string
// Files is a list of absolute paths seen so far. This includes all
// previously seen paths, where as the former Offsets parameter did not.
Files []string
// Imports stores a graph inside a vertex so we have a current cursor.
// This means that as we recurse through our import graph (hopefully a
// DAG) we can know what the parent vertex in our graph is to edge to.
// If we ever can't topologically sort it, then it has an import loop.
Imports *pgraph.SelfVertex
// Metadata is the metadata structure associated with the given parsing.
// It can be present, which is often the case when importing a module,
// or it can be nil, which is often the case when parsing a single file.
// When imports are nested (eg: an imported module imports another one)
// the metadata structure can recursively point to an earlier structure.
Metadata *Metadata
// Modules is an absolute path to a modules directory on the current Fs.
// It is the directory to use to look for remote modules if we haven't
// specified an alternative with the metadata Path field. This is
// usually initialized with the global modules path that can come from
// the cli or an environment variable, but this only occurs for the
// initial download/get operation, and obviously not once we're running
// a deploy, since by then everything in here would have been copied to
// the runtime fs.
Modules string
// Downloader is the interface that must be fulfilled to download
// modules. If a missing import is found, and this is not nil, then it
// will be run once in an attempt to get the missing module before it
// fails outright. In practice, it is recommended to separate this
// download phase in a separate step from the production running and
// deploys, however that is not blocked at the level of this interface.
Downloader Downloader
// LexParser is a function that needs to get passed in to run the lexer
// and parser to build the initial AST. This is passed in this way to
// avoid dependency cycles.
LexParser func(io.Reader) (Stmt, error)
// StrInterpolater is a function that needs to get passed in to run the
// string interpolation. This is passed in this way to avoid dependency
// cycles.
StrInterpolater func(string, *Pos, *Data) (Expr, error)
//World engine.World // TODO: do we need this?
// Prefix provides a unique path prefix that we can namespace in. It is
// currently shared identically across the whole AST. Nodes should be
// careful to not write on top of other nodes data.
Prefix string
// Debug represents if we're running in debug mode or not.
Debug bool
// Logf is a logger which should be used.
Logf func(format string, v ...interface{})
}
// Scope represents a mapping between a variables identifier and the
// corresponding expression it is bound to. Local scopes in this language exist
// and are formed by nesting within if statements. Child scopes can shadow
// variables in parent scopes, which is another way of saying they can redefine
// previously used variables as long as the new binding happens within a child
// scope. This is useful so that someone in the top scope can't prevent a child
// module from ever using that variable name again. It might be worth revisiting
// this point in the future if we find it adds even greater code safety. Please
// report any bugs you have written that would have been prevented by this. This
// also contains the currently available functions. They function similarly to
// the variables, and you can add new ones with a function statement definition.
// An interesting note about these is that they exist in a distinct namespace
// from the variables, which could actually contain lambda functions.
type Scope struct {
Variables map[string]Expr
Functions map[string]Expr // the Expr will usually be an *ExprFunc (actually it's usually (or always) an *ExprSingleton, which wraps an *ExprFunc now)
Classes map[string]Stmt
Chain []Node // chain of previously seen node's
}
// EmptyScope returns the zero, empty value for the scope, with all the internal
// lists initialized appropriately.
func EmptyScope() *Scope {
return &Scope{
Variables: make(map[string]Expr),
Functions: make(map[string]Expr),
Classes: make(map[string]Stmt),
Chain: []Node{},
}
}
// InitScope initializes any uninitialized part of the struct. It is safe to use
// on scopes with existing data.
func (obj *Scope) InitScope() {
if obj.Variables == nil {
obj.Variables = make(map[string]Expr)
}
if obj.Functions == nil {
obj.Functions = make(map[string]Expr)
}
if obj.Classes == nil {
obj.Classes = make(map[string]Stmt)
}
if obj.Chain == nil {
obj.Chain = []Node{}
}
}
// Copy makes a copy of the Scope struct. This ensures that if the internal map
// is changed, it doesn't affect other copies of the Scope. It does *not* copy
// or change the Expr pointers contained within, since these are references, and
// we need those to be consistently pointing to the same things after copying.
func (obj *Scope) Copy() *Scope {
variables := make(map[string]Expr)
functions := make(map[string]Expr)
classes := make(map[string]Stmt)
chain := []Node{}
if obj != nil { // allow copying nil scopes
obj.InitScope() // safety
for k, v := range obj.Variables { // copy
variables[k] = v // we don't copy the expr's!
}
for k, v := range obj.Functions { // copy
functions[k] = v // we don't copy the generator func's
}
for k, v := range obj.Classes { // copy
classes[k] = v // we don't copy the StmtClass!
}
for _, x := range obj.Chain { // copy
chain = append(chain, x) // we don't copy the Stmt pointer!
}
}
return &Scope{
Variables: variables,
Functions: functions,
Classes: classes,
Chain: chain,
}
}
// Merge takes an existing scope and merges a scope on top of it. If any
// elements had to be overwritten, then the error result will contain some info.
// Even if this errors, the scope will have been merged successfully. The merge
// runs in a deterministic order so that errors will be consistent. Use Copy if
// you don't want to change this destructively.
// FIXME: this doesn't currently merge Chain's... Should it?
func (obj *Scope) Merge(scope *Scope) error {
var err error
// collect names so we can iterate in a deterministic order
namedVariables := []string{}
namedFunctions := []string{}
namedClasses := []string{}
for name := range scope.Variables {
namedVariables = append(namedVariables, name)
}
for name := range scope.Functions {
namedFunctions = append(namedFunctions, name)
}
for name := range scope.Classes {
namedClasses = append(namedClasses, name)
}
sort.Strings(namedVariables)
sort.Strings(namedFunctions)
sort.Strings(namedClasses)
obj.InitScope() // safety
for _, name := range namedVariables {
if _, exists := obj.Variables[name]; exists {
e := fmt.Errorf("variable `%s` was overwritten", name)
err = errwrap.Append(err, e)
}
obj.Variables[name] = scope.Variables[name]
}
for _, name := range namedFunctions {
if _, exists := obj.Functions[name]; exists {
e := fmt.Errorf("function `%s` was overwritten", name)
err = errwrap.Append(err, e)
}
obj.Functions[name] = scope.Functions[name]
}
for _, name := range namedClasses {
if _, exists := obj.Classes[name]; exists {
e := fmt.Errorf("class `%s` was overwritten", name)
err = errwrap.Append(err, e)
}
obj.Classes[name] = scope.Classes[name]
}
return err
}
// IsEmpty returns whether or not a scope is empty or not.
// FIXME: this doesn't currently consider Chain's... Should it?
func (obj *Scope) IsEmpty() bool {
//if obj == nil { // TODO: add me if this turns out to be useful
// return true
//}
if len(obj.Variables) > 0 {
return false
}
if len(obj.Functions) > 0 {
return false
}
if len(obj.Classes) > 0 {
return false
}
return true
}
// Arg represents a name identifier for a func or class argument declaration and
// is sometimes accompanied by a type. This does not satisfy the Expr interface.
type Arg struct {
Name string
Type *types.Type // nil if unspecified (needs to be solved for)
}
// String returns a short representation of this arg.
func (obj *Arg) String() string {
s := obj.Name
if obj.Type != nil {
s += fmt.Sprintf(" %s", obj.Type.String())
}
return s
}
// Edge is the data structure representing a compiled edge that is used in the
// lang to express a dependency between two resources and optionally send/recv.
type Edge struct {
Kind1 string // kind of resource
Name1 string // name of resource
Send string // name of field used for send/recv (optional)
Kind2 string // kind of resource
Name2 string // name of resource
Recv string // name of field used for send/recv (optional)
Notify bool // is there a notification being sent?
}
// Output is a collection of data returned by a Stmt.
type Output struct { // returned by Stmt
Resources []engine.Res
Edges []*Edge
//Exported []*Exports // TODO: add exported resources
}
// EmptyOutput returns the zero, empty value for the output, with all the
// internal lists initialized appropriately.
func EmptyOutput() *Output {
return &Output{
Resources: []engine.Res{},
Edges: []*Edge{},
}
}