Add //third_party/sqlite to dirs_to_snapshot, remove net_sql.patch

third_party/sqlite/sqlite-src-3070603/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.
+**
+******************************************************************************
+**
+** This is an SQLite module implementing full-text search.
+*/
+
+/*
+** The code in this file is only compiled if:
+**
+**     * The FTS3 module is being built as an extension
+**       (in which case SQLITE_CORE is not defined), or
+**
+**     * The FTS3 module is being built into the core of
+**       SQLite (in which case SQLITE_ENABLE_FTS3 is defined).
+*/
+
+/* The full-text index is stored in a series of b+tree (-like)
+** structures called segments which map terms to doclists.  The
+** structures are like b+trees in layout, but are constructed from the
+** bottom up in optimal fashion and are not updatable.  Since trees
+** are built from the bottom up, things will be described from the
+** bottom up.
+**
+**
+**** Varints ****
+** The basic unit of encoding is a variable-length integer called a
+** varint.  We encode variable-length integers in little-endian order
+** using seven bits * per byte as follows:
+**
+** KEY:
+**         A = 0xxxxxxx    7 bits of data and one flag bit
+**         B = 1xxxxxxx    7 bits of data and one flag bit
+**
+**  7 bits - A
+** 14 bits - BA
+** 21 bits - BBA
+** and so on.
+**
+** This is similar in concept to how sqlite encodes "varints" but
+** the encoding is not the same.  SQLite varints are big-endian
+** are are limited to 9 bytes in length whereas FTS3 varints are
+** little-endian and can be up to 10 bytes in length (in theory).
+**
+** Example encodings:
+**
+**     1:    0x01
+**   127:    0x7f
+**   128:    0x81 0x00
+**
+**
+**** Document lists ****
+** A doclist (document list) holds a docid-sorted list of hits for a
+** given term.  Doclists hold docids and associated token positions.
+** A docid is the unique integer identifier for a single document.
+** A position is the index of a word within the document.  The first 
+** word of the document has a position of 0.
+**
+** FTS3 used to optionally store character offsets using a compile-time
+** option.  But that functionality is no longer supported.
+**
+** A doclist is stored like this:
+**
+** array {
+**   varint docid;
+**   array {                (position list for column 0)
+**     varint position;     (2 more than the delta from previous position)
+**   }
+**   array {
+**     varint POS_COLUMN;   (marks start of position list for new column)
+**     varint column;       (index of new column)
+**     array {
+**       varint position;   (2 more than the delta from previous position)
+**     }
+**   }
+**   varint POS_END;        (marks end of positions for this document.
+** }
+**
+** Here, array { X } means zero or more occurrences of X, adjacent in
+** memory.  A "position" is an index of a token in the token stream
+** generated by the tokenizer. Note that POS_END and POS_COLUMN occur 
+** in the same logical place as the position element, and act as sentinals
+** ending a position list array.  POS_END is 0.  POS_COLUMN is 1.
+** The positions numbers are not stored literally but rather as two more
+** than the difference from the prior position, or the just the position plus
+** 2 for the first position.  Example:
+**
+**   label:       A B C D E  F  G H   I  J K
+**   value:     123 5 9 1 1 14 35 0 234 72 0
+**
+** The 123 value is the first docid.  For column zero in this document
+** there are two matches at positions 3 and 10 (5-2 and 9-2+3).  The 1
+** at D signals the start of a new column; the 1 at E indicates that the
+** new column is column number 1.  There are two positions at 12 and 45
+** (14-2 and 35-2+12).  The 0 at H indicate the end-of-document.  The
+** 234 at I is the next docid.  It has one position 72 (72-2) and then
+** terminates with the 0 at K.
+**
+** A "position-list" is the list of positions for multiple columns for
+** a single docid.  A "column-list" is the set of positions for a single
+** column.  Hence, a position-list consists of one or more column-lists,
+** a document record consists of a docid followed by a position-list and
+** a doclist consists of one or more document records.
+**
+** A bare doclist omits the position information, becoming an 
+** array of varint-encoded docids.
+**
+**** Segment leaf nodes ****
+** Segment leaf nodes store terms and doclists, ordered by term.  Leaf
+** nodes are written using LeafWriter, and read using LeafReader (to
+** iterate through a single leaf node's data) and LeavesReader (to
+** iterate through a segment's entire leaf layer).  Leaf nodes have
+** the format:
+**
+** varint iHeight;             (height from leaf level, always 0)
+** varint nTerm;               (length of first term)
+** char pTerm[nTerm];          (content of first term)
+** varint nDoclist;            (length of term's associated doclist)
+** char pDoclist[nDoclist];    (content of doclist)
+** array {
+**                             (further terms are delta-encoded)
+**   varint nPrefix;           (length of prefix shared with previous term)
+**   varint nSuffix;           (length of unshared suffix)
+**   char pTermSuffix[nSuffix];(unshared suffix of next term)
+**   varint nDoclist;          (length of term's associated doclist)
+**   char pDoclist[nDoclist];  (content of doclist)
+** }
+**
+** Here, array { X } means zero or more occurrences of X, adjacent in
+** memory.
+**
+** Leaf nodes are broken into blocks which are stored contiguously in
+** the %_segments table in sorted order.  This means that when the end
+** of a node is reached, the next term is in the node with the next
+** greater node id.
+**
+** New data is spilled to a new leaf node when the current node
+** exceeds LEAF_MAX bytes (default 2048).  New data which itself is
+** larger than STANDALONE_MIN (default 1024) is placed in a standalone
+** node (a leaf node with a single term and doclist).  The goal of
+** these settings is to pack together groups of small doclists while
+** making it efficient to directly access large doclists.  The
+** assumption is that large doclists represent terms which are more
+** likely to be query targets.
+**
+** TODO(shess) It may be useful for blocking decisions to be more
+** dynamic.  For instance, it may make more sense to have a 2.5k leaf
+** node rather than splitting into 2k and .5k nodes.  My intuition is
+** that this might extend through 2x or 4x the pagesize.
+**
+**
+**** Segment interior nodes ****
+** Segment interior nodes store blockids for subtree nodes and terms
+** to describe what data is stored by the each subtree.  Interior
+** nodes are written using InteriorWriter, and read using
+** InteriorReader.  InteriorWriters are created as needed when
+** SegmentWriter creates new leaf nodes, or when an interior node
+** itself grows too big and must be split.  The format of interior
+** nodes:
+**
+** varint iHeight;           (height from leaf level, always >0)
+** varint iBlockid;          (block id of node's leftmost subtree)
+** optional {
+**   varint nTerm;           (length of first term)
+**   char pTerm[nTerm];      (content of first term)
+**   array {
+**                                (further terms are delta-encoded)
+**     varint nPrefix;            (length of shared prefix with previous term)
+**     varint nSuffix;            (length of unshared suffix)
+**     char pTermSuffix[nSuffix]; (unshared suffix of next term)
+**   }
+** }
+**
+** Here, optional { X } means an optional element, while array { X }
+** means zero or more occurrences of X, adjacent in memory.
+**
+** An interior node encodes n terms separating n+1 subtrees.  The
+** subtree blocks are contiguous, so only the first subtree's blockid
+** is encoded.  The subtree at iBlockid will contain all terms less
+** than the first term encoded (or all terms if no term is encoded).
+** Otherwise, for terms greater than or equal to pTerm[i] but less
+** than pTerm[i+1], the subtree for that term will be rooted at
+** iBlockid+i.  Interior nodes only store enough term data to
+** distinguish adjacent children (if the rightmost term of the left
+** child is "something", and the leftmost term of the right child is
+** "wicked", only "w" is stored).
+**
+** New data is spilled to a new interior node at the same height when
+** the current node exceeds INTERIOR_MAX bytes (default 2048).
+** INTERIOR_MIN_TERMS (default 7) keeps large terms from monopolizing
+** interior nodes and making the tree too skinny.  The interior nodes
+** at a given height are naturally tracked by interior nodes at
+** height+1, and so on.
+**
+**
+**** Segment directory ****
+** The segment directory in table %_segdir stores meta-information for
+** merging and deleting segments, and also the root node of the
+** segment's tree.
+**
+** The root node is the top node of the segment's tree after encoding
+** the entire segment, restricted to ROOT_MAX bytes (default 1024).
+** This could be either a leaf node or an interior node.  If the top
+** node requires more than ROOT_MAX bytes, it is flushed to %_segments
+** and a new root interior node is generated (which should always fit
+** within ROOT_MAX because it only needs space for 2 varints, the
+** height and the blockid of the previous root).
+**
+** The meta-information in the segment directory is:
+**   level               - segment level (see below)
+**   idx                 - index within level
+**                       - (level,idx uniquely identify a segment)
+**   start_block         - first leaf node
+**   leaves_end_block    - last leaf node
+**   end_block           - last block (including interior nodes)
+**   root                - contents of root node
+**
+** If the root node is a leaf node, then start_block,
+** leaves_end_block, and end_block are all 0.
+**
+**
+**** Segment merging ****
+** To amortize update costs, segments are grouped into levels and
+** merged in batches.  Each increase in level represents exponentially
+** more documents.
+**
+** New documents (actually, document updates) are tokenized and
+** written individually (using LeafWriter) to a level 0 segment, with
+** incrementing idx.  When idx reaches MERGE_COUNT (default 16), all
+** level 0 segments are merged into a single level 1 segment.  Level 1
+** is populated like level 0, and eventually MERGE_COUNT level 1
+** segments are merged to a single level 2 segment (representing
+** MERGE_COUNT^2 updates), and so on.
+**
+** A segment merge traverses all segments at a given level in
+** parallel, performing a straightforward sorted merge.  Since segment
+** leaf nodes are written in to the %_segments table in order, this
+** merge traverses the underlying sqlite disk structures efficiently.
+** After the merge, all segment blocks from the merged level are
+** deleted.
+**
+** MERGE_COUNT controls how often we merge segments.  16 seems to be
+** somewhat of a sweet spot for insertion performance.  32 and 64 show
+** very similar performance numbers to 16 on insertion, though they're
+** a tiny bit slower (perhaps due to more overhead in merge-time
+** sorting).  8 is about 20% slower than 16, 4 about 50% slower than
+** 16, 2 about 66% slower than 16.
+**
+** At query time, high MERGE_COUNT increases the number of segments
+** which need to be scanned and merged.  For instance, with 100k docs
+** inserted:
+**
+**    MERGE_COUNT   segments
+**       16           25
+**        8           12
+**        4           10
+**        2            6
+**
+** This appears to have only a moderate impact on queries for very
+** frequent terms (which are somewhat dominated by segment merge
+** costs), and infrequent and non-existent terms still seem to be fast
+** even with many segments.
+**
+** TODO(shess) That said, it would be nice to have a better query-side
+** argument for MERGE_COUNT of 16.  Also, it is possible/likely that
+** optimizations to things like doclist merging will swing the sweet
+** spot around.
+**
+**
+**
+**** Handling of deletions and updates ****
+** Since we're using a segmented structure, with no docid-oriented
+** index into the term index, we clearly cannot simply update the term
+** index when a document is deleted or updated.  For deletions, we
+** write an empty doclist (varint(docid) varint(POS_END)), for updates
+** we simply write the new doclist.  Segment merges overwrite older
+** data for a particular docid with newer data, so deletes or updates
+** will eventually overtake the earlier data and knock it out.  The
+** query logic likewise merges doclists so that newer data knocks out
+** older data.
+**
+** TODO(shess) Provide a VACUUM type operation to clear out all
+** deletions and duplications.  This would basically be a forced merge
+** into a single segment.
+*/
+
+#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)
+
+#if defined(SQLITE_ENABLE_FTS3) && !defined(SQLITE_CORE)
+# define SQLITE_CORE 1
+#endif
+
+#include "fts3Int.h"
+
+#include <assert.h>
+#include <stdlib.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <string.h>
+#include <stdarg.h>
+
+#include "fts3.h"
+#ifndef SQLITE_CORE 
+# include "sqlite3ext.h"
+  SQLITE_EXTENSION_INIT1
+#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);
+    vu >>= 7;
+  }while( vu!=0 );
+  q[-1] &= 0x7f;  /* turn off high bit in final byte */
+  assert( q - (unsigned char *)p <= FTS3_VARINT_MAX );
+  return (int) (q - (unsigned char *)p);
+}
+
+/* 
+** Read a 64-bit variable-length integer from memory starting at p[0].
+** Return the number of bytes read, or 0 on error.
+** The value is stored in *v.
+*/
+int sqlite3Fts3GetVarint(const char *p, sqlite_int64 *v){
+  const unsigned char *q = (const unsigned char *) p;
+  sqlite_uint64 x = 0, y = 1;
+  while( (*q&0x80)==0x80 && q-(unsigned char *)p<FTS3_VARINT_MAX ){
+    x += y * (*q++ & 0x7f);
+    y <<= 7;
+  }
+  x += y * (*q++);
+  *v = (sqlite_int64) x;
+  return (int) (q - (unsigned char *)p);
+}
+
+/*
+** Similar to sqlite3Fts3GetVarint(), except that the output is truncated to a
+** 32-bit integer before it is returned.
+*/
+int sqlite3Fts3GetVarint32(const char *p, int *pi){
+ sqlite_int64 i;
+ int ret = sqlite3Fts3GetVarint(p, &i);
+ *pi = (int) i;
+ return ret;
+}
+
+/*
+** Return the number of bytes required to encode v as a varint
+*/
+int sqlite3Fts3VarintLen(sqlite3_uint64 v){
+  int i = 0;
+  do{
+    i++;
+    v >>= 7;
+  }while( v!=0 );
+  return i;
+}
+
+/*
+** Convert an SQL-style quoted string into a normal string by removing
+** the quote characters.  The conversion is done in-place.  If the
+** input does not begin with a quote character, then this routine
+** is a no-op.
+**
+** Examples:
+**
+**     "abc"   becomes   abc
+**     'xyz'   becomes   xyz
+**     [pqr]   becomes   pqr
+**     `mno`   becomes   mno
+**
+*/
+void sqlite3Fts3Dequote(char *z){
+  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]) ){
+      if( z[iIn]==quote ){
+        if( z[iIn+1]!=quote ) break;
+        z[iOut++] = quote;
+        iIn += 2;
+      }else{
+        z[iOut++] = z[iIn++];
+      }
+    }
+    z[iOut] = '\0';
+  }
+}
+
+/*
+** Read a single varint from the doclist at *pp and advance *pp to point
+** to the first byte past the end of the varint.  Add the value of the varint
+** to *pVal.
+*/
+static void fts3GetDeltaVarint(char **pp, sqlite3_int64 *pVal){
+  sqlite3_int64 iVal;
+  *pp += sqlite3Fts3GetVarint(*pp, &iVal);
+  *pVal += iVal;
+}
+
+/*
+** As long as *pp has not reached its end (pEnd), then do the same
+** as fts3GetDeltaVarint(): read a single varint and add it to *pVal.
+** But if we have reached the end of the varint, just set *pp=0 and
+** leave *pVal unchanged.
+*/
+static void fts3GetDeltaVarint2(char **pp, char *pEnd, sqlite3_int64 *pVal){
+  if( *pp>=pEnd ){
+    *pp = 0;
+  }else{
+    fts3GetDeltaVarint(pp, pVal);
+  }
+}
+
+/*
+** The xDisconnect() virtual table method.
+*/
+static int fts3DisconnectMethod(sqlite3_vtab *pVtab){
+  Fts3Table *p = (Fts3Table *)pVtab;
+  int i;
+
+  assert( p->nPendingData==0 );
+  assert( p->pSegments==0 );
+
+  /* Free any prepared statements held */
+  for(i=0; i<SizeofArray(p->aStmt); i++){
+    sqlite3_finalize(p->aStmt[i]);
+  }
+  sqlite3_free(p->zSegmentsTbl);
+  sqlite3_free(p->zReadExprlist);
+  sqlite3_free(p->zWriteExprlist);
+
+  /* Invoke the tokenizer destructor to free the tokenizer. */
+  p->pTokenizer->pModule->xDestroy(p->pTokenizer);
+
+  sqlite3_free(p);
+  return SQLITE_OK;
+}
+
+/*
+** 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 */
+  ...                    /* Arguments to the format string */
+){
+  va_list ap;
+  char *zSql;
+  if( *pRc ) return;
+  va_start(ap, zFormat);
+  zSql = sqlite3_vmprintf(zFormat, ap);
+  va_end(ap);
+  if( zSql==0 ){
+    *pRc = SQLITE_NOMEM;
+  }else{
+    *pRc = sqlite3_exec(db, zSql, 0, 0, 0);
+    sqlite3_free(zSql);
+  }
+}
+
+/*
+** The xDestroy() virtual table method.
+*/
+static int fts3DestroyMethod(sqlite3_vtab *pVtab){
+  int rc = SQLITE_OK;              /* Return code */
+  Fts3Table *p = (Fts3Table *)pVtab;
+  sqlite3 *db = p->db;
+
+  /* Drop the shadow tables */
+  fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_content'", p->zDb, p->zName);
+  fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_segments'", p->zDb,p->zName);
+  fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_segdir'", p->zDb, p->zName);
+  fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_docsize'", p->zDb, p->zName);
+  fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_stat'", p->zDb, p->zName);
+
+  /* If everything has worked, invoke fts3DisconnectMethod() to free the
+  ** memory associated with the Fts3Table structure and return SQLITE_OK.
+  ** Otherwise, return an SQLite error code.
+  */
+  return (rc==SQLITE_OK ? fts3DisconnectMethod(pVtab) : rc);
+}
+
+
+/*
+** Invoke sqlite3_declare_vtab() to declare the schema for the FTS3 table
+** passed as the first argument. This is done as part of the xConnect()
+** and xCreate() methods.
+**
+** If *pRc is non-zero when this function is called, it is a no-op. 
+** Otherwise, if an error occurs, an SQLite error code is stored in *pRc
+** before returning.
+*/
+static void fts3DeclareVtab(int *pRc, Fts3Table *p){
+  if( *pRc==SQLITE_OK ){
+    int i;                        /* Iterator variable */
+    int rc;                       /* Return code */
+    char *zSql;                   /* SQL statement passed to declare_vtab() */
+    char *zCols;                  /* List of user defined columns */
+
+    /* Create a list of user columns for the virtual table */
+    zCols = sqlite3_mprintf("%Q, ", p->azColumn[0]);
+    for(i=1; zCols && i<p->nColumn; i++){
+      zCols = sqlite3_mprintf("%z%Q, ", zCols, p->azColumn[i]);
+    }
+
+    /* Create the whole "CREATE TABLE" statement to pass to SQLite */
+    zSql = sqlite3_mprintf(
+        "CREATE TABLE x(%s %Q HIDDEN, docid HIDDEN)", zCols, p->zName
+    );
+    if( !zCols || !zSql ){
+      rc = SQLITE_NOMEM;
+    }else{
+      rc = sqlite3_declare_vtab(p->db, zSql);
+    }
+
+    sqlite3_free(zSql);
+    sqlite3_free(zCols);
+    *pRc = rc;
+  }
+}
+
+/*
+** Create the backing store tables (%_content, %_segments and %_segdir)
+** required by the FTS3 table passed as the only argument. This is done
+** as part of the vtab xCreate() method.
+**
+** If the p->bHasDocsize boolean is true (indicating that this is an
+** FTS4 table, not an FTS3 table) then also create the %_docsize and
+** %_stat tables required by FTS4.
+*/
+static int fts3CreateTables(Fts3Table *p){
+  int rc = SQLITE_OK;             /* Return code */
+  int i;                          /* Iterator variable */
+  char *zContentCols;             /* Columns of %_content table */
+  sqlite3 *db = p->db;            /* The database connection */
+
+  /* Create a list of user columns for the content table */
+  zContentCols = sqlite3_mprintf("docid INTEGER PRIMARY KEY");
+  for(i=0; zContentCols && i<p->nColumn; i++){
+    char *z = p->azColumn[i];
+    zContentCols = sqlite3_mprintf("%z, 'c%d%q'", zContentCols, i, z);
+  }
+  if( zContentCols==0 ) rc = SQLITE_NOMEM;
+
+  /* Create the content table */
+  fts3DbExec(&rc, db, 
+     "CREATE TABLE %Q.'%q_content'(%s)",
+     p->zDb, p->zName, zContentCols
+  );
+  sqlite3_free(zContentCols);
+  /* Create other tables */
+  fts3DbExec(&rc, db, 
+      "CREATE TABLE %Q.'%q_segments'(blockid INTEGER PRIMARY KEY, block BLOB);",
+      p->zDb, p->zName
+  );
+  fts3DbExec(&rc, db, 
+      "CREATE TABLE %Q.'%q_segdir'("
+        "level INTEGER,"
+        "idx INTEGER,"
+        "start_block INTEGER,"
+        "leaves_end_block INTEGER,"
+        "end_block INTEGER,"
+        "root BLOB,"
+        "PRIMARY KEY(level, idx)"
+      ");",
+      p->zDb, p->zName
+  );
+  if( p->bHasDocsize ){
+    fts3DbExec(&rc, db, 
+        "CREATE TABLE %Q.'%q_docsize'(docid INTEGER PRIMARY KEY, size BLOB);",
+        p->zDb, p->zName
+    );
+  }
+  if( p->bHasStat ){
+    fts3DbExec(&rc, db, 
+        "CREATE TABLE %Q.'%q_stat'(id INTEGER PRIMARY KEY, value BLOB);",
+        p->zDb, p->zName
+    );
+  }
+  return rc;
+}
+
+/*
+** Store the current database page-size in bytes in p->nPgsz.
+**
+** If *pRc is non-zero when this function is called, it is a no-op. 
+** Otherwise, if an error occurs, an SQLite error code is stored in *pRc
+** before returning.
+*/
+static void fts3DatabasePageSize(int *pRc, Fts3Table *p){
+  if( *pRc==SQLITE_OK ){
+    int rc;                       /* Return code */
+    char *zSql;                   /* SQL text "PRAGMA %Q.page_size" */
+    sqlite3_stmt *pStmt;          /* Compiled "PRAGMA %Q.page_size" statement */
+  
+    zSql = sqlite3_mprintf("PRAGMA %Q.page_size", p->zDb);
+    if( !zSql ){
+      rc = SQLITE_NOMEM;
+    }else{
+      rc = sqlite3_prepare(p->db, zSql, -1, &pStmt, 0);
+      if( rc==SQLITE_OK ){
+        sqlite3_step(pStmt);
+        p->nPgsz = sqlite3_column_int(pStmt, 0);
+        rc = sqlite3_finalize(pStmt);
+      }
+    }
+    assert( p->nPgsz>0 || rc!=SQLITE_OK );
+    sqlite3_free(zSql);
+    *pRc = rc;
+  }
+}
+
+/*
+** "Special" FTS4 arguments are column specifications of the following form:
+**
+**   <key> = <value>
+**
+** There may not be whitespace surrounding the "=" character. The <value> 
+** term may be quoted, but the <key> may not.
+*/
+static int fts3IsSpecialColumn(
+  const char *z, 
+  int *pnKey,
+  char **pzValue
+){
+  char *zValue;
+  const char *zCsr = z;
+
+  while( *zCsr!='=' ){
+    if( *zCsr=='\0' ) return 0;
+    zCsr++;
+  }
+
+  *pnKey = (int)(zCsr-z);
+  zValue = sqlite3_mprintf("%s", &zCsr[1]);
+  if( zValue ){
+    sqlite3Fts3Dequote(zValue);
+  }
+  *pzValue = zValue;
+  return 1;
+}
+
+/*
+** Append the output of a printf() style formatting to an existing string.
+*/
+static void fts3Appendf(
+  int *pRc,                       /* IN/OUT: Error code */
+  char **pz,                      /* IN/OUT: Pointer to string buffer */
+  const char *zFormat,            /* Printf format string to append */
+  ...                             /* Arguments for printf format string */
+){
+  if( *pRc==SQLITE_OK ){
+    va_list ap;
+    char *z;
+    va_start(ap, zFormat);
+    z = sqlite3_vmprintf(zFormat, ap);
+    if( z && *pz ){
+      char *z2 = sqlite3_mprintf("%s%s", *pz, z);
+      sqlite3_free(z);
+      z = z2;
+    }
+    if( z==0 ) *pRc = SQLITE_NOMEM;
+    sqlite3_free(*pz);
+    *pz = z;
+  }
+}
+
+/*
+** Return a copy of input string zInput enclosed in double-quotes (") and
+** with all double quote characters escaped. For example:
+**
+**     fts3QuoteId("un \"zip\"")   ->    "un \"\"zip\"\""
+**
+** The pointer returned points to memory obtained from sqlite3_malloc(). It
+** is the callers responsibility to call sqlite3_free() to release this
+** memory.
+*/
+static char *fts3QuoteId(char const *zInput){
+  int nRet;
+  char *zRet;
+  nRet = 2 + strlen(zInput)*2 + 1;
+  zRet = sqlite3_malloc(nRet);
+  if( zRet ){
+    int i;
+    char *z = zRet;
+    *(z++) = '"';
+    for(i=0; zInput[i]; i++){
+      if( zInput[i]=='"' ) *(z++) = '"';
+      *(z++) = zInput[i];
+    }
+    *(z++) = '"';
+    *(z++) = '\0';
+  }
+  return zRet;
+}
+
+/*
+** Return a list of comma separated SQL expressions that could be used
+** in a SELECT statement such as the following:
+**
+**     SELECT <list of expressions> FROM %_content AS x ...
+**
+** to return the docid, followed by each column of text data in order
+** from left to write. If parameter zFunc is not NULL, then instead of
+** being returned directly each column of text data is passed to an SQL
+** function named zFunc first. For example, if zFunc is "unzip" and the
+** table has the three user-defined columns "a", "b", and "c", the following
+** string is returned:
+**
+**     "docid, unzip(x.'a'), unzip(x.'b'), unzip(x.'c')"
+**
+** The pointer returned points to a buffer allocated by sqlite3_malloc(). It
+** is the responsibility of the caller to eventually free it.
+**
+** If *pRc is not SQLITE_OK when this function is called, it is a no-op (and
+** a NULL pointer is returned). Otherwise, if an OOM error is encountered
+** by this function, NULL is returned and *pRc is set to SQLITE_NOMEM. If
+** no error occurs, *pRc is left unmodified.
+*/
+static char *fts3ReadExprList(Fts3Table *p, const char *zFunc, int *pRc){
+  char *zRet = 0;
+  char *zFree = 0;
+  char *zFunction;
+  int i;
+
+  if( !zFunc ){
+    zFunction = "";
+  }else{
+    zFree = zFunction = fts3QuoteId(zFunc);
+  }
+  fts3Appendf(pRc, &zRet, "docid");
+  for(i=0; i<p->nColumn; i++){
+    fts3Appendf(pRc, &zRet, ",%s(x.'c%d%q')", zFunction, i, p->azColumn[i]);
+  }
+  sqlite3_free(zFree);
+  return zRet;
+}
+
+/*
+** Return a list of N comma separated question marks, where N is the number
+** of columns in the %_content table (one for the docid plus one for each
+** user-defined text column).
+**
+** If argument zFunc is not NULL, then all but the first question mark
+** is preceded by zFunc and an open bracket, and followed by a closed
+** bracket. For example, if zFunc is "zip" and the FTS3 table has three 
+** user-defined text columns, the following string is returned:
+**
+**     "?, zip(?), zip(?), zip(?)"
+**
+** The pointer returned points to a buffer allocated by sqlite3_malloc(). It
+** is the responsibility of the caller to eventually free it.
+**
+** If *pRc is not SQLITE_OK when this function is called, it is a no-op (and
+** a NULL pointer is returned). Otherwise, if an OOM error is encountered
+** by this function, NULL is returned and *pRc is set to SQLITE_NOMEM. If
+** no error occurs, *pRc is left unmodified.
+*/
+static char *fts3WriteExprList(Fts3Table *p, const char *zFunc, int *pRc){
+  char *zRet = 0;
+  char *zFree = 0;
+  char *zFunction;
+  int i;
+
+  if( !zFunc ){
+    zFunction = "";
+  }else{
+    zFree = zFunction = fts3QuoteId(zFunc);
+  }
+  fts3Appendf(pRc, &zRet, "?");
+  for(i=0; i<p->nColumn; i++){
+    fts3Appendf(pRc, &zRet, ",%s(?)", zFunction);
+  }
+  sqlite3_free(zFree);
+  return zRet;
+}
+
+/*
+** This function is the implementation of both the xConnect and xCreate
+** methods of the FTS3 virtual table.
+**
+** The argv[] array contains the following:
+**
+**   argv[0]   -> module name  ("fts3" or "fts4")
+**   argv[1]   -> database name
+**   argv[2]   -> table name
+**   argv[...] -> "column name" and other module argument fields.
+*/
+static int fts3InitVtab(
+  int isCreate,                   /* True for xCreate, false for xConnect */
+  sqlite3 *db,                    /* The SQLite database connection */
+  void *pAux,                     /* Hash table containing tokenizers */
+  int argc,                       /* Number of elements in argv array */
+  const char * const *argv,       /* xCreate/xConnect argument array */
+  sqlite3_vtab **ppVTab,          /* Write the resulting vtab structure here */
+  char **pzErr                    /* Write any error message here */
+){
+  Fts3Hash *pHash = (Fts3Hash *)pAux;
+  Fts3Table *p = 0;               /* Pointer to allocated vtab */
+  int rc = SQLITE_OK;             /* Return code */
+  int i;                          /* Iterator variable */
+  int nByte;                      /* Size of allocation used for *p */
+  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 */
+  int bNoDocsize = 0;             /* True to omit %_docsize table */
+  const char **aCol;              /* Array of column names */
+  sqlite3_tokenizer *pTokenizer = 0;        /* Tokenizer for this table */
+
+  char *zCompress = 0;
+  char *zUncompress = 0;
+
+  assert( strlen(argv[0])==4 );
+  assert( (sqlite3_strnicmp(argv[0], "fts4", 4)==0 && isFts4)
+       || (sqlite3_strnicmp(argv[0], "fts3", 4)==0 && !isFts4)
+  );
+
+  nDb = (int)strlen(argv[1]) + 1;
+  nName = (int)strlen(argv[2]) + 1;
+
+  aCol = (const char **)sqlite3_malloc(sizeof(const char *) * (argc-2) );
+  if( !aCol ) return SQLITE_NOMEM;
+  memset((void *)aCol, 0, sizeof(const char *) * (argc-2));
+
+  /* Loop through all of the arguments passed by the user to the FTS3/4
+  ** module (i.e. all the column names and special arguments). This loop
+  ** does the following:
+  **
+  **   + Figures out the number of columns the FTSX table will have, and
+  **     the number of bytes of space that must be allocated to store copies
+  **     of the column names.
+  **
+  **   + If there is a tokenizer specification included in the arguments,
+  **     initializes the tokenizer pTokenizer.
+  */
+  for(i=3; rc==SQLITE_OK && i<argc; i++){
+    char const *z = argv[i];
+    int nKey;
+    char *zVal;
+
+    /* Check if this is a tokenizer specification */
+    if( !pTokenizer 
+     && strlen(z)>8
+     && 0==sqlite3_strnicmp(z, "tokenize", 8) 
+     && 0==sqlite3Fts3IsIdChar(z[8])
+    ){
+      rc = sqlite3Fts3InitTokenizer(pHash, &z[9], &pTokenizer, pzErr);
+    }
+
+    /* Check if it is an FTS4 special argument. */
+    else if( isFts4 && fts3IsSpecialColumn(z, &nKey, &zVal) ){
+      if( !zVal ){
+        rc = SQLITE_NOMEM;
+        goto fts3_init_out;
+      }
+      if( nKey==9 && 0==sqlite3_strnicmp(z, "matchinfo", 9) ){
+        if( strlen(zVal)==4 && 0==sqlite3_strnicmp(zVal, "fts3", 4) ){
+          bNoDocsize = 1;
+        }else{
+          *pzErr = sqlite3_mprintf("unrecognized matchinfo: %s", zVal);
+          rc = SQLITE_ERROR;
+        }
+      }else if( nKey==8 && 0==sqlite3_strnicmp(z, "compress", 8) ){
+        zCompress = zVal;
+        zVal = 0;
+      }else if( nKey==10 && 0==sqlite3_strnicmp(z, "uncompress", 10) ){
+        zUncompress = zVal;
+        zVal = 0;
+      }else{
+        *pzErr = sqlite3_mprintf("unrecognized parameter: %s", z);
+        rc = SQLITE_ERROR;
+      }
+      sqlite3_free(zVal);
+    }
+
+    /* Otherwise, the argument is a column name. */
+    else {
+      nString += (int)(strlen(z) + 1);
+      aCol[nCol++] = z;
+    }
+  }
+  if( rc!=SQLITE_OK ) goto fts3_init_out;
+
+  if( nCol==0 ){
+    assert( nString==0 );
+    aCol[0] = "content";
+    nString = 8;
+    nCol = 1;
+  }
+
+  if( pTokenizer==0 ){
+    rc = sqlite3Fts3InitTokenizer(pHash, "simple", &pTokenizer, pzErr);
+    if( rc!=SQLITE_OK ) goto fts3_init_out;
+  }
+  assert( pTokenizer );
+
+
+  /* Allocate and populate the Fts3Table structure. */
+  nByte = sizeof(Fts3Table) +              /* Fts3Table */
+          nCol * sizeof(char *) +              /* azColumn */
+          nName +                              /* zName */
+          nDb +                                /* zDb */
+          nString;                             /* Space for azColumn strings */
+  p = (Fts3Table*)sqlite3_malloc(nByte);
+  if( p==0 ){
+    rc = SQLITE_NOMEM;
+    goto fts3_init_out;
+  }
+  memset(p, 0, nByte);
+  p->db = db;
+  p->nColumn = nCol;
+  p->nPendingData = 0;
+  p->azColumn = (char **)&p[1];
+  p->pTokenizer = pTokenizer;
+  p->nNodeSize = 1000;
+  p->nMaxPendingData = FTS3_MAX_PENDING_DATA;
+  p->bHasDocsize = (isFts4 && bNoDocsize==0);
+  p->bHasStat = isFts4;
+  fts3HashInit(&p->pendingTerms, FTS3_HASH_STRING, 1);
+
+  /* Fill in the zName and zDb fields of the vtab structure. */
+  zCsr = (char *)&p->azColumn[nCol];
+  p->zName = zCsr;
+  memcpy(zCsr, argv[2], nName);
+  zCsr += nName;
+  p->zDb = zCsr;
+  memcpy(zCsr, argv[1], nDb);
+  zCsr += nDb;
+
+  /* Fill in the azColumn array */
+  for(iCol=0; iCol<nCol; iCol++){
+    char *z; 
+    int n;
+    z = (char *)sqlite3Fts3NextToken(aCol[iCol], &n);
+    memcpy(zCsr, z, n);
+    zCsr[n] = '\0';
+    sqlite3Fts3Dequote(zCsr);
+    p->azColumn[iCol] = zCsr;
+    zCsr += n+1;
+    assert( zCsr <= &((char *)p)[nByte] );
+  }
+
+  if( (zCompress==0)!=(zUncompress==0) ){
+    char const *zMiss = (zCompress==0 ? "compress" : "uncompress");
+    rc = SQLITE_ERROR;
+    *pzErr = sqlite3_mprintf("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);
+  }
+
+  /* Figure out the page-size for the database. This is required in order to
+  ** estimate the cost of loading large doclists from the database (see 
+  ** function sqlite3Fts3SegReaderCost() for details).
+  */
+  fts3DatabasePageSize(&rc, p);
+
+  /* Declare the table schema to SQLite. */
+  fts3DeclareVtab(&rc, p);
+
+fts3_init_out:
+  sqlite3_free(zCompress);
+  sqlite3_free(zUncompress);
+  sqlite3_free((void *)aCol);
+  if( rc!=SQLITE_OK ){
+    if( p ){
+      fts3DisconnectMethod((sqlite3_vtab *)p);
+    }else if( pTokenizer ){
+      pTokenizer->pModule->xDestroy(pTokenizer);
+    }
+  }else{
+    *ppVTab = &p->base;
+  }
+  return rc;
+}
+
+/*
+** The xConnect() and xCreate() methods for the virtual table. All the
+** work is done in function fts3InitVtab().
+*/
+static int fts3ConnectMethod(
+  sqlite3 *db,                    /* Database connection */
+  void *pAux,                     /* Pointer to tokenizer hash table */
+  int argc,                       /* Number of elements in argv array */
+  const char * const *argv,       /* xCreate/xConnect argument array */
+  sqlite3_vtab **ppVtab,          /* OUT: New sqlite3_vtab object */
+  char **pzErr                    /* OUT: sqlite3_malloc'd error message */
+){
+  return fts3InitVtab(0, db, pAux, argc, argv, ppVtab, pzErr);
+}
+static int fts3CreateMethod(
+  sqlite3 *db,                    /* Database connection */
+  void *pAux,                     /* Pointer to tokenizer hash table */
+  int argc,                       /* Number of elements in argv array */
+  const char * const *argv,       /* xCreate/xConnect argument array */
+  sqlite3_vtab **ppVtab,          /* OUT: New sqlite3_vtab object */
+  char **pzErr                    /* OUT: sqlite3_malloc'd error message */
+){
+  return fts3InitVtab(1, db, pAux, argc, argv, ppVtab, pzErr);
+}
+
+/* 
+** 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;
+  int i;                          /* Iterator variable */
+  int iCons = -1;                 /* Index of constraint to use */
+
+  /* By default use a full table scan. This is an expensive option,
+  ** so search through the constraints to see if a more efficient 
+  ** strategy is possible.
+  */
+  pInfo->idxNum = FTS3_FULLSCAN_SEARCH;
+  pInfo->estimatedCost = 500000;
+  for(i=0; i<pInfo->nConstraint; i++){
+    struct sqlite3_index_constraint *pCons = &pInfo->aConstraint[i];
+    if( pCons->usable==0 ) continue;
+
+    /* A direct lookup on the rowid or docid column. Assign a cost of 1.0. */
+    if( pCons->op==SQLITE_INDEX_CONSTRAINT_EQ 
+     && (pCons->iColumn<0 || pCons->iColumn==p->nColumn+1 )
+    ){
+      pInfo->idxNum = FTS3_DOCID_SEARCH;
+      pInfo->estimatedCost = 1.0;
+      iCons = i;
+    }
+
+    /* A MATCH constraint. Use a full-text search.
+    **
+    ** If there is more than one MATCH constraint available, use the first
+    ** one encountered. If there is both a MATCH constraint and a direct
+    ** rowid/docid lookup, prefer the MATCH strategy. This is done even 
+    ** though the rowid/docid lookup is faster than a MATCH query, selecting
+    ** it would lead to an "unable to use function MATCH in the requested 
+    ** context" error.
+    */
+    if( pCons->op==SQLITE_INDEX_CONSTRAINT_MATCH 
+     && pCons->iColumn>=0 && pCons->iColumn<=p->nColumn
+    ){
+      pInfo->idxNum = FTS3_FULLTEXT_SEARCH + pCons->iColumn;
+      pInfo->estimatedCost = 2.0;
+      iCons = i;
+      break;
+    }
+  }
+
+  if( iCons>=0 ){
+    pInfo->aConstraintUsage[iCons].argvIndex = 1;
+    pInfo->aConstraintUsage[iCons].omit = 1;
+  } 
+  return SQLITE_OK;
+}
+
+/*
+** Implementation of xOpen method.
+*/
+static int fts3OpenMethod(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCsr){
+  sqlite3_vtab_cursor *pCsr;               /* Allocated cursor */
+
+  UNUSED_PARAMETER(pVTab);
+
+  /* Allocate a buffer large enough for an Fts3Cursor structure. If the
+  ** allocation succeeds, zero it and return SQLITE_OK. Otherwise, 
+  ** if the allocation fails, return SQLITE_NOMEM.
+  */
+  *ppCsr = pCsr = (sqlite3_vtab_cursor *)sqlite3_malloc(sizeof(Fts3Cursor));
+  if( !pCsr ){
+    return SQLITE_NOMEM;
+  }
+  memset(pCsr, 0, sizeof(Fts3Cursor));
+  return SQLITE_OK;
+}
+
+/*
+** 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);
+  sqlite3_free(pCsr);
+  return SQLITE_OK;
+}
+
+/*
+** Position the pCsr->pStmt statement so that it is on the row
+** of the %_content table that contains the last match.  Return
+** SQLITE_OK on success.  
+*/
+static int fts3CursorSeek(sqlite3_context *pContext, Fts3Cursor *pCsr){
+  if( pCsr->isRequireSeek ){
+    pCsr->isRequireSeek = 0;
+    sqlite3_bind_int64(pCsr->pStmt, 1, pCsr->iPrevId);
+    if( SQLITE_ROW==sqlite3_step(pCsr->pStmt) ){
+      return SQLITE_OK;
+    }else{
+      int rc = sqlite3_reset(pCsr->pStmt);
+      if( rc==SQLITE_OK ){
+        /* If no row was found and no error has occured, then the %_content
+        ** table is missing a row that is present in the full-text index.
+        ** The data structures are corrupt.
+        */
+        rc = SQLITE_CORRUPT;
+      }
+      pCsr->isEof = 1;
+      if( pContext ){
+        sqlite3_result_error_code(pContext, rc);
+      }
+      return rc;
+    }
+  }else{
+    return SQLITE_OK;
+  }
+}
+
+/*
+** This function is used to process a single interior node when searching
+** a b-tree for a term or term prefix. The node data is passed to this 
+** function via the zNode/nNode parameters. The term to search for is
+** passed in zTerm/nTerm.
+**
+** If piFirst is not NULL, then this function sets *piFirst to the blockid
+** of the child node that heads the sub-tree that may contain the term.
+**
+** If piLast is not NULL, then *piLast is set to the right-most child node
+** that heads a sub-tree that may contain a term for which zTerm/nTerm is
+** a prefix.
+**
+** If an OOM error occurs, SQLITE_NOMEM is returned. Otherwise, SQLITE_OK.
+*/
+static int fts3ScanInteriorNode(
+  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 *piFirst,         /* OUT: Selected child node */
+  sqlite3_int64 *piLast           /* OUT: Selected child node */
+){
+  int rc = SQLITE_OK;             /* Return code */
+  const char *zCsr = zNode;       /* Cursor to iterate through node */
+  const char *zEnd = &zCsr[nNode];/* End of interior node buffer */
+  char *zBuffer = 0;              /* Buffer to load terms into */
+  int nAlloc = 0;                 /* Size of allocated buffer */
+  int isFirstTerm = 1;            /* True when processing first term on page */
+  sqlite3_int64 iChild;           /* Block id of child node to descend to */
+
+  /* Skip over the 'height' varint that occurs at the start of every 
+  ** interior node. Then load the blockid of the left-child of the b-tree
+  ** node into variable iChild.  
+  **
+  ** Even if the data structure on disk is corrupted, this (reading two
+  ** varints from the buffer) does not risk an overread. If zNode is a
+  ** root node, then the buffer comes from a SELECT statement. SQLite does
+  ** not make this guarantee explicitly, but in practice there are always
+  ** either more than 20 bytes of allocated space following the nNode bytes of
+  ** contents, or two zero bytes. Or, if the node is read from the %_segments
+  ** table, then there are always 20 bytes of zeroed padding following the
+  ** nNode bytes of content (see sqlite3Fts3ReadBlock() for details).
+  */
+  zCsr += sqlite3Fts3GetVarint(zCsr, &iChild);
+  zCsr += sqlite3Fts3GetVarint(zCsr, &iChild);
+  if( zCsr>zEnd ){
+    return SQLITE_CORRUPT;
+  }
+  
+  while( zCsr<zEnd && (piFirst || piLast) ){
+    int cmp;                      /* memcmp() result */
+    int nSuffix;                  /* Size of term suffix */
+    int nPrefix = 0;              /* Size of term prefix */
+    int nBuffer;                  /* Total term size */
+  
+    /* Load the next term on the node into zBuffer. Use realloc() to expand
+    ** the size of zBuffer if required.  */
+    if( !isFirstTerm ){
+      zCsr += sqlite3Fts3GetVarint32(zCsr, &nPrefix);
+    }
+    isFirstTerm = 0;
+    zCsr += sqlite3Fts3GetVarint32(zCsr, &nSuffix);
+    
+    if( nPrefix<0 || nSuffix<0 || &zCsr[nSuffix]>zEnd ){
+      rc = SQLITE_CORRUPT;
+      goto finish_scan;
+    }
+    if( nPrefix+nSuffix>nAlloc ){
+      char *zNew;
+      nAlloc = (nPrefix+nSuffix) * 2;
+      zNew = (char *)sqlite3_realloc(zBuffer, nAlloc);
+      if( !zNew ){
+        rc = SQLITE_NOMEM;
+        goto finish_scan;
+      }
+      zBuffer = zNew;
+    }
+    memcpy(&zBuffer[nPrefix], zCsr, nSuffix);
+    nBuffer = nPrefix + nSuffix;
+    zCsr += nSuffix;
+
+    /* Compare the term we are searching for with the term just loaded from
+    ** the interior node. If the specified term is greater than or equal
+    ** to the term from the interior node, then all terms on the sub-tree 
+    ** headed by node iChild are smaller than zTerm. No need to search 
+    ** iChild.
+    **
+    ** If the interior node term is larger than the specified term, then
+    ** the tree headed by iChild may contain the specified term.
+    */
+    cmp = memcmp(zTerm, zBuffer, (nBuffer>nTerm ? nTerm : nBuffer));
+    if( piFirst && (cmp<0 || (cmp==0 && nBuffer>nTerm)) ){
+      *piFirst = iChild;
+      piFirst = 0;
+    }
+
+    if( piLast && cmp<0 ){
+      *piLast = iChild;
+      piLast = 0;
+    }
+
+    iChild++;
+  };
+
+  if( piFirst ) *piFirst = iChild;
+  if( piLast ) *piLast = iChild;
+
+ finish_scan:
+  sqlite3_free(zBuffer);
+  return rc;
+}
+
+
+/*
+** The buffer pointed to by argument zNode (size nNode bytes) contains an
+** interior node of a b-tree segment. The zTerm buffer (size nTerm bytes)
+** contains a term. This function searches the sub-tree headed by the zNode
+** node for the range of leaf nodes that may contain the specified term
+** or terms for which the specified term is a prefix.
+**
+** If piLeaf is not NULL, then *piLeaf is set to the blockid of the 
+** left-most leaf node in the tree that may contain the specified term.
+** If piLeaf2 is not NULL, then *piLeaf2 is set to the blockid of the
+** right-most leaf node that may contain a term for which the specified
+** term is a prefix.
+**
+** It is possible that the range of returned leaf nodes does not contain 
+** the specified term or any terms for which it is a prefix. However, if the 
+** segment does contain any such terms, they are stored within the identified
+** range. Because this function only inspects interior segment nodes (and
+** never loads leaf nodes into memory), it is not possible to be sure.
+**
+** If an error occurs, an error code other than SQLITE_OK is returned.
+*/ 
+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 iHeight;                    /* Height of this node in tree */
+
+  assert( piLeaf || piLeaf2 );
+
+  sqlite3Fts3GetVarint32(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 */
+
+    if( piLeaf && piLeaf2 && (*piLeaf!=*piLeaf2) ){
+      rc = sqlite3Fts3ReadBlock(p, *piLeaf, &zBlob, &nBlob);
+      if( rc==SQLITE_OK ){
+        rc = fts3SelectLeaf(p, zTerm, nTerm, zBlob, nBlob, piLeaf, 0);
+      }
+      sqlite3_free(zBlob);
+      piLeaf = 0;
+      zBlob = 0;
+    }
+
+    if( rc==SQLITE_OK ){
+      rc = sqlite3Fts3ReadBlock(p, piLeaf ? *piLeaf : *piLeaf2, &zBlob, &nBlob);
+    }
+    if( rc==SQLITE_OK ){
+      rc = fts3SelectLeaf(p, zTerm, nTerm, zBlob, nBlob, piLeaf, piLeaf2);
+    }
+    sqlite3_free(zBlob);
+  }
+
+  return rc;
+}
+
+/*
+** This function is used to create delta-encoded serialized lists of FTS3 
+** varints. Each call to this function appends a single varint to a list.
+*/
+static void fts3PutDeltaVarint(
+  char **pp,                      /* IN/OUT: Output pointer */
+  sqlite3_int64 *piPrev,          /* IN/OUT: Previous value written to list */
+  sqlite3_int64 iVal              /* Write this value to the list */
+){
+  assert( iVal-*piPrev > 0 || (*piPrev==0 && iVal==0) );
+  *pp += sqlite3Fts3PutVarint(*pp, iVal-*piPrev);
+  *piPrev = iVal;
+}
+
+/*
+** When this function is called, *ppPoslist is assumed to point to the 
+** start of a position-list. After it returns, *ppPoslist points to the
+** first byte after the position-list.
+**
+** A position list is list of positions (delta encoded) and columns for 
+** a single document record of a doclist.  So, in other words, this
+** routine advances *ppPoslist so that it points to the next docid in
+** the doclist, or to the first byte past the end of the doclist.
+**
+** If pp is not NULL, then the contents of the position list are copied
+** to *pp. *pp is set to point to the first byte past the last byte copied
+** before this function returns.
+*/
+static void fts3PoslistCopy(char **pp, char **ppPoslist){
+  char *pEnd = *ppPoslist;
+  char c = 0;
+
+  /* The end of a position list is marked by a zero encoded as an FTS3 
+  ** varint. A single POS_END (0) byte. Except, if the 0 byte is preceded by
+  ** a byte with the 0x80 bit set, then it is not a varint 0, but the tail
+  ** of some other, multi-byte, value.
+  **
+  ** The following while-loop moves pEnd to point to the first byte that is not 
+  ** immediately preceded by a byte with the 0x80 bit set. Then increments
+  ** pEnd once more so that it points to the byte immediately following the
+  ** last byte in the position-list.
+  */
+  while( *pEnd | c ){
+    c = *pEnd++ & 0x80;
+    testcase( c!=0 && (*pEnd)==0 );
+  }
+  pEnd++;  /* Advance past the POS_END terminator byte */
+
+  if( pp ){
+    int n = (int)(pEnd - *ppPoslist);
+    char *p = *pp;
+    memcpy(p, *ppPoslist, n);
+    p += n;
+    *pp = p;
+  }
+  *ppPoslist = pEnd;
+}
+
+/*
+** When this function is called, *ppPoslist is assumed to point to the 
+** start of a column-list. After it returns, *ppPoslist points to the
+** to the terminator (POS_COLUMN or POS_END) byte of the column-list.
+**
+** A column-list is list of delta-encoded positions for a single column
+** within a single document within a doclist.
+**
+** The column-list is terminated either by a POS_COLUMN varint (1) or
+** a POS_END varint (0).  This routine leaves *ppPoslist pointing to
+** the POS_COLUMN or POS_END that terminates the column-list.
+**
+** If pp is not NULL, then the contents of the column-list are copied
+** to *pp. *pp is set to point to the first byte past the last byte copied
+** before this function returns.  The POS_COLUMN or POS_END terminator
+** is not copied into *pp.
+*/
+static void fts3ColumnlistCopy(char **pp, char **ppPoslist){
+  char *pEnd = *ppPoslist;
+  char c = 0;
+
+  /* A column-list is terminated by either a 0x01 or 0x00 byte that is
+  ** not part of a multi-byte varint.
+  */
+  while( 0xFE & (*pEnd | c) ){
+    c = *pEnd++ & 0x80;
+    testcase( c!=0 && ((*pEnd)&0xfe)==0 );
+  }
+  if( pp ){
+    int n = (int)(pEnd - *ppPoslist);
+    char *p = *pp;
+    memcpy(p, *ppPoslist, n);
+    p += n;
+    *pp = p;
+  }
+  *ppPoslist = pEnd;
+}
+
+/*
+** Value used to signify the end of an position-list. This is safe because
+** it is not possible to have a document with 2^31 terms.
+*/
+#define POSITION_LIST_END 0x7fffffff
+
+/*
+** This function is used to help parse position-lists. When this function is
+** called, *pp may point to the start of the next varint in the position-list
+** being parsed, or it may point to 1 byte past the end of the position-list
+** (in which case **pp will be a terminator bytes POS_END (0) or
+** (1)).
+**
+** If *pp points past the end of the current position-list, set *pi to 
+** POSITION_LIST_END and return. Otherwise, read the next varint from *pp,
+** increment the current value of *pi by the value read, and set *pp to
+** point to the next value before returning.
+**
+** Before calling this routine *pi must be initialized to the value of
+** the previous position, or zero if we are reading the first position
+** in the position-list.  Because positions are delta-encoded, the value
+** of the previous position is needed in order to compute the value of
+** the next position.
+*/
+static void fts3ReadNextPos(
+  char **pp,                    /* IN/OUT: Pointer into position-list buffer */
+  sqlite3_int64 *pi             /* IN/OUT: Value read from position-list */
+){
+  if( (**pp)&0xFE ){
+    fts3GetDeltaVarint(pp, pi);
+    *pi -= 2;
+  }else{
+    *pi = POSITION_LIST_END;
+  }
+}
+
+/*
+** If parameter iCol is not 0, write an POS_COLUMN (1) byte followed by
+** the value of iCol encoded as a varint to *pp.   This will start a new
+** column list.
+**
+** Set *pp to point to the byte just after the last byte written before 
+** returning (do not modify it if iCol==0). Return the total number of bytes
+** written (0 if iCol==0).
+*/
+static int fts3PutColNumber(char **pp, int iCol){
+  int n = 0;                      /* Number of bytes written */
+  if( iCol ){
+    char *p = *pp;                /* Output pointer */
+    n = 1 + sqlite3Fts3PutVarint(&p[1], iCol);
+    *p = 0x01;
+    *pp = &p[n];
+  }
+  return n;
+}
+
+/*
+** Compute the union of two position lists.  The output written
+** into *pp contains all positions of both *pp1 and *pp2 in sorted
+** order and with any duplicates removed.  All pointers are
+** updated appropriately.   The caller is responsible for insuring
+** that there is enough space in *pp to hold the complete output.
+*/
+static void fts3PoslistMerge(
+  char **pp,                      /* Output buffer */
+  char **pp1,                     /* Left input list */
+  char **pp2                      /* Right input list */
+){
+  char *p = *pp;
+  char *p1 = *pp1;
+  char *p2 = *pp2;
+
+  while( *p1 || *p2 ){
+    int iCol1;         /* The current column index in pp1 */
+    int iCol2;         /* The current column index in pp2 */
+
+    if( *p1==POS_COLUMN ) sqlite3Fts3GetVarint32(&p1[1], &iCol1);
+    else if( *p1==POS_END ) iCol1 = POSITION_LIST_END;
+    else iCol1 = 0;
+
+    if( *p2==POS_COLUMN ) sqlite3Fts3GetVarint32(&p2[1], &iCol2);
+    else if( *p2==POS_END ) iCol2 = POSITION_LIST_END;
+    else iCol2 = 0;
+
+    if( iCol1==iCol2 ){
+      sqlite3_int64 i1 = 0;       /* Last position from pp1 */
+      sqlite3_int64 i2 = 0;       /* Last position from pp2 */
+      sqlite3_int64 iPrev = 0;
+      int n = fts3PutColNumber(&p, iCol1);
+      p1 += n;
+      p2 += n;
+
+      /* At this point, both p1 and p2 point to the start of column-lists
+      ** for the same column (the column with index iCol1 and iCol2).
+      ** A column-list is a list of non-negative delta-encoded varints, each 
+      ** incremented by 2 before being stored. Each list is terminated by a
+      ** POS_END (0) or POS_COLUMN (1). The following block merges the two lists
+      ** and writes the results to buffer p. p is left pointing to the byte
+      ** after the list written. No terminator (POS_END or POS_COLUMN) is
+      ** written to the output.
+      */
+      fts3GetDeltaVarint(&p1, &i1);
+      fts3GetDeltaVarint(&p2, &i2);
+      do {
+        fts3PutDeltaVarint(&p, &iPrev, (i1<i2) ? i1 : i2); 
+        iPrev -= 2;
+        if( i1==i2 ){
+          fts3ReadNextPos(&p1, &i1);
+          fts3ReadNextPos(&p2, &i2);
+        }else if( i1<i2 ){
+          fts3ReadNextPos(&p1, &i1);
+        }else{
+          fts3ReadNextPos(&p2, &i2);
+        }
+      }while( i1!=POSITION_LIST_END || i2!=POSITION_LIST_END );
+    }else if( iCol1<iCol2 ){
+      p1 += fts3PutColNumber(&p, iCol1);
+      fts3ColumnlistCopy(&p, &p1);
+    }else{
+      p2 += fts3PutColNumber(&p, iCol2);
+      fts3ColumnlistCopy(&p, &p2);
+    }
+  }
+
+  *p++ = POS_END;
+  *pp = p;
+  *pp1 = p1 + 1;
+  *pp2 = p2 + 1;
+}
+
+/*
+** nToken==1 searches for adjacent positions.
+**
+** This function is used to merge two position lists into one. When it is
+** called, *pp1 and *pp2 must both point to position lists. A position-list is
+** the part of a doclist that follows each document id. For example, if a row
+** contains:
+**
+**     'a b c'|'x y z'|'a b b a'
+**
+** Then the position list for this row for token 'b' would consist of:
+**
+**     0x02 0x01 0x02 0x03 0x03 0x00
+**
+** When this function returns, both *pp1 and *pp2 are left pointing to the
+** byte following the 0x00 terminator of their respective position lists.
+**
+** If isSaveLeft is 0, an entry is added to the output position list for 
+** each position in *pp2 for which there exists one or more positions in
+** *pp1 so that (pos(*pp2)>pos(*pp1) && pos(*pp2)-pos(*pp1)<=nToken). i.e.
+** when the *pp1 token appears before the *pp2 token, but not more than nToken
+** slots before it.
+*/
+static int fts3PoslistPhraseMerge(
+  char **pp,                      /* IN/OUT: Preallocated output buffer */
+  int nToken,                     /* Maximum difference in token positions */
+  int isSaveLeft,                 /* Save the left position */
+  int isExact,                    /* If *pp1 is exactly nTokens before *pp2 */
+  char **pp1,                     /* IN/OUT: Left input list */
+  char **pp2                      /* IN/OUT: Right input list */
+){
+  char *p = (pp ? *pp : 0);
+  char *p1 = *pp1;
+  char *p2 = *pp2;
+  int iCol1 = 0;
+  int iCol2 = 0;
+
+  /* Never set both isSaveLeft and isExact for the same invocation. */
+  assert( isSaveLeft==0 || isExact==0 );
+
+  assert( *p1!=0 && *p2!=0 );
+  if( *p1==POS_COLUMN ){ 
+    p1++;
+    p1 += sqlite3Fts3GetVarint32(p1, &iCol1);
+  }
+  if( *p2==POS_COLUMN ){ 
+    p2++;
+    p2 += sqlite3Fts3GetVarint32(p2, &iCol2);
+  }
+
+  while( 1 ){
+    if( iCol1==iCol2 ){
+      char *pSave = p;
+      sqlite3_int64 iPrev = 0;
+      sqlite3_int64 iPos1 = 0;
+      sqlite3_int64 iPos2 = 0;
+
+      if( pp && iCol1 ){
+        *p++ = POS_COLUMN;
+        p += sqlite3Fts3PutVarint(p, iCol1);
+      }
+
+      assert( *p1!=POS_END && *p1!=POS_COLUMN );
+      assert( *p2!=POS_END && *p2!=POS_COLUMN );
+      fts3GetDeltaVarint(&p1, &iPos1); iPos1 -= 2;
+      fts3GetDeltaVarint(&p2, &iPos2); iPos2 -= 2;
+
+      while( 1 ){
+        if( iPos2==iPos1+nToken 
+         || (isExact==0 && iPos2>iPos1 && iPos2<=iPos1+nToken) 
+        ){
+          sqlite3_int64 iSave;
+          if( !pp ){
+            fts3PoslistCopy(0, &p2);
+            fts3PoslistCopy(0, &p1);
+            *pp1 = p1;
+            *pp2 = p2;
+            return 1;
+          }
+          iSave = isSaveLeft ? iPos1 : iPos2;
+          fts3PutDeltaVarint(&p, &iPrev, iSave+2); iPrev -= 2;
+          pSave = 0;
+        }
+        if( (!isSaveLeft && iPos2<=(iPos1+nToken)) || iPos2<=iPos1 ){
+          if( (*p2&0xFE)==0 ) break;
+          fts3GetDeltaVarint(&p2, &iPos2); iPos2 -= 2;
+        }else{
+          if( (*p1&0xFE)==0 ) break;
+          fts3GetDeltaVarint(&p1, &iPos1); iPos1 -= 2;
+        }
+      }
+
+      if( pSave ){
+        assert( pp && p );
+        p = pSave;
+      }
+
+      fts3ColumnlistCopy(0, &p1);
+      fts3ColumnlistCopy(0, &p2);
+      assert( (*p1&0xFE)==0 && (*p2&0xFE)==0 );
+      if( 0==*p1 || 0==*p2 ) break;
+
+      p1++;
+      p1 += sqlite3Fts3GetVarint32(p1, &iCol1);
+      p2++;
+      p2 += sqlite3Fts3GetVarint32(p2, &iCol2);
+    }
+
+    /* Advance pointer p1 or p2 (whichever corresponds to the smaller of
+    ** iCol1 and iCol2) so that it points to either the 0x00 that marks the
+    ** end of the position list, or the 0x01 that precedes the next 
+    ** column-number in the position list. 
+    */
+    else if( iCol1<iCol2 ){
+      fts3ColumnlistCopy(0, &p1);
+      if( 0==*p1 ) break;
+      p1++;
+      p1 += sqlite3Fts3GetVarint32(p1, &iCol1);
+    }else{
+      fts3ColumnlistCopy(0, &p2);
+      if( 0==*p2 ) break;
+      p2++;
+      p2 += sqlite3Fts3GetVarint32(p2, &iCol2);
+    }
+  }
+
+  fts3PoslistCopy(0, &p2);
+  fts3PoslistCopy(0, &p1);
+  *pp1 = p1;
+  *pp2 = p2;
+  if( !pp || *pp==p ){
+    return 0;
+  }
+  *p++ = 0x00;
+  *pp = p;
+  return 1;
+}
+
+/*
+** Merge two position-lists as required by the NEAR operator.
+*/
+static int fts3PoslistNearMerge(
+  char **pp,                      /* Output buffer */
+  char *aTmp,                     /* Temporary buffer space */
+  int nRight,                     /* Maximum difference in token positions */
+  int nLeft,                      /* Maximum difference in token positions */
+  char **pp1,                     /* IN/OUT: Left input list */
+  char **pp2                      /* IN/OUT: Right input list */
+){
+  char *p1 = *pp1;
+  char *p2 = *pp2;
+
+  if( !pp ){
+    if( fts3PoslistPhraseMerge(0, nRight, 0, 0, pp1, pp2) ) return 1;
+    *pp1 = p1;
+    *pp2 = p2;
+    return fts3PoslistPhraseMerge(0, nLeft, 0, 0, pp2, pp1);
+  }else{
+    char *pTmp1 = aTmp;
+    char *pTmp2;
+    char *aTmp2;
+    int res = 1;
+
+    fts3PoslistPhraseMerge(&pTmp1, nRight, 0, 0, pp1, pp2);
+    aTmp2 = pTmp2 = pTmp1;
+    *pp1 = p1;
+    *pp2 = p2;
+    fts3PoslistPhraseMerge(&pTmp2, nLeft, 1, 0, pp2, pp1);
+    if( pTmp1!=aTmp && pTmp2!=aTmp2 ){
+      fts3PoslistMerge(pp, &aTmp, &aTmp2);
+    }else if( pTmp1!=aTmp ){
+      fts3PoslistCopy(pp, &aTmp);
+    }else if( pTmp2!=aTmp2 ){
+      fts3PoslistCopy(pp, &aTmp2);
+    }else{
+      res = 0;
+    }
+
+    return res;
+  }
+}
+
+/*
+** Values that may be used as the first parameter to fts3DoclistMerge().
+*/
+#define MERGE_NOT        2        /* D + D -> D */
+#define MERGE_AND        3        /* D + D -> D */
+#define MERGE_OR         4        /* D + D -> D */
+#define MERGE_POS_OR     5        /* P + P -> P */
+#define MERGE_PHRASE     6        /* P + P -> D */
+#define MERGE_POS_PHRASE 7        /* P + P -> P */
+#define MERGE_NEAR       8        /* P + P -> D */
+#define MERGE_POS_NEAR   9        /* P + P -> P */
+
+/*
+** Merge the two doclists passed in buffer a1 (size n1 bytes) and a2
+** (size n2 bytes). The output is written to pre-allocated buffer aBuffer,
+** which is guaranteed to be large enough to hold the results. The number
+** of bytes written to aBuffer is stored in *pnBuffer before returning.
+**
+** If successful, SQLITE_OK is returned. Otherwise, if a malloc error
+** occurs while allocating a temporary buffer as part of the merge operation,
+** SQLITE_NOMEM is returned.
+*/
+static int fts3DoclistMerge(
+  int mergetype,                  /* One of the MERGE_XXX constants */
+  int nParam1,                    /* Used by MERGE_NEAR and MERGE_POS_NEAR */
+  int nParam2,                    /* Used by MERGE_NEAR and MERGE_POS_NEAR */
+  char *aBuffer,                  /* Pre-allocated output buffer */
+  int *pnBuffer,                  /* OUT: Bytes written to aBuffer */
+  char *a1,                       /* Buffer containing first doclist */
+  int n1,                         /* Size of buffer a1 */
+  char *a2,                       /* Buffer containing second doclist */
+  int n2,                         /* Size of buffer a2 */
+  int *pnDoc                      /* OUT: Number of docids in output */
+){
+  sqlite3_int64 i1 = 0;
+  sqlite3_int64 i2 = 0;
+  sqlite3_int64 iPrev = 0;
+
+  char *p = aBuffer;
+  char *p1 = a1;
+  char *p2 = a2;
+  char *pEnd1 = &a1[n1];
+  char *pEnd2 = &a2[n2];
+  int nDoc = 0;
+
+  assert( mergetype==MERGE_OR     || mergetype==MERGE_POS_OR 
+       || mergetype==MERGE_AND    || mergetype==MERGE_NOT
+       || mergetype==MERGE_PHRASE || mergetype==MERGE_POS_PHRASE
+       || mergetype==MERGE_NEAR   || mergetype==MERGE_POS_NEAR
+  );
+
+  if( !aBuffer ){
+    *pnBuffer = 0;
+    return SQLITE_NOMEM;
+  }
+
+  /* Read the first docid from each doclist */
+  fts3GetDeltaVarint2(&p1, pEnd1, &i1);
+  fts3GetDeltaVarint2(&p2, pEnd2, &i2);
+
+  switch( mergetype ){
+    case MERGE_OR:
+    case MERGE_POS_OR:
+      while( p1 || p2 ){
+        if( p2 && p1 && i1==i2 ){
+          fts3PutDeltaVarint(&p, &iPrev, i1);
+          if( mergetype==MERGE_POS_OR ) fts3PoslistMerge(&p, &p1, &p2);
+          fts3GetDeltaVarint2(&p1, pEnd1, &i1);
+          fts3GetDeltaVarint2(&p2, pEnd2, &i2);
+        }else if( !p2 || (p1 && i1<i2) ){
+          fts3PutDeltaVarint(&p, &iPrev, i1);
+          if( mergetype==MERGE_POS_OR ) fts3PoslistCopy(&p, &p1);
+          fts3GetDeltaVarint2(&p1, pEnd1, &i1);
+        }else{
+          fts3PutDeltaVarint(&p, &iPrev, i2);
+          if( mergetype==MERGE_POS_OR ) fts3PoslistCopy(&p, &p2);
+          fts3GetDeltaVarint2(&p2, pEnd2, &i2);
+        }
+      }
+      break;
+
+    case MERGE_AND:
+      while( p1 && p2 ){
+        if( i1==i2 ){
+          fts3PutDeltaVarint(&p, &iPrev, i1);
+          fts3GetDeltaVarint2(&p1, pEnd1, &i1);
+          fts3GetDeltaVarint2(&p2, pEnd2, &i2);
+          nDoc++;
+        }else if( i1<i2 ){
+          fts3GetDeltaVarint2(&p1, pEnd1, &i1);
+        }else{
+          fts3GetDeltaVarint2(&p2, pEnd2, &i2);
+        }
+      }
+      break;
+
+    case MERGE_NOT:
+      while( p1 ){
+        if( p2 && i1==i2 ){
+          fts3GetDeltaVarint2(&p1, pEnd1, &i1);
+          fts3GetDeltaVarint2(&p2, pEnd2, &i2);
+        }else if( !p2 || i1<i2 ){
+          fts3PutDeltaVarint(&p, &iPrev, i1);
+          fts3GetDeltaVarint2(&p1, pEnd1, &i1);
+        }else{
+          fts3GetDeltaVarint2(&p2, pEnd2, &i2);
+        }
+      }
+      break;
+
+    case MERGE_POS_PHRASE:
+    case MERGE_PHRASE: {
+      char **ppPos = (mergetype==MERGE_PHRASE ? 0 : &p);
+      while( p1 && p2 ){
+        if( i1==i2 ){
+          char *pSave = p;
+          sqlite3_int64 iPrevSave = iPrev;
+          fts3PutDeltaVarint(&p, &iPrev, i1);
+          if( 0==fts3PoslistPhraseMerge(ppPos, nParam1, 0, 1, &p1, &p2) ){
+            p = pSave;
+            iPrev = iPrevSave;
+          }else{
+            nDoc++;
+          }
+          fts3GetDeltaVarint2(&p1, pEnd1, &i1);
+          fts3GetDeltaVarint2(&p2, pEnd2, &i2);
+        }else if( i1<i2 ){
+          fts3PoslistCopy(0, &p1);
+          fts3GetDeltaVarint2(&p1, pEnd1, &i1);
+        }else{
+          fts3PoslistCopy(0, &p2);
+          fts3GetDeltaVarint2(&p2, pEnd2, &i2);
+        }
+      }
+      break;
+    }
+
+    default: assert( mergetype==MERGE_POS_NEAR || mergetype==MERGE_NEAR ); {
+      char *aTmp = 0;
+      char **ppPos = 0;
+
+      if( mergetype==MERGE_POS_NEAR ){
+        ppPos = &p;
+        aTmp = sqlite3_malloc(2*(n1+n2+1));
+        if( !aTmp ){
+          return SQLITE_NOMEM;
+        }
+      }
+
+      while( p1 && p2 ){
+        if( i1==i2 ){
+          char *pSave = p;
+          sqlite3_int64 iPrevSave = iPrev;
+          fts3PutDeltaVarint(&p, &iPrev, i1);
+
+          if( !fts3PoslistNearMerge(ppPos, aTmp, nParam1, nParam2, &p1, &p2) ){
+            iPrev = iPrevSave;
+            p = pSave;
+          }
+
+          fts3GetDeltaVarint2(&p1, pEnd1, &i1);
+          fts3GetDeltaVarint2(&p2, pEnd2, &i2);
+        }else if( i1<i2 ){
+          fts3PoslistCopy(0, &p1);
+          fts3GetDeltaVarint2(&p1, pEnd1, &i1);
+        }else{
+          fts3PoslistCopy(0, &p2);
+          fts3GetDeltaVarint2(&p2, pEnd2, &i2);
+        }
+      }
+      sqlite3_free(aTmp);
+      break;
+    }
+  }
+
+  if( pnDoc ) *pnDoc = nDoc;
+  *pnBuffer = (int)(p-aBuffer);
+  return SQLITE_OK;
+}
+
+/* 
+** A pointer to an instance of this structure is used as the context 
+** argument to sqlite3Fts3SegReaderIterate()
+*/
+typedef struct TermSelect TermSelect;
+struct TermSelect {
+  int isReqPos;
+  char *aaOutput[16];             /* Malloc'd output buffer */
+  int anOutput[16];               /* Size of output in bytes */
+};
+
+/*
+** Merge all doclists in the TermSelect.aaOutput[] array into a single
+** doclist stored in TermSelect.aaOutput[0]. If successful, delete all
+** other doclists (except the aaOutput[0] one) and return SQLITE_OK.
+**
+** If an OOM error occurs, return SQLITE_NOMEM. In this case it is
+** the responsibility of the caller to free any doclists left in the
+** TermSelect.aaOutput[] array.
+*/
+static int fts3TermSelectMerge(TermSelect *pTS){
+  int mergetype = (pTS->isReqPos ? MERGE_POS_OR : MERGE_OR);
+  char *aOut = 0;
+  int nOut = 0;
+  int i;
+
+  /* Loop through the doclists in the aaOutput[] array. Merge them all
+  ** into a single doclist.
+  */
+  for(i=0; i<SizeofArray(pTS->aaOutput); i++){
+    if( pTS->aaOutput[i] ){
+      if( !aOut ){
+        aOut = pTS->aaOutput[i];
+        nOut = pTS->anOutput[i];
+        pTS->aaOutput[i] = 0;
+      }else{
+        int nNew = nOut + pTS->anOutput[i];
+        char *aNew = sqlite3_malloc(nNew);
+        if( !aNew ){
+          sqlite3_free(aOut);
+          return SQLITE_NOMEM;
+        }
+        fts3DoclistMerge(mergetype, 0, 0,
+            aNew, &nNew, pTS->aaOutput[i], pTS->anOutput[i], aOut, nOut, 0
+        );
+        sqlite3_free(pTS->aaOutput[i]);
+        sqlite3_free(aOut);
+        pTS->aaOutput[i] = 0;
+        aOut = aNew;
+        nOut = nNew;
+      }
+    }
+  }
+
+  pTS->aaOutput[0] = aOut;
+  pTS->anOutput[0] = nOut;
+  return SQLITE_OK;
+}
+
+/*
+** This function is used as the sqlite3Fts3SegReaderIterate() callback when
+** querying the full-text index for a doclist associated with a term or
+** term-prefix.
+*/
+static int fts3TermSelectCb(
+  Fts3Table *p,                   /* Virtual table object */
+  void *pContext,                 /* Pointer to TermSelect structure */
+  char *zTerm,
+  int nTerm,
+  char *aDoclist,
+  int nDoclist
+){
+  TermSelect *pTS = (TermSelect *)pContext;
+
+  UNUSED_PARAMETER(p);
+  UNUSED_PARAMETER(zTerm);
+  UNUSED_PARAMETER(nTerm);
+
+  if( pTS->aaOutput[0]==0 ){
+    /* If this is the first term selected, copy the doclist to the output
+    ** buffer using memcpy(). TODO: Add a way to transfer control of the
+    ** aDoclist buffer from the caller so as to avoid the memcpy().
+    */
+    pTS->aaOutput[0] = sqlite3_malloc(nDoclist);
+    pTS->anOutput[0] = nDoclist;
+    if( pTS->aaOutput[0] ){
+      memcpy(pTS->aaOutput[0], aDoclist, nDoclist);
+    }else{
+      return SQLITE_NOMEM;
+    }
+  }else{
+    int mergetype = (pTS->isReqPos ? MERGE_POS_OR : MERGE_OR);
+    char *aMerge = aDoclist;
+    int nMerge = nDoclist;
+    int iOut;
+
+    for(iOut=0; iOut<SizeofArray(pTS->aaOutput); iOut++){
+      char *aNew;
+      int nNew;
+      if( pTS->aaOutput[iOut]==0 ){
+        assert( iOut>0 );
+        pTS->aaOutput[iOut] = aMerge;
+        pTS->anOutput[iOut] = nMerge;
+        break;
+      }
+
+      nNew = nMerge + pTS->anOutput[iOut];
+      aNew = sqlite3_malloc(nNew);
+      if( !aNew ){
+        if( aMerge!=aDoclist ){
+          sqlite3_free(aMerge);
+        }
+        return SQLITE_NOMEM;
+      }
+      fts3DoclistMerge(mergetype, 0, 0, aNew, &nNew, 
+          pTS->aaOutput[iOut], pTS->anOutput[iOut], aMerge, nMerge, 0
+      );
+
+      if( iOut>0 ) sqlite3_free(aMerge);
+      sqlite3_free(pTS->aaOutput[iOut]);
+      pTS->aaOutput[iOut] = 0;
+
+      aMerge = aNew;
+      nMerge = nNew;
+      if( (iOut+1)==SizeofArray(pTS->aaOutput) ){
+        pTS->aaOutput[iOut] = aMerge;
+        pTS->anOutput[iOut] = nMerge;
+      }
+    }
+  }
+  return SQLITE_OK;
+}
+
+static int fts3DeferredTermSelect(
+  Fts3DeferredToken *pToken,      /* Phrase token */
+  int isTermPos,                  /* True to include positions */
+  int *pnOut,                     /* OUT: Size of list */
+  char **ppOut                    /* OUT: Body of list */
+){
+  char *aSource;
+  int nSource;
+
+  aSource = sqlite3Fts3DeferredDoclist(pToken, &nSource);
+  if( !aSource ){
+    *pnOut = 0;
+    *ppOut = 0;
+  }else if( isTermPos ){
+    *ppOut = sqlite3_malloc(nSource);
+    if( !*ppOut ) return SQLITE_NOMEM;
+    memcpy(*ppOut, aSource, nSource);
+    *pnOut = nSource;
+  }else{
+    sqlite3_int64 docid;
+    *pnOut = sqlite3Fts3GetVarint(aSource, &docid);
+    *ppOut = sqlite3_malloc(*pnOut);
+    if( !*ppOut ) return SQLITE_NOMEM;
+    sqlite3Fts3PutVarint(*ppOut, docid);
+  }
+
+  return SQLITE_OK;
+}
+
+int sqlite3Fts3SegReaderCursor(
+  Fts3Table *p,                   /* FTS3 table handle */
+  int iLevel,                     /* Level of segments to scan */
+  const char *zTerm,              /* Term to query for */
+  int nTerm,                      /* Size of zTerm in bytes */
+  int isPrefix,                   /* True for a prefix search */
+  int isScan,                     /* True to scan from zTerm to EOF */
+  Fts3SegReaderCursor *pCsr       /* Cursor object to populate */
+){
+  int rc = SQLITE_OK;
+  int rc2;
+  int iAge = 0;
+  sqlite3_stmt *pStmt = 0;
+  Fts3SegReader *pPending = 0;
+
+  assert( iLevel==FTS3_SEGCURSOR_ALL 
+      ||  iLevel==FTS3_SEGCURSOR_PENDING 
+      ||  iLevel>=0
+  );
+  assert( FTS3_SEGCURSOR_PENDING<0 );
+  assert( FTS3_SEGCURSOR_ALL<0 );
+  assert( iLevel==FTS3_SEGCURSOR_ALL || (zTerm==0 && isPrefix==1) );
+  assert( isPrefix==0 || isScan==0 );
+
+
+  memset(pCsr, 0, sizeof(Fts3SegReaderCursor));
+
+  /* If iLevel is less than 0, include a seg-reader for the pending-terms. */
+  assert( isScan==0 || fts3HashCount(&p->pendingTerms)==0 );
+  if( iLevel<0 && isScan==0 ){
+    rc = sqlite3Fts3SegReaderPending(p, zTerm, nTerm, isPrefix, &pPending);
+    if( rc==SQLITE_OK && pPending ){
+      int nByte = (sizeof(Fts3SegReader *) * 16);
+      pCsr->apSegment = (Fts3SegReader **)sqlite3_malloc(nByte);
+      if( pCsr->apSegment==0 ){
+        rc = SQLITE_NOMEM;
+      }else{
+        pCsr->apSegment[0] = pPending;
+        pCsr->nSegment = 1;
+        pPending = 0;
+      }
+    }
+  }
+
+  if( iLevel!=FTS3_SEGCURSOR_PENDING ){
+    if( rc==SQLITE_OK ){
+      rc = sqlite3Fts3AllSegdirs(p, iLevel, &pStmt);
+    }
+    while( rc==SQLITE_OK && SQLITE_ROW==(rc = sqlite3_step(pStmt)) ){
+
+      /* Read the values returned by the SELECT into local variables. */
+      sqlite3_int64 iStartBlock = sqlite3_column_int64(pStmt, 1);
+      sqlite3_int64 iLeavesEndBlock = sqlite3_column_int64(pStmt, 2);
+      sqlite3_int64 iEndBlock = sqlite3_column_int64(pStmt, 3);
+      int nRoot = sqlite3_column_bytes(pStmt, 4);
+      char const *zRoot = sqlite3_column_blob(pStmt, 4);
+
+      /* If nSegment is a multiple of 16 the array needs to be extended. */
+      if( (pCsr->nSegment%16)==0 ){
+        Fts3SegReader **apNew;
+        int nByte = (pCsr->nSegment + 16)*sizeof(Fts3SegReader*);
+        apNew = (Fts3SegReader **)sqlite3_realloc(pCsr->apSegment, nByte);
+        if( !apNew ){
+          rc = SQLITE_NOMEM;
+          goto finished;
+        }
+        pCsr->apSegment = apNew;
+      }
+
+      /* If zTerm is not NULL, and this segment is not stored entirely on its
+      ** root node, the range of leaves scanned can be reduced. Do this. */
+      if( iStartBlock && zTerm ){
+        sqlite3_int64 *pi = (isPrefix ? &iLeavesEndBlock : 0);
+        rc = fts3SelectLeaf(p, zTerm, nTerm, zRoot, nRoot, &iStartBlock, pi);
+        if( rc!=SQLITE_OK ) goto finished;
+        if( isPrefix==0 && isScan==0 ) iLeavesEndBlock = iStartBlock;
+      }
+ 
+      rc = sqlite3Fts3SegReaderNew(iAge, iStartBlock, iLeavesEndBlock,
+          iEndBlock, zRoot, nRoot, &pCsr->apSegment[pCsr->nSegment]
+      );
+      if( rc!=SQLITE_OK ) goto finished;
+      pCsr->nSegment++;
+      iAge++;
+    }
+  }
+
+ finished:
+  rc2 = sqlite3_reset(pStmt);
+  if( rc==SQLITE_DONE ) rc = rc2;
+  sqlite3Fts3SegReaderFree(pPending);
+
+  return rc;
+}
+
+
+static int fts3TermSegReaderCursor(
+  Fts3Cursor *pCsr,               /* Virtual table cursor handle */
+  const char *zTerm,              /* Term to query for */
+  int nTerm,                      /* Size of zTerm in bytes */
+  int isPrefix,                   /* True for a prefix search */
+  Fts3SegReaderCursor **ppSegcsr  /* OUT: Allocated seg-reader cursor */
+){
+  Fts3SegReaderCursor *pSegcsr;   /* Object to allocate and return */
+  int rc = SQLITE_NOMEM;          /* Return code */
+
+  pSegcsr = sqlite3_malloc(sizeof(Fts3SegReaderCursor));
+  if( pSegcsr ){
+    Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
+    int i;
+    int nCost = 0;
+    rc = sqlite3Fts3SegReaderCursor(
+        p, FTS3_SEGCURSOR_ALL, zTerm, nTerm, isPrefix, 0, pSegcsr);
+  
+    for(i=0; rc==SQLITE_OK && i<pSegcsr->nSegment; i++){
+      rc = sqlite3Fts3SegReaderCost(pCsr, pSegcsr->apSegment[i], &nCost);
+    }
+    pSegcsr->nCost = nCost;
+  }
+
+  *ppSegcsr = pSegcsr;
+  return rc;
+}
+
+static void fts3SegReaderCursorFree(Fts3SegReaderCursor *pSegcsr){
+  sqlite3Fts3SegReaderFinish(pSegcsr);
+  sqlite3_free(pSegcsr);
+}
+
+/*
+** This function retreives the doclist for the specified term (or term
+** prefix) from the database. 
+**
+** The returned doclist may be in one of two formats, depending on the 
+** value of parameter isReqPos. If isReqPos is zero, then the doclist is
+** a sorted list of delta-compressed docids (a bare doclist). If isReqPos
+** is non-zero, then the returned list is in the same format as is stored 
+** in the database without the found length specifier at the start of on-disk
+** doclists.
+*/
+static int fts3TermSelect(
+  Fts3Table *p,                   /* Virtual table handle */
+  Fts3PhraseToken *pTok,          /* Token to query for */
+  int iColumn,                    /* Column to query (or -ve for all columns) */
+  int isReqPos,                   /* True to include position lists in output */
+  int *pnOut,                     /* OUT: Size of buffer at *ppOut */
+  char **ppOut                    /* OUT: Malloced result buffer */
+){
+  int rc;                         /* Return code */
+  Fts3SegReaderCursor *pSegcsr;   /* Seg-reader cursor for this term */
+  TermSelect tsc;                 /* Context object for fts3TermSelectCb() */
+  Fts3SegFilter filter;           /* Segment term filter configuration */
+
+  pSegcsr = pTok->pSegcsr;
+  memset(&tsc, 0, sizeof(TermSelect));
+  tsc.isReqPos = isReqPos;
+
+  filter.flags = FTS3_SEGMENT_IGNORE_EMPTY 
+        | (pTok->isPrefix ? FTS3_SEGMENT_PREFIX : 0)
+        | (isReqPos ? FTS3_SEGMENT_REQUIRE_POS : 0)
+        | (iColumn<p->nColumn ? FTS3_SEGMENT_COLUMN_FILTER : 0);
+  filter.iCol = iColumn;
+  filter.zTerm = pTok->z;
+  filter.nTerm = pTok->n;
+
+  rc = sqlite3Fts3SegReaderStart(p, pSegcsr, &filter);
+  while( SQLITE_OK==rc
+      && SQLITE_ROW==(rc = sqlite3Fts3SegReaderStep(p, pSegcsr)) 
+  ){
+    rc = fts3TermSelectCb(p, (void *)&tsc, 
+        pSegcsr->zTerm, pSegcsr->nTerm, pSegcsr->aDoclist, pSegcsr->nDoclist
+    );
+  }
+
+  if( rc==SQLITE_OK ){
+    rc = fts3TermSelectMerge(&tsc);
+  }
+  if( rc==SQLITE_OK ){
+    *ppOut = tsc.aaOutput[0];
+    *pnOut = tsc.anOutput[0];
+  }else{
+    int i;
+    for(i=0; i<SizeofArray(tsc.aaOutput); i++){
+      sqlite3_free(tsc.aaOutput[i]);
+    }
+  }
+
+  fts3SegReaderCursorFree(pSegcsr);
+  pTok->pSegcsr = 0;
+  return rc;
+}
+
+/*
+** This function counts the total number of docids in the doclist stored
+** in buffer aList[], size nList bytes.
+**
+** If the isPoslist argument is true, then it is assumed that the doclist
+** contains a position-list following each docid. Otherwise, it is assumed
+** that the doclist is simply a list of docids stored as delta encoded 
+** varints.
+*/
+static int fts3DoclistCountDocids(int isPoslist, char *aList, int nList){
+  int nDoc = 0;                   /* Return value */
+  if( aList ){
+    char *aEnd = &aList[nList];   /* Pointer to one byte after EOF */
+    char *p = aList;              /* Cursor */
+    if( !isPoslist ){
+      /* The number of docids in the list is the same as the number of 
+      ** varints. In FTS3 a varint consists of a single byte with the 0x80 
+      ** bit cleared and zero or more bytes with the 0x80 bit set. So to
+      ** count the varints in the buffer, just count the number of bytes
+      ** with the 0x80 bit clear.  */
+      while( p<aEnd ) nDoc += (((*p++)&0x80)==0);
+    }else{
+      while( p<aEnd ){
+        nDoc++;
+        while( (*p++)&0x80 );     /* Skip docid varint */
+        fts3PoslistCopy(0, &p);   /* Skip over position list */
+      }
+    }
+  }
+
+  return nDoc;
+}
+
+/*
+** Call sqlite3Fts3DeferToken() for each token in the expression pExpr.
+*/
+static int fts3DeferExpression(Fts3Cursor *pCsr, Fts3Expr *pExpr){
+  int rc = SQLITE_OK;
+  if( pExpr ){
+    rc = fts3DeferExpression(pCsr, pExpr->pLeft);
+    if( rc==SQLITE_OK ){
+      rc = fts3DeferExpression(pCsr, pExpr->pRight);
+    }
+    if( pExpr->eType==FTSQUERY_PHRASE ){
+      int iCol = pExpr->pPhrase->iColumn;
+      int i;
+      for(i=0; rc==SQLITE_OK && i<pExpr->pPhrase->nToken; i++){
+        Fts3PhraseToken *pToken = &pExpr->pPhrase->aToken[i];
+        if( pToken->pDeferred==0 ){
+          rc = sqlite3Fts3DeferToken(pCsr, pToken, iCol);
+        }
+      }
+    }
+  }
+  return rc;
+}
+
+/*
+** This function removes the position information from a doclist. When
+** called, buffer aList (size *pnList bytes) contains a doclist that includes
+** position information. This function removes the position information so
+** that aList contains only docids, and adjusts *pnList to reflect the new
+** (possibly reduced) size of the doclist.
+*/
+static void fts3DoclistStripPositions(
+  char *aList,                    /* IN/OUT: Buffer containing doclist */
+  int *pnList                     /* IN/OUT: Size of doclist in bytes */
+){
+  if( aList ){
+    char *aEnd = &aList[*pnList]; /* Pointer to one byte after EOF */
+    char *p = aList;              /* Input cursor */
+    char *pOut = aList;           /* Output cursor */
+  
+    while( p<aEnd ){
+      sqlite3_int64 delta;
+      p += sqlite3Fts3GetVarint(p, &delta);
+      fts3PoslistCopy(0, &p);
+      pOut += sqlite3Fts3PutVarint(pOut, delta);
+    }
+
+    *pnList = (int)(pOut - aList);
+  }
+}
+
+/* 
+** Return a DocList corresponding to the phrase *pPhrase.
+**
+** If this function returns SQLITE_OK, but *pnOut is set to a negative value,
+** then no tokens in the phrase were looked up in the full-text index. This
+** is only possible when this function is called from within xFilter(). The
+** caller should assume that all documents match the phrase. The actual
+** filtering will take place in xNext().
+*/
+static int fts3PhraseSelect(
+  Fts3Cursor *pCsr,               /* Virtual table cursor handle */
+  Fts3Phrase *pPhrase,            /* Phrase to return a doclist for */
+  int isReqPos,                   /* True if output should contain positions */
+  char **paOut,                   /* OUT: Pointer to malloc'd result buffer */
+  int *pnOut                      /* OUT: Size of buffer at *paOut */
+){
+  char *pOut = 0;
+  int nOut = 0;
+  int rc = SQLITE_OK;
+  int ii;
+  int iCol = pPhrase->iColumn;
+  int isTermPos = (pPhrase->nToken>1 || isReqPos);
+  Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
+  int isFirst = 1;
+
+  int iPrevTok = 0;
+  int nDoc = 0;
+
+  /* If this is an xFilter() evaluation, create a segment-reader for each
+  ** phrase token. Or, if this is an xNext() or snippet/offsets/matchinfo
+  ** evaluation, only create segment-readers if there are no Fts3DeferredToken
+  ** objects attached to the phrase-tokens.
+  */
+  for(ii=0; ii<pPhrase->nToken; ii++){
+    Fts3PhraseToken *pTok = &pPhrase->aToken[ii];
+    if( pTok->pSegcsr==0 ){
+      if( (pCsr->eEvalmode==FTS3_EVAL_FILTER)
+       || (pCsr->eEvalmode==FTS3_EVAL_NEXT && pCsr->pDeferred==0) 
+       || (pCsr->eEvalmode==FTS3_EVAL_MATCHINFO && pTok->bFulltext) 
+      ){
+        rc = fts3TermSegReaderCursor(
+            pCsr, pTok->z, pTok->n, pTok->isPrefix, &pTok->pSegcsr
+        );
+        if( rc!=SQLITE_OK ) return rc;
+      }
+    }
+  }
+
+  for(ii=0; ii<pPhrase->nToken; ii++){
+    Fts3PhraseToken *pTok;        /* Token to find doclist for */
+    int iTok = 0;                 /* The token being queried this iteration */
+    char *pList = 0;              /* Pointer to token doclist */
+    int nList = 0;                /* Size of buffer at pList */
+
+    /* Select a token to process. If this is an xFilter() call, then tokens 
+    ** are processed in order from least to most costly. Otherwise, tokens 
+    ** are processed in the order in which they occur in the phrase.
+    */
+    if( pCsr->eEvalmode==FTS3_EVAL_MATCHINFO ){
+      assert( isReqPos );
+      iTok = ii;
+      pTok = &pPhrase->aToken[iTok];
+      if( pTok->bFulltext==0 ) continue;
+    }else if( pCsr->eEvalmode==FTS3_EVAL_NEXT || isReqPos ){
+      iTok = ii;
+      pTok = &pPhrase->aToken[iTok];
+    }else{
+      int nMinCost = 0x7FFFFFFF;
+      int jj;
+
+      /* Find the remaining token with the lowest cost. */
+      for(jj=0; jj<pPhrase->nToken; jj++){
+        Fts3SegReaderCursor *pSegcsr = pPhrase->aToken[jj].pSegcsr;
+        if( pSegcsr && pSegcsr->nCost<nMinCost ){
+          iTok = jj;
+          nMinCost = pSegcsr->nCost;
+        }
+      }
+      pTok = &pPhrase->aToken[iTok];
+
+      /* This branch is taken if it is determined that loading the doclist
+      ** for the next token would require more IO than loading all documents
+      ** currently identified by doclist pOut/nOut. No further doclists will
+      ** be loaded from the full-text index for this phrase.
+      */
+      if( nMinCost>nDoc && ii>0 ){
+        rc = fts3DeferExpression(pCsr, pCsr->pExpr);
+        break;
+      }
+    }
+
+    if( pCsr->eEvalmode==FTS3_EVAL_NEXT && pTok->pDeferred ){
+      rc = fts3DeferredTermSelect(pTok->pDeferred, isTermPos, &nList, &pList);
+    }else{
+      if( pTok->pSegcsr ){
+        rc = fts3TermSelect(p, pTok, iCol, isTermPos, &nList, &pList);
+      }
+      pTok->bFulltext = 1;
+    }
+    assert( rc!=SQLITE_OK || pCsr->eEvalmode || pTok->pSegcsr==0 );
+    if( rc!=SQLITE_OK ) break;
+
+    if( isFirst ){
+      pOut = pList;
+      nOut = nList;
+      if( pCsr->eEvalmode==FTS3_EVAL_FILTER && pPhrase->nToken>1 ){
+        nDoc = fts3DoclistCountDocids(1, pOut, nOut);
+      }
+      isFirst = 0;
+      iPrevTok = iTok;
+    }else{
+      /* Merge the new term list and the current output. */
+      char *aLeft, *aRight;
+      int nLeft, nRight;
+      int nDist;
+      int mt;
+
+      /* If this is the final token of the phrase, and positions were not
+      ** requested by the caller, use MERGE_PHRASE instead of POS_PHRASE.
+      ** This drops the position information from the output list.
+      */
+      mt = MERGE_POS_PHRASE;
+      if( ii==pPhrase->nToken-1 && !isReqPos ) mt = MERGE_PHRASE;
+
+      assert( iPrevTok!=iTok );
+      if( iPrevTok<iTok ){
+        aLeft = pOut;
+        nLeft = nOut;
+        aRight = pList;
+        nRight = nList;
+        nDist = iTok-iPrevTok;
+        iPrevTok = iTok;
+      }else{
+        aRight = pOut;
+        nRight = nOut;
+        aLeft = pList;
+        nLeft = nList;
+        nDist = iPrevTok-iTok;
+      }
+      pOut = aRight;
+      fts3DoclistMerge(
+          mt, nDist, 0, pOut, &nOut, aLeft, nLeft, aRight, nRight, &nDoc
+      );
+      sqlite3_free(aLeft);
+    }
+    assert( nOut==0 || pOut!=0 );
+  }
+
+  if( rc==SQLITE_OK ){
+    if( ii!=pPhrase->nToken ){
+      assert( pCsr->eEvalmode==FTS3_EVAL_FILTER && isReqPos==0 );
+      fts3DoclistStripPositions(pOut, &nOut);
+    }
+    *paOut = pOut;
+    *pnOut = nOut;
+  }else{
+    sqlite3_free(pOut);
+  }
+  return rc;
+}
+
+/*
+** This function merges two doclists according to the requirements of a
+** NEAR operator.
+**
+** Both input doclists must include position information. The output doclist 
+** includes position information if the first argument to this function
+** is MERGE_POS_NEAR, or does not if it is MERGE_NEAR.
+*/
+static int fts3NearMerge(
+  int mergetype,                  /* MERGE_POS_NEAR or MERGE_NEAR */
+  int nNear,                      /* Parameter to NEAR operator */
+  int nTokenLeft,                 /* Number of tokens in LHS phrase arg */
+  char *aLeft,                    /* Doclist for LHS (incl. positions) */
+  int nLeft,                      /* Size of LHS doclist in bytes */
+  int nTokenRight,                /* As nTokenLeft */
+  char *aRight,                   /* As aLeft */
+  int nRight,                     /* As nRight */
+  char **paOut,                   /* OUT: Results of merge (malloced) */
+  int *pnOut                      /* OUT: Sized of output buffer */
+){
+  char *aOut;                     /* Buffer to write output doclist to */
+  int rc;                         /* Return code */
+
+  assert( mergetype==MERGE_POS_NEAR || MERGE_NEAR );
+
+  aOut = sqlite3_malloc(nLeft+nRight+1);
+  if( aOut==0 ){
+    rc = SQLITE_NOMEM;
+  }else{
+    rc = fts3DoclistMerge(mergetype, nNear+nTokenRight, nNear+nTokenLeft, 
+      aOut, pnOut, aLeft, nLeft, aRight, nRight, 0
+    );
+    if( rc!=SQLITE_OK ){
+      sqlite3_free(aOut);
+      aOut = 0;
+    }
+  }
+
+  *paOut = aOut;
+  return rc;
+}
+
+/*
+** This function is used as part of the processing for the snippet() and
+** offsets() functions.
+**
+** Both pLeft and pRight are expression nodes of type FTSQUERY_PHRASE. Both
+** have their respective doclists (including position information) loaded
+** in Fts3Expr.aDoclist/nDoclist. This function removes all entries from
+** each doclist that are not within nNear tokens of a corresponding entry
+** in the other doclist.
+*/
+int sqlite3Fts3ExprNearTrim(Fts3Expr *pLeft, Fts3Expr *pRight, int nNear){
+  int rc;                         /* Return code */
+
+  assert( pLeft->eType==FTSQUERY_PHRASE );
+  assert( pRight->eType==FTSQUERY_PHRASE );
+  assert( pLeft->isLoaded && pRight->isLoaded );
+
+  if( pLeft->aDoclist==0 || pRight->aDoclist==0 ){
+    sqlite3_free(pLeft->aDoclist);
+    sqlite3_free(pRight->aDoclist);
+    pRight->aDoclist = 0;
+    pLeft->aDoclist = 0;
+    rc = SQLITE_OK;
+  }else{
+    char *aOut;                   /* Buffer in which to assemble new doclist */
+    int nOut;                     /* Size of buffer aOut in bytes */
+
+    rc = fts3NearMerge(MERGE_POS_NEAR, nNear, 
+        pLeft->pPhrase->nToken, pLeft->aDoclist, pLeft->nDoclist,
+        pRight->pPhrase->nToken, pRight->aDoclist, pRight->nDoclist,
+        &aOut, &nOut
+    );
+    if( rc!=SQLITE_OK ) return rc;
+    sqlite3_free(pRight->aDoclist);
+    pRight->aDoclist = aOut;
+    pRight->nDoclist = nOut;
+
+    rc = fts3NearMerge(MERGE_POS_NEAR, nNear, 
+        pRight->pPhrase->nToken, pRight->aDoclist, pRight->nDoclist,
+        pLeft->pPhrase->nToken, pLeft->aDoclist, pLeft->nDoclist,
+        &aOut, &nOut
+    );
+    sqlite3_free(pLeft->aDoclist);
+    pLeft->aDoclist = aOut;
+    pLeft->nDoclist = nOut;
+  }
+  return rc;
+}
+
+
+/*
+** Allocate an Fts3SegReaderArray for each token in the expression pExpr. 
+** The allocated objects are stored in the Fts3PhraseToken.pArray member
+** variables of each token structure.
+*/
+static int fts3ExprAllocateSegReaders(
+  Fts3Cursor *pCsr,               /* FTS3 table */
+  Fts3Expr *pExpr,                /* Expression to create seg-readers for */
+  int *pnExpr                     /* OUT: Number of AND'd expressions */
+){
+  int rc = SQLITE_OK;             /* Return code */
+
+  assert( pCsr->eEvalmode==FTS3_EVAL_FILTER );
+  if( pnExpr && pExpr->eType!=FTSQUERY_AND ){
+    (*pnExpr)++;
+    pnExpr = 0;
+  }
+
+  if( pExpr->eType==FTSQUERY_PHRASE ){
+    Fts3Phrase *pPhrase = pExpr->pPhrase;
+    int ii;
+
+    for(ii=0; rc==SQLITE_OK && ii<pPhrase->nToken; ii++){
+      Fts3PhraseToken *pTok = &pPhrase->aToken[ii];
+      if( pTok->pSegcsr==0 ){
+        rc = fts3TermSegReaderCursor(
+            pCsr, pTok->z, pTok->n, pTok->isPrefix, &pTok->pSegcsr
+        );
+      }
+    }
+  }else{ 
+    rc = fts3ExprAllocateSegReaders(pCsr, pExpr->pLeft, pnExpr);
+    if( rc==SQLITE_OK ){
+      rc = fts3ExprAllocateSegReaders(pCsr, pExpr->pRight, pnExpr);
+    }
+  }
+  return rc;
+}
+
+/*
+** Free the Fts3SegReaderArray objects associated with each token in the
+** expression pExpr. In other words, this function frees the resources
+** allocated by fts3ExprAllocateSegReaders().
+*/
+static void fts3ExprFreeSegReaders(Fts3Expr *pExpr){
+  if( pExpr ){
+    Fts3Phrase *pPhrase = pExpr->pPhrase;
+    if( pPhrase ){
+      int kk;
+      for(kk=0; kk<pPhrase->nToken; kk++){
+        fts3SegReaderCursorFree(pPhrase->aToken[kk].pSegcsr);
+        pPhrase->aToken[kk].pSegcsr = 0;
+      }
+    }
+    fts3ExprFreeSegReaders(pExpr->pLeft);
+    fts3ExprFreeSegReaders(pExpr->pRight);
+  }
+}
+
+/*
+** Return the sum of the costs of all tokens in the expression pExpr. This
+** function must be called after Fts3SegReaderArrays have been allocated
+** for all tokens using fts3ExprAllocateSegReaders().
+*/
+static int fts3ExprCost(Fts3Expr *pExpr){
+  int nCost;                      /* Return value */
+  if( pExpr->eType==FTSQUERY_PHRASE ){
+    Fts3Phrase *pPhrase = pExpr->pPhrase;
+    int ii;
+    nCost = 0;
+    for(ii=0; ii<pPhrase->nToken; ii++){
+      Fts3SegReaderCursor *pSegcsr = pPhrase->aToken[ii].pSegcsr;
+      if( pSegcsr ) nCost += pSegcsr->nCost;
+    }
+  }else{
+    nCost = fts3ExprCost(pExpr->pLeft) + fts3ExprCost(pExpr->pRight);
+  }
+  return nCost;
+}
+
+/*
+** The following is a helper function (and type) for fts3EvalExpr(). It
+** must be called after Fts3SegReaders have been allocated for every token
+** in the expression. See the context it is called from in fts3EvalExpr()
+** for further explanation.
+*/
+typedef struct ExprAndCost ExprAndCost;
+struct ExprAndCost {
+  Fts3Expr *pExpr;
+  int nCost;
+};
+static void fts3ExprAssignCosts(
+  Fts3Expr *pExpr,                /* Expression to create seg-readers for */
+  ExprAndCost **ppExprCost        /* OUT: Write to *ppExprCost */
+){
+  if( pExpr->eType==FTSQUERY_AND ){
+    fts3ExprAssignCosts(pExpr->pLeft, ppExprCost);
+    fts3ExprAssignCosts(pExpr->pRight, ppExprCost);
+  }else{
+    (*ppExprCost)->pExpr = pExpr;
+    (*ppExprCost)->nCost = fts3ExprCost(pExpr);
+    (*ppExprCost)++;
+  }
+}
+
+/*
+** Evaluate the full-text expression pExpr against FTS3 table pTab. Store
+** the resulting doclist in *paOut and *pnOut. This routine mallocs for
+** the space needed to store the output. The caller is responsible for
+** freeing the space when it has finished.
+**
+** This function is called in two distinct contexts:
+**
+**   * From within the virtual table xFilter() method. In this case, the
+**     output doclist contains entries for all rows in the table, based on
+**     data read from the full-text index.
+**
+**     In this case, if the query expression contains one or more tokens that 
+**     are very common, then the returned doclist may contain a superset of 
+**     the documents that actually match the expression.
+**
+**   * From within the virtual table xNext() method. This call is only made
+**     if the call from within xFilter() found that there were very common 
+**     tokens in the query expression and did return a superset of the 
+**     matching documents. In this case the returned doclist contains only
+**     entries that correspond to the current row of the table. Instead of
+**     reading the data for each token from the full-text index, the data is
+**     already available in-memory in the Fts3PhraseToken.pDeferred structures.
+**     See fts3EvalDeferred() for how it gets there.
+**
+** In the first case above, Fts3Cursor.doDeferred==0. In the second (if it is
+** required) Fts3Cursor.doDeferred==1.
+**
+** If the SQLite invokes the snippet(), offsets() or matchinfo() function
+** as part of a SELECT on an FTS3 table, this function is called on each
+** individual phrase expression in the query. If there were very common tokens
+** found in the xFilter() call, then this function is called once for phrase
+** for each row visited, and the returned doclist contains entries for the
+** current row only. Otherwise, if there were no very common tokens, then this
+** function is called once only for each phrase in the query and the returned
+** doclist contains entries for all rows of the table.
+**
+** Fts3Cursor.doDeferred==1 when this function is called on phrases as a
+** result of a snippet(), offsets() or matchinfo() invocation.
+*/
+static int fts3EvalExpr(
+  Fts3Cursor *p,                  /* Virtual table cursor handle */
+  Fts3Expr *pExpr,                /* Parsed fts3 expression */
+  char **paOut,                   /* OUT: Pointer to malloc'd result buffer */
+  int *pnOut,                     /* OUT: Size of buffer at *paOut */
+  int isReqPos                    /* Require positions in output buffer */
+){
+  int rc = SQLITE_OK;             /* Return code */
+
+  /* Zero the output parameters. */
+  *paOut = 0;
+  *pnOut = 0;
+
+  if( pExpr ){
+    assert( pExpr->eType==FTSQUERY_NEAR   || pExpr->eType==FTSQUERY_OR     
+         || pExpr->eType==FTSQUERY_AND    || pExpr->eType==FTSQUERY_NOT
+         || pExpr->eType==FTSQUERY_PHRASE
+    );
+    assert( pExpr->eType==FTSQUERY_PHRASE || isReqPos==0 );
+
+    if( pExpr->eType==FTSQUERY_PHRASE ){
+      rc = fts3PhraseSelect(p, pExpr->pPhrase,
+          isReqPos || (pExpr->pParent && pExpr->pParent->eType==FTSQUERY_NEAR),
+          paOut, pnOut
+      );
+      fts3ExprFreeSegReaders(pExpr);
+    }else if( p->eEvalmode==FTS3_EVAL_FILTER && pExpr->eType==FTSQUERY_AND ){
+      ExprAndCost *aExpr = 0;     /* Array of AND'd expressions and costs */
+      int nExpr = 0;              /* Size of aExpr[] */
+      char *aRet = 0;             /* Doclist to return to caller */
+      int nRet = 0;               /* Length of aRet[] in bytes */
+      int nDoc = 0x7FFFFFFF;
+
+      assert( !isReqPos );
+
+      rc = fts3ExprAllocateSegReaders(p, pExpr, &nExpr);
+      if( rc==SQLITE_OK ){
+        assert( nExpr>1 );
+        aExpr = sqlite3_malloc(sizeof(ExprAndCost) * nExpr);
+        if( !aExpr ) rc = SQLITE_NOMEM;
+      }
+      if( rc==SQLITE_OK ){
+        int ii;                   /* Used to iterate through expressions */
+
+        fts3ExprAssignCosts(pExpr, &aExpr);
+        aExpr -= nExpr;
+        for(ii=0; ii<nExpr; ii++){
+          char *aNew;
+          int nNew;
+          int jj;
+          ExprAndCost *pBest = 0;
+  
+          for(jj=0; jj<nExpr; jj++){
+            ExprAndCost *pCand = &aExpr[jj];
+            if( pCand->pExpr && (pBest==0 || pCand->nCost<pBest->nCost) ){
+              pBest = pCand;
+            }
+          }
+  
+          if( pBest->nCost>nDoc ){
+            rc = fts3DeferExpression(p, p->pExpr);
+            break;
+          }else{
+            rc = fts3EvalExpr(p, pBest->pExpr, &aNew, &nNew, 0);
+            if( rc!=SQLITE_OK ) break;
+            pBest->pExpr = 0;
+            if( ii==0 ){
+              aRet = aNew;
+              nRet = nNew;
+              nDoc = fts3DoclistCountDocids(0, aRet, nRet);
+            }else{
+              fts3DoclistMerge(
+                  MERGE_AND, 0, 0, aRet, &nRet, aRet, nRet, aNew, nNew, &nDoc
+              );
+              sqlite3_free(aNew);
+            }
+          }
+        }
+      }
+
+      if( rc==SQLITE_OK ){
+        *paOut = aRet;
+        *pnOut = nRet;
+      }else{
+        assert( *paOut==0 );
+        sqlite3_free(aRet);
+      }
+      sqlite3_free(aExpr);
+      fts3ExprFreeSegReaders(pExpr);
+
+    }else{
+      char *aLeft;
+      char *aRight;
+      int nLeft;
+      int nRight;
+
+      assert( pExpr->eType==FTSQUERY_NEAR 
+           || pExpr->eType==FTSQUERY_OR
+           || pExpr->eType==FTSQUERY_NOT
+           || (pExpr->eType==FTSQUERY_AND && p->eEvalmode==FTS3_EVAL_NEXT)
+      );
+
+      if( 0==(rc = fts3EvalExpr(p, pExpr->pRight, &aRight, &nRight, isReqPos))
+       && 0==(rc = fts3EvalExpr(p, pExpr->pLeft, &aLeft, &nLeft, isReqPos))
+      ){
+        switch( pExpr->eType ){
+          case FTSQUERY_NEAR: {
+            Fts3Expr *pLeft;
+            Fts3Expr *pRight;
+            int mergetype = MERGE_NEAR;
+            if( pExpr->pParent && pExpr->pParent->eType==FTSQUERY_NEAR ){
+              mergetype = MERGE_POS_NEAR;
+            }
+            pLeft = pExpr->pLeft;
+            while( pLeft->eType==FTSQUERY_NEAR ){ 
+              pLeft=pLeft->pRight;
+            }
+            pRight = pExpr->pRight;
+            assert( pRight->eType==FTSQUERY_PHRASE );
+            assert( pLeft->eType==FTSQUERY_PHRASE );
+
+            rc = fts3NearMerge(mergetype, pExpr->nNear, 
+                pLeft->pPhrase->nToken, aLeft, nLeft,
+                pRight->pPhrase->nToken, aRight, nRight,
+                paOut, pnOut
+            );
+            sqlite3_free(aLeft);
+            break;
+          }
+
+          case FTSQUERY_OR: {
+            /* Allocate a buffer for the output. The maximum size is the
+            ** sum of the sizes of the two input buffers. The +1 term is
+            ** so that a buffer of zero bytes is never allocated - this can
+            ** cause fts3DoclistMerge() to incorrectly return SQLITE_NOMEM.
+            */
+            char *aBuffer = sqlite3_malloc(nRight+nLeft+1);
+            rc = fts3DoclistMerge(MERGE_OR, 0, 0, aBuffer, pnOut,
+                aLeft, nLeft, aRight, nRight, 0
+            );
+            *paOut = aBuffer;
+            sqlite3_free(aLeft);
+            break;
+          }
+
+          default: {
+            assert( FTSQUERY_NOT==MERGE_NOT && FTSQUERY_AND==MERGE_AND );
+            fts3DoclistMerge(pExpr->eType, 0, 0, aLeft, pnOut,
+                aLeft, nLeft, aRight, nRight, 0
+            );
+            *paOut = aLeft;
+            break;
+          }
+        }
+      }
+      sqlite3_free(aRight);
+    }
+  }
+
+  assert( rc==SQLITE_OK || *paOut==0 );
+  return rc;
+}
+
+/*
+** This function is called from within xNext() for each row visited by
+** an FTS3 query. If evaluating the FTS3 query expression within xFilter()
+** was able to determine the exact set of matching rows, this function sets
+** *pbRes to true and returns SQLITE_IO immediately.
+**
+** Otherwise, if evaluating the query expression within xFilter() returned a
+** superset of the matching documents instead of an exact set (this happens
+** when the query includes very common tokens and it is deemed too expensive to
+** load their doclists from disk), this function tests if the current row
+** really does match the FTS3 query.
+**
+** If an error occurs, an SQLite error code is returned. Otherwise, SQLITE_OK
+** is returned and *pbRes is set to true if the current row matches the
+** FTS3 query (and should be included in the results returned to SQLite), or
+** false otherwise.
+*/
+static int fts3EvalDeferred(
+  Fts3Cursor *pCsr,               /* FTS3 cursor pointing at row to test */
+  int *pbRes                      /* OUT: Set to true if row is a match */
+){
+  int rc = SQLITE_OK;
+  if( pCsr->pDeferred==0 ){
+    *pbRes = 1;
+  }else{
+    rc = fts3CursorSeek(0, pCsr);
+    if( rc==SQLITE_OK ){
+      sqlite3Fts3FreeDeferredDoclists(pCsr);
+      rc = sqlite3Fts3CacheDeferredDoclists(pCsr);
+    }
+    if( rc==SQLITE_OK ){
+      char *a = 0;
+      int n = 0;
+      rc = fts3EvalExpr(pCsr, pCsr->pExpr, &a, &n, 0);
+      assert( n>=0 );
+      *pbRes = (n>0);
+      sqlite3_free(a);
+    }
+  }
+  return rc;
+}
+
+/*
+** Advance the cursor to the next row in the %_content table that
+** matches the search criteria.  For a MATCH search, this will be
+** the next row that matches. For a full-table scan, this will be
+** simply the next row in the %_content table.  For a docid lookup,
+** this routine simply sets the EOF flag.
+**
+** Return SQLITE_OK if nothing goes wrong.  SQLITE_OK is returned
+** even if we reach end-of-file.  The fts3EofMethod() will be called
+** subsequently to determine whether or not an EOF was hit.
+*/
+static int fts3NextMethod(sqlite3_vtab_cursor *pCursor){
+  int res;
+  int rc = SQLITE_OK;             /* Return code */
+  Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;
+
+  pCsr->eEvalmode = FTS3_EVAL_NEXT;
+  do {
+    if( pCsr->aDoclist==0 ){
+      if( SQLITE_ROW!=sqlite3_step(pCsr->pStmt) ){
+        pCsr->isEof = 1;
+        rc = sqlite3_reset(pCsr->pStmt);
+        break;
+      }
+      pCsr->iPrevId = sqlite3_column_int64(pCsr->pStmt, 0);
+    }else{
+      if( pCsr->pNextId>=&pCsr->aDoclist[pCsr->nDoclist] ){
+        pCsr->isEof = 1;
+        break;
+      }
+      sqlite3_reset(pCsr->pStmt);
+      fts3GetDeltaVarint(&pCsr->pNextId, &pCsr->iPrevId);
+      pCsr->isRequireSeek = 1;
+      pCsr->isMatchinfoNeeded = 1;
+    }
+  }while( SQLITE_OK==(rc = fts3EvalDeferred(pCsr, &res)) && res==0 );
+
+  return rc;
+}
+
+/*
+** This is the xFilter interface for the virtual table.  See
+** the virtual table xFilter method documentation for additional
+** information.
+**
+** If idxNum==FTS3_FULLSCAN_SEARCH then do a full table scan against
+** the %_content table.
+**
+** If idxNum==FTS3_DOCID_SEARCH then do a docid lookup for a single entry
+** in the %_content table.
+**
+** If idxNum>=FTS3_FULLTEXT_SEARCH then use the full text index.  The
+** column on the left-hand side of the MATCH operator is column
+** 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 */
+){
+  const char *azSql[] = {
+    "SELECT %s FROM %Q.'%q_content' AS x WHERE docid = ?", /* non-full-scan */
+    "SELECT %s FROM %Q.'%q_content' AS x ",                /* full-scan */
+  };
+  int rc;                         /* Return code */
+  char *zSql;                     /* SQL statement used to access %_content */
+  Fts3Table *p = (Fts3Table *)pCursor->pVtab;
+  Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;
+
+  UNUSED_PARAMETER(idxStr);
+  UNUSED_PARAMETER(nVal);
+
+  assert( idxNum>=0 && idxNum<=(FTS3_FULLTEXT_SEARCH+p->nColumn) );
+  assert( nVal==0 || nVal==1 );
+  assert( (nVal==0)==(idxNum==FTS3_FULLSCAN_SEARCH) );
+  assert( p->pSegments==0 );
+
+  /* In case the cursor has been used before, clear it now. */
+  sqlite3_finalize(pCsr->pStmt);
+  sqlite3_free(pCsr->aDoclist);
+  sqlite3Fts3ExprFree(pCsr->pExpr);
+  memset(&pCursor[1], 0, sizeof(Fts3Cursor)-sizeof(sqlite3_vtab_cursor));
+
+  if( idxNum!=FTS3_DOCID_SEARCH && idxNum!=FTS3_FULLSCAN_SEARCH ){
+    int iCol = idxNum-FTS3_FULLTEXT_SEARCH;
+    const char *zQuery = (const char *)sqlite3_value_text(apVal[0]);
+
+    if( zQuery==0 && sqlite3_value_type(apVal[0])!=SQLITE_NULL ){
+      return SQLITE_NOMEM;
+    }
+
+    rc = sqlite3Fts3ExprParse(p->pTokenizer, p->azColumn, p->nColumn, 
+        iCol, zQuery, -1, &pCsr->pExpr
+    );
+    if( rc!=SQLITE_OK ){
+      if( rc==SQLITE_ERROR ){
+        p->base.zErrMsg = sqlite3_mprintf("malformed MATCH expression: [%s]",
+                                          zQuery);
+      }
+      return rc;
+    }
+
+    rc = sqlite3Fts3ReadLock(p);
+    if( rc!=SQLITE_OK ) return rc;
+
+    rc = fts3EvalExpr(pCsr, pCsr->pExpr, &pCsr->aDoclist, &pCsr->nDoclist, 0);
+    sqlite3Fts3SegmentsClose(p);
+    if( rc!=SQLITE_OK ) return rc;
+    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.
+  */
+  zSql = (char *)azSql[idxNum==FTS3_FULLSCAN_SEARCH];
+  zSql = sqlite3_mprintf(zSql, p->zReadExprlist, p->zDb, p->zName);
+  if( !zSql ){
+    rc = SQLITE_NOMEM;
+  }else{
+    rc = sqlite3_prepare_v2(p->db, zSql, -1, &pCsr->pStmt, 0);
+    sqlite3_free(zSql);
+  }
+  if( rc==SQLITE_OK && idxNum==FTS3_DOCID_SEARCH ){
+    rc = sqlite3_bind_value(pCsr->pStmt, 1, apVal[0]);
+  }
+  pCsr->eSearch = (i16)idxNum;
+
+  if( rc!=SQLITE_OK ) return rc;
+  return fts3NextMethod(pCursor);
+}
+
+/* 
+** This is the xEof method of the virtual table. SQLite calls this 
+** routine to find out if it has reached the end of a result set.
+*/
+static int fts3EofMethod(sqlite3_vtab_cursor *pCursor){
+  return ((Fts3Cursor *)pCursor)->isEof;
+}
+
+/* 
+** This is the xRowid method. The SQLite core calls this routine to
+** retrieve the rowid for the current row of the result set. fts3
+** exposes %_content.docid as the rowid for the virtual table. The
+** rowid should be written to *pRowid.
+*/
+static int fts3RowidMethod(sqlite3_vtab_cursor *pCursor, sqlite_int64 *pRowid){
+  Fts3Cursor *pCsr = (Fts3Cursor *) pCursor;
+  if( pCsr->aDoclist ){
+    *pRowid = pCsr->iPrevId;
+  }else{
+    /* This branch runs if the query is implemented using a full-table scan
+    ** (not using the full-text index). In this case grab the rowid from the
+    ** SELECT statement.
+    */
+    assert( pCsr->isRequireSeek==0 );
+    *pRowid = sqlite3_column_int64(pCsr->pStmt, 0);
+  }
+  return SQLITE_OK;
+}
+
+/* 
+** This is the xColumn method, called by SQLite to request a value from
+** the row that the supplied cursor currently points to.
+*/
+static int fts3ColumnMethod(
+  sqlite3_vtab_cursor *pCursor,   /* Cursor to retrieve value from */
+  sqlite3_context *pContext,      /* Context for sqlite3_result_xxx() calls */
+  int iCol                        /* Index of column to read value from */
+){
+  int rc;                         /* Return Code */
+  Fts3Cursor *pCsr = (Fts3Cursor *) pCursor;
+  Fts3Table *p = (Fts3Table *)pCursor->pVtab;
+
+  /* The column value supplied by SQLite must be in range. */
+  assert( iCol>=0 && iCol<=p->nColumn+1 );
+
+  if( iCol==p->nColumn+1 ){
+    /* This call is a request for the "docid" column. Since "docid" is an 
+    ** alias for "rowid", use the xRowid() method to obtain the value.
+    */
+    sqlite3_int64 iRowid;
+    rc = fts3RowidMethod(pCursor, &iRowid);
+    sqlite3_result_int64(pContext, iRowid);
+  }else if( iCol==p->nColumn ){
+    /* The extra column whose name is the same as the table.
+    ** Return a blob which is a pointer to the cursor.
+    */
+    sqlite3_result_blob(pContext, &pCsr, sizeof(pCsr), SQLITE_TRANSIENT);
+    rc = SQLITE_OK;
+  }else{
+    rc = fts3CursorSeek(0, pCsr);
+    if( rc==SQLITE_OK ){
+      sqlite3_result_value(pContext, sqlite3_column_value(pCsr->pStmt, iCol+1));
+    }
+  }
+  return rc;
+}
+
+/* 
+** This function is the implementation of the xUpdate callback used by 
+** FTS3 virtual tables. It is invoked by SQLite each time a row is to be
+** inserted, updated or deleted.
+*/
+static int fts3UpdateMethod(
+  sqlite3_vtab *pVtab,            /* Virtual table handle */
+  int nArg,                       /* Size of argument array */
+  sqlite3_value **apVal,          /* Array of arguments */
+  sqlite_int64 *pRowid            /* OUT: The affected (or effected) rowid */
+){
+  return sqlite3Fts3UpdateMethod(pVtab, nArg, apVal, pRowid);
+}
+
+/*
+** Implementation of xSync() method. Flush the contents of the pending-terms
+** hash-table to the database.
+*/
+static int fts3SyncMethod(sqlite3_vtab *pVtab){
+  int rc = sqlite3Fts3PendingTermsFlush((Fts3Table *)pVtab);
+  sqlite3Fts3SegmentsClose((Fts3Table *)pVtab);
+  return rc;
+}
+
+/*
+** Implementation of xBegin() method. This is a no-op.
+*/
+static int fts3BeginMethod(sqlite3_vtab *pVtab){
+  UNUSED_PARAMETER(pVtab);
+  assert( ((Fts3Table *)pVtab)->nPendingData==0 );
+  return SQLITE_OK;
+}
+
+/*
+** Implementation of xCommit() method. This is a no-op. The contents of
+** the pending-terms hash-table have already been flushed into the database
+** by fts3SyncMethod().
+*/
+static int fts3CommitMethod(sqlite3_vtab *pVtab){
+  UNUSED_PARAMETER(pVtab);
+  assert( ((Fts3Table *)pVtab)->nPendingData==0 );
+  return SQLITE_OK;
+}
+
+/*
+** Implementation of xRollback(). Discard the contents of the pending-terms
+** hash-table. Any changes made to the database are reverted by SQLite.
+*/
+static int fts3RollbackMethod(sqlite3_vtab *pVtab){
+  sqlite3Fts3PendingTermsClear((Fts3Table *)pVtab);
+  return SQLITE_OK;
+}
+
+/*
+** Load the doclist associated with expression pExpr to pExpr->aDoclist.
+** The loaded doclist contains positions as well as the document ids.
+** This is used by the matchinfo(), snippet() and offsets() auxillary
+** functions.
+*/
+int sqlite3Fts3ExprLoadDoclist(Fts3Cursor *pCsr, Fts3Expr *pExpr){
+  int rc;
+  assert( pExpr->eType==FTSQUERY_PHRASE && pExpr->pPhrase );
+  assert( pCsr->eEvalmode==FTS3_EVAL_NEXT );
+  rc = fts3EvalExpr(pCsr, pExpr, &pExpr->aDoclist, &pExpr->nDoclist, 1);
+  return rc;
+}
+
+int sqlite3Fts3ExprLoadFtDoclist(
+  Fts3Cursor *pCsr, 
+  Fts3Expr *pExpr,
+  char **paDoclist,
+  int *pnDoclist
+){
+  int rc;
+  assert( pCsr->eEvalmode==FTS3_EVAL_NEXT );
+  assert( pExpr->eType==FTSQUERY_PHRASE && pExpr->pPhrase );
+  pCsr->eEvalmode = FTS3_EVAL_MATCHINFO;
+  rc = fts3EvalExpr(pCsr, pExpr, paDoclist, pnDoclist, 1);
+  pCsr->eEvalmode = FTS3_EVAL_NEXT;
+  return rc;
+}
+
+/*
+** After ExprLoadDoclist() (see above) has been called, this function is
+** used to iterate/search through the position lists that make up the doclist
+** stored in pExpr->aDoclist.
+*/
+char *sqlite3Fts3FindPositions(
+  Fts3Expr *pExpr,                /* Access this expressions doclist */
+  sqlite3_int64 iDocid,           /* Docid associated with requested pos-list */
+  int iCol                        /* Column of requested pos-list */
+){
+  assert( pExpr->isLoaded );
+  if( pExpr->aDoclist ){
+    char *pEnd = &pExpr->aDoclist[pExpr->nDoclist];
+    char *pCsr;
+
+    if( pExpr->pCurrent==0 ){
+      pExpr->pCurrent = pExpr->aDoclist;
+      pExpr->iCurrent = 0;
+      pExpr->pCurrent += sqlite3Fts3GetVarint(pExpr->pCurrent,&pExpr->iCurrent);
+    }
+    pCsr = pExpr->pCurrent;
+    assert( pCsr );
+
+    while( pCsr<pEnd ){
+      if( pExpr->iCurrent<iDocid ){
+        fts3PoslistCopy(0, &pCsr);
+        if( pCsr<pEnd ){
+          fts3GetDeltaVarint(&pCsr, &pExpr->iCurrent);
+        }
+        pExpr->pCurrent = pCsr;
+      }else{
+        if( pExpr->iCurrent==iDocid ){
+          int iThis = 0;
+          if( iCol<0 ){
+            /* If iCol is negative, return a pointer to the start of the
+            ** position-list (instead of a pointer to the start of a list
+            ** of offsets associated with a specific column).
+            */
+            return pCsr;
+          }
+          while( iThis<iCol ){
+            fts3ColumnlistCopy(0, &pCsr);
+            if( *pCsr==0x00 ) return 0;
+            pCsr++;
+            pCsr += sqlite3Fts3GetVarint32(pCsr, &iThis);
+          }
+          if( iCol==iThis && (*pCsr&0xFE) ) return pCsr;
+        }
+        return 0;
+      }
+    }
+  }
+
+  return 0;
+}
+
+/*
+** 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 
+** output variable *ppCsr and SQLITE_OK is returned. Otherwise, an error
+** message is written to context pContext and SQLITE_ERROR returned. The
+** string passed via zFunc is used as part of the error message.
+*/
+static int fts3FunctionArg(
+  sqlite3_context *pContext,      /* SQL function call context */
+  const char *zFunc,              /* Function name */
+  sqlite3_value *pVal,            /* argv[0] passed to function */
+  Fts3Cursor **ppCsr              /* OUT: Store cursor handle here */
+){
+  Fts3Cursor *pRet;
+  if( sqlite3_value_type(pVal)!=SQLITE_BLOB 
+   || sqlite3_value_bytes(pVal)!=sizeof(Fts3Cursor *)
+  ){
+    char *zErr = sqlite3_mprintf("illegal first argument to %s", zFunc);
+    sqlite3_result_error(pContext, zErr, -1);
+    sqlite3_free(zErr);
+    return SQLITE_ERROR;
+  }
+  memcpy(&pRet, sqlite3_value_blob(pVal), sizeof(Fts3Cursor *));
+  *ppCsr = pRet;
+  return SQLITE_OK;
+}
+
+/*
+** Implementation of the snippet() function for FTS3
+*/
+static void fts3SnippetFunc(
+  sqlite3_context *pContext,      /* SQLite function call context */
+  int nVal,                       /* Size of apVal[] array */
+  sqlite3_value **apVal           /* Array of arguments */
+){
+  Fts3Cursor *pCsr;               /* Cursor handle passed through apVal[0] */
+  const char *zStart = "<b>";
+  const char *zEnd = "</b>";
+  const char *zEllipsis = "<b>...</b>";
+  int iCol = -1;
+  int nToken = 15;                /* Default number of tokens in snippet */
+
+  /* There must be at least one argument passed to this function (otherwise
+  ** the non-overloaded version would have been called instead of this one).
+  */
+  assert( nVal>=1 );
+
+  if( nVal>6 ){
+    sqlite3_result_error(pContext, 
+        "wrong number of arguments to function snippet()", -1);
+    return;
+  }
+  if( fts3FunctionArg(pContext, "snippet", apVal[0], &pCsr) ) return;
+
+  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( 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 */
+  int nVal,                       /* Size of argument array */
+  sqlite3_value **apVal           /* Array of arguments */
+){
+  Fts3Cursor *pCsr;               /* Cursor handle passed through apVal[0] */
+
+  UNUSED_PARAMETER(nVal);
+
+  assert( nVal==1 );
+  if( fts3FunctionArg(pContext, "offsets", apVal[0], &pCsr) ) return;
+  assert( pCsr );
+  if( SQLITE_OK==fts3CursorSeek(pContext, pCsr) ){
+    sqlite3Fts3Offsets(pContext, pCsr);
+  }
+}
+
+/* 
+** Implementation of the special optimize() function for FTS3. This 
+** function merges all segments in the database to a single segment.
+** Example usage is:
+**
+**   SELECT optimize(t) FROM t LIMIT 1;
+**
+** where 't' is the name of an FTS3 table.
+*/
+static void fts3OptimizeFunc(
+  sqlite3_context *pContext,      /* SQLite function call context */
+  int nVal,                       /* Size of argument array */
+  sqlite3_value **apVal           /* Array of arguments */
+){
+  int rc;                         /* Return code */
+  Fts3Table *p;                   /* Virtual table handle */
+  Fts3Cursor *pCursor;            /* Cursor handle passed through apVal[0] */
+
+  UNUSED_PARAMETER(nVal);
+
+  assert( nVal==1 );
+  if( fts3FunctionArg(pContext, "optimize", apVal[0], &pCursor) ) return;
+  p = (Fts3Table *)pCursor->base.pVtab;
+  assert( p );
+
+  rc = sqlite3Fts3Optimize(p);
+
+  switch( rc ){
+    case SQLITE_OK:
+      sqlite3_result_text(pContext, "Index optimized", -1, SQLITE_STATIC);
+      break;
+    case SQLITE_DONE:
+      sqlite3_result_text(pContext, "Index already optimal", -1, SQLITE_STATIC);
+      break;
+    default:
+      sqlite3_result_error_code(pContext, rc);
+      break;
+  }
+}
+
+/*
+** Implementation of the matchinfo() function for FTS3
+*/
+static void fts3MatchinfoFunc(
+  sqlite3_context *pContext,      /* SQLite function call context */
+  int nVal,                       /* Size of argument array */
+  sqlite3_value **apVal           /* Array of arguments */
+){
+  Fts3Cursor *pCsr;               /* Cursor handle passed through apVal[0] */
+  assert( nVal==1 || nVal==2 );
+  if( SQLITE_OK==fts3FunctionArg(pContext, "matchinfo", apVal[0], &pCsr) ){
+    const char *zArg = 0;
+    if( nVal>1 ){
+      zArg = (const char *)sqlite3_value_text(apVal[1]);
+    }
+    sqlite3Fts3Matchinfo(pContext, pCsr, zArg);
+  }
+}
+
+/*
+** This routine implements the xFindFunction method for the FTS3
+** virtual table.
+*/
+static int fts3FindFunctionMethod(
+  sqlite3_vtab *pVtab,            /* Virtual table handle */
+  int nArg,                       /* Number of SQL function arguments */
+  const char *zName,              /* Name of SQL function */
+  void (**pxFunc)(sqlite3_context*,int,sqlite3_value**), /* OUT: Result */
+  void **ppArg                    /* Unused */
+){
+  struct Overloaded {
+    const char *zName;
+    void (*xFunc)(sqlite3_context*,int,sqlite3_value**);
+  } aOverload[] = {
+    { "snippet", fts3SnippetFunc },
+    { "offsets", fts3OffsetsFunc },
+    { "optimize", fts3OptimizeFunc },
+    { "matchinfo", fts3MatchinfoFunc },
+  };
+  int i;                          /* Iterator variable */
+
+  UNUSED_PARAMETER(pVtab);
+  UNUSED_PARAMETER(nArg);
+  UNUSED_PARAMETER(ppArg);
+
+  for(i=0; i<SizeofArray(aOverload); i++){
+    if( strcmp(zName, aOverload[i].zName)==0 ){
+      *pxFunc = aOverload[i].xFunc;
+      return 1;
+    }
+  }
+
+  /* No function of the specified name was found. Return 0. */
+  return 0;
+}
+
+/*
+** Implementation of FTS3 xRename method. Rename an fts3 table.
+*/
+static int fts3RenameMethod(
+  sqlite3_vtab *pVtab,            /* Virtual table handle */
+  const char *zName               /* New name of table */
+){
+  Fts3Table *p = (Fts3Table *)pVtab;
+  sqlite3 *db = p->db;            /* Database connection */
+  int rc;                         /* Return Code */
+
+  rc = sqlite3Fts3PendingTermsFlush(p);
+  if( rc!=SQLITE_OK ){
+    return rc;
+  }
+
+  fts3DbExec(&rc, db,
+    "ALTER TABLE %Q.'%q_content'  RENAME TO '%q_content';",
+    p->zDb, p->zName, zName
+  );
+  if( p->bHasDocsize ){
+    fts3DbExec(&rc, db,
+      "ALTER TABLE %Q.'%q_docsize'  RENAME TO '%q_docsize';",
+      p->zDb, p->zName, zName
+    );
+  }
+  if( p->bHasStat ){
+    fts3DbExec(&rc, db,
+      "ALTER TABLE %Q.'%q_stat'  RENAME TO '%q_stat';",
+      p->zDb, p->zName, zName
+    );
+  }
+  fts3DbExec(&rc, db,
+    "ALTER TABLE %Q.'%q_segments' RENAME TO '%q_segments';",
+    p->zDb, p->zName, zName
+  );
+  fts3DbExec(&rc, db,
+    "ALTER TABLE %Q.'%q_segdir'   RENAME TO '%q_segdir';",
+    p->zDb, p->zName, zName
+  );
+  return rc;
+}
+
+static const sqlite3_module fts3Module = {
+  /* iVersion      */ 0,
+  /* xCreate       */ fts3CreateMethod,
+  /* xConnect      */ fts3ConnectMethod,
+  /* xBestIndex    */ fts3BestIndexMethod,
+  /* xDisconnect   */ fts3DisconnectMethod,
+  /* xDestroy      */ fts3DestroyMethod,
+  /* xOpen         */ fts3OpenMethod,
+  /* xClose        */ fts3CloseMethod,
+  /* xFilter       */ fts3FilterMethod,
+  /* xNext         */ fts3NextMethod,
+  /* xEof          */ fts3EofMethod,
+  /* xColumn       */ fts3ColumnMethod,
+  /* xRowid        */ fts3RowidMethod,
+  /* xUpdate       */ fts3UpdateMethod,
+  /* xBegin        */ fts3BeginMethod,
+  /* xSync         */ fts3SyncMethod,
+  /* xCommit       */ fts3CommitMethod,
+  /* xRollback     */ fts3RollbackMethod,
+  /* xFindFunction */ fts3FindFunctionMethod,
+  /* xRename */       fts3RenameMethod,
+};
+
+/*
+** This function is registered as the module destructor (called when an
+** FTS3 enabled database connection is closed). It frees the memory
+** allocated for the tokenizer hash table.
+*/
+static void hashDestroy(void *p){
+  Fts3Hash *pHash = (Fts3Hash *)p;
+  sqlite3Fts3HashClear(pHash);
+  sqlite3_free(pHash);
+}
+
+/*
+** The fts3 built-in tokenizers - "simple", "porter" and "icu"- are 
+** implemented in files fts3_tokenizer1.c, fts3_porter.c and fts3_icu.c
+** respectively. The following three forward declarations are for functions
+** declared in these files used to retrieve the respective implementations.
+**
+** Calling sqlite3Fts3SimpleTokenizerModule() sets the value pointed
+** to by the argument to point to the "simple" tokenizer implementation.
+** And so on.
+*/
+void sqlite3Fts3SimpleTokenizerModule(sqlite3_tokenizer_module const**ppModule);
+void sqlite3Fts3PorterTokenizerModule(sqlite3_tokenizer_module const**ppModule);
+#ifdef SQLITE_ENABLE_ICU
+void sqlite3Fts3IcuTokenizerModule(sqlite3_tokenizer_module const**ppModule);
+#endif
+
+/*
+** Initialise the fts3 extension. If this extension is built as part
+** of the sqlite library, then this function is called directly by
+** SQLite. If fts3 is built as a dynamically loadable extension, this
+** function is called by the sqlite3_extension_init() entry point.
+*/
+int sqlite3Fts3Init(sqlite3 *db){
+  int rc = SQLITE_OK;
+  Fts3Hash *pHash = 0;
+  const sqlite3_tokenizer_module *pSimple = 0;
+  const sqlite3_tokenizer_module *pPorter = 0;
+
+#ifdef SQLITE_ENABLE_ICU
+  const sqlite3_tokenizer_module *pIcu = 0;
+  sqlite3Fts3IcuTokenizerModule(&pIcu);
+#endif
+
+  rc = sqlite3Fts3InitAux(db);
+  if( rc!=SQLITE_OK ) return rc;
+
+  sqlite3Fts3SimpleTokenizerModule(&pSimple);
+  sqlite3Fts3PorterTokenizerModule(&pPorter);
+
+  /* Allocate and initialise the hash-table used to store tokenizers. */
+  pHash = sqlite3_malloc(sizeof(Fts3Hash));
+  if( !pHash ){
+    rc = SQLITE_NOMEM;
+  }else{
+    sqlite3Fts3HashInit(pHash, FTS3_HASH_STRING, 1);
+  }
+
+  /* Load the built-in tokenizers into the hash table */
+  if( rc==SQLITE_OK ){
+    if( sqlite3Fts3HashInsert(pHash, "simple", 7, (void *)pSimple)
+     || sqlite3Fts3HashInsert(pHash, "porter", 7, (void *)pPorter) 
+#ifdef SQLITE_ENABLE_ICU
+     || (pIcu && sqlite3Fts3HashInsert(pHash, "icu", 4, (void *)pIcu))
+#endif
+    ){
+      rc = SQLITE_NOMEM;
+    }
+  }
+
+#ifdef SQLITE_TEST
+  if( rc==SQLITE_OK ){
+    rc = sqlite3Fts3ExprInitTestInterface(db);
+  }
+#endif
+
+  /* Create the virtual table wrapper around the hash-table and overload 
+  ** the two scalar functions. If this is successful, register the
+  ** module with sqlite.
+  */
+  if( SQLITE_OK==rc 
+   && SQLITE_OK==(rc = sqlite3Fts3InitHashTable(db, pHash, "fts3_tokenizer"))
+   && SQLITE_OK==(rc = sqlite3_overload_function(db, "snippet", -1))
+   && SQLITE_OK==(rc = sqlite3_overload_function(db, "offsets", 1))
+   && SQLITE_OK==(rc = sqlite3_overload_function(db, "matchinfo", 1))
+   && SQLITE_OK==(rc = sqlite3_overload_function(db, "matchinfo", 2))
+   && SQLITE_OK==(rc = sqlite3_overload_function(db, "optimize", 1))
+  ){
+    rc = sqlite3_create_module_v2(
+        db, "fts3", &fts3Module, (void *)pHash, hashDestroy
+    );
+    if( rc==SQLITE_OK ){
+      rc = sqlite3_create_module_v2(
+          db, "fts4", &fts3Module, (void *)pHash, 0
+      );
+    }
+    return rc;
+  }
+
+  /* An error has occurred. Delete the hash table and return the error code. */
+  assert( rc!=SQLITE_OK );
+  if( pHash ){
+    sqlite3Fts3HashClear(pHash);
+    sqlite3_free(pHash);
+  }
+  return rc;
+}
+
+#if !SQLITE_CORE
+int sqlite3_extension_init(
+  sqlite3 *db, 
+  char **pzErrMsg,
+  const sqlite3_api_routines *pApi
+){
+  SQLITE_EXTENSION_INIT2(pApi)
+  return sqlite3Fts3Init(db);
+}
+#endif
+
+#endif