/*
** A phrase. One or more terms that must appear in a contiguous sequence
** within a document for it to match.
*/
struct Fts5ExprPhrase {
  Fts5Buffer poslist;             /* Current position list */
  i64 iRowid;                     /* Current rowid */
  int nTerm;                      /* Number of entries in aTerm[] */
  Fts5ExprTerm aTerm[0];          /* Terms that make up this phrase */
};

/*
** One or more phrases that must appear within a certain token distance of
** each other within each matching document.
................................................................................
  int i;                          /* Current offset in a[] */

  /* Output variables */
  int bEof;                       /* Set to true at EOF */
  i64 iPos;                       /* (iCol<<32) + iPos */
};

static void fts5PoslistIterNext(Fts5PoslistIter *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);
      pIter->iPos = ((u64)iVal << 32);
      pIter->i += getVarint32(&pIter->a[pIter->i], iVal);
    }
    pIter->iPos += (iVal-2);
  }

}

static void fts5PoslistIterInit(const u8 *a, int n, Fts5PoslistIter *pIter){
  memset(pIter, 0, sizeof(*pIter));
  pIter->a = a;
  pIter->n = n;
  fts5PoslistIterNext(pIter);
}


























/*
*************************************************************************/

void sqlite3Fts5ParseError(Fts5Parse *pParse, const char *zFmt, ...){
  if( pParse->rc==SQLITE_OK ){
    va_list ap;
    va_start(ap, zFmt);
................................................................................
** not a match.
*/
static int fts5ExprPhraseIsMatch(
  Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
  Fts5ExprPhrase *pPhrase,        /* Phrase object to initialize */
  int *pbMatch                    /* OUT: Set to true if really a match */
){

  Fts5PoslistIter aStatic[4];
  Fts5PoslistIter *aIter = aStatic;
  int i;
  int rc = SQLITE_OK;



  if( pPhrase->nTerm>(sizeof(aStatic) / sizeof(aStatic[0])) ){
    int nByte = sizeof(Fts5PoslistIter) * pPhrase->nTerm;
    aIter = (Fts5PoslistIter*)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);
    fts5PoslistIterInit(a, n, &aIter[i]);
  }

  *pbMatch = 0;
  while( 1 ){

    int bMatch = 1;
    i64 iPos = aIter[0].iPos;


    for(i=1; i<pPhrase->nTerm; i++){
      Fts5PoslistIter *pPos = &aIter[i];
      i64 iAdj = pPos->iPos-i;
      if( (pPos->iPos-i)!=iPos ){
        bMatch = 0;
        if( iAdj>iPos ) iPos = iAdj;


      }

    }

    if( bMatch ){
      *pbMatch = 1;
      break;
    }




    for(i=0; i<pPhrase->nTerm; i++){





































      Fts5PoslistIter *pPos = &aIter[i];
      while( (pPos->iPos-i) < iPos ){




        fts5PoslistIterNext(pPos);
        if( pPos->bEof ) goto ismatch_out;
      }

    }
  }


 ismatch_out:

  if( aIter!=aStatic ) sqlite3_free(aIter);
  return rc;
}

/*


























































** All individual term iterators in pPhrase are guaranteed to be valid when
** this function is called. This function checks if all term iterators
** point to the same rowid, and if not, advances them until they do.
** If an EOF is reached before this happens, *pbEof is set to true before
** returning.
**
** SQLITE_OK is returned if an error occurs, or an SQLite error code 
** otherwise. It is not considered an error code if an iterator reaches
** EOF.
*/
static int fts5ExprPhraseNextRowidMatch(
  Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
  Fts5ExprPhrase *pPhrase,        /* Phrase object to initialize */
  int *pbEof                      /* OUT: Set to true if phrase at EOF */
){

  assert( *pbEof==0 );
  while( 1 ){
    int i;
    int bMatch = 1;
    i64 iMin = sqlite3Fts5IterRowid(pPhrase->aTerm[0].pIter);
    for(i=1; i<pPhrase->nTerm; i++){
      i64 iRowid = sqlite3Fts5IterRowid(pPhrase->aTerm[i].pIter);
      if( iRowid!=iMin ){
        bMatch = 0;
        if( iRowid<iMin ) iMin = iRowid;
      }
    }


    if( bMatch ) break;



    for(i=0; i<pPhrase->nTerm; i++){
      Fts5IndexIter *pIter = pPhrase->aTerm[i].pIter;
      while( sqlite3Fts5IterRowid(pIter)>iMin ){
        sqlite3Fts5IterNext(pIter, 0);
        if( sqlite3Fts5IterEof(pIter) ){
          *pbEof = 1;
          return SQLITE_OK;


        }
      }

    }
  }

  return SQLITE_OK;
}

static int fts5ExprPhraseAdvanceAll(
  Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
  Fts5ExprPhrase *pPhrase,        /* Phrase object to initialize */
  int *pbEof                      /* OUT: Set to true if phrase at EOF */
){
  int i;
  int rc = SQLITE_OK;
  for(i=0; i<pPhrase->nTerm; i++){
    Fts5IndexIter *pIter = pPhrase->aTerm[i].pIter;
    sqlite3Fts5IterNext(pIter, 0);
    if( sqlite3Fts5IterEof(pIter) ){
      *pbEof = 1;
      break;
    }
  }

  return rc;
}

/*
** Argument pPhrase points to a multi-term phrase object. All individual
** term iterators point to valid entries (not EOF).
*
** This function tests if the term iterators currently all point to the
** same rowid, and if so, if the rowid matches the phrase constraint. If
** so, the pPhrase->poslist buffer is populated and the pPhrase->iRowid
** variable set before returning. Or, if the current combination of 
** iterators is not a match, they are advanced until they are. If one of
** the iterators reaches EOF before a match is found, *pbEof is set to
** true before returning. The final values of the pPhrase->poslist and 
** iRowid fields are undefined in this case.
**
** SQLITE_OK is returned if an error occurs, or an SQLite error code 
** otherwise. It is not considered an error code if an iterator reaches
** EOF.
*/
static int fts5ExprPhraseNextMatch(
  Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
  Fts5ExprPhrase *pPhrase,        /* Phrase object to initialize */
  int *pbEof                      /* OUT: Set to true if phrase at EOF */
){
  int i;                          /* Used to iterate through terms */
  int rc = SQLITE_OK;             /* Return code */
  int bMatch = 0;

  assert( *pbEof==0 );

  while( 1 ){
    rc = fts5ExprPhraseNextRowidMatch(pExpr, pPhrase, pbEof);
    if( rc!=SQLITE_OK || *pbEof ) break;

    /* At this point, all term iterators are valid and point to the same rowid.
    ** The following assert() statements verify this.  */
#ifdef SQLITE_DEBUG
    for(i=0; i<pPhrase->nTerm; i++){
      Fts5IndexIter *pIter = pPhrase->aTerm[i].pIter;
      Fts5IndexIter *pOne = pPhrase->aTerm[0].pIter;
      assert( 0==sqlite3Fts5IterEof(pIter) );
      assert( sqlite3Fts5IterRowid(pOne)==sqlite3Fts5IterRowid(pIter) );
    }
#endif

    rc = fts5ExprPhraseIsMatch(pExpr, pPhrase, &bMatch);
    if( rc!=SQLITE_OK || bMatch ) break;
    rc = fts5ExprPhraseAdvanceAll(pExpr, pPhrase, pbEof);
    if( rc!=SQLITE_OK || *pbEof ) break;
  }

  pPhrase->iRowid = sqlite3Fts5IterRowid(pPhrase->aTerm[0].pIter);
  return rc;
}

/*
** Advance the phrase iterator pPhrase to the next match.
*/
static int fts5ExprPhraseNext(
  Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
  Fts5ExprPhrase *pPhrase,        /* Phrase object to initialize */
  int *pbEof                      /* OUT: Set to true if phrase at EOF */
){
  int i;
  for(i=0; i<pPhrase->nTerm; i++){
    Fts5IndexIter *pIter = pPhrase->aTerm[i].pIter;
    sqlite3Fts5IterNext(pIter, 0);
    if( sqlite3Fts5IterEof(pIter) ){
      *pbEof = 1;
      return SQLITE_OK;
    }
  }

  if( pPhrase->nTerm==1 ){
    pPhrase->iRowid = sqlite3Fts5IterRowid(pPhrase->aTerm[0].pIter);
  }else{
    fts5ExprPhraseNextMatch(pExpr, pPhrase, pbEof);
  }













  return SQLITE_OK;
}

/*
** Point phrase object pPhrase at the first matching document. Or, if there 
** are no matching documents at all, move pPhrase to EOF and set *pbEof to
** true before returning.
**
** If no error occurs, SQLITE_OK is returned. Otherwise, an SQLite error
** code.
*/
static int fts5ExprPhraseFirst(
  Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
  Fts5ExprPhrase *pPhrase,        /* Phrase object to initialize */
  int *pbEof                      /* OUT: Set to true if phrase at EOF */

){
  int i;                          /* Used to iterate through terms */
  int rc = SQLITE_OK;




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

  if( pPhrase->nTerm==1 ){
    const u8 *a; int n;
    Fts5IndexIter *pIter = pPhrase->aTerm[0].pIter;
    pPhrase->iRowid = sqlite3Fts5IterRowid(pIter);
    a = sqlite3Fts5IterPoslist(pIter, &n);
    if( a ){
      sqlite3Fts5BufferSet(&rc, &pPhrase->poslist, n, a);
    }
  }else{
    rc = fts5ExprPhraseNextMatch(pExpr, pPhrase, pbEof);
  }

  return rc;
}
 
static int fts5ExprNodeFirst(Fts5Expr *pExpr, Fts5ExprNode *pNode){
  int rc = SQLITE_OK;

  pNode->bEof = 0;
  if( pNode->eType==FTS5_STRING ){
    Fts5ExprPhrase *pPhrase = pNode->pNear->apPhrase[0];
    assert( pNode->pNear->nPhrase==1 );
    assert( pNode->bEof==0 );
    rc = fts5ExprPhraseFirst(pExpr, pPhrase, &pNode->bEof);
    pNode->iRowid = pPhrase->iRowid;




  }else{
    rc = fts5ExprNodeFirst(pExpr, pNode->pLeft);
    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeFirst(pExpr, pNode->pRight);
    }
    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeTest(pExpr, pNode);
................................................................................
  return rc;
}

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

  if( pNode->eType==FTS5_STRING ){
    Fts5ExprPhrase *pPhrase = pNode->pNear->apPhrase[0];
    assert( pNode->pNear->nPhrase==1 );
    rc = fts5ExprPhraseNext(pExpr, pPhrase, &pNode->bEof);
    pNode->iRowid = pPhrase->iRowid;
  }else{
    assert( 0 );
  }
  return rc;
}


