tests/torture.at

   1 # Torturing Bison.                                    -*- Autotest -*-
   2 # Copyright 2001 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_DATA_STACK_TORTURE(C-PROLOGUE)
  23 # ---------------------------------
  24 # A parser specialized in torturing the stack size.
  25 m4_define([AT_DATA_STACK_TORTURE],
  26 [# A grammar of parens growing the stack thanks to right recursion.
  27 # exp:
  28 AT_DATA([input.y],
  29 [[%{
  30 #include <stdio.h>
  31 #include <stdlib.h>
  32 #include <assert.h>
  33 ]$1[
  34   static int yylex (void);
  35   static void yyerror (const char *msg);
  36 #define YYPRINT(File, Type, Value)                   \
  37   fprintf (File, " (%d, stack size = %d, max = %d)", \
  38            Value, yyssp - yyss + 1, yystacksize);
  39 %}
  40 %error-verbose
  41 %debug
  42 %token WAIT_FOR_EOF
  43 %%
  44 exp: WAIT_FOR_EOF exp | ;
  45 %%
  46 static void
  47 yyerror (const char *msg)
  48 {
  49   fprintf (stderr, "%s\n", msg);
  50   exit (1);
  51 }
  52
  53 /* There are YYLVAL_MAX of WAIT_FOR_EOFs. */
  54 unsigned int yylval_max;
  55
  56 static int
  57 yylex (void)
  58 {
  59   if (yylval--)
  60     return WAIT_FOR_EOF;
  61   else
  62     return EOF;
  63 }
  64
  65 int
  66 main (int argc, const char **argv)
  67 {
  68   assert (argc == 2);
  69   yylval = atoi (argv[1]);
  70   yydebug = 1;
  71   return yyparse ();
  72 }
  73 ]])
  74 AT_CHECK([bison input.y -o input.c])
  75 AT_CHECK([$CC $CFLAGS $CPPFLAGS input.c -o input], 0, [], [ignore])
  76 ])
  77
  78
  79 ## -------------------------------------- ##
  80 ## Exploding the Stack Size with Alloca.  ##
  81 ## -------------------------------------- ##
  82
  83 AT_SETUP([Exploding the Stack Size with Alloca])
  84
  85 AT_DATA_STACK_TORTURE
  86
  87 # Below the limit of 200.
  88 AT_CHECK([input 20], 0, [], [ignore])
  89 # Two enlargements: 2 * 2 * 200.
  90 AT_CHECK([input 900], 0, [], [ignore])
  91 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
  92 # multiply by two starting at 200 => 5120 is the last possible).
  93 AT_CHECK([input 10000], 1, [], [ignore])
  94
  95 AT_CLEANUP
  96
  97
  98
  99
 100 ## -------------------------------------- ##
 101 ## Exploding the Stack Size with Malloc.  ##
 102 ## -------------------------------------- ##
 103
 104 AT_SETUP([Exploding the Stack Size with Malloc])
 105
 106 AT_DATA_STACK_TORTURE([[#define YYSTACK_USE_ALLOCA 0]])
 107
 108 # Below the limit of 200.
 109 AT_CHECK([input 20], 0, [], [ignore])
 110 # Two enlargements: 2 * 2 * 200.
 111 AT_CHECK([input 900], 0, [], [ignore])
 112 # Fails: beyond the limit of 10,000 (which we don't reach anyway since we
 113 # multiply by two starting at 200 => 5120 is the possible).
 114 AT_CHECK([input 10000], 1, [], [ignore])
 115
 116 AT_CLEANUP
 117
 118
 119 ## ----------------- ##
 120 ## GNU AWK Grammar.  ##
 121 ## ----------------- ##
 122
 123 AT_SETUP([GNU AWK Grammar])
 124
 125 # We have been careful to strip all the actions excepts the
 126 # mid-rule actions.  We rely on %expect to check that there are
 127 # indeed 65 SR conflicts.
 128 #
 129 # Bison was once wrong, due to an incorrect computation of nullable.
 130 # It reported 485 SR conflicts!
 131
 132 AT_DATA([[input.y]],
 133 [[%expect 65
 134
 135 %token FUNC_CALL NAME REGEXP
 136 %token ERROR
 137 %token YNUMBER YSTRING
 138 %token RELOP APPEND_OP
 139 %token ASSIGNOP MATCHOP NEWLINE CONCAT_OP
 140 %token LEX_BEGIN LEX_END LEX_IF LEX_ELSE LEX_RETURN LEX_DELETE
 141 %token LEX_WHILE LEX_DO LEX_FOR LEX_BREAK LEX_CONTINUE
 142 %token LEX_PRINT LEX_PRINTF LEX_NEXT LEX_EXIT LEX_FUNCTION
 143 %token LEX_GETLINE LEX_NEXTFILE
 144 %token LEX_IN
 145 %token LEX_AND LEX_OR INCREMENT DECREMENT
 146 %token LEX_BUILTIN LEX_LENGTH
 147
 148 /* Lowest to highest */
 149 %right ASSIGNOP
 150 %right '?' ':'
 151 %left LEX_OR
 152 %left LEX_AND
 153 %left LEX_GETLINE
 154 %nonassoc LEX_IN
 155 %left FUNC_CALL LEX_BUILTIN LEX_LENGTH
 156 %nonassoc ','
 157 %nonassoc MATCHOP
 158 %nonassoc RELOP '<' '>' '|' APPEND_OP TWOWAYIO
 159 %left CONCAT_OP
 160 %left YSTRING YNUMBER
 161 %left '+' '-'
 162 %left '*' '/' '%'
 163 %right '!' UNARY
 164 %right '^'
 165 %left INCREMENT DECREMENT
 166 %left '$'
 167 %left '(' ')'
 168 %%
 169
 170 start
 171         : opt_nls program opt_nls
 172         ;
 173
 174 program
 175         : rule
 176         | program rule
 177         | error
 178         | program error
 179         | /* empty */
 180         ;
 181
 182 rule
 183         : LEX_BEGIN {} action
 184         | LEX_END {}   action
 185         | LEX_BEGIN statement_term
 186         | LEX_END statement_term
 187         | pattern action
 188         | action
 189         | pattern statement_term
 190         | function_prologue function_body
 191         ;
 192
 193 func_name
 194         : NAME
 195         | FUNC_CALL
 196         | lex_builtin
 197         ;
 198
 199 lex_builtin
 200         : LEX_BUILTIN
 201         | LEX_LENGTH
 202         ;
 203
 204 function_prologue
 205         : LEX_FUNCTION {} func_name '(' opt_param_list r_paren opt_nls
 206         ;
 207
 208 function_body
 209         : l_brace statements r_brace opt_semi opt_nls
 210         | l_brace r_brace opt_semi opt_nls
 211         ;
 212
 213
 214 pattern
 215         : exp
 216         | exp ',' exp
 217         ;
 218
 219 regexp
 220         /*
 221          * In this rule, want_regexp tells yylex that the next thing
 222          * is a regexp so it should read up to the closing slash.
 223          */
 224         : '/' {} REGEXP '/'
 225         ;
 226
 227 action
 228         : l_brace statements r_brace opt_semi opt_nls
 229         | l_brace r_brace opt_semi opt_nls
 230         ;
 231
 232 statements
 233         : statement
 234         | statements statement
 235         | error
 236         | statements error
 237         ;
 238
 239 statement_term
 240         : nls
 241         | semi opt_nls
 242         ;
 243
 244 statement
 245         : semi opt_nls
 246         | l_brace r_brace
 247         | l_brace statements r_brace
 248         | if_statement
 249         | LEX_WHILE '(' exp r_paren opt_nls statement
 250         | LEX_DO opt_nls statement LEX_WHILE '(' exp r_paren opt_nls
 251         | LEX_FOR '(' NAME LEX_IN NAME r_paren opt_nls statement
 252         | LEX_FOR '(' opt_exp semi opt_nls exp semi opt_nls opt_exp r_paren opt_nls statement
 253         | LEX_FOR '(' opt_exp semi opt_nls semi opt_nls opt_exp r_paren opt_nls statement
 254         | LEX_BREAK statement_term
 255         | LEX_CONTINUE statement_term
 256         | print '(' expression_list r_paren output_redir statement_term
 257         | print opt_rexpression_list output_redir statement_term
 258         | LEX_NEXT statement_term
 259         | LEX_NEXTFILE statement_term
 260         | LEX_EXIT opt_exp statement_term
 261         | LEX_RETURN {} opt_exp statement_term
 262         | LEX_DELETE NAME '[' expression_list ']' statement_term
 263         | LEX_DELETE NAME  statement_term
 264         | exp statement_term
 265         ;
 266
 267 print
 268         : LEX_PRINT
 269         | LEX_PRINTF
 270         ;
 271
 272 if_statement
 273         : LEX_IF '(' exp r_paren opt_nls statement
 274         | LEX_IF '(' exp r_paren opt_nls statement
 275              LEX_ELSE opt_nls statement
 276         ;
 277
 278 nls
 279         : NEWLINE
 280         | nls NEWLINE
 281         ;
 282
 283 opt_nls
 284         : /* empty */
 285         | nls
 286         ;
 287
 288 input_redir
 289         : /* empty */
 290         | '<' simp_exp
 291         ;
 292
 293 output_redir
 294         : /* empty */
 295         | '>' exp
 296         | APPEND_OP exp
 297         | '|' exp
 298         | TWOWAYIO exp
 299         ;
 300
 301 opt_param_list
 302         : /* empty */
 303         | param_list
 304         ;
 305
 306 param_list
 307         : NAME
 308         | param_list comma NAME
 309         | error
 310         | param_list error
 311         | param_list comma error
 312         ;
 313
 314 /* optional expression, as in for loop */
 315 opt_exp
 316         : /* empty */
 317         | exp
 318         ;
 319
 320 opt_rexpression_list
 321         : /* empty */
 322         | rexpression_list
 323         ;
 324
 325 rexpression_list
 326         : rexp
 327         | rexpression_list comma rexp
 328         | error
 329         | rexpression_list error
 330         | rexpression_list error rexp
 331         | rexpression_list comma error
 332         ;
 333
 334 opt_expression_list
 335         : /* empty */
 336         | expression_list
 337         ;
 338
 339 expression_list
 340         : exp
 341         | expression_list comma exp
 342         | error
 343         | expression_list error
 344         | expression_list error exp
 345         | expression_list comma error
 346         ;
 347
 348 /* Expressions, not including the comma operator.  */
 349 exp     : variable ASSIGNOP {} exp
 350         | '(' expression_list r_paren LEX_IN NAME
 351         | exp '|' LEX_GETLINE opt_variable
 352         | exp TWOWAYIO LEX_GETLINE opt_variable
 353         | LEX_GETLINE opt_variable input_redir
 354         | exp LEX_AND exp
 355         | exp LEX_OR exp
 356         | exp MATCHOP exp
 357         | regexp
 358         | '!' regexp %prec UNARY
 359         | exp LEX_IN NAME
 360         | exp RELOP exp
 361         | exp '<' exp
 362         | exp '>' exp
 363         | exp '?' exp ':' exp
 364         | simp_exp
 365         | exp simp_exp %prec CONCAT_OP
 366         ;
 367
 368 rexp
 369         : variable ASSIGNOP {} rexp
 370         | rexp LEX_AND rexp
 371         | rexp LEX_OR rexp
 372         | LEX_GETLINE opt_variable input_redir
 373         | regexp
 374         | '!' regexp %prec UNARY
 375         | rexp MATCHOP rexp
 376         | rexp LEX_IN NAME
 377         | rexp RELOP rexp
 378         | rexp '?' rexp ':' rexp
 379         | simp_exp
 380         | rexp simp_exp %prec CONCAT_OP
 381         ;
 382
 383 simp_exp
 384         : non_post_simp_exp
 385         /* Binary operators in order of decreasing precedence.  */
 386         | simp_exp '^' simp_exp
 387         | simp_exp '*' simp_exp
 388         | simp_exp '/' simp_exp
 389         | simp_exp '%' simp_exp
 390         | simp_exp '+' simp_exp
 391         | simp_exp '-' simp_exp
 392         | variable INCREMENT
 393         | variable DECREMENT
 394         ;
 395
 396 non_post_simp_exp
 397         : '!' simp_exp %prec UNARY
 398         | '(' exp r_paren
 399         | LEX_BUILTIN
 400           '(' opt_expression_list r_paren
 401         | LEX_LENGTH '(' opt_expression_list r_paren
 402         | LEX_LENGTH
 403         | FUNC_CALL '(' opt_expression_list r_paren
 404         | variable
 405         | INCREMENT variable
 406         | DECREMENT variable
 407         | YNUMBER
 408         | YSTRING
 409         | '-' simp_exp    %prec UNARY
 410         | '+' simp_exp    %prec UNARY
 411         ;
 412
 413 opt_variable
 414         : /* empty */
 415         | variable
 416         ;
 417
 418 variable
 419         : NAME
 420         | NAME '[' expression_list ']'
 421         | '$' non_post_simp_exp
 422         ;
 423
 424 l_brace
 425         : '{' opt_nls
 426         ;
 427
 428 r_brace
 429         : '}' opt_nls
 430         ;
 431
 432 r_paren
 433         : ')'
 434         ;
 435
 436 opt_semi
 437         : /* empty */
 438         | semi
 439         ;
 440
 441 semi
 442         : ';'
 443         ;
 444
 445 comma   : ',' opt_nls
 446         ;
 447
 448 %%
 449 ]])
 450
 451 # Pass plenty of options, to exercise plenty of code, even if we
 452 # don't actually check the output.  But SEGV is watching us, and
 453 # so might do dmalloc.
 454 AT_CHECK([[bison --verbose --defines input.y]])
 455
 456 AT_CLEANUP