But I'd like to stress that this is a problem of this implementation, but not of the CPS technique as such: CPS is just not used to its extreme here to allow for tail-call optimisation of all functions, which would then result in O(1) stack usage.
The problem with this implementation is that gcc cannot tail-call optimise every function call, because continuation results are evaluated in the middle of the computation (e.g. for all 'or' decisions). This means the compiler cannot discard the old stack frame.
I should try harder and see what gcc can then do for me! :-)
Also, I should have led with this: I very much enjoyed the blog post and perusing the code. Great work!
For the regex problem, because of the required backtracking, data usage is definitely not O(1), so the continuation data will not be storable on the stack for an O(1) stack tail-call-only CPS version of regex. That context data for the continuations will need to go to the heap, and so we are basically back to how you'd avoid recursion to avoid unbounded stack: by using some data structures on the heap. And at that point, you could just use more straight-forward data structures than those needed for CPS here.
Anyway, the one-phase parsing+matching is still interesting, I think, and it is worth a try to get it to work in O(1) stack by storing the continuation data on the heap. So after fixing SIGSEGVs for infinite recursions, I will go back to fixing memory leaks. :-)
You can implement your own handler for a stack overflow, allowing allocation of additional stack space which can be chained to the original stack. This is how some language runtimes handle [or used to handle] segmented stacks that grow on demand.
I don't know what that means. I don't see how auto-generated code would fix my problem. The regex parser should return an error to the caller if the regex exceeds some limit.
Dynamically growing the stack sounds like a cute hack. I doubt I'd consider it superior to just using the heap though.
(My sibling is also correct)
I think the key missing drawback that isn't stated here is that even if you fix all of your logical bugs, then unless every function call is tail-call optimized by the compiler, then your parser isn't quite safe for untrusted regular expressions. e.g., A user could write `(((((...a...)))))`, and if you don't guard against it with some hard limit on nesting depth, then you're vulnerable to stack overflows. So let's say you implement nesting limits. What limit should be set? /shrug
This is why I write my regex parsers without recursion and instead use an explicit stack on the heap. It is then a bit easier to more robustly manage nesting limits.