runtime.c 49.5 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*
 * This file is part of the Micro Python project, http://micropython.org/
 *
 * 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.
 */

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

32
#include "mpconfig.h"
33
#include "nlr.h"
Damien's avatar
Damien committed
34
#include "misc.h"
35
#include "qstr.h"
36
#include "obj.h"
37
#include "objtuple.h"
38
#include "objlist.h"
39
#include "objmodule.h"
40
#include "parsenum.h"
41
#include "runtime0.h"
Damien's avatar
Damien committed
42
#include "runtime.h"
43
#include "emitglue.h"
44
#include "builtin.h"
45
#include "bc.h"
46
#include "smallint.h"
47
#include "objgenerator.h"
48
#include "lexer.h"
49
50
51
#include "parse.h"
#include "parsehelper.h"
#include "compile.h"
52
#include "stackctrl.h"
53
#include "gc.h"
54

55
#if 0 // print debugging info
56
#define DEBUG_PRINT (1)
57
#define DEBUG_printf DEBUG_printf
58
#define DEBUG_OP_printf(...) DEBUG_printf(__VA_ARGS__)
59
#else // don't print debugging info
60
61
#define DEBUG_printf(...) (void)0
#define DEBUG_OP_printf(...) (void)0
62
#endif
Damien's avatar
Damien committed
63

64
65
66
// pending exception object (MP_OBJ_NULL if not pending)
mp_obj_t mp_pending_exception;

67
// locals and globals need to be pointers because they can be the same in outer module scope
68
69
STATIC mp_obj_dict_t *dict_locals;
STATIC mp_obj_dict_t *dict_globals;
70

71
// dictionary for the __main__ module
72
STATIC mp_obj_dict_t dict_main;
73
74
75
76

const mp_obj_module_t mp_module___main__ = {
    .base = { &mp_type_module },
    .name = MP_QSTR___main__,
77
    .globals = (mp_obj_dict_t*)&dict_main,
78
79
};

80
81
82
83
#if MICROPY_CAN_OVERRIDE_BUILTINS
mp_obj_dict_t *mp_module_builtins_override_dict;
#endif

Damien George's avatar
Damien George committed
84
void mp_init(void) {
85
    qstr_init();
Paul Sokolovsky's avatar
Paul Sokolovsky committed
86
    mp_stack_ctrl_init();
87

88
89
90
    // no pending exceptions to start with
    mp_pending_exception = MP_OBJ_NULL;

91
92
93
94
#if MICROPY_ENABLE_EMERGENCY_EXCEPTION_BUF
    mp_init_emergency_exception_buf();
#endif

95
    // call port specific initialization if any
96
97
98
99
#ifdef MICROPY_PORT_INIT_FUNC
    MICROPY_PORT_INIT_FUNC;
#endif

100
101
    // optimization disabled by default
    mp_optimise_value = 0;
102

103
104
    // init global module stuff
    mp_module_init();
105

106
    // initialise the __main__ module
107
108
    mp_obj_dict_init(&dict_main, 1);
    mp_obj_dict_store(&dict_main, MP_OBJ_NEW_QSTR(MP_QSTR___name__), MP_OBJ_NEW_QSTR(MP_QSTR___main__));
109
110

    // locals = globals for outer module (see Objects/frameobject.c/PyFrame_New())
111
    dict_locals = dict_globals = &dict_main;
112
113
114
115
116

    #if MICROPY_CAN_OVERRIDE_BUILTINS
    // start with no extensions to builtins
    mp_module_builtins_override_dict = NULL;
    #endif
Damien's avatar
Damien committed
117
118
}

Damien George's avatar
Damien George committed
119
void mp_deinit(void) {
120
    //mp_obj_dict_free(&dict_main);
121
    mp_module_deinit();
stijn's avatar
stijn committed
122
123
124
125
126

    // call port specific deinitialization if any 
#ifdef MICROPY_PORT_INIT_FUNC
    MICROPY_PORT_DEINIT_FUNC;
#endif
Damien's avatar
Damien committed
127
128
}

129
130
mp_obj_t mp_load_const_int(qstr qstr) {
    DEBUG_OP_printf("load '%s'\n", qstr_str(qstr));
131
    mp_uint_t len;
132
133
134
135
    const byte* data = qstr_data(qstr, &len);
    return mp_parse_num_integer((const char*)data, len, 0);
}

Damien George's avatar
Damien George committed
136
mp_obj_t mp_load_const_dec(qstr qstr) {
Damien's avatar
Damien committed
137
    DEBUG_OP_printf("load '%s'\n", qstr_str(qstr));
138
    mp_uint_t len;
139
    const byte* data = qstr_data(qstr, &len);
140
    return mp_parse_num_decimal((const char*)data, len, true, false);
Damien's avatar
Damien committed
141
142
}

