bc: implement pass-by-reference code from upstream

function                                             old     new   delta
zxc_program_popResultAndCopyToVar                    298     493    +195
bc_vec_pushIndex                                       -      75     +75
zxc_vm_process                                       859     928     +69
xc_program_dereference                                 -      66     +66
bc_vec_npush                                           -      65     +65
zbc_num_s                                            239     249     +10
zxc_program_num                                     1024    1032      +8
zbc_num_divmod                                       150     156      +6
xc_program_search                                    143     146      +3
zxc_program_assign                                   392     389      -3
zdc_program_execStr                                  520     517      -3
xc_program_pushVar                                   198     195      -3
zxc_program_exec                                    4101    4092      -9
zbc_program_call                                     318     308     -10
zbc_func_insert                                      120     104     -16
zbc_parse_stmt_possibly_auto                        1460    1439     -21
bc_vec_push                                           53      12     -41
xc_parse_pushIndex                                    61      18     -43
------------------------------------------------------------------------------
(add/remove: 3/0 grow/shrink: 6/9 up/down: 497/-149)          Total: 348 bytes

Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>

1 files changed, 185 insertions, 86 deletions

diff --git a/miscutils/bc.c b/miscutils/bc.c
index 7fecb264d..36e978ed8 100644
--- a/miscutils/bc.c
+++ b/miscutils/bc.c
@@ -4,8 +4,8 @@
  * Adapted from https://github.com/gavinhoward/bc
  * Original code copyright (c) 2018 Gavin D. Howard and contributors.
  */
-//TODO: GNU extensions:
-// support "define f(*param[])" - "pass array by reference" syntax
+//TODO:
+// maybe implement a^b for non-integer b?
 
 #define DEBUG_LEXER   0
 #define DEBUG_COMPILE 0
@@ -380,6 +380,12 @@ typedef struct BcInstPtr {
 	size_t inst_idx;
 } BcInstPtr;
 
+typedef enum BcType {
+	BC_TYPE_VAR,
+	BC_TYPE_ARRAY,
+	BC_TYPE_REF,
+} BcType;
+
 typedef enum BcLexType {
 	XC_LEX_EOF,
 	XC_LEX_INVALID,
@@ -1092,15 +1098,25 @@ static void bc_vec_pop_all(BcVec *v)
 	bc_vec_npop(v, v->len);
 }
 
-static size_t bc_vec_push(BcVec *v, const void *data)
+static size_t bc_vec_npush(BcVec *v, size_t n, const void *data)
 {
 	size_t len = v->len;
-	if (len >= v->cap) bc_vec_grow(v, 1);
-	memmove(v->v + (v->size * len), data, v->size);
-	v->len++;
+	if (len + n > v->cap) bc_vec_grow(v, n);
+	memmove(v->v + (v->size * len), data, v->size * n);
+	v->len = len + n;
 	return len;
 }
 
+static size_t bc_vec_push(BcVec *v, const void *data)
+{
+	return bc_vec_npush(v, 1, data);
+	//size_t len = v->len;
+	//if (len >= v->cap) bc_vec_grow(v, 1);
+	//memmove(v->v + (v->size * len), data, v->size);
+	//v->len = len + 1;
+	//return len;
+}
+
 // G.prog.results often needs "pop old operand, push result" idiom.
 // Can do this without a few extra ops
 static size_t bc_result_pop_and_push(const void *data)
@@ -3528,14 +3544,14 @@ static void xc_parse_pushName(char *name)
 // (The above describes 32-bit case).
 #define SMALL_INDEX_LIMIT (0x100 - sizeof(size_t))
 
-static void xc_parse_pushIndex(size_t idx)
+static void bc_vec_pushIndex(BcVec *v, size_t idx)
 {
 	size_t mask;
 	unsigned amt;
 
 	dbg_lex("%s:%d pushing index %zd", __func__, __LINE__, idx);
 	if (idx < SMALL_INDEX_LIMIT) {
-		xc_parse_push(idx);
+		bc_vec_pushByte(v, idx);
 		return;
 	}
 
@@ -3548,14 +3564,19 @@ static void xc_parse_pushIndex(size_t idx)
 	}
 	// amt is at least 1 here - "one byte of length data follows"
 
