py/runtime: Allow multiple **args in a function call.

This is a partial implementation of PEP 448 to allow multiple ** unpackings
when calling a function or method.

The compiler is modified to encode the argument as a None: obj key-value
pair (similar to how regular keyword arguments are encoded as str: obj
pairs).  The extra object that was pushed on the stack to hold a single **
unpacking object is no longer used and is removed.

The runtime is modified to decode this new format.

Signed-off-by: David Lechner <david@pybricks.com>

9 files changed, 122 insertions, 83 deletions

diff --git a/py/compile.c b/py/compile.c
index 36f33f97f..1636bd157 100644
--- a/py/compile.c
+++ b/py/compile.c
@@ -2397,7 +2397,7 @@ STATIC void compile_trailer_paren_helper(compiler_t *comp, mp_parse_node_t pn_ar
     int n_positional = n_positional_extra;
     uint n_keyword = 0;
     uint star_flags = 0;
-    mp_parse_node_struct_t *star_args_node = NULL, *dblstar_args_node = NULL;
+    mp_parse_node_struct_t *star_args_node = NULL;
     for (size_t i = 0; i < n_args; i++) {
         if (MP_PARSE_NODE_IS_STRUCT(args[i])) {
             mp_parse_node_struct_t *pns_arg = (mp_parse_node_struct_t *)args[i];
@@ -2409,12 +2409,11 @@ STATIC void compile_trailer_paren_helper(compiler_t *comp, mp_parse_node_t pn_ar
                 star_flags |= MP_EMIT_STAR_FLAG_SINGLE;
                 star_args_node = pns_arg;
             } else if (MP_PARSE_NODE_STRUCT_KIND(pns_arg) == PN_arglist_dbl_star) {
-                if (star_flags & MP_EMIT_STAR_FLAG_DOUBLE) {
-                    compile_syntax_error(comp, (mp_parse_node_t)pns_arg, MP_ERROR_TEXT("can't have multiple **x"));
-                    return;
-                }
                 star_flags |= MP_EMIT_STAR_FLAG_DOUBLE;
-                dblstar_args_node = pns_arg;
+                // double-star args are stored as kw arg with key of None
+                EMIT(load_null);
+                compile_node(comp, pns_arg->nodes[0]);
+                n_keyword++;
             } else if (MP_PARSE_NODE_STRUCT_KIND(pns_arg) == PN_argument) {
                 #if MICROPY_PY_ASSIGN_EXPR
                 if (MP_PARSE_NODE_IS_STRUCT_KIND(pns_arg->nodes[1], PN_argument_3)) {
@@ -2429,7 +2428,7 @@ STATIC void compile_trailer_paren_helper(compiler_t *comp, mp_parse_node_t pn_ar
                     }
                     EMIT_ARG(load_const_str, MP_PARSE_NODE_LEAF_ARG(pns_arg->nodes[0]));
                     compile_node(comp, pns_arg->nodes[1]);
-                    n_keyword += 1;
+                    n_keyword++;
                 } else {
                     compile_comprehension(comp, pns_arg, SCOPE_GEN_EXPR);
                     n_positional++;
@@ -2460,11 +2459,6 @@ STATIC void compile_trailer_paren_helper(compiler_t *comp, mp_parse_node_t pn_ar
         } else {
             compile_node(comp, star_args_node->nodes[0]);
         }
-        if (dblstar_args_node == NULL) {
-            EMIT(load_null);
-        } else {
-            compile_node(comp, dblstar_args_node->nodes[0]);
-        }
     }
 
     // emit the function/method call
diff --git a/py/emitbc.c b/py/emitbc.c
index 1f5cd9d32..21ec12191 100644
--- a/py/emitbc.c
+++ b/py/emitbc.c
@@ -752,7 +752,9 @@ void mp_emit_bc_make_closure(emit_t *emit, scope_t *scope, mp_uint_t n_closed_ov
 
 STATIC void emit_bc_call_function_method_helper(emit_t *emit, int stack_adj, mp_uint_t bytecode_base, mp_uint_t n_positional, mp_uint_t n_keyword, mp_uint_t star_flags) {
     if (star_flags) {
-        stack_adj -= (int)n_positional + 2 * (int)n_keyword + 2;
+        // each positional arg is one object, each kwarg is two objects, the key
+        // and the value and one extra object for the star args bitmap.
+        stack_adj -= (int)n_positional + 2 * (int)n_keyword + 1;
         emit_write_bytecode_byte_uint(emit, stack_adj, bytecode_base + 1, (n_keyword << 8) | n_positional); // TODO make it 2 separate uints?
     } else {
         stack_adj -= (int)n_positional + 2 * (int)n_keyword;
diff --git a/py/emitnative.c b/py/emitnative.c
index a207dd30f..286398404 100644
--- a/py/emitnative.c
+++ b/py/emitnative.c
@@ -2752,7 +2752,7 @@ STATIC void emit_native_call_function(emit_t *emit, mp_uint_t n_positional, mp_u
     } else {
         assert(vtype_fun == VTYPE_PYOBJ);
         if (star_flags) {
-            emit_get_stack_pointer_to_reg_for_pop(emit, REG_ARG_3, n_positional + 2 * n_keyword + 3); // pointer to args
+            emit_get_stack_pointer_to_reg_for_pop(emit, REG_ARG_3, n_positional + 2 * n_keyword + 2); // pointer to args
             emit_call_with_2_imm_args(emit, MP_F_CALL_METHOD_N_KW_VAR, 0, REG_ARG_1, n_positional | (n_keyword << 8), REG_ARG_2);
             emit_post_push_reg(emit, VTYPE_PYOBJ, REG_RET);
         } else {
@@ -2768,7 +2768,7 @@ STATIC void emit_native_call_function(emit_t *emit, mp_uint_t n_positional, mp_u
 
 STATIC void emit_native_call_method(emit_t *emit, mp_uint_t n_positional, mp_uint_t n_keyword, mp_uint_t star_flags) {
     if (star_flags) {
-        emit_get_stack_pointer_to_reg_for_pop(emit, REG_ARG_3, n_positional + 2 * n_keyword + 4); // pointer to args
+        emit_get_stack_pointer_to_reg_for_pop(emit, REG_ARG_3, n_positional + 2 * n_keyword + 3); // pointer to args
         emit_call_with_2_imm_args(emit, MP_F_CALL_METHOD_N_KW_VAR, 1, REG_ARG_1, n_positional | (n_keyword << 8), REG_ARG_2);
         emit_post_push_reg(emit, VTYPE_PYOBJ, REG_RET);
     } else {
diff --git a/py/runtime.c b/py/runtime.c
index ba3fbe7fa..e6bfbda58 100644
--- a/py/runtime.c
+++ b/py/runtime.c
@@ -702,9 +702,8 @@ void mp_call_prepare_args_n_kw_var(bool have_self, size_t n_args_n_kw, const mp_
     uint n_args = n_args_n_kw & 0xff;
     uint n_kw = (n_args_n_kw >> 8) & 0xff;
     mp_obj_t pos_seq = args[n_args + 2 * n_kw]; // may be MP_OBJ_NULL
-    mp_obj_t kw_dict = args[n_args + 2 * n_kw + 1]; // may be MP_OBJ_NULL
 
-    DEBUG_OP_printf("call method var (fun=%p, self=%p, n_args=%u, n_kw=%u, args=%p, seq=%p, dict=%p)\n", fun, self, n_args, n_kw, args, pos_seq, kw_dict);
+    DEBUG_OP_printf("call method var (fun=%p, self=%p, n_args=%u, n_kw=%u, args=%p, seq=%p)\n", fun, self, n_args, n_kw, args, pos_seq);
 
     // We need to create the following array of objects:
     //     args[0 .. n_args]  unpacked(pos_seq)  args[n_args .. n_args + 2 * n_kw]  unpacked(kw_dict)
@@ -717,8 +716,13 @@ void mp_call_prepare_args_n_kw_var(bool have_self, size_t n_args_n_kw, const mp_
 
     // Try to get a hint for the size of the kw_dict
     uint kw_dict_len = 0;
-    if (kw_dict != MP_OBJ_NULL && mp_obj_is_type(kw_dict, &mp_type_dict)) {
-        kw_dict_len = mp_obj_dict_len(kw_dict);
+
+    for (uint i = 0; i < n_kw; i++) {
+        mp_obj_t key = args[n_args + i * 2];
+        mp_obj_t value = args[n_args + i * 2 + 1];
+        if (key == MP_OBJ_NULL && value != MP_OBJ_NULL && mp_obj_is_type(value, &mp_type_dict)) {
+            kw_dict_len += mp_obj_dict_len(value);
+        }
     }
 
     // Extract the pos_seq sequence to the new args array.
@@ -792,64 +796,72 @@ void mp_call_prepare_args_n_kw_var(bool have_self, size_t n_args_n_kw, const mp_
     // The size of the args2 array now is the number of positional args.
     uint pos_args_len = args2_len;
 
-    // Copy the fixed kw args.
-    mp_seq_copy(args2 + args2_len, args + n_args, 2 * n_kw, mp_obj_t);
-    args2_len += 2 * n_kw;
-
-    // Extract (key,value) pairs from kw_dict dictionary and append to args2.
-    // Note that it can be arbitrary iterator.
-    if (kw_dict == MP_OBJ_NULL) {
-        // pass
-    } else if (mp_obj_is_type(kw_dict, &mp_type_dict)) {
-        // dictionary
-        mp_map_t *map = mp_obj_dict_get_map(kw_dict);
-        assert(args2_len + 2 * map->used <= args2_alloc); // should have enough, since kw_dict_len is in this case hinted correctly above
-        for (size_t i = 0; i < map->alloc; i++) {
-            if (mp_map_slot_is_filled(map, i)) {
-                // the key must be a qstr, so intern it if it's a string
-                mp_obj_t key = map->table[i].key;
-                if (!mp_obj_is_qstr(key)) {
-                    key = mp_obj_str_intern_checked(key);
-                }
-                args2[args2_len++] = key;
-                args2[args2_len++] = map->table[i].value;
-            }
-        }
-    } else {
-        // generic mapping:
-        // - call keys() to get an iterable of all keys in the mapping
-        // - call __getitem__ for each key to get the corresponding value
-
-        // get the keys iterable
-        mp_obj_t dest[3];
-        mp_load_method(kw_dict, MP_QSTR_keys, dest);
-        mp_obj_t iterable = mp_getiter(mp_call_method_n_kw(0, 0, dest), NULL);
-
-        mp_obj_t key;
-        while ((key = mp_iternext(iterable)) != MP_OBJ_STOP_ITERATION) {
-            // expand size of args array if needed
-            if (args2_len + 1 >= args2_alloc) {
-                uint new_alloc = args2_alloc * 2;
-                if (new_alloc < 4) {
-                    new_alloc = 4;
+    // Copy the kw args.
+    for (uint i = 0; i < n_kw; i++) {
+        mp_obj_t kw_key = args[n_args + i * 2];
+        mp_obj_t kw_value = args[n_args + i * 2 + 1];
+        if (kw_key == MP_OBJ_NULL) {
+            // double-star args
+            if (kw_value == MP_OBJ_NULL) {
+                // pass
+            } else if (mp_obj_is_type(kw_value, &mp_type_dict)) {
+                // dictionary
+                mp_map_t *map = mp_obj_dict_get_map(kw_value);
+                // should have enough, since kw_dict_len is in this case hinted correctly above
+                assert(args2_len + 2 * map->used <= args2_alloc);
+                for (size_t j = 0; j < map->alloc; j++) {
+                    if (mp_map_slot_is_filled(map, j)) {
+                        // the key must be a qstr, so intern it if it's a string
+                        mp_obj_t key = map->table[j].key;
+                        if (!mp_obj_is_qstr(key)) {
+                            key = mp_obj_str_intern_checked(key);
+                        }
+                        args2[args2_len++] = key;
+                        args2[args2_len++] = map->table[j].value;
+                    }
                 }
-                args2 = mp_nonlocal_realloc(args2, args2_alloc * sizeof(mp_obj_t), new_alloc * sizeof(mp_obj_t));
-                args2_alloc = new_alloc;
-            }
+            } else {
+                // generic mapping:
+                // - call keys() to get an iterable of all keys in the mapping
+                // - call __getitem__ for each key to get the corresponding value
+
+                // get the keys iterable
+                mp_obj_t dest[3];
+                mp_load_method(kw_value, MP_QSTR_keys, dest);
+                mp_obj_t iterable = mp_getiter(mp_call_method_n_kw(0, 0, dest), NULL);
+
+                mp_obj_t key;
+                while ((key = mp_iternext(iterable)) != MP_OBJ_STOP_ITERATION) {
+                    // expand size of args array if needed
+                    if (args2_len + 1 >= args2_alloc) {
+                        uint new_alloc = args2_alloc * 2;
+                        if (new_alloc < 4) {
+                            new_alloc = 4;
+                        }
+                        args2 = mp_nonlocal_realloc(args2, args2_alloc * sizeof(mp_obj_t), new_alloc * sizeof(mp_obj_t));
+                        args2_alloc = new_alloc;
+                    }
 
-            // the key must be a qstr, so intern it if it's a string
-            if (!mp_obj_is_qstr(key)) {
-                key = mp_obj_str_intern_checked(key);
-            }
+                    // the key must be a qstr, so intern it if it's a string
+                    if (!mp_obj_is_qstr(key)) {
+                        key = mp_obj_str_intern_checked(key);
+                    }
 
-            // get the value corresponding to the key
-            mp_load_method(kw_dict, MP_QSTR___getitem__, dest);
-            dest[2] = key;
-            mp_obj_t value = mp_call_method_n_kw(1, 0, dest);
+                    // get the value corresponding to the key
+                    mp_load_method(kw_value, MP_QSTR___getitem__, dest);
+                    dest[2] = key;
+                    mp_obj_t value = mp_call_method_n_kw(1, 0, dest);
 
-            // store the key/value pair in the argument array
-            args2[args2_len++] = key;
-            args2[args2_len++] = value;
+                    // store the key/value pair in the argument array
+                    args2[args2_len++] = key;
+                    args2[args2_len++] = value;
+                }
+            }
+        } else {
+            // normal kwarg
+            assert(args2_len + 2 <= args2_alloc);
+            args2[args2_len++] = kw_key;
+            args2[args2_len++] = kw_value;
         }
     }
 
diff --git a/py/vm.c b/py/vm.c
index fa163423a..145000483 100644
--- a/py/vm.c
+++ b/py/vm.c
@@ -949,8 +949,8 @@ unwind_jump:;
                     // unum & 0xff == n_positional
                     // (unum >> 8) & 0xff == n_keyword
                     // We have following stack layout here:
-                    // fun arg0 arg1 ... kw0 val0 kw1 val1 ... seq dict <- TOS
-                    sp -= (unum & 0xff) + ((unum >> 7) & 0x1fe) + 2;
+                    // fun arg0 arg1 ... kw0 val0 kw1 val1 ... seq <- TOS
+                    sp -= (unum & 0xff) + ((unum >> 7) & 0x1fe) + 1;
                     #if MICROPY_STACKLESS
                     if (mp_obj_get_type(*sp) == &mp_type_fun_bc) {
                         code_state->ip = ip;
@@ -1034,8 +1034,8 @@ unwind_jump:;
                     // unum & 0xff == n_positional
                     // (unum >> 8) & 0xff == n_keyword
                     // We have following stack layout here:
-                    // fun self arg0 arg1 ... kw0 val0 kw1 val1 ... seq dict <- TOS
-                    sp -= (unum & 0xff) + ((unum >> 7) & 0x1fe) + 3;
+                    // fun self arg0 arg1 ... kw0 val0 kw1 val1 ... seq <- TOS
+                    sp -= (unum & 0xff) + ((unum >> 7) & 0x1fe) + 2;
                     #if MICROPY_STACKLESS
                     if (mp_obj_get_type(*sp) == &mp_type_fun_bc) {
                         code_state->ip = ip;
diff --git a/tests/basics/fun_calldblstar4.py b/tests/basics/fun_calldblstar4.py
new file mode 100644
index 000000000..acb332a8c
--- /dev/null
+++ b/tests/basics/fun_calldblstar4.py
@@ -0,0 +1,33 @@
+# test calling a function with multiple **args
+
+
+def f(a, b=None, c=None):
+    print(a, b, c)
+
+
+f(**{"a": 1}, **{"b": 2})
+f(**{"a": 1}, **{"b": 2}, c=3)
+f(**{"a": 1}, b=2, **{"c": 3})
+
+try:
+    f(1, **{"b": 2}, **{"b": 3})
+except TypeError:
+    print("TypeError")
+
+# test calling a method with multiple **args
+
+
+class A:
+    def f(self, a, b=None, c=None):
+        print(a, b, c)
+
+
+a = A()
+a.f(**{"a": 1}, **{"b": 2})
+a.f(**{"a": 1}, **{"b": 2}, c=3)
+a.f(**{"a": 1}, b=2, **{"c": 3})
+
+try:
+    a.f(1, **{"b": 2}, **{"b": 3})
+except TypeError:
+    print("TypeError")
diff --git a/tests/basics/python34.py b/tests/basics/python34.py
index 0f6e4bafd..609a8b6b8 100644
--- a/tests/basics/python34.py
+++ b/tests/basics/python34.py
@@ -25,7 +25,6 @@ def test_syntax(code):
     except SyntaxError:
         print("SyntaxError")
 test_syntax("f(*a, *b)") # can't have multiple * (in 3.5 we can)
-test_syntax("f(**a, **b)") # can't have multiple ** (in 3.5 we can)
 test_syntax("f(*a, b)") # can't have positional after *
 test_syntax("f(**a, b)") # can't have positional after **
 test_syntax("() = []") # can't assign to empty tuple (in 3.6 we can)
diff --git a/tests/basics/python34.py.exp b/tests/basics/python34.py.exp
index 848017130..75f1c2c05 100644
--- a/tests/basics/python34.py.exp
+++ b/tests/basics/python34.py.exp
@@ -8,7 +8,6 @@ SyntaxError
 SyntaxError
 SyntaxError
 SyntaxError
-SyntaxError
 3.4
 3 4
 IndexError('foo',)
diff --git a/tests/cmdline/cmd_showbc.py.exp b/tests/cmdline/cmd_showbc.py.exp
index 92501e124..663bacda0 100644
--- a/tests/cmdline/cmd_showbc.py.exp
+++ b/tests/cmdline/cmd_showbc.py.exp
@@ -297,8 +297,8 @@ arg names:
 208 POP_TOP
 209 LOAD_FAST 0
 210 LOAD_DEREF 14
-212 LOAD_NULL
-213 CALL_FUNCTION_VAR_KW n=0 nkw=0
+212 LOAD_CONST_SMALL_INT 1
+213 CALL_FUNCTION_VAR_KW n=1 nkw=0
 215 POP_TOP
 216 LOAD_FAST 0
 217 LOAD_METHOD b
@@ -318,8 +318,8 @@ arg names:
 239 LOAD_FAST 0
 240 LOAD_METHOD b
 242 LOAD_FAST 1
-243 LOAD_NULL
-244 CALL_METHOD_VAR_KW n=0 nkw=0
+243 LOAD_CONST_SMALL_INT 1
+244 CALL_METHOD_VAR_KW n=1 nkw=0
 246 POP_TOP
 247 LOAD_FAST 0
 248 POP_JUMP_IF_FALSE 255