1// Copyright 2021 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 eval contains the high level CUE evaluation strategy. 16// 17// CUE allows for a significant amount of freedom in order of evaluation due to 18// the commutativity of the unification operation. This package implements one 19// of the possible strategies. 20package adt 21 22// TODO: 23// - result should be nodeContext: this allows optionals info to be extracted 24// and computed. 25// 26 27import ( 28 "fmt" 29 "html/template" 30 "strings" 31 32 "cuelang.org/go/cue/ast" 33 "cuelang.org/go/cue/errors" 34 "cuelang.org/go/cue/token" 35) 36 37// TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO 38// 39// - Reuse work from previous cycles. For instance, if we can guarantee that a 40// value is always correct for partial results, we can just process the arcs 41// going from Partial to Finalized, without having to reevaluate the value. 42// 43// - Test closedness far more thoroughly. 44// 45 46type Stats struct { 47 DisjunctCount int 48 UnifyCount int 49 50 Freed int 51 Retained int 52 Reused int 53 Allocs int 54} 55 56// Leaks reports the number of nodeContext structs leaked. These are typically 57// benign, as they will just be garbage collected, as long as the pointer from 58// the original nodes has been eliminated or the original nodes are also not 59// referred to. But Leaks may have notable impact on performance, and thus 60// should be avoided. 61func (s *Stats) Leaks() int { 62 return s.Allocs + s.Reused - s.Freed 63} 64 65var stats = template.Must(template.New("stats").Parse(`{{"" -}} 66 67Leaks: {{.Leaks}} 68Freed: {{.Freed}} 69Reused: {{.Reused}} 70Allocs: {{.Allocs}} 71Retain: {{.Retained}} 72 73Unifications: {{.UnifyCount}} 74Disjuncts: {{.DisjunctCount}}`)) 75 76func (s *Stats) String() string { 77 buf := &strings.Builder{} 78 _ = stats.Execute(buf, s) 79 return buf.String() 80} 81 82func (c *OpContext) Stats() *Stats { 83 return &c.stats 84} 85 86// TODO: Note: NewContext takes essentially a cue.Value. By making this 87// type more central, we can perhaps avoid context creation. 88 89// func NewContext(r Runtime, v *Vertex) *OpContext { 90// e := NewUnifier(r) 91// return e.NewContext(v) 92// } 93 94var structSentinel = &StructMarker{} 95 96var incompleteSentinel = &Bottom{ 97 Code: IncompleteError, 98 Err: errors.Newf(token.NoPos, "incomplete"), 99} 100 101// evaluate returns the evaluated value associated with v. It may return a 102// partial result. That is, if v was not yet unified, it may return a 103// concrete value that must be the result assuming the configuration has no 104// errors. 105// 106// This semantics allows CUE to break reference cycles in a straightforward 107// manner. 108// 109// Vertex v must still be evaluated at some point to catch the underlying 110// error. 111// 112// TODO: return *Vertex 113func (c *OpContext) evaluate(v *Vertex, state VertexStatus) Value { 114 if v.isUndefined() { 115 // Use node itself to allow for cycle detection. 116 c.Unify(v, state) 117 } 118 119 if n := v.state; n != nil { 120 if n.errs != nil && !n.errs.IsIncomplete() { 121 return n.errs 122 } 123 if n.scalar != nil && isCyclePlaceholder(v.BaseValue) { 124 return n.scalar 125 } 126 } 127 128 switch x := v.BaseValue.(type) { 129 case *Bottom: 130 if x.IsIncomplete() { 131 c.AddBottom(x) 132 return nil 133 } 134 return x 135 136 case nil: 137 if v.state != nil { 138 switch x := v.state.getValidators().(type) { 139 case Value: 140 return x 141 default: 142 w := *v 143 w.BaseValue = x 144 return &w 145 } 146 } 147 Assertf(false, "no BaseValue: state: %v; requested: %v", v.status, state) 148 } 149 150 if v.status < Finalized && v.state != nil { 151 // TODO: errors are slightly better if we always add addNotify, but 152 // in this case it is less likely to cause a performance penalty. 153 // See https://github.com/cuelang/cue/issues/661. It may be possible to 154 // relax this again once we have proper tests to prevent regressions of 155 // that issue. 156 if !v.state.done() || v.state.errs != nil { 157 v.state.addNotify(c.vertex) 158 } 159 } 160 161 return v 162} 163 164// Unify fully unifies all values of a Vertex to completion and stores 165// the result in the Vertex. If unify was called on v before it returns 166// the cached results. 167func (c *OpContext) Unify(v *Vertex, state VertexStatus) { 168 // defer c.PopVertex(c.PushVertex(v)) 169 170 // Ensure a node will always have a nodeContext after calling Unify if it is 171 // not yet Finalized. 172 n := v.getNodeContext(c) 173 defer v.freeNode(n) 174 175 if state <= v.Status() { 176 if v.Status() != Partial && state != Partial { 177 return 178 } 179 } 180 181 switch v.Status() { 182 case Evaluating: 183 n.insertConjuncts() 184 return 185 186 case EvaluatingArcs: 187 Assertf(v.status > 0, "unexpected status %d", v.status) 188 return 189 190 case 0: 191 if v.Label.IsDef() { 192 v.Closed = true 193 } 194 195 if v.Parent != nil { 196 if v.Parent.Closed { 197 v.Closed = true 198 } 199 } 200 201 if !n.checkClosed(state) { 202 return 203 } 204 205 defer c.PopArc(c.PushArc(v)) 206 207 c.stats.UnifyCount++ 208 209 // Clear any remaining error. 210 if err := c.Err(); err != nil { 211 panic("uncaught error") 212 } 213 214 // Set the cache to a cycle error to ensure a cyclic reference will result 215 // in an error if applicable. A cyclic error may be ignored for 216 // non-expression references. The cycle error may also be removed as soon 217 // as there is evidence what a correct value must be, but before all 218 // validation has taken place. 219 // 220 // TODO(cycle): having a more recursive algorithm would make this 221 // special cycle handling unnecessary. 222 v.BaseValue = cycle 223 224 v.UpdateStatus(Evaluating) 225 226 n.conjuncts = v.Conjuncts 227 n.insertConjuncts() 228 229 fallthrough 230 231 case Partial: 232 defer c.PopArc(c.PushArc(v)) 233 234 v.status = Evaluating 235 236 // Use maybeSetCache for cycle breaking 237 for n.maybeSetCache(); n.expandOne(); n.maybeSetCache() { 238 } 239 240 n.doNotify() 241 242 if !n.done() { 243 switch { 244 case len(n.disjunctions) > 0 && isCyclePlaceholder(v.BaseValue): 245 // We disallow entering computations of disjunctions with 246 // incomplete data. 247 if state == Finalized { 248 b := c.NewErrf("incomplete cause disjunction") 249 b.Code = IncompleteError 250 n.errs = CombineErrors(nil, n.errs, b) 251 v.SetValue(n.ctx, Finalized, b) 252 } else { 253 n.node.UpdateStatus(Partial) 254 } 255 return 256 257 case state <= AllArcs: 258 n.node.UpdateStatus(Partial) 259 return 260 } 261 } 262 263 if s := v.Status(); state <= s { 264 // We have found a partial result. There may still be errors 265 // down the line which may result from further evaluating this 266 // field, but that will be caught when evaluating this field 267 // for real. 268 269 // This also covers the case where a recursive evaluation triggered 270 // this field to become finalized in the mean time. In that case 271 // we can avoid running another expandDisjuncts. 272 return 273 } 274 275 // Disjunctions should always be finalized. If there are nested 276 // disjunctions the last one should be finalized. 277 disState := state 278 if len(n.disjunctions) > 0 && disState != Finalized { 279 disState = Finalized 280 } 281 n.expandDisjuncts(disState, n, maybeDefault, false, true) 282 283 n.finalizeDisjuncts() 284 285 switch len(n.disjuncts) { 286 case 0: 287 case 1: 288 x := n.disjuncts[0].result 289 x.state = nil 290 *v = x 291 292 default: 293 d := n.createDisjunct() 294 v.BaseValue = d 295 // The conjuncts will have too much information. Better have no 296 // information than incorrect information. 297 for _, d := range d.Values { 298 // We clear the conjuncts for now. As these disjuncts are for API 299 // use only, we will fill them out when necessary (using Defaults). 300 d.Conjuncts = nil 301 302 // TODO: use a more principled form of dereferencing. For instance, 303 // disjuncts could already be assumed to be the given Vertex, and 304 // the the main vertex could be dereferenced during evaluation. 305 for _, a := range d.Arcs { 306 for _, x := range a.Conjuncts { 307 // All the environments for embedded structs need to be 308 // dereferenced. 309 for env := x.Env; env != nil && env.Vertex == v; env = env.Up { 310 env.Vertex = d 311 } 312 } 313 } 314 } 315 v.Arcs = nil 316 // v.Structs = nil // TODO: should we keep or discard the Structs? 317 // TODO: how to represent closedness information? Do we need it? 318 } 319 320 // If the state has changed, it is because a disjunct has been run, or 321 // because a single disjunct has replaced it. Restore the old state as 322 // to not confuse memory management. 323 v.state = n 324 325 // We don't do this in postDisjuncts, as it should only be done after 326 // completing all disjunctions. 327 if !n.done() { 328 if err := n.incompleteErrors(); err != nil { 329 b, _ := n.node.BaseValue.(*Bottom) 330 if b != err { 331 err = CombineErrors(n.ctx.src, b, err) 332 } 333 n.node.BaseValue = err 334 } 335 } 336 337 if state != Finalized { 338 return 339 } 340 341 if v.BaseValue == nil { 342 v.BaseValue = n.getValidators() 343 } 344 345 // Free memory here? 346 v.UpdateStatus(Finalized) 347 348 case AllArcs: 349 if !n.checkClosed(state) { 350 break 351 } 352 353 defer c.PopArc(c.PushArc(v)) 354 355 n.completeArcs(state) 356 357 case Finalized: 358 } 359} 360 361// insertConjuncts inserts conjuncts previously uninserted. 362func (n *nodeContext) insertConjuncts() { 363 for len(n.conjuncts) > 0 { 364 nInfos := len(n.node.Structs) 365 p := &n.conjuncts[0] 366 n.conjuncts = n.conjuncts[1:] 367 n.addExprConjunct(*p) 368 369 // Record the OptionalTypes for all structs that were inferred by this 370 // Conjunct. This information can be used by algorithms such as trim. 371 for i := nInfos; i < len(n.node.Structs); i++ { 372 p.CloseInfo.FieldTypes |= n.node.Structs[i].types 373 } 374 } 375} 376 377// finalizeDisjuncts: incomplete errors are kept around and not removed early. 378// This call filters the incomplete errors and removes them 379// 380// This also collects all errors of empty disjunctions. These cannot be 381// collected during the finalization state of individual disjuncts. Care should 382// be taken to only call this after all disjuncts have been finalized. 383func (n *nodeContext) finalizeDisjuncts() { 384 a := n.disjuncts 385 if len(a) == 0 { 386 return 387 } 388 k := 0 389 for i, d := range a { 390 switch d.finalDone() { 391 case true: 392 a[k], a[i] = d, a[k] 393 k++ 394 default: 395 if err := d.incompleteErrors(); err != nil { 396 n.disjunctErrs = append(n.disjunctErrs, err) 397 } 398 } 399 d.free() 400 } 401 if k == 0 { 402 n.makeError() 403 } 404 n.disjuncts = a[:k] 405} 406 407func (n *nodeContext) doNotify() { 408 if n.errs == nil || len(n.notify) == 0 { 409 return 410 } 411 for _, v := range n.notify { 412 if v.state == nil { 413 if b, ok := v.BaseValue.(*Bottom); ok { 414 v.BaseValue = CombineErrors(nil, b, n.errs) 415 } else { 416 v.BaseValue = n.errs 417 } 418 } else { 419 v.state.addBottom(n.errs) 420 } 421 } 422 n.notify = n.notify[:0] 423} 424 425func (n *nodeContext) postDisjunct(state VertexStatus) { 426 ctx := n.ctx 427 428 for { 429 // Use maybeSetCache for cycle breaking 430 for n.maybeSetCache(); n.expandOne(); n.maybeSetCache() { 431 } 432 433 if aList, id := n.addLists(); aList != nil { 434 n.updateNodeType(ListKind, aList, id) 435 } else { 436 break 437 } 438 } 439 440 if n.aStruct != nil { 441 n.updateNodeType(StructKind, n.aStruct, n.aStructID) 442 } 443 444 switch err := n.getErr(); { 445 case err != nil: 446 n.node.BaseValue = err 447 n.errs = nil 448 449 default: 450 if isCyclePlaceholder(n.node.BaseValue) { 451 if !n.done() { 452 n.node.BaseValue = n.incompleteErrors() 453 } else { 454 n.node.BaseValue = nil 455 } 456 } 457 // TODO: this ideally should be done here. However, doing so causes 458 // a somewhat more aggressive cutoff in disjunction cycles, which cause 459 // some incompatibilities. Fix in another CL. 460 // 461 // else if !n.done() { 462 // n.expandOne() 463 // if err := n.incompleteErrors(); err != nil { 464 // n.node.BaseValue = err 465 // } 466 // } 467 468 // We are no longer evaluating. 469 // n.node.UpdateStatus(Partial) 470 n.node.UpdateStatus(Evaluating) 471 472 // Either set to Conjunction or error. 473 // TODO: verify and simplify the below code to determine whether 474 // something is a struct. 475 markStruct := false 476 if n.aStruct != nil { 477 markStruct = true 478 } else if len(n.node.Structs) > 0 { 479 markStruct = n.kind&StructKind != 0 && !n.hasTop 480 } 481 v := n.node.Value() 482 if n.node.BaseValue == nil && markStruct { 483 n.node.BaseValue = &StructMarker{} 484 v = n.node 485 } 486 if v != nil && IsConcrete(v) { 487 // Also check when we already have errors as we may find more 488 // serious errors and would like to know about all errors anyway. 489 490 if n.lowerBound != nil { 491 if b := ctx.Validate(n.lowerBound, v); b != nil { 492 // TODO(errors): make Validate return boolean and generate 493 // optimized conflict message. Also track and inject IDs 494 // to determine origin location.s 495 if e, _ := b.Err.(*ValueError); e != nil { 496 e.AddPosition(n.lowerBound) 497 e.AddPosition(v) 498 } 499 n.addBottom(b) 500 } 501 } 502 if n.upperBound != nil { 503 if b := ctx.Validate(n.upperBound, v); b != nil { 504 // TODO(errors): make Validate return boolean and generate 505 // optimized conflict message. Also track and inject IDs 506 // to determine origin location.s 507 if e, _ := b.Err.(*ValueError); e != nil { 508 e.AddPosition(n.upperBound) 509 e.AddPosition(v) 510 } 511 n.addBottom(b) 512 } 513 } 514 // MOVE BELOW 515 // TODO(perf): only delay processing of actual non-monotonic checks. 516 skip := n.skipNonMonotonicChecks() 517 if v := n.node.Value(); v != nil && IsConcrete(v) && !skip { 518 for _, v := range n.checks { 519 // TODO(errors): make Validate return bottom and generate 520 // optimized conflict message. Also track and inject IDs 521 // to determine origin location.s 522 if b := ctx.Validate(v, n.node); b != nil { 523 n.addBottom(b) 524 } 525 } 526 } 527 } else if state == Finalized { 528 n.node.BaseValue = n.getValidators() 529 } 530 531 if v == nil { 532 break 533 } 534 535 switch { 536 case v.Kind() == ListKind: 537 for _, a := range n.node.Arcs { 538 if a.Label.Typ() == StringLabel { 539 n.addErr(ctx.Newf("list may not have regular fields")) 540 // TODO(errors): add positions for list and arc definitions. 541 542 } 543 } 544 545 // case !isStruct(n.node) && v.Kind() != BottomKind: 546 // for _, a := range n.node.Arcs { 547 // if a.Label.IsRegular() { 548 // n.addErr(errors.Newf(token.NoPos, 549 // // TODO(errors): add positions of non-struct values and arcs. 550 // "cannot combine scalar values with arcs")) 551 // } 552 // } 553 } 554 } 555 556 if err := n.getErr(); err != nil { 557 if b, _ := n.node.BaseValue.(*Bottom); b != nil { 558 err = CombineErrors(nil, b, err) 559 } 560 n.node.BaseValue = err 561 // TODO: add return: if evaluation of arcs is important it can be done 562 // later. Logically we're done. 563 } 564 565 n.completeArcs(state) 566} 567 568func (n *nodeContext) incompleteErrors() *Bottom { 569 // collect incomplete errors. 570 var err *Bottom // n.incomplete 571 for _, d := range n.dynamicFields { 572 err = CombineErrors(nil, err, d.err) 573 } 574 for _, c := range n.forClauses { 575 err = CombineErrors(nil, err, c.err) 576 } 577 for _, c := range n.ifClauses { 578 err = CombineErrors(nil, err, c.err) 579 } 580 for _, x := range n.exprs { 581 err = CombineErrors(nil, err, x.err) 582 } 583 if err == nil { 584 // safeguard. 585 err = incompleteSentinel 586 } 587 return err 588} 589 590// TODO(perf): ideally we should always perform a closedness check if 591// state is Finalized. This is currently not possible when computing a 592// partial disjunction as the closedness information is not yet 593// complete, possibly leading to a disjunct to be rejected prematurely. 594// It is probably possible to fix this if we could add StructInfo 595// structures demarked per conjunct. 596// 597// In practice this should not be a problem: when disjuncts originate 598// from the same disjunct, they will have the same StructInfos, and thus 599// Equal is able to equate them even in the precense of optional field. 600// In general, combining any limited set of disjuncts will soon reach 601// a fixed point where duplicate elements can be eliminated this way. 602// 603// Note that not checking closedness is irrelevant for disjunctions of 604// scalars. This means it also doesn't hurt performance where structs 605// have a discriminator field (e.g. Kubernetes). We should take care, 606// though, that any potential performance issues are eliminated for 607// Protobuf-like oneOf fields. 608func (n *nodeContext) checkClosed(state VertexStatus) bool { 609 ignore := state != Finalized || n.skipNonMonotonicChecks() 610 611 v := n.node 612 if !v.Label.IsInt() && v.Parent != nil && !ignore { 613 ctx := n.ctx 614 // Visit arcs recursively to validate and compute error. 615 if _, err := verifyArc2(ctx, v.Label, v, v.Closed); err != nil { 616 // Record error in child node to allow recording multiple 617 // conflicts at the appropriate place, to allow valid fields to 618 // be represented normally and, most importantly, to avoid 619 // recursive processing of a disallowed field. 620 v.SetValue(ctx, Finalized, err) 621 return false 622 } 623 } 624 return true 625} 626 627func (n *nodeContext) completeArcs(state VertexStatus) { 628 629 if state <= AllArcs { 630 n.node.UpdateStatus(AllArcs) 631 return 632 } 633 634 n.node.UpdateStatus(EvaluatingArcs) 635 636 ctx := n.ctx 637 638 if cyclic := n.hasCycle && !n.hasNonCycle; cyclic { 639 n.node.BaseValue = CombineErrors(nil, 640 n.node.Value(), 641 &Bottom{ 642 Code: StructuralCycleError, 643 Err: ctx.Newf("structural cycle"), 644 Value: n.node.Value(), 645 // TODO: probably, this should have the referenced arc. 646 }) 647 // Don't process Arcs. This is mostly to ensure that no Arcs with 648 // an Unprocessed status remain in the output. 649 n.node.Arcs = nil 650 } else { 651 // Visit arcs recursively to validate and compute error. 652 for _, a := range n.node.Arcs { 653 if a.nonMonotonicInsertGen >= a.nonMonotonicLookupGen && a.nonMonotonicLookupGen > 0 { 654 err := ctx.Newf( 655 "cycle: field inserted by if clause that was previously evaluated by another if clause: %s", a.Label) 656 err.AddPosition(n.node) 657 n.node.BaseValue = &Bottom{Err: err} 658 } else if a.nonMonotonicReject { 659 err := ctx.Newf( 660 "cycle: field was added after an if clause evaluated it: %s", 661 a.Label) 662 err.AddPosition(n.node) 663 n.node.BaseValue = &Bottom{Err: err} 664 } 665 666 // Call UpdateStatus here to be absolutely sure the status is set 667 // correctly and that we are not regressing. 668 n.node.UpdateStatus(EvaluatingArcs) 669 ctx.Unify(a, state) 670 // Don't set the state to Finalized if the child arcs are not done. 671 if state == Finalized && a.status < Finalized { 672 state = AllArcs 673 } 674 if err, _ := a.BaseValue.(*Bottom); err != nil { 675 n.node.AddChildError(err) 676 } 677 } 678 } 679 680 n.node.UpdateStatus(state) 681} 682 683// TODO: this is now a sentinel. Use a user-facing error that traces where 684// the cycle originates. 685var cycle = &Bottom{ 686 Err: errors.Newf(token.NoPos, "cycle error"), 687 Code: CycleError, 688} 689 690func isCyclePlaceholder(v BaseValue) bool { 691 return v == cycle 692} 693 694func (n *nodeContext) createDisjunct() *Disjunction { 695 a := make([]*Vertex, len(n.disjuncts)) 696 p := 0 697 hasDefaults := false 698 for i, x := range n.disjuncts { 699 v := new(Vertex) 700 *v = x.result 701 v.state = nil 702 switch x.defaultMode { 703 case isDefault: 704 a[i] = a[p] 705 a[p] = v 706 p++ 707 hasDefaults = true 708 709 case notDefault: 710 hasDefaults = true 711 fallthrough 712 case maybeDefault: 713 a[i] = v 714 } 715 } 716 // TODO: disambiguate based on concrete values. 717 // TODO: consider not storing defaults. 718 // if p > 0 { 719 // a = a[:p] 720 // } 721 return &Disjunction{ 722 Values: a, 723 NumDefaults: p, 724 HasDefaults: hasDefaults, 725 } 726} 727 728type arcKey struct { 729 arc *Vertex 730 id CloseInfo 731} 732 733// A nodeContext is used to collate all conjuncts of a value to facilitate 734// unification. Conceptually order of unification does not matter. However, 735// order has relevance when performing checks of non-monotic properities. Such 736// checks should only be performed once the full value is known. 737type nodeContext struct { 738 nextFree *nodeContext 739 refCount int 740 741 ctx *OpContext 742 node *Vertex 743 744 // usedArcs is a list of arcs that were looked up during non-monotonic operations, but do not exist yet. 745 usedArcs []*Vertex 746 747 // TODO: (this is CL is first step) 748 // filter *Vertex a subset of composite with concrete fields for 749 // bloom-like filtering of disjuncts. We should first verify, however, 750 // whether some breath-first search gives sufficient performance, as this 751 // should already ensure a quick-fail for struct disjunctions with 752 // discriminators. 753 754 arcMap []arcKey 755 756 // snapshot holds the last value of the vertex before calling postDisjunct. 757 snapshot Vertex 758 759 // Result holds the last evaluated value of the vertex after calling 760 // postDisjunct. 761 result Vertex 762 763 // Current value (may be under construction) 764 scalar Value // TODO: use Value in node. 765 scalarID CloseInfo 766 767 // Concrete conjuncts 768 kind Kind 769 kindExpr Expr // expr that adjust last value (for error reporting) 770 kindID CloseInfo // for error tracing 771 lowerBound *BoundValue // > or >= 772 upperBound *BoundValue // < or <= 773 checks []Validator // BuiltinValidator, other bound values. 774 errs *Bottom 775 776 // Conjuncts holds a reference to the Vertex Arcs that still need 777 // processing. It does NOT need to be copied. 778 conjuncts []Conjunct 779 780 // notify is used to communicate errors in cyclic dependencies. 781 // TODO: also use this to communicate increasingly more concrete values. 782 notify []*Vertex 783 784 // Struct information 785 dynamicFields []envDynamic 786 ifClauses []envYield 787 forClauses []envYield 788 aStruct Expr 789 aStructID CloseInfo 790 791 // Expression conjuncts 792 lists []envList 793 vLists []*Vertex 794 exprs []envExpr 795 796 hasTop bool 797 hasCycle bool // has conjunct with structural cycle 798 hasNonCycle bool // has conjunct without structural cycle 799 800 // Disjunction handling 801 disjunctions []envDisjunct 802 803 // usedDefault indicates the for each of possibly multiple parent 804 // disjunctions whether it is unified with a default disjunct or not. 805 // This is then later used to determine whether a disjunction should 806 // be treated as a marked disjunction. 807 usedDefault []defaultInfo 808 809 defaultMode defaultMode 810 disjuncts []*nodeContext 811 buffer []*nodeContext 812 disjunctErrs []*Bottom 813} 814 815type defaultInfo struct { 816 // parentMode indicates whether this values was used as a default value, 817 // based on the parent mode. 818 parentMode defaultMode 819 820 // The result of default evaluation for a nested disjunction. 821 nestedMode defaultMode 822 823 origMode defaultMode 824} 825 826func (n *nodeContext) addNotify(v *Vertex) { 827 if v != nil { 828 n.notify = append(n.notify, v) 829 } 830} 831 832func (n *nodeContext) clone() *nodeContext { 833 d := n.ctx.newNodeContext(n.node) 834 835 d.refCount++ 836 837 d.ctx = n.ctx 838 d.node = n.node 839 840 d.scalar = n.scalar 841 d.scalarID = n.scalarID 842 d.kind = n.kind 843 d.kindExpr = n.kindExpr 844 d.kindID = n.kindID 845 d.aStruct = n.aStruct 846 d.aStructID = n.aStructID 847 d.hasTop = n.hasTop 848 849 d.lowerBound = n.lowerBound 850 d.upperBound = n.upperBound 851 d.errs = n.errs 852 d.hasTop = n.hasTop 853 d.hasCycle = n.hasCycle 854 d.hasNonCycle = n.hasNonCycle 855 856 // d.arcMap = append(d.arcMap, n.arcMap...) // XXX add? 857 // d.usedArcs = append(d.usedArcs, n.usedArcs...) // XXX: add? 858 d.notify = append(d.notify, n.notify...) 859 d.checks = append(d.checks, n.checks...) 860 d.dynamicFields = append(d.dynamicFields, n.dynamicFields...) 861 d.ifClauses = append(d.ifClauses, n.ifClauses...) 862 d.forClauses = append(d.forClauses, n.forClauses...) 863 d.lists = append(d.lists, n.lists...) 864 d.vLists = append(d.vLists, n.vLists...) 865 d.exprs = append(d.exprs, n.exprs...) 866 d.usedDefault = append(d.usedDefault, n.usedDefault...) 867 868 // No need to clone d.disjunctions 869 870 return d 871} 872 873func (c *OpContext) newNodeContext(node *Vertex) *nodeContext { 874 if n := c.freeListNode; n != nil { 875 c.stats.Reused++ 876 c.freeListNode = n.nextFree 877 878 *n = nodeContext{ 879 ctx: c, 880 node: node, 881 kind: TopKind, 882 usedArcs: n.usedArcs[:0], 883 arcMap: n.arcMap[:0], 884 notify: n.notify[:0], 885 checks: n.checks[:0], 886 dynamicFields: n.dynamicFields[:0], 887 ifClauses: n.ifClauses[:0], 888 forClauses: n.forClauses[:0], 889 lists: n.lists[:0], 890 vLists: n.vLists[:0], 891 exprs: n.exprs[:0], 892 disjunctions: n.disjunctions[:0], 893 usedDefault: n.usedDefault[:0], 894 disjunctErrs: n.disjunctErrs[:0], 895 disjuncts: n.disjuncts[:0], 896 buffer: n.buffer[:0], 897 } 898 899 return n 900 } 901 c.stats.Allocs++ 902 903 return &nodeContext{ 904 ctx: c, 905 node: node, 906 kind: TopKind, 907 } 908} 909 910func (v *Vertex) getNodeContext(c *OpContext) *nodeContext { 911 if v.state == nil { 912 if v.status == Finalized { 913 return nil 914 } 915 v.state = c.newNodeContext(v) 916 } else if v.state.node != v { 917 panic("getNodeContext: nodeContext out of sync") 918 } 919 v.state.refCount++ 920 return v.state 921} 922 923func (v *Vertex) freeNode(n *nodeContext) { 924 if n == nil { 925 return 926 } 927 if n.node != v { 928 panic("freeNode: unpaired free") 929 } 930 if v.state != nil && v.state != n { 931 panic("freeNode: nodeContext out of sync") 932 } 933 if n.refCount--; n.refCount == 0 { 934 if v.status == Finalized { 935 v.freeNodeState() 936 } else { 937 n.ctx.stats.Retained++ 938 } 939 } 940} 941 942func (v *Vertex) freeNodeState() { 943 if v.state == nil { 944 return 945 } 946 state := v.state 947 v.state = nil 948 949 state.ctx.freeNodeContext(state) 950} 951 952func (n *nodeContext) free() { 953 if n.refCount--; n.refCount == 0 { 954 n.ctx.freeNodeContext(n) 955 } 956} 957 958func (c *OpContext) freeNodeContext(n *nodeContext) { 959 c.stats.Freed++ 960 n.nextFree = c.freeListNode 961 c.freeListNode = n 962 n.node = nil 963 n.refCount = 0 964} 965 966// TODO(perf): return a dedicated ConflictError that can track original 967// positions on demand. 968func (n *nodeContext) addConflict( 969 v1, v2 Node, 970 k1, k2 Kind, 971 id1, id2 CloseInfo) { 972 973 ctx := n.ctx 974 975 var err *ValueError 976 if k1 == k2 { 977 err = ctx.NewPosf(token.NoPos, "conflicting values %s and %s", v1, v2) 978 } else { 979 err = ctx.NewPosf(token.NoPos, 980 "conflicting values %s and %s (mismatched types %s and %s)", 981 v1, v2, k1, k2) 982 } 983 984 err.AddPosition(v1) 985 err.AddPosition(v2) 986 err.AddClosedPositions(id1) 987 err.AddClosedPositions(id2) 988 989 n.addErr(err) 990} 991 992func (n *nodeContext) updateNodeType(k Kind, v Expr, id CloseInfo) bool { 993 ctx := n.ctx 994 kind := n.kind & k 995 996 switch { 997 case n.kind == BottomKind, 998 k == BottomKind: 999 return false 1000 1001 case kind == BottomKind: 1002 if n.kindExpr != nil { 1003 n.addConflict(n.kindExpr, v, n.kind, k, n.kindID, id) 1004 } else { 1005 n.addErr(ctx.Newf( 1006 "conflicting value %s (mismatched types %s and %s)", 1007 v, n.kind, k)) 1008 } 1009 } 1010 1011 if n.kind != kind || n.kindExpr == nil { 1012 n.kindExpr = v 1013 } 1014 n.kind = kind 1015 return kind != BottomKind 1016} 1017 1018func (n *nodeContext) done() bool { 1019 return len(n.dynamicFields) == 0 && 1020 len(n.ifClauses) == 0 && 1021 len(n.forClauses) == 0 && 1022 len(n.exprs) == 0 1023} 1024 1025// finalDone is like done, but allows for cycle errors, which can be ignored 1026// as they essentially indicate a = a & _. 1027func (n *nodeContext) finalDone() bool { 1028 for _, x := range n.exprs { 1029 if x.err.Code != CycleError { 1030 return false 1031 } 1032 } 1033 return len(n.dynamicFields) == 0 && 1034 len(n.ifClauses) == 0 && 1035 len(n.forClauses) == 0 1036} 1037 1038// hasErr is used to determine if an evaluation path, for instance a single 1039// path after expanding all disjunctions, has an error. 1040func (n *nodeContext) hasErr() bool { 1041 if n.node.ChildErrors != nil { 1042 return true 1043 } 1044 if n.node.Status() > Evaluating && n.node.IsErr() { 1045 return true 1046 } 1047 return n.ctx.HasErr() || n.errs != nil 1048} 1049 1050func (n *nodeContext) getErr() *Bottom { 1051 n.errs = CombineErrors(nil, n.errs, n.ctx.Err()) 1052 return n.errs 1053} 1054 1055// getValidators sets the vertex' Value in case there was no concrete value. 1056func (n *nodeContext) getValidators() BaseValue { 1057 ctx := n.ctx 1058 1059 a := []Value{} 1060 // if n.node.Value != nil { 1061 // a = append(a, n.node.Value) 1062 // } 1063 kind := TopKind 1064 if n.lowerBound != nil { 1065 a = append(a, n.lowerBound) 1066 kind &= n.lowerBound.Kind() 1067 } 1068 if n.upperBound != nil { 1069 a = append(a, n.upperBound) 1070 kind &= n.upperBound.Kind() 1071 } 1072 for _, c := range n.checks { 1073 // Drop !=x if x is out of bounds with another bound. 1074 if b, _ := c.(*BoundValue); b != nil && b.Op == NotEqualOp { 1075 if n.upperBound != nil && 1076 SimplifyBounds(ctx, n.kind, n.upperBound, b) != nil { 1077 continue 1078 } 1079 if n.lowerBound != nil && 1080 SimplifyBounds(ctx, n.kind, n.lowerBound, b) != nil { 1081 continue 1082 } 1083 } 1084 a = append(a, c) 1085 kind &= c.Kind() 1086 } 1087 if kind&^n.kind != 0 { 1088 a = append(a, &BasicType{K: n.kind}) 1089 } 1090 1091 var v BaseValue 1092 switch len(a) { 1093 case 0: 1094 // Src is the combined input. 1095 v = &BasicType{K: n.kind} 1096 1097 case 1: 1098 v = a[0].(Value) // remove cast 1099 1100 default: 1101 v = &Conjunction{Values: a} 1102 } 1103 1104 return v 1105} 1106 1107// TODO: this function can probably go as this is now handled in the nodeContext. 1108func (n *nodeContext) maybeSetCache() { 1109 if n.node.Status() > Partial { // n.node.BaseValue != nil 1110 return 1111 } 1112 if n.scalar != nil { 1113 n.node.BaseValue = n.scalar 1114 } 1115 // NOTE: this is now handled by associating the nodeContext 1116 // if n.errs != nil { 1117 // n.node.SetValue(n.ctx, Partial, n.errs) 1118 // } 1119} 1120 1121type envExpr struct { 1122 c Conjunct 1123 err *Bottom 1124} 1125 1126type envDynamic struct { 1127 env *Environment 1128 field *DynamicField 1129 id CloseInfo 1130 err *Bottom 1131} 1132 1133type envYield struct { 1134 env *Environment 1135 yield Yielder 1136 id CloseInfo 1137 err *Bottom 1138} 1139 1140type envList struct { 1141 env *Environment 1142 list *ListLit 1143 n int64 // recorded length after evaluator 1144 elipsis *Ellipsis 1145 id CloseInfo 1146} 1147 1148func (n *nodeContext) addBottom(b *Bottom) { 1149 n.errs = CombineErrors(nil, n.errs, b) 1150 // TODO(errors): consider doing this 1151 // n.kindExpr = n.errs 1152 // n.kind = 0 1153} 1154 1155func (n *nodeContext) addErr(err errors.Error) { 1156 if err != nil { 1157 n.addBottom(&Bottom{Err: err}) 1158 } 1159} 1160 1161// addExprConjuncts will attempt to evaluate an Expr and insert the value 1162// into the nodeContext if successful or queue it for later evaluation if it is 1163// incomplete or is not value. 1164func (n *nodeContext) addExprConjunct(v Conjunct) { 1165 env := v.Env 1166 id := v.CloseInfo 1167 1168 switch x := v.Expr().(type) { 1169 case *Vertex: 1170 if x.IsData() { 1171 n.addValueConjunct(env, x, id) 1172 } else { 1173 n.addVertexConjuncts(env, id, x, x, true) 1174 } 1175 1176 case Value: 1177 n.addValueConjunct(env, x, id) 1178 1179 case *BinaryExpr: 1180 if x.Op == AndOp { 1181 n.addExprConjunct(MakeConjunct(env, x.X, id)) 1182 n.addExprConjunct(MakeConjunct(env, x.Y, id)) 1183 } else { 1184 n.evalExpr(v) 1185 } 1186 1187 case *StructLit: 1188 n.addStruct(env, x, id) 1189 1190 case *ListLit: 1191 n.lists = append(n.lists, envList{env: env, list: x, id: id}) 1192 1193 case *DisjunctionExpr: 1194 n.addDisjunction(env, x, id) 1195 1196 default: 1197 // Must be Resolver or Evaluator. 1198 n.evalExpr(v) 1199 } 1200} 1201 1202// evalExpr is only called by addExprConjunct. If an error occurs, it records 1203// the error in n and returns nil. 1204func (n *nodeContext) evalExpr(v Conjunct) { 1205 // Require an Environment. 1206 ctx := n.ctx 1207 1208 closeID := v.CloseInfo 1209 1210 // TODO: see if we can do without these counters. 1211 for _, d := range v.Env.Deref { 1212 d.EvalCount++ 1213 } 1214 for _, d := range v.Env.Cycles { 1215 d.SelfCount++ 1216 } 1217 defer func() { 1218 for _, d := range v.Env.Deref { 1219 d.EvalCount-- 1220 } 1221 for _, d := range v.Env.Cycles { 1222 d.SelfCount++ 1223 } 1224 }() 1225 1226 switch x := v.Expr().(type) { 1227 case Resolver: 1228 arc, err := ctx.Resolve(v.Env, x) 1229 if err != nil && !err.IsIncomplete() { 1230 n.addBottom(err) 1231 break 1232 } 1233 if arc == nil { 1234 n.exprs = append(n.exprs, envExpr{v, err}) 1235 break 1236 } 1237 1238 n.addVertexConjuncts(v.Env, v.CloseInfo, v.Expr(), arc, false) 1239 1240 case Evaluator: 1241 // Interpolation, UnaryExpr, BinaryExpr, CallExpr 1242 // Could be unify? 1243 val := ctx.evaluateRec(v.Env, v.Expr(), Partial) 1244 if b, ok := val.(*Bottom); ok && b.IsIncomplete() { 1245 n.exprs = append(n.exprs, envExpr{v, b}) 1246 break 1247 } 1248 1249 if v, ok := val.(*Vertex); ok { 1250 // Handle generated disjunctions (as in the 'or' builtin). 1251 // These come as a Vertex, but should not be added as a value. 1252 b, ok := v.BaseValue.(*Bottom) 1253 if ok && b.IsIncomplete() && len(v.Conjuncts) > 0 { 1254 for _, c := range v.Conjuncts { 1255 c.CloseInfo = closeID 1256 n.addExprConjunct(c) 1257 } 1258 break 1259 } 1260 } 1261 1262 // TODO: also to through normal Vertex handling here. At the moment 1263 // addValueConjunct handles StructMarker.NeedsClose, as this is always 1264 // only needed when evaluation an Evaluator, and not a Resolver. 1265 // The two code paths should ideally be merged once this separate 1266 // mechanism is eliminated. 1267 // 1268 // if arc, ok := val.(*Vertex); ok && !arc.IsData() { 1269 // n.addVertexConjuncts(v.Env, closeID, v.Expr(), arc) 1270 // break 1271 // } 1272 1273 // TODO: insert in vertex as well 1274 n.addValueConjunct(v.Env, val, closeID) 1275 1276 default: 1277 panic(fmt.Sprintf("unknown expression of type %T", x)) 1278 } 1279} 1280 1281func (n *nodeContext) addVertexConjuncts(env *Environment, closeInfo CloseInfo, x Expr, arc *Vertex, inline bool) { 1282 1283 // We need to ensure that each arc is only unified once (or at least) a 1284 // bounded time, witch each conjunct. Comprehensions, for instance, may 1285 // distribute a value across many values that get unified back into the 1286 // same value. If such a value is a disjunction, than a disjunction of N 1287 // disjuncts will result in a factor N more unifications for each 1288 // occurrence of such value, resulting in exponential running time. This 1289 // is especially common values that are used as a type. 1290 // 1291 // However, unification is idempotent, so each such conjunct only needs 1292 // to be unified once. This cache checks for this and prevents an 1293 // exponential blowup in such case. 1294 // 1295 // TODO(perf): this cache ensures the conjuncts of an arc at most once 1296 // per ID. However, we really need to add the conjuncts of an arc only 1297 // once total, and then add the close information once per close ID 1298 // (pointer can probably be shared). Aside from being more performant, 1299 // this is probably the best way to guarantee that conjunctions are 1300 // linear in this case. 1301 key := arcKey{arc, closeInfo} 1302 for _, k := range n.arcMap { 1303 if key == k { 1304 return 1305 } 1306 } 1307 n.arcMap = append(n.arcMap, key) 1308 1309 // Pass detection of structural cycles from parent to children. 1310 cyclic := false 1311 if env != nil { 1312 // If a reference is in a tainted set, so is the value it refers to. 1313 cyclic = env.Cyclic 1314 } 1315 1316 status := arc.Status() 1317 1318 switch status { 1319 case Evaluating: 1320 // Reference cycle detected. We have reached a fixed point and 1321 // adding conjuncts at this point will not change the value. Also, 1322 // continuing to pursue this value will result in an infinite loop. 1323 1324 // TODO: add a mechanism so that the computation will only have to 1325 // be done once? 1326 1327 if arc == n.node { 1328 // TODO: we could use node sharing here. This may avoid an 1329 // exponential blowup during evaluation, like is possible with 1330 // YAML. 1331 return 1332 } 1333 1334 case EvaluatingArcs: 1335 // Structural cycle detected. Continue evaluation as usual, but 1336 // keep track of whether any other conjuncts without structural 1337 // cycles are added. If not, evaluation of child arcs will end 1338 // with this node. 1339 1340 // For the purpose of determining whether at least one non-cyclic 1341 // conjuncts exists, we consider all conjuncts of a cyclic conjuncts 1342 // also cyclic. 1343 1344 cyclic = true 1345 n.hasCycle = true 1346 1347 // As the EvaluatingArcs mechanism bypasses the self-reference 1348 // mechanism, we need to separately keep track of it here. 1349 // If this (originally) is a self-reference node, adding them 1350 // will result in recursively adding the same reference. For this 1351 // we also mark the node as evaluating. 1352 if arc.SelfCount > 0 { 1353 return 1354 } 1355 1356 // This count is added for values that are directly added below. 1357 // The count is handled separately for delayed values. 1358 arc.SelfCount++ 1359 defer func() { arc.SelfCount-- }() 1360 } 1361 1362 // Performance: the following if check filters cases that are not strictly 1363 // necessary for correct functioning. Not updating the closeInfo may cause 1364 // some position information to be lost for top-level positions of merges 1365 // resulting form APIs. These tend to be fairly uninteresting. 1366 // At the same time, this optimization may prevent considerable slowdown 1367 // in case an API does many calls to Unify. 1368 if !inline || arc.IsClosedStruct() || arc.IsClosedList() { 1369 closeInfo = closeInfo.SpawnRef(arc, IsDef(x), x) 1370 } 1371 1372 if arc.status == 0 && !inline { 1373 // This is a rare condition, but can happen in certain 1374 // evaluation orders. Unfortunately, adding this breaks 1375 // resolution of cyclic mutually referring disjunctions. But it 1376 // is necessary to prevent lookups in unevaluated structs. 1377 // TODO(cycles): this can probably most easily be fixed with a 1378 // having a more recursive implementation. 1379 n.ctx.Unify(arc, AllArcs) 1380 } 1381 1382 for _, c := range arc.Conjuncts { 1383 var a []*Vertex 1384 if env != nil { 1385 a = env.Deref 1386 } 1387 if inline { 1388 c = updateCyclic(c, cyclic, nil, nil) 1389 } else { 1390 c = updateCyclic(c, cyclic, arc, a) 1391 } 1392 1393 // Note that we are resetting the tree here. We hereby assume that 1394 // closedness conflicts resulting from unifying the referenced arc were 1395 // already caught there and that we can ignore further errors here. 1396 c.CloseInfo = closeInfo 1397 n.addExprConjunct(c) 1398 } 1399} 1400 1401// isDef reports whether an expressions is a reference that references a 1402// definition anywhere in its selection path. 1403// 1404// TODO(performance): this should be merged with resolve(). But for now keeping 1405// this code isolated makes it easier to see what it is for. 1406func isDef(x Expr) bool { 1407 switch r := x.(type) { 1408 case *FieldReference: 1409 return r.Label.IsDef() 1410 1411 case *SelectorExpr: 1412 if r.Sel.IsDef() { 1413 return true 1414 } 1415 return isDef(r.X) 1416 1417 case *IndexExpr: 1418 return isDef(r.X) 1419 } 1420 return false 1421} 1422 1423// updateCyclicStatus looks for proof of non-cyclic conjuncts to override 1424// a structural cycle. 1425func (n *nodeContext) updateCyclicStatus(env *Environment) { 1426 if env == nil || !env.Cyclic { 1427 n.hasNonCycle = true 1428 } 1429} 1430 1431func updateCyclic(c Conjunct, cyclic bool, deref *Vertex, a []*Vertex) Conjunct { 1432 env := c.Env 1433 switch { 1434 case env == nil: 1435 if !cyclic && deref == nil { 1436 return c 1437 } 1438 env = &Environment{Cyclic: cyclic} 1439 case deref == nil && env.Cyclic == cyclic && len(a) == 0: 1440 return c 1441 default: 1442 // The conjunct may still be in use in other fields, so we should 1443 // make a new copy to mark Cyclic only for this case. 1444 e := *env 1445 e.Cyclic = e.Cyclic || cyclic 1446 env = &e 1447 } 1448 if deref != nil || len(a) > 0 { 1449 cp := make([]*Vertex, 0, len(a)+1) 1450 cp = append(cp, a...) 1451 if deref != nil { 1452 cp = append(cp, deref) 1453 } 1454 env.Deref = cp 1455 } 1456 if deref != nil { 1457 env.Cycles = append(env.Cycles, deref) 1458 } 1459 return MakeConjunct(env, c.Expr(), c.CloseInfo) 1460} 1461 1462func (n *nodeContext) addValueConjunct(env *Environment, v Value, id CloseInfo) { 1463 n.updateCyclicStatus(env) 1464 1465 ctx := n.ctx 1466 1467 if x, ok := v.(*Vertex); ok { 1468 if m, ok := x.BaseValue.(*StructMarker); ok { 1469 n.aStruct = x 1470 n.aStructID = id 1471 if m.NeedClose { 1472 id = id.SpawnRef(x, IsDef(x), x) 1473 id.IsClosed = true 1474 } 1475 } 1476 1477 cyclic := env != nil && env.Cyclic 1478 1479 if !x.IsData() { 1480 // TODO: this really shouldn't happen anymore. 1481 if isComplexStruct(ctx, x) { 1482 // This really shouldn't happen, but just in case. 1483 n.addVertexConjuncts(env, id, x, x, true) 1484 return 1485 } 1486 1487 for _, c := range x.Conjuncts { 1488 c = updateCyclic(c, cyclic, nil, nil) 1489 c.CloseInfo = id 1490 n.addExprConjunct(c) // TODO: Pass from eval 1491 } 1492 return 1493 } 1494 1495 // TODO: evaluate value? 1496 switch v := x.BaseValue.(type) { 1497 default: 1498 panic(fmt.Sprintf("invalid type %T", x.BaseValue)) 1499 1500 case *ListMarker: 1501 n.vLists = append(n.vLists, x) 1502 return 1503 1504 case *StructMarker: 1505 1506 case Value: 1507 n.addValueConjunct(env, v, id) 1508 } 1509 1510 if len(x.Arcs) == 0 { 1511 return 1512 } 1513 1514 s := &StructLit{} 1515 1516 // Keep ordering of Go struct for topological sort. 1517 n.node.AddStruct(s, env, id) 1518 n.node.Structs = append(n.node.Structs, x.Structs...) 1519 1520 for _, a := range x.Arcs { 1521 // TODO(errors): report error when this is a regular field. 1522 c := MakeConjunct(nil, a, id) 1523 c = updateCyclic(c, cyclic, nil, nil) 1524 n.insertField(a.Label, c) 1525 s.MarkField(a.Label) 1526 } 1527 return 1528 } 1529 1530 switch b := v.(type) { 1531 case *Bottom: 1532 n.addBottom(b) 1533 return 1534 case *Builtin: 1535 if v := b.BareValidator(); v != nil { 1536 n.addValueConjunct(env, v, id) 1537 return 1538 } 1539 } 1540 1541 if !n.updateNodeType(v.Kind(), v, id) { 1542 return 1543 } 1544 1545 switch x := v.(type) { 1546 case *Disjunction: 1547 n.addDisjunctionValue(env, x, id) 1548 1549 case *Conjunction: 1550 for _, x := range x.Values { 1551 n.addValueConjunct(env, x, id) 1552 } 1553 1554 case *Top: 1555 n.hasTop = true 1556 1557 case *BasicType: 1558 // handled above 1559 1560 case *BoundValue: 1561 switch x.Op { 1562 case LessThanOp, LessEqualOp: 1563 if y := n.upperBound; y != nil { 1564 n.upperBound = nil 1565 v := SimplifyBounds(ctx, n.kind, x, y) 1566 if err := valueError(v); err != nil { 1567 err.AddPosition(v) 1568 err.AddPosition(n.upperBound) 1569 err.AddClosedPositions(id) 1570 } 1571 n.addValueConjunct(env, v, id) 1572 return 1573 } 1574 n.upperBound = x 1575 1576 case GreaterThanOp, GreaterEqualOp: 1577 if y := n.lowerBound; y != nil { 1578 n.lowerBound = nil 1579 v := SimplifyBounds(ctx, n.kind, x, y) 1580 if err := valueError(v); err != nil { 1581 err.AddPosition(v) 1582 err.AddPosition(n.lowerBound) 1583 err.AddClosedPositions(id) 1584 } 1585 n.addValueConjunct(env, v, id) 1586 return 1587 } 1588 n.lowerBound = x 1589 1590 case EqualOp, NotEqualOp, MatchOp, NotMatchOp: 1591 // This check serves as simplifier, but also to remove duplicates. 1592 k := 0 1593 match := false 1594 for _, c := range n.checks { 1595 if y, ok := c.(*BoundValue); ok { 1596 switch z := SimplifyBounds(ctx, n.kind, x, y); { 1597 case z == y: 1598 match = true 1599 case z == x: 1600 continue 1601 } 1602 } 1603 n.checks[k] = c 1604 k++ 1605 } 1606 n.checks = n.checks[:k] 1607 if !match { 1608 n.checks = append(n.checks, x) 1609 } 1610 return 1611 } 1612 1613 case Validator: 1614 // This check serves as simplifier, but also to remove duplicates. 1615 for i, y := range n.checks { 1616 if b := SimplifyValidator(ctx, x, y); b != nil { 1617 n.checks[i] = b 1618 return 1619 } 1620 } 1621 n.updateNodeType(x.Kind(), x, id) 1622 n.checks = append(n.checks, x) 1623 1624 case *Vertex: 1625 // handled above. 1626 1627 case Value: // *NullLit, *BoolLit, *NumLit, *StringLit, *BytesLit, *Builtin 1628 if y := n.scalar; y != nil { 1629 if b, ok := BinOp(ctx, EqualOp, x, y).(*Bool); !ok || !b.B { 1630 n.addConflict(x, y, x.Kind(), y.Kind(), n.scalarID, id) 1631 } 1632 // TODO: do we need to explicitly add again? 1633 // n.scalar = nil 1634 // n.addValueConjunct(c, BinOp(c, EqualOp, x, y)) 1635 break 1636 } 1637 n.scalar = x 1638 n.scalarID = id 1639 1640 default: 1641 panic(fmt.Sprintf("unknown value type %T", x)) 1642 } 1643 1644 if n.lowerBound != nil && n.upperBound != nil { 1645 if u := SimplifyBounds(ctx, n.kind, n.lowerBound, n.upperBound); u != nil { 1646 if err := valueError(u); err != nil { 1647 err.AddPosition(n.lowerBound) 1648 err.AddPosition(n.upperBound) 1649 err.AddClosedPositions(id) 1650 } 1651 n.lowerBound = nil 1652 n.upperBound = nil 1653 n.addValueConjunct(env, u, id) 1654 } 1655 } 1656} 1657 1658func valueError(v Value) *ValueError { 1659 if v == nil { 1660 return nil 1661 } 1662 b, _ := v.(*Bottom) 1663 if b == nil { 1664 return nil 1665 } 1666 err, _ := b.Err.(*ValueError) 1667 if err == nil { 1668 return nil 1669 } 1670 return err 1671} 1672 1673// addStruct collates the declarations of a struct. 1674// 1675// addStruct fulfills two additional pivotal functions: 1676// 1) Implement vertex unification (this happens through De Bruijn indices 1677// combined with proper set up of Environments). 1678// 2) Implied closedness for definitions. 1679// 1680func (n *nodeContext) addStruct( 1681 env *Environment, 1682 s *StructLit, 1683 closeInfo CloseInfo) { 1684 1685 n.updateCyclicStatus(env) // to handle empty structs. 1686 1687 ctx := n.ctx 1688 1689 // NOTE: This is a crucial point in the code: 1690 // Unification derferencing happens here. The child nodes are set to 1691 // an Environment linked to the current node. Together with the De Bruijn 1692 // indices, this determines to which Vertex a reference resolves. 1693 1694 // TODO(perf): consider using environment cache: 1695 // var childEnv *Environment 1696 // for _, s := range n.nodeCache.sub { 1697 // if s.Up == env { 1698 // childEnv = s 1699 // } 1700 // } 1701 childEnv := &Environment{ 1702 Up: env, 1703 Vertex: n.node, 1704 } 1705 if env != nil { 1706 childEnv.Cyclic = env.Cyclic 1707 childEnv.Deref = env.Deref 1708 } 1709 1710 s.Init() 1711 1712 if s.HasEmbed && !s.IsFile() { 1713 closeInfo = closeInfo.SpawnGroup(nil) 1714 } 1715 1716 parent := n.node.AddStruct(s, childEnv, closeInfo) 1717 closeInfo.IsClosed = false 1718 parent.Disable = true // disable until processing is done. 1719 1720 for _, d := range s.Decls { 1721 switch x := d.(type) { 1722 case *Field: 1723 // handle in next iteration. 1724 1725 case *DynamicField: 1726 n.aStruct = s 1727 n.aStructID = closeInfo 1728 n.dynamicFields = append(n.dynamicFields, envDynamic{childEnv, x, closeInfo, nil}) 1729 1730 case *ForClause: 1731 // Why is this not an embedding? 1732 n.forClauses = append(n.forClauses, envYield{childEnv, x, closeInfo, nil}) 1733 1734 case Yielder: 1735 // Why is this not an embedding? 1736 n.ifClauses = append(n.ifClauses, envYield{childEnv, x, closeInfo, nil}) 1737 1738 case Expr: 1739 // add embedding to optional 1740 1741 // TODO(perf): only do this if addExprConjunct below will result in 1742 // a fieldSet. Otherwise the entry will just be removed next. 1743 id := closeInfo.SpawnEmbed(x) 1744 1745 // push and opo embedding type. 1746 n.addExprConjunct(MakeConjunct(childEnv, x, id)) 1747 1748 case *OptionalField, *BulkOptionalField, *Ellipsis: 1749 // Nothing to do here. Note that the precense of these fields do not 1750 // excluded embedded scalars: only when they match actual fields 1751 // does it exclude those. 1752 1753 default: 1754 panic("unreachable") 1755 } 1756 } 1757 1758 if !s.HasEmbed { 1759 n.aStruct = s 1760 n.aStructID = closeInfo 1761 } 1762 1763 // Apply existing fields 1764 for _, arc := range n.node.Arcs { 1765 // Reuse Acceptor interface. 1766 parent.MatchAndInsert(ctx, arc) 1767 } 1768 1769 parent.Disable = false 1770 1771 for _, d := range s.Decls { 1772 switch x := d.(type) { 1773 case *Field: 1774 if x.Label.IsString() { 1775 n.aStruct = s 1776 n.aStructID = closeInfo 1777 } 1778 n.insertField(x.Label, MakeConjunct(childEnv, x, closeInfo)) 1779 } 1780 } 1781} 1782 1783// TODO(perf): if an arc is the only arc with that label added to a Vertex, and 1784// if there are no conjuncts of optional fields to be added, then the arc could 1785// be added as is until any of these conditions change. This would allow 1786// structure sharing in many cases. One should be careful, however, to 1787// recursively track arcs of previously unified evaluated vertices ot make this 1788// optimization meaningful. 1789// 1790// An alternative approach to avoid evaluating optional arcs (if we take that 1791// route) is to not recursively evaluate those arcs, even for Finalize. This is 1792// possible as it is not necessary to evaluate optional arcs to evaluate 1793// disjunctions. 1794func (n *nodeContext) insertField(f Feature, x Conjunct) *Vertex { 1795 ctx := n.ctx 1796 arc, isNew := n.node.GetArc(ctx, f) 1797 1798 arc.addConjunct(x) 1799 1800 switch { 1801 case isNew: 1802 for _, s := range n.node.Structs { 1803 if s.Disable { 1804 continue 1805 } 1806 s.MatchAndInsert(ctx, arc) 1807 } 1808 1809 case arc.state != nil: 1810 s := arc.state 1811 switch { 1812 case arc.Status() <= AllArcs: 1813 // This may happen when a struct has multiple comprehensions, where 1814 // the insertion of one of which depends on the outcome of another. 1815 1816 // TODO: to something more principled by allowing values to 1817 // monotonically increase. 1818 arc.status = Partial 1819 arc.BaseValue = nil 1820 s.disjuncts = s.disjuncts[:0] 1821 s.disjunctErrs = s.disjunctErrs[:0] 1822 1823 fallthrough 1824 1825 default: 1826 arc.state.addExprConjunct(x) 1827 } 1828 1829 case arc.Status() == 0: 1830 default: 1831 n.addErr(ctx.NewPosf(pos(x.Field()), 1832 "cannot add field %s: was already used", 1833 f.SelectorString(ctx))) 1834 } 1835 return arc 1836} 1837 1838// expandOne adds dynamic fields to a node until a fixed point is reached. 1839// On each iteration, dynamic fields that cannot resolve due to incomplete 1840// values are skipped. They will be retried on the next iteration until no 1841// progress can be made. Note that a dynamic field may add more dynamic fields. 1842// 1843// forClauses are processed after all other clauses. A struct may be referenced 1844// before it is complete, meaning that fields added by other forms of injection 1845// may influence the result of a for clause _after_ it has already been 1846// processed. We could instead detect such insertion and feed it to the 1847// ForClause to generate another entry or have the for clause be recomputed. 1848// This seems to be too complicated and lead to iffy edge cases. 1849// TODO(errors): detect when a field is added to a struct that is already used 1850// in a for clause. 1851func (n *nodeContext) expandOne() (done bool) { 1852 // Don't expand incomplete expressions if we detected a cycle. 1853 if n.done() || (n.hasCycle && !n.hasNonCycle) { 1854 return false 1855 } 1856 1857 var progress bool 1858 1859 if progress = n.injectDynamic(); progress { 1860 return true 1861 } 1862 1863 if progress = n.injectEmbedded(&(n.ifClauses)); progress { 1864 return true 1865 } 1866 1867 if progress = n.injectEmbedded(&(n.forClauses)); progress { 1868 return true 1869 } 1870 1871 // Do expressions after comprehensions, as comprehensions can never 1872 // refer to embedded scalars, whereas expressions may refer to generated 1873 // fields if we were to allow attributes to be defined alongside 1874 // scalars. 1875 exprs := n.exprs 1876 n.exprs = n.exprs[:0] 1877 for _, x := range exprs { 1878 n.addExprConjunct(x.c) 1879 1880 // collect and and or 1881 } 1882 if len(n.exprs) < len(exprs) { 1883 return true 1884 } 1885 1886 // No progress, report error later if needed: unification with 1887 // disjuncts may resolve this later later on. 1888 return false 1889} 1890 1891// injectDynamic evaluates and inserts dynamic declarations. 1892func (n *nodeContext) injectDynamic() (progress bool) { 1893 ctx := n.ctx 1894 k := 0 1895 1896 a := n.dynamicFields 1897 for _, d := range n.dynamicFields { 1898 var f Feature 1899 v, complete := ctx.Evaluate(d.env, d.field.Key) 1900 if !complete { 1901 d.err, _ = v.(*Bottom) 1902 a[k] = d 1903 k++ 1904 continue 1905 } 1906 if b, _ := v.(*Bottom); b != nil { 1907 n.addValueConjunct(nil, b, d.id) 1908 continue 1909 } 1910 f = ctx.Label(d.field.Key, v) 1911 n.insertField(f, MakeConjunct(d.env, d.field, d.id)) 1912 } 1913 1914 progress = k < len(n.dynamicFields) 1915 1916 n.dynamicFields = a[:k] 1917 1918 return progress 1919} 1920 1921// injectEmbedded evaluates and inserts embeddings. It first evaluates all 1922// embeddings before inserting the results to ensure that the order of 1923// evaluation does not matter. 1924func (n *nodeContext) injectEmbedded(all *[]envYield) (progress bool) { 1925 ctx := n.ctx 1926 type envStruct struct { 1927 env *Environment 1928 s *StructLit 1929 } 1930 var sa []envStruct 1931 f := func(env *Environment, st *StructLit) { 1932 sa = append(sa, envStruct{env, st}) 1933 } 1934 1935 k := 0 1936 for i := 0; i < len(*all); i++ { 1937 d := (*all)[i] 1938 sa = sa[:0] 1939 1940 if err := ctx.Yield(d.env, d.yield, f); err != nil { 1941 if err.IsIncomplete() { 1942 d.err = err 1943 (*all)[k] = d 1944 k++ 1945 } else { 1946 // continue to collect other errors. 1947 n.addBottom(err) 1948 } 1949 continue 1950 } 1951 1952 if len(sa) == 0 { 1953 continue 1954 } 1955 id := d.id.SpawnSpan(d.yield, ComprehensionSpan) 1956 1957 n.ctx.nonMonotonicInsertNest++ 1958 for _, st := range sa { 1959 n.addStruct(st.env, st.s, id) 1960 } 1961 n.ctx.nonMonotonicInsertNest-- 1962 } 1963 1964 progress = k < len(*all) 1965 1966 *all = (*all)[:k] 1967 1968 return progress 1969} 1970 1971// addLists 1972// 1973// TODO: association arrays: 1974// If an association array marker was present in a struct, create a struct node 1975// instead of a list node. In either case, a node may only have list fields 1976// or struct fields and not both. 1977// 1978// addLists should be run after the fixpoint expansion: 1979// - it enforces that comprehensions may not refer to the list itself 1980// - there may be no other fields within the list. 1981// 1982// TODO(embeddedScalars): for embedded scalars, there should be another pass 1983// of evaluation expressions after expanding lists. 1984func (n *nodeContext) addLists() (oneOfTheLists Expr, anID CloseInfo) { 1985 if len(n.lists) == 0 && len(n.vLists) == 0 { 1986 return nil, CloseInfo{} 1987 } 1988 1989 isOpen := true 1990 max := 0 1991 var maxNode Expr 1992 1993 if m, ok := n.node.BaseValue.(*ListMarker); ok { 1994 isOpen = m.IsOpen 1995 max = len(n.node.Arcs) 1996 } 1997 1998 c := n.ctx 1999 2000 for _, l := range n.vLists { 2001 oneOfTheLists = l 2002 2003 elems := l.Elems() 2004 isClosed := l.IsClosedList() 2005 2006 switch { 2007 case len(elems) < max: 2008 if isClosed { 2009 n.invalidListLength(len(elems), max, l, maxNode) 2010 continue 2011 } 2012 2013 case len(elems) > max: 2014 if !isOpen { 2015 n.invalidListLength(max, len(elems), maxNode, l) 2016 continue 2017 } 2018 isOpen = !isClosed 2019 max = len(elems) 2020 maxNode = l 2021 2022 case isClosed: 2023 isOpen = false 2024 maxNode = l 2025 } 2026 2027 for _, a := range elems { 2028 if a.Conjuncts == nil { 2029 x := a.BaseValue.(Value) 2030 n.insertField(a.Label, MakeConjunct(nil, x, CloseInfo{})) 2031 continue 2032 } 2033 for _, c := range a.Conjuncts { 2034 n.insertField(a.Label, c) 2035 } 2036 } 2037 } 2038 2039outer: 2040 for i, l := range n.lists { 2041 n.updateCyclicStatus(l.env) 2042 2043 index := int64(0) 2044 hasComprehension := false 2045 for j, elem := range l.list.Elems { 2046 switch x := elem.(type) { 2047 case Yielder: 2048 err := c.Yield(l.env, x, func(e *Environment, st *StructLit) { 2049 label, err := MakeLabel(x.Source(), index, IntLabel) 2050 n.addErr(err) 2051 index++ 2052 c := MakeConjunct(e, st, l.id) 2053 n.insertField(label, c) 2054 }) 2055 hasComprehension = true 2056 if err != nil { 2057 n.addBottom(err) 2058 continue outer 2059 } 2060 2061 case *Ellipsis: 2062 if j != len(l.list.Elems)-1 { 2063 n.addErr(c.Newf("ellipsis must be last element in list")) 2064 } 2065 2066 n.lists[i].elipsis = x 2067 2068 default: 2069 label, err := MakeLabel(x.Source(), index, IntLabel) 2070 n.addErr(err) 2071 index++ // TODO: don't use insertField. 2072 n.insertField(label, MakeConjunct(l.env, x, l.id)) 2073 } 2074 2075 // Terminate early in case of runaway comprehension. 2076 if !isOpen && int(index) > max { 2077 n.invalidListLength(max, len(l.list.Elems), maxNode, l.list) 2078 continue outer 2079 } 2080 } 2081 2082 oneOfTheLists = l.list 2083 anID = l.id 2084 2085 switch closed := n.lists[i].elipsis == nil; { 2086 case int(index) < max: 2087 if closed { 2088 n.invalidListLength(int(index), max, l.list, maxNode) 2089 continue 2090 } 2091 2092 case int(index) > max, 2093 closed && isOpen, 2094 (!closed == isOpen) && !hasComprehension: 2095 max = int(index) 2096 maxNode = l.list 2097 isOpen = !closed 2098 } 2099 2100 n.lists[i].n = index 2101 } 2102 2103 // add additionalItem values to list and construct optionals. 2104 elems := n.node.Elems() 2105 for _, l := range n.vLists { 2106 if !l.IsClosedList() { 2107 continue 2108 } 2109 2110 newElems := l.Elems() 2111 if len(newElems) >= len(elems) { 2112 continue // error generated earlier, if applicable. 2113 } 2114 2115 for _, arc := range elems[len(newElems):] { 2116 l.MatchAndInsert(c, arc) 2117 } 2118 } 2119 2120 for _, l := range n.lists { 2121 if l.elipsis == nil { 2122 continue 2123 } 2124 2125 s := &StructLit{Decls: []Decl{l.elipsis}} 2126 s.Init() 2127 info := n.node.AddStruct(s, l.env, l.id) 2128 2129 for _, arc := range elems[l.n:] { 2130 info.MatchAndInsert(c, arc) 2131 } 2132 } 2133 2134 sources := []ast.Expr{} 2135 // Add conjuncts for additional items. 2136 for _, l := range n.lists { 2137 if l.elipsis == nil { 2138 continue 2139 } 2140 if src, _ := l.elipsis.Source().(ast.Expr); src != nil { 2141 sources = append(sources, src) 2142 } 2143 } 2144 2145 if m, ok := n.node.BaseValue.(*ListMarker); !ok { 2146 n.node.SetValue(c, Partial, &ListMarker{ 2147 Src: ast.NewBinExpr(token.AND, sources...), 2148 IsOpen: isOpen, 2149 }) 2150 } else { 2151 if expr, _ := m.Src.(ast.Expr); expr != nil { 2152 sources = append(sources, expr) 2153 } 2154 m.Src = ast.NewBinExpr(token.AND, sources...) 2155 m.IsOpen = m.IsOpen && isOpen 2156 } 2157 2158 n.lists = n.lists[:0] 2159 n.vLists = n.vLists[:0] 2160 2161 return oneOfTheLists, anID 2162} 2163 2164func (n *nodeContext) invalidListLength(na, nb int, a, b Expr) { 2165 n.addErr(n.ctx.Newf("incompatible list lengths (%d and %d)", na, nb)) 2166} 2167