................................................................................
    sCtx.pPhrase->aTerm[sCtx.pPhrase->nTerm-1].bPrefix = bPrefix;
  }

  sqlite3_free(z);
  return sCtx.pPhrase;
}






void sqlite3Fts5ParseNear(Fts5Parse *pParse, Fts5Token *pTok){
  if( pParse->rc==SQLITE_OK ){
    if( pTok->n!=4 || memcmp("NEAR", pTok->p, 4) ){
      sqlite3Fts5ParseError(
          pParse, "fts5: syntax error near \"%.*s\"", pTok->n, pTok->p
      );
    }

/*
** A phrase. One or more terms that must appear in a contiguous sequence
** within a document for it to match.
*/
struct Fts5ExprPhrase {
  Fts5Buffer poslist;             /* Current position list */

  int nTerm;                      /* Number of entries in aTerm[] */
  Fts5ExprTerm aTerm[0];          /* Terms that make up this phrase */
};

/*
** One or more phrases that must appear within a certain token distance of
** each other within each matching document.
................................................................................
  int i;                          /* Current offset in a[] */

  /* Output variables */
  int bEof;                       /* Set to true at EOF */
  i64 iPos;                       /* (iCol<<32) + iPos */
};

static int fts5PoslistIterNext(Fts5PoslistIter *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);
      pIter->iPos = ((u64)iVal << 32);
      pIter->i += getVarint32(&pIter->a[pIter->i], iVal);
    }
    pIter->iPos += (iVal-2);
  }
  return pIter->bEof;
}

