1/* 2Copyright 2017 Google Inc. All rights reserved. 3 4Licensed under the Apache License, Version 2.0 (the "License"); 5you may not use this file except in compliance with the License. 6You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10Unless required by applicable law or agreed to in writing, software 11distributed under the License is distributed on an "AS IS" BASIS, 12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13See the License for the specific language governing permissions and 14limitations under the License. 15*/ 16 17package jsonnet 18 19import ( 20 "errors" 21 "fmt" 22 23 "github.com/google/go-jsonnet/ast" 24) 25 26// value represents a concrete jsonnet value of a specific type. 27// Various operations on values are allowed, depending on their type. 28// All values are of course immutable. 29type value interface { 30 aValue() 31 32 getType() *valueType 33} 34 35type valueType struct { 36 name string 37} 38 39var stringType = &valueType{"string"} 40var numberType = &valueType{"number"} 41var functionType = &valueType{"function"} 42var objectType = &valueType{"object"} 43var booleanType = &valueType{"boolean"} 44var nullType = &valueType{"null"} 45var arrayType = &valueType{"array"} 46 47// potentialValue is something that may be evaluated to a concrete value. 48// The result of the evaluation may *NOT* depend on the current state 49// of the interpreter. The evaluation may fail. 50// 51// It can be used to represent lazy values (e.g. variables values in jsonnet 52// are not calculated before they are used). It is also a useful abstraction 53// in other cases like error handling. 54// 55// It may or may not require arbitrary computation when getValue is called the 56// first time, but any subsequent calls will immediately return. 57// 58// TODO(sbarzowski) perhaps call it just "Thunk"? 59type potentialValue interface { 60 // fromWhere keeps the information from where the evaluation was requested. 61 getValue(i *interpreter, fromWhere traceElement) (value, error) 62 63 aPotentialValue() 64} 65 66// A set of variables with associated thunks. 67type bindingFrame map[ast.Identifier]*cachedThunk 68 69type valueBase struct{} 70 71func (v *valueBase) aValue() {} 72 73// Primitive values 74// ------------------------------------- 75 76type valueString interface { 77 value 78 length() int 79 getRunes() []rune 80 getGoString() string 81 index(i *interpreter, trace traceElement, index int) (value, error) 82} 83 84// valueFlatString represents a string value, internally using a []rune for quick 85// indexing. 86type valueFlatString struct { 87 valueBase 88 // We use rune slices instead of strings for quick indexing 89 value []rune 90} 91 92func (s *valueFlatString) index(i *interpreter, trace traceElement, index int) (value, error) { 93 if 0 <= index && index < s.length() { 94 return makeValueString(string(s.value[index])), nil 95 } 96 return nil, i.Error(fmt.Sprintf("Index %d out of bounds, not within [0, %v)", index, s.length()), trace) 97} 98 99func (s *valueFlatString) getRunes() []rune { 100 return s.value 101} 102 103func (s *valueFlatString) getGoString() string { 104 return string(s.value) 105} 106 107func (s *valueFlatString) length() int { 108 return len(s.value) 109} 110 111func (s *valueFlatString) getType() *valueType { 112 return stringType 113} 114 115// TODO(sbarzowski) this was chosen on a hunch, be more systematic about it 116const extendedStringMinLength = 30 117 118// Indirect representation of long strings. 119// It consists of two parts, left and right, concatenation of which is the whole string. 120type valueStringTree struct { 121 valueBase 122 left, right valueString 123 len int 124} 125 126func buildFullString(s valueString, buf *[]rune) { 127 switch s := s.(type) { 128 case *valueFlatString: 129 *buf = append(*buf, s.value...) 130 case *valueStringTree: 131 buildFullString(s.left, buf) 132 buildFullString(s.right, buf) 133 } 134} 135 136func (s *valueStringTree) flattenToLeft() { 137 if s.right != nil { 138 result := make([]rune, 0, s.len) 139 buildFullString(s, &result) 140 s.left = makeStringFromRunes(result) 141 s.right = nil 142 } 143} 144 145func (s *valueStringTree) index(i *interpreter, trace traceElement, index int) (value, error) { 146 if 0 <= index && index < s.len { 147 s.flattenToLeft() 148 return s.left.index(i, trace, index) 149 } 150 return nil, i.Error(fmt.Sprintf("Index %d out of bounds, not within [0, %v)", index, s.length()), trace) 151} 152 153func (s *valueStringTree) getRunes() []rune { 154 s.flattenToLeft() 155 return s.left.getRunes() 156} 157 158func (s *valueStringTree) getGoString() string { 159 s.flattenToLeft() 160 return s.left.getGoString() 161} 162 163func (s *valueStringTree) length() int { 164 return s.len 165} 166 167func (s *valueStringTree) getType() *valueType { 168 return stringType 169} 170 171func emptyString() *valueFlatString { 172 return &valueFlatString{} 173} 174 175func makeStringFromRunes(runes []rune) *valueFlatString { 176 return &valueFlatString{value: runes} 177} 178 179func concatStrings(a, b valueString) valueString { 180 aLen := a.length() 181 bLen := b.length() 182 if aLen == 0 { 183 return b 184 } else if bLen == 0 { 185 return a 186 } else if aLen+bLen < extendedStringMinLength { 187 runesA := a.getRunes() 188 runesB := b.getRunes() 189 result := make([]rune, 0, aLen+bLen) 190 result = append(result, runesA...) 191 result = append(result, runesB...) 192 return makeStringFromRunes(result) 193 } else { 194 return &valueStringTree{ 195 left: a, 196 right: b, 197 len: aLen + bLen, 198 } 199 } 200} 201 202func stringLessThan(a, b valueString) bool { 203 runesA := a.getRunes() 204 runesB := b.getRunes() 205 var length int 206 if len(runesA) < len(runesB) { 207 length = len(runesA) 208 } else { 209 length = len(runesB) 210 } 211 for i := 0; i < length; i++ { 212 if runesA[i] != runesB[i] { 213 return runesA[i] < runesB[i] 214 } 215 } 216 return len(runesA) < len(runesB) 217} 218 219func stringEqual(a, b valueString) bool { 220 runesA := a.getRunes() 221 runesB := b.getRunes() 222 if len(runesA) != len(runesB) { 223 return false 224 } 225 for i := 0; i < len(runesA); i++ { 226 if runesA[i] != runesB[i] { 227 return false 228 } 229 } 230 return true 231} 232 233func makeValueString(v string) valueString { 234 return &valueFlatString{value: []rune(v)} 235} 236 237type valueBoolean struct { 238 valueBase 239 value bool 240} 241 242func (*valueBoolean) getType() *valueType { 243 return booleanType 244} 245 246func makeValueBoolean(v bool) *valueBoolean { 247 return &valueBoolean{value: v} 248} 249 250func (b *valueBoolean) not() *valueBoolean { 251 return makeValueBoolean(!b.value) 252} 253 254type valueNumber struct { 255 valueBase 256 value float64 257} 258 259func (*valueNumber) getType() *valueType { 260 return numberType 261} 262 263func makeValueNumber(v float64) *valueNumber { 264 return &valueNumber{value: v} 265} 266 267func intToValue(i int) *valueNumber { 268 return makeValueNumber(float64(i)) 269} 270 271func int64ToValue(i int64) *valueNumber { 272 return makeValueNumber(float64(i)) 273} 274 275type valueNull struct { 276 valueBase 277} 278 279var nullValue valueNull 280 281func makeValueNull() *valueNull { 282 return &nullValue 283} 284 285func (*valueNull) getType() *valueType { 286 return nullType 287} 288 289// ast.Array 290// ------------------------------------- 291 292type valueArray struct { 293 valueBase 294 elements []*cachedThunk 295} 296 297func (arr *valueArray) index(i *interpreter, trace traceElement, index int) (value, error) { 298 if 0 <= index && index < arr.length() { 299 return i.evaluatePV(arr.elements[index], trace) 300 } 301 return nil, i.Error(fmt.Sprintf("Index %d out of bounds, not within [0, %v)", index, arr.length()), trace) 302} 303 304func (arr *valueArray) length() int { 305 return len(arr.elements) 306} 307 308func makeValueArray(elements []*cachedThunk) *valueArray { 309 // We don't want to keep a bigger array than necessary 310 // so we create a new one with minimal capacity 311 var arrayElems []*cachedThunk 312 if len(elements) == cap(elements) { 313 arrayElems = elements 314 } else { 315 arrayElems = make([]*cachedThunk, len(elements)) 316 for i := range elements { 317 arrayElems[i] = elements[i] 318 } 319 } 320 return &valueArray{ 321 elements: arrayElems, 322 } 323} 324 325func concatArrays(a, b *valueArray) *valueArray { 326 result := make([]*cachedThunk, 0, len(a.elements)+len(b.elements)) 327 for _, r := range a.elements { 328 result = append(result, r) 329 } 330 for _, r := range b.elements { 331 result = append(result, r) 332 } 333 return &valueArray{elements: result} 334} 335 336func (*valueArray) getType() *valueType { 337 return arrayType 338} 339 340// ast.Function 341// ------------------------------------- 342 343type valueFunction struct { 344 valueBase 345 ec evalCallable 346} 347 348// TODO(sbarzowski) better name? 349type evalCallable interface { 350 evalCall(args callArguments, i *interpreter, trace traceElement) (value, error) 351 Parameters() parameters 352} 353 354func (f *valueFunction) call(i *interpreter, trace traceElement, args callArguments) (value, error) { 355 err := checkArguments(i, trace, args, f.Parameters()) 356 if err != nil { 357 return nil, err 358 } 359 return f.ec.evalCall(args, i, trace) 360} 361 362func (f *valueFunction) Parameters() parameters { 363 return f.ec.Parameters() 364} 365 366func checkArguments(i *interpreter, trace traceElement, args callArguments, params parameters) error { 367 received := make(map[ast.Identifier]bool) 368 accepted := make(map[ast.Identifier]bool) 369 370 numPassed := len(args.positional) 371 numExpected := len(params.required) + len(params.optional) 372 373 if numPassed > numExpected { 374 return i.Error(fmt.Sprintf("function expected %v positional argument(s), but got %v", numExpected, numPassed), trace) 375 } 376 377 for _, param := range params.required { 378 accepted[param] = true 379 } 380 381 for _, param := range params.optional { 382 accepted[param.name] = true 383 } 384 385 for i := range args.positional { 386 if i < len(params.required) { 387 received[params.required[i]] = true 388 } else { 389 received[params.optional[i-len(params.required)].name] = true 390 } 391 } 392 393 for _, arg := range args.named { 394 if _, present := received[arg.name]; present { 395 return i.Error(fmt.Sprintf("Argument %v already provided", arg.name), trace) 396 } 397 if _, present := accepted[arg.name]; !present { 398 return i.Error(fmt.Sprintf("function has no parameter %v", arg.name), trace) 399 } 400 received[arg.name] = true 401 } 402 403 for _, param := range params.required { 404 if _, present := received[param]; !present { 405 return i.Error(fmt.Sprintf("Missing argument: %v", param), trace) 406 } 407 } 408 409 return nil 410} 411 412func (f *valueFunction) getType() *valueType { 413 return functionType 414} 415 416// parameters represents required position and optional named parameters for a 417// function definition. 418type parameters struct { 419 required ast.Identifiers 420 optional []namedParameter 421} 422 423type namedParameter struct { 424 name ast.Identifier 425 defaultArg ast.Node 426} 427 428type potentialValueInEnv interface { 429 inEnv(env *environment) *cachedThunk 430} 431 432type callArguments struct { 433 positional []*cachedThunk 434 named []namedCallArgument 435 tailstrict bool 436} 437 438type namedCallArgument struct { 439 name ast.Identifier 440 pv *cachedThunk 441} 442 443func args(xs ...*cachedThunk) callArguments { 444 return callArguments{positional: xs} 445} 446 447// Objects 448// ------------------------------------- 449 450// Object is a value that allows indexing (taking a value of a field) 451// and combining through mixin inheritence (operator +). 452 453type valueObject struct { 454 valueBase 455 assertionError error 456 cache map[objectCacheKey]value 457 uncached uncachedObject 458} 459 460// Hack - we need to distinguish not-checked-yet and no error situations 461// so we have a special value for no error and nil means that we don't know yet. 462var errNoErrorInObjectInvariants = errors.New("no error - assertions passed") 463 464type objectCacheKey struct { 465 field string 466 depth int 467} 468 469type selfBinding struct { 470 // self is the lexically nearest object we are in, or nil. Note 471 // that this is not the same as context, because we could be inside a function, 472 // inside an object and then context would be the function, but self would still point 473 // to the object. 474 self *valueObject 475 476 // superDepth is the "super" level of self. Sometimes, we look upwards in the 477 // inheritance tree, e.g. via an explicit use of super, or because a given field 478 // has been inherited. When evaluating a field from one of these super objects, 479 // we need to bind self to the concrete object (so self must point 480 // there) but uses of super should be resolved relative to the object whose 481 // field we are evaluating. Thus, we keep a second field for that. This is 482 // usually 0, unless we are evaluating a super object's field. 483 // TODO(sbarzowski) provide some examples 484 // TODO(sbarzowski) provide somewhere a complete explanation of the object model 485 superDepth int 486} 487 488func makeUnboundSelfBinding() selfBinding { 489 return selfBinding{ 490 nil, 491 123456789, // poison value 492 } 493} 494 495func objectBinding(obj *valueObject) selfBinding { 496 return selfBinding{self: obj, superDepth: 0} 497} 498 499func (sb selfBinding) super() selfBinding { 500 return selfBinding{self: sb.self, superDepth: sb.superDepth + 1} 501} 502 503// hidden represents wether to include hidden fields in a lookup. 504type hidden int 505 506// With/without hidden fields 507const ( 508 withHidden hidden = iota 509 withoutHidden 510) 511 512func withHiddenFromBool(with bool) hidden { 513 if with { 514 return withHidden 515 } 516 return withoutHidden 517} 518 519func (*valueObject) getType() *valueType { 520 return objectType 521} 522 523func (obj *valueObject) index(i *interpreter, trace traceElement, field string) (value, error) { 524 return objectIndex(i, trace, objectBinding(obj), field) 525} 526 527func (obj *valueObject) assertionsChecked() bool { 528 // nil - not checked yet 529 // errNoErrorInObjectInvariants - we checked and there is no error (or checking in progress) 530 return obj.assertionError != nil 531} 532 533func (obj *valueObject) setAssertionsCheckResult(err error) { 534 if err != nil { 535 obj.assertionError = err 536 } else { 537 obj.assertionError = errNoErrorInObjectInvariants 538 } 539} 540 541func (obj *valueObject) getAssertionsCheckResult() error { 542 if obj.assertionError == nil { 543 panic("Assertions not checked yet") 544 } 545 if obj.assertionError == errNoErrorInObjectInvariants { 546 return nil 547 } 548 return obj.assertionError 549} 550 551type uncachedObject interface { 552 inheritanceSize() int 553} 554 555type objectLocal struct { 556 name ast.Identifier 557 // Locals may depend on self and super so they are unbound fields and not simply thunks 558 node ast.Node 559} 560 561// simpleObject represents a flat object (no inheritance). 562// Note that it can be used as part of extended objects 563// in inheritance using operator +. 564// 565// Fields are late bound (to object), so they are not values or potentialValues. 566// This is important for inheritance, for example: 567// Let a = {x: 42} and b = {y: self.x}. Evaluating b.y is an error, 568// but (a+b).y evaluates to 42. 569type simpleObject struct { 570 upValues bindingFrame 571 fields simpleObjectFieldMap 572 asserts []unboundField 573 locals []objectLocal 574} 575 576func checkAssertionsHelper(i *interpreter, trace traceElement, obj *valueObject, curr uncachedObject, superDepth int) error { 577 switch curr := curr.(type) { 578 case *extendedObject: 579 err := checkAssertionsHelper(i, trace, obj, curr.right, superDepth) 580 if err != nil { 581 return err 582 } 583 err = checkAssertionsHelper(i, trace, obj, curr.left, superDepth+curr.right.inheritanceSize()) 584 if err != nil { 585 return err 586 } 587 return nil 588 case *simpleObject: 589 for _, assert := range curr.asserts { 590 sb := selfBinding{self: obj, superDepth: superDepth} 591 fieldUpValues := prepareFieldUpvalues(sb, curr.upValues, curr.locals) 592 _, err := assert.evaluate(i, trace, sb, fieldUpValues, "") 593 if err != nil { 594 return err 595 } 596 } 597 return nil 598 case nil: 599 return nil 600 default: 601 panic(fmt.Sprintf("Unknown object type %#v", curr)) 602 } 603} 604 605func checkAssertions(i *interpreter, trace traceElement, obj *valueObject) error { 606 if !obj.assertionsChecked() { 607 // Assertions may refer to the object that will normally 608 // trigger checking of assertions, resulting in an endless recursion. 609 // To avoid that, while we check them, we treat them as already passed. 610 obj.setAssertionsCheckResult(errNoErrorInObjectInvariants) 611 obj.setAssertionsCheckResult(checkAssertionsHelper(i, trace, obj, obj.uncached, 0)) 612 } 613 return obj.getAssertionsCheckResult() 614} 615 616func (*simpleObject) inheritanceSize() int { 617 return 1 618} 619 620func makeValueSimpleObject(b bindingFrame, fields simpleObjectFieldMap, asserts []unboundField, locals []objectLocal) *valueObject { 621 return &valueObject{ 622 cache: make(map[objectCacheKey]value), 623 uncached: &simpleObject{ 624 upValues: b, 625 fields: fields, 626 asserts: asserts, 627 locals: locals, 628 }, 629 } 630} 631 632type simpleObjectFieldMap map[string]simpleObjectField 633 634type simpleObjectField struct { 635 hide ast.ObjectFieldHide 636 field unboundField 637} 638 639// unboundField is a field that doesn't know yet in which object it is. 640type unboundField interface { 641 evaluate(i *interpreter, trace traceElement, sb selfBinding, origBinding bindingFrame, fieldName string) (value, error) 642} 643 644// extendedObject represents an object created through inheritance (left + right). 645// We represent it as the pair of objects. This results in a tree-like structure. 646// Example: 647// (A + B) + C 648// 649// + 650// / \ 651// + C 652// / \ 653// A B 654// 655// It is possible to create an arbitrary binary tree. 656// Note however, that because + is associative the only thing that matters 657// is the order of leafs. 658// 659// This represenation allows us to implement "+" in O(1), 660// but requires going through the tree and trying subsequent leafs for field access. 661// 662type extendedObject struct { 663 left, right uncachedObject 664 totalInheritanceSize int 665} 666 667func (o *extendedObject) inheritanceSize() int { 668 return o.totalInheritanceSize 669} 670 671func makeValueExtendedObject(left, right *valueObject) *valueObject { 672 return &valueObject{ 673 cache: make(map[objectCacheKey]value), 674 uncached: &extendedObject{ 675 left: left.uncached, 676 right: right.uncached, 677 totalInheritanceSize: left.uncached.inheritanceSize() + right.uncached.inheritanceSize(), 678 }, 679 } 680} 681 682// findField returns a field in object curr, with superDepth at least minSuperDepth 683// It also returns an associated bindingFrame and actual superDepth that the field 684// was found at. 685func findField(curr uncachedObject, minSuperDepth int, f string) (bool, simpleObjectField, bindingFrame, []objectLocal, int) { 686 switch curr := curr.(type) { 687 case *extendedObject: 688 if curr.right.inheritanceSize() > minSuperDepth { 689 found, field, frame, locals, counter := findField(curr.right, minSuperDepth, f) 690 if found { 691 return true, field, frame, locals, counter 692 } 693 } 694 found, field, frame, locals, counter := findField(curr.left, minSuperDepth-curr.right.inheritanceSize(), f) 695 return found, field, frame, locals, counter + curr.right.inheritanceSize() 696 697 case *simpleObject: 698 if minSuperDepth <= 0 { 699 if field, ok := curr.fields[f]; ok { 700 return true, field, curr.upValues, curr.locals, 0 701 } 702 } 703 return false, simpleObjectField{}, nil, nil, 0 704 default: 705 panic(fmt.Sprintf("Unknown object type %#v", curr)) 706 } 707} 708 709func prepareFieldUpvalues(sb selfBinding, upValues bindingFrame, locals []objectLocal) bindingFrame { 710 newUpValues := make(bindingFrame) 711 for k, v := range upValues { 712 newUpValues[k] = v 713 } 714 localThunks := make([]*cachedThunk, 0, len(locals)) 715 for _, l := range locals { 716 th := &cachedThunk{ 717 // We will fill upValues later 718 env: &environment{upValues: nil, selfBinding: sb}, 719 body: l.node, 720 } 721 newUpValues[l.name] = th 722 localThunks = append(localThunks, th) 723 } 724 for _, th := range localThunks { 725 th.env.upValues = newUpValues 726 } 727 return newUpValues 728} 729 730func objectIndex(i *interpreter, trace traceElement, sb selfBinding, fieldName string) (value, error) { 731 err := checkAssertions(i, trace, sb.self) 732 if err != nil { 733 return nil, err 734 } 735 if sb.superDepth >= sb.self.uncached.inheritanceSize() { 736 return nil, i.Error("Attempt to use super when there is no super class.", trace) 737 } 738 739 found, field, upValues, locals, foundAt := findField(sb.self.uncached, sb.superDepth, fieldName) 740 if !found { 741 return nil, i.Error(fmt.Sprintf("Field does not exist: %s", fieldName), trace) 742 } 743 744 if val, ok := sb.self.cache[objectCacheKey{field: fieldName, depth: foundAt}]; ok { 745 return val, nil 746 } 747 748 fieldSelfBinding := selfBinding{self: sb.self, superDepth: foundAt} 749 fieldUpValues := prepareFieldUpvalues(fieldSelfBinding, upValues, locals) 750 751 val, err := field.field.evaluate(i, trace, fieldSelfBinding, fieldUpValues, fieldName) 752 753 if err == nil { 754 sb.self.cache[objectCacheKey{field: fieldName, depth: foundAt}] = val 755 } 756 757 return val, err 758} 759 760func objectHasField(sb selfBinding, fieldName string, h hidden) bool { 761 found, field, _, _, _ := findField(sb.self.uncached, sb.superDepth, fieldName) 762 if !found || (h == withoutHidden && field.hide == ast.ObjectFieldHidden) { 763 return false 764 } 765 return true 766} 767 768type fieldHideMap map[string]ast.ObjectFieldHide 769 770func uncachedObjectFieldsVisibility(obj uncachedObject) fieldHideMap { 771 r := make(fieldHideMap) 772 switch obj := obj.(type) { 773 case *extendedObject: 774 r = uncachedObjectFieldsVisibility(obj.left) 775 rightMap := uncachedObjectFieldsVisibility(obj.right) 776 for k, v := range rightMap { 777 if v == ast.ObjectFieldInherit { 778 if _, alreadyExists := r[k]; !alreadyExists { 779 r[k] = v 780 } 781 } else { 782 r[k] = v 783 } 784 } 785 return r 786 787 case *simpleObject: 788 for fieldName, field := range obj.fields { 789 r[fieldName] = field.hide 790 } 791 } 792 return r 793} 794 795func objectFieldsVisibility(obj *valueObject) fieldHideMap { 796 return uncachedObjectFieldsVisibility(obj.uncached) 797} 798 799// Returns field names of an object. Gotcha: the order of fields is unpredictable. 800func objectFields(obj *valueObject, h hidden) []string { 801 var r []string 802 for fieldName, hide := range objectFieldsVisibility(obj) { 803 if h == withHidden || hide != ast.ObjectFieldHidden { 804 r = append(r, fieldName) 805 } 806 } 807 return r 808} 809 810func duplicateFieldNameErrMsg(fieldName string) string { 811 return fmt.Sprintf("Duplicate field name: %s", unparseString(fieldName)) 812} 813