compile.c

/*
 * 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.
 */

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <math.h>

#include "misc.h"
#include "mpconfig.h"
#include "qstr.h"
#include "lexer.h"
#include "parse.h"
#include "runtime0.h"
#include "obj.h"
#include "emitglue.h"
#include "scope.h"
#include "emit.h"
#include "compile.h"
#include "runtime.h"
#include "builtin.h"
#include "smallint.h"

// TODO need to mangle __attr names

#define MICROPY_EMIT_NATIVE (MICROPY_EMIT_X64 || MICROPY_EMIT_THUMB)

typedef enum {
    PN_none = 0,
#define DEF_RULE(rule, comp, kind, ...) PN_##rule,
#include "grammar.h"
#undef DEF_RULE
    PN_maximum_number_of,
    PN_string, // special node for non-interned string
} pn_kind_t;

#define EMIT(fun) (comp->emit_method_table->fun(comp->emit))
#define EMIT_ARG(fun, ...) (comp->emit_method_table->fun(comp->emit, __VA_ARGS__))
#define EMIT_INLINE_ASM(fun) (comp->emit_inline_asm_method_table->fun(comp->emit_inline_asm))
#define EMIT_INLINE_ASM_ARG(fun, ...) (comp->emit_inline_asm_method_table->fun(comp->emit_inline_asm, __VA_ARGS__))

typedef struct _compiler_t {
    qstr source_file;
    uint8_t is_repl;
    uint8_t pass; // holds enum type pass_kind_t
    uint8_t had_error; // try to keep compiler clean from nlr
    uint8_t func_arg_is_super; // used to compile special case of super() function call

    uint next_label;

    uint16_t break_label; // highest bit set indicates we are breaking out of a for loop
    uint16_t continue_label;
    int break_continue_except_level;
    uint16_t cur_except_level; // increased for SETUP_EXCEPT, SETUP_FINALLY; decreased for POP_BLOCK, POP_EXCEPT

    uint8_t have_star;
    uint16_t num_dict_params;
    uint16_t num_default_params;

    scope_t *scope_head;
    scope_t *scope_cur;

    emit_t *emit;                                   // current emitter
    const emit_method_table_t *emit_method_table;   // current emit method table

    emit_inline_asm_t *emit_inline_asm;                                   // current emitter for inline asm
    const emit_inline_asm_method_table_t *emit_inline_asm_method_table;   // current emit method table for inline asm
} compiler_t;

STATIC void compile_syntax_error(compiler_t *comp, mp_parse_node_t pn, const char *msg) {
    // TODO store the error message to a variable in compiler_t instead of printing it
    if (MP_PARSE_NODE_IS_STRUCT(pn)) {
        printf("  File \"%s\", line " UINT_FMT "\n", qstr_str(comp->source_file), (machine_uint_t)((mp_parse_node_struct_t*)pn)->source_line);
    } else {
        printf("  File \"%s\"\n", qstr_str(comp->source_file));
    }
    printf("SyntaxError: %s\n", msg);
    comp->had_error = true;
}

STATIC const mp_map_elem_t mp_constants_table[] = {
    // Extra constants as defined by a port
    MICROPY_PORT_CONSTANTS
};

STATIC const mp_map_t mp_constants_map = {
    .all_keys_are_qstrs = 1,
    .table_is_fixed_array = 1,
    .used = ARRAY_SIZE(mp_constants_table),
    .alloc = ARRAY_SIZE(mp_constants_table),
    .table = (mp_map_elem_t*)mp_constants_table,
};

