Implement expression parsing

2 files changed, 513 insertions, 11 deletions

diff --git a/include/expr.h b/include/expr.h
index 93b9204..8b4d8b0 100644
--- a/include/expr.h
+++ b/include/expr.h
@@ -4,10 +4,6 @@
 #include "lex.h"
 #include "type.h"
 
-struct grouping_e {
-	struct disjunction_e *inner;
-};
-
 struct number_e {
 	struct number value;
 	struct type type;
@@ -30,7 +26,7 @@ struct literal_e {
 	enum literal kind;
 	union {
 		bool b;
-		const char *str;
+		char *str;
 		struct number_e num;
 		struct array_e arr;
 	} lit;
@@ -57,7 +53,7 @@ enum primary {
 struct primary_e {
 	enum primary kind;
 	union {
-		struct grouping_e grp;
+		struct disjunction_e *grp;
 		struct literal_e lit;
 		struct call_e call;
 		struct path path;
@@ -65,6 +61,7 @@ struct primary_e {
 };
 
 enum unary_postfix {
+	UPS_NONE,
 	UPS_DEREF,
 	UPS_TRY,
 	UPS_ASSERT,
@@ -76,9 +73,10 @@ struct unarypost_e {
 };
 
 enum unary_prefix {
-	UPR_NUMNEG,
-	UPR_BOOLNEG,
-	UPR_BITNEG,
+	UPR_NONE,
+	UPR_NEG,
+	UPR_INVERT,
+	UPR_BNEG,
 };
 
 struct unarypre_e {
@@ -142,7 +140,7 @@ enum term {
 
 struct term_e {
 	enum term term;
-	struct num_e lhs, rhs;
+	struct num_e lhs, *rhs;
 };
 
 enum comparison {
@@ -165,7 +163,7 @@ struct cmp_e {
 
 struct eq_e {
 	bool invert;
-	struct cmp_e lhs, rhs;
+	struct cmp_e lhs, *rhs;
 };
 
 enum boolean {
diff --git a/src/parse.c b/src/parse.c
index ef4f4dc..8789d37 100644
--- a/src/parse.c
+++ b/src/parse.c
@@ -1,9 +1,15 @@
+#define _POSIX_C_SOURCE 200809L
+
 #include <stdarg.h>
 #include <stdlib.h>
 #include <stdnoreturn.h>
+#include <string.h>
 #include "parse.h"
 #include "util.h"
 
+static bool parse_disjunction_e(struct lexer *lexer,
+		struct disjunction_e *out);
+
 static noreturn void
 error(struct location loc, const char *fmt, ...)
 {
@@ -55,6 +61,504 @@ parse_path(struct lexer *lexer, struct path *out)
 }
 
 static bool
+parse_grouping_e(struct lexer *lexer, struct disjunction_e *out)
+{
+	if (!match(lexer, T_LPAREN)) {
+		return false;
+	}
+
+	if (!parse_disjunction_e(lexer, out)) {
+		error(lex_loc(lexer), "syntax error: expected expression");
+	}
+
+	if (!match(lexer, T_RPAREN)) {
+		error(lex_loc(lexer), "syntax error: expected ')'");
+	}
+
+	return true;
+}
+
+static bool
+parse_literal_e(struct lexer *lexer, struct literal_e *out)
+{
+	/* TODO */
+	error(lex_loc(lexer), "unimplemented: literals");
+}
+
+// Invariant: Only called from parse_primary_e with path already consumed.
+static bool
+parse_call_e(struct lexer *lexer, struct call_e *out, struct path path)
+{
+	if (!match(lexer, T_LPAREN)) {
+		return false;
+	}
+
+	out->path = path;
+	out->args = must_calloc(1, sizeof(struct disjunction_e));
+	out->argsz = 1;
+	out->arglen = 0;
+
+	struct disjunction_e expr;
+	while (parse_disjunction_e(lexer, &expr)) {
+		if (out->arglen >= out->argsz) {
+			out->argsz *= 2;
+			size_t sz = sizeof(struct disjunction_e) * out->argsz;
+			out->args = must_realloc(out->args, sz);
+		}
+		out->args[out->arglen++] = expr;
+	}
+
+	if (!match(lexer, T_RPAREN)) {
+		error(lex_loc(lexer), "syntax error: expected ')'");
+	}
+
+	return true;
+}
+
+static bool
+parse_primary_e(struct lexer *lexer, struct primary_e *out)
+{
+	out->prim.grp = must_malloc(sizeof(struct disjunction_e));
+	if (parse_grouping_e(lexer, out->prim.grp)) {
+		out->kind = PRM_GROUPING;
+		return true;
+	}
+	free(out->prim.grp);
+	if (parse_literal_e(lexer, &out->prim.lit)) {
+		out->kind = PRM_LITERAL;
+		return true;
+	}
+	if (parse_path(lexer, &out->prim.path)) {
+		out->kind = PRM_PATH;
+		if (parse_call_e(lexer, &out->prim.call, out->prim.path)) {
+			out->kind = PRM_CALL;
+		}
+		return true;
+	}
+}
+
+static bool
+parse_unarypost_e(struct lexer *lexer, struct unarypost_e *out)
+{
+	if (!parse_primary_e(lexer, &out->prim)) {
+		return false;
+	}
+
+	if (match(lexer, T_STAR)) {
+		out->op = UPS_DEREF;
+	} else if (match(lexer, T_QUESTION)) {
+		out->op = UPS_TRY;
+	} else if (match(lexer, T_BANG)) {
+		out->op = UPS_ASSERT;
+	} else {
+		out->op = UPS_NONE;
+	}
+
+	return true;
+}
+
+static bool
+parse_unarypre_e(struct lexer *lexer, struct unarypre_e *out)
+{
+	if (match(lexer, T_MINUS)) {
+		out->op = UPR_NEG;
+	} else if (match(lexer, T_BANG)) {
+		out->op = UPR_INVERT;
+	} else if (match(lexer, T_BNOT)) {
+		out->op = UPR_BNEG;
+	} else {
+		out->op = UPR_NONE;
+	}
+
+	if (!parse_unarypost_e(lexer, &out->post)) {
+		error(lex_loc(lexer),
+				"syntax error: expected unary postfix expression");
+	}
+
+	return true;
+}
+
+static bool
+parse_bitfactor_rhs(struct lexer *lexer, struct unarypre_e *out)
+{
+	if (!match(lexer, T_BAND)) {
+		return false;
+	}
+
+	if (!parse_unarypre_e(lexer, out)) {
+		error(lex_loc(lexer),
+				"syntax error: expected unary prefix expression");
+	}
+
+	return true;
+}
+
+static bool
+parse_bitfactor_e(struct lexer *lexer, struct bitfactor_e *out)
+{
+	if (!parse_unarypre_e(lexer, &out->lhs)) {
+		return false;
+	}
+
+	out->rhs = must_calloc(1, sizeof(struct unarypre_e));
+	out->rhssz = 1;
+	out->rhslen = 0;
+
+	struct unarypre_e rhs;
+	while (parse_bitfactor_rhs(lexer, &rhs)) {
+		if (out->rhslen >= out->rhssz) {
+			out->rhssz *= 2;
+			size_t sz = sizeof(struct unarypre_e) * out->rhssz;
+			out->rhs = must_realloc(out->rhs, sz);
+		}
+		out->rhs[out->rhslen++] = rhs;
+	}
+
+	return true;
+}
+
+static bool
+parse_bitsummand_rhs(struct lexer *lexer, struct bitfactor_e *out)
+{
+	if (!match(lexer, T_BXOR)) {
+		return false;
+	}
+
+	if (!parse_bitfactor_e(lexer, out)) {
+		error(lex_loc(lexer), "syntax error: expected bit factor");
+	}
+
+	return true;
+}
+
+static bool
+parse_bitsummand_e(struct lexer *lexer, struct bitsummand_e *out)
+{
+	if (!parse_bitfactor_e(lexer, &out->lhs)) {
+		return false;
+	}
+
+	out->rhs = must_calloc(1, sizeof(struct bitfactor_e));
+	out->rhssz = 1;
+	out->rhslen = 0;
+
+	struct bitfactor_e rhs;
+	while (parse_bitsummand_rhs(lexer, &rhs)) {
+		if (out->rhslen >= out->rhssz) {
+			out->rhssz *= 2;
+			size_t sz = sizeof(struct bitfactor_e) * out->rhssz;
+			out->rhs = must_realloc(out->rhs, sz);
+		}
+		out->rhs[out->rhslen++] = rhs;
+	}
+
+	return true;
+}
+
+static bool
+parse_bin_rhs(struct lexer *lexer, struct bitsummand_e *out)
+{
+	if (!match(lexer, T_BOR)) {
+		return false;
+	}
+
+	if (!parse_bitsummand_e(lexer, out)) {
+		error(lex_loc(lexer), "syntax error: expected bit summand");
+	}
+
+	return true;
+}
+
+static bool
+parse_bin_e(struct lexer *lexer, struct bin_e *out)
+{
+	if (!parse_bitsummand_e(lexer, &out->lhs)) {
+		return false;
+	}
+
+	out->rhs = must_calloc(1, sizeof(struct bitsummand_e));
+	out->rhssz = 1;
+	out->rhslen = 0;
+
+	struct bitsummand_e rhs;
+	while (parse_bin_rhs(lexer, &rhs)) {
+		if (out->rhslen >= out->rhssz) {
+			out->rhssz *= 2;
+			size_t sz = sizeof(struct bitsummand_e) * out->rhssz;
+			out->rhs = must_realloc(out->rhs, sz);
+		}
+		out->rhs[out->rhslen++] = rhs;
+	}
+
+	return true;
+}
+
+static bool
+parse_factor_rhs(struct lexer *lexer, struct factor_rhs *out)
+{
+	if (match(lexer, T_STAR)) {
+		out->factor = FCT_MUL;
+	} else if (match(lexer, T_DIV)) {
+		out->factor = FCT_DIV;
+	} else if (match(lexer, T_MODULO)) {
+		out->factor = FCT_REM;
+	} else {
+		return false;
+	}
+
+	if (!parse_bin_e(lexer, &out->bin)) {
+		error(lex_loc(lexer),
+				"syntax error: expected bitwise expression");
+	}
+
+	return true;
+}
+
+static bool
+parse_factor_e(struct lexer *lexer, struct factor_e *out)
+{
+	if (!parse_bin_e(lexer, &out->lhs)) {
+		return false;
+	}
+
+	out->rhs = must_calloc(1, sizeof(struct factor_rhs));
+	out->rhssz = 1;
+	out->rhslen = 0;
+
+	struct factor_rhs rhs;
+	while (parse_factor_rhs(lexer, &rhs)) {
+		if (out->rhslen >= out->rhssz) {
+			out->rhssz *= 2;
+			size_t sz = sizeof(struct factor_rhs) * out->rhssz;
+			out->rhs = must_realloc(out->rhs, sz);
+		}
+		out->rhs[out->rhslen++] = rhs;
+	}
+
+	return true;
+}
+
+static bool
+parse_num_rhs(struct lexer *lexer, struct num_rhs *out)
+{
+	if (match(lexer, T_ADD)) {
+		out->num = NUM_ADD;
+	} else if (match(lexer, T_MINUS)) {
+		out->num = NUM_SUB;
+	} else {
+		return false;
+	}
+
+	if (!parse_factor_e(lexer, &out->factor)) {
+		error(lex_loc(lexer),
+				"syntax error: expected factor expression");
+	}
+
+	return true;
+}
+
+static bool
+parse_num_e(struct lexer *lexer, struct num_e *out)
+{
+	if (!parse_factor_e(lexer, &out->lhs)) {
+		return false;
+	}
+
+	out->rhs = must_calloc(1, sizeof(struct num_rhs));
+	out->rhssz = 1;
+	out->rhslen = 0;
+
+	struct num_rhs rhs;
+	while (parse_num_rhs(lexer, &rhs)) {
+		if (out->rhslen >= out->rhssz) {
+			out->rhssz *= 2;
+			size_t sz = sizeof(struct num_rhs) * out->rhssz;
+			out->rhs = must_realloc(out->rhs, sz);
+		}
+		out->rhs[out->rhslen++] = rhs;
+	}
+
+	return true;
+}
+
+static bool
+parse_term_e(struct lexer *lexer, struct term_e *out)
+{
+	if (!parse_num_e(lexer, &out->lhs)) {
+		return false;
+	}
+
+	if (match(lexer, T_BSHL)) {
+		out->term = TRM_SHL;
+	} else if (match(lexer, T_BSHR)) {
+		out->term = TRM_SHL;
+	} else {
+		out->term = TRM_NUM;
+		out->rhs = NULL;
+		return true;
+	}
+
+	out->rhs = must_malloc(sizeof(struct num_e));
+	if (!parse_num_e(lexer, out->rhs)) {
+		error(lex_loc(lexer),
+				"syntax error: expected numeral expression");
+	}
+
+	return true;
+}
+
+static bool
+parse_comparison_rhs(struct lexer *lexer, struct cmp_rhs *out)
+{
+	if (match(lexer, T_LT)) {
+		out->cmp = CMP_LT;
+	} else if (match(lexer, T_LE)) {
+		out->cmp = CMP_LE;
+	} else if (match(lexer, T_GT)) {
+		out->cmp = CMP_GT;
+	} else if (match(lexer, T_GE)) {
+		out->cmp = CMP_GE;
+	} else {
+		return false;
+	}
+
+	if (!parse_term_e(lexer, &out->term)) {
+		error(lex_loc(lexer), "syntax error: expected term");
+	}
+
+	return true;
+}
+
+static bool
+parse_comparison_e(struct lexer *lexer, struct cmp_e *out)
+{
+	if (!parse_term_e(lexer, &out->lhs)) {
+		return false;
+	}
+
+	out->rhs = must_calloc(1, sizeof(struct cmp_rhs));
+	out->rhssz = 1;
+	out->rhslen = 0;
+
+	struct cmp_rhs rhs;
+	while (parse_comparison_rhs(lexer, &rhs)) {
+		if (out->rhslen >= out->rhssz) {
+			out->rhssz *= 2;
+			size_t sz = sizeof(struct cmp_rhs) * out->rhssz;
+			out->rhs = must_realloc(out->rhs, sz);
+		}
+		out->rhs[out->rhslen++] = rhs;
+	}
+
+	return true;
+}
+
+static bool
+parse_equality_e(struct lexer *lexer, struct eq_e *out)
+{
+	if (!parse_comparison_e(lexer, &out->lhs)) {
+		return false;
+	}
+
+	if (match(lexer, T_EQ)) {
+		out->invert = false;
+	} else if (match(lexer, T_NEQ)) {
+		out->invert = true;
+	} else {
+		out->rhs = NULL;
+		return true;
+	}
+
+	out->rhs = must_malloc(sizeof(struct cmp_e));
+	if (!parse_comparison_e(lexer, out->rhs)) {
+		error(lex_loc(lexer), "syntax error: expected comparison");
+	}
+
+	return true;
+}
+
+static bool
+parse_bool_e(struct lexer *lexer, struct bool_e *out)
+{
+	if (parse_equality_e(lexer, &out->cond.eq)) {
+		out->kind = B_EQ;
+		return true;
+	}
+	if (parse_comparison_e(lexer, &out->cond.cmp)) {
+		out->kind = B_CMP;
+		return true;
+	}
+
+	return false;
+}
+
+static bool
+parse_conjunction_e(struct lexer *lexer, struct conjunction_e *out)
+{
+	out->bools = must_calloc(1, sizeof(struct bool_e));
+	out->boolsz = 1;
+	out->boollen = 0;
+
+	struct bool_e b;
+	if (!parse_bool_e(lexer, &b)) {
+		return false;
+	}
+	out->bools[out->boollen++] = b;
+
+	while (match(lexer, T_AND)) {
+		if (!parse_bool_e(lexer, &b)) {
+			error(lex_loc(lexer),
+				"syntax error: expected boolean expression");
+		}
+
+		if (out->boollen >= out->boolsz) {
+			out->boolsz *= 2;
+			size_t sz = sizeof(struct bool_e) * out->boolsz;
+			out->bools = must_realloc(out->bools, sz);
+		}
+		out->bools[out->boollen++] = b;
+	}
+
+	return true;
+}
+
+static bool
+parse_disjunction_e(struct lexer *lexer, struct disjunction_e *out)
+{
+	out->cons = must_calloc(1, sizeof(struct conjunction_e));
+	out->consz = 1;
+	out->conlen = 0;
+
+	struct conjunction_e con;
+	if (!parse_conjunction_e(lexer, &con)) {
+		return false;
+	}
+	out->cons[out->conlen++] = con;
+
+	while (match(lexer, T_OR)) {
+		if (!parse_conjunction_e(lexer, &con)) {
+			error(lex_loc(lexer),
+				"syntax error: expected conjunction");
+		}
+
+		if (out->conlen >= out->consz) {
+			out->consz *= 2;
+			size_t sz = sizeof(struct conjunction_e) * out->consz;
+			out->cons = must_realloc(out->cons, sz);
+		}
+		out->cons[out->conlen++] = con;
+	}
+
+	return true;
+}
+
+static bool
+parse_expr(struct lexer *lexer, struct ast_expr *out)
+{
+	return !parse_disjunction_e(lexer, &out->dis);
+}
+
+static bool
 parse_import(struct lexer *lexer, struct ast_import *out)
 {
 	if (!match(lexer, T_IMPORT)) {