}
  *ppCsr = (sqlite3_vtab_cursor*)pCsr;
  return rc;
}

static int fts5StmtType(int idxNum){
  if( FTS5_PLAN(idxNum)==FTS5_PLAN_SCAN ){
    return (idxNum&FTS5_ORDER_ASC) ? FTS5_STMT_SCAN_ASC : FTS5_STMT_SCAN_DESC;
  }
  return FTS5_STMT_LOOKUP;
}

/*
** This function is called after the cursor passed as the only argument
** is moved to point at a different row. It clears all cached data 
................................................................................
      }
      break;
  }
  
  return rc;
}

static int fts5CursorFirstSorted(Fts5Table *pTab, Fts5Cursor *pCsr, int bAsc){
  Fts5Config *pConfig = pTab->pConfig;
  Fts5Sorter *pSorter;
  int nPhrase;
  int nByte;
  int rc = SQLITE_OK;
  char *zSql;
  const char *zRank = pCsr->zRank;
................................................................................
  ** table, saving it creates a circular reference.
  **
  ** If SQLite a built-in statement cache, this wouldn't be a problem. */
  zSql = sqlite3_mprintf("SELECT rowid, rank FROM %Q.%Q ORDER BY %s(%s%s%s) %s",
      pConfig->zDb, pConfig->zName, zRank, pConfig->zName,
      (zRankArgs ? ", " : ""),
      (zRankArgs ? zRankArgs : ""),
      bAsc ? "ASC" : "DESC"
  );
  if( zSql==0 ){
    rc = SQLITE_NOMEM;
  }else{
    rc = sqlite3_prepare_v2(pConfig->db, zSql, -1, &pSorter->pStmt, 0);
    sqlite3_free(zSql);
  }
................................................................................
    sqlite3_free(pSorter);
    pCsr->pSorter = 0;
  }

  return rc;
}

static int fts5CursorFirst(Fts5Table *pTab, Fts5Cursor *pCsr, int bAsc){
  int rc;
  rc = sqlite3Fts5ExprFirst(pCsr->pExpr, pTab->pIndex, bAsc);
  if( sqlite3Fts5ExprEof(pCsr->pExpr) ){
    CsrFlagSet(pCsr, FTS5CSR_EOF);
  }
  fts5CsrNewrow(pCsr);
  return rc;
}

................................................................................
  int idxNum,                     /* Strategy index */
  const char *idxStr,             /* Unused */
  int nVal,                       /* Number of elements in apVal */
  sqlite3_value **apVal           /* Arguments for the indexing scheme */
){
  Fts5Table *pTab = (Fts5Table*)(pCursor->pVtab);
  Fts5Cursor *pCsr = (Fts5Cursor*)pCursor;
  int bAsc = ((idxNum & FTS5_ORDER_ASC) ? 1 : 0);
  int rc = SQLITE_OK;

  assert( nVal<=2 );
  assert( pCsr->pStmt==0 );
  assert( pCsr->pExpr==0 );
  assert( pCsr->csrflags==0 );
  assert( pCsr->pRank==0 );
................................................................................
    ** set to FTS5_PLAN_SORTED_MATCH). pSortCsr is the cursor that will
    ** return results to the user for this query. The current cursor 
    ** (pCursor) is used to execute the query issued by function 
    ** fts5CursorFirstSorted() above.  */
    assert( FTS5_PLAN(idxNum)==FTS5_PLAN_SCAN );
    pCsr->idxNum = FTS5_PLAN_SOURCE;
    pCsr->pExpr = pTab->pSortCsr->pExpr;
    rc = fts5CursorFirst(pTab, pCsr, bAsc);
  }else{
    int ePlan = FTS5_PLAN(idxNum);
    pCsr->idxNum = idxNum;
    if( ePlan==FTS5_PLAN_MATCH || ePlan==FTS5_PLAN_SORTED_MATCH ){
      const char *zExpr = (const char*)sqlite3_value_text(apVal[0]);

      rc = fts5CursorParseRank(pTab->pConfig, pCsr, (nVal==2 ? apVal[1] : 0));
................................................................................
          ** but a request for an internal parameter.  */
          rc = fts5SpecialMatch(pTab, pCsr, &zExpr[1]);
        }else{
          char **pzErr = &pTab->base.zErrMsg;
          rc = sqlite3Fts5ExprNew(pTab->pConfig, zExpr, &pCsr->pExpr, pzErr);
          if( rc==SQLITE_OK ){
            if( ePlan==FTS5_PLAN_MATCH ){
              rc = fts5CursorFirst(pTab, pCsr, bAsc);
            }else{
              rc = fts5CursorFirstSorted(pTab, pCsr, bAsc);
            }
          }
        }
      }
    }else{
      /* This is either a full-table scan (ePlan==FTS5_PLAN_SCAN) or a lookup
      ** by rowid (ePlan==FTS5_PLAN_ROWID).  */

  }
  *ppCsr = (sqlite3_vtab_cursor*)pCsr;
  return rc;
}

static int fts5StmtType(int idxNum){
  if( FTS5_PLAN(idxNum)==FTS5_PLAN_SCAN ){
    return (idxNum&FTS5_ORDER_DESC) ? FTS5_STMT_SCAN_DESC : FTS5_STMT_SCAN_ASC;
  }
  return FTS5_STMT_LOOKUP;
}

/*
** This function is called after the cursor passed as the only argument
** is moved to point at a different row. It clears all cached data 
................................................................................
      }
      break;
  }
  
  return rc;
}

static int fts5CursorFirstSorted(Fts5Table *pTab, Fts5Cursor *pCsr, int bDesc){
  Fts5Config *pConfig = pTab->pConfig;
  Fts5Sorter *pSorter;
  int nPhrase;
  int nByte;
  int rc = SQLITE_OK;
  char *zSql;
  const char *zRank = pCsr->zRank;
................................................................................
  ** table, saving it creates a circular reference.
  **
  ** If SQLite a built-in statement cache, this wouldn't be a problem. */
  zSql = sqlite3_mprintf("SELECT rowid, rank FROM %Q.%Q ORDER BY %s(%s%s%s) %s",
      pConfig->zDb, pConfig->zName, zRank, pConfig->zName,
      (zRankArgs ? ", " : ""),
      (zRankArgs ? zRankArgs : ""),
      bDesc ? "DESC" : "ASC"
  );
  if( zSql==0 ){
    rc = SQLITE_NOMEM;
  }else{
    rc = sqlite3_prepare_v2(pConfig->db, zSql, -1, &pSorter->pStmt, 0);
    sqlite3_free(zSql);
  }
................................................................................
    sqlite3_free(pSorter);
    pCsr->pSorter = 0;
  }

  return rc;
}

static int fts5CursorFirst(Fts5Table *pTab, Fts5Cursor *pCsr, int bDesc){
  int rc;
  rc = sqlite3Fts5ExprFirst(pCsr->pExpr, pTab->pIndex, bDesc);
  if( sqlite3Fts5ExprEof(pCsr->pExpr) ){
    CsrFlagSet(pCsr, FTS5CSR_EOF);
  }
  fts5CsrNewrow(pCsr);
  return rc;
}

