[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
master: Merge tag 'v3.7.5'
From: |
Akim Demaille |
Subject: |
master: Merge tag 'v3.7.5' |
Date: |
Sun, 24 Jan 2021 09:25:32 +0100 |
commit c94456986d590cc58cb7f7fd151c132c13a49644 (HEAD -> upmaster)
Merge: fb144c021 2fac23b9d
Author: Akim Demaille <akim.demaille@gmail.com>
Date: Sun Jan 24 09:22:49 2021 +0100
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
diff --git a/NEWS b/NEWS
index d780a5f14..e5b2091e0 100644
--- a/NEWS
+++ b/NEWS
@@ -1,6 +1,27 @@
GNU Bison NEWS
-* Noteworthy changes in release ?.? (????-??-??) [?]
+* Noteworthy changes in release 3.7.5 (2021-01-24) [stable]
+
+** Bug fixes
+
+*** Counterexample Generation
+
+ In some cases counterexample generation could crash. This is fixed.
+
+*** Fix Table Generation
+
+ In some very rare conditions, when there are many useless tokens, it was
+ possible to generate incorrect parsers.
+
+*** GLR parsers now support %merge together with api.value.type=union.
+
+*** C++ parsers use noexcept in more places.
+
+*** Generated parsers avoid some warnings about signedness issues.
+
+*** C-language parsers now avoid warnings from pedantic clang.
+
+*** C-language parsers now work around quirks of HP-UX 11.23 (2003).
** Changes
diff --git a/cfg.mk b/cfg.mk
index 6725a1866..84756ac5d 100644
--- a/cfg.mk
+++ b/cfg.mk
@@ -156,6 +156,7 @@ exclude = \
$(call exclude,
\
bindtextdomain=^lib/main.c$$
\
cast_of_argument_to_free=^src/muscle-tab.c$$
\
+ copyright_check=gnulib/lib/version-etc.c$$
\
error_message_uppercase=etc/bench.pl.in$$
\
po_check=^tests|(^po/POTFILES.in|.md)$$
\
preprocessor_indentation=^data/|^lib/|^src/parse-gram.[ch]$$
\
diff --git a/data/skeletons/c.m4 b/data/skeletons/c.m4
index fccd4cc80..f2abec5a0 100644
--- a/data/skeletons/c.m4
+++ b/data/skeletons/c.m4
@@ -254,6 +254,18 @@ typedef int_least16_t yytype_int16;
typedef short yytype_int16;
#endif
+/* Work around bug in HP-UX 11.23, which defines these macros
+ incorrectly for preprocessor constants. This workaround can likely
+ be removed in 2023, as HPE has promised support for HP-UX 11.23
+ (aka HP-UX 11i v2) only through the end of 2022; see Table 2 of
+ <https://h20195.www2.hpe.com/V2/getpdf.aspx/4AA4-7673ENW.pdf>. */
+#ifdef __hpux
+# undef UINT_LEAST8_MAX
+# undef UINT_LEAST16_MAX
+# define UINT_LEAST8_MAX 255
+# define UINT_LEAST16_MAX 65535
+#endif
+
#if defined __UINT_LEAST8_MAX__ && __UINT_LEAST8_MAX__ <= __INT_MAX__
typedef __UINT_LEAST8_TYPE__ yytype_uint8;
#elif (!defined __UINT_LEAST8_MAX__ && defined YY_STDINT_H \
diff --git a/src/state-item.c b/src/state-item.c
index 2fa519ed1..fea56a597 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 0c98c3273..b04a496eb 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;
}
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- master: Merge tag 'v3.7.5',
Akim Demaille <=