/ Check-in [47a9f3cc]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Begin adding query support to fts5.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | fts5
Files: files | file ages | folders
SHA1:47a9f3cc92deefe163108e3507bd4614bf1f5da7
User & Date: dan 2014-06-25 20:28:38
Context
2014-06-26
12:31
Fix minor problems in term matching. check-in: 94eeb077 user: dan tags: fts5
2014-06-25
20:28
Begin adding query support to fts5. check-in: 47a9f3cc user: dan tags: fts5
2014-06-24
16:59
Add simple full-table-scan and rowid lookup support to fts5. check-in: 3515da85 user: dan tags: fts5
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/fts5/fts5.c.

    14     14   */
    15     15   
    16     16   #include "fts5Int.h"
    17     17   
    18     18   typedef struct Fts5Table Fts5Table;
    19     19   typedef struct Fts5Cursor Fts5Cursor;
    20     20   
           21  +/*
           22  +** Virtual-table object.
           23  +*/
    21     24   struct Fts5Table {
    22     25     sqlite3_vtab base;              /* Base class used by SQLite core */
    23     26     Fts5Config *pConfig;            /* Virtual table configuration */
    24     27     Fts5Index *pIndex;              /* Full-text index */
    25     28     Fts5Storage *pStorage;          /* Document store */
    26     29   };
    27     30   
           31  +/*
           32  +** Virtual-table cursor object.
           33  +*/
    28     34   struct Fts5Cursor {
    29     35     sqlite3_vtab_cursor base;       /* Base class used by SQLite core */
    30     36     int idxNum;                     /* idxNum passed to xFilter() */
    31     37     sqlite3_stmt *pStmt;            /* Statement used to read %_content */
    32     38     int bEof;                       /* True at EOF */
           39  +  Fts5Expr *pExpr;                /* Expression for MATCH queries */
           40  +  int bSeekRequired;
    33     41   };
    34     42   
    35     43   /*
    36     44   ** Close a virtual table handle opened by fts5InitVtab(). If the bDestroy
    37     45   ** argument is non-zero, attempt delete the shadow tables from teh database
    38     46   */
    39     47   static int fts5FreeVtab(Fts5Table *pTab, int bDestroy){
................................................................................
   161    169   #define FTS5_PLAN_ROWID   3       /* (rowid = ?) */
   162    170   
   163    171   #define FTS5_PLAN(idxNum) ((idxNum) & 0x7)
   164    172   
   165    173   #define FTS5_ORDER_DESC   8       /* ORDER BY rowid DESC */
   166    174   #define FTS5_ORDER_ASC   16       /* ORDER BY rowid ASC */
   167    175   
   168         -
          176  +/*
          177  +** Search the object passed as the first argument for a usable constraint
          178  +** on column iCol using operator eOp. If one is found, return its index in
          179  +** the pInfo->aConstraint[] array. If no such constraint is found, return
          180  +** a negative value.
          181  +*/
   169    182   static int fts5FindConstraint(sqlite3_index_info *pInfo, int eOp, int iCol){
   170    183     int i;
   171         -
   172    184     for(i=0; i<pInfo->nConstraint; i++){
   173    185       struct sqlite3_index_constraint *p = &pInfo->aConstraint[i];
   174    186       if( p->usable && p->iColumn==iCol && p->op==eOp ) return i;
   175    187     }
   176         -
   177    188     return -1;
   178    189   }
   179    190   
   180    191   /* 
   181    192   ** Implementation of the xBestIndex method for FTS5 tables. There
   182    193   ** are three possible strategies, in order of preference:
   183    194   **
................................................................................
   249    260   static int fts5CloseMethod(sqlite3_vtab_cursor *pCursor){
   250    261     Fts5Table *pTab = (Fts5Table*)(pCursor->pVtab);
   251    262     Fts5Cursor *pCsr = (Fts5Cursor*)pCursor;
   252    263     if( pCsr->pStmt ){
   253    264       int eStmt = fts5StmtType(pCsr->idxNum);
   254    265       sqlite3Fts5StorageStmtRelease(pTab->pStorage, eStmt, pCsr->pStmt);
   255    266     }
          267  +  sqlite3Fts5ExprFree(pCsr->pExpr);
   256    268     sqlite3_free(pCsr);
   257    269     return SQLITE_OK;
   258    270   }
   259    271   
   260    272   
   261    273   /*
   262    274   ** Advance the cursor to the next row in the table that matches the 
................................................................................
   267    279   ** subsequently to determine whether or not an EOF was hit.
   268    280   */
   269    281   static int fts5NextMethod(sqlite3_vtab_cursor *pCursor){
   270    282     Fts5Cursor *pCsr = (Fts5Cursor*)pCursor;
   271    283     int ePlan = FTS5_PLAN(pCsr->idxNum);
   272    284     int rc = SQLITE_OK;
   273    285   
   274         -  assert( ePlan!=FTS5_PLAN_MATCH );
   275    286     if( ePlan!=FTS5_PLAN_MATCH ){
   276    287       rc = sqlite3_step(pCsr->pStmt);
   277    288       if( rc!=SQLITE_ROW ){
   278    289         pCsr->bEof = 1;
   279    290         rc = sqlite3_reset(pCsr->pStmt);
   280    291       }else{
   281    292         rc = SQLITE_OK;
   282    293       }
          294  +  }else{
          295  +    rc = sqlite3Fts5ExprNext(pCsr->pExpr);
          296  +    pCsr->bEof = sqlite3Fts5ExprEof(pCsr->pExpr);
          297  +    pCsr->bSeekRequired = 1;
   283    298     }
   284    299     
   285    300     return rc;
   286    301   }
   287    302   
   288    303   /*
   289    304   ** This is the xFilter interface for the virtual table.  See
................................................................................
   298    313     sqlite3_value **apVal           /* Arguments for the indexing scheme */
   299    314   ){
   300    315     Fts5Table *pTab = (Fts5Table*)(pCursor->pVtab);
   301    316     Fts5Cursor *pCsr = (Fts5Cursor*)pCursor;
   302    317     int rc = SQLITE_OK;
   303    318     int ePlan = FTS5_PLAN(idxNum);
   304    319     int eStmt = fts5StmtType(idxNum);
          320  +  int bAsc = ((idxNum & FTS5_ORDER_ASC) ? 1 : 0);
   305    321   
   306         -  assert( ePlan!=FTS5_PLAN_MATCH );
   307    322     memset(&pCursor[1], 0, sizeof(Fts5Cursor) - sizeof(sqlite3_vtab_cursor));
   308    323     pCsr->idxNum = idxNum;
   309    324   
   310    325     rc = sqlite3Fts5StorageStmt(pTab->pStorage, eStmt, &pCsr->pStmt);
   311         -  if( ePlan==FTS5_PLAN_ROWID ){
   312         -    sqlite3_bind_value(pCsr->pStmt, 1, apVal[0]);
          326  +  if( rc==SQLITE_OK ){
          327  +    if( ePlan==FTS5_PLAN_MATCH ){
          328  +      char **pzErr = &pTab->base.zErrMsg;
          329  +      const char *zExpr = (const char*)sqlite3_value_text(apVal[0]);
          330  +      rc = sqlite3Fts5ExprNew(pTab->pConfig, zExpr, &pCsr->pExpr, pzErr);
          331  +      if( rc==SQLITE_OK ){
          332  +        rc = sqlite3Fts5ExprFirst(pCsr->pExpr, pTab->pIndex, bAsc);
          333  +        pCsr->bEof = sqlite3Fts5ExprEof(pCsr->pExpr);
          334  +        pCsr->bSeekRequired = 1;
          335  +      }
          336  +    }else{
          337  +      if( ePlan==FTS5_PLAN_ROWID ){
          338  +        sqlite3_bind_value(pCsr->pStmt, 1, apVal[0]);
          339  +      }
          340  +      rc = fts5NextMethod(pCursor);
          341  +    }
   313    342     }
   314    343   
   315         -  if( rc==SQLITE_OK ){
   316         -    rc = fts5NextMethod(pCursor);
   317         -  }
   318    344     return rc;
   319    345   }
   320    346   
   321    347   /* 
   322    348   ** This is the xEof method of the virtual table. SQLite calls this 
   323    349   ** routine to find out if it has reached the end of a result set.
   324    350   */
................................................................................
   334    360   ** rowid should be written to *pRowid.
   335    361   */
   336    362   static int fts5RowidMethod(sqlite3_vtab_cursor *pCursor, sqlite_int64 *pRowid){
   337    363     Fts5Cursor *pCsr = (Fts5Cursor*)pCursor;
   338    364     int ePlan = FTS5_PLAN(pCsr->idxNum);
   339    365     
   340    366     assert( pCsr->bEof==0 );
   341         -  assert( ePlan!=FTS5_PLAN_MATCH );
   342         -
   343    367     if( ePlan!=FTS5_PLAN_MATCH ){
   344    368       *pRowid = sqlite3_column_int64(pCsr->pStmt, 0);
          369  +  }else{
          370  +    *pRowid = sqlite3Fts5ExprRowid(pCsr->pExpr);
   345    371     }
   346    372   
   347    373     return SQLITE_OK;
   348    374   }
   349    375   
   350    376   /* 
   351    377   ** This is the xColumn method, called by SQLite to request a value from
................................................................................
   354    380   static int fts5ColumnMethod(
   355    381     sqlite3_vtab_cursor *pCursor,   /* Cursor to retrieve value from */
   356    382     sqlite3_context *pCtx,          /* Context for sqlite3_result_xxx() calls */
   357    383     int iCol                        /* Index of column to read value from */
   358    384   ){
   359    385     Fts5Cursor *pCsr = (Fts5Cursor*)pCursor;
   360    386     int ePlan = FTS5_PLAN(pCsr->idxNum);
          387  +  int rc = SQLITE_OK;
   361    388     
   362    389     assert( pCsr->bEof==0 );
   363         -  assert( ePlan!=FTS5_PLAN_MATCH );
   364         -  if( ePlan!=FTS5_PLAN_MATCH ){
          390  +  if( pCsr->bSeekRequired ){
          391  +    assert( ePlan==FTS5_PLAN_MATCH && pCsr->pExpr );
          392  +    sqlite3_reset(pCsr->pStmt);
          393  +    sqlite3_bind_int64(pCsr->pStmt, 1, sqlite3Fts5ExprRowid(pCsr->pExpr));
          394  +    rc = sqlite3_step(pCsr->pStmt);
          395  +    if( rc==SQLITE_ROW ){
          396  +      rc = SQLITE_OK;
          397  +    }else{
          398  +      rc = sqlite3_reset(pCsr->pStmt);
          399  +      if( rc==SQLITE_OK ){
          400  +        rc = SQLITE_CORRUPT_VTAB;
          401  +      }
          402  +    }
          403  +  }
          404  +
          405  +  if( rc==SQLITE_OK ){
   365    406       sqlite3_result_value(pCtx, sqlite3_column_value(pCsr->pStmt, iCol+1));
   366    407     }
   367         -  return SQLITE_OK;
          408  +  return rc;
   368    409   }
   369    410   
   370    411   /*
   371    412   ** This function is called to handle an FTS INSERT command. In other words,
   372    413   ** an INSERT statement of the form:
   373    414   **
   374    415   **     INSERT INTO fts(fts) VALUES($pVal)

Changes to ext/fts5/fts5Int.h.

    70     70   /**************************************************************************
    71     71   ** Interface to code in fts5_index.c. fts5_index.c contains contains code
    72     72   ** to access the data stored in the %_data table.
    73     73   */
    74     74   
    75     75   typedef struct Fts5Index Fts5Index;
    76     76   typedef struct Fts5IndexIter Fts5IndexIter;
           77  +
    77     78   
    78     79   /*
    79     80   ** Values used as part of the flags argument passed to IndexQuery().
    80     81   */
    81     82   #define FTS5INDEX_QUERY_PREFIX 0x0001       /* Prefix query */
    82     83   #define FTS5INDEX_QUERY_ASC    0x0002       /* Docs in ascending rowid order */
    83     84   #define FTS5INDEX_QUERY_MATCH  0x0004       /* Use the iMatch arg to Next() */
    84         -#define FTS5INDEX_QUERY_DELETE 0x0008       /* Visit delete markers */
    85     85   
    86     86   /*
    87     87   ** Create/destroy an Fts5Index object.
    88     88   */
    89     89   int sqlite3Fts5IndexOpen(Fts5Config *pConfig, int bCreate, Fts5Index**, char**);
    90     90   int sqlite3Fts5IndexClose(Fts5Index *p, int bDestroy);
    91     91   
................................................................................
   110    110   );
   111    111   
   112    112   /*
   113    113   ** Docid list iteration.
   114    114   */
   115    115   int  sqlite3Fts5IterEof(Fts5IndexIter*);
   116    116   void sqlite3Fts5IterNext(Fts5IndexIter*, i64 iMatch);
   117         -int sqlite3Fts5IterSeek(Fts5IndexIter*, i64 iDocid);
   118         -i64  sqlite3Fts5IterDocid(Fts5IndexIter*);
          117  +i64  sqlite3Fts5IterRowid(Fts5IndexIter*);
   119    118   
   120    119   /*
   121    120   ** Position list iteration.
   122    121   **
   123    122   **   for(
   124    123   **     iPos=sqlite3Fts5IterFirstPos(pIter, iCol); 
   125    124   **     iPos>=0; 
   126    125   **     iPos=sqlite3Fts5IterNextPos(pIter)
   127    126   **   ){
   128    127   **     // token appears at position iPos of column iCol of the current document
   129    128   **   }
   130    129   */
   131         -int sqlite3Fts5IterFirstPos(Fts5IndexIter*, int iCol);
   132         -int sqlite3Fts5IterNextPos(Fts5IndexIter*);
          130  +// int sqlite3Fts5IterFirstPos(Fts5IndexIter*, int iCol);
          131  +// int sqlite3Fts5IterNextPos(Fts5IndexIter*);
   133    132   
   134    133   /*
   135    134   ** Close an iterator opened by sqlite3Fts5IndexQuery().
   136    135   */
   137    136   void sqlite3Fts5IterClose(Fts5IndexIter*);
   138    137   
   139    138   /*
................................................................................
   209    208   ** End of interface to code in fts5_index.c.
   210    209   **************************************************************************/
   211    210   
   212    211   /**************************************************************************
   213    212   ** Interface to code in fts5_storage.c. fts5_storage.c contains contains 
   214    213   ** code to access the data stored in the %_content and %_docsize tables.
   215    214   */
          215  +
          216  +#define FTS5_STMT_SCAN_ASC  0     /* SELECT rowid, * FROM ... ORDER BY 1 ASC */
          217  +#define FTS5_STMT_SCAN_DESC 1     /* SELECT rowid, * FROM ... ORDER BY 1 DESC */
          218  +#define FTS5_STMT_LOOKUP    2     /* SELECT rowid, * FROM ... WHERE rowid=? */
          219  +
   216    220   typedef struct Fts5Storage Fts5Storage;
   217    221   
   218    222   int sqlite3Fts5StorageOpen(Fts5Config*, Fts5Index*, int, Fts5Storage**, char**);
   219    223   int sqlite3Fts5StorageClose(Fts5Storage *p, int bDestroy);
   220    224   
   221    225   int sqlite3Fts5DropTable(Fts5Config*, const char *zPost);
   222    226   int sqlite3Fts5CreateTable(Fts5Config*, const char*, const char*, char **pzErr);
   223    227   
   224    228   int sqlite3Fts5StorageDelete(Fts5Storage *p, i64);
   225    229   int sqlite3Fts5StorageInsert(Fts5Storage *p, sqlite3_value **apVal, int, i64*);
   226    230   
   227    231   int sqlite3Fts5StorageIntegrity(Fts5Storage *p);
   228    232   
   229         -#define FTS5_STMT_SCAN_ASC  0     /* SELECT rowid, * FROM ... ORDER BY 1 ASC */
   230         -#define FTS5_STMT_SCAN_DESC 1     /* SELECT rowid, * FROM ... ORDER BY 1 DESC */
   231         -#define FTS5_STMT_LOOKUP    2     /* SELECT rowid, * FROM ... WHERE rowid=? */
   232         -
   233    233   int sqlite3Fts5StorageStmt(Fts5Storage *p, int eStmt, sqlite3_stmt **);
   234    234   void sqlite3Fts5StorageStmtRelease(Fts5Storage *p, int eStmt, sqlite3_stmt*);
   235         -
   236    235   
   237    236   
   238    237   /*
   239    238   ** End of interface to code in fts5_storage.c.
   240    239   **************************************************************************/
   241    240   
   242    241   
   243    242   /**************************************************************************
   244    243   ** Interface to code in fts5_expr.c. 
   245    244   */
   246    245   typedef struct Fts5Expr Fts5Expr;
          246  +typedef struct Fts5ExprNode Fts5ExprNode;
   247    247   typedef struct Fts5Parse Fts5Parse;
   248    248   typedef struct Fts5Token Fts5Token;
   249    249   typedef struct Fts5ExprPhrase Fts5ExprPhrase;
   250    250   typedef struct Fts5ExprNearset Fts5ExprNearset;
   251    251   
   252    252   struct Fts5Token {
   253    253     const char *p;                  /* Token text (not NULL terminated) */
   254    254     int n;                          /* Size of buffer p in bytes */
   255    255   };
   256    256   
          257  +/* Parse a MATCH expression. */
   257    258   int sqlite3Fts5ExprNew(
   258    259     Fts5Config *pConfig, 
   259         -  Fts5Index *pIdx, 
   260    260     const char *zExpr,
   261    261     Fts5Expr **ppNew, 
   262    262     char **pzErr
   263    263   );
   264    264   
   265         -int sqlite3Fts5ExprFirst(Fts5Expr *p);
   266         -int sqlite3Fts5ExprNext(Fts5Expr *p);
   267         -int sqlite3Fts5ExprEof(Fts5Expr *p);
   268         -i64 sqlite3Fts5ExprRowid(Fts5Expr *p);
          265  +/*
          266  +** for(rc = sqlite3Fts5ExprFirst(pExpr, pIdx, bAsc);
          267  +**     rc==SQLITE_OK && 0==sqlite3Fts5ExprEof(pExpr);
          268  +**     rc = sqlite3Fts5ExprNext(pExpr)
          269  +** ){
          270  +**   // The document with rowid iRowid matches the expression!
          271  +**   i64 iRowid = sqlite3Fts5ExprRowid(pExpr);
          272  +** }
          273  +*/
          274  +int sqlite3Fts5ExprFirst(Fts5Expr*, Fts5Index *pIdx, int bAsc);
          275  +int sqlite3Fts5ExprNext(Fts5Expr*);
          276  +int sqlite3Fts5ExprEof(Fts5Expr*);
          277  +i64 sqlite3Fts5ExprRowid(Fts5Expr*);
   269    278   
   270         -void sqlite3Fts5ExprFree(Fts5Expr *p);
   271         -
   272         -// int sqlite3Fts5IterFirstPos(Fts5Expr*, int iCol, int *piPos);
   273         -// int sqlite3Fts5IterNextPos(Fts5Expr*, int *piPos);
          279  +void sqlite3Fts5ExprFree(Fts5Expr*);
   274    280   
   275    281   /* Called during startup to register a UDF with SQLite */
   276    282   int sqlite3Fts5ExprInit(sqlite3*);
   277    283   
   278    284   /*******************************************
   279    285   ** The fts5_expr.c API above this point is used by the other hand-written
   280    286   ** C code in this module. The interfaces below this point are called by
   281    287   ** the parser code in fts5parse.y.  */
   282    288   
   283    289   void sqlite3Fts5ParseError(Fts5Parse *pParse, const char *zFmt, ...);
   284    290   
   285         -Fts5Expr *sqlite3Fts5ParseExpr(
   286         -  Fts5Parse *pParse, 
   287         -  int eType, 
   288         -  Fts5Expr *pLeft, 
   289         -  Fts5Expr *pRight, 
          291  +Fts5ExprNode *sqlite3Fts5ParseNode(
          292  +  Fts5Parse *pParse,
          293  +  int eType,
          294  +  Fts5ExprNode *pLeft,
          295  +  Fts5ExprNode *pRight,
   290    296     Fts5ExprNearset *pNear
   291    297   );
   292    298   
   293    299   Fts5ExprPhrase *sqlite3Fts5ParseTerm(
   294    300     Fts5Parse *pParse, 
   295    301     Fts5ExprPhrase *pPhrase, 
   296    302     Fts5Token *pToken,
................................................................................
   301    307     Fts5Parse*, 
   302    308     Fts5ExprNearset*,
   303    309     Fts5ExprPhrase* 
   304    310   );
   305    311   
   306    312   void sqlite3Fts5ParsePhraseFree(Fts5ExprPhrase*);
   307    313   void sqlite3Fts5ParseNearsetFree(Fts5ExprNearset*);
          314  +void sqlite3Fts5ParseNodeFree(Fts5ExprNode*);
   308    315   
   309    316   void sqlite3Fts5ParseSetDistance(Fts5Parse*, Fts5ExprNearset*, Fts5Token*);
   310    317   void sqlite3Fts5ParseSetColumn(Fts5Parse*, Fts5ExprNearset*, Fts5Token*);
   311         -void sqlite3Fts5ParseFinished(Fts5Parse *pParse, Fts5Expr *p);
          318  +void sqlite3Fts5ParseFinished(Fts5Parse *pParse, Fts5ExprNode *p);
   312    319   void sqlite3Fts5ParseNear(Fts5Parse *pParse, Fts5Token*);
   313    320   
   314    321   
   315    322   /*
   316    323   ** End of interface to code in fts5_expr.c.
   317    324   **************************************************************************/
   318    325   
   319    326   #endif

Changes to ext/fts5/fts5_expr.c.

    25     25   /*
    26     26   ** Functions generated by lemon from fts5parse.y.
    27     27   */
    28     28   void *sqlite3Fts5ParserAlloc(void *(*mallocProc)(size_t));
    29     29   void sqlite3Fts5ParserFree(void*, void (*freeProc)(void*));
    30     30   void sqlite3Fts5Parser(void*, int, Fts5Token, Fts5Parse*);
    31     31   
           32  +struct Fts5Expr {
           33  +  Fts5Index *pIndex;
           34  +  Fts5ExprNode *pRoot;
           35  +  int bAsc;
           36  +};
           37  +
    32     38   /*
    33     39   ** eType:
    34     40   **   Expression node type. Always one of:
    35     41   **
    36     42   **       FTS5_AND                 (pLeft, pRight valid)
    37     43   **       FTS5_OR                  (pLeft, pRight valid)
    38     44   **       FTS5_NOT                 (pLeft, pRight valid)
    39     45   **       FTS5_STRING              (pNear valid)
    40     46   */
    41         -struct Fts5Expr {
           47  +struct Fts5ExprNode {
    42     48     int eType;                      /* Node type */
    43         -  Fts5Expr *pLeft;                /* Left hand child node */
    44         -  Fts5Expr *pRight;               /* Right hand child node */
           49  +  Fts5ExprNode *pLeft;            /* Left hand child node */
           50  +  Fts5ExprNode *pRight;           /* Right hand child node */
    45     51     Fts5ExprNearset *pNear;         /* For FTS5_STRING - cluster of phrases */
           52  +  int bEof;                       /* True at EOF */
           53  +  i64 iRowid;
    46     54   };
    47     55   
    48     56   /*
    49     57   ** An instance of the following structure represents a single search term
    50     58   ** or term prefix.
    51     59   */
    52     60   struct Fts5ExprTerm {
    53     61     int bPrefix;                    /* True for a prefix term */
    54     62     char *zTerm;                    /* nul-terminated term */
           63  +  Fts5IndexIter *pIter;           /* Iterator for this term */
    55     64   };
    56     65   
    57     66   /*
    58     67   ** A phrase. One or more terms that must appear in a contiguous sequence
    59     68   ** within a document for it to match.
    60     69   */
    61     70   struct Fts5ExprPhrase {
................................................................................
    78     87   /*
    79     88   ** Parse context.
    80     89   */
    81     90   struct Fts5Parse {
    82     91     Fts5Config *pConfig;
    83     92     char *zErr;
    84     93     int rc;
    85         -  Fts5Expr *pExpr;                /* Result of a successful parse */
           94  +  Fts5ExprNode *pExpr;            /* Result of a successful parse */
    86     95   };
    87     96   
    88     97   void sqlite3Fts5ParseError(Fts5Parse *pParse, const char *zFmt, ...){
    89     98     if( pParse->rc==SQLITE_OK ){
    90     99       va_list ap;
    91    100       va_start(ap, zFmt);
    92    101       pParse->zErr = sqlite3_vmprintf(zFmt, ap);
................................................................................
   164    173     return tok;
   165    174   }
   166    175   
   167    176   static void *fts5ParseAlloc(size_t t){ return sqlite3_malloc((int)t); }
   168    177   static void fts5ParseFree(void *p){ sqlite3_free(p); }
   169    178   
   170    179   int sqlite3Fts5ExprNew(
   171         -  Fts5Config *pConfig, 
   172         -  Fts5Index *pIdx, 
          180  +  Fts5Config *pConfig,            /* FTS5 Configuration */
   173    181     const char *zExpr,              /* Expression text */
   174    182     Fts5Expr **ppNew, 
   175    183     char **pzErr
   176    184   ){
   177    185     Fts5Parse sParse;
   178    186     Fts5Token token;
   179    187     const char *z = zExpr;
   180    188     int t;                          /* Next token type */
   181    189     void *pEngine;
          190  +  Fts5Expr *pNew;
   182    191   
   183    192     *ppNew = 0;
   184    193     *pzErr = 0;
   185    194     memset(&sParse, 0, sizeof(sParse));
   186    195     pEngine = sqlite3Fts5ParserAlloc(fts5ParseAlloc);
   187         -  if( pEngine==0 ) return SQLITE_NOMEM;
          196  +  if( pEngine==0 ){ return SQLITE_NOMEM; }
   188    197     sParse.pConfig = pConfig;
   189    198   
   190    199     do {
   191    200       t = fts5ExprGetToken(&sParse, &z, &token);
   192    201       sqlite3Fts5Parser(pEngine, t, token, &sParse);
   193    202     }while( sParse.rc==SQLITE_OK && t!=FTS5_EOF );
   194    203     sqlite3Fts5ParserFree(pEngine, fts5ParseFree);
   195    204   
   196    205     assert( sParse.pExpr==0 || (sParse.rc==SQLITE_OK && sParse.zErr==0) );
   197         -  *ppNew = sParse.pExpr;
          206  +  if( sParse.rc==SQLITE_OK ){
          207  +    *ppNew = pNew = sqlite3_malloc(sizeof(Fts5Expr));
          208  +    if( pNew==0 ){
          209  +      sParse.rc = SQLITE_NOMEM;
          210  +    }else{
          211  +      pNew->pRoot = sParse.pExpr;
          212  +      pNew->pIndex = 0;
          213  +    }
          214  +  }
          215  +
   198    216     *pzErr = sParse.zErr;
   199    217     return sParse.rc;
   200    218   }
   201    219   
   202    220   /*
   203         -** Free the object passed as the only argument.
          221  +** Free the expression node object passed as the only argument.
   204    222   */
   205         -void sqlite3Fts5ExprFree(Fts5Expr *p){
          223  +void sqlite3Fts5ParseNodeFree(Fts5ExprNode *p){
   206    224     if( p ){
   207         -    sqlite3Fts5ExprFree(p->pLeft);
   208         -    sqlite3Fts5ExprFree(p->pRight);
          225  +    sqlite3Fts5ParseNodeFree(p->pLeft);
          226  +    sqlite3Fts5ParseNodeFree(p->pRight);
   209    227       sqlite3Fts5ParseNearsetFree(p->pNear);
   210    228       sqlite3_free(p);
   211    229     }
   212    230   }
          231  +
          232  +/*
          233  +** Free the expression object passed as the only argument.
          234  +*/
          235  +void sqlite3Fts5ExprFree(Fts5Expr *p){
          236  +  if( p ){
          237  +    sqlite3Fts5ParseNodeFree(p->pRoot);
          238  +    sqlite3_free(p);
          239  +  }
          240  +}
          241  +
          242  +/*
          243  +**
          244  +*/
          245  +static int fts5ExprNodeTest(Fts5Expr *pExpr, Fts5ExprNode *pNode){
          246  +  assert( 0 );
          247  +  return SQLITE_OK;
          248  +}
          249  + 
          250  +static int fts5ExprNodeFirst(Fts5Expr *pExpr, Fts5ExprNode *pNode){
          251  +  int rc = SQLITE_OK;
          252  +
          253  +  pNode->bEof = 0;
          254  +  if( pNode->eType==FTS5_STRING ){
          255  +    Fts5ExprPhrase *pPhrase = pNode->pNear->apPhrase[0];
          256  +    Fts5ExprTerm *pTerm = &pPhrase->aTerm[0];
          257  +    assert( pNode->pNear->nPhrase==1 && pPhrase->nTerm==1 );
          258  +
          259  +    pTerm->pIter = sqlite3Fts5IndexQuery(
          260  +        pExpr->pIndex, pTerm->zTerm, strlen(pTerm->zTerm),
          261  +        (pTerm->bPrefix ? FTS5INDEX_QUERY_PREFIX : 0) |
          262  +        (pExpr->bAsc ? FTS5INDEX_QUERY_ASC : 0)
          263  +    );
          264  +    if( sqlite3Fts5IterEof(pTerm->pIter) ){
          265  +      pNode->bEof = 1;
          266  +    }else{
          267  +      pNode->iRowid = sqlite3Fts5IterRowid(pTerm->pIter);
          268  +    }
          269  +
          270  +  }else{
          271  +    rc = fts5ExprNodeFirst(pExpr, pNode->pLeft);
          272  +    if( rc==SQLITE_OK ){
          273  +      rc = fts5ExprNodeFirst(pExpr, pNode->pRight);
          274  +    }
          275  +    if( rc==SQLITE_OK ){
          276  +      rc = fts5ExprNodeTest(pExpr, pNode);
          277  +    }
          278  +  }
          279  +  return rc;
          280  +}
          281  +
          282  +static int fts5ExprNodeNext(Fts5Expr *pExpr, Fts5ExprNode *pNode){
          283  +  int rc = SQLITE_OK;
          284  +
          285  +  if( pNode->eType==FTS5_STRING ){
          286  +    Fts5ExprPhrase *pPhrase = pNode->pNear->apPhrase[0];
          287  +    Fts5ExprTerm *pTerm = &pPhrase->aTerm[0];
          288  +    assert( pNode->pNear->nPhrase==1 && pPhrase->nTerm==1 );
          289  +    sqlite3Fts5IterNext(pTerm->pIter, 0);
          290  +    if( sqlite3Fts5IterEof(pTerm->pIter) ){
          291  +      pNode->bEof = 1;
          292  +    }else{
          293  +      pNode->iRowid = sqlite3Fts5IterRowid(pTerm->pIter);
          294  +    }
          295  +  }else{
          296  +    assert( 0 );
          297  +  }
          298  +  return rc;
          299  +}
          300  +
          301  +
          302  +
          303  +/*
          304  +** Begin iterating through the set of documents in index pIdx matched by
          305  +** the MATCH expression passed as the first argument. If the "bAsc" parameter
          306  +** is passed a non-zero value, iteration is in ascending rowid order. Or,
          307  +** if it is zero, in descending order.
          308  +**
          309  +** Return SQLITE_OK if successful, or an SQLite error code otherwise. It
          310  +** is not considered an error if the query does not match any documents.
          311  +*/
          312  +int sqlite3Fts5ExprFirst(Fts5Expr *p, Fts5Index *pIdx, int bAsc){
          313  +  int rc;
          314  +  p->pIndex = pIdx;
          315  +  p->bAsc = bAsc;
          316  +  rc = fts5ExprNodeFirst(p, p->pRoot);
          317  +  return rc;
          318  +}
          319  +
          320  +/*
          321  +** Move to the next document 
          322  +**
          323  +** Return SQLITE_OK if successful, or an SQLite error code otherwise. It
          324  +** is not considered an error if the query does not match any documents.
          325  +*/
          326  +int sqlite3Fts5ExprNext(Fts5Expr *p){
          327  +  int rc;
          328  +  rc = fts5ExprNodeNext(p, p->pRoot);
          329  +  return rc;
          330  +}
          331  +
          332  +int sqlite3Fts5ExprEof(Fts5Expr *p){
          333  +  return p->pRoot->bEof;
          334  +}
          335  +
          336  +i64 sqlite3Fts5ExprRowid(Fts5Expr *p){
          337  +  return p->pRoot->iRowid;
          338  +}
   213    339   
   214    340   /*
   215    341   ** Argument pIn points to a buffer of nIn bytes. This function allocates
   216    342   ** and returns a new buffer populated with a copy of (pIn/nIn) with a 
   217    343   ** nul-terminator byte appended to it.
   218    344   **
   219    345   ** It is the responsibility of the caller to eventually free the returned
................................................................................
   225    351       memcpy(zRet, pIn, nIn);
   226    352       zRet[nIn] = '\0';
   227    353     }
   228    354     return zRet;
   229    355   }
   230    356   
   231    357   static int fts5ParseStringFromToken(Fts5Token *pToken, char **pz){
   232         -  *pz = sqlite3_mprintf("%.*s", pToken->n, pToken->p);
          358  +  *pz = fts5Strdup(pToken->p, pToken->n);
   233    359     if( *pz==0 ) return SQLITE_NOMEM;
   234    360     return SQLITE_OK;
   235    361   }
   236    362   
   237    363   /*
   238    364   ** Free the phrase object passed as the only argument.
   239    365   */
   240    366   static void fts5ExprPhraseFree(Fts5ExprPhrase *pPhrase){
   241    367     if( pPhrase ){
   242    368       int i;
   243    369       for(i=0; i<pPhrase->nTerm; i++){
   244         -      sqlite3_free(pPhrase->aTerm[i].zTerm);
          370  +      Fts5ExprTerm *pTerm = &pPhrase->aTerm[i];
          371  +      sqlite3_free(pTerm->zTerm);
          372  +      if( pTerm->pIter ){
          373  +        sqlite3Fts5IterClose(pTerm->pIter);
          374  +      }
   245    375       }
   246    376       sqlite3_free(pPhrase);
   247    377     }
   248    378   }
   249    379   
   250    380   /*
   251    381   ** If argument pNear is NULL, then a new Fts5ExprNearset object is allocated
................................................................................
   353    483       for(i=0; i<pNear->nPhrase; i++){
   354    484         fts5ExprPhraseFree(pNear->apPhrase[i]);
   355    485       }
   356    486       sqlite3_free(pNear);
   357    487     }
   358    488   }
   359    489   
   360         -void sqlite3Fts5ParseFinished(Fts5Parse *pParse, Fts5Expr *p){
          490  +void sqlite3Fts5ParseFinished(Fts5Parse *pParse, Fts5ExprNode *p){
   361    491     assert( pParse->pExpr==0 );
   362    492     pParse->pExpr = p;
   363    493   }
   364    494   
   365    495   /*
   366    496   ** This function is called by the parser to process a string token. The
   367    497   ** string may or may not be quoted. In any case it is tokenized and a
................................................................................
   397    527     return sCtx.pPhrase;
   398    528   }
   399    529   
   400    530   void sqlite3Fts5ParseNear(Fts5Parse *pParse, Fts5Token *pTok){
   401    531     if( pParse->rc==SQLITE_OK ){
   402    532       if( pTok->n!=4 || memcmp("NEAR", pTok->p, 4) ){
   403    533         sqlite3Fts5ParseError(
   404         -          pParse, "syntax error near \"%.*s\"", pTok->n, pTok->p
          534  +          pParse, "fts5: syntax error near \"%.*s\"", pTok->n, pTok->p
   405    535         );
   406    536       }
   407    537     }
   408    538   }
   409    539   
   410    540   void sqlite3Fts5ParseSetDistance(
   411    541     Fts5Parse *pParse, 
................................................................................
   456    586     }
   457    587   }
   458    588   
   459    589   /*
   460    590   ** Allocate and return a new expression object. If anything goes wrong (i.e.
   461    591   ** OOM error), leave an error code in pParse and return NULL.
   462    592   */
   463         -Fts5Expr *sqlite3Fts5ParseExpr(
          593  +Fts5ExprNode *sqlite3Fts5ParseNode(
   464    594     Fts5Parse *pParse,              /* Parse context */
   465    595     int eType,                      /* FTS5_STRING, AND, OR or NOT */
   466         -  Fts5Expr *pLeft,                /* Left hand child expression */
   467         -  Fts5Expr *pRight,               /* Right hand child expression */
          596  +  Fts5ExprNode *pLeft,            /* Left hand child expression */
          597  +  Fts5ExprNode *pRight,           /* Right hand child expression */
   468    598     Fts5ExprNearset *pNear          /* For STRING expressions, the near cluster */
   469    599   ){
   470         -  Fts5Expr *pRet = 0;
          600  +  Fts5ExprNode *pRet = 0;
   471    601   
   472    602     if( pParse->rc==SQLITE_OK ){
   473    603       assert( (eType!=FTS5_STRING && pLeft  && pRight  && !pNear)
   474    604           || (eType==FTS5_STRING && !pLeft && !pRight && pNear)
   475    605       );
   476         -    pRet = (Fts5Expr*)sqlite3_malloc(sizeof(Fts5Expr));
          606  +    pRet = (Fts5ExprNode*)sqlite3_malloc(sizeof(Fts5ExprNode));
   477    607       if( pRet==0 ){
   478    608         pParse->rc = SQLITE_NOMEM;
   479    609       }else{
   480    610         memset(pRet, 0, sizeof(*pRet));
   481    611         pRet->eType = eType;
   482    612         pRet->pLeft = pLeft;
   483    613         pRet->pRight = pRight;
   484    614         pRet->pNear = pNear;
   485    615       }
   486    616     }
   487    617   
   488    618     if( pRet==0 ){
   489    619       assert( pParse->rc!=SQLITE_OK );
   490         -    sqlite3Fts5ExprFree(pLeft);
   491         -    sqlite3Fts5ExprFree(pRight);
          620  +    sqlite3Fts5ParseNodeFree(pLeft);
          621  +    sqlite3Fts5ParseNodeFree(pRight);
   492    622       sqlite3Fts5ParseNearsetFree(pNear);
   493    623     }
   494    624     return pRet;
   495    625   }
   496    626   
   497    627   static char *fts5ExprTermPrint(Fts5ExprTerm *pTerm){
   498    628     char *zQuoted = sqlite3_malloc(strlen(pTerm->zTerm) * 2 + 3 + 2);
................................................................................
   525    655       sqlite3_free(zNew);
   526    656       zNew = zNew2;
   527    657     }
   528    658     sqlite3_free(zApp);
   529    659     return zNew;
   530    660   }
   531    661   
   532         -static char *fts5ExprPrint(Fts5Config *pConfig, Fts5Expr *pExpr){
          662  +static char *fts5ExprPrint(Fts5Config *pConfig, Fts5ExprNode *pExpr){
   533    663     char *zRet = 0;
   534    664     if( pExpr->eType==FTS5_STRING ){
   535    665       Fts5ExprNearset *pNear = pExpr->pNear;
   536    666       int i; 
   537    667       int iTerm;
   538    668   
   539    669       if( pNear->iCol>=0 ){
................................................................................
   630    760     for(i=1; i<nArg; i++){
   631    761       azConfig[i+2] = (const char*)sqlite3_value_text(apVal[i]);
   632    762     }
   633    763     zExpr = (const char*)sqlite3_value_text(apVal[0]);
   634    764   
   635    765     rc = sqlite3Fts5ConfigParse(db, nConfig, azConfig, &pConfig, &zErr);
   636    766     if( rc==SQLITE_OK ){
   637         -    rc = sqlite3Fts5ExprNew(pConfig, 0, zExpr, &pExpr, &zErr);
          767  +    rc = sqlite3Fts5ExprNew(pConfig, zExpr, &pExpr, &zErr);
   638    768     }
   639    769     if( rc==SQLITE_OK ){
   640         -    char *zText = fts5ExprPrint(pConfig, pExpr);
          770  +    char *zText = fts5ExprPrint(pConfig, pExpr->pRoot);
   641    771       if( rc==SQLITE_OK ){
   642    772         sqlite3_result_text(pCtx, zText, -1, SQLITE_TRANSIENT);
   643    773         sqlite3_free(zText);
   644    774       }
   645    775     }
   646    776   
   647    777     if( rc!=SQLITE_OK ){

Changes to ext/fts5/fts5_index.c.

   292    292     int rc;                         /* Current error code */
   293    293   
   294    294     /* State used by the fts5DataXXX() functions. */
   295    295     sqlite3_blob *pReader;          /* RO incr-blob open on %_data table */
   296    296     sqlite3_stmt *pWriter;          /* "INSERT ... %_data VALUES(?,?)" */
   297    297     sqlite3_stmt *pDeleter;         /* "DELETE FROM %_data ... id>=? AND id<=?" */
   298    298   };
          299  +
          300  +struct Fts5IndexIter {
          301  +  Fts5Index *pIndex;
          302  +  Fts5Structure *pStruct;
          303  +  Fts5MultiSegIter *pMulti;
          304  +};
          305  +
   299    306   
   300    307   /*
   301    308   ** Buffer object for the incremental building of string data.
   302    309   */
   303    310   struct Fts5Buffer {
   304    311     u8 *p;
   305    312     int n;
................................................................................
   421    428   **
   422    429   ** pLeaf:
   423    430   **   Buffer containing current leaf page data. Set to NULL at EOF.
   424    431   **
   425    432   ** iTermLeafPgno, iTermLeafOffset:
   426    433   **   Leaf page number containing the last term read from the segment. And
   427    434   **   the offset immediately following the term data.
          435  +**
          436  +** bOneTerm:
          437  +**   If true, set the iterator to point to EOF after the current doclist has
          438  +**   been exhausted. Do not proceed to the next term in the segment.
   428    439   */
   429    440   struct Fts5SegIter {
   430    441     Fts5StructureSegment *pSeg;     /* Segment to iterate through */
   431    442     int iIdx;                       /* Byte offset within current leaf */
          443  +  int bOneTerm;                   /* If true, iterate through single doclist */
   432    444     int iLeafPgno;                  /* Current leaf page number */
   433    445     Fts5Data *pLeaf;                /* Current leaf data */
   434    446     int iLeafOffset;                /* Byte offset within current leaf */
   435    447   
   436    448     int iTermLeafPgno;
   437    449     int iTermLeafOffset;
   438    450   
................................................................................
   652    664     Fts5Buffer *pBuf, 
   653    665     int nData, 
   654    666     const u8 *pData
   655    667   ){
   656    668     pBuf->n = 0;
   657    669     fts5BufferAppendBlob(pRc, pBuf, nData, pData);
   658    670   }
          671  +
          672  +/*
          673  +** Compare the contents of the pLeft buffer with the pRight/nRight blob.
          674  +**
          675  +** Return -ve if pLeft is smaller than pRight, 0 if they are equal or
          676  +** +ve if pRight is smaller than pLeft. In other words:
          677  +**
          678  +**     res = *pLeft - *pRight
          679  +*/
          680  +static int fts5BufferCompareBlob(
          681  +  Fts5Buffer *pLeft,              /* Left hand side of comparison */
          682  +  const u8 *pRight, int nRight    /* Right hand side of comparison */
          683  +){
          684  +  int nCmp = MIN(pLeft->n, nRight);
          685  +  int res = memcmp(pLeft->p, pRight, nCmp);
          686  +  return (res==0 ? (pLeft->n - nRight) : res);
          687  +}
   659    688   
   660    689   /*
   661    690   ** Compare the contents of the two buffers using memcmp(). If one buffer
   662    691   ** is a prefix of the other, it is considered the lesser.
   663    692   **
   664    693   ** Return -ve if pLeft is smaller than pRight, 0 if they are equal or
   665    694   ** +ve if pRight is smaller than pLeft. In other words:
................................................................................
   735    764   **
   736    765   ** If an error occurs, NULL is returned and an error left in the 
   737    766   ** Fts5Index object.
   738    767   */
   739    768   static Fts5Data *fts5DataRead(Fts5Index *p, i64 iRowid){
   740    769     Fts5Data *pRet = fts5DataReadOrBuffer(p, 0, iRowid);
   741    770     assert( (pRet==0)==(p->rc!=SQLITE_OK) );
   742         -assert( pRet );
   743    771     return pRet;
   744    772   }
   745    773   
   746    774   /*
   747    775   ** Read a record from the %_data table into the buffer supplied as the
   748    776   ** second argument.
   749    777   **
................................................................................
  1001   1029       }
  1002   1030     }
  1003   1031   
  1004   1032     fts5DataWrite(p, FTS5_STRUCTURE_ROWID(iIdx), buf.p, buf.n);
  1005   1033     fts5BufferFree(&buf);
  1006   1034   }
  1007   1035   
         1036  +
         1037  +/*
         1038  +** If the pIter->iOff offset currently points to an entry indicating one
         1039  +** or more term-less nodes, advance past it and set pIter->nEmpty to
         1040  +** the number of empty child nodes.
         1041  +*/
         1042  +static void fts5NodeIterGobbleNEmpty(Fts5NodeIter *pIter){
         1043  +  if( pIter->iOff<pIter->nData && 0==(pIter->aData[pIter->iOff] & 0xfe) ){
         1044  +    pIter->iOff++;
         1045  +    pIter->iOff += getVarint32(&pIter->aData[pIter->iOff], pIter->nEmpty);
         1046  +  }else{
         1047  +    pIter->nEmpty = 0;
         1048  +  }
         1049  +}
         1050  +
         1051  +/*
         1052  +** Advance to the next entry within the node.
         1053  +*/
         1054  +static void fts5NodeIterNext(int *pRc, Fts5NodeIter *pIter){
         1055  +  if( pIter->iOff>=pIter->nData ){
         1056  +    pIter->aData = 0;
         1057  +    pIter->iChild += pIter->nEmpty;
         1058  +  }else{
         1059  +    int nPre, nNew;
         1060  +    pIter->iOff += getVarint32(&pIter->aData[pIter->iOff], nPre);
         1061  +    pIter->iOff += getVarint32(&pIter->aData[pIter->iOff], nNew);
         1062  +    pIter->term.n = nPre-2;
         1063  +    fts5BufferAppendBlob(pRc, &pIter->term, nNew, pIter->aData+pIter->iOff);
         1064  +    pIter->iOff += nNew;
         1065  +    pIter->iChild += (1 + pIter->nEmpty);
         1066  +    fts5NodeIterGobbleNEmpty(pIter);
         1067  +    if( *pRc ) pIter->aData = 0;
         1068  +  }
         1069  +}
         1070  +
         1071  +
         1072  +/*
         1073  +** Initialize the iterator object pIter to iterate through the internal
         1074  +** segment node in pData.
         1075  +*/
         1076  +static void fts5NodeIterInit(const u8 *aData, int nData, Fts5NodeIter *pIter){
         1077  +  memset(pIter, 0, sizeof(*pIter));
         1078  +  pIter->aData = aData;
         1079  +  pIter->nData = nData;
         1080  +  pIter->iOff = getVarint32(aData, pIter->iChild);
         1081  +  fts5NodeIterGobbleNEmpty(pIter);
         1082  +}
         1083  +
         1084  +/*
         1085  +** Free any memory allocated by the iterator object.
         1086  +*/
         1087  +static void fts5NodeIterFree(Fts5NodeIter *pIter){
         1088  +  fts5BufferFree(&pIter->term);
         1089  +}
  1008   1090   
  1009   1091   /*
  1010   1092   ** Load the next leaf page into the segment iterator.
  1011   1093   */
  1012   1094   static void fts5SegIterNextPage(
  1013   1095     Fts5Index *p,                   /* FTS5 backend object */
  1014   1096     Fts5SegIter *pIter              /* Iterator to advance to next page */
................................................................................
  1074   1156   
  1075   1157     if( p->rc==SQLITE_OK ){
  1076   1158       u8 *a = pIter->pLeaf->p;
  1077   1159       pIter->iLeafOffset = fts5GetU16(&a[2]);
  1078   1160       fts5SegIterLoadTerm(p, pIter, 0);
  1079   1161     }
  1080   1162   }
         1163  +
         1164  +/*
         1165  +** Initialize the object pIter to point to term pTerm/nTerm within segment
         1166  +** pSeg, index iIdx. If there is no such term in the index, the iterator
         1167  +** is set to EOF.
         1168  +**
         1169  +** If an error occurs, Fts5Index.rc is set to an appropriate error code. If 
         1170  +** an error has already occurred when this function is called, it is a no-op.
         1171  +*/
         1172  +static void fts5SegIterSeekInit(
         1173  +  Fts5Index *p,                   /* FTS5 backend */
         1174  +  int iIdx,                       /* Config.aHash[] index of FTS index */
         1175  +  const u8 *pTerm, int nTerm,     /* Term to seek to */
         1176  +  Fts5StructureSegment *pSeg,     /* Description of segment */
         1177  +  Fts5SegIter *pIter              /* Object to populate */
         1178  +){
         1179  +  int iPg = 1;
         1180  +  int h;
         1181  +
         1182  +  assert( pTerm && nTerm );
         1183  +  memset(pIter, 0, sizeof(*pIter));
         1184  +  pIter->pSeg = pSeg;
         1185  +  pIter->iIdx = iIdx;
         1186  +  pIter->bOneTerm = 1;
         1187  +
         1188  +  for(h=pSeg->nHeight-1; h>0; h--){
         1189  +    Fts5NodeIter node;              /* For iterating through internal nodes */
         1190  +    i64 iRowid = FTS5_SEGMENT_ROWID(iIdx, pSeg->iSegid, h, iPg);
         1191  +    Fts5Data *pNode = fts5DataRead(p, iRowid);
         1192  +    if( pNode==0 ) break;
         1193  +
         1194  +    fts5NodeIterInit(pNode->p, pNode->n, &node);
         1195  +    assert( node.term.n==0 );
         1196  +
         1197  +    iPg = node.iChild;
         1198  +    for(fts5NodeIterNext(&p->rc, &node);
         1199  +        node.aData && fts5BufferCompareBlob(&node.term, pTerm, nTerm)>=0;
         1200  +        fts5NodeIterNext(&p->rc, &node)
         1201  +    ){
         1202  +      iPg = node.iChild;
         1203  +    }
         1204  +  }
         1205  +
         1206  +  if( iPg>=pSeg->pgnoFirst ){
         1207  +    int res;
         1208  +    pIter->iLeafPgno = iPg - 1;
         1209  +    fts5SegIterNextPage(p, pIter);
         1210  +    if( pIter->pLeaf ){
         1211  +      u8 *a = pIter->pLeaf->p;
         1212  +      int n = pIter->pLeaf->n;
         1213  +
         1214  +      pIter->iLeafOffset = fts5GetU16(&a[2]);
         1215  +      fts5SegIterLoadTerm(p, pIter, 0);
         1216  +
         1217  +      while( (res = fts5BufferCompareBlob(&pIter->term, pTerm, nTerm)) ){
         1218  +        if( res<0 ){
         1219  +          /* Search for the end of the position list within the current page. */
         1220  +          int iOff;
         1221  +          for(iOff=pIter->iLeafOffset; iOff<n && a[iOff]; iOff++);
         1222  +          pIter->iLeafOffset = iOff+1;
         1223  +          if( iOff<n ) continue;
         1224  +        }
         1225  +
         1226  +        /* No matching term on this page. Set the iterator to EOF. */
         1227  +        fts5DataRelease(pIter->pLeaf);
         1228  +        pIter->pLeaf = 0;
         1229  +        break;
         1230  +      }
         1231  +    }
         1232  +  }
         1233  +}
  1081   1234   
  1082   1235   /*
  1083   1236   ** Advance iterator pIter to the next entry. 
  1084   1237   **
  1085   1238   ** If an error occurs, Fts5Index.rc is set to an appropriate error code. It 
  1086   1239   ** is not considered an error if the iterator reaches EOF. If an error has 
  1087   1240   ** already occurred when this function is called, it is a no-op.
................................................................................
  1133   1286             pIter->iLeafOffset = iOff;
  1134   1287             bNewTerm = 1;
  1135   1288           }
  1136   1289         }
  1137   1290       }
  1138   1291   
  1139   1292       /* Check if the iterator is now at EOF. If so, return early. */
  1140         -    if( pIter->pLeaf==0 ) return;
  1141         -    if( bNewTerm ){
  1142         -      fts5SegIterLoadTerm(p, pIter, nKeep);
         1293  +    if( pIter->pLeaf && bNewTerm ){
         1294  +      if( pIter->bOneTerm ){
         1295  +        fts5DataRelease(pIter->pLeaf);
         1296  +        pIter->pLeaf = 0;
         1297  +      }else{
         1298  +        fts5SegIterLoadTerm(p, pIter, nKeep);
         1299  +      }
  1143   1300       }
  1144   1301     }
  1145   1302   }
  1146   1303   
  1147   1304   /*
  1148   1305   ** Zero the iterator passed as the only argument.
  1149   1306   */
................................................................................
  1259   1416   ** The iterator initially points to the first term/rowid entry in the 
  1260   1417   ** iterated data.
  1261   1418   */
  1262   1419   static void fts5MultiIterNew(
  1263   1420     Fts5Index *p,                   /* FTS5 backend to iterate within */
  1264   1421     Fts5Structure *pStruct,         /* Structure of specific index */
  1265   1422     int iIdx,                       /* Config.aHash[] index of FTS index */
         1423  +  const u8 *pTerm, int nTerm,     /* Term to seek to (or NULL/0) */
  1266   1424     int iLevel,                     /* Level to iterate (-1 for all) */
  1267   1425     int nSegment,                   /* Number of segments to merge (iLevel>=0) */
  1268   1426     Fts5MultiSegIter **ppOut        /* New object */
  1269   1427   ){
  1270   1428     int nSeg;                       /* Number of segments merged */
  1271   1429     int nSlot;                      /* Power of two >= nSeg */
  1272   1430     int iIter = 0;                  /* */
  1273   1431     int iSeg;                       /* Used to iterate through segments */
  1274   1432     Fts5StructureLevel *pLvl;
  1275   1433     Fts5MultiSegIter *pNew;
         1434  +
         1435  +  assert( (pTerm==0 && nTerm==0) || iLevel<0 );
  1276   1436   
  1277   1437     /* Allocate space for the new multi-seg-iterator. */
  1278   1438     if( iLevel<0 ){
  1279   1439       nSeg = fts5StructureCountSegments(pStruct);
  1280   1440     }else{
  1281   1441       nSeg = MIN(pStruct->aLevel[iLevel].nSeg, nSegment);
  1282   1442     }
................................................................................
  1292   1452     pNew->aFirst = (u16*)&pNew->aSeg[nSlot];
  1293   1453   
  1294   1454     /* Initialize each of the component segment iterators. */
  1295   1455     if( iLevel<0 ){
  1296   1456       Fts5StructureLevel *pEnd = &pStruct->aLevel[pStruct->nLevel];
  1297   1457       for(pLvl=&pStruct->aLevel[0]; pLvl<pEnd; pLvl++){
  1298   1458         for(iSeg=pLvl->nSeg-1; iSeg>=0; iSeg--){
  1299         -        fts5SegIterInit(p, iIdx, &pLvl->aSeg[iSeg], &pNew->aSeg[iIter++]);
         1459  +        Fts5SegIter *pIter = &pNew->aSeg[iIter++];
         1460  +        if( pTerm==0 ){
         1461  +          fts5SegIterInit(p, iIdx, &pLvl->aSeg[iSeg], pIter);
         1462  +        }else{
         1463  +          fts5SegIterSeekInit(p, iIdx, pTerm, nTerm, &pLvl->aSeg[iSeg], pIter);
         1464  +        }
  1300   1465         }
  1301   1466       }
  1302   1467     }else{
  1303   1468       pLvl = &pStruct->aLevel[iLevel];
  1304   1469       for(iSeg=nSeg-1; iSeg>=0; iSeg--){
  1305   1470         fts5SegIterInit(p, iIdx, &pLvl->aSeg[iSeg], &pNew->aSeg[iIter++]);
  1306   1471       }
................................................................................
  1697   1862     int i;
  1698   1863     for(i=0; i<nNew && i<nOld; i++){
  1699   1864       if( pOld[i]!=pNew[i] ) break;
  1700   1865     }
  1701   1866     return i;
  1702   1867   }
  1703   1868   
  1704         -/*
  1705         -** If the pIter->iOff offset currently points to an entry indicating one
  1706         -** or more term-less nodes, advance past it and set pIter->nEmpty to
  1707         -** the number of empty child nodes.
  1708         -*/
  1709         -static void fts5NodeIterGobbleNEmpty(Fts5NodeIter *pIter){
  1710         -  if( pIter->iOff<pIter->nData && 0==(pIter->aData[pIter->iOff] & 0xfe) ){
  1711         -    pIter->iOff++;
  1712         -    pIter->iOff += getVarint32(&pIter->aData[pIter->iOff], pIter->nEmpty);
  1713         -  }else{
  1714         -    pIter->nEmpty = 0;
  1715         -  }
  1716         -}
  1717         -
  1718         -/*
  1719         -** Advance to the next entry within the node.
  1720         -*/
  1721         -static void fts5NodeIterNext(int *pRc, Fts5NodeIter *pIter){
  1722         -  if( pIter->iOff>=pIter->nData ){
  1723         -    pIter->aData = 0;
  1724         -    pIter->iChild += pIter->nEmpty;
  1725         -  }else{
  1726         -    int nPre, nNew;
  1727         -    pIter->iOff += getVarint32(&pIter->aData[pIter->iOff], nPre);
  1728         -    pIter->iOff += getVarint32(&pIter->aData[pIter->iOff], nNew);
  1729         -    pIter->term.n = nPre-2;
  1730         -    fts5BufferAppendBlob(pRc, &pIter->term, nNew, pIter->aData+pIter->iOff);
  1731         -    pIter->iOff += nNew;
  1732         -    pIter->iChild += (1 + pIter->nEmpty);
  1733         -    fts5NodeIterGobbleNEmpty(pIter);
  1734         -    if( *pRc ) pIter->aData = 0;
  1735         -  }
  1736         -}
  1737         -
  1738         -
  1739         -/*
  1740         -** Initialize the iterator object pIter to iterate through the internal
  1741         -** segment node in pData.
  1742         -*/
  1743         -static void fts5NodeIterInit(int nData, const u8 *aData, Fts5NodeIter *pIter){
  1744         -  memset(pIter, 0, sizeof(*pIter));
  1745         -  pIter->aData = aData;
  1746         -  pIter->nData = nData;
  1747         -  pIter->iOff = getVarint32(aData, pIter->iChild);
  1748         -  fts5NodeIterGobbleNEmpty(pIter);
  1749         -}
  1750         -
  1751         -/*
  1752         -** Free any memory allocated by the iterator object.
  1753         -*/
  1754         -static void fts5NodeIterFree(Fts5NodeIter *pIter){
  1755         -  fts5BufferFree(&pIter->term);
  1756         -}
  1757         -
  1758   1869   
  1759   1870   /*
  1760   1871   ** This is called once for each leaf page except the first that contains
  1761   1872   ** at least one term. Argument (nTerm/pTerm) is the split-key - a term that
  1762   1873   ** is larger than all terms written to earlier leaves, and equal to or
  1763   1874   ** smaller than the first term on the new leaf.
  1764   1875   **
................................................................................
  2058   2169       for(i=pSeg->nHeight-1; i>0; i--){
  2059   2170         i64 iRowid = FTS5_SEGMENT_ROWID(pWriter->iIdx, pWriter->iSegid, i, pgno);
  2060   2171         Fts5PageWriter *pPg = &pWriter->aWriter[i];
  2061   2172         pPg->pgno = pgno;
  2062   2173         fts5DataBuffer(p, &pPg->buf, iRowid);
  2063   2174         if( p->rc==SQLITE_OK ){
  2064   2175           Fts5NodeIter ss;
  2065         -        fts5NodeIterInit(pPg->buf.n, pPg->buf.p, &ss);
         2176  +        fts5NodeIterInit(pPg->buf.p, pPg->buf.n, &ss);
  2066   2177           while( ss.aData ) fts5NodeIterNext(&p->rc, &ss);
  2067   2178           fts5BufferSet(&p->rc, &pPg->term, ss.term.n, ss.term.p);
  2068   2179           pgno = ss.iChild;
  2069   2180           fts5NodeIterFree(&ss);
  2070   2181         }
  2071   2182       }
  2072   2183       if( pSeg->nHeight==1 ){
................................................................................
  2163   2274       nInput = pLvl->nSeg;
  2164   2275     }
  2165   2276   #if 0
  2166   2277   fprintf(stdout, "merging %d segments from level %d!", nInput, iLvl);
  2167   2278   fflush(stdout);
  2168   2279   #endif
  2169   2280   
  2170         -  for(fts5MultiIterNew(p, pStruct, iIdx, iLvl, nInput, &pIter);
         2281  +  for(fts5MultiIterNew(p, pStruct, iIdx, 0, 0, iLvl, nInput, &pIter);
  2171   2282         fts5MultiIterEof(p, pIter)==0;
  2172   2283         fts5MultiIterNext(p, pIter)
  2173   2284     ){
  2174   2285       Fts5PosIter sPos;             /* Used to iterate through position list */
  2175   2286       int iCol = 0;                 /* Current output column */
  2176   2287       int iPos = 0;                 /* Current output position */
  2177   2288       int nTerm;
................................................................................
  2520   2631       pIter->aLvl = (Fts5BtreeIterLevel*)fts5IdxMalloc(p, nByte);
  2521   2632     }
  2522   2633     for(i=0; p->rc==SQLITE_OK && i<pIter->nLvl; i++){
  2523   2634       i64 iRowid = FTS5_SEGMENT_ROWID(iIdx, pSeg->iSegid, i+1, 1);
  2524   2635       Fts5Data *pData;
  2525   2636       pIter->aLvl[i].pData = pData = fts5DataRead(p, iRowid);
  2526   2637       if( pData ){
  2527         -      fts5NodeIterInit(pData->n, pData->p, &pIter->aLvl[i].s);
         2638  +      fts5NodeIterInit(pData->p, pData->n, &pIter->aLvl[i].s);
  2528   2639       }
  2529   2640     }
  2530   2641   
  2531   2642     if( pIter->nLvl==0 || p->rc ){
  2532   2643       pIter->bEof = 1;
  2533   2644       pIter->iLeaf = pSeg->pgnoLast;
  2534   2645     }else{
................................................................................
  2559   2670     }else{
  2560   2671       int iSegid = pIter->pSeg->iSegid;
  2561   2672       for(i--; i>=0; i--){
  2562   2673         Fts5BtreeIterLevel *pLvl = &pIter->aLvl[i];
  2563   2674         i64 iRowid = FTS5_SEGMENT_ROWID(pIter->iIdx,iSegid,i+1,pLvl[1].s.iChild);
  2564   2675         pLvl->pData = fts5DataRead(p, iRowid);
  2565   2676         if( pLvl->pData ){
  2566         -        fts5NodeIterInit(pLvl->pData->n, pLvl->pData->p, &pLvl->s);
         2677  +        fts5NodeIterInit(pLvl->pData->p, pLvl->pData->n, &pLvl->s);
  2567   2678         }
  2568   2679       }
  2569   2680     }
  2570   2681   
  2571   2682     pIter->nEmpty = pIter->aLvl[0].s.nEmpty;
  2572   2683     pIter->iLeaf = pIter->aLvl[0].s.iChild;
  2573   2684     assert( p->rc==SQLITE_OK || pIter->bEof );
................................................................................
  2663   2774     int rc;                         /* Return code */
  2664   2775     u64 cksum2 = 0;                 /* Checksum based on contents of indexes */
  2665   2776   
  2666   2777     /* Check that the checksum of the index matches the argument checksum */
  2667   2778     for(iIdx=0; iIdx<=pConfig->nPrefix; iIdx++){
  2668   2779       Fts5MultiSegIter *pIter;
  2669   2780       Fts5Structure *pStruct = fts5StructureRead(p, iIdx);
  2670         -    for(fts5MultiIterNew(p, pStruct, iIdx, -1, 0, &pIter);
         2781  +    for(fts5MultiIterNew(p, pStruct, iIdx, 0, 0, -1, 0, &pIter);
  2671   2782           fts5MultiIterEof(p, pIter)==0;
  2672   2783           fts5MultiIterNext(p, pIter)
  2673   2784       ){
  2674   2785         Fts5PosIter sPos;           /* Used to iterate through position list */
  2675   2786         int n;                      /* Size of term in bytes */
  2676   2787         i64 iRowid = fts5MultiIterRowid(pIter);
  2677   2788         char *z = (char*)fts5MultiIterTerm(pIter, &n);
................................................................................
  2889   3000           if( iOff<n ){
  2890   3001             iOff += getVarint32(&a[iOff], nKeep);
  2891   3002           }
  2892   3003         }
  2893   3004         fts5BufferFree(&term);
  2894   3005       }else{
  2895   3006         Fts5NodeIter ss;
  2896         -      for(fts5NodeIterInit(n, a, &ss); ss.aData; fts5NodeIterNext(&rc, &ss)){
         3007  +      for(fts5NodeIterInit(a, n, &ss); ss.aData; fts5NodeIterNext(&rc, &ss)){
  2897   3008           if( ss.term.n==0 ){
  2898   3009             fts5BufferAppendPrintf(&rc, &s, " left=%d", ss.iChild);
  2899   3010           }else{
  2900   3011             fts5BufferAppendPrintf(&rc,&s, " \"%.*s\"", ss.term.n, ss.term.p);
  2901   3012           }
  2902   3013           if( ss.nEmpty ){
  2903   3014             fts5BufferAppendPrintf(&rc, &s, " empty=%d", ss.nEmpty);
................................................................................
  2932   3043   
  2933   3044   /*
  2934   3045   ** Set the target page size for the index object.
  2935   3046   */
  2936   3047   void sqlite3Fts5IndexPgsz(Fts5Index *p, int pgsz){
  2937   3048     p->pgsz = pgsz;
  2938   3049   }
         3050  +
         3051  +/*
         3052  +** Open a new iterator to iterate though all docids that match the 
         3053  +** specified token or token prefix.
         3054  +*/
         3055  +Fts5IndexIter *sqlite3Fts5IndexQuery(
         3056  +  Fts5Index *p,                   /* FTS index to query */
         3057  +  const char *pToken, int nToken, /* Token (or prefix) to query for */
         3058  +  int flags                       /* Mask of FTS5INDEX_QUERY_X flags */
         3059  +){
         3060  +  Fts5IndexIter *pRet;
         3061  +  int iIdx = 0;
         3062  +
         3063  +  if( flags & FTS5INDEX_QUERY_PREFIX ){
         3064  +    Fts5Config *pConfig = p->pConfig;
         3065  +    for(iIdx=1; iIdx<=pConfig->nPrefix; iIdx++){
         3066  +      if( pConfig->aPrefix[iIdx-1]==nToken ) break;
         3067  +    }
         3068  +    if( iIdx>pConfig->nPrefix ){
         3069  +      /* No matching prefix index. todo: deal with this. */
         3070  +      assert( 0 );
         3071  +    }
         3072  +  }
         3073  +
         3074  +  pRet = (Fts5IndexIter*)sqlite3_malloc(sizeof(Fts5IndexIter));
         3075  +  if( pRet ){
         3076  +    pRet->pStruct = fts5StructureRead(p, 0);
         3077  +    if( pRet->pStruct ){
         3078  +      fts5MultiIterNew(p, 
         3079  +          pRet->pStruct, iIdx, (const u8*)pToken, nToken, -1, 0, &pRet->pMulti
         3080  +      );
         3081  +    }
         3082  +    pRet->pIndex = p;
         3083  +  }
         3084  +
         3085  +  if( p->rc ){
         3086  +    sqlite3Fts5IterClose(pRet);
         3087  +    pRet = 0;
         3088  +  }
         3089  +  return pRet;
         3090  +}
         3091  +
         3092  +/*
         3093  +** Return true if the iterator passed as the only argument is at EOF.
         3094  +*/
         3095  +int sqlite3Fts5IterEof(Fts5IndexIter *pIter){
         3096  +  return fts5MultiIterEof(pIter->pIndex, pIter->pMulti);
         3097  +}
         3098  +
         3099  +/*
         3100  +** Move to the next matching rowid. 
         3101  +*/
         3102  +void sqlite3Fts5IterNext(Fts5IndexIter *pIter, i64 iMatch){
         3103  +  fts5MultiIterNext(pIter->pIndex, pIter->pMulti);
         3104  +}
         3105  +
         3106  +/*
         3107  +** Return the current rowid.
         3108  +*/
         3109  +i64 sqlite3Fts5IterRowid(Fts5IndexIter *pIter){
         3110  +  return fts5MultiIterRowid(pIter->pMulti);
         3111  +}
         3112  +
         3113  +/*
         3114  +** Close an iterator opened by an earlier call to sqlite3Fts5IndexQuery().
         3115  +*/
         3116  +void sqlite3Fts5IterClose(Fts5IndexIter *pIter){
         3117  +  if( pIter ){
         3118  +    fts5MultiIterFree(pIter->pIndex, pIter->pMulti);
         3119  +    fts5StructureRelease(pIter->pStruct);
         3120  +    fts5CloseReader(pIter->pIndex);
         3121  +    sqlite3_free(pIter);
         3122  +  }
         3123  +}
  2939   3124   

Changes to test/fts5ab.test.

    49     49   do_execsql_test 1.5 {
    50     50     SELECT * FROM t1 WHERE rowid=2.01;
    51     51   } {}
    52     52   
    53     53   do_execsql_test 1.6 {
    54     54     SELECT * FROM t1 WHERE rowid=1.99;
    55     55   } {}
           56  +
           57  +#-------------------------------------------------------------------------
           58  +
           59  +reset_db
           60  +do_execsql_test 2.1 {
           61  +  CREATE VIRTUAL TABLE t1 USING fts5(x);
           62  +  INSERT INTO t1 VALUES('one');
           63  +  INSERT INTO t1 VALUES('two');
           64  +  INSERT INTO t1 VALUES('three');
           65  +}
           66  +
           67  +do_catchsql_test 2.2 {
           68  +  SELECT rowid, * FROM t1 WHERE t1 MATCH 'AND AND'
           69  +} {1 {fts5: syntax error near "AND"}}
           70  +
           71  +do_execsql_test 2.3 { SELECT rowid, * FROM t1 WHERE t1 MATCH 'two' } {2 two}
           72  +do_execsql_test 2.4 { SELECT rowid, * FROM t1 WHERE t1 MATCH 'three' } {3 three}
           73  +do_execsql_test 2.5 { SELECT rowid, * FROM t1 WHERE t1 MATCH 'one' } {1 one}
           74  +
           75  +
    56     76   
    57     77   finish_test

Changes to test/fts5ea.test.

    52     52       {c2 : NEAR("one" "two", 10) AND c1 : "hello" + "world"}
    53     53   } {
    54     54     do_execsql_test 2.$tn {SELECT fts5_expr($expr, 'c1', 'c2')} [list $res]
    55     55   }
    56     56   
    57     57   breakpoint
    58     58   foreach {tn expr err} {
    59         -  1 {AND}                          {syntax error near "AND"}
    60         -  2 {abc def AND}                  {syntax error near ""}
    61         -  3 {abc OR AND}                   {syntax error near "AND"}
    62         -  4 {(a OR b) abc}                 {syntax error near "abc"}
    63         -  5 {NEaR (a b)}                   {syntax error near "NEaR"}
    64         -  6 {(a OR b) NOT c)}              {syntax error near ")"}
           59  +  1 {AND}                          {fts5: syntax error near "AND"}
           60  +  2 {abc def AND}                  {fts5: syntax error near ""}
           61  +  3 {abc OR AND}                   {fts5: syntax error near "AND"}
           62  +  4 {(a OR b) abc}                 {fts5: syntax error near "abc"}
           63  +  5 {NEaR (a b)}                   {fts5: syntax error near "NEaR"}
           64  +  6 {(a OR b) NOT c)}              {fts5: syntax error near ")"}
    65     65     7 {nosuch: a nosuch2: b}         {no such column: nosuch}
    66     66     8 {addr: a nosuch2: b}           {no such column: nosuch2}
    67     67   } {
    68     68     do_catchsql_test 3.$tn {SELECT fts5_expr($expr, 'name', 'addr')} [list 1 $err]
    69     69   }
    70     70   
    71     71   

Changes to test/permutations.test.

   217    217     fts4aa.test fts4content.test
   218    218     fts3conf.test fts3prefix.test fts3fault2.test fts3corrupt.test
   219    219     fts3corrupt2.test fts3first.test fts4langid.test fts4merge.test
   220    220     fts4check.test fts4unicode.test fts4noti.test
   221    221     fts3varint.test
   222    222     fts4growth.test fts4growth2.test
   223    223   }
          224  +
          225  +test_suite "fts5" -prefix "" -description {
          226  +  All FTS5 tests.
          227  +} -files {
          228  +  fts5aa.test fts5ab.test fts5ea.test
          229  +}
   224    230   
   225    231   test_suite "nofaultsim" -prefix "" -description {
   226    232     "Very" quick test suite. Runs in less than 5 minutes on a workstation. 
   227    233     This test suite is the same as the "quick" tests, except that some files
   228    234     that test malloc and IO errors are omitted.
   229    235   } -files [
   230    236     test_set $allquicktests -exclude *malloc* *ioerr* *fault*