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

[Paul Eggert]

* lib/dfa.c (reorder_tokens): When setting
map[d->follows[i].elems[j].index], instead of incorrectly assuming
that (i < d->follows[i].elems[j].index), use two loops, one to set
the map array and the other to use it.  The incorrect assumption
caused some elements to be missed, and this in turn caused grep's
dfa-heap-overrun test to fail on Solaris 10 sparc when compiled
with GCC.  I found this bug while investigating
https://buildfarm.opencsw.org/buildbot/builders/ggrep-solaris10-sparc/builds/183
and I think the bug also occurs on GNU/Linux but with more-subtle
symptoms.  The bug predates the recent dfa.c changes; perhaps the
recent changes make the bug more likely.
---
 ChangeLog | 15 +++++++++++++++
 lib/dfa.c | 12 ++++++------
 2 files changed, 21 insertions(+), 6 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index a5c14c45e..1b5720761 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,18 @@
+2020-09-13  Paul Eggert  <eggert@cs.ucla.edu>
+
+       dfa: fix dfa-heap-overrun failure
+       * lib/dfa.c (reorder_tokens): When setting
+       map[d->follows[i].elems[j].index], instead of incorrectly assuming
+       that (i < d->follows[i].elems[j].index), use two loops, one to set
+       the map array and the other to use it.  The incorrect assumption
+       caused some elements to be missed, and this in turn caused grep's
+       dfa-heap-overrun test to fail on Solaris 10 sparc when compiled
+       with GCC.  I found this bug while investigating
+       
https://buildfarm.opencsw.org/buildbot/builders/ggrep-solaris10-sparc/builds/183
+       and I think the bug also occurs on GNU/Linux but with more-subtle
+       symptoms.  The bug predates the recent dfa.c changes; perhaps the
+       recent changes make the bug more likely.
+
 2020-09-13  Bruno Haible  <bruno@clisp.org>
 
        parse-datetime: Make the build rule work with parallel 'make'.
diff --git a/lib/dfa.c b/lib/dfa.c
index 0f0764887..4992bcaf2 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -2519,6 +2519,11 @@ reorder_tokens (struct dfa *d)
   else
     multibyte_prop = NULL;
 
+  for (idx_t i = 0; i < d->tindex; i++)
+    for (idx_t j = 0; j < d->follows[i].nelem; j++)
+      if (map[d->follows[i].elems[j].index] == -1)
+        map[d->follows[i].elems[j].index] = nleaves++;
+
   for (idx_t i = 0; i < d->tindex; i++)
     {
       if (map[i] == -1)
@@ -2537,12 +2542,7 @@ reorder_tokens (struct dfa *d)
         multibyte_prop[map[i]] = d->multibyte_prop[i];
 
       for (idx_t j = 0; j < d->follows[i].nelem; j++)
-        {
-          if (map[d->follows[i].elems[j].index] == -1)
-            map[d->follows[i].elems[j].index] = nleaves++;
-
-          d->follows[i].elems[j].index = map[d->follows[i].elems[j].index];
-        }
+        d->follows[i].elems[j].index = map[d->follows[i].elems[j].index];
 
       qsort (d->follows[i].elems, d->follows[i].nelem,
              sizeof *d->follows[i].elems, compare);
-- 
2.17.1