ref: d9f6cb0d7f88d15f8a110c63e84ab7b5514755c2
dir: /flisp.c/
/*
femtoLisp
by Jeff Bezanson (C) 2009
Distributed under the BSD License
*/
#include "flisp.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 "iostream.h"
#include "fsixel.h"
#include "compress.h"
value_t FL_builtins_table_sym, FL_quote, FL_lambda, FL_function, FL_comma, FL_commaat;
value_t FL_commadot, FL_trycatch, FL_backquote;
value_t FL_conssym, FL_symbolsym, FL_fixnumsym, FL_vectorsym, FL_builtinsym, FL_vu8sym;
value_t FL_definesym, FL_defmacrosym, FL_forsym, FL_setqsym;
value_t FL_tsym, FL_Tsym, FL_fsym, FL_Fsym, FL_booleansym, FL_nullsym, FL_evalsym, FL_fnsym;
value_t FL_nulsym, FL_alarmsym, FL_backspacesym, FL_tabsym, FL_linefeedsym, FL_newlinesym;
value_t FL_vtabsym, FL_pagesym, FL_returnsym, FL_escsym, FL_spacesym, FL_deletesym;
value_t FL_IOError, FL_ParseError, FL_TypeError, FL_ArgError, FL_MemoryError;
value_t FL_DivideError, FL_BoundsError, FL_Error, FL_KeyError, FL_EnumerationError;
value_t FL_UnboundError;
value_t FL_sizesym, FL_tosym;
value_t FL_printwidthsym, FL_printreadablysym, FL_printprettysym, FL_printlengthsym;
value_t FL_printlevelsym;
value_t FL_tablesym, FL_arraysym;
value_t FL_iostreamsym, FL_rdsym, FL_wrsym, FL_apsym, FL_crsym, FL_truncsym;
value_t FL_instrsym, FL_outstrsym;
value_t FL_int8sym, FL_uint8sym, FL_int16sym, FL_uint16sym, FL_int32sym, FL_uint32sym;
value_t FL_int64sym, FL_uint64sym, FL_bignumsym;
value_t FL_bytesym, FL_runesym, FL_floatsym, FL_doublesym;
value_t FL_stringtypesym, FL_runestringtypesym;
typedef struct {
char *name;
builtin_t fptr;
}builtinspec_t;
#ifdef NDEBUG
__thread
#endif
Fl *fl;
bool
isbuiltin(value_t x)
{
uint32_t i;
return tag(x) == TAG_FUNCTION && (i = uintval(x)) < nelem(builtins) && builtins[i].name != nil;
}
static value_t apply_cl(uint32_t nargs);
// error utilities ------------------------------------------------------------
void
free_readstate(fl_readstate_t *rs)
{
htable_free(&rs->backrefs);
htable_free(&rs->gensyms);
}
_Noreturn void
fl_exit(int status)
{
FL(exiting) = true;
gc(0);
exit(status);
}
#define FL_TRY \
fl_exception_context_t _ctx; int l__tr, l__ca; \
_ctx.sp = FL(sp); _ctx.frame = FL(curr_frame); _ctx.rdst = FL(readstate); _ctx.prev = FL(exctx); \
_ctx.ngchnd = FL(ngchandles); FL(exctx) = &_ctx; \
if(!setjmp(_ctx.buf)) \
for(l__tr = 1; l__tr; l__tr = 0, (void)(FL(exctx) = FL(exctx)->prev))
#define FL_CATCH_INC \
l__ca = 0, FL(lasterror) = FL_nil, FL(throwing_frame) = 0, FL(sp) = _ctx.sp, FL(curr_frame) = _ctx.frame
#define FL_CATCH \
else \
for(l__ca = 1; l__ca; FL_CATCH_INC)
#define FL_CATCH_NO_INC \
else \
for(l__ca = 1; l__ca;)
void
fl_savestate(fl_exception_context_t *_ctx)
{
_ctx->sp = FL(sp);
_ctx->frame = FL(curr_frame);
_ctx->rdst = FL(readstate);
_ctx->prev = FL(exctx);
_ctx->ngchnd = FL(ngchandles);
}
void
fl_restorestate(fl_exception_context_t *_ctx)
{
FL(lasterror) = FL_nil;
FL(throwing_frame) = 0;
FL(sp) = _ctx->sp;
FL(curr_frame) = _ctx->frame;
}
_Noreturn void
fl_raise(value_t e)
{
ios_flush(ios_stdout);
ios_flush(ios_stderr);
FL(lasterror) = e;
// unwind read state
while(FL(readstate) != FL(exctx)->rdst){
free_readstate(FL(readstate));
FL(readstate) = FL(readstate)->prev;
}
if(FL(throwing_frame) == 0)
FL(throwing_frame) = FL(curr_frame);
FL(ngchandles) = FL(exctx)->ngchnd;
fl_exception_context_t *thisctx = FL(exctx);
if(FL(exctx)->prev) // don't throw past toplevel
FL(exctx) = FL(exctx)->prev;
longjmp(thisctx->buf, 1);
}
_Noreturn void
lerrorf(value_t e, const char *format, ...)
{
char msgbuf[256];
va_list args;
PUSH(e);
va_start(args, format);
vsnprintf(msgbuf, sizeof(msgbuf), format, args);
value_t msg = string_from_cstr(msgbuf);
va_end(args);
e = POP();
fl_raise(fl_list2(e, msg));
}
_Noreturn void
type_error(const char *expected, value_t got)
{
fl_raise(fl_listn(3, FL_TypeError, symbol(expected, false), got));
}
_Noreturn void
bounds_error(value_t arr, value_t ind)
{
fl_raise(fl_listn(3, FL_BoundsError, arr, ind));
}
_Noreturn void
unbound_error(value_t sym)
{
fl_raise(fl_listn(2, FL_UnboundError, sym));
}
// safe cast operators --------------------------------------------------------
#define isstring fl_isstring
#define SAFECAST_OP(type, ctype, cnvt) \
ctype to##type(value_t v) \
{ \
if(__likely(is##type(v))) \
return (ctype)cnvt(v); \
type_error(#type, v); \
}
SAFECAST_OP(cons, cons_t*, ptr)
SAFECAST_OP(symbol, symbol_t*, ptr)
SAFECAST_OP(fixnum, fixnum_t, numval)
//SAFECAST_OP(cvalue, cvalue_t*, ptr)
SAFECAST_OP(string, char*, cvalue_data)
#undef isstring
// symbol table ---------------------------------------------------------------
bool
fl_is_keyword_name(const char *str, size_t len)
{
return (str[0] == ':' || str[len-1] == ':') && str[1] != '\0';
}
static symbol_t *
mk_symbol(const char *str, int len, bool copy)
{
symbol_t *sym;
sym = MEM_ALLOC(sizeof(*sym) + (copy ? len+1 : 0));
assert(((uintptr_t)sym & 0x7) == 0); // make sure malloc aligns 8
sym->numtype = NONNUMERIC;
if(fl_is_keyword_name(str, len)){
value_t s = tagptr(sym, TAG_SYM);
setc(s, s);
sym->flags = FLAG_KEYWORD;
}else{
sym->binding = UNBOUND;
sym->flags = 0;
}
sym->type = nil;
sym->hash = memhash32(str, len)^0xAAAAAAAA;
if(copy){
sym->name = (const char*)(sym+1);
memcpy((char*)sym->name, str, len+1);
}else{
sym->name = str;
}
sym->size = 0;
return sym;
}
value_t
symbol(const char *str, bool copy)
{
int len = strlen(str);
symbol_t *v;
const char *k;
if(!Tgetkv(FL(symtab), str, len, &k, (void**)&v)){
v = mk_symbol(str, len, copy);
FL(symtab) = Tsetl(FL(symtab), v->name, len, v);
}
return tagptr(v, TAG_SYM);
}
BUILTIN("gensym", gensym)
{
argcount(nargs, 0);
USED(args);
gensym_t *gs = alloc_words(sizeof(gensym_t)/sizeof(value_t));
gs->id = FL(gensym_ctr)++;
gs->binding = UNBOUND;
gs->type = nil;
return tagptr(gs, TAG_SYM);
}
value_t
gensym(void)
{
return fn_builtin_gensym(nil, 0);
}
BUILTIN("gensym?", gensymp)
{
argcount(nargs, 1);
return isgensym(args[0]) ? FL_t : FL_f;
}
char *
uint2str(char *dest, size_t len, uint64_t num, uint32_t base)
{
int i = len-1;
uint64_t b = (uint64_t)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 *
symbol_name(value_t v)
{
if(ismanaged(v)){
gensym_t *gs = (gensym_t*)ptr(v);
FL(gsnameno) = 1-FL(gsnameno);
char *n = uint2str(FL(gsname)[FL(gsnameno)]+1, sizeof(FL(gsname)[0])-1, gs->id, 10);
*(--n) = 'g';
return n;
}
return ((symbol_t*)ptr(v))->name;
}
// conses ---------------------------------------------------------------------
value_t
mk_cons(void)
{
cons_t *c;
if(__unlikely(FL(curheap) > FL(lim)))
gc(0);
c = (cons_t*)FL(curheap);
FL(curheap) += sizeof(cons_t);
return tagptr(c, TAG_CONS);
}
void *
alloc_words(uint32_t n)
{
value_t *first;
assert(n > 0);
n = ALIGNED(n, 2); // only allocate multiples of 2 words
if(__unlikely((value_t*)FL(curheap) > (value_t*)FL(lim)+2-n)){
gc(0);
while((value_t*)FL(curheap) > ((value_t*)FL(lim))+2-n)
gc(1);
}
first = (value_t*)FL(curheap);
FL(curheap) += n*sizeof(value_t);
return first;
}
value_t
alloc_vector(size_t n, int init)
{
if(n == 0)
return FL(the_empty_vector);
value_t *c = alloc_words(n+1);
value_t v = tagptr(c, TAG_VECTOR);
vector_setsize(v, n);
if(init){
unsigned int i;
for(i = 0; i < n; i++)
vector_elt(v, i) = FL_void;
}
return v;
}
// collector ------------------------------------------------------------------
void
fl_gc_handle(value_t *pv)
{
if(__unlikely(FL(ngchandles) >= N_GC_HANDLES))
lerrorf(FL_MemoryError, "out of gc handles");
FL(gchandles)[FL(ngchandles)++] = pv;
}
void
fl_free_gc_handles(uint32_t n)
{
assert(FL(ngchandles) >= n);
FL(ngchandles) -= n;
}
value_t
relocate(value_t v)
{
value_t a, d, nc, first, *pcdr;
if(isfixnum(v))
return v;
uintptr_t t = tag(v);
if(t == TAG_CONS){
// iterative implementation allows arbitrarily long cons chains
pcdr = &first;
do{
if((a = car_(v)) == TAG_FWD){
*pcdr = cdr_(v);
return first;
}
car_(v) = TAG_FWD;
d = cdr_(v);
*pcdr = nc = tagptr((cons_t*)FL(curheap), TAG_CONS);
FL(curheap) += sizeof(cons_t);
cdr_(v) = nc;
car_(nc) = relocate(a);
pcdr = &cdr_(nc);
v = d;
}while(iscons(v));
*pcdr = d == FL_nil ? FL_nil : relocate(d);
return first;
}
if(!ismanaged(v))
return v;
if(isforwarded(v))
return forwardloc(v);
if(t == TAG_CVALUE)
return cvalue_relocate(v);
if(t == TAG_CPRIM){
cprim_t *pcp = ptr(v);
size_t nw = CPRIM_NWORDS-1+NWORDS(cp_class(pcp)->size);
cprim_t *ncp = alloc_words(nw);
while(nw--)
((value_t*)ncp)[nw] = ((value_t*)pcp)[nw];
nc = tagptr(ncp, TAG_CPRIM);
forward(v, nc);
return nc;
}
if(t == TAG_FUNCTION){
function_t *fn = ptr(v);
function_t *nfn = alloc_words(4);
nfn->bcode = fn->bcode;
nfn->vals = fn->vals;
nc = tagptr(nfn, TAG_FUNCTION);
forward(v, nc);
nfn->env = relocate(fn->env);
nfn->vals = relocate(nfn->vals);
nfn->bcode = relocate(nfn->bcode);
assert(!ismanaged(fn->name));
nfn->name = fn->name;
return nc;
}
if(t == TAG_VECTOR){
// N.B.: 0-length vectors secretly have space for a first element
size_t i, sz = vector_size(v);
if(vector_elt(v, -1) & 0x1){
// grown vector
nc = relocate(vector_elt(v, 0));
forward(v, nc);
}else{
nc = tagptr(alloc_words(sz+1), TAG_VECTOR);
vector_setsize(nc, sz);
a = vector_elt(v, 0);
forward(v, nc);
if(sz > 0){
vector_elt(nc, 0) = relocate(a);
for(i = 1; i < sz; i++)
vector_elt(nc, i) = relocate(vector_elt(v, i));
}
}
return nc;
}
if(t == TAG_SYM){
gensym_t *gs = ptr(v);
gensym_t *ng = alloc_words(sizeof(gensym_t)/sizeof(value_t));
ng->id = gs->id;
ng->binding = gs->binding;
nc = tagptr(ng, TAG_SYM);
forward(v, nc);
if(__likely(ng->binding != UNBOUND))
ng->binding = relocate(ng->binding);
return nc;
}
return v;
}
static void
trace_globals(void)
{
const char *k = nil;
symbol_t *v;
while(Tnext(FL(symtab), &k, (void**)&v)){
if(v->binding != UNBOUND)
v->binding = relocate(v->binding);
}
}
void
gc(int mustgrow)
{
void *temp;
uint32_t i, f, top;
fl_readstate_t *rs;
FL(gccalls)++;
FL(curheap) = FL(tospace);
if(FL(grew))
FL(lim) = FL(curheap)+FL(heapsize)*2-sizeof(cons_t);
else
FL(lim) = FL(curheap)+FL(heapsize)-sizeof(cons_t);
if(FL(throwing_frame) > FL(curr_frame)){
top = FL(throwing_frame) - 3;
f = FL(stack)[FL(throwing_frame)-3];
}else{
top = FL(sp);
f = FL(curr_frame);
}
while(1){
for(i = f; i < top; i++)
FL(stack)[i] = relocate(FL(stack)[i]);
if(f == 0)
break;
top = f - 3;
f = FL(stack)[f-3];
}
for(i = 0; i < FL(ngchandles); i++)
*FL(gchandles)[i] = relocate(*FL(gchandles)[i]);
trace_globals();
relocate_typetable();
rs = FL(readstate);
while(rs){
value_t ent;
for(i = 0; i < rs->backrefs.size; i++){
ent = (value_t)rs->backrefs.table[i];
if(ent != (value_t)HT_NOTFOUND)
rs->backrefs.table[i] = (void*)relocate(ent);
}
for(i = 0; i < rs->gensyms.size; i++){
ent = (value_t)rs->gensyms.table[i];
if(ent != (value_t)HT_NOTFOUND)
rs->gensyms.table[i] = (void*)relocate(ent);
}
rs->source = relocate(rs->source);
rs = rs->prev;
}
FL(lasterror) = relocate(FL(lasterror));
FL(memory_exception_value) = relocate(FL(memory_exception_value));
FL(the_empty_vector) = relocate(FL(the_empty_vector));
FL(the_empty_string) = relocate(FL(the_empty_string));
sweep_finalizers();
#if defined(VERBOSEGC)
printf("GC: found %d/%d live conses\n",
(FL(curheap)-FL(tospace))/sizeof(cons_t), FL(heapsize)/sizeof(cons_t));
#endif
temp = FL(tospace);
FL(tospace) = FL(fromspace);
FL(fromspace) = temp;
// 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(FL(grew) || ((FL(lim)-FL(curheap)) < (int)(FL(heapsize)/5)) || mustgrow){
temp = MEM_REALLOC(FL(tospace), FL(heapsize)*2);
if(__unlikely(temp == nil))
fl_raise(FL(memory_exception_value));
FL(tospace) = temp;
if(FL(grew)){
FL(heapsize) *= 2;
temp = bitvector_resize(FL(consflags), 0, FL(heapsize)/sizeof(cons_t), 1);
if(__unlikely(temp == nil))
fl_raise(FL(memory_exception_value));
FL(consflags) = (uint32_t*)temp;
}
FL(grew) = !FL(grew);
}
if(__unlikely((value_t*)FL(curheap) > (value_t*)FL(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.
gc(0);
}
}
static void
grow_stack(void)
{
size_t newsz = FL(nstack) * 2;
value_t *ns = MEM_REALLOC(FL(stack), newsz*sizeof(value_t));
if(__unlikely(ns == nil))
lerrorf(FL_MemoryError, "stack overflow");
FL(stack) = ns;
FL(nstack) = newsz;
}
// utils ----------------------------------------------------------------------
// apply function with n args on the stack
static value_t
_applyn(uint32_t n)
{
value_t f = FL(stack)[FL(sp)-n-1];
uint32_t saveSP = FL(sp);
value_t v;
if(iscbuiltin(f))
v = ((builtin_t*)ptr(f))[3](&FL(stack)[FL(sp)-n], n);
else if(isfunction(f))
v = apply_cl(n);
else if(__likely(isbuiltin(f))){
value_t tab = symbol_value(FL_builtins_table_sym);
if(__unlikely(ptr(tab) == nil))
unbound_error(tab);
FL(stack)[FL(sp)-n-1] = vector_elt(tab, uintval(f));
v = apply_cl(n);
}else{
type_error("function", f);
}
FL(sp) = saveSP;
return v;
}
value_t
fl_apply(value_t f, value_t l)
{
value_t v = l;
uint32_t n = FL(sp);
PUSH(f);
while(iscons(v)){
if(FL(sp) >= FL(nstack))
grow_stack();
PUSH(car_(v));
v = cdr_(v);
}
if(v != FL_nil)
lerrorf(FL_ArgError, "apply: last argument: not a list");
n = FL(sp) - n - 1;
v = _applyn(n);
POPN(n+1);
return v;
}
value_t
fl_applyn(uint32_t n, value_t f, ...)
{
va_list ap;
va_start(ap, f);
size_t i;
PUSH(f);
while(FL(sp)+n >= FL(nstack))
grow_stack();
for(i = 0; i < n; i++){
value_t a = va_arg(ap, value_t);
PUSH(a);
}
value_t v = _applyn(n);
POPN(n+1);
va_end(ap);
return v;
}
value_t
fl_listn(size_t n, ...)
{
va_list ap;
va_start(ap, n);
uint32_t si = FL(sp);
size_t i;
while(FL(sp)+n >= FL(nstack))
grow_stack();
for(i = 0; i < n; i++){
value_t a = va_arg(ap, value_t);
PUSH(a);
}
cons_t *c = alloc_words(n*2);
cons_t *l = c;
for(i = 0; i < n; i++){
c->car = FL(stack)[si++];
c->cdr = tagptr(c+1, TAG_CONS);
c++;
}
c[-1].cdr = FL_nil;
POPN(n);
va_end(ap);
return tagptr(l, TAG_CONS);
}
value_t
fl_list2(value_t a, value_t b)
{
PUSH(a);
PUSH(b);
cons_t *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 = FL_nil;
return tagptr(c, TAG_CONS);
}
value_t
fl_cons(value_t a, value_t b)
{
PUSH(a);
PUSH(b);
value_t c = mk_cons();
cdr_(c) = POP();
car_(c) = POP();
return c;
}
bool
fl_isnumber(value_t v)
{
if(isfixnum(v))
return true;
if(iscprim(v)){
cprim_t *c = ptr(v);
return c->type != FL(runetype) && valid_numtype(c->type->numtype);
}
if(iscvalue(v)){
cvalue_t *c = ptr(v);
return valid_numtype(cp_numtype(c));
}
return false;
}
// eval -----------------------------------------------------------------------
static value_t
list(value_t *args, uint32_t nargs, int star)
{
cons_t *c;
uint32_t i;
value_t v;
v = cons_reserve(nargs);
c = ptr(v);
for(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 = FL_nil;
return v;
}
static value_t
copy_list(value_t L)
{
if(!iscons(L))
return FL_nil;
PUSH(FL_nil);
PUSH(L);
value_t *plcons = &FL(stack)[FL(sp)-2];
value_t *pL = &FL(stack)[FL(sp)-1];
value_t c;
c = mk_cons(); PUSH(c); // save first cons
car_(c) = car_(*pL);
cdr_(c) = FL_nil;
*plcons = c;
*pL = cdr_(*pL);
while(iscons(*pL)){
c = mk_cons();
car_(c) = car_(*pL);
cdr_(c) = FL_nil;
cdr_(*plcons) = c;
*plcons = c;
*pL = cdr_(*pL);
}
c = POP(); // first cons
POPN(2);
return c;
}
static value_t
do_trycatch(void)
{
uint32_t saveSP = FL(sp);
value_t v = FL_nil;
value_t thunk = FL(stack)[FL(sp)-2];
FL(stack)[FL(sp)-2] = FL(stack)[FL(sp)-1];
FL(stack)[FL(sp)-1] = thunk;
FL_TRY{
v = apply_cl(0);
}
FL_CATCH{
v = FL(stack)[saveSP-2];
PUSH(v);
PUSH(FL(lasterror));
v = apply_cl(1);
}
FL(sp) = saveSP;
return v;
}
/*
argument layout on stack is
|--required args--|--opt args--|--kw args--|--rest args...
*/
static uint32_t
process_keys(value_t kwtable, uint32_t nreq, uint32_t nkw, uint32_t nopt, uint32_t bp, uint32_t nargs, int va)
{
uint32_t extr = nopt+nkw;
uint32_t ntot = nreq+extr;
value_t args[64], v = FL_nil;
uint32_t i, a = 0, nrestargs;
value_t s1 = FL(stack)[FL(sp)-1];
value_t s3 = FL(stack)[FL(sp)-3];
value_t s4 = FL(stack)[FL(sp)-4];
if(__unlikely(nargs < nreq))
lerrorf(FL_ArgError, "too few arguments");
if(__unlikely(extr > nelem(args)))
lerrorf(FL_ArgError, "too many arguments");
for(i = 0; i < extr; i++)
args[i] = UNBOUND;
for(i = nreq; i < nargs; i++){
v = FL(stack)[bp+i];
if(issymbol(v) && iskeyword((symbol_t*)ptr(v)))
break;
if(a >= nopt)
goto no_kw;
args[a++] = v;
}
if(i >= nargs)
goto no_kw;
// now process keywords
uintptr_t n = vector_size(kwtable)/2;
do{
i++;
if(__unlikely(i >= nargs))
lerrorf(FL_ArgError, "keyword %s requires an argument", symbol_name(v));
value_t hv = fixnum(((symbol_t*)ptr(v))->hash);
fixnum_t lx = numval(hv);
uintptr_t x = 2*((lx < 0 ? -lx : lx) % n);
if(__likely(vector_elt(kwtable, x) == v)){
uintptr_t idx = numval(vector_elt(kwtable, x+1));
assert(idx < nkw);
idx += nopt;
if(args[idx] == UNBOUND){
// if duplicate key, keep first value
args[idx] = FL(stack)[bp+i];
}
}else{
lerrorf(FL_ArgError, "unsupported keyword %s", symbol_name(v));
}
i++;
if(i >= nargs)
break;
v = FL(stack)[bp+i];
}while(issymbol(v) && iskeyword((symbol_t*)ptr(v)));
no_kw:
nrestargs = nargs - i;
if(__unlikely(!va && nrestargs > 0))
lerrorf(FL_ArgError, "too many arguments");
nargs = ntot + nrestargs;
if(nrestargs)
memmove(&FL(stack)[bp+ntot], &FL(stack)[bp+i], nrestargs*sizeof(value_t));
memmove(&FL(stack)[bp+nreq], args, extr*sizeof(value_t));
FL(sp) = bp + nargs;
assert(FL(sp) < FL(nstack)-4);
PUSH(s4);
PUSH(s3);
PUSH(nargs);
PUSH(s1);
FL(curr_frame) = FL(sp);
return nargs;
}
#define GET_INT32(a) \
((int32_t) \
((((uint32_t)a[0])<<0) | \
(((uint32_t)a[1])<<8) | \
(((uint32_t)a[2])<<16) | \
(((uint32_t)a[3])<<24)))
#define GET_INT16(a) \
((int16_t) \
((((int16_t)a[0])<<0) | \
(((int16_t)a[1])<<8)))
#define PUT_INT32(a, i) \
do{ \
((uint8_t*)(a))[0] = ((uint32_t)(i)>>0)&0xff; \
((uint8_t*)(a))[1] = ((uint32_t)(i)>>8)&0xff; \
((uint8_t*)(a))[2] = ((uint32_t)(i)>>16)&0xff; \
((uint8_t*)(a))[3] = ((uint32_t)(i)>>24)&0xff; \
}while(0)
/*
stack on entry: <func> <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 value_t
apply_cl(uint32_t nargs)
{
uint32_t top_frame = FL(curr_frame);
uint32_t n, bp;
const uint8_t *ip;
fixnum_t s, hi;
bool tail;
// temporary variables (not necessary to preserve across calls)
size_t isz;
uint32_t i, ipd;
symbol_t *sym;
cons_t *c;
value_t *pv;
value_t func, v, e;
int x;
n = 0;
v = 0;
USED(n);
USED(v);
apply_cl_top:
bp = FL(sp)-nargs;
func = FL(stack)[bp-1];
ip = cvalue_data(fn_bcode(func));
assert(!ismanaged((uintptr_t)ip));
i = FL(sp)+GET_INT32(ip);
while(i >= FL(nstack))
grow_stack();
ip += 4;
PUSH(fn_env(func));
PUSH(FL(curr_frame));
PUSH(nargs);
ipd = FL(sp);
FL(sp)++; // ip
FL(curr_frame) = FL(sp);
#if defined(COMPUTED_GOTO)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpedantic"
static const void *ops[] = {
#define GOTO_OP_OFFSET(op) [op] = &&op_##op
#include "vm_goto.inc"
#undef GOTO_OP_OFFSET
};
#define NEXT_OP goto *ops[*ip++]
#define LABEL(x) x
#define OP(x) op_##x:
NEXT_OP;
#include "vm.inc"
#undef OP
#undef LABEL
#undef NEXT_OP
#pragma GCC diagnostic pop
#else /* just a usual (portable) switch/case */
uint8_t op = *ip++;
while(1){
switch(op){
#define NEXT_OP break
#define LABEL(x) x
#define OP(x) case x:
#include "vm.inc"
#undef OP
#undef LABEL
#undef NEXT_OP
}
op = *ip++;
}
#endif
}
#define SWAP_INT32(a)
#define SWAP_INT16(a)
#include "maxstack.inc"
#if BYTE_ORDER == BIG_ENDIAN
#undef SWAP_INT32
#undef SWAP_INT16
#define SWAP_INT32(a) \
do{ \
uint8_t *x = (void*)a, y; \
y = x[0]; x[0] = x[3]; x[3] = y; \
y = x[1]; x[1] = x[2]; x[2] = y; \
}while(0)
#define SWAP_INT16(a) \
do{ \
uint8_t *x = (void*)a, y; \
y = x[0]; x[0] = x[1]; x[1] = y; \
}while(0)
#define compute_maxstack compute_maxstack_swap
#include "maxstack.inc"
#undef compute_maxstack
#else
#endif
// top = top frame pointer to start at
static value_t
_stacktrace(uint32_t top)
{
value_t lst = FL_nil;
fl_gc_handle(&lst);
while(top > 0){
const uint8_t *ip1 = (void*)FL(stack)[top-1];
uint32_t sz = FL(stack)[top-2]+1;
uint32_t bp = top-4-sz;
value_t func = FL(stack)[bp];
const uint8_t *ip0 = cvalue_data(fn_bcode(func));
intptr_t ip = ip1 - ip0 - 1; /* -1: ip1 is *after* the one that was being executed */
value_t v = alloc_vector(sz+1, 0);
vector_elt(v, 0) = fixnum(ip);
vector_elt(v, 1) = func;
for(uint32_t i = 1; i < sz; i++){
value_t si = FL(stack)[bp+i];
// if there's an error evaluating argument defaults some slots
// might be left set to UNBOUND
vector_elt(v, i+1) = si == UNBOUND ? FL_void : si;
}
lst = fl_cons(v, lst);
top = FL(stack)[top-3];
}
fl_free_gc_handles(1);
return lst;
}
// builtins -------------------------------------------------------------------
BUILTIN("gc", gc)
{
USED(args);
argcount(nargs, 0);
gc(0);
return FL_void;
}
BUILTIN("function", function)
{
if(nargs == 1 && issymbol(args[0]))
return fn_builtin_builtin(args, nargs);
if(nargs < 2 || nargs > 4)
argcount(nargs, 2);
if(__unlikely(!fl_isstring(args[0])))
type_error("string", args[0]);
if(__unlikely(!isvector(args[1])))
type_error("vector", args[1]);
cvalue_t *arr = (cvalue_t*)ptr(args[0]);
cv_pin(arr);
char *data = cv_data(arr);
int ms;
if((uint8_t)data[4] >= N_OPCODES){
// read syntax, shifted 48 for compact text representation
size_t i, sz = cv_len(arr);
for(i = 0; i < sz; i++)
data[i] -= 48;
#if BYTE_ORDER == BIG_ENDIAN
ms = compute_maxstack((uint8_t*)data, cv_len(arr));
}else{
ms = compute_maxstack_swap((uint8_t*)data, cv_len(arr));
}
#else
}
ms = compute_maxstack((uint8_t*)data, cv_len(arr));
#endif
if(ms < 0)
lerrorf(FL_ArgError, "invalid bytecode");
PUT_INT32(data, ms);
function_t *fn = alloc_words(4);
value_t fv = tagptr(fn, TAG_FUNCTION);
fn->bcode = args[0];
fn->vals = args[1];
fn->env = FL_nil;
fn->name = FL_lambda;
if(nargs > 2){
if(issymbol(args[2])){
fn->name = args[2];
if(nargs > 3)
fn->env = args[3];
}else{
fn->env = args[2];
if(nargs > 3){
if(__unlikely(!issymbol(args[3])))
type_error("symbol", args[3]);
fn->name = args[3];
}
}
if(__unlikely(isgensym(fn->name)))
lerrorf(FL_ArgError, "name should not be a gensym");
}
return fv;
}
BUILTIN("function:code", function_code)
{
argcount(nargs, 1);
value_t v = args[0];
if(__unlikely(!isclosure(v)))
type_error("function", v);
return fn_bcode(v);
}
BUILTIN("function:vals", function_vals)
{
argcount(nargs, 1);
value_t v = args[0];
if(__unlikely(!isclosure(v)))
type_error("function", v);
return fn_vals(v);
}
BUILTIN("function:env", function_env)
{
argcount(nargs, 1);
value_t v = args[0];
if(__unlikely(!isclosure(v)))
type_error("function", v);
return fn_env(v);
}
BUILTIN("function:name", function_name)
{
argcount(nargs, 1);
value_t v = args[0];
if(isclosure(v))
return fn_name(v);
if(isbuiltin(v))
return symbol(builtins[uintval(v)].name, false);
if(iscbuiltin(v)){
v = (value_t)ptrhash_get(&FL(reverse_dlsym_lookup_table), (cvalue_t*)ptr(v));
if(v == (value_t)HT_NOTFOUND)
return FL_f;
return v;
}
type_error("function", v);
}
BUILTIN("copy-list", copy_list)
{
argcount(nargs, 1);
return copy_list(args[0]);
}
BUILTIN("append", append)
{
value_t first = FL_nil, lst, lastcons = FL_nil;
uint32_t i;
if(nargs == 0)
return FL_nil;
fl_gc_handle(&first);
fl_gc_handle(&lastcons);
for(i = 0; i < nargs; i++){
lst = args[i];
if(iscons(lst)){
lst = copy_list(lst);
if(first == FL_nil)
first = lst;
else
cdr_(lastcons) = lst;
lastcons = tagptr((((cons_t*)FL(curheap))-1), TAG_CONS);
}else if(lst != FL_nil){
type_error("cons", lst);
}
}
fl_free_gc_handles(2);
return first;
}
BUILTIN("list*", liststar)
{
if(nargs == 1)
return args[0];
if(nargs == 0)
argcount(nargs, 1);
return list(args, nargs, 1);
}
BUILTIN("stacktrace", stacktrace)
{
USED(args);
argcount(nargs, 0);
return _stacktrace(FL(throwing_frame) ? FL(throwing_frame) : FL(curr_frame));
}
BUILTIN("map", map)
{
if(__unlikely(nargs < 2))
lerrorf(FL_ArgError, "too few arguments");
intptr_t argSP = args-FL(stack);
assert(argSP >= 0 && argSP < FL(nstack));
while(FL(sp)+2+1+nargs >= FL(nstack))
grow_stack();
uint32_t k = FL(sp);
PUSH(FL_nil);
PUSH(FL_nil);
for(bool first = true;;){
PUSH(FL(stack)[argSP]);
for(uint32_t i = 1; i < nargs; i++){
if(!iscons(FL(stack)[argSP+i])){
POPN(2+i);
return FL(stack)[k+1];
}
PUSH(car(FL(stack)[argSP+i]));
FL(stack)[argSP+i] = cdr_(FL(stack)[argSP+i]);
}
value_t v = _applyn(nargs-1);
POPN(nargs);
PUSH(v);
value_t c = mk_cons();
car_(c) = POP(); cdr_(c) = FL_nil;
if(first)
FL(stack)[k+1] = c;
else
cdr_(FL(stack)[k]) = c;
FL(stack)[k] = c;
first = false;
}
}
BUILTIN("for-each", for_each)
{
if(__unlikely(nargs < 2))
lerrorf(FL_ArgError, "too few arguments");
intptr_t argSP = args-FL(stack);
assert(argSP >= 0 && argSP < FL(nstack));
if(FL(sp)+1+2*nargs >= FL(nstack))
grow_stack();
for(size_t n = 0;; n++){
PUSH(FL(stack)[argSP]);
uint32_t pargs = 0;
for(uint32_t i = 1; i < nargs; i++, pargs++){
value_t v = FL(stack)[argSP+i];
if(iscons(v)){
PUSH(car_(v));
FL(stack)[argSP+i] = cdr_(v);
continue;
}
if(isvector(v)){
size_t sz = vector_size(v);
if(n < sz){
PUSH(vector_elt(v, n));
continue;
}
}
if(isarray(v)){
size_t sz = cvalue_arraylen(v);
if(n < sz){
value_t a[2];
a[0] = v;
a[1] = fixnum(n);
PUSH(cvalue_array_aref(a));
continue;
}
}
if(ishashtable(v)){
htable_t *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((value_t)table[h->i]);
pargs++;
PUSH((value_t)table[h->i+1]);
h->i += 2;
continue;
}
h->i = 0;
}
POPN(pargs+1);
return FL_void;
}
_applyn(pargs);
POPN(pargs+1);
}
}
BUILTIN("sleep", fl_sleep)
{
if(nargs > 1)
argcount(nargs, 1);
double s = nargs > 0 ? todouble(args[0]) : 0;
sleep_ms(s * 1000.0);
return FL_void;
}
BUILTIN("vm-stats", vm_stats)
{
USED(args);
argcount(nargs, 0);
ios_printf(ios_stderr, "heap total %10"PRIu32"\n", FL(heapsize));
ios_printf(ios_stderr, "heap free %10"PRIu32"\n", (uint32_t)(FL(lim)-FL(curheap)));
ios_printf(ios_stderr, "heap used %10"PRIu32"\n", (uint32_t)(FL(curheap)-FL(fromspace)));
ios_printf(ios_stderr, "stack %10"PRIu32"\n", FL(nstack)*sizeof(value_t));
ios_printf(ios_stderr, "gc calls %10"PRIu64"\n", (uint64_t)FL(gccalls));
ios_printf(ios_stderr, "max finalizers %10"PRIu32"\n", (uint32_t)FL(maxfinalizers));
ios_printf(ios_stderr, "opcodes %10d\n", N_OPCODES);
return FL_void;
}
static const builtinspec_t builtin_fns[] = {
#define BUILTIN_FN(l, c){l, fn_builtin_##c},
#include "builtin_fns.h"
#undef BUILTIN_FN
};
// initialization -------------------------------------------------------------
void
fl_init(size_t initial_heapsize)
{
int i;
fl = MEM_CALLOC(1, sizeof(*fl));
FL(scr_width) = 100;
FL(heapsize) = initial_heapsize;
FL(fromspace) = MEM_ALLOC(FL(heapsize));
FL(tospace) = MEM_ALLOC(FL(heapsize));
FL(curheap) = FL(fromspace);
FL(lim) = FL(curheap)+FL(heapsize)-sizeof(cons_t);
FL(consflags) = bitvector_new(FL(heapsize)/sizeof(cons_t), 1);
htable_new(&FL(printconses), 32);
comparehash_init();
FL(nstack) = 4096;
FL(stack) = MEM_ALLOC(FL(nstack)*sizeof(value_t));
FL_lambda = symbol("λ", false);
FL_function = symbol("function", false);
FL_quote = symbol("quote", false);
FL_trycatch = symbol("trycatch", false);
FL_backquote = symbol("quasiquote", false);
FL_comma = symbol("unquote", false);
FL_commaat = symbol("unquote-splicing", false);
FL_commadot = symbol("unquote-nsplicing", false);
FL_IOError = symbol("io-error", false);
FL_ParseError = symbol("parse-error", false);
FL_TypeError = symbol("type-error", false);
FL_ArgError = symbol("arg-error", false);
FL_UnboundError = symbol("unbound-error", false);
FL_KeyError = symbol("key-error", false);
FL_MemoryError = symbol("memory-error", false);
FL_BoundsError = symbol("bounds-error", false);
FL_DivideError = symbol("divide-error", false);
FL_EnumerationError = symbol("enumeration-error", false);
FL_Error = symbol("error", false);
FL_conssym = symbol("cons", false);
FL_symbolsym = symbol("symbol", false);
FL_fixnumsym = symbol("fixnum", false);
FL_vectorsym = symbol("vector", false);
FL_builtinsym = symbol("builtin", false);
FL_booleansym = symbol("boolean", false);
FL_nullsym = symbol("null", false);
FL_definesym = symbol("define", false);
FL_defmacrosym = symbol("define-macro", false);
FL_forsym = symbol("for", false);
FL_setqsym = symbol("set!", false);
FL_evalsym = symbol("eval", false);
FL_vu8sym = symbol("vu8", false);
FL_fnsym = symbol("fn", false);
FL_nulsym = symbol("nul", false);
FL_alarmsym = symbol("alarm", false);
FL_backspacesym = symbol("backspace", false);
FL_tabsym = symbol("tab", false);
FL_linefeedsym = symbol("linefeed", false);
FL_vtabsym = symbol("vtab", false);
FL_pagesym = symbol("page", false);
FL_returnsym = symbol("return", false);
FL_escsym = symbol("esc", false);
FL_spacesym = symbol("space", false);
FL_deletesym = symbol("delete", false);
FL_newlinesym = symbol("newline", false);
FL_tsym = symbol("t", false);
FL_Tsym = symbol("T", false);
FL_fsym = symbol("f", false);
FL_Fsym = symbol("F", false);
FL_builtins_table_sym = symbol("*builtins*", false);
set(FL_printprettysym = symbol("*print-pretty*", false), FL_t);
set(FL_printreadablysym = symbol("*print-readably*", false), FL_t);
set(FL_printwidthsym = symbol("*print-width*", false), fixnum(FL(scr_width)));
set(FL_printlengthsym = symbol("*print-length*", false), FL_f);
set(FL_printlevelsym = symbol("*print-level*", false), FL_f);
FL(lasterror) = FL_nil;
for(i = 0; i < nelem(builtins); i++){
if(builtins[i].name)
set(symbol(builtins[i].name, false), builtin(i));
}
set(symbol("procedure?", false), builtin(OP_FUNCTIONP));
set(symbol("top-level-bound?", false), builtin(OP_BOUNDP));
FL(the_empty_vector) = tagptr(alloc_words(1), TAG_VECTOR);
vector_setsize(FL(the_empty_vector), 0);
cvalues_init();
set(symbol("*os-name*", false), cvalue_static_cstring(__os_name__));
FL(memory_exception_value) = fl_list2(FL_MemoryError, cvalue_static_cstring("out of memory"));
const builtinspec_t *b;
for(i = 0, b = builtin_fns; i < nelem(builtin_fns); i++, b++)
set(symbol(b->name, false), cbuiltin(b->name, b->fptr));
table_init();
iostream_init();
fsixel_init();
compress_init();
}
// top level ------------------------------------------------------------------
value_t
fl_toplevel_eval(value_t expr)
{
return fl_applyn(1, symbol_value(FL_evalsym), expr);
}
int
fl_load_system_image(value_t sys_image_iostream)
{
value_t e;
uint32_t saveSP;
symbol_t *sym;
PUSH(sys_image_iostream);
saveSP = FL(sp);
FL_TRY{
while(1){
e = fl_read_sexpr(FL(stack)[FL(sp)-1]);
if(ios_eof(value2c(ios_t*, FL(stack)[FL(sp)-1])))
break;
if(isfunction(e)){
// stage 0 format: series of thunks
PUSH(e);
(void)_applyn(0);
FL(sp) = saveSP;
}else{
// stage 1 format: list alternating symbol/value
while(iscons(e)){
sym = tosymbol(car_(e));
e = cdr_(e);
(void)tocons(e);
sym->binding = car_(e);
e = cdr_(e);
}
break;
}
}
}
FL_CATCH_NO_INC{
ios_puts(ios_stderr, "fatal error during bootstrap: ");
fl_print(ios_stderr, FL(lasterror));
ios_putc(ios_stderr, '\n');
return 1;
}
ios_close(value2c(ios_t*, FL(stack)[FL(sp)-1]));
POPN(1);
return 0;
}