boa_tester stack overflows in debug mode

[hansl]

Running the boa_tester in debug in the main branch aborts with a stack overflow.

In release mode everything seems fine, but we should still investigate.

[jasonwilliams]

Yeah I think we're going to have to fix this properly, if you run the benchmarks in debug mode (just the first one or second one) it also stack overflows.

I think we're gonna have to find the smallest test case that causes this and try to fix it, it's happening at the parser level.

[Nikita-str]

The problem is here test262\test\language\statements\function\S13.2.1_A1_T1.js:

(function(){
  (function(){
    ... repeated 32 times in total ...
  })()
})()

Rust generator

  let mut js = String::new();
  let n = 32;
  (0..n).for_each(|_| js += "(function(){ ");
  (0..n).for_each(|_| js += " })()");

---

First of all, in the case there will be about 20 nested parse calls between two function statement, so for 32 functions the call's depth is definitely more than 500. And in case of boa_tester there also is stack-size overheads for boa_tester itself.

I tried to reduce stack size for this case, and even made it about 3 times shorter(mostly by boxing & in one place you can remove about 7 nested calls per function statement for the case), but it's not enough for profile.dev case. And that is the main problem. After stack-size optimization, with opt-level = 1 (profile.test case) it can pass the test with n = 150, and with opt-level = 0 (profile.dev case) it can only pass the test with n = 35*.

*

And you can say: "hmm 35 is more than 32 so we are done!" But unfortunately this results are for the next code:

#[test]
fn tmp_test() {
    let mut js = String::new();
    let n = 36;
    (0..n).for_each(|_| js += "(function(){ \n");
    (0..n).for_each(|_| js += " })()");

    let interner = &mut Interner::default();
    crate::Parser::new(crate::Source::from_bytes(&js))
        .parse_script(&boa_ast::scope::Scope::new_global(), interner)
        .expect("failed to parse");
}

And when you run boa_tester it passes only with n = 17 and with large n stackoverflow is happening. So you can approximately estimate overhead costs of boa_tester itself. I tried to make size of stack allocation for boa_tester smaller too, but seems like I don't see something because I don't understand why it takes so many stack memory (there is few function that with opt-level = 0 have about 0x500 bytes of stack alloc but this is not enough problematic to make n twice less because they are not called recursively). Hmm... Is it possible that something that makes testing parallel allocates a half-sized stack?

A little visual comparison:

///	opt-level = 1 stack alloc	opt-level = 0 stack alloc
stack alloc between two function stmt in the example	~13 KB	~58 KB
BitwiseORExpr::parse stack alloc	~280 bytes	~1500 bytes

So, as you can see, stack allocation with opt-level = 0 is 4 times larger than with opt-level = 1.

And I don't know how to optimize the stack size further. I move many things into box and make some structure smaller, but it's not enough.

---

So I have some questions:

1. Can we just change profile.dev.opt-level from 0 to 1?
2. Is there a stack reduction task separated from this problem? In other words, my changes don't solve the problem but reduce the stack size quite significantly, should I create a PR?

[Nikita-str]

Just found out that some stack-size optimizations affect only opt-level = 0, so the issue will be solved.

[jasonwilliams]

Hey @Nikita-str thanks for taking such a detailed look at this problem. I really appreciated the small reproducible test case you made.

It looks like we need to refactor how the parsing works to not keep hitting these stack overflows long term by the looks of it.

There was some similar discussion about this on another issue here #162, what are your thoughts?

It would be good long term to be able to run Boa in dev mode and not have stack overflows so we can debug issues like this, which makes me think adjusting the opt-level is a sticking plaster for now.

Just found out that some stack-size optimizations affect only opt-level = 0, so the issue will be solved.

I don’t understand this, could you explain more?

[Nikita-str]

I don’t understand this, could you explain more?

I tried to reduce the stack size while debugging with opt-level = 1, and then I found that for opt-level = 0 you can split some functions and it will reduce the stack size significantly for opt-level = 0 but will have no effect for others opt-levels. Actually it looks slightly ugly but it's more convenient to discuss the ugliness on concrete code, so I'll finish some changes, and then create a PR. In mentioned case of repeating (function()( I managed to reduce the stack size in 6 times for opt-level = 0.

Example of such splitting:

fn parse(...) -> Output {
   ... many code here # 1 ... 
   OftenRecExpression::parse(...);
   ... many code here # 2 ...
}

into

fn parse(...) -> Output {
   parse_prefix(...); 
   OftenRecExpression::parse(...);
   parse_tail(...)
}
fn parse_prefix(...) -> AnyOutput {
   ... many code here # 1 ...
}
fn parse_tail(...) -> Output {
   ... many code here # 2 ...
}

---

Now about #162. With the current approach you can only shift the numbers on which this happens. To make stack overflow impossible in general case you should rewrite parser fully, except for dead-end call branches. And, I'm making very intuitive first-sight assumption based on how I would try to solve the issue, probably you should have some stack structure that will return through all N calls when recursion happens and save all context(local variables), and if it happens to work(lol) there will be no more nested calls than longest non-repeating chain of statement (in other words, no more than amount of existing TokenParser objects). Maybe there is an easier rewriting, idk.