static void fts5PoslistIterInit(const u8 *a, int n, Fts5PoslistIter *pIter){
  memset(pIter, 0, sizeof(*pIter));
  pIter->a = a;
  pIter->n = n;
  fts5PoslistIterNext(pIter);
}

typedef struct Fts5PoslistWriter Fts5PoslistWriter;
struct Fts5PoslistWriter {
  int iCol;
  int iOff;
};

static int fts5PoslistWriterAppend(
  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;
}
/*
*************************************************************************/

void sqlite3Fts5ParseError(Fts5Parse *pParse, const char *zFmt, ...){
  if( pParse->rc==SQLITE_OK ){
    va_list ap;
    va_start(ap, zFmt);
................................................................................
** not a match.
*/
static int fts5ExprPhraseIsMatch(
  Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
  Fts5ExprPhrase *pPhrase,        /* Phrase object to initialize */
  int *pbMatch                    /* OUT: Set to true if really a match */
){
  Fts5PoslistWriter writer = {0, 0};
  Fts5PoslistIter aStatic[4];
  Fts5PoslistIter *aIter = aStatic;
  int i;
  int rc = SQLITE_OK;

  /* 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(Fts5PoslistIter) * pPhrase->nTerm;
    aIter = (Fts5PoslistIter*)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);
    fts5PoslistIterInit(a, n, &aIter[i]);
  }

  fts5BufferZero(&pPhrase->poslist);
  while( 1 ){

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

          while( pPos->iPos<iAdj ){
            if( fts5PoslistIterNext(pPos) ) goto ismatch_out;
          }
          if( pPos->iPos>iAdj ) iPos = pPos->iPos-i;
        }
      }
    }while( bMatch==0 );



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

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

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


static int fts5ExprNearIsMatch(Fts5ExprNearset *pNear, int *pbMatch){
  Fts5PoslistIter aStatic[4];
  Fts5PoslistIter *aIter = aStatic;
  int i;
  int rc = SQLITE_OK;
  int bMatch;
  i64 iMax;

  /* 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(Fts5PoslistIter) * pNear->nPhrase;
    aIter = (Fts5PoslistIter*)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; 
    fts5PoslistIterInit(pPoslist->p, pPoslist->n, &aIter[i]);
  }

  iMax = aIter[0].iPos;
  do {
    bMatch = 1;
    for(i=0; i<pNear->nPhrase; i++){
      Fts5PoslistIter *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( fts5PoslistIterNext(pPos) ) goto ismatch_out;

        }
        if( pPos->iPos>iMax ) iMax = pPos->iPos;
      }
    }
  }while( bMatch==0 );

 ismatch_out:
  *pbMatch = bMatch;
  if( aIter!=aStatic ) sqlite3_free(aIter);
  return rc;
}

/*
** Advance each phrase iterator in phrase pNear. If any reach EOF, set
** output variable *pbEof to true before returning.
*/
static int fts5ExprNearAdvanceAll(
  Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
  Fts5ExprNearset *pNear,         /* Near object to advance iterators of */
  int *pbEof                      /* OUT: Set to true if phrase at EOF */
){
  int rc = SQLITE_OK;             /* Return code */
  int i, j;                       /* Phrase and token index, respectively */

  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;
      sqlite3Fts5IterNext(pIter, 0);
      if( sqlite3Fts5IterEof(pIter) ){
        *pbEof = 1;
        return rc;
      }
    }
  }

  return rc;
}

/*
** 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 */
  i64 *piMin,                     /* IN/OUT: Minimum rowid seen so far */
  int *pRc,                       /* OUT: Error code */
  int *pbEof                      /* OUT: Set to true if EOF */
){
  i64 iMin = *piMin;
  i64 iRowid;
  while( (iRowid = sqlite3Fts5IterRowid(pIter))>iMin ){
    sqlite3Fts5IterNext(pIter, 0);
    if( sqlite3Fts5IterEof(pIter) ){
      *pbEof = 1;
      return 1;
    }
  }
  if( iRowid<iMin ){
    *piMin = iRowid;
  }

  return 0;
}