// this function is essentially a simple preprocessor
STATIC mp_parse_node_t fold_constants(compiler_t *comp, mp_parse_node_t pn, mp_map_t *consts) {
    if (0) {
        // dummy
#if MICROPY_COMP_CONST
    } else if (MP_PARSE_NODE_IS_ID(pn)) {
        // lookup identifier in table of dynamic constants
        qstr qst = MP_PARSE_NODE_LEAF_ARG(pn);
        mp_map_elem_t *elem = mp_map_lookup(consts, MP_OBJ_NEW_QSTR(qst), MP_MAP_LOOKUP);
        if (elem != NULL) {
            pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, MP_OBJ_SMALL_INT_VALUE(elem->value));
        }
#endif
    } else if (MP_PARSE_NODE_IS_STRUCT(pn)) {
        mp_parse_node_struct_t *pns = (mp_parse_node_struct_t*)pn;

        // fold some parse nodes before folding their arguments
        switch (MP_PARSE_NODE_STRUCT_KIND(pns)) {
#if MICROPY_COMP_CONST
            case PN_expr_stmt:
                if (!MP_PARSE_NODE_IS_NULL(pns->nodes[1])) {
                    mp_parse_node_struct_t *pns1 = (mp_parse_node_struct_t*)pns->nodes[1];
                    if (MP_PARSE_NODE_STRUCT_KIND(pns1) == PN_expr_stmt_assign) {
                        if (MP_PARSE_NODE_IS_ID(pns->nodes[0])
                            && MP_PARSE_NODE_IS_STRUCT_KIND(pns1->nodes[0], PN_power)
                            && MP_PARSE_NODE_IS_ID(((mp_parse_node_struct_t*)pns1->nodes[0])->nodes[0])
                            && MP_PARSE_NODE_LEAF_ARG(((mp_parse_node_struct_t*)pns1->nodes[0])->nodes[0]) == MP_QSTR_const
                            && MP_PARSE_NODE_IS_STRUCT_KIND(((mp_parse_node_struct_t*)pns1->nodes[0])->nodes[1], PN_trailer_paren)
                            && MP_PARSE_NODE_IS_NULL(((mp_parse_node_struct_t*)pns1->nodes[0])->nodes[2])
                            ) {
                            // code to assign dynamic constants: id = const(value)

                            // get the id
                            qstr id_qstr = MP_PARSE_NODE_LEAF_ARG(pns->nodes[0]);

                            // get the value
                            mp_parse_node_t pn_value = ((mp_parse_node_struct_t*)((mp_parse_node_struct_t*)pns1->nodes[0])->nodes[1])->nodes[0];
                            pn_value = fold_constants(comp, pn_value, consts);
                            if (!MP_PARSE_NODE_IS_SMALL_INT(pn_value)) {
                                compile_syntax_error(comp, (mp_parse_node_t)pns, "constant must be an integer");
                                break;
                            }
                            machine_int_t value = MP_PARSE_NODE_LEAF_SMALL_INT(pn_value);

                            // store the value in the table of dynamic constants
                            mp_map_elem_t *elem = mp_map_lookup(consts, MP_OBJ_NEW_QSTR(id_qstr), MP_MAP_LOOKUP_ADD_IF_NOT_FOUND);
                            if (elem->value != MP_OBJ_NULL) {
                                compile_syntax_error(comp, (mp_parse_node_t)pns, "constant redefined");
                                break;
                            }
                            elem->value = MP_OBJ_NEW_SMALL_INT(value);

                            // replace const(value) with value
                            pns1->nodes[0] = pn_value;

                            // finished folding this assignment
                            return pn;
                        }
                    }
                }
                break;
#endif
            case PN_string:
                return pn;
        }

        // fold arguments
        int n = MP_PARSE_NODE_STRUCT_NUM_NODES(pns);
        for (int i = 0; i < n; i++) {
            pns->nodes[i] = fold_constants(comp, pns->nodes[i], consts);
        }

        // try to fold this parse node
        switch (MP_PARSE_NODE_STRUCT_KIND(pns)) {
            case PN_atom_paren:
                if (n == 1 && MP_PARSE_NODE_IS_SMALL_INT(pns->nodes[0])) {
                    // (int)
                    pn = pns->nodes[0];
                }
                break;

            case PN_expr:
                if (n == 2 && MP_PARSE_NODE_IS_SMALL_INT(pns->nodes[0]) && MP_PARSE_NODE_IS_SMALL_INT(pns->nodes[1])) {
                    // int | int
                    machine_int_t arg0 = MP_PARSE_NODE_LEAF_SMALL_INT(pns->nodes[0]);
                    machine_int_t arg1 = MP_PARSE_NODE_LEAF_SMALL_INT(pns->nodes[1]);
                    pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, arg0 | arg1);
                }
                break;

            case PN_and_expr:
                if (n == 2 && MP_PARSE_NODE_IS_SMALL_INT(pns->nodes[0]) && MP_PARSE_NODE_IS_SMALL_INT(pns->nodes[1])) {
                    // int & int
                    machine_int_t arg0 = MP_PARSE_NODE_LEAF_SMALL_INT(pns->nodes[0]);
                    machine_int_t arg1 = MP_PARSE_NODE_LEAF_SMALL_INT(pns->nodes[1]);
                    pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, arg0 & arg1);
                }
                break;

            case PN_shift_expr:
                if (n == 3 && MP_PARSE_NODE_IS_SMALL_INT(pns->nodes[0]) && MP_PARSE_NODE_IS_SMALL_INT(pns->nodes[2])) {
                    machine_int_t arg0 = MP_PARSE_NODE_LEAF_SMALL_INT(pns->nodes[0]);
                    machine_int_t arg1 = MP_PARSE_NODE_LEAF_SMALL_INT(pns->nodes[2]);
                    if (MP_PARSE_NODE_IS_TOKEN_KIND(pns->nodes[1], MP_TOKEN_OP_DBL_LESS)) {
                        // int << int
                        if (!(arg1 >= BITS_PER_WORD || arg0 > (MP_SMALL_INT_MAX >> arg1) || arg0 < (MP_SMALL_INT_MIN >> arg1))) {
                            pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, arg0 << arg1);
                        }
                    } else if (MP_PARSE_NODE_IS_TOKEN_KIND(pns->nodes[1], MP_TOKEN_OP_DBL_MORE)) {
                        // int >> int
                        pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, arg0 >> arg1);
                    } else {
                        // shouldn't happen
                        assert(0);
                    }
                }
                break;

            case PN_arith_expr:
                // overflow checking here relies on SMALL_INT being strictly smaller than machine_int_t
                if (n == 3 && MP_PARSE_NODE_IS_SMALL_INT(pns->nodes[0]) && MP_PARSE_NODE_IS_SMALL_INT(pns->nodes[2])) {
                    machine_int_t arg0 = MP_PARSE_NODE_LEAF_SMALL_INT(pns->nodes[0]);
                    machine_int_t arg1 = MP_PARSE_NODE_LEAF_SMALL_INT(pns->nodes[2]);
                    if (MP_PARSE_NODE_IS_TOKEN_KIND(pns->nodes[1], MP_TOKEN_OP_PLUS)) {
                        // int + int
                        arg0 += arg1;
                    } else if (MP_PARSE_NODE_IS_TOKEN_KIND(pns->nodes[1], MP_TOKEN_OP_MINUS)) {
                        // int - int
                        arg0 -= arg1;
                    } else {
                        // shouldn't happen
                        assert(0);
                    }
                    if (MP_SMALL_INT_FITS(arg0)) {
                        //printf("%ld + %ld\n", arg0, arg1);
                        pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, arg0);
                    }
                }
                break;

            case PN_term:
                if (n == 3 && MP_PARSE_NODE_IS_SMALL_INT(pns->nodes[0]) && MP_PARSE_NODE_IS_SMALL_INT(pns->nodes[2])) {
                    machine_int_t arg0 = MP_PARSE_NODE_LEAF_SMALL_INT(pns->nodes[0]);
                    machine_int_t arg1 = MP_PARSE_NODE_LEAF_SMALL_INT(pns->nodes[2]);
                    if (MP_PARSE_NODE_IS_TOKEN_KIND(pns->nodes[1], MP_TOKEN_OP_STAR)) {
                        // int * int
                        if (!mp_small_int_mul_overflow(arg0, arg1)) {
                            arg0 *= arg1;
                            if (MP_SMALL_INT_FITS(arg0)) {
                                pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, arg0);
                            }
                        }
                    } else if (MP_PARSE_NODE_IS_TOKEN_KIND(pns->nodes[1], MP_TOKEN_OP_SLASH)) {
                        // int / int
                        // pass
                    } else if (MP_PARSE_NODE_IS_TOKEN_KIND(pns->nodes[1], MP_TOKEN_OP_PERCENT)) {
                        // int%int
                        pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, mp_small_int_modulo(arg0, arg1));
                    } else if (MP_PARSE_NODE_IS_TOKEN_KIND(pns->nodes[1], MP_TOKEN_OP_DBL_SLASH)) {
                        if (arg1 != 0) {
                            // int // int
                            pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, mp_small_int_floor_divide(arg0, arg1));
                        }
                    } else {
                        // shouldn't happen
                        assert(0);
                    }
                }
                break;

            case PN_factor_2:
                if (MP_PARSE_NODE_IS_SMALL_INT(pns->nodes[1])) {
                    machine_int_t arg = MP_PARSE_NODE_LEAF_SMALL_INT(pns->nodes[1]);
                    if (MP_PARSE_NODE_IS_TOKEN_KIND(pns->nodes[0], MP_TOKEN_OP_PLUS)) {
                        // +int
                        pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, arg);
                    } else if (MP_PARSE_NODE_IS_TOKEN_KIND(pns->nodes[0], MP_TOKEN_OP_MINUS)) {
                        // -int
                        pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, -arg);
                    } else if (MP_PARSE_NODE_IS_TOKEN_KIND(pns->nodes[0], MP_TOKEN_OP_TILDE)) {
                        // ~int
                        pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, ~arg);
                    } else {
                        // shouldn't happen
                        assert(0);
                    }
                }
                break;

            case PN_power:
                if (0) {
#if MICROPY_EMIT_CPYTHON
                } else if (MP_PARSE_NODE_IS_SMALL_INT(pns->nodes[0]) && MP_PARSE_NODE_IS_NULL(pns->nodes[1]) && !MP_PARSE_NODE_IS_NULL(pns->nodes[2])) {
                    // int ** x
                    // can overflow; enabled only to compare with CPython
                    mp_parse_node_struct_t* pns2 = (mp_parse_node_struct_t*)pns->nodes[2];
                    if (MP_PARSE_NODE_IS_SMALL_INT(pns2->nodes[0])) {
                        int power = MP_PARSE_NODE_LEAF_SMALL_INT(pns2->nodes[0]);
                        if (power >= 0) {
                            int ans = 1;
                            int base = MP_PARSE_NODE_LEAF_SMALL_INT(pns->nodes[0]);
                            for (; power > 0; power--) {
                                ans *= base;
                            }
                            pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, ans);
                        }
                    }
