Add tail call optimization to dc

This took a bit to do, but it basically stores how many tail calls have
happened at the current spot on the stack. And when a quit happens, it
takes the tail calls into account.

I don't have to worry about storing the tail call optimized strings
because they would have just quit anyway, so I can just act as though I
quit all of them.

2 files changed, 63 insertions, 27 deletions

diff --git a/include/program.h b/include/program.h
index 3a527a26..726fc8f6 100644
--- a/include/program.h
+++ b/include/program.h
@@ -55,11 +55,6 @@ typedef struct BcProgram {
 	BcBigDig globals[BC_PROG_GLOBALS_LEN];
 	BcVec globals_v[BC_PROG_GLOBALS_LEN];
 
-#if DC_ENABLED
-	BcBigDig strm;
-	BcNum strmb;
-#endif // DC_ENABLED
-
 	BcVec results;
 	BcVec stack;
 
@@ -74,6 +69,13 @@ typedef struct BcProgram {
 	BcVec arrs;
 	BcVec arr_map;
 
+#if DC_ENABLED
+	BcVec tail_calls;
+
+	BcBigDig strm;
+	BcNum strmb;
+#endif // DC_ENABLED
+
 	BcNum one;
 
 #if BC_ENABLED
diff --git a/src/program.c b/src/program.c
index 1d93da7b..fb73dee7 100644
--- a/src/program.c
+++ b/src/program.c
@@ -473,6 +473,12 @@ static BcStatus bc_program_read(BcProgram *p) {
 
 	bc_vec_pushByte(&f->code, vm->read_ret);
 	bc_vec_push(&p->stack, &ip);
+#if DC_ENABLED
+	if (!BC_IS_BC) {
+		size_t temp = 0;
+		bc_vec_push(&p->tail_calls, &temp);
+	}
+#endif // DC_ENABLED
 
 exec_err:
 	bc_parse_free(&parse);
@@ -1378,31 +1384,47 @@ static BcStatus bc_program_printStream(BcProgram *p) {
 	return s;
 }
 
-static BcStatus bc_program_nquit(BcProgram *p) {
+static BcStatus bc_program_nquit(BcProgram *p, uchar inst) {
 
 	BcStatus s;
 	BcResult *opnd;
 	BcNum *num;
 	BcBigDig val;
+	size_t i;
 
-	s = bc_program_prep(p, &opnd, &num);
-	if (BC_ERR(s)) return s;
-	s = bc_num_bigdig(num, &val);
-	if (BC_ERR(s)) return s;
+	assert(p->stack.len == p->tail_calls.len);
 
-	bc_vec_pop(&p->results);
+	if (inst == BC_INST_QUIT) {
+		val = 2;
+		s = BC_STATUS_SUCCESS;
+	}
+	else {
 
-	s = bc_program_checkStack(&p->stack, val);
-	if (BC_ERR(s)) return s;
-	else if (p->stack.len == val) return BC_STATUS_QUIT;
+		s = bc_program_prep(p, &opnd, &num);
+		if (BC_ERR(s)) return s;
+		s = bc_num_bigdig(num, &val);
+		if (BC_ERR(s)) return s;
+
+		bc_vec_pop(&p->results);
+	}
+
+	for (i = 0; val && i < p->tail_calls.len; ++i) {
+		size_t calls = *((size_t*) bc_vec_item_rev(&p->tail_calls, i)) + 1;
+		if (calls >= val) val = 0;
+		else val -= calls;
+	}
 
-	bc_vec_npop(&p->stack, val);
+	if (i == p->stack.len) s = BC_STATUS_QUIT;
+	else {
+		bc_vec_npop(&p->stack, i);
+		bc_vec_npop(&p->tail_calls, i);
+	}
 
 	return s;
 }
 
 static BcStatus bc_program_execStr(BcProgram *p, const char *restrict code,
-                                   size_t *restrict bgn, bool cond)
+                                   size_t *restrict bgn, bool cond, size_t len)
 {
 	BcStatus s = BC_STATUS_SUCCESS;
 	BcResult *r;
@@ -1414,6 +1436,8 @@ static BcStatus bc_program_execStr(BcProgram *p, const char *restrict code,
 	BcNum *n;
 	bool exec;
 
+	assert(p->stack.len == p->tail_calls.len);
+
 	s = bc_program_operand(p, &r, &n, 0);
 	if (BC_ERR(s)) return s;
 
@@ -1478,6 +1502,15 @@ static BcStatus bc_program_execStr(BcProgram *p, const char *restrict code,
 	ip.func = fidx;
 
 	bc_vec_pop(&p->results);
+
+	// Tail call.
+	if (p->stack.len > 1 && *bgn == len - 1 && code[*bgn] == BC_INST_POP_EXEC) {
+		size_t *call_ptr = bc_vec_top(&p->tail_calls);
+		*call_ptr += 1;
+		bc_vec_pop(&p->stack);
+	}
+	else bc_vec_push(&p->tail_calls, &ip.idx);
+
 	bc_vec_push(&p->stack, &ip);
 
 	return BC_STATUS_SUCCESS;
@@ -1546,6 +1579,10 @@ void bc_program_free(BcProgram *p) {
 		bc_num_free(&p->last);
 	}
 #endif // BC_ENABLED
+
+#if DC_ENABLED
+	if (!BC_IS_BC) bc_vec_free(&p->tail_calls);
+#endif // DC_ENABLED
 }
 #endif // NDEBUG
 
@@ -1569,6 +1606,11 @@ void bc_program_init(BcProgram *p) {
 
 #if DC_ENABLED
 	if (!BC_IS_BC) {
+
+		bc_vec_init(&p->tail_calls, sizeof(size_t), NULL);
+		i = 0;
+		bc_vec_push(&p->tail_calls, &i);
+
 		p->strm = UCHAR_MAX + 1;
 		bc_num_setup(&p->strmb, p->strmb_num, BC_NUM_BIGDIG_LOG10);
 		bc_num_bigdig2num(&p->strmb, p->strm);
@@ -1920,6 +1962,7 @@ BcStatus bc_program_exec(BcProgram *p) {
 			{
 				assert(BC_PROG_STACK(&p->stack, 2));
 				bc_vec_pop(&p->stack);
+				bc_vec_pop(&p->tail_calls);
 				ip = bc_vec_top(&p->stack);
 				func = bc_vec_item(&p->fns, ip->func);
 				code = func->code.v;
@@ -1942,7 +1985,7 @@ BcStatus bc_program_exec(BcProgram *p) {
 			case BC_INST_EXEC_COND:
 			{
 				cond = (inst == BC_INST_EXEC_COND);
-				s = bc_program_execStr(p, code, &ip->idx, cond);
+				s = bc_program_execStr(p, code, &ip->idx, cond, func->code.len);
 				ip = bc_vec_top(&p->stack);
 				func = bc_vec_item(&p->fns, ip->func);
 				code = func->code.v;
@@ -2024,18 +2067,9 @@ BcStatus bc_program_exec(BcProgram *p) {
 			}
 
 			case BC_INST_QUIT:
-			{
-				if (p->stack.len <= 2) s = BC_STATUS_QUIT;
-				else bc_vec_npop(&p->stack, 2);
-				ip = bc_vec_top(&p->stack);
-				func = bc_vec_item(&p->fns, ip->func);
-				code = func->code.v;
-				break;
-			}
-
 			case BC_INST_NQUIT:
 			{
-				s = bc_program_nquit(p);
+				s = bc_program_nquit(p, inst);
 				ip = bc_vec_top(&p->stack);
 				func = bc_vec_item(&p->fns, ip->func);
 				code = func->code.v;