const u8 *a, int n,             /* Buffer containing poslist */
  int *pi,                        /* IN/OUT: Offset within a[] */
  i64 *piOff                      /* IN/OUT: Current offset */
);

/* Malloc utility */
void *sqlite3Fts5MallocZero(int *pRc, int nByte);


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

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

  const u8 *a, int n,             /* Buffer containing poslist */
  int *pi,                        /* IN/OUT: Offset within a[] */
  i64 *piOff                      /* IN/OUT: Current offset */
);

/* Malloc utility */
void *sqlite3Fts5MallocZero(int *pRc, int nByte);
char *sqlite3Fts5Strndup(int *pRc, const char *pIn, int nIn);

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

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

      *pRc = SQLITE_NOMEM;
    }else{
      memset(pRet, 0, nByte);
    }
  }
  return pRet;
}

























#endif /* SQLITE_ENABLE_FTS5 */

      *pRc = SQLITE_NOMEM;
    }else{
      memset(pRet, 0, nByte);
    }
  }
  return pRet;
}

/*
** Return a nul-terminated copy of the string indicated by pIn. If nIn
** is non-negative, then it is the length of the string in bytes. Otherwise,
** the length of the string is determined using strlen().
**
** It is the responsibility of the caller to eventually free the returned
** buffer using sqlite3_free(). If an OOM error occurs, NULL is returned. 
*/
char *sqlite3Fts5Strndup(int *pRc, const char *pIn, int nIn){
  char *zRet = 0;
  if( *pRc==SQLITE_OK ){
    if( nIn<0 ){
      nIn = strlen(pIn);
    }
    zRet = (char*)sqlite3_malloc(nIn+1);
    if( zRet ){
      memcpy(zRet, pIn, nIn);
      zRet[nIn] = '\0';
    }else{
      *pRc = SQLITE_NOMEM;
    }
  }
  return zRet;
}
#endif /* SQLITE_ENABLE_FTS5 */

  assert( 0==fts5_iswhitespace(z[0]) );
  quote = z[0];
  if( quote=='[' || quote=='\'' || quote=='"' || quote=='`' ){
    fts5Dequote(z);
  }
}

/*
** Duplicate the string passed as the only argument into a buffer allocated
** by sqlite3_malloc().
**
** Return 0 if an OOM error is encountered.
*/
static char *fts5Strdup(int *pRc, const char *z){
  char *pRet = 0;
  if( *pRc==SQLITE_OK ){
    pRet = sqlite3_mprintf("%s", z);
    if( pRet==0 ) *pRc = SQLITE_NOMEM;
  }
  return pRet;
}

/*
** Argument z points to a nul-terminated string containing an SQL identifier.
** This function returns a copy of the identifier enclosed in backtick 
** quotes.
*/
static char *fts5EscapeName(int *pRc, const char *z){
  char *pRet = 0;
................................................................................

  if( sqlite3_strnicmp("content_rowid", zCmd, nCmd)==0 ){
    int rc = SQLITE_OK;
    if( pConfig->zContentRowid ){
      *pzErr = sqlite3_mprintf("multiple content_rowid=... directives");
      rc = SQLITE_ERROR;
    }else{
      pConfig->zContentRowid = fts5Strdup(&rc, zArg);
    }
    return rc;
  }

  *pzErr = sqlite3_mprintf("unrecognized option: \"%.*s\"", nCmd, zCmd);
  return SQLITE_ERROR;
}
................................................................................
  memset(pRet, 0, sizeof(Fts5Config));
  pRet->db = db;
  pRet->iCookie = -1;

  nByte = nArg * (sizeof(char*) + sizeof(u8));
  pRet->azCol = (char**)sqlite3Fts5MallocZero(&rc, nByte);
  pRet->abUnindexed = (u8*)&pRet->azCol[nArg];
  pRet->zDb = fts5Strdup(&rc, azArg[1]);
  pRet->zName = fts5Strdup(&rc, azArg[2]);
  if( rc==SQLITE_OK && sqlite3_stricmp(pRet->zName, FTS5_RANK_NAME)==0 ){
    *pzErr = sqlite3_mprintf("reserved fts5 table name: %s", pRet->zName);
    rc = SQLITE_ERROR;
  }

  for(i=3; rc==SQLITE_OK && i<nArg; i++){
    const char *zOrig = azArg[i];
................................................................................
      rc = SQLITE_NOMEM;
    }else{
      sqlite3_free(pRet->zContentRowid);
      pRet->zContentRowid = 0;
    }
  }
  if( rc==SQLITE_OK && pRet->zContentRowid==0 ){
    pRet->zContentRowid = fts5Strdup(&rc, "rowid");
  }

  /* Formulate the zContentExprlist text */
  if( rc==SQLITE_OK ){
    rc = fts5ConfigMakeExprlist(pRet);
  }

  assert( 0==fts5_iswhitespace(z[0]) );
  quote = z[0];
  if( quote=='[' || quote=='\'' || quote=='"' || quote=='`' ){
    fts5Dequote(z);
  }
}
















