]> git.saurik.com Git - bison.git/blob - tests/torture.at
(AT_INCREASE_DATA_SIZE): New macro.
[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 %{
52 #include <stdio.h>
53 #include <stdlib.h>
54 #include <assert.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 { assert (\@S|@1 == 0); \$\$ = \@S|@1; }
80 | input exp { assert (\@S|@2 == \@S|@1 + 1); \$\$ = \@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 input.y -v -o input.c])
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 %{
168 #include <stdio.h>
169 #include <stdlib.h>
170 #include <assert.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 input.y -v -o input.c])
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 #include <assert.h>
276
277 #define YYERROR_VERBOSE 1
278 #define YYDEBUG 1
279
280 static int yylex (void);
281 static void yyerror (const char *msg);
282 %}
283 %union
284 {
285 int val;
286 };
287
288 %type <val> input exp
289 %token token
290 EOF
291
292 print
293 wrap ("%type <val> ",
294 " ",
295 map { "n$_" } (1 .. $max)),
296 "\n";
297
298 for my $count (1 .. $max)
299 {
300 print "%token t$count $count \"$count\"\n";
301 };
302
303 print <<EOF;
304 %%
305 input:
306 exp { assert (\@S|@1 == 1); \$\$ = \@S|@1; }
307 | input exp { assert (\@S|@2 == \@S|@1 + 1); \$\$ = \@S|@2; }
308 ;
309
310 exp:
311 n1 "1" { assert (\@S|@1 == 1); }
312 EOF
313
314 for my $count (2 .. $max)
315 {
316 print "| n$count \"$count\" { assert (\@S|@1 == $count); }\n";
317 };
318 print ";\n";
319
320 for my $count (1 .. $max)
321 {
322 print "n$count: token { \$\$ = $count; };\n";
323 };
324
325 print <<EOF;
326 %%
327 static int
328 yylex (void)
329 {
330 static int return_token = 1;
331 static int counter = 1;
332 if (counter > $max)
333 return 0;
334 if (return_token)
335 {
336 return_token = 0;
337 return token;
338 }
339 return_token = 1;
340 return counter++;
341 }
342
343 static void
344 yyerror (const char *msg)
345 {
346 fprintf (stderr, "%s\\n", msg);
347 }
348
349 int
350 main (void)
351 {
352 yydebug = !!getenv ("YYDEBUG");
353 return yyparse ();
354 }
355 EOF
356 ]])
357
358 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
359 mv stdout $1
360 ])
361
362
363 ## ----------------- ##
364 ## Many lookaheads. ##
365 ## ----------------- ##
366
367 AT_SETUP([Many lookaheads])
368
369 AT_DATA_LOOKAHEADS_GRAMMAR([input.y], [1000])
370
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)
374
375 AT_CHECK([bison input.y -v -o input.c])
376 AT_COMPILE([input])
377 AT_PARSER_CHECK([./input])
378
379 AT_CLEANUP
380
381
382
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.
388 # exp:
389 AT_DATA([input.y],
390 [[%{
391 #include <stdio.h>
392 #include <stdlib.h>
393 #include <assert.h>
394 ]$1[
395 static int yylex (void);
396 static void yyerror (const char *msg);
397 %}
398 %error-verbose
399 %debug
400 %token WAIT_FOR_EOF
401 %%
402 exp: WAIT_FOR_EOF exp | ;
403 %%
404 static void
405 yyerror (const char *msg)
406 {
407 fprintf (stderr, "%s\n", msg);
408 exit (1);
409 }
410
411 /* There are YYLVAL_MAX of WAIT_FOR_EOFs. */
412 unsigned int yylval_max;
413
414 static int
415 yylex (void)
416 {
417 if (yylval--)
418 return WAIT_FOR_EOF;
419 else
420 return EOF;
421 }
422
423 int
424 main (int argc, const char **argv)
425 {
426 assert (argc == 2);
427 yylval = atoi (argv[1]);
428 yydebug = 1;
429 return yyparse ();
430 }
431 ]])
432 AT_CHECK([bison input.y -o input.c])
433 AT_COMPILE([input])
434 ])
435
436
437 ## -------------------------------------- ##
438 ## Exploding the Stack Size with Alloca. ##
439 ## -------------------------------------- ##
440
441 AT_SETUP([Exploding the Stack Size with Alloca])
442
443 AT_DATA_STACK_TORTURE
444
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])
452
453 AT_CLEANUP
454
455
456
457
458 ## -------------------------------------- ##
459 ## Exploding the Stack Size with Malloc. ##
460 ## -------------------------------------- ##
461
462 AT_SETUP([Exploding the Stack Size with Malloc])
463
464 AT_DATA_STACK_TORTURE([[#define YYSTACK_USE_ALLOCA 0]])
465
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])
473
474 AT_CLEANUP