text: /*
   * This file is part of the Micro Python project, http://micropython.org/
   *
   * The MIT License (MIT)
   *
   * Copyright (c) 2013-2015 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 <unistd.h> // for ssize_t
  #include <assert.h>
  #include <string.h>
  
  #include "py/nlr.h"
  #include "py/lexer.h"
  #include "py/parse.h"
  #include "py/parsenum.h"
  #include "py/runtime0.h"
  #include "py/runtime.h"
  #include "py/objint.h"
  #include "py/builtin.h"
  
  #if MICROPY_ENABLE_COMPILER
  
  #define RULE_ACT_ARG_MASK       (0x0f)
  #define RULE_ACT_KIND_MASK      (0x30)
  #define RULE_ACT_ALLOW_IDENT    (0x40)
  #define RULE_ACT_ADD_BLANK      (0x80)
  #define RULE_ACT_OR             (0x10)
  #define RULE_ACT_AND            (0x20)
  #define RULE_ACT_LIST           (0x30)
  
  #define RULE_ARG_KIND_MASK      (0xf000)
  #define RULE_ARG_ARG_MASK       (0x0fff)
  #define RULE_ARG_TOK            (0x1000)
  #define RULE_ARG_RULE           (0x2000)
  #define RULE_ARG_OPT_RULE       (0x3000)
  
  #define ADD_BLANK_NODE(rule) ((rule->act & RULE_ACT_ADD_BLANK) != 0)
  
  // (un)comment to use rule names; for debugging
  //#define USE_RULE_NAME (1)
  
  typedef struct _rule_t {
      byte rule_id;
      byte act;
  #ifdef USE_RULE_NAME
      const char *rule_name;
  #endif
      uint16_t arg[];
  } rule_t;
  
  enum {
  #define DEF_RULE(rule, comp, kind, ...) RULE_##rule,
  #include "py/grammar.h"
  #undef DEF_RULE
      RULE_maximum_number_of,
      RULE_string, // special node for non-interned string
      RULE_bytes, // special node for non-interned bytes
      RULE_const_object, // special node for a constant, generic Python object
  };
  
  #define ident                   (RULE_ACT_ALLOW_IDENT)
  #define blank                   (RULE_ACT_ADD_BLANK)
  #define or(n)                   (RULE_ACT_OR | n)
  #define and(n)                  (RULE_ACT_AND | n)
  #define one_or_more             (RULE_ACT_LIST | 2)
  #define list                    (RULE_ACT_LIST | 1)
  #define list_with_end           (RULE_ACT_LIST | 3)
  #define tok(t)                  (RULE_ARG_TOK | MP_TOKEN_##t)
  #define rule(r)                 (RULE_ARG_RULE | RULE_##r)
  #define opt_rule(r)             (RULE_ARG_OPT_RULE | RULE_##r)
  #ifdef USE_RULE_NAME
  #define DEF_RULE(rule, comp, kind, ...) static const rule_t rule_##rule = { RULE_##rule, kind, #rule, { __VA_ARGS__ } };
  #else
  #define DEF_RULE(rule, comp, kind, ...) static const rule_t rule_##rule = { RULE_##rule, kind, { __VA_ARGS__ } };
  #endif
  #include "py/grammar.h"
  #undef or
  #undef and
  #undef list
  #undef list_with_end
  #undef tok
  #undef rule
  #undef opt_rule
  #undef one_or_more
  #undef DEF_RULE
  
  STATIC const rule_t *rules[] = {
  #define DEF_RULE(rule, comp, kind, ...) &rule_##rule,
  #include "py/grammar.h"
  #undef DEF_RULE
  };
  
  typedef struct _rule_stack_t {
      size_t src_line : 8 * sizeof(size_t) - 8; // maximum bits storing source line number
      size_t rule_id : 8; // this must be large enough to fit largest rule number
      size_t arg_i; // this dictates the maximum nodes in a "list" of things
  } rule_stack_t;
  
  typedef struct _mp_parse_chunk_t {
      size_t alloc;
      union {
          size_t used;
          struct _mp_parse_chunk_t *next;
      } union_;
      byte data[];
  } mp_parse_chunk_t;
  
  typedef enum {
      PARSE_ERROR_NONE = 0,
      PARSE_ERROR_MEMORY,
      PARSE_ERROR_CONST,
  } parse_error_t;
  
  typedef struct _parser_t {
      parse_error_t parse_error;
  
      size_t rule_stack_alloc;
      size_t rule_stack_top;
      rule_stack_t *rule_stack;
  
      size_t result_stack_alloc;
      size_t result_stack_top;
      mp_parse_node_t *result_stack;
  
      mp_lexer_t *lexer;
  
      mp_parse_tree_t tree;
      mp_parse_chunk_t *cur_chunk;
  
      #if MICROPY_COMP_CONST
      mp_map_t consts;
      #endif
  } parser_t;
  
  STATIC void *parser_alloc(parser_t *parser, size_t num_bytes) {
      // use a custom memory allocator to store parse nodes sequentially in large chunks
  
      mp_parse_chunk_t *chunk = parser->cur_chunk;
  
      if (chunk != NULL && chunk->union_.used + num_bytes > chunk->alloc) {
          // not enough room at end of previously allocated chunk so try to grow
          mp_parse_chunk_t *new_data = (mp_parse_chunk_t*)m_renew_maybe(byte, chunk,
              sizeof(mp_parse_chunk_t) + chunk->alloc,
              sizeof(mp_parse_chunk_t) + chunk->alloc + num_bytes, false);
          if (new_data == NULL) {
              // could not grow existing memory; shrink it to fit previous
              (void)m_renew_maybe(byte, chunk, sizeof(mp_parse_chunk_t) + chunk->alloc,
                  sizeof(mp_parse_chunk_t) + chunk->union_.used, false);
              chunk->alloc = chunk->union_.used;
              chunk->union_.next = parser->tree.chunk;
              parser->tree.chunk = chunk;
              chunk = NULL;
          } else {
              // could grow existing memory
              chunk->alloc += num_bytes;
          }
      }
  
      if (chunk == NULL) {
          // no previous chunk, allocate a new chunk
          size_t alloc = MICROPY_ALLOC_PARSE_CHUNK_INIT;
          if (alloc < num_bytes) {
              alloc = num_bytes;
          }
          chunk = (mp_parse_chunk_t*)m_new(byte, sizeof(mp_parse_chunk_t) + alloc);
          chunk->alloc = alloc;
          chunk->union_.used = 0;
          parser->cur_chunk = chunk;
      }
  
      byte *ret = chunk->data + chunk->union_.used;
      chunk->union_.used += num_bytes;
      return ret;
  }
  
  STATIC void push_rule(parser_t *parser, size_t src_line, const rule_t *rule, size_t arg_i) {
      if (parser->parse_error) {
          return;
      }
      if (parser->rule_stack_top >= parser->rule_stack_alloc) {
          rule_stack_t *rs = m_renew_maybe(rule_stack_t, parser->rule_stack, parser->rule_stack_alloc, parser->rule_stack_alloc + MICROPY_ALLOC_PARSE_RULE_INC, true);
          if (rs == NULL) {
              parser->parse_error = PARSE_ERROR_MEMORY;
              return;
          }
          parser->rule_stack = rs;
          parser->rule_stack_alloc += MICROPY_ALLOC_PARSE_RULE_INC;
      }
      rule_stack_t *rs = &parser->rule_stack[parser->rule_stack_top++];
      rs->src_line = src_line;
      rs->rule_id = rule->rule_id;
      rs->arg_i = arg_i;
  }
  
  STATIC void push_rule_from_arg(parser_t *parser, size_t arg) {
      assert((arg & RULE_ARG_KIND_MASK) == RULE_ARG_RULE || (arg & RULE_ARG_KIND_MASK) == RULE_ARG_OPT_RULE);
      size_t rule_id = arg & RULE_ARG_ARG_MASK;
      assert(rule_id < RULE_maximum_number_of);
      push_rule(parser, parser->lexer->tok_line, rules[rule_id], 0);
  }
  
  STATIC void pop_rule(parser_t *parser, const rule_t **rule, size_t *arg_i, size_t *src_line) {
      assert(!parser->parse_error);
      parser->rule_stack_top -= 1;
      *rule = rules[parser->rule_stack[parser->rule_stack_top].rule_id];
      *arg_i = parser->rule_stack[parser->rule_stack_top].arg_i;
      *src_line = parser->rule_stack[parser->rule_stack_top].src_line;
  }
  
  mp_parse_node_t mp_parse_node_new_leaf(size_t kind, mp_int_t arg) {
      if (kind == MP_PARSE_NODE_SMALL_INT) {
          return (mp_parse_node_t)(kind | (arg << 1));
      }
      return (mp_parse_node_t)(kind | (arg << 4));
  }
  
  bool mp_parse_node_get_int_maybe(mp_parse_node_t pn, mp_obj_t *o) {
      if (MP_PARSE_NODE_IS_SMALL_INT(pn)) {
          *o = MP_OBJ_NEW_SMALL_INT(MP_PARSE_NODE_LEAF_SMALL_INT(pn));
          return true;
      } else if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, RULE_const_object)) {
          mp_parse_node_struct_t *pns = (mp_parse_node_struct_t*)pn;
          #if MICROPY_OBJ_REPR == MICROPY_OBJ_REPR_D
          // nodes are 32-bit pointers, but need to extract 64-bit object
          *o = (uint64_t)pns->nodes[0] | ((uint64_t)pns->nodes[1] << 32);
          #else
          *o = (mp_obj_t)pns->nodes[0];
          #endif
          return MP_OBJ_IS_INT(*o);
      } else {
          return false;
      }
  }
  
  int mp_parse_node_extract_list(mp_parse_node_t *pn, size_t 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);
          }
      }
  }
  
  #if MICROPY_DEBUG_PRINTERS
  void mp_parse_node_print(mp_parse_node_t pn, size_t indent) {
      if (MP_PARSE_NODE_IS_STRUCT(pn)) {
          printf("[% 4d] ", (int)((mp_parse_node_struct_t*)pn)->source_line);
      } else {
          printf("       ");
      }
      for (size_t i = 0; i < indent; i++) {
          printf(" ");
      }
      if (MP_PARSE_NODE_IS_NULL(pn)) {
          printf("NULL\n");
      } else if (MP_PARSE_NODE_IS_SMALL_INT(pn)) {
          mp_int_t arg = MP_PARSE_NODE_LEAF_SMALL_INT(pn);
          printf("int(" INT_FMT ")\n", arg);
      } else if (MP_PARSE_NODE_IS_LEAF(pn)) {
          uintptr_t arg = MP_PARSE_NODE_LEAF_ARG(pn);
          switch (MP_PARSE_NODE_LEAF_KIND(pn)) {
              case MP_PARSE_NODE_ID: printf("id(%s)\n", qstr_str(arg)); break;
              case MP_PARSE_NODE_STRING: printf("str(%s)\n", qstr_str(arg)); break;
              case MP_PARSE_NODE_BYTES: printf("bytes(%s)\n", qstr_str(arg)); break;
              case MP_PARSE_NODE_TOKEN: printf("tok(%u)\n", (uint)arg); break;
              default: assert(0);
          }
      } else {
          // node must be a mp_parse_node_struct_t
          mp_parse_node_struct_t *pns = (mp_parse_node_struct_t*)pn;
          if (MP_PARSE_NODE_STRUCT_KIND(pns) == RULE_string) {
              printf("literal str(%.*s)\n", (int)pns->nodes[1], (char*)pns->nodes[0]);
          } else if (MP_PARSE_NODE_STRUCT_KIND(pns) == RULE_bytes) {
              printf("literal bytes(%.*s)\n", (int)pns->nodes[1], (char*)pns->nodes[0]);
          } else if (MP_PARSE_NODE_STRUCT_KIND(pns) == RULE_const_object) {
              #if MICROPY_OBJ_REPR == MICROPY_OBJ_REPR_D
              printf("literal const(%016llx)\n", (uint64_t)pns->nodes[0] | ((uint64_t)pns->nodes[1] << 32));
              #else
              printf("literal const(%p)\n", (mp_obj_t)pns->nodes[0]);
              #endif
          } else {
              size_t n = MP_PARSE_NODE_STRUCT_NUM_NODES(pns);
  #ifdef USE_RULE_NAME
              printf("%s(%u) (n=%u)\n", rules[MP_PARSE_NODE_STRUCT_KIND(pns)]->rule_name, (uint)MP_PARSE_NODE_STRUCT_KIND(pns), (uint)n);
  #else
              printf("rule(%u) (n=%u)\n", (uint)MP_PARSE_NODE_STRUCT_KIND(pns), (uint)n);
  #endif
              for (size_t i = 0; i < n; i++) {
                  mp_parse_node_print(pns->nodes[i], indent + 2);
              }
          }
      }
  }
  #endif // MICROPY_DEBUG_PRINTERS
  
  /*
  STATIC void result_stack_show(parser_t *parser) {
      printf("result stack, most recent first\n");
      for (ssize_t i = parser->result_stack_top - 1; i >= 0; i--) {
          mp_parse_node_print(parser->result_stack[i], 0);
      }
  }
  */
  
  STATIC mp_parse_node_t pop_result(parser_t *parser) {
      if (parser->parse_error) {
          return MP_PARSE_NODE_NULL;
      }
      assert(parser->result_stack_top > 0);
      return parser->result_stack[--parser->result_stack_top];
  }
  
  STATIC mp_parse_node_t peek_result(parser_t *parser, size_t pos) {
      if (parser->parse_error) {
          return MP_PARSE_NODE_NULL;
      }
      assert(parser->result_stack_top > pos);
      return parser->result_stack[parser->result_stack_top - 1 - pos];
  }
  
  STATIC void push_result_node(parser_t *parser, mp_parse_node_t pn) {
      if (parser->parse_error) {
          return;
      }
      if (parser->result_stack_top >= parser->result_stack_alloc) {
          mp_parse_node_t *stack = m_renew_maybe(mp_parse_node_t, parser->result_stack, parser->result_stack_alloc, parser->result_stack_alloc + MICROPY_ALLOC_PARSE_RESULT_INC, true);
          if (stack == NULL) {
              parser->parse_error = PARSE_ERROR_MEMORY;
              return;
          }
          parser->result_stack = stack;
          parser->result_stack_alloc += MICROPY_ALLOC_PARSE_RESULT_INC;
      }
      parser->result_stack[parser->result_stack_top++] = pn;
  }
  
  STATIC mp_parse_node_t make_node_string_bytes(parser_t *parser, size_t src_line, size_t rule_kind, const char *str, size_t len) {
      mp_parse_node_struct_t *pn = parser_alloc(parser, sizeof(mp_parse_node_struct_t) + sizeof(mp_parse_node_t) * 2);
      if (pn == NULL) {
          parser->parse_error = PARSE_ERROR_MEMORY;
          return MP_PARSE_NODE_NULL;
      }
      pn->source_line = src_line;
      pn->kind_num_nodes = rule_kind | (2 << 8);
      char *p = m_new(char, len);
      memcpy(p, str, len);
      pn->nodes[0] = (uintptr_t)p;
      pn->nodes[1] = len;
      return (mp_parse_node_t)pn;
  }
  
  STATIC mp_parse_node_t make_node_const_object(parser_t *parser, size_t src_line, mp_obj_t obj) {
      mp_parse_node_struct_t *pn = parser_alloc(parser, sizeof(mp_parse_node_struct_t) + sizeof(mp_obj_t));
      if (pn == NULL) {
          parser->parse_error = PARSE_ERROR_MEMORY;
          return MP_PARSE_NODE_NULL;
      }
      pn->source_line = src_line;
      #if MICROPY_OBJ_REPR == MICROPY_OBJ_REPR_D
      // nodes are 32-bit pointers, but need to store 64-bit object
      pn->kind_num_nodes = RULE_const_object | (2 << 8);
      pn->nodes[0] = (uint64_t)obj;
      pn->nodes[1] = (uint64_t)obj >> 32;
      #else
      pn->kind_num_nodes = RULE_const_object | (1 << 8);
      pn->nodes[0] = (uintptr_t)obj;
      #endif
      return (mp_parse_node_t)pn;
  }
  
  STATIC void push_result_token(parser_t *parser) {
      mp_parse_node_t pn;
      mp_lexer_t *lex = parser->lexer;
      if (lex->tok_kind == MP_TOKEN_NAME) {
          qstr id = qstr_from_strn(lex->vstr.buf, lex->vstr.len);
          #if MICROPY_COMP_CONST
          // lookup identifier in table of dynamic constants
          mp_map_elem_t *elem = mp_map_lookup(&parser->consts, MP_OBJ_NEW_QSTR(id), MP_MAP_LOOKUP);
          if (elem != NULL) {
              pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, MP_OBJ_SMALL_INT_VALUE(elem->value));
          } else
          #endif
          {
              pn = mp_parse_node_new_leaf(MP_PARSE_NODE_ID, id);
          }
      } else if (lex->tok_kind == MP_TOKEN_INTEGER) {
          mp_obj_t o = mp_parse_num_integer(lex->vstr.buf, lex->vstr.len, 0, lex);
          if (MP_OBJ_IS_SMALL_INT(o)) {
              pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, MP_OBJ_SMALL_INT_VALUE(o));
          } else {
              pn = make_node_const_object(parser, lex->tok_line, o);
          }
      } else if (lex->tok_kind == MP_TOKEN_FLOAT_OR_IMAG) {
          mp_obj_t o = mp_parse_num_decimal(lex->vstr.buf, lex->vstr.len, true, false, lex);
          pn = make_node_const_object(parser, lex->tok_line, o);
      } else if (lex->tok_kind == MP_TOKEN_STRING || lex->tok_kind == MP_TOKEN_BYTES) {
          // Don't automatically intern all strings/bytes.  doc strings (which are usually large)
          // will be discarded by the compiler, and so we shouldn't intern them.
          qstr qst = MP_QSTR_NULL;
          if (lex->vstr.len <= MICROPY_ALLOC_PARSE_INTERN_STRING_LEN) {
              // intern short strings
              qst = qstr_from_strn(lex->vstr.buf, lex->vstr.len);
          } else {
              // check if this string is already interned
              qst = qstr_find_strn(lex->vstr.buf, lex->vstr.len);
          }
          if (qst != MP_QSTR_NULL) {
              // qstr exists, make a leaf node
              pn = mp_parse_node_new_leaf(lex->tok_kind == MP_TOKEN_STRING ? MP_PARSE_NODE_STRING : MP_PARSE_NODE_BYTES, qst);
          } else {
              // not interned, make a node holding a pointer to the string/bytes data
              pn = make_node_string_bytes(parser, lex->tok_line, lex->tok_kind == MP_TOKEN_STRING ? RULE_string : RULE_bytes, lex->vstr.buf, lex->vstr.len);
          }
      } else {
          pn = mp_parse_node_new_leaf(MP_PARSE_NODE_TOKEN, lex->tok_kind);
      }
      push_result_node(parser, pn);
  }
  
  #if MICROPY_COMP_MODULE_CONST
  STATIC const mp_rom_map_elem_t mp_constants_table[] = {
      #if MICROPY_PY_UCTYPES
      { MP_ROM_QSTR(MP_QSTR_uctypes), MP_ROM_PTR(&mp_module_uctypes) },
      #endif
      // Extra constants as defined by a port
      MICROPY_PORT_CONSTANTS
  };
  STATIC MP_DEFINE_CONST_MAP(mp_constants_map, mp_constants_table);
  #endif
  
  #if MICROPY_COMP_CONST_FOLDING
  STATIC bool fold_constants(parser_t *parser, const rule_t *rule, size_t num_args) {
      // this code does folding of arbitrary integer expressions, eg 1 + 2 * 3 + 4
      // it does not do partial folding, eg 1 + 2 + x -> 3 + x
  
      mp_obj_t arg0;
      if (rule->rule_id == RULE_expr
          || rule->rule_id == RULE_xor_expr
          || rule->rule_id == RULE_and_expr) {
          // folding for binary ops: | ^ &
          mp_parse_node_t pn = peek_result(parser, num_args - 1);
          if (!mp_parse_node_get_int_maybe(pn, &arg0)) {
              return false;
          }
          mp_binary_op_t op;
          if (rule->rule_id == RULE_expr) {
              op = MP_BINARY_OP_OR;
          } else if (rule->rule_id == RULE_xor_expr) {
              op = MP_BINARY_OP_XOR;
          } else {
              op = MP_BINARY_OP_AND;
          }
          for (ssize_t i = num_args - 2; i >= 0; --i) {
              pn = peek_result(parser, i);
              mp_obj_t arg1;
              if (!mp_parse_node_get_int_maybe(pn, &arg1)) {
                  return false;
              }
              arg0 = mp_binary_op(op, arg0, arg1);
          }
      } else if (rule->rule_id == RULE_shift_expr
          || rule->rule_id == RULE_arith_expr
          || rule->rule_id == RULE_term) {
          // folding for binary ops: << >> + - * / % //
          mp_parse_node_t pn = peek_result(parser, num_args - 1);
          if (!mp_parse_node_get_int_maybe(pn, &arg0)) {
              return false;
          }
          for (ssize_t i = num_args - 2; i >= 1; i -= 2) {
              pn = peek_result(parser, i - 1);
              mp_obj_t arg1;
              if (!mp_parse_node_get_int_maybe(pn, &arg1)) {
                  return false;
              }
              mp_token_kind_t tok = MP_PARSE_NODE_LEAF_ARG(peek_result(parser, i));
              static const uint8_t token_to_op[] = {
                  MP_BINARY_OP_ADD,
                  MP_BINARY_OP_SUBTRACT,
                  MP_BINARY_OP_MULTIPLY,
                  255,//MP_BINARY_OP_POWER,
                  255,//MP_BINARY_OP_TRUE_DIVIDE,
                  MP_BINARY_OP_FLOOR_DIVIDE,
                  MP_BINARY_OP_MODULO,
                  255,//MP_BINARY_OP_LESS
                  MP_BINARY_OP_LSHIFT,
                  255,//MP_BINARY_OP_MORE
                  MP_BINARY_OP_RSHIFT,
              };
              mp_binary_op_t op = token_to_op[tok - MP_TOKEN_OP_PLUS];
              if (op == (mp_binary_op_t)255) {
                  return false;
              }
              int rhs_sign = mp_obj_int_sign(arg1);
              if (op <= MP_BINARY_OP_RSHIFT) {
                  // << and >> can't have negative rhs
                  if (rhs_sign < 0) {
                      return false;
                  }
              } else if (op >= MP_BINARY_OP_FLOOR_DIVIDE) {
                  // % and // can't have zero rhs
                  if (rhs_sign == 0) {
                      return false;
                  }
              }
              arg0 = mp_binary_op(op, arg0, arg1);
          }
      } else if (rule->rule_id == RULE_factor_2) {
          // folding for unary ops: + - ~
          mp_parse_node_t pn = peek_result(parser, 0);
          if (!mp_parse_node_get_int_maybe(pn, &arg0)) {
              return false;
          }
          mp_token_kind_t tok = MP_PARSE_NODE_LEAF_ARG(peek_result(parser, 1));
          mp_unary_op_t op;
          if (tok == MP_TOKEN_OP_PLUS) {
              op = MP_UNARY_OP_POSITIVE;
          } else if (tok == MP_TOKEN_OP_MINUS) {
              op = MP_UNARY_OP_NEGATIVE;
          } else {
              assert(tok == MP_TOKEN_OP_TILDE); // should be
              op = MP_UNARY_OP_INVERT;
          }
          arg0 = mp_unary_op(op, arg0);
  
      #if MICROPY_COMP_CONST
      } else if (rule->rule_id == RULE_expr_stmt) {
          mp_parse_node_t pn1 = peek_result(parser, 0);
          if (!MP_PARSE_NODE_IS_NULL(pn1)
              && !(MP_PARSE_NODE_IS_STRUCT_KIND(pn1, RULE_expr_stmt_augassign)
              || MP_PARSE_NODE_IS_STRUCT_KIND(pn1, RULE_expr_stmt_assign_list))) {
              // this node is of the form <x> = <y>
              mp_parse_node_t pn0 = peek_result(parser, 1);
              if (MP_PARSE_NODE_IS_ID(pn0)
                  && MP_PARSE_NODE_IS_STRUCT_KIND(pn1, RULE_power)
                  && MP_PARSE_NODE_IS_ID(((mp_parse_node_struct_t*)pn1)->nodes[0])
                  && MP_PARSE_NODE_LEAF_ARG(((mp_parse_node_struct_t*)pn1)->nodes[0]) == MP_QSTR_const
                  && MP_PARSE_NODE_IS_STRUCT_KIND(((mp_parse_node_struct_t*)pn1)->nodes[1], RULE_trailer_paren)
                  && MP_PARSE_NODE_IS_NULL(((mp_parse_node_struct_t*)pn1)->nodes[2])
                  ) {
                  // code to assign dynamic constants: id = const(value)
  
                  // get the id
                  qstr id = MP_PARSE_NODE_LEAF_ARG(pn0);
  
                  // get the value
                  mp_parse_node_t pn_value = ((mp_parse_node_struct_t*)((mp_parse_node_struct_t*)pn1)->nodes[1])->nodes[0];
                  if (!MP_PARSE_NODE_IS_SMALL_INT(pn_value)) {
                      parser->parse_error = PARSE_ERROR_CONST;
                      return false;
                  }
                  mp_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(&parser->consts, MP_OBJ_NEW_QSTR(id), MP_MAP_LOOKUP_ADD_IF_NOT_FOUND);
                  assert(elem->value == MP_OBJ_NULL);
                  elem->value = MP_OBJ_NEW_SMALL_INT(value);
  
                  // replace const(value) with value
                  pop_result(parser);
                  push_result_node(parser, pn_value);
  
                  // finished folding this assignment, but we still want it to be part of the tree
                  return false;
              }
          }
          return false;
      #endif
  
      #if MICROPY_COMP_MODULE_CONST
      } else if (rule->rule_id == RULE_power) {
          mp_parse_node_t pn0 = peek_result(parser, 2);
          mp_parse_node_t pn1 = peek_result(parser, 1);
          mp_parse_node_t pn2 = peek_result(parser, 0);
          if (!(MP_PARSE_NODE_IS_ID(pn0)
              && MP_PARSE_NODE_IS_STRUCT_KIND(pn1, RULE_trailer_period)
              && MP_PARSE_NODE_IS_NULL(pn2))) {
              return false;
          }
          // id1.id2
          // 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*)pn1;
          assert(MP_PARSE_NODE_IS_ID(pns1->nodes[0]));
          qstr q_base = MP_PARSE_NODE_LEAF_ARG(pn0);
          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) {
              return false;
          }
          mp_obj_t dest[2];
          mp_load_method_maybe(elem->value, q_attr, dest);
          if (!(MP_OBJ_IS_INT(dest[0]) && dest[1] == MP_OBJ_NULL)) {
              return false;
          }
          arg0 = dest[0];
      #endif
  
      } else {
          return false;
      }
  
      // success folding this rule
  
      for (size_t i = num_args; i > 0; i--) {
          pop_result(parser);
      }
      if (MP_OBJ_IS_SMALL_INT(arg0)) {
          push_result_node(parser, mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, MP_OBJ_SMALL_INT_VALUE(arg0)));
      } else {
          // TODO reuse memory for parse node struct?
          push_result_node(parser, make_node_const_object(parser, 0, arg0));
      }
  
      return true;
  }
  #endif
  
  STATIC void push_result_rule(parser_t *parser, size_t src_line, const rule_t *rule, size_t num_args) {
      // optimise away parenthesis around an expression if possible
      if (rule->rule_id == RULE_atom_paren) {
          // there should be just 1 arg for this rule
          mp_parse_node_t pn = peek_result(parser, 0);
          if (MP_PARSE_NODE_IS_NULL(pn)) {
              // need to keep parenthesis for ()
          } else if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, RULE_testlist_comp)) {
              // need to keep parenthesis for (a, b, ...)
          } else {
              // parenthesis around a single expression, so it's just the expression
              return;
          }
      }
  
      #if MICROPY_COMP_CONST_FOLDING
      if (fold_constants(parser, rule, num_args)) {
          // we folded this rule so return straight away
          return;
      }
      #endif
  
      mp_parse_node_struct_t *pn = parser_alloc(parser, sizeof(mp_parse_node_struct_t) + sizeof(mp_parse_node_t) * num_args);
      if (pn == NULL) {
          parser->parse_error = PARSE_ERROR_MEMORY;
          return;
      }
      pn->source_line = src_line;
      pn->kind_num_nodes = (rule->rule_id & 0xff) | (num_args << 8);
      for (size_t i = num_args; i > 0; i--) {
          pn->nodes[i - 1] = pop_result(parser);
      }
      push_result_node(parser, (mp_parse_node_t)pn);
  }
  
  mp_parse_tree_t mp_parse(mp_lexer_t *lex, mp_parse_input_kind_t input_kind) {
  
      // initialise parser and allocate memory for its stacks
  
      parser_t parser;
  
      parser.parse_error = PARSE_ERROR_NONE;
  
      parser.rule_stack_alloc = MICROPY_ALLOC_PARSE_RULE_INIT;
      parser.rule_stack_top = 0;
      parser.rule_stack = m_new_maybe(rule_stack_t, parser.rule_stack_alloc);
  
      parser.result_stack_alloc = MICROPY_ALLOC_PARSE_RESULT_INIT;
      parser.result_stack_top = 0;
      parser.result_stack = m_new_maybe(mp_parse_node_t, parser.result_stack_alloc);
  
      parser.lexer = lex;
  
      parser.tree.chunk = NULL;
      parser.cur_chunk = NULL;
  
      #if MICROPY_COMP_CONST
      mp_map_init(&parser.consts, 0);
      #endif
  
      // check if we could allocate the stacks
      if (parser.rule_stack == NULL || parser.result_stack == NULL) {
          goto memory_error;
      }
  
      // work out the top-level rule to use, and push it on the stack
      size_t top_level_rule;
      switch (input_kind) {
          case MP_PARSE_SINGLE_INPUT: top_level_rule = RULE_single_input; break;
          case MP_PARSE_EVAL_INPUT: top_level_rule = RULE_eval_input; break;
          default: top_level_rule = RULE_file_input;
      }
      push_rule(&parser, lex->tok_line, rules[top_level_rule], 0);
  
      // parse!
  
      size_t n, i; // state for the current rule
      size_t rule_src_line; // source line for the first token matched by the current rule
      bool backtrack = false;
      const rule_t *rule = NULL;
  
      for (;;) {
          next_rule:
          if (parser.rule_stack_top == 0 || parser.parse_error) {
              break;
          }
  
          pop_rule(&parser, &rule, &i, &rule_src_line);
          n = rule->act & RULE_ACT_ARG_MASK;
  
          /*
          // debugging
          printf("depth=%d ", parser.rule_stack_top);
          for (int j = 0; j < parser.rule_stack_top; ++j) {
              printf(" ");
          }
          printf("%s n=%d i=%d bt=%d\n", rule->rule_name, n, i, backtrack);
          */
  
          switch (rule->act & RULE_ACT_KIND_MASK) {
              case RULE_ACT_OR:
                  if (i > 0 && !backtrack) {
                      goto next_rule;
                  } else {
                      backtrack = false;
                  }
                  for (; i < n; ++i) {
                      uint16_t kind = rule->arg[i] & RULE_ARG_KIND_MASK;
                      if (kind == RULE_ARG_TOK) {
                          if (lex->tok_kind == (rule->arg[i] & RULE_ARG_ARG_MASK)) {
                              push_result_token(&parser);
                              mp_lexer_to_next(lex);
                              goto next_rule;
                          }
                      } else {
                          assert(kind == RULE_ARG_RULE);
                          if (i + 1 < n) {
                              push_rule(&parser, rule_src_line, rule, i + 1); // save this or-rule
                          }
                          push_rule_from_arg(&parser, rule->arg[i]); // push child of or-rule
                          goto next_rule;
                      }
                  }
                  backtrack = true;
                  break;
  
              case RULE_ACT_AND: {
  
                  // failed, backtrack if we can, else syntax error
                  if (backtrack) {
                      assert(i > 0);
                      if ((rule->arg[i - 1] & RULE_ARG_KIND_MASK) == RULE_ARG_OPT_RULE) {
                          // an optional rule that failed, so continue with next arg
                          push_result_node(&parser, MP_PARSE_NODE_NULL);
                          backtrack = false;
                      } else {
                          // a mandatory rule that failed, so propagate backtrack
                          if (i > 1) {
                              // already eaten tokens so can't backtrack
                              goto syntax_error;
                          } else {
                              goto next_rule;
                          }
                      }
                  }
  
                  // progress through the rule
                  for (; i < n; ++i) {
                      switch (rule->arg[i] & RULE_ARG_KIND_MASK) {
                          case RULE_ARG_TOK: {
                              // need to match a token
                              mp_token_kind_t tok_kind = rule->arg[i] & RULE_ARG_ARG_MASK;
                              if (lex->tok_kind == tok_kind) {
                                  // matched token
                                  if (tok_kind == MP_TOKEN_NAME) {
                                      push_result_token(&parser);
                                  }
                                  mp_lexer_to_next(lex);
                              } else {
                                  // failed to match token
                                  if (i > 0) {
                                      // already eaten tokens so can't backtrack
                                      goto syntax_error;
                                  } else {
                                      // this rule failed, so backtrack
                                      backtrack = true;
                                      goto next_rule;
                                  }
                              }
                              break;
                          }
                          case RULE_ARG_RULE:
                          case RULE_ARG_OPT_RULE:
                          rule_and_no_other_choice:
                              push_rule(&parser, rule_src_line, rule, i + 1); // save this and-rule
                              push_rule_from_arg(&parser, rule->arg[i]); // push child of and-rule
                              goto next_rule;
                          default:
                              assert(0);
                              goto rule_and_no_other_choice; // to help flow control analysis
                      }
                  }
  
                  assert(i == n);
  
                  // matched the rule, so now build the corresponding parse_node
  
                  // count number of arguments for the parse_node
                  i = 0;
                  bool emit_rule = false;
                  for (size_t x = 0; x < n; ++x) {
                      if ((rule->arg[x] & RULE_ARG_KIND_MASK) == RULE_ARG_TOK) {
                          mp_token_kind_t tok_kind = rule->arg[x] & RULE_ARG_ARG_MASK;
                          if (tok_kind >= MP_TOKEN_NAME) {
                              emit_rule = true;
                          }
                          if (tok_kind == MP_TOKEN_NAME) {
                              // only tokens which were names are pushed to stack
                              i += 1;
                          }
                      } else {
                          // rules are always pushed
                          i += 1;
                      }
                  }
  
                  #if !MICROPY_ENABLE_DOC_STRING
                  // this code discards lonely statements, such as doc strings
                  if (input_kind != MP_PARSE_SINGLE_INPUT && rule->rule_id == RULE_expr_stmt && peek_result(&parser, 0) == MP_PARSE_NODE_NULL) {
                      mp_parse_node_t p = peek_result(&parser, 1);
                      if ((MP_PARSE_NODE_IS_LEAF(p) && !MP_PARSE_NODE_IS_ID(p)) || MP_PARSE_NODE_IS_STRUCT_KIND(p, RULE_string)) {
                          pop_result(&parser); // MP_PARSE_NODE_NULL
                          mp_parse_node_t pn = pop_result(&parser); // possibly RULE_string
                          if (MP_PARSE_NODE_IS_STRUCT(pn)) {
                              mp_parse_node_struct_t *pns = (mp_parse_node_struct_t *)pn;
                              if (MP_PARSE_NODE_STRUCT_KIND(pns) == RULE_string) {
                                  m_del(char, (char*)pns->nodes[0], (size_t)pns->nodes[1]);
                              }
                          }
                          push_result_rule(&parser, rule_src_line, rules[RULE_pass_stmt], 0);
                          break;
                      }
                  }
                  #endif
  
                  // always emit these rules, even if they have only 1 argument
                  if (rule->rule_id == RULE_expr_stmt || rule->rule_id == RULE_yield_stmt) {
                      emit_rule = true;
                  }
  
                  // if a rule has the RULE_ACT_ALLOW_IDENT bit set then this
                  // rule should not be emitted if it has only 1 argument
                  if (rule->act & RULE_ACT_ALLOW_IDENT) {
                      emit_rule = false;
                  }
  
                  // always emit these rules, and add an extra blank node at the end (to be used by the compiler to store data)
                  if (ADD_BLANK_NODE(rule)) {
                      emit_rule = true;
                      push_result_node(&parser, MP_PARSE_NODE_NULL);
                      i += 1;
                  }
  
                  size_t num_not_nil = 0;
                  for (size_t x = 0; x < i; ++x) {
                      if (peek_result(&parser, x) != MP_PARSE_NODE_NULL) {
                          num_not_nil += 1;
                      }
                  }
                  if (emit_rule || num_not_nil != 1) {
                      // need to add rule when num_not_nil==0 for, eg, atom_paren, testlist_comp_3b
                      push_result_rule(&parser, rule_src_line, rule, i);
                  } else {
                      // single result, leave it on stack
                      mp_parse_node_t pn = MP_PARSE_NODE_NULL;
                      for (size_t x = 0; x < i; ++x) {
                          mp_parse_node_t pn2 = pop_result(&parser);
                          if (pn2 != MP_PARSE_NODE_NULL) {
                              pn = pn2;
                          }
                      }
                      push_result_node(&parser, pn);
                  }
                  break;
              }
  
              case RULE_ACT_LIST: {
                  // n=2 is: item item*
                  // n=1 is: item (sep item)*
                  // n=3 is: item (sep item)* [sep]
                  bool had_trailing_sep;
                  if (backtrack) {
                      list_backtrack:
                      had_trailing_sep = false;
                      if (n == 2) {
                          if (i == 1) {
                              // fail on item, first time round; propagate backtrack
                              goto next_rule;
                          } else {
                              // fail on item, in later rounds; finish with this rule
                              backtrack = false;
                          }
                      } else {
                          if (i == 1) {
                              // fail on item, first time round; propagate backtrack
                              goto next_rule;
                          } else if ((i & 1) == 1) {
                              // fail on item, in later rounds; have eaten tokens so can't backtrack
                              if (n == 3) {
                                  // list allows trailing separator; finish parsing list
                                  had_trailing_sep = true;
                                  backtrack = false;
                              } else {
                                  // list doesn't allowing trailing separator; fail
                                  goto syntax_error;
                              }
                          } else {
                              // fail on separator; finish parsing list
                              backtrack = false;
                          }
                      }
                  } else {
                      for (;;) {
                          size_t arg = rule->arg[i & 1 & n];
                          switch (arg & RULE_ARG_KIND_MASK) {
                              case RULE_ARG_TOK:
                                  if (lex->tok_kind == (arg & RULE_ARG_ARG_MASK)) {
                                      if (i & 1 & n) {
                                          // separators which are tokens are not pushed to result stack
                                      } else {
                                          push_result_token(&parser);
                                      }
                                      mp_lexer_to_next(lex);
                                      // got element of list, so continue parsing list
                                      i += 1;
                                  } else {
                                      // couldn't get element of list
                                      i += 1;
                                      backtrack = true;
                                      goto list_backtrack;
                                  }
                                  break;
                              case RULE_ARG_RULE:
                              rule_list_no_other_choice:
                                  push_rule(&parser, rule_src_line, rule, i + 1); // save this list-rule
                                  push_rule_from_arg(&parser, arg); // push child of list-rule
                                  goto next_rule;
                              default:
                                  assert(0);
                                  goto rule_list_no_other_choice; // to help flow control analysis
                          }
                      }
                  }
                  assert(i >= 1);
  
                  // compute number of elements in list, result in i
                  i -= 1;
                  if ((n & 1) && (rule->arg[1] & RULE_ARG_KIND_MASK) == RULE_ARG_TOK) {
                      // don't count separators when they are tokens
                      i = (i + 1) / 2;
                  }
  
                  if (i == 1) {
                      // list matched single item
                      if (had_trailing_sep) {
                          // if there was a trailing separator, make a list of a single item
                          push_result_rule(&parser, rule_src_line, rule, i);
                      } else {
                          // just leave single item on stack (ie don't wrap in a list)
                      }
                  } else {
                      push_result_rule(&parser, rule_src_line, rule, i);
                  }
                  break;
              }
  
              default:
                  assert(0);
          }
      }
  
      #if MICROPY_COMP_CONST
      mp_map_deinit(&parser.consts);
      #endif
  
      // truncate final chunk and link into chain of chunks
      if (parser.cur_chunk != NULL) {
          (void)m_renew(byte, parser.cur_chunk,
              sizeof(mp_parse_chunk_t) + parser.cur_chunk->alloc,
              sizeof(mp_parse_chunk_t) + parser.cur_chunk->union_.used);
          parser.cur_chunk->alloc = parser.cur_chunk->union_.used;
          parser.cur_chunk->union_.next = parser.tree.chunk;
          parser.tree.chunk = parser.cur_chunk;
      }
  
      mp_obj_t exc;
  
      if (parser.parse_error) {
          #if MICROPY_COMP_CONST
          if (parser.parse_error == PARSE_ERROR_CONST) {
              exc = mp_obj_new_exception_msg(&mp_type_SyntaxError,
                  "constant must be an integer");
          } else
          #endif
          {
              assert(parser.parse_error == PARSE_ERROR_MEMORY);
          memory_error:
              exc = mp_obj_new_exception_msg(&mp_type_MemoryError,
                  "parser could not allocate enough memory");
          }
          parser.tree.root = MP_PARSE_NODE_NULL;
      } else if (
          lex->tok_kind != MP_TOKEN_END // check we are at the end of the token stream
          || parser.result_stack_top == 0 // check that we got a node (can fail on empty input)
          ) {
      syntax_error:
          if (lex->tok_kind == MP_TOKEN_INDENT) {
              exc = mp_obj_new_exception_msg(&mp_type_IndentationError,
                  "unexpected indent");
          } else if (lex->tok_kind == MP_TOKEN_DEDENT_MISMATCH) {
              exc = mp_obj_new_exception_msg(&mp_type_IndentationError,
                  "unindent does not match any outer indentation level");
          } else {
              exc = mp_obj_new_exception_msg(&mp_type_SyntaxError,
                  "invalid syntax");
          }
          parser.tree.root = MP_PARSE_NODE_NULL;
      } else {
          // no errors
  
          //result_stack_show(parser);
          //printf("rule stack alloc: %d\n", parser.rule_stack_alloc);
          //printf("result stack alloc: %d\n", parser.result_stack_alloc);
          //printf("number of parse nodes allocated: %d\n", num_parse_nodes_allocated);
  
          // get the root parse node that we created
          assert(parser.result_stack_top == 1);
          exc = MP_OBJ_NULL;
          parser.tree.root = parser.result_stack[0];
      }
  
      // free the memory that we don't need anymore
      m_del(rule_stack_t, parser.rule_stack, parser.rule_stack_alloc);
      m_del(mp_parse_node_t, parser.result_stack, parser.result_stack_alloc);
      // we also free the lexer on behalf of the caller (see below)
  
      if (exc != MP_OBJ_NULL) {
          // had an error so raise the exception
          // add traceback to give info about file name and location
          // we don't have a 'block' name, so just pass the NULL qstr to indicate this
          mp_obj_exception_add_traceback(exc, lex->source_name, lex->tok_line, MP_QSTR_NULL);
          mp_lexer_free(lex);
          nlr_raise(exc);
      } else {
          mp_lexer_free(lex);
          return parser.tree;
      }
  }
  
  void mp_parse_tree_clear(mp_parse_tree_t *tree) {
      mp_parse_chunk_t *chunk = tree->chunk;
      while (chunk != NULL) {
          mp_parse_chunk_t *next = chunk->union_.next;
          m_del(byte, chunk, sizeof(mp_parse_chunk_t) + chunk->alloc);
          chunk = next;
      }
  }
  
  #endif // MICROPY_ENABLE_COMPILER
  