/*
** Argument z points to a nul-terminated string containing an SQL identifier.
** This function returns a copy of the identifier enclosed in backtick 
** quotes.
*/
static char *fts5EscapeName(int *pRc, const char *z){
  char *pRet = 0;
................................................................................

  if( sqlite3_strnicmp("content_rowid", zCmd, nCmd)==0 ){
    int rc = SQLITE_OK;
    if( pConfig->zContentRowid ){
      *pzErr = sqlite3_mprintf("multiple content_rowid=... directives");
      rc = SQLITE_ERROR;
    }else{
      pConfig->zContentRowid = sqlite3Fts5Strndup(&rc, zArg, -1);
    }
    return rc;
  }

  *pzErr = sqlite3_mprintf("unrecognized option: \"%.*s\"", nCmd, zCmd);
  return SQLITE_ERROR;
}
................................................................................
  memset(pRet, 0, sizeof(Fts5Config));
  pRet->db = db;
  pRet->iCookie = -1;

  nByte = nArg * (sizeof(char*) + sizeof(u8));
  pRet->azCol = (char**)sqlite3Fts5MallocZero(&rc, nByte);
  pRet->abUnindexed = (u8*)&pRet->azCol[nArg];
  pRet->zDb = sqlite3Fts5Strndup(&rc, azArg[1], -1);
  pRet->zName = sqlite3Fts5Strndup(&rc, azArg[2], -1);
  if( rc==SQLITE_OK && sqlite3_stricmp(pRet->zName, FTS5_RANK_NAME)==0 ){
    *pzErr = sqlite3_mprintf("reserved fts5 table name: %s", pRet->zName);
    rc = SQLITE_ERROR;
  }

  for(i=3; rc==SQLITE_OK && i<nArg; i++){
    const char *zOrig = azArg[i];
................................................................................
      rc = SQLITE_NOMEM;
    }else{
      sqlite3_free(pRet->zContentRowid);
      pRet->zContentRowid = 0;
    }
  }
  if( rc==SQLITE_OK && pRet->zContentRowid==0 ){
    pRet->zContentRowid = sqlite3Fts5Strndup(&rc, "rowid", -1);
  }

  /* Formulate the zContentExprlist text */
  if( rc==SQLITE_OK ){
    rc = fts5ConfigMakeExprlist(pRet);
  }

  }

  sqlite3_free(sParse.apPhrase);
  *pzErr = sParse.zErr;
  return sParse.rc;
}

static char *fts5ExprStrdup(int *pRc, const char *zIn){
  char *zRet = 0;
  if( *pRc==SQLITE_OK ){
    int nByte = strlen(zIn) + 1;
    zRet = sqlite3_malloc(nByte);
    if( zRet ){
      memcpy(zRet, zIn, nByte);
    }else{
      *pRc = SQLITE_NOMEM;
    }
  }
  return zRet;
}

static void *fts5ExprMalloc(int *pRc, int nByte){
  void *pRet = 0;
  if( *pRc==SQLITE_OK ){
    pRet = sqlite3_malloc(nByte);
    if( pRet ){
      memset(pRet, 0, nByte);
    }else{
      *pRc = SQLITE_NOMEM;
    }
  }
  return pRet;
}

