Re: [bug-gnulib] Re: getdate don't need alloca

[Paul Eggert]

Stepan Kasal <address@hidden> writes:

> I think bison-generated code should behave more transparently and propose
> the patch attached to this mail.

On further thought, it'd be nicer to change Bison parsers to never use
alloca unless the user explicitly asks for it.  alloca is a pain to
get right, and it's safer to avoid it unless it's explicitly asked for.

Also, Bison should let the user set YYMAXDEPTH to a value that is not
a preprocessor constant, and the documentation should be clearer about
the user's responsibility with respect to arithmetic and stack
overflow.

I installed this change to Bison.

2004-12-22  Paul Eggert  <address@hidden>

        * NEWS: Bison-generated parsers no longer default to using the
        alloca function (when available) to extend the parser stack, due
        to widespread problems in unchecked stack-overflow detection.
        * data/glr.c (YYMAXDEPTH): Remove undef when zero.  It's the user's
        responsibility to set it to a positive value.  This lets the user
        specify a value that is not a preprocessor constant.
        * data/yacc.c (YYMAXDEPTH): Likewise.
        (YYSTACK_ALLOC): Define only if YYSTACK_USE_ALLOCA is nonzero.
        * doc/bison.texinfo (Stack Overflow): YYMAXDEPTH no longer needs
        to be a compile-time constant.  However, explain the constraints on it.
        Also, explain the constraints on YYINITDEPTH.
        (Table of Symbols): Explain that alloca is no longer the default.
        Explain the user's responsibility if they define YYSTACK_USE_ALLOCA
        to 1.

Index: NEWS
===================================================================
RCS file: /cvsroot/bison/bison/NEWS,v
retrieving revision 1.108
diff -p -u -r1.108 NEWS
--- NEWS        17 Dec 2004 15:24:32 -0000      1.108
+++ NEWS        22 Dec 2004 21:11:26 -0000
@@ -3,6 +3,12 @@ Bison News
 
 Changes in version 1.875f:
 
+* Bison-generated parsers no longer default to using the alloca function
+  (when available) to extend the parser stack, due to widespread
+  problems in unchecked stack-overflow detection.  You can "#define
+  YYSTACK_USE_ALLOCA 1" to use alloca anyway, but please read the
+  manual to determine safe values for YYMAXDEPTH in that case.
+
 Changes in version 1.875e, 2004-12-10:
 
 * New directive: %initial-action.
Index: data/glr.c
===================================================================
RCS file: /cvsroot/bison/bison/data/glr.c,v
retrieving revision 1.88
diff -p -u -r1.88 glr.c
--- data/glr.c  20 Dec 2004 03:43:48 -0000      1.88
+++ data/glr.c  22 Dec 2004 21:11:26 -0000
@@ -536,10 +536,6 @@ int yydebug;
    SIZE_MAX < YYMAXDEPTH * sizeof (GLRStackItem)
    evaluated with infinite-precision integer arithmetic.  */
 
-#if YYMAXDEPTH == 0
-# undef YYMAXDEPTH
-#endif
-
 #ifndef YYMAXDEPTH
 # define YYMAXDEPTH ]b4_stack_depth_max[
 #endif
