SQLite

#define fts5BufferZero(x)             sqlite3Fts5BufferZero(x)
#define fts5BufferGrow(a,b,c)         sqlite3Fts5BufferGrow(a,b,c)
#define fts5BufferAppendVarint(a,b,c) sqlite3Fts5BufferAppendVarint(a,b,c)
#define fts5BufferFree(a)             sqlite3Fts5BufferFree(a)
#define fts5BufferAppendBlob(a,b,c,d) sqlite3Fts5BufferAppendBlob(a,b,c,d)
#define fts5BufferSet(a,b,c,d)        sqlite3Fts5BufferSet(a,b,c,d)

typedef struct Fts5PoslistReader Fts5PoslistReader;
struct Fts5PoslistReader {
  /* Variables used only by sqlite3Fts5PoslistIterXXX() functions. */
  int iCol;                       /* If (iCol>=0), this column only */
  const u8 *a;                    /* Position list to iterate through */
  int n;                          /* Size of buffer at a[] in bytes */
  int i;                          /* Current offset in a[] */

  /* Output variables */
  int bEof;                       /* Set to true at EOF */
  i64 iPos;                       /* (iCol<<32) + iPos */
};
int sqlite3Fts5PoslistReaderInit(
  int iCol,                       /* If (iCol>=0), this column only */
  const u8 *a, int n,             /* Poslist buffer to iterate through */
  Fts5PoslistReader *pIter        /* Iterator object to initialize */
);
int sqlite3Fts5PoslistReaderNext(Fts5PoslistReader*);

typedef struct Fts5PoslistWriter Fts5PoslistWriter;
struct Fts5PoslistWriter {
  int iCol;
  int iOff;
};
int sqlite3Fts5PoslistWriterAppend(Fts5Buffer*, Fts5PoslistWriter*, i64);


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

/**************************************************************************
** Interface to code in fts5_index.c. fts5_index.c contains contains code

  Fts5Buffer *pBuf, 
  int nData, 
  const u8 *pData
){
  pBuf->n = 0;
  sqlite3Fts5BufferAppendBlob(pRc, pBuf, nData, pData);
}


/*
** Advance the iterator object passed as the only argument. Return true
** if the iterator reaches EOF, or false otherwise.
*/
int sqlite3Fts5PoslistReaderNext(Fts5PoslistReader *pIter){
  if( pIter->i>=pIter->n ){
    pIter->bEof = 1;
  }else{
    int iVal;
    pIter->i += getVarint32(&pIter->a[pIter->i], iVal);
    if( iVal==1 ){
      pIter->i += getVarint32(&pIter->a[pIter->i], iVal);
      if( pIter->iCol>=0 && iVal>pIter->iCol ){
        pIter->bEof = 1;
      }else{
        pIter->iPos = ((u64)iVal << 32);
        pIter->i += getVarint32(&pIter->a[pIter->i], iVal);
      }
    }
    pIter->iPos += (iVal-2);
  }
  return pIter->bEof;
}

int sqlite3Fts5PoslistReaderInit(
  int iCol,                       /* If (iCol>=0), this column only */
  const u8 *a, int n,             /* Poslist buffer to iterate through */
  Fts5PoslistReader *pIter        /* Iterator object to initialize */
){
  memset(pIter, 0, sizeof(*pIter));
  pIter->a = a;
  pIter->n = n;
  pIter->iCol = iCol;
  do {
    sqlite3Fts5PoslistReaderNext(pIter);
  }while( pIter->bEof==0 && (pIter->iPos >> 32)<iCol );
  return pIter->bEof;
}

int sqlite3Fts5PoslistWriterAppend(
  Fts5Buffer *pBuf, 
  Fts5PoslistWriter *pWriter,
  i64 iPos
){
  int rc = SQLITE_OK;
  int iCol = (int)(iPos >> 32);
  int iOff = (iPos & 0x7FFFFFFF);

  if( iCol!=pWriter->iCol ){
    fts5BufferAppendVarint(&rc, pBuf, 1);
    fts5BufferAppendVarint(&rc, pBuf, iCol);
    pWriter->iCol = iCol;
    pWriter->iOff = 0;
  }
  fts5BufferAppendVarint(&rc, pBuf, (iOff - pWriter->iOff) + 2);

  return rc;
}

struct Fts5Parse {
  Fts5Config *pConfig;
  char *zErr;
  int rc;
  Fts5ExprNode *pExpr;            /* Result of a successful parse */
};














































































