Repository: google/starlark-go
Pull request #397 (2022-02-16 16:00:24)

Add dict|dict and dict|=dict
This change adds support for the `x | y` operation (ordered union) in dictionaries and the in-place `x |= y` statement, in which the resulting value of x aliases the original, which is mutated.

Spec change:  https://github.com/bazelbuild/starlark/pull/215
Java change: https://github.com/bazelbuild/bazel/pull/14540


Patch:
diff --git a/README.md b/README.md
index fb11a02..5eafad9 100644
--- a/README.md
+++ b/README.md
@@ -53,7 +53,7 @@ Build the code:
 ```shell
 # check out the code and dependencies,
 # and install interpreter in $GOPATH/bin
-$ go get -u go.starlark.net/cmd/starlark
+$ go install go.starlark.net/cmd/starlark@latest
 ```
 
 Run the interpreter:
diff --git a/doc/spec.md b/doc/spec.md
index 0728589..90afccc 100644
--- a/doc/spec.md
+++ b/doc/spec.md
@@ -175,6 +175,8 @@ reproducibility is paramount, such as build tools.
     * [string·lower](#string·lower)
     * [string·lstrip](#string·lstrip)
     * [string·partition](#string·partition)
+    * [string·removeprefix](#string·removeprefix)
+    * [string·removesuffix](#string·removesuffix)
     * [string·replace](#string·replace)
     * [string·rfind](#string·rfind)
     * [string·rindex](#string·rindex)
@@ -680,6 +682,8 @@ Strings have several built-in methods:
 * [`lstrip`](#string·lstrip)
 * [`partition`](#string·partition)
 * [`replace`](#string·replace)
+* [`removeprefix`](#string·removeprefix)
+* [`removesuffix`](#string·removesuffix)
 * [`rfind`](#string·rfind)
 * [`rindex`](#string·rindex)
 * [`rpartition`](#string·rpartition)
@@ -902,6 +906,20 @@ fail.
 A dictionary used in a Boolean context is considered true if it is
 non-empty.
 
+The binary `|` operation may be applied to two dictionaries.
+It yields a new dictionary whose set of keys is the union of the sets
+of keys of the two operands. The corresponding values are taken from
+the operands, where the value taken from the right operand takes
+precedence if both contain a given key.  Iterating over the keys in
+the resulting dictionary first yields all keys in the left operand in
+insertion order, then all keys in the right operand that were not
+present in the left operand, again in insertion order.
+
+There is also an augmented assignment version of the `|` operation.
+For two dictionaries `x` and `y`, the statement `x |= y` behaves
+similar to `x = x | y`, but updates `x` in place rather than assigning
+a new dictionary to it.
+
 Dictionaries may be compared for equality using `==` and `!=`.  Two
 dictionaries compare equal if they contain the same number of items
 and each key/value item (k, v) found in one dictionary is also present
@@ -2014,6 +2032,9 @@ Sets
       int & int                 # bitwise intersection (AND)
       set & set                 # set intersection
       set ^ set                 # set symmetric difference
+
+Dict
+      dict | dict               # ordered union
 ```
 
 The operands of the arithmetic operators `+`, `-`, `*`, `//`, and
@@ -2052,10 +2073,14 @@ For sets, it yields a new set containing the intersection of the
 elements of the operand sets, preserving the element order of the left
 operand.
 
-The `|` operator likewise computes bitwise or set unions.
+The `|` operator likewise computes bitwise, set, or dict unions.
 The result of `set | set` is a new set whose elements are the
 union of the operands, preserving the order of the elements of the
 operands, left before right.
+Similarly, the result of `dict | dict` is a new dict whose entries are
+the union of the operands, preserving the order in which keys first
+appear, but using the value from the right operand for each key
+common to both dicts.
 
 The `^` operator accepts operands of either `int` or `set` type.
 For integers, it yields the bitwise XOR (exclusive OR) of its operands.
@@ -2578,7 +2603,7 @@ m.f = ""
 
 Compound targets may consist of a comma-separated list of
 subtargets, optionally surrounded by parentheses or square brackets,
-and targets may be nested arbitarily in this way.
+and targets may be nested arbitrarily in this way.
 An assignment to a compound target checks that the right-hand value is a
 sequence with the same number of elements as the target.
 Each element of the sequence is then assigned to the corresponding
@@ -3193,7 +3218,7 @@ specified base, decimal by default.
 If `base` is zero, x is interpreted like an integer literal, the base
 being inferred from an optional base prefix such as `0b`, `0o`, or
 `0x` preceding the first digit.
-When the `base` is provided explictly, a matching base prefix is
+When the `base` is provided explicitly, a matching base prefix is
 also permitted, and has no effect.
 Irrespective of base, the string may start with an optional `+` or `-`
 sign indicating the sign of the result.
@@ -4026,6 +4051,30 @@ If S does not contain `x`, `partition` returns `(S, "", "")`.
 "one/two/three".partition("/")		# ("one", "/", "two/three")
 ```
 
+<a id='string·removeprefix'></a>
+### string·removeprefix
+
+`S.removeprefix(prefix)` returns a copy of string S with the prefix `prefix`
+removed if S starts with `prefix`, otherwise it returns S.
+
+```python
+"banana".removeprefix("ban")          # "ana"
+"banana".removeprefix("foo")          # "banana"
+"foofoobar".removeprefix("foo")       # "foobar"
+```
+
+<a id='string·removesuffix'></a>
+### string·removesuffix
+
+`S.removesuffix(suffix)` returns a copy of string S with the suffix `suffix`
+removed if S ends with `suffix`, otherwise it returns S.
+
+```python
+"banana".removesuffix("nana")         # "ba"
+"banana".removesuffix("foo")          # "banana"
+"banana".removesuffix("na")           # "bana"
+```
+
 <a id='string·replace'></a>
 ### string·replace
 
diff --git a/go.mod b/go.mod
index d14060e..ae5f371 100644
--- a/go.mod
+++ b/go.mod
@@ -7,7 +7,7 @@ require (
 	github.com/chzyer/readline v0.0.0-20180603132655-2972be24d48e
 	github.com/chzyer/test v0.0.0-20180213035817-a1ea475d72b1 // indirect
 	github.com/google/go-cmp v0.5.1 // indirect
-	golang.org/x/sys v0.0.0-20200930185726-fdedc70b468f
+	golang.org/x/sys v0.0.0-20220811171246-fbc7d0a398ab
 	golang.org/x/xerrors v0.0.0-20200804184101-5ec99f83aff1 // indirect
 	google.golang.org/protobuf v1.25.0
 )
diff --git a/go.sum b/go.sum
index 90a8048..62e9fda 100644
--- a/go.sum
+++ b/go.sum
@@ -43,8 +43,8 @@ golang.org/x/sync v0.0.0-20181108010431-42b317875d0f/go.mod h1:RxMgew5VJxzue5/jJ
 golang.org/x/sync v0.0.0-20190423024810-112230192c58/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
 golang.org/x/sys v0.0.0-20180830151530-49385e6e1522/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
 golang.org/x/sys v0.0.0-20190215142949-d0b11bdaac8a/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
-golang.org/x/sys v0.0.0-20200930185726-fdedc70b468f h1:+Nyd8tzPX9R7BWHguqsrbFdRx3WQ/1ib8I44HXV5yTA=
-golang.org/x/sys v0.0.0-20200930185726-fdedc70b468f/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
+golang.org/x/sys v0.0.0-20220811171246-fbc7d0a398ab h1:2QkjZIsXupsJbJIdSjjUOgWK3aEtzyuh2mPt3l/CkeU=
+golang.org/x/sys v0.0.0-20220811171246-fbc7d0a398ab/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
 golang.org/x/text v0.3.0/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
 golang.org/x/tools v0.0.0-20190114222345-bf090417da8b/go.mod h1:n7NCudcB/nEzxVGmLbDWY5pfWTLqBcC2KZ6jyYvM4mQ=
 golang.org/x/tools v0.0.0-20190226205152-f727befe758c/go.mod h1:9Yl7xja0Znq3iFh3HoIrodX9oNMXvdceNzlUR8zjMvY=
diff --git a/internal/compile/compile.go b/internal/compile/compile.go
index c314e6e..888d95c 100644
--- a/internal/compile/compile.go
+++ b/internal/compile/compile.go
@@ -47,7 +47,7 @@ var Disassemble = false
 const debug = false // make code generation verbose, for debugging the compiler
 
 // Increment this to force recompilation of saved bytecode files.
-const Version = 12
+const Version = 13
 
 type Opcode uint8
 
@@ -100,18 +100,19 @@ const (
 	FALSE     // - FALSE False
 	MANDATORY // - MANDATORY Mandatory	     [sentinel value for required kwonly args]
 
-	ITERPUSH    //       iterable ITERPUSH    -  [pushes the iterator stack]
-	ITERPOP     //              - ITERPOP     -    [pops the iterator stack]
-	NOT         //          value NOT         bool
-	RETURN      //          value RETURN      -
-	SETINDEX    //        a i new SETINDEX    -
-	INDEX       //            a i INDEX       elem
-	SETDICT     // dict key value SETDICT     -
-	SETDICTUNIQ // dict key value SETDICTUNIQ -
-	APPEND      //      list elem APPEND      -
-	SLICE       //   x lo hi step SLICE       slice
-	INPLACE_ADD //            x y INPLACE_ADD z      where z is x+y or x.extend(y)
-	MAKEDICT    //              - MAKEDICT    dict
+	ITERPUSH     //       iterable ITERPUSH     -  [pushes the iterator stack]
+	ITERPOP      //              - ITERPOP      -    [pops the iterator stack]
+	NOT          //          value NOT          bool
+	RETURN       //          value RETURN       -
+	SETINDEX     //        a i new SETINDEX     -
+	INDEX        //            a i INDEX        elem
+	SETDICT      // dict key value SETDICT      -
+	SETDICTUNIQ  // dict key value SETDICTUNIQ  -
+	APPEND       //      list elem APPEND       -
+	SLICE        //   x lo hi step SLICE        slice
+	INPLACE_ADD  //            x y INPLACE_ADD  z      where z is x+y or x.extend(y)
+	INPLACE_PIPE //            x y INPLACE_PIPE z      where z is x|y
+	MAKEDICT     //              - MAKEDICT     dict
 
 	// --- opcodes with an argument must go below this line ---
 
@@ -177,6 +178,7 @@ var opcodeNames = [...]string{
 	IN:           "in",
 	INDEX:        "index",
 	INPLACE_ADD:  "inplace_add",
+	INPLACE_PIPE: "inplace_pipe",
 	ITERJMP:      "iterjmp",
 	ITERPOP:      "iterpop",
 	ITERPUSH:     "iterpush",
@@ -250,6 +252,7 @@ var stackEffect = [...]int8{
 	IN:           -1,
 	INDEX:        -1,
 	INPLACE_ADD:  -1,
+	INPLACE_PIPE: -1,
 	ITERJMP:      variableStackEffect,
 	ITERPOP:      0,
 	ITERPUSH:     -1,
@@ -1145,11 +1148,16 @@ func (fcomp *fcomp) stmt(stmt syntax.Stmt) {
 
 			fcomp.expr(stmt.RHS)
 
-			if stmt.Op == syntax.PLUS_EQ {
-				// Allow the runtime to optimize list += iterable.
+			// In-place x+=y and x|=y have special semantics:
+			// the resulting x aliases the original x.
+			switch stmt.Op {
+			case syntax.PLUS_EQ:
 				fcomp.setPos(stmt.OpPos)
 				fcomp.emit(INPLACE_ADD)
-			} else {
+			case syntax.PIPE_EQ:
+				fcomp.setPos(stmt.OpPos)
+				fcomp.emit(INPLACE_PIPE)
+			default:
 				fcomp.binop(stmt.OpPos, stmt.Op-syntax.PLUS_EQ+syntax.PLUS)
 			}
 			set()
diff --git a/starlark/eval.go b/starlark/eval.go
index d0ad91f..4941d44 100644
--- a/starlark/eval.go
+++ b/starlark/eval.go
@@ -47,6 +47,10 @@ type Thread struct {
 	// See example_test.go for some example implementations of Load.
 	Load func(thread *Thread, module string) (StringDict, error)
 
+	// OnMaxSteps is called when the thread reaches the limit set by SetMaxExecutionSteps.
+	// The default behavior is to call thread.Cancel("too many steps").
+	OnMaxSteps func(thread *Thread)
+
 	// steps counts abstract computation steps executed by this thread.
 	steps, maxSteps uint64
 
@@ -74,7 +78,8 @@ func (thread *Thread) ExecutionSteps() uint64 {
 // SetMaxExecutionSteps sets a limit on the number of Starlark
 // computation steps that may be executed by this thread. If the
 // thread's step counter exceeds this limit, the interpreter calls
-// thread.Cancel("too many steps").
+// the optional OnMaxSteps function or the default behavior
+// of calling thread.Cancel("too many steps").
 func (thread *Thread) SetMaxExecutionSteps(max uint64) {
 	thread.maxSteps = max
 }
@@ -1031,6 +1036,12 @@ func Binary(op syntax.Token, x, y Value) (Value, error) {
 			if y, ok := y.(Int); ok {
 				return x.Or(y), nil
 			}
+
+		case *Dict: // union
+			if y, ok := y.(*Dict); ok {
+				return x.Union(y), nil
+			}
+
 		case *Set: // union
 			if y, ok := y.(*Set); ok {
 				iter := Iterate(y)
diff --git a/starlark/hashtable.go b/starlark/hashtable.go
index 27990b5..9fab60e 100644
--- a/starlark/hashtable.go
+++ b/starlark/hashtable.go
@@ -12,6 +12,8 @@ import (
 // hashtable is used to represent Starlark dict and set values.
 // It is a hash table whose key/value entries form a doubly-linked list
 // in the order the entries were inserted.
+//
+// Initialized instances of hashtable must not be copied.
 type hashtable struct {
 	table     []bucket  // len is zero or a power of two
 	bucket0   [1]bucket // inline allocation for small maps.
@@ -20,8 +22,17 @@ type hashtable struct {
 	head      *entry  // insertion order doubly-linked list; may be nil
 	tailLink  **entry // address of nil link at end of list (perhaps &head)
 	frozen    bool
+
+	_ noCopy // triggers vet copylock check on this type.
 }
 
+// noCopy is zero-sized type that triggers vet's copylock check.
+// See https://github.com/golang/go/issues/8005#issuecomment-190753527.
+type noCopy struct{}
+
+func (*noCopy) Lock()   {}
+func (*noCopy) Unlock() {}
+
 const bucketSize = 8
 
 type bucket struct {
@@ -70,11 +81,8 @@ func (ht *hashtable) freeze() {
 }
 
 func (ht *hashtable) insert(k, v Value) error {
-	if ht.frozen {
-		return fmt.Errorf("cannot insert into frozen hash table")
-	}
-	if ht.itercount > 0 {
-		return fmt.Errorf("cannot insert into hash table during iteration")
+	if err := ht.checkMutable("insert into"); err != nil {
+		return err
 	}
 	if ht.table == nil {
 		ht.init(1)
@@ -230,11 +238,8 @@ func (ht *hashtable) keys() []Value {
 }
 
 func (ht *hashtable) delete(k Value) (v Value, found bool, err error) {
-	if ht.frozen {
-		return nil, false, fmt.Errorf("cannot delete from frozen hash table")
-	}
-	if ht.itercount > 0 {
-		return nil, false, fmt.Errorf("cannot delete from hash table during iteration")
+	if err := ht.checkMutable("delete from"); err != nil {
+		return nil, false, err
 	}
 	if ht.table == nil {
 		return None, false, nil // empty
@@ -277,12 +282,21 @@ func (ht *hashtable) delete(k Value) (v Value, found bool, err error) {
 	return None, false, nil // not found
 }
 
-func (ht *hashtable) clear() error {
+// checkMutable reports an error if the hash table should not be mutated.
+// verb+" dict" should describe the operation.
+func (ht *hashtable) checkMutable(verb string) error {
 	if ht.frozen {
-		return fmt.Errorf("cannot clear frozen hash table")
+		return fmt.Errorf("cannot %s frozen hash table", verb)
 	}
 	if ht.itercount > 0 {
-		return fmt.Errorf("cannot clear hash table during iteration")
+		return fmt.Errorf("cannot %s hash table during iteration", verb)
+	}
+	return nil
+}
+
+func (ht *hashtable) clear() error {
+	if err := ht.checkMutable("clear"); err != nil {
+		return err
 	}
 	if ht.table != nil {
 		for i := range ht.table {
@@ -295,6 +309,15 @@ func (ht *hashtable) clear() error {
 	return nil
 }
 
+func (ht *hashtable) addAll(other *hashtable) error {
+	for e := other.head; e != nil; e = e.next {
+		if err := ht.insert(e.key, e.value); err != nil {
+			return err
+		}
+	}
+	return nil
+}
+
 // dump is provided as an aid to debugging.
 func (ht *hashtable) dump() {
 	fmt.Printf("hashtable %p len=%d head=%p tailLink=%p",
diff --git a/starlark/int.go b/starlark/int.go
index e6dee14..398811b 100644
--- a/starlark/int.go
+++ b/starlark/int.go
@@ -46,13 +46,18 @@ func MakeUint64(x uint64) Int {
 // MakeBigInt returns a Starlark int for the specified big.Int.
 // The new Int value will contain a copy of x. The caller is safe to modify x.
 func MakeBigInt(x *big.Int) Int {
-	if n := x.BitLen(); n < 32 || n == 32 && x.Int64() == math.MinInt32 {
+	if isSmall(x) {
 		return makeSmallInt(x.Int64())
 	}
 	z := new(big.Int).Set(x)
 	return makeBigInt(z)
 }
 
+func isSmall(x *big.Int) bool {
+	n := x.BitLen()
+	return n < 32 || n == 32 && x.Int64() == math.MinInt32
+}
+
 var (
 	zero, one = makeSmallInt(0), makeSmallInt(1)
 	oneBig    = big.NewInt(1)
diff --git a/starlark/int_generic.go b/starlark/int_generic.go
index b0d2f14..f2adf45 100644
--- a/starlark/int_generic.go
+++ b/starlark/int_generic.go
@@ -1,4 +1,5 @@
-//+build !linux,!darwin,!dragonfly,!freebsd,!netbsd,!solaris darwin,arm64 !amd64,!arm64,!mips64x,!ppc64x
+//go:build (!linux && !darwin && !dragonfly && !freebsd && !netbsd && !solaris) || (!amd64 && !arm64 && !mips64x && !ppc64x && !loong64)
+// +build !linux,!darwin,!dragonfly,!freebsd,!netbsd,!solaris !amd64,!arm64,!mips64x,!ppc64x,!loong64
 
 package starlark
 
diff --git a/starlark/int_posix64.go b/starlark/int_posix64.go
index 000fc86..2ab0bed 100644
--- a/starlark/int_posix64.go
+++ b/starlark/int_posix64.go
@@ -1,5 +1,6 @@
-//+build linux darwin dragonfly freebsd netbsd solaris
-//+build amd64 arm64,!darwin mips64x ppc64x
+//go:build (linux || darwin || dragonfly || freebsd || netbsd || solaris) && (amd64 || arm64 || mips64x || ppc64x || loong64)
+// +build linux darwin dragonfly freebsd netbsd solaris
+// +build amd64 arm64 mips64x ppc64x loong64
 
 package starlark
 
@@ -10,16 +11,12 @@ package starlark
 // values be represented as an unsafe.Pointer, so that Int-to-Value
 // interface conversion need not allocate.
 
-// Although iOS (arm64,darwin) claims to be a POSIX-compliant,
-// it limits each process to about 700MB of virtual address space,
-// which defeats the optimization.
-//
-// TODO(golang.org/issue/38485): darwin,arm64 may refer to macOS in the future.
-// Update this when there are distinct GOOS values for macOS, iOS, and other Apple
-// operating systems on arm64.
-//
-// This optimization is disabled on OpenBSD, because its default
-// ulimit for virtual memory is a measly GB or so.
+// Although iOS (which, like macOS, appears as darwin/arm64) is
+// POSIX-compliant, it limits each process to about 700MB of virtual
+// address space, which defeats the optimization.  Similarly,
+// OpenBSD's default ulimit for virtual memory is a measly GB or so.
+// On both those platforms the attempted optimization will fail and
+// fall back to the slow implementation.
 
 // An alternative approach to this optimization would be to embed the
 // int32 values in pointers using odd values, which can be distinguished
@@ -41,15 +38,24 @@ import (
 // so that Int-to-Value conversions need not allocate.
 //
 // The pointer is either a *big.Int, if the value is big, or a pointer into a
-// reserved portion of the address space (smallints), if the value is small.
+// reserved portion of the address space (smallints), if the value is small
+// and the address space allocation succeeded.
 //
 // See int_generic.go for the basic representation concepts.
 type intImpl unsafe.Pointer
 
 // get returns the (small, big) arms of the union.
 func (i Int) get() (int64, *big.Int) {
-	ptr := uintptr(i.impl)
-	if ptr >= smallints && ptr < smallints+1<<32 {
+	if smallints == 0 {
+		// optimization disabled
+		if x := (*big.Int)(i.impl); isSmall(x) {
+			return x.Int64(), nil
+		} else {
+			return 0, x
+		}
+	}
+
+	if ptr := uintptr(i.impl); ptr >= smallints && ptr < smallints+1<<32 {
 		return math.MinInt32 + int64(ptr-smallints), nil
 	}
 	return 0, (*big.Int)(i.impl)
@@ -57,6 +63,11 @@ func (i Int) get() (int64, *big.Int) {
 
 // Precondition: math.MinInt32 <= x && x <= math.MaxInt32
 func makeSmallInt(x int64) Int {
+	if smallints == 0 {
+		// optimization disabled
+		return Int{intImpl(big.NewInt(x))}
+	}
+
 	return Int{intImpl(uintptr(x-math.MinInt32) + smallints)}
 }
 
@@ -66,12 +77,15 @@ func makeBigInt(x *big.Int) Int { return Int{intImpl(x)} }
 // smallints is the base address of a 2^32 byte memory region.
 // Pointers to addresses in this region represent int32 values.
 // We assume smallints is not at the very top of the address space.
+//
+// Zero means the optimization is disabled and all Ints allocate a big.Int.
 var smallints = reserveAddresses(1 << 32)
 
 func reserveAddresses(len int) uintptr {
 	b, err := unix.Mmap(-1, 0, len, unix.PROT_READ, unix.MAP_PRIVATE|unix.MAP_ANON)
 	if err != nil {
-		log.Fatalf("mmap: %v", err)
+		log.Printf("Starlark failed to allocate 4GB address space: %v. Integer performance may suffer.", err)
+		return 0 // optimization disabled
 	}
 	return uintptr(unsafe.Pointer(&b[0]))
 }
diff --git a/starlark/interp.go b/starlark/interp.go
index 642d8f5..9961e2f 100644
--- a/starlark/interp.go
+++ b/starlark/interp.go
@@ -89,7 +89,11 @@ loop:
 	for {
 		thread.steps++
 		if thread.steps >= thread.maxSteps {
-			thread.Cancel("too many steps")
+			if thread.OnMaxSteps != nil {
+				thread.OnMaxSteps(thread)
+			} else {
+				thread.Cancel("too many steps")
+			}
 		}
 		if reason := atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&thread.cancelReason))); reason != nil {
 			err = fmt.Errorf("Starlark computation cancelled: %s", *(*string)(reason))
@@ -220,6 +224,34 @@ loop:
 			stack[sp] = z
 			sp++
 
+		case compile.INPLACE_PIPE:
+			y := stack[sp-1]
+			x := stack[sp-2]
+			sp -= 2
+
+			// It's possible that y is not Dict but
+			// nonetheless defines x|y, in which case we
+			// should fall back to the general case.
+			var z Value
+			if xdict, ok := x.(*Dict); ok {
+				if ydict, ok := y.(*Dict); ok {
+					if err = xdict.ht.checkMutable("apply |= to"); err != nil {
+						break loop
+					}
+					xdict.ht.addAll(&ydict.ht) // can't fail
+					z = xdict
+				}
+			}
+			if z == nil {
+				z, err = Binary(syntax.PIPE, x, y)
+				if err != nil {
+					break loop
+				}
+			}
+
+			stack[sp] = z
+			sp++
+
 		case compile.NONE:
 			stack[sp] = None
 			sp++
diff --git a/starlark/library.go b/starlark/library.go
index cb2c820..1c801be 100644
--- a/starlark/library.go
+++ b/starlark/library.go
@@ -123,6 +123,8 @@ var (
 		"lower":          NewBuiltin("lower", string_lower),
 		"lstrip":         NewBuiltin("lstrip", string_strip), // sic
 		"partition":      NewBuiltin("partition", string_partition),
+		"removeprefix":   NewBuiltin("removeprefix", string_removefix),
+		"removesuffix":   NewBuiltin("removesuffix", string_removefix),
 		"replace":        NewBuiltin("replace", string_replace),
 		"rfind":          NewBuiltin("rfind", string_rfind),
 		"rindex":         NewBuiltin("rindex", string_rindex),
@@ -1889,6 +1891,22 @@ func string_partition(_ *Thread, b *Builtin, args Tuple, kwargs []Tuple) (Value,
 	return tuple, nil
 }
 
+// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·removeprefix
+// https://github.com/google/starlark-go/blob/master/doc/spec.md#string·removesuffix
+func string_removefix(_ *Thread, b *Builtin, args Tuple, kwargs []Tuple) (Value, error) {
+	recv := string(b.Receiver().(String))
+	var fix string
+	if err := UnpackPositionalArgs(b.Name(), args, kwargs, 1, &fix); err != nil {
+		return nil, err
+	}
+	if b.name[len("remove")] == 'p' {
+		recv = strings.TrimPrefix(recv, fix)
+	} else {
+		recv = strings.TrimSuffix(recv, fix)
+	}
+	return String(recv), nil
+}
+
 // https://github.com/google/starlark-go/blob/master/doc/spec.md#string·replace
 func string_replace(_ *Thread, b *Builtin, args Tuple, kwargs []Tuple) (Value, error) {
 	recv := string(b.Receiver().(String))
diff --git a/starlark/value.go b/starlark/value.go
index 8cd5967..b51d4ca 100644
--- a/starlark/value.go
+++ b/starlark/value.go
@@ -795,6 +795,14 @@ func (d *Dict) Freeze()                                         { d.ht.freeze()
 func (d *Dict) Truth() Bool                                     { return d.Len() > 0 }
 func (d *Dict) Hash() (uint32, error)                           { return 0, fmt.Errorf("unhashable type: dict") }
 
+func (x *Dict) Union(y *Dict) *Dict {
+	z := new(Dict)
+	z.ht.init(x.Len()) // a lower bound
+	z.ht.addAll(&x.ht) // can't fail
+	z.ht.addAll(&y.ht) // can't fail
+	return z
+}
+
 func (d *Dict) Attr(name string) (Value, error) { return builtinAttr(d, name, dictMethods) }
 func (d *Dict) AttrNames() []string             { return builtinAttrNames(dictMethods) }
 
@@ -816,8 +824,8 @@ func dictsEqual(x, y *Dict, depth int) (bool, error) {
 	if x.Len() != y.Len() {
 		return false, nil
 	}
-	for _, xitem := range x.Items() {
-		key, xval := xitem[0], xitem[1]
+	for e := x.ht.head; e != nil; e = e.next {
+		key, xval := e.key, e.value
 
 		if yval, found, _ := y.Get(key); !found {
 			return false, nil
@@ -1185,8 +1193,8 @@ func writeValue(out *strings.Builder, x Value, path []Value) {
 			out.WriteString("...") // dict contains itself
 		} else {
 			sep := ""
-			for _, item := range x.Items() {
-				k, v := item[0], item[1]
+			for e := x.ht.head; e != nil; e = e.next {
+				k, v := e.key, e.value
 				out.WriteString(sep)
 				writeValue(out, k, path)
 				out.WriteString(": ")
diff --git a/starlarkjson/json.go b/starlarkjson/json.go
index 07852f0..6579c7e 100644
--- a/starlarkjson/json.go
+++ b/starlarkjson/json.go
@@ -12,5 +12,5 @@ import (
 	"go.starlark.net/lib/json"
 )
 
-// Module is an alias of json.Module for backwards import compatibilty
+// Module is an alias of json.Module for backwards import compatibility
 var Module = json.Module


Test patch:
diff --git a/.github/workflows/tests.yml b/.github/workflows/tests.yml
index 4944036..893cc11 100644
--- a/.github/workflows/tests.yml
+++ b/.github/workflows/tests.yml
@@ -5,7 +5,7 @@ jobs:
     strategy:
       matrix:
         os: [ubuntu-latest, macos-latest, windows-latest]
-        go-version: [1.16.x, 1.17.x]
+        go-version: [1.18.x, 1.19.x]
     runs-on: ${{ matrix.os }}
     steps:
       - name: Install Go
diff --git a/starlark/bench_test.go b/starlark/bench_test.go
index 7cfefe0..e62cf59 100644
--- a/starlark/bench_test.go
+++ b/starlark/bench_test.go
@@ -16,7 +16,7 @@ import (
 	"go.starlark.net/starlarktest"
 )
 
-func Benchmark(b *testing.B) {
+func BenchmarkStarlark(b *testing.B) {
 	defer setOptions("")
 
 	testdata := starlarktest.DataFile("starlark", ".")
diff --git a/starlark/int_test.go b/starlark/int_test.go
index ad1bf92..8c20a31 100644
--- a/starlark/int_test.go
+++ b/starlark/int_test.go
@@ -5,9 +5,15 @@
 package starlark
 
 import (
+	"flag"
 	"fmt"
+	"log"
 	"math"
 	"math/big"
+	"os"
+	"os/exec"
+	"runtime"
+	"strings"
 	"testing"
 )
 
@@ -100,3 +106,50 @@ func TestImmutabilityBigInt(t *testing.T) {
 		}
 	}
 }
+
+// TestIntFallback creates a small Int value in a child process with
+// limited address space to ensure that it still works, but prints a warning.
+func TestIntFallback(t *testing.T) {
+	if runtime.GOOS != "linux" {
+		t.Skipf("test disabled on this platform (requires ulimit -v)")
+	}
+	exe, err := os.Executable()
+	if err != nil {
+		t.Fatalf("can't find file name of executable: %v", err)
+	}
+	// ulimit -v limits the address space in KB. Not portable.
+	// 1GB is enough for the Go runtime but not for the optimization.
+	cmd := exec.Command("/bin/sh", "-c", fmt.Sprintf("ulimit -v 1000000 && %q --entry=intfallback", exe))
+	out, err := cmd.CombinedOutput()
+	if err != nil {
+		t.Fatalf("intfallback subcommand failed: %v\n%s", err, out)
+	}
+
+	// Check the warning was printed.
+	if !strings.Contains(string(out), "Integer performance may suffer") {
+		t.Errorf("expected warning was not printed. Output=<<%s>>", out)
+	}
+}
+
+// intfallback is called in a child process with limited address space.
+func intfallback() {
+	const want = 123
+	if got, _ := MakeBigInt(big.NewInt(want)).Int64(); got != want {
+		log.Fatalf("intfallback: got %d, want %d", got, want)
+	}
+}
+
+// The --entry flag invokes an alternate entry point, for use in subprocess tests.
+func TestMain(m *testing.M) {
+	var entry string
+	flag.StringVar(&entry, "entry", "", "child process entry-point")
+	flag.Parse()
+	switch entry {
+	case "":
+		os.Exit(m.Run()) // normal case
+	case "intfallback":
+		intfallback()
+	default:
+		log.Fatalf("unknown entry point: %s", entry)
+	}
+}
diff --git a/starlark/testdata/benchmark.star b/starlark/testdata/benchmark.star
index b02868d..79614f0 100644
--- a/starlark/testdata/benchmark.star
+++ b/starlark/testdata/benchmark.star
@@ -60,3 +60,11 @@ def bench_mix(b):
             if i:
                 x += 1
             a = [x for x in range(i)]
+
+largedict = {str(v): v for v in range(1000)}
+
+def bench_dict_equal(b):
+    "Benchmark of dict equality operation."
+    for _ in range(b.n):
+        if largedict != largedict:
+            fail("invalid comparison")
diff --git a/starlark/testdata/dict.star b/starlark/testdata/dict.star
index 1aeb1e7..7e7fb14 100644
--- a/starlark/testdata/dict.star
+++ b/starlark/testdata/dict.star
@@ -246,3 +246,76 @@ _ = {
         ("three", 3),
     ]
 }
+
+
+---
+# dict | dict (union)
+
+load("assert.star", "assert", "freeze")
+
+empty_dict = dict()
+dict_with_a_b = dict(a=1, b=[1, 2])
+dict_with_b = dict(b=[1, 2])
+dict_with_other_b = dict(b=[3, 4])
+
+assert.eq(empty_dict | dict_with_a_b, dict_with_a_b)
+# Verify iteration order.
+assert.eq((empty_dict | dict_with_a_b).items(), dict_with_a_b.items())
+assert.eq(dict_with_a_b | empty_dict, dict_with_a_b)
+assert.eq((dict_with_a_b | empty_dict).items(), dict_with_a_b.items())
+assert.eq(dict_with_b | dict_with_a_b, dict_with_a_b)
+assert.eq((dict_with_b | dict_with_a_b).items(), dict(b=[1, 2], a=1).items())
+assert.eq(dict_with_a_b | dict_with_b, dict_with_a_b)
+assert.eq((dict_with_a_b | dict_with_b).items(), dict_with_a_b.items())
+assert.eq(dict_with_b | dict_with_other_b, dict_with_other_b)
+assert.eq((dict_with_b | dict_with_other_b).items(), dict_with_other_b.items())
+assert.eq(dict_with_other_b | dict_with_b, dict_with_b)
+assert.eq((dict_with_other_b | dict_with_b).items(), dict_with_b.items())
+
+assert.eq(empty_dict, dict())
+assert.eq(dict_with_b, dict(b=[1,2]))
+
+assert.fails(lambda: dict() | [], "unknown binary op: dict [|] list")
+
+# dict |= dict (in-place union)
+
+def test_dict_union_assignment():
+    x = dict()
+    saved = x
+    x |= {"a": 1}
+    x |= {"b": 2}
+    x |= {"c": "3", 7: 4}
+    x |= {"b": "5", "e": 6}
+    want = {"a": 1, "b": "5", "c": "3", 7: 4, "e": 6}
+    assert.eq(x, want)
+    assert.eq(x.items(), want.items())
+    assert.eq(saved, x) # they are aliases
+
+    a = {8: 1, "b": 2}
+    b = {"b": 1, "c": 6}
+    c = {"d": 7}
+    d = {(5, "a"): ("c", 8)}
+    orig_a, orig_c = a, c
+    a |= b
+    c |= a
+    c |= d
+    expected_2 = {"d": 7, 8: 1, "b": 1, "c": 6, (5, "a"): ("c", 8)}
+    assert.eq(c, expected_2)
+    assert.eq(c.items(), expected_2.items())
+    assert.eq(b, {"b": 1, "c": 6})
+
+    # aliasing:
+    assert.eq(a, orig_a)
+    assert.eq(c, orig_c)
+    a.clear()
+    c.clear()
+    assert.eq(a, orig_a)
+    assert.eq(c, orig_c)
+
+test_dict_union_assignment()
+
+def dict_union_assignment_type_mismatch():
+    some_dict = dict()
+    some_dict |= []
+
+assert.fails(dict_union_assignment_type_mismatch, "unknown binary op: dict [|] list")
\ No newline at end of file
diff --git a/starlark/testdata/math.star b/starlark/testdata/math.star
index ab2644d..4173e6d 100644
--- a/starlark/testdata/math.star
+++ b/starlark/testdata/math.star
@@ -255,8 +255,8 @@ assert.fails(lambda: math.sin("0"), "got string, want float or int")
 # tan
 assert.eq(math.tan(0.0), 0)
 assert.eq(math.tan(0), 0)
-assert.eq(math.tan(math.pi / 4), 1)
-assert.eq(math.tan(-math.pi / 4), -1)
+assert.true(near(math.tan(math.pi / 4), 1, 0.00000000000001))
+assert.true(near(math.tan(-math.pi / 4), -1, 0.00000000000001))
 assert.eq(math.tan(inf), nan)
 assert.eq(math.tan(-inf), nan)
 assert.eq(math.tan(nan), nan)
diff --git a/starlark/testdata/string.star b/starlark/testdata/string.star
index b317d1a..1a38d62 100644
--- a/starlark/testdata/string.star
+++ b/starlark/testdata/string.star
@@ -470,3 +470,24 @@ assert.true(not "Ǆenan Ǉubović".istitle())
 assert.fails(lambda: "".starts_with, "no .starts_with field.*did you mean .startswith")
 assert.fails(lambda: "".StartsWith, "no .StartsWith field.*did you mean .startswith")
 assert.fails(lambda: "".fin, "no .fin field.*.did you mean .find")
+
+
+# removesuffix
+assert.eq("Apricot".removesuffix("cot"), "Apri")
+assert.eq("Apricot".removesuffix("Cot"), "Apricot")
+assert.eq("Apricot".removesuffix("t"), "Aprico")
+assert.eq("a".removesuffix(""), "a")
+assert.eq("".removesuffix(""), "")
+assert.eq("".removesuffix("a"), "")
+assert.eq("Apricot".removesuffix("co"), "Apricot")
+assert.eq("Apricotcot".removesuffix("cot"), "Apricot")
+
+# removeprefix
+assert.eq("Apricot".removeprefix("Apr"), "icot")
+assert.eq("Apricot".removeprefix("apr"), "Apricot")
+assert.eq("Apricot".removeprefix("A"), "pricot")
+assert.eq("a".removeprefix(""), "a")
+assert.eq("".removeprefix(""), "")
+assert.eq("".removeprefix("a"), "")
+assert.eq("Apricot".removeprefix("pr"), "Apricot")
+assert.eq("AprApricot".removeprefix("Apr"), "Apricot")
\ No newline at end of file
diff --git a/syntax/scan_test.go b/syntax/scan_test.go
index 9582bd7..599dbbc 100644
--- a/syntax/scan_test.go
+++ b/syntax/scan_test.go
@@ -275,7 +275,7 @@ pass`, "pass newline pass EOF"}, // consecutive newlines are consolidated
 		if err != nil {
 			got = err.(Error).Error()
 		}
-		// Prefix match allows us to truncate errors in expecations.
+		// Prefix match allows us to truncate errors in expectations.
 		// Success cases all end in EOF.
 		if !strings.HasPrefix(got, test.want) {
 			t.Errorf("scan `%s` = [%s], want [%s]", test.input, got, test.want)
diff --git a/syntax/testdata/scan.star b/syntax/testdata/scan.star
index 4f62ba9..eec85c9 100644
--- a/syntax/testdata/scan.star
+++ b/syntax/testdata/scan.star
@@ -123,7 +123,7 @@ def _emit_generate_params_action(cmds, ctx, fn):
 
 def _emit_go_asm_action(ctx, source, hdrs, out_obj):
     """Construct the command line for compiling Go Assembly code.
-    Constructs a symlink tree to accomodate for workspace name.
+    Constructs a symlink tree to accommodate for workspace name.
     Args:
       ctx: The starlark Context.
       source: a source code artifact