runtime.c 43.2 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.
 */

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

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

51
#if 0 // print debugging info
52
#define DEBUG_PRINT (1)
53
#define DEBUG_printf DEBUG_printf
54
#define DEBUG_OP_printf(...) DEBUG_printf(__VA_ARGS__)
55
#else // don't print debugging info
56
57
#define DEBUG_printf(...) (void)0
#define DEBUG_OP_printf(...) (void)0
58
#endif
Damien's avatar
Damien committed
59

60
// locals and globals need to be pointers because they can be the same in outer module scope
61
62
STATIC mp_obj_dict_t *dict_locals;
STATIC mp_obj_dict_t *dict_globals;
63

64
// dictionary for the __main__ module
65
STATIC mp_obj_dict_t dict_main;
66
67
68
69

const mp_obj_module_t mp_module___main__ = {
    .base = { &mp_type_module },
    .name = MP_QSTR___main__,
70
    .globals = (mp_obj_dict_t*)&dict_main,
71
72
};

Damien George's avatar
Damien George committed
73
void mp_init(void) {
74
    qstr_init();
Paul Sokolovsky's avatar
Paul Sokolovsky committed
75
    mp_stack_ctrl_init();
76

77
78
79
80
#if MICROPY_ENABLE_EMERGENCY_EXCEPTION_BUF
    mp_init_emergency_exception_buf();
#endif

81
    // call port specific initialization if any
82
83
84
85
#ifdef MICROPY_PORT_INIT_FUNC
    MICROPY_PORT_INIT_FUNC;
#endif

86
87
    // optimization disabled by default
    mp_optimise_value = 0;
88

89
90
    // init global module stuff
    mp_module_init();
91

92
    // initialise the __main__ module
93
94
    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__));
95
96

    // locals = globals for outer module (see Objects/frameobject.c/PyFrame_New())
97
    dict_locals = dict_globals = &dict_main;
Damien's avatar
Damien committed
98
99
}

Damien George's avatar
Damien George committed
100
void mp_deinit(void) {
101
    //mp_obj_dict_free(&dict_main);
102
    mp_module_deinit();
stijn's avatar
stijn committed
103
104
105
106
107

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

110
111
112
113
114
115
116
mp_obj_t mp_load_const_int(qstr qstr) {
    DEBUG_OP_printf("load '%s'\n", qstr_str(qstr));
    uint len;
    const byte* data = qstr_data(qstr, &len);
    return mp_parse_num_integer((const char*)data, len, 0);
}

Damien George's avatar
Damien George committed
117
mp_obj_t mp_load_const_dec(qstr qstr) {
Damien's avatar
Damien committed
118
    DEBUG_OP_printf("load '%s'\n", qstr_str(qstr));
119
120
    uint len;
    const byte* data = qstr_data(qstr, &len);
121
    return mp_parse_num_decimal((const char*)data, len, true, false);
Damien's avatar
Damien committed
122
123
}

Damien George's avatar
Damien George committed
124
mp_obj_t mp_load_const_str(qstr qstr) {
Damien's avatar
Damien committed
125
    DEBUG_OP_printf("load '%s'\n", qstr_str(qstr));
126
    return MP_OBJ_NEW_QSTR(qstr);
Damien's avatar
Damien committed
127
128
}

Damien George's avatar
Damien George committed
129
mp_obj_t mp_load_const_bytes(qstr qstr) {
130
131
132
133
134
135
    DEBUG_OP_printf("load b'%s'\n", qstr_str(qstr));
    uint len;
    const byte *data = qstr_data(qstr, &len);
    return mp_obj_new_bytes(data, len);
}

Damien George's avatar
Damien George committed
136
mp_obj_t mp_load_name(qstr qstr) {
Damien's avatar
Damien committed
137
    // logic: search locals, globals, builtins
138
    DEBUG_OP_printf("load name %s\n", qstr_str(qstr));
139
    // If we're at the outer scope (locals == globals), dispatch to load_global right away
140
141
    if (dict_locals != dict_globals) {
        mp_map_elem_t *elem = mp_map_lookup(&dict_locals->map, MP_OBJ_NEW_QSTR(qstr), MP_MAP_LOOKUP);
142
143
144
        if (elem != NULL) {
            return elem->value;
        }
Damien's avatar
Damien committed
145
    }
146
    return mp_load_global(qstr);
Damien's avatar
Damien committed
147
148
}

Damien George's avatar
Damien George committed
149
mp_obj_t mp_load_global(qstr qstr) {
150
151
    // logic: search globals, builtins
    DEBUG_OP_printf("load global %s\n", qstr_str(qstr));
152
    mp_map_elem_t *elem = mp_map_lookup(&dict_globals->map, MP_OBJ_NEW_QSTR(qstr), MP_MAP_LOOKUP);
153
    if (elem == NULL) {
154
155
        // TODO lookup in dynamic table of builtins first
        elem = mp_map_lookup((mp_map_t*)&mp_builtin_object_dict_obj.map, MP_OBJ_NEW_QSTR(qstr), MP_MAP_LOOKUP);
156
        if (elem == NULL) {
157
            nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_NameError, "name '%s' is not defined", qstr_str(qstr)));
158
159
160
        }
    }
    return elem->value;
