parse.c 42.4 KB
Newer Older
1
2
3
4
5
/*
 * This file is part of the Micro Python project, http://micropython.org/
 *
 * The MIT License (MIT)
 *
6
 * Copyright (c) 2013-2015 Damien P. George
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

xbe's avatar
xbe committed
27
#include <stdbool.h>
Damien's avatar
Damien committed
28
29
#include <stdint.h>
#include <stdio.h>
30
#include <unistd.h> // for ssize_t
Damien's avatar
Damien committed
31
#include <assert.h>
32
#include <string.h>
Damien's avatar
Damien committed
33

34
#include "py/nlr.h"
35
36
37
#include "py/lexer.h"
#include "py/parse.h"
#include "py/parsenum.h"
38
#include "py/runtime0.h"
39
#include "py/runtime.h"
40
#include "py/objint.h"
41
#include "py/builtin.h"
Damien's avatar
Damien committed
42

43
44
#if MICROPY_ENABLE_COMPILER

Damien's avatar
Damien committed
45
#define RULE_ACT_ARG_MASK       (0x0f)
46
47
48
#define RULE_ACT_KIND_MASK      (0x30)
#define RULE_ACT_ALLOW_IDENT    (0x40)
#define RULE_ACT_ADD_BLANK      (0x80)
Damien's avatar
Damien committed
49
50
51
52
53
54
55
56
#define RULE_ACT_OR             (0x10)
#define RULE_ACT_AND            (0x20)
#define RULE_ACT_LIST           (0x30)

#define RULE_ARG_KIND_MASK      (0xf000)
#define RULE_ARG_ARG_MASK       (0x0fff)
#define RULE_ARG_TOK            (0x1000)
#define RULE_ARG_RULE           (0x2000)
57
#define RULE_ARG_OPT_RULE       (0x3000)
Damien's avatar
Damien committed
58
59
60
61
62
63
64
65
66
67
68
69
70
71

// (un)comment to use rule names; for debugging
//#define USE_RULE_NAME (1)

typedef struct _rule_t {
    byte rule_id;
    byte act;
#ifdef USE_RULE_NAME
    const char *rule_name;
#endif
    uint16_t arg[];
} rule_t;

enum {
72
#define DEF_RULE(rule, comp, kind, ...) RULE_##rule,
73
#include "py/grammar.h"
Damien's avatar
Damien committed
74
75
#undef DEF_RULE
    RULE_maximum_number_of,
76
    RULE_string, // special node for non-interned string
77
    RULE_bytes, // special node for non-interned bytes
78
    RULE_const_object, // special node for a constant, generic Python object
Damien's avatar
Damien committed
79
80
81
82
};

#define or(n)                   (RULE_ACT_OR | n)
#define and(n)                  (RULE_ACT_AND | n)
83
84
#define and_ident(n)            (RULE_ACT_AND | n | RULE_ACT_ALLOW_IDENT)
#define and_blank(n)            (RULE_ACT_AND | n | RULE_ACT_ADD_BLANK)
Damien's avatar
Damien committed
85
86
87
#define one_or_more             (RULE_ACT_LIST | 2)
#define list                    (RULE_ACT_LIST | 1)
#define list_with_end           (RULE_ACT_LIST | 3)
88
#define tok(t)                  (RULE_ARG_TOK | MP_TOKEN_##t)
Damien's avatar
Damien committed
89
90
91
#define rule(r)                 (RULE_ARG_RULE | RULE_##r)
#define opt_rule(r)             (RULE_ARG_OPT_RULE | RULE_##r)
#ifdef USE_RULE_NAME
92
#define DEF_RULE(rule, comp, kind, ...) static const rule_t rule_##rule = { RULE_##rule, kind, #rule, { __VA_ARGS__ } };
Damien's avatar
Damien committed
93
#else
94
#define DEF_RULE(rule, comp, kind, ...) static const rule_t rule_##rule = { RULE_##rule, kind, { __VA_ARGS__ } };
Damien's avatar
Damien committed
95
#endif
96
#include "py/grammar.h"
Damien's avatar
Damien committed
97
98
99
100
101
102
103
104
105
106
#undef or
#undef and
#undef list
#undef list_with_end
#undef tok
#undef rule
#undef opt_rule
#undef one_or_more
#undef DEF_RULE

107
STATIC const rule_t *const rules[] = {
108
#define DEF_RULE(rule, comp, kind, ...) &rule_##rule,
109
#include "py/grammar.h"
Damien's avatar
Damien committed
110
111
112
113
#undef DEF_RULE
};

typedef struct _rule_stack_t {
114
115
116
    size_t src_line : 8 * sizeof(size_t) - 8; // maximum bits storing source line number
    size_t rule_id : 8; // this must be large enough to fit largest rule number
    size_t arg_i; // this dictates the maximum nodes in a "list" of things
Damien's avatar
Damien committed
117
118
} rule_stack_t;

119
typedef struct _mp_parse_chunk_t {
120
    size_t alloc;
121
    union {
122
        size_t used;
123
124
125
126
127
        struct _mp_parse_chunk_t *next;
    } union_;
    byte data[];
} mp_parse_chunk_t;

128
129
130
131
132
133
typedef enum {
    PARSE_ERROR_NONE = 0,
    PARSE_ERROR_MEMORY,
    PARSE_ERROR_CONST,
} parse_error_t;

Damien's avatar
Damien committed
134
typedef struct _parser_t {
135
    parse_error_t parse_error;
136

137
138
    size_t rule_stack_alloc;
    size_t rule_stack_top;
Damien's avatar
Damien committed
139
140
    rule_stack_t *rule_stack;

141
142
    size_t result_stack_alloc;
    size_t result_stack_top;
143
    mp_parse_node_t *result_stack;
144
145

    mp_lexer_t *lexer;
146
147
148

    mp_parse_tree_t tree;
    mp_parse_chunk_t *cur_chunk;
Damien's avatar
Damien committed
149

150
151
152
153
    #if MICROPY_COMP_CONST
    mp_map_t consts;
    #endif
} parser_t;
154

155
156
157
158
159
160
161
162
163
164
165
166
STATIC void *parser_alloc(parser_t *parser, size_t num_bytes) {
    // use a custom memory allocator to store parse nodes sequentially in large chunks

    mp_parse_chunk_t *chunk = parser->cur_chunk;

    if (chunk != NULL && chunk->union_.used + num_bytes > chunk->alloc) {
        // not enough room at end of previously allocated chunk so try to grow
        mp_parse_chunk_t *new_data = (mp_parse_chunk_t*)m_renew_maybe(byte, chunk,
            sizeof(mp_parse_chunk_t) + chunk->alloc,
            sizeof(mp_parse_chunk_t) + chunk->alloc + num_bytes, false);
        if (new_data == NULL) {
            // could not grow existing memory; shrink it to fit previous
167
168
            (void)m_renew_maybe(byte, chunk, sizeof(mp_parse_chunk_t) + chunk->alloc,
                sizeof(mp_parse_chunk_t) + chunk->union_.used, false);
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
            chunk->alloc = chunk->union_.used;
            chunk->union_.next = parser->tree.chunk;
            parser->tree.chunk = chunk;
            chunk = NULL;
        } else {
            // could grow existing memory
            chunk->alloc += num_bytes;
        }
    }

    if (chunk == NULL) {
        // no previous chunk, allocate a new chunk
        size_t alloc = MICROPY_ALLOC_PARSE_CHUNK_INIT;
        if (alloc < num_bytes) {
            alloc = num_bytes;
        }
        chunk = (mp_parse_chunk_t*)m_new(byte, sizeof(mp_parse_chunk_t) + alloc);
        chunk->alloc = alloc;
        chunk->union_.used = 0;
        parser->cur_chunk = chunk;
    }

    byte *ret = chunk->data + chunk->union_.used;
    chunk->union_.used += num_bytes;
    return ret;
}

196
STATIC void push_rule(parser_t *parser, size_t src_line, const rule_t *rule, size_t arg_i) {
197
    if (parser->parse_error) {
198
199
        return;
    }
Damien's avatar
Damien committed
200
    if (parser->rule_stack_top >= parser->rule_stack_alloc) {
201
        rule_stack_t *rs = m_renew_maybe(rule_stack_t, parser->rule_stack, parser->rule_stack_alloc, parser->rule_stack_alloc + MICROPY_ALLOC_PARSE_RULE_INC, true);
202
        if (rs == NULL) {
203
            parser->parse_error = PARSE_ERROR_MEMORY;
204
205
206
            return;
        }
        parser->rule_stack = rs;
207
        parser->rule_stack_alloc += MICROPY_ALLOC_PARSE_RULE_INC;
Damien's avatar
Damien committed
208
    }
209
210
211
212
    rule_stack_t *rs = &parser->rule_stack[parser->rule_stack_top++];
    rs->src_line = src_line;
    rs->rule_id = rule->rule_id;
    rs->arg_i = arg_i;
Damien's avatar
Damien committed
213
214
}

215
STATIC void push_rule_from_arg(parser_t *parser, size_t arg) {
Damien's avatar
Damien committed
216
    assert((arg & RULE_ARG_KIND_MASK) == RULE_ARG_RULE || (arg & RULE_ARG_KIND_MASK) == RULE_ARG_OPT_RULE);
217
    size_t rule_id = arg & RULE_ARG_ARG_MASK;
Damien's avatar
Damien committed
218
    assert(rule_id < RULE_maximum_number_of);
219
    push_rule(parser, parser->lexer->tok_line, rules[rule_id], 0);
Damien's avatar
Damien committed
220
221
}

222
STATIC void pop_rule(parser_t *parser, const rule_t **rule, size_t *arg_i, size_t *src_line) {
223
    assert(!parser->parse_error);
Damien's avatar
Damien committed
224
225
226
    parser->rule_stack_top -= 1;
    *rule = rules[parser->rule_stack[parser->rule_stack_top].rule_id];
    *arg_i = parser->rule_stack[parser->rule_stack_top].arg_i;
227
    *src_line = parser->rule_stack[parser->rule_stack_top].src_line;
Damien's avatar
Damien committed
228
229
}

230
231
232
233
234
235
236
237
238
239
bool mp_parse_node_is_const_false(mp_parse_node_t pn) {
    return MP_PARSE_NODE_IS_TOKEN_KIND(pn, MP_TOKEN_KW_FALSE)
        || (MP_PARSE_NODE_IS_SMALL_INT(pn) && MP_PARSE_NODE_LEAF_SMALL_INT(pn) == 0);
}

bool mp_parse_node_is_const_true(mp_parse_node_t pn) {
    return MP_PARSE_NODE_IS_TOKEN_KIND(pn, MP_TOKEN_KW_TRUE)
        || (MP_PARSE_NODE_IS_SMALL_INT(pn) && MP_PARSE_NODE_LEAF_SMALL_INT(pn) != 0);
}

240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
bool mp_parse_node_get_int_maybe(mp_parse_node_t pn, mp_obj_t *o) {
    if (MP_PARSE_NODE_IS_SMALL_INT(pn)) {
        *o = MP_OBJ_NEW_SMALL_INT(MP_PARSE_NODE_LEAF_SMALL_INT(pn));
        return true;
    } else if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, RULE_const_object)) {
        mp_parse_node_struct_t *pns = (mp_parse_node_struct_t*)pn;
        #if MICROPY_OBJ_REPR == MICROPY_OBJ_REPR_D
        // nodes are 32-bit pointers, but need to extract 64-bit object
        *o = (uint64_t)pns->nodes[0] | ((uint64_t)pns->nodes[1] << 32);
        #else
        *o = (mp_obj_t)pns->nodes[0];
        #endif
        return MP_OBJ_IS_INT(*o);
    } else {
        return false;
    }
}

258
int mp_parse_node_extract_list(mp_parse_node_t *pn, size_t pn_kind, mp_parse_node_t **nodes) {
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
    if (MP_PARSE_NODE_IS_NULL(*pn)) {
        *nodes = NULL;
        return 0;
    } else if (MP_PARSE_NODE_IS_LEAF(*pn)) {
        *nodes = pn;
        return 1;
    } else {
        mp_parse_node_struct_t *pns = (mp_parse_node_struct_t*)(*pn);
        if (MP_PARSE_NODE_STRUCT_KIND(pns) != pn_kind) {
            *nodes = pn;
            return 1;
        } else {
            *nodes = pns->nodes;
            return MP_PARSE_NODE_STRUCT_NUM_NODES(pns);
        }
    }
}

277
#if MICROPY_DEBUG_PRINTERS
278
void mp_parse_node_print(mp_parse_node_t pn, size_t indent) {
279
280
281
282
283
    if (MP_PARSE_NODE_IS_STRUCT(pn)) {
        printf("[% 4d] ", (int)((mp_parse_node_struct_t*)pn)->source_line);
    } else {
        printf("       ");
    }
284
    for (size_t i = 0; i < indent; i++) {
Damien's avatar
Damien committed
285
286
        printf(" ");
    }
287
    if (MP_PARSE_NODE_IS_NULL(pn)) {
Damien's avatar
Damien committed
288
        printf("NULL\n");
289
    } else if (MP_PARSE_NODE_IS_SMALL_INT(pn)) {
290
        mp_int_t arg = MP_PARSE_NODE_LEAF_SMALL_INT(pn);
291
        printf("int(" INT_FMT ")\n", arg);
292
    } else if (MP_PARSE_NODE_IS_LEAF(pn)) {
293
        uintptr_t arg = MP_PARSE_NODE_LEAF_ARG(pn);
294
295
296
297
        switch (MP_PARSE_NODE_LEAF_KIND(pn)) {
            case MP_PARSE_NODE_ID: printf("id(%s)\n", qstr_str(arg)); break;
            case MP_PARSE_NODE_STRING: printf("str(%s)\n", qstr_str(arg)); break;
            case MP_PARSE_NODE_BYTES: printf("bytes(%s)\n", qstr_str(arg)); break;
298
            case MP_PARSE_NODE_TOKEN: printf("tok(%u)\n", (uint)arg); break;
Damien's avatar
Damien committed
299
300
301
            default: assert(0);
        }
    } else {
302
        // node must be a mp_parse_node_struct_t
303
        mp_parse_node_struct_t *pns = (mp_parse_node_struct_t*)pn;
304
305
        if (MP_PARSE_NODE_STRUCT_KIND(pns) == RULE_string) {
            printf("literal str(%.*s)\n", (int)pns->nodes[1], (char*)pns->nodes[0]);
306
307
        } else if (MP_PARSE_NODE_STRUCT_KIND(pns) == RULE_bytes) {
            printf("literal bytes(%.*s)\n", (int)pns->nodes[1], (char*)pns->nodes[0]);
308
        } else if (MP_PARSE_NODE_STRUCT_KIND(pns) == RULE_const_object) {
309
310
311
            #if MICROPY_OBJ_REPR == MICROPY_OBJ_REPR_D
            printf("literal const(%016llx)\n", (uint64_t)pns->nodes[0] | ((uint64_t)pns->nodes[1] << 32));
            #else
312
            printf("literal const(%p)\n", (mp_obj_t)pns->nodes[0]);
313
            #endif
314
        } else {
315
            size_t n = MP_PARSE_NODE_STRUCT_NUM_NODES(pns);
Damien's avatar
Damien committed
316
#ifdef USE_RULE_NAME
317
            printf("%s(%u) (n=%u)\n", rules[MP_PARSE_NODE_STRUCT_KIND(pns)]->rule_name, (uint)MP_PARSE_NODE_STRUCT_KIND(pns), (uint)n);
Damien's avatar
Damien committed
318
#else
319
            printf("rule(%u) (n=%u)\n", (uint)MP_PARSE_NODE_STRUCT_KIND(pns), (uint)n);
Damien's avatar
Damien committed
320
#endif
321
            for (size_t i = 0; i < n; i++) {
322
323
                mp_parse_node_print(pns->nodes[i], indent + 2);
            }
Damien's avatar
Damien committed
324
325
326
        }
    }
}
327
#endif // MICROPY_DEBUG_PRINTERS
Damien's avatar
Damien committed
328
329

/*
330
STATIC void result_stack_show(parser_t *parser) {
Damien's avatar
Damien committed
331
    printf("result stack, most recent first\n");
332
    for (ssize_t i = parser->result_stack_top - 1; i >= 0; i--) {
333
        mp_parse_node_print(parser->result_stack[i], 0);
Damien's avatar
Damien committed
334
335
336
337
    }
}
*/

