1: /*
2: ** 2006 Oct 10
3: **
4: ** The author disclaims copyright to this source code. In place of
5: ** a legal notice, here is a blessing:
6: **
7: ** May you do good and not evil.
8: ** May you find forgiveness for yourself and forgive others.
9: ** May you share freely, never taking more than you give.
10: **
11: ******************************************************************************
12: **
13: ** This is an SQLite module implementing full-text search.
14: */
15:
16: /*
17: ** The code in this file is only compiled if:
18: **
19: ** * The FTS3 module is being built as an extension
20: ** (in which case SQLITE_CORE is not defined), or
21: **
22: ** * The FTS3 module is being built into the core of
23: ** SQLite (in which case SQLITE_ENABLE_FTS3 is defined).
24: */
25:
26: /* The full-text index is stored in a series of b+tree (-like)
27: ** structures called segments which map terms to doclists. The
28: ** structures are like b+trees in layout, but are constructed from the
29: ** bottom up in optimal fashion and are not updatable. Since trees
30: ** are built from the bottom up, things will be described from the
31: ** bottom up.
32: **
33: **
34: **** Varints ****
35: ** The basic unit of encoding is a variable-length integer called a
36: ** varint. We encode variable-length integers in little-endian order
37: ** using seven bits * per byte as follows:
38: **
39: ** KEY:
40: ** A = 0xxxxxxx 7 bits of data and one flag bit
41: ** B = 1xxxxxxx 7 bits of data and one flag bit
42: **
43: ** 7 bits - A
44: ** 14 bits - BA
45: ** 21 bits - BBA
46: ** and so on.
47: **
48: ** This is similar in concept to how sqlite encodes "varints" but
49: ** the encoding is not the same. SQLite varints are big-endian
50: ** are are limited to 9 bytes in length whereas FTS3 varints are
51: ** little-endian and can be up to 10 bytes in length (in theory).
52: **
53: ** Example encodings:
54: **
55: ** 1: 0x01
56: ** 127: 0x7f
57: ** 128: 0x81 0x00
58: **
59: **
60: **** Document lists ****
61: ** A doclist (document list) holds a docid-sorted list of hits for a
62: ** given term. Doclists hold docids and associated token positions.
63: ** A docid is the unique integer identifier for a single document.
64: ** A position is the index of a word within the document. The first
65: ** word of the document has a position of 0.
66: **
67: ** FTS3 used to optionally store character offsets using a compile-time
68: ** option. But that functionality is no longer supported.
69: **
70: ** A doclist is stored like this:
71: **
72: ** array {
73: ** varint docid;
74: ** array { (position list for column 0)
75: ** varint position; (2 more than the delta from previous position)
76: ** }
77: ** array {
78: ** varint POS_COLUMN; (marks start of position list for new column)
79: ** varint column; (index of new column)
80: ** array {
81: ** varint position; (2 more than the delta from previous position)
82: ** }
83: ** }
84: ** varint POS_END; (marks end of positions for this document.
85: ** }
86: **
87: ** Here, array { X } means zero or more occurrences of X, adjacent in
88: ** memory. A "position" is an index of a token in the token stream
89: ** generated by the tokenizer. Note that POS_END and POS_COLUMN occur
90: ** in the same logical place as the position element, and act as sentinals
91: ** ending a position list array. POS_END is 0. POS_COLUMN is 1.
92: ** The positions numbers are not stored literally but rather as two more
93: ** than the difference from the prior position, or the just the position plus
94: ** 2 for the first position. Example:
95: **
96: ** label: A B C D E F G H I J K
97: ** value: 123 5 9 1 1 14 35 0 234 72 0
98: **
99: ** The 123 value is the first docid. For column zero in this document
100: ** there are two matches at positions 3 and 10 (5-2 and 9-2+3). The 1
101: ** at D signals the start of a new column; the 1 at E indicates that the
102: ** new column is column number 1. There are two positions at 12 and 45
103: ** (14-2 and 35-2+12). The 0 at H indicate the end-of-document. The
104: ** 234 at I is the next docid. It has one position 72 (72-2) and then
105: ** terminates with the 0 at K.
106: **
107: ** A "position-list" is the list of positions for multiple columns for
108: ** a single docid. A "column-list" is the set of positions for a single
109: ** column. Hence, a position-list consists of one or more column-lists,
110: ** a document record consists of a docid followed by a position-list and
111: ** a doclist consists of one or more document records.
112: **
113: ** A bare doclist omits the position information, becoming an
114: ** array of varint-encoded docids.
115: **
116: **** Segment leaf nodes ****
117: ** Segment leaf nodes store terms and doclists, ordered by term. Leaf
118: ** nodes are written using LeafWriter, and read using LeafReader (to
119: ** iterate through a single leaf node's data) and LeavesReader (to
120: ** iterate through a segment's entire leaf layer). Leaf nodes have
121: ** the format:
122: **
123: ** varint iHeight; (height from leaf level, always 0)
124: ** varint nTerm; (length of first term)
125: ** char pTerm[nTerm]; (content of first term)
126: ** varint nDoclist; (length of term's associated doclist)
127: ** char pDoclist[nDoclist]; (content of doclist)
128: ** array {
129: ** (further terms are delta-encoded)
130: ** varint nPrefix; (length of prefix shared with previous term)
131: ** varint nSuffix; (length of unshared suffix)
132: ** char pTermSuffix[nSuffix];(unshared suffix of next term)
133: ** varint nDoclist; (length of term's associated doclist)
134: ** char pDoclist[nDoclist]; (content of doclist)
135: ** }
136: **
137: ** Here, array { X } means zero or more occurrences of X, adjacent in
138: ** memory.
139: **
140: ** Leaf nodes are broken into blocks which are stored contiguously in
141: ** the %_segments table in sorted order. This means that when the end
142: ** of a node is reached, the next term is in the node with the next
143: ** greater node id.
144: **
145: ** New data is spilled to a new leaf node when the current node
146: ** exceeds LEAF_MAX bytes (default 2048). New data which itself is
147: ** larger than STANDALONE_MIN (default 1024) is placed in a standalone
148: ** node (a leaf node with a single term and doclist). The goal of
149: ** these settings is to pack together groups of small doclists while
150: ** making it efficient to directly access large doclists. The
151: ** assumption is that large doclists represent terms which are more
152: ** likely to be query targets.
153: **
154: ** TODO(shess) It may be useful for blocking decisions to be more
155: ** dynamic. For instance, it may make more sense to have a 2.5k leaf
156: ** node rather than splitting into 2k and .5k nodes. My intuition is
157: ** that this might extend through 2x or 4x the pagesize.
158: **
159: **
160: **** Segment interior nodes ****
161: ** Segment interior nodes store blockids for subtree nodes and terms
162: ** to describe what data is stored by the each subtree. Interior
163: ** nodes are written using InteriorWriter, and read using
164: ** InteriorReader. InteriorWriters are created as needed when
165: ** SegmentWriter creates new leaf nodes, or when an interior node
166: ** itself grows too big and must be split. The format of interior
167: ** nodes:
168: **
169: ** varint iHeight; (height from leaf level, always >0)
170: ** varint iBlockid; (block id of node's leftmost subtree)
171: ** optional {
172: ** varint nTerm; (length of first term)
173: ** char pTerm[nTerm]; (content of first term)
174: ** array {
175: ** (further terms are delta-encoded)
176: ** varint nPrefix; (length of shared prefix with previous term)
177: ** varint nSuffix; (length of unshared suffix)
178: ** char pTermSuffix[nSuffix]; (unshared suffix of next term)
179: ** }
180: ** }
181: **
182: ** Here, optional { X } means an optional element, while array { X }
183: ** means zero or more occurrences of X, adjacent in memory.
184: **
185: ** An interior node encodes n terms separating n+1 subtrees. The
186: ** subtree blocks are contiguous, so only the first subtree's blockid
187: ** is encoded. The subtree at iBlockid will contain all terms less
188: ** than the first term encoded (or all terms if no term is encoded).
189: ** Otherwise, for terms greater than or equal to pTerm[i] but less
190: ** than pTerm[i+1], the subtree for that term will be rooted at
191: ** iBlockid+i. Interior nodes only store enough term data to
192: ** distinguish adjacent children (if the rightmost term of the left
193: ** child is "something", and the leftmost term of the right child is
194: ** "wicked", only "w" is stored).
195: **
196: ** New data is spilled to a new interior node at the same height when
197: ** the current node exceeds INTERIOR_MAX bytes (default 2048).
198: ** INTERIOR_MIN_TERMS (default 7) keeps large terms from monopolizing
199: ** interior nodes and making the tree too skinny. The interior nodes
200: ** at a given height are naturally tracked by interior nodes at
201: ** height+1, and so on.
202: **
203: **
204: **** Segment directory ****
205: ** The segment directory in table %_segdir stores meta-information for
206: ** merging and deleting segments, and also the root node of the
207: ** segment's tree.
208: **
209: ** The root node is the top node of the segment's tree after encoding
210: ** the entire segment, restricted to ROOT_MAX bytes (default 1024).
211: ** This could be either a leaf node or an interior node. If the top
212: ** node requires more than ROOT_MAX bytes, it is flushed to %_segments
213: ** and a new root interior node is generated (which should always fit
214: ** within ROOT_MAX because it only needs space for 2 varints, the
215: ** height and the blockid of the previous root).
216: **
217: ** The meta-information in the segment directory is:
218: ** level - segment level (see below)
219: ** idx - index within level
220: ** - (level,idx uniquely identify a segment)
221: ** start_block - first leaf node
222: ** leaves_end_block - last leaf node
223: ** end_block - last block (including interior nodes)
224: ** root - contents of root node
225: **
226: ** If the root node is a leaf node, then start_block,
227: ** leaves_end_block, and end_block are all 0.
228: **
229: **
230: **** Segment merging ****
231: ** To amortize update costs, segments are grouped into levels and
232: ** merged in batches. Each increase in level represents exponentially
233: ** more documents.
234: **
235: ** New documents (actually, document updates) are tokenized and
236: ** written individually (using LeafWriter) to a level 0 segment, with
237: ** incrementing idx. When idx reaches MERGE_COUNT (default 16), all
238: ** level 0 segments are merged into a single level 1 segment. Level 1
239: ** is populated like level 0, and eventually MERGE_COUNT level 1
240: ** segments are merged to a single level 2 segment (representing
241: ** MERGE_COUNT^2 updates), and so on.
242: **
243: ** A segment merge traverses all segments at a given level in
244: ** parallel, performing a straightforward sorted merge. Since segment
245: ** leaf nodes are written in to the %_segments table in order, this
246: ** merge traverses the underlying sqlite disk structures efficiently.
247: ** After the merge, all segment blocks from the merged level are
248: ** deleted.
249: **
250: ** MERGE_COUNT controls how often we merge segments. 16 seems to be
251: ** somewhat of a sweet spot for insertion performance. 32 and 64 show
252: ** very similar performance numbers to 16 on insertion, though they're
253: ** a tiny bit slower (perhaps due to more overhead in merge-time
254: ** sorting). 8 is about 20% slower than 16, 4 about 50% slower than
255: ** 16, 2 about 66% slower than 16.
256: **
257: ** At query time, high MERGE_COUNT increases the number of segments
258: ** which need to be scanned and merged. For instance, with 100k docs
259: ** inserted:
260: **
261: ** MERGE_COUNT segments
262: ** 16 25
263: ** 8 12
264: ** 4 10
265: ** 2 6
266: **
267: ** This appears to have only a moderate impact on queries for very
268: ** frequent terms (which are somewhat dominated by segment merge
269: ** costs), and infrequent and non-existent terms still seem to be fast
270: ** even with many segments.
271: **
272: ** TODO(shess) That said, it would be nice to have a better query-side
273: ** argument for MERGE_COUNT of 16. Also, it is possible/likely that
274: ** optimizations to things like doclist merging will swing the sweet
275: ** spot around.
276: **
277: **
278: **
279: **** Handling of deletions and updates ****
280: ** Since we're using a segmented structure, with no docid-oriented
281: ** index into the term index, we clearly cannot simply update the term
282: ** index when a document is deleted or updated. For deletions, we
283: ** write an empty doclist (varint(docid) varint(POS_END)), for updates
284: ** we simply write the new doclist. Segment merges overwrite older
285: ** data for a particular docid with newer data, so deletes or updates
286: ** will eventually overtake the earlier data and knock it out. The
287: ** query logic likewise merges doclists so that newer data knocks out
288: ** older data.
289: **
290: ** TODO(shess) Provide a VACUUM type operation to clear out all
291: ** deletions and duplications. This would basically be a forced merge
292: ** into a single segment.
293: */
294:
295: #include "fts3Int.h"
296: #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)
297:
298: #if defined(SQLITE_ENABLE_FTS3) && !defined(SQLITE_CORE)
299: # define SQLITE_CORE 1
300: #endif
301:
302: #include <assert.h>
303: #include <stdlib.h>
304: #include <stddef.h>
305: #include <stdio.h>
306: #include <string.h>
307: #include <stdarg.h>
308:
309: #include "fts3.h"
310: #ifndef SQLITE_CORE
311: # include "sqlite3ext.h"
312: SQLITE_EXTENSION_INIT1
313: #endif
314:
315: static int fts3EvalNext(Fts3Cursor *pCsr);
316: static int fts3EvalStart(Fts3Cursor *pCsr);
317: static int fts3TermSegReaderCursor(
318: Fts3Cursor *, const char *, int, int, Fts3MultiSegReader **);
319:
320: /*
321: ** Write a 64-bit variable-length integer to memory starting at p[0].
322: ** The length of data written will be between 1 and FTS3_VARINT_MAX bytes.
323: ** The number of bytes written is returned.
324: */
325: int sqlite3Fts3PutVarint(char *p, sqlite_int64 v){
326: unsigned char *q = (unsigned char *) p;
327: sqlite_uint64 vu = v;
328: do{
329: *q++ = (unsigned char) ((vu & 0x7f) | 0x80);
330: vu >>= 7;
331: }while( vu!=0 );
332: q[-1] &= 0x7f; /* turn off high bit in final byte */
333: assert( q - (unsigned char *)p <= FTS3_VARINT_MAX );
334: return (int) (q - (unsigned char *)p);
335: }
336:
337: /*
338: ** Read a 64-bit variable-length integer from memory starting at p[0].
339: ** Return the number of bytes read, or 0 on error.
340: ** The value is stored in *v.
341: */
342: int sqlite3Fts3GetVarint(const char *p, sqlite_int64 *v){
343: const unsigned char *q = (const unsigned char *) p;
344: sqlite_uint64 x = 0, y = 1;
345: while( (*q&0x80)==0x80 && q-(unsigned char *)p<FTS3_VARINT_MAX ){
346: x += y * (*q++ & 0x7f);
347: y <<= 7;
348: }
349: x += y * (*q++);
350: *v = (sqlite_int64) x;
351: return (int) (q - (unsigned char *)p);
352: }
353:
354: /*
355: ** Similar to sqlite3Fts3GetVarint(), except that the output is truncated to a
356: ** 32-bit integer before it is returned.
357: */
358: int sqlite3Fts3GetVarint32(const char *p, int *pi){
359: sqlite_int64 i;
360: int ret = sqlite3Fts3GetVarint(p, &i);
361: *pi = (int) i;
362: return ret;
363: }
364:
365: /*
366: ** Return the number of bytes required to encode v as a varint
367: */
368: int sqlite3Fts3VarintLen(sqlite3_uint64 v){
369: int i = 0;
370: do{
371: i++;
372: v >>= 7;
373: }while( v!=0 );
374: return i;
375: }
376:
377: /*
378: ** Convert an SQL-style quoted string into a normal string by removing
379: ** the quote characters. The conversion is done in-place. If the
380: ** input does not begin with a quote character, then this routine
381: ** is a no-op.
382: **
383: ** Examples:
384: **
385: ** "abc" becomes abc
386: ** 'xyz' becomes xyz
387: ** [pqr] becomes pqr
388: ** `mno` becomes mno
389: **
390: */
391: void sqlite3Fts3Dequote(char *z){
392: char quote; /* Quote character (if any ) */
393:
394: quote = z[0];
395: if( quote=='[' || quote=='\'' || quote=='"' || quote=='`' ){
396: int iIn = 1; /* Index of next byte to read from input */
397: int iOut = 0; /* Index of next byte to write to output */
398:
399: /* If the first byte was a '[', then the close-quote character is a ']' */
400: if( quote=='[' ) quote = ']';
401:
402: while( ALWAYS(z[iIn]) ){
403: if( z[iIn]==quote ){
404: if( z[iIn+1]!=quote ) break;
405: z[iOut++] = quote;
406: iIn += 2;
407: }else{
408: z[iOut++] = z[iIn++];
409: }
410: }
411: z[iOut] = '\0';
412: }
413: }
414:
415: /*
416: ** Read a single varint from the doclist at *pp and advance *pp to point
417: ** to the first byte past the end of the varint. Add the value of the varint
418: ** to *pVal.
419: */
420: static void fts3GetDeltaVarint(char **pp, sqlite3_int64 *pVal){
421: sqlite3_int64 iVal;
422: *pp += sqlite3Fts3GetVarint(*pp, &iVal);
423: *pVal += iVal;
424: }
425:
426: /*
427: ** When this function is called, *pp points to the first byte following a
428: ** varint that is part of a doclist (or position-list, or any other list
429: ** of varints). This function moves *pp to point to the start of that varint,
430: ** and sets *pVal by the varint value.
431: **
432: ** Argument pStart points to the first byte of the doclist that the
433: ** varint is part of.
434: */
435: static void fts3GetReverseVarint(
436: char **pp,
437: char *pStart,
438: sqlite3_int64 *pVal
439: ){
440: sqlite3_int64 iVal;
441: char *p;
442:
443: /* Pointer p now points at the first byte past the varint we are
444: ** interested in. So, unless the doclist is corrupt, the 0x80 bit is
445: ** clear on character p[-1]. */
446: for(p = (*pp)-2; p>=pStart && *p&0x80; p--);
447: p++;
448: *pp = p;
449:
450: sqlite3Fts3GetVarint(p, &iVal);
451: *pVal = iVal;
452: }
453:
454: /*
455: ** The xDisconnect() virtual table method.
456: */
457: static int fts3DisconnectMethod(sqlite3_vtab *pVtab){
458: Fts3Table *p = (Fts3Table *)pVtab;
459: int i;
460:
461: assert( p->nPendingData==0 );
462: assert( p->pSegments==0 );
463:
464: /* Free any prepared statements held */
465: for(i=0; i<SizeofArray(p->aStmt); i++){
466: sqlite3_finalize(p->aStmt[i]);
467: }
468: sqlite3_free(p->zSegmentsTbl);
469: sqlite3_free(p->zReadExprlist);
470: sqlite3_free(p->zWriteExprlist);
471: sqlite3_free(p->zContentTbl);
472:
473: /* Invoke the tokenizer destructor to free the tokenizer. */
474: p->pTokenizer->pModule->xDestroy(p->pTokenizer);
475:
476: sqlite3_free(p);
477: return SQLITE_OK;
478: }
479:
480: /*
481: ** Construct one or more SQL statements from the format string given
482: ** and then evaluate those statements. The success code is written
483: ** into *pRc.
484: **
485: ** If *pRc is initially non-zero then this routine is a no-op.
486: */
487: static void fts3DbExec(
488: int *pRc, /* Success code */
489: sqlite3 *db, /* Database in which to run SQL */
490: const char *zFormat, /* Format string for SQL */
491: ... /* Arguments to the format string */
492: ){
493: va_list ap;
494: char *zSql;
495: if( *pRc ) return;
496: va_start(ap, zFormat);
497: zSql = sqlite3_vmprintf(zFormat, ap);
498: va_end(ap);
499: if( zSql==0 ){
500: *pRc = SQLITE_NOMEM;
501: }else{
502: *pRc = sqlite3_exec(db, zSql, 0, 0, 0);
503: sqlite3_free(zSql);
504: }
505: }
506:
507: /*
508: ** The xDestroy() virtual table method.
509: */
510: static int fts3DestroyMethod(sqlite3_vtab *pVtab){
511: Fts3Table *p = (Fts3Table *)pVtab;
512: int rc = SQLITE_OK; /* Return code */
513: const char *zDb = p->zDb; /* Name of database (e.g. "main", "temp") */
514: sqlite3 *db = p->db; /* Database handle */
515:
516: /* Drop the shadow tables */
517: if( p->zContentTbl==0 ){
518: fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_content'", zDb, p->zName);
519: }
520: fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_segments'", zDb,p->zName);
521: fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_segdir'", zDb, p->zName);
522: fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_docsize'", zDb, p->zName);
523: fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_stat'", zDb, p->zName);
524:
525: /* If everything has worked, invoke fts3DisconnectMethod() to free the
526: ** memory associated with the Fts3Table structure and return SQLITE_OK.
527: ** Otherwise, return an SQLite error code.
528: */
529: return (rc==SQLITE_OK ? fts3DisconnectMethod(pVtab) : rc);
530: }
531:
532:
533: /*
534: ** Invoke sqlite3_declare_vtab() to declare the schema for the FTS3 table
535: ** passed as the first argument. This is done as part of the xConnect()
536: ** and xCreate() methods.
537: **
538: ** If *pRc is non-zero when this function is called, it is a no-op.
539: ** Otherwise, if an error occurs, an SQLite error code is stored in *pRc
540: ** before returning.
541: */
542: static void fts3DeclareVtab(int *pRc, Fts3Table *p){
543: if( *pRc==SQLITE_OK ){
544: int i; /* Iterator variable */
545: int rc; /* Return code */
546: char *zSql; /* SQL statement passed to declare_vtab() */
547: char *zCols; /* List of user defined columns */
548:
549: sqlite3_vtab_config(p->db, SQLITE_VTAB_CONSTRAINT_SUPPORT, 1);
550:
551: /* Create a list of user columns for the virtual table */
552: zCols = sqlite3_mprintf("%Q, ", p->azColumn[0]);
553: for(i=1; zCols && i<p->nColumn; i++){
554: zCols = sqlite3_mprintf("%z%Q, ", zCols, p->azColumn[i]);
555: }
556:
557: /* Create the whole "CREATE TABLE" statement to pass to SQLite */
558: zSql = sqlite3_mprintf(
559: "CREATE TABLE x(%s %Q HIDDEN, docid HIDDEN)", zCols, p->zName
560: );
561: if( !zCols || !zSql ){
562: rc = SQLITE_NOMEM;
563: }else{
564: rc = sqlite3_declare_vtab(p->db, zSql);
565: }
566:
567: sqlite3_free(zSql);
568: sqlite3_free(zCols);
569: *pRc = rc;
570: }
571: }
572:
573: /*
574: ** Create the backing store tables (%_content, %_segments and %_segdir)
575: ** required by the FTS3 table passed as the only argument. This is done
576: ** as part of the vtab xCreate() method.
577: **
578: ** If the p->bHasDocsize boolean is true (indicating that this is an
579: ** FTS4 table, not an FTS3 table) then also create the %_docsize and
580: ** %_stat tables required by FTS4.
581: */
582: static int fts3CreateTables(Fts3Table *p){
583: int rc = SQLITE_OK; /* Return code */
584: int i; /* Iterator variable */
585: sqlite3 *db = p->db; /* The database connection */
586:
587: if( p->zContentTbl==0 ){
588: char *zContentCols; /* Columns of %_content table */
589:
590: /* Create a list of user columns for the content table */
591: zContentCols = sqlite3_mprintf("docid INTEGER PRIMARY KEY");
592: for(i=0; zContentCols && i<p->nColumn; i++){
593: char *z = p->azColumn[i];
594: zContentCols = sqlite3_mprintf("%z, 'c%d%q'", zContentCols, i, z);
595: }
596: if( zContentCols==0 ) rc = SQLITE_NOMEM;
597:
598: /* Create the content table */
599: fts3DbExec(&rc, db,
600: "CREATE TABLE %Q.'%q_content'(%s)",
601: p->zDb, p->zName, zContentCols
602: );
603: sqlite3_free(zContentCols);
604: }
605:
606: /* Create other tables */
607: fts3DbExec(&rc, db,
608: "CREATE TABLE %Q.'%q_segments'(blockid INTEGER PRIMARY KEY, block BLOB);",
609: p->zDb, p->zName
610: );
611: fts3DbExec(&rc, db,
612: "CREATE TABLE %Q.'%q_segdir'("
613: "level INTEGER,"
614: "idx INTEGER,"
615: "start_block INTEGER,"
616: "leaves_end_block INTEGER,"
617: "end_block INTEGER,"
618: "root BLOB,"
619: "PRIMARY KEY(level, idx)"
620: ");",
621: p->zDb, p->zName
622: );
623: if( p->bHasDocsize ){
624: fts3DbExec(&rc, db,
625: "CREATE TABLE %Q.'%q_docsize'(docid INTEGER PRIMARY KEY, size BLOB);",
626: p->zDb, p->zName
627: );
628: }
629: if( p->bHasStat ){
630: fts3DbExec(&rc, db,
631: "CREATE TABLE %Q.'%q_stat'(id INTEGER PRIMARY KEY, value BLOB);",
632: p->zDb, p->zName
633: );
634: }
635: return rc;
636: }
637:
638: /*
639: ** Store the current database page-size in bytes in p->nPgsz.
640: **
641: ** If *pRc is non-zero when this function is called, it is a no-op.
642: ** Otherwise, if an error occurs, an SQLite error code is stored in *pRc
643: ** before returning.
644: */
645: static void fts3DatabasePageSize(int *pRc, Fts3Table *p){
646: if( *pRc==SQLITE_OK ){
647: int rc; /* Return code */
648: char *zSql; /* SQL text "PRAGMA %Q.page_size" */
649: sqlite3_stmt *pStmt; /* Compiled "PRAGMA %Q.page_size" statement */
650:
651: zSql = sqlite3_mprintf("PRAGMA %Q.page_size", p->zDb);
652: if( !zSql ){
653: rc = SQLITE_NOMEM;
654: }else{
655: rc = sqlite3_prepare(p->db, zSql, -1, &pStmt, 0);
656: if( rc==SQLITE_OK ){
657: sqlite3_step(pStmt);
658: p->nPgsz = sqlite3_column_int(pStmt, 0);
659: rc = sqlite3_finalize(pStmt);
660: }else if( rc==SQLITE_AUTH ){
661: p->nPgsz = 1024;
662: rc = SQLITE_OK;
663: }
664: }
665: assert( p->nPgsz>0 || rc!=SQLITE_OK );
666: sqlite3_free(zSql);
667: *pRc = rc;
668: }
669: }
670:
671: /*
672: ** "Special" FTS4 arguments are column specifications of the following form:
673: **
674: ** <key> = <value>
675: **
676: ** There may not be whitespace surrounding the "=" character. The <value>
677: ** term may be quoted, but the <key> may not.
678: */
679: static int fts3IsSpecialColumn(
680: const char *z,
681: int *pnKey,
682: char **pzValue
683: ){
684: char *zValue;
685: const char *zCsr = z;
686:
687: while( *zCsr!='=' ){
688: if( *zCsr=='\0' ) return 0;
689: zCsr++;
690: }
691:
692: *pnKey = (int)(zCsr-z);
693: zValue = sqlite3_mprintf("%s", &zCsr[1]);
694: if( zValue ){
695: sqlite3Fts3Dequote(zValue);
696: }
697: *pzValue = zValue;
698: return 1;
699: }
700:
701: /*
702: ** Append the output of a printf() style formatting to an existing string.
703: */
704: static void fts3Appendf(
705: int *pRc, /* IN/OUT: Error code */
706: char **pz, /* IN/OUT: Pointer to string buffer */
707: const char *zFormat, /* Printf format string to append */
708: ... /* Arguments for printf format string */
709: ){
710: if( *pRc==SQLITE_OK ){
711: va_list ap;
712: char *z;
713: va_start(ap, zFormat);
714: z = sqlite3_vmprintf(zFormat, ap);
715: va_end(ap);
716: if( z && *pz ){
717: char *z2 = sqlite3_mprintf("%s%s", *pz, z);
718: sqlite3_free(z);
719: z = z2;
720: }
721: if( z==0 ) *pRc = SQLITE_NOMEM;
722: sqlite3_free(*pz);
723: *pz = z;
724: }
725: }
726:
727: /*
728: ** Return a copy of input string zInput enclosed in double-quotes (") and
729: ** with all double quote characters escaped. For example:
730: **
731: ** fts3QuoteId("un \"zip\"") -> "un \"\"zip\"\""
732: **
733: ** The pointer returned points to memory obtained from sqlite3_malloc(). It
734: ** is the callers responsibility to call sqlite3_free() to release this
735: ** memory.
736: */
737: static char *fts3QuoteId(char const *zInput){
738: int nRet;
739: char *zRet;
740: nRet = 2 + strlen(zInput)*2 + 1;
741: zRet = sqlite3_malloc(nRet);
742: if( zRet ){
743: int i;
744: char *z = zRet;
745: *(z++) = '"';
746: for(i=0; zInput[i]; i++){
747: if( zInput[i]=='"' ) *(z++) = '"';
748: *(z++) = zInput[i];
749: }
750: *(z++) = '"';
751: *(z++) = '\0';
752: }
753: return zRet;
754: }
755:
756: /*
757: ** Return a list of comma separated SQL expressions and a FROM clause that
758: ** could be used in a SELECT statement such as the following:
759: **
760: ** SELECT <list of expressions> FROM %_content AS x ...
761: **
762: ** to return the docid, followed by each column of text data in order
763: ** from left to write. If parameter zFunc is not NULL, then instead of
764: ** being returned directly each column of text data is passed to an SQL
765: ** function named zFunc first. For example, if zFunc is "unzip" and the
766: ** table has the three user-defined columns "a", "b", and "c", the following
767: ** string is returned:
768: **
769: ** "docid, unzip(x.'a'), unzip(x.'b'), unzip(x.'c') FROM %_content AS x"
770: **
771: ** The pointer returned points to a buffer allocated by sqlite3_malloc(). It
772: ** is the responsibility of the caller to eventually free it.
773: **
774: ** If *pRc is not SQLITE_OK when this function is called, it is a no-op (and
775: ** a NULL pointer is returned). Otherwise, if an OOM error is encountered
776: ** by this function, NULL is returned and *pRc is set to SQLITE_NOMEM. If
777: ** no error occurs, *pRc is left unmodified.
778: */
779: static char *fts3ReadExprList(Fts3Table *p, const char *zFunc, int *pRc){
780: char *zRet = 0;
781: char *zFree = 0;
782: char *zFunction;
783: int i;
784:
785: if( p->zContentTbl==0 ){
786: if( !zFunc ){
787: zFunction = "";
788: }else{
789: zFree = zFunction = fts3QuoteId(zFunc);
790: }
791: fts3Appendf(pRc, &zRet, "docid");
792: for(i=0; i<p->nColumn; i++){
793: fts3Appendf(pRc, &zRet, ",%s(x.'c%d%q')", zFunction, i, p->azColumn[i]);
794: }
795: sqlite3_free(zFree);
796: }else{
797: fts3Appendf(pRc, &zRet, "rowid");
798: for(i=0; i<p->nColumn; i++){
799: fts3Appendf(pRc, &zRet, ", x.'%q'", p->azColumn[i]);
800: }
801: }
802: fts3Appendf(pRc, &zRet, "FROM '%q'.'%q%s' AS x",
803: p->zDb,
804: (p->zContentTbl ? p->zContentTbl : p->zName),
805: (p->zContentTbl ? "" : "_content")
806: );
807: return zRet;
808: }
809:
810: /*
811: ** Return a list of N comma separated question marks, where N is the number
812: ** of columns in the %_content table (one for the docid plus one for each
813: ** user-defined text column).
814: **
815: ** If argument zFunc is not NULL, then all but the first question mark
816: ** is preceded by zFunc and an open bracket, and followed by a closed
817: ** bracket. For example, if zFunc is "zip" and the FTS3 table has three
818: ** user-defined text columns, the following string is returned:
819: **
820: ** "?, zip(?), zip(?), zip(?)"
821: **
822: ** The pointer returned points to a buffer allocated by sqlite3_malloc(). It
823: ** is the responsibility of the caller to eventually free it.
824: **
825: ** If *pRc is not SQLITE_OK when this function is called, it is a no-op (and
826: ** a NULL pointer is returned). Otherwise, if an OOM error is encountered
827: ** by this function, NULL is returned and *pRc is set to SQLITE_NOMEM. If
828: ** no error occurs, *pRc is left unmodified.
829: */
830: static char *fts3WriteExprList(Fts3Table *p, const char *zFunc, int *pRc){
831: char *zRet = 0;
832: char *zFree = 0;
833: char *zFunction;
834: int i;
835:
836: if( !zFunc ){
837: zFunction = "";
838: }else{
839: zFree = zFunction = fts3QuoteId(zFunc);
840: }
841: fts3Appendf(pRc, &zRet, "?");
842: for(i=0; i<p->nColumn; i++){
843: fts3Appendf(pRc, &zRet, ",%s(?)", zFunction);
844: }
845: sqlite3_free(zFree);
846: return zRet;
847: }
848:
849: /*
850: ** This function interprets the string at (*pp) as a non-negative integer
851: ** value. It reads the integer and sets *pnOut to the value read, then
852: ** sets *pp to point to the byte immediately following the last byte of
853: ** the integer value.
854: **
855: ** Only decimal digits ('0'..'9') may be part of an integer value.
856: **
857: ** If *pp does not being with a decimal digit SQLITE_ERROR is returned and
858: ** the output value undefined. Otherwise SQLITE_OK is returned.
859: **
860: ** This function is used when parsing the "prefix=" FTS4 parameter.
861: */
862: static int fts3GobbleInt(const char **pp, int *pnOut){
863: const char *p; /* Iterator pointer */
864: int nInt = 0; /* Output value */
865:
866: for(p=*pp; p[0]>='0' && p[0]<='9'; p++){
867: nInt = nInt * 10 + (p[0] - '0');
868: }
869: if( p==*pp ) return SQLITE_ERROR;
870: *pnOut = nInt;
871: *pp = p;
872: return SQLITE_OK;
873: }
874:
875: /*
876: ** This function is called to allocate an array of Fts3Index structures
877: ** representing the indexes maintained by the current FTS table. FTS tables
878: ** always maintain the main "terms" index, but may also maintain one or
879: ** more "prefix" indexes, depending on the value of the "prefix=" parameter
880: ** (if any) specified as part of the CREATE VIRTUAL TABLE statement.
881: **
882: ** Argument zParam is passed the value of the "prefix=" option if one was
883: ** specified, or NULL otherwise.
884: **
885: ** If no error occurs, SQLITE_OK is returned and *apIndex set to point to
886: ** the allocated array. *pnIndex is set to the number of elements in the
887: ** array. If an error does occur, an SQLite error code is returned.
888: **
889: ** Regardless of whether or not an error is returned, it is the responsibility
890: ** of the caller to call sqlite3_free() on the output array to free it.
891: */
892: static int fts3PrefixParameter(
893: const char *zParam, /* ABC in prefix=ABC parameter to parse */
894: int *pnIndex, /* OUT: size of *apIndex[] array */
895: struct Fts3Index **apIndex /* OUT: Array of indexes for this table */
896: ){
897: struct Fts3Index *aIndex; /* Allocated array */
898: int nIndex = 1; /* Number of entries in array */
899:
900: if( zParam && zParam[0] ){
901: const char *p;
902: nIndex++;
903: for(p=zParam; *p; p++){
904: if( *p==',' ) nIndex++;
905: }
906: }
907:
908: aIndex = sqlite3_malloc(sizeof(struct Fts3Index) * nIndex);
909: *apIndex = aIndex;
910: *pnIndex = nIndex;
911: if( !aIndex ){
912: return SQLITE_NOMEM;
913: }
914:
915: memset(aIndex, 0, sizeof(struct Fts3Index) * nIndex);
916: if( zParam ){
917: const char *p = zParam;
918: int i;
919: for(i=1; i<nIndex; i++){
920: int nPrefix;
921: if( fts3GobbleInt(&p, &nPrefix) ) return SQLITE_ERROR;
922: aIndex[i].nPrefix = nPrefix;
923: p++;
924: }
925: }
926:
927: return SQLITE_OK;
928: }
929:
930: /*
931: ** This function is called when initializing an FTS4 table that uses the
932: ** content=xxx option. It determines the number of and names of the columns
933: ** of the new FTS4 table.
934: **
935: ** The third argument passed to this function is the value passed to the
936: ** config=xxx option (i.e. "xxx"). This function queries the database for
937: ** a table of that name. If found, the output variables are populated
938: ** as follows:
939: **
940: ** *pnCol: Set to the number of columns table xxx has,
941: **
942: ** *pnStr: Set to the total amount of space required to store a copy
943: ** of each columns name, including the nul-terminator.
944: **
945: ** *pazCol: Set to point to an array of *pnCol strings. Each string is
946: ** the name of the corresponding column in table xxx. The array
947: ** and its contents are allocated using a single allocation. It
948: ** is the responsibility of the caller to free this allocation
949: ** by eventually passing the *pazCol value to sqlite3_free().
950: **
951: ** If the table cannot be found, an error code is returned and the output
952: ** variables are undefined. Or, if an OOM is encountered, SQLITE_NOMEM is
953: ** returned (and the output variables are undefined).
954: */
955: static int fts3ContentColumns(
956: sqlite3 *db, /* Database handle */
957: const char *zDb, /* Name of db (i.e. "main", "temp" etc.) */
958: const char *zTbl, /* Name of content table */
959: const char ***pazCol, /* OUT: Malloc'd array of column names */
960: int *pnCol, /* OUT: Size of array *pazCol */
961: int *pnStr /* OUT: Bytes of string content */
962: ){
963: int rc = SQLITE_OK; /* Return code */
964: char *zSql; /* "SELECT *" statement on zTbl */
965: sqlite3_stmt *pStmt = 0; /* Compiled version of zSql */
966:
967: zSql = sqlite3_mprintf("SELECT * FROM %Q.%Q", zDb, zTbl);
968: if( !zSql ){
969: rc = SQLITE_NOMEM;
970: }else{
971: rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
972: }
973: sqlite3_free(zSql);
974:
975: if( rc==SQLITE_OK ){
976: const char **azCol; /* Output array */
977: int nStr = 0; /* Size of all column names (incl. 0x00) */
978: int nCol; /* Number of table columns */
979: int i; /* Used to iterate through columns */
980:
981: /* Loop through the returned columns. Set nStr to the number of bytes of
982: ** space required to store a copy of each column name, including the
983: ** nul-terminator byte. */
984: nCol = sqlite3_column_count(pStmt);
985: for(i=0; i<nCol; i++){
986: const char *zCol = sqlite3_column_name(pStmt, i);
987: nStr += strlen(zCol) + 1;
988: }
989:
990: /* Allocate and populate the array to return. */
991: azCol = (const char **)sqlite3_malloc(sizeof(char *) * nCol + nStr);
992: if( azCol==0 ){
993: rc = SQLITE_NOMEM;
994: }else{
995: char *p = (char *)&azCol[nCol];
996: for(i=0; i<nCol; i++){
997: const char *zCol = sqlite3_column_name(pStmt, i);
998: int n = strlen(zCol)+1;
999: memcpy(p, zCol, n);
1000: azCol[i] = p;
1001: p += n;
1002: }
1003: }
1004: sqlite3_finalize(pStmt);
1005:
1006: /* Set the output variables. */
1007: *pnCol = nCol;
1008: *pnStr = nStr;
1009: *pazCol = azCol;
1010: }
1011:
1012: return rc;
1013: }
1014:
1015: /*
1016: ** This function is the implementation of both the xConnect and xCreate
1017: ** methods of the FTS3 virtual table.
1018: **
1019: ** The argv[] array contains the following:
1020: **
1021: ** argv[0] -> module name ("fts3" or "fts4")
1022: ** argv[1] -> database name
1023: ** argv[2] -> table name
1024: ** argv[...] -> "column name" and other module argument fields.
1025: */
1026: static int fts3InitVtab(
1027: int isCreate, /* True for xCreate, false for xConnect */
1028: sqlite3 *db, /* The SQLite database connection */
1029: void *pAux, /* Hash table containing tokenizers */
1030: int argc, /* Number of elements in argv array */
1031: const char * const *argv, /* xCreate/xConnect argument array */
1032: sqlite3_vtab **ppVTab, /* Write the resulting vtab structure here */
1033: char **pzErr /* Write any error message here */
1034: ){
1035: Fts3Hash *pHash = (Fts3Hash *)pAux;
1036: Fts3Table *p = 0; /* Pointer to allocated vtab */
1037: int rc = SQLITE_OK; /* Return code */
1038: int i; /* Iterator variable */
1039: int nByte; /* Size of allocation used for *p */
1040: int iCol; /* Column index */
1041: int nString = 0; /* Bytes required to hold all column names */
1042: int nCol = 0; /* Number of columns in the FTS table */
1043: char *zCsr; /* Space for holding column names */
1044: int nDb; /* Bytes required to hold database name */
1045: int nName; /* Bytes required to hold table name */
1046: int isFts4 = (argv[0][3]=='4'); /* True for FTS4, false for FTS3 */
1047: const char **aCol; /* Array of column names */
1048: sqlite3_tokenizer *pTokenizer = 0; /* Tokenizer for this table */
1049:
1050: int nIndex; /* Size of aIndex[] array */
1051: struct Fts3Index *aIndex = 0; /* Array of indexes for this table */
1052:
1053: /* The results of parsing supported FTS4 key=value options: */
1054: int bNoDocsize = 0; /* True to omit %_docsize table */
1055: int bDescIdx = 0; /* True to store descending indexes */
1056: char *zPrefix = 0; /* Prefix parameter value (or NULL) */
1057: char *zCompress = 0; /* compress=? parameter (or NULL) */
1058: char *zUncompress = 0; /* uncompress=? parameter (or NULL) */
1059: char *zContent = 0; /* content=? parameter (or NULL) */
1060:
1061: assert( strlen(argv[0])==4 );
1062: assert( (sqlite3_strnicmp(argv[0], "fts4", 4)==0 && isFts4)
1063: || (sqlite3_strnicmp(argv[0], "fts3", 4)==0 && !isFts4)
1064: );
1065:
1066: nDb = (int)strlen(argv[1]) + 1;
1067: nName = (int)strlen(argv[2]) + 1;
1068:
1069: aCol = (const char **)sqlite3_malloc(sizeof(const char *) * (argc-2) );
1070: if( !aCol ) return SQLITE_NOMEM;
1071: memset((void *)aCol, 0, sizeof(const char *) * (argc-2));
1072:
1073: /* Loop through all of the arguments passed by the user to the FTS3/4
1074: ** module (i.e. all the column names and special arguments). This loop
1075: ** does the following:
1076: **
1077: ** + Figures out the number of columns the FTSX table will have, and
1078: ** the number of bytes of space that must be allocated to store copies
1079: ** of the column names.
1080: **
1081: ** + If there is a tokenizer specification included in the arguments,
1082: ** initializes the tokenizer pTokenizer.
1083: */
1084: for(i=3; rc==SQLITE_OK && i<argc; i++){
1085: char const *z = argv[i];
1086: int nKey;
1087: char *zVal;
1088:
1089: /* Check if this is a tokenizer specification */
1090: if( !pTokenizer
1091: && strlen(z)>8
1092: && 0==sqlite3_strnicmp(z, "tokenize", 8)
1093: && 0==sqlite3Fts3IsIdChar(z[8])
1094: ){
1095: rc = sqlite3Fts3InitTokenizer(pHash, &z[9], &pTokenizer, pzErr);
1096: }
1097:
1098: /* Check if it is an FTS4 special argument. */
1099: else if( isFts4 && fts3IsSpecialColumn(z, &nKey, &zVal) ){
1100: struct Fts4Option {
1101: const char *zOpt;
1102: int nOpt;
1103: } aFts4Opt[] = {
1104: { "matchinfo", 9 }, /* 0 -> MATCHINFO */
1105: { "prefix", 6 }, /* 1 -> PREFIX */
1106: { "compress", 8 }, /* 2 -> COMPRESS */
1107: { "uncompress", 10 }, /* 3 -> UNCOMPRESS */
1108: { "order", 5 }, /* 4 -> ORDER */
1109: { "content", 7 } /* 5 -> CONTENT */
1110: };
1111:
1112: int iOpt;
1113: if( !zVal ){
1114: rc = SQLITE_NOMEM;
1115: }else{
1116: for(iOpt=0; iOpt<SizeofArray(aFts4Opt); iOpt++){
1117: struct Fts4Option *pOp = &aFts4Opt[iOpt];
1118: if( nKey==pOp->nOpt && !sqlite3_strnicmp(z, pOp->zOpt, pOp->nOpt) ){
1119: break;
1120: }
1121: }
1122: if( iOpt==SizeofArray(aFts4Opt) ){
1123: *pzErr = sqlite3_mprintf("unrecognized parameter: %s", z);
1124: rc = SQLITE_ERROR;
1125: }else{
1126: switch( iOpt ){
1127: case 0: /* MATCHINFO */
1128: if( strlen(zVal)!=4 || sqlite3_strnicmp(zVal, "fts3", 4) ){
1129: *pzErr = sqlite3_mprintf("unrecognized matchinfo: %s", zVal);
1130: rc = SQLITE_ERROR;
1131: }
1132: bNoDocsize = 1;
1133: break;
1134:
1135: case 1: /* PREFIX */
1136: sqlite3_free(zPrefix);
1137: zPrefix = zVal;
1138: zVal = 0;
1139: break;
1140:
1141: case 2: /* COMPRESS */
1142: sqlite3_free(zCompress);
1143: zCompress = zVal;
1144: zVal = 0;
1145: break;
1146:
1147: case 3: /* UNCOMPRESS */
1148: sqlite3_free(zUncompress);
1149: zUncompress = zVal;
1150: zVal = 0;
1151: break;
1152:
1153: case 4: /* ORDER */
1154: if( (strlen(zVal)!=3 || sqlite3_strnicmp(zVal, "asc", 3))
1155: && (strlen(zVal)!=4 || sqlite3_strnicmp(zVal, "desc", 4))
1156: ){
1157: *pzErr = sqlite3_mprintf("unrecognized order: %s", zVal);
1158: rc = SQLITE_ERROR;
1159: }
1160: bDescIdx = (zVal[0]=='d' || zVal[0]=='D');
1161: break;
1162:
1163: default: /* CONTENT */
1164: assert( iOpt==5 );
1165: sqlite3_free(zUncompress);
1166: zContent = zVal;
1167: zVal = 0;
1168: break;
1169: }
1170: }
1171: sqlite3_free(zVal);
1172: }
1173: }
1174:
1175: /* Otherwise, the argument is a column name. */
1176: else {
1177: nString += (int)(strlen(z) + 1);
1178: aCol[nCol++] = z;
1179: }
1180: }
1181:
1182: /* If a content=xxx option was specified, the following:
1183: **
1184: ** 1. Ignore any compress= and uncompress= options.
1185: **
1186: ** 2. If no column names were specified as part of the CREATE VIRTUAL
1187: ** TABLE statement, use all columns from the content table.
1188: */
1189: if( rc==SQLITE_OK && zContent ){
1190: sqlite3_free(zCompress);
1191: sqlite3_free(zUncompress);
1192: zCompress = 0;
1193: zUncompress = 0;
1194: if( nCol==0 ){
1195: sqlite3_free((void*)aCol);
1196: aCol = 0;
1197: rc = fts3ContentColumns(db, argv[1], zContent, &aCol, &nCol, &nString);
1198: }
1199: assert( rc!=SQLITE_OK || nCol>0 );
1200: }
1201: if( rc!=SQLITE_OK ) goto fts3_init_out;
1202:
1203: if( nCol==0 ){
1204: assert( nString==0 );
1205: aCol[0] = "content";
1206: nString = 8;
1207: nCol = 1;
1208: }
1209:
1210: if( pTokenizer==0 ){
1211: rc = sqlite3Fts3InitTokenizer(pHash, "simple", &pTokenizer, pzErr);
1212: if( rc!=SQLITE_OK ) goto fts3_init_out;
1213: }
1214: assert( pTokenizer );
1215:
1216: rc = fts3PrefixParameter(zPrefix, &nIndex, &aIndex);
1217: if( rc==SQLITE_ERROR ){
1218: assert( zPrefix );
1219: *pzErr = sqlite3_mprintf("error parsing prefix parameter: %s", zPrefix);
1220: }
1221: if( rc!=SQLITE_OK ) goto fts3_init_out;
1222:
1223: /* Allocate and populate the Fts3Table structure. */
1224: nByte = sizeof(Fts3Table) + /* Fts3Table */
1225: nCol * sizeof(char *) + /* azColumn */
1226: nIndex * sizeof(struct Fts3Index) + /* aIndex */
1227: nName + /* zName */
1228: nDb + /* zDb */
1229: nString; /* Space for azColumn strings */
1230: p = (Fts3Table*)sqlite3_malloc(nByte);
1231: if( p==0 ){
1232: rc = SQLITE_NOMEM;
1233: goto fts3_init_out;
1234: }
1235: memset(p, 0, nByte);
1236: p->db = db;
1237: p->nColumn = nCol;
1238: p->nPendingData = 0;
1239: p->azColumn = (char **)&p[1];
1240: p->pTokenizer = pTokenizer;
1241: p->nMaxPendingData = FTS3_MAX_PENDING_DATA;
1242: p->bHasDocsize = (isFts4 && bNoDocsize==0);
1243: p->bHasStat = isFts4;
1244: p->bDescIdx = bDescIdx;
1245: p->zContentTbl = zContent;
1246: zContent = 0;
1247: TESTONLY( p->inTransaction = -1 );
1248: TESTONLY( p->mxSavepoint = -1 );
1249:
1250: p->aIndex = (struct Fts3Index *)&p->azColumn[nCol];
1251: memcpy(p->aIndex, aIndex, sizeof(struct Fts3Index) * nIndex);
1252: p->nIndex = nIndex;
1253: for(i=0; i<nIndex; i++){
1254: fts3HashInit(&p->aIndex[i].hPending, FTS3_HASH_STRING, 1);
1255: }
1256:
1257: /* Fill in the zName and zDb fields of the vtab structure. */
1258: zCsr = (char *)&p->aIndex[nIndex];
1259: p->zName = zCsr;
1260: memcpy(zCsr, argv[2], nName);
1261: zCsr += nName;
1262: p->zDb = zCsr;
1263: memcpy(zCsr, argv[1], nDb);
1264: zCsr += nDb;
1265:
1266: /* Fill in the azColumn array */
1267: for(iCol=0; iCol<nCol; iCol++){
1268: char *z;
1269: int n = 0;
1270: z = (char *)sqlite3Fts3NextToken(aCol[iCol], &n);
1271: memcpy(zCsr, z, n);
1272: zCsr[n] = '\0';
1273: sqlite3Fts3Dequote(zCsr);
1274: p->azColumn[iCol] = zCsr;
1275: zCsr += n+1;
1276: assert( zCsr <= &((char *)p)[nByte] );
1277: }
1278:
1279: if( (zCompress==0)!=(zUncompress==0) ){
1280: char const *zMiss = (zCompress==0 ? "compress" : "uncompress");
1281: rc = SQLITE_ERROR;
1282: *pzErr = sqlite3_mprintf("missing %s parameter in fts4 constructor", zMiss);
1283: }
1284: p->zReadExprlist = fts3ReadExprList(p, zUncompress, &rc);
1285: p->zWriteExprlist = fts3WriteExprList(p, zCompress, &rc);
1286: if( rc!=SQLITE_OK ) goto fts3_init_out;
1287:
1288: /* If this is an xCreate call, create the underlying tables in the
1289: ** database. TODO: For xConnect(), it could verify that said tables exist.
1290: */
1291: if( isCreate ){
1292: rc = fts3CreateTables(p);
1293: }
1294:
1295: /* Figure out the page-size for the database. This is required in order to
1296: ** estimate the cost of loading large doclists from the database. */
1297: fts3DatabasePageSize(&rc, p);
1298: p->nNodeSize = p->nPgsz-35;
1299:
1300: /* Declare the table schema to SQLite. */
1301: fts3DeclareVtab(&rc, p);
1302:
1303: fts3_init_out:
1304: sqlite3_free(zPrefix);
1305: sqlite3_free(aIndex);
1306: sqlite3_free(zCompress);
1307: sqlite3_free(zUncompress);
1308: sqlite3_free(zContent);
1309: sqlite3_free((void *)aCol);
1310: if( rc!=SQLITE_OK ){
1311: if( p ){
1312: fts3DisconnectMethod((sqlite3_vtab *)p);
1313: }else if( pTokenizer ){
1314: pTokenizer->pModule->xDestroy(pTokenizer);
1315: }
1316: }else{
1317: assert( p->pSegments==0 );
1318: *ppVTab = &p->base;
1319: }
1320: return rc;
1321: }
1322:
1323: /*
1324: ** The xConnect() and xCreate() methods for the virtual table. All the
1325: ** work is done in function fts3InitVtab().
1326: */
1327: static int fts3ConnectMethod(
1328: sqlite3 *db, /* Database connection */
1329: void *pAux, /* Pointer to tokenizer hash table */
1330: int argc, /* Number of elements in argv array */
1331: const char * const *argv, /* xCreate/xConnect argument array */
1332: sqlite3_vtab **ppVtab, /* OUT: New sqlite3_vtab object */
1333: char **pzErr /* OUT: sqlite3_malloc'd error message */
1334: ){
1335: return fts3InitVtab(0, db, pAux, argc, argv, ppVtab, pzErr);
1336: }
1337: static int fts3CreateMethod(
1338: sqlite3 *db, /* Database connection */
1339: void *pAux, /* Pointer to tokenizer hash table */
1340: int argc, /* Number of elements in argv array */
1341: const char * const *argv, /* xCreate/xConnect argument array */
1342: sqlite3_vtab **ppVtab, /* OUT: New sqlite3_vtab object */
1343: char **pzErr /* OUT: sqlite3_malloc'd error message */
1344: ){
1345: return fts3InitVtab(1, db, pAux, argc, argv, ppVtab, pzErr);
1346: }
1347:
1348: /*
1349: ** Implementation of the xBestIndex method for FTS3 tables. There
1350: ** are three possible strategies, in order of preference:
1351: **
1352: ** 1. Direct lookup by rowid or docid.
1353: ** 2. Full-text search using a MATCH operator on a non-docid column.
1354: ** 3. Linear scan of %_content table.
1355: */
1356: static int fts3BestIndexMethod(sqlite3_vtab *pVTab, sqlite3_index_info *pInfo){
1357: Fts3Table *p = (Fts3Table *)pVTab;
1358: int i; /* Iterator variable */
1359: int iCons = -1; /* Index of constraint to use */
1360:
1361: /* By default use a full table scan. This is an expensive option,
1362: ** so search through the constraints to see if a more efficient
1363: ** strategy is possible.
1364: */
1365: pInfo->idxNum = FTS3_FULLSCAN_SEARCH;
1366: pInfo->estimatedCost = 500000;
1367: for(i=0; i<pInfo->nConstraint; i++){
1368: struct sqlite3_index_constraint *pCons = &pInfo->aConstraint[i];
1369: if( pCons->usable==0 ) continue;
1370:
1371: /* A direct lookup on the rowid or docid column. Assign a cost of 1.0. */
1372: if( pCons->op==SQLITE_INDEX_CONSTRAINT_EQ
1373: && (pCons->iColumn<0 || pCons->iColumn==p->nColumn+1 )
1374: ){
1375: pInfo->idxNum = FTS3_DOCID_SEARCH;
1376: pInfo->estimatedCost = 1.0;
1377: iCons = i;
1378: }
1379:
1380: /* A MATCH constraint. Use a full-text search.
1381: **
1382: ** If there is more than one MATCH constraint available, use the first
1383: ** one encountered. If there is both a MATCH constraint and a direct
1384: ** rowid/docid lookup, prefer the MATCH strategy. This is done even
1385: ** though the rowid/docid lookup is faster than a MATCH query, selecting
1386: ** it would lead to an "unable to use function MATCH in the requested
1387: ** context" error.
1388: */
1389: if( pCons->op==SQLITE_INDEX_CONSTRAINT_MATCH
1390: && pCons->iColumn>=0 && pCons->iColumn<=p->nColumn
1391: ){
1392: pInfo->idxNum = FTS3_FULLTEXT_SEARCH + pCons->iColumn;
1393: pInfo->estimatedCost = 2.0;
1394: iCons = i;
1395: break;
1396: }
1397: }
1398:
1399: if( iCons>=0 ){
1400: pInfo->aConstraintUsage[iCons].argvIndex = 1;
1401: pInfo->aConstraintUsage[iCons].omit = 1;
1402: }
1403:
1404: /* Regardless of the strategy selected, FTS can deliver rows in rowid (or
1405: ** docid) order. Both ascending and descending are possible.
1406: */
1407: if( pInfo->nOrderBy==1 ){
1408: struct sqlite3_index_orderby *pOrder = &pInfo->aOrderBy[0];
1409: if( pOrder->iColumn<0 || pOrder->iColumn==p->nColumn+1 ){
1410: if( pOrder->desc ){
1411: pInfo->idxStr = "DESC";
1412: }else{
1413: pInfo->idxStr = "ASC";
1414: }
1415: pInfo->orderByConsumed = 1;
1416: }
1417: }
1418:
1419: assert( p->pSegments==0 );
1420: return SQLITE_OK;
1421: }
1422:
1423: /*
1424: ** Implementation of xOpen method.
1425: */
1426: static int fts3OpenMethod(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCsr){
1427: sqlite3_vtab_cursor *pCsr; /* Allocated cursor */
1428:
1429: UNUSED_PARAMETER(pVTab);
1430:
1431: /* Allocate a buffer large enough for an Fts3Cursor structure. If the
1432: ** allocation succeeds, zero it and return SQLITE_OK. Otherwise,
1433: ** if the allocation fails, return SQLITE_NOMEM.
1434: */
1435: *ppCsr = pCsr = (sqlite3_vtab_cursor *)sqlite3_malloc(sizeof(Fts3Cursor));
1436: if( !pCsr ){
1437: return SQLITE_NOMEM;
1438: }
1439: memset(pCsr, 0, sizeof(Fts3Cursor));
1440: return SQLITE_OK;
1441: }
1442:
1443: /*
1444: ** Close the cursor. For additional information see the documentation
1445: ** on the xClose method of the virtual table interface.
1446: */
1447: static int fts3CloseMethod(sqlite3_vtab_cursor *pCursor){
1448: Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;
1449: assert( ((Fts3Table *)pCsr->base.pVtab)->pSegments==0 );
1450: sqlite3_finalize(pCsr->pStmt);
1451: sqlite3Fts3ExprFree(pCsr->pExpr);
1452: sqlite3Fts3FreeDeferredTokens(pCsr);
1453: sqlite3_free(pCsr->aDoclist);
1454: sqlite3_free(pCsr->aMatchinfo);
1455: assert( ((Fts3Table *)pCsr->base.pVtab)->pSegments==0 );
1456: sqlite3_free(pCsr);
1457: return SQLITE_OK;
1458: }
1459:
1460: /*
1461: ** If pCsr->pStmt has not been prepared (i.e. if pCsr->pStmt==0), then
1462: ** compose and prepare an SQL statement of the form:
1463: **
1464: ** "SELECT <columns> FROM %_content WHERE rowid = ?"
1465: **
1466: ** (or the equivalent for a content=xxx table) and set pCsr->pStmt to
1467: ** it. If an error occurs, return an SQLite error code.
1468: **
1469: ** Otherwise, set *ppStmt to point to pCsr->pStmt and return SQLITE_OK.
1470: */
1471: static int fts3CursorSeekStmt(Fts3Cursor *pCsr, sqlite3_stmt **ppStmt){
1472: int rc = SQLITE_OK;
1473: if( pCsr->pStmt==0 ){
1474: Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
1475: char *zSql;
1476: zSql = sqlite3_mprintf("SELECT %s WHERE rowid = ?", p->zReadExprlist);
1477: if( !zSql ) return SQLITE_NOMEM;
1478: rc = sqlite3_prepare_v2(p->db, zSql, -1, &pCsr->pStmt, 0);
1479: sqlite3_free(zSql);
1480: }
1481: *ppStmt = pCsr->pStmt;
1482: return rc;
1483: }
1484:
1485: /*
1486: ** Position the pCsr->pStmt statement so that it is on the row
1487: ** of the %_content table that contains the last match. Return
1488: ** SQLITE_OK on success.
1489: */
1490: static int fts3CursorSeek(sqlite3_context *pContext, Fts3Cursor *pCsr){
1491: int rc = SQLITE_OK;
1492: if( pCsr->isRequireSeek ){
1493: sqlite3_stmt *pStmt = 0;
1494:
1495: rc = fts3CursorSeekStmt(pCsr, &pStmt);
1496: if( rc==SQLITE_OK ){
1497: sqlite3_bind_int64(pCsr->pStmt, 1, pCsr->iPrevId);
1498: pCsr->isRequireSeek = 0;
1499: if( SQLITE_ROW==sqlite3_step(pCsr->pStmt) ){
1500: return SQLITE_OK;
1501: }else{
1502: rc = sqlite3_reset(pCsr->pStmt);
1503: if( rc==SQLITE_OK && ((Fts3Table *)pCsr->base.pVtab)->zContentTbl==0 ){
1504: /* If no row was found and no error has occured, then the %_content
1505: ** table is missing a row that is present in the full-text index.
1506: ** The data structures are corrupt. */
1507: rc = FTS_CORRUPT_VTAB;
1508: pCsr->isEof = 1;
1509: }
1510: }
1511: }
1512: }
1513:
1514: if( rc!=SQLITE_OK && pContext ){
1515: sqlite3_result_error_code(pContext, rc);
1516: }
1517: return rc;
1518: }
1519:
1520: /*
1521: ** This function is used to process a single interior node when searching
1522: ** a b-tree for a term or term prefix. The node data is passed to this
1523: ** function via the zNode/nNode parameters. The term to search for is
1524: ** passed in zTerm/nTerm.
1525: **
1526: ** If piFirst is not NULL, then this function sets *piFirst to the blockid
1527: ** of the child node that heads the sub-tree that may contain the term.
1528: **
1529: ** If piLast is not NULL, then *piLast is set to the right-most child node
1530: ** that heads a sub-tree that may contain a term for which zTerm/nTerm is
1531: ** a prefix.
1532: **
1533: ** If an OOM error occurs, SQLITE_NOMEM is returned. Otherwise, SQLITE_OK.
1534: */
1535: static int fts3ScanInteriorNode(
1536: const char *zTerm, /* Term to select leaves for */
1537: int nTerm, /* Size of term zTerm in bytes */
1538: const char *zNode, /* Buffer containing segment interior node */
1539: int nNode, /* Size of buffer at zNode */
1540: sqlite3_int64 *piFirst, /* OUT: Selected child node */
1541: sqlite3_int64 *piLast /* OUT: Selected child node */
1542: ){
1543: int rc = SQLITE_OK; /* Return code */
1544: const char *zCsr = zNode; /* Cursor to iterate through node */
1545: const char *zEnd = &zCsr[nNode];/* End of interior node buffer */
1546: char *zBuffer = 0; /* Buffer to load terms into */
1547: int nAlloc = 0; /* Size of allocated buffer */
1548: int isFirstTerm = 1; /* True when processing first term on page */
1549: sqlite3_int64 iChild; /* Block id of child node to descend to */
1550:
1551: /* Skip over the 'height' varint that occurs at the start of every
1552: ** interior node. Then load the blockid of the left-child of the b-tree
1553: ** node into variable iChild.
1554: **
1555: ** Even if the data structure on disk is corrupted, this (reading two
1556: ** varints from the buffer) does not risk an overread. If zNode is a
1557: ** root node, then the buffer comes from a SELECT statement. SQLite does
1558: ** not make this guarantee explicitly, but in practice there are always
1559: ** either more than 20 bytes of allocated space following the nNode bytes of
1560: ** contents, or two zero bytes. Or, if the node is read from the %_segments
1561: ** table, then there are always 20 bytes of zeroed padding following the
1562: ** nNode bytes of content (see sqlite3Fts3ReadBlock() for details).
1563: */
1564: zCsr += sqlite3Fts3GetVarint(zCsr, &iChild);
1565: zCsr += sqlite3Fts3GetVarint(zCsr, &iChild);
1566: if( zCsr>zEnd ){
1567: return FTS_CORRUPT_VTAB;
1568: }
1569:
1570: while( zCsr<zEnd && (piFirst || piLast) ){
1571: int cmp; /* memcmp() result */
1572: int nSuffix; /* Size of term suffix */
1573: int nPrefix = 0; /* Size of term prefix */
1574: int nBuffer; /* Total term size */
1575:
1576: /* Load the next term on the node into zBuffer. Use realloc() to expand
1577: ** the size of zBuffer if required. */
1578: if( !isFirstTerm ){
1579: zCsr += sqlite3Fts3GetVarint32(zCsr, &nPrefix);
1580: }
1581: isFirstTerm = 0;
1582: zCsr += sqlite3Fts3GetVarint32(zCsr, &nSuffix);
1583:
1584: if( nPrefix<0 || nSuffix<0 || &zCsr[nSuffix]>zEnd ){
1585: rc = FTS_CORRUPT_VTAB;
1586: goto finish_scan;
1587: }
1588: if( nPrefix+nSuffix>nAlloc ){
1589: char *zNew;
1590: nAlloc = (nPrefix+nSuffix) * 2;
1591: zNew = (char *)sqlite3_realloc(zBuffer, nAlloc);
1592: if( !zNew ){
1593: rc = SQLITE_NOMEM;
1594: goto finish_scan;
1595: }
1596: zBuffer = zNew;
1597: }
1598: assert( zBuffer );
1599: memcpy(&zBuffer[nPrefix], zCsr, nSuffix);
1600: nBuffer = nPrefix + nSuffix;
1601: zCsr += nSuffix;
1602:
1603: /* Compare the term we are searching for with the term just loaded from
1604: ** the interior node. If the specified term is greater than or equal
1605: ** to the term from the interior node, then all terms on the sub-tree
1606: ** headed by node iChild are smaller than zTerm. No need to search
1607: ** iChild.
1608: **
1609: ** If the interior node term is larger than the specified term, then
1610: ** the tree headed by iChild may contain the specified term.
1611: */
1612: cmp = memcmp(zTerm, zBuffer, (nBuffer>nTerm ? nTerm : nBuffer));
1613: if( piFirst && (cmp<0 || (cmp==0 && nBuffer>nTerm)) ){
1614: *piFirst = iChild;
1615: piFirst = 0;
1616: }
1617:
1618: if( piLast && cmp<0 ){
1619: *piLast = iChild;
1620: piLast = 0;
1621: }
1622:
1623: iChild++;
1624: };
1625:
1626: if( piFirst ) *piFirst = iChild;
1627: if( piLast ) *piLast = iChild;
1628:
1629: finish_scan:
1630: sqlite3_free(zBuffer);
1631: return rc;
1632: }
1633:
1634:
1635: /*
1636: ** The buffer pointed to by argument zNode (size nNode bytes) contains an
1637: ** interior node of a b-tree segment. The zTerm buffer (size nTerm bytes)
1638: ** contains a term. This function searches the sub-tree headed by the zNode
1639: ** node for the range of leaf nodes that may contain the specified term
1640: ** or terms for which the specified term is a prefix.
1641: **
1642: ** If piLeaf is not NULL, then *piLeaf is set to the blockid of the
1643: ** left-most leaf node in the tree that may contain the specified term.
1644: ** If piLeaf2 is not NULL, then *piLeaf2 is set to the blockid of the
1645: ** right-most leaf node that may contain a term for which the specified
1646: ** term is a prefix.
1647: **
1648: ** It is possible that the range of returned leaf nodes does not contain
1649: ** the specified term or any terms for which it is a prefix. However, if the
1650: ** segment does contain any such terms, they are stored within the identified
1651: ** range. Because this function only inspects interior segment nodes (and
1652: ** never loads leaf nodes into memory), it is not possible to be sure.
1653: **
1654: ** If an error occurs, an error code other than SQLITE_OK is returned.
1655: */
1656: static int fts3SelectLeaf(
1657: Fts3Table *p, /* Virtual table handle */
1658: const char *zTerm, /* Term to select leaves for */
1659: int nTerm, /* Size of term zTerm in bytes */
1660: const char *zNode, /* Buffer containing segment interior node */
1661: int nNode, /* Size of buffer at zNode */
1662: sqlite3_int64 *piLeaf, /* Selected leaf node */
1663: sqlite3_int64 *piLeaf2 /* Selected leaf node */
1664: ){
1665: int rc; /* Return code */
1666: int iHeight; /* Height of this node in tree */
1667:
1668: assert( piLeaf || piLeaf2 );
1669:
1670: sqlite3Fts3GetVarint32(zNode, &iHeight);
1671: rc = fts3ScanInteriorNode(zTerm, nTerm, zNode, nNode, piLeaf, piLeaf2);
1672: assert( !piLeaf2 || !piLeaf || rc!=SQLITE_OK || (*piLeaf<=*piLeaf2) );
1673:
1674: if( rc==SQLITE_OK && iHeight>1 ){
1675: char *zBlob = 0; /* Blob read from %_segments table */
1676: int nBlob; /* Size of zBlob in bytes */
1677:
1678: if( piLeaf && piLeaf2 && (*piLeaf!=*piLeaf2) ){
1679: rc = sqlite3Fts3ReadBlock(p, *piLeaf, &zBlob, &nBlob, 0);
1680: if( rc==SQLITE_OK ){
1681: rc = fts3SelectLeaf(p, zTerm, nTerm, zBlob, nBlob, piLeaf, 0);
1682: }
1683: sqlite3_free(zBlob);
1684: piLeaf = 0;
1685: zBlob = 0;
1686: }
1687:
1688: if( rc==SQLITE_OK ){
1689: rc = sqlite3Fts3ReadBlock(p, piLeaf?*piLeaf:*piLeaf2, &zBlob, &nBlob, 0);
1690: }
1691: if( rc==SQLITE_OK ){
1692: rc = fts3SelectLeaf(p, zTerm, nTerm, zBlob, nBlob, piLeaf, piLeaf2);
1693: }
1694: sqlite3_free(zBlob);
1695: }
1696:
1697: return rc;
1698: }
1699:
1700: /*
1701: ** This function is used to create delta-encoded serialized lists of FTS3
1702: ** varints. Each call to this function appends a single varint to a list.
1703: */
1704: static void fts3PutDeltaVarint(
1705: char **pp, /* IN/OUT: Output pointer */
1706: sqlite3_int64 *piPrev, /* IN/OUT: Previous value written to list */
1707: sqlite3_int64 iVal /* Write this value to the list */
1708: ){
1709: assert( iVal-*piPrev > 0 || (*piPrev==0 && iVal==0) );
1710: *pp += sqlite3Fts3PutVarint(*pp, iVal-*piPrev);
1711: *piPrev = iVal;
1712: }
1713:
1714: /*
1715: ** When this function is called, *ppPoslist is assumed to point to the
1716: ** start of a position-list. After it returns, *ppPoslist points to the
1717: ** first byte after the position-list.
1718: **
1719: ** A position list is list of positions (delta encoded) and columns for
1720: ** a single document record of a doclist. So, in other words, this
1721: ** routine advances *ppPoslist so that it points to the next docid in
1722: ** the doclist, or to the first byte past the end of the doclist.
1723: **
1724: ** If pp is not NULL, then the contents of the position list are copied
1725: ** to *pp. *pp is set to point to the first byte past the last byte copied
1726: ** before this function returns.
1727: */
1728: static void fts3PoslistCopy(char **pp, char **ppPoslist){
1729: char *pEnd = *ppPoslist;
1730: char c = 0;
1731:
1732: /* The end of a position list is marked by a zero encoded as an FTS3
1733: ** varint. A single POS_END (0) byte. Except, if the 0 byte is preceded by
1734: ** a byte with the 0x80 bit set, then it is not a varint 0, but the tail
1735: ** of some other, multi-byte, value.
1736: **
1737: ** The following while-loop moves pEnd to point to the first byte that is not
1738: ** immediately preceded by a byte with the 0x80 bit set. Then increments
1739: ** pEnd once more so that it points to the byte immediately following the
1740: ** last byte in the position-list.
1741: */
1742: while( *pEnd | c ){
1743: c = *pEnd++ & 0x80;
1744: testcase( c!=0 && (*pEnd)==0 );
1745: }
1746: pEnd++; /* Advance past the POS_END terminator byte */
1747:
1748: if( pp ){
1749: int n = (int)(pEnd - *ppPoslist);
1750: char *p = *pp;
1751: memcpy(p, *ppPoslist, n);
1752: p += n;
1753: *pp = p;
1754: }
1755: *ppPoslist = pEnd;
1756: }
1757:
1758: /*
1759: ** When this function is called, *ppPoslist is assumed to point to the
1760: ** start of a column-list. After it returns, *ppPoslist points to the
1761: ** to the terminator (POS_COLUMN or POS_END) byte of the column-list.
1762: **
1763: ** A column-list is list of delta-encoded positions for a single column
1764: ** within a single document within a doclist.
1765: **
1766: ** The column-list is terminated either by a POS_COLUMN varint (1) or
1767: ** a POS_END varint (0). This routine leaves *ppPoslist pointing to
1768: ** the POS_COLUMN or POS_END that terminates the column-list.
1769: **
1770: ** If pp is not NULL, then the contents of the column-list are copied
1771: ** to *pp. *pp is set to point to the first byte past the last byte copied
1772: ** before this function returns. The POS_COLUMN or POS_END terminator
1773: ** is not copied into *pp.
1774: */
1775: static void fts3ColumnlistCopy(char **pp, char **ppPoslist){
1776: char *pEnd = *ppPoslist;
1777: char c = 0;
1778:
1779: /* A column-list is terminated by either a 0x01 or 0x00 byte that is
1780: ** not part of a multi-byte varint.
1781: */
1782: while( 0xFE & (*pEnd | c) ){
1783: c = *pEnd++ & 0x80;
1784: testcase( c!=0 && ((*pEnd)&0xfe)==0 );
1785: }
1786: if( pp ){
1787: int n = (int)(pEnd - *ppPoslist);
1788: char *p = *pp;
1789: memcpy(p, *ppPoslist, n);
1790: p += n;
1791: *pp = p;
1792: }
1793: *ppPoslist = pEnd;
1794: }
1795:
1796: /*
1797: ** Value used to signify the end of an position-list. This is safe because
1798: ** it is not possible to have a document with 2^31 terms.
1799: */
1800: #define POSITION_LIST_END 0x7fffffff
1801:
1802: /*
1803: ** This function is used to help parse position-lists. When this function is
1804: ** called, *pp may point to the start of the next varint in the position-list
1805: ** being parsed, or it may point to 1 byte past the end of the position-list
1806: ** (in which case **pp will be a terminator bytes POS_END (0) or
1807: ** (1)).
1808: **
1809: ** If *pp points past the end of the current position-list, set *pi to
1810: ** POSITION_LIST_END and return. Otherwise, read the next varint from *pp,
1811: ** increment the current value of *pi by the value read, and set *pp to
1812: ** point to the next value before returning.
1813: **
1814: ** Before calling this routine *pi must be initialized to the value of
1815: ** the previous position, or zero if we are reading the first position
1816: ** in the position-list. Because positions are delta-encoded, the value
1817: ** of the previous position is needed in order to compute the value of
1818: ** the next position.
1819: */
1820: static void fts3ReadNextPos(
1821: char **pp, /* IN/OUT: Pointer into position-list buffer */
1822: sqlite3_int64 *pi /* IN/OUT: Value read from position-list */
1823: ){
1824: if( (**pp)&0xFE ){
1825: fts3GetDeltaVarint(pp, pi);
1826: *pi -= 2;
1827: }else{
1828: *pi = POSITION_LIST_END;
1829: }
1830: }
1831:
1832: /*
1833: ** If parameter iCol is not 0, write an POS_COLUMN (1) byte followed by
1834: ** the value of iCol encoded as a varint to *pp. This will start a new
1835: ** column list.
1836: **
1837: ** Set *pp to point to the byte just after the last byte written before
1838: ** returning (do not modify it if iCol==0). Return the total number of bytes
1839: ** written (0 if iCol==0).
1840: */
1841: static int fts3PutColNumber(char **pp, int iCol){
1842: int n = 0; /* Number of bytes written */
1843: if( iCol ){
1844: char *p = *pp; /* Output pointer */
1845: n = 1 + sqlite3Fts3PutVarint(&p[1], iCol);
1846: *p = 0x01;
1847: *pp = &p[n];
1848: }
1849: return n;
1850: }
1851:
1852: /*
1853: ** Compute the union of two position lists. The output written
1854: ** into *pp contains all positions of both *pp1 and *pp2 in sorted
1855: ** order and with any duplicates removed. All pointers are
1856: ** updated appropriately. The caller is responsible for insuring
1857: ** that there is enough space in *pp to hold the complete output.
1858: */
1859: static void fts3PoslistMerge(
1860: char **pp, /* Output buffer */
1861: char **pp1, /* Left input list */
1862: char **pp2 /* Right input list */
1863: ){
1864: char *p = *pp;
1865: char *p1 = *pp1;
1866: char *p2 = *pp2;
1867:
1868: while( *p1 || *p2 ){
1869: int iCol1; /* The current column index in pp1 */
1870: int iCol2; /* The current column index in pp2 */
1871:
1872: if( *p1==POS_COLUMN ) sqlite3Fts3GetVarint32(&p1[1], &iCol1);
1873: else if( *p1==POS_END ) iCol1 = POSITION_LIST_END;
1874: else iCol1 = 0;
1875:
1876: if( *p2==POS_COLUMN ) sqlite3Fts3GetVarint32(&p2[1], &iCol2);
1877: else if( *p2==POS_END ) iCol2 = POSITION_LIST_END;
1878: else iCol2 = 0;
1879:
1880: if( iCol1==iCol2 ){
1881: sqlite3_int64 i1 = 0; /* Last position from pp1 */
1882: sqlite3_int64 i2 = 0; /* Last position from pp2 */
1883: sqlite3_int64 iPrev = 0;
1884: int n = fts3PutColNumber(&p, iCol1);
1885: p1 += n;
1886: p2 += n;
1887:
1888: /* At this point, both p1 and p2 point to the start of column-lists
1889: ** for the same column (the column with index iCol1 and iCol2).
1890: ** A column-list is a list of non-negative delta-encoded varints, each
1891: ** incremented by 2 before being stored. Each list is terminated by a
1892: ** POS_END (0) or POS_COLUMN (1). The following block merges the two lists
1893: ** and writes the results to buffer p. p is left pointing to the byte
1894: ** after the list written. No terminator (POS_END or POS_COLUMN) is
1895: ** written to the output.
1896: */
1897: fts3GetDeltaVarint(&p1, &i1);
1898: fts3GetDeltaVarint(&p2, &i2);
1899: do {
1900: fts3PutDeltaVarint(&p, &iPrev, (i1<i2) ? i1 : i2);
1901: iPrev -= 2;
1902: if( i1==i2 ){
1903: fts3ReadNextPos(&p1, &i1);
1904: fts3ReadNextPos(&p2, &i2);
1905: }else if( i1<i2 ){
1906: fts3ReadNextPos(&p1, &i1);
1907: }else{
1908: fts3ReadNextPos(&p2, &i2);
1909: }
1910: }while( i1!=POSITION_LIST_END || i2!=POSITION_LIST_END );
1911: }else if( iCol1<iCol2 ){
1912: p1 += fts3PutColNumber(&p, iCol1);
1913: fts3ColumnlistCopy(&p, &p1);
1914: }else{
1915: p2 += fts3PutColNumber(&p, iCol2);
1916: fts3ColumnlistCopy(&p, &p2);
1917: }
1918: }
1919:
1920: *p++ = POS_END;
1921: *pp = p;
1922: *pp1 = p1 + 1;
1923: *pp2 = p2 + 1;
1924: }
1925:
1926: /*
1927: ** This function is used to merge two position lists into one. When it is
1928: ** called, *pp1 and *pp2 must both point to position lists. A position-list is
1929: ** the part of a doclist that follows each document id. For example, if a row
1930: ** contains:
1931: **
1932: ** 'a b c'|'x y z'|'a b b a'
1933: **
1934: ** Then the position list for this row for token 'b' would consist of:
1935: **
1936: ** 0x02 0x01 0x02 0x03 0x03 0x00
1937: **
1938: ** When this function returns, both *pp1 and *pp2 are left pointing to the
1939: ** byte following the 0x00 terminator of their respective position lists.
1940: **
1941: ** If isSaveLeft is 0, an entry is added to the output position list for
1942: ** each position in *pp2 for which there exists one or more positions in
1943: ** *pp1 so that (pos(*pp2)>pos(*pp1) && pos(*pp2)-pos(*pp1)<=nToken). i.e.
1944: ** when the *pp1 token appears before the *pp2 token, but not more than nToken
1945: ** slots before it.
1946: **
1947: ** e.g. nToken==1 searches for adjacent positions.
1948: */
1949: static int fts3PoslistPhraseMerge(
1950: char **pp, /* IN/OUT: Preallocated output buffer */
1951: int nToken, /* Maximum difference in token positions */
1952: int isSaveLeft, /* Save the left position */
1953: int isExact, /* If *pp1 is exactly nTokens before *pp2 */
1954: char **pp1, /* IN/OUT: Left input list */
1955: char **pp2 /* IN/OUT: Right input list */
1956: ){
1957: char *p = *pp;
1958: char *p1 = *pp1;
1959: char *p2 = *pp2;
1960: int iCol1 = 0;
1961: int iCol2 = 0;
1962:
1963: /* Never set both isSaveLeft and isExact for the same invocation. */
1964: assert( isSaveLeft==0 || isExact==0 );
1965:
1966: assert( p!=0 && *p1!=0 && *p2!=0 );
1967: if( *p1==POS_COLUMN ){
1968: p1++;
1969: p1 += sqlite3Fts3GetVarint32(p1, &iCol1);
1970: }
1971: if( *p2==POS_COLUMN ){
1972: p2++;
1973: p2 += sqlite3Fts3GetVarint32(p2, &iCol2);
1974: }
1975:
1976: while( 1 ){
1977: if( iCol1==iCol2 ){
1978: char *pSave = p;
1979: sqlite3_int64 iPrev = 0;
1980: sqlite3_int64 iPos1 = 0;
1981: sqlite3_int64 iPos2 = 0;
1982:
1983: if( iCol1 ){
1984: *p++ = POS_COLUMN;
1985: p += sqlite3Fts3PutVarint(p, iCol1);
1986: }
1987:
1988: assert( *p1!=POS_END && *p1!=POS_COLUMN );
1989: assert( *p2!=POS_END && *p2!=POS_COLUMN );
1990: fts3GetDeltaVarint(&p1, &iPos1); iPos1 -= 2;
1991: fts3GetDeltaVarint(&p2, &iPos2); iPos2 -= 2;
1992:
1993: while( 1 ){
1994: if( iPos2==iPos1+nToken
1995: || (isExact==0 && iPos2>iPos1 && iPos2<=iPos1+nToken)
1996: ){
1997: sqlite3_int64 iSave;
1998: iSave = isSaveLeft ? iPos1 : iPos2;
1999: fts3PutDeltaVarint(&p, &iPrev, iSave+2); iPrev -= 2;
2000: pSave = 0;
2001: assert( p );
2002: }
2003: if( (!isSaveLeft && iPos2<=(iPos1+nToken)) || iPos2<=iPos1 ){
2004: if( (*p2&0xFE)==0 ) break;
2005: fts3GetDeltaVarint(&p2, &iPos2); iPos2 -= 2;
2006: }else{
2007: if( (*p1&0xFE)==0 ) break;
2008: fts3GetDeltaVarint(&p1, &iPos1); iPos1 -= 2;
2009: }
2010: }
2011:
2012: if( pSave ){
2013: assert( pp && p );
2014: p = pSave;
2015: }
2016:
2017: fts3ColumnlistCopy(0, &p1);
2018: fts3ColumnlistCopy(0, &p2);
2019: assert( (*p1&0xFE)==0 && (*p2&0xFE)==0 );
2020: if( 0==*p1 || 0==*p2 ) break;
2021:
2022: p1++;
2023: p1 += sqlite3Fts3GetVarint32(p1, &iCol1);
2024: p2++;
2025: p2 += sqlite3Fts3GetVarint32(p2, &iCol2);
2026: }
2027:
2028: /* Advance pointer p1 or p2 (whichever corresponds to the smaller of
2029: ** iCol1 and iCol2) so that it points to either the 0x00 that marks the
2030: ** end of the position list, or the 0x01 that precedes the next
2031: ** column-number in the position list.
2032: */
2033: else if( iCol1<iCol2 ){
2034: fts3ColumnlistCopy(0, &p1);
2035: if( 0==*p1 ) break;
2036: p1++;
2037: p1 += sqlite3Fts3GetVarint32(p1, &iCol1);
2038: }else{
2039: fts3ColumnlistCopy(0, &p2);
2040: if( 0==*p2 ) break;
2041: p2++;
2042: p2 += sqlite3Fts3GetVarint32(p2, &iCol2);
2043: }
2044: }
2045:
2046: fts3PoslistCopy(0, &p2);
2047: fts3PoslistCopy(0, &p1);
2048: *pp1 = p1;
2049: *pp2 = p2;
2050: if( *pp==p ){
2051: return 0;
2052: }
2053: *p++ = 0x00;
2054: *pp = p;
2055: return 1;
2056: }
2057:
2058: /*
2059: ** Merge two position-lists as required by the NEAR operator. The argument
2060: ** position lists correspond to the left and right phrases of an expression
2061: ** like:
2062: **
2063: ** "phrase 1" NEAR "phrase number 2"
2064: **
2065: ** Position list *pp1 corresponds to the left-hand side of the NEAR
2066: ** expression and *pp2 to the right. As usual, the indexes in the position
2067: ** lists are the offsets of the last token in each phrase (tokens "1" and "2"
2068: ** in the example above).
2069: **
2070: ** The output position list - written to *pp - is a copy of *pp2 with those
2071: ** entries that are not sufficiently NEAR entries in *pp1 removed.
2072: */
2073: static int fts3PoslistNearMerge(
2074: char **pp, /* Output buffer */
2075: char *aTmp, /* Temporary buffer space */
2076: int nRight, /* Maximum difference in token positions */
2077: int nLeft, /* Maximum difference in token positions */
2078: char **pp1, /* IN/OUT: Left input list */
2079: char **pp2 /* IN/OUT: Right input list */
2080: ){
2081: char *p1 = *pp1;
2082: char *p2 = *pp2;
2083:
2084: char *pTmp1 = aTmp;
2085: char *pTmp2;
2086: char *aTmp2;
2087: int res = 1;
2088:
2089: fts3PoslistPhraseMerge(&pTmp1, nRight, 0, 0, pp1, pp2);
2090: aTmp2 = pTmp2 = pTmp1;
2091: *pp1 = p1;
2092: *pp2 = p2;
2093: fts3PoslistPhraseMerge(&pTmp2, nLeft, 1, 0, pp2, pp1);
2094: if( pTmp1!=aTmp && pTmp2!=aTmp2 ){
2095: fts3PoslistMerge(pp, &aTmp, &aTmp2);
2096: }else if( pTmp1!=aTmp ){
2097: fts3PoslistCopy(pp, &aTmp);
2098: }else if( pTmp2!=aTmp2 ){
2099: fts3PoslistCopy(pp, &aTmp2);
2100: }else{
2101: res = 0;
2102: }
2103:
2104: return res;
2105: }
2106:
2107: /*
2108: ** An instance of this function is used to merge together the (potentially
2109: ** large number of) doclists for each term that matches a prefix query.
2110: ** See function fts3TermSelectMerge() for details.
2111: */
2112: typedef struct TermSelect TermSelect;
2113: struct TermSelect {
2114: char *aaOutput[16]; /* Malloc'd output buffers */
2115: int anOutput[16]; /* Size each output buffer in bytes */
2116: };
2117:
2118: /*
2119: ** This function is used to read a single varint from a buffer. Parameter
2120: ** pEnd points 1 byte past the end of the buffer. When this function is
2121: ** called, if *pp points to pEnd or greater, then the end of the buffer
2122: ** has been reached. In this case *pp is set to 0 and the function returns.
2123: **
2124: ** If *pp does not point to or past pEnd, then a single varint is read
2125: ** from *pp. *pp is then set to point 1 byte past the end of the read varint.
2126: **
2127: ** If bDescIdx is false, the value read is added to *pVal before returning.
2128: ** If it is true, the value read is subtracted from *pVal before this
2129: ** function returns.
2130: */
2131: static void fts3GetDeltaVarint3(
2132: char **pp, /* IN/OUT: Point to read varint from */
2133: char *pEnd, /* End of buffer */
2134: int bDescIdx, /* True if docids are descending */
2135: sqlite3_int64 *pVal /* IN/OUT: Integer value */
2136: ){
2137: if( *pp>=pEnd ){
2138: *pp = 0;
2139: }else{
2140: sqlite3_int64 iVal;
2141: *pp += sqlite3Fts3GetVarint(*pp, &iVal);
2142: if( bDescIdx ){
2143: *pVal -= iVal;
2144: }else{
2145: *pVal += iVal;
2146: }
2147: }
2148: }
2149:
2150: /*
2151: ** This function is used to write a single varint to a buffer. The varint
2152: ** is written to *pp. Before returning, *pp is set to point 1 byte past the
2153: ** end of the value written.
2154: **
2155: ** If *pbFirst is zero when this function is called, the value written to
2156: ** the buffer is that of parameter iVal.
2157: **
2158: ** If *pbFirst is non-zero when this function is called, then the value
2159: ** written is either (iVal-*piPrev) (if bDescIdx is zero) or (*piPrev-iVal)
2160: ** (if bDescIdx is non-zero).
2161: **
2162: ** Before returning, this function always sets *pbFirst to 1 and *piPrev
2163: ** to the value of parameter iVal.
2164: */
2165: static void fts3PutDeltaVarint3(
2166: char **pp, /* IN/OUT: Output pointer */
2167: int bDescIdx, /* True for descending docids */
2168: sqlite3_int64 *piPrev, /* IN/OUT: Previous value written to list */
2169: int *pbFirst, /* IN/OUT: True after first int written */
2170: sqlite3_int64 iVal /* Write this value to the list */
2171: ){
2172: sqlite3_int64 iWrite;
2173: if( bDescIdx==0 || *pbFirst==0 ){
2174: iWrite = iVal - *piPrev;
2175: }else{
2176: iWrite = *piPrev - iVal;
2177: }
2178: assert( *pbFirst || *piPrev==0 );
2179: assert( *pbFirst==0 || iWrite>0 );
2180: *pp += sqlite3Fts3PutVarint(*pp, iWrite);
2181: *piPrev = iVal;
2182: *pbFirst = 1;
2183: }
2184:
2185:
2186: /*
2187: ** This macro is used by various functions that merge doclists. The two
2188: ** arguments are 64-bit docid values. If the value of the stack variable
2189: ** bDescDoclist is 0 when this macro is invoked, then it returns (i1-i2).
2190: ** Otherwise, (i2-i1).
2191: **
2192: ** Using this makes it easier to write code that can merge doclists that are
2193: ** sorted in either ascending or descending order.
2194: */
2195: #define DOCID_CMP(i1, i2) ((bDescDoclist?-1:1) * (i1-i2))
2196:
2197: /*
2198: ** This function does an "OR" merge of two doclists (output contains all
2199: ** positions contained in either argument doclist). If the docids in the
2200: ** input doclists are sorted in ascending order, parameter bDescDoclist
2201: ** should be false. If they are sorted in ascending order, it should be
2202: ** passed a non-zero value.
2203: **
2204: ** If no error occurs, *paOut is set to point at an sqlite3_malloc'd buffer
2205: ** containing the output doclist and SQLITE_OK is returned. In this case
2206: ** *pnOut is set to the number of bytes in the output doclist.
2207: **
2208: ** If an error occurs, an SQLite error code is returned. The output values
2209: ** are undefined in this case.
2210: */
2211: static int fts3DoclistOrMerge(
2212: int bDescDoclist, /* True if arguments are desc */
2213: char *a1, int n1, /* First doclist */
2214: char *a2, int n2, /* Second doclist */
2215: char **paOut, int *pnOut /* OUT: Malloc'd doclist */
2216: ){
2217: sqlite3_int64 i1 = 0;
2218: sqlite3_int64 i2 = 0;
2219: sqlite3_int64 iPrev = 0;
2220: char *pEnd1 = &a1[n1];
2221: char *pEnd2 = &a2[n2];
2222: char *p1 = a1;
2223: char *p2 = a2;
2224: char *p;
2225: char *aOut;
2226: int bFirstOut = 0;
2227:
2228: *paOut = 0;
2229: *pnOut = 0;
2230:
2231: /* Allocate space for the output. Both the input and output doclists
2232: ** are delta encoded. If they are in ascending order (bDescDoclist==0),
2233: ** then the first docid in each list is simply encoded as a varint. For
2234: ** each subsequent docid, the varint stored is the difference between the
2235: ** current and previous docid (a positive number - since the list is in
2236: ** ascending order).
2237: **
2238: ** The first docid written to the output is therefore encoded using the
2239: ** same number of bytes as it is in whichever of the input lists it is
2240: ** read from. And each subsequent docid read from the same input list
2241: ** consumes either the same or less bytes as it did in the input (since
2242: ** the difference between it and the previous value in the output must
2243: ** be a positive value less than or equal to the delta value read from
2244: ** the input list). The same argument applies to all but the first docid
2245: ** read from the 'other' list. And to the contents of all position lists
2246: ** that will be copied and merged from the input to the output.
2247: **
2248: ** However, if the first docid copied to the output is a negative number,
2249: ** then the encoding of the first docid from the 'other' input list may
2250: ** be larger in the output than it was in the input (since the delta value
2251: ** may be a larger positive integer than the actual docid).
2252: **
2253: ** The space required to store the output is therefore the sum of the
2254: ** sizes of the two inputs, plus enough space for exactly one of the input
2255: ** docids to grow.
2256: **
2257: ** A symetric argument may be made if the doclists are in descending
2258: ** order.
2259: */
2260: aOut = sqlite3_malloc(n1+n2+FTS3_VARINT_MAX-1);
2261: if( !aOut ) return SQLITE_NOMEM;
2262:
2263: p = aOut;
2264: fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1);
2265: fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2);
2266: while( p1 || p2 ){
2267: sqlite3_int64 iDiff = DOCID_CMP(i1, i2);
2268:
2269: if( p2 && p1 && iDiff==0 ){
2270: fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i1);
2271: fts3PoslistMerge(&p, &p1, &p2);
2272: fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);
2273: fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);
2274: }else if( !p2 || (p1 && iDiff<0) ){
2275: fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i1);
2276: fts3PoslistCopy(&p, &p1);
2277: fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);
2278: }else{
2279: fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i2);
2280: fts3PoslistCopy(&p, &p2);
2281: fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);
2282: }
2283: }
2284:
2285: *paOut = aOut;
2286: *pnOut = (p-aOut);
2287: assert( *pnOut<=n1+n2+FTS3_VARINT_MAX-1 );
2288: return SQLITE_OK;
2289: }
2290:
2291: /*
2292: ** This function does a "phrase" merge of two doclists. In a phrase merge,
2293: ** the output contains a copy of each position from the right-hand input
2294: ** doclist for which there is a position in the left-hand input doclist
2295: ** exactly nDist tokens before it.
2296: **
2297: ** If the docids in the input doclists are sorted in ascending order,
2298: ** parameter bDescDoclist should be false. If they are sorted in ascending
2299: ** order, it should be passed a non-zero value.
2300: **
2301: ** The right-hand input doclist is overwritten by this function.
2302: */
2303: static void fts3DoclistPhraseMerge(
2304: int bDescDoclist, /* True if arguments are desc */
2305: int nDist, /* Distance from left to right (1=adjacent) */
2306: char *aLeft, int nLeft, /* Left doclist */
2307: char *aRight, int *pnRight /* IN/OUT: Right/output doclist */
2308: ){
2309: sqlite3_int64 i1 = 0;
2310: sqlite3_int64 i2 = 0;
2311: sqlite3_int64 iPrev = 0;
2312: char *pEnd1 = &aLeft[nLeft];
2313: char *pEnd2 = &aRight[*pnRight];
2314: char *p1 = aLeft;
2315: char *p2 = aRight;
2316: char *p;
2317: int bFirstOut = 0;
2318: char *aOut = aRight;
2319:
2320: assert( nDist>0 );
2321:
2322: p = aOut;
2323: fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1);
2324: fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2);
2325:
2326: while( p1 && p2 ){
2327: sqlite3_int64 iDiff = DOCID_CMP(i1, i2);
2328: if( iDiff==0 ){
2329: char *pSave = p;
2330: sqlite3_int64 iPrevSave = iPrev;
2331: int bFirstOutSave = bFirstOut;
2332:
2333: fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i1);
2334: if( 0==fts3PoslistPhraseMerge(&p, nDist, 0, 1, &p1, &p2) ){
2335: p = pSave;
2336: iPrev = iPrevSave;
2337: bFirstOut = bFirstOutSave;
2338: }
2339: fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);
2340: fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);
2341: }else if( iDiff<0 ){
2342: fts3PoslistCopy(0, &p1);
2343: fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);
2344: }else{
2345: fts3PoslistCopy(0, &p2);
2346: fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);
2347: }
2348: }
2349:
2350: *pnRight = p - aOut;
2351: }
2352:
2353: /*
2354: ** Argument pList points to a position list nList bytes in size. This
2355: ** function checks to see if the position list contains any entries for
2356: ** a token in position 0 (of any column). If so, it writes argument iDelta
2357: ** to the output buffer pOut, followed by a position list consisting only
2358: ** of the entries from pList at position 0, and terminated by an 0x00 byte.
2359: ** The value returned is the number of bytes written to pOut (if any).
2360: */
2361: int sqlite3Fts3FirstFilter(
2362: sqlite3_int64 iDelta, /* Varint that may be written to pOut */
2363: char *pList, /* Position list (no 0x00 term) */
2364: int nList, /* Size of pList in bytes */
2365: char *pOut /* Write output here */
2366: ){
2367: int nOut = 0;
2368: int bWritten = 0; /* True once iDelta has been written */
2369: char *p = pList;
2370: char *pEnd = &pList[nList];
2371:
2372: if( *p!=0x01 ){
2373: if( *p==0x02 ){
2374: nOut += sqlite3Fts3PutVarint(&pOut[nOut], iDelta);
2375: pOut[nOut++] = 0x02;
2376: bWritten = 1;
2377: }
2378: fts3ColumnlistCopy(0, &p);
2379: }
2380:
2381: while( p<pEnd && *p==0x01 ){
2382: sqlite3_int64 iCol;
2383: p++;
2384: p += sqlite3Fts3GetVarint(p, &iCol);
2385: if( *p==0x02 ){
2386: if( bWritten==0 ){
2387: nOut += sqlite3Fts3PutVarint(&pOut[nOut], iDelta);
2388: bWritten = 1;
2389: }
2390: pOut[nOut++] = 0x01;
2391: nOut += sqlite3Fts3PutVarint(&pOut[nOut], iCol);
2392: pOut[nOut++] = 0x02;
2393: }
2394: fts3ColumnlistCopy(0, &p);
2395: }
2396: if( bWritten ){
2397: pOut[nOut++] = 0x00;
2398: }
2399:
2400: return nOut;
2401: }
2402:
2403:
2404: /*
2405: ** Merge all doclists in the TermSelect.aaOutput[] array into a single
2406: ** doclist stored in TermSelect.aaOutput[0]. If successful, delete all
2407: ** other doclists (except the aaOutput[0] one) and return SQLITE_OK.
2408: **
2409: ** If an OOM error occurs, return SQLITE_NOMEM. In this case it is
2410: ** the responsibility of the caller to free any doclists left in the
2411: ** TermSelect.aaOutput[] array.
2412: */
2413: static int fts3TermSelectFinishMerge(Fts3Table *p, TermSelect *pTS){
2414: char *aOut = 0;
2415: int nOut = 0;
2416: int i;
2417:
2418: /* Loop through the doclists in the aaOutput[] array. Merge them all
2419: ** into a single doclist.
2420: */
2421: for(i=0; i<SizeofArray(pTS->aaOutput); i++){
2422: if( pTS->aaOutput[i] ){
2423: if( !aOut ){
2424: aOut = pTS->aaOutput[i];
2425: nOut = pTS->anOutput[i];
2426: pTS->aaOutput[i] = 0;
2427: }else{
2428: int nNew;
2429: char *aNew;
2430:
2431: int rc = fts3DoclistOrMerge(p->bDescIdx,
2432: pTS->aaOutput[i], pTS->anOutput[i], aOut, nOut, &aNew, &nNew
2433: );
2434: if( rc!=SQLITE_OK ){
2435: sqlite3_free(aOut);
2436: return rc;
2437: }
2438:
2439: sqlite3_free(pTS->aaOutput[i]);
2440: sqlite3_free(aOut);
2441: pTS->aaOutput[i] = 0;
2442: aOut = aNew;
2443: nOut = nNew;
2444: }
2445: }
2446: }
2447:
2448: pTS->aaOutput[0] = aOut;
2449: pTS->anOutput[0] = nOut;
2450: return SQLITE_OK;
2451: }
2452:
2453: /*
2454: ** Merge the doclist aDoclist/nDoclist into the TermSelect object passed
2455: ** as the first argument. The merge is an "OR" merge (see function
2456: ** fts3DoclistOrMerge() for details).
2457: **
2458: ** This function is called with the doclist for each term that matches
2459: ** a queried prefix. It merges all these doclists into one, the doclist
2460: ** for the specified prefix. Since there can be a very large number of
2461: ** doclists to merge, the merging is done pair-wise using the TermSelect
2462: ** object.
2463: **
2464: ** This function returns SQLITE_OK if the merge is successful, or an
2465: ** SQLite error code (SQLITE_NOMEM) if an error occurs.
2466: */
2467: static int fts3TermSelectMerge(
2468: Fts3Table *p, /* FTS table handle */
2469: TermSelect *pTS, /* TermSelect object to merge into */
2470: char *aDoclist, /* Pointer to doclist */
2471: int nDoclist /* Size of aDoclist in bytes */
2472: ){
2473: if( pTS->aaOutput[0]==0 ){
2474: /* If this is the first term selected, copy the doclist to the output
2475: ** buffer using memcpy(). */
2476: pTS->aaOutput[0] = sqlite3_malloc(nDoclist);
2477: pTS->anOutput[0] = nDoclist;
2478: if( pTS->aaOutput[0] ){
2479: memcpy(pTS->aaOutput[0], aDoclist, nDoclist);
2480: }else{
2481: return SQLITE_NOMEM;
2482: }
2483: }else{
2484: char *aMerge = aDoclist;
2485: int nMerge = nDoclist;
2486: int iOut;
2487:
2488: for(iOut=0; iOut<SizeofArray(pTS->aaOutput); iOut++){
2489: if( pTS->aaOutput[iOut]==0 ){
2490: assert( iOut>0 );
2491: pTS->aaOutput[iOut] = aMerge;
2492: pTS->anOutput[iOut] = nMerge;
2493: break;
2494: }else{
2495: char *aNew;
2496: int nNew;
2497:
2498: int rc = fts3DoclistOrMerge(p->bDescIdx, aMerge, nMerge,
2499: pTS->aaOutput[iOut], pTS->anOutput[iOut], &aNew, &nNew
2500: );
2501: if( rc!=SQLITE_OK ){
2502: if( aMerge!=aDoclist ) sqlite3_free(aMerge);
2503: return rc;
2504: }
2505:
2506: if( aMerge!=aDoclist ) sqlite3_free(aMerge);
2507: sqlite3_free(pTS->aaOutput[iOut]);
2508: pTS->aaOutput[iOut] = 0;
2509:
2510: aMerge = aNew;
2511: nMerge = nNew;
2512: if( (iOut+1)==SizeofArray(pTS->aaOutput) ){
2513: pTS->aaOutput[iOut] = aMerge;
2514: pTS->anOutput[iOut] = nMerge;
2515: }
2516: }
2517: }
2518: }
2519: return SQLITE_OK;
2520: }
2521:
2522: /*
2523: ** Append SegReader object pNew to the end of the pCsr->apSegment[] array.
2524: */
2525: static int fts3SegReaderCursorAppend(
2526: Fts3MultiSegReader *pCsr,
2527: Fts3SegReader *pNew
2528: ){
2529: if( (pCsr->nSegment%16)==0 ){
2530: Fts3SegReader **apNew;
2531: int nByte = (pCsr->nSegment + 16)*sizeof(Fts3SegReader*);
2532: apNew = (Fts3SegReader **)sqlite3_realloc(pCsr->apSegment, nByte);
2533: if( !apNew ){
2534: sqlite3Fts3SegReaderFree(pNew);
2535: return SQLITE_NOMEM;
2536: }
2537: pCsr->apSegment = apNew;
2538: }
2539: pCsr->apSegment[pCsr->nSegment++] = pNew;
2540: return SQLITE_OK;
2541: }
2542:
2543: /*
2544: ** Add seg-reader objects to the Fts3MultiSegReader object passed as the
2545: ** 8th argument.
2546: **
2547: ** This function returns SQLITE_OK if successful, or an SQLite error code
2548: ** otherwise.
2549: */
2550: static int fts3SegReaderCursor(
2551: Fts3Table *p, /* FTS3 table handle */
2552: int iIndex, /* Index to search (from 0 to p->nIndex-1) */
2553: int iLevel, /* Level of segments to scan */
2554: const char *zTerm, /* Term to query for */
2555: int nTerm, /* Size of zTerm in bytes */
2556: int isPrefix, /* True for a prefix search */
2557: int isScan, /* True to scan from zTerm to EOF */
2558: Fts3MultiSegReader *pCsr /* Cursor object to populate */
2559: ){
2560: int rc = SQLITE_OK; /* Error code */
2561: sqlite3_stmt *pStmt = 0; /* Statement to iterate through segments */
2562: int rc2; /* Result of sqlite3_reset() */
2563:
2564: /* If iLevel is less than 0 and this is not a scan, include a seg-reader
2565: ** for the pending-terms. If this is a scan, then this call must be being
2566: ** made by an fts4aux module, not an FTS table. In this case calling
2567: ** Fts3SegReaderPending might segfault, as the data structures used by
2568: ** fts4aux are not completely populated. So it's easiest to filter these
2569: ** calls out here. */
2570: if( iLevel<0 && p->aIndex ){
2571: Fts3SegReader *pSeg = 0;
2572: rc = sqlite3Fts3SegReaderPending(p, iIndex, zTerm, nTerm, isPrefix, &pSeg);
2573: if( rc==SQLITE_OK && pSeg ){
2574: rc = fts3SegReaderCursorAppend(pCsr, pSeg);
2575: }
2576: }
2577:
2578: if( iLevel!=FTS3_SEGCURSOR_PENDING ){
2579: if( rc==SQLITE_OK ){
2580: rc = sqlite3Fts3AllSegdirs(p, iIndex, iLevel, &pStmt);
2581: }
2582:
2583: while( rc==SQLITE_OK && SQLITE_ROW==(rc = sqlite3_step(pStmt)) ){
2584: Fts3SegReader *pSeg = 0;
2585:
2586: /* Read the values returned by the SELECT into local variables. */
2587: sqlite3_int64 iStartBlock = sqlite3_column_int64(pStmt, 1);
2588: sqlite3_int64 iLeavesEndBlock = sqlite3_column_int64(pStmt, 2);
2589: sqlite3_int64 iEndBlock = sqlite3_column_int64(pStmt, 3);
2590: int nRoot = sqlite3_column_bytes(pStmt, 4);
2591: char const *zRoot = sqlite3_column_blob(pStmt, 4);
2592:
2593: /* If zTerm is not NULL, and this segment is not stored entirely on its
2594: ** root node, the range of leaves scanned can be reduced. Do this. */
2595: if( iStartBlock && zTerm ){
2596: sqlite3_int64 *pi = (isPrefix ? &iLeavesEndBlock : 0);
2597: rc = fts3SelectLeaf(p, zTerm, nTerm, zRoot, nRoot, &iStartBlock, pi);
2598: if( rc!=SQLITE_OK ) goto finished;
2599: if( isPrefix==0 && isScan==0 ) iLeavesEndBlock = iStartBlock;
2600: }
2601:
2602: rc = sqlite3Fts3SegReaderNew(pCsr->nSegment+1,
2603: iStartBlock, iLeavesEndBlock, iEndBlock, zRoot, nRoot, &pSeg
2604: );
2605: if( rc!=SQLITE_OK ) goto finished;
2606: rc = fts3SegReaderCursorAppend(pCsr, pSeg);
2607: }
2608: }
2609:
2610: finished:
2611: rc2 = sqlite3_reset(pStmt);
2612: if( rc==SQLITE_DONE ) rc = rc2;
2613:
2614: return rc;
2615: }
2616:
2617: /*
2618: ** Set up a cursor object for iterating through a full-text index or a
2619: ** single level therein.
2620: */
2621: int sqlite3Fts3SegReaderCursor(
2622: Fts3Table *p, /* FTS3 table handle */
2623: int iIndex, /* Index to search (from 0 to p->nIndex-1) */
2624: int iLevel, /* Level of segments to scan */
2625: const char *zTerm, /* Term to query for */
2626: int nTerm, /* Size of zTerm in bytes */
2627: int isPrefix, /* True for a prefix search */
2628: int isScan, /* True to scan from zTerm to EOF */
2629: Fts3MultiSegReader *pCsr /* Cursor object to populate */
2630: ){
2631: assert( iIndex>=0 && iIndex<p->nIndex );
2632: assert( iLevel==FTS3_SEGCURSOR_ALL
2633: || iLevel==FTS3_SEGCURSOR_PENDING
2634: || iLevel>=0
2635: );
2636: assert( iLevel<FTS3_SEGDIR_MAXLEVEL );
2637: assert( FTS3_SEGCURSOR_ALL<0 && FTS3_SEGCURSOR_PENDING<0 );
2638: assert( isPrefix==0 || isScan==0 );
2639:
2640: /* "isScan" is only set to true by the ft4aux module, an ordinary
2641: ** full-text tables. */
2642: assert( isScan==0 || p->aIndex==0 );
2643:
2644: memset(pCsr, 0, sizeof(Fts3MultiSegReader));
2645:
2646: return fts3SegReaderCursor(
2647: p, iIndex, iLevel, zTerm, nTerm, isPrefix, isScan, pCsr
2648: );
2649: }
2650:
2651: /*
2652: ** In addition to its current configuration, have the Fts3MultiSegReader
2653: ** passed as the 4th argument also scan the doclist for term zTerm/nTerm.
2654: **
2655: ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.
2656: */
2657: static int fts3SegReaderCursorAddZero(
2658: Fts3Table *p, /* FTS virtual table handle */
2659: const char *zTerm, /* Term to scan doclist of */
2660: int nTerm, /* Number of bytes in zTerm */
2661: Fts3MultiSegReader *pCsr /* Fts3MultiSegReader to modify */
2662: ){
2663: return fts3SegReaderCursor(p, 0, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 0, 0,pCsr);
2664: }
2665:
2666: /*
2667: ** Open an Fts3MultiSegReader to scan the doclist for term zTerm/nTerm. Or,
2668: ** if isPrefix is true, to scan the doclist for all terms for which
2669: ** zTerm/nTerm is a prefix. If successful, return SQLITE_OK and write
2670: ** a pointer to the new Fts3MultiSegReader to *ppSegcsr. Otherwise, return
2671: ** an SQLite error code.
2672: **
2673: ** It is the responsibility of the caller to free this object by eventually
2674: ** passing it to fts3SegReaderCursorFree()
2675: **
2676: ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.
2677: ** Output parameter *ppSegcsr is set to 0 if an error occurs.
2678: */
2679: static int fts3TermSegReaderCursor(
2680: Fts3Cursor *pCsr, /* Virtual table cursor handle */
2681: const char *zTerm, /* Term to query for */
2682: int nTerm, /* Size of zTerm in bytes */
2683: int isPrefix, /* True for a prefix search */
2684: Fts3MultiSegReader **ppSegcsr /* OUT: Allocated seg-reader cursor */
2685: ){
2686: Fts3MultiSegReader *pSegcsr; /* Object to allocate and return */
2687: int rc = SQLITE_NOMEM; /* Return code */
2688:
2689: pSegcsr = sqlite3_malloc(sizeof(Fts3MultiSegReader));
2690: if( pSegcsr ){
2691: int i;
2692: int bFound = 0; /* True once an index has been found */
2693: Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
2694:
2695: if( isPrefix ){
2696: for(i=1; bFound==0 && i<p->nIndex; i++){
2697: if( p->aIndex[i].nPrefix==nTerm ){
2698: bFound = 1;
2699: rc = sqlite3Fts3SegReaderCursor(
2700: p, i, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 0, 0, pSegcsr);
2701: pSegcsr->bLookup = 1;
2702: }
2703: }
2704:
2705: for(i=1; bFound==0 && i<p->nIndex; i++){
2706: if( p->aIndex[i].nPrefix==nTerm+1 ){
2707: bFound = 1;
2708: rc = sqlite3Fts3SegReaderCursor(
2709: p, i, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 1, 0, pSegcsr
2710: );
2711: if( rc==SQLITE_OK ){
2712: rc = fts3SegReaderCursorAddZero(p, zTerm, nTerm, pSegcsr);
2713: }
2714: }
2715: }
2716: }
2717:
2718: if( bFound==0 ){
2719: rc = sqlite3Fts3SegReaderCursor(
2720: p, 0, FTS3_SEGCURSOR_ALL, zTerm, nTerm, isPrefix, 0, pSegcsr
2721: );
2722: pSegcsr->bLookup = !isPrefix;
2723: }
2724: }
2725:
2726: *ppSegcsr = pSegcsr;
2727: return rc;
2728: }
2729:
2730: /*
2731: ** Free an Fts3MultiSegReader allocated by fts3TermSegReaderCursor().
2732: */
2733: static void fts3SegReaderCursorFree(Fts3MultiSegReader *pSegcsr){
2734: sqlite3Fts3SegReaderFinish(pSegcsr);
2735: sqlite3_free(pSegcsr);
2736: }
2737:
2738: /*
2739: ** This function retreives the doclist for the specified term (or term
2740: ** prefix) from the database.
2741: */
2742: static int fts3TermSelect(
2743: Fts3Table *p, /* Virtual table handle */
2744: Fts3PhraseToken *pTok, /* Token to query for */
2745: int iColumn, /* Column to query (or -ve for all columns) */
2746: int *pnOut, /* OUT: Size of buffer at *ppOut */
2747: char **ppOut /* OUT: Malloced result buffer */
2748: ){
2749: int rc; /* Return code */
2750: Fts3MultiSegReader *pSegcsr; /* Seg-reader cursor for this term */
2751: TermSelect tsc; /* Object for pair-wise doclist merging */
2752: Fts3SegFilter filter; /* Segment term filter configuration */
2753:
2754: pSegcsr = pTok->pSegcsr;
2755: memset(&tsc, 0, sizeof(TermSelect));
2756:
2757: filter.flags = FTS3_SEGMENT_IGNORE_EMPTY | FTS3_SEGMENT_REQUIRE_POS
2758: | (pTok->isPrefix ? FTS3_SEGMENT_PREFIX : 0)
2759: | (pTok->bFirst ? FTS3_SEGMENT_FIRST : 0)
2760: | (iColumn<p->nColumn ? FTS3_SEGMENT_COLUMN_FILTER : 0);
2761: filter.iCol = iColumn;
2762: filter.zTerm = pTok->z;
2763: filter.nTerm = pTok->n;
2764:
2765: rc = sqlite3Fts3SegReaderStart(p, pSegcsr, &filter);
2766: while( SQLITE_OK==rc
2767: && SQLITE_ROW==(rc = sqlite3Fts3SegReaderStep(p, pSegcsr))
2768: ){
2769: rc = fts3TermSelectMerge(p, &tsc, pSegcsr->aDoclist, pSegcsr->nDoclist);
2770: }
2771:
2772: if( rc==SQLITE_OK ){
2773: rc = fts3TermSelectFinishMerge(p, &tsc);
2774: }
2775: if( rc==SQLITE_OK ){
2776: *ppOut = tsc.aaOutput[0];
2777: *pnOut = tsc.anOutput[0];
2778: }else{
2779: int i;
2780: for(i=0; i<SizeofArray(tsc.aaOutput); i++){
2781: sqlite3_free(tsc.aaOutput[i]);
2782: }
2783: }
2784:
2785: fts3SegReaderCursorFree(pSegcsr);
2786: pTok->pSegcsr = 0;
2787: return rc;
2788: }
2789:
2790: /*
2791: ** This function counts the total number of docids in the doclist stored
2792: ** in buffer aList[], size nList bytes.
2793: **
2794: ** If the isPoslist argument is true, then it is assumed that the doclist
2795: ** contains a position-list following each docid. Otherwise, it is assumed
2796: ** that the doclist is simply a list of docids stored as delta encoded
2797: ** varints.
2798: */
2799: static int fts3DoclistCountDocids(char *aList, int nList){
2800: int nDoc = 0; /* Return value */
2801: if( aList ){
2802: char *aEnd = &aList[nList]; /* Pointer to one byte after EOF */
2803: char *p = aList; /* Cursor */
2804: while( p<aEnd ){
2805: nDoc++;
2806: while( (*p++)&0x80 ); /* Skip docid varint */
2807: fts3PoslistCopy(0, &p); /* Skip over position list */
2808: }
2809: }
2810:
2811: return nDoc;
2812: }
2813:
2814: /*
2815: ** Advance the cursor to the next row in the %_content table that
2816: ** matches the search criteria. For a MATCH search, this will be
2817: ** the next row that matches. For a full-table scan, this will be
2818: ** simply the next row in the %_content table. For a docid lookup,
2819: ** this routine simply sets the EOF flag.
2820: **
2821: ** Return SQLITE_OK if nothing goes wrong. SQLITE_OK is returned
2822: ** even if we reach end-of-file. The fts3EofMethod() will be called
2823: ** subsequently to determine whether or not an EOF was hit.
2824: */
2825: static int fts3NextMethod(sqlite3_vtab_cursor *pCursor){
2826: int rc;
2827: Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;
2828: if( pCsr->eSearch==FTS3_DOCID_SEARCH || pCsr->eSearch==FTS3_FULLSCAN_SEARCH ){
2829: if( SQLITE_ROW!=sqlite3_step(pCsr->pStmt) ){
2830: pCsr->isEof = 1;
2831: rc = sqlite3_reset(pCsr->pStmt);
2832: }else{
2833: pCsr->iPrevId = sqlite3_column_int64(pCsr->pStmt, 0);
2834: rc = SQLITE_OK;
2835: }
2836: }else{
2837: rc = fts3EvalNext((Fts3Cursor *)pCursor);
2838: }
2839: assert( ((Fts3Table *)pCsr->base.pVtab)->pSegments==0 );
2840: return rc;
2841: }
2842:
2843: /*
2844: ** This is the xFilter interface for the virtual table. See
2845: ** the virtual table xFilter method documentation for additional
2846: ** information.
2847: **
2848: ** If idxNum==FTS3_FULLSCAN_SEARCH then do a full table scan against
2849: ** the %_content table.
2850: **
2851: ** If idxNum==FTS3_DOCID_SEARCH then do a docid lookup for a single entry
2852: ** in the %_content table.
2853: **
2854: ** If idxNum>=FTS3_FULLTEXT_SEARCH then use the full text index. The
2855: ** column on the left-hand side of the MATCH operator is column
2856: ** number idxNum-FTS3_FULLTEXT_SEARCH, 0 indexed. argv[0] is the right-hand
2857: ** side of the MATCH operator.
2858: */
2859: static int fts3FilterMethod(
2860: sqlite3_vtab_cursor *pCursor, /* The cursor used for this query */
2861: int idxNum, /* Strategy index */
2862: const char *idxStr, /* Unused */
2863: int nVal, /* Number of elements in apVal */
2864: sqlite3_value **apVal /* Arguments for the indexing scheme */
2865: ){
2866: int rc;
2867: char *zSql; /* SQL statement used to access %_content */
2868: Fts3Table *p = (Fts3Table *)pCursor->pVtab;
2869: Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;
2870:
2871: UNUSED_PARAMETER(idxStr);
2872: UNUSED_PARAMETER(nVal);
2873:
2874: assert( idxNum>=0 && idxNum<=(FTS3_FULLTEXT_SEARCH+p->nColumn) );
2875: assert( nVal==0 || nVal==1 );
2876: assert( (nVal==0)==(idxNum==FTS3_FULLSCAN_SEARCH) );
2877: assert( p->pSegments==0 );
2878:
2879: /* In case the cursor has been used before, clear it now. */
2880: sqlite3_finalize(pCsr->pStmt);
2881: sqlite3_free(pCsr->aDoclist);
2882: sqlite3Fts3ExprFree(pCsr->pExpr);
2883: memset(&pCursor[1], 0, sizeof(Fts3Cursor)-sizeof(sqlite3_vtab_cursor));
2884:
2885: if( idxStr ){
2886: pCsr->bDesc = (idxStr[0]=='D');
2887: }else{
2888: pCsr->bDesc = p->bDescIdx;
2889: }
2890: pCsr->eSearch = (i16)idxNum;
2891:
2892: if( idxNum!=FTS3_DOCID_SEARCH && idxNum!=FTS3_FULLSCAN_SEARCH ){
2893: int iCol = idxNum-FTS3_FULLTEXT_SEARCH;
2894: const char *zQuery = (const char *)sqlite3_value_text(apVal[0]);
2895:
2896: if( zQuery==0 && sqlite3_value_type(apVal[0])!=SQLITE_NULL ){
2897: return SQLITE_NOMEM;
2898: }
2899:
2900: rc = sqlite3Fts3ExprParse(p->pTokenizer, p->azColumn, p->bHasStat,
2901: p->nColumn, iCol, zQuery, -1, &pCsr->pExpr
2902: );
2903: if( rc!=SQLITE_OK ){
2904: if( rc==SQLITE_ERROR ){
2905: static const char *zErr = "malformed MATCH expression: [%s]";
2906: p->base.zErrMsg = sqlite3_mprintf(zErr, zQuery);
2907: }
2908: return rc;
2909: }
2910:
2911: rc = sqlite3Fts3ReadLock(p);
2912: if( rc!=SQLITE_OK ) return rc;
2913:
2914: rc = fts3EvalStart(pCsr);
2915:
2916: sqlite3Fts3SegmentsClose(p);
2917: if( rc!=SQLITE_OK ) return rc;
2918: pCsr->pNextId = pCsr->aDoclist;
2919: pCsr->iPrevId = 0;
2920: }
2921:
2922: /* Compile a SELECT statement for this cursor. For a full-table-scan, the
2923: ** statement loops through all rows of the %_content table. For a
2924: ** full-text query or docid lookup, the statement retrieves a single
2925: ** row by docid.
2926: */
2927: if( idxNum==FTS3_FULLSCAN_SEARCH ){
2928: zSql = sqlite3_mprintf(
2929: "SELECT %s ORDER BY rowid %s",
2930: p->zReadExprlist, (pCsr->bDesc ? "DESC" : "ASC")
2931: );
2932: if( zSql ){
2933: rc = sqlite3_prepare_v2(p->db, zSql, -1, &pCsr->pStmt, 0);
2934: sqlite3_free(zSql);
2935: }else{
2936: rc = SQLITE_NOMEM;
2937: }
2938: }else if( idxNum==FTS3_DOCID_SEARCH ){
2939: rc = fts3CursorSeekStmt(pCsr, &pCsr->pStmt);
2940: if( rc==SQLITE_OK ){
2941: rc = sqlite3_bind_value(pCsr->pStmt, 1, apVal[0]);
2942: }
2943: }
2944: if( rc!=SQLITE_OK ) return rc;
2945:
2946: return fts3NextMethod(pCursor);
2947: }
2948:
2949: /*
2950: ** This is the xEof method of the virtual table. SQLite calls this
2951: ** routine to find out if it has reached the end of a result set.
2952: */
2953: static int fts3EofMethod(sqlite3_vtab_cursor *pCursor){
2954: return ((Fts3Cursor *)pCursor)->isEof;
2955: }
2956:
2957: /*
2958: ** This is the xRowid method. The SQLite core calls this routine to
2959: ** retrieve the rowid for the current row of the result set. fts3
2960: ** exposes %_content.docid as the rowid for the virtual table. The
2961: ** rowid should be written to *pRowid.
2962: */
2963: static int fts3RowidMethod(sqlite3_vtab_cursor *pCursor, sqlite_int64 *pRowid){
2964: Fts3Cursor *pCsr = (Fts3Cursor *) pCursor;
2965: *pRowid = pCsr->iPrevId;
2966: return SQLITE_OK;
2967: }
2968:
2969: /*
2970: ** This is the xColumn method, called by SQLite to request a value from
2971: ** the row that the supplied cursor currently points to.
2972: */
2973: static int fts3ColumnMethod(
2974: sqlite3_vtab_cursor *pCursor, /* Cursor to retrieve value from */
2975: sqlite3_context *pContext, /* Context for sqlite3_result_xxx() calls */
2976: int iCol /* Index of column to read value from */
2977: ){
2978: int rc = SQLITE_OK; /* Return Code */
2979: Fts3Cursor *pCsr = (Fts3Cursor *) pCursor;
2980: Fts3Table *p = (Fts3Table *)pCursor->pVtab;
2981:
2982: /* The column value supplied by SQLite must be in range. */
2983: assert( iCol>=0 && iCol<=p->nColumn+1 );
2984:
2985: if( iCol==p->nColumn+1 ){
2986: /* This call is a request for the "docid" column. Since "docid" is an
2987: ** alias for "rowid", use the xRowid() method to obtain the value.
2988: */
2989: sqlite3_result_int64(pContext, pCsr->iPrevId);
2990: }else if( iCol==p->nColumn ){
2991: /* The extra column whose name is the same as the table.
2992: ** Return a blob which is a pointer to the cursor.
2993: */
2994: sqlite3_result_blob(pContext, &pCsr, sizeof(pCsr), SQLITE_TRANSIENT);
2995: }else{
2996: rc = fts3CursorSeek(0, pCsr);
2997: if( rc==SQLITE_OK && sqlite3_data_count(pCsr->pStmt)>(iCol+1) ){
2998: sqlite3_result_value(pContext, sqlite3_column_value(pCsr->pStmt, iCol+1));
2999: }
3000: }
3001:
3002: assert( ((Fts3Table *)pCsr->base.pVtab)->pSegments==0 );
3003: return rc;
3004: }
3005:
3006: /*
3007: ** This function is the implementation of the xUpdate callback used by
3008: ** FTS3 virtual tables. It is invoked by SQLite each time a row is to be
3009: ** inserted, updated or deleted.
3010: */
3011: static int fts3UpdateMethod(
3012: sqlite3_vtab *pVtab, /* Virtual table handle */
3013: int nArg, /* Size of argument array */
3014: sqlite3_value **apVal, /* Array of arguments */
3015: sqlite_int64 *pRowid /* OUT: The affected (or effected) rowid */
3016: ){
3017: return sqlite3Fts3UpdateMethod(pVtab, nArg, apVal, pRowid);
3018: }
3019:
3020: /*
3021: ** Implementation of xSync() method. Flush the contents of the pending-terms
3022: ** hash-table to the database.
3023: */
3024: static int fts3SyncMethod(sqlite3_vtab *pVtab){
3025: int rc = sqlite3Fts3PendingTermsFlush((Fts3Table *)pVtab);
3026: sqlite3Fts3SegmentsClose((Fts3Table *)pVtab);
3027: return rc;
3028: }
3029:
3030: /*
3031: ** Implementation of xBegin() method. This is a no-op.
3032: */
3033: static int fts3BeginMethod(sqlite3_vtab *pVtab){
3034: TESTONLY( Fts3Table *p = (Fts3Table*)pVtab );
3035: UNUSED_PARAMETER(pVtab);
3036: assert( p->pSegments==0 );
3037: assert( p->nPendingData==0 );
3038: assert( p->inTransaction!=1 );
3039: TESTONLY( p->inTransaction = 1 );
3040: TESTONLY( p->mxSavepoint = -1; );
3041: return SQLITE_OK;
3042: }
3043:
3044: /*
3045: ** Implementation of xCommit() method. This is a no-op. The contents of
3046: ** the pending-terms hash-table have already been flushed into the database
3047: ** by fts3SyncMethod().
3048: */
3049: static int fts3CommitMethod(sqlite3_vtab *pVtab){
3050: TESTONLY( Fts3Table *p = (Fts3Table*)pVtab );
3051: UNUSED_PARAMETER(pVtab);
3052: assert( p->nPendingData==0 );
3053: assert( p->inTransaction!=0 );
3054: assert( p->pSegments==0 );
3055: TESTONLY( p->inTransaction = 0 );
3056: TESTONLY( p->mxSavepoint = -1; );
3057: return SQLITE_OK;
3058: }
3059:
3060: /*
3061: ** Implementation of xRollback(). Discard the contents of the pending-terms
3062: ** hash-table. Any changes made to the database are reverted by SQLite.
3063: */
3064: static int fts3RollbackMethod(sqlite3_vtab *pVtab){
3065: Fts3Table *p = (Fts3Table*)pVtab;
3066: sqlite3Fts3PendingTermsClear(p);
3067: assert( p->inTransaction!=0 );
3068: TESTONLY( p->inTransaction = 0 );
3069: TESTONLY( p->mxSavepoint = -1; );
3070: return SQLITE_OK;
3071: }
3072:
3073: /*
3074: ** When called, *ppPoslist must point to the byte immediately following the
3075: ** end of a position-list. i.e. ( (*ppPoslist)[-1]==POS_END ). This function
3076: ** moves *ppPoslist so that it instead points to the first byte of the
3077: ** same position list.
3078: */
3079: static void fts3ReversePoslist(char *pStart, char **ppPoslist){
3080: char *p = &(*ppPoslist)[-2];
3081: char c = 0;
3082:
3083: while( p>pStart && (c=*p--)==0 );
3084: while( p>pStart && (*p & 0x80) | c ){
3085: c = *p--;
3086: }
3087: if( p>pStart ){ p = &p[2]; }
3088: while( *p++&0x80 );
3089: *ppPoslist = p;
3090: }
3091:
3092: /*
3093: ** Helper function used by the implementation of the overloaded snippet(),
3094: ** offsets() and optimize() SQL functions.
3095: **
3096: ** If the value passed as the third argument is a blob of size
3097: ** sizeof(Fts3Cursor*), then the blob contents are copied to the
3098: ** output variable *ppCsr and SQLITE_OK is returned. Otherwise, an error
3099: ** message is written to context pContext and SQLITE_ERROR returned. The
3100: ** string passed via zFunc is used as part of the error message.
3101: */
3102: static int fts3FunctionArg(
3103: sqlite3_context *pContext, /* SQL function call context */
3104: const char *zFunc, /* Function name */
3105: sqlite3_value *pVal, /* argv[0] passed to function */
3106: Fts3Cursor **ppCsr /* OUT: Store cursor handle here */
3107: ){
3108: Fts3Cursor *pRet;
3109: if( sqlite3_value_type(pVal)!=SQLITE_BLOB
3110: || sqlite3_value_bytes(pVal)!=sizeof(Fts3Cursor *)
3111: ){
3112: char *zErr = sqlite3_mprintf("illegal first argument to %s", zFunc);
3113: sqlite3_result_error(pContext, zErr, -1);
3114: sqlite3_free(zErr);
3115: return SQLITE_ERROR;
3116: }
3117: memcpy(&pRet, sqlite3_value_blob(pVal), sizeof(Fts3Cursor *));
3118: *ppCsr = pRet;
3119: return SQLITE_OK;
3120: }
3121:
3122: /*
3123: ** Implementation of the snippet() function for FTS3
3124: */
3125: static void fts3SnippetFunc(
3126: sqlite3_context *pContext, /* SQLite function call context */
3127: int nVal, /* Size of apVal[] array */
3128: sqlite3_value **apVal /* Array of arguments */
3129: ){
3130: Fts3Cursor *pCsr; /* Cursor handle passed through apVal[0] */
3131: const char *zStart = "<b>";
3132: const char *zEnd = "</b>";
3133: const char *zEllipsis = "<b>...</b>";
3134: int iCol = -1;
3135: int nToken = 15; /* Default number of tokens in snippet */
3136:
3137: /* There must be at least one argument passed to this function (otherwise
3138: ** the non-overloaded version would have been called instead of this one).
3139: */
3140: assert( nVal>=1 );
3141:
3142: if( nVal>6 ){
3143: sqlite3_result_error(pContext,
3144: "wrong number of arguments to function snippet()", -1);
3145: return;
3146: }
3147: if( fts3FunctionArg(pContext, "snippet", apVal[0], &pCsr) ) return;
3148:
3149: switch( nVal ){
3150: case 6: nToken = sqlite3_value_int(apVal[5]);
3151: case 5: iCol = sqlite3_value_int(apVal[4]);
3152: case 4: zEllipsis = (const char*)sqlite3_value_text(apVal[3]);
3153: case 3: zEnd = (const char*)sqlite3_value_text(apVal[2]);
3154: case 2: zStart = (const char*)sqlite3_value_text(apVal[1]);
3155: }
3156: if( !zEllipsis || !zEnd || !zStart ){
3157: sqlite3_result_error_nomem(pContext);
3158: }else if( SQLITE_OK==fts3CursorSeek(pContext, pCsr) ){
3159: sqlite3Fts3Snippet(pContext, pCsr, zStart, zEnd, zEllipsis, iCol, nToken);
3160: }
3161: }
3162:
3163: /*
3164: ** Implementation of the offsets() function for FTS3
3165: */
3166: static void fts3OffsetsFunc(
3167: sqlite3_context *pContext, /* SQLite function call context */
3168: int nVal, /* Size of argument array */
3169: sqlite3_value **apVal /* Array of arguments */
3170: ){
3171: Fts3Cursor *pCsr; /* Cursor handle passed through apVal[0] */
3172:
3173: UNUSED_PARAMETER(nVal);
3174:
3175: assert( nVal==1 );
3176: if( fts3FunctionArg(pContext, "offsets", apVal[0], &pCsr) ) return;
3177: assert( pCsr );
3178: if( SQLITE_OK==fts3CursorSeek(pContext, pCsr) ){
3179: sqlite3Fts3Offsets(pContext, pCsr);
3180: }
3181: }
3182:
3183: /*
3184: ** Implementation of the special optimize() function for FTS3. This
3185: ** function merges all segments in the database to a single segment.
3186: ** Example usage is:
3187: **
3188: ** SELECT optimize(t) FROM t LIMIT 1;
3189: **
3190: ** where 't' is the name of an FTS3 table.
3191: */
3192: static void fts3OptimizeFunc(
3193: sqlite3_context *pContext, /* SQLite function call context */
3194: int nVal, /* Size of argument array */
3195: sqlite3_value **apVal /* Array of arguments */
3196: ){
3197: int rc; /* Return code */
3198: Fts3Table *p; /* Virtual table handle */
3199: Fts3Cursor *pCursor; /* Cursor handle passed through apVal[0] */
3200:
3201: UNUSED_PARAMETER(nVal);
3202:
3203: assert( nVal==1 );
3204: if( fts3FunctionArg(pContext, "optimize", apVal[0], &pCursor) ) return;
3205: p = (Fts3Table *)pCursor->base.pVtab;
3206: assert( p );
3207:
3208: rc = sqlite3Fts3Optimize(p);
3209:
3210: switch( rc ){
3211: case SQLITE_OK:
3212: sqlite3_result_text(pContext, "Index optimized", -1, SQLITE_STATIC);
3213: break;
3214: case SQLITE_DONE:
3215: sqlite3_result_text(pContext, "Index already optimal", -1, SQLITE_STATIC);
3216: break;
3217: default:
3218: sqlite3_result_error_code(pContext, rc);
3219: break;
3220: }
3221: }
3222:
3223: /*
3224: ** Implementation of the matchinfo() function for FTS3
3225: */
3226: static void fts3MatchinfoFunc(
3227: sqlite3_context *pContext, /* SQLite function call context */
3228: int nVal, /* Size of argument array */
3229: sqlite3_value **apVal /* Array of arguments */
3230: ){
3231: Fts3Cursor *pCsr; /* Cursor handle passed through apVal[0] */
3232: assert( nVal==1 || nVal==2 );
3233: if( SQLITE_OK==fts3FunctionArg(pContext, "matchinfo", apVal[0], &pCsr) ){
3234: const char *zArg = 0;
3235: if( nVal>1 ){
3236: zArg = (const char *)sqlite3_value_text(apVal[1]);
3237: }
3238: sqlite3Fts3Matchinfo(pContext, pCsr, zArg);
3239: }
3240: }
3241:
3242: /*
3243: ** This routine implements the xFindFunction method for the FTS3
3244: ** virtual table.
3245: */
3246: static int fts3FindFunctionMethod(
3247: sqlite3_vtab *pVtab, /* Virtual table handle */
3248: int nArg, /* Number of SQL function arguments */
3249: const char *zName, /* Name of SQL function */
3250: void (**pxFunc)(sqlite3_context*,int,sqlite3_value**), /* OUT: Result */
3251: void **ppArg /* Unused */
3252: ){
3253: struct Overloaded {
3254: const char *zName;
3255: void (*xFunc)(sqlite3_context*,int,sqlite3_value**);
3256: } aOverload[] = {
3257: { "snippet", fts3SnippetFunc },
3258: { "offsets", fts3OffsetsFunc },
3259: { "optimize", fts3OptimizeFunc },
3260: { "matchinfo", fts3MatchinfoFunc },
3261: };
3262: int i; /* Iterator variable */
3263:
3264: UNUSED_PARAMETER(pVtab);
3265: UNUSED_PARAMETER(nArg);
3266: UNUSED_PARAMETER(ppArg);
3267:
3268: for(i=0; i<SizeofArray(aOverload); i++){
3269: if( strcmp(zName, aOverload[i].zName)==0 ){
3270: *pxFunc = aOverload[i].xFunc;
3271: return 1;
3272: }
3273: }
3274:
3275: /* No function of the specified name was found. Return 0. */
3276: return 0;
3277: }
3278:
3279: /*
3280: ** Implementation of FTS3 xRename method. Rename an fts3 table.
3281: */
3282: static int fts3RenameMethod(
3283: sqlite3_vtab *pVtab, /* Virtual table handle */
3284: const char *zName /* New name of table */
3285: ){
3286: Fts3Table *p = (Fts3Table *)pVtab;
3287: sqlite3 *db = p->db; /* Database connection */
3288: int rc; /* Return Code */
3289:
3290: /* As it happens, the pending terms table is always empty here. This is
3291: ** because an "ALTER TABLE RENAME TABLE" statement inside a transaction
3292: ** always opens a savepoint transaction. And the xSavepoint() method
3293: ** flushes the pending terms table. But leave the (no-op) call to
3294: ** PendingTermsFlush() in in case that changes.
3295: */
3296: assert( p->nPendingData==0 );
3297: rc = sqlite3Fts3PendingTermsFlush(p);
3298:
3299: if( p->zContentTbl==0 ){
3300: fts3DbExec(&rc, db,
3301: "ALTER TABLE %Q.'%q_content' RENAME TO '%q_content';",
3302: p->zDb, p->zName, zName
3303: );
3304: }
3305:
3306: if( p->bHasDocsize ){
3307: fts3DbExec(&rc, db,
3308: "ALTER TABLE %Q.'%q_docsize' RENAME TO '%q_docsize';",
3309: p->zDb, p->zName, zName
3310: );
3311: }
3312: if( p->bHasStat ){
3313: fts3DbExec(&rc, db,
3314: "ALTER TABLE %Q.'%q_stat' RENAME TO '%q_stat';",
3315: p->zDb, p->zName, zName
3316: );
3317: }
3318: fts3DbExec(&rc, db,
3319: "ALTER TABLE %Q.'%q_segments' RENAME TO '%q_segments';",
3320: p->zDb, p->zName, zName
3321: );
3322: fts3DbExec(&rc, db,
3323: "ALTER TABLE %Q.'%q_segdir' RENAME TO '%q_segdir';",
3324: p->zDb, p->zName, zName
3325: );
3326: return rc;
3327: }
3328:
3329: /*
3330: ** The xSavepoint() method.
3331: **
3332: ** Flush the contents of the pending-terms table to disk.
3333: */
3334: static int fts3SavepointMethod(sqlite3_vtab *pVtab, int iSavepoint){
3335: UNUSED_PARAMETER(iSavepoint);
3336: assert( ((Fts3Table *)pVtab)->inTransaction );
3337: assert( ((Fts3Table *)pVtab)->mxSavepoint < iSavepoint );
3338: TESTONLY( ((Fts3Table *)pVtab)->mxSavepoint = iSavepoint );
3339: return fts3SyncMethod(pVtab);
3340: }
3341:
3342: /*
3343: ** The xRelease() method.
3344: **
3345: ** This is a no-op.
3346: */
3347: static int fts3ReleaseMethod(sqlite3_vtab *pVtab, int iSavepoint){
3348: TESTONLY( Fts3Table *p = (Fts3Table*)pVtab );
3349: UNUSED_PARAMETER(iSavepoint);
3350: UNUSED_PARAMETER(pVtab);
3351: assert( p->inTransaction );
3352: assert( p->mxSavepoint >= iSavepoint );
3353: TESTONLY( p->mxSavepoint = iSavepoint-1 );
3354: return SQLITE_OK;
3355: }
3356:
3357: /*
3358: ** The xRollbackTo() method.
3359: **
3360: ** Discard the contents of the pending terms table.
3361: */
3362: static int fts3RollbackToMethod(sqlite3_vtab *pVtab, int iSavepoint){
3363: Fts3Table *p = (Fts3Table*)pVtab;
3364: UNUSED_PARAMETER(iSavepoint);
3365: assert( p->inTransaction );
3366: assert( p->mxSavepoint >= iSavepoint );
3367: TESTONLY( p->mxSavepoint = iSavepoint );
3368: sqlite3Fts3PendingTermsClear(p);
3369: return SQLITE_OK;
3370: }
3371:
3372: static const sqlite3_module fts3Module = {
3373: /* iVersion */ 2,
3374: /* xCreate */ fts3CreateMethod,
3375: /* xConnect */ fts3ConnectMethod,
3376: /* xBestIndex */ fts3BestIndexMethod,
3377: /* xDisconnect */ fts3DisconnectMethod,
3378: /* xDestroy */ fts3DestroyMethod,
3379: /* xOpen */ fts3OpenMethod,
3380: /* xClose */ fts3CloseMethod,
3381: /* xFilter */ fts3FilterMethod,
3382: /* xNext */ fts3NextMethod,
3383: /* xEof */ fts3EofMethod,
3384: /* xColumn */ fts3ColumnMethod,
3385: /* xRowid */ fts3RowidMethod,
3386: /* xUpdate */ fts3UpdateMethod,
3387: /* xBegin */ fts3BeginMethod,
3388: /* xSync */ fts3SyncMethod,
3389: /* xCommit */ fts3CommitMethod,
3390: /* xRollback */ fts3RollbackMethod,
3391: /* xFindFunction */ fts3FindFunctionMethod,
3392: /* xRename */ fts3RenameMethod,
3393: /* xSavepoint */ fts3SavepointMethod,
3394: /* xRelease */ fts3ReleaseMethod,
3395: /* xRollbackTo */ fts3RollbackToMethod,
3396: };
3397:
3398: /*
3399: ** This function is registered as the module destructor (called when an
3400: ** FTS3 enabled database connection is closed). It frees the memory
3401: ** allocated for the tokenizer hash table.
3402: */
3403: static void hashDestroy(void *p){
3404: Fts3Hash *pHash = (Fts3Hash *)p;
3405: sqlite3Fts3HashClear(pHash);
3406: sqlite3_free(pHash);
3407: }
3408:
3409: /*
3410: ** The fts3 built-in tokenizers - "simple", "porter" and "icu"- are
3411: ** implemented in files fts3_tokenizer1.c, fts3_porter.c and fts3_icu.c
3412: ** respectively. The following three forward declarations are for functions
3413: ** declared in these files used to retrieve the respective implementations.
3414: **
3415: ** Calling sqlite3Fts3SimpleTokenizerModule() sets the value pointed
3416: ** to by the argument to point to the "simple" tokenizer implementation.
3417: ** And so on.
3418: */
3419: void sqlite3Fts3SimpleTokenizerModule(sqlite3_tokenizer_module const**ppModule);
3420: void sqlite3Fts3PorterTokenizerModule(sqlite3_tokenizer_module const**ppModule);
3421: #ifdef SQLITE_ENABLE_ICU
3422: void sqlite3Fts3IcuTokenizerModule(sqlite3_tokenizer_module const**ppModule);
3423: #endif
3424:
3425: /*
3426: ** Initialise the fts3 extension. If this extension is built as part
3427: ** of the sqlite library, then this function is called directly by
3428: ** SQLite. If fts3 is built as a dynamically loadable extension, this
3429: ** function is called by the sqlite3_extension_init() entry point.
3430: */
3431: int sqlite3Fts3Init(sqlite3 *db){
3432: int rc = SQLITE_OK;
3433: Fts3Hash *pHash = 0;
3434: const sqlite3_tokenizer_module *pSimple = 0;
3435: const sqlite3_tokenizer_module *pPorter = 0;
3436:
3437: #ifdef SQLITE_ENABLE_ICU
3438: const sqlite3_tokenizer_module *pIcu = 0;
3439: sqlite3Fts3IcuTokenizerModule(&pIcu);
3440: #endif
3441:
3442: #ifdef SQLITE_TEST
3443: rc = sqlite3Fts3InitTerm(db);
3444: if( rc!=SQLITE_OK ) return rc;
3445: #endif
3446:
3447: rc = sqlite3Fts3InitAux(db);
3448: if( rc!=SQLITE_OK ) return rc;
3449:
3450: sqlite3Fts3SimpleTokenizerModule(&pSimple);
3451: sqlite3Fts3PorterTokenizerModule(&pPorter);
3452:
3453: /* Allocate and initialise the hash-table used to store tokenizers. */
3454: pHash = sqlite3_malloc(sizeof(Fts3Hash));
3455: if( !pHash ){
3456: rc = SQLITE_NOMEM;
3457: }else{
3458: sqlite3Fts3HashInit(pHash, FTS3_HASH_STRING, 1);
3459: }
3460:
3461: /* Load the built-in tokenizers into the hash table */
3462: if( rc==SQLITE_OK ){
3463: if( sqlite3Fts3HashInsert(pHash, "simple", 7, (void *)pSimple)
3464: || sqlite3Fts3HashInsert(pHash, "porter", 7, (void *)pPorter)
3465: #ifdef SQLITE_ENABLE_ICU
3466: || (pIcu && sqlite3Fts3HashInsert(pHash, "icu", 4, (void *)pIcu))
3467: #endif
3468: ){
3469: rc = SQLITE_NOMEM;
3470: }
3471: }
3472:
3473: #ifdef SQLITE_TEST
3474: if( rc==SQLITE_OK ){
3475: rc = sqlite3Fts3ExprInitTestInterface(db);
3476: }
3477: #endif
3478:
3479: /* Create the virtual table wrapper around the hash-table and overload
3480: ** the two scalar functions. If this is successful, register the
3481: ** module with sqlite.
3482: */
3483: if( SQLITE_OK==rc
3484: && SQLITE_OK==(rc = sqlite3Fts3InitHashTable(db, pHash, "fts3_tokenizer"))
3485: && SQLITE_OK==(rc = sqlite3_overload_function(db, "snippet", -1))
3486: && SQLITE_OK==(rc = sqlite3_overload_function(db, "offsets", 1))
3487: && SQLITE_OK==(rc = sqlite3_overload_function(db, "matchinfo", 1))
3488: && SQLITE_OK==(rc = sqlite3_overload_function(db, "matchinfo", 2))
3489: && SQLITE_OK==(rc = sqlite3_overload_function(db, "optimize", 1))
3490: ){
3491: rc = sqlite3_create_module_v2(
3492: db, "fts3", &fts3Module, (void *)pHash, hashDestroy
3493: );
3494: if( rc==SQLITE_OK ){
3495: rc = sqlite3_create_module_v2(
3496: db, "fts4", &fts3Module, (void *)pHash, 0
3497: );
3498: }
3499: return rc;
3500: }
3501:
3502: /* An error has occurred. Delete the hash table and return the error code. */
3503: assert( rc!=SQLITE_OK );
3504: if( pHash ){
3505: sqlite3Fts3HashClear(pHash);
3506: sqlite3_free(pHash);
3507: }
3508: return rc;
3509: }
3510:
3511: /*
3512: ** Allocate an Fts3MultiSegReader for each token in the expression headed
3513: ** by pExpr.
3514: **
3515: ** An Fts3SegReader object is a cursor that can seek or scan a range of
3516: ** entries within a single segment b-tree. An Fts3MultiSegReader uses multiple
3517: ** Fts3SegReader objects internally to provide an interface to seek or scan
3518: ** within the union of all segments of a b-tree. Hence the name.
3519: **
3520: ** If the allocated Fts3MultiSegReader just seeks to a single entry in a
3521: ** segment b-tree (if the term is not a prefix or it is a prefix for which
3522: ** there exists prefix b-tree of the right length) then it may be traversed
3523: ** and merged incrementally. Otherwise, it has to be merged into an in-memory
3524: ** doclist and then traversed.
3525: */
3526: static void fts3EvalAllocateReaders(
3527: Fts3Cursor *pCsr, /* FTS cursor handle */
3528: Fts3Expr *pExpr, /* Allocate readers for this expression */
3529: int *pnToken, /* OUT: Total number of tokens in phrase. */
3530: int *pnOr, /* OUT: Total number of OR nodes in expr. */
3531: int *pRc /* IN/OUT: Error code */
3532: ){
3533: if( pExpr && SQLITE_OK==*pRc ){
3534: if( pExpr->eType==FTSQUERY_PHRASE ){
3535: int i;
3536: int nToken = pExpr->pPhrase->nToken;
3537: *pnToken += nToken;
3538: for(i=0; i<nToken; i++){
3539: Fts3PhraseToken *pToken = &pExpr->pPhrase->aToken[i];
3540: int rc = fts3TermSegReaderCursor(pCsr,
3541: pToken->z, pToken->n, pToken->isPrefix, &pToken->pSegcsr
3542: );
3543: if( rc!=SQLITE_OK ){
3544: *pRc = rc;
3545: return;
3546: }
3547: }
3548: assert( pExpr->pPhrase->iDoclistToken==0 );
3549: pExpr->pPhrase->iDoclistToken = -1;
3550: }else{
3551: *pnOr += (pExpr->eType==FTSQUERY_OR);
3552: fts3EvalAllocateReaders(pCsr, pExpr->pLeft, pnToken, pnOr, pRc);
3553: fts3EvalAllocateReaders(pCsr, pExpr->pRight, pnToken, pnOr, pRc);
3554: }
3555: }
3556: }
3557:
3558: /*
3559: ** Arguments pList/nList contain the doclist for token iToken of phrase p.
3560: ** It is merged into the main doclist stored in p->doclist.aAll/nAll.
3561: **
3562: ** This function assumes that pList points to a buffer allocated using
3563: ** sqlite3_malloc(). This function takes responsibility for eventually
3564: ** freeing the buffer.
3565: */
3566: static void fts3EvalPhraseMergeToken(
3567: Fts3Table *pTab, /* FTS Table pointer */
3568: Fts3Phrase *p, /* Phrase to merge pList/nList into */
3569: int iToken, /* Token pList/nList corresponds to */
3570: char *pList, /* Pointer to doclist */
3571: int nList /* Number of bytes in pList */
3572: ){
3573: assert( iToken!=p->iDoclistToken );
3574:
3575: if( pList==0 ){
3576: sqlite3_free(p->doclist.aAll);
3577: p->doclist.aAll = 0;
3578: p->doclist.nAll = 0;
3579: }
3580:
3581: else if( p->iDoclistToken<0 ){
3582: p->doclist.aAll = pList;
3583: p->doclist.nAll = nList;
3584: }
3585:
3586: else if( p->doclist.aAll==0 ){
3587: sqlite3_free(pList);
3588: }
3589:
3590: else {
3591: char *pLeft;
3592: char *pRight;
3593: int nLeft;
3594: int nRight;
3595: int nDiff;
3596:
3597: if( p->iDoclistToken<iToken ){
3598: pLeft = p->doclist.aAll;
3599: nLeft = p->doclist.nAll;
3600: pRight = pList;
3601: nRight = nList;
3602: nDiff = iToken - p->iDoclistToken;
3603: }else{
3604: pRight = p->doclist.aAll;
3605: nRight = p->doclist.nAll;
3606: pLeft = pList;
3607: nLeft = nList;
3608: nDiff = p->iDoclistToken - iToken;
3609: }
3610:
3611: fts3DoclistPhraseMerge(pTab->bDescIdx, nDiff, pLeft, nLeft, pRight,&nRight);
3612: sqlite3_free(pLeft);
3613: p->doclist.aAll = pRight;
3614: p->doclist.nAll = nRight;
3615: }
3616:
3617: if( iToken>p->iDoclistToken ) p->iDoclistToken = iToken;
3618: }
3619:
3620: /*
3621: ** Load the doclist for phrase p into p->doclist.aAll/nAll. The loaded doclist
3622: ** does not take deferred tokens into account.
3623: **
3624: ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.
3625: */
3626: static int fts3EvalPhraseLoad(
3627: Fts3Cursor *pCsr, /* FTS Cursor handle */
3628: Fts3Phrase *p /* Phrase object */
3629: ){
3630: Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
3631: int iToken;
3632: int rc = SQLITE_OK;
3633:
3634: for(iToken=0; rc==SQLITE_OK && iToken<p->nToken; iToken++){
3635: Fts3PhraseToken *pToken = &p->aToken[iToken];
3636: assert( pToken->pDeferred==0 || pToken->pSegcsr==0 );
3637:
3638: if( pToken->pSegcsr ){
3639: int nThis = 0;
3640: char *pThis = 0;
3641: rc = fts3TermSelect(pTab, pToken, p->iColumn, &nThis, &pThis);
3642: if( rc==SQLITE_OK ){
3643: fts3EvalPhraseMergeToken(pTab, p, iToken, pThis, nThis);
3644: }
3645: }
3646: assert( pToken->pSegcsr==0 );
3647: }
3648:
3649: return rc;
3650: }
3651:
3652: /*
3653: ** This function is called on each phrase after the position lists for
3654: ** any deferred tokens have been loaded into memory. It updates the phrases
3655: ** current position list to include only those positions that are really
3656: ** instances of the phrase (after considering deferred tokens). If this
3657: ** means that the phrase does not appear in the current row, doclist.pList
3658: ** and doclist.nList are both zeroed.
3659: **
3660: ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.
3661: */
3662: static int fts3EvalDeferredPhrase(Fts3Cursor *pCsr, Fts3Phrase *pPhrase){
3663: int iToken; /* Used to iterate through phrase tokens */
3664: char *aPoslist = 0; /* Position list for deferred tokens */
3665: int nPoslist = 0; /* Number of bytes in aPoslist */
3666: int iPrev = -1; /* Token number of previous deferred token */
3667:
3668: assert( pPhrase->doclist.bFreeList==0 );
3669:
3670: for(iToken=0; iToken<pPhrase->nToken; iToken++){
3671: Fts3PhraseToken *pToken = &pPhrase->aToken[iToken];
3672: Fts3DeferredToken *pDeferred = pToken->pDeferred;
3673:
3674: if( pDeferred ){
3675: char *pList;
3676: int nList;
3677: int rc = sqlite3Fts3DeferredTokenList(pDeferred, &pList, &nList);
3678: if( rc!=SQLITE_OK ) return rc;
3679:
3680: if( pList==0 ){
3681: sqlite3_free(aPoslist);
3682: pPhrase->doclist.pList = 0;
3683: pPhrase->doclist.nList = 0;
3684: return SQLITE_OK;
3685:
3686: }else if( aPoslist==0 ){
3687: aPoslist = pList;
3688: nPoslist = nList;
3689:
3690: }else{
3691: char *aOut = pList;
3692: char *p1 = aPoslist;
3693: char *p2 = aOut;
3694:
3695: assert( iPrev>=0 );
3696: fts3PoslistPhraseMerge(&aOut, iToken-iPrev, 0, 1, &p1, &p2);
3697: sqlite3_free(aPoslist);
3698: aPoslist = pList;
3699: nPoslist = aOut - aPoslist;
3700: if( nPoslist==0 ){
3701: sqlite3_free(aPoslist);
3702: pPhrase->doclist.pList = 0;
3703: pPhrase->doclist.nList = 0;
3704: return SQLITE_OK;
3705: }
3706: }
3707: iPrev = iToken;
3708: }
3709: }
3710:
3711: if( iPrev>=0 ){
3712: int nMaxUndeferred = pPhrase->iDoclistToken;
3713: if( nMaxUndeferred<0 ){
3714: pPhrase->doclist.pList = aPoslist;
3715: pPhrase->doclist.nList = nPoslist;
3716: pPhrase->doclist.iDocid = pCsr->iPrevId;
3717: pPhrase->doclist.bFreeList = 1;
3718: }else{
3719: int nDistance;
3720: char *p1;
3721: char *p2;
3722: char *aOut;
3723:
3724: if( nMaxUndeferred>iPrev ){
3725: p1 = aPoslist;
3726: p2 = pPhrase->doclist.pList;
3727: nDistance = nMaxUndeferred - iPrev;
3728: }else{
3729: p1 = pPhrase->doclist.pList;
3730: p2 = aPoslist;
3731: nDistance = iPrev - nMaxUndeferred;
3732: }
3733:
3734: aOut = (char *)sqlite3_malloc(nPoslist+8);
3735: if( !aOut ){
3736: sqlite3_free(aPoslist);
3737: return SQLITE_NOMEM;
3738: }
3739:
3740: pPhrase->doclist.pList = aOut;
3741: if( fts3PoslistPhraseMerge(&aOut, nDistance, 0, 1, &p1, &p2) ){
3742: pPhrase->doclist.bFreeList = 1;
3743: pPhrase->doclist.nList = (aOut - pPhrase->doclist.pList);
3744: }else{
3745: sqlite3_free(aOut);
3746: pPhrase->doclist.pList = 0;
3747: pPhrase->doclist.nList = 0;
3748: }
3749: sqlite3_free(aPoslist);
3750: }
3751: }
3752:
3753: return SQLITE_OK;
3754: }
3755:
3756: /*
3757: ** This function is called for each Fts3Phrase in a full-text query
3758: ** expression to initialize the mechanism for returning rows. Once this
3759: ** function has been called successfully on an Fts3Phrase, it may be
3760: ** used with fts3EvalPhraseNext() to iterate through the matching docids.
3761: **
3762: ** If parameter bOptOk is true, then the phrase may (or may not) use the
3763: ** incremental loading strategy. Otherwise, the entire doclist is loaded into
3764: ** memory within this call.
3765: **
3766: ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.
3767: */
3768: static int fts3EvalPhraseStart(Fts3Cursor *pCsr, int bOptOk, Fts3Phrase *p){
3769: int rc; /* Error code */
3770: Fts3PhraseToken *pFirst = &p->aToken[0];
3771: Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
3772:
3773: if( pCsr->bDesc==pTab->bDescIdx
3774: && bOptOk==1
3775: && p->nToken==1
3776: && pFirst->pSegcsr
3777: && pFirst->pSegcsr->bLookup
3778: && pFirst->bFirst==0
3779: ){
3780: /* Use the incremental approach. */
3781: int iCol = (p->iColumn >= pTab->nColumn ? -1 : p->iColumn);
3782: rc = sqlite3Fts3MsrIncrStart(
3783: pTab, pFirst->pSegcsr, iCol, pFirst->z, pFirst->n);
3784: p->bIncr = 1;
3785:
3786: }else{
3787: /* Load the full doclist for the phrase into memory. */
3788: rc = fts3EvalPhraseLoad(pCsr, p);
3789: p->bIncr = 0;
3790: }
3791:
3792: assert( rc!=SQLITE_OK || p->nToken<1 || p->aToken[0].pSegcsr==0 || p->bIncr );
3793: return rc;
3794: }
3795:
3796: /*
3797: ** This function is used to iterate backwards (from the end to start)
3798: ** through doclists. It is used by this module to iterate through phrase
3799: ** doclists in reverse and by the fts3_write.c module to iterate through
3800: ** pending-terms lists when writing to databases with "order=desc".
3801: **
3802: ** The doclist may be sorted in ascending (parameter bDescIdx==0) or
3803: ** descending (parameter bDescIdx==1) order of docid. Regardless, this
3804: ** function iterates from the end of the doclist to the beginning.
3805: */
3806: void sqlite3Fts3DoclistPrev(
3807: int bDescIdx, /* True if the doclist is desc */
3808: char *aDoclist, /* Pointer to entire doclist */
3809: int nDoclist, /* Length of aDoclist in bytes */
3810: char **ppIter, /* IN/OUT: Iterator pointer */
3811: sqlite3_int64 *piDocid, /* IN/OUT: Docid pointer */
3812: int *pnList, /* IN/OUT: List length pointer */
3813: u8 *pbEof /* OUT: End-of-file flag */
3814: ){
3815: char *p = *ppIter;
3816:
3817: assert( nDoclist>0 );
3818: assert( *pbEof==0 );
3819: assert( p || *piDocid==0 );
3820: assert( !p || (p>aDoclist && p<&aDoclist[nDoclist]) );
3821:
3822: if( p==0 ){
3823: sqlite3_int64 iDocid = 0;
3824: char *pNext = 0;
3825: char *pDocid = aDoclist;
3826: char *pEnd = &aDoclist[nDoclist];
3827: int iMul = 1;
3828:
3829: while( pDocid<pEnd ){
3830: sqlite3_int64 iDelta;
3831: pDocid += sqlite3Fts3GetVarint(pDocid, &iDelta);
3832: iDocid += (iMul * iDelta);
3833: pNext = pDocid;
3834: fts3PoslistCopy(0, &pDocid);
3835: while( pDocid<pEnd && *pDocid==0 ) pDocid++;
3836: iMul = (bDescIdx ? -1 : 1);
3837: }
3838:
3839: *pnList = pEnd - pNext;
3840: *ppIter = pNext;
3841: *piDocid = iDocid;
3842: }else{
3843: int iMul = (bDescIdx ? -1 : 1);
3844: sqlite3_int64 iDelta;
3845: fts3GetReverseVarint(&p, aDoclist, &iDelta);
3846: *piDocid -= (iMul * iDelta);
3847:
3848: if( p==aDoclist ){
3849: *pbEof = 1;
3850: }else{
3851: char *pSave = p;
3852: fts3ReversePoslist(aDoclist, &p);
3853: *pnList = (pSave - p);
3854: }
3855: *ppIter = p;
3856: }
3857: }
3858:
3859: /*
3860: ** Attempt to move the phrase iterator to point to the next matching docid.
3861: ** If an error occurs, return an SQLite error code. Otherwise, return
3862: ** SQLITE_OK.
3863: **
3864: ** If there is no "next" entry and no error occurs, then *pbEof is set to
3865: ** 1 before returning. Otherwise, if no error occurs and the iterator is
3866: ** successfully advanced, *pbEof is set to 0.
3867: */
3868: static int fts3EvalPhraseNext(
3869: Fts3Cursor *pCsr, /* FTS Cursor handle */
3870: Fts3Phrase *p, /* Phrase object to advance to next docid */
3871: u8 *pbEof /* OUT: Set to 1 if EOF */
3872: ){
3873: int rc = SQLITE_OK;
3874: Fts3Doclist *pDL = &p->doclist;
3875: Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
3876:
3877: if( p->bIncr ){
3878: assert( p->nToken==1 );
3879: assert( pDL->pNextDocid==0 );
3880: rc = sqlite3Fts3MsrIncrNext(pTab, p->aToken[0].pSegcsr,
3881: &pDL->iDocid, &pDL->pList, &pDL->nList
3882: );
3883: if( rc==SQLITE_OK && !pDL->pList ){
3884: *pbEof = 1;
3885: }
3886: }else if( pCsr->bDesc!=pTab->bDescIdx && pDL->nAll ){
3887: sqlite3Fts3DoclistPrev(pTab->bDescIdx, pDL->aAll, pDL->nAll,
3888: &pDL->pNextDocid, &pDL->iDocid, &pDL->nList, pbEof
3889: );
3890: pDL->pList = pDL->pNextDocid;
3891: }else{
3892: char *pIter; /* Used to iterate through aAll */
3893: char *pEnd = &pDL->aAll[pDL->nAll]; /* 1 byte past end of aAll */
3894: if( pDL->pNextDocid ){
3895: pIter = pDL->pNextDocid;
3896: }else{
3897: pIter = pDL->aAll;
3898: }
3899:
3900: if( pIter>=pEnd ){
3901: /* We have already reached the end of this doclist. EOF. */
3902: *pbEof = 1;
3903: }else{
3904: sqlite3_int64 iDelta;
3905: pIter += sqlite3Fts3GetVarint(pIter, &iDelta);
3906: if( pTab->bDescIdx==0 || pDL->pNextDocid==0 ){
3907: pDL->iDocid += iDelta;
3908: }else{
3909: pDL->iDocid -= iDelta;
3910: }
3911: pDL->pList = pIter;
3912: fts3PoslistCopy(0, &pIter);
3913: pDL->nList = (pIter - pDL->pList);
3914:
3915: /* pIter now points just past the 0x00 that terminates the position-
3916: ** list for document pDL->iDocid. However, if this position-list was
3917: ** edited in place by fts3EvalNearTrim(), then pIter may not actually
3918: ** point to the start of the next docid value. The following line deals
3919: ** with this case by advancing pIter past the zero-padding added by
3920: ** fts3EvalNearTrim(). */
3921: while( pIter<pEnd && *pIter==0 ) pIter++;
3922:
3923: pDL->pNextDocid = pIter;
3924: assert( pIter>=&pDL->aAll[pDL->nAll] || *pIter );
3925: *pbEof = 0;
3926: }
3927: }
3928:
3929: return rc;
3930: }
3931:
3932: /*
3933: **
3934: ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.
3935: ** Otherwise, fts3EvalPhraseStart() is called on all phrases within the
3936: ** expression. Also the Fts3Expr.bDeferred variable is set to true for any
3937: ** expressions for which all descendent tokens are deferred.
3938: **
3939: ** If parameter bOptOk is zero, then it is guaranteed that the
3940: ** Fts3Phrase.doclist.aAll/nAll variables contain the entire doclist for
3941: ** each phrase in the expression (subject to deferred token processing).
3942: ** Or, if bOptOk is non-zero, then one or more tokens within the expression
3943: ** may be loaded incrementally, meaning doclist.aAll/nAll is not available.
3944: **
3945: ** If an error occurs within this function, *pRc is set to an SQLite error
3946: ** code before returning.
3947: */
3948: static void fts3EvalStartReaders(
3949: Fts3Cursor *pCsr, /* FTS Cursor handle */
3950: Fts3Expr *pExpr, /* Expression to initialize phrases in */
3951: int bOptOk, /* True to enable incremental loading */
3952: int *pRc /* IN/OUT: Error code */
3953: ){
3954: if( pExpr && SQLITE_OK==*pRc ){
3955: if( pExpr->eType==FTSQUERY_PHRASE ){
3956: int i;
3957: int nToken = pExpr->pPhrase->nToken;
3958: for(i=0; i<nToken; i++){
3959: if( pExpr->pPhrase->aToken[i].pDeferred==0 ) break;
3960: }
3961: pExpr->bDeferred = (i==nToken);
3962: *pRc = fts3EvalPhraseStart(pCsr, bOptOk, pExpr->pPhrase);
3963: }else{
3964: fts3EvalStartReaders(pCsr, pExpr->pLeft, bOptOk, pRc);
3965: fts3EvalStartReaders(pCsr, pExpr->pRight, bOptOk, pRc);
3966: pExpr->bDeferred = (pExpr->pLeft->bDeferred && pExpr->pRight->bDeferred);
3967: }
3968: }
3969: }
3970:
3971: /*
3972: ** An array of the following structures is assembled as part of the process
3973: ** of selecting tokens to defer before the query starts executing (as part
3974: ** of the xFilter() method). There is one element in the array for each
3975: ** token in the FTS expression.
3976: **
3977: ** Tokens are divided into AND/NEAR clusters. All tokens in a cluster belong
3978: ** to phrases that are connected only by AND and NEAR operators (not OR or
3979: ** NOT). When determining tokens to defer, each AND/NEAR cluster is considered
3980: ** separately. The root of a tokens AND/NEAR cluster is stored in
3981: ** Fts3TokenAndCost.pRoot.
3982: */
3983: typedef struct Fts3TokenAndCost Fts3TokenAndCost;
3984: struct Fts3TokenAndCost {
3985: Fts3Phrase *pPhrase; /* The phrase the token belongs to */
3986: int iToken; /* Position of token in phrase */
3987: Fts3PhraseToken *pToken; /* The token itself */
3988: Fts3Expr *pRoot; /* Root of NEAR/AND cluster */
3989: int nOvfl; /* Number of overflow pages to load doclist */
3990: int iCol; /* The column the token must match */
3991: };
3992:
3993: /*
3994: ** This function is used to populate an allocated Fts3TokenAndCost array.
3995: **
3996: ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.
3997: ** Otherwise, if an error occurs during execution, *pRc is set to an
3998: ** SQLite error code.
3999: */
4000: static void fts3EvalTokenCosts(
4001: Fts3Cursor *pCsr, /* FTS Cursor handle */
4002: Fts3Expr *pRoot, /* Root of current AND/NEAR cluster */
4003: Fts3Expr *pExpr, /* Expression to consider */
4004: Fts3TokenAndCost **ppTC, /* Write new entries to *(*ppTC)++ */
4005: Fts3Expr ***ppOr, /* Write new OR root to *(*ppOr)++ */
4006: int *pRc /* IN/OUT: Error code */
4007: ){
4008: if( *pRc==SQLITE_OK ){
4009: if( pExpr->eType==FTSQUERY_PHRASE ){
4010: Fts3Phrase *pPhrase = pExpr->pPhrase;
4011: int i;
4012: for(i=0; *pRc==SQLITE_OK && i<pPhrase->nToken; i++){
4013: Fts3TokenAndCost *pTC = (*ppTC)++;
4014: pTC->pPhrase = pPhrase;
4015: pTC->iToken = i;
4016: pTC->pRoot = pRoot;
4017: pTC->pToken = &pPhrase->aToken[i];
4018: pTC->iCol = pPhrase->iColumn;
4019: *pRc = sqlite3Fts3MsrOvfl(pCsr, pTC->pToken->pSegcsr, &pTC->nOvfl);
4020: }
4021: }else if( pExpr->eType!=FTSQUERY_NOT ){
4022: assert( pExpr->eType==FTSQUERY_OR
4023: || pExpr->eType==FTSQUERY_AND
4024: || pExpr->eType==FTSQUERY_NEAR
4025: );
4026: assert( pExpr->pLeft && pExpr->pRight );
4027: if( pExpr->eType==FTSQUERY_OR ){
4028: pRoot = pExpr->pLeft;
4029: **ppOr = pRoot;
4030: (*ppOr)++;
4031: }
4032: fts3EvalTokenCosts(pCsr, pRoot, pExpr->pLeft, ppTC, ppOr, pRc);
4033: if( pExpr->eType==FTSQUERY_OR ){
4034: pRoot = pExpr->pRight;
4035: **ppOr = pRoot;
4036: (*ppOr)++;
4037: }
4038: fts3EvalTokenCosts(pCsr, pRoot, pExpr->pRight, ppTC, ppOr, pRc);
4039: }
4040: }
4041: }
4042:
4043: /*
4044: ** Determine the average document (row) size in pages. If successful,
4045: ** write this value to *pnPage and return SQLITE_OK. Otherwise, return
4046: ** an SQLite error code.
4047: **
4048: ** The average document size in pages is calculated by first calculating
4049: ** determining the average size in bytes, B. If B is less than the amount
4050: ** of data that will fit on a single leaf page of an intkey table in
4051: ** this database, then the average docsize is 1. Otherwise, it is 1 plus
4052: ** the number of overflow pages consumed by a record B bytes in size.
4053: */
4054: static int fts3EvalAverageDocsize(Fts3Cursor *pCsr, int *pnPage){
4055: if( pCsr->nRowAvg==0 ){
4056: /* The average document size, which is required to calculate the cost
4057: ** of each doclist, has not yet been determined. Read the required
4058: ** data from the %_stat table to calculate it.
4059: **
4060: ** Entry 0 of the %_stat table is a blob containing (nCol+1) FTS3
4061: ** varints, where nCol is the number of columns in the FTS3 table.
4062: ** The first varint is the number of documents currently stored in
4063: ** the table. The following nCol varints contain the total amount of
4064: ** data stored in all rows of each column of the table, from left
4065: ** to right.
4066: */
4067: int rc;
4068: Fts3Table *p = (Fts3Table*)pCsr->base.pVtab;
4069: sqlite3_stmt *pStmt;
4070: sqlite3_int64 nDoc = 0;
4071: sqlite3_int64 nByte = 0;
4072: const char *pEnd;
4073: const char *a;
4074:
4075: rc = sqlite3Fts3SelectDoctotal(p, &pStmt);
4076: if( rc!=SQLITE_OK ) return rc;
4077: a = sqlite3_column_blob(pStmt, 0);
4078: assert( a );
4079:
4080: pEnd = &a[sqlite3_column_bytes(pStmt, 0)];
4081: a += sqlite3Fts3GetVarint(a, &nDoc);
4082: while( a<pEnd ){
4083: a += sqlite3Fts3GetVarint(a, &nByte);
4084: }
4085: if( nDoc==0 || nByte==0 ){
4086: sqlite3_reset(pStmt);
4087: return FTS_CORRUPT_VTAB;
4088: }
4089:
4090: pCsr->nDoc = nDoc;
4091: pCsr->nRowAvg = (int)(((nByte / nDoc) + p->nPgsz) / p->nPgsz);
4092: assert( pCsr->nRowAvg>0 );
4093: rc = sqlite3_reset(pStmt);
4094: if( rc!=SQLITE_OK ) return rc;
4095: }
4096:
4097: *pnPage = pCsr->nRowAvg;
4098: return SQLITE_OK;
4099: }
4100:
4101: /*
4102: ** This function is called to select the tokens (if any) that will be
4103: ** deferred. The array aTC[] has already been populated when this is
4104: ** called.
4105: **
4106: ** This function is called once for each AND/NEAR cluster in the
4107: ** expression. Each invocation determines which tokens to defer within
4108: ** the cluster with root node pRoot. See comments above the definition
4109: ** of struct Fts3TokenAndCost for more details.
4110: **
4111: ** If no error occurs, SQLITE_OK is returned and sqlite3Fts3DeferToken()
4112: ** called on each token to defer. Otherwise, an SQLite error code is
4113: ** returned.
4114: */
4115: static int fts3EvalSelectDeferred(
4116: Fts3Cursor *pCsr, /* FTS Cursor handle */
4117: Fts3Expr *pRoot, /* Consider tokens with this root node */
4118: Fts3TokenAndCost *aTC, /* Array of expression tokens and costs */
4119: int nTC /* Number of entries in aTC[] */
4120: ){
4121: Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
4122: int nDocSize = 0; /* Number of pages per doc loaded */
4123: int rc = SQLITE_OK; /* Return code */
4124: int ii; /* Iterator variable for various purposes */
4125: int nOvfl = 0; /* Total overflow pages used by doclists */
4126: int nToken = 0; /* Total number of tokens in cluster */
4127:
4128: int nMinEst = 0; /* The minimum count for any phrase so far. */
4129: int nLoad4 = 1; /* (Phrases that will be loaded)^4. */
4130:
4131: /* Tokens are never deferred for FTS tables created using the content=xxx
4132: ** option. The reason being that it is not guaranteed that the content
4133: ** table actually contains the same data as the index. To prevent this from
4134: ** causing any problems, the deferred token optimization is completely
4135: ** disabled for content=xxx tables. */
4136: if( pTab->zContentTbl ){
4137: return SQLITE_OK;
4138: }
4139:
4140: /* Count the tokens in this AND/NEAR cluster. If none of the doclists
4141: ** associated with the tokens spill onto overflow pages, or if there is
4142: ** only 1 token, exit early. No tokens to defer in this case. */
4143: for(ii=0; ii<nTC; ii++){
4144: if( aTC[ii].pRoot==pRoot ){
4145: nOvfl += aTC[ii].nOvfl;
4146: nToken++;
4147: }
4148: }
4149: if( nOvfl==0 || nToken<2 ) return SQLITE_OK;
4150:
4151: /* Obtain the average docsize (in pages). */
4152: rc = fts3EvalAverageDocsize(pCsr, &nDocSize);
4153: assert( rc!=SQLITE_OK || nDocSize>0 );
4154:
4155:
4156: /* Iterate through all tokens in this AND/NEAR cluster, in ascending order
4157: ** of the number of overflow pages that will be loaded by the pager layer
4158: ** to retrieve the entire doclist for the token from the full-text index.
4159: ** Load the doclists for tokens that are either:
4160: **
4161: ** a. The cheapest token in the entire query (i.e. the one visited by the
4162: ** first iteration of this loop), or
4163: **
4164: ** b. Part of a multi-token phrase.
4165: **
4166: ** After each token doclist is loaded, merge it with the others from the
4167: ** same phrase and count the number of documents that the merged doclist
4168: ** contains. Set variable "nMinEst" to the smallest number of documents in
4169: ** any phrase doclist for which 1 or more token doclists have been loaded.
4170: ** Let nOther be the number of other phrases for which it is certain that
4171: ** one or more tokens will not be deferred.
4172: **
4173: ** Then, for each token, defer it if loading the doclist would result in
4174: ** loading N or more overflow pages into memory, where N is computed as:
4175: **
4176: ** (nMinEst + 4^nOther - 1) / (4^nOther)
4177: */
4178: for(ii=0; ii<nToken && rc==SQLITE_OK; ii++){
4179: int iTC; /* Used to iterate through aTC[] array. */
4180: Fts3TokenAndCost *pTC = 0; /* Set to cheapest remaining token. */
4181:
4182: /* Set pTC to point to the cheapest remaining token. */
4183: for(iTC=0; iTC<nTC; iTC++){
4184: if( aTC[iTC].pToken && aTC[iTC].pRoot==pRoot
4185: && (!pTC || aTC[iTC].nOvfl<pTC->nOvfl)
4186: ){
4187: pTC = &aTC[iTC];
4188: }
4189: }
4190: assert( pTC );
4191:
4192: if( ii && pTC->nOvfl>=((nMinEst+(nLoad4/4)-1)/(nLoad4/4))*nDocSize ){
4193: /* The number of overflow pages to load for this (and therefore all
4194: ** subsequent) tokens is greater than the estimated number of pages
4195: ** that will be loaded if all subsequent tokens are deferred.
4196: */
4197: Fts3PhraseToken *pToken = pTC->pToken;
4198: rc = sqlite3Fts3DeferToken(pCsr, pToken, pTC->iCol);
4199: fts3SegReaderCursorFree(pToken->pSegcsr);
4200: pToken->pSegcsr = 0;
4201: }else{
4202: /* Set nLoad4 to the value of (4^nOther) for the next iteration of the
4203: ** for-loop. Except, limit the value to 2^24 to prevent it from
4204: ** overflowing the 32-bit integer it is stored in. */
4205: if( ii<12 ) nLoad4 = nLoad4*4;
4206:
4207: if( ii==0 || pTC->pPhrase->nToken>1 ){
4208: /* Either this is the cheapest token in the entire query, or it is
4209: ** part of a multi-token phrase. Either way, the entire doclist will
4210: ** (eventually) be loaded into memory. It may as well be now. */
4211: Fts3PhraseToken *pToken = pTC->pToken;
4212: int nList = 0;
4213: char *pList = 0;
4214: rc = fts3TermSelect(pTab, pToken, pTC->iCol, &nList, &pList);
4215: assert( rc==SQLITE_OK || pList==0 );
4216: if( rc==SQLITE_OK ){
4217: int nCount;
4218: fts3EvalPhraseMergeToken(pTab, pTC->pPhrase, pTC->iToken,pList,nList);
4219: nCount = fts3DoclistCountDocids(
4220: pTC->pPhrase->doclist.aAll, pTC->pPhrase->doclist.nAll
4221: );
4222: if( ii==0 || nCount<nMinEst ) nMinEst = nCount;
4223: }
4224: }
4225: }
4226: pTC->pToken = 0;
4227: }
4228:
4229: return rc;
4230: }
4231:
4232: /*
4233: ** This function is called from within the xFilter method. It initializes
4234: ** the full-text query currently stored in pCsr->pExpr. To iterate through
4235: ** the results of a query, the caller does:
4236: **
4237: ** fts3EvalStart(pCsr);
4238: ** while( 1 ){
4239: ** fts3EvalNext(pCsr);
4240: ** if( pCsr->bEof ) break;
4241: ** ... return row pCsr->iPrevId to the caller ...
4242: ** }
4243: */
4244: static int fts3EvalStart(Fts3Cursor *pCsr){
4245: Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
4246: int rc = SQLITE_OK;
4247: int nToken = 0;
4248: int nOr = 0;
4249:
4250: /* Allocate a MultiSegReader for each token in the expression. */
4251: fts3EvalAllocateReaders(pCsr, pCsr->pExpr, &nToken, &nOr, &rc);
4252:
4253: /* Determine which, if any, tokens in the expression should be deferred. */
4254: if( rc==SQLITE_OK && nToken>1 && pTab->bHasStat ){
4255: Fts3TokenAndCost *aTC;
4256: Fts3Expr **apOr;
4257: aTC = (Fts3TokenAndCost *)sqlite3_malloc(
4258: sizeof(Fts3TokenAndCost) * nToken
4259: + sizeof(Fts3Expr *) * nOr * 2
4260: );
4261: apOr = (Fts3Expr **)&aTC[nToken];
4262:
4263: if( !aTC ){
4264: rc = SQLITE_NOMEM;
4265: }else{
4266: int ii;
4267: Fts3TokenAndCost *pTC = aTC;
4268: Fts3Expr **ppOr = apOr;
4269:
4270: fts3EvalTokenCosts(pCsr, 0, pCsr->pExpr, &pTC, &ppOr, &rc);
4271: nToken = pTC-aTC;
4272: nOr = ppOr-apOr;
4273:
4274: if( rc==SQLITE_OK ){
4275: rc = fts3EvalSelectDeferred(pCsr, 0, aTC, nToken);
4276: for(ii=0; rc==SQLITE_OK && ii<nOr; ii++){
4277: rc = fts3EvalSelectDeferred(pCsr, apOr[ii], aTC, nToken);
4278: }
4279: }
4280:
4281: sqlite3_free(aTC);
4282: }
4283: }
4284:
4285: fts3EvalStartReaders(pCsr, pCsr->pExpr, 1, &rc);
4286: return rc;
4287: }
4288:
4289: /*
4290: ** Invalidate the current position list for phrase pPhrase.
4291: */
4292: static void fts3EvalInvalidatePoslist(Fts3Phrase *pPhrase){
4293: if( pPhrase->doclist.bFreeList ){
4294: sqlite3_free(pPhrase->doclist.pList);
4295: }
4296: pPhrase->doclist.pList = 0;
4297: pPhrase->doclist.nList = 0;
4298: pPhrase->doclist.bFreeList = 0;
4299: }
4300:
4301: /*
4302: ** This function is called to edit the position list associated with
4303: ** the phrase object passed as the fifth argument according to a NEAR
4304: ** condition. For example:
4305: **
4306: ** abc NEAR/5 "def ghi"
4307: **
4308: ** Parameter nNear is passed the NEAR distance of the expression (5 in
4309: ** the example above). When this function is called, *paPoslist points to
4310: ** the position list, and *pnToken is the number of phrase tokens in, the
4311: ** phrase on the other side of the NEAR operator to pPhrase. For example,
4312: ** if pPhrase refers to the "def ghi" phrase, then *paPoslist points to
4313: ** the position list associated with phrase "abc".
4314: **
4315: ** All positions in the pPhrase position list that are not sufficiently
4316: ** close to a position in the *paPoslist position list are removed. If this
4317: ** leaves 0 positions, zero is returned. Otherwise, non-zero.
4318: **
4319: ** Before returning, *paPoslist is set to point to the position lsit
4320: ** associated with pPhrase. And *pnToken is set to the number of tokens in
4321: ** pPhrase.
4322: */
4323: static int fts3EvalNearTrim(
4324: int nNear, /* NEAR distance. As in "NEAR/nNear". */
4325: char *aTmp, /* Temporary space to use */
4326: char **paPoslist, /* IN/OUT: Position list */
4327: int *pnToken, /* IN/OUT: Tokens in phrase of *paPoslist */
4328: Fts3Phrase *pPhrase /* The phrase object to trim the doclist of */
4329: ){
4330: int nParam1 = nNear + pPhrase->nToken;
4331: int nParam2 = nNear + *pnToken;
4332: int nNew;
4333: char *p2;
4334: char *pOut;
4335: int res;
4336:
4337: assert( pPhrase->doclist.pList );
4338:
4339: p2 = pOut = pPhrase->doclist.pList;
4340: res = fts3PoslistNearMerge(
4341: &pOut, aTmp, nParam1, nParam2, paPoslist, &p2
4342: );
4343: if( res ){
4344: nNew = (pOut - pPhrase->doclist.pList) - 1;
4345: assert( pPhrase->doclist.pList[nNew]=='\0' );
4346: assert( nNew<=pPhrase->doclist.nList && nNew>0 );
4347: memset(&pPhrase->doclist.pList[nNew], 0, pPhrase->doclist.nList - nNew);
4348: pPhrase->doclist.nList = nNew;
4349: *paPoslist = pPhrase->doclist.pList;
4350: *pnToken = pPhrase->nToken;
4351: }
4352:
4353: return res;
4354: }
4355:
4356: /*
4357: ** This function is a no-op if *pRc is other than SQLITE_OK when it is called.
4358: ** Otherwise, it advances the expression passed as the second argument to
4359: ** point to the next matching row in the database. Expressions iterate through
4360: ** matching rows in docid order. Ascending order if Fts3Cursor.bDesc is zero,
4361: ** or descending if it is non-zero.
4362: **
4363: ** If an error occurs, *pRc is set to an SQLite error code. Otherwise, if
4364: ** successful, the following variables in pExpr are set:
4365: **
4366: ** Fts3Expr.bEof (non-zero if EOF - there is no next row)
4367: ** Fts3Expr.iDocid (valid if bEof==0. The docid of the next row)
4368: **
4369: ** If the expression is of type FTSQUERY_PHRASE, and the expression is not
4370: ** at EOF, then the following variables are populated with the position list
4371: ** for the phrase for the visited row:
4372: **
4373: ** FTs3Expr.pPhrase->doclist.nList (length of pList in bytes)
4374: ** FTs3Expr.pPhrase->doclist.pList (pointer to position list)
4375: **
4376: ** It says above that this function advances the expression to the next
4377: ** matching row. This is usually true, but there are the following exceptions:
4378: **
4379: ** 1. Deferred tokens are not taken into account. If a phrase consists
4380: ** entirely of deferred tokens, it is assumed to match every row in
4381: ** the db. In this case the position-list is not populated at all.
4382: **
4383: ** Or, if a phrase contains one or more deferred tokens and one or
4384: ** more non-deferred tokens, then the expression is advanced to the
4385: ** next possible match, considering only non-deferred tokens. In other
4386: ** words, if the phrase is "A B C", and "B" is deferred, the expression
4387: ** is advanced to the next row that contains an instance of "A * C",
4388: ** where "*" may match any single token. The position list in this case
4389: ** is populated as for "A * C" before returning.
4390: **
4391: ** 2. NEAR is treated as AND. If the expression is "x NEAR y", it is
4392: ** advanced to point to the next row that matches "x AND y".
4393: **
4394: ** See fts3EvalTestDeferredAndNear() for details on testing if a row is
4395: ** really a match, taking into account deferred tokens and NEAR operators.
4396: */
4397: static void fts3EvalNextRow(
4398: Fts3Cursor *pCsr, /* FTS Cursor handle */
4399: Fts3Expr *pExpr, /* Expr. to advance to next matching row */
4400: int *pRc /* IN/OUT: Error code */
4401: ){
4402: if( *pRc==SQLITE_OK ){
4403: int bDescDoclist = pCsr->bDesc; /* Used by DOCID_CMP() macro */
4404: assert( pExpr->bEof==0 );
4405: pExpr->bStart = 1;
4406:
4407: switch( pExpr->eType ){
4408: case FTSQUERY_NEAR:
4409: case FTSQUERY_AND: {
4410: Fts3Expr *pLeft = pExpr->pLeft;
4411: Fts3Expr *pRight = pExpr->pRight;
4412: assert( !pLeft->bDeferred || !pRight->bDeferred );
4413:
4414: if( pLeft->bDeferred ){
4415: /* LHS is entirely deferred. So we assume it matches every row.
4416: ** Advance the RHS iterator to find the next row visited. */
4417: fts3EvalNextRow(pCsr, pRight, pRc);
4418: pExpr->iDocid = pRight->iDocid;
4419: pExpr->bEof = pRight->bEof;
4420: }else if( pRight->bDeferred ){
4421: /* RHS is entirely deferred. So we assume it matches every row.
4422: ** Advance the LHS iterator to find the next row visited. */
4423: fts3EvalNextRow(pCsr, pLeft, pRc);
4424: pExpr->iDocid = pLeft->iDocid;
4425: pExpr->bEof = pLeft->bEof;
4426: }else{
4427: /* Neither the RHS or LHS are deferred. */
4428: fts3EvalNextRow(pCsr, pLeft, pRc);
4429: fts3EvalNextRow(pCsr, pRight, pRc);
4430: while( !pLeft->bEof && !pRight->bEof && *pRc==SQLITE_OK ){
4431: sqlite3_int64 iDiff = DOCID_CMP(pLeft->iDocid, pRight->iDocid);
4432: if( iDiff==0 ) break;
4433: if( iDiff<0 ){
4434: fts3EvalNextRow(pCsr, pLeft, pRc);
4435: }else{
4436: fts3EvalNextRow(pCsr, pRight, pRc);
4437: }
4438: }
4439: pExpr->iDocid = pLeft->iDocid;
4440: pExpr->bEof = (pLeft->bEof || pRight->bEof);
4441: }
4442: break;
4443: }
4444:
4445: case FTSQUERY_OR: {
4446: Fts3Expr *pLeft = pExpr->pLeft;
4447: Fts3Expr *pRight = pExpr->pRight;
4448: sqlite3_int64 iCmp = DOCID_CMP(pLeft->iDocid, pRight->iDocid);
4449:
4450: assert( pLeft->bStart || pLeft->iDocid==pRight->iDocid );
4451: assert( pRight->bStart || pLeft->iDocid==pRight->iDocid );
4452:
4453: if( pRight->bEof || (pLeft->bEof==0 && iCmp<0) ){
4454: fts3EvalNextRow(pCsr, pLeft, pRc);
4455: }else if( pLeft->bEof || (pRight->bEof==0 && iCmp>0) ){
4456: fts3EvalNextRow(pCsr, pRight, pRc);
4457: }else{
4458: fts3EvalNextRow(pCsr, pLeft, pRc);
4459: fts3EvalNextRow(pCsr, pRight, pRc);
4460: }
4461:
4462: pExpr->bEof = (pLeft->bEof && pRight->bEof);
4463: iCmp = DOCID_CMP(pLeft->iDocid, pRight->iDocid);
4464: if( pRight->bEof || (pLeft->bEof==0 && iCmp<0) ){
4465: pExpr->iDocid = pLeft->iDocid;
4466: }else{
4467: pExpr->iDocid = pRight->iDocid;
4468: }
4469:
4470: break;
4471: }
4472:
4473: case FTSQUERY_NOT: {
4474: Fts3Expr *pLeft = pExpr->pLeft;
4475: Fts3Expr *pRight = pExpr->pRight;
4476:
4477: if( pRight->bStart==0 ){
4478: fts3EvalNextRow(pCsr, pRight, pRc);
4479: assert( *pRc!=SQLITE_OK || pRight->bStart );
4480: }
4481:
4482: fts3EvalNextRow(pCsr, pLeft, pRc);
4483: if( pLeft->bEof==0 ){
4484: while( !*pRc
4485: && !pRight->bEof
4486: && DOCID_CMP(pLeft->iDocid, pRight->iDocid)>0
4487: ){
4488: fts3EvalNextRow(pCsr, pRight, pRc);
4489: }
4490: }
4491: pExpr->iDocid = pLeft->iDocid;
4492: pExpr->bEof = pLeft->bEof;
4493: break;
4494: }
4495:
4496: default: {
4497: Fts3Phrase *pPhrase = pExpr->pPhrase;
4498: fts3EvalInvalidatePoslist(pPhrase);
4499: *pRc = fts3EvalPhraseNext(pCsr, pPhrase, &pExpr->bEof);
4500: pExpr->iDocid = pPhrase->doclist.iDocid;
4501: break;
4502: }
4503: }
4504: }
4505: }
4506:
4507: /*
4508: ** If *pRc is not SQLITE_OK, or if pExpr is not the root node of a NEAR
4509: ** cluster, then this function returns 1 immediately.
4510: **
4511: ** Otherwise, it checks if the current row really does match the NEAR
4512: ** expression, using the data currently stored in the position lists
4513: ** (Fts3Expr->pPhrase.doclist.pList/nList) for each phrase in the expression.
4514: **
4515: ** If the current row is a match, the position list associated with each
4516: ** phrase in the NEAR expression is edited in place to contain only those
4517: ** phrase instances sufficiently close to their peers to satisfy all NEAR
4518: ** constraints. In this case it returns 1. If the NEAR expression does not
4519: ** match the current row, 0 is returned. The position lists may or may not
4520: ** be edited if 0 is returned.
4521: */
4522: static int fts3EvalNearTest(Fts3Expr *pExpr, int *pRc){
4523: int res = 1;
4524:
4525: /* The following block runs if pExpr is the root of a NEAR query.
4526: ** For example, the query:
4527: **
4528: ** "w" NEAR "x" NEAR "y" NEAR "z"
4529: **
4530: ** which is represented in tree form as:
4531: **
4532: ** |
4533: ** +--NEAR--+ <-- root of NEAR query
4534: ** | |
4535: ** +--NEAR--+ "z"
4536: ** | |
4537: ** +--NEAR--+ "y"
4538: ** | |
4539: ** "w" "x"
4540: **
4541: ** The right-hand child of a NEAR node is always a phrase. The
4542: ** left-hand child may be either a phrase or a NEAR node. There are
4543: ** no exceptions to this - it's the way the parser in fts3_expr.c works.
4544: */
4545: if( *pRc==SQLITE_OK
4546: && pExpr->eType==FTSQUERY_NEAR
4547: && pExpr->bEof==0
4548: && (pExpr->pParent==0 || pExpr->pParent->eType!=FTSQUERY_NEAR)
4549: ){
4550: Fts3Expr *p;
4551: int nTmp = 0; /* Bytes of temp space */
4552: char *aTmp; /* Temp space for PoslistNearMerge() */
4553:
4554: /* Allocate temporary working space. */
4555: for(p=pExpr; p->pLeft; p=p->pLeft){
4556: nTmp += p->pRight->pPhrase->doclist.nList;
4557: }
4558: nTmp += p->pPhrase->doclist.nList;
4559: aTmp = sqlite3_malloc(nTmp*2);
4560: if( !aTmp ){
4561: *pRc = SQLITE_NOMEM;
4562: res = 0;
4563: }else{
4564: char *aPoslist = p->pPhrase->doclist.pList;
4565: int nToken = p->pPhrase->nToken;
4566:
4567: for(p=p->pParent;res && p && p->eType==FTSQUERY_NEAR; p=p->pParent){
4568: Fts3Phrase *pPhrase = p->pRight->pPhrase;
4569: int nNear = p->nNear;
4570: res = fts3EvalNearTrim(nNear, aTmp, &aPoslist, &nToken, pPhrase);
4571: }
4572:
4573: aPoslist = pExpr->pRight->pPhrase->doclist.pList;
4574: nToken = pExpr->pRight->pPhrase->nToken;
4575: for(p=pExpr->pLeft; p && res; p=p->pLeft){
4576: int nNear;
4577: Fts3Phrase *pPhrase;
4578: assert( p->pParent && p->pParent->pLeft==p );
4579: nNear = p->pParent->nNear;
4580: pPhrase = (
4581: p->eType==FTSQUERY_NEAR ? p->pRight->pPhrase : p->pPhrase
4582: );
4583: res = fts3EvalNearTrim(nNear, aTmp, &aPoslist, &nToken, pPhrase);
4584: }
4585: }
4586:
4587: sqlite3_free(aTmp);
4588: }
4589:
4590: return res;
4591: }
4592:
4593: /*
4594: ** This function is a helper function for fts3EvalTestDeferredAndNear().
4595: ** Assuming no error occurs or has occurred, It returns non-zero if the
4596: ** expression passed as the second argument matches the row that pCsr
4597: ** currently points to, or zero if it does not.
4598: **
4599: ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.
4600: ** If an error occurs during execution of this function, *pRc is set to
4601: ** the appropriate SQLite error code. In this case the returned value is
4602: ** undefined.
4603: */
4604: static int fts3EvalTestExpr(
4605: Fts3Cursor *pCsr, /* FTS cursor handle */
4606: Fts3Expr *pExpr, /* Expr to test. May or may not be root. */
4607: int *pRc /* IN/OUT: Error code */
4608: ){
4609: int bHit = 1; /* Return value */
4610: if( *pRc==SQLITE_OK ){
4611: switch( pExpr->eType ){
4612: case FTSQUERY_NEAR:
4613: case FTSQUERY_AND:
4614: bHit = (
4615: fts3EvalTestExpr(pCsr, pExpr->pLeft, pRc)
4616: && fts3EvalTestExpr(pCsr, pExpr->pRight, pRc)
4617: && fts3EvalNearTest(pExpr, pRc)
4618: );
4619:
4620: /* If the NEAR expression does not match any rows, zero the doclist for
4621: ** all phrases involved in the NEAR. This is because the snippet(),
4622: ** offsets() and matchinfo() functions are not supposed to recognize
4623: ** any instances of phrases that are part of unmatched NEAR queries.
4624: ** For example if this expression:
4625: **
4626: ** ... MATCH 'a OR (b NEAR c)'
4627: **
4628: ** is matched against a row containing:
4629: **
4630: ** 'a b d e'
4631: **
4632: ** then any snippet() should ony highlight the "a" term, not the "b"
4633: ** (as "b" is part of a non-matching NEAR clause).
4634: */
4635: if( bHit==0
4636: && pExpr->eType==FTSQUERY_NEAR
4637: && (pExpr->pParent==0 || pExpr->pParent->eType!=FTSQUERY_NEAR)
4638: ){
4639: Fts3Expr *p;
4640: for(p=pExpr; p->pPhrase==0; p=p->pLeft){
4641: if( p->pRight->iDocid==pCsr->iPrevId ){
4642: fts3EvalInvalidatePoslist(p->pRight->pPhrase);
4643: }
4644: }
4645: if( p->iDocid==pCsr->iPrevId ){
4646: fts3EvalInvalidatePoslist(p->pPhrase);
4647: }
4648: }
4649:
4650: break;
4651:
4652: case FTSQUERY_OR: {
4653: int bHit1 = fts3EvalTestExpr(pCsr, pExpr->pLeft, pRc);
4654: int bHit2 = fts3EvalTestExpr(pCsr, pExpr->pRight, pRc);
4655: bHit = bHit1 || bHit2;
4656: break;
4657: }
4658:
4659: case FTSQUERY_NOT:
4660: bHit = (
4661: fts3EvalTestExpr(pCsr, pExpr->pLeft, pRc)
4662: && !fts3EvalTestExpr(pCsr, pExpr->pRight, pRc)
4663: );
4664: break;
4665:
4666: default: {
4667: if( pCsr->pDeferred
4668: && (pExpr->iDocid==pCsr->iPrevId || pExpr->bDeferred)
4669: ){
4670: Fts3Phrase *pPhrase = pExpr->pPhrase;
4671: assert( pExpr->bDeferred || pPhrase->doclist.bFreeList==0 );
4672: if( pExpr->bDeferred ){
4673: fts3EvalInvalidatePoslist(pPhrase);
4674: }
4675: *pRc = fts3EvalDeferredPhrase(pCsr, pPhrase);
4676: bHit = (pPhrase->doclist.pList!=0);
4677: pExpr->iDocid = pCsr->iPrevId;
4678: }else{
4679: bHit = (pExpr->bEof==0 && pExpr->iDocid==pCsr->iPrevId);
4680: }
4681: break;
4682: }
4683: }
4684: }
4685: return bHit;
4686: }
4687:
4688: /*
4689: ** This function is called as the second part of each xNext operation when
4690: ** iterating through the results of a full-text query. At this point the
4691: ** cursor points to a row that matches the query expression, with the
4692: ** following caveats:
4693: **
4694: ** * Up until this point, "NEAR" operators in the expression have been
4695: ** treated as "AND".
4696: **
4697: ** * Deferred tokens have not yet been considered.
4698: **
4699: ** If *pRc is not SQLITE_OK when this function is called, it immediately
4700: ** returns 0. Otherwise, it tests whether or not after considering NEAR
4701: ** operators and deferred tokens the current row is still a match for the
4702: ** expression. It returns 1 if both of the following are true:
4703: **
4704: ** 1. *pRc is SQLITE_OK when this function returns, and
4705: **
4706: ** 2. After scanning the current FTS table row for the deferred tokens,
4707: ** it is determined that the row does *not* match the query.
4708: **
4709: ** Or, if no error occurs and it seems the current row does match the FTS
4710: ** query, return 0.
4711: */
4712: static int fts3EvalTestDeferredAndNear(Fts3Cursor *pCsr, int *pRc){
4713: int rc = *pRc;
4714: int bMiss = 0;
4715: if( rc==SQLITE_OK ){
4716:
4717: /* If there are one or more deferred tokens, load the current row into
4718: ** memory and scan it to determine the position list for each deferred
4719: ** token. Then, see if this row is really a match, considering deferred
4720: ** tokens and NEAR operators (neither of which were taken into account
4721: ** earlier, by fts3EvalNextRow()).
4722: */
4723: if( pCsr->pDeferred ){
4724: rc = fts3CursorSeek(0, pCsr);
4725: if( rc==SQLITE_OK ){
4726: rc = sqlite3Fts3CacheDeferredDoclists(pCsr);
4727: }
4728: }
4729: bMiss = (0==fts3EvalTestExpr(pCsr, pCsr->pExpr, &rc));
4730:
4731: /* Free the position-lists accumulated for each deferred token above. */
4732: sqlite3Fts3FreeDeferredDoclists(pCsr);
4733: *pRc = rc;
4734: }
4735: return (rc==SQLITE_OK && bMiss);
4736: }
4737:
4738: /*
4739: ** Advance to the next document that matches the FTS expression in
4740: ** Fts3Cursor.pExpr.
4741: */
4742: static int fts3EvalNext(Fts3Cursor *pCsr){
4743: int rc = SQLITE_OK; /* Return Code */
4744: Fts3Expr *pExpr = pCsr->pExpr;
4745: assert( pCsr->isEof==0 );
4746: if( pExpr==0 ){
4747: pCsr->isEof = 1;
4748: }else{
4749: do {
4750: if( pCsr->isRequireSeek==0 ){
4751: sqlite3_reset(pCsr->pStmt);
4752: }
4753: assert( sqlite3_data_count(pCsr->pStmt)==0 );
4754: fts3EvalNextRow(pCsr, pExpr, &rc);
4755: pCsr->isEof = pExpr->bEof;
4756: pCsr->isRequireSeek = 1;
4757: pCsr->isMatchinfoNeeded = 1;
4758: pCsr->iPrevId = pExpr->iDocid;
4759: }while( pCsr->isEof==0 && fts3EvalTestDeferredAndNear(pCsr, &rc) );
4760: }
4761: return rc;
4762: }
4763:
4764: /*
4765: ** Restart interation for expression pExpr so that the next call to
4766: ** fts3EvalNext() visits the first row. Do not allow incremental
4767: ** loading or merging of phrase doclists for this iteration.
4768: **
4769: ** If *pRc is other than SQLITE_OK when this function is called, it is
4770: ** a no-op. If an error occurs within this function, *pRc is set to an
4771: ** SQLite error code before returning.
4772: */
4773: static void fts3EvalRestart(
4774: Fts3Cursor *pCsr,
4775: Fts3Expr *pExpr,
4776: int *pRc
4777: ){
4778: if( pExpr && *pRc==SQLITE_OK ){
4779: Fts3Phrase *pPhrase = pExpr->pPhrase;
4780:
4781: if( pPhrase ){
4782: fts3EvalInvalidatePoslist(pPhrase);
4783: if( pPhrase->bIncr ){
4784: assert( pPhrase->nToken==1 );
4785: assert( pPhrase->aToken[0].pSegcsr );
4786: sqlite3Fts3MsrIncrRestart(pPhrase->aToken[0].pSegcsr);
4787: *pRc = fts3EvalPhraseStart(pCsr, 0, pPhrase);
4788: }
4789:
4790: pPhrase->doclist.pNextDocid = 0;
4791: pPhrase->doclist.iDocid = 0;
4792: }
4793:
4794: pExpr->iDocid = 0;
4795: pExpr->bEof = 0;
4796: pExpr->bStart = 0;
4797:
4798: fts3EvalRestart(pCsr, pExpr->pLeft, pRc);
4799: fts3EvalRestart(pCsr, pExpr->pRight, pRc);
4800: }
4801: }
4802:
4803: /*
4804: ** After allocating the Fts3Expr.aMI[] array for each phrase in the
4805: ** expression rooted at pExpr, the cursor iterates through all rows matched
4806: ** by pExpr, calling this function for each row. This function increments
4807: ** the values in Fts3Expr.aMI[] according to the position-list currently
4808: ** found in Fts3Expr.pPhrase->doclist.pList for each of the phrase
4809: ** expression nodes.
4810: */
4811: static void fts3EvalUpdateCounts(Fts3Expr *pExpr){
4812: if( pExpr ){
4813: Fts3Phrase *pPhrase = pExpr->pPhrase;
4814: if( pPhrase && pPhrase->doclist.pList ){
4815: int iCol = 0;
4816: char *p = pPhrase->doclist.pList;
4817:
4818: assert( *p );
4819: while( 1 ){
4820: u8 c = 0;
4821: int iCnt = 0;
4822: while( 0xFE & (*p | c) ){
4823: if( (c&0x80)==0 ) iCnt++;
4824: c = *p++ & 0x80;
4825: }
4826:
4827: /* aMI[iCol*3 + 1] = Number of occurrences
4828: ** aMI[iCol*3 + 2] = Number of rows containing at least one instance
4829: */
4830: pExpr->aMI[iCol*3 + 1] += iCnt;
4831: pExpr->aMI[iCol*3 + 2] += (iCnt>0);
4832: if( *p==0x00 ) break;
4833: p++;
4834: p += sqlite3Fts3GetVarint32(p, &iCol);
4835: }
4836: }
4837:
4838: fts3EvalUpdateCounts(pExpr->pLeft);
4839: fts3EvalUpdateCounts(pExpr->pRight);
4840: }
4841: }
4842:
4843: /*
4844: ** Expression pExpr must be of type FTSQUERY_PHRASE.
4845: **
4846: ** If it is not already allocated and populated, this function allocates and
4847: ** populates the Fts3Expr.aMI[] array for expression pExpr. If pExpr is part
4848: ** of a NEAR expression, then it also allocates and populates the same array
4849: ** for all other phrases that are part of the NEAR expression.
4850: **
4851: ** SQLITE_OK is returned if the aMI[] array is successfully allocated and
4852: ** populated. Otherwise, if an error occurs, an SQLite error code is returned.
4853: */
4854: static int fts3EvalGatherStats(
4855: Fts3Cursor *pCsr, /* Cursor object */
4856: Fts3Expr *pExpr /* FTSQUERY_PHRASE expression */
4857: ){
4858: int rc = SQLITE_OK; /* Return code */
4859:
4860: assert( pExpr->eType==FTSQUERY_PHRASE );
4861: if( pExpr->aMI==0 ){
4862: Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
4863: Fts3Expr *pRoot; /* Root of NEAR expression */
4864: Fts3Expr *p; /* Iterator used for several purposes */
4865:
4866: sqlite3_int64 iPrevId = pCsr->iPrevId;
4867: sqlite3_int64 iDocid;
4868: u8 bEof;
4869:
4870: /* Find the root of the NEAR expression */
4871: pRoot = pExpr;
4872: while( pRoot->pParent && pRoot->pParent->eType==FTSQUERY_NEAR ){
4873: pRoot = pRoot->pParent;
4874: }
4875: iDocid = pRoot->iDocid;
4876: bEof = pRoot->bEof;
4877: assert( pRoot->bStart );
4878:
4879: /* Allocate space for the aMSI[] array of each FTSQUERY_PHRASE node */
4880: for(p=pRoot; p; p=p->pLeft){
4881: Fts3Expr *pE = (p->eType==FTSQUERY_PHRASE?p:p->pRight);
4882: assert( pE->aMI==0 );
4883: pE->aMI = (u32 *)sqlite3_malloc(pTab->nColumn * 3 * sizeof(u32));
4884: if( !pE->aMI ) return SQLITE_NOMEM;
4885: memset(pE->aMI, 0, pTab->nColumn * 3 * sizeof(u32));
4886: }
4887:
4888: fts3EvalRestart(pCsr, pRoot, &rc);
4889:
4890: while( pCsr->isEof==0 && rc==SQLITE_OK ){
4891:
4892: do {
4893: /* Ensure the %_content statement is reset. */
4894: if( pCsr->isRequireSeek==0 ) sqlite3_reset(pCsr->pStmt);
4895: assert( sqlite3_data_count(pCsr->pStmt)==0 );
4896:
4897: /* Advance to the next document */
4898: fts3EvalNextRow(pCsr, pRoot, &rc);
4899: pCsr->isEof = pRoot->bEof;
4900: pCsr->isRequireSeek = 1;
4901: pCsr->isMatchinfoNeeded = 1;
4902: pCsr->iPrevId = pRoot->iDocid;
4903: }while( pCsr->isEof==0
4904: && pRoot->eType==FTSQUERY_NEAR
4905: && fts3EvalTestDeferredAndNear(pCsr, &rc)
4906: );
4907:
4908: if( rc==SQLITE_OK && pCsr->isEof==0 ){
4909: fts3EvalUpdateCounts(pRoot);
4910: }
4911: }
4912:
4913: pCsr->isEof = 0;
4914: pCsr->iPrevId = iPrevId;
4915:
4916: if( bEof ){
4917: pRoot->bEof = bEof;
4918: }else{
4919: /* Caution: pRoot may iterate through docids in ascending or descending
4920: ** order. For this reason, even though it seems more defensive, the
4921: ** do loop can not be written:
4922: **
4923: ** do {...} while( pRoot->iDocid<iDocid && rc==SQLITE_OK );
4924: */
4925: fts3EvalRestart(pCsr, pRoot, &rc);
4926: do {
4927: fts3EvalNextRow(pCsr, pRoot, &rc);
4928: assert( pRoot->bEof==0 );
4929: }while( pRoot->iDocid!=iDocid && rc==SQLITE_OK );
4930: fts3EvalTestDeferredAndNear(pCsr, &rc);
4931: }
4932: }
4933: return rc;
4934: }
4935:
4936: /*
4937: ** This function is used by the matchinfo() module to query a phrase
4938: ** expression node for the following information:
4939: **
4940: ** 1. The total number of occurrences of the phrase in each column of
4941: ** the FTS table (considering all rows), and
4942: **
4943: ** 2. For each column, the number of rows in the table for which the
4944: ** column contains at least one instance of the phrase.
4945: **
4946: ** If no error occurs, SQLITE_OK is returned and the values for each column
4947: ** written into the array aiOut as follows:
4948: **
4949: ** aiOut[iCol*3 + 1] = Number of occurrences
4950: ** aiOut[iCol*3 + 2] = Number of rows containing at least one instance
4951: **
4952: ** Caveats:
4953: **
4954: ** * If a phrase consists entirely of deferred tokens, then all output
4955: ** values are set to the number of documents in the table. In other
4956: ** words we assume that very common tokens occur exactly once in each
4957: ** column of each row of the table.
4958: **
4959: ** * If a phrase contains some deferred tokens (and some non-deferred
4960: ** tokens), count the potential occurrence identified by considering
4961: ** the non-deferred tokens instead of actual phrase occurrences.
4962: **
4963: ** * If the phrase is part of a NEAR expression, then only phrase instances
4964: ** that meet the NEAR constraint are included in the counts.
4965: */
4966: int sqlite3Fts3EvalPhraseStats(
4967: Fts3Cursor *pCsr, /* FTS cursor handle */
4968: Fts3Expr *pExpr, /* Phrase expression */
4969: u32 *aiOut /* Array to write results into (see above) */
4970: ){
4971: Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
4972: int rc = SQLITE_OK;
4973: int iCol;
4974:
4975: if( pExpr->bDeferred && pExpr->pParent->eType!=FTSQUERY_NEAR ){
4976: assert( pCsr->nDoc>0 );
4977: for(iCol=0; iCol<pTab->nColumn; iCol++){
4978: aiOut[iCol*3 + 1] = (u32)pCsr->nDoc;
4979: aiOut[iCol*3 + 2] = (u32)pCsr->nDoc;
4980: }
4981: }else{
4982: rc = fts3EvalGatherStats(pCsr, pExpr);
4983: if( rc==SQLITE_OK ){
4984: assert( pExpr->aMI );
4985: for(iCol=0; iCol<pTab->nColumn; iCol++){
4986: aiOut[iCol*3 + 1] = pExpr->aMI[iCol*3 + 1];
4987: aiOut[iCol*3 + 2] = pExpr->aMI[iCol*3 + 2];
4988: }
4989: }
4990: }
4991:
4992: return rc;
4993: }
4994:
4995: /*
4996: ** The expression pExpr passed as the second argument to this function
4997: ** must be of type FTSQUERY_PHRASE.
4998: **
4999: ** The returned value is either NULL or a pointer to a buffer containing
5000: ** a position-list indicating the occurrences of the phrase in column iCol
5001: ** of the current row.
5002: **
5003: ** More specifically, the returned buffer contains 1 varint for each
5004: ** occurence of the phrase in the column, stored using the normal (delta+2)
5005: ** compression and is terminated by either an 0x01 or 0x00 byte. For example,
5006: ** if the requested column contains "a b X c d X X" and the position-list
5007: ** for 'X' is requested, the buffer returned may contain:
5008: **
5009: ** 0x04 0x05 0x03 0x01 or 0x04 0x05 0x03 0x00
5010: **
5011: ** This function works regardless of whether or not the phrase is deferred,
5012: ** incremental, or neither.
5013: */
5014: char *sqlite3Fts3EvalPhrasePoslist(
5015: Fts3Cursor *pCsr, /* FTS3 cursor object */
5016: Fts3Expr *pExpr, /* Phrase to return doclist for */
5017: int iCol /* Column to return position list for */
5018: ){
5019: Fts3Phrase *pPhrase = pExpr->pPhrase;
5020: Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
5021: char *pIter = pPhrase->doclist.pList;
5022: int iThis;
5023:
5024: assert( iCol>=0 && iCol<pTab->nColumn );
5025: if( !pIter
5026: || pExpr->bEof
5027: || pExpr->iDocid!=pCsr->iPrevId
5028: || (pPhrase->iColumn<pTab->nColumn && pPhrase->iColumn!=iCol)
5029: ){
5030: return 0;
5031: }
5032:
5033: assert( pPhrase->doclist.nList>0 );
5034: if( *pIter==0x01 ){
5035: pIter++;
5036: pIter += sqlite3Fts3GetVarint32(pIter, &iThis);
5037: }else{
5038: iThis = 0;
5039: }
5040: while( iThis<iCol ){
5041: fts3ColumnlistCopy(0, &pIter);
5042: if( *pIter==0x00 ) return 0;
5043: pIter++;
5044: pIter += sqlite3Fts3GetVarint32(pIter, &iThis);
5045: }
5046:
5047: return ((iCol==iThis)?pIter:0);
5048: }
5049:
5050: /*
5051: ** Free all components of the Fts3Phrase structure that were allocated by
5052: ** the eval module. Specifically, this means to free:
5053: **
5054: ** * the contents of pPhrase->doclist, and
5055: ** * any Fts3MultiSegReader objects held by phrase tokens.
5056: */
5057: void sqlite3Fts3EvalPhraseCleanup(Fts3Phrase *pPhrase){
5058: if( pPhrase ){
5059: int i;
5060: sqlite3_free(pPhrase->doclist.aAll);
5061: fts3EvalInvalidatePoslist(pPhrase);
5062: memset(&pPhrase->doclist, 0, sizeof(Fts3Doclist));
5063: for(i=0; i<pPhrase->nToken; i++){
5064: fts3SegReaderCursorFree(pPhrase->aToken[i].pSegcsr);
5065: pPhrase->aToken[i].pSegcsr = 0;
5066: }
5067: }
5068: }
5069:
5070: /*
5071: ** Return SQLITE_CORRUPT_VTAB.
5072: */
5073: #ifdef SQLITE_DEBUG
5074: int sqlite3Fts3Corrupt(){
5075: return SQLITE_CORRUPT_VTAB;
5076: }
5077: #endif
5078:
5079: #if !SQLITE_CORE
5080: /*
5081: ** Initialize API pointer table, if required.
5082: */
5083: int sqlite3_extension_init(
5084: sqlite3 *db,
5085: char **pzErrMsg,
5086: const sqlite3_api_routines *pApi
5087: ){
5088: SQLITE_EXTENSION_INIT2(pApi)
5089: return sqlite3Fts3Init(db);
5090: }
5091: #endif
5092:
5093: #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to fts3.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sqlite3 / ext / fts3