/* zc0: stage 0 of the bootstrap. a small c compiler for the subset of zc that
   compiler.zc is written in. it reads zc source on stdin and writes a genome
   header (vm words placed at GORG) on stdout, in the same image layout the
   resident compiler's image mode produces. no lifetime analysis, no quote, no
   parse words, no block expressions: those only exist in compiler.zc. tags
   (m, d, -> u) and casts (as u, as d) are parsed and recorded in signatures
   but not checked. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define GORG 0xC0000
#define ZFP 0xA0000		/* frame pointer word */
#define FTOP 0xF0000		/* frame stack grows down from here */
#define MAXW 0x40000

enum { T_EOF, T_NUM, T_ID, T_STR, T_OP };
enum { K_FN = 1, K_GVAR, K_GARR, K_CONST, K_KW, K_ENH };
enum { O_Q, O_LD, O_ST, O_PICK, O_DROP, O_SWAP, O_CALL, O_JMP, O_JZ, O_RET,
	O_IN, O_EMPTY, O_OUT, O_ADD, O_SUB, O_MUL, O_AND, O_OR, O_XOR, O_SHR, O_LT };
static const char *mn = "q@!$_~cjzr,?.+-*&|^><%";

static char *src; static int pos, line = 1;
static int tk, tv, glue; static char ts[4096];	/* current token */

static int img[MAXW], here = GORG;
static void emit(int w) { if (here - GORG >= MAXW) { fprintf(stderr, "image too big\n"); exit(1); } img[here++ - GORG] = w; }
static void lit(int v) { emit((int)((unsigned)v * 2 + 1)); }
static void op(int k) { emit(k * 2); }
static void setlit(int at, int v) { img[at - GORG] = (int)((unsigned)v * 2 + 1); }

static void die(const char *m) { fprintf(stderr, "zc0: line %d: %s (at '%s')\n", line, m, ts); exit(1); }

/* ---- lexer ---- */
static const char *ops3[] = { "<<=", ">>=", 0 };
static const char *ops2[] = { "==", "!=", "<=", ">=", "<<", ">>", "&&", "||", "++", "--", "+=", "-=", "*=", "/=", "%=", "&=", "|=", "^=", "->", 0 };
static int esc(void)
{
	int c = src[pos++];
	if (c != '\\') return c;
	c = src[pos++];
	switch (c) { case 'n': return 10; case 't': return 9; case 'r': return 13; case '0': return 0; case 'e': return 27; }
	return c;
}
static void next(void)
{
	int ws = 0, i;
	for (;;) {
		while (src[pos] && isspace((unsigned char)src[pos])) { if (src[pos] == '\n') line++; pos++; ws = 1; }
		if (src[pos] == '/' && src[pos + 1] == '/') { while (src[pos] && src[pos] != '\n') pos++; ws = 1; continue; }
		if (src[pos] == '/' && src[pos + 1] == '*') { pos += 2; while (src[pos] && !(src[pos] == '*' && src[pos + 1] == '/')) { if (src[pos] == '\n') line++; pos++; } if (src[pos]) pos += 2; ws = 1; continue; }
		break;
	}
	glue = !ws;
	if (!src[pos] || src[pos] == '`') { tk = T_EOF; strcpy(ts, "<eof>"); return; }
	if (isdigit((unsigned char)src[pos])) {
		char *e; tv = (int)strtoul(src + pos, &e, 0); memcpy(ts, src + pos, e - src - pos); ts[e - src - pos] = 0; pos = e - src; tk = T_NUM; return;
	}
	if (isalpha((unsigned char)src[pos]) || src[pos] == '_') {
		i = 0; while (isalnum((unsigned char)src[pos]) || src[pos] == '_') ts[i++] = src[pos++];
		ts[i] = 0; tk = T_ID; return;
	}
	if (src[pos] == '\'') { pos++; tv = esc(); if (src[pos++] != '\'') die("bad char literal"); tk = T_NUM; strcpy(ts, "'c'"); return; }
	if (src[pos] == '"') { pos++; i = 0; while (src[pos] && src[pos] != '"') ts[i++] = (char)esc(); ts[i] = 0; pos++; tk = T_STR; return; }
	tk = T_OP;
	for (i = 0; ops3[i]; i++) if (!strncmp(src + pos, ops3[i], 3)) { strcpy(ts, ops3[i]); pos += 3; return; }
	for (i = 0; ops2[i]; i++) if (!strncmp(src + pos, ops2[i], 2)) { strcpy(ts, ops2[i]); pos += 2; return; }
	ts[0] = src[pos++]; ts[1] = 0;
}
static int is(const char *s) { return (tk == T_OP || tk == T_ID) && !strcmp(ts, s); }
static int accept(const char *s) { if (is(s)) { next(); return 1; } return 0; }
static void expect(const char *s) { if (!accept(s)) { char b[64]; sprintf(b, "expected '%s'", s); die(b); } }
static char *ident(void) { static char b[8][256]; static int k; char *r = b[k++ & 7]; if (tk != T_ID) die("expected a name"); strcpy(r, ts); next(); return r; }