#endif
                } else if (MP_PARSE_NODE_IS_ID(pns->nodes[0]) && MP_PARSE_NODE_IS_STRUCT_KIND(pns->nodes[1], PN_trailer_period) && MP_PARSE_NODE_IS_NULL(pns->nodes[2])) {
                    // id.id
                    // look it up in constant table, see if it can be replaced with an integer
                    mp_parse_node_struct_t* pns1 = (mp_parse_node_struct_t*)pns->nodes[1];
                    assert(MP_PARSE_NODE_IS_ID(pns1->nodes[0]));
                    qstr q_base = MP_PARSE_NODE_LEAF_ARG(pns->nodes[0]);
                    qstr q_attr = MP_PARSE_NODE_LEAF_ARG(pns1->nodes[0]);
                    mp_map_elem_t *elem = mp_map_lookup((mp_map_t*)&mp_constants_map, MP_OBJ_NEW_QSTR(q_base), MP_MAP_LOOKUP);
                    if (elem != NULL) {
                        mp_obj_t dest[2];
                        mp_load_method_maybe(elem->value, q_attr, dest);
                        if (MP_OBJ_IS_SMALL_INT(dest[0]) && dest[1] == NULL) {
                            machine_int_t val = MP_OBJ_SMALL_INT_VALUE(dest[0]);
                            if (MP_SMALL_INT_FITS(val)) {
                                pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, val);
                            }
                        }
                    }
                }
                break;
        }
    }

    return pn;
}

