ext/misc/closure.c

   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 */
 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 */
 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 */
 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 */
 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 */
 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 */
 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 */
 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 */
 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 */
 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 */
 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 */
 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 */
 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 */
 424 static char *closureDequote(const char *zIn){
 425   int nIn;                        /* Size of input string, in bytes */
 426   char *zOut;                     /* Output (dequoted) string */
 427
 428   nIn = (int)strlen(zIn);
 429   zOut = sqlite3_malloc(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, 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 */
 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 */
 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 */
 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 */
 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 */
 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 */
 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 */
 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 */
 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 */
 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 */
 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 */
 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 */
 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 */
 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 */
 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   int seenMatch = 0;
 830   const struct sqlite3_index_constraint *pConstraint;
 831   closure_vtab *pVtab = (closure_vtab*)pTab;
 832   double rCost = 10000000.0;
 833
 834   pConstraint = pIdxInfo->aConstraint;
 835   for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
 836     if( pConstraint->iColumn==CLOSURE_COL_ROOT
 837      && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ ){
 838       seenMatch = 1;
 839     }
 840     if( pConstraint->usable==0 ) continue;
 841     if( (iPlan & 1)==0
 842      && pConstraint->iColumn==CLOSURE_COL_ROOT
 843      && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
 844     ){
 845       iPlan |= 1;
 846       pIdxInfo->aConstraintUsage[i].argvIndex = 1;
 847       pIdxInfo->aConstraintUsage[i].omit = 1;
 848       rCost /= 100.0;
 849     }
 850     if( (iPlan & 0x0000f0)==0
 851      && pConstraint->iColumn==CLOSURE_COL_DEPTH
 852      && (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT
 853            || pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE
 854            || pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ)
 855     ){
 856       iPlan |= idx<<4;
 857       pIdxInfo->aConstraintUsage[i].argvIndex = ++idx;
 858       if( pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT ) iPlan |= 0x000002;
 859       rCost /= 5.0;
 860     }
 861     if( (iPlan & 0x000f00)==0
 862      && pConstraint->iColumn==CLOSURE_COL_TABLENAME
 863      && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
 864     ){
 865       iPlan |= idx<<8;
 866       pIdxInfo->aConstraintUsage[i].argvIndex = ++idx;
 867       pIdxInfo->aConstraintUsage[i].omit = 1;
 868       rCost /= 5.0;
 869     }
 870     if( (iPlan & 0x00f000)==0
 871      && pConstraint->iColumn==CLOSURE_COL_IDCOLUMN
 872      && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
 873     ){
 874       iPlan |= idx<<12;
 875       pIdxInfo->aConstraintUsage[i].argvIndex = ++idx;
 876       pIdxInfo->aConstraintUsage[i].omit = 1;
 877     }
 878     if( (iPlan & 0x0f0000)==0
 879      && pConstraint->iColumn==CLOSURE_COL_PARENTCOLUMN
 880      && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
 881     ){
 882       iPlan |= idx<<16;
 883       pIdxInfo->aConstraintUsage[i].argvIndex = ++idx;
 884       pIdxInfo->aConstraintUsage[i].omit = 1;
 885     }
 886   }
 887   if( (pVtab->zTableName==0    && (iPlan & 0x000f00)==0)
 888    || (pVtab->zIdColumn==0     && (iPlan & 0x00f000)==0)
 889    || (pVtab->zParentColumn==0 && (iPlan & 0x0f0000)==0)
 890   ){
 891     /* All of tablename, idcolumn, and parentcolumn must be specified
 892     ** in either the CREATE VIRTUAL TABLE or in the WHERE clause constraints
 893     ** or else the result is an empty set. */
 894     iPlan = 0;
 895   }
 896   pIdxInfo->idxNum = iPlan;
 897   if( pIdxInfo->nOrderBy==1
 898    && pIdxInfo->aOrderBy[0].iColumn==CLOSURE_COL_ID
 899    && pIdxInfo->aOrderBy[0].desc==0
 900   ){
 901     pIdxInfo->orderByConsumed = 1;
 902   }
 903   if( seenMatch && (iPlan&1)==0 ) rCost *= 1e30;
 904   pIdxInfo->estimatedCost = rCost;
 905
 906   return SQLITE_OK;
 907 }
 908
 909 /*
 910 ** A virtual table module that implements the "transitive_closure".
 911 */
 912 static sqlite3_module closureModule = {
 913   0,                      /* iVersion */
 914   closureConnect,         /* xCreate */
 915   closureConnect,         /* xConnect */
 916   closureBestIndex,       /* xBestIndex */
 917   closureDisconnect,      /* xDisconnect */
 918   closureDisconnect,      /* xDestroy */
 919   closureOpen,            /* xOpen - open a cursor */
 920   closureClose,           /* xClose - close a cursor */
 921   closureFilter,          /* xFilter - configure scan constraints */
 922   closureNext,            /* xNext - advance a cursor */
 923   closureEof,             /* xEof - check for end of scan */
 924   closureColumn,          /* xColumn - read data */
 925   closureRowid,           /* xRowid - read data */
 926   0,                      /* xUpdate */
 927   0,                      /* xBegin */
 928   0,                      /* xSync */
 929   0,                      /* xCommit */
 930   0,                      /* xRollback */
 931   0,                      /* xFindMethod */
 932   0,                      /* xRename */
 933   0,                      /* xSavepoint */
 934   0,                      /* xRelease */
 935   0                       /* xRollbackTo */
 936 };
 937
 938 #endif /* SQLITE_OMIT_VIRTUALTABLE */
 939
 940 /*
 941 ** Register the closure virtual table
 942 */
 943 #ifdef _WIN32
 944 __declspec(dllexport)
 945 #endif
 946 int sqlite3_closure_init(
 947   sqlite3 *db,
 948   char **pzErrMsg,
 949   const sqlite3_api_routines *pApi
 950 ){
 951   int rc = SQLITE_OK;
 952   SQLITE_EXTENSION_INIT2(pApi);
 953   (void)pzErrMsg;
 954 #ifndef SQLITE_OMIT_VIRTUALTABLE
 955   rc = sqlite3_create_module(db, "transitive_closure", &closureModule, 0);
 956 #endif /* SQLITE_OMIT_VIRTUALTABLE */
 957   return rc;
 958 }