bug in dfa.c

[Arne Jansen]

Hi,

the function state_index searches for a state with the same
position set as the given set. The loop which checks for
equality is imho missing the check if the nelem differ.
If one list is a subset of the other, the check might
accidentally match.
This is extremely unlikely for small expressions, but if you
have some 100,000 states it gets quite likely.

Below a proposed fix, though untested:

  for (i = 0; i < s->nelem; ++i)
    hash ^= s->elems[i].index + s->elems[i].constraint;

  /* Try to find a state that exactly matches the proposed one. */
  for (i = 0; i < d->sindex; ++i)
    {
      if (hash != d->states[i].hash || s->nelem !=
          d->states[i].elems.nelem
          || newline != d->states[i].newline || letter !=
             d->states[i].letter)
        continue;
+    if (s->nelem != d->states[i].elems.nelem)
+       continue;
      for (j = 0; j < s->nelem; ++j)
        if (s->elems[j].constraint
            != d->states[i].elems.elems[j].constraint
            || s->elems[j].index != d->states[i].elems.elems[j].index)
          break;
      if (j == s->nelem)
        return i;
    }

Cheers,
Arne

--
--------------------------------------------------------------
Telefon: +49 (0)30-39802-214
Telefax: +49 (0)30-39802-222
E-Mail:  address@hidden
--------------------------------------------------------------
Strato Rechenzentrum AG
Pascalstrasse 10
10587 Berlin
--------------------------------------------------------------
Vorsitzender des Aufsichtsrates: Damian Schmidt
Vorstand: Julien Ardisson, Christian Mueller, Christian Negrutiu,
          Christoph Steffens, Rene Wienholtz
Amtsgericht Berlin-Charlottenburg HRB 75629