STATIC void compile_trailer_paren_helper(compiler_t *comp, mp_parse_node_t pn_arglist, bool is_method_call, int n_positional_extra);
void compile_comprehension(compiler_t *comp, mp_parse_node_struct_t *pns, scope_kind_t kind);
STATIC void compile_node(compiler_t *comp, mp_parse_node_t pn);

STATIC uint comp_next_label(compiler_t *comp) {
    return comp->next_label++;
}

STATIC void compile_increase_except_level(compiler_t *comp) {
    comp->cur_except_level += 1;
    if (comp->cur_except_level > comp->scope_cur->exc_stack_size) {
        comp->scope_cur->exc_stack_size = comp->cur_except_level;
    }
}

STATIC void compile_decrease_except_level(compiler_t *comp) {
    assert(comp->cur_except_level > 0);
    comp->cur_except_level -= 1;
}

STATIC scope_t *scope_new_and_link(compiler_t *comp, scope_kind_t kind, mp_parse_node_t pn, uint emit_options) {
    scope_t *scope = scope_new(kind, pn, comp->source_file, emit_options);
    scope->parent = comp->scope_cur;
    scope->next = NULL;
    if (comp->scope_head == NULL) {
        comp->scope_head = scope;
    } else {
        scope_t *s = comp->scope_head;
        while (s->next != NULL) {
            s = s->next;
        }
        s->next = scope;
    }
    return scope;
}

STATIC void apply_to_single_or_list(compiler_t *comp, mp_parse_node_t pn, int pn_list_kind, void (*f)(compiler_t*, mp_parse_node_t)) {
    if (MP_PARSE_NODE_IS_STRUCT(pn) && MP_PARSE_NODE_STRUCT_KIND((mp_parse_node_struct_t*)pn) == pn_list_kind) {
        mp_parse_node_struct_t *pns = (mp_parse_node_struct_t*)pn;
        int num_nodes = MP_PARSE_NODE_STRUCT_NUM_NODES(pns);
        for (int i = 0; i < num_nodes; i++) {
            f(comp, pns->nodes[i]);
        }
    } else if (!MP_PARSE_NODE_IS_NULL(pn)) {
        f(comp, pn);
    }
}

STATIC int list_get(mp_parse_node_t *pn, int pn_kind, mp_parse_node_t **nodes) {
    if (MP_PARSE_NODE_IS_NULL(*pn)) {
        *nodes = NULL;
        return 0;
    } else if (MP_PARSE_NODE_IS_LEAF(*pn)) {
        *nodes = pn;
        return 1;
    } else {
        mp_parse_node_struct_t *pns = (mp_parse_node_struct_t*)(*pn);
        if (MP_PARSE_NODE_STRUCT_KIND(pns) != pn_kind) {
            *nodes = pn;
            return 1;
        } else {
            *nodes = pns->nodes;
            return MP_PARSE_NODE_STRUCT_NUM_NODES(pns);
        }
    }
}

void compile_do_nothing(compiler_t *comp, mp_parse_node_struct_t *pns) {
}

void compile_generic_all_nodes(compiler_t *comp, mp_parse_node_struct_t *pns) {
    int num_nodes = MP_PARSE_NODE_STRUCT_NUM_NODES(pns);
    for (int i = 0; i < num_nodes; i++) {
        compile_node(comp, pns->nodes[i]);
    }
}

#if MICROPY_EMIT_CPYTHON
STATIC bool cpython_c_tuple_is_const(mp_parse_node_t pn) {
    if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, PN_string)) {
        return true;
    }
    if (!MP_PARSE_NODE_IS_LEAF(pn)) {
        return false;
    }
    if (MP_PARSE_NODE_IS_ID(pn)) {
        return false;
    }
    return true;
}

STATIC void cpython_c_print_quoted_str(vstr_t *vstr, const char *str, uint len, bool bytes) {
    bool has_single_quote = false;
    bool has_double_quote = false;
    for (int i = 0; i < len; i++) {
        if (str[i] == '\'') {
            has_single_quote = true;
        } else if (str[i] == '"') {
            has_double_quote = true;
        }
    }
    if (bytes) {
        vstr_printf(vstr, "b");
    }
    bool quote_single = false;
    if (has_single_quote && !has_double_quote) {
        vstr_printf(vstr, "\"");
    } else {
        quote_single = true;
        vstr_printf(vstr, "'");
    }
    for (int i = 0; i < len; i++) {
        if (str[i] == '\n') {
            vstr_printf(vstr, "\\n");
        } else if (str[i] == '\\') {
            vstr_printf(vstr, "\\\\");
        } else if (str[i] == '\'' && quote_single) {
            vstr_printf(vstr, "\\'");
        } else {
            vstr_printf(vstr, "%c", str[i]);
        }
    }
    if (has_single_quote && !has_double_quote) {
        vstr_printf(vstr, "\"");
    } else {
        vstr_printf(vstr, "'");
    }
}

