[FEATURE] flatten SplitRecursively's recursive function calls by using an explicit stack #898
Description
In #897 we set a recursion depth limit for SplitRecursively as a stop gap, to avoid stack overflow. But it means sometimes the split quality will be affected when the AST layer is very deep. e.g. some languages's AST uses tail-recursion style to define lists, which may cause deep AST.
A few test cases that we encountered with deep AST:
- https://github.com/llvm/llvm-project/blob/3ce25abd4afe4ab744e695a7c254966db1dea1ca/clang/test/C/C99/n590.c#L60-L113 (very deep!)
- https://github.com/llvm/llvm-project/blob/630712f4c1ed8b8927b86a99a4d33bf10cabfd0d/bolt/lib/Core/Relocation.cpp#L57-L101 (it's deep, but under current limit now, but once there's more
caseit will exceed the limit) - https://github.com/llvm/llvm-project/blob/d6fae7f921795400aaf6cffe27c6c0d664a5deff/clang-tools-extra/clang-tidy/misc/MisleadingIdentifier.cpp#L41-L120 (similar to above, deep but just under the current limit)
We want to flatten the recursive calls, by explicitly managing a stack (e.g. use a Vec). In such case the space is allocated on the heap instead of stack, which has much much higher size limit.
❤️ Contributors, please refer to 📙Contributing Guide.
Unless the PR can be sent immediately (e.g. just a few lines of code), we recommend you to leave a comment on the issue like I'm working on it or Can I work on this issue? to avoid duplicating work. Our Discord server is always open and friendly.