tests/torture.at

   1 # Torturing Bison.                                    -*- Autotest -*-
   2 # Copyright (C) 2001, 2002 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., 59 Temple Place - Suite 330, Boston, MA
  17 # 02111-1307, 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     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 %{
  52 #include <stdio.h>
  53 #include <stdlib.h>
  54
  55 #define YYERROR_VERBOSE 1
  56 #define YYDEBUG 1
  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_CHECK([bison -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 %{
 167 #include <stdio.h>
 168 #include <stdlib.h>
 169
 170 #define YYERROR_VERBOSE 1
 171 #define YYDEBUG 1
 172
 173 static int yylex (void);
 174 static void yyerror (const char *msg);
 175 %}
 176 EOF
 177
 178 for my $size (1 .. $max)
 179   {
 180     print "%token t$size $size \"$size\"\n";
 181   };
 182
 183 print <<EOF;
 184 %%
 185 EOF
 186
 187 use Text::Wrap;
 188 print
 189   wrap ("exp: ", "  ",
 190         (map { "\"$_\"" } (1 .. $max)), ";"),
 191   "\n";
 192
 193 print <<EOF;
 194 %%
 195 static int
 196 yylex (void)
 197 {
 198   static int counter = 1;
 199   if (counter > $max)
 200     return 0;
 201   else
 202   return counter++;
 203 }
 204
 205 static void
 206 yyerror (const char *msg)
 207 {
 208   fprintf (stderr, "%s\\n", msg);
 209 }
 210
 211 int
 212 main (void)
 213 {
 214   yydebug = !!getenv ("YYDEBUG");
 215   return yyparse ();
 216 }
 217 EOF
 218 ]])
 219
 220 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
 221 mv stdout $1
 222 ])
 223
 224
 225 ## ---------------- ##
 226 ## Big horizontal.  ##
 227 ## ---------------- ##
 228
 229 AT_SETUP([Big horizontal])
 230
 231 # I have been able to go up to 10000 on my machine, but I had to
 232 # increase the maximum stack size (* 100).  It gave:
 233 #
 234 # input.y      263k
 235 # input.tab.c  1.3M
 236 # input        453k
 237 #
 238 # gengram.pl 10000                 0.70s user 0.01s sys  99% cpu    0.711 total
 239 # bison input.y                  730.56s user 0.53s sys  99% cpu 12:12.34 total
 240 # gcc -Wall input.tab.c -o input   5.81s user 0.20s sys 100% cpu     6.01 total
 241 # ./input                          0.00s user 0.01s sys 108% cpu     0.01 total
 242 #
 243 AT_DATA_HORIZONTAL_GRAMMAR([input.y], [1000])
 244
 245 # GNU m4 requires about 70 MiB for this test on a 32-bit host.
 246 # Ask for 200 MiB, which should be plenty even on a 64-bit host.
 247 AT_INCREASE_DATA_SIZE(204000)
 248
 249 AT_CHECK([bison -v -o input.c input.y])
 250 AT_COMPILE([input])
 251 AT_PARSER_CHECK([./input])
 252
 253 AT_CLEANUP
 254
 255
 256
 257 # AT_DATA_LOOKAHEADS_GRAMMAR(FILE-NAME, SIZE)
 258 # -------------------------------------------
 259 # Create FILE-NAME, containing a self checking parser for a grammar
 260 # requiring SIZE lookaheads.
 261 m4_define([AT_DATA_LOOKAHEADS_GRAMMAR],
 262 [AT_DATA([[gengram.pl]],
 263 [[#! /usr/bin/perl -w
 264
 265 use strict;
 266 use Text::Wrap;
 267 my $max = $ARGV[0] || 10;
 268
 269 print <<EOF;
 270 %{
 271 #include <stdio.h>
 272 #include <stdlib.h>
 273
 274 #define YYERROR_VERBOSE 1
 275 #define YYDEBUG 1
 276
 277 static int yylex (void);
 278 static void yyerror (const char *msg);
 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 for my $count (1 .. $max)
 296   {
 297     print "%token t$count $count \"$count\"\n";
 298   };
 299
 300 print <<EOF;
 301 %%
 302 input:
 303   exp        { if (\@S|@1 != 1) abort (); \$\$ = \@S|@1; }
 304 | input exp  { if (\@S|@2 != \@S|@1 + 1) abort (); \$\$ = \@S|@2; }
 305 ;
 306
 307 exp:
 308   n1 "1" { if (\@S|@1 != 1) abort (); }
 309 EOF
 310
 311 for my $count (2 .. $max)
 312   {
 313     print "| n$count \"$count\" { if (\@S|@1 != $count) abort (); }\n";
 314   };
 315 print ";\n";
 316
 317 for my $count (1 .. $max)
 318   {
 319     print "n$count: token { \$\$ = $count; };\n";
 320   };
 321
 322 print <<EOF;
 323 %%
 324 static int
 325 yylex (void)
 326 {
 327   static int return_token = 1;
 328   static int counter = 1;
 329   if (counter > $max)
 330     return 0;
 331   if (return_token)
 332     {
 333       return_token = 0;
 334       return token;
 335     }
 336   return_token = 1;
 337   return counter++;
 338 }
 339
 340 static void
 341 yyerror (const char *msg)
 342 {
 343   fprintf (stderr, "%s\\n", msg);
 344 }
 345
 346 int
 347 main (void)
 348 {
 349   yydebug = !!getenv ("YYDEBUG");
 350   return yyparse ();
 351 }
 352 EOF
 353 ]])
 354
 355 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
 356 mv stdout $1
 357 ])
 358
 359
 360 ## ----------------- ##
 361 ## Many lookaheads.  ##
 362 ## ----------------- ##
 363
 364 AT_SETUP([Many lookaheads])
 365
 366 AT_DATA_LOOKAHEADS_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_CHECK([bison -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)
 381 # ---------------------------------
 382 # A parser specialized in torturing the stack size.
 383 m4_define([AT_DATA_STACK_TORTURE],
 384 [# A grammar of parens growing the stack thanks to right recursion.
 385 # exp:
 386 AT_DATA([input.y],
 387 [[%{
 388 #include <stdio.h>
 389 #include <stdlib.h>
 390 ]$1[
 391   static int yylex (void);
 392   static void yyerror (const char *msg);
 393 %}
 394 %error-verbose
 395 %debug
 396 %token WAIT_FOR_EOF
 397 %%
 398 exp: WAIT_FOR_EOF exp | ;
 399 %%
 400 static void
 401 yyerror (const char *msg)
 402 {
 403   fprintf (stderr, "%s\n", msg);
 404   exit (1);
 405 }
 406
 407 /* There are YYLVAL_MAX of WAIT_FOR_EOFs. */
 408 unsigned int yylval_max;
 409
 410 static int
 411 yylex (void)
 412 {
 413   if (yylval--)
 414     return WAIT_FOR_EOF;
 415   else
 416     return EOF;
 417 }
 418
 419 int
 420 main (int argc, const char **argv)
 421 {
 422   if (argc != 2)
 423     abort ();
 424   yylval = atoi (argv[1]);
 425   yydebug = 1;
 426   return yyparse ();
 427 }
 428 ]])
 429 AT_CHECK([bison -o input.c input.y])
 430 AT_COMPILE([input])
 431 ])
 432
 433
 434 ## -------------------------------------- ##
 435 ## Exploding the Stack Size with Alloca.  ##
 436 ## -------------------------------------- ##
 437
 438 AT_SETUP([Exploding the Stack Size with Alloca])
 439
 440 AT_DATA_STACK_TORTURE
 441
 442 # Below the limit of 200.
 443 AT_PARSER_CHECK([./input 20], 0, [], [ignore])
 444 # Two enlargements: 2 * 2 * 200.
 445 AT_PARSER_CHECK([./input 900], 0, [], [ignore])
 446 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
 447 # multiply by two starting at 200 => 5120 is the last possible).
 448 AT_PARSER_CHECK([./input 10000], 1, [], [ignore])
 449
 450 AT_CLEANUP
 451
 452
 453
 454
 455 ## -------------------------------------- ##
 456 ## Exploding the Stack Size with Malloc.  ##
 457 ## -------------------------------------- ##
 458
 459 AT_SETUP([Exploding the Stack Size with Malloc])
 460
 461 AT_DATA_STACK_TORTURE([[#define YYSTACK_USE_ALLOCA 0]])
 462
 463 # Below the limit of 200.
 464 AT_PARSER_CHECK([./input 20], 0, [], [ignore])
 465 # Two enlargements: 2 * 2 * 200.
 466 AT_PARSER_CHECK([./input 900], 0, [], [ignore])
 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 possible).
 469 AT_PARSER_CHECK([./input 10000], 1, [], [ignore])
 470
 471 AT_CLEANUP