Merge tag 'v3.7.5'

Three new commits:

commit 8358090292e21c61a583da542bad9099ad65f355
Author: Paul Eggert <eggert@cs.ucla.edu>
Date:   Wed Jan 20 18:30:16 2021 -0800

    c: port to HP-UX 11.23

commit 2c294c132528ede23d8ae4959783a67e9ff05ac5
Author: Vincent Imbimbo <vmi6@cornell.edu>
Date:   Sat Jan 23 13:25:18 2021 -0500

    cex: fix state-item pruning

commit c22902e360e0fbbe9fd5657dcf107e03166da309
Author: Akim Demaille <akim.demaille@gmail.com>
Date:   Sat Jan 23 18:40:15 2021 +0100

    tables: fix handling for useless tokens

2 files changed, 95 insertions, 47 deletions

diff --git a/src/state-item.c b/src/state-item.c
index 2fa519ed..fea56a59 100644
--- a/src/state-item.c
+++ b/src/state-item.c
@@ -384,11 +384,10 @@ disable_state_item (state_item *si)
     bitset_free (si->prods);
 }
 
-/* disable all transitions and productions that can only be
- * reached through this state_item.
- */
+/* Disable all state_item paths that lead to/from SI and nowhere
+   else.  */
 static void
-prune_forward (const state_item *si)
+prune_state_item (const state_item *si)
 {
   state_item_list queue =
     gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true, 1,
@@ -398,8 +397,16 @@ prune_forward (const state_item *si)
     {
       state_item *dsi = (state_item *) gl_list_get_at (queue, 0);
       gl_list_remove_at (queue, 0);
-      if (dsi->trans >= 0)
-        gl_list_add_last (queue, &state_items[dsi->trans]);
+      if (SI_DISABLED (dsi - state_items))
+        continue;
+
+      if (dsi->trans >= 0 && !SI_DISABLED (dsi->trans))
+      {
+        const state_item *trans = &state_items[dsi->trans];
+        bitset_reset (trans->revs, dsi - state_items);
+        if (bitset_empty_p (trans->revs))
+          gl_list_add_last (queue, trans);
+      }
 
       if (dsi->prods)
         {
@@ -407,32 +414,15 @@ prune_forward (const state_item *si)
           state_item_number sin;
           BITSET_FOR_EACH (biter, dsi->prods, sin, 0)
             {
+              if (SI_DISABLED (sin))
+                continue;
               const state_item *prod = &state_items[sin];
               bitset_reset (prod->revs, dsi - state_items);
               if (bitset_empty_p (prod->revs))
                 gl_list_add_last (queue, prod);
             }
         }
-      if (dsi != si)
-        disable_state_item (dsi);
-    }
-  gl_list_free (queue);
-}
 
-/* disable all state_item paths that lead to
- * si and nowhere else.
- */
-static void
-prune_backward (const state_item *si)
-{
-  state_item_list queue =
-    gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true, 1,
-                    (const void **) &si);
-
-  while (gl_list_size (queue) > 0)
-    {
-      state_item *dsi = (state_item *) gl_list_get_at (queue, 0);
-      gl_list_remove_at (queue, 0);
       bitset_iterator biter;
       state_item_number sin;
       BITSET_FOR_EACH (biter, dsi->revs, sin, 0)
@@ -440,7 +430,9 @@ prune_backward (const state_item *si)
           if (SI_DISABLED (sin))
             continue;
           state_item *rev = &state_items[sin];
-          if (rev->prods)
+          if (&state_items[rev->trans] == dsi)
+            gl_list_add_last (queue, rev);
+          else if (rev->prods)
             {
               bitset_reset (rev->prods, dsi - state_items);
               if (bitset_empty_p (rev->prods))
@@ -449,16 +441,13 @@ prune_backward (const state_item *si)
           else
             gl_list_add_last (queue, rev);
         }
-      if (dsi != si)
-        disable_state_item (dsi);
+      disable_state_item (dsi);
     }
   gl_list_free (queue);
 }
 
-/*
- To make searches more efficient, we can prune away paths that are
- caused by disabled transitions.
- */
+/* To make searches more efficient, prune away paths that are caused
+   by disabled transitions.  */
 static void
 prune_disabled_paths (void)
 {
@@ -466,11 +455,7 @@ prune_disabled_paths (void)
     {
       state_item *si = &state_items[i];
       if (si->trans == -1 && item_number_is_symbol_number (*si->item))
-        {
-          prune_forward (si);
-          prune_backward (si);
-          disable_state_item (si);
-        }
+        prune_state_item (si);
     }
 }
 
