libcdecl: Fix parsing of very long declarator lists.

The way the toplevel declaration parser is currently arranged requires
shifting every declarator symbol before any part of the full declarator
list is reduced.  Thus, very long declarations (with about 5000 or more
full declarators) can lead to a parse error since the symbol stack is
exhausted (even if there would otherwise be enough memory to allocate
this many declarator items).

Technically this kind of failure is permitted by the C language, as
implementations are not required to support declarations of this size.
However, it is better to avoid arbitrary limits like this and it is not
a big problem to do so.

Simply collecting the declarators in reverse order allows for the list
elements to be reduced as they are encountered, which avoids excessive
use of the symbol stack.  However in this case the order matters, so
the final list must be reversed before it is returned from the parser.

Add a new test case to cover this behaviour.

diff --git a/src/parse.y b/src/parse.y
index 3a17b998babf5cabc1bc5cfb6e76278304da74f8..0a12f3f9e7aa6cdeacaba331afd5785bc7d9da35 100644 (file)
--- a/src/parse.y
+++ b/src/parse.y
@@ -226,11 +226,29 @@ static struct cdecl_declspec *join_specs3(struct cdecl_declspec *a,
        return b;
 }
 
+/*
+ * Reverse the order of a "struct cdecl" list, and return the new first
+ * element of the list (i.e., the last element of the original list).
+ */
+static struct cdecl *reverse_decls(struct cdecl *decl)
+{
+       struct cdecl *prev, *next;
+
+       for (prev = NULL; decl; decl = next) {
+               next = decl->next;
+               decl->next = prev;
+               prev = decl;
+       }
+
+       return prev;
+}
+
 /*
  * Alter an abstract declarator (type name) to declare an identifier instead,
  * used by the English parser rules to reduce "identifier as type" sequences.
  */
-static struct cdecl *insert_identifier(struct cdecl *decl, struct parse_item *ident)
+static struct cdecl *
+insert_identifier(struct cdecl *decl, struct parse_item *ident)
 {
        struct cdecl_declarator *d, **p = &decl->declarators;
 
@@ -343,7 +361,7 @@ cdecl: english | declaration
 
 semi: | T_SEMICOLON
 declaration: declspecs declarators semi {
-       $$ = $2;
+       $$ = reverse_decls($2);
        $$->specifiers = $1;
 };
 
@@ -382,9 +400,9 @@ qualifiers: { $$ = NULL; } | qualifiers qualifier {
        $$->next = $1;
 }
 
-declarators: declarator_wrap | declarator_wrap T_COMMA declarators {
-       $$ = $1;
-       $$->next = $3;
+declarators: declarator_wrap | declarators T_COMMA declarator_wrap {
+       $$ = $3;
+       $$->next = $1;
 }
 
 declarator_wrap: declarator {

diff --git a/tests/stress.at b/tests/stress.at
index 40e8812e1716a9b64c4f439cba78faac7ce8e800..605a69ac27b6c3ebe2f047130df5476fa2c90003 100644 (file)
--- a/tests/stress.at
+++ b/tests/stress.at
@@ -125,3 +125,44 @@ inline int f()
 ]])
 
 AT_CLEANUP
+
+# Check that we can parse declarations with more than 10000 declarators.
+AT_SETUP([Excessive declarators])
+
+AT_DATA([check.awk],
+[[# We don't need any field splitting, so choose a character that does not
+# appear in C code to avoid tripping over 199-field limit in HP-UX 11 awk.
+BEGIN { FS = "@"; runstart = 0; }
+END { finish_run(NR); }
+
+$0 != lastline {
+  finish_run(NR-1);
+  lastline = $0;
+  runstart = NR;
+  print;
+}
+
+function finish_run(nr) {
+  count = nr - runstart;
+  if (count > 0)
+    print "[repeated " count " more times]";
+}
+]])
+
+a="a"
+for i in 1 2 3 4 5 6 7 8 9 10 11 12 13 14; do
+  AS_VAR_APPEND([a], [",$a"])
+done
+
+cat >test.dat <<EOF
+explain int $a
+EOF
+
+AT_CHECK([cdecl99 -f test.dat >test.out; status=$?;
+$AWK -f check.awk test.out
+exit $status], [0],
+[[declare a as int
+[repeated 16383 more times]
+]])
+
+AT_CLEANUP