void sqlite3Fts5ParseError(Fts5Parse *pParse, const char *zFmt, ...){
  if( pParse->rc==SQLITE_OK ){
    va_list ap;
    va_start(ap, zFmt);
    pParse->zErr = sqlite3_vmprintf(zFmt, ap);
    va_end(ap);
    pParse->rc = SQLITE_ERROR;

static int fts5ExprPhraseIsMatch(
  Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
  int iCol,                       /* If >=0, search for matches in iCol only */
  Fts5ExprPhrase *pPhrase,        /* Phrase object to initialize */
  int *pbMatch                    /* OUT: Set to true if really a match */
){
  Fts5PoslistWriter writer = {0, 0};
  Fts5PoslistReader aStatic[4];
  Fts5PoslistReader *aIter = aStatic;
  int i;
  int rc = SQLITE_OK;

  fts5BufferZero(&pPhrase->poslist);

  /* If the aStatic[] array is not large enough, allocate a large array
  ** using sqlite3_malloc(). This approach could be improved upon. */
  if( pPhrase->nTerm>(sizeof(aStatic) / sizeof(aStatic[0])) ){
    int nByte = sizeof(Fts5PoslistReader) * pPhrase->nTerm;
    aIter = (Fts5PoslistReader*)sqlite3_malloc(nByte);
    if( !aIter ) return SQLITE_NOMEM;
  }

  /* Initialize a term iterator for each term in the phrase */
  for(i=0; i<pPhrase->nTerm; i++){
    int n;
    const u8 *a = sqlite3Fts5IterPoslist(pPhrase->aTerm[i].pIter, &n);
    if( sqlite3Fts5PoslistReaderInit(iCol, a, n, &aIter[i]) ) goto ismatch_out;
  }

  while( 1 ){
    int bMatch;
    i64 iPos = aIter[0].iPos;
    do {
      bMatch = 1;
      for(i=0; i<pPhrase->nTerm; i++){
        Fts5PoslistReader *pPos = &aIter[i];
        i64 iAdj = iPos + i;
        if( pPos->iPos!=iAdj ){
          bMatch = 0;
          while( pPos->iPos<iAdj ){
            if( sqlite3Fts5PoslistReaderNext(pPos) ) goto ismatch_out;
          }
          if( pPos->iPos>iAdj ) iPos = pPos->iPos-i;
        }
      }
    }while( bMatch==0 );

    /* Append position iPos to the output */
    rc = sqlite3Fts5PoslistWriterAppend(&pPhrase->poslist, &writer, iPos);
    if( rc!=SQLITE_OK ) goto ismatch_out;

    for(i=0; i<pPhrase->nTerm; i++){
      if( sqlite3Fts5PoslistReaderNext(&aIter[i]) ) goto ismatch_out;
    }
  }

 ismatch_out:
  *pbMatch = (pPhrase->poslist.n>0);
  if( aIter!=aStatic ) sqlite3_free(aIter);
  return rc;

** final value of *pbMatch is undefined.
**
** TODO: This function should also edit the position lists associated
** with each phrase to remove any phrase instances that are not part of
** a set of intances that collectively matches the NEAR constraint.
*/
static int fts5ExprNearIsMatch(Fts5ExprNearset *pNear, int *pbMatch){
  Fts5PoslistReader aStatic[4];
  Fts5PoslistReader *aIter = aStatic;
  int i;
  int rc = SQLITE_OK;
  int bMatch;
  i64 iMax;

  assert( pNear->nPhrase>1 );

  /* If the aStatic[] array is not large enough, allocate a large array
  ** using sqlite3_malloc(). This approach could be improved upon. */
  if( pNear->nPhrase>(sizeof(aStatic) / sizeof(aStatic[0])) ){
    int nByte = sizeof(Fts5PoslistReader) * pNear->nPhrase;
    aIter = (Fts5PoslistReader*)sqlite3_malloc(nByte);
    if( !aIter ) return SQLITE_NOMEM;
  }

  /* Initialize a term iterator for each phrase */
  for(i=0; i<pNear->nPhrase; i++){
    Fts5Buffer *pPoslist = &pNear->apPhrase[i]->poslist; 
    sqlite3Fts5PoslistReaderInit(-1, pPoslist->p, pPoslist->n, &aIter[i]);
  }

  iMax = aIter[0].iPos;
  do {
    bMatch = 1;
    for(i=0; i<pNear->nPhrase; i++){
      Fts5PoslistReader *pPos = &aIter[i];
      i64 iMin = iMax - pNear->apPhrase[i]->nTerm - pNear->nNear;
      if( pPos->iPos<iMin || pPos->iPos>iMax ){
        bMatch = 0;
        while( pPos->iPos<iMin ){
          if( sqlite3Fts5PoslistReaderNext(pPos) ) goto ismatch_out;
        }
        if( pPos->iPos>iMax ) iMax = pPos->iPos;
      }
    }
  }while( bMatch==0 );

 ismatch_out:

typedef struct Fts5MultiSegIter Fts5MultiSegIter;
typedef struct Fts5NodeIter Fts5NodeIter;
typedef struct Fts5PageWriter Fts5PageWriter;
typedef struct Fts5PendingDoclist Fts5PendingDoclist;
typedef struct Fts5PendingPoslist Fts5PendingPoslist;
typedef struct Fts5PosIter Fts5PosIter;
typedef struct Fts5SegIter Fts5SegIter;
typedef struct Fts5DoclistIter Fts5DoclistIter;
typedef struct Fts5SegWriter Fts5SegWriter;
typedef struct Fts5Structure Fts5Structure;
typedef struct Fts5StructureLevel Fts5StructureLevel;
typedef struct Fts5StructureSegment Fts5StructureSegment;


/*

  int rc;                         /* Current error code */

  /* State used by the fts5DataXXX() functions. */
  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<=?" */
};

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

  /* Output variables. aPoslist==0 at EOF */
  i64 iRowid;
  u8 *aPoslist;
  int nPoslist;
};

struct Fts5IndexIter {
  Fts5Index *pIndex;
  Fts5Structure *pStruct;
  Fts5MultiSegIter *pMulti;
  Fts5DoclistIter *pDoclist;
  Fts5Buffer poslist;             /* Buffer containing current poslist */
};

/*
** A single record read from the %_data table.
*/
struct Fts5Data {

** pLeaf:
**   Buffer containing current leaf page data. Set to NULL at EOF.
**
** iTermLeafPgno, iTermLeafOffset:
**   Leaf page number containing the last term read from the segment. And
**   the offset immediately following the term data.
**
** flags:
**   Mask of FTS5_SEGITER_XXX values. Interpreted as follows:
**
**   FTS5_SEGITER_ONETERM:
**     If set, set the iterator to point to EOF after the current doclist 
**     has been exhausted. Do not proceed to the next term in the segment.
*/
struct Fts5SegIter {
  Fts5StructureSegment *pSeg;     /* Segment to iterate through */
  int iIdx;                       /* Byte offset within current leaf */
  int flags;                      /* Mask of configuration flags */
  int iLeafPgno;                  /* Current leaf page number */
  Fts5Data *pLeaf;                /* Current leaf data */
  int iLeafOffset;                /* Byte offset within current leaf */

  int iTermLeafPgno;
  int iTermLeafOffset;

  /* Variables populated based on current entry. */
  Fts5Buffer term;                /* Current term */
  i64 iRowid;                     /* Current rowid */
};

#define FTS5_SEGITER_ONETERM 0x01


/*
** Object for iterating through paginated data.
*/
struct Fts5ChunkIter {
  Fts5Data *pLeaf;                /* Current leaf data. NULL -> EOF. */
  i64 iLeafRowid;                 /* Absolute rowid of current leaf */
  int nRem;                       /* Remaining bytes of data to read */

  /* Output parameters */
  u8 *p;                          /* Pointer to chunk of data */
  int n;                          /* Size of buffer p in bytes */
};

/*
** Object for iterating through a single position list on disk.
*/
struct Fts5PosIter {
  Fts5ChunkIter chunk;            /* Current chunk of data */
  int iOff;                       /* Offset within chunk data */

  int iCol;
  int iPos;

  const u8 *pRight, int nRight    /* Right hand side of comparison */
){
  int nCmp = MIN(pLeft->n, nRight);
  int res = memcmp(pLeft->p, pRight, nCmp);
  return (res==0 ? (pLeft->n - nRight) : res);
}

#if 0
static int fts5CompareBlob(
  const u8 *pLeft, int nLeft,
  const u8 *pRight, int nRight
){
  int nCmp = MIN(nLeft, nRight);
  int res = memcmp(pLeft, pRight, nCmp);
  return (res==0 ? (nLeft - nRight) : res);
}
#endif

/*
** Compare the contents of the two buffers using memcmp(). If one buffer
** is a prefix of the other, it is considered the lesser.
**
** Return -ve if pLeft is smaller than pRight, 0 if they are equal or
** +ve if pRight is smaller than pLeft. In other words:
**

/*
** Release a reference to data record returned by an earlier call to
** fts5DataRead().
*/
static void fts5DataRelease(Fts5Data *pData){
  if( pData ){
    assert( pData->nRef>0 );
    pData->nRef--;
    if( pData->nRef==0 ) sqlite3_free(pData);
  }
}

static void fts5DataReference(Fts5Data *pData){
  pData->nRef++;

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


























































































/*
** Advance iterator pIter to the next entry. 
**
** If an error occurs, Fts5Index.rc is set to an appropriate error code. It 
** is not considered an error if the iterator reaches EOF. If an error has 
** already occurred when this function is called, it is a no-op.
*/

          bNewTerm = 1;
        }
      }
    }

    /* Check if the iterator is now at EOF. If so, return early. */
    if( pIter->pLeaf && bNewTerm ){
      if( pIter->flags & FTS5_SEGITER_ONETERM ){
        fts5DataRelease(pIter->pLeaf);
        pIter->pLeaf = 0;
      }else{
        fts5SegIterLoadTerm(p, pIter, nKeep);
      }
    }
  }
}