/*
** Create a new FTS5 expression by cloning phrase iPhrase of the
** expression passed as the second argument.
*/
int sqlite3Fts5ExprPhraseExpr(
  Fts5Config *pConfig,
  Fts5Expr *pExpr, 
................................................................................
){
  int rc = SQLITE_OK;             /* Return code */
  Fts5ExprPhrase *pOrig;          /* The phrase extracted from pExpr */
  Fts5ExprPhrase *pCopy;          /* Copy of pOrig */
  Fts5Expr *pNew = 0;             /* Expression to return via *ppNew */

  pOrig = pExpr->apExprPhrase[iPhrase];
  pCopy = (Fts5ExprPhrase*)fts5ExprMalloc(&rc, 
      sizeof(Fts5ExprPhrase) + sizeof(Fts5ExprTerm) * pOrig->nTerm
  );
  if( pCopy ){
    int i;                          /* Used to iterate through phrase terms */
    Fts5ExprPhrase **apPhrase;
    Fts5ExprNode *pNode;
    Fts5ExprNearset *pNear;

    pNew = (Fts5Expr*)fts5ExprMalloc(&rc, sizeof(Fts5Expr));

    apPhrase = (Fts5ExprPhrase**)fts5ExprMalloc(&rc, sizeof(Fts5ExprPhrase*));

    pNode = (Fts5ExprNode*)fts5ExprMalloc(&rc, sizeof(Fts5ExprNode));
    pNear = (Fts5ExprNearset*)fts5ExprMalloc(&rc, 
        sizeof(Fts5ExprNearset) + sizeof(Fts5ExprPhrase*)
    );

    for(i=0; i<pOrig->nTerm; i++){
      pCopy->aTerm[i].zTerm = fts5ExprStrdup(&rc, pOrig->aTerm[i].zTerm);
      pCopy->aTerm[i].bPrefix = pOrig->aTerm[i].bPrefix;
    }

    if( rc==SQLITE_OK ){
      /* All the allocations succeeded. Put the expression object together. */
      pNew->pIndex = pExpr->pIndex;
      pNew->pRoot = pNode;
................................................................................
 ismatch_out:
  *pbMatch = (a[0].pOut->n>0);
  if( a!=aStatic ) sqlite3_free(a);
  return rc;
}

/*
** Advance each term iterator in each phrase in 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 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;
      int rc = sqlite3Fts5IterNext(pIter);
      if( rc || sqlite3Fts5IterEof(pIter) ){
        *pbEof = 1;
        return rc;
      }
    }
  }

  return SQLITE_OK;
}

/*
** Advance iterator pIter until it points to a value equal to or laster
** than the initial value of *piLast. If this means the iterator points
** to a value laster than *piLast, update *piLast to the new lastest value.
**
................................................................................
**
** 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,
  int bFromValid,
  i64 iFrom
){
  Fts5ExprNearset *pNear = pNode->pNear;
  int rc = SQLITE_OK;
  int i, j;                       /* Phrase and token index, respectively */
  i64 iLast;                      /* Lastest rowid any iterator points to */
  int bMatch;                     /* True if all terms are at the same rowid */

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

  do {
    bMatch = 1;
    for(i=0; i<pNear->nPhrase; i++){
      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
      for(j=0; j<pPhrase->nTerm; j++){
        Fts5IndexIter *pIter = pPhrase->aTerm[j].pIter;
................................................................................
**
** 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,            /* The "NEAR" node (FTS5_STRING) */
  int bFromValid,
  i64 iFrom
){
  int rc = SQLITE_OK;
  Fts5ExprNearset *pNear = pNode->pNear;
  while( 1 ){
    int i;

    /* Advance the iterators until they all point to the same rowid */
    rc = fts5ExprNearNextRowidMatch(pExpr, pNode, bFromValid, iFrom);
    if( rc!=SQLITE_OK || pNode->bEof ) break;

    /* Check that each phrase in the nearset matches the current row.
    ** Populate the pPhrase->poslist buffers at the same time. If any
    ** phrase is not a match, break out of the loop early.  */
    for(i=0; rc==SQLITE_OK && i<pNear->nPhrase; i++){
      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
................................................................................
      }
      if( rc!=SQLITE_OK || bMatch ) break;
    }

    /* If control flows to here, then the current rowid is not a match.
    ** Advance all term iterators in all phrases to the next rowid. */
    if( rc==SQLITE_OK ){
      rc = fts5ExprNearAdvanceAll(pExpr, pNear, &pNode->bEof);
    }
    if( pNode->bEof || rc!=SQLITE_OK ) break;
  }

  return rc;
}

................................................................................
    }
  }

  return rc;
}

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

















/*
** 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
................................................................................
static int fts5NodeCompare(
  Fts5Expr *pExpr,
  Fts5ExprNode *p1, 
  Fts5ExprNode *p2
){
  if( p2->bEof ) return -1;
  if( p1->bEof ) return +1;
  if( pExpr->bDesc==0 ){
    if( p1->iRowid<p2->iRowid ) return -1;
    return (p1->iRowid > p2->iRowid);
  }else{
    if( p1->iRowid>p2->iRowid ) return -1;
    return (p1->iRowid < p2->iRowid);
  }
}

/*
** Advance node iterator pNode, part of expression pExpr. If argument
** bFromValid is zero, then pNode is advanced exactly once. Or, if argument
** bFromValid is non-zero, then pNode is advanced until it is at or past
** rowid value iFrom. Whether "past" means "less than" or "greater than"
................................................................................
  i64 iFrom
){
  int rc = SQLITE_OK;

  if( pNode->bEof==0 ){
    switch( pNode->eType ){
      case FTS5_STRING: {
        rc = fts5ExprNearAdvanceAll(pExpr, pNode->pNear, &pNode->bEof);
        break;
      };

      case FTS5_AND: {
        rc = fts5ExprNodeNext(pExpr, pNode->pLeft, bFromValid, iFrom);
        if( rc==SQLITE_OK ){
          /* todo: update (iFrom/bFromValid) here */
................................................................................
      }

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

        if( cmp==0 ){
          rc = fts5ExprNodeNext(pExpr, p1, bFromValid, iFrom);



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

        break;
      }

      default: assert( pNode->eType==FTS5_NOT ); {
        rc = fts5ExprNodeNext(pExpr, pNode->pLeft, bFromValid, iFrom);
        break;
      }
    }

    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeNextMatch(pExpr, pNode, bFromValid, iFrom);
    }
  }













  return rc;
}

static void fts5ExprSetEof(Fts5ExprNode *pNode){
  if( pNode ){
    pNode->bEof = 1;
    fts5ExprSetEof(pNode->pLeft);
    fts5ExprSetEof(pNode->pRight);
  }
}

