sqlite_int64 ret;
  assert( !atEnd(pReader) );
  assert( pReader->iLastPos==-1 );
  getVarint(pReader->p, &ret);
  return ret;
}

/* Read the next docid. 
*/
static sqlite_int64 readDocid(DocListReader *pReader){
  sqlite_int64 ret;
  assert( !atEnd(pReader) );
  assert( pReader->iLastPos==-1 );
  pReader->p += getVarint(pReader->p, &ret);
  if( pReader->pDoclist->iType>=DL_POSITIONS ){
................................................................................

/* Read the next position from a position list.
 * Returns the position, or -1 at the end of the list. */
static int readPosition(DocListReader *pReader){
  int i;
  int iType = pReader->pDoclist->iType;




  assert( !atEnd(pReader) );
  assert( pReader->iLastPos!=-1 );

  if( iType<DL_POSITIONS ){
    return -1;
  }
  pReader->p += getVarint32(pReader->p, &i);
  if( i==0 ){
    pReader->iLastPos = -1;
................................................................................
  while( !atEnd(&updateReader) ){
    char *pSource = updateReader.p;
    sqlite_int64 iDocid = readDocid(&updateReader);
    skipPositionList(&updateReader);
    docListSpliceElement(&accReader, iDocid, pSource, updateReader.p-pSource);
  }
}














/*
** pLeft and pRight are two DocListReaders that are pointing to
** positions lists of the same document: iDocid. 
**
** If there are no instances in pLeft or pRight where the position
** of pLeft is iOffset less than the position of pRight, then this
** routine adds nothing to pOut.
**
** If there are one or more instances where positions from pLeft
** are exactly iOffset less than positions from pRight, then add a new

** document record to pOut and include the positions from pLeft.

**
** pLeft and pRight are left pointing at the next document.
*/
static void mergePosList(
  DocListReader *pLeft,    /* Left position list */
  DocListReader *pRight,   /* Right position list */
  sqlite_int64 iDocid,     /* The docid from pLeft and pRight */
  int iOffset,             /* Copy if pLeft.pos+iOffset==pRight.iPos */
  DocList *pOut            /* Write the merged document record here */
){
  int iLeftPos = readPosition(pLeft);
  int iRightPos = readPosition(pRight);
  int match = 0;

  /* Loop until we've reached the end of both position lists. */
  while( iLeftPos!=-1 && iRightPos!=-1 ){
    if( iLeftPos+iOffset==iRightPos ){
      if( !match ){
        docListAddDocid(pOut, iDocid);
        match = 1;
      }
      if( pOut->iType>=DL_POSITIONS ){
        docListAddPos(pOut, iLeftPos);
      }
      iLeftPos = readPosition(pLeft);
      iRightPos = readPosition(pRight);
    }else if( iRightPos<iLeftPos+iOffset ){
      iRightPos = readPosition(pRight);
    }else{
      iLeftPos = readPosition(pLeft);
    }
  }
  if( iLeftPos>=0 ) skipPositionList(pLeft);
  if( iRightPos>=0 ) skipPositionList(pRight);
}



/*
** Read the next non-deleted docid off of pIn.  Return
** 0 if we reach the end of pDoclist.





*/
static sqlite_int64 nextValidDocid(DocListReader *pIn){






  sqlite_int64 docid = 0;
  while( !atEnd(pIn) && (docid = readDocid(pIn))==0 ){
    skipPositionList(pIn);
  }
  return docid;
















}

/* We have two doclists:  pLeft and pRight.
** Write the intersection of these two doclists into pOut.

**
** nLeftPhrase is the number of words of a phrase that have
** contributed to pLeft.
*/
static void mergeBlockAnd(
  DocList *pLeft,    /* Doclist resulting from the words on the left */
  DocList *pRight,   /* Doclist for the next word to the right */
  int nLeftPhrase,   /* Number of matching phrase terms in pLeft */
  DocList *pOut      /* Write the combined doclist here */
){
  DocListReader left, right;
  sqlite_int64 docidLeft, docidRight;



  readerInit(&left, pLeft);
  readerInit(&right, pRight);
  docidLeft = nextValidDocid(&left);
  docidRight = nextValidDocid(&right);

  while( docidLeft>0 && docidRight>0 ){
    if( docidLeft<docidRight ){
      skipPositionList(&left);
      docidLeft = nextValidDocid(&left);
    }else if( docidRight<docidLeft ){
      skipPositionList(&right);
      docidRight = nextValidDocid(&right);
    }else{
      /* Found a match */
      if( pLeft->iType>=DL_POSITIONS ){
        mergePosList(&left, &right, docidLeft, nLeftPhrase, pOut);
      }else{
        docListAddDocid(pOut, docidLeft);
        skipPositionList(&left);
        skipPositionList(&right);
      }
      docidLeft = nextValidDocid(&left);
      docidRight = nextValidDocid(&right);
    }
  }
}

/* We have two doclists:  pLeft and pRight.
** Write into pOut all documents that occur in pLeft but not
** in pRight.
**
** The output pOut never holds positions.
*/
static void mergeBlockExcept(
  DocList *pLeft,    /* Doclist resulting from the words on the left */
  DocList *pRight,   /* Doclist for the next word to the right */
  DocList *pOut      /* Write the combined doclist here */
){
  DocListReader left, right;
  sqlite_int64 docidLeft, docidRight, priorLeft;

  readerInit(&left, pLeft);
  readerInit(&right, pRight);
  docidLeft = nextValidDocid(&left);
  docidRight = nextValidDocid(&right);

  while( docidLeft>0 ){
    priorLeft = docidLeft;
    if( docidRight==0 || docidLeft<docidRight ){
      docListAddDocid(pOut, docidLeft);
    }
    if( docidRight==0 || docidLeft<=docidRight ){
      skipPositionList(&left);
      docidLeft = nextValidDocid(&left);
    }
    if( docidRight>0 && docidRight<=priorLeft ){
      skipPositionList(&right);
      docidRight = nextValidDocid(&right);
    }
  }
}

/* We have two doclists:  pLeft and pRight.
** Write the union of these two doclists into pOut.

**
** The output pOut never holds positions.
*/
static void mergeBlockOr(
  DocList *pLeft,    /* Doclist resulting from the words on the left */
  DocList *pRight,   /* Doclist for the next word to the right */
  DocList *pOut      /* Write the combined doclist here */
){
  DocListReader left, right;
  sqlite_int64 docidLeft, docidRight, priorLeft;

................................................................................
    if( docidLeft<=docidRight ){
      docListAddDocid(pOut, docidLeft);
    }else{
      docListAddDocid(pOut, docidRight);
    }
    priorLeft = docidLeft;
    if( docidLeft<=docidRight ){
      skipPositionList(&left);
      docidLeft = nextValidDocid(&left);
    }
    if( docidRight>0 && docidRight<=priorLeft ){
      skipPositionList(&right);
      docidRight = nextValidDocid(&right);
    }
  }
  while( docidLeft>0 ){
    docListAddDocid(pOut, docidLeft);
    skipPositionList(&left);
    docidLeft = nextValidDocid(&left);
  }
  while( docidRight>0 ){
    docListAddDocid(pOut, docidRight);
    skipPositionList(&right);
    docidRight = nextValidDocid(&right);
  }







































}

/* Duplicate a string; the caller must free() the returned string.
 * (We don't use strdup() since it's not part of the standard C library and
 * may not be available everywhere.) */
static char *string_dup(const char *s){
  int n = strlen(s);
................................................................................
          c->eof = 1;
          return rc;
      }
    case QUERY_FULLTEXT:
      rc = sqlite3_reset(c->pStmt);
      if( rc!=SQLITE_OK ) return rc;

      if( atEnd(&c->result)){

        c->eof = 1;
        return SQLITE_OK;
      }
      iDocid = readDocid(&c->result);
      rc = sqlite3_bind_int64(c->pStmt, 1, iDocid);
      if( rc!=SQLITE_OK ) return rc;
      /* TODO(shess) Handle SQLITE_SCHEMA AND SQLITE_BUSY. */
      rc = sqlite3_step(c->pStmt);
      if( rc==SQLITE_ROW ){   /* the case we expect */
        c->eof = 0;
        return SQLITE_OK;
................................................................................
      return rc==SQLITE_DONE ? SQLITE_ERROR : rc;
    default:
      assert( 0 );
      return SQLITE_ERROR;  /* not reached */
  }
}

/*
** Different kinds of allowed document merge operations.
*/
#define MERGE_AND    1     /* Intersection of left and right */
#define MERGE_OR     2     /* Union of left and right */
#define MERGE_EXCEPT 3     /* Documents in left but not in right */

/* Read the posting list for [pTerm]; AND it with the doclist [pIn] to
 * produce the doclist [out], using the given phrase position [iPhrasePos].
 * (*pSelect) is used to hold an SQLite statement used inside this function;
 * the caller should initialize *pSelect to NULL before the first call.
 */
static int mergeQuery(
  fulltext_vtab *v,              /* The full text index virtual table */
  const char *pTerm, int nTerm,  /* Term we are searching for */
  DocList *pIn,                  /* Prior search results. NULL for first term */
  int iPhrasePos,                /* Offset to first term of phrase search */
  int eOp,                       /* MERGE_AND, MERGE_OR, or MERGE_EXCEPT */
  DocList *out                   /* Write results here */
){
  int rc;
  DocList doclist;

  /* If [pIn] is already empty, there's no point in reading the
   * posting list to AND it in; return immediately. */
  if( pIn!=NULL && eOp==MERGE_AND && !pIn->nData ) return SQLITE_OK;

  rc = term_select_all(v, pTerm, nTerm, &doclist);
  if( rc!=SQLITE_OK ) return rc;

  /* If there is no input and the output wants to contain position
  ** information, then make the result the doclist for pTerm.
  */
  if( pIn==0 && out->iType>=DL_POSITIONS ){
    docListDestroy(out);
    *out = doclist;
    return SQLITE_OK;
  }

  if( eOp==MERGE_AND && pIn!=0 ){
    mergeBlockAnd(pIn, &doclist, iPhrasePos, out);
  }else if( eOp==MERGE_OR || pIn==0 ){
    mergeBlockOr(pIn, &doclist, out);
  }else if( eOp==MERGE_EXCEPT ){
    mergeBlockExcept(pIn, &doclist, out);
  }
  docListDestroy(&doclist);

  return SQLITE_OK;
}

/* A single term in a query is represented by an instances of
** the following structure.
*/
typedef struct QueryTerm {
  int firstInPhrase; /* true if this term begins a new phrase */

  int isOr;          /* this term is preceded by "OR" */
  int isNot;         /* this term is preceded by "-" */
  char *pTerm;       /* text of the term.  '\000' terminated.  malloced */
  int nTerm;         /* Number of bytes in pTerm[] */
} QueryTerm;

/* A parsed query.






































 *
 * We could, in theory, allow query strings to be complicated
 * nested expressions with precedence determined by parentheses.
 * But none of the major search engines do this.  (Perhaps the
 * feeling is that an parenthesized expression is two complex of
 * an idea for the average user to grasp.)  Taking our lead from
 * the major search engines, we will allow queries to be a list
................................................................................
 *
 *    [one OR -two]          ==>    one OR two
 *
 */
typedef struct Query {
  int nTerms;           /* Number of terms in the query */
  QueryTerm *pTerms;    /* Array of terms.  Space obtained from malloc() */

} Query;

/* Add a new term pTerm[0..nTerm-1] to the query *q.  The new term is
** the beginning of a phrase is firstInPhrase is true.
*/
static void queryAdd(Query *q, int firstInPhrase, const char *pTerm, int nTerm){
  QueryTerm *t;
  ++q->nTerms;
  q->pTerms = realloc(q->pTerms, q->nTerms * sizeof(q->pTerms[0]));
  if( q->pTerms==0 ){
    q->nTerms = 0;
    return;
  }
  t = &q->pTerms[q->nTerms - 1];
  memset(t, 0, sizeof(*t));
  t->firstInPhrase = firstInPhrase;
  t->pTerm = malloc(nTerm+1);
  memcpy(t->pTerm, pTerm, nTerm);
  t->pTerm[nTerm] = 0;
  t->nTerm = nTerm;


}

/* Free all of the memory that was malloced in order to build *q.
*/
static void queryDestroy(Query *q){
  int i;
  for(i = 0; i < q->nTerms; ++i){
................................................................................
}

/*
** Parse the text at pSegment[0..nSegment-1].  Add additional terms
** to the query being assemblied in pQuery.
**
** inPhrase is true if pSegment[0..nSegement-1] is contained within
** double-quotes.  If inPhrase is true, then only the first term
** is marked with firstInPhrase and OR and "-" syntax is ignored.
** If inPhrase is false, then every term found is marked with
** firstInPhrase and OR and "-" syntax is significant.
*/
static int tokenizeSegment(sqlite3_tokenizer *pTokenizer,

                            const char *pSegment, int nSegment, int inPhrase,
                            Query *pQuery){



  const sqlite3_tokenizer_module *pModule = pTokenizer->pModule;
  sqlite3_tokenizer_cursor *pCursor;
  int is_first = 1;
  int isOr = 0;

  
  int rc = pModule->xOpen(pTokenizer, pSegment, nSegment, &pCursor);
  if( rc!=SQLITE_OK ) return rc;
  pCursor->pTokenizer = pTokenizer;

  while( 1 ){
    const char *pToken;
................................................................................

    rc = pModule->xNext(pCursor,
                        &pToken, &nToken,
                        &iBegin, &iEnd, &iPos);
    if( rc!=SQLITE_OK ) break;
    if( !inPhrase && pQuery->nTerms>0 && nToken==2
         && pSegment[iBegin]=='O' && pSegment[iBegin+1]=='R' ){
      isOr = 1;
      continue;
    }
    queryAdd(pQuery, !inPhrase || is_first, pToken, nToken);
    if( !inPhrase ){
      if( isOr ){
        pQuery->pTerms[pQuery->nTerms-1].isOr = 1;
      }else if( iBegin>0 && pSegment[iBegin-1]=='-' ){
        pQuery->pTerms[pQuery->nTerms-1].isNot = 1;
      }
    }
    is_first = 0;
    isOr = 0;



  }

  return pModule->xClose(pCursor);
}

/* Parse a query string, yielding a Query object [pQuery], which the caller
 * must free. */
................................................................................
static int parseQuery(fulltext_vtab *v, const char *pInput, int nInput,
                      Query *pQuery){
  int iInput, inPhrase = 0;

  if( nInput<0 ) nInput = strlen(pInput);
  pQuery->nTerms = 0;
  pQuery->pTerms = NULL;


  for(iInput=0; iInput<nInput; ++iInput){
    int i;
    for(i=iInput; i<nInput && pInput[i]!='"'; ++i)
      ;
    if( i>iInput ){
      tokenizeSegment(v->pTokenizer, pInput+iInput, i-iInput, inPhrase,
................................................................................
/* Perform a full-text query using the search expression in
** pInput[0..nInput-1].  Return a list of matching documents
** in pResult.
*/
static int fulltextQuery(fulltext_vtab *v, const char *pInput, int nInput,
                          DocList **pResult){
  Query q;
  int phrase_start = -1;
  int i;
  DocList *d = NULL;



  int rc = parseQuery(v, pInput, nInput, &q);
  if( rc!=SQLITE_OK ) return rc;

  /* Merge AND terms. */
  for(i = 0 ; i < q.nTerms ; ++i){
    int needPositions;
    DocList *next;

    if( q.pTerms[i].isNot || q.pTerms[i].isOr ){
      /* Handle all OR and NOT terms in a separate pass */

      continue;
    }

    /* In each merge step, we need to generate positions whenever we're
     * processing a phrase which hasn't ended yet. */
    needPositions = i<q.nTerms-1 && !q.pTerms[i+1].firstInPhrase;
    next = docListNew(needPositions ? DL_POSITIONS : DL_DOCIDS);
    if( q.pTerms[i].firstInPhrase ){
      phrase_start = i;
    }
    rc = mergeQuery(v, q.pTerms[i].pTerm, q.pTerms[i].nTerm,
                     d, i-phrase_start, MERGE_AND, next);
    if( rc!=SQLITE_OK ) break;
    if( d!=NULL ){
      docListDelete(d);
    }
    d = next;
  }

  /* Do the OR terms */
  for(i=0; i<q.nTerms; i++){
    DocList *next;
    if( !q.pTerms[i].isOr ) continue;
    next = docListNew(DL_DOCIDS);
    rc = mergeQuery(v, q.pTerms[i].pTerm, q.pTerms[i].nTerm,
                    d, 0, MERGE_OR, next);
    if( d ){
      docListDelete(d);
    }
    d = next;
  }

  /* Do the EXCEPT terms */
  for(i=0; i<q.nTerms; i++){
    DocList *next;
    if( !q.pTerms[i].isNot ) continue;
    next = docListNew(DL_DOCIDS);
    rc = mergeQuery(v, q.pTerms[i].pTerm, q.pTerms[i].nTerm,
                    d, 0, MERGE_EXCEPT, next);
    if( d ){
      docListDelete(d);
    }
    d = next;
  }

  queryDestroy(&q);
  *pResult = d;
  return rc;
}

static int fulltextFilter(sqlite3_vtab_cursor *pCursor,
                          int idxNum, const char *idxStr,
                          int argc, sqlite3_value **argv){
  fulltext_cursor *c = (fulltext_cursor *) pCursor;

  sqlite_int64 ret;
  assert( !atEnd(pReader) );
  assert( pReader->iLastPos==-1 );
  getVarint(pReader->p, &ret);
  return ret;
}

/* Read the next docid.   See also nextValidDocid().
*/
static sqlite_int64 readDocid(DocListReader *pReader){
  sqlite_int64 ret;
  assert( !atEnd(pReader) );
  assert( pReader->iLastPos==-1 );
  pReader->p += getVarint(pReader->p, &ret);
  if( pReader->pDoclist->iType>=DL_POSITIONS ){
................................................................................

/* Read the next position from a position list.
 * Returns the position, or -1 at the end of the list. */
static int readPosition(DocListReader *pReader){
  int i;
  int iType = pReader->pDoclist->iType;

  if( pReader->iLastPos==-1 ){
    return -1;
  }
  assert( !atEnd(pReader) );


  if( iType<DL_POSITIONS ){
    return -1;
  }
  pReader->p += getVarint32(pReader->p, &i);
  if( i==0 ){
    pReader->iLastPos = -1;
................................................................................
  while( !atEnd(&updateReader) ){
    char *pSource = updateReader.p;
    sqlite_int64 iDocid = readDocid(&updateReader);
    skipPositionList(&updateReader);
    docListSpliceElement(&accReader, iDocid, pSource, updateReader.p-pSource);
  }
}

/*
** Read the next non-deleted docid off of pIn.  Return
** 0 if we reach the end of pDoclist.
*/
static sqlite_int64 nextValidDocid(DocListReader *pIn){
  sqlite_int64 docid = 0;
  skipPositionList(pIn);
  while( !atEnd(pIn) && (docid = readDocid(pIn))==0 ){
    skipPositionList(pIn);
  }
  return docid;
}

/*
** pLeft and pRight are two DocListReaders that are pointing to
** positions lists of the same document: iDocid. 
**
** If there are no instances in pLeft or pRight where the position
** of pLeft is one less than the position of pRight, then this
** routine adds nothing to pOut.
**
** If there are one or more instances where positions from pLeft
** are exactly one less than positions from pRight, then add a new
** document record to pOut.  If pOut wants to hold positions, then
** include the positions from pRight that are one more than a
** position in pLeft.  In other words:  pRight.iPos==pLeft.iPos+1.
**
** pLeft and pRight are left pointing at the next document record.
*/
static void mergePosList(
  DocListReader *pLeft,    /* Left position list */
  DocListReader *pRight,   /* Right position list */
  sqlite_int64 iDocid,     /* The docid from pLeft and pRight */

  DocList *pOut            /* Write the merged document record here */
){
  int iLeftPos = readPosition(pLeft);
  int iRightPos = readPosition(pRight);
  int match = 0;

  /* Loop until we've reached the end of both position lists. */
  while( iLeftPos!=-1 && iRightPos!=-1 ){
    if( iLeftPos+1==iRightPos ){
      if( !match ){
        docListAddDocid(pOut, iDocid);
        match = 1;
      }
      if( pOut->iType>=DL_POSITIONS ){
        docListAddPos(pOut, iRightPos);
      }
      iLeftPos = readPosition(pLeft);
      iRightPos = readPosition(pRight);
    }else if( iRightPos<iLeftPos+1 ){
      iRightPos = readPosition(pRight);
    }else{
      iLeftPos = readPosition(pLeft);
    }
  }
  if( iLeftPos>=0 ) skipPositionList(pLeft);
  if( iRightPos>=0 ) skipPositionList(pRight);
}

/* We have two doclists:  pLeft and pRight.
** Write the phrase intersection of these two doclists into pOut.
**


** A phrase intersection means that two documents only match
** if pLeft.iPos+1==pRight.iPos.
**
** The output pOut may or may not contain positions.  If pOut
** does contain positions, they are the positions of pRight.
*/

static void docListPhraseMerge(
  DocList *pLeft,    /* Doclist resulting from the words on the left */
  DocList *pRight,   /* Doclist for the next word to the right */
  DocList *pOut      /* Write the combined doclist here */
){
  DocListReader left, right;
  sqlite_int64 docidLeft, docidRight;




  readerInit(&left, pLeft);
  readerInit(&right, pRight);
  docidLeft = nextValidDocid(&left);
  docidRight = nextValidDocid(&right);

  while( docidLeft>0 && docidRight>0 ){
    if( docidLeft<docidRight ){
      docidLeft = nextValidDocid(&left);
    }else if( docidRight<docidLeft ){
      docidRight = nextValidDocid(&right);
    }else{
      mergePosList(&left, &right, docidLeft, pOut);
      docidLeft = nextValidDocid(&left);
      docidRight = nextValidDocid(&right);
    }
  }
}

/* We have two doclists:  pLeft and pRight.
** Write the intersection of these two doclists into pOut.
** Only docids are matched.  Position information is ignored.
**

** The output pOut never holds positions.
*/
static void docListAndMerge(
  DocList *pLeft,    /* Doclist resulting from the words on the left */
  DocList *pRight,   /* Doclist for the next word to the right */

  DocList *pOut      /* Write the combined doclist here */
){
  DocListReader left, right;
  sqlite_int64 docidLeft, docidRight;

  assert( pOut->iType<DL_POSITIONS );

  readerInit(&left, pLeft);
  readerInit(&right, pRight);
  docidLeft = nextValidDocid(&left);
  docidRight = nextValidDocid(&right);

  while( docidLeft>0 && docidRight>0 ){
    if( docidLeft<docidRight ){

      docidLeft = nextValidDocid(&left);
    }else if( docidRight<docidLeft ){

      docidRight = nextValidDocid(&right);
    }else{




      docListAddDocid(pOut, docidLeft);



      docidLeft = nextValidDocid(&left);
      docidRight = nextValidDocid(&right);
    }
  }
}

/* We have two doclists:  pLeft and pRight.



































** Write the union of these two doclists into pOut.
** Only docids are matched.  Position information is ignored.
**
** The output pOut never holds positions.
*/
static void docListOrMerge(
  DocList *pLeft,    /* Doclist resulting from the words on the left */
  DocList *pRight,   /* Doclist for the next word to the right */
  DocList *pOut      /* Write the combined doclist here */
){
  DocListReader left, right;
  sqlite_int64 docidLeft, docidRight, priorLeft;

................................................................................
    if( docidLeft<=docidRight ){
      docListAddDocid(pOut, docidLeft);
    }else{
      docListAddDocid(pOut, docidRight);
    }
    priorLeft = docidLeft;
    if( docidLeft<=docidRight ){

      docidLeft = nextValidDocid(&left);
    }
    if( docidRight>0 && docidRight<=priorLeft ){

      docidRight = nextValidDocid(&right);
    }
  }
  while( docidLeft>0 ){
    docListAddDocid(pOut, docidLeft);

    docidLeft = nextValidDocid(&left);
  }
  while( docidRight>0 ){
    docListAddDocid(pOut, docidRight);

    docidRight = nextValidDocid(&right);
  }
}

/* We have two doclists:  pLeft and pRight.
** Write into pOut all documents that occur in pLeft but not
** in pRight.
**
** Only docids are matched.  Position information is ignored.
**
** The output pOut never holds positions.
*/
static void docListExceptMerge(
  DocList *pLeft,    /* Doclist resulting from the words on the left */
  DocList *pRight,   /* Doclist for the next word to the right */
  DocList *pOut      /* Write the combined doclist here */
){
  DocListReader left, right;
  sqlite_int64 docidLeft, docidRight, priorLeft;

  readerInit(&left, pLeft);
  readerInit(&right, pRight);
  docidLeft = nextValidDocid(&left);
  docidRight = nextValidDocid(&right);

  while( docidLeft>0 && docidRight>0 ){
    priorLeft = docidLeft;
    if( docidLeft<docidRight ){
      docListAddDocid(pOut, docidLeft);
    }
    if( docidLeft<=docidRight ){
      docidLeft = nextValidDocid(&left);
    }
    if( docidRight>0 && docidRight<=priorLeft ){
      docidRight = nextValidDocid(&right);
    }
  }
  while( docidLeft>0 ){
    docListAddDocid(pOut, docidLeft);
    docidLeft = nextValidDocid(&left);
  }
}

/* Duplicate a string; the caller must free() the returned string.
 * (We don't use strdup() since it's not part of the standard C library and
 * may not be available everywhere.) */
static char *string_dup(const char *s){
  int n = strlen(s);
................................................................................
          c->eof = 1;
          return rc;
      }
    case QUERY_FULLTEXT:
      rc = sqlite3_reset(c->pStmt);
      if( rc!=SQLITE_OK ) return rc;

      iDocid = nextValidDocid(&c->result);
      if( iDocid==0 ){
        c->eof = 1;
        return SQLITE_OK;
      }

      rc = sqlite3_bind_int64(c->pStmt, 1, iDocid);
      if( rc!=SQLITE_OK ) return rc;
      /* TODO(shess) Handle SQLITE_SCHEMA AND SQLITE_BUSY. */
      rc = sqlite3_step(c->pStmt);
      if( rc==SQLITE_ROW ){   /* the case we expect */
        c->eof = 0;
        return SQLITE_OK;
................................................................................
      return rc==SQLITE_DONE ? SQLITE_ERROR : rc;
    default:
      assert( 0 );
      return SQLITE_ERROR;  /* not reached */
  }
}




















































/* A single term in a query is represented by an instances of
** the following structure.
*/
typedef struct QueryTerm {

  int nPhrase;       /* How many following terms are part of the same phrase */
  int isOr;          /* this term is preceded by "OR" */
  int isNot;         /* this term is preceded by "-" */
  char *pTerm;       /* text of the term.  '\000' terminated.  malloced */
  int nTerm;         /* Number of bytes in pTerm[] */
} QueryTerm;



/* Return a DocList corresponding to the query term *pTerm.  If *pTerm
** is the first term of a phrase query, go ahead and evaluate the phrase
** query and return the doclist for the entire phrase query.
**
** The result is stored in pTerm->doclist.
*/
static int docListOfTerm(
  fulltext_vtab *v,     /* The full text index */
  QueryTerm *pQTerm,    /* Term we are looking for, or 1st term of a phrase */
  DocList **ppResult    /* Write the result here */
){
  DocList *pLeft, *pRight, *pNew;
  int i, rc;

  pLeft = docListNew(DL_POSITIONS);
  rc = term_select_all(v, pQTerm->pTerm, pQTerm->nTerm, pLeft);
  if( rc ) return rc;
  for(i=1; i<=pQTerm->nPhrase; i++){
    pRight = docListNew(DL_POSITIONS);
    rc = term_select_all(v, pQTerm[i].pTerm, pQTerm[i].nTerm, pRight);
    if( rc ){
      docListDelete(pLeft);
      return rc;
    }
    pNew = docListNew(i<pQTerm->nPhrase ? DL_POSITIONS : DL_DOCIDS);
    docListPhraseMerge(pLeft, pRight, pNew);
    docListDelete(pLeft);
    docListDelete(pRight);
    pLeft = pNew;
  }
  *ppResult = pLeft;
  return SQLITE_OK;
}



/* Parse a query string into a Query structure.
 *
 * We could, in theory, allow query strings to be complicated
 * nested expressions with precedence determined by parentheses.
 * But none of the major search engines do this.  (Perhaps the
 * feeling is that an parenthesized expression is two complex of
 * an idea for the average user to grasp.)  Taking our lead from
 * the major search engines, we will allow queries to be a list
................................................................................
 *
 *    [one OR -two]          ==>    one OR two
 *
 */
typedef struct Query {
  int nTerms;           /* Number of terms in the query */
  QueryTerm *pTerms;    /* Array of terms.  Space obtained from malloc() */
  int nextIsOr;         /* Set the isOr flag on the next inserted term */
} Query;

/* Add a new term pTerm[0..nTerm-1] to the query *q.

*/
static void queryAdd(Query *q, const char *pTerm, int nTerm){
  QueryTerm *t;
  ++q->nTerms;
  q->pTerms = realloc(q->pTerms, q->nTerms * sizeof(q->pTerms[0]));
  if( q->pTerms==0 ){
    q->nTerms = 0;
    return;
  }
  t = &q->pTerms[q->nTerms - 1];
  memset(t, 0, sizeof(*t));

  t->pTerm = malloc(nTerm+1);
  memcpy(t->pTerm, pTerm, nTerm);
  t->pTerm[nTerm] = 0;
  t->nTerm = nTerm;
  t->isOr = q->nextIsOr;
  q->nextIsOr = 0;
}

/* Free all of the memory that was malloced in order to build *q.
*/
static void queryDestroy(Query *q){
  int i;
  for(i = 0; i < q->nTerms; ++i){
................................................................................
}

/*
** Parse the text at pSegment[0..nSegment-1].  Add additional terms
** to the query being assemblied in pQuery.
**
** inPhrase is true if pSegment[0..nSegement-1] is contained within
** double-quotes.  If inPhrase is true, then the first term
** is marked with the number of terms in the phrase less one and
** OR and "-" syntax is ignored.  If inPhrase is false, then every
** term found is marked with nPhrase=0 and OR and "-" syntax is significant.
*/
static int tokenizeSegment(
  sqlite3_tokenizer *pTokenizer,          /* The tokenizer to use */
  const char *pSegment, int nSegment,     /* Query expression being parsed */

  int inPhrase,                           /* True if within "..." */
  Query *pQuery                           /* Append results here */
){
  const sqlite3_tokenizer_module *pModule = pTokenizer->pModule;
  sqlite3_tokenizer_cursor *pCursor;


  int firstIndex = pQuery->nTerms;
  
  int rc = pModule->xOpen(pTokenizer, pSegment, nSegment, &pCursor);
  if( rc!=SQLITE_OK ) return rc;
  pCursor->pTokenizer = pTokenizer;

  while( 1 ){
    const char *pToken;
................................................................................

    rc = pModule->xNext(pCursor,
                        &pToken, &nToken,
                        &iBegin, &iEnd, &iPos);
    if( rc!=SQLITE_OK ) break;
    if( !inPhrase && pQuery->nTerms>0 && nToken==2
         && pSegment[iBegin]=='O' && pSegment[iBegin+1]=='R' ){
      pQuery->nextIsOr = 1;
      continue;
    }
    queryAdd(pQuery, pToken, nToken);



    if( !inPhrase && iBegin>0 && pSegment[iBegin-1]=='-' ){
      pQuery->pTerms[pQuery->nTerms-1].isNot = 1;
    }
  }



  if( inPhrase && pQuery->nTerms>firstIndex ){
    pQuery->pTerms[firstIndex].nPhrase = pQuery->nTerms - firstIndex - 1;
  }

  return pModule->xClose(pCursor);
}

/* Parse a query string, yielding a Query object [pQuery], which the caller
 * must free. */
................................................................................
static int parseQuery(fulltext_vtab *v, const char *pInput, int nInput,
                      Query *pQuery){
  int iInput, inPhrase = 0;

  if( nInput<0 ) nInput = strlen(pInput);
  pQuery->nTerms = 0;
  pQuery->pTerms = NULL;
  pQuery->nextIsOr = 0;

  for(iInput=0; iInput<nInput; ++iInput){
    int i;
    for(i=iInput; i<nInput && pInput[i]!='"'; ++i)
      ;
    if( i>iInput ){
      tokenizeSegment(v->pTokenizer, pInput+iInput, i-iInput, inPhrase,
................................................................................
/* Perform a full-text query using the search expression in
** pInput[0..nInput-1].  Return a list of matching documents
** in pResult.
*/
static int fulltextQuery(fulltext_vtab *v, const char *pInput, int nInput,
                          DocList **pResult){
  Query q;

  int i, rc;
  DocList *pLeft = NULL;
  DocList *pRight, *pNew;
  int nNot = 0;

  rc = parseQuery(v, pInput, nInput, &q);
  if( rc!=SQLITE_OK ) return rc;

  /* Merge AND terms. */
  for(i = 0 ; i < q.nTerms; i += q.pTerms[i].nPhrase + 1){



    if( q.pTerms[i].isNot ){
      /* Handle all NOT terms in a separate pass */
      nNot++;
      continue;
    }

    rc = docListOfTerm(v, &q.pTerms[i], &pRight);
    if( rc ){
      queryDestroy(&q);
      return rc;
    }
    if( pLeft==0 ){
      pLeft = pRight;
    }else{
      pNew = docListNew(DL_DOCIDS);
      if( q.pTerms[i].isOr ){
        docListOrMerge(pLeft, pRight, pNew);
      }else{
        docListAndMerge(pLeft, pRight, pNew);
      }
      docListDelete(pRight);
      docListDelete(pLeft);
      pLeft = pNew;
    }
  }

  if( nNot && pLeft==0 ){
    /* We do not yet know how to handle a query of only NOT terms */
    return SQLITE_ERROR;
  }


  /* Do the EXCEPT terms */
  for(i=0; i<q.nTerms;  i += q.pTerms[i].nPhrase + 1){
    if( !q.pTerms[i].isNot ) continue;
    rc = docListOfTerm(v, &q.pTerms[i], &pRight);
    if( rc ){
      queryDestroy(&q);
      docListDelete(pLeft);
      return rc;
    }
    pNew = docListNew(DL_DOCIDS);
    docListExceptMerge(pLeft, pRight, pNew);
    docListDelete(pRight);
    docListDelete(pLeft);
    pLeft = pNew;
  }

  queryDestroy(&q);
  *pResult = pLeft;
  return rc;
}

static int fulltextFilter(sqlite3_vtab_cursor *pCursor,
                          int idxNum, const char *idxStr,
                          int argc, sqlite3_value **argv){
  fulltext_cursor *c = (fulltext_cursor *) pCursor;

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing all sorts of SQLite interfaces.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test1.c,v 1.219 2006/09/04 15:53:53 drh Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include "os.h"
#include <stdlib.h>
#include <string.h>

................................................................................
#endif

#ifdef SQLITE_OMIT_FOREIGN_KEY
  Tcl_SetVar2(interp, "sqlite_options", "foreignkey", "0", TCL_GLOBAL_ONLY);
#else
  Tcl_SetVar2(interp, "sqlite_options", "foreignkey", "1", TCL_GLOBAL_ONLY);
#endif







#ifdef SQLITE_OMIT_GLOBALRECOVER
  Tcl_SetVar2(interp, "sqlite_options", "globalrecover", "0", TCL_GLOBAL_ONLY);
#else
  Tcl_SetVar2(interp, "sqlite_options", "globalrecover", "1", TCL_GLOBAL_ONLY);
#endif

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing all sorts of SQLite interfaces.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test1.c,v 1.220 2006/09/10 03:34:06 drh Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include "os.h"
#include <stdlib.h>
#include <string.h>

................................................................................
#endif

#ifdef SQLITE_OMIT_FOREIGN_KEY
  Tcl_SetVar2(interp, "sqlite_options", "foreignkey", "0", TCL_GLOBAL_ONLY);
#else
  Tcl_SetVar2(interp, "sqlite_options", "foreignkey", "1", TCL_GLOBAL_ONLY);
#endif

#ifdef SQLITE_ENABLE_FTS1
  Tcl_SetVar2(interp, "sqlite_options", "fts1", "1", TCL_GLOBAL_ONLY);
#else
  Tcl_SetVar2(interp, "sqlite_options", "fts1", "0", TCL_GLOBAL_ONLY);
#endif

#ifdef SQLITE_OMIT_GLOBALRECOVER
  Tcl_SetVar2(interp, "sqlite_options", "globalrecover", "0", TCL_GLOBAL_ONLY);
#else
  Tcl_SetVar2(interp, "sqlite_options", "globalrecover", "1", TCL_GLOBAL_ONLY);
#endif

# 2006 September 9
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#*************************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is testing the FTS1 module.
#
# $Id: fts1a.test,v 1.1 2006/09/10 03:34:06 drh Exp $
#

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

# If SQLITE_ENABLE_FTS1 is defined, omit this file.
ifcapable !fts1 {
  finish_test
  return
}

# Construct a full-text search table containing five keywords:
# one, two, three, four, and five, in various combinations.  The
# rowid for each will be a bitmask for the elements it contains.
#
db eval {
  CREATE VIRTUAL TABLE t1 USING fts1;
  INSERT INTO t1(content) VALUES('one');
  INSERT INTO t1(content) VALUES('two');
  INSERT INTO t1(content) VALUES('one two');
  INSERT INTO t1(content) VALUES('three');
  INSERT INTO t1(content) VALUES('one three');
  INSERT INTO t1(content) VALUES('two three');
  INSERT INTO t1(content) VALUES('one two three');
  INSERT INTO t1(content) VALUES('four');
  INSERT INTO t1(content) VALUES('one four');
  INSERT INTO t1(content) VALUES('two four');
  INSERT INTO t1(content) VALUES('one two four');
  INSERT INTO t1(content) VALUES('three four');
  INSERT INTO t1(content) VALUES('one three four');
  INSERT INTO t1(content) VALUES('two three four');
  INSERT INTO t1(content) VALUES('one two three four');
  INSERT INTO t1(content) VALUES('five');
  INSERT INTO t1(content) VALUES('one five');
  INSERT INTO t1(content) VALUES('two five');
  INSERT INTO t1(content) VALUES('one two five');
  INSERT INTO t1(content) VALUES('three five');
  INSERT INTO t1(content) VALUES('one three five');
  INSERT INTO t1(content) VALUES('two three five');
  INSERT INTO t1(content) VALUES('one two three five');
  INSERT INTO t1(content) VALUES('four five');
  INSERT INTO t1(content) VALUES('one four five');
  INSERT INTO t1(content) VALUES('two four five');
  INSERT INTO t1(content) VALUES('one two four five');
  INSERT INTO t1(content) VALUES('three four five');
  INSERT INTO t1(content) VALUES('one three four five');
  INSERT INTO t1(content) VALUES('two three four five');
  INSERT INTO t1(content) VALUES('one two three four five');
}

do_test fts1a-1.1 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH 'one'}
} {1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31}
do_test fts1a-1.2 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH 'one two'}
} {3 7 11 15 19 23 27 31}
do_test fts1a-1.3 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH 'two one'}
} {3 7 11 15 19 23 27 31}
do_test fts1a-1.4 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH 'one two three'}
} {7 15 23 31}
do_test fts1a-1.5 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH 'one three two'}
} {7 15 23 31}
do_test fts1a-1.6 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH 'two three one'}
} {7 15 23 31}
do_test fts1a-1.7 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH 'two one three'}
} {7 15 23 31}
do_test fts1a-1.8 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH 'three one two'}
} {7 15 23 31}
do_test fts1a-1.9 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH 'three two one'}
} {7 15 23 31}
do_test fts1a-1.10 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH 'one two THREE'}
} {7 15 23 31}
do_test fts1a-1.11 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH '  ONE    Two   three  '}
} {7 15 23 31}