STATIC void cpython_c_tuple_emit_const(compiler_t *comp, mp_parse_node_t pn, vstr_t *vstr) {
    if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, PN_string)) {
        mp_parse_node_struct_t *pns = (mp_parse_node_struct_t*)pn;
        cpython_c_print_quoted_str(vstr, (const char*)pns->nodes[0], (machine_uint_t)pns->nodes[1], false);
        return;
    }

    assert(MP_PARSE_NODE_IS_LEAF(pn));
    if (MP_PARSE_NODE_IS_SMALL_INT(pn)) {
        vstr_printf(vstr, INT_FMT, MP_PARSE_NODE_LEAF_SMALL_INT(pn));
        return;
    }

    int arg = MP_PARSE_NODE_LEAF_ARG(pn);
    switch (MP_PARSE_NODE_LEAF_KIND(pn)) {
        case MP_PARSE_NODE_ID: assert(0);
        case MP_PARSE_NODE_INTEGER: vstr_printf(vstr, "%s", qstr_str(arg)); break;
        case MP_PARSE_NODE_DECIMAL: vstr_printf(vstr, "%s", qstr_str(arg)); break;
        case MP_PARSE_NODE_STRING:
        case MP_PARSE_NODE_BYTES: {
            uint len;
            const byte *str = qstr_data(arg, &len);
            cpython_c_print_quoted_str(vstr, (const char*)str, len, MP_PARSE_NODE_LEAF_KIND(pn) == MP_PARSE_NODE_BYTES);
            break;
        }
        case MP_PARSE_NODE_TOKEN:
            switch (arg) {
                case MP_TOKEN_KW_FALSE: vstr_printf(vstr, "False"); break;
                case MP_TOKEN_KW_NONE: vstr_printf(vstr, "None"); break;
                case MP_TOKEN_KW_TRUE: vstr_printf(vstr, "True"); break;
                default: assert(0); // shouldn't happen
            }
            break;
        default: assert(0);
    }
}

STATIC void cpython_c_tuple(compiler_t *comp, mp_parse_node_t pn, mp_parse_node_struct_t *pns_list) {
    int n = 0;
    if (pns_list != NULL) {
        n = MP_PARSE_NODE_STRUCT_NUM_NODES(pns_list);
    }
    int total = n;
    bool is_const = true;
    if (!MP_PARSE_NODE_IS_NULL(pn)) {
        total += 1;
        if (!cpython_c_tuple_is_const(pn)) {
            is_const = false;
        }
    }
    for (int i = 0; i < n; i++) {
        if (!cpython_c_tuple_is_const(pns_list->nodes[i])) {
            is_const = false;
            break;
        }
    }
    if (total > 0 && is_const) {
        bool need_comma = false;
        vstr_t *vstr = vstr_new();
        vstr_printf(vstr, "(");
        if (!MP_PARSE_NODE_IS_NULL(pn)) {
            cpython_c_tuple_emit_const(comp, pn, vstr);
            need_comma = true;
        }
        for (int i = 0; i < n; i++) {
            if (need_comma) {
                vstr_printf(vstr, ", ");
            }
            cpython_c_tuple_emit_const(comp, pns_list->nodes[i], vstr);
            need_comma = true;
        }
        if (total == 1) {
            vstr_printf(vstr, ",)");
        } else {
            vstr_printf(vstr, ")");
        }
        EMIT_ARG(load_const_verbatim_str, vstr_str(vstr));
        vstr_free(vstr);
    } else {
        if (!MP_PARSE_NODE_IS_NULL(pn)) {
            compile_node(comp, pn);
        }
        for (int i = 0; i < n; i++) {
            compile_node(comp, pns_list->nodes[i]);
        }
        EMIT_ARG(build_tuple, total);
    }
}
#endif

// funnelling all tuple creations through this function is purely so we can optionally agree with CPython
STATIC void c_tuple(compiler_t *comp, mp_parse_node_t pn, mp_parse_node_struct_t *pns_list) {
#if MICROPY_EMIT_CPYTHON
    cpython_c_tuple(comp, pn, pns_list);
#else
    int total = 0;
    if (!MP_PARSE_NODE_IS_NULL(pn)) {
        compile_node(comp, pn);
        total += 1;
    }
    if (pns_list != NULL) {
        int n = MP_PARSE_NODE_STRUCT_NUM_NODES(pns_list);
        for (int i = 0; i < n; i++) {
            compile_node(comp, pns_list->nodes[i]);
        }
        total += n;
    }
    EMIT_ARG(build_tuple, total);
#endif
}

void compile_generic_tuple(compiler_t *comp, mp_parse_node_struct_t *pns) {
    // a simple tuple expression
    c_tuple(comp, MP_PARSE_NODE_NULL, pns);
}

STATIC bool node_is_const_false(mp_parse_node_t pn) {
    return MP_PARSE_NODE_IS_TOKEN_KIND(pn, MP_TOKEN_KW_FALSE);
    // untested: || (MP_PARSE_NODE_IS_SMALL_INT(pn) && MP_PARSE_NODE_LEAF_SMALL_INT(pn) == 0);
}

STATIC bool node_is_const_true(mp_parse_node_t pn) {
    return MP_PARSE_NODE_IS_TOKEN_KIND(pn, MP_TOKEN_KW_TRUE) || (MP_PARSE_NODE_IS_SMALL_INT(pn) && MP_PARSE_NODE_LEAF_SMALL_INT(pn) == 1);
}

