From 5968f54f55a157aac934b57a9925e95a8b747221 Mon Sep 17 00:00:00 2001
From: Stephen Dolan <mu@netsoc.tcd.ie>
Date: Tue, 18 Dec 2012 17:36:24 +0000
Subject: [PATCH] Fix a bug in stack reallocation during deep recursion.

---
 execute.c        |  6 +++---
 forkable_stack.h | 21 ++++++++++++---------
 testdata         |  5 +++++
 3 files changed, 20 insertions(+), 12 deletions(-)

diff --git a/execute.c b/execute.c
index a4719aa..6d0bf72 100644
--- a/execute.c
+++ b/execute.c
@@ -469,9 +469,9 @@ jv jq_next() {
 
 
 void jq_init(struct bytecode* bc, jv input) {
-  forkable_stack_init(&data_stk, sizeof(stackval) * 1000); // FIXME: lower this number, see if it breaks
-  forkable_stack_init(&frame_stk, 10240); // FIXME: lower this number, see if it breaks
-  forkable_stack_init(&fork_stk, 10240); // FIXME: lower this number, see if it breaks
+  forkable_stack_init(&data_stk, sizeof(stackval) * 100);
+  forkable_stack_init(&frame_stk, 1024);
+  forkable_stack_init(&fork_stk, 1024);
   
   stack_push(stackval_root(input));
   struct closure top = {bc, -1};
diff --git a/forkable_stack.h b/forkable_stack.h
index 041bfac..c96c132 100644
--- a/forkable_stack.h
+++ b/forkable_stack.h
@@ -112,21 +112,24 @@ static void forkable_stack_pop(struct forkable_stack* s) {
 
 
 struct forkable_stack_state {
-  int prevpos, prevlimit;
+  // We save the previous pos, savedlimit as
+  // length-pos, length-savedlimit since these
+  // values are stable across stack reallocations.
+  int prev_pos_delta, prev_limit_delta;
 };
 
 static void forkable_stack_save(struct forkable_stack* s, struct forkable_stack_state* state) {
   forkable_stack_check(s);
-  state->prevpos = s->pos;
-  state->prevlimit = s->savedlimit;
+  state->prev_pos_delta = s->length - s->pos;
+  state->prev_limit_delta = s->length - s->savedlimit;
   if (s->pos < s->savedlimit) s->savedlimit = s->pos;
 }
 
 static void forkable_stack_switch(struct forkable_stack* s, struct forkable_stack_state* state) {
   forkable_stack_check(s);
   int curr_pos = s->pos;
-  s->pos = state->prevpos;
-  state->prevpos = curr_pos;
+  s->pos = s->length - state->prev_pos_delta;
+  state->prev_pos_delta = s->length - curr_pos;
 
   int curr_limit = s->savedlimit;
   if (curr_pos < curr_limit) s->savedlimit = curr_pos;
@@ -136,10 +139,10 @@ static void forkable_stack_switch(struct forkable_stack* s, struct forkable_stac
 
 static void forkable_stack_restore(struct forkable_stack* s, struct forkable_stack_state* state) {
   forkable_stack_check(s);
-  assert(s->savedlimit <= state->prevpos);
-  assert(s->savedlimit <= state->prevlimit);
-  s->pos = state->prevpos;
-  s->savedlimit = state->prevlimit;
+  assert(s->savedlimit <= s->length - state->prev_pos_delta);
+  assert(s->savedlimit <= s->length - state->prev_limit_delta);
+  s->pos = s->length - state->prev_pos_delta;
+  s->savedlimit = s->length - state->prev_limit_delta;
   forkable_stack_check(s);
 }
 
diff --git a/testdata b/testdata
index 00ecc69..a1c72f0 100644
--- a/testdata
+++ b/testdata
@@ -311,6 +311,11 @@ def fac: if . == 1 then 1 else . * (. - 1 | fac) end; [.[] | fac]
 [1,2,3,4]
 [1,2,6,24]
 
+# test stack overflow and reallocation
+# this test is disabled for now, it takes a realllllly long time.
+# def f: if length > 1000 then . else .+[1]|f end; f | length
+# []
+# 1001
 
 #
 # Assignment
-- 
2.40.0