Damien George's avatar
Damien George committed
143
mp_obj_t mp_load_const_str(qstr qstr) {
Damien's avatar
Damien committed
144
    DEBUG_OP_printf("load '%s'\n", qstr_str(qstr));
145
    return MP_OBJ_NEW_QSTR(qstr);
Damien's avatar
Damien committed
146
147
}

Damien George's avatar
Damien George committed
148
mp_obj_t mp_load_const_bytes(qstr qstr) {
149
    DEBUG_OP_printf("load b'%s'\n", qstr_str(qstr));
150
    mp_uint_t len;
151
152
153
154
    const byte *data = qstr_data(qstr, &len);
    return mp_obj_new_bytes(data, len);
}

Damien George's avatar
Damien George committed
155
mp_obj_t mp_load_name(qstr qstr) {
Damien's avatar
Damien committed
156
    // logic: search locals, globals, builtins
157
    DEBUG_OP_printf("load name %s\n", qstr_str(qstr));
158
    // If we're at the outer scope (locals == globals), dispatch to load_global right away
159
160
    if (dict_locals != dict_globals) {
        mp_map_elem_t *elem = mp_map_lookup(&dict_locals->map, MP_OBJ_NEW_QSTR(qstr), MP_MAP_LOOKUP);
161
162
163
        if (elem != NULL) {
            return elem->value;
        }
Damien's avatar
Damien committed
164
    }
165
    return mp_load_global(qstr);
Damien's avatar
Damien committed
166
167
}

Damien George's avatar
Damien George committed
168
mp_obj_t mp_load_global(qstr qstr) {
169
170
    // logic: search globals, builtins
    DEBUG_OP_printf("load global %s\n", qstr_str(qstr));
171
    mp_map_elem_t *elem = mp_map_lookup(&dict_globals->map, MP_OBJ_NEW_QSTR(qstr), MP_MAP_LOOKUP);
172
    if (elem == NULL) {
173
174
175
176
177
178
179
180
181
182
        #if MICROPY_CAN_OVERRIDE_BUILTINS
        if (mp_module_builtins_override_dict != NULL) {
            // lookup in additional dynamic table of builtins first
            elem = mp_map_lookup(&mp_module_builtins_override_dict->map, MP_OBJ_NEW_QSTR(qstr), MP_MAP_LOOKUP);
            if (elem != NULL) {
                return elem->value;
            }
        }
        #endif
        elem = mp_map_lookup((mp_map_t*)&mp_module_builtins_globals.map, MP_OBJ_NEW_QSTR(qstr), MP_MAP_LOOKUP);
183
        if (elem == NULL) {
184
185
186
187
188
189
190
            if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE) {
                nlr_raise(mp_obj_new_exception_msg(&mp_type_NameError,
                    "name not defined"));
            } else {
                nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_NameError,
                    "name '%s' is not defined", qstr_str(qstr)));
            }
191
192
193
        }
    }
    return elem->value;
Damien's avatar
Damien committed
194
195
}

Damien George's avatar
Damien George committed
196
mp_obj_t mp_load_build_class(void) {
Damien's avatar
Damien committed
197
    DEBUG_OP_printf("load_build_class\n");
198
199
200
201
202
203
204
205
206
    #if MICROPY_CAN_OVERRIDE_BUILTINS
    if (mp_module_builtins_override_dict != NULL) {
        // lookup in additional dynamic table of builtins first
        mp_map_elem_t *elem = mp_map_lookup(&mp_module_builtins_override_dict->map, MP_OBJ_NEW_QSTR(MP_QSTR___build_class__), MP_MAP_LOOKUP);
        if (elem != NULL) {
            return elem->value;
        }
    }
    #endif
207
    return (mp_obj_t)&mp_builtin___build_class___obj;
Damien's avatar
Damien committed
208
209
}

Damien George's avatar
Damien George committed
210
void mp_store_name(qstr qstr, mp_obj_t obj) {
211
    DEBUG_OP_printf("store name %s <- %p\n", qstr_str(qstr), obj);
212
    mp_obj_dict_store(dict_locals, MP_OBJ_NEW_QSTR(qstr), obj);
213
214
}

Damien George's avatar
Damien George committed
215
void mp_delete_name(qstr qstr) {
216
    DEBUG_OP_printf("delete name %s\n", qstr_str(qstr));
217
218
    // TODO convert KeyError to NameError if qstr not found
    mp_obj_dict_delete(dict_locals, MP_OBJ_NEW_QSTR(qstr));
219
220
}

Damien George's avatar
Damien George committed
221
void mp_store_global(qstr qstr, mp_obj_t obj) {
222
    DEBUG_OP_printf("store global %s <- %p\n", qstr_str(qstr), obj);
223
    mp_obj_dict_store(dict_globals, MP_OBJ_NEW_QSTR(qstr), obj);
Damien's avatar
Damien committed
224
225
}

