tests/torture.at

   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 %{
  54 #include <stdio.h>
  55 #include <stdlib.h>
  56
  57 #define YYERROR_VERBOSE 1
  58 #define YYDEBUG 1
  59
  60 static int yylex (void);
  61 static void yyerror (const char *msg);
  62 %}
  63 %union
  64 {
  65   int val;
  66 };
  67
  68 %token END "end"
  69 %type <val> exp input
  70 EOF
  71
  72 for my $size (1 .. $max)
  73   {
  74     print "%token t$size $size \"$size\"\n";
  75   };
  76
  77 print <<EOF;
  78 %%
  79 input:
  80   exp        { if (\@S|@1 != 0) abort (); \$\$ = \@S|@1; }
  81 | input exp  { if (\@S|@2 != \@S|@1 + 1) abort (); \$\$ = \@S|@2; }
  82 ;
  83
  84 exp:
  85   END
  86     { \$\$ = 0; }
  87 EOF
  88
  89 for my $size (1 .. $max)
  90   {
  91     use Text::Wrap;
  92     print wrap ("| ", "   ",
  93                 (map { "\"$_\"" } (1 .. $size)),
  94                 " END \n"),
  95                   "    { \$\$ = $size; }\n";
  96   };
  97 print ";\n";
  98
  99 print <<EOF;
 100 %%
 101 static int
 102 yylex (void)
 103 {
 104   static int inner = 1;
 105   static int outer = 0;
 106   if (outer > $max)
 107     return 0;
 108   else if (inner > outer)
 109     {
 110       inner = 1;
 111       ++outer;
 112       return END;
 113     }
 114   return inner++;
 115 }
 116
 117 static void
 118 yyerror (const char *msg)
 119 {
 120   fprintf (stderr, "%s\\n", msg);
 121 }
 122
 123 int
 124 main (void)
 125 {
 126   yydebug = !!getenv ("YYDEBUG");
 127   return yyparse ();
 128 }
 129 EOF
 130 ]])
 131
 132 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
 133 mv stdout $1
 134 ])
 135
 136
 137 ## -------------- ##
 138 ## Big triangle.  ##
 139 ## -------------- ##
 140
 141 AT_SETUP([Big triangle])
 142
 143 # I have been able to go up to 2000 on my machine.
 144 # I tried 3000, a 29Mb grammar file, but then my system killed bison.
 145 # With 500 and the new parser, which consume far too much memory,
 146 # it gets killed too.  Of course the parser is to be cleaned.
 147 AT_DATA_TRIANGULAR_GRAMMAR([input.y], [200])
 148 AT_CHECK([bison -v -o input.c input.y])
 149 AT_COMPILE([input])
 150 AT_PARSER_CHECK([./input])
 151
 152 AT_CLEANUP
 153
 154
 155
 156 # AT_DATA_HORIZONTAL_GRAMMAR(FILE-NAME, SIZE)
 157 # -------------------------------------------
 158 # Create FILE-NAME, containing a self checking parser for a huge
 159 # horizontal grammar.
 160 m4_define([AT_DATA_HORIZONTAL_GRAMMAR],
 161 [AT_DATA([[gengram.pl]],
 162 [[#! /usr/bin/perl -w
 163
 164 use strict;
 165 my $max = $ARGV[0] || 10;
 166
 167 print <<EOF;
 168 ]AT_DATA_GRAMMAR_PROLOGUE[
 169 %{
 170 #include <stdio.h>
 171 #include <stdlib.h>
 172
 173 #define YYERROR_VERBOSE 1
 174 #define YYDEBUG 1
 175
 176 static int yylex (void);
 177 static void yyerror (const char *msg);
 178 %}
 179 EOF
 180
 181 for my $size (1 .. $max)
 182   {
 183     print "%token t$size $size \"$size\"\n";
 184   };
 185
 186 print <<EOF;
 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 %{
 274 #include <stdio.h>
 275 #include <stdlib.h>
 276
 277 #define YYERROR_VERBOSE 1
 278 #define YYDEBUG 1
 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 for my $count (1 .. $max)
 299   {
 300     print "%token t$count $count \"$count\"\n";
 301   };
 302
 303 print <<EOF;
 304 %%
 305 input:
 306   exp        { if (\@S|@1 != 1) abort (); \$\$ = \@S|@1; }
 307 | input exp  { if (\@S|@2 != \@S|@1 + 1) abort (); \$\$ = \@S|@2; }
 308 ;
 309
 310 exp:
 311   n1 "1" { if (\@S|@1 != 1) abort (); }
 312 EOF
 313
 314 for my $count (2 .. $max)
 315   {
 316     print "| n$count \"$count\" { if (\@S|@1 != $count) abort (); }\n";
 317   };
 318 print ";\n";
 319
 320 for my $count (1 .. $max)
 321   {
 322     print "n$count: token { \$\$ = $count; };\n";
 323   };
 324
 325 print <<EOF;
 326 %%
 327 static int
 328 yylex (void)
 329 {
 330   static int return_token = 1;
 331   static int counter = 1;
 332   if (counter > $max)
 333     return 0;
 334   if (return_token)
 335     {
 336       return_token = 0;
 337       return token;
 338     }
 339   return_token = 1;
 340   return counter++;
 341 }
 342
 343 static void
 344 yyerror (const char *msg)
 345 {
 346   fprintf (stderr, "%s\\n", msg);
 347 }
 348
 349 int
 350 main (void)
 351 {
 352   yydebug = !!getenv ("YYDEBUG");
 353   return yyparse ();
 354 }
 355 EOF
 356 ]])
 357
 358 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
 359 mv stdout $1
 360 ])
 361
 362
 363 ## ------------------------ ##
 364 ## Many look-ahead tokens.  ##
 365 ## ------------------------ ##
 366
 367 AT_SETUP([Many look-ahead tokens])
 368
 369 AT_DATA_LOOK_AHEAD_TOKENS_GRAMMAR([input.y], [1000])
 370
 371 # GNU m4 requires about 70 MiB for this test on a 32-bit host.
 372 # Ask for 200 MiB, which should be plenty even on a 64-bit host.
 373 AT_INCREASE_DATA_SIZE(204000)
 374
 375 AT_CHECK([bison -v -o input.c input.y])
 376 AT_COMPILE([input])
 377 AT_PARSER_CHECK([./input])
 378
 379 AT_CLEANUP
 380
 381
 382
 383 # AT_DATA_STACK_TORTURE(C-PROLOGUE)
 384 # ---------------------------------
 385 # A parser specialized in torturing the stack size.
 386 m4_define([AT_DATA_STACK_TORTURE],
 387 [# A grammar of parens growing the stack thanks to right recursion.
 388 # exp:
 389 AT_DATA([input.y],
 390 [[%{
 391 #include <errno.h>
 392 #include <limits.h>
 393 #include <stdio.h>
 394 #include <stdlib.h>
 395 ]$1[
 396   static int yylex (void);
 397   static void yyerror (const char *msg);
 398 %}
 399 %error-verbose
 400 %debug
 401 %token WAIT_FOR_EOF
 402 %%
 403 exp: WAIT_FOR_EOF exp | ;
 404 %%
 405 static void
 406 yyerror (const char *msg)
 407 {
 408   fprintf (stderr, "%s\n", msg);
 409 }
 410
 411 static int
 412 yylex (void)
 413 {
 414   if (yylval--)
 415     return WAIT_FOR_EOF;
 416   else
 417     return EOF;
 418 }
 419
 420 int
 421 main (int argc, const char **argv)
 422 {
 423   char *endp;
 424   if (argc != 2)
 425     abort ();
 426   yylval = strtol (argv[1], &endp, 10);
 427   if (! (argv[1] != endp
 428          && 0 <= yylval && yylval <= INT_MAX
 429          && errno != ERANGE))
 430     abort ();
 431   yydebug = 1;
 432   return yyparse ();
 433 }
 434 ]])
 435 AT_CHECK([bison -o input.c input.y])
 436 AT_COMPILE([input])
 437 ])
 438
 439
 440 ## -------------------------------------- ##
 441 ## Exploding the Stack Size with Alloca.  ##
 442 ## -------------------------------------- ##
 443
 444 AT_SETUP([Exploding the Stack Size with Alloca])
 445
 446 AT_DATA_STACK_TORTURE([[
 447 #if defined __GNUC__ || defined alloca
 448 # define YYSTACK_USE_ALLOCA 1
 449 #endif
 450 ]])
 451
 452 # Below the limit of 200.
 453 AT_PARSER_CHECK([./input 20], 0, [], [ignore])
 454 # Two enlargements: 2 * 2 * 200.
 455 AT_PARSER_CHECK([./input 900], 0, [], [ignore])
 456 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
 457 # multiply by two starting at 200 => 5120 is the last possible).
 458 AT_PARSER_CHECK([./input 10000], 2, [], [ignore])
 459
 460 AT_CLEANUP
 461
 462
 463
 464
 465 ## -------------------------------------- ##
 466 ## Exploding the Stack Size with Malloc.  ##
 467 ## -------------------------------------- ##
 468
 469 AT_SETUP([Exploding the Stack Size with Malloc])
 470
 471 AT_DATA_STACK_TORTURE([[#define YYSTACK_USE_ALLOCA 0]])
 472
 473 # Below the limit of 200.
 474 AT_PARSER_CHECK([./input 20], 0, [], [ignore])
 475 # Two enlargements: 2 * 2 * 200.
 476 AT_PARSER_CHECK([./input 900], 0, [], [ignore])
 477 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
 478 # multiply by two starting at 200 => 5120 is the possible).
 479 AT_PARSER_CHECK([./input 10000], 2, [], [ignore])
 480
 481 AT_CLEANUP