Parse arithmetic expressions.

5 files changed, 280 insertions, 67 deletions

diff --git a/dimension/parse.c b/dimension/parse.c
index 51203c5..25d983c 100644
--- a/dimension/parse.c
+++ b/dimension/parse.c
@@ -50,8 +50,8 @@ dmnsn_parse_expect(dmnsn_token_type type, const dmnsn_array *tokens,
 }
 
 static int
-dmnsn_parse_float(const dmnsn_array *tokens, unsigned int *ip,
-                  dmnsn_array *astree)
+dmnsn_parse_number(const dmnsn_array *tokens, unsigned int *ip,
+                   dmnsn_array *astree)
 {
   unsigned int i = *ip;
 
@@ -62,55 +62,233 @@ dmnsn_parse_float(const dmnsn_array *tokens, unsigned int *ip,
     return 1;
   }
 
-  int negative = 0;
   dmnsn_token token;
   dmnsn_array_get(tokens, i, &token);
 
-  if (token.type == DMNSN_T_MINUS) {
-    negative = 1;
+  dmnsn_astnode astnode;
+  astnode.children = NULL;
+
+  if (token.type == DMNSN_T_INTEGER) {
+    astnode.type = DMNSN_AST_INTEGER;
 
+    long *value = malloc(sizeof(double));
+    if (!value)
+      dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate room for integer.");
+
+    *value = strtol(token.value, NULL, 0);
+    astnode.ptr = value;
     ++i;
-    if (i >= dmnsn_array_size(tokens)) {
-      fprintf(stderr, "Expected '%s' or '%s', found end of file\n",
-              dmnsn_token_string(DMNSN_T_INTEGER),
-              dmnsn_token_string(DMNSN_T_FLOAT));
-      return 1;
-    }
-    dmnsn_array_get(tokens, i, &token);
-  }
+  } else if (token.type == DMNSN_T_FLOAT) {
+    astnode.type = DMNSN_AST_FLOAT;
 
-  double *value = malloc(sizeof(double));
-  if (!value) 
-    dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate room for float.");
+    double *value = malloc(sizeof(double));
+    if (!value)
+      dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate room for float.");
 
-  if (token.type == DMNSN_T_INTEGER || token.type == DMNSN_T_FLOAT) {
     *value = strtod(token.value, NULL);
+    astnode.ptr = value;
     ++i;
   } else {
-    fprintf(stderr, "Expected '%s' or '%s', found '%s'\n",
-            dmnsn_token_string(DMNSN_T_INTEGER),
-            dmnsn_token_string(DMNSN_T_FLOAT),
-            dmnsn_token_string(token.type));
+    dmnsn_diagnostic(token.filename, token.line, token.col,
+                     "Expected '%s' or '%s', found '%s'",
+                     dmnsn_token_string(DMNSN_T_INTEGER),
+                     dmnsn_token_string(DMNSN_T_FLOAT),
+                     dmnsn_token_string(token.type));
+    goto bailout;
+  }
+
+  dmnsn_array_push(astree, &astnode);
+  *ip = i;
+  return 0;
+
+ bailout:
+  dmnsn_delete_astree(astnode.children);
+  return 1;
+}
+
+static dmnsn_astnode_type
+dmnsn_op_map(dmnsn_token_type type)
+{
+  switch (type) {
+  case DMNSN_T_PLUS:
+    return DMNSN_AST_ADD;
+
+  case DMNSN_T_MINUS:
+    return DMNSN_AST_SUB;
+
+  case DMNSN_T_STAR:
+    return DMNSN_AST_MUL;
+
+  case DMNSN_T_SLASH:
+    return DMNSN_AST_DIV;
+
+  default:
+    dmnsn_error(DMNSN_SEVERITY_HIGH, "Invalid token mapped to operator.");
+    return 0; /* Silence compiler warning */
+  }
+}
+
+static int
+dmnsn_op_precedence(dmnsn_astnode_type type)
+{
+  switch(type) {
+  case DMNSN_AST_ADD:
+  case DMNSN_AST_SUB:
+    return 0;
+
+  case DMNSN_AST_MUL:
+  case DMNSN_AST_DIV:
     return 1;
+
+  default:
+    dmnsn_error(DMNSN_SEVERITY_HIGH,
+                "Precedence asked of invalid operator.");
+    return 0; /* Silence compiler warning */
   }
+}
 
-  if (negative)
-    *value *= -1.0;
+static int dmnsn_parse_arithexp(const dmnsn_array *tokens, unsigned int *ip,
+                                dmnsn_array *astree);
 
-  dmnsn_astnode astnode;
-  astnode.type     = DMNSN_AST_FLOAT;
-  astnode.children = NULL;
-  astnode.ptr      = value;
+static int
+dmnsn_parse_arithexp(const dmnsn_array *tokens, unsigned int *ip,
+                     dmnsn_array *astree)
+{
+  dmnsn_token token;
+  unsigned int i = *ip;
 
-  dmnsn_array_push(astree, &astnode);
+  if (i >= dmnsn_array_size(tokens)) {
+    fprintf(stderr, "Expected arithmetic expression, found end of file\n");
+    return 1;
+  }
+
+  dmnsn_array *numstack = dmnsn_new_array(sizeof(dmnsn_astnode)),
+              *opstack  = dmnsn_new_array(sizeof(dmnsn_astnode_type));
+
+  while (i < dmnsn_array_size(tokens)) {
+    dmnsn_array_get(tokens, i, &token);
+
+    if (token.type == DMNSN_T_INTEGER || token.type == DMNSN_T_FLOAT) {
+      dmnsn_parse_number(tokens, &i, numstack);
+    } else if (token.type == DMNSN_T_LPAREN) {
+      ++i;
+
+      if (dmnsn_parse_arithexp(tokens, &i, numstack) != 0)
+        goto bailout;
+
+      if (dmnsn_parse_expect(DMNSN_T_RPAREN, tokens, &i) != 0)
+        goto bailout;
+    } else if (token.type == DMNSN_T_PLUS
+               || token.type == DMNSN_T_MINUS
+               || token.type == DMNSN_T_STAR
+               || token.type == DMNSN_T_SLASH)
+
+    {
+      if (dmnsn_array_size(opstack) == dmnsn_array_size(numstack)) {
+        if (token.type == DMNSN_T_MINUS) {
+          /* Unary '-' -- negation */
+          dmnsn_astnode astnode;
+          astnode.type     = DMNSN_AST_NEGATE;
+          astnode.children = dmnsn_new_array(sizeof(dmnsn_astnode));
+          astnode.ptr      = NULL;
+
+          ++i;
+          dmnsn_array_get(tokens, i, &token);
+          if (token.type == DMNSN_T_LPAREN) {
+            if (dmnsn_parse_arithexp(tokens, &i, astnode.children) != 0)
+              goto bailout;
+          } else {
+            if (dmnsn_parse_number(tokens, &i, astnode.children) != 0)
+              goto bailout;
+          }
+
+          dmnsn_array_push(numstack, &astnode);
+        } else {
+          dmnsn_diagnostic(token.filename, token.line, token.col,
+                           "Unexpected '%s' when parsing arithmetic expression",
+                           dmnsn_token_string(token.type));
+          return 1;
+        }
+      } else if (dmnsn_array_size(opstack) == 0) {
+        dmnsn_astnode_type type = dmnsn_op_map(token.type);
+        dmnsn_array_push(opstack, &type);
+        ++i;
+      } else {
+        dmnsn_astnode_type type = dmnsn_op_map(token.type), last_type;
+        dmnsn_array_get(opstack, dmnsn_array_size(opstack) - 1, &last_type);
+
+        while (dmnsn_op_precedence(type) <= dmnsn_op_precedence(last_type)) {
+          dmnsn_astnode astnode, lhs, rhs;
+          astnode.type     = last_type;
+          astnode.children = dmnsn_new_array(sizeof(dmnsn_astnode));
+          astnode.ptr      = NULL;
+
+          dmnsn_array_pop(numstack, &rhs);
+          dmnsn_array_pop(numstack, &lhs);
+
+          dmnsn_array_push(astnode.children, &lhs);
+          dmnsn_array_push(astnode.children, &rhs);
+
+          dmnsn_array_push(numstack, &astnode);
+          dmnsn_array_resize(opstack, dmnsn_array_size(opstack) - 1);
+
+          if (dmnsn_array_size(opstack) > 0) {
+            dmnsn_array_get(opstack, dmnsn_array_size(opstack) - 1, &last_type);
+          } else {
+            break;
+          }
+        }
+
+        dmnsn_array_push(opstack, &type);
+        ++i;
+      }
+    } else {
+      break;
+    }
+  }
+
+  if (dmnsn_array_size(numstack) == 0) {
+    dmnsn_diagnostic(token.filename, token.line, token.col,
+                     "Expected arithmetic expression, found '%s'",
+                     dmnsn_token_string(token.type));
+    goto bailout;
+  }
+
+  while (dmnsn_array_size(numstack) > 1) {
+    dmnsn_astnode_type type;
+    dmnsn_array_pop(opstack, &type);
+
+    dmnsn_astnode astnode, lhs, rhs;
+    astnode.type     = type;
+    astnode.children = dmnsn_new_array(sizeof(dmnsn_astnode));
+    astnode.ptr      = NULL;
+
+    dmnsn_array_pop(numstack, &rhs);
+    dmnsn_array_pop(numstack, &lhs);
+
+    dmnsn_array_push(astnode.children, &lhs);
+    dmnsn_array_push(astnode.children, &rhs);
+
+    dmnsn_array_push(numstack, &astnode);
+  }
+
+  dmnsn_array_push(astree, dmnsn_array_at(numstack, 0));
+  dmnsn_delete_array(opstack);
+  dmnsn_delete_array(numstack);
   *ip = i;
   return 0;
+
+ bailout:
+  dmnsn_delete_array(opstack);
+  dmnsn_delete_astree(numstack);
+  return 1;
 }
 
 static int
 dmnsn_parse_vector(const dmnsn_array *tokens, unsigned int *ip,
                    dmnsn_array *astree)
 {
+  dmnsn_token token;
   unsigned int i = *ip;
 
   if (dmnsn_parse_expect(DMNSN_T_LESS, tokens, &i) != 0)
@@ -121,26 +299,22 @@ dmnsn_parse_vector(const dmnsn_array *tokens, unsigned int *ip,
   astnode.children = dmnsn_new_array(sizeof(dmnsn_astnode));
   astnode.ptr      = NULL;
 
-  /* First element */
-  if (dmnsn_parse_float(tokens, &i, astnode.children) != 0)
-    goto bailout;
-
-  if (dmnsn_parse_expect(DMNSN_T_COMMA, tokens, &i) != 0)
-    goto bailout;
-
-  /* Second element */
-  if (dmnsn_parse_float(tokens, &i, astnode.children) != 0)
-    goto bailout;
-
-  if (dmnsn_parse_expect(DMNSN_T_COMMA, tokens, &i) != 0)
-    goto bailout;
+  do {
+    if (dmnsn_parse_arithexp(tokens, &i, astnode.children) != 0)
+      goto bailout;
 
-  /* Third element */
-  if (dmnsn_parse_float(tokens, &i, astnode.children) != 0)
-    goto bailout;
+    dmnsn_array_get(tokens, i, &token);
+    if (token.type != DMNSN_T_COMMA && token.type != DMNSN_T_GREATER) {
+      dmnsn_diagnostic(token.filename, token.line, token.col,
+                       "Expected '%s' or '%s'; found '%s'",
+                       dmnsn_token_string(DMNSN_T_COMMA),
+                       dmnsn_token_string(DMNSN_T_GREATER),
+                       dmnsn_token_string(token.type));
+      goto bailout;
+    }
 
-  if (dmnsn_parse_expect(DMNSN_T_GREATER, tokens, &i) != 0)
-    goto bailout;
+    ++i;
+  } while (token.type != DMNSN_T_GREATER);
 
   dmnsn_array_push(astree, &astnode);
   *ip = i;
@@ -214,7 +388,7 @@ dmnsn_parse_sphere(const dmnsn_array *tokens, unsigned int *ip,
     goto bailout;
 
   /* Radius */
-  if (dmnsn_parse_float(tokens, &i, astnode.children) != 0)
+  if (dmnsn_parse_number(tokens, &i, astnode.children) != 0)
     goto bailout;
 
   if (dmnsn_parse_expect(DMNSN_T_RBRACE, tokens, &i) != 0)
@@ -250,18 +424,13 @@ dmnsn_parse(const dmnsn_array *tokens)
 
     switch (token.type) {
     case DMNSN_T_BOX:
-      if (dmnsn_parse_box(tokens, &i, astree) != 0) {
-        dmnsn_diagnostic(token.filename, token.line, token.col, "Invalid box");
+      if (dmnsn_parse_box(tokens, &i, astree) != 0)
         goto bailout;
-      }
       break;
 
     case DMNSN_T_SPHERE:
-      if (dmnsn_parse_sphere(tokens, &i, astree) != 0) {
-        dmnsn_diagnostic(token.filename, token.line, token.col,
-                         "Invalid sphere");
+      if (dmnsn_parse_sphere(tokens, &i, astree) != 0)
         goto bailout;
-      }
       break;
 
     default:
@@ -310,9 +479,15 @@ dmnsn_delete_astree(dmnsn_array *astree)
 static void
 dmnsn_print_astnode(FILE *file, dmnsn_astnode astnode)
 {
+  long ivalue;
   double dvalue;
 
   switch (astnode.type) {
+  case DMNSN_AST_INTEGER:
+    ivalue = *(long *)astnode.ptr;
+    fprintf(file, "(%s %ld)", dmnsn_astnode_string(astnode.type), ivalue);
+    break;
+
   case DMNSN_AST_FLOAT:
     dvalue = *(double *)astnode.ptr;
     fprintf(file, "(%s %g)", dmnsn_astnode_string(astnode.type), dvalue);
@@ -377,9 +552,15 @@ dmnsn_astnode_string(dmnsn_astnode_type astnode_type)
   case type:                                                                   \
     return str;
 
+  dmnsn_astnode_map(DMNSN_AST_FLOAT, "float");
+  dmnsn_astnode_map(DMNSN_AST_INTEGER, "integer");
+  dmnsn_astnode_map(DMNSN_AST_NEGATE, "-");
+  dmnsn_astnode_map(DMNSN_AST_ADD, "+");
+  dmnsn_astnode_map(DMNSN_AST_SUB, "-");
+  dmnsn_astnode_map(DMNSN_AST_MUL, "*");
+  dmnsn_astnode_map(DMNSN_AST_DIV, "/");
   dmnsn_astnode_map(DMNSN_AST_BOX, "box");
   dmnsn_astnode_map(DMNSN_AST_VECTOR, "vector");
-  dmnsn_astnode_map(DMNSN_AST_FLOAT, "float");
   dmnsn_astnode_map(DMNSN_AST_SPHERE, "sphere");
 
   default:
diff --git a/dimension/parse.h b/dimension/parse.h
index 02bda6e..d4420fa 100644
--- a/dimension/parse.h
+++ b/dimension/parse.h
@@ -22,6 +22,11 @@
 typedef enum {
   DMNSN_AST_FLOAT,
   DMNSN_AST_INTEGER,
+  DMNSN_AST_NEGATE,
+  DMNSN_AST_ADD,
+  DMNSN_AST_SUB,
+  DMNSN_AST_MUL,
+  DMNSN_AST_DIV,
   DMNSN_AST_VECTOR,
   DMNSN_AST_BOX,
   DMNSN_AST_SPHERE,
diff --git a/dimension/realize.c b/dimension/realize.c
index 8bbf0cc..f9f5532 100644
--- a/dimension/realize.c
+++ b/dimension/realize.c
@@ -25,14 +25,41 @@
 static double
 dmnsn_realize_float(dmnsn_astnode astnode)
 {
-  if (astnode.type == DMNSN_AST_FLOAT) {
-    double *x = astnode.ptr;
-    return *x;
-  } else if (astnode.type == DMNSN_AST_INTEGER) {
-    long *x = astnode.ptr;
-    return *x;
-  } else {
-    dmnsn_error(DMNSN_SEVERITY_HIGH, "Expected a float or an integer.");
+  dmnsn_astnode lhs, rhs;
+
+  switch (astnode.type) {
+  case DMNSN_AST_FLOAT:
+    return *(double *)astnode.ptr;
+
+  case DMNSN_AST_INTEGER:
+    return *(long *)astnode.ptr;
+
+  case DMNSN_AST_NEGATE:
+    dmnsn_array_get(astnode.children, 0, &rhs);
+    return -dmnsn_realize_float(rhs);
+
+  case DMNSN_AST_ADD:
+    dmnsn_array_get(astnode.children, 0, &lhs);
+    dmnsn_array_get(astnode.children, 1, &rhs);
+    return dmnsn_realize_float(lhs) + dmnsn_realize_float(rhs);
+
+  case DMNSN_AST_SUB:
+    dmnsn_array_get(astnode.children, 0, &lhs);
+    dmnsn_array_get(astnode.children, 1, &rhs);
+    return dmnsn_realize_float(lhs) - dmnsn_realize_float(rhs);
+
+  case DMNSN_AST_MUL:
+    dmnsn_array_get(astnode.children, 0, &lhs);
+    dmnsn_array_get(astnode.children, 1, &rhs);
+    return dmnsn_realize_float(lhs) * dmnsn_realize_float(rhs);
+
+  case DMNSN_AST_DIV:
+    dmnsn_array_get(astnode.children, 0, &lhs);
+    dmnsn_array_get(astnode.children, 1, &rhs);
+    return dmnsn_realize_float(lhs) / dmnsn_realize_float(rhs);
+
+  default:
+    dmnsn_error(DMNSN_SEVERITY_HIGH, "Invalid arithmetic expression.");
     return 0; /* Silence compiler warning */
   }
 }
diff --git a/tests/dimension/demo.pov b/tests/dimension/demo.pov
index 386fdd0..24d934a 100644
--- a/tests/dimension/demo.pov
+++ b/tests/dimension/demo.pov
@@ -20,9 +20,9 @@
 // Render demo scene
 
 box {
-  <-1.0, -1.0, -1.0>, <1.0, 1.0, 1.0>
+  <-2.0 + 1, -2/2.0, -1.0>, <1.0, (1.0 + 2)*2 - 5, 1.0 + 2*2 - 4>
 }
 
 sphere {
-  <0, 0, 0>, 1.25
+  <1/5 + -1/5, 1/5.0 - 1.0/5, 0>, 1.25
 }
diff --git a/tests/dimension/demo.sh b/tests/dimension/demo.sh
index 7674fd4..bd05f3d 100755
--- a/tests/dimension/demo.sh
+++ b/tests/dimension/demo.sh
@@ -20,8 +20,8 @@
 #########################################################################
 
 demo=$(${top_builddir}/dimension/dimension --tokenize --parse ${srcdir}/demo.pov)
-demo_exp='(box { < - (float "1.0") , - (float "1.0") , - (float "1.0") > , < (float "1.0") , (float "1.0") , (float "1.0") > } sphere { < (integer "0") , (integer "0") , (integer "0") > , (float "1.25") })
-((box (vector (float -1) (float -1) (float -1)) (vector (float 1) (float 1) (float 1))) (sphere (vector (float 0) (float 0) (float 0)) (float 1.25)))'
+demo_exp='(box { < - (float "2.0") + (integer "1") , - (integer "2") / (float "2.0") , - (float "1.0") > , < (float "1.0") , \( (float "1.0") + (integer "2") \) * (integer "2") - (integer "5") , (float "1.0") + (integer "2") * (integer "2") - (integer "4") > } sphere { < (integer "1") / (integer "5") + - (integer "1") / (integer "5") , (integer "1") / (float "5.0") - (float "1.0") / (integer "5") , (integer "0") > , (float "1.25") })
+((box (vector (+ (- (float 2)) (integer 1)) (/ (- (integer 2)) (float 2)) (- (float 1))) (vector (float 1) (- (* (+ (float 1) (integer 2)) (integer 2)) (integer 5)) (- (+ (float 1) (* (integer 2) (integer 2))) (integer 4)))) (sphere (vector (+ (/ (integer 1) (integer 5)) (/ (- (integer 1)) (integer 5))) (- (/ (integer 1) (float 5)) (/ (float 1) (integer 5))) (integer 0)) (float 1.25)))'
 
 if [ "$demo" != "$demo_exp" ]; then
   echo "demo.pov parsed as \"$demo\"" >&2