/*
**
*/
static int fts5ExprNodeNextMatch(
  Fts5Expr *pExpr, 
  Fts5ExprNode *pNode,
  int bFromValid,
  i64 iFrom
){
  int rc = SQLITE_OK;
  if( pNode->bEof==0 ){
    switch( pNode->eType ){

      case FTS5_STRING: {
        rc = fts5ExprNearNextMatch(pExpr, pNode, bFromValid, iFrom);
        break;
      }

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

        while( p1->bEof==0 && p2->bEof==0 && p2->iRowid!=p1->iRowid ){
          Fts5ExprNode *pAdv;

          assert( pExpr->bDesc==0 || pExpr->bDesc==1 );
          if( pExpr->bDesc==(p1->iRowid > p2->iRowid) ){
            pAdv = p1;
            if( bFromValid==0 || pExpr->bDesc==(p2->iRowid < iFrom) ){
              iFrom = p2->iRowid;
            }
          }else{
            pAdv = p2;
            if( bFromValid==0 || pExpr->bDesc==(p1->iRowid < iFrom) ){
              iFrom = p1->iRowid;
            }
          }
          rc = fts5ExprNodeNext(pExpr, pAdv, 1, iFrom);
          if( rc!=SQLITE_OK ) break;
        }
        if( p1->bEof || p2->bEof ){
          fts5ExprSetEof(pNode);
        }
................................................................................
        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, bFromValid, iFrom);

          }

          if( rc || cmp ) break;
          rc = fts5ExprNodeNext(pExpr, p1, bFromValid, iFrom);
        }
        pNode->bEof = p1->bEof;
        pNode->iRowid = p1->iRowid;
        break;
      }
    }
  }
................................................................................
  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, 0, 0);
    }

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



................................................................................
  return (p->pRoot==0 || p->pRoot->bEof);
}

i64 sqlite3Fts5ExprRowid(Fts5Expr *p){
  return p->pRoot->iRowid;
}

/*
** Argument pIn points to a buffer of nIn bytes. This function allocates
** and returns a new buffer populated with a copy of (pIn/nIn) with a 
** nul-terminator byte appended to it.
**
** It is the responsibility of the caller to eventually free the returned
** buffer using sqlite3_free(). If an OOM error occurs, NULL is returned. 
*/
static char *fts5Strndup(int *pRc, const char *pIn, int nIn){
  char *zRet = 0;
  if( *pRc==SQLITE_OK ){
    zRet = (char*)sqlite3_malloc(nIn+1);
    if( zRet ){
      memcpy(zRet, pIn, nIn);
      zRet[nIn] = '\0';
    }else{
      *pRc = SQLITE_NOMEM;
    }
  }
  return zRet;
}

static int fts5ParseStringFromToken(Fts5Token *pToken, char **pz){
  int rc = SQLITE_OK;
  *pz = fts5Strndup(&rc, pToken->p, pToken->n);
  return rc;
}

/*
** Free the phrase object passed as the only argument.
*/
static void fts5ExprPhraseFree(Fts5ExprPhrase *pPhrase){
................................................................................
      if( pRet==0 ){
        pParse->rc = SQLITE_NOMEM;
      }else{
        memset(pRet, 0, nByte);
        pRet->iCol = -1;
      }
    }else if( (pNear->nPhrase % SZALLOC)==0 ){
      int nNew = pRet->nPhrase + SZALLOC;
      int nByte = sizeof(Fts5ExprNearset) + nNew * sizeof(Fts5ExprPhrase*);

      pRet = (Fts5ExprNearset*)sqlite3_realloc(pNear, nByte);
      if( pRet==0 ){
        pParse->rc = SQLITE_NOMEM;
      }
    }else{
................................................................................
    if( pPhrase==0 ) memset(pNew, 0, sizeof(Fts5ExprPhrase));
    pCtx->pPhrase = pPhrase = pNew;
    pNew->nTerm = nNew - SZALLOC;
  }

  pTerm = &pPhrase->aTerm[pPhrase->nTerm++];
  memset(pTerm, 0, sizeof(Fts5ExprTerm));
  pTerm->zTerm = fts5Strndup(&rc, pToken, nToken);

  return rc;
}


/*
** Free the phrase object passed as the only argument.
................................................................................

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

void sqlite3Fts5ParseSetDistance(
  Fts5Parse *pParse, 
  Fts5ExprNearset *pNear, 
  Fts5Token *p
................................................................................
}

void sqlite3Fts5ParseSetColumn(
  Fts5Parse *pParse, 
  Fts5ExprNearset *pNear, 
  Fts5Token *p
){

  char *z = 0;
  int rc = fts5ParseStringFromToken(p, &z);
  if( rc==SQLITE_OK ){
    Fts5Config *pConfig = pParse->pConfig;
    int i;
    for(i=0; i<pConfig->nCol; i++){
      if( 0==sqlite3_stricmp(pConfig->azCol[i], z) ){
        pNear->iCol = i;
        break;
      }
    }
    if( i==pConfig->nCol ){
      sqlite3Fts5ParseError(pParse, "no such column: %s", z);
    }
    sqlite3_free(z);
  }else{
    pParse->rc = rc;

  }
}

/*
** Allocate and return a new expression object. If anything goes wrong (i.e.
** OOM error), leave an error code in pParse and return NULL.
*/

  }

  sqlite3_free(sParse.apPhrase);
  *pzErr = sParse.zErr;
  return sParse.rc;
}




























