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 ## ------------------------------------- ##
  23 ## Creating a large artificial grammar.  ##
  24 ## ------------------------------------- ##
  25
  26 # AT_DATA_TRIANGULAR_GRAMMAR(FILE-NAME, SIZE)
  27 # -------------------------------------------
  28 # Create FILE-NAME, containing a self checking parser for a huge
  29 # triangular grammar.
  30 m4_define([AT_DATA_TRIANGULAR_GRAMMAR],
  31 [AT_DATA([[gengram.pl]],
  32 [[#! /usr/bin/perl -w
  33
  34 use strict;
  35 my $max = $ARGV[0] || 10;
  36
  37 print <<EOF;
  38 %{
  39 #include <stdio.h>
  40 #include <stdlib.h>
  41 #include <assert.h>
  42
  43 #define YYERROR_VERBOSE 1
  44 #define YYDEBUG 1
  45
  46 static int yylex (void);
  47 static void yyerror (const char *msg);
  48 %}
  49 %union
  50 {
  51   int val;
  52 };
  53
  54 %token END "end"
  55 %type <val> exp input
  56 EOF
  57
  58 for my $size (1 .. $max)
  59   {
  60     print "%token t$size $size \"$size\"\n";
  61   };
  62
  63 print <<EOF;
  64 %%
  65 input:
  66   exp        { assert (\@S|@1 == 0); \$\$ = \@S|@1; }
  67 | input exp  { assert (\@S|@2 == \@S|@1 + 1); \$\$ = \@S|@2; }
  68 ;
  69
  70 exp:
  71   END
  72     { \$\$ = 0; }
  73 EOF
  74
  75 for my $size (1 .. $max)
  76   {
  77     use Text::Wrap;
  78     print wrap ("| ", "   ",
  79                 (map { "\"$_\"" } (1 .. $size)),
  80                 " END \n"),
  81                   "    { \$\$ = $size; }\n";
  82   };
  83 print ";\n";
  84
  85 print <<EOF;
  86 %%
  87 static int
  88 yylex (void)
  89 {
  90   static int inner = 1;
  91   static int outer = 0;
  92   if (outer > $max)
  93     return 0;
  94   else if (inner > outer)
  95     {
  96       inner = 1;
  97       ++outer;
  98       return END;
  99     }
 100   return inner++;
 101 }
 102
 103 static void
 104 yyerror (const char *msg)
 105 {
 106   fprintf (stderr, "%s\\n", msg);
 107 }
 108
 109 int
 110 main (void)
 111 {
 112   yydebug = !!getenv ("YYDEBUG");
 113   return yyparse ();
 114 }
 115 EOF
 116 ]])
 117
 118 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
 119 mv stdout $1
 120 ])
 121
 122
 123 ## -------------- ##
 124 ## Big triangle.  ##
 125 ## -------------- ##
 126
 127 AT_SETUP([Big triangle])
 128
 129 # I have been able to go up to 2000 on my machine.
 130 # I tried 3000, a 29Mb grammar file, but then my system killed bison.
 131 # With 500 and the new parser, which consume far too much memory,
 132 # it gets killed too.  Of course the parser is to be cleaned.
 133 AT_DATA_TRIANGULAR_GRAMMAR([input.y], [200])
 134 AT_CHECK([bison input.y -v -o input.c])
 135 AT_CHECK([$CC $CFLAGS $CPPFLAGS input.c -o input], 0, [], [ignore])
 136 AT_CHECK([./input])
 137
 138 AT_CLEANUP
 139
 140
 141
 142 # AT_DATA_HORIZONTAL_GRAMMAR(FILE-NAME, SIZE)
 143 # -------------------------------------------
 144 # Create FILE-NAME, containing a self checking parser for a huge
 145 # horizontal grammar.
 146 m4_define([AT_DATA_HORIZONTAL_GRAMMAR],
 147 [AT_DATA([[gengram.pl]],
 148 [[#! /usr/bin/perl -w
 149
 150 use strict;
 151 my $max = $ARGV[0] || 10;
 152
 153 print <<EOF;
 154 %{
 155 #include <stdio.h>
 156 #include <stdlib.h>
 157 #include <assert.h>
 158
 159 #define YYERROR_VERBOSE 1
 160 #define YYDEBUG 1
 161
 162 static int yylex (void);
 163 static void yyerror (const char *msg);
 164 %}
 165 EOF
 166
 167 for my $size (1 .. $max)
 168   {
 169     print "%token t$size $size \"$size\"\n";
 170   };
 171
 172 print <<EOF;
 173 %%
 174 EOF
 175
 176 use Text::Wrap;
 177 print
 178   wrap ("exp: ", "  ",
 179         (map { "\"$_\"" } (1 .. $max)), ";"),
 180   "\n";
 181
 182 print <<EOF;
 183 %%
 184 static int
 185 yylex (void)
 186 {
 187   static int counter = 1;
 188   if (counter > $max)
 189     return 0;
 190   else
 191   return counter++;
 192 }
 193
 194 static void
 195 yyerror (const char *msg)
 196 {
 197   fprintf (stderr, "%s\\n", msg);
 198 }
 199
 200 int
 201 main (void)
 202 {
 203   yydebug = !!getenv ("YYDEBUG");
 204   return yyparse ();
 205 }
 206 EOF
 207 ]])
 208
 209 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
 210 mv stdout $1
 211 ])
 212
 213
 214 ## ---------------- ##
 215 ## Big horizontal.  ##
 216 ## ---------------- ##
 217
 218 AT_SETUP([Big horizontal])
 219
 220 # I have been able to go up to 10000 on my machine, but I had to
 221 # increase the maximum stack size (* 100).  It gave:
 222 #
 223 # input.y      263k
 224 # input.tab.c  1.3M
 225 # input        453k
 226 #
 227 # gengram.pl 10000                 0.70s user 0.01s sys  99% cpu    0.711 total
 228 # bison input.y                  730.56s user 0.53s sys  99% cpu 12:12.34 total
 229 # gcc -Wall input.tab.c -o input   5.81s user 0.20s sys 100% cpu     6.01 total
 230 # ./input                          0.00s user 0.01s sys 108% cpu     0.01 total
 231 #
 232 AT_DATA_HORIZONTAL_GRAMMAR([input.y], [1000])
 233 AT_CHECK([bison input.y -v -o input.c])
 234 AT_CHECK([$CC $CFLAGS $CPPFLAGS input.c -o input], 0, [], [ignore])
 235 AT_CHECK([./input])
 236
 237 AT_CLEANUP
 238
 239
 240
 241 # AT_DATA_LOOKAHEADS_GRAMMAR(FILE-NAME, SIZE)
 242 # -------------------------------------------
 243 # Create FILE-NAME, containing a self checking parser for a grammar
 244 # requiring SIZE lookaheads.
 245 m4_define([AT_DATA_LOOKAHEADS_GRAMMAR],
 246 [AT_DATA([[gengram.pl]],
 247 [[#! /usr/bin/perl -w
 248
 249 use strict;
 250 use Text::Wrap;
 251 my $max = $ARGV[0] || 10;
 252
 253 print <<EOF;
 254 %{
 255 #include <stdio.h>
 256 #include <stdlib.h>
 257 #include <assert.h>
 258
 259 #define YYERROR_VERBOSE 1
 260 #define YYDEBUG 1
 261
 262 static int yylex (void);
 263 static void yyerror (const char *msg);
 264 %}
 265 %union
 266 {
 267   int val;
 268 };
 269
 270 %type <val> input exp
 271 %token token
 272 EOF
 273
 274 print
 275   wrap ("%type <val> ",
 276         "            ",
 277         map { "n$_" } (1 .. $max)),
 278   "\n";
 279
 280 for my $count (1 .. $max)
 281   {
 282     print "%token t$count $count \"$count\"\n";
 283   };
 284
 285 print <<EOF;
 286 %%
 287 input:
 288   exp        { assert (\@S|@1 == 1); \$\$ = \@S|@1; }
 289 | input exp  { assert (\@S|@2 == \@S|@1 + 1); \$\$ = \@S|@2; }
 290 ;
 291
 292 exp:
 293   n1 "1" { assert (\@S|@1 == 1); }
 294 EOF
 295
 296 for my $count (2 .. $max)
 297   {
 298     print "| n$count \"$count\" { assert (\@S|@1 == $count); }\n";
 299   };
 300 print ";\n";
 301
 302 for my $count (1 .. $max)
 303   {
 304     print "n$count: token { \$\$ = $count; };\n";
 305   };
 306
 307 print <<EOF;
 308 %%
 309 static int
 310 yylex (void)
 311 {
 312   static int return_token = 1;
 313   static int counter = 1;
 314   if (counter > $max)
 315     return 0;
 316   if (return_token)
 317     {
 318       return_token = 0;
 319       return token;
 320     }
 321   return_token = 1;
 322   return counter++;
 323 }
 324
 325 static void
 326 yyerror (const char *msg)
 327 {
 328   fprintf (stderr, "%s\\n", msg);
 329 }
 330
 331 int
 332 main (void)
 333 {
 334   yydebug = !!getenv ("YYDEBUG");
 335   return yyparse ();
 336 }
 337 EOF
 338 ]])
 339
 340 AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
 341 mv stdout $1
 342 ])
 343
 344
 345 ## ----------------- ##
 346 ## Many lookaheads.  ##
 347 ## ----------------- ##
 348
 349 AT_SETUP([Many lookaheads])
 350
 351 AT_DATA_LOOKAHEADS_GRAMMAR([input.y], [1000])
 352 AT_CHECK([bison input.y -v -o input.c])
 353 AT_CHECK([$CC $CFLAGS $CPPFLAGS input.c -o input], 0, [], [ignore])
 354 AT_CHECK([./input])
 355
 356 AT_CLEANUP
 357
 358
 359
 360 # AT_DATA_STACK_TORTURE(C-PROLOGUE)
 361 # ---------------------------------
 362 # A parser specialized in torturing the stack size.
 363 m4_define([AT_DATA_STACK_TORTURE],
 364 [# A grammar of parens growing the stack thanks to right recursion.
 365 # exp:
 366 AT_DATA([input.y],
 367 [[%{
 368 #include <stdio.h>
 369 #include <stdlib.h>
 370 #include <assert.h>
 371 ]$1[
 372   static int yylex (void);
 373   static void yyerror (const char *msg);
 374 #define YYPRINT(File, Type, Value)                   \
 375   fprintf (File, " (%d, stack size = %d, max = %d)", \
 376            Value, yyssp - yyss + 1, yystacksize);
 377 %}
 378 %error-verbose
 379 %debug
 380 %token WAIT_FOR_EOF
 381 %%
 382 exp: WAIT_FOR_EOF exp | ;
 383 %%
 384 static void
 385 yyerror (const char *msg)
 386 {
 387   fprintf (stderr, "%s\n", msg);
 388   exit (1);
 389 }
 390
 391 /* There are YYLVAL_MAX of WAIT_FOR_EOFs. */
 392 unsigned int yylval_max;
 393
 394 static int
 395 yylex (void)
 396 {
 397   if (yylval--)
 398     return WAIT_FOR_EOF;
 399   else
 400     return EOF;
 401 }
 402
 403 int
 404 main (int argc, const char **argv)
 405 {
 406   assert (argc == 2);
 407   yylval = atoi (argv[1]);
 408   yydebug = 1;
 409   return yyparse ();
 410 }
 411 ]])
 412 AT_CHECK([bison input.y -o input.c])
 413 AT_CHECK([$CC $CFLAGS $CPPFLAGS input.c -o input], 0, [], [ignore])
 414 ])
 415
 416
 417 ## -------------------------------------- ##
 418 ## Exploding the Stack Size with Alloca.  ##
 419 ## -------------------------------------- ##
 420
 421 AT_SETUP([Exploding the Stack Size with Alloca])
 422
 423 AT_DATA_STACK_TORTURE
 424
 425 # Below the limit of 200.
 426 AT_CHECK([./input 20], 0, [], [ignore])
 427 # Two enlargements: 2 * 2 * 200.
 428 AT_CHECK([./input 900], 0, [], [ignore])
 429 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
 430 # multiply by two starting at 200 => 5120 is the last possible).
 431 AT_CHECK([./input 10000], 1, [], [ignore])
 432
 433 AT_CLEANUP
 434
 435
 436
 437
 438 ## -------------------------------------- ##
 439 ## Exploding the Stack Size with Malloc.  ##
 440 ## -------------------------------------- ##
 441
 442 AT_SETUP([Exploding the Stack Size with Malloc])
 443
 444 AT_DATA_STACK_TORTURE([[#define YYSTACK_USE_ALLOCA 0]])
 445
 446 # Below the limit of 200.
 447 AT_CHECK([./input 20], 0, [], [ignore])
 448 # Two enlargements: 2 * 2 * 200.
 449 AT_CHECK([./input 900], 0, [], [ignore])
 450 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
 451 # multiply by two starting at 200 => 5120 is the possible).
 452 AT_CHECK([./input 10000], 1, [], [ignore])
 453
 454 AT_CLEANUP