226
227
228
229
230
231
void mp_delete_global(qstr qstr) {
    DEBUG_OP_printf("delete global %s\n", qstr_str(qstr));
    // TODO convert KeyError to NameError if qstr not found
    mp_obj_dict_delete(dict_globals, MP_OBJ_NEW_QSTR(qstr));
}

232
mp_obj_t mp_unary_op(mp_uint_t op, mp_obj_t arg) {
233
    DEBUG_OP_printf("unary " UINT_FMT " %p\n", op, arg);
234

235
    if (MP_OBJ_IS_SMALL_INT(arg)) {
236
        mp_int_t val = MP_OBJ_SMALL_INT_VALUE(arg);
Damien's avatar
Damien committed
237
        switch (op) {
Damien George's avatar
Damien George committed
238
            case MP_UNARY_OP_BOOL:
239
                return MP_BOOL(val != 0);
Damien George's avatar
Damien George committed
240
            case MP_UNARY_OP_POSITIVE:
241
                return arg;
Damien George's avatar
Damien George committed
242
            case MP_UNARY_OP_NEGATIVE:
243
244
245
246
247
248
                // check for overflow
                if (val == MP_SMALL_INT_MIN) {
                    return mp_obj_new_int(-val);
                } else {
                    return MP_OBJ_NEW_SMALL_INT(-val);
                }
Damien George's avatar
Damien George committed
249
            case MP_UNARY_OP_INVERT:
250
251
252
253
                return MP_OBJ_NEW_SMALL_INT(~val);
            default:
                assert(0);
                return arg;
254
        }
255
256
257
258
    } 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);
259
            if (result != MP_OBJ_NULL) {
260
261
                return result;
            }
Damien's avatar
Damien committed
262
        }
263
264
265
266
267
268
269
270
271
        if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE) {
            nlr_raise(mp_obj_new_exception_msg(&mp_type_TypeError,
                "unsupported type for operator"));
        } else {
            // TODO specify in error message what the operator is
            nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_TypeError,
                "bad operand type for unary operator: '%s'",
                mp_obj_get_type_str(arg)));
        }
Damien's avatar
Damien committed
272
    }
Damien's avatar
Damien committed
273
274
}

