search

julianandrews / sgf-parse

SGF parsing library for Rust.
MIT License
13 stars 3 forks source link

Stack Overflow can happen during parse #7

Closed julianandrews closed 3 years ago

julianandrews commented 3 years ago

Currently since the parsing is recursive, if there is a deep enough stack, it can cause a stack overflow.

Here's a sample input that would trigger the issue:

(;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;)

I don't think this is likely to affect any real-world sgf files, but it's still incorrect!

julianandrews commented 3 years ago

Interestingly the above input only overflows on debug builds. With a release build, I guess the stack use is a lot smaller.

julianandrews commented 3 years ago

According to this post: https://stackoverflow.com/a/65898182/252723 the stack size is the same for debug and release builds. I'm guessing that the compiled version was managing to tail call optimize. As written, the code didn't look as if the call was in tail position, but I could totally imagine it ending up that way after other optimizations.

So this may have not been a real bug in release builds.

That said, as far as I know, Rust provides no guarantees about when tail calls get optimized, so I think fixing this was the right call even if the code is a little more complex.