Damien's avatar
Damien committed
161
162
}

Damien George's avatar
Damien George committed
163
mp_obj_t mp_load_build_class(void) {
Damien's avatar
Damien committed
164
    DEBUG_OP_printf("load_build_class\n");
165
166
167
    // TODO lookup __build_class__ in dynamic table of builtins first
    // ... else no user-defined __build_class__, return builtin one
    return (mp_obj_t)&mp_builtin___build_class___obj;
Damien's avatar
Damien committed
168
169
}

Damien George's avatar
Damien George committed
170
void mp_store_name(qstr qstr, mp_obj_t obj) {
171
    DEBUG_OP_printf("store name %s <- %p\n", qstr_str(qstr), obj);
172
    mp_obj_dict_store(dict_locals, MP_OBJ_NEW_QSTR(qstr), obj);
173
174
}

Damien George's avatar
Damien George committed
175
void mp_delete_name(qstr qstr) {
176
    DEBUG_OP_printf("delete name %s\n", qstr_str(qstr));
177
178
    // TODO convert KeyError to NameError if qstr not found
    mp_obj_dict_delete(dict_locals, MP_OBJ_NEW_QSTR(qstr));
179
180
}

Damien George's avatar
Damien George committed
181
void mp_store_global(qstr qstr, mp_obj_t obj) {
182
    DEBUG_OP_printf("store global %s <- %p\n", qstr_str(qstr), obj);
183
    mp_obj_dict_store(dict_globals, MP_OBJ_NEW_QSTR(qstr), obj);
Damien's avatar
Damien committed
184
185
}

186
187
188
189
190
191
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));
}

192
mp_obj_t mp_unary_op(mp_uint_t op, mp_obj_t arg) {
193
    DEBUG_OP_printf("unary " UINT_FMT " %p\n", op, arg);
194

195
    if (MP_OBJ_IS_SMALL_INT(arg)) {
196
        mp_int_t val = MP_OBJ_SMALL_INT_VALUE(arg);
Damien's avatar
Damien committed
197
        switch (op) {
Damien George's avatar
Damien George committed
198
            case MP_UNARY_OP_BOOL:
199
                return MP_BOOL(val != 0);
Damien George's avatar
Damien George committed
200
            case MP_UNARY_OP_POSITIVE:
201
                return arg;
Damien George's avatar
Damien George committed
202
            case MP_UNARY_OP_NEGATIVE:
203
204
205
206
207
208
                // 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
209
            case MP_UNARY_OP_INVERT:
210
211
212
213
                return MP_OBJ_NEW_SMALL_INT(~val);
            default:
                assert(0);
                return arg;
214
        }
215
216
217
218
    } 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);
219
            if (result != MP_OBJ_NULL) {
220
221
                return result;
            }