338
STATIC mp_parse_node_t pop_result(parser_t *parser) {
339
    if (parser->parse_error) {
340
341
        return MP_PARSE_NODE_NULL;
    }
Damien's avatar
Damien committed
342
343
344
345
    assert(parser->result_stack_top > 0);
    return parser->result_stack[--parser->result_stack_top];
}

346
STATIC mp_parse_node_t peek_result(parser_t *parser, size_t pos) {
347
    if (parser->parse_error) {
348
349
        return MP_PARSE_NODE_NULL;
    }
Damien's avatar
Damien committed
350
351
352
353
    assert(parser->result_stack_top > pos);
    return parser->result_stack[parser->result_stack_top - 1 - pos];
}

354
STATIC void push_result_node(parser_t *parser, mp_parse_node_t pn) {
355
    if (parser->parse_error) {
356
357
        return;
    }
358
    if (parser->result_stack_top >= parser->result_stack_alloc) {
359
        mp_parse_node_t *stack = m_renew_maybe(mp_parse_node_t, parser->result_stack, parser->result_stack_alloc, parser->result_stack_alloc + MICROPY_ALLOC_PARSE_RESULT_INC, true);
360
        if (stack == NULL) {
361
            parser->parse_error = PARSE_ERROR_MEMORY;
362
363
            return;
        }
364
        parser->result_stack = stack;
365
        parser->result_stack_alloc += MICROPY_ALLOC_PARSE_RESULT_INC;
366
    }
Damien's avatar
Damien committed
367
368
369
    parser->result_stack[parser->result_stack_top++] = pn;
}

