1 // Copyright 2020 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 // This file implements the closedness algorithm. 18 19 // Outline of algorithm 20 // 21 // To compute closedness each Vertex is associated with a tree which has 22 // leaf nodes with sets of allowed labels, and interior nodes that describe 23 // how these sets may be combines: Or, for embedding, or And for definitions. 24 // 25 // Each conjunct of a Vertex is associated with such a leaf node. Each 26 // conjunct that evaluates to a struct is added to the list of Structs, which 27 // in the end forms this tree. If a conjunct is embedded, or references another 28 // struct or definition, it adds interior node to reflect this. 29 // 30 // To test whether a feature is allowed, it must satisfy the resulting 31 // expression tree. 32 // 33 // In order to avoid having to copy the tree for each node, the tree is linked 34 // from leaf node to root, rather than the other way around. This allows 35 // parent nodes to be shared as the tree grows and ensures that the growth 36 // of the tree is bounded by the number of conjuncts. As a consequence, this 37 // requires a two-pass algorithm: 38 // 39 // - walk up to mark which nodes are required and count the number of 40 // child nodes that need to be satisfied. 41 // - verify fields in leaf structs and mark parent leafs as satisfied 42 // when appropriate. 43 // 44 // A label is allowed if all required root nodes are marked as accepted after 45 // these two passes. 46 // 47 48 // A note on embeddings: it is important to keep track which conjuncts originate 49 // from an embedding, as an embedded value may eventually turn into a closed 50 // struct. Consider 51 // 52 // a: { 53 // b 54 // d: e: int 55 // } 56 // b: d: { 57 // #A & #B 58 // } 59 // 60 // At the point of evaluating `a`, the struct is not yet closed. However, 61 // descending into `d` will trigger the inclusion of definitions which in turn 62 // causes the struct to be closed. At this point, it is important to know that 63 // `b` originated from an embedding, as otherwise `e` may not be allowed. 64 65 // TODO(perf): 66 // - less nodes 67 // - disable StructInfo nodes that can no longer pass a feature 68 // - sort StructInfos active ones first. 69 70 // TODO(errors): return a dedicated ConflictError that can track original 71 // positions on demand. 72 73 // IsInOneOf reports whether any of the Structs associated with v is contained 74 // within any of the span types in the given mask. 75 func (v *Vertex) IsInOneOf(mask SpanType) bool { 76 for _, s := range v.Structs { 77 if s.CloseInfo.IsInOneOf(mask) { 78 return true 79 } 80 } 81 return false 82 } 83 84 // IsRecursivelyClosed returns true if this value is either a definition or unified 85 // with a definition. 86 func (v *Vertex) IsRecursivelyClosed() bool { 87 return v.Closed || v.IsInOneOf(DefinitionSpan) 88 } 89 90 type closeNodeType uint8 91 92 const ( 93 // a closeRef node is created when there is a non-definition reference. 94 // These nodes are not necessary for computing results, but may be 95 // relevant down the line to group closures through embedded values and 96 // to track position information for failures. 97 closeRef closeNodeType = iota 98 99 // closeDef indicates this node was introduced as a result of referencing 100 // a definition. 101 closeDef 102 103 // closeEmbed indicates this node was added as a result of an embedding. 104 closeEmbed 105 106 _ = closeRef // silence the linter 107 ) 108 109 // TODO: merge with closeInfo: this is a leftover of the refactoring. 110 type CloseInfo struct { 111 *closeInfo // old implementation (TODO: remove) 112 cc *closeContext // new implementation (TODO: rename field to closeCtx) 113 114 // IsClosed is true if this conjunct represents a single level of closing 115 // as indicated by the closed builtin. 116 IsClosed bool 117 118 // FromEmbed indicates whether this conjunct was inserted because of an 119 // embedding. This flag is sticky: it will be set for conjuncts created 120 // from fields defined by this conjunct. 121 // NOTE: only used when using closeContext. 122 FromEmbed bool 123 124 // FromDef indicates whether this conjunct was inserted because of a 125 // definition. This flag is sticky: it will be set for conjuncts created 126 // from fields defined by this conjunct. 127 // NOTE: only used when using closeContext. 128 FromDef bool 129 130 // FieldTypes indicates which kinds of fields (optional, dynamic, patterns, 131 // etc.) are contained in this conjunct. 132 FieldTypes OptionalType 133 134 CycleInfo 135 } 136 137 func (c CloseInfo) Location() Node { 138 if c.closeInfo == nil { 139 return nil 140 } 141 return c.closeInfo.location 142 } 143 144 func (c CloseInfo) span() SpanType { 145 if c.closeInfo == nil { 146 return 0 147 } 148 return c.closeInfo.span 149 } 150 151 func (c CloseInfo) RootSpanType() SpanType { 152 if c.closeInfo == nil { 153 return 0 154 } 155 return c.root 156 } 157 158 // IsInOneOf reports whether c is contained within any of the span types in the 159 // given mask. 160 func (c CloseInfo) IsInOneOf(t SpanType) bool { 161 return c.span()&t != 0 162 } 163 164 // TODO(perf): remove: error positions should always be computed on demand 165 // in dedicated error types. 166 func (c *CloseInfo) AddPositions(ctx *OpContext) { 167 for s := c.closeInfo; s != nil; s = s.parent { 168 if loc := s.location; loc != nil { 169 ctx.AddPosition(loc) 170 } 171 } 172 } 173 174 // TODO(perf): use on StructInfo. Then if parent and expression are the same 175 // it is possible to use cached value. 176 func (c CloseInfo) SpawnEmbed(x Node) CloseInfo { 177 c.closeInfo = &closeInfo{ 178 parent: c.closeInfo, 179 location: x, 180 mode: closeEmbed, 181 root: EmbeddingSpan, 182 span: c.span() | EmbeddingSpan, 183 } 184 return c 185 } 186 187 // SpawnGroup is used for structs that contain embeddings that may end up 188 // closing the struct. This is to force that `b` is not allowed in 189 // 190 // a: {#foo} & {b: int} 191 func (c CloseInfo) SpawnGroup(x Expr) CloseInfo { 192 c.closeInfo = &closeInfo{ 193 parent: c.closeInfo, 194 location: x, 195 span: c.span(), 196 } 197 return c 198 } 199 200 // SpawnSpan is used to track that a value is introduced by a comprehension 201 // or constraint. Definition and embedding spans are introduced with SpawnRef 202 // and SpawnEmbed, respectively. 203 func (c CloseInfo) SpawnSpan(x Node, t SpanType) CloseInfo { 204 c.closeInfo = &closeInfo{ 205 parent: c.closeInfo, 206 location: x, 207 root: t, 208 span: c.span() | t, 209 } 210 return c 211 } 212 213 func (c CloseInfo) SpawnRef(arc *Vertex, isDef bool, x Expr) CloseInfo { 214 span := c.span() 215 found := false 216 if !isDef { 217 xnode := Node(x) // Optimization so we're comparing identical interface types. 218 // TODO: make this work for non-definitions too. 219 for p := c.closeInfo; p != nil; p = p.parent { 220 if p.span == span && p.location == xnode { 221 found = true 222 break 223 } 224 } 225 } 226 if !found { 227 c.closeInfo = &closeInfo{ 228 parent: c.closeInfo, 229 location: x, 230 span: span, 231 } 232 } 233 if isDef { 234 c.mode = closeDef 235 c.closeInfo.root = DefinitionSpan 236 c.closeInfo.span |= DefinitionSpan 237 } 238 return c 239 } 240 241 // IsDef reports whether an expressions is a reference that references a 242 // definition anywhere in its selection path. 243 // 244 // TODO(performance): this should be merged with resolve(). But for now keeping 245 // this code isolated makes it easier to see what it is for. 246 func IsDef(x Expr) bool { 247 switch r := x.(type) { 248 case *FieldReference: 249 return r.Label.IsDef() 250 251 case *SelectorExpr: 252 if r.Sel.IsDef() { 253 return true 254 } 255 return IsDef(r.X) 256 257 case *IndexExpr: 258 return IsDef(r.X) 259 } 260 return false 261 } 262 263 // A SpanType is used to indicate whether a CUE value is within the scope of 264 // a certain CUE language construct, the span type. 265 type SpanType uint8 266 267 const ( 268 // EmbeddingSpan means that this value was embedded at some point and should 269 // not be included as a possible root node in the todo field of OpContext. 270 EmbeddingSpan SpanType = 1 << iota 271 ConstraintSpan 272 ComprehensionSpan 273 DefinitionSpan 274 ) 275 276 type closeInfo struct { 277 // location records the expression that led to this node's introduction. 278 location Node 279 280 // The parent node in the tree. 281 parent *closeInfo 282 283 // TODO(performance): if references are chained, we could have a separate 284 // parent pointer to skip the chain. 285 286 // mode indicates whether this node was added as part of an embedding, 287 // definition or non-definition reference. 288 mode closeNodeType 289 290 // noCheck means this struct is irrelevant for closedness checking. This can 291 // happen when: 292 // - it is a sibling of a new definition. 293 noCheck bool // don't process for inclusion info 294 295 root SpanType 296 span SpanType 297 } 298 299 // closeStats holds the administrative fields for a closeInfo value. Each 300 // closeInfo is associated with a single closeStats value per unification 301 // operator. This association is done through an OpContext. This allows the 302 // same value to be used in multiple concurrent unification operations. 303 // NOTE: there are other parts of the algorithm that are not thread-safe yet. 304 type closeStats struct { 305 // the other fields of this closeStats value are only valid if generation 306 // is equal to the generation in OpContext. This allows for lazy 307 // initialization of closeStats. 308 generation int 309 310 // These counts keep track of how many required child nodes need to be 311 // completed before this node is accepted. 312 requiredCount int 313 acceptedCount int 314 315 // accepted is set if this node is accepted. 316 accepted bool 317 318 required bool 319 320 inTodoList bool // true if added to todo list. 321 next *closeStats 322 } 323 324 func (c *closeInfo) isClosed() bool { 325 return c.mode == closeDef 326 } 327 328 // isClosed reports whether v is closed at this level (so not recursively). 329 func isClosed(v *Vertex) bool { 330 // We could have used IsRecursivelyClosed here, but (effectively) 331 // implementing it again here allows us to only have to iterate over 332 // Structs once. 333 if v.Closed { 334 return true 335 } 336 for _, s := range v.Structs { 337 if s.IsClosed || s.IsInOneOf(DefinitionSpan) { 338 return true 339 } 340 } 341 return false 342 } 343 344 // Accept determines whether f is allowed in n. It uses the OpContext for 345 // caching administrative fields. 346 func Accept(ctx *OpContext, n *Vertex, f Feature) (found, required bool) { 347 ctx.generation++ 348 ctx.todo = nil 349 350 var optionalTypes OptionalType 351 352 // TODO(perf): more aggressively determine whether a struct is open or 353 // closed: open structs do not have to be checked, yet they can particularly 354 // be the ones with performance issues, for instanced as a result of 355 // embedded for comprehensions. 356 for _, s := range n.Structs { 357 if !s.useForAccept() { 358 continue 359 } 360 markCounts(ctx, s.CloseInfo) 361 optionalTypes |= s.types 362 } 363 364 var str Value 365 if f.Index() == MaxIndex { 366 f &= fTypeMask 367 } else if optionalTypes&(HasComplexPattern|HasDynamic) != 0 && f.IsString() { 368 str = f.ToValue(ctx) 369 } 370 371 for _, s := range n.Structs { 372 if !s.useForAccept() { 373 continue 374 } 375 if verifyArc(ctx, s, f, str) { 376 // Beware: don't add to below expression: this relies on the 377 // side effects of markUp. 378 ok := markUp(ctx, s.closeInfo, 0) 379 found = found || ok 380 } 381 } 382 383 // Reject if any of the roots is not accepted. 384 for x := ctx.todo; x != nil; x = x.next { 385 if !x.accepted { 386 return false, true 387 } 388 } 389 390 return found, ctx.todo != nil 391 } 392 393 func markCounts(ctx *OpContext, info CloseInfo) { 394 if info.IsClosed { 395 markRequired(ctx, info.closeInfo) 396 return 397 } 398 for s := info.closeInfo; s != nil; s = s.parent { 399 if s.isClosed() { 400 markRequired(ctx, s) 401 return 402 } 403 } 404 } 405 406 func markRequired(ctx *OpContext, info *closeInfo) { 407 count := 0 408 for ; ; info = info.parent { 409 var s closeInfo 410 if info != nil { 411 s = *info 412 } 413 414 x := getScratch(ctx, info) 415 416 x.requiredCount += count 417 418 if x.required { 419 return 420 } 421 422 if s.span&EmbeddingSpan == 0 && !x.inTodoList { 423 x.next = ctx.todo 424 ctx.todo = x 425 x.inTodoList = true 426 } 427 428 x.required = true 429 430 if info == nil { 431 return 432 } 433 434 count = 0 435 if s.mode != closeEmbed { 436 count = 1 437 } 438 } 439 } 440 441 func markUp(ctx *OpContext, info *closeInfo, count int) bool { 442 for ; ; info = info.parent { 443 var s closeInfo 444 if info != nil { 445 s = *info 446 } 447 448 x := getScratch(ctx, info) 449 450 x.acceptedCount += count 451 452 if x.acceptedCount < x.requiredCount { 453 return false 454 } 455 456 x.accepted = true 457 458 if info == nil { 459 return true 460 } 461 462 count = 0 463 if x.required && s.mode != closeEmbed { 464 count = 1 465 } 466 } 467 } 468 469 // getScratch: explain generation. 470 func getScratch(ctx *OpContext, s *closeInfo) *closeStats { 471 m := ctx.closed 472 if m == nil { 473 m = map[*closeInfo]*closeStats{} 474 ctx.closed = m 475 } 476 477 x := m[s] 478 if x == nil { 479 x = &closeStats{} 480 m[s] = x 481 } 482 483 if x.generation != ctx.generation { 484 *x = closeStats{generation: ctx.generation} 485 } 486 487 return x 488 } 489 490 func verifyArc(ctx *OpContext, s *StructInfo, f Feature, label Value) bool { 491 isRegular := f.IsString() 492 493 o := s.StructLit 494 env := s.Env 495 496 if len(o.Additional) > 0 || o.IsOpen { 497 return true 498 } 499 500 for _, g := range o.Fields { 501 if f == g.Label { 502 return true 503 } 504 } 505 506 if !isRegular { 507 return false 508 } 509 510 // Do not record errors during this validation. 511 errs := ctx.errs 512 defer func() { ctx.errs = errs }() 513 514 if len(o.Dynamic) > 0 && f.IsString() && label != nil { 515 for _, b := range o.Dynamic { 516 v := env.evalCached(ctx, b.Key) 517 v, _ = ctx.getDefault(v) 518 s, ok := Unwrap(v).(*String) 519 if !ok { 520 continue 521 } 522 if label.(*String).Str == s.Str { 523 return true 524 } 525 } 526 } 527 528 for _, b := range o.Bulk { 529 if matchBulk(ctx, env, b, f, label) { 530 return true 531 } 532 } 533 534 // TODO(perf): delay adding this position: create a special error type that 535 // computes all necessary positions on demand. 536 if ctx != nil { 537 ctx.AddPosition(s.StructLit) 538 } 539 540 return false 541 } 542