tests/torture.at

   1 # Torturing Bison.                                    -*- Autotest -*-
   2
   3 # Copyright (C) 2001-2002, 2004-2007, 2009-2015, 2018-2021 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 <https://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_REQUIRE([ulimit -S -d $1])
  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 %define parse.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_PERL_REQUIRE([-w ./gengram.pl $2], 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 %define parse.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_PERL_REQUIRE([-w ./gengram.pl $2], 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([-o input.c input.y])
 237 AT_COMPILE([input])
 238 AT_PARSER_CHECK([input])
 239
 240 AT_CLEANUP
 241
 242
 243
 244 ## ------------------- ##
 245 ## State number type.  ##
 246 ## ------------------- ##
 247
 248 # AT_TEST(NUM-STATES, TYPE)
 249 # -------------------------
 250 # Check that automaton with NUM-STATES uses TYPE has state number type.
 251 # Check that parser works.
 252
 253 m4_pushdef([AT_TEST],
 254 [AT_SETUP([State number type: $1 states])
 255
 256 AT_BISON_OPTION_PUSHDEFS
 257
 258 AT_REQUIRE([ruby $abs_top_srcdir/tests/linear $1 >input.y])
 259 # Old versions of GCC reject large values given to #line.
 260 AT_FULL_COMPILE([input], [], [], [], [--no-line])
 261 AT_CHECK([[sed -ne 's/#define YYNSTATES  *\([0-9]*\)/\1/p' input.c]],   [], [$1
 262 ])
 263 AT_CHECK([[sed -ne 's/typedef \(.*\) yy_state_t;/\1/p' input.c]], [], [$2
 264 ])
 265 AT_PARSER_CHECK([input])
 266
 267 AT_BISON_OPTION_POPDEFS
 268 AT_CLEANUP])
 269
 270 AT_TEST(  [128], [yytype_int8])
 271 AT_TEST(  [129], [yytype_uint8])
 272 AT_TEST(  [256], [yytype_uint8])
 273 AT_TEST(  [257], [yytype_int16])
 274 AT_TEST([32768], [yytype_int16])
 275 AT_TEST([65536], [yytype_uint16])
 276 AT_TEST([65537], [int])
 277
 278 m4_popdef([AT_TEST])
 279
 280
 281
 282 ## ------------------------ ##
 283 ## Many lookahead tokens.   ##
 284 ## ------------------------ ##
 285
 286 # AT_DATA_LOOKAHEADS_GRAMMAR(FILE-NAME, SIZE)
 287 # -------------------------------------------
 288 # Create FILE-NAME, containing a self checking parser for a grammar
 289 # requiring SIZE lookahead tokens.
 290 m4_define([AT_DATA_LOOKAHEADS_GRAMMAR],
 291 [AT_BISON_OPTION_PUSHDEFS
 292 AT_DATA([[gengram.pl]],
 293 [[#! /usr/bin/perl -w
 294
 295 use strict;
 296 use Text::Wrap;
 297 my $max = $ARGV[0] || 10;
 298
 299 print <<EOF;
 300 %define parse.error verbose
 301 %debug
 302 %{
 303 ]AT_DATA_SOURCE_PROLOGUE[
 304 # include <stdio.h>
 305 # include <stdlib.h>
 306 # include <assert.h>
 307 # define MAX $max
 308 ]AT_YYLEX_DECLARE[
 309 ]AT_YYERROR_DECLARE[
 310 %}
 311 %union
 312 {
 313   int val;
 314 };
 315
 316 %type <val> input exp
 317 %token token
 318 EOF
 319
 320 print
 321   wrap ("%type <val> ",
 322         "            ",
 323         map { "n$_" } (1 .. $max)),
 324   "\n";
 325
 326 print "%token\n";
 327 for my $count (1 .. $max)
 328   {
 329     print "    t$count $count \"$count\"\n";
 330   };
 331
 332 print <<EOF;
 333 %%
 334 input:
 335   exp        { assert (\@S|@1 == 1); \$\$ = \@S|@1; }
 336 | input exp  { assert (\@S|@2 == \@S|@1 + 1); \$\$ = \@S|@2; }
 337 ;
 338
 339 exp:
 340   n1 "1" { assert (\@S|@1 == 1); \@S|@\@S|@ = \@S|@1; }
 341 EOF
 342
 343 for my $count (2 .. $max)
 344   {
 345     print "| n$count \"$count\" { assert (\@S|@1 == $count); \@S|@\@S|@ = \@S|@1; }\n";
 346   };
 347 print ";\n";
 348
 349 for my $count (1 .. $max)
 350   {
 351     print "n$count: token { \$\$ = $count; };\n";
 352   };
 353
 354 print <<\EOF;
 355 %%
 356 ]AT_YYERROR_DEFINE[
 357 static int
 358 yylex (void)
 359 {
 360   static int return_token = 1;
 361   static int counter = 1;
 362   if (counter > MAX)
 363     {
 364       assert (counter++ == MAX + 1);
 365       return 0;
 366     }
 367   if (return_token)
 368     {
 369       return_token = 0;
 370       return token;
 371     }
 372   return_token = 1;
 373   return counter++;
 374 }
 375
 376 ]AT_MAIN_DEFINE[
 377 EOF
 378 ]])
 379
 380 AT_PERL_REQUIRE([-w ./gengram.pl $2], 0, [stdout])
 381 mv stdout $1
 382 AT_BISON_OPTION_POPDEFS
 383 ])
 384
 385 AT_SETUP([Many lookahead tokens])
 386
 387 AT_DATA_LOOKAHEADS_GRAMMAR([input.y], [1000])
 388
 389 # GNU m4 requires about 70 MiB for this test on a 32-bit host.
 390 # Ask for 200 MiB, which should be plenty even on a 64-bit host.
 391 AT_INCREASE_DATA_SIZE(204000)
 392
 393 AT_BISON_CHECK([-v -o input.c input.y])
 394 AT_COMPILE([input])
 395 AT_PARSER_CHECK([input])
 396
 397 AT_CLEANUP
 398
 399
 400
 401 # AT_DATA_STACK_TORTURE(C-PROLOGUE, [BISON-DECLS])
 402 # ------------------------------------------------
 403 # A parser specialized in torturing the stack size.
 404 m4_define([AT_DATA_STACK_TORTURE],
 405 [AT_BISON_OPTION_PUSHDEFS([$2])
 406 # A grammar of parens growing the stack thanks to right recursion.
 407 AT_DATA_GRAMMAR([input.y],
 408 [[%{
 409 #include <errno.h>
 410 #include <limits.h>
 411 #include <stdio.h>
 412 #include <stdlib.h>
 413 ]$1[
 414   ]AT_YYLEX_DECLARE[
 415   ]AT_YYERROR_DECLARE[
 416 %}
 417 ]$2[
 418 %define parse.error verbose
 419 %token WAIT_FOR_EOF
 420 %%
 421 exp: WAIT_FOR_EOF exp | %empty;
 422 %%
 423 ]AT_YYERROR_DEFINE[
 424 #include <assert.h>
 425 static int
 426 yylex (void)
 427 {
 428   assert (0 <= yylval);
 429   if (yylval--)
 430     return WAIT_FOR_EOF;
 431   else
 432     return EOF;
 433 }
 434
 435 /* Return argv[1] as an int. */
 436 static int
 437 get_args (int argc, const char **argv)
 438 {
 439   long res;
 440   char *endp;
 441   assert (argc == 2); (void) argc;
 442   res = strtol (argv[1], &endp, 10);
 443   assert (argv[1] != endp);
 444   assert (0 <= res);
 445   assert (res <= INT_MAX);
 446   assert (errno != ERANGE);
 447   return YY_CAST (int, res);
 448 }
 449
 450 int
 451 main (int argc, const char **argv)
 452 {
 453   YYSTYPE yylval_init = get_args (argc, argv);
 454   int status = 0;
 455   int count;
 456 ]m4_bmatch([$2], [api.push-pull both],
 457 [[  yypstate *ps = yypstate_new ();
 458 ]])[
 459   for (count = 0; count < 2; ++count)
 460     {
 461       int new_status;
 462       yylval = yylval_init;
 463       new_status = ]m4_bmatch([$2], [api.push-pull both],
 464                               [[yypull_parse (ps)]],
 465                               [[yyparse ()]])[;
 466       if (count == 0)
 467         status = new_status;
 468       else
 469         assert (new_status == status);
 470     }]m4_bmatch([$2], [api.push-pull both], [[
 471   yypstate_delete (ps);]])[
 472   return status;
 473 }
 474 ]])
 475 AT_BISON_OPTION_POPDEFS([$2])
 476 AT_BISON_CHECK([-o input.c input.y])
 477 AT_COMPILE([input])
 478 ])
 479
 480
 481 ## -------------------------------------- ##
 482 ## Exploding the Stack Size with Alloca.  ##
 483 ## -------------------------------------- ##
 484
 485 AT_SETUP([Exploding the Stack Size with Alloca])
 486
 487 m4_pushdef([AT_USE_ALLOCA], [[
 488 #if (defined __GNUC__ || defined __BUILTIN_VA_ARG_INCR \
 489      || defined _AIX || defined _MSC_VER || defined _ALLOCA_H)
 490 # define YYSTACK_USE_ALLOCA 1
 491 #endif
 492 ]])
 493
 494 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA])
 495
 496 # Below the limit of 200.
 497 AT_PARSER_CHECK([input 20], 0, [], [ignore],
 498                 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
 499 # Two enlargements: 2 * 2 * 200.
 500 AT_PARSER_CHECK([input 900], 0, [], [ignore],
 501                 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
 502 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
 503 # multiply by two starting at 200 => 5120 is the last possible).
 504 AT_PARSER_CHECK([input 10000], 2, [], [ignore],
 505                 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
 506
 507 # The push parser can't use alloca since the stacks can't be locals.  This test
 508 # just helps guarantee we don't let the YYSTACK_USE_ALLOCA feature affect
 509 # push parsers.
 510 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA],
 511 [[%define api.push-pull both
 512 ]])
 513 AT_PARSER_CHECK([input 20], 0, [], [ignore],
 514                 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
 515 AT_PARSER_CHECK([input 900], 0, [], [ignore],
 516                 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
 517 AT_PARSER_CHECK([input 10000], 2, [], [ignore],
 518                 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
 519
 520 m4_popdef([AT_USE_ALLOCA])
 521
 522 AT_CLEANUP
 523
 524
 525
 526
 527 ## -------------------------------------- ##
 528 ## Exploding the Stack Size with Malloc.  ##
 529 ## -------------------------------------- ##
 530
 531 AT_SETUP([Exploding the Stack Size with Malloc])
 532
 533 m4_pushdef([AT_USE_ALLOCA], [[#define YYSTACK_USE_ALLOCA 0]])
 534
 535 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA])
 536
 537 # Below the limit of 200.
 538 AT_PARSER_CHECK([input 20], 0, [], [ignore],
 539                 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
 540 # Two enlargements: 2 * 2 * 200.
 541 AT_PARSER_CHECK([input 900], 0, [], [ignore],
 542                 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
 543 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
 544 # multiply by two starting at 200 => 5120 is the possible).
 545 AT_PARSER_CHECK([input 10000], 2, [], [ignore],
 546                 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
 547
 548 AT_DATA_STACK_TORTURE([AT_USE_ALLOCA],
 549 [[%define api.push-pull both
 550 ]])
 551 AT_PARSER_CHECK([input 20], 0, [], [ignore],
 552                 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
 553 AT_PARSER_CHECK([input 900], 0, [], [ignore],
 554                 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
 555 AT_PARSER_CHECK([input 10000], 2, [], [ignore],
 556                 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]])
 557
 558 m4_popdef([AT_USE_ALLOCA])
 559
 560 AT_CLEANUP