#include "sl.h"
#include "operators.h"
#include "cvalues.h"
#include "types.h"
#include "print.h"
#include "read.h"
#include "timefuncs.h"
#include "equal.h"
#include "hashing.h"
#include "table.h"
#include "io.h"
#include "compress.h"
#include "slmath.h"
#include "str.h"

sl_v sl_builtinssym, sl_quote, sl_lambda, sl_comma, sl_commaat;
sl_v sl_commadot, sl_trycatch, sl_backquote;
sl_v sl_conssym, sl_symsym, sl_fixnumsym, sl_vecsym, sl_builtinsym, sl_vu8sym;
sl_v sl_defsym, sl_defmacrosym, sl_forsym, sl_setqsym, sl_listsym;
sl_v sl_boolsym, sl_nullsym, sl_evalsym, sl_fnsym, sl_trimsym, sl_strsym;
sl_v sl_errio, sl_errparse, sl_errtype, sl_errarg, sl_errmem, sl_errconst;
sl_v sl_errdiv0, sl_errbounds, sl_err, sl_errkey, sl_errunbound, sl_erroom;
sl_v sl_emptyvec, sl_emptystr, sl_vecstructsym, sl_structsym;

static sl_v sl_errarity;

sl_v sl_tablesym, sl_arrsym;
sl_v sl_s8sym, sl_u8sym, sl_s16sym, sl_u16sym, sl_s32sym, sl_u32sym;
sl_v sl_s64sym, sl_u64sym, sl_p32sym, sl_p64sym, sl_ptrsym, sl_bignumsym;
sl_v sl_utf8sym, sl_runesym, sl_f32sym, sl_f64sym;

sl_type *sl_bignumtype, *sl_builtintype;
sl_type *sl_s8type, *sl_u8type;
sl_type *sl_s16type, *sl_u16type;
sl_type *sl_s32type, *sl_u32type;
sl_type *sl_s64type, *sl_u64type;
sl_type *sl_p32type, *sl_p64type;
sl_type *sl_f32type, *sl_f64type;
sl_type *sl_utf8type, *sl_runetype;
sl_type *sl_strtype;

sl_thread(sl_proc *slp);
sl_vm slvm_ = {0};

typedef struct {
	const char *name;
	sl_builtinfn fptr;
}sl_builtinspec;

bool
isbuiltin(sl_v x)
{
	int i;
	return tag(x) == TAG_FN && (i = uintval(x)) < nelem(builtins) && builtins[i].name != nil;
}

static sl_v apply_cl(int nargs) sl_hotfn;

// error utilities ------------------------------------------------------------

void
free_readstate(sl_readstate *rs)
{
	htable_free(&rs->backrefs);
	htable_free(&rs->gensyms);
}

_Noreturn void
sl_exit(const char *status)
{
	if(!slvm.exiting){
		slvm.exiting = true;
		sl_applyn(
			1,
			sym_value(mk_sym("__finish", false)),
			status == nil ? sl_nil : cvalue_static_cstr(status)
		);
		sl_gc(false);
	}
	exits(status);
}

#define SL_TRY \
	sl_exctx _ctx; int l__tr, l__ca; \
	_ctx.osp = sl.sp - sl.stack; _ctx.frame = sl.curr_frame; \
	_ctx.rdst = sl.readstate; _ctx.prev = sl.exctx; \
	_ctx.ngchnd = slvm.ngchandles; sl.exctx = &_ctx; \
	if(!sl_setjmp(_ctx.buf)) \
		for(l__tr = 1; l__tr; l__tr = 0, (void)(sl.exctx = sl.exctx->prev))

#define SL_CATCH_INC \
	l__ca = 0, sl.lasterror = sl_nil, sl.throwing_frame = 0, \
	sl.sp = sl.stack + _ctx.osp, sl.curr_frame = _ctx.frame

#define SL_CATCH \
	else \
		for(l__ca = 1; l__ca; SL_CATCH_INC)

#define SL_CATCH_NO_INC \
	else \
		for(l__ca = 1; l__ca;)

void
sl_savestate(sl_exctx *_ctx)
{
	_ctx->osp = sl.sp - sl.stack;
	_ctx->frame = sl.curr_frame;
	_ctx->rdst = sl.readstate;
	_ctx->prev = sl.exctx;
	_ctx->ngchnd = slvm.ngchandles;
}

void
sl_restorestate(sl_exctx *_ctx)
{
	sl.lasterror = sl_nil;
	sl.throwing_frame = 0;
	sl.sp = sl.stack + _ctx->osp;
	sl.curr_frame = _ctx->frame;
}

static sl_v
mk_loc(sl_v io, ios_loc *l)
{
	return mk_listn(3, io, fixnum(l->lineno), fixnum(l->colno));
}

_Noreturn void
sl_raise(sl_v e)
{
	ios_flush(ios_stdout);
	ios_flush(ios_stderr);

	if(sl.readstate != sl.exctx->rdst){
		sl_gc_handle(&e);
		e = mk_cons(mk_loc(sl.readstate->source, &sl.readstate->errloc), e);
		sl_free_gc_handles(1);
	}

	sl.lasterror = e;
	// unwind read state
	while(sl.readstate != sl.exctx->rdst){
		free_readstate(sl.readstate);
		sl.readstate = sl.readstate->prev;
	}
	if(sl.throwing_frame == 0)
		sl.throwing_frame = sl.curr_frame;
	slvm.ngchandles = sl.exctx->ngchnd;
	sl_exctx *thisctx = sl.exctx;
	if(sl.exctx->prev)   // don't throw past toplevel
		sl.exctx = sl.exctx->prev;
	sl_longjmp(thisctx->buf, 1);
}

_Noreturn void
lerrorf(sl_v e, const char *format, ...)
{
	char msgbuf[256];
	va_list args;

	PUSH(e);
	va_start(args, format);
	vsnprintf(msgbuf, sizeof(msgbuf), format, args);
	sl_v msg = str_from_cstr(msgbuf);
	va_end(args);

	e = POP();
	sl_raise(mk_list2(e, msg));
}

_Noreturn void
type_error(const char *what, const char *expected, sl_v got)
{
	if(what == nil)
		sl_raise(mk_listn(3, sl_errtype, mk_sym(expected, false), got));
	sl_raise(mk_listn(4, sl_errtype, mk_sym(expected, false), got, mk_sym(what, false)));
}