#if MICROPY_EMIT_CPYTHON
// the is_nested variable is purely to match with CPython, which doesn't fully optimise not's
STATIC void cpython_c_if_cond(compiler_t *comp, mp_parse_node_t pn, bool jump_if, int label, bool is_nested) {
    if (node_is_const_false(pn)) {
        if (jump_if == false) {
            EMIT_ARG(jump, label);
        }
        return;
    } else if (node_is_const_true(pn)) {
        if (jump_if == true) {
            EMIT_ARG(jump, label);
        }
        return;
    } else if (MP_PARSE_NODE_IS_STRUCT(pn)) {
        mp_parse_node_struct_t *pns = (mp_parse_node_struct_t*)pn;
        int n = MP_PARSE_NODE_STRUCT_NUM_NODES(pns);
        if (MP_PARSE_NODE_STRUCT_KIND(pns) == PN_or_test) {
            if (jump_if == false) {
                uint label2 = comp_next_label(comp);
                for (int i = 0; i < n - 1; i++) {
                    cpython_c_if_cond(comp, pns->nodes[i], true, label2, true);
                }
                cpython_c_if_cond(comp, pns->nodes[n - 1], false, label, true);
                EMIT_ARG(label_assign, label2);
            } else {
                for (int i = 0; i < n; i++) {
                    cpython_c_if_cond(comp, pns->nodes[i], true, label, true);
                }
            }
            return;
        } else if (MP_PARSE_NODE_STRUCT_KIND(pns) == PN_and_test) {
            if (jump_if == false) {
                for (int i = 0; i < n; i++) {
                    cpython_c_if_cond(comp, pns->nodes[i], false, label, true);
                }
            } else {
                uint label2 = comp_next_label(comp);
                for (int i = 0; i < n - 1; i++) {
                    cpython_c_if_cond(comp, pns->nodes[i], false, label2, true);
                }
                cpython_c_if_cond(comp, pns->nodes[n - 1], true, label, true);
                EMIT_ARG(label_assign, label2);
            }
            return;
        } else if (!is_nested && MP_PARSE_NODE_STRUCT_KIND(pns) == PN_not_test_2) {
            cpython_c_if_cond(comp, pns->nodes[0], !jump_if, label, true);
            return;
        }
    }

    // nothing special, fall back to default compiling for node and jump
    compile_node(comp, pn);
    if (jump_if == false) {
        EMIT_ARG(pop_jump_if_false, label);
    } else {
        EMIT_ARG(pop_jump_if_true, label);
    }
}
#endif

STATIC void c_if_cond(compiler_t *comp, mp_parse_node_t pn, bool jump_if, int label) {
#if MICROPY_EMIT_CPYTHON
    cpython_c_if_cond(comp, pn, jump_if, label, false);
#else
    if (node_is_const_false(pn)) {
        if (jump_if == false) {
            EMIT_ARG(jump, label);
        }
        return;
    } else if (node_is_const_true(pn)) {
        if (jump_if == true) {
            EMIT_ARG(jump, label);
        }
        return;
    } else if (MP_PARSE_NODE_IS_STRUCT(pn)) {
        mp_parse_node_struct_t *pns = (mp_parse_node_struct_t*)pn;
        int n = MP_PARSE_NODE_STRUCT_NUM_NODES(pns);
        if (MP_PARSE_NODE_STRUCT_KIND(pns) == PN_or_test) {
            if (jump_if == false) {
                uint label2 = comp_next_label(comp);
                for (int i = 0; i < n - 1; i++) {
                    c_if_cond(comp, pns->nodes[i], true, label2);
                }
                c_if_cond(comp, pns->nodes[n - 1], false, label);
                EMIT_ARG(label_assign, label2);
            } else {
                for (int i = 0; i < n; i++) {
                    c_if_cond(comp, pns->nodes[i], true, label);
                }
            }
            return;
        } else if (MP_PARSE_NODE_STRUCT_KIND(pns) == PN_and_test) {
            if (jump_if == false) {
                for (int i = 0; i < n; i++) {
                    c_if_cond(comp, pns->nodes[i], false, label);
                }
            } else {
                uint label2 = comp_next_label(comp);
                for (int i = 0; i < n - 1; i++) {
                    c_if_cond(comp, pns->nodes[i], false, label2);
                }
                c_if_cond(comp, pns->nodes[n - 1], true, label);
                EMIT_ARG(label_assign, label2);
            }
            return;
        } else if (MP_PARSE_NODE_STRUCT_KIND(pns) == PN_not_test_2) {
            c_if_cond(comp, pns->nodes[0], !jump_if, label);
            return;
        }
    }

    // nothing special, fall back to default compiling for node and jump
    compile_node(comp, pn);
    if (jump_if == false) {
        EMIT_ARG(pop_jump_if_false, label);
    } else {
        EMIT_ARG(pop_jump_if_true, label);
    }
#endif
}

typedef enum { ASSIGN_STORE, ASSIGN_AUG_LOAD, ASSIGN_AUG_STORE } assign_kind_t;
void c_assign(compiler_t *comp, mp_parse_node_t pn, assign_kind_t kind);

