LCOV - code coverage report
Current view: top level - py - parse.c (source / functions) Hit Total Coverage
Test: unix_coverage_v1.19.1-992-g38e7b842c.info Lines: 557 561 99.3 %
Date: 2023-03-23 12:38:05 Functions: 28 28 100.0 %
Branches: 387 435 89.0 %

           Branch data     Line data    Source code
       1                 :            : /*
       2                 :            :  * This file is part of the MicroPython project, http://micropython.org/
       3                 :            :  *
       4                 :            :  * The MIT License (MIT)
       5                 :            :  *
       6                 :            :  * Copyright (c) 2013-2017 Damien P. George
       7                 :            :  *
       8                 :            :  * Permission is hereby granted, free of charge, to any person obtaining a copy
       9                 :            :  * of this software and associated documentation files (the "Software"), to deal
      10                 :            :  * in the Software without restriction, including without limitation the rights
      11                 :            :  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
      12                 :            :  * copies of the Software, and to permit persons to whom the Software is
      13                 :            :  * furnished to do so, subject to the following conditions:
      14                 :            :  *
      15                 :            :  * The above copyright notice and this permission notice shall be included in
      16                 :            :  * all copies or substantial portions of the Software.
      17                 :            :  *
      18                 :            :  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
      19                 :            :  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
      20                 :            :  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
      21                 :            :  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
      22                 :            :  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
      23                 :            :  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
      24                 :            :  * THE SOFTWARE.
      25                 :            :  */
      26                 :            : 
      27                 :            : #include <stdbool.h>
      28                 :            : #include <stdint.h>
      29                 :            : #include <stdio.h>
      30                 :            : #include <unistd.h> // for ssize_t
      31                 :            : #include <assert.h>
      32                 :            : #include <string.h>
      33                 :            : 
      34                 :            : #include "py/lexer.h"
      35                 :            : #include "py/parse.h"
      36                 :            : #include "py/parsenum.h"
      37                 :            : #include "py/runtime.h"
      38                 :            : #include "py/objint.h"
      39                 :            : #include "py/objstr.h"
      40                 :            : #include "py/builtin.h"
      41                 :            : 
      42                 :            : #if MICROPY_ENABLE_COMPILER
      43                 :            : 
      44                 :            : #define RULE_ACT_ARG_MASK       (0x0f)
      45                 :            : #define RULE_ACT_KIND_MASK      (0x30)
      46                 :            : #define RULE_ACT_ALLOW_IDENT    (0x40)
      47                 :            : #define RULE_ACT_ADD_BLANK      (0x80)
      48                 :            : #define RULE_ACT_OR             (0x10)
      49                 :            : #define RULE_ACT_AND            (0x20)
      50                 :            : #define RULE_ACT_LIST           (0x30)
      51                 :            : 
      52                 :            : #define RULE_ARG_KIND_MASK      (0xf000)
      53                 :            : #define RULE_ARG_ARG_MASK       (0x0fff)
      54                 :            : #define RULE_ARG_TOK            (0x1000)
      55                 :            : #define RULE_ARG_RULE           (0x2000)
      56                 :            : #define RULE_ARG_OPT_RULE       (0x3000)
      57                 :            : 
      58                 :            : // *FORMAT-OFF*
      59                 :            : 
      60                 :            : enum {
      61                 :            : // define rules with a compile function
      62                 :            : #define DEF_RULE(rule, comp, kind, ...) RULE_##rule,
      63                 :            : #define DEF_RULE_NC(rule, kind, ...)
      64                 :            : #include "py/grammar.h"
      65                 :            : #undef DEF_RULE
      66                 :            : #undef DEF_RULE_NC
      67                 :            :     RULE_const_object, // special node for a constant, generic Python object
      68                 :            : 
      69                 :            : // define rules without a compile function
      70                 :            : #define DEF_RULE(rule, comp, kind, ...)
      71                 :            : #define DEF_RULE_NC(rule, kind, ...) RULE_##rule,
      72                 :            : #include "py/grammar.h"
      73                 :            : #undef DEF_RULE
      74                 :            : #undef DEF_RULE_NC
      75                 :            : };
      76                 :            : 
      77                 :            : // Define an array of actions corresponding to each rule
      78                 :            : STATIC const uint8_t rule_act_table[] = {
      79                 :            : #define or(n)                   (RULE_ACT_OR | n)
      80                 :            : #define and(n)                  (RULE_ACT_AND | n)
      81                 :            : #define and_ident(n)            (RULE_ACT_AND | n | RULE_ACT_ALLOW_IDENT)
      82                 :            : #define and_blank(n)            (RULE_ACT_AND | n | RULE_ACT_ADD_BLANK)
      83                 :            : #define one_or_more             (RULE_ACT_LIST | 2)
      84                 :            : #define list                    (RULE_ACT_LIST | 1)
      85                 :            : #define list_with_end           (RULE_ACT_LIST | 3)
      86                 :            : 
      87                 :            : #define DEF_RULE(rule, comp, kind, ...) kind,
      88                 :            : #define DEF_RULE_NC(rule, kind, ...)
      89                 :            : #include "py/grammar.h"
      90                 :            : #undef DEF_RULE
      91                 :            : #undef DEF_RULE_NC
      92                 :            : 
      93                 :            :     0, // RULE_const_object
      94                 :            : 
      95                 :            : #define DEF_RULE(rule, comp, kind, ...)
      96                 :            : #define DEF_RULE_NC(rule, kind, ...) kind,
      97                 :            : #include "py/grammar.h"
      98                 :            : #undef DEF_RULE
      99                 :            : #undef DEF_RULE_NC
     100                 :            : 
     101                 :            : #undef or
     102                 :            : #undef and
     103                 :            : #undef and_ident
     104                 :            : #undef and_blank
     105                 :            : #undef one_or_more
     106                 :            : #undef list
     107                 :            : #undef list_with_end
     108                 :            : };
     109                 :            : 
     110                 :            : // Define the argument data for each rule, as a combined array
     111                 :            : STATIC const uint16_t rule_arg_combined_table[] = {
     112                 :            : #define tok(t)                  (RULE_ARG_TOK | MP_TOKEN_##t)
     113                 :            : #define rule(r)                 (RULE_ARG_RULE | RULE_##r)
     114                 :            : #define opt_rule(r)             (RULE_ARG_OPT_RULE | RULE_##r)
     115                 :            : 
     116                 :            : #define DEF_RULE(rule, comp, kind, ...) __VA_ARGS__,
     117                 :            : #define DEF_RULE_NC(rule, kind, ...)
     118                 :            : #include "py/grammar.h"
     119                 :            : #undef DEF_RULE
     120                 :            : #undef DEF_RULE_NC
     121                 :            : 
     122                 :            : #define DEF_RULE(rule, comp, kind, ...)
     123                 :            : #define DEF_RULE_NC(rule, kind, ...)  __VA_ARGS__,
     124                 :            : #include "py/grammar.h"
     125                 :            : #undef DEF_RULE
     126                 :            : #undef DEF_RULE_NC
     127                 :            : 
     128                 :            : #undef tok
     129                 :            : #undef rule
     130                 :            : #undef opt_rule
     131                 :            : };
     132                 :            : 
     133                 :            : // Macro to create a list of N identifiers where N is the number of variable arguments to the macro
     134                 :            : #define RULE_EXPAND(x) x
     135                 :            : #define RULE_PADDING(rule, ...) RULE_PADDING2(rule, __VA_ARGS__, RULE_PADDING_IDS(rule))
     136                 :            : #define RULE_PADDING2(rule, ...) RULE_EXPAND(RULE_PADDING3(rule, __VA_ARGS__))
     137                 :            : #define RULE_PADDING3(rule, _1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, ...) __VA_ARGS__
     138                 :            : #define RULE_PADDING_IDS(r) PAD13_##r, PAD12_##r, PAD11_##r, PAD10_##r, PAD9_##r, PAD8_##r, PAD7_##r, PAD6_##r, PAD5_##r, PAD4_##r, PAD3_##r, PAD2_##r, PAD1_##r,
     139                 :            : 
     140                 :            : // Use an enum to create constants specifying how much room a rule takes in rule_arg_combined_table
     141                 :            : enum {
     142                 :            : #define DEF_RULE(rule, comp, kind, ...) RULE_PADDING(rule, __VA_ARGS__)
     143                 :            : #define DEF_RULE_NC(rule, kind, ...)
     144                 :            : #include "py/grammar.h"
     145                 :            : #undef DEF_RULE
     146                 :            : #undef DEF_RULE_NC
     147                 :            : #define DEF_RULE(rule, comp, kind, ...)
     148                 :            : #define DEF_RULE_NC(rule, kind, ...) RULE_PADDING(rule, __VA_ARGS__)
     149                 :            : #include "py/grammar.h"
     150                 :            : #undef DEF_RULE
     151                 :            : #undef DEF_RULE_NC
     152                 :            : };
     153                 :            : 
     154                 :            : // Macro to compute the start of a rule in rule_arg_combined_table
     155                 :            : #define RULE_ARG_OFFSET(rule, ...) RULE_ARG_OFFSET2(rule, __VA_ARGS__, RULE_ARG_OFFSET_IDS(rule))
     156                 :            : #define RULE_ARG_OFFSET2(rule, ...) RULE_EXPAND(RULE_ARG_OFFSET3(rule, __VA_ARGS__))
     157                 :            : #define RULE_ARG_OFFSET3(rule, _1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, _14, ...) _14
     158                 :            : #define RULE_ARG_OFFSET_IDS(r) PAD13_##r, PAD12_##r, PAD11_##r, PAD10_##r, PAD9_##r, PAD8_##r, PAD7_##r, PAD6_##r, PAD5_##r, PAD4_##r, PAD3_##r, PAD2_##r, PAD1_##r, PAD0_##r,
     159                 :            : 
     160                 :            : // Use the above enum values to create a table of offsets for each rule's arg
     161                 :            : // data, which indexes rule_arg_combined_table.  The offsets require 9 bits of
     162                 :            : // storage but only the lower 8 bits are stored here.  The 9th bit is computed
     163                 :            : // in get_rule_arg using the FIRST_RULE_WITH_OFFSET_ABOVE_255 constant.
     164                 :            : STATIC const uint8_t rule_arg_offset_table[] = {
     165                 :            : #define DEF_RULE(rule, comp, kind, ...) RULE_ARG_OFFSET(rule, __VA_ARGS__) & 0xff,
     166                 :            : #define DEF_RULE_NC(rule, kind, ...)
     167                 :            : #include "py/grammar.h"
     168                 :            : #undef DEF_RULE
     169                 :            : #undef DEF_RULE_NC
     170                 :            :     0, // RULE_const_object
     171                 :            : #define DEF_RULE(rule, comp, kind, ...)
     172                 :            : #define DEF_RULE_NC(rule, kind, ...) RULE_ARG_OFFSET(rule, __VA_ARGS__) & 0xff,
     173                 :            : #include "py/grammar.h"
     174                 :            : #undef DEF_RULE
     175                 :            : #undef DEF_RULE_NC
     176                 :            : };
     177                 :            : 
     178                 :            : // Define a constant that's used to determine the 9th bit of the values in rule_arg_offset_table
     179                 :            : static const size_t FIRST_RULE_WITH_OFFSET_ABOVE_255 =
     180                 :            : #define DEF_RULE(rule, comp, kind, ...) RULE_ARG_OFFSET(rule, __VA_ARGS__) >= 0x100 ? RULE_##rule :
     181                 :            : #define DEF_RULE_NC(rule, kind, ...)
     182                 :            : #include "py/grammar.h"
     183                 :            : #undef DEF_RULE
     184                 :            : #undef DEF_RULE_NC
     185                 :            : #define DEF_RULE(rule, comp, kind, ...)
     186                 :            : #define DEF_RULE_NC(rule, kind, ...) RULE_ARG_OFFSET(rule, __VA_ARGS__) >= 0x100 ? RULE_##rule :
     187                 :            : #include "py/grammar.h"
     188                 :            : #undef DEF_RULE
     189                 :            : #undef DEF_RULE_NC
     190                 :            : 0;
     191                 :            : 
     192                 :            : #if MICROPY_DEBUG_PARSE_RULE_NAME
     193                 :            : // Define an array of rule names corresponding to each rule
     194                 :            : STATIC const char *const rule_name_table[] = {
     195                 :            : #define DEF_RULE(rule, comp, kind, ...) #rule,
     196                 :            : #define DEF_RULE_NC(rule, kind, ...)
     197                 :            : #include "py/grammar.h"
     198                 :            : #undef DEF_RULE
     199                 :            : #undef DEF_RULE_NC
     200                 :            :     "", // RULE_const_object
     201                 :            : #define DEF_RULE(rule, comp, kind, ...)
     202                 :            : #define DEF_RULE_NC(rule, kind, ...) #rule,
     203                 :            : #include "py/grammar.h"
     204                 :            : #undef DEF_RULE
     205                 :            : #undef DEF_RULE_NC
     206                 :            : };
     207                 :            : #endif
     208                 :            : 
     209                 :            : // *FORMAT-ON*
     210                 :            : 
     211                 :            : typedef struct _rule_stack_t {
     212                 :            :     size_t src_line : (8 * sizeof(size_t) - 8); // maximum bits storing source line number
     213                 :            :     size_t rule_id : 8; // this must be large enough to fit largest rule number
     214                 :            :     size_t arg_i; // this dictates the maximum nodes in a "list" of things
     215                 :            : } rule_stack_t;
     216                 :            : 
     217                 :            : typedef struct _mp_parse_chunk_t {
     218                 :            :     size_t alloc;
     219                 :            :     union {
     220                 :            :         size_t used;
     221                 :            :         struct _mp_parse_chunk_t *next;
     222                 :            :     } union_;
     223                 :            :     byte data[];
     224                 :            : } mp_parse_chunk_t;
     225                 :            : 
     226                 :            : typedef struct _parser_t {
     227                 :            :     size_t rule_stack_alloc;
     228                 :            :     size_t rule_stack_top;
     229                 :            :     rule_stack_t *rule_stack;
     230                 :            : 
     231                 :            :     size_t result_stack_alloc;
     232                 :            :     size_t result_stack_top;
     233                 :            :     mp_parse_node_t *result_stack;
     234                 :            : 
     235                 :            :     mp_lexer_t *lexer;
     236                 :            : 
     237                 :            :     mp_parse_tree_t tree;
     238                 :            :     mp_parse_chunk_t *cur_chunk;
     239                 :            : 
     240                 :            :     #if MICROPY_COMP_CONST
     241                 :            :     mp_map_t consts;
     242                 :            :     #endif
     243                 :            : } parser_t;
     244                 :            : 
     245                 :   16901950 : STATIC const uint16_t *get_rule_arg(uint8_t r_id) {
     246                 :   16901950 :     size_t off = rule_arg_offset_table[r_id];
     247         [ +  + ]:   16901950 :     if (r_id >= FIRST_RULE_WITH_OFFSET_ABOVE_255) {
     248                 :    5761153 :         off |= 0x100;
     249                 :            :     }
     250                 :   16901950 :     return &rule_arg_combined_table[off];
     251                 :            : }
     252                 :            : 
     253                 :     247153 : STATIC void *parser_alloc(parser_t *parser, size_t num_bytes) {
     254                 :            :     // use a custom memory allocator to store parse nodes sequentially in large chunks
     255                 :            : 
     256                 :     247153 :     mp_parse_chunk_t *chunk = parser->cur_chunk;
     257                 :            : 
     258   [ +  +  +  + ]:     247153 :     if (chunk != NULL && chunk->union_.used + num_bytes > chunk->alloc) {
     259                 :            :         // not enough room at end of previously allocated chunk so try to grow
     260                 :     188833 :         mp_parse_chunk_t *new_data = (mp_parse_chunk_t *)m_renew_maybe(byte, chunk,
     261                 :            :             sizeof(mp_parse_chunk_t) + chunk->alloc,
     262                 :            :             sizeof(mp_parse_chunk_t) + chunk->alloc + num_bytes, false);
     263         [ +  + ]:     188833 :         if (new_data == NULL) {
     264                 :            :             // could not grow existing memory; shrink it to fit previous
     265                 :       8871 :             (void)m_renew_maybe(byte, chunk, sizeof(mp_parse_chunk_t) + chunk->alloc,
     266                 :            :                 sizeof(mp_parse_chunk_t) + chunk->union_.used, false);
     267                 :       8871 :             chunk->alloc = chunk->union_.used;
     268                 :       8871 :             chunk->union_.next = parser->tree.chunk;
     269                 :       8871 :             parser->tree.chunk = chunk;
     270                 :       8871 :             chunk = NULL;
     271                 :            :         } else {
     272                 :            :             // could grow existing memory
     273                 :     179962 :             chunk->alloc += num_bytes;
     274                 :            :         }
     275                 :            :     }
     276                 :            : 
     277                 :     188833 :     if (chunk == NULL) {
     278                 :            :         // no previous chunk, allocate a new chunk
     279                 :      12428 :         size_t alloc = MICROPY_ALLOC_PARSE_CHUNK_INIT;
     280         [ +  + ]:      12428 :         if (alloc < num_bytes) {
     281                 :         51 :             alloc = num_bytes;
     282                 :            :         }
     283                 :      12428 :         chunk = (mp_parse_chunk_t *)m_new(byte, sizeof(mp_parse_chunk_t) + alloc);
     284                 :      12428 :         chunk->alloc = alloc;
     285                 :      12428 :         chunk->union_.used = 0;
     286                 :      12428 :         parser->cur_chunk = chunk;
     287                 :            :     }
     288                 :            : 
     289                 :     247153 :     byte *ret = chunk->data + chunk->union_.used;
     290                 :     247153 :     chunk->union_.used += num_bytes;
     291                 :     247153 :     return ret;
     292                 :            : }
     293                 :            : 
     294                 :            : #if MICROPY_COMP_CONST_TUPLE
     295                 :        284 : STATIC void parser_free_parse_node_struct(parser_t *parser, mp_parse_node_struct_t *pns) {
     296                 :        284 :     mp_parse_chunk_t *chunk = parser->cur_chunk;
     297   [ +  +  +  + ]:        284 :     if (chunk->data <= (byte *)pns && (byte *)pns < chunk->data + chunk->union_.used) {
     298                 :        236 :         size_t num_bytes = sizeof(mp_parse_node_struct_t) + sizeof(mp_parse_node_t) * MP_PARSE_NODE_STRUCT_NUM_NODES(pns);
     299                 :        236 :         chunk->union_.used -= num_bytes;
     300                 :            :     }
     301                 :        284 : }
     302                 :            : #endif
     303                 :            : 
     304                 :   16902845 : STATIC void push_rule(parser_t *parser, size_t src_line, uint8_t rule_id, size_t arg_i) {
     305         [ +  + ]:   16902845 :     if (parser->rule_stack_top >= parser->rule_stack_alloc) {
     306                 :       1255 :         rule_stack_t *rs = m_renew(rule_stack_t, parser->rule_stack, parser->rule_stack_alloc, parser->rule_stack_alloc + MICROPY_ALLOC_PARSE_RULE_INC);
     307                 :       1255 :         parser->rule_stack = rs;
     308                 :       1255 :         parser->rule_stack_alloc += MICROPY_ALLOC_PARSE_RULE_INC;
     309                 :            :     }
     310                 :   16902845 :     rule_stack_t *rs = &parser->rule_stack[parser->rule_stack_top++];
     311                 :   16902845 :     rs->src_line = src_line;
     312                 :   16902845 :     rs->rule_id = rule_id;
     313                 :   16902845 :     rs->arg_i = arg_i;
     314                 :   16902845 : }
     315                 :            : 
     316                 :    9246885 : STATIC void push_rule_from_arg(parser_t *parser, size_t arg) {
     317         [ -  + ]:    9246885 :     assert((arg & RULE_ARG_KIND_MASK) == RULE_ARG_RULE || (arg & RULE_ARG_KIND_MASK) == RULE_ARG_OPT_RULE);
     318                 :    9246885 :     size_t rule_id = arg & RULE_ARG_ARG_MASK;
     319                 :    9246885 :     push_rule(parser, parser->lexer->tok_line, rule_id, 0);
     320                 :    9248049 : }
     321                 :            : 
     322                 :   16901812 : STATIC uint8_t pop_rule(parser_t *parser, size_t *arg_i, size_t *src_line) {
     323                 :   16901812 :     parser->rule_stack_top -= 1;
     324                 :   16901812 :     uint8_t rule_id = parser->rule_stack[parser->rule_stack_top].rule_id;
     325                 :   16901812 :     *arg_i = parser->rule_stack[parser->rule_stack_top].arg_i;
     326                 :   16901812 :     *src_line = parser->rule_stack[parser->rule_stack_top].src_line;
     327                 :   16901812 :     return rule_id;
     328                 :            : }
     329                 :            : 
     330                 :            : #if MICROPY_COMP_CONST_TUPLE
     331                 :       5228 : STATIC uint8_t peek_rule(parser_t *parser, size_t n) {
     332         [ -  + ]:       5228 :     assert(parser->rule_stack_top > n);
     333                 :       5228 :     return parser->rule_stack[parser->rule_stack_top - 1 - n].rule_id;
     334                 :            : }
     335                 :            : #endif
     336                 :            : 
     337                 :       8310 : bool mp_parse_node_get_int_maybe(mp_parse_node_t pn, mp_obj_t *o) {
     338         [ +  + ]:       8310 :     if (MP_PARSE_NODE_IS_SMALL_INT(pn)) {
     339                 :       3481 :         *o = MP_OBJ_NEW_SMALL_INT(MP_PARSE_NODE_LEAF_SMALL_INT(pn));
     340                 :       3481 :         return true;
     341   [ +  -  +  +  :       4829 :     } else if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, RULE_const_object)) {
                   +  + ]
     342                 :       1501 :         mp_parse_node_struct_t *pns = (mp_parse_node_struct_t *)pn;
     343         [ +  - ]:       1501 :         *o = mp_parse_node_extract_const_object(pns);
     344   [ +  -  +  -  :       2237 :         return mp_obj_is_int(*o);
                   +  + ]
     345                 :            :     } else {
     346                 :            :         return false;
     347                 :            :     }
     348                 :            : }
     349                 :            : 
     350                 :            : #if MICROPY_COMP_CONST_TUPLE || MICROPY_COMP_CONST
     351                 :      69354 : STATIC bool mp_parse_node_is_const(mp_parse_node_t pn) {
     352         [ +  + ]:      69354 :     if (MP_PARSE_NODE_IS_SMALL_INT(pn)) {
     353                 :            :         // Small integer.
     354                 :            :         return true;
     355         [ +  + ]:      62893 :     } else if (MP_PARSE_NODE_IS_LEAF(pn)) {
     356                 :            :         // Possible str, or constant literal.
     357                 :      14480 :         uintptr_t kind = MP_PARSE_NODE_LEAF_KIND(pn);
     358         [ +  + ]:      14480 :         if (kind == MP_PARSE_NODE_STRING) {
     359                 :            :             return true;
     360         [ +  + ]:      13116 :         } else if (kind == MP_PARSE_NODE_TOKEN) {
     361                 :       6374 :             uintptr_t arg = MP_PARSE_NODE_LEAF_ARG(pn);
     362                 :       6374 :             return arg == MP_TOKEN_KW_NONE
     363                 :            :                    || arg == MP_TOKEN_KW_FALSE
     364                 :            :                    || arg == MP_TOKEN_KW_TRUE
     365                 :       6374 :                    || arg == MP_TOKEN_ELLIPSIS;
     366                 :            :         }
     367   [ +  -  +  + ]:      48413 :     } else if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, RULE_const_object)) {
     368                 :            :         // Constant object.
     369                 :            :         return true;
     370         [ +  + ]:      47229 :     } else if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, RULE_atom_paren)) {
     371                 :            :         // Possible empty tuple.
     372                 :         82 :         mp_parse_node_struct_t *pns = (mp_parse_node_struct_t *)pn;
     373                 :         82 :         return MP_PARSE_NODE_IS_NULL(pns->nodes[0]);
     374                 :            :     }
     375                 :            :     return false;
     376                 :            : }
     377                 :            : 
     378                 :       7517 : STATIC mp_obj_t mp_parse_node_convert_to_obj(mp_parse_node_t pn) {
     379         [ -  + ]:       7517 :     assert(mp_parse_node_is_const(pn));
     380         [ +  + ]:       7517 :     if (MP_PARSE_NODE_IS_SMALL_INT(pn)) {
     381                 :       3165 :         mp_int_t arg = MP_PARSE_NODE_LEAF_SMALL_INT(pn);
     382                 :            :         #if MICROPY_DYNAMIC_COMPILER
     383                 :            :         mp_uint_t sign_mask = -((mp_uint_t)1 << (mp_dynamic_compiler.small_int_bits - 1));
     384                 :            :         if (!((arg & sign_mask) == 0 || (arg & sign_mask) == sign_mask)) {
     385                 :            :             // Integer doesn't fit in a small-int, so create a multi-precision int object.
     386                 :            :             return mp_obj_new_int_from_ll(arg);
     387                 :            :         }
     388                 :            :         #endif
     389                 :       3165 :         return MP_OBJ_NEW_SMALL_INT(arg);
     390         [ +  + ]:       4352 :     } else if (MP_PARSE_NODE_IS_LEAF(pn)) {
     391                 :       3784 :         uintptr_t kind = MP_PARSE_NODE_LEAF_KIND(pn);
     392                 :       3784 :         uintptr_t arg = MP_PARSE_NODE_LEAF_ARG(pn);
     393         [ +  + ]:       3784 :         if (kind == MP_PARSE_NODE_STRING) {
     394                 :        598 :             return MP_OBJ_NEW_QSTR(arg);
     395                 :            :         } else {
     396         [ -  + ]:       3186 :             assert(MP_PARSE_NODE_LEAF_KIND(pn) == MP_PARSE_NODE_TOKEN);
     397   [ +  +  +  + ]:       3186 :             switch (arg) {
     398                 :            :                 case MP_TOKEN_KW_NONE:
     399                 :            :                     return mp_const_none;
     400                 :        172 :                 case MP_TOKEN_KW_FALSE:
     401                 :        172 :                     return mp_const_false;
     402                 :       3004 :                 case MP_TOKEN_KW_TRUE:
     403                 :       3004 :                     return mp_const_true;
     404                 :          2 :                 default:
     405         [ -  + ]:          2 :                     assert(arg == MP_TOKEN_ELLIPSIS);
     406                 :            :                     return MP_OBJ_FROM_PTR(&mp_const_ellipsis_obj);
     407                 :            :             }
     408                 :            :         }
     409   [ +  -  +  + ]:        568 :     } else if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, RULE_const_object)) {
     410                 :        544 :         mp_parse_node_struct_t *pns = (mp_parse_node_struct_t *)pn;
     411                 :        544 :         return mp_parse_node_extract_const_object(pns);
     412                 :            :     } else {
     413         [ -  + ]:         24 :         assert(MP_PARSE_NODE_IS_STRUCT_KIND(pn, RULE_atom_paren));
     414         [ -  + ]:         24 :         assert(MP_PARSE_NODE_IS_NULL(((mp_parse_node_struct_t *)pn)->nodes[0]));
     415                 :            :         return mp_const_empty_tuple;
     416                 :            :     }
     417                 :            : }
     418                 :            : #endif
     419                 :            : 
     420                 :      56910 : STATIC bool parse_node_is_const_bool(mp_parse_node_t pn, bool value) {
     421                 :            :     // Returns true if 'pn' is a constant whose boolean value is equivalent to 'value'
     422                 :            :     #if MICROPY_COMP_CONST_TUPLE || MICROPY_COMP_CONST
     423   [ +  +  +  + ]:      56910 :     return mp_parse_node_is_const(pn) && mp_obj_is_true(mp_parse_node_convert_to_obj(pn)) == value;
     424                 :            :     #else
     425                 :            :     return MP_PARSE_NODE_IS_TOKEN_KIND(pn, value ? MP_TOKEN_KW_TRUE : MP_TOKEN_KW_FALSE)
     426                 :            :            || (MP_PARSE_NODE_IS_SMALL_INT(pn) && !!MP_PARSE_NODE_LEAF_SMALL_INT(pn) == value);
     427                 :            :     #endif
     428                 :            : }
     429                 :            : 
     430                 :      28604 : bool mp_parse_node_is_const_false(mp_parse_node_t pn) {
     431                 :      28604 :     return parse_node_is_const_bool(pn, false);
     432                 :            : }
     433                 :            : 
     434                 :      28306 : bool mp_parse_node_is_const_true(mp_parse_node_t pn) {
     435                 :      28306 :     return parse_node_is_const_bool(pn, true);
     436                 :            : }
     437                 :            : 
     438                 :     470672 : size_t mp_parse_node_extract_list(mp_parse_node_t *pn, size_t pn_kind, mp_parse_node_t **nodes) {
     439         [ +  + ]:     470672 :     if (MP_PARSE_NODE_IS_NULL(*pn)) {
     440                 :     244435 :         *nodes = NULL;
     441                 :     244435 :         return 0;
     442         [ +  + ]:     226237 :     } else if (MP_PARSE_NODE_IS_LEAF(*pn)) {
     443                 :      49367 :         *nodes = pn;
     444                 :      49367 :         return 1;
     445                 :            :     } else {
     446                 :     176870 :         mp_parse_node_struct_t *pns = (mp_parse_node_struct_t *)(*pn);
     447         [ +  + ]:     176870 :         if (MP_PARSE_NODE_STRUCT_KIND(pns) != pn_kind) {
     448                 :     142046 :             *nodes = pn;
     449                 :     142046 :             return 1;
     450                 :            :         } else {
     451                 :      34824 :             *nodes = pns->nodes;
     452                 :      34824 :             return MP_PARSE_NODE_STRUCT_NUM_NODES(pns);
     453                 :            :         }
     454                 :            :     }
     455                 :            : }
     456                 :            : 
     457                 :            : #if MICROPY_DEBUG_PRINTERS
     458                 :         78 : void mp_parse_node_print(const mp_print_t *print, mp_parse_node_t pn, size_t indent) {
     459   [ +  +  +  + ]:         78 :     if (MP_PARSE_NODE_IS_STRUCT(pn)) {
     460                 :         44 :         mp_printf(print, "[% 4d] ", (int)((mp_parse_node_struct_t *)pn)->source_line);
     461                 :            :     } else {
     462                 :         34 :         mp_printf(print, "       ");
     463                 :            :     }
     464         [ +  + ]:        410 :     for (size_t i = 0; i < indent; i++) {
     465                 :        332 :         mp_printf(print, " ");
     466                 :            :     }
     467         [ +  + ]:         78 :     if (MP_PARSE_NODE_IS_NULL(pn)) {
     468                 :          4 :         mp_printf(print, "NULL\n");
     469         [ +  + ]:         74 :     } else if (MP_PARSE_NODE_IS_SMALL_INT(pn)) {
     470                 :          2 :         mp_int_t arg = MP_PARSE_NODE_LEAF_SMALL_INT(pn);
     471                 :          2 :         mp_printf(print, "int(" INT_FMT ")\n", arg);
     472         [ +  + ]:         72 :     } else if (MP_PARSE_NODE_IS_LEAF(pn)) {
     473                 :         28 :         uintptr_t arg = MP_PARSE_NODE_LEAF_ARG(pn);
     474      [ +  +  + ]:         28 :         switch (MP_PARSE_NODE_LEAF_KIND(pn)) {
     475                 :         22 :             case MP_PARSE_NODE_ID:
     476                 :         22 :                 mp_printf(print, "id(%s)\n", qstr_str(arg));
     477                 :         22 :                 break;
     478                 :          2 :             case MP_PARSE_NODE_STRING:
     479                 :          2 :                 mp_printf(print, "str(%s)\n", qstr_str(arg));
     480                 :          2 :                 break;
     481                 :          4 :             default:
     482         [ -  + ]:          4 :                 assert(MP_PARSE_NODE_LEAF_KIND(pn) == MP_PARSE_NODE_TOKEN);
     483                 :          4 :                 mp_printf(print, "tok(%u)\n", (uint)arg);
     484                 :          4 :                 break;
     485                 :            :         }
     486                 :            :     } else {
     487                 :            :         // node must be a mp_parse_node_struct_t
     488                 :         44 :         mp_parse_node_struct_t *pns = (mp_parse_node_struct_t *)pn;
     489         [ +  + ]:         44 :         if (MP_PARSE_NODE_STRUCT_KIND(pns) == RULE_const_object) {
     490                 :         10 :             mp_obj_t obj = mp_parse_node_extract_const_object(pns);
     491                 :            :             #if MICROPY_OBJ_REPR == MICROPY_OBJ_REPR_D
     492                 :            :             mp_printf(print, "literal const(%016llx)=", obj);
     493                 :            :             #else
     494                 :         10 :             mp_printf(print, "literal const(%p)=", obj);
     495                 :            :             #endif
     496                 :         10 :             mp_obj_print_helper(print, obj, PRINT_REPR);
     497                 :         10 :             mp_printf(print, "\n");
     498                 :            :         } else {
     499                 :         34 :             size_t n = MP_PARSE_NODE_STRUCT_NUM_NODES(pns);
     500                 :            :             #if MICROPY_DEBUG_PARSE_RULE_NAME
     501                 :         34 :             mp_printf(print, "%s(%u) (n=%u)\n", rule_name_table[MP_PARSE_NODE_STRUCT_KIND(pns)], (uint)MP_PARSE_NODE_STRUCT_KIND(pns), (uint)n);
     502                 :            :             #else
     503                 :            :             mp_printf(print, "rule(%u) (n=%u)\n", (uint)MP_PARSE_NODE_STRUCT_KIND(pns), (uint)n);
     504                 :            :             #endif
     505         [ +  + ]:        110 :             for (size_t i = 0; i < n; i++) {
     506                 :         76 :                 mp_parse_node_print(print, pns->nodes[i], indent + 2);
     507                 :            :             }
     508                 :            :         }
     509                 :            :     }
     510                 :         78 : }
     511                 :            : #endif // MICROPY_DEBUG_PRINTERS
     512                 :            : 
     513                 :            : /*
     514                 :            : STATIC void result_stack_show(const mp_print_t *print, parser_t *parser) {
     515                 :            :     mp_printf(print, "result stack, most recent first\n");
     516                 :            :     for (ssize_t i = parser->result_stack_top - 1; i >= 0; i--) {
     517                 :            :         mp_parse_node_print(print, parser->result_stack[i], 0);
     518                 :            :     }
     519                 :            : }
     520                 :            : */
     521                 :            : 
     522                 :    1424159 : STATIC mp_parse_node_t pop_result(parser_t *parser) {
     523         [ -  + ]:    1424159 :     assert(parser->result_stack_top > 0);
     524                 :    1424159 :     return parser->result_stack[--parser->result_stack_top];
     525                 :            : }
     526                 :            : 
     527                 :    1476278 : STATIC mp_parse_node_t peek_result(parser_t *parser, size_t pos) {
     528         [ -  + ]:    1476278 :     assert(parser->result_stack_top > pos);
     529                 :    1476278 :     return parser->result_stack[parser->result_stack_top - 1 - pos];
     530                 :            : }
     531                 :            : 
     532                 :    1427892 : STATIC void push_result_node(parser_t *parser, mp_parse_node_t pn) {
     533         [ +  + ]:    1427892 :     if (parser->result_stack_top >= parser->result_stack_alloc) {
     534                 :        650 :         mp_parse_node_t *stack = m_renew(mp_parse_node_t, parser->result_stack, parser->result_stack_alloc, parser->result_stack_alloc + MICROPY_ALLOC_PARSE_RESULT_INC);
     535                 :        650 :         parser->result_stack = stack;
     536                 :        650 :         parser->result_stack_alloc += MICROPY_ALLOC_PARSE_RESULT_INC;
     537                 :            :     }
     538                 :    1427892 :     parser->result_stack[parser->result_stack_top++] = pn;
     539                 :    1427892 : }
     540                 :            : 
     541                 :       8186 : STATIC mp_parse_node_t make_node_const_object(parser_t *parser, size_t src_line, mp_obj_t obj) {
     542                 :       8186 :     mp_parse_node_struct_t *pn = parser_alloc(parser, sizeof(mp_parse_node_struct_t) + sizeof(mp_obj_t));
     543                 :       8186 :     pn->source_line = src_line;
     544                 :            :     #if MICROPY_OBJ_REPR == MICROPY_OBJ_REPR_D
     545                 :            :     // nodes are 32-bit pointers, but need to store 64-bit object
     546                 :            :     pn->kind_num_nodes = RULE_const_object | (2 << 8);
     547                 :            :     pn->nodes[0] = (uint64_t)obj;
     548                 :            :     pn->nodes[1] = (uint64_t)obj >> 32;
     549                 :            :     #else
     550                 :       8186 :     pn->kind_num_nodes = RULE_const_object | (1 << 8);
     551                 :       8186 :     pn->nodes[0] = (uintptr_t)obj;
     552                 :            :     #endif
     553                 :       8186 :     return (mp_parse_node_t)pn;
     554                 :            : }
     555                 :            : 
     556                 :            : // Create a parse node represeting a constant object, possibly optimising the case of
     557                 :            : // an integer, by putting the (small) integer value directly in the parse node itself.
     558                 :      28907 : STATIC mp_parse_node_t make_node_const_object_optimised(parser_t *parser, size_t src_line, mp_obj_t obj) {
     559         [ +  + ]:      28907 :     if (mp_obj_is_small_int(obj)) {
     560                 :      27628 :         mp_int_t val = MP_OBJ_SMALL_INT_VALUE(obj);
     561                 :            :         #if MICROPY_OBJ_REPR == MICROPY_OBJ_REPR_D
     562                 :            :         // A parse node is only 32-bits and the small-int value must fit in 31-bits
     563                 :            :         if (((val ^ (val << 1)) & 0xffffffff80000000) != 0) {
     564                 :            :             return make_node_const_object(parser, src_line, obj);
     565                 :            :         }
     566                 :            :         #endif
     567                 :            :         #if MICROPY_DYNAMIC_COMPILER
     568                 :            :         // Check that the integer value fits in target runtime's small-int
     569                 :            :         mp_uint_t sign_mask = -((mp_uint_t)1 << (mp_dynamic_compiler.small_int_bits - 1));
     570                 :            :         if (!((val & sign_mask) == 0 || (val & sign_mask) == sign_mask)) {
     571                 :            :             return make_node_const_object(parser, src_line, obj);
     572                 :            :         }
     573                 :            :         #endif
     574                 :      27628 :         return mp_parse_node_new_small_int(val);
     575                 :            :     } else {
     576                 :       1279 :         return make_node_const_object(parser, src_line, obj);
     577                 :            :     }
     578                 :            : }
     579                 :            : 
     580                 :     173086 : STATIC void push_result_token(parser_t *parser, uint8_t rule_id) {
     581                 :     173086 :     mp_parse_node_t pn;
     582                 :     173086 :     mp_lexer_t *lex = parser->lexer;
     583         [ +  + ]:     173086 :     if (lex->tok_kind == MP_TOKEN_NAME) {
     584                 :     114582 :         qstr id = qstr_from_strn(lex->vstr.buf, lex->vstr.len);
     585                 :            :         #if MICROPY_COMP_CONST
     586                 :            :         // if name is a standalone identifier, look it up in the table of dynamic constants
     587                 :     114569 :         mp_map_elem_t *elem;
     588         [ +  + ]:     114569 :         if (rule_id == RULE_atom
     589         [ +  + ]:      83418 :             && (elem = mp_map_lookup(&parser->consts, MP_OBJ_NEW_QSTR(id), MP_MAP_LOOKUP)) != NULL) {
     590                 :        189 :             pn = make_node_const_object_optimised(parser, lex->tok_line, elem->value);
     591                 :            :         } else {
     592                 :     114381 :             pn = mp_parse_node_new_leaf(MP_PARSE_NODE_ID, id);
     593                 :            :         }
     594                 :            :         #else
     595                 :            :         (void)rule_id;
     596                 :            :         pn = mp_parse_node_new_leaf(MP_PARSE_NODE_ID, id);
     597                 :            :         #endif
     598         [ +  + ]:      58504 :     } else if (lex->tok_kind == MP_TOKEN_INTEGER) {
     599                 :      25602 :         mp_obj_t o = mp_parse_num_integer(lex->vstr.buf, lex->vstr.len, 0, lex);
     600                 :      25590 :         pn = make_node_const_object_optimised(parser, lex->tok_line, o);
     601         [ +  + ]:      32902 :     } else if (lex->tok_kind == MP_TOKEN_FLOAT_OR_IMAG) {
     602                 :       1629 :         mp_obj_t o = mp_parse_num_float(lex->vstr.buf, lex->vstr.len, true, lex);
     603                 :       1629 :         pn = make_node_const_object(parser, lex->tok_line, o);
     604         [ +  + ]:      31273 :     } else if (lex->tok_kind == MP_TOKEN_STRING) {
     605                 :            :         // Don't automatically intern all strings.  Doc strings (which are usually large)
     606                 :            :         // will be discarded by the compiler, and so we shouldn't intern them.
     607                 :      15137 :         qstr qst = MP_QSTRnull;
     608         [ +  + ]:      15137 :         if (lex->vstr.len <= MICROPY_ALLOC_PARSE_INTERN_STRING_LEN) {
     609                 :            :             // intern short strings
     610                 :      12491 :             qst = qstr_from_strn(lex->vstr.buf, lex->vstr.len);
     611                 :            :         } else {
     612                 :            :             // check if this string is already interned
     613                 :       2646 :             qst = qstr_find_strn(lex->vstr.buf, lex->vstr.len);
     614                 :            :         }
     615         [ +  + ]:      15137 :         if (qst != MP_QSTRnull) {
     616                 :            :             // qstr exists, make a leaf node
     617                 :      12878 :             pn = mp_parse_node_new_leaf(MP_PARSE_NODE_STRING, qst);
     618                 :            :         } else {
     619                 :            :             // not interned, make a node holding a pointer to the string object
     620                 :       2259 :             mp_obj_t o = mp_obj_new_str_copy(&mp_type_str, (const byte *)lex->vstr.buf, lex->vstr.len);
     621                 :       2259 :             pn = make_node_const_object(parser, lex->tok_line, o);
     622                 :            :         }
     623         [ +  + ]:      16136 :     } else if (lex->tok_kind == MP_TOKEN_BYTES) {
     624                 :            :         // make a node holding a pointer to the bytes object
     625                 :       1840 :         mp_obj_t o = mp_obj_new_bytes((const byte *)lex->vstr.buf, lex->vstr.len);
     626                 :       1840 :         pn = make_node_const_object(parser, lex->tok_line, o);
     627                 :            :     } else {
     628                 :      14296 :         pn = mp_parse_node_new_leaf(MP_PARSE_NODE_TOKEN, lex->tok_kind);
     629                 :            :     }
     630                 :     173062 :     push_result_node(parser, pn);
     631                 :     173062 : }
     632                 :            : 
     633                 :            : #if MICROPY_COMP_MODULE_CONST
     634                 :            : STATIC const mp_rom_map_elem_t mp_constants_table[] = {
     635                 :            :     #if MICROPY_PY_UERRNO
     636                 :            :     { MP_ROM_QSTR(MP_QSTR_errno), MP_ROM_PTR(&mp_module_uerrno) },
     637                 :            :     #endif
     638                 :            :     #if MICROPY_PY_UCTYPES
     639                 :            :     { MP_ROM_QSTR(MP_QSTR_uctypes), MP_ROM_PTR(&mp_module_uctypes) },
     640                 :            :     #endif
     641                 :            :     // Extra constants as defined by a port
     642                 :            :     MICROPY_PORT_CONSTANTS
     643                 :            : };
     644                 :            : STATIC MP_DEFINE_CONST_MAP(mp_constants_map, mp_constants_table);
     645                 :            : #endif
     646                 :            : 
     647                 :            : STATIC void push_result_rule(parser_t *parser, size_t src_line, uint8_t rule_id, size_t num_args);
     648                 :            : 
     649                 :            : #if MICROPY_COMP_CONST_FOLDING
     650                 :            : #if MICROPY_COMP_CONST_FOLDING_COMPILER_WORKAROUND
     651                 :            : // Some versions of the xtensa-esp32-elf-gcc compiler generate wrong code if this
     652                 :            : // function is static, so provide a hook for them to work around this problem.
     653                 :            : MP_NOINLINE
     654                 :            : #endif
     655                 :     243439 : STATIC bool fold_logical_constants(parser_t *parser, uint8_t rule_id, size_t *num_args) {
     656                 :     243439 :     if (rule_id == RULE_or_test
     657         [ +  + ]:     243439 :         || rule_id == RULE_and_test) {
     658                 :            :         // folding for binary logical ops: or and
     659                 :        493 :         size_t copy_to = *num_args;
     660         [ +  - ]:        974 :         for (size_t i = copy_to; i > 0;) {
     661                 :        974 :             mp_parse_node_t pn = peek_result(parser, --i);
     662                 :        974 :             parser->result_stack[parser->result_stack_top - copy_to] = pn;
     663         [ +  + ]:        974 :             if (i == 0) {
     664                 :            :                 // always need to keep the last value
     665                 :            :                 break;
     666                 :            :             }
     667         [ +  + ]:        503 :             if (rule_id == RULE_or_test) {
     668         [ +  + ]:        186 :                 if (mp_parse_node_is_const_true(pn)) {
     669                 :            :                     //
     670                 :            :                     break;
     671         [ +  + ]:        176 :                 } else if (!mp_parse_node_is_const_false(pn)) {
     672                 :        166 :                     copy_to -= 1;
     673                 :            :                 }
     674                 :            :             } else {
     675                 :            :                 // RULE_and_test
     676         [ +  + ]:        317 :                 if (mp_parse_node_is_const_false(pn)) {
     677                 :            :                     break;
     678         [ +  + ]:        305 :                 } else if (!mp_parse_node_is_const_true(pn)) {
     679                 :        295 :                     copy_to -= 1;
     680                 :            :                 }
     681                 :            :             }
     682                 :            :         }
     683                 :        493 :         copy_to -= 1; // copy_to now contains number of args to pop
     684                 :            : 
     685                 :            :         // pop and discard all the short-circuited expressions
     686         [ +  + ]:        535 :         for (size_t i = 0; i < copy_to; ++i) {
     687                 :         42 :             pop_result(parser);
     688                 :            :         }
     689                 :        493 :         *num_args -= copy_to;
     690                 :            : 
     691                 :            :         // we did a complete folding if there's only 1 arg left
     692                 :        493 :         return *num_args == 1;
     693                 :            : 
     694         [ +  + ]:     242946 :     } else if (rule_id == RULE_not_test_2) {
     695                 :            :         // folding for unary logical op: not
     696                 :        472 :         mp_parse_node_t pn = peek_result(parser, 0);
     697         [ +  + ]:        472 :         if (mp_parse_node_is_const_false(pn)) {
     698                 :            :             pn = mp_parse_node_new_leaf(MP_PARSE_NODE_TOKEN, MP_TOKEN_KW_TRUE);
     699         [ +  + ]:        438 :         } else if (mp_parse_node_is_const_true(pn)) {
     700                 :            :             pn = mp_parse_node_new_leaf(MP_PARSE_NODE_TOKEN, MP_TOKEN_KW_FALSE);
     701                 :            :         } else {
     702                 :            :             return false;
     703                 :            :         }
     704                 :         60 :         pop_result(parser);
     705                 :         60 :         push_result_node(parser, pn);
     706                 :         60 :         return true;
     707                 :            :     }
     708                 :            : 
     709                 :            :     return false;
     710                 :            : }
     711                 :            : 
     712                 :     243346 : STATIC bool fold_constants(parser_t *parser, uint8_t rule_id, size_t num_args) {
     713                 :            :     // this code does folding of arbitrary integer expressions, eg 1 + 2 * 3 + 4
     714                 :            :     // it does not do partial folding, eg 1 + 2 + x -> 3 + x
     715                 :            : 
     716                 :     243346 :     mp_obj_t arg0;
     717                 :     243346 :     if (rule_id == RULE_expr
     718                 :            :         || rule_id == RULE_xor_expr
     719                 :     243346 :         || rule_id == RULE_and_expr
     720   [ +  +  +  +  :     243346 :         || rule_id == RULE_power) {
                   +  + ]
     721                 :            :         // folding for binary ops: | ^ & **
     722                 :       1299 :         mp_parse_node_t pn = peek_result(parser, num_args - 1);
     723         [ +  + ]:       1299 :         if (!mp_parse_node_get_int_maybe(pn, &arg0)) {
     724                 :            :             return false;
     725                 :            :         }
     726                 :        694 :         mp_binary_op_t op;
     727   [ +  +  +  + ]:        694 :         if (rule_id == RULE_expr) {
     728                 :            :             op = MP_BINARY_OP_OR;
     729                 :            :         } else if (rule_id == RULE_xor_expr) {
     730                 :            :             op = MP_BINARY_OP_XOR;
     731                 :            :         } else if (rule_id == RULE_and_expr) {
     732                 :            :             op = MP_BINARY_OP_AND;
     733                 :            :         } else {
     734                 :        694 :             op = MP_BINARY_OP_POWER;
     735                 :            :         }
     736         [ +  + ]:       1438 :         for (ssize_t i = num_args - 2; i >= 0; --i) {
     737                 :        774 :             pn = peek_result(parser, i);
     738                 :        774 :             mp_obj_t arg1;
     739         [ +  + ]:        774 :             if (!mp_parse_node_get_int_maybe(pn, &arg1)) {
     740                 :         30 :                 return false;
     741                 :            :             }
     742   [ +  +  +  + ]:        750 :             if (op == MP_BINARY_OP_POWER && mp_obj_int_sign(arg1) < 0) {
     743                 :            :                 // ** can't have negative rhs
     744                 :            :                 return false;
     745                 :            :             }
     746                 :        744 :             arg0 = mp_binary_op(op, arg0, arg1);
     747                 :            :         }
     748                 :            :     } else if (rule_id == RULE_shift_expr
     749                 :            :                || rule_id == RULE_arith_expr
     750                 :            :                || rule_id == RULE_term) {
     751                 :            :         // folding for binary ops: << >> + - * @ / % //
     752                 :       3198 :         mp_parse_node_t pn = peek_result(parser, num_args - 1);
     753         [ +  + ]:       3198 :         if (!mp_parse_node_get_int_maybe(pn, &arg0)) {
     754                 :            :             return false;
     755                 :            :         }
     756         [ +  + ]:       1227 :         for (ssize_t i = num_args - 2; i >= 1; i -= 2) {
     757                 :        751 :             pn = peek_result(parser, i - 1);
     758                 :        751 :             mp_obj_t arg1;
     759         [ +  + ]:        751 :             if (!mp_parse_node_get_int_maybe(pn, &arg1)) {
     760                 :        257 :                 return false;
     761                 :            :             }
     762                 :        544 :             mp_token_kind_t tok = MP_PARSE_NODE_LEAF_ARG(peek_result(parser, i));
     763         [ +  + ]:        544 :             if (tok == MP_TOKEN_OP_AT || tok == MP_TOKEN_OP_SLASH) {
     764                 :            :                 // Can't fold @ or /
     765                 :            :                 return false;
     766                 :            :             }
     767                 :        518 :             mp_binary_op_t op = MP_BINARY_OP_LSHIFT + (tok - MP_TOKEN_OP_DBL_LESS);
     768                 :        518 :             int rhs_sign = mp_obj_int_sign(arg1);
     769         [ +  + ]:        518 :             if (op <= MP_BINARY_OP_RSHIFT) {
     770                 :            :                 // << and >> can't have negative rhs
     771         [ +  + ]:        276 :                 if (rhs_sign < 0) {
     772                 :            :                     return false;
     773                 :            :                 }
     774         [ +  + ]:        242 :             } else if (op >= MP_BINARY_OP_FLOOR_DIVIDE) {
     775                 :            :                 // % and // can't have zero rhs
     776         [ +  + ]:         45 :                 if (rhs_sign == 0) {
     777                 :            :                     return false;
     778                 :            :                 }
     779                 :            :             }
     780                 :        494 :             arg0 = mp_binary_op(op, arg0, arg1);
     781                 :            :         }
     782                 :            :     } else if (rule_id == RULE_factor_2) {
     783                 :            :         // folding for unary ops: + - ~
     784                 :       2288 :         mp_parse_node_t pn = peek_result(parser, 0);
     785         [ +  + ]:       2288 :         if (!mp_parse_node_get_int_maybe(pn, &arg0)) {
     786                 :            :             return false;
     787                 :            :         }
     788                 :       1496 :         mp_token_kind_t tok = MP_PARSE_NODE_LEAF_ARG(peek_result(parser, 1));
     789                 :       1496 :         mp_unary_op_t op;
     790         [ +  + ]:       1496 :         if (tok == MP_TOKEN_OP_TILDE) {
     791                 :            :             op = MP_UNARY_OP_INVERT;
     792                 :            :         } else {
     793         [ -  + ]:       1478 :             assert(tok == MP_TOKEN_OP_PLUS || tok == MP_TOKEN_OP_MINUS); // should be
     794                 :            :             op = MP_UNARY_OP_POSITIVE + (tok - MP_TOKEN_OP_PLUS);
     795                 :            :         }
     796                 :       1496 :         arg0 = mp_unary_op(op, arg0);
     797                 :            : 
     798                 :            :     #if MICROPY_COMP_CONST
     799                 :            :     } else if (rule_id == RULE_expr_stmt) {
     800                 :      33535 :         mp_parse_node_t pn1 = peek_result(parser, 0);
     801         [ +  + ]:      33535 :         if (!MP_PARSE_NODE_IS_NULL(pn1)
     802   [ +  +  +  + ]:       9162 :             && !(MP_PARSE_NODE_IS_STRUCT_KIND(pn1, RULE_expr_stmt_augassign)
     803                 :            :                  || MP_PARSE_NODE_IS_STRUCT_KIND(pn1, RULE_expr_stmt_assign_list))) {
     804                 :            :             // this node is of the form <x> = <y>
     805                 :       8733 :             mp_parse_node_t pn0 = peek_result(parser, 1);
     806         [ +  + ]:       8733 :             if (MP_PARSE_NODE_IS_ID(pn0)
     807   [ +  +  +  + ]:       6327 :                 && MP_PARSE_NODE_IS_STRUCT_KIND(pn1, RULE_atom_expr_normal)
     808         [ +  + ]:       3138 :                 && MP_PARSE_NODE_IS_ID(((mp_parse_node_struct_t *)pn1)->nodes[0])
     809         [ +  + ]:       3118 :                 && MP_PARSE_NODE_LEAF_ARG(((mp_parse_node_struct_t *)pn1)->nodes[0]) == MP_QSTR_const
     810   [ +  -  +  -  :        101 :                 && MP_PARSE_NODE_IS_STRUCT_KIND(((mp_parse_node_struct_t *)pn1)->nodes[1], RULE_trailer_paren)
                   +  - ]
     811                 :            :                 ) {
     812                 :            :                 // code to assign dynamic constants: id = const(value)
     813                 :            : 
     814                 :            :                 // get the id
     815                 :        101 :                 qstr id = MP_PARSE_NODE_LEAF_ARG(pn0);
     816                 :            : 
     817                 :            :                 // get the value
     818                 :        101 :                 mp_parse_node_t pn_value = ((mp_parse_node_struct_t *)((mp_parse_node_struct_t *)pn1)->nodes[1])->nodes[0];
     819         [ +  + ]:        101 :                 if (!mp_parse_node_is_const(pn_value)) {
     820                 :         32 :                     mp_obj_t exc = mp_obj_new_exception_msg(&mp_type_SyntaxError,
     821                 :         32 :                         MP_ERROR_TEXT("not a constant"));
     822                 :         32 :                     mp_obj_exception_add_traceback(exc, parser->lexer->source_name,
     823                 :         32 :                         ((mp_parse_node_struct_t *)pn1)->source_line, MP_QSTRnull);
     824                 :         32 :                     nlr_raise(exc);
     825                 :            :                 }
     826                 :         69 :                 mp_obj_t value = mp_parse_node_convert_to_obj(pn_value);
     827                 :            : 
     828                 :            :                 // store the value in the table of dynamic constants
     829                 :         69 :                 mp_map_elem_t *elem = mp_map_lookup(&parser->consts, MP_OBJ_NEW_QSTR(id), MP_MAP_LOOKUP_ADD_IF_NOT_FOUND);
     830         [ -  + ]:         69 :                 assert(elem->value == MP_OBJ_NULL);
     831                 :         69 :                 elem->value = value;
     832                 :            : 
     833                 :            :                 // If the constant starts with an underscore then treat it as a private
     834                 :            :                 // variable and don't emit any code to store the value to the id.
     835         [ +  + ]:         69 :                 if (qstr_str(id)[0] == '_') {
     836                 :         38 :                     pop_result(parser); // pop const(value)
     837                 :         38 :                     pop_result(parser); // pop id
     838                 :         38 :                     push_result_rule(parser, 0, RULE_pass_stmt, 0); // replace with "pass"
     839                 :         38 :                     return true;
     840                 :            :                 }
     841                 :            : 
     842                 :            :                 // replace const(value) with value
     843                 :         31 :                 pop_result(parser);
     844                 :         31 :                 push_result_node(parser, pn_value);
     845                 :            : 
     846                 :            :                 // finished folding this assignment, but we still want it to be part of the tree
     847                 :         31 :                 return false;
     848                 :            :             }
     849                 :            :         }
     850                 :            :         return false;
     851                 :            :     #endif
     852                 :            : 
     853                 :            :     #if MICROPY_COMP_MODULE_CONST
     854                 :            :     } else if (rule_id == RULE_atom_expr_normal) {
     855                 :      48014 :         mp_parse_node_t pn0 = peek_result(parser, 1);
     856                 :      48014 :         mp_parse_node_t pn1 = peek_result(parser, 0);
     857   [ +  +  +  - ]:      48014 :         if (!(MP_PARSE_NODE_IS_ID(pn0)
     858   [ +  -  +  + ]:      46460 :               && MP_PARSE_NODE_IS_STRUCT_KIND(pn1, RULE_trailer_period))) {
     859                 :      47522 :             return false;
     860                 :            :         }
     861                 :            :         // id1.id2
     862                 :            :         // look it up in constant table, see if it can be replaced with an integer
     863                 :       4984 :         mp_parse_node_struct_t *pns1 = (mp_parse_node_struct_t *)pn1;
     864         [ -  + ]:       4984 :         assert(MP_PARSE_NODE_IS_ID(pns1->nodes[0]));
     865                 :       4984 :         qstr q_base = MP_PARSE_NODE_LEAF_ARG(pn0);
     866                 :       4984 :         qstr q_attr = MP_PARSE_NODE_LEAF_ARG(pns1->nodes[0]);
     867                 :       4984 :         mp_map_elem_t *elem = mp_map_lookup((mp_map_t *)&mp_constants_map, MP_OBJ_NEW_QSTR(q_base), MP_MAP_LOOKUP);
     868         [ +  + ]:       4984 :         if (elem == NULL) {
     869                 :            :             return false;
     870                 :            :         }
     871                 :        494 :         mp_obj_t dest[2];
     872                 :        494 :         mp_load_method_maybe(elem->value, q_attr, dest);
     873   [ +  -  +  +  :        494 :         if (!(dest[0] != MP_OBJ_NULL && mp_obj_is_int(dest[0]) && dest[1] == MP_OBJ_NULL)) {
          -  +  -  -  +  
                      - ]
     874                 :            :             return false;
     875                 :            :         }
     876                 :        492 :         arg0 = dest[0];
     877                 :            :     #endif
     878                 :            : 
     879                 :            :     } else {
     880                 :            :         return false;
     881                 :            :     }
     882                 :            : 
     883                 :            :     // success folding this rule
     884                 :            : 
     885         [ +  + ]:       9964 :     for (size_t i = num_args; i > 0; i--) {
     886                 :       6836 :         pop_result(parser);
     887                 :            :     }
     888                 :       3128 :     push_result_node(parser, make_node_const_object_optimised(parser, 0, arg0));
     889                 :            : 
     890                 :       3128 :     return true;
     891                 :            : }
     892                 :            : #endif
     893                 :            : 
     894                 :            : #if MICROPY_COMP_CONST_TUPLE
     895                 :       2334 : STATIC bool build_tuple_from_stack(parser_t *parser, size_t src_line, size_t num_args) {
     896         [ +  + ]:       6005 :     for (size_t i = num_args; i > 0;) {
     897                 :       4826 :         mp_parse_node_t pn = peek_result(parser, --i);
     898         [ +  + ]:       4826 :         if (!mp_parse_node_is_const(pn)) {
     899                 :            :             return false;
     900                 :            :         }
     901                 :            :     }
     902                 :       1179 :     mp_obj_tuple_t *tuple = MP_OBJ_TO_PTR(mp_obj_new_tuple(num_args, NULL));
     903         [ +  + ]:       4449 :     for (size_t i = num_args; i > 0;) {
     904                 :       3270 :         mp_parse_node_t pn = pop_result(parser);
     905                 :       3270 :         tuple->items[--i] = mp_parse_node_convert_to_obj(pn);
     906   [ +  -  +  + ]:       3270 :         if (MP_PARSE_NODE_IS_STRUCT(pn)) {
     907                 :        284 :             parser_free_parse_node_struct(parser, (mp_parse_node_struct_t *)pn);
     908                 :            :         }
     909                 :            :     }
     910                 :       1179 :     push_result_node(parser, make_node_const_object(parser, src_line, MP_OBJ_FROM_PTR(tuple)));
     911                 :       1179 :     return true;
     912                 :            : }
     913                 :            : 
     914                 :     240147 : STATIC bool build_tuple(parser_t *parser, size_t src_line, uint8_t rule_id, size_t num_args) {
     915         [ +  + ]:     240147 :     if (rule_id == RULE_testlist_comp) {
     916         [ +  + ]:       1751 :         if (peek_rule(parser, 0) == RULE_atom_paren) {
     917                 :            :             // Tuple of the form "(a,)".
     918                 :       1277 :             return build_tuple_from_stack(parser, src_line, num_args);
     919                 :            :         }
     920                 :            :     }
     921         [ +  + ]:     238870 :     if (rule_id == RULE_testlist_comp_3c) {
     922         [ -  + ]:       1159 :         assert(peek_rule(parser, 0) == RULE_testlist_comp_3b);
     923         [ -  + ]:       1159 :         assert(peek_rule(parser, 1) == RULE_testlist_comp);
     924         [ +  + ]:       1159 :         if (peek_rule(parser, 2) == RULE_atom_paren) {
     925                 :            :             // Tuple of the form "(a, b)".
     926         [ +  + ]:        735 :             if (build_tuple_from_stack(parser, src_line, num_args)) {
     927                 :        403 :                 parser->rule_stack_top -= 2; // discard 2 rules
     928                 :        403 :                 return true;
     929                 :            :             }
     930                 :            :         }
     931                 :            :     }
     932                 :     238467 :     if (rule_id == RULE_testlist_star_expr
     933         [ +  + ]:     238467 :         || rule_id == RULE_testlist
     934         [ -  + ]:     238145 :         || rule_id == RULE_subscriptlist) {
     935                 :            :         // Tuple of the form:
     936                 :            :         //  - x = a, b
     937                 :            :         //  - return a, b
     938                 :            :         //  - for x in a, b: pass
     939                 :            :         //  - x[a, b]
     940                 :        322 :         return build_tuple_from_stack(parser, src_line, num_args);
     941                 :            :     }
     942                 :            : 
     943                 :            :     return false;
     944                 :            : }
     945                 :            : #endif
     946                 :            : 
     947                 :     246058 : STATIC void push_result_rule(parser_t *parser, size_t src_line, uint8_t rule_id, size_t num_args) {
     948                 :            :     // Simplify and optimise certain rules, to reduce memory usage and simplify the compiler.
     949         [ +  + ]:     246058 :     if (rule_id == RULE_atom_paren) {
     950                 :            :         // Remove parenthesis around a single expression if possible.
     951                 :            :         // This atom_paren rule always has a single argument, and after this
     952                 :            :         // optimisation that argument is either NULL or testlist_comp.
     953                 :       2991 :         mp_parse_node_t pn = peek_result(parser, 0);
     954         [ +  + ]:       2991 :         if (MP_PARSE_NODE_IS_NULL(pn)) {
     955                 :            :             // need to keep parenthesis for ()
     956   [ +  +  +  + ]:       2747 :         } else if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, RULE_testlist_comp)) {
     957                 :            :             // need to keep parenthesis for (a, b, ...)
     958                 :            :         } else {
     959                 :            :             // parenthesis around a single expression, so it's just the expression
     960                 :            :             return;
     961                 :            :         }
     962         [ +  + ]:     243067 :     } else if (rule_id == RULE_testlist_comp) {
     963                 :            :         // The testlist_comp rule can be the sole argument to either atom_parent
     964                 :            :         // or atom_bracket, for (...) and [...] respectively.
     965         [ -  + ]:       2507 :         assert(num_args == 2);
     966                 :       2507 :         mp_parse_node_t pn = peek_result(parser, 0);
     967   [ +  -  +  + ]:       2507 :         if (MP_PARSE_NODE_IS_STRUCT(pn)) {
     968                 :       1408 :             mp_parse_node_struct_t *pns = (mp_parse_node_struct_t *)pn;
     969         [ +  + ]:       1408 :             if (MP_PARSE_NODE_STRUCT_KIND(pns) == RULE_testlist_comp_3b) {
     970                 :            :                 // tuple of one item, with trailing comma
     971                 :        241 :                 pop_result(parser);
     972                 :        241 :                 --num_args;
     973         [ +  + ]:       1167 :             } else if (MP_PARSE_NODE_STRUCT_KIND(pns) == RULE_testlist_comp_3c) {
     974                 :            :                 // tuple of many items, convert testlist_comp_3c to testlist_comp
     975                 :        756 :                 pop_result(parser);
     976         [ -  + ]:        756 :                 assert(pn == peek_result(parser, 0));
     977                 :        756 :                 pns->kind_num_nodes = rule_id | MP_PARSE_NODE_STRUCT_NUM_NODES(pns) << 8;
     978                 :        756 :                 return;
     979                 :            :             } else if (MP_PARSE_NODE_STRUCT_KIND(pns) == RULE_comp_for) {
     980                 :            :                 // generator expression
     981                 :            :             } else {
     982                 :            :                 // tuple with 2 items
     983                 :            :             }
     984                 :            :         } else {
     985                 :            :             // tuple with 2 items
     986                 :            :         }
     987         [ +  + ]:     240560 :     } else if (rule_id == RULE_testlist_comp_3c) {
     988                 :            :         // steal first arg of outer testlist_comp rule
     989                 :       1159 :         ++num_args;
     990                 :            :     }
     991                 :            : 
     992                 :            :     #if MICROPY_COMP_CONST_FOLDING
     993         [ +  + ]:     243438 :     if (fold_logical_constants(parser, rule_id, &num_args)) {
     994                 :            :         // we folded this rule so return straight away
     995                 :            :         return;
     996                 :            :     }
     997         [ +  + ]:     243345 :     if (fold_constants(parser, rule_id, num_args)) {
     998                 :            :         // we folded this rule so return straight away
     999                 :            :         return;
    1000                 :            :     }
    1001                 :            :     #endif
    1002                 :            : 
    1003                 :            :     #if MICROPY_COMP_CONST_TUPLE
    1004         [ +  + ]:     240147 :     if (build_tuple(parser, src_line, rule_id, num_args)) {
    1005                 :            :         // we built a tuple from this rule so return straightaway
    1006                 :            :         return;
    1007                 :            :     }
    1008                 :            :     #endif
    1009                 :            : 
    1010                 :     238968 :     mp_parse_node_struct_t *pn = parser_alloc(parser, sizeof(mp_parse_node_struct_t) + sizeof(mp_parse_node_t) * num_args);
    1011                 :     238967 :     pn->source_line = src_line;
    1012                 :     238967 :     pn->kind_num_nodes = (rule_id & 0xff) | (num_args << 8);
    1013         [ +  + ]:     701694 :     for (size_t i = num_args; i > 0; i--) {
    1014                 :     462727 :         pn->nodes[i - 1] = pop_result(parser);
    1015                 :            :     }
    1016         [ +  + ]:     238967 :     if (rule_id == RULE_testlist_comp_3c) {
    1017                 :            :         // need to push something non-null to replace stolen first arg of testlist_comp
    1018                 :        756 :         push_result_node(parser, (mp_parse_node_t)pn);
    1019                 :            :     }
    1020                 :     238967 :     push_result_node(parser, (mp_parse_node_t)pn);
    1021                 :            : }
    1022                 :            : 
    1023                 :       3716 : mp_parse_tree_t mp_parse(mp_lexer_t *lex, mp_parse_input_kind_t input_kind) {
    1024                 :            : 
    1025                 :            :     // initialise parser and allocate memory for its stacks
    1026                 :            : 
    1027                 :       3716 :     parser_t parser;
    1028                 :            : 
    1029                 :       3716 :     parser.rule_stack_alloc = MICROPY_ALLOC_PARSE_RULE_INIT;
    1030                 :       3716 :     parser.rule_stack_top = 0;
    1031                 :       3716 :     parser.rule_stack = m_new(rule_stack_t, parser.rule_stack_alloc);
    1032                 :            : 
    1033                 :       3716 :     parser.result_stack_alloc = MICROPY_ALLOC_PARSE_RESULT_INIT;
    1034                 :       3716 :     parser.result_stack_top = 0;
    1035                 :       3716 :     parser.result_stack = m_new(mp_parse_node_t, parser.result_stack_alloc);
    1036                 :            : 
    1037                 :       3716 :     parser.lexer = lex;
    1038                 :            : 
    1039                 :       3716 :     parser.tree.chunk = NULL;
    1040                 :       3716 :     parser.cur_chunk = NULL;
    1041                 :            : 
    1042                 :            :     #if MICROPY_COMP_CONST
    1043                 :       3716 :     mp_map_init(&parser.consts, 0);
    1044                 :            :     #endif
    1045                 :            : 
    1046                 :            :     // work out the top-level rule to use, and push it on the stack
    1047                 :       3716 :     size_t top_level_rule;
    1048      [ +  +  + ]:       3716 :     switch (input_kind) {
    1049                 :            :         case MP_PARSE_SINGLE_INPUT:
    1050                 :            :             top_level_rule = RULE_single_input;
    1051                 :            :             break;
    1052                 :        374 :         case MP_PARSE_EVAL_INPUT:
    1053                 :        374 :             top_level_rule = RULE_eval_input;
    1054                 :        374 :             break;
    1055                 :       3119 :         default:
    1056                 :       3119 :             top_level_rule = RULE_file_input;
    1057                 :            :     }
    1058                 :       3716 :     push_rule(&parser, lex->tok_line, top_level_rule, 0);
    1059                 :            : 
    1060                 :            :     // parse!
    1061                 :            : 
    1062                 :       3716 :     bool backtrack = false;
    1063                 :            : 
    1064                 :    2725972 :     for (;;) {
    1065                 :   16906611 :     next_rule:
    1066         [ +  + ]:   16910327 :         if (parser.rule_stack_top == 0) {
    1067                 :            :             break;
    1068                 :            :         }
    1069                 :            : 
    1070                 :            :         // Pop the next rule to process it
    1071                 :   16906699 :         size_t i; // state for the current rule
    1072                 :   16906699 :         size_t rule_src_line; // source line for the first token matched by the current rule
    1073                 :   16906699 :         uint8_t rule_id = pop_rule(&parser, &i, &rule_src_line);
    1074                 :   16906212 :         uint8_t rule_act = rule_act_table[rule_id];
    1075                 :   16906212 :         const uint16_t *rule_arg = get_rule_arg(rule_id);
    1076                 :   16906212 :         size_t n = rule_act & RULE_ACT_ARG_MASK;
    1077                 :            : 
    1078                 :            :         #if 0
    1079                 :            :         // debugging
    1080                 :            :         printf("depth=" UINT_FMT " ", parser.rule_stack_top);
    1081                 :            :         for (int j = 0; j < parser.rule_stack_top; ++j) {
    1082                 :            :             printf(" ");
    1083                 :            :         }
    1084                 :            :         printf("%s n=" UINT_FMT " i=" UINT_FMT " bt=%d\n", rule_name_table[rule_id], n, i, backtrack);
    1085                 :            :         #endif
    1086                 :            : 
    1087      [ +  +  + ]:   16906212 :         switch (rule_act & RULE_ACT_KIND_MASK) {
    1088                 :    5627189 :             case RULE_ACT_OR:
    1089   [ +  +  +  + ]:    5627189 :                 if (i > 0 && !backtrack) {
    1090                 :     139303 :                     goto next_rule;
    1091                 :            :                 } else {
    1092                 :    9109924 :                     backtrack = false;
    1093                 :            :                 }
    1094         [ +  + ]:    9109924 :                 for (; i < n; ++i) {
    1095                 :    8496904 :                     uint16_t kind = rule_arg[i] & RULE_ARG_KIND_MASK;
    1096         [ +  + ]:    8496904 :                     if (kind == RULE_ARG_TOK) {
    1097         [ +  + ]:    3763973 :                         if (lex->tok_kind == (rule_arg[i] & RULE_ARG_ARG_MASK)) {
    1098                 :     141935 :                             push_result_token(&parser, rule_id);
    1099                 :     141911 :                             mp_lexer_to_next(lex);
    1100                 :     141911 :                             goto next_rule;
    1101                 :            :                         }
    1102                 :            :                     } else {
    1103         [ -  + ]:    4732931 :                         assert(kind == RULE_ARG_RULE);
    1104         [ +  + ]:    4732931 :                         if (i + 1 < n) {
    1105                 :    3139513 :                             push_rule(&parser, rule_src_line, rule_id, i + 1); // save this or-rule
    1106                 :            :                         }
    1107                 :    4732811 :                         push_rule_from_arg(&parser, rule_arg[i]); // push child of or-rule
    1108                 :    4732733 :                         goto next_rule;
    1109                 :            :                     }
    1110                 :            :                 }
    1111                 :            :                 backtrack = true;
    1112                 :            :                 break;
    1113                 :            : 
    1114                 :    6533469 :             case RULE_ACT_AND: {
    1115                 :            : 
    1116                 :            :                 // failed, backtrack if we can, else syntax error
    1117         [ +  + ]:    6533469 :                 if (backtrack) {
    1118         [ -  + ]:    1025293 :                     assert(i > 0);
    1119         [ +  + ]:    1025293 :                     if ((rule_arg[i - 1] & RULE_ARG_KIND_MASK) == RULE_ARG_OPT_RULE) {
    1120                 :            :                         // an optional rule that failed, so continue with next arg
    1121                 :     492455 :                         push_result_node(&parser, MP_PARSE_NODE_NULL);
    1122                 :     492455 :                         backtrack = false;
    1123                 :            :                     } else {
    1124                 :            :                         // a mandatory rule that failed, so propagate backtrack
    1125         [ +  + ]:     532838 :                         if (i > 1) {
    1126                 :            :                             // already eaten tokens so can't backtrack
    1127                 :         32 :                             goto syntax_error;
    1128                 :            :                         } else {
    1129                 :     532834 :                             goto next_rule;
    1130                 :            :                         }
    1131                 :            :                     }
    1132                 :            :                 }
    1133                 :            : 
    1134                 :            :                 // progress through the rule
    1135         [ +  + ]:    6353752 :                 for (; i < n; ++i) {
    1136         [ +  + ]:    5637281 :                     if ((rule_arg[i] & RULE_ARG_KIND_MASK) == RULE_ARG_TOK) {
    1137                 :            :                         // need to match a token
    1138                 :    3845361 :                         mp_token_kind_t tok_kind = rule_arg[i] & RULE_ARG_ARG_MASK;
    1139         [ +  + ]:    3845361 :                         if (lex->tok_kind == tok_kind) {
    1140                 :            :                             // matched token
    1141         [ +  + ]:     352380 :                             if (tok_kind == MP_TOKEN_NAME) {
    1142                 :      28224 :                                 push_result_token(&parser, rule_id);
    1143                 :            :                             }
    1144                 :     352380 :                             mp_lexer_to_next(lex);
    1145                 :            :                         } else {
    1146                 :            :                             // failed to match token
    1147         [ +  + ]:    3492981 :                             if (i > 0) {
    1148                 :            :                                 // already eaten tokens so can't backtrack
    1149                 :         24 :                                 goto syntax_error;
    1150                 :            :                             } else {
    1151                 :            :                                 // this rule failed, so backtrack
    1152                 :    3492957 :                                 backtrack = true;
    1153                 :    3492957 :                                 goto next_rule;
    1154                 :            :                             }
    1155                 :            :                         }
    1156                 :            :                     } else {
    1157                 :    1791920 :                         push_rule(&parser, rule_src_line, rule_id, i + 1); // save this and-rule
    1158                 :    1791842 :                         push_rule_from_arg(&parser, rule_arg[i]); // push child of and-rule
    1159                 :    1791825 :                         goto next_rule;
    1160                 :            :                     }
    1161                 :            :                 }
    1162                 :            : 
    1163         [ -  + ]:     716471 :                 assert(i == n);
    1164                 :            : 
    1165                 :            :                 // matched the rule, so now build the corresponding parse_node
    1166                 :            : 
    1167                 :            :                 #if !MICROPY_ENABLE_DOC_STRING
    1168                 :            :                 // this code discards lonely statements, such as doc strings
    1169   [ +  +  +  + ]:     716471 :                 if (input_kind != MP_PARSE_SINGLE_INPUT && rule_id == RULE_expr_stmt && peek_result(&parser, 0) == MP_PARSE_NODE_NULL) {
    1170                 :      24275 :                     mp_parse_node_t p = peek_result(&parser, 1);
    1171   [ +  +  +  + ]:      24275 :                     if ((MP_PARSE_NODE_IS_LEAF(p) && !MP_PARSE_NODE_IS_ID(p))
    1172   [ +  -  +  +  :      24253 :                         || MP_PARSE_NODE_IS_STRUCT_KIND(p, RULE_const_object)) {
                   -  + ]
    1173                 :         22 :                         pop_result(&parser); // MP_PARSE_NODE_NULL
    1174                 :         22 :                         pop_result(&parser); // const expression (leaf or RULE_const_object)
    1175                 :            :                         // Pushing the "pass" rule here will overwrite any RULE_const_object
    1176                 :            :                         // entry that was on the result stack, allowing the GC to reclaim
    1177                 :            :                         // the memory from the const object when needed.
    1178                 :         22 :                         push_result_rule(&parser, rule_src_line, RULE_pass_stmt, 0);
    1179                 :         22 :                         break;
    1180                 :            :                     }
    1181                 :            :                 }
    1182                 :            :                 #endif
    1183                 :            : 
    1184                 :            :                 // count number of arguments for the parse node
    1185                 :     716449 :                 i = 0;
    1186                 :     716449 :                 size_t num_not_nil = 0;
    1187         [ +  + ]:    2325791 :                 for (size_t x = n; x > 0;) {
    1188                 :    1609343 :                     --x;
    1189         [ +  + ]:    1609343 :                     if ((rule_arg[x] & RULE_ARG_KIND_MASK) == RULE_ARG_TOK) {
    1190                 :     351915 :                         mp_token_kind_t tok_kind = rule_arg[x] & RULE_ARG_ARG_MASK;
    1191         [ +  + ]:     351915 :                         if (tok_kind == MP_TOKEN_NAME) {
    1192                 :            :                             // only tokens which were names are pushed to stack
    1193                 :      28220 :                             i += 1;
    1194                 :      28220 :                             num_not_nil += 1;
    1195                 :            :                         }
    1196                 :            :                     } else {
    1197                 :            :                         // rules are always pushed
    1198         [ +  + ]:    1257428 :                         if (peek_result(&parser, i) != MP_PARSE_NODE_NULL) {
    1199                 :     765014 :                             num_not_nil += 1;
    1200                 :            :                         }
    1201                 :    1257427 :                         i += 1;
    1202                 :            :                     }
    1203                 :            :                 }
    1204                 :            : 
    1205   [ +  +  +  + ]:    1229099 :                 if (num_not_nil == 1 && (rule_act & RULE_ACT_ALLOW_IDENT)) {
    1206                 :            :                     // this rule has only 1 argument and should not be emitted
    1207                 :            :                     mp_parse_node_t pn = MP_PARSE_NODE_NULL;
    1208         [ +  + ]:    1462642 :                     for (size_t x = 0; x < i; ++x) {
    1209                 :     949991 :                         mp_parse_node_t pn2 = pop_result(&parser);
    1210         [ +  + ]:     949991 :                         if (pn2 != MP_PARSE_NODE_NULL) {
    1211                 :     512652 :                             pn = pn2;
    1212                 :            :                         }
    1213                 :            :                     }
    1214                 :     512651 :                     push_result_node(&parser, pn);
    1215                 :            :                 } else {
    1216                 :            :                     // this rule must be emitted
    1217                 :            : 
    1218         [ +  + ]:     203797 :                     if (rule_act & RULE_ACT_ADD_BLANK) {
    1219                 :            :                         // and add an extra blank node at the end (used by the compiler to store data)
    1220                 :       5618 :                         push_result_node(&parser, MP_PARSE_NODE_NULL);
    1221                 :       5618 :                         i += 1;
    1222                 :            :                     }
    1223                 :            : 
    1224                 :     203797 :                     push_result_rule(&parser, rule_src_line, rule_id, i);
    1225                 :            :                 }
    1226                 :            :                 break;
    1227                 :            :             }
    1228                 :            : 
    1229                 :    4745554 :             default: {
    1230         [ -  + ]:    4745554 :                 assert((rule_act & RULE_ACT_KIND_MASK) == RULE_ACT_LIST);
    1231                 :            : 
    1232                 :            :                 // n=2 is: item item*
    1233                 :            :                 // n=1 is: item (sep item)*
    1234                 :            :                 // n=3 is: item (sep item)* [sep]
    1235                 :    4745554 :                 bool had_trailing_sep;
    1236         [ +  + ]:    4745554 :                 if (backtrack) {
    1237                 :    1238078 :                 list_backtrack:
    1238                 :    2021211 :                     had_trailing_sep = false;
    1239         [ +  + ]:    2021211 :                     if (n == 2) {
    1240         [ +  + ]:     269683 :                         if (i == 1) {
    1241                 :            :                             // fail on item, first time round; propagate backtrack
    1242                 :     181967 :                             goto next_rule;
    1243                 :            :                         } else {
    1244                 :            :                             // fail on item, in later rounds; finish with this rule
    1245                 :            :                             backtrack = false;
    1246                 :            :                         }
    1247                 :            :                     } else {
    1248         [ +  + ]:    1751528 :                         if (i == 1) {
    1249                 :            :                             // fail on item, first time round; propagate backtrack
    1250                 :     442735 :                             goto next_rule;
    1251         [ +  + ]:    1308793 :                         } else if ((i & 1) == 1) {
    1252                 :            :                             // fail on item, in later rounds; have eaten tokens so can't backtrack
    1253         [ +  + ]:        369 :                             if (n == 3) {
    1254                 :            :                                 // list allows trailing separator; finish parsing list
    1255                 :            :                                 had_trailing_sep = true;
    1256                 :            :                                 backtrack = false;
    1257                 :            :                             } else {
    1258                 :            :                                 // list doesn't allowing trailing separator; fail
    1259                 :          4 :                                 goto syntax_error;
    1260                 :            :                             }
    1261                 :            :                         } else {
    1262                 :            :                             // fail on separator; finish parsing list
    1263                 :            :                             backtrack = false;
    1264                 :            :                         }
    1265                 :            :                     }
    1266                 :            :                 } else {
    1267                 :    3535087 :                     for (;;) {
    1268                 :    3535087 :                         size_t arg = rule_arg[i & 1 & n];
    1269         [ +  + ]:    3535087 :                         if ((arg & RULE_ARG_KIND_MASK) == RULE_ARG_TOK) {
    1270         [ +  + ]:     810651 :                             if (lex->tok_kind == (arg & RULE_ARG_ARG_MASK)) {
    1271         [ +  + ]:      27518 :                                 if (i & 1 & n) {
    1272                 :            :                                     // separators which are tokens are not pushed to result stack
    1273                 :            :                                 } else {
    1274                 :       2927 :                                     push_result_token(&parser, rule_id);
    1275                 :            :                                 }
    1276                 :      27518 :                                 mp_lexer_to_next(lex);
    1277                 :            :                                 // got element of list, so continue parsing list
    1278                 :      27611 :                                 i += 1;
    1279                 :            :                             } else {
    1280                 :            :                                 // couldn't get element of list
    1281                 :     783133 :                                 i += 1;
    1282                 :     783133 :                                 backtrack = true;
    1283                 :     783133 :                                 goto list_backtrack;
    1284                 :            :                             }
    1285                 :            :                         } else {
    1286         [ -  + ]:    2724436 :                             assert((arg & RULE_ARG_KIND_MASK) == RULE_ARG_RULE);
    1287                 :    2724436 :                             push_rule(&parser, rule_src_line, rule_id, i + 1); // save this list-rule
    1288                 :    2724375 :                             push_rule_from_arg(&parser, arg); // push child of list-rule
    1289                 :    2724374 :                             goto next_rule;
    1290                 :            :                         }
    1291                 :            :                     }
    1292                 :            :                 }
    1293         [ -  + ]:    1396505 :                 assert(i >= 1);
    1294                 :            : 
    1295                 :            :                 // compute number of elements in list, result in i
    1296                 :    1396505 :                 i -= 1;
    1297   [ +  +  +  + ]:    1396505 :                 if ((n & 1) && (rule_arg[1] & RULE_ARG_KIND_MASK) == RULE_ARG_TOK) {
    1298                 :            :                     // don't count separators when they are tokens
    1299                 :     783328 :                     i = (i + 1) / 2;
    1300                 :            :                 }
    1301                 :            : 
    1302         [ +  + ]:    1396505 :                 if (i == 1) {
    1303                 :            :                     // list matched single item
    1304         [ +  + ]:    1354470 :                     if (had_trailing_sep) {
    1305                 :            :                         // if there was a trailing separator, make a list of a single item
    1306                 :        159 :                         push_result_rule(&parser, rule_src_line, rule_id, i);
    1307                 :            :                     } else {
    1308                 :            :                         // just leave single item on stack (ie don't wrap in a list)
    1309                 :            :                     }
    1310                 :            :                 } else {
    1311                 :      42035 :                     push_result_rule(&parser, rule_src_line, rule_id, i);
    1312                 :            :                 }
    1313                 :            :                 break;
    1314                 :            :             }
    1315                 :            :         }
    1316                 :            :     }
    1317                 :            : 
    1318                 :            :     #if MICROPY_COMP_CONST
    1319                 :       3628 :     mp_map_deinit(&parser.consts);
    1320                 :            :     #endif
    1321                 :            : 
    1322                 :            :     // truncate final chunk and link into chain of chunks
    1323         [ +  + ]:       3628 :     if (parser.cur_chunk != NULL) {
    1324                 :       3501 :         (void)m_renew_maybe(byte, parser.cur_chunk,
    1325                 :            :             sizeof(mp_parse_chunk_t) + parser.cur_chunk->alloc,
    1326                 :            :             sizeof(mp_parse_chunk_t) + parser.cur_chunk->union_.used,
    1327                 :            :             false);
    1328                 :       3501 :         parser.cur_chunk->alloc = parser.cur_chunk->union_.used;
    1329                 :       3501 :         parser.cur_chunk->union_.next = parser.tree.chunk;
    1330                 :       3501 :         parser.tree.chunk = parser.cur_chunk;
    1331                 :            :     }
    1332                 :            : 
    1333                 :       3628 :     if (
    1334         [ +  + ]:       3628 :         lex->tok_kind != MP_TOKEN_END // check we are at the end of the token stream
    1335         [ +  + ]:       3582 :         || parser.result_stack_top == 0 // check that we got a node (can fail on empty input)
    1336                 :            :         ) {
    1337                 :         54 :     syntax_error:;
    1338                 :         86 :         mp_obj_t exc;
    1339         [ +  + ]:         86 :         if (lex->tok_kind == MP_TOKEN_INDENT) {
    1340                 :          4 :             exc = mp_obj_new_exception_msg(&mp_type_IndentationError,
    1341                 :          4 :                 MP_ERROR_TEXT("unexpected indent"));
    1342         [ +  + ]:         82 :         } else if (lex->tok_kind == MP_TOKEN_DEDENT_MISMATCH) {
    1343                 :          4 :             exc = mp_obj_new_exception_msg(&mp_type_IndentationError,
    1344                 :          4 :                 MP_ERROR_TEXT("unindent doesn't match any outer indent level"));
    1345                 :            :         #if MICROPY_PY_FSTRINGS
    1346         [ -  + ]:         78 :         } else if (lex->tok_kind == MP_TOKEN_MALFORMED_FSTRING) {
    1347                 :          0 :             exc = mp_obj_new_exception_msg(&mp_type_SyntaxError,
    1348                 :          0 :                 MP_ERROR_TEXT("malformed f-string"));
    1349         [ -  + ]:         78 :         } else if (lex->tok_kind == MP_TOKEN_FSTRING_RAW) {
    1350                 :          0 :             exc = mp_obj_new_exception_msg(&mp_type_SyntaxError,
    1351                 :          0 :                 MP_ERROR_TEXT("raw f-strings are not supported"));
    1352                 :            :         #endif
    1353                 :            :         } else {
    1354                 :         78 :             exc = mp_obj_new_exception_msg(&mp_type_SyntaxError,
    1355                 :         78 :                 MP_ERROR_TEXT("invalid syntax"));
    1356                 :            :         }
    1357                 :            :         // add traceback to give info about file name and location
    1358                 :            :         // we don't have a 'block' name, so just pass the NULL qstr to indicate this
    1359                 :         86 :         mp_obj_exception_add_traceback(exc, lex->source_name, lex->tok_line, MP_QSTRnull);
    1360                 :         86 :         nlr_raise(exc);
    1361                 :            :     }
    1362                 :            : 
    1363                 :            :     // get the root parse node that we created
    1364         [ -  + ]:       3574 :     assert(parser.result_stack_top == 1);
    1365                 :       3574 :     parser.tree.root = parser.result_stack[0];
    1366                 :            : 
    1367                 :            :     // free the memory that we don't need anymore
    1368                 :       3574 :     m_del(rule_stack_t, parser.rule_stack, parser.rule_stack_alloc);
    1369                 :       3574 :     m_del(mp_parse_node_t, parser.result_stack, parser.result_stack_alloc);
    1370                 :            : 
    1371                 :            :     // we also free the lexer on behalf of the caller
    1372                 :       3574 :     mp_lexer_free(lex);
    1373                 :            : 
    1374                 :       3574 :     return parser.tree;
    1375                 :            : }
    1376                 :            : 
    1377                 :       3552 : void mp_parse_tree_clear(mp_parse_tree_t *tree) {
    1378                 :       3552 :     mp_parse_chunk_t *chunk = tree->chunk;
    1379         [ +  + ]:      15750 :     while (chunk != NULL) {
    1380                 :      12198 :         mp_parse_chunk_t *next = chunk->union_.next;
    1381                 :      12198 :         m_del(byte, chunk, sizeof(mp_parse_chunk_t) + chunk->alloc);
    1382                 :      12198 :         chunk = next;
    1383                 :            :     }
    1384                 :       3552 : }
    1385                 :            : 
    1386                 :            : #endif // MICROPY_ENABLE_COMPILER

Generated by: LCOV version 1.15-5-g462f71d