OLD | NEW |
(Empty) | |
| 1 # Torturing Bison. -*- Autotest -*- |
| 2 # Copyright (C) 2001, 2002, 2004, 2005, 2006, 2007 Free Software Foundation, |
| 3 # Inc. |
| 4 |
| 5 # This program is free software: you can redistribute it and/or modify |
| 6 # it under the terms of the GNU General Public License as published by |
| 7 # the Free Software Foundation, either version 3 of the License, or |
| 8 # (at your option) any later version. |
| 9 # |
| 10 # This program is distributed in the hope that it will be useful, |
| 11 # but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 13 # GNU General Public License for more details. |
| 14 # |
| 15 # You should have received a copy of the GNU General Public License |
| 16 # along with this program. If not, see <http://www.gnu.org/licenses/>. |
| 17 |
| 18 AT_BANNER([[Torture Tests.]]) |
| 19 |
| 20 |
| 21 # AT_INCREASE_DATA_SIZE(SIZE) |
| 22 # --------------------------- |
| 23 # Try to increase the data size to SIZE KiB if possible. |
| 24 m4_define([AT_INCREASE_DATA_SIZE], |
| 25 [data_limit=`(ulimit -S -d) 2>/dev/null` |
| 26 case $data_limit in |
| 27 [[0-9]]*) |
| 28 if test "$data_limit" -lt $1; then |
| 29 AT_CHECK([ulimit -S -d $1 || exit 77]) |
| 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 %error-verbose |
| 53 %debug |
| 54 %{ |
| 55 #include <stdio.h> |
| 56 #include <stdlib.h> |
| 57 |
| 58 static int yylex (void); |
| 59 static void yyerror (const char *msg); |
| 60 %} |
| 61 %union |
| 62 { |
| 63 int val; |
| 64 }; |
| 65 |
| 66 %token END "end" |
| 67 %type <val> exp input |
| 68 EOF |
| 69 |
| 70 for my $size (1 .. $max) |
| 71 { |
| 72 print "%token t$size $size \"$size\"\n"; |
| 73 }; |
| 74 |
| 75 print <<EOF; |
| 76 %% |
| 77 input: |
| 78 exp { if (\@S|@1 != 0) abort (); \$\$ = \@S|@1; } |
| 79 | input exp { if (\@S|@2 != \@S|@1 + 1) abort (); \$\$ = \@S|@2; } |
| 80 ; |
| 81 |
| 82 exp: |
| 83 END |
| 84 { \$\$ = 0; } |
| 85 EOF |
| 86 |
| 87 for my $size (1 .. $max) |
| 88 { |
| 89 use Text::Wrap; |
| 90 print wrap ("| ", " ", |
| 91 (map { "\"$_\"" } (1 .. $size)), |
| 92 " END \n"), |
| 93 " { \$\$ = $size; }\n"; |
| 94 }; |
| 95 print ";\n"; |
| 96 |
| 97 print <<EOF; |
| 98 %% |
| 99 static int |
| 100 yylex (void) |
| 101 { |
| 102 static int inner = 1; |
| 103 static int outer = 0; |
| 104 if (outer > $max) |
| 105 return 0; |
| 106 else if (inner > outer) |
| 107 { |
| 108 inner = 1; |
| 109 ++outer; |
| 110 return END; |
| 111 } |
| 112 return inner++; |
| 113 } |
| 114 |
| 115 static void |
| 116 yyerror (const char *msg) |
| 117 { |
| 118 fprintf (stderr, "%s\\n", msg); |
| 119 } |
| 120 |
| 121 int |
| 122 main (void) |
| 123 { |
| 124 yydebug = !!getenv ("YYDEBUG"); |
| 125 return yyparse (); |
| 126 } |
| 127 EOF |
| 128 ]]) |
| 129 |
| 130 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout]) |
| 131 mv stdout $1 |
| 132 ]) |
| 133 |
| 134 |
| 135 ## -------------- ## |
| 136 ## Big triangle. ## |
| 137 ## -------------- ## |
| 138 |
| 139 AT_SETUP([Big triangle]) |
| 140 |
| 141 # I have been able to go up to 2000 on my machine. |
| 142 # I tried 3000, a 29Mb grammar file, but then my system killed bison. |
| 143 # With 500 and the new parser, which consume far too much memory, |
| 144 # it gets killed too. Of course the parser is to be cleaned. |
| 145 AT_DATA_TRIANGULAR_GRAMMAR([input.y], [200]) |
| 146 AT_BISON_CHECK_NO_XML([-v -o input.c input.y]) |
| 147 AT_COMPILE([input]) |
| 148 AT_PARSER_CHECK([./input]) |
| 149 |
| 150 AT_CLEANUP |
| 151 |
| 152 |
| 153 |
| 154 # AT_DATA_HORIZONTAL_GRAMMAR(FILE-NAME, SIZE) |
| 155 # ------------------------------------------- |
| 156 # Create FILE-NAME, containing a self checking parser for a huge |
| 157 # horizontal grammar. |
| 158 m4_define([AT_DATA_HORIZONTAL_GRAMMAR], |
| 159 [AT_DATA([[gengram.pl]], |
| 160 [[#! /usr/bin/perl -w |
| 161 |
| 162 use strict; |
| 163 my $max = $ARGV[0] || 10; |
| 164 |
| 165 print <<EOF; |
| 166 ]AT_DATA_GRAMMAR_PROLOGUE[ |
| 167 %error-verbose |
| 168 %debug |
| 169 %{ |
| 170 #include <stdio.h> |
| 171 #include <stdlib.h> |
| 172 |
| 173 static int yylex (void); |
| 174 static void yyerror (const char *msg); |
| 175 %} |
| 176 |
| 177 %token |
| 178 EOF |
| 179 for my $size (1 .. $max) |
| 180 { |
| 181 print " t$size $size \"$size\"\n"; |
| 182 }; |
| 183 |
| 184 print <<EOF; |
| 185 |
| 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 counter++; |
| 203 if (counter++ != $max + 1) |
| 204 abort (); |
| 205 return 0; |
| 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_BISON_CHECK_NO_XML([-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_LOOKAHEAD_TOKENS_GRAMMAR(FILE-NAME, SIZE) |
| 261 # -------------------------------------------------- |
| 262 # Create FILE-NAME, containing a self checking parser for a grammar |
| 263 # requiring SIZE lookahead tokens. |
| 264 m4_define([AT_DATA_LOOKAHEAD_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 { |
| 335 if (counter++ != $max + 1) |
| 336 abort (); |
| 337 return 0; |
| 338 } |
| 339 if (return_token) |
| 340 { |
| 341 return_token = 0; |
| 342 return token; |
| 343 } |
| 344 return_token = 1; |
| 345 return counter++; |
| 346 } |
| 347 |
| 348 static void |
| 349 yyerror (const char *msg) |
| 350 { |
| 351 fprintf (stderr, "%s\\n", msg); |
| 352 } |
| 353 |
| 354 int |
| 355 main (void) |
| 356 { |
| 357 yydebug = !!getenv ("YYDEBUG"); |
| 358 return yyparse (); |
| 359 } |
| 360 EOF |
| 361 ]]) |
| 362 |
| 363 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout]) |
| 364 mv stdout $1 |
| 365 ]) |
| 366 |
| 367 |
| 368 ## ------------------------ ## |
| 369 ## Many lookahead tokens. ## |
| 370 ## ------------------------ ## |
| 371 |
| 372 AT_SETUP([Many lookahead tokens]) |
| 373 |
| 374 AT_DATA_LOOKAHEAD_TOKENS_GRAMMAR([input.y], [1000]) |
| 375 |
| 376 # GNU m4 requires about 70 MiB for this test on a 32-bit host. |
| 377 # Ask for 200 MiB, which should be plenty even on a 64-bit host. |
| 378 AT_INCREASE_DATA_SIZE(204000) |
| 379 |
| 380 AT_BISON_CHECK([-v -o input.c input.y]) |
| 381 AT_COMPILE([input]) |
| 382 AT_PARSER_CHECK([./input]) |
| 383 |
| 384 AT_CLEANUP |
| 385 |
| 386 |
| 387 |
| 388 # AT_DATA_STACK_TORTURE(C-PROLOGUE, [BISON-DECLS]) |
| 389 # ------------------------------------------------ |
| 390 # A parser specialized in torturing the stack size. |
| 391 m4_define([AT_DATA_STACK_TORTURE], |
| 392 [# A grammar of parens growing the stack thanks to right recursion. |
| 393 # exp: |
| 394 AT_DATA([input.y], |
| 395 [[%{ |
| 396 #include <errno.h> |
| 397 #include <limits.h> |
| 398 #include <stdio.h> |
| 399 #include <stdlib.h> |
| 400 ]$1[ |
| 401 static int yylex (void); |
| 402 static void yyerror (const char *msg); |
| 403 %} |
| 404 ]$2[ |
| 405 %error-verbose |
| 406 %debug |
| 407 %token WAIT_FOR_EOF |
| 408 %% |
| 409 exp: WAIT_FOR_EOF exp | ; |
| 410 %% |
| 411 static void |
| 412 yyerror (const char *msg) |
| 413 { |
| 414 fprintf (stderr, "%s\n", msg); |
| 415 } |
| 416 |
| 417 static int |
| 418 yylex (void) |
| 419 { |
| 420 if (yylval < 0) |
| 421 abort (); |
| 422 if (yylval--) |
| 423 return WAIT_FOR_EOF; |
| 424 else |
| 425 return EOF; |
| 426 } |
| 427 |
| 428 int |
| 429 main (int argc, const char **argv) |
| 430 { |
| 431 char *endp; |
| 432 YYSTYPE yylval_init; |
| 433 if (argc != 2) |
| 434 abort (); |
| 435 yylval_init = strtol (argv[1], &endp, 10); |
| 436 if (! (argv[1] != endp |
| 437 && 0 <= yylval_init && yylval_init <= INT_MAX |
| 438 && errno != ERANGE)) |
| 439 abort (); |
| 440 yydebug = 1; |
| 441 { |
| 442 int count; |
| 443 int status; |
| 444 ]m4_bmatch([$2], [%push-], |
| 445 [[ yypstate *ps = yypstate_new (); |
| 446 ]])[ for (count = 0; count < 2; ++count) |
| 447 { |
| 448 int new_status; |
| 449 yylval = yylval_init; |
| 450 ]m4_bmatch([$2], [%push-], |
| 451 [[ new_status = yypull_parse (ps); |
| 452 ]], |
| 453 [[ new_status = yyparse (); |
| 454 ]])[ if (count > 0 && new_status != status) |
| 455 abort (); |
| 456 status = new_status; |
| 457 } |
| 458 ]m4_bmatch([$2], [%push-], |
| 459 [[ yypstate_delete (ps); |
| 460 ]])[ return status; |
| 461 } |
| 462 } |
| 463 ]]) |
| 464 AT_BISON_CHECK([-o input.c input.y]) |
| 465 AT_COMPILE([input]) |
| 466 ]) |
| 467 |
| 468 |
| 469 ## -------------------------------------- ## |
| 470 ## Exploding the Stack Size with Alloca. ## |
| 471 ## -------------------------------------- ## |
| 472 |
| 473 AT_SETUP([Exploding the Stack Size with Alloca]) |
| 474 |
| 475 m4_pushdef([AT_USE_ALLOCA], [[ |
| 476 #if (defined __GNUC__ || defined __BUILTIN_VA_ARG_INCR \ |
| 477 || defined _AIX || defined _MSC_VER || defined _ALLOCA_H) |
| 478 # define YYSTACK_USE_ALLOCA 1 |
| 479 #endif |
| 480 ]]) |
| 481 |
| 482 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA]) |
| 483 |
| 484 # Below the limit of 200. |
| 485 AT_PARSER_CHECK([./input 20], 0, [], [ignore], |
| 486 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) |
| 487 # Two enlargements: 2 * 2 * 200. |
| 488 AT_PARSER_CHECK([./input 900], 0, [], [ignore], |
| 489 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) |
| 490 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we |
| 491 # multiply by two starting at 200 => 5120 is the last possible). |
| 492 AT_PARSER_CHECK([./input 10000], 2, [], [ignore], |
| 493 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) |
| 494 |
| 495 # The push parser can't use alloca since the stacks can't be locals. This test |
| 496 # just helps guarantee we don't let the YYSTACK_USE_ALLOCA feature affect |
| 497 # push parsers. |
| 498 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA], |
| 499 [[%define api.push_pull "both" |
| 500 ]]) |
| 501 AT_PARSER_CHECK([./input 20], 0, [], [ignore], |
| 502 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) |
| 503 AT_PARSER_CHECK([./input 900], 0, [], [ignore], |
| 504 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) |
| 505 AT_PARSER_CHECK([./input 10000], 2, [], [ignore], |
| 506 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) |
| 507 |
| 508 m4_popdef([AT_USE_ALLOCA]) |
| 509 |
| 510 AT_CLEANUP |
| 511 |
| 512 |
| 513 |
| 514 |
| 515 ## -------------------------------------- ## |
| 516 ## Exploding the Stack Size with Malloc. ## |
| 517 ## -------------------------------------- ## |
| 518 |
| 519 AT_SETUP([Exploding the Stack Size with Malloc]) |
| 520 |
| 521 m4_pushdef([AT_USE_ALLOCA], [[#define YYSTACK_USE_ALLOCA 0]]) |
| 522 |
| 523 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA]) |
| 524 |
| 525 # Below the limit of 200. |
| 526 AT_PARSER_CHECK([./input 20], 0, [], [ignore], |
| 527 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) |
| 528 # Two enlargements: 2 * 2 * 200. |
| 529 AT_PARSER_CHECK([./input 900], 0, [], [ignore], |
| 530 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) |
| 531 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we |
| 532 # multiply by two starting at 200 => 5120 is the possible). |
| 533 AT_PARSER_CHECK([./input 10000], 2, [], [ignore], |
| 534 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) |
| 535 |
| 536 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA], |
| 537 [[%define api.push_pull "both" |
| 538 ]]) |
| 539 AT_PARSER_CHECK([./input 20], 0, [], [ignore], |
| 540 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) |
| 541 AT_PARSER_CHECK([./input 900], 0, [], [ignore], |
| 542 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) |
| 543 AT_PARSER_CHECK([./input 10000], 2, [], [ignore], |
| 544 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) |
| 545 |
| 546 m4_popdef([AT_USE_ALLOCA]) |
| 547 |
| 548 AT_CLEANUP |
OLD | NEW |