................................................................................
  int idxNum,                     /* Strategy index */
  const char *idxStr,             /* Unused */
  int nVal,                       /* Number of elements in apVal */
  sqlite3_value **apVal           /* Arguments for the indexing scheme */
){
  Fts5Table *pTab = (Fts5Table*)(pCursor->pVtab);
  Fts5Cursor *pCsr = (Fts5Cursor*)pCursor;
  int bDesc = ((idxNum & FTS5_ORDER_DESC) ? 1 : 0);
  int rc = SQLITE_OK;

  assert( nVal<=2 );
  assert( pCsr->pStmt==0 );
  assert( pCsr->pExpr==0 );
  assert( pCsr->csrflags==0 );
  assert( pCsr->pRank==0 );
................................................................................
    ** set to FTS5_PLAN_SORTED_MATCH). pSortCsr is the cursor that will
    ** return results to the user for this query. The current cursor 
    ** (pCursor) is used to execute the query issued by function 
    ** fts5CursorFirstSorted() above.  */
    assert( FTS5_PLAN(idxNum)==FTS5_PLAN_SCAN );
    pCsr->idxNum = FTS5_PLAN_SOURCE;
    pCsr->pExpr = pTab->pSortCsr->pExpr;
    rc = fts5CursorFirst(pTab, pCsr, bDesc);
  }else{
    int ePlan = FTS5_PLAN(idxNum);
    pCsr->idxNum = idxNum;
    if( ePlan==FTS5_PLAN_MATCH || ePlan==FTS5_PLAN_SORTED_MATCH ){
      const char *zExpr = (const char*)sqlite3_value_text(apVal[0]);

      rc = fts5CursorParseRank(pTab->pConfig, pCsr, (nVal==2 ? apVal[1] : 0));
................................................................................
          ** but a request for an internal parameter.  */
          rc = fts5SpecialMatch(pTab, pCsr, &zExpr[1]);
        }else{
          char **pzErr = &pTab->base.zErrMsg;
          rc = sqlite3Fts5ExprNew(pTab->pConfig, zExpr, &pCsr->pExpr, pzErr);
          if( rc==SQLITE_OK ){
            if( ePlan==FTS5_PLAN_MATCH ){
              rc = fts5CursorFirst(pTab, pCsr, bDesc);
            }else{
              rc = fts5CursorFirstSorted(pTab, pCsr, bDesc);
            }
          }
        }
      }
    }else{
      /* This is either a full-table scan (ePlan==FTS5_PLAN_SCAN) or a lookup
      ** by rowid (ePlan==FTS5_PLAN_ROWID).  */

typedef struct Fts5Index Fts5Index;
typedef struct Fts5IndexIter Fts5IndexIter;

/*
** Values used as part of the flags argument passed to IndexQuery().
*/
#define FTS5INDEX_QUERY_PREFIX 0x0001       /* Prefix query */
#define FTS5INDEX_QUERY_ASC    0x0002       /* Docs in ascending rowid order */

/*
** Create/destroy an Fts5Index object.
*/
int sqlite3Fts5IndexOpen(Fts5Config *pConfig, int bCreate, Fts5Index**, char**);
int sqlite3Fts5IndexClose(Fts5Index *p, int bDestroy);

................................................................................
**************************************************************************/

/**************************************************************************
** Interface to code in fts5_hash.c. 
*/
typedef struct Fts5Hash Fts5Hash;








/*
** Create a hash table, free a hash table.
*/
int sqlite3Fts5HashNew(Fts5Hash**, int *pnSize);
void sqlite3Fts5HashFree(Fts5Hash*);

int sqlite3Fts5HashWrite(
................................................................................
  Fts5Hash*,
  void *pCtx,
  int (*xTerm)(void*, const char*, int),
  int (*xEntry)(void*, i64, const u8*, int),
  int (*xTermDone)(void*)
);








/*
** End of interface to code in fts5_hash.c.
**************************************************************************/

/**************************************************************************
................................................................................
  Fts5Config *pConfig, 
  const char *zExpr,
  Fts5Expr **ppNew, 
  char **pzErr
);

/*
** for(rc = sqlite3Fts5ExprFirst(pExpr, pIdx, bAsc);
**     rc==SQLITE_OK && 0==sqlite3Fts5ExprEof(pExpr);
**     rc = sqlite3Fts5ExprNext(pExpr)
** ){
**   // The document with rowid iRowid matches the expression!
**   i64 iRowid = sqlite3Fts5ExprRowid(pExpr);
** }
*/
int sqlite3Fts5ExprFirst(Fts5Expr*, Fts5Index *pIdx, int bAsc);
int sqlite3Fts5ExprNext(Fts5Expr*);
int sqlite3Fts5ExprEof(Fts5Expr*);
i64 sqlite3Fts5ExprRowid(Fts5Expr*);

void sqlite3Fts5ExprFree(Fts5Expr*);

/* Called during startup to register a UDF with SQLite */

typedef struct Fts5Index Fts5Index;
typedef struct Fts5IndexIter Fts5IndexIter;

/*
** Values used as part of the flags argument passed to IndexQuery().
*/
#define FTS5INDEX_QUERY_PREFIX 0x0001       /* Prefix query */
#define FTS5INDEX_QUERY_DESC    0x0002      /* Docs in descending rowid order */

/*
** Create/destroy an Fts5Index object.
*/
int sqlite3Fts5IndexOpen(Fts5Config *pConfig, int bCreate, Fts5Index**, char**);
int sqlite3Fts5IndexClose(Fts5Index *p, int bDestroy);

................................................................................
**************************************************************************/

/**************************************************************************
** Interface to code in fts5_hash.c. 
*/
typedef struct Fts5Hash Fts5Hash;

typedef struct Fts5Data Fts5Data;
struct Fts5Data {
  u8 *p;                          /* Pointer to buffer containing record */
  int n;                          /* Size of record in bytes */
  int nRef;                       /* Ref count */
};

/*
** Create a hash table, free a hash table.
*/
int sqlite3Fts5HashNew(Fts5Hash**, int *pnSize);
void sqlite3Fts5HashFree(Fts5Hash*);

int sqlite3Fts5HashWrite(
................................................................................
  Fts5Hash*,
  void *pCtx,
  int (*xTerm)(void*, const char*, int),
  int (*xEntry)(void*, i64, const u8*, int),
  int (*xTermDone)(void*)
);

int sqlite3Fts5HashQuery(
  Fts5Hash*,                      /* Hash table to query */
  const char *pTerm, int nTerm,   /* Query term */
  Fts5Data **ppData               /* OUT: Query result */
);


/*
** End of interface to code in fts5_hash.c.
**************************************************************************/

/**************************************************************************
................................................................................
  Fts5Config *pConfig, 
  const char *zExpr,
  Fts5Expr **ppNew, 
  char **pzErr
);

/*
** for(rc = sqlite3Fts5ExprFirst(pExpr, pIdx, bDesc);
**     rc==SQLITE_OK && 0==sqlite3Fts5ExprEof(pExpr);
**     rc = sqlite3Fts5ExprNext(pExpr)
** ){
**   // The document with rowid iRowid matches the expression!
**   i64 iRowid = sqlite3Fts5ExprRowid(pExpr);
** }
*/
int sqlite3Fts5ExprFirst(Fts5Expr*, Fts5Index *pIdx, int bDesc);
int sqlite3Fts5ExprNext(Fts5Expr*);
int sqlite3Fts5ExprEof(Fts5Expr*);
i64 sqlite3Fts5ExprRowid(Fts5Expr*);

void sqlite3Fts5ExprFree(Fts5Expr*);

/* Called during startup to register a UDF with SQLite */

void *sqlite3Fts5ParserAlloc(void *(*mallocProc)(size_t));
void sqlite3Fts5ParserFree(void*, void (*freeProc)(void*));
void sqlite3Fts5Parser(void*, int, Fts5Token, Fts5Parse*);

struct Fts5Expr {
  Fts5Index *pIndex;
  Fts5ExprNode *pRoot;
  int bAsc;
  int nPhrase;                    /* Number of phrases in expression */
  Fts5ExprPhrase **apExprPhrase;  /* Pointers to phrase objects */
};

/*
** eType:
**   Expression node type. Always one of:
................................................................................
    }
  }

  return SQLITE_OK;
}

/*
** Advance iterator pIter until it points to a value equal to or smaller
** than the initial value of *piMin. If this means the iterator points
** to a value smaller than *piMin, update *piMin to the new smallest value.
**
** If the iterator reaches EOF, set *pbEof to true before returning. If
** an error occurs, set *pRc to an error code. If either *pbEof or *pRc
** are set, return a non-zero value. Otherwise, return zero.
*/
static int fts5ExprAdvanceto(
  Fts5IndexIter *pIter,           /* Iterator to advance */
  int bAsc,                       /* True if iterator is "rowid ASC" */
  i64 *piLast,                    /* IN/OUT: Lastest rowid seen so far */
  int *pRc,                       /* OUT: Error code */
  int *pbEof                      /* OUT: Set to true if EOF */
){
  i64 iLast = *piLast;
  i64 iRowid;

  iRowid = sqlite3Fts5IterRowid(pIter);
  if( (bAsc==0 && iRowid>iLast) || (bAsc && iRowid<iLast) ){
    sqlite3Fts5IterNextFrom(pIter, iLast);
    if( sqlite3Fts5IterEof(pIter) ){
      *pbEof = 1;
      return 1;
    }
    iRowid = sqlite3Fts5IterRowid(pIter);
    assert( (bAsc==0 && iRowid<=iLast) || (bAsc==1 && iRowid>=iLast) );
  }
  *piLast = iRowid;

  return 0;
}

/*
................................................................................
){
  Fts5ExprNearset *pNear = pNode->pNear;
  int rc = SQLITE_OK;
  int i, j;                       /* Phrase and token index, respectively */
  i64 iLast;                      /* Lastest rowid any iterator points to */
  int bMatch;                     /* True if all terms are at the same rowid */

  /* Set iLast, the lastest rowid any iterator points to. If the iterator
  ** skips through rowids in the default descending order, this means the
  ** minimum rowid. Or, if the iterator is "ORDER BY rowid ASC", then it
  ** means the maximum rowid.  */
  iLast = sqlite3Fts5IterRowid(pNear->apPhrase[0]->aTerm[0].pIter);
  if( bFromValid && (iFrom>iLast)==(pExpr->bAsc!=0) ){

    iLast = iFrom;
  }

  do {
    bMatch = 1;
    for(i=0; i<pNear->nPhrase; i++){
      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
      for(j=0; j<pPhrase->nTerm; j++){
        Fts5IndexIter *pIter = pPhrase->aTerm[j].pIter;
        i64 iRowid = sqlite3Fts5IterRowid(pIter);
        if( iRowid!=iLast ) bMatch = 0;
        if( fts5ExprAdvanceto(pIter, pExpr->bAsc, &iLast, &rc, &pNode->bEof) ){
          return rc;
        }
      }
    }
  }while( bMatch==0 );

  pNode->iRowid = iLast;
................................................................................
  for(i=0; rc==SQLITE_OK && i<pNear->nPhrase; i++){
    pPhrase = pNear->apPhrase[i];
    for(j=0; j<pPhrase->nTerm; j++){
      pTerm = &pPhrase->aTerm[j];
      rc = sqlite3Fts5IndexQuery(
          pExpr->pIndex, pTerm->zTerm, strlen(pTerm->zTerm),
          (pTerm->bPrefix ? FTS5INDEX_QUERY_PREFIX : 0) |
          (pExpr->bAsc ? FTS5INDEX_QUERY_ASC : 0),
          &pTerm->pIter
      );
      assert( rc==SQLITE_OK || pTerm->pIter==0 );
      if( pTerm->pIter==0 || sqlite3Fts5IterEof(pTerm->pIter) ){
        pNode->bEof = 1;
        break;
      }
................................................................................
static int fts5NodeCompare(
  Fts5Expr *pExpr,
  Fts5ExprNode *p1, 
  Fts5ExprNode *p2
){
  if( p2->bEof ) return -1;
  if( p1->bEof ) return +1;
  if( pExpr->bAsc ){
    if( p1->iRowid<p2->iRowid ) return -1;
    return (p1->iRowid > p2->iRowid);
  }else{
    if( p1->iRowid>p2->iRowid ) return -1;
    return (p1->iRowid < p2->iRowid);
  }
}
................................................................................
        break;
      }

      case FTS5_AND: {
        Fts5ExprNode *p1 = pNode->pLeft;
        Fts5ExprNode *p2 = pNode->pRight;


        while( p1->bEof==0 && p2->bEof==0 && p2->iRowid!=p1->iRowid ){
          Fts5ExprNode *pAdv;
          assert( pExpr->bAsc==0 || pExpr->bAsc==1 );
          if( pExpr->bAsc==(p1->iRowid < p2->iRowid) ){

            pAdv = p1;
            if( bFromValid==0 || pExpr->bAsc==(p2->iRowid > iFrom) ){
              iFrom = p2->iRowid;
            }
          }else{
            pAdv = p2;
            if( bFromValid==0 || pExpr->bAsc==(p1->iRowid > iFrom) ){
              iFrom = p1->iRowid;
            }
          }
          rc = fts5ExprNodeNext(pExpr, pAdv, 1, iFrom);
          if( rc!=SQLITE_OK ) break;
        }
        if( p1->bEof || p2->bEof ){
................................................................................
  return rc;
}



/*
** Begin iterating through the set of documents in index pIdx matched by
** the MATCH expression passed as the first argument. If the "bAsc" parameter
** is passed a non-zero value, iteration is in ascending rowid order. Or,
** if it is zero, in descending order.
**
** Return SQLITE_OK if successful, or an SQLite error code otherwise. It
** is not considered an error if the query does not match any documents.
*/
int sqlite3Fts5ExprFirst(Fts5Expr *p, Fts5Index *pIdx, int bAsc){
  int rc = SQLITE_OK;
  if( p->pRoot ){
    p->pIndex = pIdx;
    p->bAsc = bAsc;
    rc = fts5ExprNodeFirst(p, p->pRoot);
  }
  return rc;
}

/*
** Move to the next document 

void *sqlite3Fts5ParserAlloc(void *(*mallocProc)(size_t));
void sqlite3Fts5ParserFree(void*, void (*freeProc)(void*));
void sqlite3Fts5Parser(void*, int, Fts5Token, Fts5Parse*);

struct Fts5Expr {
  Fts5Index *pIndex;
  Fts5ExprNode *pRoot;
  int bDesc;                      /* Iterate in descending docid order */
  int nPhrase;                    /* Number of phrases in expression */
  Fts5ExprPhrase **apExprPhrase;  /* Pointers to phrase objects */
};

/*
** eType:
**   Expression node type. Always one of:
................................................................................
    }
  }

  return SQLITE_OK;
}

/*
** Advance iterator pIter until it points to a value equal to or laster
** than the initial value of *piLast. If this means the iterator points
** to a value laster than *piLast, update *piLast to the new lastest value.
**
** If the iterator reaches EOF, set *pbEof to true before returning. If
** an error occurs, set *pRc to an error code. If either *pbEof or *pRc
** are set, return a non-zero value. Otherwise, return zero.
*/
static int fts5ExprAdvanceto(
  Fts5IndexIter *pIter,           /* Iterator to advance */
  int bDesc,                      /* True if iterator is "rowid DESC" */
  i64 *piLast,                    /* IN/OUT: Lastest rowid seen so far */
  int *pRc,                       /* OUT: Error code */
  int *pbEof                      /* OUT: Set to true if EOF */
){
  i64 iLast = *piLast;
  i64 iRowid;

  iRowid = sqlite3Fts5IterRowid(pIter);
  if( (bDesc==0 && iLast>iRowid) || (bDesc && iLast<iRowid) ){
    sqlite3Fts5IterNextFrom(pIter, iLast);
    if( sqlite3Fts5IterEof(pIter) ){
      *pbEof = 1;
      return 1;
    }
    iRowid = sqlite3Fts5IterRowid(pIter);
    assert( (bDesc==0 && iRowid>=iLast) || (bDesc==1 && iRowid<=iLast) );
  }
  *piLast = iRowid;

  return 0;
}

/*
................................................................................
){
  Fts5ExprNearset *pNear = pNode->pNear;
  int rc = SQLITE_OK;
  int i, j;                       /* Phrase and token index, respectively */
  i64 iLast;                      /* Lastest rowid any iterator points to */
  int bMatch;                     /* True if all terms are at the same rowid */

  /* Initialize iLast, the "lastest" rowid any iterator points to. If the
  ** iterator skips through rowids in the default ascending order, this means
  ** the maximum rowid. Or, if the iterator is "ORDER BY rowid DESC", then it
  ** means the minimum rowid.  */
  iLast = sqlite3Fts5IterRowid(pNear->apPhrase[0]->aTerm[0].pIter);
  if( bFromValid && (iFrom>iLast)==(pExpr->bDesc==0) ){
    assert( pExpr->bDesc || iFrom>=iLast );
    iLast = iFrom;
  }

  do {
    bMatch = 1;
    for(i=0; i<pNear->nPhrase; i++){
      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
      for(j=0; j<pPhrase->nTerm; j++){
        Fts5IndexIter *pIter = pPhrase->aTerm[j].pIter;
        i64 iRowid = sqlite3Fts5IterRowid(pIter);
        if( iRowid!=iLast ) bMatch = 0;
        if( fts5ExprAdvanceto(pIter, pExpr->bDesc, &iLast, &rc, &pNode->bEof) ){
          return rc;
        }
      }
    }
  }while( bMatch==0 );

  pNode->iRowid = iLast;
................................................................................
  for(i=0; rc==SQLITE_OK && i<pNear->nPhrase; i++){
    pPhrase = pNear->apPhrase[i];
    for(j=0; j<pPhrase->nTerm; j++){
      pTerm = &pPhrase->aTerm[j];
      rc = sqlite3Fts5IndexQuery(
          pExpr->pIndex, pTerm->zTerm, strlen(pTerm->zTerm),
          (pTerm->bPrefix ? FTS5INDEX_QUERY_PREFIX : 0) |
          (pExpr->bDesc ? FTS5INDEX_QUERY_DESC : 0),
          &pTerm->pIter
      );
      assert( rc==SQLITE_OK || pTerm->pIter==0 );
      if( pTerm->pIter==0 || sqlite3Fts5IterEof(pTerm->pIter) ){
        pNode->bEof = 1;
        break;
      }
................................................................................
static int fts5NodeCompare(
  Fts5Expr *pExpr,
  Fts5ExprNode *p1, 
  Fts5ExprNode *p2
){
  if( p2->bEof ) return -1;
  if( p1->bEof ) return +1;
  if( pExpr->bDesc==0 ){
    if( p1->iRowid<p2->iRowid ) return -1;
    return (p1->iRowid > p2->iRowid);
  }else{
    if( p1->iRowid>p2->iRowid ) return -1;
    return (p1->iRowid < p2->iRowid);
  }
}
................................................................................
        break;
      }

      case FTS5_AND: {
        Fts5ExprNode *p1 = pNode->pLeft;
        Fts5ExprNode *p2 = pNode->pRight;


        while( p1->bEof==0 && p2->bEof==0 && p2->iRowid!=p1->iRowid ){
          Fts5ExprNode *pAdv;
          assert( pExpr->bDesc==0 || pExpr->bDesc==1 );

          if( pExpr->bDesc==(p1->iRowid > p2->iRowid) ){
            pAdv = p1;
            if( bFromValid==0 || pExpr->bDesc==(p2->iRowid < iFrom) ){
              iFrom = p2->iRowid;
            }
          }else{
            pAdv = p2;
            if( bFromValid==0 || pExpr->bDesc==(p1->iRowid < iFrom) ){
              iFrom = p1->iRowid;
            }
          }
          rc = fts5ExprNodeNext(pExpr, pAdv, 1, iFrom);
          if( rc!=SQLITE_OK ) break;
        }
        if( p1->bEof || p2->bEof ){
................................................................................
  return rc;
}



/*
** Begin iterating through the set of documents in index pIdx matched by
** the MATCH expression passed as the first argument. If the "bDesc" parameter
** is passed a non-zero value, iteration is in descending rowid order. Or,
** if it is zero, in ascending order.
**
** Return SQLITE_OK if successful, or an SQLite error code otherwise. It
** is not considered an error if the query does not match any documents.
*/
int sqlite3Fts5ExprFirst(Fts5Expr *p, Fts5Index *pIdx, int bDesc){
  int rc = SQLITE_OK;
  if( p->pRoot ){
    p->pIndex = pIdx;
    p->bDesc = bDesc;
    rc = fts5ExprNodeFirst(p, p->pRoot);
  }
  return rc;
}

/*
** Move to the next document 

** nData:
**   Bytes of data written since iRowidOff.
*/
struct Fts5HashEntry {
  Fts5HashEntry *pNext;           /* Next hash entry with same hash-key */
  
  int nAlloc;                     /* Total size of allocation */
  int iRowidOff;                  /* Offset of last rowid written */
  int nData;                      /* Total bytes of data (incl. structure) */

  int iCol;                       /* Column of last value written */
  int iPos;                       /* Position of last value written */
  i64 iRowid;                     /* Rowid of last value written */
  char zKey[0];                   /* Nul-terminated entry key */
};












/*
** Allocate a new hash table.
*/
int sqlite3Fts5HashNew(Fts5Hash **ppNew, int *pnByte){
  int rc = SQLITE_OK;
  Fts5Hash *pNew;
................................................................................

  sqlite3_free(apOld);
  pHash->nSlot = nNew;
  pHash->aSlot = apNew;
  return SQLITE_OK;
}

/*
** Store the 32-bit integer passed as the second argument in buffer p.
*/
static int fts5PutNativeInt(u8 *p, int i){
  assert( sizeof(i)==4 );
  memcpy(p, &i, sizeof(i));
  return sizeof(i);
}

/*
** Read and return the 32-bit integer stored in buffer p.
*/
static int fts5GetNativeU32(u8 *p){
  int i;
  assert( sizeof(i)==4 );
  memcpy(&i, p, sizeof(i));
  return i;
}

int sqlite3Fts5HashWrite(
  Fts5Hash *pHash,
  i64 iRowid,                     /* Rowid for this entry */
  int iCol,                       /* Column token appears in (-ve -> delete) */
  int iPos,                       /* Position of token within column */
  const char *pToken, int nToken  /* Token to add or remove to or from index */
){
  unsigned int iHash = fts5HashKey(pHash->nSlot, pToken, nToken);
  Fts5HashEntry *p;
  u8 *pPtr;
  int nIncr = 0;                  /* Amount to increment (*pHash->pnByte) by */

  /* Attempt to locate an existing hash object */
  for(p=pHash->aSlot[iHash]; p; p=p->pNext){
    if( memcmp(p->zKey, pToken, nToken)==0 && p->zKey[nToken]==0 ) break;
  }

  /* If an existing hash entry cannot be found, create a new one. */
  if( p==0 ){
    int nByte = sizeof(Fts5HashEntry) + nToken + 1 + 64;
................................................................................

    p = (Fts5HashEntry*)sqlite3_malloc(nByte);
    if( !p ) return SQLITE_NOMEM;
    memset(p, 0, sizeof(Fts5HashEntry));
    p->nAlloc = nByte;
    memcpy(p->zKey, pToken, nToken);
    p->zKey[nToken] = '\0';
    p->iRowidOff = p->nData = nToken + 1 + sizeof(Fts5HashEntry);
    p->nData += sqlite3PutVarint(&((u8*)p)[p->nData], iRowid);


    p->iRowid = iRowid;
    p->pNext = pHash->aSlot[iHash];
    pHash->aSlot[iHash] = p;
    pHash->nEntry++;

    nIncr += p->nData;
  }

  /* Check there is enough space to append a new entry. Worst case scenario
  ** is:
  **
  **     + 4 bytes for the previous entry size field,
  **     + 9 bytes for a new rowid,

  **     + 1 byte for a "new column" byte,
  **     + 3 bytes for a new column number (16-bit max) as a varint,
  **     + 5 bytes for the new position offset (32-bit max).
  */
  if( (p->nAlloc - p->nData) < (4 + 9 + 1 + 3 + 5) ){
    int nNew = p->nAlloc * 2;
    Fts5HashEntry *pNew;
    Fts5HashEntry **pp;
    pNew = (Fts5HashEntry*)sqlite3_realloc(p, nNew);
    if( pNew==0 ) return SQLITE_NOMEM;
    pNew->nAlloc = nNew;
    for(pp=&pHash->aSlot[iHash]; *pp!=p; pp=&(*pp)->pNext);
................................................................................
  }
  pPtr = (u8*)p;
  nIncr -= p->nData;

  /* If this is a new rowid, append the 4-byte size field for the previous
  ** entry, and the new rowid for this entry.  */
  if( iRowid!=p->iRowid ){
    p->nData += fts5PutNativeInt(&pPtr[p->nData], p->nData - p->iRowidOff);
    p->iRowidOff = p->nData;
    p->nData += sqlite3PutVarint(&pPtr[p->nData], iRowid);


    p->iCol = 0;
    p->iPos = 0;
    p->iRowid = iRowid;
  }

  if( iCol>=0 ){
    /* Append a new column value, if necessary */
................................................................................
  int rc;

  rc = fts5HashEntrySort(pHash, &pList);
  if( rc==SQLITE_OK ){
    while( pList ){
      Fts5HashEntry *pNext = pList->pNext;
      if( rc==SQLITE_OK ){
        u8 *pPtr = (u8*)pList;
        int nKey = strlen(pList->zKey);
        int iOff = pList->iRowidOff;
        int iEnd = sizeof(Fts5HashEntry) + nKey + 1;
        int nByte = pList->nData - pList->iRowidOff;

        rc = xTerm(pCtx, pList->zKey, nKey);
        while( rc==SQLITE_OK && iOff ){
          int nVarint;
          i64 iRowid;
          nVarint = getVarint(&pPtr[iOff], (u64*)&iRowid);
          rc = xEntry(pCtx, iRowid, &pPtr[iOff+nVarint], nByte-nVarint);
          if( iOff==iEnd ){
            iOff = 0;
          }else{
            nByte = fts5GetNativeU32(&pPtr[iOff-sizeof(int)]);
            iOff = iOff - sizeof(int) - nByte;
          }
        }
        if( rc==SQLITE_OK ){
          rc = xTermDone(pCtx);
        }



      }
      sqlite3_free(pList);
      pList = pNext;
    }
  }
  return rc;
}

** nData:
**   Bytes of data written since iRowidOff.
*/
struct Fts5HashEntry {
  Fts5HashEntry *pNext;           /* Next hash entry with same hash-key */
  
  int nAlloc;                     /* Total size of allocation */
  int iSzPoslist;                 /* Offset of space for 4-byte poslist size */
  int nData;                      /* Total bytes of data (incl. structure) */

  int iCol;                       /* Column of last value written */
  int iPos;                       /* Position of last value written */
  i64 iRowid;                     /* Rowid of last value written */
  char zKey[0];                   /* Nul-terminated entry key */
};

/*
** Format value iVal as a 4-byte varint and write it to buffer a[]. 4 bytes
** are used even if the value could fit in a smaller amount of space. 
*/
static void fts5Put4ByteVarint(u8 *a, int iVal){
  a[0] = (0x80 | (u8)(iVal >> 21));
  a[1] = (0x80 | (u8)(iVal >> 14));
  a[2] = (0x80 | (u8)(iVal >>  7));
  a[3] = (0x7F & (u8)(iVal));
}

/*
** Allocate a new hash table.
*/
int sqlite3Fts5HashNew(Fts5Hash **ppNew, int *pnByte){
  int rc = SQLITE_OK;
  Fts5Hash *pNew;
................................................................................

  sqlite3_free(apOld);
  pHash->nSlot = nNew;
  pHash->aSlot = apNew;
  return SQLITE_OK;
}




















int sqlite3Fts5HashWrite(
  Fts5Hash *pHash,
  i64 iRowid,                     /* Rowid for this entry */
  int iCol,                       /* Column token appears in (-ve -> delete) */
  int iPos,                       /* Position of token within column */
  const char *pToken, int nToken  /* Token to add or remove to or from index */
){
  unsigned int iHash = fts5HashKey(pHash->nSlot, pToken, nToken);
  Fts5HashEntry *p;
  u8 *pPtr;
  int nIncr = 0;                  /* Amount to increment (*pHash->pnByte) by */

  /* Attempt to locate an existing hash entry */
  for(p=pHash->aSlot[iHash]; p; p=p->pNext){
    if( memcmp(p->zKey, pToken, nToken)==0 && p->zKey[nToken]==0 ) break;
  }

  /* If an existing hash entry cannot be found, create a new one. */
  if( p==0 ){
    int nByte = sizeof(Fts5HashEntry) + nToken + 1 + 64;
................................................................................

    p = (Fts5HashEntry*)sqlite3_malloc(nByte);
    if( !p ) return SQLITE_NOMEM;
    memset(p, 0, sizeof(Fts5HashEntry));
    p->nAlloc = nByte;
    memcpy(p->zKey, pToken, nToken);
    p->zKey[nToken] = '\0';
    p->nData = nToken + 1 + sizeof(Fts5HashEntry);
    p->nData += sqlite3PutVarint(&((u8*)p)[p->nData], iRowid);
    p->iSzPoslist = p->nData;
    p->nData += 4;
    p->iRowid = iRowid;
    p->pNext = pHash->aSlot[iHash];
    pHash->aSlot[iHash] = p;
    pHash->nEntry++;

    nIncr += p->nData;
  }

  /* Check there is enough space to append a new entry. Worst case scenario
  ** is:
  **

  **     + 9 bytes for a new rowid,
  **     + 4 bytes reserved for the "poslist size" varint.
  **     + 1 byte for a "new column" byte,
  **     + 3 bytes for a new column number (16-bit max) as a varint,
  **     + 5 bytes for the new position offset (32-bit max).
  */
  if( (p->nAlloc - p->nData) < (9 + 4 + 1 + 3 + 5) ){
    int nNew = p->nAlloc * 2;
    Fts5HashEntry *pNew;
    Fts5HashEntry **pp;
    pNew = (Fts5HashEntry*)sqlite3_realloc(p, nNew);
    if( pNew==0 ) return SQLITE_NOMEM;
    pNew->nAlloc = nNew;
    for(pp=&pHash->aSlot[iHash]; *pp!=p; pp=&(*pp)->pNext);
................................................................................
  }
  pPtr = (u8*)p;
  nIncr -= p->nData;

  /* If this is a new rowid, append the 4-byte size field for the previous
  ** entry, and the new rowid for this entry.  */
  if( iRowid!=p->iRowid ){
    assert( p->iSzPoslist>0 );
    fts5Put4ByteVarint(&pPtr[p->iSzPoslist], p->nData - p->iSzPoslist - 4);
    p->nData += sqlite3PutVarint(&pPtr[p->nData], iRowid - p->iRowid);
    p->iSzPoslist = p->nData;
    p->nData += 4;
    p->iCol = 0;
    p->iPos = 0;
    p->iRowid = iRowid;
  }

  if( iCol>=0 ){
    /* Append a new column value, if necessary */
................................................................................
  int rc;

  rc = fts5HashEntrySort(pHash, &pList);
  if( rc==SQLITE_OK ){
    while( pList ){
      Fts5HashEntry *pNext = pList->pNext;
      if( rc==SQLITE_OK ){
        const int nSz = pList->nData - pList->iSzPoslist - 4;
        const int nKey = strlen(pList->zKey);
        i64 iRowid = 0;
        u8 *pPtr = (u8*)pList;
        int iOff = sizeof(Fts5HashEntry) + nKey + 1;

        /* Fill in the final poslist size field */
        fts5Put4ByteVarint(&pPtr[pList->iSzPoslist], nSz);
        
        /* Issue the new-term callback */
        rc = xTerm(pCtx, pList->zKey, nKey);

        /* Issue the xEntry callbacks */
        while( rc==SQLITE_OK && iOff<pList->nData ){
          i64 iDelta;             /* Rowid delta value */
          int nPoslist;           /* Size of position list in bytes */
          iOff += getVarint(&pPtr[iOff], (u64*)&iDelta);
          iRowid += iDelta;
          iOff += fts5GetVarint32(&pPtr[iOff], nPoslist);
          rc = xEntry(pCtx, iRowid, &pPtr[iOff], nPoslist);
          iOff += nPoslist;
        }

        /* Issue the term-done callback */
        if( rc==SQLITE_OK ) rc = xTermDone(pCtx);
      }
      sqlite3_free(pList);
      pList = pNext;
    }
  }
  return rc;
}

**     incremental merge operations.
**
*/

#define FTS5_OPT_WORK_UNIT  1000  /* Number of leaf pages per optimize step */
#define FTS5_WORK_UNIT      64    /* Number of leaf pages in unit of work */

#define FTS5_MIN_DLIDX_SIZE  4    /* Add dlidx if this many empty pages */

/*
** Details:
**
** The %_data table managed by this module,
**
**     CREATE TABLE %_data(id INTEGER PRIMARY KEY, block BLOB);
................................................................................
** without overreading if the records are corrupt.
*/
#define FTS5_DATA_ZERO_PADDING 8

typedef struct Fts5BtreeIter Fts5BtreeIter;
typedef struct Fts5BtreeIterLevel Fts5BtreeIterLevel;
typedef struct Fts5ChunkIter Fts5ChunkIter;
typedef struct Fts5Data Fts5Data;
typedef struct Fts5DlidxIter Fts5DlidxIter;
typedef struct Fts5MultiSegIter Fts5MultiSegIter;
typedef struct Fts5NodeIter Fts5NodeIter;
typedef struct Fts5PageWriter Fts5PageWriter;
typedef struct Fts5PosIter Fts5PosIter;
typedef struct Fts5SegIter Fts5SegIter;
typedef struct Fts5DoclistIter Fts5DoclistIter;
................................................................................
  sqlite3_blob *pReader;          /* RO incr-blob open on %_data table */
  sqlite3_stmt *pWriter;          /* "INSERT ... %_data VALUES(?,?)" */
  sqlite3_stmt *pDeleter;         /* "DELETE FROM %_data ... id>=? AND id<=?" */
  int nRead;                      /* Total number of blocks read */
};

struct Fts5DoclistIter {
  int bAsc;
  u8 *a;
  int n;
  int i;

  /* Output variables. aPoslist==0 at EOF */
  i64 iRowid;
  u8 *aPoslist;
................................................................................
  Fts5Index *pIndex;
  Fts5Structure *pStruct;
  Fts5MultiSegIter *pMulti;
  Fts5DoclistIter *pDoclist;
  Fts5Buffer poslist;             /* Buffer containing current poslist */
};

/*
** A single record read from the %_data table.
*/
struct Fts5Data {
  u8 *p;                          /* Pointer to buffer containing record */
  int n;                          /* Size of record in bytes */
  int nRef;                       /* Ref count */
};

/*
** The contents of the "structure" record for each index are represented
** using an Fts5Structure record in memory. Which uses instances of the 
** other Fts5StructureXXX types as components.
*/
struct Fts5StructureSegment {
  int iSegid;                     /* Segment id */
................................................................................
*/
static void fts5DlidxIterFree(Fts5DlidxIter *pIter){
  if( pIter ){
    fts5DataRelease(pIter->pData);
    sqlite3_free(pIter);
  }
}






/*
** Load the next leaf page into the segment iterator.
*/
static void fts5SegIterNextPage(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5SegIter *pIter              /* Iterator to advance to next page */
................................................................................
    );
  }else{
    pIter->pLeaf = 0;
  }
}

/*
** Leave pIter->iLeafOffset as the offset to the size field of the first






** position list. The position list belonging to document pIter->iRowid.

*/
static void fts5SegIterLoadTerm(Fts5Index *p, Fts5SegIter *pIter, int nKeep){
  u8 *a = pIter->pLeaf->p;        /* Buffer to read data from */
  int iOff = pIter->iLeafOffset;  /* Offset to read at */
  int nNew;                       /* Bytes of new data */

  iOff += fts5GetVarint32(&a[iOff], nNew);
................................................................................
  if( p->rc==SQLITE_OK ){
    u8 *a = pIter->pLeaf->p;
    pIter->iLeafOffset = fts5GetU16(&a[2]);
    fts5SegIterLoadTerm(p, pIter, 0);
  }
}

static void fts5LeafHeader(Fts5Data *pLeaf, int *piRowid, int *piTerm){
  *piRowid = (int)fts5GetU16(&pLeaf->p[0]);
  *piTerm = (int)fts5GetU16(&pLeaf->p[2]);
}

/*
** This function is only ever called on iterators created by calls to
** Fts5IndexQuery() with the FTS5INDEX_QUERY_ASC flag set.
**
** When this function is called, iterator pIter points to the first rowid
** on the current leaf associated with the term being queried. This function
** advances it to point to the last such rowid and, if necessary, initializes
................................................................................
    int nPos;

    i += fts5GetVarint32(&a[i], nPos);
    i += nPos;
    if( i>=n ) break;
    i += getVarint(&a[i], (u64*)&iDelta);
    if( iDelta==0 ) break;
    pIter->iRowid -= iDelta;

    if( iRowidOffset>=pIter->nRowidOffset ){
      int nNew = pIter->nRowidOffset + 8;
      int *aNew = (int*)sqlite3_realloc(pIter->aRowidOffset, nNew*sizeof(int));
      if( aNew==0 ){
        p->rc = SQLITE_NOMEM;
        break;
................................................................................
  int bRet = 0;
  Fts5Data *pLeaf = pIter->pLeaf;
  if( p->rc==SQLITE_OK && pLeaf ){
    if( pIter->iLeafOffset<pLeaf->n ){
      bRet = (pLeaf->p[pIter->iLeafOffset]==0x00);
    }else{
      Fts5Data *pNew = fts5DataRead(p, FTS5_SEGMENT_ROWID(
            pIter->iIdx, pIter->pSeg->iSegid, 0, pIter->iLeafPgno
      ));
      if( pNew ){
        bRet = (pNew->p[4]==0x00);
        fts5DataRelease(pNew);
      }
    }
  }
................................................................................
        i64 iDelta;
        pIter->iRowidOffset--;

        pIter->iLeafOffset = iOff = pIter->aRowidOffset[pIter->iRowidOffset];
        iOff += fts5GetVarint32(&a[iOff], nPos);
        iOff += nPos;
        getVarint(&a[iOff], (u64*)&iDelta);
        pIter->iRowid += iDelta;
      }else{
        fts5SegIterReverseNewPage(p, pIter);
      }
    }else{
      Fts5Data *pLeaf = pIter->pLeaf;
      int iOff;
      int bNewTerm = 0;
................................................................................
          if( iOff>=n ){
            fts5SegIterNextPage(p, pIter);
            pIter->iLeafOffset = 4;
          }else if( iOff!=fts5GetU16(&a[2]) ){
            pIter->iLeafOffset += fts5GetVarint32(&a[iOff], nKeep);
          }
        }else{
          pIter->iRowid -= iDelta;
        }
      }else{
        iOff = 0;
        /* Next entry is not on the current page */
        while( iOff==0 ){
          fts5SegIterNextPage(p, pIter);
          pLeaf = pIter->pLeaf;
................................................................................
  Fts5SegIter *pIter              /* Object to populate */
){
  int iPg = 1;
  int h;
  int bGe = ((flags & FTS5INDEX_QUERY_PREFIX) && iIdx==0);
  int bDlidx = 0;                 /* True if there is a doclist-index */

  assert( bGe==0 || (flags & FTS5INDEX_QUERY_ASC)==0 );
  assert( pTerm && nTerm );
  memset(pIter, 0, sizeof(*pIter));
  pIter->pSeg = pSeg;
  pIter->iIdx = iIdx;

  /* This block sets stack variable iPg to the leaf page number that may
  ** contain term (pTerm/nTerm), if it is present in the segment. */
................................................................................
      pIter->pLeaf = 0;
    }
  }

  if( p->rc==SQLITE_OK && bGe==0 ){
    pIter->flags |= FTS5_SEGITER_ONETERM;
    if( pIter->pLeaf ){
      if( flags & FTS5INDEX_QUERY_ASC ){
        pIter->flags |= FTS5_SEGITER_REVERSE;
      }
      if( bDlidx ){
        fts5SegIterLoadDlidx(p, iIdx, pIter);
      }
      if( flags & FTS5INDEX_QUERY_ASC ){
        fts5SegIterReverse(p, iIdx, pIter);
      }
    }
  }
}

/*
................................................................................
    iRes = i1;
  }else{
    int res = fts5BufferCompare(&p1->term, &p2->term);
    if( res==0 ){
      assert( i2>i1 );
      assert( i2!=0 );
      if( p1->iRowid==p2->iRowid ) return i2;
      res = ((p1->iRowid < p2->iRowid)==pIter->bRev) ? -1 : +1;
    }
    assert( res!=0 );
    if( res<0 ){
      iRes = i1;
    }else{
      iRes = i2;
    }
  }

  pIter->aFirst[iOut] = iRes;
  return 0;
}

/*
** Free the iterator object passed as the second argument.
*/
static void fts5MultiIterFree(Fts5Index *p, Fts5MultiSegIter *pIter){
  if( pIter ){
    int i;
    for(i=0; i<pIter->nSeg; i++){
      fts5SegIterClear(&pIter->aSeg[i]);
    }
    sqlite3_free(pIter);
  }
}

static void fts5MultiIterAdvanced(
  Fts5Index *p,                   /* FTS5 backend to iterate within */
  Fts5MultiSegIter *pIter,        /* Iterator to update aFirst[] array for */
  int iChanged,                   /* Index of sub-iterator just advanced */
  int iMinset                     /* Minimum entry in aFirst[] to set */
){
  int i;
  for(i=(pIter->nSeg+iChanged)/2; i>=iMinset && p->rc==SQLITE_OK; i=i/2){
    int iEq;
    if( (iEq = fts5MultiIterDoCompare(pIter, i)) ){
      fts5SegIterNext(p, &pIter->aSeg[iEq]);
      i = pIter->nSeg + iEq;
    }
  }
}

/*
** Move the seg-iter so that it points to the first rowid on page iLeafPgno.
** It is an error if leaf iLeafPgno contains no rowid.
*/
static void fts5SegIterGotoPage(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5SegIter *pIter,             /* Iterator to advance */
................................................................................
    if( pIter->pLeaf==0 ) break;
    if( bRev==0 && pIter->iRowid<=iMatch ) break;
    if( bRev!=0 && pIter->iRowid>=iMatch ) break;
    bMove = 1;
  }
}































/*
** Move the iterator to the next entry. 
**
** If an error occurs, an error code is left in Fts5Index.rc. It is not 
** considered an error if the iterator reaches EOF, or if it is already at 
** EOF when this function is called.
*/
................................................................................
      sizeof(Fts5SegIter) * nSlot +       /* pNew->aSeg[] */
      sizeof(u16) * nSlot                 /* pNew->aFirst[] */
  );
  if( pNew==0 ) return;
  pNew->nSeg = nSlot;
  pNew->aSeg = (Fts5SegIter*)&pNew[1];
  pNew->aFirst = (u16*)&pNew->aSeg[nSlot];
  pNew->bRev = (0!=(flags & FTS5INDEX_QUERY_ASC));
  pNew->bSkipEmpty = bSkipEmpty;

  /* Initialize each of the component segment iterators. */
  if( iLevel<0 ){
    Fts5StructureLevel *pEnd = &pStruct->aLevel[pStruct->nLevel];
    for(pLvl=&pStruct->aLevel[0]; pLvl<pEnd; pLvl++){
      for(iSeg=pLvl->nSeg-1; iSeg>=0; iSeg--){
................................................................................
  i64 iMatch
){
  while( 1 ){
    i64 iRowid;
    fts5MultiIterNext(p, pIter, 1, iMatch);
    if( fts5MultiIterEof(p, pIter) ) break;
    iRowid = fts5MultiIterRowid(pIter);
    if( pIter->bRev==0 && iRowid<=iMatch ) break;
    if( pIter->bRev!=0 && iRowid>=iMatch ) break;
  }
}

/*
** Return a pointer to a buffer containing the term associated with the 
** entry that the iterator currently points to.
*/
................................................................................
      fts5WriteDlidxAppend(p, pWriter, iRowid);
    }

    /* Write the docid. */
    if( pWriter->bFirstRowidInDoclist || pWriter->bFirstRowidInPage ){
      fts5BufferAppendVarint(&p->rc, &pPage->buf, iRowid);
    }else{
      assert( p->rc || iRowid<pWriter->iPrevRowid );
      fts5BufferAppendVarint(&p->rc, &pPage->buf, pWriter->iPrevRowid - iRowid);
    }
    pWriter->iPrevRowid = iRowid;
    pWriter->bFirstRowidInDoclist = 0;
    pWriter->bFirstRowidInPage = 0;

    if( pPage->buf.n>=p->pConfig->pgsz ){
      fts5WriteFlushLeaf(p, pWriter);
................................................................................
}

static void fts5DoclistIterNext(Fts5DoclistIter *pIter){
  if( pIter->i<pIter->n ){
    if( pIter->i ){
      i64 iDelta;
      pIter->i += getVarint(&pIter->a[pIter->i], (u64*)&iDelta);
      if( pIter->bAsc ){
        pIter->iRowid += iDelta;
      }else{
        pIter->iRowid -= iDelta;
      }
    }else{
      pIter->i += getVarint(&pIter->a[pIter->i], (u64*)&pIter->iRowid);
    }
    pIter->i += fts5GetVarint32(&pIter->a[pIter->i], pIter->nPoslist);
    pIter->aPoslist = &pIter->a[pIter->i];
    pIter->i += pIter->nPoslist;
................................................................................
  }else{
    pIter->aPoslist = 0;
  }
}

static void fts5DoclistIterInit(
  Fts5Buffer *pBuf, 
  int bAsc, 
  Fts5DoclistIter *pIter
){
  memset(pIter, 0, sizeof(*pIter));
  pIter->a = pBuf->p;
  pIter->n = pBuf->n;
  pIter->bAsc = bAsc;
  fts5DoclistIterNext(pIter);
}

/*
** Append a doclist to buffer pBuf.
*/
static void fts5MergeAppendDocid(
  int *pRc,                       /* IN/OUT: Error code */
  int bAsc,
  Fts5Buffer *pBuf,               /* Buffer to write to */
  i64 *piLastRowid,               /* IN/OUT: Previous rowid written (if any) */
  i64 iRowid                      /* Rowid to append */
){
  if( pBuf->n==0 ){
    fts5BufferAppendVarint(pRc, pBuf, iRowid);
  }else if( bAsc==0 ){
    fts5BufferAppendVarint(pRc, pBuf, *piLastRowid - iRowid);
  }else{
    fts5BufferAppendVarint(pRc, pBuf, iRowid - *piLastRowid);
  }
  *piLastRowid = iRowid;
}

................................................................................
** returning.
**
** If an error occurs, an error code is left in p->rc. If an error has
** already occurred, this function is a no-op.
*/
static void fts5MergePrefixLists(
  Fts5Index *p,                   /* FTS5 backend object */
  int bAsc,
  Fts5Buffer *p1,                 /* First list to merge */
  Fts5Buffer *p2                  /* Second list to merge */
){
  if( p2->n ){
    i64 iLastRowid = 0;
    Fts5DoclistIter i1;
    Fts5DoclistIter i2;
    Fts5Buffer out;
    Fts5Buffer tmp;
    memset(&out, 0, sizeof(out));
    memset(&tmp, 0, sizeof(tmp));

    fts5DoclistIterInit(p1, bAsc, &i1);
    fts5DoclistIterInit(p2, bAsc, &i2);
    while( i1.aPoslist!=0 || i2.aPoslist!=0 ){
      if( i2.aPoslist==0 || (i1.aPoslist && 
           ( (!bAsc && i1.iRowid>i2.iRowid) || (bAsc && i1.iRowid<i2.iRowid) )
      )){
        /* Copy entry from i1 */
        fts5MergeAppendDocid(&p->rc, bAsc, &out, &iLastRowid, i1.iRowid);
        fts5BufferAppendVarint(&p->rc, &out, i1.nPoslist);
        fts5BufferAppendBlob(&p->rc, &out, i1.nPoslist, i1.aPoslist);
        fts5DoclistIterNext(&i1);
      }
      else if( i1.aPoslist==0 || i2.iRowid!=i1.iRowid ){
        /* Copy entry from i2 */
        fts5MergeAppendDocid(&p->rc, bAsc, &out, &iLastRowid, i2.iRowid);
        fts5BufferAppendVarint(&p->rc, &out, i2.nPoslist);
        fts5BufferAppendBlob(&p->rc, &out, i2.nPoslist, i2.aPoslist);
        fts5DoclistIterNext(&i2);
      }
      else{
        Fts5PoslistReader r1;
        Fts5PoslistReader r2;
        Fts5PoslistWriter writer;

        memset(&writer, 0, sizeof(writer));

        /* Merge the two position lists. */ 
        fts5MergeAppendDocid(&p->rc, bAsc, &out, &iLastRowid, i2.iRowid);
        fts5BufferZero(&tmp);
        sqlite3Fts5PoslistReaderInit(-1, i1.aPoslist, i1.nPoslist, &r1);
        sqlite3Fts5PoslistReaderInit(-1, i2.aPoslist, i2.nPoslist, &r2);
        while( p->rc==SQLITE_OK && (r1.bEof==0 || r2.bEof==0) ){
          i64 iNew;
          if( r2.bEof || (r1.bEof==0 && r1.iPos<r2.iPos) ){
            iNew = r1.iPos;
................................................................................
  Fts5Buffer tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

static void fts5SetupPrefixIter(
  Fts5Index *p,                   /* Index to read from */
  int bAsc,                       /* True for "ORDER BY rowid ASC" */
  const u8 *pToken,               /* Buffer containing prefix to match */
  int nToken,                     /* Size of buffer pToken in bytes */
  Fts5IndexIter *pIter            /* Populate this object */
){
  Fts5Structure *pStruct;
  Fts5Buffer *aBuf;
  const int nBuf = 32;
................................................................................
      i64 iRowid = fts5MultiIterRowid(p1);
      int nTerm;
      const u8 *pTerm = fts5MultiIterTerm(p1, &nTerm);
      assert( memcmp(pToken, pTerm, MIN(nToken, nTerm))<=0 );
      if( nTerm<nToken || memcmp(pToken, pTerm, nToken) ) break;

      if( doclist.n>0 
       && ((!bAsc && iRowid>=iLastRowid) || (bAsc && iRowid<=iLastRowid))
      ){

        for(i=0; p->rc==SQLITE_OK && doclist.n; i++){
          assert( i<nBuf );
          if( aBuf[i].n==0 ){
            fts5BufferSwap(&doclist, &aBuf[i]);
            fts5BufferZero(&doclist);
          }else{
            fts5MergePrefixLists(p, bAsc, &doclist, &aBuf[i]);
            fts5BufferZero(&aBuf[i]);
          }
        }
      }
      if( doclist.n==0 ){
        fts5BufferAppendVarint(&p->rc, &doclist, iRowid);
      }else if( bAsc==0 ){
        fts5BufferAppendVarint(&p->rc, &doclist, iLastRowid - iRowid);
      }else{
        fts5BufferAppendVarint(&p->rc, &doclist, iRowid - iLastRowid);
      }
      iLastRowid = iRowid;
      fts5MultiIterPoslist(p, p1, 1, &doclist);
    }

    for(i=0; i<nBuf; i++){
      fts5MergePrefixLists(p, bAsc, &doclist, &aBuf[i]);
      fts5BufferFree(&aBuf[i]);
    }
    fts5MultiIterFree(p, p1);

    pDoclist = (Fts5DoclistIter*)fts5IdxMalloc(p, sizeof(Fts5DoclistIter));
    if( !pDoclist ){
      fts5BufferFree(&doclist);
    }else{
      pIter->pDoclist = pDoclist;
      fts5DoclistIterInit(&doclist, bAsc, pIter->pDoclist);
    }
  }

  fts5StructureRelease(pStruct);
  sqlite3_free(aBuf);
}

................................................................................
      pRet->pStruct = fts5StructureRead(p, iIdx);
      if( pRet->pStruct ){
        fts5MultiIterNew(p, pRet->pStruct, 
            iIdx, 1, flags, (const u8*)pToken, nToken, -1, 0, &pRet->pMulti
        );
      }
    }else{
      int bAsc = (flags & FTS5INDEX_QUERY_ASC)!=0;
      fts5SetupPrefixIter(p, bAsc, (const u8*)pToken, nToken, pRet);
    }
  }

  if( p->rc ){
    sqlite3Fts5IterClose(pRet);
    pRet = 0;
  }
................................................................................
** matching rowid that occurs at or after iMatch. The definition of "at 
** or after" depends on whether this iterator iterates in ascending or 
** descending rowid order.
*/
static void fts5DoclistIterNextFrom(Fts5DoclistIter *p, i64 iMatch){
  do{
    i64 iRowid = p->iRowid;
    if( p->bAsc!=0 && iRowid>=iMatch ) break;
    if( p->bAsc==0 && iRowid<=iMatch ) break;
    fts5DoclistIterNext(p);
  }while( p->aPoslist );
}

/*
** Move to the next matching rowid that occurs at or after iMatch. The
** definition of "at or after" depends on whether this iterator iterates
................................................................................
    int nPos;
    iOff += fts5GetVarint32(&a[iOff], nPos);
    iOff += fts5DecodePoslist(pRc, pBuf, &a[iOff], MIN(n-iOff, nPos));
    if( iOff<n ){
      i64 iDelta;
      iOff += sqlite3GetVarint(&a[iOff], (u64*)&iDelta);
      if( iDelta==0 ) return iOff;
      iDocid -= iDelta;
      sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " rowid=%lld", iDocid);
    }
  }

  return iOff;
}

................................................................................
        iOff = iRowidOff;
      }else if( iTermOff ){
        iOff = iTermOff;
      }else{
        iOff = n;
      }
      fts5DecodePoslist(&rc, &s, &a[4], iOff-4);


      assert( iRowidOff==0 || iOff==iRowidOff );
      if( iRowidOff ){
        iOff += fts5DecodeDoclist(&rc, &s, &a[iOff], n-iOff);
      }

      assert( iTermOff==0 || iOff==iTermOff );

**     incremental merge operations.
**
*/

#define FTS5_OPT_WORK_UNIT  1000  /* Number of leaf pages per optimize step */
#define FTS5_WORK_UNIT      64    /* Number of leaf pages in unit of work */

#define FTS5_MIN_DLIDX_SIZE 4000  /* Add dlidx if this many empty pages */

/*
** Details:
**
** The %_data table managed by this module,
**
**     CREATE TABLE %_data(id INTEGER PRIMARY KEY, block BLOB);
................................................................................
** without overreading if the records are corrupt.
*/
#define FTS5_DATA_ZERO_PADDING 8

typedef struct Fts5BtreeIter Fts5BtreeIter;
typedef struct Fts5BtreeIterLevel Fts5BtreeIterLevel;
typedef struct Fts5ChunkIter Fts5ChunkIter;

typedef struct Fts5DlidxIter Fts5DlidxIter;
typedef struct Fts5MultiSegIter Fts5MultiSegIter;
typedef struct Fts5NodeIter Fts5NodeIter;
typedef struct Fts5PageWriter Fts5PageWriter;
typedef struct Fts5PosIter Fts5PosIter;
typedef struct Fts5SegIter Fts5SegIter;
typedef struct Fts5DoclistIter Fts5DoclistIter;
................................................................................
  sqlite3_blob *pReader;          /* RO incr-blob open on %_data table */
  sqlite3_stmt *pWriter;          /* "INSERT ... %_data VALUES(?,?)" */
  sqlite3_stmt *pDeleter;         /* "DELETE FROM %_data ... id>=? AND id<=?" */
  int nRead;                      /* Total number of blocks read */
};

struct Fts5DoclistIter {
  int bDesc;                      /* True for DESC order, false for ASC */
  u8 *a;
  int n;
  int i;

  /* Output variables. aPoslist==0 at EOF */
  i64 iRowid;
  u8 *aPoslist;
................................................................................
  Fts5Index *pIndex;
  Fts5Structure *pStruct;
  Fts5MultiSegIter *pMulti;
  Fts5DoclistIter *pDoclist;
  Fts5Buffer poslist;             /* Buffer containing current poslist */
};










/*
** The contents of the "structure" record for each index are represented
** using an Fts5Structure record in memory. Which uses instances of the 
** other Fts5StructureXXX types as components.
*/
struct Fts5StructureSegment {
  int iSegid;                     /* Segment id */
................................................................................
*/
static void fts5DlidxIterFree(Fts5DlidxIter *pIter){
  if( pIter ){
    fts5DataRelease(pIter->pData);
    sqlite3_free(pIter);
  }
}

static void fts5LeafHeader(Fts5Data *pLeaf, int *piRowid, int *piTerm){
  *piRowid = (int)fts5GetU16(&pLeaf->p[0]);
  *piTerm = (int)fts5GetU16(&pLeaf->p[2]);
}

/*
** Load the next leaf page into the segment iterator.
*/
static void fts5SegIterNextPage(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5SegIter *pIter              /* Iterator to advance to next page */
................................................................................
    );
  }else{
    pIter->pLeaf = 0;
  }
}

/*
** Fts5SegIter.iLeafOffset currently points to the first byte of the 
** "nSuffix" field of a term. Function parameter nKeep contains the value
** of the "nPrefix" field (if there was one - it is passed 0 if this is
** the first term in the segment).
**
** This function populates (Fts5SegIter.term) and (Fts5SegIter.iRowid)
** accordingly and leaves (Fts5SegIter.iLeafOffset) set to the offset to 
** the size field of the first position list. The position list belonging 
** to document (Fts5SegIter.iRowid).
*/
static void fts5SegIterLoadTerm(Fts5Index *p, Fts5SegIter *pIter, int nKeep){
  u8 *a = pIter->pLeaf->p;        /* Buffer to read data from */
  int iOff = pIter->iLeafOffset;  /* Offset to read at */
  int nNew;                       /* Bytes of new data */

  iOff += fts5GetVarint32(&a[iOff], nNew);
................................................................................
  if( p->rc==SQLITE_OK ){
    u8 *a = pIter->pLeaf->p;
    pIter->iLeafOffset = fts5GetU16(&a[2]);
    fts5SegIterLoadTerm(p, pIter, 0);
  }
}






/*
** This function is only ever called on iterators created by calls to
** Fts5IndexQuery() with the FTS5INDEX_QUERY_ASC flag set.
**
** When this function is called, iterator pIter points to the first rowid
** on the current leaf associated with the term being queried. This function
** advances it to point to the last such rowid and, if necessary, initializes
................................................................................
    int nPos;

    i += fts5GetVarint32(&a[i], nPos);
    i += nPos;
    if( i>=n ) break;
    i += getVarint(&a[i], (u64*)&iDelta);
    if( iDelta==0 ) break;
    pIter->iRowid += iDelta;

    if( iRowidOffset>=pIter->nRowidOffset ){
      int nNew = pIter->nRowidOffset + 8;
      int *aNew = (int*)sqlite3_realloc(pIter->aRowidOffset, nNew*sizeof(int));
      if( aNew==0 ){
        p->rc = SQLITE_NOMEM;
        break;
................................................................................
  int bRet = 0;
  Fts5Data *pLeaf = pIter->pLeaf;
  if( p->rc==SQLITE_OK && pLeaf ){
    if( pIter->iLeafOffset<pLeaf->n ){
      bRet = (pLeaf->p[pIter->iLeafOffset]==0x00);
    }else{
      Fts5Data *pNew = fts5DataRead(p, FTS5_SEGMENT_ROWID(
            pIter->iIdx, pIter->pSeg->iSegid, 0, pIter->iLeafPgno+1
      ));
      if( pNew ){
        bRet = (pNew->p[4]==0x00);
        fts5DataRelease(pNew);
      }
    }
  }
................................................................................
        i64 iDelta;
        pIter->iRowidOffset--;

        pIter->iLeafOffset = iOff = pIter->aRowidOffset[pIter->iRowidOffset];
        iOff += fts5GetVarint32(&a[iOff], nPos);
        iOff += nPos;
        getVarint(&a[iOff], (u64*)&iDelta);
        pIter->iRowid -= iDelta;
      }else{
        fts5SegIterReverseNewPage(p, pIter);
      }
    }else{
      Fts5Data *pLeaf = pIter->pLeaf;
      int iOff;
      int bNewTerm = 0;
................................................................................
          if( iOff>=n ){
            fts5SegIterNextPage(p, pIter);
            pIter->iLeafOffset = 4;
          }else if( iOff!=fts5GetU16(&a[2]) ){
            pIter->iLeafOffset += fts5GetVarint32(&a[iOff], nKeep);
          }
        }else{
          pIter->iRowid += iDelta;
        }
      }else{
        iOff = 0;
        /* Next entry is not on the current page */
        while( iOff==0 ){
          fts5SegIterNextPage(p, pIter);
          pLeaf = pIter->pLeaf;
................................................................................
  Fts5SegIter *pIter              /* Object to populate */
){
  int iPg = 1;
  int h;
  int bGe = ((flags & FTS5INDEX_QUERY_PREFIX) && iIdx==0);
  int bDlidx = 0;                 /* True if there is a doclist-index */

  assert( bGe==0 || (flags & FTS5INDEX_QUERY_DESC)==0 );
  assert( pTerm && nTerm );
  memset(pIter, 0, sizeof(*pIter));
  pIter->pSeg = pSeg;
  pIter->iIdx = iIdx;

  /* This block sets stack variable iPg to the leaf page number that may
  ** contain term (pTerm/nTerm), if it is present in the segment. */
................................................................................
      pIter->pLeaf = 0;
    }
  }

  if( p->rc==SQLITE_OK && bGe==0 ){
    pIter->flags |= FTS5_SEGITER_ONETERM;
    if( pIter->pLeaf ){
      if( flags & FTS5INDEX_QUERY_DESC ){
        pIter->flags |= FTS5_SEGITER_REVERSE;
      }
      if( bDlidx ){
        fts5SegIterLoadDlidx(p, iIdx, pIter);
      }
      if( flags & FTS5INDEX_QUERY_DESC ){
        fts5SegIterReverse(p, iIdx, pIter);
      }
    }
  }
}