void c_assign_power(compiler_t *comp, mp_parse_node_struct_t *pns, assign_kind_t assign_kind) {
    if (assign_kind != ASSIGN_AUG_STORE) {
        compile_node(comp, pns->nodes[0]);
    }

    if (MP_PARSE_NODE_IS_STRUCT(pns->nodes[1])) {
        mp_parse_node_struct_t *pns1 = (mp_parse_node_struct_t*)pns->nodes[1];
        if (MP_PARSE_NODE_STRUCT_KIND(pns1) == PN_power_trailers) {
            int n = MP_PARSE_NODE_STRUCT_NUM_NODES(pns1);
            if (assign_kind != ASSIGN_AUG_STORE) {
                for (int i = 0; i < n - 1; i++) {
                    compile_node(comp, pns1->nodes[i]);
                }
            }
            assert(MP_PARSE_NODE_IS_STRUCT(pns1->nodes[n - 1]));
            pns1 = (mp_parse_node_struct_t*)pns1->nodes[n - 1];
        }
        if (MP_PARSE_NODE_STRUCT_KIND(pns1) == PN_trailer_paren) {
            goto cannot_assign;
        } else if (MP_PARSE_NODE_STRUCT_KIND(pns1) == PN_trailer_bracket) {
            if (assign_kind == ASSIGN_AUG_STORE) {
                EMIT(rot_three);
                EMIT(store_subscr);
            } else {
                compile_node(comp, pns1->nodes[0]);
                if (assign_kind == ASSIGN_AUG_LOAD) {
                    EMIT(dup_top_two);
                    EMIT(load_subscr);
                } else {
                    EMIT(store_subscr);
                }
            }
        } else if (MP_PARSE_NODE_STRUCT_KIND(pns1) == PN_trailer_period) {
            assert(MP_PARSE_NODE_IS_ID(pns1->nodes[0]));
            if (assign_kind == ASSIGN_AUG_LOAD) {
                EMIT(dup_top);
                EMIT_ARG(load_attr, MP_PARSE_NODE_LEAF_ARG(pns1->nodes[0]));
            } else {
                if (assign_kind == ASSIGN_AUG_STORE) {
                    EMIT(rot_two);
                }
                EMIT_ARG(store_attr, MP_PARSE_NODE_LEAF_ARG(pns1->nodes[0]));
            }
        } else {
            goto cannot_assign;
        }
    } else {
        goto cannot_assign;
    }

    if (!MP_PARSE_NODE_IS_NULL(pns->nodes[2])) {
        goto cannot_assign;
    }

    return;

cannot_assign:
    compile_syntax_error(comp, (mp_parse_node_t)pns, "can't assign to expression");
}

// we need to allow for a caller passing in 1 initial node (node_head) followed by an array of nodes (nodes_tail)
void c_assign_tuple(compiler_t *comp, mp_parse_node_t node_head, uint num_tail, mp_parse_node_t *nodes_tail) {
    uint num_head = (node_head == MP_PARSE_NODE_NULL) ? 0 : 1;

    // look for star expression
    int have_star_index = -1;
    if (num_head != 0 && MP_PARSE_NODE_IS_STRUCT_KIND(node_head, PN_star_expr)) {
        EMIT_ARG(unpack_ex, 0, num_tail);
        have_star_index = 0;
    }
    for (int i = 0; i < num_tail; i++) {
        if (MP_PARSE_NODE_IS_STRUCT_KIND(nodes_tail[i], PN_star_expr)) {
            if (have_star_index < 0) {
                EMIT_ARG(unpack_ex, num_head + i, num_tail - i - 1);
                have_star_index = num_head + i;
            } else {
                compile_syntax_error(comp, nodes_tail[i], "multiple *x in assignment");
                return;
            }
        }
    }
    if (have_star_index < 0) {
        EMIT_ARG(unpack_sequence, num_head + num_tail);
    }
    if (num_head != 0) {
        if (0 == have_star_index) {
            c_assign(comp, ((mp_parse_node_struct_t*)node_head)->nodes[0], ASSIGN_STORE);
        } else {
            c_assign(comp, node_head, ASSIGN_STORE);
        }
    }
    for (int i = 0; i < num_tail; i++) {
        if (num_head + i == have_star_index) {
            c_assign(comp, ((mp_parse_node_struct_t*)nodes_tail[i])->nodes[0], ASSIGN_STORE);
        } else {
            c_assign(comp, nodes_tail[i], ASSIGN_STORE);
        }
    }
}

