/* ** 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 #include #include #include #include #include #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>= 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; iaStmt); i++){ sqlite3_finalize(p->aStmt[i]); } for(i=0; inLeavesStmt; 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 && inColumn; 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 && inColumn; 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; idb = 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; iazColumn[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; inConstraint; 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( zCsrnAlloc ){ 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, (i1iPos1 && 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 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 && i1isReqPos ? MERGE_POS_OR : MERGE_OR); char *aOut = 0; int nOut = 0; int i; /* Loop through the doclists in the aaOutput[] array. Merge them all ** into a single doclist. */ for(i=0; iaaOutput); i++){ if( pTS->aaOutput[i] ){ if( !aOut ){ aOut = pTS->aaOutput[i]; nOut = pTS->anOutput[i]; pTS->aaOutput[0] = 0; }else{ int nNew = nOut + pTS->anOutput[i]; char *aNew = sqlite3_malloc(nNew); if( !aNew ){ sqlite3_free(aOut); return SQLITE_NOMEM; } fts3DoclistMerge(mergetype, 0, 0, aNew, &nNew, pTS->aaOutput[i], pTS->anOutput[i], aOut, nOut ); sqlite3_free(pTS->aaOutput[i]); sqlite3_free(aOut); pTS->aaOutput[i] = 0; aOut = aNew; nOut = nNew; } } } pTS->aaOutput[0] = aOut; pTS->anOutput[0] = nOut; return SQLITE_OK; } /* ** This function is used as the sqlite3Fts3SegReaderIterate() callback when ** querying the full-text index for a doclist associated with a term or ** term-prefix. */ static int fts3TermSelectCb( Fts3Table *p, /* Virtual table object */ void *pContext, /* Pointer to TermSelect structure */ char *zTerm, int nTerm, char *aDoclist, int nDoclist ){ TermSelect *pTS = (TermSelect *)pContext; UNUSED_PARAMETER(p); UNUSED_PARAMETER(zTerm); UNUSED_PARAMETER(nTerm); if( pTS->aaOutput[0]==0 ){ /* If this is the first term selected, copy the doclist to the output ** buffer using memcpy(). TODO: Add a way to transfer control of the ** aDoclist buffer from the caller so as to avoid the memcpy(). */ pTS->aaOutput[0] = sqlite3_malloc(nDoclist); pTS->anOutput[0] = nDoclist; if( pTS->aaOutput[0] ){ memcpy(pTS->aaOutput[0], aDoclist, nDoclist); }else{ return SQLITE_NOMEM; } }else{ int mergetype = (pTS->isReqPos ? MERGE_POS_OR : MERGE_OR); char *aMerge = aDoclist; int nMerge = nDoclist; int iOut; for(iOut=0; iOutaaOutput); iOut++){ char *aNew; int nNew; if( pTS->aaOutput[iOut]==0 ){ assert( iOut>0 ); pTS->aaOutput[iOut] = aMerge; pTS->anOutput[iOut] = nMerge; break; } nNew = nMerge + pTS->anOutput[iOut]; aNew = sqlite3_malloc(nNew); if( !aNew ){ if( aMerge!=aDoclist ){ sqlite3_free(aMerge); } return SQLITE_NOMEM; } fts3DoclistMerge(mergetype, 0, 0, aNew, &nNew, pTS->aaOutput[iOut], pTS->anOutput[iOut], aMerge, nMerge ); if( iOut>0 ) sqlite3_free(aMerge); sqlite3_free(pTS->aaOutput[iOut]); pTS->aaOutput[iOut] = 0; aMerge = aNew; nMerge = nNew; if( (iOut+1)==SizeofArray(pTS->aaOutput) ){ pTS->aaOutput[iOut] = aMerge; pTS->anOutput[iOut] = nMerge; } } } return SQLITE_OK; } /* ** 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) | (iColumnnColumn ? 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 ){ rc = fts3TermSelectMerge(&tsc); } if( rc==SQLITE_OK ){ *ppOut = tsc.aaOutput[0]; *pnOut = tsc.anOutput[0]; }else{ for(i=0; iiColumn; int isTermPos = (pPhrase->nToken>1 || isReqPos); for(ii=0; iinToken; 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( pCsriCurrentiCurrent); } 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=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; idb; 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 to 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