diff --git a/src/tables.c b/src/tables.c
index 0c98c327..b04a496e 100644
--- a/src/tables.c
+++ b/src/tables.c
@@ -111,9 +111,13 @@ base_number *base = NULL;
    computation equals to BASE_MINIMUM, later mapped to BASE_NINF to
    keep parser tables small.  */
 base_number base_ninf = 0;
+
 /* Bitset representing an integer set in the range
-   -nstates..table_size (as an upper bound) */
+   POS_SET_OFFSET..(POS_SET_OFFSET + SIZE).  POS_SET_OFFSET is
+   nonpositive. */
 static bitset pos_set = NULL;
+/* The integer denoted by bitno 0 in pos_set.  */
+static int pos_set_base = 0;
 
 static int *conflrow;
 int *conflict_table;
@@ -138,6 +142,71 @@ int high;
 state_number *yydefgoto;
 rule_number *yydefact;
 
+
+/*----------.
+| pos_set.  |
+`----------*/
+
+#if 0
+static void
+pos_set_dump (void)
+{
+  fprintf (stderr, "pos_set (%ld, %d) =", bitset_size (pos_set), pos_set_base);
+  bitset_iterator biter;
+  int i;
+  BITSET_FOR_EACH (biter, pos_set, i, 0)
+    fprintf (stderr, " %d", i + pos_set_base);
+  putc ('\n', stderr);
+}
+#endif
+
+
+/* The size and base of POS_SET are not known, we need to be able to
+   move the base farther "on the left", and grow "on the right".
+
+   It would be nice to be able to predict the base accurately, but it
+   seems difficult (-nstates seems to work most of the time, except
+   when there are useless tokens).
+
+   FIXME: The current approach is correct, but with poor performances.
+   Bitsets need to support 'assign' and 'shift'.  And instead of
+   extending POS_SET just for the out-of-range new values, we need
+   something like doubling the size.
+  */
+
+static void
+pos_set_set (int pos)
+{
+  int bitno = pos - pos_set_base;
+  if (bitno < 0)
+    {
+      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.
+      // 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);
+        else
+          bitset_reset (pos_set, i + delta);
+      pos_set_base = pos;
+      bitno = 0;
+    }
+  else if (bitset_size (pos_set) <= bitno)
+    bitset_resize (pos_set, bitno + 1);
+  bitset_set (pos_set, bitno);
+}
+
+static bool
+pos_set_test (int pos)
+{
+  const int bitno = pos - pos_set_base;
+  return bitset_test (pos_set, bitno);
+}
+
+
 /*-------------------------------------------------------------------.
 | If TABLE, CONFLICT_TABLE, and CHECK are too small to be addressed  |
 | at DESIRED, grow them.  TABLE[DESIRED] can be used, so the desired |
@@ -168,8 +237,6 @@ table_grow (int desired)
   check = xnrealloc (check, table_size, sizeof *check);
   for (int i = old_size; i < table_size; ++i)
     check[i] = -1;
-
-  bitset_resize (pos_set, table_size + nstates);
 }
 
 
@@ -672,7 +739,7 @@ pack_vector (vector_number vector)
               ok = false;
           }
 
-        if (ok && bitset_test (pos_set, nstates + res))
+        if (ok && pos_set_test (res))
           ok = false;
       }
 
@@ -732,6 +799,7 @@ pack_table (void)
 {
   base = xnmalloc (nvectors, sizeof *base);
   pos_set = bitset_create (table_size + nstates, BITSET_FRUGAL);
+  pos_set_base = -nstates;
   table = xcalloc (table_size, sizeof *table);
   conflict_table = xcalloc (table_size, sizeof *conflict_table);
   check = xnmalloc (table_size, sizeof *check);
@@ -757,12 +825,7 @@ pack_table (void)
         /* Action of I were already coded for S.  */
         place = base[s];
 
-      /* Store PLACE into POS_SET.  PLACE might not belong to the set
-         of possible values for instance with useless tokens.  It
-         would be more satisfying to eliminate the need for this
-         'if'.  */
-      if (0 <= nstates + place)
-        bitset_set (pos_set, nstates + place);
+      pos_set_set (place);
       base[order[i]] = place;
     }