[PATCH 01/11] dfa: fix corner case with anchors

[Paolo Bonzini]

* NEWS: Document bugfix.
* src/dfa.c (insert, delete, merge): Do not merge nodes with the
same index and different constraints.
* tests/spencer1.tests: Add test cases.
---
 NEWS                 |    5 +++++
 src/dfa.c            |   23 ++++++++++++-----------
 tests/spencer1.tests |   12 ++++++++++++
 3 files changed, 29 insertions(+), 11 deletions(-)

diff --git a/NEWS b/NEWS
index 9efb82a..5467d37 100644
--- a/NEWS
+++ b/NEWS
@@ -33,6 +33,11 @@ GNU grep NEWS                                    -*- outline 
-*-
   grep no longer emits an error message and quits on MS-Windows when
   invoked with the -r option.
 
+  grep interprets correctly some regular expressions where anchors
+  (^, $, \<, \>, \B, \b) occur before an "|".  For example "(^|\B)a"
+  incorrectly reported a match the string "x a".
+  [bug present since "the beginning"]
+
 ** New features
 
   If no file operand is given, grep -r now searches the working directory.
diff --git a/src/dfa.c b/src/dfa.c
index 8dbadd5..58505bf 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -1853,17 +1853,18 @@ insert (position p, position_set *s)
   while (lo < hi)
     {
       int mid = ((unsigned) lo + (unsigned) hi) >> 1;
-      if (s->elems[mid].index > p.index)
+      if (s->elems[mid].index > p.index
+         || (s->elems[mid].index == p.index
+             && s->elems[mid].constraint > p.constraint))
         lo = mid + 1;
       else
         hi = mid;
     }
 
-  if (lo < count && p.index == s->elems[lo].index)
-    {
-      s->elems[lo].constraint |= p.constraint;
-      return;
-    }
+  if (lo < count
+      && p.index == s->elems[lo].index
+      && p.constraint == s->elems[lo].constraint)
+    return;
 
   REALLOC_IF_NECESSARY(s->elems, s->alloc, count + 1);
   for (i = count; i > lo; i--)
@@ -1886,11 +1887,11 @@ merge (position_set const *s1, position_set const *s2, 
position_set *m)
       m->elems[m->nelem++] = s1->elems[i++];
     else if (s1->elems[i].index < s2->elems[j].index)
       m->elems[m->nelem++] = s2->elems[j++];
+    else if (s1->elems[i].constraint > s2->elems[j].constraint)
+      m->elems[m->nelem++] = s1->elems[i++];
     else
-      {
-        m->elems[m->nelem] = s1->elems[i++];
-        m->elems[m->nelem++].constraint |= s2->elems[j++].constraint;
-      }
+      m->elems[m->nelem++] = s2->elems[j++];
+
   while (i < s1->nelem)
     m->elems[m->nelem++] = s1->elems[i++];
   while (j < s2->nelem)
@@ -1904,7 +1905,7 @@ delete (position p, position_set *s)
   int i;
 
   for (i = 0; i < s->nelem; ++i)
-    if (p.index == s->elems[i].index)
+    if (p.index == s->elems[i].index && p.constraint == s->elems[i].constraint)
       break;
   if (i < s->nelem)
     for (--s->nelem; i < s->nelem; ++i)
diff --git a/tests/spencer1.tests b/tests/spencer1.tests
index ecbed0f..855265f 100644
--- a/tests/spencer1.tests
+++ b/tests/spencer1.tests
@@ -129,3 +129,15 @@
 address@hidden(bc)address@hidden
 address@hidden@ac
 0@(....)address@hidden
+0@(^|\B)address@hidden
+0@(^|\B)address@hidden
+1@(^|\B)address@hidden abc
address@hidden|address@hidden
address@hidden|address@hidden
address@hidden|address@hidden abc
+0@(^|\>)address@hidden
+1@(^|\>)address@hidden
+1@(^|\>)address@hidden abc
address@hidden|\>address@hidden
address@hidden|\>address@hidden
address@hidden|\>address@hidden abc
-- 
1.7.7.1