370
STATIC mp_parse_node_t make_node_string_bytes(parser_t *parser, size_t src_line, size_t rule_kind, const char *str, size_t len) {
371
    mp_parse_node_struct_t *pn = parser_alloc(parser, sizeof(mp_parse_node_struct_t) + sizeof(mp_parse_node_t) * 2);
372
    if (pn == NULL) {
373
        parser->parse_error = PARSE_ERROR_MEMORY;
374
        return MP_PARSE_NODE_NULL;
375
376
    }
    pn->source_line = src_line;
377
    pn->kind_num_nodes = rule_kind | (2 << 8);
378
379
    char *p = m_new(char, len);
    memcpy(p, str, len);
380
    pn->nodes[0] = (uintptr_t)p;
381
    pn->nodes[1] = len;
382
383
384
    return (mp_parse_node_t)pn;
}

385
STATIC mp_parse_node_t make_node_const_object(parser_t *parser, size_t src_line, mp_obj_t obj) {
386
    mp_parse_node_struct_t *pn = parser_alloc(parser, sizeof(mp_parse_node_struct_t) + sizeof(mp_obj_t));
387
    if (pn == NULL) {
388
        parser->parse_error = PARSE_ERROR_MEMORY;
389
390
391
        return MP_PARSE_NODE_NULL;
    }
    pn->source_line = src_line;
392
393
394
395
396
397
    #if MICROPY_OBJ_REPR == MICROPY_OBJ_REPR_D
    // nodes are 32-bit pointers, but need to store 64-bit object
    pn->kind_num_nodes = RULE_const_object | (2 << 8);
    pn->nodes[0] = (uint64_t)obj;
    pn->nodes[1] = (uint64_t)obj >> 32;
    #else
398
    pn->kind_num_nodes = RULE_const_object | (1 << 8);
399
    pn->nodes[0] = (uintptr_t)obj;
400
    #endif
401
    return (mp_parse_node_t)pn;
402
}
403

