[Chicken-hackers] [PATCH] Re: [PATCH] Update irregex to 0.9.0

[Peter Bex]

On Thu, Sep 20, 2012 at 02:32:47PM +0200, Sven Hartrumpf wrote:
> Hi.
> 
> Peter wrote:
> >> I decided to go ahead
> >> and update our core irregex to the latest version.  The attached patches
> >> (all 4 of them) synchronizes us with upstream 0.9.0 irregex.  This gives
> >> some performance improvements for submatches.
> 
> And some severe bugs?

While I did expect bugs to crop up when running regexes "in the wild", I
didn't expect any bugs in this part of the code.  The surprising thing
is that our test suite has zero tests for searching when there is
trailing data with submatches.

The reason this failed is because, when searching, irregex runs the DFA
over a string and records the positions of matching substrings.
This means that the memory slots which get manipulated during operation
keep getting manipulated while processing the trailing data.  Then, when
it's finished, it "jumps back" and reads out the old indices and applies
the old finalizers, but does so using the current values of the memory
slots.  This is obviously wrong.

I've added a simplified test case and fixed the code by making it run
the finalizer whenever transitioning from an accepting state to a
nonaccepting state, thereby preserving the state of the memory slots
at the time the match is found.  I've also cleaned up my code a little
because returning to it after a few months, it was a little hard to
understand.  See the attached two patches.

Thanks for reporting this bug!

Cheers,
Peter
-- 
http://sjamaan.ath.cx
--
"The process of preparing programs for a digital computer
 is especially attractive, not only because it can be economically
 and scientifically rewarding, but also because it can be an aesthetic
 experience much like composing poetry or music."
                                                        -- Donald Knuth

0001-Irregex-Use-proper-abstractions-for-manipulating-the.patch
Description: Text document

0002-Irregex-Fix-problem-with-suffixes-returned-while-sea.patch
Description: Text document