/*
** All individual term iterators in pNear are guaranteed to be valid when
** this function is called. This function checks if all term iterators
** point to the same rowid, and if not, advances them until they do.
** If an EOF is reached before this happens, *pbEof is set to true before
** returning.
**
** SQLITE_OK is returned if an error occurs, or an SQLite error code 
** otherwise. It is not considered an error code if an iterator reaches
** EOF.
*/
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 iMin;                       /* Smallest rowid any iterator points to */
  int bMatch;








  iMin = 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!=iMin ) bMatch = 0;
        if( fts5ExprAdvanceto(pIter, &iMin, &rc, &pNode->bEof) ) return rc;
      }
    }
  }while( bMatch==0 );





















  pNode->iRowid = iMin;
  return rc;
}

/*
** Argument pNode points to a NEAR node. All individual term iterators 
** point to valid entries (not EOF).
*
** This function tests if the term iterators currently all point to the
** same rowid, and if so, if the row matches the phrase and NEAR constraints. 
** If so, the pPhrase->poslist buffers are populated and the pNode->iRowid
** variable set before returning. Or, if the current combination of 
** iterators is not a match, they are advanced until they are. If one of
** the iterators reaches EOF before a match is found, *pbEof is set to
** true before returning. The final values of the pPhrase->poslist and 
** iRowid fields are undefined in this case.
**
** SQLITE_OK is returned if an error occurs, or an SQLite error code 
** otherwise. It is not considered an error code if an iterator reaches
** EOF.
*/
static int fts5ExprNearNextMatch(
  Fts5Expr *pExpr,                /* Expression that pNear is a part of */
  Fts5ExprNode *pNode
){
  int rc = SQLITE_OK;
  Fts5ExprNearset *pNear = pNode->pNear;
  while( 1 ){
    int i;

    /* Advance the iterators until they are a match */
    rc = fts5ExprNearNextRowidMatch(pExpr, pNode);
    if( pNode->bEof || rc!=SQLITE_OK ) break;

    for(i=0; i<pNear->nPhrase; i++){
      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
      if( pPhrase->nTerm>1 ){
        int bMatch = 0;
        rc = fts5ExprPhraseIsMatch(pExpr, pPhrase, &bMatch);
        if( rc!=SQLITE_OK ) return rc;
        if( bMatch==0 ) break;
      }else{
        int n;
        u8 *a = sqlite3Fts5IterPoslist(pPhrase->aTerm[0].pIter, &n);
        fts5BufferSet(&rc, &pPhrase->poslist, n, a);
      }
    }

    if( i==pNear->nPhrase ){
      int bMatch = 1;
      if( pNear->nPhrase>1 ){
        rc = fts5ExprNearIsMatch(pNear, &bMatch);
      }
      if( rc!=SQLITE_OK || bMatch ) break;
    }

    rc = fts5ExprNearAdvanceAll(pExpr, pNear, &pNode->bEof);
    if( pNode->bEof || rc!=SQLITE_OK ) break;
  }

  return rc;
}

