1 /* fts2 has a design flaw which can lead to database corruption (see 2 ** below). It is recommended not to use it any longer, instead use 3 ** fts3 (or higher). If you believe that your use of fts2 is safe, 4 ** add -DSQLITE_ENABLE_BROKEN_FTS2=1 to your CFLAGS. 5 */ 6 #if (!defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS2)) \ 7 && !defined(SQLITE_ENABLE_BROKEN_FTS2) 8 #error fts2 has a design flaw and has been deprecated. 9 #endif 10 /* The flaw is that fts2 uses the content table's unaliased rowid as 11 ** the unique docid. fts2 embeds the rowid in the index it builds, 12 ** and expects the rowid to not change. The SQLite VACUUM operation 13 ** will renumber such rowids, thereby breaking fts2. If you are using 14 ** fts2 in a system which has disabled VACUUM, then you can continue 15 ** to use it safely. Note that PRAGMA auto_vacuum does NOT disable 16 ** VACUUM, though systems using auto_vacuum are unlikely to invoke 17 ** VACUUM. 18 ** 19 ** Unlike fts1, which is safe across VACUUM if you never delete 20 ** documents, fts2 has a second exposure to this flaw, in the segments 21 ** table. So fts2 should be considered unsafe across VACUUM in all 22 ** cases. 23 */ 24 25 /* 26 ** 2006 Oct 10 27 ** 28 ** The author disclaims copyright to this source code. In place of 29 ** a legal notice, here is a blessing: 30 ** 31 ** May you do good and not evil. 32 ** May you find forgiveness for yourself and forgive others. 33 ** May you share freely, never taking more than you give. 34 ** 35 ****************************************************************************** 36 ** 37 ** This is an SQLite module implementing full-text search. 38 */ 39 40 /* TODO(shess): To make it easier to spot changes without groveling 41 ** through changelogs, I've defined GEARS_FTS2_CHANGES to call them 42 ** out, and I will document them here. On imports, these changes 43 ** should be reviewed to make sure they are still present, or are 44 ** dropped as appropriate. 45 ** 46 ** SQLite core adds the custom function fts2_tokenizer() to be used 47 ** for defining new tokenizers. The second parameter is a vtable 48 ** pointer encoded as a blob. Obviously this cannot be exposed to 49 ** Gears callers for security reasons. It could be suppressed in the 50 ** authorizer, but for now I have simply commented the definition out. 51 */ 52 #define GEARS_FTS2_CHANGES 1 53 54 /* 55 ** The code in this file is only compiled if: 56 ** 57 ** * The FTS2 module is being built as an extension 58 ** (in which case SQLITE_CORE is not defined), or 59 ** 60 ** * The FTS2 module is being built into the core of 61 ** SQLite (in which case SQLITE_ENABLE_FTS2 is defined). 62 */ 63 64 /* TODO(shess) Consider exporting this comment to an HTML file or the 65 ** wiki. 66 */ 67 /* The full-text index is stored in a series of b+tree (-like) 68 ** structures called segments which map terms to doclists. The 69 ** structures are like b+trees in layout, but are constructed from the 70 ** bottom up in optimal fashion and are not updatable. Since trees 71 ** are built from the bottom up, things will be described from the 72 ** bottom up. 73 ** 74 ** 75 **** Varints **** 76 ** The basic unit of encoding is a variable-length integer called a 77 ** varint. We encode variable-length integers in little-endian order 78 ** using seven bits * per byte as follows: 79 ** 80 ** KEY: 81 ** A = 0xxxxxxx 7 bits of data and one flag bit 82 ** B = 1xxxxxxx 7 bits of data and one flag bit 83 ** 84 ** 7 bits - A 85 ** 14 bits - BA 86 ** 21 bits - BBA 87 ** and so on. 88 ** 89 ** This is identical to how sqlite encodes varints (see util.c). 90 ** 91 ** 92 **** Document lists **** 93 ** A doclist (document list) holds a docid-sorted list of hits for a 94 ** given term. Doclists hold docids, and can optionally associate 95 ** token positions and offsets with docids. 96 ** 97 ** A DL_POSITIONS_OFFSETS doclist is stored like this: 98 ** 99 ** array { 100 ** varint docid; 101 ** array { (position list for column 0) 102 ** varint position; (delta from previous position plus POS_BASE) 103 ** varint startOffset; (delta from previous startOffset) 104 ** varint endOffset; (delta from startOffset) 105 ** } 106 ** array { 107 ** varint POS_COLUMN; (marks start of position list for new column) 108 ** varint column; (index of new column) 109 ** array { 110 ** varint position; (delta from previous position plus POS_BASE) 111 ** varint startOffset;(delta from previous startOffset) 112 ** varint endOffset; (delta from startOffset) 113 ** } 114 ** } 115 ** varint POS_END; (marks end of positions for this document. 116 ** } 117 ** 118 ** Here, array { X } means zero or more occurrences of X, adjacent in 119 ** memory. A "position" is an index of a token in the token stream 120 ** generated by the tokenizer, while an "offset" is a byte offset, 121 ** both based at 0. Note that POS_END and POS_COLUMN occur in the 122 ** same logical place as the position element, and act as sentinals 123 ** ending a position list array. 124 ** 125 ** A DL_POSITIONS doclist omits the startOffset and endOffset 126 ** information. A DL_DOCIDS doclist omits both the position and 127 ** offset information, becoming an array of varint-encoded docids. 128 ** 129 ** On-disk data is stored as type DL_DEFAULT, so we don't serialize 130 ** the type. Due to how deletion is implemented in the segmentation 131 ** system, on-disk doclists MUST store at least positions. 132 ** 133 ** 134 **** Segment leaf nodes **** 135 ** Segment leaf nodes store terms and doclists, ordered by term. Leaf 136 ** nodes are written using LeafWriter, and read using LeafReader (to 137 ** iterate through a single leaf node's data) and LeavesReader (to 138 ** iterate through a segment's entire leaf layer). Leaf nodes have 139 ** the format: 140 ** 141 ** varint iHeight; (height from leaf level, always 0) 142 ** varint nTerm; (length of first term) 143 ** char pTerm[nTerm]; (content of first term) 144 ** varint nDoclist; (length of term's associated doclist) 145 ** char pDoclist[nDoclist]; (content of doclist) 146 ** array { 147 ** (further terms are delta-encoded) 148 ** varint nPrefix; (length of prefix shared with previous term) 149 ** varint nSuffix; (length of unshared suffix) 150 ** char pTermSuffix[nSuffix];(unshared suffix of next term) 151 ** varint nDoclist; (length of term's associated doclist) 152 ** char pDoclist[nDoclist]; (content of doclist) 153 ** } 154 ** 155 ** Here, array { X } means zero or more occurrences of X, adjacent in 156 ** memory. 157 ** 158 ** Leaf nodes are broken into blocks which are stored contiguously in 159 ** the %_segments table in sorted order. This means that when the end 160 ** of a node is reached, the next term is in the node with the next 161 ** greater node id. 162 ** 163 ** New data is spilled to a new leaf node when the current node 164 ** exceeds LEAF_MAX bytes (default 2048). New data which itself is 165 ** larger than STANDALONE_MIN (default 1024) is placed in a standalone 166 ** node (a leaf node with a single term and doclist). The goal of 167 ** these settings is to pack together groups of small doclists while 168 ** making it efficient to directly access large doclists. The 169 ** assumption is that large doclists represent terms which are more 170 ** likely to be query targets. 171 ** 172 ** TODO(shess) It may be useful for blocking decisions to be more 173 ** dynamic. For instance, it may make more sense to have a 2.5k leaf 174 ** node rather than splitting into 2k and .5k nodes. My intuition is 175 ** that this might extend through 2x or 4x the pagesize. 176 ** 177 ** 178 **** Segment interior nodes **** 179 ** Segment interior nodes store blockids for subtree nodes and terms 180 ** to describe what data is stored by the each subtree. Interior 181 ** nodes are written using InteriorWriter, and read using 182 ** InteriorReader. InteriorWriters are created as needed when 183 ** SegmentWriter creates new leaf nodes, or when an interior node 184 ** itself grows too big and must be split. The format of interior 185 ** nodes: 186 ** 187 ** varint iHeight; (height from leaf level, always >0) 188 ** varint iBlockid; (block id of node's leftmost subtree) 189 ** optional { 190 ** varint nTerm; (length of first term) 191 ** char pTerm[nTerm]; (content of first term) 192 ** array { 193 ** (further terms are delta-encoded) 194 ** varint nPrefix; (length of shared prefix with previous term) 195 ** varint nSuffix; (length of unshared suffix) 196 ** char pTermSuffix[nSuffix]; (unshared suffix of next term) 197 ** } 198 ** } 199 ** 200 ** Here, optional { X } means an optional element, while array { X } 201 ** means zero or more occurrences of X, adjacent in memory. 202 ** 203 ** An interior node encodes n terms separating n+1 subtrees. The 204 ** subtree blocks are contiguous, so only the first subtree's blockid 205 ** is encoded. The subtree at iBlockid will contain all terms less 206 ** than the first term encoded (or all terms if no term is encoded). 207 ** Otherwise, for terms greater than or equal to pTerm[i] but less 208 ** than pTerm[i+1], the subtree for that term will be rooted at 209 ** iBlockid+i. Interior nodes only store enough term data to 210 ** distinguish adjacent children (if the rightmost term of the left 211 ** child is "something", and the leftmost term of the right child is 212 ** "wicked", only "w" is stored). 213 ** 214 ** New data is spilled to a new interior node at the same height when 215 ** the current node exceeds INTERIOR_MAX bytes (default 2048). 216 ** INTERIOR_MIN_TERMS (default 7) keeps large terms from monopolizing 217 ** interior nodes and making the tree too skinny. The interior nodes 218 ** at a given height are naturally tracked by interior nodes at 219 ** height+1, and so on. 220 ** 221 ** 222 **** Segment directory **** 223 ** The segment directory in table %_segdir stores meta-information for 224 ** merging and deleting segments, and also the root node of the 225 ** segment's tree. 226 ** 227 ** The root node is the top node of the segment's tree after encoding 228 ** the entire segment, restricted to ROOT_MAX bytes (default 1024). 229 ** This could be either a leaf node or an interior node. If the top 230 ** node requires more than ROOT_MAX bytes, it is flushed to %_segments 231 ** and a new root interior node is generated (which should always fit 232 ** within ROOT_MAX because it only needs space for 2 varints, the 233 ** height and the blockid of the previous root). 234 ** 235 ** The meta-information in the segment directory is: 236 ** level - segment level (see below) 237 ** idx - index within level 238 ** - (level,idx uniquely identify a segment) 239 ** start_block - first leaf node 240 ** leaves_end_block - last leaf node 241 ** end_block - last block (including interior nodes) 242 ** root - contents of root node 243 ** 244 ** If the root node is a leaf node, then start_block, 245 ** leaves_end_block, and end_block are all 0. 246 ** 247 ** 248 **** Segment merging **** 249 ** To amortize update costs, segments are groups into levels and 250 ** merged in matches. Each increase in level represents exponentially 251 ** more documents. 252 ** 253 ** New documents (actually, document updates) are tokenized and 254 ** written individually (using LeafWriter) to a level 0 segment, with 255 ** incrementing idx. When idx reaches MERGE_COUNT (default 16), all 256 ** level 0 segments are merged into a single level 1 segment. Level 1 257 ** is populated like level 0, and eventually MERGE_COUNT level 1 258 ** segments are merged to a single level 2 segment (representing 259 ** MERGE_COUNT^2 updates), and so on. 260 ** 261 ** A segment merge traverses all segments at a given level in 262 ** parallel, performing a straightforward sorted merge. Since segment 263 ** leaf nodes are written in to the %_segments table in order, this 264 ** merge traverses the underlying sqlite disk structures efficiently. 265 ** After the merge, all segment blocks from the merged level are 266 ** deleted. 267 ** 268 ** MERGE_COUNT controls how often we merge segments. 16 seems to be 269 ** somewhat of a sweet spot for insertion performance. 32 and 64 show 270 ** very similar performance numbers to 16 on insertion, though they're 271 ** a tiny bit slower (perhaps due to more overhead in merge-time 272 ** sorting). 8 is about 20% slower than 16, 4 about 50% slower than 273 ** 16, 2 about 66% slower than 16. 274 ** 275 ** At query time, high MERGE_COUNT increases the number of segments 276 ** which need to be scanned and merged. For instance, with 100k docs 277 ** inserted: 278 ** 279 ** MERGE_COUNT segments 280 ** 16 25 281 ** 8 12 282 ** 4 10 283 ** 2 6 284 ** 285 ** This appears to have only a moderate impact on queries for very 286 ** frequent terms (which are somewhat dominated by segment merge 287 ** costs), and infrequent and non-existent terms still seem to be fast 288 ** even with many segments. 289 ** 290 ** TODO(shess) That said, it would be nice to have a better query-side 291 ** argument for MERGE_COUNT of 16. Also, it is possible/likely that 292 ** optimizations to things like doclist merging will swing the sweet 293 ** spot around. 294 ** 295 ** 296 ** 297 **** Handling of deletions and updates **** 298 ** Since we're using a segmented structure, with no docid-oriented 299 ** index into the term index, we clearly cannot simply update the term 300 ** index when a document is deleted or updated. For deletions, we 301 ** write an empty doclist (varint(docid) varint(POS_END)), for updates 302 ** we simply write the new doclist. Segment merges overwrite older 303 ** data for a particular docid with newer data, so deletes or updates 304 ** will eventually overtake the earlier data and knock it out. The 305 ** query logic likewise merges doclists so that newer data knocks out 306 ** older data. 307 ** 308 ** TODO(shess) Provide a VACUUM type operation to clear out all 309 ** deletions and duplications. This would basically be a forced merge 310 ** into a single segment. 311 */ 312 313 #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS2) 314 315 #if defined(SQLITE_ENABLE_FTS2) && !defined(SQLITE_CORE) 316 # define SQLITE_CORE 1 317 #endif 318 319 #include <assert.h> 320 #include <stdlib.h> 321 #include <stdio.h> 322 #include <string.h> 323 #include "fts2.h" 324 #include "fts2_hash.h" 325 #include "fts2_tokenizer.h" 326 #include "sqlite3.h" 327 #ifndef SQLITE_CORE 328 # include "sqlite3ext.h" 329 SQLITE_EXTENSION_INIT1 330 #endif 331 332 333 /* TODO(shess) MAN, this thing needs some refactoring. At minimum, it 334 ** would be nice to order the file better, perhaps something along the 335 ** lines of: 336 ** 337 ** - utility functions 338 ** - table setup functions 339 ** - table update functions 340 ** - table query functions 341 ** 342 ** Put the query functions last because they're likely to reference 343 ** typedefs or functions from the table update section. 344 */ 345 346 #if 0 347 # define TRACE(A) printf A; fflush(stdout) 348 #else 349 # define TRACE(A) 350 #endif 351 352 #if 0 353 /* Useful to set breakpoints. See main.c sqlite3Corrupt(). */ 354 static int fts2Corrupt(void){ 355 return SQLITE_CORRUPT; 356 } 357 # define SQLITE_CORRUPT_BKPT fts2Corrupt() 358 #else 359 # define SQLITE_CORRUPT_BKPT SQLITE_CORRUPT 360 #endif 361 362 /* It is not safe to call isspace(), tolower(), or isalnum() on 363 ** hi-bit-set characters. This is the same solution used in the 364 ** tokenizer. 365 */ 366 /* TODO(shess) The snippet-generation code should be using the 367 ** tokenizer-generated tokens rather than doing its own local 368 ** tokenization. 369 */ 370 /* TODO(shess) Is __isascii() a portable version of (c&0x80)==0? */ 371 static int safe_isspace(char c){ 372 return c==' ' || c=='\t' || c=='\n' || c=='\r' || c=='\v' || c=='\f'; 373 } 374 static int safe_tolower(char c){ 375 return (c>='A' && c<='Z') ? (c - 'A' + 'a') : c; 376 } 377 static int safe_isalnum(char c){ 378 return (c>='0' && c<='9') || (c>='A' && c<='Z') || (c>='a' && c<='z'); 379 } 380 381 typedef enum DocListType { 382 DL_DOCIDS, /* docids only */ 383 DL_POSITIONS, /* docids + positions */ 384 DL_POSITIONS_OFFSETS /* docids + positions + offsets */ 385 } DocListType; 386 387 /* 388 ** By default, only positions and not offsets are stored in the doclists. 389 ** To change this so that offsets are stored too, compile with 390 ** 391 ** -DDL_DEFAULT=DL_POSITIONS_OFFSETS 392 ** 393 ** If DL_DEFAULT is set to DL_DOCIDS, your table can only be inserted 394 ** into (no deletes or updates). 395 */ 396 #ifndef DL_DEFAULT 397 # define DL_DEFAULT DL_POSITIONS 398 #endif 399 400 enum { 401 POS_END = 0, /* end of this position list */ 402 POS_COLUMN, /* followed by new column number */ 403 POS_BASE 404 }; 405 406 /* MERGE_COUNT controls how often we merge segments (see comment at 407 ** top of file). 408 */ 409 #define MERGE_COUNT 16 410 411 /* utility functions */ 412 413 /* CLEAR() and SCRAMBLE() abstract memset() on a pointer to a single 414 ** record to prevent errors of the form: 415 ** 416 ** my_function(SomeType *b){ 417 ** memset(b, '\0', sizeof(b)); // sizeof(b)!=sizeof(*b) 418 ** } 419 */ 420 /* TODO(shess) Obvious candidates for a header file. */ 421 #define CLEAR(b) memset(b, '\0', sizeof(*(b))) 422 423 #ifndef NDEBUG 424 # define SCRAMBLE(b) memset(b, 0x55, sizeof(*(b))) 425 #else 426 # define SCRAMBLE(b) 427 #endif 428 429 /* We may need up to VARINT_MAX bytes to store an encoded 64-bit integer. */ 430 #define VARINT_MAX 10 431 432 /* Write a 64-bit variable-length integer to memory starting at p[0]. 433 * The length of data written will be between 1 and VARINT_MAX bytes. 434 * The number of bytes written is returned. */ 435 static int putVarint(char *p, sqlite_int64 v){ 436 unsigned char *q = (unsigned char *) p; 437 sqlite_uint64 vu = v; 438 do{ 439 *q++ = (unsigned char) ((vu & 0x7f) | 0x80); 440 vu >>= 7; 441 }while( vu!=0 ); 442 q[-1] &= 0x7f; /* turn off high bit in final byte */ 443 assert( q - (unsigned char *)p <= VARINT_MAX ); 444 return (int) (q - (unsigned char *)p); 445 } 446 447 /* Read a 64-bit variable-length integer from memory starting at p[0]. 448 * Return the number of bytes read, or 0 on error. 449 * The value is stored in *v. */ 450 static int getVarintSafe(const char *p, sqlite_int64 *v, int max){ 451 const unsigned char *q = (const unsigned char *) p; 452 sqlite_uint64 x = 0, y = 1; 453 if( max>VARINT_MAX ) max = VARINT_MAX; 454 while( max && (*q & 0x80) == 0x80 ){ 455 max--; 456 x += y * (*q++ & 0x7f); 457 y <<= 7; 458 } 459 if ( !max ){ 460 assert( 0 ); 461 return 0; /* tried to read too much; bad data */ 462 } 463 x += y * (*q++); 464 *v = (sqlite_int64) x; 465 return (int) (q - (unsigned char *)p); 466 } 467 468 static int getVarint(const char *p, sqlite_int64 *v){ 469 return getVarintSafe(p, v, VARINT_MAX); 470 } 471 472 static int getVarint32Safe(const char *p, int *pi, int max){ 473 sqlite_int64 i; 474 int ret = getVarintSafe(p, &i, max); 475 if( !ret ) return ret; 476 *pi = (int) i; 477 assert( *pi==i ); 478 return ret; 479 } 480 481 static int getVarint32(const char* p, int *pi){ 482 return getVarint32Safe(p, pi, VARINT_MAX); 483 } 484 485 /*******************************************************************/ 486 /* DataBuffer is used to collect data into a buffer in piecemeal 487 ** fashion. It implements the usual distinction between amount of 488 ** data currently stored (nData) and buffer capacity (nCapacity). 489 ** 490 ** dataBufferInit - create a buffer with given initial capacity. 491 ** dataBufferReset - forget buffer's data, retaining capacity. 492 ** dataBufferDestroy - free buffer's data. 493 ** dataBufferSwap - swap contents of two buffers. 494 ** dataBufferExpand - expand capacity without adding data. 495 ** dataBufferAppend - append data. 496 ** dataBufferAppend2 - append two pieces of data at once. 497 ** dataBufferReplace - replace buffer's data. 498 */ 499 typedef struct DataBuffer { 500 char *pData; /* Pointer to malloc'ed buffer. */ 501 int nCapacity; /* Size of pData buffer. */ 502 int nData; /* End of data loaded into pData. */ 503 } DataBuffer; 504 505 static void dataBufferInit(DataBuffer *pBuffer, int nCapacity){ 506 assert( nCapacity>=0 ); 507 pBuffer->nData = 0; 508 pBuffer->nCapacity = nCapacity; 509 pBuffer->pData = nCapacity==0 ? NULL : sqlite3_malloc(nCapacity); 510 } 511 static void dataBufferReset(DataBuffer *pBuffer){ 512 pBuffer->nData = 0; 513 } 514 static void dataBufferDestroy(DataBuffer *pBuffer){ 515 if( pBuffer->pData!=NULL ) sqlite3_free(pBuffer->pData); 516 SCRAMBLE(pBuffer); 517 } 518 static void dataBufferSwap(DataBuffer *pBuffer1, DataBuffer *pBuffer2){ 519 DataBuffer tmp = *pBuffer1; 520 *pBuffer1 = *pBuffer2; 521 *pBuffer2 = tmp; 522 } 523 static void dataBufferExpand(DataBuffer *pBuffer, int nAddCapacity){ 524 assert( nAddCapacity>0 ); 525 /* TODO(shess) Consider expanding more aggressively. Note that the 526 ** underlying malloc implementation may take care of such things for 527 ** us already. 528 */ 529 if( pBuffer->nData+nAddCapacity>pBuffer->nCapacity ){ 530 pBuffer->nCapacity = pBuffer->nData+nAddCapacity; 531 pBuffer->pData = sqlite3_realloc(pBuffer->pData, pBuffer->nCapacity); 532 } 533 } 534 static void dataBufferAppend(DataBuffer *pBuffer, 535 const char *pSource, int nSource){ 536 assert( nSource>0 && pSource!=NULL ); 537 dataBufferExpand(pBuffer, nSource); 538 memcpy(pBuffer->pData+pBuffer->nData, pSource, nSource); 539 pBuffer->nData += nSource; 540 } 541 static void dataBufferAppend2(DataBuffer *pBuffer, 542 const char *pSource1, int nSource1, 543 const char *pSource2, int nSource2){ 544 assert( nSource1>0 && pSource1!=NULL ); 545 assert( nSource2>0 && pSource2!=NULL ); 546 dataBufferExpand(pBuffer, nSource1+nSource2); 547 memcpy(pBuffer->pData+pBuffer->nData, pSource1, nSource1); 548 memcpy(pBuffer->pData+pBuffer->nData+nSource1, pSource2, nSource2); 549 pBuffer->nData += nSource1+nSource2; 550 } 551 static void dataBufferReplace(DataBuffer *pBuffer, 552 const char *pSource, int nSource){ 553 dataBufferReset(pBuffer); 554 dataBufferAppend(pBuffer, pSource, nSource); 555 } 556 557 /* StringBuffer is a null-terminated version of DataBuffer. */ 558 typedef struct StringBuffer { 559 DataBuffer b; /* Includes null terminator. */ 560 } StringBuffer; 561 562 static void initStringBuffer(StringBuffer *sb){ 563 dataBufferInit(&sb->b, 100); 564 dataBufferReplace(&sb->b, "", 1); 565 } 566 static int stringBufferLength(StringBuffer *sb){ 567 return sb->b.nData-1; 568 } 569 static char *stringBufferData(StringBuffer *sb){ 570 return sb->b.pData; 571 } 572 static void stringBufferDestroy(StringBuffer *sb){ 573 dataBufferDestroy(&sb->b); 574 } 575 576 static void nappend(StringBuffer *sb, const char *zFrom, int nFrom){ 577 assert( sb->b.nData>0 ); 578 if( nFrom>0 ){ 579 sb->b.nData--; 580 dataBufferAppend2(&sb->b, zFrom, nFrom, "", 1); 581 } 582 } 583 static void append(StringBuffer *sb, const char *zFrom){ 584 nappend(sb, zFrom, strlen(zFrom)); 585 } 586 587 /* Append a list of strings separated by commas. */ 588 static void appendList(StringBuffer *sb, int nString, char **azString){ 589 int i; 590 for(i=0; i<nString; ++i){ 591 if( i>0 ) append(sb, ", "); 592 append(sb, azString[i]); 593 } 594 } 595 596 static int endsInWhiteSpace(StringBuffer *p){ 597 return stringBufferLength(p)>0 && 598 safe_isspace(stringBufferData(p)[stringBufferLength(p)-1]); 599 } 600 601 /* If the StringBuffer ends in something other than white space, add a 602 ** single space character to the end. 603 */ 604 static void appendWhiteSpace(StringBuffer *p){ 605 if( stringBufferLength(p)==0 ) return; 606 if( !endsInWhiteSpace(p) ) append(p, " "); 607 } 608 609 /* Remove white space from the end of the StringBuffer */ 610 static void trimWhiteSpace(StringBuffer *p){ 611 while( endsInWhiteSpace(p) ){ 612 p->b.pData[--p->b.nData-1] = '\0'; 613 } 614 } 615 616 /*******************************************************************/ 617 /* DLReader is used to read document elements from a doclist. The 618 ** current docid is cached, so dlrDocid() is fast. DLReader does not 619 ** own the doclist buffer. 620 ** 621 ** dlrAtEnd - true if there's no more data to read. 622 ** dlrDocid - docid of current document. 623 ** dlrDocData - doclist data for current document (including docid). 624 ** dlrDocDataBytes - length of same. 625 ** dlrAllDataBytes - length of all remaining data. 626 ** dlrPosData - position data for current document. 627 ** dlrPosDataLen - length of pos data for current document (incl POS_END). 628 ** dlrStep - step to current document. 629 ** dlrInit - initial for doclist of given type against given data. 630 ** dlrDestroy - clean up. 631 ** 632 ** Expected usage is something like: 633 ** 634 ** DLReader reader; 635 ** dlrInit(&reader, pData, nData); 636 ** while( !dlrAtEnd(&reader) ){ 637 ** // calls to dlrDocid() and kin. 638 ** dlrStep(&reader); 639 ** } 640 ** dlrDestroy(&reader); 641 */ 642 typedef struct DLReader { 643 DocListType iType; 644 const char *pData; 645 int nData; 646 647 sqlite_int64 iDocid; 648 int nElement; 649 } DLReader; 650 651 static int dlrAtEnd(DLReader *pReader){ 652 assert( pReader->nData>=0 ); 653 return pReader->nData<=0; 654 } 655 static sqlite_int64 dlrDocid(DLReader *pReader){ 656 assert( !dlrAtEnd(pReader) ); 657 return pReader->iDocid; 658 } 659 static const char *dlrDocData(DLReader *pReader){ 660 assert( !dlrAtEnd(pReader) ); 661 return pReader->pData; 662 } 663 static int dlrDocDataBytes(DLReader *pReader){ 664 assert( !dlrAtEnd(pReader) ); 665 return pReader->nElement; 666 } 667 static int dlrAllDataBytes(DLReader *pReader){ 668 assert( !dlrAtEnd(pReader) ); 669 return pReader->nData; 670 } 671 /* TODO(shess) Consider adding a field to track iDocid varint length 672 ** to make these two functions faster. This might matter (a tiny bit) 673 ** for queries. 674 */ 675 static const char *dlrPosData(DLReader *pReader){ 676 sqlite_int64 iDummy; 677 int n = getVarintSafe(pReader->pData, &iDummy, pReader->nElement); 678 if( !n ) return NULL; 679 assert( !dlrAtEnd(pReader) ); 680 return pReader->pData+n; 681 } 682 static int dlrPosDataLen(DLReader *pReader){ 683 sqlite_int64 iDummy; 684 int n = getVarint(pReader->pData, &iDummy); 685 assert( !dlrAtEnd(pReader) ); 686 return pReader->nElement-n; 687 } 688 static int dlrStep(DLReader *pReader){ 689 assert( !dlrAtEnd(pReader) ); 690 691 /* Skip past current doclist element. */ 692 assert( pReader->nElement<=pReader->nData ); 693 pReader->pData += pReader->nElement; 694 pReader->nData -= pReader->nElement; 695 696 /* If there is more data, read the next doclist element. */ 697 if( pReader->nData>0 ){ 698 sqlite_int64 iDocidDelta; 699 int nTotal = 0; 700 int iDummy, n = getVarintSafe(pReader->pData, &iDocidDelta, pReader->nData); 701 if( !n ) return SQLITE_CORRUPT_BKPT; 702 nTotal += n; 703 pReader->iDocid += iDocidDelta; 704 if( pReader->iType>=DL_POSITIONS ){ 705 while( 1 ){ 706 n = getVarint32Safe(pReader->pData+nTotal, &iDummy, 707 pReader->nData-nTotal); 708 if( !n ) return SQLITE_CORRUPT_BKPT; 709 nTotal += n; 710 if( iDummy==POS_END ) break; 711 if( iDummy==POS_COLUMN ){ 712 n = getVarint32Safe(pReader->pData+nTotal, &iDummy, 713 pReader->nData-nTotal); 714 if( !n ) return SQLITE_CORRUPT_BKPT; 715 nTotal += n; 716 }else if( pReader->iType==DL_POSITIONS_OFFSETS ){ 717 n = getVarint32Safe(pReader->pData+nTotal, &iDummy, 718 pReader->nData-nTotal); 719 if( !n ) return SQLITE_CORRUPT_BKPT; 720 nTotal += n; 721 n = getVarint32Safe(pReader->pData+nTotal, &iDummy, 722 pReader->nData-nTotal); 723 if( !n ) return SQLITE_CORRUPT_BKPT; 724 nTotal += n; 725 } 726 } 727 } 728 pReader->nElement = nTotal; 729 assert( pReader->nElement<=pReader->nData ); 730 } 731 return SQLITE_OK; 732 } 733 static void dlrDestroy(DLReader *pReader){ 734 SCRAMBLE(pReader); 735 } 736 static int dlrInit(DLReader *pReader, DocListType iType, 737 const char *pData, int nData){ 738 int rc; 739 assert( pData!=NULL && nData!=0 ); 740 pReader->iType = iType; 741 pReader->pData = pData; 742 pReader->nData = nData; 743 pReader->nElement = 0; 744 pReader->iDocid = 0; 745 746 /* Load the first element's data. There must be a first element. */ 747 rc = dlrStep(pReader); 748 if( rc!=SQLITE_OK ) dlrDestroy(pReader); 749 return rc; 750 } 751 752 #ifndef NDEBUG 753 /* Verify that the doclist can be validly decoded. Also returns the 754 ** last docid found because it is convenient in other assertions for 755 ** DLWriter. 756 */ 757 static void docListValidate(DocListType iType, const char *pData, int nData, 758 sqlite_int64 *pLastDocid){ 759 sqlite_int64 iPrevDocid = 0; 760 assert( nData>0 ); 761 assert( pData!=0 ); 762 assert( pData+nData>pData ); 763 while( nData!=0 ){ 764 sqlite_int64 iDocidDelta; 765 int n = getVarint(pData, &iDocidDelta); 766 iPrevDocid += iDocidDelta; 767 if( iType>DL_DOCIDS ){ 768 int iDummy; 769 while( 1 ){ 770 n += getVarint32(pData+n, &iDummy); 771 if( iDummy==POS_END ) break; 772 if( iDummy==POS_COLUMN ){ 773 n += getVarint32(pData+n, &iDummy); 774 }else if( iType>DL_POSITIONS ){ 775 n += getVarint32(pData+n, &iDummy); 776 n += getVarint32(pData+n, &iDummy); 777 } 778 assert( n<=nData ); 779 } 780 } 781 assert( n<=nData ); 782 pData += n; 783 nData -= n; 784 } 785 if( pLastDocid ) *pLastDocid = iPrevDocid; 786 } 787 #define ASSERT_VALID_DOCLIST(i, p, n, o) docListValidate(i, p, n, o) 788 #else 789 #define ASSERT_VALID_DOCLIST(i, p, n, o) assert( 1 ) 790 #endif 791 792 /*******************************************************************/ 793 /* DLWriter is used to write doclist data to a DataBuffer. DLWriter 794 ** always appends to the buffer and does not own it. 795 ** 796 ** dlwInit - initialize to write a given type doclistto a buffer. 797 ** dlwDestroy - clear the writer's memory. Does not free buffer. 798 ** dlwAppend - append raw doclist data to buffer. 799 ** dlwCopy - copy next doclist from reader to writer. 800 ** dlwAdd - construct doclist element and append to buffer. 801 ** Only apply dlwAdd() to DL_DOCIDS doclists (else use PLWriter). 802 */ 803 typedef struct DLWriter { 804 DocListType iType; 805 DataBuffer *b; 806 sqlite_int64 iPrevDocid; 807 #ifndef NDEBUG 808 int has_iPrevDocid; 809 #endif 810 } DLWriter; 811 812 static void dlwInit(DLWriter *pWriter, DocListType iType, DataBuffer *b){ 813 pWriter->b = b; 814 pWriter->iType = iType; 815 pWriter->iPrevDocid = 0; 816 #ifndef NDEBUG 817 pWriter->has_iPrevDocid = 0; 818 #endif 819 } 820 static void dlwDestroy(DLWriter *pWriter){ 821 SCRAMBLE(pWriter); 822 } 823 /* iFirstDocid is the first docid in the doclist in pData. It is 824 ** needed because pData may point within a larger doclist, in which 825 ** case the first item would be delta-encoded. 826 ** 827 ** iLastDocid is the final docid in the doclist in pData. It is 828 ** needed to create the new iPrevDocid for future delta-encoding. The 829 ** code could decode the passed doclist to recreate iLastDocid, but 830 ** the only current user (docListMerge) already has decoded this 831 ** information. 832 */ 833 /* TODO(shess) This has become just a helper for docListMerge. 834 ** Consider a refactor to make this cleaner. 835 */ 836 static int dlwAppend(DLWriter *pWriter, 837 const char *pData, int nData, 838 sqlite_int64 iFirstDocid, sqlite_int64 iLastDocid){ 839 sqlite_int64 iDocid = 0; 840 char c[VARINT_MAX]; 841 int nFirstOld, nFirstNew; /* Old and new varint len of first docid. */ 842 #ifndef NDEBUG 843 sqlite_int64 iLastDocidDelta; 844 #endif 845 846 /* Recode the initial docid as delta from iPrevDocid. */ 847 nFirstOld = getVarintSafe(pData, &iDocid, nData); 848 if( !nFirstOld ) return SQLITE_CORRUPT_BKPT; 849 assert( nFirstOld<nData || (nFirstOld==nData && pWriter->iType==DL_DOCIDS) ); 850 nFirstNew = putVarint(c, iFirstDocid-pWriter->iPrevDocid); 851 852 /* Verify that the incoming doclist is valid AND that it ends with 853 ** the expected docid. This is essential because we'll trust this 854 ** docid in future delta-encoding. 855 */ 856 ASSERT_VALID_DOCLIST(pWriter->iType, pData, nData, &iLastDocidDelta); 857 assert( iLastDocid==iFirstDocid-iDocid+iLastDocidDelta ); 858 859 /* Append recoded initial docid and everything else. Rest of docids 860 ** should have been delta-encoded from previous initial docid. 861 */ 862 if( nFirstOld<nData ){ 863 dataBufferAppend2(pWriter->b, c, nFirstNew, 864 pData+nFirstOld, nData-nFirstOld); 865 }else{ 866 dataBufferAppend(pWriter->b, c, nFirstNew); 867 } 868 pWriter->iPrevDocid = iLastDocid; 869 return SQLITE_OK; 870 } 871 static int dlwCopy(DLWriter *pWriter, DLReader *pReader){ 872 return dlwAppend(pWriter, dlrDocData(pReader), dlrDocDataBytes(pReader), 873 dlrDocid(pReader), dlrDocid(pReader)); 874 } 875 static void dlwAdd(DLWriter *pWriter, sqlite_int64 iDocid){ 876 char c[VARINT_MAX]; 877 int n = putVarint(c, iDocid-pWriter->iPrevDocid); 878 879 /* Docids must ascend. */ 880 assert( !pWriter->has_iPrevDocid || iDocid>pWriter->iPrevDocid ); 881 assert( pWriter->iType==DL_DOCIDS ); 882 883 dataBufferAppend(pWriter->b, c, n); 884 pWriter->iPrevDocid = iDocid; 885 #ifndef NDEBUG 886 pWriter->has_iPrevDocid = 1; 887 #endif 888 } 889 890 /*******************************************************************/ 891 /* PLReader is used to read data from a document's position list. As 892 ** the caller steps through the list, data is cached so that varints 893 ** only need to be decoded once. 894 ** 895 ** plrInit, plrDestroy - create/destroy a reader. 896 ** plrColumn, plrPosition, plrStartOffset, plrEndOffset - accessors 897 ** plrAtEnd - at end of stream, only call plrDestroy once true. 898 ** plrStep - step to the next element. 899 */ 900 typedef struct PLReader { 901 /* These refer to the next position's data. nData will reach 0 when 902 ** reading the last position, so plrStep() signals EOF by setting 903 ** pData to NULL. 904 */ 905 const char *pData; 906 int nData; 907 908 DocListType iType; 909 int iColumn; /* the last column read */ 910 int iPosition; /* the last position read */ 911 int iStartOffset; /* the last start offset read */ 912 int iEndOffset; /* the last end offset read */ 913 } PLReader; 914 915 static int plrAtEnd(PLReader *pReader){ 916 return pReader->pData==NULL; 917 } 918 static int plrColumn(PLReader *pReader){ 919 assert( !plrAtEnd(pReader) ); 920 return pReader->iColumn; 921 } 922 static int plrPosition(PLReader *pReader){ 923 assert( !plrAtEnd(pReader) ); 924 return pReader->iPosition; 925 } 926 static int plrStartOffset(PLReader *pReader){ 927 assert( !plrAtEnd(pReader) ); 928 return pReader->iStartOffset; 929 } 930 static int plrEndOffset(PLReader *pReader){ 931 assert( !plrAtEnd(pReader) ); 932 return pReader->iEndOffset; 933 } 934 static int plrStep(PLReader *pReader){ 935 int i, n, nTotal = 0; 936 937 assert( !plrAtEnd(pReader) ); 938 939 if( pReader->nData<=0 ){ 940 pReader->pData = NULL; 941 return SQLITE_OK; 942 } 943 944 n = getVarint32Safe(pReader->pData, &i, pReader->nData); 945 if( !n ) return SQLITE_CORRUPT_BKPT; 946 nTotal += n; 947 if( i==POS_COLUMN ){ 948 n = getVarint32Safe(pReader->pData+nTotal, &pReader->iColumn, 949 pReader->nData-nTotal); 950 if( !n ) return SQLITE_CORRUPT_BKPT; 951 nTotal += n; 952 pReader->iPosition = 0; 953 pReader->iStartOffset = 0; 954 n = getVarint32Safe(pReader->pData+nTotal, &i, pReader->nData-nTotal); 955 if( !n ) return SQLITE_CORRUPT_BKPT; 956 nTotal += n; 957 } 958 /* Should never see adjacent column changes. */ 959 assert( i!=POS_COLUMN ); 960 961 if( i==POS_END ){ 962 assert( nTotal<=pReader->nData ); 963 pReader->nData = 0; 964 pReader->pData = NULL; 965 return SQLITE_OK; 966 } 967 968 pReader->iPosition += i-POS_BASE; 969 if( pReader->iType==DL_POSITIONS_OFFSETS ){ 970 n = getVarint32Safe(pReader->pData+nTotal, &i, pReader->nData-nTotal); 971 if( !n ) return SQLITE_CORRUPT_BKPT; 972 nTotal += n; 973 pReader->iStartOffset += i; 974 n = getVarint32Safe(pReader->pData+nTotal, &i, pReader->nData-nTotal); 975 if( !n ) return SQLITE_CORRUPT_BKPT; 976 nTotal += n; 977 pReader->iEndOffset = pReader->iStartOffset+i; 978 } 979 assert( nTotal<=pReader->nData ); 980 pReader->pData += nTotal; 981 pReader->nData -= nTotal; 982 return SQLITE_OK; 983 } 984 985 static void plrDestroy(PLReader *pReader){ 986 SCRAMBLE(pReader); 987 } 988 989 static int plrInit(PLReader *pReader, DLReader *pDLReader){ 990 int rc; 991 pReader->pData = dlrPosData(pDLReader); 992 pReader->nData = dlrPosDataLen(pDLReader); 993 pReader->iType = pDLReader->iType; 994 pReader->iColumn = 0; 995 pReader->iPosition = 0; 996 pReader->iStartOffset = 0; 997 pReader->iEndOffset = 0; 998 rc = plrStep(pReader); 999 if( rc!=SQLITE_OK ) plrDestroy(pReader); 1000 return rc; 1001 } 1002 1003 /*******************************************************************/ 1004 /* PLWriter is used in constructing a document's position list. As a 1005 ** convenience, if iType is DL_DOCIDS, PLWriter becomes a no-op. 1006 ** PLWriter writes to the associated DLWriter's buffer. 1007 ** 1008 ** plwInit - init for writing a document's poslist. 1009 ** plwDestroy - clear a writer. 1010 ** plwAdd - append position and offset information. 1011 ** plwCopy - copy next position's data from reader to writer. 1012 ** plwTerminate - add any necessary doclist terminator. 1013 ** 1014 ** Calling plwAdd() after plwTerminate() may result in a corrupt 1015 ** doclist. 1016 */ 1017 /* TODO(shess) Until we've written the second item, we can cache the 1018 ** first item's information. Then we'd have three states: 1019 ** 1020 ** - initialized with docid, no positions. 1021 ** - docid and one position. 1022 ** - docid and multiple positions. 1023 ** 1024 ** Only the last state needs to actually write to dlw->b, which would 1025 ** be an improvement in the DLCollector case. 1026 */ 1027 typedef struct PLWriter { 1028 DLWriter *dlw; 1029 1030 int iColumn; /* the last column written */ 1031 int iPos; /* the last position written */ 1032 int iOffset; /* the last start offset written */ 1033 } PLWriter; 1034 1035 /* TODO(shess) In the case where the parent is reading these values 1036 ** from a PLReader, we could optimize to a copy if that PLReader has 1037 ** the same type as pWriter. 1038 */ 1039 static void plwAdd(PLWriter *pWriter, int iColumn, int iPos, 1040 int iStartOffset, int iEndOffset){ 1041 /* Worst-case space for POS_COLUMN, iColumn, iPosDelta, 1042 ** iStartOffsetDelta, and iEndOffsetDelta. 1043 */ 1044 char c[5*VARINT_MAX]; 1045 int n = 0; 1046 1047 /* Ban plwAdd() after plwTerminate(). */ 1048 assert( pWriter->iPos!=-1 ); 1049 1050 if( pWriter->dlw->iType==DL_DOCIDS ) return; 1051 1052 if( iColumn!=pWriter->iColumn ){ 1053 n += putVarint(c+n, POS_COLUMN); 1054 n += putVarint(c+n, iColumn); 1055 pWriter->iColumn = iColumn; 1056 pWriter->iPos = 0; 1057 pWriter->iOffset = 0; 1058 } 1059 assert( iPos>=pWriter->iPos ); 1060 n += putVarint(c+n, POS_BASE+(iPos-pWriter->iPos)); 1061 pWriter->iPos = iPos; 1062 if( pWriter->dlw->iType==DL_POSITIONS_OFFSETS ){ 1063 assert( iStartOffset>=pWriter->iOffset ); 1064 n += putVarint(c+n, iStartOffset-pWriter->iOffset); 1065 pWriter->iOffset = iStartOffset; 1066 assert( iEndOffset>=iStartOffset ); 1067 n += putVarint(c+n, iEndOffset-iStartOffset); 1068 } 1069 dataBufferAppend(pWriter->dlw->b, c, n); 1070 } 1071 static void plwCopy(PLWriter *pWriter, PLReader *pReader){ 1072 plwAdd(pWriter, plrColumn(pReader), plrPosition(pReader), 1073 plrStartOffset(pReader), plrEndOffset(pReader)); 1074 } 1075 static void plwInit(PLWriter *pWriter, DLWriter *dlw, sqlite_int64 iDocid){ 1076 char c[VARINT_MAX]; 1077 int n; 1078 1079 pWriter->dlw = dlw; 1080 1081 /* Docids must ascend. */ 1082 assert( !pWriter->dlw->has_iPrevDocid || iDocid>pWriter->dlw->iPrevDocid ); 1083 n = putVarint(c, iDocid-pWriter->dlw->iPrevDocid); 1084 dataBufferAppend(pWriter->dlw->b, c, n); 1085 pWriter->dlw->iPrevDocid = iDocid; 1086 #ifndef NDEBUG 1087 pWriter->dlw->has_iPrevDocid = 1; 1088 #endif 1089 1090 pWriter->iColumn = 0; 1091 pWriter->iPos = 0; 1092 pWriter->iOffset = 0; 1093 } 1094 /* TODO(shess) Should plwDestroy() also terminate the doclist? But 1095 ** then plwDestroy() would no longer be just a destructor, it would 1096 ** also be doing work, which isn't consistent with the overall idiom. 1097 ** Another option would be for plwAdd() to always append any necessary 1098 ** terminator, so that the output is always correct. But that would 1099 ** add incremental work to the common case with the only benefit being 1100 ** API elegance. Punt for now. 1101 */ 1102 static void plwTerminate(PLWriter *pWriter){ 1103 if( pWriter->dlw->iType>DL_DOCIDS ){ 1104 char c[VARINT_MAX]; 1105 int n = putVarint(c, POS_END); 1106 dataBufferAppend(pWriter->dlw->b, c, n); 1107 } 1108 #ifndef NDEBUG 1109 /* Mark as terminated for assert in plwAdd(). */ 1110 pWriter->iPos = -1; 1111 #endif 1112 } 1113 static void plwDestroy(PLWriter *pWriter){ 1114 SCRAMBLE(pWriter); 1115 } 1116 1117 /*******************************************************************/ 1118 /* DLCollector wraps PLWriter and DLWriter to provide a 1119 ** dynamically-allocated doclist area to use during tokenization. 1120 ** 1121 ** dlcNew - malloc up and initialize a collector. 1122 ** dlcDelete - destroy a collector and all contained items. 1123 ** dlcAddPos - append position and offset information. 1124 ** dlcAddDoclist - add the collected doclist to the given buffer. 1125 ** dlcNext - terminate the current document and open another. 1126 */ 1127 typedef struct DLCollector { 1128 DataBuffer b; 1129 DLWriter dlw; 1130 PLWriter plw; 1131 } DLCollector; 1132 1133 /* TODO(shess) This could also be done by calling plwTerminate() and 1134 ** dataBufferAppend(). I tried that, expecting nominal performance 1135 ** differences, but it seemed to pretty reliably be worth 1% to code 1136 ** it this way. I suspect it is the incremental malloc overhead (some 1137 ** percentage of the plwTerminate() calls will cause a realloc), so 1138 ** this might be worth revisiting if the DataBuffer implementation 1139 ** changes. 1140 */ 1141 static void dlcAddDoclist(DLCollector *pCollector, DataBuffer *b){ 1142 if( pCollector->dlw.iType>DL_DOCIDS ){ 1143 char c[VARINT_MAX]; 1144 int n = putVarint(c, POS_END); 1145 dataBufferAppend2(b, pCollector->b.pData, pCollector->b.nData, c, n); 1146 }else{ 1147 dataBufferAppend(b, pCollector->b.pData, pCollector->b.nData); 1148 } 1149 } 1150 static void dlcNext(DLCollector *pCollector, sqlite_int64 iDocid){ 1151 plwTerminate(&pCollector->plw); 1152 plwDestroy(&pCollector->plw); 1153 plwInit(&pCollector->plw, &pCollector->dlw, iDocid); 1154 } 1155 static void dlcAddPos(DLCollector *pCollector, int iColumn, int iPos, 1156 int iStartOffset, int iEndOffset){ 1157 plwAdd(&pCollector->plw, iColumn, iPos, iStartOffset, iEndOffset); 1158 } 1159 1160 static DLCollector *dlcNew(sqlite_int64 iDocid, DocListType iType){ 1161 DLCollector *pCollector = sqlite3_malloc(sizeof(DLCollector)); 1162 dataBufferInit(&pCollector->b, 0); 1163 dlwInit(&pCollector->dlw, iType, &pCollector->b); 1164 plwInit(&pCollector->plw, &pCollector->dlw, iDocid); 1165 return pCollector; 1166 } 1167 static void dlcDelete(DLCollector *pCollector){ 1168 plwDestroy(&pCollector->plw); 1169 dlwDestroy(&pCollector->dlw); 1170 dataBufferDestroy(&pCollector->b); 1171 SCRAMBLE(pCollector); 1172 sqlite3_free(pCollector); 1173 } 1174 1175 1176 /* Copy the doclist data of iType in pData/nData into *out, trimming 1177 ** unnecessary data as we go. Only columns matching iColumn are 1178 ** copied, all columns copied if iColumn is -1. Elements with no 1179 ** matching columns are dropped. The output is an iOutType doclist. 1180 */ 1181 /* NOTE(shess) This code is only valid after all doclists are merged. 1182 ** If this is run before merges, then doclist items which represent 1183 ** deletion will be trimmed, and will thus not effect a deletion 1184 ** during the merge. 1185 */ 1186 static int docListTrim(DocListType iType, const char *pData, int nData, 1187 int iColumn, DocListType iOutType, DataBuffer *out){ 1188 DLReader dlReader; 1189 DLWriter dlWriter; 1190 int rc; 1191 1192 assert( iOutType<=iType ); 1193 1194 rc = dlrInit(&dlReader, iType, pData, nData); 1195 if( rc!=SQLITE_OK ) return rc; 1196 dlwInit(&dlWriter, iOutType, out); 1197 1198 while( !dlrAtEnd(&dlReader) ){ 1199 PLReader plReader; 1200 PLWriter plWriter; 1201 int match = 0; 1202 1203 rc = plrInit(&plReader, &dlReader); 1204 if( rc!=SQLITE_OK ) break; 1205 1206 while( !plrAtEnd(&plReader) ){ 1207 if( iColumn==-1 || plrColumn(&plReader)==iColumn ){ 1208 if( !match ){ 1209 plwInit(&plWriter, &dlWriter, dlrDocid(&dlReader)); 1210 match = 1; 1211 } 1212 plwAdd(&plWriter, plrColumn(&plReader), plrPosition(&plReader), 1213 plrStartOffset(&plReader), plrEndOffset(&plReader)); 1214 } 1215 rc = plrStep(&plReader); 1216 if( rc!=SQLITE_OK ){ 1217 plrDestroy(&plReader); 1218 goto err; 1219 } 1220 } 1221 if( match ){ 1222 plwTerminate(&plWriter); 1223 plwDestroy(&plWriter); 1224 } 1225 1226 plrDestroy(&plReader); 1227 rc = dlrStep(&dlReader); 1228 if( rc!=SQLITE_OK ) break; 1229 } 1230 err: 1231 dlwDestroy(&dlWriter); 1232 dlrDestroy(&dlReader); 1233 return rc; 1234 } 1235 1236 /* Used by docListMerge() to keep doclists in the ascending order by 1237 ** docid, then ascending order by age (so the newest comes first). 1238 */ 1239 typedef struct OrderedDLReader { 1240 DLReader *pReader; 1241 1242 /* TODO(shess) If we assume that docListMerge pReaders is ordered by 1243 ** age (which we do), then we could use pReader comparisons to break 1244 ** ties. 1245 */ 1246 int idx; 1247 } OrderedDLReader; 1248 1249 /* Order eof to end, then by docid asc, idx desc. */ 1250 static int orderedDLReaderCmp(OrderedDLReader *r1, OrderedDLReader *r2){ 1251 if( dlrAtEnd(r1->pReader) ){ 1252 if( dlrAtEnd(r2->pReader) ) return 0; /* Both atEnd(). */ 1253 return 1; /* Only r1 atEnd(). */ 1254 } 1255 if( dlrAtEnd(r2->pReader) ) return -1; /* Only r2 atEnd(). */ 1256 1257 if( dlrDocid(r1->pReader)<dlrDocid(r2->pReader) ) return -1; 1258 if( dlrDocid(r1->pReader)>dlrDocid(r2->pReader) ) return 1; 1259 1260 /* Descending on idx. */ 1261 return r2->idx-r1->idx; 1262 } 1263 1264 /* Bubble p[0] to appropriate place in p[1..n-1]. Assumes that 1265 ** p[1..n-1] is already sorted. 1266 */ 1267 /* TODO(shess) Is this frequent enough to warrant a binary search? 1268 ** Before implementing that, instrument the code to check. In most 1269 ** current usage, I expect that p[0] will be less than p[1] a very 1270 ** high proportion of the time. 1271 */ 1272 static void orderedDLReaderReorder(OrderedDLReader *p, int n){ 1273 while( n>1 && orderedDLReaderCmp(p, p+1)>0 ){ 1274 OrderedDLReader tmp = p[0]; 1275 p[0] = p[1]; 1276 p[1] = tmp; 1277 n--; 1278 p++; 1279 } 1280 } 1281 1282 /* Given an array of doclist readers, merge their doclist elements 1283 ** into out in sorted order (by docid), dropping elements from older 1284 ** readers when there is a duplicate docid. pReaders is assumed to be 1285 ** ordered by age, oldest first. 1286 */ 1287 /* TODO(shess) nReaders must be <= MERGE_COUNT. This should probably 1288 ** be fixed. 1289 */ 1290 static int docListMerge(DataBuffer *out, 1291 DLReader *pReaders, int nReaders){ 1292 OrderedDLReader readers[MERGE_COUNT]; 1293 DLWriter writer; 1294 int i, n; 1295 const char *pStart = 0; 1296 int nStart = 0; 1297 sqlite_int64 iFirstDocid = 0, iLastDocid = 0; 1298 int rc = SQLITE_OK; 1299 1300 assert( nReaders>0 ); 1301 if( nReaders==1 ){ 1302 dataBufferAppend(out, dlrDocData(pReaders), dlrAllDataBytes(pReaders)); 1303 return SQLITE_OK; 1304 } 1305 1306 assert( nReaders<=MERGE_COUNT ); 1307 n = 0; 1308 for(i=0; i<nReaders; i++){ 1309 assert( pReaders[i].iType==pReaders[0].iType ); 1310 readers[i].pReader = pReaders+i; 1311 readers[i].idx = i; 1312 n += dlrAllDataBytes(&pReaders[i]); 1313 } 1314 /* Conservatively size output to sum of inputs. Output should end 1315 ** up strictly smaller than input. 1316 */ 1317 dataBufferExpand(out, n); 1318 1319 /* Get the readers into sorted order. */ 1320 while( i-->0 ){ 1321 orderedDLReaderReorder(readers+i, nReaders-i); 1322 } 1323 1324 dlwInit(&writer, pReaders[0].iType, out); 1325 while( !dlrAtEnd(readers[0].pReader) ){ 1326 sqlite_int64 iDocid = dlrDocid(readers[0].pReader); 1327 1328 /* If this is a continuation of the current buffer to copy, extend 1329 ** that buffer. memcpy() seems to be more efficient if it has a 1330 ** lots of data to copy. 1331 */ 1332 if( dlrDocData(readers[0].pReader)==pStart+nStart ){ 1333 nStart += dlrDocDataBytes(readers[0].pReader); 1334 }else{ 1335 if( pStart!=0 ){ 1336 rc = dlwAppend(&writer, pStart, nStart, iFirstDocid, iLastDocid); 1337 if( rc!=SQLITE_OK ) goto err; 1338 } 1339 pStart = dlrDocData(readers[0].pReader); 1340 nStart = dlrDocDataBytes(readers[0].pReader); 1341 iFirstDocid = iDocid; 1342 } 1343 iLastDocid = iDocid; 1344 rc = dlrStep(readers[0].pReader); 1345 if( rc!=SQLITE_OK ) goto err; 1346 1347 /* Drop all of the older elements with the same docid. */ 1348 for(i=1; i<nReaders && 1349 !dlrAtEnd(readers[i].pReader) && 1350 dlrDocid(readers[i].pReader)==iDocid; i++){ 1351 rc = dlrStep(readers[i].pReader); 1352 if( rc!=SQLITE_OK ) goto err; 1353 } 1354 1355 /* Get the readers back into order. */ 1356 while( i-->0 ){ 1357 orderedDLReaderReorder(readers+i, nReaders-i); 1358 } 1359 } 1360 1361 /* Copy over any remaining elements. */ 1362 if( nStart>0 ) 1363 rc = dlwAppend(&writer, pStart, nStart, iFirstDocid, iLastDocid); 1364 err: 1365 dlwDestroy(&writer); 1366 return rc; 1367 } 1368 1369 /* Helper function for posListUnion(). Compares the current position 1370 ** between left and right, returning as standard C idiom of <0 if 1371 ** left<right, >0 if left>right, and 0 if left==right. "End" always 1372 ** compares greater. 1373 */ 1374 static int posListCmp(PLReader *pLeft, PLReader *pRight){ 1375 assert( pLeft->iType==pRight->iType ); 1376 if( pLeft->iType==DL_DOCIDS ) return 0; 1377 1378 if( plrAtEnd(pLeft) ) return plrAtEnd(pRight) ? 0 : 1; 1379 if( plrAtEnd(pRight) ) return -1; 1380 1381 if( plrColumn(pLeft)<plrColumn(pRight) ) return -1; 1382 if( plrColumn(pLeft)>plrColumn(pRight) ) return 1; 1383 1384 if( plrPosition(pLeft)<plrPosition(pRight) ) return -1; 1385 if( plrPosition(pLeft)>plrPosition(pRight) ) return 1; 1386 if( pLeft->iType==DL_POSITIONS ) return 0; 1387 1388 if( plrStartOffset(pLeft)<plrStartOffset(pRight) ) return -1; 1389 if( plrStartOffset(pLeft)>plrStartOffset(pRight) ) return 1; 1390 1391 if( plrEndOffset(pLeft)<plrEndOffset(pRight) ) return -1; 1392 if( plrEndOffset(pLeft)>plrEndOffset(pRight) ) return 1; 1393 1394 return 0; 1395 } 1396 1397 /* Write the union of position lists in pLeft and pRight to pOut. 1398 ** "Union" in this case meaning "All unique position tuples". Should 1399 ** work with any doclist type, though both inputs and the output 1400 ** should be the same type. 1401 */ 1402 static int posListUnion(DLReader *pLeft, DLReader *pRight, DLWriter *pOut){ 1403 PLReader left, right; 1404 PLWriter writer; 1405 int rc; 1406 1407 assert( dlrDocid(pLeft)==dlrDocid(pRight) ); 1408 assert( pLeft->iType==pRight->iType ); 1409 assert( pLeft->iType==pOut->iType ); 1410 1411 rc = plrInit(&left, pLeft); 1412 if( rc != SQLITE_OK ) return rc; 1413 rc = plrInit(&right, pRight); 1414 if( rc != SQLITE_OK ){ 1415 plrDestroy(&left); 1416 return rc; 1417 } 1418 plwInit(&writer, pOut, dlrDocid(pLeft)); 1419 1420 while( !plrAtEnd(&left) || !plrAtEnd(&right) ){ 1421 int c = posListCmp(&left, &right); 1422 if( c<0 ){ 1423 plwCopy(&writer, &left); 1424 rc = plrStep(&left); 1425 if( rc != SQLITE_OK ) break; 1426 }else if( c>0 ){ 1427 plwCopy(&writer, &right); 1428 rc = plrStep(&right); 1429 if( rc != SQLITE_OK ) break; 1430 }else{ 1431 plwCopy(&writer, &left); 1432 rc = plrStep(&left); 1433 if( rc != SQLITE_OK ) break; 1434 rc = plrStep(&right); 1435 if( rc != SQLITE_OK ) break; 1436 } 1437 } 1438 1439 plwTerminate(&writer); 1440 plwDestroy(&writer); 1441 plrDestroy(&left); 1442 plrDestroy(&right); 1443 return rc; 1444 } 1445 1446 /* Write the union of doclists in pLeft and pRight to pOut. For 1447 ** docids in common between the inputs, the union of the position 1448 ** lists is written. Inputs and outputs are always type DL_DEFAULT. 1449 */ 1450 static int docListUnion( 1451 const char *pLeft, int nLeft, 1452 const char *pRight, int nRight, 1453 DataBuffer *pOut /* Write the combined doclist here */ 1454 ){ 1455 DLReader left, right; 1456 DLWriter writer; 1457 int rc; 1458 1459 if( nLeft==0 ){ 1460 if( nRight!=0) dataBufferAppend(pOut, pRight, nRight); 1461 return SQLITE_OK; 1462 } 1463 if( nRight==0 ){ 1464 dataBufferAppend(pOut, pLeft, nLeft); 1465 return SQLITE_OK; 1466 } 1467 1468 rc = dlrInit(&left, DL_DEFAULT, pLeft, nLeft); 1469 if( rc!=SQLITE_OK ) return rc; 1470 rc = dlrInit(&right, DL_DEFAULT, pRight, nRight); 1471 if( rc!=SQLITE_OK ){ 1472 dlrDestroy(&left); 1473 return rc; 1474 } 1475 dlwInit(&writer, DL_DEFAULT, pOut); 1476 1477 while( !dlrAtEnd(&left) || !dlrAtEnd(&right) ){ 1478 if( dlrAtEnd(&right) ){ 1479 rc = dlwCopy(&writer, &left); 1480 if( rc!=SQLITE_OK ) break; 1481 rc = dlrStep(&left); 1482 if( rc!=SQLITE_OK ) break; 1483 }else if( dlrAtEnd(&left) ){ 1484 rc = dlwCopy(&writer, &right); 1485 if( rc!=SQLITE_OK ) break; 1486 rc = dlrStep(&right); 1487 if( rc!=SQLITE_OK ) break; 1488 }else if( dlrDocid(&left)<dlrDocid(&right) ){ 1489 rc = dlwCopy(&writer, &left); 1490 if( rc!=SQLITE_OK ) break; 1491 rc = dlrStep(&left); 1492 if( rc!=SQLITE_OK ) break; 1493 }else if( dlrDocid(&left)>dlrDocid(&right) ){ 1494 rc = dlwCopy(&writer, &right); 1495 if( rc!=SQLITE_OK ) break; 1496 rc = dlrStep(&right); 1497 if( rc!=SQLITE_OK ) break; 1498 }else{ 1499 rc = posListUnion(&left, &right, &writer); 1500 if( rc!=SQLITE_OK ) break; 1501 rc = dlrStep(&left); 1502 if( rc!=SQLITE_OK ) break; 1503 rc = dlrStep(&right); 1504 if( rc!=SQLITE_OK ) break; 1505 } 1506 } 1507 1508 dlrDestroy(&left); 1509 dlrDestroy(&right); 1510 dlwDestroy(&writer); 1511 return rc; 1512 } 1513 1514 /* pLeft and pRight are DLReaders positioned to the same docid. 1515 ** 1516 ** If there are no instances in pLeft or pRight where the position 1517 ** of pLeft is one less than the position of pRight, then this 1518 ** routine adds nothing to pOut. 1519 ** 1520 ** If there are one or more instances where positions from pLeft 1521 ** are exactly one less than positions from pRight, then add a new 1522 ** document record to pOut. If pOut wants to hold positions, then 1523 ** include the positions from pRight that are one more than a 1524 ** position in pLeft. In other words: pRight.iPos==pLeft.iPos+1. 1525 */ 1526 static int posListPhraseMerge(DLReader *pLeft, DLReader *pRight, 1527 DLWriter *pOut){ 1528 PLReader left, right; 1529 PLWriter writer; 1530 int match = 0; 1531 int rc; 1532 1533 assert( dlrDocid(pLeft)==dlrDocid(pRight) ); 1534 assert( pOut->iType!=DL_POSITIONS_OFFSETS ); 1535 1536 rc = plrInit(&left, pLeft); 1537 if( rc!=SQLITE_OK ) return rc; 1538 rc = plrInit(&right, pRight); 1539 if( rc!=SQLITE_OK ){ 1540 plrDestroy(&left); 1541 return rc; 1542 } 1543 1544 while( !plrAtEnd(&left) && !plrAtEnd(&right) ){ 1545 if( plrColumn(&left)<plrColumn(&right) ){ 1546 rc = plrStep(&left); 1547 if( rc!=SQLITE_OK ) break; 1548 }else if( plrColumn(&left)>plrColumn(&right) ){ 1549 rc = plrStep(&right); 1550 if( rc!=SQLITE_OK ) break; 1551 }else if( plrPosition(&left)+1<plrPosition(&right) ){ 1552 rc = plrStep(&left); 1553 if( rc!=SQLITE_OK ) break; 1554 }else if( plrPosition(&left)+1>plrPosition(&right) ){ 1555 rc = plrStep(&right); 1556 if( rc!=SQLITE_OK ) break; 1557 }else{ 1558 if( !match ){ 1559 plwInit(&writer, pOut, dlrDocid(pLeft)); 1560 match = 1; 1561 } 1562 plwAdd(&writer, plrColumn(&right), plrPosition(&right), 0, 0); 1563 rc = plrStep(&left); 1564 if( rc!=SQLITE_OK ) break; 1565 rc = plrStep(&right); 1566 if( rc!=SQLITE_OK ) break; 1567 } 1568 } 1569 1570 if( match ){ 1571 plwTerminate(&writer); 1572 plwDestroy(&writer); 1573 } 1574 1575 plrDestroy(&left); 1576 plrDestroy(&right); 1577 return rc; 1578 } 1579 1580 /* We have two doclists with positions: pLeft and pRight. 1581 ** Write the phrase intersection of these two doclists into pOut. 1582 ** 1583 ** A phrase intersection means that two documents only match 1584 ** if pLeft.iPos+1==pRight.iPos. 1585 ** 1586 ** iType controls the type of data written to pOut. If iType is 1587 ** DL_POSITIONS, the positions are those from pRight. 1588 */ 1589 static int docListPhraseMerge( 1590 const char *pLeft, int nLeft, 1591 const char *pRight, int nRight, 1592 DocListType iType, 1593 DataBuffer *pOut /* Write the combined doclist here */ 1594 ){ 1595 DLReader left, right; 1596 DLWriter writer; 1597 int rc; 1598 1599 if( nLeft==0 || nRight==0 ) return SQLITE_OK; 1600 1601 assert( iType!=DL_POSITIONS_OFFSETS ); 1602 1603 rc = dlrInit(&left, DL_POSITIONS, pLeft, nLeft); 1604 if( rc!=SQLITE_OK ) return rc; 1605 rc = dlrInit(&right, DL_POSITIONS, pRight, nRight); 1606 if( rc!=SQLITE_OK ){ 1607 dlrDestroy(&left); 1608 return rc; 1609 } 1610 dlwInit(&writer, iType, pOut); 1611 1612 while( !dlrAtEnd(&left) && !dlrAtEnd(&right) ){ 1613 if( dlrDocid(&left)<dlrDocid(&right) ){ 1614 rc = dlrStep(&left); 1615 if( rc!=SQLITE_OK ) break; 1616 }else if( dlrDocid(&right)<dlrDocid(&left) ){ 1617 rc = dlrStep(&right); 1618 if( rc!=SQLITE_OK ) break; 1619 }else{ 1620 rc = posListPhraseMerge(&left, &right, &writer); 1621 if( rc!=SQLITE_OK ) break; 1622 rc = dlrStep(&left); 1623 if( rc!=SQLITE_OK ) break; 1624 rc = dlrStep(&right); 1625 if( rc!=SQLITE_OK ) break; 1626 } 1627 } 1628 1629 dlrDestroy(&left); 1630 dlrDestroy(&right); 1631 dlwDestroy(&writer); 1632 return rc; 1633 } 1634 1635 /* We have two DL_DOCIDS doclists: pLeft and pRight. 1636 ** Write the intersection of these two doclists into pOut as a 1637 ** DL_DOCIDS doclist. 1638 */ 1639 static int docListAndMerge( 1640 const char *pLeft, int nLeft, 1641 const char *pRight, int nRight, 1642 DataBuffer *pOut /* Write the combined doclist here */ 1643 ){ 1644 DLReader left, right; 1645 DLWriter writer; 1646 int rc; 1647 1648 if( nLeft==0 || nRight==0 ) return SQLITE_OK; 1649 1650 rc = dlrInit(&left, DL_DOCIDS, pLeft, nLeft); 1651 if( rc!=SQLITE_OK ) return rc; 1652 rc = dlrInit(&right, DL_DOCIDS, pRight, nRight); 1653 if( rc!=SQLITE_OK ){ 1654 dlrDestroy(&left); 1655 return rc; 1656 } 1657 dlwInit(&writer, DL_DOCIDS, pOut); 1658 1659 while( !dlrAtEnd(&left) && !dlrAtEnd(&right) ){ 1660 if( dlrDocid(&left)<dlrDocid(&right) ){ 1661 rc = dlrStep(&left); 1662 if( rc!=SQLITE_OK ) break; 1663 }else if( dlrDocid(&right)<dlrDocid(&left) ){ 1664 rc = dlrStep(&right); 1665 if( rc!=SQLITE_OK ) break; 1666 }else{ 1667 dlwAdd(&writer, dlrDocid(&left)); 1668 rc = dlrStep(&left); 1669 if( rc!=SQLITE_OK ) break; 1670 rc = dlrStep(&right); 1671 if( rc!=SQLITE_OK ) break; 1672 } 1673 } 1674 1675 dlrDestroy(&left); 1676 dlrDestroy(&right); 1677 dlwDestroy(&writer); 1678 return rc; 1679 } 1680 1681 /* We have two DL_DOCIDS doclists: pLeft and pRight. 1682 ** Write the union of these two doclists into pOut as a 1683 ** DL_DOCIDS doclist. 1684 */ 1685 static int docListOrMerge( 1686 const char *pLeft, int nLeft, 1687 const char *pRight, int nRight, 1688 DataBuffer *pOut /* Write the combined doclist here */ 1689 ){ 1690 DLReader left, right; 1691 DLWriter writer; 1692 int rc; 1693 1694 if( nLeft==0 ){ 1695 if( nRight!=0 ) dataBufferAppend(pOut, pRight, nRight); 1696 return SQLITE_OK; 1697 } 1698 if( nRight==0 ){ 1699 dataBufferAppend(pOut, pLeft, nLeft); 1700 return SQLITE_OK; 1701 } 1702 1703 rc = dlrInit(&left, DL_DOCIDS, pLeft, nLeft); 1704 if( rc!=SQLITE_OK ) return rc; 1705 rc = dlrInit(&right, DL_DOCIDS, pRight, nRight); 1706 if( rc!=SQLITE_OK ){ 1707 dlrDestroy(&left); 1708 return rc; 1709 } 1710 dlwInit(&writer, DL_DOCIDS, pOut); 1711 1712 while( !dlrAtEnd(&left) || !dlrAtEnd(&right) ){ 1713 if( dlrAtEnd(&right) ){ 1714 dlwAdd(&writer, dlrDocid(&left)); 1715 rc = dlrStep(&left); 1716 if( rc!=SQLITE_OK ) break; 1717 }else if( dlrAtEnd(&left) ){ 1718 dlwAdd(&writer, dlrDocid(&right)); 1719 rc = dlrStep(&right); 1720 if( rc!=SQLITE_OK ) break; 1721 }else if( dlrDocid(&left)<dlrDocid(&right) ){ 1722 dlwAdd(&writer, dlrDocid(&left)); 1723 rc = dlrStep(&left); 1724 if( rc!=SQLITE_OK ) break; 1725 }else if( dlrDocid(&right)<dlrDocid(&left) ){ 1726 dlwAdd(&writer, dlrDocid(&right)); 1727 rc = dlrStep(&right); 1728 if( rc!=SQLITE_OK ) break; 1729 }else{ 1730 dlwAdd(&writer, dlrDocid(&left)); 1731 rc = dlrStep(&left); 1732 if( rc!=SQLITE_OK ) break; 1733 rc = dlrStep(&right); 1734 if( rc!=SQLITE_OK ) break; 1735 } 1736 } 1737 1738 dlrDestroy(&left); 1739 dlrDestroy(&right); 1740 dlwDestroy(&writer); 1741 return rc; 1742 } 1743 1744 /* We have two DL_DOCIDS doclists: pLeft and pRight. 1745 ** Write into pOut as DL_DOCIDS doclist containing all documents that 1746 ** occur in pLeft but not in pRight. 1747 */ 1748 static int docListExceptMerge( 1749 const char *pLeft, int nLeft, 1750 const char *pRight, int nRight, 1751 DataBuffer *pOut /* Write the combined doclist here */ 1752 ){ 1753 DLReader left, right; 1754 DLWriter writer; 1755 int rc; 1756 1757 if( nLeft==0 ) return SQLITE_OK; 1758 if( nRight==0 ){ 1759 dataBufferAppend(pOut, pLeft, nLeft); 1760 return SQLITE_OK; 1761 } 1762 1763 rc = dlrInit(&left, DL_DOCIDS, pLeft, nLeft); 1764 if( rc!=SQLITE_OK ) return rc; 1765 rc = dlrInit(&right, DL_DOCIDS, pRight, nRight); 1766 if( rc!=SQLITE_OK ){ 1767 dlrDestroy(&left); 1768 return rc; 1769 } 1770 dlwInit(&writer, DL_DOCIDS, pOut); 1771 1772 while( !dlrAtEnd(&left) ){ 1773 while( !dlrAtEnd(&right) && dlrDocid(&right)<dlrDocid(&left) ){ 1774 rc = dlrStep(&right); 1775 if( rc!=SQLITE_OK ) goto err; 1776 } 1777 if( dlrAtEnd(&right) || dlrDocid(&left)<dlrDocid(&right) ){ 1778 dlwAdd(&writer, dlrDocid(&left)); 1779 } 1780 rc = dlrStep(&left); 1781 if( rc!=SQLITE_OK ) break; 1782 } 1783 1784 err: 1785 dlrDestroy(&left); 1786 dlrDestroy(&right); 1787 dlwDestroy(&writer); 1788 return rc; 1789 } 1790 1791 static char *string_dup_n(const char *s, int n){ 1792 char *str = sqlite3_malloc(n + 1); 1793 memcpy(str, s, n); 1794 str[n] = '\0'; 1795 return str; 1796 } 1797 1798 /* Duplicate a string; the caller must free() the returned string. 1799 * (We don't use strdup() since it is not part of the standard C library and 1800 * may not be available everywhere.) */ 1801 static char *string_dup(const char *s){ 1802 return string_dup_n(s, strlen(s)); 1803 } 1804 1805 /* Format a string, replacing each occurrence of the % character with 1806 * zDb.zName. This may be more convenient than sqlite_mprintf() 1807 * when one string is used repeatedly in a format string. 1808 * The caller must free() the returned string. */ 1809 static char *string_format(const char *zFormat, 1810 const char *zDb, const char *zName){ 1811 const char *p; 1812 size_t len = 0; 1813 size_t nDb = strlen(zDb); 1814 size_t nName = strlen(zName); 1815 size_t nFullTableName = nDb+1+nName; 1816 char *result; 1817 char *r; 1818 1819 /* first compute length needed */ 1820 for(p = zFormat ; *p ; ++p){ 1821 len += (*p=='%' ? nFullTableName : 1); 1822 } 1823 len += 1; /* for null terminator */ 1824 1825 r = result = sqlite3_malloc(len); 1826 for(p = zFormat; *p; ++p){ 1827 if( *p=='%' ){ 1828 memcpy(r, zDb, nDb); 1829 r += nDb; 1830 *r++ = '.'; 1831 memcpy(r, zName, nName); 1832 r += nName; 1833 } else { 1834 *r++ = *p; 1835 } 1836 } 1837 *r++ = '\0'; 1838 assert( r == result + len ); 1839 return result; 1840 } 1841 1842 static int sql_exec(sqlite3 *db, const char *zDb, const char *zName, 1843 const char *zFormat){ 1844 char *zCommand = string_format(zFormat, zDb, zName); 1845 int rc; 1846 TRACE(("FTS2 sql: %s\n", zCommand)); 1847 rc = sqlite3_exec(db, zCommand, NULL, 0, NULL); 1848 sqlite3_free(zCommand); 1849 return rc; 1850 } 1851 1852 static int sql_prepare(sqlite3 *db, const char *zDb, const char *zName, 1853 sqlite3_stmt **ppStmt, const char *zFormat){ 1854 char *zCommand = string_format(zFormat, zDb, zName); 1855 int rc; 1856 TRACE(("FTS2 prepare: %s\n", zCommand)); 1857 rc = sqlite3_prepare_v2(db, zCommand, -1, ppStmt, NULL); 1858 sqlite3_free(zCommand); 1859 return rc; 1860 } 1861 1862 /* end utility functions */ 1863 1864 /* Forward reference */ 1865 typedef struct fulltext_vtab fulltext_vtab; 1866 1867 /* A single term in a query is represented by an instances of 1868 ** the following structure. 1869 */ 1870 typedef struct QueryTerm { 1871 short int nPhrase; /* How many following terms are part of the same phrase */ 1872 short int iPhrase; /* This is the i-th term of a phrase. */ 1873 short int iColumn; /* Column of the index that must match this term */ 1874 signed char isOr; /* this term is preceded by "OR" */ 1875 signed char isNot; /* this term is preceded by "-" */ 1876 signed char isPrefix; /* this term is followed by "*" */ 1877 char *pTerm; /* text of the term. '\000' terminated. malloced */ 1878 int nTerm; /* Number of bytes in pTerm[] */ 1879 } QueryTerm; 1880 1881 1882 /* A query string is parsed into a Query structure. 1883 * 1884 * We could, in theory, allow query strings to be complicated 1885 * nested expressions with precedence determined by parentheses. 1886 * But none of the major search engines do this. (Perhaps the 1887 * feeling is that an parenthesized expression is two complex of 1888 * an idea for the average user to grasp.) Taking our lead from 1889 * the major search engines, we will allow queries to be a list 1890 * of terms (with an implied AND operator) or phrases in double-quotes, 1891 * with a single optional "-" before each non-phrase term to designate 1892 * negation and an optional OR connector. 1893 * 1894 * OR binds more tightly than the implied AND, which is what the 1895 * major search engines seem to do. So, for example: 1896 * 1897 * [one two OR three] ==> one AND (two OR three) 1898 * [one OR two three] ==> (one OR two) AND three 1899 * 1900 * A "-" before a term matches all entries that lack that term. 1901 * The "-" must occur immediately before the term with in intervening 1902 * space. This is how the search engines do it. 1903 * 1904 * A NOT term cannot be the right-hand operand of an OR. If this 1905 * occurs in the query string, the NOT is ignored: 1906 * 1907 * [one OR -two] ==> one OR two 1908 * 1909 */ 1910 typedef struct Query { 1911 fulltext_vtab *pFts; /* The full text index */ 1912 int nTerms; /* Number of terms in the query */ 1913 QueryTerm *pTerms; /* Array of terms. Space obtained from malloc() */ 1914 int nextIsOr; /* Set the isOr flag on the next inserted term */ 1915 int nextColumn; /* Next word parsed must be in this column */ 1916 int dfltColumn; /* The default column */ 1917 } Query; 1918 1919 1920 /* 1921 ** An instance of the following structure keeps track of generated 1922 ** matching-word offset information and snippets. 1923 */ 1924 typedef struct Snippet { 1925 int nMatch; /* Total number of matches */ 1926 int nAlloc; /* Space allocated for aMatch[] */ 1927 struct snippetMatch { /* One entry for each matching term */ 1928 char snStatus; /* Status flag for use while constructing snippets */ 1929 short int iCol; /* The column that contains the match */ 1930 short int iTerm; /* The index in Query.pTerms[] of the matching term */ 1931 short int nByte; /* Number of bytes in the term */ 1932 int iStart; /* The offset to the first character of the term */ 1933 } *aMatch; /* Points to space obtained from malloc */ 1934 char *zOffset; /* Text rendering of aMatch[] */ 1935 int nOffset; /* strlen(zOffset) */ 1936 char *zSnippet; /* Snippet text */ 1937 int nSnippet; /* strlen(zSnippet) */ 1938 } Snippet; 1939 1940 1941 typedef enum QueryType { 1942 QUERY_GENERIC, /* table scan */ 1943 QUERY_ROWID, /* lookup by rowid */ 1944 QUERY_FULLTEXT /* QUERY_FULLTEXT + [i] is a full-text search for column i*/ 1945 } QueryType; 1946 1947 typedef enum fulltext_statement { 1948 CONTENT_INSERT_STMT, 1949 CONTENT_SELECT_STMT, 1950 CONTENT_UPDATE_STMT, 1951 CONTENT_DELETE_STMT, 1952 CONTENT_EXISTS_STMT, 1953 1954 BLOCK_INSERT_STMT, 1955 BLOCK_SELECT_STMT, 1956 BLOCK_DELETE_STMT, 1957 BLOCK_DELETE_ALL_STMT, 1958 1959 SEGDIR_MAX_INDEX_STMT, 1960 SEGDIR_SET_STMT, 1961 SEGDIR_SELECT_LEVEL_STMT, 1962 SEGDIR_SPAN_STMT, 1963 SEGDIR_DELETE_STMT, 1964 SEGDIR_SELECT_SEGMENT_STMT, 1965 SEGDIR_SELECT_ALL_STMT, 1966 SEGDIR_DELETE_ALL_STMT, 1967 SEGDIR_COUNT_STMT, 1968 1969 MAX_STMT /* Always at end! */ 1970 } fulltext_statement; 1971 1972 /* These must exactly match the enum above. */ 1973 /* TODO(shess): Is there some risk that a statement will be used in two 1974 ** cursors at once, e.g. if a query joins a virtual table to itself? 1975 ** If so perhaps we should move some of these to the cursor object. 1976 */ 1977 static const char *const fulltext_zStatement[MAX_STMT] = { 1978 /* CONTENT_INSERT */ NULL, /* generated in contentInsertStatement() */ 1979 /* CONTENT_SELECT */ "select * from %_content where rowid = ?", 1980 /* CONTENT_UPDATE */ NULL, /* generated in contentUpdateStatement() */ 1981 /* CONTENT_DELETE */ "delete from %_content where rowid = ?", 1982 /* CONTENT_EXISTS */ "select rowid from %_content limit 1", 1983 1984 /* BLOCK_INSERT */ "insert into %_segments values (?)", 1985 /* BLOCK_SELECT */ "select block from %_segments where rowid = ?", 1986 /* BLOCK_DELETE */ "delete from %_segments where rowid between ? and ?", 1987 /* BLOCK_DELETE_ALL */ "delete from %_segments", 1988 1989 /* SEGDIR_MAX_INDEX */ "select max(idx) from %_segdir where level = ?", 1990 /* SEGDIR_SET */ "insert into %_segdir values (?, ?, ?, ?, ?, ?)", 1991 /* SEGDIR_SELECT_LEVEL */ 1992 "select start_block, leaves_end_block, root, idx from %_segdir " 1993 " where level = ? order by idx", 1994 /* SEGDIR_SPAN */ 1995 "select min(start_block), max(end_block) from %_segdir " 1996 " where level = ? and start_block <> 0", 1997 /* SEGDIR_DELETE */ "delete from %_segdir where level = ?", 1998 1999 /* NOTE(shess): The first three results of the following two 2000 ** statements must match. 2001 */ 2002 /* SEGDIR_SELECT_SEGMENT */ 2003 "select start_block, leaves_end_block, root from %_segdir " 2004 " where level = ? and idx = ?", 2005 /* SEGDIR_SELECT_ALL */ 2006 "select start_block, leaves_end_block, root from %_segdir " 2007 " order by level desc, idx asc", 2008 /* SEGDIR_DELETE_ALL */ "delete from %_segdir", 2009 /* SEGDIR_COUNT */ "select count(*), ifnull(max(level),0) from %_segdir", 2010 }; 2011 2012 /* 2013 ** A connection to a fulltext index is an instance of the following 2014 ** structure. The xCreate and xConnect methods create an instance 2015 ** of this structure and xDestroy and xDisconnect free that instance. 2016 ** All other methods receive a pointer to the structure as one of their 2017 ** arguments. 2018 */ 2019 struct fulltext_vtab { 2020 sqlite3_vtab base; /* Base class used by SQLite core */ 2021 sqlite3 *db; /* The database connection */ 2022 const char *zDb; /* logical database name */ 2023 const char *zName; /* virtual table name */ 2024 int nColumn; /* number of columns in virtual table */ 2025 char **azColumn; /* column names. malloced */ 2026 char **azContentColumn; /* column names in content table; malloced */ 2027 sqlite3_tokenizer *pTokenizer; /* tokenizer for inserts and queries */ 2028 2029 /* Precompiled statements which we keep as long as the table is 2030 ** open. 2031 */ 2032 sqlite3_stmt *pFulltextStatements[MAX_STMT]; 2033 2034 /* Precompiled statements used for segment merges. We run a 2035 ** separate select across the leaf level of each tree being merged. 2036 */ 2037 sqlite3_stmt *pLeafSelectStmts[MERGE_COUNT]; 2038 /* The statement used to prepare pLeafSelectStmts. */ 2039 #define LEAF_SELECT \ 2040 "select block from %_segments where rowid between ? and ? order by rowid" 2041 2042 /* These buffer pending index updates during transactions. 2043 ** nPendingData estimates the memory size of the pending data. It 2044 ** doesn't include the hash-bucket overhead, nor any malloc 2045 ** overhead. When nPendingData exceeds kPendingThreshold, the 2046 ** buffer is flushed even before the transaction closes. 2047 ** pendingTerms stores the data, and is only valid when nPendingData 2048 ** is >=0 (nPendingData<0 means pendingTerms has not been 2049 ** initialized). iPrevDocid is the last docid written, used to make 2050 ** certain we're inserting in sorted order. 2051 */ 2052 int nPendingData; 2053 #define kPendingThreshold (1*1024*1024) 2054 sqlite_int64 iPrevDocid; 2055 fts2Hash pendingTerms; 2056 }; 2057 2058 /* 2059 ** When the core wants to do a query, it create a cursor using a 2060 ** call to xOpen. This structure is an instance of a cursor. It 2061 ** is destroyed by xClose. 2062 */ 2063 typedef struct fulltext_cursor { 2064 sqlite3_vtab_cursor base; /* Base class used by SQLite core */ 2065 QueryType iCursorType; /* Copy of sqlite3_index_info.idxNum */ 2066 sqlite3_stmt *pStmt; /* Prepared statement in use by the cursor */ 2067 int eof; /* True if at End Of Results */ 2068 Query q; /* Parsed query string */ 2069 Snippet snippet; /* Cached snippet for the current row */ 2070 int iColumn; /* Column being searched */ 2071 DataBuffer result; /* Doclist results from fulltextQuery */ 2072 DLReader reader; /* Result reader if result not empty */ 2073 } fulltext_cursor; 2074 2075 static struct fulltext_vtab *cursor_vtab(fulltext_cursor *c){ 2076 return (fulltext_vtab *) c->base.pVtab; 2077 } 2078 2079 static const sqlite3_module fts2Module; /* forward declaration */ 2080 2081 /* Return a dynamically generated statement of the form 2082 * insert into %_content (rowid, ...) values (?, ...) 2083 */ 2084 static const char *contentInsertStatement(fulltext_vtab *v){ 2085 StringBuffer sb; 2086 int i; 2087 2088 initStringBuffer(&sb); 2089 append(&sb, "insert into %_content (rowid, "); 2090 appendList(&sb, v->nColumn, v->azContentColumn); 2091 append(&sb, ") values (?"); 2092 for(i=0; i<v->nColumn; ++i) 2093 append(&sb, ", ?"); 2094 append(&sb, ")"); 2095 return stringBufferData(&sb); 2096 } 2097 2098 /* Return a dynamically generated statement of the form 2099 * update %_content set [col_0] = ?, [col_1] = ?, ... 2100 * where rowid = ? 2101 */ 2102 static const char *contentUpdateStatement(fulltext_vtab *v){ 2103 StringBuffer sb; 2104 int i; 2105 2106 initStringBuffer(&sb); 2107 append(&sb, "update %_content set "); 2108 for(i=0; i<v->nColumn; ++i) { 2109 if( i>0 ){ 2110 append(&sb, ", "); 2111 } 2112 append(&sb, v->azContentColumn[i]); 2113 append(&sb, " = ?"); 2114 } 2115 append(&sb, " where rowid = ?"); 2116 return stringBufferData(&sb); 2117 } 2118 2119 /* Puts a freshly-prepared statement determined by iStmt in *ppStmt. 2120 ** If the indicated statement has never been prepared, it is prepared 2121 ** and cached, otherwise the cached version is reset. 2122 */ 2123 static int sql_get_statement(fulltext_vtab *v, fulltext_statement iStmt, 2124 sqlite3_stmt **ppStmt){ 2125 assert( iStmt<MAX_STMT ); 2126 if( v->pFulltextStatements[iStmt]==NULL ){ 2127 const char *zStmt; 2128 int rc; 2129 switch( iStmt ){ 2130 case CONTENT_INSERT_STMT: 2131 zStmt = contentInsertStatement(v); break; 2132 case CONTENT_UPDATE_STMT: 2133 zStmt = contentUpdateStatement(v); break; 2134 default: 2135 zStmt = fulltext_zStatement[iStmt]; 2136 } 2137 rc = sql_prepare(v->db, v->zDb, v->zName, &v->pFulltextStatements[iStmt], 2138 zStmt); 2139 if( zStmt != fulltext_zStatement[iStmt]) sqlite3_free((void *) zStmt); 2140 if( rc!=SQLITE_OK ) return rc; 2141 } else { 2142 int rc = sqlite3_reset(v->pFulltextStatements[iStmt]); 2143 if( rc!=SQLITE_OK ) return rc; 2144 } 2145 2146 *ppStmt = v->pFulltextStatements[iStmt]; 2147 return SQLITE_OK; 2148 } 2149 2150 /* Like sqlite3_step(), but convert SQLITE_DONE to SQLITE_OK and 2151 ** SQLITE_ROW to SQLITE_ERROR. Useful for statements like UPDATE, 2152 ** where we expect no results. 2153 */ 2154 static int sql_single_step(sqlite3_stmt *s){ 2155 int rc = sqlite3_step(s); 2156 return (rc==SQLITE_DONE) ? SQLITE_OK : rc; 2157 } 2158 2159 /* Like sql_get_statement(), but for special replicated LEAF_SELECT 2160 ** statements. idx -1 is a special case for an uncached version of 2161 ** the statement (used in the optimize implementation). 2162 */ 2163 /* TODO(shess) Write version for generic statements and then share 2164 ** that between the cached-statement functions. 2165 */ 2166 static int sql_get_leaf_statement(fulltext_vtab *v, int idx, 2167 sqlite3_stmt **ppStmt){ 2168 assert( idx>=-1 && idx<MERGE_COUNT ); 2169 if( idx==-1 ){ 2170 return sql_prepare(v->db, v->zDb, v->zName, ppStmt, LEAF_SELECT); 2171 }else if( v->pLeafSelectStmts[idx]==NULL ){ 2172 int rc = sql_prepare(v->db, v->zDb, v->zName, &v->pLeafSelectStmts[idx], 2173 LEAF_SELECT); 2174 if( rc!=SQLITE_OK ) return rc; 2175 }else{ 2176 int rc = sqlite3_reset(v->pLeafSelectStmts[idx]); 2177 if( rc!=SQLITE_OK ) return rc; 2178 } 2179 2180 *ppStmt = v->pLeafSelectStmts[idx]; 2181 return SQLITE_OK; 2182 } 2183 2184 /* insert into %_content (rowid, ...) values ([rowid], [pValues]) */ 2185 static int content_insert(fulltext_vtab *v, sqlite3_value *rowid, 2186 sqlite3_value **pValues){ 2187 sqlite3_stmt *s; 2188 int i; 2189 int rc = sql_get_statement(v, CONTENT_INSERT_STMT, &s); 2190 if( rc!=SQLITE_OK ) return rc; 2191 2192 rc = sqlite3_bind_value(s, 1, rowid); 2193 if( rc!=SQLITE_OK ) return rc; 2194 2195 for(i=0; i<v->nColumn; ++i){ 2196 rc = sqlite3_bind_value(s, 2+i, pValues[i]); 2197 if( rc!=SQLITE_OK ) return rc; 2198 } 2199 2200 return sql_single_step(s); 2201 } 2202 2203 /* update %_content set col0 = pValues[0], col1 = pValues[1], ... 2204 * where rowid = [iRowid] */ 2205 static int content_update(fulltext_vtab *v, sqlite3_value **pValues, 2206 sqlite_int64 iRowid){ 2207 sqlite3_stmt *s; 2208 int i; 2209 int rc = sql_get_statement(v, CONTENT_UPDATE_STMT, &s); 2210 if( rc!=SQLITE_OK ) return rc; 2211 2212 for(i=0; i<v->nColumn; ++i){ 2213 rc = sqlite3_bind_value(s, 1+i, pValues[i]); 2214 if( rc!=SQLITE_OK ) return rc; 2215 } 2216 2217 rc = sqlite3_bind_int64(s, 1+v->nColumn, iRowid); 2218 if( rc!=SQLITE_OK ) return rc; 2219 2220 return sql_single_step(s); 2221 } 2222 2223 static void freeStringArray(int nString, const char **pString){ 2224 int i; 2225 2226 for (i=0 ; i < nString ; ++i) { 2227 if( pString[i]!=NULL ) sqlite3_free((void *) pString[i]); 2228 } 2229 sqlite3_free((void *) pString); 2230 } 2231 2232 /* select * from %_content where rowid = [iRow] 2233 * The caller must delete the returned array and all strings in it. 2234 * null fields will be NULL in the returned array. 2235 * 2236 * TODO: Perhaps we should return pointer/length strings here for consistency 2237 * with other code which uses pointer/length. */ 2238 static int content_select(fulltext_vtab *v, sqlite_int64 iRow, 2239 const char ***pValues){ 2240 sqlite3_stmt *s; 2241 const char **values; 2242 int i; 2243 int rc; 2244 2245 *pValues = NULL; 2246 2247 rc = sql_get_statement(v, CONTENT_SELECT_STMT, &s); 2248 if( rc!=SQLITE_OK ) return rc; 2249 2250 rc = sqlite3_bind_int64(s, 1, iRow); 2251 if( rc!=SQLITE_OK ) return rc; 2252 2253 rc = sqlite3_step(s); 2254 if( rc!=SQLITE_ROW ) return rc; 2255 2256 values = (const char **) sqlite3_malloc(v->nColumn * sizeof(const char *)); 2257 for(i=0; i<v->nColumn; ++i){ 2258 if( sqlite3_column_type(s, i)==SQLITE_NULL ){ 2259 values[i] = NULL; 2260 }else{ 2261 values[i] = string_dup((char*)sqlite3_column_text(s, i)); 2262 } 2263 } 2264 2265 /* We expect only one row. We must execute another sqlite3_step() 2266 * to complete the iteration; otherwise the table will remain locked. */ 2267 rc = sqlite3_step(s); 2268 if( rc==SQLITE_DONE ){ 2269 *pValues = values; 2270 return SQLITE_OK; 2271 } 2272 2273 freeStringArray(v->nColumn, values); 2274 return rc; 2275 } 2276 2277 /* delete from %_content where rowid = [iRow ] */ 2278 static int content_delete(fulltext_vtab *v, sqlite_int64 iRow){ 2279 sqlite3_stmt *s; 2280 int rc = sql_get_statement(v, CONTENT_DELETE_STMT, &s); 2281 if( rc!=SQLITE_OK ) return rc; 2282 2283 rc = sqlite3_bind_int64(s, 1, iRow); 2284 if( rc!=SQLITE_OK ) return rc; 2285 2286 return sql_single_step(s); 2287 } 2288 2289 /* Returns SQLITE_ROW if any rows exist in %_content, SQLITE_DONE if 2290 ** no rows exist, and any error in case of failure. 2291 */ 2292 static int content_exists(fulltext_vtab *v){ 2293 sqlite3_stmt *s; 2294 int rc = sql_get_statement(v, CONTENT_EXISTS_STMT, &s); 2295 if( rc!=SQLITE_OK ) return rc; 2296 2297 rc = sqlite3_step(s); 2298 if( rc!=SQLITE_ROW ) return rc; 2299 2300 /* We expect only one row. We must execute another sqlite3_step() 2301 * to complete the iteration; otherwise the table will remain locked. */ 2302 rc = sqlite3_step(s); 2303 if( rc==SQLITE_DONE ) return SQLITE_ROW; 2304 if( rc==SQLITE_ROW ) return SQLITE_ERROR; 2305 return rc; 2306 } 2307 2308 /* insert into %_segments values ([pData]) 2309 ** returns assigned rowid in *piBlockid 2310 */ 2311 static int block_insert(fulltext_vtab *v, const char *pData, int nData, 2312 sqlite_int64 *piBlockid){ 2313 sqlite3_stmt *s; 2314 int rc = sql_get_statement(v, BLOCK_INSERT_STMT, &s); 2315 if( rc!=SQLITE_OK ) return rc; 2316 2317 rc = sqlite3_bind_blob(s, 1, pData, nData, SQLITE_STATIC); 2318 if( rc!=SQLITE_OK ) return rc; 2319 2320 rc = sqlite3_step(s); 2321 if( rc==SQLITE_ROW ) return SQLITE_ERROR; 2322 if( rc!=SQLITE_DONE ) return rc; 2323 2324 *piBlockid = sqlite3_last_insert_rowid(v->db); 2325 return SQLITE_OK; 2326 } 2327 2328 /* delete from %_segments 2329 ** where rowid between [iStartBlockid] and [iEndBlockid] 2330 ** 2331 ** Deletes the range of blocks, inclusive, used to delete the blocks 2332 ** which form a segment. 2333 */ 2334 static int block_delete(fulltext_vtab *v, 2335 sqlite_int64 iStartBlockid, sqlite_int64 iEndBlockid){ 2336 sqlite3_stmt *s; 2337 int rc = sql_get_statement(v, BLOCK_DELETE_STMT, &s); 2338 if( rc!=SQLITE_OK ) return rc; 2339 2340 rc = sqlite3_bind_int64(s, 1, iStartBlockid); 2341 if( rc!=SQLITE_OK ) return rc; 2342 2343 rc = sqlite3_bind_int64(s, 2, iEndBlockid); 2344 if( rc!=SQLITE_OK ) return rc; 2345 2346 return sql_single_step(s); 2347 } 2348 2349 /* Returns SQLITE_ROW with *pidx set to the maximum segment idx found 2350 ** at iLevel. Returns SQLITE_DONE if there are no segments at 2351 ** iLevel. Otherwise returns an error. 2352 */ 2353 static int segdir_max_index(fulltext_vtab *v, int iLevel, int *pidx){ 2354 sqlite3_stmt *s; 2355 int rc = sql_get_statement(v, SEGDIR_MAX_INDEX_STMT, &s); 2356 if( rc!=SQLITE_OK ) return rc; 2357 2358 rc = sqlite3_bind_int(s, 1, iLevel); 2359 if( rc!=SQLITE_OK ) return rc; 2360 2361 rc = sqlite3_step(s); 2362 /* Should always get at least one row due to how max() works. */ 2363 if( rc==SQLITE_DONE ) return SQLITE_DONE; 2364 if( rc!=SQLITE_ROW ) return rc; 2365 2366 /* NULL means that there were no inputs to max(). */ 2367 if( SQLITE_NULL==sqlite3_column_type(s, 0) ){ 2368 rc = sqlite3_step(s); 2369 if( rc==SQLITE_ROW ) return SQLITE_ERROR; 2370 return rc; 2371 } 2372 2373 *pidx = sqlite3_column_int(s, 0); 2374 2375 /* We expect only one row. We must execute another sqlite3_step() 2376 * to complete the iteration; otherwise the table will remain locked. */ 2377 rc = sqlite3_step(s); 2378 if( rc==SQLITE_ROW ) return SQLITE_ERROR; 2379 if( rc!=SQLITE_DONE ) return rc; 2380 return SQLITE_ROW; 2381 } 2382 2383 /* insert into %_segdir values ( 2384 ** [iLevel], [idx], 2385 ** [iStartBlockid], [iLeavesEndBlockid], [iEndBlockid], 2386 ** [pRootData] 2387 ** ) 2388 */ 2389 static int segdir_set(fulltext_vtab *v, int iLevel, int idx, 2390 sqlite_int64 iStartBlockid, 2391 sqlite_int64 iLeavesEndBlockid, 2392 sqlite_int64 iEndBlockid, 2393 const char *pRootData, int nRootData){ 2394 sqlite3_stmt *s; 2395 int rc = sql_get_statement(v, SEGDIR_SET_STMT, &s); 2396 if( rc!=SQLITE_OK ) return rc; 2397 2398 rc = sqlite3_bind_int(s, 1, iLevel); 2399 if( rc!=SQLITE_OK ) return rc; 2400 2401 rc = sqlite3_bind_int(s, 2, idx); 2402 if( rc!=SQLITE_OK ) return rc; 2403 2404 rc = sqlite3_bind_int64(s, 3, iStartBlockid); 2405 if( rc!=SQLITE_OK ) return rc; 2406 2407 rc = sqlite3_bind_int64(s, 4, iLeavesEndBlockid); 2408 if( rc!=SQLITE_OK ) return rc; 2409 2410 rc = sqlite3_bind_int64(s, 5, iEndBlockid); 2411 if( rc!=SQLITE_OK ) return rc; 2412 2413 rc = sqlite3_bind_blob(s, 6, pRootData, nRootData, SQLITE_STATIC); 2414 if( rc!=SQLITE_OK ) return rc; 2415 2416 return sql_single_step(s); 2417 } 2418 2419 /* Queries %_segdir for the block span of the segments in level 2420 ** iLevel. Returns SQLITE_DONE if there are no blocks for iLevel, 2421 ** SQLITE_ROW if there are blocks, else an error. 2422 */ 2423 static int segdir_span(fulltext_vtab *v, int iLevel, 2424 sqlite_int64 *piStartBlockid, 2425 sqlite_int64 *piEndBlockid){ 2426 sqlite3_stmt *s; 2427 int rc = sql_get_statement(v, SEGDIR_SPAN_STMT, &s); 2428 if( rc!=SQLITE_OK ) return rc; 2429 2430 rc = sqlite3_bind_int(s, 1, iLevel); 2431 if( rc!=SQLITE_OK ) return rc; 2432 2433 rc = sqlite3_step(s); 2434 if( rc==SQLITE_DONE ) return SQLITE_DONE; /* Should never happen */ 2435 if( rc!=SQLITE_ROW ) return rc; 2436 2437 /* This happens if all segments at this level are entirely inline. */ 2438 if( SQLITE_NULL==sqlite3_column_type(s, 0) ){ 2439 /* We expect only one row. We must execute another sqlite3_step() 2440 * to complete the iteration; otherwise the table will remain locked. */ 2441 int rc2 = sqlite3_step(s); 2442 if( rc2==SQLITE_ROW ) return SQLITE_ERROR; 2443 return rc2; 2444 } 2445 2446 *piStartBlockid = sqlite3_column_int64(s, 0); 2447 *piEndBlockid = sqlite3_column_int64(s, 1); 2448 2449 /* We expect only one row. We must execute another sqlite3_step() 2450 * to complete the iteration; otherwise the table will remain locked. */ 2451 rc = sqlite3_step(s); 2452 if( rc==SQLITE_ROW ) return SQLITE_ERROR; 2453 if( rc!=SQLITE_DONE ) return rc; 2454 return SQLITE_ROW; 2455 } 2456 2457 /* Delete the segment blocks and segment directory records for all 2458 ** segments at iLevel. 2459 */ 2460 static int segdir_delete(fulltext_vtab *v, int iLevel){ 2461 sqlite3_stmt *s; 2462 sqlite_int64 iStartBlockid, iEndBlockid; 2463 int rc = segdir_span(v, iLevel, &iStartBlockid, &iEndBlockid); 2464 if( rc!=SQLITE_ROW && rc!=SQLITE_DONE ) return rc; 2465 2466 if( rc==SQLITE_ROW ){ 2467 rc = block_delete(v, iStartBlockid, iEndBlockid); 2468 if( rc!=SQLITE_OK ) return rc; 2469 } 2470 2471 /* Delete the segment directory itself. */ 2472 rc = sql_get_statement(v, SEGDIR_DELETE_STMT, &s); 2473 if( rc!=SQLITE_OK ) return rc; 2474 2475 rc = sqlite3_bind_int64(s, 1, iLevel); 2476 if( rc!=SQLITE_OK ) return rc; 2477 2478 return sql_single_step(s); 2479 } 2480 2481 /* Delete entire fts index, SQLITE_OK on success, relevant error on 2482 ** failure. 2483 */ 2484 static int segdir_delete_all(fulltext_vtab *v){ 2485 sqlite3_stmt *s; 2486 int rc = sql_get_statement(v, SEGDIR_DELETE_ALL_STMT, &s); 2487 if( rc!=SQLITE_OK ) return rc; 2488 2489 rc = sql_single_step(s); 2490 if( rc!=SQLITE_OK ) return rc; 2491 2492 rc = sql_get_statement(v, BLOCK_DELETE_ALL_STMT, &s); 2493 if( rc!=SQLITE_OK ) return rc; 2494 2495 return sql_single_step(s); 2496 } 2497 2498 /* Returns SQLITE_OK with *pnSegments set to the number of entries in 2499 ** %_segdir and *piMaxLevel set to the highest level which has a 2500 ** segment. Otherwise returns the SQLite error which caused failure. 2501 */ 2502 static int segdir_count(fulltext_vtab *v, int *pnSegments, int *piMaxLevel){ 2503 sqlite3_stmt *s; 2504 int rc = sql_get_statement(v, SEGDIR_COUNT_STMT, &s); 2505 if( rc!=SQLITE_OK ) return rc; 2506 2507 rc = sqlite3_step(s); 2508 /* TODO(shess): This case should not be possible? Should stronger 2509 ** measures be taken if it happens? 2510 */ 2511 if( rc==SQLITE_DONE ){ 2512 *pnSegments = 0; 2513 *piMaxLevel = 0; 2514 return SQLITE_OK; 2515 } 2516 if( rc!=SQLITE_ROW ) return rc; 2517 2518 *pnSegments = sqlite3_column_int(s, 0); 2519 *piMaxLevel = sqlite3_column_int(s, 1); 2520 2521 /* We expect only one row. We must execute another sqlite3_step() 2522 * to complete the iteration; otherwise the table will remain locked. */ 2523 rc = sqlite3_step(s); 2524 if( rc==SQLITE_DONE ) return SQLITE_OK; 2525 if( rc==SQLITE_ROW ) return SQLITE_ERROR; 2526 return rc; 2527 } 2528 2529 /* TODO(shess) clearPendingTerms() is far down the file because 2530 ** writeZeroSegment() is far down the file because LeafWriter is far 2531 ** down the file. Consider refactoring the code to move the non-vtab 2532 ** code above the vtab code so that we don't need this forward 2533 ** reference. 2534 */ 2535 static int clearPendingTerms(fulltext_vtab *v); 2536 2537 /* 2538 ** Free the memory used to contain a fulltext_vtab structure. 2539 */ 2540 static void fulltext_vtab_destroy(fulltext_vtab *v){ 2541 int iStmt, i; 2542 2543 TRACE(("FTS2 Destroy %p\n", v)); 2544 for( iStmt=0; iStmt<MAX_STMT; iStmt++ ){ 2545 if( v->pFulltextStatements[iStmt]!=NULL ){ 2546 sqlite3_finalize(v->pFulltextStatements[iStmt]); 2547 v->pFulltextStatements[iStmt] = NULL; 2548 } 2549 } 2550 2551 for( i=0; i<MERGE_COUNT; i++ ){ 2552 if( v->pLeafSelectStmts[i]!=NULL ){ 2553 sqlite3_finalize(v->pLeafSelectStmts[i]); 2554 v->pLeafSelectStmts[i] = NULL; 2555 } 2556 } 2557 2558 if( v->pTokenizer!=NULL ){ 2559 v->pTokenizer->pModule->xDestroy(v->pTokenizer); 2560 v->pTokenizer = NULL; 2561 } 2562 2563 clearPendingTerms(v); 2564 2565 sqlite3_free(v->azColumn); 2566 for(i = 0; i < v->nColumn; ++i) { 2567 sqlite3_free(v->azContentColumn[i]); 2568 } 2569 sqlite3_free(v->azContentColumn); 2570 sqlite3_free(v); 2571 } 2572 2573 /* 2574 ** Token types for parsing the arguments to xConnect or xCreate. 2575 */ 2576 #define TOKEN_EOF 0 /* End of file */ 2577 #define TOKEN_SPACE 1 /* Any kind of whitespace */ 2578 #define TOKEN_ID 2 /* An identifier */ 2579 #define TOKEN_STRING 3 /* A string literal */ 2580 #define TOKEN_PUNCT 4 /* A single punctuation character */ 2581 2582 /* 2583 ** If X is a character that can be used in an identifier then 2584 ** IdChar(X) will be true. Otherwise it is false. 2585 ** 2586 ** For ASCII, any character with the high-order bit set is 2587 ** allowed in an identifier. For 7-bit characters, 2588 ** sqlite3IsIdChar[X] must be 1. 2589 ** 2590 ** Ticket #1066. the SQL standard does not allow '$' in the 2591 ** middle of identfiers. But many SQL implementations do. 2592 ** SQLite will allow '$' in identifiers for compatibility. 2593 ** But the feature is undocumented. 2594 */ 2595 static const char isIdChar[] = { 2596 /* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF */ 2597 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 2x */ 2598 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, /* 3x */ 2599 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 4x */ 2600 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, /* 5x */ 2601 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 6x */ 2602 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, /* 7x */ 2603 }; 2604 #define IdChar(C) (((c=C)&0x80)!=0 || (c>0x1f && isIdChar[c-0x20])) 2605 2606 2607 /* 2608 ** Return the length of the token that begins at z[0]. 2609 ** Store the token type in *tokenType before returning. 2610 */ 2611 static int getToken(const char *z, int *tokenType){ 2612 int i, c; 2613 switch( *z ){ 2614 case 0: { 2615 *tokenType = TOKEN_EOF; 2616 return 0; 2617 } 2618 case ' ': case '\t': case '\n': case '\f': case '\r': { 2619 for(i=1; safe_isspace(z[i]); i++){} 2620 *tokenType = TOKEN_SPACE; 2621 return i; 2622 } 2623 case '`': 2624 case '\'': 2625 case '"': { 2626 int delim = z[0]; 2627 for(i=1; (c=z[i])!=0; i++){ 2628 if( c==delim ){ 2629 if( z[i+1]==delim ){ 2630 i++; 2631 }else{ 2632 break; 2633 } 2634 } 2635 } 2636 *tokenType = TOKEN_STRING; 2637 return i + (c!=0); 2638 } 2639 case '[': { 2640 for(i=1, c=z[0]; c!=']' && (c=z[i])!=0; i++){} 2641 *tokenType = TOKEN_ID; 2642 return i; 2643 } 2644 default: { 2645 if( !IdChar(*z) ){ 2646 break; 2647 } 2648 for(i=1; IdChar(z[i]); i++){} 2649 *tokenType = TOKEN_ID; 2650 return i; 2651 } 2652 } 2653 *tokenType = TOKEN_PUNCT; 2654 return 1; 2655 } 2656 2657 /* 2658 ** A token extracted from a string is an instance of the following 2659 ** structure. 2660 */ 2661 typedef struct Token { 2662 const char *z; /* Pointer to token text. Not '\000' terminated */ 2663 short int n; /* Length of the token text in bytes. */ 2664 } Token; 2665 2666 /* 2667 ** Given a input string (which is really one of the argv[] parameters 2668 ** passed into xConnect or xCreate) split the string up into tokens. 2669 ** Return an array of pointers to '\000' terminated strings, one string 2670 ** for each non-whitespace token. 2671 ** 2672 ** The returned array is terminated by a single NULL pointer. 2673 ** 2674 ** Space to hold the returned array is obtained from a single 2675 ** malloc and should be freed by passing the return value to free(). 2676 ** The individual strings within the token list are all a part of 2677 ** the single memory allocation and will all be freed at once. 2678 */ 2679 static char **tokenizeString(const char *z, int *pnToken){ 2680 int nToken = 0; 2681 Token *aToken = sqlite3_malloc( strlen(z) * sizeof(aToken[0]) ); 2682 int n = 1; 2683 int e, i; 2684 int totalSize = 0; 2685 char **azToken; 2686 char *zCopy; 2687 while( n>0 ){ 2688 n = getToken(z, &e); 2689 if( e!=TOKEN_SPACE ){ 2690 aToken[nToken].z = z; 2691 aToken[nToken].n = n; 2692 nToken++; 2693 totalSize += n+1; 2694 } 2695 z += n; 2696 } 2697 azToken = (char**)sqlite3_malloc( nToken*sizeof(char*) + totalSize ); 2698 zCopy = (char*)&azToken[nToken]; 2699 nToken--; 2700 for(i=0; i<nToken; i++){ 2701 azToken[i] = zCopy; 2702 n = aToken[i].n; 2703 memcpy(zCopy, aToken[i].z, n); 2704 zCopy[n] = 0; 2705 zCopy += n+1; 2706 } 2707 azToken[nToken] = 0; 2708 sqlite3_free(aToken); 2709 *pnToken = nToken; 2710 return azToken; 2711 } 2712 2713 /* 2714 ** Convert an SQL-style quoted string into a normal string by removing 2715 ** the quote characters. The conversion is done in-place. If the 2716 ** input does not begin with a quote character, then this routine 2717 ** is a no-op. 2718 ** 2719 ** Examples: 2720 ** 2721 ** "abc" becomes abc 2722 ** 'xyz' becomes xyz 2723 ** [pqr] becomes pqr 2724 ** `mno` becomes mno 2725 */ 2726 static void dequoteString(char *z){ 2727 int quote; 2728 int i, j; 2729 if( z==0 ) return; 2730 quote = z[0]; 2731 switch( quote ){ 2732 case '\'': break; 2733 case '"': break; 2734 case '`': break; /* For MySQL compatibility */ 2735 case '[': quote = ']'; break; /* For MS SqlServer compatibility */ 2736 default: return; 2737 } 2738 for(i=1, j=0; z[i]; i++){ 2739 if( z[i]==quote ){ 2740 if( z[i+1]==quote ){ 2741 z[j++] = quote; 2742 i++; 2743 }else{ 2744 z[j++] = 0; 2745 break; 2746 } 2747 }else{ 2748 z[j++] = z[i]; 2749 } 2750 } 2751 } 2752 2753 /* 2754 ** The input azIn is a NULL-terminated list of tokens. Remove the first 2755 ** token and all punctuation tokens. Remove the quotes from 2756 ** around string literal tokens. 2757 ** 2758 ** Example: 2759 ** 2760 ** input: tokenize chinese ( 'simplifed' , 'mixed' ) 2761 ** output: chinese simplifed mixed 2762 ** 2763 ** Another example: 2764 ** 2765 ** input: delimiters ( '[' , ']' , '...' ) 2766 ** output: [ ] ... 2767 */ 2768 static void tokenListToIdList(char **azIn){ 2769 int i, j; 2770 if( azIn ){ 2771 for(i=0, j=-1; azIn[i]; i++){ 2772 if( safe_isalnum(azIn[i][0]) || azIn[i][1] ){ 2773 dequoteString(azIn[i]); 2774 if( j>=0 ){ 2775 azIn[j] = azIn[i]; 2776 } 2777 j++; 2778 } 2779 } 2780 azIn[j] = 0; 2781 } 2782 } 2783 2784 2785 /* 2786 ** Find the first alphanumeric token in the string zIn. Null-terminate 2787 ** this token. Remove any quotation marks. And return a pointer to 2788 ** the result. 2789 */ 2790 static char *firstToken(char *zIn, char **pzTail){ 2791 int n, ttype; 2792 while(1){ 2793 n = getToken(zIn, &ttype); 2794 if( ttype==TOKEN_SPACE ){ 2795 zIn += n; 2796 }else if( ttype==TOKEN_EOF ){ 2797 *pzTail = zIn; 2798 return 0; 2799 }else{ 2800 zIn[n] = 0; 2801 *pzTail = &zIn[1]; 2802 dequoteString(zIn); 2803 return zIn; 2804 } 2805 } 2806 /*NOTREACHED*/ 2807 } 2808 2809 /* Return true if... 2810 ** 2811 ** * s begins with the string t, ignoring case 2812 ** * s is longer than t 2813 ** * The first character of s beyond t is not a alphanumeric 2814 ** 2815 ** Ignore leading space in *s. 2816 ** 2817 ** To put it another way, return true if the first token of 2818 ** s[] is t[]. 2819 */ 2820 static int startsWith(const char *s, const char *t){ 2821 while( safe_isspace(*s) ){ s++; } 2822 while( *t ){ 2823 if( safe_tolower(*s++)!=safe_tolower(*t++) ) return 0; 2824 } 2825 return *s!='_' && !safe_isalnum(*s); 2826 } 2827 2828 /* 2829 ** An instance of this structure defines the "spec" of a 2830 ** full text index. This structure is populated by parseSpec 2831 ** and use by fulltextConnect and fulltextCreate. 2832 */ 2833 typedef struct TableSpec { 2834 const char *zDb; /* Logical database name */ 2835 const char *zName; /* Name of the full-text index */ 2836 int nColumn; /* Number of columns to be indexed */ 2837 char **azColumn; /* Original names of columns to be indexed */ 2838 char **azContentColumn; /* Column names for %_content */ 2839 char **azTokenizer; /* Name of tokenizer and its arguments */ 2840 } TableSpec; 2841 2842 /* 2843 ** Reclaim all of the memory used by a TableSpec 2844 */ 2845 static void clearTableSpec(TableSpec *p) { 2846 sqlite3_free(p->azColumn); 2847 sqlite3_free(p->azContentColumn); 2848 sqlite3_free(p->azTokenizer); 2849 } 2850 2851 /* Parse a CREATE VIRTUAL TABLE statement, which looks like this: 2852 * 2853 * CREATE VIRTUAL TABLE email 2854 * USING fts2(subject, body, tokenize mytokenizer(myarg)) 2855 * 2856 * We return parsed information in a TableSpec structure. 2857 * 2858 */ 2859 static int parseSpec(TableSpec *pSpec, int argc, const char *const*argv, 2860 char**pzErr){ 2861 int i, n; 2862 char *z, *zDummy; 2863 char **azArg; 2864 const char *zTokenizer = 0; /* argv[] entry describing the tokenizer */ 2865 2866 assert( argc>=3 ); 2867 /* Current interface: 2868 ** argv[0] - module name 2869 ** argv[1] - database name 2870 ** argv[2] - table name 2871 ** argv[3..] - columns, optionally followed by tokenizer specification 2872 ** and snippet delimiters specification. 2873 */ 2874 2875 /* Make a copy of the complete argv[][] array in a single allocation. 2876 ** The argv[][] array is read-only and transient. We can write to the 2877 ** copy in order to modify things and the copy is persistent. 2878 */ 2879 CLEAR(pSpec); 2880 for(i=n=0; i<argc; i++){ 2881 n += strlen(argv[i]) + 1; 2882 } 2883 azArg = sqlite3_malloc( sizeof(char*)*argc + n ); 2884 if( azArg==0 ){ 2885 return SQLITE_NOMEM; 2886 } 2887 z = (char*)&azArg[argc]; 2888 for(i=0; i<argc; i++){ 2889 azArg[i] = z; 2890 strcpy(z, argv[i]); 2891 z += strlen(z)+1; 2892 } 2893 2894 /* Identify the column names and the tokenizer and delimiter arguments 2895 ** in the argv[][] array. 2896 */ 2897 pSpec->zDb = azArg[1]; 2898 pSpec->zName = azArg[2]; 2899 pSpec->nColumn = 0; 2900 pSpec->azColumn = azArg; 2901 zTokenizer = "tokenize simple"; 2902 for(i=3; i<argc; ++i){ 2903 if( startsWith(azArg[i],"tokenize") ){ 2904 zTokenizer = azArg[i]; 2905 }else{ 2906 z = azArg[pSpec->nColumn] = firstToken(azArg[i], &zDummy); 2907 pSpec->nColumn++; 2908 } 2909 } 2910 if( pSpec->nColumn==0 ){ 2911 azArg[0] = "content"; 2912 pSpec->nColumn = 1; 2913 } 2914 2915 /* 2916 ** Construct the list of content column names. 2917 ** 2918 ** Each content column name will be of the form cNNAAAA 2919 ** where NN is the column number and AAAA is the sanitized 2920 ** column name. "sanitized" means that special characters are 2921 ** converted to "_". The cNN prefix guarantees that all column 2922 ** names are unique. 2923 ** 2924 ** The AAAA suffix is not strictly necessary. It is included 2925 ** for the convenience of people who might examine the generated 2926 ** %_content table and wonder what the columns are used for. 2927 */ 2928 pSpec->azContentColumn = sqlite3_malloc( pSpec->nColumn * sizeof(char *) ); 2929 if( pSpec->azContentColumn==0 ){ 2930 clearTableSpec(pSpec); 2931 return SQLITE_NOMEM; 2932 } 2933 for(i=0; i<pSpec->nColumn; i++){ 2934 char *p; 2935 pSpec->azContentColumn[i] = sqlite3_mprintf("c%d%s", i, azArg[i]); 2936 for (p = pSpec->azContentColumn[i]; *p ; ++p) { 2937 if( !safe_isalnum(*p) ) *p = '_'; 2938 } 2939 } 2940 2941 /* 2942 ** Parse the tokenizer specification string. 2943 */ 2944 pSpec->azTokenizer = tokenizeString(zTokenizer, &n); 2945 tokenListToIdList(pSpec->azTokenizer); 2946 2947 return SQLITE_OK; 2948 } 2949 2950 /* 2951 ** Generate a CREATE TABLE statement that describes the schema of 2952 ** the virtual table. Return a pointer to this schema string. 2953 ** 2954 ** Space is obtained from sqlite3_mprintf() and should be freed 2955 ** using sqlite3_free(). 2956 */ 2957 static char *fulltextSchema( 2958 int nColumn, /* Number of columns */ 2959 const char *const* azColumn, /* List of columns */ 2960 const char *zTableName /* Name of the table */ 2961 ){ 2962 int i; 2963 char *zSchema, *zNext; 2964 const char *zSep = "("; 2965 zSchema = sqlite3_mprintf("CREATE TABLE x"); 2966 for(i=0; i<nColumn; i++){ 2967 zNext = sqlite3_mprintf("%s%s%Q", zSchema, zSep, azColumn[i]); 2968 sqlite3_free(zSchema); 2969 zSchema = zNext; 2970 zSep = ","; 2971 } 2972 zNext = sqlite3_mprintf("%s,%Q)", zSchema, zTableName); 2973 sqlite3_free(zSchema); 2974 return zNext; 2975 } 2976 2977 /* 2978 ** Build a new sqlite3_vtab structure that will describe the 2979 ** fulltext index defined by spec. 2980 */ 2981 static int constructVtab( 2982 sqlite3 *db, /* The SQLite database connection */ 2983 fts2Hash *pHash, /* Hash table containing tokenizers */ 2984 TableSpec *spec, /* Parsed spec information from parseSpec() */ 2985 sqlite3_vtab **ppVTab, /* Write the resulting vtab structure here */ 2986 char **pzErr /* Write any error message here */ 2987 ){ 2988 int rc; 2989 int n; 2990 fulltext_vtab *v = 0; 2991 const sqlite3_tokenizer_module *m = NULL; 2992 char *schema; 2993 2994 char const *zTok; /* Name of tokenizer to use for this fts table */ 2995 int nTok; /* Length of zTok, including nul terminator */ 2996 2997 v = (fulltext_vtab *) sqlite3_malloc(sizeof(fulltext_vtab)); 2998 if( v==0 ) return SQLITE_NOMEM; 2999 CLEAR(v); 3000 /* sqlite will initialize v->base */ 3001 v->db = db; 3002 v->zDb = spec->zDb; /* Freed when azColumn is freed */ 3003 v->zName = spec->zName; /* Freed when azColumn is freed */ 3004 v->nColumn = spec->nColumn; 3005 v->azContentColumn = spec->azContentColumn; 3006 spec->azContentColumn = 0; 3007 v->azColumn = spec->azColumn; 3008 spec->azColumn = 0; 3009 3010 if( spec->azTokenizer==0 ){ 3011 return SQLITE_NOMEM; 3012 } 3013 3014 zTok = spec->azTokenizer[0]; 3015 if( !zTok ){ 3016 zTok = "simple"; 3017 } 3018 nTok = strlen(zTok)+1; 3019 3020 m = (sqlite3_tokenizer_module *)sqlite3Fts2HashFind(pHash, zTok, nTok); 3021 if( !m ){ 3022 *pzErr = sqlite3_mprintf("unknown tokenizer: %s", spec->azTokenizer[0]); 3023 rc = SQLITE_ERROR; 3024 goto err; 3025 } 3026 3027 for(n=0; spec->azTokenizer[n]; n++){} 3028 if( n ){ 3029 rc = m->xCreate(n-1, (const char*const*)&spec->azTokenizer[1], 3030 &v->pTokenizer); 3031 }else{ 3032 rc = m->xCreate(0, 0, &v->pTokenizer); 3033 } 3034 if( rc!=SQLITE_OK ) goto err; 3035 v->pTokenizer->pModule = m; 3036 3037 /* TODO: verify the existence of backing tables foo_content, foo_term */ 3038 3039 schema = fulltextSchema(v->nColumn, (const char*const*)v->azColumn, 3040 spec->zName); 3041 rc = sqlite3_declare_vtab(db, schema); 3042 sqlite3_free(schema); 3043 if( rc!=SQLITE_OK ) goto err; 3044 3045 memset(v->pFulltextStatements, 0, sizeof(v->pFulltextStatements)); 3046 3047 /* Indicate that the buffer is not live. */ 3048 v->nPendingData = -1; 3049 3050 *ppVTab = &v->base; 3051 TRACE(("FTS2 Connect %p\n", v)); 3052 3053 return rc; 3054 3055 err: 3056 fulltext_vtab_destroy(v); 3057 return rc; 3058 } 3059 3060 static int fulltextConnect( 3061 sqlite3 *db, 3062 void *pAux, 3063 int argc, const char *const*argv, 3064 sqlite3_vtab **ppVTab, 3065 char **pzErr 3066 ){ 3067 TableSpec spec; 3068 int rc = parseSpec(&spec, argc, argv, pzErr); 3069 if( rc!=SQLITE_OK ) return rc; 3070 3071 rc = constructVtab(db, (fts2Hash *)pAux, &spec, ppVTab, pzErr); 3072 clearTableSpec(&spec); 3073 return rc; 3074 } 3075 3076 /* The %_content table holds the text of each document, with 3077 ** the rowid used as the docid. 3078 */ 3079 /* TODO(shess) This comment needs elaboration to match the updated 3080 ** code. Work it into the top-of-file comment at that time. 3081 */ 3082 static int fulltextCreate(sqlite3 *db, void *pAux, 3083 int argc, const char * const *argv, 3084 sqlite3_vtab **ppVTab, char **pzErr){ 3085 int rc; 3086 TableSpec spec; 3087 StringBuffer schema; 3088 TRACE(("FTS2 Create\n")); 3089 3090 rc = parseSpec(&spec, argc, argv, pzErr); 3091 if( rc!=SQLITE_OK ) return rc; 3092 3093 initStringBuffer(&schema); 3094 append(&schema, "CREATE TABLE %_content("); 3095 appendList(&schema, spec.nColumn, spec.azContentColumn); 3096 append(&schema, ")"); 3097 rc = sql_exec(db, spec.zDb, spec.zName, stringBufferData(&schema)); 3098 stringBufferDestroy(&schema); 3099 if( rc!=SQLITE_OK ) goto out; 3100 3101 rc = sql_exec(db, spec.zDb, spec.zName, 3102 "create table %_segments(block blob);"); 3103 if( rc!=SQLITE_OK ) goto out; 3104 3105 rc = sql_exec(db, spec.zDb, spec.zName, 3106 "create table %_segdir(" 3107 " level integer," 3108 " idx integer," 3109 " start_block integer," 3110 " leaves_end_block integer," 3111 " end_block integer," 3112 " root blob," 3113 " primary key(level, idx)" 3114 ");"); 3115 if( rc!=SQLITE_OK ) goto out; 3116 3117 rc = constructVtab(db, (fts2Hash *)pAux, &spec, ppVTab, pzErr); 3118 3119 out: 3120 clearTableSpec(&spec); 3121 return rc; 3122 } 3123 3124 /* Decide how to handle an SQL query. */ 3125 static int fulltextBestIndex(sqlite3_vtab *pVTab, sqlite3_index_info *pInfo){ 3126 int i; 3127 TRACE(("FTS2 BestIndex\n")); 3128 3129 for(i=0; i<pInfo->nConstraint; ++i){ 3130 const struct sqlite3_index_constraint *pConstraint; 3131 pConstraint = &pInfo->aConstraint[i]; 3132 if( pConstraint->usable ) { 3133 if( pConstraint->iColumn==-1 && 3134 pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ ){ 3135 pInfo->idxNum = QUERY_ROWID; /* lookup by rowid */ 3136 TRACE(("FTS2 QUERY_ROWID\n")); 3137 } else if( pConstraint->iColumn>=0 && 3138 pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH ){ 3139 /* full-text search */ 3140 pInfo->idxNum = QUERY_FULLTEXT + pConstraint->iColumn; 3141 TRACE(("FTS2 QUERY_FULLTEXT %d\n", pConstraint->iColumn)); 3142 } else continue; 3143 3144 pInfo->aConstraintUsage[i].argvIndex = 1; 3145 pInfo->aConstraintUsage[i].omit = 1; 3146 3147 /* An arbitrary value for now. 3148 * TODO: Perhaps rowid matches should be considered cheaper than 3149 * full-text searches. */ 3150 pInfo->estimatedCost = 1.0; 3151 3152 return SQLITE_OK; 3153 } 3154 } 3155 pInfo->idxNum = QUERY_GENERIC; 3156 return SQLITE_OK; 3157 } 3158 3159 static int fulltextDisconnect(sqlite3_vtab *pVTab){ 3160 TRACE(("FTS2 Disconnect %p\n", pVTab)); 3161 fulltext_vtab_destroy((fulltext_vtab *)pVTab); 3162 return SQLITE_OK; 3163 } 3164 3165 static int fulltextDestroy(sqlite3_vtab *pVTab){ 3166 fulltext_vtab *v = (fulltext_vtab *)pVTab; 3167 int rc; 3168 3169 TRACE(("FTS2 Destroy %p\n", pVTab)); 3170 rc = sql_exec(v->db, v->zDb, v->zName, 3171 "drop table if exists %_content;" 3172 "drop table if exists %_segments;" 3173 "drop table if exists %_segdir;" 3174 ); 3175 if( rc!=SQLITE_OK ) return rc; 3176 3177 fulltext_vtab_destroy((fulltext_vtab *)pVTab); 3178 return SQLITE_OK; 3179 } 3180 3181 static int fulltextOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){ 3182 fulltext_cursor *c; 3183 3184 c = (fulltext_cursor *) sqlite3_malloc(sizeof(fulltext_cursor)); 3185 if( c ){ 3186 memset(c, 0, sizeof(fulltext_cursor)); 3187 /* sqlite will initialize c->base */ 3188 *ppCursor = &c->base; 3189 TRACE(("FTS2 Open %p: %p\n", pVTab, c)); 3190 return SQLITE_OK; 3191 }else{ 3192 return SQLITE_NOMEM; 3193 } 3194 } 3195 3196 3197 /* Free all of the dynamically allocated memory held by *q 3198 */ 3199 static void queryClear(Query *q){ 3200 int i; 3201 for(i = 0; i < q->nTerms; ++i){ 3202 sqlite3_free(q->pTerms[i].pTerm); 3203 } 3204 sqlite3_free(q->pTerms); 3205 CLEAR(q); 3206 } 3207 3208 /* Free all of the dynamically allocated memory held by the 3209 ** Snippet 3210 */ 3211 static void snippetClear(Snippet *p){ 3212 sqlite3_free(p->aMatch); 3213 sqlite3_free(p->zOffset); 3214 sqlite3_free(p->zSnippet); 3215 CLEAR(p); 3216 } 3217 /* 3218 ** Append a single entry to the p->aMatch[] log. 3219 */ 3220 static void snippetAppendMatch( 3221 Snippet *p, /* Append the entry to this snippet */ 3222 int iCol, int iTerm, /* The column and query term */ 3223 int iStart, int nByte /* Offset and size of the match */ 3224 ){ 3225 int i; 3226 struct snippetMatch *pMatch; 3227 if( p->nMatch+1>=p->nAlloc ){ 3228 p->nAlloc = p->nAlloc*2 + 10; 3229 p->aMatch = sqlite3_realloc(p->aMatch, p->nAlloc*sizeof(p->aMatch[0]) ); 3230 if( p->aMatch==0 ){ 3231 p->nMatch = 0; 3232 p->nAlloc = 0; 3233 return; 3234 } 3235 } 3236 i = p->nMatch++; 3237 pMatch = &p->aMatch[i]; 3238 pMatch->iCol = iCol; 3239 pMatch->iTerm = iTerm; 3240 pMatch->iStart = iStart; 3241 pMatch->nByte = nByte; 3242 } 3243 3244 /* 3245 ** Sizing information for the circular buffer used in snippetOffsetsOfColumn() 3246 */ 3247 #define FTS2_ROTOR_SZ (32) 3248 #define FTS2_ROTOR_MASK (FTS2_ROTOR_SZ-1) 3249 3250 /* 3251 ** Add entries to pSnippet->aMatch[] for every match that occurs against 3252 ** document zDoc[0..nDoc-1] which is stored in column iColumn. 3253 */ 3254 static void snippetOffsetsOfColumn( 3255 Query *pQuery, 3256 Snippet *pSnippet, 3257 int iColumn, 3258 const char *zDoc, 3259 int nDoc 3260 ){ 3261 const sqlite3_tokenizer_module *pTModule; /* The tokenizer module */ 3262 sqlite3_tokenizer *pTokenizer; /* The specific tokenizer */ 3263 sqlite3_tokenizer_cursor *pTCursor; /* Tokenizer cursor */ 3264 fulltext_vtab *pVtab; /* The full text index */ 3265 int nColumn; /* Number of columns in the index */ 3266 const QueryTerm *aTerm; /* Query string terms */ 3267 int nTerm; /* Number of query string terms */ 3268 int i, j; /* Loop counters */ 3269 int rc; /* Return code */ 3270 unsigned int match, prevMatch; /* Phrase search bitmasks */ 3271 const char *zToken; /* Next token from the tokenizer */ 3272 int nToken; /* Size of zToken */ 3273 int iBegin, iEnd, iPos; /* Offsets of beginning and end */ 3274 3275 /* The following variables keep a circular buffer of the last 3276 ** few tokens */ 3277 unsigned int iRotor = 0; /* Index of current token */ 3278 int iRotorBegin[FTS2_ROTOR_SZ]; /* Beginning offset of token */ 3279 int iRotorLen[FTS2_ROTOR_SZ]; /* Length of token */ 3280 3281 pVtab = pQuery->pFts; 3282 nColumn = pVtab->nColumn; 3283 pTokenizer = pVtab->pTokenizer; 3284 pTModule = pTokenizer->pModule; 3285 rc = pTModule->xOpen(pTokenizer, zDoc, nDoc, &pTCursor); 3286 if( rc ) return; 3287 pTCursor->pTokenizer = pTokenizer; 3288 aTerm = pQuery->pTerms; 3289 nTerm = pQuery->nTerms; 3290 if( nTerm>=FTS2_ROTOR_SZ ){ 3291 nTerm = FTS2_ROTOR_SZ - 1; 3292 } 3293 prevMatch = 0; 3294 while(1){ 3295 rc = pTModule->xNext(pTCursor, &zToken, &nToken, &iBegin, &iEnd, &iPos); 3296 if( rc ) break; 3297 iRotorBegin[iRotor&FTS2_ROTOR_MASK] = iBegin; 3298 iRotorLen[iRotor&FTS2_ROTOR_MASK] = iEnd-iBegin; 3299 match = 0; 3300 for(i=0; i<nTerm; i++){ 3301 int iCol; 3302 iCol = aTerm[i].iColumn; 3303 if( iCol>=0 && iCol<nColumn && iCol!=iColumn ) continue; 3304 if( aTerm[i].nTerm>nToken ) continue; 3305 if( !aTerm[i].isPrefix && aTerm[i].nTerm<nToken ) continue; 3306 assert( aTerm[i].nTerm<=nToken ); 3307 if( memcmp(aTerm[i].pTerm, zToken, aTerm[i].nTerm) ) continue; 3308 if( aTerm[i].iPhrase>1 && (prevMatch & (1<<i))==0 ) continue; 3309 match |= 1<<i; 3310 if( i==nTerm-1 || aTerm[i+1].iPhrase==1 ){ 3311 for(j=aTerm[i].iPhrase-1; j>=0; j--){ 3312 int k = (iRotor-j) & FTS2_ROTOR_MASK; 3313 snippetAppendMatch(pSnippet, iColumn, i-j, 3314 iRotorBegin[k], iRotorLen[k]); 3315 } 3316 } 3317 } 3318 prevMatch = match<<1; 3319 iRotor++; 3320 } 3321 pTModule->xClose(pTCursor); 3322 } 3323 3324 3325 /* 3326 ** Compute all offsets for the current row of the query. 3327 ** If the offsets have already been computed, this routine is a no-op. 3328 */ 3329 static void snippetAllOffsets(fulltext_cursor *p){ 3330 int nColumn; 3331 int iColumn, i; 3332 int iFirst, iLast; 3333 fulltext_vtab *pFts; 3334 3335 if( p->snippet.nMatch ) return; 3336 if( p->q.nTerms==0 ) return; 3337 pFts = p->q.pFts; 3338 nColumn = pFts->nColumn; 3339 iColumn = (p->iCursorType - QUERY_FULLTEXT); 3340 if( iColumn<0 || iColumn>=nColumn ){ 3341 iFirst = 0; 3342 iLast = nColumn-1; 3343 }else{ 3344 iFirst = iColumn; 3345 iLast = iColumn; 3346 } 3347 for(i=iFirst; i<=iLast; i++){ 3348 const char *zDoc; 3349 int nDoc; 3350 zDoc = (const char*)sqlite3_column_text(p->pStmt, i+1); 3351 nDoc = sqlite3_column_bytes(p->pStmt, i+1); 3352 snippetOffsetsOfColumn(&p->q, &p->snippet, i, zDoc, nDoc); 3353 } 3354 } 3355 3356 /* 3357 ** Convert the information in the aMatch[] array of the snippet 3358 ** into the string zOffset[0..nOffset-1]. 3359 */ 3360 static void snippetOffsetText(Snippet *p){ 3361 int i; 3362 int cnt = 0; 3363 StringBuffer sb; 3364 char zBuf[200]; 3365 if( p->zOffset ) return; 3366 initStringBuffer(&sb); 3367 for(i=0; i<p->nMatch; i++){ 3368 struct snippetMatch *pMatch = &p->aMatch[i]; 3369 zBuf[0] = ' '; 3370 sqlite3_snprintf(sizeof(zBuf)-1, &zBuf[cnt>0], "%d %d %d %d", 3371 pMatch->iCol, pMatch->iTerm, pMatch->iStart, pMatch->nByte); 3372 append(&sb, zBuf); 3373 cnt++; 3374 } 3375 p->zOffset = stringBufferData(&sb); 3376 p->nOffset = stringBufferLength(&sb); 3377 } 3378 3379 /* 3380 ** zDoc[0..nDoc-1] is phrase of text. aMatch[0..nMatch-1] are a set 3381 ** of matching words some of which might be in zDoc. zDoc is column 3382 ** number iCol. 3383 ** 3384 ** iBreak is suggested spot in zDoc where we could begin or end an 3385 ** excerpt. Return a value similar to iBreak but possibly adjusted 3386 ** to be a little left or right so that the break point is better. 3387 */ 3388 static int wordBoundary( 3389 int iBreak, /* The suggested break point */ 3390 const char *zDoc, /* Document text */ 3391 int nDoc, /* Number of bytes in zDoc[] */ 3392 struct snippetMatch *aMatch, /* Matching words */ 3393 int nMatch, /* Number of entries in aMatch[] */ 3394 int iCol /* The column number for zDoc[] */ 3395 ){ 3396 int i; 3397 if( iBreak<=10 ){ 3398 return 0; 3399 } 3400 if( iBreak>=nDoc-10 ){ 3401 return nDoc; 3402 } 3403 for(i=0; i<nMatch && aMatch[i].iCol<iCol; i++){} 3404 while( i<nMatch && aMatch[i].iStart+aMatch[i].nByte<iBreak ){ i++; } 3405 if( i<nMatch ){ 3406 if( aMatch[i].iStart<iBreak+10 ){ 3407 return aMatch[i].iStart; 3408 } 3409 if( i>0 && aMatch[i-1].iStart+aMatch[i-1].nByte>=iBreak ){ 3410 return aMatch[i-1].iStart; 3411 } 3412 } 3413 for(i=1; i<=10; i++){ 3414 if( safe_isspace(zDoc[iBreak-i]) ){ 3415 return iBreak - i + 1; 3416 } 3417 if( safe_isspace(zDoc[iBreak+i]) ){ 3418 return iBreak + i + 1; 3419 } 3420 } 3421 return iBreak; 3422 } 3423 3424 3425 3426 /* 3427 ** Allowed values for Snippet.aMatch[].snStatus 3428 */ 3429 #define SNIPPET_IGNORE 0 /* It is ok to omit this match from the snippet */ 3430 #define SNIPPET_DESIRED 1 /* We want to include this match in the snippet */ 3431 3432 /* 3433 ** Generate the text of a snippet. 3434 */ 3435 static void snippetText( 3436 fulltext_cursor *pCursor, /* The cursor we need the snippet for */ 3437 const char *zStartMark, /* Markup to appear before each match */ 3438 const char *zEndMark, /* Markup to appear after each match */ 3439 const char *zEllipsis /* Ellipsis mark */ 3440 ){ 3441 int i, j; 3442 struct snippetMatch *aMatch; 3443 int nMatch; 3444 int nDesired; 3445 StringBuffer sb; 3446 int tailCol; 3447 int tailOffset; 3448 int iCol; 3449 int nDoc; 3450 const char *zDoc; 3451 int iStart, iEnd; 3452 int tailEllipsis = 0; 3453 int iMatch; 3454 3455 3456 sqlite3_free(pCursor->snippet.zSnippet); 3457 pCursor->snippet.zSnippet = 0; 3458 aMatch = pCursor->snippet.aMatch; 3459 nMatch = pCursor->snippet.nMatch; 3460 initStringBuffer(&sb); 3461 3462 for(i=0; i<nMatch; i++){ 3463 aMatch[i].snStatus = SNIPPET_IGNORE; 3464 } 3465 nDesired = 0; 3466 for(i=0; i<pCursor->q.nTerms; i++){ 3467 for(j=0; j<nMatch; j++){ 3468 if( aMatch[j].iTerm==i ){ 3469 aMatch[j].snStatus = SNIPPET_DESIRED; 3470 nDesired++; 3471 break; 3472 } 3473 } 3474 } 3475 3476 iMatch = 0; 3477 tailCol = -1; 3478 tailOffset = 0; 3479 for(i=0; i<nMatch && nDesired>0; i++){ 3480 if( aMatch[i].snStatus!=SNIPPET_DESIRED ) continue; 3481 nDesired--; 3482 iCol = aMatch[i].iCol; 3483 zDoc = (const char*)sqlite3_column_text(pCursor->pStmt, iCol+1); 3484 nDoc = sqlite3_column_bytes(pCursor->pStmt, iCol+1); 3485 iStart = aMatch[i].iStart - 40; 3486 iStart = wordBoundary(iStart, zDoc, nDoc, aMatch, nMatch, iCol); 3487 if( iStart<=10 ){ 3488 iStart = 0; 3489 } 3490 if( iCol==tailCol && iStart<=tailOffset+20 ){ 3491 iStart = tailOffset; 3492 } 3493 if( (iCol!=tailCol && tailCol>=0) || iStart!=tailOffset ){ 3494 trimWhiteSpace(&sb); 3495 appendWhiteSpace(&sb); 3496 append(&sb, zEllipsis); 3497 appendWhiteSpace(&sb); 3498 } 3499 iEnd = aMatch[i].iStart + aMatch[i].nByte + 40; 3500 iEnd = wordBoundary(iEnd, zDoc, nDoc, aMatch, nMatch, iCol); 3501 if( iEnd>=nDoc-10 ){ 3502 iEnd = nDoc; 3503 tailEllipsis = 0; 3504 }else{ 3505 tailEllipsis = 1; 3506 } 3507 while( iMatch<nMatch && aMatch[iMatch].iCol<iCol ){ iMatch++; } 3508 while( iStart<iEnd ){ 3509 while( iMatch<nMatch && aMatch[iMatch].iStart<iStart 3510 && aMatch[iMatch].iCol<=iCol ){ 3511 iMatch++; 3512 } 3513 if( iMatch<nMatch && aMatch[iMatch].iStart<iEnd 3514 && aMatch[iMatch].iCol==iCol ){ 3515 nappend(&sb, &zDoc[iStart], aMatch[iMatch].iStart - iStart); 3516 iStart = aMatch[iMatch].iStart; 3517 append(&sb, zStartMark); 3518 nappend(&sb, &zDoc[iStart], aMatch[iMatch].nByte); 3519 append(&sb, zEndMark); 3520 iStart += aMatch[iMatch].nByte; 3521 for(j=iMatch+1; j<nMatch; j++){ 3522 if( aMatch[j].iTerm==aMatch[iMatch].iTerm 3523 && aMatch[j].snStatus==SNIPPET_DESIRED ){ 3524 nDesired--; 3525 aMatch[j].snStatus = SNIPPET_IGNORE; 3526 } 3527 } 3528 }else{ 3529 nappend(&sb, &zDoc[iStart], iEnd - iStart); 3530 iStart = iEnd; 3531 } 3532 } 3533 tailCol = iCol; 3534 tailOffset = iEnd; 3535 } 3536 trimWhiteSpace(&sb); 3537 if( tailEllipsis ){ 3538 appendWhiteSpace(&sb); 3539 append(&sb, zEllipsis); 3540 } 3541 pCursor->snippet.zSnippet = stringBufferData(&sb); 3542 pCursor->snippet.nSnippet = stringBufferLength(&sb); 3543 } 3544 3545 3546 /* 3547 ** Close the cursor. For additional information see the documentation 3548 ** on the xClose method of the virtual table interface. 3549 */ 3550 static int fulltextClose(sqlite3_vtab_cursor *pCursor){ 3551 fulltext_cursor *c = (fulltext_cursor *) pCursor; 3552 TRACE(("FTS2 Close %p\n", c)); 3553 sqlite3_finalize(c->pStmt); 3554 queryClear(&c->q); 3555 snippetClear(&c->snippet); 3556 if( c->result.nData!=0 ) dlrDestroy(&c->reader); 3557 dataBufferDestroy(&c->result); 3558 sqlite3_free(c); 3559 return SQLITE_OK; 3560 } 3561 3562 static int fulltextNext(sqlite3_vtab_cursor *pCursor){ 3563 fulltext_cursor *c = (fulltext_cursor *) pCursor; 3564 int rc; 3565 3566 TRACE(("FTS2 Next %p\n", pCursor)); 3567 snippetClear(&c->snippet); 3568 if( c->iCursorType < QUERY_FULLTEXT ){ 3569 /* TODO(shess) Handle SQLITE_SCHEMA AND SQLITE_BUSY. */ 3570 rc = sqlite3_step(c->pStmt); 3571 switch( rc ){ 3572 case SQLITE_ROW: 3573 c->eof = 0; 3574 return SQLITE_OK; 3575 case SQLITE_DONE: 3576 c->eof = 1; 3577 return SQLITE_OK; 3578 default: 3579 c->eof = 1; 3580 return rc; 3581 } 3582 } else { /* full-text query */ 3583 rc = sqlite3_reset(c->pStmt); 3584 if( rc!=SQLITE_OK ) return rc; 3585 3586 if( c->result.nData==0 || dlrAtEnd(&c->reader) ){ 3587 c->eof = 1; 3588 return SQLITE_OK; 3589 } 3590 rc = sqlite3_bind_int64(c->pStmt, 1, dlrDocid(&c->reader)); 3591 if( rc!=SQLITE_OK ) return rc; 3592 rc = dlrStep(&c->reader); 3593 if( rc!=SQLITE_OK ) return rc; 3594 /* TODO(shess) Handle SQLITE_SCHEMA AND SQLITE_BUSY. */ 3595 rc = sqlite3_step(c->pStmt); 3596 if( rc==SQLITE_ROW ){ /* the case we expect */ 3597 c->eof = 0; 3598 return SQLITE_OK; 3599 } 3600 3601 /* Corrupt if the index refers to missing document. */ 3602 if( rc==SQLITE_DONE ) return SQLITE_CORRUPT_BKPT; 3603 3604 return rc; 3605 } 3606 } 3607 3608 3609 /* TODO(shess) If we pushed LeafReader to the top of the file, or to 3610 ** another file, term_select() could be pushed above 3611 ** docListOfTerm(). 3612 */ 3613 static int termSelect(fulltext_vtab *v, int iColumn, 3614 const char *pTerm, int nTerm, int isPrefix, 3615 DocListType iType, DataBuffer *out); 3616 3617 /* Return a DocList corresponding to the query term *pTerm. If *pTerm 3618 ** is the first term of a phrase query, go ahead and evaluate the phrase 3619 ** query and return the doclist for the entire phrase query. 3620 ** 3621 ** The resulting DL_DOCIDS doclist is stored in pResult, which is 3622 ** overwritten. 3623 */ 3624 static int docListOfTerm( 3625 fulltext_vtab *v, /* The full text index */ 3626 int iColumn, /* column to restrict to. No restriction if >=nColumn */ 3627 QueryTerm *pQTerm, /* Term we are looking for, or 1st term of a phrase */ 3628 DataBuffer *pResult /* Write the result here */ 3629 ){ 3630 DataBuffer left, right, new; 3631 int i, rc; 3632 3633 /* No phrase search if no position info. */ 3634 assert( pQTerm->nPhrase==0 || DL_DEFAULT!=DL_DOCIDS ); 3635 3636 /* This code should never be called with buffered updates. */ 3637 assert( v->nPendingData<0 ); 3638 3639 dataBufferInit(&left, 0); 3640 rc = termSelect(v, iColumn, pQTerm->pTerm, pQTerm->nTerm, pQTerm->isPrefix, 3641 0<pQTerm->nPhrase ? DL_POSITIONS : DL_DOCIDS, &left); 3642 if( rc ) return rc; 3643 for(i=1; i<=pQTerm->nPhrase && left.nData>0; i++){ 3644 dataBufferInit(&right, 0); 3645 rc = termSelect(v, iColumn, pQTerm[i].pTerm, pQTerm[i].nTerm, 3646 pQTerm[i].isPrefix, DL_POSITIONS, &right); 3647 if( rc ){ 3648 dataBufferDestroy(&left); 3649 return rc; 3650 } 3651 dataBufferInit(&new, 0); 3652 rc = docListPhraseMerge(left.pData, left.nData, right.pData, right.nData, 3653 i<pQTerm->nPhrase ? DL_POSITIONS : DL_DOCIDS, &new); 3654 dataBufferDestroy(&left); 3655 dataBufferDestroy(&right); 3656 if( rc!=SQLITE_OK ){ 3657 dataBufferDestroy(&new); 3658 return rc; 3659 } 3660 left = new; 3661 } 3662 *pResult = left; 3663 return rc; 3664 } 3665 3666 /* Add a new term pTerm[0..nTerm-1] to the query *q. 3667 */ 3668 static void queryAdd(Query *q, const char *pTerm, int nTerm){ 3669 QueryTerm *t; 3670 ++q->nTerms; 3671 q->pTerms = sqlite3_realloc(q->pTerms, q->nTerms * sizeof(q->pTerms[0])); 3672 if( q->pTerms==0 ){ 3673 q->nTerms = 0; 3674 return; 3675 } 3676 t = &q->pTerms[q->nTerms - 1]; 3677 CLEAR(t); 3678 t->pTerm = sqlite3_malloc(nTerm+1); 3679 memcpy(t->pTerm, pTerm, nTerm); 3680 t->pTerm[nTerm] = 0; 3681 t->nTerm = nTerm; 3682 t->isOr = q->nextIsOr; 3683 t->isPrefix = 0; 3684 q->nextIsOr = 0; 3685 t->iColumn = q->nextColumn; 3686 q->nextColumn = q->dfltColumn; 3687 } 3688 3689 /* 3690 ** Check to see if the string zToken[0...nToken-1] matches any 3691 ** column name in the virtual table. If it does, 3692 ** return the zero-indexed column number. If not, return -1. 3693 */ 3694 static int checkColumnSpecifier( 3695 fulltext_vtab *pVtab, /* The virtual table */ 3696 const char *zToken, /* Text of the token */ 3697 int nToken /* Number of characters in the token */ 3698 ){ 3699 int i; 3700 for(i=0; i<pVtab->nColumn; i++){ 3701 if( memcmp(pVtab->azColumn[i], zToken, nToken)==0 3702 && pVtab->azColumn[i][nToken]==0 ){ 3703 return i; 3704 } 3705 } 3706 return -1; 3707 } 3708 3709 /* 3710 ** Parse the text at pSegment[0..nSegment-1]. Add additional terms 3711 ** to the query being assemblied in pQuery. 3712 ** 3713 ** inPhrase is true if pSegment[0..nSegement-1] is contained within 3714 ** double-quotes. If inPhrase is true, then the first term 3715 ** is marked with the number of terms in the phrase less one and 3716 ** OR and "-" syntax is ignored. If inPhrase is false, then every 3717 ** term found is marked with nPhrase=0 and OR and "-" syntax is significant. 3718 */ 3719 static int tokenizeSegment( 3720 sqlite3_tokenizer *pTokenizer, /* The tokenizer to use */ 3721 const char *pSegment, int nSegment, /* Query expression being parsed */ 3722 int inPhrase, /* True if within "..." */ 3723 Query *pQuery /* Append results here */ 3724 ){ 3725 const sqlite3_tokenizer_module *pModule = pTokenizer->pModule; 3726 sqlite3_tokenizer_cursor *pCursor; 3727 int firstIndex = pQuery->nTerms; 3728 int iCol; 3729 int nTerm = 1; 3730 int iEndLast = -1; 3731 3732 int rc = pModule->xOpen(pTokenizer, pSegment, nSegment, &pCursor); 3733 if( rc!=SQLITE_OK ) return rc; 3734 pCursor->pTokenizer = pTokenizer; 3735 3736 while( 1 ){ 3737 const char *pToken; 3738 int nToken, iBegin, iEnd, iPos; 3739 3740 rc = pModule->xNext(pCursor, 3741 &pToken, &nToken, 3742 &iBegin, &iEnd, &iPos); 3743 if( rc!=SQLITE_OK ) break; 3744 if( !inPhrase && 3745 pSegment[iEnd]==':' && 3746 (iCol = checkColumnSpecifier(pQuery->pFts, pToken, nToken))>=0 ){ 3747 pQuery->nextColumn = iCol; 3748 continue; 3749 } 3750 if( !inPhrase && pQuery->nTerms>0 && nToken==2 3751 && pSegment[iBegin]=='O' && pSegment[iBegin+1]=='R' ){ 3752 pQuery->nextIsOr = 1; 3753 continue; 3754 } 3755 3756 /* 3757 * The ICU tokenizer considers '*' a break character, so the code below 3758 * sets isPrefix correctly, but since that code doesn't eat the '*', the 3759 * ICU tokenizer returns it as the next token. So eat it here until a 3760 * better solution presents itself. 3761 */ 3762 if( pQuery->nTerms>0 && nToken==1 && pSegment[iBegin]=='*' && 3763 iEndLast==iBegin){ 3764 pQuery->pTerms[pQuery->nTerms-1].isPrefix = 1; 3765 continue; 3766 } 3767 iEndLast = iEnd; 3768 3769 queryAdd(pQuery, pToken, nToken); 3770 if( !inPhrase && iBegin>0 && pSegment[iBegin-1]=='-' ){ 3771 pQuery->pTerms[pQuery->nTerms-1].isNot = 1; 3772 } 3773 if( iEnd<nSegment && pSegment[iEnd]=='*' ){ 3774 pQuery->pTerms[pQuery->nTerms-1].isPrefix = 1; 3775 } 3776 pQuery->pTerms[pQuery->nTerms-1].iPhrase = nTerm; 3777 if( inPhrase ){ 3778 nTerm++; 3779 } 3780 } 3781 3782 if( inPhrase && pQuery->nTerms>firstIndex ){ 3783 pQuery->pTerms[firstIndex].nPhrase = pQuery->nTerms - firstIndex - 1; 3784 } 3785 3786 return pModule->xClose(pCursor); 3787 } 3788 3789 /* Parse a query string, yielding a Query object pQuery. 3790 ** 3791 ** The calling function will need to queryClear() to clean up 3792 ** the dynamically allocated memory held by pQuery. 3793 */ 3794 static int parseQuery( 3795 fulltext_vtab *v, /* The fulltext index */ 3796 const char *zInput, /* Input text of the query string */ 3797 int nInput, /* Size of the input text */ 3798 int dfltColumn, /* Default column of the index to match against */ 3799 Query *pQuery /* Write the parse results here. */ 3800 ){ 3801 int iInput, inPhrase = 0; 3802 3803 if( zInput==0 ) nInput = 0; 3804 if( nInput<0 ) nInput = strlen(zInput); 3805 pQuery->nTerms = 0; 3806 pQuery->pTerms = NULL; 3807 pQuery->nextIsOr = 0; 3808 pQuery->nextColumn = dfltColumn; 3809 pQuery->dfltColumn = dfltColumn; 3810 pQuery->pFts = v; 3811 3812 for(iInput=0; iInput<nInput; ++iInput){ 3813 int i; 3814 for(i=iInput; i<nInput && zInput[i]!='"'; ++i){} 3815 if( i>iInput ){ 3816 tokenizeSegment(v->pTokenizer, zInput+iInput, i-iInput, inPhrase, 3817 pQuery); 3818 } 3819 iInput = i; 3820 if( i<nInput ){ 3821 assert( zInput[i]=='"' ); 3822 inPhrase = !inPhrase; 3823 } 3824 } 3825 3826 if( inPhrase ){ 3827 /* unmatched quote */ 3828 queryClear(pQuery); 3829 return SQLITE_ERROR; 3830 } 3831 return SQLITE_OK; 3832 } 3833 3834 /* TODO(shess) Refactor the code to remove this forward decl. */ 3835 static int flushPendingTerms(fulltext_vtab *v); 3836 3837 /* Perform a full-text query using the search expression in 3838 ** zInput[0..nInput-1]. Return a list of matching documents 3839 ** in pResult. 3840 ** 3841 ** Queries must match column iColumn. Or if iColumn>=nColumn 3842 ** they are allowed to match against any column. 3843 */ 3844 static int fulltextQuery( 3845 fulltext_vtab *v, /* The full text index */ 3846 int iColumn, /* Match against this column by default */ 3847 const char *zInput, /* The query string */ 3848 int nInput, /* Number of bytes in zInput[] */ 3849 DataBuffer *pResult, /* Write the result doclist here */ 3850 Query *pQuery /* Put parsed query string here */ 3851 ){ 3852 int i, iNext, rc; 3853 DataBuffer left, right, or, new; 3854 int nNot = 0; 3855 QueryTerm *aTerm; 3856 3857 /* TODO(shess) Instead of flushing pendingTerms, we could query for 3858 ** the relevant term and merge the doclist into what we receive from 3859 ** the database. Wait and see if this is a common issue, first. 3860 ** 3861 ** A good reason not to flush is to not generate update-related 3862 ** error codes from here. 3863 */ 3864 3865 /* Flush any buffered updates before executing the query. */ 3866 rc = flushPendingTerms(v); 3867 if( rc!=SQLITE_OK ) return rc; 3868 3869 /* TODO(shess) I think that the queryClear() calls below are not 3870 ** necessary, because fulltextClose() already clears the query. 3871 */ 3872 rc = parseQuery(v, zInput, nInput, iColumn, pQuery); 3873 if( rc!=SQLITE_OK ) return rc; 3874 3875 /* Empty or NULL queries return no results. */ 3876 if( pQuery->nTerms==0 ){ 3877 dataBufferInit(pResult, 0); 3878 return SQLITE_OK; 3879 } 3880 3881 /* Merge AND terms. */ 3882 /* TODO(shess) I think we can early-exit if( i>nNot && left.nData==0 ). */ 3883 aTerm = pQuery->pTerms; 3884 for(i = 0; i<pQuery->nTerms; i=iNext){ 3885 if( aTerm[i].isNot ){ 3886 /* Handle all NOT terms in a separate pass */ 3887 nNot++; 3888 iNext = i + aTerm[i].nPhrase+1; 3889 continue; 3890 } 3891 iNext = i + aTerm[i].nPhrase + 1; 3892 rc = docListOfTerm(v, aTerm[i].iColumn, &aTerm[i], &right); 3893 if( rc ){ 3894 if( i!=nNot ) dataBufferDestroy(&left); 3895 queryClear(pQuery); 3896 return rc; 3897 } 3898 while( iNext<pQuery->nTerms && aTerm[iNext].isOr ){ 3899 rc = docListOfTerm(v, aTerm[iNext].iColumn, &aTerm[iNext], &or); 3900 iNext += aTerm[iNext].nPhrase + 1; 3901 if( rc ){ 3902 if( i!=nNot ) dataBufferDestroy(&left); 3903 dataBufferDestroy(&right); 3904 queryClear(pQuery); 3905 return rc; 3906 } 3907 dataBufferInit(&new, 0); 3908 rc = docListOrMerge(right.pData, right.nData, or.pData, or.nData, &new); 3909 dataBufferDestroy(&right); 3910 dataBufferDestroy(&or); 3911 if( rc!=SQLITE_OK ){ 3912 if( i!=nNot ) dataBufferDestroy(&left); 3913 queryClear(pQuery); 3914 dataBufferDestroy(&new); 3915 return rc; 3916 } 3917 right = new; 3918 } 3919 if( i==nNot ){ /* first term processed. */ 3920 left = right; 3921 }else{ 3922 dataBufferInit(&new, 0); 3923 rc = docListAndMerge(left.pData, left.nData, 3924 right.pData, right.nData, &new); 3925 dataBufferDestroy(&right); 3926 dataBufferDestroy(&left); 3927 if( rc!=SQLITE_OK ){ 3928 queryClear(pQuery); 3929 dataBufferDestroy(&new); 3930 return rc; 3931 } 3932 left = new; 3933 } 3934 } 3935 3936 if( nNot==pQuery->nTerms ){ 3937 /* We do not yet know how to handle a query of only NOT terms */ 3938 return SQLITE_ERROR; 3939 } 3940 3941 /* Do the EXCEPT terms */ 3942 for(i=0; i<pQuery->nTerms; i += aTerm[i].nPhrase + 1){ 3943 if( !aTerm[i].isNot ) continue; 3944 rc = docListOfTerm(v, aTerm[i].iColumn, &aTerm[i], &right); 3945 if( rc ){ 3946 queryClear(pQuery); 3947 dataBufferDestroy(&left); 3948 return rc; 3949 } 3950 dataBufferInit(&new, 0); 3951 rc = docListExceptMerge(left.pData, left.nData, 3952 right.pData, right.nData, &new); 3953 dataBufferDestroy(&right); 3954 dataBufferDestroy(&left); 3955 if( rc!=SQLITE_OK ){ 3956 <