1# Torturing Bison. -*- Autotest -*- 2 3# Copyright (C) 2001-2002, 2004-2007, 2009-2012 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 <http://www.gnu.org/licenses/>. 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_BISON_OPTION_PUSHDEFS 46AT_DATA([[gengram.pl]], 47[[#! /usr/bin/perl -w 48 49use strict; 50my $max = $ARGV[0] || 10; 51 52print <<EOF; 53]AT_DATA_GRAMMAR_PROLOGUE[ 54%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 71EOF 72 73for my $size (1 .. $max) 74 { 75 print "%token t$size $size \"$size\"\n"; 76 }; 77 78print <<EOF; 79%% 80input: 81 exp { assert (\@S|@1 == 0); \$\$ = \@S|@1; } 82| input exp { assert (\@S|@2 == \@S|@1 + 1); \$\$ = \@S|@2; } 83; 84 85exp: 86 END 87 { \$\$ = 0; } 88EOF 89 90for my $size (1 .. $max) 91 { 92 use Text::Wrap; 93 print wrap ("| ", " ", 94 (map { "\"$_\"" } (1 .. $size)), 95 " END \n"), 96 " { \$\$ = $size; }\n"; 97 }; 98print ";\n"; 99 100print <<\EOF; 101%% 102]AT_YYERROR_DEFINE[ 103static int 104yylex (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} 118int 119main (void) 120{ 121 yydebug = !!getenv ("YYDEBUG"); 122 return yyparse (); 123} 124EOF 125]]) 126AT_BISON_OPTION_POPDEFS 127 128AT_CHECK([$PERL -w ./gengram.pl $2 || exit 77], 0, [stdout]) 129mv stdout $1 130]) 131 132 133## -------------- ## 134## Big triangle. ## 135## -------------- ## 136 137AT_SETUP([Big triangle]) 138 139# I have been able to go up to 2000 on my machine. 140# I tried 3000, a 29Mb grammar file, but then my system killed bison. 141# With 500 and the new parser, which consume far too much memory, 142# it gets killed too. Of course the parser is to be cleaned. 143AT_DATA_TRIANGULAR_GRAMMAR([input.y], [200]) 144AT_BISON_CHECK_NO_XML([-v -o input.c input.y]) 145AT_COMPILE([input]) 146AT_PARSER_CHECK([./input]) 147 148AT_CLEANUP 149 150 151 152# AT_DATA_HORIZONTAL_GRAMMAR(FILE-NAME, SIZE) 153# ------------------------------------------- 154# Create FILE-NAME, containing a self checking parser for a huge 155# horizontal grammar. 156m4_define([AT_DATA_HORIZONTAL_GRAMMAR], 157[AT_BISON_OPTION_PUSHDEFS 158AT_DATA([[gengram.pl]], 159[[#! /usr/bin/perl -w 160 161use strict; 162my $max = $ARGV[0] || 10; 163 164print <<EOF; 165]AT_DATA_GRAMMAR_PROLOGUE[ 166%error-verbose 167%debug 168%{ 169#include <stdio.h> 170#include <stdlib.h> 171#define MAX $max 172]AT_YYLEX_DECLARE[ 173]AT_YYERROR_DECLARE[ 174%} 175 176%token 177EOF 178for my $size (1 .. $max) 179 { 180 print " t$size $size \"$size\"\n"; 181 }; 182 183print <<EOF; 184 185%% 186EOF 187 188use Text::Wrap; 189print 190 wrap ("exp: ", " ", 191 (map { "\"$_\"" } (1 .. $max)), ";"), 192 "\n"; 193 194print <<\EOF; 195%% 196#include <assert.h> 197]AT_YYERROR_DEFINE[ 198static int 199yylex (void) 200{ 201 static int counter = 1; 202 if (counter <= MAX) 203 return counter++; 204 assert (counter++ == MAX + 1); 205 return 0; 206} 207 208int 209main (void) 210{ 211 yydebug = !!getenv ("YYDEBUG"); 212 return yyparse (); 213} 214EOF 215]]) 216 217AT_CHECK([$PERL -w ./gengram.pl $2 || exit 77], 0, [stdout]) 218mv stdout $1 219AT_BISON_OPTION_POPDEFS 220]) 221 222 223## ---------------- ## 224## Big horizontal. ## 225## ---------------- ## 226 227AT_SETUP([Big horizontal]) 228 229# I have been able to go up to 10000 on my machine, but I had to 230# increase the maximum stack size (* 100). It gave: 231# 232# input.y 263k 233# input.tab.c 1.3M 234# input 453k 235# 236# gengram.pl 10000 0.70s user 0.01s sys 99% cpu 0.711 total 237# bison input.y 730.56s user 0.53s sys 99% cpu 12:12.34 total 238# gcc -Wall input.tab.c -o input 5.81s user 0.20s sys 100% cpu 6.01 total 239# ./input 0.00s user 0.01s sys 108% cpu 0.01 total 240# 241AT_DATA_HORIZONTAL_GRAMMAR([input.y], [1000]) 242 243# GNU m4 requires about 70 MiB for this test on a 32-bit host. 244# Ask for 200 MiB, which should be plenty even on a 64-bit host. 245AT_INCREASE_DATA_SIZE(204000) 246 247AT_BISON_CHECK_NO_XML([-v -o input.c input.y]) 248AT_COMPILE([input]) 249AT_PARSER_CHECK([./input]) 250 251AT_CLEANUP 252 253 254 255# AT_DATA_LOOKAHEAD_TOKENS_GRAMMAR(FILE-NAME, SIZE) 256# -------------------------------------------------- 257# Create FILE-NAME, containing a self checking parser for a grammar 258# requiring SIZE lookahead tokens. 259m4_define([AT_DATA_LOOKAHEAD_TOKENS_GRAMMAR], 260[AT_BISON_OPTION_PUSHDEFS 261AT_DATA([[gengram.pl]], 262[[#! /usr/bin/perl -w 263 264use strict; 265use Text::Wrap; 266my $max = $ARGV[0] || 10; 267 268print <<EOF; 269%error-verbose 270%debug 271%{ 272]AT_DATA_SOURCE_PROLOGUE[ 273# include <stdio.h> 274# include <stdlib.h> 275# include <assert.h> 276# define MAX $max 277]AT_YYLEX_DECLARE[ 278]AT_YYERROR_DECLARE[ 279%} 280%union 281{ 282 int val; 283}; 284 285%type <val> input exp 286%token token 287EOF 288 289print 290 wrap ("%type <val> ", 291 " ", 292 map { "n$_" } (1 .. $max)), 293 "\n"; 294 295print "%token\n"; 296for my $count (1 .. $max) 297 { 298 print " t$count $count \"$count\"\n"; 299 }; 300 301print <<EOF; 302%% 303input: 304 exp { assert (\@S|@1 == 1); \$\$ = \@S|@1; } 305| input exp { assert (\@S|@2 == \@S|@1 + 1); \$\$ = \@S|@2; } 306; 307 308exp: 309 n1 "1" { assert (\@S|@1 == 1); \@S|@\@S|@ = \@S|@1; } 310EOF 311 312for my $count (2 .. $max) 313 { 314 print "| n$count \"$count\" { assert (\@S|@1 == $count); \@S|@\@S|@ = \@S|@1; }\n"; 315 }; 316print ";\n"; 317 318for my $count (1 .. $max) 319 { 320 print "n$count: token { \$\$ = $count; };\n"; 321 }; 322 323print <<\EOF; 324%% 325]AT_YYERROR_DEFINE[ 326static int 327yylex (void) 328{ 329 static int return_token = 1; 330 static int counter = 1; 331 if (counter > MAX) 332 { 333 assert (counter++ == MAX + 1); 334 return 0; 335 } 336 if (return_token) 337 { 338 return_token = 0; 339 return token; 340 } 341 return_token = 1; 342 return counter++; 343} 344 345int 346main (void) 347{ 348 yydebug = !!getenv ("YYDEBUG"); 349 return yyparse (); 350} 351EOF 352]]) 353 354AT_CHECK([$PERL -w ./gengram.pl $2 || exit 77], 0, [stdout]) 355mv stdout $1 356AT_BISON_OPTION_POPDEFS 357]) 358 359 360## ------------------------ ## 361## Many lookahead tokens. ## 362## ------------------------ ## 363 364AT_SETUP([Many lookahead tokens]) 365 366AT_DATA_LOOKAHEAD_TOKENS_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. 370AT_INCREASE_DATA_SIZE(204000) 371 372AT_BISON_CHECK([-v -o input.c input.y]) 373AT_COMPILE([input]) 374AT_PARSER_CHECK([./input]) 375 376AT_CLEANUP 377 378 379 380# AT_DATA_STACK_TORTURE(C-PROLOGUE, [BISON-DECLS]) 381# ------------------------------------------------ 382# A parser specialized in torturing the stack size. 383m4_define([AT_DATA_STACK_TORTURE], 384[AT_BISON_OPTION_PUSHDEFS([$2]) 385# A grammar of parens growing the stack thanks to right recursion. 386# exp: 387AT_DATA_GRAMMAR([input.y], 388[[%{ 389#include <errno.h> 390#include <limits.h> 391#include <stdio.h> 392#include <stdlib.h> 393]$1[ 394 ]AT_YYLEX_DECLARE[ 395 ]AT_YYERROR_DECLARE[ 396%} 397]$2[ 398%error-verbose 399%debug 400%token WAIT_FOR_EOF 401%% 402exp: WAIT_FOR_EOF exp | ; 403%% 404]AT_YYERROR_DEFINE[ 405#include <assert.h> 406static int 407yylex (void) 408{ 409 assert (0 <= yylval); 410 if (yylval--) 411 return WAIT_FOR_EOF; 412 else 413 return EOF; 414} 415 416/* Return argv[1] as an int. */ 417static int 418get_args (int argc, const char **argv) 419{ 420 int res; 421 char *endp; 422 assert (argc == 2); 423 res = strtol (argv[1], &endp, 10); 424 assert (argv[1] != endp); 425 assert (0 <= res); 426 assert (res <= INT_MAX); 427 assert (errno != ERANGE); 428 return res; 429} 430 431int 432main (int argc, const char **argv) 433{ 434 YYSTYPE yylval_init = get_args (argc, argv); 435 int status = 0; 436 int count; 437]m4_bmatch([$2], [api.push-pull both], 438[[ yypstate *ps = yypstate_new (); 439]])[ yydebug = 1; 440 for (count = 0; count < 2; ++count) 441 { 442 int new_status; 443 yylval = yylval_init; 444 new_status = ]m4_bmatch([$2], [api.push-pull both], 445 [[yypull_parse (ps)]], 446 [[yyparse ()]])[; 447 if (count == 0) 448 status = new_status; 449 else 450 assert (new_status == status); 451 }]m4_bmatch([$2], [api.push-pull both],[[ 452 yypstate_delete (ps);]])[ 453 return status; 454} 455]]) 456AT_BISON_OPTION_POPDEFS([$2]) 457AT_BISON_CHECK([-o input.c input.y]) 458AT_COMPILE([input]) 459]) 460 461 462## -------------------------------------- ## 463## Exploding the Stack Size with Alloca. ## 464## -------------------------------------- ## 465 466AT_SETUP([Exploding the Stack Size with Alloca]) 467 468m4_pushdef([AT_USE_ALLOCA], [[ 469#if (defined __GNUC__ || defined __BUILTIN_VA_ARG_INCR \ 470 || defined _AIX || defined _MSC_VER || defined _ALLOCA_H) 471# define YYSTACK_USE_ALLOCA 1 472#endif 473]]) 474 475AT_DATA_STACK_TORTURE([AT_USE_ALLOCA]) 476 477# Below the limit of 200. 478AT_PARSER_CHECK([./input 20], 0, [], [ignore], 479 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 480# Two enlargements: 2 * 2 * 200. 481AT_PARSER_CHECK([./input 900], 0, [], [ignore], 482 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 483# Fails: beyond the limit of 10,000 (which we don't reach anyway since we 484# multiply by two starting at 200 => 5120 is the last possible). 485AT_PARSER_CHECK([./input 10000], 2, [], [ignore], 486 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 487 488# The push parser can't use alloca since the stacks can't be locals. This test 489# just helps guarantee we don't let the YYSTACK_USE_ALLOCA feature affect 490# push parsers. 491AT_DATA_STACK_TORTURE([AT_USE_ALLOCA], 492[[%define api.push-pull both 493]]) 494AT_PARSER_CHECK([./input 20], 0, [], [ignore], 495 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 496AT_PARSER_CHECK([./input 900], 0, [], [ignore], 497 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 498AT_PARSER_CHECK([./input 10000], 2, [], [ignore], 499 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 500 501m4_popdef([AT_USE_ALLOCA]) 502 503AT_CLEANUP 504 505 506 507 508## -------------------------------------- ## 509## Exploding the Stack Size with Malloc. ## 510## -------------------------------------- ## 511 512AT_SETUP([Exploding the Stack Size with Malloc]) 513 514m4_pushdef([AT_USE_ALLOCA], [[#define YYSTACK_USE_ALLOCA 0]]) 515 516AT_DATA_STACK_TORTURE([AT_USE_ALLOCA]) 517 518# Below the limit of 200. 519AT_PARSER_CHECK([./input 20], 0, [], [ignore], 520 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 521# Two enlargements: 2 * 2 * 200. 522AT_PARSER_CHECK([./input 900], 0, [], [ignore], 523 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 524# Fails: beyond the limit of 10,000 (which we don't reach anyway since we 525# multiply by two starting at 200 => 5120 is the possible). 526AT_PARSER_CHECK([./input 10000], 2, [], [ignore], 527 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 528 529AT_DATA_STACK_TORTURE([AT_USE_ALLOCA], 530[[%define api.push-pull both 531]]) 532AT_PARSER_CHECK([./input 20], 0, [], [ignore], 533 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 534AT_PARSER_CHECK([./input 900], 0, [], [ignore], 535 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 536AT_PARSER_CHECK([./input 10000], 2, [], [ignore], 537 [[VALGRIND_OPTS="$VALGRIND_OPTS --log-fd=1"]]) 538 539m4_popdef([AT_USE_ALLOCA]) 540 541AT_CLEANUP 542