text: /*
  ** 2014 May 31
  **
  ** 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.
  **
  ******************************************************************************
  **
  */
  
  
  
  #include "fts5Int.h"
  #include "fts5parse.h"
  
  /*
  ** All token types in the generated fts5parse.h file are greater than 0.
  */
  #define FTS5_EOF 0
  
  #define FTS5_LARGEST_INT64  (0xffffffff|(((i64)0x7fffffff)<<32))
  
  typedef struct Fts5ExprTerm Fts5ExprTerm;
  
  /*
  ** Functions generated by lemon from fts5parse.y.
  */
  void *sqlite3Fts5ParserAlloc(void *(*mallocProc)(u64));
  void sqlite3Fts5ParserFree(void*, void (*freeProc)(void*));
  void sqlite3Fts5Parser(void*, int, Fts5Token, Fts5Parse*);
  #ifndef NDEBUG
  #include <stdio.h>
  void sqlite3Fts5ParserTrace(FILE*, char*);
  #endif
  int sqlite3Fts5ParserFallback(int);
  
  
  struct Fts5Expr {
    Fts5Index *pIndex;
    Fts5Config *pConfig;
    Fts5ExprNode *pRoot;
    int bDesc;                      /* Iterate in descending rowid order */
    int nPhrase;                    /* Number of phrases in expression */
    Fts5ExprPhrase **apExprPhrase;  /* Pointers to phrase objects */
  };
  
  /*
  ** eType:
  **   Expression node type. Always one of:
  **
  **       FTS5_AND                 (nChild, apChild valid)
  **       FTS5_OR                  (nChild, apChild valid)
  **       FTS5_NOT                 (nChild, apChild valid)
  **       FTS5_STRING              (pNear valid)
  **       FTS5_TERM                (pNear valid)
  */
  struct Fts5ExprNode {
    int eType;                      /* Node type */
    int bEof;                       /* True at EOF */
    int bNomatch;                   /* True if entry is not a match */
  
    /* Next method for this node. */
    int (*xNext)(Fts5Expr*, Fts5ExprNode*, int, i64);
  
    i64 iRowid;                     /* Current rowid */
    Fts5ExprNearset *pNear;         /* For FTS5_STRING - cluster of phrases */
  
    /* Child nodes. For a NOT node, this array always contains 2 entries. For 
    ** AND or OR nodes, it contains 2 or more entries.  */
    int nChild;                     /* Number of child nodes */
    Fts5ExprNode *apChild[1];       /* Array of child nodes */
  };
  
  #define Fts5NodeIsString(p) ((p)->eType==FTS5_TERM || (p)->eType==FTS5_STRING)
  
  /*
  ** Invoke the xNext method of an Fts5ExprNode object. This macro should be
  ** used as if it has the same signature as the xNext() methods themselves.
  */
  #define fts5ExprNodeNext(a,b,c,d) (b)->xNext((a), (b), (c), (d))
  
  /*
  ** An instance of the following structure represents a single search term
  ** or term prefix.
  */
  struct Fts5ExprTerm {
    u8 bPrefix;                     /* True for a prefix term */
    u8 bFirst;                      /* True if token must be first in column */
    char *zTerm;                    /* nul-terminated term */
    Fts5IndexIter *pIter;           /* Iterator for this term */
    Fts5ExprTerm *pSynonym;         /* Pointer to first in list of synonyms */
  };
  
  /*
  ** A phrase. One or more terms that must appear in a contiguous sequence
  ** within a document for it to match.
  */
  struct Fts5ExprPhrase {
    Fts5ExprNode *pNode;            /* FTS5_STRING node this phrase is part of */
    Fts5Buffer poslist;             /* Current position list */
    int nTerm;                      /* Number of entries in aTerm[] */
    Fts5ExprTerm aTerm[1];          /* 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.
  */
  struct Fts5ExprNearset {
    int nNear;                      /* NEAR parameter */
    Fts5Colset *pColset;            /* Columns to search (NULL -> all columns) */
    int nPhrase;                    /* Number of entries in aPhrase[] array */
    Fts5ExprPhrase *apPhrase[1];    /* Array of phrase pointers */
  };
  
  
  /*
  ** Parse context.
  */
  struct Fts5Parse {
    Fts5Config *pConfig;
    char *zErr;
    int rc;
    int nPhrase;                    /* Size of apPhrase array */
    Fts5ExprPhrase **apPhrase;      /* Array of all phrases */
    Fts5ExprNode *pExpr;            /* Result of a successful parse */
    int bPhraseToAnd;               /* Convert "a+b" to "a AND b" */
  };
  
  void sqlite3Fts5ParseError(Fts5Parse *pParse, const char *zFmt, ...){
    va_list ap;
    va_start(ap, zFmt);
    if( pParse->rc==SQLITE_OK ){
      assert( pParse->zErr==0 );
      pParse->zErr = sqlite3_vmprintf(zFmt, ap);
      pParse->rc = SQLITE_ERROR;
    }
    va_end(ap);
  }
  
  static int fts5ExprIsspace(char t){
    return t==' ' || t=='\t' || t=='\n' || t=='\r';
  }
  
  /*
  ** Read the first token from the nul-terminated string at *pz.
  */
  static int fts5ExprGetToken(
    Fts5Parse *pParse, 
    const char **pz,                /* IN/OUT: Pointer into buffer */
    Fts5Token *pToken
  ){
    const char *z = *pz;
    int tok;
  
    /* Skip past any whitespace */
    while( fts5ExprIsspace(*z) ) z++;
  
    pToken->p = z;
    pToken->n = 1;
    switch( *z ){
      case '(':  tok = FTS5_LP;    break;
      case ')':  tok = FTS5_RP;    break;
      case '{':  tok = FTS5_LCP;   break;
      case '}':  tok = FTS5_RCP;   break;
      case ':':  tok = FTS5_COLON; break;
      case ',':  tok = FTS5_COMMA; break;
      case '+':  tok = FTS5_PLUS;  break;
      case '*':  tok = FTS5_STAR;  break;
      case '-':  tok = FTS5_MINUS; break;
      case '^':  tok = FTS5_CARET; break;
      case '\0': tok = FTS5_EOF;   break;
  
      case '"': {
        const char *z2;
        tok = FTS5_STRING;
  
        for(z2=&z[1]; 1; z2++){
          if( z2[0]=='"' ){
            z2++;
            if( z2[0]!='"' ) break;
          }
          if( z2[0]=='\0' ){
            sqlite3Fts5ParseError(pParse, "unterminated string");
            return FTS5_EOF;
          }
        }
        pToken->n = (z2 - z);
        break;
      }
  
      default: {
        const char *z2;
        if( sqlite3Fts5IsBareword(z[0])==0 ){
          sqlite3Fts5ParseError(pParse, "fts5: syntax error near \"%.1s\"", z);
          return FTS5_EOF;
        }
        tok = FTS5_STRING;
        for(z2=&z[1]; sqlite3Fts5IsBareword(*z2); z2++);
        pToken->n = (z2 - z);
        if( pToken->n==2 && memcmp(pToken->p, "OR", 2)==0 )  tok = FTS5_OR;
        if( pToken->n==3 && memcmp(pToken->p, "NOT", 3)==0 ) tok = FTS5_NOT;
        if( pToken->n==3 && memcmp(pToken->p, "AND", 3)==0 ) tok = FTS5_AND;
        break;
      }
    }
  
    *pz = &pToken->p[pToken->n];
    return tok;
  }
  
  static void *fts5ParseAlloc(u64 t){ return sqlite3_malloc64((sqlite3_int64)t);}
  static void fts5ParseFree(void *p){ sqlite3_free(p); }
  
  int sqlite3Fts5ExprNew(
    Fts5Config *pConfig,            /* FTS5 Configuration */
    int bPhraseToAnd,
    int iCol,
    const char *zExpr,              /* Expression text */
    Fts5Expr **ppNew, 
    char **pzErr
  ){
    Fts5Parse sParse;
    Fts5Token token;
    const char *z = zExpr;
    int t;                          /* Next token type */
    void *pEngine;
    Fts5Expr *pNew;
  
    *ppNew = 0;
    *pzErr = 0;
    memset(&sParse, 0, sizeof(sParse));
    sParse.bPhraseToAnd = bPhraseToAnd;
    pEngine = sqlite3Fts5ParserAlloc(fts5ParseAlloc);
    if( pEngine==0 ){ return SQLITE_NOMEM; }
    sParse.pConfig = pConfig;
  
    do {
      t = fts5ExprGetToken(&sParse, &z, &token);
      sqlite3Fts5Parser(pEngine, t, token, &sParse);
    }while( sParse.rc==SQLITE_OK && t!=FTS5_EOF );
    sqlite3Fts5ParserFree(pEngine, fts5ParseFree);
  
    /* If the LHS of the MATCH expression was a user column, apply the
    ** implicit column-filter.  */
    if( iCol<pConfig->nCol && sParse.pExpr && sParse.rc==SQLITE_OK ){
      int n = sizeof(Fts5Colset);
      Fts5Colset *pColset = (Fts5Colset*)sqlite3Fts5MallocZero(&sParse.rc, n);
      if( pColset ){
        pColset->nCol = 1;
        pColset->aiCol[0] = iCol;
        sqlite3Fts5ParseSetColset(&sParse, sParse.pExpr, pColset);
      }
    }
  
    assert( sParse.rc!=SQLITE_OK || sParse.zErr==0 );
    if( sParse.rc==SQLITE_OK ){
      *ppNew = pNew = sqlite3_malloc(sizeof(Fts5Expr));
      if( pNew==0 ){
        sParse.rc = SQLITE_NOMEM;
        sqlite3Fts5ParseNodeFree(sParse.pExpr);
      }else{
        if( !sParse.pExpr ){
          const int nByte = sizeof(Fts5ExprNode);
          pNew->pRoot = (Fts5ExprNode*)sqlite3Fts5MallocZero(&sParse.rc, nByte);
          if( pNew->pRoot ){
            pNew->pRoot->bEof = 1;
          }
        }else{
          pNew->pRoot = sParse.pExpr;
        }
        pNew->pIndex = 0;
        pNew->pConfig = pConfig;
        pNew->apExprPhrase = sParse.apPhrase;
        pNew->nPhrase = sParse.nPhrase;
        pNew->bDesc = 0;
        sParse.apPhrase = 0;
      }
    }else{
      sqlite3Fts5ParseNodeFree(sParse.pExpr);
    }
  
    sqlite3_free(sParse.apPhrase);
    *pzErr = sParse.zErr;
    return sParse.rc;
  }
  
  /*
  ** This function is only called when using the special 'trigram' tokenizer.
  ** Argument zText contains the text of a LIKE or GLOB pattern matched
  ** against column iCol. This function creates and compiles an FTS5 MATCH
  ** expression that will match a superset of the rows matched by the LIKE or
  ** GLOB. If successful, SQLITE_OK is returned. Otherwise, an SQLite error
  ** code.
  */
  int sqlite3Fts5ExprPattern(
    Fts5Config *pConfig, int bGlob, int iCol, const char *zText, Fts5Expr **pp
  ){
    i64 nText = strlen(zText);
    char *zExpr = (char*)sqlite3_malloc64(nText*4 + 1);
    int rc = SQLITE_OK;
  
    if( zExpr==0 ){
      rc = SQLITE_NOMEM;
    }else{
      char aSpec[3];
      int iOut = 0;
      int i = 0;
      int iFirst = 0;
  
      if( bGlob==0 ){
        aSpec[0] = '_';
        aSpec[1] = '%';
        aSpec[2] = 0;
      }else{
        aSpec[0] = '*';
        aSpec[1] = '?';
        aSpec[2] = '[';
      }
  
      while( i<=nText ){
        if( i==nText 
         || zText[i]==aSpec[0] || zText[i]==aSpec[1] || zText[i]==aSpec[2] 
        ){
          if( i-iFirst>=3 ){
            int jj;
            zExpr[iOut++] = '"';
            for(jj=iFirst; jj<i; jj++){
              zExpr[iOut++] = zText[jj];
              if( zText[jj]=='"' ) zExpr[iOut++] = '"';
            }
            zExpr[iOut++] = '"';
            zExpr[iOut++] = ' ';
          }
          if( zText[i]==aSpec[2] ){
            i += 2;
            if( zText[i-1]=='^' ) i++;
            while( i<nText && zText[i]!=']' ) i++;
          }
          iFirst = i+1;
        }
        i++;
      }
      if( iOut>0 ){
        int bAnd = 0;
        if( pConfig->eDetail!=FTS5_DETAIL_FULL ){
          bAnd = 1;
          if( pConfig->eDetail==FTS5_DETAIL_NONE ){
            iCol = pConfig->nCol;
          }
        }
        zExpr[iOut] = '\0';
        rc = sqlite3Fts5ExprNew(pConfig, bAnd, iCol, zExpr, pp,pConfig->pzErrmsg);
      }else{
        *pp = 0;
      }
      sqlite3_free(zExpr);
    }
  
    return rc;
  }
  
  /*
  ** Free the expression node object passed as the only argument.
  */
  void sqlite3Fts5ParseNodeFree(Fts5ExprNode *p){
    if( p ){
      int i;
      for(i=0; i<p->nChild; i++){
        sqlite3Fts5ParseNodeFree(p->apChild[i]);
      }
      sqlite3Fts5ParseNearsetFree(p->pNear);
      sqlite3_free(p);
    }
  }
  
  /*
  ** Free the expression object passed as the only argument.
  */
  void sqlite3Fts5ExprFree(Fts5Expr *p){
    if( p ){
      sqlite3Fts5ParseNodeFree(p->pRoot);
      sqlite3_free(p->apExprPhrase);
      sqlite3_free(p);
    }
  }
  
  int sqlite3Fts5ExprAnd(Fts5Expr **pp1, Fts5Expr *p2){
    Fts5Parse sParse;
    memset(&sParse, 0, sizeof(sParse));
  
    if( *pp1 ){
      Fts5Expr *p1 = *pp1;
      int nPhrase = p1->nPhrase + p2->nPhrase;
  
      p1->pRoot = sqlite3Fts5ParseNode(&sParse, FTS5_AND, p1->pRoot, p2->pRoot,0);
      p2->pRoot = 0;
  
      if( sParse.rc==SQLITE_OK ){
        Fts5ExprPhrase **ap = (Fts5ExprPhrase**)sqlite3_realloc(
            p1->apExprPhrase, nPhrase * sizeof(Fts5ExprPhrase*)
        );
        if( ap==0 ){
          sParse.rc = SQLITE_NOMEM;
        }else{
          int i;
          memmove(&ap[p2->nPhrase], ap, p1->nPhrase*sizeof(Fts5ExprPhrase*));
          for(i=0; i<p2->nPhrase; i++){
            ap[i] = p2->apExprPhrase[i];
          }
          p1->nPhrase = nPhrase;
          p1->apExprPhrase = ap;
        }
      }
      sqlite3_free(p2->apExprPhrase);
      sqlite3_free(p2);
    }else{
      *pp1 = p2;
    }
  
    return sParse.rc;
  }
  
  /*
  ** Argument pTerm must be a synonym iterator. Return the current rowid
  ** that it points to.
  */
  static i64 fts5ExprSynonymRowid(Fts5ExprTerm *pTerm, int bDesc, int *pbEof){
    i64 iRet = 0;
    int bRetValid = 0;
    Fts5ExprTerm *p;
  
    assert( pTerm->pSynonym );
    assert( bDesc==0 || bDesc==1 );
    for(p=pTerm; p; p=p->pSynonym){
      if( 0==sqlite3Fts5IterEof(p->pIter) ){
        i64 iRowid = p->pIter->iRowid;
        if( bRetValid==0 || (bDesc!=(iRowid<iRet)) ){
          iRet = iRowid;
          bRetValid = 1;
        }
      }
    }
  
    if( pbEof && bRetValid==0 ) *pbEof = 1;
    return iRet;
  }
  
  /*
  ** Argument pTerm must be a synonym iterator.
  */
  static int fts5ExprSynonymList(
    Fts5ExprTerm *pTerm, 
    i64 iRowid,
    Fts5Buffer *pBuf,               /* Use this buffer for space if required */
    u8 **pa, int *pn
  ){
    Fts5PoslistReader aStatic[4];
    Fts5PoslistReader *aIter = aStatic;
    int nIter = 0;
    int nAlloc = 4;
    int rc = SQLITE_OK;
    Fts5ExprTerm *p;
  
    assert( pTerm->pSynonym );
    for(p=pTerm; p; p=p->pSynonym){
      Fts5IndexIter *pIter = p->pIter;
      if( sqlite3Fts5IterEof(pIter)==0 && pIter->iRowid==iRowid ){
        if( pIter->nData==0 ) continue;
        if( nIter==nAlloc ){
          sqlite3_int64 nByte = sizeof(Fts5PoslistReader) * nAlloc * 2;
          Fts5PoslistReader *aNew = (Fts5PoslistReader*)sqlite3_malloc64(nByte);
          if( aNew==0 ){
            rc = SQLITE_NOMEM;
            goto synonym_poslist_out;
          }
          memcpy(aNew, aIter, sizeof(Fts5PoslistReader) * nIter);
          nAlloc = nAlloc*2;
          if( aIter!=aStatic ) sqlite3_free(aIter);
          aIter = aNew;
        }
        sqlite3Fts5PoslistReaderInit(pIter->pData, pIter->nData, &aIter[nIter]);
        assert( aIter[nIter].bEof==0 );
        nIter++;
      }
    }
  
    if( nIter==1 ){
      *pa = (u8*)aIter[0].a;
      *pn = aIter[0].n;
    }else{
      Fts5PoslistWriter writer = {0};
      i64 iPrev = -1;
      fts5BufferZero(pBuf);
      while( 1 ){
        int i;
        i64 iMin = FTS5_LARGEST_INT64;
        for(i=0; i<nIter; i++){
          if( aIter[i].bEof==0 ){
            if( aIter[i].iPos==iPrev ){
              if( sqlite3Fts5PoslistReaderNext(&aIter[i]) ) continue;
            }
            if( aIter[i].iPos<iMin ){
              iMin = aIter[i].iPos;
            }
          }
        }
        if( iMin==FTS5_LARGEST_INT64 || rc!=SQLITE_OK ) break;
        rc = sqlite3Fts5PoslistWriterAppend(pBuf, &writer, iMin);
        iPrev = iMin;
      }
      if( rc==SQLITE_OK ){
        *pa = pBuf->p;
        *pn = pBuf->n;
      }
    }
  
   synonym_poslist_out:
    if( aIter!=aStatic ) sqlite3_free(aIter);
    return rc;
  }
  
  
  /*
  ** All individual term iterators in pPhrase are guaranteed to be valid and
  ** pointing to the same rowid when this function is called. This function 
  ** checks if the current rowid really is a match, and if so populates
  ** the pPhrase->poslist buffer accordingly. Output parameter *pbMatch
  ** is set to true if this is really a match, or false otherwise.
  **
  ** SQLITE_OK is returned if an error occurs, or an SQLite error code 
  ** otherwise. It is not considered an error code if the current rowid is 
  ** not a match.
  */
  static int fts5ExprPhraseIsMatch(
    Fts5ExprNode *pNode,            /* Node pPhrase belongs to */
    Fts5ExprPhrase *pPhrase,        /* Phrase object to initialize */
    int *pbMatch                    /* OUT: Set to true if really a match */
  ){
    Fts5PoslistWriter writer = {0};
    Fts5PoslistReader aStatic[4];
    Fts5PoslistReader *aIter = aStatic;
    int i;
    int rc = SQLITE_OK;
    int bFirst = pPhrase->aTerm[0].bFirst;
    
    fts5BufferZero(&pPhrase->poslist);
  
    /* If the aStatic[] array is not large enough, allocate a large array
    ** using sqlite3_malloc(). This approach could be improved upon. */
    if( pPhrase->nTerm>ArraySize(aStatic) ){
      sqlite3_int64 nByte = sizeof(Fts5PoslistReader) * pPhrase->nTerm;
      aIter = (Fts5PoslistReader*)sqlite3_malloc64(nByte);
      if( !aIter ) return SQLITE_NOMEM;
    }
    memset(aIter, 0, sizeof(Fts5PoslistReader) * pPhrase->nTerm);
  
    /* Initialize a term iterator for each term in the phrase */
    for(i=0; i<pPhrase->nTerm; i++){
      Fts5ExprTerm *pTerm = &pPhrase->aTerm[i];
      int n = 0;
      int bFlag = 0;
      u8 *a = 0;
      if( pTerm->pSynonym ){
        Fts5Buffer buf = {0, 0, 0};
        rc = fts5ExprSynonymList(pTerm, pNode->iRowid, &buf, &a, &n);
        if( rc ){
          sqlite3_free(a);
          goto ismatch_out;
        }
        if( a==buf.p ) bFlag = 1;
      }else{
        a = (u8*)pTerm->pIter->pData;
        n = pTerm->pIter->nData;
      }
      sqlite3Fts5PoslistReaderInit(a, n, &aIter[i]);
      aIter[i].bFlag = (u8)bFlag;
      if( aIter[i].bEof ) goto ismatch_out;
    }
  
    while( 1 ){
      int bMatch;
      i64 iPos = aIter[0].iPos;
      do {
        bMatch = 1;
        for(i=0; i<pPhrase->nTerm; i++){
          Fts5PoslistReader *pPos = &aIter[i];
          i64 iAdj = iPos + i;
          if( pPos->iPos!=iAdj ){
            bMatch = 0;
            while( pPos->iPos<iAdj ){
              if( sqlite3Fts5PoslistReaderNext(pPos) ) goto ismatch_out;
            }
            if( pPos->iPos>iAdj ) iPos = pPos->iPos-i;
          }
        }
      }while( bMatch==0 );
  
      /* Append position iPos to the output */
      if( bFirst==0 || FTS5_POS2OFFSET(iPos)==0 ){
        rc = sqlite3Fts5PoslistWriterAppend(&pPhrase->poslist, &writer, iPos);
        if( rc!=SQLITE_OK ) goto ismatch_out;
      }
  
      for(i=0; i<pPhrase->nTerm; i++){
        if( sqlite3Fts5PoslistReaderNext(&aIter[i]) ) goto ismatch_out;
      }
    }
  
   ismatch_out:
    *pbMatch = (pPhrase->poslist.n>0);
    for(i=0; i<pPhrase->nTerm; i++){
      if( aIter[i].bFlag ) sqlite3_free((u8*)aIter[i].a);
    }
    if( aIter!=aStatic ) sqlite3_free(aIter);
    return rc;
  }
  
  typedef struct Fts5LookaheadReader Fts5LookaheadReader;
  struct Fts5LookaheadReader {
    const u8 *a;                    /* Buffer containing position list */
    int n;                          /* Size of buffer a[] in bytes */
    int i;                          /* Current offset in position list */
    i64 iPos;                       /* Current position */
    i64 iLookahead;                 /* Next position */
  };
  
  #define FTS5_LOOKAHEAD_EOF (((i64)1) << 62)
  
  static int fts5LookaheadReaderNext(Fts5LookaheadReader *p){
    p->iPos = p->iLookahead;
    if( sqlite3Fts5PoslistNext64(p->a, p->n, &p->i, &p->iLookahead) ){
      p->iLookahead = FTS5_LOOKAHEAD_EOF;
    }
    return (p->iPos==FTS5_LOOKAHEAD_EOF);
  }
  
  static int fts5LookaheadReaderInit(
    const u8 *a, int n,             /* Buffer to read position list from */
    Fts5LookaheadReader *p          /* Iterator object to initialize */
  ){
    memset(p, 0, sizeof(Fts5LookaheadReader));
    p->a = a;
    p->n = n;
    fts5LookaheadReaderNext(p);
    return fts5LookaheadReaderNext(p);
  }
  
  typedef struct Fts5NearTrimmer Fts5NearTrimmer;
  struct Fts5NearTrimmer {
    Fts5LookaheadReader reader;     /* Input iterator */
    Fts5PoslistWriter writer;       /* Writer context */
    Fts5Buffer *pOut;               /* Output poslist */
  };
  
  /*
  ** The near-set object passed as the first argument contains more than
  ** one phrase. All phrases currently point to the same row. The
  ** Fts5ExprPhrase.poslist buffers are populated accordingly. This function
  ** tests if the current row contains instances of each phrase sufficiently
  ** close together to meet the NEAR constraint. Non-zero is returned if it
  ** does, or zero otherwise.
  **
  ** If in/out parameter (*pRc) is set to other than SQLITE_OK when this
  ** function is called, it is a no-op. Or, if an error (e.g. SQLITE_NOMEM)
  ** occurs within this function (*pRc) is set accordingly before returning.
  ** The return value is undefined in both these cases.
  ** 
  ** If no error occurs and non-zero (a match) is returned, the position-list
  ** of each phrase object is edited to contain only those entries that
  ** meet the constraint before returning.
  */
  static int fts5ExprNearIsMatch(int *pRc, Fts5ExprNearset *pNear){
    Fts5NearTrimmer aStatic[4];
    Fts5NearTrimmer *a = aStatic;
    Fts5ExprPhrase **apPhrase = pNear->apPhrase;
  
    int i;
    int rc = *pRc;
    int bMatch;
  
    assert( pNear->nPhrase>1 );
  
    /* If the aStatic[] array is not large enough, allocate a large array
    ** using sqlite3_malloc(). This approach could be improved upon. */
    if( pNear->nPhrase>ArraySize(aStatic) ){
      sqlite3_int64 nByte = sizeof(Fts5NearTrimmer) * pNear->nPhrase;
      a = (Fts5NearTrimmer*)sqlite3Fts5MallocZero(&rc, nByte);
    }else{
      memset(aStatic, 0, sizeof(aStatic));
    }
    if( rc!=SQLITE_OK ){
      *pRc = rc;
      return 0;
    }
  
    /* Initialize a lookahead iterator for each phrase. After passing the
    ** buffer and buffer size to the lookaside-reader init function, zero
    ** the phrase poslist buffer. The new poslist for the phrase (containing
    ** the same entries as the original with some entries removed on account 
    ** of the NEAR constraint) is written over the original even as it is
    ** being read. This is safe as the entries for the new poslist are a
    ** subset of the old, so it is not possible for data yet to be read to
    ** be overwritten.  */
    for(i=0; i<pNear->nPhrase; i++){
      Fts5Buffer *pPoslist = &apPhrase[i]->poslist;
      fts5LookaheadReaderInit(pPoslist->p, pPoslist->n, &a[i].reader);
      pPoslist->n = 0;
      a[i].pOut = pPoslist;
    }
  
    while( 1 ){
      int iAdv;
      i64 iMin;
      i64 iMax;
  
      /* This block advances the phrase iterators until they point to a set of
      ** entries that together comprise a match.  */
      iMax = a[0].reader.iPos;
      do {
        bMatch = 1;
        for(i=0; i<pNear->nPhrase; i++){
          Fts5LookaheadReader *pPos = &a[i].reader;
          iMin = iMax - pNear->apPhrase[i]->nTerm - pNear->nNear;
          if( pPos->iPos<iMin || pPos->iPos>iMax ){
            bMatch = 0;
            while( pPos->iPos<iMin ){
              if( fts5LookaheadReaderNext(pPos) ) goto ismatch_out;
            }
            if( pPos->iPos>iMax ) iMax = pPos->iPos;
          }
        }
      }while( bMatch==0 );
  
      /* Add an entry to each output position list */
      for(i=0; i<pNear->nPhrase; i++){
        i64 iPos = a[i].reader.iPos;
        Fts5PoslistWriter *pWriter = &a[i].writer;
        if( a[i].pOut->n==0 || iPos!=pWriter->iPrev ){
          sqlite3Fts5PoslistWriterAppend(a[i].pOut, pWriter, iPos);
        }
      }
  
      iAdv = 0;
      iMin = a[0].reader.iLookahead;
      for(i=0; i<pNear->nPhrase; i++){
        if( a[i].reader.iLookahead < iMin ){
          iMin = a[i].reader.iLookahead;
          iAdv = i;
        }
      }
      if( fts5LookaheadReaderNext(&a[iAdv].reader) ) goto ismatch_out;
    }
  
    ismatch_out: {
      int bRet = a[0].pOut->n>0;
      *pRc = rc;
      if( a!=aStatic ) sqlite3_free(a);
      return bRet;
    }
  }
  
  /*
  ** Advance iterator pIter until it points to a value equal to or laster
  ** than the initial value of *piLast. If this means the iterator points
  ** to a value laster than *piLast, update *piLast to the new lastest value.
  **
  ** If the iterator reaches EOF, set *pbEof to true before returning. If
  ** an error occurs, set *pRc to an error code. If either *pbEof or *pRc
  ** are set, return a non-zero value. Otherwise, return zero.
  */
  static int fts5ExprAdvanceto(
    Fts5IndexIter *pIter,           /* Iterator to advance */
    int bDesc,                      /* True if iterator is "rowid DESC" */
    i64 *piLast,                    /* IN/OUT: Lastest rowid seen so far */
    int *pRc,                       /* OUT: Error code */
    int *pbEof                      /* OUT: Set to true if EOF */
  ){
    i64 iLast = *piLast;
    i64 iRowid;
  
    iRowid = pIter->iRowid;
    if( (bDesc==0 && iLast>iRowid) || (bDesc && iLast<iRowid) ){
      int rc = sqlite3Fts5IterNextFrom(pIter, iLast);
      if( rc || sqlite3Fts5IterEof(pIter) ){
        *pRc = rc;
        *pbEof = 1;
        return 1;
      }
      iRowid = pIter->iRowid;
      assert( (bDesc==0 && iRowid>=iLast) || (bDesc==1 && iRowid<=iLast) );
    }
    *piLast = iRowid;
  
    return 0;
  }
  
  static int fts5ExprSynonymAdvanceto(
    Fts5ExprTerm *pTerm,            /* Term iterator to advance */
    int bDesc,                      /* True if iterator is "rowid DESC" */
    i64 *piLast,                    /* IN/OUT: Lastest rowid seen so far */
    int *pRc                        /* OUT: Error code */
  ){
    int rc = SQLITE_OK;
    i64 iLast = *piLast;
    Fts5ExprTerm *p;
    int bEof = 0;
  
    for(p=pTerm; rc==SQLITE_OK && p; p=p->pSynonym){
      if( sqlite3Fts5IterEof(p->pIter)==0 ){
        i64 iRowid = p->pIter->iRowid;
        if( (bDesc==0 && iLast>iRowid) || (bDesc && iLast<iRowid) ){
          rc = sqlite3Fts5IterNextFrom(p->pIter, iLast);
        }
      }
    }
  
    if( rc!=SQLITE_OK ){
      *pRc = rc;
      bEof = 1;
    }else{
      *piLast = fts5ExprSynonymRowid(pTerm, bDesc, &bEof);
    }
    return bEof;
  }
  
  
  static int fts5ExprNearTest(
    int *pRc,
    Fts5Expr *pExpr,                /* Expression that pNear is a part of */
    Fts5ExprNode *pNode             /* The "NEAR" node (FTS5_STRING) */
  ){
    Fts5ExprNearset *pNear = pNode->pNear;
    int rc = *pRc;
  
    if( pExpr->pConfig->eDetail!=FTS5_DETAIL_FULL ){
      Fts5ExprTerm *pTerm;
      Fts5ExprPhrase *pPhrase = pNear->apPhrase[0];
      pPhrase->poslist.n = 0;
      for(pTerm=&pPhrase->aTerm[0]; pTerm; pTerm=pTerm->pSynonym){
        Fts5IndexIter *pIter = pTerm->pIter;
        if( sqlite3Fts5IterEof(pIter)==0 ){
          if( pIter->iRowid==pNode->iRowid && pIter->nData>0 ){
            pPhrase->poslist.n = 1;
          }
        }
      }
      return pPhrase->poslist.n;
    }else{
      int i;
  
      /* 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( pPhrase->nTerm>1 || pPhrase->aTerm[0].pSynonym 
         || pNear->pColset || pPhrase->aTerm[0].bFirst
        ){
          int bMatch = 0;
          rc = fts5ExprPhraseIsMatch(pNode, pPhrase, &bMatch);
          if( bMatch==0 ) break;
        }else{
          Fts5IndexIter *pIter = pPhrase->aTerm[0].pIter;
          fts5BufferSet(&rc, &pPhrase->poslist, pIter->nData, pIter->pData);
        }
      }
  
      *pRc = rc;
      if( i==pNear->nPhrase && (i==1 || fts5ExprNearIsMatch(pRc, pNear)) ){
        return 1;
      }
      return 0;
    }
  }
  
  
  /*
  ** Initialize all term iterators in the pNear object. If any term is found
  ** to match no documents at all, return immediately without initializing any
  ** further iterators.
  **
  ** If an error occurs, return an SQLite error code. Otherwise, return
  ** SQLITE_OK. It is not considered an error if some term matches zero
  ** documents.
  */
  static int fts5ExprNearInitAll(
    Fts5Expr *pExpr,
    Fts5ExprNode *pNode
  ){
    Fts5ExprNearset *pNear = pNode->pNear;
    int i;
  
    assert( pNode->bNomatch==0 );
    for(i=0; i<pNear->nPhrase; i++){
      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
      if( pPhrase->nTerm==0 ){
        pNode->bEof = 1;
        return SQLITE_OK;
      }else{
        int j;
        for(j=0; j<pPhrase->nTerm; j++){
          Fts5ExprTerm *pTerm = &pPhrase->aTerm[j];
          Fts5ExprTerm *p;
          int bHit = 0;
  
          for(p=pTerm; p; p=p->pSynonym){
            int rc;
            if( p->pIter ){
              sqlite3Fts5IterClose(p->pIter);
              p->pIter = 0;
            }
            rc = sqlite3Fts5IndexQuery(
                pExpr->pIndex, p->zTerm, (int)strlen(p->zTerm),
                (pTerm->bPrefix ? FTS5INDEX_QUERY_PREFIX : 0) |
                (pExpr->bDesc ? FTS5INDEX_QUERY_DESC : 0),
                pNear->pColset,
                &p->pIter
            );
            assert( (rc==SQLITE_OK)==(p->pIter!=0) );
            if( rc!=SQLITE_OK ) return rc;
            if( 0==sqlite3Fts5IterEof(p->pIter) ){
              bHit = 1;
            }
          }
  
          if( bHit==0 ){
            pNode->bEof = 1;
            return SQLITE_OK;
          }
        }
      }
    }
  
    pNode->bEof = 0;
    return SQLITE_OK;
  }
  
  /*
  ** If pExpr is an ASC iterator, this function returns a value with the
  ** same sign as:
  **
  **   (iLhs - iRhs)
  **
  ** Otherwise, if this is a DESC iterator, the opposite is returned:
  **
  **   (iRhs - iLhs)
  */
  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);
    }
  }
  
  static void fts5ExprSetEof(Fts5ExprNode *pNode){
    int i;
    pNode->bEof = 1;
    pNode->bNomatch = 0;
    for(i=0; i<pNode->nChild; i++){
      fts5ExprSetEof(pNode->apChild[i]);
    }
  }
  
  static void fts5ExprNodeZeroPoslist(Fts5ExprNode *pNode){
    if( pNode->eType==FTS5_STRING || pNode->eType==FTS5_TERM ){
      Fts5ExprNearset *pNear = pNode->pNear;
      int i;
      for(i=0; i<pNear->nPhrase; i++){
        Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
        pPhrase->poslist.n = 0;
      }
    }else{
      int i;
      for(i=0; i<pNode->nChild; i++){
        fts5ExprNodeZeroPoslist(pNode->apChild[i]);
      }
    }
  }
  
  
  
  /*
  ** 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;
    return fts5RowidCmp(pExpr, p1->iRowid, p2->iRowid);
  }
  
  /*
  ** 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 fts5ExprNodeTest_STRING(
    Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
    Fts5ExprNode *pNode
  ){
    Fts5ExprNearset *pNear = pNode->pNear;
    Fts5ExprPhrase *pLeft = pNear->apPhrase[0];
    int rc = SQLITE_OK;
    i64 iLast;                      /* Lastest rowid any iterator points to */
    int i, j;                       /* Phrase and token index, respectively */
    int bMatch;                     /* True if all terms are at the same rowid */
    const int bDesc = pExpr->bDesc;
  
    /* Check that this node should not be FTS5_TERM */
    assert( pNear->nPhrase>1 
         || pNear->apPhrase[0]->nTerm>1 
         || pNear->apPhrase[0]->aTerm[0].pSynonym
         || pNear->apPhrase[0]->aTerm[0].bFirst
    );
  
    /* 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.  */
    if( pLeft->aTerm[0].pSynonym ){
      iLast = fts5ExprSynonymRowid(&pLeft->aTerm[0], bDesc, 0);
    }else{
      iLast = pLeft->aTerm[0].pIter->iRowid;
    }
  
    do {
      bMatch = 1;
      for(i=0; i<pNear->nPhrase; i++){
        Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
        for(j=0; j<pPhrase->nTerm; j++){
          Fts5ExprTerm *pTerm = &pPhrase->aTerm[j];
          if( pTerm->pSynonym ){
            i64 iRowid = fts5ExprSynonymRowid(pTerm, bDesc, 0);
            if( iRowid==iLast ) continue;
            bMatch = 0;
            if( fts5ExprSynonymAdvanceto(pTerm, bDesc, &iLast, &rc) ){
              pNode->bNomatch = 0;
              pNode->bEof = 1;
              return rc;
            }
          }else{
            Fts5IndexIter *pIter = pPhrase->aTerm[j].pIter;
            if( pIter->iRowid==iLast || pIter->bEof ) continue;
            bMatch = 0;
            if( fts5ExprAdvanceto(pIter, bDesc, &iLast, &rc, &pNode->bEof) ){
              return rc;
            }
          }
        }
      }
    }while( bMatch==0 );
  
    pNode->iRowid = iLast;
    pNode->bNomatch = ((0==fts5ExprNearTest(&rc, pExpr, pNode)) && rc==SQLITE_OK);
    assert( pNode->bEof==0 || pNode->bNomatch==0 );
  
    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 fts5ExprNodeNext_STRING(
    Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
    Fts5ExprNode *pNode,            /* FTS5_STRING or FTS5_TERM node */
    int bFromValid,
    i64 iFrom 
  ){
    Fts5ExprTerm *pTerm = &pNode->pNear->apPhrase[0]->aTerm[0];
    int rc = SQLITE_OK;
  
    pNode->bNomatch = 0;
    if( pTerm->pSynonym ){
      int bEof = 1;
      Fts5ExprTerm *p;
  
      /* Find the firstest rowid any synonym points to. */
      i64 iRowid = fts5ExprSynonymRowid(pTerm, pExpr->bDesc, 0);
  
      /* Advance each iterator that currently points to iRowid. Or, if iFrom
      ** is valid - each iterator that points to a rowid before iFrom.  */
      for(p=pTerm; p; p=p->pSynonym){
        if( sqlite3Fts5IterEof(p->pIter)==0 ){
          i64 ii = p->pIter->iRowid;
          if( ii==iRowid 
           || (bFromValid && ii!=iFrom && (ii>iFrom)==pExpr->bDesc) 
          ){
            if( bFromValid ){
              rc = sqlite3Fts5IterNextFrom(p->pIter, iFrom);
            }else{
              rc = sqlite3Fts5IterNext(p->pIter);
            }
            if( rc!=SQLITE_OK ) break;
            if( sqlite3Fts5IterEof(p->pIter)==0 ){
              bEof = 0;
            }
          }else{
            bEof = 0;
          }
        }
      }
  
      /* Set the EOF flag if either all synonym iterators are at EOF or an
      ** error has occurred.  */
      pNode->bEof = (rc || bEof);
    }else{
      Fts5IndexIter *pIter = pTerm->pIter;
  
      assert( Fts5NodeIsString(pNode) );
      if( bFromValid ){
        rc = sqlite3Fts5IterNextFrom(pIter, iFrom);
      }else{
        rc = sqlite3Fts5IterNext(pIter);
      }
  
      pNode->bEof = (rc || sqlite3Fts5IterEof(pIter));
    }
  
    if( pNode->bEof==0 ){
      assert( rc==SQLITE_OK );
      rc = fts5ExprNodeTest_STRING(pExpr, pNode);
    }
  
    return rc;
  }
  
  
  static int fts5ExprNodeTest_TERM(
    Fts5Expr *pExpr,                /* Expression that pNear is a part of */
    Fts5ExprNode *pNode             /* The "NEAR" node (FTS5_TERM) */
  ){
    /* As this "NEAR" object is actually a single phrase that consists 
    ** of a single term only, grab pointers into the poslist managed by the
    ** fts5_index.c iterator object. This is much faster than synthesizing 
    ** a new poslist the way we have to for more complicated phrase or NEAR
    ** expressions.  */
    Fts5ExprPhrase *pPhrase = pNode->pNear->apPhrase[0];
    Fts5IndexIter *pIter = pPhrase->aTerm[0].pIter;
  
    assert( pNode->eType==FTS5_TERM );
    assert( pNode->pNear->nPhrase==1 && pPhrase->nTerm==1 );
    assert( pPhrase->aTerm[0].pSynonym==0 );
  
    pPhrase->poslist.n = pIter->nData;
    if( pExpr->pConfig->eDetail==FTS5_DETAIL_FULL ){
      pPhrase->poslist.p = (u8*)pIter->pData;
    }
    pNode->iRowid = pIter->iRowid;
    pNode->bNomatch = (pPhrase->poslist.n==0);
    return SQLITE_OK;
  }
  
  /*
  ** xNext() method for a node of type FTS5_TERM.
  */
  static int fts5ExprNodeNext_TERM(
    Fts5Expr *pExpr, 
    Fts5ExprNode *pNode,
    int bFromValid,
    i64 iFrom
  ){
    int rc;
    Fts5IndexIter *pIter = pNode->pNear->apPhrase[0]->aTerm[0].pIter;
  
    assert( pNode->bEof==0 );
    if( bFromValid ){
      rc = sqlite3Fts5IterNextFrom(pIter, iFrom);
    }else{
      rc = sqlite3Fts5IterNext(pIter);
    }
    if( rc==SQLITE_OK && sqlite3Fts5IterEof(pIter)==0 ){
      rc = fts5ExprNodeTest_TERM(pExpr, pNode);
    }else{
      pNode->bEof = 1;
      pNode->bNomatch = 0;
    }
    return rc;
  }
  
  static void fts5ExprNodeTest_OR(
    Fts5Expr *pExpr,                /* Expression of which pNode is a part */
    Fts5ExprNode *pNode             /* Expression node to test */
  ){
    Fts5ExprNode *pNext = pNode->apChild[0];
    int i;
  
    for(i=1; i<pNode->nChild; i++){
      Fts5ExprNode *pChild = pNode->apChild[i];
      int cmp = fts5NodeCompare(pExpr, pNext, pChild);
      if( cmp>0 || (cmp==0 && pChild->bNomatch==0) ){
        pNext = pChild;
      }
    }
    pNode->iRowid = pNext->iRowid;
    pNode->bEof = pNext->bEof;
    pNode->bNomatch = pNext->bNomatch;
  }
  
  static int fts5ExprNodeNext_OR(
    Fts5Expr *pExpr, 
    Fts5ExprNode *pNode,
    int bFromValid,
    i64 iFrom
  ){
    int i;
    i64 iLast = pNode->iRowid;
  
    for(i=0; i<pNode->nChild; i++){
      Fts5ExprNode *p1 = pNode->apChild[i];
      assert( p1->bEof || fts5RowidCmp(pExpr, p1->iRowid, iLast)>=0 );
      if( p1->bEof==0 ){
        if( (p1->iRowid==iLast) 
         || (bFromValid && fts5RowidCmp(pExpr, p1->iRowid, iFrom)<0)
        ){
          int rc = fts5ExprNodeNext(pExpr, p1, bFromValid, iFrom);
          if( rc!=SQLITE_OK ){
            pNode->bNomatch = 0;
            return rc;
          }
        }
      }
    }
  
    fts5ExprNodeTest_OR(pExpr, pNode);
    return SQLITE_OK;
  }
  
  /*
  ** Argument pNode is an FTS5_AND node.
  */
  static int fts5ExprNodeTest_AND(
    Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
    Fts5ExprNode *pAnd              /* FTS5_AND node to advance */
  ){
    int iChild;
    i64 iLast = pAnd->iRowid;
    int rc = SQLITE_OK;
    int bMatch;
  
    assert( pAnd->bEof==0 );
    do {
      pAnd->bNomatch = 0;
      bMatch = 1;
      for(iChild=0; iChild<pAnd->nChild; iChild++){
        Fts5ExprNode *pChild = pAnd->apChild[iChild];
        int cmp = fts5RowidCmp(pExpr, iLast, pChild->iRowid);
        if( cmp>0 ){
          /* Advance pChild until it points to iLast or laster */
          rc = fts5ExprNodeNext(pExpr, pChild, 1, iLast);
          if( rc!=SQLITE_OK ){
            pAnd->bNomatch = 0;
            return rc;
          }
        }
  
        /* If the child node is now at EOF, so is the parent AND node. Otherwise,
        ** the child node is guaranteed to have advanced at least as far as
        ** rowid iLast. So if it is not at exactly iLast, pChild->iRowid is the
        ** new lastest rowid seen so far.  */
        assert( pChild->bEof || fts5RowidCmp(pExpr, iLast, pChild->iRowid)<=0 );
        if( pChild->bEof ){
          fts5ExprSetEof(pAnd);
          bMatch = 1;
          break;
        }else if( iLast!=pChild->iRowid ){
          bMatch = 0;
          iLast = pChild->iRowid;
        }
  
        if( pChild->bNomatch ){
          pAnd->bNomatch = 1;
        }
      }
    }while( bMatch==0 );
  
    if( pAnd->bNomatch && pAnd!=pExpr->pRoot ){
      fts5ExprNodeZeroPoslist(pAnd);
    }
    pAnd->iRowid = iLast;
    return SQLITE_OK;
  }
  
  static int fts5ExprNodeNext_AND(
    Fts5Expr *pExpr, 
    Fts5ExprNode *pNode,
    int bFromValid,
    i64 iFrom
  ){
    int rc = fts5ExprNodeNext(pExpr, pNode->apChild[0], bFromValid, iFrom);
    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeTest_AND(pExpr, pNode);
    }else{
      pNode->bNomatch = 0;
    }
    return rc;
  }
  
  static int fts5ExprNodeTest_NOT(
    Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
    Fts5ExprNode *pNode             /* FTS5_NOT node to advance */
  ){
    int rc = SQLITE_OK;
    Fts5ExprNode *p1 = pNode->apChild[0];
    Fts5ExprNode *p2 = pNode->apChild[1];
    assert( pNode->nChild==2 );
  
    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( cmp || p2->bNomatch ) break;
      rc = fts5ExprNodeNext(pExpr, p1, 0, 0);
    }
    pNode->bEof = p1->bEof;
    pNode->bNomatch = p1->bNomatch;
    pNode->iRowid = p1->iRowid;
    if( p1->bEof ){
      fts5ExprNodeZeroPoslist(p2);
    }
    return rc;
  }
  
  static int fts5ExprNodeNext_NOT(
    Fts5Expr *pExpr, 
    Fts5ExprNode *pNode,
    int bFromValid,
    i64 iFrom
  ){
    int rc = fts5ExprNodeNext(pExpr, pNode->apChild[0], bFromValid, iFrom);
    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeTest_NOT(pExpr, pNode);
    }
    if( rc!=SQLITE_OK ){
      pNode->bNomatch = 0;
    }
    return rc;
  }
  
  /*
  ** 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 fts5ExprNodeTest(
    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 = fts5ExprNodeTest_STRING(pExpr, pNode);
          break;
        }
  
        case FTS5_TERM: {
          rc = fts5ExprNodeTest_TERM(pExpr, pNode);
          break;
        }
  
        case FTS5_AND: {
          rc = fts5ExprNodeTest_AND(pExpr, pNode);
          break;
        }
  
        case FTS5_OR: {
          fts5ExprNodeTest_OR(pExpr, pNode);
          break;
        }
  
        default: assert( pNode->eType==FTS5_NOT ); {
          rc = fts5ExprNodeTest_NOT(pExpr, pNode);
          break;
        }
      }
    }
    return rc;
  }
  
   
  /*
  ** Set node pNode, which is part of expression pExpr, to point to the first
  ** match. If there are no matches, set the Node.bEof flag to indicate EOF.
  **
  ** Return an SQLite error code if an error occurs, or SQLITE_OK otherwise.
  ** It is not an error if there are no matches.
  */
  static int fts5ExprNodeFirst(Fts5Expr *pExpr, Fts5ExprNode *pNode){
    int rc = SQLITE_OK;
    pNode->bEof = 0;
    pNode->bNomatch = 0;
  
    if( Fts5NodeIsString(pNode) ){
      /* Initialize all term iterators in the NEAR object. */
      rc = fts5ExprNearInitAll(pExpr, pNode);
    }else if( pNode->xNext==0 ){
      pNode->bEof = 1;
    }else{
      int i;
      int nEof = 0;
      for(i=0; i<pNode->nChild && rc==SQLITE_OK; i++){
        Fts5ExprNode *pChild = pNode->apChild[i];
        rc = fts5ExprNodeFirst(pExpr, pNode->apChild[i]);
        assert( pChild->bEof==0 || pChild->bEof==1 );
        nEof += pChild->bEof;
      }
      pNode->iRowid = pNode->apChild[0]->iRowid;
  
      switch( pNode->eType ){
        case FTS5_AND:
          if( nEof>0 ) fts5ExprSetEof(pNode);
          break;
  
        case FTS5_OR:
          if( pNode->nChild==nEof ) fts5ExprSetEof(pNode);
          break;
  
        default:
          assert( pNode->eType==FTS5_NOT );
          pNode->bEof = pNode->apChild[0]->bEof;
          break;
      }
    }
  
    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeTest(pExpr, pNode);
    }
    return rc;
  }
  
  
  /*
  ** Begin iterating through the set of documents in index pIdx matched by
  ** the MATCH expression passed as the first argument. If the "bDesc" 
  ** parameter is passed a non-zero value, iteration is in descending rowid 
  ** order. Or, if it is zero, in ascending order.
  **
  ** If iterating in ascending rowid order (bDesc==0), the first document
  ** visited is that with the smallest rowid that is larger than or equal
  ** to parameter iFirst. Or, if iterating in ascending order (bDesc==1),
  ** then the first document visited must have a rowid smaller than or
  ** equal to iFirst.
  **
  ** Return SQLITE_OK if successful, or an SQLite error code otherwise. It
  ** is not considered an error if the query does not match any documents.
  */
  int sqlite3Fts5ExprFirst(Fts5Expr *p, Fts5Index *pIdx, i64 iFirst, int bDesc){
    Fts5ExprNode *pRoot = p->pRoot;
    int rc;                         /* Return code */
  
    p->pIndex = pIdx;
    p->bDesc = bDesc;
    rc = fts5ExprNodeFirst(p, pRoot);
  
    /* If not at EOF but the current rowid occurs earlier than iFirst in
    ** the iteration order, move to document iFirst or later. */
    if( rc==SQLITE_OK 
     && 0==pRoot->bEof 
     && fts5RowidCmp(p, pRoot->iRowid, iFirst)<0 
    ){
      rc = fts5ExprNodeNext(p, pRoot, 1, iFirst);
    }
  
    /* If the iterator is not at a real match, skip forward until it is. */
    while( pRoot->bNomatch && rc==SQLITE_OK ){
      assert( pRoot->bEof==0 );
      rc = fts5ExprNodeNext(p, pRoot, 0, 0);
    }
    return rc;
  }
  
  /*
  ** Move to the next document 
  **
  ** Return SQLITE_OK if successful, or an SQLite error code otherwise. It
  ** is not considered an error if the query does not match any documents.
  */
  int sqlite3Fts5ExprNext(Fts5Expr *p, i64 iLast){
    int rc;
    Fts5ExprNode *pRoot = p->pRoot;
    assert( pRoot->bEof==0 && pRoot->bNomatch==0 );
    do {
      rc = fts5ExprNodeNext(p, pRoot, 0, 0);
      assert( pRoot->bNomatch==0 || (rc==SQLITE_OK && pRoot->bEof==0) );
    }while( pRoot->bNomatch );
    if( fts5RowidCmp(p, pRoot->iRowid, iLast)>0 ){
      pRoot->bEof = 1;
    }
    return rc;
  }
  
  int sqlite3Fts5ExprEof(Fts5Expr *p){
    return 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( pPhrase ){
      int i;
      for(i=0; i<pPhrase->nTerm; i++){
        Fts5ExprTerm *pSyn;
        Fts5ExprTerm *pNext;
        Fts5ExprTerm *pTerm = &pPhrase->aTerm[i];
        sqlite3_free(pTerm->zTerm);
        sqlite3Fts5IterClose(pTerm->pIter);
        for(pSyn=pTerm->pSynonym; pSyn; pSyn=pNext){
          pNext = pSyn->pSynonym;
          sqlite3Fts5IterClose(pSyn->pIter);
          fts5BufferFree((Fts5Buffer*)&pSyn[1]);
          sqlite3_free(pSyn);
        }
      }
      if( pPhrase->poslist.nSpace>0 ) fts5BufferFree(&pPhrase->poslist);
      sqlite3_free(pPhrase);
    }
  }
  
  /*
  ** Set the "bFirst" flag on the first token of the phrase passed as the
  ** only argument.
  */
  void sqlite3Fts5ParseSetCaret(Fts5ExprPhrase *pPhrase){
    if( pPhrase && pPhrase->nTerm ){
      pPhrase->aTerm[0].bFirst = 1;
    }
  }
  
  /*
  ** If argument pNear is NULL, then a new Fts5ExprNearset object is allocated
  ** and populated with pPhrase. Or, if pNear is not NULL, phrase pPhrase is
  ** appended to it and the results returned.
  **
  ** If an OOM error occurs, both the pNear and pPhrase objects are freed and
  ** NULL returned.
  */
  Fts5ExprNearset *sqlite3Fts5ParseNearset(
    Fts5Parse *pParse,              /* Parse context */
    Fts5ExprNearset *pNear,         /* Existing nearset, or NULL */
    Fts5ExprPhrase *pPhrase         /* Recently parsed phrase */
  ){
    const int SZALLOC = 8;
    Fts5ExprNearset *pRet = 0;
  
    if( pParse->rc==SQLITE_OK ){
      if( pPhrase==0 ){
        return pNear;
      }
      if( pNear==0 ){
        sqlite3_int64 nByte;
        nByte = sizeof(Fts5ExprNearset) + SZALLOC * sizeof(Fts5ExprPhrase*);
        pRet = sqlite3_malloc64(nByte);
        if( pRet==0 ){
          pParse->rc = SQLITE_NOMEM;
        }else{
          memset(pRet, 0, (size_t)nByte);
        }
      }else if( (pNear->nPhrase % SZALLOC)==0 ){
        int nNew = pNear->nPhrase + SZALLOC;
        sqlite3_int64 nByte;
  
        nByte = sizeof(Fts5ExprNearset) + nNew * sizeof(Fts5ExprPhrase*);
        pRet = (Fts5ExprNearset*)sqlite3_realloc64(pNear, nByte);
        if( pRet==0 ){
          pParse->rc = SQLITE_NOMEM;
        }
      }else{
        pRet = pNear;
      }
    }
  
    if( pRet==0 ){
      assert( pParse->rc!=SQLITE_OK );
      sqlite3Fts5ParseNearsetFree(pNear);
      sqlite3Fts5ParsePhraseFree(pPhrase);
    }else{
      if( pRet->nPhrase>0 ){
        Fts5ExprPhrase *pLast = pRet->apPhrase[pRet->nPhrase-1];
        assert( pLast==pParse->apPhrase[pParse->nPhrase-2] );
        if( pPhrase->nTerm==0 ){
          fts5ExprPhraseFree(pPhrase);
          pRet->nPhrase--;
          pParse->nPhrase--;
          pPhrase = pLast;
        }else if( pLast->nTerm==0 ){
          fts5ExprPhraseFree(pLast);
          pParse->apPhrase[pParse->nPhrase-2] = pPhrase;
          pParse->nPhrase--;
          pRet->nPhrase--;
        }
      }
      pRet->apPhrase[pRet->nPhrase++] = pPhrase;
    }
    return pRet;
  }
  
  typedef struct TokenCtx TokenCtx;
  struct TokenCtx {
    Fts5ExprPhrase *pPhrase;
    int rc;
  };
  
  /*
  ** Callback for tokenizing terms used by ParseTerm().
  */
  static int fts5ParseTokenize(
    void *pContext,                 /* Pointer to Fts5InsertCtx object */
    int tflags,                     /* Mask of FTS5_TOKEN_* flags */
    const char *pToken,             /* Buffer containing token */
    int nToken,                     /* Size of token in bytes */
    int iUnused1,                   /* Start offset of token */
    int iUnused2                    /* End offset of token */
  ){
    int rc = SQLITE_OK;
    const int SZALLOC = 8;
    TokenCtx *pCtx = (TokenCtx*)pContext;
    Fts5ExprPhrase *pPhrase = pCtx->pPhrase;
  
    UNUSED_PARAM2(iUnused1, iUnused2);
  
    /* If an error has already occurred, this is a no-op */
    if( pCtx->rc!=SQLITE_OK ) return pCtx->rc;
    if( nToken>FTS5_MAX_TOKEN_SIZE ) nToken = FTS5_MAX_TOKEN_SIZE;
  
    if( pPhrase && pPhrase->nTerm>0 && (tflags & FTS5_TOKEN_COLOCATED) ){
      Fts5ExprTerm *pSyn;
      sqlite3_int64 nByte = sizeof(Fts5ExprTerm) + sizeof(Fts5Buffer) + nToken+1;
      pSyn = (Fts5ExprTerm*)sqlite3_malloc64(nByte);
      if( pSyn==0 ){
        rc = SQLITE_NOMEM;
      }else{
        memset(pSyn, 0, (size_t)nByte);
        pSyn->zTerm = ((char*)pSyn) + sizeof(Fts5ExprTerm) + sizeof(Fts5Buffer);
        memcpy(pSyn->zTerm, pToken, nToken);
        pSyn->pSynonym = pPhrase->aTerm[pPhrase->nTerm-1].pSynonym;
        pPhrase->aTerm[pPhrase->nTerm-1].pSynonym = pSyn;
      }
    }else{
      Fts5ExprTerm *pTerm;
      if( pPhrase==0 || (pPhrase->nTerm % SZALLOC)==0 ){
        Fts5ExprPhrase *pNew;
        int nNew = SZALLOC + (pPhrase ? pPhrase->nTerm : 0);
  
        pNew = (Fts5ExprPhrase*)sqlite3_realloc64(pPhrase, 
            sizeof(Fts5ExprPhrase) + sizeof(Fts5ExprTerm) * nNew
        );
        if( pNew==0 ){
          rc = SQLITE_NOMEM;
        }else{
          if( pPhrase==0 ) memset(pNew, 0, sizeof(Fts5ExprPhrase));
          pCtx->pPhrase = pPhrase = pNew;
          pNew->nTerm = nNew - SZALLOC;
        }
      }
  
      if( rc==SQLITE_OK ){
        pTerm = &pPhrase->aTerm[pPhrase->nTerm++];
        memset(pTerm, 0, sizeof(Fts5ExprTerm));
        pTerm->zTerm = sqlite3Fts5Strndup(&rc, pToken, nToken);
      }
    }
  
    pCtx->rc = rc;
    return rc;
  }
  
  
  /*
  ** Free the phrase object passed as the only argument.
  */
  void sqlite3Fts5ParsePhraseFree(Fts5ExprPhrase *pPhrase){
    fts5ExprPhraseFree(pPhrase);
  }
  
  /*
  ** Free the phrase object passed as the second argument.
  */
  void sqlite3Fts5ParseNearsetFree(Fts5ExprNearset *pNear){
    if( pNear ){
      int i;
      for(i=0; i<pNear->nPhrase; i++){
        fts5ExprPhraseFree(pNear->apPhrase[i]);
      }
      sqlite3_free(pNear->pColset);
      sqlite3_free(pNear);
    }
  }
  
  void sqlite3Fts5ParseFinished(Fts5Parse *pParse, Fts5ExprNode *p){
    assert( pParse->pExpr==0 );
    pParse->pExpr = p;
  }
  
  static int parseGrowPhraseArray(Fts5Parse *pParse){
    if( (pParse->nPhrase % 8)==0 ){
      sqlite3_int64 nByte = sizeof(Fts5ExprPhrase*) * (pParse->nPhrase + 8);
      Fts5ExprPhrase **apNew;
      apNew = (Fts5ExprPhrase**)sqlite3_realloc64(pParse->apPhrase, nByte);
      if( apNew==0 ){
        pParse->rc = SQLITE_NOMEM;
        return SQLITE_NOMEM;
      }
      pParse->apPhrase = apNew;
    }
    return SQLITE_OK;
  }
  
  /*
  ** This function is called by the parser to process a string token. The
  ** string may or may not be quoted. In any case it is tokenized and a
  ** phrase object consisting of all tokens returned.
  */
  Fts5ExprPhrase *sqlite3Fts5ParseTerm(
    Fts5Parse *pParse,              /* Parse context */
    Fts5ExprPhrase *pAppend,        /* Phrase to append to */
    Fts5Token *pToken,              /* String to tokenize */
    int bPrefix                     /* True if there is a trailing "*" */
  ){
    Fts5Config *pConfig = pParse->pConfig;
    TokenCtx sCtx;                  /* Context object passed to callback */
    int rc;                         /* Tokenize return code */
    char *z = 0;
  
    memset(&sCtx, 0, sizeof(TokenCtx));
    sCtx.pPhrase = pAppend;
  
    rc = fts5ParseStringFromToken(pToken, &z);
    if( rc==SQLITE_OK ){
      int flags = FTS5_TOKENIZE_QUERY | (bPrefix ? FTS5_TOKENIZE_PREFIX : 0);
      int n;
      sqlite3Fts5Dequote(z);
      n = (int)strlen(z);
      rc = sqlite3Fts5Tokenize(pConfig, flags, z, n, &sCtx, fts5ParseTokenize);
    }
    sqlite3_free(z);
    if( rc || (rc = sCtx.rc) ){
      pParse->rc = rc;
      fts5ExprPhraseFree(sCtx.pPhrase);
      sCtx.pPhrase = 0;
    }else{
  
      if( pAppend==0 ){
        if( parseGrowPhraseArray(pParse) ){
          fts5ExprPhraseFree(sCtx.pPhrase);
          return 0;
        }
        pParse->nPhrase++;
      }
  
      if( sCtx.pPhrase==0 ){
        /* This happens when parsing a token or quoted phrase that contains
        ** no token characters at all. (e.g ... MATCH '""'). */
        sCtx.pPhrase = sqlite3Fts5MallocZero(&pParse->rc, sizeof(Fts5ExprPhrase));
      }else if( sCtx.pPhrase->nTerm ){
        sCtx.pPhrase->aTerm[sCtx.pPhrase->nTerm-1].bPrefix = (u8)bPrefix;
      }
      pParse->apPhrase[pParse->nPhrase-1] = sCtx.pPhrase;
    }
  
    return sCtx.pPhrase;
  }
  
  /*
  ** Create a new FTS5 expression by cloning phrase iPhrase of the
  ** expression passed as the second argument.
  */
  int sqlite3Fts5ExprClonePhrase(
    Fts5Expr *pExpr, 
    int iPhrase, 
    Fts5Expr **ppNew
  ){
    int rc = SQLITE_OK;             /* Return code */
    Fts5ExprPhrase *pOrig;          /* The phrase extracted from pExpr */
    Fts5Expr *pNew = 0;             /* Expression to return via *ppNew */
    TokenCtx sCtx = {0,0};          /* Context object for fts5ParseTokenize */
  
    pOrig = pExpr->apExprPhrase[iPhrase];
    pNew = (Fts5Expr*)sqlite3Fts5MallocZero(&rc, sizeof(Fts5Expr));
    if( rc==SQLITE_OK ){
      pNew->apExprPhrase = (Fts5ExprPhrase**)sqlite3Fts5MallocZero(&rc, 
          sizeof(Fts5ExprPhrase*));
    }
    if( rc==SQLITE_OK ){
      pNew->pRoot = (Fts5ExprNode*)sqlite3Fts5MallocZero(&rc, 
          sizeof(Fts5ExprNode));
    }
    if( rc==SQLITE_OK ){
      pNew->pRoot->pNear = (Fts5ExprNearset*)sqlite3Fts5MallocZero(&rc, 
          sizeof(Fts5ExprNearset) + sizeof(Fts5ExprPhrase*));
    }
    if( rc==SQLITE_OK ){
      Fts5Colset *pColsetOrig = pOrig->pNode->pNear->pColset;
      if( pColsetOrig ){
        sqlite3_int64 nByte;
        Fts5Colset *pColset;
        nByte = sizeof(Fts5Colset) + (pColsetOrig->nCol-1) * sizeof(int);
        pColset = (Fts5Colset*)sqlite3Fts5MallocZero(&rc, nByte);
        if( pColset ){ 
          memcpy(pColset, pColsetOrig, (size_t)nByte);
        }
        pNew->pRoot->pNear->pColset = pColset;
      }
    }
  
    if( pOrig->nTerm ){
      int i;                          /* Used to iterate through phrase terms */
      for(i=0; rc==SQLITE_OK && i<pOrig->nTerm; i++){
        int tflags = 0;
        Fts5ExprTerm *p;
        for(p=&pOrig->aTerm[i]; p && rc==SQLITE_OK; p=p->pSynonym){
          const char *zTerm = p->zTerm;
          rc = fts5ParseTokenize((void*)&sCtx, tflags, zTerm, (int)strlen(zTerm),
              0, 0);
          tflags = FTS5_TOKEN_COLOCATED;
        }
        if( rc==SQLITE_OK ){
          sCtx.pPhrase->aTerm[i].bPrefix = pOrig->aTerm[i].bPrefix;
          sCtx.pPhrase->aTerm[i].bFirst = pOrig->aTerm[i].bFirst;
        }
      }
    }else{
      /* This happens when parsing a token or quoted phrase that contains
      ** no token characters at all. (e.g ... MATCH '""'). */
      sCtx.pPhrase = sqlite3Fts5MallocZero(&rc, sizeof(Fts5ExprPhrase));
    }
  
    if( rc==SQLITE_OK ){
      /* All the allocations succeeded. Put the expression object together. */
      pNew->pIndex = pExpr->pIndex;
      pNew->pConfig = pExpr->pConfig;
      pNew->nPhrase = 1;
      pNew->apExprPhrase[0] = sCtx.pPhrase;
      pNew->pRoot->pNear->apPhrase[0] = sCtx.pPhrase;
      pNew->pRoot->pNear->nPhrase = 1;
      sCtx.pPhrase->pNode = pNew->pRoot;
  
      if( pOrig->nTerm==1 
       && pOrig->aTerm[0].pSynonym==0 
       && pOrig->aTerm[0].bFirst==0 
      ){
        pNew->pRoot->eType = FTS5_TERM;
        pNew->pRoot->xNext = fts5ExprNodeNext_TERM;
      }else{
        pNew->pRoot->eType = FTS5_STRING;
        pNew->pRoot->xNext = fts5ExprNodeNext_STRING;
      }
    }else{
      sqlite3Fts5ExprFree(pNew);
      fts5ExprPhraseFree(sCtx.pPhrase);
      pNew = 0;
    }
  
    *ppNew = pNew;
    return rc;
  }
  
  
  /*
  ** 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
  ){
    if( pNear ){
      int nNear = 0;
      int i;
      if( p->n ){
        for(i=0; i<p->n; i++){
          char c = (char)p->p[i];
          if( c<'0' || c>'9' ){
            sqlite3Fts5ParseError(
                pParse, "expected integer, got \"%.*s\"", p->n, p->p
                );
            return;
          }
          nNear = nNear * 10 + (p->p[i] - '0');
        }
      }else{
        nNear = FTS5_DEFAULT_NEARDIST;
      }
      pNear->nNear = nNear;
    }
  }
  
  /*
  ** The second argument passed to this function may be NULL, or it may be
  ** an existing Fts5Colset object. This function returns a pointer to
  ** a new colset object containing the contents of (p) with new value column
  ** number iCol appended. 
  **
  ** If an OOM error occurs, store an error code in pParse and return NULL.
  ** The old colset object (if any) is not freed in this case.
  */
  static Fts5Colset *fts5ParseColset(
    Fts5Parse *pParse,              /* Store SQLITE_NOMEM here if required */
    Fts5Colset *p,                  /* Existing colset object */
    int iCol                        /* New column to add to colset object */
  ){
    int nCol = p ? p->nCol : 0;     /* Num. columns already in colset object */
    Fts5Colset *pNew;               /* New colset object to return */
  
    assert( pParse->rc==SQLITE_OK );
    assert( iCol>=0 && iCol<pParse->pConfig->nCol );
  
    pNew = sqlite3_realloc64(p, sizeof(Fts5Colset) + sizeof(int)*nCol);
    if( pNew==0 ){
      pParse->rc = SQLITE_NOMEM;
    }else{
      int *aiCol = pNew->aiCol;
      int i, j;
      for(i=0; i<nCol; i++){
        if( aiCol[i]==iCol ) return pNew;
        if( aiCol[i]>iCol ) break;
      }
      for(j=nCol; j>i; j--){
        aiCol[j] = aiCol[j-1];
      }
      aiCol[i] = iCol;
      pNew->nCol = nCol+1;
  
  #ifndef NDEBUG
      /* Check that the array is in order and contains no duplicate entries. */
      for(i=1; i<pNew->nCol; i++) assert( pNew->aiCol[i]>pNew->aiCol[i-1] );
  #endif
    }
  
    return pNew;
  }
  
  /*
  ** Allocate and return an Fts5Colset object specifying the inverse of
  ** the colset passed as the second argument. Free the colset passed
  ** as the second argument before returning.
  */
  Fts5Colset *sqlite3Fts5ParseColsetInvert(Fts5Parse *pParse, Fts5Colset *p){
    Fts5Colset *pRet;
    int nCol = pParse->pConfig->nCol;
  
    pRet = (Fts5Colset*)sqlite3Fts5MallocZero(&pParse->rc, 
        sizeof(Fts5Colset) + sizeof(int)*nCol
    );
    if( pRet ){
      int i;
      int iOld = 0;
      for(i=0; i<nCol; i++){
        if( iOld>=p->nCol || p->aiCol[iOld]!=i ){
          pRet->aiCol[pRet->nCol++] = i;
        }else{
          iOld++;
        }
      }
    }
  
    sqlite3_free(p);
    return pRet;
  }
  
  Fts5Colset *sqlite3Fts5ParseColset(
    Fts5Parse *pParse,              /* Store SQLITE_NOMEM here if required */
    Fts5Colset *pColset,            /* Existing colset object */
    Fts5Token *p
  ){
    Fts5Colset *pRet = 0;
    int iCol;
    char *z;                        /* Dequoted copy of token p */
  
    z = sqlite3Fts5Strndup(&pParse->rc, p->p, p->n);
    if( pParse->rc==SQLITE_OK ){
      Fts5Config *pConfig = pParse->pConfig;
      sqlite3Fts5Dequote(z);
      for(iCol=0; iCol<pConfig->nCol; iCol++){
        if( 0==sqlite3_stricmp(pConfig->azCol[iCol], z) ) break;
      }
      if( iCol==pConfig->nCol ){
        sqlite3Fts5ParseError(pParse, "no such column: %s", z);
      }else{
        pRet = fts5ParseColset(pParse, pColset, iCol);
      }
      sqlite3_free(z);
    }
  
    if( pRet==0 ){
      assert( pParse->rc!=SQLITE_OK );
      sqlite3_free(pColset);
    }
  
    return pRet;
  }
  
  /*
  ** If argument pOrig is NULL, or if (*pRc) is set to anything other than
  ** SQLITE_OK when this function is called, NULL is returned. 
  **
  ** Otherwise, a copy of (*pOrig) is made into memory obtained from
  ** sqlite3Fts5MallocZero() and a pointer to it returned. If the allocation
  ** fails, (*pRc) is set to SQLITE_NOMEM and NULL is returned.
  */
  static Fts5Colset *fts5CloneColset(int *pRc, Fts5Colset *pOrig){
    Fts5Colset *pRet;
    if( pOrig ){
      sqlite3_int64 nByte = sizeof(Fts5Colset) + (pOrig->nCol-1) * sizeof(int);
      pRet = (Fts5Colset*)sqlite3Fts5MallocZero(pRc, nByte);
      if( pRet ){ 
        memcpy(pRet, pOrig, (size_t)nByte);
      }
    }else{
      pRet = 0;
    }
    return pRet;
  }
  
  /*
  ** Remove from colset pColset any columns that are not also in colset pMerge.
  */
  static void fts5MergeColset(Fts5Colset *pColset, Fts5Colset *pMerge){
    int iIn = 0;          /* Next input in pColset */
    int iMerge = 0;       /* Next input in pMerge */
    int iOut = 0;         /* Next output slot in pColset */
  
    while( iIn<pColset->nCol && iMerge<pMerge->nCol ){
      int iDiff = pColset->aiCol[iIn] - pMerge->aiCol[iMerge];
      if( iDiff==0 ){
        pColset->aiCol[iOut++] = pMerge->aiCol[iMerge];
        iMerge++;
        iIn++;
      }else if( iDiff>0 ){
        iMerge++;
      }else{
        iIn++;
      }
    }
    pColset->nCol = iOut;
  }
  
  /*
  ** Recursively apply colset pColset to expression node pNode and all of
  ** its decendents. If (*ppFree) is not NULL, it contains a spare copy
  ** of pColset. This function may use the spare copy and set (*ppFree) to
  ** zero, or it may create copies of pColset using fts5CloneColset().
  */
  static void fts5ParseSetColset(
    Fts5Parse *pParse, 
    Fts5ExprNode *pNode, 
    Fts5Colset *pColset,
    Fts5Colset **ppFree
  ){
    if( pParse->rc==SQLITE_OK ){
      assert( pNode->eType==FTS5_TERM || pNode->eType==FTS5_STRING 
           || pNode->eType==FTS5_AND  || pNode->eType==FTS5_OR
           || pNode->eType==FTS5_NOT  || pNode->eType==FTS5_EOF
      );
      if( pNode->eType==FTS5_STRING || pNode->eType==FTS5_TERM ){
        Fts5ExprNearset *pNear = pNode->pNear;
        if( pNear->pColset ){
          fts5MergeColset(pNear->pColset, pColset);
          if( pNear->pColset->nCol==0 ){
            pNode->eType = FTS5_EOF;
            pNode->xNext = 0;
          }
        }else if( *ppFree ){
          pNear->pColset = pColset;
          *ppFree = 0;
        }else{
          pNear->pColset = fts5CloneColset(&pParse->rc, pColset);
        }
      }else{
        int i;
        assert( pNode->eType!=FTS5_EOF || pNode->nChild==0 );
        for(i=0; i<pNode->nChild; i++){
          fts5ParseSetColset(pParse, pNode->apChild[i], pColset, ppFree);
        }
      }
    }
  }
  
  /*
  ** Apply colset pColset to expression node pExpr and all of its descendents.
  */
  void sqlite3Fts5ParseSetColset(
    Fts5Parse *pParse, 
    Fts5ExprNode *pExpr, 
    Fts5Colset *pColset 
  ){
    Fts5Colset *pFree = pColset;
    if( pParse->pConfig->eDetail==FTS5_DETAIL_NONE ){
      sqlite3Fts5ParseError(pParse, 
          "fts5: column queries are not supported (detail=none)"
      );
    }else{
      fts5ParseSetColset(pParse, pExpr, pColset, &pFree);
    }
    sqlite3_free(pFree);
  }
  
  static void fts5ExprAssignXNext(Fts5ExprNode *pNode){
    switch( pNode->eType ){
      case FTS5_STRING: {
        Fts5ExprNearset *pNear = pNode->pNear;
        if( pNear->nPhrase==1 && pNear->apPhrase[0]->nTerm==1 
         && pNear->apPhrase[0]->aTerm[0].pSynonym==0
         && pNear->apPhrase[0]->aTerm[0].bFirst==0
        ){
          pNode->eType = FTS5_TERM;
          pNode->xNext = fts5ExprNodeNext_TERM;
        }else{
          pNode->xNext = fts5ExprNodeNext_STRING;
        }
        break;
      };
  
      case FTS5_OR: {
        pNode->xNext = fts5ExprNodeNext_OR;
        break;
      };
  
      case FTS5_AND: {
        pNode->xNext = fts5ExprNodeNext_AND;
        break;
      };
  
      default: assert( pNode->eType==FTS5_NOT ); {
        pNode->xNext = fts5ExprNodeNext_NOT;
        break;
      };
    }
  }
  
  static void fts5ExprAddChildren(Fts5ExprNode *p, Fts5ExprNode *pSub){
    if( p->eType!=FTS5_NOT && pSub->eType==p->eType ){
      int nByte = sizeof(Fts5ExprNode*) * pSub->nChild;
      memcpy(&p->apChild[p->nChild], pSub->apChild, nByte);
      p->nChild += pSub->nChild;
      sqlite3_free(pSub);
    }else{
      p->apChild[p->nChild++] = pSub;
    }
  }
  
  /*
  ** This function is used when parsing LIKE or GLOB patterns against
  ** trigram indexes that specify either detail=column or detail=none.
  ** It converts a phrase:
  **
  **     abc + def + ghi
  **
  ** into an AND tree:
  **
  **     abc AND def AND ghi
  */
  static Fts5ExprNode *fts5ParsePhraseToAnd(
    Fts5Parse *pParse, 
    Fts5ExprNearset *pNear
  ){
    int nTerm = pNear->apPhrase[0]->nTerm;
    int ii;
    int nByte;
    Fts5ExprNode *pRet;
  
    assert( pNear->nPhrase==1 );
    assert( pParse->bPhraseToAnd );
  
    nByte = sizeof(Fts5ExprNode) + nTerm*sizeof(Fts5ExprNode*);
    pRet = (Fts5ExprNode*)sqlite3Fts5MallocZero(&pParse->rc, nByte);
    if( pRet ){
      pRet->eType = FTS5_AND;
      pRet->nChild = nTerm;
      fts5ExprAssignXNext(pRet);
      pParse->nPhrase--;
      for(ii=0; ii<nTerm; ii++){
        Fts5ExprPhrase *pPhrase = (Fts5ExprPhrase*)sqlite3Fts5MallocZero(
            &pParse->rc, sizeof(Fts5ExprPhrase)
        );
        if( pPhrase ){
          if( parseGrowPhraseArray(pParse) ){
            fts5ExprPhraseFree(pPhrase);
          }else{
            pParse->apPhrase[pParse->nPhrase++] = pPhrase;
            pPhrase->nTerm = 1;
            pPhrase->aTerm[0].zTerm = sqlite3Fts5Strndup(
                &pParse->rc, pNear->apPhrase[0]->aTerm[ii].zTerm, -1
            );
            pRet->apChild[ii] = sqlite3Fts5ParseNode(pParse, FTS5_STRING, 
                0, 0, sqlite3Fts5ParseNearset(pParse, 0, pPhrase)
            );
          }
        }
      }
    
      if( pParse->rc ){
        sqlite3Fts5ParseNodeFree(pRet);
        pRet = 0;
      }else{
        sqlite3Fts5ParseNearsetFree(pNear);
      }
    }
  
    return pRet;
  }
  
  /*
  ** Allocate and return a new expression object. If anything goes wrong (i.e.
  ** OOM error), leave an error code in pParse and return NULL.
  */
  Fts5ExprNode *sqlite3Fts5ParseNode(
    Fts5Parse *pParse,              /* Parse context */
    int eType,                      /* FTS5_STRING, AND, OR or NOT */
    Fts5ExprNode *pLeft,            /* Left hand child expression */
    Fts5ExprNode *pRight,           /* Right hand child expression */
    Fts5ExprNearset *pNear          /* For STRING expressions, the near cluster */
  ){
    Fts5ExprNode *pRet = 0;
  
    if( pParse->rc==SQLITE_OK ){
      int nChild = 0;               /* Number of children of returned node */
      sqlite3_int64 nByte;          /* Bytes of space to allocate for this node */
   
      assert( (eType!=FTS5_STRING && !pNear)
           || (eType==FTS5_STRING && !pLeft && !pRight)
      );
      if( eType==FTS5_STRING && pNear==0 ) return 0;
      if( eType!=FTS5_STRING && pLeft==0 ) return pRight;
      if( eType!=FTS5_STRING && pRight==0 ) return pLeft;
  
      if( eType==FTS5_STRING 
       && pParse->bPhraseToAnd 
       && pNear->apPhrase[0]->nTerm>1
      ){
        pRet = fts5ParsePhraseToAnd(pParse, pNear);
      }else{
        if( eType==FTS5_NOT ){
          nChild = 2;
        }else if( eType==FTS5_AND || eType==FTS5_OR ){
          nChild = 2;
          if( pLeft->eType==eType ) nChild += pLeft->nChild-1;
          if( pRight->eType==eType ) nChild += pRight->nChild-1;
        }
  
        nByte = sizeof(Fts5ExprNode) + sizeof(Fts5ExprNode*)*(nChild-1);
        pRet = (Fts5ExprNode*)sqlite3Fts5MallocZero(&pParse->rc, nByte);
  
        if( pRet ){
          pRet->eType = eType;
          pRet->pNear = pNear;
          fts5ExprAssignXNext(pRet);
          if( eType==FTS5_STRING ){
            int iPhrase;
            for(iPhrase=0; iPhrase<pNear->nPhrase; iPhrase++){
              pNear->apPhrase[iPhrase]->pNode = pRet;
              if( pNear->apPhrase[iPhrase]->nTerm==0 ){
                pRet->xNext = 0;
                pRet->eType = FTS5_EOF;
              }
            }
  
            if( pParse->pConfig->eDetail!=FTS5_DETAIL_FULL ){
              Fts5ExprPhrase *pPhrase = pNear->apPhrase[0];
              if( pNear->nPhrase!=1 
                  || pPhrase->nTerm>1
                  || (pPhrase->nTerm>0 && pPhrase->aTerm[0].bFirst)
                ){
                sqlite3Fts5ParseError(pParse, 
                    "fts5: %s queries are not supported (detail!=full)", 
                    pNear->nPhrase==1 ? "phrase": "NEAR"
                );
                sqlite3_free(pRet);
                pRet = 0;
              }
            }
          }else{
            fts5ExprAddChildren(pRet, pLeft);
            fts5ExprAddChildren(pRet, pRight);
          }
        }
      }
    }
  
    if( pRet==0 ){
      assert( pParse->rc!=SQLITE_OK );
      sqlite3Fts5ParseNodeFree(pLeft);
      sqlite3Fts5ParseNodeFree(pRight);
      sqlite3Fts5ParseNearsetFree(pNear);
    }
    return pRet;
  }
  
  Fts5ExprNode *sqlite3Fts5ParseImplicitAnd(
    Fts5Parse *pParse,              /* Parse context */
    Fts5ExprNode *pLeft,            /* Left hand child expression */
    Fts5ExprNode *pRight            /* Right hand child expression */
  ){
    Fts5ExprNode *pRet = 0;
    Fts5ExprNode *pPrev;
  
    if( pParse->rc ){
      sqlite3Fts5ParseNodeFree(pLeft);
      sqlite3Fts5ParseNodeFree(pRight);
    }else{
  
      assert( pLeft->eType==FTS5_STRING 
          || pLeft->eType==FTS5_TERM
          || pLeft->eType==FTS5_EOF
          || pLeft->eType==FTS5_AND
      );
      assert( pRight->eType==FTS5_STRING 
          || pRight->eType==FTS5_TERM 
          || pRight->eType==FTS5_EOF 
      );
  
      if( pLeft->eType==FTS5_AND ){
        pPrev = pLeft->apChild[pLeft->nChild-1];
      }else{
        pPrev = pLeft;
      }
      assert( pPrev->eType==FTS5_STRING 
          || pPrev->eType==FTS5_TERM 
          || pPrev->eType==FTS5_EOF 
          );
  
      if( pRight->eType==FTS5_EOF ){
        assert( pParse->apPhrase[pParse->nPhrase-1]==pRight->pNear->apPhrase[0] );
        sqlite3Fts5ParseNodeFree(pRight);
        pRet = pLeft;
        pParse->nPhrase--;
      }
      else if( pPrev->eType==FTS5_EOF ){
        Fts5ExprPhrase **ap;
  
        if( pPrev==pLeft ){
          pRet = pRight;
        }else{
          pLeft->apChild[pLeft->nChild-1] = pRight;
          pRet = pLeft;
        }
  
        ap = &pParse->apPhrase[pParse->nPhrase-1-pRight->pNear->nPhrase];
        assert( ap[0]==pPrev->pNear->apPhrase[0] );
        memmove(ap, &ap[1], sizeof(Fts5ExprPhrase*)*pRight->pNear->nPhrase);
        pParse->nPhrase--;
  
        sqlite3Fts5ParseNodeFree(pPrev);
      }
      else{
        pRet = sqlite3Fts5ParseNode(pParse, FTS5_AND, pLeft, pRight, 0);
      }
    }
  
    return pRet;
  }
  
  #ifdef SQLITE_TEST
  static char *fts5ExprTermPrint(Fts5ExprTerm *pTerm){
    sqlite3_int64 nByte = 0;
    Fts5ExprTerm *p;
    char *zQuoted;
  
    /* Determine the maximum amount of space required. */
    for(p=pTerm; p; p=p->pSynonym){
      nByte += (int)strlen(pTerm->zTerm) * 2 + 3 + 2;
    }
    zQuoted = sqlite3_malloc64(nByte);
  
    if( zQuoted ){
      int i = 0;
      for(p=pTerm; p; p=p->pSynonym){
        char *zIn = p->zTerm;
        zQuoted[i++] = '"';
        while( *zIn ){
          if( *zIn=='"' ) zQuoted[i++] = '"';
          zQuoted[i++] = *zIn++;
        }
        zQuoted[i++] = '"';
        if( p->pSynonym ) zQuoted[i++] = '|';
      }
      if( pTerm->bPrefix ){
        zQuoted[i++] = ' ';
        zQuoted[i++] = '*';
      }
      zQuoted[i++] = '\0';
    }
    return zQuoted;
  }
  
  static char *fts5PrintfAppend(char *zApp, const char *zFmt, ...){
    char *zNew;
    va_list ap;
    va_start(ap, zFmt);
    zNew = sqlite3_vmprintf(zFmt, ap);
    va_end(ap);
    if( zApp && zNew ){
      char *zNew2 = sqlite3_mprintf("%s%s", zApp, zNew);
      sqlite3_free(zNew);
      zNew = zNew2;
    }
    sqlite3_free(zApp);
    return zNew;
  }
  
  /*
  ** Compose a tcl-readable representation of expression pExpr. Return a 
  ** pointer to a buffer containing that representation. It is the 
  ** responsibility of the caller to at some point free the buffer using 
  ** sqlite3_free().
  */
  static char *fts5ExprPrintTcl(
    Fts5Config *pConfig, 
    const char *zNearsetCmd,
    Fts5ExprNode *pExpr
  ){
    char *zRet = 0;
    if( pExpr->eType==FTS5_STRING || pExpr->eType==FTS5_TERM ){
      Fts5ExprNearset *pNear = pExpr->pNear;
      int i; 
      int iTerm;
  
      zRet = fts5PrintfAppend(zRet, "%s ", zNearsetCmd);
      if( zRet==0 ) return 0;
      if( pNear->pColset ){
        int *aiCol = pNear->pColset->aiCol;
        int nCol = pNear->pColset->nCol;
        if( nCol==1 ){
          zRet = fts5PrintfAppend(zRet, "-col %d ", aiCol[0]);
        }else{
          zRet = fts5PrintfAppend(zRet, "-col {%d", aiCol[0]);
          for(i=1; i<pNear->pColset->nCol; i++){
            zRet = fts5PrintfAppend(zRet, " %d", aiCol[i]);
          }
          zRet = fts5PrintfAppend(zRet, "} ");
        }
        if( zRet==0 ) return 0;
      }
  
      if( pNear->nPhrase>1 ){
        zRet = fts5PrintfAppend(zRet, "-near %d ", pNear->nNear);
        if( zRet==0 ) return 0;
      }
  
      zRet = fts5PrintfAppend(zRet, "--");
      if( zRet==0 ) return 0;
  
      for(i=0; i<pNear->nPhrase; i++){
        Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
  
        zRet = fts5PrintfAppend(zRet, " {");
        for(iTerm=0; zRet && iTerm<pPhrase->nTerm; iTerm++){
          char *zTerm = pPhrase->aTerm[iTerm].zTerm;
          zRet = fts5PrintfAppend(zRet, "%s%s", iTerm==0?"":" ", zTerm);
          if( pPhrase->aTerm[iTerm].bPrefix ){
            zRet = fts5PrintfAppend(zRet, "*");
          }
        }
  
        if( zRet ) zRet = fts5PrintfAppend(zRet, "}");
        if( zRet==0 ) return 0;
      }
  
    }else{
      char const *zOp = 0;
      int i;
      switch( pExpr->eType ){
        case FTS5_AND: zOp = "AND"; break;
        case FTS5_NOT: zOp = "NOT"; break;
        default: 
          assert( pExpr->eType==FTS5_OR );
          zOp = "OR"; 
          break;
      }
  
      zRet = sqlite3_mprintf("%s", zOp);
      for(i=0; zRet && i<pExpr->nChild; i++){
        char *z = fts5ExprPrintTcl(pConfig, zNearsetCmd, pExpr->apChild[i]);
        if( !z ){
          sqlite3_free(zRet);
          zRet = 0;
        }else{
          zRet = fts5PrintfAppend(zRet, " [%z]", z);
        }
      }
    }
  
    return zRet;
  }
  
  static char *fts5ExprPrint(Fts5Config *pConfig, Fts5ExprNode *pExpr){
    char *zRet = 0;
    if( pExpr->eType==0 ){
      return sqlite3_mprintf("\"\"");
    }else
    if( pExpr->eType==FTS5_STRING || pExpr->eType==FTS5_TERM ){
      Fts5ExprNearset *pNear = pExpr->pNear;
      int i; 
      int iTerm;
  
      if( pNear->pColset ){
        int ii;
        Fts5Colset *pColset = pNear->pColset;
        if( pColset->nCol>1 ) zRet = fts5PrintfAppend(zRet, "{");
        for(ii=0; ii<pColset->nCol; ii++){
          zRet = fts5PrintfAppend(zRet, "%s%s", 
              pConfig->azCol[pColset->aiCol[ii]], ii==pColset->nCol-1 ? "" : " "
          );
        }
        if( zRet ){
          zRet = fts5PrintfAppend(zRet, "%s : ", pColset->nCol>1 ? "}" : "");
        }
        if( zRet==0 ) return 0;
      }
  
      if( pNear->nPhrase>1 ){
        zRet = fts5PrintfAppend(zRet, "NEAR(");
        if( zRet==0 ) return 0;
      }
  
      for(i=0; i<pNear->nPhrase; i++){
        Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
        if( i!=0 ){
          zRet = fts5PrintfAppend(zRet, " ");
          if( zRet==0 ) return 0;
        }
        for(iTerm=0; iTerm<pPhrase->nTerm; iTerm++){
          char *zTerm = fts5ExprTermPrint(&pPhrase->aTerm[iTerm]);
          if( zTerm ){
            zRet = fts5PrintfAppend(zRet, "%s%s", iTerm==0?"":" + ", zTerm);
            sqlite3_free(zTerm);
          }
          if( zTerm==0 || zRet==0 ){
            sqlite3_free(zRet);
            return 0;
          }
        }
      }
  
      if( pNear->nPhrase>1 ){
        zRet = fts5PrintfAppend(zRet, ", %d)", pNear->nNear);
        if( zRet==0 ) return 0;
      }
  
    }else{
      char const *zOp = 0;
      int i;
  
      switch( pExpr->eType ){
        case FTS5_AND: zOp = " AND "; break;
        case FTS5_NOT: zOp = " NOT "; break;
        default:  
          assert( pExpr->eType==FTS5_OR );
          zOp = " OR "; 
          break;
      }
  
      for(i=0; i<pExpr->nChild; i++){
        char *z = fts5ExprPrint(pConfig, pExpr->apChild[i]);
        if( z==0 ){
          sqlite3_free(zRet);
          zRet = 0;
        }else{
          int e = pExpr->apChild[i]->eType;
          int b = (e!=FTS5_STRING && e!=FTS5_TERM && e!=FTS5_EOF);
          zRet = fts5PrintfAppend(zRet, "%s%s%z%s", 
              (i==0 ? "" : zOp),
              (b?"(":""), z, (b?")":"")
          );
        }
        if( zRet==0 ) break;
      }
    }
  
    return zRet;
  }
  
  /*
  ** The implementation of user-defined scalar functions fts5_expr() (bTcl==0)
  ** and fts5_expr_tcl() (bTcl!=0).
  */
  static void fts5ExprFunction(
    sqlite3_context *pCtx,          /* Function call context */
    int nArg,                       /* Number of args */
    sqlite3_value **apVal,          /* Function arguments */
    int bTcl
  ){
    Fts5Global *pGlobal = (Fts5Global*)sqlite3_user_data(pCtx);
    sqlite3 *db = sqlite3_context_db_handle(pCtx);
    const char *zExpr = 0;
    char *zErr = 0;
    Fts5Expr *pExpr = 0;
    int rc;
    int i;
  
    const char **azConfig;          /* Array of arguments for Fts5Config */
    const char *zNearsetCmd = "nearset";
    int nConfig;                    /* Size of azConfig[] */
    Fts5Config *pConfig = 0;
    int iArg = 1;
  
    if( nArg<1 ){
      zErr = sqlite3_mprintf("wrong number of arguments to function %s",
          bTcl ? "fts5_expr_tcl" : "fts5_expr"
      );
      sqlite3_result_error(pCtx, zErr, -1);
      sqlite3_free(zErr);
      return;
    }
  
    if( bTcl && nArg>1 ){
      zNearsetCmd = (const char*)sqlite3_value_text(apVal[1]);
      iArg = 2;
    }
  
    nConfig = 3 + (nArg-iArg);
    azConfig = (const char**)sqlite3_malloc64(sizeof(char*) * nConfig);
    if( azConfig==0 ){
      sqlite3_result_error_nomem(pCtx);
      return;
    }
    azConfig[0] = 0;
    azConfig[1] = "main";
    azConfig[2] = "tbl";
    for(i=3; iArg<nArg; iArg++){
      const char *z = (const char*)sqlite3_value_text(apVal[iArg]);
      azConfig[i++] = (z ? z : "");
    }
  
    zExpr = (const char*)sqlite3_value_text(apVal[0]);
    if( zExpr==0 ) zExpr = "";
  
    rc = sqlite3Fts5ConfigParse(pGlobal, db, nConfig, azConfig, &pConfig, &zErr);
    if( rc==SQLITE_OK ){
      rc = sqlite3Fts5ExprNew(pConfig, 0, pConfig->nCol, zExpr, &pExpr, &zErr);
    }
    if( rc==SQLITE_OK ){
      char *zText;
      if( pExpr->pRoot->xNext==0 ){
        zText = sqlite3_mprintf("");
      }else if( bTcl ){
        zText = fts5ExprPrintTcl(pConfig, zNearsetCmd, pExpr->pRoot);
      }else{
        zText = fts5ExprPrint(pConfig, pExpr->pRoot);
      }
      if( zText==0 ){
        rc = SQLITE_NOMEM;
      }else{
        sqlite3_result_text(pCtx, zText, -1, SQLITE_TRANSIENT);
        sqlite3_free(zText);
      }
    }
  
    if( rc!=SQLITE_OK ){
      if( zErr ){
        sqlite3_result_error(pCtx, zErr, -1);
        sqlite3_free(zErr);
      }else{
        sqlite3_result_error_code(pCtx, rc);
      }
    }
    sqlite3_free((void *)azConfig);
    sqlite3Fts5ConfigFree(pConfig);
    sqlite3Fts5ExprFree(pExpr);
  }
  
  static void fts5ExprFunctionHr(
    sqlite3_context *pCtx,          /* Function call context */
    int nArg,                       /* Number of args */
    sqlite3_value **apVal           /* Function arguments */
  ){
    fts5ExprFunction(pCtx, nArg, apVal, 0);
  }
  static void fts5ExprFunctionTcl(
    sqlite3_context *pCtx,          /* Function call context */
    int nArg,                       /* Number of args */
    sqlite3_value **apVal           /* Function arguments */
  ){
    fts5ExprFunction(pCtx, nArg, apVal, 1);
  }
  
  /*
  ** The implementation of an SQLite user-defined-function that accepts a
  ** single integer as an argument. If the integer is an alpha-numeric 
  ** unicode code point, 1 is returned. Otherwise 0.
  */
  static void fts5ExprIsAlnum(
    sqlite3_context *pCtx,          /* Function call context */
    int nArg,                       /* Number of args */
    sqlite3_value **apVal           /* Function arguments */
  ){
    int iCode;
    u8 aArr[32];
    if( nArg!=1 ){
      sqlite3_result_error(pCtx, 
          "wrong number of arguments to function fts5_isalnum", -1
      );
      return;
    }
    memset(aArr, 0, sizeof(aArr));
    sqlite3Fts5UnicodeCatParse("L*", aArr);
    sqlite3Fts5UnicodeCatParse("N*", aArr);
    sqlite3Fts5UnicodeCatParse("Co", aArr);
    iCode = sqlite3_value_int(apVal[0]);
    sqlite3_result_int(pCtx, aArr[sqlite3Fts5UnicodeCategory((u32)iCode)]);
  }
  
  static void fts5ExprFold(
    sqlite3_context *pCtx,          /* Function call context */
    int nArg,                       /* Number of args */
    sqlite3_value **apVal           /* Function arguments */
  ){
    if( nArg!=1 && nArg!=2 ){
      sqlite3_result_error(pCtx, 
          "wrong number of arguments to function fts5_fold", -1
      );
    }else{
      int iCode;
      int bRemoveDiacritics = 0;
      iCode = sqlite3_value_int(apVal[0]);
      if( nArg==2 ) bRemoveDiacritics = sqlite3_value_int(apVal[1]);
      sqlite3_result_int(pCtx, sqlite3Fts5UnicodeFold(iCode, bRemoveDiacritics));
    }
  }
  #endif /* ifdef SQLITE_TEST */
  
  /*
  ** This is called during initialization to register the fts5_expr() scalar
  ** UDF with the SQLite handle passed as the only argument.
  */
  int sqlite3Fts5ExprInit(Fts5Global *pGlobal, sqlite3 *db){
  #ifdef SQLITE_TEST
    struct Fts5ExprFunc {
      const char *z;
      void (*x)(sqlite3_context*,int,sqlite3_value**);
    } aFunc[] = {
      { "fts5_expr",     fts5ExprFunctionHr },
      { "fts5_expr_tcl", fts5ExprFunctionTcl },
      { "fts5_isalnum",  fts5ExprIsAlnum },
      { "fts5_fold",     fts5ExprFold },
    };
    int i;
    int rc = SQLITE_OK;
    void *pCtx = (void*)pGlobal;
  
    for(i=0; rc==SQLITE_OK && i<ArraySize(aFunc); i++){
      struct Fts5ExprFunc *p = &aFunc[i];
      rc = sqlite3_create_function(db, p->z, -1, SQLITE_UTF8, pCtx, p->x, 0, 0);
    }
  #else
    int rc = SQLITE_OK;
    UNUSED_PARAM2(pGlobal,db);
  #endif
  
    /* Avoid warnings indicating that sqlite3Fts5ParserTrace() and
    ** sqlite3Fts5ParserFallback() are unused */
  #ifndef NDEBUG
    (void)sqlite3Fts5ParserTrace;
  #endif
    (void)sqlite3Fts5ParserFallback;
  
    return rc;
  }
  
  /*
  ** Return the number of phrases in expression pExpr.
  */
  int sqlite3Fts5ExprPhraseCount(Fts5Expr *pExpr){
    return (pExpr ? pExpr->nPhrase : 0);
  }
  
  /*
  ** Return the number of terms in the iPhrase'th phrase in pExpr.
  */
  int sqlite3Fts5ExprPhraseSize(Fts5Expr *pExpr, int iPhrase){
    if( iPhrase<0 || iPhrase>=pExpr->nPhrase ) return 0;
    return pExpr->apExprPhrase[iPhrase]->nTerm;
  }
  
  /*
  ** This function is used to access the current position list for phrase
  ** iPhrase.
  */
  int sqlite3Fts5ExprPoslist(Fts5Expr *pExpr, int iPhrase, const u8 **pa){
    int nRet;
    Fts5ExprPhrase *pPhrase = pExpr->apExprPhrase[iPhrase];
    Fts5ExprNode *pNode = pPhrase->pNode;
    if( pNode->bEof==0 && pNode->iRowid==pExpr->pRoot->iRowid ){
      *pa = pPhrase->poslist.p;
      nRet = pPhrase->poslist.n;
    }else{
      *pa = 0;
      nRet = 0;
    }
    return nRet;
  }
  
  struct Fts5PoslistPopulator {
    Fts5PoslistWriter writer;
    int bOk;                        /* True if ok to populate */
    int bMiss;
  };
  
  Fts5PoslistPopulator *sqlite3Fts5ExprClearPoslists(Fts5Expr *pExpr, int bLive){
    Fts5PoslistPopulator *pRet;
    pRet = sqlite3_malloc64(sizeof(Fts5PoslistPopulator)*pExpr->nPhrase);
    if( pRet ){
      int i;
      memset(pRet, 0, sizeof(Fts5PoslistPopulator)*pExpr->nPhrase);
      for(i=0; i<pExpr->nPhrase; i++){
        Fts5Buffer *pBuf = &pExpr->apExprPhrase[i]->poslist;
        Fts5ExprNode *pNode = pExpr->apExprPhrase[i]->pNode;
        assert( pExpr->apExprPhrase[i]->nTerm==1 );
        if( bLive && 
            (pBuf->n==0 || pNode->iRowid!=pExpr->pRoot->iRowid || pNode->bEof)
        ){
          pRet[i].bMiss = 1;
        }else{
          pBuf->n = 0;
        }
      }
    }
    return pRet;
  }
  
  struct Fts5ExprCtx {
    Fts5Expr *pExpr;
    Fts5PoslistPopulator *aPopulator;
    i64 iOff;
  };
  typedef struct Fts5ExprCtx Fts5ExprCtx;
  
  /*
  ** TODO: Make this more efficient!
  */
  static int fts5ExprColsetTest(Fts5Colset *pColset, int iCol){
    int i;
    for(i=0; i<pColset->nCol; i++){
      if( pColset->aiCol[i]==iCol ) return 1;
    }
    return 0;
  }
  
  static int fts5ExprPopulatePoslistsCb(
    void *pCtx,                /* Copy of 2nd argument to xTokenize() */
    int tflags,                /* Mask of FTS5_TOKEN_* flags */
    const char *pToken,        /* Pointer to buffer containing token */
    int nToken,                /* Size of token in bytes */
    int iUnused1,              /* Byte offset of token within input text */
    int iUnused2               /* Byte offset of end of token within input text */
  ){
    Fts5ExprCtx *p = (Fts5ExprCtx*)pCtx;
    Fts5Expr *pExpr = p->pExpr;
    int i;
  
    UNUSED_PARAM2(iUnused1, iUnused2);
  
    if( nToken>FTS5_MAX_TOKEN_SIZE ) nToken = FTS5_MAX_TOKEN_SIZE;
    if( (tflags & FTS5_TOKEN_COLOCATED)==0 ) p->iOff++;
    for(i=0; i<pExpr->nPhrase; i++){
      Fts5ExprTerm *pTerm;
      if( p->aPopulator[i].bOk==0 ) continue;
      for(pTerm=&pExpr->apExprPhrase[i]->aTerm[0]; pTerm; pTerm=pTerm->pSynonym){
        int nTerm = (int)strlen(pTerm->zTerm);
        if( (nTerm==nToken || (nTerm<nToken && pTerm->bPrefix))
         && memcmp(pTerm->zTerm, pToken, nTerm)==0
        ){
          int rc = sqlite3Fts5PoslistWriterAppend(
              &pExpr->apExprPhrase[i]->poslist, &p->aPopulator[i].writer, p->iOff
          );
          if( rc ) return rc;
          break;
        }
      }
    }
    return SQLITE_OK;
  }
  
  int sqlite3Fts5ExprPopulatePoslists(
    Fts5Config *pConfig,
    Fts5Expr *pExpr, 
    Fts5PoslistPopulator *aPopulator,
    int iCol, 
    const char *z, int n
  ){
    int i;
    Fts5ExprCtx sCtx;
    sCtx.pExpr = pExpr;
    sCtx.aPopulator = aPopulator;
    sCtx.iOff = (((i64)iCol) << 32) - 1;
  
    for(i=0; i<pExpr->nPhrase; i++){
      Fts5ExprNode *pNode = pExpr->apExprPhrase[i]->pNode;
      Fts5Colset *pColset = pNode->pNear->pColset;
      if( (pColset && 0==fts5ExprColsetTest(pColset, iCol)) 
       || aPopulator[i].bMiss
      ){
        aPopulator[i].bOk = 0;
      }else{
        aPopulator[i].bOk = 1;
      }
    }
  
    return sqlite3Fts5Tokenize(pConfig, 
        FTS5_TOKENIZE_DOCUMENT, z, n, (void*)&sCtx, fts5ExprPopulatePoslistsCb
    );
  }
  
  static void fts5ExprClearPoslists(Fts5ExprNode *pNode){
    if( pNode->eType==FTS5_TERM || pNode->eType==FTS5_STRING ){
      pNode->pNear->apPhrase[0]->poslist.n = 0;
    }else{
      int i;
      for(i=0; i<pNode->nChild; i++){
        fts5ExprClearPoslists(pNode->apChild[i]);
      }
    }
  }
  
  static int fts5ExprCheckPoslists(Fts5ExprNode *pNode, i64 iRowid){
    pNode->iRowid = iRowid;
    pNode->bEof = 0;
    switch( pNode->eType ){
      case FTS5_TERM:
      case FTS5_STRING:
        return (pNode->pNear->apPhrase[0]->poslist.n>0);
  
      case FTS5_AND: {
        int i;
        for(i=0; i<pNode->nChild; i++){
          if( fts5ExprCheckPoslists(pNode->apChild[i], iRowid)==0 ){
            fts5ExprClearPoslists(pNode);
            return 0;
          }
        }
        break;
      }
  
      case FTS5_OR: {
        int i;
        int bRet = 0;
        for(i=0; i<pNode->nChild; i++){
          if( fts5ExprCheckPoslists(pNode->apChild[i], iRowid) ){
            bRet = 1;
          }
        }
        return bRet;
      }
  
      default: {
        assert( pNode->eType==FTS5_NOT );
        if( 0==fts5ExprCheckPoslists(pNode->apChild[0], iRowid)
            || 0!=fts5ExprCheckPoslists(pNode->apChild[1], iRowid)
          ){
          fts5ExprClearPoslists(pNode);
          return 0;
        }
        break;
      }
    }
    return 1;
  }
  
  void sqlite3Fts5ExprCheckPoslists(Fts5Expr *pExpr, i64 iRowid){
    fts5ExprCheckPoslists(pExpr->pRoot, iRowid);
  }
  
  /*
  ** This function is only called for detail=columns tables. 
  */
  int sqlite3Fts5ExprPhraseCollist(
    Fts5Expr *pExpr, 
    int iPhrase, 
    const u8 **ppCollist, 
    int *pnCollist
  ){
    Fts5ExprPhrase *pPhrase = pExpr->apExprPhrase[iPhrase];
    Fts5ExprNode *pNode = pPhrase->pNode;
    int rc = SQLITE_OK;
  
    assert( iPhrase>=0 && iPhrase<pExpr->nPhrase );
    assert( pExpr->pConfig->eDetail==FTS5_DETAIL_COLUMNS );
  
    if( pNode->bEof==0 
     && pNode->iRowid==pExpr->pRoot->iRowid 
     && pPhrase->poslist.n>0
    ){
      Fts5ExprTerm *pTerm = &pPhrase->aTerm[0];
      if( pTerm->pSynonym ){
        Fts5Buffer *pBuf = (Fts5Buffer*)&pTerm->pSynonym[1];
        rc = fts5ExprSynonymList(
            pTerm, pNode->iRowid, pBuf, (u8**)ppCollist, pnCollist
        );
      }else{
        *ppCollist = pPhrase->aTerm[0].pIter->pData;
        *pnCollist = pPhrase->aTerm[0].pIter->nData;
      }
    }else{
      *ppCollist = 0;
      *pnCollist = 0;
    }
  
    return rc;
  }
  