third_party/sqlite/ext/fts2/fts2.c - Issue 3108030: Move bundled copy of sqlite one level deeper to better separate it...

Side by Side Diff: third_party/sqlite/ext/fts2/fts2.c

Issue 3108030: Move bundled copy of sqlite one level deeper to better separate it... (Closed) Base URL: svn://svn.chromium.org/chrome/trunk/src/

Patch Set: Created 10 years, 4 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

View unified diff | Download patch | Annotate | Revision Log

OLD	NEW
	(Empty)
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 <ctype.h>

324

325 #include "fts2.h"

326 #include "fts2_hash.h"

327 #include "fts2_tokenizer.h"

328 #include "sqlite3.h"

329 #include "sqlite3ext.h"

330 SQLITE_EXTENSION_INIT1

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&0x80)==0 ? isspace(c) : 0;

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&0x80)==0 ? isalnum(c) : 0;

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 (110241024)

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( nTokensizeof(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 charconst)&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 charconst)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 constargv,

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 queryClear(pQuery);

3957 dataBufferDestroy(&new);

3958 return rc;

3959 }

3960 left = new;

3961 }

3962

3963 *pResult = left;

3964 return rc;

3965 }

3966

3967 /*

3968 ** This is the xFilter interface for the virtual table. See

3969 ** the virtual table xFilter method documentation for additional

3970 ** information.

3971 **

3972 ** If idxNum==QUERY_GENERIC then do a full table scan against

3973 ** the %_content table.

3974 **

3975 ** If idxNum==QUERY_ROWID then do a rowid lookup for a single entry

3976 ** in the %_content table.

3977 **

3978 ** If idxNum>=QUERY_FULLTEXT then use the full text index. The

3979 ** column on the left-hand side of the MATCH operator is column

3980 ** number idxNum-QUERY_FULLTEXT, 0 indexed. argv[0] is the right-hand

3981 ** side of the MATCH operator.

3982 */

3983 /* TODO(shess) Upgrade the cursor initialization and destruction to

3984 ** account for fulltextFilter() being called multiple times on the

3985 ** same cursor. The current solution is very fragile. Apply fix to

3986 ** fts2 as appropriate.

3987 */

3988 static int fulltextFilter(

3989 sqlite3_vtab_cursor pCursor, / The cursor used for this query */

3990 int idxNum, const char idxStr, / Which indexing scheme to use */

3991 int argc, sqlite3_value *argv / Arguments for the indexing scheme */

3992 ){

3993 fulltext_cursor c = (fulltext_cursor ) pCursor;

3994 fulltext_vtab *v = cursor_vtab(c);

3995 int rc;

3996

3997 TRACE(("FTS2 Filter %p\n",pCursor));

3998

3999 /* If the cursor has a statement that was not prepared according to

4000 ** idxNum, clear it. I believe all calls to fulltextFilter with a

4001 ** given cursor will have the same idxNum , but in this case it's

4002 ** easy to be safe.

4003 */

4004 if( c->pStmt && c->iCursorType!=idxNum ){

4005 sqlite3_finalize(c->pStmt);

4006 c->pStmt = NULL;

4007 }

4008

4009 /* Get a fresh statement appropriate to idxNum. */

4010 /* TODO(shess): Add a prepared-statement cache in the vt structure.

4011 ** The cache must handle multiple open cursors. Easier to cache the

4012 ** statement variants at the vt to reduce malloc/realloc/free here.

4013 ** Or we could have a StringBuffer variant which allowed stack

4014 ** construction for small values.

4015 */

4016 if( !c->pStmt ){

4017 char zSql = sqlite3_mprintf("select rowid, from %%_content %s",

4018 idxNum==QUERY_GENERIC ? "" : "where rowid=?");

4019 rc = sql_prepare(v->db, v->zDb, v->zName, &c->pStmt, zSql);

4020 sqlite3_free(zSql);

4021 if( rc!=SQLITE_OK ) return rc;

4022 c->iCursorType = idxNum;

4023 }else{

4024 sqlite3_reset(c->pStmt);

4025 assert( c->iCursorType==idxNum );

4026 }

4027

4028 switch( idxNum ){

4029 case QUERY_GENERIC:

4030 break;

4031

4032 case QUERY_ROWID:

4033 rc = sqlite3_bind_int64(c->pStmt, 1, sqlite3_value_int64(argv[0]));

4034 if( rc!=SQLITE_OK ) return rc;

4035 break;

4036

4037 default: /* full-text search */

4038 {

4039 const char zQuery = (const char )sqlite3_value_text(argv[0]);

4040 assert( idxNum<=QUERY_FULLTEXT+v->nColumn);

4041 assert( argc==1 );

4042 queryClear(&c->q);

4043 if( c->result.nData!=0 ){

4044 /* This case happens if the same cursor is used repeatedly. */

4045 dlrDestroy(&c->reader);

4046 dataBufferReset(&c->result);

4047 }else{

4048 dataBufferInit(&c->result, 0);

4049 }

4050 rc = fulltextQuery(v, idxNum-QUERY_FULLTEXT, zQuery, -1, &c->result, &c->q );

4051 if( rc!=SQLITE_OK ) return rc;

4052 if( c->result.nData!=0 ){

4053 rc = dlrInit(&c->reader, DL_DOCIDS, c->result.pData, c->result.nData);

4054 if( rc!=SQLITE_OK ) return rc;

4055 }

4056 break;

4057 }

4058 }

4059

4060 return fulltextNext(pCursor);

4061 }

4062

4063 /* This is the xEof method of the virtual table. The SQLite core

4064 ** calls this routine to find out if it has reached the end of

4065 ** a query's results set.

4066 */

4067 static int fulltextEof(sqlite3_vtab_cursor *pCursor){

4068 fulltext_cursor c = (fulltext_cursor ) pCursor;

4069 return c->eof;

4070 }

4071

4072 /* This is the xColumn method of the virtual table. The SQLite

4073 ** core calls this method during a query when it needs the value

4074 ** of a column from the virtual table. This method needs to use

4075 ** one of the sqlite3_result_*() routines to store the requested

4076 ** value back in the pContext.

4077 */

4078 static int fulltextColumn(sqlite3_vtab_cursor *pCursor,

4079 sqlite3_context *pContext, int idxCol){

4080 fulltext_cursor c = (fulltext_cursor ) pCursor;

4081 fulltext_vtab *v = cursor_vtab(c);

4082

4083 if( idxCol<v->nColumn ){

4084 sqlite3_value *pVal = sqlite3_column_value(c->pStmt, idxCol+1);

4085 sqlite3_result_value(pContext, pVal);

4086 }else if( idxCol==v->nColumn ){

4087 /* The extra column whose name is the same as the table.

4088 ** Return a blob which is a pointer to the cursor

4089 */

4090 sqlite3_result_blob(pContext, &c, sizeof(c), SQLITE_TRANSIENT);

4091 }

4092 return SQLITE_OK;

4093 }

4094

4095 /* This is the xRowid method. The SQLite core calls this routine to

4096 ** retrive the rowid for the current row of the result set. The

4097 ** rowid should be written to *pRowid.

4098 */

4099 static int fulltextRowid(sqlite3_vtab_cursor pCursor, sqlite_int64 pRowid){

4100 fulltext_cursor c = (fulltext_cursor ) pCursor;

4101

4102 *pRowid = sqlite3_column_int64(c->pStmt, 0);

4103 return SQLITE_OK;

4104 }

4105

4106 /* Add all terms in [zText] to pendingTerms table. If [iColumn] > 0,

4107 ** we also store positions and offsets in the hash table using that

4108 ** column number.

4109 */

4110 static int buildTerms(fulltext_vtab *v, sqlite_int64 iDocid,

4111 const char *zText, int iColumn){

4112 sqlite3_tokenizer *pTokenizer = v->pTokenizer;

4113 sqlite3_tokenizer_cursor *pCursor;

4114 const char *pToken;

4115 int nTokenBytes;

4116 int iStartOffset, iEndOffset, iPosition;

4117 int rc;

4118

4119 rc = pTokenizer->pModule->xOpen(pTokenizer, zText, -1, &pCursor);

4120 if( rc!=SQLITE_OK ) return rc;

4121

4122 pCursor->pTokenizer = pTokenizer;

4123 while( SQLITE_OK==(rc=pTokenizer->pModule->xNext(pCursor,

4124 &pToken, &nTokenBytes,

4125 &iStartOffset, &iEndOffset,

4126 &iPosition)) ){

4127 DLCollector *p;

4128 int nData; /* Size of doclist before our update. */

4129

4130 /* Positions can't be negative; we use -1 as a terminator

4131 * internally. Token can't be NULL or empty. */

4132 if( iPosition<0 \|\| pToken == NULL \|\| nTokenBytes == 0 ){

4133 rc = SQLITE_ERROR;

4134 break;

4135 }

4136

4137 p = fts2HashFind(&v->pendingTerms, pToken, nTokenBytes);

4138 if( p==NULL ){

4139 nData = 0;

4140 p = dlcNew(iDocid, DL_DEFAULT);

4141 fts2HashInsert(&v->pendingTerms, pToken, nTokenBytes, p);

4142

4143 /* Overhead for our hash table entry, the key, and the value. */

4144 v->nPendingData += sizeof(struct fts2HashElem)+sizeof(*p)+nTokenBytes;

4145 }else{

4146 nData = p->b.nData;

4147 if( p->dlw.iPrevDocid!=iDocid ) dlcNext(p, iDocid);

4148 }

4149 if( iColumn>=0 ){

4150 dlcAddPos(p, iColumn, iPosition, iStartOffset, iEndOffset);

4151 }

4152

4153 /* Accumulate data added by dlcNew or dlcNext, and dlcAddPos. */

4154 v->nPendingData += p->b.nData-nData;

4155 }

4156

4157 /* TODO(shess) Check return? Should this be able to cause errors at

4158 ** this point? Actually, same question about sqlite3_finalize(),

4159 ** though one could argue that failure there means that the data is

4160 ** not durable. ponder

4161 */

4162 pTokenizer->pModule->xClose(pCursor);

4163 if( SQLITE_DONE == rc ) return SQLITE_OK;

4164 return rc;

4165 }

4166

4167 /* Add doclists for all terms in [pValues] to pendingTerms table. */

4168 static int insertTerms(fulltext_vtab *v, sqlite_int64 iRowid,

4169 sqlite3_value **pValues){

4170 int i;

4171 for(i = 0; i < v->nColumn ; ++i){

4172 char zText = (char)sqlite3_value_text(pValues[i]);

4173 int rc = buildTerms(v, iRowid, zText, i);

4174 if( rc!=SQLITE_OK ) return rc;

4175 }

4176 return SQLITE_OK;

4177 }

4178

4179 /* Add empty doclists for all terms in the given row's content to

4180 ** pendingTerms.

4181 */

4182 static int deleteTerms(fulltext_vtab *v, sqlite_int64 iRowid){

4183 const char **pValues;

4184 int i, rc;

4185

4186 /* TODO(shess) Should we allow such tables at all? */

4187 if( DL_DEFAULT==DL_DOCIDS ) return SQLITE_ERROR;

4188

4189 rc = content_select(v, iRowid, &pValues);

4190 if( rc!=SQLITE_OK ) return rc;

4191

4192 for(i = 0 ; i < v->nColumn; ++i) {

4193 rc = buildTerms(v, iRowid, pValues[i], -1);

4194 if( rc!=SQLITE_OK ) break;

4195 }

4196

4197 freeStringArray(v->nColumn, pValues);

4198 return SQLITE_OK;

4199 }

4200

4201 /* TODO(shess) Refactor the code to remove this forward decl. */

4202 static int initPendingTerms(fulltext_vtab *v, sqlite_int64 iDocid);

4203

4204 /* Insert a row into the %_content table; set *piRowid to be the ID of the

4205 ** new row. Add doclists for terms to pendingTerms.

4206 */

4207 static int index_insert(fulltext_vtab v, sqlite3_value pRequestRowid,

4208 sqlite3_value *pValues, sqlite_int64 piRowid){

4209 int rc;

4210

4211 rc = content_insert(v, pRequestRowid, pValues); /* execute an SQL INSERT */

4212 if( rc!=SQLITE_OK ) return rc;

4213

4214 *piRowid = sqlite3_last_insert_rowid(v->db);

4215 rc = initPendingTerms(v, *piRowid);

4216 if( rc!=SQLITE_OK ) return rc;

4217

4218 return insertTerms(v, *piRowid, pValues);

4219 }

4220

4221 /* Delete a row from the %_content table; add empty doclists for terms

4222 ** to pendingTerms.

4223 */

4224 static int index_delete(fulltext_vtab *v, sqlite_int64 iRow){

4225 int rc = initPendingTerms(v, iRow);

4226 if( rc!=SQLITE_OK ) return rc;

4227

4228 rc = deleteTerms(v, iRow);

4229 if( rc!=SQLITE_OK ) return rc;

4230

4231 return content_delete(v, iRow); /* execute an SQL DELETE */

4232 }

4233

4234 /* Update a row in the %_content table; add delete doclists to

4235 ** pendingTerms for old terms not in the new data, add insert doclists

4236 ** to pendingTerms for terms in the new data.

4237 */

4238 static int index_update(fulltext_vtab *v, sqlite_int64 iRow,

4239 sqlite3_value **pValues){

4240 int rc = initPendingTerms(v, iRow);

4241 if( rc!=SQLITE_OK ) return rc;

4242

4243 /* Generate an empty doclist for each term that previously appeared in this

4244 * row. */

4245 rc = deleteTerms(v, iRow);

4246 if( rc!=SQLITE_OK ) return rc;

4247

4248 rc = content_update(v, pValues, iRow); /* execute an SQL UPDATE */

4249 if( rc!=SQLITE_OK ) return rc;

4250

4251 /* Now add positions for terms which appear in the updated row. */

4252 return insertTerms(v, iRow, pValues);

4253 }

4254

4255 /*******************************************************************/

4256 /* InteriorWriter is used to collect terms and block references into

4257 ** interior nodes in %_segments. See commentary at top of file for

4258 ** format.

4259 */

4260

4261 /* How large interior nodes can grow. */

4262 #define INTERIOR_MAX 2048

4263

4264 /* Minimum number of terms per interior node (except the root). This

4265 ** prevents large terms from making the tree too skinny - must be >0

4266 ** so that the tree always makes progress. Note that the min tree

4267 ** fanout will be INTERIOR_MIN_TERMS+1.

4268 */

4269 #define INTERIOR_MIN_TERMS 7

4270 #if INTERIOR_MIN_TERMS<1

4271 # error INTERIOR_MIN_TERMS must be greater than 0.

4272 #endif

4273

4274 /* ROOT_MAX controls how much data is stored inline in the segment

4275 ** directory.

4276 */

4277 /* TODO(shess) Push ROOT_MAX down to whoever is writing things. It's

4278 ** only here so that interiorWriterRootInfo() and leafWriterRootInfo()

4279 ** can both see it, but if the caller passed it in, we wouldn't even

4280 ** need a define.

4281 */

4282 #define ROOT_MAX 1024

4283 #if ROOT_MAX<VARINT_MAX*2

4284 # error ROOT_MAX must have enough space for a header.

4285 #endif

4286

4287 /* InteriorBlock stores a linked-list of interior blocks while a lower

4288 ** layer is being constructed.

4289 */

4290 typedef struct InteriorBlock {

4291 DataBuffer term; /* Leftmost term in block's subtree. */

4292 DataBuffer data; /* Accumulated data for the block. */

4293 struct InteriorBlock *next;

4294 } InteriorBlock;

4295

4296 static InteriorBlock *interiorBlockNew(int iHeight, sqlite_int64 iChildBlock,

4297 const char *pTerm, int nTerm){

4298 InteriorBlock *block = sqlite3_malloc(sizeof(InteriorBlock));

4299 char c[VARINT_MAX+VARINT_MAX];

4300 int n;

4301

4302 if( block ){

4303 memset(block, 0, sizeof(*block));

4304 dataBufferInit(&block->term, 0);

4305 dataBufferReplace(&block->term, pTerm, nTerm);

4306

4307 n = putVarint(c, iHeight);

4308 n += putVarint(c+n, iChildBlock);

4309 dataBufferInit(&block->data, INTERIOR_MAX);

4310 dataBufferReplace(&block->data, c, n);

4311 }

4312 return block;

4313 }

4314

4315 #ifndef NDEBUG

4316 /* Verify that the data is readable as an interior node. */

4317 static void interiorBlockValidate(InteriorBlock *pBlock){

4318 const char *pData = pBlock->data.pData;

4319 int nData = pBlock->data.nData;

4320 int n, iDummy;

4321 sqlite_int64 iBlockid;

4322

4323 assert( nData>0 );

4324 assert( pData!=0 );

4325 assert( pData+nData>pData );

4326

4327 /* Must lead with height of node as a varint(n), n>0 */

4328 n = getVarint32(pData, &iDummy);

4329 assert( n>0 );

4330 assert( iDummy>0 );

4331 assert( n<nData );

4332 pData += n;

4333 nData -= n;

4334

4335 /* Must contain iBlockid. */

4336 n = getVarint(pData, &iBlockid);

4337 assert( n>0 );

4338 assert( n<=nData );

4339 pData += n;

4340 nData -= n;

4341

4342 /* Zero or more terms of positive length */

4343 if( nData!=0 ){

4344 /* First term is not delta-encoded. */

4345 n = getVarint32(pData, &iDummy);

4346 assert( n>0 );

4347 assert( iDummy>0 );

4348 assert( n+iDummy>0);

4349 assert( n+iDummy<=nData );

4350 pData += n+iDummy;

4351 nData -= n+iDummy;

4352

4353 /* Following terms delta-encoded. */

4354 while( nData!=0 ){

4355 /* Length of shared prefix. */

4356 n = getVarint32(pData, &iDummy);

4357 assert( n>0 );

4358 assert( iDummy>=0 );

4359 assert( n<nData );

4360 pData += n;

4361 nData -= n;

4362

4363 /* Length and data of distinct suffix. */

4364 n = getVarint32(pData, &iDummy);

4365 assert( n>0 );

4366 assert( iDummy>0 );

4367 assert( n+iDummy>0);

4368 assert( n+iDummy<=nData );

4369 pData += n+iDummy;

4370 nData -= n+iDummy;

4371 }

4372 }

4373 }