275
mp_obj_t mp_binary_op(mp_uint_t op, mp_obj_t lhs, mp_obj_t rhs) {
276
    DEBUG_OP_printf("binary " UINT_FMT " %p %p\n", op, lhs, rhs);
277
278
279
280
281
282
283
284
285
286

    // 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 +=

287
    // deal with is
Damien George's avatar
Damien George committed
288
    if (op == MP_BINARY_OP_IS) {
289
290
291
        return MP_BOOL(lhs == rhs);
    }

292
    // deal with == and != for all types
Damien George's avatar
Damien George committed
293
    if (op == MP_BINARY_OP_EQUAL || op == MP_BINARY_OP_NOT_EQUAL) {
294
        if (mp_obj_equal(lhs, rhs)) {
Damien George's avatar
Damien George committed
295
            if (op == MP_BINARY_OP_EQUAL) {
296
297
298
299
300
                return mp_const_true;
            } else {
                return mp_const_false;
            }
        } else {
Damien George's avatar
Damien George committed
301
            if (op == MP_BINARY_OP_EQUAL) {
302
303
304
305
306
307
308
309
                return mp_const_false;
            } else {
                return mp_const_true;
            }
        }
    }

    // deal with exception_match for all types
Damien George's avatar
Damien George committed
310
    if (op == MP_BINARY_OP_EXCEPTION_MATCH) {
311
312
        // rhs must be issubclass(rhs, BaseException)
        if (mp_obj_is_exception_type(rhs)) {
313
            if (mp_obj_exception_match(lhs, rhs)) {
314
315
316
317
                return mp_const_true;
            } else {
                return mp_const_false;
            }
318
319
320
321
322
323
324
325
326
327
328
329
        } else if (MP_OBJ_IS_TYPE(rhs, &mp_type_tuple)) {
            mp_obj_tuple_t *tuple = rhs;
            for (mp_uint_t i = 0; i < tuple->len; i++) {
                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;
330
        }
331
        goto unsupported_op;
332
333
    }

334
    if (MP_OBJ_IS_SMALL_INT(lhs)) {
335
        mp_int_t lhs_val = MP_OBJ_SMALL_INT_VALUE(lhs);
336
        if (MP_OBJ_IS_SMALL_INT(rhs)) {
337
            mp_int_t rhs_val = MP_OBJ_SMALL_INT_VALUE(rhs);
338
339
340
            // 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:
341
342
            //      +       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
343
            //      *       checked explicitly
344
345
            //      /       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
346
            //      <<      checked explicitly
347
            switch (op) {
Damien George's avatar
Damien George committed
348
349
350
351
352
353
354
355
                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: {
356
357
                    if (rhs_val < 0) {
                        // negative shift not allowed
358
                        nlr_raise(mp_obj_new_exception_msg(&mp_type_ValueError, "negative shift count"));
359
360
361
362
363
364
365
366
367
368
                    } else if (rhs_val >= BITS_PER_WORD || lhs_val > (MP_SMALL_INT_MAX >> rhs_val) || lhs_val < (MP_SMALL_INT_MIN >> rhs_val)) {
                        // 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
369
370
                case MP_BINARY_OP_RSHIFT:
                case MP_BINARY_OP_INPLACE_RSHIFT:
371
372
                    if (rhs_val < 0) {
                        // negative shift not allowed
373
                        nlr_raise(mp_obj_new_exception_msg(&mp_type_ValueError, "negative shift count"));
374
375
                    } else {
                        // standard precision is enough for right-shift
376
377
378
379
380
                        if (rhs_val >= BITS_PER_WORD) {
                            // Shifting to big amounts is underfined behavior
                            // in C and is CPU-dependent; propagate sign bit.
                            rhs_val = BITS_PER_WORD - 1;
                        }
381
382
383
                        lhs_val >>= rhs_val;
                    }
                    break;
Damien George's avatar
Damien George committed
384
385
386
387
388
389
                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: {
390

391
                    // If long long type exists and is larger than mp_int_t, then
392
                    // we can use the following code to perform overflow-checked multiplication.
393
                    // Otherwise (eg in x64 case) we must use mp_small_int_mul_overflow.
394
395
396
397
398
399
400
401
                    #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
402
                        lhs_val = (mp_int_t)res;
403
404
405
                    }
                    #endif

406
407
408
409
410
411
412
413
                    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);
                    }
414
415
                    break;
                }
Damien George's avatar
Damien George committed
416
417
                case MP_BINARY_OP_FLOOR_DIVIDE:
                case MP_BINARY_OP_INPLACE_FLOOR_DIVIDE:
418
419
420
                    if (rhs_val == 0) {
                        goto zero_division;
                    }
421
                    lhs_val = mp_small_int_floor_divide(lhs_val, rhs_val);
422
                    break;
423

424
                #if MICROPY_PY_BUILTINS_FLOAT
Damien George's avatar
Damien George committed
425
                case MP_BINARY_OP_TRUE_DIVIDE:
426
427
                case MP_BINARY_OP_INPLACE_TRUE_DIVIDE:
                    if (rhs_val == 0) {
428
                        goto zero_division;
429
430
                    }
                    return mp_obj_new_float((mp_float_t)lhs_val / (mp_float_t)rhs_val);
431
                #endif
432

Damien George's avatar
Damien George committed
433
                case MP_BINARY_OP_MODULO:
434
435
                case MP_BINARY_OP_INPLACE_MODULO: {
                    lhs_val = mp_small_int_modulo(lhs_val, rhs_val);
436
437
                    break;
                }
438

Damien George's avatar
Damien George committed
439
440
                case MP_BINARY_OP_POWER:
                case MP_BINARY_OP_INPLACE_POWER:
441
                    if (rhs_val < 0) {
442
                        #if MICROPY_PY_BUILTINS_FLOAT
443
444
445
                        lhs = mp_obj_new_float(lhs_val);
                        goto generic_binary_op;
                        #else
446
                        nlr_raise(mp_obj_new_exception_msg(&mp_type_ValueError, "negative power with no float support"));
447
448
                        #endif
                    } else {
449
                        mp_int_t ans = 1;
450
451
                        while (rhs_val > 0) {
                            if (rhs_val & 1) {
452
                                if (mp_small_int_mul_overflow(ans, lhs_val)) {
453
454
                                    goto power_overflow;
                                }
455
                                ans *= lhs_val;
456
457
458
                            }
                            if (rhs_val == 1) {
                                break;
459
460
                            }
                            rhs_val /= 2;
461
                            if (mp_small_int_mul_overflow(lhs_val, lhs_val)) {
462
463
                                goto power_overflow;
                            }
464
                            lhs_val *= lhs_val;
465
                        }
466
                        lhs_val = ans;
467
                    }
468
                    break;
469
470
471
472
473
474

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

Damien George's avatar
Damien George committed
475
476
477
478
                case MP_BINARY_OP_LESS: return MP_BOOL(lhs_val < rhs_val); break;
                case MP_BINARY_OP_MORE: return MP_BOOL(lhs_val > rhs_val); break;
                case MP_BINARY_OP_LESS_EQUAL: return MP_BOOL(lhs_val <= rhs_val); break;
                case MP_BINARY_OP_MORE_EQUAL: return MP_BOOL(lhs_val >= rhs_val); break;
479

480
481
                default:
                    goto unsupported_op;
482
            }
483
            // TODO: We just should make mp_obj_new_int() inline and use that
484
            if (MP_SMALL_INT_FITS(lhs_val)) {
485
                return MP_OBJ_NEW_SMALL_INT(lhs_val);
486
487
            } else {
                return mp_obj_new_int(lhs_val);
488
            }
489
#if MICROPY_PY_BUILTINS_FLOAT
490
        } else if (MP_OBJ_IS_TYPE(rhs, &mp_type_float)) {
491
492
493
494
495
496
            mp_obj_t res = mp_obj_float_binary_op(op, lhs_val, rhs);
            if (res == MP_OBJ_NULL) {
                goto unsupported_op;
            } else {
                return res;
            }
497
#if MICROPY_PY_BUILTINS_COMPLEX
498
        } else if (MP_OBJ_IS_TYPE(rhs, &mp_type_complex)) {
499
500
501
502
503
504
            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;
            }
505
#endif
506
#endif
507
        }
508
    }