404
STATIC void push_result_token(parser_t *parser, const rule_t *rule) {
405
    mp_parse_node_t pn;
406
407
    mp_lexer_t *lex = parser->lexer;
    if (lex->tok_kind == MP_TOKEN_NAME) {
408
409
        qstr id = qstr_from_strn(lex->vstr.buf, lex->vstr.len);
        #if MICROPY_COMP_CONST
410
411
412
413
        // if name is a standalone identifier, look it up in the table of dynamic constants
        mp_map_elem_t *elem;
        if (rule->rule_id == RULE_atom
            && (elem = mp_map_lookup(&parser->consts, MP_OBJ_NEW_QSTR(id), MP_MAP_LOOKUP)) != NULL) {
414
            pn = mp_parse_node_new_small_int(MP_OBJ_SMALL_INT_VALUE(elem->value));
415
        } else {
416
417
            pn = mp_parse_node_new_leaf(MP_PARSE_NODE_ID, id);
        }
418
419
420
421
        #else
        (void)rule;
        pn = mp_parse_node_new_leaf(MP_PARSE_NODE_ID, id);
        #endif
422
423
424
    } else if (lex->tok_kind == MP_TOKEN_INTEGER) {
        mp_obj_t o = mp_parse_num_integer(lex->vstr.buf, lex->vstr.len, 0, lex);
        if (MP_OBJ_IS_SMALL_INT(o)) {
425
            pn = mp_parse_node_new_small_int(MP_OBJ_SMALL_INT_VALUE(o));
Damien's avatar
Damien committed
426
        } else {
427
            pn = make_node_const_object(parser, lex->tok_line, o);
Damien's avatar
Damien committed
428
        }
429
430
431
    } else if (lex->tok_kind == MP_TOKEN_FLOAT_OR_IMAG) {
        mp_obj_t o = mp_parse_num_decimal(lex->vstr.buf, lex->vstr.len, true, false, lex);
        pn = make_node_const_object(parser, lex->tok_line, o);
432
433
    } else if (lex->tok_kind == MP_TOKEN_STRING || lex->tok_kind == MP_TOKEN_BYTES) {
        // Don't automatically intern all strings/bytes.  doc strings (which are usually large)
434
435
        // will be discarded by the compiler, and so we shouldn't intern them.
        qstr qst = MP_QSTR_NULL;
436
        if (lex->vstr.len <= MICROPY_ALLOC_PARSE_INTERN_STRING_LEN) {
437
            // intern short strings
438
            qst = qstr_from_strn(lex->vstr.buf, lex->vstr.len);
439
440
        } else {
            // check if this string is already interned
441
            qst = qstr_find_strn(lex->vstr.buf, lex->vstr.len);
442
443
444
        }
        if (qst != MP_QSTR_NULL) {
            // qstr exists, make a leaf node
445
            pn = mp_parse_node_new_leaf(lex->tok_kind == MP_TOKEN_STRING ? MP_PARSE_NODE_STRING : MP_PARSE_NODE_BYTES, qst);
446
        } else {
447
            // not interned, make a node holding a pointer to the string/bytes data
448
            pn = make_node_string_bytes(parser, lex->tok_line, lex->tok_kind == MP_TOKEN_STRING ? RULE_string : RULE_bytes, lex->vstr.buf, lex->vstr.len);
449
        }
Damien's avatar
Damien committed
450
    } else {
451
        pn = mp_parse_node_new_leaf(MP_PARSE_NODE_TOKEN, lex->tok_kind);
Damien's avatar
Damien committed
452
453
454
455
    }
    push_result_node(parser, pn);
}

456
#if MICROPY_COMP_MODULE_CONST
457
STATIC const mp_rom_map_elem_t mp_constants_table[] = {
458
459
460
    #if MICROPY_PY_UERRNO
    { MP_ROM_QSTR(MP_QSTR_errno), MP_ROM_PTR(&mp_module_uerrno) },
    #endif
461
    #if MICROPY_PY_UCTYPES
462
    { MP_ROM_QSTR(MP_QSTR_uctypes), MP_ROM_PTR(&mp_module_uctypes) },
463
464
465
466
467
468
469
    #endif
    // Extra constants as defined by a port
    MICROPY_PORT_CONSTANTS
};
STATIC MP_DEFINE_CONST_MAP(mp_constants_map, mp_constants_table);
#endif

470
471
STATIC void push_result_rule(parser_t *parser, size_t src_line, const rule_t *rule, size_t num_args);