/*
** Initialize all term iterators in the pNear object. If any term is found
** to match no documents at all, set *pbEof to true and return immediately,
** without initializing any further iterators.
*/
static int fts5ExprNearInitAll(
  Fts5Expr *pExpr,
  Fts5ExprNode *pNode
){
  Fts5ExprNearset *pNear = pNode->pNear;
  Fts5ExprTerm *pTerm;
  Fts5ExprPhrase *pPhrase;
  int i, j;

  for(i=0; i<pNear->nPhrase; i++){
    pPhrase = pNear->apPhrase[i];
    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( sqlite3Fts5IterEof(pTerm->pIter) ){
        pNode->bEof = 1;
        return SQLITE_OK;
      }
    }
  }

  return SQLITE_OK;
}









static int fts5ExprNearNext(
  Fts5Expr *pExpr,                /* Expression that pNear is a part of */


  Fts5ExprNode *pNode
){


  int rc = fts5ExprNearAdvanceAll(pExpr, pNode->pNear, &pNode->bEof);
  if( rc==SQLITE_OK && pNode->bEof==0 ){
    rc = fts5ExprNearNextMatch(pExpr, pNode);
  }

























  return rc;
}
 
static int fts5ExprNodeFirst(Fts5Expr *pExpr, Fts5ExprNode *pNode){
  int rc = SQLITE_OK;
  pNode->bEof = 0;

  if( pNode->eType==FTS5_STRING ){

    /* Initialize all term iterators in the NEAR object. */
    rc = fts5ExprNearInitAll(pExpr, pNode);

    /* Attempt to advance to the first match */
    if( rc==SQLITE_OK && pNode->bEof==0 ){
      rc = fts5ExprNearNextMatch(pExpr, pNode);
    }

  }else{
    rc = fts5ExprNodeFirst(pExpr, pNode->pLeft);
    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeFirst(pExpr, pNode->pRight);
    }
    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeTest(pExpr, pNode);
................................................................................
  return rc;
}

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

  if( pNode->eType==FTS5_STRING ){
    rc = fts5ExprNearNext(pExpr, pNode);



  }else{
    assert( 0 );
  }
  return rc;
}


