SQLite

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains routines used for analyzing expressions and
** for generating VDBE code that evaluates expressions in SQLite.
**
** $Id: expr.c,v 1.289 2007/05/10 10:46:56 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** Return the 'affinity' of the expression pExpr if any.
**

      }
    }
    if( pLeft->flags & EP_ExpCollate ){
      pNew->flags |= EP_ExpCollate;
      pNew->pColl = pLeft->pColl;
    }
  }

  sqlite3ExprSetHeight(pNew);
  return pNew;
}

/*
** Works like sqlite3Expr() but frees its pLeft and pRight arguments
** if it fails due to a malloc problem.
*/

    return 0;
  }
  pNew->op = TK_FUNCTION;
  pNew->pList = pList;
  assert( pToken->dyn==0 );
  pNew->token = *pToken;
  pNew->span = pNew->token;

  sqlite3ExprSetHeight(pNew);
  return pNew;
}

/*
** Assign a variable number to an expression that encodes a wildcard
** in the original SQL statement.  
**

  }
  pNew->span.z = 0;
  pNew->pLeft = sqlite3ExprDup(p->pLeft);
  pNew->pRight = sqlite3ExprDup(p->pRight);
  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){
  if( pTo->dyn ) sqliteFree((char*)pTo->z);
  if( pFrom->z ){
    pTo->n = pFrom->n;
    pTo->z = (u8*)sqliteStrNDup((char*)pFrom->z, pFrom->n);

  const char *zObject
){
  if( pEList && pEList->nExpr>iLimit ){
    sqlite3ErrorMsg(pParse, "too many columns in %s", zObject);
  }
}


#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.
*/
void sqlite3ExprListDelete(ExprList *pList){
  int i;
  struct ExprList_item *pItem;
  if( pList==0 ) return;

** usage.  Make sure all function names are recognized and all functions
** have the correct number of arguments.  Leave an error message
** in pParse->zErrMsg if anything is amiss.  Return the number of errors.
**
** If the expression contains aggregate functions then set the EP_Agg
** property on the expression.
*/
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);
  }
  if( pNC->hasAgg ){
    ExprSetProperty(pExpr, EP_Agg);
  }else if( savedHasAgg ){
    pNC->hasAgg = 1;

** operator or subquery.
*/
#ifndef SQLITE_OMIT_SUBQUERY
void sqlite3CodeSubselect(Parse *pParse, Expr *pExpr){
  int testAddr = 0;                       /* One-time test address */
  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:
  **
  **    *  The right-hand side is a correlated subquery
  **    *  The right-hand side is an expression list containing variables
  **    *  We are inside a trigger

      break;
    }
  }

  if( testAddr ){
    sqlite3VdbeJumpHere(v, testAddr);
  }

  return;
}
#endif /* SQLITE_OMIT_SUBQUERY */

/*
** Generate an instruction that will put the integer describe by
** text z[0..n-1] on the stack.

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** 
** This file defines various limits of what SQLite can process.
**
** @(#) $Id: limits.h,v 1.6 2007/05/10 10:46:56 danielk1977 Exp $
*/

/*
** The maximum length of a TEXT or BLOB in bytes.   This also
** limits the size of a row in a table or index.
**
** The hard limit is the ability of a 32-bit signed integer

** The hard limit here is the same as SQLITE_MAX_LENGTH.
*/
#ifndef SQLITE_MAX_SQL_LENGTH
# define SQLITE_MAX_SQL_LENGTH 1000000
#endif

/*
** 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_DEPTH
# define SQLITE_MAX_EXPR_DEPTH 0
#endif

/*
** The maximum number of opcodes in a VDBE program.
*/
#ifndef SQLITE_MAX_VDBE_OP
# define SQLITE_MAX_VDBE_OP 25000