/*
................................................................................
    iRes = i1;
  }else{
    int res = fts5BufferCompare(&p1->term, &p2->term);
    if( res==0 ){
      assert( i2>i1 );
      assert( i2!=0 );
      if( p1->iRowid==p2->iRowid ) return i2;
      res = ((p1->iRowid > p2->iRowid)==pIter->bRev) ? -1 : +1;
    }
    assert( res!=0 );
    if( res<0 ){
      iRes = i1;
    }else{
      iRes = i2;
    }
  }

  pIter->aFirst[iOut] = iRes;
  return 0;
}






























/*
** Move the seg-iter so that it points to the first rowid on page iLeafPgno.
** It is an error if leaf iLeafPgno contains no rowid.
*/
static void fts5SegIterGotoPage(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5SegIter *pIter,             /* Iterator to advance */
................................................................................
    if( pIter->pLeaf==0 ) break;
    if( bRev==0 && pIter->iRowid<=iMatch ) break;
    if( bRev!=0 && pIter->iRowid>=iMatch ) break;
    bMove = 1;
  }
}


/*
** Free the iterator object passed as the second argument.
*/
static void fts5MultiIterFree(Fts5Index *p, Fts5MultiSegIter *pIter){
  if( pIter ){
    int i;
    for(i=0; i<pIter->nSeg; i++){
      fts5SegIterClear(&pIter->aSeg[i]);
    }
    sqlite3_free(pIter);
  }
}

