1 # Torturing Bison. -*- Autotest -*- 2 # Copyright (C) 2001, 2002, 2004, 2005 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., 51 Franklin Street, Fifth Floor, Boston, MA 17 # 02110-1301, 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 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_DATA([[gengram.pl]], 46 [[#! /usr/bin/perl -w 47 48 use strict; 49 my $max = $ARGV[0] || 10; 50 51 print <<EOF; 52 ]AT_DATA_GRAMMAR_PROLOGUE[ 53 %error-verbose 54 %debug 55 %{ 56 #include <stdio.h> 57 #include <stdlib.h> 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 %error-verbose 169 %debug 170 %{ 171 #include <stdio.h> 172 #include <stdlib.h> 173 174 static int yylex (void); 175 static void yyerror (const char *msg); 176 %} 177 178 %token 179 EOF 180 for my $size (1 .. $max) 181 { 182 print " t$size $size \"$size\"\n"; 183 }; 184 185 print <<EOF; 186 187 %% 188 EOF 189 190 use Text::Wrap; 191 print 192 wrap ("exp: ", " ", 193 (map { "\"$_\"" } (1 .. $max)), ";"), 194 "\n"; 195 196 print <<EOF; 197 %% 198 static int 199 yylex (void) 200 { 201 static int counter = 1; 202 if (counter > $max) 203 return 0; 204 else 205 return counter++; 206 } 207 208 static void 209 yyerror (const char *msg) 210 { 211 fprintf (stderr, "%s\\n", msg); 212 } 213 214 int 215 main (void) 216 { 217 yydebug = !!getenv ("YYDEBUG"); 218 return yyparse (); 219 } 220 EOF 221 ]]) 222 223 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout]) 224 mv stdout $1 225 ]) 226 227 228 ## ---------------- ## 229 ## Big horizontal. ## 230 ## ---------------- ## 231 232 AT_SETUP([Big horizontal]) 233 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: 236 # 237 # input.y 263k 238 # input.tab.c 1.3M 239 # input 453k 240 # 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 245 # 246 AT_DATA_HORIZONTAL_GRAMMAR([input.y], [1000]) 247 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) 251 252 AT_CHECK([bison -v -o input.c input.y]) 253 AT_COMPILE([input]) 254 AT_PARSER_CHECK([./input]) 255 256 AT_CLEANUP 257 258 259 260 # AT_DATA_LOOK_AHEAD_TOKENS_GRAMMAR(FILE-NAME, SIZE) 261 # -------------------------------------------------- 262 # Create FILE-NAME, containing a self checking parser for a grammar 263 # requiring SIZE look-ahead tokens. 264 m4_define([AT_DATA_LOOK_AHEAD_TOKENS_GRAMMAR], 265 [AT_DATA([[gengram.pl]], 266 [[#! /usr/bin/perl -w 267 268 use strict; 269 use Text::Wrap; 270 my $max = $ARGV[0] || 10; 271 272 print <<EOF; 273 %error-verbose 274 %debug 275 %{ 276 # include <stdio.h> 277 # include <stdlib.h> 278 # include <assert.h> 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 print "%token\n"; 299 for my $count (1 .. $max) 300 { 301 print " t$count $count \"$count\"\n"; 302 }; 303 304 print <<EOF; 305 %% 306 input: 307 exp { assert (\@S|@1 == 1); \$\$ = \@S|@1; } 308 | input exp { assert (\@S|@2 == \@S|@1 + 1); \$\$ = \@S|@2; } 309 ; 310 311 exp: 312 n1 "1" { assert (\@S|@1 == 1); \@S|@\@S|@ = \@S|@1; } 313 EOF 314 315 for my $count (2 .. $max) 316 { 317 print "| n$count \"$count\" { assert (\@S|@1 == $count); \@S|@\@S|@ = \@S|@1; }\n"; 318 }; 319 print ";\n"; 320 321 for my $count (1 .. $max) 322 { 323 print "n$count: token { \$\$ = $count; };\n"; 324 }; 325 326 print <<EOF; 327 %% 328 static int 329 yylex (void) 330 { 331 static int return_token = 1; 332 static int counter = 1; 333 if (counter > $max) 334 return 0; 335 if (return_token) 336 { 337 return_token = 0; 338 return token; 339 } 340 return_token = 1; 341 return counter++; 342 } 343 344 static void 345 yyerror (const char *msg) 346 { 347 fprintf (stderr, "%s\\n", msg); 348 } 349 350 int 351 main (void) 352 { 353 yydebug = !!getenv ("YYDEBUG"); 354 return yyparse (); 355 } 356 EOF 357 ]]) 358 359 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout]) 360 mv stdout $1 361 ]) 362 363 364 ## ------------------------ ## 365 ## Many look-ahead tokens. ## 366 ## ------------------------ ## 367 368 AT_SETUP([Many look-ahead tokens]) 369 370 AT_DATA_LOOK_AHEAD_TOKENS_GRAMMAR([input.y], [1000]) 371 372 # GNU m4 requires about 70 MiB for this test on a 32-bit host. 373 # Ask for 200 MiB, which should be plenty even on a 64-bit host. 374 AT_INCREASE_DATA_SIZE(204000) 375 376 AT_CHECK([bison -v -o input.c input.y]) 377 AT_COMPILE([input]) 378 AT_PARSER_CHECK([./input]) 379 380 AT_CLEANUP 381 382 383 384 # AT_DATA_STACK_TORTURE(C-PROLOGUE) 385 # --------------------------------- 386 # A parser specialized in torturing the stack size. 387 m4_define([AT_DATA_STACK_TORTURE], 388 [# A grammar of parens growing the stack thanks to right recursion. 389 # exp: 390 AT_DATA([input.y], 391 [[%{ 392 #include <errno.h> 393 #include <limits.h> 394 #include <stdio.h> 395 #include <stdlib.h> 396 ]$1[ 397 static int yylex (void); 398 static void yyerror (const char *msg); 399 %} 400 %error-verbose 401 %debug 402 %token WAIT_FOR_EOF 403 %% 404 exp: WAIT_FOR_EOF exp | ; 405 %% 406 static void 407 yyerror (const char *msg) 408 { 409 fprintf (stderr, "%s\n", msg); 410 } 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 char *endp; 425 if (argc != 2) 426 abort (); 427 yylval = strtol (argv[1], &endp, 10); 428 if (! (argv[1] != endp 429 && 0 <= yylval && yylval <= INT_MAX 430 && errno != ERANGE)) 431 abort (); 432 yydebug = 1; 433 return yyparse (); 434 } 435 ]]) 436 AT_CHECK([bison -o input.c input.y]) 437 AT_COMPILE([input]) 438 ]) 439 440 441 ## -------------------------------------- ## 442 ## Exploding the Stack Size with Alloca. ## 443 ## -------------------------------------- ## 444 445 AT_SETUP([Exploding the Stack Size with Alloca]) 446 447 AT_DATA_STACK_TORTURE([[ 448 #if (defined __GNUC__ || defined __BUILTIN_VA_ARG_INCR \ 449 || defined _AIX || defined _MSC_VER || defined _ALLOCA_H) 450 # define YYSTACK_USE_ALLOCA 1 451 #endif 452 ]]) 453 454 # Below the limit of 200. 455 AT_PARSER_CHECK([./input 20], 0, [], [ignore]) 456 # Two enlargements: 2 * 2 * 200. 457 AT_PARSER_CHECK([./input 900], 0, [], [ignore]) 458 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we 459 # multiply by two starting at 200 => 5120 is the last possible). 460 AT_PARSER_CHECK([./input 10000], 2, [], [ignore]) 461 462 AT_CLEANUP 463 464 465 466 467 ## -------------------------------------- ## 468 ## Exploding the Stack Size with Malloc. ## 469 ## -------------------------------------- ## 470 471 AT_SETUP([Exploding the Stack Size with Malloc]) 472 473 AT_DATA_STACK_TORTURE([[#define YYSTACK_USE_ALLOCA 0]]) 474 475 # Below the limit of 200. 476 AT_PARSER_CHECK([./input 20], 0, [], [ignore]) 477 # Two enlargements: 2 * 2 * 200. 478 AT_PARSER_CHECK([./input 900], 0, [], [ignore]) 479 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we 480 # multiply by two starting at 200 => 5120 is the possible). 481 AT_PARSER_CHECK([./input 10000], 2, [], [ignore]) 482 483 AT_CLEANUP 484
