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 import ( 18 "fmt" 19 ) 20 21 // This file holds the logic for the insertion of fields and pattern 22 // constraints, including tracking closedness. 23 // 24 // 25 // DESIGN GOALS 26 // 27 // Key to performance is to fail early during evaluation. This is especially 28 // true for disjunctions. In CUE evaluation, conjuncts may be evaluated in a 29 // fairly arbitrary order. We want to retain this flexibility while also failing 30 // on disallowed fields as soon as we have enough data to tell for certain. 31 // 32 // Keeping track of which fields are allowed means keeping provenance data on 33 // whether certain conjuncts originate from embeddings or definitions, as well 34 // as how they group together with other conjuncts. These data structure should 35 // allow for a "mark and unwind" approach to allow for backtracking when 36 // computing disjunctions. 37 // 38 // References to the same CUE value may be added as conjuncts through various 39 // paths. For instance, a reference to a definition may be added directly, or 40 // through embedding. How they are added affects which set of fields are 41 // allowed. This can make the removal of duplicate conjuncts hard. A solution 42 // should make it straightforward to deduplicate conjuncts if they have the same 43 // impact on field inclusion. 44 // 45 // All conjuncts associated with field constraints, including optional fields 46 // and pattern constraints, should be collated, deduplicated, and evaluated as 47 // if they were regular fields. This allows comparisons between values to be 48 // meaningful and helps to filter disjuncts. 49 // 50 // The provenance data generated by this algorithm should ideally be easily 51 // usable in external APIs. 52 // 53 // 54 // DATA STRUCTURES 55 // 56 // Conjuncts 57 // 58 // To keep track of conjunct provenance, each conjunct has a few flags that 59 // indicates whether it orignates from 60 // - an embedding 61 // - a definition 62 // - a reference (optional and unimplemented) 63 // 64 // Conjuncts with the same origin are represented as a single Conjunct in the 65 // Vertex, where this conjunct is a list of these conjuncts. In other words, the 66 // conjuncts of a Vertex are really a forest (group of trees) of conjuncts that, 67 // recursively, reflect the provenance of the conjuncts contained within it. 68 // 69 // The current implementation uses a Vertex for listing conjuncts with the same 70 // origin. This Vertex is marked as "Dynamic", as it does not have a CUE path 71 // that leads to them. 72 // 73 // 74 // Constraints 75 // 76 // Vertex values separately keep track of pattern constraints. These consist of 77 // a list of patterns with associated conjuncts, and a CUE expression that 78 // represents the set of allowed fields. This information is mostly for equality 79 // checking: by the time this data is produced, conjuncts associated with 80 // patterns are already inserted into the computed subfields. 81 // 82 // Note that this representation assumes that patterns are always accrued 83 // cumulatively: a field that is allowed will accrue the conjuncts of any 84 // matched pattern, even if it originates from an embedding that itself does not 85 // allow this field. 86 // 87 // 88 // ALGORITHM 89 // 90 // When processing the conjuncts of a Vertex, subfields are tracked per 91 // "grouping" (the list of conjuncts of the same origin). Each grouping keeps a 92 // counter of the number of unprocessed conjuncts and subgroups associated with 93 // it. Field inclusion (closedness) can be computed as soon as all subconjuncts 94 // and subgroups are processed. 95 // 96 // Conjuncts of subfields are inserted in such a way that they reflect the same 97 // grouping as the parent Vertex, plus any grouping that may be added by the 98 // subfield itself. 99 // 100 // It would be possible, though, to collapse certain (combinations of) groups 101 // that contain only a single conjunct. This can limit the size of such conjunct 102 // trees. 103 // 104 // As conjuncts are added within their grouping context, it is possible to 105 // uniquely identify conjuncts only by Vertex and expression pointer, 106 // disregarding the Environment. 107 // 108 // 109 // EXAMPLE DATA STRUCTURE 110 // 111 // a: #A 112 // #A: { 113 // #B 114 // x: r1 115 // } 116 // #B: y: r2 117 // r1: z: r3 118 // r2: 2 119 // r3: foo: 2 120 // 121 // gets evaluated into: 122 // 123 // V_a: Arcs{ 124 // x: V_x [ V_def(#A)[ r1 ] ] 125 // y: V_y [ V_def(#A)[ V_embed(#B)[ r2 ] ] ] 126 // } 127 // 128 // When evaluating V_x, its Arcs, in turn become: 129 // 130 // V_x: Arcs{ 131 // z: V_z [ V_def(#A)[ V_ref(r1)[ r3 ]) ]] 132 // } 133 // 134 // The V_def(#A) is necessary here to ensure that closedness information can be 135 // computed, if necessary. The V_ref's, however, are optional, and can be 136 // omitted if provenance is less important: 137 // 138 // V_x: Arcs{ 139 // z: V_z [ V_def(#A)[ r3 ]] 140 // } 141 // 142 // Another possible optimization is to eliminate Vertices if there is only one 143 // conjunct: the embedding and definition flags in the conjunct can be 144 // sufficient in that case. The provenance data could potentially be derived 145 // from the Environment in that case. If an embedding conjunct is itself the 146 // only conjunct in a list, the embedding bit can be eliminated. So V_y in the 147 // above example could be reduced to 148 // 149 // V_y [ V_def(#A)[ r2 ] ] 150 // 151 152 // TODO(perf): 153 // - the data structures could probably be collapsed with Conjunct. and the 154 // Vertex inserted into the Conjuncts could be a special ConjunctGroup. 155 156 type closeContext struct { 157 // Used to recursively insert Vertices. 158 parent *closeContext 159 160 dependencies []*ccDep // For testing only. See debug.go 161 162 // externalDeps lists the closeContexts associated with a root node for 163 // which there are outstanding decrements (can only be NOTIFY or ARC). This 164 // is used to break counter cycles, if necessary. 165 // 166 // This is only used for root closedContext and only for debugging. 167 // TODO: move to nodeContext. 168 externalDeps []ccArcRef 169 170 // child links to a sequence which additional patterns need to be verified 171 // against (&&). If there are more than one, these additional nodes are 172 // linked with next. Only closed nodes with patterns are added. Arc sets are 173 // already merged during processing. 174 child *closeContext 175 176 // next holds a linked list of nodes to process. 177 // See comments above and see linkPatterns. 178 next *closeContext 179 180 // if conjunctCount is 0, pattern constraints can be merged and the 181 // closedness can be checked. To ensure that this is true, there should 182 // be an additional increment at the start before any processing is done. 183 conjunctCount int 184 185 src *Vertex 186 187 // isDef indicates whether the closeContext is created as part of a 188 // definition. 189 isDef bool 190 191 // hasEllipsis indicates whether the node contains an ellipsis. 192 hasEllipsis bool 193 194 // hasTop indicates a node has at least one top conjunct. 195 hasTop bool 196 197 // hasNonTop indicates a node has at least one conjunct that is not top. 198 hasNonTop bool 199 200 // isClosedOnce is true if this closeContext is the result of calling the 201 // close builtin. 202 isClosedOnce bool 203 204 // isEmbed indicates whether the closeContext is created as part of an 205 // embedding. 206 isEmbed bool 207 208 // isClosed is true if a node is a def, it became closed because of a 209 // reference or if it is closed by the close builtin. 210 // 211 // isClosed must only be set to true if all fields and pattern constraints 212 // that define the domain of the node have been added. 213 isClosed bool 214 215 // isTotal is true if a node contains an ellipsis and is defined for all 216 // values. 217 isTotal bool 218 219 // done is true if all dependencies have been decremented. 220 done bool 221 222 // isDecremented is used to keep track of whether the evaluator decremented 223 // a closedContext for the ROOT depKind. 224 isDecremented bool 225 226 // needsCloseInSchedule is non-nil if a closeContext that was created 227 // as an arc still needs to be decremented. It points to the creating arc 228 // for reporting purposes. 229 needsCloseInSchedule *closeContext 230 231 // parentConjuncts represent the parent of this embedding or definition. 232 // Any closeContext is represented by a ConjunctGroup in parent of the 233 // expression tree. 234 parentConjuncts conjunctGrouper 235 // TODO: Only needed if more than one conjuncts. 236 237 // arcs represents closeContexts for sub fields and notification targets 238 // associated with this node that reflect the same point in the expression 239 // tree as this closeContext. In both cases the are keyed by Vertex. 240 arcs []ccArc 241 242 // parentIndex is the position in the parent's arcs slice that corresponds 243 // to this closeContext. This is currently unused. The intention is to use 244 // this to allow groups with single elements (which will be the majority) 245 // to be represented in place in the parent. 246 parentIndex int 247 248 group *ConjunctGroup 249 250 // Patterns contains all patterns of the current closeContext. 251 // It is used in the construction of Expr. 252 Patterns []Value 253 254 // Expr contains the Expr that is used for checking whether a Feature 255 // is allowed in this context. It is only complete after the full 256 // context has been completed, but it can be used for initial checking 257 // once isClosed is true. 258 Expr Value 259 } 260 261 // Label is a convenience function to return the label of the associated Vertex. 262 func (c *closeContext) Label() Feature { 263 return c.src.Label 264 } 265 266 type ccArc struct { 267 kind depKind 268 decremented bool 269 key *closeContext 270 cc *closeContext 271 } 272 273 // A ccArcRef x refers to the x.src.arcs[x.index]. 274 // We use this instead of pointers, because the address may change when 275 // growing a slice. We use this instead mechanism instead of a pointers so 276 // that we do not need to maintain separate free buffers once we use pools of 277 // closeContext. 278 type ccArcRef struct { 279 src *closeContext 280 index int 281 } 282 283 type conjunctGrouper interface { 284 assignConjunct(root *closeContext, c Conjunct, check, checkClosed bool) (arc *closeContext, pos int, added bool) 285 } 286 287 func (n *nodeContext) getArc(f Feature, mode ArcType) (arc *Vertex, isNew bool) { 288 v := n.node 289 for _, a := range v.Arcs { 290 if a.Label == f { 291 if f.IsLet() { 292 a.MultiLet = true 293 // TODO: add return here? 294 } 295 a.updateArcType(mode) 296 return a, false 297 } 298 } 299 300 arc = &Vertex{ 301 Parent: v, 302 Label: f, 303 ArcType: mode, 304 nonRooted: v.IsDynamic || v.Label.IsLet() || v.nonRooted, 305 } 306 if n.scheduler.frozen&fieldSetKnown != 0 { 307 b := n.ctx.NewErrf("field %v not allowed by earlier comprehension or reference cycle", f) 308 n.ctx.AddBottom(b) 309 // This may panic for list arithmetic. Safer to leave out for now. 310 arc.ArcType = ArcNotPresent 311 } 312 v.Arcs = append(v.Arcs, arc) 313 return arc, true 314 } 315 316 func (v *Vertex) assignConjunct(root *closeContext, c Conjunct, check, checkClosed bool) (a *closeContext, pos int, added bool) { 317 // TODO: consider clearing CloseInfo.cc. 318 // c.CloseInfo.cc = nil 319 320 arc := root.src 321 322 pos = len(arc.Conjuncts) 323 324 added = !check || !arc.hasConjunct(c) 325 if added { 326 c.CloseInfo.cc = root 327 arc.addConjunctUnchecked(c) 328 } 329 330 return root, pos, added 331 } 332 333 func (cc *closeContext) getKeyedCC(key *closeContext, c CycleInfo, checkClosed bool) *closeContext { 334 for _, a := range cc.arcs { 335 if a.key == key { 336 return a.cc 337 } 338 } 339 340 group := &ConjunctGroup{} 341 342 if cc.parentConjuncts == cc { 343 panic("parent is self") 344 } 345 346 parent, pos, _ := cc.parentConjuncts.assignConjunct(key, Conjunct{ 347 CloseInfo: CloseInfo{ 348 FromDef: cc.isDef, 349 FromEmbed: cc.isEmbed, 350 CycleInfo: c, 351 }, 352 x: group, 353 }, false, checkClosed) 354 355 arc := &closeContext{ 356 parent: parent, 357 parentConjuncts: parent, 358 parentIndex: pos, 359 360 src: key.src, 361 group: group, 362 363 isDef: cc.isDef, 364 isEmbed: cc.isEmbed, 365 needsCloseInSchedule: cc, 366 } 367 368 arc.parent.incDependent(PARENT, arc) 369 370 // If the parent, w.r.t. the subfield relation was already processed, 371 // there is no need to register the notification. 372 arc.incDependent(EVAL, cc) // matched in REF(decrement:nodeDone) 373 374 // A let field never depends on its parent. So it is okay to filter here. 375 if !arc.Label().IsLet() { 376 // prevent a dependency on self. 377 if key.src != cc.src { 378 cc.addDependency(ARC, key, arc, key) 379 } 380 } 381 382 v := key.src 383 if checkClosed && v.Parent != nil && v.Parent.state != nil { 384 v.Parent.state.checkArc(cc, v) 385 } 386 387 return arc 388 } 389 390 func (cc *closeContext) linkNotify(dst *Vertex, key *closeContext, c CycleInfo) bool { 391 for _, a := range cc.arcs { 392 if a.key == key { 393 return false 394 } 395 } 396 397 cc.addDependency(NOTIFY, key, key, dst.cc) 398 return true 399 } 400 401 func (cc *closeContext) assignConjunct(root *closeContext, c Conjunct, check, checkClosed bool) (arc *closeContext, pos int, added bool) { 402 arc = cc.getKeyedCC(root, c.CloseInfo.CycleInfo, checkClosed) 403 404 pos = len(*arc.group) 405 406 c.CloseInfo.cc = nil 407 added = !check || !hasConjunct(*arc.group, c) 408 if added { 409 c.CloseInfo.cc = arc 410 411 if c.CloseInfo.cc.src != arc.src { 412 panic("Inconsistent src") 413 } 414 *arc.group = append(*arc.group, c) 415 } 416 417 return arc, pos, added 418 } 419 420 // spawnCloseContext wraps the closeContext in c with a new one and returns 421 // this new context along with an updated CloseInfo. The new values reflect 422 // that the set of fields represented by c are now, for instance, enclosed in 423 // an embedding or a definition. 424 // 425 // This call is used when preparing ADT values for evaluation. 426 func (c CloseInfo) spawnCloseContext(t closeNodeType) (CloseInfo, *closeContext) { 427 cc := c.cc 428 if cc == nil { 429 panic("nil closeContext") 430 } 431 432 c.cc = &closeContext{ 433 parent: cc, 434 src: cc.src, 435 parentConjuncts: cc, 436 } 437 438 cc.incDependent(PARENT, c.cc) // REF(decrement: spawn) 439 440 switch t { 441 case closeDef: 442 c.cc.isDef = true 443 case closeEmbed: 444 c.cc.isEmbed = true 445 } 446 447 return c, c.cc 448 } 449 450 // addDependency adds a dependent arc to c. If child is an arc, child.src == key 451 func (c *closeContext) addDependency(kind depKind, key, child, root *closeContext) { 452 // NOTE: do not increment 453 // - either root closeContext or otherwise resulting from sub closeContext 454 // all conjuncts will be added now, notified, or scheduled as task. 455 456 child.incDependent(kind, c) // matched in decDependent REF(arcs) 457 458 for _, a := range c.arcs { 459 if a.key == key { 460 panic("addArc: Label already exists") 461 } 462 } 463 464 // TODO: this tests seems sensible, but panics. Investigate what could 465 // trigger this. 466 // if child.src.Parent != c.src { 467 // panic("addArc: inconsistent parent") 468 // } 469 if child.src.cc != root.src.cc { 470 panic("addArc: inconsistent root") 471 } 472 c.arcs = append(c.arcs, ccArc{ 473 kind: kind, 474 key: key, 475 cc: child, 476 }) 477 root.externalDeps = append(root.externalDeps, ccArcRef{ 478 src: c, 479 index: len(c.arcs) - 1, 480 }) 481 } 482 483 // incDependent needs to be called for any conjunct or child closeContext 484 // scheduled for c that is queued for later processing and not scheduled 485 // immediately. 486 func (c *closeContext) incDependent(kind depKind, dependant *closeContext) (debug *ccDep) { 487 if c.src == nil { 488 panic("incDependent: unexpected nil state") 489 } 490 491 debug = c.addDependent(kind, dependant) 492 493 if c.done { 494 ctx := c.src.state.ctx 495 openDebugGraph(ctx, c.src, "incDependent: already checked") 496 497 panic(fmt.Sprintf("incDependent: already closed: %p", c)) 498 } 499 500 c.conjunctCount++ 501 return debug 502 } 503 504 // decDependent needs to be called for any conjunct or child closeContext for 505 // which a corresponding incDependent was called after it has been successfully 506 // processed. 507 func (c *closeContext) decDependent(ctx *OpContext, kind depKind, dependant *closeContext) { 508 v := c.src 509 510 c.matchDecrement(v, kind, dependant) 511 512 if c.conjunctCount == 0 { 513 panic(fmt.Sprintf("negative reference counter %d %p", c.conjunctCount, c)) 514 } 515 516 c.conjunctCount-- 517 if c.conjunctCount > 0 { 518 return 519 } 520 521 c.done = true 522 523 p := c.parent 524 525 if c.isDef && !c.hasEllipsis && (!c.hasTop || c.hasNonTop) { 526 c.isClosed = true 527 if p != nil { 528 p.isDef = true 529 } 530 } 531 532 if c.isClosedOnce { 533 c.isClosed = true 534 if p != nil { 535 p.isClosedOnce = true 536 } 537 } 538 539 for i, a := range c.arcs { 540 cc := a.cc 541 if a.decremented { 542 continue 543 } 544 c.arcs[i].decremented = true 545 cc.decDependent(ctx, a.kind, c) // REF(arcs) 546 } 547 548 c.finalizePattern() 549 550 if p == nil { 551 // Root pattern, set allowed patterns. 552 if pcs := v.PatternConstraints; pcs != nil { 553 if pcs.Allowed != nil { 554 panic("unexpected allowed set") 555 } 556 pcs.Allowed = c.Expr 557 return 558 } 559 return 560 } 561 562 if c.hasEllipsis { 563 p.hasEllipsis = true 564 } 565 if c.hasTop { 566 p.hasTop = true 567 } 568 if c.hasNonTop { 569 p.hasNonTop = true 570 } 571 572 if !c.isEmbed && c.isClosed { 573 // Merge the two closeContexts and ensure that the patterns and fields 574 // are mutually compatible according to the closedness rules. 575 injectClosed(ctx, c, p) 576 p.Expr = mergeConjunctions(p.Expr, c.Expr) 577 } else { 578 // Do not check closedness of fields for embeddings. 579 // The pattern constraints of the embedding still need to be added 580 // to the current context. 581 p.linkPatterns(c) 582 } 583 584 p.decDependent(ctx, PARENT, c) // REF(decrement: spawn) 585 586 // If we have started decrementing a child closeContext, the parent started 587 // as well. If it is still marked as needing an EVAL decrement, which can 588 // happen if processing started before the node was added, it is safe to 589 // decrement it now. In this case the NOTIFY and ARC dependencies will keep 590 // the nodes alive until they can be completed. 591 if dep := p.needsCloseInSchedule; dep != nil { 592 p.needsCloseInSchedule = nil 593 p.decDependent(ctx, EVAL, dep) 594 } 595 } 596 597 // linkPatterns merges the patterns of child into c, if needed. 598 func (c *closeContext) linkPatterns(child *closeContext) { 599 if len(child.Patterns) > 0 { 600 child.next = c.child 601 c.child = child 602 } 603 } 604 605 // checkArc validates that the node corresponding to cc allows a field with 606 // label v.Label. 607 func (n *nodeContext) checkArc(cc *closeContext, v *Vertex) *Vertex { 608 f := v.Label 609 ctx := n.ctx 610 611 if f.IsHidden() || f.IsLet() { 612 return v 613 } 614 615 if cc.isClosed && !matchPattern(ctx, cc.Expr, f) { 616 ctx.notAllowedError(n.node, v) 617 } 618 if n.scheduler.frozen&fieldSetKnown != 0 { 619 for _, a := range n.node.Arcs { 620 if a.Label == f { 621 return v 622 } 623 } 624 var b *Bottom 625 // TODO: include cycle data and improve error message. 626 if f.IsInt() { 627 b = ctx.NewErrf( 628 "element at index %v not allowed by earlier comprehension or reference cycle", f) 629 } else { 630 b = ctx.NewErrf( 631 "field %v not allowed by earlier comprehension or reference cycle", f) 632 } 633 v.SetValue(ctx, b) 634 } 635 636 return v 637 } 638 639 // insertConjunct inserts conjunct c into cc. 640 func (cc *closeContext) insertConjunct(key *closeContext, c Conjunct, id CloseInfo, check, checkClosed bool) bool { 641 arc, _, added := cc.assignConjunct(key, c, check, checkClosed) 642 if key.src != arc.src { 643 panic("inconsistent src") 644 } 645 646 if !added { 647 return false 648 } 649 650 if n := key.src.state; n != nil { 651 c.CloseInfo.cc = nil 652 id.cc = arc 653 n.scheduleConjunct(c, id) 654 655 for _, rec := range n.notify { 656 if n.node.ArcType == ArcPending { 657 panic("unexpected pending arc") 658 } 659 cc.insertConjunct(rec.cc, c, id, check, checkClosed) 660 } 661 } 662 663 return true 664 } 665 666 // insertArc inserts conjunct c into n. If check is true it will not add c if it 667 // was already added. 668 // Returns the arc of n.node with label f. 669 func (n *nodeContext) insertArc(f Feature, mode ArcType, c Conjunct, id CloseInfo, check bool) *Vertex { 670 if n == nil { 671 panic("nil nodeContext") 672 } 673 if n.node == nil { 674 panic("nil node") 675 } 676 cc := id.cc 677 if cc == nil { 678 panic("nil closeContext") 679 } 680 681 v, insertedArc := n.getArc(f, mode) 682 683 if v.ArcType == ArcNotPresent { 684 n.node.reportFieldCycleError(n.ctx, c.Source().Pos(), f) 685 return v 686 } 687 688 if !cc.insertConjunct(v.rootCloseContext(), c, id, check, true) { 689 return v 690 } 691 692 if !insertedArc { 693 return v 694 } 695 696 // Match and insert patterns. 697 if pcs := n.node.PatternConstraints; pcs != nil { 698 for _, pc := range pcs.Pairs { 699 if matchPattern(n.ctx, pc.Pattern, f) { 700 for _, c := range pc.Constraint.Conjuncts { 701 n.addConstraint(v, mode, c, check) 702 } 703 } 704 } 705 } 706 707 return v 708 } 709 710 // addConstraint adds a constraint to arc of n. 711 // 712 // In order to resolve LabelReferences, it is not always possible to walk up 713 // the parent Vertex chain to determan the label, because a label reference 714 // may point past a point of referral. For instance, 715 // 716 // test: [ID=_]: name: ID 717 // test: A: {} 718 // B: test.A & {} // B.name should be "A", not "B". 719 // 720 // The arc must be the node arc to which the conjunct is added. 721 func (n *nodeContext) addConstraint(arc *Vertex, mode ArcType, c Conjunct, check bool) { 722 // TODO(perf): avoid cloning the Environment, if: 723 // - the pattern constraint has no LabelReference 724 // (require compile-time support) 725 // - there are no references in the conjunct pointing to this node. 726 // - consider adding this value to the Conjunct struct 727 f := arc.Label 728 bulkEnv := *c.Env 729 bulkEnv.DynamicLabel = f 730 c.Env = &bulkEnv 731 732 // TODO(constraintNode): this should ideally be 733 // cc := id.cc 734 // or 735 // cc := c.CloseInfo.cc.src.cc 736 // 737 // Where id is the closeContext corresponding to the field, or the root 738 // context. But it is a bit hard to figure out how to account for this, as 739 // either this information is not available or the root context results in 740 // errors for the other use of addConstraint. For this reason, we keep 741 // things symmetric for now and will keep things as is, just avoiding the 742 // closedness check. 743 cc := c.CloseInfo.cc 744 745 arc, _ = n.getArc(f, mode) 746 747 root := arc.rootCloseContext() 748 cc.insertConjunct(root, c, c.CloseInfo, check, false) 749 } 750 751 func (n *nodeContext) insertPattern(pattern Value, c Conjunct) { 752 ctx := n.ctx 753 cc := c.CloseInfo.cc 754 755 // Collect patterns in root vertex. This allows comparing disjuncts for 756 // equality as well as inserting new arcs down the line as they are 757 // inserted. 758 if !n.insertConstraint(pattern, c) { 759 return 760 } 761 762 // Match against full set of arcs from root, but insert in current vertex. 763 // Hypothesis: this may not be necessary. Maybe for closedness. 764 // TODO: may need to replicate the closedContext for patterns. 765 // Also: Conjuncts for matching other arcs in this node may be different 766 // for matching arcs using v.foo?, if we need to ensure that conjuncts 767 // from arcs and patterns are grouped under the same vertex. 768 // TODO: verify. See test Pattern 1b 769 for _, a := range n.node.Arcs { 770 if matchPattern(n.ctx, pattern, a.Label) { 771 // TODO: is it necessary to check for uniqueness here? 772 n.addConstraint(a, a.ArcType, c, true) 773 } 774 } 775 776 if cc.isTotal { 777 return 778 } 779 if isTotal(pattern) { 780 cc.isTotal = true 781 cc.Patterns = cc.Patterns[:0] 782 return 783 } 784 785 // insert pattern in current set. 786 // TODO: normalize patterns 787 // TODO: do we only need to do this for closed contexts? 788 for _, pc := range cc.Patterns { 789 if Equal(ctx, pc, pattern, 0) { 790 return 791 } 792 } 793 cc.Patterns = append(cc.Patterns, pattern) 794 } 795 796 // isTotal reports whether pattern value p represents a full domain, that is, 797 // whether it is of type BasicType or Top. 798 func isTotal(p Value) bool { 799 switch p.(type) { 800 case *BasicType: 801 return true 802 case *Top: 803 return true 804 } 805 return false 806 } 807 808 // injectClosed updates dst so that it only allows fields allowed by closed. 809 // 810 // It first ensures that the fields contained in dst are allowed by the fields 811 // and patterns defined in closed. It reports an error in the nodeContext if 812 // this is not the case. 813 func injectClosed(ctx *OpContext, closed, dst *closeContext) { 814 // TODO: check that fields are not void arcs. 815 outer: 816 for _, a := range dst.arcs { 817 ca := a.cc 818 f := ca.Label() 819 if f.IsHidden() || f.IsLet() { 820 continue 821 } 822 for _, b := range closed.arcs { 823 cb := b.cc 824 if f == cb.Label() { 825 continue outer 826 } 827 } 828 if !matchPattern(ctx, closed.Expr, ca.Label()) { 829 ctx.notAllowedError(closed.src, ca.src) 830 continue 831 } 832 } 833 834 if !dst.isClosed { 835 // Since dst is not closed, it is safe to take all patterns from 836 // closed. 837 // This is only necessary for passing up patterns into embeddings. For 838 // (the conjunction of) definitions the construction is handled 839 // elsewhere. 840 // TODO(perf): reclaim slice memory 841 dst.Patterns = closed.Patterns 842 843 dst.isClosed = true 844 } 845 } 846 847 func (ctx *OpContext) addPositions(c Conjunct) { 848 if x, ok := c.x.(*ConjunctGroup); ok { 849 for _, c := range *x { 850 ctx.addPositions(c) 851 } 852 } 853 if pos := c.Field(); pos != nil { 854 ctx.AddPosition(pos) 855 } 856 } 857 858 // notAllowedError reports a field not allowed error in n and sets the value 859 // for arc f to that error. 860 func (ctx *OpContext) notAllowedError(v, arc *Vertex) { 861 defer ctx.PopArc(ctx.PushArc(arc)) 862 863 defer ctx.ReleasePositions(ctx.MarkPositions()) 864 865 for _, c := range arc.Conjuncts { 866 ctx.addPositions(c) 867 } 868 // XXX(0.7): Find another way to get this provenance information. Not 869 // currently stored in new evaluator. 870 // for _, s := range x.Structs { 871 // s.AddPositions(ctx) 872 // } 873 874 if arc.ArcType == ArcPending { 875 arc.ArcType = ArcNotPresent 876 return 877 } 878 // TODO: setting arc instead of n.node eliminates subfields. This may be 879 // desirable or not, but it differs, at least from <=v0.6 behavior. 880 arc.SetValue(ctx, ctx.NewErrf("field not allowed")) 881 882 // TODO: remove? We are now setting it on both fields, which seems to be 883 // necessary for now. But we should remove this as it often results in 884 // a duplicate error. 885 // v.SetValue(ctx, ctx.NewErrf("field not allowed")) 886 887 // TODO: create a special kind of error that gets the positions 888 // of the relevant locations upon request from the arc. 889 } 890 891 // mergeConjunctions combines two values into one. It never modifies an 892 // existing conjunction. 893 func mergeConjunctions(a, b Value) Value { 894 if a == nil { 895 return b 896 } 897 if b == nil { 898 return a 899 } 900 ca, _ := a.(*Conjunction) 901 cb, _ := b.(*Conjunction) 902 n := 2 903 if ca != nil { 904 n += len(ca.Values) - 1 905 } 906 if cb != nil { 907 n += len(cb.Values) - 1 908 } 909 vs := make([]Value, 0, n) 910 if ca != nil { 911 vs = append(vs, ca.Values...) 912 } else { 913 vs = append(vs, a) 914 } 915 if cb != nil { 916 vs = append(vs, cb.Values...) 917 } else { 918 vs = append(vs, b) 919 } 920 // TODO: potentially order conjuncts to make matching more likely. 921 return &Conjunction{Values: vs} 922 } 923 924 // finalizePattern updates c.Expr to a CUE Value representing all fields allowed 925 // by the pattern constraints of c. If this context or any of its direct 926 // children is closed, the result will be a conjunction of all these closed 927 // values. Otherwise it will be a disjunction of all its children. A nil value 928 // represents all values. 929 func (c *closeContext) finalizePattern() { 930 switch { 931 case c.Expr != nil: // Patterns and expression are already set. 932 if !c.isClosed { 933 panic("c.Expr set unexpectedly") 934 } 935 return 936 case c.isTotal: // All values are allowed always. 937 return 938 } 939 940 // As this context is not closed, the pattern is somewhat meaningless. 941 // It may still be useful for analysis. 942 or := c.Patterns 943 944 for cc := c.child; cc != nil; cc = cc.next { 945 if cc.isTotal { 946 return 947 } 948 // Could be closed, in which case it must also be an embedding. 949 950 // TODO: simplify the values. 951 switch x := cc.Expr.(type) { 952 case nil: 953 case *Disjunction: 954 or = append(or, x.Values...) 955 default: 956 or = append(or, x) 957 } 958 } 959 960 switch len(or) { 961 case 0: 962 case 1: 963 c.Expr = or[0] 964 default: 965 // TODO: potentially order conjuncts to make matching more likely. 966 c.Expr = &Disjunction{Values: or} 967 } 968 } 969