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 | 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 | } |
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 | */ |
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 | */ |
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 | */ |
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 | */ |
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 | */ |
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 | */ |
225 | int sqlite3WalkerDepthIncrease(Walker *pWalker, Select *pSelect){ |
226 | UNUSED_PARAMETER(pSelect); |
227 | pWalker->walkerDepth++; |
228 | return WRC_Continue; |
229 | } |
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 | */ |
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 | */ |
254 | int sqlite3SelectWalkNoop(Walker *NotUsed, Select *NotUsed2){ |
255 | UNUSED_PARAMETER2(NotUsed, NotUsed2); |
256 | return WRC_Continue; |
257 | } |
258 | |