1 # Torturing Bison. -*- Autotest -*-
2 # Copyright (C) 2001, 2002, 2004, 2005, 2006, 2007, 2009 Free Software
5 # This program is free software: you can redistribute it and/or modify
6 # it under the terms of the GNU General Public License as published by
7 # the Free Software Foundation, either version 3 of the License, or
8 # (at your option) any later version.
10 # This program is distributed in the hope that it will be useful,
11 # but WITHOUT ANY WARRANTY; without even the implied warranty of
12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 # GNU General Public License for more details.
15 # You should have received a copy of the GNU General Public License
16 # along with this program. If not, see <http://www.gnu.org/licenses/>.
18 AT_BANNER([[Torture Tests.]])
21 # AT_INCREASE_DATA_SIZE(SIZE)
22 # ---------------------------
23 # Try to increase the data size to SIZE KiB if possible.
24 m4_define([AT_INCREASE_DATA_SIZE],
25 [data_limit=`(ulimit -S -d) 2>/dev/null`
28 if test "$data_limit" -lt $1; then
29 AT_CHECK([ulimit -S -d $1 || exit 77])
35 ## ------------------------------------- ##
36 ## Creating a large artificial grammar. ##
37 ## ------------------------------------- ##
39 # AT_DATA_TRIANGULAR_GRAMMAR(FILE-NAME, SIZE)
40 # -------------------------------------------
41 # Create FILE-NAME, containing a self checking parser for a huge
43 m4_define([AT_DATA_TRIANGULAR_GRAMMAR],
44 [AT_DATA([[gengram.pl]],
48 my $max = $ARGV[0] || 10;
51 ]AT_DATA_GRAMMAR_PROLOGUE[
58 static int yylex (void);
59 static void yyerror (const char *msg);
70 for my $size (1 .. $max)
72 print "%token t$size $size \"$size\"\n";
78 exp { if (\@S|@1 != 0) abort (); \$\$ = \@S|@1; }
79 | input exp { if (\@S|@2 != \@S|@1 + 1) abort (); \$\$ = \@S|@2; }
87 for my $size (1 .. $max)
90 print wrap ("| ", " ",
91 (map { "\"$_\"" } (1 .. $size)),
93 " { \$\$ = $size; }\n";
102 static int inner = 1;
103 static int outer = 0;
106 else if (inner > outer)
116 yyerror (const char *msg)
118 fprintf (stderr, "%s\\n", msg);
124 yydebug = !!getenv ("YYDEBUG");
130 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
139 AT_SETUP([Big triangle])
141 # I have been able to go up to 2000 on my machine.
142 # I tried 3000, a 29Mb grammar file, but then my system killed bison.
143 # With 500 and the new parser, which consume far too much memory,
144 # it gets killed too. Of course the parser is to be cleaned.
145 AT_DATA_TRIANGULAR_GRAMMAR([input.y], [200])
146 AT_BISON_CHECK_NO_XML([-v -o input.c input.y])
148 AT_PARSER_CHECK([./input])
154 # AT_DATA_HORIZONTAL_GRAMMAR(FILE-NAME, SIZE)
155 # -------------------------------------------
156 # Create FILE-NAME, containing a self checking parser for a huge
157 # horizontal grammar.
158 m4_define([AT_DATA_HORIZONTAL_GRAMMAR],
159 [AT_DATA([[gengram.pl]],
160 [[#! /usr/bin/perl -w
163 my $max = $ARGV[0] || 10;
166 ]AT_DATA_GRAMMAR_PROLOGUE[
173 static int yylex (void);
174 static void yyerror (const char *msg);
179 for my $size (1 .. $max)
181 print " t$size $size \"$size\"\n";
192 (map { "\"$_\"" } (1 .. $max)), ";"),
200 static int counter = 1;
203 if (counter++ != $max + 1)
209 yyerror (const char *msg)
211 fprintf (stderr, "%s\\n", msg);
217 yydebug = !!getenv ("YYDEBUG");
223 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
228 ## ---------------- ##
229 ## Big horizontal. ##
230 ## ---------------- ##
232 AT_SETUP([Big horizontal])
234 # I have been able to go up to 10000 on my machine, but I had to
235 # increase the maximum stack size (* 100). It gave:
241 # gengram.pl 10000 0.70s user 0.01s sys 99% cpu 0.711 total
242 # bison input.y 730.56s user 0.53s sys 99% cpu 12:12.34 total
243 # gcc -Wall input.tab.c -o input 5.81s user 0.20s sys 100% cpu 6.01 total
244 # ./input 0.00s user 0.01s sys 108% cpu 0.01 total
246 AT_DATA_HORIZONTAL_GRAMMAR([input.y], [1000])
248 # GNU m4 requires about 70 MiB for this test on a 32-bit host.
249 # Ask for 200 MiB, which should be plenty even on a 64-bit host.
250 AT_INCREASE_DATA_SIZE(204000)
252 AT_BISON_CHECK_NO_XML([-v -o input.c input.y])
254 AT_PARSER_CHECK([./input])
260 # AT_DATA_LOOKAHEAD_TOKENS_GRAMMAR(FILE-NAME, SIZE)
261 # --------------------------------------------------
262 # Create FILE-NAME, containing a self checking parser for a grammar
263 # requiring SIZE lookahead tokens.
264 m4_define([AT_DATA_LOOKAHEAD_TOKENS_GRAMMAR],
265 [AT_DATA([[gengram.pl]],
266 [[#! /usr/bin/perl -w
270 my $max = $ARGV[0] || 10;
280 static int yylex (void);
281 static void yyerror (const char *msg);
288 %type <val> input exp
293 wrap ("%type <val> ",
295 map { "n$_" } (1 .. $max)),
299 for my $count (1 .. $max)
301 print " t$count $count \"$count\"\n";
307 exp { assert (\@S|@1 == 1); \$\$ = \@S|@1; }
308 | input exp { assert (\@S|@2 == \@S|@1 + 1); \$\$ = \@S|@2; }
312 n1 "1" { assert (\@S|@1 == 1); \@S|@\@S|@ = \@S|@1; }
315 for my $count (2 .. $max)
317 print "| n$count \"$count\" { assert (\@S|@1 == $count); \@S|@\@S|@ = \@S|@1; }\n";
321 for my $count (1 .. $max)
323 print "n$count: token { \$\$ = $count; };\n";
331 static int return_token = 1;
332 static int counter = 1;
335 if (counter++ != $max + 1)
349 yyerror (const char *msg)
351 fprintf (stderr, "%s\\n", msg);
357 yydebug = !!getenv ("YYDEBUG");
363 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
368 ## ------------------------ ##
369 ## Many lookahead tokens. ##
370 ## ------------------------ ##
372 AT_SETUP([Many lookahead tokens])
374 AT_DATA_LOOKAHEAD_TOKENS_GRAMMAR([input.y], [1000])
376 # GNU m4 requires about 70 MiB for this test on a 32-bit host.
377 # Ask for 200 MiB, which should be plenty even on a 64-bit host.
378 AT_INCREASE_DATA_SIZE(204000)
380 AT_BISON_CHECK([-v -o input.c input.y])
382 AT_PARSER_CHECK([./input])
388 # AT_DATA_STACK_TORTURE(C-PROLOGUE, [BISON-DECLS])
389 # ------------------------------------------------
390 # A parser specialized in torturing the stack size.
391 m4_define([AT_DATA_STACK_TORTURE],
392 [# A grammar of parens growing the stack thanks to right recursion.
401 static int yylex (void);
402 static void yyerror (const char *msg);
409 exp: WAIT_FOR_EOF exp | ;
412 yyerror (const char *msg)
414 fprintf (stderr, "%s\n", msg);
429 main (int argc, const char **argv)
435 yylval_init = strtol (argv[1], &endp, 10);
436 if (! (argv[1] != endp
437 && 0 <= yylval_init && yylval_init <= INT_MAX
444 ]m4_bmatch([$2], [%push-],
445 [[ yypstate *ps = yypstate_new ();
446 ]])[ for (count = 0; count < 2; ++count)
449 yylval = yylval_init;
450 ]m4_bmatch([$2], [%push-],
451 [[ new_status = yypull_parse (ps);
453 [[ new_status = yyparse ();
454 ]])[ if (count > 0 && new_status != status)
458 ]m4_bmatch([$2], [%push-],
459 [[ yypstate_delete (ps);
464 AT_BISON_CHECK([-o input.c input.y])
469 ## -------------------------------------- ##
470 ## Exploding the Stack Size with Alloca. ##
471 ## -------------------------------------- ##
473 AT_SETUP([Exploding the Stack Size with Alloca])
475 m4_pushdef([AT_USE_ALLOCA], [[
476 #if (defined __GNUC__ || defined __BUILTIN_VA_ARG_INCR \
477 || defined _AIX || defined _MSC_VER || defined _ALLOCA_H)
478 # define YYSTACK_USE_ALLOCA 1
482 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA])
484 # Below the limit of 200.
485 AT_PARSER_CHECK([./input 20], 0, [], [ignore],
486 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
487 # Two enlargements: 2 * 2 * 200.
488 AT_PARSER_CHECK([./input 900], 0, [], [ignore],
489 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
490 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
491 # multiply by two starting at 200 => 5120 is the last possible).
492 AT_PARSER_CHECK([./input 10000], 2, [], [ignore],
493 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
495 # The push parser can't use alloca since the stacks can't be locals. This test
496 # just helps guarantee we don't let the YYSTACK_USE_ALLOCA feature affect
498 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA],
499 [[%define api.push-pull "both"
501 AT_PARSER_CHECK([./input 20], 0, [], [ignore],
502 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
503 AT_PARSER_CHECK([./input 900], 0, [], [ignore],
504 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
505 AT_PARSER_CHECK([./input 10000], 2, [], [ignore],
506 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
508 m4_popdef([AT_USE_ALLOCA])
515 ## -------------------------------------- ##
516 ## Exploding the Stack Size with Malloc. ##
517 ## -------------------------------------- ##
519 AT_SETUP([Exploding the Stack Size with Malloc])
521 m4_pushdef([AT_USE_ALLOCA], [[#define YYSTACK_USE_ALLOCA 0]])
523 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA])
525 # Below the limit of 200.
526 AT_PARSER_CHECK([./input 20], 0, [], [ignore],
527 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
528 # Two enlargements: 2 * 2 * 200.
529 AT_PARSER_CHECK([./input 900], 0, [], [ignore],
530 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
531 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
532 # multiply by two starting at 200 => 5120 is the possible).
533 AT_PARSER_CHECK([./input 10000], 2, [], [ignore],
534 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
536 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA],
537 [[%define api.push-pull "both"
539 AT_PARSER_CHECK([./input 20], 0, [], [ignore],
540 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
541 AT_PARSER_CHECK([./input 900], 0, [], [ignore],
542 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
543 AT_PARSER_CHECK([./input 10000], 2, [], [ignore],
544 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
546 m4_popdef([AT_USE_ALLOCA])