/*
** Initialize the object pIter to point to term pTerm/nTerm within segment
** pSeg, index iIdx. If there is no such term in the index, the iterator
** is set to EOF.
**
** If an error occurs, Fts5Index.rc is set to an appropriate error code. If 
** an error has already occurred when this function is called, it is a no-op.
*/
static void fts5SegIterSeekInit(
  Fts5Index *p,                   /* FTS5 backend */
  int iIdx,                       /* Config.aHash[] index of FTS index */
  const u8 *pTerm, int nTerm,     /* Term to seek to */
  int bGe,                        /* If true seek for >=. If false, == */
  Fts5StructureSegment *pSeg,     /* Description of segment */
  Fts5SegIter *pIter              /* Object to populate */
){
  int iPg = 1;
  int h;

  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. */
  for(h=pSeg->nHeight-1; h>0; h--){
    Fts5NodeIter node;              /* For iterating through internal nodes */
    i64 iRowid = FTS5_SEGMENT_ROWID(iIdx, pSeg->iSegid, h, iPg);
    Fts5Data *pNode = fts5DataRead(p, iRowid);
    if( pNode==0 ) break;

    fts5NodeIterInit(pNode->p, pNode->n, &node);
    assert( node.term.n==0 );

    iPg = node.iChild;
    for(fts5NodeIterNext(&p->rc, &node);
        node.aData && fts5BufferCompareBlob(&node.term, pTerm, nTerm)<=0;
        fts5NodeIterNext(&p->rc, &node)
    ){
      iPg = node.iChild;
    }
    fts5NodeIterFree(&node);
    fts5DataRelease(pNode);
  }

  if( iPg<pSeg->pgnoFirst ){
    iPg = pSeg->pgnoFirst;
  }

  pIter->iLeafPgno = iPg - 1;
  fts5SegIterNextPage(p, pIter);

  if( pIter->pLeaf ){
    int res;
    pIter->iLeafOffset = fts5GetU16(&pIter->pLeaf->p[2]);
    fts5SegIterLoadTerm(p, pIter, 0);
    do {
      res = fts5BufferCompareBlob(&pIter->term, pTerm, nTerm);
      if( res>=0 ) break;
      fts5SegIterNext(p, pIter);
    }while( pIter->pLeaf );

    if( bGe==0 && res ){
      /* Set iterator to point to EOF */
      fts5DataRelease(pIter->pLeaf);
      pIter->pLeaf = 0;
    }
  }

  if( bGe==0 ) pIter->flags |= FTS5_SEGITER_ONETERM;
}

