blob: 2b2c3b8d26861eefc1062aa4a9191f9d7aa46b42 [file] [log] [blame]
/*
** 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; (delta from previous doclist)
** 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 delta to next docid (357). It has one position 70
** (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.
*/
#include "fts3Int.h"
#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)
#if defined(SQLITE_ENABLE_FTS3) && !defined(SQLITE_CORE)
# define SQLITE_CORE 1
#endif
#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
typedef struct Fts3HashWrapper Fts3HashWrapper;
struct Fts3HashWrapper {
Fts3Hash hash; /* Hash table */
int nRef; /* Number of pointers to this object */
};
static int fts3EvalNext(Fts3Cursor *pCsr);
static int fts3EvalStart(Fts3Cursor *pCsr);
static int fts3TermSegReaderCursor(
Fts3Cursor *, const char *, int, int, Fts3MultiSegReader **);
/*
** This variable is set to false when running tests for which the on disk
** structures should not be corrupt. Otherwise, true. If it is false, extra
** assert() conditions in the fts3 code are activated - conditions that are
** only true if it is guaranteed that the fts3 database is not corrupt.
*/
#ifdef SQLITE_DEBUG
int sqlite3_fts3_may_be_corrupt = 1;
#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);
}
#define GETVARINT_STEP(v, ptr, shift, mask1, mask2, var, ret) \
v = (v & mask1) | ( (*(const unsigned char*)(ptr++)) << shift ); \
if( (v & mask2)==0 ){ var = v; return ret; }
#define GETVARINT_INIT(v, ptr, shift, mask1, mask2, var, ret) \
v = (*ptr++); \
if( (v & mask2)==0 ){ var = v; return ret; }
int sqlite3Fts3GetVarintU(const char *pBuf, sqlite_uint64 *v){
const unsigned char *p = (const unsigned char*)pBuf;
const unsigned char *pStart = p;
u32 a;
u64 b;
int shift;
GETVARINT_INIT(a, p, 0, 0x00, 0x80, *v, 1);
GETVARINT_STEP(a, p, 7, 0x7F, 0x4000, *v, 2);
GETVARINT_STEP(a, p, 14, 0x3FFF, 0x200000, *v, 3);
GETVARINT_STEP(a, p, 21, 0x1FFFFF, 0x10000000, *v, 4);
b = (a & 0x0FFFFFFF );
for(shift=28; shift<=63; shift+=7){
u64 c = *p++;
b += (c&0x7F) << shift;
if( (c & 0x80)==0 ) break;
}
*v = b;
return (int)(p - pStart);
}
/*
** 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 *pBuf, sqlite_int64 *v){
return sqlite3Fts3GetVarintU(pBuf, (sqlite3_uint64*)v);
}
/*
** Read a 64-bit variable-length integer from memory starting at p[0] and
** not extending past pEnd[-1].
** Return the number of bytes read, or 0 on error.
** The value is stored in *v.
*/
int sqlite3Fts3GetVarintBounded(
const char *pBuf,
const char *pEnd,
sqlite_int64 *v
){
const unsigned char *p = (const unsigned char*)pBuf;
const unsigned char *pStart = p;
const unsigned char *pX = (const unsigned char*)pEnd;
u64 b = 0;
int shift;
for(shift=0; shift<=63; shift+=7){
u64 c = p<pX ? *p : 0;
p++;
b += (c&0x7F) << shift;
if( (c & 0x80)==0 ) break;
}
*v = b;
return (int)(p - pStart);
}
/*
** Similar to sqlite3Fts3GetVarint(), except that the output is truncated to
** a non-negative 32-bit integer before it is returned.
*/
int sqlite3Fts3GetVarint32(const char *p, int *pi){
const unsigned char *ptr = (const unsigned char*)p;
u32 a;
#ifndef fts3GetVarint32
GETVARINT_INIT(a, ptr, 0, 0x00, 0x80, *pi, 1);
#else
a = (*ptr++);
assert( a & 0x80 );
#endif
GETVARINT_STEP(a, ptr, 7, 0x7F, 0x4000, *pi, 2);
GETVARINT_STEP(a, ptr, 14, 0x3FFF, 0x200000, *pi, 3);
GETVARINT_STEP(a, ptr, 21, 0x1FFFFF, 0x10000000, *pi, 4);
a = (a & 0x0FFFFFFF );
*pi = (int)(a | ((u32)(*ptr & 0x07) << 28));
assert( 0==(a & 0x80000000) );
assert( *pi>=0 );
return 5;
}
/*
** 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( 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;
}
/*
** When this function is called, *pp points to the first byte following a
** varint that is part of a doclist (or position-list, or any other list
** of varints). This function moves *pp to point to the start of that varint,
** and sets *pVal by the varint value.
**
** Argument pStart points to the first byte of the doclist that the
** varint is part of.
*/
static void fts3GetReverseVarint(
char **pp,
char *pStart,
sqlite3_int64 *pVal
){
sqlite3_int64 iVal;
char *p;
/* Pointer p now points at the first byte past the varint we are
** interested in. So, unless the doclist is corrupt, the 0x80 bit is
** clear on character p[-1]. */
for(p = (*pp)-2; p>=pStart && *p&0x80; p--);
p++;
*pp = p;
sqlite3Fts3GetVarint(p, &iVal);
*pVal = iVal;
}
/*
** 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 */
sqlite3_finalize(p->pSeekStmt);
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);
sqlite3_free(p->zContentTbl);
sqlite3_free(p->zLanguageid);
/* Invoke the tokenizer destructor to free the tokenizer. */
p->pTokenizer->pModule->xDestroy(p->pTokenizer);
sqlite3_free(p);
return SQLITE_OK;
}
/*
** Write an error message into *pzErr
*/
void sqlite3Fts3ErrMsg(char **pzErr, const char *zFormat, ...){
va_list ap;
sqlite3_free(*pzErr);
va_start(ap, zFormat);
*pzErr = sqlite3_vmprintf(zFormat, ap);
va_end(ap);
}
/*
** Construct one or more SQL statements from the format string given
** and then evaluate those statements. The success code is written
** into *pRc.
**
** If *pRc is initially non-zero then this routine is a no-op.
*/
static void fts3DbExec(
int *pRc, /* Success code */
sqlite3 *db, /* Database in which to run SQL */
const char *zFormat, /* Format string for SQL */
... /* 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){
Fts3Table *p = (Fts3Table *)pVtab;
int rc = SQLITE_OK; /* Return code */
const char *zDb = p->zDb; /* Name of database (e.g. "main", "temp") */
sqlite3 *db = p->db; /* Database handle */
/* Drop the shadow tables */
fts3DbExec(&rc, db,
"DROP TABLE IF EXISTS %Q.'%q_segments';"
"DROP TABLE IF EXISTS %Q.'%q_segdir';"
"DROP TABLE IF EXISTS %Q.'%q_docsize';"
"DROP TABLE IF EXISTS %Q.'%q_stat';"
"%s DROP TABLE IF EXISTS %Q.'%q_content';",
zDb, p->zName,
zDb, p->zName,
zDb, p->zName,
zDb, p->zName,
(p->zContentTbl ? "--" : ""), 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 */
const char *zLanguageid;
zLanguageid = (p->zLanguageid ? p->zLanguageid : "__langid");
sqlite3_vtab_config(p->db, SQLITE_VTAB_CONSTRAINT_SUPPORT, 1);
sqlite3_vtab_config(p->db, SQLITE_VTAB_INNOCUOUS);
/* 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, %Q HIDDEN)",
zCols, p->zName, zLanguageid
);
if( !zCols || !zSql ){
rc = SQLITE_NOMEM;
}else{
rc = sqlite3_declare_vtab(p->db, zSql);
}
sqlite3_free(zSql);
sqlite3_free(zCols);
*pRc = rc;
}
}
/*
** Create the %_stat table if it does not already exist.
*/
void sqlite3Fts3CreateStatTable(int *pRc, Fts3Table *p){
fts3DbExec(pRc, p->db,
"CREATE TABLE IF NOT EXISTS %Q.'%q_stat'"
"(id INTEGER PRIMARY KEY, value BLOB);",
p->zDb, p->zName
);
if( (*pRc)==SQLITE_OK ) p->bHasStat = 1;
}
/*
** 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 */
sqlite3 *db = p->db; /* The database connection */
if( p->zContentTbl==0 ){
const char *zLanguageid = p->zLanguageid;
char *zContentCols; /* Columns of %_content table */
/* 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( zLanguageid && zContentCols ){
zContentCols = sqlite3_mprintf("%z, langid", zContentCols, zLanguageid);
}
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
);
}
assert( p->bHasStat==p->bFts4 );
if( p->bHasStat ){
sqlite3Fts3CreateStatTable(&rc, p);
}
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);
}else if( rc==SQLITE_AUTH ){
p->nPgsz = 1024;
rc = SQLITE_OK;
}
}
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);
va_end(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){
sqlite3_int64 nRet;
char *zRet;
nRet = 2 + (int)strlen(zInput)*2 + 1;
zRet = sqlite3_malloc64(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 and a FROM clause 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') FROM %_content AS x"
**
** 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( p->zContentTbl==0 ){
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]);
}
if( p->zLanguageid ){
fts3Appendf(pRc, &zRet, ", x.%Q", "langid");
}
sqlite3_free(zFree);
}else{
fts3Appendf(pRc, &zRet, "rowid");
for(i=0; i<p->nColumn; i++){
fts3Appendf(pRc, &zRet, ", x.'%q'", p->azColumn[i]);
}
if( p->zLanguageid ){
fts3Appendf(pRc, &zRet, ", x.%Q", p->zLanguageid);
}
}
fts3Appendf(pRc, &zRet, " FROM '%q'.'%q%s' AS x",
p->zDb,
(p->zContentTbl ? p->zContentTbl : p->zName),
(p->zContentTbl ? "" : "_content")
);
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);
}
if( p->zLanguageid ){
fts3Appendf(pRc, &zRet, ", ?");
}
sqlite3_free(zFree);
return zRet;
}
/*
** Buffer z contains a positive integer value encoded as utf-8 text.
** Decode this value and store it in *pnOut, returning the number of bytes
** consumed. If an overflow error occurs return a negative value.
*/
int sqlite3Fts3ReadInt(const char *z, int *pnOut){
u64 iVal = 0;
int i;
for(i=0; z[i]>='0' && z[i]<='9'; i++){
iVal = iVal*10 + (z[i] - '0');
if( iVal>0x7FFFFFFF ) return -1;
}
*pnOut = (int)iVal;
return i;
}
/*
** This function interprets the string at (*pp) as a non-negative integer
** value. It reads the integer and sets *pnOut to the value read, then
** sets *pp to point to the byte immediately following the last byte of
** the integer value.
**
** Only decimal digits ('0'..'9') may be part of an integer value.
**
** If *pp does not being with a decimal digit SQLITE_ERROR is returned and
** the output value undefined. Otherwise SQLITE_OK is returned.
**
** This function is used when parsing the "prefix=" FTS4 parameter.
*/
static int fts3GobbleInt(const char **pp, int *pnOut){
const int MAX_NPREFIX = 10000000;
int nInt = 0; /* Output value */
int nByte;
nByte = sqlite3Fts3ReadInt(*pp, &nInt);
if( nInt>MAX_NPREFIX ){
nInt = 0;
}
if( nByte==0 ){
return SQLITE_ERROR;
}
*pnOut = nInt;
*pp += nByte;
return SQLITE_OK;
}
/*
** This function is called to allocate an array of Fts3Index structures
** representing the indexes maintained by the current FTS table. FTS tables
** always maintain the main "terms" index, but may also maintain one or
** more "prefix" indexes, depending on the value of the "prefix=" parameter
** (if any) specified as part of the CREATE VIRTUAL TABLE statement.
**
** Argument zParam is passed the value of the "prefix=" option if one was
** specified, or NULL otherwise.
**
** If no error occurs, SQLITE_OK is returned and *apIndex set to point to
** the allocated array. *pnIndex is set to the number of elements in the
** array. If an error does occur, an SQLite error code is returned.
**
** Regardless of whether or not an error is returned, it is the responsibility
** of the caller to call sqlite3_free() on the output array to free it.
*/
static int fts3PrefixParameter(
const char *zParam, /* ABC in prefix=ABC parameter to parse */
int *pnIndex, /* OUT: size of *apIndex[] array */
struct Fts3Index **apIndex /* OUT: Array of indexes for this table */
){
struct Fts3Index *aIndex; /* Allocated array */
int nIndex = 1; /* Number of entries in array */
if( zParam && zParam[0] ){
const char *p;
nIndex++;
for(p=zParam; *p; p++){
if( *p==',' ) nIndex++;
}
}
aIndex = sqlite3_malloc64(sizeof(struct Fts3Index) * nIndex);
*apIndex = aIndex;
if( !aIndex ){
return SQLITE_NOMEM;
}
memset(aIndex, 0, sizeof(struct Fts3Index) * nIndex);
if( zParam ){
const char *p = zParam;
int i;
for(i=1; i<nIndex; i++){
int nPrefix = 0;
if( fts3GobbleInt(&p, &nPrefix) ) return SQLITE_ERROR;
assert( nPrefix>=0 );
if( nPrefix==0 ){
nIndex--;
i--;
}else{
aIndex[i].nPrefix = nPrefix;
}
p++;
}
}
*pnIndex = nIndex;
return SQLITE_OK;
}
/*
** This function is called when initializing an FTS4 table that uses the
** content=xxx option. It determines the number of and names of the columns
** of the new FTS4 table.
**
** The third argument passed to this function is the value passed to the
** config=xxx option (i.e. "xxx"). This function queries the database for
** a table of that name. If found, the output variables are populated
** as follows:
**
** *pnCol: Set to the number of columns table xxx has,
**
** *pnStr: Set to the total amount of space required to store a copy
** of each columns name, including the nul-terminator.
**
** *pazCol: Set to point to an array of *pnCol strings. Each string is
** the name of the corresponding column in table xxx. The array
** and its contents are allocated using a single allocation. It
** is the responsibility of the caller to free this allocation
** by eventually passing the *pazCol value to sqlite3_free().
**
** If the table cannot be found, an error code is returned and the output
** variables are undefined. Or, if an OOM is encountered, SQLITE_NOMEM is
** returned (and the output variables are undefined).
*/
static int fts3ContentColumns(
sqlite3 *db, /* Database handle */
const char *zDb, /* Name of db (i.e. "main", "temp" etc.) */
const char *zTbl, /* Name of content table */
const char ***pazCol, /* OUT: Malloc'd array of column names */
int *pnCol, /* OUT: Size of array *pazCol */
int *pnStr, /* OUT: Bytes of string content */
char **pzErr /* OUT: error message */
){
int rc = SQLITE_OK; /* Return code */
char *zSql; /* "SELECT *" statement on zTbl */
sqlite3_stmt *pStmt = 0; /* Compiled version of zSql */
zSql = sqlite3_mprintf("SELECT * FROM %Q.%Q", zDb, zTbl);
if( !zSql ){
rc = SQLITE_NOMEM;
}else{
rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
if( rc!=SQLITE_OK ){
sqlite3Fts3ErrMsg(pzErr, "%s", sqlite3_errmsg(db));
}
}
sqlite3_free(zSql);
if( rc==SQLITE_OK ){
const char **azCol; /* Output array */
sqlite3_int64 nStr = 0; /* Size of all column names (incl. 0x00) */
int nCol; /* Number of table columns */
int i; /* Used to iterate through columns */
/* Loop through the returned columns. Set nStr to the number of bytes of
** space required to store a copy of each column name, including the
** nul-terminator byte. */
nCol = sqlite3_column_count(pStmt);
for(i=0; i<nCol; i++){
const char *zCol = sqlite3_column_name(pStmt, i);
nStr += strlen(zCol) + 1;
}
/* Allocate and populate the array to return. */
azCol = (const char **)sqlite3_malloc64(sizeof(char *) * nCol + nStr);
if( azCol==0 ){
rc = SQLITE_NOMEM;
}else{
char *p = (char *)&azCol[nCol];
for(i=0; i<nCol; i++){
const char *zCol = sqlite3_column_name(pStmt, i);
int n = (int)strlen(zCol)+1;
memcpy(p, zCol, n);
azCol[i] = p;
p += n;
}
}
sqlite3_finalize(pStmt);
/* Set the output variables. */
*pnCol = nCol;
*pnStr = nStr;
*pazCol = azCol;
}
return rc;
}
/*
** 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 = &((Fts3HashWrapper*)pAux)->hash;
Fts3Table *p = 0; /* Pointer to allocated vtab */
int rc = SQLITE_OK; /* Return code */
int i; /* Iterator variable */
sqlite3_int64 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 */
const char **aCol; /* Array of column names */
sqlite3_tokenizer *pTokenizer = 0; /* Tokenizer for this table */
int nIndex = 0; /* Size of aIndex[] array */
struct Fts3Index *aIndex = 0; /* Array of indexes for this table */
/* The results of parsing supported FTS4 key=value options: */
int bNoDocsize = 0; /* True to omit %_docsize table */
int bDescIdx = 0; /* True to store descending indexes */
char *zPrefix = 0; /* Prefix parameter value (or NULL) */
char *zCompress = 0; /* compress=? parameter (or NULL) */
char *zUncompress = 0; /* uncompress=? parameter (or NULL) */
char *zContent = 0; /* content=? parameter (or NULL) */
char *zLanguageid = 0; /* languageid=? parameter (or NULL) */
char **azNotindexed = 0; /* The set of notindexed= columns */
int nNotindexed = 0; /* Size of azNotindexed[] array */
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;
nByte = sizeof(const char *) * (argc-2);
aCol = (const char **)sqlite3_malloc64(nByte);
if( aCol ){
memset((void*)aCol, 0, nByte);
azNotindexed = (char **)sqlite3_malloc64(nByte);
}
if( azNotindexed ){
memset(azNotindexed, 0, nByte);
}
if( !aCol || !azNotindexed ){
rc = SQLITE_NOMEM;
goto fts3_init_out;
}
/* 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) ){
struct Fts4Option {
const char *zOpt;
int nOpt;
} aFts4Opt[] = {
{ "matchinfo", 9 }, /* 0 -> MATCHINFO */
{ "prefix", 6 }, /* 1 -> PREFIX */
{ "compress", 8 }, /* 2 -> COMPRESS */
{ "uncompress", 10 }, /* 3 -> UNCOMPRESS */
{ "order", 5 }, /* 4 -> ORDER */
{ "content", 7 }, /* 5 -> CONTENT */
{ "languageid", 10 }, /* 6 -> LANGUAGEID */
{ "notindexed", 10 } /* 7 -> NOTINDEXED */
};
int iOpt;
if( !zVal ){
rc = SQLITE_NOMEM;
}else{
for(iOpt=0; iOpt<SizeofArray(aFts4Opt); iOpt++){
struct Fts4Option *pOp = &aFts4Opt[iOpt];
if( nKey==pOp->nOpt && !sqlite3_strnicmp(z, pOp->zOpt, pOp->nOpt) ){
break;
}
}
switch( iOpt ){
case 0: /* MATCHINFO */
if( strlen(zVal)!=4 || sqlite3_strnicmp(zVal, "fts3", 4) ){
sqlite3Fts3ErrMsg(pzErr, "unrecognized matchinfo: %s", zVal);
rc = SQLITE_ERROR;
}
bNoDocsize = 1;
break;
case 1: /* PREFIX */
sqlite3_free(zPrefix);
zPrefix = zVal;
zVal = 0;
break;
case 2: /* COMPRESS */
sqlite3_free(zCompress);
zCompress = zVal;
zVal = 0;
break;
case 3: /* UNCOMPRESS */
sqlite3_free(zUncompress);
zUncompress = zVal;
zVal = 0;
break;
case 4: /* ORDER */
if( (strlen(zVal)!=3 || sqlite3_strnicmp(zVal, "asc", 3))
&& (strlen(zVal)!=4 || sqlite3_strnicmp(zVal, "desc", 4))
){
sqlite3Fts3ErrMsg(pzErr, "unrecognized order: %s", zVal);
rc = SQLITE_ERROR;
}
bDescIdx = (zVal[0]=='d' || zVal[0]=='D');
break;
case 5: /* CONTENT */
sqlite3_free(zContent);
zContent = zVal;
zVal = 0;
break;
case 6: /* LANGUAGEID */
assert( iOpt==6 );
sqlite3_free(zLanguageid);
zLanguageid = zVal;
zVal = 0;
break;
case 7: /* NOTINDEXED */
azNotindexed[nNotindexed++] = zVal;
zVal = 0;
break;
default:
assert( iOpt==SizeofArray(aFts4Opt) );
sqlite3Fts3ErrMsg(pzErr, "unrecognized parameter: %s", z);
rc = SQLITE_ERROR;
break;
}
sqlite3_free(zVal);
}
}
/* Otherwise, the argument is a column name. */
else {
nString += (int)(strlen(z) + 1);
aCol[nCol++] = z;
}
}
/* If a content=xxx option was specified, the following:
**
** 1. Ignore any compress= and uncompress= options.
**
** 2. If no column names were specified as part of the CREATE VIRTUAL
** TABLE statement, use all columns from the content table.
*/
if( rc==SQLITE_OK && zContent ){
sqlite3_free(zCompress);
sqlite3_free(zUncompress);
zCompress = 0;
zUncompress = 0;
if( nCol==0 ){
sqlite3_free((void*)aCol);
aCol = 0;
rc = fts3ContentColumns(db, argv[1], zContent,&aCol,&nCol,&nString,pzErr);
/* If a languageid= option was specified, remove the language id
** column from the aCol[] array. */
if( rc==SQLITE_OK && zLanguageid ){
int j;
for(j=0; j<nCol; j++){
if( sqlite3_stricmp(zLanguageid, aCol[j])==0 ){
int k;
for(k=j; k<nCol; k++) aCol[k] = aCol[k+1];
nCol--;
break;
}
}
}
}
}
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 );
rc = fts3PrefixParameter(zPrefix, &nIndex, &aIndex);
if( rc==SQLITE_ERROR ){
assert( zPrefix );
sqlite3Fts3ErrMsg(pzErr, "error parsing prefix parameter: %s", zPrefix);
}
if( rc!=SQLITE_OK ) goto fts3_init_out;
/* Allocate and populate the Fts3Table structure. */
nByte = sizeof(Fts3Table) + /* Fts3Table */
nCol * sizeof(char *) + /* azColumn */
nIndex * sizeof(struct Fts3Index) + /* aIndex */
nCol * sizeof(u8) + /* abNotindexed */
nName + /* zName */
nDb + /* zDb */
nString; /* Space for azColumn strings */
p = (Fts3Table*)sqlite3_malloc64(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->nMaxPendingData = FTS3_MAX_PENDING_DATA;
p->bHasDocsize = (isFts4 && bNoDocsize==0);
p->bHasStat = (u8)isFts4;
p->bFts4 = (u8)isFts4;
p->bDescIdx = (u8)bDescIdx;
p->nAutoincrmerge = 0xff; /* 0xff means setting unknown */
p->zContentTbl = zContent;
p->zLanguageid = zLanguageid;
zContent = 0;
zLanguageid = 0;
TESTONLY( p->inTransaction = -1 );
TESTONLY( p->mxSavepoint = -1 );
p->aIndex = (struct Fts3Index *)&p->azColumn[nCol];
memcpy(p->aIndex, aIndex, sizeof(struct Fts3Index) * nIndex);
p->nIndex = nIndex;
for(i=0; i<nIndex; i++){
fts3HashInit(&p->aIndex[i].hPending, FTS3_HASH_STRING, 1);
}
p->abNotindexed = (u8 *)&p->aIndex[nIndex];
/* Fill in the zName and zDb fields of the vtab structure. */
zCsr = (char *)&p->abNotindexed[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 = 0;
z = (char *)sqlite3Fts3NextToken(aCol[iCol], &n);
if( n>0 ){
memcpy(zCsr, z, n);
}
zCsr[n] = '\0';
sqlite3Fts3Dequote(zCsr);
p->azColumn[iCol] = zCsr;
zCsr += n+1;
assert( zCsr <= &((char *)p)[nByte] );
}
/* Fill in the abNotindexed array */
for(iCol=0; iCol<nCol; iCol++){
int n = (int)strlen(p->azColumn[iCol]);
for(i=0; i<nNotindexed; i++){
char *zNot = azNotindexed[i];
if( zNot && n==(int)strlen(zNot)
&& 0==sqlite3_strnicmp(p->azColumn[iCol], zNot, n)
){
p->abNotindexed[iCol] = 1;
sqlite3_free(zNot);
azNotindexed[i] = 0;
}
}
}
for(i=0; i<nNotindexed; i++){
if( azNotindexed[i] ){
sqlite3Fts3ErrMsg(pzErr, "no such column: %s", azNotindexed[i]);
rc = SQLITE_ERROR;
}
}
if( rc==SQLITE_OK && (zCompress==0)!=(zUncompress==0) ){
char const *zMiss = (zCompress==0 ? "compress" : "uncompress");
rc = SQLITE_ERROR;
sqlite3Fts3ErrMsg(pzErr, "missing %s parameter in fts4 constructor", zMiss);
}
p->zReadExprlist = fts3ReadExprList(p, zUncompress, &rc);
p->zWriteExprlist = fts3WriteExprList(p, zCompress, &rc);
if( rc!=SQLITE_OK ) goto fts3_init_out;
/* If this is an xCreate call, create the underlying tables in the
** database. TODO: For xConnect(), it could verify that said tables exist.
*/
if( isCreate ){
rc = fts3CreateTables(p);
}
/* Check to see if a legacy fts3 table has been "upgraded" by the
** addition of a %_stat table so that it can use incremental merge.
*/
if( !isFts4 && !isCreate ){
p->bHasStat = 2;
}
/* Figure out the page-size for the database. This is required in order to
** estimate the cost of loading large doclists from the database. */
fts3DatabasePageSize(&rc, p);
p->nNodeSize = p->nPgsz-35;
#if defined(SQLITE_DEBUG)||defined(SQLITE_TEST)
p->nMergeCount = FTS3_MERGE_COUNT;
#endif
/* Declare the table schema to SQLite. */
fts3DeclareVtab(&rc, p);
fts3_init_out:
sqlite3_free(zPrefix);
sqlite3_free(aIndex);
sqlite3_free(zCompress);
sqlite3_free(zUncompress);
sqlite3_free(zContent);
sqlite3_free(zLanguageid);
for(i=0; i<nNotindexed; i++) sqlite3_free(azNotindexed[i]);
sqlite3_free((void *)aCol);
sqlite3_free((void *)azNotindexed);
if( rc!=SQLITE_OK ){
if( p ){
fts3DisconnectMethod((sqlite3_vtab *)p);
}else if( pTokenizer ){
pTokenizer->pModule->xDestroy(pTokenizer);
}
}else{
assert( p->pSegments==0 );
*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);
}
/*
** Set the pIdxInfo->estimatedRows variable to nRow. Unless this
** extension is currently being used by a version of SQLite too old to
** support estimatedRows. In that case this function is a no-op.
*/
static void fts3SetEstimatedRows(sqlite3_index_info *pIdxInfo, i64 nRow){
#if SQLITE_VERSION_NUMBER>=3008002
if( sqlite3_libversion_number()>=3008002 ){
pIdxInfo->estimatedRows = nRow;
}
#endif
}
/*
** Set the SQLITE_INDEX_SCAN_UNIQUE flag in pIdxInfo->flags. Unless this
** extension is currently being used by a version of SQLite too old to
** support index-info flags. In that case this function is a no-op.
*/
static void fts3SetUniqueFlag(sqlite3_index_info *pIdxInfo){
#if SQLITE_VERSION_NUMBER>=3008012
if( sqlite3_libversion_number()>=3008012 ){
pIdxInfo->idxFlags |= SQLITE_INDEX_SCAN_UNIQUE;
}
#endif
}
/*
** Implementation of the xBestIndex method for FTS3 tables. There
** are three possible strategies, in order of preference:
**
** 1. Direct lookup by rowid or docid.
** 2. Full-text search using a MATCH operator on a non-docid column.
** 3. Linear scan of %_content table.
*/
static int fts3BestIndexMethod(sqlite3_vtab *pVTab, sqlite3_index_info *pInfo){
Fts3Table *p = (Fts3Table *)pVTab;
int i; /* Iterator variable */
int iCons = -1; /* Index of constraint to use */
int iLangidCons = -1; /* Index of langid=x constraint, if present */
int iDocidGe = -1; /* Index of docid>=x constraint, if present */
int iDocidLe = -1; /* Index of docid<=x constraint, if present */
int iIdx;
if( p->bLock ){
return SQLITE_ERROR;
}
/* 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 = 5000000;
for(i=0; i<pInfo->nConstraint; i++){
int bDocid; /* True if this constraint is on docid */
struct sqlite3_index_constraint *pCons = &pInfo->aConstraint[i];
if( pCons->usable==0 ){
if( pCons->op==SQLITE_INDEX_CONSTRAINT_MATCH ){
/* There exists an unusable MATCH constraint. This means that if
** the planner does elect to use the results of this call as part
** of the overall query plan the user will see an "unable to use
** function MATCH in the requested context" error. To discourage
** this, return a very high cost here. */
pInfo->idxNum = FTS3_FULLSCAN_SEARCH;
pInfo->estimatedCost = 1e50;
fts3SetEstimatedRows(pInfo, ((sqlite3_int64)1) << 50);
return SQLITE_OK;
}
continue;
}
bDocid = (pCons->iColumn<0 || pCons->iColumn==p->nColumn+1);
/* A direct lookup on the rowid or docid column. Assign a cost of 1.0. */
if( iCons<0 && pCons->op==SQLITE_INDEX_CONSTRAINT_EQ && bDocid ){
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;
}
/* Equality constraint on the langid column */
if( pCons->op==SQLITE_INDEX_CONSTRAINT_EQ
&& pCons->iColumn==p->nColumn + 2
){
iLangidCons = i;
}
if( bDocid ){
switch( pCons->op ){
case SQLITE_INDEX_CONSTRAINT_GE:
case SQLITE_INDEX_CONSTRAINT_GT:
iDocidGe = i;
break;
case SQLITE_INDEX_CONSTRAINT_LE:
case SQLITE_INDEX_CONSTRAINT_LT:
iDocidLe = i;
break;
}
}
}
/* If using a docid=? or rowid=? strategy, set the UNIQUE flag. */
if( pInfo->idxNum==FTS3_DOCID_SEARCH ) fts3SetUniqueFlag(pInfo);
iIdx = 1;
if( iCons>=0 ){
pInfo->aConstraintUsage[iCons].argvIndex = iIdx++;
pInfo->aConstraintUsage[iCons].omit = 1;
}
if( iLangidCons>=0 ){
pInfo->idxNum |= FTS3_HAVE_LANGID;
pInfo->aConstraintUsage[iLangidCons].argvIndex = iIdx++;
}
if( iDocidGe>=0 ){
pInfo->idxNum |= FTS3_HAVE_DOCID_GE;
pInfo->aConstraintUsage[iDocidGe].argvIndex = iIdx++;
}
if( iDocidLe>=0 ){
pInfo->idxNum |= FTS3_HAVE_DOCID_LE;
pInfo->aConstraintUsage[iDocidLe].argvIndex = iIdx++;
}
/* Regardless of the strategy selected, FTS can deliver rows in rowid (or
** docid) order. Both ascending and descending are possible.
*/
if( pInfo->nOrderBy==1 ){
struct sqlite3_index_orderby *pOrder = &pInfo->aOrderBy[0];
if( pOrder->iColumn<0 || pOrder->iColumn==p->nColumn+1 ){
if( pOrder->desc ){
pInfo->idxStr = "DESC";
}else{
pInfo->idxStr = "ASC";
}
pInfo->orderByConsumed = 1;
}
}
assert( p->pSegments==0 );
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;
}
/*
** Finalize the statement handle at pCsr->pStmt.
**
** Or, if that statement handle is one created by fts3CursorSeekStmt(),
** and the Fts3Table.pSeekStmt slot is currently NULL, save the statement
** pointer there instead of finalizing it.
*/
static void fts3CursorFinalizeStmt(Fts3Cursor *pCsr){
if( pCsr->bSeekStmt ){
Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
if( p->pSeekStmt==0 ){
p->pSeekStmt = pCsr->pStmt;
sqlite3_reset(pCsr->pStmt);
pCsr->pStmt = 0;
}
pCsr->bSeekStmt = 0;
}
sqlite3_finalize(pCsr->pStmt);
}
/*
** Free all resources currently held by the cursor passed as the only
** argument.
*/
static void fts3ClearCursor(Fts3Cursor *pCsr){
fts3CursorFinalizeStmt(pCsr);
sqlite3Fts3FreeDeferredTokens(pCsr);
sqlite3_free(pCsr->aDoclist);
sqlite3Fts3MIBufferFree(pCsr->pMIBuffer);
sqlite3Fts3ExprFree(pCsr->pExpr);
memset(&(&pCsr->base)[1], 0, sizeof(Fts3Cursor)-sizeof(sqlite3_vtab_cursor));
}
/*
** 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 );
fts3ClearCursor(pCsr);
assert( ((Fts3Table *)pCsr->base.pVtab)->pSegments==0 );
sqlite3_free(pCsr);
return SQLITE_OK;
}
/*
** If pCsr->pStmt has not been prepared (i.e. if pCsr->pStmt==0), then
** compose and prepare an SQL statement of the form:
**
** "SELECT <columns> FROM %_content WHERE rowid = ?"
**
** (or the equivalent for a content=xxx table) and set pCsr->pStmt to
** it. If an error occurs, return an SQLite error code.
*/
static int fts3CursorSeekStmt(Fts3Cursor *pCsr){
int rc = SQLITE_OK;
if( pCsr->pStmt==0 ){
Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
char *zSql;
if( p->pSeekStmt ){
pCsr->pStmt = p->pSeekStmt;
p->pSeekStmt = 0;
}else{
zSql = sqlite3_mprintf("SELECT %s WHERE rowid = ?", p->zReadExprlist);
if( !zSql ) return SQLITE_NOMEM;
p->bLock++;
rc = sqlite3_prepare_v3(
p->db, zSql,-1,SQLITE_PREPARE_PERSISTENT,&pCsr->pStmt,0
);
p->bLock--;
sqlite3_free(zSql);
}
if( rc==SQLITE_OK ) pCsr->bSeekStmt = 1;
}
return rc;
}
/*
** 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){
int rc = SQLITE_OK;
if( pCsr->isRequireSeek ){
rc = fts3CursorSeekStmt(pCsr);
if( rc==SQLITE_OK ){
Fts3Table *pTab = (Fts3Table*)pCsr->base.pVtab;
pTab->bLock++;
sqlite3_bind_int64(pCsr->pStmt, 1, pCsr->iPrevId);
pCsr->isRequireSeek = 0;
if( SQLITE_ROW==sqlite3_step(pCsr->pStmt) ){
pTab->bLock--;
return SQLITE_OK;
}else{
pTab->bLock--;
rc = sqlite3_reset(pCsr->pStmt);
if( rc==SQLITE_OK && ((Fts3Table *)pCsr->base.pVtab)->zContentTbl==0 ){
/* If no row was found and no error has occurred, then the %_content
** table is missing a row that is present in the full-text index.
** The data structures are corrupt. */
rc = FTS_CORRUPT_VTAB;
pCsr->isEof = 1;
}
}
}
}
if( rc!=SQLITE_OK && pContext ){
sqlite3_result_error_code(pContext, rc);
}
return rc;
}
/*
** 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 */
i64 nAlloc = 0; /* Size of allocated buffer */
int isFirstTerm = 1; /* True when processing first term on page */
u64 iChild; /* Block id of child node to descend to */
int nBuffer = 0; /* Total term size */
/* 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 += sqlite3Fts3GetVarintU(zCsr, &iChild);
zCsr += sqlite3Fts3GetVarintU(zCsr, &iChild);
if( zCsr>zEnd ){
return FTS_CORRUPT_VTAB;
}
while( zCsr<zEnd && (piFirst || piLast) ){
int cmp; /* memcmp() result */
int nSuffix; /* Size of term suffix */
int nPrefix = 0; /* Size of term prefix */
/* Load the next term on the node into zBuffer. Use realloc() to expand
** the size of zBuffer if required. */
if( !isFirstTerm ){
zCsr += fts3GetVarint32(zCsr, &nPrefix);
if( nPrefix>nBuffer ){
rc = FTS_CORRUPT_VTAB;
goto finish_scan;
}
}
isFirstTerm = 0;
zCsr += fts3GetVarint32(zCsr, &nSuffix);
assert( nPrefix>=0 && nSuffix>=0 );
if( nPrefix>zCsr-zNode || nSuffix>zEnd-zCsr || nSuffix==0 ){
rc = FTS_CORRUPT_VTAB;
goto finish_scan;
}
if( (i64)nPrefix+nSuffix>nAlloc ){
char *zNew;
nAlloc = ((i64)nPrefix+nSuffix) * 2;
zNew = (char *)sqlite3_realloc64(zBuffer, nAlloc);
if( !zNew ){
rc = SQLITE_NOMEM;
goto finish_scan;
}
zBuffer = zNew;
}
assert( zBuffer );
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 = (i64)iChild;
piFirst = 0;
}
if( piLast && cmp<0 ){
*piLast = (i64)iChild;
piLast = 0;
}
iChild++;
};
if( piFirst ) *piFirst = (i64)iChild;
if( piLast ) *piLast = (i64)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 = SQLITE_OK; /* Return code */
int iHeight; /* Height of this node in tree */
assert( piLeaf || piLeaf2 );
fts3GetVarint32(zNode, &iHeight);
rc = fts3ScanInteriorNode(zTerm, nTerm, zNode, nNode, piLeaf, piLeaf2);
assert_fts3_nc( !piLeaf2 || !piLeaf || rc!=SQLITE_OK || (*piLeaf<=*piLeaf2) );
if( rc==SQLITE_OK && iHeight>1 ){
char *zBlob = 0; /* Blob read from %_segments table */
int nBlob = 0; /* Size of zBlob in bytes */
if( piLeaf && piLeaf2 && (*piLeaf!=*piLeaf2) ){
rc = sqlite3Fts3ReadBlock(p, *piLeaf, &zBlob, &nBlob, 0);
if( rc==SQLITE_OK ){
rc = fts3SelectLeaf(p, zTerm, nTerm, zBlob, nBlob, piLeaf, 0);
}
sqlite3_free(zBlob);
piLeaf = 0;
zBlob = 0;
}
if( rc==SQLITE_OK ){
rc = sqlite3Fts3ReadBlock(p, piLeaf?*piLeaf:*piLeaf2, &zBlob, &nBlob, 0);
}
if( rc==SQLITE_OK ){
int iNewHeight = 0;
fts3GetVarint32(zBlob, &iNewHeight);
if( iNewHeight>=iHeight ){
rc = FTS_CORRUPT_VTAB;
}else{
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_fts3_nc( 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 must be
** as large or larger than any value that might appear on the
** position-list, even a position list that has been corrupted.
*/
#define POSITION_LIST_END LARGEST_INT64
/*
** 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 ){
int iVal;
*pp += fts3GetVarint32((*pp), &iVal);
*pi += iVal;
*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 int 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 ){
fts3GetVarint32(&p1[1], &iCol1);
if( iCol1==0 ) return FTS_CORRUPT_VTAB;
}
else if( *p1==POS_END ) iCol1 = 0x7fffffff;
else iCol1 = 0;
if( *p2==POS_COLUMN ){
fts3GetVarint32(&p2[1], &iCol2);
if( iCol2==0 ) return FTS_CORRUPT_VTAB;
}
else if( *p2==POS_END ) iCol2 = 0x7fffffff;
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);
if( i1<2 || i2<2 ){
break;
}
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;
return SQLITE_OK;
}
/*
** 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.
**
** e.g. nToken==1 searches for adjacent positions.
*/
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;
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_fts3_nc( p!=0 && *p1!=0 && *p2!=0 );
if( *p1==POS_COLUMN ){
p1++;
p1 += fts3GetVarint32(p1, &iCol1);
/* iCol1==0 indicates corruption. Column 0 does not have a POS_COLUMN
** entry, so this is actually end-of-doclist. */
if( iCol1==0 ) return 0;
}
if( *p2==POS_COLUMN ){
p2++;
p2 += fts3GetVarint32(p2, &iCol2);
/* As above, iCol2==0 indicates corruption. */
if( iCol2==0 ) return 0;
}
while( 1 ){
if( iCol1==iCol2 ){
char *pSave = p;
sqlite3_int64 iPrev = 0;
sqlite3_int64 iPos1 = 0;
sqlite3_int64 iPos2 = 0;
if( iCol1 ){
*p++ = POS_COLUMN;
p += sqlite3Fts3PutVarint(p, iCol1);
}
fts3GetDeltaVarint(&p1, &iPos1); iPos1 -= 2;
fts3GetDeltaVarint(&p2, &iPos2); iPos2 -= 2;
if( iPos1<0 || iPos2<0 ) break;
while( 1 ){
if( iPos2==iPos1+nToken
|| (isExact==0 && iPos2>iPos1 && iPos2<=iPos1+nToken)
){
sqlite3_int64 iSave;
iSave = isSaveLeft ? iPos1 : iPos2;
fts3PutDeltaVarint(&p, &iPrev, iSave+2); iPrev -= 2;
pSave = 0;
assert( p );
}
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 += fts3GetVarint32(p1, &iCol1);
p2++;
p2 += fts3GetVarint32(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 += fts3GetVarint32(p1, &iCol1);
}else{
fts3ColumnlistCopy(0, &p2);
if( 0==*p2 ) break;
p2++;
p2 += fts3GetVarint32(p2, &iCol2);
}
}
fts3PoslistCopy(0, &p2);
fts3PoslistCopy(0, &p1);
*pp1 = p1;
*pp2 = p2;
if( *pp==p ){
return 0;
}
*p++ = 0x00;
*pp = p;
return 1;
}
/*
** Merge two position-lists as required by the NEAR operator. The argument
** position lists correspond to the left and right phrases of an expression
** like:
**
** "phrase 1" NEAR "phrase number 2"
**
** Position list *pp1 corresponds to the left-hand side of the NEAR
** expression and *pp2 to the right. As usual, the indexes in the position
** lists are the offsets of the last token in each phrase (tokens "1" and "2"
** in the example above).
**
** The output position list - written to *pp - is a copy of *pp2 with those
** entries that are not sufficiently NEAR entries in *pp1 removed.
*/
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;
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;
}
/*
** An instance of this function is used to merge together the (potentially
** large number of) doclists for each term that matches a prefix query.
** See function fts3TermSelectMerge() for details.
*/
typedef struct TermSelect TermSelect;
struct TermSelect {
char *aaOutput[16]; /* Malloc'd output buffers */
int anOutput[16]; /* Size each output buffer in bytes */
};
/*
** This function is used to read a single varint from a buffer. Parameter
** pEnd points 1 byte past the end of the buffer. When this function is
** called, if *pp points to pEnd or greater, then the end of the buffer
** has been reached. In this case *pp is set to 0 and the function returns.
**
** If *pp does not point to or past pEnd, then a single varint is read
** from *pp. *pp is then set to point 1 byte past the end of the read varint.
**
** If bDescIdx is false, the value read is added to *pVal before returning.
** If it is true, the value read is subtracted from *pVal before this
** function returns.
*/
static void fts3GetDeltaVarint3(
char **pp, /* IN/OUT: Point to read varint from */
char *pEnd, /* End of buffer */
int bDescIdx, /* True if docids are descending */
sqlite3_int64 *pVal /* IN/OUT: Integer value */
){
if( *pp>=pEnd ){
*pp = 0;
}else{
u64 iVal;
*pp += sqlite3Fts3GetVarintU(*pp, &iVal);
if( bDescIdx ){
*pVal = (i64)((u64)*pVal - iVal);
}else{
*pVal = (i64)((u64)*pVal + iVal);
}
}
}
/*
** This function is used to write a single varint to a buffer. The varint
** is written to *pp. Before returning, *pp is set to point 1 byte past the
** end of the value written.
**
** If *pbFirst is zero when this function is called, the value written to
** the buffer is that of parameter iVal.
**
** If *pbFirst is non-zero when this function is called, then the value
** written is either (iVal-*piPrev) (if bDescIdx is zero) or (*piPrev-iVal)
** (if bDescIdx is non-zero).
**
** Before returning, this function always sets *pbFirst to 1 and *piPrev
** to the value of parameter iVal.
*/
static void fts3PutDeltaVarint3(
char **pp, /* IN/OUT: Output pointer */
int bDescIdx, /* True for descending docids */
sqlite3_int64 *piPrev, /* IN/OUT: Previous value written to list */
int *pbFirst, /* IN/OUT: True after first int written */
sqlite3_int64 iVal /* Write this value to the list */
){
sqlite3_uint64 iWrite;
if( bDescIdx==0 || *pbFirst==0 ){
assert_fts3_nc( *pbFirst==0 || iVal>=*piPrev );
iWrite = (u64)iVal - (u64)*piPrev;
}else{
assert_fts3_nc( *piPrev>=iVal );
iWrite = (u64)*piPrev - (u64)iVal;
}
assert( *pbFirst || *piPrev==0 );
assert_fts3_nc( *pbFirst==0 || iWrite>0 );
*pp += sqlite3Fts3PutVarint(*pp, iWrite);
*piPrev = iVal;
*pbFirst = 1;
}
/*
** This macro is used by various functions that merge doclists. The two
** arguments are 64-bit docid values. If the value of the stack variable
** bDescDoclist is 0 when this macro is invoked, then it returns (i1-i2).
** Otherwise, (i2-i1).
**
** Using this makes it easier to write code that can merge doclists that are
** sorted in either ascending or descending order.
*/
/* #define DOCID_CMP(i1, i2) ((bDescDoclist?-1:1) * (i64)((u64)i1-i2)) */
#define DOCID_CMP(i1, i2) ((bDescDoclist?-1:1) * (i1>i2?1:((i1==i2)?0:-1)))
/*
** This function does an "OR" merge of two doclists (output contains all
** positions contained in either argument doclist). If the docids in the
** input doclists are sorted in ascending order, parameter bDescDoclist
** should be false. If they are sorted in ascending order, it should be
** passed a non-zero value.
**
** If no error occurs, *paOut is set to point at an sqlite3_malloc'd buffer
** containing the output doclist and SQLITE_OK is returned. In this case
** *pnOut is set to the number of bytes in the output doclist.
**
** If an error occurs, an SQLite error code is returned. The output values
** are undefined in this case.
*/
static int fts3DoclistOrMerge(
int bDescDoclist, /* True if arguments are desc */
char *a1, int n1, /* First doclist */
char *a2, int n2, /* Second doclist */
char **paOut, int *pnOut /* OUT: Malloc'd doclist */
){
int rc = SQLITE_OK;
sqlite3_int64 i1 = 0;
sqlite3_int64 i2 = 0;
sqlite3_int64 iPrev = 0;
char *pEnd1 = &a1[n1];
char *pEnd2 = &a2[n2];
char *p1 = a1;
char *p2 = a2;
char *p;
char *aOut;
int bFirstOut = 0;
*paOut = 0;
*pnOut = 0;
/* Allocate space for the output. Both the input and output doclists
** are delta encoded. If they are in ascending order (bDescDoclist==0),
** then the first docid in each list is simply encoded as a varint. For
** each subsequent docid, the varint stored is the difference between the
** current and previous docid (a positive number - since the list is in
** ascending order).
**
** The first docid written to the output is therefore encoded using the
** same number of bytes as it is in whichever of the input lists it is
** read from. And each subsequent docid read from the same input list
** consumes either the same or less bytes as it did in the input (since
** the difference between it and the previous value in the output must
** be a positive value less than or equal to the delta value read from
** the input list). The same argument applies to all but the first docid
** read from the 'other' list. And to the contents of all position lists
** that will be copied and merged from the input to the output.
**
** However, if the first docid copied to the output is a negative number,
** then the encoding of the first docid from the 'other' input list may
** be larger in the output than it was in the input (since the delta value
** may be a larger positive integer than the actual docid).
**
** The space required to store the output is therefore the sum of the
** sizes of the two inputs, plus enough space for exactly one of the input
** docids to grow.
**
** A symetric argument may be made if the doclists are in descending
** order.
*/
aOut = sqlite3_malloc64((i64)n1+n2+FTS3_VARINT_MAX-1+FTS3_BUFFER_PADDING);
if( !aOut ) return SQLITE_NOMEM;
p = aOut;
fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1);
fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2);
while( p1 || p2 ){
sqlite3_int64 iDiff = DOCID_CMP(i1, i2);
if( p2 && p1 && iDiff==0 ){
fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i1);
rc = fts3PoslistMerge(&p, &p1, &p2);
if( rc ) break;
fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);
fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);
}else if( !p2 || (p1 && iDiff<0) ){
fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i1);
fts3PoslistCopy(&p, &p1);
fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);
}else{
fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i2);
fts3PoslistCopy(&p, &p2);
fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);
}
assert( (p-aOut)<=((p1?(p1-a1):n1)+(p2?(p2-a2):n2)+FTS3_VARINT_MAX-1) );
}
if( rc!=SQLITE_OK ){
sqlite3_free(aOut);
p = aOut = 0;
}else{
assert( (p-aOut)<=n1+n2+FTS3_VARINT_MAX-1 );
memset(&aOut[(p-aOut)], 0, FTS3_BUFFER_PADDING);
}
*paOut = aOut;
*pnOut = (int)(p-aOut);
return rc;
}
/*
** This function does a "phrase" merge of two doclists. In a phrase merge,
** the output contains a copy of each position from the right-hand input
** doclist for which there is a position in the left-hand input doclist
** exactly nDist tokens before it.
**
** If the docids in the input doclists are sorted in ascending order,
** parameter bDescDoclist should be false. If they are sorted in ascending
** order, it should be passed a non-zero value.
**
** The right-hand input doclist is overwritten by this function.
*/
static int fts3DoclistPhraseMerge(
int bDescDoclist, /* True if arguments are desc */
int nDist, /* Distance from left to right (1=adjacent) */
char *aLeft, int nLeft, /* Left doclist */
char **paRight, int *pnRight /* IN/OUT: Right/output doclist */
){
sqlite3_int64 i1 = 0;
sqlite3_int64 i2 = 0;
sqlite3_int64 iPrev = 0;
char *aRight = *paRight;
char *pEnd1 = &aLeft[nLeft];
char *pEnd2 = &aRight[*pnRight];
char *p1 = aLeft;
char *p2 = aRight;
char *p;
int bFirstOut = 0;
char *aOut;
assert( nDist>0 );
if( bDescDoclist ){
aOut = sqlite3_malloc64((sqlite3_int64)*pnRight + FTS3_VARINT_MAX);
if( aOut==0 ) return SQLITE_NOMEM;
}else{
aOut = aRight;
}
p = aOut;
fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1);
fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2);
while( p1 && p2 ){
sqlite3_int64 iDiff = DOCID_CMP(i1, i2);
if( iDiff==0 ){
char *pSave = p;
sqlite3_int64 iPrevSave = iPrev;
int bFirstOutSave = bFirstOut;
fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i1);
if( 0==fts3PoslistPhraseMerge(&p, nDist, 0, 1, &p1, &p2) ){
p = pSave;
iPrev = iPrevSave;
bFirstOut = bFirstOutSave;
}
fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);
fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);
}else if( iDiff<0 ){
fts3PoslistCopy(0, &p1);
fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);
}else{
fts3PoslistCopy(0, &p2);
fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);
}
}
*pnRight = (int)(p - aOut);
if( bDescDoclist ){
sqlite3_free(aRight);
*paRight = aOut;
}
return SQLITE_OK;
}
/*
** Argument pList points to a position list nList bytes in size. This
** function checks to see if the position list contains any entries for
** a token in position 0 (of any column). If so, it writes argument iDelta
** to the output buffer pOut, followed by a position list consisting only
** of the entries from pList at position 0, and terminated by an 0x00 byte.
** The value returned is the number of bytes written to pOut (if any).
*/
int sqlite3Fts3FirstFilter(
sqlite3_int64 iDelta, /* Varint that may be written to pOut */
char *pList, /* Position list (no 0x00 term) */
int nList, /* Size of pList in bytes */
char *pOut /* Write output here */
){
int nOut = 0;
int bWritten = 0; /* True once iDelta has been written */
char *p = pList;
char *pEnd = &pList[nList];
if( *p!=0x01 ){
if( *p==0x02 ){
nOut += sqlite3Fts3PutVarint(&pOut[nOut], iDelta);
pOut[nOut++] = 0x02;
bWritten = 1;
}
fts3ColumnlistCopy(0, &p);
}
while( p<pEnd ){
sqlite3_int64 iCol;
p++;
p += sqlite3Fts3GetVarint(p, &iCol);
if( *p==0x02 ){
if( bWritten==0 ){
nOut += sqlite3Fts3PutVarint(&pOut[nOut], iDelta);
bWritten = 1;
}
pOut[nOut++] = 0x01;
nOut += sqlite3Fts3PutVarint(&pOut[nOut], iCol);
pOut[nOut++] = 0x02;
}
fts3ColumnlistCopy(0, &p);
}
if( bWritten ){
pOut[nOut++] = 0x00;
}
return nOut;
}
/*
** 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 fts3TermSelectFinishMerge(Fts3Table *p, TermSelect *pTS){
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;
char *aNew;
int rc = fts3DoclistOrMerge(p->bDescIdx,
pTS->aaOutput[i], pTS->anOutput[i], aOut, nOut, &aNew, &nNew
);
if( rc!=SQLITE_OK ){
sqlite3_free(aOut);
return rc;
}
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;
}
/*
** Merge the doclist aDoclist/nDoclist into the TermSelect object passed
** as the first argument. The merge is an "OR" merge (see function
** fts3DoclistOrMerge() for details).
**
** This function is called with the doclist for each term that matches
** a queried prefix. It merges all these doclists into one, the doclist
** for the specified prefix. Since there can be a very large number of
** doclists to merge, the merging is done pair-wise using the TermSelect
** object.
**
** This function returns SQLITE_OK if the merge is successful, or an
** SQLite error code (SQLITE_NOMEM) if an error occurs.
*/
static int fts3TermSelectMerge(
Fts3Table *p, /* FTS table handle */
TermSelect *pTS, /* TermSelect object to merge into */
char *aDoclist, /* Pointer to doclist */
int nDoclist /* Size of aDoclist in bytes */
){
if( pTS->aaOutput[0]==0 ){
/* If this is the first term selected, copy the doclist to the output
** buffer using memcpy().
**
** Add FTS3_VARINT_MAX bytes of unused space to the end of the
** allocation. This is so as to ensure that the buffer is big enough
** to hold the current doclist AND'd with any other doclist. If the
** doclists are stored in order=ASC order, this padding would not be
** required (since the size of [doclistA AND doclistB] is always less
** than or equal to the size of [doclistA] in that case). But this is
** not true for order=DESC. For example, a doclist containing (1, -1)
** may be smaller than (-1), as in the first example the -1 may be stored
** as a single-byte delta, whereas in the second it must be stored as a
** FTS3_VARINT_MAX byte varint.
**
** Similar padding is added in the fts3DoclistOrMerge() function.
*/
pTS->aaOutput[0] = sqlite3_malloc64((i64)nDoclist + FTS3_VARINT_MAX + 1);
pTS->anOutput[0] = nDoclist;
if( pTS->aaOutput[0] ){
memcpy(pTS->aaOutput[0], aDoclist, nDoclist);
memset(&pTS->aaOutput[0][nDoclist], 0, FTS3_VARINT_MAX);
}else{
return SQLITE_NOMEM;
}
}else{
char *aMerge = aDoclist;
int nMerge = nDoclist;
int iOut;
for(iOut=0; iOut<SizeofArray(pTS->aaOutput); iOut++){
if( pTS->aaOutput[iOut]==0 ){
assert( iOut>0 );
pTS->aaOutput[iOut] = aMerge;
pTS->anOutput[iOut] = nMerge;
break;
}else{
char *aNew;
int nNew;
int rc = fts3DoclistOrMerge(p->bDescIdx, aMerge, nMerge,
pTS->aaOutput[iOut], pTS->anOutput[iOut], &aNew, &nNew
);
if( rc!=SQLITE_OK ){
if( aMerge!=aDoclist ) sqlite3_free(aMerge);
return rc;
}
if( aMerge!=aDoclist ) 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;
}
/*
** Append SegReader object pNew to the end of the pCsr->apSegment[] array.
*/
static int fts3SegReaderCursorAppend(
Fts3MultiSegReader *pCsr,
Fts3SegReader *pNew
){
if( (pCsr->nSegment%16)==0 ){
Fts3SegReader **apNew;
sqlite3_int64 nByte = (pCsr->nSegment + 16)*sizeof(Fts3SegReader*);
apNew = (Fts3SegReader **)sqlite3_realloc64(pCsr->apSegment, nByte);
if( !apNew ){
sqlite3Fts3SegReaderFree(pNew);
return SQLITE_NOMEM;
}
pCsr->apSegment = apNew;
}
pCsr->apSegment[pCsr->nSegment++] = pNew;
return SQLITE_OK;
}
/*
** Add seg-reader objects to the Fts3MultiSegReader object passed as the
** 8th argument.
**
** This function returns SQLITE_OK if successful, or an SQLite error code
** otherwise.
*/
static int fts3SegReaderCursor(
Fts3Table *p, /* FTS3 table handle */
int iLangid, /* Language id */
int iIndex, /* Index to search (from 0 to p->nIndex-1) */
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 */
Fts3MultiSegReader *pCsr /* Cursor object to populate */
){
int rc = SQLITE_OK; /* Error code */
sqlite3_stmt *pStmt = 0; /* Statement to iterate through segments */
int rc2; /* Result of sqlite3_reset() */
/* If iLevel is less than 0 and this is not a scan, include a seg-reader
** for the pending-terms. If this is a scan, then this call must be being
** made by an fts4aux module, not an FTS table. In this case calling
** Fts3SegReaderPending might segfault, as the data structures used by
** fts4aux are not completely populated. So it's easiest to filter these
** calls out here. */
if( iLevel<0 && p->aIndex && p->iPrevLangid==iLangid ){
Fts3SegReader *pSeg = 0;
rc = sqlite3Fts3SegReaderPending(p, iIndex, zTerm, nTerm, isPrefix||isScan, &pSeg);
if( rc==SQLITE_OK && pSeg ){
rc = fts3SegReaderCursorAppend(pCsr, pSeg);
}
}
if( iLevel!=FTS3_SEGCURSOR_PENDING ){
if( rc==SQLITE_OK ){
rc = sqlite3Fts3AllSegdirs(p, iLangid, iIndex, iLevel, &pStmt);
}
while( rc==SQLITE_OK && SQLITE_ROW==(rc = sqlite3_step(pStmt)) ){
Fts3SegReader *pSeg = 0;
/* 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 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 && zRoot ){
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(pCsr->nSegment+1,
(isPrefix==0 && isScan==0),
iStartBlock, iLeavesEndBlock,
iEndBlock, zRoot, nRoot, &pSeg
);
if( rc!=SQLITE_OK ) goto finished;
rc = fts3SegReaderCursorAppend(pCsr, pSeg);
}
}
finished:
rc2 = sqlite3_reset(pStmt);
if( rc==SQLITE_DONE ) rc = rc2;
return rc;
}
/*
** Set up a cursor object for iterating through a full-text index or a
** single level therein.
*/
int sqlite3Fts3SegReaderCursor(
Fts3Table *p, /* FTS3 table handle */
int iLangid, /* Language-id to search */
int iIndex, /* Index to search (from 0 to p->nIndex-1) */
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 */
Fts3MultiSegReader *pCsr /* Cursor object to populate */
){
assert( iIndex>=0 && iIndex<p->nIndex );
assert( iLevel==FTS3_SEGCURSOR_ALL
|| iLevel==FTS3_SEGCURSOR_PENDING
|| iLevel>=0
);
assert( iLevel<FTS3_SEGDIR_MAXLEVEL );
assert( FTS3_SEGCURSOR_ALL<0 && FTS3_SEGCURSOR_PENDING<0 );
assert( isPrefix==0 || isScan==0 );
memset(pCsr, 0, sizeof(Fts3MultiSegReader));
return fts3SegReaderCursor(
p, iLangid, iIndex, iLevel, zTerm, nTerm, isPrefix, isScan, pCsr
);
}
/*
** In addition to its current configuration, have the Fts3MultiSegReader
** passed as the 4th argument also scan the doclist for term zTerm/nTerm.
**
** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.
*/
static int fts3SegReaderCursorAddZero(
Fts3Table