/
states.go
321 lines (279 loc) · 9.81 KB
/
states.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
// Copyright 2023 CUE Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package adt
// TODO: clean up following notes:
// Used in expr.go:
// - ctx.value (uses: noncrete scalar allowed, concrete scalar, concrete composite)
// - evalState
// - ctx.node (need to know all fields)
// - ctx.lookup
// - ctx.concrete
//
// - ctx.relLabel
// OK: always exists
// - ctx.relNode (upcount + unify(partial))
// OK: node always exists.
//
// - ctx.evalState (in validation of comparison against bottom)
//
// - arc.Finalize (finalized)
// - CompleteArcs (conjuncts)
//
// lookup in p1
// - process remaining field todos
// lookup:
// if node is currently processing, just look up directly and create
// field with notification.
//
// if node has not been processed, process once.
//
// Any dynamic fields should have been triggered by the existence of a new
// arc. This will either cascade the evaluation or not.
// p1: {
// (p1.baz): "bar" // t1
// (p1.foo): "baz" // t2
// baz: "foo"
// }
//
// <p1, fieldsKnown> -> t1 -> <p1.baz, scalar>
// <p1.foo, scalar> -> t1
// <p1, fieldsKnown> -> t2 -> <p1.foo, scalar>
// p2: {
// (p2[p2.baz]): "bar"
// (p2.foo): "baz"
// baz: "qux"
// qux: "foo"
// }
// b -> a - > b: detected cycle in b:
//
// xxx register expression (a-10) being processed as a post constraint.
// add task to pending.
// register value as waiting for scalar to be completed later.
// return with cycle/ in complete error.
//
// - in b:
// xxx register expression (b+10) as post constraint.
// add task to pending
// register value as waiting for scalar to be completed later.
// 5 is processed and set
// this completes the task in b
// this sets a scalar in b
// this completes the expression in a
//
// b: a - 10
// a: b + 10
// a: 5
//
// a: a
// a: 5
//
// These are the condition types of the CUE evaluator. A scheduler
// is associated with a single Vertex. So when these states refer to a Vertex,
// it is the Vertex associated with the scheduler.
//
// There are core conditions and condition sets. The core conditions are
// determined during operation as conditions are met. The condition sets are
// used to indicate a set of required or provided conditions.
//
// Core conditions can be signal conditions or counter conditions. A counter
// condition is triggered if all conjuncts that contribute to the computation
// of this condition have been met. A signal condition is triggered as soon as
// evidence is found that this condition is met. Unless otherwise specified,
// conditions are counter conditions.
const (
// allAncestorsProcessed indicates that all conjuncts that could be added
// to the Vertex by any of its ancestors have been added. In other words,
// all ancestors schedulers have reached the state fieldConjunctsKnown.
//
// This is a signal condition. It is explicitly set in unify when a
// parent meets fieldConjunctsKnown|allAncestorsProcessed.
allAncestorsProcessed condition = 1 << iota
// Really: all ancestor subfield tasks processed.
// arcTypeKnown means that the ArcType value of a Vertex is fully
// determined. The ArcType of all fields of a Vertex need to be known
// before the complete set of fields of this Vertex can be known.
arcTypeKnown
// valueKnown means that it is known what the "type" of the value would be
// if present.
valueKnown
// scalarKnown indicates that a Vertex has either a concrete scalar value or
// that it is known that it will never have a scalar value.
//
// This is a signal condition that is reached when:
// - a node is set to a concrete scalar value
// - a node is set to an error
// - or if XXXstate is reached.
//
// TODO: rename to something better?
scalarKnown
// listTypeKnown indicates that it is known that lists unified with this
// Vertex should be interpreted as integer indexed lists, as associative
// lists, or an error.
//
// This is a signal condition that is reached when:
// - allFieldsKnown is reached (all expressions have )
// - it is unified with an associative list type
listTypeKnown
// fieldConjunctsKnown means that all the conjuncts of all fields are
// known.
fieldConjunctsKnown
// fieldSetKnown means that all fields of this node are known. This is true
// if all tasks that can add a field have been processed and if
// all pending arcs have been resolved.
fieldSetKnown
// // allConjunctsKnown means that all conjuncts have been registered as a
// // task. allParentsProcessed must be true for this to be true.
// allConjunctsKnown
// allTasksCompleted means that all tasks of a Vertex have been completed
// with the exception of validation tasks. A Vertex may still not be
// finalized.
allTasksCompleted
// subFieldsProcessed means that all tasks of a Vertex, including those of
// its arcs have been completed.
//
// This is a signal condition that is met if all arcs have reached the
// the state finalStateKnown.
//
subFieldsProcessed
leftOfMaxCoreCondition
finalStateKnown condition = leftOfMaxCoreCondition - 1
preValidation condition = finalStateKnown //&^ validationCompleted
conditionsUsingCounters = arcTypeKnown |
valueKnown |
fieldConjunctsKnown |
allTasksCompleted
// The xConjunct condition sets indicate a conjunct MAY contribute the to
// final result. For some conjuncts it may not be known what the
// contribution will be. In such a cases the set that reflects all possible
// contributions should be used. For instance, an embedded reference may
// resolve to a scalar or struct.
//
// All conjunct states include allTasksCompleted.
// a genericConjunct is one for which the contributions to the states
// are not known in advance. For instance, an embedded reference can be
// anything. In such case, all conditions are included.
genericConjunct = allTasksCompleted |
scalarKnown |
valueKnown |
fieldConjunctsKnown
// a fieldConjunct is on that only adds a new field to the struct.
fieldConjunct = allTasksCompleted |
fieldConjunctsKnown
// a scalarConjunct is one that is guaranteed to result in a scalar or
// list value.
scalarConjunct = allTasksCompleted |
scalarKnown |
valueKnown
// needsX condition sets are used to indicate which conditions need to be
// met.
needFieldConjunctsKnown = fieldConjunctsKnown |
allAncestorsProcessed
needFieldSetKnown = fieldSetKnown |
allAncestorsProcessed
needTasksDone = allAncestorsProcessed | allTasksCompleted
// concreteKnown means that we know whether a value is concrete or not.
// At the moment this is equal to 'scalarKnown'.
concreteKnown = scalarKnown
)
// schedConfig configures a taskContext with the states needed for the
// CUE evaluator. It is used in OpContext.New as a template for creating
// new taskContexts.
var schedConfig = taskContext{
counterMask: conditionsUsingCounters,
autoUnblock: listTypeKnown | scalarKnown | arcTypeKnown,
complete: stateCompletions,
}
// stateCompletions indicates the completion of conditions based on the
// completions of other conditions.
func stateCompletions(s *scheduler) condition {
x := s.completed
v := s.node.node
s.node.Logf("=== stateCompletions: %v %v", v.Label, s.completed)
if x.meets(allAncestorsProcessed) {
x |= conditionsUsingCounters &^ s.provided
// If we have a pending arc, a sub arc may still cause the arc to
// become not pending. For instance, if 'a' is pending in the following
// if x != _!_ {
// a: b: 1
// }
// it may still become not pending if 'b' becomes a regular arc.
if s.counters[arcTypeKnown] == 0 && x.meets(subFieldsProcessed) {
x |= arcTypeKnown
}
}
switch {
case v.ArcType == ArcMember, v.ArcType == ArcNotPresent:
x |= arcTypeKnown
case x&arcTypeKnown != 0 && v.ArcType == ArcPending:
v.ArcType = ArcNotPresent
}
if x.meets(valueKnown) {
// NOTE: in this case, scalarKnown is not the same as concreteKnown,
// especially if this arc is Pending, as it may still become concrete.
// We probably want to separate this out.
if v.ArcType == ArcMember || v.ArcType == ArcNotPresent {
x |= scalarKnown
}
x |= listTypeKnown
}
if x.meets(needFieldConjunctsKnown | needTasksDone) {
switch {
case x.meets(subFieldsProcessed):
x |= fieldSetKnown
default:
for _, a := range v.Arcs {
if a.ArcType == ArcPending {
return x
}
}
x |= fieldSetKnown
}
}
return x
}
// allChildConjunctsKnown indicates that all conjuncts have been added by
// the parents and every conjunct that may add fields to subfields have been
// processed.
func (v *Vertex) allChildConjunctsKnown() bool {
if v == nil {
return true
}
return v.state.meets(fieldConjunctsKnown | allAncestorsProcessed)
}
func (n *nodeContext) scheduleTask(r *runner, env *Environment, x Node, ci CloseInfo) *task {
t := &task{
run: r,
node: n,
env: env,
id: ci,
x: x,
}
n.insertTask(t)
return t
}
// require ensures that a given condition is met for the given Vertex by
// evaluating it. It yields execution back to the scheduler if it cannot
// be completed at this point.
func (c *OpContext) require(v *Vertex, needs condition) {
state := v.getState(c)
if state == nil {
return
}
state.process(needs, yield)
}
// scalarValue evaluates the given expression and either returns a
// concrete value or schedules the task for later evaluation.
func (ctx *OpContext) scalarValue(t *task, x Expr) Value {
return ctx.value(x, require(0, scalarKnown))
}