4374 #define ASSERT_VALID_INTERIOR_BLOCK(x) interiorBlockValidate(x)

4375 #else

4376 #define ASSERT_VALID_INTERIOR_BLOCK(x) assert( 1 )

4377 #endif

4378

4379 typedef struct InteriorWriter {

4380 int iHeight; /* from 0 at leaves. */

4381 InteriorBlock first, last;

4382 struct InteriorWriter *parentWriter;

4383

4384 DataBuffer term; /* Last term written to block "last". */

4385 sqlite_int64 iOpeningChildBlock; /* First child block in block "last". */

4386 #ifndef NDEBUG

4387 sqlite_int64 iLastChildBlock; /* for consistency checks. */

4388 #endif

4389 } InteriorWriter;

4390

4391 /* Initialize an interior node where pTerm[nTerm] marks the leftmost

4392 ** term in the tree. iChildBlock is the leftmost child block at the

4393 ** next level down the tree.

4394 */

4395 static void interiorWriterInit(int iHeight, const char *pTerm, int nTerm,

4396 sqlite_int64 iChildBlock,

4397 InteriorWriter *pWriter){

4398 InteriorBlock *block;

4399 assert( iHeight>0 );

4400 CLEAR(pWriter);

4401

4402 pWriter->iHeight = iHeight;

4403 pWriter->iOpeningChildBlock = iChildBlock;

4404 #ifndef NDEBUG

4405 pWriter->iLastChildBlock = iChildBlock;

4406 #endif

4407 block = interiorBlockNew(iHeight, iChildBlock, pTerm, nTerm);

4408 pWriter->last = pWriter->first = block;

4409 ASSERT_VALID_INTERIOR_BLOCK(pWriter->last);

4410 dataBufferInit(&pWriter->term, 0);

4411 }

4412

4413 /* Append the child node rooted at iChildBlock to the interior node,

4414 ** with pTerm[nTerm] as the leftmost term in iChildBlock's subtree.

4415 */

4416 static void interiorWriterAppend(InteriorWriter *pWriter,

4417 const char *pTerm, int nTerm,

4418 sqlite_int64 iChildBlock){

4419 char c[VARINT_MAX+VARINT_MAX];

4420 int n, nPrefix = 0;

4421

4422 ASSERT_VALID_INTERIOR_BLOCK(pWriter->last);

4423

4424 /* The first term written into an interior node is actually

4425 ** associated with the second child added (the first child was added

4426 ** in interiorWriterInit, or in the if clause at the bottom of this

4427 ** function). That term gets encoded straight up, with nPrefix left

4428 ** at 0.

4429 */

4430 if( pWriter->term.nData==0 ){

4431 n = putVarint(c, nTerm);

4432 }else{

4433 while( nPrefix<pWriter->term.nData &&

4434 pTerm[nPrefix]==pWriter->term.pData[nPrefix] ){

4435 nPrefix++;

4436 }

4437

4438 n = putVarint(c, nPrefix);

4439 n += putVarint(c+n, nTerm-nPrefix);

4440 }

4441

4442 #ifndef NDEBUG

4443 pWriter->iLastChildBlock++;

4444 #endif

4445 assert( pWriter->iLastChildBlock==iChildBlock );

4446

4447 /* Overflow to a new block if the new term makes the current block

4448 ** too big, and the current block already has enough terms.

4449 */

4450 if( pWriter->last->data.nData+n+nTerm-nPrefix>INTERIOR_MAX &&

4451 iChildBlock-pWriter->iOpeningChildBlock>INTERIOR_MIN_TERMS ){

4452 pWriter->last->next = interiorBlockNew(pWriter->iHeight, iChildBlock,

4453 pTerm, nTerm);

4454 pWriter->last = pWriter->last->next;

4455 pWriter->iOpeningChildBlock = iChildBlock;

4456 dataBufferReset(&pWriter->term);

4457 }else{

4458 dataBufferAppend2(&pWriter->last->data, c, n,

4459 pTerm+nPrefix, nTerm-nPrefix);

4460 dataBufferReplace(&pWriter->term, pTerm, nTerm);

4461 }

4462 ASSERT_VALID_INTERIOR_BLOCK(pWriter->last);

4463 }

4464

4465 /* Free the space used by pWriter, including the linked-list of

4466 ** InteriorBlocks, and parentWriter, if present.

4467 */

4468 static int interiorWriterDestroy(InteriorWriter *pWriter){

4469 InteriorBlock *block = pWriter->first;

4470

4471 while( block!=NULL ){

4472 InteriorBlock *b = block;

4473 block = block->next;

4474 dataBufferDestroy(&b->term);

4475 dataBufferDestroy(&b->data);

4476 sqlite3_free(b);

4477 }

4478 if( pWriter->parentWriter!=NULL ){

4479 interiorWriterDestroy(pWriter->parentWriter);

4480 sqlite3_free(pWriter->parentWriter);

4481 }

4482 dataBufferDestroy(&pWriter->term);

4483 SCRAMBLE(pWriter);

4484 return SQLITE_OK;

4485 }

4486

4487 /* If pWriter can fit entirely in ROOT_MAX, return it as the root info

4488 ** directly, leaving *piEndBlockid unchanged. Otherwise, flush

4489 ** pWriter to %_segments, building a new layer of interior nodes, and

4490 ** recursively ask for their root into.

4491 */

4492 static int interiorWriterRootInfo(fulltext_vtab v, InteriorWriter pWriter,

4493 char *ppRootInfo, int pnRootInfo,

4494 sqlite_int64 *piEndBlockid){

4495 InteriorBlock *block = pWriter->first;

4496 sqlite_int64 iBlockid = 0;

4497 int rc;

4498

4499 /* If we can fit the segment inline */

4500 if( block==pWriter->last && block->data.nData<ROOT_MAX ){

4501 *ppRootInfo = block->data.pData;

4502 *pnRootInfo = block->data.nData;

4503 return SQLITE_OK;

4504 }

4505

4506 /* Flush the first block to %_segments, and create a new level of

4507 ** interior node.

4508 */

4509 ASSERT_VALID_INTERIOR_BLOCK(block);

4510 rc = block_insert(v, block->data.pData, block->data.nData, &iBlockid);

4511 if( rc!=SQLITE_OK ) return rc;

4512 *piEndBlockid = iBlockid;

4513

4514 pWriter->parentWriter = sqlite3_malloc(sizeof(*pWriter->parentWriter));

4515 interiorWriterInit(pWriter->iHeight+1,

4516 block->term.pData, block->term.nData,

4517 iBlockid, pWriter->parentWriter);

4518

4519 /* Flush additional blocks and append to the higher interior

4520 ** node.

4521 */

4522 for(block=block->next; block!=NULL; block=block->next){

4523 ASSERT_VALID_INTERIOR_BLOCK(block);

4524 rc = block_insert(v, block->data.pData, block->data.nData, &iBlockid);

4525 if( rc!=SQLITE_OK ) return rc;

4526 *piEndBlockid = iBlockid;

4527

4528 interiorWriterAppend(pWriter->parentWriter,

4529 block->term.pData, block->term.nData, iBlockid);

4530 }

4531

4532 /* Parent node gets the chance to be the root. */

4533 return interiorWriterRootInfo(v, pWriter->parentWriter,

4534 ppRootInfo, pnRootInfo, piEndBlockid);

4535 }

4536

4537 /****************************************************************/

4538 /* InteriorReader is used to read off the data from an interior node

4539 ** (see comment at top of file for the format).

4540 */

4541 typedef struct InteriorReader {

4542 const char *pData;

4543 int nData;

4544

4545 DataBuffer term; /* previous term, for decoding term delta. */

4546

4547 sqlite_int64 iBlockid;

4548 } InteriorReader;

4549

4550 static void interiorReaderDestroy(InteriorReader *pReader){

4551 dataBufferDestroy(&pReader->term);

4552 SCRAMBLE(pReader);

4553 }

4554

4555 static int interiorReaderInit(const char *pData, int nData,

4556 InteriorReader *pReader){

4557 int n, nTerm;

4558

4559 /* These conditions are checked and met by the callers. */

4560 assert( nData>0 );

4561 assert( pData[0]!='\0' );

4562

4563 CLEAR(pReader);

4564

4565 /* Decode the base blockid, and set the cursor to the first term. */

4566 n = getVarintSafe(pData+1, &pReader->iBlockid, nData-1);

4567 if( !n ) return SQLITE_CORRUPT_BKPT;

4568 pReader->pData = pData+1+n;

4569 pReader->nData = nData-(1+n);

4570

4571 /* A single-child interior node (such as when a leaf node was too

4572 ** large for the segment directory) won't have any terms.

4573 ** Otherwise, decode the first term.

4574 */

4575 if( pReader->nData==0 ){

4576 dataBufferInit(&pReader->term, 0);

4577 }else{

4578 n = getVarint32Safe(pReader->pData, &nTerm, pReader->nData);

4579 if( !n \|\| nTerm<0 \|\| nTerm>pReader->nData-n) return SQLITE_CORRUPT_BKPT;

4580 dataBufferInit(&pReader->term, nTerm);

4581 dataBufferReplace(&pReader->term, pReader->pData+n, nTerm);

4582 pReader->pData += n+nTerm;

4583 pReader->nData -= n+nTerm;

4584 }

4585 return SQLITE_OK;

4586 }

4587

4588 static int interiorReaderAtEnd(InteriorReader *pReader){

4589 return pReader->term.nData<=0;

4590 }

4591

4592 static sqlite_int64 interiorReaderCurrentBlockid(InteriorReader *pReader){

4593 return pReader->iBlockid;

4594 }

4595

4596 static int interiorReaderTermBytes(InteriorReader *pReader){

4597 assert( !interiorReaderAtEnd(pReader) );

4598 return pReader->term.nData;

4599 }

4600 static const char interiorReaderTerm(InteriorReader pReader){

4601 assert( !interiorReaderAtEnd(pReader) );

4602 return pReader->term.pData;

4603 }

4604

4605 /* Step forward to the next term in the node. */

4606 static int interiorReaderStep(InteriorReader *pReader){

4607 assert( !interiorReaderAtEnd(pReader) );

4608

4609 /* If the last term has been read, signal eof, else construct the

4610 ** next term.

4611 */

4612 if( pReader->nData==0 ){

4613 dataBufferReset(&pReader->term);

4614 }else{

4615 int n, nPrefix, nSuffix;

4616

4617 n = getVarint32Safe(pReader->pData, &nPrefix, pReader->nData);

4618 if( !n ) return SQLITE_CORRUPT_BKPT;

4619 pReader->nData -= n;

4620 pReader->pData += n;

4621 n = getVarint32Safe(pReader->pData, &nSuffix, pReader->nData);

4622 if( !n ) return SQLITE_CORRUPT_BKPT;

4623 pReader->nData -= n;

4624 pReader->pData += n;

4625 if( nSuffix<0 \|\| nSuffix>pReader->nData ) return SQLITE_CORRUPT_BKPT;

4626 if( nPrefix<0 \|\| nPrefix>pReader->term.nData ) return SQLITE_CORRUPT_BKPT;

4627

4628 /* Truncate the current term and append suffix data. */

4629 pReader->term.nData = nPrefix;

4630 dataBufferAppend(&pReader->term, pReader->pData, nSuffix);

4631

4632 pReader->pData += nSuffix;

4633 pReader->nData -= nSuffix;

4634 }

4635 pReader->iBlockid++;

4636 return SQLITE_OK;

4637 }

4638

4639 /* Compare the current term to pTerm[nTerm], returning strcmp-style

4640 ** results. If isPrefix, equality means equal through nTerm bytes.

4641 */

4642 static int interiorReaderTermCmp(InteriorReader *pReader,

4643 const char *pTerm, int nTerm, int isPrefix){

4644 const char *pReaderTerm = interiorReaderTerm(pReader);

4645 int nReaderTerm = interiorReaderTermBytes(pReader);

4646 int c, n = nReaderTerm<nTerm ? nReaderTerm : nTerm;

4647

4648 if( n==0 ){

4649 if( nReaderTerm>0 ) return -1;

4650 if( nTerm>0 ) return 1;

4651 return 0;

4652 }

4653

4654 c = memcmp(pReaderTerm, pTerm, n);

4655 if( c!=0 ) return c;

4656 if( isPrefix && n==nTerm ) return 0;

4657 return nReaderTerm - nTerm;

4658 }

4659

4660 /****************************************************************/

4661 /* LeafWriter is used to collect terms and associated doclist data

4662 ** into leaf blocks in %_segments (see top of file for format info).

4663 ** Expected usage is:

4664 **

4665 ** LeafWriter writer;

4666 ** leafWriterInit(0, 0, &writer);

4667 ** while( sorted_terms_left_to_process ){

4668 ** // data is doclist data for that term.

4669 ** rc = leafWriterStep(v, &writer, pTerm, nTerm, pData, nData);

4670 ** if( rc!=SQLITE_OK ) goto err;

4671 ** }

4672 ** rc = leafWriterFinalize(v, &writer);

4673 **err:

4674 ** leafWriterDestroy(&writer);

4675 ** return rc;

4676 **

4677 ** leafWriterStep() may write a collected leaf out to %_segments.

4678 ** leafWriterFinalize() finishes writing any buffered data and stores

4679 ** a root node in %_segdir. leafWriterDestroy() frees all buffers and

4680 ** InteriorWriters allocated as part of writing this segment.

4681 **

4682 ** TODO(shess) Document leafWriterStepMerge().

4683 */

4684

4685 /* Put terms with data this big in their own block. */

4686 #define STANDALONE_MIN 1024

4687

4688 /* Keep leaf blocks below this size. */

4689 #define LEAF_MAX 2048

4690

4691 typedef struct LeafWriter {

4692 int iLevel;

4693 int idx;

4694 sqlite_int64 iStartBlockid; /* needed to create the root info */

4695 sqlite_int64 iEndBlockid; /* when we're done writing. */

4696

4697 DataBuffer term; /* previous encoded term */

4698 DataBuffer data; /* encoding buffer */

4699

4700 /* bytes of first term in the current node which distinguishes that

4701 ** term from the last term of the previous node.

4702 */

4703 int nTermDistinct;

4704

4705 InteriorWriter parentWriter; /* if we overflow */

4706 int has_parent;

4707 } LeafWriter;

4708

4709 static void leafWriterInit(int iLevel, int idx, LeafWriter *pWriter){

4710 CLEAR(pWriter);

4711 pWriter->iLevel = iLevel;

4712 pWriter->idx = idx;

4713

4714 dataBufferInit(&pWriter->term, 32);

4715

4716 /* Start out with a reasonably sized block, though it can grow. */

4717 dataBufferInit(&pWriter->data, LEAF_MAX);

4718 }

4719

4720 #ifndef NDEBUG

4721 /* Verify that the data is readable as a leaf node. */

4722 static void leafNodeValidate(const char *pData, int nData){

4723 int n, iDummy;

4724

4725 if( nData==0 ) return;

4726 assert( nData>0 );

4727 assert( pData!=0 );

4728 assert( pData+nData>pData );

4729

4730 /* Must lead with a varint(0) */

4731 n = getVarint32(pData, &iDummy);

4732 assert( iDummy==0 );

4733 assert( n>0 );

4734 assert( n<nData );

4735 pData += n;

4736 nData -= n;

4737

4738 /* Leading term length and data must fit in buffer. */

4739 n = getVarint32(pData, &iDummy);

4740 assert( n>0 );

4741 assert( iDummy>0 );

4742 assert( n+iDummy>0 );

4743 assert( n+iDummy<nData );

4744 pData += n+iDummy;

4745 nData -= n+iDummy;

4746

4747 /* Leading term's doclist length and data must fit. */

4748 n = getVarint32(pData, &iDummy);

4749 assert( n>0 );

4750 assert( iDummy>0 );

4751 assert( n+iDummy>0 );

4752 assert( n+iDummy<=nData );

4753 ASSERT_VALID_DOCLIST(DL_DEFAULT, pData+n, iDummy, NULL);

4754 pData += n+iDummy;

4755 nData -= n+iDummy;

4756

4757 /* Verify that trailing terms and doclists also are readable. */

4758 while( nData!=0 ){

4759 n = getVarint32(pData, &iDummy);

4760 assert( n>0 );

4761 assert( iDummy>=0 );

4762 assert( n<nData );

4763 pData += n;

4764 nData -= n;

4765 n = getVarint32(pData, &iDummy);

4766 assert( n>0 );

4767 assert( iDummy>0 );

4768 assert( n+iDummy>0 );

4769 assert( n+iDummy<nData );

4770 pData += n+iDummy;

4771 nData -= n+iDummy;

4772

4773 n = getVarint32(pData, &iDummy);

4774 assert( n>0 );

4775 assert( iDummy>0 );

4776 assert( n+iDummy>0 );

4777 assert( n+iDummy<=nData );

4778 ASSERT_VALID_DOCLIST(DL_DEFAULT, pData+n, iDummy, NULL);

4779 pData += n+iDummy;

4780 nData -= n+iDummy;

4781 }

4782 }

4783 #define ASSERT_VALID_LEAF_NODE(p, n) leafNodeValidate(p, n)

4784 #else

4785 #define ASSERT_VALID_LEAF_NODE(p, n) assert( 1 )

4786 #endif

4787

4788 /* Flush the current leaf node to %_segments, and adding the resulting

4789 ** blockid and the starting term to the interior node which will

4790 ** contain it.

4791 */