509

510
    /* deal with `in`
511
512
     *
     * NOTE `a in b` is `b.__contains__(a)`, hence why the generic dispatch
Damien George's avatar
Damien George committed
513
     * needs to go below with swapped arguments
514
     */
Damien George's avatar
Damien George committed
515
    if (op == MP_BINARY_OP_IN) {
516
517
518
        mp_obj_type_t *type = mp_obj_get_type(rhs);
        if (type->binary_op != NULL) {
            mp_obj_t res = type->binary_op(op, rhs, lhs);
519
            if (res != MP_OBJ_NULL) {
520
                return res;
John R. Lenton's avatar
John R. Lenton committed
521
            }
522
523
524
        }
        if (type->getiter != NULL) {
            /* second attempt, walk the iterator */
Damien George's avatar
Damien George committed
525
            mp_obj_t iter = mp_getiter(rhs);
526
            mp_obj_t next;
527
            while ((next = mp_iternext(iter)) != MP_OBJ_STOP_ITERATION) {
528
                if (mp_obj_equal(next, lhs)) {
529
                    return mp_const_true;
John R. Lenton's avatar
John R. Lenton committed
530
                }
531
            }
532
            return mp_const_false;
533
534
        }

535
536
537
538
539
540
541
        if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE) {
            nlr_raise(mp_obj_new_exception_msg(&mp_type_TypeError,
                "object not iterable"));
        } else {
            nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_TypeError,
                "'%s' object is not iterable", mp_obj_get_type_str(rhs)));
        }
542
543
    }

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

555
556
    // TODO implement dispatch for reverse binary ops

557
unsupported_op:
558
559
560
561
562
563
564
565
566
    if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE) {
        nlr_raise(mp_obj_new_exception_msg(&mp_type_TypeError,
            "unsupported type for operator"));
    } else {
        // TODO specify in error message what the operator is
        nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_TypeError,
            "unsupported operand types for binary operator: '%s', '%s'",
            mp_obj_get_type_str(lhs), mp_obj_get_type_str(rhs)));
    }
567
568

zero_division:
569
    nlr_raise(mp_obj_new_exception_msg(&mp_type_ZeroDivisionError, "division by zero"));
Damien's avatar
Damien committed
570
571
}

Damien George's avatar
Damien George committed
572
573
mp_obj_t mp_call_function_0(mp_obj_t fun) {
    return mp_call_function_n_kw(fun, 0, 0, NULL);
574
575
}

Damien George's avatar
Damien George committed
576
577
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);
578
579
}

Damien George's avatar
Damien George committed
580
mp_obj_t mp_call_function_2(mp_obj_t fun, mp_obj_t arg1, mp_obj_t arg2) {
581
    mp_obj_t args[2];
582
583
    args[0] = arg1;
    args[1] = arg2;
Damien George's avatar
Damien George committed
584
    return mp_call_function_n_kw(fun, 2, 0, args);
585
586
}

587
// args contains, eg: arg0  arg1  key0  value0  key1  value1
588
mp_obj_t mp_call_function_n_kw(mp_obj_t fun_in, mp_uint_t n_args, mp_uint_t n_kw, const mp_obj_t *args) {
589
590
    // 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
591

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

594
595
596
597
598
    // get the type
    mp_obj_type_t *type = mp_obj_get_type(fun_in);

    // do the call
    if (type->call != NULL) {
599
        return type->call(fun_in, n_args, n_kw, args);
600
    }
601

602
603
604
605
606
607
608
    if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE) {
        nlr_raise(mp_obj_new_exception_msg(&mp_type_TypeError,
            "object not callable"));
    } else {
        nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_TypeError,
            "'%s' object is not callable", mp_obj_get_type_str(fun_in)));
    }
