Reorganize some of the code that detects expression trees with a depth greater than EXPR_MAX_DEPTH so that they are detected earlier. This further reduces the opportunities for stack overflow. (CVS 5189)

FossilOrigin-Name: 16d4c53a8e4d3cfc1abac3b8bb44d8bfd9471e32

3 files changed, 114 insertions, 88 deletions

diff --git a/src/expr.c b/src/expr.c
index 5813e2d2c..298dbac0c 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -12,7 +12,7 @@
 ** This file contains routines used for analyzing expressions and
 ** for generating VDBE code that evaluates expressions in SQLite.
 **
-** $Id: expr.c,v 1.372 2008/05/28 13:49:36 drh Exp $
+** $Id: expr.c,v 1.373 2008/06/05 16:47:39 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 #include <ctype.h>
@@ -253,6 +253,101 @@ static int codeCompare(
   return addr;
 }
 
+#if SQLITE_MAX_EXPR_DEPTH>0
+/*
+** Check that argument nHeight is less than or equal to the maximum
+** expression depth allowed. If it is not, leave an error message in
+** pParse.
+*/
+static int checkExprHeight(Parse *pParse, int nHeight){
+  int rc = SQLITE_OK;
+  int mxHeight = pParse->db->aLimit[SQLITE_LIMIT_EXPR_DEPTH];
+  if( nHeight>mxHeight ){
+    sqlite3ErrorMsg(pParse, 
+       "Expression tree is too large (maximum depth %d)", mxHeight
+    );
+    rc = SQLITE_ERROR;
+  }
+  return rc;
+}
+
+/* The following three functions, heightOfExpr(), heightOfExprList()
+** and heightOfSelect(), are used to determine the maximum height
+** of any expression tree referenced by the structure passed as the
+** first argument.
+**
+** If this maximum height is greater than the current value pointed
+** to by pnHeight, the second parameter, then set *pnHeight to that
+** value.
+*/
+static void heightOfExpr(Expr *p, int *pnHeight){
+  if( p ){
+    if( p->nHeight>*pnHeight ){
+      *pnHeight = p->nHeight;
+    }
+  }
+}
+static void heightOfExprList(ExprList *p, int *pnHeight){
+  if( p ){
+    int i;
+    for(i=0; i<p->nExpr; i++){
+      heightOfExpr(p->a[i].pExpr, pnHeight);
+    }
+  }
+}
+static void heightOfSelect(Select *p, int *pnHeight){
+  if( p ){
+    heightOfExpr(p->pWhere, pnHeight);
+    heightOfExpr(p->pHaving, pnHeight);
+    heightOfExpr(p->pLimit, pnHeight);
+    heightOfExpr(p->pOffset, pnHeight);
+    heightOfExprList(p->pEList, pnHeight);
+    heightOfExprList(p->pGroupBy, pnHeight);
+    heightOfExprList(p->pOrderBy, pnHeight);
+    heightOfSelect(p->pPrior, pnHeight);
+  }
+}
+
+/*
+** Set the Expr.nHeight variable in the structure passed as an 
+** argument. An expression with no children, Expr.pList or 
+** Expr.pSelect member has a height of 1. Any other expression
+** has a height equal to the maximum height of any other 
+** referenced Expr plus one.
+*/
+static void exprSetHeight(Expr *p){
+  int nHeight = 0;
+  heightOfExpr(p->pLeft, &nHeight);
+  heightOfExpr(p->pRight, &nHeight);
+  heightOfExprList(p->pList, &nHeight);
+  heightOfSelect(p->pSelect, &nHeight);
+  p->nHeight = nHeight + 1;
+}
+
+/*
+** Set the Expr.nHeight variable using the exprSetHeight() function. If
+** the height is greater than the maximum allowed expression depth,
+** leave an error in pParse.
+*/
+void sqlite3ExprSetHeight(Parse *pParse, Expr *p){
+  exprSetHeight(p);
+  checkExprHeight(pParse, p->nHeight);
+}
+
+/*
+** Return the maximum height of any expression tree referenced
+** by the select statement passed as an argument.
+*/
+int sqlite3SelectExprHeight(Select *p){
+  int nHeight = 0;
+  heightOfSelect(p, &nHeight);
+  return nHeight;
+}
+#else
+  #define checkExprHeight(x,y)
+  #define exprSetHeight(y)
+#endif /* SQLITE_MAX_EXPR_DEPTH>0 */
+
 /*
 ** Construct a new expression node and return a pointer to it.  Memory
 ** for this node is obtained from sqlite3_malloc().  The calling function
@@ -297,7 +392,7 @@ Expr *sqlite3Expr(
     }
   }
 
-  sqlite3ExprSetHeight(pNew);
+  exprSetHeight(pNew);
   return pNew;
 }
 
@@ -312,7 +407,11 @@ Expr *sqlite3PExpr(
   Expr *pRight,           /* Right operand */
   const Token *pToken     /* Argument token */
 ){
-  return sqlite3Expr(pParse->db, op, pLeft, pRight, pToken);
+  Expr *p = sqlite3Expr(pParse->db, op, pLeft, pRight, pToken);
+  if( p ){
+    checkExprHeight(pParse, p->nHeight);
+  }
+  return p;
 }
 
 /*
@@ -391,7 +490,7 @@ Expr *sqlite3ExprFunction(Parse *pParse, ExprList *pList, Token *pToken){
   pNew->token = *pToken;
   pNew->span = pNew->token;
 
-  sqlite3ExprSetHeight(pNew);
+  sqlite3ExprSetHeight(pParse, pNew);
   return pNew;
 }
 
@@ -738,75 +837,6 @@ void sqlite3ExprListCheckLength(
   }
 }
 
-/* The following three functions, heightOfExpr(), heightOfExprList()
-** and heightOfSelect(), are used to determine the maximum height
-** of any expression tree referenced by the structure passed as the
-** first argument.
-**
-** If this maximum height is greater than the current value pointed
-** to by pnHeight, the second parameter, then set *pnHeight to that
-** value.
-*/
-#if SQLITE_MAX_EXPR_DEPTH>0
-static void heightOfExpr(Expr *p, int *pnHeight){
-  if( p ){
-    if( p->nHeight>*pnHeight ){
-      *pnHeight = p->nHeight;
-    }
-  }
-}
-static void heightOfExprList(ExprList *p, int *pnHeight){
-  if( p ){
-    int i;
-    for(i=0; i<p->nExpr; i++){
-      heightOfExpr(p->a[i].pExpr, pnHeight);
-    }
-  }
-}
-static void heightOfSelect(Select *p, int *pnHeight){
-  if( p ){
-    heightOfExpr(p->pWhere, pnHeight);
-    heightOfExpr(p->pHaving, pnHeight);
-    heightOfExpr(p->pLimit, pnHeight);
-    heightOfExpr(p->pOffset, pnHeight);
-    heightOfExprList(p->pEList, pnHeight);
-    heightOfExprList(p->pGroupBy, pnHeight);
-    heightOfExprList(p->pOrderBy, pnHeight);
-    heightOfSelect(p->pPrior, pnHeight);
-  }
-}
-#endif /* SQLITE_MAX_EXPR_DEPTH>0 */
-
-/*
-** Set the Expr.nHeight variable in the structure passed as an 
-** argument. An expression with no children, Expr.pList or 
-** Expr.pSelect member has a height of 1. Any other expression
-** has a height equal to the maximum height of any other 
-** referenced Expr plus one.
-*/
-#if SQLITE_MAX_EXPR_DEPTH>0
-void sqlite3ExprSetHeight(Expr *p){
-  int nHeight = 0;
-  heightOfExpr(p->pLeft, &nHeight);
-  heightOfExpr(p->pRight, &nHeight);
-  heightOfExprList(p->pList, &nHeight);
-  heightOfSelect(p->pSelect, &nHeight);
-  p->nHeight = nHeight + 1;
-}
-#endif /* SQLITE_MAX_EXPR_DEPTH>0 */
-
-/*
-** Return the maximum height of any expression tree referenced
-** by the select statement passed as an argument.
-*/
-#if SQLITE_MAX_EXPR_DEPTH>0
-int sqlite3SelectExprHeight(Select *p){
-  int nHeight = 0;
-  heightOfSelect(p, &nHeight);
-  return nHeight;
-}
-#endif /* SQLITE_MAX_EXPR_DEPTH>0 */
-
 /*
 ** Delete an entire expression list.
 */
