Wrong fix for #72

[bazsi]

Hi,

As it seems the fix for #72 was not entirely successful. The bitset is not properly shifted to the right. See this patch:

diff --git a/src/tables.c b/src/tables.c
index b04a496e..60e3ec93 100644
--- a/src/tables.c
+++ b/src/tables.c
@@ -186,8 +186,8 @@ pos_set_set (int pos)
       bitset_resize (pos_set, new_size);
       // Shift all the bits by DELTA.
       // FIXME: add bitset_assign, and bitset_shift?
-      for (int i = new_size - 1; delta <= i ; --i)
-        if (bitset_test (pos_set, i))
+      for (int i = old_size - 1; i >= -delta ; --i)
+        if (i >= 0 && bitset_test (pos_set, i))
           bitset_set (pos_set, i + delta);
         else
           bitset_reset (pos_set, i + delta);

With this patch in place, the generated grammars work for me.

[bazsi]

@akimd can you check if this patch is sufficient?
thanks

[akimd]

Hi @bazsi
Sorry for the delays. Yes, you are right, my fix was wrong on several accounts... I will install the following patch. This deserves a new release.

commit b426de59c284cd512b1ec974ac39f4fdbd0d3f21
Author: Akim Demaille <akim.demaille@gmail.com>
Date:   Sun Mar 7 08:19:36 2021 +0100

    tables: fix again the handling for useless tokens
    
    The right-shift added in c22902e360e0fbbe9fd5657dcf107e03166da309
    ("tables: fix handling for useless tokens") is incorrect.  In
    particular, we need to reset the "new" bits.
    
    Reported by Balázs Scheidler.
    https://github.com/akimd/bison/issues/74
    
    * src/tables.c (pos_set_set): Fix the right-shift.

diff --git a/src/tables.c b/src/tables.c
index 6c8fc1cc6..a0f7cb365 100644
--- a/src/tables.c
+++ b/src/tables.c
@@ -180,21 +180,26 @@ pos_set_set (int pos)
   int bitno = pos - pos_set_base;
   if (bitno < 0)
     {
+      // Need more room on the left.
+      // DELTA is positive.  Run 'bitset >> delta'.
       const int delta = pos_set_base - pos;
       const int old_size = bitset_size (pos_set);
       const int new_size = old_size + delta;
       bitset_resize (pos_set, new_size);
-      // Shift all the bits by DELTA.
+      // Right-shift all the bits by DELTA.  Be sure to reset the new
+      // bits on the left.
+      //
       // FIXME: add bitset_assign, and bitset_shift?
-      for (int i = new_size - 1; delta <= i ; --i)
-        if (bitset_test (pos_set, i))
-          bitset_set (pos_set, i + delta);
+      for (int i = new_size - 1; 0 <= i ; --i)
+        if (delta <= i && bitset_test (pos_set, i - delta))
+          bitset_set (pos_set, i);
         else
-          bitset_reset (pos_set, i + delta);
+          bitset_reset (pos_set, i);
       pos_set_base = pos;
       bitno = 0;
     }
   else if (bitset_size (pos_set) <= bitno)
+    // Need more room on the right.
     bitset_resize (pos_set, bitno + 1);
   bitset_set (pos_set, bitno);
 }

[akimd]

Fixed in 3.7.6. Thanks for the report Balázs, and sorry about this.

[bazsi]

thanks. a syslog-ng member already pulled this into our "tarball" generating docker image. hopefully it would eventually make it into distros.

…

On Wed, Mar 10, 2021 at 6:38 AM Akim Demaille ***@***.***> wrote: Closed #74 <#74>. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#74 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAFOK5REIQQAUT6TN7G35FTTC4AWNANCNFSM4XPN5XEA> .

-- Bazsi