Re: [PATCH 1/3] dfa: fix dfa-heap-overrun failure

[Norihiro Tanaka]

On Mon, 14 Sep 2020 00:28:32 -0700
Paul Eggert <eggert@cs.ucla.edu> wrote:

> On 9/14/20 12:13 AM, Norihiro Tanaka wrote:
> 
> > when (i >= d->follows[i].elems[j].index), it seems that
> > map[d->follows[i].elems[j].index] has been already set a value more than 0.
> >
> > What case violates this assumption?
> 
> Thank you for looking into this. I ran into the problem with the 
> dfa-heap-overrun test:
> 
> grep -E '(^| )*(a|b)*(c|d)*( |$)' < /dev/null
> 
> I can reproduce the problem by applying the attached patch to current dfa.c. 
> This patch brings back the previous algorithm, except with a runtime test of 
> the assumption. If I then run the dfa-heap-overrun test, it dumps core on my 
> platform (Ubuntu 18.04.5 x86-64, en_US.utf8 locale) because the assumption is 
> violated.

Thanks for giving me the patch.  I confirmed the crash reproduces with
the patch in GNU/Linux, and I found that a closure to be removed was not
removed.

The bug is introduced in commit cafb61533f5bfb989698e3924f97471498b2422b
which is a first patch I wrote, and I attach a patch to fix the bug.

0001-dfa-fix-failure-in-removal-of-epsilon-closure.patch
Description: Text document