Damien's avatar
Damien committed
222
        }
223
        // TODO specify in error message what the operator is
224
        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
225
    }
Damien's avatar
Damien committed
226
227
}

228
mp_obj_t mp_binary_op(mp_uint_t op, mp_obj_t lhs, mp_obj_t rhs) {
229
    DEBUG_OP_printf("binary " UINT_FMT " %p %p\n", op, lhs, rhs);
230
231
232
233
234
235
236
237
238
239

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

240
    // deal with is
Damien George's avatar
Damien George committed
241
    if (op == MP_BINARY_OP_IS) {
242
243
244
        return MP_BOOL(lhs == rhs);
    }

245
    // deal with == and != for all types
Damien George's avatar
Damien George committed
246
    if (op == MP_BINARY_OP_EQUAL || op == MP_BINARY_OP_NOT_EQUAL) {
247
        if (mp_obj_equal(lhs, rhs)) {
Damien George's avatar
Damien George committed
248
            if (op == MP_BINARY_OP_EQUAL) {
249
250
251
252
253
                return mp_const_true;
            } else {
                return mp_const_false;
            }
        } else {
Damien George's avatar
Damien George committed
254
            if (op == MP_BINARY_OP_EQUAL) {
255
256
257
258
259
260
261
262
                return mp_const_false;
            } else {
                return mp_const_true;
            }
        }
    }

    // deal with exception_match for all types
Damien George's avatar
Damien George committed
263
    if (op == MP_BINARY_OP_EXCEPTION_MATCH) {
264
265
        // rhs must be issubclass(rhs, BaseException)
        if (mp_obj_is_exception_type(rhs)) {
266
            if (mp_obj_exception_match(lhs, rhs)) {
267
268
269
270
                return mp_const_true;
            } else {
                return mp_const_false;
            }
271
272
273
274
275
276
277
278
279
280
281
282
        } 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;
283
        }
284
        goto unsupported_op;
285
286
    }