/*
** Create a new FTS5 expression by cloning phrase iPhrase of the
** expression passed as the second argument.
*/
int sqlite3Fts5ExprPhraseExpr(
  Fts5Config *pConfig,
  Fts5Expr *pExpr, 
................................................................................
){
  int rc = SQLITE_OK;             /* Return code */
  Fts5ExprPhrase *pOrig;          /* The phrase extracted from pExpr */
  Fts5ExprPhrase *pCopy;          /* Copy of pOrig */
  Fts5Expr *pNew = 0;             /* Expression to return via *ppNew */

  pOrig = pExpr->apExprPhrase[iPhrase];
  pCopy = (Fts5ExprPhrase*)sqlite3Fts5MallocZero(&rc, 
      sizeof(Fts5ExprPhrase) + sizeof(Fts5ExprTerm) * pOrig->nTerm
  );
  if( pCopy ){
    int i;                          /* Used to iterate through phrase terms */
    Fts5ExprPhrase **apPhrase;
    Fts5ExprNode *pNode;
    Fts5ExprNearset *pNear;

    pNew = (Fts5Expr*)sqlite3Fts5MallocZero(&rc, sizeof(Fts5Expr));
    apPhrase = (Fts5ExprPhrase**)sqlite3Fts5MallocZero(&rc, 
        sizeof(Fts5ExprPhrase*)
    );
    pNode = (Fts5ExprNode*)sqlite3Fts5MallocZero(&rc, sizeof(Fts5ExprNode));
    pNear = (Fts5ExprNearset*)sqlite3Fts5MallocZero(&rc, 
        sizeof(Fts5ExprNearset) + sizeof(Fts5ExprPhrase*)
    );

    for(i=0; i<pOrig->nTerm; i++){
      pCopy->aTerm[i].zTerm = sqlite3Fts5Strndup(&rc, pOrig->aTerm[i].zTerm,-1);
      pCopy->aTerm[i].bPrefix = pOrig->aTerm[i].bPrefix;
    }

    if( rc==SQLITE_OK ){
      /* All the allocations succeeded. Put the expression object together. */
      pNew->pIndex = pExpr->pIndex;
      pNew->pRoot = pNode;
................................................................................
 ismatch_out:
  *pbMatch = (a[0].pOut->n>0);
  if( a!=aStatic ) sqlite3_free(a);
  return rc;
}

/*
** Advance the first term iterator in the first phrase of pNear. Set output
** variable *pbEof to true if it reaches EOF or if an error occurs.
**
** Return SQLITE_OK if successful, or an SQLite error code if an error
** occurs.
*/
static int fts5ExprNearAdvanceFirst(
  Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
  Fts5ExprNode *pNode,            /* FTS5_STRING node */
  int bFromValid,
  i64 iFrom 
){
  Fts5IndexIter *pIter = pNode->pNear->apPhrase[0]->aTerm[0].pIter;
  int rc;

  if( bFromValid ){
    rc = sqlite3Fts5IterNextFrom(pIter, iFrom);
  }else{
    rc = sqlite3Fts5IterNext(pIter);
  }

  pNode->bEof = (rc || sqlite3Fts5IterEof(pIter));
  return rc;
}

/*
** Advance iterator pIter until it points to a value equal to or laster
** than the initial value of *piLast. If this means the iterator points
** to a value laster than *piLast, update *piLast to the new lastest value.
**
................................................................................
**
** 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 iLast;                      /* Lastest rowid any iterator points to */
  int bMatch;                     /* True if all terms are at the same rowid */

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





  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;
................................................................................
**
** 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             /* The "NEAR" node (FTS5_STRING) */


){
  int rc = SQLITE_OK;
  Fts5ExprNearset *pNear = pNode->pNear;
  while( 1 ){
    int i;

    /* Advance the iterators until they all point to the same rowid */
    rc = fts5ExprNearNextRowidMatch(pExpr, pNode);
    if( rc!=SQLITE_OK || pNode->bEof ) break;

    /* Check that each phrase in the nearset matches the current row.
    ** Populate the pPhrase->poslist buffers at the same time. If any
    ** phrase is not a match, break out of the loop early.  */
    for(i=0; rc==SQLITE_OK && i<pNear->nPhrase; i++){
      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
................................................................................
      }
      if( rc!=SQLITE_OK || bMatch ) break;
    }

    /* If control flows to here, then the current rowid is not a match.
    ** Advance all term iterators in all phrases to the next rowid. */
    if( rc==SQLITE_OK ){
      rc = fts5ExprNearAdvanceFirst(pExpr, pNode, 0, 0);
    }
    if( pNode->bEof || rc!=SQLITE_OK ) break;
  }

  return rc;
}

................................................................................
    }
  }

  return rc;
}

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


static int fts5RowidCmp(
  Fts5Expr *pExpr,
  i64 iLhs,
  i64 iRhs
){
  assert( pExpr->bDesc==0 || pExpr->bDesc==1 );
  if( pExpr->bDesc==0 ){
    if( iLhs<iRhs ) return -1;
    return (iLhs > iRhs);
  }else{
    if( iLhs>iRhs ) return -1;
    return (iLhs < iRhs);
  }
}