4792 static int leafWriterInternalFlush(fulltext_vtab v, LeafWriter pWriter,

4793 int iData, int nData){

4794 sqlite_int64 iBlockid = 0;

4795 const char *pStartingTerm;

4796 int nStartingTerm, rc, n;

4797

4798 /* Must have the leading varint(0) flag, plus at least some

4799 ** valid-looking data.

4800 */

4801 assert( nData>2 );

4802 assert( iData>=0 );

4803 assert( iData+nData<=pWriter->data.nData );

4804 ASSERT_VALID_LEAF_NODE(pWriter->data.pData+iData, nData);

4805

4806 rc = block_insert(v, pWriter->data.pData+iData, nData, &iBlockid);

4807 if( rc!=SQLITE_OK ) return rc;

4808 assert( iBlockid!=0 );

4809

4810 /* Reconstruct the first term in the leaf for purposes of building

4811 ** the interior node.

4812 */

4813 n = getVarint32(pWriter->data.pData+iData+1, &nStartingTerm);

4814 pStartingTerm = pWriter->data.pData+iData+1+n;

4815 assert( pWriter->data.nData>iData+1+n+nStartingTerm );

4816 assert( pWriter->nTermDistinct>0 );

4817 assert( pWriter->nTermDistinct<=nStartingTerm );

4818 nStartingTerm = pWriter->nTermDistinct;

4819

4820 if( pWriter->has_parent ){

4821 interiorWriterAppend(&pWriter->parentWriter,

4822 pStartingTerm, nStartingTerm, iBlockid);

4823 }else{

4824 interiorWriterInit(1, pStartingTerm, nStartingTerm, iBlockid,

4825 &pWriter->parentWriter);

4826 pWriter->has_parent = 1;

4827 }

4828

4829 /* Track the span of this segment's leaf nodes. */

4830 if( pWriter->iEndBlockid==0 ){

4831 pWriter->iEndBlockid = pWriter->iStartBlockid = iBlockid;

4832 }else{

4833 pWriter->iEndBlockid++;

4834 assert( iBlockid==pWriter->iEndBlockid );

4835 }

4836

4837 return SQLITE_OK;

4838 }

4839 static int leafWriterFlush(fulltext_vtab v, LeafWriter pWriter){

4840 int rc = leafWriterInternalFlush(v, pWriter, 0, pWriter->data.nData);

4841 if( rc!=SQLITE_OK ) return rc;

4842

4843 /* Re-initialize the output buffer. */

4844 dataBufferReset(&pWriter->data);

4845

4846 return SQLITE_OK;

4847 }

4848

4849 /* Fetch the root info for the segment. If the entire leaf fits

4850 ** within ROOT_MAX, then it will be returned directly, otherwise it

4851 ** will be flushed and the root info will be returned from the

4852 ** interior node. *piEndBlockid is set to the blockid of the last

4853 ** interior or leaf node written to disk (0 if none are written at

4854 ** all).

4855 */

4856 static int leafWriterRootInfo(fulltext_vtab v, LeafWriter pWriter,

4857 char *ppRootInfo, int pnRootInfo,

4858 sqlite_int64 *piEndBlockid){

4859 /* we can fit the segment entirely inline */

4860 if( !pWriter->has_parent && pWriter->data.nData<ROOT_MAX ){

4861 *ppRootInfo = pWriter->data.pData;

4862 *pnRootInfo = pWriter->data.nData;

4863 *piEndBlockid = 0;

4864 return SQLITE_OK;

4865 }

4866

4867 /* Flush remaining leaf data. */

4868 if( pWriter->data.nData>0 ){

4869 int rc = leafWriterFlush(v, pWriter);

4870 if( rc!=SQLITE_OK ) return rc;

4871 }

4872

4873 /* We must have flushed a leaf at some point. */

4874 assert( pWriter->has_parent );

4875

4876 /* Tenatively set the end leaf blockid as the end blockid. If the

4877 ** interior node can be returned inline, this will be the final

4878 ** blockid, otherwise it will be overwritten by

4879 ** interiorWriterRootInfo().

4880 */

4881 *piEndBlockid = pWriter->iEndBlockid;

4882

4883 return interiorWriterRootInfo(v, &pWriter->parentWriter,

4884 ppRootInfo, pnRootInfo, piEndBlockid);

4885 }

4886

4887 /* Collect the rootInfo data and store it into the segment directory.

4888 ** This has the effect of flushing the segment's leaf data to

4889 ** %_segments, and also flushing any interior nodes to %_segments.

4890 */

4891 static int leafWriterFinalize(fulltext_vtab v, LeafWriter pWriter){

4892 sqlite_int64 iEndBlockid;

4893 char *pRootInfo;

4894 int rc, nRootInfo;

4895

4896 rc = leafWriterRootInfo(v, pWriter, &pRootInfo, &nRootInfo, &iEndBlockid);

4897 if( rc!=SQLITE_OK ) return rc;

4898

4899 /* Don't bother storing an entirely empty segment. */

4900 if( iEndBlockid==0 && nRootInfo==0 ) return SQLITE_OK;

4901

4902 return segdir_set(v, pWriter->iLevel, pWriter->idx,

4903 pWriter->iStartBlockid, pWriter->iEndBlockid,

4904 iEndBlockid, pRootInfo, nRootInfo);

4905 }

4906

4907 static void leafWriterDestroy(LeafWriter *pWriter){

4908 if( pWriter->has_parent ) interiorWriterDestroy(&pWriter->parentWriter);

4909 dataBufferDestroy(&pWriter->term);

4910 dataBufferDestroy(&pWriter->data);

4911 }

4912

4913 /* Encode a term into the leafWriter, delta-encoding as appropriate.

4914 ** Returns the length of the new term which distinguishes it from the

4915 ** previous term, which can be used to set nTermDistinct when a node

4916 ** boundary is crossed.

4917 */

4918 static int leafWriterEncodeTerm(LeafWriter *pWriter,

4919 const char *pTerm, int nTerm){

4920 char c[VARINT_MAX+VARINT_MAX];

4921 int n, nPrefix = 0;

4922

4923 assert( nTerm>0 );

4924 while( nPrefix<pWriter->term.nData &&

4925 pTerm[nPrefix]==pWriter->term.pData[nPrefix] ){

4926 nPrefix++;

4927 /* Failing this implies that the terms weren't in order. */

4928 assert( nPrefix<nTerm );

4929 }

4930

4931 if( pWriter->data.nData==0 ){

4932 /* Encode the node header and leading term as:

4933 ** varint(0)

4934 ** varint(nTerm)

4935 ** char pTerm[nTerm]

4936 */

4937 n = putVarint(c, '\0');

4938 n += putVarint(c+n, nTerm);

4939 dataBufferAppend2(&pWriter->data, c, n, pTerm, nTerm);

4940 }else{

4941 /* Delta-encode the term as:

4942 ** varint(nPrefix)

4943 ** varint(nSuffix)

4944 ** char pTermSuffix[nSuffix]

4945 */

4946 n = putVarint(c, nPrefix);

4947 n += putVarint(c+n, nTerm-nPrefix);

4948 dataBufferAppend2(&pWriter->data, c, n, pTerm+nPrefix, nTerm-nPrefix);

4949 }

4950 dataBufferReplace(&pWriter->term, pTerm, nTerm);

4951

4952 return nPrefix+1;

4953 }

4954

4955 /* Used to avoid a memmove when a large amount of doclist data is in

4956 ** the buffer. This constructs a node and term header before

4957 ** iDoclistData and flushes the resulting complete node using

4958 ** leafWriterInternalFlush().

4959 */

4960 static int leafWriterInlineFlush(fulltext_vtab v, LeafWriter pWriter,

4961 const char *pTerm, int nTerm,

4962 int iDoclistData){

4963 char c[VARINT_MAX+VARINT_MAX];

4964 int iData, n = putVarint(c, 0);

4965 n += putVarint(c+n, nTerm);

4966

4967 /* There should always be room for the header. Even if pTerm shared

4968 ** a substantial prefix with the previous term, the entire prefix

4969 ** could be constructed from earlier data in the doclist, so there

4970 ** should be room.

4971 */

4972 assert( iDoclistData>=n+nTerm );

4973

4974 iData = iDoclistData-(n+nTerm);

4975 memcpy(pWriter->data.pData+iData, c, n);

4976 memcpy(pWriter->data.pData+iData+n, pTerm, nTerm);

4977

4978 return leafWriterInternalFlush(v, pWriter, iData, pWriter->data.nData-iData);

4979 }

4980

4981 /* Push pTerm[nTerm] along with the doclist data to the leaf layer of

4982 ** %_segments.

4983 */

4984 static int leafWriterStepMerge(fulltext_vtab v, LeafWriter pWriter,

4985 const char *pTerm, int nTerm,

4986 DLReader *pReaders, int nReaders){

4987 char c[VARINT_MAX+VARINT_MAX];

4988 int iTermData = pWriter->data.nData, iDoclistData;

4989 int i, nData, n, nActualData, nActual, rc, nTermDistinct;

4990

4991 ASSERT_VALID_LEAF_NODE(pWriter->data.pData, pWriter->data.nData);

4992 nTermDistinct = leafWriterEncodeTerm(pWriter, pTerm, nTerm);

4993

4994 /* Remember nTermDistinct if opening a new node. */

4995 if( iTermData==0 ) pWriter->nTermDistinct = nTermDistinct;

4996

4997 iDoclistData = pWriter->data.nData;

4998

4999 /* Estimate the length of the merged doclist so we can leave space

5000 ** to encode it.

5001 */

5002 for(i=0, nData=0; i<nReaders; i++){

5003 nData += dlrAllDataBytes(&pReaders[i]);

5004 }

5005 n = putVarint(c, nData);

5006 dataBufferAppend(&pWriter->data, c, n);

5007

5008 rc = docListMerge(&pWriter->data, pReaders, nReaders);

5009 if( rc!= SQLITE_OK ) return rc;

5010 ASSERT_VALID_DOCLIST(DL_DEFAULT,

5011 pWriter->data.pData+iDoclistData+n,

5012 pWriter->data.nData-iDoclistData-n, NULL);

5013

5014 /* The actual amount of doclist data at this point could be smaller

5015 ** than the length we encoded. Additionally, the space required to

5016 ** encode this length could be smaller. For small doclists, this is

5017 ** not a big deal, we can just use memmove() to adjust things.

5018 */

5019 nActualData = pWriter->data.nData-(iDoclistData+n);

5020 nActual = putVarint(c, nActualData);

5021 assert( nActualData<=nData );

5022 assert( nActual<=n );

5023

5024 /* If the new doclist is big enough for force a standalone leaf

5025 ** node, we can immediately flush it inline without doing the

5026 ** memmove().

5027 */

5028 /* TODO(shess) This test matches leafWriterStep(), which does this

5029 ** test before it knows the cost to varint-encode the term and

5030 ** doclist lengths. At some point, change to

5031 ** pWriter->data.nData-iTermData>STANDALONE_MIN.

5032 */

5033 if( nTerm+nActualData>STANDALONE_MIN ){

5034 /* Push leaf node from before this term. */

5035 if( iTermData>0 ){

5036 rc = leafWriterInternalFlush(v, pWriter, 0, iTermData);

5037 if( rc!=SQLITE_OK ) return rc;

5038

5039 pWriter->nTermDistinct = nTermDistinct;

5040 }

5041

5042 /* Fix the encoded doclist length. */

5043 iDoclistData += n - nActual;

5044 memcpy(pWriter->data.pData+iDoclistData, c, nActual);

5045

5046 /* Push the standalone leaf node. */

5047 rc = leafWriterInlineFlush(v, pWriter, pTerm, nTerm, iDoclistData);

5048 if( rc!=SQLITE_OK ) return rc;

5049

5050 /* Leave the node empty. */

5051 dataBufferReset(&pWriter->data);

5052

5053 return rc;

5054 }

5055

5056 /* At this point, we know that the doclist was small, so do the

5057 ** memmove if indicated.

5058 */

5059 if( nActual<n ){

5060 memmove(pWriter->data.pData+iDoclistData+nActual,

5061 pWriter->data.pData+iDoclistData+n,

5062 pWriter->data.nData-(iDoclistData+n));

5063 pWriter->data.nData -= n-nActual;

5064 }

5065

5066 /* Replace written length with actual length. */

5067 memcpy(pWriter->data.pData+iDoclistData, c, nActual);

5068

5069 /* If the node is too large, break things up. */

5070 /* TODO(shess) This test matches leafWriterStep(), which does this

5071 ** test before it knows the cost to varint-encode the term and

5072 ** doclist lengths. At some point, change to

5073 ** pWriter->data.nData>LEAF_MAX.

5074 */

5075 if( iTermData+nTerm+nActualData>LEAF_MAX ){

5076 /* Flush out the leading data as a node */

5077 rc = leafWriterInternalFlush(v, pWriter, 0, iTermData);

5078 if( rc!=SQLITE_OK ) return rc;

5079

5080 pWriter->nTermDistinct = nTermDistinct;

5081

5082 /* Rebuild header using the current term */

5083 n = putVarint(pWriter->data.pData, 0);

5084 n += putVarint(pWriter->data.pData+n, nTerm);

5085 memcpy(pWriter->data.pData+n, pTerm, nTerm);

5086 n += nTerm;

5087

5088 /* There should always be room, because the previous encoding

5089 ** included all data necessary to construct the term.

5090 */

5091 assert( n<iDoclistData );

5092 /* So long as STANDALONE_MIN is half or less of LEAF_MAX, the

5093 ** following memcpy() is safe (as opposed to needing a memmove).

5094 */

5095 assert( 2*STANDALONE_MIN<=LEAF_MAX );

5096 assert( n+pWriter->data.nData-iDoclistData<iDoclistData );

5097 memcpy(pWriter->data.pData+n,

5098 pWriter->data.pData+iDoclistData,

5099 pWriter->data.nData-iDoclistData);

5100 pWriter->data.nData -= iDoclistData-n;

5101 }

5102 ASSERT_VALID_LEAF_NODE(pWriter->data.pData, pWriter->data.nData);

5103

5104 return SQLITE_OK;

5105 }

5106

5107 /* Push pTerm[nTerm] along with the doclist data to the leaf layer of

5108 ** %_segments.

5109 */

5110 /* TODO(shess) Revise writeZeroSegment() so that doclists are

5111 ** constructed directly in pWriter->data.

5112 */

5113 static int leafWriterStep(fulltext_vtab v, LeafWriter pWriter,

5114 const char *pTerm, int nTerm,

5115 const char *pData, int nData){

5116 int rc;

5117 DLReader reader;

5118

5119 rc = dlrInit(&reader, DL_DEFAULT, pData, nData);

5120 if( rc!=SQLITE_OK ) return rc;

5121 rc = leafWriterStepMerge(v, pWriter, pTerm, nTerm, &reader, 1);

5122 dlrDestroy(&reader);

5123

5124 return rc;

5125 }

5126

5127

5128 /****************************************************************/

5129 /* LeafReader is used to iterate over an individual leaf node. */

5130 typedef struct LeafReader {

5131 DataBuffer term; /* copy of current term. */

5132

5133 const char pData; / data for current term. */

5134 int nData;

5135 } LeafReader;

5136

5137 static void leafReaderDestroy(LeafReader *pReader){

5138 dataBufferDestroy(&pReader->term);

5139 SCRAMBLE(pReader);

5140 }

5141

5142 static int leafReaderAtEnd(LeafReader *pReader){

5143 return pReader->nData<=0;

5144 }

5145

5146 /* Access the current term. */

5147 static int leafReaderTermBytes(LeafReader *pReader){

5148 return pReader->term.nData;

5149 }

5150 static const char leafReaderTerm(LeafReader pReader){

5151 assert( pReader->term.nData>0 );

5152 return pReader->term.pData;

5153 }

5154

5155 /* Access the doclist data for the current term. */

5156 static int leafReaderDataBytes(LeafReader *pReader){

5157 int nData;

5158 assert( pReader->term.nData>0 );

5159 getVarint32(pReader->pData, &nData);

5160 return nData;

5161 }

5162 static const char leafReaderData(LeafReader pReader){

5163 int n, nData;

5164 assert( pReader->term.nData>0 );

5165 n = getVarint32Safe(pReader->pData, &nData, pReader->nData);

5166 if( !n \|\| nData>pReader->nData-n ) return NULL;

5167 return pReader->pData+n;

5168 }

5169

5170 static int leafReaderInit(const char pData, int nData, LeafReader pReader){

5171 int nTerm, n;

5172

5173 /* All callers check this precondition. */

5174 assert( nData>0 );

5175 assert( pData[0]=='\0' );

5176

5177 CLEAR(pReader);

5178

5179 /* Read the first term, skipping the header byte. */

5180 n = getVarint32Safe(pData+1, &nTerm, nData-1);

5181 if( !n \|\| nTerm<0 \|\| nTerm>nData-1-n ) return SQLITE_CORRUPT_BKPT;

5182 dataBufferInit(&pReader->term, nTerm);

5183 dataBufferReplace(&pReader->term, pData+1+n, nTerm);

5184

5185 /* Position after the first term. */

5186 pReader->pData = pData+1+n+nTerm;

5187 pReader->nData = nData-1-n-nTerm;

5188 return SQLITE_OK;

5189 }

5190

5191 /* Step the reader forward to the next term. */

5192 static int leafReaderStep(LeafReader *pReader){

5193 int n, nData, nPrefix, nSuffix;

5194 assert( !leafReaderAtEnd(pReader) );

5195

5196 /* Skip previous entry's data block. */

5197 n = getVarint32Safe(pReader->pData, &nData, pReader->nData);

5198 if( !n \|\| nData<0 \|\| nData>pReader->nData-n ) return SQLITE_CORRUPT_BKPT;

5199 pReader->pData += n+nData;

5200 pReader->nData -= n+nData;

5201

5202 if( !leafReaderAtEnd(pReader) ){

5203 /* Construct the new term using a prefix from the old term plus a

5204 ** suffix from the leaf data.

5205 */

5206 n = getVarint32Safe(pReader->pData, &nPrefix, pReader->nData);

5207 if( !n ) return SQLITE_CORRUPT_BKPT;

5208 pReader->nData -= n;

5209 pReader->pData += n;

5210 n = getVarint32Safe(pReader->pData, &nSuffix, pReader->nData);

5211 if( !n ) return SQLITE_CORRUPT_BKPT;

5212 pReader->nData -= n;

5213 pReader->pData += n;

5214 if( nSuffix<0 \|\| nSuffix>pReader->nData ) return SQLITE_CORRUPT_BKPT;

5215 if( nPrefix<0 \|\| nPrefix>pReader->term.nData ) return SQLITE_CORRUPT_BKPT;

5216 pReader->term.nData = nPrefix;

5217 dataBufferAppend(&pReader->term, pReader->pData, nSuffix);

5218

5219 pReader->pData += nSuffix;

5220 pReader->nData -= nSuffix;

5221 }

5222 return SQLITE_OK;

5223 }

