Source file src/go.starlark.net/starlark/library.go

Documentation: go.starlark.net/starlark

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

View as plain text