runtime.c 55.8 KB
Newer Older
1
/*
2
 * This file is part of the MicroPython project, http://micropython.org/
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
 *
 * The MIT License (MIT)
 *
 * Copyright (c) 2013, 2014 Damien P. George
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

Damien's avatar
Damien committed
27 28 29 30
#include <stdio.h>
#include <string.h>
#include <assert.h>

31 32
#include "py/parsenum.h"
#include "py/compile.h"
33
#include "py/objstr.h"
34 35 36 37 38 39 40 41 42
#include "py/objtuple.h"
#include "py/objlist.h"
#include "py/objmodule.h"
#include "py/objgenerator.h"
#include "py/smallint.h"
#include "py/runtime.h"
#include "py/builtin.h"
#include "py/stackctrl.h"
#include "py/gc.h"
43

44
#if MICROPY_DEBUG_VERBOSE // print debugging info
45
#define DEBUG_PRINT (1)
46
#define DEBUG_printf DEBUG_printf
47
#define DEBUG_OP_printf(...) DEBUG_printf(__VA_ARGS__)
48
#else // don't print debugging info
49 50
#define DEBUG_printf(...) (void)0
#define DEBUG_OP_printf(...) (void)0
51
#endif
Damien's avatar
Damien committed
52

53
#if !defined(MP_STATE_PTR)
54 55
const mp_obj_module_t mp_module___main__ = {
    .base = { &mp_type_module },
56
    .globals = (mp_obj_dict_t*)&MP_STATE_VM(dict_main),
57
};
58
#endif
59

Damien George's avatar
Damien George committed
60
void mp_init(void) {
61
    qstr_init();
62

63
    // no pending exceptions to start with
64
    MP_STATE_VM(mp_pending_exception) = MP_OBJ_NULL;
65 66 67 68
    #if MICROPY_ENABLE_SCHEDULER
    MP_STATE_VM(sched_state) = MP_SCHED_IDLE;
    MP_STATE_VM(sched_sp) = 0;
    #endif
69

70 71 72 73
#if MICROPY_ENABLE_EMERGENCY_EXCEPTION_BUF
    mp_init_emergency_exception_buf();
#endif

74 75 76 77 78 79
    #if MICROPY_KBD_EXCEPTION
    // initialise the exception object for raising KeyboardInterrupt
    MP_STATE_VM(mp_kbd_exception).base.type = &mp_type_KeyboardInterrupt;
    MP_STATE_VM(mp_kbd_exception).traceback_alloc = 0;
    MP_STATE_VM(mp_kbd_exception).traceback_len = 0;
    MP_STATE_VM(mp_kbd_exception).traceback_data = NULL;
80
    MP_STATE_VM(mp_kbd_exception).args = (mp_obj_tuple_t*)&mp_const_empty_tuple_obj;
81 82
    #endif

83
    // call port specific initialization if any
84 85 86 87
#ifdef MICROPY_PORT_INIT_FUNC
    MICROPY_PORT_INIT_FUNC;
#endif

88
    // optimization disabled by default
89
    MP_STATE_VM(mp_optimise_value) = 0;
90

91 92
    // init global module dict
    mp_obj_dict_init(&MP_STATE_VM(mp_loaded_modules_dict), 3);
93

94
    // initialise the __main__ module
95 96 97 98
    #if defined(MP_STATE_PTR)
    MP_STATE_VM(mp_module___main__).base.type = &mp_type_module;
    MP_STATE_VM(mp_module___main__).globals = &MP_STATE_VM(dict_main);
    #endif
99
    mp_obj_dict_init(&MP_STATE_VM(dict_main), 1);
100
    mp_obj_dict_store(MP_OBJ_FROM_PTR(&MP_STATE_VM(dict_main)), MP_OBJ_NEW_QSTR(MP_QSTR___name__), MP_OBJ_NEW_QSTR(MP_QSTR___main__));
101 102

    // locals = globals for outer module (see Objects/frameobject.c/PyFrame_New())
103 104
    mp_locals_set(&MP_STATE_VM(dict_main));
    mp_globals_set(&MP_STATE_VM(dict_main));
105 106 107

    #if MICROPY_CAN_OVERRIDE_BUILTINS
    // start with no extensions to builtins
108
    MP_STATE_VM(mp_module_builtins_override_dict) = NULL;
109
    #endif
110

111 112 113 114 115 116 117
    #if MICROPY_PY_OS_DUPTERM
    for (size_t i = 0; i < MICROPY_PY_OS_DUPTERM; ++i) {
        MP_STATE_VM(dupterm_objs[i]) = MP_OBJ_NULL;
    }
    MP_STATE_VM(dupterm_arr_obj) = MP_OBJ_NULL;
    #endif

118 119 120 121 122
    #if MICROPY_FSUSERMOUNT
    // zero out the pointers to the user-mounted devices
    memset(MP_STATE_VM(fs_user_mount), 0, sizeof(MP_STATE_VM(fs_user_mount)));
    #endif

123 124 125 126 127 128
    #if MICROPY_VFS
    // initialise the VFS sub-system
    MP_STATE_VM(vfs_cur) = NULL;
    MP_STATE_VM(vfs_mount_table) = NULL;
    #endif

129 130 131 132 133
    #if MICROPY_PY_THREAD_GIL
    mp_thread_mutex_init(&MP_STATE_VM(gil_mutex));
    #endif

    MP_THREAD_GIL_ENTER();
Damien's avatar
Damien committed
134 135
}

Damien George's avatar
Damien George committed
136
void mp_deinit(void) {
137
    //mp_obj_dict_free(&dict_main);
138
    //mp_map_deinit(&MP_STATE_VM(mp_loaded_modules_map));
stijn's avatar
stijn committed
139

140
    // call port specific deinitialization if any
stijn's avatar
stijn committed
141 142 143
#ifdef MICROPY_PORT_INIT_FUNC
    MICROPY_PORT_DEINIT_FUNC;
#endif
Damien's avatar
Damien committed
144 145
}

146
mp_obj_t mp_load_name(qstr qst) {
Damien's avatar
Damien committed
147
    // logic: search locals, globals, builtins
148
    DEBUG_OP_printf("load name %s\n", qstr_str(qst));
149
    // If we're at the outer scope (locals == globals), dispatch to load_global right away
150 151
    if (mp_locals_get() != mp_globals_get()) {
        mp_map_elem_t *elem = mp_map_lookup(&mp_locals_get()->map, MP_OBJ_NEW_QSTR(qst), MP_MAP_LOOKUP);
152 153 154
        if (elem != NULL) {
            return elem->value;
        }
Damien's avatar
Damien committed
155
    }
156
    return mp_load_global(qst);
Damien's avatar
Damien committed
157 158
}

159
mp_obj_t mp_load_global(qstr qst) {
160
    // logic: search globals, builtins
161
    DEBUG_OP_printf("load global %s\n", qstr_str(qst));
162
    mp_map_elem_t *elem = mp_map_lookup(&mp_globals_get()->map, MP_OBJ_NEW_QSTR(qst), MP_MAP_LOOKUP);
163
    if (elem == NULL) {
164
        #if MICROPY_CAN_OVERRIDE_BUILTINS
165
        if (MP_STATE_VM(mp_module_builtins_override_dict) != NULL) {
166
            // lookup in additional dynamic table of builtins first
167
            elem = mp_map_lookup(&MP_STATE_VM(mp_module_builtins_override_dict)->map, MP_OBJ_NEW_QSTR(qst), MP_MAP_LOOKUP);
168 169 170 171 172
            if (elem != NULL) {
                return elem->value;
            }
        }
        #endif
173
        elem = mp_map_lookup((mp_map_t*)&mp_module_builtins_globals.map, MP_OBJ_NEW_QSTR(qst), MP_MAP_LOOKUP);
174
        if (elem == NULL) {
175
            #if MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE
176
                mp_raise_msg(&mp_type_NameError, "name not defined");
177
            #else
178
                nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_NameError,
179
                    "name '%q' is not defined", qst));
180
            #endif
181 182 183
        }
    }
    return elem->value;
Damien's avatar
Damien committed
184 185
}

Damien George's avatar
Damien George committed
186
mp_obj_t mp_load_build_class(void) {
Damien's avatar
Damien committed
187
    DEBUG_OP_printf("load_build_class\n");
188
    #if MICROPY_CAN_OVERRIDE_BUILTINS
189
    if (MP_STATE_VM(mp_module_builtins_override_dict) != NULL) {
190
        // lookup in additional dynamic table of builtins first
191
        mp_map_elem_t *elem = mp_map_lookup(&MP_STATE_VM(mp_module_builtins_override_dict)->map, MP_OBJ_NEW_QSTR(MP_QSTR___build_class__), MP_MAP_LOOKUP);
192 193 194 195 196
        if (elem != NULL) {
            return elem->value;
        }
    }
    #endif
197
    return MP_OBJ_FROM_PTR(&mp_builtin___build_class___obj);
Damien's avatar
Damien committed
198 199
}

200 201
void mp_store_name(qstr qst, mp_obj_t obj) {
    DEBUG_OP_printf("store name %s <- %p\n", qstr_str(qst), obj);
202
    mp_obj_dict_store(MP_OBJ_FROM_PTR(mp_locals_get()), MP_OBJ_NEW_QSTR(qst), obj);
203 204
}

205 206 207
void mp_delete_name(qstr qst) {
    DEBUG_OP_printf("delete name %s\n", qstr_str(qst));
    // TODO convert KeyError to NameError if qst not found
208
    mp_obj_dict_delete(MP_OBJ_FROM_PTR(mp_locals_get()), MP_OBJ_NEW_QSTR(qst));
209 210
}

211 212
void mp_store_global(qstr qst, mp_obj_t obj) {
    DEBUG_OP_printf("store global %s <- %p\n", qstr_str(qst), obj);
213
    mp_obj_dict_store(MP_OBJ_FROM_PTR(mp_globals_get()), MP_OBJ_NEW_QSTR(qst), obj);
Damien's avatar
Damien committed
214 215
}

216 217 218
void mp_delete_global(qstr qst) {
    DEBUG_OP_printf("delete global %s\n", qstr_str(qst));
    // TODO convert KeyError to NameError if qst not found
219
    mp_obj_dict_delete(MP_OBJ_FROM_PTR(mp_globals_get()), MP_OBJ_NEW_QSTR(qst));
220 221
}

222
mp_obj_t mp_unary_op(mp_unary_op_t op, mp_obj_t arg) {
223
    DEBUG_OP_printf("unary " UINT_FMT " %q %p\n", op, mp_unary_op_method_name[op], arg);
224

225 226 227 228
    if (op == MP_UNARY_OP_NOT) {
        // "not x" is the negative of whether "x" is true per Python semantics
        return mp_obj_new_bool(mp_obj_is_true(arg) == 0);
    } else if (MP_OBJ_IS_SMALL_INT(arg)) {
229
        mp_int_t val = MP_OBJ_SMALL_INT_VALUE(arg);
Damien's avatar
Damien committed
230
        switch (op) {
Damien George's avatar
Damien George committed
231
            case MP_UNARY_OP_BOOL:
232
                return mp_obj_new_bool(val != 0);
233 234
            case MP_UNARY_OP_HASH:
                return arg;
Damien George's avatar
Damien George committed
235
            case MP_UNARY_OP_POSITIVE:
236
                return arg;
Damien George's avatar
Damien George committed
237
            case MP_UNARY_OP_NEGATIVE:
238 239 240 241 242 243
                // check for overflow
                if (val == MP_SMALL_INT_MIN) {
                    return mp_obj_new_int(-val);
                } else {
                    return MP_OBJ_NEW_SMALL_INT(-val);
                }
244 245 246 247 248 249 250 251 252
            case MP_UNARY_OP_ABS:
                if (val >= 0) {
                    return arg;
                } else if (val == MP_SMALL_INT_MIN) {
                    // check for overflow
                    return mp_obj_new_int(-val);
                } else {
                    return MP_OBJ_NEW_SMALL_INT(-val);
                }
253
            default:
254 255
                assert(op == MP_UNARY_OP_INVERT);
                return MP_OBJ_NEW_SMALL_INT(~val);
256
        }
257 258 259
    } else if (op == MP_UNARY_OP_HASH && MP_OBJ_IS_STR_OR_BYTES(arg)) {
        // fast path for hashing str/bytes
        GET_STR_HASH(arg, h);
260 261 262 263
        if (h == 0) {
            GET_STR_DATA_LEN(arg, data, len);
            h = qstr_compute_hash(data, len);
        }
264
        return MP_OBJ_NEW_SMALL_INT(h);
265 266 267 268
    } else {
        mp_obj_type_t *type = mp_obj_get_type(arg);
        if (type->unary_op != NULL) {
            mp_obj_t result = type->unary_op(op, arg);
269
            if (result != MP_OBJ_NULL) {
270 271
                return result;
            }
Damien's avatar
Damien committed
272
        }
273
        #if MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE
274
            mp_raise_TypeError("unsupported type for operator");
275
        #else
276
            nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_TypeError,
277 278
                "unsupported type for %q: '%s'",
                mp_unary_op_method_name[op], mp_obj_get_type_str(arg)));
279
        #endif
Damien's avatar
Damien committed
280
    }
Damien's avatar
Damien committed
281 282
}

283
mp_obj_t mp_binary_op(mp_binary_op_t op, mp_obj_t lhs, mp_obj_t rhs) {
284
    DEBUG_OP_printf("binary " UINT_FMT " %q %p %p\n", op, mp_binary_op_method_name[op], lhs, rhs);
285 286 287 288 289 290 291 292 293 294

    // TODO correctly distinguish inplace operators for mutable objects
    // lookup logic that CPython uses for +=:
    //   check for implemented +=
    //   then check for implemented +
    //   then check for implemented seq.inplace_concat
    //   then check for implemented seq.concat
    //   then fail
    // note that list does not implement + or +=, so that inplace_concat is reached first for +=

295
    // deal with is
Damien George's avatar
Damien George committed
296
    if (op == MP_BINARY_OP_IS) {
297
        return mp_obj_new_bool(lhs == rhs);
298 299
    }

300
    // deal with == and != for all types
Damien George's avatar
Damien George committed
301
    if (op == MP_BINARY_OP_EQUAL || op == MP_BINARY_OP_NOT_EQUAL) {
302
        if (mp_obj_equal(lhs, rhs)) {
Damien George's avatar
Damien George committed
303
            if (op == MP_BINARY_OP_EQUAL) {
304 305 306 307 308
                return mp_const_true;
            } else {
                return mp_const_false;
            }
        } else {
Damien George's avatar
Damien George committed
309
            if (op == MP_BINARY_OP_EQUAL) {
310 311 312 313 314 315 316 317
                return mp_const_false;
            } else {
                return mp_const_true;
            }
        }
    }

    // deal with exception_match for all types
Damien George's avatar
Damien George committed
318
    if (op == MP_BINARY_OP_EXCEPTION_MATCH) {
319 320
        // rhs must be issubclass(rhs, BaseException)
        if (mp_obj_is_exception_type(rhs)) {
321
            if (mp_obj_exception_match(lhs, rhs)) {
322 323 324 325
                return mp_const_true;
            } else {
                return mp_const_false;
            }
326
        } else if (MP_OBJ_IS_TYPE(rhs, &mp_type_tuple)) {
327
            mp_obj_tuple_t *tuple = MP_OBJ_TO_PTR(rhs);
328
            for (size_t i = 0; i < tuple->len; i++) {
329 330 331 332 333 334 335 336 337
                rhs = tuple->items[i];
                if (!mp_obj_is_exception_type(rhs)) {
                    goto unsupported_op;
                }
                if (mp_obj_exception_match(lhs, rhs)) {
                    return mp_const_true;
                }
            }
            return mp_const_false;
338
        }
339
        goto unsupported_op;
340 341
    }

342
    if (MP_OBJ_IS_SMALL_INT(lhs)) {
343
        mp_int_t lhs_val = MP_OBJ_SMALL_INT_VALUE(lhs);
344
        if (MP_OBJ_IS_SMALL_INT(rhs)) {
345
            mp_int_t rhs_val = MP_OBJ_SMALL_INT_VALUE(rhs);
346 347 348
            // This is a binary operation: lhs_val op rhs_val
            // We need to be careful to handle overflow; see CERT INT32-C
            // Operations that can overflow:
349 350
            //      +       result always fits in mp_int_t, then handled by SMALL_INT check
            //      -       result always fits in mp_int_t, then handled by SMALL_INT check
351
            //      *       checked explicitly
352 353
            //      /       if lhs=MIN and rhs=-1; result always fits in mp_int_t, then handled by SMALL_INT check
            //      %       if lhs=MIN and rhs=-1; result always fits in mp_int_t, then handled by SMALL_INT check
354
            //      <<      checked explicitly
355
            switch (op) {
Damien George's avatar
Damien George committed
356 357 358 359 360 361 362 363
                case MP_BINARY_OP_OR:
                case MP_BINARY_OP_INPLACE_OR: lhs_val |= rhs_val; break;
                case MP_BINARY_OP_XOR:
                case MP_BINARY_OP_INPLACE_XOR: lhs_val ^= rhs_val; break;
                case MP_BINARY_OP_AND:
                case MP_BINARY_OP_INPLACE_AND: lhs_val &= rhs_val; break;
                case MP_BINARY_OP_LSHIFT:
                case MP_BINARY_OP_INPLACE_LSHIFT: {
364 365
                    if (rhs_val < 0) {
                        // negative shift not allowed
366
                        mp_raise_ValueError("negative shift count");
367
                    } else if (rhs_val >= (mp_int_t)BITS_PER_WORD || lhs_val > (MP_SMALL_INT_MAX >> rhs_val) || lhs_val < (MP_SMALL_INT_MIN >> rhs_val)) {
368 369 370 371 372 373 374 375 376
                        // left-shift will overflow, so use higher precision integer
                        lhs = mp_obj_new_int_from_ll(lhs_val);
                        goto generic_binary_op;
                    } else {
                        // use standard precision
                        lhs_val <<= rhs_val;
                    }
                    break;
                }
Damien George's avatar
Damien George committed
377 378
                case MP_BINARY_OP_RSHIFT:
                case MP_BINARY_OP_INPLACE_RSHIFT:
379 380
                    if (rhs_val < 0) {
                        // negative shift not allowed
381
                        mp_raise_ValueError("negative shift count");
382 383
                    } else {
                        // standard precision is enough for right-shift
384
                        if (rhs_val >= (mp_int_t)BITS_PER_WORD) {
385 386 387 388
                            // Shifting to big amounts is underfined behavior
                            // in C and is CPU-dependent; propagate sign bit.
                            rhs_val = BITS_PER_WORD - 1;
                        }
389 390 391
                        lhs_val >>= rhs_val;
                    }
                    break;
Damien George's avatar
Damien George committed
392 393 394 395 396 397
                case MP_BINARY_OP_ADD:
                case MP_BINARY_OP_INPLACE_ADD: lhs_val += rhs_val; break;
                case MP_BINARY_OP_SUBTRACT:
                case MP_BINARY_OP_INPLACE_SUBTRACT: lhs_val -= rhs_val; break;
                case MP_BINARY_OP_MULTIPLY:
                case MP_BINARY_OP_INPLACE_MULTIPLY: {
398

399
                    // If long long type exists and is larger than mp_int_t, then
400
                    // we can use the following code to perform overflow-checked multiplication.
401
                    // Otherwise (eg in x64 case) we must use mp_small_int_mul_overflow.
402 403 404 405 406 407 408 409
                    #if 0
                    // compute result using long long precision
                    long long res = (long long)lhs_val * (long long)rhs_val;
                    if (res > MP_SMALL_INT_MAX || res < MP_SMALL_INT_MIN) {
                        // result overflowed SMALL_INT, so return higher precision integer
                        return mp_obj_new_int_from_ll(res);
                    } else {
                        // use standard precision
410
                        lhs_val = (mp_int_t)res;
411 412 413
                    }
                    #endif

414 415 416 417 418 419 420 421
                    if (mp_small_int_mul_overflow(lhs_val, rhs_val)) {
                        // use higher precision
                        lhs = mp_obj_new_int_from_ll(lhs_val);
                        goto generic_binary_op;
                    } else {
                        // use standard precision
                        return MP_OBJ_NEW_SMALL_INT(lhs_val * rhs_val);
                    }
422
                }
Damien George's avatar
Damien George committed
423 424
                case MP_BINARY_OP_FLOOR_DIVIDE:
                case MP_BINARY_OP_INPLACE_FLOOR_DIVIDE:
425 426 427
                    if (rhs_val == 0) {
                        goto zero_division;
                    }
428
                    lhs_val = mp_small_int_floor_divide(lhs_val, rhs_val);
429
                    break;
430

431
                #if MICROPY_PY_BUILTINS_FLOAT
Damien George's avatar
Damien George committed
432
                case MP_BINARY_OP_TRUE_DIVIDE:
433 434
                case MP_BINARY_OP_INPLACE_TRUE_DIVIDE:
                    if (rhs_val == 0) {
435
                        goto zero_division;
436 437
                    }
                    return mp_obj_new_float((mp_float_t)lhs_val / (mp_float_t)rhs_val);
438
                #endif
439

Damien George's avatar
Damien George committed
440
                case MP_BINARY_OP_MODULO:
441
                case MP_BINARY_OP_INPLACE_MODULO: {
442 443 444
                    if (rhs_val == 0) {
                        goto zero_division;
                    }
445
                    lhs_val = mp_small_int_modulo(lhs_val, rhs_val);
446 447
                    break;
                }
448

Damien George's avatar
Damien George committed
449 450
                case MP_BINARY_OP_POWER:
                case MP_BINARY_OP_INPLACE_POWER:
451
                    if (rhs_val < 0) {
452
                        #if MICROPY_PY_BUILTINS_FLOAT
453 454 455
                        lhs = mp_obj_new_float(lhs_val);
                        goto generic_binary_op;
                        #else
456
                        mp_raise_ValueError("negative power with no float support");
457 458
                        #endif
                    } else {
459
                        mp_int_t ans = 1;
460 461
                        while (rhs_val > 0) {
                            if (rhs_val & 1) {
462
                                if (mp_small_int_mul_overflow(ans, lhs_val)) {
463 464
                                    goto power_overflow;
                                }
465
                                ans *= lhs_val;
466 467 468
                            }
                            if (rhs_val == 1) {
                                break;
469 470
                            }
                            rhs_val /= 2;
471
                            if (mp_small_int_mul_overflow(lhs_val, lhs_val)) {
472 473
                                goto power_overflow;
                            }
474
                            lhs_val *= lhs_val;
475
                        }
476
                        lhs_val = ans;
477
                    }
478
                    break;
479 480 481 482 483 484

                power_overflow:
                    // use higher precision
                    lhs = mp_obj_new_int_from_ll(MP_OBJ_SMALL_INT_VALUE(lhs));
                    goto generic_binary_op;

485 486 487 488 489
                case MP_BINARY_OP_DIVMOD: {
                    if (rhs_val == 0) {
                        goto zero_division;
                    }
                    // to reduce stack usage we don't pass a temp array of the 2 items
490
                    mp_obj_tuple_t *tuple = MP_OBJ_TO_PTR(mp_obj_new_tuple(2, NULL));
491 492
                    tuple->items[0] = MP_OBJ_NEW_SMALL_INT(mp_small_int_floor_divide(lhs_val, rhs_val));
                    tuple->items[1] = MP_OBJ_NEW_SMALL_INT(mp_small_int_modulo(lhs_val, rhs_val));
493
                    return MP_OBJ_FROM_PTR(tuple);
494 495
                }

496 497 498 499
                case MP_BINARY_OP_LESS: return mp_obj_new_bool(lhs_val < rhs_val);
                case MP_BINARY_OP_MORE: return mp_obj_new_bool(lhs_val > rhs_val);
                case MP_BINARY_OP_LESS_EQUAL: return mp_obj_new_bool(lhs_val <= rhs_val);
                case MP_BINARY_OP_MORE_EQUAL: return mp_obj_new_bool(lhs_val >= rhs_val);
500

501 502
                default:
                    goto unsupported_op;
503
            }
504
            // TODO: We just should make mp_obj_new_int() inline and use that
505
            if (MP_SMALL_INT_FITS(lhs_val)) {
506
                return MP_OBJ_NEW_SMALL_INT(lhs_val);
507 508
            } else {
                return mp_obj_new_int(lhs_val);
509
            }
510
#if MICROPY_PY_BUILTINS_FLOAT
511
        } else if (mp_obj_is_float(rhs)) {
512 513 514 515 516 517
            mp_obj_t res = mp_obj_float_binary_op(op, lhs_val, rhs);
            if (res == MP_OBJ_NULL) {
                goto unsupported_op;
            } else {
                return res;
            }
518
#if MICROPY_PY_BUILTINS_COMPLEX
519
        } else if (MP_OBJ_IS_TYPE(rhs, &mp_type_complex)) {
520 521 522 523 524 525
            mp_obj_t res = mp_obj_complex_binary_op(op, lhs_val, 0, rhs);
            if (res == MP_OBJ_NULL) {
                goto unsupported_op;
            } else {
                return res;
            }
526
#endif
527
#endif
528
        }
529
    }
530

531
    // Convert MP_BINARY_OP_IN to MP_BINARY_OP_CONTAINS with swapped args.
Damien George's avatar
Damien George committed
532
    if (op == MP_BINARY_OP_IN) {
533 534 535 536
        op = MP_BINARY_OP_CONTAINS;
        mp_obj_t temp = lhs;
        lhs = rhs;
        rhs = temp;
537 538
    }

539
    // generic binary_op supplied by type
540 541 542
    mp_obj_type_t *type;
generic_binary_op:
    type = mp_obj_get_type(lhs);
543 544
    if (type->binary_op != NULL) {
        mp_obj_t result = type->binary_op(op, lhs, rhs);
545
        if (result != MP_OBJ_NULL) {
546
            return result;
Damien's avatar
Damien committed
547 548
        }
    }
549

550 551 552 553 554 555 556 557 558 559 560 561 562 563
#if MICROPY_PY_REVERSE_SPECIAL_METHODS
    if (op >= MP_BINARY_OP_OR && op <= MP_BINARY_OP_REVERSE_POWER) {
        mp_obj_t t = rhs;
        rhs = lhs;
        lhs = t;
        if (op <= MP_BINARY_OP_POWER) {
            op += MP_BINARY_OP_REVERSE_OR - MP_BINARY_OP_OR;
            goto generic_binary_op;
        }

        // Convert __rop__ back to __op__ for error message
        op -= MP_BINARY_OP_REVERSE_OR - MP_BINARY_OP_OR;
    }
#endif
564

565 566 567 568 569 570 571 572 573 574 575 576 577 578
    if (op == MP_BINARY_OP_CONTAINS) {
        // If type didn't support containment then explicitly walk the iterator.
        // mp_getiter will raise the appropriate exception if lhs is not iterable.
        mp_obj_iter_buf_t iter_buf;
        mp_obj_t iter = mp_getiter(lhs, &iter_buf);
        mp_obj_t next;
        while ((next = mp_iternext(iter)) != MP_OBJ_STOP_ITERATION) {
            if (mp_obj_equal(next, rhs)) {
                return mp_const_true;
            }
        }
        return mp_const_false;
    }

579
unsupported_op:
580
    #if MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE
581
        mp_raise_TypeError("unsupported type for operator");
582
    #else
583
        nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_TypeError,
584 585
            "unsupported types for %q: '%s', '%s'",
            mp_binary_op_method_name[op], mp_obj_get_type_str(lhs), mp_obj_get_type_str(rhs)));
586
    #endif
587 588

zero_division:
589
    mp_raise_msg(&mp_type_ZeroDivisionError, "division by zero");
Damien's avatar
Damien committed
590 591
}

Damien George's avatar
Damien George committed
592 593
mp_obj_t mp_call_function_0(mp_obj_t fun) {
    return mp_call_function_n_kw(fun, 0, 0, NULL);
594 595
}

Damien George's avatar
Damien George committed
596 597
mp_obj_t mp_call_function_1(mp_obj_t fun, mp_obj_t arg) {
    return mp_call_function_n_kw(fun, 1, 0, &arg);
598 599
}

Damien George's avatar
Damien George committed
600
mp_obj_t mp_call_function_2(mp_obj_t fun, mp_obj_t arg1, mp_obj_t arg2) {
601
    mp_obj_t args[2];
602 603
    args[0] = arg1;
    args[1] = arg2;
Damien George's avatar
Damien George committed
604
    return mp_call_function_n_kw(fun, 2, 0, args);
605 606
}

607
// args contains, eg: arg0  arg1  key0  value0  key1  value1
608
mp_obj_t mp_call_function_n_kw(mp_obj_t fun_in, size_t n_args, size_t n_kw, const mp_obj_t *args) {
609 610
    // TODO improve this: fun object can specify its type and we parse here the arguments,
    // passing to the function arrays of fixed and keyword arguments
611

612
    DEBUG_OP_printf("calling function %p(n_args=" UINT_FMT ", n_kw=" UINT_FMT ", args=%p)\n", fun_in, n_args, n_kw, args);
613

614 615 616 617 618
    // get the type
    mp_obj_type_t *type = mp_obj_get_type(fun_in);

    // do the call
    if (type->call != NULL) {
619
        return type->call(fun_in, n_args, n_kw, args);
620
    }
621

622
    #if MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE
623
        mp_raise_TypeError("object not callable");
624
    #else
625 626
        nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_TypeError,
            "'%s' object is not callable", mp_obj_get_type_str(fun_in)));
627
    #endif
628 629
}

630 631
// args contains: fun  self/NULL  arg(0)  ...  arg(n_args-2)  arg(n_args-1)  kw_key(0)  kw_val(0)  ... kw_key(n_kw-1)  kw_val(n_kw-1)
// if n_args==0 and n_kw==0 then there are only fun and self/NULL
632
mp_obj_t mp_call_method_n_kw(size_t n_args, size_t n_kw, const mp_obj_t *args) {
633
    DEBUG_OP_printf("call method (fun=%p, self=%p, n_args=" UINT_FMT ", n_kw=" UINT_FMT ", args=%p)\n", args[0], args[1], n_args, n_kw, args);
634
    int adjust = (args[1] == MP_OBJ_NULL) ? 0 : 1;
Damien George's avatar
Damien George committed
635
    return mp_call_function_n_kw(args[0], n_args + adjust, n_kw, args + 2 - adjust);
636 637
}

638 639 640 641
// This function only needs to be exposed externally when in stackless mode.
#if !MICROPY_STACKLESS
STATIC
#endif
642
void mp_call_prepare_args_n_kw_var(bool have_self, size_t n_args_n_kw, const mp_obj_t *args, mp_call_args_t *out_args) {
643 644 645 646 647 648 649
    mp_obj_t fun = *args++;
    mp_obj_t self = MP_OBJ_NULL;
    if (have_self) {
        self = *args++; // may be MP_OBJ_NULL
    }
    uint n_args = n_args_n_kw & 0xff;
    uint n_kw = (n_args_n_kw >> 8) & 0xff;
650 651
    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
652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676

    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);

    // 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)
    // TODO: optimize one day to avoid constructing new arg array? Will be hard.

    // The new args array
    mp_obj_t *args2;
    uint args2_alloc;
    uint args2_len = 0;

    // 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);
    }

    // Extract the pos_seq sequence to the new args array.
    // Note that it can be arbitrary iterator.
    if (pos_seq == MP_OBJ_NULL) {
        // no sequence

        // allocate memory for the new array of args
        args2_alloc = 1 + n_args + 2 * (n_kw + kw_dict_len);
677
        args2 = mp_nonlocal_alloc(args2_alloc * sizeof(mp_obj_t));
678 679 680 681 682 683 684

        // copy the self
        if (self != MP_OBJ_NULL) {
            args2[args2_len++] = self;
        }

        // copy the fixed pos args
685
        mp_seq_copy(args2 + args2_len, args, n_args, mp_obj_t);
686 687 688 689 690 691
        args2_len += n_args;

    } else if (MP_OBJ_IS_TYPE(pos_seq, &mp_type_tuple) || MP_OBJ_IS_TYPE(pos_seq, &mp_type_list)) {
        // optimise the case of a tuple and list

        // get the items
692
        size_t len;
693 694 695 696 697
        mp_obj_t *items;
        mp_obj_get_array(pos_seq, &len, &items);

        // allocate memory for the new array of args
        args2_alloc = 1 + n_args + len + 2 * (n_kw + kw_dict_len);
698
        args2 = mp_nonlocal_alloc(args2_alloc * sizeof(mp_obj_t));
699 700 701 702 703 704 705

        // copy the self
        if (self != MP_OBJ_NULL) {
            args2[args2_len++] = self;
        }

        // copy the fixed and variable position args
706
        mp_seq_cat(args2 + args2_len, args, n_args, items, len, mp_obj_t);
707 708 709 710 711 712 713
        args2_len += n_args + len;

    } else {
        // generic iterator

        // allocate memory for the new array of args
        args2_alloc = 1 + n_args + 2 * (n_kw + kw_dict_len) + 3;
714
        args2 = mp_nonlocal_alloc(args2_alloc * sizeof(mp_obj_t));
715 716 717 718 719 720 721

        // copy the self
        if (self != MP_OBJ_NULL) {
            args2[args2_len++] = self;
        }

        // copy the fixed position args
722
        mp_seq_copy(args2 + args2_len, args, n_args, mp_obj_t);
723
        args2_len += n_args;
724 725

        // extract the variable position args from the iterator
726 727
        mp_obj_iter_buf_t iter_buf;
        mp_obj_t iterable = mp_getiter(pos_seq, &iter_buf);
728
        mp_obj_t item;
729
        while ((item = mp_iternext(iterable)) != MP_OBJ_STOP_ITERATION) {
730
            if (args2_len >= args2_alloc) {
731
                args2 = mp_nonlocal_realloc(args2, args2_alloc * sizeof(mp_obj_t), args2_alloc * 2 * sizeof(mp_obj_t));
732 733 734 735 736 737 738 739 740 741
                args2_alloc *= 2;
            }
            args2[args2_len++] = item;
        }
    }

    // The size of the args2 array now is the number of positional args.
    uint pos_args_len = args2_len;

    // Copy the fixed kw args.
742
    mp_seq_copy(args2 + args2_len, args + n_args, 2 * n_kw, mp_obj_t);
743 744 745 746 747 748 749 750 751 752
    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
753
        for (size_t i = 0; i < map->alloc; i++) {
754
            if (MP_MAP_SLOT_IS_FILLED(map, i)) {
755 756 757 758 759 760
                // 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_TYPE(key, &mp_type_str)) {
                    key = mp_obj_str_intern(key);
                }
                args2[args2_len++] = key;
761 762 763 764
                args2[args2_len++] = map->table[i].value;
            }
        }
    } else {
765 766 767 768 769 770 771
        // 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);
772
        mp_obj_t iterable = mp_getiter(mp_call_method_n_kw(0, 0, dest), NULL);
773 774 775 776

        mp_obj_t key;
        while ((key = mp_iternext(iterable)) != MP_OBJ_STOP_ITERATION) {
            // expand size of args array if needed
777 778 779 780 781
            if (args2_len + 1 >= args2_alloc) {
                uint new_alloc = args2_alloc * 2;
                if (new_alloc < 4) {
                    new_alloc = 4;
                }
782
                args2 = mp_nonlocal_realloc(args2, args2_alloc * sizeof(mp_obj_t), new_alloc * sizeof(mp_obj_t));
783 784
                args2_alloc = new_alloc;
            }
785

786 787 788 789
            // the key must be a qstr, so intern it if it's a string
            if (MP_OBJ_IS_TYPE(key, &mp_type_str)) {
                key = mp_obj_str_intern(key);
            }
790 791 792 793 794 795 796

            // 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);

            // store the key/value pair in the argument array
797
            args2[args2_len++] = key;
798
            args2[args2_len++] = value;
799 800 801
        }
    }

802 803 804 805 806 807 808
    out_args->fun = fun;
    out_args->args = args2;
    out_args->n_args = pos_args_len;
    out_args->n_kw = (args2_len - pos_args_len) / 2;
    out_args->n_alloc = args2_alloc;
}

809
mp_obj_t mp_call_method_n_kw_var(bool have_self, size_t n_args_n_kw, const mp_obj_t *args) {
810
    mp_call_args_t out_args;
811 812 813
    mp_call_prepare_args_n_kw_var(have_self, n_args_n_kw, args, &out_args);

    mp_obj_t res = mp_call_function_n_kw(out_args.fun, out_args.n_args, out_args.n_kw, out_args.args);
814
    mp_nonlocal_free(out_args.args, out_args.n_alloc * sizeof(mp_obj_t));
815 816 817 818

    return res;
}

819
// unpacked items are stored in reverse order into the array pointed to by items
820
void mp_unpack_sequence(mp_obj_t seq_in, size_t num, mp_obj_t *items) {
821
    size_t seq_len;
822
    if (MP_OBJ_IS_TYPE(seq_in, &mp_type_tuple) || MP_OBJ_IS_TYPE(seq_in, &mp_type_list)) {
823
        mp_obj_t *seq_items;
824
        mp_obj_get_array(seq_in, &seq_len, &seq_items);
825
        if (seq_len < num) {
826
            goto too_short;
827
        } else if (seq_len > num) {
828
            goto too_long;
829
        }
830
        for (size_t i = 0; i < num; i++) {
831 832
            items[i] = seq_items[num - 1 - i];
        }
833
    } else {
834 835
        mp_obj_iter_buf_t iter_buf;
        mp_obj_t iterable = mp_getiter(seq_in, &iter_buf);
836 837

        for (seq_len = 0; seq_len < num; seq_len++) {
Damien George's avatar
Damien George committed
838
            mp_obj_t el = mp_iternext(iterable);
839
            if (el == MP_OBJ_STOP_ITERATION) {
840 841 842 843
                goto too_short;
            }
            items[num - 1 - seq_len] = el;
        }
844
        if (mp_iternext(iterable) != MP_OBJ_STOP_ITERATION) {
845 846
            goto too_long;
        }
847
    }
848 849 850
    return;

too_short:
851
    #if MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE
852
        mp_raise_ValueError("wrong number of values to unpack");
853
    #else
854
        nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_ValueError,
855
            "need more than %d values to unpack", (int)seq_len));
856
    #endif
857
too_long:
858
    #if MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE
859
        mp_raise_ValueError("wrong number of values to unpack");
860
    #else
861
        nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_ValueError,
862
            "too many values to unpack (expected %d)", (int)num));
863
    #endif
864 865
}

866
// unpacked items are stored in reverse order into the array pointed to by items
867 868 869
void mp_unpack_ex(mp_obj_t seq_in, size_t num_in, mp_obj_t *items) {
    size_t num_left = num_in & 0xff;
    size_t num_right = (num_in >> 8) & 0xff;
870
    DEBUG_OP_printf("unpack ex " UINT_FMT " " UINT_FMT "\n", num_left, num_right);
871
    size_t seq_len;
872 873
    if (MP_OBJ_IS_TYPE(seq_in, &mp_type_tuple) || MP_OBJ_IS_TYPE(seq_in, &mp_type_list)) {
        mp_obj_t *seq_items;
874
        mp_obj_get_array(seq_in, &seq_len, &seq_items);
875 876 877
        if (seq_len < num_left + num_right) {
            goto too_short;
        }
878
        for (size_t i = 0; i < num_right; i++) {
879 880 881
            items[i] = seq_items[seq_len - 1 - i];
        }
        items[num_right] = mp_obj_new_list(seq_len - num_left - num_right, seq_items + num_left);
882
        for (size_t i = 0; i < num_left; i++) {
883 884 885 886 887 888 889
            items[num_right + 1 + i] = seq_items[num_left - 1 - i];
        }
    } else {
        // Generic iterable; this gets a bit messy: we unpack known left length to the
        // items destination array, then the rest to a dynamically created list.  Once the
        // iterable is exhausted, we take from this list for the right part of the items.
        // TODO Improve to waste less memory in the dynamically created list.
890
        mp_obj_t iterable = mp_getiter(seq_in, NULL);
891 892 893
        mp_obj_t item;
        for (seq_len = 0; seq_len < num_left; seq_len++) {
            item = mp_iternext(iterable);
894
            if (item == MP_OBJ_STOP_ITERATION) {
895 896 897 898
                goto too_short;
            }
            items[num_left + num_right + 1 - 1 - seq_len] = item;
        }
899
        mp_obj_list_t *rest = MP_OBJ_TO_PTR(mp_obj_new_list(0, NULL));
900
        while ((item = mp_iternext(iterable)) != MP_OBJ_STOP_ITERATION) {
901
            mp_obj_list_append(MP_OBJ_FROM_PTR(rest), item);
902
        }
903
        if (rest->len < num_right) {
904 905
            goto too_short;
        }
906
        items[num_right] = MP_OBJ_FROM_PTR(rest);
907
        for (size_t i = 0; i < num_right; i++) {
908
            items[num_right - 1 - i] = rest->items[rest->len - num_right + i];
909
        }
910
        mp_obj_list_set_len(MP_OBJ_FROM_PTR(rest), rest->len - num_right);
911 912 913 914
    }
    return;

too_short:
915
    #if MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE
916
        mp_raise_ValueError("wrong number of values to unpack");
917
    #else
918
        nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_ValueError,
919
            "need more than %d values to unpack", (int)seq_len));
920
    #endif
921 922
}

923
mp_obj_t mp_load_attr(mp_obj_t base, qstr attr) {
924
    DEBUG_OP_printf("load attr %p.%s\n", base, qstr_str(attr));
925
    // use load_method
926
    mp_obj_t dest[2];
927 928
    mp_load_method(base, attr, dest);
    if (dest[1] == MP_OBJ_NULL) {
929
        // load_method returned just a normal attribute
930
        return dest[0];
931 932 933
    } else {
        // load_method returned a method, so build a bound method object
        return mp_obj_new_bound_meth(dest[0], dest[1]);
Damien's avatar
Damien committed
934 935 936
    }
}

937 938 939 940 941 942 943 944 945 946 947 948
#if MICROPY_BUILTIN_METHOD_CHECK_SELF_ARG

// The following "checked fun" type is local to the mp_convert_member_lookup
// function, and serves to check that the first argument to a builtin function
// has the correct type.

typedef struct _mp_obj_checked_fun_t {
    mp_obj_base_t base;
    const mp_obj_type_t *type;
    mp_obj_t fun;
} mp_obj_checked_fun_t;

949
STATIC mp_obj_t checked_fun_call(mp_obj_t self_in, size_t n_args, size_t n_kw, const mp_obj_t *args) {
950
    mp_obj_checked_fun_t *self = MP_OBJ_TO_PTR(self_in);
951 952 953
    if (n_args > 0) {
        const mp_obj_type_t *arg0_type = mp_obj_get_type(args[0]);
        if (arg0_type != self->type) {
954
            #if MICROPY_ERROR_REPORTING != MICROPY_ERROR_REPORTING_DETAILED
955
                mp_raise_TypeError("argument has wrong type");
956
            #else
957 958
                nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_TypeError,
                    "argument should be a '%q' not a '%q'", self->type->name, arg0_type->name));
959
            #endif
960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975
        }
    }
    return mp_call_function_n_kw(self->fun, n_args, n_kw, args);
}

STATIC const mp_obj_type_t mp_type_checked_fun = {
    { &mp_type_type },
    .name = MP_QSTR_function,
    .call = checked_fun_call,
};

STATIC mp_obj_t mp_obj_new_checked_fun(const mp_obj_type_t *type, mp_obj_t fun) {
    mp_obj_checked_fun_t *o = m_new_obj(mp_obj_checked_fun_t);
    o->base.type = &mp_type_checked_fun;
    o->type = type;
    o->fun = fun;
976
    return MP_OBJ_FROM_PTR(o);
977 978 979 980
}

#endif // MICROPY_BUILTIN_METHOD_CHECK_SELF_ARG

981 982 983 984 985 986 987
// Given a member that was extracted from an instance, convert it correctly
// and put the result in the dest[] array for a possible method call.
// Conversion means dealing with static/class methods, callables, and values.
// see http://docs.python.org/3/howto/descriptor.html
void mp_convert_member_lookup(mp_obj_t self, const mp_obj_type_t *type, mp_obj_t member, mp_obj_t *dest) {
    if (MP_OBJ_IS_TYPE(member, &mp_type_staticmethod)) {
        // return just the function
988
        dest[0] = ((mp_obj_static_class_method_t*)MP_OBJ_TO_PTR(member))->fun;