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 "log" 20 "os" 21 "reflect" 22 "regexp" 23 24 "github.com/cockroachdb/apd/v2" 25 "golang.org/x/text/encoding/unicode" 26 27 "cuelang.org/go/cue/ast" 28 "cuelang.org/go/cue/errors" 29 "cuelang.org/go/cue/token" 30) 31 32// Debug sets whether extra aggressive checking should be done. 33// This should typically default to true for pre-releases and default to 34// false otherwise. 35var Debug bool = os.Getenv("CUE_DEBUG") != "0" 36 37// Verbosity sets the log level. There are currently only two levels: 38// 0: no logging 39// 1: logging 40var Verbosity int 41 42// Assert panics if the condition is false. Assert can be used to check for 43// conditions that are considers to break an internal variant or unexpected 44// condition, but that nonetheless probably will be handled correctly down the 45// line. For instance, a faulty condition could lead to to error being caught 46// down the road, but resulting in an inaccurate error message. In production 47// code it is better to deal with the bad error message than to panic. 48// 49// It is advisable for each use of Assert to document how the error is expected 50// to be handled down the line. 51func Assertf(b bool, format string, args ...interface{}) { 52 if Debug && !b { 53 panic(fmt.Sprintf("assertion failed: "+format, args...)) 54 } 55} 56 57// Assertf either panics or reports an error to c if the condition is not met. 58func (c *OpContext) Assertf(pos token.Pos, b bool, format string, args ...interface{}) { 59 if !b { 60 if Debug { 61 panic(fmt.Sprintf("assertion failed: "+format, args...)) 62 } 63 c.addErrf(0, pos, format, args...) 64 } 65} 66 67func init() { 68 log.SetFlags(log.Lshortfile) 69} 70 71func Logf(format string, args ...interface{}) { 72 if Verbosity == 0 { 73 return 74 } 75 s := fmt.Sprintf(format, args...) 76 _ = log.Output(2, s) 77} 78 79var pMap = map[*Vertex]int{} 80 81func (c *OpContext) Logf(v *Vertex, format string, args ...interface{}) { 82 if Verbosity == 0 { 83 return 84 } 85 p := pMap[v] 86 if p == 0 { 87 p = len(pMap) + 1 88 pMap[v] = p 89 } 90 a := append([]interface{}{ 91 p, 92 v.Label.SelectorString(c), 93 v.Path(), 94 }, args...) 95 for i := 2; i < len(a); i++ { 96 switch x := a[i].(type) { 97 case Node: 98 a[i] = c.Str(x) 99 case Feature: 100 a[i] = x.SelectorString(c) 101 } 102 } 103 s := fmt.Sprintf(" [%d] %s/%v"+format, a...) 104 _ = log.Output(2, s) 105} 106 107// Runtime defines an interface for low-level representation conversion and 108// lookup. 109type Runtime interface { 110 // StringIndexer allows for converting string labels to and from a 111 // canonical numeric representation. 112 StringIndexer 113 114 // LoadImport loads a unique Vertex associated with a given import path. It 115 // returns an error if no import for this package could be found. 116 LoadImport(importPath string) (*Vertex, errors.Error) 117 118 // StoreType associates a CUE expression with a Go type. 119 StoreType(t reflect.Type, src ast.Expr, expr Expr) 120 121 // LoadType retrieves a previously stored CUE expression for a given Go 122 // type if available. 123 LoadType(t reflect.Type) (src ast.Expr, expr Expr, ok bool) 124} 125 126type Config struct { 127 Runtime 128 Format func(Node) string 129} 130 131// New creates an operation context. 132func New(v *Vertex, cfg *Config) *OpContext { 133 if cfg.Runtime == nil { 134 panic("nil Runtime") 135 } 136 ctx := &OpContext{ 137 Runtime: cfg.Runtime, 138 Format: cfg.Format, 139 vertex: v, 140 } 141 if v != nil { 142 ctx.e = &Environment{Up: nil, Vertex: v} 143 } 144 return ctx 145} 146 147// An OpContext implements CUE's unification operation. It's operations only 148// operation on values that are created with the Runtime with which an OpContext 149// is associated. An OpContext is not goroutine save and only one goroutine may 150// use an OpContext at a time. 151// 152type OpContext struct { 153 Runtime 154 Format func(Node) string 155 156 stats Stats 157 freeListNode *nodeContext 158 159 e *Environment 160 src ast.Node 161 errs *Bottom 162 positions []Node // keep track of error positions 163 164 // vertex is used to determine the path location in case of error. Turning 165 // this into a stack could also allow determining the cyclic path for 166 // structural cycle errors. 167 vertex *Vertex 168 169 nonMonotonicLookupNest int32 170 nonMonotonicRejectNest int32 171 nonMonotonicInsertNest int32 172 nonMonotonicGeneration int32 173 174 // These fields are used associate scratch fields for computing closedness 175 // of a Vertex. These fields could have been included in StructInfo (like 176 // Tomabechi's unification algorithm), but we opted for an indirection to 177 // allow concurrent unification. 178 // 179 // TODO(perf): have two generations: one for each pass of the closedness 180 // algorithm, so that the results of the first pass can be reused for all 181 // features of a node. 182 generation int 183 closed map[*closeInfo]*closeStats 184 todo *closeStats 185 186 // inDisjunct indicates that non-monotonic checks should be skipped. 187 // This is used if we want to do some extra work to eliminate disjunctions 188 // early. The result of unificantion should be thrown away if this check is 189 // used. 190 // 191 // TODO: replace this with a mechanism to determine the correct set (per 192 // conjunct) of StructInfos to include in closedness checking. 193 inDisjunct int 194 195 // inConstaint overrides inDisjunct as field matching should always be 196 // enabled. 197 inConstraint int 198} 199 200func (n *nodeContext) skipNonMonotonicChecks() bool { 201 if n.ctx.inConstraint > 0 { 202 return false 203 } 204 return n.ctx.inDisjunct > 0 205} 206 207// Impl is for internal use only. This will go. 208func (c *OpContext) Impl() Runtime { 209 return c.Runtime 210} 211 212func (c *OpContext) Pos() token.Pos { 213 if c.src == nil { 214 return token.NoPos 215 } 216 return c.src.Pos() 217} 218 219func (c *OpContext) Source() ast.Node { 220 return c.src 221} 222 223// NewContext creates an operation context. 224func NewContext(r Runtime, v *Vertex) *OpContext { 225 return New(v, &Config{Runtime: r}) 226} 227 228func (c *OpContext) pos() token.Pos { 229 if c.src == nil { 230 return token.NoPos 231 } 232 return c.src.Pos() 233} 234 235func (c *OpContext) spawn(node *Vertex) *Environment { 236 node.Parent = c.e.Vertex // TODO: Is this necessary? 237 return &Environment{ 238 Up: c.e, 239 Vertex: node, 240 241 // Copy cycle data. 242 Cyclic: c.e.Cyclic, 243 Deref: c.e.Deref, 244 Cycles: c.e.Cycles, 245 } 246} 247 248func (c *OpContext) Env(upCount int32) *Environment { 249 e := c.e 250 for ; upCount > 0; upCount-- { 251 e = e.Up 252 } 253 return e 254} 255 256func (c *OpContext) relNode(upCount int32) *Vertex { 257 e := c.e 258 for ; upCount > 0; upCount-- { 259 e = e.Up 260 } 261 c.Unify(e.Vertex, Partial) 262 return e.Vertex 263} 264 265func (c *OpContext) relLabel(upCount int32) Feature { 266 // locate current label. 267 e := c.e 268 for ; upCount > 0; upCount-- { 269 e = e.Up 270 } 271 return e.DynamicLabel 272} 273 274func (c *OpContext) concreteIsPossible(op Op, x Expr) bool { 275 if !AssertConcreteIsPossible(op, x) { 276 // No need to take position of expression. 277 c.AddErr(c.NewPosf(token.NoPos, 278 "invalid operand %s ('%s' requires concrete value)", x, op)) 279 return false 280 } 281 return true 282} 283 284// Assert that the given expression can evaluate to a concrete value. 285func AssertConcreteIsPossible(op Op, x Expr) bool { 286 switch v := x.(type) { 287 case *Bottom: 288 case *BoundExpr: 289 return false 290 case Value: 291 return v.Concreteness() == Concrete 292 } 293 return true 294} 295 296// HasErr reports whether any error was reported, including whether value 297// was incomplete. 298func (c *OpContext) HasErr() bool { 299 return c.errs != nil 300} 301 302func (c *OpContext) Err() *Bottom { 303 b := c.errs 304 c.errs = nil 305 return b 306} 307 308func (c *OpContext) addErrf(code ErrorCode, pos token.Pos, msg string, args ...interface{}) { 309 err := c.NewPosf(pos, msg, args...) 310 c.addErr(code, err) 311} 312 313func (c *OpContext) addErr(code ErrorCode, err errors.Error) { 314 c.AddBottom(&Bottom{Code: code, Err: err}) 315} 316 317// AddBottom records an error in OpContext. 318func (c *OpContext) AddBottom(b *Bottom) { 319 c.errs = CombineErrors(c.src, c.errs, b) 320} 321 322// AddErr records an error in OpContext. It returns errors collected so far. 323func (c *OpContext) AddErr(err errors.Error) *Bottom { 324 if err != nil { 325 c.AddBottom(&Bottom{Err: err}) 326 } 327 return c.errs 328} 329 330// NewErrf creates a *Bottom value and returns it. The returned uses the 331// current source as the point of origin of the error. 332func (c *OpContext) NewErrf(format string, args ...interface{}) *Bottom { 333 // TODO: consider renaming ot NewBottomf: this is now confusing as we also 334 // have Newf. 335 err := c.Newf(format, args...) 336 return &Bottom{Src: c.src, Err: err, Code: EvalError} 337} 338 339// AddErrf records an error in OpContext. It returns errors collected so far. 340func (c *OpContext) AddErrf(format string, args ...interface{}) *Bottom { 341 return c.AddErr(c.Newf(format, args...)) 342} 343 344type frame struct { 345 env *Environment 346 err *Bottom 347 src ast.Node 348} 349 350func (c *OpContext) PushState(env *Environment, src ast.Node) (saved frame) { 351 saved.env = c.e 352 saved.err = c.errs 353 saved.src = c.src 354 355 c.errs = nil 356 if src != nil { 357 c.src = src 358 } 359 c.e = env 360 361 return saved 362} 363 364func (c *OpContext) PopState(s frame) *Bottom { 365 err := c.errs 366 c.e = s.env 367 c.errs = s.err 368 c.src = s.src 369 return err 370} 371 372// PushArc signals c that arc v is currently being processed for the purpose 373// of error reporting. PopArc should be called with the returned value once 374// processing of v is completed. 375func (c *OpContext) PushArc(v *Vertex) (saved *Vertex) { 376 c.vertex, saved = v, c.vertex 377 return saved 378} 379 380// PopArc signals completion of processing the current arc. 381func (c *OpContext) PopArc(saved *Vertex) { 382 c.vertex = saved 383} 384 385// Resolve finds a node in the tree. 386// 387// Should only be used to insert Conjuncts. TODO: perhaps only return Conjuncts 388// and error. 389func (c *OpContext) Resolve(env *Environment, r Resolver) (*Vertex, *Bottom) { 390 s := c.PushState(env, r.Source()) 391 392 arc := r.resolve(c, Partial) 393 394 err := c.PopState(s) 395 if err != nil { 396 return nil, err 397 } 398 399 if arc.ChildErrors != nil && arc.ChildErrors.Code == StructuralCycleError { 400 return nil, arc.ChildErrors 401 } 402 403 for { 404 x, ok := arc.BaseValue.(*Vertex) 405 if !ok { 406 break 407 } 408 arc = x 409 } 410 411 return arc, err 412} 413 414// Validate calls validates value for the given validator. 415// 416// TODO(errors): return boolean instead: only the caller has enough information 417// to generate a proper error message. 418func (c *OpContext) Validate(check Validator, value Value) *Bottom { 419 // TODO: use a position stack to push both values. 420 saved := c.src 421 c.src = check.Source() 422 423 err := check.validate(c, value) 424 425 c.src = saved 426 427 return err 428} 429 430// Yield evaluates a Yielder and calls f for each result. 431func (c *OpContext) Yield(env *Environment, y Yielder, f YieldFunc) *Bottom { 432 s := c.PushState(env, y.Source()) 433 434 y.yield(c, f) 435 436 return c.PopState(s) 437 438} 439 440// Concrete returns the concrete value of x after evaluating it. 441// msg is used to mention the context in which an error occurred, if any. 442func (c *OpContext) Concrete(env *Environment, x Expr, msg interface{}) (result Value, complete bool) { 443 444 w, complete := c.Evaluate(env, x) 445 446 w, ok := c.getDefault(w) 447 if !ok { 448 return w, false 449 } 450 v := Unwrap(w) 451 452 if !IsConcrete(v) { 453 complete = false 454 b := c.NewErrf("non-concrete value %v in operand to %s", w, msg) 455 b.Code = IncompleteError 456 v = b 457 } 458 459 if !complete { 460 return v, complete 461 } 462 463 return v, true 464} 465 466// getDefault resolves a disjunction to a single value. If there is no default 467// value, or if there is more than one default value, it reports an "incomplete" 468// error and return false. In all other cases it will return true, even if 469// v is already an error. v may be nil, in which case it will also return nil. 470func (c *OpContext) getDefault(v Value) (result Value, ok bool) { 471 var d *Disjunction 472 switch x := v.(type) { 473 default: 474 return v, true 475 476 case *Vertex: 477 // TODO: return vertex if not disjunction. 478 switch t := x.BaseValue.(type) { 479 case *Disjunction: 480 d = t 481 482 case *Vertex: 483 return c.getDefault(t) 484 485 default: 486 return x, true 487 } 488 489 case *Disjunction: 490 d = x 491 } 492 493 if d.NumDefaults != 1 { 494 c.addErrf(IncompleteError, c.pos(), 495 "unresolved disjunction %s (type %s)", d, d.Kind()) 496 return nil, false 497 } 498 return c.getDefault(d.Values[0]) 499} 500 501// Evaluate evaluates an expression within the given environment and indicates 502// whether the result is complete. It will always return a non-nil result. 503func (c *OpContext) Evaluate(env *Environment, x Expr) (result Value, complete bool) { 504 s := c.PushState(env, x.Source()) 505 506 val := c.evalState(x, Partial) 507 508 complete = true 509 510 if err, _ := val.(*Bottom); err != nil && err.IsIncomplete() { 511 complete = false 512 } 513 if val == nil { 514 complete = false 515 // TODO ENSURE THIS DOESN"T HAPPEN> 516 val = &Bottom{ 517 Code: IncompleteError, 518 Err: c.Newf("UNANTICIPATED ERROR"), 519 } 520 521 } 522 523 _ = c.PopState(s) 524 525 if !complete || val == nil { 526 return val, false 527 } 528 529 return val, true 530} 531 532func (c *OpContext) evaluateRec(env *Environment, x Expr, state VertexStatus) Value { 533 s := c.PushState(env, x.Source()) 534 535 val := c.evalState(x, state) 536 if val == nil { 537 // Be defensive: this never happens, but just in case. 538 Assertf(false, "nil return value: unspecified error") 539 val = &Bottom{ 540 Code: IncompleteError, 541 Err: c.Newf("UNANTICIPATED ERROR"), 542 } 543 } 544 _ = c.PopState(s) 545 546 return val 547} 548 549// value evaluates expression v within the current environment. The result may 550// be nil if the result is incomplete. value leaves errors untouched to that 551// they can be collected by the caller. 552func (c *OpContext) value(x Expr) (result Value) { 553 v := c.evalState(x, Partial) 554 555 v, _ = c.getDefault(v) 556 v = Unwrap(v) 557 return v 558} 559 560func (c *OpContext) evalState(v Expr, state VertexStatus) (result Value) { 561 savedSrc := c.src 562 c.src = v.Source() 563 err := c.errs 564 c.errs = nil 565 566 defer func() { 567 c.errs = CombineErrors(c.src, c.errs, err) 568 569 if v, ok := result.(*Vertex); ok { 570 if b, _ := v.BaseValue.(*Bottom); b != nil { 571 switch b.Code { 572 case IncompleteError: 573 case CycleError: 574 if state == Partial { 575 break 576 } 577 fallthrough 578 default: 579 result = b 580 } 581 } 582 } 583 584 // TODO: remove this when we handle errors more principally. 585 if b, ok := result.(*Bottom); ok { 586 if c.src != nil && 587 b.Code == CycleError && 588 len(errors.Positions(b.Err)) == 0 { 589 bb := *b 590 bb.Err = errors.Wrapf(b.Err, c.src.Pos(), "") 591 result = &bb 592 } 593 if c.errs != result { 594 c.errs = CombineErrors(c.src, c.errs, result) 595 } 596 } 597 if c.errs != nil { 598 result = c.errs 599 } 600 c.src = savedSrc 601 }() 602 603 switch x := v.(type) { 604 case Value: 605 return x 606 607 case Evaluator: 608 v := x.evaluate(c) 609 return v 610 611 case Resolver: 612 arc := x.resolve(c, state) 613 if c.HasErr() { 614 return nil 615 } 616 if arc == nil { 617 return nil 618 } 619 620 v := c.evaluate(arc, state) 621 return v 622 623 default: 624 // This can only happen, really, if v == nil, which is not allowed. 625 panic(fmt.Sprintf("unexpected Expr type %T", v)) 626 } 627} 628 629// unifyNode returns a possibly partially evaluated node value. 630// 631// TODO: maybe return *Vertex, *Bottom 632// 633func (c *OpContext) unifyNode(v Expr, state VertexStatus) (result Value) { 634 savedSrc := c.src 635 c.src = v.Source() 636 err := c.errs 637 c.errs = nil 638 639 defer func() { 640 c.errs = CombineErrors(c.src, c.errs, err) 641 642 if v, ok := result.(*Vertex); ok { 643 if b, _ := v.BaseValue.(*Bottom); b != nil { 644 switch b.Code { 645 case IncompleteError: 646 case CycleError: 647 if state == Partial { 648 break 649 } 650 fallthrough 651 default: 652 result = b 653 } 654 } 655 } 656 657 // TODO: remove this when we handle errors more principally. 658 if b, ok := result.(*Bottom); ok { 659 if c.src != nil && 660 b.Code == CycleError && 661 b.Err.Position() == token.NoPos && 662 len(b.Err.InputPositions()) == 0 { 663 bb := *b 664 bb.Err = errors.Wrapf(b.Err, c.src.Pos(), "") 665 result = &bb 666 } 667 c.errs = CombineErrors(c.src, c.errs, result) 668 } 669 if c.errs != nil { 670 result = c.errs 671 } 672 c.src = savedSrc 673 }() 674 675 switch x := v.(type) { 676 case Value: 677 return x 678 679 case Evaluator: 680 v := x.evaluate(c) 681 return v 682 683 case Resolver: 684 v := x.resolve(c, state) 685 if c.HasErr() { 686 return nil 687 } 688 if v == nil { 689 return nil 690 } 691 692 if v.isUndefined() { 693 // Use node itself to allow for cycle detection. 694 c.Unify(v, AllArcs) 695 } 696 697 return v 698 699 default: 700 // This can only happen, really, if v == nil, which is not allowed. 701 panic(fmt.Sprintf("unexpected Expr type %T", v)) 702 } 703} 704 705func (c *OpContext) lookup(x *Vertex, pos token.Pos, l Feature, state VertexStatus) *Vertex { 706 if l == InvalidLabel || x == nil { 707 // TODO: is it possible to have an invalid label here? Maybe through the 708 // API? 709 return &Vertex{} 710 } 711 712 // var kind Kind 713 // if x.BaseValue != nil { 714 // kind = x.BaseValue.Kind() 715 // } 716 717 switch x.BaseValue.(type) { 718 case *StructMarker: 719 if l.Typ() == IntLabel { 720 c.addErrf(0, pos, "invalid struct selector %s (type int)", l) 721 return nil 722 } 723 724 case *ListMarker: 725 switch { 726 case l.Typ() == IntLabel: 727 switch { 728 case l.Index() < 0: 729 c.addErrf(0, pos, "invalid list index %s (index must be non-negative)", l) 730 return nil 731 case l.Index() > len(x.Arcs): 732 c.addErrf(0, pos, "invalid list index %s (out of bounds)", l) 733 return nil 734 } 735 736 case l.IsDef(), l.IsHidden(): 737 738 default: 739 c.addErrf(0, pos, "invalid list index %s (type string)", l) 740 return nil 741 } 742 743 case nil: 744 // c.addErrf(IncompleteError, pos, "incomplete value %s", x) 745 // return nil 746 747 case *Bottom: 748 749 default: 750 kind := x.BaseValue.Kind() 751 if kind&(ListKind|StructKind) != 0 { 752 // c.addErrf(IncompleteError, pos, 753 // "cannot look up %s in incomplete type %s (type %s)", 754 // l, x.Source(), kind) 755 // return nil 756 } else if !l.IsDef() && !l.IsHidden() { 757 c.addErrf(0, pos, 758 "invalid selector %s for value of type %s", l, kind) 759 return nil 760 } 761 } 762 763 a := x.Lookup(l) 764 765 var hasCycle bool 766outer: 767 switch { 768 case c.nonMonotonicLookupNest == 0 && c.nonMonotonicRejectNest == 0: 769 case a != nil: 770 if state == Partial { 771 a.nonMonotonicLookupGen = c.nonMonotonicGeneration 772 } 773 774 case x.state != nil && state == Partial: 775 for _, e := range x.state.exprs { 776 if isCyclePlaceholder(e.err) { 777 hasCycle = true 778 } 779 } 780 for _, a := range x.state.usedArcs { 781 if a.Label == l { 782 a.nonMonotonicLookupGen = c.nonMonotonicGeneration 783 if c.nonMonotonicRejectNest > 0 { 784 a.nonMonotonicReject = true 785 } 786 break outer 787 } 788 } 789 a := &Vertex{Label: l, nonMonotonicLookupGen: c.nonMonotonicGeneration} 790 if c.nonMonotonicRejectNest > 0 { 791 a.nonMonotonicReject = true 792 } 793 x.state.usedArcs = append(x.state.usedArcs, a) 794 } 795 if a == nil { 796 if x.state != nil { 797 for _, e := range x.state.exprs { 798 if isCyclePlaceholder(e.err) { 799 hasCycle = true 800 } 801 } 802 } 803 code := IncompleteError 804 if !x.Accept(c, l) { 805 code = 0 806 } else if hasCycle { 807 code = CycleError 808 } 809 // TODO: if the struct was a literal struct, we can also treat it as 810 // closed and make this a permanent error. 811 label := l.SelectorString(c.Runtime) 812 813 // TODO(errors): add path reference and make message 814 // "undefined field %s in %s" 815 if l.IsInt() { 816 c.addErrf(code, pos, "index out of range [%d] with length %d", 817 l.Index(), len(x.Elems())) 818 } else { 819 if code != 0 && x.IsOptional(l) { 820 c.addErrf(code, pos, 821 "cannot reference optional field: %s", label) 822 } else { 823 c.addErrf(code, pos, "undefined field: %s", label) 824 } 825 } 826 } 827 return a 828} 829 830func (c *OpContext) Label(src Expr, x Value) Feature { 831 return labelFromValue(c, src, x) 832} 833 834func (c *OpContext) typeError(v Value, k Kind) { 835 if isError(v) { 836 return 837 } 838 if !IsConcrete(v) && v.Kind()&k != 0 { 839 c.addErrf(IncompleteError, pos(v), "incomplete %s: %s", k, v) 840 } else { 841 c.AddErrf("cannot use %s (type %s) as type %s", v, v.Kind(), k) 842 } 843} 844 845func (c *OpContext) typeErrorAs(v Value, k Kind, as interface{}) { 846 if as == nil { 847 c.typeError(v, k) 848 return 849 } 850 if isError(v) { 851 return 852 } 853 if !IsConcrete(v) && v.Kind()&k != 0 { 854 c.addErrf(IncompleteError, pos(v), 855 "incomplete %s in %v: %s", k, as, v) 856 } else { 857 c.AddErrf("cannot use %s (type %s) as type %s in %v", v, v.Kind(), k, as) 858 } 859} 860 861var emptyNode = &Vertex{} 862 863func pos(x Node) token.Pos { 864 if x.Source() == nil { 865 return token.NoPos 866 } 867 return x.Source().Pos() 868} 869 870func (c *OpContext) node(orig Node, x Expr, scalar bool, state VertexStatus) *Vertex { 871 // TODO: always get the vertex. This allows a whole bunch of trickery 872 // down the line. 873 v := c.unifyNode(x, state) 874 875 v, ok := c.getDefault(v) 876 if !ok { 877 // Error already generated by getDefault. 878 return emptyNode 879 } 880 881 // The two if blocks below are rather subtle. If we have an error of 882 // the sentinel value cycle, we have earlier determined that the cycle is 883 // allowed and that it can be ignored here. Any other CycleError is an 884 // annotated cycle error that could be taken as is. 885 // TODO: do something simpler. 886 if scalar { 887 if w := Unwrap(v); !isCyclePlaceholder(w) { 888 v = w 889 } 890 } 891 892 node, ok := v.(*Vertex) 893 if ok && !isCyclePlaceholder(node.BaseValue) { 894 v = node.Value() 895 } 896 897 switch nv := v.(type) { 898 case nil: 899 switch orig.(type) { 900 case *ForClause: 901 c.addErrf(IncompleteError, pos(x), 902 "cannot range over %s (incomplete)", x) 903 default: 904 c.addErrf(IncompleteError, pos(x), 905 "%s undefined (%s is incomplete)", orig, x) 906 } 907 return emptyNode 908 909 case *Bottom: 910 // TODO: this is a bit messy. In some cases errors are already added 911 // and in some cases not. Not a huge deal, as errors will be uniqued 912 // down the line, but could be better. 913 c.AddBottom(nv) 914 return emptyNode 915 916 case *Vertex: 917 if node == nil { 918 panic("unexpected markers with nil node") 919 } 920 921 default: 922 if kind := v.Kind(); kind&StructKind != 0 { 923 switch orig.(type) { 924 case *ForClause: 925 c.addErrf(IncompleteError, pos(x), 926 "cannot range over %s (incomplete type %s)", x, kind) 927 default: 928 c.addErrf(IncompleteError, pos(x), 929 "%s undefined as %s is incomplete (type %s)", orig, x, kind) 930 } 931 return emptyNode 932 933 } else if !ok { 934 c.addErrf(0, pos(x), // TODO(error): better message. 935 "invalid operand %s (found %s, want list or struct)", 936 x.Source(), v.Kind()) 937 return emptyNode 938 } 939 } 940 941 return node 942} 943 944// Elems returns the elements of a list. 945func (c *OpContext) Elems(v Value) []*Vertex { 946 list := c.list(v) 947 return list.Elems() 948} 949 950func (c *OpContext) list(v Value) *Vertex { 951 x, ok := v.(*Vertex) 952 if !ok || !x.IsList() { 953 c.typeError(v, ListKind) 954 return emptyNode 955 } 956 return x 957} 958 959func (c *OpContext) scalar(v Value) Value { 960 v = Unwrap(v) 961 switch v.(type) { 962 case *Null, *Bool, *Num, *String, *Bytes: 963 default: 964 c.typeError(v, ScalarKinds) 965 } 966 return v 967} 968 969var zero = &Num{K: NumKind} 970 971func (c *OpContext) Num(v Value, as interface{}) *Num { 972 v = Unwrap(v) 973 if isError(v) { 974 return zero 975 } 976 x, ok := v.(*Num) 977 if !ok { 978 c.typeErrorAs(v, NumKind, as) 979 return zero 980 } 981 return x 982} 983 984func (c *OpContext) Int64(v Value) int64 { 985 v = Unwrap(v) 986 if isError(v) { 987 return 0 988 } 989 x, ok := v.(*Num) 990 if !ok { 991 c.typeError(v, IntKind) 992 return 0 993 } 994 i, err := x.X.Int64() 995 if err != nil { 996 c.AddErrf("number is not an int64: %v", err) 997 return 0 998 } 999 return i 1000} 1001 1002func (c *OpContext) uint64(v Value, as string) uint64 { 1003 v = Unwrap(v) 1004 if isError(v) { 1005 return 0 1006 } 1007 x, ok := v.(*Num) 1008 if !ok { 1009 c.typeErrorAs(v, IntKind, as) 1010 return 0 1011 } 1012 if x.X.Negative { 1013 // TODO: improve message 1014 c.AddErrf("cannot convert negative number to uint64") 1015 return 0 1016 } 1017 if !x.X.Coeff.IsUint64() { 1018 // TODO: improve message 1019 c.AddErrf("cannot convert number %s to uint64", x.X) 1020 return 0 1021 } 1022 return x.X.Coeff.Uint64() 1023} 1024 1025func (c *OpContext) BoolValue(v Value) bool { 1026 return c.boolValue(v, nil) 1027} 1028 1029func (c *OpContext) boolValue(v Value, as interface{}) bool { 1030 v = Unwrap(v) 1031 if isError(v) { 1032 return false 1033 } 1034 x, ok := v.(*Bool) 1035 if !ok { 1036 c.typeErrorAs(v, BoolKind, as) 1037 return false 1038 } 1039 return x.B 1040} 1041 1042func (c *OpContext) StringValue(v Value) string { 1043 return c.stringValue(v, nil) 1044} 1045 1046// ToBytes returns the bytes value of a scalar value. 1047func (c *OpContext) ToBytes(v Value) []byte { 1048 if x, ok := v.(*Bytes); ok { 1049 return x.B 1050 } 1051 return []byte(c.ToString(v)) 1052} 1053 1054// ToString returns the string value of a scalar value. 1055func (c *OpContext) ToString(v Value) string { 1056 return c.toStringValue(v, StringKind|NumKind|BytesKind|BoolKind, nil) 1057 1058} 1059 1060func (c *OpContext) stringValue(v Value, as interface{}) string { 1061 return c.toStringValue(v, StringKind, as) 1062} 1063 1064func (c *OpContext) toStringValue(v Value, k Kind, as interface{}) string { 1065 v = Unwrap(v) 1066 if isError(v) { 1067 return "" 1068 } 1069 if v.Kind()&k == 0 { 1070 if as == nil { 1071 c.typeError(v, k) 1072 } else { 1073 c.typeErrorAs(v, k, as) 1074 } 1075 return "" 1076 } 1077 switch x := v.(type) { 1078 case *String: 1079 return x.Str 1080 1081 case *Bytes: 1082 return bytesToString(x.B) 1083 1084 case *Num: 1085 return x.X.String() 1086 1087 case *Bool: 1088 if x.B { 1089 return "true" 1090 } 1091 return "false" 1092 1093 default: 1094 c.addErrf(IncompleteError, c.pos(), 1095 "non-concrete value %s (type %s)", v, v.Kind()) 1096 } 1097 return "" 1098} 1099 1100func bytesToString(b []byte) string { 1101 b, _ = unicode.UTF8.NewDecoder().Bytes(b) 1102 return string(b) 1103} 1104 1105func (c *OpContext) bytesValue(v Value, as interface{}) []byte { 1106 v = Unwrap(v) 1107 if isError(v) { 1108 return nil 1109 } 1110 x, ok := v.(*Bytes) 1111 if !ok { 1112 c.typeErrorAs(v, BytesKind, as) 1113 return nil 1114 } 1115 return x.B 1116} 1117 1118var matchNone = regexp.MustCompile("^$") 1119 1120func (c *OpContext) regexp(v Value) *regexp.Regexp { 1121 v = Unwrap(v) 1122 if isError(v) { 1123 return matchNone 1124 } 1125 switch x := v.(type) { 1126 case *String: 1127 if x.RE != nil { 1128 return x.RE 1129 } 1130 // TODO: synchronization 1131 p, err := regexp.Compile(x.Str) 1132 if err != nil { 1133 // FatalError? How to cache error 1134 c.AddErrf("invalid regexp: %s", err) 1135 x.RE = matchNone 1136 } else { 1137 x.RE = p 1138 } 1139 return x.RE 1140 1141 case *Bytes: 1142 if x.RE != nil { 1143 return x.RE 1144 } 1145 // TODO: synchronization 1146 p, err := regexp.Compile(string(x.B)) 1147 if err != nil { 1148 c.AddErrf("invalid regexp: %s", err) 1149 x.RE = matchNone 1150 } else { 1151 x.RE = p 1152 } 1153 return x.RE 1154 1155 default: 1156 c.typeError(v, StringKind|BytesKind) 1157 return matchNone 1158 } 1159} 1160 1161// newNum creates a new number of the given kind. It reports an error value 1162// instead if any error occurred. 1163func (c *OpContext) newNum(d *apd.Decimal, k Kind, sources ...Node) Value { 1164 if c.HasErr() { 1165 return c.Err() 1166 } 1167 return &Num{Src: c.src, X: *d, K: k} 1168} 1169 1170func (c *OpContext) NewInt64(n int64, sources ...Node) Value { 1171 if c.HasErr() { 1172 return c.Err() 1173 } 1174 d := apd.New(n, 0) 1175 return &Num{Src: c.src, X: *d, K: IntKind} 1176} 1177 1178func (c *OpContext) NewString(s string) Value { 1179 if c.HasErr() { 1180 return c.Err() 1181 } 1182 return &String{Src: c.src, Str: s} 1183} 1184 1185func (c *OpContext) newBytes(b []byte) Value { 1186 if c.HasErr() { 1187 return c.Err() 1188 } 1189 return &Bytes{Src: c.src, B: b} 1190} 1191 1192func (c *OpContext) newBool(b bool) Value { 1193 if c.HasErr() { 1194 return c.Err() 1195 } 1196 return &Bool{Src: c.src, B: b} 1197} 1198 1199func (c *OpContext) newList(src ast.Node, parent *Vertex) *Vertex { 1200 return &Vertex{Parent: parent, BaseValue: &ListMarker{}} 1201} 1202 1203// Str reports a debug string of x. 1204func (c *OpContext) Str(x Node) string { 1205 if c.Format == nil { 1206 return fmt.Sprintf("%T", x) 1207 } 1208 return c.Format(x) 1209} 1210 1211// NewList returns a new list for the given values. 1212func (c *OpContext) NewList(values ...Value) *Vertex { 1213 // TODO: consider making this a literal list instead. 1214 list := &ListLit{} 1215 v := &Vertex{ 1216 Conjuncts: []Conjunct{{Env: nil, x: list}}, 1217 } 1218 1219 for _, x := range values { 1220 list.Elems = append(list.Elems, x) 1221 } 1222 c.Unify(v, Finalized) 1223 return v 1224} 1225