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