1// Copyright 2017 The Bazel Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5// Package starlark provides a Starlark interpreter. 6// 7// Starlark values are represented by the Value interface. 8// The following built-in Value types are known to the evaluator: 9// 10// NoneType -- NoneType 11// Bool -- bool 12// Int -- int 13// Float -- float 14// String -- string 15// *List -- list 16// Tuple -- tuple 17// *Dict -- dict 18// *Set -- set 19// *Function -- function (implemented in Starlark) 20// *Builtin -- builtin_function_or_method (function or method implemented in Go) 21// 22// Client applications may define new data types that satisfy at least 23// the Value interface. Such types may provide additional operations by 24// implementing any of these optional interfaces: 25// 26// Callable -- value is callable like a function 27// Comparable -- value defines its own comparison operations 28// Iterable -- value is iterable using 'for' loops 29// Sequence -- value is iterable sequence of known length 30// Indexable -- value is sequence with efficient random access 31// Mapping -- value maps from keys to values, like a dictionary 32// HasBinary -- value defines binary operations such as * and + 33// HasAttrs -- value has readable fields or methods x.f 34// HasSetField -- value has settable fields x.f 35// HasSetIndex -- value supports element update using x[i]=y 36// HasSetKey -- value supports map update using x[k]=v 37// HasUnary -- value defines unary operations such as + and - 38// 39// Client applications may also define domain-specific functions in Go 40// and make them available to Starlark programs. Use NewBuiltin to 41// construct a built-in value that wraps a Go function. The 42// implementation of the Go function may use UnpackArgs to make sense of 43// the positional and keyword arguments provided by the caller. 44// 45// Starlark's None value is not equal to Go's nil. Go's nil is not a legal 46// Starlark value, but the compiler will not stop you from converting nil 47// to Value. Be careful to avoid allowing Go nil values to leak into 48// Starlark data structures. 49// 50// The Compare operation requires two arguments of the same 51// type, but this constraint cannot be expressed in Go's type system. 52// (This is the classic "binary method problem".) 53// So, each Value type's CompareSameType method is a partial function 54// that compares a value only against others of the same type. 55// Use the package's standalone Compare (or Equal) function to compare 56// an arbitrary pair of values. 57// 58// To parse and evaluate a Starlark source file, use ExecFile. The Eval 59// function evaluates a single expression. All evaluator functions 60// require a Thread parameter which defines the "thread-local storage" 61// of a Starlark thread and may be used to plumb application state 62// through Starlark code and into callbacks. When evaluation fails it 63// returns an EvalError from which the application may obtain a 64// backtrace of active Starlark calls. 65// 66package starlark // import "go.starlark.net/starlark" 67 68// This file defines the data types of Starlark and their basic operations. 69 70import ( 71 "fmt" 72 "math" 73 "math/big" 74 "reflect" 75 "strconv" 76 "strings" 77 "unicode/utf8" 78 79 "go.starlark.net/internal/compile" 80 "go.starlark.net/syntax" 81) 82 83// Value is a value in the Starlark interpreter. 84type Value interface { 85 // String returns the string representation of the value. 86 // Starlark string values are quoted as if by Python's repr. 87 String() string 88 89 // Type returns a short string describing the value's type. 90 Type() string 91 92 // Freeze causes the value, and all values transitively 93 // reachable from it through collections and closures, to be 94 // marked as frozen. All subsequent mutations to the data 95 // structure through this API will fail dynamically, making the 96 // data structure immutable and safe for publishing to other 97 // Starlark interpreters running concurrently. 98 Freeze() 99 100 // Truth returns the truth value of an object. 101 Truth() Bool 102 103 // Hash returns a function of x such that Equals(x, y) => Hash(x) == Hash(y). 104 // Hash may fail if the value's type is not hashable, or if the value 105 // contains a non-hashable value. The hash is used only by dictionaries and 106 // is not exposed to the Starlark program. 107 Hash() (uint32, error) 108} 109 110// A Comparable is a value that defines its own equivalence relation and 111// perhaps ordered comparisons. 112type Comparable interface { 113 Value 114 // CompareSameType compares one value to another of the same Type(). 115 // The comparison operation must be one of EQL, NEQ, LT, LE, GT, or GE. 116 // CompareSameType returns an error if an ordered comparison was 117 // requested for a type that does not support it. 118 // 119 // Implementations that recursively compare subcomponents of 120 // the value should use the CompareDepth function, not Compare, to 121 // avoid infinite recursion on cyclic structures. 122 // 123 // The depth parameter is used to bound comparisons of cyclic 124 // data structures. Implementations should decrement depth 125 // before calling CompareDepth and should return an error if depth 126 // < 1. 127 // 128 // Client code should not call this method. Instead, use the 129 // standalone Compare or Equals functions, which are defined for 130 // all pairs of operands. 131 CompareSameType(op syntax.Token, y Value, depth int) (bool, error) 132} 133 134var ( 135 _ Comparable = Int{} 136 _ Comparable = False 137 _ Comparable = Float(0) 138 _ Comparable = String("") 139 _ Comparable = (*Dict)(nil) 140 _ Comparable = (*List)(nil) 141 _ Comparable = Tuple(nil) 142 _ Comparable = (*Set)(nil) 143) 144 145// A Callable value f may be the operand of a function call, f(x). 146// 147// Clients should use the Call function, never the CallInternal method. 148type Callable interface { 149 Value 150 Name() string 151 CallInternal(thread *Thread, args Tuple, kwargs []Tuple) (Value, error) 152} 153 154type callableWithPosition interface { 155 Callable 156 Position() syntax.Position 157} 158 159var ( 160 _ Callable = (*Builtin)(nil) 161 _ Callable = (*Function)(nil) 162 _ callableWithPosition = (*Function)(nil) 163) 164 165// An Iterable abstracts a sequence of values. 166// An iterable value may be iterated over by a 'for' loop or used where 167// any other Starlark iterable is allowed. Unlike a Sequence, the length 168// of an Iterable is not necessarily known in advance of iteration. 169type Iterable interface { 170 Value 171 Iterate() Iterator // must be followed by call to Iterator.Done 172} 173 174// A Sequence is a sequence of values of known length. 175type Sequence interface { 176 Iterable 177 Len() int 178} 179 180var ( 181 _ Sequence = (*Dict)(nil) 182 _ Sequence = (*Set)(nil) 183) 184 185// An Indexable is a sequence of known length that supports efficient random access. 186// It is not necessarily iterable. 187type Indexable interface { 188 Value 189 Index(i int) Value // requires 0 <= i < Len() 190 Len() int 191} 192 193// A Sliceable is a sequence that can be cut into pieces with the slice operator (x[i:j:step]). 194// 195// All native indexable objects are sliceable. 196// This is a separate interface for backwards-compatibility. 197type Sliceable interface { 198 Indexable 199 // For positive strides (step > 0), 0 <= start <= end <= n. 200 // For negative strides (step < 0), -1 <= end <= start < n. 201 // The caller must ensure that the start and end indices are valid 202 // and that step is non-zero. 203 Slice(start, end, step int) Value 204} 205 206// A HasSetIndex is an Indexable value whose elements may be assigned (x[i] = y). 207// 208// The implementation should not add Len to a negative index as the 209// evaluator does this before the call. 210type HasSetIndex interface { 211 Indexable 212 SetIndex(index int, v Value) error 213} 214 215var ( 216 _ HasSetIndex = (*List)(nil) 217 _ Indexable = Tuple(nil) 218 _ Indexable = String("") 219 _ Sliceable = Tuple(nil) 220 _ Sliceable = String("") 221 _ Sliceable = (*List)(nil) 222) 223 224// An Iterator provides a sequence of values to the caller. 225// 226// The caller must call Done when the iterator is no longer needed. 227// Operations that modify a sequence will fail if it has active iterators. 228// 229// Example usage: 230// 231// iter := iterable.Iterator() 232// defer iter.Done() 233// var x Value 234// for iter.Next(&x) { 235// ... 236// } 237// 238type Iterator interface { 239 // If the iterator is exhausted, Next returns false. 240 // Otherwise it sets *p to the current element of the sequence, 241 // advances the iterator, and returns true. 242 Next(p *Value) bool 243 Done() 244} 245 246// A Mapping is a mapping from keys to values, such as a dictionary. 247// 248// If a type satisfies both Mapping and Iterable, the iterator yields 249// the keys of the mapping. 250type Mapping interface { 251 Value 252 // Get returns the value corresponding to the specified key, 253 // or !found if the mapping does not contain the key. 254 // 255 // Get also defines the behavior of "v in mapping". 256 // The 'in' operator reports the 'found' component, ignoring errors. 257 Get(Value) (v Value, found bool, err error) 258} 259 260// An IterableMapping is a mapping that supports key enumeration. 261type IterableMapping interface { 262 Mapping 263 Iterate() Iterator // see Iterable interface 264 Items() []Tuple // a new slice containing all key/value pairs 265} 266 267var _ IterableMapping = (*Dict)(nil) 268 269// A HasSetKey supports map update using x[k]=v syntax, like a dictionary. 270type HasSetKey interface { 271 Mapping 272 SetKey(k, v Value) error 273} 274 275var _ HasSetKey = (*Dict)(nil) 276 277// A HasBinary value may be used as either operand of these binary operators: 278// + - * / // % in not in | & ^ << >> 279// 280// The Side argument indicates whether the receiver is the left or right operand. 281// 282// An implementation may decline to handle an operation by returning (nil, nil). 283// For this reason, clients should always call the standalone Binary(op, x, y) 284// function rather than calling the method directly. 285type HasBinary interface { 286 Value 287 Binary(op syntax.Token, y Value, side Side) (Value, error) 288} 289 290type Side bool 291 292const ( 293 Left Side = false 294 Right Side = true 295) 296 297// A HasUnary value may be used as the operand of these unary operators: 298// + - ~ 299// 300// An implementation may decline to handle an operation by returning (nil, nil). 301// For this reason, clients should always call the standalone Unary(op, x) 302// function rather than calling the method directly. 303type HasUnary interface { 304 Value 305 Unary(op syntax.Token) (Value, error) 306} 307 308// A HasAttrs value has fields or methods that may be read by a dot expression (y = x.f). 309// Attribute names may be listed using the built-in 'dir' function. 310// 311// For implementation convenience, a result of (nil, nil) from Attr is 312// interpreted as a "no such field or method" error. Implementations are 313// free to return a more precise error. 314type HasAttrs interface { 315 Value 316 Attr(name string) (Value, error) // returns (nil, nil) if attribute not present 317 AttrNames() []string // callers must not modify the result. 318} 319 320var ( 321 _ HasAttrs = String("") 322 _ HasAttrs = new(List) 323 _ HasAttrs = new(Dict) 324 _ HasAttrs = new(Set) 325) 326 327// A HasSetField value has fields that may be written by a dot expression (x.f = y). 328// 329// An implementation of SetField may return a NoSuchAttrError, 330// in which case the runtime may augment the error message to 331// warn of possible misspelling. 332type HasSetField interface { 333 HasAttrs 334 SetField(name string, val Value) error 335} 336 337// A NoSuchAttrError may be returned by an implementation of 338// HasAttrs.Attr or HasSetField.SetField to indicate that no such field 339// exists. In that case the runtime may augment the error message to 340// warn of possible misspelling. 341type NoSuchAttrError string 342 343func (e NoSuchAttrError) Error() string { return string(e) } 344 345// NoneType is the type of None. Its only legal value is None. 346// (We represent it as a number, not struct{}, so that None may be constant.) 347type NoneType byte 348 349const None = NoneType(0) 350 351func (NoneType) String() string { return "None" } 352func (NoneType) Type() string { return "NoneType" } 353func (NoneType) Freeze() {} // immutable 354func (NoneType) Truth() Bool { return False } 355func (NoneType) Hash() (uint32, error) { return 0, nil } 356 357// Bool is the type of a Starlark bool. 358type Bool bool 359 360const ( 361 False Bool = false 362 True Bool = true 363) 364 365func (b Bool) String() string { 366 if b { 367 return "True" 368 } else { 369 return "False" 370 } 371} 372func (b Bool) Type() string { return "bool" } 373func (b Bool) Freeze() {} // immutable 374func (b Bool) Truth() Bool { return b } 375func (b Bool) Hash() (uint32, error) { return uint32(b2i(bool(b))), nil } 376func (x Bool) CompareSameType(op syntax.Token, y_ Value, depth int) (bool, error) { 377 y := y_.(Bool) 378 return threeway(op, b2i(bool(x))-b2i(bool(y))), nil 379} 380 381// Float is the type of a Starlark float. 382type Float float64 383 384func (f Float) String() string { 385 var buf strings.Builder 386 f.format(&buf, 'g') 387 return buf.String() 388} 389 390func (f Float) format(buf *strings.Builder, conv byte) { 391 ff := float64(f) 392 if !isFinite(ff) { 393 if math.IsInf(ff, +1) { 394 buf.WriteString("+inf") 395 } else if math.IsInf(ff, -1) { 396 buf.WriteString("-inf") 397 } else { 398 buf.WriteString("nan") 399 } 400 return 401 } 402 403 // %g is the default format used by str. 404 // It uses the minimum precision to avoid ambiguity, 405 // and always includes a '.' or an 'e' so that the value 406 // is self-evidently a float, not an int. 407 if conv == 'g' || conv == 'G' { 408 s := strconv.FormatFloat(ff, conv, -1, 64) 409 buf.WriteString(s) 410 // Ensure result always has a decimal point if no exponent. 411 // "123" -> "123.0" 412 if strings.IndexByte(s, conv-'g'+'e') < 0 && strings.IndexByte(s, '.') < 0 { 413 buf.WriteString(".0") 414 } 415 return 416 } 417 418 // %[eEfF] use 6-digit precision 419 buf.WriteString(strconv.FormatFloat(ff, conv, 6, 64)) 420} 421 422func (f Float) Type() string { return "float" } 423func (f Float) Freeze() {} // immutable 424func (f Float) Truth() Bool { return f != 0.0 } 425func (f Float) Hash() (uint32, error) { 426 // Equal float and int values must yield the same hash. 427 // TODO(adonovan): opt: if f is non-integral, and thus not equal 428 // to any Int, we can avoid the Int conversion and use a cheaper hash. 429 if isFinite(float64(f)) { 430 return finiteFloatToInt(f).Hash() 431 } 432 return 1618033, nil // NaN, +/-Inf 433} 434 435func floor(f Float) Float { return Float(math.Floor(float64(f))) } 436 437// isFinite reports whether f represents a finite rational value. 438// It is equivalent to !math.IsNan(f) && !math.IsInf(f, 0). 439func isFinite(f float64) bool { 440 return math.Abs(f) <= math.MaxFloat64 441} 442 443func (x Float) CompareSameType(op syntax.Token, y_ Value, depth int) (bool, error) { 444 y := y_.(Float) 445 return threeway(op, floatCmp(x, y)), nil 446} 447 448// floatCmp performs a three-valued comparison on floats, 449// which are totally ordered with NaN > +Inf. 450func floatCmp(x, y Float) int { 451 if x > y { 452 return +1 453 } else if x < y { 454 return -1 455 } else if x == y { 456 return 0 457 } 458 459 // At least one operand is NaN. 460 if x == x { 461 return -1 // y is NaN 462 } else if y == y { 463 return +1 // x is NaN 464 } 465 return 0 // both NaN 466} 467 468func (f Float) rational() *big.Rat { return new(big.Rat).SetFloat64(float64(f)) } 469 470// AsFloat returns the float64 value closest to x. 471// The f result is undefined if x is not a float or Int. 472// The result may be infinite if x is a very large Int. 473func AsFloat(x Value) (f float64, ok bool) { 474 switch x := x.(type) { 475 case Float: 476 return float64(x), true 477 case Int: 478 return float64(x.Float()), true 479 } 480 return 0, false 481} 482 483func (x Float) Mod(y Float) Float { 484 z := Float(math.Mod(float64(x), float64(y))) 485 if (x < 0) != (y < 0) && z != 0 { 486 z += y 487 } 488 return z 489} 490 491// Unary implements the operations +float and -float. 492func (f Float) Unary(op syntax.Token) (Value, error) { 493 switch op { 494 case syntax.MINUS: 495 return -f, nil 496 case syntax.PLUS: 497 return +f, nil 498 } 499 return nil, nil 500} 501 502// String is the type of a Starlark text string. 503// 504// A String encapsulates an an immutable sequence of bytes, 505// but strings are not directly iterable. Instead, iterate 506// over the result of calling one of these four methods: 507// codepoints, codepoint_ords, elems, elem_ords. 508// 509// Strings typically contain text; use Bytes for binary strings. 510// The Starlark spec defines text strings as sequences of UTF-k 511// codes that encode Unicode code points. In this Go implementation, 512// k=8, whereas in a Java implementation, k=16. For portability, 513// operations on strings should aim to avoid assumptions about 514// the value of k. 515// 516// Warning: the contract of the Value interface's String method is that 517// it returns the value printed in Starlark notation, 518// so s.String() or fmt.Sprintf("%s", s) returns a quoted string. 519// Use string(s) or s.GoString() or fmt.Sprintf("%#v", s) to obtain the raw contents 520// of a Starlark string as a Go string. 521type String string 522 523func (s String) String() string { return syntax.Quote(string(s), false) } 524func (s String) GoString() string { return string(s) } 525func (s String) Type() string { return "string" } 526func (s String) Freeze() {} // immutable 527func (s String) Truth() Bool { return len(s) > 0 } 528func (s String) Hash() (uint32, error) { return hashString(string(s)), nil } 529func (s String) Len() int { return len(s) } // bytes 530func (s String) Index(i int) Value { return s[i : i+1] } 531 532func (s String) Slice(start, end, step int) Value { 533 if step == 1 { 534 return s[start:end] 535 } 536 537 sign := signum(step) 538 var str []byte 539 for i := start; signum(end-i) == sign; i += step { 540 str = append(str, s[i]) 541 } 542 return String(str) 543} 544 545func (s String) Attr(name string) (Value, error) { return builtinAttr(s, name, stringMethods) } 546func (s String) AttrNames() []string { return builtinAttrNames(stringMethods) } 547 548func (x String) CompareSameType(op syntax.Token, y_ Value, depth int) (bool, error) { 549 y := y_.(String) 550 return threeway(op, strings.Compare(string(x), string(y))), nil 551} 552 553func AsString(x Value) (string, bool) { v, ok := x.(String); return string(v), ok } 554 555// A stringElems is an iterable whose iterator yields a sequence of 556// elements (bytes), either numerically or as successive substrings. 557// It is an indexable sequence. 558type stringElems struct { 559 s String 560 ords bool 561} 562 563var ( 564 _ Iterable = (*stringElems)(nil) 565 _ Indexable = (*stringElems)(nil) 566) 567 568func (si stringElems) String() string { 569 if si.ords { 570 return si.s.String() + ".elem_ords()" 571 } else { 572 return si.s.String() + ".elems()" 573 } 574} 575func (si stringElems) Type() string { return "string.elems" } 576func (si stringElems) Freeze() {} // immutable 577func (si stringElems) Truth() Bool { return True } 578func (si stringElems) Hash() (uint32, error) { return 0, fmt.Errorf("unhashable: %s", si.Type()) } 579func (si stringElems) Iterate() Iterator { return &stringElemsIterator{si, 0} } 580func (si stringElems) Len() int { return len(si.s) } 581func (si stringElems) Index(i int) Value { 582 if si.ords { 583 return MakeInt(int(si.s[i])) 584 } else { 585 // TODO(adonovan): opt: preallocate canonical 1-byte strings 586 // to avoid interface allocation. 587 return si.s[i : i+1] 588 } 589} 590 591type stringElemsIterator struct { 592 si stringElems 593 i int 594} 595 596func (it *stringElemsIterator) Next(p *Value) bool { 597 if it.i == len(it.si.s) { 598 return false 599 } 600 *p = it.si.Index(it.i) 601 it.i++ 602 return true 603} 604 605func (*stringElemsIterator) Done() {} 606 607// A stringCodepoints is an iterable whose iterator yields a sequence of 608// Unicode code points, either numerically or as successive substrings. 609// It is not indexable. 610type stringCodepoints struct { 611 s String 612 ords bool 613} 614 615var _ Iterable = (*stringCodepoints)(nil) 616 617func (si stringCodepoints) String() string { 618 if si.ords { 619 return si.s.String() + ".codepoint_ords()" 620 } else { 621 return si.s.String() + ".codepoints()" 622 } 623} 624func (si stringCodepoints) Type() string { return "string.codepoints" } 625func (si stringCodepoints) Freeze() {} // immutable 626func (si stringCodepoints) Truth() Bool { return True } 627func (si stringCodepoints) Hash() (uint32, error) { return 0, fmt.Errorf("unhashable: %s", si.Type()) } 628func (si stringCodepoints) Iterate() Iterator { return &stringCodepointsIterator{si, 0} } 629 630type stringCodepointsIterator struct { 631 si stringCodepoints 632 i int 633} 634 635func (it *stringCodepointsIterator) Next(p *Value) bool { 636 s := it.si.s[it.i:] 637 if s == "" { 638 return false 639 } 640 r, sz := utf8.DecodeRuneInString(string(s)) 641 if !it.si.ords { 642 if r == utf8.RuneError { 643 *p = String(r) 644 } else { 645 *p = s[:sz] 646 } 647 } else { 648 *p = MakeInt(int(r)) 649 } 650 it.i += sz 651 return true 652} 653 654func (*stringCodepointsIterator) Done() {} 655 656// A Function is a function defined by a Starlark def statement or lambda expression. 657// The initialization behavior of a Starlark module is also represented by a Function. 658type Function struct { 659 funcode *compile.Funcode 660 module *module 661 defaults Tuple 662 freevars Tuple 663} 664 665// A module is the dynamic counterpart to a Program. 666// All functions in the same program share a module. 667type module struct { 668 program *compile.Program 669 predeclared StringDict 670 globals []Value 671 constants []Value 672} 673 674// makeGlobalDict returns a new, unfrozen StringDict containing all global 675// variables so far defined in the module. 676func (m *module) makeGlobalDict() StringDict { 677 r := make(StringDict, len(m.program.Globals)) 678 for i, id := range m.program.Globals { 679 if v := m.globals[i]; v != nil { 680 r[id.Name] = v 681 } 682 } 683 return r 684} 685 686func (fn *Function) Name() string { return fn.funcode.Name } // "lambda" for anonymous functions 687func (fn *Function) Doc() string { return fn.funcode.Doc } 688func (fn *Function) Hash() (uint32, error) { return hashString(fn.funcode.Name), nil } 689func (fn *Function) Freeze() { fn.defaults.Freeze(); fn.freevars.Freeze() } 690func (fn *Function) String() string { return toString(fn) } 691func (fn *Function) Type() string { return "function" } 692func (fn *Function) Truth() Bool { return true } 693 694// Globals returns a new, unfrozen StringDict containing all global 695// variables so far defined in the function's module. 696func (fn *Function) Globals() StringDict { return fn.module.makeGlobalDict() } 697 698func (fn *Function) Position() syntax.Position { return fn.funcode.Pos } 699func (fn *Function) NumParams() int { return fn.funcode.NumParams } 700func (fn *Function) NumKwonlyParams() int { return fn.funcode.NumKwonlyParams } 701 702// Param returns the name and position of the ith parameter, 703// where 0 <= i < NumParams(). 704// The *args and **kwargs parameters are at the end 705// even if there were optional parameters after *args. 706func (fn *Function) Param(i int) (string, syntax.Position) { 707 if i >= fn.NumParams() { 708 panic(i) 709 } 710 id := fn.funcode.Locals[i] 711 return id.Name, id.Pos 712} 713func (fn *Function) HasVarargs() bool { return fn.funcode.HasVarargs } 714func (fn *Function) HasKwargs() bool { return fn.funcode.HasKwargs } 715 716// A Builtin is a function implemented in Go. 717type Builtin struct { 718 name string 719 fn func(thread *Thread, fn *Builtin, args Tuple, kwargs []Tuple) (Value, error) 720 recv Value // for bound methods (e.g. "".startswith) 721} 722 723func (b *Builtin) Name() string { return b.name } 724func (b *Builtin) Freeze() { 725 if b.recv != nil { 726 b.recv.Freeze() 727 } 728} 729func (b *Builtin) Hash() (uint32, error) { 730 h := hashString(b.name) 731 if b.recv != nil { 732 h ^= 5521 733 } 734 return h, nil 735} 736func (b *Builtin) Receiver() Value { return b.recv } 737func (b *Builtin) String() string { return toString(b) } 738func (b *Builtin) Type() string { return "builtin_function_or_method" } 739func (b *Builtin) CallInternal(thread *Thread, args Tuple, kwargs []Tuple) (Value, error) { 740 return b.fn(thread, b, args, kwargs) 741} 742func (b *Builtin) Truth() Bool { return true } 743 744// NewBuiltin returns a new 'builtin_function_or_method' value with the specified name 745// and implementation. It compares unequal with all other values. 746func NewBuiltin(name string, fn func(thread *Thread, fn *Builtin, args Tuple, kwargs []Tuple) (Value, error)) *Builtin { 747 return &Builtin{name: name, fn: fn} 748} 749 750// BindReceiver returns a new Builtin value representing a method 751// closure, that is, a built-in function bound to a receiver value. 752// 753// In the example below, the value of f is the string.index 754// built-in method bound to the receiver value "abc": 755// 756// f = "abc".index; f("a"); f("b") 757// 758// In the common case, the receiver is bound only during the call, 759// but this still results in the creation of a temporary method closure: 760// 761// "abc".index("a") 762// 763func (b *Builtin) BindReceiver(recv Value) *Builtin { 764 return &Builtin{name: b.name, fn: b.fn, recv: recv} 765} 766 767// A *Dict represents a Starlark dictionary. 768// The zero value of Dict is a valid empty dictionary. 769// If you know the exact final number of entries, 770// it is more efficient to call NewDict. 771type Dict struct { 772 ht hashtable 773} 774 775// NewDict returns a set with initial space for 776// at least size insertions before rehashing. 777func NewDict(size int) *Dict { 778 dict := new(Dict) 779 dict.ht.init(size) 780 return dict 781} 782 783func (d *Dict) Clear() error { return d.ht.clear() } 784func (d *Dict) Delete(k Value) (v Value, found bool, err error) { return d.ht.delete(k) } 785func (d *Dict) Get(k Value) (v Value, found bool, err error) { return d.ht.lookup(k) } 786func (d *Dict) Items() []Tuple { return d.ht.items() } 787func (d *Dict) Keys() []Value { return d.ht.keys() } 788func (d *Dict) Len() int { return int(d.ht.len) } 789func (d *Dict) Iterate() Iterator { return d.ht.iterate() } 790func (d *Dict) SetKey(k, v Value) error { return d.ht.insert(k, v) } 791func (d *Dict) String() string { return toString(d) } 792func (d *Dict) Type() string { return "dict" } 793func (d *Dict) Freeze() { d.ht.freeze() } 794func (d *Dict) Truth() Bool { return d.Len() > 0 } 795func (d *Dict) Hash() (uint32, error) { return 0, fmt.Errorf("unhashable type: dict") } 796 797func (d *Dict) Attr(name string) (Value, error) { return builtinAttr(d, name, dictMethods) } 798func (d *Dict) AttrNames() []string { return builtinAttrNames(dictMethods) } 799 800func (x *Dict) CompareSameType(op syntax.Token, y_ Value, depth int) (bool, error) { 801 y := y_.(*Dict) 802 switch op { 803 case syntax.EQL: 804 ok, err := dictsEqual(x, y, depth) 805 return ok, err 806 case syntax.NEQ: 807 ok, err := dictsEqual(x, y, depth) 808 return !ok, err 809 default: 810 return false, fmt.Errorf("%s %s %s not implemented", x.Type(), op, y.Type()) 811 } 812} 813 814func dictsEqual(x, y *Dict, depth int) (bool, error) { 815 if x.Len() != y.Len() { 816 return false, nil 817 } 818 for _, xitem := range x.Items() { 819 key, xval := xitem[0], xitem[1] 820 821 if yval, found, _ := y.Get(key); !found { 822 return false, nil 823 } else if eq, err := EqualDepth(xval, yval, depth-1); err != nil { 824 return false, err 825 } else if !eq { 826 return false, nil 827 } 828 } 829 return true, nil 830} 831 832// A *List represents a Starlark list value. 833type List struct { 834 elems []Value 835 frozen bool 836 itercount uint32 // number of active iterators (ignored if frozen) 837} 838 839// NewList returns a list containing the specified elements. 840// Callers should not subsequently modify elems. 841func NewList(elems []Value) *List { return &List{elems: elems} } 842 843func (l *List) Freeze() { 844 if !l.frozen { 845 l.frozen = true 846 for _, elem := range l.elems { 847 elem.Freeze() 848 } 849 } 850} 851 852// checkMutable reports an error if the list should not be mutated. 853// verb+" list" should describe the operation. 854func (l *List) checkMutable(verb string) error { 855 if l.frozen { 856 return fmt.Errorf("cannot %s frozen list", verb) 857 } 858 if l.itercount > 0 { 859 return fmt.Errorf("cannot %s list during iteration", verb) 860 } 861 return nil 862} 863 864func (l *List) String() string { return toString(l) } 865func (l *List) Type() string { return "list" } 866func (l *List) Hash() (uint32, error) { return 0, fmt.Errorf("unhashable type: list") } 867func (l *List) Truth() Bool { return l.Len() > 0 } 868func (l *List) Len() int { return len(l.elems) } 869func (l *List) Index(i int) Value { return l.elems[i] } 870 871func (l *List) Slice(start, end, step int) Value { 872 if step == 1 { 873 elems := append([]Value{}, l.elems[start:end]...) 874 return NewList(elems) 875 } 876 877 sign := signum(step) 878 var list []Value 879 for i := start; signum(end-i) == sign; i += step { 880 list = append(list, l.elems[i]) 881 } 882 return NewList(list) 883} 884 885func (l *List) Attr(name string) (Value, error) { return builtinAttr(l, name, listMethods) } 886func (l *List) AttrNames() []string { return builtinAttrNames(listMethods) } 887 888func (l *List) Iterate() Iterator { 889 if !l.frozen { 890 l.itercount++ 891 } 892 return &listIterator{l: l} 893} 894 895func (x *List) CompareSameType(op syntax.Token, y_ Value, depth int) (bool, error) { 896 y := y_.(*List) 897 // It's tempting to check x == y as an optimization here, 898 // but wrong because a list containing NaN is not equal to itself. 899 return sliceCompare(op, x.elems, y.elems, depth) 900} 901 902func sliceCompare(op syntax.Token, x, y []Value, depth int) (bool, error) { 903 // Fast path: check length. 904 if len(x) != len(y) && (op == syntax.EQL || op == syntax.NEQ) { 905 return op == syntax.NEQ, nil 906 } 907 908 // Find first element that is not equal in both lists. 909 for i := 0; i < len(x) && i < len(y); i++ { 910 if eq, err := EqualDepth(x[i], y[i], depth-1); err != nil { 911 return false, err 912 } else if !eq { 913 switch op { 914 case syntax.EQL: 915 return false, nil 916 case syntax.NEQ: 917 return true, nil 918 default: 919 return CompareDepth(op, x[i], y[i], depth-1) 920 } 921 } 922 } 923 924 return threeway(op, len(x)-len(y)), nil 925} 926 927type listIterator struct { 928 l *List 929 i int 930} 931 932func (it *listIterator) Next(p *Value) bool { 933 if it.i < it.l.Len() { 934 *p = it.l.elems[it.i] 935 it.i++ 936 return true 937 } 938 return false 939} 940 941func (it *listIterator) Done() { 942 if !it.l.frozen { 943 it.l.itercount-- 944 } 945} 946 947func (l *List) SetIndex(i int, v Value) error { 948 if err := l.checkMutable("assign to element of"); err != nil { 949 return err 950 } 951 l.elems[i] = v 952 return nil 953} 954 955func (l *List) Append(v Value) error { 956 if err := l.checkMutable("append to"); err != nil { 957 return err 958 } 959 l.elems = append(l.elems, v) 960 return nil 961} 962 963func (l *List) Clear() error { 964 if err := l.checkMutable("clear"); err != nil { 965 return err 966 } 967 for i := range l.elems { 968 l.elems[i] = nil // aid GC 969 } 970 l.elems = l.elems[:0] 971 return nil 972} 973 974// A Tuple represents a Starlark tuple value. 975type Tuple []Value 976 977func (t Tuple) Len() int { return len(t) } 978func (t Tuple) Index(i int) Value { return t[i] } 979 980func (t Tuple) Slice(start, end, step int) Value { 981 if step == 1 { 982 return t[start:end] 983 } 984 985 sign := signum(step) 986 var tuple Tuple 987 for i := start; signum(end-i) == sign; i += step { 988 tuple = append(tuple, t[i]) 989 } 990 return tuple 991} 992 993func (t Tuple) Iterate() Iterator { return &tupleIterator{elems: t} } 994func (t Tuple) Freeze() { 995 for _, elem := range t { 996 elem.Freeze() 997 } 998} 999func (t Tuple) String() string { return toString(t) } 1000func (t Tuple) Type() string { return "tuple" } 1001func (t Tuple) Truth() Bool { return len(t) > 0 } 1002 1003func (x Tuple) CompareSameType(op syntax.Token, y_ Value, depth int) (bool, error) { 1004 y := y_.(Tuple) 1005 return sliceCompare(op, x, y, depth) 1006} 1007 1008func (t Tuple) Hash() (uint32, error) { 1009 // Use same algorithm as Python. 1010 var x, mult uint32 = 0x345678, 1000003 1011 for _, elem := range t { 1012 y, err := elem.Hash() 1013 if err != nil { 1014 return 0, err 1015 } 1016 x = x ^ y*mult 1017 mult += 82520 + uint32(len(t)+len(t)) 1018 } 1019 return x, nil 1020} 1021 1022type tupleIterator struct{ elems Tuple } 1023 1024func (it *tupleIterator) Next(p *Value) bool { 1025 if len(it.elems) > 0 { 1026 *p = it.elems[0] 1027 it.elems = it.elems[1:] 1028 return true 1029 } 1030 return false 1031} 1032 1033func (it *tupleIterator) Done() {} 1034 1035// A Set represents a Starlark set value. 1036// The zero value of Set is a valid empty set. 1037// If you know the exact final number of elements, 1038// it is more efficient to call NewSet. 1039type Set struct { 1040 ht hashtable // values are all None 1041} 1042 1043// NewSet returns a dictionary with initial space for 1044// at least size insertions before rehashing. 1045func NewSet(size int) *Set { 1046 set := new(Set) 1047 set.ht.init(size) 1048 return set 1049} 1050 1051func (s *Set) Delete(k Value) (found bool, err error) { _, found, err = s.ht.delete(k); return } 1052func (s *Set) Clear() error { return s.ht.clear() } 1053func (s *Set) Has(k Value) (found bool, err error) { _, found, err = s.ht.lookup(k); return } 1054func (s *Set) Insert(k Value) error { return s.ht.insert(k, None) } 1055func (s *Set) Len() int { return int(s.ht.len) } 1056func (s *Set) Iterate() Iterator { return s.ht.iterate() } 1057func (s *Set) String() string { return toString(s) } 1058func (s *Set) Type() string { return "set" } 1059func (s *Set) elems() []Value { return s.ht.keys() } 1060func (s *Set) Freeze() { s.ht.freeze() } 1061func (s *Set) Hash() (uint32, error) { return 0, fmt.Errorf("unhashable type: set") } 1062func (s *Set) Truth() Bool { return s.Len() > 0 } 1063 1064func (s *Set) Attr(name string) (Value, error) { return builtinAttr(s, name, setMethods) } 1065func (s *Set) AttrNames() []string { return builtinAttrNames(setMethods) } 1066 1067func (x *Set) CompareSameType(op syntax.Token, y_ Value, depth int) (bool, error) { 1068 y := y_.(*Set) 1069 switch op { 1070 case syntax.EQL: 1071 ok, err := setsEqual(x, y, depth) 1072 return ok, err 1073 case syntax.NEQ: 1074 ok, err := setsEqual(x, y, depth) 1075 return !ok, err 1076 default: 1077 return false, fmt.Errorf("%s %s %s not implemented", x.Type(), op, y.Type()) 1078 } 1079} 1080 1081func setsEqual(x, y *Set, depth int) (bool, error) { 1082 if x.Len() != y.Len() { 1083 return false, nil 1084 } 1085 for _, elem := range x.elems() { 1086 if found, _ := y.Has(elem); !found { 1087 return false, nil 1088 } 1089 } 1090 return true, nil 1091} 1092 1093func (s *Set) Union(iter Iterator) (Value, error) { 1094 set := new(Set) 1095 for _, elem := range s.elems() { 1096 set.Insert(elem) // can't fail 1097 } 1098 var x Value 1099 for iter.Next(&x) { 1100 if err := set.Insert(x); err != nil { 1101 return nil, err 1102 } 1103 } 1104 return set, nil 1105} 1106 1107// toString returns the string form of value v. 1108// It may be more efficient than v.String() for larger values. 1109func toString(v Value) string { 1110 buf := new(strings.Builder) 1111 writeValue(buf, v, nil) 1112 return buf.String() 1113} 1114 1115// writeValue writes x to out. 1116// 1117// path is used to detect cycles. 1118// It contains the list of *List and *Dict values we're currently printing. 1119// (These are the only potentially cyclic structures.) 1120// Callers should generally pass nil for path. 1121// It is safe to re-use the same path slice for multiple calls. 1122func writeValue(out *strings.Builder, x Value, path []Value) { 1123 switch x := x.(type) { 1124 case nil: 1125 out.WriteString("<nil>") // indicates a bug 1126 1127 // These four cases are duplicates of T.String(), for efficiency. 1128 case NoneType: 1129 out.WriteString("None") 1130 1131 case Int: 1132 out.WriteString(x.String()) 1133 1134 case Bool: 1135 if x { 1136 out.WriteString("True") 1137 } else { 1138 out.WriteString("False") 1139 } 1140 1141 case String: 1142 out.WriteString(syntax.Quote(string(x), false)) 1143 1144 case *List: 1145 out.WriteByte('[') 1146 if pathContains(path, x) { 1147 out.WriteString("...") // list contains itself 1148 } else { 1149 for i, elem := range x.elems { 1150 if i > 0 { 1151 out.WriteString(", ") 1152 } 1153 writeValue(out, elem, append(path, x)) 1154 } 1155 } 1156 out.WriteByte(']') 1157 1158 case Tuple: 1159 out.WriteByte('(') 1160 for i, elem := range x { 1161 if i > 0 { 1162 out.WriteString(", ") 1163 } 1164 writeValue(out, elem, path) 1165 } 1166 if len(x) == 1 { 1167 out.WriteByte(',') 1168 } 1169 out.WriteByte(')') 1170 1171 case *Function: 1172 fmt.Fprintf(out, "<function %s>", x.Name()) 1173 1174 case *Builtin: 1175 if x.recv != nil { 1176 fmt.Fprintf(out, "<built-in method %s of %s value>", x.Name(), x.recv.Type()) 1177 } else { 1178 fmt.Fprintf(out, "<built-in function %s>", x.Name()) 1179 } 1180 1181 case *Dict: 1182 out.WriteByte('{') 1183 if pathContains(path, x) { 1184 out.WriteString("...") // dict contains itself 1185 } else { 1186 sep := "" 1187 for _, item := range x.Items() { 1188 k, v := item[0], item[1] 1189 out.WriteString(sep) 1190 writeValue(out, k, path) 1191 out.WriteString(": ") 1192 writeValue(out, v, append(path, x)) // cycle check 1193 sep = ", " 1194 } 1195 } 1196 out.WriteByte('}') 1197 1198 case *Set: 1199 out.WriteString("set([") 1200 for i, elem := range x.elems() { 1201 if i > 0 { 1202 out.WriteString(", ") 1203 } 1204 writeValue(out, elem, path) 1205 } 1206 out.WriteString("])") 1207 1208 default: 1209 out.WriteString(x.String()) 1210 } 1211} 1212 1213func pathContains(path []Value, x Value) bool { 1214 for _, y := range path { 1215 if x == y { 1216 return true 1217 } 1218 } 1219 return false 1220} 1221 1222const maxdepth = 10 1223 1224// Equal reports whether two Starlark values are equal. 1225func Equal(x, y Value) (bool, error) { 1226 if x, ok := x.(String); ok { 1227 return x == y, nil // fast path for an important special case 1228 } 1229 return EqualDepth(x, y, maxdepth) 1230} 1231 1232// EqualDepth reports whether two Starlark values are equal. 1233// 1234// Recursive comparisons by implementations of Value.CompareSameType 1235// should use EqualDepth to prevent infinite recursion. 1236func EqualDepth(x, y Value, depth int) (bool, error) { 1237 return CompareDepth(syntax.EQL, x, y, depth) 1238} 1239 1240// Compare compares two Starlark values. 1241// The comparison operation must be one of EQL, NEQ, LT, LE, GT, or GE. 1242// Compare returns an error if an ordered comparison was 1243// requested for a type that does not support it. 1244// 1245// Recursive comparisons by implementations of Value.CompareSameType 1246// should use CompareDepth to prevent infinite recursion. 1247func Compare(op syntax.Token, x, y Value) (bool, error) { 1248 return CompareDepth(op, x, y, maxdepth) 1249} 1250 1251// CompareDepth compares two Starlark values. 1252// The comparison operation must be one of EQL, NEQ, LT, LE, GT, or GE. 1253// CompareDepth returns an error if an ordered comparison was 1254// requested for a pair of values that do not support it. 1255// 1256// The depth parameter limits the maximum depth of recursion 1257// in cyclic data structures. 1258func CompareDepth(op syntax.Token, x, y Value, depth int) (bool, error) { 1259 if depth < 1 { 1260 return false, fmt.Errorf("comparison exceeded maximum recursion depth") 1261 } 1262 if sameType(x, y) { 1263 if xcomp, ok := x.(Comparable); ok { 1264 return xcomp.CompareSameType(op, y, depth) 1265 } 1266 1267 // use identity comparison 1268 switch op { 1269 case syntax.EQL: 1270 return x == y, nil 1271 case syntax.NEQ: 1272 return x != y, nil 1273 } 1274 return false, fmt.Errorf("%s %s %s not implemented", x.Type(), op, y.Type()) 1275 } 1276 1277 // different types 1278 1279 // int/float ordered comparisons 1280 switch x := x.(type) { 1281 case Int: 1282 if y, ok := y.(Float); ok { 1283 var cmp int 1284 if y != y { 1285 cmp = -1 // y is NaN 1286 } else if !math.IsInf(float64(y), 0) { 1287 cmp = x.rational().Cmp(y.rational()) // y is finite 1288 } else if y > 0 { 1289 cmp = -1 // y is +Inf 1290 } else { 1291 cmp = +1 // y is -Inf 1292 } 1293 return threeway(op, cmp), nil 1294 } 1295 case Float: 1296 if y, ok := y.(Int); ok { 1297 var cmp int 1298 if x != x { 1299 cmp = +1 // x is NaN 1300 } else if !math.IsInf(float64(x), 0) { 1301 cmp = x.rational().Cmp(y.rational()) // x is finite 1302 } else if x > 0 { 1303 cmp = +1 // x is +Inf 1304 } else { 1305 cmp = -1 // x is -Inf 1306 } 1307 return threeway(op, cmp), nil 1308 } 1309 } 1310 1311 // All other values of different types compare unequal. 1312 switch op { 1313 case syntax.EQL: 1314 return false, nil 1315 case syntax.NEQ: 1316 return true, nil 1317 } 1318 return false, fmt.Errorf("%s %s %s not implemented", x.Type(), op, y.Type()) 1319} 1320 1321func sameType(x, y Value) bool { 1322 return reflect.TypeOf(x) == reflect.TypeOf(y) || x.Type() == y.Type() 1323} 1324 1325// threeway interprets a three-way comparison value cmp (-1, 0, +1) 1326// as a boolean comparison (e.g. x < y). 1327func threeway(op syntax.Token, cmp int) bool { 1328 switch op { 1329 case syntax.EQL: 1330 return cmp == 0 1331 case syntax.NEQ: 1332 return cmp != 0 1333 case syntax.LE: 1334 return cmp <= 0 1335 case syntax.LT: 1336 return cmp < 0 1337 case syntax.GE: 1338 return cmp >= 0 1339 case syntax.GT: 1340 return cmp > 0 1341 } 1342 panic(op) 1343} 1344 1345func b2i(b bool) int { 1346 if b { 1347 return 1 1348 } else { 1349 return 0 1350 } 1351} 1352 1353// Len returns the length of a string or sequence value, 1354// and -1 for all others. 1355// 1356// Warning: Len(x) >= 0 does not imply Iterate(x) != nil. 1357// A string has a known length but is not directly iterable. 1358func Len(x Value) int { 1359 switch x := x.(type) { 1360 case String: 1361 return x.Len() 1362 case Indexable: 1363 return x.Len() 1364 case Sequence: 1365 return x.Len() 1366 } 1367 return -1 1368} 1369 1370// Iterate return a new iterator for the value if iterable, nil otherwise. 1371// If the result is non-nil, the caller must call Done when finished with it. 1372// 1373// Warning: Iterate(x) != nil does not imply Len(x) >= 0. 1374// Some iterables may have unknown length. 1375func Iterate(x Value) Iterator { 1376 if x, ok := x.(Iterable); ok { 1377 return x.Iterate() 1378 } 1379 return nil 1380} 1381 1382// Bytes is the type of a Starlark binary string. 1383// 1384// A Bytes encapsulates an immutable sequence of bytes. 1385// It is comparable, indexable, and sliceable, but not direcly iterable; 1386// use bytes.elems() for an iterable view. 1387// 1388// In this Go implementation, the elements of 'string' and 'bytes' are 1389// both bytes, but in other implementations, notably Java, the elements 1390// of a 'string' are UTF-16 codes (Java chars). The spec abstracts text 1391// strings as sequences of UTF-k codes that encode Unicode code points, 1392// and operations that convert from text to binary incur UTF-k-to-UTF-8 1393// transcoding; conversely, conversion from binary to text incurs 1394// UTF-8-to-UTF-k transcoding. Because k=8 for Go, these operations 1395// are the identity function, at least for valid encodings of text. 1396type Bytes string 1397 1398var ( 1399 _ Comparable = Bytes("") 1400 _ Sliceable = Bytes("") 1401 _ Indexable = Bytes("") 1402) 1403 1404func (b Bytes) String() string { return syntax.Quote(string(b), true) } 1405func (b Bytes) Type() string { return "bytes" } 1406func (b Bytes) Freeze() {} // immutable 1407func (b Bytes) Truth() Bool { return len(b) > 0 } 1408func (b Bytes) Hash() (uint32, error) { return String(b).Hash() } 1409func (b Bytes) Len() int { return len(b) } 1410func (b Bytes) Index(i int) Value { return b[i : i+1] } 1411 1412func (b Bytes) Attr(name string) (Value, error) { return builtinAttr(b, name, bytesMethods) } 1413func (b Bytes) AttrNames() []string { return builtinAttrNames(bytesMethods) } 1414 1415func (b Bytes) Slice(start, end, step int) Value { 1416 if step == 1 { 1417 return b[start:end] 1418 } 1419 1420 sign := signum(step) 1421 var str []byte 1422 for i := start; signum(end-i) == sign; i += step { 1423 str = append(str, b[i]) 1424 } 1425 return Bytes(str) 1426} 1427 1428func (x Bytes) CompareSameType(op syntax.Token, y_ Value, depth int) (bool, error) { 1429 y := y_.(Bytes) 1430 return threeway(op, strings.Compare(string(x), string(y))), nil 1431} 1432