@@ -1536,11 +1566,7 @@ int sqlite3ExprResolveNames(
   if( pExpr==0 ) return 0;
 #if SQLITE_MAX_EXPR_DEPTH>0
   {
-    int mxDepth = pNC->pParse->db->aLimit[SQLITE_LIMIT_EXPR_DEPTH];
-    if( (pExpr->nHeight+pNC->pParse->nHeight)>mxDepth ){
-      sqlite3ErrorMsg(pNC->pParse, 
-         "Expression tree is too large (maximum depth %d)", mxDepth
-      );
+    if( checkExprHeight(pNC->pParse, pExpr->nHeight + pNC->pParse->nHeight) ){
       return 1;
     }
     pNC->pParse->nHeight += pExpr->nHeight;
diff --git a/src/parse.y b/src/parse.y
index 4df5db88e..914cad15d 100644
--- a/src/parse.y
+++ b/src/parse.y
@@ -14,7 +14,7 @@
 ** the parser.  Lemon will also generate a header file containing
 ** numeric codes for all of the tokens.
 **
-** @(#) $Id: parse.y,v 1.243 2008/04/17 20:59:38 drh Exp $
+** @(#) $Id: parse.y,v 1.244 2008/06/05 16:47:39 danielk1977 Exp $
 */
 
 // All token codes are small integers with #defines that begin with "TK_"
@@ -773,7 +773,7 @@ expr(A) ::= expr(W) between_op(N) expr(X) AND expr(Y). [BETWEEN] {
     A = sqlite3PExpr(pParse, TK_IN, X, 0, 0);
     if( A ){
       A->pList = Y;
-      sqlite3ExprSetHeight(A);
+      sqlite3ExprSetHeight(pParse, A);
     }else{
       sqlite3ExprListDelete(Y);
     }
@@ -784,7 +784,7 @@ expr(A) ::= expr(W) between_op(N) expr(X) AND expr(Y). [BETWEEN] {
     A = sqlite3PExpr(pParse, TK_SELECT, 0, 0, 0);
     if( A ){
       A->pSelect = X;
-      sqlite3ExprSetHeight(A);
+      sqlite3ExprSetHeight(pParse, A);
     }else{
       sqlite3SelectDelete(X);
     }
@@ -794,7 +794,7 @@ expr(A) ::= expr(W) between_op(N) expr(X) AND expr(Y). [BETWEEN] {
     A = sqlite3PExpr(pParse, TK_IN, X, 0, 0);
     if( A ){
       A->pSelect = Y;
-      sqlite3ExprSetHeight(A);
+      sqlite3ExprSetHeight(pParse, A);
     }else{
       sqlite3SelectDelete(Y);
     }
@@ -806,7 +806,7 @@ expr(A) ::= expr(W) between_op(N) expr(X) AND expr(Y). [BETWEEN] {
     A = sqlite3PExpr(pParse, TK_IN, X, 0, 0);
     if( A ){
       A->pSelect = sqlite3SelectNew(pParse, 0,pSrc,0,0,0,0,0,0,0);
-      sqlite3ExprSetHeight(A);
+      sqlite3ExprSetHeight(pParse, A);
     }else{
       sqlite3SrcListDelete(pSrc);
     }
@@ -818,7 +818,7 @@ expr(A) ::= expr(W) between_op(N) expr(X) AND expr(Y). [BETWEEN] {
     if( p ){
       p->pSelect = Y;
       sqlite3ExprSpan(p,&B,&E);
-      sqlite3ExprSetHeight(A);
+      sqlite3ExprSetHeight(pParse, A);
     }else{
       sqlite3SelectDelete(Y);
     }
@@ -830,7 +830,7 @@ expr(A) ::= CASE(C) case_operand(X) case_exprlist(Y) case_else(Z) END(E). {
   A = sqlite3PExpr(pParse, TK_CASE, X, Z, 0);
   if( A ){
     A->pList = Y;
-    sqlite3ExprSetHeight(A);
+    sqlite3ExprSetHeight(pParse, A);
   }else{
     sqlite3ExprListDelete(Y);
   }
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index b00a8a5c1..9981ef071 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -11,7 +11,7 @@
 *************************************************************************
 ** Internal interface definitions for SQLite.
 **
-** @(#) $Id: sqliteInt.h,v 1.705 2008/05/28 13:49:36 drh Exp $
+** @(#) $Id: sqliteInt.h,v 1.706 2008/06/05 16:47:39 danielk1977 Exp $
 */
 #ifndef _SQLITEINT_H_
 #define _SQLITEINT_H_
@@ -2196,10 +2196,10 @@ int sqlite3FindInIndex(Parse *, Expr *, int);
 #endif
 
 #if SQLITE_MAX_EXPR_DEPTH>0
-  void sqlite3ExprSetHeight(Expr *);
+  void sqlite3ExprSetHeight(Parse *pParse, Expr *p);
   int sqlite3SelectExprHeight(Select *);
 #else
-  #define sqlite3ExprSetHeight(x)
+  #define sqlite3ExprSetHeight(x,y)
   #define sqlite3SelectExprHeight(x) 0
 #endif