Experimental changes that prevent parser stack overflows by growing the

parser stack with heap memory when it reaches its limit.

FossilOrigin-Name: 3fd062905fc20507b7cfc97fa976ac5b57c5b68926bf9136bd5ea4265d2d6528

6 files changed, 112 insertions, 65 deletions

diff --git a/doc/lemon.html b/doc/lemon.html
index 66665f46f..4147d9b31 100644
--- a/doc/lemon.html
+++ b/doc/lemon.html
@@ -683,6 +683,7 @@ other than that, the order of directives in Lemon is arbitrary.</p>
 <li><tt><a href='#pifdef'>%endif</a></tt>
 <li><tt><a href='#extraarg'>%extra_argument</a></tt>
 <li><tt><a href='#pfallback'>%fallback</a></tt>
+<li><tt><a href='#reallc'>%free</a></tt>
 <li><tt><a href='#pifdef'>%if</a></tt>
 <li><tt><a href='#pifdef'>%ifdef</a></tt>
 <li><tt><a href='#pifdef'>%ifndef</a></tt>
@@ -693,6 +694,7 @@ other than that, the order of directives in Lemon is arbitrary.</p>
 <li><tt><a href='#parse_accept'>%parse_accept</a></tt>
 <li><tt><a href='#parse_failure'>%parse_failure</a></tt>
 <li><tt><a href='#pright'>%right</a></tt>
+<li><tt><a href='#reallc'>%realloc</a></tt>
 <li><tt><a href='#stack_overflow'>%stack_overflow</a></tt>
 <li><tt><a href='#stack_size'>%stack_size</a></tt>
 <li><tt><a href='#start_symbol'>%start_symbol</a></tt>
@@ -1200,6 +1202,21 @@ match any input token.</p>
 the wildcard token and some other token, the other token is always used.
 The wildcard token is only matched if there are no alternatives.</p>
 
+<a id='reallc'></a>
+<h4>4.4.26 The <tt>%realloc</tt> and <tt>%free</tt> directives</h4>
+
+<p>The <tt>%realloc</tt> and <tt>%free</tt> directives defines function
+that allocate and free heap memory.  The signatures of these functions
+should be the same as the realloc() and free() functions from the standard
+C library.
+
+<p>If both of these functions are defined
+then these functions are used to allocate and free
+memory for supplemental parser stack space, if the initial
+parse stack space is exceeded.  The initial parser stack size
+is specified by either <tt>%stack_size</tt> or the
+-DYYSTACKDEPTH compile-time flag.
+
 <a id='errors'></a>
 <h2>5.0 Error Processing</h2>
 
@@ -1224,6 +1241,7 @@ to begin parsing a new file.  This is what will happen at the very
 first syntax error, of course, if there are no instances of the
 "error" non-terminal in your grammar.</p>
 
+
 <a id='history'></a>
 <h2>6.0 History of Lemon</h2>
 
diff --git a/manifest b/manifest
index d546c7f2d..42fb3ce81 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C Add\sNEVER()\sto\sa\sbranch\sthat\sis\sno\slonger\sreachable.
-D 2024-01-24T21:08:57.555
+C Experimental\schanges\sthat\sprevent\sparser\sstack\soverflows\sby\sgrowing\sthe\nparser\sstack\swith\sheap\smemory\swhen\sit\sreaches\sits\slimit.
+D 2024-01-26T20:34:48.241
 F .fossil-settings/empty-dirs dbb81e8fc0401ac46a1491ab34a7f2c7c0452f2f06b54ebb845d024ca8283ef1
 F .fossil-settings/ignore-glob 35175cdfcf539b2318cb04a9901442804be81cd677d8b889fcc9149c21f239ea
 F LICENSE.md df5091916dbb40e6e9686186587125e1b2ff51f022cc334e886c19a0e9982724