static void fts5MultiIterAdvanced(
  Fts5Index *p,                   /* FTS5 backend to iterate within */
  Fts5MultiSegIter *pIter,        /* Iterator to update aFirst[] array for */
  int iChanged,                   /* Index of sub-iterator just advanced */
  int iMinset                     /* Minimum entry in aFirst[] to set */
){
  int i;
  for(i=(pIter->nSeg+iChanged)/2; i>=iMinset && p->rc==SQLITE_OK; i=i/2){
    int iEq;
    if( (iEq = fts5MultiIterDoCompare(pIter, i)) ){
      fts5SegIterNext(p, &pIter->aSeg[iEq]);
      i = pIter->nSeg + iEq;
    }
  }
}

/*
** Move the iterator to the next entry. 
**
** If an error occurs, an error code is left in Fts5Index.rc. It is not 
** considered an error if the iterator reaches EOF, or if it is already at 
** EOF when this function is called.
*/
................................................................................
      sizeof(Fts5SegIter) * nSlot +       /* pNew->aSeg[] */
      sizeof(u16) * nSlot                 /* pNew->aFirst[] */
  );
  if( pNew==0 ) return;
  pNew->nSeg = nSlot;
  pNew->aSeg = (Fts5SegIter*)&pNew[1];
  pNew->aFirst = (u16*)&pNew->aSeg[nSlot];
  pNew->bRev = (0!=(flags & FTS5INDEX_QUERY_DESC));
  pNew->bSkipEmpty = bSkipEmpty;

  /* Initialize each of the component segment iterators. */
  if( iLevel<0 ){
    Fts5StructureLevel *pEnd = &pStruct->aLevel[pStruct->nLevel];
    for(pLvl=&pStruct->aLevel[0]; pLvl<pEnd; pLvl++){
      for(iSeg=pLvl->nSeg-1; iSeg>=0; iSeg--){
................................................................................
  i64 iMatch
){
  while( 1 ){
    i64 iRowid;
    fts5MultiIterNext(p, pIter, 1, iMatch);
    if( fts5MultiIterEof(p, pIter) ) break;
    iRowid = fts5MultiIterRowid(pIter);
    if( pIter->bRev==0 && iRowid>=iMatch ) break;
    if( pIter->bRev!=0 && iRowid<=iMatch ) break;
  }
}

/*
** Return a pointer to a buffer containing the term associated with the 
** entry that the iterator currently points to.
*/
................................................................................
      fts5WriteDlidxAppend(p, pWriter, iRowid);
    }

    /* Write the docid. */
    if( pWriter->bFirstRowidInDoclist || pWriter->bFirstRowidInPage ){
      fts5BufferAppendVarint(&p->rc, &pPage->buf, iRowid);
    }else{
      assert( p->rc || iRowid>pWriter->iPrevRowid );
      fts5BufferAppendVarint(&p->rc, &pPage->buf, iRowid - pWriter->iPrevRowid);
    }
    pWriter->iPrevRowid = iRowid;
    pWriter->bFirstRowidInDoclist = 0;
    pWriter->bFirstRowidInPage = 0;

    if( pPage->buf.n>=p->pConfig->pgsz ){
      fts5WriteFlushLeaf(p, pWriter);
................................................................................
}

static void fts5DoclistIterNext(Fts5DoclistIter *pIter){
  if( pIter->i<pIter->n ){
    if( pIter->i ){
      i64 iDelta;
      pIter->i += getVarint(&pIter->a[pIter->i], (u64*)&iDelta);
      if( pIter->bDesc ){
        pIter->iRowid -= iDelta;
      }else{
        pIter->iRowid += iDelta;
      }
    }else{
      pIter->i += getVarint(&pIter->a[pIter->i], (u64*)&pIter->iRowid);
    }
    pIter->i += fts5GetVarint32(&pIter->a[pIter->i], pIter->nPoslist);
    pIter->aPoslist = &pIter->a[pIter->i];
    pIter->i += pIter->nPoslist;
................................................................................
  }else{
    pIter->aPoslist = 0;
  }
}

static void fts5DoclistIterInit(
  Fts5Buffer *pBuf, 
  int bDesc, 
  Fts5DoclistIter *pIter
){
  memset(pIter, 0, sizeof(*pIter));
  pIter->a = pBuf->p;
  pIter->n = pBuf->n;
  pIter->bDesc = bDesc;
  fts5DoclistIterNext(pIter);
}

/*
** Append a doclist to buffer pBuf.
*/
static void fts5MergeAppendDocid(
  int *pRc,                       /* IN/OUT: Error code */
  int bDesc,
  Fts5Buffer *pBuf,               /* Buffer to write to */
  i64 *piLastRowid,               /* IN/OUT: Previous rowid written (if any) */
  i64 iRowid                      /* Rowid to append */
){
  if( pBuf->n==0 ){
    fts5BufferAppendVarint(pRc, pBuf, iRowid);
  }else if( bDesc ){
    fts5BufferAppendVarint(pRc, pBuf, *piLastRowid - iRowid);
  }else{
    fts5BufferAppendVarint(pRc, pBuf, iRowid - *piLastRowid);
  }
  *piLastRowid = iRowid;
}

................................................................................
** returning.
**
** If an error occurs, an error code is left in p->rc. If an error has
** already occurred, this function is a no-op.
*/
static void fts5MergePrefixLists(
  Fts5Index *p,                   /* FTS5 backend object */
  int bDesc,
  Fts5Buffer *p1,                 /* First list to merge */
  Fts5Buffer *p2                  /* Second list to merge */
){
  if( p2->n ){
    i64 iLastRowid = 0;
    Fts5DoclistIter i1;
    Fts5DoclistIter i2;
    Fts5Buffer out;
    Fts5Buffer tmp;
    memset(&out, 0, sizeof(out));
    memset(&tmp, 0, sizeof(tmp));

    fts5DoclistIterInit(p1, bDesc, &i1);
    fts5DoclistIterInit(p2, bDesc, &i2);
    while( i1.aPoslist!=0 || i2.aPoslist!=0 ){
      if( i2.aPoslist==0 || (i1.aPoslist && 
           ( (bDesc && i1.iRowid>i2.iRowid) || (!bDesc && i1.iRowid<i2.iRowid) )
      )){
        /* Copy entry from i1 */
        fts5MergeAppendDocid(&p->rc, bDesc, &out, &iLastRowid, i1.iRowid);
        fts5BufferAppendVarint(&p->rc, &out, i1.nPoslist);
        fts5BufferAppendBlob(&p->rc, &out, i1.nPoslist, i1.aPoslist);
        fts5DoclistIterNext(&i1);
      }
      else if( i1.aPoslist==0 || i2.iRowid!=i1.iRowid ){
        /* Copy entry from i2 */
        fts5MergeAppendDocid(&p->rc, bDesc, &out, &iLastRowid, i2.iRowid);
        fts5BufferAppendVarint(&p->rc, &out, i2.nPoslist);
        fts5BufferAppendBlob(&p->rc, &out, i2.nPoslist, i2.aPoslist);
        fts5DoclistIterNext(&i2);
      }
      else{
        Fts5PoslistReader r1;
        Fts5PoslistReader r2;
        Fts5PoslistWriter writer;

        memset(&writer, 0, sizeof(writer));

        /* Merge the two position lists. */ 
        fts5MergeAppendDocid(&p->rc, bDesc, &out, &iLastRowid, i2.iRowid);
        fts5BufferZero(&tmp);
        sqlite3Fts5PoslistReaderInit(-1, i1.aPoslist, i1.nPoslist, &r1);
        sqlite3Fts5PoslistReaderInit(-1, i2.aPoslist, i2.nPoslist, &r2);
        while( p->rc==SQLITE_OK && (r1.bEof==0 || r2.bEof==0) ){
          i64 iNew;
          if( r2.bEof || (r1.bEof==0 && r1.iPos<r2.iPos) ){
            iNew = r1.iPos;
................................................................................
  Fts5Buffer tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

static void fts5SetupPrefixIter(
  Fts5Index *p,                   /* Index to read from */
  int bDesc,                      /* True for "ORDER BY rowid DESC" */
  const u8 *pToken,               /* Buffer containing prefix to match */
  int nToken,                     /* Size of buffer pToken in bytes */
  Fts5IndexIter *pIter            /* Populate this object */
){
  Fts5Structure *pStruct;
  Fts5Buffer *aBuf;
  const int nBuf = 32;
................................................................................
      i64 iRowid = fts5MultiIterRowid(p1);
      int nTerm;
      const u8 *pTerm = fts5MultiIterTerm(p1, &nTerm);
      assert( memcmp(pToken, pTerm, MIN(nToken, nTerm))<=0 );
      if( nTerm<nToken || memcmp(pToken, pTerm, nToken) ) break;

      if( doclist.n>0 
       && ((!bDesc && iRowid<=iLastRowid) || (bDesc && iRowid>=iLastRowid))
      ){

        for(i=0; p->rc==SQLITE_OK && doclist.n; i++){
          assert( i<nBuf );
          if( aBuf[i].n==0 ){
            fts5BufferSwap(&doclist, &aBuf[i]);
            fts5BufferZero(&doclist);
          }else{
            fts5MergePrefixLists(p, bDesc, &doclist, &aBuf[i]);
            fts5BufferZero(&aBuf[i]);
          }
        }
      }
      if( doclist.n==0 ){
        fts5BufferAppendVarint(&p->rc, &doclist, iRowid);
      }else if( bDesc ){
        fts5BufferAppendVarint(&p->rc, &doclist, iLastRowid - iRowid);
      }else{
        fts5BufferAppendVarint(&p->rc, &doclist, iRowid - iLastRowid);
      }
      iLastRowid = iRowid;
      fts5MultiIterPoslist(p, p1, 1, &doclist);
    }

    for(i=0; i<nBuf; i++){
      fts5MergePrefixLists(p, bDesc, &doclist, &aBuf[i]);
      fts5BufferFree(&aBuf[i]);
    }
    fts5MultiIterFree(p, p1);

    pDoclist = (Fts5DoclistIter*)fts5IdxMalloc(p, sizeof(Fts5DoclistIter));
    if( !pDoclist ){
      fts5BufferFree(&doclist);
    }else{
      pIter->pDoclist = pDoclist;
      fts5DoclistIterInit(&doclist, bDesc, pIter->pDoclist);
    }
  }

  fts5StructureRelease(pStruct);
  sqlite3_free(aBuf);
}

................................................................................
      pRet->pStruct = fts5StructureRead(p, iIdx);
      if( pRet->pStruct ){
        fts5MultiIterNew(p, pRet->pStruct, 
            iIdx, 1, flags, (const u8*)pToken, nToken, -1, 0, &pRet->pMulti
        );
      }
    }else{
      int bDesc = (flags & FTS5INDEX_QUERY_DESC)!=0;
      fts5SetupPrefixIter(p, bDesc, (const u8*)pToken, nToken, pRet);
    }
  }

  if( p->rc ){
    sqlite3Fts5IterClose(pRet);
    pRet = 0;
  }
................................................................................
** matching rowid that occurs at or after iMatch. The definition of "at 
** or after" depends on whether this iterator iterates in ascending or 
** descending rowid order.
*/
static void fts5DoclistIterNextFrom(Fts5DoclistIter *p, i64 iMatch){
  do{
    i64 iRowid = p->iRowid;
    if( p->bDesc==0 && iRowid>=iMatch ) break;
    if( p->bDesc!=0 && iRowid<=iMatch ) break;
    fts5DoclistIterNext(p);
  }while( p->aPoslist );
}

/*
** Move to the next matching rowid that occurs at or after iMatch. The
** definition of "at or after" depends on whether this iterator iterates
................................................................................
    int nPos;
    iOff += fts5GetVarint32(&a[iOff], nPos);
    iOff += fts5DecodePoslist(pRc, pBuf, &a[iOff], MIN(n-iOff, nPos));
    if( iOff<n ){
      i64 iDelta;
      iOff += sqlite3GetVarint(&a[iOff], (u64*)&iDelta);
      if( iDelta==0 ) return iOff;
      iDocid += iDelta;
      sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " rowid=%lld", iDocid);
    }
  }

  return iOff;
}

................................................................................
        iOff = iRowidOff;
      }else if( iTermOff ){
        iOff = iTermOff;
      }else{
        iOff = n;
      }
      fts5DecodePoslist(&rc, &s, &a[4], iOff-4);


      assert( iRowidOff==0 || iOff==iRowidOff );
      if( iRowidOff ){
        iOff += fts5DecodeDoclist(&rc, &s, &a[iOff], n-iOff);
      }

      assert( iTermOff==0 || iOff==iTermOff );

      set y [doc]
      set z [doc]
      set rowid [expr int(rand() * 100)]
      execsql { REPLACE INTO t1(rowid,x,y,z) VALUES($rowid, $x, $y, $z) }
    }
    execsql { INSERT INTO t1(t1) VALUES('integrity-check'); }
  } {}

}


#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 8.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(x, prefix="1,2,3");
  INSERT INTO t1(t1, rank) VALUES('pgsz', 32);
................................................................................
do_execsql_test 13.1 {
  CREATE VIRTUAL TABLE t1 USING fts5(x);
  INSERT INTO t1(rowid, x) VALUES(1, 'o n e'), (2, 't w o');
} {}

do_execsql_test 13.2 {
  SELECT rowid FROM t1 WHERE t1 MATCH 'o';
} {2 1}

do_execsql_test 13.4 {
  DELETE FROM t1 WHERE rowid=2;
} {}

do_execsql_test 13.5 {
  SELECT rowid FROM t1 WHERE t1 MATCH 'o';

      set y [doc]
      set z [doc]
      set rowid [expr int(rand() * 100)]
      execsql { REPLACE INTO t1(rowid,x,y,z) VALUES($rowid, $x, $y, $z) }
    }
    execsql { INSERT INTO t1(t1) VALUES('integrity-check'); }
  } {}
  if {$i==2} break
}
#db eval {SELECT rowid, fts5_decode(rowid, block) aS r FROM t1_data} {puts $r}

#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 8.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(x, prefix="1,2,3");
  INSERT INTO t1(t1, rank) VALUES('pgsz', 32);
................................................................................
do_execsql_test 13.1 {
  CREATE VIRTUAL TABLE t1 USING fts5(x);
  INSERT INTO t1(rowid, x) VALUES(1, 'o n e'), (2, 't w o');
} {}

do_execsql_test 13.2 {
  SELECT rowid FROM t1 WHERE t1 MATCH 'o';
} {1 2}

do_execsql_test 13.4 {
  DELETE FROM t1 WHERE rowid=2;
} {}

do_execsql_test 13.5 {
  SELECT rowid FROM t1 WHERE t1 MATCH 'o';

  CREATE VIRTUAL TABLE t1 USING fts5(a, b);
  INSERT INTO t1 VALUES('hello', 'world');
  INSERT INTO t1 VALUES('one two', 'three four');
  INSERT INTO t1(rowid, a, b) VALUES(45, 'forty', 'five');
}

do_execsql_test 1.1 {
  SELECT * FROM t1;
} { forty five {one two} {three four} hello world }

do_execsql_test 1.2 {
  SELECT rowid FROM t1;
} {45 2 1}

do_execsql_test 1.3 {
  SELECT rowid FROM t1 ORDER BY rowid ASC;
} {1 2 45}

do_execsql_test 1.4 {
................................................................................
  5  e    {5 4}
  6  f    {4}
  7  g    {4}
  8  x    {6}
  9  y    {6}
  10 z    {6}
} {

  do_execsql_test 2.7.$tn { SELECT rowid FROM t1 WHERE t1 MATCH $expr } $res




}

#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 3.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(a,b);
................................................................................
  3 {abase + abash} {1}
  4 {abash + abase} {9}
  5 {abaft + abashing} {8 5}
  6 {abandon + abandoning} {10}
  7 {"abashing abases abasement abaft abashing"} {8}
} {
  do_execsql_test 3.2.$tn {
    SELECT rowid FROM t1 WHERE t1 MATCH $expr
  } $res
}

do_execsql_test 3.3 {
  SELECT rowid FROM t1 WHERE t1 MATCH 'NEAR(aback abate, 2)'
} {6}

................................................................................
  3 {abase + abash} {1}
  4 {abash + abase} {9}
  5 {abaft + abashing} {5 8}
  6 {abandon + abandoning} {10}
  7 {"abashing abases abasement abaft abashing"} {8}
} {
  do_execsql_test 3.4.$tn {
    SELECT rowid FROM t1 WHERE t1 MATCH $expr ORDER BY rowid ASC
  } $res
}

#-------------------------------------------------------------------------
# Documents with more than 2M tokens.
#

................................................................................
  2 "[string repeat {a a } 1500000] x"   \
] {
  do_execsql_test 4.$tn { INSERT INTO s1 VALUES($doc) }
}

do_execsql_test 4.3 {
  SELECT rowid FROM s1 WHERE s1 MATCH 'x'
} {2 1}

do_execsql_test 4.4 {
  SELECT rowid FROM s1 WHERE s1 MATCH '"a x"'
} {2 1}

#-------------------------------------------------------------------------
# Check that a special case of segment promotion works. The case is where
# a new segment is written to level L, but the oldest segment within level
# (L-2) is larger than it.
#
do_execsql_test 5.0 {
................................................................................
} {0 1}

do_test 5.4 {
  execsql { INSERT INTO s2 VALUES(rnddoc(160)) }
  fts5_level_segs s2
} {2 0}



















finish_test

  CREATE VIRTUAL TABLE t1 USING fts5(a, b);
  INSERT INTO t1 VALUES('hello', 'world');
  INSERT INTO t1 VALUES('one two', 'three four');
  INSERT INTO t1(rowid, a, b) VALUES(45, 'forty', 'five');
}

do_execsql_test 1.1 {
  SELECT * FROM t1 ORDER BY rowid DESC;
} { forty five {one two} {three four} hello world }

do_execsql_test 1.2 {
  SELECT rowid FROM t1 ORDER BY rowid DESC;
} {45 2 1}

do_execsql_test 1.3 {
  SELECT rowid FROM t1 ORDER BY rowid ASC;
} {1 2 45}

do_execsql_test 1.4 {
................................................................................
  5  e    {5 4}
  6  f    {4}
  7  g    {4}
  8  x    {6}
  9  y    {6}
  10 z    {6}
} {
  do_execsql_test 2.7.$tn.1 { 
    SELECT rowid FROM t1 WHERE t1 MATCH $expr ORDER BY rowid DESC
  } $res
  do_execsql_test 2.7.$tn.2 { 
    SELECT rowid FROM t1 WHERE t1 MATCH $expr ORDER BY rowid ASC
  } [lsort -integer $res]
}

#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 3.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(a,b);
................................................................................
  3 {abase + abash} {1}
  4 {abash + abase} {9}
  5 {abaft + abashing} {8 5}
  6 {abandon + abandoning} {10}
  7 {"abashing abases abasement abaft abashing"} {8}
} {
  do_execsql_test 3.2.$tn {
    SELECT rowid FROM t1 WHERE t1 MATCH $expr ORDER BY rowid DESC
  } $res
}

do_execsql_test 3.3 {
  SELECT rowid FROM t1 WHERE t1 MATCH 'NEAR(aback abate, 2)'
} {6}

................................................................................
  3 {abase + abash} {1}
  4 {abash + abase} {9}
  5 {abaft + abashing} {5 8}
  6 {abandon + abandoning} {10}
  7 {"abashing abases abasement abaft abashing"} {8}
} {
  do_execsql_test 3.4.$tn {
    SELECT rowid FROM t1 WHERE t1 MATCH $expr
  } $res
}

#-------------------------------------------------------------------------
# Documents with more than 2M tokens.
#

................................................................................
  2 "[string repeat {a a } 1500000] x"   \
] {
  do_execsql_test 4.$tn { INSERT INTO s1 VALUES($doc) }
}

do_execsql_test 4.3 {
  SELECT rowid FROM s1 WHERE s1 MATCH 'x'
} {1 2}

do_execsql_test 4.4 {
  SELECT rowid FROM s1 WHERE s1 MATCH '"a x"'
} {1 2}

#-------------------------------------------------------------------------
# Check that a special case of segment promotion works. The case is where
# a new segment is written to level L, but the oldest segment within level
# (L-2) is larger than it.
#
do_execsql_test 5.0 {
................................................................................
} {0 1}

do_test 5.4 {
  execsql { INSERT INTO s2 VALUES(rnddoc(160)) }
  fts5_level_segs s2
} {2 0}

#-------------------------------------------------------------------------
#
do_execsql_test 6.0 {
  CREATE VIRTUAL TABLE s3 USING fts5(x);
  BEGIN;
    INSERT INTO s3 VALUES('a b c');
    INSERT INTO s3 VALUES('A B C');
}

do_execsql_test 6.1 {
  SELECT rowid FROM s3 WHERE s3 MATCH 'a'
} {2 1}

do_execsql_test 6.2 {
  COMMIT;
  SELECT rowid FROM s3 WHERE s3 MATCH 'a'
} {2 1}

finish_test

    99  {r c v w i v h a t a c v c r e}     {h h u m g o f b a e o}
}

do_test 1.1 {
  foreach {id x y} $data {
    execsql { INSERT INTO xx(rowid, x, y) VALUES($id, $x, $y) }
  }

} {}

# Usage:
#
#   poslist aCol ?-pc VARNAME? ?-near N? ?-col C? -- phrase1 phrase2...
#
proc poslist {aCol args} {
................................................................................
# formatted as follows:
#
#   <rowid> {<phrase 0 matches> <phrase 1 matches>...}
#
# where each <phrase X matches> element is a list of phrase matches in the
# same form as returned by auxiliary scalar function fts5_test().
#
proc matchdata {bPos expr {bAsc 0}} {

  set tclexpr [db one {SELECT fts5_expr_tcl($expr, 'nearset $cols', 'x', 'y')}]
  set res [list]

  #puts $tclexpr
  foreach {id x y} $::data {
    set cols [list $x $y]
................................................................................

sqlite3_fts5_create_function db fts5_test_poslist fts5_test_poslist

#-------------------------------------------------------------------------
# Test phrase queries.
#
foreach {tn phrase} {


  1 "o"
  2 "b q"
  3 "e a e"
  4 "m d g q q b k b w f q q p p"
  5 "l o o l v v k"
  6 "a"
  7 "b"
................................................................................
#-------------------------------------------------------------------------
#
do_execsql_test 6.integrity {
  INSERT INTO xx(xx) VALUES('integrity-check');
}
#db eval {SELECT rowid, fts5_decode(rowid, block) aS r FROM xx_data} {puts $r}
foreach {bAsc sql} {
  0 {SELECT rowid FROM xx WHERE xx MATCH $expr}
  1 {SELECT rowid FROM xx WHERE xx MATCH $expr ORDER BY rowid ASC}
} {
  foreach {tn expr} {
    0.1 x
    1 { NEAR(r c) }
    2 { NEAR(r c, 5) }
    3 { NEAR(r c, 3) }
    4 { NEAR(r c, 2) }

    99  {r c v w i v h a t a c v c r e}     {h h u m g o f b a e o}
}

do_test 1.1 {
  foreach {id x y} $data {
    execsql { INSERT INTO xx(rowid, x, y) VALUES($id, $x, $y) }
  }
  execsql { INSERT INTO xx(xx) VALUES('integrity-check') }
} {}

# Usage:
#
#   poslist aCol ?-pc VARNAME? ?-near N? ?-col C? -- phrase1 phrase2...
#
proc poslist {aCol args} {
................................................................................
# formatted as follows:
#
#   <rowid> {<phrase 0 matches> <phrase 1 matches>...}
#
# where each <phrase X matches> element is a list of phrase matches in the
# same form as returned by auxiliary scalar function fts5_test().
#
proc matchdata {bPos expr {bAsc 1}} {

  set tclexpr [db one {SELECT fts5_expr_tcl($expr, 'nearset $cols', 'x', 'y')}]
  set res [list]

  #puts $tclexpr
  foreach {id x y} $::data {
    set cols [list $x $y]
................................................................................

sqlite3_fts5_create_function db fts5_test_poslist fts5_test_poslist

#-------------------------------------------------------------------------
# Test phrase queries.
#
foreach {tn phrase} {
  8 "c"

  1 "o"
  2 "b q"
  3 "e a e"
  4 "m d g q q b k b w f q q p p"
  5 "l o o l v v k"
  6 "a"
  7 "b"
................................................................................
#-------------------------------------------------------------------------
#
do_execsql_test 6.integrity {
  INSERT INTO xx(xx) VALUES('integrity-check');
}
#db eval {SELECT rowid, fts5_decode(rowid, block) aS r FROM xx_data} {puts $r}
foreach {bAsc sql} {
  1 {SELECT rowid FROM xx WHERE xx MATCH $expr}
  0 {SELECT rowid FROM xx WHERE xx MATCH $expr ORDER BY rowid DESC}
} {
  foreach {tn expr} {
    0.1 x
    1 { NEAR(r c) }
    2 { NEAR(r c, 5) }
    3 { NEAR(r c, 3) }
    4 { NEAR(r c, 2) }

foreach {tn match res} {
  1 {c*} {1}
  2 {i*} {3 2}
  3 {t*} {3 1}
  4 {r*} {3 1}
} {
  do_execsql_test 1.$tn {
    SELECT rowid FROM yy WHERE yy MATCH $match
  } $res
}

foreach {tn match res} {
  5 {c*} {1}
  6 {i*} {2 3}
  7 {t*} {1 3}
  8 {r*} {1 3}
} {
  do_execsql_test 1.$tn {
    SELECT rowid FROM yy WHERE yy MATCH $match ORDER BY rowid ASC
  } $res
}

foreach {T create} {
  2 {
    CREATE VIRTUAL TABLE t1 USING fts5(a, b);
    INSERT INTO t1(t1, rank) VALUES('pgsz', 32);
................................................................................
      }
      if {$bMatch} { lappend ret $rowid }
    }
    return $ret
  }
  
  foreach {bAsc sql} {
    0 {SELECT rowid FROM t1 WHERE t1 MATCH $prefix}
    1 {SELECT rowid FROM t1 WHERE t1 MATCH $prefix ORDER BY rowid ASC}
  } {
    foreach {tn prefix} {
      1  {a*} 2 {ab*} 3 {abc*} 4 {abcd*} 5 {abcde*} 
      6  {f*} 7 {fg*} 8 {fgh*} 9 {fghi*} 10 {fghij*}
      11 {k*} 12 {kl*} 13 {klm*} 14 {klmn*} 15 {klmno*}
      16 {p*} 17 {pq*} 18 {pqr*} 19 {pqrs*} 20 {pqrst*}
      21 {u*} 22 {uv*} 23 {uvw*} 24 {uvwx*} 25 {uvwxy*} 26 {uvwxyz*}

foreach {tn match res} {
  1 {c*} {1}
  2 {i*} {3 2}
  3 {t*} {3 1}
  4 {r*} {3 1}
} {
  do_execsql_test 1.$tn {
    SELECT rowid FROM yy WHERE yy MATCH $match ORDER BY rowid DESC
  } $res
}

foreach {tn match res} {
  5 {c*} {1}
  6 {i*} {2 3}
  7 {t*} {1 3}
  8 {r*} {1 3}
} {
  do_execsql_test 1.$tn {
    SELECT rowid FROM yy WHERE yy MATCH $match
  } $res
}

foreach {T create} {
  2 {
    CREATE VIRTUAL TABLE t1 USING fts5(a, b);
    INSERT INTO t1(t1, rank) VALUES('pgsz', 32);
................................................................................
      }
      if {$bMatch} { lappend ret $rowid }
    }
    return $ret
  }
  
  foreach {bAsc sql} {
    1 {SELECT rowid FROM t1 WHERE t1 MATCH $prefix}
    0 {SELECT rowid FROM t1 WHERE t1 MATCH $prefix ORDER BY rowid DESC}
  } {
    foreach {tn prefix} {
      1  {a*} 2 {ab*} 3 {abc*} 4 {abcd*} 5 {abcde*} 
      6  {f*} 7 {fg*} 8 {fgh*} 9 {fghi*} 10 {fghij*}
      11 {k*} 12 {kl*} 13 {klm*} 14 {klmn*} 15 {klmno*}
      16 {p*} 17 {pq*} 18 {pqr*} 19 {pqrs*} 20 {pqrst*}
      21 {u*} 22 {uv*} 23 {uvw*} 24 {uvwx*} 25 {uvwxy*} 26 {uvwxyz*}

do_execsql_test 3.3 {
  INSERT INTO t3 
  VALUES('k x j r m a d o i z j', 'r t t t f e b r x i v j v g o');
  SELECT rowid, fts5_test_poslist(t3) 
  FROM t3 WHERE t3 MATCH 'a OR b AND c';
} {
  3 0.0.5 
  1 {0.0.6 1.0.9 0.0.10 0.0.12 1.0.15 2.1.2}

}

#-------------------------------------------------------------------------
# 
do_execsql_test 4.0 {
  CREATE VIRTUAL TABLE t4 USING fts5(x, y);
  INSERT INTO t4 
................................................................................
  INSERT INTO t6 VALUES('There are more', 'things in heaven and earth');
  INSERT INTO t6 VALUES(', Horatio, Than are', 'dreamt of in your philosophy.');
}

do_execsql_test 6.2 {
  SELECT rowid, fts5_test_tokenize(t6) FROM t6 WHERE t6 MATCH 't*'
} {
  2 {{horatio than are} {dreamt of in your philosophy}}
  1 {{there are more} {things in heaven and earth}}

}

#-------------------------------------------------------------------------
# Test the xQueryPhrase() API
#
reset_db
fts5_aux_test_functions db

do_execsql_test 3.3 {
  INSERT INTO t3 
  VALUES('k x j r m a d o i z j', 'r t t t f e b r x i v j v g o');
  SELECT rowid, fts5_test_poslist(t3) 
  FROM t3 WHERE t3 MATCH 'a OR b AND c';
} {

  1 {0.0.6 1.0.9 0.0.10 0.0.12 1.0.15 2.1.2}
  3 0.0.5 
}

#-------------------------------------------------------------------------
# 
do_execsql_test 4.0 {
  CREATE VIRTUAL TABLE t4 USING fts5(x, y);
  INSERT INTO t4 
................................................................................
  INSERT INTO t6 VALUES('There are more', 'things in heaven and earth');
  INSERT INTO t6 VALUES(', Horatio, Than are', 'dreamt of in your philosophy.');
}

do_execsql_test 6.2 {
  SELECT rowid, fts5_test_tokenize(t6) FROM t6 WHERE t6 MATCH 't*'
} {

  1 {{there are more} {things in heaven and earth}}
  2 {{horatio than are} {dreamt of in your philosophy}}
}

#-------------------------------------------------------------------------
# Test the xQueryPhrase() API
#
reset_db
fts5_aux_test_functions db

  INSERT INTO ft1 VALUES('i d i g c d c h b f');
  INSERT INTO ft1 VALUES('g d a e h a b c f j');
}

do_execsql_test 1.2 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'e';
} {
  {g d a [e] h a b c f j}
  {i c c f a d g h j [e]}
  {j f c [e] d a h j d b}
  {i a d [e] g j g d a a}

  {d c j d c j b c g [e]}
  {[e] j a [e] f h b f h h}
}

do_execsql_test 1.3 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'h + d';
} {
  {j f [h d] g h i b d f} 
  {[h d] b j c c g a c a}

}

do_execsql_test 1.4 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'd + d';
} {
  {i [d d] a g i b g [d d]}
}

do_execsql_test 1.5 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'e e e'
} {
  {g d a [e] h a b c f j}
  {i c c f a d g h j [e]}
  {j f c [e] d a h j d b}
  {i a d [e] g j g d a a}

  {d c j d c j b c g [e]}
  {[e] j a [e] f h b f h h}
}

do_execsql_test 1.6 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'd + d d + d';
} {
  {i [d d] a g i b g [d d]}
}
................................................................................

  -- The following SELECT statement returns these three rows:
  --   '[a b c] x [c d e]'
  --   '[a b c] [c d e]'
  --   '[a b c d e]'
  SELECT highlight(ft, 0, '[', ']') FROM ft WHERE ft MATCH 'a+b+c AND c+d+e';
} {
  {[a b c d e]}
  {[a b c] [c d e]}
  {[a b c] x [c d e]}
}


finish_test

  INSERT INTO ft1 VALUES('i d i g c d c h b f');
  INSERT INTO ft1 VALUES('g d a e h a b c f j');
}

do_execsql_test 1.2 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'e';
} {
  {[e] j a [e] f h b f h h}
  {d c j d c j b c g [e]}

  {i a d [e] g j g d a a}
  {j f c [e] d a h j d b}
  {i c c f a d g h j [e]}
  {g d a [e] h a b c f j}
}

do_execsql_test 1.3 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'h + d';
} {

  {[h d] b j c c g a c a}
  {j f [h d] g h i b d f} 
}

do_execsql_test 1.4 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'd + d';
} {
  {i [d d] a g i b g [d d]}
}

do_execsql_test 1.5 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'e e e'
} {
  {[e] j a [e] f h b f h h}
  {d c j d c j b c g [e]}

  {i a d [e] g j g d a a}
  {j f c [e] d a h j d b}
  {i c c f a d g h j [e]}
  {g d a [e] h a b c f j}
}

do_execsql_test 1.6 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'd + d d + d';
} {
  {i [d d] a g i b g [d d]}
}
................................................................................

  -- The following SELECT statement returns these three rows:
  --   '[a b c] x [c d e]'
  --   '[a b c] [c d e]'
  --   '[a b c d e]'
  SELECT highlight(ft, 0, '[', ']') FROM ft WHERE ft MATCH 'a+b+c AND c+d+e';
} {
  {[a b c] x [c d e]}
  {[a b c] [c d e]}
  {[a b c d e]}
}


finish_test

} {{123 456} {123 456}}

proc rowidtest {cmd} { $cmd xRowid }
sqlite3_fts5_create_function db rowidtest rowidtest

do_execsql_test 3.3.1 {
  SELECT rowidtest(t1) FROM t1 WHERE t1 MATCH 'q'
} {2 1}

proc insttest {cmd} {
  set res [list]
  for {set i 0} {$i < [$cmd xInstCount]} {incr i} {
    lappend res [$cmd xInst $i]
  }
  set res
}
sqlite3_fts5_create_function db insttest insttest

do_execsql_test 3.4.1 {
  SELECT insttest(t1) FROM t1 WHERE t1 MATCH 'q'
} {
  {{0 0 5}} 
  {{0 0 0}}
}

do_execsql_test 3.4.2 {
  SELECT insttest(t1) FROM t1 WHERE t1 MATCH 'r+e OR w'
} {
  {{0 0 2} {1 0 4}} 
  {{1 0 1}}

}

proc coltest {cmd} {
  list [$cmd xColumnSize 0] [$cmd xColumnText 0]
}
sqlite3_fts5_create_function db coltest coltest

do_execsql_test 3.5.1 {
  SELECT coltest(t1) FROM t1 WHERE t1 MATCH 'q'
} {
  {6 {y t r e w q}} {6 {q w e r t y}}

}

#-------------------------------------------------------------------------
# Tests for remapping the "rank" column.
#
#   4.1.*: Mapped to a function with no arguments.
#   4.2.*: Mapped to a function with one or more arguments.
................................................................................
}

do_execsql_test 4.1.3 {
  SELECT rowid, rank FROM t2 
  WHERE t2 MATCH 'a' AND rank MATCH 'firstinst()'
  ORDER BY rank DESC
} {
  5 103  9 102  6 9  10 8  3 6  2 4  7 0  1 0 
}

do_execsql_test 4.1.4 {
  INSERT INTO t2(t2, rank) VALUES('rank', 'firstinst()');
  SELECT rowid, rank FROM t2 WHERE t2 MATCH 'a' ORDER BY rowid ASC
} {
  1 0 2 4 3 6   5  103
  6 9 7 0 9 102 10 8
}

do_execsql_test 4.1.5 {
  SELECT rowid, rank FROM t2 WHERE t2 MATCH 'a' ORDER BY rank DESC
} {
  5 103  9 102  6 9  10 8  3 6  2 4  7 0  1 0 
}

do_execsql_test 4.1.6 {
  INSERT INTO t2(t2, rank) VALUES('rank', 'firstinst (    ) ');
  SELECT rowid, rank FROM t2 WHERE t2 MATCH 'a' ORDER BY rank DESC
} {
  5 103  9 102  6 9  10 8  3 6  2 4  7 0  1 0 
}

proc rowidplus {cmd ival} { 
  expr [$cmd xRowid] + $ival
}
sqlite3_fts5_create_function db rowidplus rowidplus

................................................................................
breakpoint

do_execsql_test 4.3.2 {
  SELECT * FROM t3
  WHERE t3 MATCH 'a' AND rank MATCH 'rowidmod(4)' 
  ORDER BY rank ASC
} {
  {a four} {a five} {a one} {a two} {a three}
}
do_execsql_test 4.3.3 {
  SELECT *, rank FROM t3
  WHERE t3 MATCH 'a' AND rank MATCH 'rowidmod(3)' 
  ORDER BY rank ASC
} {
  {a three} 0 {a four} 1 {a one} 1 {a five} 2 {a two} 2
}


finish_test

} {{123 456} {123 456}}

proc rowidtest {cmd} { $cmd xRowid }
sqlite3_fts5_create_function db rowidtest rowidtest

do_execsql_test 3.3.1 {
  SELECT rowidtest(t1) FROM t1 WHERE t1 MATCH 'q'
} {1 2}

proc insttest {cmd} {
  set res [list]
  for {set i 0} {$i < [$cmd xInstCount]} {incr i} {
    lappend res [$cmd xInst $i]
  }
  set res
}
sqlite3_fts5_create_function db insttest insttest

do_execsql_test 3.4.1 {
  SELECT insttest(t1) FROM t1 WHERE t1 MATCH 'q'
} {
  {{0 0 0}}
  {{0 0 5}} 
}

do_execsql_test 3.4.2 {
  SELECT insttest(t1) FROM t1 WHERE t1 MATCH 'r+e OR w'
} {

  {{1 0 1}}
  {{0 0 2} {1 0 4}} 
}

proc coltest {cmd} {
  list [$cmd xColumnSize 0] [$cmd xColumnText 0]
}
sqlite3_fts5_create_function db coltest coltest

do_execsql_test 3.5.1 {
  SELECT coltest(t1) FROM t1 WHERE t1 MATCH 'q'
} {
  {6 {q w e r t y}}
  {6 {y t r e w q}} 
}

#-------------------------------------------------------------------------
# Tests for remapping the "rank" column.
#
#   4.1.*: Mapped to a function with no arguments.
#   4.2.*: Mapped to a function with one or more arguments.
................................................................................
}

do_execsql_test 4.1.3 {
  SELECT rowid, rank FROM t2 
  WHERE t2 MATCH 'a' AND rank MATCH 'firstinst()'
  ORDER BY rank DESC
} {
  5 103  9 102  6 9  10 8  3 6  2 4  1 0  7 0  
}

do_execsql_test 4.1.4 {
  INSERT INTO t2(t2, rank) VALUES('rank', 'firstinst()');
  SELECT rowid, rank FROM t2 WHERE t2 MATCH 'a' ORDER BY rowid ASC
} {
  1 0 2 4 3 6   5  103
  6 9 7 0 9 102 10 8
}

do_execsql_test 4.1.5 {
  SELECT rowid, rank FROM t2 WHERE t2 MATCH 'a' ORDER BY rank DESC
} {
  5 103  9 102  6 9  10 8  3 6  2 4  1 0  7 0  
}

do_execsql_test 4.1.6 {
  INSERT INTO t2(t2, rank) VALUES('rank', 'firstinst (    ) ');
  SELECT rowid, rank FROM t2 WHERE t2 MATCH 'a' ORDER BY rank DESC
} {
  5 103  9 102  6 9  10 8  3 6  2 4   1 0  7 0  
}

proc rowidplus {cmd ival} { 
  expr [$cmd xRowid] + $ival
}
sqlite3_fts5_create_function db rowidplus rowidplus

................................................................................
breakpoint

do_execsql_test 4.3.2 {
  SELECT * FROM t3
  WHERE t3 MATCH 'a' AND rank MATCH 'rowidmod(4)' 
  ORDER BY rank ASC
} {
  {a four} {a one} {a five} {a two} {a three}
}
do_execsql_test 4.3.3 {
  SELECT *, rank FROM t3
  WHERE t3 MATCH 'a' AND rank MATCH 'rowidmod(3)' 
  ORDER BY rank ASC
} {
  {a three} 0 {a one} 1 {a four} 1 {a two} 2 {a five} 2 
}


finish_test

  INSERT INTO f1(rowid, a, b) VALUES(1, 'one',   'o n e');
  INSERT INTO f1(rowid, a, b) VALUES(2, 'two',   't w o');
  INSERT INTO f1(rowid, a, b) VALUES(3, 'three', 't h r e e');
}

do_execsql_test 1.2 {
  SELECT rowid FROM f1 WHERE f1 MATCH 'o';
} {2 1}

do_execsql_test 1.3 {
  INSERT INTO f1(a, b) VALUES('four',   'f o u r');
  SELECT rowid FROM f1 WHERE f1 MATCH 'o';
} {4 2 1}

do_execsql_test 1.4 {
  SELECT rowid, a, b FROM f1 WHERE f1 MATCH 'o';
} {4 {} {} 2 {} {} 1 {} {}}

do_execsql_test 1.5 {
  SELECT rowid, highlight(f1, 0, '[', ']') FROM f1 WHERE f1 MATCH 'o';
} {4 {} 2 {} 1 {}}

do_execsql_test 1.6 {
  SELECT rowid, highlight(f1, 0, '[', ']') IS NULL FROM f1 WHERE f1 MATCH 'o';
} {4 1 2 1 1 1}

do_execsql_test 1.7 {
  SELECT rowid, snippet(f1, -1, '[', ']', '...', 5) IS NULL 
  FROM f1 WHERE f1 MATCH 'o';
} {4 1 2 1 1 1}

do_execsql_test 1.8 {
  SELECT rowid, snippet(f1, 1, '[', ']', '...', 5) IS NULL 
  FROM f1 WHERE f1 MATCH 'o';
} {4 1 2 1 1 1}

do_execsql_test 1.9 {
  SELECT rowid FROM f1;
} {4 3 2 1}

do_execsql_test 1.10 {
  SELECT * FROM f1;
} {{} {}  {} {}  {} {}  {} {}}

do_execsql_test 1.11 {
  SELECT rowid, a, b FROM f1 ORDER BY rowid ASC;
................................................................................

do_execsql_test 1.15 {
  INSERT INTO f1(f1, rowid, a, b) VALUES('delete', 2, 'two', 't w o');
} {}

do_execsql_test 1.16 {
  SELECT rowid FROM f1 WHERE f1 MATCH 'o';
} {4 1}

do_execsql_test 1.17 {
  SELECT rowid FROM f1;
} {4 3 1}

#-------------------------------------------------------------------------
# External content tables
#
reset_db
do_execsql_test 2.1 {
  -- Create a table. And an external content fts5 table to index it.

  INSERT INTO f1(rowid, a, b) VALUES(1, 'one',   'o n e');
  INSERT INTO f1(rowid, a, b) VALUES(2, 'two',   't w o');
  INSERT INTO f1(rowid, a, b) VALUES(3, 'three', 't h r e e');
}

do_execsql_test 1.2 {
  SELECT rowid FROM f1 WHERE f1 MATCH 'o';
} {1 2}

do_execsql_test 1.3 {
  INSERT INTO f1(a, b) VALUES('four',   'f o u r');
  SELECT rowid FROM f1 WHERE f1 MATCH 'o';
} {1 2 4}

do_execsql_test 1.4 {
  SELECT rowid, a, b FROM f1 WHERE f1 MATCH 'o';
} {1 {} {} 2 {} {} 4 {} {}}

do_execsql_test 1.5 {
  SELECT rowid, highlight(f1, 0, '[', ']') FROM f1 WHERE f1 MATCH 'o';
} {1 {} 2 {} 4 {}}

do_execsql_test 1.6 {
  SELECT rowid, highlight(f1, 0, '[', ']') IS NULL FROM f1 WHERE f1 MATCH 'o';
} {1 1 2 1 4 1}

do_execsql_test 1.7 {
  SELECT rowid, snippet(f1, -1, '[', ']', '...', 5) IS NULL 
  FROM f1 WHERE f1 MATCH 'o';
} {1 1 2 1 4 1}

do_execsql_test 1.8 {
  SELECT rowid, snippet(f1, 1, '[', ']', '...', 5) IS NULL 
  FROM f1 WHERE f1 MATCH 'o';
} {1 1 2 1 4 1}

do_execsql_test 1.9 {
  SELECT rowid FROM f1;
} {1 2 3 4}

do_execsql_test 1.10 {
  SELECT * FROM f1;
} {{} {}  {} {}  {} {}  {} {}}

do_execsql_test 1.11 {
  SELECT rowid, a, b FROM f1 ORDER BY rowid ASC;
................................................................................

do_execsql_test 1.15 {
  INSERT INTO f1(f1, rowid, a, b) VALUES('delete', 2, 'two', 't w o');
} {}

do_execsql_test 1.16 {
  SELECT rowid FROM f1 WHERE f1 MATCH 'o';
} {1 4}

do_execsql_test 1.17 {
  SELECT rowid FROM f1;
} {1 3 4}

#-------------------------------------------------------------------------
# External content tables
#
reset_db
do_execsql_test 2.1 {
  -- Create a table. And an external content fts5 table to index it.

  catchsql { INSERT INTO t1(t1) VALUES('integrity-check') }
} {1 {database disk image is malformed}}

db_restore_and_reopen
#db eval {SELECT rowid, fts5_decode(rowid, block) aS r FROM t1_data} {puts $r}



#--------------------------------------------------------------------

do_execsql_test 2.0 {
  CREATE VIRTUAL TABLE t2 USING fts5(x);
  INSERT INTO t2(t2, rank) VALUES('pgsz', 32);
}

do_test 2.1 {
  db transaction {
    for {set i 0} {$i < 20} {incr i} {
      execsql { INSERT INTO t2 VALUES('xxxxxxxxxx') }

    }
    for {set i 0} {$i < 20} {incr i} {
      execsql { INSERT INTO t2 VALUES('xxxxxxxxxzzzz') }
    }
  }
} {}
db eval {SELECT rowid, fts5_decode(rowid, block) aS r FROM t2_data} {puts $r}



finish_test

  catchsql { INSERT INTO t1(t1) VALUES('integrity-check') }
} {1 {database disk image is malformed}}

db_restore_and_reopen
#db eval {SELECT rowid, fts5_decode(rowid, block) aS r FROM t1_data} {puts $r}



#--------------------------------------------------------------------
#
do_execsql_test 2.0 {
  CREATE VIRTUAL TABLE t2 USING fts5(x);
  INSERT INTO t2(t2, rank) VALUES('pgsz', 64);
}
db func rnddoc fts5_rnddoc
do_test 2.1 {

  for {set i 0} {$i < 500} {incr i} {
    execsql { INSERT INTO t2 VALUES(rnddoc(50)) }
    execsql { INSERT INTO t2(t2) VALUES('integrity-check') }
  }


} {}



#--------------------------------------------------------------------
#

finish_test

  INSERT INTO t2 VALUES('k fe fd rd a gi ho kk', 'ng m c r d ml rm r');
}
faultsim_save_and_close

foreach {tn expr res} {
  1 { dk  }           7
  2 { m f }           1
  3 { f*  }           {10 9 8 6 5 4 3 1}
  4 { m OR f }        {10 9 8 5 4 1}
  5 { sn + gh }       {5}
  6 { "sn gh" }       {5}
  7 { NEAR(r a, 5) }  {9}
  8 { m* f* }         {10 9 8 6 4 1}
  9 { m* + f* }       {8 1}
} {
  do_faultsim_test 4.$tn -prep {
    faultsim_restore_and_reopen
  } -body "
    execsql { SELECT rowid FROM t2 WHERE t2 MATCH '$expr' }
  " -test "
    faultsim_test_result {[list 0 $res]}
................................................................................

reset_db
db func rnddoc rnddoc

do_test 8.0 {
  execsql { CREATE VIRTUAL TABLE x1 USING fts5(a) }
  set ::res [list]
  for {set i 100} {$i>0} {incr i -1} {
    execsql { INSERT INTO x1 VALUES( rnddoc(50) ) }
    lappend ::res $i
  }
} {}

do_faultsim_test 8.1 -faults oom* -prep {
} -body {

  INSERT INTO t2 VALUES('k fe fd rd a gi ho kk', 'ng m c r d ml rm r');
}
faultsim_save_and_close

foreach {tn expr res} {
  1 { dk  }           7
  2 { m f }           1
  3 { f*  }           {1 3 4 5 6 8 9 10}
  4 { m OR f }        {1 4 5 8 9 10}
  5 { sn + gh }       {5}
  6 { "sn gh" }       {5}
  7 { NEAR(r a, 5) }  {9}
  8 { m* f* }         {1 4 6 8 9 10}
  9 { m* + f* }       {1 8}
} {
  do_faultsim_test 4.$tn -prep {
    faultsim_restore_and_reopen
  } -body "
    execsql { SELECT rowid FROM t2 WHERE t2 MATCH '$expr' }
  " -test "
    faultsim_test_result {[list 0 $res]}
................................................................................

reset_db
db func rnddoc rnddoc

do_test 8.0 {
  execsql { CREATE VIRTUAL TABLE x1 USING fts5(a) }
  set ::res [list]
  for {set i 1} {$i<100} {incr i 1} {
    execsql { INSERT INTO x1 VALUES( rnddoc(50) ) }
    lappend ::res $i
  }
} {}

do_faultsim_test 8.1 -faults oom* -prep {
} -body {

  }
  foreach str $strlist { execsql { INSERT INTO x4 VALUES($str) } }
  execsql COMMIT
} {}

do_execsql_test 5.1 {
  SELECT rowid FROM x4 WHERE x4 MATCH 'a'
} {4 3 2 1}

set res [db one {SELECT count(*) FROM x4_data}]
do_execsql_test 5.2 {
  SELECT count(fts5_decode(rowid, block)) FROM x4_data;
} $res

finish_test

  }
  foreach str $strlist { execsql { INSERT INTO x4 VALUES($str) } }
  execsql COMMIT
} {}

do_execsql_test 5.1 {
  SELECT rowid FROM x4 WHERE x4 MATCH 'a'
} {1 2 3 4}

set res [db one {SELECT count(*) FROM x4_data}]
do_execsql_test 5.2 {
  SELECT count(fts5_decode(rowid, block)) FROM x4_data;
} $res

finish_test