287
    if (MP_OBJ_IS_SMALL_INT(lhs)) {
288
        mp_int_t lhs_val = MP_OBJ_SMALL_INT_VALUE(lhs);
289
        if (MP_OBJ_IS_SMALL_INT(rhs)) {
290
            mp_int_t rhs_val = MP_OBJ_SMALL_INT_VALUE(rhs);
291
292
293
            // 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:
294
295
            //      +       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
296
            //      *       checked explicitly
297
298
            //      /       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
299
            //      <<      checked explicitly
300
            switch (op) {
Damien George's avatar
Damien George committed
301
302
303
304
305
306
307
308
                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: {
309
310
                    if (rhs_val < 0) {
                        // negative shift not allowed
311
                        nlr_raise(mp_obj_new_exception_msg(&mp_type_ValueError, "negative shift count"));
312
313
314
315
316
317
318
319
320
321
                    } 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
322
323
                case MP_BINARY_OP_RSHIFT:
                case MP_BINARY_OP_INPLACE_RSHIFT:
324
325
                    if (rhs_val < 0) {
                        // negative shift not allowed
326
                        nlr_raise(mp_obj_new_exception_msg(&mp_type_ValueError, "negative shift count"));
327
328
329
330
331
                    } else {
                        // standard precision is enough for right-shift
                        lhs_val >>= rhs_val;
                    }
                    break;
Damien George's avatar
Damien George committed
332
333
334
335
336
337
                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: {
338

339
                    // If long long type exists and is larger than mp_int_t, then
340
                    // we can use the following code to perform overflow-checked multiplication.
341
                    // Otherwise (eg in x64 case) we must use mp_small_int_mul_overflow.
342
343
344
345
346
347
348
349
                    #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
350
                        lhs_val = (mp_int_t)res;
351
352
353
                    }
                    #endif

354
355
356
357
358
359
360
361
                    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);
                    }
362
363
                    break;
                }
Damien George's avatar
Damien George committed
364
365
                case MP_BINARY_OP_FLOOR_DIVIDE:
                case MP_BINARY_OP_INPLACE_FLOOR_DIVIDE:
366
367
368
                    if (rhs_val == 0) {
                        goto zero_division;
                    }
369
                    lhs_val = mp_small_int_floor_divide(lhs_val, rhs_val);
370
                    break;
371

372
                #if MICROPY_PY_BUILTINS_FLOAT
Damien George's avatar
Damien George committed
373
                case MP_BINARY_OP_TRUE_DIVIDE:
374
375
                case MP_BINARY_OP_INPLACE_TRUE_DIVIDE:
                    if (rhs_val == 0) {
376
                        goto zero_division;
377
378
                    }
                    return mp_obj_new_float((mp_float_t)lhs_val / (mp_float_t)rhs_val);
379
                #endif
380

Damien George's avatar
Damien George committed
381
                case MP_BINARY_OP_MODULO:
382
383
                case MP_BINARY_OP_INPLACE_MODULO: {
                    lhs_val = mp_small_int_modulo(lhs_val, rhs_val);
384
385
                    break;
                }
386

Damien George's avatar
Damien George committed
387
388
                case MP_BINARY_OP_POWER:
                case MP_BINARY_OP_INPLACE_POWER:
389
                    if (rhs_val < 0) {
390
                        #if MICROPY_PY_BUILTINS_FLOAT
391
392
393
                        lhs = mp_obj_new_float(lhs_val);
                        goto generic_binary_op;
                        #else
394
                        nlr_raise(mp_obj_new_exception_msg(&mp_type_ValueError, "negative power with no float support"));
395
396
                        #endif
                    } else {
397
                        mp_int_t ans = 1;
398
399
                        while (rhs_val > 0) {
                            if (rhs_val & 1) {
400
                                if (mp_small_int_mul_overflow(ans, lhs_val)) {
401
402
                                    goto power_overflow;
                                }
403
                                ans *= lhs_val;
404
405
406
                            }
                            if (rhs_val == 1) {
                                break;
407
408
                            }
                            rhs_val /= 2;
409
                            if (mp_small_int_mul_overflow(lhs_val, lhs_val)) {
410
411
                                goto power_overflow;
                            }
412
                            lhs_val *= lhs_val;
413
                        }
414
                        lhs_val = ans;
415
                    }
416
                    break;
417
418
419
420
421
422

                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
423
424
425
426
                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;
427

428
429
                default:
                    goto unsupported_op;
430
            }
431
            // TODO: We just should make mp_obj_new_int() inline and use that
432
            if (MP_SMALL_INT_FITS(lhs_val)) {
433
                return MP_OBJ_NEW_SMALL_INT(lhs_val);
434
435
            } else {
                return mp_obj_new_int(lhs_val);
436
            }
437
#if MICROPY_PY_BUILTINS_FLOAT
438
        } else if (MP_OBJ_IS_TYPE(rhs, &mp_type_float)) {
439
440
441
442
443
444
            mp_obj_t res = mp_obj_float_binary_op(op, lhs_val, rhs);
            if (res == MP_OBJ_NULL) {
                goto unsupported_op;
            } else {
                return res;
            }
445
#if MICROPY_PY_BUILTINS_COMPLEX
446
        } else if (MP_OBJ_IS_TYPE(rhs, &mp_type_complex)) {
447
448
449
450
451
452
            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;
            }
453
#endif
454
#endif
455
        }
456
    }
457

458
    /* deal with `in`
459
460
     *
     * NOTE `a in b` is `b.__contains__(a)`, hence why the generic dispatch
Damien George's avatar
Damien George committed
461
     * needs to go below with swapped arguments
462
     */
Damien George's avatar
Damien George committed
463
    if (op == MP_BINARY_OP_IN) {
464
465
466
        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);
467
            if (res != MP_OBJ_NULL) {
468
                return res;
John R. Lenton's avatar
John R. Lenton committed
469
            }