@@ -40,7 +40,7 @@ F doc/F2FS.txt c1d4a0ae9711cfe0e1d8b019d154f1c29e0d3abfe820787ba1e9ed7691160fcd
 F doc/compile-for-windows.md 50b27d77be96195c66031a3181cb8684ed822327ea834e07f9c014213e5e3bcf
 F doc/json-enhancements.md e356fc834781f1f1aa22ee300027a270b2c960122468499bf347bb123ce1ea4f
 F doc/jsonb.md 5fab4b8613aa9153fbeb6259297bd4697988af8b3d23900deba588fa7841456b
-F doc/lemon.html 44a53a1d2b42d7751f7b2f478efb23c978e258d794bfd172442307a755b9fa44
+F doc/lemon.html 8b266ff711d2ec7f867c3dca37634963f48a630329908cc282beebfa8c708706
 F doc/pager-invariants.txt 27fed9a70ddad2088750c4a2b493b63853da2710
 F doc/testrunner.md 8d36ec692cf4994bb66d84a4645b9afa1ce9d47dc12cbf8d437c5a5fb6ddeedb
 F doc/trusted-schema.md 33625008620e879c7bcfbbfa079587612c434fa094d338b08242288d358c3e8a
@@ -727,7 +727,7 @@ F src/os_win.c 6ff43bac175bd9ed79e7c0f96840b139f2f51d01689a638fd05128becf94908a
 F src/os_win.h 7b073010f1451abe501be30d12f6bc599824944a
 F src/pager.c ff60e98138d2499082ac6230f01ac508aba545315debccfca2fd6042f5f10fcd
 F src/pager.h 4b1140d691860de0be1347474c51fee07d5420bd7f802d38cbab8ea4ab9f538a
-F src/parse.y 020d80386eb216ec9520549106353c517d2bbc89be28752ffdca649a9eaf56ec
+F src/parse.y 41926c507955f2c13b10bb344883874cde82ea3ed16cb3b7867a43298d040d79
 F src/pcache.c 040b165f30622a21b7a9a77c6f2e4877a32fb7f22d4c7f0d2a6fa6833a156a75
 F src/pcache.h 1497ce1b823cf00094bb0cf3bac37b345937e6f910890c626b16512316d3abf5
 F src/pcache1.c 602acb23c471bb8d557a6f0083cc2be641d6cafcafa19e481eba7ef4c9ca0f00
@@ -2072,8 +2072,8 @@ F tool/genfkey.test b6afd7b825d797a1e1274f519ab5695373552ecad5cd373530c63533638a
 F tool/getlock.c f4c39b651370156cae979501a7b156bdba50e7ce
 F tool/index_usage.c f62a0c701b2c7ff2f3e21d206f093c123f222dbf07136a10ffd1ca15a5c706c5
 F tool/kvtest-speed.sh 4761a9c4b3530907562314d7757995787f7aef8f
-F tool/lemon.c 19e368bc8e97ff4071115119a7911ca3b0c56eba7926d8ada8b4a86fcc69a176
-F tool/lempar.c 57478ea48420da05faa873c6d1616321caa5464644588c97fbe8e0ea04450748
+F tool/lemon.c 7e5c3c27062c94a40b73a980b8045a4201cb3335165b72ae476040dc513aa533
+F tool/lempar.c fa7ab4dd5bc069ffa276cbd85bea767e6472f4163106b94edd5ad01dd4babdc8
 F tool/libvers.c caafc3b689638a1d88d44bc5f526c2278760d9b9
 F tool/loadfts.c c3c64e4d5e90e8ba41159232c2189dba4be7b862
 F tool/logest.c c34e5944318415de513d29a6098df247a9618c96d83c38d4abd88641fe46e669
@@ -2161,8 +2161,11 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93
 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc
 F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e
 F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0
-P 996cfdf9b5f70408faeaa68ba2ea9494e419be8f2c59d89ab702419056e3569c
-R cc29f59aa57a1c6bea20c14e055ec6a4
+P 9411337a7b3237366768fc708396da53d67a7a17b6cdc5c6f8932c5ab32217a9
+R de3584eaf5d75ac532effc39455b51de
+T *branch * growable-parser-stack
+T *sym-growable-parser-stack *
+T -sym-trunk *
 U drh
