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 /*
  21 ** Walk an expression tree.  Invoke the callback once for each node
  22 ** of the expression, while decending.  (In other words, the callback
  23 ** is invoked before visiting children.)
  24 **
  25 ** The return value from the callback should be one of the WRC_*
  26 ** constants to specify how to proceed with the walk.
  27 **
  28 **    WRC_Continue      Continue descending down the tree.
  29 **
  30 **    WRC_Prune         Do not descend into child nodes.  But allow
  31 **                      the walk to continue with sibling nodes.
  32 **
  33 **    WRC_Abort         Do no more callbacks.  Unwind the stack and
  34 **                      return the top-level walk call.
  35 **
  36 ** The return value from this routine is WRC_Abort to abandon the tree walk
  37 ** and WRC_Continue to continue.
  38 */
  39 int sqlite3WalkExpr(Walker *pWalker, Expr *pExpr){
  40   int rc;
  41   if( pExpr==0 ) return WRC_Continue;
  42   testcase( ExprHasProperty(pExpr, EP_TokenOnly) );
  43   testcase( ExprHasProperty(pExpr, EP_Reduced) );
  44   rc = pWalker->xExprCallback(pWalker, pExpr);
  45   if( rc==WRC_Continue
  46               && !ExprHasAnyProperty(pExpr,EP_TokenOnly) ){
  47     if( sqlite3WalkExpr(pWalker, pExpr->pLeft) ) return WRC_Abort;
  48     if( sqlite3WalkExpr(pWalker, pExpr->pRight) ) return WRC_Abort;
  49     if( ExprHasProperty(pExpr, EP_xIsSelect) ){
  50       if( sqlite3WalkSelect(pWalker, pExpr->x.pSelect) ) return WRC_Abort;
  51     }else{
  52       if( sqlite3WalkExprList(pWalker, pExpr->x.pList) ) return WRC_Abort;
  53     }
  54   }
  55   return rc & WRC_Abort;
  56 }
  57
  58 /*
  59 ** Call sqlite3WalkExpr() for every expression in list p or until
  60 ** an abort request is seen.
  61 */
  62 int sqlite3WalkExprList(Walker *pWalker, ExprList *p){
  63   int i;
  64   struct ExprList_item *pItem;
  65   if( p ){
  66     for(i=p->nExpr, pItem=p->a; i>0; i--, pItem++){
  67       if( sqlite3WalkExpr(pWalker, pItem->pExpr) ) return WRC_Abort;
  68     }
  69   }
  70   return WRC_Continue;
  71 }
  72
  73 /*
  74 ** Walk all expressions associated with SELECT statement p.  Do
  75 ** not invoke the SELECT callback on p, but do (of course) invoke
  76 ** any expr callbacks and SELECT callbacks that come from subqueries.
  77 ** Return WRC_Abort or WRC_Continue.
  78 */
  79 int sqlite3WalkSelectExpr(Walker *pWalker, Select *p){
  80   if( sqlite3WalkExprList(pWalker, p->pEList) ) return WRC_Abort;
  81   if( sqlite3WalkExpr(pWalker, p->pWhere) ) return WRC_Abort;
  82   if( sqlite3WalkExprList(pWalker, p->pGroupBy) ) return WRC_Abort;
  83   if( sqlite3WalkExpr(pWalker, p->pHaving) ) return WRC_Abort;
  84   if( sqlite3WalkExprList(pWalker, p->pOrderBy) ) return WRC_Abort;
  85   if( sqlite3WalkExpr(pWalker, p->pLimit) ) return WRC_Abort;
  86   if( sqlite3WalkExpr(pWalker, p->pOffset) ) return WRC_Abort;
  87   return WRC_Continue;
  88 }
  89
  90 /*
  91 ** Walk the parse trees associated with all subqueries in the
  92 ** FROM clause of SELECT statement p.  Do not invoke the select
  93 ** callback on p, but do invoke it on each FROM clause subquery
  94 ** and on any subqueries further down in the tree.  Return
  95 ** WRC_Abort or WRC_Continue;
  96 */
  97 int sqlite3WalkSelectFrom(Walker *pWalker, Select *p){
  98   SrcList *pSrc;
  99   int i;
 100   struct SrcList_item *pItem;
 101
 102   pSrc = p->pSrc;
 103   if( ALWAYS(pSrc) ){
 104     for(i=pSrc->nSrc, pItem=pSrc->a; i>0; i--, pItem++){
 105       if( sqlite3WalkSelect(pWalker, pItem->pSelect) ){
 106         return WRC_Abort;
 107       }
 108     }
 109   }
 110   return WRC_Continue;
 111 }
 112
 113 /*
 114 ** Call sqlite3WalkExpr() for every expression in Select statement p.
 115 ** Invoke sqlite3WalkSelect() for subqueries in the FROM clause and
 116 ** on the compound select chain, p->pPrior.  Invoke the xSelectCallback()
 117 ** either before or after the walk of expressions and FROM clause, depending
 118 ** on whether pWalker->bSelectDepthFirst is false or true, respectively.
 119 **
 120 ** Return WRC_Continue under normal conditions.  Return WRC_Abort if
 121 ** there is an abort request.
 122 **
 123 ** If the Walker does not have an xSelectCallback() then this routine
 124 ** is a no-op returning WRC_Continue.
 125 */
 126 int sqlite3WalkSelect(Walker *pWalker, Select *p){
 127   int rc;
 128   if( p==0 || pWalker->xSelectCallback==0 ) return WRC_Continue;
 129   rc = WRC_Continue;
 130   pWalker->walkerDepth++;
 131   while( p ){
 132     if( !pWalker->bSelectDepthFirst ){
 133        rc = pWalker->xSelectCallback(pWalker, p);
 134        if( rc ) break;
 135     }
 136     if( sqlite3WalkSelectExpr(pWalker, p)
 137      || sqlite3WalkSelectFrom(pWalker, p)
 138     ){
 139       pWalker->walkerDepth--;
 140       return WRC_Abort;
 141     }
 142     if( pWalker->bSelectDepthFirst ){
 143       rc = pWalker->xSelectCallback(pWalker, p);
 144       /* Depth-first search is currently only used for
 145       ** selectAddSubqueryTypeInfo() and that routine always returns
 146       ** WRC_Continue (0).  So the following branch is never taken. */
 147       if( NEVER(rc) ) break;
 148     }
 149     p = p->pPrior;
 150   }
 151   pWalker->walkerDepth--;
 152   return rc & WRC_Abort;
 153 }