summaryrefslogtreecommitdiffstats
path: root/dimension/parse.c
diff options
context:
space:
mode:
Diffstat (limited to 'dimension/parse.c')
-rw-r--r--dimension/parse.c582
1 files changed, 582 insertions, 0 deletions
diff --git a/dimension/parse.c b/dimension/parse.c
new file mode 100644
index 0000000..0bc080f
--- /dev/null
+++ b/dimension/parse.c
@@ -0,0 +1,582 @@
+/*************************************************************************
+ * Copyright (C) 2009 Tavian Barnes <tavianator@gmail.com> *
+ * *
+ * This file is part of Dimension. *
+ * *
+ * Dimension is free software; you can redistribute it and/or modify it *
+ * under the terms of the GNU General Public License as published by the *
+ * Free Software Foundation; either version 3 of the License, or (at *
+ * your option) any later version. *
+ * *
+ * Dimension is distributed in the hope that it will be useful, but *
+ * WITHOUT ANY WARRANTY; without even the implied warranty of *
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
+ * General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU General Public License *
+ * along with this program. If not, see <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+#include "parse.h"
+
+static dmnsn_astnode
+dmnsn_new_astnode(dmnsn_astnode_type type)
+{
+ dmnsn_astnode astnode = {
+ .type = type,
+ .children = NULL,
+ .ptr = NULL,
+ .refcount = malloc(sizeof(unsigned int)),
+ .filename = "<environment>",
+ .line = -1,
+ .col = -1,
+ };
+
+ if (!astnode.refcount) {
+ dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate reference count.");
+ }
+ *astnode.refcount = 0;
+
+ return astnode;
+}
+
+dmnsn_astnode
+dmnsn_new_ast_integer(long value)
+{
+ dmnsn_astnode astnode = dmnsn_new_astnode(DMNSN_AST_INTEGER);
+
+ astnode.ptr = malloc(sizeof(long));
+ if (!astnode.ptr)
+ dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate room for integer.");
+
+ *(long *)astnode.ptr = value;
+ return astnode;
+}
+
+dmnsn_astnode
+dmnsn_new_ast_float(double value)
+{
+ dmnsn_astnode astnode = dmnsn_new_astnode(DMNSN_AST_FLOAT);
+
+ astnode.ptr = malloc(sizeof(double));
+ if (!astnode.ptr)
+ dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate room for float.");
+
+ *(double *)astnode.ptr = value;
+ return astnode;
+}
+
+dmnsn_astnode
+dmnsn_new_ast_string(const char *value)
+{
+ dmnsn_astnode astnode = dmnsn_new_astnode(DMNSN_AST_STRING);
+ astnode.ptr = strdup(value);
+ return astnode;
+}
+
+void
+dmnsn_delete_astnode(dmnsn_astnode astnode)
+{
+ if (*astnode.refcount <= 1) {
+ dmnsn_delete_astree(astnode.children);
+ free(astnode.ptr);
+ free(astnode.refcount);
+ } else {
+ --*astnode.refcount;
+ }
+}
+
+void
+dmnsn_delete_astree(dmnsn_astree *astree)
+{
+ unsigned int i;
+ dmnsn_astnode node;
+
+ if (astree) {
+ for (i = 0; i < dmnsn_array_size(astree); ++i) {
+ dmnsn_array_get(astree, i, &node);
+ dmnsn_delete_astnode(node);
+ }
+ dmnsn_delete_array(astree);
+ }
+}
+
+/* TODO: use a hash table for symbol tables rather than an array */
+
+typedef struct dmnsn_symbol {
+ char *id;
+ dmnsn_astnode value;
+} dmnsn_symbol;
+
+dmnsn_symbol_table *
+dmnsn_new_symbol_table()
+{
+ dmnsn_symbol_table *symtable = dmnsn_new_array(sizeof(dmnsn_array *));
+ dmnsn_push_scope(symtable);
+ return symtable;
+}
+
+static void
+dmnsn_delete_scope(dmnsn_array *scope)
+{
+ while (dmnsn_array_size(scope) > 0) {
+ dmnsn_symbol symbol;
+ dmnsn_array_pop(scope, &symbol);
+
+ free(symbol.id);
+ dmnsn_delete_astnode(symbol.value);
+ }
+ dmnsn_delete_array(scope);
+}
+
+void
+dmnsn_delete_symbol_table(dmnsn_symbol_table *symtable)
+{
+ while (dmnsn_array_size(symtable) > 0) {
+ dmnsn_array *scope;
+ dmnsn_array_pop(symtable, &scope);
+ dmnsn_delete_scope(scope);
+ }
+ dmnsn_delete_array(symtable);
+}
+
+void
+dmnsn_push_scope(dmnsn_symbol_table *symtable)
+{
+ dmnsn_array *scope = dmnsn_new_array(sizeof(dmnsn_symbol));
+ dmnsn_array_push(symtable, &scope);
+}
+
+void dmnsn_pop_scope(dmnsn_symbol_table *symtable)
+{
+ dmnsn_array *scope;
+ dmnsn_array_pop(symtable, &scope);
+ dmnsn_delete_scope(scope);
+}
+
+void dmnsn_push_symbol(dmnsn_symbol_table *symtable,
+ const char *id, dmnsn_astnode value)
+{
+ ++*value.refcount;
+
+ dmnsn_array *scope;
+ dmnsn_array_get(symtable, dmnsn_array_size(symtable) - 1, &scope);
+
+ dmnsn_symbol symbol = { .id = strdup(id), .value = value };
+ dmnsn_array_push(scope, &symbol);
+}
+
+dmnsn_astnode *
+dmnsn_find_symbol(dmnsn_symbol_table *symtable, const char *id)
+{
+ unsigned int i;
+ for (i = 0; i < dmnsn_array_size(symtable); ++i) {
+ dmnsn_array *scope;
+ dmnsn_array_get(symtable, dmnsn_array_size(symtable) - i - 1, &scope);
+
+ unsigned int j;
+ for (j = 0; j < dmnsn_array_size(symtable); ++j) {
+ dmnsn_symbol *symbol = dmnsn_array_at(scope,
+ dmnsn_array_size(scope) - j - 1);
+
+ if (strcmp(id, symbol->id) == 0)
+ return &symbol->value;
+ }
+ }
+
+ return NULL;
+}
+
+static dmnsn_astnode
+dmnsn_copy_astnode(dmnsn_astnode astnode)
+{
+ dmnsn_astnode copy = {
+ .type = astnode.type,
+ .children = dmnsn_new_array(sizeof(dmnsn_astnode)),
+ .ptr = NULL,
+ .refcount = malloc(sizeof(unsigned int)),
+ .filename = astnode.filename,
+ .line = astnode.line,
+ .col = astnode.col
+ };
+
+ if (!copy.refcount) {
+ dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate reference count.");
+ }
+ *copy.refcount = 1;
+
+ return copy;
+}
+
+static dmnsn_astnode
+dmnsn_eval_scalar_unary(dmnsn_astnode astnode, dmnsn_symbol_table *symtable)
+{
+ dmnsn_astnode ret = dmnsn_copy_astnode(astnode), rhs;
+ dmnsn_array_get(astnode.children, 0, &rhs);
+ rhs = dmnsn_eval_scalar(rhs, symtable);
+
+ if (rhs.type == DMNSN_AST_INTEGER) {
+ long n = *(long *)rhs.ptr;
+ long *res = malloc(sizeof(long));
+ if (!res)
+ dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for integer.");
+
+ switch(astnode.type) {
+ case DMNSN_AST_NEGATE:
+ *res = -n;
+ break;
+
+ default:
+ dmnsn_error(DMNSN_SEVERITY_HIGH,
+ "Attempt to evaluate wrong unary operator.");
+ }
+
+ ret.type = DMNSN_AST_INTEGER;
+ ret.ptr = res;
+ } else if (rhs.type == DMNSN_AST_FLOAT) {
+ double n = *(double *)rhs.ptr;
+ double *res = malloc(sizeof(double));
+ if (!res)
+ dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for float.");
+
+ switch(astnode.type) {
+ case DMNSN_AST_NEGATE:
+ *res = -n;
+ break;
+
+ default:
+ dmnsn_error(DMNSN_SEVERITY_HIGH,
+ "Attempt to evaluate wrong unary operator.");
+ }
+
+ ret.type = DMNSN_AST_FLOAT;
+ ret.ptr = res;
+ } else {
+ dmnsn_error(DMNSN_SEVERITY_HIGH,
+ "Invalid right hand side to unary operator.");
+ }
+
+ dmnsn_delete_astnode(rhs);
+ return ret;
+}
+
+static dmnsn_astnode
+dmnsn_eval_scalar_binary(dmnsn_astnode astnode, dmnsn_symbol_table *symtable)
+{
+ dmnsn_astnode ret = dmnsn_copy_astnode(astnode), lhs, rhs;
+ dmnsn_array_get(astnode.children, 0, &lhs);
+ dmnsn_array_get(astnode.children, 1, &rhs);
+ lhs = dmnsn_eval_scalar(lhs, symtable);
+ rhs = dmnsn_eval_scalar(rhs, symtable);
+
+ if (lhs.type == DMNSN_AST_INTEGER && rhs.type == DMNSN_AST_INTEGER
+ && astnode.type != DMNSN_AST_DIV) {
+ long l, r;
+ l = *(long *)lhs.ptr;
+ r = *(long *)rhs.ptr;
+
+ long *res = malloc(sizeof(long));
+ if (!res)
+ dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for integer.");
+
+ switch (astnode.type) {
+ case DMNSN_AST_ADD:
+ *res = l + r;
+ break;
+ case DMNSN_AST_SUB:
+ *res = l - r;
+ break;
+ case DMNSN_AST_MUL:
+ *res = l*r;
+ break;
+
+ default:
+ dmnsn_error(DMNSN_SEVERITY_HIGH,
+ "Attempt to evaluate wrong binary operator.");
+ }
+
+ ret.type = DMNSN_AST_INTEGER;
+ ret.ptr = res;
+ } else {
+ double l = 0.0, r = 0.0;
+
+ if (lhs.type == DMNSN_AST_INTEGER)
+ l = *(long *)lhs.ptr;
+ else if (lhs.type == DMNSN_AST_FLOAT)
+ l = *(double *)lhs.ptr;
+ else
+ dmnsn_error(DMNSN_SEVERITY_HIGH,
+ "Invalid left hand side to binary operator.");
+
+ if (rhs.type == DMNSN_AST_INTEGER)
+ r = *(long *)rhs.ptr;
+ else if (rhs.type == DMNSN_AST_FLOAT)
+ r = *(double *)rhs.ptr;
+ else
+ dmnsn_error(DMNSN_SEVERITY_HIGH,
+ "Invalid right hand side to binary operator.");
+
+ double *res = malloc(sizeof(double));
+ if (!res)
+ dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for float.");
+
+ switch (astnode.type) {
+ case DMNSN_AST_ADD:
+ *res = l + r;
+ break;
+ case DMNSN_AST_SUB:
+ *res = l - r;
+ break;
+ case DMNSN_AST_MUL:
+ *res = l*r;
+ break;
+ case DMNSN_AST_DIV:
+ *res = l/r;
+ break;
+
+ default:
+ dmnsn_error(DMNSN_SEVERITY_HIGH,
+ "Attempt to evaluate wrong binary operator.");
+ }
+
+ ret.type = DMNSN_AST_FLOAT;
+ ret.ptr = res;
+ }
+
+ dmnsn_delete_astnode(lhs);
+ dmnsn_delete_astnode(rhs);
+ return ret;
+}
+
+dmnsn_astnode
+dmnsn_eval_scalar(dmnsn_astnode astnode, dmnsn_symbol_table *symtable)
+{
+ dmnsn_astnode ret;
+
+ switch (astnode.type) {
+ case DMNSN_AST_INTEGER:
+ ret = dmnsn_copy_astnode(astnode);
+ ret.ptr = malloc(sizeof(long));
+ if (!ret.ptr)
+ dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for integer.");
+
+ memcpy(ret.ptr, astnode.ptr, sizeof(long));
+ return ret;
+
+ case DMNSN_AST_FLOAT:
+ ret = dmnsn_copy_astnode(astnode);
+ ret.ptr = malloc(sizeof(double));
+ if (!ret.ptr)
+ dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for float.");
+
+ memcpy(ret.ptr, astnode.ptr, sizeof(double));
+ return ret;
+
+ case DMNSN_AST_NEGATE:
+ return dmnsn_eval_scalar_unary(astnode, symtable);
+
+ case DMNSN_AST_ADD:
+ case DMNSN_AST_SUB:
+ case DMNSN_AST_MUL:
+ case DMNSN_AST_DIV:
+ return dmnsn_eval_scalar_binary(astnode, symtable);
+
+ default:
+ dmnsn_error(DMNSN_SEVERITY_HIGH,
+ "Given non-arithmetic-expression to evaluate.");
+ return astnode; /* Silence warning */
+ }
+}
+
+#define DMNSN_VECTOR_NELEM 5
+
+static dmnsn_astnode
+dmnsn_vector_promote(dmnsn_astnode astnode, dmnsn_symbol_table *symtable)
+{
+ dmnsn_astnode promoted = dmnsn_copy_astnode(astnode), component;
+ promoted.type = DMNSN_AST_VECTOR;
+
+ if (astnode.type == DMNSN_AST_VECTOR) {
+ unsigned int i;
+ for (i = 0; i < dmnsn_array_size(astnode.children); ++i) {
+ dmnsn_array_get(astnode.children, i, &component);
+ component = dmnsn_eval_scalar(component, symtable);
+ dmnsn_array_push(promoted.children, &component);
+ }
+
+ while (dmnsn_array_size(promoted.children) < DMNSN_VECTOR_NELEM) {
+ component = dmnsn_copy_astnode(component);
+ component.type = DMNSN_AST_INTEGER;
+
+ long *val = malloc(sizeof(long));
+ *val = 0;
+
+ component.ptr = val;
+ dmnsn_array_push(promoted.children, &component);
+ }
+ } else {
+ component = dmnsn_eval_scalar(astnode, symtable);
+ dmnsn_array_push(promoted.children, &component);
+
+ while (dmnsn_array_size(promoted.children) < DMNSN_VECTOR_NELEM) {
+ component = dmnsn_eval_scalar(component, symtable);
+ dmnsn_array_push(promoted.children, &component);
+ }
+ }
+
+ return promoted;
+}
+
+static dmnsn_astnode
+dmnsn_eval_vector_unary(dmnsn_astnode astnode, dmnsn_symbol_table *symtable)
+{
+ unsigned int i;
+
+ dmnsn_astnode rhs;
+ dmnsn_array_get(astnode.children, 0, &rhs);
+ rhs = dmnsn_eval_vector(rhs, symtable);
+
+ dmnsn_astnode ret = dmnsn_copy_astnode(astnode), temp;
+ ret.type = DMNSN_AST_VECTOR;
+
+ dmnsn_astnode op = dmnsn_copy_astnode(astnode);
+ for (i = 0; i < DMNSN_VECTOR_NELEM; ++i) {
+ dmnsn_array_get(rhs.children, i, dmnsn_array_at(op.children, 0));
+ temp = dmnsn_eval_scalar_unary(op, symtable);
+ dmnsn_array_set(ret.children, i, &temp);
+ }
+
+ dmnsn_delete_array(op.children);
+ op.children = NULL;
+ dmnsn_delete_astnode(op);
+ dmnsn_delete_astnode(rhs);
+ return ret;
+}
+
+static dmnsn_astnode
+dmnsn_eval_vector_binary(dmnsn_astnode astnode, dmnsn_symbol_table *symtable)
+{
+ unsigned int i;
+
+ dmnsn_astnode lhs, rhs;
+ dmnsn_array_get(astnode.children, 0, &lhs);
+ dmnsn_array_get(astnode.children, 1, &rhs);
+ lhs = dmnsn_eval_vector(lhs, symtable);
+ rhs = dmnsn_eval_vector(rhs, symtable);
+
+ dmnsn_astnode ret = dmnsn_copy_astnode(astnode), temp;
+ ret.type = DMNSN_AST_VECTOR;
+
+ dmnsn_astnode op = dmnsn_copy_astnode(astnode);
+ for (i = 0; i < DMNSN_VECTOR_NELEM; ++i) {
+ dmnsn_array_get(lhs.children, i, dmnsn_array_at(op.children, 0));
+ dmnsn_array_get(rhs.children, i, dmnsn_array_at(op.children, 1));
+ temp = dmnsn_eval_scalar_binary(op, symtable);
+ dmnsn_array_set(ret.children, i, &temp);
+ }
+
+ dmnsn_delete_array(op.children);
+ op.children = NULL;
+ dmnsn_delete_astnode(op);
+ dmnsn_delete_astnode(lhs);
+ dmnsn_delete_astnode(rhs);
+ return ret;
+}
+
+dmnsn_astnode
+dmnsn_eval_vector(dmnsn_astnode astnode, dmnsn_symbol_table *symtable)
+{
+ switch (astnode.type) {
+ case DMNSN_AST_INTEGER:
+ case DMNSN_AST_FLOAT:
+ case DMNSN_AST_VECTOR:
+ return dmnsn_vector_promote(astnode, symtable);
+
+ case DMNSN_AST_NEGATE:
+ return dmnsn_eval_vector_unary(astnode, symtable);
+
+ case DMNSN_AST_ADD:
+ case DMNSN_AST_SUB:
+ case DMNSN_AST_MUL:
+ case DMNSN_AST_DIV:
+ return dmnsn_eval_vector_binary(astnode, symtable);
+
+ default:
+ dmnsn_error(DMNSN_SEVERITY_HIGH,
+ "Given non-arithmetic-expression to evaluate.");
+ return astnode; /* Silence warning */
+ }
+}
+
+static void
+dmnsn_print_astnode(FILE *file, dmnsn_astnode astnode)
+{
+ long ivalue;
+ double dvalue;
+ const char *svalue;
+
+ 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);
+ break;
+
+ case DMNSN_AST_STRING:
+ svalue = astnode.ptr;
+ fprintf(file, "(%s \"%s\")", dmnsn_astnode_string(astnode.type), svalue);
+ break;
+
+ default:
+ fprintf(file, "%s", dmnsn_astnode_string(astnode.type));
+ }
+}
+
+static void
+dmnsn_print_astree(FILE *file, dmnsn_astnode astnode)
+{
+ unsigned int i;
+ dmnsn_astnode child;
+
+ if (astnode.children && dmnsn_array_size(astnode.children) > 0) {
+ fprintf(file, "(");
+ dmnsn_print_astnode(file, astnode);
+ for (i = 0; i < dmnsn_array_size(astnode.children); ++i) {
+ dmnsn_array_get(astnode.children, i, &child);
+ fprintf(file, " ");
+ dmnsn_print_astree(file, child);
+ }
+ fprintf(file, ")");
+ } else {
+ dmnsn_print_astnode(file, astnode);
+ }
+}
+
+void
+dmnsn_print_astree_sexpr(FILE *file, const dmnsn_astree *astree)
+{
+ dmnsn_astnode astnode;
+ unsigned int i;
+
+ if (dmnsn_array_size(astree) == 0) {
+ fprintf(file, "()");
+ } else {
+ fprintf(file, "(");
+ dmnsn_array_get(astree, 0, &astnode);
+ dmnsn_print_astree(file, astnode);
+
+ for (i = 1; i < dmnsn_array_size(astree); ++i) {
+ fprintf(file, " ");
+ dmnsn_array_get(astree, i, &astnode);
+ dmnsn_print_astree(file, astnode);
+ }
+
+ fprintf(file, ")");
+ }
+
+ fprintf(file, "\n");
+}