1 # Torturing Bison. -*- Autotest -*- 2 3 # Copyright (C) 2001-2002, 2004-2007, 2009-2012 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 int 119 main (void) 120 { 121 yydebug = !!getenv ("YYDEBUG"); 122 return yyparse (); 123 } 124 EOF 125 ]]) 126 AT_BISON_OPTION_POPDEFS 127 128 AT_CHECK([$PERL -w ./gengram.pl $2 || exit 77], 0, [stdout]) 129 mv stdout $1 130 ]) 131 132 133 ## -------------- ## 134 ## Big triangle. ## 135 ## -------------- ## 136 137 AT_SETUP([Big triangle]) 138 139 # I have been able to go up to 2000 on my machine. 140 # I tried 3000, a 29Mb grammar file, but then my system killed bison. 141 # With 500 and the new parser, which consume far too much memory, 142 # it gets killed too. Of course the parser is to be cleaned. 143 AT_DATA_TRIANGULAR_GRAMMAR([input.y], [200]) 144 AT_BISON_CHECK_NO_XML([-v -o input.c input.y]) 145 AT_COMPILE([input]) 146 AT_PARSER_CHECK([./input]) 147 148 AT_CLEANUP 149 150 151 152 # AT_DATA_HORIZONTAL_GRAMMAR(FILE-NAME, SIZE) 153 # ------------------------------------------- 154 # Create FILE-NAME, containing a self checking parser for a huge 155 # horizontal grammar. 156 m4_define([AT_DATA_HORIZONTAL_GRAMMAR], 157 [AT_BISON_OPTION_PUSHDEFS 158 AT_DATA([[gengram.pl]], 159 [[#! /usr/bin/perl -w 160 161 use strict; 162 my $max = $ARGV[0] || 10; 163 164 print <<EOF; 165 ]AT_DATA_GRAMMAR_PROLOGUE[ 166 %error-verbose 167 %debug 168 %{ 169 #include <stdio.h> 170 #include <stdlib.h> 171 #define MAX $max 172 ]AT_YYLEX_DECLARE[ 173 ]AT_YYERROR_DECLARE[ 174 %} 175 176 %token 177 EOF 178 for my $size (1 .. $max) 179 { 180 print " t$size $size \"$size\"\n"; 181 }; 182 183 print <<EOF; 184 185 %% 186 EOF 187 188 use Text::Wrap; 189 print 190 wrap ("exp: ", " ", 191 (map { "\"$_\"" } (1 .. $max)), ";"), 192 "\n"; 193 194 print <<\EOF; 195 %% 196 #include <assert.h> 197 ]AT_YYERROR_DEFINE[ 198 static int 199 yylex (void) 200 { 201 static int counter = 1; 202 if (counter <= MAX) 203 return counter++; 204 assert (counter++ == MAX + 1); 205 return 0; 206 } 207 208 int 209 main (void) 210 { 211 yydebug = !!getenv ("YYDEBUG"); 212 return yyparse (); 213 } 214 EOF 215 ]]) 216 217 AT_CHECK([$PERL -w ./gengram.pl $2 || exit 77], 0, [stdout]) 218 mv stdout $1 219 AT_BISON_OPTION_POPDEFS 220 ]) 221 222 223 ## ---------------- ## 224 ## Big horizontal. ## 225 ## ---------------- ## 226 227 AT_SETUP([Big horizontal]) 228 229 # I have been able to go up to 10000 on my machine, but I had to 230 # increase the maximum stack size (* 100). It gave: 231 # 232 # input.y 263k 233 # input.tab.c 1.3M 234 # input 453k 235 # 236 # gengram.pl 10000 0.70s user 0.01s sys 99% cpu 0.711 total 237 # bison input.y 730.56s user 0.53s sys 99% cpu 12:12.34 total 238 # gcc -Wall input.tab.c -o input 5.81s user 0.20s sys 100% cpu 6.01 total 239 # ./input 0.00s user 0.01s sys 108% cpu 0.01 total 240 # 241 AT_DATA_HORIZONTAL_GRAMMAR([input.y], [1000]) 242 243 # GNU m4 requires about 70 MiB for this test on a 32-bit host. 244 # Ask for 200 MiB, which should be plenty even on a 64-bit host. 245 AT_INCREASE_DATA_SIZE(204000) 246 247 AT_BISON_CHECK_NO_XML([-v -o input.c input.y]) 248 AT_COMPILE([input]) 249 AT_PARSER_CHECK([./input]) 250 251 AT_CLEANUP 252 253 254 255 # AT_DATA_LOOKAHEAD_TOKENS_GRAMMAR(FILE-NAME, SIZE) 256 # -------------------------------------------------- 257 # Create FILE-NAME, containing a self checking parser for a grammar 258 # requiring SIZE lookahead tokens. 259 m4_define([AT_DATA_LOOKAHEAD_TOKENS_GRAMMAR], 260 [AT_BISON_OPTION_PUSHDEFS 261 AT_DATA([[gengram.pl]], 262 [[#! /usr/bin/perl -w 263 264 use strict; 265 use Text::Wrap; 266 my $max = $ARGV[0] || 10; 267 268 print <<EOF; 269 %error-verbose 270 %debug 271 %{ 272 ]AT_DATA_SOURCE_PROLOGUE[ 273 # include <stdio.h> 274 # include <stdlib.h> 275 # include <assert.h> 276 # define MAX $max 277 ]AT_YYLEX_DECLARE[ 278 ]AT_YYERROR_DECLARE[ 279 %} 280 %union 281 { 282 int val; 283 }; 284 285 %type <val> input exp 286 %token token 287 EOF 288 289 print 290 wrap ("%type <val> ", 291 " ", 292 map { "n$_" } (1 .. $max)), 293 "\n"; 294 295 print "%token\n"; 296 for my $count (1 .. $max) 297 { 298 print " t$count $count \"$count\"\n"; 299 }; 300 301 print <<EOF; 302 %% 303 input: 304 exp { assert (\@S|@1 == 1); \$\$ = \@S|@1; } 305 | input exp { assert (\@S|@2 == \@S|@1 + 1); \$\$ = \@S|@2; } 306 ; 307 308 exp: 309 n1 "1" { assert (\@S|@1 == 1); \@S|@\@S|@ = \@S|@1; } 310 EOF 311 312 for my $count (2 .. $max) 313 { 314 print "| n$count \"$count\" { assert (\@S|@1 == $count); \@S|@\@S|@ = \@S|@1; }\n"; 315 }; 316 print ";\n"; 317 318 for my $count (1 .. $max) 319 { 320 print "n$count: token { \$\$ = $count; };\n"; 321 }; 322 323 print <<\EOF; 324 %% 325 ]AT_YYERROR_DEFINE[ 326 static int 327 yylex (void) 328 { 329 static int return_token = 1; 330 static int counter = 1; 331 if (counter > MAX) 332 { 333 assert (counter++ == MAX + 1); 334 return 0; 335 } 336 if (return_token) 337 { 338 return_token = 0; 339 return token; 340 } 341 return_token = 1; 342 return counter++; 343 } 344 345 int 346 main (void) 347 { 348 yydebug = !!getenv ("YYDEBUG"); 349 return yyparse (); 350 } 351 EOF 352 ]]) 353 354 AT_CHECK([$PERL -w ./gengram.pl $2 || exit 77], 0, [stdout]) 355 mv stdout $1 356 AT_BISON_OPTION_POPDEFS 357 ]) 358 359 360 ## ------------------------ ## 361 ## Many lookahead tokens. ## 362 ## ------------------------ ## 363 364 AT_SETUP([Many lookahead tokens]) 365 366 AT_DATA_LOOKAHEAD_TOKENS_GRAMMAR([input.y], [1000]) 367 368 # GNU m4 requires about 70 MiB for this test on a 32-bit host. 369 # Ask for 200 MiB, which should be plenty even on a 64-bit host. 370 AT_INCREASE_DATA_SIZE(204000) 371 372 AT_BISON_CHECK([-v -o input.c input.y]) 373 AT_COMPILE([input]) 374 AT_PARSER_CHECK([./input]) 375 376 AT_CLEANUP 377 378 379 380 # AT_DATA_STACK_TORTURE(C-PROLOGUE, [BISON-DECLS]) 381 # ------------------------------------------------ 382 # A parser specialized in torturing the stack size. 383 m4_define([AT_DATA_STACK_TORTURE], 384 [AT_BISON_OPTION_PUSHDEFS([$2]) 385 # A grammar of parens growing the stack thanks to right recursion. 386 # exp: 387 AT_DATA_GRAMMAR([input.y], 388 [[%{ 389 #include <errno.h> 390 #include <limits.h> 391 #include <stdio.h> 392 #include <stdlib.h> 393 ]$1[ 394 ]AT_YYLEX_DECLARE[ 395 ]AT_YYERROR_DECLARE[ 396 %} 397 ]$2[ 398 %error-verbose 399 %debug 400 %token WAIT_FOR_EOF 401 %% 402 exp: WAIT_FOR_EOF exp | ; 403 %% 404 ]AT_YYERROR_DEFINE[ 405 #include <assert.h> 406 static int 407 yylex (void) 408 { 409 assert (0 <= yylval); 410 if (yylval--) 411 return WAIT_FOR_EOF; 412 else 413 return EOF; 414 } 415 416 /* Return argv[1] as an int. */ 417 static int 418 get_args (int argc, const char **argv) 419 { 420 int res; 421 char *endp; 422 assert (argc == 2); 423 res = strtol (argv[1], &endp, 10); 424 assert (argv[1] != endp); 425 assert (0 <= res); 426 assert (res <= INT_MAX); 427 assert (errno != ERANGE); 428 return res; 429 } 430 431 int 432 main (int argc, const char **argv) 433 { 434 YYSTYPE yylval_init = get_args (argc, argv); 435 int status = 0; 436 int count; 437 ]m4_bmatch([$2], [api.push-pull both], 438 [[ yypstate *ps = yypstate_new (); 439 ]])[ yydebug = 1; 440 for (count = 0; count < 2; ++count) 441 { 442 int new_status; 443 yylval = yylval_init; 444 new_status = ]m4_bmatch([$2], [api.push-pull both], 445 [[yypull_parse (ps)]], 446 [[yyparse ()]])[; 447 if (count == 0) 448 status = new_status; 449 else 450 assert (new_status == status); 451 }]m4_bmatch([$2], [api.push-pull both],[[ 452 yypstate_delete (ps);]])[ 453 return status; 454 } 455 ]]) 456 AT_BISON_OPTION_POPDEFS([$2]) 457 AT_BISON_CHECK([-o input.c input.y]) 458 AT_COMPILE([input]) 459 ]) 460 461 462 ## -------------------------------------- ## 463 ## Exploding the Stack Size with Alloca. ## 464 ## -------------------------------------- ## 465 466 AT_SETUP([Exploding the Stack Size with Alloca]) 467 468 m4_pushdef([AT_USE_ALLOCA], [[ 469 #if (defined __GNUC__ || defined __BUILTIN_VA_ARG_INCR \ 470 || defined _AIX || defined _MSC_VER || defined _ALLOCA_H) 471 # define YYSTACK_USE_ALLOCA 1 472 #endif 473 ]]) 474 475 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA]) 476 477 # Below the limit of 200. 478 AT_PARSER_CHECK([./input 20], 0, [], [ignore], 479 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 480 # Two enlargements: 2 * 2 * 200. 481 AT_PARSER_CHECK([./input 900], 0, [], [ignore], 482 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 483 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we 484 # multiply by two starting at 200 => 5120 is the last possible). 485 AT_PARSER_CHECK([./input 10000], 2, [], [ignore], 486 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 487 488 # The push parser can't use alloca since the stacks can't be locals. This test 489 # just helps guarantee we don't let the YYSTACK_USE_ALLOCA feature affect 490 # push parsers. 491 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA], 492 [[%define api.push-pull both 493 ]]) 494 AT_PARSER_CHECK([./input 20], 0, [], [ignore], 495 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 496 AT_PARSER_CHECK([./input 900], 0, [], [ignore], 497 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 498 AT_PARSER_CHECK([./input 10000], 2, [], [ignore], 499 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 500 501 m4_popdef([AT_USE_ALLOCA]) 502 503 AT_CLEANUP 504 505 506 507 508 ## -------------------------------------- ## 509 ## Exploding the Stack Size with Malloc. ## 510 ## -------------------------------------- ## 511 512 AT_SETUP([Exploding the Stack Size with Malloc]) 513 514 m4_pushdef([AT_USE_ALLOCA], [[#define YYSTACK_USE_ALLOCA 0]]) 515 516 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA]) 517 518 # Below the limit of 200. 519 AT_PARSER_CHECK([./input 20], 0, [], [ignore], 520 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 521 # Two enlargements: 2 * 2 * 200. 522 AT_PARSER_CHECK([./input 900], 0, [], [ignore], 523 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 524 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we 525 # multiply by two starting at 200 => 5120 is the possible). 526 AT_PARSER_CHECK([./input 10000], 2, [], [ignore], 527 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 528 529 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA], 530 [[%define api.push-pull both 531 ]]) 532 AT_PARSER_CHECK([./input 20], 0, [], [ignore], 533 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 534 AT_PARSER_CHECK([./input 900], 0, [], [ignore], 535 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 536 AT_PARSER_CHECK([./input 10000], 2, [], [ignore], 537 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 538 539 m4_popdef([AT_USE_ALLOCA]) 540 541 AT_CLEANUP 542
