1 files changed, 439 insertions, 0 deletions

diff --git a/docs/history/10-zc/code/zc0.c b/docs/history/10-zc/code/zc0.c
new file mode 100644
index 0000000..23df463
--- /dev/null
+++ b/docs/history/10-zc/code/zc0.c
@@ -0,0 +1,439 @@
+/* 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 };
+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 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("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("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 (tk == T_ID && (!strcmp(ts, "m") || !strcmp(ts, "d"))) {
+				char k = ts[0]; next();
+				if (tk == T_ID) t = k == 'm' ? 1 : 2;
+				else { pn[np][0] = k; pn[np][1] = 0; np++; continue; }	/* a parameter called m or d */
+			}
+			if (np < 12) tags += t << (2 * np);
+			strcpy(pn[np++], ident());
+		} while (accept(","));
+		expect(")");
+	}
+	if (accept("->")) { if (strcmp(ident(), "u")) die("only -> u is a return tag"); 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;
+}
+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("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;
+}