SQLite

**
** 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;
  while( 1 ){
    iRowid = sqlite3Fts5IterRowid(pIter);
    if( (bAsc==0 && iRowid<=iLast) || (bAsc==1 && iRowid>=iLast) ) break;
    sqlite3Fts5IterNext(pIter, 0);
    if( sqlite3Fts5IterEof(pIter) ){
      *pbEof = 1;
      return 1;
    }
  }
  if( iRowid!=iLast ){
    assert( (bAsc==0 && iRowid<iLast) || (bAsc==1 && iRowid>iLast) );
    *piLast = iRowid;
  }

  return 0;
}

/*
** All individual term iterators in pNear are guaranteed to be valid when

static int fts5ExprNearNextRowidMatch(
  Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
  Fts5ExprNode *pNode
){
  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);

  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;
  return rc;
}

/*
** Argument pNode points to a NEAR node. All individual term iterators 
** point to valid entries (not EOF).
*

    for(j=0; j<pPhrase->nTerm; j++){
      pTerm = &pPhrase->aTerm[j];
      pTerm->pIter = sqlite3Fts5IndexQuery(
          pExpr->pIndex, pTerm->zTerm, strlen(pTerm->zTerm),
          (pTerm->bPrefix ? FTS5INDEX_QUERY_PREFIX : 0) |
          (pExpr->bAsc ? FTS5INDEX_QUERY_ASC : 0)
      );
      if( pTerm->pIter && sqlite3Fts5IterEof(pTerm->pIter) ){
        pNode->bEof = 1;
        return SQLITE_OK;
      }
    }
  }

  return SQLITE_OK;
}

/* fts3ExprNodeNext() calls fts5ExprNodeNextMatch(). And vice-versa. */
static int fts5ExprNodeNextMatch(Fts5Expr*, Fts5ExprNode*);

/*
** Compare the values currently indicated by the two nodes as follows:

**
**    res = (*p1) - (*p2)
**
** Nodes that point to values that come later in the iteration order are
** considered to be larger. Nodes at EOF are the largest of all.
**
** This means that if the iteration order is ASC, then numerically larger
** rowids are considered larger. Or if it is the default DESC, numerically
** smaller rowids are larger.
*/
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);
  }
}

