# 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 #include #include ]$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