* src/bison.simple (YYSIZE_T, YYSTACK_ALLOC, YYSTACK_FREE):

[bison.git] / tests / torture.at

# Torturing Bison.                                    -*- Autotest -*-
# Copyright 2001 Free Software Foundation, Inc.

# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2, or (at your option)
# any later version.

# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.

# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
# 02111-1307, USA.

AT_BANNER([[Torture Tests.]])


# AT_DATA_STACK_TORTURE(C-PROLOGUE)
# ---------------------------------
# A parser specialized in torturing the stack size.
m4_define([AT_DATA_STACK_TORTURE],
[# A grammar of parens growing the stack thanks to right recursion.
# exp:
AT_DATA([input.y],
[[%{
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
]$1[
  static int yylex (void);
  static void yyerror (const char *msg);
#define YYPRINT(File, Type, Value)                   \
  fprintf (File, " (%d, stack size = %d, max = %d)", \
           Value, yyssp - yyss + 1, yystacksize);
%}
%error-verbose
%debug
%token WAIT_FOR_EOF
%%
exp: WAIT_FOR_EOF exp | ;
%%
static void
yyerror (const char *msg)
{
  fprintf (stderr, "%s\n", msg);
  exit (1);
}

/* There are YYLVAL_MAX of WAIT_FOR_EOFs. */
unsigned int yylval_max;

static int
yylex (void)
{
  if (yylval--)
    return WAIT_FOR_EOF;
  else
    return EOF;
}

int
main (int argc, const char **argv)
{
  assert (argc == 2);
  yylval = atoi (argv[1]);
  yydebug = 1;
  return yyparse ();
}
]])
AT_CHECK([bison input.y -o input.c])
AT_CHECK([$CC $CFLAGS $CPPFLAGS input.c -o input], 0, [], [ignore])
])


## -------------------------------------- ##
## Exploding the Stack Size with Alloca.  ##
## -------------------------------------- ##

AT_SETUP([Exploding the Stack Size with Alloca])

AT_DATA_STACK_TORTURE

# Below the limit of 200.
AT_CHECK([input 20], 0, [], [ignore])
# Two enlargements: 2 * 2 * 200.
AT_CHECK([input 900], 0, [], [ignore])
# Fails: beyond the limit of 10,000 (which we don't reach anyway since we
# multiply by two starting at 200 => 5120 is the last possible).
AT_CHECK([input 10000], 1, [], [ignore])

AT_CLEANUP




## -------------------------------------- ##
## Exploding the Stack Size with Malloc.  ##
## -------------------------------------- ##

AT_SETUP([Exploding the Stack Size with Malloc])