**
*************************************************************************
** This file contains SQLite's grammar for SQL.  Process this file
** using the lemon parser generator to generate C code that runs
** the parser.  Lemon will also generate a header file containing
** numeric codes for all of the tokens.
**
** @(#) $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_"
%token_prefix TK_

// The type of the data attached to each token is Token.  This is also the
// default type for non-terminals.

  %type in_op {int}
  in_op(A) ::= IN.      {A = 0;}
  in_op(A) ::= NOT IN.  {A = 1;}
  expr(A) ::= expr(X) in_op(N) LP exprlist(Y) RP(E). [IN] {
    A = sqlite3Expr(TK_IN, X, 0, 0);
    if( A ){
      A->pList = Y;
      sqlite3ExprSetHeight(A);
    }else{
      sqlite3ExprListDelete(Y);
    }
    if( N ) A = sqlite3Expr(TK_NOT, A, 0, 0);
    sqlite3ExprSpan(A,&X->span,&E);
  }
  expr(A) ::= LP(B) select(X) RP(E). {
    A = sqlite3Expr(TK_SELECT, 0, 0, 0);
    if( A ){
      A->pSelect = X;
      sqlite3ExprSetHeight(A);
    }else{
      sqlite3SelectDelete(X);
    }
    sqlite3ExprSpan(A,&B,&E);
  }
  expr(A) ::= expr(X) in_op(N) LP select(Y) RP(E).  [IN] {
    A = sqlite3Expr(TK_IN, X, 0, 0);
    if( A ){
      A->pSelect = Y;
      sqlite3ExprSetHeight(A);
    }else{
      sqlite3SelectDelete(Y);
    }
    if( N ) A = sqlite3Expr(TK_NOT, A, 0, 0);
    sqlite3ExprSpan(A,&X->span,&E);
  }
  expr(A) ::= expr(X) in_op(N) nm(Y) dbnm(Z). [IN] {
    SrcList *pSrc = sqlite3SrcListAppend(0,&Y,&Z);
    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);
    }
    if( N ) A = sqlite3Expr(TK_NOT, A, 0, 0);
    sqlite3ExprSpan(A,&X->span,Z.z?&Z:&Y);
  }
  expr(A) ::= EXISTS(B) LP select(Y) RP(E). {
    Expr *p = A = sqlite3Expr(TK_EXISTS, 0, 0, 0);
    if( p ){
      p->pSelect = Y;
      sqlite3ExprSpan(p,&B,&E);
      sqlite3ExprSetHeight(A);
    }else{
      sqlite3SelectDelete(Y);
    }
  }
%endif SQLITE_OMIT_SUBQUERY

/* CASE expressions */
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);
  }
  sqlite3ExprSpan(A, &C, &E);
}
%type case_exprlist {ExprList*}
%destructor case_exprlist {sqlite3ExprListDelete($$);}

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements in SQLite.
**
** $Id: select.c,v 1.344 2007/05/10 10:46:57 danielk1977 Exp $
*/
#include "sqliteInt.h"


/*
** Delete all the content of a Select structure but do not deallocate
** the select structure itself.

    if( pItem->zName!=0 ){
      zSavedAuthContext = pParse->zAuthContext;
      pParse->zAuthContext = pItem->zName;
      needRestoreContext = 1;
    }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;
    }
    pTabList = p->pSrc;
    pWhere = p->pWhere;
    if( !IgnorableOrderby(eDest) ){
      pOrderBy = p->pOrderBy;

/*
** 2001 September 15
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.563 2007/05/10 10:46:57 danielk1977 Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_
#include "limits.h"


#if defined(SQLITE_TCL) || defined(TCLSH)

  AggInfo *pAggInfo;     /* Used by TK_AGG_COLUMN and TK_AGG_FUNCTION */
  int iAgg;              /* Which entry in pAggInfo->aCol[] or ->aFunc[] */
  int iRightJoinTable;   /* If EP_FromJoin, the right table of the join */
  Select *pSelect;       /* When the expression is a sub-select.  Also the
                         ** 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
};

/*
** The following are the meanings of bits in the Expr.flags field.
*/
#define EP_FromJoin     0x01  /* Originated in ON or USING clause of a join */
#define EP_Agg          0x02  /* Contains one or more aggregate functions */

  TriggerStack *trigStack;  /* Trigger actions being coded */
  const char *zAuthContext; /* The 6th parameter to db->xAuth callbacks */
#ifndef SQLITE_OMIT_VIRTUALTABLE
  Token sArg;                /* Complete text of a module argument */
  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
  #define IN_DECLARE_VTAB 0
#else
  #define IN_DECLARE_VTAB (pParse->declareVtab)
#endif

int sqlite3VtabCallConnect(Parse*, Table*);
int sqlite3VtabCallDestroy(sqlite3*, int, const char *);
int sqlite3VtabBegin(sqlite3 *, sqlite3_vtab *);
FuncDef *sqlite3VtabOverloadFunction(FuncDef*, int nArg, Expr*);
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);
void sqlite3Put4byte(u8*, u32);

#ifdef SQLITE_SSE

