1 // Copyright 2023 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 15 package adt 16 17 // TODO: clean up following notes: 18 19 // Used in expr.go: 20 // - ctx.value (uses: noncrete scalar allowed, concrete scalar, concrete composite) 21 // - evalState 22 // - ctx.node (need to know all fields) 23 // - ctx.lookup 24 // - ctx.concrete 25 // 26 // - ctx.relLabel 27 // OK: always exists 28 // - ctx.relNode (upcount + unify(partial)) 29 // OK: node always exists. 30 // 31 // - ctx.evalState (in validation of comparison against bottom) 32 // 33 // - arc.Finalize (finalized) 34 // - CompleteArcs (conjuncts) 35 // 36 37 // lookup in p1 38 // - process remaining field todos 39 40 // lookup: 41 // if node is currently processing, just look up directly and create 42 // field with notification. 43 // 44 // if node has not been processed, process once. 45 // 46 // Any dynamic fields should have been triggered by the existence of a new 47 // arc. This will either cascade the evaluation or not. 48 49 // p1: { 50 // (p1.baz): "bar" // t1 51 // (p1.foo): "baz" // t2 52 // baz: "foo" 53 // } 54 // 55 // <p1, fieldsKnown> -> t1 -> <p1.baz, scalar> 56 // <p1.foo, scalar> -> t1 57 // <p1, fieldsKnown> -> t2 -> <p1.foo, scalar> 58 59 // p2: { 60 // (p2[p2.baz]): "bar" 61 // (p2.foo): "baz" 62 // baz: "qux" 63 // qux: "foo" 64 // } 65 66 // b -> a - > b: detected cycle in b: 67 // 68 // xxx register expression (a-10) being processed as a post constraint. 69 // add task to pending. 70 // register value as waiting for scalar to be completed later. 71 // return with cycle/ in complete error. 72 // 73 // - in b: 74 // xxx register expression (b+10) as post constraint. 75 // add task to pending 76 // register value as waiting for scalar to be completed later. 77 // 5 is processed and set 78 // this completes the task in b 79 // this sets a scalar in b 80 // this completes the expression in a 81 // 82 // b: a - 10 83 // a: b + 10 84 // a: 5 85 // 86 // a: a 87 // a: 5 88 // 89 90 // These are the condition types of the CUE evaluator. A scheduler 91 // is associated with a single Vertex. So when these states refer to a Vertex, 92 // it is the Vertex associated with the scheduler. 93 // 94 // There are core conditions and condition sets. The core conditions are 95 // determined during operation as conditions are met. The condition sets are 96 // used to indicate a set of required or provided conditions. 97 // 98 // Core conditions can be signal conditions or counter conditions. A counter 99 // condition is triggered if all conjuncts that contribute to the computation 100 // of this condition have been met. A signal condition is triggered as soon as 101 // evidence is found that this condition is met. Unless otherwise specified, 102 // conditions are counter conditions. 103 const ( 104 // allAncestorsProcessed indicates that all conjuncts that could be added 105 // to the Vertex by any of its ancestors have been added. In other words, 106 // all ancestors schedulers have reached the state fieldConjunctsKnown. 107 // 108 // This is a signal condition. It is explicitly set in unify when a 109 // parent meets fieldConjunctsKnown|allAncestorsProcessed. 110 allAncestorsProcessed condition = 1 << iota 111 112 // Really: all ancestor subfield tasks processed. 113 114 // arcTypeKnown means that the ArcType value of a Vertex is fully 115 // determined. The ArcType of all fields of a Vertex need to be known 116 // before the complete set of fields of this Vertex can be known. 117 arcTypeKnown 118 119 // valueKnown means that it is known what the "type" of the value would be 120 // if present. 121 valueKnown 122 123 // scalarKnown indicates that a Vertex has either a concrete scalar value or 124 // that it is known that it will never have a scalar value. 125 // 126 // This is a signal condition that is reached when: 127 // - a node is set to a concrete scalar value 128 // - a node is set to an error 129 // - or if XXXstate is reached. 130 // 131 // TODO: rename to something better? 132 scalarKnown 133 134 // listTypeKnown indicates that it is known that lists unified with this 135 // Vertex should be interpreted as integer indexed lists, as associative 136 // lists, or an error. 137 // 138 // This is a signal condition that is reached when: 139 // - allFieldsKnown is reached (all expressions have ) 140 // - it is unified with an associative list type 141 listTypeKnown 142 143 // fieldConjunctsKnown means that all the conjuncts of all fields are 144 // known. 145 fieldConjunctsKnown 146 147 // fieldSetKnown means that all fields of this node are known. This is true 148 // if all tasks that can add a field have been processed and if 149 // all pending arcs have been resolved. 150 fieldSetKnown 151 152 // // allConjunctsKnown means that all conjuncts have been registered as a 153 // // task. allParentsProcessed must be true for this to be true. 154 // allConjunctsKnown 155 156 // allTasksCompleted means that all tasks of a Vertex have been completed 157 // with the exception of validation tasks. A Vertex may still not be 158 // finalized. 159 allTasksCompleted 160 161 // subFieldsProcessed means that all tasks of a Vertex, including those of 162 // its arcs have been completed. 163 // 164 // This is a signal condition that is met if all arcs have reached the 165 // the state finalStateKnown. 166 // 167 subFieldsProcessed 168 169 leftOfMaxCoreCondition 170 171 finalStateKnown condition = leftOfMaxCoreCondition - 1 172 173 preValidation condition = finalStateKnown //&^ validationCompleted 174 175 conditionsUsingCounters = arcTypeKnown | 176 valueKnown | 177 fieldConjunctsKnown | 178 allTasksCompleted 179 180 // The xConjunct condition sets indicate a conjunct MAY contribute the to 181 // final result. For some conjuncts it may not be known what the 182 // contribution will be. In such a cases the set that reflects all possible 183 // contributions should be used. For instance, an embedded reference may 184 // resolve to a scalar or struct. 185 // 186 // All conjunct states include allTasksCompleted. 187 188 // a genericConjunct is one for which the contributions to the states 189 // are not known in advance. For instance, an embedded reference can be 190 // anything. In such case, all conditions are included. 191 genericConjunct = allTasksCompleted | 192 scalarKnown | 193 valueKnown | 194 fieldConjunctsKnown 195 196 // a fieldConjunct is on that only adds a new field to the struct. 197 fieldConjunct = allTasksCompleted | 198 fieldConjunctsKnown 199 200 // a scalarConjunct is one that is guaranteed to result in a scalar or 201 // list value. 202 scalarConjunct = allTasksCompleted | 203 scalarKnown | 204 valueKnown 205 206 // needsX condition sets are used to indicate which conditions need to be 207 // met. 208 209 needFieldConjunctsKnown = fieldConjunctsKnown | 210 allAncestorsProcessed 211 212 needFieldSetKnown = fieldSetKnown | 213 allAncestorsProcessed 214 215 needTasksDone = allAncestorsProcessed | allTasksCompleted 216 217 // concreteKnown means that we know whether a value is concrete or not. 218 // At the moment this is equal to 'scalarKnown'. 219 concreteKnown = scalarKnown 220 ) 221 222 // schedConfig configures a taskContext with the states needed for the 223 // CUE evaluator. It is used in OpContext.New as a template for creating 224 // new taskContexts. 225 var schedConfig = taskContext{ 226 counterMask: conditionsUsingCounters, 227 autoUnblock: listTypeKnown | scalarKnown | arcTypeKnown, 228 complete: stateCompletions, 229 } 230 231 // stateCompletions indicates the completion of conditions based on the 232 // completions of other conditions. 233 func stateCompletions(s *scheduler) condition { 234 x := s.completed 235 v := s.node.node 236 s.node.Logf("=== stateCompletions: %v %v", v.Label, s.completed) 237 if x.meets(allAncestorsProcessed) { 238 x |= conditionsUsingCounters &^ s.provided 239 // If we have a pending arc, a sub arc may still cause the arc to 240 // become not pending. For instance, if 'a' is pending in the following 241 // if x != _!_ { 242 // a: b: 1 243 // } 244 // it may still become not pending if 'b' becomes a regular arc. 245 if s.counters[arcTypeKnown] == 0 && x.meets(subFieldsProcessed) { 246 x |= arcTypeKnown 247 } 248 } 249 switch { 250 case v.ArcType == ArcMember, v.ArcType == ArcNotPresent: 251 x |= arcTypeKnown 252 case x&arcTypeKnown != 0 && v.ArcType == ArcPending: 253 v.ArcType = ArcNotPresent 254 } 255 256 if x.meets(valueKnown) { 257 // NOTE: in this case, scalarKnown is not the same as concreteKnown, 258 // especially if this arc is Pending, as it may still become concrete. 259 // We probably want to separate this out. 260 if v.ArcType == ArcMember || v.ArcType == ArcNotPresent { 261 x |= scalarKnown 262 } 263 x |= listTypeKnown 264 } 265 266 if x.meets(needFieldConjunctsKnown | needTasksDone) { 267 switch { 268 case x.meets(subFieldsProcessed): 269 x |= fieldSetKnown 270 default: 271 for _, a := range v.Arcs { 272 if a.ArcType == ArcPending { 273 return x 274 } 275 } 276 x |= fieldSetKnown 277 } 278 } 279 return x 280 } 281 282 // allChildConjunctsKnown indicates that all conjuncts have been added by 283 // the parents and every conjunct that may add fields to subfields have been 284 // processed. 285 func (v *Vertex) allChildConjunctsKnown() bool { 286 if v == nil { 287 return true 288 } 289 290 return v.state.meets(fieldConjunctsKnown | allAncestorsProcessed) 291 } 292 293 func (n *nodeContext) scheduleTask(r *runner, env *Environment, x Node, ci CloseInfo) *task { 294 t := &task{ 295 run: r, 296 node: n, 297 298 env: env, 299 id: ci, 300 x: x, 301 } 302 n.insertTask(t) 303 return t 304 } 305 306 // require ensures that a given condition is met for the given Vertex by 307 // evaluating it. It yields execution back to the scheduler if it cannot 308 // be completed at this point. 309 func (c *OpContext) require(v *Vertex, needs condition) { 310 state := v.getState(c) 311 if state == nil { 312 return 313 } 314 state.process(needs, yield) 315 } 316 317 // scalarValue evaluates the given expression and either returns a 318 // concrete value or schedules the task for later evaluation. 319 func (ctx *OpContext) scalarValue(t *task, x Expr) Value { 320 return ctx.value(x, require(0, scalarKnown)) 321 } 322