]> git.saurik.com Git - bison.git/blob - tests/torture.at
gnulib: update
[bison.git] / tests / torture.at
1 # Torturing Bison. -*- Autotest -*-
2
3 # Copyright (C) 2001-2002, 2004-2007, 2009-2013 Free Software
4 # Foundation, Inc.
5
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.
10 #
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.
15 #
16 # You should have received a copy of the GNU General Public License
17 # along with this program. If not, see <http://www.gnu.org/licenses/>.
18
19 AT_BANNER([[Torture Tests.]])
20
21
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`
27 case $data_limit in
28 [[0-9]]*)
29 if test "$data_limit" -lt $1; then
30 AT_CHECK([ulimit -S -d $1 || exit 77])
31 ulimit -S -d $1
32 fi
33 esac])
34
35
36 ## ------------------------------------- ##
37 ## Creating a large artificial grammar. ##
38 ## ------------------------------------- ##
39
40 # AT_DATA_TRIANGULAR_GRAMMAR(FILE-NAME, SIZE)
41 # -------------------------------------------
42 # Create FILE-NAME, containing a self checking parser for a huge
43 # triangular grammar.
44 m4_define([AT_DATA_TRIANGULAR_GRAMMAR],
45 [AT_BISON_OPTION_PUSHDEFS
46 AT_DATA([[gengram.pl]],
47 [[#! /usr/bin/perl -w
48
49 use strict;
50 my $max = $ARGV[0] || 10;
51
52 print <<EOF;
53 ]AT_DATA_GRAMMAR_PROLOGUE[
54 %error-verbose
55 %debug
56 %{
57 #include <stdio.h>
58 #include <stdlib.h>
59 #include <assert.h>
60 #define MAX $max
61 ]AT_YYLEX_DECLARE[
62 ]AT_YYERROR_DECLARE[
63 %}
64 %union
65 {
66 int val;
67 };
68
69 %token END "end"
70 %type <val> exp input
71 EOF
72
73 for my $size (1 .. $max)
74 {
75 print "%token t$size $size \"$size\"\n";
76 };
77
78 print <<EOF;
79 %%
80 input:
81 exp { assert (\@S|@1 == 0); \$\$ = \@S|@1; }
82 | input exp { assert (\@S|@2 == \@S|@1 + 1); \$\$ = \@S|@2; }
83 ;
84
85 exp:
86 END
87 { \$\$ = 0; }
88 EOF
89
90 for my $size (1 .. $max)
91 {
92 use Text::Wrap;
93 print wrap ("| ", " ",
94 (map { "\"$_\"" } (1 .. $size)),
95 " END \n"),
96 " { \$\$ = $size; }\n";
97 };
98 print ";\n";
99
100 print <<\EOF;
101 %%
102 ]AT_YYERROR_DEFINE[
103 static int
104 yylex (void)
105 {
106 static int inner = 1;
107 static int outer = 0;
108 if (outer > MAX)
109 return 0;
110 else if (inner > outer)
111 {
112 inner = 1;
113 ++outer;
114 return END;
115 }
116 return inner++;
117 }
118 ]AT_MAIN_DEFINE[
119 EOF
120 ]])
121 AT_BISON_OPTION_POPDEFS
122
123 AT_CHECK([$PERL -w ./gengram.pl $2 || exit 77], 0, [stdout])
124 mv stdout $1
125 ])
126
127
128 ## -------------- ##
129 ## Big triangle. ##
130 ## -------------- ##
131
132 AT_SETUP([Big triangle])
133
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])
140 AT_COMPILE([input])
141 AT_PARSER_CHECK([./input])
142
143 AT_CLEANUP
144
145
146
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
155
156 use strict;
157 my $max = $ARGV[0] || 10;
158
159 print <<EOF;
160 ]AT_DATA_GRAMMAR_PROLOGUE[
161 %error-verbose
162 %debug
163 %{
164 #include <stdio.h>
165 #include <stdlib.h>
166 #define MAX $max
167 ]AT_YYLEX_DECLARE[
168 ]AT_YYERROR_DECLARE[
169 %}
170
171 %token
172 EOF
173 for my $size (1 .. $max)
174 {
175 print " t$size $size \"$size\"\n";
176 };
177
178 print <<EOF;
179
180 %%
181 EOF
182
183 use Text::Wrap;
184 print
185 wrap ("exp: ", " ",
186 (map { "\"$_\"" } (1 .. $max)), ";"),
187 "\n";
188
189 print <<\EOF;
190 %%
191 #include <assert.h>
192 ]AT_YYERROR_DEFINE[
193 static int
194 yylex (void)
195 {
196 static int counter = 1;
197 if (counter <= MAX)
198 return counter++;
199 assert (counter++ == MAX + 1);
200 return 0;
201 }
202 ]AT_MAIN_DEFINE[
203 EOF
204 ]])
205
206 AT_CHECK([$PERL -w ./gengram.pl $2 || exit 77], 0, [stdout])
207 mv stdout $1
208 AT_BISON_OPTION_POPDEFS
209 ])
210
211
212 ## ---------------- ##
213 ## Big horizontal. ##
214 ## ---------------- ##
215
216 AT_SETUP([Big horizontal])
217
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:
220 #
221 # input.y 263k
222 # input.tab.c 1.3M
223 # input 453k
224 #
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
229 #
230 AT_DATA_HORIZONTAL_GRAMMAR([input.y], [1000])
231
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)
235
236 AT_BISON_CHECK_NO_XML([-v -o input.c input.y])
237 AT_COMPILE([input])
238 AT_PARSER_CHECK([./input])
239
240 AT_CLEANUP
241
242
243
244 # AT_DATA_LOOKAHEAD_TOKENS_GRAMMAR(FILE-NAME, SIZE)
245 # --------------------------------------------------
246 # Create FILE-NAME, containing a self checking parser for a grammar
247 # requiring SIZE lookahead tokens.
248 m4_define([AT_DATA_LOOKAHEAD_TOKENS_GRAMMAR],
249 [AT_BISON_OPTION_PUSHDEFS
250 AT_DATA([[gengram.pl]],
251 [[#! /usr/bin/perl -w
252
253 use strict;
254 use Text::Wrap;
255 my $max = $ARGV[0] || 10;
256
257 print <<EOF;
258 %error-verbose
259 %debug
260 %{
261 ]AT_DATA_SOURCE_PROLOGUE[
262 # include <stdio.h>
263 # include <stdlib.h>
264 # include <assert.h>
265 # define MAX $max
266 ]AT_YYLEX_DECLARE[
267 ]AT_YYERROR_DECLARE[
268 %}
269 %union
270 {
271 int val;
272 };
273
274 %type <val> input exp
275 %token token
276 EOF
277
278 print
279 wrap ("%type <val> ",
280 " ",
281 map { "n$_" } (1 .. $max)),
282 "\n";
283
284 print "%token\n";
285 for my $count (1 .. $max)
286 {
287 print " t$count $count \"$count\"\n";
288 };
289
290 print <<EOF;
291 %%
292 input:
293 exp { assert (\@S|@1 == 1); \$\$ = \@S|@1; }
294 | input exp { assert (\@S|@2 == \@S|@1 + 1); \$\$ = \@S|@2; }
295 ;
296
297 exp:
298 n1 "1" { assert (\@S|@1 == 1); \@S|@\@S|@ = \@S|@1; }
299 EOF
300
301 for my $count (2 .. $max)
302 {
303 print "| n$count \"$count\" { assert (\@S|@1 == $count); \@S|@\@S|@ = \@S|@1; }\n";
304 };
305 print ";\n";
306
307 for my $count (1 .. $max)
308 {
309 print "n$count: token { \$\$ = $count; };\n";
310 };
311
312 print <<\EOF;
313 %%
314 ]AT_YYERROR_DEFINE[
315 static int
316 yylex (void)
317 {
318 static int return_token = 1;
319 static int counter = 1;
320 if (counter > MAX)
321 {
322 assert (counter++ == MAX + 1);
323 return 0;
324 }
325 if (return_token)
326 {
327 return_token = 0;
328 return token;
329 }
330 return_token = 1;
331 return counter++;
332 }
333
334 ]AT_MAIN_DEFINE[
335 EOF
336 ]])
337
338 AT_CHECK([$PERL -w ./gengram.pl $2 || exit 77], 0, [stdout])
339 mv stdout $1
340 AT_BISON_OPTION_POPDEFS
341 ])
342
343
344 ## ------------------------ ##
345 ## Many lookahead tokens. ##
346 ## ------------------------ ##
347
348 AT_SETUP([Many lookahead tokens])
349
350 AT_DATA_LOOKAHEAD_TOKENS_GRAMMAR([input.y], [1000])
351
352 # GNU m4 requires about 70 MiB for this test on a 32-bit host.
353 # Ask for 200 MiB, which should be plenty even on a 64-bit host.
354 AT_INCREASE_DATA_SIZE(204000)
355
356 AT_BISON_CHECK([-v -o input.c input.y])
357 AT_COMPILE([input])
358 AT_PARSER_CHECK([./input])
359
360 AT_CLEANUP
361
362
363
364 # AT_DATA_STACK_TORTURE(C-PROLOGUE, [BISON-DECLS])
365 # ------------------------------------------------
366 # A parser specialized in torturing the stack size.
367 m4_define([AT_DATA_STACK_TORTURE],
368 [AT_BISON_OPTION_PUSHDEFS([$2])
369 # A grammar of parens growing the stack thanks to right recursion.
370 # exp:
371 AT_DATA_GRAMMAR([input.y],
372 [[%{
373 #include <errno.h>
374 #include <limits.h>
375 #include <stdio.h>
376 #include <stdlib.h>
377 ]$1[
378 ]AT_YYLEX_DECLARE[
379 ]AT_YYERROR_DECLARE[
380 %}
381 ]$2[
382 %error-verbose
383 %debug
384 %token WAIT_FOR_EOF
385 %%
386 exp: WAIT_FOR_EOF exp | ;
387 %%
388 ]AT_YYERROR_DEFINE[
389 #include <assert.h>
390 static int
391 yylex (void)
392 {
393 assert (0 <= yylval);
394 if (yylval--)
395 return WAIT_FOR_EOF;
396 else
397 return EOF;
398 }
399
400 /* Return argv[1] as an int. */
401 static int
402 get_args (int argc, const char **argv)
403 {
404 int res;
405 char *endp;
406 assert (argc == 2);
407 res = strtol (argv[1], &endp, 10);
408 assert (argv[1] != endp);
409 assert (0 <= res);
410 assert (res <= INT_MAX);
411 assert (errno != ERANGE);
412 return res;
413 }
414
415 int
416 main (int argc, const char **argv)
417 {
418 YYSTYPE yylval_init = get_args (argc, argv);
419 int status = 0;
420 int count;
421 ]m4_bmatch([$2], [api.push-pull both],
422 [[ yypstate *ps = yypstate_new ();
423 ]])[ yydebug = 1;
424 for (count = 0; count < 2; ++count)
425 {
426 int new_status;
427 yylval = yylval_init;
428 new_status = ]m4_bmatch([$2], [api.push-pull both],
429 [[yypull_parse (ps)]],
430 [[yyparse ()]])[;
431 if (count == 0)
432 status = new_status;
433 else
434 assert (new_status == status);
435 }]m4_bmatch([$2], [api.push-pull both],[[
436 yypstate_delete (ps);]])[
437 return status;
438 }
439 ]])
440 AT_BISON_OPTION_POPDEFS([$2])
441 AT_BISON_CHECK([-o input.c input.y])
442 AT_COMPILE([input])
443 ])
444
445
446 ## -------------------------------------- ##
447 ## Exploding the Stack Size with Alloca. ##
448 ## -------------------------------------- ##
449
450 AT_SETUP([Exploding the Stack Size with Alloca])
451
452 m4_pushdef([AT_USE_ALLOCA], [[
453 #if (defined __GNUC__ || defined __BUILTIN_VA_ARG_INCR \
454 || defined _AIX || defined _MSC_VER || defined _ALLOCA_H)
455 # define YYSTACK_USE_ALLOCA 1
456 #endif
457 ]])
458
459 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA])
460
461 # Below the limit of 200.
462 AT_PARSER_CHECK([./input 20], 0, [], [ignore],
463 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
464 # Two enlargements: 2 * 2 * 200.
465 AT_PARSER_CHECK([./input 900], 0, [], [ignore],
466 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
467 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
468 # multiply by two starting at 200 => 5120 is the last possible).
469 AT_PARSER_CHECK([./input 10000], 2, [], [ignore],
470 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
471
472 # The push parser can't use alloca since the stacks can't be locals. This test
473 # just helps guarantee we don't let the YYSTACK_USE_ALLOCA feature affect
474 # push parsers.
475 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA],
476 [[%define api.push-pull both
477 ]])
478 AT_PARSER_CHECK([./input 20], 0, [], [ignore],
479 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
480 AT_PARSER_CHECK([./input 900], 0, [], [ignore],
481 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
482 AT_PARSER_CHECK([./input 10000], 2, [], [ignore],
483 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
484
485 m4_popdef([AT_USE_ALLOCA])
486
487 AT_CLEANUP
488
489
490
491
492 ## -------------------------------------- ##
493 ## Exploding the Stack Size with Malloc. ##
494 ## -------------------------------------- ##
495
496 AT_SETUP([Exploding the Stack Size with Malloc])
497
498 m4_pushdef([AT_USE_ALLOCA], [[#define YYSTACK_USE_ALLOCA 0]])
499
500 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA])
501
502 # Below the limit of 200.
503 AT_PARSER_CHECK([./input 20], 0, [], [ignore],
504 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
505 # Two enlargements: 2 * 2 * 200.
506 AT_PARSER_CHECK([./input 900], 0, [], [ignore],
507 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
508 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
509 # multiply by two starting at 200 => 5120 is the possible).
510 AT_PARSER_CHECK([./input 10000], 2, [], [ignore],
511 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
512
513 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA],
514 [[%define api.push-pull both
515 ]])
516 AT_PARSER_CHECK([./input 20], 0, [], [ignore],
517 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
518 AT_PARSER_CHECK([./input 900], 0, [], [ignore],
519 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
520 AT_PARSER_CHECK([./input 10000], 2, [], [ignore],
521 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
522
523 m4_popdef([AT_USE_ALLOCA])
524
525 AT_CLEANUP