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     if( sqlite3WalkExprList(pWalker, pWin->pOrderBy) ) return WRC_Abort;
  29     if( sqlite3WalkExprList(pWalker, pWin->pPartition) ) return WRC_Abort;
  30     if( sqlite3WalkExpr(pWalker, pWin->pFilter) ) return WRC_Abort;
  31   }
  32   return WRC_Continue;
  33 }
  34 #endif
  35
  36 /*
  37 ** Walk an expression tree.  Invoke the callback once for each node
  38 ** of the expression, while descending.  (In other words, the callback
  39 ** is invoked before visiting children.)
  40 **
  41 ** The return value from the callback should be one of the WRC_*
  42 ** constants to specify how to proceed with the walk.
  43 **
  44 **    WRC_Continue      Continue descending down the tree.
  45 **
  46 **    WRC_Prune         Do not descend into child nodes, but allow
  47 **                      the walk to continue with sibling nodes.
  48 **
  49 **    WRC_Abort         Do no more callbacks.  Unwind the stack and
  50 **                      return from the top-level walk call.
  51 **
  52 ** The return value from this routine is WRC_Abort to abandon the tree walk
  53 ** and WRC_Continue to continue.
  54 */
  55 static SQLITE_NOINLINE int walkExpr(Walker *pWalker, Expr *pExpr){
  56   int rc;
  57   testcase( ExprHasProperty(pExpr, EP_TokenOnly) );
  58   testcase( ExprHasProperty(pExpr, EP_Reduced) );
  59   while(1){
  60     rc = pWalker->xExprCallback(pWalker, pExpr);
  61     if( rc ) return rc & WRC_Abort;
  62     if( !ExprHasProperty(pExpr,(EP_TokenOnly|EP_Leaf)) ){
  63       if( pExpr->pLeft && walkExpr(pWalker, pExpr->pLeft) ) return WRC_Abort;
  64        assert( pExpr->x.pList==0 || pExpr->pRight==0 );
  65       if( pExpr->pRight ){
  66         pExpr = pExpr->pRight;
  67         continue;
  68       }else if( ExprHasProperty(pExpr, EP_xIsSelect) ){
  69         if( sqlite3WalkSelect(pWalker, pExpr->x.pSelect) ) return WRC_Abort;
  70       }else if( pExpr->x.pList ){
  71         if( sqlite3WalkExprList(pWalker, pExpr->x.pList) ) return WRC_Abort;
  72       }
  73 #ifndef SQLITE_OMIT_WINDOWFUNC
  74       if( ExprHasProperty(pExpr, EP_WinFunc) ){
  75         if( walkWindowList(pWalker, pExpr->y.pWin) ) return WRC_Abort;
  76       }
  77 #endif
  78     }
  79     break;
  80   }
  81   return WRC_Continue;
  82 }
  83 int sqlite3WalkExpr(Walker *pWalker, Expr *pExpr){
  84   return pExpr ? walkExpr(pWalker,pExpr) : WRC_Continue;
  85 }
  86
  87 /*
  88 ** Call sqlite3WalkExpr() for every expression in list p or until
  89 ** an abort request is seen.
  90 */
  91 int sqlite3WalkExprList(Walker *pWalker, ExprList *p){
  92   int i;
  93   struct ExprList_item *pItem;
  94   if( p ){
  95     for(i=p->nExpr, pItem=p->a; i>0; i--, pItem++){
  96       if( sqlite3WalkExpr(pWalker, pItem->pExpr) ) return WRC_Abort;
  97     }
  98   }
  99   return WRC_Continue;
 100 }
 101
 102 /*
 103 ** Walk all expressions associated with SELECT statement p.  Do
 104 ** not invoke the SELECT callback on p, but do (of course) invoke
 105 ** any expr callbacks and SELECT callbacks that come from subqueries.
 106 ** Return WRC_Abort or WRC_Continue.
 107 */
 108 int sqlite3WalkSelectExpr(Walker *pWalker, Select *p){
 109   if( sqlite3WalkExprList(pWalker, p->pEList) ) return WRC_Abort;
 110   if( sqlite3WalkExpr(pWalker, p->pWhere) ) return WRC_Abort;
 111   if( sqlite3WalkExprList(pWalker, p->pGroupBy) ) return WRC_Abort;
 112   if( sqlite3WalkExpr(pWalker, p->pHaving) ) return WRC_Abort;
 113   if( sqlite3WalkExprList(pWalker, p->pOrderBy) ) return WRC_Abort;
 114   if( sqlite3WalkExpr(pWalker, p->pLimit) ) return WRC_Abort;
 115 #if !defined(SQLITE_OMIT_WINDOWFUNC) && !defined(SQLITE_OMIT_ALTERTABLE)
 116   {
 117     Parse *pParse = pWalker->pParse;
 118     if( pParse && IN_RENAME_OBJECT ){
 119       int rc = walkWindowList(pWalker, p->pWinDefn);
 120       assert( rc==WRC_Continue );
 121       return rc;
 122     }
 123   }
 124 #endif
 125   return WRC_Continue;
 126 }
 127
 128 /*
 129 ** Walk the parse trees associated with all subqueries in the
 130 ** FROM clause of SELECT statement p.  Do not invoke the select
 131 ** callback on p, but do invoke it on each FROM clause subquery
 132 ** and on any subqueries further down in the tree.  Return
 133 ** WRC_Abort or WRC_Continue;
 134 */
 135 int sqlite3WalkSelectFrom(Walker *pWalker, Select *p){
 136   SrcList *pSrc;
 137   int i;
 138   struct SrcList_item *pItem;
 139
 140   pSrc = p->pSrc;
 141   assert( pSrc!=0 );
 142   for(i=pSrc->nSrc, pItem=pSrc->a; i>0; i--, pItem++){
 143     if( pItem->pSelect && sqlite3WalkSelect(pWalker, pItem->pSelect) ){
 144       return WRC_Abort;
 145     }
 146     if( pItem->fg.isTabFunc
 147      && sqlite3WalkExprList(pWalker, pItem->u1.pFuncArg)
 148     ){
 149       return WRC_Abort;
 150     }
 151   }
 152   return WRC_Continue;
 153 }
 154
 155 /*
 156 ** Call sqlite3WalkExpr() for every expression in Select statement p.
 157 ** Invoke sqlite3WalkSelect() for subqueries in the FROM clause and
 158 ** on the compound select chain, p->pPrior.
 159 **
 160 ** If it is not NULL, the xSelectCallback() callback is invoked before
 161 ** the walk of the expressions and FROM clause. The xSelectCallback2()
 162 ** method is invoked following the walk of the expressions and FROM clause,
 163 ** but only if both xSelectCallback and xSelectCallback2 are both non-NULL
 164 ** and if the expressions and FROM clause both return WRC_Continue;
 165 **
 166 ** Return WRC_Continue under normal conditions.  Return WRC_Abort if
 167 ** there is an abort request.
 168 **
 169 ** If the Walker does not have an xSelectCallback() then this routine
 170 ** is a no-op returning WRC_Continue.
 171 */
 172 int sqlite3WalkSelect(Walker *pWalker, Select *p){
 173   int rc;
 174   if( p==0 ) return WRC_Continue;
 175   if( pWalker->xSelectCallback==0 ) return WRC_Continue;
 176   do{
 177     rc = pWalker->xSelectCallback(pWalker, p);
 178     if( rc ) return rc & WRC_Abort;
 179     if( sqlite3WalkSelectExpr(pWalker, p)
 180      || sqlite3WalkSelectFrom(pWalker, p)
 181     ){
 182       return WRC_Abort;
 183     }
 184     if( pWalker->xSelectCallback2 ){
 185       pWalker->xSelectCallback2(pWalker, p);
 186     }
 187     p = p->pPrior;
 188   }while( p!=0 );
 189   return WRC_Continue;
 190 }