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