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

View as plain text