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