................................................................................
    sCtx.pPhrase->aTerm[sCtx.pPhrase->nTerm-1].bPrefix = bPrefix;
  }

  sqlite3_free(z);
  return sCtx.pPhrase;
}

/*
** Token pTok has appeared in a MATCH expression where the NEAR operator
** is expected. If token pTok does not contain "NEAR", store an error
** in the pParse object.
*/
void sqlite3Fts5ParseNear(Fts5Parse *pParse, Fts5Token *pTok){
  if( pParse->rc==SQLITE_OK ){
    if( pTok->n!=4 || memcmp("NEAR", pTok->p, 4) ){
      sqlite3Fts5ParseError(
          pParse, "fts5: syntax error near \"%.*s\"", pTok->n, pTok->p
      );
    }

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

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

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

#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 2.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(a,b);
  INSERT INTO t1(t1) VALUES('pgsz=32');
}

foreach {tn a b} {
   1 {abashed abandons abase abash abaft} {abases abased}
   2 {abasing abases abaft abated abandons} {abases abandoned}
................................................................................
   5 {abaft abashing abatement abash abasements} {abandons abandoning}
   6 {aback abate abasements abashes abandoned} {abasement abased}
   7 {abandons abated abased aback abandoning} {abases abandoned}
   8 {abashing abases abasement abaft abashing} {abashed abate}
   9 {abash abase abate abashing abashed} {abandon abandoned}
   10 {abate abandoning abandons abasement aback} {abandon abandoning}
} {
  do_execsql_test 2.1.$tn.1 { INSERT INTO t1 VALUES($a, $b) } 
  do_execsql_test 2.1.$tn.2 { INSERT INTO t1(t1) VALUES('integrity-check') }
}

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 2.2.$tn {
    SELECT rowid FROM t1 WHERE t1 MATCH $expr
  } $res
}







finish_test

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

foreach {tn a b} {
   1 {abashed abandons abase abash abaft} {abases abased}
   2 {abasing abases abaft abated abandons} {abases abandoned}
................................................................................
   5 {abaft abashing abatement abash abasements} {abandons abandoning}
   6 {aback abate abasements abashes abandoned} {abasement abased}
   7 {abandons abated abased aback abandoning} {abases abandoned}
   8 {abashing abases abasement abaft abashing} {abashed abate}
   9 {abash abase abate abashing abashed} {abandon abandoned}
   10 {abate abandoning abandons abasement aback} {abandon abandoning}
} {
  do_execsql_test 3.1.$tn.1 { INSERT INTO t1 VALUES($a, $b) } 
  do_execsql_test 3.1.$tn.2 { INSERT INTO t1(t1) VALUES('integrity-check') }
}

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
}

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


finish_test

# 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 fts5ac

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

do_execsql_test 1.0 {
  CREATE VIRTUAL TABLE xx USING fts5(x,y);
  INSERT INTO xx(xx) VALUES('pgsz=32');
}

