Add code to enforce the MAX_EXPR_DEPTH limit. (CVS 3968)

FossilOrigin-Name: 2c9c94a24d52a1c9f5d1b32cbdff794a2dd74126

6 files changed, 137 insertions, 16 deletions

diff --git a/src/expr.c b/src/expr.c
index 828cf6050..e7358b554 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.288 2007/05/09 11:37:23 danielk1977 Exp $
+** $Id: expr.c,v 1.289 2007/05/10 10:46:56 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 #include <ctype.h>
@@ -247,6 +247,8 @@ Expr *sqlite3Expr(int op, Expr *pLeft, Expr *pRight, const Token *pToken){
       pNew->pColl = pLeft->pColl;
     }
   }
+
+  sqlite3ExprSetHeight(pNew);
   return pNew;
 }
 
@@ -343,6 +345,8 @@ Expr *sqlite3ExprFunction(ExprList *pList, Token *pToken){
   assert( pToken->dyn==0 );
   pNew->token = *pToken;
   pNew->span = pNew->token;
+
+  sqlite3ExprSetHeight(pNew);
   return pNew;
 }
 
@@ -478,6 +482,9 @@ Expr *sqlite3ExprDup(Expr *p){
   pNew->pList = sqlite3ExprListDup(p->pList);
   pNew->pSelect = sqlite3SelectDup(p->pSelect);
   pNew->pTab = p->pTab;
+#if SQLITE_MAX_EXPR_DEPTH>0
+  pNew->nHeight = p->nHeight;
+#endif
   return pNew;
 }
 void sqlite3TokenCopy(Token *pTo, Token *pFrom){
@@ -671,6 +678,72 @@ void sqlite3ExprListCheckLength(
   }
 }
 
+
+#if SQLITE_MAX_EXPR_DEPTH>0
+/* 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.
+*/
+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;
+}
+
+/*
+** 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;
+}
+#endif
+
 /*
 ** Delete an entire expression list.
 */
