Implement loops

pablogsal · May 26, 2020 · May 27, 2020 · May 27, 2020 · May 27, 2020 · May 27, 2020
commit d2a980fa338a011d285a74698570f7f3b24ebc2a
diff --git a/Parser/pegen/vm.c b/Parser/pegen/vm.c
@@ -14,10 +14,12 @@ push_frame(Stack *stack, Rule *rule)
     assert(stack->top < 100);
     Frame *f = &stack->frames[stack->top++];
     f->rule = rule;
+    f->mark = stack->p->mark;
     f->ialt = 0;
     f->iop = 0;
     f->cut = 0;
-    f->mark = stack->p->mark;
+    f->ncollected = 0;
+    f->collection = NULL;
     f->ival = 0;
     return f;
 }
@@ -26,11 +28,28 @@ static Frame *
 pop_frame(Stack *stack)
 {
     assert(stack->top > 1);
-    Frame *f = &stack->frames[--stack->top - 1];
+    Frame *f = &stack->frames[--stack->top];  // Frame being popped
+    if (f->collection) {
+        PyMem_Free(f->collection);
+    }
+    f = &stack->frames[stack->top - 1];  // New top of stack
     printf("               pop %s\n", f->rule->name);
     return f;
 }
 
+static asdl_seq *
+make_asdl_seq(Parser *p, void *collection[], int ncollected)
+{
+    asdl_seq *seq = _Py_asdl_seq_new(ncollected, p->arena);
+    if (!seq) {
+        return NULL;
+    }
+    for (int i = 0; i < ncollected; i++) {
+        asdl_seq_SET(seq, i, collection[i]);
+    }
+    return seq;
+}
+
 static void *
 run_vm(Parser *p, Rule rules[], int start)
 {
@@ -43,8 +62,8 @@ run_vm(Parser *p, Rule rules[], int start)
     if (p->mark == p->fill)
         _PyPegen_fill_token(p);
     for (int i = 0; i < stack.top; i++) printf(" ");
-    printf("Rule: %s; ialt=%d; iop=%d; op=%s; p^='%s'\n",
-           f->rule->name, f->ialt, f->iop, opcode_names[f->rule->opcodes[f->iop]],
+    printf("Rule: %s; ialt=%d; iop=%d; op=%s; mark=%d; token=%d; p^='%s'\n",
+           f->rule->name, f->ialt, f->iop, opcode_names[f->rule->opcodes[f->iop]], p->mark, p->tokens[p->mark]->type,
            p->fill > p-> mark ? PyBytes_AsString(p->tokens[p->mark]->bytes) : "<UNSEEN>");
     switch (f->rule->opcodes[f->iop++]) {
     case OP_NOOP:
@@ -60,6 +79,33 @@ run_vm(Parser *p, Rule rules[], int start)
         goto top;
     case OP_OPTIONAL:
         goto top;
+    case OP_LOOP_START:
+        f->ncollected = 0;
+        f->collection = PyMem_Malloc(0);
+        if (!f->collection) {
+            return PyErr_NoMemory();
+        }
+        goto top;
+    case OP_LOOP_ITERATE:
+        f->mark = p->mark;
+        assert(f->ival == 1);
+        v = f->vals[0];
+        assert(v);
+        f->collection = PyMem_Realloc(f->collection, (f->ncollected + 1) * sizeof(void *));
+        if (!f->collection) {
+            return NULL;
+        }
+        f->collection[f->ncollected++] = v;
+        f->iop = f->rule->alts[f->ialt] + 1;  // Skip OP_LOOP_START operation
+        f->ival = 0;
+        goto top;
+    case OP_LOOP_COLLECT:
+        v = make_asdl_seq(p, f->collection, f->ncollected);
+        f = pop_frame(&stack);
+        if (!v) {
+            return PyErr_NoMemory();
+        }
+        break;
     case OP_TOKEN:
         oparg = f->rule->opcodes[f->iop++];
         v = _PyPegen_expect_token(p, oparg);
@@ -76,10 +122,10 @@ run_vm(Parser *p, Rule rules[], int start)
     case OP_SUCCESS:
         oparg = f->rule->opcodes[f->iop++];
         v = call_action(p, f, oparg);
-        if (v) {
+        if (v || PyErr_Occurred()) {
             return v;
         }
-        // fallthrough
+        return RAISE_SYNTAX_ERROR("Final action failed");
     case OP_FAILURE:
         return RAISE_SYNTAX_ERROR("A syntax error");
     default:

diff --git a/Parser/pegen/vm.h b/Parser/pegen/vm.h
@@ -6,13 +6,13 @@ typedef enum _opcodes {
     OP_CUT,
     OP_OPTIONAL,
     OP_LOOP_START,
-    OP_LOOP_COLLECT,
+    OP_LOOP_ITERATE,
     OP_FAILURE,
     // The rest have an argument
     OP_TOKEN,
     OP_RULE,
     OP_RETURN,
-    OP_LOOP_CONTINUE,
+    OP_LOOP_COLLECT,
     OP_SUCCESS,
 } Opcode;
 
@@ -24,13 +24,13 @@ char *opcode_names[] = {
     "OP_CUT",
     "OP_OPTIONAL",
     "OP_LOOP_START",
-    "OP_LOOP_COLLECT",
+    "OP_LOOP_ITERATE",
     "OP_FAILURE",
     // The rest have an argument
     "OP_TOKEN",
     "OP_RULE",
     "OP_RETURN",
-    "OP_LOOP_CONTINUE",
+    "OP_LOOP_COLLECT",
     "OP_SUCCESS",
 };
 
@@ -42,10 +42,12 @@ typedef struct _rule {
 
 typedef struct _frame {
     Rule *rule;
+    int mark;
     int ialt;
     int iop;
     int cut;
-    int mark;
+    int ncollected;
+    void **collection;
     int ival;
     void *vals[10];
 } Frame;
@@ -58,9 +60,9 @@ typedef struct _stack {
 
 /* Toy grammar
 
-NOTE: [expr] is optional to test OP_RULE_OPTIONAL.
+NOTE: [expr] is right-recursive.
 
-start: stmt ENDMARKER
+start: stmt* ENDMARKER
 stmt: expr NEWLINE
 expr: term '+' expr | term
 term: NAME | NUMBER
@@ -73,6 +75,7 @@ static KeywordToken *reserved_keywords[] = {
 
 enum {
       R_START,
+      R_STMTS,
       R_STMT,
       R_EXPR,
       R_TERM,
@@ -90,19 +93,32 @@ enum {
 static Rule all_rules[] = {
 
     {"start",
-     {0, 4, -1},
+     {0, 6, -1},
      {
-      OP_RULE, R_STMT,
+      OP_RULE, R_STMTS,
+      OP_TOKEN, ENDMARKER,
       OP_SUCCESS, A_START_0,
 
       OP_FAILURE,
      },
     },
 
+    {"stmt*",
+     {0, 4, -1},
+     {
+      OP_LOOP_START,
+      OP_RULE, R_STMT,
+      OP_LOOP_ITERATE,
+
+      OP_LOOP_COLLECT,
+     },
+    },
+
     {"stmt",
      {0, -1},
      {
       OP_RULE, R_EXPR,
+      OP_TOKEN, NEWLINE,
       OP_RETURN, A_STMT_0,
      },
     },
@@ -139,15 +155,21 @@ call_action(Parser *p, Frame *f, int iaction)
     Token *t = p->tokens[f->mark];
     int _start_lineno = t->lineno;
     int _start_col_offset = t->col_offset;
-    t = p->tokens[p->mark - 1];
+    if (p->mark > 0) {
+        t = p->tokens[p->mark - 1];
+    }
+    else {
+        // Debug anomaly rather than crashing
+        printf("p->mark=%d, p->fill=%d, f->mark=%d\n", p->mark, p->fill, f->mark);
+    }
     int _end_lineno = t->end_lineno;
     int _end_col_offset = t->end_col_offset;
 
     switch (iaction) {
     case A_START_0:
         return  _PyPegen_make_module(p, f->vals[0]);
     case A_STMT_0:
-        return _PyPegen_singleton_seq(p, _Py_Expr(f->vals[0], EXTRA));
+        return _Py_Expr(f->vals[0], EXTRA);
     case A_EXPR_0:
         if (f->vals[2])
             return _Py_BinOp(f->vals[0], Add, f->vals[2], EXTRA);