/*
** 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
................................................................................
static int fts5NodeCompare(
  Fts5Expr *pExpr,
  Fts5ExprNode *p1, 
  Fts5ExprNode *p2
){
  if( p2->bEof ) return -1;
  if( p1->bEof ) return +1;
  return fts5RowidCmp(pExpr, p1->iRowid, p2->iRowid);






}

/*
** Advance node iterator pNode, part of expression pExpr. If argument
** bFromValid is zero, then pNode is advanced exactly once. Or, if argument
** bFromValid is non-zero, then pNode is advanced until it is at or past
** rowid value iFrom. Whether "past" means "less than" or "greater than"
................................................................................
  i64 iFrom
){
  int rc = SQLITE_OK;

  if( pNode->bEof==0 ){
    switch( pNode->eType ){
      case FTS5_STRING: {
        rc = fts5ExprNearAdvanceFirst(pExpr, pNode, bFromValid, iFrom);
        break;
      };

      case FTS5_AND: {
        rc = fts5ExprNodeNext(pExpr, pNode->pLeft, bFromValid, iFrom);
        if( rc==SQLITE_OK ){
          /* todo: update (iFrom/bFromValid) here */
................................................................................
      }

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

        if( cmp<=0 || (bFromValid && fts5RowidCmp(pExpr,p1->iRowid,iFrom)<0) ){
          rc = fts5ExprNodeNext(pExpr, p1, bFromValid, iFrom);
        }

        if( cmp>=0 || (bFromValid && fts5RowidCmp(pExpr,p2->iRowid,iFrom)<0) ){
          if( rc==SQLITE_OK ){
            rc = fts5ExprNodeNext(pExpr, p2, bFromValid, iFrom);
          }


        }

        break;
      }

      default: assert( pNode->eType==FTS5_NOT ); {
        rc = fts5ExprNodeNext(pExpr, pNode->pLeft, bFromValid, iFrom);
        break;
      }
    }

    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeNextMatch(pExpr, pNode);
    }
  }

  /* Assert that if bFromValid was true, either:
  **
  **   a) an error occurred, or
  **   b) the node is now at EOF, or
  **   c) the node is now at or past rowid iFrom.
  */
  assert( bFromValid==0 
      || rc!=SQLITE_OK                                                  /* a */
      || pNode->bEof                                                    /* b */
      || pNode->iRowid==iFrom || pExpr->bDesc==(pNode->iRowid<iFrom)    /* c */
  );

  return rc;
}

static void fts5ExprSetEof(Fts5ExprNode *pNode){
  if( pNode ){
    pNode->bEof = 1;
    fts5ExprSetEof(pNode->pLeft);
    fts5ExprSetEof(pNode->pRight);
  }
}

/*
** If pNode currently points to a match, this function returns SQLITE_OK
** without modifying it. Otherwise, pNode is advanced until it does point
** to a match or EOF is reached.
*/
static int fts5ExprNodeNextMatch(
  Fts5Expr *pExpr,                /* Expression of which pNode is a part */
  Fts5ExprNode *pNode             /* Expression node to test */
){
  int rc = SQLITE_OK;
  if( pNode->bEof==0 ){
    switch( pNode->eType ){

      case FTS5_STRING: {
        rc = fts5ExprNearNextMatch(pExpr, pNode);
        break;
      }

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

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

            iFrom = p2->iRowid;

          }else{
            pAdv = p2;

            iFrom = p1->iRowid;

          }
          rc = fts5ExprNodeNext(pExpr, pAdv, 1, iFrom);
          if( rc!=SQLITE_OK ) break;
        }
        if( p1->bEof || p2->bEof ){
          fts5ExprSetEof(pNode);
        }
................................................................................
        pNode->iRowid = pNext->iRowid;
        break;
      }

      default: assert( pNode->eType==FTS5_NOT ); {
        Fts5ExprNode *p1 = pNode->pLeft;
        Fts5ExprNode *p2 = pNode->pRight;

        while( rc==SQLITE_OK && p1->bEof==0 ){

          int cmp = fts5NodeCompare(pExpr, p1, p2);
          if( cmp>0 ){
            rc = fts5ExprNodeNext(pExpr, p2, 1, p1->iRowid);
            cmp = fts5NodeCompare(pExpr, p1, p2);
          }
          assert( rc!=SQLITE_OK || cmp<=0 );
          if( rc || cmp<0 ) break;
          rc = fts5ExprNodeNext(pExpr, p1, 0, 0);
        }
        pNode->bEof = p1->bEof;
        pNode->iRowid = p1->iRowid;
        break;
      }
    }
  }
................................................................................
  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 = fts5ExprNodeNextMatch(pExpr, pNode);
    }
  }
  return rc;
}



................................................................................
  return (p->pRoot==0 || p->pRoot->bEof);
}

i64 sqlite3Fts5ExprRowid(Fts5Expr *p){
  return p->pRoot->iRowid;
}























static int fts5ParseStringFromToken(Fts5Token *pToken, char **pz){
  int rc = SQLITE_OK;
  *pz = sqlite3Fts5Strndup(&rc, pToken->p, pToken->n);
  return rc;
}

