Import SQLite 3.10.2.

third_party/sqlite/src/ext/fts3/fts3.c

 /*
 ** 2006 Oct 10
 **
 ** 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.
 **
@@ skipping 296 matching lines @@
 #ifndef SQLITE_CORE 
 # include "sqlite3ext.h"
   SQLITE_EXTENSION_INIT1
 #endif
 
 static int fts3EvalNext(Fts3Cursor *pCsr);
 static int fts3EvalStart(Fts3Cursor *pCsr);
 static int fts3TermSegReaderCursor(
     Fts3Cursor *, const char *, int, int, Fts3MultiSegReader **);
 
+#ifndef SQLITE_AMALGAMATION
+# if defined(SQLITE_DEBUG)
+int sqlite3Fts3Always(int b) { assert( b ); return b; }
+int sqlite3Fts3Never(int b)  { assert( !b ); return b; }
+# endif
+#endif
+
 /* 
 ** Write a 64-bit variable-length integer to memory starting at p[0].
 ** The length of data written will be between 1 and FTS3_VARINT_MAX bytes.
 ** The number of bytes written is returned.
 */
 int sqlite3Fts3PutVarint(char *p, sqlite_int64 v){
   unsigned char *q = (unsigned char *) p;
   sqlite_uint64 vu = v;
   do{
     *q++ = (unsigned char) ((vu & 0x7f) | 0x80);
@@ skipping 89 matching lines @@
   char quote;                     /* Quote character (if any ) */
 
   quote = z[0];
   if( quote=='[' || quote=='\'' || quote=='"' || quote=='`' ){
     int iIn = 1;                  /* Index of next byte to read from input */
     int iOut = 0;                 /* Index of next byte to write to output */
 
     /* If the first byte was a '[', then the close-quote character is a ']' */
     if( quote=='[' ) quote = ']';  
 
-    while( ALWAYS(z[iIn]) ){
+    while( z[iIn] ){
       if( z[iIn]==quote ){
         if( z[iIn+1]!=quote ) break;
         z[iOut++] = quote;
         iIn += 2;
       }else{
         z[iOut++] = z[iIn++];
       }
     }
     z[iOut] = '\0';
   }
@@ skipping 59 matching lines @@
   sqlite3_free(p->zLanguageid);
 
   /* Invoke the tokenizer destructor to free the tokenizer. */
   p->pTokenizer->pModule->xDestroy(p->pTokenizer);
 
   sqlite3_free(p);
   return SQLITE_OK;
 }
 
 /*
+** Write an error message into *pzErr
+*/
+void sqlite3Fts3ErrMsg(char **pzErr, const char *zFormat, ...){
+  va_list ap;
+  sqlite3_free(*pzErr);
+  va_start(ap, zFormat);
+  *pzErr = sqlite3_vmprintf(zFormat, ap);
+  va_end(ap);
+}
+
+/*
 ** Construct one or more SQL statements from the format string given
 ** and then evaluate those statements. The success code is written
 ** into *pRc.
 **
 ** If *pRc is initially non-zero then this routine is a no-op.
 */
 static void fts3DbExec(
   int *pRc,              /* Success code */
   sqlite3 *db,           /* Database in which to run SQL */
   const char *zFormat,   /* Format string for SQL */
@@ skipping 388 matching lines @@
 ** the integer value.
 **
 ** Only decimal digits ('0'..'9') may be part of an integer value. 
 **
 ** If *pp does not being with a decimal digit SQLITE_ERROR is returned and
 ** the output value undefined. Otherwise SQLITE_OK is returned.
 **
 ** This function is used when parsing the "prefix=" FTS4 parameter.
 */
 static int fts3GobbleInt(const char **pp, int *pnOut){
+  const int MAX_NPREFIX = 10000000;
   const char *p;                  /* Iterator pointer */
   int nInt = 0;                   /* Output value */
 
   for(p=*pp; p[0]>='0' && p[0]<='9'; p++){
     nInt = nInt * 10 + (p[0] - '0');
+    if( nInt>MAX_NPREFIX ){
+      nInt = 0;
+      break;
+    }
   }
   if( p==*pp ) return SQLITE_ERROR;
   *pnOut = nInt;
   *pp = p;
   return SQLITE_OK;
 }
 
 /*
 ** This function is called to allocate an array of Fts3Index structures
 ** representing the indexes maintained by the current FTS table. FTS tables
@@ skipping 22 matching lines @@
   if( zParam && zParam[0] ){
     const char *p;
     nIndex++;
     for(p=zParam; *p; p++){
       if( *p==',' ) nIndex++;
     }
   }
 
   aIndex = sqlite3_malloc(sizeof(struct Fts3Index) * nIndex);
   *apIndex = aIndex;
-  *pnIndex = nIndex;
   if( !aIndex ){
     return SQLITE_NOMEM;
   }
 
   memset(aIndex, 0, sizeof(struct Fts3Index) * nIndex);
   if( zParam ){
     const char *p = zParam;
     int i;
     for(i=1; i<nIndex; i++){
-      int nPrefix;
+      int nPrefix = 0;
       if( fts3GobbleInt(&p, &nPrefix) ) return SQLITE_ERROR;
-      aIndex[i].nPrefix = nPrefix;
+      assert( nPrefix>=0 );
+      if( nPrefix==0 ){
+        nIndex--;
+        i--;
+      }else{
+        aIndex[i].nPrefix = nPrefix;
+      }
       p++;
     }
   }
 
+  *pnIndex = nIndex;
   return SQLITE_OK;
 }
 
 /*
 ** This function is called when initializing an FTS4 table that uses the
 ** content=xxx option. It determines the number of and names of the columns
 ** of the new FTS4 table.
 **
 ** The third argument passed to this function is the value passed to the
 ** config=xxx option (i.e. "xxx"). This function queries the database for
@@ skipping 14 matching lines @@
 ** If the table cannot be found, an error code is returned and the output
 ** variables are undefined. Or, if an OOM is encountered, SQLITE_NOMEM is
 ** returned (and the output variables are undefined).
 */
 static int fts3ContentColumns(
   sqlite3 *db,                    /* Database handle */
   const char *zDb,                /* Name of db (i.e. "main", "temp" etc.) */
   const char *zTbl,               /* Name of content table */
   const char ***pazCol,           /* OUT: Malloc'd array of column names */
   int *pnCol,                     /* OUT: Size of array *pazCol */
-  int *pnStr                      /* OUT: Bytes of string content */
+  int *pnStr,                     /* OUT: Bytes of string content */
+  char **pzErr                    /* OUT: error message */
 ){
   int rc = SQLITE_OK;             /* Return code */
   char *zSql;                     /* "SELECT *" statement on zTbl */  
   sqlite3_stmt *pStmt = 0;        /* Compiled version of zSql */
 
   zSql = sqlite3_mprintf("SELECT * FROM %Q.%Q", zDb, zTbl);
   if( !zSql ){
     rc = SQLITE_NOMEM;
   }else{
     rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
+    if( rc!=SQLITE_OK ){
+      sqlite3Fts3ErrMsg(pzErr, "%s", sqlite3_errmsg(db));
+    }
   }
   sqlite3_free(zSql);
 
   if( rc==SQLITE_OK ){
     const char **azCol;           /* Output array */
     int nStr = 0;                 /* Size of all column names (incl. 0x00) */
     int nCol;                     /* Number of table columns */
     int i;                        /* Used to iterate through columns */
 
     /* Loop through the returned columns. Set nStr to the number of bytes of
@@ skipping 58 matching lines @@
   int iCol;                       /* Column index */
   int nString = 0;                /* Bytes required to hold all column names */
   int nCol = 0;                   /* Number of columns in the FTS table */
   char *zCsr;                     /* Space for holding column names */
   int nDb;                        /* Bytes required to hold database name */
   int nName;                      /* Bytes required to hold table name */
   int isFts4 = (argv[0][3]=='4'); /* True for FTS4, false for FTS3 */
   const char **aCol;              /* Array of column names */
   sqlite3_tokenizer *pTokenizer = 0;        /* Tokenizer for this table */
 
-  int nIndex;                     /* Size of aIndex[] array */
+  int nIndex = 0;                 /* Size of aIndex[] array */
   struct Fts3Index *aIndex = 0;   /* Array of indexes for this table */
 
   /* The results of parsing supported FTS4 key=value options: */
   int bNoDocsize = 0;             /* True to omit %_docsize table */
   int bDescIdx = 0;               /* True to store descending indexes */
   char *zPrefix = 0;              /* Prefix parameter value (or NULL) */
   char *zCompress = 0;            /* compress=? parameter (or NULL) */
   char *zUncompress = 0;          /* uncompress=? parameter (or NULL) */
   char *zContent = 0;             /* content=? parameter (or NULL) */
   char *zLanguageid = 0;          /* languageid=? parameter (or NULL) */
@@ skipping 67 matching lines @@
       if( !zVal ){
         rc = SQLITE_NOMEM;
       }else{
         for(iOpt=0; iOpt<SizeofArray(aFts4Opt); iOpt++){
           struct Fts4Option *pOp = &aFts4Opt[iOpt];
           if( nKey==pOp->nOpt && !sqlite3_strnicmp(z, pOp->zOpt, pOp->nOpt) ){
             break;
           }
         }
         if( iOpt==SizeofArray(aFts4Opt) ){
-          *pzErr = sqlite3_mprintf("unrecognized parameter: %s", z);
+          sqlite3Fts3ErrMsg(pzErr, "unrecognized parameter: %s", z);
           rc = SQLITE_ERROR;
         }else{
           switch( iOpt ){
             case 0:               /* MATCHINFO */
               if( strlen(zVal)!=4 || sqlite3_strnicmp(zVal, "fts3", 4) ){
-                *pzErr = sqlite3_mprintf("unrecognized matchinfo: %s", zVal);
+                sqlite3Fts3ErrMsg(pzErr, "unrecognized matchinfo: %s", zVal);
                 rc = SQLITE_ERROR;
               }
               bNoDocsize = 1;
               break;
 
             case 1:               /* PREFIX */
               sqlite3_free(zPrefix);
               zPrefix = zVal;
               zVal = 0;
               break;
 
             case 2:               /* COMPRESS */
               sqlite3_free(zCompress);
               zCompress = zVal;
               zVal = 0;
               break;
 
             case 3:               /* UNCOMPRESS */
               sqlite3_free(zUncompress);
               zUncompress = zVal;
               zVal = 0;
               break;
 
             case 4:               /* ORDER */
               if( (strlen(zVal)!=3 || sqlite3_strnicmp(zVal, "asc", 3)) 
                && (strlen(zVal)!=4 || sqlite3_strnicmp(zVal, "desc", 4)) 
               ){
-                *pzErr = sqlite3_mprintf("unrecognized order: %s", zVal);
+                sqlite3Fts3ErrMsg(pzErr, "unrecognized order: %s", zVal);
                 rc = SQLITE_ERROR;
               }
               bDescIdx = (zVal[0]=='d' || zVal[0]=='D');
               break;
 
             case 5:              /* CONTENT */
               sqlite3_free(zContent);
               zContent = zVal;
               zVal = 0;
               break;
@@ skipping 30 matching lines @@
   **      TABLE statement, use all columns from the content table.
   */
   if( rc==SQLITE_OK && zContent ){
     sqlite3_free(zCompress); 
     sqlite3_free(zUncompress); 
     zCompress = 0;
     zUncompress = 0;
     if( nCol==0 ){
       sqlite3_free((void*)aCol); 
       aCol = 0;
-      rc = fts3ContentColumns(db, argv[1], zContent, &aCol, &nCol, &nString);
+      rc = fts3ContentColumns(db, argv[1], zContent,&aCol,&nCol,&nString,pzErr);
 
       /* If a languageid= option was specified, remove the language id
       ** column from the aCol[] array. */ 
       if( rc==SQLITE_OK && zLanguageid ){
         int j;
         for(j=0; j<nCol; j++){
           if( sqlite3_stricmp(zLanguageid, aCol[j])==0 ){
             int k;
             for(k=j; k<nCol; k++) aCol[k] = aCol[k+1];
             nCol--;
@@ skipping 14 matching lines @@
 
   if( pTokenizer==0 ){
     rc = sqlite3Fts3InitTokenizer(pHash, "simple", &pTokenizer, pzErr);
     if( rc!=SQLITE_OK ) goto fts3_init_out;
   }
   assert( pTokenizer );
 
   rc = fts3PrefixParameter(zPrefix, &nIndex, &aIndex);
   if( rc==SQLITE_ERROR ){
     assert( zPrefix );
-    *pzErr = sqlite3_mprintf("error parsing prefix parameter: %s", zPrefix);
+    sqlite3Fts3ErrMsg(pzErr, "error parsing prefix parameter: %s", zPrefix);
   }
   if( rc!=SQLITE_OK ) goto fts3_init_out;
 
   /* Allocate and populate the Fts3Table structure. */
   nByte = sizeof(Fts3Table) +                  /* Fts3Table */
           nCol * sizeof(char *) +              /* azColumn */
           nIndex * sizeof(struct Fts3Index) +  /* aIndex */
           nCol * sizeof(u8) +                  /* abNotindexed */
           nName +                              /* zName */
           nDb +                                /* zDb */
@@ skipping 61 matching lines @@
        && 0==sqlite3_strnicmp(p->azColumn[iCol], zNot, n) 
       ){
         p->abNotindexed[iCol] = 1;
         sqlite3_free(zNot);
         azNotindexed[i] = 0;
       }
     }
   }
   for(i=0; i<nNotindexed; i++){
     if( azNotindexed[i] ){
-      *pzErr = sqlite3_mprintf("no such column: %s", azNotindexed[i]);
+      sqlite3Fts3ErrMsg(pzErr, "no such column: %s", azNotindexed[i]);
       rc = SQLITE_ERROR;
     }
   }
 
   if( rc==SQLITE_OK && (zCompress==0)!=(zUncompress==0) ){
     char const *zMiss = (zCompress==0 ? "compress" : "uncompress");
     rc = SQLITE_ERROR;
-    *pzErr = sqlite3_mprintf("missing %s parameter in fts4 constructor", zMiss);
+    sqlite3Fts3ErrMsg(pzErr, "missing %s parameter in fts4 constructor", zMiss);
   }
   p->zReadExprlist = fts3ReadExprList(p, zUncompress, &rc);
   p->zWriteExprlist = fts3WriteExprList(p, zCompress, &rc);
   if( rc!=SQLITE_OK ) goto fts3_init_out;
 
   /* If this is an xCreate call, create the underlying tables in the 
   ** database. TODO: For xConnect(), it could verify that said tables exist.
   */
   if( isCreate ){
     rc = fts3CreateTables(p);
@@ skipping 68 matching lines @@
 ** support estimatedRows. In that case this function is a no-op.
 */
 static void fts3SetEstimatedRows(sqlite3_index_info *pIdxInfo, i64 nRow){
 #if SQLITE_VERSION_NUMBER>=3008002
   if( sqlite3_libversion_number()>=3008002 ){
     pIdxInfo->estimatedRows = nRow;
   }
 #endif
 }
 
+/*
+** Set the SQLITE_INDEX_SCAN_UNIQUE flag in pIdxInfo->flags. Unless this
+** extension is currently being used by a version of SQLite too old to
+** support index-info flags. In that case this function is a no-op.
+*/
+static void fts3SetUniqueFlag(sqlite3_index_info *pIdxInfo){
+#if SQLITE_VERSION_NUMBER>=3008012
+  if( sqlite3_libversion_number()>=3008012 ){
+    pIdxInfo->idxFlags |= SQLITE_INDEX_SCAN_UNIQUE;
+  }
+#endif
+}
+
 /* 
 ** Implementation of the xBestIndex method for FTS3 tables. There
 ** are three possible strategies, in order of preference:
 **
 **   1. Direct lookup by rowid or docid. 
 **   2. Full-text search using a MATCH operator on a non-docid column.
 **   3. Linear scan of %_content table.
 */
 static int fts3BestIndexMethod(sqlite3_vtab *pVTab, sqlite3_index_info *pInfo){
   Fts3Table *p = (Fts3Table *)pVTab;
@@ skipping 70 matching lines @@
           break;
 
         case SQLITE_INDEX_CONSTRAINT_LE:
         case SQLITE_INDEX_CONSTRAINT_LT:
           iDocidLe = i;
           break;
       }
     }
   }
 
+  /* If using a docid=? or rowid=? strategy, set the UNIQUE flag. */
+  if( pInfo->idxNum==FTS3_DOCID_SEARCH ) fts3SetUniqueFlag(pInfo);
+
   iIdx = 1;
   if( iCons>=0 ){
     pInfo->aConstraintUsage[iCons].argvIndex = iIdx++;
     pInfo->aConstraintUsage[iCons].omit = 1;
   } 
   if( iLangidCons>=0 ){
     pInfo->idxNum |= FTS3_HAVE_LANGID;
     pInfo->aConstraintUsage[iLangidCons].argvIndex = iIdx++;
   } 
   if( iDocidGe>=0 ){
@@ skipping 48 matching lines @@
 ** Close the cursor.  For additional information see the documentation
 ** on the xClose method of the virtual table interface.
 */
 static int fts3CloseMethod(sqlite3_vtab_cursor *pCursor){
   Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;
   assert( ((Fts3Table *)pCsr->base.pVtab)->pSegments==0 );
   sqlite3_finalize(pCsr->pStmt);
   sqlite3Fts3ExprFree(pCsr->pExpr);
   sqlite3Fts3FreeDeferredTokens(pCsr);
   sqlite3_free(pCsr->aDoclist);
-  sqlite3_free(pCsr->aMatchinfo);
+  sqlite3Fts3MIBufferFree(pCsr->pMIBuffer);
   assert( ((Fts3Table *)pCsr->base.pVtab)->pSegments==0 );
   sqlite3_free(pCsr);
   return SQLITE_OK;
 }
 
 /*
 ** If pCsr->pStmt has not been prepared (i.e. if pCsr->pStmt==0), then
 ** compose and prepare an SQL statement of the form:
 **
 **    "SELECT <columns> FROM %_content WHERE rowid = ?"
@@ skipping 196 matching lines @@
 */ 
 static int fts3SelectLeaf(
   Fts3Table *p,                   /* Virtual table handle */
   const char *zTerm,              /* Term to select leaves for */
   int nTerm,                      /* Size of term zTerm in bytes */
   const char *zNode,              /* Buffer containing segment interior node */
   int nNode,                      /* Size of buffer at zNode */
   sqlite3_int64 *piLeaf,          /* Selected leaf node */
   sqlite3_int64 *piLeaf2          /* Selected leaf node */
 ){
-  int rc;                         /* Return code */
+  int rc = SQLITE_OK;             /* Return code */
   int iHeight;                    /* Height of this node in tree */
 
   assert( piLeaf || piLeaf2 );
 
   fts3GetVarint32(zNode, &iHeight);
   rc = fts3ScanInteriorNode(zTerm, nTerm, zNode, nNode, piLeaf, piLeaf2);
   assert( !piLeaf2 || !piLeaf || rc!=SQLITE_OK || (*piLeaf<=*piLeaf2) );
 
   if( rc==SQLITE_OK && iHeight>1 ){
     char *zBlob = 0;              /* Blob read from %_segments table */
-    int nBlob;                    /* Size of zBlob in bytes */
+    int nBlob = 0;                /* Size of zBlob in bytes */
 
     if( piLeaf && piLeaf2 && (*piLeaf!=*piLeaf2) ){
       rc = sqlite3Fts3ReadBlock(p, *piLeaf, &zBlob, &nBlob, 0);
       if( rc==SQLITE_OK ){
         rc = fts3SelectLeaf(p, zTerm, nTerm, zBlob, nBlob, piLeaf, 0);
       }
       sqlite3_free(zBlob);
       piLeaf = 0;
       zBlob = 0;
     }
@@ skipping 606 matching lines @@
 ** the output contains a copy of each position from the right-hand input
 ** doclist for which there is a position in the left-hand input doclist
 ** exactly nDist tokens before it.
 **
 ** If the docids in the input doclists are sorted in ascending order,
 ** parameter bDescDoclist should be false. If they are sorted in ascending 
 ** order, it should be passed a non-zero value.
 **
 ** The right-hand input doclist is overwritten by this function.
 */
-static void fts3DoclistPhraseMerge(
+static int fts3DoclistPhraseMerge(
   int bDescDoclist,               /* True if arguments are desc */
   int nDist,                      /* Distance from left to right (1=adjacent) */
   char *aLeft, int nLeft,         /* Left doclist */
-  char *aRight, int *pnRight      /* IN/OUT: Right/output doclist */
+  char **paRight, int *pnRight    /* IN/OUT: Right/output doclist */
 ){
   sqlite3_int64 i1 = 0;
   sqlite3_int64 i2 = 0;
   sqlite3_int64 iPrev = 0;
+  char *aRight = *paRight;
   char *pEnd1 = &aLeft[nLeft];
   char *pEnd2 = &aRight[*pnRight];
   char *p1 = aLeft;
   char *p2 = aRight;
   char *p;
   int bFirstOut = 0;
-  char *aOut = aRight;
+  char *aOut;
 
   assert( nDist>0 );
+  if( bDescDoclist ){
+    aOut = sqlite3_malloc(*pnRight + FTS3_VARINT_MAX);
+    if( aOut==0 ) return SQLITE_NOMEM;
+  }else{
+    aOut = aRight;
+  }
+  p = aOut;
 
-  p = aOut;
   fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1);
   fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2);
 
   while( p1 && p2 ){
     sqlite3_int64 iDiff = DOCID_CMP(i1, i2);
     if( iDiff==0 ){
       char *pSave = p;
       sqlite3_int64 iPrevSave = iPrev;
       int bFirstOutSave = bFirstOut;
 
       fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i1);
       if( 0==fts3PoslistPhraseMerge(&p, nDist, 0, 1, &p1, &p2) ){
         p = pSave;
         iPrev = iPrevSave;
         bFirstOut = bFirstOutSave;
       }
       fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);
       fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);
     }else if( iDiff<0 ){
       fts3PoslistCopy(0, &p1);
       fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);
     }else{
       fts3PoslistCopy(0, &p2);
       fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);
     }
   }
 
   *pnRight = (int)(p - aOut);
+  if( bDescDoclist ){
+    sqlite3_free(aRight);
+    *paRight = aOut;
+  }
+
+  return SQLITE_OK;
 }
 
 /*
 ** Argument pList points to a position list nList bytes in size. This
 ** function checks to see if the position list contains any entries for
 ** a token in position 0 (of any column). If so, it writes argument iDelta
 ** to the output buffer pOut, followed by a position list consisting only
 ** of the entries from pList at position 0, and terminated by an 0x00 byte.
 ** The value returned is the number of bytes written to pOut (if any).
 */
@@ skipping 104 matching lines @@
 ** SQLite error code (SQLITE_NOMEM) if an error occurs.
 */
 static int fts3TermSelectMerge(
   Fts3Table *p,                   /* FTS table handle */
   TermSelect *pTS,                /* TermSelect object to merge into */
   char *aDoclist,                 /* Pointer to doclist */
   int nDoclist                    /* Size of aDoclist in bytes */
 ){
   if( pTS->aaOutput[0]==0 ){
     /* If this is the first term selected, copy the doclist to the output
-    ** buffer using memcpy(). */
-    pTS->aaOutput[0] = sqlite3_malloc(nDoclist);
+    ** buffer using memcpy(). 
+    **
+    ** Add FTS3_VARINT_MAX bytes of unused space to the end of the 
+    ** allocation. This is so as to ensure that the buffer is big enough
+    ** to hold the current doclist AND'd with any other doclist. If the
+    ** doclists are stored in order=ASC order, this padding would not be
+    ** required (since the size of [doclistA AND doclistB] is always less
+    ** than or equal to the size of [doclistA] in that case). But this is
+    ** not true for order=DESC. For example, a doclist containing (1, -1) 
+    ** may be smaller than (-1), as in the first example the -1 may be stored
+    ** as a single-byte delta, whereas in the second it must be stored as a
+    ** FTS3_VARINT_MAX byte varint.
+    **
+    ** Similar padding is added in the fts3DoclistOrMerge() function.
+    */
+    pTS->aaOutput[0] = sqlite3_malloc(nDoclist + FTS3_VARINT_MAX + 1);
     pTS->anOutput[0] = nDoclist;
     if( pTS->aaOutput[0] ){
       memcpy(pTS->aaOutput[0], aDoclist, nDoclist);
     }else{
       return SQLITE_NOMEM;
     }
   }else{
     char *aMerge = aDoclist;
     int nMerge = nDoclist;
     int iOut;
@@ skipping 76 matching lines @@
   int rc2;                        /* Result of sqlite3_reset() */
 
   /* If iLevel is less than 0 and this is not a scan, include a seg-reader 
   ** for the pending-terms. If this is a scan, then this call must be being
   ** made by an fts4aux module, not an FTS table. In this case calling
   ** Fts3SegReaderPending might segfault, as the data structures used by 
   ** fts4aux are not completely populated. So it's easiest to filter these
   ** calls out here.  */
   if( iLevel<0 && p->aIndex ){
     Fts3SegReader *pSeg = 0;
-    rc = sqlite3Fts3SegReaderPending(p, iIndex, zTerm, nTerm, isPrefix, &pSeg);
+    rc = sqlite3Fts3SegReaderPending(p, iIndex, zTerm, nTerm, isPrefix||isScan, &pSeg);
     if( rc==SQLITE_OK && pSeg ){
       rc = fts3SegReaderCursorAppend(pCsr, pSeg);
     }
   }
 
   if( iLevel!=FTS3_SEGCURSOR_PENDING ){
     if( rc==SQLITE_OK ){
       rc = sqlite3Fts3AllSegdirs(p, iLangid, iIndex, iLevel, &pStmt);
     }
 
@@ skipping 304 matching lines @@
 ** number idxNum-FTS3_FULLTEXT_SEARCH, 0 indexed.  argv[0] is the right-hand
 ** side of the MATCH operator.
 */
 static int fts3FilterMethod(
   sqlite3_vtab_cursor *pCursor,   /* The cursor used for this query */
   int idxNum,                     /* Strategy index */
   const char *idxStr,             /* Unused */
   int nVal,                       /* Number of elements in apVal */
   sqlite3_value **apVal           /* Arguments for the indexing scheme */
 ){
-  int rc;
+  int rc = SQLITE_OK;
   char *zSql;                     /* SQL statement used to access %_content */
   int eSearch;
   Fts3Table *p = (Fts3Table *)pCursor->pVtab;
   Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;
 
   sqlite3_value *pCons = 0;       /* The MATCH or rowid constraint, if any */
   sqlite3_value *pLangid = 0;     /* The "langid = ?" constraint, if any */
   sqlite3_value *pDocidGe = 0;    /* The "docid >= ?" constraint, if any */
   sqlite3_value *pDocidLe = 0;    /* The "docid <= ?" constraint, if any */
   int iIdx;
 
   UNUSED_PARAMETER(idxStr);
   UNUSED_PARAMETER(nVal);
 
   eSearch = (idxNum & 0x0000FFFF);
   assert( eSearch>=0 && eSearch<=(FTS3_FULLTEXT_SEARCH+p->nColumn) );
   assert( p->pSegments==0 );
 
   /* Collect arguments into local variables */
   iIdx = 0;
   if( eSearch!=FTS3_FULLSCAN_SEARCH ) pCons = apVal[iIdx++];
   if( idxNum & FTS3_HAVE_LANGID ) pLangid = apVal[iIdx++];
   if( idxNum & FTS3_HAVE_DOCID_GE ) pDocidGe = apVal[iIdx++];
   if( idxNum & FTS3_HAVE_DOCID_LE ) pDocidLe = apVal[iIdx++];
   assert( iIdx==nVal );
 
   /* In case the cursor has been used before, clear it now. */
   sqlite3_finalize(pCsr->pStmt);
   sqlite3_free(pCsr->aDoclist);
-  sqlite3_free(pCsr->aMatchinfo);
+  sqlite3Fts3MIBufferFree(pCsr->pMIBuffer);
   sqlite3Fts3ExprFree(pCsr->pExpr);
   memset(&pCursor[1], 0, sizeof(Fts3Cursor)-sizeof(sqlite3_vtab_cursor));
 
   /* Set the lower and upper bounds on docids to return */
   pCsr->iMinDocid = fts3DocidRange(pDocidGe, SMALLEST_INT64);
   pCsr->iMaxDocid = fts3DocidRange(pDocidLe, LARGEST_INT64);
 
   if( idxStr ){
     pCsr->bDesc = (idxStr[0]=='D');
   }else{
@@ skipping 27 matching lines @@
     pCsr->pNextId = pCsr->aDoclist;
     pCsr->iPrevId = 0;
   }
 
   /* Compile a SELECT statement for this cursor. For a full-table-scan, the
   ** statement loops through all rows of the %_content table. For a
   ** full-text query or docid lookup, the statement retrieves a single
   ** row by docid.
   */
   if( eSearch==FTS3_FULLSCAN_SEARCH ){
-    zSql = sqlite3_mprintf(
-        "SELECT %s ORDER BY rowid %s",
-        p->zReadExprlist, (pCsr->bDesc ? "DESC" : "ASC")
-    );
+    if( pDocidGe || pDocidLe ){
+      zSql = sqlite3_mprintf(
+          "SELECT %s WHERE rowid BETWEEN %lld AND %lld ORDER BY rowid %s",
+          p->zReadExprlist, pCsr->iMinDocid, pCsr->iMaxDocid,
+          (pCsr->bDesc ? "DESC" : "ASC")
+      );
+    }else{
+      zSql = sqlite3_mprintf("SELECT %s ORDER BY rowid %s", 
+          p->zReadExprlist, (pCsr->bDesc ? "DESC" : "ASC")
+      );
+    }
     if( zSql ){
       rc = sqlite3_prepare_v2(p->db, zSql, -1, &pCsr->pStmt, 0);
       sqlite3_free(zSql);
     }else{
       rc = SQLITE_NOMEM;
     }
   }else if( eSearch==FTS3_DOCID_SEARCH ){
     rc = fts3CursorSeekStmt(pCsr, &pCsr->pStmt);
     if( rc==SQLITE_OK ){
       rc = sqlite3_bind_value(pCsr->pStmt, 1, pCons);
@@ skipping 215 matching lines @@
 /*
 ** When called, *ppPoslist must point to the byte immediately following the
 ** end of a position-list. i.e. ( (*ppPoslist)[-1]==POS_END ). This function
 ** moves *ppPoslist so that it instead points to the first byte of the
 ** same position list.
 */
 static void fts3ReversePoslist(char *pStart, char **ppPoslist){
   char *p = &(*ppPoslist)[-2];
   char c = 0;
 
+  /* Skip backwards passed any trailing 0x00 bytes added by NearTrim() */
   while( p>pStart && (c=*p--)==0 );
+
+  /* Search backwards for a varint with value zero (the end of the previous 
+  ** poslist). This is an 0x00 byte preceded by some byte that does not
+  ** have the 0x80 bit set.  */
   while( p>pStart && (*p & 0x80) | c ){ 
     c = *p--; 
   }
-  if( p>pStart ){ p = &p[2]; }
+  assert( p==pStart || c==0 );
+
+  /* At this point p points to that preceding byte without the 0x80 bit
+  ** set. So to find the start of the poslist, skip forward 2 bytes then
+  ** over a varint. 
+  **
+  ** Normally. The other case is that p==pStart and the poslist to return
+  ** is the first in the doclist. In this case do not skip forward 2 bytes.
+  ** The second part of the if condition (c==0 && *ppPoslist>&p[2])
+  ** is required for cases where the first byte of a doclist and the
+  ** doclist is empty. For example, if the first docid is 10, a doclist
+  ** that begins with:
+  **
+  **   0x0A 0x00 <next docid delta varint>
+  */
+  if( p>pStart || (c==0 && *ppPoslist>&p[2]) ){ p = &p[2]; }
   while( *p++&0x80 );
   *ppPoslist = p;
 }
 
 /*
 ** Helper function used by the implementation of the overloaded snippet(),
 ** offsets() and optimize() SQL functions.
 **
 ** If the value passed as the third argument is a blob of size
 ** sizeof(Fts3Cursor*), then the blob contents are copied to the 
@@ skipping 50 matching lines @@
 
   switch( nVal ){
     case 6: nToken = sqlite3_value_int(apVal[5]);
     case 5: iCol = sqlite3_value_int(apVal[4]);
     case 4: zEllipsis = (const char*)sqlite3_value_text(apVal[3]);
     case 3: zEnd = (const char*)sqlite3_value_text(apVal[2]);
     case 2: zStart = (const char*)sqlite3_value_text(apVal[1]);
   }
   if( !zEllipsis || !zEnd || !zStart ){
     sqlite3_result_error_nomem(pContext);
+  }else if( nToken==0 ){
+    sqlite3_result_text(pContext, "", -1, SQLITE_STATIC);
   }else if( SQLITE_OK==fts3CursorSeek(pContext, pCsr) ){
     sqlite3Fts3Snippet(pContext, pCsr, zStart, zEnd, zEllipsis, iCol, nToken);
   }
 }
 
 /*
 ** Implementation of the offsets() function for FTS3
 */
 static void fts3OffsetsFunc(
   sqlite3_context *pContext,      /* SQLite function call context */
@@ skipping 423 matching lines @@
   }
 }
 
 /*
 ** Arguments pList/nList contain the doclist for token iToken of phrase p.
 ** It is merged into the main doclist stored in p->doclist.aAll/nAll.
 **
 ** This function assumes that pList points to a buffer allocated using
 ** sqlite3_malloc(). This function takes responsibility for eventually
 ** freeing the buffer.
+**
+** SQLITE_OK is returned if successful, or SQLITE_NOMEM if an error occurs.
 */
-static void fts3EvalPhraseMergeToken(
+static int fts3EvalPhraseMergeToken(
   Fts3Table *pTab,                /* FTS Table pointer */
   Fts3Phrase *p,                  /* Phrase to merge pList/nList into */
   int iToken,                     /* Token pList/nList corresponds to */
   char *pList,                    /* Pointer to doclist */
   int nList                       /* Number of bytes in pList */
 ){
+  int rc = SQLITE_OK;
   assert( iToken!=p->iDoclistToken );
 
   if( pList==0 ){
     sqlite3_free(p->doclist.aAll);
     p->doclist.aAll = 0;
     p->doclist.nAll = 0;
   }
 
   else if( p->iDoclistToken<0 ){
     p->doclist.aAll = pList;
@@ skipping 18 matching lines @@
       nRight = nList;
       nDiff = iToken - p->iDoclistToken;
     }else{
       pRight = p->doclist.aAll;
       nRight = p->doclist.nAll;
       pLeft = pList;
       nLeft = nList;
       nDiff = p->iDoclistToken - iToken;
     }
 
-    fts3DoclistPhraseMerge(pTab->bDescIdx, nDiff, pLeft, nLeft, pRight,&nRight);
+    rc = fts3DoclistPhraseMerge(
+        pTab->bDescIdx, nDiff, pLeft, nLeft, &pRight, &nRight
+    );
     sqlite3_free(pLeft);
     p->doclist.aAll = pRight;
     p->doclist.nAll = nRight;
   }
 
   if( iToken>p->iDoclistToken ) p->iDoclistToken = iToken;
+  return rc;
 }
 
 /*
 ** Load the doclist for phrase p into p->doclist.aAll/nAll. The loaded doclist
 ** does not take deferred tokens into account.
 **
 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.
 */
 static int fts3EvalPhraseLoad(
   Fts3Cursor *pCsr,               /* FTS Cursor handle */
   Fts3Phrase *p                   /* Phrase object */
 ){
   Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
   int iToken;
   int rc = SQLITE_OK;
 
   for(iToken=0; rc==SQLITE_OK && iToken<p->nToken; iToken++){
     Fts3PhraseToken *pToken = &p->aToken[iToken];
     assert( pToken->pDeferred==0 || pToken->pSegcsr==0 );
 
     if( pToken->pSegcsr ){
       int nThis = 0;
       char *pThis = 0;
       rc = fts3TermSelect(pTab, pToken, p->iColumn, &nThis, &pThis);
       if( rc==SQLITE_OK ){
-        fts3EvalPhraseMergeToken(pTab, p, iToken, pThis, nThis);
+        rc = fts3EvalPhraseMergeToken(pTab, p, iToken, pThis, nThis);
       }
     }
     assert( pToken->pSegcsr==0 );
   }
 
   return rc;
 }
 
 /*
 ** This function is called on each phrase after the position lists for
@@ skipping 124 matching lines @@
 
   /* Determine if doclists may be loaded from disk incrementally. This is
   ** possible if the bOptOk argument is true, the FTS doclists will be
   ** scanned in forward order, and the phrase consists of 
   ** MAX_INCR_PHRASE_TOKENS or fewer tokens, none of which are are "^first"
   ** tokens or prefix tokens that cannot use a prefix-index.  */
   int bHaveIncr = 0;
   int bIncrOk = (bOptOk 
    && pCsr->bDesc==pTab->bDescIdx 
    && p->nToken<=MAX_INCR_PHRASE_TOKENS && p->nToken>0
-   && p->nToken<=MAX_INCR_PHRASE_TOKENS && p->nToken>0
 #ifdef SQLITE_TEST
    && pTab->bNoIncrDoclist==0
 #endif
   );
   for(i=0; bIncrOk==1 && i<p->nToken; i++){
     Fts3PhraseToken *pToken = &p->aToken[i];
     if( pToken->bFirst || (pToken->pSegcsr!=0 && !pToken->pSegcsr->bLookup) ){
       bIncrOk = 0;
     }
     if( pToken->pSegcsr ) bHaveIncr = 1;
@@ skipping 99 matching lines @@
   assert( nDoclist>0 );
   assert( *pbEof==0 );
   assert( p || *piDocid==0 );
   assert( !p || (p>=aDoclist && p<=&aDoclist[nDoclist]) );
 
   if( p==0 ){
     p = aDoclist;
     p += sqlite3Fts3GetVarint(p, piDocid);
   }else{
     fts3PoslistCopy(0, &p);
+    while( p<&aDoclist[nDoclist] && *p==0 ) p++; 
     if( p>=&aDoclist[nDoclist] ){
       *pbEof = 1;
     }else{
       sqlite3_int64 iVar;
       p += sqlite3Fts3GetVarint(p, &iVar);
       *piDocid += ((bDescIdx ? -1 : 1) * iVar);
     }
   }
 
   *ppIter = p;
@@ skipping 257 matching lines @@
 ** If an error occurs within this function, *pRc is set to an SQLite error
 ** code before returning.
 */
 static void fts3EvalStartReaders(
   Fts3Cursor *pCsr,               /* FTS Cursor handle */
   Fts3Expr *pExpr,                /* Expression to initialize phrases in */
   int *pRc                        /* IN/OUT: Error code */
 ){
   if( pExpr && SQLITE_OK==*pRc ){
     if( pExpr->eType==FTSQUERY_PHRASE ){
-      int i;
       int nToken = pExpr->pPhrase->nToken;
-      for(i=0; i<nToken; i++){
-        if( pExpr->pPhrase->aToken[i].pDeferred==0 ) break;
+      if( nToken ){
+        int i;
+        for(i=0; i<nToken; i++){
+          if( pExpr->pPhrase->aToken[i].pDeferred==0 ) break;
+        }
+        pExpr->bDeferred = (i==nToken);
       }
-      pExpr->bDeferred = (i==nToken);
       *pRc = fts3EvalPhraseStart(pCsr, 1, pExpr->pPhrase);
     }else{
       fts3EvalStartReaders(pCsr, pExpr->pLeft, pRc);
       fts3EvalStartReaders(pCsr, pExpr->pRight, pRc);
       pExpr->bDeferred = (pExpr->pLeft->bDeferred && pExpr->pRight->bDeferred);
     }
   }
 }
 
 /*
@@ skipping 235 matching lines @@
       if( ii==0 || (pTC->pPhrase->nToken>1 && ii!=nToken-1) ){
         /* Either this is the cheapest token in the entire query, or it is
         ** part of a multi-token phrase. Either way, the entire doclist will
         ** (eventually) be loaded into memory. It may as well be now. */
         Fts3PhraseToken *pToken = pTC->pToken;
         int nList = 0;
         char *pList = 0;
         rc = fts3TermSelect(pTab, pToken, pTC->iCol, &nList, &pList);
         assert( rc==SQLITE_OK || pList==0 );
         if( rc==SQLITE_OK ){
+          rc = fts3EvalPhraseMergeToken(
+              pTab, pTC->pPhrase, pTC->iToken,pList,nList
+          );
+        }
+        if( rc==SQLITE_OK ){
           int nCount;
-          fts3EvalPhraseMergeToken(pTab, pTC->pPhrase, pTC->iToken,pList,nList);
           nCount = fts3DoclistCountDocids(
               pTC->pPhrase->doclist.aAll, pTC->pPhrase->doclist.nAll
           );
           if( ii==0 || nCount<nMinEst ) nMinEst = nCount;
         }
       }
     }
     pTC->pToken = 0;
   }
 
@@ skipping 157 matching lines @@
 **      more non-deferred tokens, then the expression is advanced to the 
 **      next possible match, considering only non-deferred tokens. In other
 **      words, if the phrase is "A B C", and "B" is deferred, the expression
 **      is advanced to the next row that contains an instance of "A * C", 
 **      where "*" may match any single token. The position list in this case
 **      is populated as for "A * C" before returning.
 **
 **   2. NEAR is treated as AND. If the expression is "x NEAR y", it is 
 **      advanced to point to the next row that matches "x AND y".
 ** 
-** See fts3EvalTestDeferredAndNear() for details on testing if a row is
+** See sqlite3Fts3EvalTestDeferred() for details on testing if a row is
 ** really a match, taking into account deferred tokens and NEAR operators.
 */
 static void fts3EvalNextRow(
   Fts3Cursor *pCsr,               /* FTS Cursor handle */
   Fts3Expr *pExpr,                /* Expr. to advance to next matching row */
   int *pRc                        /* IN/OUT: Error code */
 ){
   if( *pRc==SQLITE_OK ){
     int bDescDoclist = pCsr->bDesc;         /* Used by DOCID_CMP() macro */
     assert( pExpr->bEof==0 );
@@ skipping 26 matching lines @@
             sqlite3_int64 iDiff = DOCID_CMP(pLeft->iDocid, pRight->iDocid);
             if( iDiff==0 ) break;
             if( iDiff<0 ){
               fts3EvalNextRow(pCsr, pLeft, pRc);
             }else{
               fts3EvalNextRow(pCsr, pRight, pRc);
             }
           }
           pExpr->iDocid = pLeft->iDocid;
           pExpr->bEof = (pLeft->bEof || pRight->bEof);
+          if( pExpr->eType==FTSQUERY_NEAR && pExpr->bEof ){
+            if( pRight->pPhrase && pRight->pPhrase->doclist.aAll ){
+              Fts3Doclist *pDl = &pRight->pPhrase->doclist;
+              while( *pRc==SQLITE_OK && pRight->bEof==0 ){
+                memset(pDl->pList, 0, pDl->nList);
+                fts3EvalNextRow(pCsr, pRight, pRc);
+              }
+            }
+            if( pLeft->pPhrase && pLeft->pPhrase->doclist.aAll ){
+              Fts3Doclist *pDl = &pLeft->pPhrase->doclist;
+              while( *pRc==SQLITE_OK && pLeft->bEof==0 ){
+                memset(pDl->pList, 0, pDl->nList);
+                fts3EvalNextRow(pCsr, pLeft, pRc);
+              }
+            }
+          }
         }
         break;
       }
   
       case FTSQUERY_OR: {
         Fts3Expr *pLeft = pExpr->pLeft;
         Fts3Expr *pRight = pExpr->pRight;
         sqlite3_int64 iCmp = DOCID_CMP(pLeft->iDocid, pRight->iDocid);
 
         assert( pLeft->bStart || pLeft->iDocid==pRight->iDocid );
@@ skipping 137 matching lines @@
       }
 
       sqlite3_free(aTmp);
     }
   }
 
   return res;
 }
 
 /*
-** This function is a helper function for fts3EvalTestDeferredAndNear().
+** This function is a helper function for sqlite3Fts3EvalTestDeferred().
 ** Assuming no error occurs or has occurred, It returns non-zero if the
 ** expression passed as the second argument matches the row that pCsr 
 ** currently points to, or zero if it does not.
 **
 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.
 ** If an error occurs during execution of this function, *pRc is set to 
 ** the appropriate SQLite error code. In this case the returned value is 
 ** undefined.
 */
 static int fts3EvalTestExpr(
@@ skipping 100 matching lines @@
 ** expression. It returns 1 if both of the following are true:
 **
 **   1. *pRc is SQLITE_OK when this function returns, and
 **
 **   2. After scanning the current FTS table row for the deferred tokens,
 **      it is determined that the row does *not* match the query.
 **
 ** Or, if no error occurs and it seems the current row does match the FTS
 ** query, return 0.
 */
-static int fts3EvalTestDeferredAndNear(Fts3Cursor *pCsr, int *pRc){
+int sqlite3Fts3EvalTestDeferred(Fts3Cursor *pCsr, int *pRc){
   int rc = *pRc;
   int bMiss = 0;
   if( rc==SQLITE_OK ){
 
     /* If there are one or more deferred tokens, load the current row into
     ** memory and scan it to determine the position list for each deferred
     ** token. Then, see if this row is really a match, considering deferred
     ** tokens and NEAR operators (neither of which were taken into account
     ** earlier, by fts3EvalNextRow()). 
     */
@@ skipping 26 matching lines @@
     do {
       if( pCsr->isRequireSeek==0 ){
         sqlite3_reset(pCsr->pStmt);
       }
       assert( sqlite3_data_count(pCsr->pStmt)==0 );
       fts3EvalNextRow(pCsr, pExpr, &rc);
       pCsr->isEof = pExpr->bEof;
       pCsr->isRequireSeek = 1;
       pCsr->isMatchinfoNeeded = 1;
       pCsr->iPrevId = pExpr->iDocid;
-    }while( pCsr->isEof==0 && fts3EvalTestDeferredAndNear(pCsr, &rc) );
+    }while( pCsr->isEof==0 && sqlite3Fts3EvalTestDeferred(pCsr, &rc) );
   }
 
   /* Check if the cursor is past the end of the docid range specified
   ** by Fts3Cursor.iMinDocid/iMaxDocid. If so, set the EOF flag.  */
   if( rc==SQLITE_OK && (
         (pCsr->bDesc==0 && pCsr->iPrevId>pCsr->iMaxDocid)
      || (pCsr->bDesc!=0 && pCsr->iPrevId<pCsr->iMinDocid)
   )){
     pCsr->isEof = 1;
   }
@@ skipping 26 matching lines @@
           Fts3PhraseToken *pToken = &pPhrase->aToken[i];
           assert( pToken->pDeferred==0 );
           if( pToken->pSegcsr ){
             sqlite3Fts3MsrIncrRestart(pToken->pSegcsr);
           }
         }
         *pRc = fts3EvalPhraseStart(pCsr, 0, pPhrase);
       }
       pPhrase->doclist.pNextDocid = 0;
       pPhrase->doclist.iDocid = 0;
+      pPhrase->pOrPoslist = 0;
     }
 
     pExpr->iDocid = 0;
     pExpr->bEof = 0;
     pExpr->bStart = 0;
 
     fts3EvalRestart(pCsr, pExpr->pLeft, pRc);
     fts3EvalRestart(pCsr, pExpr->pRight, pRc);
   }
 }
@@ skipping 93 matching lines @@
         assert( sqlite3_data_count(pCsr->pStmt)==0 );
 
         /* Advance to the next document */
         fts3EvalNextRow(pCsr, pRoot, &rc);
         pCsr->isEof = pRoot->bEof;
         pCsr->isRequireSeek = 1;
         pCsr->isMatchinfoNeeded = 1;
         pCsr->iPrevId = pRoot->iDocid;
       }while( pCsr->isEof==0 
            && pRoot->eType==FTSQUERY_NEAR 
-           && fts3EvalTestDeferredAndNear(pCsr, &rc) 
+           && sqlite3Fts3EvalTestDeferred(pCsr, &rc) 
       );
 
       if( rc==SQLITE_OK && pCsr->isEof==0 ){
         fts3EvalUpdateCounts(pRoot);
       }
     }
 
     pCsr->isEof = 0;
     pCsr->iPrevId = iPrevId;
 
     if( bEof ){
       pRoot->bEof = bEof;
     }else{
       /* Caution: pRoot may iterate through docids in ascending or descending
       ** order. For this reason, even though it seems more defensive, the 
       ** do loop can not be written:
       **
       **   do {...} while( pRoot->iDocid<iDocid && rc==SQLITE_OK );
       */
       fts3EvalRestart(pCsr, pRoot, &rc);
       do {
         fts3EvalNextRow(pCsr, pRoot, &rc);
         assert( pRoot->bEof==0 );
       }while( pRoot->iDocid!=iDocid && rc==SQLITE_OK );
-      fts3EvalTestDeferredAndNear(pCsr, &rc);
     }
   }
   return rc;
 }
 
 /*
 ** This function is used by the matchinfo() module to query a phrase 
 ** expression node for the following information:
 **
 **   1. The total number of occurrences of the phrase in each column of 
@@ skipping 86 matching lines @@
   ** column iCol, return a NULL pointer.  */
   *ppOut = 0;
   assert( iCol>=0 && iCol<pTab->nColumn );
   if( (pPhrase->iColumn<pTab->nColumn && pPhrase->iColumn!=iCol) ){
     return SQLITE_OK;
   }
 
   iDocid = pExpr->iDocid;
   pIter = pPhrase->doclist.pList;
   if( iDocid!=pCsr->iPrevId || pExpr->bEof ){
+    int rc = SQLITE_OK;
     int bDescDoclist = pTab->bDescIdx;      /* For DOCID_CMP macro */
-    int iMul;                     /* +1 if csr dir matches index dir, else -1 */
     int bOr = 0;
-    u8 bEof = 0;
     u8 bTreeEof = 0;
     Fts3Expr *p;                  /* Used to iterate from pExpr to root */
     Fts3Expr *pNear;              /* Most senior NEAR ancestor (or pExpr) */
+    int bMatch;
 
     /* Check if this phrase descends from an OR expression node. If not, 
     ** return NULL. Otherwise, the entry that corresponds to docid 
     ** pCsr->iPrevId may lie earlier in the doclist buffer. Or, if the
     ** tree that the node is part of has been marked as EOF, but the node
     ** itself is not EOF, then it may point to an earlier entry. */
     pNear = pExpr;
     for(p=pExpr->pParent; p; p=p->pParent){
       if( p->eType==FTSQUERY_OR ) bOr = 1;
       if( p->eType==FTSQUERY_NEAR ) pNear = p;
       if( p->bEof ) bTreeEof = 1;
     }
     if( bOr==0 ) return SQLITE_OK;
 
     /* This is the descendent of an OR node. In this case we cannot use
     ** an incremental phrase. Load the entire doclist for the phrase
     ** into memory in this case.  */
     if( pPhrase->bIncr ){
-      int rc = SQLITE_OK;
-      int bEofSave = pExpr->bEof;
-      fts3EvalRestart(pCsr, pExpr, &rc);
-      while( rc==SQLITE_OK && !pExpr->bEof ){
-        fts3EvalNextRow(pCsr, pExpr, &rc);
-        if( bEofSave==0 && pExpr->iDocid==iDocid ) break;
+      int bEofSave = pNear->bEof;
+      fts3EvalRestart(pCsr, pNear, &rc);
+      while( rc==SQLITE_OK && !pNear->bEof ){
+        fts3EvalNextRow(pCsr, pNear, &rc);
+        if( bEofSave==0 && pNear->iDocid==iDocid ) break;
       }
-      pIter = pPhrase->doclist.pList;
       assert( rc!=SQLITE_OK || pPhrase->bIncr==0 );
-      if( rc!=SQLITE_OK ) return rc;
     }
-    
-    iMul = ((pCsr->bDesc==bDescDoclist) ? 1 : -1);
-    while( bTreeEof==1 
-        && pNear->bEof==0
-        && (DOCID_CMP(pNear->iDocid, pCsr->iPrevId) * iMul)<0
-    ){
-      int rc = SQLITE_OK;
-      fts3EvalNextRow(pCsr, pExpr, &rc);
-      if( rc!=SQLITE_OK ) return rc;
-      iDocid = pExpr->iDocid;
-      pIter = pPhrase->doclist.pList;
+    if( bTreeEof ){
+      while( rc==SQLITE_OK && !pNear->bEof ){
+        fts3EvalNextRow(pCsr, pNear, &rc);
+      }
     }
+    if( rc!=SQLITE_OK ) return rc;
 
-    bEof = (pPhrase->doclist.nAll==0);
-    assert( bDescDoclist==0 || bDescDoclist==1 );
-    assert( pCsr->bDesc==0 || pCsr->bDesc==1 );
+    bMatch = 1;
+    for(p=pNear; p; p=p->pLeft){
+      u8 bEof = 0;
+      Fts3Expr *pTest = p;
+      Fts3Phrase *pPh;
+      assert( pTest->eType==FTSQUERY_NEAR || pTest->eType==FTSQUERY_PHRASE );
+      if( pTest->eType==FTSQUERY_NEAR ) pTest = pTest->pRight;
+      assert( pTest->eType==FTSQUERY_PHRASE );
+      pPh = pTest->pPhrase;
 
-    if( bEof==0 ){
+      pIter = pPh->pOrPoslist;
+      iDocid = pPh->iOrDocid;
       if( pCsr->bDesc==bDescDoclist ){
-        int dummy;
-        if( pNear->bEof ){
-          /* This expression is already at EOF. So position it to point to the
-          ** last entry in the doclist at pPhrase->doclist.aAll[]. Variable
-          ** iDocid is already set for this entry, so all that is required is
-          ** to set pIter to point to the first byte of the last position-list
-          ** in the doclist. 
-          **
-          ** It would also be correct to set pIter and iDocid to zero. In
-          ** this case, the first call to sqltie3Fts4DoclistPrev() below
-          ** would also move the iterator to point to the last entry in the 
-          ** doclist. However, this is expensive, as to do so it has to 
-          ** iterate through the entire doclist from start to finish (since
-          ** it does not know the docid for the last entry).  */
-          pIter = &pPhrase->doclist.aAll[pPhrase->doclist.nAll-1];
-          fts3ReversePoslist(pPhrase->doclist.aAll, &pIter);
-        }
-        while( (pIter==0 || DOCID_CMP(iDocid, pCsr->iPrevId)>0 ) && bEof==0 ){
-          sqlite3Fts3DoclistPrev(
-              bDescDoclist, pPhrase->doclist.aAll, pPhrase->doclist.nAll, 
-              &pIter, &iDocid, &dummy, &bEof
+        bEof = !pPh->doclist.nAll ||
+          (pIter >= (pPh->doclist.aAll + pPh->doclist.nAll));
+        while( (pIter==0 || DOCID_CMP(iDocid, pCsr->iPrevId)<0 ) && bEof==0 ){
+          sqlite3Fts3DoclistNext(
+              bDescDoclist, pPh->doclist.aAll, pPh->doclist.nAll, 
+              &pIter, &iDocid, &bEof
           );
         }
       }else{
-        if( pNear->bEof ){
-          pIter = 0;
-          iDocid = 0;
-        }
-        while( (pIter==0 || DOCID_CMP(iDocid, pCsr->iPrevId)<0 ) && bEof==0 ){
-          sqlite3Fts3DoclistNext(
-              bDescDoclist, pPhrase->doclist.aAll, pPhrase->doclist.nAll, 
-              &pIter, &iDocid, &bEof
-          );
+        bEof = !pPh->doclist.nAll || (pIter && pIter<=pPh->doclist.aAll);
+        while( (pIter==0 || DOCID_CMP(iDocid, pCsr->iPrevId)>0 ) && bEof==0 ){
+          int dummy;
+          sqlite3Fts3DoclistPrev(
+              bDescDoclist, pPh->doclist.aAll, pPh->doclist.nAll, 
+              &pIter, &iDocid, &dummy, &bEof
+              );
         }
       }
+      pPh->pOrPoslist = pIter;
+      pPh->iOrDocid = iDocid;
+      if( bEof || iDocid!=pCsr->iPrevId ) bMatch = 0;
     }
 
-    if( bEof || iDocid!=pCsr->iPrevId ) pIter = 0;
+    if( bMatch ){
+      pIter = pPhrase->pOrPoslist;
+    }else{
+      pIter = 0;
+    }
   }
   if( pIter==0 ) return SQLITE_OK;
 
   if( *pIter==0x01 ){
     pIter++;
     pIter += fts3GetVarint32(pIter, &iThis);
   }else{
     iThis = 0;
   }
   while( iThis<iCol ){
     fts3ColumnlistCopy(0, &pIter);
-    if( *pIter==0x00 ) return 0;
+    if( *pIter==0x00 ) return SQLITE_OK;
     pIter++;
     pIter += fts3GetVarint32(pIter, &iThis);
   }
+  if( *pIter==0x00 ){
+    pIter = 0;
+  }
 
   *ppOut = ((iCol==iThis)?pIter:0);
   return SQLITE_OK;
 }
 
 /*
 ** Free all components of the Fts3Phrase structure that were allocated by
 ** the eval module. Specifically, this means to free:
 **
 **   * the contents of pPhrase->doclist, and
@@ skipping 33 matching lines @@
   sqlite3 *db, 
   char **pzErrMsg,
   const sqlite3_api_routines *pApi
 ){
   SQLITE_EXTENSION_INIT2(pApi)
   return sqlite3Fts3Init(db);
 }
 #endif
 
 #endif