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