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*/
25static 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*/
64static 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}
96int 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*/
104int 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*/
119void 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*/
131int 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*/
164int 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*/
202int 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*/
225int sqlite3WalkerDepthIncrease(Walker *pWalker, Select *pSelect){
226 UNUSED_PARAMETER(pSelect);
227 pWalker->walkerDepth++;
228 return WRC_Continue;
229}
230void 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*/
245int 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*/
254int sqlite3SelectWalkNoop(Walker *NotUsed, Select *NotUsed2){
255 UNUSED_PARAMETER2(NotUsed, NotUsed2);
256 return WRC_Continue;
257}
258