/* ---- symbols ---- */
typedef struct { char name[64]; int kind, val, sig, defd; } Sym;
static Sym sy[4096]; static int nsy;
typedef struct { int at, sym; } Fix;
static Fix fx[65536]; static int nfx;
static Sym *find(const char *n) { int i; for (i = nsy; i--;) if (!strcmp(sy[i].name, n)) return &sy[i]; return 0; }
static Sym *add(const char *n, int kind, int val)
{
	Sym *s = find(n);
	if (s && s->kind == K_FN && kind == K_FN && !s->defd) { s->val = val; return s; }	/* prototype or forward use */
	s = &sy[nsy++]; strncpy(s->name, n, 63); s->kind = kind; s->val = val; s->defd = 1; s->sig = 0; return s;
}
static void fnref(const char *n)	/* push a function address, fixing it up later if needed */
{
	Sym *s = find(n);
	if (!s) { s = add(n, K_FN, 0); s->defd = 0; }
	if (s->kind != K_FN) die("not a function");
	if (s->defd) { lit(s->val); return; }
	fx[nfx].at = here; fx[nfx++].sym = (int)(s - sy); lit(0);
}

/* ---- locals ---- */
typedef struct { char name[64]; int slot, arr; } Loc;
static Loc lo[1024]; static int nlo, nslot, infn;
static Loc *findl(const char *n) { int i; for (i = nlo; i--;) if (!strcmp(lo[i].name, n)) return &lo[i]; return 0; }
static void laddr(int k) { lit(ZFP); op(O_LD); if (k) { lit(k); op(O_ADD); } }

/* ---- operator tables ---- */
static void seq_isz(void) { lit(0); op(O_PICK); lit(0); op(O_SWAP); op(O_SUB); op(O_OR); lit(31); op(O_SHR); lit(1); op(O_ADD); }
static void seq_nz(void) { lit(0); op(O_PICK); lit(0); op(O_SWAP); op(O_SUB); op(O_OR); lit(31); op(O_SHR); lit(0); op(O_SWAP); op(O_SUB); }
static int binprec(void)
{
	static const char *n[] = { "*", "/", "%", "+", "-", "<<", ">>", "<", ">", "<=", ">=", "==", "!=", "&", "^", "|", "&&", "||", 0 };
	static int p[] = { 10, 10, 10, 9, 9, 8, 8, 7, 7, 7, 7, 6, 6, 5, 4, 3, 2, 1 };
	int i;
	if (tk != T_OP) return 0;
	for (i = 0; n[i]; i++) if (!strcmp(ts, n[i])) return p[i];
	return 0;
}
static void binop(const char *o)
{
	if (!strcmp(o, "*")) op(O_MUL);
	else if (!strcmp(o, "/")) { fnref("zdiv"); op(O_CALL); }
	else if (!strcmp(o, "%")) { fnref("zmod"); op(O_CALL); }
	else if (!strcmp(o, "+")) op(O_ADD);
	else if (!strcmp(o, "-")) op(O_SUB);
	else if (!strcmp(o, "<<")) { fnref("zshl"); op(O_CALL); }
	else if (!strcmp(o, ">>")) op(O_SHR);
	else if (!strcmp(o, "<")) op(O_LT);
	else if (!strcmp(o, ">")) { op(O_SWAP); op(O_LT); }
	else if (!strcmp(o, "<=")) { op(O_SWAP); op(O_LT); lit(1); op(O_XOR); }
	else if (!strcmp(o, ">=")) { op(O_LT); lit(1); op(O_XOR); }
	else if (!strcmp(o, "==")) { op(O_SUB); seq_isz(); }
	else if (!strcmp(o, "!=")) { op(O_SUB); seq_nz(); }
	else if (!strcmp(o, "&")) op(O_AND);
	else if (!strcmp(o, "^")) op(O_XOR);
	else if (!strcmp(o, "|")) op(O_OR);
	else die("bad operator");
}