470
471
472
473
        }
        if (type->getiter != NULL) {
            /* second attempt, walk the iterator */
            mp_obj_t next = NULL;
Damien George's avatar
Damien George committed
474
            mp_obj_t iter = mp_getiter(rhs);
475
            while ((next = mp_iternext(iter)) != MP_OBJ_STOP_ITERATION) {
476
                if (mp_obj_equal(next, lhs)) {
477
                    return mp_const_true;
John R. Lenton's avatar
John R. Lenton committed
478
                }
479
            }
480
            return mp_const_false;
481
482
        }

483
        nlr_raise(mp_obj_new_exception_msg_varg(
484
                     &mp_type_TypeError, "'%s' object is not iterable",
485
486
487
488
                     mp_obj_get_type_str(rhs)));
        return mp_const_none;
    }

489
    // generic binary_op supplied by type
490
491
492
    mp_obj_type_t *type;
generic_binary_op:
    type = mp_obj_get_type(lhs);
493
494
    if (type->binary_op != NULL) {
        mp_obj_t result = type->binary_op(op, lhs, rhs);
495
        if (result != MP_OBJ_NULL) {
496
            return result;
Damien's avatar
Damien committed
497
498
        }
    }
499

500
501
    // TODO implement dispatch for reverse binary ops

John R. Lenton's avatar
John R. Lenton committed
502
    // TODO specify in error message what the operator is
503
unsupported_op:
504
    nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_TypeError,
John R. Lenton's avatar
John R. Lenton committed
505
506
        "unsupported operand types for binary operator: '%s', '%s'",
        mp_obj_get_type_str(lhs), mp_obj_get_type_str(rhs)));
507
    return mp_const_none;
508
509

zero_division:
510
    nlr_raise(mp_obj_new_exception_msg(&mp_type_ZeroDivisionError, "division by zero"));
Damien's avatar
Damien committed
511
512
}

Damien George's avatar
Damien George committed
513
514
mp_obj_t mp_call_function_0(mp_obj_t fun) {
    return mp_call_function_n_kw(fun, 0, 0, NULL);
515
516
}

Damien George's avatar
Damien George committed
517
518
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);
519
520
}

Damien George's avatar
Damien George committed
521
mp_obj_t mp_call_function_2(mp_obj_t fun, mp_obj_t arg1, mp_obj_t arg2) {
522
    mp_obj_t args[2];
523
524
    args[0] = arg1;
    args[1] = arg2;
Damien George's avatar
Damien George committed
525
    return mp_call_function_n_kw(fun, 2, 0, args);
526
527
}

528
// args contains, eg: arg0  arg1  key0  value0  key1  value1
529
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) {
530
531
    // 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
532

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

535
536
537
538
539
    // get the type
    mp_obj_type_t *type = mp_obj_get_type(fun_in);

    // do the call
    if (type->call != NULL) {
540
        return type->call(fun_in, n_args, n_kw, args);
541
    }
542
543

    nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_TypeError, "'%s' object is not callable", mp_obj_get_type_str(fun_in)));
544
545
}

546
547
// 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
548
mp_obj_t mp_call_method_n_kw(mp_uint_t n_args, mp_uint_t n_kw, const mp_obj_t *args) {
549
    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);
550
    int adjust = (args[1] == NULL) ? 0 : 1;
Damien George's avatar
Damien George committed
551
    return mp_call_function_n_kw(args[0], n_args + adjust, n_kw, args + 2 - adjust);
552
553
}

