Improve list parsing

The previous algorithm was O(n^2)

3 files changed, 40 insertions, 9 deletions

diff --git a/src/ast.c b/src/ast.c
index e776764..e1c6d9a 100644
--- a/src/ast.c
+++ b/src/ast.c
@@ -208,16 +208,41 @@ Ast *ast_paramToCons(Ast *ast) {
   if (ast == NULL) {
     return ast_makeAST(AST_NIL, NULL, NULL);
   }
-
-  Ast *head = ast->left;
-  Ast *tail = ast->right;
-  Ast *ret = ast_makeAST(AST_OPCONS, NULL,
-			 ast_makeList2(head, ast_paramToCons(tail)));
-  return ret;
   
+  Ast *head = NULL, *tail = NULL, *current = ast;
+  while (current != NULL) {
+        head = current->left;
+        tail = current->right;
+        current->id = AST_OPCONS;
+        current->left = NULL;
+        if (tail == NULL) {
+            current->right = ast_makeList2(head, ast_makeAST(AST_NIL, NULL, NULL));
+            break;
+        }
+        else {
+            current->right = ast_makeList2(head, tail);
+            current = tail;
+        }
+  }
+  return ast;
 }
 
+Ast *ast_reverseList(Ast *l) {
+    Ast *prev = NULL;
+    Ast *current = l;
+    Ast *next = NULL;
+    while (current != NULL) {
+        next = current->right;
+        current->right = prev;
+        prev = current;
+        current = next;
+    }
+    return prev;
+}
 
+Ast *ast_addFirst(Ast *l, Ast *p) {
+    return ast_makeAST(AST_LIST, p, l);
+}
 
 Ast *ast_addLast(Ast *l, Ast *p)
 {
diff --git a/src/ast.h b/src/ast.h
index 257024f..6124de8 100644
--- a/src/ast.h
+++ b/src/ast.h
@@ -46,6 +46,8 @@ Ast *ast_makeSymbol(char *name);
 Ast *ast_makeInt(long num);
 Ast *ast_makeAST(AST_ID id, Ast *left, Ast *right);
 Ast *ast_makeTuple(Ast *tuple);
+Ast *ast_reverseList(Ast *l);
+Ast *ast_addFirst(Ast *l, Ast *p);
 Ast *ast_addLast(Ast *l, Ast *p);
 Ast *ast_getNth(Ast *p,int nth);
 Ast *ast_getTail(Ast *p);
diff --git a/src/inpla.y b/src/inpla.y
index 0bdf4b4..bc612f7 100644
--- a/src/inpla.y
+++ b/src/inpla.y
@@ -195,7 +195,7 @@ static char *Errormsg = NULL;
 %token INTERFACE IFCE PRNAT FREE EXIT MEMSTAT
 %token END_OF_FILE USE
 
-%type <ast> body astterm astterm_item nameterm agentterm astparam astparams
+%type <ast> body astterm astterm_item nameterm agentterm astparam astparams_rev astparams
 val_declare
 rule 
 ap aplist
@@ -513,9 +513,13 @@ astparam
 | '(' astparams ')' { $$ = $2; }
 ;
 
-astparams
+astparams_rev
 : astterm { $$ = ast_makeList1($1); }
-| astparams ',' astterm { $$ = ast_addLast($1, $3); }
+| astparams_rev ',' astterm { $$ = ast_addFirst($1, $3); }
+;
+
+astparams
+: astparams_rev { $$ = ast_reverseList($1); }
 ;
 
 ap