-Z 22d3dca63255cbf92f3e39d6096754f7
+Z 64ba7e2f532c5b55e706d3959cc36418
 # Remove this line to create a well-formed Fossil manifest.
diff --git a/manifest.uuid b/manifest.uuid
index 48c5e7a6d..acfd13cd3 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-9411337a7b3237366768fc708396da53d67a7a17b6cdc5c6f8932c5ab32217a9
\ No newline at end of file
+3fd062905fc20507b7cfc97fa976ac5b57c5b68926bf9136bd5ea4265d2d6528
\ No newline at end of file
diff --git a/src/parse.y b/src/parse.y
index 19491192e..0e41f54cf 100644
--- a/src/parse.y
+++ b/src/parse.y
@@ -21,6 +21,10 @@
 */
 }
 
+// Function used to enlarge the parser stack, if needed
+%realloc sqlite3_realloc64
+%free    sqlite3_free
+
 // All token codes are small integers with #defines that begin with "TK_"
 %token_prefix TK_
 
diff --git a/tool/lemon.c b/tool/lemon.c
index 7804837a0..c578b44ba 100644
--- a/tool/lemon.c
+++ b/tool/lemon.c
@@ -418,6 +418,8 @@ struct lemon {
   char *filename;          /* Name of the input file */
   char *outname;           /* Name of the current output file */
   char *tokenprefix;       /* A prefix added to token names in the .h file */
+  char *reallocFunc;       /* Function to use to allocate stack space */
+  char *freeFunc;          /* Function to use to free stack space */
   int nconflict;           /* Number of parsing conflicts */
   int nactiontab;          /* Number of entries in the yy_action[] table */
   int nlookaheadtab;       /* Number of entries in yy_lookahead[] */
@@ -2531,6 +2533,12 @@ static void parseonetoken(struct pstate *psp)
         }else if( strcmp(x,"default_type")==0 ){
           psp->declargslot = &(psp->gp->vartype);
           psp->insertLineMacro = 0;
+        }else if( strcmp(x,"realloc")==0 ){
+          psp->declargslot = &(psp->gp->reallocFunc);
+          psp->insertLineMacro = 0;
+        }else if( strcmp(x,"free")==0 ){
+          psp->declargslot = &(psp->gp->freeFunc);
+          psp->insertLineMacro = 0;
         }else if( strcmp(x,"stack_size")==0 ){
           psp->declargslot = &(psp->gp->stacksize);
           psp->insertLineMacro = 0;
@@ -4501,6 +4509,21 @@ void ReportTable(
     fprintf(out,"#define %sARG_FETCH\n",name); lineno++;
     fprintf(out,"#define %sARG_STORE\n",name); lineno++;
   }
+  if( lemp->reallocFunc ){
+    fprintf(out,"#define YYREALLOC %s\n", lemp->reallocFunc); lineno++;
+  }else{
+    fprintf(out,"#define YYREALLOC realloc\n"); lineno++;
+  }
+  if( lemp->freeFunc ){
+    fprintf(out,"#define YYFREE %s\n", lemp->freeFunc); lineno++;
+  }else{
+    fprintf(out,"#define YYFREE free\n"); lineno++;
+  }
+  if( lemp->reallocFunc && lemp->freeFunc ){
+    fprintf(out,"#define YYDYNSTACK 1\n"); lineno++;
+  }else{
+    fprintf(out,"#define YYDYNSTACK 0\n"); lineno++;
+  }
   if( lemp->ctx && lemp->ctx[0] ){
     i = lemonStrlen(lemp->ctx);
     while( i>=1 && ISSPACE(lemp->ctx[i-1]) ) i--;
diff --git a/tool/lempar.c b/tool/lempar.c
index 8cc57897d..d8e64c40d 100644
--- a/tool/lempar.c
+++ b/tool/lempar.c
@@ -67,6 +67,9 @@
 **    ParseARG_STORE     Code to store %extra_argument into yypParser
 **    ParseARG_FETCH     Code to extract %extra_argument from yypParser
 **    ParseCTX_*         As ParseARG_ except for %extra_context
+**    YYREALLOC          Name of the realloc() function to use
+**    YYFREE             Name of the free() function to use
+**    YYDYNSTACK         True if stack space should be extended on heap
 **    YYERRORSYMBOL      is the code number of the error symbol.  If not
 **                       defined, then do no error processing.
 **    YYNSTATE           the combined number of states.
@@ -101,6 +104,22 @@
 # define yytestcase(X)
 #endif
 
+/* Macro to determine if stack space has the ability to grow using
+** heap memory.
+*/
+#if YYSTACKDEPTH<=0 || YYDYNSTACK
+# define YYGROWABLESTACK 1
+#else
+# define YYGROWABLESTACK 0
+#endif
+
+/* Guarantee a minimum number of initial stack slots.
+*/
+#if YYSTACKDEPTH<=0
+# undef YYSTACKDEPTH
+# define YYSTACKDEPTH 2  /* Need a minimum stack size */
+#endif
+
 
 /* Next are the tables used to determine what action to take based on the
 ** current state and lookahead token.  These tables are used to implement
@@ -212,14 +231,9 @@ struct yyParser {
 #endif
   ParseARG_SDECL                /* A place to hold %extra_argument */
   ParseCTX_SDECL                /* A place to hold %extra_context */
-#if YYSTACKDEPTH<=0
-  int yystksz;                  /* Current side of the stack */
-  yyStackEntry *yystack;        /* The parser's stack */
-  yyStackEntry yystk0;          /* First stack entry */
-#else
-  yyStackEntry yystack[YYSTACKDEPTH];  /* The parser's stack */
-  yyStackEntry *yystackEnd;            /* Last entry in the stack */
-#endif
+  yyStackEntry *yystackEnd;           /* Last entry in the stack */
+  yyStackEntry *yystack;              /* The parser stack */
+  yyStackEntry yystk0[YYSTACKDEPTH];  /* Initial stack space */
 };
 typedef struct yyParser yyParser;
 
@@ -273,37 +287,45 @@ static const char *const yyRuleName[] = {
 #endif /* NDEBUG */
 
 
-#if YYSTACKDEPTH<=0
+#if YYGROWABLESTACK
 /*
 ** Try to increase the size of the parser stack.  Return the number
 ** of errors.  Return 0 on success.
 */
 static int yyGrowStack(yyParser *p){
+  int oldSize = 1 + (int)(p->yystackEnd - p->yystack)/sizeof(p->yystack[0]);
   int newSize;
   int idx;
   yyStackEntry *pNew;
 
-  newSize = p->yystksz*2 + 100;
+  newSize = oldSize*2 + 100;
   idx = p->yytos ? (int)(p->yytos - p->yystack) : 0;
-  if( p->yystack==&p->yystk0 ){
-    pNew = malloc(newSize*sizeof(pNew[0]));
-    if( pNew ) pNew[0] = p->yystk0;
+  if( p->yystack==p->yystk0 ){
+    pNew = YYREALLOC(0, newSize*sizeof(pNew[0]));
+    if( pNew==0 ) return 1;
+    memcpy(pNew, p->yystk0, sizeof(p->yystk0));
   }else{
-    pNew = realloc(p->yystack, newSize*sizeof(pNew[0]));
+    pNew = YYREALLOC(p->yystack, newSize*sizeof(pNew[0]));
+    if( pNew==0 ) return 1;
   }
-  if( pNew ){
-    p->yystack = pNew;
-    p->yytos = &p->yystack[idx];
+  p->yystack = pNew;
+  p->yytos = &p->yystack[idx];
 #ifndef NDEBUG
-    if( yyTraceFILE ){
-      fprintf(yyTraceFILE,"%sStack grows from %d to %d entries.\n",
-              yyTracePrompt, p->yystksz, newSize);
-    }
-#endif
-    p->yystksz = newSize;
+  if( yyTraceFILE ){
+    fprintf(yyTraceFILE,"%sStack grows from %d to %d entries.\n",
+            yyTracePrompt, oldSize, newSize);
   }
-  return pNew==0; 
+#endif
+  p->yystackEnd = &p->yystack[newSize-1];
+  return 0;
 }
+#endif /* YYGROWABLESTACK */
+
+#if !YYGROWABLESTACK
+/* For builds that do no have a growable stack, yyGrowStack always
+** returns an error.
+*/
+# define yyGrowStack(X) 1
 #endif
 
 /* Datatype of the argument to the memory allocated passed as the
@@ -323,24 +345,14 @@ void ParseInit(void *yypRawParser ParseCTX_PDECL){
 #ifdef YYTRACKMAXSTACKDEPTH
   yypParser->yyhwm = 0;
 #endif
-#if YYSTACKDEPTH<=0
-  yypParser->yytos = NULL;
-  yypParser->yystack = NULL;
-  yypParser->yystksz = 0;
-  if( yyGrowStack(yypParser) ){
-    yypParser->yystack = &yypParser->yystk0;
-    yypParser->yystksz = 1;
-  }
-#endif
+  yypParser->yystack = yypParser->yystk0;
+  yypParser->yystackEnd = &yypParser->yystack[YYSTACKDEPTH-1];
 #ifndef YYNOERRORRECOVERY
   yypParser->yyerrcnt = -1;
 #endif
   yypParser->yytos = yypParser->yystack;
   yypParser->yystack[0].stateno = 0;
   yypParser->yystack[0].major = 0;
-#if YYSTACKDEPTH>0
-  yypParser->yystackEnd = &yypParser->yystack[YYSTACKDEPTH-1];
-#endif
 }
 
 #ifndef Parse_ENGINEALWAYSONSTACK
@@ -427,8 +439,8 @@ static void yy_pop_parser_stack(yyParser *pParser){
 void ParseFinalize(void *p){
   yyParser *pParser = (yyParser*)p;
   while( pParser->yytos>pParser->yystack ) yy_pop_parser_stack(pParser);
-#if YYSTACKDEPTH<=0
-  if( pParser->yystack!=&pParser->yystk0 ) free(pParser->yystack);
+#if YYGROWABLESTACK
+  if( pParser->yystack!=pParser->yystk0 ) YYFREE(pParser->yystack);
 #endif
 }
 
@@ -654,25 +666,19 @@ static void yy_shift(
     assert( yypParser->yyhwm == (int)(yypParser->yytos - yypParser->yystack) );
   }
 #endif
-#if YYSTACKDEPTH>0 
-  if( yypParser->yytos>yypParser->yystackEnd ){
-    yypParser->yytos--;
-    yyStackOverflow(yypParser);
-    return;
-  }
-#else
-  if( yypParser->yytos>=&yypParser->yystack[yypParser->yystksz] ){
+  yytos = yypParser->yytos;
+  if( yytos>yypParser->yystackEnd ){
     if( yyGrowStack(yypParser) ){
       yypParser->yytos--;
       yyStackOverflow(yypParser);
       return;
     }
+    yytos = yypParser->yytos;
+    assert( yytos <= yypParser->yystackEnd );
   }
-#endif
   if( yyNewState > YY_MAX_SHIFT ){
     yyNewState += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
   }
-  yytos = yypParser->yytos;
   yytos->stateno = yyNewState;
   yytos->major = yyMajor;
   yytos->minor.yy0 = yyMinor;
@@ -911,19 +917,12 @@ void Parse(
                   (int)(yypParser->yytos - yypParser->yystack));
         }
 #endif
-#if YYSTACKDEPTH>0 
         if( yypParser->yytos>=yypParser->yystackEnd ){
-          yyStackOverflow(yypParser);
-          break;
-        }
-#else
-        if( yypParser->yytos>=&yypParser->yystack[yypParser->yystksz-1] ){
           if( yyGrowStack(yypParser) ){
             yyStackOverflow(yypParser);
             break;
           }
         }
-#endif
       }
       yyact = yy_reduce(yypParser,yyruleno,yymajor,yyminor ParseCTX_PARAM);
     }else if( yyact <= YY_MAX_SHIFTREDUCE ){