609
610
}

611
612
// 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
613
mp_obj_t mp_call_method_n_kw(mp_uint_t n_args, mp_uint_t n_kw, const mp_obj_t *args) {
614
    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);
615
    int adjust = (args[1] == NULL) ? 0 : 1;
Damien George's avatar
Damien George committed
616
    return mp_call_function_n_kw(args[0], n_args + adjust, n_kw, args + 2 - adjust);
617
618
}

619
mp_obj_t mp_call_method_n_kw_var(bool have_self, mp_uint_t n_args_n_kw, const mp_obj_t *args) {
620
621
622
623
624
625
626
    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;
627
628
    mp_obj_t pos_seq = args[n_args + 2 * n_kw]; // map be MP_OBJ_NULL
    mp_obj_t kw_dict = args[n_args + 2 * n_kw + 1]; // map be MP_OBJ_NULL
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661

    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);
        args2 = m_new(mp_obj_t, args2_alloc);

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

        // copy the fixed pos args
662
        mp_seq_copy(args2 + args2_len, args, n_args, mp_obj_t);
663
664
665
666
667
668
        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
669
        mp_uint_t len;
670
671
672
673
674
675
676
677
678
679
680
681
682
        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);
        args2 = m_new(mp_obj_t, args2_alloc);

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

        // copy the fixed and variable position args
683
        mp_seq_cat(args2 + args2_len, args, n_args, items, len, mp_obj_t);
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
        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;
        args2 = m_new(mp_obj_t, args2_alloc);

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

        // copy the fixed position args
699
        mp_seq_copy(args2 + args2_len, args, n_args, mp_obj_t);
700
701
702
703

        // extract the variable position args from the iterator
        mp_obj_t iterable = mp_getiter(pos_seq);
        mp_obj_t item;
704
        while ((item = mp_iternext(iterable)) != MP_OBJ_STOP_ITERATION) {
705
706
707
708
709
710
711
712
713
714
715
716
            if (args2_len >= args2_alloc) {
                args2 = m_renew(mp_obj_t, args2, args2_alloc, args2_alloc * 2);
                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.
717
    mp_seq_copy(args2 + args2_len, args + n_args, 2 * n_kw, mp_obj_t);
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
    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 (uint i = 0; i < map->alloc; i++) {
            if (map->table[i].key != MP_OBJ_NULL) {
                args2[args2_len++] = map->table[i].key;
                args2[args2_len++] = map->table[i].value;
            }
        }
    } else {
        // generic mapping
        // TODO is calling 'items' on the mapping the correct thing to do here?
        mp_obj_t dest[2];
        mp_load_method(kw_dict, MP_QSTR_items, dest);
        mp_obj_t iterable = mp_getiter(mp_call_method_n_kw(0, 0, dest));
        mp_obj_t item;
741
        while ((item = mp_iternext(iterable)) != MP_OBJ_STOP_ITERATION) {
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
            if (args2_len + 1 >= args2_alloc) {
                uint new_alloc = args2_alloc * 2;
                if (new_alloc < 4) {
                    new_alloc = 4;
                }
                args2 = m_renew(mp_obj_t, args2, args2_alloc, new_alloc);
                args2_alloc = new_alloc;
            }
            mp_obj_t *items;
            mp_obj_get_array_fixed_n(item, 2, &items);
            args2[args2_len++] = items[0];
            args2[args2_len++] = items[1];
        }
    }

    mp_obj_t res = mp_call_function_n_kw(fun, pos_args_len, (args2_len - pos_args_len) / 2, args2);
    m_del(mp_obj_t, args2, args2_alloc);

    return res;
}

763
// unpacked items are stored in reverse order into the array pointed to by items
764
void mp_unpack_sequence(mp_obj_t seq_in, mp_uint_t num, mp_obj_t *items) {
765
    mp_uint_t seq_len;
766
    if (MP_OBJ_IS_TYPE(seq_in, &mp_type_tuple) || MP_OBJ_IS_TYPE(seq_in, &mp_type_list)) {
767
        mp_obj_t *seq_items;
768
        if (MP_OBJ_IS_TYPE(seq_in, &mp_type_tuple)) {
769
770
771
            mp_obj_tuple_get(seq_in, &seq_len, &seq_items);
        } else {
            mp_obj_list_get(seq_in, &seq_len, &seq_items);
772
        }
773
        if (seq_len < num) {
774
            goto too_short;
775
        } else if (seq_len > num) {
776
            goto too_long;
777
        }
778
        for (mp_uint_t i = 0; i < num; i++) {
779
780
            items[i] = seq_items[num - 1 - i];
        }
781
    } else {
Damien George's avatar
Damien George committed
782
        mp_obj_t iterable = mp_getiter(seq_in);
783
784

        for (seq_len = 0; seq_len < num; seq_len++) {
Damien George's avatar
Damien George committed
785
            mp_obj_t el = mp_iternext(iterable);
786
            if (el == MP_OBJ_STOP_ITERATION) {
787
788
789
790
                goto too_short;
            }
            items[num - 1 - seq_len] = el;
        }
791
        if (mp_iternext(iterable) != MP_OBJ_STOP_ITERATION) {
792
793
            goto too_long;
        }
794
    }
795
796
797
    return;

too_short:
798
799
800
801
802
803
804
    if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE) {
        nlr_raise(mp_obj_new_exception_msg(&mp_type_ValueError,
            "wrong number of values to unpack"));
    } else {
        nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_ValueError,
            "need more than %d values to unpack", seq_len));
    }
