src/walker.c

   1 /*
   2 ** 2008 August 16
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 *************************************************************************
  12 ** This file contains routines used for walking the parser tree for
  13 ** an SQL statement.
  14 */
  15 #include "sqliteInt.h"
  16 #include <stdlib.h>
  17 #include <string.h>
  18
  19
  20 #if !defined(SQLITE_OMIT_WINDOWFUNC)
  21 /*
  22 ** Walk all expressions linked into the list of Window objects passed
  23 ** as the second argument.
  24 */
  25 static int walkWindowList(Walker *pWalker, Window *pList){
  26   Window *pWin;
  27   for(pWin=pList; pWin; pWin=pWin->pNextWin){
  28     int rc;
  29     rc = sqlite3WalkExprList(pWalker, pWin->pOrderBy);
  30     if( rc ) return WRC_Abort;
  31     rc = sqlite3WalkExprList(pWalker, pWin->pPartition);
  32     if( rc ) return WRC_Abort;
  33     rc = sqlite3WalkExpr(pWalker, pWin->pFilter);
  34     if( rc ) return WRC_Abort;
  35
  36     /* The next two are purely for calls to sqlite3RenameExprUnmap()
  37     ** within sqlite3WindowOffsetExpr().  Because of constraints imposed
  38     ** by sqlite3WindowOffsetExpr(), they can never fail.  The results do
  39     ** not matter anyhow. */
  40     rc = sqlite3WalkExpr(pWalker, pWin->pStart);
  41     if( NEVER(rc) ) return WRC_Abort;
  42     rc = sqlite3WalkExpr(pWalker, pWin->pEnd);
  43     if( NEVER(rc) ) return WRC_Abort;
  44   }
  45   return WRC_Continue;
  46 }
  47 #endif
  48
  49 /*
  50 ** Walk an expression tree.  Invoke the callback once for each node
  51 ** of the expression, while descending.  (In other words, the callback
  52 ** is invoked before visiting children.)
  53 **
  54 ** The return value from the callback should be one of the WRC_*
  55 ** constants to specify how to proceed with the walk.
  56 **
  57 **    WRC_Continue      Continue descending down the tree.
  58 **
  59 **    WRC_Prune         Do not descend into child nodes, but allow
  60 **                      the walk to continue with sibling nodes.
  61 **
  62 **    WRC_Abort         Do no more callbacks.  Unwind the stack and
  63 **                      return from the top-level walk call.
  64 **
  65 ** The return value from this routine is WRC_Abort to abandon the tree walk
  66 ** and WRC_Continue to continue.
  67 */
  68 static SQLITE_NOINLINE int walkExpr(Walker *pWalker, Expr *pExpr){
  69   int rc;
  70   testcase( ExprHasProperty(pExpr, EP_TokenOnly) );
  71   testcase( ExprHasProperty(pExpr, EP_Reduced) );
  72   while(1){
  73     rc = pWalker->xExprCallback(pWalker, pExpr);
  74     if( rc ) return rc & WRC_Abort;
  75     if( !ExprHasProperty(pExpr,(EP_TokenOnly|EP_Leaf)) ){
  76       assert( pExpr->x.pList==0 || pExpr->pRight==0 );
  77       if( pExpr->pLeft && walkExpr(pWalker, pExpr->pLeft) ) return WRC_Abort;
  78       if( pExpr->pRight ){
  79         assert( !ExprHasProperty(pExpr, EP_WinFunc) );
  80         pExpr = pExpr->pRight;
  81         continue;
  82       }else if( ExprHasProperty(pExpr, EP_xIsSelect) ){
  83         assert( !ExprHasProperty(pExpr, EP_WinFunc) );
  84         if( sqlite3WalkSelect(pWalker, pExpr->x.pSelect) ) return WRC_Abort;
  85       }else{
  86         if( pExpr->x.pList ){
  87           if( sqlite3WalkExprList(pWalker, pExpr->x.pList) ) return WRC_Abort;
  88         }
  89 #ifndef SQLITE_OMIT_WINDOWFUNC
  90         if( ExprHasProperty(pExpr, EP_WinFunc) ){
  91           if( walkWindowList(pWalker, pExpr->y.pWin) ) return WRC_Abort;
  92         }
  93 #endif
  94       }
  95     }
  96     break;
  97   }
  98   return WRC_Continue;
  99 }
 100 int sqlite3WalkExpr(Walker *pWalker, Expr *pExpr){
 101   return pExpr ? walkExpr(pWalker,pExpr) : WRC_Continue;
 102 }
 103
 104 /*
 105 ** Call sqlite3WalkExpr() for every expression in list p or until
 106 ** an abort request is seen.
 107 */
 108 int sqlite3WalkExprList(Walker *pWalker, ExprList *p){
 109   int i;
 110   struct ExprList_item *pItem;
 111   if( p ){
 112     for(i=p->nExpr, pItem=p->a; i>0; i--, pItem++){
 113       if( sqlite3WalkExpr(pWalker, pItem->pExpr) ) return WRC_Abort;
 114     }
 115   }
 116   return WRC_Continue;
 117 }
 118
 119 /*
 120 ** Walk all expressions associated with SELECT statement p.  Do
 121 ** not invoke the SELECT callback on p, but do (of course) invoke
 122 ** any expr callbacks and SELECT callbacks that come from subqueries.
 123 ** Return WRC_Abort or WRC_Continue.
 124 */
 125 int sqlite3WalkSelectExpr(Walker *pWalker, Select *p){
 126   if( sqlite3WalkExprList(pWalker, p->pEList) ) return WRC_Abort;
 127   if( sqlite3WalkExpr(pWalker, p->pWhere) ) return WRC_Abort;
 128   if( sqlite3WalkExprList(pWalker, p->pGroupBy) ) return WRC_Abort;
 129   if( sqlite3WalkExpr(pWalker, p->pHaving) ) return WRC_Abort;
 130   if( sqlite3WalkExprList(pWalker, p->pOrderBy) ) return WRC_Abort;
 131   if( sqlite3WalkExpr(pWalker, p->pLimit) ) return WRC_Abort;
 132 #if !defined(SQLITE_OMIT_WINDOWFUNC) && !defined(SQLITE_OMIT_ALTERTABLE)
 133   {
 134     Parse *pParse = pWalker->pParse;
 135     if( pParse && IN_RENAME_OBJECT ){
 136       /* The following may return WRC_Abort if there are unresolvable
 137       ** symbols (e.g. a table that does not exist) in a window definition. */
 138       int rc = walkWindowList(pWalker, p->pWinDefn);
 139       return rc;
 140     }
 141   }
 142 #endif
 143   return WRC_Continue;
 144 }
 145
 146 /*
 147 ** Walk the parse trees associated with all subqueries in the
 148 ** FROM clause of SELECT statement p.  Do not invoke the select
 149 ** callback on p, but do invoke it on each FROM clause subquery
 150 ** and on any subqueries further down in the tree.  Return
 151 ** WRC_Abort or WRC_Continue;
 152 */
 153 int sqlite3WalkSelectFrom(Walker *pWalker, Select *p){
 154   SrcList *pSrc;
 155   int i;
 156   struct SrcList_item *pItem;
 157
 158   pSrc = p->pSrc;
 159   if( pSrc ){
 160     for(i=pSrc->nSrc, pItem=pSrc->a; i>0; i--, pItem++){
 161       if( pItem->pSelect && sqlite3WalkSelect(pWalker, pItem->pSelect) ){
 162         return WRC_Abort;
 163       }
 164       if( pItem->fg.isTabFunc
 165        && sqlite3WalkExprList(pWalker, pItem->u1.pFuncArg)
 166       ){
 167         return WRC_Abort;
 168       }
 169     }
 170   }
 171   return WRC_Continue;
 172 }
 173
 174 /*
 175 ** Call sqlite3WalkExpr() for every expression in Select statement p.
 176 ** Invoke sqlite3WalkSelect() for subqueries in the FROM clause and
 177 ** on the compound select chain, p->pPrior.
 178 **
 179 ** If it is not NULL, the xSelectCallback() callback is invoked before
 180 ** the walk of the expressions and FROM clause. The xSelectCallback2()
 181 ** method is invoked following the walk of the expressions and FROM clause,
 182 ** but only if both xSelectCallback and xSelectCallback2 are both non-NULL
 183 ** and if the expressions and FROM clause both return WRC_Continue;
 184 **
 185 ** Return WRC_Continue under normal conditions.  Return WRC_Abort if
 186 ** there is an abort request.
 187 **
 188 ** If the Walker does not have an xSelectCallback() then this routine
 189 ** is a no-op returning WRC_Continue.
 190 */
 191 int sqlite3WalkSelect(Walker *pWalker, Select *p){
 192   int rc;
 193   if( p==0 ) return WRC_Continue;
 194   if( pWalker->xSelectCallback==0 ) return WRC_Continue;
 195   do{
 196     rc = pWalker->xSelectCallback(pWalker, p);
 197     if( rc ) return rc & WRC_Abort;
 198     if( sqlite3WalkSelectExpr(pWalker, p)
 199      || sqlite3WalkSelectFrom(pWalker, p)
 200     ){
 201       return WRC_Abort;
 202     }
 203     if( pWalker->xSelectCallback2 ){
 204       pWalker->xSelectCallback2(pWalker, p);
 205     }
 206     p = p->pPrior;
 207   }while( p!=0 );
 208   return WRC_Continue;
 209 }
 210
 211 /* Increase the walkerDepth when entering a subquery, and
 212 ** descrease when leaving the subquery.
 213 */
 214 int sqlite3WalkerDepthIncrease(Walker *pWalker, Select *pSelect){
 215   UNUSED_PARAMETER(pSelect);
 216   pWalker->walkerDepth++;
 217   return WRC_Continue;
 218 }
 219 void sqlite3WalkerDepthDecrease(Walker *pWalker, Select *pSelect){
 220   UNUSED_PARAMETER(pSelect);
 221   pWalker->walkerDepth--;
 222 }
 223
 224
 225 /*
 226 ** No-op routine for the parse-tree walker.
 227 **
 228 ** When this routine is the Walker.xExprCallback then expression trees
 229 ** are walked without any actions being taken at each node.  Presumably,
 230 ** when this routine is used for Walker.xExprCallback then
 231 ** Walker.xSelectCallback is set to do something useful for every
 232 ** subquery in the parser tree.
 233 */
 234 int sqlite3ExprWalkNoop(Walker *NotUsed, Expr *NotUsed2){
 235   UNUSED_PARAMETER2(NotUsed, NotUsed2);
 236   return WRC_Continue;
 237 }
 238
 239 /*
 240 ** No-op routine for the parse-tree walker for SELECT statements.
 241 ** subquery in the parser tree.
 242 */
 243 int sqlite3SelectWalkNoop(Walker *NotUsed, Select *NotUsed2){
 244   UNUSED_PARAMETER2(NotUsed, NotUsed2);
 245   return WRC_Continue;
 246 }