/* ---- constant expressions (globals, array sizes, const) ---- */
static int cexpr(void);
static int cprim(void)
{
	int v; Sym *s;
	if (tk == T_NUM) { v = tv; next(); return v; }
	if (accept("-")) return -cprim();
	if (accept("~")) return ~cprim();
	if (accept("(")) { v = cexpr(); expect(")"); return v; }
	if (tk == T_ID && (s = find(ts)) && (s->kind == K_CONST || (s->kind != K_GVAR && s->defd))) { next(); return s->val; }
	die("constant expected"); return 0;
}
static int cexpr(void)
{
	int v = cprim();
	for (;;) {
		if (accept("+")) v += cprim(); else if (accept("-")) v -= cprim();
		else if (accept("*")) v *= cprim(); else if (accept("|")) v |= cprim();
		else if (accept("&")) v &= cprim(); else if (accept("<<")) v <<= cprim();
		else if (accept(">>")) v >>= cprim(); else return v;
	}
}

/* ---- expressions ---- */
static int lv;	/* the stack top is an address not yet loaded */
static void rval(void) { if (lv) { op(O_LD); lv = 0; } }
static void expr(void);
static void strlit(void)	/* inline string: jump over it, push its address */
{
	int j = here, a, i, n = (int)strlen(ts);
	lit(0); op(O_JMP); a = here;
	for (i = 0; i < n; i++) emit((unsigned char)ts[i]);
	emit(0); setlit(j, here); lit(a); next();
}
static int args(void) { int n = 0; expect("("); if (!accept(")")) { do { expr(); rval(); n++; } while (accept(",")); expect(")"); } return n; }
static void asmblock(void);
static void primary(void)
{
	char *n; Loc *l; Sym *s;
	lv = 0;
	if (tk == T_NUM) { lit(tv); next(); return; }
	if (tk == T_STR) { strlit(); return; }
	if (accept("(")) { expr(); expect(")"); return; }
	if (is("asm")) { next(); asmblock(); return; }
	n = ident();
	if ((l = findl(n))) { laddr(l->slot); lv = !l->arr; return; }
	s = find(n);
	if (s && s->kind == K_CONST) { lit(s->val); return; }
	if (s && s->kind == K_GVAR) { lit(s->val); lv = 1; return; }
	if (s && s->kind == K_GARR) { lit(s->val); return; }
	if (is("(")) { args(); fnref(n); op(O_CALL); return; }
	fnref(n);
}
static void incdec(int post, int d)
{
	if (!lv) die("++/-- needs an lvalue");
	lv = 0;
	if (post) { lit(0); op(O_PICK); op(O_LD); lit(0); op(O_PICK); lit(d); op(O_ADD); lit(2); op(O_PICK); op(O_ST); op(O_SWAP); op(O_DROP); }
	else { lit(0); op(O_PICK); op(O_LD); lit(d); op(O_ADD); lit(0); op(O_PICK); lit(2); op(O_PICK); op(O_ST); op(O_SWAP); op(O_DROP); }
}
static void postfix(void)
{
	int n;
	primary();
	for (;;) {
		if (accept("[")) { rval(); expr(); rval(); expect("]"); op(O_ADD); lv = 1; }
		else if (is("(")) { rval(); n = args(); lit(n); op(O_PICK); op(O_CALL); op(O_SWAP); op(O_DROP); }
		else if (accept("++")) incdec(1, 1);
		else if (accept("--")) incdec(1, -1);
		else if (accept("as")) ident();
		else return;
	}
}
static void unary(void)
{
	if (accept("-")) { unary(); rval(); lit(0); op(O_SWAP); op(O_SUB); }
	else if (accept("!")) { unary(); rval(); seq_isz(); }
	else if (accept("~")) { unary(); rval(); lit(-1); op(O_XOR); }
	else if (accept("*")) { unary(); rval(); lv = 1; }
	else if (accept("&")) { unary(); if (!lv) die("& needs an lvalue"); lv = 0; }
	else if (accept("++")) { unary(); incdec(0, 1); }
	else if (accept("--")) { unary(); incdec(0, -1); }
	else if (tk == T_ID && (!strcmp(ts, "u") || !strcmp(ts, "m") || !strcmp(ts, "d"))) { next(); expect("*"); unary(); }	/* u*x: a recast, no code */
	else postfix();
}
static void bin(int minp)
{
	int p, a, b; char o[8];
	unary();
	while ((p = binprec()) && p >= minp) {
		strcpy(o, ts); next(); rval();
		if (!strcmp(o, "&&")) {
			a = here; lit(0); op(O_JZ); bin(p + 1); rval(); seq_nz();
			b = here; lit(0); op(O_JMP); setlit(a, here); lit(0); setlit(b, here);
		} else if (!strcmp(o, "||")) {
			a = here; lit(0); op(O_JZ); lit(1); b = here; lit(0); op(O_JMP);
			setlit(a, here); bin(p + 1); rval(); seq_nz(); setlit(b, here);
		} else { bin(p + 1); rval(); binop(o); }
		lv = 0;
	}
}
static void expr(void)
{
	char o[8];
	bin(1);
	if (is("=")) {
		if (!lv) die("assignment needs an lvalue");
		next(); expr(); rval();
		op(O_SWAP); lit(1); op(O_PICK); op(O_SWAP); op(O_ST); lv = 0;
	} else if (tk == T_OP && strlen(ts) >= 2 && ts[strlen(ts) - 1] == '=' && strcmp(ts, "==") && strcmp(ts, "!=") && strcmp(ts, "<=") && strcmp(ts, ">=")) {
		if (!lv) die("assignment needs an lvalue");
		strcpy(o, ts); o[strlen(o) - 1] = 0; next();
		lit(0); op(O_PICK); op(O_LD); lv = 0; expr(); rval(); binop(o);
		op(O_SWAP); lit(1); op(O_PICK); op(O_SWAP); op(O_ST); lv = 0;
	}
}

