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