Add code to enforce the MAX_EXPR_DEPTH limit. (CVS 3968)
FossilOrigin-Name: 2c9c94a24d52a1c9f5d1b32cbdff794a2dd74126
diff --git a/src/expr.c b/src/expr.c
index 828cf60..e7358b5 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 @@
pNew->pColl = pLeft->pColl;
}
}
+
+ sqlite3ExprSetHeight(pNew);
return pNew;
}
@@ -343,6 +345,8 @@
assert( pToken->dyn==0 );
pNew->token = *pToken;
pNew->span = pNew->token;
+
+ sqlite3ExprSetHeight(pNew);
return pNew;
}
@@ -478,6 +482,9 @@
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 @@
}
}
+
+#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 @@
** 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 @@
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 @@
if( testAddr ){
sqlite3VdbeJumpHere(v, testAddr);
}
+
return;
}
#endif /* SQLITE_OMIT_SUBQUERY */
diff --git a/src/limits.h b/src/limits.h
index ff7bdfd..21c3668 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 a7e07b9..991a932 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 @@
A = sqlite3Expr(TK_IN, X, 0, 0);
if( A ){
A->pList = Y;
+ sqlite3ExprSetHeight(A);
}else{
sqlite3ExprListDelete(Y);
}
@@ -776,6 +777,7 @@
A = sqlite3Expr(TK_SELECT, 0, 0, 0);
if( A ){
A->pSelect = X;
+ sqlite3ExprSetHeight(A);
}else{
sqlite3SelectDelete(X);
}
@@ -785,6 +787,7 @@
A = sqlite3Expr(TK_IN, X, 0, 0);
if( A ){
A->pSelect = Y;
+ sqlite3ExprSetHeight(A);
}else{
sqlite3SelectDelete(Y);
}
@@ -796,6 +799,7 @@
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 @@
if( p ){
p->pSelect = Y;
sqlite3ExprSpan(p,&B,&E);
+ sqlite3ExprSetHeight(A);
}else{
sqlite3SelectDelete(Y);
}
@@ -818,6 +823,7 @@
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 83c9d6b..dd8b81d 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 @@
}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 8daf349..fc2525f 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 @@
** 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 @@
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 @@
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 40c0215..7f4689e 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 @@
(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;