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