472
#if MICROPY_COMP_CONST_FOLDING
473
STATIC bool fold_constants(parser_t *parser, const rule_t *rule, size_t num_args) {
474
475
476
    // this code does folding of arbitrary integer expressions, eg 1 + 2 * 3 + 4
    // it does not do partial folding, eg 1 + 2 + x -> 3 + x

477
    mp_obj_t arg0;
478
479
480
481
482
    if (rule->rule_id == RULE_expr
        || rule->rule_id == RULE_xor_expr
        || rule->rule_id == RULE_and_expr) {
        // folding for binary ops: | ^ &
        mp_parse_node_t pn = peek_result(parser, num_args - 1);
483
        if (!mp_parse_node_get_int_maybe(pn, &arg0)) {
484
485
            return false;
        }
486
487
488
489
490
491
492
493
        mp_binary_op_t op;
        if (rule->rule_id == RULE_expr) {
            op = MP_BINARY_OP_OR;
        } else if (rule->rule_id == RULE_xor_expr) {
            op = MP_BINARY_OP_XOR;
        } else {
            op = MP_BINARY_OP_AND;
        }
494
        for (ssize_t i = num_args - 2; i >= 0; --i) {
495
            pn = peek_result(parser, i);
496
497
            mp_obj_t arg1;
            if (!mp_parse_node_get_int_maybe(pn, &arg1)) {
498
499
                return false;
            }
500
            arg0 = mp_binary_op(op, arg0, arg1);
501
502
503
504
505
506
        }
    } else if (rule->rule_id == RULE_shift_expr
        || rule->rule_id == RULE_arith_expr
        || rule->rule_id == RULE_term) {
        // folding for binary ops: << >> + - * / % //
        mp_parse_node_t pn = peek_result(parser, num_args - 1);
507
        if (!mp_parse_node_get_int_maybe(pn, &arg0)) {
508
509
            return false;
        }
510
        for (ssize_t i = num_args - 2; i >= 1; i -= 2) {
511
            pn = peek_result(parser, i - 1);
512
513
            mp_obj_t arg1;
            if (!mp_parse_node_get_int_maybe(pn, &arg1)) {
514
515
516
                return false;
            }
            mp_token_kind_t tok = MP_PARSE_NODE_LEAF_ARG(peek_result(parser, i));
517
518
519
520
521
522
523
524
525
526
527
528
529
530
            static const uint8_t token_to_op[] = {
                MP_BINARY_OP_ADD,
                MP_BINARY_OP_SUBTRACT,
                MP_BINARY_OP_MULTIPLY,
                255,//MP_BINARY_OP_POWER,
                255,//MP_BINARY_OP_TRUE_DIVIDE,
                MP_BINARY_OP_FLOOR_DIVIDE,
                MP_BINARY_OP_MODULO,
                255,//MP_BINARY_OP_LESS
                MP_BINARY_OP_LSHIFT,
                255,//MP_BINARY_OP_MORE
                MP_BINARY_OP_RSHIFT,
            };
            mp_binary_op_t op = token_to_op[tok - MP_TOKEN_OP_PLUS];
531
            if (op == (mp_binary_op_t)255) {
532
                return false;
533
534
535
536
537
            }
            int rhs_sign = mp_obj_int_sign(arg1);
            if (op <= MP_BINARY_OP_RSHIFT) {
                // << and >> can't have negative rhs
                if (rhs_sign < 0) {
538
539
                    return false;
                }
540
541
542
            } else if (op >= MP_BINARY_OP_FLOOR_DIVIDE) {
                // % and // can't have zero rhs
                if (rhs_sign == 0) {
543
544
545
                    return false;
                }
            }
546
            arg0 = mp_binary_op(op, arg0, arg1);
547
548
549
550
        }
    } else if (rule->rule_id == RULE_factor_2) {
        // folding for unary ops: + - ~
        mp_parse_node_t pn = peek_result(parser, 0);
551
        if (!mp_parse_node_get_int_maybe(pn, &arg0)) {
552
553
554
            return false;
        }
        mp_token_kind_t tok = MP_PARSE_NODE_LEAF_ARG(peek_result(parser, 1));
555
        mp_unary_op_t op;
556
        if (tok == MP_TOKEN_OP_PLUS) {
557
            op = MP_UNARY_OP_POSITIVE;
558
        } else if (tok == MP_TOKEN_OP_MINUS) {
559
            op = MP_UNARY_OP_NEGATIVE;
560
561
        } else {
            assert(tok == MP_TOKEN_OP_TILDE); // should be
562
            op = MP_UNARY_OP_INVERT;
563
        }
564
        arg0 = mp_unary_op(op, arg0);
565
566
567
568
569
570
571
572
573
574

    #if MICROPY_COMP_CONST
    } else if (rule->rule_id == RULE_expr_stmt) {
        mp_parse_node_t pn1 = peek_result(parser, 0);
        if (!MP_PARSE_NODE_IS_NULL(pn1)
            && !(MP_PARSE_NODE_IS_STRUCT_KIND(pn1, RULE_expr_stmt_augassign)
            || MP_PARSE_NODE_IS_STRUCT_KIND(pn1, RULE_expr_stmt_assign_list))) {
            // this node is of the form <x> = <y>
            mp_parse_node_t pn0 = peek_result(parser, 1);
            if (MP_PARSE_NODE_IS_ID(pn0)
575
                && MP_PARSE_NODE_IS_STRUCT_KIND(pn1, RULE_atom_expr_normal)
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
                && MP_PARSE_NODE_IS_ID(((mp_parse_node_struct_t*)pn1)->nodes[0])
                && MP_PARSE_NODE_LEAF_ARG(((mp_parse_node_struct_t*)pn1)->nodes[0]) == MP_QSTR_const
                && MP_PARSE_NODE_IS_STRUCT_KIND(((mp_parse_node_struct_t*)pn1)->nodes[1], RULE_trailer_paren)
                ) {
                // code to assign dynamic constants: id = const(value)

                // get the id
                qstr id = MP_PARSE_NODE_LEAF_ARG(pn0);

                // get the value
                mp_parse_node_t pn_value = ((mp_parse_node_struct_t*)((mp_parse_node_struct_t*)pn1)->nodes[1])->nodes[0];
                if (!MP_PARSE_NODE_IS_SMALL_INT(pn_value)) {
                    parser->parse_error = PARSE_ERROR_CONST;
                    return false;
                }
                mp_int_t value = MP_PARSE_NODE_LEAF_SMALL_INT(pn_value);

                // store the value in the table of dynamic constants
                mp_map_elem_t *elem = mp_map_lookup(&parser->consts, MP_OBJ_NEW_QSTR(id), MP_MAP_LOOKUP_ADD_IF_NOT_FOUND);
                assert(elem->value == MP_OBJ_NULL);
                elem->value = MP_OBJ_NEW_SMALL_INT(value);

598
599
600
601
602
603
604
605
606
                // If the constant starts with an underscore then treat it as a private
                // variable and don't emit any code to store the value to the id.
                if (qstr_str(id)[0] == '_') {
                    pop_result(parser); // pop const(value)
                    pop_result(parser); // pop id
                    push_result_rule(parser, 0, rules[RULE_pass_stmt], 0); // replace with "pass"
                    return true;
                }

607
608
609
610
611
612
613
614
615
616
617
618
                // replace const(value) with value
                pop_result(parser);
                push_result_node(parser, pn_value);

                // finished folding this assignment, but we still want it to be part of the tree
                return false;
            }
        }
        return false;
    #endif

    #if MICROPY_COMP_MODULE_CONST
619
620
621
    } else if (rule->rule_id == RULE_atom_expr_normal) {
        mp_parse_node_t pn0 = peek_result(parser, 1);
        mp_parse_node_t pn1 = peek_result(parser, 0);
622
        if (!(MP_PARSE_NODE_IS_ID(pn0)
623
            && MP_PARSE_NODE_IS_STRUCT_KIND(pn1, RULE_trailer_period))) {
624
625
626
627
628
629
630
631
632
633
634
635
636
637
            return false;
        }
        // id1.id2
        // look it up in constant table, see if it can be replaced with an integer
        mp_parse_node_struct_t *pns1 = (mp_parse_node_struct_t*)pn1;
        assert(MP_PARSE_NODE_IS_ID(pns1->nodes[0]));
        qstr q_base = MP_PARSE_NODE_LEAF_ARG(pn0);
        qstr q_attr = MP_PARSE_NODE_LEAF_ARG(pns1->nodes[0]);
        mp_map_elem_t *elem = mp_map_lookup((mp_map_t*)&mp_constants_map, MP_OBJ_NEW_QSTR(q_base), MP_MAP_LOOKUP);
        if (elem == NULL) {
            return false;
        }
        mp_obj_t dest[2];
        mp_load_method_maybe(elem->value, q_attr, dest);
638
        if (!(dest[0] != MP_OBJ_NULL && MP_OBJ_IS_INT(dest[0]) && dest[1] == MP_OBJ_NULL)) {
639
640
            return false;
        }
641
        arg0 = dest[0];
642
643
644
645
646
647
648
649
    #endif

    } else {
        return false;
    }

    // success folding this rule

650
    for (size_t i = num_args; i > 0; i--) {
651
652
        pop_result(parser);
    }
653
    if (MP_OBJ_IS_SMALL_INT(arg0)) {
654
        push_result_node(parser, mp_parse_node_new_small_int(MP_OBJ_SMALL_INT_VALUE(arg0)));
655
656
657
658
    } else {
        // TODO reuse memory for parse node struct?
        push_result_node(parser, make_node_const_object(parser, 0, arg0));
    }
659
660
661
662
663

    return true;
}
#endif