-	xc_parse_push((SMALL_INDEX_LIMIT - 1) + amt);
+	bc_vec_pushByte(v, (SMALL_INDEX_LIMIT - 1) + amt);
 
 	do {
-		xc_parse_push((unsigned char)idx);
+		bc_vec_pushByte(v, (unsigned char)idx);
 		idx >>= 8;
 	} while (idx != 0);
 }
 
+static void xc_parse_pushIndex(size_t idx)
+{
+	bc_vec_pushIndex(&G.prs.func->code, idx);
+}
+
 static void xc_parse_pushInst_and_Index(unsigned inst, size_t idx)
 {
 	xc_parse_push(inst);
@@ -4340,7 +4361,7 @@ static BC_STATUS zbc_parse_break_or_continue(BcLexType type)
 }
 #define zbc_parse_break_or_continue(...) (zbc_parse_break_or_continue(__VA_ARGS__) COMMA_SUCCESS)
 
-static BC_STATUS zbc_func_insert(BcFunc *f, char *name, bool var)
+static BC_STATUS zbc_func_insert(BcFunc *f, char *name, BcType type)
 {
 	BcId *autoid;
 	BcId a;
@@ -4349,13 +4370,13 @@ static BC_STATUS zbc_func_insert(BcFunc *f, char *name, bool var)
 	autoid = (void*)f->autos.v;
 	for (i = 0; i < f->autos.len; i++, autoid++) {
 		if (strcmp(name, autoid->name) == 0
-		 && var == autoid->idx
+		 && type == (BcType) autoid->idx
 		) {
 			RETURN_STATUS(bc_error("duplicate function parameter or auto name"));
 		}
 	}
 
-	a.idx = var;
+	a.idx = type;
 	a.name = name;
 
 	bc_vec_push(&f->autos, &a);
@@ -4368,7 +4389,7 @@ static BC_STATUS zbc_parse_funcdef(void)
 {
 	BcParse *p = &G.prs;
 	BcStatus s;
-	bool var, comma, voidfunc;
+	bool comma, voidfunc;
 	char *name;
 
 	dbg_lex_enter("%s:%d entered", __func__, __LINE__);
@@ -4406,6 +4427,16 @@ static BC_STATUS zbc_parse_funcdef(void)
 
 	comma = false;
 	while (p->lex != BC_LEX_RPAREN) {
+		BcType t = BC_TYPE_VAR;
+
+		if (p->lex == XC_LEX_OP_MULTIPLY) {
+			t = BC_TYPE_REF;
+			s = zxc_lex_next();
+			if (s) RETURN_STATUS(s);
+			s = zbc_POSIX_does_not_allow("references");
+			if (s) RETURN_STATUS(s);
+		}
+
 		if (p->lex != XC_LEX_NAME)
 			RETURN_STATUS(bc_error_bad_function_definition());
 
@@ -4415,9 +4446,8 @@ static BC_STATUS zbc_parse_funcdef(void)
 		s = zxc_lex_next();
 		if (s) goto err;
 
-		var = p->lex != BC_LEX_LBRACKET;
-
-		if (!var) {
+		if (p->lex == BC_LEX_LBRACKET) {
+			if (t == BC_TYPE_VAR) t = BC_TYPE_ARRAY;
 			s = zxc_lex_next();
 			if (s) goto err;
 
@@ -4429,6 +4459,10 @@ static BC_STATUS zbc_parse_funcdef(void)
 			s = zxc_lex_next();
 			if (s) goto err;
 		}
+		else if (t == BC_TYPE_REF) {
+			s = bc_error_at("vars can't be references");
+			goto err;
+		}
 
 		comma = p->lex == BC_LEX_COMMA;
 		if (comma) {
@@ -4436,7 +4470,7 @@ static BC_STATUS zbc_parse_funcdef(void)
 			if (s) goto err;
 		}
 
-		s = zbc_func_insert(p->func, name, var);
+		s = zbc_func_insert(p->func, name, t);
 		if (s) goto err;
 	}
 
@@ -4488,7 +4522,7 @@ static BC_STATUS zbc_parse_auto(void)
 	if (s) RETURN_STATUS(s);
 
 	for (;;) {
-		bool var;
+		BcType t;
 
 		if (p->lex != XC_LEX_NAME)
 			RETURN_STATUS(bc_error_at("bad 'auto' syntax"));
@@ -4497,8 +4531,9 @@ static BC_STATUS zbc_parse_auto(void)
 		s = zxc_lex_next();
 		if (s) goto err;
 
-		var = (p->lex != BC_LEX_LBRACKET);
-		if (!var) {
+		t = BC_TYPE_VAR;
+		if (p->lex == BC_LEX_LBRACKET) {
+			t = BC_TYPE_ARRAY;
 			s = zxc_lex_next();
 			if (s) goto err;
 
@@ -4510,7 +4545,7 @@ static BC_STATUS zbc_parse_auto(void)
 			if (s) goto err;
 		}
 
-		s = zbc_func_insert(p->func, name, var);
+		s = zbc_func_insert(p->func, name, t);
 		if (s) goto err;
 
 		if (p->lex == XC_LEX_NLINE
@@ -5119,12 +5154,64 @@ static BC_STATUS zdc_parse_exprs_until_eof(void)
 #define STACK_HAS_MORE_THAN(s, n)          ((s)->len > ((size_t)(n)))
 #define STACK_HAS_EQUAL_OR_MORE_THAN(s, n) ((s)->len >= ((size_t)(n)))
 
-static BcVec* xc_program_search(char *id, bool var)
+static size_t xc_program_index(char *code, size_t *bgn)
+{
+	unsigned char *bytes = (void*)(code + *bgn);
+	unsigned amt;
+	unsigned i;
+	size_t res;
+
+	amt = *bytes++;
+	if (amt < SMALL_INDEX_LIMIT) {
+		*bgn += 1;
+		return amt;
+	}
+	amt -= (SMALL_INDEX_LIMIT - 1); // amt is 1 or more here
+	*bgn += amt + 1;
+
+	res = 0;
+	i = 0;
+	do {
+		res |= (size_t)(*bytes++) << i;
+		i += 8;
+	} while (--amt != 0);
+
+	return res;
+}
+
+static char *xc_program_name(char *code, size_t *bgn)
+{
+	code += *bgn;
+	*bgn += strlen(code) + 1;
+
+	return xstrdup(code);
+}
+
+static BcVec* xc_program_dereference(BcVec *vec)
+{
+	BcVec *v;
+	size_t vidx, nidx, i = 0;
+
+	//assert(vec->size == sizeof(uint8_t));
+
+	vidx = xc_program_index(vec->v, &i);
+	nidx = xc_program_index(vec->v, &i);
+
+	v = bc_vec_item(&G.prog.arrs, vidx);
+	v = bc_vec_item(v, nidx);
+
+	//assert(v->size != sizeof(uint8_t));
+
+	return v;
+}
+
+static BcVec* xc_program_search(char *id, BcType type)
 {
 	BcId e, *ptr;
 	BcVec *v, *map;
 	size_t i;
 	int new;
+	bool var = (type == BC_TYPE_VAR);
 
 	v = var ? &G.prog.vars : &G.prog.arrs;
 	map = var ? &G.prog.var_map : &G.prog.arr_map;
@@ -5178,17 +5265,20 @@ static BC_STATUS zxc_program_num(BcResult *r, BcNum **num)
 	case XC_RESULT_VAR:
 	case XC_RESULT_ARRAY:
 	case XC_RESULT_ARRAY_ELEM: {
-		BcVec *v;
-		void *p;
-		v = xc_program_search(r->d.id.name, r->t == XC_RESULT_VAR);
-// dc variables are all stacks, so here we have this:
-		p = bc_vec_top(v);
-// TODO: eliminate these stacks for bc-only config?
+		BcType type = (r->t == XC_RESULT_VAR) ? BC_TYPE_VAR : BC_TYPE_ARRAY;
+		BcVec *v = xc_program_search(r->d.id.name, type);
+		void *p = bc_vec_top(v);
+
 		if (r->t == XC_RESULT_ARRAY_ELEM) {
+			size_t idx = r->d.id.idx;
+
 			v = p;
-			if (v->len <= r->d.id.idx)
-				bc_array_expand(v, r->d.id.idx + 1);
-			*num = bc_vec_item(v, r->d.id.idx);
+			if (v->size == sizeof(uint8_t))
+				v = xc_program_dereference(v);
+			//assert(v->size == sizeof(BcNum));
+			if (v->len <= idx)
+				bc_array_expand(v, idx + 1);
+			*num = bc_vec_item(v, idx);
 		} else {
 			*num = p;
 		}
@@ -5347,39 +5437,6 @@ static BC_STATUS zxc_program_read(void)
 }
 #define zxc_program_read(...) (zxc_program_read(__VA_ARGS__) COMMA_SUCCESS)
 
-static size_t xc_program_index(char *code, size_t *bgn)
-{
-	unsigned char *bytes = (void*)(code + *bgn);
-	unsigned amt;
-	unsigned i;
-	size_t res;
-
-	amt = *bytes++;
-	if (amt < SMALL_INDEX_LIMIT) {
-		*bgn += 1;
-		return amt;
-	}
-	amt -= (SMALL_INDEX_LIMIT - 1); // amt is 1 or more here
-	*bgn += amt + 1;
-
-	res = 0;
-	i = 0;
-	do {
-		res |= (size_t)(*bytes++) << i;
-		i += 8;
-	} while (--amt != 0);
-
-	return res;
-}
-
-static char *xc_program_name(char *code, size_t *bgn)
-{
-	code += *bgn;
-	*bgn += strlen(code) + 1;
-
-	return xstrdup(code);
-}
-
 static void xc_program_printString(const char *str)
 {
 #if ENABLE_DC
@@ -5755,43 +5812,81 @@ static BC_STATUS zdc_program_assignStr(BcResult *r, BcVec *v, bool push)
 #define zdc_program_assignStr(...) (zdc_program_assignStr(__VA_ARGS__) COMMA_SUCCESS)
 #endif // ENABLE_DC
 
-static BC_STATUS zxc_program_popResultAndCopyToVar(char *name, bool var)
+static BC_STATUS zxc_program_popResultAndCopyToVar(char *name, BcType t)
 {
 	BcStatus s;
 	BcResult *ptr, r;
-	BcVec *v;
+	BcVec *vec;
 	BcNum *n;
+	bool var = (t == BC_TYPE_VAR);
 
 	if (!STACK_HAS_MORE_THAN(&G.prog.results, 0))
 		RETURN_STATUS(bc_error_stack_has_too_few_elements());
 
 	ptr = bc_vec_top(&G.prog.results);
-	if ((ptr->t == XC_RESULT_ARRAY) != !var)
+	if ((ptr->t == XC_RESULT_ARRAY) == var)
 		RETURN_STATUS(bc_error_variable_is_wrong_type());
-	v = xc_program_search(name, var);
+	vec = xc_program_search(name, t);
 
 #if ENABLE_DC
-	if (ptr->t == XC_RESULT_STR && !var)
-		RETURN_STATUS(bc_error_variable_is_wrong_type());
-	if (ptr->t == XC_RESULT_STR)
-		RETURN_STATUS(zdc_program_assignStr(ptr, v, true));
+	if (ptr->t == XC_RESULT_STR) {
+		if (!var)
+			RETURN_STATUS(bc_error_variable_is_wrong_type());
+		RETURN_STATUS(zdc_program_assignStr(ptr, vec, true));
+	}
 #endif
 
 	s = zxc_program_num(ptr, &n);
 	if (s) RETURN_STATUS(s);
 
 	// Do this once more to make sure that pointers were not invalidated.
-	v = xc_program_search(name, var);
+	vec = xc_program_search(name, t);
 
 	if (var) {
 		bc_num_init_DEF_SIZE(&r.d.n);
 		bc_num_copy(&r.d.n, n);
 	} else {
+		BcVec *v = (BcVec*) n;
+		bool ref, ref_size;
+
+		ref = (v->size == sizeof(BcVec) && t != BC_TYPE_ARRAY);
+		ref_size = (v->size == sizeof(uint8_t));
+
+		if (ref || (ref_size && t == BC_TYPE_REF)) {
+			bc_vec_init(&r.d.v, sizeof(uint8_t), NULL);
+			if (ref) {
+				size_t vidx, idx;
+				BcId id;
+
+				id.name = ptr->d.id.name;
+				v = xc_program_search(ptr->d.id.name, BC_TYPE_REF);
+
+				// Make sure the pointer was not invalidated.
+				vec = xc_program_search(name, t);
+
+				vidx = bc_map_find_exact(&G.prog.arr_map, &id);
+				//assert(vidx != BC_VEC_INVALID_IDX);
+				vidx = ((BcId*) bc_vec_item(&G.prog.arr_map, vidx))->idx;
+				idx = v->len - 1;
+
+				bc_vec_pushIndex(&r.d.v, vidx);
+				bc_vec_pushIndex(&r.d.v, idx);
+			}
+			// If we get here, we are copying a ref to a ref.
+			else bc_vec_npush(&r.d.v, v->len, v->v);
+
+			// We need to return early.
+			goto ret;
+		}
+
+		if (ref_size && t != BC_TYPE_REF)
+			v = xc_program_dereference(v);
+
 		bc_array_init(&r.d.v, true);
-		bc_array_copy(&r.d.v, (BcVec *) n);
+		bc_array_copy(&r.d.v, v);
 	}
-
-	bc_vec_push(v, &r.d);
+ ret:
+	bc_vec_push(vec, &r.d);
 	bc_vec_pop(&G.prog.results);
 
 	RETURN_STATUS(s);
@@ -5818,7 +5913,7 @@ static BC_STATUS zxc_program_assign(char inst)
 
 		if (left->t != XC_RESULT_VAR)
 			RETURN_STATUS(bc_error_variable_is_wrong_type());
-		v = xc_program_search(left->d.id.name, true);
+		v = xc_program_search(left->d.id.name, BC_TYPE_VAR);
 
 		RETURN_STATUS(zdc_program_assignStr(right, v, false));
 	}
@@ -5897,7 +5992,7 @@ static BC_STATUS xc_program_pushVar(char *code, size_t *bgn,
 
 #if ENABLE_DC
 	if (pop || copy) {
-		BcVec *v = xc_program_search(name, true);
+		BcVec *v = xc_program_search(name, BC_TYPE_VAR);
 		BcNum *num = bc_vec_top(v);
 
 		free(name);
@@ -6014,16 +6109,19 @@ static BC_STATUS zbc_program_call(char *code, size_t *idx)
 	for (i = 0; i < nparams; ++i) {
 		BcResult *arg;
 		BcStatus s;
+		bool arr;
 
 		a = bc_vec_item(&func->autos, nparams - 1 - i);
 		arg = bc_vec_top(&G.prog.results);
 
-		if ((!a->idx) != (arg->t == XC_RESULT_ARRAY) // array/variable mismatch
+		arr = (a->idx == BC_TYPE_ARRAY || a->idx == BC_TYPE_REF);
+
+		if (arr != (arg->t == XC_RESULT_ARRAY) // array/variable mismatch
 		// || arg->t == XC_RESULT_STR - impossible, f("str") is not a legal syntax (strings are not bc expressions)
 		) {
 			RETURN_STATUS(bc_error_variable_is_wrong_type());
 		}
-		s = zxc_program_popResultAndCopyToVar(a->name, a->idx);
+		s = zxc_program_popResultAndCopyToVar(a->name, (BcType) a->idx);
 		if (s) RETURN_STATUS(s);
 	}
 
@@ -6031,12 +6129,13 @@ static BC_STATUS zbc_program_call(char *code, size_t *idx)
 	for (; i < func->autos.len; i++, a++) {
 		BcVec *v;
 
-		v = xc_program_search(a->name, a->idx);
-		if (a->idx) {
+		v = xc_program_search(a->name, (BcType) a->idx);
+		if (a->idx == BC_TYPE_VAR) {
 			BcNum n2;
 			bc_num_init_DEF_SIZE(&n2);
 			bc_vec_push(v, &n2);
 		} else {
+			//assert(a->idx == BC_TYPE_ARRAY);
 			BcVec v2;
 			bc_array_init(&v2, true);
 			bc_vec_push(v, &v2);
@@ -6087,7 +6186,7 @@ static BC_STATUS zbc_program_return(char inst)
 	a = (void*)f->autos.v;
 	for (i = 0; i < f->autos.len; i++, a++) {
 		BcVec *v;
-		v = xc_program_search(a->name, a->idx);
+		v = xc_program_search(a->name, (BcType) a->idx);
 		bc_vec_pop(v);
 	}
 
@@ -6399,7 +6498,7 @@ static BC_STATUS zdc_program_execStr(char *code, size_t *bgn, bool cond)
 
 		if (exec) {
 			BcVec *v;
-			v = xc_program_search(name, true);
+			v = xc_program_search(name, BC_TYPE_VAR);
 			n = bc_vec_top(v);
 		}
 
@@ -6724,7 +6823,7 @@ static BC_STATUS zxc_program_exec(void)
 		}
 		case DC_INST_PUSH_TO_VAR: {
 			char *name = xc_program_name(code, &ip->inst_idx);
-			s = zxc_program_popResultAndCopyToVar(name, true);
+			s = zxc_program_popResultAndCopyToVar(name, BC_TYPE_VAR);
 			free(name);
 			break;
 		}