]> git.saurik.com Git - bison.git/blob - tests/torture.at
(nullable_compute): Do not subtract from the returned value of malloc.
[bison.git] / tests / torture.at
1 # Torturing Bison. -*- Autotest -*-
2 # Copyright (C) 2001, 2002 Free Software Foundation, Inc.
3
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)
7 # any later version.
8
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.
13
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
17 # 02111-1307, USA.
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 ulimit -S -d $1
31 fi
32 esac])
33
34
35 ## ------------------------------------- ##
36 ## Creating a large artificial grammar. ##
37 ## ------------------------------------- ##
38
39 # AT_DATA_TRIANGULAR_GRAMMAR(FILE-NAME, SIZE)
40 # -------------------------------------------
41 # Create FILE-NAME, containing a self checking parser for a huge
42 # triangular grammar.
43 m4_define([AT_DATA_TRIANGULAR_GRAMMAR],
44 [AT_DATA([[gengram.pl]],
45 [[#! /usr/bin/perl -w
46
47 use strict;
48 my $max = $ARGV[0] || 10;
49
50 print <<EOF;
51 ]AT_DATA_GRAMMAR_PROLOGUE[
52 %{
53 #include <stdio.h>
54 #include <stdlib.h>
55
56 #define YYERROR_VERBOSE 1
57 #define YYDEBUG 1
58
59 static int yylex (void);
60 static void yyerror (const char *msg);
61 %}
62 %union
63 {
64 int val;
65 };
66
67 %token END "end"
68 %type <val> exp input
69 EOF
70
71 for my $size (1 .. $max)
72 {
73 print "%token t$size $size \"$size\"\n";
74 };
75
76 print <<EOF;
77 %%
78 input:
79 exp { if (\@S|@1 != 0) abort (); \$\$ = \@S|@1; }
80 | input exp { if (\@S|@2 != \@S|@1 + 1) abort (); \$\$ = \@S|@2; }
81 ;
82
83 exp:
84 END
85 { \$\$ = 0; }
86 EOF
87
88 for my $size (1 .. $max)
89 {
90 use Text::Wrap;
91 print wrap ("| ", " ",
92 (map { "\"$_\"" } (1 .. $size)),
93 " END \n"),
94 " { \$\$ = $size; }\n";
95 };
96 print ";\n";
97
98 print <<EOF;
99 %%
100 static int
101 yylex (void)
102 {
103 static int inner = 1;
104 static int outer = 0;
105 if (outer > $max)
106 return 0;
107 else if (inner > outer)
108 {
109 inner = 1;
110 ++outer;
111 return END;
112 }
113 return inner++;
114 }
115
116 static void
117 yyerror (const char *msg)
118 {
119 fprintf (stderr, "%s\\n", msg);
120 }
121
122 int
123 main (void)
124 {
125 yydebug = !!getenv ("YYDEBUG");
126 return yyparse ();
127 }
128 EOF
129 ]])
130
131 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
132 mv stdout $1
133 ])
134
135
136 ## -------------- ##
137 ## Big triangle. ##
138 ## -------------- ##
139
140 AT_SETUP([Big triangle])
141
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 -v -o input.c input.y])
148 AT_COMPILE([input])
149 AT_PARSER_CHECK([./input])
150
151 AT_CLEANUP
152
153
154
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
162
163 use strict;
164 my $max = $ARGV[0] || 10;
165
166 print <<EOF;
167 ]AT_DATA_GRAMMAR_PROLOGUE[
168 %{
169 #include <stdio.h>
170 #include <stdlib.h>
171
172 #define YYERROR_VERBOSE 1
173 #define YYDEBUG 1
174
175 static int yylex (void);
176 static void yyerror (const char *msg);
177 %}
178 EOF
179
180 for my $size (1 .. $max)
181 {
182 print "%token t$size $size \"$size\"\n";
183 };
184
185 print <<EOF;
186 %%
187 EOF
188
189 use Text::Wrap;
190 print
191 wrap ("exp: ", " ",
192 (map { "\"$_\"" } (1 .. $max)), ";"),
193 "\n";
194
195 print <<EOF;
196 %%
197 static int
198 yylex (void)
199 {
200 static int counter = 1;
201 if (counter > $max)
202 return 0;
203 else
204 return counter++;
205 }
206
207 static void
208 yyerror (const char *msg)
209 {
210 fprintf (stderr, "%s\\n", msg);
211 }
212
213 int
214 main (void)
215 {
216 yydebug = !!getenv ("YYDEBUG");
217 return yyparse ();
218 }
219 EOF
220 ]])
221
222 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
223 mv stdout $1
224 ])
225
226
227 ## ---------------- ##
228 ## Big horizontal. ##
229 ## ---------------- ##
230
231 AT_SETUP([Big horizontal])
232
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:
235 #
236 # input.y 263k
237 # input.tab.c 1.3M
238 # input 453k
239 #
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
244 #
245 AT_DATA_HORIZONTAL_GRAMMAR([input.y], [1000])
246
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)
250
251 AT_CHECK([bison -v -o input.c input.y])
252 AT_COMPILE([input])
253 AT_PARSER_CHECK([./input])
254
255 AT_CLEANUP
256
257
258
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
266
267 use strict;
268 use Text::Wrap;
269 my $max = $ARGV[0] || 10;
270
271 print <<EOF;
272 %{
273 #include <stdio.h>
274 #include <stdlib.h>
275
276 #define YYERROR_VERBOSE 1
277 #define YYDEBUG 1
278
279 static int yylex (void);
280 static void yyerror (const char *msg);
281 %}
282 %union
283 {
284 int val;
285 };
286
287 %type <val> input exp
288 %token token
289 EOF
290
291 print
292 wrap ("%type <val> ",
293 " ",
294 map { "n$_" } (1 .. $max)),
295 "\n";
296
297 for my $count (1 .. $max)
298 {
299 print "%token t$count $count \"$count\"\n";
300 };
301
302 print <<EOF;
303 %%
304 input:
305 exp { if (\@S|@1 != 1) abort (); \$\$ = \@S|@1; }
306 | input exp { if (\@S|@2 != \@S|@1 + 1) abort (); \$\$ = \@S|@2; }
307 ;
308
309 exp:
310 n1 "1" { if (\@S|@1 != 1) abort (); }
311 EOF
312
313 for my $count (2 .. $max)
314 {
315 print "| n$count \"$count\" { if (\@S|@1 != $count) abort (); }\n";
316 };
317 print ";\n";
318
319 for my $count (1 .. $max)
320 {
321 print "n$count: token { \$\$ = $count; };\n";
322 };
323
324 print <<EOF;
325 %%
326 static int
327 yylex (void)
328 {
329 static int return_token = 1;
330 static int counter = 1;
331 if (counter > $max)
332 return 0;
333 if (return_token)
334 {
335 return_token = 0;
336 return token;
337 }
338 return_token = 1;
339 return counter++;
340 }
341
342 static void
343 yyerror (const char *msg)
344 {
345 fprintf (stderr, "%s\\n", msg);
346 }
347
348 int
349 main (void)
350 {
351 yydebug = !!getenv ("YYDEBUG");
352 return yyparse ();
353 }
354 EOF
355 ]])
356
357 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
358 mv stdout $1
359 ])
360
361
362 ## ----------------- ##
363 ## Many lookaheads. ##
364 ## ----------------- ##
365
366 AT_SETUP([Many lookaheads])
367
368 AT_DATA_LOOKAHEADS_GRAMMAR([input.y], [1000])
369
370 # GNU m4 requires about 70 MiB for this test on a 32-bit host.
371 # Ask for 200 MiB, which should be plenty even on a 64-bit host.
372 AT_INCREASE_DATA_SIZE(204000)
373
374 AT_CHECK([bison -v -o input.c input.y])
375 AT_COMPILE([input])
376 AT_PARSER_CHECK([./input])
377
378 AT_CLEANUP
379
380
381
382 # AT_DATA_STACK_TORTURE(C-PROLOGUE)
383 # ---------------------------------
384 # A parser specialized in torturing the stack size.
385 m4_define([AT_DATA_STACK_TORTURE],
386 [# A grammar of parens growing the stack thanks to right recursion.
387 # exp:
388 AT_DATA([input.y],
389 [[%{
390 #include <stdio.h>
391 #include <stdlib.h>
392 ]$1[
393 static int yylex (void);
394 static void yyerror (const char *msg);
395 %}
396 %error-verbose
397 %debug
398 %token WAIT_FOR_EOF
399 %%
400 exp: WAIT_FOR_EOF exp | ;
401 %%
402 static void
403 yyerror (const char *msg)
404 {
405 fprintf (stderr, "%s\n", msg);
406 exit (1);
407 }
408
409 /* There are YYLVAL_MAX of WAIT_FOR_EOFs. */
410 unsigned int yylval_max;
411
412 static int
413 yylex (void)
414 {
415 if (yylval--)
416 return WAIT_FOR_EOF;
417 else
418 return EOF;
419 }
420
421 int
422 main (int argc, const char **argv)
423 {
424 if (argc != 2)
425 abort ();
426 yylval = atoi (argv[1]);
427 yydebug = 1;
428 return yyparse ();
429 }
430 ]])
431 AT_CHECK([bison -o input.c input.y])
432 AT_COMPILE([input])
433 ])
434
435
436 ## -------------------------------------- ##
437 ## Exploding the Stack Size with Alloca. ##
438 ## -------------------------------------- ##
439
440 AT_SETUP([Exploding the Stack Size with Alloca])
441
442 AT_DATA_STACK_TORTURE
443
444 # Below the limit of 200.
445 AT_PARSER_CHECK([./input 20], 0, [], [ignore])
446 # Two enlargements: 2 * 2 * 200.
447 AT_PARSER_CHECK([./input 900], 0, [], [ignore])
448 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
449 # multiply by two starting at 200 => 5120 is the last possible).
450 AT_PARSER_CHECK([./input 10000], 1, [], [ignore])
451
452 AT_CLEANUP
453
454
455
456
457 ## -------------------------------------- ##
458 ## Exploding the Stack Size with Malloc. ##
459 ## -------------------------------------- ##
460
461 AT_SETUP([Exploding the Stack Size with Malloc])
462
463 AT_DATA_STACK_TORTURE([[#define YYSTACK_USE_ALLOCA 0]])
464
465 # Below the limit of 200.
466 AT_PARSER_CHECK([./input 20], 0, [], [ignore])
467 # Two enlargements: 2 * 2 * 200.
468 AT_PARSER_CHECK([./input 900], 0, [], [ignore])
469 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
470 # multiply by two starting at 200 => 5120 is the possible).
471 AT_PARSER_CHECK([./input 10000], 1, [], [ignore])
472
473 AT_CLEANUP