664
STATIC void push_result_rule(parser_t *parser, size_t src_line, const rule_t *rule, size_t num_args) {
665
666
667
668
669
670
671
672
673
674
675
676
677
678
    // optimise away parenthesis around an expression if possible
    if (rule->rule_id == RULE_atom_paren) {
        // there should be just 1 arg for this rule
        mp_parse_node_t pn = peek_result(parser, 0);
        if (MP_PARSE_NODE_IS_NULL(pn)) {
            // need to keep parenthesis for ()
        } else if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, RULE_testlist_comp)) {
            // need to keep parenthesis for (a, b, ...)
        } else {
            // parenthesis around a single expression, so it's just the expression
            return;
        }
    }

679
680
681
682
683
684
685
    #if MICROPY_COMP_CONST_FOLDING
    if (fold_constants(parser, rule, num_args)) {
        // we folded this rule so return straight away
        return;
    }
    #endif

686
    mp_parse_node_struct_t *pn = parser_alloc(parser, sizeof(mp_parse_node_struct_t) + sizeof(mp_parse_node_t) * num_args);
687
    if (pn == NULL) {
688
        parser->parse_error = PARSE_ERROR_MEMORY;
689
690
691
692
        return;
    }
    pn->source_line = src_line;
    pn->kind_num_nodes = (rule->rule_id & 0xff) | (num_args << 8);
693
    for (size_t i = num_args; i > 0; i--) {
Damien's avatar
Damien committed
694
695
        pn->nodes[i - 1] = pop_result(parser);
    }
696
    push_result_node(parser, (mp_parse_node_t)pn);
Damien's avatar
Damien committed
697
698
}

