From: Akim Demaille Date: Mon, 10 Dec 2001 08:43:38 +0000 (+0000) Subject: Bison dumps core on bash.y. X-Git-Tag: BISON-1_30g~12 X-Git-Url: https://git.saurik.com/bison.git/commitdiff_plain/ed45e93ed80e490c4a53e97de64f866e61407484?ds=inline Bison dumps core on bash.y. Reported by Pascal Bart. * src/warshall.c (bitmatrix_print): New. (TC): Use it. When performing a transitive closure R(i, j) && R(j, k) => R(i, k), j must be the outer loop. * tests/regression.at (Broken Closure): New. --- diff --git a/ChangeLog b/ChangeLog index 419a36d4..4240599d 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,14 @@ +2001-12-10 Akim Demaille + + Bison dumps core on bash.y. + Reported by Pascal Bart. + + * src/warshall.c (bitmatrix_print): New. + (TC): Use it. + When performing a transitive closure R(i, j) && R(j, k) => R(i, k), + j must be the outer loop. + * tests/regression.at (Broken Closure): New. + 2001-12-05 Akim Demaille Version 1.30f. diff --git a/src/lalr.c b/src/lalr.c index 09dc7602..44eaa3ed 100644 --- a/src/lalr.c +++ b/src/lalr.c @@ -247,16 +247,17 @@ set_goto_map (void) ngotos = 0; for (sp = first_shift; sp; sp = sp->next) - for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i) - { - symbol = state_table[sp->shifts[i]].accessing_symbol; + if (sp->nshifts) + for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i) + { + symbol = state_table[sp->shifts[i]].accessing_symbol; - if (ngotos == MAXSHORT) - fatal (_("too many gotos (max %d)"), MAXSHORT); + if (ngotos == MAXSHORT) + fatal (_("too many gotos (max %d)"), MAXSHORT); - ngotos++; - goto_map[symbol]++; - } + ngotos++; + goto_map[symbol]++; + } k = 0; for (i = ntokens; i < nsyms; i++) @@ -277,15 +278,16 @@ set_goto_map (void) for (sp = first_shift; sp; sp = sp->next) { state1 = sp->number; - for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i) - { - state2 = sp->shifts[i]; - symbol = state_table[state2].accessing_symbol; - - k = temp_map[symbol]++; - from_state[k] = state1; - to_state[k] = state2; - } + if (sp->nshifts) + for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i) + { + state2 = sp->shifts[i]; + symbol = state_table[state2].accessing_symbol; + + k = temp_map[symbol]++; + from_state[k] = state1; + to_state[k] = state2; + } } XFREE (temp_map + ntokens); diff --git a/src/warshall.c b/src/warshall.c index a9d579e6..5963f472 100644 --- a/src/warshall.c +++ b/src/warshall.c @@ -20,6 +20,7 @@ #include "system.h" +#include "getargs.h" #include "warshall.h" /*-------------------------------------------------------------. @@ -27,6 +28,51 @@ | transive closure of what was given. | `-------------------------------------------------------------*/ +static void +bitmatrix_print (const char *title, unsigned *matrix, size_t size) +{ + size_t i, j; + size_t rowsize = WORDSIZE (size) * sizeof (unsigned); +#define ROW(Num) ((unsigned *) ((char *) matrix + ((Num) * rowsize))) + + /* Title. */ + fprintf (stderr, "%s BEGIN\n", title); + + /* Column numbers. */ + fputs (" ", stderr); + for (i = 0; i < size; ++i) + putc (i / 10 ? '0' + i / 10 : ' ', stderr); + putc ('\n', stderr); + fputs (" ", stderr); + for (i = 0; i < size; ++i) + fprintf (stderr, "%d", i % 10); + putc ('\n', stderr); + + /* Bar. */ + fputs (" +", stderr); + for (i = 0; i < size; ++i) + putc ('-', stderr); + fputs ("+\n", stderr); + + /* Contents. */ + for (i = 0; i < size; ++i) + { + fprintf (stderr, "%2d|", i); + for (j = 0; j < size; ++j) + fputs (BITISSET (ROW (i), j) ? "1" : " ", stderr); + fputs ("|\n", stderr); + } + + /* Bar. */ + fputs (" +", stderr); + for (i = 0; i < size; ++i) + putc ('-', stderr); + fputs ("+\n", stderr); + + /* End title. */ + fprintf (stderr, "%s END\n\n", title); +} + #define R(Num) (unsigned *) ((char *) R + ((Num) * rowsize)) static void @@ -35,12 +81,21 @@ TC (unsigned *R, int n) int rowsize = WORDSIZE (n) * sizeof (unsigned); int i, j, k; + if (trace_flag) + bitmatrix_print ("TC: Input", R, n); + + /* R (J, I) && R (I, K) => R (J, K). + I *must* be the outter loop. */ + for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) - if (BITISSET (R (i), j)) - for (k = 0; k < rowsize; ++k) + if (BITISSET (R (j), i)) + for (k = 0; k < n; ++k) if (BITISSET (R (i), k)) SETBIT (R (j), k); + + if (trace_flag) + bitmatrix_print ("TC: Output", R, n); } diff --git a/tests/regression.at b/tests/regression.at index f141c4b8..70e3420b 100644 --- a/tests/regression.at +++ b/tests/regression.at @@ -611,3 +611,78 @@ AT_CLEANUP AT_TEST_CPP_GUARD_H([input/input]) AT_TEST_CPP_GUARD_H([9foo]) + + +## ---------------- ## +## Broken Closure. ## +## ---------------- ## + +# TC was once broken during a massive `simplification' of the code. +# It resulted in bison dumping core on the following grammar (the +# computation of FIRSTS uses TC). It managed to produce a pretty +# exotic closure: +# +# TC: Input +# +# 01234567 +# +--------+ +# 0| 1 | +# 1| 1 | +# 2| 1 | +# 3| 1 | +# 4| 1 | +# 5| 1 | +# 6| 1| +# 7| | +# +--------+ +# +# TC: Output +# +# 01234567 +# +--------+ +# 0| 1 | +# 1| 111 | +# 2| 111 | +# 3| 1111 | +# 4| 111 1 | +# 5| 111 1 | +# 6| 111 1| +# 7| 111 | +# +--------+ +# +# instead of that below. + +AT_SETUP([Broken Closure]) + +AT_DATA([input.y], +[[%% +a: b +b: c +c: d +d: e +e: f +f: g +g: h +h: 'h' +]]) + +AT_CHECK([bison --trace input.y 2>&1 | + sed -n '/^TC: Output BEGIN/,/^TC: Output END/p'], + [0], +[[TC: Output BEGIN + @&t@ + 01234567 + +--------+ + 0| 1111111| + 1| 111111| + 2| 11111| + 3| 1111| + 4| 111| + 5| 11| + 6| 1| + 7| | + +--------+ +TC: Output END +]]) + +AT_CLEANUP