search

haskell / happy

The Happy parser generator for Haskell
Other
276 stars 84 forks source link

Happy overflow bug #98

Closed harpocrates closed 7 years ago

harpocrates commented 7 years ago

This fixes #93. In a nutshell:

My happyTable/happyCheck have over 2^15 entries in them. That isn't a problem by itself, if it weren't for the fact that happyActOffsets/happyGotoOffsets store indices pointing into happyTable in signed 16 bit numbers. Then, the issue is that the indices that are being written into happyActOffsets sometimes get too big. When that happens, they wrap around to the vicinity of -32000.

The fix is simple: keep track of the smallest value in happyActOffsets/happyGotoOffsets. Then, when reading values back out of these arrays, we check if the value read is smaller than what is supposed to be the smallest value. If it is, we know that there was an accidental overflow (and we add 2^16 to the value we got out).

This lets us have happyTable/happyCheck tables with a little under 2^16 entries - double what we currently have and with no extra space cost. (And enough to fix my project.)

harpocrates commented 7 years ago

I think this is now ready to merge. When run with --ghc, happy now

Also, what is the usual release cycle for happy? I've been holding off on releasing my language-rust package since this bug affects it, but if happy isn't due for a release for some time still...

simonmar commented 7 years ago

Good diagnosis!

Perhaps I'm missing something here, but wouldn't an easier fix be to use unsigned 16-bit offsets rather than signed offsets?

harpocrates commented 7 years ago

I'm not sure that would work so easily. The problem is that entries in happyActOffsets/happyGotoOffsets can also be slightly negative and still meaningful. After retrieving an offset from one of these tables, the offset is added to the token number and the sum of those (if positive) is used to look into happyTable/happyCheck.

All that to say that small negative offsets are still used, so we can't just switch to unsigned offsets.

Does this make sense?

harpocrates commented 7 years ago

Would you prefer if I opened a new PR on a new branch with a cleaner history? I think I mistakenly branched off of https://github.com/simonmar/happy/pull/97 instead.

simonmar commented 7 years ago

Up to you whether you force-push to this branch or open a new PR.

harpocrates commented 7 years ago

I've opened a new PR, so I'm closing this one.