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
get_rule_arg(uint8_t r_id)245 STATIC const uint16_t *get_rule_arg(uint8_t r_id) {
246 size_t off = rule_arg_offset_table[r_id];
247 if (r_id >= FIRST_RULE_WITH_OFFSET_ABOVE_255) {
248 off |= 0x100;
249 }
250 return &rule_arg_combined_table[off];
251 }
252
parser_alloc(parser_t * parser,size_t num_bytes)253 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 mp_parse_chunk_t *chunk = parser->cur_chunk;
257
258 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 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 if (new_data == NULL) {
264 // could not grow existing memory; shrink it to fit previous
265 (void)m_renew_maybe(byte, chunk, sizeof(mp_parse_chunk_t) + chunk->alloc,
266 sizeof(mp_parse_chunk_t) + chunk->union_.used, false);
267 chunk->alloc = chunk->union_.used;
268 chunk->union_.next = parser->tree.chunk;
269 parser->tree.chunk = chunk;
270 chunk = NULL;
271 } else {
272 // could grow existing memory
273 chunk->alloc += num_bytes;
274 }
275 }
276
277 if (chunk == NULL) {
278 // no previous chunk, allocate a new chunk
279 size_t alloc = MICROPY_ALLOC_PARSE_CHUNK_INIT;
280 if (alloc < num_bytes) {
281 alloc = num_bytes;
282 }
283 chunk = (mp_parse_chunk_t *)m_new(byte, sizeof(mp_parse_chunk_t) + alloc);
284 chunk->alloc = alloc;
285 chunk->union_.used = 0;
286 parser->cur_chunk = chunk;
287 }
288
289 byte *ret = chunk->data + chunk->union_.used;
290 chunk->union_.used += num_bytes;
291 return ret;
292 }
293
push_rule(parser_t * parser,size_t src_line,uint8_t rule_id,size_t arg_i)294 STATIC void push_rule(parser_t *parser, size_t src_line, uint8_t rule_id, size_t arg_i) {
295 if (parser->rule_stack_top >= parser->rule_stack_alloc) {
296 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);
297 parser->rule_stack = rs;
298 parser->rule_stack_alloc += MICROPY_ALLOC_PARSE_RULE_INC;
299 }
300 rule_stack_t *rs = &parser->rule_stack[parser->rule_stack_top++];
301 rs->src_line = src_line;
302 rs->rule_id = rule_id;
303 rs->arg_i = arg_i;
304 }
305
push_rule_from_arg(parser_t * parser,size_t arg)306 STATIC void push_rule_from_arg(parser_t *parser, size_t arg) {
307 assert((arg & RULE_ARG_KIND_MASK) == RULE_ARG_RULE || (arg & RULE_ARG_KIND_MASK) == RULE_ARG_OPT_RULE);
308 size_t rule_id = arg & RULE_ARG_ARG_MASK;
309 push_rule(parser, parser->lexer->tok_line, rule_id, 0);
310 }
311
pop_rule(parser_t * parser,size_t * arg_i,size_t * src_line)312 STATIC uint8_t pop_rule(parser_t *parser, size_t *arg_i, size_t *src_line) {
313 parser->rule_stack_top -= 1;
314 uint8_t rule_id = parser->rule_stack[parser->rule_stack_top].rule_id;
315 *arg_i = parser->rule_stack[parser->rule_stack_top].arg_i;
316 *src_line = parser->rule_stack[parser->rule_stack_top].src_line;
317 return rule_id;
318 }
319
mp_parse_node_is_const_false(mp_parse_node_t pn)320 bool mp_parse_node_is_const_false(mp_parse_node_t pn) {
321 return MP_PARSE_NODE_IS_TOKEN_KIND(pn, MP_TOKEN_KW_FALSE)
322 || (MP_PARSE_NODE_IS_SMALL_INT(pn) && MP_PARSE_NODE_LEAF_SMALL_INT(pn) == 0);
323 }
324
mp_parse_node_is_const_true(mp_parse_node_t pn)325 bool mp_parse_node_is_const_true(mp_parse_node_t pn) {
326 return MP_PARSE_NODE_IS_TOKEN_KIND(pn, MP_TOKEN_KW_TRUE)
327 || (MP_PARSE_NODE_IS_SMALL_INT(pn) && MP_PARSE_NODE_LEAF_SMALL_INT(pn) != 0);
328 }
329
mp_parse_node_get_int_maybe(mp_parse_node_t pn,mp_obj_t * o)330 bool mp_parse_node_get_int_maybe(mp_parse_node_t pn, mp_obj_t *o) {
331 if (MP_PARSE_NODE_IS_SMALL_INT(pn)) {
332 *o = MP_OBJ_NEW_SMALL_INT(MP_PARSE_NODE_LEAF_SMALL_INT(pn));
333 return true;
334 } else if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, RULE_const_object)) {
335 mp_parse_node_struct_t *pns = (mp_parse_node_struct_t *)pn;
336 #if MICROPY_OBJ_REPR == MICROPY_OBJ_REPR_D
337 // nodes are 32-bit pointers, but need to extract 64-bit object
338 *o = (uint64_t)pns->nodes[0] | ((uint64_t)pns->nodes[1] << 32);
339 #else
340 *o = (mp_obj_t)pns->nodes[0];
341 #endif
342 return mp_obj_is_int(*o);
343 } else {
344 return false;
345 }
346 }
347
mp_parse_node_extract_list(mp_parse_node_t * pn,size_t pn_kind,mp_parse_node_t ** nodes)348 size_t mp_parse_node_extract_list(mp_parse_node_t *pn, size_t pn_kind, mp_parse_node_t **nodes) {
349 if (MP_PARSE_NODE_IS_NULL(*pn)) {
350 *nodes = NULL;
351 return 0;
352 } else if (MP_PARSE_NODE_IS_LEAF(*pn)) {
353 *nodes = pn;
354 return 1;
355 } else {
356 mp_parse_node_struct_t *pns = (mp_parse_node_struct_t *)(*pn);
357 if (MP_PARSE_NODE_STRUCT_KIND(pns) != pn_kind) {
358 *nodes = pn;
359 return 1;
360 } else {
361 *nodes = pns->nodes;
362 return MP_PARSE_NODE_STRUCT_NUM_NODES(pns);
363 }
364 }
365 }
366
367 #if MICROPY_DEBUG_PRINTERS
mp_parse_node_print(const mp_print_t * print,mp_parse_node_t pn,size_t indent)368 void mp_parse_node_print(const mp_print_t *print, mp_parse_node_t pn, size_t indent) {
369 if (MP_PARSE_NODE_IS_STRUCT(pn)) {
370 mp_printf(print, "[% 4d] ", (int)((mp_parse_node_struct_t *)pn)->source_line);
371 } else {
372 mp_printf(print, " ");
373 }
374 for (size_t i = 0; i < indent; i++) {
375 mp_printf(print, " ");
376 }
377 if (MP_PARSE_NODE_IS_NULL(pn)) {
378 mp_printf(print, "NULL\n");
379 } else if (MP_PARSE_NODE_IS_SMALL_INT(pn)) {
380 mp_int_t arg = MP_PARSE_NODE_LEAF_SMALL_INT(pn);
381 mp_printf(print, "int(" INT_FMT ")\n", arg);
382 } else if (MP_PARSE_NODE_IS_LEAF(pn)) {
383 uintptr_t arg = MP_PARSE_NODE_LEAF_ARG(pn);
384 switch (MP_PARSE_NODE_LEAF_KIND(pn)) {
385 case MP_PARSE_NODE_ID:
386 mp_printf(print, "id(%s)\n", qstr_str(arg));
387 break;
388 case MP_PARSE_NODE_STRING:
389 mp_printf(print, "str(%s)\n", qstr_str(arg));
390 break;
391 case MP_PARSE_NODE_BYTES:
392 mp_printf(print, "bytes(%s)\n", qstr_str(arg));
393 break;
394 default:
395 assert(MP_PARSE_NODE_LEAF_KIND(pn) == MP_PARSE_NODE_TOKEN);
396 mp_printf(print, "tok(%u)\n", (uint)arg);
397 break;
398 }
399 } else {
400 // node must be a mp_parse_node_struct_t
401 mp_parse_node_struct_t *pns = (mp_parse_node_struct_t *)pn;
402 if (MP_PARSE_NODE_STRUCT_KIND(pns) == RULE_const_object) {
403 #if MICROPY_OBJ_REPR == MICROPY_OBJ_REPR_D
404 mp_printf(print, "literal const(%016llx)\n", (uint64_t)pns->nodes[0] | ((uint64_t)pns->nodes[1] << 32));
405 #else
406 mp_printf(print, "literal const(%p)\n", (mp_obj_t)pns->nodes[0]);
407 #endif
408 } else {
409 size_t n = MP_PARSE_NODE_STRUCT_NUM_NODES(pns);
410 #if MICROPY_DEBUG_PARSE_RULE_NAME
411 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);
412 #else
413 mp_printf(print, "rule(%u) (n=%u)\n", (uint)MP_PARSE_NODE_STRUCT_KIND(pns), (uint)n);
414 #endif
415 for (size_t i = 0; i < n; i++) {
416 mp_parse_node_print(print, pns->nodes[i], indent + 2);
417 }
418 }
419 }
420 }
421 #endif // MICROPY_DEBUG_PRINTERS
422
423 /*
424 STATIC void result_stack_show(const mp_print_t *print, parser_t *parser) {
425 mp_printf(print, "result stack, most recent first\n");
426 for (ssize_t i = parser->result_stack_top - 1; i >= 0; i--) {
427 mp_parse_node_print(print, parser->result_stack[i], 0);
428 }
429 }
430 */
431
pop_result(parser_t * parser)432 STATIC mp_parse_node_t pop_result(parser_t *parser) {
433 assert(parser->result_stack_top > 0);
434 return parser->result_stack[--parser->result_stack_top];
435 }
436
peek_result(parser_t * parser,size_t pos)437 STATIC mp_parse_node_t peek_result(parser_t *parser, size_t pos) {
438 assert(parser->result_stack_top > pos);
439 return parser->result_stack[parser->result_stack_top - 1 - pos];
440 }
441
push_result_node(parser_t * parser,mp_parse_node_t pn)442 STATIC void push_result_node(parser_t *parser, mp_parse_node_t pn) {
443 if (parser->result_stack_top >= parser->result_stack_alloc) {
444 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);
445 parser->result_stack = stack;
446 parser->result_stack_alloc += MICROPY_ALLOC_PARSE_RESULT_INC;
447 }
448 parser->result_stack[parser->result_stack_top++] = pn;
449 }
450
make_node_const_object(parser_t * parser,size_t src_line,mp_obj_t obj)451 STATIC mp_parse_node_t make_node_const_object(parser_t *parser, size_t src_line, mp_obj_t obj) {
452 mp_parse_node_struct_t *pn = parser_alloc(parser, sizeof(mp_parse_node_struct_t) + sizeof(mp_obj_t));
453 pn->source_line = src_line;
454 #if MICROPY_OBJ_REPR == MICROPY_OBJ_REPR_D
455 // nodes are 32-bit pointers, but need to store 64-bit object
456 pn->kind_num_nodes = RULE_const_object | (2 << 8);
457 pn->nodes[0] = (uint64_t)obj;
458 pn->nodes[1] = (uint64_t)obj >> 32;
459 #else
460 pn->kind_num_nodes = RULE_const_object | (1 << 8);
461 pn->nodes[0] = (uintptr_t)obj;
462 #endif
463 return (mp_parse_node_t)pn;
464 }
465
mp_parse_node_new_small_int_checked(parser_t * parser,mp_obj_t o_val)466 STATIC mp_parse_node_t mp_parse_node_new_small_int_checked(parser_t *parser, mp_obj_t o_val) {
467 (void)parser;
468 mp_int_t val = MP_OBJ_SMALL_INT_VALUE(o_val);
469 #if MICROPY_OBJ_REPR == MICROPY_OBJ_REPR_D
470 // A parse node is only 32-bits and the small-int value must fit in 31-bits
471 if (((val ^ (val << 1)) & 0xffffffff80000000) != 0) {
472 return make_node_const_object(parser, 0, o_val);
473 }
474 #endif
475 return mp_parse_node_new_small_int(val);
476 }
477
push_result_token(parser_t * parser,uint8_t rule_id)478 STATIC void push_result_token(parser_t *parser, uint8_t rule_id) {
479 mp_parse_node_t pn;
480 mp_lexer_t *lex = parser->lexer;
481 if (lex->tok_kind == MP_TOKEN_NAME) {
482 qstr id = qstr_from_strn(lex->vstr.buf, lex->vstr.len);
483 #if MICROPY_COMP_CONST
484 // if name is a standalone identifier, look it up in the table of dynamic constants
485 mp_map_elem_t *elem;
486 if (rule_id == RULE_atom
487 && (elem = mp_map_lookup(&parser->consts, MP_OBJ_NEW_QSTR(id), MP_MAP_LOOKUP)) != NULL) {
488 if (mp_obj_is_small_int(elem->value)) {
489 pn = mp_parse_node_new_small_int_checked(parser, elem->value);
490 } else {
491 pn = make_node_const_object(parser, lex->tok_line, elem->value);
492 }
493 } else {
494 pn = mp_parse_node_new_leaf(MP_PARSE_NODE_ID, id);
495 }
496 #else
497 (void)rule_id;
498 pn = mp_parse_node_new_leaf(MP_PARSE_NODE_ID, id);
499 #endif
500 } else if (lex->tok_kind == MP_TOKEN_INTEGER) {
501 mp_obj_t o = mp_parse_num_integer(lex->vstr.buf, lex->vstr.len, 0, lex);
502 if (mp_obj_is_small_int(o)) {
503 pn = mp_parse_node_new_small_int_checked(parser, o);
504 } else {
505 pn = make_node_const_object(parser, lex->tok_line, o);
506 }
507 } else if (lex->tok_kind == MP_TOKEN_FLOAT_OR_IMAG) {
508 mp_obj_t o = mp_parse_num_decimal(lex->vstr.buf, lex->vstr.len, true, false, lex);
509 pn = make_node_const_object(parser, lex->tok_line, o);
510 } else if (lex->tok_kind == MP_TOKEN_STRING || lex->tok_kind == MP_TOKEN_BYTES) {
511 // Don't automatically intern all strings/bytes. doc strings (which are usually large)
512 // will be discarded by the compiler, and so we shouldn't intern them.
513 qstr qst = MP_QSTRnull;
514 if (lex->vstr.len <= MICROPY_ALLOC_PARSE_INTERN_STRING_LEN) {
515 // intern short strings
516 qst = qstr_from_strn(lex->vstr.buf, lex->vstr.len);
517 } else {
518 // check if this string is already interned
519 qst = qstr_find_strn(lex->vstr.buf, lex->vstr.len);
520 }
521 if (qst != MP_QSTRnull) {
522 // qstr exists, make a leaf node
523 pn = mp_parse_node_new_leaf(lex->tok_kind == MP_TOKEN_STRING ? MP_PARSE_NODE_STRING : MP_PARSE_NODE_BYTES, qst);
524 } else {
525 // not interned, make a node holding a pointer to the string/bytes object
526 mp_obj_t o = mp_obj_new_str_copy(
527 lex->tok_kind == MP_TOKEN_STRING ? &mp_type_str : &mp_type_bytes,
528 (const byte *)lex->vstr.buf, lex->vstr.len);
529 pn = make_node_const_object(parser, lex->tok_line, o);
530 }
531 } else {
532 pn = mp_parse_node_new_leaf(MP_PARSE_NODE_TOKEN, lex->tok_kind);
533 }
534 push_result_node(parser, pn);
535 }
536
537 #if MICROPY_COMP_MODULE_CONST
538 STATIC const mp_rom_map_elem_t mp_constants_table[] = {
539 #if MICROPY_PY_UERRNO
540 { MP_ROM_QSTR(MP_QSTR_errno), MP_ROM_PTR(&mp_module_uerrno) },
541 #endif
542 #if MICROPY_PY_UCTYPES
543 { MP_ROM_QSTR(MP_QSTR_uctypes), MP_ROM_PTR(&mp_module_uctypes) },
544 #endif
545 // Extra constants as defined by a port
546 MICROPY_PORT_CONSTANTS
547 };
548 STATIC MP_DEFINE_CONST_MAP(mp_constants_map, mp_constants_table);
549 #endif
550
551 STATIC void push_result_rule(parser_t *parser, size_t src_line, uint8_t rule_id, size_t num_args);
552
553 #if MICROPY_COMP_CONST_FOLDING
fold_logical_constants(parser_t * parser,uint8_t rule_id,size_t * num_args)554 STATIC bool fold_logical_constants(parser_t *parser, uint8_t rule_id, size_t *num_args) {
555 if (rule_id == RULE_or_test
556 || rule_id == RULE_and_test) {
557 // folding for binary logical ops: or and
558 size_t copy_to = *num_args;
559 for (size_t i = copy_to; i > 0;) {
560 mp_parse_node_t pn = peek_result(parser, --i);
561 parser->result_stack[parser->result_stack_top - copy_to] = pn;
562 if (i == 0) {
563 // always need to keep the last value
564 break;
565 }
566 if (rule_id == RULE_or_test) {
567 if (mp_parse_node_is_const_true(pn)) {
568 //
569 break;
570 } else if (!mp_parse_node_is_const_false(pn)) {
571 copy_to -= 1;
572 }
573 } else {
574 // RULE_and_test
575 if (mp_parse_node_is_const_false(pn)) {
576 break;
577 } else if (!mp_parse_node_is_const_true(pn)) {
578 copy_to -= 1;
579 }
580 }
581 }
582 copy_to -= 1; // copy_to now contains number of args to pop
583
584 // pop and discard all the short-circuited expressions
585 for (size_t i = 0; i < copy_to; ++i) {
586 pop_result(parser);
587 }
588 *num_args -= copy_to;
589
590 // we did a complete folding if there's only 1 arg left
591 return *num_args == 1;
592
593 } else if (rule_id == RULE_not_test_2) {
594 // folding for unary logical op: not
595 mp_parse_node_t pn = peek_result(parser, 0);
596 if (mp_parse_node_is_const_false(pn)) {
597 pn = mp_parse_node_new_leaf(MP_PARSE_NODE_TOKEN, MP_TOKEN_KW_TRUE);
598 } else if (mp_parse_node_is_const_true(pn)) {
599 pn = mp_parse_node_new_leaf(MP_PARSE_NODE_TOKEN, MP_TOKEN_KW_FALSE);
600 } else {
601 return false;
602 }
603 pop_result(parser);
604 push_result_node(parser, pn);
605 return true;
606 }
607
608 return false;
609 }
610
fold_constants(parser_t * parser,uint8_t rule_id,size_t num_args)611 STATIC bool fold_constants(parser_t *parser, uint8_t rule_id, size_t num_args) {
612 // this code does folding of arbitrary integer expressions, eg 1 + 2 * 3 + 4
613 // it does not do partial folding, eg 1 + 2 + x -> 3 + x
614
615 mp_obj_t arg0;
616 if (rule_id == RULE_expr
617 || rule_id == RULE_xor_expr
618 || rule_id == RULE_and_expr
619 || rule_id == RULE_power) {
620 // folding for binary ops: | ^ & **
621 mp_parse_node_t pn = peek_result(parser, num_args - 1);
622 if (!mp_parse_node_get_int_maybe(pn, &arg0)) {
623 return false;
624 }
625 mp_binary_op_t op;
626 if (rule_id == RULE_expr) {
627 op = MP_BINARY_OP_OR;
628 } else if (rule_id == RULE_xor_expr) {
629 op = MP_BINARY_OP_XOR;
630 } else if (rule_id == RULE_and_expr) {
631 op = MP_BINARY_OP_AND;
632 } else {
633 op = MP_BINARY_OP_POWER;
634 }
635 for (ssize_t i = num_args - 2; i >= 0; --i) {
636 pn = peek_result(parser, i);
637 mp_obj_t arg1;
638 if (!mp_parse_node_get_int_maybe(pn, &arg1)) {
639 return false;
640 }
641 if (op == MP_BINARY_OP_POWER && mp_obj_int_sign(arg1) < 0) {
642 // ** can't have negative rhs
643 return false;
644 }
645 arg0 = mp_binary_op(op, arg0, arg1);
646 }
647 } else if (rule_id == RULE_shift_expr
648 || rule_id == RULE_arith_expr
649 || rule_id == RULE_term) {
650 // folding for binary ops: << >> + - * @ / % //
651 mp_parse_node_t pn = peek_result(parser, num_args - 1);
652 if (!mp_parse_node_get_int_maybe(pn, &arg0)) {
653 return false;
654 }
655 for (ssize_t i = num_args - 2; i >= 1; i -= 2) {
656 pn = peek_result(parser, i - 1);
657 mp_obj_t arg1;
658 if (!mp_parse_node_get_int_maybe(pn, &arg1)) {
659 return false;
660 }
661 mp_token_kind_t tok = MP_PARSE_NODE_LEAF_ARG(peek_result(parser, i));
662 if (tok == MP_TOKEN_OP_AT || tok == MP_TOKEN_OP_SLASH) {
663 // Can't fold @ or /
664 return false;
665 }
666 mp_binary_op_t op = MP_BINARY_OP_LSHIFT + (tok - MP_TOKEN_OP_DBL_LESS);
667 int rhs_sign = mp_obj_int_sign(arg1);
668 if (op <= MP_BINARY_OP_RSHIFT) {
669 // << and >> can't have negative rhs
670 if (rhs_sign < 0) {
671 return false;
672 }
673 } else if (op >= MP_BINARY_OP_FLOOR_DIVIDE) {
674 // % and // can't have zero rhs
675 if (rhs_sign == 0) {
676 return false;
677 }
678 }
679 arg0 = mp_binary_op(op, arg0, arg1);
680 }
681 } else if (rule_id == RULE_factor_2) {
682 // folding for unary ops: + - ~
683 mp_parse_node_t pn = peek_result(parser, 0);
684 if (!mp_parse_node_get_int_maybe(pn, &arg0)) {
685 return false;
686 }
687 mp_token_kind_t tok = MP_PARSE_NODE_LEAF_ARG(peek_result(parser, 1));
688 mp_unary_op_t op;
689 if (tok == MP_TOKEN_OP_TILDE) {
690 op = MP_UNARY_OP_INVERT;
691 } else {
692 assert(tok == MP_TOKEN_OP_PLUS || tok == MP_TOKEN_OP_MINUS); // should be
693 op = MP_UNARY_OP_POSITIVE + (tok - MP_TOKEN_OP_PLUS);
694 }
695 arg0 = mp_unary_op(op, arg0);
696
697 #if MICROPY_COMP_CONST
698 } else if (rule_id == RULE_expr_stmt) {
699 mp_parse_node_t pn1 = peek_result(parser, 0);
700 if (!MP_PARSE_NODE_IS_NULL(pn1)
701 && !(MP_PARSE_NODE_IS_STRUCT_KIND(pn1, RULE_expr_stmt_augassign)
702 || MP_PARSE_NODE_IS_STRUCT_KIND(pn1, RULE_expr_stmt_assign_list))) {
703 // this node is of the form <x> = <y>
704 mp_parse_node_t pn0 = peek_result(parser, 1);
705 if (MP_PARSE_NODE_IS_ID(pn0)
706 && MP_PARSE_NODE_IS_STRUCT_KIND(pn1, RULE_atom_expr_normal)
707 && MP_PARSE_NODE_IS_ID(((mp_parse_node_struct_t *)pn1)->nodes[0])
708 && MP_PARSE_NODE_LEAF_ARG(((mp_parse_node_struct_t *)pn1)->nodes[0]) == MP_QSTR_const
709 && MP_PARSE_NODE_IS_STRUCT_KIND(((mp_parse_node_struct_t *)pn1)->nodes[1], RULE_trailer_paren)
710 ) {
711 // code to assign dynamic constants: id = const(value)
712
713 // get the id
714 qstr id = MP_PARSE_NODE_LEAF_ARG(pn0);
715
716 // get the value
717 mp_parse_node_t pn_value = ((mp_parse_node_struct_t *)((mp_parse_node_struct_t *)pn1)->nodes[1])->nodes[0];
718 mp_obj_t value;
719 if (!mp_parse_node_get_int_maybe(pn_value, &value)) {
720 mp_obj_t exc = mp_obj_new_exception_msg(&mp_type_SyntaxError,
721 MP_ERROR_TEXT("constant must be an integer"));
722 mp_obj_exception_add_traceback(exc, parser->lexer->source_name,
723 ((mp_parse_node_struct_t *)pn1)->source_line, MP_QSTRnull);
724 nlr_raise(exc);
725 }
726
727 // store the value in the table of dynamic constants
728 mp_map_elem_t *elem = mp_map_lookup(&parser->consts, MP_OBJ_NEW_QSTR(id), MP_MAP_LOOKUP_ADD_IF_NOT_FOUND);
729 assert(elem->value == MP_OBJ_NULL);
730 elem->value = value;
731
732 // If the constant starts with an underscore then treat it as a private
733 // variable and don't emit any code to store the value to the id.
734 if (qstr_str(id)[0] == '_') {
735 pop_result(parser); // pop const(value)
736 pop_result(parser); // pop id
737 push_result_rule(parser, 0, RULE_pass_stmt, 0); // replace with "pass"
738 return true;
739 }
740
741 // replace const(value) with value
742 pop_result(parser);
743 push_result_node(parser, pn_value);
744
745 // finished folding this assignment, but we still want it to be part of the tree
746 return false;
747 }
748 }
749 return false;
750 #endif
751
752 #if MICROPY_COMP_MODULE_CONST
753 } else if (rule_id == RULE_atom_expr_normal) {
754 mp_parse_node_t pn0 = peek_result(parser, 1);
755 mp_parse_node_t pn1 = peek_result(parser, 0);
756 if (!(MP_PARSE_NODE_IS_ID(pn0)
757 && MP_PARSE_NODE_IS_STRUCT_KIND(pn1, RULE_trailer_period))) {
758 return false;
759 }
760 // id1.id2
761 // look it up in constant table, see if it can be replaced with an integer
762 mp_parse_node_struct_t *pns1 = (mp_parse_node_struct_t *)pn1;
763 assert(MP_PARSE_NODE_IS_ID(pns1->nodes[0]));
764 qstr q_base = MP_PARSE_NODE_LEAF_ARG(pn0);
765 qstr q_attr = MP_PARSE_NODE_LEAF_ARG(pns1->nodes[0]);
766 mp_map_elem_t *elem = mp_map_lookup((mp_map_t *)&mp_constants_map, MP_OBJ_NEW_QSTR(q_base), MP_MAP_LOOKUP);
767 if (elem == NULL) {
768 return false;
769 }
770 mp_obj_t dest[2];
771 mp_load_method_maybe(elem->value, q_attr, dest);
772 if (!(dest[0] != MP_OBJ_NULL && mp_obj_is_int(dest[0]) && dest[1] == MP_OBJ_NULL)) {
773 return false;
774 }
775 arg0 = dest[0];
776 #endif
777
778 } else {
779 return false;
780 }
781
782 // success folding this rule
783
784 for (size_t i = num_args; i > 0; i--) {
785 pop_result(parser);
786 }
787 if (mp_obj_is_small_int(arg0)) {
788 push_result_node(parser, mp_parse_node_new_small_int_checked(parser, arg0));
789 } else {
790 // TODO reuse memory for parse node struct?
791 push_result_node(parser, make_node_const_object(parser, 0, arg0));
792 }
793
794 return true;
795 }
796 #endif
797
push_result_rule(parser_t * parser,size_t src_line,uint8_t rule_id,size_t num_args)798 STATIC void push_result_rule(parser_t *parser, size_t src_line, uint8_t rule_id, size_t num_args) {
799 // optimise away parenthesis around an expression if possible
800 if (rule_id == RULE_atom_paren) {
801 // there should be just 1 arg for this rule
802 mp_parse_node_t pn = peek_result(parser, 0);
803 if (MP_PARSE_NODE_IS_NULL(pn)) {
804 // need to keep parenthesis for ()
805 } else if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, RULE_testlist_comp)) {
806 // need to keep parenthesis for (a, b, ...)
807 } else {
808 // parenthesis around a single expression, so it's just the expression
809 return;
810 }
811 }
812
813 #if MICROPY_COMP_CONST_FOLDING
814 if (fold_logical_constants(parser, rule_id, &num_args)) {
815 // we folded this rule so return straight away
816 return;
817 }
818 if (fold_constants(parser, rule_id, num_args)) {
819 // we folded this rule so return straight away
820 return;
821 }
822 #endif
823
824 mp_parse_node_struct_t *pn = parser_alloc(parser, sizeof(mp_parse_node_struct_t) + sizeof(mp_parse_node_t) * num_args);
825 pn->source_line = src_line;
826 pn->kind_num_nodes = (rule_id & 0xff) | (num_args << 8);
827 for (size_t i = num_args; i > 0; i--) {
828 pn->nodes[i - 1] = pop_result(parser);
829 }
830 push_result_node(parser, (mp_parse_node_t)pn);
831 }
832
mp_parse(mp_lexer_t * lex,mp_parse_input_kind_t input_kind)833 mp_parse_tree_t mp_parse(mp_lexer_t *lex, mp_parse_input_kind_t input_kind) {
834
835 // initialise parser and allocate memory for its stacks
836
837 parser_t parser;
838
839 parser.rule_stack_alloc = MICROPY_ALLOC_PARSE_RULE_INIT;
840 parser.rule_stack_top = 0;
841 parser.rule_stack = m_new(rule_stack_t, parser.rule_stack_alloc);
842
843 parser.result_stack_alloc = MICROPY_ALLOC_PARSE_RESULT_INIT;
844 parser.result_stack_top = 0;
845 parser.result_stack = m_new(mp_parse_node_t, parser.result_stack_alloc);
846
847 parser.lexer = lex;
848
849 parser.tree.chunk = NULL;
850 parser.cur_chunk = NULL;
851
852 #if MICROPY_COMP_CONST
853 mp_map_init(&parser.consts, 0);
854 #endif
855
856 // work out the top-level rule to use, and push it on the stack
857 size_t top_level_rule;
858 switch (input_kind) {
859 case MP_PARSE_SINGLE_INPUT:
860 top_level_rule = RULE_single_input;
861 break;
862 case MP_PARSE_EVAL_INPUT:
863 top_level_rule = RULE_eval_input;
864 break;
865 default:
866 top_level_rule = RULE_file_input;
867 }
868 push_rule(&parser, lex->tok_line, top_level_rule, 0);
869
870 // parse!
871
872 bool backtrack = false;
873
874 for (;;) {
875 next_rule:
876 if (parser.rule_stack_top == 0) {
877 break;
878 }
879
880 // Pop the next rule to process it
881 size_t i; // state for the current rule
882 size_t rule_src_line; // source line for the first token matched by the current rule
883 uint8_t rule_id = pop_rule(&parser, &i, &rule_src_line);
884 uint8_t rule_act = rule_act_table[rule_id];
885 const uint16_t *rule_arg = get_rule_arg(rule_id);
886 size_t n = rule_act & RULE_ACT_ARG_MASK;
887
888 #if 0
889 // debugging
890 printf("depth=" UINT_FMT " ", parser.rule_stack_top);
891 for (int j = 0; j < parser.rule_stack_top; ++j) {
892 printf(" ");
893 }
894 printf("%s n=" UINT_FMT " i=" UINT_FMT " bt=%d\n", rule_name_table[rule_id], n, i, backtrack);
895 #endif
896
897 switch (rule_act & RULE_ACT_KIND_MASK) {
898 case RULE_ACT_OR:
899 if (i > 0 && !backtrack) {
900 goto next_rule;
901 } else {
902 backtrack = false;
903 }
904 for (; i < n; ++i) {
905 uint16_t kind = rule_arg[i] & RULE_ARG_KIND_MASK;
906 if (kind == RULE_ARG_TOK) {
907 if (lex->tok_kind == (rule_arg[i] & RULE_ARG_ARG_MASK)) {
908 push_result_token(&parser, rule_id);
909 mp_lexer_to_next(lex);
910 goto next_rule;
911 }
912 } else {
913 assert(kind == RULE_ARG_RULE);
914 if (i + 1 < n) {
915 push_rule(&parser, rule_src_line, rule_id, i + 1); // save this or-rule
916 }
917 push_rule_from_arg(&parser, rule_arg[i]); // push child of or-rule
918 goto next_rule;
919 }
920 }
921 backtrack = true;
922 break;
923
924 case RULE_ACT_AND: {
925
926 // failed, backtrack if we can, else syntax error
927 if (backtrack) {
928 assert(i > 0);
929 if ((rule_arg[i - 1] & RULE_ARG_KIND_MASK) == RULE_ARG_OPT_RULE) {
930 // an optional rule that failed, so continue with next arg
931 push_result_node(&parser, MP_PARSE_NODE_NULL);
932 backtrack = false;
933 } else {
934 // a mandatory rule that failed, so propagate backtrack
935 if (i > 1) {
936 // already eaten tokens so can't backtrack
937 goto syntax_error;
938 } else {
939 goto next_rule;
940 }
941 }
942 }
943
944 // progress through the rule
945 for (; i < n; ++i) {
946 if ((rule_arg[i] & RULE_ARG_KIND_MASK) == RULE_ARG_TOK) {
947 // need to match a token
948 mp_token_kind_t tok_kind = rule_arg[i] & RULE_ARG_ARG_MASK;
949 if (lex->tok_kind == tok_kind) {
950 // matched token
951 if (tok_kind == MP_TOKEN_NAME) {
952 push_result_token(&parser, rule_id);
953 }
954 mp_lexer_to_next(lex);
955 } else {
956 // failed to match token
957 if (i > 0) {
958 // already eaten tokens so can't backtrack
959 goto syntax_error;
960 } else {
961 // this rule failed, so backtrack
962 backtrack = true;
963 goto next_rule;
964 }
965 }
966 } else {
967 push_rule(&parser, rule_src_line, rule_id, i + 1); // save this and-rule
968 push_rule_from_arg(&parser, rule_arg[i]); // push child of and-rule
969 goto next_rule;
970 }
971 }
972
973 assert(i == n);
974
975 // matched the rule, so now build the corresponding parse_node
976
977 #if !MICROPY_ENABLE_DOC_STRING
978 // this code discards lonely statements, such as doc strings
979 if (input_kind != MP_PARSE_SINGLE_INPUT && rule_id == RULE_expr_stmt && peek_result(&parser, 0) == MP_PARSE_NODE_NULL) {
980 mp_parse_node_t p = peek_result(&parser, 1);
981 if ((MP_PARSE_NODE_IS_LEAF(p) && !MP_PARSE_NODE_IS_ID(p))
982 || MP_PARSE_NODE_IS_STRUCT_KIND(p, RULE_const_object)) {
983 pop_result(&parser); // MP_PARSE_NODE_NULL
984 pop_result(&parser); // const expression (leaf or RULE_const_object)
985 // Pushing the "pass" rule here will overwrite any RULE_const_object
986 // entry that was on the result stack, allowing the GC to reclaim
987 // the memory from the const object when needed.
988 push_result_rule(&parser, rule_src_line, RULE_pass_stmt, 0);
989 break;
990 }
991 }
992 #endif
993
994 // count number of arguments for the parse node
995 i = 0;
996 size_t num_not_nil = 0;
997 for (size_t x = n; x > 0;) {
998 --x;
999 if ((rule_arg[x] & RULE_ARG_KIND_MASK) == RULE_ARG_TOK) {
1000 mp_token_kind_t tok_kind = rule_arg[x] & RULE_ARG_ARG_MASK;
1001 if (tok_kind == MP_TOKEN_NAME) {
1002 // only tokens which were names are pushed to stack
1003 i += 1;
1004 num_not_nil += 1;
1005 }
1006 } else {
1007 // rules are always pushed
1008 if (peek_result(&parser, i) != MP_PARSE_NODE_NULL) {
1009 num_not_nil += 1;
1010 }
1011 i += 1;
1012 }
1013 }
1014
1015 if (num_not_nil == 1 && (rule_act & RULE_ACT_ALLOW_IDENT)) {
1016 // this rule has only 1 argument and should not be emitted
1017 mp_parse_node_t pn = MP_PARSE_NODE_NULL;
1018 for (size_t x = 0; x < i; ++x) {
1019 mp_parse_node_t pn2 = pop_result(&parser);
1020 if (pn2 != MP_PARSE_NODE_NULL) {
1021 pn = pn2;
1022 }
1023 }
1024 push_result_node(&parser, pn);
1025 } else {
1026 // this rule must be emitted
1027
1028 if (rule_act & RULE_ACT_ADD_BLANK) {
1029 // and add an extra blank node at the end (used by the compiler to store data)
1030 push_result_node(&parser, MP_PARSE_NODE_NULL);
1031 i += 1;
1032 }
1033
1034 push_result_rule(&parser, rule_src_line, rule_id, i);
1035 }
1036 break;
1037 }
1038
1039 default: {
1040 assert((rule_act & RULE_ACT_KIND_MASK) == RULE_ACT_LIST);
1041
1042 // n=2 is: item item*
1043 // n=1 is: item (sep item)*
1044 // n=3 is: item (sep item)* [sep]
1045 bool had_trailing_sep;
1046 if (backtrack) {
1047 list_backtrack:
1048 had_trailing_sep = false;
1049 if (n == 2) {
1050 if (i == 1) {
1051 // fail on item, first time round; propagate backtrack
1052 goto next_rule;
1053 } else {
1054 // fail on item, in later rounds; finish with this rule
1055 backtrack = false;
1056 }
1057 } else {
1058 if (i == 1) {
1059 // fail on item, first time round; propagate backtrack
1060 goto next_rule;
1061 } else if ((i & 1) == 1) {
1062 // fail on item, in later rounds; have eaten tokens so can't backtrack
1063 if (n == 3) {
1064 // list allows trailing separator; finish parsing list
1065 had_trailing_sep = true;
1066 backtrack = false;
1067 } else {
1068 // list doesn't allowing trailing separator; fail
1069 goto syntax_error;
1070 }
1071 } else {
1072 // fail on separator; finish parsing list
1073 backtrack = false;
1074 }
1075 }
1076 } else {
1077 for (;;) {
1078 size_t arg = rule_arg[i & 1 & n];
1079 if ((arg & RULE_ARG_KIND_MASK) == RULE_ARG_TOK) {
1080 if (lex->tok_kind == (arg & RULE_ARG_ARG_MASK)) {
1081 if (i & 1 & n) {
1082 // separators which are tokens are not pushed to result stack
1083 } else {
1084 push_result_token(&parser, rule_id);
1085 }
1086 mp_lexer_to_next(lex);
1087 // got element of list, so continue parsing list
1088 i += 1;
1089 } else {
1090 // couldn't get element of list
1091 i += 1;
1092 backtrack = true;
1093 goto list_backtrack;
1094 }
1095 } else {
1096 assert((arg & RULE_ARG_KIND_MASK) == RULE_ARG_RULE);
1097 push_rule(&parser, rule_src_line, rule_id, i + 1); // save this list-rule
1098 push_rule_from_arg(&parser, arg); // push child of list-rule
1099 goto next_rule;
1100 }
1101 }
1102 }
1103 assert(i >= 1);
1104
1105 // compute number of elements in list, result in i
1106 i -= 1;
1107 if ((n & 1) && (rule_arg[1] & RULE_ARG_KIND_MASK) == RULE_ARG_TOK) {
1108 // don't count separators when they are tokens
1109 i = (i + 1) / 2;
1110 }
1111
1112 if (i == 1) {
1113 // list matched single item
1114 if (had_trailing_sep) {
1115 // if there was a trailing separator, make a list of a single item
1116 push_result_rule(&parser, rule_src_line, rule_id, i);
1117 } else {
1118 // just leave single item on stack (ie don't wrap in a list)
1119 }
1120 } else {
1121 push_result_rule(&parser, rule_src_line, rule_id, i);
1122 }
1123 break;
1124 }
1125 }
1126 }
1127
1128 #if MICROPY_COMP_CONST
1129 mp_map_deinit(&parser.consts);
1130 #endif
1131
1132 // truncate final chunk and link into chain of chunks
1133 if (parser.cur_chunk != NULL) {
1134 (void)m_renew_maybe(byte, parser.cur_chunk,
1135 sizeof(mp_parse_chunk_t) + parser.cur_chunk->alloc,
1136 sizeof(mp_parse_chunk_t) + parser.cur_chunk->union_.used,
1137 false);
1138 parser.cur_chunk->alloc = parser.cur_chunk->union_.used;
1139 parser.cur_chunk->union_.next = parser.tree.chunk;
1140 parser.tree.chunk = parser.cur_chunk;
1141 }
1142
1143 if (
1144 lex->tok_kind != MP_TOKEN_END // check we are at the end of the token stream
1145 || parser.result_stack_top == 0 // check that we got a node (can fail on empty input)
1146 ) {
1147 syntax_error:;
1148 mp_obj_t exc;
1149 if (lex->tok_kind == MP_TOKEN_INDENT) {
1150 exc = mp_obj_new_exception_msg(&mp_type_IndentationError,
1151 MP_ERROR_TEXT("unexpected indent"));
1152 } else if (lex->tok_kind == MP_TOKEN_DEDENT_MISMATCH) {
1153 exc = mp_obj_new_exception_msg(&mp_type_IndentationError,
1154 MP_ERROR_TEXT("unindent doesn't match any outer indent level"));
1155 #if MICROPY_PY_FSTRINGS
1156 } else if (lex->tok_kind == MP_TOKEN_MALFORMED_FSTRING) {
1157 exc = mp_obj_new_exception_msg(&mp_type_SyntaxError,
1158 MP_ERROR_TEXT("malformed f-string"));
1159 } else if (lex->tok_kind == MP_TOKEN_FSTRING_RAW) {
1160 exc = mp_obj_new_exception_msg(&mp_type_SyntaxError,
1161 MP_ERROR_TEXT("raw f-strings are not supported"));
1162 #endif
1163 } else {
1164 exc = mp_obj_new_exception_msg(&mp_type_SyntaxError,
1165 MP_ERROR_TEXT("invalid syntax"));
1166 }
1167 // add traceback to give info about file name and location
1168 // we don't have a 'block' name, so just pass the NULL qstr to indicate this
1169 mp_obj_exception_add_traceback(exc, lex->source_name, lex->tok_line, MP_QSTRnull);
1170 nlr_raise(exc);
1171 }
1172
1173 // get the root parse node that we created
1174 assert(parser.result_stack_top == 1);
1175 parser.tree.root = parser.result_stack[0];
1176
1177 // free the memory that we don't need anymore
1178 m_del(rule_stack_t, parser.rule_stack, parser.rule_stack_alloc);
1179 m_del(mp_parse_node_t, parser.result_stack, parser.result_stack_alloc);
1180
1181 // we also free the lexer on behalf of the caller
1182 mp_lexer_free(lex);
1183
1184 return parser.tree;
1185 }
1186
mp_parse_tree_clear(mp_parse_tree_t * tree)1187 void mp_parse_tree_clear(mp_parse_tree_t *tree) {
1188 mp_parse_chunk_t *chunk = tree->chunk;
1189 while (chunk != NULL) {
1190 mp_parse_chunk_t *next = chunk->union_.next;
1191 m_del(byte, chunk, sizeof(mp_parse_chunk_t) + chunk->alloc);
1192 chunk = next;
1193 }
1194 }
1195
1196 #endif // MICROPY_ENABLE_COMPILER
1197