/* ---- asm blocks: raw vm words ---- */
static void asmblock(void)
{
	char ln[128][64], rn[256][64]; int la[128], nl = 0, ra[256], nr = 0, i, k; const char *c;
	Loc *l; Sym *s;
	expect("{");
	while (!accept("}")) {
		if (tk == T_EOF) die("unterminated asm");
		if (tk == T_NUM) { lit(tv); next(); continue; }
		if (tk == T_STR) { strlit(); continue; }
		if (accept("#")) { if (tk != T_NUM) die("# needs a number"); emit(tv); next(); continue; }
		if (is("-")) { next(); if (tk == T_NUM && glue) { lit(-tv); next(); } else op(O_SUB); continue; }
		if (accept(":")) { strcpy(ln[nl], ident()); la[nl++] = here; continue; }
		if (strlen(ts) == 1 && (c = strchr(mn, ts[0]))) { op((int)(c - mn)); next(); continue; }
		if (tk != T_ID) die("bad asm token");
		if ((l = findl(ts))) { laddr(l->slot); next(); continue; }
		if ((s = find(ts)) && s->kind != K_FN) { lit(s->val); next(); continue; }
		if (s) { fnref(ts); next(); continue; }
		strcpy(rn[nr], ts); ra[nr++] = here; lit(0); next();	/* a label of this block */
	}
	for (i = 0; i < nr; i++) {
		for (k = -1; ++k < nl && strcmp(ln[k], rn[i]);) ;
		if (k == nl) die("unknown asm label");
		setlit(ra[i], la[k]);
	}
}