699
mp_parse_tree_t mp_parse(mp_lexer_t *lex, mp_parse_input_kind_t input_kind) {
700

701
    // initialise parser and allocate memory for its stacks
702

703
    parser_t parser;
704

705
    parser.parse_error = PARSE_ERROR_NONE;
706

707
    parser.rule_stack_alloc = MICROPY_ALLOC_PARSE_RULE_INIT;
708
709
    parser.rule_stack_top = 0;
    parser.rule_stack = m_new_maybe(rule_stack_t, parser.rule_stack_alloc);
Damien's avatar
Damien committed
710

711
    parser.result_stack_alloc = MICROPY_ALLOC_PARSE_RESULT_INIT;
712
713
    parser.result_stack_top = 0;
    parser.result_stack = m_new_maybe(mp_parse_node_t, parser.result_stack_alloc);
Damien's avatar
Damien committed
714

715
716
    parser.lexer = lex;

717
718
719
    parser.tree.chunk = NULL;
    parser.cur_chunk = NULL;

720
721
722
723
    #if MICROPY_COMP_CONST
    mp_map_init(&parser.consts, 0);
    #endif

724
725
726
727
    // check if we could allocate the stacks
    if (parser.rule_stack == NULL || parser.result_stack == NULL) {
        goto memory_error;
    }
728

729
    // work out the top-level rule to use, and push it on the stack
730
    size_t top_level_rule;
Damien's avatar
Damien committed
731
    switch (input_kind) {
732
        case MP_PARSE_SINGLE_INPUT: top_level_rule = RULE_single_input; break;
Damien George's avatar
Damien George committed
733
        case MP_PARSE_EVAL_INPUT: top_level_rule = RULE_eval_input; break;
Damien's avatar
Damien committed
734
735
        default: top_level_rule = RULE_file_input;
    }
736
    push_rule(&parser, lex->tok_line, rules[top_level_rule], 0);
Damien's avatar
Damien committed
737

738
739
    // parse!

740
741
    size_t n, i; // state for the current rule
    size_t rule_src_line; // source line for the first token matched by the current rule
Damien's avatar
Damien committed
742
    bool backtrack = false;
743
    const rule_t *rule = NULL;
Damien's avatar
Damien committed
744
745
746

    for (;;) {
        next_rule:
747
        if (parser.rule_stack_top == 0 || parser.parse_error) {
Damien's avatar
Damien committed
748
749
750
            break;
        }

751
        pop_rule(&parser, &rule, &i, &rule_src_line);
Damien's avatar
Damien committed
752
753
754
755
        n = rule->act & RULE_ACT_ARG_MASK;

        /*
        // debugging
756
757
        printf("depth=%d ", parser.rule_stack_top);
        for (int j = 0; j < parser.rule_stack_top; ++j) {
Damien's avatar
Damien committed
758
759
760
761
762
763
764
765
766
767
768
769
            printf(" ");
        }
        printf("%s n=%d i=%d bt=%d\n", rule->rule_name, n, i, backtrack);
        */

        switch (rule->act & RULE_ACT_KIND_MASK) {
            case RULE_ACT_OR:
                if (i > 0 && !backtrack) {
                    goto next_rule;
                } else {
                    backtrack = false;
                }
770
771
772
773
                for (; i < n; ++i) {
                    uint16_t kind = rule->arg[i] & RULE_ARG_KIND_MASK;
                    if (kind == RULE_ARG_TOK) {
                        if (lex->tok_kind == (rule->arg[i] & RULE_ARG_ARG_MASK)) {
774
                            push_result_token(&parser, rule);
775
                            mp_lexer_to_next(lex);
Damien's avatar
Damien committed
776
                            goto next_rule;
777
                        }
Damien's avatar
Damien committed
778
                    } else {
779
780
781
782
783
                        assert(kind == RULE_ARG_RULE);
                        if (i + 1 < n) {
                            push_rule(&parser, rule_src_line, rule, i + 1); // save this or-rule
                        }
                        push_rule_from_arg(&parser, rule->arg[i]); // push child of or-rule
Damien's avatar
Damien committed
784
785
786
                        goto next_rule;
                    }
                }
787
                backtrack = true;
Damien's avatar
Damien committed
788
789
                break;

790
            case RULE_ACT_AND: {
Damien's avatar
Damien committed
791
792
793
794
795
796

                // failed, backtrack if we can, else syntax error
                if (backtrack) {
                    assert(i > 0);
                    if ((rule->arg[i - 1] & RULE_ARG_KIND_MASK) == RULE_ARG_OPT_RULE) {
                        // an optional rule that failed, so continue with next arg
797
                        push_result_node(&parser, MP_PARSE_NODE_NULL);
Damien's avatar
Damien committed
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
                        backtrack = false;
                    } else {
                        // a mandatory rule that failed, so propagate backtrack
                        if (i > 1) {
                            // already eaten tokens so can't backtrack
                            goto syntax_error;
                        } else {
                            goto next_rule;
                        }
                    }
                }

                // progress through the rule
                for (; i < n; ++i) {
                    switch (rule->arg[i] & RULE_ARG_KIND_MASK) {
813
                        case RULE_ARG_TOK: {
Damien's avatar
Damien committed
814
                            // need to match a token
815
                            mp_token_kind_t tok_kind = rule->arg[i] & RULE_ARG_ARG_MASK;
816
                            if (lex->tok_kind == tok_kind) {
Damien's avatar
Damien committed
817
                                // matched token
818
                                if (tok_kind == MP_TOKEN_NAME) {
819
                                    push_result_token(&parser, rule);
Damien's avatar
Damien committed
820
                                }
821
                                mp_lexer_to_next(lex);
Damien's avatar
Damien committed
822
823
824
825
826
827
828
829
830
831
832
833
                            } else {
                                // failed to match token
                                if (i > 0) {
                                    // already eaten tokens so can't backtrack
                                    goto syntax_error;
                                } else {
                                    // this rule failed, so backtrack
                                    backtrack = true;
                                    goto next_rule;
                                }
                            }
                            break;
834
                        }
Damien's avatar
Damien committed
835
836
                        case RULE_ARG_RULE:
                        case RULE_ARG_OPT_RULE:
837
                        rule_and_no_other_choice:
838
839
                            push_rule(&parser, rule_src_line, rule, i + 1); // save this and-rule
                            push_rule_from_arg(&parser, rule->arg[i]); // push child of and-rule
Damien's avatar
Damien committed
840
841
842
                            goto next_rule;
                        default:
                            assert(0);
843
                            goto rule_and_no_other_choice; // to help flow control analysis
Damien's avatar
Damien committed
844
845
846
847
848
849
850
                    }
                }

                assert(i == n);

                // matched the rule, so now build the corresponding parse_node

851
                #if !MICROPY_ENABLE_DOC_STRING
852
                // this code discards lonely statements, such as doc strings
853
854
                if (input_kind != MP_PARSE_SINGLE_INPUT && rule->rule_id == RULE_expr_stmt && peek_result(&parser, 0) == MP_PARSE_NODE_NULL) {
                    mp_parse_node_t p = peek_result(&parser, 1);
855
                    if ((MP_PARSE_NODE_IS_LEAF(p) && !MP_PARSE_NODE_IS_ID(p)) || MP_PARSE_NODE_IS_STRUCT_KIND(p, RULE_string)) {
856
                        pop_result(&parser); // MP_PARSE_NODE_NULL
857
858
859
860
                        mp_parse_node_t pn = pop_result(&parser); // possibly RULE_string
                        if (MP_PARSE_NODE_IS_STRUCT(pn)) {
                            mp_parse_node_struct_t *pns = (mp_parse_node_struct_t *)pn;
                            if (MP_PARSE_NODE_STRUCT_KIND(pns) == RULE_string) {
861
                                m_del(char, (char*)pns->nodes[0], (size_t)pns->nodes[1]);
862
863
                            }
                        }
864
                        push_result_rule(&parser, rule_src_line, rules[RULE_pass_stmt], 0);
865
866
867
                        break;
                    }
                }
868
                #endif
869

870
871
                // count number of arguments for the parse node
                i = 0;
872
                size_t num_not_nil = 0;
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
                for (size_t x = n; x > 0;) {
                    --x;
                    if ((rule->arg[x] & RULE_ARG_KIND_MASK) == RULE_ARG_TOK) {
                        mp_token_kind_t tok_kind = rule->arg[x] & RULE_ARG_ARG_MASK;
                        if (tok_kind == MP_TOKEN_NAME) {
                            // only tokens which were names are pushed to stack
                            i += 1;
                            num_not_nil += 1;
                        }
                    } else {
                        // rules are always pushed
                        if (peek_result(&parser, i) != MP_PARSE_NODE_NULL) {
                            num_not_nil += 1;
                        }
                        i += 1;
Damien's avatar
Damien committed
888
889
                    }
                }
890
891
892

                if (num_not_nil == 1 && (rule->act & RULE_ACT_ALLOW_IDENT)) {
                    // this rule has only 1 argument and should not be emitted
893
                    mp_parse_node_t pn = MP_PARSE_NODE_NULL;
894
                    for (size_t x = 0; x < i; ++x) {
895
                        mp_parse_node_t pn2 = pop_result(&parser);
896
                        if (pn2 != MP_PARSE_NODE_NULL) {
Damien's avatar
Damien committed
897
898
899
                            pn = pn2;
                        }
                    }
900
                    push_result_node(&parser, pn);
901
902
903
904
905
906
907
908
909
910
                } else {
                    // this rule must be emitted

                    if (rule->act & RULE_ACT_ADD_BLANK) {
                        // and add an extra blank node at the end (used by the compiler to store data)
                        push_result_node(&parser, MP_PARSE_NODE_NULL);
                        i += 1;
                    }

                    push_result_rule(&parser, rule_src_line, rule, i);
Damien's avatar
Damien committed
911
912
                }
                break;
913
            }
Damien's avatar
Damien committed
914

915
            case RULE_ACT_LIST: {
Damien's avatar
Damien committed
916
917
918
                // n=2 is: item item*
                // n=1 is: item (sep item)*
                // n=3 is: item (sep item)* [sep]
919
                bool had_trailing_sep;
Damien's avatar
Damien committed
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
                if (backtrack) {
                    list_backtrack:
                    had_trailing_sep = false;
                    if (n == 2) {
                        if (i == 1) {
                            // fail on item, first time round; propagate backtrack
                            goto next_rule;
                        } else {
                            // fail on item, in later rounds; finish with this rule
                            backtrack = false;
                        }
                    } else {
                        if (i == 1) {
                            // fail on item, first time round; propagate backtrack
                            goto next_rule;
                        } else if ((i & 1) == 1) {
                            // fail on item, in later rounds; have eaten tokens so can't backtrack
                            if (n == 3) {
                                // list allows trailing separator; finish parsing list
                                had_trailing_sep = true;
                                backtrack = false;
                            } else {
                                // list doesn't allowing trailing separator; fail
                                goto syntax_error;
                            }
                        } else {
                            // fail on separator; finish parsing list
                            backtrack = false;
                        }
                    }
                } else {
                    for (;;) {
952
                        size_t arg = rule->arg[i & 1 & n];
Damien's avatar
Damien committed
953
954
                        switch (arg & RULE_ARG_KIND_MASK) {
                            case RULE_ARG_TOK:
955
                                if (lex->tok_kind == (arg & RULE_ARG_ARG_MASK)) {
Damien's avatar
Damien committed
956
957
958
                                    if (i & 1 & n) {
                                        // separators which are tokens are not pushed to result stack
                                    } else {
959
                                        push_result_token(&parser, rule);
Damien's avatar
Damien committed
960
                                    }
961
                                    mp_lexer_to_next(lex);
Damien's avatar
Damien committed
962
963
964
965
966
967
968
969
970
971
                                    // got element of list, so continue parsing list
                                    i += 1;
                                } else {
                                    // couldn't get element of list
                                    i += 1;
                                    backtrack = true;
                                    goto list_backtrack;
                                }
                                break;
                            case RULE_ARG_RULE:
972
                            rule_list_no_other_choice:
973
974
                                push_rule(&parser, rule_src_line, rule, i + 1); // save this list-rule
                                push_rule_from_arg(&parser, arg); // push child of list-rule
Damien's avatar
Damien committed
975
976
977
                                goto next_rule;
                            default:
                                assert(0);
978
                                goto rule_list_no_other_choice; // to help flow control analysis
Damien's avatar
Damien committed
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
                        }
                    }
                }
                assert(i >= 1);

                // compute number of elements in list, result in i
                i -= 1;
                if ((n & 1) && (rule->arg[1] & RULE_ARG_KIND_MASK) == RULE_ARG_TOK) {
                    // don't count separators when they are tokens
                    i = (i + 1) / 2;
                }

                if (i == 1) {
                    // list matched single item
                    if (had_trailing_sep) {
                        // if there was a trailing separator, make a list of a single item
995
                        push_result_rule(&parser, rule_src_line, rule, i);
Damien's avatar
Damien committed
996
997
998
999
                    } else {
                        // just leave single item on stack (ie don't wrap in a list)
                    }
                } else {
1000
                    push_result_rule(&parser, rule_src_line, rule, i);