static int fts5ExprNodeNext(Fts5Expr *pExpr, Fts5ExprNode *pNode){
  int rc = SQLITE_OK;

  if( pNode->bEof==0 ){
    switch( pNode->eType ){

        if( rc==SQLITE_OK ) rc = fts5ExprNodeNext(pExpr, pNode->pRight);
        break;
      }

      case FTS5_OR: {
        Fts5ExprNode *p1 = pNode->pLeft;
        Fts5ExprNode *p2 = pNode->pRight;
        int cmp = fts5NodeCompare(pExpr, p1, p2);

        if( cmp==0 ){
          rc = fts5ExprNodeNext(pExpr, p1);
          if( rc==SQLITE_OK ) rc = fts5ExprNodeNext(pExpr, p2);
        }else{
          rc = fts5ExprNodeNext(pExpr, (cmp < 0) ? p1 : p2);
        }

      }

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

        while( p1->bEof==0 && p2->bEof==0 && p2->iRowid!=p1->iRowid ){
          Fts5ExprNode *pAdv;
          if( pExpr->bAsc ){
            pAdv = (p1->iRowid < p2->iRowid) ? p1 : p2;
          }else{
            pAdv = (p1->iRowid > p2->iRowid) ? p1 : p2;
          }
          rc = fts5ExprNodeNext(pExpr, pAdv);
          if( rc!=SQLITE_OK ) break;
        }
        pNode->bEof = p1->bEof || p2->bEof;
        pNode->iRowid = p1->iRowid;
        break;
      }

      case FTS5_OR: {
        Fts5ExprNode *p1 = pNode->pLeft;
        Fts5ExprNode *p2 = pNode->pRight;
        Fts5ExprNode *pNext = (fts5NodeCompare(pExpr, p1, p2) > 0 ? p2 : p1);
        pNode->bEof = pNext->bEof;
        pNode->iRowid = pNext->iRowid;
        break;
      }

      default: assert( pNode->eType==FTS5_NOT ); {
        Fts5ExprNode *p1 = pNode->pLeft;
        Fts5ExprNode *p2 = pNode->pRight;
        while( rc==SQLITE_OK ){
          int cmp;
          while( rc==SQLITE_OK && (cmp = fts5NodeCompare(pExpr, p1, p2))>0 ){
            rc = fts5ExprNodeNext(pExpr, p2);
          }
          if( rc || cmp ) break;
          rc = fts5ExprNodeNext(pExpr, p1);
        }
        pNode->bEof = p1->bEof;
        pNode->iRowid = p1->iRowid;

  /* 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 {
  int bAsc;
  u8 *a;
  int n;
  int i;

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

** considered to be greater than all other iterators.
**
** aFirst[1] contains the index in aSeg[] of the iterator that points to
** the smallest key overall. aFirst[0] is unused. 
*/
struct Fts5MultiSegIter {
  int nSeg;                       /* Size of aSeg[] array */
  int bRev;                       /* True to iterate in reverse order */
  Fts5SegIter *aSeg;              /* Array of segment iterators */
  u16 *aFirst;                    /* Current merge state (see above) */
};

/*
** Object for iterating through a single segment, visiting each term/docid
** pair in the segment.

**
** 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.
**
**   FTS5_SEGITER_REVERSE:
**     This flag is only ever set if FTS5_SEGITER_ONETERM is also set. If
**     it is set, iterate through docids in ascending order instead of the
**     default descending order.
**
** iRowidOffset/nRowidOffset/aRowidOffset:
**     These are used if the FTS5_SEGITER_REVERSE flag is set.
**
**     Each time a new page is loaded, the iterator is set to point to the
**     final rowid. Additionally, the aRowidOffset[] array is populated 
**     with the byte offsets of all relevant rowid fields on the page. 
*/
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 */

  /* The page and offset from which the current term was read. The offset 
  ** is the offset of the first rowid in the current doclist.  */
  int iTermLeafPgno;
  int iTermLeafOffset;

  /* The following are only used if the FTS5_SEGITER_REVERSE flag is set. */
  int iRowidOffset;               /* Current entry in aRowidOffset[] */
  int nRowidOffset;               /* Allocated size of aRowidOffset[] array */
  int *aRowidOffset;              /* Array of offset to rowid fields */

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

#define FTS5_SEGITER_ONETERM 0x01
#define FTS5_SEGITER_REVERSE 0x02


/*
** Object for iterating through paginated data.
*/
struct Fts5ChunkIter {
  Fts5Data *pLeaf;                /* Current leaf data. NULL -> EOF. */

  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
** the aRowidOffset[] and iRowidOffset variables.
*/
static void fts5SegIterReverseInitPage(Fts5Index *p, Fts5SegIter *pIter){
  int n = pIter->pLeaf->n;
  int i = pIter->iLeafOffset;
  u8 *a = pIter->pLeaf->p;
  int iRowidOffset = 0;

  while( p->rc==SQLITE_OK && i<n ){
    i64 iDelta = 0;
    int nPos;

    i += getVarint32(&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;
      }
      pIter->aRowidOffset = aNew;
      pIter->nRowidOffset = nNew;
    }

    pIter->aRowidOffset[iRowidOffset++] = pIter->iLeafOffset;
    pIter->iLeafOffset = i;
  }
  pIter->iRowidOffset = iRowidOffset;
}


/*
** 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.
*/
static void fts5SegIterNext(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5SegIter *pIter              /* Iterator to advance */
){
  if( p->rc==SQLITE_OK ){
    if( pIter->flags & FTS5_SEGITER_REVERSE ){
      if( pIter->iRowidOffset>0 ){
        u8 *a = pIter->pLeaf->p;
        int iOff;
        int nPos;
        i64 iDelta;
        pIter->iRowidOffset--;

        pIter->iLeafOffset = iOff = pIter->aRowidOffset[pIter->iRowidOffset];
        iOff += getVarint32(&a[iOff], nPos);
        iOff += nPos;
        getVarint(&a[iOff], (u64*)&iDelta);
        pIter->iRowid += iDelta;
      }else{
        fts5DataRelease(pIter->pLeaf);
        pIter->pLeaf = 0;
        while( p->rc==SQLITE_OK && pIter->iLeafPgno>pIter->iTermLeafPgno ){
          Fts5Data *pNew;
          pIter->iLeafPgno--;
          pNew = fts5DataRead(p, FTS5_SEGMENT_ROWID(
                pIter->iIdx, pIter->pSeg->iSegid, 0, pIter->iLeafPgno
          ));
          if( pNew ){
            if( pIter->iLeafPgno==pIter->iTermLeafPgno ){
              if( pIter->iTermLeafOffset<pNew->n ){
                pIter->pLeaf = pNew;
                pIter->iLeafOffset = pIter->iTermLeafOffset;
              }
            }else{
              int iRowidOff, dummy;
              fts5LeafHeader(pNew, &iRowidOff, &dummy);
              if( iRowidOff ){
                pIter->pLeaf = pNew;
                pIter->iLeafOffset = iRowidOff;
              }
            }

            if( pIter->pLeaf ){
              u8 *a = &pIter->pLeaf->p[pIter->iLeafOffset];
              pIter->iLeafOffset += getVarint(a, (u64*)&pIter->iRowid);
              break;
            }else{
              fts5DataRelease(pNew);
            }
          }
        }

        if( pIter->pLeaf ){
          fts5SegIterReverseInitPage(p, pIter);
        }
      }
    }else{
      Fts5Data *pLeaf = pIter->pLeaf;
      int iOff;
      int bNewTerm = 0;
      int nKeep = 0;

      /* Search for the end of the position list within the current page. */
      u8 *a = pLeaf->p;
      int n = pLeaf->n;

      iOff = pIter->iLeafOffset;
      if( iOff<n ){
        int nPoslist;
        iOff += getVarint32(&a[iOff], nPoslist);
        iOff += nPoslist;
      }

      if( iOff<n ){
        /* The next entry is on the current page */
        u64 iDelta;
        iOff += sqlite3GetVarint(&a[iOff], &iDelta);
        pIter->iLeafOffset = iOff;
        if( iDelta==0 ){
          bNewTerm = 1;
          if( iOff>=n ){
            fts5SegIterNextPage(p, pIter);
            pIter->iLeafOffset = 4;
          }else if( iOff!=fts5GetU16(&a[2]) ){
            pIter->iLeafOffset += getVarint32(&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;
          if( pLeaf==0 ) break;
          if( (iOff = fts5GetU16(&pLeaf->p[0])) ){
            iOff += sqlite3GetVarint(&pLeaf->p[iOff], (u64*)&pIter->iRowid);
            pIter->iLeafOffset = iOff;
          }
          else if( (iOff = fts5GetU16(&pLeaf->p[2])) ){
            pIter->iLeafOffset = iOff;
            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);
        }
      }
    }
  }
}

/*
** Iterator pIter currently points to the first rowid in a doclist. This
** function sets the iterator up so that iterates in reverse order through
** the doclist.
*/
static void fts5SegIterReverse(Fts5Index *p, int iIdx, Fts5SegIter *pIter){
  Fts5Data *pLeaf;                /* Current leaf data */
  int iOff = pIter->iLeafOffset;  /* Byte offset within current leaf */
  Fts5Data *pLast = 0;
  int pgnoLast = 0;

  /* Move to the page that contains the last rowid in this doclist. */
  pLeaf = pIter->pLeaf;

  while( iOff<pLeaf->n ){
    int nPos;
    i64 iDelta;

    /* Position list size in bytes */
    iOff += getVarint32(&pLeaf->p[iOff], nPos);
    iOff += nPos;
    if( iOff>=pLeaf->n ) break;

    /* Rowid delta. Or, if 0x00, the end of doclist marker. */
    nPos = getVarint(&pLeaf->p[iOff], (u64*)&iDelta);
    if( iDelta==0 ) break;
    iOff += nPos;
  }

  if( iOff>=pLeaf->n ){
    Fts5StructureSegment *pSeg = pIter->pSeg;
    i64 iAbs = FTS5_SEGMENT_ROWID(iIdx, pSeg->iSegid, 0, pIter->iLeafPgno);
    i64 iLast = FTS5_SEGMENT_ROWID(iIdx, pSeg->iSegid, 0, pSeg->pgnoLast);

    /* The last rowid in the doclist may not be on the current page. Search
    ** forward to find the page containing the last rowid.  */
    for(iAbs++; p->rc==SQLITE_OK && iAbs<=iLast; iAbs++){
      Fts5Data *pNew = fts5DataRead(p, iAbs);
      if( pNew ){
        int iRowid, iTerm;
        fts5LeafHeader(pNew, &iRowid, &iTerm);
        if( iRowid ){
          Fts5Data *pTmp = pLast;
          pLast = pNew;
          pNew = pTmp;
          pgnoLast = iAbs & (((i64)1 << FTS5_DATA_PAGE_B) - 1);
        }
        if( iTerm ){
          iAbs = iLast;
        }
        fts5DataRelease(pNew);
      }
    }
  }

  /* If pLast is NULL at this point, then the last rowid for this doclist
  ** lies on the page currently indicated by the iterator. In this case 
  ** iLastOff is set to the value that pIter->iLeafOffset will take when
  ** the iterator points to that rowid.
  **
  ** Or, if pLast is non-NULL, then it is the page that contains the last
  ** rowid.
  */
  if( pLast ){
    int dummy;
    fts5DataRelease(pIter->pLeaf);
    pIter->pLeaf = pLast;
    pIter->iLeafPgno = pgnoLast;
    fts5LeafHeader(pLast, &iOff, &dummy);
    iOff += getVarint(&pLast->p[iOff], (u64*)&pIter->iRowid);
    pIter->iLeafOffset = iOff;
  }

  fts5SegIterReverseInitPage(p, pIter);
  pIter->flags |= FTS5_SEGITER_REVERSE;
}

/*
** 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 flags,                      /* Mask of FTS5INDEX_XXX flags */
  Fts5StructureSegment *pSeg,     /* Description of segment */
  Fts5SegIter *pIter              /* Object to populate */
){
  int iPg = 1;
  int h;
  int bGe = ((flags & FTS5INDEX_QUERY_PREFIX) && iIdx==0);

  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. */

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

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

/*
** Zero the iterator passed as the only argument.
*/
static void fts5SegIterClear(Fts5SegIter *pIter){
  fts5BufferFree(&pIter->term);
  fts5DataRelease(pIter->pLeaf);
  sqlite3_free(pIter->aRowidOffset);
  memset(pIter, 0, sizeof(Fts5SegIter));
}

/*
** Do the comparison necessary to populate pIter->aFirst[iOut].
**
** If the returned value is non-zero, then it is the index of an entry
** in the pIter->aSeg[] array that is (a) not at EOF, and (b) pointing
** to a key that is a duplicate of another, higher priority, 
** segment-iterator in the pSeg->aSeg[] array.
*/
static int fts5MultiIterDoCompare(Fts5MultiSegIter *pIter, int iOut){
  int i1;                         /* Index of left-hand Fts5SegIter */
  int i2;                         /* Index of right-hand Fts5SegIter */
  int iRes;
  Fts5SegIter *p1;                /* Left-hand Fts5SegIter */
  Fts5SegIter *p2;                /* Right-hand Fts5SegIter */

  assert( iOut<pIter->nSeg && iOut>0 );
  assert( pIter->bRev==0 || pIter->bRev==1 );

  if( iOut>=(pIter->nSeg/2) ){
    i1 = (iOut - pIter->nSeg/2) * 2;
    i2 = i1 + 1;
  }else{
    i1 = pIter->aFirst[iOut*2];
    i2 = pIter->aFirst[iOut*2+1];

    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;
    }

** 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 flags,                      /* 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 */

      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));

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

}

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 += 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, 
  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;
}

/*
** 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 */
  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;


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

  if( aBuf && pStruct ){
    Fts5DoclistIter *pDoclist;
    int i;

    ){
      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; doclist.n && p->rc==SQLITE_OK; 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);
}

    memset(pRet, 0, sizeof(Fts5IndexIter));

    pRet->pIndex = p;
    if( iIdx>=0 ){
      pRet->pStruct = fts5StructureRead(p, iIdx);
      if( pRet->pStruct ){
        fts5MultiIterNew(p, pRet->pStruct, 
            iIdx, 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;
  }

  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);
    assert( p->rc==SQLITE_OK );
    if( p->rc ) return 0;
    *pn = pIter->poslist.n;
    return pIter->poslist.p;
  }
}

