Add dict|dict and dict|=dict (#397)
diff --git a/doc/spec.md b/doc/spec.md index 37772e0..90afccc 100644 --- a/doc/spec.md +++ b/doc/spec.md
@@ -906,6 +906,20 @@ 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 @@ -2018,6 +2032,9 @@ 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 @@ -2056,10 +2073,14 @@ 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.
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 @@ 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 @@ 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 @@ IN: "in", INDEX: "index", INPLACE_ADD: "inplace_add", + INPLACE_PIPE: "inplace_pipe", ITERJMP: "iterjmp", ITERPOP: "iterpop", ITERPUSH: "iterpush", @@ -250,6 +252,7 @@ IN: -1, INDEX: -1, INPLACE_ADD: -1, + INPLACE_PIPE: -1, ITERJMP: variableStackEffect, ITERPOP: 0, ITERPUSH: -1, @@ -1145,11 +1148,16 @@ 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 49d4756..4941d44 100644 --- a/starlark/eval.go +++ b/starlark/eval.go
@@ -1036,6 +1036,12 @@ 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 @@ // 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 @@ 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) 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) 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 @@ 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 @@ 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/interp.go b/starlark/interp.go index 2dcc731..9961e2f 100644 --- a/starlark/interp.go +++ b/starlark/interp.go
@@ -224,6 +224,34 @@ 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/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/value.go b/starlark/value.go index 72f3001..b51d4ca 100644 --- a/starlark/value.go +++ b/starlark/value.go
@@ -795,6 +795,14 @@ 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) }