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 15package adt 16 17import ( 18 "fmt" 19 20 "cuelang.org/go/cue/ast" 21 "cuelang.org/go/cue/errors" 22 "cuelang.org/go/cue/token" 23) 24 25// TODO: unanswered questions about structural cycles: 26// 27// 1. When detecting a structural cycle, should we consider this as: 28// a) an unevaluated value, 29// b) an incomplete error (which does not affect parent validity), or 30// c) a special value. 31// 32// Making it an error is the simplest way to ensure reentrancy is disallowed: 33// without an error it would require an additional mechanism to stop reentrancy 34// from continuing to process. Even worse, in some cases it may only partially 35// evaluate, resulting in unexpected results. For this reason, we are taking 36// approach `b` for now. 37// 38// This has some consequences of how disjunctions are treated though. Consider 39// 40// list: { 41// head: _ 42// tail: list | null 43// } 44// 45// When making it an error, evaluating the above will result in 46// 47// list: { 48// head: _ 49// tail: null 50// } 51// 52// because list will result in a structural cycle, and thus an error, it will be 53// stripped from the disjunction. This may or may not be a desirable property. A 54// nice thing is that it is not required to write `list | *null`. A disadvantage 55// is that this is perhaps somewhat inexplicit. 56// 57// When not making it an error (and simply cease evaluating child arcs upon 58// cycle detection), the result would be: 59// 60// list: { 61// head: _ 62// tail: list | null 63// } 64// 65// In other words, an evaluation would result in a cycle and thus an error. 66// Implementations can recognize such cases by having unevaluated arcs. An 67// explicit structure cycle marker would probably be less error prone. 68// 69// Note that in both cases, a reference to list will still use the original 70// conjuncts, so the result will be the same for either method in this case. 71// 72// 73// 2. Structural cycle allowance. 74// 75// Structural cycle detection disallows reentrancy as well. This means one 76// cannot use structs for recursive computation. This will probably preclude 77// evaluation of some configuration. Given that there is no real alternative 78// yet, we could allow structural cycle detection to be optionally disabled. 79 80// An Environment links the parent scopes for identifier lookup to a composite 81// node. Each conjunct that make up node in the tree can be associated with 82// a different environment (although some conjuncts may share an Environment). 83type Environment struct { 84 Up *Environment 85 Vertex *Vertex 86 87 // DynamicLabel is only set when instantiating a field from a pattern 88 // constraint. It is used to resolve label references. 89 DynamicLabel Feature 90 91 // TODO(perf): make the following public fields a shareable struct as it 92 // mostly is going to be the same for child nodes. 93 94 // Cyclic indicates a structural cycle was detected for this conjunct or one 95 // of its ancestors. 96 Cyclic bool 97 98 // Deref keeps track of nodes that should dereference to Vertex. It is used 99 // for detecting structural cycle. 100 // 101 // The detection algorithm is based on Tomabechi's quasi-destructive graph 102 // unification. This detection requires dependencies to be resolved into 103 // fully dereferenced vertices. This is not the case in our algorithm: 104 // the result of evaluating conjuncts is placed into dereferenced vertices 105 // _after_ they are evaluated, but the Environment still points to the 106 // non-dereferenced context. 107 // 108 // In order to be able to detect structural cycles, we need to ensure that 109 // at least one node that is part of a cycle in the context in which 110 // conjunctions are evaluated dereferences correctly. 111 // 112 // The only field necessary to detect a structural cycle, however, is 113 // the Status field of the Vertex. So rather than dereferencing a node 114 // proper, it is sufficient to copy the Status of the dereferenced nodes 115 // to these nodes (will always be EvaluatingArcs). 116 Deref []*Vertex 117 118 // Cycles contains vertices for which cycles are detected. It is used 119 // for tracking self-references within structural cycles. 120 // 121 // Unlike Deref, Cycles is not incremented with child nodes. 122 // TODO: Cycles is always a tail end of Deref, so this can be optimized. 123 Cycles []*Vertex 124 125 cache map[Expr]Value 126} 127 128type ID int32 129 130// evalCached is used to look up let expressions. Caching let expressions 131// prevents a possible combinatorial explosion. 132func (e *Environment) evalCached(c *OpContext, x Expr) Value { 133 if v, ok := x.(Value); ok { 134 return v 135 } 136 v, ok := e.cache[x] 137 if !ok { 138 if e.cache == nil { 139 e.cache = map[Expr]Value{} 140 } 141 env, src := c.e, c.src 142 c.e, c.src = e, x.Source() 143 v = c.evalState(x, Partial) // TODO: should this be Finalized? 144 c.e, c.src = env, src 145 e.cache[x] = v 146 } 147 return v 148} 149 150// A Vertex is a node in the value tree. It may be a leaf or internal node. 151// It may have arcs to represent elements of a fully evaluated struct or list. 152// 153// For structs, it only contains definitions and concrete fields. 154// optional fields are dropped. 155// 156// It maintains source information such as a list of conjuncts that contributed 157// to the value. 158type Vertex struct { 159 // Parent links to a parent Vertex. This parent should only be used to 160 // access the parent's Label field to find the relative location within a 161 // tree. 162 Parent *Vertex 163 164 // Label is the feature leading to this vertex. 165 Label Feature 166 167 // State: 168 // eval: nil, BaseValue: nil -- unevaluated 169 // eval: *, BaseValue: nil -- evaluating 170 // eval: *, BaseValue: * -- finalized 171 // 172 state *nodeContext 173 // TODO: move the following status fields to nodeContext. 174 175 // status indicates the evaluation progress of this vertex. 176 status VertexStatus 177 178 // isData indicates that this Vertex is to be interepreted as data: pattern 179 // and additional constraints, as well as optional fields, should be 180 // ignored. 181 isData bool 182 Closed bool 183 nonMonotonicReject bool 184 nonMonotonicInsertGen int32 185 nonMonotonicLookupGen int32 186 187 // EvalCount keeps track of temporary dereferencing during evaluation. 188 // If EvalCount > 0, status should be considered to be EvaluatingArcs. 189 EvalCount int32 190 191 // SelfCount is used for tracking self-references. 192 SelfCount int32 193 194 // BaseValue is the value associated with this vertex. For lists and structs 195 // this is a sentinel value indicating its kind. 196 BaseValue BaseValue 197 198 // ChildErrors is the collection of all errors of children. 199 ChildErrors *Bottom 200 201 // The parent of nodes can be followed to determine the path within the 202 // configuration of this node. 203 // Value Value 204 Arcs []*Vertex // arcs are sorted in display order. 205 206 // Conjuncts lists the structs that ultimately formed this Composite value. 207 // This includes all selected disjuncts. 208 // 209 // This value may be nil, in which case the Arcs are considered to define 210 // the final value of this Vertex. 211 Conjuncts []Conjunct 212 213 // Structs is a slice of struct literals that contributed to this value. 214 // This information is used to compute the topological sort of arcs. 215 Structs []*StructInfo 216} 217 218type StructInfo struct { 219 *StructLit 220 221 Env *Environment 222 223 CloseInfo 224 225 // Embed indicates the struct in which this struct is embedded (originally), 226 // or nil if this is a root structure. 227 // Embed *StructInfo 228 // Context *RefInfo // the location from which this struct originates. 229 Disable bool 230 231 Embedding bool 232} 233 234// TODO(perf): this could be much more aggressive for eliminating structs that 235// are immaterial for closing. 236func (s *StructInfo) useForAccept() bool { 237 if c := s.closeInfo; c != nil { 238 return !c.noCheck 239 } 240 return true 241} 242 243// VertexStatus indicates the evaluation progress of a Vertex. 244type VertexStatus int8 245 246const ( 247 // Unprocessed indicates a Vertex has not been processed before. 248 // Value must be nil. 249 Unprocessed VertexStatus = iota 250 251 // Evaluating means that the current Vertex is being evaluated. If this is 252 // encountered it indicates a reference cycle. Value must be nil. 253 Evaluating 254 255 // Partial indicates that the result was only partially evaluated. It will 256 // need to be fully evaluated to get a complete results. 257 // 258 // TODO: this currently requires a renewed computation. Cache the 259 // nodeContext to allow reusing the computations done so far. 260 Partial 261 262 // AllArcs is request only. It must be past Partial, but 263 // before recursively resolving arcs. 264 AllArcs 265 266 // EvaluatingArcs indicates that the arcs of the Vertex are currently being 267 // evaluated. If this is encountered it indicates a structural cycle. 268 // Value does not have to be nil 269 EvaluatingArcs 270 271 // Finalized means that this node is fully evaluated and that the results 272 // are save to use without further consideration. 273 Finalized 274) 275 276func (s VertexStatus) String() string { 277 switch s { 278 case Unprocessed: 279 return "unprocessed" 280 case Evaluating: 281 return "evaluating" 282 case Partial: 283 return "partial" 284 case AllArcs: 285 return "allarcs" 286 case EvaluatingArcs: 287 return "evaluatingArcs" 288 case Finalized: 289 return "finalized" 290 default: 291 return "unknown" 292 } 293} 294 295func (v *Vertex) Status() VertexStatus { 296 if v.EvalCount > 0 { 297 return EvaluatingArcs 298 } 299 return v.status 300} 301 302func (v *Vertex) UpdateStatus(s VertexStatus) { 303 Assertf(v.status <= s+1, "attempt to regress status from %d to %d", v.Status(), s) 304 305 if s == Finalized && v.BaseValue == nil { 306 // panic("not finalized") 307 } 308 v.status = s 309} 310 311// Value returns the Value of v without definitions if it is a scalar 312// or itself otherwise. 313func (v *Vertex) Value() Value { 314 switch x := v.BaseValue.(type) { 315 case nil: 316 return nil 317 case *StructMarker, *ListMarker: 318 return v 319 case Value: 320 return x 321 default: 322 panic(fmt.Sprintf("unexpected type %T", v.BaseValue)) 323 } 324} 325 326// isUndefined reports whether a vertex does not have a useable BaseValue yet. 327func (v *Vertex) isUndefined() bool { 328 switch v.BaseValue { 329 case nil, cycle: 330 return true 331 } 332 return false 333} 334 335func (x *Vertex) IsConcrete() bool { 336 return x.Concreteness() <= Concrete 337} 338 339// IsData reports whether v should be interpreted in data mode. In other words, 340// it tells whether optional field matching and non-regular fields, like 341// definitions and hidden fields, should be ignored. 342func (v *Vertex) IsData() bool { 343 return v.isData || len(v.Conjuncts) == 0 344} 345 346// ToDataSingle creates a new Vertex that represents just the regular fields 347// of this vertex. Arcs are left untouched. 348// It is used by cue.Eval to convert nodes to data on per-node basis. 349func (v *Vertex) ToDataSingle() *Vertex { 350 w := *v 351 w.isData = true 352 w.state = nil 353 w.status = Finalized 354 return &w 355} 356 357// ToDataAll returns a new v where v and all its descendents contain only 358// the regular fields. 359func (v *Vertex) ToDataAll() *Vertex { 360 arcs := make([]*Vertex, 0, len(v.Arcs)) 361 for _, a := range v.Arcs { 362 if a.Label.IsRegular() { 363 arcs = append(arcs, a.ToDataAll()) 364 } 365 } 366 w := *v 367 w.state = nil 368 w.status = Finalized 369 370 w.BaseValue = toDataAll(w.BaseValue) 371 w.Arcs = arcs 372 w.isData = true 373 w.Conjuncts = make([]Conjunct, len(v.Conjuncts)) 374 // TODO(perf): this is not strictly necessary for evaluation, but it can 375 // hurt performance greatly. Drawback is that it may disable ordering. 376 for _, s := range w.Structs { 377 s.Disable = true 378 } 379 copy(w.Conjuncts, v.Conjuncts) 380 for i, c := range w.Conjuncts { 381 if v, _ := c.x.(Value); v != nil { 382 w.Conjuncts[i].x = toDataAll(v).(Value) 383 } 384 } 385 return &w 386} 387 388func toDataAll(v BaseValue) BaseValue { 389 switch x := v.(type) { 390 default: 391 return x 392 393 case *Vertex: 394 return x.ToDataAll() 395 396 // The following cases are always erroneous, but we handle them anyway 397 // to avoid issues with the closedness algorithm down the line. 398 case *Disjunction: 399 d := *x 400 d.Values = make([]*Vertex, len(x.Values)) 401 for i, v := range x.Values { 402 d.Values[i] = v.ToDataAll() 403 } 404 return &d 405 406 case *Conjunction: 407 c := *x 408 c.Values = make([]Value, len(x.Values)) 409 for i, v := range x.Values { 410 // This case is okay because the source is of type Value. 411 c.Values[i] = toDataAll(v).(Value) 412 } 413 return &c 414 } 415} 416 417// func (v *Vertex) IsEvaluating() bool { 418// return v.Value == cycle 419// } 420 421func (v *Vertex) IsErr() bool { 422 // if v.Status() > Evaluating { 423 if _, ok := v.BaseValue.(*Bottom); ok { 424 return true 425 } 426 // } 427 return false 428} 429 430func (v *Vertex) Err(c *OpContext, state VertexStatus) *Bottom { 431 c.Unify(v, state) 432 if b, ok := v.BaseValue.(*Bottom); ok { 433 return b 434 } 435 return nil 436} 437 438// func (v *Vertex) Evaluate() 439 440func (v *Vertex) Finalize(c *OpContext) { 441 // Saving and restoring the error context prevents v from panicking in 442 // case the caller did not handle existing errors in the context. 443 err := c.errs 444 c.errs = nil 445 c.Unify(v, Finalized) 446 c.errs = err 447} 448 449func (v *Vertex) AddErr(ctx *OpContext, b *Bottom) { 450 v.BaseValue = CombineErrors(nil, v.Value(), b) 451 v.UpdateStatus(Finalized) 452} 453 454func (v *Vertex) SetValue(ctx *OpContext, state VertexStatus, value BaseValue) *Bottom { 455 v.BaseValue = value 456 v.UpdateStatus(state) 457 return nil 458} 459 460// ToVertex wraps v in a new Vertex, if necessary. 461func ToVertex(v Value) *Vertex { 462 switch x := v.(type) { 463 case *Vertex: 464 return x 465 default: 466 n := &Vertex{ 467 status: Finalized, 468 BaseValue: x, 469 } 470 n.AddConjunct(MakeRootConjunct(nil, v)) 471 return n 472 } 473} 474 475// Unwrap returns the possibly non-concrete scalar value of v or nil if v is 476// a list, struct or of undefined type. 477func Unwrap(v Value) Value { 478 x, ok := v.(*Vertex) 479 if !ok { 480 return v 481 } 482 // b, _ := x.BaseValue.(*Bottom) 483 if n := x.state; n != nil && isCyclePlaceholder(x.BaseValue) { 484 if n.errs != nil && !n.errs.IsIncomplete() { 485 return n.errs 486 } 487 if n.scalar != nil { 488 return n.scalar 489 } 490 } 491 return x.Value() 492} 493 494// OptionalType is a bit field of the type of optional constraints in use by an 495// Acceptor. 496type OptionalType int8 497 498const ( 499 HasField OptionalType = 1 << iota // X: T 500 HasDynamic // (X): T or "\(X)": T 501 HasPattern // [X]: T 502 HasComplexPattern // anything but a basic type 503 HasAdditional // ...T 504 IsOpen // Defined for all fields 505) 506 507func (v *Vertex) Kind() Kind { 508 // This is possible when evaluating comprehensions. It is potentially 509 // not known at this time what the type is. 510 switch { 511 case v.state != nil: 512 return v.state.kind 513 case v.BaseValue == nil: 514 return TopKind 515 default: 516 return v.BaseValue.Kind() 517 } 518} 519 520func (v *Vertex) OptionalTypes() OptionalType { 521 var mask OptionalType 522 for _, s := range v.Structs { 523 mask |= s.OptionalTypes() 524 } 525 return mask 526} 527 528// IsOptional reports whether a field is explicitly defined as optional, 529// as opposed to whether it is allowed by a pattern constraint. 530func (v *Vertex) IsOptional(label Feature) bool { 531 for _, s := range v.Structs { 532 if s.IsOptional(label) { 533 return true 534 } 535 } 536 return false 537} 538 539func (v *Vertex) accepts(ok, required bool) bool { 540 return ok || (!required && !v.Closed) 541} 542 543func (v *Vertex) IsClosedStruct() bool { 544 switch x := v.BaseValue.(type) { 545 default: 546 return false 547 548 case *StructMarker: 549 if x.NeedClose { 550 return true 551 } 552 553 case *Disjunction: 554 } 555 return v.Closed || isClosed(v) 556} 557 558func (v *Vertex) IsClosedList() bool { 559 if x, ok := v.BaseValue.(*ListMarker); ok { 560 return !x.IsOpen 561 } 562 return false 563} 564 565// TODO: return error instead of boolean? (or at least have version that does.) 566func (v *Vertex) Accept(ctx *OpContext, f Feature) bool { 567 if f.IsInt() { 568 switch x := v.BaseValue.(type) { 569 case *ListMarker: 570 // TODO(perf): use precomputed length. 571 if f.Index() < len(v.Elems()) { 572 return true 573 } 574 return !v.IsClosedList() 575 576 case *Disjunction: 577 for _, v := range x.Values { 578 if v.Accept(ctx, f) { 579 return true 580 } 581 } 582 return false 583 584 default: 585 return v.Kind()&ListKind != 0 586 } 587 } 588 589 if k := v.Kind(); k&StructKind == 0 && f.IsString() && f != AnyLabel { 590 // If the value is bottom, we may not really know if this used to 591 // be a struct. 592 if k != BottomKind || len(v.Structs) == 0 { 593 return false 594 } 595 } 596 597 if f.IsHidden() || !v.IsClosedStruct() || v.Lookup(f) != nil { 598 return true 599 } 600 601 // TODO(perf): collect positions in error. 602 defer ctx.ReleasePositions(ctx.MarkPositions()) 603 604 return v.accepts(Accept(ctx, v, f)) 605} 606 607// MatchAndInsert finds the conjuncts for optional fields, pattern 608// constraints, and additional constraints that match f and inserts them in 609// arc. Use f is 0 to match all additional constraints only. 610func (v *Vertex) MatchAndInsert(ctx *OpContext, arc *Vertex) { 611 if !v.Accept(ctx, arc.Label) { 612 return 613 } 614 615 // Go backwards to simulate old implementation. 616 for i := len(v.Structs) - 1; i >= 0; i-- { 617 s := v.Structs[i] 618 if s.Disable { 619 continue 620 } 621 s.MatchAndInsert(ctx, arc) 622 } 623} 624 625func (v *Vertex) IsList() bool { 626 _, ok := v.BaseValue.(*ListMarker) 627 return ok 628} 629 630// Lookup returns the Arc with label f if it exists or nil otherwise. 631func (v *Vertex) Lookup(f Feature) *Vertex { 632 for _, a := range v.Arcs { 633 if a.Label == f { 634 return a 635 } 636 } 637 return nil 638} 639 640// Elems returns the regular elements of a list. 641func (v *Vertex) Elems() []*Vertex { 642 // TODO: add bookkeeping for where list arcs start and end. 643 a := make([]*Vertex, 0, len(v.Arcs)) 644 for _, x := range v.Arcs { 645 if x.Label.IsInt() { 646 a = append(a, x) 647 } 648 } 649 return a 650} 651 652// GetArc returns a Vertex for the outgoing arc with label f. It creates and 653// ads one if it doesn't yet exist. 654func (v *Vertex) GetArc(c *OpContext, f Feature) (arc *Vertex, isNew bool) { 655 arc = v.Lookup(f) 656 if arc == nil { 657 for _, a := range v.state.usedArcs { 658 if a.Label == f { 659 arc = a 660 v.Arcs = append(v.Arcs, arc) 661 isNew = true 662 if c.nonMonotonicInsertNest > 0 { 663 a.nonMonotonicInsertGen = c.nonMonotonicGeneration 664 } 665 break 666 } 667 } 668 } 669 if arc == nil { 670 arc = &Vertex{Parent: v, Label: f} 671 v.Arcs = append(v.Arcs, arc) 672 isNew = true 673 if c.nonMonotonicInsertNest > 0 { 674 arc.nonMonotonicInsertGen = c.nonMonotonicGeneration 675 } 676 } 677 if c.nonMonotonicInsertNest == 0 { 678 arc.nonMonotonicInsertGen = 0 679 } 680 return arc, isNew 681} 682 683func (v *Vertex) Source() ast.Node { 684 if v != nil { 685 if b, ok := v.BaseValue.(Value); ok { 686 return b.Source() 687 } 688 } 689 return nil 690} 691 692// AddConjunct adds the given Conjuncts to v if it doesn't already exist. 693func (v *Vertex) AddConjunct(c Conjunct) *Bottom { 694 if v.BaseValue != nil { 695 // TODO: investigate why this happens at all. Removing it seems to 696 // change the order of fields in some cases. 697 // 698 // This is likely a bug in the evaluator and should not happen. 699 return &Bottom{Err: errors.Newf(token.NoPos, "cannot add conjunct")} 700 } 701 v.addConjunct(c) 702 return nil 703} 704 705func (v *Vertex) addConjunct(c Conjunct) { 706 for _, x := range v.Conjuncts { 707 if x == c { 708 return 709 } 710 } 711 v.Conjuncts = append(v.Conjuncts, c) 712} 713 714func (v *Vertex) AddStruct(s *StructLit, env *Environment, ci CloseInfo) *StructInfo { 715 info := StructInfo{ 716 StructLit: s, 717 Env: env, 718 CloseInfo: ci, 719 } 720 for _, t := range v.Structs { 721 if *t == info { 722 return t 723 } 724 } 725 t := &info 726 v.Structs = append(v.Structs, t) 727 return t 728} 729 730// Path computes the sequence of Features leading from the root to of the 731// instance to this Vertex. 732// 733// NOTE: this is for debugging purposes only. 734func (v *Vertex) Path() []Feature { 735 return appendPath(nil, v) 736} 737 738func appendPath(a []Feature, v *Vertex) []Feature { 739 if v.Parent == nil { 740 return a 741 } 742 a = appendPath(a, v.Parent) 743 if v.Label != 0 { 744 // A Label may be 0 for programmatically inserted nodes. 745 a = append(a, v.Label) 746 } 747 return a 748} 749 750// An Conjunct is an Environment-Expr pair. The Environment is the starting 751// point for reference lookup for any reference contained in X. 752type Conjunct struct { 753 Env *Environment 754 x Node 755 756 // CloseInfo is a unique number that tracks a group of conjuncts that need 757 // belong to a single originating definition. 758 CloseInfo CloseInfo 759} 760 761// TODO(perf): replace with composite literal if this helps performance. 762 763// MakeRootConjunct creates a conjunct from the given environment and node. 764// It panics if x cannot be used as an expression. 765func MakeRootConjunct(env *Environment, x Node) Conjunct { 766 return MakeConjunct(env, x, CloseInfo{}) 767} 768 769func MakeConjunct(env *Environment, x Node, id CloseInfo) Conjunct { 770 if env == nil { 771 // TODO: better is to pass one. 772 env = &Environment{} 773 } 774 switch x.(type) { 775 case Expr, interface{ expr() Expr }: 776 default: 777 panic(fmt.Sprintf("invalid Node type %T", x)) 778 } 779 return Conjunct{env, x, id} 780} 781 782func (c *Conjunct) Source() ast.Node { 783 return c.x.Source() 784} 785 786func (c *Conjunct) Field() Node { 787 return c.x 788} 789 790func (c *Conjunct) Expr() Expr { 791 switch x := c.x.(type) { 792 case Expr: 793 return x 794 case interface{ expr() Expr }: 795 return x.expr() 796 default: 797 panic("unreachable") 798 } 799} 800