/* ---- statements ---- */
static int brk[256][64], nbrk[256], cont[256], nloop;
static int epi[1024], nepi;
static void stmt(void);
static void block(void)
{
	int save = nlo;
	expect("{");
	while (!accept("}")) { if (tk == T_EOF) die("missing }"); stmt(); }
	nlo = save;
}
static void jmp_to(int t) { lit(t); op(O_JMP); }
static void loopbody(int contaddr)
{
	nbrk[nloop] = 0; cont[nloop++] = contaddr;
	stmt();
	nloop--;
}
static void patchbreaks(void) { int i; for (i = 0; i < nbrk[nloop]; i++) setlit(brk[nloop][i], here); }
static void stmt(void)
{
	int a, b, c, d;
	if (accept(";")) return;
	if (is("{")) { block(); return; }
	if (accept("let") || accept("var")) {
		do {
			Loc *l = &lo[nlo++]; strcpy(l->name, ident()); l->arr = 0;
			if (accept("[")) { int n = cexpr(); expect("]"); nslot += n; l->slot = nslot - n; l->arr = 1; }
			else l->slot = nslot++;
			if (accept("=")) { expr(); rval(); laddr(l->slot); op(O_ST); }
		} while (accept(","));
		expect(";"); return;
	}
	if (accept("unchecked")) { stmt(); return; }
	if (accept("if")) {
		expect("("); expr(); rval(); expect(")");
		a = here; lit(0); op(O_JZ); stmt();
		if (accept("else")) { b = here; lit(0); op(O_JMP); setlit(a, here); stmt(); setlit(b, here); }
		else setlit(a, here);
		return;
	}
	if (accept("while")) {
		c = here; expect("("); expr(); rval(); expect(")");
		a = here; lit(0); op(O_JZ);
		loopbody(c); jmp_to(c); setlit(a, here); patchbreaks(); return;
	}
	if (accept("for")) {
		int save = nlo;
		expect("(");
		if (!is(";")) { if (is("let") || is("var")) { stmt(); goto cond; } expr(); rval(); op(O_DROP); }
		expect(";");
	cond:	c = here;
		if (!is(";")) { expr(); rval(); } else lit(1);
		expect(";");
		a = here; lit(0); op(O_JZ); b = here; lit(0); op(O_JMP);
		d = here;
		if (!is(")")) { expr(); rval(); op(O_DROP); }
		expect(")"); jmp_to(c);
		setlit(b, here);
		loopbody(d); jmp_to(d); setlit(a, here); patchbreaks();
		nlo = save; return;
	}
	if (accept("break")) { if (!nloop) die("break outside a loop"); brk[nloop - 1][nbrk[nloop - 1]++] = here; lit(0); op(O_JMP); expect(";"); return; }
	if (accept("continue")) { if (!nloop) die("continue outside a loop"); jmp_to(cont[nloop - 1]); expect(";"); return; }
	if (accept("return")) {
		if (!is(";")) { expr(); rval(); } else lit(0);
		expect(";"); epi[nepi++] = here; lit(0); op(O_JMP); return;
	}
	if (is("asm")) { next(); asmblock(); return; }
	expr(); rval(); op(O_DROP); expect(";");
}

/* ---- top level ---- */
static void fndef(void)
{
	char *n = ident(); Sym *s; int np = 0, tags = 0, t, ret = 0, frame, i;
	char pn[16][64];
	s = find(n);
	if (!s || s->kind != K_FN) { s = add(n, K_FN, 0); s->defd = 0; }
	expect("(");
	if (!accept(")")) {
		do {
			t = 0;
			if (accept(".")) {	/* .m name, .d name */
				if (is("m")) t = 1; else if (is("d")) t = 2; else die("a parameter tag is .m or .d");
				next();
			}
			if (np < 12) tags += t << (2 * np);
			strcpy(pn[np++], ident());
		} while (accept(","));
		expect(")");
	}
	if (accept("->")) { expect("."); if (strcmp(ident(), "u")) die("the return tag is -> .u"); ret = 1; }
	s->sig = ret + 2 * np + 64 * tags;
	if (accept(";")) return;	/* prototype */
	if (s->defd) die("function defined twice");
	s->val = here; s->defd = 1;
	nlo = 0; nslot = 0; nepi = 0; infn = 1;
	for (i = 0; i < np; i++) { strcpy(lo[nlo].name, pn[i]); lo[nlo].arr = 0; lo[nlo++].slot = nslot++; }
	/* prologue: fp -= frame, then pop the arguments into their slots */
	lit(ZFP); op(O_LD); frame = here; lit(0); op(O_SUB); lit(ZFP); op(O_ST);
	for (i = np; i--;) { laddr(i); op(O_ST); }
	block();
	lit(0);
	for (i = 0; i < nepi; i++) setlit(epi[i], here);
	lit(ZFP); op(O_LD); lit(nslot); op(O_ADD); lit(ZFP); op(O_ST); op(O_RET);
	setlit(frame, nslot);
	infn = 0;
}
/* enhance name(params) [-> n] micro "recipe"; or ... vm { asm };
   emits the install descriptor; the booted genome installs it */