5224

5225 /* strcmp-style comparison of pReader's current term against pTerm.

5226 ** If isPrefix, equality means equal through nTerm bytes.

5227 */

5228 static int leafReaderTermCmp(LeafReader *pReader,

5229 const char *pTerm, int nTerm, int isPrefix){

5230 int c, n = pReader->term.nData<nTerm ? pReader->term.nData : nTerm;

5231 if( n==0 ){

5232 if( pReader->term.nData>0 ) return -1;

5233 if(nTerm>0 ) return 1;

5234 return 0;

5235 }

5236

5237 c = memcmp(pReader->term.pData, pTerm, n);

5238 if( c!=0 ) return c;

5239 if( isPrefix && n==nTerm ) return 0;

5240 return pReader->term.nData - nTerm;

5241 }

5242

5243

5244 /****************************************************************/

5245 /* LeavesReader wraps LeafReader to allow iterating over the entire

5246 ** leaf layer of the tree.

5247 */

5248 typedef struct LeavesReader {

5249 int idx; /* Index within the segment. */

5250

5251 sqlite3_stmt pStmt; / Statement we're streaming leaves from. */

5252 int eof; /* we've seen SQLITE_DONE from pStmt. */

5253

5254 LeafReader leafReader; /* reader for the current leaf. */

5255 DataBuffer rootData; /* root data for inline. */

5256 } LeavesReader;

5257

5258 /* Access the current term. */

5259 static int leavesReaderTermBytes(LeavesReader *pReader){

5260 assert( !pReader->eof );

5261 return leafReaderTermBytes(&pReader->leafReader);

5262 }

5263 static const char leavesReaderTerm(LeavesReader pReader){

5264 assert( !pReader->eof );

5265 return leafReaderTerm(&pReader->leafReader);

5266 }

5267

5268 /* Access the doclist data for the current term. */

5269 static int leavesReaderDataBytes(LeavesReader *pReader){

5270 assert( !pReader->eof );

5271 return leafReaderDataBytes(&pReader->leafReader);

5272 }

5273 static const char leavesReaderData(LeavesReader pReader){

5274 assert( !pReader->eof );

5275 return leafReaderData(&pReader->leafReader);

5276 }

5277

5278 static int leavesReaderAtEnd(LeavesReader *pReader){

5279 return pReader->eof;

5280 }

5281

5282 /* loadSegmentLeaves() may not read all the way to SQLITE_DONE, thus

5283 ** leaving the statement handle open, which locks the table.

5284 */

5285 /* TODO(shess) This "solution" is not satisfactory. Really, there

5286 ** should be check-in function for all statement handles which

5287 ** arranges to call sqlite3_reset(). This most likely will require

5288 ** modification to control flow all over the place, though, so for now

5289 ** just punt.

5290 **

5291 ** Note the the current system assumes that segment merges will run to

5292 ** completion, which is why this particular probably hasn't arisen in

5293 ** this case. Probably a brittle assumption.

5294 */

5295 static int leavesReaderReset(LeavesReader *pReader){

5296 return sqlite3_reset(pReader->pStmt);

5297 }

5298

5299 static void leavesReaderDestroy(LeavesReader *pReader){

5300 /* If idx is -1, that means we're using a non-cached statement

5301 ** handle in the optimize() case, so we need to release it.

5302 */

5303 if( pReader->pStmt!=NULL && pReader->idx==-1 ){

5304 sqlite3_finalize(pReader->pStmt);

5305 }

5306 leafReaderDestroy(&pReader->leafReader);

5307 dataBufferDestroy(&pReader->rootData);

5308 SCRAMBLE(pReader);

5309 }

5310

5311 /* Initialize pReader with the given root data (if iStartBlockid==0

5312 ** the leaf data was entirely contained in the root), or from the

5313 ** stream of blocks between iStartBlockid and iEndBlockid, inclusive.

5314 */

5315 /* TODO(shess): Figure out a means of indicating how many leaves are

5316 ** expected, for purposes of detecting corruption.

5317 */

5318 static int leavesReaderInit(fulltext_vtab *v,

5319 int idx,

5320 sqlite_int64 iStartBlockid,

5321 sqlite_int64 iEndBlockid,

5322 const char *pRootData, int nRootData,

5323 LeavesReader *pReader){

5324 CLEAR(pReader);

5325 pReader->idx = idx;

5326

5327 dataBufferInit(&pReader->rootData, 0);

5328 if( iStartBlockid==0 ){

5329 int rc;

5330 /* Corrupt if this can't be a leaf node. */

5331 if( pRootData==NULL \|\| nRootData<1 \|\| pRootData[0]!='\0' ){

5332 return SQLITE_CORRUPT_BKPT;

5333 }

5334 /* Entire leaf level fit in root data. */

5335 dataBufferReplace(&pReader->rootData, pRootData, nRootData);

5336 rc = leafReaderInit(pReader->rootData.pData, pReader->rootData.nData,

5337 &pReader->leafReader);

5338 if( rc!=SQLITE_OK ){

5339 dataBufferDestroy(&pReader->rootData);

5340 return rc;

5341 }

5342 }else{

5343 sqlite3_stmt *s;

5344 int rc = sql_get_leaf_statement(v, idx, &s);

5345 if( rc!=SQLITE_OK ) return rc;

5346

5347 rc = sqlite3_bind_int64(s, 1, iStartBlockid);

5348 if( rc!=SQLITE_OK ) goto err;

5349

5350 rc = sqlite3_bind_int64(s, 2, iEndBlockid);

5351 if( rc!=SQLITE_OK ) goto err;

5352

5353 rc = sqlite3_step(s);

5354

5355 /* Corrupt if interior node referenced missing leaf node. */

5356 if( rc==SQLITE_DONE ){

5357 rc = SQLITE_CORRUPT_BKPT;

5358 goto err;

5359 }

5360

5361 if( rc!=SQLITE_ROW ) goto err;

5362 rc = SQLITE_OK;

5363

5364 /* Corrupt if leaf data isn't a blob. */

5365 if( sqlite3_column_type(s, 0)!=SQLITE_BLOB ){

5366 rc = SQLITE_CORRUPT_BKPT;

5367 }else{

5368 const char *pLeafData = sqlite3_column_blob(s, 0);

5369 int nLeafData = sqlite3_column_bytes(s, 0);

5370

5371 /* Corrupt if this can't be a leaf node. */

5372 if( pLeafData==NULL \|\| nLeafData<1 \|\| pLeafData[0]!='\0' ){

5373 rc = SQLITE_CORRUPT_BKPT;

5374 }else{

5375 rc = leafReaderInit(pLeafData, nLeafData, &pReader->leafReader);

5376 }

5377 }

5378

5379 err:

5380 if( rc!=SQLITE_OK ){

5381 if( idx==-1 ){

5382 sqlite3_finalize(s);

5383 }else{

5384 sqlite3_reset(s);

5385 }

5386 return rc;

5387 }

5388

5389 pReader->pStmt = s;

5390 }

5391 return SQLITE_OK;

5392 }

5393

5394 /* Step the current leaf forward to the next term. If we reach the

5395 ** end of the current leaf, step forward to the next leaf block.

5396 */

5397 static int leavesReaderStep(fulltext_vtab v, LeavesReader pReader){

5398 int rc;

5399 assert( !leavesReaderAtEnd(pReader) );

5400 rc = leafReaderStep(&pReader->leafReader);

5401 if( rc!=SQLITE_OK ) return rc;

5402

5403 if( leafReaderAtEnd(&pReader->leafReader) ){

5404 if( pReader->rootData.pData ){

5405 pReader->eof = 1;

5406 return SQLITE_OK;

5407 }

5408 rc = sqlite3_step(pReader->pStmt);

5409 if( rc!=SQLITE_ROW ){

5410 pReader->eof = 1;

5411 return rc==SQLITE_DONE ? SQLITE_OK : rc;

5412 }

5413

5414 /* Corrupt if leaf data isn't a blob. */

5415 if( sqlite3_column_type(pReader->pStmt, 0)!=SQLITE_BLOB ){

5416 return SQLITE_CORRUPT_BKPT;

5417 }else{

5418 LeafReader tmp;

5419 const char *pLeafData = sqlite3_column_blob(pReader->pStmt, 0);

5420 int nLeafData = sqlite3_column_bytes(pReader->pStmt, 0);

5421

5422 /* Corrupt if this can't be a leaf node. */

5423 if( pLeafData==NULL \|\| nLeafData<1 \|\| pLeafData[0]!='\0' ){

5424 return SQLITE_CORRUPT_BKPT;

5425 }

5426

5427 rc = leafReaderInit(pLeafData, nLeafData, &tmp);

5428 if( rc!=SQLITE_OK ) return rc;

5429 leafReaderDestroy(&pReader->leafReader);

5430 pReader->leafReader = tmp;

5431 }

5432 }

5433 return SQLITE_OK;

5434 }

5435

5436 /* Order LeavesReaders by their term, ignoring idx. Readers at eof

5437 ** always sort to the end.

5438 */

5439 static int leavesReaderTermCmp(LeavesReader lr1, LeavesReader lr2){

5440 if( leavesReaderAtEnd(lr1) ){

5441 if( leavesReaderAtEnd(lr2) ) return 0;

5442 return 1;

5443 }

5444 if( leavesReaderAtEnd(lr2) ) return -1;

5445

5446 return leafReaderTermCmp(&lr1->leafReader,

5447 leavesReaderTerm(lr2), leavesReaderTermBytes(lr2),

5448 0);

5449 }

5450

5451 /* Similar to leavesReaderTermCmp(), with additional ordering by idx

5452 ** so that older segments sort before newer segments.

5453 */

5454 static int leavesReaderCmp(LeavesReader lr1, LeavesReader lr2){

5455 int c = leavesReaderTermCmp(lr1, lr2);

5456 if( c!=0 ) return c;

5457 return lr1->idx-lr2->idx;

5458 }

5459

5460 /* Assume that pLr[1]..pLr[nLr] are sorted. Bubble pLr[0] into its

5461 ** sorted position.

5462 */

5463 static void leavesReaderReorder(LeavesReader *pLr, int nLr){

5464 while( nLr>1 && leavesReaderCmp(pLr, pLr+1)>0 ){

5465 LeavesReader tmp = pLr[0];

5466 pLr[0] = pLr[1];

5467 pLr[1] = tmp;

5468 nLr--;

5469 pLr++;

5470 }

5471 }

5472

5473 /* Initializes pReaders with the segments from level iLevel, returning

5474 ** the number of segments in *piReaders. Leaves pReaders in sorted

5475 ** order.

5476 */

5477 static int leavesReadersInit(fulltext_vtab *v, int iLevel,

5478 LeavesReader pReaders, int piReaders){

5479 sqlite3_stmt *s;

5480 int i, rc = sql_get_statement(v, SEGDIR_SELECT_LEVEL_STMT, &s);

5481 if( rc!=SQLITE_OK ) return rc;

5482

5483 rc = sqlite3_bind_int(s, 1, iLevel);

5484 if( rc!=SQLITE_OK ) return rc;

5485

5486 i = 0;

5487 while( (rc = sqlite3_step(s))==SQLITE_ROW ){

5488 sqlite_int64 iStart = sqlite3_column_int64(s, 0);

5489 sqlite_int64 iEnd = sqlite3_column_int64(s, 1);

5490 const char *pRootData = sqlite3_column_blob(s, 2);

5491 int nRootData = sqlite3_column_bytes(s, 2);

5492 sqlite_int64 iIndex = sqlite3_column_int64(s, 3);

5493

5494 /* Corrupt if we get back different types than we stored. */

5495 /* Also corrupt if the index is not sequential starting at 0. */

5496 if( sqlite3_column_type(s, 0)!=SQLITE_INTEGER \|\|

5497 sqlite3_column_type(s, 1)!=SQLITE_INTEGER \|\|

5498 sqlite3_column_type(s, 2)!=SQLITE_BLOB \|\|

5499 i!=iIndex \|\|

5500 i>=MERGE_COUNT ){

5501 rc = SQLITE_CORRUPT_BKPT;

5502 break;

5503 }

5504

5505 rc = leavesReaderInit(v, i, iStart, iEnd, pRootData, nRootData,

5506 &pReaders[i]);

5507 if( rc!=SQLITE_OK ) break;

5508

5509 i++;

5510 }

5511 if( rc!=SQLITE_DONE ){

5512 while( i-->0 ){

5513 leavesReaderDestroy(&pReaders[i]);

5514 }

5515 sqlite3_reset(s); /* So we don't leave a lock. */

5516 return rc;

5517 }

5518

5519 *piReaders = i;

5520

5521 /* Leave our results sorted by term, then age. */

5522 while( i-- ){

5523 leavesReaderReorder(pReaders+i, *piReaders-i);

5524 }

5525 return SQLITE_OK;

5526 }

5527

5528 /* Merge doclists from pReaders[nReaders] into a single doclist, which

5529 ** is written to pWriter. Assumes pReaders is ordered oldest to

5530 ** newest.

5531 */

5532 /* TODO(shess) Consider putting this inline in segmentMerge(). */

5533 static int leavesReadersMerge(fulltext_vtab *v,

5534 LeavesReader *pReaders, int nReaders,

5535 LeafWriter *pWriter){

5536 DLReader dlReaders[MERGE_COUNT];

5537 const char *pTerm = leavesReaderTerm(pReaders);

5538 int i, nTerm = leavesReaderTermBytes(pReaders);

5539 int rc;

5540

5541 assert( nReaders<=MERGE_COUNT );

5542

5543 for(i=0; i<nReaders; i++){

5544 const char *pData = leavesReaderData(pReaders+i);

5545 if( pData==NULL ){

5546 rc = SQLITE_CORRUPT_BKPT;

5547 break;

5548 }

5549 rc = dlrInit(&dlReaders[i], DL_DEFAULT,

5550 pData,

5551 leavesReaderDataBytes(pReaders+i));

5552 if( rc!=SQLITE_OK ) break;

5553 }

5554 if( rc!=SQLITE_OK ){

5555 while( i-->0 ){

5556 dlrDestroy(&dlReaders[i]);

5557 }

5558 return rc;

5559 }

5560

5561 return leafWriterStepMerge(v, pWriter, pTerm, nTerm, dlReaders, nReaders);

5562 }

5563

5564 /* Forward ref due to mutual recursion with segdirNextIndex(). */

5565 static int segmentMerge(fulltext_vtab *v, int iLevel);

5566

5567 /* Put the next available index at iLevel into *pidx. If iLevel

5568 ** already has MERGE_COUNT segments, they are merged to a higher

5569 ** level to make room.

5570 */

5571 static int segdirNextIndex(fulltext_vtab v, int iLevel, int pidx){

5572 int rc = segdir_max_index(v, iLevel, pidx);

5573 if( rc==SQLITE_DONE ){ /* No segments at iLevel. */

5574 *pidx = 0;

5575 }else if( rc==SQLITE_ROW ){

5576 if( *pidx==(MERGE_COUNT-1) ){

5577 rc = segmentMerge(v, iLevel);

5578 if( rc!=SQLITE_OK ) return rc;

5579 *pidx = 0;

5580 }else{

5581 (*pidx)++;

5582 }

5583 }else{

5584 return rc;

5585 }

5586 return SQLITE_OK;

5587 }

5588

5589 /* Merge MERGE_COUNT segments at iLevel into a new segment at

5590 ** iLevel+1. If iLevel+1 is already full of segments, those will be

5591 ** merged to make room.

5592 */

5593 static int segmentMerge(fulltext_vtab *v, int iLevel){

5594 LeafWriter writer;

5595 LeavesReader lrs[MERGE_COUNT];

5596 int i, rc, idx = 0;

5597

5598 /* Determine the next available segment index at the next level,

5599 ** merging as necessary.

5600 */

5601 rc = segdirNextIndex(v, iLevel+1, &idx);

5602 if( rc!=SQLITE_OK ) return rc;

5603

5604 /* TODO(shess) This assumes that we'll always see exactly

5605 ** MERGE_COUNT segments to merge at a given level. That will be

5606 ** broken if we allow the developer to request preemptive or

5607 ** deferred merging.

5608 */

5609 memset(&lrs, '\0', sizeof(lrs));

5610 rc = leavesReadersInit(v, iLevel, lrs, &i);

5611 if( rc!=SQLITE_OK ) return rc;

5612

5613 leafWriterInit(iLevel+1, idx, &writer);

5614

5615 if( i!=MERGE_COUNT ){

5616 rc = SQLITE_CORRUPT_BKPT;

5617 goto err;

5618 }

5619

5620 /* Since leavesReaderReorder() pushes readers at eof to the end,

5621 ** when the first reader is empty, all will be empty.

5622 */

5623 while( !leavesReaderAtEnd(lrs) ){

5624 /* Figure out how many readers share their next term. */

5625 for(i=1; i<MERGE_COUNT && !leavesReaderAtEnd(lrs+i); i++){

5626 if( 0!=leavesReaderTermCmp(lrs, lrs+i) ) break;

5627 }

5628

5629 rc = leavesReadersMerge(v, lrs, i, &writer);

5630 if( rc!=SQLITE_OK ) goto err;

5631

5632 /* Step forward those that were merged. */

5633 while( i-->0 ){

5634 rc = leavesReaderStep(v, lrs+i);

5635 if( rc!=SQLITE_OK ) goto err;

5636

5637 /* Reorder by term, then by age. */

5638 leavesReaderReorder(lrs+i, MERGE_COUNT-i);

5639 }

5640 }

5641

5642 for(i=0; i<MERGE_COUNT; i++){

5643 leavesReaderDestroy(&lrs[i]);

5644 }

5645

5646 rc = leafWriterFinalize(v, &writer);

5647 leafWriterDestroy(&writer);

5648 if( rc!=SQLITE_OK ) return rc;

5649

5650 /* Delete the merged segment data. */

5651 return segdir_delete(v, iLevel);

5652

5653 err:

5654 for(i=0; i<MERGE_COUNT; i++){

5655 leavesReaderDestroy(&lrs[i]);

5656 }

5657 leafWriterDestroy(&writer);

5658 return rc;

5659 }