/*
** Free the phrase object passed as the only argument.
*/
static void fts5ExprPhraseFree(Fts5ExprPhrase *pPhrase){
................................................................................
      if( pRet==0 ){
        pParse->rc = SQLITE_NOMEM;
      }else{
        memset(pRet, 0, nByte);
        pRet->iCol = -1;
      }
    }else if( (pNear->nPhrase % SZALLOC)==0 ){
      int nNew = pNear->nPhrase + SZALLOC;
      int nByte = sizeof(Fts5ExprNearset) + nNew * sizeof(Fts5ExprPhrase*);

      pRet = (Fts5ExprNearset*)sqlite3_realloc(pNear, nByte);
      if( pRet==0 ){
        pParse->rc = SQLITE_NOMEM;
      }
    }else{
................................................................................
    if( pPhrase==0 ) memset(pNew, 0, sizeof(Fts5ExprPhrase));
    pCtx->pPhrase = pPhrase = pNew;
    pNew->nTerm = nNew - SZALLOC;
  }

  pTerm = &pPhrase->aTerm[pPhrase->nTerm++];
  memset(pTerm, 0, sizeof(Fts5ExprTerm));
  pTerm->zTerm = sqlite3Fts5Strndup(&rc, pToken, nToken);

  return rc;
}


/*
** Free the phrase object passed as the only argument.
................................................................................

/*
** 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( pTok->n!=4 || memcmp("NEAR", pTok->p, 4) ){
    sqlite3Fts5ParseError(
        pParse, "fts5: syntax error near \"%.*s\"", pTok->n, pTok->p
    );

  }
}

void sqlite3Fts5ParseSetDistance(
  Fts5Parse *pParse, 
  Fts5ExprNearset *pNear, 
  Fts5Token *p
................................................................................
}

void sqlite3Fts5ParseSetColumn(
  Fts5Parse *pParse, 
  Fts5ExprNearset *pNear, 
  Fts5Token *p
){
  if( pParse->rc==SQLITE_OK ){
    char *z = 0;
    int rc = fts5ParseStringFromToken(p, &z);
    if( rc==SQLITE_OK ){
      Fts5Config *pConfig = pParse->pConfig;
      int i;
      for(i=0; i<pConfig->nCol; i++){
        if( 0==sqlite3_stricmp(pConfig->azCol[i], z) ){
          pNear->iCol = i;
          break;
        }
      }
      if( i==pConfig->nCol ){
        sqlite3Fts5ParseError(pParse, "no such column: %s", z);
      }
      sqlite3_free(z);
    }else{
      pParse->rc = rc;
    }
  }
}

/*
** Allocate and return a new expression object. If anything goes wrong (i.e.
** OOM error), leave an error code in pParse and return NULL.
*/

foreach {tn expr err} {
  1 {AND}                          {fts5: syntax error near "AND"}
  2 {abc def AND}                  {fts5: syntax error near ""}
  3 {abc OR AND}                   {fts5: syntax error near "AND"}
  4 {(a OR b) abc}                 {fts5: syntax error near "abc"}
  5 {NEaR (a b)}                   {fts5: syntax error near "NEaR"}

  6 {(a OR b) NOT c)}              {fts5: syntax error near ")"}
  7 {nosuch: a nosuch2: b}         {no such column: nosuch}
  8 {addr: a nosuch2: b}           {no such column: nosuch2}
  9 {NOT}                          {fts5: syntax error near "NOT"}
  10 {a AND "abc}                  {unterminated string}



} {
  do_catchsql_test 3.$tn {SELECT fts5_expr($expr, 'name', 'addr')} [list 1 $err]
}




finish_test

foreach {tn expr err} {
  1 {AND}                          {fts5: syntax error near "AND"}
  2 {abc def AND}                  {fts5: syntax error near ""}
  3 {abc OR AND}                   {fts5: syntax error near "AND"}
  4 {(a OR b) abc}                 {fts5: syntax error near "abc"}
  5 {NEaR (a b)}                   {fts5: syntax error near "NEaR"}
  6 {NEa (a b)}                    {fts5: syntax error near "NEa"}
  7 {(a OR b) NOT c)}              {fts5: syntax error near ")"}
  8 {nosuch: a nosuch2: b}         {no such column: nosuch}
  9 {addr: a nosuch2: b}           {no such column: nosuch2}
  10 {NOT}                          {fts5: syntax error near "NOT"}
  11 {a AND "abc}                  {unterminated string}

  12 {NEAR(a b, xyz)}              {expected integer, got "xyz"}
  13 {NEAR(a b, // )}              {expected integer, got "//"}
} {
  do_catchsql_test 3.$tn {SELECT fts5_expr($expr, 'name', 'addr')} [list 1 $err]
}




finish_test

sqlite3_fts5_create_function db previc  previc

do_faultsim_test 6.2 -faults oom-t* -body {
  db eval { SELECT previc(x3) FROM x3 WHERE x3 MATCH 'a' }
} -test {
  faultsim_test_result {0 {0 2 7}} {1 SQLITE_NOMEM}
}



#-------------------------------------------------------------------------
# OOM error when querying for a phrase with many tokens.
#
reset_db
do_execsql_test 7.0 {
  CREATE VIRTUAL TABLE tt USING fts5(x, y);
................................................................................
  INSERT INTO tt VALUES('a g b d a g', 'e g a e a c');  -- 5
  INSERT INTO tt VALUES('c d b d e f', 'f g e g e e');  -- 6
  INSERT INTO tt VALUES('e g f f b c', 'f c e f g f');  -- 7
  INSERT INTO tt VALUES('e g c f c e', 'f e e a f g');  -- 8
  INSERT INTO tt VALUES('e a e b e e', 'd c c f f f');  -- 9
  INSERT INTO tt VALUES('f a g g c c', 'e g d g c e');  -- 10
  INSERT INTO tt VALUES('c d b a e f', 'f g e h e e');  -- 11




}

do_faultsim_test 7.2 -faults oom-* -body {
  db eval { SELECT rowid FROM tt WHERE tt MATCH 'f+g+e+g+e+e' }
} -test {
  faultsim_test_result {0 6} {1 SQLITE_NOMEM}
}
................................................................................

do_faultsim_test 7.3 -faults oom-* -body {
  db eval { SELECT rowid FROM tt WHERE tt MATCH 'NEAR(a b c d e f)' }
} -test {
  faultsim_test_result {0 11} {1 SQLITE_NOMEM}
}

















}

#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 8.0 {
  CREATE VIRTUAL TABLE tt USING fts5(x);
................................................................................

do_faultsim_test 8.2 -faults oom-t* -body {
  db eval { SELECT count(*) FROM tt WHERE tt MATCH 'a OR d' }
} -test {
  faultsim_test_result {0 100} {1 SQLITE_NOMEM}
}

























finish_test

sqlite3_fts5_create_function db previc  previc

do_faultsim_test 6.2 -faults oom-t* -body {
  db eval { SELECT previc(x3) FROM x3 WHERE x3 MATCH 'a' }
} -test {
  faultsim_test_result {0 {0 2 7}} {1 SQLITE_NOMEM}
}

}