AT_DATA_STACK_TORTURE([[#define YYSTACK_USE_ALLOCA 0]])

# Below the limit of 200.
AT_CHECK([input 20], 0, [], [ignore])
# Two enlargements: 2 * 2 * 200.
AT_CHECK([input 900], 0, [], [ignore])
# Fails: beyond the limit of 10,000 (which we don't reach anyway since we
# multiply by two starting at 200 => 5120 is the possible).
AT_CHECK([input 10000], 1, [], [ignore])

AT_CLEANUP


## ----------------- ##
## GNU AWK Grammar.  ##
## ----------------- ##

AT_SETUP([GNU AWK Grammar])

# We have been careful to strip all the actions excepts the
# mid-rule actions.  We rely on %expect to check that there are
# indeed 65 SR conflicts.
#
# Bison was once wrong, due to an incorrect computation of nullable.
# It reported 485 SR conflicts!

AT_DATA([[input.y]],
[[%expect 65

%token FUNC_CALL NAME REGEXP
%token ERROR
%token YNUMBER YSTRING
%token RELOP APPEND_OP
%token ASSIGNOP MATCHOP NEWLINE CONCAT_OP
%token LEX_BEGIN LEX_END LEX_IF LEX_ELSE LEX_RETURN LEX_DELETE
%token LEX_WHILE LEX_DO LEX_FOR LEX_BREAK LEX_CONTINUE
%token LEX_PRINT LEX_PRINTF LEX_NEXT LEX_EXIT LEX_FUNCTION
%token LEX_GETLINE LEX_NEXTFILE
%token LEX_IN
%token LEX_AND LEX_OR INCREMENT DECREMENT
%token LEX_BUILTIN LEX_LENGTH

/* Lowest to highest */
%right ASSIGNOP
%right '?' ':'
%left LEX_OR
%left LEX_AND
%left LEX_GETLINE
%nonassoc LEX_IN
%left FUNC_CALL LEX_BUILTIN LEX_LENGTH
%nonassoc ','
%nonassoc MATCHOP
%nonassoc RELOP '<' '>' '|' APPEND_OP TWOWAYIO
%left CONCAT_OP
%left YSTRING YNUMBER
%left '+' '-'
%left '*' '/' '%'
%right '!' UNARY
%right '^'
%left INCREMENT DECREMENT
%left '$'
%left '(' ')'
%%

start
	: opt_nls program opt_nls
	;

program
	: rule
	| program rule
	| error
	| program error
	| /* empty */
	;

rule
	: LEX_BEGIN {} action
	| LEX_END {}   action
	| LEX_BEGIN statement_term
	| LEX_END statement_term
	| pattern action
	| action
	| pattern statement_term
	| function_prologue function_body
	;

func_name
	: NAME
	| FUNC_CALL
	| lex_builtin
	;

lex_builtin
	: LEX_BUILTIN
	| LEX_LENGTH
	;

function_prologue
	: LEX_FUNCTION {} func_name '(' opt_param_list r_paren opt_nls
	;

function_body
	: l_brace statements r_brace opt_semi opt_nls
	| l_brace r_brace opt_semi opt_nls
	;


pattern
	: exp
	| exp ',' exp
	;

regexp
	/*
	 * In this rule, want_regexp tells yylex that the next thing
	 * is a regexp so it should read up to the closing slash.
	 */
	: '/' {} REGEXP '/'
	;

action
	: l_brace statements r_brace opt_semi opt_nls
	| l_brace r_brace opt_semi opt_nls
	;

statements
	: statement
	| statements statement
	| error
	| statements error
	;

statement_term
	: nls
	| semi opt_nls
	;

statement
	: semi opt_nls
	| l_brace r_brace
	| l_brace statements r_brace
	| if_statement
	| LEX_WHILE '(' exp r_paren opt_nls statement
	| LEX_DO opt_nls statement LEX_WHILE '(' exp r_paren opt_nls
	| LEX_FOR '(' NAME LEX_IN NAME r_paren opt_nls statement
	| LEX_FOR '(' opt_exp semi opt_nls exp semi opt_nls opt_exp r_paren opt_nls statement
	| LEX_FOR '(' opt_exp semi opt_nls semi opt_nls opt_exp r_paren opt_nls statement
	| LEX_BREAK statement_term
	| LEX_CONTINUE statement_term
	| print '(' expression_list r_paren output_redir statement_term
	| print opt_rexpression_list output_redir statement_term
	| LEX_NEXT statement_term
	| LEX_NEXTFILE statement_term
	| LEX_EXIT opt_exp statement_term
	| LEX_RETURN {} opt_exp statement_term
	| LEX_DELETE NAME '[' expression_list ']' statement_term
	| LEX_DELETE NAME  statement_term
	| exp statement_term
	;

print
	: LEX_PRINT
	| LEX_PRINTF
	;

if_statement
	: LEX_IF '(' exp r_paren opt_nls statement
	| LEX_IF '(' exp r_paren opt_nls statement
	     LEX_ELSE opt_nls statement
	;

nls
	: NEWLINE
	| nls NEWLINE
	;

opt_nls
	: /* empty */
	| nls
	;

input_redir
	: /* empty */
	| '<' simp_exp
	;

output_redir
	: /* empty */
	| '>' exp
	| APPEND_OP exp
	| '|' exp
	| TWOWAYIO exp
	;

opt_param_list
	: /* empty */
	| param_list
	;

param_list
	: NAME
	| param_list comma NAME
	| error
	| param_list error
	| param_list comma error
	;

/* optional expression, as in for loop */
opt_exp
	: /* empty */
	| exp
	;

opt_rexpression_list
	: /* empty */
	| rexpression_list
	;

rexpression_list
	: rexp
	| rexpression_list comma rexp
	| error
	| rexpression_list error
	| rexpression_list error rexp
	| rexpression_list comma error
	;

opt_expression_list
	: /* empty */
	| expression_list
	;

expression_list
	: exp
	| expression_list comma exp
	| error
	| expression_list error
	| expression_list error exp
	| expression_list comma error
	;

/* Expressions, not including the comma operator.  */
exp	: variable ASSIGNOP {} exp
	| '(' expression_list r_paren LEX_IN NAME
	| exp '|' LEX_GETLINE opt_variable
	| exp TWOWAYIO LEX_GETLINE opt_variable
	| LEX_GETLINE opt_variable input_redir
	| exp LEX_AND exp
	| exp LEX_OR exp
	| exp MATCHOP exp
	| regexp
	| '!' regexp %prec UNARY
	| exp LEX_IN NAME
	| exp RELOP exp
	| exp '<' exp
	| exp '>' exp
	| exp '?' exp ':' exp
	| simp_exp
	| exp simp_exp %prec CONCAT_OP
	;

rexp
	: variable ASSIGNOP {} rexp
	| rexp LEX_AND rexp
	| rexp LEX_OR rexp
	| LEX_GETLINE opt_variable input_redir
	| regexp
	| '!' regexp %prec UNARY
	| rexp MATCHOP rexp
	| rexp LEX_IN NAME
	| rexp RELOP rexp
	| rexp '?' rexp ':' rexp
	| simp_exp
	| rexp simp_exp %prec CONCAT_OP
	;

simp_exp
	: non_post_simp_exp
	/* Binary operators in order of decreasing precedence.  */
	| simp_exp '^' simp_exp
	| simp_exp '*' simp_exp
	| simp_exp '/' simp_exp
	| simp_exp '%' simp_exp
	| simp_exp '+' simp_exp
	| simp_exp '-' simp_exp
	| variable INCREMENT
	| variable DECREMENT
	;

non_post_simp_exp
	: '!' simp_exp %prec UNARY
	| '(' exp r_paren
	| LEX_BUILTIN
	  '(' opt_expression_list r_paren
	| LEX_LENGTH '(' opt_expression_list r_paren
	| LEX_LENGTH
	| FUNC_CALL '(' opt_expression_list r_paren
	| variable
	| INCREMENT variable
	| DECREMENT variable
	| YNUMBER
	| YSTRING
	| '-' simp_exp    %prec UNARY
	| '+' simp_exp    %prec UNARY
	;

opt_variable
	: /* empty */
	| variable
	;

variable
	: NAME
	| NAME '[' expression_list ']'
	| '$' non_post_simp_exp
	;

l_brace
	: '{' opt_nls
	;

r_brace
	: '}' opt_nls
	;

r_paren
	: ')'
	;

opt_semi
	: /* empty */
	| semi
	;

semi
	: ';'
	;

comma	: ',' opt_nls
	;

%%
]])

# Pass plenty of options, to exercise plenty of code, even if we
# don't actually check the output.  But SEGV is watching us, and
# so might do dmalloc.
AT_CHECK([[bison --verbose --defines input.y]])

AT_CLEANUP