554
mp_obj_t mp_call_method_n_kw_var(bool have_self, mp_uint_t n_args_n_kw, const mp_obj_t *args) {
555
556
557
558
559
560
561
    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;
562
563
    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
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596

    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
597
        mp_seq_copy(args2 + args2_len, args, n_args, mp_obj_t);
598
599
600
601
602
603
        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
604
        mp_uint_t len;
605
606
607
608
609
610
611
612
613
614
615
616
617
        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
618
        mp_seq_cat(args2 + args2_len, args, n_args, items, len, mp_obj_t);
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
        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
634
        mp_seq_copy(args2 + args2_len, args, n_args, mp_obj_t);
635
636
637
638

        // extract the variable position args from the iterator
        mp_obj_t iterable = mp_getiter(pos_seq);
        mp_obj_t item;
639
        while ((item = mp_iternext(iterable)) != MP_OBJ_STOP_ITERATION) {
640
641
642
643
644
645
646
647
648
649
650
651
            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.
652
    mp_seq_copy(args2 + args2_len, args + n_args, 2 * n_kw, mp_obj_t);
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
    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;
676
        while ((item = mp_iternext(iterable)) != MP_OBJ_STOP_ITERATION) {
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
            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;
}

698
// unpacked items are stored in reverse order into the array pointed to by items
699
void mp_unpack_sequence(mp_obj_t seq_in, mp_uint_t num, mp_obj_t *items) {
700
    mp_uint_t seq_len;
701
    if (MP_OBJ_IS_TYPE(seq_in, &mp_type_tuple) || MP_OBJ_IS_TYPE(seq_in, &mp_type_list)) {
702
        mp_obj_t *seq_items;
703
        if (MP_OBJ_IS_TYPE(seq_in, &mp_type_tuple)) {
704
705
706
            mp_obj_tuple_get(seq_in, &seq_len, &seq_items);
        } else {
            mp_obj_list_get(seq_in, &seq_len, &seq_items);
707
        }
708
        if (seq_len < num) {
709
            goto too_short;
710
        } else if (seq_len > num) {
711
            goto too_long;
712
        }
713
        for (mp_uint_t i = 0; i < num; i++) {
714
715
            items[i] = seq_items[num - 1 - i];
        }
716
    } else {
Damien George's avatar
Damien George committed
717
        mp_obj_t iterable = mp_getiter(seq_in);
718
719

        for (seq_len = 0; seq_len < num; seq_len++) {
Damien George's avatar
Damien George committed
720
            mp_obj_t el = mp_iternext(iterable);
721
            if (el == MP_OBJ_STOP_ITERATION) {
722
723
724
725
                goto too_short;
            }
            items[num - 1 - seq_len] = el;
        }
726
        if (mp_iternext(iterable) != MP_OBJ_STOP_ITERATION) {
727
728
            goto too_long;
        }
729
    }
730
731
732
    return;

too_short:
733
    nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_ValueError, "need more than %d values to unpack", seq_len));
734
too_long:
735
    nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_ValueError, "too many values to unpack (expected %d)", num));
736
737
}

738
// unpacked items are stored in reverse order into the array pointed to by items
739
740
741
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;
742
    DEBUG_OP_printf("unpack ex " UINT_FMT " " UINT_FMT "\n", num_left, num_right);
743
    mp_uint_t seq_len;
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
    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;
        }
759
        for (mp_uint_t i = 0; i < num_right; i++) {
760
761
762
            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);
763
        for (mp_uint_t i = 0; i < num_left; i++) {
764
765
766
767
768
769
770
771
772
773
774
            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);
775
            if (item == MP_OBJ_STOP_ITERATION) {
776
777
778
779
                goto too_short;
            }
            items[num_left + num_right + 1 - 1 - seq_len] = item;
        }
780
        mp_obj_list_t *rest = mp_obj_new_list(0, NULL);
781
        while ((item = mp_iternext(iterable)) != MP_OBJ_STOP_ITERATION) {
782
783
            mp_obj_list_append(rest, item);
        }
784
        if (rest->len < num_right) {
785
786
787
            goto too_short;
        }
        items[num_right] = rest;
788
        for (mp_uint_t i = 0; i < num_right; i++) {
789
            items[num_right - 1 - i] = rest->items[rest->len - num_right + i];
790
        }
791
        mp_obj_list_set_len(rest, rest->len - num_right);
792
793
794
795
796
797
798
    }
    return;

too_short:
    nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_ValueError, "need more than %d values to unpack", seq_len));
}