** 
** This file contains code used for testing the SQLite system.
** None of the code in this file goes into a deliverable build.
** 
** The focus of this file is providing the TCL testing layer
** access to compile-time constants.
**
** $Id: test_config.c,v 1.4 2007/05/10 10:46:57 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include "os.h"
#include <stdlib.h>
#include <string.h>

  }
  {
    static int sqlite_max_sql_length = SQLITE_MAX_SQL_LENGTH;
    Tcl_LinkVar(interp, "SQLITE_MAX_SQL_LENGTH",
           (char*)&sqlite_max_sql_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;
    Tcl_LinkVar(interp, "SQLITE_MAX_VDBE_OP",
           (char*)&sqlite_max_vdbe_op, TCL_LINK_INT|TCL_LINK_READ_ONLY);
  }
  {

#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# This file contains tests to verify that the limits defined in
# sqlite source file limits.h are enforced.
#
# $Id: sqllimits1.test,v 1.7 2007/05/10 10:46:57 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Test organization:
#
#     sqllimits-1.*:  SQLITE_MAX_LENGTH
#     sqllimits-2.*:  SQLITE_MAX_SQL_LENGTH
#     sqllimits-3.*:  SQLITE_MAX_PAGE_COUNT
#     sqllimits-4.*:  SQLITE_MAX_COLUMN
#
#
#     sqllimits-7.*:   SQLITE_MAX_FUNCTION_ARG  
#     sqllimits-8.*:   SQLITE_MAX_ATTACHED
#     sqllimits-9.*:   SQLITE_MAX_VARIABLE_NUMBER
#     sqllimits-10.*:  SQLITE_MAX_PAGE_SIZE
#     sqllimits-11.*:  SQLITE_MAX_LIKE_PATTERN_LENGTH
#
# Todo:
#
#     sqllimits-5.*:   SQLITE_MAX_EXPR_DEPTH            (sqlite todo)
#     sqllimits-6.*:   SQLITE_MAX_VDBE_OP               (sqlite todo)
#

#--------------------------------------------------------------------
# Test cases sqllimits-1.* test that the SQLITE_MAX_LENGTH limit
# is enforced.
#

    lappend cols "c$i"
  }
  catchsql "CREATE TABLE t2([join $cols ,])"
  catchsql "CREATE VIEW v1 AS SELECT *, c1 AS o FROM t2;"
} {1 {too many columns in result set}}

#--------------------------------------------------------------------
# These tests - sqllimits-5.* - test that the SQLITE_MAX_EXPR_DEPTH
# limit is enforced. The limit refers to the number of terms in 
# the expression.
#
if {$::SQLITE_MAX_EXPR_DEPTH != 1000} {
  puts -nonewline stderr "WARNING: Compile with -DSQLITE_MAX_EXPR_DEPTH to run "
  puts stderr "tests sqllimits-1.5.X"
} else {
  do_test sqllimits-1.5.1 {
    set max $::SQLITE_MAX_EXPR_DEPTH
    set expr "(1 [string repeat {AND 1 } $max])"
    catchsql [subst {
      SELECT $expr
    }]
  } "1 {Expression tree is too large (maximum depth $::SQLITE_MAX_EXPR_DEPTH)}"
  
  # Attempting to beat the expression depth limit using nested SELECT
  # queries causes a parser stack overflow. 
  do_test sqllimits-1.5.2 {
    set max $::SQLITE_MAX_EXPR_DEPTH
    set expr "SELECT 1"
    for {set i 0} {$i <= $max} {incr i} {
      set expr "SELECT ($expr)"
    }
    catchsql [subst {
      SELECT $expr
    }]
  } "1 {parser stack overflow}"
  
  
  do_test sqllimits-1.5.3 {
    execsql {
      PRAGMA max_page_count = 1000000;  -- 1 GB
      CREATE TABLE v0(a);
      INSERT INTO v0 VALUES(1);
    }
    db transaction {
      for {set i 1} {$i < 200} {incr i} {
        set expr "(a [string repeat {AND 1 } 50]) AS a"
        execsql [subst {
          CREATE VIEW v${i} AS SELECT $expr FROM v[expr {$i-1}]
        }]
      }
    }
  } {}
  
  do_test sqllimits-1.5.4 {
    catchsql {
      SELECT a FROM v199
    }
  } "1 {Expression tree is too large (maximum depth $::SQLITE_MAX_EXPR_DEPTH)}"
}

#--------------------------------------------------------------------
# Test cases sqllimits-6.* test that the SQLITE_MAX_VDBE_OP
# limit works as expected. The limit refers to the number of opcodes
# in a single VDBE program.
#
# TODO