1 # Torturing Bison. -*- Autotest -*-
3 # Copyright (C) 2001-2002, 2004-2007, 2009-2015, 2018-2021 Free Software
6 # This program is free software: you can redistribute it and/or modify
7 # it under the terms of the GNU General Public License as published by
8 # the Free Software Foundation, either version 3 of the License, or
9 # (at your option) any later version.
11 # This program is distributed in the hope that it will be useful,
12 # but WITHOUT ANY WARRANTY; without even the implied warranty of
13 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 # GNU General Public License for more details.
16 # You should have received a copy of the GNU General Public License
17 # along with this program. If not, see <https://www.gnu.org/licenses/>.
19 AT_BANNER([[Torture Tests.]])
22 # AT_INCREASE_DATA_SIZE(SIZE)
23 # ---------------------------
24 # Try to increase the data size to SIZE KiB if possible.
25 m4_define([AT_INCREASE_DATA_SIZE],
26 [data_limit=`(ulimit -S -d) 2>/dev/null`
29 if test "$data_limit" -lt $1; then
30 AT_REQUIRE([ulimit -S -d $1])
36 ## ------------------------------------- ##
37 ## Creating a large artificial grammar. ##
38 ## ------------------------------------- ##
40 # AT_DATA_TRIANGULAR_GRAMMAR(FILE-NAME, SIZE)
41 # -------------------------------------------
42 # Create FILE-NAME, containing a self checking parser for a huge
44 m4_define([AT_DATA_TRIANGULAR_GRAMMAR],
45 [AT_BISON_OPTION_PUSHDEFS
46 AT_DATA([[gengram.pl]],
50 my $max = $ARGV[0] || 10;
53 ]AT_DATA_GRAMMAR_PROLOGUE[
54 %define parse.error verbose
73 for my $size (1 .. $max)
75 print "%token t$size $size \"$size\"\n";
81 exp { assert (\@S|@1 == 0); \$\$ = \@S|@1; }
82 | input exp { assert (\@S|@2 == \@S|@1 + 1); \$\$ = \@S|@2; }
90 for my $size (1 .. $max)
93 print wrap ("| ", " ",
94 (map { "\"$_\"" } (1 .. $size)),
96 " { \$\$ = $size; }\n";
106 static int inner = 1;
107 static int outer = 0;
110 else if (inner > outer)
121 AT_BISON_OPTION_POPDEFS
123 AT_PERL_REQUIRE([-w ./gengram.pl $2], 0, [stdout])
132 AT_SETUP([Big triangle])
134 # I have been able to go up to 2000 on my machine.
135 # I tried 3000, a 29Mb grammar file, but then my system killed bison.
136 # With 500 and the new parser, which consume far too much memory,
137 # it gets killed too. Of course the parser is to be cleaned.
138 AT_DATA_TRIANGULAR_GRAMMAR([input.y], [200])
139 AT_BISON_CHECK_NO_XML([-v -o input.c input.y])
141 AT_PARSER_CHECK([input])
147 # AT_DATA_HORIZONTAL_GRAMMAR(FILE-NAME, SIZE)
148 # -------------------------------------------
149 # Create FILE-NAME, containing a self checking parser for a huge
150 # horizontal grammar.
151 m4_define([AT_DATA_HORIZONTAL_GRAMMAR],
152 [AT_BISON_OPTION_PUSHDEFS
153 AT_DATA([[gengram.pl]],
154 [[#! /usr/bin/perl -w
157 my $max = $ARGV[0] || 10;
160 ]AT_DATA_GRAMMAR_PROLOGUE[
161 %define parse.error verbose
173 for my $size (1 .. $max)
175 print " t$size $size \"$size\"\n";
186 (map { "\"$_\"" } (1 .. $max)), ";"),
196 static int counter = 1;
199 assert (counter++ == MAX + 1);
206 AT_PERL_REQUIRE([-w ./gengram.pl $2], 0, [stdout])
208 AT_BISON_OPTION_POPDEFS
212 ## ---------------- ##
213 ## Big horizontal. ##
214 ## ---------------- ##
216 AT_SETUP([Big horizontal])
218 # I have been able to go up to 10000 on my machine, but I had to
219 # increase the maximum stack size (* 100). It gave:
225 # gengram.pl 10000 0.70s user 0.01s sys 99% cpu 0.711 total
226 # bison input.y 730.56s user 0.53s sys 99% cpu 12:12.34 total
227 # gcc -Wall input.tab.c -o input 5.81s user 0.20s sys 100% cpu 6.01 total
228 # ./input 0.00s user 0.01s sys 108% cpu 0.01 total
230 AT_DATA_HORIZONTAL_GRAMMAR([input.y], [1000])
232 # GNU m4 requires about 70 MiB for this test on a 32-bit host.
233 # Ask for 200 MiB, which should be plenty even on a 64-bit host.
234 AT_INCREASE_DATA_SIZE(204000)
236 AT_BISON_CHECK_NO_XML([-o input.c input.y])
238 AT_PARSER_CHECK([input])
244 ## ------------------- ##
245 ## State number type. ##
246 ## ------------------- ##
248 # AT_TEST(NUM-STATES, TYPE)
249 # -------------------------
250 # Check that automaton with NUM-STATES uses TYPE has state number type.
251 # Check that parser works.
253 m4_pushdef([AT_TEST],
254 [AT_SETUP([State number type: $1 states])
256 AT_BISON_OPTION_PUSHDEFS
258 AT_REQUIRE([ruby $abs_top_srcdir/tests/linear $1 >input.y])
259 # Old versions of GCC reject large values given to #line.
260 AT_FULL_COMPILE([input], [], [], [], [--no-line])
261 AT_CHECK([[sed -ne 's/#define YYNSTATES *\([0-9]*\)/\1/p' input.c]], [], [$1
263 AT_CHECK([[sed -ne 's/typedef \(.*\) yy_state_t;/\1/p' input.c]], [], [$2
265 AT_PARSER_CHECK([input])
267 AT_BISON_OPTION_POPDEFS
270 AT_TEST( [128], [yytype_int8])
271 AT_TEST( [129], [yytype_uint8])
272 AT_TEST( [256], [yytype_uint8])
273 AT_TEST( [257], [yytype_int16])
274 AT_TEST([32768], [yytype_int16])
275 AT_TEST([65536], [yytype_uint16])
276 AT_TEST([65537], [int])
282 ## ------------------------ ##
283 ## Many lookahead tokens. ##
284 ## ------------------------ ##
286 # AT_DATA_LOOKAHEADS_GRAMMAR(FILE-NAME, SIZE)
287 # -------------------------------------------
288 # Create FILE-NAME, containing a self checking parser for a grammar
289 # requiring SIZE lookahead tokens.
290 m4_define([AT_DATA_LOOKAHEADS_GRAMMAR],
291 [AT_BISON_OPTION_PUSHDEFS
292 AT_DATA([[gengram.pl]],
293 [[#! /usr/bin/perl -w
297 my $max = $ARGV[0] || 10;
300 %define parse.error verbose
303 ]AT_DATA_SOURCE_PROLOGUE[
316 %type <val> input exp
321 wrap ("%type <val> ",
323 map { "n$_" } (1 .. $max)),
327 for my $count (1 .. $max)
329 print " t$count $count \"$count\"\n";
335 exp { assert (\@S|@1 == 1); \$\$ = \@S|@1; }
336 | input exp { assert (\@S|@2 == \@S|@1 + 1); \$\$ = \@S|@2; }
340 n1 "1" { assert (\@S|@1 == 1); \@S|@\@S|@ = \@S|@1; }
343 for my $count (2 .. $max)
345 print "| n$count \"$count\" { assert (\@S|@1 == $count); \@S|@\@S|@ = \@S|@1; }\n";
349 for my $count (1 .. $max)
351 print "n$count: token { \$\$ = $count; };\n";
360 static int return_token = 1;
361 static int counter = 1;
364 assert (counter++ == MAX + 1);
380 AT_PERL_REQUIRE([-w ./gengram.pl $2], 0, [stdout])
382 AT_BISON_OPTION_POPDEFS
385 AT_SETUP([Many lookahead tokens])
387 AT_DATA_LOOKAHEADS_GRAMMAR([input.y], [1000])
389 # GNU m4 requires about 70 MiB for this test on a 32-bit host.
390 # Ask for 200 MiB, which should be plenty even on a 64-bit host.
391 AT_INCREASE_DATA_SIZE(204000)
393 AT_BISON_CHECK([-v -o input.c input.y])
395 AT_PARSER_CHECK([input])
401 # AT_DATA_STACK_TORTURE(C-PROLOGUE, [BISON-DECLS])
402 # ------------------------------------------------
403 # A parser specialized in torturing the stack size.
404 m4_define([AT_DATA_STACK_TORTURE],
405 [AT_BISON_OPTION_PUSHDEFS([$2])
406 # A grammar of parens growing the stack thanks to right recursion.
407 AT_DATA_GRAMMAR([input.y],
418 %define parse.error verbose
421 exp: WAIT_FOR_EOF exp | %empty;
428 assert (0 <= yylval);
435 /* Return argv[1] as an int. */
437 get_args (int argc, const char **argv)
441 assert (argc == 2); (void) argc;
442 res = strtol (argv[1], &endp, 10);
443 assert (argv[1] != endp);
445 assert (res <= INT_MAX);
446 assert (errno != ERANGE);
447 return YY_CAST (int, res);
451 main (int argc, const char **argv)
453 YYSTYPE yylval_init = get_args (argc, argv);
456 ]m4_bmatch([$2], [api.push-pull both],
457 [[ yypstate *ps = yypstate_new ();
459 for (count = 0; count < 2; ++count)
462 yylval = yylval_init;
463 new_status = ]m4_bmatch([$2], [api.push-pull both],
464 [[yypull_parse (ps)]],
469 assert (new_status == status);
470 }]m4_bmatch([$2], [api.push-pull both], [[
471 yypstate_delete (ps);]])[
475 AT_BISON_OPTION_POPDEFS([$2])
476 AT_BISON_CHECK([-o input.c input.y])
481 ## -------------------------------------- ##
482 ## Exploding the Stack Size with Alloca. ##
483 ## -------------------------------------- ##
485 AT_SETUP([Exploding the Stack Size with Alloca])
487 m4_pushdef([AT_USE_ALLOCA], [[
488 #if (defined __GNUC__ || defined __BUILTIN_VA_ARG_INCR \
489 || defined _AIX || defined _MSC_VER || defined _ALLOCA_H)
490 # define YYSTACK_USE_ALLOCA 1
494 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA])
496 # Below the limit of 200.
497 AT_PARSER_CHECK([input 20], 0, [], [ignore],
498 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
499 # Two enlargements: 2 * 2 * 200.
500 AT_PARSER_CHECK([input 900], 0, [], [ignore],
501 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
502 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
503 # multiply by two starting at 200 => 5120 is the last possible).
504 AT_PARSER_CHECK([input 10000], 2, [], [ignore],
505 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
507 # The push parser can't use alloca since the stacks can't be locals. This test
508 # just helps guarantee we don't let the YYSTACK_USE_ALLOCA feature affect
510 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA],
511 [[%define api.push-pull both
513 AT_PARSER_CHECK([input 20], 0, [], [ignore],
514 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
515 AT_PARSER_CHECK([input 900], 0, [], [ignore],
516 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
517 AT_PARSER_CHECK([input 10000], 2, [], [ignore],
518 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
520 m4_popdef([AT_USE_ALLOCA])
527 ## -------------------------------------- ##
528 ## Exploding the Stack Size with Malloc. ##
529 ## -------------------------------------- ##
531 AT_SETUP([Exploding the Stack Size with Malloc])
533 m4_pushdef([AT_USE_ALLOCA], [[#define YYSTACK_USE_ALLOCA 0]])
535 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA])
537 # Below the limit of 200.
538 AT_PARSER_CHECK([input 20], 0, [], [ignore],
539 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
540 # Two enlargements: 2 * 2 * 200.
541 AT_PARSER_CHECK([input 900], 0, [], [ignore],
542 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
543 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
544 # multiply by two starting at 200 => 5120 is the possible).
545 AT_PARSER_CHECK([input 10000], 2, [], [ignore],
546 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
548 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA],
549 [[%define api.push-pull both
551 AT_PARSER_CHECK([input 20], 0, [], [ignore],
552 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
553 AT_PARSER_CHECK([input 900], 0, [], [ignore],
554 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
555 AT_PARSER_CHECK([input 10000], 2, [], [ignore],
556 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
558 m4_popdef([AT_USE_ALLOCA])