805
too_long:
806
807
808
809
810
811
812
    if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE) {
        nlr_raise(mp_obj_new_exception_msg(&mp_type_ValueError,
            "wrong number of values to unpack"));
    } else {
        nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_ValueError,
            "too many values to unpack (expected %d)", num));
    }
813
814
}

815
// unpacked items are stored in reverse order into the array pointed to by items
816
817
818
void mp_unpack_ex(mp_obj_t seq_in, mp_uint_t num_in, mp_obj_t *items) {
    mp_uint_t num_left = num_in & 0xff;
    mp_uint_t num_right = (num_in >> 8) & 0xff;
819
    DEBUG_OP_printf("unpack ex " UINT_FMT " " UINT_FMT "\n", num_left, num_right);
820
    mp_uint_t seq_len;
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
    if (MP_OBJ_IS_TYPE(seq_in, &mp_type_tuple) || MP_OBJ_IS_TYPE(seq_in, &mp_type_list)) {
        mp_obj_t *seq_items;
        if (MP_OBJ_IS_TYPE(seq_in, &mp_type_tuple)) {
            mp_obj_tuple_get(seq_in, &seq_len, &seq_items);
        } else {
            if (num_left == 0 && num_right == 0) {
                // *a, = b # sets a to b if b is a list
                items[0] = seq_in;
                return;
            }
            mp_obj_list_get(seq_in, &seq_len, &seq_items);
        }
        if (seq_len < num_left + num_right) {
            goto too_short;
        }
836
        for (mp_uint_t i = 0; i < num_right; i++) {
837
838
839
            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);
840
        for (mp_uint_t i = 0; i < num_left; i++) {
841
842
843
844
845
846
847
848
849
850
851
            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.
        mp_obj_t iterable = mp_getiter(seq_in);
        mp_obj_t item;
        for (seq_len = 0; seq_len < num_left; seq_len++) {
            item = mp_iternext(iterable);
852
            if (item == MP_OBJ_STOP_ITERATION) {
853
854
855
856
                goto too_short;
            }
            items[num_left + num_right + 1 - 1 - seq_len] = item;
        }
857
        mp_obj_list_t *rest = mp_obj_new_list(0, NULL);
858
        while ((item = mp_iternext(iterable)) != MP_OBJ_STOP_ITERATION) {
859
860
            mp_obj_list_append(rest, item);
        }
861
        if (rest->len < num_right) {
862
863
864
            goto too_short;
        }
        items[num_right] = rest;
865
        for (mp_uint_t i = 0; i < num_right; i++) {
866
            items[num_right - 1 - i] = rest->items[rest->len - num_right + i];
867
        }
868
        mp_obj_list_set_len(rest, rest->len - num_right);
869
870
871
872
    }
    return;

too_short:
873
874
875
876
877
878
879
    if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE) {
        nlr_raise(mp_obj_new_exception_msg(&mp_type_ValueError,
            "wrong number of values to unpack"));
    } else {
        nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_ValueError,
            "need more than %d values to unpack", seq_len));
    }
880
881
}

882
mp_obj_t mp_load_attr(mp_obj_t base, qstr attr) {
883
    DEBUG_OP_printf("load attr %p.%s\n", base, qstr_str(attr));
884
    // use load_method
885
    mp_obj_t dest[2];
886
887
    mp_load_method(base, attr, dest);
    if (dest[1] == MP_OBJ_NULL) {
888
        // load_method returned just a normal attribute
889
        return dest[0];
890
891
892
    } 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
893
894
895
    }
}