799
mp_obj_t mp_load_attr(mp_obj_t base, qstr attr) {
800
    DEBUG_OP_printf("load attr %p.%s\n", base, qstr_str(attr));
801
    // use load_method
802
    mp_obj_t dest[2];
803
804
    mp_load_method(base, attr, dest);
    if (dest[1] == MP_OBJ_NULL) {
805
        // load_method returned just a normal attribute
806
        return dest[0];
807
808
809
    } 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
810
811
812
    }
}

813
814
815
// 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
816
void mp_load_method_maybe(mp_obj_t base, qstr attr, mp_obj_t *dest) {
817
818
819
820
821
822
823
    // 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
824
825
    // look for built-in names
    if (0) {
826
#if MICROPY_CPYTHON_COMPAT
Damien George's avatar
Damien George committed
827
828
829
    } else if (attr == MP_QSTR___class__) {
        // a.__class__ is equivalent to type(a)
        dest[0] = type;
830
#endif
Damien George's avatar
Damien George committed
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847

    } 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
848
            // see http://docs.python.org/3/howto/descriptor.html
Damien George's avatar
Damien George committed
849
850
851
852
853
854
855
            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);
856
857
858
            } 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
859
860
861
862
863
864
865
            } 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
866
867
            }
        }
868
    }
869
870
}

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

Damien George's avatar
Damien George committed
874
    mp_load_method_maybe(base, attr, dest);
875

876
    if (dest[0] == MP_OBJ_NULL) {
877
878
        // no attribute/method called attr
        // following CPython, we give a more detailed error message for type objects
879
        if (MP_OBJ_IS_TYPE(base, &mp_type_type)) {
880
            nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_AttributeError,
881
                "type object '%s' has no attribute '%s'", qstr_str(((mp_obj_type_t*)base)->name), qstr_str(attr)));
882
        } else {
883
            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)));
884
885
        }
    }
886
887
}

Damien George's avatar
Damien George committed
888
void mp_store_attr(mp_obj_t base, qstr attr, mp_obj_t value) {
Damien's avatar
Damien committed
889
    DEBUG_OP_printf("store attr %p.%s <- %p\n", base, qstr_str(attr), value);
890
891
892
893
894
    mp_obj_type_t *type = mp_obj_get_type(base);
    if (type->store_attr != NULL) {
        if (type->store_attr(base, attr, value)) {
            return;
        }
895
    }
896
    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)));
897
898
}

Damien George's avatar
Damien George committed
899
mp_obj_t mp_getiter(mp_obj_t o_in) {
900
    assert(o_in);
901
902
    mp_obj_type_t *type = mp_obj_get_type(o_in);
    if (type->getiter != NULL) {
903
904
905
906
907
        mp_obj_t iter = type->getiter(o_in);
        if (iter == MP_OBJ_NULL) {
            goto not_iterable;
        }
        return iter;
908
    } else {
909
        // check for __iter__ method
910
        mp_obj_t dest[2];
Damien George's avatar
Damien George committed
911
        mp_load_method_maybe(o_in, MP_QSTR___iter__, dest);
912
        if (dest[0] != MP_OBJ_NULL) {
913
            // __iter__ exists, call it and return its result
Damien George's avatar
Damien George committed
914
            return mp_call_method_n_kw(0, 0, dest);
915
        } else {
Damien George's avatar
Damien George committed
916
            mp_load_method_maybe(o_in, MP_QSTR___getitem__, dest);
917
918
919
920
921
            if (dest[0] != MP_OBJ_NULL) {
                // __getitem__ exists, create an iterator
                return mp_obj_new_getitem_iter(dest);
            } else {
                // object not iterable
922
not_iterable:
923
                nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_TypeError, "'%s' object is not iterable", mp_obj_get_type_str(o_in)));
924
            }
925
        }
926
927
    }
}
928

929
// may return MP_OBJ_STOP_ITERATION as an optimisation instead of raise StopIteration()
930
// may also raise StopIteration()
Damien George's avatar
Damien George committed
931
mp_obj_t mp_iternext_allow_raise(mp_obj_t o_in) {
932
933
934
    mp_obj_type_t *type = mp_obj_get_type(o_in);
    if (type->iternext != NULL) {
        return type->iternext(o_in);