Recursing binary expression causes stackoverflow

[Boshen]

When oxc is being used in Rolldown run on large applications (lots of javascript code), the combination of tokio + rayon + recursing binary expressions in transform and codegen can easily cause stack overflow.

This was evident when I worked on Rspack with swc. The proposed solution was to set RUST_MIN_STACK to a super high value.

Hours can be lost when debugging such cases, and I don't want to tell my downstream users to set a higher RUST_MIN_STACK.

Besides, esbuild unrolls its recursions for binary expressions, and we should do the same since our goal is to target super large codebases.

---

To trigger the stack overflow, we can have a set of tests where RUST_MIN_STACK is to a lower number.

tasks/coverage/misc/pass/swc-1627.js also contains a large binary expression.

Or we can dynamically generate a large dynamic expression so we don't commit in a huge file.

Seen in wild: https://github.com/denoland/deno/issues/24325#issuecomment-2203867362

            "AAEAAAASAQAABAAgR0RFRrRCsIIAAir4AAACYkdQT1Or8IZpAAItXAAAZS5H" +
            "U1VCeoGFdwACkowAABWQT1MvMpl2sYAAAhh4AAAAYGNtYXDG7lFtAAId8AAA" +
            "BoJjdnQgBg4uPQACJ2gAAABaZnBnbYP7I6sAAiR0AAABvGdhc3AACAATAAIq" +
            "7AAAAAxnbHlm1d+kywAAASwAAfh4aGRteHmPiKEAAhjYAAAFGGhlYWT9R9JX" +
            "AAID5AAAADZoaGVhDUgS1wACGFQAAAAkaG10eN7XI9kAAgQcAAAUOGxvY2HG" +
            // <continues for ~3864 more lines

And code generated file: https://github.com/StoneCypher/jssm/blob/main/src/ts/fsl_parser.ts

[overlookmotel]

SWC also hit stack overflow with deeply nested if statements: https://github.com/swc-project/swc/issues/5470

I guess in theory at least, there are many ways you could craft a JS file which will produce deep recursion and exhaust the stack.

[Boshen]

Oh yes I remember this one, another test case for us: https://github.com/StoneCypher/jssm/blob/main/src/ts/fsl_parser.ts

[Boshen]

I added two tests in https://github.com/oxc-project/oxc/pull/4084

It crashes the formatter straight away. We aren't working on the formatter so I disabled it.

Increasing the depth causes stack overflow in different places of the toolchain:

• crashes parser when huge_nested_statements gets big
• crashes semantic when huge_binary_expression gets big

I also observed that it crashes easily when run inside rayon / tokio.

[overlookmotel]

I believe SWC got around this by using https://crates.io/crates/stacker. I'm not sure if that's the best solution for us or not.

Only other general solution I can see is to replace recursion with loops, but that'd involve major architectural changes throughout most components of Oxc.

[Boshen]

No stacker, I tried it before, it doesn't work in wasm.

esbuild unrolls everything so we'll try our best to unroll them.

But we should start documenting RUST_MIN_STACK and crashing on large binaries is expected behavior, to avoid maintenance burnout.

[Boshen]

https://github.com/oxc-project/oxc/pull/4548 is a demonstration of visiting binary + logical expressions on the heap.