static int nenh;
static void enhdef(void)
{
	char *n = ident(), pn[8][64]; int np = 0, nout = 1, d, na, pay, len = 0, i, j; Sym *s;
	expect("(");
	if (!accept(")")) { do { if (np == 8) die("at most 8 inputs"); strcpy(pn[np++], ident()); } while (accept(",")); expect(")"); }
	if (accept("->")) { nout = tv; next(); }
	d = here; for (i = 0; i < 7; i++) emit(0);
	na = here; for (i = 0; i < np; i++) emit(0);
	for (i = 0; i < np; i++) { img[na + i - GORG] = here; for (j = 0; pn[i][j]; j++) emit((unsigned char)pn[i][j]); emit(0); }
	if (accept("micro")) { pay = here; while (tk == T_STR) { for (j = 0; ts[j]; j++) emit((unsigned char)ts[j]); next(); } emit(0); }
	else if (accept("vm")) { pay = here; asmblock(); op(O_RET); len = here - pay; img[d + 1 - GORG] = 1; }
	else die("expected micro or vm");
	img[d - GORG] = nenh; img[d + 2 - GORG] = np; img[d + 3 - GORG] = nout;
	img[d + 4 - GORG] = pay; img[d + 5 - GORG] = len; img[d + 6 - GORG] = na;
	s = add(n, K_ENH, nenh++); s->sig = np + nout * 16 + d * 256;
	expect(";");
}
static void top(void)
{
	while (tk != T_EOF) {
		if (accept("unchecked")) continue;
		if (accept("fn")) { fndef(); continue; }
		if (accept("const")) { do { char *n = ident(); expect("="); add(n, K_CONST, cexpr()); } while (accept(",")); expect(";"); continue; }
		if (accept("enhance")) { enhdef(); continue; }
		if (accept("let") || accept("var")) {
			do {
				char *n = ident();
				if (accept("[")) { int k = cexpr(), a = here; expect("]"); while (k--) emit(0); add(n, K_GARR, a); }
				else {
					int a = here; add(n, K_GVAR, a); emit(0);
					if (accept("=")) {
						if (tk == T_STR) { int i, l = (int)strlen(ts); img[a - GORG] = here; for (i = 0; i < l; i++) emit((unsigned char)ts[i]); emit(0); next(); }
						else img[a - GORG] = cexpr();
					}
				}
			} while (accept(","));
			expect(";"); continue;
		}
		die("expected fn, var or const");
	}
}

int main(void)
{
	static char buf[1 << 22]; int n = (int)fread(buf, 1, sizeof buf - 1, stdin), i, j; Sym *st;
	buf[n] = 0; src = buf; next();
	/* image header: set the frame pointer, jump to start, then the symbol blob pointer and image end */
	lit(FTOP); lit(ZFP); op(O_ST); fnref("start"); op(O_JMP); emit(0); emit(0);
	top();
	for (i = 0; i < nfx; i++) {
		Sym *s = &sy[fx[i].sym];
		if (!s->defd) { fprintf(stderr, "zc0: undefined function %s\n", s->name); return 1; }
		setlit(fx[i].at, s->val);
	}
	if (!(st = find("start")) || !st->defd) { fprintf(stderr, "zc0: no start\n"); return 1; }
	/* symbol blob: kind, value, sig, name chars, 0 ... then a 0 kind */
	img[5] = here;
	for (i = 0; i < nsy; i++) {
		emit(sy[i].kind); emit(sy[i].val); emit(sy[i].sig);
		for (j = 0; sy[i].name[j]; j++) emit((unsigned char)sy[i].name[j]);
		emit(0);
	}
	emit(0);
	img[6] = here;
	printf("#define GORG %d\n#define GLEN %d\nstatic const int genome[] = {", GORG, here - GORG);
	for (i = 0; i < here - GORG; i++) printf("%s%d", !i ? "\n" : i % 16 ? "," : ",\n", img[i]);
	printf("\n};\n");
	return 0;
}