set data {
    0   {p o q e z k z p n f y u z y n y}   {l o o l v v k}
    1   {p k h h p y l l h i p v n}         {p p l u r i f a j g e r r x w}
    2   {l s z j k i m p s}                 {l w e j t j e e i t w r o p o}
    3   {x g y m y m h p}                   {k j j b r e y y a k y}
    4   {q m a i y i z}                     {o w a g k x g j m w e u k}
    5   {k o a w y b s z}                   {s g l m m l m g p}
    6   {d a q i z h b l c p k j g k}       {p x u j x t v c z}
    7   {f d a g o c t i}                   {w f c x l d r k i j}
    8   {y g w u b q p o m j y b p a e k}   {r i d k y w o z q m a t p}
    9   {r k o m c c j s x m x m x m q r}   {y r c a q d z k n x n}
    10  {k j q m g q a j d}                 {d d e z g w h c d o o g x d}
    11  {j z u m o y q j f w e e w t r j w} {g m o r x n t n w i f g l z f}
    12  {s y w a w d o h x m k}             {c w k z b p o r a}
    13  {u t h x e g s k n g i}             {f j w g c s r}
    14  {b f i c s u z t k}                 {c k q s j u i z o}
    15  {n a f n u s w h y n s i q e w}     {x g e g a s s h n}
    16  {k s q e j n p}                     {t r j f t o e k k l m i}
    17  {g d t u w r o p m n m n p h b o u} {h s w o s l j e}
    18  {f l q y q q g e e x j r}           {n b r r g e i r t x q k}
    19  {f i r g o a w e p i l o a w}       {e k r z t d g h g i b d i e m}
    20  {l d u u f p y}                     {g o m m u x m g l j t t x x u}
    21  {m c d k x i c z l}                 {m i a i e u h}
    22  {w b f o c g x y j}                 {z d w x d f h i p}
    23  {w u i u x t c h k i b}             {b y k h b v r t g j}
    24  {h f d j s w s b a p k}             {a q y u z e y m m j q r}
    25  {d i x y x x k i y f s d j h z p n} {l l q m e t c w g y h t s v g}
    26  {g s q w t d k x g f m j p k y}     {r m b x e l t d}
    27  {j l s q u g y v e c l o}           {m f l m m m h g x x l n c}
    28  {c t j g v r s b z j}               {l c f y d t q n}
    29  {e x z y w i h l}                   {b n b x e y q e n u m}
    30  {g y y h j b w r}                   {q b q f u s k c k g r}
    31  {g u l x l b r c m z b u c}         {k g t b x k x n t e z d h o}
    32  {w g v l z f b z h p s c v h}       {g e w v m h k r g w a r f q}
    33  {c g n f u d o y o b}               {e y o h x x y y i z s b h a j}
    34  {v y h c q u u s q y x x k s q}     {d n r m y k n t i r n w e}
    35  {o u c x l e b t a}                 {y b a x y f z x r}
    36  {x p h l j a a u u j h}             {x o f s z m b c q p}
    37  {k q t i c a q n m v v}             {v r z e f m y o}
    38  {r w t t t t r v v o e p g h}       {l w x a g a u h y}
    39  {o p v g v b a g o}                 {j t q c r b b g y z}
    40  {f s o r o d t h q f x l}           {r d b m k i f s t d l m y x j w}
    41  {t m o t m f m f}                   {i p i q j v n v m b q}
    42  {t x w a r l w d t b c o d o}       {a h f h w z d n s}
    43  {t u q c d g p q x j o l c x c}     {m n t o z z j a y}
    44  {v d i i k b f s z r v r z y}       {g n q y s x x m b x c l w}
    45  {p v v a c s z y e o l}             {m v t u d k m k q b d c v z r}
    46  {f y k l d r q w r s t r e}         {h m v r r l r r t f q e x y}
    47  {w l n l t y x}                     {n h s l a f c h u f l x x m v n o}
    48  {t n v i k e b p z p d j j l i o}   {i v z p g u e j s i k n h w d c}
    49  {z v x p n l t a j c}               {e j l e n c e t a d}
    50  {w u b x u i v h a i y m m r p m s} {s r h d o g z y f f x e}
    51  {d c c x b c a x g}                 {p r a j v u y}
    52  {f w g r c o d l t u e z h i}       {j l l s s b j m}
    53  {p m t f k i x}                     {u v y a z g w v v m x h i}
    54  {l c z g l o j i c d e b}           {b f v y w u i b e i y}
    55  {r h c x f x a d s}                 {z x y k f l r b q c v}
    56  {v x x c y h z x b g m o q n c}     {h n b i t g h a q b c o r u}
    57  {d g l o h t b s b r}               {n u e p t i m u}
    58  {t d y e t d c w u o s w x f c h}   {i o s v y b r d r}
    59  {l b a p q n d r}                   {k d c c d n y q h g a o p e x}
    60  {f r z v m p k r}                   {x x r i s b a g f c}
    61  {s a z i e r f i w c n y v z t k s} {y y i r y n l s b w i e k n}
    62  {n x p r e x q r m v i b y}         {f o o z n b s r q j}
    63  {y j s u j x o n r q t f}           {f v k n v x u s o a d e f e}
    64  {u s i l y c x q}                   {r k c h p c h b o s s u s p b}
    65  {m p i o s h o}                     {s w h u n d m n q t y k b w c}
    66  {l d f g m x x x o}                 {s w d d f b y j j h h t i y p j o}
    67  {c b m h f n v w n h}               {i r w i e x r w l z p x u g u l s}
    68  {y a h u h i m a y q}               {d d r x h e v q n z y c j}
    69  {c x f d x o n p o b r t b l p l}   {m i t k b x v f p t m l l y r o}
    70  {u t l w w m s}                     {m f m o l t k o p e}
    71  {f g q e l n d m z x q}             {z s i i i m f w w f n g p e q}
    72  {n l h a v u o d f j d e x}         {v v s l f g d g r a j x i f z x}
    73  {x v m v f i g q e w}               {r y s j i k m j j e d g r n o i f}
    74  {g d y n o h p s y q z j d w n h w} {x o d l t j i b r d o r y}
    75  {p g b i u r b e q d v o a g w m k} {q y z s f q o h}
    76  {u z a q u f i f f b}               {b s p b a a d x r r i q f}
    77  {w h h z t h p o a h h e e}         {h w r p h k z v y f r x}
    78  {c a r k i a p u x}                 {f w l p t e m l}
    79  {q q u k o t r k z}                 {f b m c w p s s o z}
    80  {t i g v y q s r x m r x z e f}     {x o j w a u e y s j c b u p p r o}
    81  {n j n h r l a r e o z w e}         {v o r r j a v b}
    82  {i f i d k w d n h}                 {o i d z i z l m w s b q v u}
    83  {m d g q q b k b w f q q p p}       {j m q f b y c i z k y q p l e a}
    84  {m x o n y f g}                     {y c n x n q j i y c l h b r q z}
    85  {v o z l n p c}                     {g n j n t b b x n c l d a g j v}
    86  {z n a y f b t k k t d b z a v}     {r p c n r u k u}
    87  {b q t x z e c w}                   {q a o a l o a h i m j r}
    88  {j f h o x x a z g b a f a m i b}   {j z c z y x e x w t}
    89  {t c t p r s u c q n}               {z x l i k n f q l n t}
    90  {w t d q j g m r f k n}             {l e w f w w a l y q k i q t p c t}
    91  {c b o k l i c b s j n m b l}       {y f p q o w g}
    92  {f y d j o q t c c q m f j s t}     {f h e d y m o k}
    93  {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}
    94  {s f e a e t i h h d q p z t q}     {b k m k w h c}
    95  {h b n j t k i h o q u}             {w n g i t o k c a m y p f l x c p}
    96  {f c x p y r b m o l m o a}         {p c a q s u n n x d c f a o}
    97  {u h h k m n k}                     {u b v n u a o c}
    98  {s p e t c z d f n w f}             {l s f j b l c e s h}
    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) }
  }
} {}

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"
  8 "c"
  9 "no"
  10 "L O O L V V K"
} {
  set res [list]
  foreach {id x y} $data {
    set pat [string tolower $phrase]
    if {[string first $pat $x]>=0 || [string first $pat $y]>=0} {
      set res [concat $id $res]
    }
  }
  set n [llength $res]
  do_execsql_test 1.2.$tn.$n { 
    SELECT rowid FROM xx WHERE xx match '"' || $phrase || '"'
  } $res
}



finish_test