#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 bool parse_array(struct lexer *lexer, struct type *out);
static bool parse_type(struct lexer *lexer, struct type *out);
static bool parse_block(struct lexer *lexer, struct ast_block *out);
static bool parse_control_e(struct lexer *lexer, struct control_e *out);
static bool parse_location(struct lexer *lexer, struct location_e *out);
static bool parse_assignment_e(struct lexer *lexer, struct assign_e *out);

static noreturn void
error(struct location loc, const char *fmt, ...)
{
	fprintf(stderr, "%s:%d:%d ", loc.file, loc.line, loc.column);

	va_list ap;
	va_start(ap, fmt);
	vfprintf(stderr, fmt, ap);
	va_end(ap);

	fprintf(stderr, "\n");
	exit(EXIT_PARSE);
}

static void
append(struct path *path, const char *name)
{
	if (path->seglen >= path->segsz) {
		path->segsz *= 2;
		size_t sz = sizeof(const char *) * path->segsz;
		path->segments = must_realloc(path->segments, sz);
	}

	path->segments[path->seglen++] = name;
}

static bool
parse_path(struct lexer *lexer, struct path *out)
{
	struct token name;

	if (lex(lexer, &name) != T_NAME) {
		unlex(lexer, &name);
		return false;
	}

	out->segments = must_calloc(1, sizeof(const char *));
	out->segments[0] = name.info.str;
	out->seglen = 1;
	out->segsz = 1;

	while (match(lexer, T_MODDELIM)) {
		if (lex(lexer, &name) != T_NAME) {
			error(name.loc, "syntax error: expected name");
		}
		append(out, name.info.str);
	}

	return true;
}

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_bool_lit(struct lexer *lexer, bool *out)
{
	if (match(lexer, T_TRUE)) {
		*out = true;
	} else if (match(lexer, T_FALSE)) {
		*out = false;
	} else {
		return false;
	}

	return true;
}

static bool
parse_string(struct lexer *lexer, char **out)
{
	*out = NULL;

	struct token s;
	bool isstr = false;
	while (lex(lexer, &s) == T_STRING) {
		if (*out) {
			size_t sz = strlen(*out) + strlen(s.info.str) + 1;
			*out = must_realloc(*out, sz);
		} else {
			*out = strdup(s.info.str);
		}

		isstr = true;
	}
	unlex(lexer, &s);

	return isstr;
}

static bool
parse_number_e(struct lexer *lexer, struct number_e *out)
{
	struct token num;
	if (lex(lexer, &num) != T_NUMBER) {
		unlex(lexer, &num);
		return false;
	}
	out->value = num.info.num;

	out->type = must_malloc(sizeof(struct type));
	if (!parse_type(lexer, out->type)) {
		error(lex_loc(lexer), "syntax error: expected type");
	}

	return true;
}

static bool
parse_array_e(struct lexer *lexer, struct array_e *out)
{
	struct type type;
	if (!parse_array(lexer, &type)) {
		return false;
	}
	out->meta = must_malloc(sizeof(struct cer_array));
	*out->meta = type.desc.array;

	out->elems = must_calloc(1, sizeof(struct disjunction_e));
	out->elemsz = 1;
	out->elemlen = 0;

	struct disjunction_e elem;
	while (parse_disjunction_e(lexer, &elem)) {
		if (out->elemlen >= out->elemsz) {
			out->elemsz *= 2;
			size_t sz = sizeof(struct disjunction_e) * out->elemsz;
			out->elems = must_realloc(out->elems, sz);
		}
		out->elems[out->elemlen++] = elem;
	}

	return true;
}

static bool
parse_literal_e(struct lexer *lexer, struct literal_e *out)
{
	if (parse_bool_lit(lexer, &out->lit.b)) {
		out->kind = LIT_BOOL;
		return true;
	}
	if (parse_string(lexer, &out->lit.str)) {
		out->kind = LIT_STRING;
		return true;
	}
	if (parse_number_e(lexer, &out->lit.num)) {
		out->kind = LIT_NUMBER;
		return true;
	}
	if (parse_array_e(lexer, &out->lit.arr)) {
		out->kind = LIT_ARRAY;
		return true;
	}

	return false;
}