_Noreturn void
bounds_error(sl_v arr, sl_v ind)
{
	sl_raise(mk_listn(3, sl_errbounds, arr, ind));
}

_Noreturn void
const_error(sl_v sym)
{
	sl_raise(mk_list2(sl_errconst, sym));
}

_Noreturn void
unbound_error(sl_v sym)
{
	sl_raise(mk_listn(2, sl_errunbound, sym));
}

_Noreturn void
arity_error(int nargs, int c)
{
	sl_raise(mk_listn(3, sl_errarity, size_wrap(c), size_wrap(nargs)));
}

// safe cast operators --------------------------------------------------------

#define SAFECAST_OP(type, ctype, cnvt) \
	ctype to##type(sl_v v) \
	{ \
		if(sl_likely(is##type(v))) \
			return (ctype)cnvt(v); \
		cthrow(type_error("value", #type, v), v); \
	}
SAFECAST_OP(cons, sl_cons*, ptr)
SAFECAST_OP(sym, sl_sym*, ptr)
SAFECAST_OP(fixnum, sl_fx, numval)
//SAFECAST_OP(cvalue, sl_cv*, ptr)
SAFECAST_OP(str, char*, cvalue_data)

// symbol table ---------------------------------------------------------------

static sl_sym *
alloc_sym(const char *str, int len, bool copy)
{
	sl_sym *sym = MEM_ALLOC(sizeof(*sym) + (copy ? len+1 : 0));
	sym->numtype = NONNUMERIC;
	if(str[0] == ':' && str[1] != 0){
		sl_v s = tagptr(sym, TAG_SYM);
		sym->flags = FLAG_KEYWORD;
		setc(s, s);
	}else{
		sym->binding = sl_unbound;
		sym->flags = 0;
	}
	sym->type = nil;
	sym->hash = memhash32(str, len)^0xAAAAAAAAU; // sing along
	if(copy){
		memcpy((char*)(sym+1), str, len+1);
		sym->name = (const char*)(sym+1);
	}else{
		sym->name = str;
	}
	sym->size = 0;
	return sym;
}

sl_v
mk_sym(const char *str, bool copy)
{
	int len = strlen(str);
	sl_sym *v;
	const char *k;
	if(!Tgetkv(slvm.symbols, str, len, &k, (void**)&v)){
		v = alloc_sym(str, len, copy);
		slvm.symbols = Tsetl(slvm.symbols, v->name, len, v);
	}
	if(v->binding == sl_lambda)
		return sl_lambda;
	return tagptr(v, TAG_SYM);
}

sl_v
mk_csym_(const char *str, int len)
{
	sl_sym *v = alloc_sym(str, len, false);
	slvm.symbols = Tsetl(slvm.symbols, str, len, v);
	return tagptr(v, TAG_SYM);
}

BUILTIN("gensym", gensym)
{
	argcount(nargs, 0);
	sl_gensym *gs = alloc_words(sizeof(sl_gensym)/sizeof(sl_v));
	gs->id = slvm.gensym_ctr++;
	gs->binding = sl_unbound;
	gs->type = nil;
	return tagptr(gs, TAG_SYM);
}

sl_v
mk_gensym(void)
{
	return fn_builtin_gensym(nil, 0);
}

sl_purefn
BUILTIN("gensym?", gensymp)
{
	argcount(nargs, 1);
	return isgensym(args[0]) ? sl_t : sl_nil;
}

char *
uint2str(char *dest, usize len, u64int num, int base)
{
	int i = len-1;
	u64int b = (u64int)base;
	char ch;
	dest[i--] = '\0';
	while(i >= 0){
		ch = (char)(num % b);
		if(ch < 10)
			ch += '0';
		else
			ch = ch-10+'A';
		dest[i--] = ch;
		num /= b;
		if(num == 0)
			break;
	}
	return &dest[i+1];
}

const char *
sym_name(sl_v v)
{
	char *n = (char*)sym_name_(v);
	if(n != nil)
		return n;
	assert(ismanaged(v));
	sl_gensym *gs = ptr(v);
	slvm.gsnameno = 1-slvm.gsnameno;
	n = uint2str(slvm.gsname[slvm.gsnameno]+1, sizeof(slvm.gsname[0])-1, gs->id, 10);
	*(--n) = 'g';
	return n;
}

// conses ---------------------------------------------------------------------

sl_v
alloc_cons(void)
{
	sl_cons *c;

	if(sl_unlikely(slvm.curheap > slvm.lim))
		sl_gc(false);
	c = (sl_cons*)slvm.curheap;
	slvm.curheap += sizeof(sl_cons);
	return tagptr(c, TAG_CONS);
}

void *
alloc_words(usize n)
{
	sl_v *first;

	// force 8-byte alignment (32-bit) and always two cells (to forward)
	assert(n > 0);
	if(n & 1)
		n++;
	if(sl_unlikely((sl_v*)slvm.curheap > (sl_v*)slvm.lim+2-n)){
		sl_gc(false);
		while(sl_unlikely((sl_v*)slvm.curheap > (sl_v*)slvm.lim+2-n))
			sl_gc(true);
	}
	first = (sl_v*)slvm.curheap;
	slvm.curheap += n*sizeof(sl_v);
	return first;
}

sl_v
alloc_vec(usize n, bool init)
{
	if(n == 0)
		return sl_emptyvec;
	sl_v *c = alloc_words(n+1);
	sl_v v = tagptr(c, TAG_VEC);
	vec_setsize(v, n, VEC_VEC);
	if(init){
		for(usize i = 0; i < n; i++)
			vec_elt(v, i) = sl_void;
	}
	return v;
}

void
sl_stack_grow(void)
{
	sl_v *s = MEM_REALLOC(sl.stack, 2*sl.nstack*sizeof(sl.stack));
	if(s == nil)
		sl_raise(sl_erroom);
	sl.nstack *= 2;
	sl.sp = s + (sl.sp - sl.stack);
	sl.stackend = s + sl.nstack;
	sl.stack = s;
}

// collector ------------------------------------------------------------------

void
sl_gc_handle(sl_v *pv)
{
	if(sl_unlikely(slvm.ngchandles == slvm.maxgchandles)){
		sl_v **gh = MEM_REALLOC(slvm.gchandles, slvm.maxgchandles*2*sizeof(sl_v*));
		if(gh == nil)
			cthrow(lerrorf(sl_errmem, "out of gc handles"), pv);
		slvm.maxgchandles *= 2;
		slvm.gchandles = gh;
	}
	slvm.gchandles[slvm.ngchandles++] = pv;
}

void
sl_free_gc_handles(int n)
{
	assert(slvm.ngchandles >= n);
	slvm.ngchandles -= n;
}

sl_v
sl_relocate(sl_v v)
{
	sl_v a, d, nc, first, *pcdr;

	if(isfixnum(v) || isunboxed(v) || isspecial(v))
		return v;

	uintptr t = tag(v);
	if(t == TAG_CONS){
		// iterative implementation allows arbitrarily long cons chains
		pcdr = &first;
		do{
			a = car_(v);
			if(sl_unlikely(isforwarded(v))){
				*pcdr = forwardloc(v);
				return first;
			}
			d = cdr_(v);
			*pcdr = nc = tagptr((sl_cons*)slvm.curheap, TAG_CONS);
			slvm.curheap += sizeof(sl_cons);
			forward(v, nc);
			car_(nc) = ismanaged(a) ? sl_relocate(a) : a;
			pcdr = &cdr_(nc);
			v = d;
		}while(iscons(v));
		*pcdr = d == sl_nil ? sl_nil : sl_relocate(d);
		return first;
	}

	if(!ismanaged(v))
		return v;
	if(isforwarded(v))
		return forwardloc(v);

	if(t == TAG_CVALUE){
		if(sl_unlikely(slvm.exiting)){
			sweep_cv(ptr(v));
			return sl_nil;
		}
		return cvalue_relocate(v);
	}
	if(t == TAG_VEC){
		// N.B.: 0-length vectors secretly have space for a first element
		usize i, sz = vec_size(v);
		if(sl_unlikely(vec_elt(v, -1) & VEC_GROWN)){
			// grown vector
			nc = sl_relocate(vec_elt(v, 0));
			forward(v, nc);
		}else{
			nc = tagptr(alloc_words(sz+1), TAG_VEC);
			vec_setsize(nc, sz, vec_type(v));
			a = vec_elt(v, 0);
			forward(v, nc);
			if(sl_likely(sz > 0)){
				vec_elt(nc, 0) = sl_relocate(a);
				for(i = 1; i < sz; i++)
					vec_elt(nc, i) = sl_relocate(vec_elt(v, i));
			}
		}
		return nc;
	}
	if(t == TAG_FN){
		sl_fn *fn = ptr(v), f;
		f.vals = sl_relocate(fn->vals);
		f.bcode = sl_relocate(fn->bcode);
		f.env = fn->env == sl_nil ? sl_nil : sl_relocate(fn->env);
		f.name = sl_relocate(fn->name);
		f.maxstack = fn->maxstack;
		sl_fn *nfn = alloc_words(sizeof(sl_fn)/sizeof(sl_v));
		*nfn = f;
		assert(!ismanaged(nfn->vals));
		assert(!ismanaged(nfn->bcode));
		assert(!ismanaged(nfn->env));
		assert(!ismanaged(nfn->name));
		nc = tagptr(nfn, TAG_FN);
		forward(v, nc);
		return nc;
	}
	if(t == TAG_SYM){
		sl_gensym *gs = ptr(v);
		sl_gensym *ng = alloc_words(sizeof(sl_gensym)/sizeof(sl_v));
		ng->id = gs->id;
		ng->binding = gs->binding;
		ng->type = gs->type;
		ng->name = gs->name;
		nc = tagptr(ng, TAG_SYM);
		forward(v, nc);
		if(ng->binding != sl_unbound)
			ng->binding = sl_relocate(ng->binding);
		return nc;
	}
	return v;
}

static void
trace_globals(void)
{
	const char *k = nil;
	sl_sym *v;
	while(Tnext(slvm.symbols, &k, (void**)&v)){
		if(v->binding != sl_unbound)
			v->binding = sl_relocate(v->binding);
	}
}

void
sl_gc(bool mustgrow)
{
	slvm.gccalls++;
	slvm.lim = slvm.curheap = slvm.tospace;
	slvm.lim += slvm.heapsize * (slvm.grew ? 2 : 1) - sizeof(sl_cons);

	usize top, f;
	if(sl.throwing_frame > sl.curr_frame){
		top = sl.throwing_frame - 3;
		f = sl.stack[top];
	}else{
		top = sl.sp - sl.stack;
		f = sl.curr_frame;
	}
	for(;;){
		for(usize p = f; p < top; p++){
			sl_v v = sl_relocate(sl.stack[p]);
			sl.stack[p] = v;
		}
		if(f == 0)
			break;
		top = f - 3;
		f = sl.stack[top];
	}
	for(int i = 0; i < slvm.ngchandles; i++)
		*slvm.gchandles[i] = sl_relocate(*slvm.gchandles[i]);
	trace_globals();
	relocate_typetable();
	sl_readstate *rs = sl.readstate;
	while(rs){
		sl_v ent;
		for(int i = 0; i < rs->backrefs.size; i++){
			ent = (sl_v)rs->backrefs.table[i];
			if(ent != (sl_v)HT_NOTFOUND)
				rs->backrefs.table[i] = (void*)sl_relocate(ent);
		}
		for(int i = 0; i < rs->gensyms.size; i++){
			ent = (sl_v)rs->gensyms.table[i];
			if(ent != (sl_v)HT_NOTFOUND)
				rs->gensyms.table[i] = (void*)sl_relocate(ent);
		}
		rs->source = sl_relocate(rs->source);
		rs = rs->prev;
	}
	sl.lasterror = sl_relocate(sl.lasterror);
	sl_erroom = sl_relocate(sl_erroom);
	sl_emptyvec = sl_relocate(sl_emptyvec);
	sl_emptystr = sl_relocate(sl_emptystr);

	sweep_finalizers();

	void *temp = slvm.tospace;
	slvm.tospace = slvm.fromspace;
	slvm.fromspace = temp;

	// FIXME(sigrid): add some extra to the "used"?
	sl_segused(slvm.fromspace, slvm.heapsize, slvm.curheap-slvm.fromspace);

	// if we're using > 80% of the space, resize tospace so we have
	// more space to fill next time. if we grew tospace last time,
	// grow the other half of the heap this time to catch up.
	if(slvm.grew || mustgrow || ((intptr)(slvm.lim-slvm.curheap) < (intptr)slvm.heapsize/5)){
		sl_segfree(slvm.tospace, slvm.heapsize);
		slvm.tospace = sl_segalloc(slvm.heapsize*2);
		if(sl_unlikely(slvm.tospace == nil)){
			slvm.tospace = sl_segalloc(slvm.heapsize);
			if(slvm.tospace == nil){
				// FIXME(sigrid): lost it entirely. give up?
				// alternatively, wait and try indefinitely?
				sysfatal("lost tospace");
			}
			sl_raise(sl_erroom);
		}
		if(slvm.grew){
			slvm.heapsize *= 2;
			temp = bitvector_resize(sl.consflags, 0, slvm.heapsize/sizeof(sl_cons), 1);
			if(sl_unlikely(temp == nil))
				sl_raise(sl_erroom);
			sl.consflags = (u32int*)temp;
		}
		slvm.grew = !slvm.grew;
	}
	if(sl_unlikely((sl_v*)slvm.curheap > (sl_v*)slvm.lim-2)){
		// all data was live; gc again and grow heap.
		// but also always leave at least 4 words available, so a closure
		// can be allocated without an extra check.
		sl_gc(false);
	}
}

// utils ----------------------------------------------------------------------

// apply function with n args on the stack
sl_hotfn
static sl_v
_applyn(int n)
{
	sl_v f = sl.sp[-n-1];
	usize osp = sl.sp - sl.stack;
	sl_v v;
	if(iscbuiltin(f)){
		v = ((sl_cv*)ptr(f))->cbuiltin(sl.sp-n, n);
	}else if(sl_likely(isbuiltin(f))){
		sl_v tab = sym_value(sl_builtinssym);
		if(sl_unlikely(ptr(tab) == nil))
			cthrow(unbound_error(tab), n);
		sl.sp[-n-1] = vec_elt(tab, uintval(f));
		v = apply_cl(n);
	}else if(isfn(f)){
		v = apply_cl(n);
	}else{
		cthrow(type_error(nil, "fn", f), n);
	}
	sl.sp = sl.stack + osp;
	return v;
}

sl_v
sl_apply(sl_v f, sl_v v)
{
	PUSH_SAFE(f);
	int n;
	for(n = 0; iscons(v); n++){
		PUSH_SAFE(car_(v));
		v = cdr_(v);
	}
	if(v != sl_nil)
		cthrow(lerrorf(sl_errarg, "apply: last argument: not a list"), f);
	v = _applyn(n);
	POPN(1+n);
	return v;
}

sl_v
sl_applyn(int n, sl_v f, ...)
{
	va_list ap;
	va_start(ap, f);

	stack_for(1+n);
	PUSH(f);
	for(int i = 0; i < n; i++){
		sl_v a = va_arg(ap, sl_v);
		PUSH(a);
	}
	sl_v v = _applyn(n);
	POPN(1+n);
	va_end(ap);
	return v;
}

sl_v
mk_listn(int n, ...)
{
	va_list ap;
	va_start(ap, n);
	sl_v si = sl.sp - sl.stack;

	stack_for(n);
	for(int i = 0; i < n; i++){
		sl_v a = va_arg(ap, sl_v);
		PUSH(a);
	}
	sl_cons *c = alloc_words(n*2);
	sl_cons *l = c;
	for(int i = 0; i < n; i++){
		c->car = sl.stack[si++];
		c->cdr = tagptr(c+1, TAG_CONS);
		c++;
	}
	c[-1].cdr = sl_nil;

	POPN(n);
	va_end(ap);
	return tagptr(l, TAG_CONS);
}

sl_v
mk_list2(sl_v a, sl_v b)
{
	PUSH(a);
	PUSH(b);
	sl_cons *c = alloc_words(4);
	b = POP();
	a = POP();
	c[0].car = a;
	c[0].cdr = tagptr(c+1, TAG_CONS);
	c[1].car = b;
	c[1].cdr = sl_nil;
	return tagptr(c, TAG_CONS);
}

sl_v
mk_cons(sl_v a, sl_v b)
{
	PUSH(a);
	PUSH(b);
	sl_v c = alloc_cons();
	cdr_(c) = POP();
	car_(c) = POP();
	return c;
}

bool
isnum(sl_v v)
{
	if(isfixnum(v))
		return true;
	if(isubnum(v))
		return true;
	if(iscvalue(v)){
		sl_cv *cv = ptr(v);
		return valid_numtype(cv_numtype(cv));
	}
	return false;
}

// eval -----------------------------------------------------------------------

sl_hotfn
static sl_v
list(sl_v *args, int nargs, bool star)
{
	if(sl_unlikely(nargs == 0))
		return sl_nil;
	sl_v v = cons_reserve(nargs);
	sl_cons *c = ptr(v);
	for(int i = 0; i < nargs; i++){
		c->car = args[i];
		c->cdr = tagptr(c+1, TAG_CONS);
		c++;
	}
	if(star)
		c[-2].cdr = c[-1].car;
	else
		c[-1].cdr = sl_nil;
	return v;
}

static sl_v
do_trycatch(void)
{
	usize osp = sl.sp - sl.stack;
	sl_v v = sl_nil;
	sl_v thunk = sl.sp[-2];
	sl.sp[-2] = sl.sp[-1];
	sl.sp[-1] = thunk;

	SL_TRY{
		v = apply_cl(0);
	}
	SL_CATCH{
		v = sl.stack[osp-2];
		PUSH_SAFE(v);
		PUSH_SAFE(sl.lasterror);
		v = apply_cl(1);
	}
	sl.sp = sl.stack + osp;
	return v;
}

/*
  argument layout on stack is
  |--required args--|--opt args--|--kw args--|--rest args...
*/
static int
process_keys(sl_v kwtable, int nreq, int nkw, int nopt, usize bp, int nargs, int va)
{
	int extr = nopt+nkw;
	int ntot = nreq+extr;
	sl_v args[64], v = sl_nil;
	int i, a = 0, nrestargs;
	sl_v s1 = sl.sp[-1];
	sl_v s3 = sl.sp[-3];
	sl_v s4 = sl.sp[-4];
	if(sl_unlikely(nargs < nreq))
		cthrow(arity_error(nargs, nreq), kwtable);
	if(sl_unlikely(extr > nelem(args)))
		cthrow(lerrorf(sl_errarg, "too many arguments"), kwtable);
	for(i = 0; i < extr; i++)
		args[i] = sl_unbound;
	for(i = nreq; i < nargs; i++){
		v = sl.stack[bp+i];
		if(issym(v) && iskeyword((sl_sym*)ptr(v)))
			break;
		if(a >= nopt)
			goto no_kw;
		args[a++] = v;
	}
	if(i >= nargs)
		goto no_kw;
	// now process keywords
	int n = vec_size(kwtable);
	do{
		i++;
		if(sl_unlikely(i >= nargs))
			cthrow(lerrorf(sl_errarg, "keyword %s requires an argument", sym_name(v)), kwtable);
		int x;
		for(x = 0; x < n; x++){
			if(sl_likely(vec_elt(kwtable, x) == v)){
				args[x + nopt] = sl.stack[bp+i];
				break;
			}
		}
		if(x == n)
			cthrow(lerrorf(sl_errarg, "unsupported keyword %s", sym_name(v)), kwtable);
		i++;
		if(i >= nargs)
			break;
		v = sl.stack[bp+i];
	}while(issym(v) && iskeyword((sl_sym*)ptr(v)));
no_kw:
	nrestargs = nargs - i;
	if(sl_unlikely(!va && nrestargs > 0))
		cthrow(arity_error(nrestargs, nreq), kwtable);
	nargs = ntot + nrestargs;
	if(nrestargs)
		memmove(&sl.stack[bp+ntot], &sl.stack[bp+i], nrestargs*sizeof(sl_v));
	memmove(&sl.stack[bp+nreq], args, extr*sizeof(sl_v));
	sl.sp = &sl.stack[bp+nargs];
	assert(sl.sp < sl.stackend-4);
	PUSH(s4);
	PUSH(s3);
	PUSH(nargs);
	PUSH(s1);
	sl.curr_frame = sl.sp - sl.stack;
	return nargs;
}

#if BYTE_ORDER == LITTLE_ENDIAN && defined(MEM_UNALIGNED_ACCESS)
#define GET_S32(a) *(const s32int*)(a)
#define GET_S16(a) *(const s16int*)(a)
#else
#define GET_S32(a) (s32int)((a)[0]<<0 | (a)[1]<<8 | (a)[2]<<16 | (u32int)(a)[3]<<24)
#define GET_S16(a) (s16int)((a)[0]<<0 | (a)[1]<<8)
#endif

/*
  stack on entry: <fn> <nargs args...>
  caller's responsibility:
  - put the stack in this state
  - provide arg count
  - respect tail position
  - restore SP

  callee's responsibility:
  - check arg counts
  - allocate vararg array
  - push closed env, set up new environment
*/
static sl_v
apply_cl(int nargs)
{
	usize obp, ipd, top_frame = sl.curr_frame;
	const u8int *ip;
	bool tail;
	int n;

	goto apply_func;

#if defined(COMPUTED_GOTO)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpedantic"
	static const void * const ops[] = {
#define GOTO_OP_OFFSET(op) [op] = &&op_##op
#include "vm_goto.h"
#undef GOTO_OP_OFFSET
	};
#define NEXT_OP do{ goto *ops[*ip++]; }while(0)
#define LABEL(x) x
#define OP(x) op_##x:
#include "vm.h"
#undef OP
#undef LABEL
#undef NEXT_OP
#pragma GCC diagnostic pop
#else /* just a usual (portable) switch/case */
	u8int op;
	while(1){
		switch(op){
#define NEXT_OP break
#define LABEL(x) x
#define OP(x) case x:
#include "vm.h"
#undef OP
#undef LABEL
#undef NEXT_OP
		}
		op = *ip++;
	}
#endif
}

// top = top frame pointer to start at
static sl_v
_stacktrace(usize top)
{
	sl_v lst = sl_nil, v = sl_nil, fn = sl_nil;

	sl_gc_handle(&lst);
	sl_gc_handle(&v);
	sl_gc_handle(&fn);
	while(top > 0){
		const u8int *ip1 = (void*)sl.stack[top-1];
		int sz = sl.stack[top-2]+1;
		usize bp = top-4-sz;
		fn = sl.stack[bp+0];
		v = alloc_vec(sz+1, 0);
		if(iscbuiltin(fn))
			vec_elt(v, 0) = lst == sl_nil ? mk_ptr(sl.cpc) : fn;
		else{
			/* -1: ip1 is *after* the one that was being executed */
			intptr ip = ip1 - (const u8int*)cvalue_data(fn_bcode(fn)) - 1;
			vec_elt(v, 0) = fixnum(ip);
		}
		vec_elt(v, 1) = fn;
		for(int i = 1; i < sz; i++){
			sl_v si = sl.stack[bp+i];
			// if there's an error evaluating argument defaults some slots
			// might be left set to sl_unbound
			vec_elt(v, i+1) = si == sl_unbound ? sl_void : si;
		}
		lst = mk_cons(v, lst);
		top = sl.stack[top-3];
	}
	sl_free_gc_handles(3);
	return lst;
}

// builtins -------------------------------------------------------------------

BUILTIN("gc", gc)
{
	argcount(nargs, 0);
	sl_gc(false);
	return sl_void;
}

BUILTIN("fn", fn)
{
	if(nargs == 1){
		sl_v f = args[0];
		if(issym(f))
			f = sym_value(f);
		if(f == sl_unbound)
			unbound_error(f);
		if(!isfn(f))
			type_error(nil, "fn", f);
		return f;
	}
	if(nargs < 1 || nargs > 6)
		argcount(nargs, 1);
	sl_fn *fn = alloc_words(sizeof(sl_fn)/sizeof(sl_v));
	sl_v fv = tagptr(fn, TAG_FN);
	fn->bcode = sl_emptystr;
	fn->vals = sl_emptyvec;
	fn->env = sl_nil;
	fn->name = sl_lambda;
	u8int *data = nil;
	usize sz = 0;
	bool envset = false, valsset = false;
	bool nameset = false, maxstackset = false;
	bool bcodeset = false, raw = false;
	for(int i = 0; nargs > i; i++){
		sl_v v = args[i];
		if(!envset && (v == sl_nil || (valsset && isvec(v)))){
			envset = true;
			fn->env = v;
		}else if(!valsset && isvec(v)){
			valsset = true;
			fn->vals = v;
		}else if(v == sl_t){
			raw = true;
		}else if(!nameset && issym(v)){
			if(sl_unlikely(isgensym(v)))
				bthrow(lerrorf(sl_errarg, "name cannot be a gensym"));
			nameset = true;
			fn->name = v;
		}else if(!maxstackset && isfixnum(v)){
			if(sl_unlikely(numval(v) < 0))
				bthrow(lerrorf(sl_errarg, "invalid maxstack value"));
			maxstackset = true;
			fn->maxstack = numval(v);
		}else if(!bcodeset && isstr(v)){
			bcodeset = true;
			sl_cv *arr = ptr(v);
			cv_pin(arr);
			data = cv_data(arr);
			sz = cv_len(arr);
			fn->bcode = v;
		}else{
			bthrow(lerrorf(sl_errarg, "unexpected argument type"));
		}
	}
	if(!bcodeset)
		bthrow(lerrorf(sl_errarg, "no code"));
	if(!maxstackset)
		bthrow(lerrorf(sl_errarg, "no max stack"));
	if(!raw){
		// read syntax, shifted 48 for compact text representation
		for(usize j = 0; j < sz; j++)
			data[j] -= 48;
	}
	return fv;
}

sl_purefn
BUILTIN("fn-code", fn_code)
{
	argcount(nargs, 1);
	sl_v v = args[0];
	if(sl_unlikely(!isfn(v)))
		bthrow(type_error(nil, "fn", v));
	if(sl_unlikely(iscbuiltin(v) || isbuiltin(v)))
		return v;
	return fn_bcode(v);
}

sl_purefn
BUILTIN("fn-vals", fn_vals)
{
	argcount(nargs, 1);
	sl_v v = args[0];
	if(sl_unlikely(!isfn(v)))
		bthrow(type_error(nil, "fn", v));
	if(sl_unlikely(iscbuiltin(v) || isbuiltin(v)))
		return sl_emptyvec;
	return fn_vals(v);
}

sl_purefn
BUILTIN("fn-env", fn_env)
{
	argcount(nargs, 1);
	sl_v v = args[0];
	if(sl_unlikely(!isfn(v)))
		bthrow(type_error(nil, "fn", v));
	if(sl_unlikely(iscbuiltin(v) || isbuiltin(v)))
		return sl_nil;
	return fn_env(v);
}

BUILTIN("fn-name", fn_name)
{
	argcount(nargs, 1);
	sl_v v = args[0];
	if(isbuiltin(v))
		return mk_sym(builtins[uintval(v)].name, false);
	if(iscbuiltin(v)){
		v = (sl_v)ptrhash_get(&slvm.reverse_dlsym_lookup, ptr(v));
		if(v == (sl_v)HT_NOTFOUND)
			return sl_nil;
		return v;
	}
	if(isfn(v))
		return fn_name(v);
	bthrow(type_error(nil, "fn", v));
}

BUILTIN("fn-maxstack", fn_maxstack)
{
	argcount(nargs, 1);
	sl_v v = args[0];
	if(isbuiltin(v) || iscbuiltin(v))
		return fixnum(0);
	if(isfn(v))
		return size_wrap(fn_maxstack(v));
	bthrow(type_error(nil, "fn", v));
}

BUILTIN("list*", liststar)
{
	if(nargs == 1)
		return args[0];
	if(nargs == 0)
		argcount(nargs, 1);
	return list(args, nargs, true);
}

BUILTIN("stacktrace", stacktrace)
{
	argcount(nargs, 0);
	return _stacktrace(sl.throwing_frame ? sl.throwing_frame : sl.curr_frame);
}

static sl_v
map_seq(sl_v rt, sl_v *args, int nargs)
{
	enum {
		RT_AUTO,
		RT_LIST,
		RT_VEC,
		RT_ARR,
		RT_STR,
		RT_TBL,
		RT_NIL,
	} rtype = RT_AUTO;
	sl_v arrtype = sl_nil;
	bool rtdecl = true;
	if(rt == sl_nil)
		rtype = RT_NIL;
	else if(rt == sl_unbound)
		rtdecl = false;
	else if(issym(rt)){
		if(rt == sl_listsym)
			rtype = RT_LIST;
		else if(rt == sl_vecsym)
			rtype = RT_VEC;
		else if(rt == sl_strsym)
			rtype = RT_STR;
		else if(rt == sl_tablesym)
			rtype = RT_TBL;
		else
			bthrow(type_error("result-type", "sequence type specifier", rt));
	}else if(iscons(rt)){
		if(car_(rt) != sl_arrsym)
			bthrow(type_error("result-type", "array type specifier", rt));
		rtype = RT_ARR;
		arrtype = car_(cdr_(rt));
		get_arr_type(arrtype);
	}else{
		bthrow(type_error("result-type", "sequence type specifier", rt));
	}
	usize k = sl.sp - sl.stack;
	usize oargs = args - sl.stack;
	stack_for(2+nargs*2+2);
	PUSH(sl_nil);
	PUSH(sl_nil);
	for(usize n = 0;; n++){
		PUSH(sl.stack[oargs+0]);
		int pargs = 0;
		for(int i = 1; i < nargs; i++, pargs++){
			sl_v v = sl.stack[oargs+i];
			if(iscons(v)){
				if(!rtdecl){
					if(rtype == RT_AUTO)
						rtype = RT_LIST;
					if(rtype != RT_LIST)
						bthrow(lerrorf(sl_errarg, "sequence type mismatch"));
				}
				PUSH(car_(v));
				sl.stack[oargs+i] = cdr_(v);
				continue;
			}else if(isvec(v)){
				if(!rtdecl){
					if(rtype == RT_AUTO)
						rtype = RT_VEC;
					if(rtype != RT_VEC)
						bthrow(lerrorf(sl_errarg, "sequence type mismatch"));
				}
				usize sz = vec_size(v);
				if(n < sz){
					PUSH(vec_elt(v, n));
					continue;
				}
			}else if(isstr(v)){
				if(!rtdecl){
					if(rtype == RT_AUTO)
						rtype = RT_STR;
					if(rtype != RT_STR)
						bthrow(lerrorf(sl_errarg, "sequence type mismatch"));
				}
				usize b = rune_index(v, n);
				if(b < cv_len(ptr(v))){
					Rune r;
					chartorune(&r, tostr(v)+b);
					PUSH(mk_rune(r));
					continue;
				}
			}else if(isarr(v)){
				if(!rtdecl){
					if(rtype == RT_AUTO){
						rtype = RT_ARR;
						arrtype = cv_class(ptr(v))->eltype->type;
					}
					if(rtype != RT_ARR || arrtype != cv_class(ptr(v))->eltype->type)
						bthrow(lerrorf(sl_errarg, "sequence type mismatch"));
				}
				usize sz = cvalue_arrlen(v);
				if(n < sz){
					sl_v aref[2];
					aref[0] = v;
					aref[1] = fixnum(n);
					PUSH(cvalue_arr_aref(aref));
					continue;
				}
			}else if(ishashtable(v)){
				if(!rtdecl){
					if(rtype == RT_AUTO)
						rtype = RT_TBL;
					if(rtype != RT_TBL)
						bthrow(lerrorf(sl_errarg, "sequence type mismatch"));
				}
				sl_htable *h = totable(v);
				assert(n != 0 || h->i == 0);
				void **table = h->table;
				for(; h->i < h->size; h->i += 2){
					if(table[h->i+1] != HT_NOTFOUND)
						break;
				}
				if(h->i < h->size){
					PUSH((sl_v)table[h->i]);
					pargs++;
					PUSH((sl_v)table[h->i+1]);
					h->i += 2;
					continue;
				}
				h->i = 0;
			}
			POPN(pargs+1);
			switch(rtype){
			default:
				break;
			case RT_VEC:
				sl.stack[k+1] = alloc_vec(n, 0);
				memmove(&vec_elt(sl.stack[k+1], 0), sl.sp-n, n*sizeof(sl_v));
				POPN(n);
				break;
			case RT_ARR:
				sl.stack[k+0] = sym_value(sl_arrsym);
				sl.stack[k+1] = arrtype;
				sl.stack[k+1] = _applyn(n+1);
				POPN(n);
				break;
			case RT_STR:
				sl.stack[k+1] = sym_value(sl_strsym);
				sl.stack[k+1] = _applyn(n);
				POPN(n);
				break;
			case RT_TBL:
				sl.stack[k+1] = sym_value(sl_tablesym);
				sl.stack[k+1] = _applyn(2*n);
				POPN(2*n);
				break;
			case RT_NIL:
				sl.stack[k+1] = sl_nil;
				break;
			}
			sl_v res = sl.stack[k+1];
			POPN(2);
			return res;
		}
		sl_v c, v = _applyn(pargs);
		POPN(pargs+1);
		switch(rtype){
		default:
			PUSH(v);
			break;
		case RT_NIL:
			break;
		case RT_TBL:
			PUSH(car(v));
			PUSH(cdr(v));
			break;
		case RT_LIST:
			sl_gc_handle(&v);
			c = alloc_cons();
			sl_free_gc_handles(1);
			car_(c) = v;
			cdr_(c) = sl_nil;
			if(n == 0)
				sl.stack[k+1] = c;
			else
				cdr_(sl.stack[k+0]) = c;
			sl.stack[k+0] = c;
			break;
		}
	}
}

BUILTIN("map", map)
{
	if(sl_unlikely(nargs < 2))
		argcount(nargs, 2);
	sl_v v = args[0];
	return isfn(v)
		? map_seq(sl_unbound, args, nargs)
		: map_seq(v, args+1, nargs-1);
}

BUILTIN("for-each", for_each)
{
	if(sl_unlikely(nargs < 2))
		argcount(nargs, 2);
	map_seq(sl_nil, args, nargs);
	return sl_void;
}

BUILTIN("sleep", sl_sleep)
{
	if(nargs > 1)
		argcount(nargs, 1);
	double s = nargs > 0 ? todouble(args[0]) : 0;
	sleep_ms(s * 1000.0);
	return sl_void;
}

BUILTIN("vm-stats", vm_stats)
{
	argcount(nargs, 0);
	ios *io = toio(sym_value(sl_iooutsym), true, false, true);
	ios_printf(io, "heap total     %10"PRIuPTR" bytes\n", slvm.heapsize);
	ios_printf(io, "heap free      %10"PRIuPTR" bytes\n", (uintptr)(slvm.lim-slvm.curheap));
	ios_printf(io, "heap used      %10"PRIuPTR" bytes\n", (uintptr)(slvm.curheap-slvm.fromspace));
	ios_printf(io, "stack          %10"PRIu64" bytes\n", (u64int)sl.nstack*sizeof(sl_v));
	ios_printf(io, "finalizers     %10"PRIu32"\n", (u32int)slvm.nfinalizers);
	ios_printf(io, "max finalizers %10"PRIu32"\n", (u32int)slvm.maxfinalizers);
	ios_printf(io, "gc handles     %10"PRIu32"\n", (u32int)slvm.ngchandles);
	ios_printf(io, "max gc handles %10"PRIu32"\n", (u32int)slvm.maxgchandles);
	ios_printf(io, "gc calls       %10"PRIu64"\n", (u64int)slvm.gccalls);
	ios_printf(io, "opcodes        %10d\n", N_OPCODES);
	return sl_void;
}

static const sl_builtinspec builtin_fns[] = {
#define BUILTIN_FN(l, c, attr){l, (sl_builtinfn)fn_builtin_##c},
#include "builtin_fns.h"
#undef BUILTIN_FN
};

// initialization -------------------------------------------------------------

int
sl_init(usize heapsize)
{
	int i;

	if((slp = MEM_CALLOC(1, sizeof(*slp))) == nil)
		return -1;
	sl.scr_width = 100;

	slvm.heapsize = heapsize*sizeof(sl_v);

	if((slvm.fromspace = sl_segalloc(slvm.heapsize)) == nil){
failed:
		MEM_FREE(sl.consflags);
		MEM_FREE(slvm.finalizers);
		MEM_FREE(slvm.gchandles);
		MEM_FREE(sl.stack);
		sl_segfree(slvm.fromspace, slvm.heapsize);
		sl_segfree(slvm.tospace, slvm.heapsize);
		htable_free(&sl.printconses);
		MEM_FREE(slp);
		return -1;
	}

	if((slvm.tospace = sl_segalloc(slvm.heapsize)) == nil)
		goto failed;
	slvm.curheap = slvm.fromspace;
	slvm.lim = slvm.curheap+slvm.heapsize-sizeof(sl_cons);

	sl.nstack = STACK_SIZE0;
	if((sl.stack = MEM_ALLOC(sl.nstack*sizeof(sl_v))) == nil)
		goto failed;
	sl.sp = sl.stack;
	sl.stackend = sl.stack + sl.nstack - 4;

	slvm.maxfinalizers = 512;
	if((slvm.finalizers = MEM_ALLOC(slvm.maxfinalizers * sizeof(*slvm.finalizers))) == nil)
		goto failed;
	slvm.maxgchandles = 16;
	if((slvm.gchandles = MEM_ALLOC(slvm.maxgchandles * sizeof(sl_v*))) == nil)
		goto failed;

	if((sl.consflags = bitvector_new(slvm.heapsize/sizeof(sl_cons), 1)) == nil)
		goto failed;
	if((htable_new(&sl.printconses, 32)) == nil)
		goto failed;

	comparehash_init();

	sl_lambda = mk_csym("λ");
	setc(mk_csym("lambda"), sl_lambda);
	setc(mk_csym("NIL"), sl_nil);
	setc(mk_csym("T"), sl_t);
	sl_quote = mk_csym("quote");
	sl_trycatch = mk_csym("trycatch");
	sl_backquote = mk_csym("quasiquote");
	sl_comma = mk_csym("unquote");
	sl_commaat = mk_csym("unquote-splicing");
	sl_commadot = mk_csym("unquote-nsplicing");
	sl_errio = mk_csym("io-error");
	sl_errparse = mk_csym("parse-error");
	sl_errtype = mk_csym("type-error");
	sl_errarg = mk_csym("arg-error");
	sl_errarity = mk_csym("arity-error");
	sl_errunbound = mk_csym("unbound-error");
	sl_errkey = mk_csym("key-error");
	sl_errmem = mk_csym("memory-error");
	sl_errconst = mk_csym("const-error");
	sl_errbounds = mk_csym("bounds-error");
	sl_errdiv0 = mk_csym("divide-error");
	sl_err = mk_csym("error");
	sl_conssym = mk_csym("cons");
	sl_symsym = mk_csym("sym");
	sl_fixnumsym = mk_csym("fixnum");
	sl_vecsym = mk_csym("vec");
	sl_builtinsym = mk_csym("builtin");
	sl_boolsym = mk_csym("bool");
	sl_nullsym = mk_csym("null");
	sl_defsym = mk_csym("def");
	sl_defmacrosym = mk_csym("defmacro");
	sl_forsym = mk_csym("for");
	sl_setqsym = mk_csym("set!");
	sl_evalsym = mk_csym("eval");
	sl_vu8sym = mk_csym("vu8");
	sl_fnsym = mk_csym("fn");
	sl_trimsym = mk_csym(":trim");

	sl_vecstructsym = mk_csym("%struct%");
	sl_structsym = mk_csym("struct");
	sl_builtinssym = mk_csym("*builtins*");
	sl_listsym = mk_csym("list");
	sl_tablesym = mk_csym("table");
	sl_strsym = mk_csym("str");

	setc(mk_csym("most-positive-fixnum"), fixnum(FIXNUM_MAX));
	setc(mk_csym("most-negative-fixnum"), fixnum(FIXNUM_MIN));

	sl.lasterror = sl_nil;

	for(i = 0; i < nelem(builtins); i++){
		if(builtins[i].name != nil)
			set(mk_sym(builtins[i].name, false), builtin(i));
	}

	sl_emptyvec = tagptr(alloc_words(2), TAG_VEC);
	vec_setsize(sl_emptyvec, 0, VEC_VEC);

	sl_read_init();
	sl_print_init();
	cvalues_init();

	setc(mk_csym("+os-name+"), cvalue_static_cstr(__os_name__));
#if defined(__os_version__)
	setc(mk_csym("+os-version+"), cvalue_static_cstr(__os_version__));
#endif
#if BYTE_ORDER == LITTLE_ENDIAN
	setc(mk_csym("+endianness+"), mk_csym(":little-endian"));
#else
	setc(mk_csym("+endianness+"), mk_csym(":big-endian"));
#endif
	sl_erroom = mk_list2(sl_errmem, cvalue_static_cstr("out of memory"));

	const sl_builtinspec *b;
	for(i = 0, b = builtin_fns; i < nelem(builtin_fns); i++, b++)
		mk_cbuiltin(b->name, b->fptr);
	table_init();
	io_init();
	compress_init();
	sys_init();
	math_init();
	str_init();
	return 0;
}

// top level ------------------------------------------------------------------

sl_v
sl_toplevel_eval(sl_v expr)
{
	return sl_applyn(1, sym_value(sl_evalsym), expr);
}

int
sl_load_system_image(sl_v sys_image_io)
{
	PUSH(sys_image_io);
	usize osp = sl.sp - sl.stack;
	SL_TRY{
		while(1){
			sl.sp = sl.stack + osp;
			sl_v e = sl_read_sexpr(sl.sp[-1], false);
			if(ios_eof(value2c(ios*, sl.sp[-1])))
				break;
			if(isfn(e)){
				// stage 0 format: series of thunks
				PUSH(e);
				(void)_applyn(0);
			}else{
				// stage 1 format: list alternating symbol/value
				while(iscons(e)){
					sl_sym *sym = tosym(car_(e));
					e = cdr_(e);
					if(sym->binding != sl_unbound)
						ios_printf(ios_stderr, "%s redefined on boot\n", sym->name);
					sym->binding = car_(e);
					e = cdr_(e);
				}
				break;
			}
		}
	}
	SL_CATCH_NO_INC{
		ios_puts(ios_stderr, "fatal error during bootstrap: ");
		sl_print(ios_stderr, sl.lasterror);
		ios_putc(ios_stderr, '\n');
		break;
	}
	sl.sp = sl.stack + osp - 1;
	return 0;
}