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 = None 136 _ Comparable = Int{} 137 _ Comparable = False 138 _ Comparable = Float(0) 139 _ Comparable = String("") 140 _ Comparable = (*Dict)(nil) 141 _ Comparable = (*List)(nil) 142 _ Comparable = Tuple(nil) 143 _ Comparable = (*Set)(nil) 144) 145 146// A Callable value f may be the operand of a function call, f(x). 147// 148// Clients should use the Call function, never the CallInternal method. 149type Callable interface { 150 Value 151 Name() string 152 CallInternal(thread *Thread, args Tuple, kwargs []Tuple) (Value, error) 153} 154 155type callableWithPosition interface { 156 Callable 157 Position() syntax.Position 158} 159 160var ( 161 _ Callable = (*Builtin)(nil) 162 _ Callable = (*Function)(nil) 163 _ callableWithPosition = (*Function)(nil) 164) 165 166// An Iterable abstracts a sequence of values. 167// An iterable value may be iterated over by a 'for' loop or used where 168// any other Starlark iterable is allowed. Unlike a Sequence, the length 169// of an Iterable is not necessarily known in advance of iteration. 170type Iterable interface { 171 Value 172 Iterate() Iterator // must be followed by call to Iterator.Done 173} 174 175// A Sequence is a sequence of values of known length. 176type Sequence interface { 177 Iterable 178 Len() int 179} 180 181var ( 182 _ Sequence = (*Dict)(nil) 183 _ Sequence = (*Set)(nil) 184) 185 186// An Indexable is a sequence of known length that supports efficient random access. 187// It is not necessarily iterable. 188type Indexable interface { 189 Value 190 Index(i int) Value // requires 0 <= i < Len() 191 Len() int 192} 193 194// A Sliceable is a sequence that can be cut into pieces with the slice operator (x[i:j:step]). 195// 196// All native indexable objects are sliceable. 197// This is a separate interface for backwards-compatibility. 198type Sliceable interface { 199 Indexable 200 // For positive strides (step > 0), 0 <= start <= end <= n. 201 // For negative strides (step < 0), -1 <= end <= start < n. 202 // The caller must ensure that the start and end indices are valid 203 // and that step is non-zero. 204 Slice(start, end, step int) Value 205} 206 207// A HasSetIndex is an Indexable value whose elements may be assigned (x[i] = y). 208// 209// The implementation should not add Len to a negative index as the 210// evaluator does this before the call. 211type HasSetIndex interface { 212 Indexable 213 SetIndex(index int, v Value) error 214} 215 216var ( 217 _ HasSetIndex = (*List)(nil) 218 _ Indexable = Tuple(nil) 219 _ Indexable = String("") 220 _ Sliceable = Tuple(nil) 221 _ Sliceable = String("") 222 _ Sliceable = (*List)(nil) 223) 224 225// An Iterator provides a sequence of values to the caller. 226// 227// The caller must call Done when the iterator is no longer needed. 228// Operations that modify a sequence will fail if it has active iterators. 229// 230// Example usage: 231// 232// iter := iterable.Iterator() 233// defer iter.Done() 234// var x Value 235// for iter.Next(&x) { 236// ... 237// } 238// 239type Iterator interface { 240 // If the iterator is exhausted, Next returns false. 241 // Otherwise it sets *p to the current element of the sequence, 242 // advances the iterator, and returns true. 243 Next(p *Value) bool 244 Done() 245} 246 247// A Mapping is a mapping from keys to values, such as a dictionary. 248// 249// If a type satisfies both Mapping and Iterable, the iterator yields 250// the keys of the mapping. 251type Mapping interface { 252 Value 253 // Get returns the value corresponding to the specified key, 254 // or !found if the mapping does not contain the key. 255 // 256 // Get also defines the behavior of "v in mapping". 257 // The 'in' operator reports the 'found' component, ignoring errors. 258 Get(Value) (v Value, found bool, err error) 259} 260 261// An IterableMapping is a mapping that supports key enumeration. 262type IterableMapping interface { 263 Mapping 264 Iterate() Iterator // see Iterable interface 265 Items() []Tuple // a new slice containing all key/value pairs 266} 267 268var _ IterableMapping = (*Dict)(nil) 269 270// A HasSetKey supports map update using x[k]=v syntax, like a dictionary. 271type HasSetKey interface { 272 Mapping 273 SetKey(k, v Value) error 274} 275 276var _ HasSetKey = (*Dict)(nil) 277 278// A HasBinary value may be used as either operand of these binary operators: 279// + - * / // % in not in | & ^ << >> 280// 281// The Side argument indicates whether the receiver is the left or right operand. 282// 283// An implementation may decline to handle an operation by returning (nil, nil). 284// For this reason, clients should always call the standalone Binary(op, x, y) 285// function rather than calling the method directly. 286type HasBinary interface { 287 Value 288 Binary(op syntax.Token, y Value, side Side) (Value, error) 289} 290 291type Side bool 292 293const ( 294 Left Side = false 295 Right Side = true 296) 297 298// A HasUnary value may be used as the operand of these unary operators: 299// + - ~ 300// 301// An implementation may decline to handle an operation by returning (nil, nil). 302// For this reason, clients should always call the standalone Unary(op, x) 303// function rather than calling the method directly. 304type HasUnary interface { 305 Value 306 Unary(op syntax.Token) (Value, error) 307} 308 309// A HasAttrs value has fields or methods that may be read by a dot expression (y = x.f). 310// Attribute names may be listed using the built-in 'dir' function. 311// 312// For implementation convenience, a result of (nil, nil) from Attr is 313// interpreted as a "no such field or method" error. Implementations are 314// free to return a more precise error. 315type HasAttrs interface { 316 Value 317 Attr(name string) (Value, error) // returns (nil, nil) if attribute not present 318 AttrNames() []string // callers must not modify the result. 319} 320 321var ( 322 _ HasAttrs = String("") 323 _ HasAttrs = new(List) 324 _ HasAttrs = new(Dict) 325 _ HasAttrs = new(Set) 326) 327 328// A HasSetField value has fields that may be written by a dot expression (x.f = y). 329// 330// An implementation of SetField may return a NoSuchAttrError, 331// in which case the runtime may augment the error message to 332// warn of possible misspelling. 333type HasSetField interface { 334 HasAttrs 335 SetField(name string, val Value) error 336} 337 338// A NoSuchAttrError may be returned by an implementation of 339// HasAttrs.Attr or HasSetField.SetField to indicate that no such field 340// exists. In that case the runtime may augment the error message to 341// warn of possible misspelling. 342type NoSuchAttrError string 343 344func (e NoSuchAttrError) Error() string { return string(e) } 345 346// NoneType is the type of None. Its only legal value is None. 347// (We represent it as a number, not struct{}, so that None may be constant.) 348type NoneType byte 349 350const None = NoneType(0) 351 352func (NoneType) String() string { return "None" } 353func (NoneType) Type() string { return "NoneType" } 354func (NoneType) Freeze() {} // immutable 355func (NoneType) Truth() Bool { return False } 356func (NoneType) Hash() (uint32, error) { return 0, nil } 357func (NoneType) CompareSameType(op syntax.Token, y Value, depth int) (bool, error) { 358 return threeway(op, 0), nil 359} 360 361// Bool is the type of a Starlark bool. 362type Bool bool 363 364const ( 365 False Bool = false 366 True Bool = true 367) 368 369func (b Bool) String() string { 370 if b { 371 return "True" 372 } else { 373 return "False" 374 } 375} 376func (b Bool) Type() string { return "bool" } 377func (b Bool) Freeze() {} // immutable 378func (b Bool) Truth() Bool { return b } 379func (b Bool) Hash() (uint32, error) { return uint32(b2i(bool(b))), nil } 380func (x Bool) CompareSameType(op syntax.Token, y_ Value, depth int) (bool, error) { 381 y := y_.(Bool) 382 return threeway(op, b2i(bool(x))-b2i(bool(y))), nil 383} 384 385// Float is the type of a Starlark float. 386type Float float64 387 388func (f Float) String() string { return strconv.FormatFloat(float64(f), 'g', 6, 64) } 389func (f Float) Type() string { return "float" } 390func (f Float) Freeze() {} // immutable 391func (f Float) Truth() Bool { return f != 0.0 } 392func (f Float) Hash() (uint32, error) { 393 // Equal float and int values must yield the same hash. 394 // TODO(adonovan): opt: if f is non-integral, and thus not equal 395 // to any Int, we can avoid the Int conversion and use a cheaper hash. 396 if isFinite(float64(f)) { 397 return finiteFloatToInt(f).Hash() 398 } 399 return 1618033, nil // NaN, +/-Inf 400} 401 402func floor(f Float) Float { return Float(math.Floor(float64(f))) } 403 404// isFinite reports whether f represents a finite rational value. 405// It is equivalent to !math.IsNan(f) && !math.IsInf(f, 0). 406func isFinite(f float64) bool { 407 return math.Abs(f) <= math.MaxFloat64 408} 409 410func (x Float) CompareSameType(op syntax.Token, y_ Value, depth int) (bool, error) { 411 y := y_.(Float) 412 switch op { 413 case syntax.EQL: 414 return x == y, nil 415 case syntax.NEQ: 416 return x != y, nil 417 case syntax.LE: 418 return x <= y, nil 419 case syntax.LT: 420 return x < y, nil 421 case syntax.GE: 422 return x >= y, nil 423 case syntax.GT: 424 return x > y, nil 425 } 426 panic(op) 427} 428 429func (f Float) rational() *big.Rat { return new(big.Rat).SetFloat64(float64(f)) } 430 431// AsFloat returns the float64 value closest to x. 432// The f result is undefined if x is not a float or int. 433func AsFloat(x Value) (f float64, ok bool) { 434 switch x := x.(type) { 435 case Float: 436 return float64(x), true 437 case Int: 438 return float64(x.Float()), true 439 } 440 return 0, false 441} 442 443func (x Float) Mod(y Float) Float { return Float(math.Mod(float64(x), float64(y))) } 444 445// Unary implements the operations +float and -float. 446func (f Float) Unary(op syntax.Token) (Value, error) { 447 switch op { 448 case syntax.MINUS: 449 return -f, nil 450 case syntax.PLUS: 451 return +f, nil 452 } 453 return nil, nil 454} 455 456// String is the type of a Starlark string. 457// 458// A String encapsulates an an immutable sequence of bytes, 459// but strings are not directly iterable. Instead, iterate 460// over the result of calling one of these four methods: 461// codepoints, codepoint_ords, elems, elem_ords. 462// 463// Warning: the contract of the Value interface's String method is that 464// it returns the value printed in Starlark notation, 465// so s.String() or fmt.Sprintf("%s", s) returns a quoted string. 466// Use string(s) or s.GoString() or fmt.Sprintf("%#v", s) to obtain the raw contents 467// of a Starlark string as a Go string. 468type String string 469 470func (s String) String() string { return strconv.Quote(string(s)) } 471func (s String) GoString() string { return string(s) } 472func (s String) Type() string { return "string" } 473func (s String) Freeze() {} // immutable 474func (s String) Truth() Bool { return len(s) > 0 } 475func (s String) Hash() (uint32, error) { return hashString(string(s)), nil } 476func (s String) Len() int { return len(s) } // bytes 477func (s String) Index(i int) Value { return s[i : i+1] } 478 479func (s String) Slice(start, end, step int) Value { 480 if step == 1 { 481 return s[start:end] 482 } 483 484 sign := signum(step) 485 var str []byte 486 for i := start; signum(end-i) == sign; i += step { 487 str = append(str, s[i]) 488 } 489 return String(str) 490} 491 492func (s String) Attr(name string) (Value, error) { return builtinAttr(s, name, stringMethods) } 493func (s String) AttrNames() []string { return builtinAttrNames(stringMethods) } 494 495func (x String) CompareSameType(op syntax.Token, y_ Value, depth int) (bool, error) { 496 y := y_.(String) 497 return threeway(op, strings.Compare(string(x), string(y))), nil 498} 499 500func AsString(x Value) (string, bool) { v, ok := x.(String); return string(v), ok } 501 502// A stringIterable is an iterable whose iterator yields a sequence of 503// either Unicode code points or elements (bytes), 504// either numerically or as successive substrings. 505type stringIterable struct { 506 s String 507 ords bool 508 codepoints bool 509} 510 511var _ Iterable = (*stringIterable)(nil) 512 513func (si stringIterable) String() string { 514 var etype string 515 if si.codepoints { 516 etype = "codepoint" 517 } else { 518 etype = "elem" 519 } 520 if si.ords { 521 return si.s.String() + "." + etype + "_ords()" 522 } else { 523 return si.s.String() + "." + etype + "s()" 524 } 525} 526func (si stringIterable) Type() string { 527 if si.codepoints { 528 return "codepoints" 529 } else { 530 return "elems" 531 } 532} 533func (si stringIterable) Freeze() {} // immutable 534func (si stringIterable) Truth() Bool { return True } 535func (si stringIterable) Hash() (uint32, error) { return 0, fmt.Errorf("unhashable: %s", si.Type()) } 536func (si stringIterable) Iterate() Iterator { return &stringIterator{si, 0} } 537 538type stringIterator struct { 539 si stringIterable 540 i int 541} 542 543func (it *stringIterator) Next(p *Value) bool { 544 s := it.si.s[it.i:] 545 if s == "" { 546 return false 547 } 548 if it.si.codepoints { 549 r, sz := utf8.DecodeRuneInString(string(s)) 550 if !it.si.ords { 551 *p = s[:sz] 552 } else { 553 *p = MakeInt(int(r)) 554 } 555 it.i += sz 556 } else { 557 b := int(s[0]) 558 if !it.si.ords { 559 *p = s[:1] 560 } else { 561 *p = MakeInt(b) 562 } 563 it.i += 1 564 } 565 return true 566} 567 568func (*stringIterator) Done() {} 569 570// A Function is a function defined by a Starlark def statement or lambda expression. 571// The initialization behavior of a Starlark module is also represented by a Function. 572type Function struct { 573 funcode *compile.Funcode 574 module *module 575 defaults Tuple 576 freevars Tuple 577} 578 579// A module is the dynamic counterpart to a Program. 580// All functions in the same program share a module. 581type module struct { 582 program *compile.Program 583 predeclared StringDict 584 globals []Value 585 constants []Value 586} 587 588// makeGlobalDict returns a new, unfrozen StringDict containing all global 589// variables so far defined in the module. 590func (m *module) makeGlobalDict() StringDict { 591 r := make(StringDict, len(m.program.Globals)) 592 for i, id := range m.program.Globals { 593 if v := m.globals[i]; v != nil { 594 r[id.Name] = v 595 } 596 } 597 return r 598} 599 600func (fn *Function) Name() string { return fn.funcode.Name } // "lambda" for anonymous functions 601func (fn *Function) Doc() string { return fn.funcode.Doc } 602func (fn *Function) Hash() (uint32, error) { return hashString(fn.funcode.Name), nil } 603func (fn *Function) Freeze() { fn.defaults.Freeze(); fn.freevars.Freeze() } 604func (fn *Function) String() string { return toString(fn) } 605func (fn *Function) Type() string { return "function" } 606func (fn *Function) Truth() Bool { return true } 607 608// Globals returns a new, unfrozen StringDict containing all global 609// variables so far defined in the function's module. 610func (fn *Function) Globals() StringDict { return fn.module.makeGlobalDict() } 611 612func (fn *Function) Position() syntax.Position { return fn.funcode.Pos } 613func (fn *Function) NumParams() int { return fn.funcode.NumParams } 614func (fn *Function) NumKwonlyParams() int { return fn.funcode.NumKwonlyParams } 615 616// Param returns the name and position of the ith parameter, 617// where 0 <= i < NumParams(). 618// The *args and **kwargs parameters are at the end 619// even if there were optional parameters after *args. 620func (fn *Function) Param(i int) (string, syntax.Position) { 621 if i >= fn.NumParams() { 622 panic(i) 623 } 624 id := fn.funcode.Locals[i] 625 return id.Name, id.Pos 626} 627func (fn *Function) HasVarargs() bool { return fn.funcode.HasVarargs } 628func (fn *Function) HasKwargs() bool { return fn.funcode.HasKwargs } 629 630// A Builtin is a function implemented in Go. 631type Builtin struct { 632 name string 633 fn func(thread *Thread, fn *Builtin, args Tuple, kwargs []Tuple) (Value, error) 634 recv Value // for bound methods (e.g. "".startswith) 635} 636 637func (b *Builtin) Name() string { return b.name } 638func (b *Builtin) Freeze() { 639 if b.recv != nil { 640 b.recv.Freeze() 641 } 642} 643func (b *Builtin) Hash() (uint32, error) { 644 h := hashString(b.name) 645 if b.recv != nil { 646 h ^= 5521 647 } 648 return h, nil 649} 650func (b *Builtin) Receiver() Value { return b.recv } 651func (b *Builtin) String() string { return toString(b) } 652func (b *Builtin) Type() string { return "builtin_function_or_method" } 653func (b *Builtin) CallInternal(thread *Thread, args Tuple, kwargs []Tuple) (Value, error) { 654 return b.fn(thread, b, args, kwargs) 655} 656func (b *Builtin) Truth() Bool { return true } 657 658// NewBuiltin returns a new 'builtin_function_or_method' value with the specified name 659// and implementation. It compares unequal with all other values. 660func NewBuiltin(name string, fn func(thread *Thread, fn *Builtin, args Tuple, kwargs []Tuple) (Value, error)) *Builtin { 661 return &Builtin{name: name, fn: fn} 662} 663 664// BindReceiver returns a new Builtin value representing a method 665// closure, that is, a built-in function bound to a receiver value. 666// 667// In the example below, the value of f is the string.index 668// built-in method bound to the receiver value "abc": 669// 670// f = "abc".index; f("a"); f("b") 671// 672// In the common case, the receiver is bound only during the call, 673// but this still results in the creation of a temporary method closure: 674// 675// "abc".index("a") 676// 677func (b *Builtin) BindReceiver(recv Value) *Builtin { 678 return &Builtin{name: b.name, fn: b.fn, recv: recv} 679} 680 681// A *Dict represents a Starlark dictionary. 682// The zero value of Dict is a valid empty dictionary. 683// If you know the exact final number of entries, 684// it is more efficient to call NewDict. 685type Dict struct { 686 ht hashtable 687} 688 689// NewDict returns a set with initial space for 690// at least size insertions before rehashing. 691func NewDict(size int) *Dict { 692 dict := new(Dict) 693 dict.ht.init(size) 694 return dict 695} 696 697func (d *Dict) Clear() error { return d.ht.clear() } 698func (d *Dict) Delete(k Value) (v Value, found bool, err error) { return d.ht.delete(k) } 699func (d *Dict) Get(k Value) (v Value, found bool, err error) { return d.ht.lookup(k) } 700func (d *Dict) Items() []Tuple { return d.ht.items() } 701func (d *Dict) Keys() []Value { return d.ht.keys() } 702func (d *Dict) Len() int { return int(d.ht.len) } 703func (d *Dict) Iterate() Iterator { return d.ht.iterate() } 704func (d *Dict) SetKey(k, v Value) error { return d.ht.insert(k, v) } 705func (d *Dict) String() string { return toString(d) } 706func (d *Dict) Type() string { return "dict" } 707func (d *Dict) Freeze() { d.ht.freeze() } 708func (d *Dict) Truth() Bool { return d.Len() > 0 } 709func (d *Dict) Hash() (uint32, error) { return 0, fmt.Errorf("unhashable type: dict") } 710 711func (d *Dict) Attr(name string) (Value, error) { return builtinAttr(d, name, dictMethods) } 712func (d *Dict) AttrNames() []string { return builtinAttrNames(dictMethods) } 713 714func (x *Dict) CompareSameType(op syntax.Token, y_ Value, depth int) (bool, error) { 715 y := y_.(*Dict) 716 switch op { 717 case syntax.EQL: 718 ok, err := dictsEqual(x, y, depth) 719 return ok, err 720 case syntax.NEQ: 721 ok, err := dictsEqual(x, y, depth) 722 return !ok, err 723 default: 724 return false, fmt.Errorf("%s %s %s not implemented", x.Type(), op, y.Type()) 725 } 726} 727 728func dictsEqual(x, y *Dict, depth int) (bool, error) { 729 if x.Len() != y.Len() { 730 return false, nil 731 } 732 for _, xitem := range x.Items() { 733 key, xval := xitem[0], xitem[1] 734 735 if yval, found, _ := y.Get(key); !found { 736 return false, nil 737 } else if eq, err := EqualDepth(xval, yval, depth-1); err != nil { 738 return false, err 739 } else if !eq { 740 return false, nil 741 } 742 } 743 return true, nil 744} 745 746// A *List represents a Starlark list value. 747type List struct { 748 elems []Value 749 frozen bool 750 itercount uint32 // number of active iterators (ignored if frozen) 751} 752 753// NewList returns a list containing the specified elements. 754// Callers should not subsequently modify elems. 755func NewList(elems []Value) *List { return &List{elems: elems} } 756 757func (l *List) Freeze() { 758 if !l.frozen { 759 l.frozen = true 760 for _, elem := range l.elems { 761 elem.Freeze() 762 } 763 } 764} 765 766// checkMutable reports an error if the list should not be mutated. 767// verb+" list" should describe the operation. 768func (l *List) checkMutable(verb string) error { 769 if l.frozen { 770 return fmt.Errorf("cannot %s frozen list", verb) 771 } 772 if l.itercount > 0 { 773 return fmt.Errorf("cannot %s list during iteration", verb) 774 } 775 return nil 776} 777 778func (l *List) String() string { return toString(l) } 779func (l *List) Type() string { return "list" } 780func (l *List) Hash() (uint32, error) { return 0, fmt.Errorf("unhashable type: list") } 781func (l *List) Truth() Bool { return l.Len() > 0 } 782func (l *List) Len() int { return len(l.elems) } 783func (l *List) Index(i int) Value { return l.elems[i] } 784 785func (l *List) Slice(start, end, step int) Value { 786 if step == 1 { 787 elems := append([]Value{}, l.elems[start:end]...) 788 return NewList(elems) 789 } 790 791 sign := signum(step) 792 var list []Value 793 for i := start; signum(end-i) == sign; i += step { 794 list = append(list, l.elems[i]) 795 } 796 return NewList(list) 797} 798 799func (l *List) Attr(name string) (Value, error) { return builtinAttr(l, name, listMethods) } 800func (l *List) AttrNames() []string { return builtinAttrNames(listMethods) } 801 802func (l *List) Iterate() Iterator { 803 if !l.frozen { 804 l.itercount++ 805 } 806 return &listIterator{l: l} 807} 808 809func (x *List) CompareSameType(op syntax.Token, y_ Value, depth int) (bool, error) { 810 y := y_.(*List) 811 // It's tempting to check x == y as an optimization here, 812 // but wrong because a list containing NaN is not equal to itself. 813 return sliceCompare(op, x.elems, y.elems, depth) 814} 815 816func sliceCompare(op syntax.Token, x, y []Value, depth int) (bool, error) { 817 // Fast path: check length. 818 if len(x) != len(y) && (op == syntax.EQL || op == syntax.NEQ) { 819 return op == syntax.NEQ, nil 820 } 821 822 // Find first element that is not equal in both lists. 823 for i := 0; i < len(x) && i < len(y); i++ { 824 if eq, err := EqualDepth(x[i], y[i], depth-1); err != nil { 825 return false, err 826 } else if !eq { 827 switch op { 828 case syntax.EQL: 829 return false, nil 830 case syntax.NEQ: 831 return true, nil 832 default: 833 return CompareDepth(op, x[i], y[i], depth-1) 834 } 835 } 836 } 837 838 return threeway(op, len(x)-len(y)), nil 839} 840 841type listIterator struct { 842 l *List 843 i int 844} 845 846func (it *listIterator) Next(p *Value) bool { 847 if it.i < it.l.Len() { 848 *p = it.l.elems[it.i] 849 it.i++ 850 return true 851 } 852 return false 853} 854 855func (it *listIterator) Done() { 856 if !it.l.frozen { 857 it.l.itercount-- 858 } 859} 860 861func (l *List) SetIndex(i int, v Value) error { 862 if err := l.checkMutable("assign to element of"); err != nil { 863 return err 864 } 865 l.elems[i] = v 866 return nil 867} 868 869func (l *List) Append(v Value) error { 870 if err := l.checkMutable("append to"); err != nil { 871 return err 872 } 873 l.elems = append(l.elems, v) 874 return nil 875} 876 877func (l *List) Clear() error { 878 if err := l.checkMutable("clear"); err != nil { 879 return err 880 } 881 for i := range l.elems { 882 l.elems[i] = nil // aid GC 883 } 884 l.elems = l.elems[:0] 885 return nil 886} 887 888// A Tuple represents a Starlark tuple value. 889type Tuple []Value 890 891func (t Tuple) Len() int { return len(t) } 892func (t Tuple) Index(i int) Value { return t[i] } 893 894func (t Tuple) Slice(start, end, step int) Value { 895 if step == 1 { 896 return t[start:end] 897 } 898 899 sign := signum(step) 900 var tuple Tuple 901 for i := start; signum(end-i) == sign; i += step { 902 tuple = append(tuple, t[i]) 903 } 904 return tuple 905} 906 907func (t Tuple) Iterate() Iterator { return &tupleIterator{elems: t} } 908func (t Tuple) Freeze() { 909 for _, elem := range t { 910 elem.Freeze() 911 } 912} 913func (t Tuple) String() string { return toString(t) } 914func (t Tuple) Type() string { return "tuple" } 915func (t Tuple) Truth() Bool { return len(t) > 0 } 916 917func (x Tuple) CompareSameType(op syntax.Token, y_ Value, depth int) (bool, error) { 918 y := y_.(Tuple) 919 return sliceCompare(op, x, y, depth) 920} 921 922func (t Tuple) Hash() (uint32, error) { 923 // Use same algorithm as Python. 924 var x, mult uint32 = 0x345678, 1000003 925 for _, elem := range t { 926 y, err := elem.Hash() 927 if err != nil { 928 return 0, err 929 } 930 x = x ^ y*mult 931 mult += 82520 + uint32(len(t)+len(t)) 932 } 933 return x, nil 934} 935 936type tupleIterator struct{ elems Tuple } 937 938func (it *tupleIterator) Next(p *Value) bool { 939 if len(it.elems) > 0 { 940 *p = it.elems[0] 941 it.elems = it.elems[1:] 942 return true 943 } 944 return false 945} 946 947func (it *tupleIterator) Done() {} 948 949// A Set represents a Starlark set value. 950// The zero value of Set is a valid empty set. 951// If you know the exact final number of elements, 952// it is more efficient to call NewSet. 953type Set struct { 954 ht hashtable // values are all None 955} 956 957// NewSet returns a dictionary with initial space for 958// at least size insertions before rehashing. 959func NewSet(size int) *Set { 960 set := new(Set) 961 set.ht.init(size) 962 return set 963} 964 965func (s *Set) Delete(k Value) (found bool, err error) { _, found, err = s.ht.delete(k); return } 966func (s *Set) Clear() error { return s.ht.clear() } 967func (s *Set) Has(k Value) (found bool, err error) { _, found, err = s.ht.lookup(k); return } 968func (s *Set) Insert(k Value) error { return s.ht.insert(k, None) } 969func (s *Set) Len() int { return int(s.ht.len) } 970func (s *Set) Iterate() Iterator { return s.ht.iterate() } 971func (s *Set) String() string { return toString(s) } 972func (s *Set) Type() string { return "set" } 973func (s *Set) elems() []Value { return s.ht.keys() } 974func (s *Set) Freeze() { s.ht.freeze() } 975func (s *Set) Hash() (uint32, error) { return 0, fmt.Errorf("unhashable type: set") } 976func (s *Set) Truth() Bool { return s.Len() > 0 } 977 978func (s *Set) Attr(name string) (Value, error) { return builtinAttr(s, name, setMethods) } 979func (s *Set) AttrNames() []string { return builtinAttrNames(setMethods) } 980 981func (x *Set) CompareSameType(op syntax.Token, y_ Value, depth int) (bool, error) { 982 y := y_.(*Set) 983 switch op { 984 case syntax.EQL: 985 ok, err := setsEqual(x, y, depth) 986 return ok, err 987 case syntax.NEQ: 988 ok, err := setsEqual(x, y, depth) 989 return !ok, err 990 default: 991 return false, fmt.Errorf("%s %s %s not implemented", x.Type(), op, y.Type()) 992 } 993} 994 995func setsEqual(x, y *Set, depth int) (bool, error) { 996 if x.Len() != y.Len() { 997 return false, nil 998 } 999 for _, elem := range x.elems() { 1000 if found, _ := y.Has(elem); !found { 1001 return false, nil 1002 } 1003 } 1004 return true, nil 1005} 1006 1007func (s *Set) Union(iter Iterator) (Value, error) { 1008 set := new(Set) 1009 for _, elem := range s.elems() { 1010 set.Insert(elem) // can't fail 1011 } 1012 var x Value 1013 for iter.Next(&x) { 1014 if err := set.Insert(x); err != nil { 1015 return nil, err 1016 } 1017 } 1018 return set, nil 1019} 1020 1021// toString returns the string form of value v. 1022// It may be more efficient than v.String() for larger values. 1023func toString(v Value) string { 1024 buf := new(strings.Builder) 1025 writeValue(buf, v, nil) 1026 return buf.String() 1027} 1028 1029// writeValue writes x to out. 1030// 1031// path is used to detect cycles. 1032// It contains the list of *List and *Dict values we're currently printing. 1033// (These are the only potentially cyclic structures.) 1034// Callers should generally pass nil for path. 1035// It is safe to re-use the same path slice for multiple calls. 1036func writeValue(out *strings.Builder, x Value, path []Value) { 1037 switch x := x.(type) { 1038 case nil: 1039 out.WriteString("<nil>") // indicates a bug 1040 1041 case NoneType: 1042 out.WriteString("None") 1043 1044 case Int: 1045 out.WriteString(x.String()) 1046 1047 case Bool: 1048 if x { 1049 out.WriteString("True") 1050 } else { 1051 out.WriteString("False") 1052 } 1053 1054 case String: 1055 fmt.Fprintf(out, "%q", string(x)) 1056 1057 case *List: 1058 out.WriteByte('[') 1059 if pathContains(path, x) { 1060 out.WriteString("...") // list contains itself 1061 } else { 1062 for i, elem := range x.elems { 1063 if i > 0 { 1064 out.WriteString(", ") 1065 } 1066 writeValue(out, elem, append(path, x)) 1067 } 1068 } 1069 out.WriteByte(']') 1070 1071 case Tuple: 1072 out.WriteByte('(') 1073 for i, elem := range x { 1074 if i > 0 { 1075 out.WriteString(", ") 1076 } 1077 writeValue(out, elem, path) 1078 } 1079 if len(x) == 1 { 1080 out.WriteByte(',') 1081 } 1082 out.WriteByte(')') 1083 1084 case *Function: 1085 fmt.Fprintf(out, "<function %s>", x.Name()) 1086 1087 case *Builtin: 1088 if x.recv != nil { 1089 fmt.Fprintf(out, "<built-in method %s of %s value>", x.Name(), x.recv.Type()) 1090 } else { 1091 fmt.Fprintf(out, "<built-in function %s>", x.Name()) 1092 } 1093 1094 case *Dict: 1095 out.WriteByte('{') 1096 if pathContains(path, x) { 1097 out.WriteString("...") // dict contains itself 1098 } else { 1099 sep := "" 1100 for _, item := range x.Items() { 1101 k, v := item[0], item[1] 1102 out.WriteString(sep) 1103 writeValue(out, k, path) 1104 out.WriteString(": ") 1105 writeValue(out, v, append(path, x)) // cycle check 1106 sep = ", " 1107 } 1108 } 1109 out.WriteByte('}') 1110 1111 case *Set: 1112 out.WriteString("set([") 1113 for i, elem := range x.elems() { 1114 if i > 0 { 1115 out.WriteString(", ") 1116 } 1117 writeValue(out, elem, path) 1118 } 1119 out.WriteString("])") 1120 1121 default: 1122 out.WriteString(x.String()) 1123 } 1124} 1125 1126func pathContains(path []Value, x Value) bool { 1127 for _, y := range path { 1128 if x == y { 1129 return true 1130 } 1131 } 1132 return false 1133} 1134 1135const maxdepth = 10 1136 1137// Equal reports whether two Starlark values are equal. 1138func Equal(x, y Value) (bool, error) { 1139 if x, ok := x.(String); ok { 1140 return x == y, nil // fast path for an important special case 1141 } 1142 return EqualDepth(x, y, maxdepth) 1143} 1144 1145// EqualDepth reports whether two Starlark values are equal. 1146// 1147// Recursive comparisons by implementations of Value.CompareSameType 1148// should use EqualDepth to prevent infinite recursion. 1149func EqualDepth(x, y Value, depth int) (bool, error) { 1150 return CompareDepth(syntax.EQL, x, y, depth) 1151} 1152 1153// Compare compares two Starlark values. 1154// The comparison operation must be one of EQL, NEQ, LT, LE, GT, or GE. 1155// Compare returns an error if an ordered comparison was 1156// requested for a type that does not support it. 1157// 1158// Recursive comparisons by implementations of Value.CompareSameType 1159// should use CompareDepth to prevent infinite recursion. 1160func Compare(op syntax.Token, x, y Value) (bool, error) { 1161 return CompareDepth(op, x, y, maxdepth) 1162} 1163 1164// CompareDepth compares two Starlark values. 1165// The comparison operation must be one of EQL, NEQ, LT, LE, GT, or GE. 1166// CompareDepth returns an error if an ordered comparison was 1167// requested for a pair of values that do not support it. 1168// 1169// The depth parameter limits the maximum depth of recursion 1170// in cyclic data structures. 1171func CompareDepth(op syntax.Token, x, y Value, depth int) (bool, error) { 1172 if depth < 1 { 1173 return false, fmt.Errorf("comparison exceeded maximum recursion depth") 1174 } 1175 if sameType(x, y) { 1176 if xcomp, ok := x.(Comparable); ok { 1177 return xcomp.CompareSameType(op, y, depth) 1178 } 1179 1180 // use identity comparison 1181 switch op { 1182 case syntax.EQL: 1183 return x == y, nil 1184 case syntax.NEQ: 1185 return x != y, nil 1186 } 1187 return false, fmt.Errorf("%s %s %s not implemented", x.Type(), op, y.Type()) 1188 } 1189 1190 // different types 1191 1192 // int/float ordered comparisons 1193 switch x := x.(type) { 1194 case Int: 1195 if y, ok := y.(Float); ok { 1196 if y != y { 1197 return false, nil // y is NaN 1198 } 1199 var cmp int 1200 if !math.IsInf(float64(y), 0) { 1201 cmp = x.rational().Cmp(y.rational()) // y is finite 1202 } else if y > 0 { 1203 cmp = -1 // y is +Inf 1204 } else { 1205 cmp = +1 // y is -Inf 1206 } 1207 return threeway(op, cmp), nil 1208 } 1209 case Float: 1210 if y, ok := y.(Int); ok { 1211 if x != x { 1212 return false, nil // x is NaN 1213 } 1214 var cmp int 1215 if !math.IsInf(float64(x), 0) { 1216 cmp = x.rational().Cmp(y.rational()) // x is finite 1217 } else if x > 0 { 1218 cmp = -1 // x is +Inf 1219 } else { 1220 cmp = +1 // x is -Inf 1221 } 1222 return threeway(op, cmp), nil 1223 } 1224 } 1225 1226 // All other values of different types compare unequal. 1227 switch op { 1228 case syntax.EQL: 1229 return false, nil 1230 case syntax.NEQ: 1231 return true, nil 1232 } 1233 return false, fmt.Errorf("%s %s %s not implemented", x.Type(), op, y.Type()) 1234} 1235 1236func sameType(x, y Value) bool { 1237 return reflect.TypeOf(x) == reflect.TypeOf(y) || x.Type() == y.Type() 1238} 1239 1240// threeway interprets a three-way comparison value cmp (-1, 0, +1) 1241// as a boolean comparison (e.g. x < y). 1242func threeway(op syntax.Token, cmp int) bool { 1243 switch op { 1244 case syntax.EQL: 1245 return cmp == 0 1246 case syntax.NEQ: 1247 return cmp != 0 1248 case syntax.LE: 1249 return cmp <= 0 1250 case syntax.LT: 1251 return cmp < 0 1252 case syntax.GE: 1253 return cmp >= 0 1254 case syntax.GT: 1255 return cmp > 0 1256 } 1257 panic(op) 1258} 1259 1260func b2i(b bool) int { 1261 if b { 1262 return 1 1263 } else { 1264 return 0 1265 } 1266} 1267 1268// Len returns the length of a string or sequence value, 1269// and -1 for all others. 1270// 1271// Warning: Len(x) >= 0 does not imply Iterate(x) != nil. 1272// A string has a known length but is not directly iterable. 1273func Len(x Value) int { 1274 switch x := x.(type) { 1275 case String: 1276 return x.Len() 1277 case Sequence: 1278 return x.Len() 1279 } 1280 return -1 1281} 1282 1283// Iterate return a new iterator for the value if iterable, nil otherwise. 1284// If the result is non-nil, the caller must call Done when finished with it. 1285// 1286// Warning: Iterate(x) != nil does not imply Len(x) >= 0. 1287// Some iterables may have unknown length. 1288func Iterate(x Value) Iterator { 1289 if x, ok := x.(Iterable); ok { 1290 return x.Iterate() 1291 } 1292 return nil 1293} 1294