/*

foreach {tn expr res} {
  1 {abash} {9 5 3 1}
  2 {abase} {9 4 3 1}
  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}

foreach {tn expr res} {
  1 {abash} {1 3 5 9}
  2 {abase} {1 3 4 9}
  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
}


finish_test

      break
    }
  }

  return $bMatch
}

proc matchdata {expr {bAsc 0}} {
  set tclexpr [db one {SELECT fts5_expr_tcl($expr, 'nearset $cols', 'x', 'y')}]
  set res [list]
  foreach {id x y} $::data {
    set cols [list $x $y]
    if $tclexpr {
      lappend res $id
    }
  }

  # puts $tclexpr

  if {$bAsc} {
    set res [lsort -integer -increasing $res]
  } else {
    set res [lsort -integer -decreasing $res]
  }

  return $res
}

foreach {tn phrase} {
  1 "o"
  2 "b q"
  3 "e a e"

  1 {a b} {[N $x -- {a}] && [N $x -- {b}]}
} {
  do_execsql_test 3.$tn {SELECT fts5_expr_tcl($expr, 'N $x')} [list $tclexpr]
}

#-------------------------------------------------------------------------
#
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) }
    5 { NEAR(r c, 0) }
    6 { NEAR(a b c) }
    7 { NEAR(a b c, 8) }
    8  { x : NEAR(r c) }
    9  { y : NEAR(r c) }
    10 { x : "r c" }
    11 { y : "r c" }
    12 { a AND b }
    13 { a AND b AND c }
    14a { a }
    14b { a OR b }
    15 { a OR b AND c }
    16 { c AND b OR a }
    17 { c AND (b OR a) }
    18 { c NOT (b OR a) }
    19 { c NOT b OR a AND d }
  } {
    set res [matchdata $expr $bAsc]
    do_execsql_test 4.$bAsc.$tn.[llength $res] $sql $res


  }
}



finish_test

  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) VALUES('pgsz=32');
  }
  

      if {[lsearch -glob $a $prefix]>=0 || [lsearch -glob $b $prefix]>=0} {
        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*}
      27 {x*}
    } {
      set res [prefix_query $prefix]
      if {$bAsc} {
        set res [lsort -integer -increasing $res]
      }
      set n [llength $res]
      do_execsql_test $T.$bAsc.$tn.$n $sql $res
    }
  }
}

finish_test

  fts3varint.test
  fts4growth.test fts4growth2.test
}

test_suite "fts5" -prefix "" -description {
  All FTS5 tests.
} -files {
  fts5aa.test fts5ab.test fts5ac.test fts5ad.test fts5ea.test
}

test_suite "nofaultsim" -prefix "" -description {
  "Very" quick test suite. Runs in less than 5 minutes on a workstation. 
  This test suite is the same as the "quick" tests, except that some files
  that test malloc and IO errors are omitted.
} -files [