896
897
898
// no attribute found, returns:     dest[0] == MP_OBJ_NULL, dest[1] == MP_OBJ_NULL
// normal attribute found, returns: dest[0] == <attribute>, dest[1] == MP_OBJ_NULL
// method attribute found, returns: dest[0] == <method>,    dest[1] == <self>
Damien George's avatar
Damien George committed
899
void mp_load_method_maybe(mp_obj_t base, qstr attr, mp_obj_t *dest) {
900
901
902
903
904
905
906
    // clear output to indicate no attribute/method found yet
    dest[0] = MP_OBJ_NULL;
    dest[1] = MP_OBJ_NULL;

    // get the type
    mp_obj_type_t *type = mp_obj_get_type(base);

Damien George's avatar
Damien George committed
907
908
    // look for built-in names
    if (0) {
909
#if MICROPY_CPYTHON_COMPAT
Damien George's avatar
Damien George committed
910
911
912
    } else if (attr == MP_QSTR___class__) {
        // a.__class__ is equivalent to type(a)
        dest[0] = type;
913
#endif
Damien George's avatar
Damien George committed
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930

    } else if (attr == MP_QSTR___next__ && type->iternext != NULL) {
        dest[0] = (mp_obj_t)&mp_builtin_next_obj;
        dest[1] = base;

    } else if (type->load_attr != NULL) {
        // this type can do its own load, so call it
        type->load_attr(base, attr, dest);

    } else if (type->locals_dict != NULL) {
        // generic method lookup
        // this is a lookup in the object (ie not class or type)
        assert(MP_OBJ_IS_TYPE(type->locals_dict, &mp_type_dict)); // Micro Python restriction, for now
        mp_map_t *locals_map = mp_obj_dict_get_map(type->locals_dict);
        mp_map_elem_t *elem = mp_map_lookup(locals_map, MP_OBJ_NEW_QSTR(attr), MP_MAP_LOOKUP);
        if (elem != NULL) {
            // check if the methods are functions, static or class methods
931
            // see http://docs.python.org/3/howto/descriptor.html
Damien George's avatar
Damien George committed
932
933
934
935
936
937
938
            if (MP_OBJ_IS_TYPE(elem->value, &mp_type_staticmethod)) {
                // return just the function
                dest[0] = ((mp_obj_static_class_method_t*)elem->value)->fun;
            } else if (MP_OBJ_IS_TYPE(elem->value, &mp_type_classmethod)) {
                // return a bound method, with self being the type of this object
                dest[0] = ((mp_obj_static_class_method_t*)elem->value)->fun;
                dest[1] = mp_obj_get_type(base);
939
940
941
            } else if (MP_OBJ_IS_TYPE(elem->value, &mp_type_type)) {
                // Don't try to bind types
                dest[0] = elem->value;
Damien George's avatar
Damien George committed
942
943
944
945
946
947
948
            } else if (mp_obj_is_callable(elem->value)) {
                // return a bound method, with self being this object
                dest[0] = elem->value;
                dest[1] = base;
            } else {
                // class member is a value, so just return that value
                dest[0] = elem->value;
Damien's avatar
Damien committed
949
950
            }
        }
951
    }
952
953
}

Damien George's avatar
Damien George committed
954
void mp_load_method(mp_obj_t base, qstr attr, mp_obj_t *dest) {
955
956
    DEBUG_OP_printf("load method %p.%s\n", base, qstr_str(attr));

Damien George's avatar
Damien George committed
957
    mp_load_method_maybe(base, attr, dest);
958

959
    if (dest[0] == MP_OBJ_NULL) {
960
        // no attribute/method called attr
961
962
963
        if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE) {
            nlr_raise(mp_obj_new_exception_msg(&mp_type_AttributeError,
                "no such attribute"));
964
        } else {
965
966
967
968
969
970
971
972
973
974
            // following CPython, we give a more detailed error message for type objects
            if (MP_OBJ_IS_TYPE(base, &mp_type_type)) {
                nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_AttributeError,
                    "type object '%s' has no attribute '%s'",
                    qstr_str(((mp_obj_type_t*)base)->name), qstr_str(attr)));
            } else {
                nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_AttributeError,
                    "'%s' object has no attribute '%s'",
                    mp_obj_get_type_str(base), qstr_str(attr)));
            }
975
976
        }
    }
977
978
}

Damien George's avatar
Damien George committed
979
void mp_store_attr(mp_obj_t base, qstr attr, mp_obj_t value) {
Damien's avatar
Damien committed
980
    DEBUG_OP_printf("store attr %p.%s <- %p\n", base, qstr_str(attr), value);
981
982
983
984
985
    mp_obj_type_t *type = mp_obj_get_type(base);
    if (type->store_attr != NULL) {
        if (type->store_attr(base, attr, value)) {
            return;
        }
986
    }
987
988
989
990
991
992
993
994
    if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE) {
        nlr_raise(mp_obj_new_exception_msg(&mp_type_AttributeError,
            "no such attribute"));
    } else {
        nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_AttributeError,
            "'%s' object has no attribute '%s'",
            mp_obj_get_type_str(base), qstr_str(attr)));
    }
995
996
}