// Invariant: Only called from parse_primary_e with path already consumed.
static bool
parse_call_e(struct lexer *lexer, struct call_e *out, struct location_e *loc)
{
	if (!match(lexer, T_LPAREN)) {
		return false;
	}

	out->loc = loc;

	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_named_e(struct lexer *lexer, struct named_e *out)
{
	if (!parse_location(lexer, &out->loc)) {
		return false;
	}

	if (parse_assignment_e(lexer, &out->nmd.assign)) {
		out->kind = NMD_ASSIGN;
		return true;
	}
	if (parse_call_e(lexer, &out->nmd.call, &out->loc)) {
		out->kind = NMD_CALL;
		return true;
	}

	out->kind = NMD_LOCATION;
	return true;
}

static bool
parse_primary_e(struct lexer *lexer, struct primary_e *out)
{
	if (parse_control_e(lexer, &out->prim.ctl)) {
		out->kind = PRM_CONTROL;
		return true;
	}
	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_named_e(lexer, &out->prim.nmd)) {
		out->kind = PRM_NAMED;
		return true;
	}

	return false;
}

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;
	}

	bool post_ok = parse_unarypost_e(lexer, &out->post);
	if (!post_ok) {
		if (out->op == UPR_NONE) {
			return false;
		}

		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_integer(struct lexer *lexer, struct type *out)
{
	struct token token;
	switch(lex(lexer, &token)) {
	case T_INT8:
		out->kind = TYP_INT;
		out->desc.i.sign = true;
		out->desc.i.bits = 8;
		return true;
	case T_UINT8:
		out->kind = TYP_INT;
		out->desc.i.sign = false;
		out->desc.i.bits = 8;
		return true;
	case T_INT16:
		out->kind = TYP_INT;
		out->desc.i.sign = true;
		out->desc.i.bits = 16;
		return true;
	case T_UINT16:
		out->kind = TYP_INT;
		out->desc.i.sign = false;
		out->desc.i.bits = 16;
		return true;
	case T_INT32:
		out->kind = TYP_INT;
		out->desc.i.sign = true;
		out->desc.i.bits = 32;
		return true;
	case T_UINT32:
		out->kind = TYP_INT;
		out->desc.i.sign = false;
		out->desc.i.bits = 32;
		return true;
	case T_INT64:
		out->kind = TYP_INT;
		out->desc.i.sign = true;
		out->desc.i.bits = 64;
		return true;
	case T_UINT64:
		out->kind = TYP_INT;
		out->desc.i.sign = false;
		out->desc.i.bits = 64;
		return true;
	case T_INT:
		out->kind = TYP_INT;
		out->desc.i.sign = true;
		out->desc.i.bits = PLATBITS;
		return true;
	case T_UINT:
		out->kind = TYP_INT;
		out->desc.i.sign = false;
		out->desc.i.bits = PLATBITS;
		return true;
	default:
		unlex(lexer, &token);
		return false;
	}
}

static bool
parse_float(struct lexer *lexer, struct type *out)
{
	struct token token;
	switch (lex(lexer, &token)) {
	case T_FLOAT32:
		out->kind = TYP_FLOAT;
		out->desc.f.is64 = false;
		return true;
	case T_FLOAT64:
		out->kind = TYP_FLOAT;
		out->desc.f.is64 = true;
	default:
		unlex(lexer, &token);
		return false;
	}
}

static bool
parse_field(struct lexer *lexer, struct field *out)
{
	struct token name;
	if (lex(lexer, &name) != T_NAME) {
		unlex(lexer, &name);
		return false;
	}
	out->name = name.info.str;

	struct type *type = must_malloc(sizeof(struct type));
	if (!parse_type(lexer, type)) {
		error(lex_loc(lexer), "syntax error: expected type");
	}
	out->type = type;

	return true;
}

static bool
parse_struct(struct lexer *lexer, struct type *out)
{
	if (!match(lexer, T_STRUCT)) {
		return false;
	}
	if (!match(lexer, T_LBRACE)) {
		error(lex_loc(lexer), "syntax error: expected '{'");
	}

	out->kind = TYP_STRUCT;
	out->desc.s.fields = must_calloc(1, sizeof(struct field));
	out->desc.s.fieldsz = 1;
	out->desc.s.fieldlen = 0;

	struct field field;
	while (parse_field(lexer, &field)) {
		if (out->desc.s.fieldlen >= out->desc.s.fieldsz) {
			out->desc.s.fieldsz *= 2;
			size_t sz = sizeof(struct field) * out->desc.s.fieldsz;
			out->desc.s.fields = must_realloc(out->desc.s.fields,
				sz);
		}
		out->desc.s.fields[out->desc.s.fieldlen++] = field;

		if (!match(lexer, T_COMMA)) {
			break;
		}
	}

	if (!match(lexer, T_RBRACE)) {
		error(lex_loc(lexer), "syntax error: expected '}'");
	}

	return true;
}

static bool parse_union(struct lexer *lexer, struct type *out)
{
	if (!match(lexer, T_UNION)) {
		return false;
	}

	out->desc.un.tag_type = NULL;
	if (match(lexer, T_LPAREN)) {
		out->desc.un.tag_type = must_malloc(sizeof(struct type));
		if (!parse_type(lexer, out->desc.un.tag_type)) {
			error(lex_loc(lexer), "syntax error: expected type");
		}

		if (!match(lexer, T_RPAREN)) {
			error(lex_loc(lexer), "syntax error: expected ')'");
		}
	}

	if (!match(lexer, T_LBRACE)) {
		error(lex_loc(lexer), "syntax error: expected '{'");
	}

	out->kind = TYP_UNION;
	out->desc.un.alts = must_calloc(1, sizeof(struct type));
	out->desc.un.altsz = 1;
	out->desc.un.altlen = 0;

	struct type alt;
	while (parse_type(lexer, &alt)) {
		if (out->desc.un.altlen >= out->desc.un.altsz) {
			out->desc.un.altsz *= 2;
			size_t sz = sizeof(struct type) * out->desc.un.altsz;
			out->desc.un.alts = must_realloc(out->desc.un.alts, sz);
		}
		out->desc.un.alts[out->desc.un.altlen++] = alt;

		if (!match(lexer, T_COMMA)) {
			break;
		}
	}

	if (!match(lexer, T_RBRACE)) {
		error(lex_loc(lexer), "syntax error: expected '}'");
	}

	return true;
}

static bool
parse_array(struct lexer *lexer, struct type *out)
{
	if (!match(lexer, T_LBRACKET)) {
		return false;
	}

	out->kind = TYP_ARRAY;

	out->desc.array.length = must_malloc(sizeof(struct disjunction_e));
	if (!parse_disjunction_e(lexer, out->desc.array.length)) {
		out->kind = TYP_SLICE;
	}

	if (!match(lexer, T_RBRACKET)) {
		error(lex_loc(lexer), "syntax error: expected ']'");
	}

	struct type *type = must_malloc(sizeof(struct type));
	if (!parse_type(lexer, type)) {
		error(lex_loc(lexer), "syntax error: expected type");
	}
	out->desc.array.member_type = type;

	return true;
}

static bool
parse_type(struct lexer *lexer, struct type *out)
{
	struct token token;
	switch (lex(lexer, &token)) {
	case T_STAR:
		out->kind = TYP_POINTER;
		out->desc.inner = must_malloc(sizeof(struct type));

		if (!parse_type(lexer, out->desc.inner)) {
			error(lex_loc(lexer), "syntax error: expected type");
		}
		return true;
	case T_QUESTION:
		out->kind = TYP_OPTIONAL;
		out->desc.inner = must_malloc(sizeof(struct type));

		if (!parse_type(lexer, out->desc.inner)) {
			error(lex_loc(lexer), "syntax error: expected type");
		}
		return true;
	case T_BANG:
		out->kind = TYP_FALLIBLE;
		out->desc.inner = must_malloc(sizeof(struct type));

		if (!parse_type(lexer, out->desc.inner)) {
			error(lex_loc(lexer), "syntax error: expected type");
		}
		return true;
	case T_BOOL:
		out->kind = TYP_BOOL;
		return true;
	}
	unlex(lexer, &token);

	if (parse_integer(lexer, out)) {
		return true;
	}
	if (parse_float(lexer, out)) {
		return true;
	}
	if (parse_struct(lexer, out)) {
		return true;
	}
	if (parse_union(lexer, out)) {
		return true;
	}
	if (parse_array(lexer, out)) {
		return true;
	}

	struct path path;
	if (parse_path(lexer, &path)) {
		out->kind = TYP_PATH;
		out->desc.path = path;
		return true;
	}

	return false;
}

static bool
parse_externfunc(struct lexer *lexer, struct ast_externfunc *out)
{
	out->params = must_calloc(1, sizeof(struct type));
	out->paramsz = 1;
	out->paramlen = 0;

	if (!match(lexer, T_EXTERN)) {
		return false;
	}
	if (!match(lexer, T_FUNC)) {
		error(lex_loc(lexer), "syntax error: expected keyword 'func'");
	}

	struct token name;
	if (lex(lexer, &name) != T_NAME) {
		error(lex_loc(lexer), "syntax error: expected name");
	}
	out->name = name.info.str;

	if (!match(lexer, T_LPAREN)) {
		error(lex_loc(lexer), "syntax error: expected '('");
	}

	struct type paramtype;
	while (parse_type(lexer, &paramtype)) {
		if (out->paramlen >= out->paramsz) {
			out->paramsz *= 2;
			size_t sz = sizeof(struct type) * out->paramsz;
			out->params = must_realloc(out->params, sz);
		}
		out->params[out->paramlen++] = paramtype;

		if (!match(lexer, T_COMMA)) {
			break;
		}
	}

	if (!match(lexer, T_RPAREN)) {
		error(lex_loc(lexer), "syntax error: expected ')'");
	}

	bool nonvoid = parse_type(lexer, &out->ret);

	if (!match(lexer, T_SEMICOLON)) {
		error(lex_loc(lexer), "syntax error: expected semicolon");
	}

	return true;
}

static bool
parse_return(struct lexer *lexer, struct ast_return *out)
{
	if (!match(lexer, T_RETURN)) {
		return false;
	}

	out->value = must_malloc(sizeof(struct ast_expr));
	if (!parse_expr(lexer, out->value)) {
		free(out->value);
		out->value = NULL;
	}

	return true;
}

static bool
parse_break(struct lexer *lexer, struct ast_break *out)
{
	if (!match(lexer, T_BREAK)) {
		return false;
	}

	if (!match(lexer, T_COLON)) {
		out->label = NULL;
		return true;
	}

	struct token label;
	if (lex(lexer, &label) != T_NAME) {
		error(lex_loc(lexer), "syntax error: expected name");
	}
	out->label = label.info.str;

	out->value = must_malloc(sizeof(struct ast_expr));
	if (!parse_expr(lexer, out->value)) {
		free(out->value);
		out->value = NULL;
	}

	return true;
}

static bool
parse_continue(struct lexer *lexer, struct ast_break *out)
{
	if (!match(lexer, T_CONTINUE)) {
		return false;
	}

	if (!match(lexer, T_COLON)) {
		out->label = NULL;
		return true;
	}

	struct token label;
	if (lex(lexer, &label) != T_NAME) {
		error(lex_loc(lexer), "syntax error: expected name");
	}
	out->label = label.info.str;

	out->value = NULL;
	return true;
}

static bool
parse_declaration(struct lexer *lexer, struct ast_declaration *out)
{
	if (!match(lexer, T_LET)) {
		return false;
	}

	out->mut = false;

	struct token name;
	if (lex(lexer, &name) != T_NAME) {
		error(lex_loc(lexer), "syntax error: expected name");
	}
	out->name = name.info.str;

	if (!match(lexer, T_ASSIGN)) {
		error(lex_loc(lexer), "syntax error: expected '='");
	}

	out->value = must_malloc(sizeof(struct ast_expr));
	if (!parse_expr(lexer, out->value)) {
		error(lex_loc(lexer), "syntax error: expected expression");
	}

	return true;
}

static bool
parse_subindex(struct lexer *lexer, struct ast_expr *out)
{
	if (!match(lexer, T_LBRACKET)) {
		return false;
	}

	if (!parse_expr(lexer, out)) {
		error(lex_loc(lexer), "syntax error: expected expression");
	}

	if (!match(lexer, T_RBRACKET)) {
		error(lex_loc(lexer), "syntax error: expected ']'");
	}

	return true;
}

static bool
parse_subfield(struct lexer *lexer, const char **out)
{
	if (!match(lexer, T_DOT)) {
		return false;
	}

	struct token name;
	if (lex(lexer, &name) != T_NAME) {
		error(lex_loc(lexer), "syntax error: expected name");
	}
	*out = name.info.str;

	return true;
}

static bool
parse_loc_postfix(struct lexer *lexer, struct loc_postfix *out)
{
	if (parse_subindex(lexer, &out->id.index)) {
		out->sub = SUB_INDEX;
		return true;
	}
	if (parse_subfield(lexer, &out->id.field)) {
		out->sub = SUB_FIELD;
		return true;
	}

	return false;
}

static bool
parse_location(struct lexer *lexer, struct location_e *out)
{
	out->path = must_malloc(sizeof(struct path));
	if (!parse_path(lexer, out->path)) {
		free(out->path);
		return false;
	}

	out->subs = must_calloc(1, sizeof(struct loc_postfix));
	out->subsz = 1;
	out->sublen = 0;

	struct loc_postfix sub;
	while (parse_loc_postfix(lexer, &sub)) {
		if (out->sublen >= out->subsz) {
			out->subsz *= 2;
			size_t sz = sizeof(struct loc_postfix) * out->subsz;
			out->subs = must_realloc(out->subs, sz);
		}
		out->subs[out->sublen++] = sub;
	}

	return true;
}

static bool
parse_assignment_e(struct lexer *lexer, struct assign_e *out)
{
	if (!parse_location(lexer, &out->dst)) {
		return false;
	}

	if (!match(lexer, T_ASSIGN)) {
		error(lex_loc(lexer), "syntax error: expected '='");
	}

	out->value = must_malloc(sizeof(struct ast_expr));
	if (!parse_expr(lexer, out->value)) {
		error(lex_loc(lexer), "syntax error: expected expression");
	}

	return true;
}

static bool
parse_call(struct lexer *lexer, struct call_e *out)
{
	/* TODO */
	return false;
}

static bool
parse_defer(struct lexer *lexer, struct call_e *out)
{
	if (!match(lexer, T_DEFER)) {
		return false;
	}

	struct location_e *loc = must_malloc(sizeof(struct location_e));
	if (!parse_location(lexer, loc)) {
		error(lex_loc(lexer), "syntax error: expected path");
	}

	if (!parse_call_e(lexer, out, loc)) {
		error(lex_loc(lexer), "syntax error: expected call");
	}

	return true;
}

static bool
parse_statement(struct lexer *lexer, struct ast_statement *out)
{
	if (parse_return(lexer, &out->stmt.ret)) {
		out->action = STM_RETURN;
		if (!match(lexer, T_SEMICOLON)) {
			error(lex_loc(lexer), "syntax error: expected semicolon");
		}
		return true;
	}
	if (parse_break(lexer, &out->stmt.brk)) {
		out->action = STM_BREAK;
		if (!match(lexer, T_SEMICOLON)) {
			error(lex_loc(lexer), "syntax error: expected semicolon");
		}
		return true;
	}
	if (parse_continue(lexer, &out->stmt.brk)) {
		out->action = STM_CONTINUE;
		if (!match(lexer, T_SEMICOLON)) {
			error(lex_loc(lexer), "syntax error: expected semicolon");
		}
		return true;
	}
	if (parse_declaration(lexer, &out->stmt.decl)) {
		out->action = STM_DECL;
		if (!match(lexer, T_SEMICOLON)) {
			error(lex_loc(lexer), "syntax error: expected semicolon");
		}
		return true;
	}
	out->stmt.call = must_malloc(sizeof(struct call_e));
	if (parse_defer(lexer, out->stmt.call)) {
		out->action = STM_DEFER;
		if (!match(lexer, T_SEMICOLON)) {
			error(lex_loc(lexer), "syntax error: expected semicolon");
		}
		return true;
	}
	free(out->stmt.call);

	return false;
}

static bool
parse_control_e(struct lexer *lexer, struct control_e *out)
{
	/* TODO */
	return false;
}

static bool
parse_command(struct lexer *lexer, struct ast_cmd *out)
{
	if (parse_block(lexer, &out->cmd.blk)) {
		out->kind = CMD_BLOCK;
		return true;
	}
	if (parse_statement(lexer, &out->cmd.stmt)) {
		out->kind = CMD_STATEMENT;
		return true;
	}

	return false;
}

static bool
parse_block(struct lexer *lexer, struct ast_block *out)
{
	if (!match(lexer, T_LBRACE)) {
		return false;
	}

	out->cmds = must_calloc(1, sizeof(struct ast_cmd));
	out->cmdsz = 1;
	out->cmdlen = 0;

	struct ast_cmd cmd;
	while (parse_command(lexer, &cmd)) {
		if (out->cmdlen >= out->cmdsz) {
			out->cmdsz *= 2;
			size_t sz = sizeof(struct ast_cmd) * out->cmdsz;
			out->cmds = must_realloc(out->cmds, sz);
		}
		out->cmds[out->cmdlen++] = cmd;
	}

	if (!match(lexer, T_RBRACE)) {
		error(lex_loc(lexer), "syntax error: expected '}'");
	}

	return true;
}

static bool
parse_param(struct lexer *lexer, struct ast_param *out)
{
	struct token name;
	if (lex(lexer, &name) != T_NAME) {
		unlex(lexer, &name);
		return false;
	}
	out->name = name.info.str;

	if (!parse_type(lexer, &out->type)) {
		error(lex_loc(lexer), "syntax error: expected type");
	}

	return true;
}

static bool
parse_function(struct lexer *lexer, struct ast_func *out)
{
	out->params = must_calloc(1, sizeof(struct ast_param));
	out->paramsz = 1;
	out->paramlen = 0;

	if (!match(lexer, T_FUNC)) {
		if (out->exported) {
			error(lex_loc(lexer),
				"syntax error: expected keyword 'func'");
		}
		return false;
	}

	struct token name;
	if (lex(lexer, &name) != T_NAME) {
		error(lex_loc(lexer), "syntax error: expected name");
	}
	out->name = name.info.str;

	if (!match(lexer, T_LPAREN)) {
		error(lex_loc(lexer), "syntax error: expected '('");
	}

	struct ast_param param;
	while (parse_param(lexer, &param)) {
		if (out->paramlen >= out->paramsz) {
			out->paramsz *= 2;
			size_t sz = sizeof(struct ast_param) * out->paramsz;
			out->params = must_realloc(out->params, sz);
		}
		out->params[out->paramlen++] = param;

		if (!match(lexer, T_COMMA)) {
			break;
		}
	}

	if (!match(lexer, T_RPAREN)) {
		error(lex_loc(lexer), "syntax error: expected ')'");
	}

	out->ret = must_malloc(sizeof(struct type));
	bool nonvoid = parse_type(lexer, out->ret);

	out->block = must_malloc(sizeof(struct ast_block));
	if (!parse_block(lexer, out->block)) {
		error(lex_loc(lexer), "syntax error: expected block");
	}

	return true;
}

static bool
parse_bool(struct lexer *lexer, bool *out)
{
	struct token token;
	switch (lex(lexer, &token)) {
	case T_FALSE:
		*out = false;
		return true;
	case T_TRUE:
		*out = true;
		return true;
	default:
		unlex(lexer, &token);
		return false;
	}
}

static bool
parse_const_global(struct lexer *lexer, struct ast_const_global *out)
{
	if (!match(lexer, T_CONST)) {
		return false;
	}

	struct token name;
	if (lex(lexer, &name) != T_NAME) {
		error(lex_loc(lexer), "syntax error: expected name");
	}
	out->name = name.info.str;

	if (!match(lexer, T_ASSIGN)) {
		error(lex_loc(lexer), "syntax error: expected '='");
	}

	struct token token;
	if (lex(lexer, &token) == T_NUMBER) {
		if (!match(lexer, T_SEMICOLON)) {
			error(lex_loc(lexer),
				"syntax error: expected semicolon");
		}

		out->kind = CST_NUMBER;
		out->value.num = token.info.num;
		return true;
	}
	unlex(lexer, &token);

	if (parse_bool(lexer, &out->value.b)) {
		if (!match(lexer, T_SEMICOLON)) {
			error(lex_loc(lexer),
				"syntax error: expected semicolon");
		}

		out->kind = CST_BOOL;
		return true;
	}

	bool isstr = false;
	out->value.str = must_malloc(1);
	memset(out->value.str, 0, 1);
	while (lex(lexer, &token) == T_STRING) {
		size_t sz = strlen(out->value.str) + strlen(token.info.str) + 1;
		out->value.str = must_realloc(out->value.str, sz);
		strcat(out->value.str, token.info.str);
		isstr = true;
	}
	unlex(lexer, &token);

	if (isstr) {
		if (!match(lexer, T_SEMICOLON)) {
			error(lex_loc(lexer),
				"syntax error: expected semicolon");
		}

		out->kind = CST_STRING;
		return true;
	}

	if (parse_type(lexer, &out->value.type)) {
		if (!match(lexer, T_SEMICOLON)) {
			error(lex_loc(lexer),
				"syntax error: expected semicolon");
		}

		out->kind = CST_TYPE;
		return true;
	}

	error(lex_loc(lexer),
			"syntax error: expected number, bool, string or type");
}

static bool
parse_toplevel(struct lexer *lexer, struct ast_toplevel *out)
{
	struct ast_externfunc *extfn =
			must_malloc(sizeof(struct ast_externfunc));
	if (parse_externfunc(lexer, extfn)) {
		out->kind = TOP_EXTERNFUNC;
		out->decl.extfn = extfn;
		return true;
	}
	free(extfn);

	struct ast_func *func = must_malloc(sizeof(struct ast_func));
	if (parse_function(lexer, func)) {
		out->kind = TOP_FUNC;
		out->decl.function = func;
		return true;
	}
	free(func);

	struct ast_const_global *c =
			must_malloc(sizeof(struct ast_const_global));
	if (parse_const_global(lexer, c)) {
		out->kind = TOP_CONST;
		out->decl.constant = c;
		return true;
	}
	free(c);

	if (!match(lexer, T_EOF)) {
		error(lex_loc(lexer),
				"syntax error: expected top-level declaration");
	}

	return false;
}

void
parse(struct lexer *lexer, struct ast_unit *ast)
{
	ast->imports = must_calloc(1, sizeof(struct ast_import));
	ast->tops = must_calloc(1, sizeof(struct ast_toplevel));
	ast->impsz = 1;
	ast->implen = 0;
	ast->topsz = 1;
	ast->toplen = 0;

	struct ast_toplevel top;
	while (parse_toplevel(lexer, &top)) {
		if (ast->toplen >= ast->topsz) {
			ast->topsz *= 2;
			size_t sz = sizeof(struct ast_toplevel) * ast->topsz;
			ast->tops = must_realloc(ast->tops, sz);
		}
		ast->tops[ast->toplen++] = top;
	}
}