1 # Torturing Bison. -*- Autotest -*-
2 # Copyright (C) 2001, 2002 Free Software Foundation, Inc.
4 # This program is free software; you can redistribute it and/or modify
5 # it under the terms of the GNU General Public License as published by
6 # the Free Software Foundation; either version 2, or (at your option)
9 # This program is distributed in the hope that it will be useful,
10 # but WITHOUT ANY WARRANTY; without even the implied warranty of
11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 # GNU General Public License for more details.
14 # You should have received a copy of the GNU General Public License
15 # along with this program; if not, write to the Free Software
16 # Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
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
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;
56 #define YYERROR_VERBOSE 1
59 static int yylex (void);
60 static void yyerror (const char *msg);
71 for my $size (1 .. $max)
73 print "%token t$size $size \"$size\"\n";
79 exp { assert (\@S|@1 == 0); \$\$ = \@S|@1; }
80 | input exp { assert (\@S|@2 == \@S|@1 + 1); \$\$ = \@S|@2; }
88 for my $size (1 .. $max)
91 print wrap ("| ", " ",
92 (map { "\"$_\"" } (1 .. $size)),
94 " { \$\$ = $size; }\n";
103 static int inner = 1;
104 static int outer = 0;
107 else if (inner > outer)
117 yyerror (const char *msg)
119 fprintf (stderr, "%s\\n", msg);
125 yydebug = !!getenv ("YYDEBUG");
131 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
140 AT_SETUP([Big triangle])
142 # I have been able to go up to 2000 on my machine.
143 # I tried 3000, a 29Mb grammar file, but then my system killed bison.
144 # With 500 and the new parser, which consume far too much memory,
145 # it gets killed too. Of course the parser is to be cleaned.
146 AT_DATA_TRIANGULAR_GRAMMAR([input.y], [200])
147 AT_CHECK([bison input.y -v -o input.c])
149 AT_PARSER_CHECK([./input])
155 # AT_DATA_HORIZONTAL_GRAMMAR(FILE-NAME, SIZE)
156 # -------------------------------------------
157 # Create FILE-NAME, containing a self checking parser for a huge
158 # horizontal grammar.
159 m4_define([AT_DATA_HORIZONTAL_GRAMMAR],
160 [AT_DATA([[gengram.pl]],
161 [[#! /usr/bin/perl -w
164 my $max = $ARGV[0] || 10;
172 #define YYERROR_VERBOSE 1
175 static int yylex (void);
176 static void yyerror (const char *msg);
180 for my $size (1 .. $max)
182 print "%token t$size $size \"$size\"\n";
192 (map { "\"$_\"" } (1 .. $max)), ";"),
200 static int counter = 1;
208 yyerror (const char *msg)
210 fprintf (stderr, "%s\\n", msg);
216 yydebug = !!getenv ("YYDEBUG");
222 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
227 ## ---------------- ##
228 ## Big horizontal. ##
229 ## ---------------- ##
231 AT_SETUP([Big horizontal])
233 # I have been able to go up to 10000 on my machine, but I had to
234 # increase the maximum stack size (* 100). It gave:
240 # gengram.pl 10000 0.70s user 0.01s sys 99% cpu 0.711 total
241 # bison input.y 730.56s user 0.53s sys 99% cpu 12:12.34 total
242 # gcc -Wall input.tab.c -o input 5.81s user 0.20s sys 100% cpu 6.01 total
243 # ./input 0.00s user 0.01s sys 108% cpu 0.01 total
245 AT_DATA_HORIZONTAL_GRAMMAR([input.y], [1000])
247 # GNU m4 requires about 70 MiB for this test on a 32-bit host.
248 # Ask for 200 MiB, which should be plenty even on a 64-bit host.
249 AT_INCREASE_DATA_SIZE(204000)
251 AT_CHECK([bison input.y -v -o input.c])
253 AT_PARSER_CHECK([./input])
259 # AT_DATA_LOOKAHEADS_GRAMMAR(FILE-NAME, SIZE)
260 # -------------------------------------------
261 # Create FILE-NAME, containing a self checking parser for a grammar
262 # requiring SIZE lookaheads.
263 m4_define([AT_DATA_LOOKAHEADS_GRAMMAR],
264 [AT_DATA([[gengram.pl]],
265 [[#! /usr/bin/perl -w
269 my $max = $ARGV[0] || 10;
277 #define YYERROR_VERBOSE 1
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)),
298 for my $count (1 .. $max)
300 print "%token t$count $count \"$count\"\n";
306 exp { assert (\@S|@1 == 1); \$\$ = \@S|@1; }
307 | input exp { assert (\@S|@2 == \@S|@1 + 1); \$\$ = \@S|@2; }
311 n1 "1" { assert (\@S|@1 == 1); }
314 for my $count (2 .. $max)
316 print "| n$count \"$count\" { assert (\@S|@1 == $count); }\n";
320 for my $count (1 .. $max)
322 print "n$count: token { \$\$ = $count; };\n";
330 static int return_token = 1;
331 static int counter = 1;
344 yyerror (const char *msg)
346 fprintf (stderr, "%s\\n", msg);
352 yydebug = !!getenv ("YYDEBUG");
358 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
363 ## ----------------- ##
364 ## Many lookaheads. ##
365 ## ----------------- ##
367 AT_SETUP([Many lookaheads])
369 AT_DATA_LOOKAHEADS_GRAMMAR([input.y], [1000])
371 # GNU m4 requires about 70 MiB for this test on a 32-bit host.
372 # Ask for 200 MiB, which should be plenty even on a 64-bit host.
373 AT_INCREASE_DATA_SIZE(204000)
375 AT_CHECK([bison input.y -v -o input.c])
377 AT_PARSER_CHECK([./input])
383 # AT_DATA_STACK_TORTURE(C-PROLOGUE)
384 # ---------------------------------
385 # A parser specialized in torturing the stack size.
386 m4_define([AT_DATA_STACK_TORTURE],
387 [# A grammar of parens growing the stack thanks to right recursion.
395 static int yylex (void);
396 static void yyerror (const char *msg);
402 exp: WAIT_FOR_EOF exp | ;
405 yyerror (const char *msg)
407 fprintf (stderr, "%s\n", msg);
411 /* There are YYLVAL_MAX of WAIT_FOR_EOFs. */
412 unsigned int yylval_max;
424 main (int argc, const char **argv)
427 yylval = atoi (argv[1]);
432 AT_CHECK([bison input.y -o input.c])
437 ## -------------------------------------- ##
438 ## Exploding the Stack Size with Alloca. ##
439 ## -------------------------------------- ##
441 AT_SETUP([Exploding the Stack Size with Alloca])
443 AT_DATA_STACK_TORTURE
445 # Below the limit of 200.
446 AT_PARSER_CHECK([./input 20], 0, [], [ignore])
447 # Two enlargements: 2 * 2 * 200.
448 AT_PARSER_CHECK([./input 900], 0, [], [ignore])
449 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
450 # multiply by two starting at 200 => 5120 is the last possible).
451 AT_PARSER_CHECK([./input 10000], 1, [], [ignore])
458 ## -------------------------------------- ##
459 ## Exploding the Stack Size with Malloc. ##
460 ## -------------------------------------- ##
462 AT_SETUP([Exploding the Stack Size with Malloc])
464 AT_DATA_STACK_TORTURE([[#define YYSTACK_USE_ALLOCA 0]])
466 # Below the limit of 200.
467 AT_PARSER_CHECK([./input 20], 0, [], [ignore])
468 # Two enlargements: 2 * 2 * 200.
469 AT_PARSER_CHECK([./input 900], 0, [], [ignore])
470 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
471 # multiply by two starting at 200 => 5120 is the possible).
472 AT_PARSER_CHECK([./input 10000], 1, [], [ignore])