// assigns top of stack to pn
void c_assign(compiler_t *comp, mp_parse_node_t pn, assign_kind_t assign_kind) {
    tail_recursion:
    if (MP_PARSE_NODE_IS_NULL(pn)) {
        assert(0);
    } else if (MP_PARSE_NODE_IS_LEAF(pn)) {
        if (MP_PARSE_NODE_IS_ID(pn)) {
            int arg = MP_PARSE_NODE_LEAF_ARG(pn);
            switch (assign_kind) {
                case ASSIGN_STORE:
                case ASSIGN_AUG_STORE:
                    EMIT_ARG(store_id, arg);
                    break;
                case ASSIGN_AUG_LOAD:
                    EMIT_ARG(load_id, arg);
                    break;
            }
        } else {
            compile_syntax_error(comp, pn, "can't assign to literal");
            return;
        }
    } else {
        mp_parse_node_struct_t *pns = (mp_parse_node_struct_t*)pn;
        switch (MP_PARSE_NODE_STRUCT_KIND(pns)) {
            case PN_power:
                // lhs is an index or attribute
                c_assign_power(comp, pns, assign_kind);
                break;

            case PN_testlist_star_expr:
            case PN_exprlist:
                // lhs is a tuple
                if (assign_kind != ASSIGN_STORE) {
                    goto bad_aug;
                }
                c_assign_tuple(comp, MP_PARSE_NODE_NULL, MP_PARSE_NODE_STRUCT_NUM_NODES(pns), pns->nodes);
                break;

            case PN_atom_paren:
                // lhs is something in parenthesis
                if (MP_PARSE_NODE_IS_NULL(pns->nodes[0])) {
                    // empty tuple
                    goto cannot_assign;
                } else if (MP_PARSE_NODE_IS_STRUCT_KIND(pns->nodes[0], PN_testlist_comp)) {
                    pns = (mp_parse_node_struct_t*)pns->nodes[0];
                    goto testlist_comp;
                } else {
                    // parenthesis around 1 item, is just that item
                    pn = pns->nodes[0];
                    goto tail_recursion;
                }
                break;

            case PN_atom_bracket:
                // lhs is something in brackets
                if (assign_kind != ASSIGN_STORE) {
                    goto bad_aug;
                }
                if (MP_PARSE_NODE_IS_NULL(pns->nodes[0])) {
                    // empty list, assignment allowed
                    c_assign_tuple(comp, MP_PARSE_NODE_NULL, 0, NULL);
                } else if (MP_PARSE_NODE_IS_STRUCT_KIND(pns->nodes[0], PN_testlist_comp)) {
                    pns = (mp_parse_node_struct_t*)pns->nodes[0];
                    goto testlist_comp;
                } else {
                    // brackets around 1 item
                    c_assign_tuple(comp, pns->nodes[0], 0, NULL);
                }
                break;

            default:
                goto cannot_assign;
        }
        return;

        testlist_comp:
        // lhs is a sequence
        if (MP_PARSE_NODE_IS_STRUCT(pns->nodes[1])) {
            mp_parse_node_struct_t *pns2 = (mp_parse_node_struct_t*)pns->nodes[1];
            if (MP_PARSE_NODE_STRUCT_KIND(pns2) == PN_testlist_comp_3b) {
                // sequence of one item, with trailing comma
                assert(MP_PARSE_NODE_IS_NULL(pns2->nodes[0]));
                c_assign_tuple(comp, pns->nodes[0], 0, NULL);
            } else if (MP_PARSE_NODE_STRUCT_KIND(pns2) == PN_testlist_comp_3c) {
                // sequence of many items
                uint n = MP_PARSE_NODE_STRUCT_NUM_NODES(pns2);
                c_assign_tuple(comp, pns->nodes[0], n, pns2->nodes);
            } else if (MP_PARSE_NODE_STRUCT_KIND(pns) == PN_comp_for) {
                // TODO can we ever get here? can it be compiled?
                goto cannot_assign;
            } else {
                // sequence with 2 items
                goto sequence_with_2_items;
            }
        } else {
            // sequence with 2 items
            sequence_with_2_items:
            c_assign_tuple(comp, MP_PARSE_NODE_NULL, 2, pns->nodes);
        }
        return;
    }
    return;

    cannot_assign:
    compile_syntax_error(comp, pn, "can't assign to expression");
    return;

    bad_aug:
    compile_syntax_error(comp, pn, "illegal expression for augmented assignment");
}

// stuff for lambda and comprehensions and generators
// if we are not in CPython compatibility mode then:
//  if n_pos_defaults > 0 then there is a tuple on the stack with the positional defaults
//  if n_kw_defaults > 0 then there is a dictionary on the stack with the keyword defaults
//  if both exist, the tuple is above the dictionary (ie the first pop gets the tuple)
void close_over_variables_etc(compiler_t *comp, scope_t *this_scope, int n_pos_defaults, int n_kw_defaults) {
    assert(n_pos_defaults >= 0);
    assert(n_kw_defaults >= 0);

    // make closed over variables, if any
    // ensure they are closed over in the order defined in the outer scope (mainly to agree with CPython)
    int nfree = 0;
    if (comp->scope_cur->kind != SCOPE_MODULE) {
        for (int i = 0; i < comp->scope_cur->id_info_len; i++) {
            id_info_t *id = &comp->scope_cur->id_info[i];
            if (id->kind == ID_INFO_KIND_CELL || id->kind == ID_INFO_KIND_FREE) {
                for (int j = 0; j < this_scope->id_info_len; j++) {
                    id_info_t *id2 = &this_scope->id_info[j];
                    if (id2->kind == ID_INFO_KIND_FREE && id->qstr == id2->qstr) {
#if MICROPY_EMIT_CPYTHON
                        EMIT_ARG(load_closure, id->qstr, id->local_num);
#else
                        // in Micro Python we load closures using LOAD_FAST
                        EMIT_ARG(load_fast, id->qstr, id->flags, id->local_num);
#endif
                        nfree += 1;
                    }
                }
            }
        }
    }

    // make the function/closure
    if (nfree == 0) {
        EMIT_ARG(make_function, this_scope, n_pos_defaults, n_kw_defaults);
    } else {
        EMIT_ARG(make_closure, this_scope, nfree, n_pos_defaults, n_kw_defaults);
    }
}

void compile_funcdef_param(compiler_t *comp, mp_parse_node_t pn) {
    if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, PN_typedargslist_star)) {
        comp->have_star = true;
        /* don't need to distinguish bare from named star
        mp_parse_node_struct_t *pns = (mp_parse_node_struct_t*)pn;
        if (MP_PARSE_NODE_IS_NULL(pns->nodes[0])) {
            // bare star
        } else {
            // named star
        }
        */

    } else if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, PN_typedargslist_dbl_star)) {
        // named double star
        // TODO do we need to do anything with this?

    } else {
        mp_parse_node_t pn_id;
        mp_parse_node_t pn_colon;