/*
** Zero the iterator passed as the only argument.
*/
static void fts5SegIterClear(Fts5SegIter *pIter){
  fts5BufferFree(&pIter->term);
  fts5DataRelease(pIter->pLeaf);

** The iterator initially points to the first term/rowid entry in the 
** iterated data.
*/
static void fts5MultiIterNew(
  Fts5Index *p,                   /* FTS5 backend to iterate within */
  Fts5Structure *pStruct,         /* Structure of specific index */
  int iIdx,                       /* Config.aHash[] index of FTS index */
  int bGe,                        /* True for >= */
  const u8 *pTerm, int nTerm,     /* Term to seek to (or NULL/0) */
  int iLevel,                     /* Level to iterate (-1 for all) */
  int nSegment,                   /* Number of segments to merge (iLevel>=0) */
  Fts5MultiSegIter **ppOut        /* New object */
){
  int nSeg;                       /* Number of segments merged */
  int nSlot;                      /* Power of two >= nSeg */

  pNew->aFirst = (u16*)&pNew->aSeg[nSlot];

  /* 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--){
        Fts5StructureSegment *pSeg = &pLvl->aSeg[iSeg];
        Fts5SegIter *pIter = &pNew->aSeg[iIter++];
        if( pTerm==0 ){
          fts5SegIterInit(p, iIdx, pSeg, pIter);
        }else{
          fts5SegIterSeekInit(p, iIdx, pTerm, nTerm, bGe, pSeg, pIter);
        }
      }
    }
  }else{
    pLvl = &pStruct->aLevel[iLevel];
    for(iSeg=nSeg-1; iSeg>=0; iSeg--){
      fts5SegIterInit(p, iIdx, &pLvl->aSeg[iSeg], &pNew->aSeg[iIter++]);

    nInput = pLvl->nSeg;
  }
#if 0
fprintf(stdout, "merging %d segments from level %d!", nInput, iLvl);
fflush(stdout);
#endif

  for(fts5MultiIterNew(p, pStruct, iIdx, 0, 0, 0, iLvl, nInput, &pIter);
      fts5MultiIterEof(p, pIter)==0;
      fts5MultiIterNext(p, pIter)
  ){
    Fts5SegIter *pSeg = &pIter->aSeg[ pIter->aFirst[1] ];
    Fts5ChunkIter sPos;           /* Used to iterate through position list */
    int nTerm;
    const u8 *pTerm = fts5MultiIterTerm(pIter, &nTerm);

  int rc;                         /* Return code */
  u64 cksum2 = 0;                 /* Checksum based on contents of indexes */

  /* Check that the checksum of the index matches the argument checksum */
  for(iIdx=0; iIdx<=pConfig->nPrefix; iIdx++){
    Fts5MultiSegIter *pIter;
    Fts5Structure *pStruct = fts5StructureRead(p, iIdx);
    for(fts5MultiIterNew(p, pStruct, iIdx, 0, 0, 0, -1, 0, &pIter);
        fts5MultiIterEof(p, pIter)==0;
        fts5MultiIterNext(p, pIter)
    ){
      Fts5PosIter sPos;           /* Used to iterate through position list */
      int n;                      /* Size of term in bytes */
      i64 iRowid = fts5MultiIterRowid(pIter);
      char *z = (char*)fts5MultiIterTerm(pIter, &n);

/*
** Set the target page size for the index object.
*/
void sqlite3Fts5IndexPgsz(Fts5Index *p, int pgsz){
  p->pgsz = pgsz;
}

/*
** Iterator pMulti currently points to a valid entry (not EOF). This
** function appends a copy of the position-list of the entry pMulti 
** currently points to to buffer pBuf.
**
** If an error occurs, an error code is left in p->rc. It is assumed
** no error has already occurred when this function is called.
*/
static void fts5MultiIterPoslist(
  Fts5Index *p,
  Fts5MultiSegIter *pMulti,
  int bSz,
  Fts5Buffer *pBuf
){
  Fts5ChunkIter iter;
  Fts5SegIter *pSeg = &pMulti->aSeg[ pMulti->aFirst[1] ];
  assert( fts5MultiIterEof(p, pMulti)==0 );
  fts5ChunkIterInit(p, pSeg, &iter);
  if( fts5ChunkIterEof(p, &iter)==0 ){
    if( bSz ){
      fts5BufferAppendVarint(&p->rc, pBuf, iter.nRem);
    }
    while( fts5ChunkIterEof(p, &iter)==0 ){
      fts5BufferAppendBlob(&p->rc, pBuf, iter.n, iter.p);
      fts5ChunkIterNext(p, &iter);
    }
  }
  fts5ChunkIterRelease(&iter);
}

static void fts5DoclistIterNext(Fts5DoclistIter *pIter){
  if( pIter->i<pIter->n ){
    if( pIter->i ){
      i64 iDelta;
      pIter->i += getVarint(&pIter->a[pIter->i], (u64*)&iDelta);
      pIter->iRowid -= iDelta;
    }else{
      pIter->i += getVarint(&pIter->a[pIter->i], (u64*)&pIter->iRowid);
    }
    pIter->i += getVarint32(&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, Fts5DoclistIter *pIter){
  memset(pIter, 0, sizeof(*pIter));
  pIter->a = pBuf->p;
  pIter->n = pBuf->n;
  fts5DoclistIterNext(pIter);
}

/*
** Append a doclist to buffer pBuf.
*/
static void fts5MergeAppendDocid(
  int *pRc,                       /* IN/OUT: Error code */
  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{
    fts5BufferAppendVarint(pRc, pBuf, *piLastRowid - iRowid);
  }
  *piLastRowid = iRowid;
}

/*
** Buffers p1 and p2 contain doclists. This function merges the content
** of the two doclists together and sets buffer p1 to the result before
** 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 */
  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, &i1);
    fts5DoclistIterInit(p2, &i2);
    while( i1.aPoslist!=0 || i2.aPoslist!=0 ){
      if( i2.aPoslist==0 || (i1.aPoslist && i1.iRowid>i2.iRowid) ){
        /* Copy entry from i1 */
        fts5MergeAppendDocid(&p->rc, &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, &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, &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;
            sqlite3Fts5PoslistReaderNext(&r1);
          }else{
            iNew = r2.iPos;
            sqlite3Fts5PoslistReaderNext(&r2);
            if( r1.iPos==r2.iPos ) sqlite3Fts5PoslistReaderNext(&r1);
          }
          p->rc = sqlite3Fts5PoslistWriterAppend(&tmp, &writer, iNew);
        }

        fts5BufferAppendVarint(&p->rc, &out, tmp.n);
        fts5BufferAppendBlob(&p->rc, &out, tmp.n, tmp.p);
        fts5DoclistIterNext(&i1);
        fts5DoclistIterNext(&i2);
      }
    }

    fts5BufferSet(&p->rc, p1, out.n, out.p);
    fts5BufferFree(&tmp);
    fts5BufferFree(&out);
  }
}

static void fts5BufferSwap(Fts5Buffer *p1, Fts5Buffer *p2){
  Fts5Buffer tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

static void fts5SetupPrefixIter(
  Fts5Index *p,                   /* Index to read from */
  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;


  aBuf = (Fts5Buffer*)fts5IdxMalloc(p, sizeof(Fts5Buffer)*nBuf);
  pStruct = fts5StructureRead(p, 0);

  if( aBuf && pStruct ){
    Fts5DoclistIter *pDoclist;
    int i;
    i64 iLastRowid;
    Fts5MultiSegIter *p1 = 0;     /* Iterator used to gather data from index */
    Fts5Buffer doclist;

    memset(&doclist, 0, sizeof(doclist));
    for(fts5MultiIterNew(p, pStruct, 0, 1, pToken, nToken, -1, 0, &p1);
        fts5MultiIterEof(p, p1)==0;
        fts5MultiIterNext(p, p1)
    ){
      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 && iRowid>=iLastRowid ){
        for(i=0; doclist.n && p->rc==SQLITE_OK; i++){
          assert( i<nBuf );
          if( aBuf[i].n==0 ){
            fts5BufferSwap(&doclist, &aBuf[i]);
            fts5BufferZero(&doclist);
          }else{
            fts5MergePrefixLists(p, &doclist, &aBuf[i]);
            fts5BufferZero(&aBuf[i]);
          }
        }
      }
      if( doclist.n==0 ){
        fts5BufferAppendVarint(&p->rc, &doclist, iRowid);
      }else{
        fts5BufferAppendVarint(&p->rc, &doclist, iLastRowid - iRowid);
      }
      iLastRowid = iRowid;
      fts5MultiIterPoslist(p, p1, 1, &doclist);
    }

    for(i=0; i<nBuf; i++){
      fts5MergePrefixLists(p, &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, pIter->pDoclist);
    }
  }

  fts5StructureRelease(pStruct);
  sqlite3_free(aBuf);
}

/*
** Open a new iterator to iterate though all docids that match the 
** specified token or token prefix.
*/
Fts5IndexIter *sqlite3Fts5IndexQuery(
  Fts5Index *p,                   /* FTS index to query */
  const char *pToken, int nToken, /* Token (or prefix) to query for */
  int flags                       /* Mask of FTS5INDEX_QUERY_X flags */
){
  Fts5IndexIter *pRet;
  int iIdx = 0;

  if( flags & FTS5INDEX_QUERY_PREFIX ){
    Fts5Config *pConfig = p->pConfig;
    for(iIdx=1; iIdx<=pConfig->nPrefix; iIdx++){
      if( pConfig->aPrefix[iIdx-1]==nToken ) break;
    }
    if( iIdx>pConfig->nPrefix ){
      iIdx = -1;

    }
  }

  pRet = (Fts5IndexIter*)sqlite3_malloc(sizeof(Fts5IndexIter));
  if( pRet ){
    memset(pRet, 0, sizeof(Fts5IndexIter));

    pRet->pIndex = p;
    if( iIdx>=0 ){
      pRet->pStruct = fts5StructureRead(p, iIdx);
      if( pRet->pStruct ){
        fts5MultiIterNew(p, pRet->pStruct, 
            iIdx, 0, (const u8*)pToken, nToken, -1, 0, &pRet->pMulti
        );
      }
    }else{
      fts5SetupPrefixIter(p, (const u8*)pToken, nToken, pRet);
    }
  }

  if( p->rc ){
    sqlite3Fts5IterClose(pRet);
    pRet = 0;
  }
  return pRet;
}

/*
** Return true if the iterator passed as the only argument is at EOF.
*/
int sqlite3Fts5IterEof(Fts5IndexIter *pIter){
  if( pIter->pDoclist ){ 
    return pIter->pDoclist->aPoslist==0; 
  }else{
    return fts5MultiIterEof(pIter->pIndex, pIter->pMulti);
  }
}

/*
** Move to the next matching rowid. 
*/
void sqlite3Fts5IterNext(Fts5IndexIter *pIter, i64 iMatch){
  if( pIter->pDoclist ){
    fts5DoclistIterNext(pIter->pDoclist);
  }else{
    fts5BufferZero(&pIter->poslist);
    fts5MultiIterNext(pIter->pIndex, pIter->pMulti);
  }
}

/*
** Return the current rowid.
*/
i64 sqlite3Fts5IterRowid(Fts5IndexIter *pIter){
  if( pIter->pDoclist ){
    return pIter->pDoclist->iRowid;
  }else{
    return fts5MultiIterRowid(pIter->pMulti);
  }
}


/*
** Return a pointer to a buffer containing a copy of the position list for
** the current entry. Output variable *pn is set to the size of the buffer 
** in bytes before returning.
**
** The returned buffer does not include the 0x00 terminator byte stored on
** disk.
*/
const u8 *sqlite3Fts5IterPoslist(Fts5IndexIter *pIter, int *pn){
  if( pIter->pDoclist ){
    *pn = pIter->pDoclist->nPoslist;
    return pIter->pDoclist->aPoslist;
  }else{
    Fts5Index *p = pIter->pIndex;





    fts5BufferZero(&pIter->poslist);







    fts5MultiIterPoslist(p, pIter->pMulti, 0, &pIter->poslist);
    if( p->rc ) return 0;
    *pn = pIter->poslist.n;
    return pIter->poslist.p;
  }
}

/*
** Close an iterator opened by an earlier call to sqlite3Fts5IndexQuery().
*/
void sqlite3Fts5IterClose(Fts5IndexIter *pIter){
  if( pIter ){
    if( pIter->pDoclist ){
      sqlite3_free(pIter->pDoclist->a);
      sqlite3_free(pIter->pDoclist);
    }else{
      fts5MultiIterFree(pIter->pIndex, pIter->pMulti);
      fts5StructureRelease(pIter->pStruct);

      fts5BufferFree(&pIter->poslist);
    }
    fts5CloseReader(pIter->pIndex);
    sqlite3_free(pIter);
  }
}

# 2014 June 17
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#*************************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is testing the FTS5 module.
#
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix fts5ad

# If SQLITE_ENABLE_FTS3 is defined, omit this file.
ifcapable !fts3 {
  finish_test
  return
}

do_execsql_test 1.0 {
  CREATE VIRTUAL TABLE yy USING fts5(x, y);
  INSERT INTO yy VALUES('Changes the result to be', 'the list of all matching');
  INSERT INTO yy VALUES('indices (or all  matching', 'values if -inline is');
  INSERT INTO yy VALUES('specified as  well.) If', 'indices are returned, the');
} {}

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 {T create} {
  2 {
    CREATE VIRTUAL TABLE t1 USING fts5(a, b);
    INSERT INTO t1(t1) VALUES('pgsz=32');
  }
  
  3 {
    CREATE VIRTUAL TABLE t1 USING fts5(a, b, prefix=1,2,3,4,5);
    INSERT INTO t1(t1) VALUES('pgsz=32');
  }

} {

  do_test $T.1 { 
    execsql { DROP TABLE IF EXISTS t1 }
    execsql $create
  } {}
  
  do_test $T.1 {
    foreach {rowid a b} {
      0   {fghij uvwxyz klmn pq uvwx}         {klmn f fgh uv fghij klmno}
      1   {uv f abcd abcd fghi}               {pq klm uv uv fgh uv a}
      2   {klmn klm pqrs fghij uv}            {f k uvw ab abcd pqr uv}
      3   {ab pqrst a fghi ab pqr fg}         {k klmno a fg abcd}
      4   {abcd pqrst uvwx a fgh}             {f klmno fghij kl pqrst}
      5   {uvwxyz k abcde u a}                {uv k k kl klmn}
      6   {uvwxyz k klmn pqrst uv}            {fghi pqrs abcde u k}
      7   {uvwxy klmn u p pqrst fgh}          {p f fghi abcd uvw kl uv}
      8   {f klmno pqrst uvwxy pqrst}         {uv abcde klm pq pqr}
      9   {f abcde a uvwxyz pqrst}            {fghij abc k uvwx pqr fghij uvwxy}
      10  {ab uv f fg pqrst uvwxy}            {fgh p uv k abc klm uvw}
      11  {pq klmno a uvw abcde uvwxyz}       {fghij pq uvwxyz pqr fghi}
      12  {fgh u pq fgh uvw}                  {uvw pqr f uvwxy uvwx}
      13  {uvwx klmn f fgh abcd pqr}          {uvw k fg uv klm abcd}
      14  {ab uvwx pqrst pqr uvwxyz pqrs}     {uvwxyz abcde ab ab uvw abcde}
      15  {abc abcde uvwxyz abc kl k pqr}     {klm k k klmno u fgh}
      16  {fghi abcd fghij uv uvwxyz ab uv}   {klmn pqr a uvw fghi}
      17  {abc pqrst fghi uvwx uvw klmn fghi} {ab fg pqr pqrs p}
      18  {pqr kl a fghij fgh fg kl}          {pqr uvwxyz uvw abcd uvwxyz}
      19  {fghi fghi pqr kl fghi f}           {klmn u u klmno klmno}
      20  {abc pqrst klmno kl pq uvwxy}       {abc k fghi pqrs klm}
      21  {a pqr uvwxyz uv fghi a fgh}        {abc pqrs pqrst pq klm}
      22  {klm abc uvwxyz klm pqrst}          {fghij k pq pqr u klm fghij}
      23  {p klm uv p a a}                    {uvwxy klmn uvw abcde pq}
      24  {uv fgh fg pq uvwxy u uvwxy}        {pqrs a uvw p uvwx uvwxyz fg}
      25  {fghij fghi klmn abcd pq kl}        {fghi abcde pqrs abcd fgh uvwxy}
      26  {pq fgh a abc klmno klmn}           {fgh p k p fg fghij}
      27  {fg pq kl uvwx fghij pqrst klmn}    {abcd uvw abcd fghij f fghij}
      28  {uvw fghi p fghij pq fgh uvwx}      {k fghij abcd uvwx pqr fghi}
      29  {klm pq abcd pq f uvwxy}            {pqrst p fghij pqr p}
      30  {ab uvwx fg uvwx klmn klm}          {klmn klmno fghij klmn klm}
      31  {pq k pqr abcd a pqrs}              {abcd abcd uvw a abcd klmno ab}
      32  {pqrst u abc pq klm}                {abc kl uvwxyz fghij u fghi p}
      33  {f uvwxy u k f uvw uvwx}            {pqrs uvw fghi fg pqrst klm}
      34  {pqrs pq fghij uvwxyz pqr}          {ab abc abc uvw f pq f}
      35  {uvwxy ab uvwxy klmno kl pqrs}      {abcde uvw pqrs uvwx k k}
      36  {uvwxyz k ab abcde abc uvw}         {uvw abcde uvw klmn uv klmn}
      37  {k kl uv abcde uvwx fg u}           {u abc uvwxy k fg abcd}
      38  {fghi pqrst fghi pqr pqrst uvwx}    {u uv uvwx fghi abcde}
      39  {k pqrst k uvw fg pqrst fghij}      {uvwxy ab kl klmn uvwxyz abcde}
      40  {fg uvwxy pqrs klmn uvwxyz klm p}   {k uv ab fghij fgh k pqrs}
      41  {uvwx abc f pq uvwxy k}             {ab uvwxyz abc f fghij}
      42  {uvwxy klmno uvwxyz uvwxyz pqrst}   {uv kl kl klmno k f abcde}
      43  {abcde ab pqrs fg f fgh}            {abc fghij fghi k k}
      44  {uvw abcd a ab pqrst klmn fg}       {pqrst u uvwx pqrst fghij f pqrst}
      45  {uvwxy p kl uvwxyz ab pqrst fghi}   {abc f pqr fg a k}
      46  {u p f a fgh}                       {a kl pq uv f}
      47  {pqrs abc fghij fg abcde ab a}      {p ab uv pqrs kl fghi abcd}
      48  {abcde uvwxy pqrst uv abc pqr uvwx} {uvwxy klm uvwxy uvwx k}
      49  {fgh klm abcde klmno u}             {a f fghij f uvwxyz abc u}
      50  {uv uvw uvwxyz uvwxyz uv ab}        {uvwx pq fg u k uvwxy}
      51  {uvwxy pq p kl fghi}                {pqrs fghi pqrs abcde uvwxyz ab}
      52  {pqr p uvwxy kl pqrs klmno fghij}   {ab abcde abc pqrst pqrs uv}
      53  {fgh pqrst p a klmno}               {ab ab pqrst pqr kl pqrst}
      54  {abcd klm ab uvw a fg u}            {f pqr f abcd uv}
      55  {u fg uvwxyz k uvw}                 {abc pqrs f fghij fg pqrs uvwxy}
      56  {klm fg p fghi fg a}                {uv a fghi uvwxyz a fghi}
      57  {uvwxy k abcde fgh f fghi}          {f kl klmn f fghi klm}
      58  {klm k fgh uvw fgh fghi}            {klmno uvwx u pqrst u}
      59  {fghi pqr pqrst p uvw fghij}        {uv pqrst pqrs pq fghij klm}
      60  {uvwx klm uvwxy uv klmn}            {p a a abc klmn ab k}
      61  {uvwxy uvwx klm uvwx klm}           {pqrs ab ab uvwxyz fg}
      62  {kl uv uv uvw fg kl k}              {abcde uvw fgh uvwxy klm}
      63  {a abc fgh u klm abcd}              {fgh pqr uv klmn fghij}
      64  {klmn k klmn klmno pqrs pqr}        {fg kl abcde klmno uvwxy kl pq}
      65  {uvwxyz klm fghi abc abcde kl}      {uvwxy uvw uvwxyz uvwxyz pq pqrst}
      66  {pq klm abc pqrst fgh f}            {u abcde pqrst abcde fg}
      67  {u pqrst kl u uvw klmno}            {u pqr pqrs fgh u p}
      68  {abc fghi uvwxy fgh k pq}           {uv p uvwx uvwxyz ab}
      69  {klmno f uvwxyz uvwxy klmn fg ab}   {fgh kl a pqr abcd pqr}
      70  {fghi pqrst pqrst uv a}             {uvwxy k p uvw uvwx a}
      71  {a fghij f p uvw}                   {klm fg abcd abcde klmno pqrs}
      72  {uv uvwx uvwx uvw klm}              {uv fghi klmno uvwxy uvw}
      73  {kl uvwxy ab f pq klm u}            {uvwxy klmn klm abcd pq fg k}
      74  {uvw pqrst abcd uvwxyz ab}          {fgh fgh klmn abc pq}
      75  {uvwxyz klm pq abcd klmno pqr uvwxyz} {kl f a fg pqr klmn}
      76  {uvw uvwxy pqr k pqrst kl}          {uvwxy abc uvw uvw u}
      77  {fgh klm u uvwxyz f uvwxy abcde}    {uv abcde klmno u u ab}
      78  {klmno abc pq pqr fgh}              {p uv abcd fgh abc u k}
      79  {fg pqr uvw pq uvwx}                {uv uvw fghij pqrs fg p}
      80  {abcd pqrs uvwx uvwxy uvwx}         {u uvw pqrst pqr abcde pqrs kl}
      81  {uvwxyz klm pq uvwxy fghij}         {p pq klm fghij u a a}
      82  {uvwx k uvwxyz klmno pqrst kl}      {abcde p f pqrst abcd uvwxyz p}
      83  {abcd abcde klm pqrst uvwxyz}       {uvw pqrst u p uvwxyz a pqrs}
      84  {k klm abc uv uvwxy klm klmn}       {k abc pqr a abc p kl}
      85  {klmn abcd pqrs p pq klm a}         {klmn kl ab uvw pq}
      86  {klmn a pqrs abc uvw pqrst}         {a pqr kl klm a k f}
      87  {pqrs ab uvwx uvwxy a pqr f}        {fg klm uvwx pqr pqr}
      88  {klmno ab k kl u uvwxyz}            {uv kl uvw fghi uv uvw}
      89  {pq fghi pqrst klmn uvwxy abc pqrs} {fg f f fg abc abcde klm}
      90  {kl a k fghi uvwx fghi u}           {ab uvw pqr fg a p abc}
      91  {uvwx pqrs klmno ab fgh uvwx}       {pqr uvwx abc kl f klmno kl}
      92  {fghij pq pqrs fghij f pqrst}       {u abcde fg pq pqr fgh k}
      93  {fgh u pqrs abcde klmno abc}        {abc fg pqrst pqr abcde}
      94  {uvwx p abc f pqr p}                {k pqrs kl klm abc fghi klm}
      95  {kl p klmno uvwxyz klmn}            {fghi ab a fghi pqrs kl}
      96  {pqr fgh pq uvwx a}                 {uvw klm klmno fg uvwxy uvwx}
      97  {fg abc uvwxyz fghi pqrst pq}       {abc k a ab abcde f}
      98  {uvwxy fghi uvwxy u abcde abcde uvw} {klmn uvwx pqrs uvw uvwxy abcde}
      99  {pq fg fghi uvwx uvwx fghij uvwxy}  {klmn klmn f abc fg a}
    } {
      execsql {
        INSERT INTO t1(rowid, a, b) VALUES($rowid, $a, $b);
      }
    }
  } {}
  
  proc prefix_query {prefix} {
    set ret [list]
    db eval {SELECT rowid, a, b FROM t1 ORDER BY rowid DESC} {
      if {[lsearch -glob $a $prefix]>=0 || [lsearch -glob $b $prefix]>=0} {
        lappend ret $rowid
      }
    }
    return $ret
  }
  
  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*}
    27 {x*}
  } {
    set res [prefix_query $prefix]
    set n [llength $res]
    do_execsql_test $T.$tn.$n {SELECT rowid FROM t1 WHERE t1 MATCH $prefix} $res
  }
}

finish_test