do_test fts1a-2.1 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH '"one"'}
} {1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31}
do_test fts1a-2.2 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH '"one two"'}
} {3 7 11 15 19 23 27 31}
do_test fts1a-2.3 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH '"two one"'}
} {}
do_test fts1a-2.4 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH '"one two three"'}
} {7 15 23 31}
do_test fts1a-2.5 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH '"one three two"'}
} {}
do_test fts1a-2.6 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH '"one two three four"'}
} {15 31}
do_test fts1a-2.7 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH '"one three two four"'}
} {}
do_test fts1a-2.8 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH '"one three five"'}
} {21}
do_test fts1a-2.9 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH '"one three" five'}
} {21 29}
do_test fts1a-2.10 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH 'five "one three"'}
} {21 29}
do_test fts1a-2.11 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH 'five "one three" four'}
} {29}
do_test fts1a-2.12 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH 'five four "one three"'}
} {29}
do_test fts1a-2.13 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH '"one three" four five'}
} {29}

do_test fts1a-3.1 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH 'one'}
} {1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31}
do_test fts1a-3.2 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH 'one -two'}
} {1 5 9 13 17 21 25 29}
do_test fts1a-3.3 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH '-two one'}
} {1 5 9 13 17 21 25 29}

do_test fts1a-4.1 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH 'one OR two'}
} {1 2 3 5 6 7 9 10 11 13 14 15 17 18 19 21 22 23 25 26 27 29 30 31}
do_test fts1a-4.2 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH '"one two" OR three'}
} {3 4 5 6 7 11 12 13 14 15 19 20 21 22 23 27 28 29 30 31}
do_test fts1a-4.3 {
  execsql {SELECT rowid FROM t1 WHERE content MATCH 'three OR "one two"'}
} {3 4 5 6 7 11 12 13 14 15 19 20 21 22 23 27 28 29 30 31}

finish_test