/*
** 2006 Oct 10
**
** The author disclaims copyright to this source code. In place of
** a legal notice, here is a blessing:
**
** May you do good and not evil.
** May you find forgiveness for yourself and forgive others.
** May you share freely, never taking more than you give.
**
******************************************************************************
**
** This is an SQLite module implementing full-text search.
*/
/*
** The code in this file is only compiled if:
**
** * The FTS3 module is being built as an extension
** (in which case SQLITE_CORE is not defined), or
**
** * The FTS3 module is being built into the core of
** SQLite (in which case SQLITE_ENABLE_FTS3 is defined).
*/
/* The full-text index is stored in a series of b+tree (-like)
** structures called segments which map terms to doclists. The
** structures are like b+trees in layout, but are constructed from the
** bottom up in optimal fashion and are not updatable. Since trees
** are built from the bottom up, things will be described from the
** bottom up.
**
**
**** Varints ****
** The basic unit of encoding is a variable-length integer called a
** varint. We encode variable-length integers in little-endian order
** using seven bits * per byte as follows:
**
** KEY:
** A = 0xxxxxxx 7 bits of data and one flag bit
** B = 1xxxxxxx 7 bits of data and one flag bit
**
** 7 bits - A
** 14 bits - BA
** 21 bits - BBA
** and so on.
**
** This is similar in concept to how sqlite encodes "varints" but
** the encoding is not the same. SQLite varints are big-endian
** are are limited to 9 bytes in length whereas FTS3 varints are
** little-endian and can be up to 10 bytes in length (in theory).
**
** Example encodings:
**
** 1: 0x01
** 127: 0x7f
** 128: 0x81 0x00
**
**
**** Document lists ****
** A doclist (document list) holds a docid-sorted list of hits for a
** given term. Doclists hold docids and associated token positions.
** A docid is the unique integer identifier for a single document.
** A position is the index of a word within the document. The first
** word of the document has a position of 0.
**
** FTS3 used to optionally store character offsets using a compile-time
** option. But that functionality is no longer supported.
**
** A doclist is stored like this:
**
** array {
** varint docid;
** array { (position list for column 0)
** varint position; (2 more than the delta from previous position)
** }
** array {
** varint POS_COLUMN; (marks start of position list for new column)
** varint column; (index of new column)
** array {
** varint position; (2 more than the delta from previous position)
** }
** }
** varint POS_END; (marks end of positions for this document.
** }
**
** Here, array { X } means zero or more occurrences of X, adjacent in
** memory. A "position" is an index of a token in the token stream
** generated by the tokenizer. Note that POS_END and POS_COLUMN occur
** in the same logical place as the position element, and act as sentinals
** ending a position list array. POS_END is 0. POS_COLUMN is 1.
** The positions numbers are not stored literally but rather as two more
** than the difference from the prior position, or the just the position plus
** 2 for the first position. Example:
**
** label: A B C D E F G H I J K
** value: 123 5 9 1 1 14 35 0 234 72 0
**
** The 123 value is the first docid. For column zero in this document
** there are two matches at positions 3 and 10 (5-2 and 9-2+3). The 1
** at D signals the start of a new column; the 1 at E indicates that the
** new column is column number 1. There are two positions at 12 and 45
** (14-2 and 35-2+12). The 0 at H indicate the end-of-document. The
** 234 at I is the next docid. It has one position 72 (72-2) and then
** terminates with the 0 at K.
**
** A "position-list" is the list of positions for multiple columns for
** a single docid. A "column-list" is the set of positions for a single
** column. Hence, a position-list consists of one or more column-lists,
** a document record consists of a docid followed by a position-list and
** a doclist consists of one or more document records.
**
** A bare doclist omits the position information, becoming an
** array of varint-encoded docids.
**
**** Segment leaf nodes ****
** Segment leaf nodes store terms and doclists, ordered by term. Leaf
** nodes are written using LeafWriter, and read using LeafReader (to
** iterate through a single leaf node's data) and LeavesReader (to
** iterate through a segment's entire leaf layer). Leaf nodes have
** the format:
**
** varint iHeight; (height from leaf level, always 0)
** varint nTerm; (length of first term)
** char pTerm[nTerm]; (content of first term)
** varint nDoclist; (length of term's associated doclist)
** char pDoclist[nDoclist]; (content of doclist)
** array {
** (further terms are delta-encoded)
** varint nPrefix; (length of prefix shared with previous term)
** varint nSuffix; (length of unshared suffix)
** char pTermSuffix[nSuffix];(unshared suffix of next term)
** varint nDoclist; (length of term's associated doclist)
** char pDoclist[nDoclist]; (content of doclist)
** }
**
** Here, array { X } means zero or more occurrences of X, adjacent in
** memory.
**
** Leaf nodes are broken into blocks which are stored contiguously in
** the %_segments table in sorted order. This means that when the end
** of a node is reached, the next term is in the node with the next
** greater node id.
**
** New data is spilled to a new leaf node when the current node
** exceeds LEAF_MAX bytes (default 2048). New data which itself is
** larger than STANDALONE_MIN (default 1024) is placed in a standalone
** node (a leaf node with a single term and doclist). The goal of
** these settings is to pack together groups of small doclists while
** making it efficient to directly access large doclists. The
** assumption is that large doclists represent terms which are more
** likely to be query targets.
**
** TODO(shess) It may be useful for blocking decisions to be more
** dynamic. For instance, it may make more sense to have a 2.5k leaf
** node rather than splitting into 2k and .5k nodes. My intuition is
** that this might extend through 2x or 4x the pagesize.
**
**
**** Segment interior nodes ****
** Segment interior nodes store blockids for subtree nodes and terms
** to describe what data is stored by the each subtree. Interior
** nodes are written using InteriorWriter, and read using
** InteriorReader. InteriorWriters are created as needed when
** SegmentWriter creates new leaf nodes, or when an interior node
** itself grows too big and must be split. The format of interior
** nodes:
**
** varint iHeight; (height from leaf level, always >0)
** varint iBlockid; (block id of node's leftmost subtree)
** optional {
** varint nTerm; (length of first term)
** char pTerm[nTerm]; (content of first term)
** array {
** (further terms are delta-encoded)
** varint nPrefix; (length of shared prefix with previous term)
** varint nSuffix; (length of unshared suffix)
** char pTermSuffix[nSuffix]; (unshared suffix of next term)
** }
** }
**
** Here, optional { X } means an optional element, while array { X }
** means zero or more occurrences of X, adjacent in memory.
**
** An interior node encodes n terms separating n+1 subtrees. The
** subtree blocks are contiguous, so only the first subtree's blockid
** is encoded. The subtree at iBlockid will contain all terms less
** than the first term encoded (or all terms if no term is encoded).
** Otherwise, for terms greater than or equal to pTerm[i] but less
** than pTerm[i+1], the subtree for that term will be rooted at
** iBlockid+i. Interior nodes only store enough term data to
** distinguish adjacent children (if the rightmost term of the left
** child is "something", and the leftmost term of the right child is
** "wicked", only "w" is stored).
**
** New data is spilled to a new interior node at the same height when
** the current node exceeds INTERIOR_MAX bytes (default 2048).
** INTERIOR_MIN_TERMS (default 7) keeps large terms from monopolizing
** interior nodes and making the tree too skinny. The interior nodes
** at a given height are naturally tracked by interior nodes at
** height+1, and so on.
**
**
**** Segment directory ****
** The segment directory in table %_segdir stores meta-information for
** merging and deleting segments, and also the root node of the
** segment's tree.
**
** The root node is the top node of the segment's tree after encoding
** the entire segment, restricted to ROOT_MAX bytes (default 1024).
** This could be either a leaf node or an interior node. If the top
** node requires more than ROOT_MAX bytes, it is flushed to %_segments
** and a new root interior node is generated (which should always fit
** within ROOT_MAX because it only needs space for 2 varints, the
** height and the blockid of the previous root).
**
** The meta-information in the segment directory is:
** level - segment level (see below)
** idx - index within level
** - (level,idx uniquely identify a segment)
** start_block - first leaf node
** leaves_end_block - last leaf node
** end_block - last block (including interior nodes)
** root - contents of root node
**
** If the root node is a leaf node, then start_block,
** leaves_end_block, and end_block are all 0.
**
**
**** Segment merging ****
** To amortize update costs, segments are grouped into levels and
** merged in batches. Each increase in level represents exponentially
** more documents.
**
** New documents (actually, document updates) are tokenized and
** written individually (using LeafWriter) to a level 0 segment, with
** incrementing idx. When idx reaches MERGE_COUNT (default 16), all
** level 0 segments are merged into a single level 1 segment. Level 1
** is populated like level 0, and eventually MERGE_COUNT level 1
** segments are merged to a single level 2 segment (representing
** MERGE_COUNT^2 updates), and so on.
**
** A segment merge traverses all segments at a given level in
** parallel, performing a straightforward sorted merge. Since segment
** leaf nodes are written in to the %_segments table in order, this
** merge traverses the underlying sqlite disk structures efficiently.
** After the merge, all segment blocks from the merged level are
** deleted.
**
** MERGE_COUNT controls how often we merge segments. 16 seems to be
** somewhat of a sweet spot for insertion performance. 32 and 64 show
** very similar performance numbers to 16 on insertion, though they're
** a tiny bit slower (perhaps due to more overhead in merge-time
** sorting). 8 is about 20% slower than 16, 4 about 50% slower than
** 16, 2 about 66% slower than 16.
**
** At query time, high MERGE_COUNT increases the number of segments
** which need to be scanned and merged. For instance, with 100k docs
** inserted:
**
** MERGE_COUNT segments
** 16 25
** 8 12
** 4 10
** 2 6
**
** This appears to have only a moderate impact on queries for very
** frequent terms (which are somewhat dominated by segment merge
** costs), and infrequent and non-existent terms still seem to be fast
** even with many segments.
**
** TODO(shess) That said, it would be nice to have a better query-side
** argument for MERGE_COUNT of 16. Also, it is possible/likely that
** optimizations to things like doclist merging will swing the sweet
** spot around.
**
**
**
**** Handling of deletions and updates ****
** Since we're using a segmented structure, with no docid-oriented
** index into the term index, we clearly cannot simply update the term
** index when a document is deleted or updated. For deletions, we
** write an empty doclist (varint(docid) varint(POS_END)), for updates
** we simply write the new doclist. Segment merges overwrite older
** data for a particular docid with newer data, so deletes or updates
** will eventually overtake the earlier data and knock it out. The
** query logic likewise merges doclists so that newer data knocks out
** older data.
**
** TODO(shess) Provide a VACUUM type operation to clear out all
** deletions and duplications. This would basically be a forced merge
** into a single segment.
*/
#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)
#if defined(SQLITE_ENABLE_FTS3) && !defined(SQLITE_CORE)
# define SQLITE_CORE 1
#endif
#include "fts3Int.h"
#include <assert.h>
#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <stdarg.h>
#include "fts3.h"
#ifndef SQLITE_CORE
# include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1
#endif
/*
** Write a 64-bit variable-length integer to memory starting at p[0].
** The length of data written will be between 1 and FTS3_VARINT_MAX bytes.
** The number of bytes written is returned.
*/
int sqlite3Fts3PutVarint(char *p, sqlite_int64 v){
unsigned char *q = (unsigned char *) p;
sqlite_uint64 vu = v;
do{
*q++ = (unsigned char) ((vu & 0x7f) | 0x80);
vu >>= 7;
}while( vu!=0 );
q[-1] &= 0x7f; /* turn off high bit in final byte */
assert( q - (unsigned char *)p <= FTS3_VARINT_MAX );
return (int) (q - (unsigned char *)p);
}
/*
** Read a 64-bit variable-length integer from memory starting at p[0].
** Return the number of bytes read, or 0 on error.
** The value is stored in *v.
*/
int sqlite3Fts3GetVarint(const char *p, sqlite_int64 *v){
const unsigned char *q = (const unsigned char *) p;
sqlite_uint64 x = 0, y = 1;
while( (*q&0x80)==0x80 && q-(unsigned char *)p<FTS3_VARINT_MAX ){
x += y * (*q++ & 0x7f);
y <<= 7;
}
x += y * (*q++);
*v = (sqlite_int64) x;
return (int) (q - (unsigned char *)p);
}
/*
** Similar to sqlite3Fts3GetVarint(), except that the output is truncated to a
** 32-bit integer before it is returned.
*/
int sqlite3Fts3GetVarint32(const char *p, int *pi){
sqlite_int64 i;
int ret = sqlite3Fts3GetVarint(p, &i);
*pi = (int) i;
return ret;
}
/*
** Return the number of bytes required to encode v as a varint
*/
int sqlite3Fts3VarintLen(sqlite3_uint64 v){
int i = 0;
do{
i++;
v >>= 7;
}while( v!=0 );
return i;
}
/*
** Convert an SQL-style quoted string into a normal string by removing
** the quote characters. The conversion is done in-place. If the
** input does not begin with a quote character, then this routine
** is a no-op.
**
** Examples:
**
** "abc" becomes abc
** 'xyz' becomes xyz
** [pqr] becomes pqr
** `mno` becomes mno
**
*/
void sqlite3Fts3Dequote(char *z){
char quote; /* Quote character (if any ) */
quote = z[0];
if( quote=='[' || quote=='\'' || quote=='"' || quote=='`' ){
int iIn = 1; /* Index of next byte to read from input */
int iOut = 0; /* Index of next byte to write to output */
/* If the first byte was a '[', then the close-quote character is a ']' */
if( quote=='[' ) quote = ']';
while( ALWAYS(z[iIn]) ){
if( z[iIn]==quote ){
if( z[iIn+1]!=quote ) break;
z[iOut++] = quote;
iIn += 2;
}else{
z[iOut++] = z[iIn++];
}
}
z[iOut] = '\0';
}
}
/*
** Read a single varint from the doclist at *pp and advance *pp to point
** to the first byte past the end of the varint. Add the value of the varint
** to *pVal.
*/
static void fts3GetDeltaVarint(char **pp, sqlite3_int64 *pVal){
sqlite3_int64 iVal;
*pp += sqlite3Fts3GetVarint(*pp, &iVal);
*pVal += iVal;
}
/*
** As long as *pp has not reached its end (pEnd), then do the same
** as fts3GetDeltaVarint(): read a single varint and add it to *pVal.
** But if we have reached the end of the varint, just set *pp=0 and
** leave *pVal unchanged.
*/
static void fts3GetDeltaVarint2(char **pp, char *pEnd, sqlite3_int64 *pVal){
if( *pp>=pEnd ){
*pp = 0;
}else{
fts3GetDeltaVarint(pp, pVal);
}
}
/*
** The xDisconnect() virtual table method.
*/
static int fts3DisconnectMethod(sqlite3_vtab *pVtab){
Fts3Table *p = (Fts3Table *)pVtab;
int i;
assert( p->nPendingData==0 );
/* Free any prepared statements held */
for(i=0; i<SizeofArray(p->aStmt); i++){
sqlite3_finalize(p->aStmt[i]);
}
for(i=0; i<p->nLeavesStmt; i++){
sqlite3_finalize(p->aLeavesStmt[i]);
}
sqlite3_free(p->zSelectLeaves);
sqlite3_free(p->aLeavesStmt);
/* Invoke the tokenizer destructor to free the tokenizer. */
p->pTokenizer->pModule->xDestroy(p->pTokenizer);
sqlite3_free(p);
return SQLITE_OK;
}
/*
** Construct one or more SQL statements from the format string given
** and then evaluate those statements. The success code is writting
** into *pRc.
**
** If *pRc is initially non-zero then this routine is a no-op.
*/
static void fts3DbExec(
int *pRc, /* Success code */
sqlite3 *db, /* Database in which to run SQL */
const char *zFormat, /* Format string for SQL */
... /* Arguments to the format string */
){
va_list ap;
char *zSql;
if( *pRc ) return;
va_start(ap, zFormat);
zSql = sqlite3_vmprintf(zFormat, ap);
va_end(ap);
if( zSql==0 ){
*pRc = SQLITE_NOMEM;
}else{
*pRc = sqlite3_exec(db, zSql, 0, 0, 0);
sqlite3_free(zSql);
}
}
/*
** The xDestroy() virtual table method.
*/
static int fts3DestroyMethod(sqlite3_vtab *pVtab){
int rc = SQLITE_OK; /* Return code */
Fts3Table *p = (Fts3Table *)pVtab;
sqlite3 *db = p->db;
/* Drop the shadow tables */
fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_content'", p->zDb, p->zName);
fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_segments'", p->zDb,p->zName);
fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_segdir'", p->zDb, p->zName);
fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_docsize'", p->zDb, p->zName);
fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_stat'", p->zDb, p->zName);
/* If everything has worked, invoke fts3DisconnectMethod() to free the
** memory associated with the Fts3Table structure and return SQLITE_OK.
** Otherwise, return an SQLite error code.
*/
return (rc==SQLITE_OK ? fts3DisconnectMethod(pVtab) : rc);
}
/*
** Invoke sqlite3_declare_vtab() to declare the schema for the FTS3 table
** passed as the first argument. This is done as part of the xConnect()
** and xCreate() methods.
*/
static int fts3DeclareVtab(Fts3Table *p){
int i; /* Iterator variable */
int rc; /* Return code */
char *zSql; /* SQL statement passed to declare_vtab() */
char *zCols; /* List of user defined columns */
/* Create a list of user columns for the virtual table */
zCols = sqlite3_mprintf("%Q, ", p->azColumn[0]);
for(i=1; zCols && i<p->nColumn; i++){
zCols = sqlite3_mprintf("%z%Q, ", zCols, p->azColumn[i]);
}
/* Create the whole "CREATE TABLE" statement to pass to SQLite */
zSql = sqlite3_mprintf(
"CREATE TABLE x(%s %Q HIDDEN, docid HIDDEN)", zCols, p->zName
);
if( !zCols || !zSql ){
rc = SQLITE_NOMEM;
}else{
rc = sqlite3_declare_vtab(p->db, zSql);
}
sqlite3_free(zSql);
sqlite3_free(zCols);
return rc;
}
/*
** Create the backing store tables (%_content, %_segments and %_segdir)
** required by the FTS3 table passed as the only argument. This is done
** as part of the vtab xCreate() method.
**
** If the p->bHasDocsize boolean is true (indicating that this is an
** FTS4 table, not an FTS3 table) then also create the %_docsize and
** %_stat tables required by FTS4.
*/
static int fts3CreateTables(Fts3Table *p){
int rc = SQLITE_OK; /* Return code */
int i; /* Iterator variable */
char *zContentCols; /* Columns of %_content table */
sqlite3 *db = p->db; /* The database connection */
/* Create a list of user columns for the content table */
if( p->bHasContent ){
zContentCols = sqlite3_mprintf("docid INTEGER PRIMARY KEY");
for(i=0; zContentCols && i<p->nColumn; i++){
char *z = p->azColumn[i];
zContentCols = sqlite3_mprintf("%z, 'c%d%q'", zContentCols, i, z);
}
if( zContentCols==0 ) rc = SQLITE_NOMEM;
/* Create the content table */
fts3DbExec(&rc, db,
"CREATE TABLE %Q.'%q_content'(%s)",
p->zDb, p->zName, zContentCols
);
sqlite3_free(zContentCols);
}
/* Create other tables */
fts3DbExec(&rc, db,
"CREATE TABLE %Q.'%q_segments'(blockid INTEGER PRIMARY KEY, block BLOB);",
p->zDb, p->zName
);
fts3DbExec(&rc, db,
"CREATE TABLE %Q.'%q_segdir'("
"level INTEGER,"
"idx INTEGER,"
"start_block INTEGER,"
"leaves_end_block INTEGER,"
"end_block INTEGER,"
"root BLOB,"
"PRIMARY KEY(level, idx)"
");",
p->zDb, p->zName
);
if( p->bHasDocsize ){
fts3DbExec(&rc, db,
"CREATE TABLE %Q.'%q_docsize'(docid INTEGER PRIMARY KEY, size BLOB);",
p->zDb, p->zName
);
fts3DbExec(&rc, db,
"CREATE TABLE %Q.'%q_stat'(id INTEGER PRIMARY KEY, value BLOB);",
p->zDb, p->zName
);
}
return rc;
}
/*
** An sqlite3_exec() callback for fts3TableExists.
*/
static int fts3TableExistsCallback(void *pArg, int n, char **pp1, char **pp2){
UNUSED_PARAMETER(n);
UNUSED_PARAMETER(pp1);
UNUSED_PARAMETER(pp2);
*(int*)pArg = 1;
return 1;
}
/*
** Determine if a table currently exists in the database.
*/
static void fts3TableExists(
int *pRc, /* Success code */
sqlite3 *db, /* The database connection to test */
const char *zDb, /* ATTACHed database within the connection */
const char *zName, /* Name of the FTS3 table */
const char *zSuffix, /* Shadow table extension */
u8 *pResult /* Write results here */
){
int rc = SQLITE_OK;
int res = 0;
char *zSql;
if( *pRc ) return;
zSql = sqlite3_mprintf(
"SELECT 1 FROM %Q.sqlite_master WHERE name='%q%s'",
zDb, zName, zSuffix
);
rc = sqlite3_exec(db, zSql, fts3TableExistsCallback, &res, 0);
sqlite3_free(zSql);
*pResult = (u8)(res & 0xff);
if( rc!=SQLITE_ABORT ) *pRc = 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 = (Fts3Hash *)pAux;
Fts3Table *p; /* Pointer to allocated vtab */
int rc; /* Return code */
int i; /* Iterator variable */
int nByte; /* Size of allocation used for *p */
int iCol; /* Column index */
int nString = 0; /* Bytes required to hold all column names */
int nCol = 0; /* Number of columns in the FTS table */
char *zCsr; /* Space for holding column names */
int nDb; /* Bytes required to hold database name */
int nName; /* Bytes required to hold table name */
const char *zTokenizer = 0; /* Name of tokenizer to use */
sqlite3_tokenizer *pTokenizer = 0; /* Tokenizer for this table */
nDb = (int)strlen(argv[1]) + 1;
nName = (int)strlen(argv[2]) + 1;
for(i=3; i<argc; i++){
char const *z = argv[i];
rc = sqlite3Fts3InitTokenizer(pHash, z, &pTokenizer, &zTokenizer, pzErr);
if( rc!=SQLITE_OK ){
return rc;
}
if( z!=zTokenizer ){
nString += (int)(strlen(z) + 1);
}
}
nCol = argc - 3 - (zTokenizer!=0);
if( zTokenizer==0 ){
rc = sqlite3Fts3InitTokenizer(pHash, 0, &pTokenizer, 0, pzErr);
if( rc!=SQLITE_OK ){
return rc;
}
assert( pTokenizer );
}
if( nCol==0 ){
nCol = 1;
}
/* Allocate and populate the Fts3Table structure. */
nByte = sizeof(Fts3Table) + /* Fts3Table */
nCol * sizeof(char *) + /* azColumn */
nName + /* zName */
nDb + /* zDb */
nString; /* Space for azColumn strings */
p = (Fts3Table*)sqlite3_malloc(nByte);
if( p==0 ){
rc = SQLITE_NOMEM;
goto fts3_init_out;
}
memset(p, 0, nByte);
p->db = db;
p->nColumn = nCol;
p->nPendingData = 0;
p->azColumn = (char **)&p[1];
p->pTokenizer = pTokenizer;
p->nNodeSize = 1000;
p->nMaxPendingData = FTS3_MAX_PENDING_DATA;
zCsr = (char *)&p->azColumn[nCol];
fts3HashInit(&p->pendingTerms, FTS3_HASH_STRING, 1);
/* Fill in the zName and zDb fields of the vtab structure. */
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 */
iCol = 0;
for(i=3; i<argc; i++){
if( argv[i]!=zTokenizer ){
char *z;
int n;
z = (char *)sqlite3Fts3NextToken(argv[i], &n);
memcpy(zCsr, z, n);
zCsr[n] = '\0';
sqlite3Fts3Dequote(zCsr);
p->azColumn[iCol++] = zCsr;
zCsr += n+1;
assert( zCsr <= &((char *)p)[nByte] );
}
}
if( iCol==0 ){
assert( nCol==1 );
p->azColumn[0] = "content";
}
/* 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 ){
p->bHasContent = 1;
p->bHasDocsize = argv[0][3]=='4';
rc = fts3CreateTables(p);
}else{
rc = SQLITE_OK;
fts3TableExists(&rc, db, argv[1], argv[2], "_content", &p->bHasContent);
fts3TableExists(&rc, db, argv[1], argv[2], "_docsize", &p->bHasDocsize);
}
if( rc!=SQLITE_OK ) goto fts3_init_out;
rc = fts3DeclareVtab(p);
if( rc!=SQLITE_OK ) goto fts3_init_out;
*ppVTab = &p->base;
fts3_init_out:
assert( p || (pTokenizer && rc!=SQLITE_OK) );
if( rc!=SQLITE_OK ){
if( p ){
fts3DisconnectMethod((sqlite3_vtab *)p);
}else{
pTokenizer->pModule->xDestroy(pTokenizer);
}
}
return rc;
}
/*
** The xConnect() and xCreate() methods for the virtual table. All the
** work is done in function fts3InitVtab().
*/
static int fts3ConnectMethod(
sqlite3 *db, /* Database connection */
void *pAux, /* Pointer to tokenizer hash table */
int argc, /* Number of elements in argv array */
const char * const *argv, /* xCreate/xConnect argument array */
sqlite3_vtab **ppVtab, /* OUT: New sqlite3_vtab object */
char **pzErr /* OUT: sqlite3_malloc'd error message */
){
return fts3InitVtab(0, db, pAux, argc, argv, ppVtab, pzErr);
}
static int fts3CreateMethod(
sqlite3 *db, /* Database connection */
void *pAux, /* Pointer to tokenizer hash table */
int argc, /* Number of elements in argv array */
const char * const *argv, /* xCreate/xConnect argument array */
sqlite3_vtab **ppVtab, /* OUT: New sqlite3_vtab object */
char **pzErr /* OUT: sqlite3_malloc'd error message */
){
return fts3InitVtab(1, db, pAux, argc, argv, ppVtab, pzErr);
}
/*
** Implementation of the xBestIndex method for FTS3 tables. There
** are three possible strategies, in order of preference:
**
** 1. Direct lookup by rowid or docid.
** 2. Full-text search using a MATCH operator on a non-docid column.
** 3. Linear scan of %_content table.
*/
static int fts3BestIndexMethod(sqlite3_vtab *pVTab, sqlite3_index_info *pInfo){
Fts3Table *p = (Fts3Table *)pVTab;
int i; /* Iterator variable */
int iCons = -1; /* Index of constraint to use */
/* By default use a full table scan. This is an expensive option,
** so search through the constraints to see if a more efficient
** strategy is possible.
*/
pInfo->idxNum = FTS3_FULLSCAN_SEARCH;
pInfo->estimatedCost = 500000;
for(i=0; i<pInfo->nConstraint; i++){
struct sqlite3_index_constraint *pCons = &pInfo->aConstraint[i];
if( pCons->usable==0 ) continue;
/* A direct lookup on the rowid or docid column. Assign a cost of 1.0. */
if( pCons->op==SQLITE_INDEX_CONSTRAINT_EQ
&& (pCons->iColumn<0 || pCons->iColumn==p->nColumn+1 )
){
pInfo->idxNum = FTS3_DOCID_SEARCH;
pInfo->estimatedCost = 1.0;
iCons = i;
}
/* A MATCH constraint. Use a full-text search.
**
** If there is more than one MATCH constraint available, use the first
** one encountered. If there is both a MATCH constraint and a direct
** rowid/docid lookup, prefer the MATCH strategy. This is done even
** though the rowid/docid lookup is faster than a MATCH query, selecting
** it would lead to an "unable to use function MATCH in the requested
** context" error.
*/
if( pCons->op==SQLITE_INDEX_CONSTRAINT_MATCH
&& pCons->iColumn>=0 && pCons->iColumn<=p->nColumn
){
pInfo->idxNum = FTS3_FULLTEXT_SEARCH + pCons->iColumn;
pInfo->estimatedCost = 2.0;
iCons = i;
break;
}
}
if( iCons>=0 ){
pInfo->aConstraintUsage[iCons].argvIndex = 1;
pInfo->aConstraintUsage[iCons].omit = 1;
}
return SQLITE_OK;
}
/*
** Implementation of xOpen method.
*/
static int fts3OpenMethod(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCsr){
sqlite3_vtab_cursor *pCsr; /* Allocated cursor */
UNUSED_PARAMETER(pVTab);
/* Allocate a buffer large enough for an Fts3Cursor structure. If the
** allocation succeeds, zero it and return SQLITE_OK. Otherwise,
** if the allocation fails, return SQLITE_NOMEM.
*/
*ppCsr = pCsr = (sqlite3_vtab_cursor *)sqlite3_malloc(sizeof(Fts3Cursor));
if( !pCsr ){
return SQLITE_NOMEM;
}
memset(pCsr, 0, sizeof(Fts3Cursor));
return SQLITE_OK;
}
/*
** Close the cursor. For additional information see the documentation
** on the xClose method of the virtual table interface.
*/
static int fulltextClose(sqlite3_vtab_cursor *pCursor){
Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;
sqlite3_finalize(pCsr->pStmt);
sqlite3Fts3ExprFree(pCsr->pExpr);
sqlite3_free(pCsr->aDoclist);
sqlite3_free(pCsr->aMatchinfo);
sqlite3_free(pCsr);
return SQLITE_OK;
}
/*
** Position the pCsr->pStmt statement so that it is on the row
** of the %_content table that contains the last match. Return
** SQLITE_OK on success.
*/
static int fts3CursorSeek(sqlite3_context *pContext, Fts3Cursor *pCsr){
if( pCsr->isRequireSeek ){
pCsr->isRequireSeek = 0;
sqlite3_bind_int64(pCsr->pStmt, 1, pCsr->iPrevId);
if( SQLITE_ROW==sqlite3_step(pCsr->pStmt) ){
return SQLITE_OK;
}else{
int rc = sqlite3_reset(pCsr->pStmt);
if( rc==SQLITE_OK ){
/* If no row was found and no error has occured, then the %_content
** table is missing a row that is present in the full-text index.
** The data structures are corrupt.
*/
rc = SQLITE_CORRUPT;
}
pCsr->isEof = 1;
if( pContext ){
sqlite3_result_error_code(pContext, rc);
}
return rc;
}
}else{
return SQLITE_OK;
}
}
/*
** Advance the cursor to the next row in the %_content table that
** matches the search criteria. For a MATCH search, this will be
** the next row that matches. For a full-table scan, this will be
** simply the next row in the %_content table. For a docid lookup,
** this routine simply sets the EOF flag.
**
** Return SQLITE_OK if nothing goes wrong. SQLITE_OK is returned
** even if we reach end-of-file. The fts3EofMethod() will be called
** subsequently to determine whether or not an EOF was hit.
*/
static int fts3NextMethod(sqlite3_vtab_cursor *pCursor){
int rc = SQLITE_OK; /* Return code */
Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;
if( pCsr->aDoclist==0 ){
if( SQLITE_ROW!=sqlite3_step(pCsr->pStmt) ){
pCsr->isEof = 1;
rc = sqlite3_reset(pCsr->pStmt);
}
}else if( pCsr->pNextId>=&pCsr->aDoclist[pCsr->nDoclist] ){
pCsr->isEof = 1;
}else{
sqlite3_reset(pCsr->pStmt);
fts3GetDeltaVarint(&pCsr->pNextId, &pCsr->iPrevId);
pCsr->isRequireSeek = 1;
pCsr->isMatchinfoNeeded = 1;
}
return rc;
}
/*
** The buffer pointed to by argument zNode (size nNode bytes) contains the
** root node of a b-tree segment. The segment is guaranteed to be at least
** one level high (i.e. the root node is not also a leaf). If successful,
** this function locates the leaf node of the segment that may contain the
** term specified by arguments zTerm and nTerm and writes its block number
** to *piLeaf.
**
** It is possible that the returned leaf node does not contain the specified
** term. However, if the segment does contain said term, it is stored on
** the identified leaf node. 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 */
){
int rc = SQLITE_OK; /* Return code */
const char *zCsr = zNode; /* Cursor to iterate through node */
const char *zEnd = &zCsr[nNode];/* End of interior node buffer */
char *zBuffer = 0; /* Buffer to load terms into */
int nAlloc = 0; /* Size of allocated buffer */
while( 1 ){
int isFirstTerm = 1; /* True when processing first term on page */
int iHeight; /* Height of this node in tree */
sqlite3_int64 iChild; /* Block id of child node to descend to */
int nBlock; /* Size of child node in bytes */
zCsr += sqlite3Fts3GetVarint32(zCsr, &iHeight);
zCsr += sqlite3Fts3GetVarint(zCsr, &iChild);
while( zCsr<zEnd ){
int cmp; /* memcmp() result */
int nSuffix; /* Size of term suffix */
int nPrefix = 0; /* Size of term prefix */
int nBuffer; /* Total term size */
/* Load the next term on the node into zBuffer */
if( !isFirstTerm ){
zCsr += sqlite3Fts3GetVarint32(zCsr, &nPrefix);
}
isFirstTerm = 0;
zCsr += sqlite3Fts3GetVarint32(zCsr, &nSuffix);
if( nPrefix+nSuffix>nAlloc ){
char *zNew;
nAlloc = (nPrefix+nSuffix) * 2;
zNew = (char *)sqlite3_realloc(zBuffer, nAlloc);
if( !zNew ){
sqlite3_free(zBuffer);
return SQLITE_NOMEM;
}
zBuffer = zNew;
}
memcpy(&zBuffer[nPrefix], zCsr, nSuffix);
nBuffer = nPrefix + nSuffix;
zCsr += nSuffix;
/* Compare the term we are searching for with the term just loaded from
** the interior node. If the specified term is greater than or equal
** to the term from the interior node, then all terms on the sub-tree
** headed by node iChild are smaller than zTerm. No need to search
** iChild.
**
** If the interior node term is larger than the specified term, then
** the tree headed by iChild may contain the specified term.
*/
cmp = memcmp(zTerm, zBuffer, (nBuffer>nTerm ? nTerm : nBuffer));
if( cmp<0 || (cmp==0 && nBuffer>nTerm) ) break;
iChild++;
};
/* If (iHeight==1), the children of this interior node are leaves. The
** specified term may be present on leaf node iChild.
*/
if( iHeight==1 ){
*piLeaf = iChild;
break;
}
/* Descend to interior node iChild. */
rc = sqlite3Fts3ReadBlock(p, iChild, &zCsr, &nBlock);
if( rc!=SQLITE_OK ) break;
zEnd = &zCsr[nBlock];
}
sqlite3_free(zBuffer);
return rc;
}
/*
** This function is used to create delta-encoded serialized lists of FTS3
** varints. Each call to this function appends a single varint to a list.
*/
static void fts3PutDeltaVarint(
char **pp, /* IN/OUT: Output pointer */
sqlite3_int64 *piPrev, /* IN/OUT: Previous value written to list */
sqlite3_int64 iVal /* Write this value to the list */
){
assert( iVal-*piPrev > 0 || (*piPrev==0 && iVal==0) );
*pp += sqlite3Fts3PutVarint(*pp, iVal-*piPrev);
*piPrev = iVal;
}
/*
** When this function is called, *ppPoslist is assumed to point to the
** start of a position-list. After it returns, *ppPoslist points to the
** first byte after the position-list.
**
** A position list is list of positions (delta encoded) and columns for
** a single document record of a doclist. So, in other words, this
** routine advances *ppPoslist so that it points to the next docid in
** the doclist, or to the first byte past the end of the doclist.
**
** If pp is not NULL, then the contents of the position list are copied
** to *pp. *pp is set to point to the first byte past the last byte copied
** before this function returns.
*/
static void fts3PoslistCopy(char **pp, char **ppPoslist){
char *pEnd = *ppPoslist;
char c = 0;
/* The end of a position list is marked by a zero encoded as an FTS3
** varint. A single POS_END (0) byte. Except, if the 0 byte is preceded by
** a byte with the 0x80 bit set, then it is not a varint 0, but the tail
** of some other, multi-byte, value.
**
** The following while-loop moves pEnd to point to the first byte that is not
** immediately preceded by a byte with the 0x80 bit set. Then increments
** pEnd once more so that it points to the byte immediately following the
** last byte in the position-list.
*/
while( *pEnd | c ){
c = *pEnd++ & 0x80;
testcase( c!=0 && (*pEnd)==0 );
}
pEnd++; /* Advance past the POS_END terminator byte */
if( pp ){
int n = (int)(pEnd - *ppPoslist);
char *p = *pp;
memcpy(p, *ppPoslist, n);
p += n;
*pp = p;
}
*ppPoslist = pEnd;
}
/*
** When this function is called, *ppPoslist is assumed to point to the
** start of a column-list. After it returns, *ppPoslist points to the
** to the terminator (POS_COLUMN or POS_END) byte of the column-list.
**
** A column-list is list of delta-encoded positions for a single column
** within a single document within a doclist.
**
** The column-list is terminated either by a POS_COLUMN varint (1) or
** a POS_END varint (0). This routine leaves *ppPoslist pointing to
** the POS_COLUMN or POS_END that terminates the column-list.
**
** If pp is not NULL, then the contents of the column-list are copied
** to *pp. *pp is set to point to the first byte past the last byte copied
** before this function returns. The POS_COLUMN or POS_END terminator
** is not copied into *pp.
*/
static void fts3ColumnlistCopy(char **pp, char **ppPoslist){
char *pEnd = *ppPoslist;
char c = 0;
/* A column-list is terminated by either a 0x01 or 0x00 byte that is
** not part of a multi-byte varint.
*/
while( 0xFE & (*pEnd | c) ){
c = *pEnd++ & 0x80;
testcase( c!=0 && ((*pEnd)&0xfe)==0 );
}
if( pp ){
int n = (int)(pEnd - *ppPoslist);
char *p = *pp;
memcpy(p, *ppPoslist, n);
p += n;
*pp = p;
}
*ppPoslist = pEnd;
}
/*
** Value used to signify the end of an position-list. This is safe because
** it is not possible to have a document with 2^31 terms.
*/
#define POSITION_LIST_END 0x7fffffff
/*
** This function is used to help parse position-lists. When this function is
** called, *pp may point to the start of the next varint in the position-list
** being parsed, or it may point to 1 byte past the end of the position-list
** (in which case **pp will be a terminator bytes POS_END (0) or
** (1)).
**
** If *pp points past the end of the current position-list, set *pi to
** POSITION_LIST_END and return. Otherwise, read the next varint from *pp,
** increment the current value of *pi by the value read, and set *pp to
** point to the next value before returning.
**
** Before calling this routine *pi must be initialized to the value of
** the previous position, or zero if we are reading the first position
** in the position-list. Because positions are delta-encoded, the value
** of the previous position is needed in order to compute the value of
** the next position.
*/
static void fts3ReadNextPos(
char **pp, /* IN/OUT: Pointer into position-list buffer */
sqlite3_int64 *pi /* IN/OUT: Value read from position-list */
){
if( (**pp)&0xFE ){
fts3GetDeltaVarint(pp, pi);
*pi -= 2;
}else{
*pi = POSITION_LIST_END;
}
}
/*
** If parameter iCol is not 0, write an POS_COLUMN (1) byte followed by
** the value of iCol encoded as a varint to *pp. This will start a new
** column list.
**
** Set *pp to point to the byte just after the last byte written before
** returning (do not modify it if iCol==0). Return the total number of bytes
** written (0 if iCol==0).
*/
static int fts3PutColNumber(char **pp, int iCol){
int n = 0; /* Number of bytes written */
if( iCol ){
char *p = *pp; /* Output pointer */
n = 1 + sqlite3Fts3PutVarint(&p[1], iCol);
*p = 0x01;
*pp = &p[n];
}
return n;
}
/*
** Compute the union of two position lists. The output written
** into *pp contains all positions of both *pp1 and *pp2 in sorted
** order and with any duplicates removed. All pointers are
** updated appropriately. The caller is responsible for insuring
** that there is enough space in *pp to hold the complete output.
*/
static void fts3PoslistMerge(
char **pp, /* Output buffer */
char **pp1, /* Left input list */
char **pp2 /* Right input list */
){
char *p = *pp;
char *p1 = *pp1;
char *p2 = *pp2;
while( *p1 || *p2 ){
int iCol1; /* The current column index in pp1 */
int iCol2; /* The current column index in pp2 */
if( *p1==POS_COLUMN ) sqlite3Fts3GetVarint32(&p1[1], &iCol1);
else if( *p1==POS_END ) iCol1 = POSITION_LIST_END;
else iCol1 = 0;
if( *p2==POS_COLUMN ) sqlite3Fts3GetVarint32(&p2[1], &iCol2);
else if( *p2==POS_END ) iCol2 = POSITION_LIST_END;
else iCol2 = 0;
if( iCol1==iCol2 ){
sqlite3_int64 i1 = 0; /* Last position from pp1 */
sqlite3_int64 i2 = 0; /* Last position from pp2 */
sqlite3_int64 iPrev = 0;
int n = fts3PutColNumber(&p, iCol1);
p1 += n;
p2 += n;
/* At this point, both p1 and p2 point to the start of column-lists
** for the same column (the column with index iCol1 and iCol2).
** A column-list is a list of non-negative delta-encoded varints, each
** incremented by 2 before being stored. Each list is terminated by a
** POS_END (0) or POS_COLUMN (1). The following block merges the two lists
** and writes the results to buffer p. p is left pointing to the byte
** after the list written. No terminator (POS_END or POS_COLUMN) is
** written to the output.
*/
fts3GetDeltaVarint(&p1, &i1);
fts3GetDeltaVarint(&p2, &i2);
do {
fts3PutDeltaVarint(&p, &iPrev, (i1<i2) ? i1 : i2);
iPrev -= 2;
if( i1==i2 ){
fts3ReadNextPos(&p1, &i1);
fts3ReadNextPos(&p2, &i2);
}else if( i1<i2 ){
fts3ReadNextPos(&p1, &i1);
}else{
fts3ReadNextPos(&p2, &i2);
}
}while( i1!=POSITION_LIST_END || i2!=POSITION_LIST_END );
}else if( iCol1<iCol2 ){
p1 += fts3PutColNumber(&p, iCol1);
fts3ColumnlistCopy(&p, &p1);
}else{
p2 += fts3PutColNumber(&p, iCol2);
fts3ColumnlistCopy(&p, &p2);
}
}
*p++ = POS_END;
*pp = p;
*pp1 = p1 + 1;
*pp2 = p2 + 1;
}
/*
** nToken==1 searches for adjacent positions.
*/
static int fts3PoslistPhraseMerge(
char **pp, /* Output buffer */
int nToken, /* Maximum difference in token positions */
int isSaveLeft, /* Save the left position */
char **pp1, /* Left input list */
char **pp2 /* Right input list */
){
char *p = (pp ? *pp : 0);
char *p1 = *pp1;
char *p2 = *pp2;
int iCol1 = 0;
int iCol2 = 0;
assert( *p1!=0 && *p2!=0 );
if( *p1==POS_COLUMN ){
p1++;
p1 += sqlite3Fts3GetVarint32(p1, &iCol1);
}
if( *p2==POS_COLUMN ){
p2++;
p2 += sqlite3Fts3GetVarint32(p2, &iCol2);
}
while( 1 ){
if( iCol1==iCol2 ){
char *pSave = p;
sqlite3_int64 iPrev = 0;
sqlite3_int64 iPos1 = 0;
sqlite3_int64 iPos2 = 0;
if( pp && iCol1 ){
*p++ = POS_COLUMN;
p += sqlite3Fts3PutVarint(p, iCol1);
}
assert( *p1!=POS_END && *p1!=POS_COLUMN );
assert( *p2!=POS_END && *p2!=POS_COLUMN );
fts3GetDeltaVarint(&p1, &iPos1); iPos1 -= 2;
fts3GetDeltaVarint(&p2, &iPos2); iPos2 -= 2;
while( 1 ){
if( iPos2>iPos1 && iPos2<=iPos1+nToken ){
sqlite3_int64 iSave;
if( !pp ){
fts3PoslistCopy(0, &p2);
fts3PoslistCopy(0, &p1);
*pp1 = p1;
*pp2 = p2;
return 1;
}
iSave = isSaveLeft ? iPos1 : iPos2;
fts3PutDeltaVarint(&p, &iPrev, iSave+2); iPrev -= 2;
pSave = 0;
}
if( (!isSaveLeft && iPos2<=(iPos1+nToken)) || iPos2<=iPos1 ){
if( (*p2&0xFE)==0 ) break;
fts3GetDeltaVarint(&p2, &iPos2); iPos2 -= 2;
}else{
if( (*p1&0xFE)==0 ) break;
fts3GetDeltaVarint(&p1, &iPos1); iPos1 -= 2;
}
}
if( pSave ){
assert( pp && p );
p = pSave;
}
fts3ColumnlistCopy(0, &p1);
fts3ColumnlistCopy(0, &p2);
assert( (*p1&0xFE)==0 && (*p2&0xFE)==0 );
if( 0==*p1 || 0==*p2 ) break;
p1++;
p1 += sqlite3Fts3GetVarint32(p1, &iCol1);
p2++;
p2 += sqlite3Fts3GetVarint32(p2, &iCol2);
}
/* Advance pointer p1 or p2 (whichever corresponds to the smaller of
** iCol1 and iCol2) so that it points to either the 0x00 that marks the
** end of the position list, or the 0x01 that precedes the next
** column-number in the position list.
*/
else if( iCol1<iCol2 ){
fts3ColumnlistCopy(0, &p1);
if( 0==*p1 ) break;
p1++;
p1 += sqlite3Fts3GetVarint32(p1, &iCol1);
}else{
fts3ColumnlistCopy(0, &p2);
if( 0==*p2 ) break;
p2++;
p2 += sqlite3Fts3GetVarint32(p2, &iCol2);
}
}
fts3PoslistCopy(0, &p2);
fts3PoslistCopy(0, &p1);
*pp1 = p1;
*pp2 = p2;
if( !pp || *pp==p ){
return 0;
}
*p++ = 0x00;
*pp = p;
return 1;
}
/*
** Merge two position-lists as required by the NEAR operator.
*/
static int fts3PoslistNearMerge(
char **pp, /* Output buffer */
char *aTmp, /* Temporary buffer space */
int nRight, /* Maximum difference in token positions */
int nLeft, /* Maximum difference in token positions */
char **pp1, /* IN/OUT: Left input list */
char **pp2 /* IN/OUT: Right input list */
){
char *p1 = *pp1;
char *p2 = *pp2;
if( !pp ){
if( fts3PoslistPhraseMerge(0, nRight, 0, pp1, pp2) ) return 1;
*pp1 = p1;
*pp2 = p2;
return fts3PoslistPhraseMerge(0, nLeft, 0, pp2, pp1);
}else{
char *pTmp1 = aTmp;
char *pTmp2;
char *aTmp2;
int res = 1;
fts3PoslistPhraseMerge(&pTmp1, nRight, 0, pp1, pp2);
aTmp2 = pTmp2 = pTmp1;
*pp1 = p1;
*pp2 = p2;
fts3PoslistPhraseMerge(&pTmp2, nLeft, 1, pp2, pp1);
if( pTmp1!=aTmp && pTmp2!=aTmp2 ){
fts3PoslistMerge(pp, &aTmp, &aTmp2);
}else if( pTmp1!=aTmp ){
fts3PoslistCopy(pp, &aTmp);
}else if( pTmp2!=aTmp2 ){
fts3PoslistCopy(pp, &aTmp2);
}else{
res = 0;
}
return res;
}
}
/*
** Values that may be used as the first parameter to fts3DoclistMerge().
*/
#define MERGE_NOT 2 /* D + D -> D */
#define MERGE_AND 3 /* D + D -> D */
#define MERGE_OR 4 /* D + D -> D */
#define MERGE_POS_OR 5 /* P + P -> P */
#define MERGE_PHRASE 6 /* P + P -> D */
#define MERGE_POS_PHRASE 7 /* P + P -> P */
#define MERGE_NEAR 8 /* P + P -> D */
#define MERGE_POS_NEAR 9 /* P + P -> P */
/*
** Merge the two doclists passed in buffer a1 (size n1 bytes) and a2
** (size n2 bytes). The output is written to pre-allocated buffer aBuffer,
** which is guaranteed to be large enough to hold the results. The number
** of bytes written to aBuffer is stored in *pnBuffer before returning.
**
** If successful, SQLITE_OK is returned. Otherwise, if a malloc error
** occurs while allocating a temporary buffer as part of the merge operation,
** SQLITE_NOMEM is returned.
*/
static int fts3DoclistMerge(
int mergetype, /* One of the MERGE_XXX constants */
int nParam1, /* Used by MERGE_NEAR and MERGE_POS_NEAR */
int nParam2, /* Used by MERGE_NEAR and MERGE_POS_NEAR */
char *aBuffer, /* Pre-allocated output buffer */
int *pnBuffer, /* OUT: Bytes written to aBuffer */
char *a1, /* Buffer containing first doclist */
int n1, /* Size of buffer a1 */
char *a2, /* Buffer containing second doclist */
int n2 /* Size of buffer a2 */
){
sqlite3_int64 i1 = 0;
sqlite3_int64 i2 = 0;
sqlite3_int64 iPrev = 0;
char *p = aBuffer;
char *p1 = a1;
char *p2 = a2;
char *pEnd1 = &a1[n1];
char *pEnd2 = &a2[n2];
assert( mergetype==MERGE_OR || mergetype==MERGE_POS_OR
|| mergetype==MERGE_AND || mergetype==MERGE_NOT
|| mergetype==MERGE_PHRASE || mergetype==MERGE_POS_PHRASE
|| mergetype==MERGE_NEAR || mergetype==MERGE_POS_NEAR
);
if( !aBuffer ){
*pnBuffer = 0;
return SQLITE_NOMEM;
}
/* Read the first docid from each doclist */
fts3GetDeltaVarint2(&p1, pEnd1, &i1);
fts3GetDeltaVarint2(&p2, pEnd2, &i2);
switch( mergetype ){
case MERGE_OR:
case MERGE_POS_OR:
while( p1 || p2 ){
if( p2 && p1 && i1==i2 ){
fts3PutDeltaVarint(&p, &iPrev, i1);
if( mergetype==MERGE_POS_OR ) fts3PoslistMerge(&p, &p1, &p2);
fts3GetDeltaVarint2(&p1, pEnd1, &i1);
fts3GetDeltaVarint2(&p2, pEnd2, &i2);
}else if( !p2 || (p1 && i1<i2) ){
fts3PutDeltaVarint(&p, &iPrev, i1);
if( mergetype==MERGE_POS_OR ) fts3PoslistCopy(&p, &p1);
fts3GetDeltaVarint2(&p1, pEnd1, &i1);
}else{
fts3PutDeltaVarint(&p, &iPrev, i2);
if( mergetype==MERGE_POS_OR ) fts3PoslistCopy(&p, &p2);
fts3GetDeltaVarint2(&p2, pEnd2, &i2);
}
}
break;
case MERGE_AND:
while( p1 && p2 ){
if( i1==i2 ){
fts3PutDeltaVarint(&p, &iPrev, i1);
fts3GetDeltaVarint2(&p1, pEnd1, &i1);
fts3GetDeltaVarint2(&p2, pEnd2, &i2);
}else if( i1<i2 ){
fts3GetDeltaVarint2(&p1, pEnd1, &i1);
}else{
fts3GetDeltaVarint2(&p2, pEnd2, &i2);
}
}
break;
case MERGE_NOT:
while( p1 ){
if( p2 && i1==i2 ){
fts3GetDeltaVarint2(&p1, pEnd1, &i1);
fts3GetDeltaVarint2(&p2, pEnd2, &i2);
}else if( !p2 || i1<i2 ){
fts3PutDeltaVarint(&p, &iPrev, i1);
fts3GetDeltaVarint2(&p1, pEnd1, &i1);
}else{
fts3GetDeltaVarint2(&p2, pEnd2, &i2);
}
}
break;
case MERGE_POS_PHRASE:
case MERGE_PHRASE: {
char **ppPos = (mergetype==MERGE_PHRASE ? 0 : &p);
while( p1 && p2 ){
if( i1==i2 ){
char *pSave = p;
sqlite3_int64 iPrevSave = iPrev;
fts3PutDeltaVarint(&p, &iPrev, i1);
if( 0==fts3PoslistPhraseMerge(ppPos, 1, 0, &p1, &p2) ){
p = pSave;
iPrev = iPrevSave;
}
fts3GetDeltaVarint2(&p1, pEnd1, &i1);
fts3GetDeltaVarint2(&p2, pEnd2, &i2);
}else if( i1<i2 ){
fts3PoslistCopy(0, &p1);
fts3GetDeltaVarint2(&p1, pEnd1, &i1);
}else{
fts3PoslistCopy(0, &p2);
fts3GetDeltaVarint2(&p2, pEnd2, &i2);
}
}
break;
}
default: assert( mergetype==MERGE_POS_NEAR || mergetype==MERGE_NEAR ); {
char *aTmp = 0;
char **ppPos = 0;
if( mergetype==MERGE_POS_NEAR ){
ppPos = &p;
aTmp = sqlite3_malloc(2*(n1+n2+1));
if( !aTmp ){
return SQLITE_NOMEM;
}
}
while( p1 && p2 ){
if( i1==i2 ){
char *pSave = p;
sqlite3_int64 iPrevSave = iPrev;
fts3PutDeltaVarint(&p, &iPrev, i1);
if( !fts3PoslistNearMerge(ppPos, aTmp, nParam1, nParam2, &p1, &p2) ){
iPrev = iPrevSave;
p = pSave;
}
fts3GetDeltaVarint2(&p1, pEnd1, &i1);
fts3GetDeltaVarint2(&p2, pEnd2, &i2);
}else if( i1<i2 ){
fts3PoslistCopy(0, &p1);
fts3GetDeltaVarint2(&p1, pEnd1, &i1);
}else{
fts3PoslistCopy(0, &p2);
fts3GetDeltaVarint2(&p2, pEnd2, &i2);
}
}
sqlite3_free(aTmp);
break;
}
}
*pnBuffer = (int)(p-aBuffer);
return SQLITE_OK;
}
/*
** A pointer to an instance of this structure is used as the context
** argument to sqlite3Fts3SegReaderIterate()
*/
typedef struct TermSelect TermSelect;
struct TermSelect {
int isReqPos;
char *aOutput; /* Malloc'd output buffer */
int nOutput; /* Size of output in bytes */
};
/*
** This function is used as the sqlite3Fts3SegReaderIterate() callback when
** querying the full-text index for a doclist associated with a term or
** term-prefix.
*/
static int fts3TermSelectCb(
Fts3Table *p, /* Virtual table object */
void *pContext, /* Pointer to TermSelect structure */
char *zTerm,
int nTerm,
char *aDoclist,
int nDoclist
){
TermSelect *pTS = (TermSelect *)pContext;
int nNew = pTS->nOutput + nDoclist;
char *aNew = sqlite3_malloc(nNew);
UNUSED_PARAMETER(p);
UNUSED_PARAMETER(zTerm);
UNUSED_PARAMETER(nTerm);
if( !aNew ){
return SQLITE_NOMEM;
}
if( pTS->nOutput==0 ){
/* If this is the first term selected, copy the doclist to the output
** buffer using memcpy(). TODO: Add a way to transfer control of the
** aDoclist buffer from the caller so as to avoid the memcpy().
*/
memcpy(aNew, aDoclist, nDoclist);
}else{
/* The output buffer is not empty. Merge doclist aDoclist with the
** existing output. This can only happen with prefix-searches (as
** searches for exact terms return exactly one doclist).
*/
int mergetype = (pTS->isReqPos ? MERGE_POS_OR : MERGE_OR);
fts3DoclistMerge(mergetype, 0, 0,
aNew, &nNew, pTS->aOutput, pTS->nOutput, aDoclist, nDoclist
);
}
sqlite3_free(pTS->aOutput);
pTS->aOutput = aNew;
pTS->nOutput = nNew;
return SQLITE_OK;
}
/*
** This function retreives the doclist for the specified term (or term
** prefix) from the database.
**
** The returned doclist may be in one of two formats, depending on the
** value of parameter isReqPos. If isReqPos is zero, then the doclist is
** a sorted list of delta-compressed docids (a bare doclist). If isReqPos
** is non-zero, then the returned list is in the same format as is stored
** in the database without the found length specifier at the start of on-disk
** doclists.
*/
static int fts3TermSelect(
Fts3Table *p, /* Virtual table handle */
int iColumn, /* Column to query (or -ve for all columns) */
const char *zTerm, /* Term to query for */
int nTerm, /* Size of zTerm in bytes */
int isPrefix, /* True for a prefix search */
int isReqPos, /* True to include position lists in output */
int *pnOut, /* OUT: Size of buffer at *ppOut */
char **ppOut /* OUT: Malloced result buffer */
){
int i;
TermSelect tsc;
Fts3SegFilter filter; /* Segment term filter configuration */
Fts3SegReader **apSegment; /* Array of segments to read data from */
int nSegment = 0; /* Size of apSegment array */
int nAlloc = 16; /* Allocated size of segment array */
int rc; /* Return code */
sqlite3_stmt *pStmt = 0; /* SQL statement to scan %_segdir table */
int iAge = 0; /* Used to assign ages to segments */
apSegment = (Fts3SegReader **)sqlite3_malloc(sizeof(Fts3SegReader*)*nAlloc);
if( !apSegment ) return SQLITE_NOMEM;
rc = sqlite3Fts3SegReaderPending(p, zTerm, nTerm, isPrefix, &apSegment[0]);
if( rc!=SQLITE_OK ) goto finished;
if( apSegment[0] ){
nSegment = 1;
}
/* Loop through the entire %_segdir table. For each segment, create a
** Fts3SegReader to iterate through the subset of the segment leaves
** that may contain a term that matches zTerm/nTerm. For non-prefix
** searches, this is always a single leaf. For prefix searches, this
** may be a contiguous block of leaves.
**
** The code in this loop does not actually load any leaves into memory
** (unless the root node happens to be a leaf). It simply examines the
** b-tree structure to determine which leaves need to be inspected.
*/
rc = sqlite3Fts3AllSegdirs(p, &pStmt);
while( rc==SQLITE_OK && SQLITE_ROW==(rc = sqlite3_step(pStmt)) ){
Fts3SegReader *pNew = 0;
int nRoot = sqlite3_column_bytes(pStmt, 4);
char const *zRoot = sqlite3_column_blob(pStmt, 4);
if( sqlite3_column_int64(pStmt, 1)==0 ){
/* The entire segment is stored on the root node (which must be a
** leaf). Do not bother inspecting any data in this case, just
** create a Fts3SegReader to scan the single leaf.
*/
rc = sqlite3Fts3SegReaderNew(p, iAge, 0, 0, 0, zRoot, nRoot, &pNew);
}else{
int rc2; /* Return value of sqlite3Fts3ReadBlock() */
sqlite3_int64 i1; /* Blockid of leaf that may contain zTerm */
rc = fts3SelectLeaf(p, zTerm, nTerm, zRoot, nRoot, &i1);
if( rc==SQLITE_OK ){
sqlite3_int64 i2 = sqlite3_column_int64(pStmt, 2);
rc = sqlite3Fts3SegReaderNew(p, iAge, i1, i2, 0, 0, 0, &pNew);
}
/* The following call to ReadBlock() serves to reset the SQL statement
** used to retrieve blocks of data from the %_segments table. If it is
** not reset here, then it may remain classified as an active statement
** by SQLite, which may lead to "DROP TABLE" or "DETACH" commands
** failing.
*/
rc2 = sqlite3Fts3ReadBlock(p, 0, 0, 0);
if( rc==SQLITE_OK ){
rc = rc2;
}
}
iAge++;
/* If a new Fts3SegReader was allocated, add it to the apSegment array. */
assert( pNew!=0 || rc!=SQLITE_OK );
if( pNew ){
if( nSegment==nAlloc ){
Fts3SegReader **pArray;
nAlloc += 16;
pArray = (Fts3SegReader **)sqlite3_realloc(
apSegment, nAlloc*sizeof(Fts3SegReader *)
);
if( !pArray ){
sqlite3Fts3SegReaderFree(p, pNew);
rc = SQLITE_NOMEM;
goto finished;
}
apSegment = pArray;
}
apSegment[nSegment++] = pNew;
}
}
if( rc!=SQLITE_DONE ){
assert( rc!=SQLITE_OK );
goto finished;
}
memset(&tsc, 0, sizeof(TermSelect));
tsc.isReqPos = isReqPos;
filter.flags = FTS3_SEGMENT_IGNORE_EMPTY
| (isPrefix ? FTS3_SEGMENT_PREFIX : 0)
| (isReqPos ? FTS3_SEGMENT_REQUIRE_POS : 0)
| (iColumn<p->nColumn ? FTS3_SEGMENT_COLUMN_FILTER : 0);
filter.iCol = iColumn;
filter.zTerm = zTerm;
filter.nTerm = nTerm;
rc = sqlite3Fts3SegReaderIterate(p, apSegment, nSegment, &filter,
fts3TermSelectCb, (void *)&tsc
);
if( rc==SQLITE_OK ){
*ppOut = tsc.aOutput;
*pnOut = tsc.nOutput;
}else{
sqlite3_free(tsc.aOutput);
}
finished:
sqlite3_reset(pStmt);
for(i=0; i<nSegment; i++){
sqlite3Fts3SegReaderFree(p, apSegment[i]);
}
sqlite3_free(apSegment);
return rc;
}
/*
** Return a DocList corresponding to the phrase *pPhrase.
*/
static int fts3PhraseSelect(
Fts3Table *p, /* Virtual table handle */
Fts3Phrase *pPhrase, /* Phrase to return a doclist for */
int isReqPos, /* True if output should contain positions */
char **paOut, /* OUT: Pointer to malloc'd result buffer */
int *pnOut /* OUT: Size of buffer at *paOut */
){
char *pOut = 0;
int nOut = 0;
int rc = SQLITE_OK;
int ii;
int iCol = pPhrase->iColumn;
int isTermPos = (pPhrase->nToken>1 || isReqPos);
for(ii=0; ii<pPhrase->nToken; ii++){
struct PhraseToken *pTok = &pPhrase->aToken[ii];
char *z = pTok->z; /* Next token of the phrase */
int n = pTok->n; /* Size of z in bytes */
int isPrefix = pTok->isPrefix;/* True if token is a prefix */
char *pList; /* Pointer to token doclist */
int nList; /* Size of buffer at pList */
rc = fts3TermSelect(p, iCol, z, n, isPrefix, isTermPos, &nList, &pList);
if( rc!=SQLITE_OK ) break;
if( ii==0 ){
pOut = pList;
nOut = nList;
}else{
/* Merge the new term list and the current output. If this is the
** last term in the phrase, and positions are not required in the
** output of this function, the positions can be dropped as part
** of this merge. Either way, the result of this merge will be
** smaller than nList bytes. The code in fts3DoclistMerge() is written
** so that it is safe to use pList as the output as well as an input
** in this case.
*/
int mergetype = MERGE_POS_PHRASE;
if( ii==pPhrase->nToken-1 && !isReqPos ){
mergetype = MERGE_PHRASE;
}
fts3DoclistMerge(mergetype, 0, 0, pList, &nOut, pOut, nOut, pList, nList);
sqlite3_free(pOut);
pOut = pList;
}
assert( nOut==0 || pOut!=0 );
}
if( rc==SQLITE_OK ){
*paOut = pOut;
*pnOut = nOut;
}else{
sqlite3_free(pOut);
}
return rc;
}
static int fts3NearMerge(
int mergetype, /* MERGE_POS_NEAR or MERGE_NEAR */
int nNear, /* Parameter to NEAR operator */
int nTokenLeft, /* Number of tokens in LHS phrase arg */
char *aLeft, /* Doclist for LHS (incl. positions) */
int nLeft, /* Size of LHS doclist in bytes */
int nTokenRight, /* As nTokenLeft */
char *aRight, /* As aLeft */
int nRight, /* As nRight */
char **paOut, /* OUT: Results of merge (malloced) */
int *pnOut /* OUT: Sized of output buffer */
){
char *aOut;
int rc;
assert( mergetype==MERGE_POS_NEAR || MERGE_NEAR );
aOut = sqlite3_malloc(nLeft+nRight+1);
if( aOut==0 ){
rc = SQLITE_NOMEM;
}else{
rc = fts3DoclistMerge(mergetype, nNear+nTokenRight, nNear+nTokenLeft,
aOut, pnOut, aLeft, nLeft, aRight, nRight
);
if( rc!=SQLITE_OK ){
sqlite3_free(aOut);
aOut = 0;
}
}
*paOut = aOut;
return rc;
}
int sqlite3Fts3ExprNearTrim(Fts3Expr *pLeft, Fts3Expr *pRight, int nNear){
int rc;
if( pLeft->aDoclist==0 || pRight->aDoclist==0 ){
sqlite3_free(pLeft->aDoclist);
sqlite3_free(pRight->aDoclist);
pRight->aDoclist = 0;
pLeft->aDoclist = 0;
rc = SQLITE_OK;
}else{
char *aOut;
int nOut;
rc = fts3NearMerge(MERGE_POS_NEAR, nNear,
pLeft->pPhrase->nToken, pLeft->aDoclist, pLeft->nDoclist,
pRight->pPhrase->nToken, pRight->aDoclist, pRight->nDoclist,
&aOut, &nOut
);
if( rc!=SQLITE_OK ) return rc;
sqlite3_free(pRight->aDoclist);
pRight->aDoclist = aOut;
pRight->nDoclist = nOut;
rc = fts3NearMerge(MERGE_POS_NEAR, nNear,
pRight->pPhrase->nToken, pRight->aDoclist, pRight->nDoclist,
pLeft->pPhrase->nToken, pLeft->aDoclist, pLeft->nDoclist,
&aOut, &nOut
);
sqlite3_free(pLeft->aDoclist);
pLeft->aDoclist = aOut;
pLeft->nDoclist = nOut;
}
return rc;
}
/*
** Evaluate the full-text expression pExpr against fts3 table pTab. Store
** the resulting doclist in *paOut and *pnOut. This routine mallocs for
** the space needed to store the output. The caller is responsible for
** freeing the space when it has finished.
*/
static int evalFts3Expr(
Fts3Table *p, /* Virtual table handle */
Fts3Expr *pExpr, /* Parsed fts3 expression */
char **paOut, /* OUT: Pointer to malloc'd result buffer */
int *pnOut, /* OUT: Size of buffer at *paOut */
int isReqPos /* Require positions in output buffer */
){
int rc = SQLITE_OK; /* Return code */
/* Zero the output parameters. */
*paOut = 0;
*pnOut = 0;
if( pExpr ){
assert( pExpr->eType==FTSQUERY_PHRASE
|| pExpr->eType==FTSQUERY_NEAR
|| isReqPos==0
);
if( pExpr->eType==FTSQUERY_PHRASE ){
rc = fts3PhraseSelect(p, pExpr->pPhrase,
isReqPos || (pExpr->pParent && pExpr->pParent->eType==FTSQUERY_NEAR),
paOut, pnOut
);
}else{
char *aLeft;
char *aRight;
int nLeft;
int nRight;
if( 0==(rc = evalFts3Expr(p, pExpr->pRight, &aRight, &nRight, isReqPos))
&& 0==(rc = evalFts3Expr(p, pExpr->pLeft, &aLeft, &nLeft, isReqPos))
){
assert( pExpr->eType==FTSQUERY_NEAR || pExpr->eType==FTSQUERY_OR
|| pExpr->eType==FTSQUERY_AND || pExpr->eType==FTSQUERY_NOT
);
switch( pExpr->eType ){
case FTSQUERY_NEAR: {
Fts3Expr *pLeft;
Fts3Expr *pRight;
int mergetype = isReqPos ? MERGE_POS_NEAR : MERGE_NEAR;
if( pExpr->pParent && pExpr->pParent->eType==FTSQUERY_NEAR ){
mergetype = MERGE_POS_NEAR;
}
pLeft = pExpr->pLeft;
while( pLeft->eType==FTSQUERY_NEAR ){
pLeft=pLeft->pRight;
}
pRight = pExpr->pRight;
assert( pRight->eType==FTSQUERY_PHRASE );
assert( pLeft->eType==FTSQUERY_PHRASE );
rc = fts3NearMerge(mergetype, pExpr->nNear,
pLeft->pPhrase->nToken, aLeft, nLeft,
pRight->pPhrase->nToken, aRight, nRight,
paOut, pnOut
);
sqlite3_free(aLeft);
break;
}
case FTSQUERY_OR: {
/* Allocate a buffer for the output. The maximum size is the
** sum of the sizes of the two input buffers. The +1 term is
** so that a buffer of zero bytes is never allocated - this can
** cause fts3DoclistMerge() to incorrectly return SQLITE_NOMEM.
*/
char *aBuffer = sqlite3_malloc(nRight+nLeft+1);
rc = fts3DoclistMerge(MERGE_OR, 0, 0, aBuffer, pnOut,
aLeft, nLeft, aRight, nRight
);
*paOut = aBuffer;
sqlite3_free(aLeft);
break;
}
default: {
assert( FTSQUERY_NOT==MERGE_NOT && FTSQUERY_AND==MERGE_AND );
fts3DoclistMerge(pExpr->eType, 0, 0, aLeft, pnOut,
aLeft, nLeft, aRight, nRight
);
*paOut = aLeft;
break;
}
}
}
sqlite3_free(aRight);
}
}
return rc;
}
/*
** This is the xFilter interface for the virtual table. See
** the virtual table xFilter method documentation for additional
** information.
**
** If idxNum==FTS3_FULLSCAN_SEARCH then do a full table scan against
** the %_content table.
**
** If idxNum==FTS3_DOCID_SEARCH then do a docid lookup for a single entry
** in the %_content table.
**
** If idxNum>=FTS3_FULLTEXT_SEARCH then use the full text index. The
** column on the left-hand side of the MATCH operator is column
** number idxNum-FTS3_FULLTEXT_SEARCH, 0 indexed. argv[0] is the right-hand
** side of the MATCH operator.
*/
/* TODO(shess) Upgrade the cursor initialization and destruction to
** account for fts3FilterMethod() being called multiple times on the
** same cursor. The current solution is very fragile. Apply fix to
** fts3 as appropriate.
*/
static int fts3FilterMethod(
sqlite3_vtab_cursor *pCursor, /* The cursor used for this query */
int idxNum, /* Strategy index */
const char *idxStr, /* Unused */
int nVal, /* Number of elements in apVal */
sqlite3_value **apVal /* Arguments for the indexing scheme */
){
const char *azSql[] = {
"SELECT * FROM %Q.'%q_content' WHERE docid = ?", /* non-full-table-scan */
"SELECT * FROM %Q.'%q_content'", /* full-table-scan */
};
int rc; /* Return code */
char *zSql; /* SQL statement used to access %_content */
Fts3Table *p = (Fts3Table *)pCursor->pVtab;
Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;
UNUSED_PARAMETER(idxStr);
UNUSED_PARAMETER(nVal);
assert( idxNum>=0 && idxNum<=(FTS3_FULLTEXT_SEARCH+p->nColumn) );
assert( nVal==0 || nVal==1 );
assert( (nVal==0)==(idxNum==FTS3_FULLSCAN_SEARCH) );
/* In case the cursor has been used before, clear it now. */
sqlite3_finalize(pCsr->pStmt);
sqlite3_free(pCsr->aDoclist);
sqlite3Fts3ExprFree(pCsr->pExpr);
memset(&pCursor[1], 0, sizeof(Fts3Cursor)-sizeof(sqlite3_vtab_cursor));
/* Compile a SELECT statement for this cursor. For a full-table-scan, the
** statement loops through all rows of the %_content table. For a
** full-text query or docid lookup, the statement retrieves a single
** row by docid.
*/
zSql = sqlite3_mprintf(azSql[idxNum==FTS3_FULLSCAN_SEARCH], p->zDb, p->zName);
if( !zSql ){
rc = SQLITE_NOMEM;
}else{
rc = sqlite3_prepare_v2(p->db, zSql, -1, &pCsr->pStmt, 0);
sqlite3_free(zSql);
}
if( rc!=SQLITE_OK ) return rc;
pCsr->eSearch = (i16)idxNum;
if( idxNum==FTS3_DOCID_SEARCH ){
rc = sqlite3_bind_value(pCsr->pStmt, 1, apVal[0]);
}else if( idxNum!=FTS3_FULLSCAN_SEARCH ){
int iCol = idxNum-FTS3_FULLTEXT_SEARCH;
const char *zQuery = (const char *)sqlite3_value_text(apVal[0]);
if( zQuery==0 && sqlite3_value_type(apVal[0])!=SQLITE_NULL ){
return SQLITE_NOMEM;
}
rc = sqlite3Fts3ExprParse(p->pTokenizer, p->azColumn, p->nColumn,
iCol, zQuery, -1, &pCsr->pExpr
);
if( rc!=SQLITE_OK ){
if( rc==SQLITE_ERROR ){
p->base.zErrMsg = sqlite3_mprintf("malformed MATCH expression: [%s]",
zQuery);
}
return rc;
}
rc = evalFts3Expr(p, pCsr->pExpr, &pCsr->aDoclist, &pCsr->nDoclist, 0);
pCsr->pNextId = pCsr->aDoclist;
pCsr->iPrevId = 0;
}
if( rc!=SQLITE_OK ) return rc;
return fts3NextMethod(pCursor);
}
/*
** This is the xEof method of the virtual table. SQLite calls this
** routine to find out if it has reached the end of a result set.
*/
static int fts3EofMethod(sqlite3_vtab_cursor *pCursor){
return ((Fts3Cursor *)pCursor)->isEof;
}
/*
** This is the xRowid method. The SQLite core calls this routine to
** retrieve the rowid for the current row of the result set. fts3
** exposes %_content.docid as the rowid for the virtual table. The
** rowid should be written to *pRowid.
*/
static int fts3RowidMethod(sqlite3_vtab_cursor *pCursor, sqlite_int64 *pRowid){
Fts3Cursor *pCsr = (Fts3Cursor *) pCursor;
if( pCsr->aDoclist ){
*pRowid = pCsr->iPrevId;
}else{
*pRowid = sqlite3_column_int64(pCsr->pStmt, 0);
}
return SQLITE_OK;
}
/*
** This is the xColumn method, called by SQLite to request a value from
** the row that the supplied cursor currently points to.
*/
static int fts3ColumnMethod(
sqlite3_vtab_cursor *pCursor, /* Cursor to retrieve value from */
sqlite3_context *pContext, /* Context for sqlite3_result_xxx() calls */
int iCol /* Index of column to read value from */
){
int rc; /* Return Code */
Fts3Cursor *pCsr = (Fts3Cursor *) pCursor;
Fts3Table *p = (Fts3Table *)pCursor->pVtab;
/* The column value supplied by SQLite must be in range. */
assert( iCol>=0 && iCol<=p->nColumn+1 );
if( iCol==p->nColumn+1 ){
/* This call is a request for the "docid" column. Since "docid" is an
** alias for "rowid", use the xRowid() method to obtain the value.
*/
sqlite3_int64 iRowid;
rc = fts3RowidMethod(pCursor, &iRowid);
sqlite3_result_int64(pContext, iRowid);
}else if( iCol==p->nColumn ){
/* The extra column whose name is the same as the table.
** Return a blob which is a pointer to the cursor.
*/
sqlite3_result_blob(pContext, &pCsr, sizeof(pCsr), SQLITE_TRANSIENT);
rc = SQLITE_OK;
}else{
rc = fts3CursorSeek(0, pCsr);
if( rc==SQLITE_OK ){
sqlite3_result_value(pContext, sqlite3_column_value(pCsr->pStmt, iCol+1));
}
}
return rc;
}
/*
** This function is the implementation of the xUpdate callback used by
** FTS3 virtual tables. It is invoked by SQLite each time a row is to be
** inserted, updated or deleted.
*/
static int fts3UpdateMethod(
sqlite3_vtab *pVtab, /* Virtual table handle */
int nArg, /* Size of argument array */
sqlite3_value **apVal, /* Array of arguments */
sqlite_int64 *pRowid /* OUT: The affected (or effected) rowid */
){
return sqlite3Fts3UpdateMethod(pVtab, nArg, apVal, pRowid);
}
/*
** Implementation of xSync() method. Flush the contents of the pending-terms
** hash-table to the database.
*/
static int fts3SyncMethod(sqlite3_vtab *pVtab){
return sqlite3Fts3PendingTermsFlush((Fts3Table *)pVtab);
}
/*
** Implementation of xBegin() method. This is a no-op.
*/
static int fts3BeginMethod(sqlite3_vtab *pVtab){
UNUSED_PARAMETER(pVtab);
assert( ((Fts3Table *)pVtab)->nPendingData==0 );
return SQLITE_OK;
}
/*
** Implementation of xCommit() method. This is a no-op. The contents of
** the pending-terms hash-table have already been flushed into the database
** by fts3SyncMethod().
*/
static int fts3CommitMethod(sqlite3_vtab *pVtab){
UNUSED_PARAMETER(pVtab);
assert( ((Fts3Table *)pVtab)->nPendingData==0 );
return SQLITE_OK;
}
/*
** Implementation of xRollback(). Discard the contents of the pending-terms
** hash-table. Any changes made to the database are reverted by SQLite.
*/
static int fts3RollbackMethod(sqlite3_vtab *pVtab){
sqlite3Fts3PendingTermsClear((Fts3Table *)pVtab);
return SQLITE_OK;
}
/*
** Load the doclist associated with expression pExpr to pExpr->aDoclist.
** The loaded doclist contains positions as well as the document ids.
** This is used by the matchinfo(), snippet() and offsets() auxillary
** functions.
*/
int sqlite3Fts3ExprLoadDoclist(Fts3Table *pTab, Fts3Expr *pExpr){
return evalFts3Expr(pTab, pExpr, &pExpr->aDoclist, &pExpr->nDoclist, 1);
}
/*
** After ExprLoadDoclist() (see above) has been called, this function is
** used to iterate/search through the position lists that make up the doclist
** stored in pExpr->aDoclist.
*/
char *sqlite3Fts3FindPositions(
Fts3Expr *pExpr, /* Access this expressions doclist */
sqlite3_int64 iDocid, /* Docid associated with requested pos-list */
int iCol /* Column of requested pos-list */
){
assert( pExpr->isLoaded );
if( pExpr->aDoclist ){
char *pEnd = &pExpr->aDoclist[pExpr->nDoclist];
char *pCsr = pExpr->pCurrent;
assert( pCsr );
while( pCsr<pEnd ){
if( pExpr->iCurrent<iDocid ){
fts3PoslistCopy(0, &pCsr);
if( pCsr<pEnd ){
fts3GetDeltaVarint(&pCsr, &pExpr->iCurrent);
}
pExpr->pCurrent = pCsr;
}else{
if( pExpr->iCurrent==iDocid ){
int iThis = 0;
if( iCol<0 ){
/* If iCol is negative, return a pointer to the start of the
** position-list (instead of a pointer to the start of a list
** of offsets associated with a specific column).
*/
return pCsr;
}
while( iThis<iCol ){
fts3ColumnlistCopy(0, &pCsr);
if( *pCsr==0x00 ) return 0;
pCsr++;
pCsr += sqlite3Fts3GetVarint32(pCsr, &iThis);
}
if( iCol==iThis && (*pCsr&0xFE) ) return pCsr;
}
return 0;
}
}
}
return 0;
}
/*
** Helper function used by the implementation of the overloaded snippet(),
** offsets() and optimize() SQL functions.
**
** If the value passed as the third argument is a blob of size
** sizeof(Fts3Cursor*), then the blob contents are copied to the
** output variable *ppCsr and SQLITE_OK is returned. Otherwise, an error
** message is written to context pContext and SQLITE_ERROR returned. The
** string passed via zFunc is used as part of the error message.
*/
static int fts3FunctionArg(
sqlite3_context *pContext, /* SQL function call context */
const char *zFunc, /* Function name */
sqlite3_value *pVal, /* argv[0] passed to function */
Fts3Cursor **ppCsr /* OUT: Store cursor handle here */
){
Fts3Cursor *pRet;
if( sqlite3_value_type(pVal)!=SQLITE_BLOB
|| sqlite3_value_bytes(pVal)!=sizeof(Fts3Cursor *)
){
char *zErr = sqlite3_mprintf("illegal first argument to %s", zFunc);
sqlite3_result_error(pContext, zErr, -1);
sqlite3_free(zErr);
return SQLITE_ERROR;
}
memcpy(&pRet, sqlite3_value_blob(pVal), sizeof(Fts3Cursor *));
*ppCsr = pRet;
return SQLITE_OK;
}
/*
** Implementation of the snippet() function for FTS3
*/
static void fts3SnippetFunc(
sqlite3_context *pContext, /* SQLite function call context */
int nVal, /* Size of apVal[] array */
sqlite3_value **apVal /* Array of arguments */
){
Fts3Cursor *pCsr; /* Cursor handle passed through apVal[0] */
const char *zStart = "<b>";
const char *zEnd = "</b>";
const char *zEllipsis = "<b>...</b>";
int iCol = -1;
int nToken = 15; /* Default number of tokens in snippet */
/* There must be at least one argument passed to this function (otherwise
** the non-overloaded version would have been called instead of this one).
*/
assert( nVal>=1 );
if( nVal>6 ){
sqlite3_result_error(pContext,
"wrong number of arguments to function snippet()", -1);
return;
}
if( fts3FunctionArg(pContext, "snippet", apVal[0], &pCsr) ) return;
switch( nVal ){
case 6: nToken = sqlite3_value_int(apVal[5]);
case 5: iCol = sqlite3_value_int(apVal[4]);
case 4: zEllipsis = (const char*)sqlite3_value_text(apVal[3]);
case 3: zEnd = (const char*)sqlite3_value_text(apVal[2]);
case 2: zStart = (const char*)sqlite3_value_text(apVal[1]);
}
if( !zEllipsis || !zEnd || !zStart ){
sqlite3_result_error_nomem(pContext);
}else if( SQLITE_OK==fts3CursorSeek(pContext, pCsr) ){
sqlite3Fts3Snippet(pContext, pCsr, zStart, zEnd, zEllipsis, iCol, nToken);
}
}
/*
** Implementation of the offsets() function for FTS3
*/
static void fts3OffsetsFunc(
sqlite3_context *pContext, /* SQLite function call context */
int nVal, /* Size of argument array */
sqlite3_value **apVal /* Array of arguments */
){
Fts3Cursor *pCsr; /* Cursor handle passed through apVal[0] */
UNUSED_PARAMETER(nVal);
assert( nVal==1 );
if( fts3FunctionArg(pContext, "offsets", apVal[0], &pCsr) ) return;
assert( pCsr );
if( SQLITE_OK==fts3CursorSeek(pContext, pCsr) ){
sqlite3Fts3Offsets(pContext, pCsr);
}
}
/*
** Implementation of the special optimize() function for FTS3. This
** function merges all segments in the database to a single segment.
** Example usage is:
**
** SELECT optimize(t) FROM t LIMIT 1;
**
** where 't' is the name of an FTS3 table.
*/
static void fts3OptimizeFunc(
sqlite3_context *pContext, /* SQLite function call context */
int nVal, /* Size of argument array */
sqlite3_value **apVal /* Array of arguments */
){
int rc; /* Return code */
Fts3Table *p; /* Virtual table handle */
Fts3Cursor *pCursor; /* Cursor handle passed through apVal[0] */
UNUSED_PARAMETER(nVal);
assert( nVal==1 );
if( fts3FunctionArg(pContext, "optimize", apVal[0], &pCursor) ) return;
p = (Fts3Table *)pCursor->base.pVtab;
assert( p );
rc = sqlite3Fts3Optimize(p);
switch( rc ){
case SQLITE_OK:
sqlite3_result_text(pContext, "Index optimized", -1, SQLITE_STATIC);
break;
case SQLITE_DONE:
sqlite3_result_text(pContext, "Index already optimal", -1, SQLITE_STATIC);
break;
default:
sqlite3_result_error_code(pContext, rc);
break;
}
}
/*
** Implementation of the matchinfo() function for FTS3
*/
static void fts3MatchinfoFunc(
sqlite3_context *pContext, /* SQLite function call context */
int nVal, /* Size of argument array */
sqlite3_value **apVal /* Array of arguments */
){
Fts3Cursor *pCsr; /* Cursor handle passed through apVal[0] */
if( nVal!=1 ){
sqlite3_result_error(pContext,
"wrong number of arguments to function matchinfo()", -1);
return;
}
if( SQLITE_OK==fts3FunctionArg(pContext, "matchinfo", apVal[0], &pCsr) ){
sqlite3Fts3Matchinfo(pContext, pCsr);
}
}
/*
** This routine implements the xFindFunction method for the FTS3
** virtual table.
*/
static int fts3FindFunctionMethod(
sqlite3_vtab *pVtab, /* Virtual table handle */
int nArg, /* Number of SQL function arguments */
const char *zName, /* Name of SQL function */
void (**pxFunc)(sqlite3_context*,int,sqlite3_value**), /* OUT: Result */
void **ppArg /* Unused */
){
struct Overloaded {
const char *zName;
void (*xFunc)(sqlite3_context*,int,sqlite3_value**);
} aOverload[] = {
{ "snippet", fts3SnippetFunc },
{ "offsets", fts3OffsetsFunc },
{ "optimize", fts3OptimizeFunc },
{ "matchinfo", fts3MatchinfoFunc },
};
int i; /* Iterator variable */
UNUSED_PARAMETER(pVtab);
UNUSED_PARAMETER(nArg);
UNUSED_PARAMETER(ppArg);
for(i=0; i<SizeofArray(aOverload); i++){
if( strcmp(zName, aOverload[i].zName)==0 ){
*pxFunc = aOverload[i].xFunc;
return 1;
}
}
/* No function of the specified name was found. Return 0. */
return 0;
}
/*
** Implementation of FTS3 xRename method. Rename an fts3 table.
*/
static int fts3RenameMethod(
sqlite3_vtab *pVtab, /* Virtual table handle */
const char *zName /* New name of table */
){
Fts3Table *p = (Fts3Table *)pVtab;
sqlite3 *db; /* Database connection */
int rc; /* Return Code */
db = p->db;
rc = SQLITE_OK;
fts3DbExec(&rc, db,
"ALTER TABLE %Q.'%q_content' RENAME TO '%q_content';",
p->zDb, p->zName, zName
);
if( rc==SQLITE_ERROR ) rc = SQLITE_OK;
if( p->bHasDocsize ){
fts3DbExec(&rc, db,
"ALTER TABLE %Q.'%q_docsize' RENAME TO '%q_docsize';",
p->zDb, p->zName, zName
);
fts3DbExec(&rc, db,
"ALTER TABLE %Q.'%q_stat' RENAME TO '%q_stat';",
p->zDb, p->zName, zName
);
}
fts3DbExec(&rc, db,
"ALTER TABLE %Q.'%q_segments' RENAME TO '%q_segments';",
p->zDb, p->zName, zName
);
fts3DbExec(&rc, db,
"ALTER TABLE %Q.'%q_segdir' RENAME TO '%q_segdir';",
p->zDb, p->zName, zName
);
return rc;
}
static const sqlite3_module fts3Module = {
/* iVersion */ 0,
/* xCreate */ fts3CreateMethod,
/* xConnect */ fts3ConnectMethod,
/* xBestIndex */ fts3BestIndexMethod,
/* xDisconnect */ fts3DisconnectMethod,
/* xDestroy */ fts3DestroyMethod,
/* xOpen */ fts3OpenMethod,
/* xClose */ fulltextClose,
/* xFilter */ fts3FilterMethod,
/* xNext */ fts3NextMethod,
/* xEof */ fts3EofMethod,
/* xColumn */ fts3ColumnMethod,
/* xRowid */ fts3RowidMethod,
/* xUpdate */ fts3UpdateMethod,
/* xBegin */ fts3BeginMethod,
/* xSync */ fts3SyncMethod,
/* xCommit */ fts3CommitMethod,
/* xRollback */ fts3RollbackMethod,
/* xFindFunction */ fts3FindFunctionMethod,
/* xRename */ fts3RenameMethod,
};
/*
** This function is registered as the module destructor (called when an
** FTS3 enabled database connection is closed). It frees the memory
** allocated for the tokenizer hash table.
*/
static void hashDestroy(void *p){
Fts3Hash *pHash = (Fts3Hash *)p;
sqlite3Fts3HashClear(pHash);
sqlite3_free(pHash);
}
/*
** The fts3 built-in tokenizers - "simple" and "porter" - are implemented
** in files fts3_tokenizer1.c and fts3_porter.c respectively. The following
** two forward declarations are for functions declared in these files
** used to retrieve the respective implementations.
**
** Calling sqlite3Fts3SimpleTokenizerModule() sets the value pointed
** to by the argument to point a the "simple" tokenizer implementation.
** Function ...PorterTokenizerModule() sets *pModule to point to the
** porter tokenizer/stemmer implementation.
*/
void sqlite3Fts3SimpleTokenizerModule(sqlite3_tokenizer_module const**ppModule);
void sqlite3Fts3PorterTokenizerModule(sqlite3_tokenizer_module const**ppModule);
void sqlite3Fts3IcuTokenizerModule(sqlite3_tokenizer_module const**ppModule);
/*
** Initialise the fts3 extension. If this extension is built as part
** of the sqlite library, then this function is called directly by
** SQLite. If fts3 is built as a dynamically loadable extension, this
** function is called by the sqlite3_extension_init() entry point.
*/
int sqlite3Fts3Init(sqlite3 *db){
int rc = SQLITE_OK;
Fts3Hash *pHash = 0;
const sqlite3_tokenizer_module *pSimple = 0;
const sqlite3_tokenizer_module *pPorter = 0;
#ifdef SQLITE_ENABLE_ICU
const sqlite3_tokenizer_module *pIcu = 0;
sqlite3Fts3IcuTokenizerModule(&pIcu);
#endif
sqlite3Fts3SimpleTokenizerModule(&pSimple);
sqlite3Fts3PorterTokenizerModule(&pPorter);
/* Allocate and initialise the hash-table used to store tokenizers. */
pHash = sqlite3_malloc(sizeof(Fts3Hash));
if( !pHash ){
rc = SQLITE_NOMEM;
}else{
sqlite3Fts3HashInit(pHash, FTS3_HASH_STRING, 1);
}
/* Load the built-in tokenizers into the hash table */
if( rc==SQLITE_OK ){
if( sqlite3Fts3HashInsert(pHash, "simple", 7, (void *)pSimple)
|| sqlite3Fts3HashInsert(pHash, "porter", 7, (void *)pPorter)
#ifdef SQLITE_ENABLE_ICU
|| (pIcu && sqlite3Fts3HashInsert(pHash, "icu", 4, (void *)pIcu))
#endif
){
rc = SQLITE_NOMEM;
}
}
#ifdef SQLITE_TEST
if( rc==SQLITE_OK ){
rc = sqlite3Fts3ExprInitTestInterface(db);
}
#endif
/* Create the virtual table wrapper around the hash-table and overload
** the two scalar functions. If this is successful, register the
** module with sqlite.
*/
if( SQLITE_OK==rc
&& SQLITE_OK==(rc = sqlite3Fts3InitHashTable(db, pHash, "fts3_tokenizer"))
&& SQLITE_OK==(rc = sqlite3_overload_function(db, "snippet", -1))
&& SQLITE_OK==(rc = sqlite3_overload_function(db, "offsets", 1))
&& SQLITE_OK==(rc = sqlite3_overload_function(db, "matchinfo", -1))
&& SQLITE_OK==(rc = sqlite3_overload_function(db, "optimize", 1))
){
rc = sqlite3_create_module_v2(
db, "fts3", &fts3Module, (void *)pHash, hashDestroy
);
if( rc==SQLITE_OK ){
rc = sqlite3_create_module_v2(
db, "fts4", &fts3Module, (void *)pHash, 0
);
}
return rc;
}
/* An error has occurred. Delete the hash table and return the error code. */
assert( rc!=SQLITE_OK );
if( pHash ){
sqlite3Fts3HashClear(pHash);
sqlite3_free(pHash);
}
return rc;
}
#if !SQLITE_CORE
int sqlite3_extension_init(
sqlite3 *db,
char **pzErrMsg,
const sqlite3_api_routines *pApi
){
SQLITE_EXTENSION_INIT2(pApi)
return sqlite3Fts3Init(db);
}
#endif
#endif