Index: data/yacc.c
===================================================================
RCS file: /cvsroot/bison/bison/data/yacc.c,v
retrieving revision 1.78
diff -p -u -r1.78 yacc.c
--- data/yacc.c 20 Dec 2004 03:43:35 -0000      1.78
+++ data/yacc.c 22 Dec 2004 21:11:26 -0000
@@ -226,14 +226,10 @@ b4_syncline(address@hidden@], address@hidden@])[
 
 # ifdef YYSTACK_USE_ALLOCA
 #  if YYSTACK_USE_ALLOCA
-#   define YYSTACK_ALLOC alloca
-#  endif
-# else
-#  if defined (alloca) || defined (_ALLOCA_H)
-#   define YYSTACK_ALLOC alloca
-#  else
 #   ifdef __GNUC__
 #    define YYSTACK_ALLOC __builtin_alloca
+#   else
+#    define YYSTACK_ALLOC alloca
 #   endif
 #  endif
 # endif
@@ -648,10 +644,6 @@ int yydebug;
    SIZE_MAX < YYSTACK_BYTES (YYMAXDEPTH)
    evaluated with infinite-precision integer arithmetic.  */
 
-#if defined (YYMAXDEPTH) && YYMAXDEPTH == 0
-# undef YYMAXDEPTH
-#endif
-
 #ifndef YYMAXDEPTH
 # define YYMAXDEPTH ]b4_stack_depth_max[
 #endif
Index: doc/bison.texinfo
===================================================================
RCS file: /cvsroot/bison/bison/doc/bison.texinfo,v
retrieving revision 1.136
diff -p -u -r1.136 bison.texinfo
--- doc/bison.texinfo   22 Dec 2004 18:26:37 -0000      1.136
+++ doc/bison.texinfo   22 Dec 2004 21:11:26 -0000
@@ -5574,7 +5574,6 @@ By defining the macro @code{YYMAXDEPTH},
 parser stack can become before a stack overflow occurs.  Define the
 macro with a value that is an integer.  This value is the maximum number
 of tokens that can be shifted (and not reduced) before overflow.
-It must be a constant expression whose value is known at compile time.
 
 The stack space allowed is not necessarily allocated.  If you specify a
 large value for @code{YYMAXDEPTH}, the parser actually allocates a small
@@ -5583,14 +5582,26 @@ increasing allocation happens automatica
 you do not need to make @code{YYMAXDEPTH} painfully small merely to save
 space for ordinary inputs that do not need much stack.
 
+However, do not allow @code{YYMAXDEPTH} to be a value so large that
+arithmetic overflow could occur when calculating the size of the stack
+space.  Also, do not allow @code{YYMAXDEPTH} to be less than
address@hidden
+
 @cindex default stack limit
 The default value of @code{YYMAXDEPTH}, if you do not define it, is
 10000.
 
 @vindex YYINITDEPTH
 You can control how much stack is allocated initially by defining the
-macro @code{YYINITDEPTH}.  This value too must be a compile-time
-constant integer.  The default is 200.
+macro @code{YYINITDEPTH} to a positive integer.  For the C
address@hidden(1) parser, this value must be a compile-time constant
+unless you are assuming C99 or some other target language or compiler
+that allows variable-length arrays.  The default is 200.
+
+Do not allow @code{YYINITDEPTH} to be a value so large that arithmetic
+overflow would occur when calculating the size of the stack space.
+Also, do not allow @code{YYINITDEPTH} to be greater than
address@hidden
 
 @c FIXME: C++ output.
 Because of semantical differences between C and C++, the
@@ -7306,10 +7317,23 @@ syntax error.  @xref{Action Features, ,S
 @end deffn
 
 @deffn {Macro} YYSTACK_USE_ALLOCA
-Macro used to control the use of @code{alloca}.  If defined to @samp{0},
-the parser will not use @code{alloca} but @code{malloc} when trying to
-grow its internal stacks.  Do @emph{not} define @code{YYSTACK_USE_ALLOCA}
-to anything else.
+Macro used to control the use of @code{alloca} when the C
address@hidden(1) parser needs to extend its stacks.  If defined to 0,
+the parser will use @code{malloc} to extend its stacks.  If defined to
+1, the parser will use @code{alloca}.  Values other than 0 and 1 are
+reserved for future Bison extensions.  If not defined,
address@hidden defaults to 0.
+
+If you define @code{YYSTACK_USE_ALLOCA} to 1, it is your
+responsibility to make sure that @code{alloca} is visible, e.g., by
+using @acronym{GCC} or by including @code{<stdlib.h>}.  Furthermore,
+in the all-too-common case where your code may run on a host with a
+limited stack and with unreliable stack-overflow checking, you should
+set @code{YYMAXDEPTH} to a value that cannot possibly result in
+unchecked stack overflow on any of your target hosts when
address@hidden is called.  You can inspect the code that Bison
+generates in order to determine the proper numeric values.  This will
+require some expertise in low-level implementation details.
 @end deffn
 
 @deffn {Type} YYSTYPE