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 5package starlark 6 7// This file defines the library of built-ins. 8// 9// Built-ins must explicitly check the "frozen" flag before updating 10// mutable types such as lists and dicts. 11 12import ( 13 "errors" 14 "fmt" 15 "math/big" 16 "os" 17 "sort" 18 "strconv" 19 "strings" 20 "unicode" 21 "unicode/utf16" 22 "unicode/utf8" 23 24 "go.starlark.net/syntax" 25) 26 27// Universe defines the set of universal built-ins, such as None, True, and len. 28// 29// The Go application may add or remove items from the 30// universe dictionary before Starlark evaluation begins. 31// All values in the dictionary must be immutable. 32// Starlark programs cannot modify the dictionary. 33var Universe StringDict 34 35func init() { 36 // https://github.com/google/starlark-go/blob/master/doc/spec.md#built-in-constants-and-functions 37 Universe = StringDict{ 38 "None": None, 39 "True": True, 40 "False": False, 41 "any": NewBuiltin("any", any), 42 "all": NewBuiltin("all", all), 43 "bool": NewBuiltin("bool", bool_), 44 "chr": NewBuiltin("chr", chr), 45 "dict": NewBuiltin("dict", dict), 46 "dir": NewBuiltin("dir", dir), 47 "enumerate": NewBuiltin("enumerate", enumerate), 48 "fail": NewBuiltin("fail", fail), 49 "float": NewBuiltin("float", float), // requires resolve.AllowFloat 50 "getattr": NewBuiltin("getattr", getattr), 51 "hasattr": NewBuiltin("hasattr", hasattr), 52 "hash": NewBuiltin("hash", hash), 53 "int": NewBuiltin("int", int_), 54 "len": NewBuiltin("len", len_), 55 "list": NewBuiltin("list", list), 56 "max": NewBuiltin("max", minmax), 57 "min": NewBuiltin("min", minmax), 58 "ord": NewBuiltin("ord", ord), 59 "print": NewBuiltin("print", print), 60 "range": NewBuiltin("range", range_), 61 "repr": NewBuiltin("repr", repr), 62 "reversed": NewBuiltin("reversed", reversed), 63 "set": NewBuiltin("set", set), // requires resolve.AllowSet 64 "sorted": NewBuiltin("sorted", sorted), 65 "str": NewBuiltin("str", str), 66 "tuple": NewBuiltin("tuple", tuple), 67 "type": NewBuiltin("type", type_), 68 "zip": NewBuiltin("zip", zip), 69 } 70} 71 72type builtinMethod func(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) 73 74// methods of built-in types 75// https://github.com/google/starlark-go/blob/master/doc/spec.md#built-in-methods 76var ( 77 dictMethods = map[string]builtinMethod{ 78 "clear": dict_clear, 79 "get": dict_get, 80 "items": dict_items, 81 "keys": dict_keys, 82 "pop": dict_pop, 83 "popitem": dict_popitem, 84 "setdefault": dict_setdefault, 85 "update": dict_update, 86 "values": dict_values, 87 } 88 89 listMethods = map[string]builtinMethod{ 90 "append": list_append, 91 "clear": list_clear, 92 "extend": list_extend, 93 "index": list_index, 94 "insert": list_insert, 95 "pop": list_pop, 96 "remove": list_remove, 97 } 98 99 stringMethods = map[string]builtinMethod{ 100 "capitalize": string_capitalize, 101 "codepoint_ords": string_iterable, 102 "codepoints": string_iterable, // sic 103 "count": string_count, 104 "elem_ords": string_iterable, 105 "elems": string_iterable, // sic 106 "endswith": string_startswith, // sic 107 "find": string_find, 108 "format": string_format, 109 "index": string_index, 110 "isalnum": string_isalnum, 111 "isalpha": string_isalpha, 112 "isdigit": string_isdigit, 113 "islower": string_islower, 114 "isspace": string_isspace, 115 "istitle": string_istitle, 116 "isupper": string_isupper, 117 "join": string_join, 118 "lower": string_lower, 119 "lstrip": string_strip, // sic 120 "partition": string_partition, 121 "replace": string_replace, 122 "rfind": string_rfind, 123 "rindex": string_rindex, 124 "rpartition": string_partition, // sic 125 "rsplit": string_split, // sic 126 "rstrip": string_strip, // sic 127 "split": string_split, 128 "splitlines": string_splitlines, 129 "startswith": string_startswith, 130 "strip": string_strip, 131 "title": string_title, 132 "upper": string_upper, 133 } 134 135 setMethods = map[string]builtinMethod{ 136 "union": set_union, 137 } 138) 139 140func builtinAttr(recv Value, name string, methods map[string]builtinMethod) (Value, error) { 141 method := methods[name] 142 if method == nil { 143 return nil, nil // no such method 144 } 145 146 // Allocate a closure over 'method'. 147 impl := func(thread *Thread, b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 148 return method(b, args, kwargs) 149 } 150 return NewBuiltin(name, impl).BindReceiver(recv), nil 151} 152 153func builtinAttrNames(methods map[string]builtinMethod) []string { 154 names := make([]string, 0, len(methods)) 155 for name := range methods { 156 names = append(names, name) 157 } 158 sort.Strings(names) 159 return names 160} 161 162// ---- built-in functions ---- 163 164// https://github.com/google/starlark-go/blob/master/doc/spec.md#all 165func all(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 166 var iterable Iterable 167 if err := UnpackPositionalArgs("all", args, kwargs, 1, &iterable); err != nil { 168 return nil, err 169 } 170 iter := iterable.Iterate() 171 defer iter.Done() 172 var x Value 173 for iter.Next(&x) { 174 if !x.Truth() { 175 return False, nil 176 } 177 } 178 return True, nil 179} 180 181// https://github.com/google/starlark-go/blob/master/doc/spec.md#any 182func any(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 183 var iterable Iterable 184 if err := UnpackPositionalArgs("any", args, kwargs, 1, &iterable); err != nil { 185 return nil, err 186 } 187 iter := iterable.Iterate() 188 defer iter.Done() 189 var x Value 190 for iter.Next(&x) { 191 if x.Truth() { 192 return True, nil 193 } 194 } 195 return False, nil 196} 197 198// https://github.com/google/starlark-go/blob/master/doc/spec.md#bool 199func bool_(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 200 var x Value = False 201 if err := UnpackPositionalArgs("bool", args, kwargs, 0, &x); err != nil { 202 return nil, err 203 } 204 return x.Truth(), nil 205} 206 207// https://github.com/google/starlark-go/blob/master/doc/spec.md#chr 208func chr(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 209 if len(kwargs) > 0 { 210 return nil, fmt.Errorf("chr does not accept keyword arguments") 211 } 212 if len(args) != 1 { 213 return nil, fmt.Errorf("chr: got %d arguments, want 1", len(args)) 214 } 215 i, err := AsInt32(args[0]) 216 if err != nil { 217 return nil, fmt.Errorf("chr: got %s, want int", args[0].Type()) 218 } 219 if i < 0 { 220 return nil, fmt.Errorf("chr: Unicode code point %d out of range (<0)", i) 221 } 222 if i > unicode.MaxRune { 223 return nil, fmt.Errorf("chr: Unicode code point U+%X out of range (>0x10FFFF)", i) 224 } 225 return String(string(i)), nil 226} 227 228// https://github.com/google/starlark-go/blob/master/doc/spec.md#dict 229func dict(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 230 if len(args) > 1 { 231 return nil, fmt.Errorf("dict: got %d arguments, want at most 1", len(args)) 232 } 233 dict := new(Dict) 234 if err := updateDict(dict, args, kwargs); err != nil { 235 return nil, fmt.Errorf("dict: %v", err) 236 } 237 return dict, nil 238} 239 240// https://github.com/google/starlark-go/blob/master/doc/spec.md#dir 241func dir(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 242 if len(kwargs) > 0 { 243 return nil, fmt.Errorf("dir does not accept keyword arguments") 244 } 245 if len(args) != 1 { 246 return nil, fmt.Errorf("dir: got %d arguments, want 1", len(args)) 247 } 248 249 var names []string 250 if x, ok := args[0].(HasAttrs); ok { 251 names = x.AttrNames() 252 } 253 sort.Strings(names) 254 elems := make([]Value, len(names)) 255 for i, name := range names { 256 elems[i] = String(name) 257 } 258 return NewList(elems), nil 259} 260 261// https://github.com/google/starlark-go/blob/master/doc/spec.md#enumerate 262func enumerate(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 263 var iterable Iterable 264 var start int 265 if err := UnpackPositionalArgs("enumerate", args, kwargs, 1, &iterable, &start); err != nil { 266 return nil, err 267 } 268 269 iter := iterable.Iterate() 270 if iter == nil { 271 return nil, fmt.Errorf("enumerate: got %s, want iterable", iterable.Type()) 272 } 273 defer iter.Done() 274 275 var pairs []Value 276 var x Value 277 278 if n := Len(iterable); n >= 0 { 279 // common case: known length 280 pairs = make([]Value, 0, n) 281 array := make(Tuple, 2*n) // allocate a single backing array 282 for i := 0; iter.Next(&x); i++ { 283 pair := array[:2:2] 284 array = array[2:] 285 pair[0] = MakeInt(start + i) 286 pair[1] = x 287 pairs = append(pairs, pair) 288 } 289 } else { 290 // non-sequence (unknown length) 291 for i := 0; iter.Next(&x); i++ { 292 pair := Tuple{MakeInt(start + i), x} 293 pairs = append(pairs, pair) 294 } 295 } 296 297 return NewList(pairs), nil 298} 299 300// https://github.com/google/starlark-go/blob/master/doc/spec.md#fail 301func fail(thread *Thread, b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 302 sep := " " 303 if err := UnpackArgs("fail", nil, kwargs, "sep?", &sep); err != nil { 304 return nil, err 305 } 306 buf := new(strings.Builder) 307 buf.WriteString("fail: ") 308 for i, v := range args { 309 if i > 0 { 310 buf.WriteString(sep) 311 } 312 if s, ok := AsString(v); ok { 313 buf.WriteString(s) 314 } else { 315 writeValue(buf, v, nil) 316 } 317 } 318 319 return nil, errors.New(buf.String()) 320} 321 322func float(thread *Thread, b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 323 if len(kwargs) > 0 { 324 return nil, fmt.Errorf("float does not accept keyword arguments") 325 } 326 if len(args) == 0 { 327 return Float(0.0), nil 328 } 329 if len(args) != 1 { 330 return nil, fmt.Errorf("float got %d arguments, wants 1", len(args)) 331 } 332 switch x := args[0].(type) { 333 case Bool: 334 if x { 335 return Float(1.0), nil 336 } else { 337 return Float(0.0), nil 338 } 339 case Int: 340 return x.Float(), nil 341 case Float: 342 return x, nil 343 case String: 344 f, err := strconv.ParseFloat(string(x), 64) 345 if err != nil { 346 return nil, nameErr(b, err) 347 } 348 return Float(f), nil 349 default: 350 return nil, fmt.Errorf("float got %s, want number or string", x.Type()) 351 } 352} 353 354// https://github.com/google/starlark-go/blob/master/doc/spec.md#getattr 355func getattr(thread *Thread, b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 356 var object, dflt Value 357 var name string 358 if err := UnpackPositionalArgs("getattr", args, kwargs, 2, &object, &name, &dflt); err != nil { 359 return nil, err 360 } 361 if object, ok := object.(HasAttrs); ok { 362 v, err := object.Attr(name) 363 if err != nil { 364 // An error could mean the field doesn't exist, 365 // or it exists but could not be computed. 366 if dflt != nil { 367 return dflt, nil 368 } 369 return nil, nameErr(b, err) 370 } 371 if v != nil { 372 return v, nil 373 } 374 // (nil, nil) => no such field 375 } 376 if dflt != nil { 377 return dflt, nil 378 } 379 return nil, fmt.Errorf("getattr: %s has no .%s field or method", object.Type(), name) 380} 381 382// https://github.com/google/starlark-go/blob/master/doc/spec.md#hasattr 383func hasattr(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 384 var object Value 385 var name string 386 if err := UnpackPositionalArgs("hasattr", args, kwargs, 2, &object, &name); err != nil { 387 return nil, err 388 } 389 if object, ok := object.(HasAttrs); ok { 390 v, err := object.Attr(name) 391 if err == nil { 392 return Bool(v != nil), nil 393 } 394 395 // An error does not conclusively indicate presence or 396 // absence of a field: it could occur while computing 397 // the value of a present attribute, or it could be a 398 // "no such attribute" error with details. 399 for _, x := range object.AttrNames() { 400 if x == name { 401 return True, nil 402 } 403 } 404 } 405 return False, nil 406} 407 408// https://github.com/google/starlark-go/blob/master/doc/spec.md#hash 409func hash(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 410 var s string 411 if err := UnpackPositionalArgs("hash", args, kwargs, 1, &s); err != nil { 412 return nil, err 413 } 414 415 // The Starlark spec requires that the hash function be 416 // deterministic across all runs, motivated by the need 417 // for reproducibility of builds. Thus we cannot call 418 // String.Hash, which uses the fastest implementation 419 // available, because as varies across process restarts, 420 // and may evolve with the implementation. 421 422 return MakeInt(int(javaStringHash(s))), nil 423} 424 425// javaStringHash returns the same hash as would be produced by 426// java.lang.String.hashCode. This requires transcoding the string to 427// UTF-16; transcoding may introduce Unicode replacement characters 428// U+FFFD if s does not contain valid UTF-8. 429func javaStringHash(s string) (h int32) { 430 for _, r := range s { 431 if utf16.IsSurrogate(r) { 432 c1, c2 := utf16.EncodeRune(r) 433 h = 31*h + c1 434 h = 31*h + c2 435 } else { 436 h = 31*h + r // r may be U+FFFD 437 } 438 } 439 return h 440} 441 442// https://github.com/google/starlark-go/blob/master/doc/spec.md#int 443func int_(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 444 var x Value = zero 445 var base Value 446 if err := UnpackArgs("int", args, kwargs, "x", &x, "base?", &base); err != nil { 447 return nil, err 448 } 449 450 // "If x is not a number or base is given, x must be a string." 451 if s, ok := AsString(x); ok { 452 b := 10 453 if base != nil { 454 var err error 455 b, err = AsInt32(base) 456 if err != nil || b != 0 && (b < 2 || b > 36) { 457 return nil, fmt.Errorf("int: base must be an integer >= 2 && <= 36") 458 } 459 } 460 461 orig := s // save original for error message 462 463 // remove sign 464 var neg bool 465 if s != "" { 466 if s[0] == '+' { 467 s = s[1:] 468 } else if s[0] == '-' { 469 neg = true 470 s = s[1:] 471 } 472 } 473 474 // remove base prefix 475 baseprefix := 0 476 if len(s) > 1 && s[0] == '0' { 477 if len(s) > 2 { 478 switch s[1] { 479 case 'o', 'O': 480 s = s[2:] 481 baseprefix = 8 482 case 'x', 'X': 483 s = s[2:] 484 baseprefix = 16 485 case 'b', 'B': 486 s = s[2:] 487 baseprefix = 2 488 } 489 } 490 491 // For automatic base detection, 492 // a string starting with zero 493 // must be all zeros. 494 // Thus we reject int("0755", 0). 495 if baseprefix == 0 && b == 0 { 496 for i := 1; i < len(s); i++ { 497 if s[i] != '0' { 498 goto invalid 499 } 500 } 501 return zero, nil 502 } 503 504 if b != 0 && baseprefix != 0 && baseprefix != b { 505 // Explicit base doesn't match prefix, 506 // e.g. int("0o755", 16). 507 goto invalid 508 } 509 } 510 511 // select base 512 if b == 0 { 513 if baseprefix != 0 { 514 b = baseprefix 515 } else { 516 b = 10 517 } 518 } 519 520 // we explicitly handled sign above. 521 // if a sign remains, it is invalid. 522 if s != "" && (s[0] == '-' || s[0] == '+') { 523 goto invalid 524 } 525 526 // s has no sign or base prefix. 527 // 528 // int(x) permits arbitrary precision, unlike the scanner. 529 if i, ok := new(big.Int).SetString(s, b); ok { 530 res := MakeBigInt(i) 531 if neg { 532 res = zero.Sub(res) 533 } 534 return res, nil 535 } 536 537 invalid: 538 return nil, fmt.Errorf("int: invalid literal with base %d: %s", b, orig) 539 } 540 541 if base != nil { 542 return nil, fmt.Errorf("int: can't convert non-string with explicit base") 543 } 544 545 if b, ok := x.(Bool); ok { 546 if b { 547 return one, nil 548 } else { 549 return zero, nil 550 } 551 } 552 553 i, err := NumberToInt(x) 554 if err != nil { 555 return nil, fmt.Errorf("int: %s", err) 556 } 557 return i, nil 558} 559 560// https://github.com/google/starlark-go/blob/master/doc/spec.md#len 561func len_(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 562 var x Value 563 if err := UnpackPositionalArgs("len", args, kwargs, 1, &x); err != nil { 564 return nil, err 565 } 566 len := Len(x) 567 if len < 0 { 568 return nil, fmt.Errorf("len: value of type %s has no len", x.Type()) 569 } 570 return MakeInt(len), nil 571} 572 573// https://github.com/google/starlark-go/blob/master/doc/spec.md#list 574func list(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 575 var iterable Iterable 576 if err := UnpackPositionalArgs("list", args, kwargs, 0, &iterable); err != nil { 577 return nil, err 578 } 579 var elems []Value 580 if iterable != nil { 581 iter := iterable.Iterate() 582 defer iter.Done() 583 if n := Len(iterable); n > 0 { 584 elems = make([]Value, 0, n) // preallocate if length known 585 } 586 var x Value 587 for iter.Next(&x) { 588 elems = append(elems, x) 589 } 590 } 591 return NewList(elems), nil 592} 593 594// https://github.com/google/starlark-go/blob/master/doc/spec.md#min 595func minmax(thread *Thread, b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 596 if len(args) == 0 { 597 return nil, fmt.Errorf("%s requires at least one positional argument", b.Name()) 598 } 599 var keyFunc Callable 600 if err := UnpackArgs(b.Name(), nil, kwargs, "key?", &keyFunc); err != nil { 601 return nil, err 602 } 603 var op syntax.Token 604 if b.Name() == "max" { 605 op = syntax.GT 606 } else { 607 op = syntax.LT 608 } 609 var iterable Value 610 if len(args) == 1 { 611 iterable = args[0] 612 } else { 613 iterable = args 614 } 615 iter := Iterate(iterable) 616 if iter == nil { 617 return nil, fmt.Errorf("%s: %s value is not iterable", b.Name(), iterable.Type()) 618 } 619 defer iter.Done() 620 var extremum Value 621 if !iter.Next(&extremum) { 622 return nil, nameErr(b, "argument is an empty sequence") 623 } 624 625 var extremeKey Value 626 var keyargs Tuple 627 if keyFunc == nil { 628 extremeKey = extremum 629 } else { 630 keyargs = Tuple{extremum} 631 res, err := Call(thread, keyFunc, keyargs, nil) 632 if err != nil { 633 return nil, err // to preserve backtrace, don't modify error 634 } 635 extremeKey = res 636 } 637 638 var x Value 639 for iter.Next(&x) { 640 var key Value 641 if keyFunc == nil { 642 key = x 643 } else { 644 keyargs[0] = x 645 res, err := Call(thread, keyFunc, keyargs, nil) 646 if err != nil { 647 return nil, err // to preserve backtrace, don't modify error 648 } 649 key = res 650 } 651 652 if ok, err := Compare(op, key, extremeKey); err != nil { 653 return nil, nameErr(b, err) 654 } else if ok { 655 extremum = x 656 extremeKey = key 657 } 658 } 659 return extremum, nil 660} 661 662// https://github.com/google/starlark-go/blob/master/doc/spec.md#ord 663func ord(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 664 if len(kwargs) > 0 { 665 return nil, fmt.Errorf("ord does not accept keyword arguments") 666 } 667 if len(args) != 1 { 668 return nil, fmt.Errorf("ord: got %d arguments, want 1", len(args)) 669 } 670 s, ok := AsString(args[0]) 671 if !ok { 672 return nil, fmt.Errorf("ord: got %s, want string", args[0].Type()) 673 } 674 r, sz := utf8.DecodeRuneInString(s) 675 if sz == 0 || sz != len(s) { 676 n := utf8.RuneCountInString(s) 677 return nil, fmt.Errorf("ord: string encodes %d Unicode code points, want 1", n) 678 } 679 return MakeInt(int(r)), nil 680} 681 682// https://github.com/google/starlark-go/blob/master/doc/spec.md#print 683func print(thread *Thread, b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 684 sep := " " 685 if err := UnpackArgs("print", nil, kwargs, "sep?", &sep); err != nil { 686 return nil, err 687 } 688 buf := new(strings.Builder) 689 for i, v := range args { 690 if i > 0 { 691 buf.WriteString(sep) 692 } 693 if s, ok := AsString(v); ok { 694 buf.WriteString(s) 695 } else { 696 writeValue(buf, v, nil) 697 } 698 } 699 700 s := buf.String() 701 if thread.Print != nil { 702 thread.Print(thread, s) 703 } else { 704 fmt.Fprintln(os.Stderr, s) 705 } 706 return None, nil 707} 708 709// https://github.com/google/starlark-go/blob/master/doc/spec.md#range 710func range_(thread *Thread, b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 711 var start, stop, step int 712 step = 1 713 if err := UnpackPositionalArgs("range", args, kwargs, 1, &start, &stop, &step); err != nil { 714 return nil, err 715 } 716 717 // TODO(adonovan): analyze overflow/underflows cases for 32-bit implementations. 718 if len(args) == 1 { 719 // range(stop) 720 start, stop = 0, start 721 } 722 if step == 0 { 723 // we were given range(start, stop, 0) 724 return nil, nameErr(b, "step argument must not be zero") 725 } 726 727 return rangeValue{start: start, stop: stop, step: step, len: rangeLen(start, stop, step)}, nil 728} 729 730// A rangeValue is a comparable, immutable, indexable sequence of integers 731// defined by the three parameters to a range(...) call. 732// Invariant: step != 0. 733type rangeValue struct{ start, stop, step, len int } 734 735var ( 736 _ Indexable = rangeValue{} 737 _ Sequence = rangeValue{} 738 _ Comparable = rangeValue{} 739 _ Sliceable = rangeValue{} 740) 741 742func (r rangeValue) Len() int { return r.len } 743func (r rangeValue) Index(i int) Value { return MakeInt(r.start + i*r.step) } 744func (r rangeValue) Iterate() Iterator { return &rangeIterator{r, 0} } 745 746// rangeLen calculates the length of a range with the provided start, stop, and step. 747// caller must ensure that step is non-zero. 748func rangeLen(start, stop, step int) int { 749 switch { 750 case step > 0: 751 if stop > start { 752 return (stop-1-start)/step + 1 753 } 754 case step < 0: 755 if start > stop { 756 return (start-1-stop)/-step + 1 757 } 758 default: 759 panic("rangeLen: zero step") 760 } 761 return 0 762} 763 764func (r rangeValue) Slice(start, end, step int) Value { 765 newStart := r.start + r.step*start 766 newStop := r.start + r.step*end 767 newStep := r.step * step 768 return rangeValue{ 769 start: newStart, 770 stop: newStop, 771 step: newStep, 772 len: rangeLen(newStart, newStop, newStep), 773 } 774} 775 776func (r rangeValue) Freeze() {} // immutable 777func (r rangeValue) String() string { 778 if r.step != 1 { 779 return fmt.Sprintf("range(%d, %d, %d)", r.start, r.stop, r.step) 780 } else if r.start != 0 { 781 return fmt.Sprintf("range(%d, %d)", r.start, r.stop) 782 } else { 783 return fmt.Sprintf("range(%d)", r.stop) 784 } 785} 786func (r rangeValue) Type() string { return "range" } 787func (r rangeValue) Truth() Bool { return r.len > 0 } 788func (r rangeValue) Hash() (uint32, error) { return 0, fmt.Errorf("unhashable: range") } 789 790func (x rangeValue) CompareSameType(op syntax.Token, y_ Value, depth int) (bool, error) { 791 y := y_.(rangeValue) 792 switch op { 793 case syntax.EQL: 794 return rangeEqual(x, y), nil 795 case syntax.NEQ: 796 return !rangeEqual(x, y), nil 797 default: 798 return false, fmt.Errorf("%s %s %s not implemented", x.Type(), op, y.Type()) 799 } 800} 801 802func rangeEqual(x, y rangeValue) bool { 803 // Two ranges compare equal if they denote the same sequence. 804 if x.len != y.len { 805 return false // sequences differ in length 806 } 807 if x.len == 0 { 808 return true // both sequences are empty 809 } 810 if x.start != y.start { 811 return false // first element differs 812 } 813 return x.len == 1 || x.step == y.step 814} 815 816func (r rangeValue) contains(x Int) bool { 817 x32, err := AsInt32(x) 818 if err != nil { 819 return false // out of range 820 } 821 delta := x32 - r.start 822 quo, rem := delta/r.step, delta%r.step 823 return rem == 0 && 0 <= quo && quo < r.len 824} 825 826type rangeIterator struct { 827 r rangeValue 828 i int 829} 830 831func (it *rangeIterator) Next(p *Value) bool { 832 if it.i < it.r.len { 833 *p = it.r.Index(it.i) 834 it.i++ 835 return true 836 } 837 return false 838} 839func (*rangeIterator) Done() {} 840 841// https://github.com/google/starlark-go/blob/master/doc/spec.md#repr 842func repr(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 843 var x Value 844 if err := UnpackPositionalArgs("repr", args, kwargs, 1, &x); err != nil { 845 return nil, err 846 } 847 return String(x.String()), nil 848} 849 850// https://github.com/google/starlark-go/blob/master/doc/spec.md#reversed 851func reversed(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 852 var iterable Iterable 853 if err := UnpackPositionalArgs("reversed", args, kwargs, 1, &iterable); err != nil { 854 return nil, err 855 } 856 iter := iterable.Iterate() 857 defer iter.Done() 858 var elems []Value 859 if n := Len(args[0]); n >= 0 { 860 elems = make([]Value, 0, n) // preallocate if length known 861 } 862 var x Value 863 for iter.Next(&x) { 864 elems = append(elems, x) 865 } 866 n := len(elems) 867 for i := 0; i < n>>1; i++ { 868 elems[i], elems[n-1-i] = elems[n-1-i], elems[i] 869 } 870 return NewList(elems), nil 871} 872 873// https://github.com/google/starlark-go/blob/master/doc/spec.md#set 874func set(thread *Thread, b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 875 var iterable Iterable 876 if err := UnpackPositionalArgs("set", args, kwargs, 0, &iterable); err != nil { 877 return nil, err 878 } 879 set := new(Set) 880 if iterable != nil { 881 iter := iterable.Iterate() 882 defer iter.Done() 883 var x Value 884 for iter.Next(&x) { 885 if err := set.Insert(x); err != nil { 886 return nil, nameErr(b, err) 887 } 888 } 889 } 890 return set, nil 891} 892 893// https://github.com/google/starlark-go/blob/master/doc/spec.md#sorted 894func sorted(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 895 // Oddly, Python's sorted permits all arguments to be positional, thus so do we. 896 var iterable Iterable 897 var key Callable 898 var reverse bool 899 if err := UnpackArgs("sorted", args, kwargs, 900 "iterable", &iterable, 901 "key?", &key, 902 "reverse?", &reverse, 903 ); err != nil { 904 return nil, err 905 } 906 907 iter := iterable.Iterate() 908 defer iter.Done() 909 var values []Value 910 if n := Len(iterable); n > 0 { 911 values = make(Tuple, 0, n) // preallocate if length is known 912 } 913 var x Value 914 for iter.Next(&x) { 915 values = append(values, x) 916 } 917 918 // Derive keys from values by applying key function. 919 var keys []Value 920 if key != nil { 921 keys = make([]Value, len(values)) 922 for i, v := range values { 923 k, err := Call(thread, key, Tuple{v}, nil) 924 if err != nil { 925 return nil, err // to preserve backtrace, don't modify error 926 } 927 keys[i] = k 928 } 929 } 930 931 slice := &sortSlice{keys: keys, values: values} 932 if reverse { 933 sort.Stable(sort.Reverse(slice)) 934 } else { 935 sort.Stable(slice) 936 } 937 return NewList(slice.values), slice.err 938} 939 940type sortSlice struct { 941 keys []Value // nil => values[i] is key 942 values []Value 943 err error 944} 945 946func (s *sortSlice) Len() int { return len(s.values) } 947func (s *sortSlice) Less(i, j int) bool { 948 keys := s.keys 949 if s.keys == nil { 950 keys = s.values 951 } 952 ok, err := Compare(syntax.LT, keys[i], keys[j]) 953 if err != nil { 954 s.err = err 955 } 956 return ok 957} 958func (s *sortSlice) Swap(i, j int) { 959 if s.keys != nil { 960 s.keys[i], s.keys[j] = s.keys[j], s.keys[i] 961 } 962 s.values[i], s.values[j] = s.values[j], s.values[i] 963} 964 965// https://github.com/google/starlark-go/blob/master/doc/spec.md#str 966func str(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 967 if len(kwargs) > 0 { 968 return nil, fmt.Errorf("str does not accept keyword arguments") 969 } 970 if len(args) != 1 { 971 return nil, fmt.Errorf("str: got %d arguments, want exactly 1", len(args)) 972 } 973 x := args[0] 974 if _, ok := AsString(x); !ok { 975 x = String(x.String()) 976 } 977 return x, nil 978} 979 980// https://github.com/google/starlark-go/blob/master/doc/spec.md#tuple 981func tuple(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 982 var iterable Iterable 983 if err := UnpackPositionalArgs("tuple", args, kwargs, 0, &iterable); err != nil { 984 return nil, err 985 } 986 if len(args) == 0 { 987 return Tuple(nil), nil 988 } 989 iter := iterable.Iterate() 990 defer iter.Done() 991 var elems Tuple 992 if n := Len(iterable); n > 0 { 993 elems = make(Tuple, 0, n) // preallocate if length is known 994 } 995 var x Value 996 for iter.Next(&x) { 997 elems = append(elems, x) 998 } 999 return elems, nil 1000} 1001 1002// https://github.com/google/starlark-go/blob/master/doc/spec.md#type 1003func type_(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1004 if len(kwargs) > 0 { 1005 return nil, fmt.Errorf("type does not accept keyword arguments") 1006 } 1007 if len(args) != 1 { 1008 return nil, fmt.Errorf("type: got %d arguments, want exactly 1", len(args)) 1009 } 1010 return String(args[0].Type()), nil 1011} 1012 1013// https://github.com/google/starlark-go/blob/master/doc/spec.md#zip 1014func zip(thread *Thread, _ *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1015 if len(kwargs) > 0 { 1016 return nil, fmt.Errorf("zip does not accept keyword arguments") 1017 } 1018 rows, cols := 0, len(args) 1019 iters := make([]Iterator, cols) 1020 defer func() { 1021 for _, iter := range iters { 1022 if iter != nil { 1023 iter.Done() 1024 } 1025 } 1026 }() 1027 for i, seq := range args { 1028 it := Iterate(seq) 1029 if it == nil { 1030 return nil, fmt.Errorf("zip: argument #%d is not iterable: %s", i+1, seq.Type()) 1031 } 1032 iters[i] = it 1033 n := Len(seq) 1034 if i == 0 || n < rows { 1035 rows = n // possibly -1 1036 } 1037 } 1038 var result []Value 1039 if rows >= 0 { 1040 // length known 1041 result = make([]Value, rows) 1042 array := make(Tuple, cols*rows) // allocate a single backing array 1043 for i := 0; i < rows; i++ { 1044 tuple := array[:cols:cols] 1045 array = array[cols:] 1046 for j, iter := range iters { 1047 iter.Next(&tuple[j]) 1048 } 1049 result[i] = tuple 1050 } 1051 } else { 1052 // length not known 1053 outer: 1054 for { 1055 tuple := make(Tuple, cols) 1056 for i, iter := range iters { 1057 if !iter.Next(&tuple[i]) { 1058 break outer 1059 } 1060 } 1061 result = append(result, tuple) 1062 } 1063 } 1064 return NewList(result), nil 1065} 1066 1067// ---- methods of built-in types --- 1068 1069// https://github.com/google/starlark-go/blob/master/doc/spec.md#dict·get 1070func dict_get(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1071 var key, dflt Value 1072 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 1, &key, &dflt); err != nil { 1073 return nil, err 1074 } 1075 if v, ok, err := b.Receiver().(*Dict).Get(key); err != nil { 1076 return nil, nameErr(b, err) 1077 } else if ok { 1078 return v, nil 1079 } else if dflt != nil { 1080 return dflt, nil 1081 } 1082 return None, nil 1083} 1084 1085// https://github.com/google/starlark-go/blob/master/doc/spec.md#dict·clear 1086func dict_clear(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1087 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1088 return nil, err 1089 } 1090 return None, b.Receiver().(*Dict).Clear() 1091} 1092 1093// https://github.com/google/starlark-go/blob/master/doc/spec.md#dict·items 1094func dict_items(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1095 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1096 return nil, err 1097 } 1098 items := b.Receiver().(*Dict).Items() 1099 res := make([]Value, len(items)) 1100 for i, item := range items { 1101 res[i] = item // convert [2]Value to Value 1102 } 1103 return NewList(res), nil 1104} 1105 1106// https://github.com/google/starlark-go/blob/master/doc/spec.md#dict·keys 1107func dict_keys(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1108 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1109 return nil, err 1110 } 1111 return NewList(b.Receiver().(*Dict).Keys()), nil 1112} 1113 1114// https://github.com/google/starlark-go/blob/master/doc/spec.md#dict·pop 1115func dict_pop(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1116 var k, d Value 1117 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 1, &k, &d); err != nil { 1118 return nil, err 1119 } 1120 if v, found, err := b.Receiver().(*Dict).Delete(k); err != nil { 1121 return nil, nameErr(b, err) // dict is frozen or key is unhashable 1122 } else if found { 1123 return v, nil 1124 } else if d != nil { 1125 return d, nil 1126 } 1127 return nil, nameErr(b, "missing key") 1128} 1129 1130// https://github.com/google/starlark-go/blob/master/doc/spec.md#dict·popitem 1131func dict_popitem(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1132 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1133 return nil, err 1134 } 1135 recv := b.Receiver().(*Dict) 1136 k, ok := recv.ht.first() 1137 if !ok { 1138 return nil, nameErr(b, "empty dict") 1139 } 1140 v, _, err := recv.Delete(k) 1141 if err != nil { 1142 return nil, nameErr(b, err) // dict is frozen 1143 } 1144 return Tuple{k, v}, nil 1145} 1146 1147// https://github.com/google/starlark-go/blob/master/doc/spec.md#dict·setdefault 1148func dict_setdefault(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1149 var key, dflt Value = nil, None 1150 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 1, &key, &dflt); err != nil { 1151 return nil, err 1152 } 1153 dict := b.Receiver().(*Dict) 1154 if v, ok, err := dict.Get(key); err != nil { 1155 return nil, nameErr(b, err) 1156 } else if ok { 1157 return v, nil 1158 } else if err := dict.SetKey(key, dflt); err != nil { 1159 return nil, nameErr(b, err) 1160 } else { 1161 return dflt, nil 1162 } 1163} 1164 1165// https://github.com/google/starlark-go/blob/master/doc/spec.md#dict·update 1166func dict_update(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1167 if len(args) > 1 { 1168 return nil, fmt.Errorf("update: got %d arguments, want at most 1", len(args)) 1169 } 1170 if err := updateDict(b.Receiver().(*Dict), args, kwargs); err != nil { 1171 return nil, fmt.Errorf("update: %v", err) 1172 } 1173 return None, nil 1174} 1175 1176// https://github.com/google/starlark-go/blob/master/doc/spec.md#dict·update 1177func dict_values(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1178 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1179 return nil, err 1180 } 1181 items := b.Receiver().(*Dict).Items() 1182 res := make([]Value, len(items)) 1183 for i, item := range items { 1184 res[i] = item[1] 1185 } 1186 return NewList(res), nil 1187} 1188 1189// https://github.com/google/starlark-go/blob/master/doc/spec.md#list·append 1190func list_append(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1191 var object Value 1192 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 1, &object); err != nil { 1193 return nil, err 1194 } 1195 recv := b.Receiver().(*List) 1196 if err := recv.checkMutable("append to"); err != nil { 1197 return nil, nameErr(b, err) 1198 } 1199 recv.elems = append(recv.elems, object) 1200 return None, nil 1201} 1202 1203// https://github.com/google/starlark-go/blob/master/doc/spec.md#list·clear 1204func list_clear(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1205 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1206 return nil, err 1207 } 1208 if err := b.Receiver().(*List).Clear(); err != nil { 1209 return nil, nameErr(b, err) 1210 } 1211 return None, nil 1212} 1213 1214// https://github.com/google/starlark-go/blob/master/doc/spec.md#list·extend 1215func list_extend(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1216 recv := b.Receiver().(*List) 1217 var iterable Iterable 1218 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 1, &iterable); err != nil { 1219 return nil, err 1220 } 1221 if err := recv.checkMutable("extend"); err != nil { 1222 return nil, nameErr(b, err) 1223 } 1224 listExtend(recv, iterable) 1225 return None, nil 1226} 1227 1228// https://github.com/google/starlark-go/blob/master/doc/spec.md#list·index 1229func list_index(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1230 var value, start_, end_ Value 1231 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 1, &value, &start_, &end_); err != nil { 1232 return nil, err 1233 } 1234 1235 recv := b.Receiver().(*List) 1236 start, end, err := indices(start_, end_, recv.Len()) 1237 if err != nil { 1238 return nil, nameErr(b, err) 1239 } 1240 1241 for i := start; i < end; i++ { 1242 if eq, err := Equal(recv.elems[i], value); err != nil { 1243 return nil, nameErr(b, err) 1244 } else if eq { 1245 return MakeInt(i), nil 1246 } 1247 } 1248 return nil, nameErr(b, "value not in list") 1249} 1250 1251// https://github.com/google/starlark-go/blob/master/doc/spec.md#list·insert 1252func list_insert(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1253 recv := b.Receiver().(*List) 1254 var index int 1255 var object Value 1256 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 2, &index, &object); err != nil { 1257 return nil, err 1258 } 1259 if err := recv.checkMutable("insert into"); err != nil { 1260 return nil, nameErr(b, err) 1261 } 1262 1263 if index < 0 { 1264 index += recv.Len() 1265 } 1266 1267 if index >= recv.Len() { 1268 // end 1269 recv.elems = append(recv.elems, object) 1270 } else { 1271 if index < 0 { 1272 index = 0 // start 1273 } 1274 recv.elems = append(recv.elems, nil) 1275 copy(recv.elems[index+1:], recv.elems[index:]) // slide up one 1276 recv.elems[index] = object 1277 } 1278 return None, nil 1279} 1280 1281// https://github.com/google/starlark-go/blob/master/doc/spec.md#list·remove 1282func list_remove(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1283 recv := b.Receiver().(*List) 1284 var value Value 1285 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 1, &value); err != nil { 1286 return nil, err 1287 } 1288 if err := recv.checkMutable("remove from"); err != nil { 1289 return nil, nameErr(b, err) 1290 } 1291 for i, elem := range recv.elems { 1292 if eq, err := Equal(elem, value); err != nil { 1293 return nil, fmt.Errorf("remove: %v", err) 1294 } else if eq { 1295 recv.elems = append(recv.elems[:i], recv.elems[i+1:]...) 1296 return None, nil 1297 } 1298 } 1299 return nil, fmt.Errorf("remove: element not found") 1300} 1301 1302// https://github.com/google/starlark-go/blob/master/doc/spec.md#list·pop 1303func list_pop(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1304 recv := b.Receiver() 1305 list := recv.(*List) 1306 n := list.Len() 1307 i := n - 1 1308 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0, &i); err != nil { 1309 return nil, err 1310 } 1311 origI := i 1312 if i < 0 { 1313 i += n 1314 } 1315 if i < 0 || i >= n { 1316 return nil, nameErr(b, outOfRange(origI, n, list)) 1317 } 1318 if err := list.checkMutable("pop from"); err != nil { 1319 return nil, nameErr(b, err) 1320 } 1321 res := list.elems[i] 1322 list.elems = append(list.elems[:i], list.elems[i+1:]...) 1323 return res, nil 1324} 1325 1326// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·capitalize 1327func string_capitalize(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1328 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1329 return nil, err 1330 } 1331 s := string(b.Receiver().(String)) 1332 res := new(strings.Builder) 1333 res.Grow(len(s)) 1334 for i, r := range s { 1335 if i == 0 { 1336 r = unicode.ToTitle(r) 1337 } else { 1338 r = unicode.ToLower(r) 1339 } 1340 res.WriteRune(r) 1341 } 1342 return String(res.String()), nil 1343} 1344 1345// string_iterable returns an unspecified iterable value whose iterator yields: 1346// - elems: successive 1-byte substrings 1347// - codepoints: successive substrings that encode a single Unicode code point. 1348// - elem_ords: numeric values of successive bytes 1349// - codepoint_ords: numeric values of successive Unicode code points 1350func string_iterable(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1351 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1352 return nil, err 1353 } 1354 return stringIterable{ 1355 s: b.Receiver().(String), 1356 ords: b.Name()[len(b.Name())-2] == 'd', 1357 codepoints: b.Name()[0] == 'c', 1358 }, nil 1359} 1360 1361// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·count 1362func string_count(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1363 var sub string 1364 var start_, end_ Value 1365 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 1, &sub, &start_, &end_); err != nil { 1366 return nil, err 1367 } 1368 1369 recv := string(b.Receiver().(String)) 1370 start, end, err := indices(start_, end_, len(recv)) 1371 if err != nil { 1372 return nil, nameErr(b, err) 1373 } 1374 1375 var slice string 1376 if start < end { 1377 slice = recv[start:end] 1378 } 1379 return MakeInt(strings.Count(slice, sub)), nil 1380} 1381 1382// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·isalnum 1383func string_isalnum(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1384 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1385 return nil, err 1386 } 1387 recv := string(b.Receiver().(String)) 1388 for _, r := range recv { 1389 if !unicode.IsLetter(r) && !unicode.IsDigit(r) { 1390 return False, nil 1391 } 1392 } 1393 return Bool(recv != ""), nil 1394} 1395 1396// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·isalpha 1397func string_isalpha(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1398 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1399 return nil, err 1400 } 1401 recv := string(b.Receiver().(String)) 1402 for _, r := range recv { 1403 if !unicode.IsLetter(r) { 1404 return False, nil 1405 } 1406 } 1407 return Bool(recv != ""), nil 1408} 1409 1410// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·isdigit 1411func string_isdigit(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1412 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1413 return nil, err 1414 } 1415 recv := string(b.Receiver().(String)) 1416 for _, r := range recv { 1417 if !unicode.IsDigit(r) { 1418 return False, nil 1419 } 1420 } 1421 return Bool(recv != ""), nil 1422} 1423 1424// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·islower 1425func string_islower(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1426 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1427 return nil, err 1428 } 1429 recv := string(b.Receiver().(String)) 1430 return Bool(isCasedString(recv) && recv == strings.ToLower(recv)), nil 1431} 1432 1433// isCasedString reports whether its argument contains any cased code points. 1434func isCasedString(s string) bool { 1435 for _, r := range s { 1436 if isCasedRune(r) { 1437 return true 1438 } 1439 } 1440 return false 1441} 1442 1443func isCasedRune(r rune) bool { 1444 // It's unclear what the correct behavior is for a rune such as 'ffi', 1445 // a lowercase letter with no upper or title case and no SimpleFold. 1446 return 'a' <= r && r <= 'z' || 'A' <= r && r <= 'Z' || unicode.SimpleFold(r) != r 1447} 1448 1449// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·isspace 1450func string_isspace(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1451 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1452 return nil, err 1453 } 1454 recv := string(b.Receiver().(String)) 1455 for _, r := range recv { 1456 if !unicode.IsSpace(r) { 1457 return False, nil 1458 } 1459 } 1460 return Bool(recv != ""), nil 1461} 1462 1463// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·istitle 1464func string_istitle(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1465 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1466 return nil, err 1467 } 1468 recv := string(b.Receiver().(String)) 1469 1470 // Python semantics differ from x==strings.{To,}Title(x) in Go: 1471 // "uppercase characters may only follow uncased characters and 1472 // lowercase characters only cased ones." 1473 var cased, prevCased bool 1474 for _, r := range recv { 1475 if 'A' <= r && r <= 'Z' || unicode.IsTitle(r) { // e.g. "Dž" 1476 if prevCased { 1477 return False, nil 1478 } 1479 prevCased = true 1480 cased = true 1481 } else if unicode.IsLower(r) { 1482 if !prevCased { 1483 return False, nil 1484 } 1485 prevCased = true 1486 cased = true 1487 } else if unicode.IsUpper(r) { 1488 return False, nil 1489 } else { 1490 prevCased = false 1491 } 1492 } 1493 return Bool(cased), nil 1494} 1495 1496// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·isupper 1497func string_isupper(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1498 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1499 return nil, err 1500 } 1501 recv := string(b.Receiver().(String)) 1502 return Bool(isCasedString(recv) && recv == strings.ToUpper(recv)), nil 1503} 1504 1505// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·find 1506func string_find(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1507 return string_find_impl(b, args, kwargs, true, false) 1508} 1509 1510// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·format 1511func string_format(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1512 format := string(b.Receiver().(String)) 1513 var auto, manual bool // kinds of positional indexing used 1514 buf := new(strings.Builder) 1515 index := 0 1516 for { 1517 literal := format 1518 i := strings.IndexByte(format, '{') 1519 if i >= 0 { 1520 literal = format[:i] 1521 } 1522 1523 // Replace "}}" with "}" in non-field portion, rejecting a lone '}'. 1524 for { 1525 j := strings.IndexByte(literal, '}') 1526 if j < 0 { 1527 buf.WriteString(literal) 1528 break 1529 } 1530 if len(literal) == j+1 || literal[j+1] != '}' { 1531 return nil, fmt.Errorf("format: single '}' in format") 1532 } 1533 buf.WriteString(literal[:j+1]) 1534 literal = literal[j+2:] 1535 } 1536 1537 if i < 0 { 1538 break // end of format string 1539 } 1540 1541 if i+1 < len(format) && format[i+1] == '{' { 1542 // "{{" means a literal '{' 1543 buf.WriteByte('{') 1544 format = format[i+2:] 1545 continue 1546 } 1547 1548 format = format[i+1:] 1549 i = strings.IndexByte(format, '}') 1550 if i < 0 { 1551 return nil, fmt.Errorf("format: unmatched '{' in format") 1552 } 1553 1554 var arg Value 1555 conv := "s" 1556 var spec string 1557 1558 field := format[:i] 1559 format = format[i+1:] 1560 1561 var name string 1562 if i := strings.IndexByte(field, '!'); i < 0 { 1563 // "name" or "name:spec" 1564 if i := strings.IndexByte(field, ':'); i < 0 { 1565 name = field 1566 } else { 1567 name = field[:i] 1568 spec = field[i+1:] 1569 } 1570 } else { 1571 // "name!conv" or "name!conv:spec" 1572 name = field[:i] 1573 field = field[i+1:] 1574 // "conv" or "conv:spec" 1575 if i := strings.IndexByte(field, ':'); i < 0 { 1576 conv = field 1577 } else { 1578 conv = field[:i] 1579 spec = field[i+1:] 1580 } 1581 } 1582 1583 if name == "" { 1584 // "{}": automatic indexing 1585 if manual { 1586 return nil, fmt.Errorf("format: cannot switch from manual field specification to automatic field numbering") 1587 } 1588 auto = true 1589 if index >= len(args) { 1590 return nil, fmt.Errorf("format: tuple index out of range") 1591 } 1592 arg = args[index] 1593 index++ 1594 } else if num, ok := decimal(name); ok { 1595 // positional argument 1596 if auto { 1597 return nil, fmt.Errorf("format: cannot switch from automatic field numbering to manual field specification") 1598 } 1599 manual = true 1600 if num >= len(args) { 1601 return nil, fmt.Errorf("format: tuple index out of range") 1602 } else { 1603 arg = args[num] 1604 } 1605 } else { 1606 // keyword argument 1607 for _, kv := range kwargs { 1608 if string(kv[0].(String)) == name { 1609 arg = kv[1] 1610 break 1611 } 1612 } 1613 if arg == nil { 1614 // Starlark does not support Python's x.y or a[i] syntaxes, 1615 // or nested use of {...}. 1616 if strings.Contains(name, ".") { 1617 return nil, fmt.Errorf("format: attribute syntax x.y is not supported in replacement fields: %s", name) 1618 } 1619 if strings.Contains(name, "[") { 1620 return nil, fmt.Errorf("format: element syntax a[i] is not supported in replacement fields: %s", name) 1621 } 1622 if strings.Contains(name, "{") { 1623 return nil, fmt.Errorf("format: nested replacement fields not supported") 1624 } 1625 return nil, fmt.Errorf("format: keyword %s not found", name) 1626 } 1627 } 1628 1629 if spec != "" { 1630 // Starlark does not support Python's format_spec features. 1631 return nil, fmt.Errorf("format spec features not supported in replacement fields: %s", spec) 1632 } 1633 1634 switch conv { 1635 case "s": 1636 if str, ok := AsString(arg); ok { 1637 buf.WriteString(str) 1638 } else { 1639 writeValue(buf, arg, nil) 1640 } 1641 case "r": 1642 writeValue(buf, arg, nil) 1643 default: 1644 return nil, fmt.Errorf("format: unknown conversion %q", conv) 1645 } 1646 } 1647 return String(buf.String()), nil 1648} 1649 1650// decimal interprets s as a sequence of decimal digits. 1651func decimal(s string) (x int, ok bool) { 1652 n := len(s) 1653 for i := 0; i < n; i++ { 1654 digit := s[i] - '0' 1655 if digit > 9 { 1656 return 0, false 1657 } 1658 x = x*10 + int(digit) 1659 if x < 0 { 1660 return 0, false // underflow 1661 } 1662 } 1663 return x, true 1664} 1665 1666// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·index 1667func string_index(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1668 return string_find_impl(b, args, kwargs, false, false) 1669} 1670 1671// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·join 1672func string_join(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1673 recv := string(b.Receiver().(String)) 1674 var iterable Iterable 1675 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 1, &iterable); err != nil { 1676 return nil, err 1677 } 1678 iter := iterable.Iterate() 1679 defer iter.Done() 1680 buf := new(strings.Builder) 1681 var x Value 1682 for i := 0; iter.Next(&x); i++ { 1683 if i > 0 { 1684 buf.WriteString(recv) 1685 } 1686 s, ok := AsString(x) 1687 if !ok { 1688 return nil, fmt.Errorf("join: in list, want string, got %s", x.Type()) 1689 } 1690 buf.WriteString(s) 1691 } 1692 return String(buf.String()), nil 1693} 1694 1695// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·lower 1696func string_lower(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1697 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1698 return nil, err 1699 } 1700 return String(strings.ToLower(string(b.Receiver().(String)))), nil 1701} 1702 1703// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·partition 1704func string_partition(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1705 recv := string(b.Receiver().(String)) 1706 var sep string 1707 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 1, &sep); err != nil { 1708 return nil, err 1709 } 1710 if sep == "" { 1711 return nil, nameErr(b, "empty separator") 1712 } 1713 var i int 1714 if b.Name()[0] == 'p' { 1715 i = strings.Index(recv, sep) // partition 1716 } else { 1717 i = strings.LastIndex(recv, sep) // rpartition 1718 } 1719 tuple := make(Tuple, 0, 3) 1720 if i < 0 { 1721 if b.Name()[0] == 'p' { 1722 tuple = append(tuple, String(recv), String(""), String("")) 1723 } else { 1724 tuple = append(tuple, String(""), String(""), String(recv)) 1725 } 1726 } else { 1727 tuple = append(tuple, String(recv[:i]), String(sep), String(recv[i+len(sep):])) 1728 } 1729 return tuple, nil 1730} 1731 1732// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·replace 1733func string_replace(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1734 recv := string(b.Receiver().(String)) 1735 var old, new string 1736 count := -1 1737 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 2, &old, &new, &count); err != nil { 1738 return nil, err 1739 } 1740 return String(strings.Replace(recv, old, new, count)), nil 1741} 1742 1743// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·rfind 1744func string_rfind(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1745 return string_find_impl(b, args, kwargs, true, true) 1746} 1747 1748// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·rindex 1749func string_rindex(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1750 return string_find_impl(b, args, kwargs, false, true) 1751} 1752 1753// https://github.com/google/starlark-go/starlark/blob/master/doc/spec.md#string·startswith 1754// https://github.com/google/starlark-go/starlark/blob/master/doc/spec.md#string·endswith 1755func string_startswith(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1756 var x Value 1757 var start, end Value = None, None 1758 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 1, &x, &start, &end); err != nil { 1759 return nil, err 1760 } 1761 1762 // compute effective substring. 1763 s := string(b.Receiver().(String)) 1764 if start, end, err := indices(start, end, len(s)); err != nil { 1765 return nil, nameErr(b, err) 1766 } else { 1767 if end < start { 1768 end = start // => empty result 1769 } 1770 s = s[start:end] 1771 } 1772 1773 f := strings.HasPrefix 1774 if b.Name()[0] == 'e' { // endswith 1775 f = strings.HasSuffix 1776 } 1777 1778 switch x := x.(type) { 1779 case Tuple: 1780 for i, x := range x { 1781 prefix, ok := AsString(x) 1782 if !ok { 1783 return nil, fmt.Errorf("%s: want string, got %s, for element %d", 1784 b.Name(), x.Type(), i) 1785 } 1786 if f(s, prefix) { 1787 return True, nil 1788 } 1789 } 1790 return False, nil 1791 case String: 1792 return Bool(f(s, string(x))), nil 1793 } 1794 return nil, fmt.Errorf("%s: got %s, want string or tuple of string", b.Name(), x.Type()) 1795} 1796 1797// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·strip 1798// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·lstrip 1799// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·rstrip 1800func string_strip(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1801 var chars string 1802 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0, &chars); err != nil { 1803 return nil, err 1804 } 1805 recv := string(b.Receiver().(String)) 1806 var s string 1807 switch b.Name()[0] { 1808 case 's': // strip 1809 if chars != "" { 1810 s = strings.Trim(recv, chars) 1811 } else { 1812 s = strings.TrimSpace(recv) 1813 } 1814 case 'l': // lstrip 1815 if chars != "" { 1816 s = strings.TrimLeft(recv, chars) 1817 } else { 1818 s = strings.TrimLeftFunc(recv, unicode.IsSpace) 1819 } 1820 case 'r': // rstrip 1821 if chars != "" { 1822 s = strings.TrimRight(recv, chars) 1823 } else { 1824 s = strings.TrimRightFunc(recv, unicode.IsSpace) 1825 } 1826 } 1827 return String(s), nil 1828} 1829 1830// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·title 1831func string_title(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1832 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1833 return nil, err 1834 } 1835 1836 s := string(b.Receiver().(String)) 1837 1838 // Python semantics differ from x==strings.{To,}Title(x) in Go: 1839 // "uppercase characters may only follow uncased characters and 1840 // lowercase characters only cased ones." 1841 buf := new(strings.Builder) 1842 buf.Grow(len(s)) 1843 var prevCased bool 1844 for _, r := range s { 1845 if prevCased { 1846 r = unicode.ToLower(r) 1847 } else { 1848 r = unicode.ToTitle(r) 1849 } 1850 prevCased = isCasedRune(r) 1851 buf.WriteRune(r) 1852 } 1853 return String(buf.String()), nil 1854} 1855 1856// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·upper 1857func string_upper(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1858 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0); err != nil { 1859 return nil, err 1860 } 1861 return String(strings.ToUpper(string(b.Receiver().(String)))), nil 1862} 1863 1864// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·split 1865// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·rsplit 1866func string_split(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1867 recv := string(b.Receiver().(String)) 1868 var sep_ Value 1869 maxsplit := -1 1870 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0, &sep_, &maxsplit); err != nil { 1871 return nil, err 1872 } 1873 1874 var res []string 1875 1876 if sep_ == nil || sep_ == None { 1877 // special case: split on whitespace 1878 if maxsplit < 0 { 1879 res = strings.Fields(recv) 1880 } else if b.Name() == "split" { 1881 res = splitspace(recv, maxsplit) 1882 } else { // rsplit 1883 res = rsplitspace(recv, maxsplit) 1884 } 1885 1886 } else if sep, ok := AsString(sep_); ok { 1887 if sep == "" { 1888 return nil, fmt.Errorf("split: empty separator") 1889 } 1890 // usual case: split on non-empty separator 1891 if maxsplit < 0 { 1892 res = strings.Split(recv, sep) 1893 } else if b.Name() == "split" { 1894 res = strings.SplitN(recv, sep, maxsplit+1) 1895 } else { // rsplit 1896 res = strings.Split(recv, sep) 1897 if excess := len(res) - maxsplit; excess > 0 { 1898 res[0] = strings.Join(res[:excess], sep) 1899 res = append(res[:1], res[excess:]...) 1900 } 1901 } 1902 1903 } else { 1904 return nil, fmt.Errorf("split: got %s for separator, want string", sep_.Type()) 1905 } 1906 1907 list := make([]Value, len(res)) 1908 for i, x := range res { 1909 list[i] = String(x) 1910 } 1911 return NewList(list), nil 1912} 1913 1914// Precondition: max >= 0. 1915func rsplitspace(s string, max int) []string { 1916 res := make([]string, 0, max+1) 1917 end := -1 // index of field end, or -1 in a region of spaces. 1918 for i := len(s); i > 0; { 1919 r, sz := utf8.DecodeLastRuneInString(s[:i]) 1920 if unicode.IsSpace(r) { 1921 if end >= 0 { 1922 if len(res) == max { 1923 break // let this field run to the start 1924 } 1925 res = append(res, s[i:end]) 1926 end = -1 1927 } 1928 } else if end < 0 { 1929 end = i 1930 } 1931 i -= sz 1932 } 1933 if end >= 0 { 1934 res = append(res, s[:end]) 1935 } 1936 1937 resLen := len(res) 1938 for i := 0; i < resLen/2; i++ { 1939 res[i], res[resLen-1-i] = res[resLen-1-i], res[i] 1940 } 1941 1942 return res 1943} 1944 1945// Precondition: max >= 0. 1946func splitspace(s string, max int) []string { 1947 var res []string 1948 start := -1 // index of field start, or -1 in a region of spaces 1949 for i, r := range s { 1950 if unicode.IsSpace(r) { 1951 if start >= 0 { 1952 if len(res) == max { 1953 break // let this field run to the end 1954 } 1955 res = append(res, s[start:i]) 1956 start = -1 1957 } 1958 } else if start == -1 { 1959 start = i 1960 } 1961 } 1962 if start >= 0 { 1963 res = append(res, s[start:]) 1964 } 1965 return res 1966} 1967 1968// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·splitlines 1969func string_splitlines(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1970 var keepends bool 1971 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0, &keepends); err != nil { 1972 return nil, err 1973 } 1974 var lines []string 1975 if s := string(b.Receiver().(String)); s != "" { 1976 // TODO(adonovan): handle CRLF correctly. 1977 if keepends { 1978 lines = strings.SplitAfter(s, "\n") 1979 } else { 1980 lines = strings.Split(s, "\n") 1981 } 1982 if strings.HasSuffix(s, "\n") { 1983 lines = lines[:len(lines)-1] 1984 } 1985 } 1986 list := make([]Value, len(lines)) 1987 for i, x := range lines { 1988 list[i] = String(x) 1989 } 1990 return NewList(list), nil 1991} 1992 1993// https://github.com/google/starlark-go/blob/master/doc/spec.md#set·union. 1994func set_union(b *Builtin, args Tuple, kwargs []Tuple) (Value, error) { 1995 var iterable Iterable 1996 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 0, &iterable); err != nil { 1997 return nil, err 1998 } 1999 iter := iterable.Iterate() 2000 defer iter.Done() 2001 union, err := b.Receiver().(*Set).Union(iter) 2002 if err != nil { 2003 return nil, nameErr(b, err) 2004 } 2005 return union, nil 2006} 2007 2008// Common implementation of string_{r}{find,index}. 2009func string_find_impl(b *Builtin, args Tuple, kwargs []Tuple, allowError, last bool) (Value, error) { 2010 var sub string 2011 var start_, end_ Value 2012 if err := UnpackPositionalArgs(b.Name(), args, kwargs, 1, &sub, &start_, &end_); err != nil { 2013 return nil, err 2014 } 2015 2016 s := string(b.Receiver().(String)) 2017 start, end, err := indices(start_, end_, len(s)) 2018 if err != nil { 2019 return nil, nameErr(b, err) 2020 } 2021 var slice string 2022 if start < end { 2023 slice = s[start:end] 2024 } 2025 2026 var i int 2027 if last { 2028 i = strings.LastIndex(slice, sub) 2029 } else { 2030 i = strings.Index(slice, sub) 2031 } 2032 if i < 0 { 2033 if !allowError { 2034 return nil, nameErr(b, "substring not found") 2035 } 2036 return MakeInt(-1), nil 2037 } 2038 return MakeInt(i + start), nil 2039} 2040 2041// Common implementation of builtin dict function and dict.update method. 2042// Precondition: len(updates) == 0 or 1. 2043func updateDict(dict *Dict, updates Tuple, kwargs []Tuple) error { 2044 if len(updates) == 1 { 2045 switch updates := updates[0].(type) { 2046 case IterableMapping: 2047 // Iterate over dict's key/value pairs, not just keys. 2048 for _, item := range updates.Items() { 2049 if err := dict.SetKey(item[0], item[1]); err != nil { 2050 return err // dict is frozen 2051 } 2052 } 2053 default: 2054 // all other sequences 2055 iter := Iterate(updates) 2056 if iter == nil { 2057 return fmt.Errorf("got %s, want iterable", updates.Type()) 2058 } 2059 defer iter.Done() 2060 var pair Value 2061 for i := 0; iter.Next(&pair); i++ { 2062 iter2 := Iterate(pair) 2063 if iter2 == nil { 2064 return fmt.Errorf("dictionary update sequence element #%d is not iterable (%s)", i, pair.Type()) 2065 2066 } 2067 defer iter2.Done() 2068 len := Len(pair) 2069 if len < 0 { 2070 return fmt.Errorf("dictionary update sequence element #%d has unknown length (%s)", i, pair.Type()) 2071 } else if len != 2 { 2072 return fmt.Errorf("dictionary update sequence element #%d has length %d, want 2", i, len) 2073 } 2074 var k, v Value 2075 iter2.Next(&k) 2076 iter2.Next(&v) 2077 if err := dict.SetKey(k, v); err != nil { 2078 return err 2079 } 2080 } 2081 } 2082 } 2083 2084 // Then add the kwargs. 2085 before := dict.Len() 2086 for _, pair := range kwargs { 2087 if err := dict.SetKey(pair[0], pair[1]); err != nil { 2088 return err // dict is frozen 2089 } 2090 } 2091 // In the common case, each kwarg will add another dict entry. 2092 // If that's not so, check whether it is because there was a duplicate kwarg. 2093 if dict.Len() < before+len(kwargs) { 2094 keys := make(map[String]bool, len(kwargs)) 2095 for _, kv := range kwargs { 2096 k := kv[0].(String) 2097 if keys[k] { 2098 return fmt.Errorf("duplicate keyword arg: %v", k) 2099 } 2100 keys[k] = true 2101 } 2102 } 2103 2104 return nil 2105} 2106 2107// nameErr returns an error message of the form "name: msg" 2108// where name is b.Name() and msg is a string or error. 2109func nameErr(b *Builtin, msg interface{}) error { 2110 return fmt.Errorf("%s: %v", b.Name(), msg) 2111} 2112