1 /*
2 ** 2013-04-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 **
13 ** This file contains code for a virtual table that finds the transitive
14 ** closure of a parent/child relationship in a real table. The virtual
15 ** table is called "transitive_closure".
16 **
17 ** A transitive_closure virtual table is created like this:
18 **
19 ** CREATE VIRTUAL TABLE x USING transitive_closure(
20 ** tablename=<tablename>, -- T
21 ** idcolumn=<columnname>, -- X
22 ** parentcolumn=<columnname> -- P
23 ** );
24 **
25 ** When it is created, the new transitive_closure table may be supplied
26 ** with default values for the name of a table T and columns T.X and T.P.
27 ** The T.X and T.P columns must contain integers. The ideal case is for
28 ** T.X to be the INTEGER PRIMARY KEY. The T.P column should reference
29 ** the T.X column. The row referenced by T.P is the parent of the current row.
30 **
31 ** The tablename, idcolumn, and parentcolumn supplied by the CREATE VIRTUAL
32 ** TABLE statement may be overridden in individual queries by including
33 ** terms like tablename='newtable', idcolumn='id2', or
34 ** parentcolumn='parent3' in the WHERE clause of the query.
35 **
36 ** For efficiency, it is essential that there be an index on the P column:
37 **
38 ** CREATE Tidx1 ON T(P)
39 **
40 ** Suppose a specific instance of the closure table is as follows:
41 **
42 ** CREATE VIRTUAL TABLE ct1 USING transitive_closure(
43 ** tablename='group',
44 ** idcolumn='groupId',
45 ** parentcolumn='parentId'
46 ** );
47 **
48 ** Such an instance of the transitive_closure virtual table would be
49 ** appropriate for walking a tree defined using a table like this, for example:
50 **
51 ** CREATE TABLE group(
52 ** groupId INTEGER PRIMARY KEY,
53 ** parentId INTEGER REFERENCES group
54 ** );
55 ** CREATE INDEX group_idx1 ON group(parentId);
56 **
57 ** The group table above would presumably have other application-specific
58 ** fields. The key point here is that rows of the group table form a
59 ** tree. The purpose of the ct1 virtual table is to easily extract
60 ** branches of that tree.
61 **
62 ** Once it has been created, the ct1 virtual table can be queried
63 ** as follows:
64 **
65 ** SELECT * FROM element
66 ** WHERE element.groupId IN (SELECT id FROM ct1 WHERE root=?1);
67 **
68 ** The above query will return all elements that are part of group ?1
69 ** or children of group ?1 or grand-children of ?1 and so forth for all
70 ** descendents of group ?1. The same query can be formulated as a join:
71 **
72 ** SELECT element.* FROM element, ct1
73 ** WHERE element.groupid=ct1.id
74 ** AND ct1.root=?1;
75 **
76 ** The depth of the transitive_closure (the number of generations of
77 ** parent/child relations to follow) can be limited by setting "depth"
78 ** column in the WHERE clause. So, for example, the following query
79 ** finds only children and grandchildren but no further descendents:
80 **
81 ** SELECT element.* FROM element, ct1
82 ** WHERE element.groupid=ct1.id
83 ** AND ct1.root=?1
84 ** AND ct1.depth<=2;
85 **
86 ** The "ct1.depth<=2" term could be a strict equality "ct1.depth=2" in
87 ** order to find only the grandchildren of ?1, not ?1 itself or the
88 ** children of ?1.
89 **
90 ** The root=?1 term must be supplied in WHERE clause or else the query
91 ** of the ct1 virtual table will return an empty set. The tablename,
92 ** idcolumn, and parentcolumn attributes can be overridden in the WHERE
93 ** clause if desired. So, for example, the ct1 table could be repurposed
94 ** to find ancestors rather than descendents by inverting the roles of
95 ** the idcolumn and parentcolumn:
96 **
97 ** SELECT element.* FROM element, ct1
98 ** WHERE element.groupid=ct1.id
99 ** AND ct1.root=?1
100 ** AND ct1.idcolumn='parentId'
101 ** AND ct1.parentcolumn='groupId';
102 **
103 ** Multiple calls to ct1 could be combined. For example, the following
104 ** query finds all elements that "cousins" of groupId ?1. That is to say
105 ** elements where the groupId is a grandchild of the grandparent of ?1.
106 ** (This definition of "cousins" also includes siblings and self.)
107 **
108 ** SELECT element.* FROM element, ct1
109 ** WHERE element.groupId=ct1.id
110 ** AND ct1.depth=2
111 ** AND ct1.root IN (SELECT id FROM ct1
112 ** WHERE root=?1
113 ** AND depth=2
114 ** AND idcolumn='parentId'
115 ** AND parentcolumn='groupId');
116 **
117 ** In our example, the group.groupId column is unique and thus the
118 ** subquery will return exactly one row. For that reason, the IN
119 ** operator could be replaced by "=" to get the same result. But
120 ** in the general case where the idcolumn is not unique, an IN operator
121 ** would be required for this kind of query.
122 **
123 ** Note that because the tablename, idcolumn, and parentcolumn can
124 ** all be specified in the query, it is possible for an application
125 ** to define a single transitive_closure virtual table for use on lots
126 ** of different hierarchy tables. One might say:
127 **
128 ** CREATE VIRTUAL TABLE temp.closure USING transitive_closure;
129 **
130 ** As each database connection is being opened. Then the application
131 ** would always have a "closure" virtual table handy to use for querying.
132 **
133 ** SELECT element.* FROM element, closure
134 ** WHERE element.groupid=ct1.id
135 ** AND closure.root=?1
136 ** AND closure.tablename='group'
137 ** AND closure.idname='groupId'
138 ** AND closure.parentname='parentId';
139 **
140 ** See the documentation at http://www.sqlite.org/loadext.html for information
141 ** on how to compile and use loadable extensions such as this one.
142 */
143 #include "sqlite3ext.h"
144 SQLITE_EXTENSION_INIT1
145 #include <stdlib.h>
146 #include <string.h>
147 #include <assert.h>
148 #include <stdio.h>
149 #include <ctype.h>
150
151 #ifndef SQLITE_OMIT_VIRTUALTABLE
152
153 /*
154 ** Forward declaration of objects used by this implementation
155 */
156 typedef struct closure_vtab closure_vtab;
157 typedef struct closure_cursor closure_cursor;
158 typedef struct closure_queue closure_queue;
159 typedef struct closure_avl closure_avl;
160
161 /*****************************************************************************
162 ** AVL Tree implementation
163 */
164 /*
165 ** Objects that want to be members of the AVL tree should embedded an
166 ** instance of this structure.
167 */
168 struct closure_avl {
169 sqlite3_int64 id; /* Id of this entry in the table */
170 int iGeneration; /* Which generation is this entry part of */
171 closure_avl *pList; /* A linked list of nodes */
172 closure_avl *pBefore; /* Other elements less than id */
173 closure_avl *pAfter; /* Other elements greater than id */
174 closure_avl *pUp; /* Parent element */
175 short int height; /* Height of this node. Leaf==1 */
176 short int imbalance; /* Height difference between pBefore and pAfter */
177 };
178
179 /* Recompute the closure_avl.height and closure_avl.imbalance fields for p.
180 ** Assume that the children of p have correct heights.
181 */
closureAvlRecomputeHeight(closure_avl * p)182 static void closureAvlRecomputeHeight(closure_avl *p){
183 short int hBefore = p->pBefore ? p->pBefore->height : 0;
184 short int hAfter = p->pAfter ? p->pAfter->height : 0;
185 p->imbalance = hBefore - hAfter; /* -: pAfter higher. +: pBefore higher */
186 p->height = (hBefore>hAfter ? hBefore : hAfter)+1;
187 }
188
189 /*
190 ** P B
191 ** / \ / \
192 ** B Z ==> X P
193 ** / \ / \
194 ** X Y Y Z
195 **
196 */
closureAvlRotateBefore(closure_avl * pP)197 static closure_avl *closureAvlRotateBefore(closure_avl *pP){
198 closure_avl *pB = pP->pBefore;
199 closure_avl *pY = pB->pAfter;
200 pB->pUp = pP->pUp;
201 pB->pAfter = pP;
202 pP->pUp = pB;
203 pP->pBefore = pY;
204 if( pY ) pY->pUp = pP;
205 closureAvlRecomputeHeight(pP);
206 closureAvlRecomputeHeight(pB);
207 return pB;
208 }
209
210 /*
211 ** P A
212 ** / \ / \
213 ** X A ==> P Z
214 ** / \ / \
215 ** Y Z X Y
216 **
217 */
closureAvlRotateAfter(closure_avl * pP)218 static closure_avl *closureAvlRotateAfter(closure_avl *pP){
219 closure_avl *pA = pP->pAfter;
220 closure_avl *pY = pA->pBefore;
221 pA->pUp = pP->pUp;
222 pA->pBefore = pP;
223 pP->pUp = pA;
224 pP->pAfter = pY;
225 if( pY ) pY->pUp = pP;
226 closureAvlRecomputeHeight(pP);
227 closureAvlRecomputeHeight(pA);
228 return pA;
229 }
230
231 /*
232 ** Return a pointer to the pBefore or pAfter pointer in the parent
233 ** of p that points to p. Or if p is the root node, return pp.
234 */
closureAvlFromPtr(closure_avl * p,closure_avl ** pp)235 static closure_avl **closureAvlFromPtr(closure_avl *p, closure_avl **pp){
236 closure_avl *pUp = p->pUp;
237 if( pUp==0 ) return pp;
238 if( pUp->pAfter==p ) return &pUp->pAfter;
239 return &pUp->pBefore;
240 }
241
242 /*
243 ** Rebalance all nodes starting with p and working up to the root.
244 ** Return the new root.
245 */
closureAvlBalance(closure_avl * p)246 static closure_avl *closureAvlBalance(closure_avl *p){
247 closure_avl *pTop = p;
248 closure_avl **pp;
249 while( p ){
250 closureAvlRecomputeHeight(p);
251 if( p->imbalance>=2 ){
252 closure_avl *pB = p->pBefore;
253 if( pB->imbalance<0 ) p->pBefore = closureAvlRotateAfter(pB);
254 pp = closureAvlFromPtr(p,&p);
255 p = *pp = closureAvlRotateBefore(p);
256 }else if( p->imbalance<=(-2) ){
257 closure_avl *pA = p->pAfter;
258 if( pA->imbalance>0 ) p->pAfter = closureAvlRotateBefore(pA);
259 pp = closureAvlFromPtr(p,&p);
260 p = *pp = closureAvlRotateAfter(p);
261 }
262 pTop = p;
263 p = p->pUp;
264 }
265 return pTop;
266 }
267
268 /* Search the tree rooted at p for an entry with id. Return a pointer
269 ** to the entry or return NULL.
270 */
closureAvlSearch(closure_avl * p,sqlite3_int64 id)271 static closure_avl *closureAvlSearch(closure_avl *p, sqlite3_int64 id){
272 while( p && id!=p->id ){
273 p = (id<p->id) ? p->pBefore : p->pAfter;
274 }
275 return p;
276 }
277
278 /* Find the first node (the one with the smallest key).
279 */
closureAvlFirst(closure_avl * p)280 static closure_avl *closureAvlFirst(closure_avl *p){
281 if( p ) while( p->pBefore ) p = p->pBefore;
282 return p;
283 }
284
285 /* Return the node with the next larger key after p.
286 */
closureAvlNext(closure_avl * p)287 closure_avl *closureAvlNext(closure_avl *p){
288 closure_avl *pPrev = 0;
289 while( p && p->pAfter==pPrev ){
290 pPrev = p;
291 p = p->pUp;
292 }
293 if( p && pPrev==0 ){
294 p = closureAvlFirst(p->pAfter);
295 }
296 return p;
297 }
298
299 /* Insert a new node pNew. Return NULL on success. If the key is not
300 ** unique, then do not perform the insert but instead leave pNew unchanged
301 ** and return a pointer to an existing node with the same key.
302 */
closureAvlInsert(closure_avl ** ppHead,closure_avl * pNew)303 static closure_avl *closureAvlInsert(
304 closure_avl **ppHead, /* Head of the tree */
305 closure_avl *pNew /* New node to be inserted */
306 ){
307 closure_avl *p = *ppHead;
308 if( p==0 ){
309 p = pNew;
310 pNew->pUp = 0;
311 }else{
312 while( p ){
313 if( pNew->id<p->id ){
314 if( p->pBefore ){
315 p = p->pBefore;
316 }else{
317 p->pBefore = pNew;
318 pNew->pUp = p;
319 break;
320 }
321 }else if( pNew->id>p->id ){
322 if( p->pAfter ){
323 p = p->pAfter;
324 }else{
325 p->pAfter = pNew;
326 pNew->pUp = p;
327 break;
328 }
329 }else{
330 return p;
331 }
332 }
333 }
334 pNew->pBefore = 0;
335 pNew->pAfter = 0;
336 pNew->height = 1;
337 pNew->imbalance = 0;
338 *ppHead = closureAvlBalance(p);
339 return 0;
340 }
341
342 /* Walk the tree can call xDestroy on each node
343 */
closureAvlDestroy(closure_avl * p,void (* xDestroy)(closure_avl *))344 static void closureAvlDestroy(closure_avl *p, void (*xDestroy)(closure_avl*)){
345 if( p ){
346 closureAvlDestroy(p->pBefore, xDestroy);
347 closureAvlDestroy(p->pAfter, xDestroy);
348 xDestroy(p);
349 }
350 }
351 /*
352 ** End of the AVL Tree implementation
353 ******************************************************************************/
354
355 /*
356 ** A closure virtual-table object
357 */
358 struct closure_vtab {
359 sqlite3_vtab base; /* Base class - must be first */
360 char *zDb; /* Name of database. (ex: "main") */
361 char *zSelf; /* Name of this virtual table */
362 char *zTableName; /* Name of table holding parent/child relation */
363 char *zIdColumn; /* Name of ID column of zTableName */
364 char *zParentColumn; /* Name of PARENT column in zTableName */
365 sqlite3 *db; /* The database connection */
366 int nCursor; /* Number of pending cursors */
367 };
368
369 /* A closure cursor object */
370 struct closure_cursor {
371 sqlite3_vtab_cursor base; /* Base class - must be first */
372 closure_vtab *pVtab; /* The virtual table this cursor belongs to */
373 char *zTableName; /* Name of table holding parent/child relation */
374 char *zIdColumn; /* Name of ID column of zTableName */
375 char *zParentColumn; /* Name of PARENT column in zTableName */
376 closure_avl *pCurrent; /* Current element of output */
377 closure_avl *pClosure; /* The complete closure tree */
378 };
379
380 /* A queue of AVL nodes */
381 struct closure_queue {
382 closure_avl *pFirst; /* Oldest node on the queue */
383 closure_avl *pLast; /* Youngest node on the queue */
384 };
385
386 /*
387 ** Add a node to the end of the queue
388 */
queuePush(closure_queue * pQueue,closure_avl * pNode)389 static void queuePush(closure_queue *pQueue, closure_avl *pNode){
390 pNode->pList = 0;
391 if( pQueue->pLast ){
392 pQueue->pLast->pList = pNode;
393 }else{
394 pQueue->pFirst = pNode;
395 }
396 pQueue->pLast = pNode;
397 }
398
399 /*
400 ** Extract the oldest element (the front element) from the queue.
401 */
queuePull(closure_queue * pQueue)402 static closure_avl *queuePull(closure_queue *pQueue){
403 closure_avl *p = pQueue->pFirst;
404 if( p ){
405 pQueue->pFirst = p->pList;
406 if( pQueue->pFirst==0 ) pQueue->pLast = 0;
407 }
408 return p;
409 }
410
411 /*
412 ** This function converts an SQL quoted string into an unquoted string
413 ** and returns a pointer to a buffer allocated using sqlite3_malloc()
414 ** containing the result. The caller should eventually free this buffer
415 ** using sqlite3_free.
416 **
417 ** Examples:
418 **
419 ** "abc" becomes abc
420 ** 'xyz' becomes xyz
421 ** [pqr] becomes pqr
422 ** `mno` becomes mno
423 */
closureDequote(const char * zIn)424 static char *closureDequote(const char *zIn){
425 sqlite3_int64 nIn; /* Size of input string, in bytes */
426 char *zOut; /* Output (dequoted) string */
427
428 nIn = strlen(zIn);
429 zOut = sqlite3_malloc64(nIn+1);
430 if( zOut ){
431 char q = zIn[0]; /* Quote character (if any ) */
432
433 if( q!='[' && q!= '\'' && q!='"' && q!='`' ){
434 memcpy(zOut, zIn, (size_t)(nIn+1));
435 }else{
436 int iOut = 0; /* Index of next byte to write to output */
437 int iIn; /* Index of next byte to read from input */
438
439 if( q=='[' ) q = ']';
440 for(iIn=1; iIn<nIn; iIn++){
441 if( zIn[iIn]==q ) iIn++;
442 zOut[iOut++] = zIn[iIn];
443 }
444 }
445 assert( (int)strlen(zOut)<=nIn );
446 }
447 return zOut;
448 }
449
450 /*
451 ** Deallocate an closure_vtab object
452 */
closureFree(closure_vtab * p)453 static void closureFree(closure_vtab *p){
454 if( p ){
455 sqlite3_free(p->zDb);
456 sqlite3_free(p->zSelf);
457 sqlite3_free(p->zTableName);
458 sqlite3_free(p->zIdColumn);
459 sqlite3_free(p->zParentColumn);
460 memset(p, 0, sizeof(*p));
461 sqlite3_free(p);
462 }
463 }
464
465 /*
466 ** xDisconnect/xDestroy method for the closure module.
467 */
closureDisconnect(sqlite3_vtab * pVtab)468 static int closureDisconnect(sqlite3_vtab *pVtab){
469 closure_vtab *p = (closure_vtab*)pVtab;
470 assert( p->nCursor==0 );
471 closureFree(p);
472 return SQLITE_OK;
473 }
474
475 /*
476 ** Check to see if the argument is of the form:
477 **
478 ** KEY = VALUE
479 **
480 ** If it is, return a pointer to the first character of VALUE.
481 ** If not, return NULL. Spaces around the = are ignored.
482 */
closureValueOfKey(const char * zKey,const char * zStr)483 static const char *closureValueOfKey(const char *zKey, const char *zStr){
484 int nKey = (int)strlen(zKey);
485 int nStr = (int)strlen(zStr);
486 int i;
487 if( nStr<nKey+1 ) return 0;
488 if( memcmp(zStr, zKey, nKey)!=0 ) return 0;
489 for(i=nKey; isspace((unsigned char)zStr[i]); i++){}
490 if( zStr[i]!='=' ) return 0;
491 i++;
492 while( isspace((unsigned char)zStr[i]) ){ i++; }
493 return zStr+i;
494 }
495
496 /*
497 ** xConnect/xCreate method for the closure module. Arguments are:
498 **
499 ** argv[0] -> module name ("transitive_closure")
500 ** argv[1] -> database name
501 ** argv[2] -> table name
502 ** argv[3...] -> arguments
503 */
closureConnect(sqlite3 * db,void * pAux,int argc,const char * const * argv,sqlite3_vtab ** ppVtab,char ** pzErr)504 static int closureConnect(
505 sqlite3 *db,
506 void *pAux,
507 int argc, const char *const*argv,
508 sqlite3_vtab **ppVtab,
509 char **pzErr
510 ){
511 int rc = SQLITE_OK; /* Return code */
512 closure_vtab *pNew = 0; /* New virtual table */
513 const char *zDb = argv[1];
514 const char *zVal;
515 int i;
516
517 (void)pAux;
518 *ppVtab = 0;
519 pNew = sqlite3_malloc( sizeof(*pNew) );
520 if( pNew==0 ) return SQLITE_NOMEM;
521 rc = SQLITE_NOMEM;
522 memset(pNew, 0, sizeof(*pNew));
523 pNew->db = db;
524 pNew->zDb = sqlite3_mprintf("%s", zDb);
525 if( pNew->zDb==0 ) goto closureConnectError;
526 pNew->zSelf = sqlite3_mprintf("%s", argv[2]);
527 if( pNew->zSelf==0 ) goto closureConnectError;
528 for(i=3; i<argc; i++){
529 zVal = closureValueOfKey("tablename", argv[i]);
530 if( zVal ){
531 sqlite3_free(pNew->zTableName);
532 pNew->zTableName = closureDequote(zVal);
533 if( pNew->zTableName==0 ) goto closureConnectError;
534 continue;
535 }
536 zVal = closureValueOfKey("idcolumn", argv[i]);
537 if( zVal ){
538 sqlite3_free(pNew->zIdColumn);
539 pNew->zIdColumn = closureDequote(zVal);
540 if( pNew->zIdColumn==0 ) goto closureConnectError;
541 continue;
542 }
543 zVal = closureValueOfKey("parentcolumn", argv[i]);
544 if( zVal ){
545 sqlite3_free(pNew->zParentColumn);
546 pNew->zParentColumn = closureDequote(zVal);
547 if( pNew->zParentColumn==0 ) goto closureConnectError;
548 continue;
549 }
550 *pzErr = sqlite3_mprintf("unrecognized argument: [%s]\n", argv[i]);
551 closureFree(pNew);
552 *ppVtab = 0;
553 return SQLITE_ERROR;
554 }
555 rc = sqlite3_declare_vtab(db,
556 "CREATE TABLE x(id,depth,root HIDDEN,tablename HIDDEN,"
557 "idcolumn HIDDEN,parentcolumn HIDDEN)"
558 );
559 #define CLOSURE_COL_ID 0
560 #define CLOSURE_COL_DEPTH 1
561 #define CLOSURE_COL_ROOT 2
562 #define CLOSURE_COL_TABLENAME 3
563 #define CLOSURE_COL_IDCOLUMN 4
564 #define CLOSURE_COL_PARENTCOLUMN 5
565 if( rc!=SQLITE_OK ){
566 closureFree(pNew);
567 }
568 *ppVtab = &pNew->base;
569 return rc;
570
571 closureConnectError:
572 closureFree(pNew);
573 return rc;
574 }
575
576 /*
577 ** Open a new closure cursor.
578 */
closureOpen(sqlite3_vtab * pVTab,sqlite3_vtab_cursor ** ppCursor)579 static int closureOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
580 closure_vtab *p = (closure_vtab*)pVTab;
581 closure_cursor *pCur;
582 pCur = sqlite3_malloc( sizeof(*pCur) );
583 if( pCur==0 ) return SQLITE_NOMEM;
584 memset(pCur, 0, sizeof(*pCur));
585 pCur->pVtab = p;
586 *ppCursor = &pCur->base;
587 p->nCursor++;
588 return SQLITE_OK;
589 }
590
591 /*
592 ** Free up all the memory allocated by a cursor. Set it rLimit to 0
593 ** to indicate that it is at EOF.
594 */
closureClearCursor(closure_cursor * pCur)595 static void closureClearCursor(closure_cursor *pCur){
596 closureAvlDestroy(pCur->pClosure, (void(*)(closure_avl*))sqlite3_free);
597 sqlite3_free(pCur->zTableName);
598 sqlite3_free(pCur->zIdColumn);
599 sqlite3_free(pCur->zParentColumn);
600 pCur->zTableName = 0;
601 pCur->zIdColumn = 0;
602 pCur->zParentColumn = 0;
603 pCur->pCurrent = 0;
604 pCur->pClosure = 0;
605 }
606
607 /*
608 ** Close a closure cursor.
609 */
closureClose(sqlite3_vtab_cursor * cur)610 static int closureClose(sqlite3_vtab_cursor *cur){
611 closure_cursor *pCur = (closure_cursor *)cur;
612 closureClearCursor(pCur);
613 pCur->pVtab->nCursor--;
614 sqlite3_free(pCur);
615 return SQLITE_OK;
616 }
617
618 /*
619 ** Advance a cursor to its next row of output
620 */
closureNext(sqlite3_vtab_cursor * cur)621 static int closureNext(sqlite3_vtab_cursor *cur){
622 closure_cursor *pCur = (closure_cursor*)cur;
623 pCur->pCurrent = closureAvlNext(pCur->pCurrent);
624 return SQLITE_OK;
625 }
626
627 /*
628 ** Allocate and insert a node
629 */
closureInsertNode(closure_queue * pQueue,closure_cursor * pCur,sqlite3_int64 id,int iGeneration)630 static int closureInsertNode(
631 closure_queue *pQueue, /* Add new node to this queue */
632 closure_cursor *pCur, /* The cursor into which to add the node */
633 sqlite3_int64 id, /* The node ID */
634 int iGeneration /* The generation number for this node */
635 ){
636 closure_avl *pNew = sqlite3_malloc( sizeof(*pNew) );
637 if( pNew==0 ) return SQLITE_NOMEM;
638 memset(pNew, 0, sizeof(*pNew));
639 pNew->id = id;
640 pNew->iGeneration = iGeneration;
641 closureAvlInsert(&pCur->pClosure, pNew);
642 queuePush(pQueue, pNew);
643 return SQLITE_OK;
644 }
645
646 /*
647 ** Called to "rewind" a cursor back to the beginning so that
648 ** it starts its output over again. Always called at least once
649 ** prior to any closureColumn, closureRowid, or closureEof call.
650 **
651 ** This routine actually computes the closure.
652 **
653 ** See the comment at the beginning of closureBestIndex() for a
654 ** description of the meaning of idxNum. The idxStr parameter is
655 ** not used.
656 */
closureFilter(sqlite3_vtab_cursor * pVtabCursor,int idxNum,const char * idxStr,int argc,sqlite3_value ** argv)657 static int closureFilter(
658 sqlite3_vtab_cursor *pVtabCursor,
659 int idxNum, const char *idxStr,
660 int argc, sqlite3_value **argv
661 ){
662 closure_cursor *pCur = (closure_cursor *)pVtabCursor;
663 closure_vtab *pVtab = pCur->pVtab;
664 sqlite3_int64 iRoot;
665 int mxGen = 999999999;
666 char *zSql;
667 sqlite3_stmt *pStmt;
668 closure_avl *pAvl;
669 int rc = SQLITE_OK;
670 const char *zTableName = pVtab->zTableName;
671 const char *zIdColumn = pVtab->zIdColumn;
672 const char *zParentColumn = pVtab->zParentColumn;
673 closure_queue sQueue;
674
675 (void)idxStr; /* Unused parameter */
676 (void)argc; /* Unused parameter */
677 closureClearCursor(pCur);
678 memset(&sQueue, 0, sizeof(sQueue));
679 if( (idxNum & 1)==0 ){
680 /* No root=$root in the WHERE clause. Return an empty set */
681 return SQLITE_OK;
682 }
683 iRoot = sqlite3_value_int64(argv[0]);
684 if( (idxNum & 0x000f0)!=0 ){
685 mxGen = sqlite3_value_int(argv[(idxNum>>4)&0x0f]);
686 if( (idxNum & 0x00002)!=0 ) mxGen--;
687 }
688 if( (idxNum & 0x00f00)!=0 ){
689 zTableName = (const char*)sqlite3_value_text(argv[(idxNum>>8)&0x0f]);
690 pCur->zTableName = sqlite3_mprintf("%s", zTableName);
691 }
692 if( (idxNum & 0x0f000)!=0 ){
693 zIdColumn = (const char*)sqlite3_value_text(argv[(idxNum>>12)&0x0f]);
694 pCur->zIdColumn = sqlite3_mprintf("%s", zIdColumn);
695 }
696 if( (idxNum & 0x0f0000)!=0 ){
697 zParentColumn = (const char*)sqlite3_value_text(argv[(idxNum>>16)&0x0f]);
698 pCur->zParentColumn = sqlite3_mprintf("%s", zParentColumn);
699 }
700
701 zSql = sqlite3_mprintf(
702 "SELECT \"%w\".\"%w\" FROM \"%w\" WHERE \"%w\".\"%w\"=?1",
703 zTableName, zIdColumn, zTableName, zTableName, zParentColumn);
704 if( zSql==0 ){
705 return SQLITE_NOMEM;
706 }else{
707 rc = sqlite3_prepare_v2(pVtab->db, zSql, -1, &pStmt, 0);
708 sqlite3_free(zSql);
709 if( rc ){
710 sqlite3_free(pVtab->base.zErrMsg);
711 pVtab->base.zErrMsg = sqlite3_mprintf("%s", sqlite3_errmsg(pVtab->db));
712 return rc;
713 }
714 }
715 if( rc==SQLITE_OK ){
716 rc = closureInsertNode(&sQueue, pCur, iRoot, 0);
717 }
718 while( (pAvl = queuePull(&sQueue))!=0 ){
719 if( pAvl->iGeneration>=mxGen ) continue;
720 sqlite3_bind_int64(pStmt, 1, pAvl->id);
721 while( rc==SQLITE_OK && sqlite3_step(pStmt)==SQLITE_ROW ){
722 if( sqlite3_column_type(pStmt,0)==SQLITE_INTEGER ){
723 sqlite3_int64 iNew = sqlite3_column_int64(pStmt, 0);
724 if( closureAvlSearch(pCur->pClosure, iNew)==0 ){
725 rc = closureInsertNode(&sQueue, pCur, iNew, pAvl->iGeneration+1);
726 }
727 }
728 }
729 sqlite3_reset(pStmt);
730 }
731 sqlite3_finalize(pStmt);
732 if( rc==SQLITE_OK ){
733 pCur->pCurrent = closureAvlFirst(pCur->pClosure);
734 }
735
736 return rc;
737 }
738
739 /*
740 ** Only the word and distance columns have values. All other columns
741 ** return NULL
742 */
closureColumn(sqlite3_vtab_cursor * cur,sqlite3_context * ctx,int i)743 static int closureColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
744 closure_cursor *pCur = (closure_cursor*)cur;
745 switch( i ){
746 case CLOSURE_COL_ID: {
747 sqlite3_result_int64(ctx, pCur->pCurrent->id);
748 break;
749 }
750 case CLOSURE_COL_DEPTH: {
751 sqlite3_result_int(ctx, pCur->pCurrent->iGeneration);
752 break;
753 }
754 case CLOSURE_COL_ROOT: {
755 sqlite3_result_null(ctx);
756 break;
757 }
758 case CLOSURE_COL_TABLENAME: {
759 sqlite3_result_text(ctx,
760 pCur->zTableName ? pCur->zTableName : pCur->pVtab->zTableName,
761 -1, SQLITE_TRANSIENT);
762 break;
763 }
764 case CLOSURE_COL_IDCOLUMN: {
765 sqlite3_result_text(ctx,
766 pCur->zIdColumn ? pCur->zIdColumn : pCur->pVtab->zIdColumn,
767 -1, SQLITE_TRANSIENT);
768 break;
769 }
770 case CLOSURE_COL_PARENTCOLUMN: {
771 sqlite3_result_text(ctx,
772 pCur->zParentColumn ? pCur->zParentColumn : pCur->pVtab->zParentColumn,
773 -1, SQLITE_TRANSIENT);
774 break;
775 }
776 }
777 return SQLITE_OK;
778 }
779
780 /*
781 ** The rowid. For the closure table, this is the same as the "id" column.
782 */
closureRowid(sqlite3_vtab_cursor * cur,sqlite_int64 * pRowid)783 static int closureRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
784 closure_cursor *pCur = (closure_cursor*)cur;
785 *pRowid = pCur->pCurrent->id;
786 return SQLITE_OK;
787 }
788
789 /*
790 ** EOF indicator
791 */
closureEof(sqlite3_vtab_cursor * cur)792 static int closureEof(sqlite3_vtab_cursor *cur){
793 closure_cursor *pCur = (closure_cursor*)cur;
794 return pCur->pCurrent==0;
795 }
796
797 /*
798 ** Search for terms of these forms:
799 **
800 ** (A) root = $root
801 ** (B1) depth < $depth
802 ** (B2) depth <= $depth
803 ** (B3) depth = $depth
804 ** (C) tablename = $tablename
805 ** (D) idcolumn = $idcolumn
806 ** (E) parentcolumn = $parentcolumn
807 **
808 **
809 **
810 ** idxNum meaning
811 ** ---------- ------------------------------------------------------
812 ** 0x00000001 Term of the form (A) found
813 ** 0x00000002 The term of bit-2 is like (B1)
814 ** 0x000000f0 Index in filter.argv[] of $depth. 0 if not used.
815 ** 0x00000f00 Index in filter.argv[] of $tablename. 0 if not used.
816 ** 0x0000f000 Index in filter.argv[] of $idcolumn. 0 if not used
817 ** 0x000f0000 Index in filter.argv[] of $parentcolumn. 0 if not used.
818 **
819 ** There must be a term of type (A). If there is not, then the index type
820 ** is 0 and the query will return an empty set.
821 */
closureBestIndex(sqlite3_vtab * pTab,sqlite3_index_info * pIdxInfo)822 static int closureBestIndex(
823 sqlite3_vtab *pTab, /* The virtual table */
824 sqlite3_index_info *pIdxInfo /* Information about the query */
825 ){
826 int iPlan = 0;
827 int i;
828 int idx = 1;
829 const struct sqlite3_index_constraint *pConstraint;
830 closure_vtab *pVtab = (closure_vtab*)pTab;
831 double rCost = 10000000.0;
832
833 pConstraint = pIdxInfo->aConstraint;
834 for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
835 if( pConstraint->usable==0 ) continue;
836 if( (iPlan & 1)==0
837 && pConstraint->iColumn==CLOSURE_COL_ROOT
838 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
839 ){
840 iPlan |= 1;
841 pIdxInfo->aConstraintUsage[i].argvIndex = 1;
842 pIdxInfo->aConstraintUsage[i].omit = 1;
843 rCost /= 100.0;
844 }
845 if( (iPlan & 0x0000f0)==0
846 && pConstraint->iColumn==CLOSURE_COL_DEPTH
847 && (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT
848 || pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE
849 || pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ)
850 ){
851 iPlan |= idx<<4;
852 pIdxInfo->aConstraintUsage[i].argvIndex = ++idx;
853 if( pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT ) iPlan |= 0x000002;
854 rCost /= 5.0;
855 }
856 if( (iPlan & 0x000f00)==0
857 && pConstraint->iColumn==CLOSURE_COL_TABLENAME
858 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
859 ){
860 iPlan |= idx<<8;
861 pIdxInfo->aConstraintUsage[i].argvIndex = ++idx;
862 pIdxInfo->aConstraintUsage[i].omit = 1;
863 rCost /= 5.0;
864 }
865 if( (iPlan & 0x00f000)==0
866 && pConstraint->iColumn==CLOSURE_COL_IDCOLUMN
867 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
868 ){
869 iPlan |= idx<<12;
870 pIdxInfo->aConstraintUsage[i].argvIndex = ++idx;
871 pIdxInfo->aConstraintUsage[i].omit = 1;
872 }
873 if( (iPlan & 0x0f0000)==0
874 && pConstraint->iColumn==CLOSURE_COL_PARENTCOLUMN
875 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
876 ){
877 iPlan |= idx<<16;
878 pIdxInfo->aConstraintUsage[i].argvIndex = ++idx;
879 pIdxInfo->aConstraintUsage[i].omit = 1;
880 }
881 }
882 if( (pVtab->zTableName==0 && (iPlan & 0x000f00)==0)
883 || (pVtab->zIdColumn==0 && (iPlan & 0x00f000)==0)
884 || (pVtab->zParentColumn==0 && (iPlan & 0x0f0000)==0)
885 ){
886 /* All of tablename, idcolumn, and parentcolumn must be specified
887 ** in either the CREATE VIRTUAL TABLE or in the WHERE clause constraints
888 ** or else the result is an empty set. */
889 iPlan = 0;
890 }
891 if( (iPlan&1)==0 ){
892 /* If there is no usable "root=?" term, then set the index-type to 0.
893 ** Also clear any argvIndex variables already set. This is necessary
894 ** to prevent the core from throwing an "xBestIndex malfunction error"
895 ** error (because the argvIndex values are not contiguously assigned
896 ** starting from 1). */
897 rCost *= 1e30;
898 for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
899 pIdxInfo->aConstraintUsage[i].argvIndex = 0;
900 }
901 iPlan = 0;
902 }
903 pIdxInfo->idxNum = iPlan;
904 if( pIdxInfo->nOrderBy==1
905 && pIdxInfo->aOrderBy[0].iColumn==CLOSURE_COL_ID
906 && pIdxInfo->aOrderBy[0].desc==0
907 ){
908 pIdxInfo->orderByConsumed = 1;
909 }
910 pIdxInfo->estimatedCost = rCost;
911
912 return SQLITE_OK;
913 }
914
915 /*
916 ** A virtual table module that implements the "transitive_closure".
917 */
918 static sqlite3_module closureModule = {
919 0, /* iVersion */
920 closureConnect, /* xCreate */
921 closureConnect, /* xConnect */
922 closureBestIndex, /* xBestIndex */
923 closureDisconnect, /* xDisconnect */
924 closureDisconnect, /* xDestroy */
925 closureOpen, /* xOpen - open a cursor */
926 closureClose, /* xClose - close a cursor */
927 closureFilter, /* xFilter - configure scan constraints */
928 closureNext, /* xNext - advance a cursor */
929 closureEof, /* xEof - check for end of scan */
930 closureColumn, /* xColumn - read data */
931 closureRowid, /* xRowid - read data */
932 0, /* xUpdate */
933 0, /* xBegin */
934 0, /* xSync */
935 0, /* xCommit */
936 0, /* xRollback */
937 0, /* xFindMethod */
938 0, /* xRename */
939 0, /* xSavepoint */
940 0, /* xRelease */
941 0, /* xRollbackTo */
942 0 /* xShadowName */
943 };
944
945 #endif /* SQLITE_OMIT_VIRTUALTABLE */
946
947 /*
948 ** Register the closure virtual table
949 */
950 #ifdef _WIN32
951 __declspec(dllexport)
952 #endif
sqlite3_closure_init(sqlite3 * db,char ** pzErrMsg,const sqlite3_api_routines * pApi)953 int sqlite3_closure_init(
954 sqlite3 *db,
955 char **pzErrMsg,
956 const sqlite3_api_routines *pApi
957 ){
958 int rc = SQLITE_OK;
959 SQLITE_EXTENSION_INIT2(pApi);
960 (void)pzErrMsg;
961 #ifndef SQLITE_OMIT_VIRTUALTABLE
962 rc = sqlite3_create_module(db, "transitive_closure", &closureModule, 0);
963 #endif /* SQLITE_OMIT_VIRTUALTABLE */
964 return rc;
965 }
966