Debian Codegraph @

ext/fts3/fts3.c

raw
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; (delta from previous doclist)
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 sentinels
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 delta to next docid (357). It has one position 70
105 ** (72-2) and then 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
291 #include "fts3Int.h"
292 #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)
293
294 #if defined(SQLITE_ENABLE_FTS3) && !defined(SQLITE_CORE)
295 # define SQLITE_CORE 1
296 #endif
297
298
299 #include "fts3.h"
300 #ifndef SQLITE_CORE
301 # include "sqlite3ext.h"
302 SQLITE_EXTENSION_INIT1
303 #endif
304
305
306 /*
307 ** Assume any b-tree layer with more levels than this is corrupt.
308 */
309 #define FTS3_MAX_BTREE_HEIGHT 48
310
311 typedef struct Fts3HashWrapper Fts3HashWrapper;
312 struct Fts3HashWrapper {
313 Fts3Hash hash; /* Hash table */
314 int nRef; /* Number of pointers to this object */
315 };
316
317 static int fts3EvalNext(Fts3Cursor *pCsr);
318 static int fts3EvalStart(Fts3Cursor *pCsr);
319 static int fts3TermSegReaderCursor(
320 Fts3Cursor *, const char *, int, int, Fts3MultiSegReader **);
321
322 /*
323 ** This variable is set to false when running tests for which the on disk
324 ** structures should not be corrupt. Otherwise, true. If it is false, extra
325 ** assert() conditions in the fts3 code are activated - conditions that are
326 ** only true if it is guaranteed that the fts3 database is not corrupt.
327 */
328 #ifdef SQLITE_DEBUG
329 int sqlite3_fts3_may_be_corrupt = 1;
330 #endif
331
332 /*
333 ** Write a 64-bit variable-length integer to memory starting at p[0].
334 ** The length of data written will be between 1 and FTS3_VARINT_MAX bytes.
335 ** The number of bytes written is returned.
336 */
337 int sqlite3Fts3PutVarint(char *p, sqlite_int64 v){
338 unsigned char *q = (unsigned char *) p;
339 sqlite_uint64 vu = v;
340 do{
341 *q++ = (unsigned char) ((vu & 0x7f) | 0x80);
342 vu >>= 7;
343 }while( vu!=0 );
344 q[-1] &= 0x7f; /* turn off high bit in final byte */
345 assert( q - (unsigned char *)p <= FTS3_VARINT_MAX );
346 return (int) (q - (unsigned char *)p);
347 }
348
349 #define GETVARINT_STEP(v, ptr, shift, mask1, mask2, var, ret) \
350 v = (v & mask1) | ( (*(const unsigned char*)(ptr++)) << shift ); \
351 if( (v & mask2)==0 ){ var = v; return ret; }
352 #define GETVARINT_INIT(v, ptr, shift, mask1, mask2, var, ret) \
353 v = (*ptr++); \
354 if( (v & mask2)==0 ){ var = v; return ret; }
355
356 int sqlite3Fts3GetVarintU(const char *pBuf, sqlite_uint64 *v){
357 const unsigned char *p = (const unsigned char*)pBuf;
358 const unsigned char *pStart = p;
359 u32 a;
360 u64 b;
361 int shift;
362
363 GETVARINT_INIT(a, p, 0, 0x00, 0x80, *v, 1);
364 GETVARINT_STEP(a, p, 7, 0x7F, 0x4000, *v, 2);
365 GETVARINT_STEP(a, p, 14, 0x3FFF, 0x200000, *v, 3);
366 GETVARINT_STEP(a, p, 21, 0x1FFFFF, 0x10000000, *v, 4);
367 b = (a & 0x0FFFFFFF );
368
369 for(shift=28; shift<=63; shift+=7){
370 u64 c = *p++;
371 b += (c&0x7F) << shift;
372 if( (c & 0x80)==0 ) break;
373 }
374 *v = b;
375 return (int)(p - pStart);
376 }
377
378 /*
379 ** Read a 64-bit variable-length integer from memory starting at p[0].
380 ** Return the number of bytes read, or 0 on error.
381 ** The value is stored in *v.
382 */
383 int sqlite3Fts3GetVarint(const char *pBuf, sqlite_int64 *v){
384 return sqlite3Fts3GetVarintU(pBuf, (sqlite3_uint64*)v);
385 }
386
387 /*
388 ** Read a 64-bit variable-length integer from memory starting at p[0] and
389 ** not extending past pEnd[-1].
390 ** Return the number of bytes read, or 0 on error.
391 ** The value is stored in *v.
392 */
393 int sqlite3Fts3GetVarintBounded(
394 const char *pBuf,
395 const char *pEnd,
396 sqlite_int64 *v
397 ){
398 const unsigned char *p = (const unsigned char*)pBuf;
399 const unsigned char *pStart = p;
400 const unsigned char *pX = (const unsigned char*)pEnd;
401 u64 b = 0;
402 int shift;
403 for(shift=0; shift<=63; shift+=7){
404 u64 c = p<pX ? *p : 0;
405 p++;
406 b += (c&0x7F) << shift;
407 if( (c & 0x80)==0 ) break;
408 }
409 *v = b;
410 return (int)(p - pStart);
411 }
412
413 /*
414 ** Similar to sqlite3Fts3GetVarint(), except that the output is truncated to
415 ** a non-negative 32-bit integer before it is returned.
416 */
417 int sqlite3Fts3GetVarint32(const char *p, int *pi){
418 const unsigned char *ptr = (const unsigned char*)p;
419 u32 a;
420
421 #ifndef fts3GetVarint32
422 GETVARINT_INIT(a, ptr, 0, 0x00, 0x80, *pi, 1);
423 #else
424 a = (*ptr++);
425 assert( a & 0x80 );
426 #endif
427
428 GETVARINT_STEP(a, ptr, 7, 0x7F, 0x4000, *pi, 2);
429 GETVARINT_STEP(a, ptr, 14, 0x3FFF, 0x200000, *pi, 3);
430 GETVARINT_STEP(a, ptr, 21, 0x1FFFFF, 0x10000000, *pi, 4);
431 a = (a & 0x0FFFFFFF );
432 *pi = (int)(a | ((u32)(*ptr & 0x07) << 28));
433 assert( 0==(a & 0x80000000) );
434 assert( *pi>=0 );
435 return 5;
436 }
437
438 /*
439 ** Return the number of bytes required to encode v as a varint
440 */
441 int sqlite3Fts3VarintLen(sqlite3_uint64 v){
442 int i = 0;
443 do{
444 i++;
445 v >>= 7;
446 }while( v!=0 );
447 return i;
448 }
449
450 /*
451 ** Convert an SQL-style quoted string into a normal string by removing
452 ** the quote characters. The conversion is done in-place. If the
453 ** input does not begin with a quote character, then this routine
454 ** is a no-op.
455 **
456 ** Examples:
457 **
458 ** "abc" becomes abc
459 ** 'xyz' becomes xyz
460 ** [pqr] becomes pqr
461 ** `mno` becomes mno
462 **
463 */
464 void sqlite3Fts3Dequote(char *z){
465 char quote; /* Quote character (if any ) */
466
467 quote = z[0];
468 if( quote=='[' || quote=='\'' || quote=='"' || quote=='`' ){
469 int iIn = 1; /* Index of next byte to read from input */
470 int iOut = 0; /* Index of next byte to write to output */
471
472 /* If the first byte was a '[', then the close-quote character is a ']' */
473 if( quote=='[' ) quote = ']';
474
475 while( z[iIn] ){
476 if( z[iIn]==quote ){
477 if( z[iIn+1]!=quote ) break;
478 z[iOut++] = quote;
479 iIn += 2;
480 }else{
481 z[iOut++] = z[iIn++];
482 }
483 }
484 z[iOut] = '\0';
485 }
486 }
487
488 /*
489 ** Read a single varint from the doclist at *pp and advance *pp to point
490 ** to the first byte past the end of the varint. Add the value of the varint
491 ** to *pVal.
492 */
493 static void fts3GetDeltaVarint(char **pp, sqlite3_int64 *pVal){
494 sqlite3_int64 iVal;
495 *pp += sqlite3Fts3GetVarint(*pp, &iVal);
496 *pVal += iVal;
497 }
498
499 /*
500 ** When this function is called, *pp points to the first byte following a
501 ** varint that is part of a doclist (or position-list, or any other list
502 ** of varints). This function moves *pp to point to the start of that varint,
503 ** and sets *pVal by the varint value.
504 **
505 ** Argument pStart points to the first byte of the doclist that the
506 ** varint is part of.
507 */
508 static void fts3GetReverseVarint(
509 char **pp,
510 char *pStart,
511 sqlite3_int64 *pVal
512 ){
513 sqlite3_int64 iVal;
514 char *p;
515
516 /* Pointer p now points at the first byte past the varint we are
517 ** interested in. So, unless the doclist is corrupt, the 0x80 bit is
518 ** clear on character p[-1]. */
519 for(p = (*pp)-2; p>=pStart && *p&0x80; p--);
520 p++;
521 *pp = p;
522
523 sqlite3Fts3GetVarint(p, &iVal);
524 *pVal = iVal;
525 }
526
527 /*
528 ** The xDisconnect() virtual table method.
529 */
530 static int fts3DisconnectMethod(sqlite3_vtab *pVtab){
531 Fts3Table *p = (Fts3Table *)pVtab;
532 int i;
533
534 assert( p->nPendingData==0 );
535 assert( p->pSegments==0 );
536
537 /* Free any prepared statements held */
538 sqlite3_finalize(p->pSeekStmt);
539 for(i=0; i<SizeofArray(p->aStmt); i++){
540 sqlite3_finalize(p->aStmt[i]);
541 }
542 sqlite3_free(p->zSegmentsTbl);
543 sqlite3_free(p->zReadExprlist);
544 sqlite3_free(p->zWriteExprlist);
545 sqlite3_free(p->zContentTbl);
546 sqlite3_free(p->zLanguageid);
547
548 /* Invoke the tokenizer destructor to free the tokenizer. */
549 p->pTokenizer->pModule->xDestroy(p->pTokenizer);
550
551 sqlite3_free(p);
552 return SQLITE_OK;
553 }
554
555 /*
556 ** Write an error message into *pzErr
557 */
558 void sqlite3Fts3ErrMsg(char **pzErr, const char *zFormat, ...){
559 va_list ap;
560 sqlite3_free(*pzErr);
561 va_start(ap, zFormat);
562 *pzErr = sqlite3_vmprintf(zFormat, ap);
563 va_end(ap);
564 }
565
566 /*
567 ** Construct one or more SQL statements from the format string given
568 ** and then evaluate those statements. The success code is written
569 ** into *pRc.
570 **
571 ** If *pRc is initially non-zero then this routine is a no-op.
572 */
573 static void fts3DbExec(
574 int *pRc, /* Success code */
575 sqlite3 *db, /* Database in which to run SQL */
576 const char *zFormat, /* Format string for SQL */
577 ... /* Arguments to the format string */
578 ){
579 va_list ap;
580 char *zSql;
581 if( *pRc ) return;
582 va_start(ap, zFormat);
583 zSql = sqlite3_vmprintf(zFormat, ap);
584 va_end(ap);
585 if( zSql==0 ){
586 *pRc = SQLITE_NOMEM;
587 }else{
588 *pRc = sqlite3_exec(db, zSql, 0, 0, 0);
589 sqlite3_free(zSql);
590 }
591 }
592
593 /*
594 ** The xDestroy() virtual table method.
595 */
596 static int fts3DestroyMethod(sqlite3_vtab *pVtab){
597 Fts3Table *p = (Fts3Table *)pVtab;
598 int rc = SQLITE_OK; /* Return code */
599 const char *zDb = p->zDb; /* Name of database (e.g. "main", "temp") */
600 sqlite3 *db = p->db; /* Database handle */
601
602 /* Drop the shadow tables */
603 fts3DbExec(&rc, db,
604 "DROP TABLE IF EXISTS %Q.'%q_segments';"
605 "DROP TABLE IF EXISTS %Q.'%q_segdir';"
606 "DROP TABLE IF EXISTS %Q.'%q_docsize';"
607 "DROP TABLE IF EXISTS %Q.'%q_stat';"
608 "%s DROP TABLE IF EXISTS %Q.'%q_content';",
609 zDb, p->zName,
610 zDb, p->zName,
611 zDb, p->zName,
612 zDb, p->zName,
613 (p->zContentTbl ? "--" : ""), zDb,p->zName
614 );
615
616 /* If everything has worked, invoke fts3DisconnectMethod() to free the
617 ** memory associated with the Fts3Table structure and return SQLITE_OK.
618 ** Otherwise, return an SQLite error code.
619 */
620 return (rc==SQLITE_OK ? fts3DisconnectMethod(pVtab) : rc);
621 }
622
623
624 /*
625 ** Invoke sqlite3_declare_vtab() to declare the schema for the FTS3 table
626 ** passed as the first argument. This is done as part of the xConnect()
627 ** and xCreate() methods.
628 **
629 ** If *pRc is non-zero when this function is called, it is a no-op.
630 ** Otherwise, if an error occurs, an SQLite error code is stored in *pRc
631 ** before returning.
632 */
633 static void fts3DeclareVtab(int *pRc, Fts3Table *p){
634 if( *pRc==SQLITE_OK ){
635 int i; /* Iterator variable */
636 int rc; /* Return code */
637 char *zSql; /* SQL statement passed to declare_vtab() */
638 char *zCols; /* List of user defined columns */
639 const char *zLanguageid;
640
641 zLanguageid = (p->zLanguageid ? p->zLanguageid : "__langid");
642 sqlite3_vtab_config(p->db, SQLITE_VTAB_CONSTRAINT_SUPPORT, 1);
643 sqlite3_vtab_config(p->db, SQLITE_VTAB_INNOCUOUS);
644
645 /* Create a list of user columns for the virtual table */
646 zCols = sqlite3_mprintf("%Q, ", p->azColumn[0]);
647 for(i=1; zCols && i<p->nColumn; i++){
648 zCols = sqlite3_mprintf("%z%Q, ", zCols, p->azColumn[i]);
649 }
650
651 /* Create the whole "CREATE TABLE" statement to pass to SQLite */
652 zSql = sqlite3_mprintf(
653 "CREATE TABLE x(%s %Q HIDDEN, docid HIDDEN, %Q HIDDEN)",
654 zCols, p->zName, zLanguageid
655 );
656 if( !zCols || !zSql ){
657 rc = SQLITE_NOMEM;
658 }else{
659 rc = sqlite3_declare_vtab(p->db, zSql);
660 }
661
662 sqlite3_free(zSql);
663 sqlite3_free(zCols);
664 *pRc = rc;
665 }
666 }
667
668 /*
669 ** Create the %_stat table if it does not already exist.
670 */
671 void sqlite3Fts3CreateStatTable(int *pRc, Fts3Table *p){
672 fts3DbExec(pRc, p->db,
673 "CREATE TABLE IF NOT EXISTS %Q.'%q_stat'"
674 "(id INTEGER PRIMARY KEY, value BLOB);",
675 p->zDb, p->zName
676 );
677 if( (*pRc)==SQLITE_OK ) p->bHasStat = 1;
678 }
679
680 /*
681 ** Create the backing store tables (%_content, %_segments and %_segdir)
682 ** required by the FTS3 table passed as the only argument. This is done
683 ** as part of the vtab xCreate() method.
684 **
685 ** If the p->bHasDocsize boolean is true (indicating that this is an
686 ** FTS4 table, not an FTS3 table) then also create the %_docsize and
687 ** %_stat tables required by FTS4.
688 */
689 static int fts3CreateTables(Fts3Table *p){
690 int rc = SQLITE_OK; /* Return code */
691 int i; /* Iterator variable */
692 sqlite3 *db = p->db; /* The database connection */
693
694 if( p->zContentTbl==0 ){
695 const char *zLanguageid = p->zLanguageid;
696 char *zContentCols; /* Columns of %_content table */
697
698 /* Create a list of user columns for the content table */
699 zContentCols = sqlite3_mprintf("docid INTEGER PRIMARY KEY");
700 for(i=0; zContentCols && i<p->nColumn; i++){
701 char *z = p->azColumn[i];
702 zContentCols = sqlite3_mprintf("%z, 'c%d%q'", zContentCols, i, z);
703 }
704 if( zLanguageid && zContentCols ){
705 zContentCols = sqlite3_mprintf("%z, langid", zContentCols, zLanguageid);
706 }
707 if( zContentCols==0 ) rc = SQLITE_NOMEM;
708
709 /* Create the content table */
710 fts3DbExec(&rc, db,
711 "CREATE TABLE %Q.'%q_content'(%s)",
712 p->zDb, p->zName, zContentCols
713 );
714 sqlite3_free(zContentCols);
715 }
716
717 /* Create other tables */
718 fts3DbExec(&rc, db,
719 "CREATE TABLE %Q.'%q_segments'(blockid INTEGER PRIMARY KEY, block BLOB);",
720 p->zDb, p->zName
721 );
722 fts3DbExec(&rc, db,
723 "CREATE TABLE %Q.'%q_segdir'("
724 "level INTEGER,"
725 "idx INTEGER,"
726 "start_block INTEGER,"
727 "leaves_end_block INTEGER,"
728 "end_block INTEGER,"
729 "root BLOB,"
730 "PRIMARY KEY(level, idx)"
731 ");",
732 p->zDb, p->zName
733 );
734 if( p->bHasDocsize ){
735 fts3DbExec(&rc, db,
736 "CREATE TABLE %Q.'%q_docsize'(docid INTEGER PRIMARY KEY, size BLOB);",
737 p->zDb, p->zName
738 );
739 }
740 assert( p->bHasStat==p->bFts4 );
741 if( p->bHasStat ){
742 sqlite3Fts3CreateStatTable(&rc, p);
743 }
744 return rc;
745 }
746
747 /*
748 ** Store the current database page-size in bytes in p->nPgsz.
749 **
750 ** If *pRc is non-zero when this function is called, it is a no-op.
751 ** Otherwise, if an error occurs, an SQLite error code is stored in *pRc
752 ** before returning.
753 */
754 static void fts3DatabasePageSize(int *pRc, Fts3Table *p){
755 if( *pRc==SQLITE_OK ){
756 int rc; /* Return code */
757 char *zSql; /* SQL text "PRAGMA %Q.page_size" */
758 sqlite3_stmt *pStmt; /* Compiled "PRAGMA %Q.page_size" statement */
759
760 zSql = sqlite3_mprintf("PRAGMA %Q.page_size", p->zDb);
761 if( !zSql ){
762 rc = SQLITE_NOMEM;
763 }else{
764 rc = sqlite3_prepare(p->db, zSql, -1, &pStmt, 0);
765 if( rc==SQLITE_OK ){
766 sqlite3_step(pStmt);
767 p->nPgsz = sqlite3_column_int(pStmt, 0);
768 rc = sqlite3_finalize(pStmt);
769 }else if( rc==SQLITE_AUTH ){
770 p->nPgsz = 1024;
771 rc = SQLITE_OK;
772 }
773 }
774 assert( p->nPgsz>0 || rc!=SQLITE_OK );
775 sqlite3_free(zSql);
776 *pRc = rc;
777 }
778 }
779
780 /*
781 ** "Special" FTS4 arguments are column specifications of the following form:
782 **
783 ** <key> = <value>
784 **
785 ** There may not be whitespace surrounding the "=" character. The <value>
786 ** term may be quoted, but the <key> may not.
787 */
788 static int fts3IsSpecialColumn(
789 const char *z,
790 int *pnKey,
791 char **pzValue
792 ){
793 char *zValue;
794 const char *zCsr = z;
795
796 while( *zCsr!='=' ){
797 if( *zCsr=='\0' ) return 0;
798 zCsr++;
799 }
800
801 *pnKey = (int)(zCsr-z);
802 zValue = sqlite3_mprintf("%s", &zCsr[1]);
803 if( zValue ){
804 sqlite3Fts3Dequote(zValue);
805 }
806 *pzValue = zValue;
807 return 1;
808 }
809
810 /*
811 ** Append the output of a printf() style formatting to an existing string.
812 */
813 static void fts3Appendf(
814 int *pRc, /* IN/OUT: Error code */
815 char **pz, /* IN/OUT: Pointer to string buffer */
816 const char *zFormat, /* Printf format string to append */
817 ... /* Arguments for printf format string */
818 ){
819 if( *pRc==SQLITE_OK ){
820 va_list ap;
821 char *z;
822 va_start(ap, zFormat);
823 z = sqlite3_vmprintf(zFormat, ap);
824 va_end(ap);
825 if( z && *pz ){
826 char *z2 = sqlite3_mprintf("%s%s", *pz, z);
827 sqlite3_free(z);
828 z = z2;
829 }
830 if( z==0 ) *pRc = SQLITE_NOMEM;
831 sqlite3_free(*pz);
832 *pz = z;
833 }
834 }
835
836 /*
837 ** Return a copy of input string zInput enclosed in double-quotes (") and
838 ** with all double quote characters escaped. For example:
839 **
840 ** fts3QuoteId("un \"zip\"") -> "un \"\"zip\"\""
841 **
842 ** The pointer returned points to memory obtained from sqlite3_malloc(). It
843 ** is the callers responsibility to call sqlite3_free() to release this
844 ** memory.
845 */
846 static char *fts3QuoteId(char const *zInput){
847 sqlite3_int64 nRet;
848 char *zRet;
849 nRet = 2 + (int)strlen(zInput)*2 + 1;
850 zRet = sqlite3_malloc64(nRet);
851 if( zRet ){
852 int i;
853 char *z = zRet;
854 *(z++) = '"';
855 for(i=0; zInput[i]; i++){
856 if( zInput[i]=='"' ) *(z++) = '"';
857 *(z++) = zInput[i];
858 }
859 *(z++) = '"';
860 *(z++) = '\0';
861 }
862 return zRet;
863 }
864
865 /*
866 ** Return a list of comma separated SQL expressions and a FROM clause that
867 ** could be used in a SELECT statement such as the following:
868 **
869 ** SELECT <list of expressions> FROM %_content AS x ...
870 **
871 ** to return the docid, followed by each column of text data in order
872 ** from left to write. If parameter zFunc is not NULL, then instead of
873 ** being returned directly each column of text data is passed to an SQL
874 ** function named zFunc first. For example, if zFunc is "unzip" and the
875 ** table has the three user-defined columns "a", "b", and "c", the following
876 ** string is returned:
877 **
878 ** "docid, unzip(x.'a'), unzip(x.'b'), unzip(x.'c') FROM %_content AS x"
879 **
880 ** The pointer returned points to a buffer allocated by sqlite3_malloc(). It
881 ** is the responsibility of the caller to eventually free it.
882 **
883 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op (and
884 ** a NULL pointer is returned). Otherwise, if an OOM error is encountered
885 ** by this function, NULL is returned and *pRc is set to SQLITE_NOMEM. If
886 ** no error occurs, *pRc is left unmodified.
887 */
888 static char *fts3ReadExprList(Fts3Table *p, const char *zFunc, int *pRc){
889 char *zRet = 0;
890 char *zFree = 0;
891 char *zFunction;
892 int i;
893
894 if( p->zContentTbl==0 ){
895 if( !zFunc ){
896 zFunction = "";
897 }else{
898 zFree = zFunction = fts3QuoteId(zFunc);
899 }
900 fts3Appendf(pRc, &zRet, "docid");
901 for(i=0; i<p->nColumn; i++){
902 fts3Appendf(pRc, &zRet, ",%s(x.'c%d%q')", zFunction, i, p->azColumn[i]);
903 }
904 if( p->zLanguageid ){
905 fts3Appendf(pRc, &zRet, ", x.%Q", "langid");
906 }
907 sqlite3_free(zFree);
908 }else{
909 fts3Appendf(pRc, &zRet, "rowid");
910 for(i=0; i<p->nColumn; i++){
911 fts3Appendf(pRc, &zRet, ", x.'%q'", p->azColumn[i]);
912 }
913 if( p->zLanguageid ){
914 fts3Appendf(pRc, &zRet, ", x.%Q", p->zLanguageid);
915 }
916 }
917 fts3Appendf(pRc, &zRet, " FROM '%q'.'%q%s' AS x",
918 p->zDb,
919 (p->zContentTbl ? p->zContentTbl : p->zName),
920 (p->zContentTbl ? "" : "_content")
921 );
922 return zRet;
923 }
924
925 /*
926 ** Return a list of N comma separated question marks, where N is the number
927 ** of columns in the %_content table (one for the docid plus one for each
928 ** user-defined text column).
929 **
930 ** If argument zFunc is not NULL, then all but the first question mark
931 ** is preceded by zFunc and an open bracket, and followed by a closed
932 ** bracket. For example, if zFunc is "zip" and the FTS3 table has three
933 ** user-defined text columns, the following string is returned:
934 **
935 ** "?, zip(?), zip(?), zip(?)"
936 **
937 ** The pointer returned points to a buffer allocated by sqlite3_malloc(). It
938 ** is the responsibility of the caller to eventually free it.
939 **
940 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op (and
941 ** a NULL pointer is returned). Otherwise, if an OOM error is encountered
942 ** by this function, NULL is returned and *pRc is set to SQLITE_NOMEM. If
943 ** no error occurs, *pRc is left unmodified.
944 */
945 static char *fts3WriteExprList(Fts3Table *p, const char *zFunc, int *pRc){
946 char *zRet = 0;
947 char *zFree = 0;
948 char *zFunction;
949 int i;
950
951 if( !zFunc ){
952 zFunction = "";
953 }else{
954 zFree = zFunction = fts3QuoteId(zFunc);
955 }
956 fts3Appendf(pRc, &zRet, "?");
957 for(i=0; i<p->nColumn; i++){
958 fts3Appendf(pRc, &zRet, ",%s(?)", zFunction);
959 }
960 if( p->zLanguageid ){
961 fts3Appendf(pRc, &zRet, ", ?");
962 }
963 sqlite3_free(zFree);
964 return zRet;
965 }
966
967 /*
968 ** Buffer z contains a positive integer value encoded as utf-8 text.
969 ** Decode this value and store it in *pnOut, returning the number of bytes
970 ** consumed. If an overflow error occurs return a negative value.
971 */
972 int sqlite3Fts3ReadInt(const char *z, int *pnOut){
973 u64 iVal = 0;
974 int i;
975 for(i=0; z[i]>='0' && z[i]<='9'; i++){
976 iVal = iVal*10 + (z[i] - '0');
977 if( iVal>0x7FFFFFFF ) return -1;
978 }
979 *pnOut = (int)iVal;
980 return i;
981 }
982
983 /*
984 ** This function interprets the string at (*pp) as a non-negative integer
985 ** value. It reads the integer and sets *pnOut to the value read, then
986 ** sets *pp to point to the byte immediately following the last byte of
987 ** the integer value.
988 **
989 ** Only decimal digits ('0'..'9') may be part of an integer value.
990 **
991 ** If *pp does not being with a decimal digit SQLITE_ERROR is returned and
992 ** the output value undefined. Otherwise SQLITE_OK is returned.
993 **
994 ** This function is used when parsing the "prefix=" FTS4 parameter.
995 */
996 static int fts3GobbleInt(const char **pp, int *pnOut){
997 const int MAX_NPREFIX = 10000000;
998 int nInt = 0; /* Output value */
999 int nByte;
1000 nByte = sqlite3Fts3ReadInt(*pp, &nInt);
1001 if( nInt>MAX_NPREFIX ){
1002 nInt = 0;
1003 }
1004 if( nByte==0 ){
1005 return SQLITE_ERROR;
1006 }
1007 *pnOut = nInt;
1008 *pp += nByte;
1009 return SQLITE_OK;
1010 }
1011
1012 /*
1013 ** This function is called to allocate an array of Fts3Index structures
1014 ** representing the indexes maintained by the current FTS table. FTS tables
1015 ** always maintain the main "terms" index, but may also maintain one or
1016 ** more "prefix" indexes, depending on the value of the "prefix=" parameter
1017 ** (if any) specified as part of the CREATE VIRTUAL TABLE statement.
1018 **
1019 ** Argument zParam is passed the value of the "prefix=" option if one was
1020 ** specified, or NULL otherwise.
1021 **
1022 ** If no error occurs, SQLITE_OK is returned and *apIndex set to point to
1023 ** the allocated array. *pnIndex is set to the number of elements in the
1024 ** array. If an error does occur, an SQLite error code is returned.
1025 **
1026 ** Regardless of whether or not an error is returned, it is the responsibility
1027 ** of the caller to call sqlite3_free() on the output array to free it.
1028 */
1029 static int fts3PrefixParameter(
1030 const char *zParam, /* ABC in prefix=ABC parameter to parse */
1031 int *pnIndex, /* OUT: size of *apIndex[] array */
1032 struct Fts3Index **apIndex /* OUT: Array of indexes for this table */
1033 ){
1034 struct Fts3Index *aIndex; /* Allocated array */
1035 int nIndex = 1; /* Number of entries in array */
1036
1037 if( zParam && zParam[0] ){
1038 const char *p;
1039 nIndex++;
1040 for(p=zParam; *p; p++){
1041 if( *p==',' ) nIndex++;
1042 }
1043 }
1044
1045 aIndex = sqlite3_malloc64(sizeof(struct Fts3Index) * nIndex);
1046 *apIndex = aIndex;
1047 if( !aIndex ){
1048 return SQLITE_NOMEM;
1049 }
1050
1051 memset(aIndex, 0, sizeof(struct Fts3Index) * nIndex);
1052 if( zParam ){
1053 const char *p = zParam;
1054 int i;
1055 for(i=1; i<nIndex; i++){
1056 int nPrefix = 0;
1057 if( fts3GobbleInt(&p, &nPrefix) ) return SQLITE_ERROR;
1058 assert( nPrefix>=0 );
1059 if( nPrefix==0 ){
1060 nIndex--;
1061 i--;
1062 }else{
1063 aIndex[i].nPrefix = nPrefix;
1064 }
1065 p++;
1066 }
1067 }
1068
1069 *pnIndex = nIndex;
1070 return SQLITE_OK;
1071 }
1072
1073 /*
1074 ** This function is called when initializing an FTS4 table that uses the
1075 ** content=xxx option. It determines the number of and names of the columns
1076 ** of the new FTS4 table.
1077 **
1078 ** The third argument passed to this function is the value passed to the
1079 ** config=xxx option (i.e. "xxx"). This function queries the database for
1080 ** a table of that name. If found, the output variables are populated
1081 ** as follows:
1082 **
1083 ** *pnCol: Set to the number of columns table xxx has,
1084 **
1085 ** *pnStr: Set to the total amount of space required to store a copy
1086 ** of each columns name, including the nul-terminator.
1087 **
1088 ** *pazCol: Set to point to an array of *pnCol strings. Each string is
1089 ** the name of the corresponding column in table xxx. The array
1090 ** and its contents are allocated using a single allocation. It
1091 ** is the responsibility of the caller to free this allocation
1092 ** by eventually passing the *pazCol value to sqlite3_free().
1093 **
1094 ** If the table cannot be found, an error code is returned and the output
1095 ** variables are undefined. Or, if an OOM is encountered, SQLITE_NOMEM is
1096 ** returned (and the output variables are undefined).
1097 */
1098 static int fts3ContentColumns(
1099 sqlite3 *db, /* Database handle */
1100 const char *zDb, /* Name of db (i.e. "main", "temp" etc.) */
1101 const char *zTbl, /* Name of content table */
1102 const char ***pazCol, /* OUT: Malloc'd array of column names */
1103 int *pnCol, /* OUT: Size of array *pazCol */
1104 int *pnStr, /* OUT: Bytes of string content */
1105 char **pzErr /* OUT: error message */
1106 ){
1107 int rc = SQLITE_OK; /* Return code */
1108 char *zSql; /* "SELECT *" statement on zTbl */
1109 sqlite3_stmt *pStmt = 0; /* Compiled version of zSql */
1110
1111 zSql = sqlite3_mprintf("SELECT * FROM %Q.%Q", zDb, zTbl);
1112 if( !zSql ){
1113 rc = SQLITE_NOMEM;
1114 }else{
1115 rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
1116 if( rc!=SQLITE_OK ){
1117 sqlite3Fts3ErrMsg(pzErr, "%s", sqlite3_errmsg(db));
1118 }
1119 }
1120 sqlite3_free(zSql);
1121
1122 if( rc==SQLITE_OK ){
1123 const char **azCol; /* Output array */
1124 sqlite3_int64 nStr = 0; /* Size of all column names (incl. 0x00) */
1125 int nCol; /* Number of table columns */
1126 int i; /* Used to iterate through columns */
1127
1128 /* Loop through the returned columns. Set nStr to the number of bytes of
1129 ** space required to store a copy of each column name, including the
1130 ** nul-terminator byte. */
1131 nCol = sqlite3_column_count(pStmt);
1132 for(i=0; i<nCol; i++){
1133 const char *zCol = sqlite3_column_name(pStmt, i);
1134 nStr += strlen(zCol) + 1;
1135 }
1136
1137 /* Allocate and populate the array to return. */
1138 azCol = (const char **)sqlite3_malloc64(sizeof(char *) * nCol + nStr);
1139 if( azCol==0 ){
1140 rc = SQLITE_NOMEM;
1141 }else{
1142 char *p = (char *)&azCol[nCol];
1143 for(i=0; i<nCol; i++){
1144 const char *zCol = sqlite3_column_name(pStmt, i);
1145 int n = (int)strlen(zCol)+1;
1146 memcpy(p, zCol, n);
1147 azCol[i] = p;
1148 p += n;
1149 }
1150 }
1151 sqlite3_finalize(pStmt);
1152
1153 /* Set the output variables. */
1154 *pnCol = nCol;
1155 *pnStr = nStr;
1156 *pazCol = azCol;
1157 }
1158
1159 return rc;
1160 }
1161
1162 /*
1163 ** This function is the implementation of both the xConnect and xCreate
1164 ** methods of the FTS3 virtual table.
1165 **
1166 ** The argv[] array contains the following:
1167 **
1168 ** argv[0] -> module name ("fts3" or "fts4")
1169 ** argv[1] -> database name
1170 ** argv[2] -> table name
1171 ** argv[...] -> "column name" and other module argument fields.
1172 */
1173 static int fts3InitVtab(
1174 int isCreate, /* True for xCreate, false for xConnect */
1175 sqlite3 *db, /* The SQLite database connection */
1176 void *pAux, /* Hash table containing tokenizers */
1177 int argc, /* Number of elements in argv array */
1178 const char * const *argv, /* xCreate/xConnect argument array */
1179 sqlite3_vtab **ppVTab, /* Write the resulting vtab structure here */
1180 char **pzErr /* Write any error message here */
1181 ){
1182 Fts3Hash *pHash = &((Fts3HashWrapper*)pAux)->hash;
1183 Fts3Table *p = 0; /* Pointer to allocated vtab */
1184 int rc = SQLITE_OK; /* Return code */
1185 int i; /* Iterator variable */
1186 sqlite3_int64 nByte; /* Size of allocation used for *p */
1187 int iCol; /* Column index */
1188 int nString = 0; /* Bytes required to hold all column names */
1189 int nCol = 0; /* Number of columns in the FTS table */
1190 char *zCsr; /* Space for holding column names */
1191 int nDb; /* Bytes required to hold database name */
1192 int nName; /* Bytes required to hold table name */
1193 int isFts4 = (argv[0][3]=='4'); /* True for FTS4, false for FTS3 */
1194 const char **aCol; /* Array of column names */
1195 sqlite3_tokenizer *pTokenizer = 0; /* Tokenizer for this table */
1196
1197 int nIndex = 0; /* Size of aIndex[] array */
1198 struct Fts3Index *aIndex = 0; /* Array of indexes for this table */
1199
1200 /* The results of parsing supported FTS4 key=value options: */
1201 int bNoDocsize = 0; /* True to omit %_docsize table */
1202 int bDescIdx = 0; /* True to store descending indexes */
1203 char *zPrefix = 0; /* Prefix parameter value (or NULL) */
1204 char *zCompress = 0; /* compress=? parameter (or NULL) */
1205 char *zUncompress = 0; /* uncompress=? parameter (or NULL) */
1206 char *zContent = 0; /* content=? parameter (or NULL) */
1207 char *zLanguageid = 0; /* languageid=? parameter (or NULL) */
1208 char **azNotindexed = 0; /* The set of notindexed= columns */
1209 int nNotindexed = 0; /* Size of azNotindexed[] array */
1210
1211 assert( strlen(argv[0])==4 );
1212 assert( (sqlite3_strnicmp(argv[0], "fts4", 4)==0 && isFts4)
1213 || (sqlite3_strnicmp(argv[0], "fts3", 4)==0 && !isFts4)
1214 );
1215
1216 nDb = (int)strlen(argv[1]) + 1;
1217 nName = (int)strlen(argv[2]) + 1;
1218
1219 nByte = sizeof(const char *) * (argc-2);
1220 aCol = (const char **)sqlite3_malloc64(nByte);
1221 if( aCol ){
1222 memset((void*)aCol, 0, nByte);
1223 azNotindexed = (char **)sqlite3_malloc64(nByte);
1224 }
1225 if( azNotindexed ){
1226 memset(azNotindexed, 0, nByte);
1227 }
1228 if( !aCol || !azNotindexed ){
1229 rc = SQLITE_NOMEM;
1230 goto fts3_init_out;
1231 }
1232
1233 /* Loop through all of the arguments passed by the user to the FTS3/4
1234 ** module (i.e. all the column names and special arguments). This loop
1235 ** does the following:
1236 **
1237 ** + Figures out the number of columns the FTSX table will have, and
1238 ** the number of bytes of space that must be allocated to store copies
1239 ** of the column names.
1240 **
1241 ** + If there is a tokenizer specification included in the arguments,
1242 ** initializes the tokenizer pTokenizer.
1243 */
1244 for(i=3; rc==SQLITE_OK && i<argc; i++){
1245 char const *z = argv[i];
1246 int nKey;
1247 char *zVal;
1248
1249 /* Check if this is a tokenizer specification */
1250 if( !pTokenizer
1251 && strlen(z)>8
1252 && 0==sqlite3_strnicmp(z, "tokenize", 8)
1253 && 0==sqlite3Fts3IsIdChar(z[8])
1254 ){
1255 rc = sqlite3Fts3InitTokenizer(pHash, &z[9], &pTokenizer, pzErr);
1256 }
1257
1258 /* Check if it is an FTS4 special argument. */
1259 else if( isFts4 && fts3IsSpecialColumn(z, &nKey, &zVal) ){
1260 struct Fts4Option {
1261 const char *zOpt;
1262 int nOpt;
1263 } aFts4Opt[] = {
1264 { "matchinfo", 9 }, /* 0 -> MATCHINFO */
1265 { "prefix", 6 }, /* 1 -> PREFIX */
1266 { "compress", 8 }, /* 2 -> COMPRESS */
1267 { "uncompress", 10 }, /* 3 -> UNCOMPRESS */
1268 { "order", 5 }, /* 4 -> ORDER */
1269 { "content", 7 }, /* 5 -> CONTENT */
1270 { "languageid", 10 }, /* 6 -> LANGUAGEID */
1271 { "notindexed", 10 } /* 7 -> NOTINDEXED */
1272 };
1273
1274 int iOpt;
1275 if( !zVal ){
1276 rc = SQLITE_NOMEM;
1277 }else{
1278 for(iOpt=0; iOpt<SizeofArray(aFts4Opt); iOpt++){
1279 struct Fts4Option *pOp = &aFts4Opt[iOpt];
1280 if( nKey==pOp->nOpt && !sqlite3_strnicmp(z, pOp->zOpt, pOp->nOpt) ){
1281 break;
1282 }
1283 }
1284 switch( iOpt ){
1285 case 0: /* MATCHINFO */
1286 if( strlen(zVal)!=4 || sqlite3_strnicmp(zVal, "fts3", 4) ){
1287 sqlite3Fts3ErrMsg(pzErr, "unrecognized matchinfo: %s", zVal);
1288 rc = SQLITE_ERROR;
1289 }
1290 bNoDocsize = 1;
1291 break;
1292
1293 case 1: /* PREFIX */
1294 sqlite3_free(zPrefix);
1295 zPrefix = zVal;
1296 zVal = 0;
1297 break;
1298
1299 case 2: /* COMPRESS */
1300 sqlite3_free(zCompress);
1301 zCompress = zVal;
1302 zVal = 0;
1303 break;
1304
1305 case 3: /* UNCOMPRESS */
1306 sqlite3_free(zUncompress);
1307 zUncompress = zVal;
1308 zVal = 0;
1309 break;
1310
1311 case 4: /* ORDER */
1312 if( (strlen(zVal)!=3 || sqlite3_strnicmp(zVal, "asc", 3))
1313 && (strlen(zVal)!=4 || sqlite3_strnicmp(zVal, "desc", 4))
1314 ){
1315 sqlite3Fts3ErrMsg(pzErr, "unrecognized order: %s", zVal);
1316 rc = SQLITE_ERROR;
1317 }
1318 bDescIdx = (zVal[0]=='d' || zVal[0]=='D');
1319 break;
1320
1321 case 5: /* CONTENT */
1322 sqlite3_free(zContent);
1323 zContent = zVal;
1324 zVal = 0;
1325 break;
1326
1327 case 6: /* LANGUAGEID */
1328 assert( iOpt==6 );
1329 sqlite3_free(zLanguageid);
1330 zLanguageid = zVal;
1331 zVal = 0;
1332 break;
1333
1334 case 7: /* NOTINDEXED */
1335 azNotindexed[nNotindexed++] = zVal;
1336 zVal = 0;
1337 break;
1338
1339 default:
1340 assert( iOpt==SizeofArray(aFts4Opt) );
1341 sqlite3Fts3ErrMsg(pzErr, "unrecognized parameter: %s", z);
1342 rc = SQLITE_ERROR;
1343 break;
1344 }
1345 sqlite3_free(zVal);
1346 }
1347 }
1348
1349 /* Otherwise, the argument is a column name. */
1350 else {
1351 nString += (int)(strlen(z) + 1);
1352 aCol[nCol++] = z;
1353 }
1354 }
1355
1356 /* If a content=xxx option was specified, the following:
1357 **
1358 ** 1. Ignore any compress= and uncompress= options.
1359 **
1360 ** 2. If no column names were specified as part of the CREATE VIRTUAL
1361 ** TABLE statement, use all columns from the content table.
1362 */
1363 if( rc==SQLITE_OK && zContent ){
1364 sqlite3_free(zCompress);
1365 sqlite3_free(zUncompress);
1366 zCompress = 0;
1367 zUncompress = 0;
1368 if( nCol==0 ){
1369 sqlite3_free((void*)aCol);
1370 aCol = 0;
1371 rc = fts3ContentColumns(db, argv[1], zContent,&aCol,&nCol,&nString,pzErr);
1372
1373 /* If a languageid= option was specified, remove the language id
1374 ** column from the aCol[] array. */
1375 if( rc==SQLITE_OK && zLanguageid ){
1376 int j;
1377 for(j=0; j<nCol; j++){
1378 if( sqlite3_stricmp(zLanguageid, aCol[j])==0 ){
1379 int k;
1380 for(k=j; k<nCol; k++) aCol[k] = aCol[k+1];
1381 nCol--;
1382 break;
1383 }
1384 }
1385 }
1386 }
1387 }
1388 if( rc!=SQLITE_OK ) goto fts3_init_out;
1389
1390 if( nCol==0 ){
1391 assert( nString==0 );
1392 aCol[0] = "content";
1393 nString = 8;
1394 nCol = 1;
1395 }
1396
1397 if( pTokenizer==0 ){
1398 rc = sqlite3Fts3InitTokenizer(pHash, "simple", &pTokenizer, pzErr);
1399 if( rc!=SQLITE_OK ) goto fts3_init_out;
1400 }
1401 assert( pTokenizer );
1402
1403 rc = fts3PrefixParameter(zPrefix, &nIndex, &aIndex);
1404 if( rc==SQLITE_ERROR ){
1405 assert( zPrefix );
1406 sqlite3Fts3ErrMsg(pzErr, "error parsing prefix parameter: %s", zPrefix);
1407 }
1408 if( rc!=SQLITE_OK ) goto fts3_init_out;
1409
1410 /* Allocate and populate the Fts3Table structure. */
1411 nByte = sizeof(Fts3Table) + /* Fts3Table */
1412 nCol * sizeof(char *) + /* azColumn */
1413 nIndex * sizeof(struct Fts3Index) + /* aIndex */
1414 nCol * sizeof(u8) + /* abNotindexed */
1415 nName + /* zName */
1416 nDb + /* zDb */
1417 nString; /* Space for azColumn strings */
1418 p = (Fts3Table*)sqlite3_malloc64(nByte);
1419 if( p==0 ){
1420 rc = SQLITE_NOMEM;
1421 goto fts3_init_out;
1422 }
1423 memset(p, 0, nByte);
1424 p->db = db;
1425 p->nColumn = nCol;
1426 p->nPendingData = 0;
1427 p->azColumn = (char **)&p[1];
1428 p->pTokenizer = pTokenizer;
1429 p->nMaxPendingData = FTS3_MAX_PENDING_DATA;
1430 p->bHasDocsize = (isFts4 && bNoDocsize==0);
1431 p->bHasStat = (u8)isFts4;
1432 p->bFts4 = (u8)isFts4;
1433 p->bDescIdx = (u8)bDescIdx;
1434 p->nAutoincrmerge = 0xff; /* 0xff means setting unknown */
1435 p->zContentTbl = zContent;
1436 p->zLanguageid = zLanguageid;
1437 zContent = 0;
1438 zLanguageid = 0;
1439 TESTONLY( p->inTransaction = -1 );
1440 TESTONLY( p->mxSavepoint = -1 );
1441
1442 p->aIndex = (struct Fts3Index *)&p->azColumn[nCol];
1443 memcpy(p->aIndex, aIndex, sizeof(struct Fts3Index) * nIndex);
1444 p->nIndex = nIndex;
1445 for(i=0; i<nIndex; i++){
1446 fts3HashInit(&p->aIndex[i].hPending, FTS3_HASH_STRING, 1);
1447 }
1448 p->abNotindexed = (u8 *)&p->aIndex[nIndex];
1449
1450 /* Fill in the zName and zDb fields of the vtab structure. */
1451 zCsr = (char *)&p->abNotindexed[nCol];
1452 p->zName = zCsr;
1453 memcpy(zCsr, argv[2], nName);
1454 zCsr += nName;
1455 p->zDb = zCsr;
1456 memcpy(zCsr, argv[1], nDb);
1457 zCsr += nDb;
1458
1459 /* Fill in the azColumn array */
1460 for(iCol=0; iCol<nCol; iCol++){
1461 char *z;
1462 int n = 0;
1463 z = (char *)sqlite3Fts3NextToken(aCol[iCol], &n);
1464 if( n>0 ){
1465 memcpy(zCsr, z, n);
1466 }
1467 zCsr[n] = '\0';
1468 sqlite3Fts3Dequote(zCsr);
1469 p->azColumn[iCol] = zCsr;
1470 zCsr += n+1;
1471 assert( zCsr <= &((char *)p)[nByte] );
1472 }
1473
1474 /* Fill in the abNotindexed array */
1475 for(iCol=0; iCol<nCol; iCol++){
1476 int n = (int)strlen(p->azColumn[iCol]);
1477 for(i=0; i<nNotindexed; i++){
1478 char *zNot = azNotindexed[i];
1479 if( zNot && n==(int)strlen(zNot)
1480 && 0==sqlite3_strnicmp(p->azColumn[iCol], zNot, n)
1481 ){
1482 p->abNotindexed[iCol] = 1;
1483 sqlite3_free(zNot);
1484 azNotindexed[i] = 0;
1485 }
1486 }
1487 }
1488 for(i=0; i<nNotindexed; i++){
1489 if( azNotindexed[i] ){
1490 sqlite3Fts3ErrMsg(pzErr, "no such column: %s", azNotindexed[i]);
1491 rc = SQLITE_ERROR;
1492 }
1493 }
1494
1495 if( rc==SQLITE_OK && (zCompress==0)!=(zUncompress==0) ){
1496 char const *zMiss = (zCompress==0 ? "compress" : "uncompress");
1497 rc = SQLITE_ERROR;
1498 sqlite3Fts3ErrMsg(pzErr, "missing %s parameter in fts4 constructor", zMiss);
1499 }
1500 p->zReadExprlist = fts3ReadExprList(p, zUncompress, &rc);
1501 p->zWriteExprlist = fts3WriteExprList(p, zCompress, &rc);
1502 if( rc!=SQLITE_OK ) goto fts3_init_out;
1503
1504 /* If this is an xCreate call, create the underlying tables in the
1505 ** database. TODO: For xConnect(), it could verify that said tables exist.
1506 */
1507 if( isCreate ){
1508 rc = fts3CreateTables(p);
1509 }
1510
1511 /* Check to see if a legacy fts3 table has been "upgraded" by the
1512 ** addition of a %_stat table so that it can use incremental merge.
1513 */
1514 if( !isFts4 && !isCreate ){
1515 p->bHasStat = 2;
1516 }
1517
1518 /* Figure out the page-size for the database. This is required in order to
1519 ** estimate the cost of loading large doclists from the database. */
1520 fts3DatabasePageSize(&rc, p);
1521 p->nNodeSize = p->nPgsz-35;
1522
1523 #if defined(SQLITE_DEBUG)||defined(SQLITE_TEST)
1524 p->nMergeCount = FTS3_MERGE_COUNT;
1525 #endif
1526
1527 /* Declare the table schema to SQLite. */
1528 fts3DeclareVtab(&rc, p);
1529
1530 fts3_init_out:
1531 sqlite3_free(zPrefix);
1532 sqlite3_free(aIndex);
1533 sqlite3_free(zCompress);
1534 sqlite3_free(zUncompress);
1535 sqlite3_free(zContent);
1536 sqlite3_free(zLanguageid);
1537 for(i=0; i<nNotindexed; i++) sqlite3_free(azNotindexed[i]);
1538 sqlite3_free((void *)aCol);
1539 sqlite3_free((void *)azNotindexed);
1540 if( rc!=SQLITE_OK ){
1541 if( p ){
1542 fts3DisconnectMethod((sqlite3_vtab *)p);
1543 }else if( pTokenizer ){
1544 pTokenizer->pModule->xDestroy(pTokenizer);
1545 }
1546 }else{
1547 assert( p->pSegments==0 );
1548 *ppVTab = &p->base;
1549 }
1550 return rc;
1551 }
1552
1553 /*
1554 ** The xConnect() and xCreate() methods for the virtual table. All the
1555 ** work is done in function fts3InitVtab().
1556 */
1557 static int fts3ConnectMethod(
1558 sqlite3 *db, /* Database connection */
1559 void *pAux, /* Pointer to tokenizer hash table */
1560 int argc, /* Number of elements in argv array */
1561 const char * const *argv, /* xCreate/xConnect argument array */
1562 sqlite3_vtab **ppVtab, /* OUT: New sqlite3_vtab object */
1563 char **pzErr /* OUT: sqlite3_malloc'd error message */
1564 ){
1565 return fts3InitVtab(0, db, pAux, argc, argv, ppVtab, pzErr);
1566 }
1567 static int fts3CreateMethod(
1568 sqlite3 *db, /* Database connection */
1569 void *pAux, /* Pointer to tokenizer hash table */
1570 int argc, /* Number of elements in argv array */
1571 const char * const *argv, /* xCreate/xConnect argument array */
1572 sqlite3_vtab **ppVtab, /* OUT: New sqlite3_vtab object */
1573 char **pzErr /* OUT: sqlite3_malloc'd error message */
1574 ){
1575 return fts3InitVtab(1, db, pAux, argc, argv, ppVtab, pzErr);
1576 }
1577
1578 /*
1579 ** Set the pIdxInfo->estimatedRows variable to nRow. Unless this
1580 ** extension is currently being used by a version of SQLite too old to
1581 ** support estimatedRows. In that case this function is a no-op.
1582 */
1583 static void fts3SetEstimatedRows(sqlite3_index_info *pIdxInfo, i64 nRow){
1584 #if SQLITE_VERSION_NUMBER>=3008002
1585 if( sqlite3_libversion_number()>=3008002 ){
1586 pIdxInfo->estimatedRows = nRow;
1587 }
1588 #endif
1589 }
1590
1591 /*
1592 ** Set the SQLITE_INDEX_SCAN_UNIQUE flag in pIdxInfo->flags. Unless this
1593 ** extension is currently being used by a version of SQLite too old to
1594 ** support index-info flags. In that case this function is a no-op.
1595 */
1596 static void fts3SetUniqueFlag(sqlite3_index_info *pIdxInfo){
1597 #if SQLITE_VERSION_NUMBER>=3008012
1598 if( sqlite3_libversion_number()>=3008012 ){
1599 pIdxInfo->idxFlags |= SQLITE_INDEX_SCAN_UNIQUE;
1600 }
1601 #endif
1602 }
1603
1604 /*
1605 ** Implementation of the xBestIndex method for FTS3 tables. There
1606 ** are three possible strategies, in order of preference:
1607 **
1608 ** 1. Direct lookup by rowid or docid.
1609 ** 2. Full-text search using a MATCH operator on a non-docid column.
1610 ** 3. Linear scan of %_content table.
1611 */
1612 static int fts3BestIndexMethod(sqlite3_vtab *pVTab, sqlite3_index_info *pInfo){
1613 Fts3Table *p = (Fts3Table *)pVTab;
1614 int i; /* Iterator variable */
1615 int iCons = -1; /* Index of constraint to use */
1616
1617 int iLangidCons = -1; /* Index of langid=x constraint, if present */
1618 int iDocidGe = -1; /* Index of docid>=x constraint, if present */
1619 int iDocidLe = -1; /* Index of docid<=x constraint, if present */
1620 int iIdx;
1621
1622 if( p->bLock ){
1623 return SQLITE_ERROR;
1624 }
1625
1626 /* By default use a full table scan. This is an expensive option,
1627 ** so search through the constraints to see if a more efficient
1628 ** strategy is possible.
1629 */
1630 pInfo->idxNum = FTS3_FULLSCAN_SEARCH;
1631 pInfo->estimatedCost = 5000000;
1632 for(i=0; i<pInfo->nConstraint; i++){
1633 int bDocid; /* True if this constraint is on docid */
1634 struct sqlite3_index_constraint *pCons = &pInfo->aConstraint[i];
1635 if( pCons->usable==0 ){
1636 if( pCons->op==SQLITE_INDEX_CONSTRAINT_MATCH ){
1637 /* There exists an unusable MATCH constraint. This means that if
1638 ** the planner does elect to use the results of this call as part
1639 ** of the overall query plan the user will see an "unable to use
1640 ** function MATCH in the requested context" error. To discourage
1641 ** this, return a very high cost here. */
1642 pInfo->idxNum = FTS3_FULLSCAN_SEARCH;
1643 pInfo->estimatedCost = 1e50;
1644 fts3SetEstimatedRows(pInfo, ((sqlite3_int64)1) << 50);
1645 return SQLITE_OK;
1646 }
1647 continue;
1648 }
1649
1650 bDocid = (pCons->iColumn<0 || pCons->iColumn==p->nColumn+1);
1651
1652 /* A direct lookup on the rowid or docid column. Assign a cost of 1.0. */
1653 if( iCons<0 && pCons->op==SQLITE_INDEX_CONSTRAINT_EQ && bDocid ){
1654 pInfo->idxNum = FTS3_DOCID_SEARCH;
1655 pInfo->estimatedCost = 1.0;
1656 iCons = i;
1657 }
1658
1659 /* A MATCH constraint. Use a full-text search.
1660 **
1661 ** If there is more than one MATCH constraint available, use the first
1662 ** one encountered. If there is both a MATCH constraint and a direct
1663 ** rowid/docid lookup, prefer the MATCH strategy. This is done even
1664 ** though the rowid/docid lookup is faster than a MATCH query, selecting
1665 ** it would lead to an "unable to use function MATCH in the requested
1666 ** context" error.
1667 */
1668 if( pCons->op==SQLITE_INDEX_CONSTRAINT_MATCH
1669 && pCons->iColumn>=0 && pCons->iColumn<=p->nColumn
1670 ){
1671 pInfo->idxNum = FTS3_FULLTEXT_SEARCH + pCons->iColumn;
1672 pInfo->estimatedCost = 2.0;
1673 iCons = i;
1674 }
1675
1676 /* Equality constraint on the langid column */
1677 if( pCons->op==SQLITE_INDEX_CONSTRAINT_EQ
1678 && pCons->iColumn==p->nColumn + 2
1679 ){
1680 iLangidCons = i;
1681 }
1682
1683 if( bDocid ){
1684 switch( pCons->op ){
1685 case SQLITE_INDEX_CONSTRAINT_GE:
1686 case SQLITE_INDEX_CONSTRAINT_GT:
1687 iDocidGe = i;
1688 break;
1689
1690 case SQLITE_INDEX_CONSTRAINT_LE:
1691 case SQLITE_INDEX_CONSTRAINT_LT:
1692 iDocidLe = i;
1693 break;
1694 }
1695 }
1696 }
1697
1698 /* If using a docid=? or rowid=? strategy, set the UNIQUE flag. */
1699 if( pInfo->idxNum==FTS3_DOCID_SEARCH ) fts3SetUniqueFlag(pInfo);
1700
1701 iIdx = 1;
1702 if( iCons>=0 ){
1703 pInfo->aConstraintUsage[iCons].argvIndex = iIdx++;
1704 pInfo->aConstraintUsage[iCons].omit = 1;
1705 }
1706 if( iLangidCons>=0 ){
1707 pInfo->idxNum |= FTS3_HAVE_LANGID;
1708 pInfo->aConstraintUsage[iLangidCons].argvIndex = iIdx++;
1709 }
1710 if( iDocidGe>=0 ){
1711 pInfo->idxNum |= FTS3_HAVE_DOCID_GE;
1712 pInfo->aConstraintUsage[iDocidGe].argvIndex = iIdx++;
1713 }
1714 if( iDocidLe>=0 ){
1715 pInfo->idxNum |= FTS3_HAVE_DOCID_LE;
1716 pInfo->aConstraintUsage[iDocidLe].argvIndex = iIdx++;
1717 }
1718
1719 /* Regardless of the strategy selected, FTS can deliver rows in rowid (or
1720 ** docid) order. Both ascending and descending are possible.
1721 */
1722 if( pInfo->nOrderBy==1 ){
1723 struct sqlite3_index_orderby *pOrder = &pInfo->aOrderBy[0];
1724 if( pOrder->iColumn<0 || pOrder->iColumn==p->nColumn+1 ){
1725 if( pOrder->desc ){
1726 pInfo->idxStr = "DESC";
1727 }else{
1728 pInfo->idxStr = "ASC";
1729 }
1730 pInfo->orderByConsumed = 1;
1731 }
1732 }
1733
1734 assert( p->pSegments==0 );
1735 return SQLITE_OK;
1736 }
1737
1738 /*
1739 ** Implementation of xOpen method.
1740 */
1741 static int fts3OpenMethod(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCsr){
1742 sqlite3_vtab_cursor *pCsr; /* Allocated cursor */
1743
1744 UNUSED_PARAMETER(pVTab);
1745
1746 /* Allocate a buffer large enough for an Fts3Cursor structure. If the
1747 ** allocation succeeds, zero it and return SQLITE_OK. Otherwise,
1748 ** if the allocation fails, return SQLITE_NOMEM.
1749 */
1750 *ppCsr = pCsr = (sqlite3_vtab_cursor *)sqlite3_malloc(sizeof(Fts3Cursor));
1751 if( !pCsr ){
1752 return SQLITE_NOMEM;
1753 }
1754 memset(pCsr, 0, sizeof(Fts3Cursor));
1755 return SQLITE_OK;
1756 }
1757
1758 /*
1759 ** Finalize the statement handle at pCsr->pStmt.
1760 **
1761 ** Or, if that statement handle is one created by fts3CursorSeekStmt(),
1762 ** and the Fts3Table.pSeekStmt slot is currently NULL, save the statement
1763 ** pointer there instead of finalizing it.
1764 */
1765 static void fts3CursorFinalizeStmt(Fts3Cursor *pCsr){
1766 if( pCsr->bSeekStmt ){
1767 Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
1768 if( p->pSeekStmt==0 ){
1769 p->pSeekStmt = pCsr->pStmt;
1770 sqlite3_reset(pCsr->pStmt);
1771 pCsr->pStmt = 0;
1772 }
1773 pCsr->bSeekStmt = 0;
1774 }
1775 sqlite3_finalize(pCsr->pStmt);
1776 }
1777
1778 /*
1779 ** Free all resources currently held by the cursor passed as the only
1780 ** argument.
1781 */
1782 static void fts3ClearCursor(Fts3Cursor *pCsr){
1783 fts3CursorFinalizeStmt(pCsr);
1784 sqlite3Fts3FreeDeferredTokens(pCsr);
1785 sqlite3_free(pCsr->aDoclist);
1786 sqlite3Fts3MIBufferFree(pCsr->pMIBuffer);
1787 sqlite3Fts3ExprFree(pCsr->pExpr);
1788 memset(&(&pCsr->base)[1], 0, sizeof(Fts3Cursor)-sizeof(sqlite3_vtab_cursor));
1789 }
1790
1791 /*
1792 ** Close the cursor. For additional information see the documentation
1793 ** on the xClose method of the virtual table interface.
1794 */
1795 static int fts3CloseMethod(sqlite3_vtab_cursor *pCursor){
1796 Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;
1797 assert( ((Fts3Table *)pCsr->base.pVtab)->pSegments==0 );
1798 fts3ClearCursor(pCsr);
1799 assert( ((Fts3Table *)pCsr->base.pVtab)->pSegments==0 );
1800 sqlite3_free(pCsr);
1801 return SQLITE_OK;
1802 }
1803
1804 /*
1805 ** If pCsr->pStmt has not been prepared (i.e. if pCsr->pStmt==0), then
1806 ** compose and prepare an SQL statement of the form:
1807 **
1808 ** "SELECT <columns> FROM %_content WHERE rowid = ?"
1809 **
1810 ** (or the equivalent for a content=xxx table) and set pCsr->pStmt to
1811 ** it. If an error occurs, return an SQLite error code.
1812 */
1813 static int fts3CursorSeekStmt(Fts3Cursor *pCsr){
1814 int rc = SQLITE_OK;
1815 if( pCsr->pStmt==0 ){
1816 Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
1817 char *zSql;
1818 if( p->pSeekStmt ){
1819 pCsr->pStmt = p->pSeekStmt;
1820 p->pSeekStmt = 0;
1821 }else{
1822 zSql = sqlite3_mprintf("SELECT %s WHERE rowid = ?", p->zReadExprlist);
1823 if( !zSql ) return SQLITE_NOMEM;
1824 p->bLock++;
1825 rc = sqlite3Fts3PrepareStmt(p, zSql, 1, 1, &pCsr->pStmt);
1826 p->bLock--;
1827 sqlite3_free(zSql);
1828 }
1829 if( rc==SQLITE_OK ) pCsr->bSeekStmt = 1;
1830 }
1831 return rc;
1832 }
1833
1834 /*
1835 ** Position the pCsr->pStmt statement so that it is on the row
1836 ** of the %_content table that contains the last match. Return
1837 ** SQLITE_OK on success.
1838 */
1839 static int fts3CursorSeek(sqlite3_context *pContext, Fts3Cursor *pCsr){
1840 int rc = SQLITE_OK;
1841 if( pCsr->isRequireSeek ){
1842 rc = fts3CursorSeekStmt(pCsr);
1843 if( rc==SQLITE_OK ){
1844 Fts3Table *pTab = (Fts3Table*)pCsr->base.pVtab;
1845 pTab->bLock++;
1846 sqlite3_bind_int64(pCsr->pStmt, 1, pCsr->iPrevId);
1847 pCsr->isRequireSeek = 0;
1848 if( SQLITE_ROW==sqlite3_step(pCsr->pStmt) ){
1849 pTab->bLock--;
1850 return SQLITE_OK;
1851 }else{
1852 pTab->bLock--;
1853 rc = sqlite3_reset(pCsr->pStmt);
1854 if( rc==SQLITE_OK && ((Fts3Table *)pCsr->base.pVtab)->zContentTbl==0 ){
1855 /* If no row was found and no error has occurred, then the %_content
1856 ** table is missing a row that is present in the full-text index.
1857 ** The data structures are corrupt. */
1858 rc = FTS_CORRUPT_VTAB;
1859 pCsr->isEof = 1;
1860 }
1861 }
1862 }
1863 }
1864
1865 if( rc!=SQLITE_OK && pContext ){
1866 sqlite3_result_error_code(pContext, rc);
1867 }
1868 return rc;
1869 }
1870
1871 /*
1872 ** This function is used to process a single interior node when searching
1873 ** a b-tree for a term or term prefix. The node data is passed to this
1874 ** function via the zNode/nNode parameters. The term to search for is
1875 ** passed in zTerm/nTerm.
1876 **
1877 ** If piFirst is not NULL, then this function sets *piFirst to the blockid
1878 ** of the child node that heads the sub-tree that may contain the term.
1879 **
1880 ** If piLast is not NULL, then *piLast is set to the right-most child node
1881 ** that heads a sub-tree that may contain a term for which zTerm/nTerm is
1882 ** a prefix.
1883 **
1884 ** If an OOM error occurs, SQLITE_NOMEM is returned. Otherwise, SQLITE_OK.
1885 */
1886 static int fts3ScanInteriorNode(
1887 const char *zTerm, /* Term to select leaves for */
1888 int nTerm, /* Size of term zTerm in bytes */
1889 const char *zNode, /* Buffer containing segment interior node */
1890 int nNode, /* Size of buffer at zNode */
1891 sqlite3_int64 *piFirst, /* OUT: Selected child node */
1892 sqlite3_int64 *piLast /* OUT: Selected child node */
1893 ){
1894 int rc = SQLITE_OK; /* Return code */
1895 const char *zCsr = zNode; /* Cursor to iterate through node */
1896 const char *zEnd = &zCsr[nNode];/* End of interior node buffer */
1897 char *zBuffer = 0; /* Buffer to load terms into */
1898 i64 nAlloc = 0; /* Size of allocated buffer */
1899 int isFirstTerm = 1; /* True when processing first term on page */
1900 u64 iChild; /* Block id of child node to descend to */
1901 int nBuffer = 0; /* Total term size */
1902
1903 /* Skip over the 'height' varint that occurs at the start of every
1904 ** interior node. Then load the blockid of the left-child of the b-tree
1905 ** node into variable iChild.
1906 **
1907 ** Even if the data structure on disk is corrupted, this (reading two
1908 ** varints from the buffer) does not risk an overread. If zNode is a
1909 ** root node, then the buffer comes from a SELECT statement. SQLite does
1910 ** not make this guarantee explicitly, but in practice there are always
1911 ** either more than 20 bytes of allocated space following the nNode bytes of
1912 ** contents, or two zero bytes. Or, if the node is read from the %_segments
1913 ** table, then there are always 20 bytes of zeroed padding following the
1914 ** nNode bytes of content (see sqlite3Fts3ReadBlock() for details).
1915 */
1916 zCsr += sqlite3Fts3GetVarintU(zCsr, &iChild);
1917 zCsr += sqlite3Fts3GetVarintU(zCsr, &iChild);
1918 if( zCsr>zEnd ){
1919 return FTS_CORRUPT_VTAB;
1920 }
1921
1922 while( zCsr<zEnd && (piFirst || piLast) ){
1923 int cmp; /* memcmp() result */
1924 int nSuffix; /* Size of term suffix */
1925 int nPrefix = 0; /* Size of term prefix */
1926
1927 /* Load the next term on the node into zBuffer. Use realloc() to expand
1928 ** the size of zBuffer if required. */
1929 if( !isFirstTerm ){
1930 zCsr += fts3GetVarint32(zCsr, &nPrefix);
1931 if( nPrefix>nBuffer ){
1932 rc = FTS_CORRUPT_VTAB;
1933 goto finish_scan;
1934 }
1935 }
1936 isFirstTerm = 0;
1937 zCsr += fts3GetVarint32(zCsr, &nSuffix);
1938
1939 assert( nPrefix>=0 && nSuffix>=0 );
1940 if( nPrefix>zCsr-zNode || nSuffix>zEnd-zCsr || nSuffix==0 ){
1941 rc = FTS_CORRUPT_VTAB;
1942 goto finish_scan;
1943 }
1944 if( (i64)nPrefix+nSuffix>nAlloc ){
1945 char *zNew;
1946 nAlloc = ((i64)nPrefix+nSuffix) * 2;
1947 zNew = (char *)sqlite3_realloc64(zBuffer, nAlloc);
1948 if( !zNew ){
1949 rc = SQLITE_NOMEM;
1950 goto finish_scan;
1951 }
1952 zBuffer = zNew;
1953 }
1954 assert( zBuffer );
1955 memcpy(&zBuffer[nPrefix], zCsr, nSuffix);
1956 nBuffer = nPrefix + nSuffix;
1957 zCsr += nSuffix;
1958
1959 /* Compare the term we are searching for with the term just loaded from
1960 ** the interior node. If the specified term is greater than or equal
1961 ** to the term from the interior node, then all terms on the sub-tree
1962 ** headed by node iChild are smaller than zTerm. No need to search
1963 ** iChild.
1964 **
1965 ** If the interior node term is larger than the specified term, then
1966 ** the tree headed by iChild may contain the specified term.
1967 */
1968 cmp = memcmp(zTerm, zBuffer, (nBuffer>nTerm ? nTerm : nBuffer));
1969 if( piFirst && (cmp<0 || (cmp==0 && nBuffer>nTerm)) ){
1970 *piFirst = (i64)iChild;
1971 piFirst = 0;
1972 }
1973
1974 if( piLast && cmp<0 ){
1975 *piLast = (i64)iChild;
1976 piLast = 0;
1977 }
1978
1979 iChild++;
1980 };
1981
1982 if( piFirst ) *piFirst = (i64)iChild;
1983 if( piLast ) *piLast = (i64)iChild;
1984
1985 finish_scan:
1986 sqlite3_free(zBuffer);
1987 return rc;
1988 }
1989
1990
1991 /*
1992 ** The buffer pointed to by argument zNode (size nNode bytes) contains an
1993 ** interior node of a b-tree segment. The zTerm buffer (size nTerm bytes)
1994 ** contains a term. This function searches the sub-tree headed by the zNode
1995 ** node for the range of leaf nodes that may contain the specified term
1996 ** or terms for which the specified term is a prefix.
1997 **
1998 ** If piLeaf is not NULL, then *piLeaf is set to the blockid of the
1999 ** left-most leaf node in the tree that may contain the specified term.
2000 ** If piLeaf2 is not NULL, then *piLeaf2 is set to the blockid of the
2001 ** right-most leaf node that may contain a term for which the specified
2002 ** term is a prefix.
2003 **
2004 ** It is possible that the range of returned leaf nodes does not contain
2005 ** the specified term or any terms for which it is a prefix. However, if the
2006 ** segment does contain any such terms, they are stored within the identified
2007 ** range. Because this function only inspects interior segment nodes (and
2008 ** never loads leaf nodes into memory), it is not possible to be sure.
2009 **
2010 ** If an error occurs, an error code other than SQLITE_OK is returned.
2011 */
2012 static int fts3SelectLeaf(
2013 Fts3Table *p, /* Virtual table handle */
2014 const char *zTerm, /* Term to select leaves for */
2015 int nTerm, /* Size of term zTerm in bytes */
2016 const char *zNode, /* Buffer containing segment interior node */
2017 int nNode, /* Size of buffer at zNode */
2018 sqlite3_int64 *piLeaf, /* Selected leaf node */
2019 sqlite3_int64 *piLeaf2 /* Selected leaf node */
2020 ){
2021 int rc = SQLITE_OK; /* Return code */
2022 int iHeight; /* Height of this node in tree */
2023
2024 assert( piLeaf || piLeaf2 );
2025
2026 fts3GetVarint32(zNode, &iHeight);
2027 if( iHeight>FTS3_MAX_BTREE_HEIGHT ){
2028 rc = FTS_CORRUPT_VTAB;
2029 }else{
2030 rc = fts3ScanInteriorNode(zTerm, nTerm, zNode, nNode, piLeaf, piLeaf2);
2031 }
2032 assert_fts3_nc( !piLeaf2 || !piLeaf || rc!=SQLITE_OK || (*piLeaf<=*piLeaf2) );
2033
2034 if( rc==SQLITE_OK && iHeight>1 ){
2035 char *zBlob = 0; /* Blob read from %_segments table */
2036 int nBlob = 0; /* Size of zBlob in bytes */
2037
2038 if( piLeaf && piLeaf2 && (*piLeaf!=*piLeaf2) ){
2039 rc = sqlite3Fts3ReadBlock(p, *piLeaf, &zBlob, &nBlob, 0);
2040 if( rc==SQLITE_OK ){
2041 rc = fts3SelectLeaf(p, zTerm, nTerm, zBlob, nBlob, piLeaf, 0);
2042 }
2043 sqlite3_free(zBlob);
2044 piLeaf = 0;
2045 zBlob = 0;
2046 }
2047
2048 if( rc==SQLITE_OK ){
2049 rc = sqlite3Fts3ReadBlock(p, piLeaf?*piLeaf:*piLeaf2, &zBlob, &nBlob, 0);
2050 }
2051 if( rc==SQLITE_OK ){
2052 int iNewHeight = 0;
2053 fts3GetVarint32(zBlob, &iNewHeight);
2054 if( iNewHeight>=iHeight ){
2055 rc = FTS_CORRUPT_VTAB;
2056 }else{
2057 rc = fts3SelectLeaf(p, zTerm, nTerm, zBlob, nBlob, piLeaf, piLeaf2);
2058 }
2059 }
2060 sqlite3_free(zBlob);
2061 }
2062
2063 return rc;
2064 }
2065
2066 /*
2067 ** This function is used to create delta-encoded serialized lists of FTS3
2068 ** varints. Each call to this function appends a single varint to a list.
2069 */
2070 static void fts3PutDeltaVarint(
2071 char **pp, /* IN/OUT: Output pointer */
2072 sqlite3_int64 *piPrev, /* IN/OUT: Previous value written to list */
2073 sqlite3_int64 iVal /* Write this value to the list */
2074 ){
2075 assert_fts3_nc( iVal-*piPrev > 0 || (*piPrev==0 && iVal==0) );
2076 *pp += sqlite3Fts3PutVarint(*pp, iVal-*piPrev);
2077 *piPrev = iVal;
2078 }
2079
2080 /*
2081 ** When this function is called, *ppPoslist is assumed to point to the
2082 ** start of a position-list. After it returns, *ppPoslist points to the
2083 ** first byte after the position-list.
2084 **
2085 ** A position list is list of positions (delta encoded) and columns for
2086 ** a single document record of a doclist. So, in other words, this
2087 ** routine advances *ppPoslist so that it points to the next docid in
2088 ** the doclist, or to the first byte past the end of the doclist.
2089 **
2090 ** If pp is not NULL, then the contents of the position list are copied
2091 ** to *pp. *pp is set to point to the first byte past the last byte copied
2092 ** before this function returns.
2093 */
2094 static void fts3PoslistCopy(char **pp, char **ppPoslist){
2095 char *pEnd = *ppPoslist;
2096 char c = 0;
2097
2098 /* The end of a position list is marked by a zero encoded as an FTS3
2099 ** varint. A single POS_END (0) byte. Except, if the 0 byte is preceded by
2100 ** a byte with the 0x80 bit set, then it is not a varint 0, but the tail
2101 ** of some other, multi-byte, value.
2102 **
2103 ** The following while-loop moves pEnd to point to the first byte that is not
2104 ** immediately preceded by a byte with the 0x80 bit set. Then increments
2105 ** pEnd once more so that it points to the byte immediately following the
2106 ** last byte in the position-list.
2107 */
2108 while( *pEnd | c ){
2109 c = *pEnd++ & 0x80;
2110 testcase( c!=0 && (*pEnd)==0 );
2111 }
2112 pEnd++; /* Advance past the POS_END terminator byte */
2113
2114 if( pp ){
2115 int n = (int)(pEnd - *ppPoslist);
2116 char *p = *pp;
2117 memcpy(p, *ppPoslist, n);
2118 p += n;
2119 *pp = p;
2120 }
2121 *ppPoslist = pEnd;
2122 }
2123
2124 /*
2125 ** When this function is called, *ppPoslist is assumed to point to the
2126 ** start of a column-list. After it returns, *ppPoslist points to the
2127 ** to the terminator (POS_COLUMN or POS_END) byte of the column-list.
2128 **
2129 ** A column-list is list of delta-encoded positions for a single column
2130 ** within a single document within a doclist.
2131 **
2132 ** The column-list is terminated either by a POS_COLUMN varint (1) or
2133 ** a POS_END varint (0). This routine leaves *ppPoslist pointing to
2134 ** the POS_COLUMN or POS_END that terminates the column-list.
2135 **
2136 ** If pp is not NULL, then the contents of the column-list are copied
2137 ** to *pp. *pp is set to point to the first byte past the last byte copied
2138 ** before this function returns. The POS_COLUMN or POS_END terminator
2139 ** is not copied into *pp.
2140 */
2141 static void fts3ColumnlistCopy(char **pp, char **ppPoslist){
2142 char *pEnd = *ppPoslist;
2143 char c = 0;
2144
2145 /* A column-list is terminated by either a 0x01 or 0x00 byte that is
2146 ** not part of a multi-byte varint.
2147 */
2148 while( 0xFE & (*pEnd | c) ){
2149 c = *pEnd++ & 0x80;
2150 testcase( c!=0 && ((*pEnd)&0xfe)==0 );
2151 }
2152 if( pp ){
2153 int n = (int)(pEnd - *ppPoslist);
2154 char *p = *pp;
2155 memcpy(p, *ppPoslist, n);
2156 p += n;
2157 *pp = p;
2158 }
2159 *ppPoslist = pEnd;
2160 }
2161
2162 /*
2163 ** Value used to signify the end of an position-list. This must be
2164 ** as large or larger than any value that might appear on the
2165 ** position-list, even a position list that has been corrupted.
2166 */
2167 #define POSITION_LIST_END LARGEST_INT64
2168
2169 /*
2170 ** This function is used to help parse position-lists. When this function is
2171 ** called, *pp may point to the start of the next varint in the position-list
2172 ** being parsed, or it may point to 1 byte past the end of the position-list
2173 ** (in which case **pp will be a terminator bytes POS_END (0) or
2174 ** (1)).
2175 **
2176 ** If *pp points past the end of the current position-list, set *pi to
2177 ** POSITION_LIST_END and return. Otherwise, read the next varint from *pp,
2178 ** increment the current value of *pi by the value read, and set *pp to
2179 ** point to the next value before returning.
2180 **
2181 ** Before calling this routine *pi must be initialized to the value of
2182 ** the previous position, or zero if we are reading the first position
2183 ** in the position-list. Because positions are delta-encoded, the value
2184 ** of the previous position is needed in order to compute the value of
2185 ** the next position.
2186 */
2187 static void fts3ReadNextPos(
2188 char **pp, /* IN/OUT: Pointer into position-list buffer */
2189 sqlite3_int64 *pi /* IN/OUT: Value read from position-list */
2190 ){
2191 if( (**pp)&0xFE ){
2192 int iVal;
2193 *pp += fts3GetVarint32((*pp), &iVal);
2194 *pi += iVal;
2195 *pi -= 2;
2196 }else{
2197 *pi = POSITION_LIST_END;
2198 }
2199 }
2200
2201 /*
2202 ** If parameter iCol is not 0, write an POS_COLUMN (1) byte followed by
2203 ** the value of iCol encoded as a varint to *pp. This will start a new
2204 ** column list.
2205 **
2206 ** Set *pp to point to the byte just after the last byte written before
2207 ** returning (do not modify it if iCol==0). Return the total number of bytes
2208 ** written (0 if iCol==0).
2209 */
2210 static int fts3PutColNumber(char **pp, int iCol){
2211 int n = 0; /* Number of bytes written */
2212 if( iCol ){
2213 char *p = *pp; /* Output pointer */
2214 n = 1 + sqlite3Fts3PutVarint(&p[1], iCol);
2215 *p = 0x01;
2216 *pp = &p[n];
2217 }
2218 return n;
2219 }
2220
2221 /*
2222 ** Compute the union of two position lists. The output written
2223 ** into *pp contains all positions of both *pp1 and *pp2 in sorted
2224 ** order and with any duplicates removed. All pointers are
2225 ** updated appropriately. The caller is responsible for insuring
2226 ** that there is enough space in *pp to hold the complete output.
2227 */
2228 static int fts3PoslistMerge(
2229 char **pp, /* Output buffer */
2230 char **pp1, /* Left input list */
2231 char **pp2 /* Right input list */
2232 ){
2233 char *p = *pp;
2234 char *p1 = *pp1;
2235 char *p2 = *pp2;
2236
2237 while( *p1 || *p2 ){
2238 int iCol1; /* The current column index in pp1 */
2239 int iCol2; /* The current column index in pp2 */
2240
2241 if( *p1==POS_COLUMN ){
2242 fts3GetVarint32(&p1[1], &iCol1);
2243 if( iCol1==0 ) return FTS_CORRUPT_VTAB;
2244 }
2245 else if( *p1==POS_END ) iCol1 = 0x7fffffff;
2246 else iCol1 = 0;
2247
2248 if( *p2==POS_COLUMN ){
2249 fts3GetVarint32(&p2[1], &iCol2);
2250 if( iCol2==0 ) return FTS_CORRUPT_VTAB;
2251 }
2252 else if( *p2==POS_END ) iCol2 = 0x7fffffff;
2253 else iCol2 = 0;
2254
2255 if( iCol1==iCol2 ){
2256 sqlite3_int64 i1 = 0; /* Last position from pp1 */
2257 sqlite3_int64 i2 = 0; /* Last position from pp2 */
2258 sqlite3_int64 iPrev = 0;
2259 int n = fts3PutColNumber(&p, iCol1);
2260 p1 += n;
2261 p2 += n;
2262
2263 /* At this point, both p1 and p2 point to the start of column-lists
2264 ** for the same column (the column with index iCol1 and iCol2).
2265 ** A column-list is a list of non-negative delta-encoded varints, each
2266 ** incremented by 2 before being stored. Each list is terminated by a
2267 ** POS_END (0) or POS_COLUMN (1). The following block merges the two lists
2268 ** and writes the results to buffer p. p is left pointing to the byte
2269 ** after the list written. No terminator (POS_END or POS_COLUMN) is
2270 ** written to the output.
2271 */
2272 fts3GetDeltaVarint(&p1, &i1);
2273 fts3GetDeltaVarint(&p2, &i2);
2274 if( i1<2 || i2<2 ){
2275 break;
2276 }
2277 do {
2278 fts3PutDeltaVarint(&p, &iPrev, (i1<i2) ? i1 : i2);
2279 iPrev -= 2;
2280 if( i1==i2 ){
2281 fts3ReadNextPos(&p1, &i1);
2282 fts3ReadNextPos(&p2, &i2);
2283 }else if( i1<i2 ){
2284 fts3ReadNextPos(&p1, &i1);
2285 }else{
2286 fts3ReadNextPos(&p2, &i2);
2287 }
2288 }while( i1!=POSITION_LIST_END || i2!=POSITION_LIST_END );
2289 }else if( iCol1<iCol2 ){
2290 p1 += fts3PutColNumber(&p, iCol1);
2291 fts3ColumnlistCopy(&p, &p1);
2292 }else{
2293 p2 += fts3PutColNumber(&p, iCol2);
2294 fts3ColumnlistCopy(&p, &p2);
2295 }
2296 }
2297
2298 *p++ = POS_END;
2299 *pp = p;
2300 *pp1 = p1 + 1;
2301 *pp2 = p2 + 1;
2302 return SQLITE_OK;
2303 }
2304
2305 /*
2306 ** This function is used to merge two position lists into one. When it is
2307 ** called, *pp1 and *pp2 must both point to position lists. A position-list is
2308 ** the part of a doclist that follows each document id. For example, if a row
2309 ** contains:
2310 **
2311 ** 'a b c'|'x y z'|'a b b a'
2312 **
2313 ** Then the position list for this row for token 'b' would consist of:
2314 **
2315 ** 0x02 0x01 0x02 0x03 0x03 0x00
2316 **
2317 ** When this function returns, both *pp1 and *pp2 are left pointing to the
2318 ** byte following the 0x00 terminator of their respective position lists.
2319 **
2320 ** If isSaveLeft is 0, an entry is added to the output position list for
2321 ** each position in *pp2 for which there exists one or more positions in
2322 ** *pp1 so that (pos(*pp2)>pos(*pp1) && pos(*pp2)-pos(*pp1)<=nToken). i.e.
2323 ** when the *pp1 token appears before the *pp2 token, but not more than nToken
2324 ** slots before it.
2325 **
2326 ** e.g. nToken==1 searches for adjacent positions.
2327 */
2328 static int fts3PoslistPhraseMerge(
2329 char **pp, /* IN/OUT: Preallocated output buffer */
2330 int nToken, /* Maximum difference in token positions */
2331 int isSaveLeft, /* Save the left position */
2332 int isExact, /* If *pp1 is exactly nTokens before *pp2 */
2333 char **pp1, /* IN/OUT: Left input list */
2334 char **pp2 /* IN/OUT: Right input list */
2335 ){
2336 char *p = *pp;
2337 char *p1 = *pp1;
2338 char *p2 = *pp2;
2339 int iCol1 = 0;
2340 int iCol2 = 0;
2341
2342 /* Never set both isSaveLeft and isExact for the same invocation. */
2343 assert( isSaveLeft==0 || isExact==0 );
2344
2345 assert_fts3_nc( p!=0 && *p1!=0 && *p2!=0 );
2346 if( *p1==POS_COLUMN ){
2347 p1++;
2348 p1 += fts3GetVarint32(p1, &iCol1);
2349 /* iCol1==0 indicates corruption. Column 0 does not have a POS_COLUMN
2350 ** entry, so this is actually end-of-doclist. */
2351 if( iCol1==0 ) return 0;
2352 }
2353 if( *p2==POS_COLUMN ){
2354 p2++;
2355 p2 += fts3GetVarint32(p2, &iCol2);
2356 /* As above, iCol2==0 indicates corruption. */
2357 if( iCol2==0 ) return 0;
2358 }
2359
2360 while( 1 ){
2361 if( iCol1==iCol2 ){
2362 char *pSave = p;
2363 sqlite3_int64 iPrev = 0;
2364 sqlite3_int64 iPos1 = 0;
2365 sqlite3_int64 iPos2 = 0;
2366
2367 if( iCol1 ){
2368 *p++ = POS_COLUMN;
2369 p += sqlite3Fts3PutVarint(p, iCol1);
2370 }
2371
2372 fts3GetDeltaVarint(&p1, &iPos1); iPos1 -= 2;
2373 fts3GetDeltaVarint(&p2, &iPos2); iPos2 -= 2;
2374 if( iPos1<0 || iPos2<0 ) break;
2375
2376 while( 1 ){
2377 if( iPos2==iPos1+nToken
2378 || (isExact==0 && iPos2>iPos1 && iPos2<=iPos1+nToken)
2379 ){
2380 sqlite3_int64 iSave;
2381 iSave = isSaveLeft ? iPos1 : iPos2;
2382 fts3PutDeltaVarint(&p, &iPrev, iSave+2); iPrev -= 2;
2383 pSave = 0;
2384 assert( p );
2385 }
2386 if( (!isSaveLeft && iPos2<=(iPos1+nToken)) || iPos2<=iPos1 ){
2387 if( (*p2&0xFE)==0 ) break;
2388 fts3GetDeltaVarint(&p2, &iPos2); iPos2 -= 2;
2389 }else{
2390 if( (*p1&0xFE)==0 ) break;
2391 fts3GetDeltaVarint(&p1, &iPos1); iPos1 -= 2;
2392 }
2393 }
2394
2395 if( pSave ){
2396 assert( pp && p );
2397 p = pSave;
2398 }
2399
2400 fts3ColumnlistCopy(0, &p1);
2401 fts3ColumnlistCopy(0, &p2);
2402 assert( (*p1&0xFE)==0 && (*p2&0xFE)==0 );
2403 if( 0==*p1 || 0==*p2 ) break;
2404
2405 p1++;
2406 p1 += fts3GetVarint32(p1, &iCol1);
2407 p2++;
2408 p2 += fts3GetVarint32(p2, &iCol2);
2409 }
2410
2411 /* Advance pointer p1 or p2 (whichever corresponds to the smaller of
2412 ** iCol1 and iCol2) so that it points to either the 0x00 that marks the
2413 ** end of the position list, or the 0x01 that precedes the next
2414 ** column-number in the position list.
2415 */
2416 else if( iCol1<iCol2 ){
2417 fts3ColumnlistCopy(0, &p1);
2418 if( 0==*p1 ) break;
2419 p1++;
2420 p1 += fts3GetVarint32(p1, &iCol1);
2421 }else{
2422 fts3ColumnlistCopy(0, &p2);
2423 if( 0==*p2 ) break;
2424 p2++;
2425 p2 += fts3GetVarint32(p2, &iCol2);
2426 }
2427 }
2428
2429 fts3PoslistCopy(0, &p2);
2430 fts3PoslistCopy(0, &p1);
2431 *pp1 = p1;
2432 *pp2 = p2;
2433 if( *pp==p ){
2434 return 0;
2435 }
2436 *p++ = 0x00;
2437 *pp = p;
2438 return 1;
2439 }
2440
2441 /*
2442 ** Merge two position-lists as required by the NEAR operator. The argument
2443 ** position lists correspond to the left and right phrases of an expression
2444 ** like:
2445 **
2446 ** "phrase 1" NEAR "phrase number 2"
2447 **
2448 ** Position list *pp1 corresponds to the left-hand side of the NEAR
2449 ** expression and *pp2 to the right. As usual, the indexes in the position
2450 ** lists are the offsets of the last token in each phrase (tokens "1" and "2"
2451 ** in the example above).
2452 **
2453 ** The output position list - written to *pp - is a copy of *pp2 with those
2454 ** entries that are not sufficiently NEAR entries in *pp1 removed.
2455 */
2456 static int fts3PoslistNearMerge(
2457 char **pp, /* Output buffer */
2458 char *aTmp, /* Temporary buffer space */
2459 int nRight, /* Maximum difference in token positions */
2460 int nLeft, /* Maximum difference in token positions */
2461 char **pp1, /* IN/OUT: Left input list */
2462 char **pp2 /* IN/OUT: Right input list */
2463 ){
2464 char *p1 = *pp1;
2465 char *p2 = *pp2;
2466
2467 char *pTmp1 = aTmp;
2468 char *pTmp2;
2469 char *aTmp2;
2470 int res = 1;
2471
2472 fts3PoslistPhraseMerge(&pTmp1, nRight, 0, 0, pp1, pp2);
2473 aTmp2 = pTmp2 = pTmp1;
2474 *pp1 = p1;
2475 *pp2 = p2;
2476 fts3PoslistPhraseMerge(&pTmp2, nLeft, 1, 0, pp2, pp1);
2477 if( pTmp1!=aTmp && pTmp2!=aTmp2 ){
2478 fts3PoslistMerge(pp, &aTmp, &aTmp2);
2479 }else if( pTmp1!=aTmp ){
2480 fts3PoslistCopy(pp, &aTmp);
2481 }else if( pTmp2!=aTmp2 ){
2482 fts3PoslistCopy(pp, &aTmp2);
2483 }else{
2484 res = 0;
2485 }
2486
2487 return res;
2488 }
2489
2490 /*
2491 ** An instance of this function is used to merge together the (potentially
2492 ** large number of) doclists for each term that matches a prefix query.
2493 ** See function fts3TermSelectMerge() for details.
2494 */
2495 typedef struct TermSelect TermSelect;
2496 struct TermSelect {
2497 char *aaOutput[16]; /* Malloc'd output buffers */
2498 int anOutput[16]; /* Size each output buffer in bytes */
2499 };
2500
2501 /*
2502 ** This function is used to read a single varint from a buffer. Parameter
2503 ** pEnd points 1 byte past the end of the buffer. When this function is
2504 ** called, if *pp points to pEnd or greater, then the end of the buffer
2505 ** has been reached. In this case *pp is set to 0 and the function returns.
2506 **
2507 ** If *pp does not point to or past pEnd, then a single varint is read
2508 ** from *pp. *pp is then set to point 1 byte past the end of the read varint.
2509 **
2510 ** If bDescIdx is false, the value read is added to *pVal before returning.
2511 ** If it is true, the value read is subtracted from *pVal before this
2512 ** function returns.
2513 */
2514 static void fts3GetDeltaVarint3(
2515 char **pp, /* IN/OUT: Point to read varint from */
2516 char *pEnd, /* End of buffer */
2517 int bDescIdx, /* True if docids are descending */
2518 sqlite3_int64 *pVal /* IN/OUT: Integer value */
2519 ){
2520 if( *pp>=pEnd ){
2521 *pp = 0;
2522 }else{
2523 u64 iVal;
2524 *pp += sqlite3Fts3GetVarintU(*pp, &iVal);
2525 if( bDescIdx ){
2526 *pVal = (i64)((u64)*pVal - iVal);
2527 }else{
2528 *pVal = (i64)((u64)*pVal + iVal);
2529 }
2530 }
2531 }
2532
2533 /*
2534 ** This function is used to write a single varint to a buffer. The varint
2535 ** is written to *pp. Before returning, *pp is set to point 1 byte past the
2536 ** end of the value written.
2537 **
2538 ** If *pbFirst is zero when this function is called, the value written to
2539 ** the buffer is that of parameter iVal.
2540 **
2541 ** If *pbFirst is non-zero when this function is called, then the value
2542 ** written is either (iVal-*piPrev) (if bDescIdx is zero) or (*piPrev-iVal)
2543 ** (if bDescIdx is non-zero).
2544 **
2545 ** Before returning, this function always sets *pbFirst to 1 and *piPrev
2546 ** to the value of parameter iVal.
2547 */
2548 static void fts3PutDeltaVarint3(
2549 char **pp, /* IN/OUT: Output pointer */
2550 int bDescIdx, /* True for descending docids */
2551 sqlite3_int64 *piPrev, /* IN/OUT: Previous value written to list */
2552 int *pbFirst, /* IN/OUT: True after first int written */
2553 sqlite3_int64 iVal /* Write this value to the list */
2554 ){
2555 sqlite3_uint64 iWrite;
2556 if( bDescIdx==0 || *pbFirst==0 ){
2557 assert_fts3_nc( *pbFirst==0 || iVal>=*piPrev );
2558 iWrite = (u64)iVal - (u64)*piPrev;
2559 }else{
2560 assert_fts3_nc( *piPrev>=iVal );
2561 iWrite = (u64)*piPrev - (u64)iVal;
2562 }
2563 assert( *pbFirst || *piPrev==0 );
2564 assert_fts3_nc( *pbFirst==0 || iWrite>0 );
2565 *pp += sqlite3Fts3PutVarint(*pp, iWrite);
2566 *piPrev = iVal;
2567 *pbFirst = 1;
2568 }
2569
2570
2571 /*
2572 ** This macro is used by various functions that merge doclists. The two
2573 ** arguments are 64-bit docid values. If the value of the stack variable
2574 ** bDescDoclist is 0 when this macro is invoked, then it returns (i1-i2).
2575 ** Otherwise, (i2-i1).
2576 **
2577 ** Using this makes it easier to write code that can merge doclists that are
2578 ** sorted in either ascending or descending order.
2579 */
2580 /* #define DOCID_CMP(i1, i2) ((bDescDoclist?-1:1) * (i64)((u64)i1-i2)) */
2581 #define DOCID_CMP(i1, i2) ((bDescDoclist?-1:1) * (i1>i2?1:((i1==i2)?0:-1)))
2582
2583 /*
2584 ** This function does an "OR" merge of two doclists (output contains all
2585 ** positions contained in either argument doclist). If the docids in the
2586 ** input doclists are sorted in ascending order, parameter bDescDoclist
2587 ** should be false. If they are sorted in ascending order, it should be
2588 ** passed a non-zero value.
2589 **
2590 ** If no error occurs, *paOut is set to point at an sqlite3_malloc'd buffer
2591 ** containing the output doclist and SQLITE_OK is returned. In this case
2592 ** *pnOut is set to the number of bytes in the output doclist.
2593 **
2594 ** If an error occurs, an SQLite error code is returned. The output values
2595 ** are undefined in this case.
2596 */
2597 static int fts3DoclistOrMerge(
2598 int bDescDoclist, /* True if arguments are desc */
2599 char *a1, int n1, /* First doclist */
2600 char *a2, int n2, /* Second doclist */
2601 char **paOut, int *pnOut /* OUT: Malloc'd doclist */
2602 ){
2603 int rc = SQLITE_OK;
2604 sqlite3_int64 i1 = 0;
2605 sqlite3_int64 i2 = 0;
2606 sqlite3_int64 iPrev = 0;
2607 char *pEnd1 = &a1[n1];
2608 char *pEnd2 = &a2[n2];
2609 char *p1 = a1;
2610 char *p2 = a2;
2611 char *p;
2612 char *aOut;
2613 int bFirstOut = 0;
2614
2615 *paOut = 0;
2616 *pnOut = 0;
2617
2618 /* Allocate space for the output. Both the input and output doclists
2619 ** are delta encoded. If they are in ascending order (bDescDoclist==0),
2620 ** then the first docid in each list is simply encoded as a varint. For
2621 ** each subsequent docid, the varint stored is the difference between the
2622 ** current and previous docid (a positive number - since the list is in
2623 ** ascending order).
2624 **
2625 ** The first docid written to the output is therefore encoded using the
2626 ** same number of bytes as it is in whichever of the input lists it is
2627 ** read from. And each subsequent docid read from the same input list
2628 ** consumes either the same or less bytes as it did in the input (since
2629 ** the difference between it and the previous value in the output must
2630 ** be a positive value less than or equal to the delta value read from
2631 ** the input list). The same argument applies to all but the first docid
2632 ** read from the 'other' list. And to the contents of all position lists
2633 ** that will be copied and merged from the input to the output.
2634 **
2635 ** However, if the first docid copied to the output is a negative number,
2636 ** then the encoding of the first docid from the 'other' input list may
2637 ** be larger in the output than it was in the input (since the delta value
2638 ** may be a larger positive integer than the actual docid).
2639 **
2640 ** The space required to store the output is therefore the sum of the
2641 ** sizes of the two inputs, plus enough space for exactly one of the input
2642 ** docids to grow.
2643 **
2644 ** A symmetric argument may be made if the doclists are in descending
2645 ** order.
2646 */
2647 aOut = sqlite3_malloc64((i64)n1+n2+FTS3_VARINT_MAX-1+FTS3_BUFFER_PADDING);
2648 if( !aOut ) return SQLITE_NOMEM;
2649
2650 p = aOut;
2651 fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1);
2652 fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2);
2653 while( p1 || p2 ){
2654 sqlite3_int64 iDiff = DOCID_CMP(i1, i2);
2655
2656 if( p2 && p1 && iDiff==0 ){
2657 fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i1);
2658 rc = fts3PoslistMerge(&p, &p1, &p2);
2659 if( rc ) break;
2660 fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);
2661 fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);
2662 }else if( !p2 || (p1 && iDiff<0) ){
2663 fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i1);
2664 fts3PoslistCopy(&p, &p1);
2665 fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);
2666 }else{
2667 fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i2);
2668 fts3PoslistCopy(&p, &p2);
2669 fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);
2670 }
2671
2672 assert( (p-aOut)<=((p1?(p1-a1):n1)+(p2?(p2-a2):n2)+FTS3_VARINT_MAX-1) );
2673 }
2674
2675 if( rc!=SQLITE_OK ){
2676 sqlite3_free(aOut);
2677 p = aOut = 0;
2678 }else{
2679 assert( (p-aOut)<=n1+n2+FTS3_VARINT_MAX-1 );
2680 memset(&aOut[(p-aOut)], 0, FTS3_BUFFER_PADDING);
2681 }
2682 *paOut = aOut;
2683 *pnOut = (int)(p-aOut);
2684 return rc;
2685 }
2686
2687 /*
2688 ** This function does a "phrase" merge of two doclists. In a phrase merge,
2689 ** the output contains a copy of each position from the right-hand input
2690 ** doclist for which there is a position in the left-hand input doclist
2691 ** exactly nDist tokens before it.
2692 **
2693 ** If the docids in the input doclists are sorted in ascending order,
2694 ** parameter bDescDoclist should be false. If they are sorted in ascending
2695 ** order, it should be passed a non-zero value.
2696 **
2697 ** The right-hand input doclist is overwritten by this function.
2698 */
2699 static int fts3DoclistPhraseMerge(
2700 int bDescDoclist, /* True if arguments are desc */
2701 int nDist, /* Distance from left to right (1=adjacent) */
2702 char *aLeft, int nLeft, /* Left doclist */
2703 char **paRight, int *pnRight /* IN/OUT: Right/output doclist */
2704 ){
2705 sqlite3_int64 i1 = 0;
2706 sqlite3_int64 i2 = 0;
2707 sqlite3_int64 iPrev = 0;
2708 char *aRight = *paRight;
2709 char *pEnd1 = &aLeft[nLeft];
2710 char *pEnd2 = &aRight[*pnRight];
2711 char *p1 = aLeft;
2712 char *p2 = aRight;
2713 char *p;
2714 int bFirstOut = 0;
2715 char *aOut;
2716
2717 assert( nDist>0 );
2718 if( bDescDoclist ){
2719 aOut = sqlite3_malloc64((sqlite3_int64)*pnRight + FTS3_VARINT_MAX);
2720 if( aOut==0 ) return SQLITE_NOMEM;
2721 }else{
2722 aOut = aRight;
2723 }
2724 p = aOut;
2725
2726 fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1);
2727 fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2);
2728
2729 while( p1 && p2 ){
2730 sqlite3_int64 iDiff = DOCID_CMP(i1, i2);
2731 if( iDiff==0 ){
2732 char *pSave = p;
2733 sqlite3_int64 iPrevSave = iPrev;
2734 int bFirstOutSave = bFirstOut;
2735
2736 fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i1);
2737 if( 0==fts3PoslistPhraseMerge(&p, nDist, 0, 1, &p1, &p2) ){
2738 p = pSave;
2739 iPrev = iPrevSave;
2740 bFirstOut = bFirstOutSave;
2741 }
2742 fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);
2743 fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);
2744 }else if( iDiff<0 ){
2745 fts3PoslistCopy(0, &p1);
2746 fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);
2747 }else{
2748 fts3PoslistCopy(0, &p2);
2749 fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);
2750 }
2751 }
2752
2753 *pnRight = (int)(p - aOut);
2754 if( bDescDoclist ){
2755 sqlite3_free(aRight);
2756 *paRight = aOut;
2757 }
2758
2759 return SQLITE_OK;
2760 }
2761
2762 /*
2763 ** Argument pList points to a position list nList bytes in size. This
2764 ** function checks to see if the position list contains any entries for
2765 ** a token in position 0 (of any column). If so, it writes argument iDelta
2766 ** to the output buffer pOut, followed by a position list consisting only
2767 ** of the entries from pList at position 0, and terminated by an 0x00 byte.
2768 ** The value returned is the number of bytes written to pOut (if any).
2769 */
2770 int sqlite3Fts3FirstFilter(
2771 sqlite3_int64 iDelta, /* Varint that may be written to pOut */
2772 char *pList, /* Position list (no 0x00 term) */
2773 int nList, /* Size of pList in bytes */
2774 char *pOut /* Write output here */
2775 ){
2776 int nOut = 0;
2777 int bWritten = 0; /* True once iDelta has been written */
2778 char *p = pList;
2779 char *pEnd = &pList[nList];
2780
2781 if( *p!=0x01 ){
2782 if( *p==0x02 ){
2783 nOut += sqlite3Fts3PutVarint(&pOut[nOut], iDelta);
2784 pOut[nOut++] = 0x02;
2785 bWritten = 1;
2786 }
2787 fts3ColumnlistCopy(0, &p);
2788 }
2789
2790 while( p<pEnd ){
2791 sqlite3_int64 iCol;
2792 p++;
2793 p += sqlite3Fts3GetVarint(p, &iCol);
2794 if( *p==0x02 ){
2795 if( bWritten==0 ){
2796 nOut += sqlite3Fts3PutVarint(&pOut[nOut], iDelta);
2797 bWritten = 1;
2798 }
2799 pOut[nOut++] = 0x01;
2800 nOut += sqlite3Fts3PutVarint(&pOut[nOut], iCol);
2801 pOut[nOut++] = 0x02;
2802 }
2803 fts3ColumnlistCopy(0, &p);
2804 }
2805 if( bWritten ){
2806 pOut[nOut++] = 0x00;
2807 }
2808
2809 return nOut;
2810 }
2811
2812
2813 /*
2814 ** Merge all doclists in the TermSelect.aaOutput[] array into a single
2815 ** doclist stored in TermSelect.aaOutput[0]. If successful, delete all
2816 ** other doclists (except the aaOutput[0] one) and return SQLITE_OK.
2817 **
2818 ** If an OOM error occurs, return SQLITE_NOMEM. In this case it is
2819 ** the responsibility of the caller to free any doclists left in the
2820 ** TermSelect.aaOutput[] array.
2821 */
2822 static int fts3TermSelectFinishMerge(Fts3Table *p, TermSelect *pTS){
2823 char *aOut = 0;
2824 int nOut = 0;
2825 int i;
2826
2827 /* Loop through the doclists in the aaOutput[] array. Merge them all
2828 ** into a single doclist.
2829 */
2830 for(i=0; i<SizeofArray(pTS->aaOutput); i++){
2831 if( pTS->aaOutput[i] ){
2832 if( !aOut ){
2833 aOut = pTS->aaOutput[i];
2834 nOut = pTS->anOutput[i];
2835 pTS->aaOutput[i] = 0;
2836 }else{
2837 int nNew;
2838 char *aNew;
2839
2840 int rc = fts3DoclistOrMerge(p->bDescIdx,
2841 pTS->aaOutput[i], pTS->anOutput[i], aOut, nOut, &aNew, &nNew
2842 );
2843 if( rc!=SQLITE_OK ){
2844 sqlite3_free(aOut);
2845 return rc;
2846 }
2847
2848 sqlite3_free(pTS->aaOutput[i]);
2849 sqlite3_free(aOut);
2850 pTS->aaOutput[i] = 0;
2851 aOut = aNew;
2852 nOut = nNew;
2853 }
2854 }
2855 }
2856
2857 pTS->aaOutput[0] = aOut;
2858 pTS->anOutput[0] = nOut;
2859 return SQLITE_OK;
2860 }
2861
2862 /*
2863 ** Merge the doclist aDoclist/nDoclist into the TermSelect object passed
2864 ** as the first argument. The merge is an "OR" merge (see function
2865 ** fts3DoclistOrMerge() for details).
2866 **
2867 ** This function is called with the doclist for each term that matches
2868 ** a queried prefix. It merges all these doclists into one, the doclist
2869 ** for the specified prefix. Since there can be a very large number of
2870 ** doclists to merge, the merging is done pair-wise using the TermSelect
2871 ** object.
2872 **
2873 ** This function returns SQLITE_OK if the merge is successful, or an
2874 ** SQLite error code (SQLITE_NOMEM) if an error occurs.
2875 */
2876 static int fts3TermSelectMerge(
2877 Fts3Table *p, /* FTS table handle */
2878 TermSelect *pTS, /* TermSelect object to merge into */
2879 char *aDoclist, /* Pointer to doclist */
2880 int nDoclist /* Size of aDoclist in bytes */
2881 ){
2882 if( pTS->aaOutput[0]==0 ){
2883 /* If this is the first term selected, copy the doclist to the output
2884 ** buffer using memcpy().
2885 **
2886 ** Add FTS3_VARINT_MAX bytes of unused space to the end of the
2887 ** allocation. This is so as to ensure that the buffer is big enough
2888 ** to hold the current doclist AND'd with any other doclist. If the
2889 ** doclists are stored in order=ASC order, this padding would not be
2890 ** required (since the size of [doclistA AND doclistB] is always less
2891 ** than or equal to the size of [doclistA] in that case). But this is
2892 ** not true for order=DESC. For example, a doclist containing (1, -1)
2893 ** may be smaller than (-1), as in the first example the -1 may be stored
2894 ** as a single-byte delta, whereas in the second it must be stored as a
2895 ** FTS3_VARINT_MAX byte varint.
2896 **
2897 ** Similar padding is added in the fts3DoclistOrMerge() function.
2898 */
2899 pTS->aaOutput[0] = sqlite3_malloc64((i64)nDoclist + FTS3_VARINT_MAX + 1);
2900 pTS->anOutput[0] = nDoclist;
2901 if( pTS->aaOutput[0] ){
2902 memcpy(pTS->aaOutput[0], aDoclist, nDoclist);
2903 memset(&pTS->aaOutput[0][nDoclist], 0, FTS3_VARINT_MAX);
2904 }else{
2905 return SQLITE_NOMEM;
2906 }
2907 }else{
2908 char *aMerge = aDoclist;
2909 int nMerge = nDoclist;
2910 int iOut;
2911
2912 for(iOut=0; iOut<SizeofArray(pTS->aaOutput); iOut++){
2913 if( pTS->aaOutput[iOut]==0 ){
2914 assert( iOut>0 );
2915 pTS->aaOutput[iOut] = aMerge;
2916 pTS->anOutput[iOut] = nMerge;
2917 break;
2918 }else{
2919 char *aNew;
2920 int nNew;
2921
2922 int rc = fts3DoclistOrMerge(p->bDescIdx, aMerge, nMerge,
2923 pTS->aaOutput[iOut], pTS->anOutput[iOut], &aNew, &nNew
2924 );
2925 if( rc!=SQLITE_OK ){
2926 if( aMerge!=aDoclist ) sqlite3_free(aMerge);
2927 return rc;
2928 }
2929
2930 if( aMerge!=aDoclist ) sqlite3_free(aMerge);
2931 sqlite3_free(pTS->aaOutput[iOut]);
2932 pTS->aaOutput[iOut] = 0;
2933
2934 aMerge = aNew;
2935 nMerge = nNew;
2936 if( (iOut+1)==SizeofArray(pTS->aaOutput) ){
2937 pTS->aaOutput[iOut] = aMerge;
2938 pTS->anOutput[iOut] = nMerge;
2939 }
2940 }
2941 }
2942 }
2943 return SQLITE_OK;
2944 }
2945
2946 /*
2947 ** Append SegReader object pNew to the end of the pCsr->apSegment[] array.
2948 */
2949 static int fts3SegReaderCursorAppend(
2950 Fts3MultiSegReader *pCsr,
2951 Fts3SegReader *pNew
2952 ){
2953 if( (pCsr->nSegment%16)==0 ){
2954 Fts3SegReader **apNew;
2955 sqlite3_int64 nByte = (pCsr->nSegment + 16)*sizeof(Fts3SegReader*);
2956 apNew = (Fts3SegReader **)sqlite3_realloc64(pCsr->apSegment, nByte);
2957 if( !apNew ){
2958 sqlite3Fts3SegReaderFree(pNew);
2959 return SQLITE_NOMEM;
2960 }
2961 pCsr->apSegment = apNew;
2962 }
2963 pCsr->apSegment[pCsr->nSegment++] = pNew;
2964 return SQLITE_OK;
2965 }
2966
2967 /*
2968 ** Add seg-reader objects to the Fts3MultiSegReader object passed as the
2969 ** 8th argument.
2970 **
2971 ** This function returns SQLITE_OK if successful, or an SQLite error code
2972 ** otherwise.
2973 */
2974 static int fts3SegReaderCursor(
2975 Fts3Table *p, /* FTS3 table handle */
2976 int iLangid, /* Language id */
2977 int iIndex, /* Index to search (from 0 to p->nIndex-1) */
2978 int iLevel, /* Level of segments to scan */
2979 const char *zTerm, /* Term to query for */
2980 int nTerm, /* Size of zTerm in bytes */
2981 int isPrefix, /* True for a prefix search */
2982 int isScan, /* True to scan from zTerm to EOF */
2983 Fts3MultiSegReader *pCsr /* Cursor object to populate */
2984 ){
2985 int rc = SQLITE_OK; /* Error code */
2986 sqlite3_stmt *pStmt = 0; /* Statement to iterate through segments */
2987 int rc2; /* Result of sqlite3_reset() */
2988
2989 /* If iLevel is less than 0 and this is not a scan, include a seg-reader
2990 ** for the pending-terms. If this is a scan, then this call must be being
2991 ** made by an fts4aux module, not an FTS table. In this case calling
2992 ** Fts3SegReaderPending might segfault, as the data structures used by
2993 ** fts4aux are not completely populated. So it's easiest to filter these
2994 ** calls out here. */
2995 if( iLevel<0 && p->aIndex && p->iPrevLangid==iLangid ){
2996 Fts3SegReader *pSeg = 0;
2997 rc = sqlite3Fts3SegReaderPending(p, iIndex, zTerm, nTerm, isPrefix||isScan, &pSeg);
2998 if( rc==SQLITE_OK && pSeg ){
2999 rc = fts3SegReaderCursorAppend(pCsr, pSeg);
3000 }
3001 }
3002
3003 if( iLevel!=FTS3_SEGCURSOR_PENDING ){
3004 if( rc==SQLITE_OK ){
3005 rc = sqlite3Fts3AllSegdirs(p, iLangid, iIndex, iLevel, &pStmt);
3006 }
3007
3008 while( rc==SQLITE_OK && SQLITE_ROW==(rc = sqlite3_step(pStmt)) ){
3009 Fts3SegReader *pSeg = 0;
3010
3011 /* Read the values returned by the SELECT into local variables. */
3012 sqlite3_int64 iStartBlock = sqlite3_column_int64(pStmt, 1);
3013 sqlite3_int64 iLeavesEndBlock = sqlite3_column_int64(pStmt, 2);
3014 sqlite3_int64 iEndBlock = sqlite3_column_int64(pStmt, 3);
3015 int nRoot = sqlite3_column_bytes(pStmt, 4);
3016 char const *zRoot = sqlite3_column_blob(pStmt, 4);
3017
3018 /* If zTerm is not NULL, and this segment is not stored entirely on its
3019 ** root node, the range of leaves scanned can be reduced. Do this. */
3020 if( iStartBlock && zTerm && zRoot ){
3021 sqlite3_int64 *pi = (isPrefix ? &iLeavesEndBlock : 0);
3022 rc = fts3SelectLeaf(p, zTerm, nTerm, zRoot, nRoot, &iStartBlock, pi);
3023 if( rc!=SQLITE_OK ) goto finished;
3024 if( isPrefix==0 && isScan==0 ) iLeavesEndBlock = iStartBlock;
3025 }
3026
3027 rc = sqlite3Fts3SegReaderNew(pCsr->nSegment+1,
3028 (isPrefix==0 && isScan==0),
3029 iStartBlock, iLeavesEndBlock,
3030 iEndBlock, zRoot, nRoot, &pSeg
3031 );
3032 if( rc!=SQLITE_OK ) goto finished;
3033 rc = fts3SegReaderCursorAppend(pCsr, pSeg);
3034 }
3035 }
3036
3037 finished:
3038 rc2 = sqlite3_reset(pStmt);
3039 if( rc==SQLITE_DONE ) rc = rc2;
3040
3041 return rc;
3042 }
3043
3044 /*
3045 ** Set up a cursor object for iterating through a full-text index or a
3046 ** single level therein.
3047 */
3048 int sqlite3Fts3SegReaderCursor(
3049 Fts3Table *p, /* FTS3 table handle */
3050 int iLangid, /* Language-id to search */
3051 int iIndex, /* Index to search (from 0 to p->nIndex-1) */
3052 int iLevel, /* Level of segments to scan */
3053 const char *zTerm, /* Term to query for */
3054 int nTerm, /* Size of zTerm in bytes */
3055 int isPrefix, /* True for a prefix search */
3056 int isScan, /* True to scan from zTerm to EOF */
3057 Fts3MultiSegReader *pCsr /* Cursor object to populate */
3058 ){
3059 assert( iIndex>=0 && iIndex<p->nIndex );
3060 assert( iLevel==FTS3_SEGCURSOR_ALL
3061 || iLevel==FTS3_SEGCURSOR_PENDING
3062 || iLevel>=0
3063 );
3064 assert( iLevel<FTS3_SEGDIR_MAXLEVEL );
3065 assert( FTS3_SEGCURSOR_ALL<0 && FTS3_SEGCURSOR_PENDING<0 );
3066 assert( isPrefix==0 || isScan==0 );
3067
3068 memset(pCsr, 0, sizeof(Fts3MultiSegReader));
3069 return fts3SegReaderCursor(
3070 p, iLangid, iIndex, iLevel, zTerm, nTerm, isPrefix, isScan, pCsr
3071 );
3072 }
3073
3074 /*
3075 ** In addition to its current configuration, have the Fts3MultiSegReader
3076 ** passed as the 4th argument also scan the doclist for term zTerm/nTerm.
3077 **
3078 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.
3079 */
3080 static int fts3SegReaderCursorAddZero(
3081 Fts3Table *p, /* FTS virtual table handle */
3082 int iLangid,
3083 const char *zTerm, /* Term to scan doclist of */
3084 int nTerm, /* Number of bytes in zTerm */
3085 Fts3MultiSegReader *pCsr /* Fts3MultiSegReader to modify */
3086 ){
3087 return fts3SegReaderCursor(p,
3088 iLangid, 0, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 0, 0,pCsr
3089 );
3090 }
3091
3092 /*
3093 ** Open an Fts3MultiSegReader to scan the doclist for term zTerm/nTerm. Or,
3094 ** if isPrefix is true, to scan the doclist for all terms for which
3095 ** zTerm/nTerm is a prefix. If successful, return SQLITE_OK and write
3096 ** a pointer to the new Fts3MultiSegReader to *ppSegcsr. Otherwise, return
3097 ** an SQLite error code.
3098 **
3099 ** It is the responsibility of the caller to free this object by eventually
3100 ** passing it to fts3SegReaderCursorFree()
3101 **
3102 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.
3103 ** Output parameter *ppSegcsr is set to 0 if an error occurs.
3104 */
3105 static int fts3TermSegReaderCursor(
3106 Fts3Cursor *pCsr, /* Virtual table cursor handle */
3107 const char *zTerm, /* Term to query for */
3108 int nTerm, /* Size of zTerm in bytes */
3109 int isPrefix, /* True for a prefix search */
3110 Fts3MultiSegReader **ppSegcsr /* OUT: Allocated seg-reader cursor */
3111 ){
3112 Fts3MultiSegReader *pSegcsr; /* Object to allocate and return */
3113 int rc = SQLITE_NOMEM; /* Return code */
3114
3115 pSegcsr = sqlite3_malloc(sizeof(Fts3MultiSegReader));
3116 if( pSegcsr ){
3117 int i;
3118 int bFound = 0; /* True once an index has been found */
3119 Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
3120
3121 if( isPrefix ){
3122 for(i=1; bFound==0 && i<p->nIndex; i++){
3123 if( p->aIndex[i].nPrefix==nTerm ){
3124 bFound = 1;
3125 rc = sqlite3Fts3SegReaderCursor(p, pCsr->iLangid,
3126 i, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 0, 0, pSegcsr
3127 );
3128 pSegcsr->bLookup = 1;
3129 }
3130 }
3131
3132 for(i=1; bFound==0 && i<p->nIndex; i++){
3133 if( p->aIndex[i].nPrefix==nTerm+1 ){
3134 bFound = 1;
3135 rc = sqlite3Fts3SegReaderCursor(p, pCsr->iLangid,
3136 i, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 1, 0, pSegcsr
3137 );
3138 if( rc==SQLITE_OK ){
3139 rc = fts3SegReaderCursorAddZero(
3140 p, pCsr->iLangid, zTerm, nTerm, pSegcsr
3141 );
3142 }
3143 }
3144 }
3145 }
3146
3147 if( bFound==0 ){
3148 rc = sqlite3Fts3SegReaderCursor(p, pCsr->iLangid,
3149 0, FTS3_SEGCURSOR_ALL, zTerm, nTerm, isPrefix, 0, pSegcsr
3150 );
3151 pSegcsr->bLookup = !isPrefix;
3152 }
3153 }
3154
3155 *ppSegcsr = pSegcsr;
3156 return rc;
3157 }
3158
3159 /*
3160 ** Free an Fts3MultiSegReader allocated by fts3TermSegReaderCursor().
3161 */
3162 static void fts3SegReaderCursorFree(Fts3MultiSegReader *pSegcsr){
3163 sqlite3Fts3SegReaderFinish(pSegcsr);
3164 sqlite3_free(pSegcsr);
3165 }
3166
3167 /*
3168 ** This function retrieves the doclist for the specified term (or term
3169 ** prefix) from the database.
3170 */
3171 static int fts3TermSelect(
3172 Fts3Table *p, /* Virtual table handle */
3173 Fts3PhraseToken *pTok, /* Token to query for */
3174 int iColumn, /* Column to query (or -ve for all columns) */
3175 int *pnOut, /* OUT: Size of buffer at *ppOut */
3176 char **ppOut /* OUT: Malloced result buffer */
3177 ){
3178 int rc; /* Return code */
3179 Fts3MultiSegReader *pSegcsr; /* Seg-reader cursor for this term */
3180 TermSelect tsc; /* Object for pair-wise doclist merging */
3181 Fts3SegFilter filter; /* Segment term filter configuration */
3182
3183 pSegcsr = pTok->pSegcsr;
3184 memset(&tsc, 0, sizeof(TermSelect));
3185
3186 filter.flags = FTS3_SEGMENT_IGNORE_EMPTY | FTS3_SEGMENT_REQUIRE_POS
3187 | (pTok->isPrefix ? FTS3_SEGMENT_PREFIX : 0)
3188 | (pTok->bFirst ? FTS3_SEGMENT_FIRST : 0)
3189 | (iColumn<p->nColumn ? FTS3_SEGMENT_COLUMN_FILTER : 0);
3190 filter.iCol = iColumn;
3191 filter.zTerm = pTok->z;
3192 filter.nTerm = pTok->n;
3193
3194 rc = sqlite3Fts3SegReaderStart(p, pSegcsr, &filter);
3195 while( SQLITE_OK==rc
3196 && SQLITE_ROW==(rc = sqlite3Fts3SegReaderStep(p, pSegcsr))
3197 ){
3198 rc = fts3TermSelectMerge(p, &tsc, pSegcsr->aDoclist, pSegcsr->nDoclist);
3199 }
3200
3201 if( rc==SQLITE_OK ){
3202 rc = fts3TermSelectFinishMerge(p, &tsc);
3203 }
3204 if( rc==SQLITE_OK ){
3205 *ppOut = tsc.aaOutput[0];
3206 *pnOut = tsc.anOutput[0];
3207 }else{
3208 int i;
3209 for(i=0; i<SizeofArray(tsc.aaOutput); i++){
3210 sqlite3_free(tsc.aaOutput[i]);
3211 }
3212 }
3213
3214 fts3SegReaderCursorFree(pSegcsr);
3215 pTok->pSegcsr = 0;
3216 return rc;
3217 }
3218
3219 /*
3220 ** This function counts the total number of docids in the doclist stored
3221 ** in buffer aList[], size nList bytes.
3222 **
3223 ** If the isPoslist argument is true, then it is assumed that the doclist
3224 ** contains a position-list following each docid. Otherwise, it is assumed
3225 ** that the doclist is simply a list of docids stored as delta encoded
3226 ** varints.
3227 */
3228 static int fts3DoclistCountDocids(char *aList, int nList){
3229 int nDoc = 0; /* Return value */
3230 if( aList ){
3231 char *aEnd = &aList[nList]; /* Pointer to one byte after EOF */
3232 char *p = aList; /* Cursor */
3233 while( p<aEnd ){
3234 nDoc++;
3235 while( (*p++)&0x80 ); /* Skip docid varint */
3236 fts3PoslistCopy(0, &p); /* Skip over position list */
3237 }
3238 }
3239
3240 return nDoc;
3241 }
3242
3243 /*
3244 ** Advance the cursor to the next row in the %_content table that
3245 ** matches the search criteria. For a MATCH search, this will be
3246 ** the next row that matches. For a full-table scan, this will be
3247 ** simply the next row in the %_content table. For a docid lookup,
3248 ** this routine simply sets the EOF flag.
3249 **
3250 ** Return SQLITE_OK if nothing goes wrong. SQLITE_OK is returned
3251 ** even if we reach end-of-file. The fts3EofMethod() will be called
3252 ** subsequently to determine whether or not an EOF was hit.
3253 */
3254 static int fts3NextMethod(sqlite3_vtab_cursor *pCursor){
3255 int rc;
3256 Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;
3257 if( pCsr->eSearch==FTS3_DOCID_SEARCH || pCsr->eSearch==FTS3_FULLSCAN_SEARCH ){
3258 Fts3Table *pTab = (Fts3Table*)pCursor->pVtab;
3259 pTab->bLock++;
3260 if( SQLITE_ROW!=sqlite3_step(pCsr->pStmt) ){
3261 pCsr->isEof = 1;
3262 rc = sqlite3_reset(pCsr->pStmt);
3263 }else{
3264 pCsr->iPrevId = sqlite3_column_int64(pCsr->pStmt, 0);
3265 rc = SQLITE_OK;
3266 }
3267 pTab->bLock--;
3268 }else{
3269 rc = fts3EvalNext((Fts3Cursor *)pCursor);
3270 }
3271 assert( ((Fts3Table *)pCsr->base.pVtab)->pSegments==0 );
3272 return rc;
3273 }
3274
3275 /*
3276 ** If the numeric type of argument pVal is "integer", then return it
3277 ** converted to a 64-bit signed integer. Otherwise, return a copy of
3278 ** the second parameter, iDefault.
3279 */
3280 static sqlite3_int64 fts3DocidRange(sqlite3_value *pVal, i64 iDefault){
3281 if( pVal ){
3282 int eType = sqlite3_value_numeric_type(pVal);
3283 if( eType==SQLITE_INTEGER ){
3284 return sqlite3_value_int64(pVal);
3285 }
3286 }
3287 return iDefault;
3288 }
3289
3290 /*
3291 ** This is the xFilter interface for the virtual table. See
3292 ** the virtual table xFilter method documentation for additional
3293 ** information.
3294 **
3295 ** If idxNum==FTS3_FULLSCAN_SEARCH then do a full table scan against
3296 ** the %_content table.
3297 **
3298 ** If idxNum==FTS3_DOCID_SEARCH then do a docid lookup for a single entry
3299 ** in the %_content table.
3300 **
3301 ** If idxNum>=FTS3_FULLTEXT_SEARCH then use the full text index. The
3302 ** column on the left-hand side of the MATCH operator is column
3303 ** number idxNum-FTS3_FULLTEXT_SEARCH, 0 indexed. argv[0] is the right-hand
3304 ** side of the MATCH operator.
3305 */
3306 static int fts3FilterMethod(
3307 sqlite3_vtab_cursor *pCursor, /* The cursor used for this query */
3308 int idxNum, /* Strategy index */
3309 const char *idxStr, /* Unused */
3310 int nVal, /* Number of elements in apVal */
3311 sqlite3_value **apVal /* Arguments for the indexing scheme */
3312 ){
3313 int rc = SQLITE_OK;
3314 char *zSql; /* SQL statement used to access %_content */
3315 int eSearch;
3316 Fts3Table *p = (Fts3Table *)pCursor->pVtab;
3317 Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;
3318
3319 sqlite3_value *pCons = 0; /* The MATCH or rowid constraint, if any */
3320 sqlite3_value *pLangid = 0; /* The "langid = ?" constraint, if any */
3321 sqlite3_value *pDocidGe = 0; /* The "docid >= ?" constraint, if any */
3322 sqlite3_value *pDocidLe = 0; /* The "docid <= ?" constraint, if any */
3323 int iIdx;
3324
3325 UNUSED_PARAMETER(idxStr);
3326 UNUSED_PARAMETER(nVal);
3327
3328 if( p->bLock ){
3329 return SQLITE_ERROR;
3330 }
3331
3332 eSearch = (idxNum & 0x0000FFFF);
3333 assert( eSearch>=0 && eSearch<=(FTS3_FULLTEXT_SEARCH+p->nColumn) );
3334 assert( p->pSegments==0 );
3335
3336 /* Collect arguments into local variables */
3337 iIdx = 0;
3338 if( eSearch!=FTS3_FULLSCAN_SEARCH ) pCons = apVal[iIdx++];
3339 if( idxNum & FTS3_HAVE_LANGID ) pLangid = apVal[iIdx++];
3340 if( idxNum & FTS3_HAVE_DOCID_GE ) pDocidGe = apVal[iIdx++];
3341 if( idxNum & FTS3_HAVE_DOCID_LE ) pDocidLe = apVal[iIdx++];
3342 assert( iIdx==nVal );
3343
3344 /* In case the cursor has been used before, clear it now. */
3345 fts3ClearCursor(pCsr);
3346
3347 /* Set the lower and upper bounds on docids to return */
3348 pCsr->iMinDocid = fts3DocidRange(pDocidGe, SMALLEST_INT64);
3349 pCsr->iMaxDocid = fts3DocidRange(pDocidLe, LARGEST_INT64);
3350
3351 if( idxStr ){
3352 pCsr->bDesc = (idxStr[0]=='D');
3353 }else{
3354 pCsr->bDesc = p->bDescIdx;
3355 }
3356 pCsr->eSearch = (i16)eSearch;
3357
3358 if( eSearch!=FTS3_DOCID_SEARCH && eSearch!=FTS3_FULLSCAN_SEARCH ){
3359 int iCol = eSearch-FTS3_FULLTEXT_SEARCH;
3360 const char *zQuery = (const char *)sqlite3_value_text(pCons);
3361
3362 if( zQuery==0 && sqlite3_value_type(pCons)!=SQLITE_NULL ){
3363 return SQLITE_NOMEM;
3364 }
3365
3366 pCsr->iLangid = 0;
3367 if( pLangid ) pCsr->iLangid = sqlite3_value_int(pLangid);
3368
3369 assert( p->base.zErrMsg==0 );
3370 rc = sqlite3Fts3ExprParse(p->pTokenizer, pCsr->iLangid,
3371 p->azColumn, p->bFts4, p->nColumn, iCol, zQuery, -1, &pCsr->pExpr,
3372 &p->base.zErrMsg
3373 );
3374 if( rc!=SQLITE_OK ){
3375 return rc;
3376 }
3377
3378 rc = fts3EvalStart(pCsr);
3379 sqlite3Fts3SegmentsClose(p);
3380 if( rc!=SQLITE_OK ) return rc;
3381 pCsr->pNextId = pCsr->aDoclist;
3382 pCsr->iPrevId = 0;
3383 }
3384
3385 /* Compile a SELECT statement for this cursor. For a full-table-scan, the
3386 ** statement loops through all rows of the %_content table. For a
3387 ** full-text query or docid lookup, the statement retrieves a single
3388 ** row by docid.
3389 */
3390 if( eSearch==FTS3_FULLSCAN_SEARCH ){
3391 if( pDocidGe || pDocidLe ){
3392 zSql = sqlite3_mprintf(
3393 "SELECT %s WHERE rowid BETWEEN %lld AND %lld ORDER BY rowid %s",
3394 p->zReadExprlist, pCsr->iMinDocid, pCsr->iMaxDocid,
3395 (pCsr->bDesc ? "DESC" : "ASC")
3396 );
3397 }else{
3398 zSql = sqlite3_mprintf("SELECT %s ORDER BY rowid %s",
3399 p->zReadExprlist, (pCsr->bDesc ? "DESC" : "ASC")
3400 );
3401 }
3402 if( zSql ){
3403 p->bLock++;
3404 rc = sqlite3Fts3PrepareStmt(p, zSql, 1, 1, &pCsr->pStmt);
3405 p->bLock--;
3406 sqlite3_free(zSql);
3407 }else{
3408 rc = SQLITE_NOMEM;
3409 }
3410 }else if( eSearch==FTS3_DOCID_SEARCH ){
3411 rc = fts3CursorSeekStmt(pCsr);
3412 if( rc==SQLITE_OK ){
3413 rc = sqlite3_bind_value(pCsr->pStmt, 1, pCons);
3414 }
3415 }
3416 if( rc!=SQLITE_OK ) return rc;
3417
3418 return fts3NextMethod(pCursor);
3419 }
3420
3421 /*
3422 ** This is the xEof method of the virtual table. SQLite calls this
3423 ** routine to find out if it has reached the end of a result set.
3424 */
3425 static int fts3EofMethod(sqlite3_vtab_cursor *pCursor){
3426 Fts3Cursor *pCsr = (Fts3Cursor*)pCursor;
3427 if( pCsr->isEof ){
3428 fts3ClearCursor(pCsr);
3429 pCsr->isEof = 1;
3430 }
3431 return pCsr->isEof;
3432 }
3433
3434 /*
3435 ** This is the xRowid method. The SQLite core calls this routine to
3436 ** retrieve the rowid for the current row of the result set. fts3
3437 ** exposes %_content.docid as the rowid for the virtual table. The
3438 ** rowid should be written to *pRowid.
3439 */
3440 static int fts3RowidMethod(sqlite3_vtab_cursor *pCursor, sqlite_int64 *pRowid){
3441 Fts3Cursor *pCsr = (Fts3Cursor *) pCursor;
3442 *pRowid = pCsr->iPrevId;
3443 return SQLITE_OK;
3444 }
3445
3446 /*
3447 ** This is the xColumn method, called by SQLite to request a value from
3448 ** the row that the supplied cursor currently points to.
3449 **
3450 ** If:
3451 **
3452 ** (iCol < p->nColumn) -> The value of the iCol'th user column.
3453 ** (iCol == p->nColumn) -> Magic column with the same name as the table.
3454 ** (iCol == p->nColumn+1) -> Docid column
3455 ** (iCol == p->nColumn+2) -> Langid column
3456 */
3457 static int fts3ColumnMethod(
3458 sqlite3_vtab_cursor *pCursor, /* Cursor to retrieve value from */
3459 sqlite3_context *pCtx, /* Context for sqlite3_result_xxx() calls */
3460 int iCol /* Index of column to read value from */
3461 ){
3462 int rc = SQLITE_OK; /* Return Code */
3463 Fts3Cursor *pCsr = (Fts3Cursor *) pCursor;
3464 Fts3Table *p = (Fts3Table *)pCursor->pVtab;
3465
3466 /* The column value supplied by SQLite must be in range. */
3467 assert( iCol>=0 && iCol<=p->nColumn+2 );
3468
3469 switch( iCol-p->nColumn ){
3470 case 0:
3471 /* The special 'table-name' column */
3472 sqlite3_result_pointer(pCtx, pCsr, "fts3cursor", 0);
3473 break;
3474
3475 case 1:
3476 /* The docid column */
3477 sqlite3_result_int64(pCtx, pCsr->iPrevId);
3478 break;
3479
3480 case 2:
3481 if( pCsr->pExpr ){
3482 sqlite3_result_int64(pCtx, pCsr->iLangid);
3483 break;
3484 }else if( p->zLanguageid==0 ){
3485 sqlite3_result_int(pCtx, 0);
3486 break;
3487 }else{
3488 iCol = p->nColumn;
3489 /* no break */ deliberate_fall_through
3490 }
3491
3492 default:
3493 /* A user column. Or, if this is a full-table scan, possibly the
3494 ** language-id column. Seek the cursor. */
3495 rc = fts3CursorSeek(0, pCsr);
3496 if( rc==SQLITE_OK && sqlite3_data_count(pCsr->pStmt)-1>iCol ){
3497 sqlite3_result_value(pCtx, sqlite3_column_value(pCsr->pStmt, iCol+1));
3498 }
3499 break;
3500 }
3501
3502 assert( ((Fts3Table *)pCsr->base.pVtab)->pSegments==0 );
3503 return rc;
3504 }
3505
3506 /*
3507 ** This function is the implementation of the xUpdate callback used by
3508 ** FTS3 virtual tables. It is invoked by SQLite each time a row is to be
3509 ** inserted, updated or deleted.
3510 */
3511 static int fts3UpdateMethod(
3512 sqlite3_vtab *pVtab, /* Virtual table handle */
3513 int nArg, /* Size of argument array */
3514 sqlite3_value **apVal, /* Array of arguments */
3515 sqlite_int64 *pRowid /* OUT: The affected (or effected) rowid */
3516 ){
3517 return sqlite3Fts3UpdateMethod(pVtab, nArg, apVal, pRowid);
3518 }
3519
3520 /*
3521 ** Implementation of xSync() method. Flush the contents of the pending-terms
3522 ** hash-table to the database.
3523 */
3524 static int fts3SyncMethod(sqlite3_vtab *pVtab){
3525
3526 /* Following an incremental-merge operation, assuming that the input
3527 ** segments are not completely consumed (the usual case), they are updated
3528 ** in place to remove the entries that have already been merged. This
3529 ** involves updating the leaf block that contains the smallest unmerged
3530 ** entry and each block (if any) between the leaf and the root node. So
3531 ** if the height of the input segment b-trees is N, and input segments
3532 ** are merged eight at a time, updating the input segments at the end
3533 ** of an incremental-merge requires writing (8*(1+N)) blocks. N is usually
3534 ** small - often between 0 and 2. So the overhead of the incremental
3535 ** merge is somewhere between 8 and 24 blocks. To avoid this overhead
3536 ** dwarfing the actual productive work accomplished, the incremental merge
3537 ** is only attempted if it will write at least 64 leaf blocks. Hence
3538 ** nMinMerge.
3539 **
3540 ** Of course, updating the input segments also involves deleting a bunch
3541 ** of blocks from the segments table. But this is not considered overhead
3542 ** as it would also be required by a crisis-merge that used the same input
3543 ** segments.
3544 */
3545 const u32 nMinMerge = 64; /* Minimum amount of incr-merge work to do */
3546
3547 Fts3Table *p = (Fts3Table*)pVtab;
3548 int rc;
3549 i64 iLastRowid = sqlite3_last_insert_rowid(p->db);
3550
3551 rc = sqlite3Fts3PendingTermsFlush(p);
3552 if( rc==SQLITE_OK
3553 && p->nLeafAdd>(nMinMerge/16)
3554 && p->nAutoincrmerge && p->nAutoincrmerge!=0xff
3555 ){
3556 int mxLevel = 0; /* Maximum relative level value in db */
3557 int A; /* Incr-merge parameter A */
3558
3559 rc = sqlite3Fts3MaxLevel(p, &mxLevel);
3560 assert( rc==SQLITE_OK || mxLevel==0 );
3561 A = p->nLeafAdd * mxLevel;
3562 A += (A/2);
3563 if( A>(int)nMinMerge ) rc = sqlite3Fts3Incrmerge(p, A, p->nAutoincrmerge);
3564 }
3565 sqlite3Fts3SegmentsClose(p);
3566 sqlite3_set_last_insert_rowid(p->db, iLastRowid);
3567 return rc;
3568 }
3569
3570 /*
3571 ** If it is currently unknown whether or not the FTS table has an %_stat
3572 ** table (if p->bHasStat==2), attempt to determine this (set p->bHasStat
3573 ** to 0 or 1). Return SQLITE_OK if successful, or an SQLite error code
3574 ** if an error occurs.
3575 */
3576 static int fts3SetHasStat(Fts3Table *p){
3577 int rc = SQLITE_OK;
3578 if( p->bHasStat==2 ){
3579 char *zTbl = sqlite3_mprintf("%s_stat", p->zName);
3580 if( zTbl ){
3581 int res = sqlite3_table_column_metadata(p->db, p->zDb, zTbl, 0,0,0,0,0,0);
3582 sqlite3_free(zTbl);
3583 p->bHasStat = (res==SQLITE_OK);
3584 }else{
3585 rc = SQLITE_NOMEM;
3586 }
3587 }
3588 return rc;
3589 }
3590
3591 /*
3592 ** Implementation of xBegin() method.
3593 */
3594 static int fts3BeginMethod(sqlite3_vtab *pVtab){
3595 Fts3Table *p = (Fts3Table*)pVtab;
3596 int rc;
3597 UNUSED_PARAMETER(pVtab);
3598 assert( p->pSegments==0 );
3599 assert( p->nPendingData==0 );
3600 assert( p->inTransaction!=1 );
3601 p->nLeafAdd = 0;
3602 rc = fts3SetHasStat(p);
3603 #ifdef SQLITE_DEBUG
3604 if( rc==SQLITE_OK ){
3605 p->inTransaction = 1;
3606 p->mxSavepoint = -1;
3607 }
3608 #endif
3609 return rc;
3610 }
3611
3612 /*
3613 ** Implementation of xCommit() method. This is a no-op. The contents of
3614 ** the pending-terms hash-table have already been flushed into the database
3615 ** by fts3SyncMethod().
3616 */
3617 static int fts3CommitMethod(sqlite3_vtab *pVtab){
3618 TESTONLY( Fts3Table *p = (Fts3Table*)pVtab );
3619 UNUSED_PARAMETER(pVtab);
3620 assert( p->nPendingData==0 );
3621 assert( p->inTransaction!=0 );
3622 assert( p->pSegments==0 );
3623 TESTONLY( p->inTransaction = 0 );
3624 TESTONLY( p->mxSavepoint = -1; );
3625 return SQLITE_OK;
3626 }
3627
3628 /*
3629 ** Implementation of xRollback(). Discard the contents of the pending-terms
3630 ** hash-table. Any changes made to the database are reverted by SQLite.
3631 */
3632 static int fts3RollbackMethod(sqlite3_vtab *pVtab){
3633 Fts3Table *p = (Fts3Table*)pVtab;
3634 sqlite3Fts3PendingTermsClear(p);
3635 assert( p->inTransaction!=0 );
3636 TESTONLY( p->inTransaction = 0 );
3637 TESTONLY( p->mxSavepoint = -1; );
3638 return SQLITE_OK;
3639 }
3640
3641 /*
3642 ** When called, *ppPoslist must point to the byte immediately following the
3643 ** end of a position-list. i.e. ( (*ppPoslist)[-1]==POS_END ). This function
3644 ** moves *ppPoslist so that it instead points to the first byte of the
3645 ** same position list.
3646 */
3647 static void fts3ReversePoslist(char *pStart, char **ppPoslist){
3648 char *p = &(*ppPoslist)[-2];
3649 char c = 0;
3650
3651 /* Skip backwards passed any trailing 0x00 bytes added by NearTrim() */
3652 while( p>pStart && (c=*p--)==0 );
3653
3654 /* Search backwards for a varint with value zero (the end of the previous
3655 ** poslist). This is an 0x00 byte preceded by some byte that does not
3656 ** have the 0x80 bit set. */
3657 while( p>pStart && (*p & 0x80) | c ){
3658 c = *p--;
3659 }
3660 assert( p==pStart || c==0 );
3661
3662 /* At this point p points to that preceding byte without the 0x80 bit
3663 ** set. So to find the start of the poslist, skip forward 2 bytes then
3664 ** over a varint.
3665 **
3666 ** Normally. The other case is that p==pStart and the poslist to return
3667 ** is the first in the doclist. In this case do not skip forward 2 bytes.
3668 ** The second part of the if condition (c==0 && *ppPoslist>&p[2])
3669 ** is required for cases where the first byte of a doclist and the
3670 ** doclist is empty. For example, if the first docid is 10, a doclist
3671 ** that begins with:
3672 **
3673 ** 0x0A 0x00 <next docid delta varint>
3674 */
3675 if( p>pStart || (c==0 && *ppPoslist>&p[2]) ){ p = &p[2]; }
3676 while( *p++&0x80 );
3677 *ppPoslist = p;
3678 }
3679
3680 /*
3681 ** Helper function used by the implementation of the overloaded snippet(),
3682 ** offsets() and optimize() SQL functions.
3683 **
3684 ** If the value passed as the third argument is a blob of size
3685 ** sizeof(Fts3Cursor*), then the blob contents are copied to the
3686 ** output variable *ppCsr and SQLITE_OK is returned. Otherwise, an error
3687 ** message is written to context pContext and SQLITE_ERROR returned. The
3688 ** string passed via zFunc is used as part of the error message.
3689 */
3690 static int fts3FunctionArg(
3691 sqlite3_context *pContext, /* SQL function call context */
3692 const char *zFunc, /* Function name */
3693 sqlite3_value *pVal, /* argv[0] passed to function */
3694 Fts3Cursor **ppCsr /* OUT: Store cursor handle here */
3695 ){
3696 int rc;
3697 *ppCsr = (Fts3Cursor*)sqlite3_value_pointer(pVal, "fts3cursor");
3698 if( (*ppCsr)!=0 ){
3699 rc = SQLITE_OK;
3700 }else{
3701 char *zErr = sqlite3_mprintf("illegal first argument to %s", zFunc);
3702 sqlite3_result_error(pContext, zErr, -1);
3703 sqlite3_free(zErr);
3704 rc = SQLITE_ERROR;
3705 }
3706 return rc;
3707 }
3708
3709 /*
3710 ** Implementation of the snippet() function for FTS3
3711 */
3712 static void fts3SnippetFunc(
3713 sqlite3_context *pContext, /* SQLite function call context */
3714 int nVal, /* Size of apVal[] array */
3715 sqlite3_value **apVal /* Array of arguments */
3716 ){
3717 Fts3Cursor *pCsr; /* Cursor handle passed through apVal[0] */
3718 const char *zStart = "<b>";
3719 const char *zEnd = "</b>";
3720 const char *zEllipsis = "<b>...</b>";
3721 int iCol = -1;
3722 int nToken = 15; /* Default number of tokens in snippet */
3723
3724 /* There must be at least one argument passed to this function (otherwise
3725 ** the non-overloaded version would have been called instead of this one).
3726 */
3727 assert( nVal>=1 );
3728
3729 if( nVal>6 ){
3730 sqlite3_result_error(pContext,
3731 "wrong number of arguments to function snippet()", -1);
3732 return;
3733 }
3734 if( fts3FunctionArg(pContext, "snippet", apVal[0], &pCsr) ) return;
3735
3736 switch( nVal ){
3737 case 6: nToken = sqlite3_value_int(apVal[5]);
3738 /* no break */ deliberate_fall_through
3739 case 5: iCol = sqlite3_value_int(apVal[4]);
3740 /* no break */ deliberate_fall_through
3741 case 4: zEllipsis = (const char*)sqlite3_value_text(apVal[3]);
3742 /* no break */ deliberate_fall_through
3743 case 3: zEnd = (const char*)sqlite3_value_text(apVal[2]);
3744 /* no break */ deliberate_fall_through
3745 case 2: zStart = (const char*)sqlite3_value_text(apVal[1]);
3746 }
3747 if( !zEllipsis || !zEnd || !zStart ){
3748 sqlite3_result_error_nomem(pContext);
3749 }else if( nToken==0 ){
3750 sqlite3_result_text(pContext, "", -1, SQLITE_STATIC);
3751 }else if( SQLITE_OK==fts3CursorSeek(pContext, pCsr) ){
3752 sqlite3Fts3Snippet(pContext, pCsr, zStart, zEnd, zEllipsis, iCol, nToken);
3753 }
3754 }
3755
3756 /*
3757 ** Implementation of the offsets() function for FTS3
3758 */
3759 static void fts3OffsetsFunc(
3760 sqlite3_context *pContext, /* SQLite function call context */
3761 int nVal, /* Size of argument array */
3762 sqlite3_value **apVal /* Array of arguments */
3763 ){
3764 Fts3Cursor *pCsr; /* Cursor handle passed through apVal[0] */
3765
3766 UNUSED_PARAMETER(nVal);
3767
3768 assert( nVal==1 );
3769 if( fts3FunctionArg(pContext, "offsets", apVal[0], &pCsr) ) return;
3770 assert( pCsr );
3771 if( SQLITE_OK==fts3CursorSeek(pContext, pCsr) ){
3772 sqlite3Fts3Offsets(pContext, pCsr);
3773 }
3774 }
3775
3776 /*
3777 ** Implementation of the special optimize() function for FTS3. This
3778 ** function merges all segments in the database to a single segment.
3779 ** Example usage is:
3780 **
3781 ** SELECT optimize(t) FROM t LIMIT 1;
3782 **
3783 ** where 't' is the name of an FTS3 table.
3784 */
3785 static void fts3OptimizeFunc(
3786 sqlite3_context *pContext, /* SQLite function call context */
3787 int nVal, /* Size of argument array */
3788 sqlite3_value **apVal /* Array of arguments */
3789 ){
3790 int rc; /* Return code */
3791 Fts3Table *p; /* Virtual table handle */
3792 Fts3Cursor *pCursor; /* Cursor handle passed through apVal[0] */
3793
3794 UNUSED_PARAMETER(nVal);
3795
3796 assert( nVal==1 );
3797 if( fts3FunctionArg(pContext, "optimize", apVal[0], &pCursor) ) return;
3798 p = (Fts3Table *)pCursor->base.pVtab;
3799 assert( p );
3800
3801 rc = sqlite3Fts3Optimize(p);
3802
3803 switch( rc ){
3804 case SQLITE_OK:
3805 sqlite3_result_text(pContext, "Index optimized", -1, SQLITE_STATIC);
3806 break;
3807 case SQLITE_DONE:
3808 sqlite3_result_text(pContext, "Index already optimal", -1, SQLITE_STATIC);
3809 break;
3810 default:
3811 sqlite3_result_error_code(pContext, rc);
3812 break;
3813 }
3814 }
3815
3816 /*
3817 ** Implementation of the matchinfo() function for FTS3
3818 */
3819 static void fts3MatchinfoFunc(
3820 sqlite3_context *pContext, /* SQLite function call context */
3821 int nVal, /* Size of argument array */
3822 sqlite3_value **apVal /* Array of arguments */
3823 ){
3824 Fts3Cursor *pCsr; /* Cursor handle passed through apVal[0] */
3825 assert( nVal==1 || nVal==2 );
3826 if( SQLITE_OK==fts3FunctionArg(pContext, "matchinfo", apVal[0], &pCsr) ){
3827 const char *zArg = 0;
3828 if( nVal>1 ){
3829 zArg = (const char *)sqlite3_value_text(apVal[1]);
3830 }
3831 sqlite3Fts3Matchinfo(pContext, pCsr, zArg);
3832 }
3833 }
3834
3835 /*
3836 ** This routine implements the xFindFunction method for the FTS3
3837 ** virtual table.
3838 */
3839 static int fts3FindFunctionMethod(
3840 sqlite3_vtab *pVtab, /* Virtual table handle */
3841 int nArg, /* Number of SQL function arguments */
3842 const char *zName, /* Name of SQL function */
3843 void (**pxFunc)(sqlite3_context*,int,sqlite3_value**), /* OUT: Result */
3844 void **ppArg /* Unused */
3845 ){
3846 struct Overloaded {
3847 const char *zName;
3848 void (*xFunc)(sqlite3_context*,int,sqlite3_value**);
3849 } aOverload[] = {
3850 { "snippet", fts3SnippetFunc },
3851 { "offsets", fts3OffsetsFunc },
3852 { "optimize", fts3OptimizeFunc },
3853 { "matchinfo", fts3MatchinfoFunc },
3854 };
3855 int i; /* Iterator variable */
3856
3857 UNUSED_PARAMETER(pVtab);
3858 UNUSED_PARAMETER(nArg);
3859 UNUSED_PARAMETER(ppArg);
3860
3861 for(i=0; i<SizeofArray(aOverload); i++){
3862 if( strcmp(zName, aOverload[i].zName)==0 ){
3863 *pxFunc = aOverload[i].xFunc;
3864 return 1;
3865 }
3866 }
3867
3868 /* No function of the specified name was found. Return 0. */
3869 return 0;
3870 }
3871
3872 /*
3873 ** Implementation of FTS3 xRename method. Rename an fts3 table.
3874 */
3875 static int fts3RenameMethod(
3876 sqlite3_vtab *pVtab, /* Virtual table handle */
3877 const char *zName /* New name of table */
3878 ){
3879 Fts3Table *p = (Fts3Table *)pVtab;
3880 sqlite3 *db = p->db; /* Database connection */
3881 int rc; /* Return Code */
3882
3883 /* At this point it must be known if the %_stat table exists or not.
3884 ** So bHasStat may not be 2. */
3885 rc = fts3SetHasStat(p);
3886
3887 /* As it happens, the pending terms table is always empty here. This is
3888 ** because an "ALTER TABLE RENAME TABLE" statement inside a transaction
3889 ** always opens a savepoint transaction. And the xSavepoint() method
3890 ** flushes the pending terms table. But leave the (no-op) call to
3891 ** PendingTermsFlush() in in case that changes.
3892 */
3893 assert( p->nPendingData==0 );
3894 if( rc==SQLITE_OK ){
3895 rc = sqlite3Fts3PendingTermsFlush(p);
3896 }
3897
3898 p->bIgnoreSavepoint = 1;
3899
3900 if( p->zContentTbl==0 ){
3901 fts3DbExec(&rc, db,
3902 "ALTER TABLE %Q.'%q_content' RENAME TO '%q_content';",
3903 p->zDb, p->zName, zName
3904 );
3905 }
3906
3907 if( p->bHasDocsize ){
3908 fts3DbExec(&rc, db,
3909 "ALTER TABLE %Q.'%q_docsize' RENAME TO '%q_docsize';",
3910 p->zDb, p->zName, zName
3911 );
3912 }
3913 if( p->bHasStat ){
3914 fts3DbExec(&rc, db,
3915 "ALTER TABLE %Q.'%q_stat' RENAME TO '%q_stat';",
3916 p->zDb, p->zName, zName
3917 );
3918 }
3919 fts3DbExec(&rc, db,
3920 "ALTER TABLE %Q.'%q_segments' RENAME TO '%q_segments';",
3921 p->zDb, p->zName, zName
3922 );
3923 fts3DbExec(&rc, db,
3924 "ALTER TABLE %Q.'%q_segdir' RENAME TO '%q_segdir';",
3925 p->zDb, p->zName, zName
3926 );
3927
3928 p->bIgnoreSavepoint = 0;
3929 return rc;
3930 }
3931
3932 /*
3933 ** The xSavepoint() method.
3934 **
3935 ** Flush the contents of the pending-terms table to disk.
3936 */
3937 static int fts3SavepointMethod(sqlite3_vtab *pVtab, int iSavepoint){
3938 int rc = SQLITE_OK;
3939 Fts3Table *pTab = (Fts3Table*)pVtab;
3940 assert( pTab->inTransaction );
3941 assert( pTab->mxSavepoint<=iSavepoint );
3942 TESTONLY( pTab->mxSavepoint = iSavepoint );
3943
3944 if( pTab->bIgnoreSavepoint==0 ){
3945 if( fts3HashCount(&pTab->aIndex[0].hPending)>0 ){
3946 char *zSql = sqlite3_mprintf("INSERT INTO %Q.%Q(%Q) VALUES('flush')",
3947 pTab->zDb, pTab->zName, pTab->zName
3948 );
3949 if( zSql ){
3950 pTab->bIgnoreSavepoint = 1;
3951 rc = sqlite3_exec(pTab->db, zSql, 0, 0, 0);
3952 pTab->bIgnoreSavepoint = 0;
3953 sqlite3_free(zSql);
3954 }else{
3955 rc = SQLITE_NOMEM;
3956 }
3957 }
3958 if( rc==SQLITE_OK ){
3959 pTab->iSavepoint = iSavepoint+1;
3960 }
3961 }
3962 return rc;
3963 }
3964
3965 /*
3966 ** The xRelease() method.
3967 **
3968 ** This is a no-op.
3969 */
3970 static int fts3ReleaseMethod(sqlite3_vtab *pVtab, int iSavepoint){
3971 Fts3Table *pTab = (Fts3Table*)pVtab;
3972 assert( pTab->inTransaction );
3973 assert( pTab->mxSavepoint >= iSavepoint );
3974 TESTONLY( pTab->mxSavepoint = iSavepoint-1 );
3975 pTab->iSavepoint = iSavepoint;
3976 return SQLITE_OK;
3977 }
3978
3979 /*
3980 ** The xRollbackTo() method.
3981 **
3982 ** Discard the contents of the pending terms table.
3983 */
3984 static int fts3RollbackToMethod(sqlite3_vtab *pVtab, int iSavepoint){
3985 Fts3Table *pTab = (Fts3Table*)pVtab;
3986 UNUSED_PARAMETER(iSavepoint);
3987 assert( pTab->inTransaction );
3988 TESTONLY( pTab->mxSavepoint = iSavepoint );
3989 if( (iSavepoint+1)<=pTab->iSavepoint ){
3990 sqlite3Fts3PendingTermsClear(pTab);
3991 }
3992 return SQLITE_OK;
3993 }
3994
3995 /*
3996 ** Return true if zName is the extension on one of the shadow tables used
3997 ** by this module.
3998 */
3999 static int fts3ShadowName(const char *zName){
4000 static const char *azName[] = {
4001 "content", "docsize", "segdir", "segments", "stat",
4002 };
4003 unsigned int i;
4004 for(i=0; i<sizeof(azName)/sizeof(azName[0]); i++){
4005 if( sqlite3_stricmp(zName, azName[i])==0 ) return 1;
4006 }
4007 return 0;
4008 }
4009
4010 /*
4011 ** Implementation of the xIntegrity() method on the FTS3/FTS4 virtual
4012 ** table.
4013 */
4014 static int fts3IntegrityMethod(
4015 sqlite3_vtab *pVtab, /* The virtual table to be checked */
4016 const char *zSchema, /* Name of schema in which pVtab lives */
4017 const char *zTabname, /* Name of the pVTab table */
4018 int isQuick, /* True if this is a quick_check */
4019 char **pzErr /* Write error message here */
4020 ){
4021 Fts3Table *p = (Fts3Table*)pVtab;
4022 int rc = SQLITE_OK;
4023 int bOk = 0;
4024
4025 UNUSED_PARAMETER(isQuick);
4026 rc = sqlite3Fts3IntegrityCheck(p, &bOk);
4027 assert( pVtab->zErrMsg==0 || rc!=SQLITE_OK );
4028 assert( rc!=SQLITE_CORRUPT_VTAB );
4029 if( rc==SQLITE_ERROR || (rc&0xFF)==SQLITE_CORRUPT ){
4030 *pzErr = sqlite3_mprintf("unable to validate the inverted index for"
4031 " FTS%d table %s.%s: %s",
4032 p->bFts4 ? 4 : 3, zSchema, zTabname, sqlite3_errstr(rc));
4033 if( *pzErr ) rc = SQLITE_OK;
4034 }else if( rc==SQLITE_OK && bOk==0 ){
4035 *pzErr = sqlite3_mprintf("malformed inverted index for FTS%d table %s.%s",
4036 p->bFts4 ? 4 : 3, zSchema, zTabname);
4037 if( *pzErr==0 ) rc = SQLITE_NOMEM;
4038 }
4039 sqlite3Fts3SegmentsClose(p);
4040 return rc;
4041 }
4042
4043
4044
4045 static const sqlite3_module fts3Module = {
4046 /* iVersion */ 4,
4047 /* xCreate */ fts3CreateMethod,
4048 /* xConnect */ fts3ConnectMethod,
4049 /* xBestIndex */ fts3BestIndexMethod,
4050 /* xDisconnect */ fts3DisconnectMethod,
4051 /* xDestroy */ fts3DestroyMethod,
4052 /* xOpen */ fts3OpenMethod,
4053 /* xClose */ fts3CloseMethod,
4054 /* xFilter */ fts3FilterMethod,
4055 /* xNext */ fts3NextMethod,
4056 /* xEof */ fts3EofMethod,
4057 /* xColumn */ fts3ColumnMethod,
4058 /* xRowid */ fts3RowidMethod,
4059 /* xUpdate */ fts3UpdateMethod,
4060 /* xBegin */ fts3BeginMethod,
4061 /* xSync */ fts3SyncMethod,
4062 /* xCommit */ fts3CommitMethod,
4063 /* xRollback */ fts3RollbackMethod,
4064 /* xFindFunction */ fts3FindFunctionMethod,
4065 /* xRename */ fts3RenameMethod,
4066 /* xSavepoint */ fts3SavepointMethod,
4067 /* xRelease */ fts3ReleaseMethod,
4068 /* xRollbackTo */ fts3RollbackToMethod,
4069 /* xShadowName */ fts3ShadowName,
4070 /* xIntegrity */ fts3IntegrityMethod,
4071 };
4072
4073 /*
4074 ** This function is registered as the module destructor (called when an
4075 ** FTS3 enabled database connection is closed). It frees the memory
4076 ** allocated for the tokenizer hash table.
4077 */
4078 static void hashDestroy(void *p){
4079 Fts3HashWrapper *pHash = (Fts3HashWrapper *)p;
4080 pHash->nRef--;
4081 if( pHash->nRef<=0 ){
4082 sqlite3Fts3HashClear(&pHash->hash);
4083 sqlite3_free(pHash);
4084 }
4085 }
4086
4087 /*
4088 ** The fts3 built-in tokenizers - "simple", "porter" and "icu"- are
4089 ** implemented in files fts3_tokenizer1.c, fts3_porter.c and fts3_icu.c
4090 ** respectively. The following three forward declarations are for functions
4091 ** declared in these files used to retrieve the respective implementations.
4092 **
4093 ** Calling sqlite3Fts3SimpleTokenizerModule() sets the value pointed
4094 ** to by the argument to point to the "simple" tokenizer implementation.
4095 ** And so on.
4096 */
4097 void sqlite3Fts3SimpleTokenizerModule(sqlite3_tokenizer_module const**ppModule);
4098 void sqlite3Fts3PorterTokenizerModule(sqlite3_tokenizer_module const**ppModule);
4099 #ifndef SQLITE_DISABLE_FTS3_UNICODE
4100 void sqlite3Fts3UnicodeTokenizer(sqlite3_tokenizer_module const**ppModule);
4101 #endif
4102 #ifdef SQLITE_ENABLE_ICU
4103 void sqlite3Fts3IcuTokenizerModule(sqlite3_tokenizer_module const**ppModule);
4104 #endif
4105
4106 /*
4107 ** Initialize the fts3 extension. If this extension is built as part
4108 ** of the sqlite library, then this function is called directly by
4109 ** SQLite. If fts3 is built as a dynamically loadable extension, this
4110 ** function is called by the sqlite3_extension_init() entry point.
4111 */
4112 int sqlite3Fts3Init(sqlite3 *db){
4113 int rc = SQLITE_OK;
4114 Fts3HashWrapper *pHash = 0;
4115 const sqlite3_tokenizer_module *pSimple = 0;
4116 const sqlite3_tokenizer_module *pPorter = 0;
4117 #ifndef SQLITE_DISABLE_FTS3_UNICODE
4118 const sqlite3_tokenizer_module *pUnicode = 0;
4119 #endif
4120
4121 #ifdef SQLITE_ENABLE_ICU
4122 const sqlite3_tokenizer_module *pIcu = 0;
4123 sqlite3Fts3IcuTokenizerModule(&pIcu);
4124 #endif
4125
4126 #ifndef SQLITE_DISABLE_FTS3_UNICODE
4127 sqlite3Fts3UnicodeTokenizer(&pUnicode);
4128 #endif
4129
4130 #ifdef SQLITE_TEST
4131 rc = sqlite3Fts3InitTerm(db);
4132 if( rc!=SQLITE_OK ) return rc;
4133 #endif
4134
4135 rc = sqlite3Fts3InitAux(db);
4136 if( rc!=SQLITE_OK ) return rc;
4137
4138 sqlite3Fts3SimpleTokenizerModule(&pSimple);
4139 sqlite3Fts3PorterTokenizerModule(&pPorter);
4140
4141 /* Allocate and initialize the hash-table used to store tokenizers. */
4142 pHash = sqlite3_malloc(sizeof(Fts3HashWrapper));
4143 if( !pHash ){
4144 rc = SQLITE_NOMEM;
4145 }else{
4146 sqlite3Fts3HashInit(&pHash->hash, FTS3_HASH_STRING, 1);
4147 pHash->nRef = 0;
4148 }
4149
4150 /* Load the built-in tokenizers into the hash table */
4151 if( rc==SQLITE_OK ){
4152 if( sqlite3Fts3HashInsert(&pHash->hash, "simple", 7, (void *)pSimple)
4153 || sqlite3Fts3HashInsert(&pHash->hash, "porter", 7, (void *)pPorter)
4154
4155 #ifndef SQLITE_DISABLE_FTS3_UNICODE
4156 || sqlite3Fts3HashInsert(&pHash->hash, "unicode61", 10, (void *)pUnicode)
4157 #endif
4158 #ifdef SQLITE_ENABLE_ICU
4159 || (pIcu && sqlite3Fts3HashInsert(&pHash->hash, "icu", 4, (void *)pIcu))
4160 #endif
4161 ){
4162 rc = SQLITE_NOMEM;
4163 }
4164 }
4165
4166 #ifdef SQLITE_TEST
4167 if( rc==SQLITE_OK ){
4168 rc = sqlite3Fts3ExprInitTestInterface(db, &pHash->hash);
4169 }
4170 #endif
4171
4172 /* Create the virtual table wrapper around the hash-table and overload
4173 ** the four scalar functions. If this is successful, register the
4174 ** module with sqlite.
4175 */
4176 if( SQLITE_OK==rc
4177 && SQLITE_OK==(rc=sqlite3Fts3InitHashTable(db,&pHash->hash,"fts3_tokenizer"))
4178 && SQLITE_OK==(rc = sqlite3_overload_function(db, "snippet", -1))
4179 && SQLITE_OK==(rc = sqlite3_overload_function(db, "offsets", 1))
4180 && SQLITE_OK==(rc = sqlite3_overload_function(db, "matchinfo", 1))
4181 && SQLITE_OK==(rc = sqlite3_overload_function(db, "matchinfo", 2))
4182 && SQLITE_OK==(rc = sqlite3_overload_function(db, "optimize", 1))
4183 ){
4184 pHash->nRef++;
4185 rc = sqlite3_create_module_v2(
4186 db, "fts3", &fts3Module, (void *)pHash, hashDestroy
4187 );
4188 if( rc==SQLITE_OK ){
4189 pHash->nRef++;
4190 rc = sqlite3_create_module_v2(
4191 db, "fts4", &fts3Module, (void *)pHash, hashDestroy
4192 );
4193 }
4194 if( rc==SQLITE_OK ){
4195 pHash->nRef++;
4196 rc = sqlite3Fts3InitTok(db, (void *)pHash, hashDestroy);
4197 }
4198 return rc;
4199 }
4200
4201
4202 /* An error has occurred. Delete the hash table and return the error code. */
4203 assert( rc!=SQLITE_OK );
4204 if( pHash ){
4205 sqlite3Fts3HashClear(&pHash->hash);
4206 sqlite3_free(pHash);
4207 }
4208 return rc;
4209 }
4210
4211 /*
4212 ** Allocate an Fts3MultiSegReader for each token in the expression headed
4213 ** by pExpr.
4214 **
4215 ** An Fts3SegReader object is a cursor that can seek or scan a range of
4216 ** entries within a single segment b-tree. An Fts3MultiSegReader uses multiple
4217 ** Fts3SegReader objects internally to provide an interface to seek or scan
4218 ** within the union of all segments of a b-tree. Hence the name.
4219 **
4220 ** If the allocated Fts3MultiSegReader just seeks to a single entry in a
4221 ** segment b-tree (if the term is not a prefix or it is a prefix for which
4222 ** there exists prefix b-tree of the right length) then it may be traversed
4223 ** and merged incrementally. Otherwise, it has to be merged into an in-memory
4224 ** doclist and then traversed.
4225 */
4226 static void fts3EvalAllocateReaders(
4227 Fts3Cursor *pCsr, /* FTS cursor handle */
4228 Fts3Expr *pExpr, /* Allocate readers for this expression */
4229 int *pnToken, /* OUT: Total number of tokens in phrase. */
4230 int *pnOr, /* OUT: Total number of OR nodes in expr. */
4231 int *pRc /* IN/OUT: Error code */
4232 ){
4233 if( pExpr && SQLITE_OK==*pRc ){
4234 if( pExpr->eType==FTSQUERY_PHRASE ){
4235 int i;
4236 int nToken = pExpr->pPhrase->nToken;
4237 *pnToken += nToken;
4238 for(i=0; i<nToken; i++){
4239 Fts3PhraseToken *pToken = &pExpr->pPhrase->aToken[i];
4240 int rc = fts3TermSegReaderCursor(pCsr,
4241 pToken->z, pToken->n, pToken->isPrefix, &pToken->pSegcsr
4242 );
4243 if( rc!=SQLITE_OK ){
4244 *pRc = rc;
4245 return;
4246 }
4247 }
4248 assert( pExpr->pPhrase->iDoclistToken==0 );
4249 pExpr->pPhrase->iDoclistToken = -1;
4250 }else{
4251 *pnOr += (pExpr->eType==FTSQUERY_OR);
4252 fts3EvalAllocateReaders(pCsr, pExpr->pLeft, pnToken, pnOr, pRc);
4253 fts3EvalAllocateReaders(pCsr, pExpr->pRight, pnToken, pnOr, pRc);
4254 }
4255 }
4256 }
4257
4258 /*
4259 ** Arguments pList/nList contain the doclist for token iToken of phrase p.
4260 ** It is merged into the main doclist stored in p->doclist.aAll/nAll.
4261 **
4262 ** This function assumes that pList points to a buffer allocated using
4263 ** sqlite3_malloc(). This function takes responsibility for eventually
4264 ** freeing the buffer.
4265 **
4266 ** SQLITE_OK is returned if successful, or SQLITE_NOMEM if an error occurs.
4267 */
4268 static int fts3EvalPhraseMergeToken(
4269 Fts3Table *pTab, /* FTS Table pointer */
4270 Fts3Phrase *p, /* Phrase to merge pList/nList into */
4271 int iToken, /* Token pList/nList corresponds to */
4272 char *pList, /* Pointer to doclist */
4273 int nList /* Number of bytes in pList */
4274 ){
4275 int rc = SQLITE_OK;
4276 assert( iToken!=p->iDoclistToken );
4277
4278 if( pList==0 ){
4279 sqlite3_free(p->doclist.aAll);
4280 p->doclist.aAll = 0;
4281 p->doclist.nAll = 0;
4282 }
4283
4284 else if( p->iDoclistToken<0 ){
4285 p->doclist.aAll = pList;
4286 p->doclist.nAll = nList;
4287 }
4288
4289 else if( p->doclist.aAll==0 ){
4290 sqlite3_free(pList);
4291 }
4292
4293 else {
4294 char *pLeft;
4295 char *pRight;
4296 int nLeft;
4297 int nRight;
4298 int nDiff;
4299
4300 if( p->iDoclistToken<iToken ){
4301 pLeft = p->doclist.aAll;
4302 nLeft = p->doclist.nAll;
4303 pRight = pList;
4304 nRight = nList;
4305 nDiff = iToken - p->iDoclistToken;
4306 }else{
4307 pRight = p->doclist.aAll;
4308 nRight = p->doclist.nAll;
4309 pLeft = pList;
4310 nLeft = nList;
4311 nDiff = p->iDoclistToken - iToken;
4312 }
4313
4314 rc = fts3DoclistPhraseMerge(
4315 pTab->bDescIdx, nDiff, pLeft, nLeft, &pRight, &nRight
4316 );
4317 sqlite3_free(pLeft);
4318 p->doclist.aAll = pRight;
4319 p->doclist.nAll = nRight;
4320 }
4321
4322 if( iToken>p->iDoclistToken ) p->iDoclistToken = iToken;
4323 return rc;
4324 }
4325
4326 /*
4327 ** Load the doclist for phrase p into p->doclist.aAll/nAll. The loaded doclist
4328 ** does not take deferred tokens into account.
4329 **
4330 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.
4331 */
4332 static int fts3EvalPhraseLoad(
4333 Fts3Cursor *pCsr, /* FTS Cursor handle */
4334 Fts3Phrase *p /* Phrase object */
4335 ){
4336 Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
4337 int iToken;
4338 int rc = SQLITE_OK;
4339
4340 for(iToken=0; rc==SQLITE_OK && iToken<p->nToken; iToken++){
4341 Fts3PhraseToken *pToken = &p->aToken[iToken];
4342 assert( pToken->pDeferred==0 || pToken->pSegcsr==0 );
4343
4344 if( pToken->pSegcsr ){
4345 int nThis = 0;
4346 char *pThis = 0;
4347 rc = fts3TermSelect(pTab, pToken, p->iColumn, &nThis, &pThis);
4348 if( rc==SQLITE_OK ){
4349 rc = fts3EvalPhraseMergeToken(pTab, p, iToken, pThis, nThis);
4350 }
4351 }
4352 assert( pToken->pSegcsr==0 );
4353 }
4354
4355 return rc;
4356 }
4357
4358 #ifndef SQLITE_DISABLE_FTS4_DEFERRED
4359 /*
4360 ** This function is called on each phrase after the position lists for
4361 ** any deferred tokens have been loaded into memory. It updates the phrases
4362 ** current position list to include only those positions that are really
4363 ** instances of the phrase (after considering deferred tokens). If this
4364 ** means that the phrase does not appear in the current row, doclist.pList
4365 ** and doclist.nList are both zeroed.
4366 **
4367 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.
4368 */
4369 static int fts3EvalDeferredPhrase(Fts3Cursor *pCsr, Fts3Phrase *pPhrase){
4370 int iToken; /* Used to iterate through phrase tokens */
4371 char *aPoslist = 0; /* Position list for deferred tokens */
4372 int nPoslist = 0; /* Number of bytes in aPoslist */
4373 int iPrev = -1; /* Token number of previous deferred token */
4374 char *aFree = (pPhrase->doclist.bFreeList ? pPhrase->doclist.pList : 0);
4375
4376 for(iToken=0; iToken<pPhrase->nToken; iToken++){
4377 Fts3PhraseToken *pToken = &pPhrase->aToken[iToken];
4378 Fts3DeferredToken *pDeferred = pToken->pDeferred;
4379
4380 if( pDeferred ){
4381 char *pList;
4382 int nList;
4383 int rc = sqlite3Fts3DeferredTokenList(pDeferred, &pList, &nList);
4384 if( rc!=SQLITE_OK ) return rc;
4385
4386 if( pList==0 ){
4387 sqlite3_free(aPoslist);
4388 sqlite3_free(aFree);
4389 pPhrase->doclist.pList = 0;
4390 pPhrase->doclist.nList = 0;
4391 return SQLITE_OK;
4392
4393 }else if( aPoslist==0 ){
4394 aPoslist = pList;
4395 nPoslist = nList;
4396
4397 }else{
4398 char *aOut = pList;
4399 char *p1 = aPoslist;
4400 char *p2 = aOut;
4401
4402 assert( iPrev>=0 );
4403 fts3PoslistPhraseMerge(&aOut, iToken-iPrev, 0, 1, &p1, &p2);
4404 sqlite3_free(aPoslist);
4405 aPoslist = pList;
4406 nPoslist = (int)(aOut - aPoslist);
4407 if( nPoslist==0 ){
4408 sqlite3_free(aPoslist);
4409 sqlite3_free(aFree);
4410 pPhrase->doclist.pList = 0;
4411 pPhrase->doclist.nList = 0;
4412 return SQLITE_OK;
4413 }
4414 }
4415 iPrev = iToken;
4416 }
4417 }
4418
4419 if( iPrev>=0 ){
4420 int nMaxUndeferred = pPhrase->iDoclistToken;
4421 if( nMaxUndeferred<0 ){
4422 pPhrase->doclist.pList = aPoslist;
4423 pPhrase->doclist.nList = nPoslist;
4424 pPhrase->doclist.iDocid = pCsr->iPrevId;
4425 pPhrase->doclist.bFreeList = 1;
4426 }else{
4427 int nDistance;
4428 char *p1;
4429 char *p2;
4430 char *aOut;
4431
4432 if( nMaxUndeferred>iPrev ){
4433 p1 = aPoslist;
4434 p2 = pPhrase->doclist.pList;
4435 nDistance = nMaxUndeferred - iPrev;
4436 }else{
4437 p1 = pPhrase->doclist.pList;
4438 p2 = aPoslist;
4439 nDistance = iPrev - nMaxUndeferred;
4440 }
4441
4442 aOut = (char *)sqlite3Fts3MallocZero(((i64)nPoslist)+FTS3_BUFFER_PADDING);
4443 if( !aOut ){
4444 sqlite3_free(aPoslist);
4445 return SQLITE_NOMEM;
4446 }
4447
4448 pPhrase->doclist.pList = aOut;
4449 assert( p1 && p2 );
4450 if( fts3PoslistPhraseMerge(&aOut, nDistance, 0, 1, &p1, &p2) ){
4451 pPhrase->doclist.bFreeList = 1;
4452 pPhrase->doclist.nList = (int)(aOut - pPhrase->doclist.pList);
4453 }else{
4454 sqlite3_free(aOut);
4455 pPhrase->doclist.pList = 0;
4456 pPhrase->doclist.nList = 0;
4457 }
4458 sqlite3_free(aPoslist);
4459 }
4460 }
4461
4462 if( pPhrase->doclist.pList!=aFree ) sqlite3_free(aFree);
4463 return SQLITE_OK;
4464 }
4465 #endif /* SQLITE_DISABLE_FTS4_DEFERRED */
4466
4467 /*
4468 ** Maximum number of tokens a phrase may have to be considered for the
4469 ** incremental doclists strategy.
4470 */
4471 #define MAX_INCR_PHRASE_TOKENS 4
4472
4473 /*
4474 ** This function is called for each Fts3Phrase in a full-text query
4475 ** expression to initialize the mechanism for returning rows. Once this
4476 ** function has been called successfully on an Fts3Phrase, it may be
4477 ** used with fts3EvalPhraseNext() to iterate through the matching docids.
4478 **
4479 ** If parameter bOptOk is true, then the phrase may (or may not) use the
4480 ** incremental loading strategy. Otherwise, the entire doclist is loaded into
4481 ** memory within this call.
4482 **
4483 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.
4484 */
4485 static int fts3EvalPhraseStart(Fts3Cursor *pCsr, int bOptOk, Fts3Phrase *p){
4486 Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
4487 int rc = SQLITE_OK; /* Error code */
4488 int i;
4489
4490 /* Determine if doclists may be loaded from disk incrementally. This is
4491 ** possible if the bOptOk argument is true, the FTS doclists will be
4492 ** scanned in forward order, and the phrase consists of
4493 ** MAX_INCR_PHRASE_TOKENS or fewer tokens, none of which are are "^first"
4494 ** tokens or prefix tokens that cannot use a prefix-index. */
4495 int bHaveIncr = 0;
4496 int bIncrOk = (bOptOk
4497 && pCsr->bDesc==pTab->bDescIdx
4498 && p->nToken<=MAX_INCR_PHRASE_TOKENS && p->nToken>0
4499 #if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
4500 && pTab->bNoIncrDoclist==0
4501 #endif
4502 );
4503 for(i=0; bIncrOk==1 && i<p->nToken; i++){
4504 Fts3PhraseToken *pToken = &p->aToken[i];
4505 if( pToken->bFirst || (pToken->pSegcsr!=0 && !pToken->pSegcsr->bLookup) ){
4506 bIncrOk = 0;
4507 }
4508 if( pToken->pSegcsr ) bHaveIncr = 1;
4509 }
4510
4511 if( bIncrOk && bHaveIncr ){
4512 /* Use the incremental approach. */
4513 int iCol = (p->iColumn >= pTab->nColumn ? -1 : p->iColumn);
4514 for(i=0; rc==SQLITE_OK && i<p->nToken; i++){
4515 Fts3PhraseToken *pToken = &p->aToken[i];
4516 Fts3MultiSegReader *pSegcsr = pToken->pSegcsr;
4517 if( pSegcsr ){
4518 rc = sqlite3Fts3MsrIncrStart(pTab, pSegcsr, iCol, pToken->z, pToken->n);
4519 }
4520 }
4521 p->bIncr = 1;
4522 }else{
4523 /* Load the full doclist for the phrase into memory. */
4524 rc = fts3EvalPhraseLoad(pCsr, p);
4525 p->bIncr = 0;
4526 }
4527
4528 assert( rc!=SQLITE_OK || p->nToken<1 || p->aToken[0].pSegcsr==0 || p->bIncr );
4529 return rc;
4530 }
4531
4532 /*
4533 ** This function is used to iterate backwards (from the end to start)
4534 ** through doclists. It is used by this module to iterate through phrase
4535 ** doclists in reverse and by the fts3_write.c module to iterate through
4536 ** pending-terms lists when writing to databases with "order=desc".
4537 **
4538 ** The doclist may be sorted in ascending (parameter bDescIdx==0) or
4539 ** descending (parameter bDescIdx==1) order of docid. Regardless, this
4540 ** function iterates from the end of the doclist to the beginning.
4541 */
4542 void sqlite3Fts3DoclistPrev(
4543 int bDescIdx, /* True if the doclist is desc */
4544 char *aDoclist, /* Pointer to entire doclist */
4545 int nDoclist, /* Length of aDoclist in bytes */
4546 char **ppIter, /* IN/OUT: Iterator pointer */
4547 sqlite3_int64 *piDocid, /* IN/OUT: Docid pointer */
4548 int *pnList, /* OUT: List length pointer */
4549 u8 *pbEof /* OUT: End-of-file flag */
4550 ){
4551 char *p = *ppIter;
4552
4553 assert( nDoclist>0 );
4554 assert( *pbEof==0 );
4555 assert_fts3_nc( p || *piDocid==0 );
4556 assert( !p || (p>aDoclist && p<&aDoclist[nDoclist]) );
4557
4558 if( p==0 ){
4559 sqlite3_int64 iDocid = 0;
4560 char *pNext = 0;
4561 char *pDocid = aDoclist;
4562 char *pEnd = &aDoclist[nDoclist];
4563 int iMul = 1;
4564
4565 while( pDocid<pEnd ){
4566 sqlite3_int64 iDelta;
4567 pDocid += sqlite3Fts3GetVarint(pDocid, &iDelta);
4568 iDocid += (iMul * iDelta);
4569 pNext = pDocid;
4570 fts3PoslistCopy(0, &pDocid);
4571 while( pDocid<pEnd && *pDocid==0 ) pDocid++;
4572 iMul = (bDescIdx ? -1 : 1);
4573 }
4574
4575 *pnList = (int)(pEnd - pNext);
4576 *ppIter = pNext;
4577 *piDocid = iDocid;
4578 }else{
4579 int iMul = (bDescIdx ? -1 : 1);
4580 sqlite3_int64 iDelta;
4581 fts3GetReverseVarint(&p, aDoclist, &iDelta);
4582 *piDocid -= (iMul * iDelta);
4583
4584 if( p==aDoclist ){
4585 *pbEof = 1;
4586 }else{
4587 char *pSave = p;
4588 fts3ReversePoslist(aDoclist, &p);
4589 *pnList = (int)(pSave - p);
4590 }
4591 *ppIter = p;
4592 }
4593 }
4594
4595 /*
4596 ** Iterate forwards through a doclist.
4597 */
4598 void sqlite3Fts3DoclistNext(
4599 int bDescIdx, /* True if the doclist is desc */
4600 char *aDoclist, /* Pointer to entire doclist */
4601 int nDoclist, /* Length of aDoclist in bytes */
4602 char **ppIter, /* IN/OUT: Iterator pointer */
4603 sqlite3_int64 *piDocid, /* IN/OUT: Docid pointer */
4604 u8 *pbEof /* OUT: End-of-file flag */
4605 ){
4606 char *p = *ppIter;
4607
4608 assert( nDoclist>0 );
4609 assert( *pbEof==0 );
4610 assert_fts3_nc( p || *piDocid==0 );
4611 assert( !p || (p>=aDoclist && p<=&aDoclist[nDoclist]) );
4612
4613 if( p==0 ){
4614 p = aDoclist;
4615 p += sqlite3Fts3GetVarint(p, piDocid);
4616 }else{
4617 fts3PoslistCopy(0, &p);
4618 while( p<&aDoclist[nDoclist] && *p==0 ) p++;
4619 if( p>=&aDoclist[nDoclist] ){
4620 *pbEof = 1;
4621 }else{
4622 sqlite3_int64 iVar;
4623 p += sqlite3Fts3GetVarint(p, &iVar);
4624 *piDocid += ((bDescIdx ? -1 : 1) * iVar);
4625 }
4626 }
4627
4628 *ppIter = p;
4629 }
4630
4631 /*
4632 ** Advance the iterator pDL to the next entry in pDL->aAll/nAll. Set *pbEof
4633 ** to true if EOF is reached.
4634 */
4635 static void fts3EvalDlPhraseNext(
4636 Fts3Table *pTab,
4637 Fts3Doclist *pDL,
4638 u8 *pbEof
4639 ){
4640 char *pIter; /* Used to iterate through aAll */
4641 char *pEnd; /* 1 byte past end of aAll */
4642
4643 if( pDL->pNextDocid ){
4644 pIter = pDL->pNextDocid;
4645 assert( pDL->aAll!=0 || pIter==0 );
4646 }else{
4647 pIter = pDL->aAll;
4648 }
4649
4650 if( pIter==0 || pIter>=(pEnd = pDL->aAll + pDL->nAll) ){
4651 /* We have already reached the end of this doclist. EOF. */
4652 *pbEof = 1;
4653 }else{
4654 sqlite3_int64 iDelta;
4655 pIter += sqlite3Fts3GetVarint(pIter, &iDelta);
4656 if( pTab->bDescIdx==0 || pDL->pNextDocid==0 ){
4657 pDL->iDocid += iDelta;
4658 }else{
4659 pDL->iDocid -= iDelta;
4660 }
4661 pDL->pList = pIter;
4662 fts3PoslistCopy(0, &pIter);
4663 pDL->nList = (int)(pIter - pDL->pList);
4664
4665 /* pIter now points just past the 0x00 that terminates the position-
4666 ** list for document pDL->iDocid. However, if this position-list was
4667 ** edited in place by fts3EvalNearTrim(), then pIter may not actually
4668 ** point to the start of the next docid value. The following line deals
4669 ** with this case by advancing pIter past the zero-padding added by
4670 ** fts3EvalNearTrim(). */
4671 while( pIter<pEnd && *pIter==0 ) pIter++;
4672
4673 pDL->pNextDocid = pIter;
4674 assert( pIter>=&pDL->aAll[pDL->nAll] || *pIter );
4675 *pbEof = 0;
4676 }
4677 }
4678
4679 /*
4680 ** Helper type used by fts3EvalIncrPhraseNext() and incrPhraseTokenNext().
4681 */
4682 typedef struct TokenDoclist TokenDoclist;
4683 struct TokenDoclist {
4684 int bIgnore;
4685 sqlite3_int64 iDocid;
4686 char *pList;
4687 int nList;
4688 };
4689
4690 /*
4691 ** Token pToken is an incrementally loaded token that is part of a
4692 ** multi-token phrase. Advance it to the next matching document in the
4693 ** database and populate output variable *p with the details of the new
4694 ** entry. Or, if the iterator has reached EOF, set *pbEof to true.
4695 **
4696 ** If an error occurs, return an SQLite error code. Otherwise, return
4697 ** SQLITE_OK.
4698 */
4699 static int incrPhraseTokenNext(
4700 Fts3Table *pTab, /* Virtual table handle */
4701 Fts3Phrase *pPhrase, /* Phrase to advance token of */
4702 int iToken, /* Specific token to advance */
4703 TokenDoclist *p, /* OUT: Docid and doclist for new entry */
4704 u8 *pbEof /* OUT: True if iterator is at EOF */
4705 ){
4706 int rc = SQLITE_OK;
4707
4708 if( pPhrase->iDoclistToken==iToken ){
4709 assert( p->bIgnore==0 );
4710 assert( pPhrase->aToken[iToken].pSegcsr==0 );
4711 fts3EvalDlPhraseNext(pTab, &pPhrase->doclist, pbEof);
4712 p->pList = pPhrase->doclist.pList;
4713 p->nList = pPhrase->doclist.nList;
4714 p->iDocid = pPhrase->doclist.iDocid;
4715 }else{
4716 Fts3PhraseToken *pToken = &pPhrase->aToken[iToken];
4717 assert( pToken->pDeferred==0 );
4718 assert( pToken->pSegcsr || pPhrase->iDoclistToken>=0 );
4719 if( pToken->pSegcsr ){
4720 assert( p->bIgnore==0 );
4721 rc = sqlite3Fts3MsrIncrNext(
4722 pTab, pToken->pSegcsr, &p->iDocid, &p->pList, &p->nList
4723 );
4724 if( p->pList==0 ) *pbEof = 1;
4725 }else{
4726 p->bIgnore = 1;
4727 }
4728 }
4729
4730 return rc;
4731 }
4732
4733
4734 /*
4735 ** The phrase iterator passed as the second argument:
4736 **
4737 ** * features at least one token that uses an incremental doclist, and
4738 **
4739 ** * does not contain any deferred tokens.
4740 **
4741 ** Advance it to the next matching document in the database and populate
4742 ** the Fts3Doclist.pList and nList fields.
4743 **
4744 ** If there is no "next" entry and no error occurs, then *pbEof is set to
4745 ** 1 before returning. Otherwise, if no error occurs and the iterator is
4746 ** successfully advanced, *pbEof is set to 0.
4747 **
4748 ** If an error occurs, return an SQLite error code. Otherwise, return
4749 ** SQLITE_OK.
4750 */
4751 static int fts3EvalIncrPhraseNext(
4752 Fts3Cursor *pCsr, /* FTS Cursor handle */
4753 Fts3Phrase *p, /* Phrase object to advance to next docid */
4754 u8 *pbEof /* OUT: Set to 1 if EOF */
4755 ){
4756 int rc = SQLITE_OK;
4757 Fts3Doclist *pDL = &p->doclist;
4758 Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
4759 u8 bEof = 0;
4760
4761 /* This is only called if it is guaranteed that the phrase has at least
4762 ** one incremental token. In which case the bIncr flag is set. */
4763 assert( p->bIncr==1 );
4764
4765 if( p->nToken==1 ){
4766 rc = sqlite3Fts3MsrIncrNext(pTab, p->aToken[0].pSegcsr,
4767 &pDL->iDocid, &pDL->pList, &pDL->nList
4768 );
4769 if( pDL->pList==0 ) bEof = 1;
4770 }else{
4771 int bDescDoclist = pCsr->bDesc;
4772 struct TokenDoclist a[MAX_INCR_PHRASE_TOKENS];
4773
4774 memset(a, 0, sizeof(a));
4775 assert( p->nToken<=MAX_INCR_PHRASE_TOKENS );
4776 assert( p->iDoclistToken<MAX_INCR_PHRASE_TOKENS );
4777
4778 while( bEof==0 ){
4779 int bMaxSet = 0;
4780 sqlite3_int64 iMax = 0; /* Largest docid for all iterators */
4781 int i; /* Used to iterate through tokens */
4782
4783 /* Advance the iterator for each token in the phrase once. */
4784 for(i=0; rc==SQLITE_OK && i<p->nToken && bEof==0; i++){
4785 rc = incrPhraseTokenNext(pTab, p, i, &a[i], &bEof);
4786 if( a[i].bIgnore==0 && (bMaxSet==0 || DOCID_CMP(iMax, a[i].iDocid)<0) ){
4787 iMax = a[i].iDocid;
4788 bMaxSet = 1;
4789 }
4790 }
4791 assert( rc!=SQLITE_OK || (p->nToken>=1 && a[p->nToken-1].bIgnore==0) );
4792 assert( rc!=SQLITE_OK || bMaxSet );
4793
4794 /* Keep advancing iterators until they all point to the same document */
4795 for(i=0; i<p->nToken; i++){
4796 while( rc==SQLITE_OK && bEof==0
4797 && a[i].bIgnore==0 && DOCID_CMP(a[i].iDocid, iMax)<0
4798 ){
4799 rc = incrPhraseTokenNext(pTab, p, i, &a[i], &bEof);
4800 if( DOCID_CMP(a[i].iDocid, iMax)>0 ){
4801 iMax = a[i].iDocid;
4802 i = 0;
4803 }
4804 }
4805 }
4806
4807 /* Check if the current entries really are a phrase match */
4808 if( bEof==0 ){
4809 int nList = 0;
4810 int nByte = a[p->nToken-1].nList;
4811 char *aDoclist = sqlite3_malloc64((i64)nByte+FTS3_BUFFER_PADDING);
4812 if( !aDoclist ) return SQLITE_NOMEM;
4813 memcpy(aDoclist, a[p->nToken-1].pList, nByte+1);
4814 memset(&aDoclist[nByte], 0, FTS3_BUFFER_PADDING);
4815
4816 for(i=0; i<(p->nToken-1); i++){
4817 if( a[i].bIgnore==0 ){
4818 char *pL = a[i].pList;
4819 char *pR = aDoclist;
4820 char *pOut = aDoclist;
4821 int nDist = p->nToken-1-i;
4822 int res = fts3PoslistPhraseMerge(&pOut, nDist, 0, 1, &pL, &pR);
4823 if( res==0 ) break;
4824 nList = (int)(pOut - aDoclist);
4825 }
4826 }
4827 if( i==(p->nToken-1) ){
4828 pDL->iDocid = iMax;
4829 pDL->pList = aDoclist;
4830 pDL->nList = nList;
4831 pDL->bFreeList = 1;
4832 break;
4833 }
4834 sqlite3_free(aDoclist);
4835 }
4836 }
4837 }
4838
4839 *pbEof = bEof;
4840 return rc;
4841 }
4842
4843 /*
4844 ** Attempt to move the phrase iterator to point to the next matching docid.
4845 ** If an error occurs, return an SQLite error code. Otherwise, return
4846 ** SQLITE_OK.
4847 **
4848 ** If there is no "next" entry and no error occurs, then *pbEof is set to
4849 ** 1 before returning. Otherwise, if no error occurs and the iterator is
4850 ** successfully advanced, *pbEof is set to 0.
4851 */
4852 static int fts3EvalPhraseNext(
4853 Fts3Cursor *pCsr, /* FTS Cursor handle */
4854 Fts3Phrase *p, /* Phrase object to advance to next docid */
4855 u8 *pbEof /* OUT: Set to 1 if EOF */
4856 ){
4857 int rc = SQLITE_OK;
4858 Fts3Doclist *pDL = &p->doclist;
4859 Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
4860
4861 if( p->bIncr ){
4862 rc = fts3EvalIncrPhraseNext(pCsr, p, pbEof);
4863 }else if( pCsr->bDesc!=pTab->bDescIdx && pDL->nAll ){
4864 sqlite3Fts3DoclistPrev(pTab->bDescIdx, pDL->aAll, pDL->nAll,
4865 &pDL->pNextDocid, &pDL->iDocid, &pDL->nList, pbEof
4866 );
4867 pDL->pList = pDL->pNextDocid;
4868 }else{
4869 fts3EvalDlPhraseNext(pTab, pDL, pbEof);
4870 }
4871
4872 return rc;
4873 }
4874
4875 /*
4876 **
4877 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.
4878 ** Otherwise, fts3EvalPhraseStart() is called on all phrases within the
4879 ** expression. Also the Fts3Expr.bDeferred variable is set to true for any
4880 ** expressions for which all descendent tokens are deferred.
4881 **
4882 ** If parameter bOptOk is zero, then it is guaranteed that the
4883 ** Fts3Phrase.doclist.aAll/nAll variables contain the entire doclist for
4884 ** each phrase in the expression (subject to deferred token processing).
4885 ** Or, if bOptOk is non-zero, then one or more tokens within the expression
4886 ** may be loaded incrementally, meaning doclist.aAll/nAll is not available.
4887 **
4888 ** If an error occurs within this function, *pRc is set to an SQLite error
4889 ** code before returning.
4890 */
4891 static void fts3EvalStartReaders(
4892 Fts3Cursor *pCsr, /* FTS Cursor handle */
4893 Fts3Expr *pExpr, /* Expression to initialize phrases in */
4894 int *pRc /* IN/OUT: Error code */
4895 ){
4896 if( pExpr && SQLITE_OK==*pRc ){
4897 if( pExpr->eType==FTSQUERY_PHRASE ){
4898 int nToken = pExpr->pPhrase->nToken;
4899 if( nToken ){
4900 int i;
4901 for(i=0; i<nToken; i++){
4902 if( pExpr->pPhrase->aToken[i].pDeferred==0 ) break;
4903 }
4904 pExpr->bDeferred = (i==nToken);
4905 }
4906 *pRc = fts3EvalPhraseStart(pCsr, 1, pExpr->pPhrase);
4907 }else{
4908 fts3EvalStartReaders(pCsr, pExpr->pLeft, pRc);
4909 fts3EvalStartReaders(pCsr, pExpr->pRight, pRc);
4910 pExpr->bDeferred = (pExpr->pLeft->bDeferred && pExpr->pRight->bDeferred);
4911 }
4912 }
4913 }
4914
4915 /*
4916 ** An array of the following structures is assembled as part of the process
4917 ** of selecting tokens to defer before the query starts executing (as part
4918 ** of the xFilter() method). There is one element in the array for each
4919 ** token in the FTS expression.
4920 **
4921 ** Tokens are divided into AND/NEAR clusters. All tokens in a cluster belong
4922 ** to phrases that are connected only by AND and NEAR operators (not OR or
4923 ** NOT). When determining tokens to defer, each AND/NEAR cluster is considered
4924 ** separately. The root of a tokens AND/NEAR cluster is stored in
4925 ** Fts3TokenAndCost.pRoot.
4926 */
4927 typedef struct Fts3TokenAndCost Fts3TokenAndCost;
4928 struct Fts3TokenAndCost {
4929 Fts3Phrase *pPhrase; /* The phrase the token belongs to */
4930 int iToken; /* Position of token in phrase */
4931 Fts3PhraseToken *pToken; /* The token itself */
4932 Fts3Expr *pRoot; /* Root of NEAR/AND cluster */
4933 int nOvfl; /* Number of overflow pages to load doclist */
4934 int iCol; /* The column the token must match */
4935 };
4936
4937 /*
4938 ** This function is used to populate an allocated Fts3TokenAndCost array.
4939 **
4940 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.
4941 ** Otherwise, if an error occurs during execution, *pRc is set to an
4942 ** SQLite error code.
4943 */
4944 static void fts3EvalTokenCosts(
4945 Fts3Cursor *pCsr, /* FTS Cursor handle */
4946 Fts3Expr *pRoot, /* Root of current AND/NEAR cluster */
4947 Fts3Expr *pExpr, /* Expression to consider */
4948 Fts3TokenAndCost **ppTC, /* Write new entries to *(*ppTC)++ */
4949 Fts3Expr ***ppOr, /* Write new OR root to *(*ppOr)++ */
4950 int *pRc /* IN/OUT: Error code */
4951 ){
4952 if( *pRc==SQLITE_OK ){
4953 if( pExpr->eType==FTSQUERY_PHRASE ){
4954 Fts3Phrase *pPhrase = pExpr->pPhrase;
4955 int i;
4956 for(i=0; *pRc==SQLITE_OK && i<pPhrase->nToken; i++){
4957 Fts3TokenAndCost *pTC = (*ppTC)++;
4958 pTC->pPhrase = pPhrase;
4959 pTC->iToken = i;
4960 pTC->pRoot = pRoot;
4961 pTC->pToken = &pPhrase->aToken[i];
4962 pTC->iCol = pPhrase->iColumn;
4963 *pRc = sqlite3Fts3MsrOvfl(pCsr, pTC->pToken->pSegcsr, &pTC->nOvfl);
4964 }
4965 }else if( pExpr->eType!=FTSQUERY_NOT ){
4966 assert( pExpr->eType==FTSQUERY_OR
4967 || pExpr->eType==FTSQUERY_AND
4968 || pExpr->eType==FTSQUERY_NEAR
4969 );
4970 assert( pExpr->pLeft && pExpr->pRight );
4971 if( pExpr->eType==FTSQUERY_OR ){
4972 pRoot = pExpr->pLeft;
4973 **ppOr = pRoot;
4974 (*ppOr)++;
4975 }
4976 fts3EvalTokenCosts(pCsr, pRoot, pExpr->pLeft, ppTC, ppOr, pRc);
4977 if( pExpr->eType==FTSQUERY_OR ){
4978 pRoot = pExpr->pRight;
4979 **ppOr = pRoot;
4980 (*ppOr)++;
4981 }
4982 fts3EvalTokenCosts(pCsr, pRoot, pExpr->pRight, ppTC, ppOr, pRc);
4983 }
4984 }
4985 }
4986
4987 /*
4988 ** Determine the average document (row) size in pages. If successful,
4989 ** write this value to *pnPage and return SQLITE_OK. Otherwise, return
4990 ** an SQLite error code.
4991 **
4992 ** The average document size in pages is calculated by first calculating
4993 ** determining the average size in bytes, B. If B is less than the amount
4994 ** of data that will fit on a single leaf page of an intkey table in
4995 ** this database, then the average docsize is 1. Otherwise, it is 1 plus
4996 ** the number of overflow pages consumed by a record B bytes in size.
4997 */
4998 static int fts3EvalAverageDocsize(Fts3Cursor *pCsr, int *pnPage){
4999 int rc = SQLITE_OK;
5000 if( pCsr->nRowAvg==0 ){
5001 /* The average document size, which is required to calculate the cost
5002 ** of each doclist, has not yet been determined. Read the required
5003 ** data from the %_stat table to calculate it.
5004 **
5005 ** Entry 0 of the %_stat table is a blob containing (nCol+1) FTS3
5006 ** varints, where nCol is the number of columns in the FTS3 table.
5007 ** The first varint is the number of documents currently stored in
5008 ** the table. The following nCol varints contain the total amount of
5009 ** data stored in all rows of each column of the table, from left
5010 ** to right.
5011 */
5012 Fts3Table *p = (Fts3Table*)pCsr->base.pVtab;
5013 sqlite3_stmt *pStmt;
5014 sqlite3_int64 nDoc = 0;
5015 sqlite3_int64 nByte = 0;
5016 const char *pEnd;
5017 const char *a;
5018
5019 rc = sqlite3Fts3SelectDoctotal(p, &pStmt);
5020 if( rc!=SQLITE_OK ) return rc;
5021 a = sqlite3_column_blob(pStmt, 0);
5022 testcase( a==0 ); /* If %_stat.value set to X'' */
5023 if( a ){
5024 pEnd = &a[sqlite3_column_bytes(pStmt, 0)];
5025 a += sqlite3Fts3GetVarintBounded(a, pEnd, &nDoc);
5026 while( a<pEnd ){
5027 a += sqlite3Fts3GetVarintBounded(a, pEnd, &nByte);
5028 }
5029 }
5030 if( nDoc==0 || nByte==0 ){
5031 sqlite3_reset(pStmt);
5032 return FTS_CORRUPT_VTAB;
5033 }
5034
5035 pCsr->nDoc = nDoc;
5036 pCsr->nRowAvg = (int)(((nByte / nDoc) + p->nPgsz) / p->nPgsz);
5037 assert( pCsr->nRowAvg>0 );
5038 rc = sqlite3_reset(pStmt);
5039 }
5040
5041 *pnPage = pCsr->nRowAvg;
5042 return rc;
5043 }
5044
5045 /*
5046 ** This function is called to select the tokens (if any) that will be
5047 ** deferred. The array aTC[] has already been populated when this is
5048 ** called.
5049 **
5050 ** This function is called once for each AND/NEAR cluster in the
5051 ** expression. Each invocation determines which tokens to defer within
5052 ** the cluster with root node pRoot. See comments above the definition
5053 ** of struct Fts3TokenAndCost for more details.
5054 **
5055 ** If no error occurs, SQLITE_OK is returned and sqlite3Fts3DeferToken()
5056 ** called on each token to defer. Otherwise, an SQLite error code is
5057 ** returned.
5058 */
5059 static int fts3EvalSelectDeferred(
5060 Fts3Cursor *pCsr, /* FTS Cursor handle */
5061 Fts3Expr *pRoot, /* Consider tokens with this root node */
5062 Fts3TokenAndCost *aTC, /* Array of expression tokens and costs */
5063 int nTC /* Number of entries in aTC[] */
5064 ){
5065 Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
5066 int nDocSize = 0; /* Number of pages per doc loaded */
5067 int rc = SQLITE_OK; /* Return code */
5068 int ii; /* Iterator variable for various purposes */
5069 int nOvfl = 0; /* Total overflow pages used by doclists */
5070 int nToken = 0; /* Total number of tokens in cluster */
5071
5072 int nMinEst = 0; /* The minimum count for any phrase so far. */
5073 int nLoad4 = 1; /* (Phrases that will be loaded)^4. */
5074
5075 /* Tokens are never deferred for FTS tables created using the content=xxx
5076 ** option. The reason being that it is not guaranteed that the content
5077 ** table actually contains the same data as the index. To prevent this from
5078 ** causing any problems, the deferred token optimization is completely
5079 ** disabled for content=xxx tables. */
5080 if( pTab->zContentTbl ){
5081 return SQLITE_OK;
5082 }
5083
5084 /* Count the tokens in this AND/NEAR cluster. If none of the doclists
5085 ** associated with the tokens spill onto overflow pages, or if there is
5086 ** only 1 token, exit early. No tokens to defer in this case. */
5087 for(ii=0; ii<nTC; ii++){
5088 if( aTC[ii].pRoot==pRoot ){
5089 nOvfl += aTC[ii].nOvfl;
5090 nToken++;
5091 }
5092 }
5093 if( nOvfl==0 || nToken<2 ) return SQLITE_OK;
5094
5095 /* Obtain the average docsize (in pages). */
5096 rc = fts3EvalAverageDocsize(pCsr, &nDocSize);
5097 assert( rc!=SQLITE_OK || nDocSize>0 );
5098
5099
5100 /* Iterate through all tokens in this AND/NEAR cluster, in ascending order
5101 ** of the number of overflow pages that will be loaded by the pager layer
5102 ** to retrieve the entire doclist for the token from the full-text index.
5103 ** Load the doclists for tokens that are either:
5104 **
5105 ** a. The cheapest token in the entire query (i.e. the one visited by the
5106 ** first iteration of this loop), or
5107 **
5108 ** b. Part of a multi-token phrase.
5109 **
5110 ** After each token doclist is loaded, merge it with the others from the
5111 ** same phrase and count the number of documents that the merged doclist
5112 ** contains. Set variable "nMinEst" to the smallest number of documents in
5113 ** any phrase doclist for which 1 or more token doclists have been loaded.
5114 ** Let nOther be the number of other phrases for which it is certain that
5115 ** one or more tokens will not be deferred.
5116 **
5117 ** Then, for each token, defer it if loading the doclist would result in
5118 ** loading N or more overflow pages into memory, where N is computed as:
5119 **
5120 ** (nMinEst + 4^nOther - 1) / (4^nOther)
5121 */
5122 for(ii=0; ii<nToken && rc==SQLITE_OK; ii++){
5123 int iTC; /* Used to iterate through aTC[] array. */
5124 Fts3TokenAndCost *pTC = 0; /* Set to cheapest remaining token. */
5125
5126 /* Set pTC to point to the cheapest remaining token. */
5127 for(iTC=0; iTC<nTC; iTC++){
5128 if( aTC[iTC].pToken && aTC[iTC].pRoot==pRoot
5129 && (!pTC || aTC[iTC].nOvfl<pTC->nOvfl)
5130 ){
5131 pTC = &aTC[iTC];
5132 }
5133 }
5134 assert( pTC );
5135
5136 if( ii && pTC->nOvfl>=((nMinEst+(nLoad4/4)-1)/(nLoad4/4))*nDocSize ){
5137 /* The number of overflow pages to load for this (and therefore all
5138 ** subsequent) tokens is greater than the estimated number of pages
5139 ** that will be loaded if all subsequent tokens are deferred.
5140 */
5141 Fts3PhraseToken *pToken = pTC->pToken;
5142 rc = sqlite3Fts3DeferToken(pCsr, pToken, pTC->iCol);
5143 fts3SegReaderCursorFree(pToken->pSegcsr);
5144 pToken->pSegcsr = 0;
5145 }else{
5146 /* Set nLoad4 to the value of (4^nOther) for the next iteration of the
5147 ** for-loop. Except, limit the value to 2^24 to prevent it from
5148 ** overflowing the 32-bit integer it is stored in. */
5149 if( ii<12 ) nLoad4 = nLoad4*4;
5150
5151 if( ii==0 || (pTC->pPhrase->nToken>1 && ii!=nToken-1) ){
5152 /* Either this is the cheapest token in the entire query, or it is
5153 ** part of a multi-token phrase. Either way, the entire doclist will
5154 ** (eventually) be loaded into memory. It may as well be now. */
5155 Fts3PhraseToken *pToken = pTC->pToken;
5156 int nList = 0;
5157 char *pList = 0;
5158 rc = fts3TermSelect(pTab, pToken, pTC->iCol, &nList, &pList);
5159 assert( rc==SQLITE_OK || pList==0 );
5160 if( rc==SQLITE_OK ){
5161 rc = fts3EvalPhraseMergeToken(
5162 pTab, pTC->pPhrase, pTC->iToken,pList,nList
5163 );
5164 }
5165 if( rc==SQLITE_OK ){
5166 int nCount;
5167 nCount = fts3DoclistCountDocids(
5168 pTC->pPhrase->doclist.aAll, pTC->pPhrase->doclist.nAll
5169 );
5170 if( ii==0 || nCount<nMinEst ) nMinEst = nCount;
5171 }
5172 }
5173 }
5174 pTC->pToken = 0;
5175 }
5176
5177 return rc;
5178 }
5179
5180 /*
5181 ** This function is called from within the xFilter method. It initializes
5182 ** the full-text query currently stored in pCsr->pExpr. To iterate through
5183 ** the results of a query, the caller does:
5184 **
5185 ** fts3EvalStart(pCsr);
5186 ** while( 1 ){
5187 ** fts3EvalNext(pCsr);
5188 ** if( pCsr->bEof ) break;
5189 ** ... return row pCsr->iPrevId to the caller ...
5190 ** }
5191 */
5192 static int fts3EvalStart(Fts3Cursor *pCsr){
5193 Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
5194 int rc = SQLITE_OK;
5195 int nToken = 0;
5196 int nOr = 0;
5197
5198 /* Allocate a MultiSegReader for each token in the expression. */
5199 fts3EvalAllocateReaders(pCsr, pCsr->pExpr, &nToken, &nOr, &rc);
5200
5201 /* Determine which, if any, tokens in the expression should be deferred. */
5202 #ifndef SQLITE_DISABLE_FTS4_DEFERRED
5203 if( rc==SQLITE_OK && nToken>1 && pTab->bFts4 ){
5204 Fts3TokenAndCost *aTC;
5205 aTC = (Fts3TokenAndCost *)sqlite3_malloc64(
5206 sizeof(Fts3TokenAndCost) * nToken
5207 + sizeof(Fts3Expr *) * nOr * 2
5208 );
5209
5210 if( !aTC ){
5211 rc = SQLITE_NOMEM;
5212 }else{
5213 Fts3Expr **apOr = (Fts3Expr **)&aTC[nToken];
5214 int ii;
5215 Fts3TokenAndCost *pTC = aTC;
5216 Fts3Expr **ppOr = apOr;
5217
5218 fts3EvalTokenCosts(pCsr, 0, pCsr->pExpr, &pTC, &ppOr, &rc);
5219 nToken = (int)(pTC-aTC);
5220 nOr = (int)(ppOr-apOr);
5221
5222 if( rc==SQLITE_OK ){
5223 rc = fts3EvalSelectDeferred(pCsr, 0, aTC, nToken);
5224 for(ii=0; rc==SQLITE_OK && ii<nOr; ii++){
5225 rc = fts3EvalSelectDeferred(pCsr, apOr[ii], aTC, nToken);
5226 }
5227 }
5228
5229 sqlite3_free(aTC);
5230 }
5231 }
5232 #endif
5233
5234 fts3EvalStartReaders(pCsr, pCsr->pExpr, &rc);
5235 return rc;
5236 }
5237
5238 /*
5239 ** Invalidate the current position list for phrase pPhrase.
5240 */
5241 static void fts3EvalInvalidatePoslist(Fts3Phrase *pPhrase){
5242 if( pPhrase->doclist.bFreeList ){
5243 sqlite3_free(pPhrase->doclist.pList);
5244 }
5245 pPhrase->doclist.pList = 0;
5246 pPhrase->doclist.nList = 0;
5247 pPhrase->doclist.bFreeList = 0;
5248 }
5249
5250 /*
5251 ** This function is called to edit the position list associated with
5252 ** the phrase object passed as the fifth argument according to a NEAR
5253 ** condition. For example:
5254 **
5255 ** abc NEAR/5 "def ghi"
5256 **
5257 ** Parameter nNear is passed the NEAR distance of the expression (5 in
5258 ** the example above). When this function is called, *paPoslist points to
5259 ** the position list, and *pnToken is the number of phrase tokens in the
5260 ** phrase on the other side of the NEAR operator to pPhrase. For example,
5261 ** if pPhrase refers to the "def ghi" phrase, then *paPoslist points to
5262 ** the position list associated with phrase "abc".
5263 **
5264 ** All positions in the pPhrase position list that are not sufficiently
5265 ** close to a position in the *paPoslist position list are removed. If this
5266 ** leaves 0 positions, zero is returned. Otherwise, non-zero.
5267 **
5268 ** Before returning, *paPoslist is set to point to the position lsit
5269 ** associated with pPhrase. And *pnToken is set to the number of tokens in
5270 ** pPhrase.
5271 */
5272 static int fts3EvalNearTrim(
5273 int nNear, /* NEAR distance. As in "NEAR/nNear". */
5274 char *aTmp, /* Temporary space to use */
5275 char **paPoslist, /* IN/OUT: Position list */
5276 int *pnToken, /* IN/OUT: Tokens in phrase of *paPoslist */
5277 Fts3Phrase *pPhrase /* The phrase object to trim the doclist of */
5278 ){
5279 int nParam1 = nNear + pPhrase->nToken;
5280 int nParam2 = nNear + *pnToken;
5281 int nNew;
5282 char *p2;
5283 char *pOut;
5284 int res;
5285
5286 assert( pPhrase->doclist.pList );
5287
5288 p2 = pOut = pPhrase->doclist.pList;
5289 res = fts3PoslistNearMerge(
5290 &pOut, aTmp, nParam1, nParam2, paPoslist, &p2
5291 );
5292 if( res ){
5293 nNew = (int)(pOut - pPhrase->doclist.pList) - 1;
5294 assert_fts3_nc( nNew<=pPhrase->doclist.nList && nNew>0 );
5295 if( nNew>=0 && nNew<=pPhrase->doclist.nList ){
5296 assert( pPhrase->doclist.pList[nNew]=='\0' );
5297 memset(&pPhrase->doclist.pList[nNew], 0, pPhrase->doclist.nList - nNew);
5298 pPhrase->doclist.nList = nNew;
5299 }
5300 *paPoslist = pPhrase->doclist.pList;
5301 *pnToken = pPhrase->nToken;
5302 }
5303
5304 return res;
5305 }
5306
5307 /*
5308 ** This function is a no-op if *pRc is other than SQLITE_OK when it is called.
5309 ** Otherwise, it advances the expression passed as the second argument to
5310 ** point to the next matching row in the database. Expressions iterate through
5311 ** matching rows in docid order. Ascending order if Fts3Cursor.bDesc is zero,
5312 ** or descending if it is non-zero.
5313 **
5314 ** If an error occurs, *pRc is set to an SQLite error code. Otherwise, if
5315 ** successful, the following variables in pExpr are set:
5316 **
5317 ** Fts3Expr.bEof (non-zero if EOF - there is no next row)
5318 ** Fts3Expr.iDocid (valid if bEof==0. The docid of the next row)
5319 **
5320 ** If the expression is of type FTSQUERY_PHRASE, and the expression is not
5321 ** at EOF, then the following variables are populated with the position list
5322 ** for the phrase for the visited row:
5323 **
5324 ** FTs3Expr.pPhrase->doclist.nList (length of pList in bytes)
5325 ** FTs3Expr.pPhrase->doclist.pList (pointer to position list)
5326 **
5327 ** It says above that this function advances the expression to the next
5328 ** matching row. This is usually true, but there are the following exceptions:
5329 **
5330 ** 1. Deferred tokens are not taken into account. If a phrase consists
5331 ** entirely of deferred tokens, it is assumed to match every row in
5332 ** the db. In this case the position-list is not populated at all.
5333 **
5334 ** Or, if a phrase contains one or more deferred tokens and one or
5335 ** more non-deferred tokens, then the expression is advanced to the
5336 ** next possible match, considering only non-deferred tokens. In other
5337 ** words, if the phrase is "A B C", and "B" is deferred, the expression
5338 ** is advanced to the next row that contains an instance of "A * C",
5339 ** where "*" may match any single token. The position list in this case
5340 ** is populated as for "A * C" before returning.
5341 **
5342 ** 2. NEAR is treated as AND. If the expression is "x NEAR y", it is
5343 ** advanced to point to the next row that matches "x AND y".
5344 **
5345 ** See sqlite3Fts3EvalTestDeferred() for details on testing if a row is
5346 ** really a match, taking into account deferred tokens and NEAR operators.
5347 */
5348 static void fts3EvalNextRow(
5349 Fts3Cursor *pCsr, /* FTS Cursor handle */
5350 Fts3Expr *pExpr, /* Expr. to advance to next matching row */
5351 int *pRc /* IN/OUT: Error code */
5352 ){
5353 if( *pRc==SQLITE_OK && pExpr->bEof==0 ){
5354 int bDescDoclist = pCsr->bDesc; /* Used by DOCID_CMP() macro */
5355 pExpr->bStart = 1;
5356
5357 switch( pExpr->eType ){
5358 case FTSQUERY_NEAR:
5359 case FTSQUERY_AND: {
5360 Fts3Expr *pLeft = pExpr->pLeft;
5361 Fts3Expr *pRight = pExpr->pRight;
5362 assert( !pLeft->bDeferred || !pRight->bDeferred );
5363
5364 if( pLeft->bDeferred ){
5365 /* LHS is entirely deferred. So we assume it matches every row.
5366 ** Advance the RHS iterator to find the next row visited. */
5367 fts3EvalNextRow(pCsr, pRight, pRc);
5368 pExpr->iDocid = pRight->iDocid;
5369 pExpr->bEof = pRight->bEof;
5370 }else if( pRight->bDeferred ){
5371 /* RHS is entirely deferred. So we assume it matches every row.
5372 ** Advance the LHS iterator to find the next row visited. */
5373 fts3EvalNextRow(pCsr, pLeft, pRc);
5374 pExpr->iDocid = pLeft->iDocid;
5375 pExpr->bEof = pLeft->bEof;
5376 }else{
5377 /* Neither the RHS or LHS are deferred. */
5378 fts3EvalNextRow(pCsr, pLeft, pRc);
5379 fts3EvalNextRow(pCsr, pRight, pRc);
5380 while( !pLeft->bEof && !pRight->bEof && *pRc==SQLITE_OK ){
5381 sqlite3_int64 iDiff = DOCID_CMP(pLeft->iDocid, pRight->iDocid);
5382 if( iDiff==0 ) break;
5383 if( iDiff<0 ){
5384 fts3EvalNextRow(pCsr, pLeft, pRc);
5385 }else{
5386 fts3EvalNextRow(pCsr, pRight, pRc);
5387 }
5388 }
5389 pExpr->iDocid = pLeft->iDocid;
5390 pExpr->bEof = (pLeft->bEof || pRight->bEof);
5391 if( pExpr->eType==FTSQUERY_NEAR && pExpr->bEof ){
5392 assert( pRight->eType==FTSQUERY_PHRASE );
5393 if( pRight->pPhrase->doclist.aAll ){
5394 Fts3Doclist *pDl = &pRight->pPhrase->doclist;
5395 while( *pRc==SQLITE_OK && pRight->bEof==0 ){
5396 memset(pDl->pList, 0, pDl->nList);
5397 fts3EvalNextRow(pCsr, pRight, pRc);
5398 }
5399 }
5400 if( pLeft->pPhrase && pLeft->pPhrase->doclist.aAll ){
5401 Fts3Doclist *pDl = &pLeft->pPhrase->doclist;
5402 while( *pRc==SQLITE_OK && pLeft->bEof==0 ){
5403 memset(pDl->pList, 0, pDl->nList);
5404 fts3EvalNextRow(pCsr, pLeft, pRc);
5405 }
5406 }
5407 pRight->bEof = pLeft->bEof = 1;
5408 }
5409 }
5410 break;
5411 }
5412
5413 case FTSQUERY_OR: {
5414 Fts3Expr *pLeft = pExpr->pLeft;
5415 Fts3Expr *pRight = pExpr->pRight;
5416 sqlite3_int64 iCmp = DOCID_CMP(pLeft->iDocid, pRight->iDocid);
5417
5418 assert_fts3_nc( pLeft->bStart || pLeft->iDocid==pRight->iDocid );
5419 assert_fts3_nc( pRight->bStart || pLeft->iDocid==pRight->iDocid );
5420
5421 if( pRight->bEof || (pLeft->bEof==0 && iCmp<0) ){
5422 fts3EvalNextRow(pCsr, pLeft, pRc);
5423 }else if( pLeft->bEof || iCmp>0 ){
5424 fts3EvalNextRow(pCsr, pRight, pRc);
5425 }else{
5426 fts3EvalNextRow(pCsr, pLeft, pRc);
5427 fts3EvalNextRow(pCsr, pRight, pRc);
5428 }
5429
5430 pExpr->bEof = (pLeft->bEof && pRight->bEof);
5431 iCmp = DOCID_CMP(pLeft->iDocid, pRight->iDocid);
5432 if( pRight->bEof || (pLeft->bEof==0 && iCmp<0) ){
5433 pExpr->iDocid = pLeft->iDocid;
5434 }else{
5435 pExpr->iDocid = pRight->iDocid;
5436 }
5437
5438 break;
5439 }
5440
5441 case FTSQUERY_NOT: {
5442 Fts3Expr *pLeft = pExpr->pLeft;
5443 Fts3Expr *pRight = pExpr->pRight;
5444
5445 if( pRight->bStart==0 ){
5446 fts3EvalNextRow(pCsr, pRight, pRc);
5447 assert( *pRc!=SQLITE_OK || pRight->bStart );
5448 }
5449
5450 fts3EvalNextRow(pCsr, pLeft, pRc);
5451 if( pLeft->bEof==0 ){
5452 while( !*pRc
5453 && !pRight->bEof
5454 && DOCID_CMP(pLeft->iDocid, pRight->iDocid)>0
5455 ){
5456 fts3EvalNextRow(pCsr, pRight, pRc);
5457 }
5458 }
5459 pExpr->iDocid = pLeft->iDocid;
5460 pExpr->bEof = pLeft->bEof;
5461 break;
5462 }
5463
5464 default: {
5465 Fts3Phrase *pPhrase = pExpr->pPhrase;
5466 fts3EvalInvalidatePoslist(pPhrase);
5467 *pRc = fts3EvalPhraseNext(pCsr, pPhrase, &pExpr->bEof);
5468 pExpr->iDocid = pPhrase->doclist.iDocid;
5469 break;
5470 }
5471 }
5472 }
5473 }
5474
5475 /*
5476 ** If *pRc is not SQLITE_OK, or if pExpr is not the root node of a NEAR
5477 ** cluster, then this function returns 1 immediately.
5478 **
5479 ** Otherwise, it checks if the current row really does match the NEAR
5480 ** expression, using the data currently stored in the position lists
5481 ** (Fts3Expr->pPhrase.doclist.pList/nList) for each phrase in the expression.
5482 **
5483 ** If the current row is a match, the position list associated with each
5484 ** phrase in the NEAR expression is edited in place to contain only those
5485 ** phrase instances sufficiently close to their peers to satisfy all NEAR
5486 ** constraints. In this case it returns 1. If the NEAR expression does not
5487 ** match the current row, 0 is returned. The position lists may or may not
5488 ** be edited if 0 is returned.
5489 */
5490 static int fts3EvalNearTest(Fts3Expr *pExpr, int *pRc){
5491 int res = 1;
5492
5493 /* The following block runs if pExpr is the root of a NEAR query.
5494 ** For example, the query:
5495 **
5496 ** "w" NEAR "x" NEAR "y" NEAR "z"
5497 **
5498 ** which is represented in tree form as:
5499 **
5500 ** |
5501 ** +--NEAR--+ <-- root of NEAR query
5502 ** | |
5503 ** +--NEAR--+ "z"
5504 ** | |
5505 ** +--NEAR--+ "y"
5506 ** | |
5507 ** "w" "x"
5508 **
5509 ** The right-hand child of a NEAR node is always a phrase. The
5510 ** left-hand child may be either a phrase or a NEAR node. There are
5511 ** no exceptions to this - it's the way the parser in fts3_expr.c works.
5512 */
5513 if( *pRc==SQLITE_OK
5514 && pExpr->eType==FTSQUERY_NEAR
5515 && (pExpr->pParent==0 || pExpr->pParent->eType!=FTSQUERY_NEAR)
5516 ){
5517 Fts3Expr *p;
5518 sqlite3_int64 nTmp = 0; /* Bytes of temp space */
5519 char *aTmp; /* Temp space for PoslistNearMerge() */
5520
5521 /* Allocate temporary working space. */
5522 for(p=pExpr; p->pLeft; p=p->pLeft){
5523 assert( p->pRight->pPhrase->doclist.nList>0 );
5524 nTmp += p->pRight->pPhrase->doclist.nList;
5525 }
5526 nTmp += p->pPhrase->doclist.nList;
5527 aTmp = sqlite3_malloc64(nTmp*2 + FTS3_VARINT_MAX);
5528 if( !aTmp ){
5529 *pRc = SQLITE_NOMEM;
5530 res = 0;
5531 }else{
5532 char *aPoslist = p->pPhrase->doclist.pList;
5533 int nToken = p->pPhrase->nToken;
5534
5535 for(p=p->pParent;res && p && p->eType==FTSQUERY_NEAR; p=p->pParent){
5536 Fts3Phrase *pPhrase = p->pRight->pPhrase;
5537 int nNear = p->nNear;
5538 res = fts3EvalNearTrim(nNear, aTmp, &aPoslist, &nToken, pPhrase);
5539 }
5540
5541 aPoslist = pExpr->pRight->pPhrase->doclist.pList;
5542 nToken = pExpr->pRight->pPhrase->nToken;
5543 for(p=pExpr->pLeft; p && res; p=p->pLeft){
5544 int nNear;
5545 Fts3Phrase *pPhrase;
5546 assert( p->pParent && p->pParent->pLeft==p );
5547 nNear = p->pParent->nNear;
5548 pPhrase = (
5549 p->eType==FTSQUERY_NEAR ? p->pRight->pPhrase : p->pPhrase
5550 );
5551 res = fts3EvalNearTrim(nNear, aTmp, &aPoslist, &nToken, pPhrase);
5552 }
5553 }
5554
5555 sqlite3_free(aTmp);
5556 }
5557
5558 return res;
5559 }
5560
5561 /*
5562 ** This function is a helper function for sqlite3Fts3EvalTestDeferred().
5563 ** Assuming no error occurs or has occurred, It returns non-zero if the
5564 ** expression passed as the second argument matches the row that pCsr
5565 ** currently points to, or zero if it does not.
5566 **
5567 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.
5568 ** If an error occurs during execution of this function, *pRc is set to
5569 ** the appropriate SQLite error code. In this case the returned value is
5570 ** undefined.
5571 */
5572 static int fts3EvalTestExpr(
5573 Fts3Cursor *pCsr, /* FTS cursor handle */
5574 Fts3Expr *pExpr, /* Expr to test. May or may not be root. */
5575 int *pRc /* IN/OUT: Error code */
5576 ){
5577 int bHit = 1; /* Return value */
5578 if( *pRc==SQLITE_OK ){
5579 switch( pExpr->eType ){
5580 case FTSQUERY_NEAR:
5581 case FTSQUERY_AND:
5582 bHit = (
5583 fts3EvalTestExpr(pCsr, pExpr->pLeft, pRc)
5584 && fts3EvalTestExpr(pCsr, pExpr->pRight, pRc)
5585 && fts3EvalNearTest(pExpr, pRc)
5586 );
5587
5588 /* If the NEAR expression does not match any rows, zero the doclist for
5589 ** all phrases involved in the NEAR. This is because the snippet(),
5590 ** offsets() and matchinfo() functions are not supposed to recognize
5591 ** any instances of phrases that are part of unmatched NEAR queries.
5592 ** For example if this expression:
5593 **
5594 ** ... MATCH 'a OR (b NEAR c)'
5595 **
5596 ** is matched against a row containing:
5597 **
5598 ** 'a b d e'
5599 **
5600 ** then any snippet() should ony highlight the "a" term, not the "b"
5601 ** (as "b" is part of a non-matching NEAR clause).
5602 */
5603 if( bHit==0
5604 && pExpr->eType==FTSQUERY_NEAR
5605 && (pExpr->pParent==0 || pExpr->pParent->eType!=FTSQUERY_NEAR)
5606 ){
5607 Fts3Expr *p;
5608 for(p=pExpr; p->pPhrase==0; p=p->pLeft){
5609 if( p->pRight->iDocid==pCsr->iPrevId ){
5610 fts3EvalInvalidatePoslist(p->pRight->pPhrase);
5611 }
5612 }
5613 if( p->iDocid==pCsr->iPrevId ){
5614 fts3EvalInvalidatePoslist(p->pPhrase);
5615 }
5616 }
5617
5618 break;
5619
5620 case FTSQUERY_OR: {
5621 int bHit1 = fts3EvalTestExpr(pCsr, pExpr->pLeft, pRc);
5622 int bHit2 = fts3EvalTestExpr(pCsr, pExpr->pRight, pRc);
5623 bHit = bHit1 || bHit2;
5624 break;
5625 }
5626
5627 case FTSQUERY_NOT:
5628 bHit = (
5629 fts3EvalTestExpr(pCsr, pExpr->pLeft, pRc)
5630 && !fts3EvalTestExpr(pCsr, pExpr->pRight, pRc)
5631 );
5632 break;
5633
5634 default: {
5635 #ifndef SQLITE_DISABLE_FTS4_DEFERRED
5636 if( pCsr->pDeferred && (pExpr->bDeferred || (
5637 pExpr->iDocid==pCsr->iPrevId && pExpr->pPhrase->doclist.pList
5638 ))){
5639 Fts3Phrase *pPhrase = pExpr->pPhrase;
5640 if( pExpr->bDeferred ){
5641 fts3EvalInvalidatePoslist(pPhrase);
5642 }
5643 *pRc = fts3EvalDeferredPhrase(pCsr, pPhrase);
5644 bHit = (pPhrase->doclist.pList!=0);
5645 pExpr->iDocid = pCsr->iPrevId;
5646 }else
5647 #endif
5648 {
5649 bHit = (
5650 pExpr->bEof==0 && pExpr->iDocid==pCsr->iPrevId
5651 && pExpr->pPhrase->doclist.nList>0
5652 );
5653 }
5654 break;
5655 }
5656 }
5657 }
5658 return bHit;
5659 }
5660
5661 /*
5662 ** This function is called as the second part of each xNext operation when
5663 ** iterating through the results of a full-text query. At this point the
5664 ** cursor points to a row that matches the query expression, with the
5665 ** following caveats:
5666 **
5667 ** * Up until this point, "NEAR" operators in the expression have been
5668 ** treated as "AND".
5669 **
5670 ** * Deferred tokens have not yet been considered.
5671 **
5672 ** If *pRc is not SQLITE_OK when this function is called, it immediately
5673 ** returns 0. Otherwise, it tests whether or not after considering NEAR
5674 ** operators and deferred tokens the current row is still a match for the
5675 ** expression. It returns 1 if both of the following are true:
5676 **
5677 ** 1. *pRc is SQLITE_OK when this function returns, and
5678 **
5679 ** 2. After scanning the current FTS table row for the deferred tokens,
5680 ** it is determined that the row does *not* match the query.
5681 **
5682 ** Or, if no error occurs and it seems the current row does match the FTS
5683 ** query, return 0.
5684 */
5685 int sqlite3Fts3EvalTestDeferred(Fts3Cursor *pCsr, int *pRc){
5686 int rc = *pRc;
5687 int bMiss = 0;
5688 if( rc==SQLITE_OK ){
5689
5690 /* If there are one or more deferred tokens, load the current row into
5691 ** memory and scan it to determine the position list for each deferred
5692 ** token. Then, see if this row is really a match, considering deferred
5693 ** tokens and NEAR operators (neither of which were taken into account
5694 ** earlier, by fts3EvalNextRow()).
5695 */
5696 if( pCsr->pDeferred ){
5697 rc = fts3CursorSeek(0, pCsr);
5698 if( rc==SQLITE_OK ){
5699 rc = sqlite3Fts3CacheDeferredDoclists(pCsr);
5700 }
5701 }
5702 bMiss = (0==fts3EvalTestExpr(pCsr, pCsr->pExpr, &rc));
5703
5704 /* Free the position-lists accumulated for each deferred token above. */
5705 sqlite3Fts3FreeDeferredDoclists(pCsr);
5706 *pRc = rc;
5707 }
5708 return (rc==SQLITE_OK && bMiss);
5709 }
5710
5711 /*
5712 ** Advance to the next document that matches the FTS expression in
5713 ** Fts3Cursor.pExpr.
5714 */
5715 static int fts3EvalNext(Fts3Cursor *pCsr){
5716 int rc = SQLITE_OK; /* Return Code */
5717 Fts3Expr *pExpr = pCsr->pExpr;
5718 assert( pCsr->isEof==0 );
5719 if( pExpr==0 ){
5720 pCsr->isEof = 1;
5721 }else{
5722 do {
5723 if( pCsr->isRequireSeek==0 ){
5724 sqlite3_reset(pCsr->pStmt);
5725 }
5726 assert( sqlite3_data_count(pCsr->pStmt)==0 );
5727 fts3EvalNextRow(pCsr, pExpr, &rc);
5728 pCsr->isEof = pExpr->bEof;
5729 pCsr->isRequireSeek = 1;
5730 pCsr->isMatchinfoNeeded = 1;
5731 pCsr->iPrevId = pExpr->iDocid;
5732 }while( pCsr->isEof==0 && sqlite3Fts3EvalTestDeferred(pCsr, &rc) );
5733 }
5734
5735 /* Check if the cursor is past the end of the docid range specified
5736 ** by Fts3Cursor.iMinDocid/iMaxDocid. If so, set the EOF flag. */
5737 if( rc==SQLITE_OK && (
5738 (pCsr->bDesc==0 && pCsr->iPrevId>pCsr->iMaxDocid)
5739 || (pCsr->bDesc!=0 && pCsr->iPrevId<pCsr->iMinDocid)
5740 )){
5741 pCsr->isEof = 1;
5742 }
5743
5744 return rc;
5745 }
5746
5747 /*
5748 ** Restart iteration for expression pExpr so that the next call to
5749 ** fts3EvalNext() visits the first row. Do not allow incremental
5750 ** loading or merging of phrase doclists for this iteration.
5751 **
5752 ** If *pRc is other than SQLITE_OK when this function is called, it is
5753 ** a no-op. If an error occurs within this function, *pRc is set to an
5754 ** SQLite error code before returning.
5755 */
5756 static void fts3EvalRestart(
5757 Fts3Cursor *pCsr,
5758 Fts3Expr *pExpr,
5759 int *pRc
5760 ){
5761 if( pExpr && *pRc==SQLITE_OK ){
5762 Fts3Phrase *pPhrase = pExpr->pPhrase;
5763
5764 if( pPhrase ){
5765 fts3EvalInvalidatePoslist(pPhrase);
5766 if( pPhrase->bIncr ){
5767 int i;
5768 for(i=0; i<pPhrase->nToken; i++){
5769 Fts3PhraseToken *pToken = &pPhrase->aToken[i];
5770 assert( pToken->pDeferred==0 );
5771 if( pToken->pSegcsr ){
5772 sqlite3Fts3MsrIncrRestart(pToken->pSegcsr);
5773 }
5774 }
5775 *pRc = fts3EvalPhraseStart(pCsr, 0, pPhrase);
5776 }
5777 pPhrase->doclist.pNextDocid = 0;
5778 pPhrase->doclist.iDocid = 0;
5779 pPhrase->pOrPoslist = 0;
5780 }
5781
5782 pExpr->iDocid = 0;
5783 pExpr->bEof = 0;
5784 pExpr->bStart = 0;
5785
5786 fts3EvalRestart(pCsr, pExpr->pLeft, pRc);
5787 fts3EvalRestart(pCsr, pExpr->pRight, pRc);
5788 }
5789 }
5790
5791 /*
5792 ** Expression node pExpr is an MSR phrase. This function restarts pExpr
5793 ** so that it is a regular phrase query, not an MSR. SQLITE_OK is returned
5794 ** if successful, or an SQLite error code otherwise.
5795 */
5796 int sqlite3Fts3MsrCancel(Fts3Cursor *pCsr, Fts3Expr *pExpr){
5797 int rc = SQLITE_OK;
5798 if( pExpr->bEof==0 ){
5799 i64 iDocid = pExpr->iDocid;
5800 fts3EvalRestart(pCsr, pExpr, &rc);
5801 while( rc==SQLITE_OK && pExpr->iDocid!=iDocid ){
5802 fts3EvalNextRow(pCsr, pExpr, &rc);
5803 if( pExpr->bEof ) rc = FTS_CORRUPT_VTAB;
5804 }
5805 }
5806 return rc;
5807 }
5808
5809 /*
5810 ** After allocating the Fts3Expr.aMI[] array for each phrase in the
5811 ** expression rooted at pExpr, the cursor iterates through all rows matched
5812 ** by pExpr, calling this function for each row. This function increments
5813 ** the values in Fts3Expr.aMI[] according to the position-list currently
5814 ** found in Fts3Expr.pPhrase->doclist.pList for each of the phrase
5815 ** expression nodes.
5816 */
5817 static void fts3EvalUpdateCounts(Fts3Expr *pExpr, int nCol){
5818 if( pExpr ){
5819 Fts3Phrase *pPhrase = pExpr->pPhrase;
5820 if( pPhrase && pPhrase->doclist.pList ){
5821 int iCol = 0;
5822 char *p = pPhrase->doclist.pList;
5823
5824 do{
5825 u8 c = 0;
5826 int iCnt = 0;
5827 while( 0xFE & (*p | c) ){
5828 if( (c&0x80)==0 ) iCnt++;
5829 c = *p++ & 0x80;
5830 }
5831
5832 /* aMI[iCol*3 + 1] = Number of occurrences
5833 ** aMI[iCol*3 + 2] = Number of rows containing at least one instance
5834 */
5835 pExpr->aMI[iCol*3 + 1] += iCnt;
5836 pExpr->aMI[iCol*3 + 2] += (iCnt>0);
5837 if( *p==0x00 ) break;
5838 p++;
5839 p += fts3GetVarint32(p, &iCol);
5840 }while( iCol<nCol );
5841 }
5842
5843 fts3EvalUpdateCounts(pExpr->pLeft, nCol);
5844 fts3EvalUpdateCounts(pExpr->pRight, nCol);
5845 }
5846 }
5847
5848 /*
5849 ** This is an sqlite3Fts3ExprIterate() callback. If the Fts3Expr.aMI[] array
5850 ** has not yet been allocated, allocate and zero it. Otherwise, just zero
5851 ** it.
5852 */
5853 static int fts3AllocateMSI(Fts3Expr *pExpr, int iPhrase, void *pCtx){
5854 Fts3Table *pTab = (Fts3Table*)pCtx;
5855 UNUSED_PARAMETER(iPhrase);
5856 if( pExpr->aMI==0 ){
5857 pExpr->aMI = (u32 *)sqlite3_malloc64(pTab->nColumn * 3 * sizeof(u32));
5858 if( pExpr->aMI==0 ) return SQLITE_NOMEM;
5859 }
5860 memset(pExpr->aMI, 0, pTab->nColumn * 3 * sizeof(u32));
5861 return SQLITE_OK;
5862 }
5863
5864 /*
5865 ** Expression pExpr must be of type FTSQUERY_PHRASE.
5866 **
5867 ** If it is not already allocated and populated, this function allocates and
5868 ** populates the Fts3Expr.aMI[] array for expression pExpr. If pExpr is part
5869 ** of a NEAR expression, then it also allocates and populates the same array
5870 ** for all other phrases that are part of the NEAR expression.
5871 **
5872 ** SQLITE_OK is returned if the aMI[] array is successfully allocated and
5873 ** populated. Otherwise, if an error occurs, an SQLite error code is returned.
5874 */
5875 static int fts3EvalGatherStats(
5876 Fts3Cursor *pCsr, /* Cursor object */
5877 Fts3Expr *pExpr /* FTSQUERY_PHRASE expression */
5878 ){
5879 int rc = SQLITE_OK; /* Return code */
5880
5881 assert( pExpr->eType==FTSQUERY_PHRASE );
5882 if( pExpr->aMI==0 ){
5883 Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
5884 Fts3Expr *pRoot; /* Root of NEAR expression */
5885
5886 sqlite3_int64 iPrevId = pCsr->iPrevId;
5887 sqlite3_int64 iDocid;
5888 u8 bEof;
5889
5890 /* Find the root of the NEAR expression */
5891 pRoot = pExpr;
5892 while( pRoot->pParent
5893 && (pRoot->pParent->eType==FTSQUERY_NEAR || pRoot->bDeferred)
5894 ){
5895 pRoot = pRoot->pParent;
5896 }
5897 iDocid = pRoot->iDocid;
5898 bEof = pRoot->bEof;
5899 assert( pRoot->bStart );
5900
5901 /* Allocate space for the aMSI[] array of each FTSQUERY_PHRASE node */
5902 rc = sqlite3Fts3ExprIterate(pRoot, fts3AllocateMSI, (void*)pTab);
5903 if( rc!=SQLITE_OK ) return rc;
5904 fts3EvalRestart(pCsr, pRoot, &rc);
5905
5906 while( pCsr->isEof==0 && rc==SQLITE_OK ){
5907
5908 do {
5909 /* Ensure the %_content statement is reset. */
5910 if( pCsr->isRequireSeek==0 ) sqlite3_reset(pCsr->pStmt);
5911 assert( sqlite3_data_count(pCsr->pStmt)==0 );
5912
5913 /* Advance to the next document */
5914 fts3EvalNextRow(pCsr, pRoot, &rc);
5915 pCsr->isEof = pRoot->bEof;
5916 pCsr->isRequireSeek = 1;
5917 pCsr->isMatchinfoNeeded = 1;
5918 pCsr->iPrevId = pRoot->iDocid;
5919 }while( pCsr->isEof==0
5920 && pRoot->eType==FTSQUERY_NEAR
5921 && sqlite3Fts3EvalTestDeferred(pCsr, &rc)
5922 );
5923
5924 if( rc==SQLITE_OK && pCsr->isEof==0 ){
5925 fts3EvalUpdateCounts(pRoot, pTab->nColumn);
5926 }
5927 }
5928
5929 pCsr->isEof = 0;
5930 pCsr->iPrevId = iPrevId;
5931
5932 if( bEof ){
5933 pRoot->bEof = bEof;
5934 }else{
5935 /* Caution: pRoot may iterate through docids in ascending or descending
5936 ** order. For this reason, even though it seems more defensive, the
5937 ** do loop can not be written:
5938 **
5939 ** do {...} while( pRoot->iDocid<iDocid && rc==SQLITE_OK );
5940 */
5941 fts3EvalRestart(pCsr, pRoot, &rc);
5942 do {
5943 fts3EvalNextRow(pCsr, pRoot, &rc);
5944 assert_fts3_nc( pRoot->bEof==0 );
5945 if( pRoot->bEof ) rc = FTS_CORRUPT_VTAB;
5946 }while( pRoot->iDocid!=iDocid && rc==SQLITE_OK );
5947 }
5948 }
5949 return rc;
5950 }
5951
5952 /*
5953 ** This function is used by the matchinfo() module to query a phrase
5954 ** expression node for the following information:
5955 **
5956 ** 1. The total number of occurrences of the phrase in each column of
5957 ** the FTS table (considering all rows), and
5958 **
5959 ** 2. For each column, the number of rows in the table for which the
5960 ** column contains at least one instance of the phrase.
5961 **
5962 ** If no error occurs, SQLITE_OK is returned and the values for each column
5963 ** written into the array aiOut as follows:
5964 **
5965 ** aiOut[iCol*3 + 1] = Number of occurrences
5966 ** aiOut[iCol*3 + 2] = Number of rows containing at least one instance
5967 **
5968 ** Caveats:
5969 **
5970 ** * If a phrase consists entirely of deferred tokens, then all output
5971 ** values are set to the number of documents in the table. In other
5972 ** words we assume that very common tokens occur exactly once in each
5973 ** column of each row of the table.
5974 **
5975 ** * If a phrase contains some deferred tokens (and some non-deferred
5976 ** tokens), count the potential occurrence identified by considering
5977 ** the non-deferred tokens instead of actual phrase occurrences.
5978 **
5979 ** * If the phrase is part of a NEAR expression, then only phrase instances
5980 ** that meet the NEAR constraint are included in the counts.
5981 */
5982 int sqlite3Fts3EvalPhraseStats(
5983 Fts3Cursor *pCsr, /* FTS cursor handle */
5984 Fts3Expr *pExpr, /* Phrase expression */
5985 u32 *aiOut /* Array to write results into (see above) */
5986 ){
5987 Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
5988 int rc = SQLITE_OK;
5989 int iCol;
5990
5991 if( pExpr->bDeferred && pExpr->pParent->eType!=FTSQUERY_NEAR ){
5992 assert( pCsr->nDoc>0 );
5993 for(iCol=0; iCol<pTab->nColumn; iCol++){
5994 aiOut[iCol*3 + 1] = (u32)pCsr->nDoc;
5995 aiOut[iCol*3 + 2] = (u32)pCsr->nDoc;
5996 }
5997 }else{
5998 rc = fts3EvalGatherStats(pCsr, pExpr);
5999 if( rc==SQLITE_OK ){
6000 assert( pExpr->aMI );
6001 for(iCol=0; iCol<pTab->nColumn; iCol++){
6002 aiOut[iCol*3 + 1] = pExpr->aMI[iCol*3 + 1];
6003 aiOut[iCol*3 + 2] = pExpr->aMI[iCol*3 + 2];
6004 }
6005 }
6006 }
6007
6008 return rc;
6009 }
6010
6011 /*
6012 ** The expression pExpr passed as the second argument to this function
6013 ** must be of type FTSQUERY_PHRASE.
6014 **
6015 ** The returned value is either NULL or a pointer to a buffer containing
6016 ** a position-list indicating the occurrences of the phrase in column iCol
6017 ** of the current row.
6018 **
6019 ** More specifically, the returned buffer contains 1 varint for each
6020 ** occurrence of the phrase in the column, stored using the normal (delta+2)
6021 ** compression and is terminated by either an 0x01 or 0x00 byte. For example,
6022 ** if the requested column contains "a b X c d X X" and the position-list
6023 ** for 'X' is requested, the buffer returned may contain:
6024 **
6025 ** 0x04 0x05 0x03 0x01 or 0x04 0x05 0x03 0x00
6026 **
6027 ** This function works regardless of whether or not the phrase is deferred,
6028 ** incremental, or neither.
6029 */
6030 int sqlite3Fts3EvalPhrasePoslist(
6031 Fts3Cursor *pCsr, /* FTS3 cursor object */
6032 Fts3Expr *pExpr, /* Phrase to return doclist for */
6033 int iCol, /* Column to return position list for */
6034 char **ppOut /* OUT: Pointer to position list */
6035 ){
6036 Fts3Phrase *pPhrase = pExpr->pPhrase;
6037 Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
6038 char *pIter;
6039 int iThis;
6040 sqlite3_int64 iDocid;
6041
6042 /* If this phrase is applies specifically to some column other than
6043 ** column iCol, return a NULL pointer. */
6044 *ppOut = 0;
6045 assert( iCol>=0 && iCol<pTab->nColumn );
6046 if( (pPhrase->iColumn<pTab->nColumn && pPhrase->iColumn!=iCol) ){
6047 return SQLITE_OK;
6048 }
6049
6050 iDocid = pExpr->iDocid;
6051 pIter = pPhrase->doclist.pList;
6052 if( iDocid!=pCsr->iPrevId || pExpr->bEof ){
6053 int rc = SQLITE_OK;
6054 int bDescDoclist = pTab->bDescIdx; /* For DOCID_CMP macro */
6055 int bOr = 0;
6056 u8 bTreeEof = 0;
6057 Fts3Expr *p; /* Used to iterate from pExpr to root */
6058 Fts3Expr *pNear; /* Most senior NEAR ancestor (or pExpr) */
6059 Fts3Expr *pRun; /* Closest non-deferred ancestor of pNear */
6060 int bMatch;
6061
6062 /* Check if this phrase descends from an OR expression node. If not,
6063 ** return NULL. Otherwise, the entry that corresponds to docid
6064 ** pCsr->iPrevId may lie earlier in the doclist buffer. Or, if the
6065 ** tree that the node is part of has been marked as EOF, but the node
6066 ** itself is not EOF, then it may point to an earlier entry. */
6067 pNear = pExpr;
6068 for(p=pExpr->pParent; p; p=p->pParent){
6069 if( p->eType==FTSQUERY_OR ) bOr = 1;
6070 if( p->eType==FTSQUERY_NEAR ) pNear = p;
6071 if( p->bEof ) bTreeEof = 1;
6072 }
6073 if( bOr==0 ) return SQLITE_OK;
6074 pRun = pNear;
6075 while( pRun->bDeferred ){
6076 assert( pRun->pParent );
6077 pRun = pRun->pParent;
6078 }
6079
6080 /* This is the descendent of an OR node. In this case we cannot use
6081 ** an incremental phrase. Load the entire doclist for the phrase
6082 ** into memory in this case. */
6083 if( pPhrase->bIncr ){
6084 int bEofSave = pRun->bEof;
6085 fts3EvalRestart(pCsr, pRun, &rc);
6086 while( rc==SQLITE_OK && !pRun->bEof ){
6087 fts3EvalNextRow(pCsr, pRun, &rc);
6088 if( bEofSave==0 && pRun->iDocid==iDocid ) break;
6089 }
6090 assert( rc!=SQLITE_OK || pPhrase->bIncr==0 );
6091 if( rc==SQLITE_OK && pRun->bEof!=bEofSave ){
6092 rc = FTS_CORRUPT_VTAB;
6093 }
6094 }
6095 if( bTreeEof ){
6096 while( rc==SQLITE_OK && !pRun->bEof ){
6097 fts3EvalNextRow(pCsr, pRun, &rc);
6098 }
6099 }
6100 if( rc!=SQLITE_OK ) return rc;
6101
6102 bMatch = 1;
6103 for(p=pNear; p; p=p->pLeft){
6104 u8 bEof = 0;
6105 Fts3Expr *pTest = p;
6106 Fts3Phrase *pPh;
6107 assert( pTest->eType==FTSQUERY_NEAR || pTest->eType==FTSQUERY_PHRASE );
6108 if( pTest->eType==FTSQUERY_NEAR ) pTest = pTest->pRight;
6109 assert( pTest->eType==FTSQUERY_PHRASE );
6110 pPh = pTest->pPhrase;
6111
6112 pIter = pPh->pOrPoslist;
6113 iDocid = pPh->iOrDocid;
6114 if( pCsr->bDesc==bDescDoclist ){
6115 bEof = !pPh->doclist.nAll ||
6116 (pIter >= (pPh->doclist.aAll + pPh->doclist.nAll));
6117 while( (pIter==0 || DOCID_CMP(iDocid, pCsr->iPrevId)<0 ) && bEof==0 ){
6118 sqlite3Fts3DoclistNext(
6119 bDescDoclist, pPh->doclist.aAll, pPh->doclist.nAll,
6120 &pIter, &iDocid, &bEof
6121 );
6122 }
6123 }else{
6124 bEof = !pPh->doclist.nAll || (pIter && pIter<=pPh->doclist.aAll);
6125 while( (pIter==0 || DOCID_CMP(iDocid, pCsr->iPrevId)>0 ) && bEof==0 ){
6126 int dummy;
6127 sqlite3Fts3DoclistPrev(
6128 bDescDoclist, pPh->doclist.aAll, pPh->doclist.nAll,
6129 &pIter, &iDocid, &dummy, &bEof
6130 );
6131 }
6132 }
6133 pPh->pOrPoslist = pIter;
6134 pPh->iOrDocid = iDocid;
6135 if( bEof || iDocid!=pCsr->iPrevId ) bMatch = 0;
6136 }
6137
6138 if( bMatch ){
6139 pIter = pPhrase->pOrPoslist;
6140 }else{
6141 pIter = 0;
6142 }
6143 }
6144 if( pIter==0 ) return SQLITE_OK;
6145
6146 if( *pIter==0x01 ){
6147 pIter++;
6148 pIter += fts3GetVarint32(pIter, &iThis);
6149 }else{
6150 iThis = 0;
6151 }
6152 while( iThis<iCol ){
6153 fts3ColumnlistCopy(0, &pIter);
6154 if( *pIter==0x00 ) return SQLITE_OK;
6155 pIter++;
6156 pIter += fts3GetVarint32(pIter, &iThis);
6157 }
6158 if( *pIter==0x00 ){
6159 pIter = 0;
6160 }
6161
6162 *ppOut = ((iCol==iThis)?pIter:0);
6163 return SQLITE_OK;
6164 }
6165
6166 /*
6167 ** Free all components of the Fts3Phrase structure that were allocated by
6168 ** the eval module. Specifically, this means to free:
6169 **
6170 ** * the contents of pPhrase->doclist, and
6171 ** * any Fts3MultiSegReader objects held by phrase tokens.
6172 */
6173 void sqlite3Fts3EvalPhraseCleanup(Fts3Phrase *pPhrase){
6174 if( pPhrase ){
6175 int i;
6176 sqlite3_free(pPhrase->doclist.aAll);
6177 fts3EvalInvalidatePoslist(pPhrase);
6178 memset(&pPhrase->doclist, 0, sizeof(Fts3Doclist));
6179 for(i=0; i<pPhrase->nToken; i++){
6180 fts3SegReaderCursorFree(pPhrase->aToken[i].pSegcsr);
6181 pPhrase->aToken[i].pSegcsr = 0;
6182 }
6183 }
6184 }
6185
6186
6187 /*
6188 ** Return SQLITE_CORRUPT_VTAB.
6189 */
6190 #ifdef SQLITE_DEBUG
6191 int sqlite3Fts3Corrupt(){
6192 return SQLITE_CORRUPT_VTAB;
6193 }
6194 #endif
6195
6196 #if !defined(SQLITE_CORE)
6197 /*
6198 ** Initialize API pointer table, if required.
6199 */
6200 #ifdef _WIN32
6201 __declspec(dllexport)
6202 #endif
6203 int sqlite3_fts3_init(
6204 sqlite3 *db,
6205 char **pzErrMsg,
6206 const sqlite3_api_routines *pApi
6207 ){
6208 SQLITE_EXTENSION_INIT2(pApi)
6209 return sqlite3Fts3Init(db);
6210 }
6211 #endif
6212
6213 #endif