#-------------------------------------------------------------------------
# OOM error when querying for a phrase with many tokens.
#
reset_db
do_execsql_test 7.0 {
  CREATE VIRTUAL TABLE tt USING fts5(x, y);
................................................................................
  INSERT INTO tt VALUES('a g b d a g', 'e g a e a c');  -- 5
  INSERT INTO tt VALUES('c d b d e f', 'f g e g e e');  -- 6
  INSERT INTO tt VALUES('e g f f b c', 'f c e f g f');  -- 7
  INSERT INTO tt VALUES('e g c f c e', 'f e e a f g');  -- 8
  INSERT INTO tt VALUES('e a e b e e', 'd c c f f f');  -- 9
  INSERT INTO tt VALUES('f a g g c c', 'e g d g c e');  -- 10
  INSERT INTO tt VALUES('c d b a e f', 'f g e h e e');  -- 11

  CREATE VIRTUAL TABLE tt2 USING fts5(o);
  INSERT INTO tt2(rowid, o) SELECT rowid, x||' '||y FROM tt;
  INSERT INTO tt2(rowid, o) VALUES(12, 'a b c d e f g h i j k l');
}

do_faultsim_test 7.2 -faults oom-* -body {
  db eval { SELECT rowid FROM tt WHERE tt MATCH 'f+g+e+g+e+e' }
} -test {
  faultsim_test_result {0 6} {1 SQLITE_NOMEM}
}
................................................................................

do_faultsim_test 7.3 -faults oom-* -body {
  db eval { SELECT rowid FROM tt WHERE tt MATCH 'NEAR(a b c d e f)' }
} -test {
  faultsim_test_result {0 11} {1 SQLITE_NOMEM}
}

do_faultsim_test 7.4 -faults oom-t* -body {
  db eval { SELECT rowid FROM tt2 WHERE tt2 MATCH '"g c f c e f e e a f"' }
} -test {
  faultsim_test_result {0 8} {1 SQLITE_NOMEM}
}

do_faultsim_test 7.5 -faults oom-* -body {
  db eval {SELECT rowid FROM tt2 WHERE tt2 MATCH 'NEAR(a b c d e f g h i j k)'}
} -test {
  faultsim_test_result {0 12} {1 SQLITE_NOMEM}
}

do_faultsim_test 7.6 -faults oom-* -body {
  db eval {SELECT rowid FROM tt WHERE tt MATCH 'y: "c c"'}
} -test {
  faultsim_test_result {0 {1 9}} {1 SQLITE_NOMEM}
}

#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 8.0 {
  CREATE VIRTUAL TABLE tt USING fts5(x);
................................................................................

do_faultsim_test 8.2 -faults oom-t* -body {
  db eval { SELECT count(*) FROM tt WHERE tt MATCH 'a OR d' }
} -test {
  faultsim_test_result {0 100} {1 SQLITE_NOMEM}
}


#-------------------------------------------------------------------------
# Fault in NOT query.
#
reset_db
do_execsql_test 9.0 {
  CREATE VIRTUAL TABLE tt USING fts5(x);
  INSERT INTO tt(tt, rank) VALUES('pgsz', 32);
  BEGIN;
    WITH ii(i) AS (SELECT 1 UNION ALL SELECT i+1 FROM ii WHERE i<200)
      INSERT INTO tt(rowid, x) 
      SELECT i, CASE WHEN (i%50)==0 THEN 'a a a a a a' ELSE 'a x a x a x' END 
      FROM ii;
  COMMIT;
}

do_faultsim_test 9.1 -faults oom-* -body {
  db eval { SELECT rowid FROM tt WHERE tt MATCH 'a NOT x' }
} -test {
  faultsim_test_result {0 {50 100 150 200}} {1 SQLITE_NOMEM}
}



finish_test