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, int bOneOnly){
  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     rc = sqlite3WalkExpr(pWalker, pWin->pStart);
  36     if( rc ) return WRC_Abort;
  37     rc = sqlite3WalkExpr(pWalker, pWin->pEnd);
  38     if( rc ) return WRC_Abort;
  39     if( bOneOnly ) break;
  40   }
  41   return WRC_Continue;
  42 }
  43 #endif
  44
  45 /*
  46 ** Walk an expression tree.  Invoke the callback once for each node
  47 ** of the expression, while descending.  (In other words, the callback
  48 ** is invoked before visiting children.)
  49 **
  50 ** The return value from the callback should be one of the WRC_*
  51 ** constants to specify how to proceed with the walk.
  52 **
  53 **    WRC_Continue      Continue descending down the tree.
  54 **
  55 **    WRC_Prune         Do not descend into child nodes, but allow
  56 **                      the walk to continue with sibling nodes.
  57 **
  58 **    WRC_Abort         Do no more callbacks.  Unwind the stack and
  59 **                      return from the top-level walk call.
  60 **
  61 ** The return value from this routine is WRC_Abort to abandon the tree walk
  62 ** and WRC_Continue to continue.
  63 */
  64 SQLITE_NOINLINE int sqlite3WalkExprNN(Walker *pWalker, Expr *pExpr){
  65   int rc;
  66   testcase( ExprHasProperty(pExpr, EP_TokenOnly) );
  67   testcase( ExprHasProperty(pExpr, EP_Reduced) );
  68   while(1){
  69     rc = pWalker->xExprCallback(pWalker, pExpr);
  70     if( rc ) return rc & WRC_Abort;
  71     if( !ExprHasProperty(pExpr,(EP_TokenOnly|EP_Leaf)) ){
  72       assert( pExpr->x.pList==0 || pExpr->pRight==0 );
  73       if( pExpr->pLeft && sqlite3WalkExprNN(pWalker, pExpr->pLeft) ){
  74         return WRC_Abort;
  75       }
  76       if( pExpr->pRight ){
  77         assert( !ExprHasProperty(pExpr, EP_WinFunc) );
  78         pExpr = pExpr->pRight;
  79         continue;
  80       }else if( ExprUseXSelect(pExpr) ){
  81         assert( !ExprHasProperty(pExpr, EP_WinFunc) );
  82         if( sqlite3WalkSelect(pWalker, pExpr->x.pSelect) ) return WRC_Abort;
  83       }else{
  84         if( pExpr->x.pList ){
  85           if( sqlite3WalkExprList(pWalker, pExpr->x.pList) ) return WRC_Abort;
  86         }
  87 #ifndef SQLITE_OMIT_WINDOWFUNC
  88         if( ExprHasProperty(pExpr, EP_WinFunc) ){
  89           if( walkWindowList(pWalker, pExpr->y.pWin, 1) ) return WRC_Abort;
  90         }
  91 #endif
  92       }
  93     }
  94     break;
  95   }
  96   return WRC_Continue;
  97 }
  98 int sqlite3WalkExpr(Walker *pWalker, Expr *pExpr){
  99   return pExpr ? sqlite3WalkExprNN(pWalker,pExpr) : WRC_Continue;
 100 }
 101
 102 /*
 103 ** Call sqlite3WalkExpr() for every expression in list p or until
 104 ** an abort request is seen.
 105 */
 106 int sqlite3WalkExprList(Walker *pWalker, ExprList *p){
 107   int i;
 108   struct ExprList_item *pItem;
 109   if( p ){
 110     for(i=p->nExpr, pItem=p->a; i>0; i--, pItem++){
 111       if( sqlite3WalkExpr(pWalker, pItem->pExpr) ) return WRC_Abort;
 112     }
 113   }
 114   return WRC_Continue;
 115 }
 116
 117 /*
 118 ** This is a no-op callback for Walker->xSelectCallback2.  If this
 119 ** callback is set, then the Select->pWinDefn list is traversed.
 120 */
 121 void sqlite3WalkWinDefnDummyCallback(Walker *pWalker, Select *p){
 122   UNUSED_PARAMETER(pWalker);
 123   UNUSED_PARAMETER(p);
 124   /* No-op */
 125 }
 126
 127 /*
 128 ** Walk all expressions associated with SELECT statement p.  Do
 129 ** not invoke the SELECT callback on p, but do (of course) invoke
 130 ** any expr callbacks and SELECT callbacks that come from subqueries.
 131 ** Return WRC_Abort or WRC_Continue.
 132 */
 133 int sqlite3WalkSelectExpr(Walker *pWalker, Select *p){
 134   if( sqlite3WalkExprList(pWalker, p->pEList) ) return WRC_Abort;
 135   if( sqlite3WalkExpr(pWalker, p->pWhere) ) return WRC_Abort;
 136   if( sqlite3WalkExprList(pWalker, p->pGroupBy) ) return WRC_Abort;
 137   if( sqlite3WalkExpr(pWalker, p->pHaving) ) return WRC_Abort;
 138   if( sqlite3WalkExprList(pWalker, p->pOrderBy) ) return WRC_Abort;
 139   if( sqlite3WalkExpr(pWalker, p->pLimit) ) return WRC_Abort;
 140 #if !defined(SQLITE_OMIT_WINDOWFUNC)
 141   if( p->pWinDefn ){
 142     Parse *pParse;
 143     if( pWalker->xSelectCallback2==sqlite3WalkWinDefnDummyCallback
 144      || ((pParse = pWalker->pParse)!=0 && IN_RENAME_OBJECT)
 145 #ifndef SQLITE_OMIT_CTE
 146      || pWalker->xSelectCallback2==sqlite3SelectPopWith
 147 #endif
 148     ){
 149       /* The following may return WRC_Abort if there are unresolvable
 150       ** symbols (e.g. a table that does not exist) in a window definition. */
 151       int rc = walkWindowList(pWalker, p->pWinDefn, 0);
 152       return rc;
 153     }
 154   }
 155 #endif
 156   return WRC_Continue;
 157 }
 158
 159 /*
 160 ** Walk the parse trees associated with all subqueries in the
 161 ** FROM clause of SELECT statement p.  Do not invoke the select
 162 ** callback on p, but do invoke it on each FROM clause subquery
 163 ** and on any subqueries further down in the tree.  Return
 164 ** WRC_Abort or WRC_Continue;
 165 */
 166 int sqlite3WalkSelectFrom(Walker *pWalker, Select *p){
 167   SrcList *pSrc;
 168   int i;
 169   SrcItem *pItem;
 170
 171   pSrc = p->pSrc;
 172   if( ALWAYS(pSrc) ){
 173     for(i=pSrc->nSrc, pItem=pSrc->a; i>0; i--, pItem++){
 174       if( pItem->pSelect && sqlite3WalkSelect(pWalker, pItem->pSelect) ){
 175         return WRC_Abort;
 176       }
 177       if( pItem->fg.isTabFunc
 178        && sqlite3WalkExprList(pWalker, pItem->u1.pFuncArg)
 179       ){
 180         return WRC_Abort;
 181       }
 182     }
 183   }
 184   return WRC_Continue;
 185 }
 186
 187 /*
 188 ** Call sqlite3WalkExpr() for every expression in Select statement p.
 189 ** Invoke sqlite3WalkSelect() for subqueries in the FROM clause and
 190 ** on the compound select chain, p->pPrior.
 191 **
 192 ** If it is not NULL, the xSelectCallback() callback is invoked before
 193 ** the walk of the expressions and FROM clause. The xSelectCallback2()
 194 ** method is invoked following the walk of the expressions and FROM clause,
 195 ** but only if both xSelectCallback and xSelectCallback2 are both non-NULL
 196 ** and if the expressions and FROM clause both return WRC_Continue;
 197 **
 198 ** Return WRC_Continue under normal conditions.  Return WRC_Abort if
 199 ** there is an abort request.
 200 **
 201 ** If the Walker does not have an xSelectCallback() then this routine
 202 ** is a no-op returning WRC_Continue.
 203 */
 204 int sqlite3WalkSelect(Walker *pWalker, Select *p){
 205   int rc;
 206   if( p==0 ) return WRC_Continue;
 207   if( pWalker->xSelectCallback==0 ) return WRC_Continue;
 208   do{
 209     rc = pWalker->xSelectCallback(pWalker, p);
 210     if( rc ) return rc & WRC_Abort;
 211     if( sqlite3WalkSelectExpr(pWalker, p)
 212      || sqlite3WalkSelectFrom(pWalker, p)
 213     ){
 214       return WRC_Abort;
 215     }
 216     if( pWalker->xSelectCallback2 ){
 217       pWalker->xSelectCallback2(pWalker, p);
 218     }
 219     p = p->pPrior;
 220   }while( p!=0 );
 221   return WRC_Continue;
 222 }
 223
 224 /* Increase the walkerDepth when entering a subquery, and
 225 ** decrease when leaving the subquery.
 226 */
 227 int sqlite3WalkerDepthIncrease(Walker *pWalker, Select *pSelect){
 228   UNUSED_PARAMETER(pSelect);
 229   pWalker->walkerDepth++;
 230   return WRC_Continue;
 231 }
 232 void sqlite3WalkerDepthDecrease(Walker *pWalker, Select *pSelect){
 233   UNUSED_PARAMETER(pSelect);
 234   pWalker->walkerDepth--;
 235 }
 236
 237
 238 /*
 239 ** No-op routine for the parse-tree walker.
 240 **
 241 ** When this routine is the Walker.xExprCallback then expression trees
 242 ** are walked without any actions being taken at each node.  Presumably,
 243 ** when this routine is used for Walker.xExprCallback then
 244 ** Walker.xSelectCallback is set to do something useful for every
 245 ** subquery in the parser tree.
 246 */
 247 int sqlite3ExprWalkNoop(Walker *NotUsed, Expr *NotUsed2){
 248   UNUSED_PARAMETER2(NotUsed, NotUsed2);
 249   return WRC_Continue;
 250 }
 251
 252 /*
 253 ** No-op routine for the parse-tree walker for SELECT statements.
 254 ** subquery in the parser tree.
 255 */
 256 int sqlite3SelectWalkNoop(Walker *NotUsed, Select *NotUsed2){
 257   UNUSED_PARAMETER2(NotUsed, NotUsed2);
 258   return WRC_Continue;
 259 }