ext/repair/checkindex.c

   1 /*
   2 ** 2017 October 27
   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
  14 #include "sqlite3ext.h"
  15 SQLITE_EXTENSION_INIT1
  16
  17 /*
  18 ** Stuff that is available inside the amalgamation, but which we need to
  19 ** declare ourselves if this module is compiled separately.
  20 */
  21 #ifndef SQLITE_AMALGAMATION
  22 # include <string.h>
  23 # include <stdio.h>
  24 # include <stdlib.h>
  25 # include <assert.h>
  26 typedef unsigned char u8;
  27 typedef unsigned short u16;
  28 typedef unsigned int u32;
  29 #define get4byte(x) (        \
  30     ((u32)((x)[0])<<24) +    \
  31     ((u32)((x)[1])<<16) +    \
  32     ((u32)((x)[2])<<8) +     \
  33     ((u32)((x)[3]))          \
  34 )
  35 #endif
  36
  37 typedef struct CidxTable CidxTable;
  38 typedef struct CidxCursor CidxCursor;
  39
  40 struct CidxTable {
  41   sqlite3_vtab base;              /* Base class.  Must be first */
  42   sqlite3 *db;
  43 };
  44
  45 struct CidxCursor {
  46   sqlite3_vtab_cursor base;       /* Base class.  Must be first */
  47   sqlite3_int64 iRowid;           /* Row number of the output */
  48   char *zIdxName;                 /* Copy of the index_name parameter */
  49   char *zAfterKey;                /* Copy of the after_key parameter */
  50   sqlite3_stmt *pStmt;            /* SQL statement that generates the output */
  51 };
  52
  53 typedef struct CidxColumn CidxColumn;
  54 struct CidxColumn {
  55   char *zExpr;                    /* Text for indexed expression */
  56   int bDesc;                      /* True for DESC columns, otherwise false */
  57   int bKey;                       /* Part of index, not PK */
  58 };
  59
  60 typedef struct CidxIndex CidxIndex;
  61 struct CidxIndex {
  62   char *zWhere;                   /* WHERE clause, if any */
  63   int nCol;                       /* Elements in aCol[] array */
  64   CidxColumn aCol[1];             /* Array of indexed columns */
  65 };
  66
  67 static void *cidxMalloc(int *pRc, int n){
  68   void *pRet = 0;
  69   assert( n!=0 );
  70   if( *pRc==SQLITE_OK ){
  71     pRet = sqlite3_malloc(n);
  72     if( pRet ){
  73       memset(pRet, 0, n);
  74     }else{
  75       *pRc = SQLITE_NOMEM;
  76     }
  77   }
  78   return pRet;
  79 }
  80
  81 static void cidxCursorError(CidxCursor *pCsr, const char *zFmt, ...){
  82   va_list ap;
  83   va_start(ap, zFmt);
  84   assert( pCsr->base.pVtab->zErrMsg==0 );
  85   pCsr->base.pVtab->zErrMsg = sqlite3_vmprintf(zFmt, ap);
  86   va_end(ap);
  87 }
  88
  89 /*
  90 ** Connect to the incremental_index_check virtual table.
  91 */
  92 static int cidxConnect(
  93   sqlite3 *db,
  94   void *pAux,
  95   int argc, const char *const*argv,
  96   sqlite3_vtab **ppVtab,
  97   char **pzErr
  98 ){
  99   int rc = SQLITE_OK;
 100   CidxTable *pRet;
 101
 102 #define IIC_ERRMSG        0
 103 #define IIC_CURRENT_KEY   1
 104 #define IIC_INDEX_NAME    2
 105 #define IIC_AFTER_KEY     3
 106 #define IIC_SCANNER_SQL   4
 107   rc = sqlite3_declare_vtab(db,
 108       "CREATE TABLE xyz("
 109       " errmsg TEXT,"            /* Error message or NULL if everything is ok */
 110       " current_key TEXT,"       /* SQLite quote() text of key values */
 111       " index_name HIDDEN,"      /* IN: name of the index being scanned */
 112       " after_key HIDDEN,"       /* IN: Start scanning after this key */
 113       " scanner_sql HIDDEN"      /* debuggingn info: SQL used for scanner */
 114       ")"
 115   );
 116   pRet = cidxMalloc(&rc, sizeof(CidxTable));
 117   if( pRet ){
 118     pRet->db = db;
 119   }
 120
 121   *ppVtab = (sqlite3_vtab*)pRet;
 122   return rc;
 123 }
 124
 125 /*
 126 ** Disconnect from or destroy an incremental_index_check virtual table.
 127 */
 128 static int cidxDisconnect(sqlite3_vtab *pVtab){
 129   CidxTable *pTab = (CidxTable*)pVtab;
 130   sqlite3_free(pTab);
 131   return SQLITE_OK;
 132 }
 133
 134 /*
 135 ** idxNum and idxStr are not used.  There are only three possible plans,
 136 ** which are all distinguished by the number of parameters.
 137 **
 138 **   No parameters:         A degenerate plan.  The result is zero rows.
 139 **   1 Parameter:           Scan all of the index starting with first entry
 140 **   2 parameters:          Scan the index starting after the "after_key".
 141 **
 142 ** Provide successively smaller costs for each of these plans to encourage
 143 ** the query planner to select the one with the most parameters.
 144 */
 145 static int cidxBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pInfo){
 146   int iIdxName = -1;
 147   int iAfterKey = -1;
 148   int i;
 149
 150   for(i=0; i<pInfo->nConstraint; i++){
 151     struct sqlite3_index_constraint *p = &pInfo->aConstraint[i];
 152     if( p->usable==0 ) continue;
 153     if( p->op!=SQLITE_INDEX_CONSTRAINT_EQ ) continue;
 154
 155     if( p->iColumn==IIC_INDEX_NAME ){
 156       iIdxName = i;
 157     }
 158     if( p->iColumn==IIC_AFTER_KEY ){
 159       iAfterKey = i;
 160     }
 161   }
 162
 163   if( iIdxName<0 ){
 164     pInfo->estimatedCost = 1000000000.0;
 165   }else{
 166     pInfo->aConstraintUsage[iIdxName].argvIndex = 1;
 167     pInfo->aConstraintUsage[iIdxName].omit = 1;
 168     if( iAfterKey<0 ){
 169       pInfo->estimatedCost = 1000000.0;
 170     }else{
 171       pInfo->aConstraintUsage[iAfterKey].argvIndex = 2;
 172       pInfo->aConstraintUsage[iAfterKey].omit = 1;
 173       pInfo->estimatedCost = 1000.0;
 174     }
 175   }
 176
 177   return SQLITE_OK;
 178 }
 179
 180 /*
 181 ** Open a new btreeinfo cursor.
 182 */
 183 static int cidxOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
 184   CidxCursor *pRet;
 185   int rc = SQLITE_OK;
 186
 187   pRet = cidxMalloc(&rc, sizeof(CidxCursor));
 188
 189   *ppCursor = (sqlite3_vtab_cursor*)pRet;
 190   return rc;
 191 }
 192
 193 /*
 194 ** Close a btreeinfo cursor.
 195 */
 196 static int cidxClose(sqlite3_vtab_cursor *pCursor){
 197   CidxCursor *pCsr = (CidxCursor*)pCursor;
 198   sqlite3_finalize(pCsr->pStmt);
 199   sqlite3_free(pCsr->zIdxName);
 200   sqlite3_free(pCsr->zAfterKey);
 201   sqlite3_free(pCsr);
 202   return SQLITE_OK;
 203 }
 204
 205 /*
 206 ** Move a btreeinfo cursor to the next entry in the file.
 207 */
 208 static int cidxNext(sqlite3_vtab_cursor *pCursor){
 209   CidxCursor *pCsr = (CidxCursor*)pCursor;
 210   int rc = sqlite3_step(pCsr->pStmt);
 211   if( rc!=SQLITE_ROW ){
 212     rc = sqlite3_finalize(pCsr->pStmt);
 213     pCsr->pStmt = 0;
 214     if( rc!=SQLITE_OK ){
 215       sqlite3 *db = ((CidxTable*)pCsr->base.pVtab)->db;
 216       cidxCursorError(pCsr, "Cursor error: %s", sqlite3_errmsg(db));
 217     }
 218   }else{
 219     pCsr->iRowid++;
 220     rc = SQLITE_OK;
 221   }
 222   return rc;
 223 }
 224
 225 /* We have reached EOF if previous sqlite3_step() returned
 226 ** anything other than SQLITE_ROW;
 227 */
 228 static int cidxEof(sqlite3_vtab_cursor *pCursor){
 229   CidxCursor *pCsr = (CidxCursor*)pCursor;
 230   return pCsr->pStmt==0;
 231 }
 232
 233 static char *cidxMprintf(int *pRc, const char *zFmt, ...){
 234   char *zRet = 0;
 235   va_list ap;
 236   va_start(ap, zFmt);
 237   zRet = sqlite3_vmprintf(zFmt, ap);
 238   if( *pRc==SQLITE_OK ){
 239     if( zRet==0 ){
 240       *pRc = SQLITE_NOMEM;
 241     }
 242   }else{
 243     sqlite3_free(zRet);
 244     zRet = 0;
 245   }
 246   va_end(ap);
 247   return zRet;
 248 }
 249
 250 static sqlite3_stmt *cidxPrepare(
 251   int *pRc, CidxCursor *pCsr, const char *zFmt, ...
 252 ){
 253   sqlite3_stmt *pRet = 0;
 254   char *zSql;
 255   va_list ap;                     /* ... printf arguments */
 256   va_start(ap, zFmt);
 257
 258   zSql = sqlite3_vmprintf(zFmt, ap);
 259   if( *pRc==SQLITE_OK ){
 260     if( zSql==0 ){
 261       *pRc = SQLITE_NOMEM;
 262     }else{
 263       sqlite3 *db = ((CidxTable*)pCsr->base.pVtab)->db;
 264       *pRc = sqlite3_prepare_v2(db, zSql, -1, &pRet, 0);
 265       if( *pRc!=SQLITE_OK ){
 266         cidxCursorError(pCsr, "SQL error: %s", sqlite3_errmsg(db));
 267       }
 268     }
 269   }
 270   sqlite3_free(zSql);
 271   va_end(ap);
 272
 273   return pRet;
 274 }
 275
 276 static void cidxFinalize(int *pRc, sqlite3_stmt *pStmt){
 277   int rc = sqlite3_finalize(pStmt);
 278   if( *pRc==SQLITE_OK ) *pRc = rc;
 279 }
 280
 281 char *cidxStrdup(int *pRc, const char *zStr){
 282   char *zRet = 0;
 283   if( *pRc==SQLITE_OK ){
 284     int n = (int)strlen(zStr);
 285     zRet = cidxMalloc(pRc, n+1);
 286     if( zRet ) memcpy(zRet, zStr, n+1);
 287   }
 288   return zRet;
 289 }
 290
 291 static void cidxFreeIndex(CidxIndex *pIdx){
 292   if( pIdx ){
 293     int i;
 294     for(i=0; i<pIdx->nCol; i++){
 295       sqlite3_free(pIdx->aCol[i].zExpr);
 296     }
 297     sqlite3_free(pIdx->zWhere);
 298     sqlite3_free(pIdx);
 299   }
 300 }
 301
 302 static int cidx_isspace(char c){
 303   return c==' ' || c=='\t' || c=='\r' || c=='\n';
 304 }
 305
 306 static int cidx_isident(char c){
 307   return c<0
 308     || (c>='0' && c<='9') || (c>='a' && c<='z')
 309     || (c>='A' && c<='Z') || c=='_';
 310 }
 311
 312 #define CIDX_PARSE_EOF   0
 313 #define CIDX_PARSE_COMMA 1      /*  "," */
 314 #define CIDX_PARSE_OPEN  2      /*  "(" */
 315 #define CIDX_PARSE_CLOSE 3      /*  ")" */
 316
 317 /*
 318 ** Argument zIn points into the start, middle or end of a CREATE INDEX
 319 ** statement. If argument pbDoNotTrim is non-NULL, then this function
 320 ** scans the input until it finds EOF, a comma (",") or an open or
 321 ** close parenthesis character. It then sets (*pzOut) to point to said
 322 ** character and returns a CIDX_PARSE_XXX constant as appropriate. The
 323 ** parser is smart enough that special characters inside SQL strings
 324 ** or comments are not returned for.
 325 **
 326 ** Or, if argument pbDoNotTrim is NULL, then this function sets *pzOut
 327 ** to point to the first character of the string that is not whitespace
 328 ** or part of an SQL comment and returns CIDX_PARSE_EOF.
 329 **
 330 ** Additionally, if pbDoNotTrim is not NULL and the element immediately
 331 ** before (*pzOut) is an SQL comment of the form "-- comment", then
 332 ** (*pbDoNotTrim) is set before returning. In all other cases it is
 333 ** cleared.
 334 */
 335 static int cidxFindNext(
 336   const char *zIn,
 337   const char **pzOut,
 338   int *pbDoNotTrim                /* OUT: True if prev is -- comment */
 339 ){
 340   const char *z = zIn;
 341
 342   while( 1 ){
 343     while( cidx_isspace(*z) ) z++;
 344     if( z[0]=='-' && z[1]=='-' ){
 345       z += 2;
 346       while( z[0]!='\n' ){
 347         if( z[0]=='\0' ) return CIDX_PARSE_EOF;
 348         z++;
 349       }
 350       while( cidx_isspace(*z) ) z++;
 351       if( pbDoNotTrim ) *pbDoNotTrim = 1;
 352     }else
 353     if( z[0]=='/' && z[1]=='*' ){
 354       z += 2;
 355       while( z[0]!='*' || z[1]!='/' ){
 356         if( z[1]=='\0' ) return CIDX_PARSE_EOF;
 357         z++;
 358       }
 359       z += 2;
 360     }else{
 361       *pzOut = z;
 362       if( pbDoNotTrim==0 ) return CIDX_PARSE_EOF;
 363       switch( *z ){
 364         case '\0':
 365           return CIDX_PARSE_EOF;
 366         case '(':
 367           return CIDX_PARSE_OPEN;
 368         case ')':
 369           return CIDX_PARSE_CLOSE;
 370         case ',':
 371           return CIDX_PARSE_COMMA;
 372
 373         case '"':
 374         case '\'':
 375         case '`': {
 376           char q = *z;
 377           z++;
 378           while( *z ){
 379             if( *z==q ){
 380               z++;
 381               if( *z!=q ) break;
 382             }
 383             z++;
 384           }
 385           break;
 386         }
 387
 388         case '[':
 389           while( *z++!=']' );
 390           break;
 391
 392         default:
 393           z++;
 394           break;
 395       }
 396       *pbDoNotTrim = 0;
 397     }
 398   }
 399
 400   assert( 0 );
 401   return -1;
 402 }
 403
 404 static int cidxParseSQL(CidxCursor *pCsr, CidxIndex *pIdx, const char *zSql){
 405   const char *z = zSql;
 406   const char *z1;
 407   int e;
 408   int rc = SQLITE_OK;
 409   int nParen = 1;
 410   int bDoNotTrim = 0;
 411   CidxColumn *pCol = pIdx->aCol;
 412
 413   e = cidxFindNext(z, &z, &bDoNotTrim);
 414   if( e!=CIDX_PARSE_OPEN ) goto parse_error;
 415   z1 = z+1;
 416   z++;
 417   while( nParen>0 ){
 418     e = cidxFindNext(z, &z, &bDoNotTrim);
 419     if( e==CIDX_PARSE_EOF ) goto parse_error;
 420     if( (e==CIDX_PARSE_COMMA || e==CIDX_PARSE_CLOSE) && nParen==1 ){
 421       const char *z2 = z;
 422       if( pCol->zExpr ) goto parse_error;
 423
 424       if( bDoNotTrim==0 ){
 425         while( cidx_isspace(z[-1]) ) z--;
 426         if( !sqlite3_strnicmp(&z[-3], "asc", 3) && 0==cidx_isident(z[-4]) ){
 427           z -= 3;
 428           while( cidx_isspace(z[-1]) ) z--;
 429         }else
 430           if( !sqlite3_strnicmp(&z[-4], "desc", 4) && 0==cidx_isident(z[-5]) ){
 431             z -= 4;
 432             while( cidx_isspace(z[-1]) ) z--;
 433           }
 434         while( cidx_isspace(z1[0]) ) z1++;
 435       }
 436
 437       pCol->zExpr = cidxMprintf(&rc, "%.*s", z-z1, z1);
 438       pCol++;
 439       z = z1 = z2+1;
 440     }
 441     if( e==CIDX_PARSE_OPEN ) nParen++;
 442     if( e==CIDX_PARSE_CLOSE ) nParen--;
 443     z++;
 444   }
 445
 446   /* Search for a WHERE clause */
 447   cidxFindNext(z, &z, 0);
 448   if( 0==sqlite3_strnicmp(z, "where", 5) ){
 449     pIdx->zWhere = cidxMprintf(&rc, "%s\n", &z[5]);
 450   }else if( z[0]!='\0' ){
 451     goto parse_error;
 452   }
 453
 454   return rc;
 455
 456  parse_error:
 457   cidxCursorError(pCsr, "Parse error in: %s", zSql);
 458   return SQLITE_ERROR;
 459 }
 460
 461 static int cidxLookupIndex(
 462   CidxCursor *pCsr,               /* Cursor object */
 463   const char *zIdx,               /* Name of index to look up */
 464   CidxIndex **ppIdx,              /* OUT: Description of columns */
 465   char **pzTab                    /* OUT: Table name */
 466 ){
 467   int rc = SQLITE_OK;
 468   char *zTab = 0;
 469   CidxIndex *pIdx = 0;
 470
 471   sqlite3_stmt *pFindTab = 0;
 472   sqlite3_stmt *pInfo = 0;
 473
 474   /* Find the table for this index. */
 475   pFindTab = cidxPrepare(&rc, pCsr,
 476       "SELECT tbl_name, sql FROM sqlite_schema WHERE name=%Q AND type='index'",
 477       zIdx
 478   );
 479   if( rc==SQLITE_OK && sqlite3_step(pFindTab)==SQLITE_ROW ){
 480     const char *zSql = (const char*)sqlite3_column_text(pFindTab, 1);
 481     zTab = cidxStrdup(&rc, (const char*)sqlite3_column_text(pFindTab, 0));
 482
 483     pInfo = cidxPrepare(&rc, pCsr, "PRAGMA index_xinfo(%Q)", zIdx);
 484     if( rc==SQLITE_OK ){
 485       int nAlloc = 0;
 486       int iCol = 0;
 487
 488       while( sqlite3_step(pInfo)==SQLITE_ROW ){
 489         const char *zName = (const char*)sqlite3_column_text(pInfo, 2);
 490         const char *zColl = (const char*)sqlite3_column_text(pInfo, 4);
 491         CidxColumn *p;
 492         if( zName==0 ) zName = "rowid";
 493         if( iCol==nAlloc ){
 494           int nByte = sizeof(CidxIndex) + sizeof(CidxColumn)*(nAlloc+8);
 495           pIdx = (CidxIndex*)sqlite3_realloc(pIdx, nByte);
 496           nAlloc += 8;
 497         }
 498         p = &pIdx->aCol[iCol++];
 499         p->bDesc = sqlite3_column_int(pInfo, 3);
 500         p->bKey = sqlite3_column_int(pInfo, 5);
 501         if( zSql==0 || p->bKey==0 ){
 502           p->zExpr = cidxMprintf(&rc, "\"%w\" COLLATE %s",zName,zColl);
 503         }else{
 504           p->zExpr = 0;
 505         }
 506         pIdx->nCol = iCol;
 507         pIdx->zWhere = 0;
 508       }
 509       cidxFinalize(&rc, pInfo);
 510     }
 511
 512     if( rc==SQLITE_OK && zSql ){
 513       rc = cidxParseSQL(pCsr, pIdx, zSql);
 514     }
 515   }
 516
 517   cidxFinalize(&rc, pFindTab);
 518   if( rc==SQLITE_OK && zTab==0 ){
 519     rc = SQLITE_ERROR;
 520   }
 521
 522   if( rc!=SQLITE_OK ){
 523     sqlite3_free(zTab);
 524     cidxFreeIndex(pIdx);
 525   }else{
 526     *pzTab = zTab;
 527     *ppIdx = pIdx;
 528   }
 529
 530   return rc;
 531 }
 532
 533 static int cidxDecodeAfter(
 534   CidxCursor *pCsr,
 535   int nCol,
 536   const char *zAfterKey,
 537   char ***pazAfter
 538 ){
 539   char **azAfter;
 540   int rc = SQLITE_OK;
 541   int nAfterKey = (int)strlen(zAfterKey);
 542
 543   azAfter = cidxMalloc(&rc, sizeof(char*)*nCol + nAfterKey+1);
 544   if( rc==SQLITE_OK ){
 545     int i;
 546     char *zCopy = (char*)&azAfter[nCol];
 547     char *p = zCopy;
 548     memcpy(zCopy, zAfterKey, nAfterKey+1);
 549     for(i=0; i<nCol; i++){
 550       while( *p==' ' ) p++;
 551
 552       /* Check NULL values */
 553       if( *p=='N' ){
 554         if( memcmp(p, "NULL", 4) ) goto parse_error;
 555         p += 4;
 556       }
 557
 558       /* Check strings and blob literals */
 559       else if( *p=='X' || *p=='\'' ){
 560         azAfter[i] = p;
 561         if( *p=='X' ) p++;
 562         if( *p!='\'' ) goto parse_error;
 563         p++;
 564         while( 1 ){
 565           if( *p=='\0' ) goto parse_error;
 566           if( *p=='\'' ){
 567             p++;
 568             if( *p!='\'' ) break;
 569           }
 570           p++;
 571         }
 572       }
 573
 574       /* Check numbers */
 575       else{
 576         azAfter[i] = p;
 577         while( (*p>='0' && *p<='9')
 578             || *p=='.' || *p=='+' || *p=='-' || *p=='e' || *p=='E'
 579         ){
 580           p++;
 581         }
 582       }
 583
 584       while( *p==' ' ) p++;
 585       if( *p!=(i==(nCol-1) ? '\0' : ',') ){
 586         goto parse_error;
 587       }
 588       *p++ = '\0';
 589     }
 590   }
 591
 592   *pazAfter = azAfter;
 593   return rc;
 594
 595  parse_error:
 596   sqlite3_free(azAfter);
 597   *pazAfter = 0;
 598   cidxCursorError(pCsr, "%s", "error parsing after value");
 599   return SQLITE_ERROR;
 600 }
 601
 602 static char *cidxWhere(
 603   int *pRc, CidxColumn *aCol, char **azAfter, int iGt, int bLastIsNull
 604 ){
 605   char *zRet = 0;
 606   const char *zSep = "";
 607   int i;
 608
 609   for(i=0; i<iGt; i++){
 610     zRet = cidxMprintf(pRc, "%z%s(%s) IS %s", zRet,
 611         zSep, aCol[i].zExpr, (azAfter[i] ? azAfter[i] : "NULL")
 612     );
 613     zSep = " AND ";
 614   }
 615
 616   if( bLastIsNull ){
 617     zRet = cidxMprintf(pRc, "%z%s(%s) IS NULL", zRet, zSep, aCol[iGt].zExpr);
 618   }
 619   else if( azAfter[iGt] ){
 620     zRet = cidxMprintf(pRc, "%z%s(%s) %s %s", zRet,
 621         zSep, aCol[iGt].zExpr, (aCol[iGt].bDesc ? "<" : ">"),
 622         azAfter[iGt]
 623     );
 624   }else{
 625     zRet = cidxMprintf(pRc, "%z%s(%s) IS NOT NULL", zRet, zSep,aCol[iGt].zExpr);
 626   }
 627
 628   return zRet;
 629 }
 630
 631 #define CIDX_CLIST_ALL         0
 632 #define CIDX_CLIST_ORDERBY     1
 633 #define CIDX_CLIST_CURRENT_KEY 2
 634 #define CIDX_CLIST_SUBWHERE    3
 635 #define CIDX_CLIST_SUBEXPR     4
 636
 637 /*
 638 ** This function returns various strings based on the contents of the
 639 ** CidxIndex structure and the eType parameter.
 640 */
 641 static char *cidxColumnList(
 642   int *pRc,                       /* IN/OUT: Error code */
 643   const char *zIdx,
 644   CidxIndex *pIdx,                /* Indexed columns */
 645   int eType                       /* True to include ASC/DESC */
 646 ){
 647   char *zRet = 0;
 648   if( *pRc==SQLITE_OK ){
 649     const char *aDir[2] = {"", " DESC"};
 650     int i;
 651     const char *zSep = "";
 652
 653     for(i=0; i<pIdx->nCol; i++){
 654       CidxColumn *p = &pIdx->aCol[i];
 655       assert( pIdx->aCol[i].bDesc==0 || pIdx->aCol[i].bDesc==1 );
 656       switch( eType ){
 657
 658         case CIDX_CLIST_ORDERBY:
 659           zRet = cidxMprintf(pRc, "%z%s%d%s", zRet, zSep, i+1, aDir[p->bDesc]);
 660           zSep = ",";
 661           break;
 662
 663         case CIDX_CLIST_CURRENT_KEY:
 664           zRet = cidxMprintf(pRc, "%z%squote(i%d)", zRet, zSep, i);
 665           zSep = "||','||";
 666           break;
 667
 668         case CIDX_CLIST_SUBWHERE:
 669           if( p->bKey==0 ){
 670             zRet = cidxMprintf(pRc, "%z%s%s IS i.i%d", zRet,
 671                 zSep, p->zExpr, i
 672             );
 673             zSep = " AND ";
 674           }
 675           break;
 676
 677         case CIDX_CLIST_SUBEXPR:
 678           if( p->bKey==1 ){
 679             zRet = cidxMprintf(pRc, "%z%s%s IS i.i%d", zRet,
 680                 zSep, p->zExpr, i
 681             );
 682             zSep = " AND ";
 683           }
 684           break;
 685
 686         default:
 687           assert( eType==CIDX_CLIST_ALL );
 688           zRet = cidxMprintf(pRc, "%z%s(%s) AS i%d", zRet, zSep, p->zExpr, i);
 689           zSep = ", ";
 690           break;
 691       }
 692     }
 693   }
 694
 695   return zRet;
 696 }
 697
 698 /*
 699 ** Generate SQL (in memory obtained from sqlite3_malloc()) that will
 700 ** continue the index scan for zIdxName starting after zAfterKey.
 701 */
 702 int cidxGenerateScanSql(
 703   CidxCursor *pCsr,           /* The cursor which needs the new statement */
 704   const char *zIdxName,       /* index to be scanned */
 705   const char *zAfterKey,      /* start after this key, if not NULL */
 706   char **pzSqlOut             /* OUT: Write the generated SQL here */
 707 ){
 708   int rc;
 709   char *zTab = 0;
 710   char *zCurrentKey = 0;
 711   char *zOrderBy = 0;
 712   char *zSubWhere = 0;
 713   char *zSubExpr = 0;
 714   char *zSrcList = 0;
 715   char **azAfter = 0;
 716   CidxIndex *pIdx = 0;
 717
 718   *pzSqlOut = 0;
 719   rc = cidxLookupIndex(pCsr, zIdxName, &pIdx, &zTab);
 720
 721   zOrderBy = cidxColumnList(&rc, zIdxName, pIdx, CIDX_CLIST_ORDERBY);
 722   zCurrentKey = cidxColumnList(&rc, zIdxName, pIdx, CIDX_CLIST_CURRENT_KEY);
 723   zSubWhere = cidxColumnList(&rc, zIdxName, pIdx, CIDX_CLIST_SUBWHERE);
 724   zSubExpr = cidxColumnList(&rc, zIdxName, pIdx, CIDX_CLIST_SUBEXPR);
 725   zSrcList = cidxColumnList(&rc, zIdxName, pIdx, CIDX_CLIST_ALL);
 726
 727   if( rc==SQLITE_OK && zAfterKey ){
 728     rc = cidxDecodeAfter(pCsr, pIdx->nCol, zAfterKey, &azAfter);
 729   }
 730
 731   if( rc==SQLITE_OK ){
 732     if( zAfterKey==0 ){
 733       *pzSqlOut = cidxMprintf(&rc,
 734           "SELECT (SELECT %s FROM %Q AS t WHERE %s), %s "
 735           "FROM (SELECT %s FROM %Q INDEXED BY %Q %s%sORDER BY %s) AS i",
 736           zSubExpr, zTab, zSubWhere, zCurrentKey,
 737           zSrcList, zTab, zIdxName,
 738           (pIdx->zWhere ? "WHERE " : ""), (pIdx->zWhere ? pIdx->zWhere : ""),
 739           zOrderBy
 740       );
 741     }else{
 742       const char *zSep = "";
 743       char *zSql;
 744       int i;
 745
 746       zSql = cidxMprintf(&rc,
 747           "SELECT (SELECT %s FROM %Q WHERE %s), %s FROM (",
 748           zSubExpr, zTab, zSubWhere, zCurrentKey
 749       );
 750       for(i=pIdx->nCol-1; i>=0; i--){
 751         int j;
 752         if( pIdx->aCol[i].bDesc && azAfter[i]==0 ) continue;
 753         for(j=0; j<2; j++){
 754           char *zWhere = cidxWhere(&rc, pIdx->aCol, azAfter, i, j);
 755           zSql = cidxMprintf(&rc, "%z"
 756               "%sSELECT * FROM ("
 757                 "SELECT %s FROM %Q INDEXED BY %Q WHERE %s%s%z ORDER BY %s"
 758               ")",
 759               zSql, zSep, zSrcList, zTab, zIdxName,
 760               pIdx->zWhere ? pIdx->zWhere : "",
 761               pIdx->zWhere ? " AND " : "",
 762               zWhere, zOrderBy
 763           );
 764           zSep = " UNION ALL ";
 765           if( pIdx->aCol[i].bDesc==0 ) break;
 766         }
 767       }
 768       *pzSqlOut = cidxMprintf(&rc, "%z) AS i", zSql);
 769     }
 770   }
 771
 772   sqlite3_free(zTab);
 773   sqlite3_free(zCurrentKey);
 774   sqlite3_free(zOrderBy);
 775   sqlite3_free(zSubWhere);
 776   sqlite3_free(zSubExpr);
 777   sqlite3_free(zSrcList);
 778   cidxFreeIndex(pIdx);
 779   sqlite3_free(azAfter);
 780   return rc;
 781 }
 782
 783
 784 /*
 785 ** Position a cursor back to the beginning.
 786 */
 787 static int cidxFilter(
 788   sqlite3_vtab_cursor *pCursor,
 789   int idxNum, const char *idxStr,
 790   int argc, sqlite3_value **argv
 791 ){
 792   int rc = SQLITE_OK;
 793   CidxCursor *pCsr = (CidxCursor*)pCursor;
 794   const char *zIdxName = 0;
 795   const char *zAfterKey = 0;
 796
 797   sqlite3_free(pCsr->zIdxName);
 798   pCsr->zIdxName = 0;
 799   sqlite3_free(pCsr->zAfterKey);
 800   pCsr->zAfterKey = 0;
 801   sqlite3_finalize(pCsr->pStmt);
 802   pCsr->pStmt = 0;
 803
 804   if( argc>0 ){
 805     zIdxName = (const char*)sqlite3_value_text(argv[0]);
 806     if( argc>1 ){
 807       zAfterKey = (const char*)sqlite3_value_text(argv[1]);
 808     }
 809   }
 810
 811   if( zIdxName ){
 812     char *zSql = 0;
 813     pCsr->zIdxName = sqlite3_mprintf("%s", zIdxName);
 814     pCsr->zAfterKey = zAfterKey ? sqlite3_mprintf("%s", zAfterKey) : 0;
 815     rc = cidxGenerateScanSql(pCsr, zIdxName, zAfterKey, &zSql);
 816     if( zSql ){
 817       pCsr->pStmt = cidxPrepare(&rc, pCsr, "%z", zSql);
 818     }
 819   }
 820
 821   if( pCsr->pStmt ){
 822     assert( rc==SQLITE_OK );
 823     rc = cidxNext(pCursor);
 824   }
 825   pCsr->iRowid = 1;
 826   return rc;
 827 }
 828
 829 /*
 830 ** Return a column value.
 831 */
 832 static int cidxColumn(
 833   sqlite3_vtab_cursor *pCursor,
 834   sqlite3_context *ctx,
 835   int iCol
 836 ){
 837   CidxCursor *pCsr = (CidxCursor*)pCursor;
 838   assert( iCol>=IIC_ERRMSG && iCol<=IIC_SCANNER_SQL );
 839   switch( iCol ){
 840     case IIC_ERRMSG: {
 841       const char *zVal = 0;
 842       if( sqlite3_column_type(pCsr->pStmt, 0)==SQLITE_INTEGER ){
 843         if( sqlite3_column_int(pCsr->pStmt, 0)==0 ){
 844           zVal = "row data mismatch";
 845         }
 846       }else{
 847         zVal = "row missing";
 848       }
 849       sqlite3_result_text(ctx, zVal, -1, SQLITE_STATIC);
 850       break;
 851     }
 852     case IIC_CURRENT_KEY: {
 853       sqlite3_result_value(ctx, sqlite3_column_value(pCsr->pStmt, 1));
 854       break;
 855     }
 856     case IIC_INDEX_NAME: {
 857       sqlite3_result_text(ctx, pCsr->zIdxName, -1, SQLITE_TRANSIENT);
 858       break;
 859     }
 860     case IIC_AFTER_KEY: {
 861       sqlite3_result_text(ctx, pCsr->zAfterKey, -1, SQLITE_TRANSIENT);
 862       break;
 863     }
 864     case IIC_SCANNER_SQL: {
 865       char *zSql = 0;
 866       cidxGenerateScanSql(pCsr, pCsr->zIdxName, pCsr->zAfterKey, &zSql);
 867       sqlite3_result_text(ctx, zSql, -1, sqlite3_free);
 868       break;
 869     }
 870   }
 871   return SQLITE_OK;
 872 }
 873
 874 /* Return the ROWID for the sqlite_btreeinfo table */
 875 static int cidxRowid(sqlite3_vtab_cursor *pCursor, sqlite_int64 *pRowid){
 876   CidxCursor *pCsr = (CidxCursor*)pCursor;
 877   *pRowid = pCsr->iRowid;
 878   return SQLITE_OK;
 879 }
 880
 881 /*
 882 ** Register the virtual table modules with the database handle passed
 883 ** as the only argument.
 884 */
 885 static int ciInit(sqlite3 *db){
 886   static sqlite3_module cidx_module = {
 887     0,                            /* iVersion */
 888     0,                            /* xCreate */
 889     cidxConnect,                  /* xConnect */
 890     cidxBestIndex,                /* xBestIndex */
 891     cidxDisconnect,               /* xDisconnect */
 892     0,                            /* xDestroy */
 893     cidxOpen,                     /* xOpen - open a cursor */
 894     cidxClose,                    /* xClose - close a cursor */
 895     cidxFilter,                   /* xFilter - configure scan constraints */
 896     cidxNext,                     /* xNext - advance a cursor */
 897     cidxEof,                      /* xEof - check for end of scan */
 898     cidxColumn,                   /* xColumn - read data */
 899     cidxRowid,                    /* xRowid - read data */
 900     0,                            /* xUpdate */
 901     0,                            /* xBegin */
 902     0,                            /* xSync */
 903     0,                            /* xCommit */
 904     0,                            /* xRollback */
 905     0,                            /* xFindMethod */
 906     0,                            /* xRename */
 907     0,                            /* xSavepoint */
 908     0,                            /* xRelease */
 909     0,                            /* xRollbackTo */
 910     0,                            /* xShadowName */
 911     0                             /* xIntegrity */
 912   };
 913   return sqlite3_create_module(db, "incremental_index_check", &cidx_module, 0);
 914 }
 915
 916 /*
 917 ** Extension load function.
 918 */
 919 #ifdef _WIN32
 920 __declspec(dllexport)
 921 #endif
 922 int sqlite3_checkindex_init(
 923   sqlite3 *db,
 924   char **pzErrMsg,
 925   const sqlite3_api_routines *pApi
 926 ){
 927   SQLITE_EXTENSION_INIT2(pApi);
 928   return ciInit(db);
 929 }