@@ -1335,15 +1408,28 @@ static int nameResolverStep(void *pArg, Expr *pExpr){
 ** If the expression contains aggregate functions then set the EP_Agg
 ** property on the expression.
 */
-int sqlite3ExprResolveNames(
+int sqlite3ExprResolveNames( 
   NameContext *pNC,       /* Namespace to resolve expressions in. */
   Expr *pExpr             /* The expression to be analyzed. */
 ){
   int savedHasAgg;
   if( pExpr==0 ) return 0;
+#if SQLITE_MAX_EXPR_DEPTH>0
+  if( (pExpr->nHeight+pNC->pParse->nHeight)>SQLITE_MAX_EXPR_DEPTH ){
+    sqlite3ErrorMsg(pNC->pParse, 
+       "Expression tree is too large (maximum depth %d)",
+       SQLITE_MAX_EXPR_DEPTH
+    );
+    return 1;
+  }
+  pNC->pParse->nHeight += pExpr->nHeight;
+#endif
   savedHasAgg = pNC->hasAgg;
   pNC->hasAgg = 0;
   walkExprTree(pExpr, nameResolverStep, pNC);
+#if SQLITE_MAX_EXPR_DEPTH>0
+  pNC->pParse->nHeight -= pExpr->nHeight;
+#endif
   if( pNC->nErr>0 ){
     ExprSetProperty(pExpr, EP_Error);
   }
@@ -1384,6 +1470,7 @@ void sqlite3CodeSubselect(Parse *pParse, Expr *pExpr){
   Vdbe *v = sqlite3GetVdbe(pParse);
   if( v==0 ) return;
 
+
   /* This code must be run in its entirety every time it is encountered
   ** if any of the following is true:
   **
@@ -1521,6 +1608,7 @@ void sqlite3CodeSubselect(Parse *pParse, Expr *pExpr){
   if( testAddr ){
     sqlite3VdbeJumpHere(v, testAddr);
   }
+
   return;
 }
 #endif /* SQLITE_OMIT_SUBQUERY */
diff --git a/src/limits.h b/src/limits.h
index ff7bdfde0..21c36680b 100644
--- a/src/limits.h
+++ b/src/limits.h
@@ -12,7 +12,7 @@
 ** 
 ** This file defines various limits of what SQLite can process.
 **
-** @(#) $Id: limits.h,v 1.5 2007/05/08 15:34:48 drh Exp $
+** @(#) $Id: limits.h,v 1.6 2007/05/10 10:46:56 danielk1977 Exp $
 */
 
 /*
@@ -56,13 +56,14 @@
 #endif
 
 /*
-** The maximum number of terms in an expression.
-** This is limited to some extent by SQLITE_MAX_SQL_LENGTH.
-** But sometime you might want to place more severe limits
-** on the complexity of an expression.
+** The maximum depth of an expression tree. This is limited to 
+** some extent by SQLITE_MAX_SQL_LENGTH. But sometime you might 
+** want to place more severe limits on the complexity of an 
+** expression. A value of 0 (the default) means do not enforce
+** any limitation on expression tree depth.
 */
-#ifndef SQLITE_MAX_EXPR_LENGTH
-# define SQLITE_MAX_EXPR_LENGTH 5000
+#ifndef SQLITE_MAX_EXPR_DEPTH
+# define SQLITE_MAX_EXPR_DEPTH 0
 #endif
 
 /*
diff --git a/src/parse.y b/src/parse.y
index a7e07b9a7..991a93269 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.224 2007/05/08 17:54:44 danielk1977 Exp $
+** @(#) $Id: parse.y,v 1.225 2007/05/10 10:46:57 danielk1977 Exp $
 */
 
 // All token codes are small integers with #defines that begin with "TK_"
@@ -766,6 +766,7 @@ expr(A) ::= expr(W) between_op(N) expr(X) AND expr(Y). [BETWEEN] {
     A = sqlite3Expr(TK_IN, X, 0, 0);
     if( A ){
       A->pList = Y;
+      sqlite3ExprSetHeight(A);
     }else{
       sqlite3ExprListDelete(Y);
     }
@@ -776,6 +777,7 @@ expr(A) ::= expr(W) between_op(N) expr(X) AND expr(Y). [BETWEEN] {
     A = sqlite3Expr(TK_SELECT, 0, 0, 0);
     if( A ){
       A->pSelect = X;
+      sqlite3ExprSetHeight(A);
     }else{
       sqlite3SelectDelete(X);
     }
@@ -785,6 +787,7 @@ expr(A) ::= expr(W) between_op(N) expr(X) AND expr(Y). [BETWEEN] {
     A = sqlite3Expr(TK_IN, X, 0, 0);
     if( A ){
       A->pSelect = Y;
+      sqlite3ExprSetHeight(A);
     }else{
       sqlite3SelectDelete(Y);
     }
@@ -796,6 +799,7 @@ expr(A) ::= expr(W) between_op(N) expr(X) AND expr(Y). [BETWEEN] {
     A = sqlite3Expr(TK_IN, X, 0, 0);
     if( A ){
       A->pSelect = sqlite3SelectNew(0,pSrc,0,0,0,0,0,0,0);
+      sqlite3ExprSetHeight(A);
     }else{
       sqlite3SrcListDelete(pSrc);
     }
@@ -807,6 +811,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);
     }else{
       sqlite3SelectDelete(Y);
     }
@@ -818,6 +823,7 @@ expr(A) ::= CASE(C) case_operand(X) case_exprlist(Y) case_else(Z) END(E). {
   A = sqlite3Expr(TK_CASE, X, Z, 0);
   if( A ){
     A->pList = Y;
+    sqlite3ExprSetHeight(A);
   }else{
     sqlite3ExprListDelete(Y);
   }
diff --git a/src/select.c b/src/select.c
index 83c9d6b67..dd8b81d82 100644
--- a/src/select.c
+++ b/src/select.c
@@ -12,7 +12,7 @@
 ** This file contains C code routines that are called by the parser
 ** to handle SELECT statements in SQLite.
 **
-** $Id: select.c,v 1.343 2007/05/09 22:56:39 drh Exp $
+** $Id: select.c,v 1.344 2007/05/10 10:46:57 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 
@@ -2940,8 +2940,21 @@ int sqlite3Select(
     }else{
       needRestoreContext = 0;
     }
+#if SQLITE_MAX_EXPR_DEPTH>0
+    /* Increment Parse.nHeight by the height of the largest expression
+    ** tree refered to by this, the parent select. The child select
+    ** may contain expression trees of at most
+    ** (SQLITE_MAX_EXPR_DEPTH-Parse.nHeight) height. This is a bit
+    ** more conservative than necessary, but much easier than enforcing
+    ** an exact limit.
+    */
+    pParse->nHeight += sqlite3SelectExprHeight(p);
+#endif
     sqlite3Select(pParse, pItem->pSelect, SRT_EphemTab, 
                  pItem->iCursor, p, i, &isAgg, 0);
+#if SQLITE_MAX_EXPR_DEPTH>0
+    pParse->nHeight -= sqlite3SelectExprHeight(p);
+#endif
     if( needRestoreContext ){
       pParse->zAuthContext = zSavedAuthContext;
     }
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 8daf349ba..fc2525f8f 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -11,7 +11,7 @@
 *************************************************************************
 ** Internal interface definitions for SQLite.
 **
-** @(#) $Id: sqliteInt.h,v 1.562 2007/05/08 21:45:28 drh Exp $
+** @(#) $Id: sqliteInt.h,v 1.563 2007/05/10 10:46:57 danielk1977 Exp $
 */
 #ifndef _SQLITEINT_H_
 #define _SQLITEINT_H_
@@ -998,6 +998,9 @@ struct Expr {
                          ** right side of "<expr> IN (<select>)" */
   Table *pTab;           /* Table for OP_Column expressions. */
   Schema *pSchema;
+#if SQLITE_MAX_EXPR_DEPTH>0
+  int nHeight;           /* Height of the tree headed by this node */
+#endif
 };
 
 /*
@@ -1343,6 +1346,9 @@ struct Parse {
   u8 declareVtab;            /* True if inside sqlite3_declare_vtab() */
   Table *pVirtualLock;       /* Require virtual table lock on this table */
 #endif
+#if SQLITE_MAX_EXPR_DEPTH>0
+  int nHeight;            /* Expression tree height of current sub-select */
+#endif
 };
 
 #ifdef SQLITE_OMIT_VIRTUALTABLE
@@ -1878,6 +1884,13 @@ void sqlite3InvalidFunction(sqlite3_context*,int,sqlite3_value**);
 int sqlite3Reprepare(Vdbe*);
 void sqlite3ExprListCheckLength(Parse*, ExprList*, int, const char*);
 
+#if SQLITE_MAX_EXPR_DEPTH>0
+  void sqlite3ExprSetHeight(Expr *);
+  int sqlite3SelectExprHeight(Select *);
+#else
+  #define sqlite3ExprSetHeight(x)
+#endif
+
 u32 sqlite3Get2byte(const u8*);
 u32 sqlite3Get4byte(const u8*);
 void sqlite3Put2byte(u8*, u32);
diff --git a/src/test_config.c b/src/test_config.c
index 40c021557..7f4689e51 100644
--- a/src/test_config.c
+++ b/src/test_config.c
@@ -16,7 +16,7 @@
 ** The focus of this file is providing the TCL testing layer
 ** access to compile-time constants.
 **
-** $Id: test_config.c,v 1.3 2007/05/09 11:37:23 danielk1977 Exp $
+** $Id: test_config.c,v 1.4 2007/05/10 10:46:57 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 #include "tcl.h"
@@ -382,9 +382,9 @@ static void set_options(Tcl_Interp *interp){
            (char*)&sqlite_max_sql_length, TCL_LINK_INT|TCL_LINK_READ_ONLY);
   }
   {
-    static int sqlite_max_expr_length = SQLITE_MAX_EXPR_LENGTH;
-    Tcl_LinkVar(interp, "SQLITE_MAX_EXPR_LENGTH",
-           (char*)&sqlite_max_expr_length, TCL_LINK_INT|TCL_LINK_READ_ONLY);
+    static int sqlite_max_expr_depth = SQLITE_MAX_EXPR_DEPTH;
+    Tcl_LinkVar(interp, "SQLITE_MAX_EXPR_DEPTH",
+           (char*)&sqlite_max_expr_depth, TCL_LINK_INT|TCL_LINK_READ_ONLY);
   }
   {
     static int sqlite_max_vdbe_op = SQLITE_MAX_VDBE_OP;