5660

5661 /* Accumulate the union of acc and pData into acc. /

5662 static int docListAccumulateUnion(DataBuffer *acc,

5663 const char *pData, int nData) {

5664 DataBuffer tmp = *acc;

5665 int rc;

5666 dataBufferInit(acc, tmp.nData+nData);

5667 rc = docListUnion(tmp.pData, tmp.nData, pData, nData, acc);

5668 dataBufferDestroy(&tmp);

5669 return rc;

5670 }

5671

5672 /* TODO(shess) It might be interesting to explore different merge

5673 ** strategies, here. For instance, since this is a sorted merge, we

5674 ** could easily merge many doclists in parallel. With some

5675 ** comprehension of the storage format, we could merge all of the

5676 ** doclists within a leaf node directly from the leaf node's storage.

5677 ** It may be worthwhile to merge smaller doclists before larger

5678 ** doclists, since they can be traversed more quickly - but the

5679 ** results may have less overlap, making them more expensive in a

5680 ** different way.

5681 */

5682

5683 /* Scan pReader for pTerm/nTerm, and merge the term's doclist over

5684 ** out (any doclists with duplicate docids overwrite those in out).

5685 ** Internal function for loadSegmentLeaf().

5686 */

5687 static int loadSegmentLeavesInt(fulltext_vtab v, LeavesReader pReader,

5688 const char *pTerm, int nTerm, int isPrefix,

5689 DataBuffer *out){

5690 /* doclist data is accumulated into pBuffers similar to how one does

5691 ** increment in binary arithmetic. If index 0 is empty, the data is

5692 ** stored there. If there is data there, it is merged and the

5693 ** results carried into position 1, with further merge-and-carry

5694 ** until an empty position is found.

5695 */

5696 DataBuffer *pBuffers = NULL;

5697 int nBuffers = 0, nMaxBuffers = 0, rc;

5698

5699 assert( nTerm>0 );

5700

5701 for(rc=SQLITE_OK; rc==SQLITE_OK && !leavesReaderAtEnd(pReader);

5702 rc=leavesReaderStep(v, pReader)){

5703 /* TODO(shess) Really want leavesReaderTermCmp(), but that name is

5704 ** already taken to compare the terms of two LeavesReaders. Think

5705 ** on a better name. [Meanwhile, break encapsulation rather than

5706 ** use a confusing name.]

5707 */

5708 int c = leafReaderTermCmp(&pReader->leafReader, pTerm, nTerm, isPrefix);

5709 if( c>0 ) break; /* Past any possible matches. */

5710 if( c==0 ){

5711 int iBuffer, nData;

5712 const char *pData = leavesReaderData(pReader);

5713 if( pData==NULL ){

5714 rc = SQLITE_CORRUPT_BKPT;

5715 break;

5716 }

5717 nData = leavesReaderDataBytes(pReader);

5718

5719 /* Find the first empty buffer. */

5720 for(iBuffer=0; iBuffer<nBuffers; ++iBuffer){

5721 if( 0==pBuffers[iBuffer].nData ) break;

5722 }

5723

5724 /* Out of buffers, add an empty one. */

5725 if( iBuffer==nBuffers ){

5726 if( nBuffers==nMaxBuffers ){

5727 DataBuffer *p;

5728 nMaxBuffers += 20;

5729

5730 /* Manual realloc so we can handle NULL appropriately. */

5731 p = sqlite3_malloc(nMaxBufferssizeof(pBuffers));

5732 if( p==NULL ){

5733 rc = SQLITE_NOMEM;

5734 break;

5735 }

5736

5737 if( nBuffers>0 ){

5738 assert(pBuffers!=NULL);

5739 memcpy(p, pBuffers, nBufferssizeof(pBuffers));

5740 sqlite3_free(pBuffers);

5741 }

5742 pBuffers = p;

5743 }

5744 dataBufferInit(&(pBuffers[nBuffers]), 0);

5745 nBuffers++;

5746 }

5747

5748 /* At this point, must have an empty at iBuffer. */

5749 assert(iBuffer<nBuffers && pBuffers[iBuffer].nData==0);

5750

5751 /* If empty was first buffer, no need for merge logic. */

5752 if( iBuffer==0 ){

5753 dataBufferReplace(&(pBuffers[0]), pData, nData);

5754 }else{

5755 /* pAcc is the empty buffer the merged data will end up in. */

5756 DataBuffer *pAcc = &(pBuffers[iBuffer]);

5757 DataBuffer *p = &(pBuffers[0]);

5758

5759 /* Handle position 0 specially to avoid need to prime pAcc

5760 ** with pData/nData.

5761 */

5762 dataBufferSwap(p, pAcc);

5763 rc = docListAccumulateUnion(pAcc, pData, nData);

5764 if( rc!=SQLITE_OK ) goto err;

5765

5766 /* Accumulate remaining doclists into pAcc. */

5767 for(++p; p<pAcc; ++p){

5768 rc = docListAccumulateUnion(pAcc, p->pData, p->nData);

5769 if( rc!=SQLITE_OK ) goto err;

5770

5771 /* dataBufferReset() could allow a large doclist to blow up

5772 ** our memory requirements.

5773 */

5774 if( p->nCapacity<1024 ){

5775 dataBufferReset(p);

5776 }else{

5777 dataBufferDestroy(p);

5778 dataBufferInit(p, 0);

5779 }

5780 }

5781 }

5782 }

5783 }

5784

5785 /* Union all the doclists together into out. /

5786 /* TODO(shess) What if out is big? Sigh. /

5787 if( rc==SQLITE_OK && nBuffers>0 ){

5788 int iBuffer;

5789 for(iBuffer=0; iBuffer<nBuffers; ++iBuffer){

5790 if( pBuffers[iBuffer].nData>0 ){

5791 if( out->nData==0 ){

5792 dataBufferSwap(out, &(pBuffers[iBuffer]));

5793 }else{

5794 rc = docListAccumulateUnion(out, pBuffers[iBuffer].pData,

5795 pBuffers[iBuffer].nData);

5796 if( rc!=SQLITE_OK ) break;

5797 }

5798 }

5799 }

5800 }

5801

5802 err:

5803 while( nBuffers-- ){

5804 dataBufferDestroy(&(pBuffers[nBuffers]));

5805 }

5806 if( pBuffers!=NULL ) sqlite3_free(pBuffers);

5807

5808 return rc;

5809 }

5810

5811 /* Call loadSegmentLeavesInt() with pData/nData as input. */

5812 static int loadSegmentLeaf(fulltext_vtab v, const char pData, int nData,

5813 const char *pTerm, int nTerm, int isPrefix,

5814 DataBuffer *out){

5815 LeavesReader reader;

5816 int rc;

5817

5818 assert( nData>1 );

5819 assert( *pData=='\0' );

5820 rc = leavesReaderInit(v, 0, 0, 0, pData, nData, &reader);

5821 if( rc!=SQLITE_OK ) return rc;

5822

5823 rc = loadSegmentLeavesInt(v, &reader, pTerm, nTerm, isPrefix, out);

5824 leavesReaderReset(&reader);

5825 leavesReaderDestroy(&reader);

5826 return rc;

5827 }

5828

5829 /* Call loadSegmentLeavesInt() with the leaf nodes from iStartLeaf to

5830 ** iEndLeaf (inclusive) as input, and merge the resulting doclist into

5831 ** out.

5832 */

5833 static int loadSegmentLeaves(fulltext_vtab *v,

5834 sqlite_int64 iStartLeaf, sqlite_int64 iEndLeaf,

5835 const char *pTerm, int nTerm, int isPrefix,

5836 DataBuffer *out){

5837 int rc;

5838 LeavesReader reader;

5839

5840 assert( iStartLeaf<=iEndLeaf );

5841 rc = leavesReaderInit(v, 0, iStartLeaf, iEndLeaf, NULL, 0, &reader);

5842 if( rc!=SQLITE_OK ) return rc;

5843

5844 rc = loadSegmentLeavesInt(v, &reader, pTerm, nTerm, isPrefix, out);

5845 leavesReaderReset(&reader);

5846 leavesReaderDestroy(&reader);

5847 return rc;

5848 }

5849

5850 /* Taking pData/nData as an interior node, find the sequence of child

5851 ** nodes which could include pTerm/nTerm/isPrefix. Note that the

5852 ** interior node terms logically come between the blocks, so there is

5853 ** one more blockid than there are terms (that block contains terms >=

5854 ** the last interior-node term).

5855 */

5856 /* TODO(shess) The calling code may already know that the end child is

5857 ** not worth calculating, because the end may be in a later sibling

5858 ** node. Consider whether breaking symmetry is worthwhile. I suspect

5859 ** it is not worthwhile.

5860 */

5861 static int getChildrenContaining(const char *pData, int nData,

5862 const char *pTerm, int nTerm, int isPrefix,

5863 sqlite_int64 *piStartChild,

5864 sqlite_int64 *piEndChild){

5865 InteriorReader reader;

5866 int rc;

5867

5868 assert( nData>1 );

5869 assert( *pData!='\0' );

5870 rc = interiorReaderInit(pData, nData, &reader);

5871 if( rc!=SQLITE_OK ) return rc;

5872

5873 /* Scan for the first child which could contain pTerm/nTerm. */

5874 while( !interiorReaderAtEnd(&reader) ){

5875 if( interiorReaderTermCmp(&reader, pTerm, nTerm, 0)>0 ) break;

5876 rc = interiorReaderStep(&reader);

5877 if( rc!=SQLITE_OK ){

5878 interiorReaderDestroy(&reader);

5879 return rc;

5880 }

5881 }

5882 *piStartChild = interiorReaderCurrentBlockid(&reader);

5883

5884 /* Keep scanning to find a term greater than our term, using prefix

5885 ** comparison if indicated. If isPrefix is false, this will be the

5886 ** same blockid as the starting block.

5887 */

5888 while( !interiorReaderAtEnd(&reader) ){

5889 if( interiorReaderTermCmp(&reader, pTerm, nTerm, isPrefix)>0 ) break;

5890 rc = interiorReaderStep(&reader);

5891 if( rc!=SQLITE_OK ){

5892 interiorReaderDestroy(&reader);

5893 return rc;

5894 }

5895 }

5896 *piEndChild = interiorReaderCurrentBlockid(&reader);

5897

5898 interiorReaderDestroy(&reader);

5899

5900 /* Children must ascend, and if !prefix, both must be the same. */

5901 assert( piEndChild>=piStartChild );

5902 assert( isPrefix \|\| piStartChild==piEndChild );

5903 return rc;

5904 }

5905

5906 /* Read block at iBlockid and pass it with other params to

5907 ** getChildrenContaining().

5908 */

5909 static int loadAndGetChildrenContaining(

5910 fulltext_vtab *v,

5911 sqlite_int64 iBlockid,

5912 const char *pTerm, int nTerm, int isPrefix,

5913 sqlite_int64 piStartChild, sqlite_int64 piEndChild

5914 ){

5915 sqlite3_stmt *s = NULL;

5916 int rc;

5917

5918 assert( iBlockid!=0 );

5919 assert( pTerm!=NULL );

5920 assert( nTerm!=0 ); /* TODO(shess) Why not allow this? */

5921 assert( piStartChild!=NULL );

5922 assert( piEndChild!=NULL );

5923

5924 rc = sql_get_statement(v, BLOCK_SELECT_STMT, &s);

5925 if( rc!=SQLITE_OK ) return rc;

5926

5927 rc = sqlite3_bind_int64(s, 1, iBlockid);

5928 if( rc!=SQLITE_OK ) return rc;

5929

5930 rc = sqlite3_step(s);

5931 /* Corrupt if interior node references missing child node. */

5932 if( rc==SQLITE_DONE ) return SQLITE_CORRUPT_BKPT;

5933 if( rc!=SQLITE_ROW ) return rc;

5934

5935 /* Corrupt if child node isn't a blob. */

5936 if( sqlite3_column_type(s, 0)!=SQLITE_BLOB ){

5937 sqlite3_reset(s); /* So we don't leave a lock. */

5938 return SQLITE_CORRUPT_BKPT;

5939 }else{

5940 const char *pData = sqlite3_column_blob(s, 0);

5941 int nData = sqlite3_column_bytes(s, 0);

5942

5943 /* Corrupt if child is not a valid interior node. */

5944 if( pData==NULL \|\| nData<1 \|\| pData[0]=='\0' ){

5945 sqlite3_reset(s); /* So we don't leave a lock. */

5946 return SQLITE_CORRUPT_BKPT;

5947 }

5948

5949 rc = getChildrenContaining(pData, nData, pTerm, nTerm,

5950 isPrefix, piStartChild, piEndChild);

5951 if( rc!=SQLITE_OK ){

5952 sqlite3_reset(s);

5953 return rc;

5954 }

5955 }

5956

5957 /* We expect only one row. We must execute another sqlite3_step()

5958 * to complete the iteration; otherwise the table will remain

5959 * locked. */

5960 rc = sqlite3_step(s);

5961 if( rc==SQLITE_ROW ) return SQLITE_ERROR;

5962 if( rc!=SQLITE_DONE ) return rc;

5963

5964 return SQLITE_OK;

5965 }

5966

5967 /* Traverse the tree represented by pData[nData] looking for

5968 ** pTerm[nTerm], placing its doclist into *out. This is internal to

5969 ** loadSegment() to make error-handling cleaner.

5970 */

5971 static int loadSegmentInt(fulltext_vtab v, const char pData, int nData,

5972 sqlite_int64 iLeavesEnd,

5973 const char *pTerm, int nTerm, int isPrefix,

5974 DataBuffer *out){

5975 /* Special case where root is a leaf. */

5976 if( *pData=='\0' ){

5977 return loadSegmentLeaf(v, pData, nData, pTerm, nTerm, isPrefix, out);

5978 }else{

5979 int rc;

5980 sqlite_int64 iStartChild, iEndChild;

5981

5982 /* Process pData as an interior node, then loop down the tree

5983 ** until we find the set of leaf nodes to scan for the term.

5984 */

5985 rc = getChildrenContaining(pData, nData, pTerm, nTerm, isPrefix,

5986 &iStartChild, &iEndChild);

5987 if( rc!=SQLITE_OK ) return rc;

5988 while( iStartChild>iLeavesEnd ){

5989 sqlite_int64 iNextStart, iNextEnd;

5990 rc = loadAndGetChildrenContaining(v, iStartChild, pTerm, nTerm, isPrefix,

5991 &iNextStart, &iNextEnd);

5992 if( rc!=SQLITE_OK ) return rc;

5993

5994 /* If we've branched, follow the end branch, too. */

5995 if( iStartChild!=iEndChild ){

5996 sqlite_int64 iDummy;

5997 rc = loadAndGetChildrenContaining(v, iEndChild, pTerm, nTerm, isPrefix,

5998 &iDummy, &iNextEnd);

5999 if( rc!=SQLITE_OK ) return rc;

6000 }

6001

6002 assert( iNextStart<=iNextEnd );

6003 iStartChild = iNextStart;

6004 iEndChild = iNextEnd;

6005 }

6006 assert( iStartChild<=iLeavesEnd );

6007 assert( iEndChild<=iLeavesEnd );

6008

6009 /* Scan through the leaf segments for doclists. */

6010 return loadSegmentLeaves(v, iStartChild, iEndChild,

6011 pTerm, nTerm, isPrefix, out);

6012 }

6013 }

6014

6015 /* Call loadSegmentInt() to collect the doclist for pTerm/nTerm, then

6016 ** merge its doclist over *out (any duplicate doclists read from the

6017 ** segment rooted at pData will overwrite those in *out).

6018 */

6019 /* TODO(shess) Consider changing this to determine the depth of the

6020 ** leaves using either the first characters of interior nodes (when

6021 ** ==1, we're one level above the leaves), or the first character of

6022 ** the root (which will describe the height of the tree directly).

6023 ** Either feels somewhat tricky to me.

6024 */

6025 /* TODO(shess) The current merge is likely to be slow for large

6026 ** doclists (though it should process from newest/smallest to

6027 ** oldest/largest, so it may not be that bad). It might be useful to

6028 ** modify things to allow for N-way merging. This could either be

6029 ** within a segment, with pairwise merges across segments, or across

6030 ** all segments at once.

6031 */

6032 static int loadSegment(fulltext_vtab v, const char pData, int nData,

6033 sqlite_int64 iLeavesEnd,

6034 const char *pTerm, int nTerm, int isPrefix,

6035 DataBuffer *out){

6036 DataBuffer result;

6037 int rc;

6038

6039 /* Corrupt if segment root can't be valid. */

6040 if( pData==NULL \|\| nData<1 ) return SQLITE_CORRUPT_BKPT;

6041

6042 /* This code should never be called with buffered updates. */

6043 assert( v->nPendingData<0 );

6044

6045 dataBufferInit(&result, 0);

6046 rc = loadSegmentInt(v, pData, nData, iLeavesEnd,

6047 pTerm, nTerm, isPrefix, &result);

6048 if( rc==SQLITE_OK && result.nData>0 ){

6049 if( out->nData==0 ){

6050 DataBuffer tmp = *out;

6051 *out = result;

6052 result = tmp;

6053 }else{

6054 DataBuffer merged;

6055 DLReader readers[2];

6056

6057 rc = dlrInit(&readers[0], DL_DEFAULT, out->pData, out->nData);

6058 if( rc==SQLITE_OK ){

6059 rc = dlrInit(&readers[1], DL_DEFAULT, result.pData, result.nData);

6060 if( rc==SQLITE_OK ){

6061 dataBufferInit(&merged, out->nData+result.nData);

6062 rc = docListMerge(&merged, readers, 2);

6063 dataBufferDestroy(out);

6064 *out = merged;

6065 dlrDestroy(&readers[1]);

6066 }

6067 dlrDestroy(&readers[0]);

6068 }

6069 }

6070 }

6071

6072 dataBufferDestroy(&result);

6073 return rc;

6074 }

6075

6076 /* Scan the database and merge together the posting lists for the term

6077 ** into *out.

6078 */

6079 static int termSelect(fulltext_vtab *v, int iColumn,

6080 const char *pTerm, int nTerm, int isPrefix,

6081 DocListType iType, DataBuffer *out){

6082 DataBuffer doclist;

6083 sqlite3_stmt *s;

6084 int rc = sql_get_statement(v, SEGDIR_SELECT_ALL_STMT, &s);

6085 if( rc!=SQLITE_OK ) return rc;

6086

6087 /* This code should never be called with buffered updates. */

6088 assert( v->nPendingData<0 );

6089

6090 dataBufferInit(&doclist, 0);

6091

6092 /* Traverse the segments from oldest to newest so that newer doclist

6093 ** elements for given docids overwrite older elements.

6094 */

6095 while( (rc = sqlite3_step(s))==SQLITE_ROW ){

6096 const char *pData = sqlite3_column_blob(s, 2);

6097 const int nData = sqlite3_column_bytes(s, 2);

6098 const sqlite_int64 iLeavesEnd = sqlite3_column_int64(s, 1);

6099

6100 /* Corrupt if we get back different types than we stored. */

6101 if( sqlite3_column_type(s, 1)!=SQLITE_INTEGER \|\|

6102 sqlite3_column_type(s, 2)!=SQLITE_BLOB ){

6103 rc = SQLITE_CORRUPT_BKPT;

6104 goto err;

6105 }

6106

6107 rc = loadSegment(v, pData, nData, iLeavesEnd, pTerm, nTerm, isPrefix,

6108 &doclist);

6109 if( rc!=SQLITE_OK ) goto err;

6110 }

6111 if( rc==SQLITE_DONE ){

6112 rc = SQLITE_OK;

6113 if( doclist.nData!=0 ){

6114 /* TODO(shess) The old term_select_all() code applied the column

6115 ** restrict as we merged segments, leading to smaller buffers.

6116 ** This is probably worthwhile to bring back, once the new storage

6117 ** system is checked in.

6118 */

6119 if( iColumn==v->nColumn) iColumn = -1;

6120 rc = docListTrim(DL_DEFAULT, doclist.pData, doclist.nData,

6121 iColumn, iType, out);

6122 }

6123 }

6124

6125 err:

6126 sqlite3_reset(s); /* So we don't leave a lock. */

6127 dataBufferDestroy(&doclist);

6128 return rc;

6129 }

6130

6131 /****************************************************************/

6132 /* Used to hold hashtable data for sorting. */

6133 typedef struct TermData {

6134 const char *pTerm;

6135 int nTerm;

6136 DLCollector *pCollector;

6137 } TermData;

6138

6139 /* Orders TermData elements in strcmp fashion ( <0 for less-than, 0

6140 ** for equal, >0 for greater-than).

6141 */

6142 static int termDataCmp(const void av, const void bv){

6143 const TermData a = (const TermData )av;

6144 const TermData b = (const TermData )bv;

6145 int n = a->nTerm<b->nTerm ? a->nTerm : b->nTerm;

6146 int c = memcmp(a->pTerm, b->pTerm, n);

6147 if( c!=0 ) return c;

6148 return a->nTerm-b->nTerm;

6149 }

6150

6151 /* Order pTerms data by term, then write a new level 0 segment using

6152 ** LeafWriter.

6153 */

6154 static int writeZeroSegment(fulltext_vtab v, fts2Hash pTerms){

6155 fts2HashElem *e;

6156 int idx, rc, i, n;

6157 TermData *pData;

6158 LeafWriter writer;

6159 DataBuffer dl;

6160

6161 /* Determine the next index at level 0, merging as necessary. */

6162 rc = segdirNextIndex(v, 0, &idx);

6163 if( rc!=SQLITE_OK ) return rc;

6164

6165 n = fts2HashCount(pTerms);

6166 pData = sqlite3_malloc(n*sizeof(TermData));

6167

6168 for(i = 0, e = fts2HashFirst(pTerms); e; i++, e = fts2HashNext(e)){

6169 assert( i<n );

6170 pData[i].pTerm = fts2HashKey(e);

6171 pData[i].nTerm = fts2HashKeysize(e);

6172 pData[i].pCollector = fts2HashData(e);

6173 }

6174 assert( i==n );

6175

6176 /* TODO(shess) Should we allow user-defined collation sequences,

6177 ** here? I think we only need that once we support prefix searches.

6178 */

6179 if( n>1 ) qsort(pData, n, sizeof(*pData), termDataCmp);

6180

6181 /* TODO(shess) Refactor so that we can write directly to the segment

6182 ** DataBuffer, as happens for segment merges.

6183 */

6184 leafWriterInit(0, idx, &writer);

6185 dataBufferInit(&dl, 0);

6186 for(i=0; i<n; i++){

6187 dataBufferReset(&dl);

6188 dlcAddDoclist(pData[i].pCollector, &dl);

6189 rc = leafWriterStep(v, &writer,

6190 pData[i].pTerm, pData[i].nTerm, dl.pData, dl.nData);

6191 if( rc!=SQLITE_OK ) goto err;

6192 }

6193 rc = leafWriterFinalize(v, &writer);

6194

6195 err:

6196 dataBufferDestroy(&dl);

6197 sqlite3_free(pData);

6198 leafWriterDestroy(&writer);

6199 return rc;

6200 }

6201

6202 /* If pendingTerms has data, free it. */

6203 static int clearPendingTerms(fulltext_vtab *v){

6204 if( v->nPendingData>=0 ){

6205 fts2HashElem *e;

6206 for(e=fts2HashFirst(&v->pendingTerms); e; e=fts2HashNext(e)){

6207 dlcDelete(fts2HashData(e));

6208 }

6209 fts2HashClear(&v->pendingTerms);

6210 v->nPendingData = -1;

6211 }

6212 return SQLITE_OK;

6213 }

6214

6215 /* If pendingTerms has data, flush it to a level-zero segment, and

6216 ** free it.

6217 */

6218 static int flushPendingTerms(fulltext_vtab *v){

6219 if( v->nPendingData>=0 ){

6220 int rc = writeZeroSegment(v, &v->pendingTerms);

6221 if( rc==SQLITE_OK ) clearPendingTerms(v);

6222 return rc;

6223 }

6224 return SQLITE_OK;

6225 }

6226

6227 /* If pendingTerms is "too big", or docid is out of order, flush it.

6228 ** Regardless, be certain that pendingTerms is initialized for use.

6229 */

6230 static int initPendingTerms(fulltext_vtab *v, sqlite_int64 iDocid){

6231 /* TODO(shess) Explore whether partially flushing the buffer on

6232 ** forced-flush would provide better performance. I suspect that if

6233 ** we ordered the doclists by size and flushed the largest until the

6234 ** buffer was half empty, that would let the less frequent terms

6235 ** generate longer doclists.

6236 */

6237 if( iDocid<=v->iPrevDocid \|\| v->nPendingData>kPendingThreshold ){

6238 int rc = flushPendingTerms(v);

6239 if( rc!=SQLITE_OK ) return rc;

6240 }

6241 if( v->nPendingData<0 ){

6242 fts2HashInit(&v->pendingTerms, FTS2_HASH_STRING, 1);

6243 v->nPendingData = 0;

6244 }

6245 v->iPrevDocid = iDocid;

6246 return SQLITE_OK;

6247 }

6248

6249 /* This function implements the xUpdate callback; it is the top-level entry

6250 * point for inserting, deleting or updating a row in a full-text table. */

6251 static int fulltextUpdate(sqlite3_vtab pVtab, int nArg, sqlite3_value *ppArg,

6252 sqlite_int64 *pRowid){

6253 fulltext_vtab v = (fulltext_vtab ) pVtab;

6254 int rc;

6255

6256 TRACE(("FTS2 Update %p\n", pVtab));

6257

6258 if( nArg<2 ){

6259 rc = index_delete(v, sqlite3_value_int64(ppArg[0]));

6260 if( rc==SQLITE_OK ){

6261 /* If we just deleted the last row in the table, clear out the

6262 ** index data.

6263 */

6264 rc = content_exists(v);

6265 if( rc==SQLITE_ROW ){

6266 rc = SQLITE_OK;

6267 }else if( rc==SQLITE_DONE ){

6268 /* Clear the pending terms so we don't flush a useless level-0

6269 ** segment when the transaction closes.

6270 */

6271 rc = clearPendingTerms(v);

6272 if( rc==SQLITE_OK ){

6273 rc = segdir_delete_all(v);

6274 }

6275 }

6276 }

6277 } else if( sqlite3_value_type(ppArg[0]) != SQLITE_NULL ){

6278 /* An update:

6279 * ppArg[0] = old rowid

6280 * ppArg[1] = new rowid

6281 * ppArg[2..2+v->nColumn-1] = values

6282 * ppArg[2+v->nColumn] = value for magic column (we ignore this)

6283 */

6284 sqlite_int64 rowid = sqlite3_value_int64(ppArg[0]);

6285 if( sqlite3_value_type(ppArg[1]) != SQLITE_INTEGER \|\|

6286 sqlite3_value_int64(ppArg[1]) != rowid ){

6287 rc = SQLITE_ERROR; /* we don't allow changing the rowid */

6288 } else {

6289 assert( nArg==2+v->nColumn+1);

6290 rc = index_update(v, rowid, &ppArg[2]);

6291 }

6292 } else {

6293 /* An insert:

6294 * ppArg[1] = requested rowid

6295 * ppArg[2..2+v->nColumn-1] = values

6296 * ppArg[2+v->nColumn] = value for magic column (we ignore this)

6297 */

6298 assert( nArg==2+v->nColumn+1);

6299 rc = index_insert(v, ppArg[1], &ppArg[2], pRowid);

6300 }

6301

6302 return rc;

6303 }

6304

6305 static int fulltextSync(sqlite3_vtab *pVtab){

6306 TRACE(("FTS2 xSync()\n"));

6307 return flushPendingTerms((fulltext_vtab *)pVtab);

6308 }

6309

6310 static int fulltextBegin(sqlite3_vtab *pVtab){

6311 fulltext_vtab v = (fulltext_vtab ) pVtab;

6312 TRACE(("FTS2 xBegin()\n"));

6313

6314 /* Any buffered updates should have been cleared by the previous

6315 ** transaction.

6316 */

6317 assert( v->nPendingData<0 );

6318 return clearPendingTerms(v);

6319 }

6320

6321 static int fulltextCommit(sqlite3_vtab *pVtab){

6322 fulltext_vtab v = (fulltext_vtab ) pVtab;

6323 TRACE(("FTS2 xCommit()\n"));

6324

6325 /* Buffered updates should have been cleared by fulltextSync(). */

6326 assert( v->nPendingData<0 );

6327 return clearPendingTerms(v);

6328 }

6329

6330 static int fulltextRollback(sqlite3_vtab *pVtab){

6331 TRACE(("FTS2 xRollback()\n"));

6332 return clearPendingTerms((fulltext_vtab *)pVtab);

6333 }

6334

6335 /*

6336 ** Implementation of the snippet() function for FTS2

6337 */

6338 static void snippetFunc(

6339 sqlite3_context *pContext,

6340 int argc,

6341 sqlite3_value **argv

6342 ){

6343 fulltext_cursor *pCursor;

6344 if( argc<1 ) return;

6345 if( sqlite3_value_type(argv[0])!=SQLITE_BLOB \|\|

6346 sqlite3_value_bytes(argv[0])!=sizeof(pCursor) ){

6347 sqlite3_result_error(pContext, "illegal first argument to html_snippet",-1);

6348 }else{

6349 const char *zStart = "<b>";

6350 const char *zEnd = "</b>";

6351 const char *zEllipsis = "<b>...</b>";

6352 memcpy(&pCursor, sqlite3_value_blob(argv[0]), sizeof(pCursor));

6353 if( argc>=2 ){

6354 zStart = (const char*)sqlite3_value_text(argv[1]);

6355 if( argc>=3 ){

6356 zEnd = (const char*)sqlite3_value_text(argv[2]);

6357 if( argc>=4 ){

6358 zEllipsis = (const char*)sqlite3_value_text(argv[3]);

6359 }

6360 }

6361 }

6362 snippetAllOffsets(pCursor);

6363 snippetText(pCursor, zStart, zEnd, zEllipsis);

6364 sqlite3_result_text(pContext, pCursor->snippet.zSnippet,

6365 pCursor->snippet.nSnippet, SQLITE_STATIC);

6366 }

6367 }

6368

6369 /*

6370 ** Implementation of the offsets() function for FTS2

6371 */

6372 static void snippetOffsetsFunc(

6373 sqlite3_context *pContext,

6374 int argc,

6375 sqlite3_value **argv

6376 ){

6377 fulltext_cursor *pCursor;

6378 if( argc<1 ) return;

6379 if( sqlite3_value_type(argv[0])!=SQLITE_BLOB \|\|

6380 sqlite3_value_bytes(argv[0])!=sizeof(pCursor) ){

6381 sqlite3_result_error(pContext, "illegal first argument to offsets",-1);

6382 }else{

6383 memcpy(&pCursor, sqlite3_value_blob(argv[0]), sizeof(pCursor));

6384 snippetAllOffsets(pCursor);

6385 snippetOffsetText(&pCursor->snippet);

6386 sqlite3_result_text(pContext,

6387 pCursor->snippet.zOffset, pCursor->snippet.nOffset,

6388 SQLITE_STATIC);

6389 }

6390 }

6391

6392 /* OptLeavesReader is nearly identical to LeavesReader, except that

6393 ** where LeavesReader is geared towards the merging of complete

6394 ** segment levels (with exactly MERGE_COUNT segments), OptLeavesReader

6395 ** is geared towards implementation of the optimize() function, and

6396 ** can merge all segments simultaneously. This version may be

6397 ** somewhat less efficient than LeavesReader because it merges into an

6398 ** accumulator rather than doing an N-way merge, but since segment

6399 ** size grows exponentially (so segment count logrithmically) this is

6400 ** probably not an immediate problem.

6401 */

6402 /* TODO(shess): Prove that assertion, or extend the merge code to

6403 ** merge tree fashion (like the prefix-searching code does).

6404 */

6405 /* TODO(shess): OptLeavesReader and LeavesReader could probably be

6406 ** merged with little or no loss of performance for LeavesReader. The

6407 ** merged code would need to handle >MERGE_COUNT segments, and would

6408 ** also need to be able to optionally optimize away deletes.

6409 */

6410 typedef struct OptLeavesReader {

6411 /* Segment number, to order readers by age. */

6412 int segment;

6413 LeavesReader reader;

6414 } OptLeavesReader;

6415

6416 static int optLeavesReaderAtEnd(OptLeavesReader *pReader){

6417 return leavesReaderAtEnd(&pReader->reader);

6418 }

6419 static int optLeavesReaderTermBytes(OptLeavesReader *pReader){

6420 return leavesReaderTermBytes(&pReader->reader);

6421 }

6422 static const char optLeavesReaderData(OptLeavesReader pReader){

6423 return leavesReaderData(&pReader->reader);

6424 }

6425 static int optLeavesReaderDataBytes(OptLeavesReader *pReader){

6426 return leavesReaderDataBytes(&pReader->reader);

6427 }

6428 static const char optLeavesReaderTerm(OptLeavesReader pReader){

6429 return leavesReaderTerm(&pReader->reader);

6430 }

6431 static int optLeavesReaderStep(fulltext_vtab v, OptLeavesReader pReader){

6432 return leavesReaderStep(v, &pReader->reader);

6433 }

6434 static int optLeavesReaderTermCmp(OptLeavesReader lr1, OptLeavesReader lr2){

6435 return leavesReaderTermCmp(&lr1->reader, &lr2->reader);

6436 }

6437 /* Order by term ascending, segment ascending (oldest to newest), with

6438 ** exhausted readers to the end.

6439 */

6440 static int optLeavesReaderCmp(OptLeavesReader lr1, OptLeavesReader lr2){

6441 int c = optLeavesReaderTermCmp(lr1, lr2);

6442 if( c!=0 ) return c;

6443 return lr1->segment-lr2->segment;

6444 }

6445 /* Bubble pLr[0] to appropriate place in pLr[1..nLr-1]. Assumes that

6446 ** pLr[1..nLr-1] is already sorted.

6447 */

6448 static void optLeavesReaderReorder(OptLeavesReader *pLr, int nLr){

6449 while( nLr>1 && optLeavesReaderCmp(pLr, pLr+1)>0 ){

6450 OptLeavesReader tmp = pLr[0];

6451 pLr[0] = pLr[1];

6452 pLr[1] = tmp;

6453 nLr--;

6454 pLr++;

6455 }

6456 }

6457

6458 /* optimize() helper function. Put the readers in order and iterate

6459 ** through them, merging doclists for matching terms into pWriter.

6460 ** Returns SQLITE_OK on success, or the SQLite error code which

6461 ** prevented success.

6462 */

6463 static int optimizeInternal(fulltext_vtab *v,

6464 OptLeavesReader *readers, int nReaders,

6465 LeafWriter *pWriter){

6466 int i, rc = SQLITE_OK;

6467 DataBuffer doclist, merged, tmp;

6468 const char *pData;

6469

6470 /* Order the readers. */

6471 i = nReaders;

6472 while( i-- > 0 ){

6473 optLeavesReaderReorder(&readers[i], nReaders-i);

6474 }

6475

6476 dataBufferInit(&doclist, LEAF_MAX);

6477 dataBufferInit(&merged, LEAF_MAX);

6478

6479 /* Exhausted readers bubble to the end, so when the first reader is

6480 ** at eof, all are at eof.

6481 */

6482 while( !optLeavesReaderAtEnd(&readers[0]) ){

6483

6484 /* Figure out how many readers share the next term. */

6485 for(i=1; i<nReaders && !optLeavesReaderAtEnd(&readers[i]); i++){

6486 if( 0!=optLeavesReaderTermCmp(&readers[0], &readers[i]) ) break;

6487 }

6488

6489 pData = optLeavesReaderData(&readers[0]);

6490 if( pData==NULL ){

6491 rc = SQLITE_CORRUPT_BKPT;

6492 break;

6493 }

6494

6495 /* Special-case for no merge. */

6496 if( i==1 ){

6497 /* Trim deletions from the doclist. */

6498 dataBufferReset(&merged);

6499 rc = docListTrim(DL_DEFAULT,

6500 pData,

6501 optLeavesReaderDataBytes(&readers[0]),

6502 -1, DL_DEFAULT, &merged);

6503 if( rc!= SQLITE_OK ) break;

6504 }else{

6505 DLReader dlReaders[MERGE_COUNT];

6506 int iReader, nReaders;

6507

6508 /* Prime the pipeline with the first reader's doclist. After

6509 ** one pass index 0 will reference the accumulated doclist.

6510 */

6511 rc = dlrInit(&dlReaders[0], DL_DEFAULT,

6512 pData,

6513 optLeavesReaderDataBytes(&readers[0]));

6514 if( rc!=SQLITE_OK ) break;

6515 iReader = 1;

6516

6517 assert( iReader<i ); /* Must execute the loop at least once. */

6518 while( iReader<i ){

6519 /* Merge 16 inputs per pass. */

6520 for( nReaders=1; iReader<i && nReaders<MERGE_COUNT;

6521 iReader++, nReaders++ ){

6522 pData = optLeavesReaderData(&readers[iReader]);

6523 if( pData == NULL ){

6524 rc = SQLITE_CORRUPT_BKPT;

6525 break;

6526 }

6527 rc = dlrInit(&dlReaders[nReaders], DL_DEFAULT,

6528 pData,

6529 optLeavesReaderDataBytes(&readers[iReader]));

6530 if( rc != SQLITE_OK ) break;

6531 }

6532

6533 /* Merge doclists and swap result into accumulator. */

6534 if( rc==SQLITE_OK ){

6535 dataBufferReset(&merged);

6536 rc = docListMerge(&merged, dlReaders, nReaders);

6537 tmp = merged;

6538 merged = doclist;

6539 doclist = tmp;

6540 }

6541

6542 while( nReaders-- > 0 ){

6543 dlrDestroy(&dlReaders[nReaders]);

6544 }

6545

6546 if( rc!=SQLITE_OK ) goto err;

6547

6548 /* Accumulated doclist to reader 0 for next pass. */

6549 rc = dlrInit(&dlReaders[0], DL_DEFAULT, doclist.pData, doclist.nData);

6550 if( rc!=SQLITE_OK ) goto err;

6551 }

6552

6553 /* Destroy reader that was left in the pipeline. */

6554 dlrDestroy(&dlReaders[0]);

6555

6556 /* Trim deletions from the doclist. */

6557 dataBufferReset(&merged);

6558 rc = docListTrim(DL_DEFAULT, doclist.pData, doclist.nData,

6559 -1, DL_DEFAULT, &merged);

6560 if( rc!=SQLITE_OK ) goto err;

6561 }

6562

6563 /* Only pass doclists with hits (skip if all hits deleted). */

6564 if( merged.nData>0 ){

6565 rc = leafWriterStep(v, pWriter,

6566 optLeavesReaderTerm(&readers[0]),

6567 optLeavesReaderTermBytes(&readers[0]),

6568 merged.pData, merged.nData);

6569 if( rc!=SQLITE_OK ) goto err;

6570 }

6571

6572 /* Step merged readers to next term and reorder. */

6573 while( i-- > 0 ){

6574 rc = optLeavesReaderStep(v, &readers[i]);

6575 if( rc!=SQLITE_OK ) goto err;

6576

6577 optLeavesReaderReorder(&readers[i], nReaders-i);

6578 }

6579 }

6580

6581 err:

6582 dataBufferDestroy(&doclist);

6583 dataBufferDestroy(&merged);

6584 return rc;

6585 }

6586

6587 /* Implement optimize() function for FTS3. optimize(t) merges all

6588 ** segments in the fts index into a single segment. 't' is the magic

6589 ** table-named column.

6590 */

6591 static void optimizeFunc(sqlite3_context *pContext,

6592 int argc, sqlite3_value **argv){

6593 fulltext_cursor *pCursor;

6594 if( argc>1 ){

6595 sqlite3_result_error(pContext, "excess arguments to optimize()",-1);

6596 }else if( sqlite3_value_type(argv[0])!=SQLITE_BLOB \|\|

6597 sqlite3_value_bytes(argv[0])!=sizeof(pCursor) ){

6598 sqlite3_result_error(pContext, "illegal first argument to optimize",-1);

6599 }else{

6600 fulltext_vtab *v;

6601 int i, rc, iMaxLevel;

6602 OptLeavesReader *readers;

6603 int nReaders;

6604 LeafWriter writer;

6605 sqlite3_stmt *s;

6606

6607 memcpy(&pCursor, sqlite3_value_blob(argv[0]), sizeof(pCursor));

6608 v = cursor_vtab(pCursor);

6609

6610 /* Flush any buffered updates before optimizing. */

6611 rc = flushPendingTerms(v);

6612 if( rc!=SQLITE_OK ) goto err;

6613

6614 rc = segdir_count(v, &nReaders, &iMaxLevel);

6615 if( rc!=SQLITE_OK ) goto err;

6616 if( nReaders==0 \|\| nReaders==1 ){

6617 sqlite3_result_text(pContext, "Index already optimal", -1,

6618 SQLITE_STATIC);

6619 return;

6620 }

6621

6622 rc = sql_get_statement(v, SEGDIR_SELECT_ALL_STMT, &s);

6623 if( rc!=SQLITE_OK ) goto err;

6624

6625 readers = sqlite3_malloc(nReaders*sizeof(readers[0]));

6626 if( readers==NULL ) goto err;

6627

6628 /* Note that there will already be a segment at this position

6629 ** until we call segdir_delete() on iMaxLevel.

6630 */

6631 leafWriterInit(iMaxLevel, 0, &writer);

6632

6633 i = 0;

6634 while( (rc = sqlite3_step(s))==SQLITE_ROW ){

6635 sqlite_int64 iStart = sqlite3_column_int64(s, 0);

6636 sqlite_int64 iEnd = sqlite3_column_int64(s, 1);

6637 const char *pRootData = sqlite3_column_blob(s, 2);

6638 int nRootData = sqlite3_column_bytes(s, 2);

6639

6640 /* Corrupt if we get back different types than we stored. */

6641 if( sqlite3_column_type(s, 0)!=SQLITE_INTEGER \|\|

6642 sqlite3_column_type(s, 1)!=SQLITE_INTEGER \|\|

6643 sqlite3_column_type(s, 2)!=SQLITE_BLOB ){

6644 rc = SQLITE_CORRUPT_BKPT;

6645 break;

6646 }

6647

6648 assert( i<nReaders );

6649 rc = leavesReaderInit(v, -1, iStart, iEnd, pRootData, nRootData,

6650 &readers[i].reader);

6651 if( rc!=SQLITE_OK ) break;

6652

6653 readers[i].segment = i;

6654 i++;

6655 }

6656

6657 /* If we managed to successfully read them all, optimize them. */

6658 if( rc==SQLITE_DONE ){

6659 assert( i==nReaders );

6660 rc = optimizeInternal(v, readers, nReaders, &writer);

6661 }else{

6662 sqlite3_reset(s); /* So we don't leave a lock. */

6663 }

6664

6665 while( i-- > 0 ){

6666 leavesReaderDestroy(&readers[i].reader);

6667 }

6668 sqlite3_free(readers);

6669

6670 /* If we've successfully gotten to here, delete the old segments

6671 ** and flush the interior structure of the new segment.

6672 */

6673 if( rc==SQLITE_OK ){

6674 for( i=0; i<=iMaxLevel; i++ ){

6675 rc = segdir_delete(v, i);

6676 if( rc!=SQLITE_OK ) break;

6677 }

6678

6679 if( rc==SQLITE_OK ) rc = leafWriterFinalize(v, &writer);

6680 }

6681

6682 leafWriterDestroy(&writer);

6683

6684 if( rc!=SQLITE_OK ) goto err;

6685

6686 sqlite3_result_text(pContext, "Index optimized", -1, SQLITE_STATIC);

6687 return;

6688

6689 /* TODO(shess): Error-handling needs to be improved along the

6690 ** lines of the dump_ functions.

6691 */

6692 err:

6693 {

6694 char buf[512];

6695 sqlite3_snprintf(sizeof(buf), buf, "Error in optimize: %s",

6696 sqlite3_errmsg(sqlite3_context_db_handle(pContext)));

6697 sqlite3_result_error(pContext, buf, -1);

6698 }

6699 }

6700 }

6701

6702 #ifdef SQLITE_TEST

6703 /* Generate an error of the form "<prefix>: <msg>". If msg is NULL,

6704 ** pull the error from the context's db handle.

6705 */

6706 static void generateError(sqlite3_context *pContext,

6707 const char prefix, const char msg){

6708 char buf[512];

6709 if( msg==NULL ) msg = sqlite3_errmsg(sqlite3_context_db_handle(pContext));

6710 sqlite3_snprintf(sizeof(buf), buf, "%s: %s", prefix, msg);

6711 sqlite3_result_error(pContext, buf, -1);

6712 }

6713

6714 /* Helper function to collect the set of terms in the segment into

6715 ** pTerms. The segment is defined by the leaf nodes between

6716 ** iStartBlockid and iEndBlockid, inclusive, or by the contents of

6717 ** pRootData if iStartBlockid is 0 (in which case the entire segment

6718 ** fit in a leaf).

6719 */

6720 static int collectSegmentTerms(fulltext_vtab v, sqlite3_stmt s,

6721 fts2Hash *pTerms){

6722 const sqlite_int64 iStartBlockid = sqlite3_column_int64(s, 0);

6723 const sqlite_int64 iEndBlockid = sqlite3_column_int64(s, 1);

6724 const char *pRootData = sqlite3_column_blob(s, 2);

6725 const int nRootData = sqlite3_column_bytes(s, 2);

6726 int rc;

6727 LeavesReader reader;

6728

6729 /* Corrupt if we get back different types than we stored. */

6730 if( sqlite3_column_type(s, 0)!=SQLITE_INTEGER \|\|

6731 sqlite3_column_type(s, 1)!=SQLITE_INTEGER \|\|

6732 sqlite3_column_type(s, 2)!=SQLITE_BLOB ){

6733 return SQLITE_CORRUPT_BKPT;

6734 }

6735

6736 rc = leavesReaderInit(v, 0, iStartBlockid, iEndBlockid,

6737 pRootData, nRootData, &reader);

6738 if( rc!=SQLITE_OK ) return rc;

6739

6740 while( rc==SQLITE_OK && !leavesReaderAtEnd(&reader) ){

6741 const char *pTerm = leavesReaderTerm(&reader);

6742 const int nTerm = leavesReaderTermBytes(&reader);

6743 void *oldValue = sqlite3Fts2HashFind(pTerms, pTerm, nTerm);

6744 void newValue = (void )((char *)oldValue+1);

6745

6746 /* From the comment before sqlite3Fts2HashInsert in fts2_hash.c,

6747 ** the data value passed is returned in case of malloc failure.

6748 */

6749 if( newValue==sqlite3Fts2HashInsert(pTerms, pTerm, nTerm, newValue) ){

6750 rc = SQLITE_NOMEM;

6751 }else{

6752 rc = leavesReaderStep(v, &reader);

6753 }

6754 }

6755

6756 leavesReaderDestroy(&reader);

6757 return rc;

6758 }

6759

6760 /* Helper function to build the result string for dump_terms(). */

6761 static int generateTermsResult(sqlite3_context pContext, fts2Hash pTerms){

6762 int iTerm, nTerms, nResultBytes, iByte;

6763 char *result;

6764 TermData *pData;

6765 fts2HashElem *e;

6766

6767 /* Iterate pTerms to generate an array of terms in pData for

6768 ** sorting.

6769 */

6770 nTerms = fts2HashCount(pTerms);

6771 assert( nTerms>0 );

6772 pData = sqlite3_malloc(nTerms*sizeof(TermData));

6773 if( pData==NULL ) return SQLITE_NOMEM;

6774

6775 nResultBytes = 0;

6776 for(iTerm = 0, e = fts2HashFirst(pTerms); e; iTerm++, e = fts2HashNext(e)){

6777 nResultBytes += fts2HashKeysize(e)+1; /* Term plus trailing space */

6778 assert( iTerm<nTerms );

6779 pData[iTerm].pTerm = fts2HashKey(e);

6780 pData[iTerm].nTerm = fts2HashKeysize(e);

6781 pData[iTerm].pCollector = fts2HashData(e); /* unused */

6782 }

6783 assert( iTerm==nTerms );

6784

6785 assert( nResultBytes>0 ); /* nTerms>0, nResultsBytes must be, too. */

6786 result = sqlite3_malloc(nResultBytes);

6787 if( result==NULL ){

6788 sqlite3_free(pData);

6789 return SQLITE_NOMEM;

6790 }

6791

6792 if( nTerms>1 ) qsort(pData, nTerms, sizeof(*pData), termDataCmp);

6793

6794 /* Read the terms in order to build the result. */

6795 iByte = 0;

6796 for(iTerm=0; iTerm<nTerms; ++iTerm){

6797 memcpy(result+iByte, pData[iTerm].pTerm, pData[iTerm].nTerm);

6798 iByte += pData[iTerm].nTerm;

6799 result[iByte++] = ' ';

6800 }

6801 assert( iByte==nResultBytes );

6802 assert( result[nResultBytes-1]==' ' );

6803 result[nResultBytes-1] = '\0';

6804

6805 /* Passes away ownership of result. */

6806 sqlite3_result_text(pContext, result, nResultBytes-1, sqlite3_free);

6807 sqlite3_free(pData);

6808 return SQLITE_OK;

6809 }

6810

6811 /* Implements dump_terms() for use in inspecting the fts2 index from

6812 ** tests. TEXT result containing the ordered list of terms joined by

6813 ** spaces. dump_terms(t, level, idx) dumps the terms for the segment

6814 ** specified by level, idx (in %_segdir), while dump_terms(t) dumps

6815 ** all terms in the index. In both cases t is the fts table's magic

6816 ** table-named column.

6817 */

6818 static void dumpTermsFunc(

6819 sqlite3_context *pContext,

6820 int argc, sqlite3_value **argv

6821 ){

6822 fulltext_cursor *pCursor;

6823 if( argc!=3 && argc!=1 ){

6824 generateError(pContext, "dump_terms", "incorrect arguments");

6825 }else if( sqlite3_value_type(argv[0])!=SQLITE_BLOB \|\|

6826 sqlite3_value_bytes(argv[0])!=sizeof(pCursor) ){

6827 generateError(pContext, "dump_terms", "illegal first argument");

6828 }else{

6829 fulltext_vtab *v;

6830 fts2Hash terms;

6831 sqlite3_stmt *s = NULL;

6832 int rc;

6833

6834 memcpy(&pCursor, sqlite3_value_blob(argv[0]), sizeof(pCursor));

6835 v = cursor_vtab(pCursor);

6836

6837 /* If passed only the cursor column, get all segments. Otherwise

6838 ** get the segment described by the following two arguments.

6839 */

6840 if( argc==1 ){

6841 rc = sql_get_statement(v, SEGDIR_SELECT_ALL_STMT, &s);

6842 }else{

6843 rc = sql_get_statement(v, SEGDIR_SELECT_SEGMENT_STMT, &s);

6844 if( rc==SQLITE_OK ){

6845 rc = sqlite3_bind_int(s, 1, sqlite3_value_int(argv[1]));

6846 if( rc==SQLITE_OK ){

6847 rc = sqlite3_bind_int(s, 2, sqlite3_value_int(argv[2]));

6848 }

6849 }

6850 }

6851

6852 if( rc!=SQLITE_OK ){

6853 generateError(pContext, "dump_terms", NULL);

6854 return;

6855 }

6856

6857 /* Collect the terms for each segment. */

6858 sqlite3Fts2HashInit(&terms, FTS2_HASH_STRING, 1);

6859 while( (rc = sqlite3_step(s))==SQLITE_ROW ){

6860 rc = collectSegmentTerms(v, s, &terms);

6861 if( rc!=SQLITE_OK ) break;

6862 }

6863

6864 if( rc!=SQLITE_DONE ){

6865 sqlite3_reset(s);

6866 generateError(pContext, "dump_terms", NULL);

6867 }else{

6868 const int nTerms = fts2HashCount(&terms);

6869 if( nTerms>0 ){

6870 rc = generateTermsResult(pContext, &terms);

6871 if( rc==SQLITE_NOMEM ){

6872 generateError(pContext, "dump_terms", "out of memory");

6873 }else{

6874 assert( rc==SQLITE_OK );

6875 }

6876 }else if( argc==3 ){

6877 /* The specific segment asked for could not be found. */

6878 generateError(pContext, "dump_terms", "segment not found");

6879 }else{

6880 /* No segments found. */

6881 /* TODO(shess): It should be impossible to reach this. This

6882 ** case can only happen for an empty table, in which case

6883 ** SQLite has no rows to call this function on.

6884 */

6885 sqlite3_result_null(pContext);

6886 }

6887 }

6888 sqlite3Fts2HashClear(&terms);

6889 }

6890 }

6891

6892 /* Expand the DL_DEFAULT doclist in pData into a text result in

6893 ** pContext.

6894 */

6895 static void createDoclistResult(sqlite3_context *pContext,

6896 const char *pData, int nData){

6897 DataBuffer dump;

6898 DLReader dlReader;

6899 int rc;

6900

6901 assert( pData!=NULL && nData>0 );

6902

6903 rc = dlrInit(&dlReader, DL_DEFAULT, pData, nData);

6904 if( rc!=SQLITE_OK ) return rc;

6905 dataBufferInit(&dump, 0);

6906 for( ; rc==SQLITE_OK && !dlrAtEnd(&dlReader); rc = dlrStep(&dlReader) ){

6907 char buf[256];

6908 PLReader plReader;

6909

6910 rc = plrInit(&plReader, &dlReader);

6911 if( rc!=SQLITE_OK ) break;

6912 if( DL_DEFAULT==DL_DOCIDS \|\| plrAtEnd(&plReader) ){

6913 sqlite3_snprintf(sizeof(buf), buf, "[%lld] ", dlrDocid(&dlReader));

6914 dataBufferAppend(&dump, buf, strlen(buf));

6915 }else{

6916 int iColumn = plrColumn(&plReader);

6917

6918 sqlite3_snprintf(sizeof(buf), buf, "[%lld %d[",

6919 dlrDocid(&dlReader), iColumn);

6920 dataBufferAppend(&dump, buf, strlen(buf));

6921

6922 for( ; !plrAtEnd(&plReader); rc = plrStep(&plReader) ){

6923 if( rc!=SQLITE_OK ) break;

6924 if( plrColumn(&plReader)!=iColumn ){

6925 iColumn = plrColumn(&plReader);

6926 sqlite3_snprintf(sizeof(buf), buf, "] %d[", iColumn);

6927 assert( dump.nData>0 );

6928 dump.nData--; /* Overwrite trailing space. */

6929 assert( dump.pData[dump.nData]==' ');

6930 dataBufferAppend(&dump, buf, strlen(buf));

6931 }

6932 if( DL_DEFAULT==DL_POSITIONS_OFFSETS ){

6933 sqlite3_snprintf(sizeof(buf), buf, "%d,%d,%d ",

6934 plrPosition(&plReader),

6935 plrStartOffset(&plReader), plrEndOffset(&plReader));

6936 }else if( DL_DEFAULT==DL_POSITIONS ){

6937 sqlite3_snprintf(sizeof(buf), buf, "%d ", plrPosition(&plReader));

6938 }else{

6939 assert( NULL=="Unhandled DL_DEFAULT value");

6940 }

6941 dataBufferAppend(&dump, buf, strlen(buf));

6942 }

6943 plrDestroy(&plReader);

6944 if( rc!= SQLITE_OK ) break;

6945

6946 assert( dump.nData>0 );

6947 dump.nData--; /* Overwrite trailing space. */

6948 assert( dump.pData[dump.nData]==' ');

6949 dataBufferAppend(&dump, "]] ", 3);

6950 }

6951 }

6952 dlrDestroy(&dlReader);

6953 if( rc!=SQLITE_OK ){

6954 dataBufferDestroy(&dump);

6955 return rc;

6956 }

6957

6958 assert( dump.nData>0 );

6959 dump.nData--; /* Overwrite trailing space. */

6960 assert( dump.pData[dump.nData]==' ');

6961 dump.pData[dump.nData] = '\0';

6962 assert( dump.nData>0 );

6963

6964 /* Passes ownership of dump's buffer to pContext. */

6965 sqlite3_result_text(pContext, dump.pData, dump.nData, sqlite3_free);

6966 dump.pData = NULL;

6967 dump.nData = dump.nCapacity = 0;

6968 return SQLITE_OK;

6969 }

6970

6971 /* Implements dump_doclist() for use in inspecting the fts2 index from

6972 ** tests. TEXT result containing a string representation of the

6973 ** doclist for the indicated term. dump_doclist(t, term, level, idx)

6974 ** dumps the doclist for term from the segment specified by level, idx

6975 ** (in %_segdir), while dump_doclist(t, term) dumps the logical

6976 ** doclist for the term across all segments. The per-segment doclist

6977 ** can contain deletions, while the full-index doclist will not

6978 ** (deletions are omitted).

6979 **

6980 ** Result formats differ with the setting of DL_DEFAULTS. Examples:

6981 **

6982 ** DL_DOCIDS: [1] [3] [7]

6983 ** DL_POSITIONS: [1 0[0 4] 1[17]] [3 1[5]]

6984 ** DL_POSITIONS_OFFSETS: [1 0[0,0,3 4,23,26] 1[17,102,105]] [3 1[5,20,23]]

6985 **

6986 ** In each case the number after the outer '[' is the docid. In the

6987 ** latter two cases, the number before the inner '[' is the column

6988 ** associated with the values within. For DL_POSITIONS the numbers

6989 ** within are the positions, for DL_POSITIONS_OFFSETS they are the

6990 ** position, the start offset, and the end offset.

6991 */

6992 static void dumpDoclistFunc(

6993 sqlite3_context *pContext,

6994 int argc, sqlite3_value **argv

6995 ){

6996 fulltext_cursor *pCursor;

6997 if( argc!=2 && argc!=4 ){

6998 generateError(pContext, "dump_doclist", "incorrect arguments");

6999 }else if( sqlite3_value_type(argv[0])!=SQLITE_BLOB \|\|

7000 sqlite3_value_bytes(argv[0])!=sizeof(pCursor) ){

7001 generateError(pContext, "dump_doclist", "illegal first argument");

7002 }else if( sqlite3_value_text(argv[1])==NULL \|\|

7003 sqlite3_value_text(argv[1])[0]=='\0' ){

7004 generateError(pContext, "dump_doclist", "empty second argument");

7005 }else{

7006 const char pTerm = (const char )sqlite3_value_text(argv[1]);

7007 const int nTerm = strlen(pTerm);

7008 fulltext_vtab *v;

7009 int rc;

7010 DataBuffer doclist;

7011

7012 memcpy(&pCursor, sqlite3_value_blob(argv[0]), sizeof(pCursor));

7013 v = cursor_vtab(pCursor);

7014

7015 dataBufferInit(&doclist, 0);

7016

7017 /* termSelect() yields the same logical doclist that queries are

7018 ** run against.

7019 */

7020 if( argc==2 ){

7021 rc = termSelect(v, v->nColumn, pTerm, nTerm, 0, DL_DEFAULT, &doclist);

7022 }else{

7023 sqlite3_stmt *s = NULL;

7024

7025 /* Get our specific segment's information. */

7026 rc = sql_get_statement(v, SEGDIR_SELECT_SEGMENT_STMT, &s);

7027 if( rc==SQLITE_OK ){

7028 rc = sqlite3_bind_int(s, 1, sqlite3_value_int(argv[2]));

7029 if( rc==SQLITE_OK ){

7030 rc = sqlite3_bind_int(s, 2, sqlite3_value_int(argv[3]));

7031 }

7032 }

7033

7034 if( rc==SQLITE_OK ){

7035 rc = sqlite3_step(s);

7036

7037 if( rc==SQLITE_DONE ){

7038 dataBufferDestroy(&doclist);

7039 generateError(pContext, "dump_doclist", "segment not found");

7040 return;

7041 }

7042

7043 /* Found a segment, load it into doclist. */

7044 if( rc==SQLITE_ROW ){

7045 const sqlite_int64 iLeavesEnd = sqlite3_column_int64(s, 1);

7046 const char *pData = sqlite3_column_blob(s, 2);

7047 const int nData = sqlite3_column_bytes(s, 2);

7048

7049 /* loadSegment() is used by termSelect() to load each

7050 ** segment's data.

7051 */

7052 rc = loadSegment(v, pData, nData, iLeavesEnd, pTerm, nTerm, 0,

7053 &doclist);

7054 if( rc==SQLITE_OK ){

7055 rc = sqlite3_step(s);

7056

7057 /* Should not have more than one matching segment. */

7058 if( rc!=SQLITE_DONE ){

7059 sqlite3_reset(s);

7060 dataBufferDestroy(&doclist);

7061 generateError(pContext, "dump_doclist", "invalid segdir");

7062 return;

7063 }

7064 rc = SQLITE_OK;

7065 }

7066 }

7067 }

7068

7069 sqlite3_reset(s);

7070 }

7071

7072 if( rc==SQLITE_OK ){

7073 if( doclist.nData>0 ){

7074 createDoclistResult(pContext, doclist.pData, doclist.nData);

7075 }else{

7076 /* TODO(shess): This can happen if the term is not present, or

7077 ** if all instances of the term have been deleted and this is

7078 ** an all-index dump. It may be interesting to distinguish

7079 ** these cases.

7080 */

7081 sqlite3_result_text(pContext, "", 0, SQLITE_STATIC);

7082 }

7083 }else if( rc==SQLITE_NOMEM ){

7084 /* Handle out-of-memory cases specially because if they are

7085 ** generated in fts2 code they may not be reflected in the db

7086 ** handle.

7087 */

7088 /* TODO(shess): Handle this more comprehensively.

7089 ** sqlite3ErrStr() has what I need, but is internal.

7090 */

7091 generateError(pContext, "dump_doclist", "out of memory");

7092 }else{

7093 generateError(pContext, "dump_doclist", NULL);

7094 }

7095

7096 dataBufferDestroy(&doclist);

7097 }

7098 }

7099 #endif

7100

7101 /*

7102 ** This routine implements the xFindFunction method for the FTS2

7103 ** virtual table.

7104 */

7105 static int fulltextFindFunction(

7106 sqlite3_vtab *pVtab,

7107 int nArg,

7108 const char *zName,

7109 void (*pxFunc)(sqlite3_context,int,sqlite3_value**),

7110 void **ppArg

7111 ){

7112 if( strcmp(zName,"snippet")==0 ){

7113 *pxFunc = snippetFunc;

7114 return 1;

7115 }else if( strcmp(zName,"offsets")==0 ){

7116 *pxFunc = snippetOffsetsFunc;

7117 return 1;

7118 }else if( strcmp(zName,"optimize")==0 ){

7119 *pxFunc = optimizeFunc;

7120 return 1;

7121 #ifdef SQLITE_TEST

7122 /* NOTE(shess): These functions are present only for testing

7123 ** purposes. No particular effort is made to optimize their

7124 ** execution or how they build their results.

7125 */

7126 }else if( strcmp(zName,"dump_terms")==0 ){

7127 /* fprintf(stderr, "Found dump_terms\n"); */

7128 *pxFunc = dumpTermsFunc;

7129 return 1;

7130 }else if( strcmp(zName,"dump_doclist")==0 ){

7131 /* fprintf(stderr, "Found dump_doclist\n"); */

7132 *pxFunc = dumpDoclistFunc;

7133 return 1;

7134 #endif

7135 }

7136 return 0;

7137 }

7138

7139 /*

7140 ** Rename an fts2 table.

7141 */

7142 static int fulltextRename(

7143 sqlite3_vtab *pVtab,

7144 const char *zName

7145 ){

7146 fulltext_vtab p = (fulltext_vtab )pVtab;

7147 int rc = SQLITE_NOMEM;

7148 char *zSql = sqlite3_mprintf(

7149 "ALTER TABLE %Q.'%q_content' RENAME TO '%q_content';"

7150 "ALTER TABLE %Q.'%q_segments' RENAME TO '%q_segments';"

7151 "ALTER TABLE %Q.'%q_segdir' RENAME TO '%q_segdir';"

7152 , p->zDb, p->zName, zName

7153 , p->zDb, p->zName, zName

7154 , p->zDb, p->zName, zName

7155 );

7156 if( zSql ){

7157 rc = sqlite3_exec(p->db, zSql, 0, 0, 0);

7158 sqlite3_free(zSql);

7159 }

7160 return rc;

7161 }

7162

7163 static const sqlite3_module fts2Module = {

7164 /* iVersion */ 0,

7165 /* xCreate */ fulltextCreate,

7166 /* xConnect */ fulltextConnect,

7167 /* xBestIndex */ fulltextBestIndex,

7168 /* xDisconnect */ fulltextDisconnect,

7169 /* xDestroy */ fulltextDestroy,

7170 /* xOpen */ fulltextOpen,

7171 /* xClose */ fulltextClose,

7172 /* xFilter */ fulltextFilter,

7173 /* xNext */ fulltextNext,

7174 /* xEof */ fulltextEof,

7175 /* xColumn */ fulltextColumn,

7176 /* xRowid */ fulltextRowid,

7177 /* xUpdate */ fulltextUpdate,

7178 /* xBegin */ fulltextBegin,

7179 /* xSync */ fulltextSync,

7180 /* xCommit */ fulltextCommit,

7181 /* xRollback */ fulltextRollback,

7182 /* xFindFunction */ fulltextFindFunction,

7183 /* xRename */ fulltextRename,

7184 };

7185

7186 static void hashDestroy(void *p){

7187 fts2Hash pHash = (fts2Hash )p;

7188 sqlite3Fts2HashClear(pHash);

7189 sqlite3_free(pHash);

7190 }

7191

7192 /*

7193 ** The fts2 built-in tokenizers - "simple" and "porter" - are implemented

7194 ** in files fts2_tokenizer1.c and fts2_porter.c respectively. The following

7195 ** two forward declarations are for functions declared in these files

7196 ** used to retrieve the respective implementations.

7197 **

7198 ** Calling sqlite3Fts2SimpleTokenizerModule() sets the value pointed

7199 ** to by the argument to point a the "simple" tokenizer implementation.

7200 ** Function ...PorterTokenizerModule() sets *pModule to point to the

7201 ** porter tokenizer/stemmer implementation.

7202 */

7203 void sqlite3Fts2SimpleTokenizerModule(sqlite3_tokenizer_module const**ppModule);

7204 void sqlite3Fts2PorterTokenizerModule(sqlite3_tokenizer_module const**ppModule);

7205 void sqlite3Fts2IcuTokenizerModule(sqlite3_tokenizer_module const**ppModule);

7206

7207 int sqlite3Fts2InitHashTable(sqlite3 , fts2Hash , const char *);

7208

7209 /*

7210 ** Initialise the fts2 extension. If this extension is built as part

7211 ** of the sqlite library, then this function is called directly by

7212 ** SQLite. If fts2 is built as a dynamically loadable extension, this

7213 ** function is called by the sqlite3_extension_init() entry point.

7214 */

7215 int sqlite3Fts2Init(sqlite3 *db){

7216 int rc = SQLITE_OK;

7217 fts2Hash *pHash = 0;

7218 const sqlite3_tokenizer_module *pSimple = 0;

7219 const sqlite3_tokenizer_module *pPorter = 0;

7220 const sqlite3_tokenizer_module *pIcu = 0;

7221

7222 sqlite3Fts2SimpleTokenizerModule(&pSimple);

7223 sqlite3Fts2PorterTokenizerModule(&pPorter);

7224 #ifdef SQLITE_ENABLE_ICU

7225 sqlite3Fts2IcuTokenizerModule(&pIcu);

7226 #endif

7227

7228 /* Allocate and initialise the hash-table used to store tokenizers. */

7229 pHash = sqlite3_malloc(sizeof(fts2Hash));

7230 if( !pHash ){

7231 rc = SQLITE_NOMEM;

7232 }else{

7233 sqlite3Fts2HashInit(pHash, FTS2_HASH_STRING, 1);

7234 }

7235

7236 /* Load the built-in tokenizers into the hash table */

7237 if( rc==SQLITE_OK ){

7238 if( sqlite3Fts2HashInsert(pHash, "simple", 7, (void *)pSimple)

7239 \|\| sqlite3Fts2HashInsert(pHash, "porter", 7, (void *)pPorter)

7240 \|\| (pIcu && sqlite3Fts2HashInsert(pHash, "icu", 4, (void *)pIcu))

7241 ){

7242 rc = SQLITE_NOMEM;

7243 }

7244 }

7245

7246 /* Create the virtual table wrapper around the hash-table and overload

7247 ** the two scalar functions. If this is successful, register the

7248 ** module with sqlite.

7249 */

7250 if( SQLITE_OK==rc

7251 #if GEARS_FTS2_CHANGES && !SQLITE_TEST

7252 /* fts2_tokenizer() disabled for security reasons. */

7253 #else

7254 && SQLITE_OK==(rc = sqlite3Fts2InitHashTable(db, pHash, "fts2_tokenizer"))

7255 #endif

7256 && SQLITE_OK==(rc = sqlite3_overload_function(db, "snippet", -1))

7257 && SQLITE_OK==(rc = sqlite3_overload_function(db, "offsets", -1))

7258 && SQLITE_OK==(rc = sqlite3_overload_function(db, "optimize", -1))

7259 #ifdef SQLITE_TEST

7260 && SQLITE_OK==(rc = sqlite3_overload_function(db, "dump_terms", -1))

7261 && SQLITE_OK==(rc = sqlite3_overload_function(db, "dump_doclist", -1))

7262 #endif

7263 ){

7264 return sqlite3_create_module_v2(

7265 db, "fts2", &fts2Module, (void *)pHash, hashDestroy

7266 );

7267 }

7268

7269 /* An error has occurred. Delete the hash table and return the error code. */

7270 assert( rc!=SQLITE_OK );

7271 if( pHash ){

7272 sqlite3Fts2HashClear(pHash);

7273 sqlite3_free(pHash);

7274 }

7275 return rc;

7276 }

7277

7278 #if !SQLITE_CORE

7279 int sqlite3_extension_init(

7280 sqlite3 *db,

7281 char **pzErrMsg,

7282 const sqlite3_api_routines *pApi

7283 ){

7284 SQLITE_EXTENSION_INIT2(pApi)

7285 return sqlite3Fts2Init(db);

7286 }

7287 #endif

7288

7289 #endif /* !defined(SQLITE_CORE) \|\| defined(SQLITE_ENABLE_FTS2) */

OLD	NEW

« no previous file with comments | « third_party/sqlite/ext/fts2/fts2.h ('k') | third_party/sqlite/ext/fts2/fts2_hash.h » ('j') | no next file with comments »