third_party/sqlite/sqlite-src-3100200/ext/fts3/fts3.c - Issue 2846743003: [sql] Remove SQLite 3.10.2 reference directory.

Side by Side Diff: third_party/sqlite/sqlite-src-3100200/ext/fts3/fts3.c

Issue 2846743003: [sql] Remove SQLite 3.10.2 reference directory. (Closed)

Patch Set: Created 3 years, 7 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:

OLD	NEW
	(Empty)
1 /*

2 ** 2006 Oct 10

3 **

4 ** The author disclaims copyright to this source code. In place of

5 ** a legal notice, here is a blessing:

6 **

7 ** May you do good and not evil.

8 ** May you find forgiveness for yourself and forgive others.

9 ** May you share freely, never taking more than you give.

10 **

11 ******************************************************************************

12 **

13 ** This is an SQLite module implementing full-text search.

14 */

15

16 /*

17 ** The code in this file is only compiled if:

18 **

19 ** * The FTS3 module is being built as an extension

20 ** (in which case SQLITE_CORE is not defined), or

21 **

22 ** * The FTS3 module is being built into the core of

23 ** SQLite (in which case SQLITE_ENABLE_FTS3 is defined).

24 */

25

26 /* The full-text index is stored in a series of b+tree (-like)

27 ** structures called segments which map terms to doclists. The

28 ** structures are like b+trees in layout, but are constructed from the

29 ** bottom up in optimal fashion and are not updatable. Since trees

30 ** are built from the bottom up, things will be described from the

31 ** bottom up.

32 **

33 **

34 ** Varints **

35 ** The basic unit of encoding is a variable-length integer called a

36 ** varint. We encode variable-length integers in little-endian order

37 ** using seven bits * per byte as follows:

38 **

39 ** KEY:

40 ** A = 0xxxxxxx 7 bits of data and one flag bit

41 ** B = 1xxxxxxx 7 bits of data and one flag bit

42 **

43 ** 7 bits - A

44 ** 14 bits - BA

45 ** 21 bits - BBA

46 ** and so on.

47 **

48 ** This is similar in concept to how sqlite encodes "varints" but

49 ** the encoding is not the same. SQLite varints are big-endian

50 ** are are limited to 9 bytes in length whereas FTS3 varints are

51 ** little-endian and can be up to 10 bytes in length (in theory).

52 **

53 ** Example encodings:

54 **

55 ** 1: 0x01

56 ** 127: 0x7f

57 ** 128: 0x81 0x00

58 **

59 **

60 ** Document lists **

61 ** A doclist (document list) holds a docid-sorted list of hits for a

62 ** given term. Doclists hold docids and associated token positions.

63 ** A docid is the unique integer identifier for a single document.

64 ** A position is the index of a word within the document. The first

65 ** word of the document has a position of 0.

66 **

67 ** FTS3 used to optionally store character offsets using a compile-time

68 ** option. But that functionality is no longer supported.

69 **

70 ** A doclist is stored like this:

71 **

72 ** array {

73 ** varint docid; (delta from previous doclist)

74 ** array { (position list for column 0)

75 ** varint position; (2 more than the delta from previous position)

76 ** }

77 ** array {

78 ** varint POS_COLUMN; (marks start of position list for new column)

79 ** varint column; (index of new column)

80 ** array {

81 ** varint position; (2 more than the delta from previous position)

82 ** }

83 ** }

84 ** varint POS_END; (marks end of positions for this document.

85 ** }

86 **

87 ** Here, array { X } means zero or more occurrences of X, adjacent in

88 ** memory. A "position" is an index of a token in the token stream

89 ** generated by the tokenizer. Note that POS_END and POS_COLUMN occur

90 ** in the same logical place as the position element, and act as sentinals

91 ** ending a position list array. POS_END is 0. POS_COLUMN is 1.

92 ** The positions numbers are not stored literally but rather as two more

93 ** than the difference from the prior position, or the just the position plus

94 ** 2 for the first position. Example:

95 **

96 ** label: A B C D E F G H I J K

97 ** value: 123 5 9 1 1 14 35 0 234 72 0

98 **

99 ** The 123 value is the first docid. For column zero in this document

100 ** there are two matches at positions 3 and 10 (5-2 and 9-2+3). The 1

101 ** at D signals the start of a new column; the 1 at E indicates that the

102 ** new column is column number 1. There are two positions at 12 and 45

103 ** (14-2 and 35-2+12). The 0 at H indicate the end-of-document. The

104 ** 234 at I is the delta to next docid (357). It has one position 70

105 ** (72-2) and then terminates with the 0 at K.

106 **

107 ** A "position-list" is the list of positions for multiple columns for

108 ** a single docid. A "column-list" is the set of positions for a single

109 ** column. Hence, a position-list consists of one or more column-lists,

110 ** a document record consists of a docid followed by a position-list and

111 ** a doclist consists of one or more document records.

112 **

113 ** A bare doclist omits the position information, becoming an

114 ** array of varint-encoded docids.

115 **

116 ** Segment leaf nodes **

117 ** Segment leaf nodes store terms and doclists, ordered by term. Leaf

118 ** nodes are written using LeafWriter, and read using LeafReader (to

119 ** iterate through a single leaf node's data) and LeavesReader (to

120 ** iterate through a segment's entire leaf layer). Leaf nodes have

121 ** the format:

122 **

123 ** varint iHeight; (height from leaf level, always 0)

124 ** varint nTerm; (length of first term)

125 ** char pTerm[nTerm]; (content of first term)

126 ** varint nDoclist; (length of term's associated doclist)

127 ** char pDoclist[nDoclist]; (content of doclist)

128 ** array {

129 ** (further terms are delta-encoded)

130 ** varint nPrefix; (length of prefix shared with previous term)

131 ** varint nSuffix; (length of unshared suffix)

132 ** char pTermSuffix[nSuffix];(unshared suffix of next term)

133 ** varint nDoclist; (length of term's associated doclist)

134 ** char pDoclist[nDoclist]; (content of doclist)

135 ** }

136 **

137 ** Here, array { X } means zero or more occurrences of X, adjacent in

138 ** memory.

139 **

140 ** Leaf nodes are broken into blocks which are stored contiguously in

141 ** the %_segments table in sorted order. This means that when the end

142 ** of a node is reached, the next term is in the node with the next

143 ** greater node id.

144 **

145 ** New data is spilled to a new leaf node when the current node

146 ** exceeds LEAF_MAX bytes (default 2048). New data which itself is

147 ** larger than STANDALONE_MIN (default 1024) is placed in a standalone

148 ** node (a leaf node with a single term and doclist). The goal of

149 ** these settings is to pack together groups of small doclists while

150 ** making it efficient to directly access large doclists. The

151 ** assumption is that large doclists represent terms which are more

152 ** likely to be query targets.

153 **

154 ** TODO(shess) It may be useful for blocking decisions to be more

155 ** dynamic. For instance, it may make more sense to have a 2.5k leaf

156 ** node rather than splitting into 2k and .5k nodes. My intuition is

157 ** that this might extend through 2x or 4x the pagesize.

158 **

159 **

160 ** Segment interior nodes **

161 ** Segment interior nodes store blockids for subtree nodes and terms

162 ** to describe what data is stored by the each subtree. Interior

163 ** nodes are written using InteriorWriter, and read using

164 ** InteriorReader. InteriorWriters are created as needed when

165 ** SegmentWriter creates new leaf nodes, or when an interior node

166 ** itself grows too big and must be split. The format of interior

167 ** nodes:

168 **

169 ** varint iHeight; (height from leaf level, always >0)

170 ** varint iBlockid; (block id of node's leftmost subtree)

171 ** optional {

172 ** varint nTerm; (length of first term)

173 ** char pTerm[nTerm]; (content of first term)

174 ** array {

175 ** (further terms are delta-encoded)

176 ** varint nPrefix; (length of shared prefix with previous term)

177 ** varint nSuffix; (length of unshared suffix)

178 ** char pTermSuffix[nSuffix]; (unshared suffix of next term)

179 ** }

180 ** }

181 **

182 ** Here, optional { X } means an optional element, while array { X }

183 ** means zero or more occurrences of X, adjacent in memory.

184 **

185 ** An interior node encodes n terms separating n+1 subtrees. The

186 ** subtree blocks are contiguous, so only the first subtree's blockid

187 ** is encoded. The subtree at iBlockid will contain all terms less

188 ** than the first term encoded (or all terms if no term is encoded).

189 ** Otherwise, for terms greater than or equal to pTerm[i] but less

190 ** than pTerm[i+1], the subtree for that term will be rooted at

191 ** iBlockid+i. Interior nodes only store enough term data to

192 ** distinguish adjacent children (if the rightmost term of the left

193 ** child is "something", and the leftmost term of the right child is

194 ** "wicked", only "w" is stored).

195 **

196 ** New data is spilled to a new interior node at the same height when

197 ** the current node exceeds INTERIOR_MAX bytes (default 2048).

198 ** INTERIOR_MIN_TERMS (default 7) keeps large terms from monopolizing

199 ** interior nodes and making the tree too skinny. The interior nodes

200 ** at a given height are naturally tracked by interior nodes at

201 ** height+1, and so on.

202 **

203 **

204 ** Segment directory **

205 ** The segment directory in table %_segdir stores meta-information for

206 ** merging and deleting segments, and also the root node of the

207 ** segment's tree.

208 **

209 ** The root node is the top node of the segment's tree after encoding

210 ** the entire segment, restricted to ROOT_MAX bytes (default 1024).

211 ** This could be either a leaf node or an interior node. If the top

212 ** node requires more than ROOT_MAX bytes, it is flushed to %_segments

213 ** and a new root interior node is generated (which should always fit

214 ** within ROOT_MAX because it only needs space for 2 varints, the

215 ** height and the blockid of the previous root).

216 **

217 ** The meta-information in the segment directory is:

218 ** level - segment level (see below)

219 ** idx - index within level

220 ** - (level,idx uniquely identify a segment)

221 ** start_block - first leaf node

222 ** leaves_end_block - last leaf node

223 ** end_block - last block (including interior nodes)

224 ** root - contents of root node

225 **

226 ** If the root node is a leaf node, then start_block,

227 ** leaves_end_block, and end_block are all 0.

228 **

229 **

230 ** Segment merging **

231 ** To amortize update costs, segments are grouped into levels and

232 ** merged in batches. Each increase in level represents exponentially

233 ** more documents.

234 **

235 ** New documents (actually, document updates) are tokenized and

236 ** written individually (using LeafWriter) to a level 0 segment, with

237 ** incrementing idx. When idx reaches MERGE_COUNT (default 16), all

238 ** level 0 segments are merged into a single level 1 segment. Level 1

239 ** is populated like level 0, and eventually MERGE_COUNT level 1

240 ** segments are merged to a single level 2 segment (representing

241 ** MERGE_COUNT^2 updates), and so on.

242 **

243 ** A segment merge traverses all segments at a given level in

244 ** parallel, performing a straightforward sorted merge. Since segment

245 ** leaf nodes are written in to the %_segments table in order, this

246 ** merge traverses the underlying sqlite disk structures efficiently.

247 ** After the merge, all segment blocks from the merged level are

248 ** deleted.

249 **

250 ** MERGE_COUNT controls how often we merge segments. 16 seems to be

251 ** somewhat of a sweet spot for insertion performance. 32 and 64 show

252 ** very similar performance numbers to 16 on insertion, though they're

253 ** a tiny bit slower (perhaps due to more overhead in merge-time

254 ** sorting). 8 is about 20% slower than 16, 4 about 50% slower than

255 ** 16, 2 about 66% slower than 16.

256 **

257 ** At query time, high MERGE_COUNT increases the number of segments

258 ** which need to be scanned and merged. For instance, with 100k docs

259 ** inserted:

260 **

261 ** MERGE_COUNT segments

262 ** 16 25

263 ** 8 12

264 ** 4 10

265 ** 2 6

266 **

267 ** This appears to have only a moderate impact on queries for very

268 ** frequent terms (which are somewhat dominated by segment merge

269 ** costs), and infrequent and non-existent terms still seem to be fast

270 ** even with many segments.

271 **

272 ** TODO(shess) That said, it would be nice to have a better query-side

273 ** argument for MERGE_COUNT of 16. Also, it is possible/likely that

274 ** optimizations to things like doclist merging will swing the sweet

275 ** spot around.

276 **

277 **

278 **

279 ** Handling of deletions and updates **

280 ** Since we're using a segmented structure, with no docid-oriented

281 ** index into the term index, we clearly cannot simply update the term

282 ** index when a document is deleted or updated. For deletions, we

283 ** write an empty doclist (varint(docid) varint(POS_END)), for updates

284 ** we simply write the new doclist. Segment merges overwrite older

285 ** data for a particular docid with newer data, so deletes or updates

286 ** will eventually overtake the earlier data and knock it out. The

287 ** query logic likewise merges doclists so that newer data knocks out

288 ** older data.

289 */

290

291 #include "fts3Int.h"

292 #if !defined(SQLITE_CORE) \|\| defined(SQLITE_ENABLE_FTS3)

293

294 #if defined(SQLITE_ENABLE_FTS3) && !defined(SQLITE_CORE)

295 # define SQLITE_CORE 1

296 #endif

297

298 #include <assert.h>

299 #include <stdlib.h>

300 #include <stddef.h>

301 #include <stdio.h>

302 #include <string.h>

303 #include <stdarg.h>

304

305 #include "fts3.h"

306 #ifndef SQLITE_CORE

307 # include "sqlite3ext.h"

308 SQLITE_EXTENSION_INIT1

309 #endif

310

311 static int fts3EvalNext(Fts3Cursor *pCsr);

312 static int fts3EvalStart(Fts3Cursor *pCsr);

313 static int fts3TermSegReaderCursor(

314 Fts3Cursor , const char , int, int, Fts3MultiSegReader **);

315

316 #ifndef SQLITE_AMALGAMATION

317 # if defined(SQLITE_DEBUG)

318 int sqlite3Fts3Always(int b) { assert( b ); return b; }

319 int sqlite3Fts3Never(int b) { assert( !b ); return b; }

320 # endif

321 #endif

322

323 /*

324 ** Write a 64-bit variable-length integer to memory starting at p[0].

325 ** The length of data written will be between 1 and FTS3_VARINT_MAX bytes.

326 ** The number of bytes written is returned.

327 */

328 int sqlite3Fts3PutVarint(char *p, sqlite_int64 v){

329 unsigned char q = (unsigned char ) p;

330 sqlite_uint64 vu = v;

331 do{

332 *q++ = (unsigned char) ((vu & 0x7f) \| 0x80);

333 vu >>= 7;

334 }while( vu!=0 );

335 q[-1] &= 0x7f; /* turn off high bit in final byte */

336 assert( q - (unsigned char *)p <= FTS3_VARINT_MAX );

337 return (int) (q - (unsigned char *)p);

338 }

339

340 #define GETVARINT_STEP(v, ptr, shift, mask1, mask2, var, ret) \

341 v = (v & mask1) \| ( (*ptr++) << shift ); \

342 if( (v & mask2)==0 ){ var = v; return ret; }

343 #define GETVARINT_INIT(v, ptr, shift, mask1, mask2, var, ret) \

344 v = (*ptr++); \

345 if( (v & mask2)==0 ){ var = v; return ret; }

346

347 /*

348 ** Read a 64-bit variable-length integer from memory starting at p[0].

349 ** Return the number of bytes read, or 0 on error.

350 ** The value is stored in *v.

351 */

352 int sqlite3Fts3GetVarint(const char p, sqlite_int64 v){

353 const char *pStart = p;

354 u32 a;

355 u64 b;

356 int shift;

357

358 GETVARINT_INIT(a, p, 0, 0x00, 0x80, *v, 1);

359 GETVARINT_STEP(a, p, 7, 0x7F, 0x4000, *v, 2);

360 GETVARINT_STEP(a, p, 14, 0x3FFF, 0x200000, *v, 3);

361 GETVARINT_STEP(a, p, 21, 0x1FFFFF, 0x10000000, *v, 4);

362 b = (a & 0x0FFFFFFF );

363

364 for(shift=28; shift<=63; shift+=7){

365 u64 c = *p++;

366 b += (c&0x7F) << shift;

367 if( (c & 0x80)==0 ) break;

368 }

369 *v = b;

370 return (int)(p - pStart);

371 }

372

373 /*

374 ** Similar to sqlite3Fts3GetVarint(), except that the output is truncated to a

375 ** 32-bit integer before it is returned.

376 */

377 int sqlite3Fts3GetVarint32(const char p, int pi){

378 u32 a;

379

380 #ifndef fts3GetVarint32

381 GETVARINT_INIT(a, p, 0, 0x00, 0x80, *pi, 1);

382 #else

383 a = (*p++);

384 assert( a & 0x80 );

385 #endif

386

387 GETVARINT_STEP(a, p, 7, 0x7F, 0x4000, *pi, 2);

388 GETVARINT_STEP(a, p, 14, 0x3FFF, 0x200000, *pi, 3);

389 GETVARINT_STEP(a, p, 21, 0x1FFFFF, 0x10000000, *pi, 4);

390 a = (a & 0x0FFFFFFF );

391 pi = (int)(a \| ((u32)(p & 0x0F) << 28));

392 return 5;

393 }

394

395 /*

396 ** Return the number of bytes required to encode v as a varint

397 */

398 int sqlite3Fts3VarintLen(sqlite3_uint64 v){

399 int i = 0;

400 do{

401 i++;

402 v >>= 7;

403 }while( v!=0 );

404 return i;

405 }

406

407 /*

408 ** Convert an SQL-style quoted string into a normal string by removing

409 ** the quote characters. The conversion is done in-place. If the

410 ** input does not begin with a quote character, then this routine

411 ** is a no-op.

412 **

413 ** Examples:

414 **

415 ** "abc" becomes abc

416 ** 'xyz' becomes xyz

417 ** [pqr] becomes pqr

418 ** `mno` becomes mno

419 **

420 */

421 void sqlite3Fts3Dequote(char *z){

422 char quote; /* Quote character (if any ) */

423

424 quote = z[0];

425 if( quote=='[' \|\| quote=='\'' \|\| quote=='"' \|\| quote=='`' ){

426 int iIn = 1; /* Index of next byte to read from input */

427 int iOut = 0; /* Index of next byte to write to output */

428

429 /* If the first byte was a '[', then the close-quote character is a ']' */

430 if( quote=='[' ) quote = ']';

431

432 while( z[iIn] ){

433 if( z[iIn]==quote ){

434 if( z[iIn+1]!=quote ) break;

435 z[iOut++] = quote;

436 iIn += 2;

437 }else{

438 z[iOut++] = z[iIn++];

439 }

440 }

441 z[iOut] = '\0';

442 }

443 }

444

445 /*

446 ** Read a single varint from the doclist at pp and advance pp to point

447 ** to the first byte past the end of the varint. Add the value of the varint

448 ** to *pVal.

449 */

450 static void fts3GetDeltaVarint(char *pp, sqlite3_int64 pVal){

451 sqlite3_int64 iVal;

452 pp += sqlite3Fts3GetVarint(pp, &iVal);

453 *pVal += iVal;

454 }

455

456 /*

457 ** When this function is called, *pp points to the first byte following a

458 ** varint that is part of a doclist (or position-list, or any other list

459 ** of varints). This function moves *pp to point to the start of that varint,

460 ** and sets *pVal by the varint value.

461 **

462 ** Argument pStart points to the first byte of the doclist that the

463 ** varint is part of.

464 */

465 static void fts3GetReverseVarint(

466 char **pp,

467 char *pStart,

468 sqlite3_int64 *pVal

469 ){

470 sqlite3_int64 iVal;

471 char *p;

472

473 /* Pointer p now points at the first byte past the varint we are

474 ** interested in. So, unless the doclist is corrupt, the 0x80 bit is

475 ** clear on character p[-1]. */

476 for(p = (pp)-2; p>=pStart && p&0x80; p--);

477 p++;

478 *pp = p;

479

480 sqlite3Fts3GetVarint(p, &iVal);

481 *pVal = iVal;

482 }

483

484 /*

485 ** The xDisconnect() virtual table method.

486 */

487 static int fts3DisconnectMethod(sqlite3_vtab *pVtab){

488 Fts3Table p = (Fts3Table )pVtab;

489 int i;

490

491 assert( p->nPendingData==0 );

492 assert( p->pSegments==0 );

493

494 /* Free any prepared statements held */

495 for(i=0; i<SizeofArray(p->aStmt); i++){

496 sqlite3_finalize(p->aStmt[i]);

497 }

498 sqlite3_free(p->zSegmentsTbl);

499 sqlite3_free(p->zReadExprlist);

500 sqlite3_free(p->zWriteExprlist);

501 sqlite3_free(p->zContentTbl);

502 sqlite3_free(p->zLanguageid);

503

504 /* Invoke the tokenizer destructor to free the tokenizer. */

505 p->pTokenizer->pModule->xDestroy(p->pTokenizer);

506

507 sqlite3_free(p);

508 return SQLITE_OK;

509 }

510

511 /*

512 ** Write an error message into *pzErr

513 */

514 void sqlite3Fts3ErrMsg(char *pzErr, const char zFormat, ...){

515 va_list ap;

516 sqlite3_free(*pzErr);

517 va_start(ap, zFormat);

518 *pzErr = sqlite3_vmprintf(zFormat, ap);

519 va_end(ap);

520 }

521

522 /*

523 ** Construct one or more SQL statements from the format string given

524 ** and then evaluate those statements. The success code is written

525 ** into *pRc.

526 **

527 ** If *pRc is initially non-zero then this routine is a no-op.

528 */

529 static void fts3DbExec(

530 int pRc, / Success code */

531 sqlite3 db, / Database in which to run SQL */

532 const char zFormat, / Format string for SQL */

533 ... /* Arguments to the format string */

534 ){

535 va_list ap;

536 char *zSql;

537 if( *pRc ) return;

538 va_start(ap, zFormat);

539 zSql = sqlite3_vmprintf(zFormat, ap);

540 va_end(ap);

541 if( zSql==0 ){

542 *pRc = SQLITE_NOMEM;

543 }else{

544 *pRc = sqlite3_exec(db, zSql, 0, 0, 0);

545 sqlite3_free(zSql);

546 }

547 }

548

549 /*

550 ** The xDestroy() virtual table method.

551 */

552 static int fts3DestroyMethod(sqlite3_vtab *pVtab){

553 Fts3Table p = (Fts3Table )pVtab;

554 int rc = SQLITE_OK; /* Return code */

555 const char zDb = p->zDb; / Name of database (e.g. "main", "temp") */

556 sqlite3 db = p->db; / Database handle */

557

558 /* Drop the shadow tables */

559 if( p->zContentTbl==0 ){

560 fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_content'", zDb, p->zName);

561 }

562 fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_segments'", zDb,p->zName);

563 fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_segdir'", zDb, p->zName);

564 fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_docsize'", zDb, p->zName);

565 fts3DbExec(&rc, db, "DROP TABLE IF EXISTS %Q.'%q_stat'", zDb, p->zName);

566

567 /* If everything has worked, invoke fts3DisconnectMethod() to free the

568 ** memory associated with the Fts3Table structure and return SQLITE_OK.

569 ** Otherwise, return an SQLite error code.

570 */

571 return (rc==SQLITE_OK ? fts3DisconnectMethod(pVtab) : rc);

572 }

573

574

575 /*

576 ** Invoke sqlite3_declare_vtab() to declare the schema for the FTS3 table

577 ** passed as the first argument. This is done as part of the xConnect()

578 ** and xCreate() methods.

579 **

580 ** If *pRc is non-zero when this function is called, it is a no-op.

581 ** Otherwise, if an error occurs, an SQLite error code is stored in *pRc

582 ** before returning.

583 */

584 static void fts3DeclareVtab(int pRc, Fts3Table p){

585 if( *pRc==SQLITE_OK ){

586 int i; /* Iterator variable */

587 int rc; /* Return code */

588 char zSql; / SQL statement passed to declare_vtab() */

589 char zCols; / List of user defined columns */

590 const char *zLanguageid;

591

592 zLanguageid = (p->zLanguageid ? p->zLanguageid : "__langid");

593 sqlite3_vtab_config(p->db, SQLITE_VTAB_CONSTRAINT_SUPPORT, 1);

594

595 /* Create a list of user columns for the virtual table */

596 zCols = sqlite3_mprintf("%Q, ", p->azColumn[0]);

597 for(i=1; zCols && i<p->nColumn; i++){

598 zCols = sqlite3_mprintf("%z%Q, ", zCols, p->azColumn[i]);

599 }

600

601 /* Create the whole "CREATE TABLE" statement to pass to SQLite */

602 zSql = sqlite3_mprintf(

603 "CREATE TABLE x(%s %Q HIDDEN, docid HIDDEN, %Q HIDDEN)",

604 zCols, p->zName, zLanguageid

605 );

606 if( !zCols \|\| !zSql ){

607 rc = SQLITE_NOMEM;

608 }else{

609 rc = sqlite3_declare_vtab(p->db, zSql);

610 }

611

612 sqlite3_free(zSql);

613 sqlite3_free(zCols);

614 *pRc = rc;

615 }

616 }

617

618 /*

619 ** Create the %_stat table if it does not already exist.

620 */

621 void sqlite3Fts3CreateStatTable(int pRc, Fts3Table p){

622 fts3DbExec(pRc, p->db,

623 "CREATE TABLE IF NOT EXISTS %Q.'%q_stat'"

624 "(id INTEGER PRIMARY KEY, value BLOB);",

625 p->zDb, p->zName

626 );

627 if( (*pRc)==SQLITE_OK ) p->bHasStat = 1;

628 }

629

630 /*

631 ** Create the backing store tables (%_content, %_segments and %_segdir)

632 ** required by the FTS3 table passed as the only argument. This is done

633 ** as part of the vtab xCreate() method.

634 **

635 ** If the p->bHasDocsize boolean is true (indicating that this is an

636 ** FTS4 table, not an FTS3 table) then also create the %_docsize and

637 ** %_stat tables required by FTS4.

638 */

639 static int fts3CreateTables(Fts3Table *p){

640 int rc = SQLITE_OK; /* Return code */

641 int i; /* Iterator variable */

642 sqlite3 db = p->db; / The database connection */

643

644 if( p->zContentTbl==0 ){

645 const char *zLanguageid = p->zLanguageid;

646 char zContentCols; / Columns of %_content table */

647

648 /* Create a list of user columns for the content table */

649 zContentCols = sqlite3_mprintf("docid INTEGER PRIMARY KEY");

650 for(i=0; zContentCols && i<p->nColumn; i++){

651 char *z = p->azColumn[i];

652 zContentCols = sqlite3_mprintf("%z, 'c%d%q'", zContentCols, i, z);

653 }

654 if( zLanguageid && zContentCols ){

655 zContentCols = sqlite3_mprintf("%z, langid", zContentCols, zLanguageid);

656 }

657 if( zContentCols==0 ) rc = SQLITE_NOMEM;

658

659 /* Create the content table */

660 fts3DbExec(&rc, db,

661 "CREATE TABLE %Q.'%q_content'(%s)",

662 p->zDb, p->zName, zContentCols

663 );

664 sqlite3_free(zContentCols);

665 }

666

667 /* Create other tables */

668 fts3DbExec(&rc, db,

669 "CREATE TABLE %Q.'%q_segments'(blockid INTEGER PRIMARY KEY, block BLOB);",

670 p->zDb, p->zName

671 );

672 fts3DbExec(&rc, db,

673 "CREATE TABLE %Q.'%q_segdir'("

674 "level INTEGER,"

675 "idx INTEGER,"

676 "start_block INTEGER,"

677 "leaves_end_block INTEGER,"

678 "end_block INTEGER,"

679 "root BLOB,"

680 "PRIMARY KEY(level, idx)"

681 ");",

682 p->zDb, p->zName

683 );

684 if( p->bHasDocsize ){

685 fts3DbExec(&rc, db,

686 "CREATE TABLE %Q.'%q_docsize'(docid INTEGER PRIMARY KEY, size BLOB);",

687 p->zDb, p->zName

688 );

689 }

690 assert( p->bHasStat==p->bFts4 );

691 if( p->bHasStat ){

692 sqlite3Fts3CreateStatTable(&rc, p);

693 }

694 return rc;

695 }

696

697 /*

698 ** Store the current database page-size in bytes in p->nPgsz.

699 **

700 ** If *pRc is non-zero when this function is called, it is a no-op.

701 ** Otherwise, if an error occurs, an SQLite error code is stored in *pRc

702 ** before returning.

703 */

704 static void fts3DatabasePageSize(int pRc, Fts3Table p){

705 if( *pRc==SQLITE_OK ){

706 int rc; /* Return code */

707 char zSql; / SQL text "PRAGMA %Q.page_size" */

708 sqlite3_stmt pStmt; / Compiled "PRAGMA %Q.page_size" statement */

709

710 zSql = sqlite3_mprintf("PRAGMA %Q.page_size", p->zDb);

711 if( !zSql ){

712 rc = SQLITE_NOMEM;

713 }else{

714 rc = sqlite3_prepare(p->db, zSql, -1, &pStmt, 0);

715 if( rc==SQLITE_OK ){

716 sqlite3_step(pStmt);

717 p->nPgsz = sqlite3_column_int(pStmt, 0);

718 rc = sqlite3_finalize(pStmt);

719 }else if( rc==SQLITE_AUTH ){

720 p->nPgsz = 1024;

721 rc = SQLITE_OK;

722 }

723 }

724 assert( p->nPgsz>0 \|\| rc!=SQLITE_OK );

725 sqlite3_free(zSql);

726 *pRc = rc;

727 }

728 }

729

730 /*

731 ** "Special" FTS4 arguments are column specifications of the following form:

732 **

733 ** <key> = <value>

734 **

735 ** There may not be whitespace surrounding the "=" character. The <value>

736 ** term may be quoted, but the <key> may not.

737 */

738 static int fts3IsSpecialColumn(

739 const char *z,

740 int *pnKey,

741 char **pzValue

742 ){

743 char *zValue;

744 const char *zCsr = z;

745

746 while( *zCsr!='=' ){

747 if( *zCsr=='\0' ) return 0;

748 zCsr++;

749 }

750

751 *pnKey = (int)(zCsr-z);

752 zValue = sqlite3_mprintf("%s", &zCsr[1]);

753 if( zValue ){

754 sqlite3Fts3Dequote(zValue);

755 }

756 *pzValue = zValue;

757 return 1;

758 }

759

760 /*

761 ** Append the output of a printf() style formatting to an existing string.

762 */

763 static void fts3Appendf(

764 int pRc, / IN/OUT: Error code */

765 char *pz, / IN/OUT: Pointer to string buffer */

766 const char zFormat, / Printf format string to append */

767 ... /* Arguments for printf format string */

768 ){

769 if( *pRc==SQLITE_OK ){

770 va_list ap;

771 char *z;

772 va_start(ap, zFormat);

773 z = sqlite3_vmprintf(zFormat, ap);

774 va_end(ap);

775 if( z && *pz ){

776 char z2 = sqlite3_mprintf("%s%s", pz, z);

777 sqlite3_free(z);

778 z = z2;

779 }

780 if( z==0 ) *pRc = SQLITE_NOMEM;

781 sqlite3_free(*pz);

782 *pz = z;

783 }

784 }

785

786 /*

787 ** Return a copy of input string zInput enclosed in double-quotes (") and

788 ** with all double quote characters escaped. For example:

789 **

790 ** fts3QuoteId("un \"zip\"") -> "un \"\"zip\"\""

791 **

792 ** The pointer returned points to memory obtained from sqlite3_malloc(). It

793 ** is the callers responsibility to call sqlite3_free() to release this

794 ** memory.

795 */

796 static char fts3QuoteId(char const zInput){

797 int nRet;

798 char *zRet;

799 nRet = 2 + (int)strlen(zInput)*2 + 1;

800 zRet = sqlite3_malloc(nRet);

801 if( zRet ){

802 int i;

803 char *z = zRet;

804 *(z++) = '"';

805 for(i=0; zInput[i]; i++){

806 if( zInput[i]=='"' ) *(z++) = '"';

807 *(z++) = zInput[i];

808 }

809 *(z++) = '"';

810 *(z++) = '\0';

811 }

812 return zRet;

813 }

814

815 /*

816 ** Return a list of comma separated SQL expressions and a FROM clause that

817 ** could be used in a SELECT statement such as the following:

818 **

819 ** SELECT <list of expressions> FROM %_content AS x ...

820 **

821 ** to return the docid, followed by each column of text data in order

822 ** from left to write. If parameter zFunc is not NULL, then instead of

823 ** being returned directly each column of text data is passed to an SQL

824 ** function named zFunc first. For example, if zFunc is "unzip" and the

825 ** table has the three user-defined columns "a", "b", and "c", the following

826 ** string is returned:

827 **

828 ** "docid, unzip(x.'a'), unzip(x.'b'), unzip(x.'c') FROM %_content AS x"

829 **

830 ** The pointer returned points to a buffer allocated by sqlite3_malloc(). It

831 ** is the responsibility of the caller to eventually free it.

832 **

833 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op (and

834 ** a NULL pointer is returned). Otherwise, if an OOM error is encountered

835 ** by this function, NULL is returned and *pRc is set to SQLITE_NOMEM. If

836 ** no error occurs, *pRc is left unmodified.

837 */

838 static char fts3ReadExprList(Fts3Table p, const char zFunc, int pRc){

839 char *zRet = 0;

840 char *zFree = 0;

841 char *zFunction;

842 int i;

843

844 if( p->zContentTbl==0 ){

845 if( !zFunc ){

846 zFunction = "";

847 }else{

848 zFree = zFunction = fts3QuoteId(zFunc);

849 }

850 fts3Appendf(pRc, &zRet, "docid");

851 for(i=0; i<p->nColumn; i++){

852 fts3Appendf(pRc, &zRet, ",%s(x.'c%d%q')", zFunction, i, p->azColumn[i]);

853 }

854 if( p->zLanguageid ){

855 fts3Appendf(pRc, &zRet, ", x.%Q", "langid");

856 }

857 sqlite3_free(zFree);

858 }else{

859 fts3Appendf(pRc, &zRet, "rowid");

860 for(i=0; i<p->nColumn; i++){

861 fts3Appendf(pRc, &zRet, ", x.'%q'", p->azColumn[i]);

862 }

863 if( p->zLanguageid ){

864 fts3Appendf(pRc, &zRet, ", x.%Q", p->zLanguageid);

865 }

866 }

867 fts3Appendf(pRc, &zRet, " FROM '%q'.'%q%s' AS x",

868 p->zDb,

869 (p->zContentTbl ? p->zContentTbl : p->zName),

870 (p->zContentTbl ? "" : "_content")

871 );

872 return zRet;

873 }

874

875 /*

876 ** Return a list of N comma separated question marks, where N is the number

877 ** of columns in the %_content table (one for the docid plus one for each

878 ** user-defined text column).

879 **

880 ** If argument zFunc is not NULL, then all but the first question mark

881 ** is preceded by zFunc and an open bracket, and followed by a closed

882 ** bracket. For example, if zFunc is "zip" and the FTS3 table has three

883 ** user-defined text columns, the following string is returned:

884 **

885 ** "?, zip(?), zip(?), zip(?)"

886 **

887 ** The pointer returned points to a buffer allocated by sqlite3_malloc(). It

888 ** is the responsibility of the caller to eventually free it.

889 **

890 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op (and

891 ** a NULL pointer is returned). Otherwise, if an OOM error is encountered

892 ** by this function, NULL is returned and *pRc is set to SQLITE_NOMEM. If

893 ** no error occurs, *pRc is left unmodified.

894 */

895 static char fts3WriteExprList(Fts3Table p, const char zFunc, int pRc){

896 char *zRet = 0;

897 char *zFree = 0;

898 char *zFunction;

899 int i;

900

901 if( !zFunc ){

902 zFunction = "";

903 }else{

904 zFree = zFunction = fts3QuoteId(zFunc);

905 }

906 fts3Appendf(pRc, &zRet, "?");

907 for(i=0; i<p->nColumn; i++){

908 fts3Appendf(pRc, &zRet, ",%s(?)", zFunction);

909 }

910 if( p->zLanguageid ){

911 fts3Appendf(pRc, &zRet, ", ?");

912 }

913 sqlite3_free(zFree);

914 return zRet;

915 }

916

917 /*

918 ** This function interprets the string at (*pp) as a non-negative integer

919 ** value. It reads the integer and sets *pnOut to the value read, then

920 ** sets *pp to point to the byte immediately following the last byte of

921 ** the integer value.

922 **

923 ** Only decimal digits ('0'..'9') may be part of an integer value.

924 **

925 ** If *pp does not being with a decimal digit SQLITE_ERROR is returned and

926 ** the output value undefined. Otherwise SQLITE_OK is returned.

927 **

928 ** This function is used when parsing the "prefix=" FTS4 parameter.

929 */

930 static int fts3GobbleInt(const char *pp, int pnOut){

931 const int MAX_NPREFIX = 10000000;

932 const char p; / Iterator pointer */

933 int nInt = 0; /* Output value */

934

935 for(p=*pp; p[0]>='0' && p[0]<='9'; p++){

936 nInt = nInt * 10 + (p[0] - '0');

937 if( nInt>MAX_NPREFIX ){

938 nInt = 0;

939 break;

940 }

941 }

942 if( p==*pp ) return SQLITE_ERROR;

943 *pnOut = nInt;

944 *pp = p;

945 return SQLITE_OK;

946 }

947

948 /*

949 ** This function is called to allocate an array of Fts3Index structures

950 ** representing the indexes maintained by the current FTS table. FTS tables

951 ** always maintain the main "terms" index, but may also maintain one or

952 ** more "prefix" indexes, depending on the value of the "prefix=" parameter

953 ** (if any) specified as part of the CREATE VIRTUAL TABLE statement.

954 **

955 ** Argument zParam is passed the value of the "prefix=" option if one was

956 ** specified, or NULL otherwise.

957 **

958 ** If no error occurs, SQLITE_OK is returned and *apIndex set to point to

959 ** the allocated array. *pnIndex is set to the number of elements in the

960 ** array. If an error does occur, an SQLite error code is returned.

961 **

962 ** Regardless of whether or not an error is returned, it is the responsibility

963 ** of the caller to call sqlite3_free() on the output array to free it.

964 */

965 static int fts3PrefixParameter(

966 const char zParam, / ABC in prefix=ABC parameter to parse */

967 int pnIndex, / OUT: size of apIndex[] array /

968 struct Fts3Index *apIndex / OUT: Array of indexes for this table */

969 ){

970 struct Fts3Index aIndex; / Allocated array */

971 int nIndex = 1; /* Number of entries in array */

972

973 if( zParam && zParam[0] ){

974 const char *p;

975 nIndex++;

976 for(p=zParam; *p; p++){

977 if( *p==',' ) nIndex++;

978 }

979 }

980

981 aIndex = sqlite3_malloc(sizeof(struct Fts3Index) * nIndex);

982 *apIndex = aIndex;

983 if( !aIndex ){

984 return SQLITE_NOMEM;

985 }

986

987 memset(aIndex, 0, sizeof(struct Fts3Index) * nIndex);

988 if( zParam ){

989 const char *p = zParam;

990 int i;

991 for(i=1; i<nIndex; i++){

992 int nPrefix = 0;

993 if( fts3GobbleInt(&p, &nPrefix) ) return SQLITE_ERROR;

994 assert( nPrefix>=0 );

995 if( nPrefix==0 ){

996 nIndex--;

997 i--;

998 }else{

999 aIndex[i].nPrefix = nPrefix;

1000 }

1001 p++;

1002 }

1003 }

1004

1005 *pnIndex = nIndex;

1006 return SQLITE_OK;

1007 }

1008

1009 /*

1010 ** This function is called when initializing an FTS4 table that uses the

1011 ** content=xxx option. It determines the number of and names of the columns

1012 ** of the new FTS4 table.

1013 **

1014 ** The third argument passed to this function is the value passed to the

1015 ** config=xxx option (i.e. "xxx"). This function queries the database for

1016 ** a table of that name. If found, the output variables are populated

1017 ** as follows:

1018 **

1019 ** *pnCol: Set to the number of columns table xxx has,

1020 **

1021 ** *pnStr: Set to the total amount of space required to store a copy

1022 ** of each columns name, including the nul-terminator.

1023 **

1024 ** pazCol: Set to point to an array of pnCol strings. Each string is

1025 ** the name of the corresponding column in table xxx. The array

1026 ** and its contents are allocated using a single allocation. It

1027 ** is the responsibility of the caller to free this allocation

1028 ** by eventually passing the *pazCol value to sqlite3_free().

1029 **

1030 ** If the table cannot be found, an error code is returned and the output

1031 ** variables are undefined. Or, if an OOM is encountered, SQLITE_NOMEM is

1032 ** returned (and the output variables are undefined).

1033 */

1034 static int fts3ContentColumns(

1035 sqlite3 db, / Database handle */

1036 const char zDb, / Name of db (i.e. "main", "temp" etc.) */

1037 const char zTbl, / Name of content table */

1038 const char **pazCol, / OUT: Malloc'd array of column names */

1039 int pnCol, / OUT: Size of array pazCol /

1040 int pnStr, / OUT: Bytes of string content */

1041 char *pzErr / OUT: error message */

1042 ){

1043 int rc = SQLITE_OK; /* Return code */

1044 char zSql; / "SELECT " statement on zTbl /

1045 sqlite3_stmt pStmt = 0; / Compiled version of zSql */

1046

1047 zSql = sqlite3_mprintf("SELECT * FROM %Q.%Q", zDb, zTbl);

1048 if( !zSql ){

1049 rc = SQLITE_NOMEM;

1050 }else{

1051 rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);

1052 if( rc!=SQLITE_OK ){

1053 sqlite3Fts3ErrMsg(pzErr, "%s", sqlite3_errmsg(db));

1054 }

1055 }

1056 sqlite3_free(zSql);

1057

1058 if( rc==SQLITE_OK ){

1059 const char *azCol; / Output array */

1060 int nStr = 0; /* Size of all column names (incl. 0x00) */

1061 int nCol; /* Number of table columns */

1062 int i; /* Used to iterate through columns */

1063

1064 /* Loop through the returned columns. Set nStr to the number of bytes of

1065 ** space required to store a copy of each column name, including the

1066 ** nul-terminator byte. */

1067 nCol = sqlite3_column_count(pStmt);

1068 for(i=0; i<nCol; i++){

1069 const char *zCol = sqlite3_column_name(pStmt, i);

1070 nStr += (int)strlen(zCol) + 1;

1071 }

1072

1073 /* Allocate and populate the array to return. */

1074 azCol = (const char *)sqlite3_malloc(sizeof(char ) * nCol + nStr);

1075 if( azCol==0 ){

1076 rc = SQLITE_NOMEM;

1077 }else{

1078 char p = (char )&azCol[nCol];

1079 for(i=0; i<nCol; i++){

1080 const char *zCol = sqlite3_column_name(pStmt, i);

1081 int n = (int)strlen(zCol)+1;

1082 memcpy(p, zCol, n);

1083 azCol[i] = p;

1084 p += n;

1085 }

1086 }

1087 sqlite3_finalize(pStmt);

1088

1089 /* Set the output variables. */

1090 *pnCol = nCol;

1091 *pnStr = nStr;

1092 *pazCol = azCol;

1093 }

1094

1095 return rc;

1096 }

1097

1098 /*

1099 ** This function is the implementation of both the xConnect and xCreate

1100 ** methods of the FTS3 virtual table.

1101 **

1102 ** The argv[] array contains the following:

1103 **

1104 ** argv[0] -> module name ("fts3" or "fts4")

1105 ** argv[1] -> database name

1106 ** argv[2] -> table name

1107 ** argv[...] -> "column name" and other module argument fields.

1108 */

1109 static int fts3InitVtab(

1110 int isCreate, /* True for xCreate, false for xConnect */

1111 sqlite3 db, / The SQLite database connection */

1112 void pAux, / Hash table containing tokenizers */

1113 int argc, /* Number of elements in argv array */

1114 const char * const argv, / xCreate/xConnect argument array */

1115 sqlite3_vtab *ppVTab, / Write the resulting vtab structure here */

1116 char *pzErr / Write any error message here */

1117 ){

1118 Fts3Hash pHash = (Fts3Hash )pAux;

1119 Fts3Table p = 0; / Pointer to allocated vtab */

1120 int rc = SQLITE_OK; /* Return code */

1121 int i; /* Iterator variable */

1122 int nByte; /* Size of allocation used for p /

1123 int iCol; /* Column index */

1124 int nString = 0; /* Bytes required to hold all column names */

1125 int nCol = 0; /* Number of columns in the FTS table */

1126 char zCsr; / Space for holding column names */

1127 int nDb; /* Bytes required to hold database name */

1128 int nName; /* Bytes required to hold table name */

1129 int isFts4 = (argv[0][3]=='4'); /* True for FTS4, false for FTS3 */

1130 const char *aCol; / Array of column names */

1131 sqlite3_tokenizer pTokenizer = 0; / Tokenizer for this table */

1132

1133 int nIndex = 0; /* Size of aIndex[] array */

1134 struct Fts3Index aIndex = 0; / Array of indexes for this table */

1135

1136 /* The results of parsing supported FTS4 key=value options: */

1137 int bNoDocsize = 0; /* True to omit %_docsize table */

1138 int bDescIdx = 0; /* True to store descending indexes */

1139 char zPrefix = 0; / Prefix parameter value (or NULL) */

1140 char zCompress = 0; / compress=? parameter (or NULL) */

1141 char zUncompress = 0; / uncompress=? parameter (or NULL) */

1142 char zContent = 0; / content=? parameter (or NULL) */

1143 char zLanguageid = 0; / languageid=? parameter (or NULL) */

1144 char *azNotindexed = 0; / The set of notindexed= columns */

1145 int nNotindexed = 0; /* Size of azNotindexed[] array */

1146

1147 assert( strlen(argv[0])==4 );

1148 assert( (sqlite3_strnicmp(argv[0], "fts4", 4)==0 && isFts4)

1149 \|\| (sqlite3_strnicmp(argv[0], "fts3", 4)==0 && !isFts4)

1150 );

1151

1152 nDb = (int)strlen(argv[1]) + 1;

1153 nName = (int)strlen(argv[2]) + 1;

1154

1155 nByte = sizeof(const char ) (argc-2);

1156 aCol = (const char **)sqlite3_malloc(nByte);

1157 if( aCol ){

1158 memset((void*)aCol, 0, nByte);

1159 azNotindexed = (char **)sqlite3_malloc(nByte);

1160 }

1161 if( azNotindexed ){

1162 memset(azNotindexed, 0, nByte);

1163 }

1164 if( !aCol \|\| !azNotindexed ){

1165 rc = SQLITE_NOMEM;

1166 goto fts3_init_out;

1167 }

1168

1169 /* Loop through all of the arguments passed by the user to the FTS3/4

1170 ** module (i.e. all the column names and special arguments). This loop

1171 ** does the following:

1172 **

1173 ** + Figures out the number of columns the FTSX table will have, and

1174 ** the number of bytes of space that must be allocated to store copies

1175 ** of the column names.

1176 **

1177 ** + If there is a tokenizer specification included in the arguments,

1178 ** initializes the tokenizer pTokenizer.

1179 */

1180 for(i=3; rc==SQLITE_OK && i<argc; i++){

1181 char const *z = argv[i];

1182 int nKey;

1183 char *zVal;

1184

1185 /* Check if this is a tokenizer specification */

1186 if( !pTokenizer

1187 && strlen(z)>8

1188 && 0==sqlite3_strnicmp(z, "tokenize", 8)

1189 && 0==sqlite3Fts3IsIdChar(z[8])

1190 ){

1191 rc = sqlite3Fts3InitTokenizer(pHash, &z[9], &pTokenizer, pzErr);

1192 }

1193

1194 /* Check if it is an FTS4 special argument. */

1195 else if( isFts4 && fts3IsSpecialColumn(z, &nKey, &zVal) ){

1196 struct Fts4Option {

1197 const char *zOpt;

1198 int nOpt;

1199 } aFts4Opt[] = {

1200 { "matchinfo", 9 }, /* 0 -> MATCHINFO */

1201 { "prefix", 6 }, /* 1 -> PREFIX */

1202 { "compress", 8 }, /* 2 -> COMPRESS */

1203 { "uncompress", 10 }, /* 3 -> UNCOMPRESS */

1204 { "order", 5 }, /* 4 -> ORDER */

1205 { "content", 7 }, /* 5 -> CONTENT */

1206 { "languageid", 10 }, /* 6 -> LANGUAGEID */

1207 { "notindexed", 10 } /* 7 -> NOTINDEXED */

1208 };

1209

1210 int iOpt;

1211 if( !zVal ){

1212 rc = SQLITE_NOMEM;

1213 }else{

1214 for(iOpt=0; iOpt<SizeofArray(aFts4Opt); iOpt++){

1215 struct Fts4Option *pOp = &aFts4Opt[iOpt];

1216 if( nKey==pOp->nOpt && !sqlite3_strnicmp(z, pOp->zOpt, pOp->nOpt) ){

1217 break;

1218 }

1219 }

1220 if( iOpt==SizeofArray(aFts4Opt) ){

1221 sqlite3Fts3ErrMsg(pzErr, "unrecognized parameter: %s", z);

1222 rc = SQLITE_ERROR;

1223 }else{

1224 switch( iOpt ){

1225 case 0: /* MATCHINFO */

1226 if( strlen(zVal)!=4 \|\| sqlite3_strnicmp(zVal, "fts3", 4) ){

1227 sqlite3Fts3ErrMsg(pzErr, "unrecognized matchinfo: %s", zVal);

1228 rc = SQLITE_ERROR;

1229 }

1230 bNoDocsize = 1;

1231 break;

1232

1233 case 1: /* PREFIX */

1234 sqlite3_free(zPrefix);

1235 zPrefix = zVal;

1236 zVal = 0;

1237 break;

1238

1239 case 2: /* COMPRESS */

1240 sqlite3_free(zCompress);

1241 zCompress = zVal;

1242 zVal = 0;

1243 break;

1244

1245 case 3: /* UNCOMPRESS */

1246 sqlite3_free(zUncompress);

1247 zUncompress = zVal;

1248 zVal = 0;

1249 break;

1250

1251 case 4: /* ORDER */

1252 if( (strlen(zVal)!=3 \|\| sqlite3_strnicmp(zVal, "asc", 3))

1253 && (strlen(zVal)!=4 \|\| sqlite3_strnicmp(zVal, "desc", 4))

1254 ){

1255 sqlite3Fts3ErrMsg(pzErr, "unrecognized order: %s", zVal);

1256 rc = SQLITE_ERROR;

1257 }

1258 bDescIdx = (zVal[0]=='d' \|\| zVal[0]=='D');

1259 break;

1260

1261 case 5: /* CONTENT */

1262 sqlite3_free(zContent);

1263 zContent = zVal;

1264 zVal = 0;

1265 break;

1266

1267 case 6: /* LANGUAGEID */

1268 assert( iOpt==6 );

1269 sqlite3_free(zLanguageid);

1270 zLanguageid = zVal;

1271 zVal = 0;

1272 break;

1273

1274 case 7: /* NOTINDEXED */

1275 azNotindexed[nNotindexed++] = zVal;

1276 zVal = 0;

1277 break;

1278 }

1279 }

1280 sqlite3_free(zVal);

1281 }

1282 }

1283

1284 /* Otherwise, the argument is a column name. */

1285 else {

1286 nString += (int)(strlen(z) + 1);

1287 aCol[nCol++] = z;

1288 }

1289 }

1290

1291 /* If a content=xxx option was specified, the following:

1292 **

1293 ** 1. Ignore any compress= and uncompress= options.

1294 **

1295 ** 2. If no column names were specified as part of the CREATE VIRTUAL

1296 ** TABLE statement, use all columns from the content table.

1297 */

1298 if( rc==SQLITE_OK && zContent ){

1299 sqlite3_free(zCompress);

1300 sqlite3_free(zUncompress);

1301 zCompress = 0;

1302 zUncompress = 0;

1303 if( nCol==0 ){

1304 sqlite3_free((void*)aCol);

1305 aCol = 0;

1306 rc = fts3ContentColumns(db, argv[1], zContent,&aCol,&nCol,&nString,pzErr);

1307

1308 /* If a languageid= option was specified, remove the language id

1309 ** column from the aCol[] array. */

1310 if( rc==SQLITE_OK && zLanguageid ){

1311 int j;

1312 for(j=0; j<nCol; j++){

1313 if( sqlite3_stricmp(zLanguageid, aCol[j])==0 ){

1314 int k;

1315 for(k=j; k<nCol; k++) aCol[k] = aCol[k+1];

1316 nCol--;

1317 break;

1318 }

1319 }

1320 }

1321 }

1322 }

1323 if( rc!=SQLITE_OK ) goto fts3_init_out;

1324

1325 if( nCol==0 ){

1326 assert( nString==0 );

1327 aCol[0] = "content";

1328 nString = 8;

1329 nCol = 1;

1330 }

1331

1332 if( pTokenizer==0 ){

1333 rc = sqlite3Fts3InitTokenizer(pHash, "simple", &pTokenizer, pzErr);

1334 if( rc!=SQLITE_OK ) goto fts3_init_out;

1335 }

1336 assert( pTokenizer );

1337

1338 rc = fts3PrefixParameter(zPrefix, &nIndex, &aIndex);

1339 if( rc==SQLITE_ERROR ){

1340 assert( zPrefix );

1341 sqlite3Fts3ErrMsg(pzErr, "error parsing prefix parameter: %s", zPrefix);

1342 }

1343 if( rc!=SQLITE_OK ) goto fts3_init_out;

1344

1345 /* Allocate and populate the Fts3Table structure. */

1346 nByte = sizeof(Fts3Table) + /* Fts3Table */

1347 nCol * sizeof(char ) + / azColumn */

1348 nIndex * sizeof(struct Fts3Index) + /* aIndex */

1349 nCol * sizeof(u8) + /* abNotindexed */

1350 nName + /* zName */

1351 nDb + /* zDb */

1352 nString; /* Space for azColumn strings */

1353 p = (Fts3Table*)sqlite3_malloc(nByte);

1354 if( p==0 ){

1355 rc = SQLITE_NOMEM;

1356 goto fts3_init_out;

1357 }

1358 memset(p, 0, nByte);

1359 p->db = db;

1360 p->nColumn = nCol;

1361 p->nPendingData = 0;

1362 p->azColumn = (char **)&p[1];

1363 p->pTokenizer = pTokenizer;

1364 p->nMaxPendingData = FTS3_MAX_PENDING_DATA;

1365 p->bHasDocsize = (isFts4 && bNoDocsize==0);

1366 p->bHasStat = isFts4;

1367 p->bFts4 = isFts4;

1368 p->bDescIdx = bDescIdx;

1369 p->nAutoincrmerge = 0xff; /* 0xff means setting unknown */

1370 p->zContentTbl = zContent;

1371 p->zLanguageid = zLanguageid;

1372 zContent = 0;

1373 zLanguageid = 0;

1374 TESTONLY( p->inTransaction = -1 );

1375 TESTONLY( p->mxSavepoint = -1 );

1376

1377 p->aIndex = (struct Fts3Index *)&p->azColumn[nCol];

1378 memcpy(p->aIndex, aIndex, sizeof(struct Fts3Index) * nIndex);

1379 p->nIndex = nIndex;

1380 for(i=0; i<nIndex; i++){

1381 fts3HashInit(&p->aIndex[i].hPending, FTS3_HASH_STRING, 1);

1382 }

1383 p->abNotindexed = (u8 *)&p->aIndex[nIndex];

1384

1385 /* Fill in the zName and zDb fields of the vtab structure. */

1386 zCsr = (char *)&p->abNotindexed[nCol];

1387 p->zName = zCsr;

1388 memcpy(zCsr, argv[2], nName);

1389 zCsr += nName;

1390 p->zDb = zCsr;

1391 memcpy(zCsr, argv[1], nDb);

1392 zCsr += nDb;

1393

1394 /* Fill in the azColumn array */

1395 for(iCol=0; iCol<nCol; iCol++){

1396 char *z;

1397 int n = 0;

1398 z = (char *)sqlite3Fts3NextToken(aCol[iCol], &n);

1399 memcpy(zCsr, z, n);

1400 zCsr[n] = '\0';

1401 sqlite3Fts3Dequote(zCsr);

1402 p->azColumn[iCol] = zCsr;

1403 zCsr += n+1;

1404 assert( zCsr <= &((char *)p)[nByte] );

1405 }

1406

1407 /* Fill in the abNotindexed array */

1408 for(iCol=0; iCol<nCol; iCol++){

1409 int n = (int)strlen(p->azColumn[iCol]);

1410 for(i=0; i<nNotindexed; i++){

1411 char *zNot = azNotindexed[i];

1412 if( zNot && n==(int)strlen(zNot)

1413 && 0==sqlite3_strnicmp(p->azColumn[iCol], zNot, n)

1414 ){

1415 p->abNotindexed[iCol] = 1;

1416 sqlite3_free(zNot);

1417 azNotindexed[i] = 0;

1418 }

1419 }

1420 }

1421 for(i=0; i<nNotindexed; i++){

1422 if( azNotindexed[i] ){

1423 sqlite3Fts3ErrMsg(pzErr, "no such column: %s", azNotindexed[i]);

1424 rc = SQLITE_ERROR;

1425 }

1426 }

1427

1428 if( rc==SQLITE_OK && (zCompress==0)!=(zUncompress==0) ){

1429 char const *zMiss = (zCompress==0 ? "compress" : "uncompress");

1430 rc = SQLITE_ERROR;

1431 sqlite3Fts3ErrMsg(pzErr, "missing %s parameter in fts4 constructor", zMiss);

1432 }

1433 p->zReadExprlist = fts3ReadExprList(p, zUncompress, &rc);

1434 p->zWriteExprlist = fts3WriteExprList(p, zCompress, &rc);

1435 if( rc!=SQLITE_OK ) goto fts3_init_out;

1436

1437 /* If this is an xCreate call, create the underlying tables in the

1438 ** database. TODO: For xConnect(), it could verify that said tables exist.

1439 */

1440 if( isCreate ){

1441 rc = fts3CreateTables(p);

1442 }

1443

1444 /* Check to see if a legacy fts3 table has been "upgraded" by the

1445 ** addition of a %_stat table so that it can use incremental merge.

1446 */

1447 if( !isFts4 && !isCreate ){

1448 p->bHasStat = 2;

1449 }

1450

1451 /* Figure out the page-size for the database. This is required in order to

1452 ** estimate the cost of loading large doclists from the database. */

1453 fts3DatabasePageSize(&rc, p);

1454 p->nNodeSize = p->nPgsz-35;

1455

1456 /* Declare the table schema to SQLite. */

1457 fts3DeclareVtab(&rc, p);

1458

1459 fts3_init_out:

1460 sqlite3_free(zPrefix);

1461 sqlite3_free(aIndex);

1462 sqlite3_free(zCompress);

1463 sqlite3_free(zUncompress);

1464 sqlite3_free(zContent);

1465 sqlite3_free(zLanguageid);

1466 for(i=0; i<nNotindexed; i++) sqlite3_free(azNotindexed[i]);

1467 sqlite3_free((void *)aCol);

1468 sqlite3_free((void *)azNotindexed);

1469 if( rc!=SQLITE_OK ){

1470 if( p ){

1471 fts3DisconnectMethod((sqlite3_vtab *)p);

1472 }else if( pTokenizer ){

1473 pTokenizer->pModule->xDestroy(pTokenizer);

1474 }

1475 }else{

1476 assert( p->pSegments==0 );

1477 *ppVTab = &p->base;

1478 }

1479 return rc;

1480 }

1481

1482 /*

1483 ** The xConnect() and xCreate() methods for the virtual table. All the

1484 ** work is done in function fts3InitVtab().

1485 */

1486 static int fts3ConnectMethod(

1487 sqlite3 db, / Database connection */

1488 void pAux, / Pointer to tokenizer hash table */

1489 int argc, /* Number of elements in argv array */

1490 const char * const argv, / xCreate/xConnect argument array */

1491 sqlite3_vtab *ppVtab, / OUT: New sqlite3_vtab object */

1492 char *pzErr / OUT: sqlite3_malloc'd error message */

1493 ){

1494 return fts3InitVtab(0, db, pAux, argc, argv, ppVtab, pzErr);

1495 }

1496 static int fts3CreateMethod(

1497 sqlite3 db, / Database connection */

1498 void pAux, / Pointer to tokenizer hash table */

1499 int argc, /* Number of elements in argv array */

1500 const char * const argv, / xCreate/xConnect argument array */

1501 sqlite3_vtab *ppVtab, / OUT: New sqlite3_vtab object */

1502 char *pzErr / OUT: sqlite3_malloc'd error message */

1503 ){

1504 return fts3InitVtab(1, db, pAux, argc, argv, ppVtab, pzErr);

1505 }

1506

1507 /*

1508 ** Set the pIdxInfo->estimatedRows variable to nRow. Unless this

1509 ** extension is currently being used by a version of SQLite too old to

1510 ** support estimatedRows. In that case this function is a no-op.

1511 */

1512 static void fts3SetEstimatedRows(sqlite3_index_info *pIdxInfo, i64 nRow){

1513 #if SQLITE_VERSION_NUMBER>=3008002

1514 if( sqlite3_libversion_number()>=3008002 ){

1515 pIdxInfo->estimatedRows = nRow;

1516 }

1517 #endif

1518 }

1519

1520 /*

1521 ** Set the SQLITE_INDEX_SCAN_UNIQUE flag in pIdxInfo->flags. Unless this

1522 ** extension is currently being used by a version of SQLite too old to

1523 ** support index-info flags. In that case this function is a no-op.

1524 */

1525 static void fts3SetUniqueFlag(sqlite3_index_info *pIdxInfo){

1526 #if SQLITE_VERSION_NUMBER>=3008012

1527 if( sqlite3_libversion_number()>=3008012 ){

1528 pIdxInfo->idxFlags \|= SQLITE_INDEX_SCAN_UNIQUE;

1529 }

1530 #endif

1531 }

1532

1533 /*

1534 ** Implementation of the xBestIndex method for FTS3 tables. There

1535 ** are three possible strategies, in order of preference:

1536 **

1537 ** 1. Direct lookup by rowid or docid.

1538 ** 2. Full-text search using a MATCH operator on a non-docid column.

1539 ** 3. Linear scan of %_content table.

1540 */

1541 static int fts3BestIndexMethod(sqlite3_vtab pVTab, sqlite3_index_info pInfo){

1542 Fts3Table p = (Fts3Table )pVTab;

1543 int i; /* Iterator variable */

1544 int iCons = -1; /* Index of constraint to use */

1545

1546 int iLangidCons = -1; /* Index of langid=x constraint, if present */

1547 int iDocidGe = -1; /* Index of docid>=x constraint, if present */

1548 int iDocidLe = -1; /* Index of docid<=x constraint, if present */

1549 int iIdx;

1550

1551 /* By default use a full table scan. This is an expensive option,

1552 ** so search through the constraints to see if a more efficient

1553 ** strategy is possible.

1554 */

1555 pInfo->idxNum = FTS3_FULLSCAN_SEARCH;

1556 pInfo->estimatedCost = 5000000;

1557 for(i=0; i<pInfo->nConstraint; i++){

1558 int bDocid; /* True if this constraint is on docid */

1559 struct sqlite3_index_constraint *pCons = &pInfo->aConstraint[i];

1560 if( pCons->usable==0 ){

1561 if( pCons->op==SQLITE_INDEX_CONSTRAINT_MATCH ){

1562 /* There exists an unusable MATCH constraint. This means that if

1563 ** the planner does elect to use the results of this call as part

1564 ** of the overall query plan the user will see an "unable to use

1565 ** function MATCH in the requested context" error. To discourage

1566 ** this, return a very high cost here. */

1567 pInfo->idxNum = FTS3_FULLSCAN_SEARCH;

1568 pInfo->estimatedCost = 1e50;

1569 fts3SetEstimatedRows(pInfo, ((sqlite3_int64)1) << 50);

1570 return SQLITE_OK;

1571 }

1572 continue;

1573 }

1574

1575 bDocid = (pCons->iColumn<0 \|\| pCons->iColumn==p->nColumn+1);

1576

1577 /* A direct lookup on the rowid or docid column. Assign a cost of 1.0. */

1578 if( iCons<0 && pCons->op==SQLITE_INDEX_CONSTRAINT_EQ && bDocid ){

1579 pInfo->idxNum = FTS3_DOCID_SEARCH;

1580 pInfo->estimatedCost = 1.0;

1581 iCons = i;

1582 }

1583

1584 /* A MATCH constraint. Use a full-text search.

1585 **

1586 ** If there is more than one MATCH constraint available, use the first

1587 ** one encountered. If there is both a MATCH constraint and a direct

1588 ** rowid/docid lookup, prefer the MATCH strategy. This is done even

1589 ** though the rowid/docid lookup is faster than a MATCH query, selecting

1590 ** it would lead to an "unable to use function MATCH in the requested

1591 ** context" error.

1592 */

1593 if( pCons->op==SQLITE_INDEX_CONSTRAINT_MATCH

1594 && pCons->iColumn>=0 && pCons->iColumn<=p->nColumn

1595 ){

1596 pInfo->idxNum = FTS3_FULLTEXT_SEARCH + pCons->iColumn;

1597 pInfo->estimatedCost = 2.0;

1598 iCons = i;

1599 }

1600

1601 /* Equality constraint on the langid column */

1602 if( pCons->op==SQLITE_INDEX_CONSTRAINT_EQ

1603 && pCons->iColumn==p->nColumn + 2

1604 ){

1605 iLangidCons = i;

1606 }

1607

1608 if( bDocid ){

1609 switch( pCons->op ){

1610 case SQLITE_INDEX_CONSTRAINT_GE:

1611 case SQLITE_INDEX_CONSTRAINT_GT:

1612 iDocidGe = i;

1613 break;

1614

1615 case SQLITE_INDEX_CONSTRAINT_LE:

1616 case SQLITE_INDEX_CONSTRAINT_LT:

1617 iDocidLe = i;

1618 break;

1619 }

1620 }

1621 }

1622

1623 /* If using a docid=? or rowid=? strategy, set the UNIQUE flag. */

1624 if( pInfo->idxNum==FTS3_DOCID_SEARCH ) fts3SetUniqueFlag(pInfo);

1625

1626 iIdx = 1;

1627 if( iCons>=0 ){

1628 pInfo->aConstraintUsage[iCons].argvIndex = iIdx++;

1629 pInfo->aConstraintUsage[iCons].omit = 1;

1630 }

1631 if( iLangidCons>=0 ){

1632 pInfo->idxNum \|= FTS3_HAVE_LANGID;

1633 pInfo->aConstraintUsage[iLangidCons].argvIndex = iIdx++;

1634 }

1635 if( iDocidGe>=0 ){

1636 pInfo->idxNum \|= FTS3_HAVE_DOCID_GE;

1637 pInfo->aConstraintUsage[iDocidGe].argvIndex = iIdx++;

1638 }

1639 if( iDocidLe>=0 ){

1640 pInfo->idxNum \|= FTS3_HAVE_DOCID_LE;

1641 pInfo->aConstraintUsage[iDocidLe].argvIndex = iIdx++;

1642 }

1643

1644 /* Regardless of the strategy selected, FTS can deliver rows in rowid (or

1645 ** docid) order. Both ascending and descending are possible.

1646 */

1647 if( pInfo->nOrderBy==1 ){

1648 struct sqlite3_index_orderby *pOrder = &pInfo->aOrderBy[0];

1649 if( pOrder->iColumn<0 \|\| pOrder->iColumn==p->nColumn+1 ){

1650 if( pOrder->desc ){

1651 pInfo->idxStr = "DESC";

1652 }else{

1653 pInfo->idxStr = "ASC";

1654 }

1655 pInfo->orderByConsumed = 1;

1656 }

1657 }

1658

1659 assert( p->pSegments==0 );

1660 return SQLITE_OK;

1661 }

1662

1663 /*

1664 ** Implementation of xOpen method.

1665 */

1666 static int fts3OpenMethod(sqlite3_vtab pVTab, sqlite3_vtab_cursor *ppCsr){

1667 sqlite3_vtab_cursor pCsr; / Allocated cursor */

1668

1669 UNUSED_PARAMETER(pVTab);

1670

1671 /* Allocate a buffer large enough for an Fts3Cursor structure. If the

1672 ** allocation succeeds, zero it and return SQLITE_OK. Otherwise,

1673 ** if the allocation fails, return SQLITE_NOMEM.

1674 */

1675 ppCsr = pCsr = (sqlite3_vtab_cursor )sqlite3_malloc(sizeof(Fts3Cursor));

1676 if( !pCsr ){

1677 return SQLITE_NOMEM;

1678 }

1679 memset(pCsr, 0, sizeof(Fts3Cursor));

1680 return SQLITE_OK;

1681 }

1682

1683 /*

1684 ** Close the cursor. For additional information see the documentation

1685 ** on the xClose method of the virtual table interface.

1686 */

1687 static int fts3CloseMethod(sqlite3_vtab_cursor *pCursor){

1688 Fts3Cursor pCsr = (Fts3Cursor )pCursor;

1689 assert( ((Fts3Table *)pCsr->base.pVtab)->pSegments==0 );

1690 sqlite3_finalize(pCsr->pStmt);

1691 sqlite3Fts3ExprFree(pCsr->pExpr);

1692 sqlite3Fts3FreeDeferredTokens(pCsr);

1693 sqlite3_free(pCsr->aDoclist);

1694 sqlite3Fts3MIBufferFree(pCsr->pMIBuffer);

1695 assert( ((Fts3Table *)pCsr->base.pVtab)->pSegments==0 );

1696 sqlite3_free(pCsr);

1697 return SQLITE_OK;

1698 }

1699

1700 /*

1701 ** If pCsr->pStmt has not been prepared (i.e. if pCsr->pStmt==0), then

1702 ** compose and prepare an SQL statement of the form:

1703 **

1704 ** "SELECT <columns> FROM %_content WHERE rowid = ?"

1705 **

1706 ** (or the equivalent for a content=xxx table) and set pCsr->pStmt to

1707 ** it. If an error occurs, return an SQLite error code.

1708 **

1709 ** Otherwise, set *ppStmt to point to pCsr->pStmt and return SQLITE_OK.

1710 */

1711 static int fts3CursorSeekStmt(Fts3Cursor pCsr, sqlite3_stmt *ppStmt){

1712 int rc = SQLITE_OK;

1713 if( pCsr->pStmt==0 ){

1714 Fts3Table p = (Fts3Table )pCsr->base.pVtab;

1715 char *zSql;

1716 zSql = sqlite3_mprintf("SELECT %s WHERE rowid = ?", p->zReadExprlist);

1717 if( !zSql ) return SQLITE_NOMEM;

1718 rc = sqlite3_prepare_v2(p->db, zSql, -1, &pCsr->pStmt, 0);

1719 sqlite3_free(zSql);

1720 }

1721 *ppStmt = pCsr->pStmt;

1722 return rc;

1723 }

1724

1725 /*

1726 ** Position the pCsr->pStmt statement so that it is on the row

1727 ** of the %_content table that contains the last match. Return

1728 ** SQLITE_OK on success.

1729 */

1730 static int fts3CursorSeek(sqlite3_context pContext, Fts3Cursor pCsr){

1731 int rc = SQLITE_OK;

1732 if( pCsr->isRequireSeek ){

1733 sqlite3_stmt *pStmt = 0;

1734

1735 rc = fts3CursorSeekStmt(pCsr, &pStmt);

1736 if( rc==SQLITE_OK ){

1737 sqlite3_bind_int64(pCsr->pStmt, 1, pCsr->iPrevId);

1738 pCsr->isRequireSeek = 0;

1739 if( SQLITE_ROW==sqlite3_step(pCsr->pStmt) ){

1740 return SQLITE_OK;

1741 }else{

1742 rc = sqlite3_reset(pCsr->pStmt);

1743 if( rc==SQLITE_OK && ((Fts3Table *)pCsr->base.pVtab)->zContentTbl==0 ){

1744 /* If no row was found and no error has occurred, then the %_content

1745 ** table is missing a row that is present in the full-text index.

1746 ** The data structures are corrupt. */

1747 rc = FTS_CORRUPT_VTAB;

1748 pCsr->isEof = 1;

1749 }

1750 }

1751 }

1752 }

1753

1754 if( rc!=SQLITE_OK && pContext ){

1755 sqlite3_result_error_code(pContext, rc);

1756 }

1757 return rc;

1758 }

1759

1760 /*

1761 ** This function is used to process a single interior node when searching

1762 ** a b-tree for a term or term prefix. The node data is passed to this

1763 ** function via the zNode/nNode parameters. The term to search for is

1764 ** passed in zTerm/nTerm.

1765 **

1766 ** If piFirst is not NULL, then this function sets *piFirst to the blockid

1767 ** of the child node that heads the sub-tree that may contain the term.

1768 **

1769 ** If piLast is not NULL, then *piLast is set to the right-most child node

1770 ** that heads a sub-tree that may contain a term for which zTerm/nTerm is

1771 ** a prefix.

1772 **

1773 ** If an OOM error occurs, SQLITE_NOMEM is returned. Otherwise, SQLITE_OK.

1774 */

1775 static int fts3ScanInteriorNode(

1776 const char zTerm, / Term to select leaves for */

1777 int nTerm, /* Size of term zTerm in bytes */

1778 const char zNode, / Buffer containing segment interior node */

1779 int nNode, /* Size of buffer at zNode */

1780 sqlite3_int64 piFirst, / OUT: Selected child node */

1781 sqlite3_int64 piLast / OUT: Selected child node */

1782 ){

1783 int rc = SQLITE_OK; /* Return code */

1784 const char zCsr = zNode; / Cursor to iterate through node */

1785 const char zEnd = &zCsr[nNode];/ End of interior node buffer */

1786 char zBuffer = 0; / Buffer to load terms into */

1787 int nAlloc = 0; /* Size of allocated buffer */

1788 int isFirstTerm = 1; /* True when processing first term on page */

1789 sqlite3_int64 iChild; /* Block id of child node to descend to */

1790

1791 /* Skip over the 'height' varint that occurs at the start of every

1792 ** interior node. Then load the blockid of the left-child of the b-tree

1793 ** node into variable iChild.

1794 **

1795 ** Even if the data structure on disk is corrupted, this (reading two

1796 ** varints from the buffer) does not risk an overread. If zNode is a

1797 ** root node, then the buffer comes from a SELECT statement. SQLite does

1798 ** not make this guarantee explicitly, but in practice there are always

1799 ** either more than 20 bytes of allocated space following the nNode bytes of

1800 ** contents, or two zero bytes. Or, if the node is read from the %_segments

1801 ** table, then there are always 20 bytes of zeroed padding following the

1802 ** nNode bytes of content (see sqlite3Fts3ReadBlock() for details).

1803 */

1804 zCsr += sqlite3Fts3GetVarint(zCsr, &iChild);

1805 zCsr += sqlite3Fts3GetVarint(zCsr, &iChild);

1806 if( zCsr>zEnd ){

1807 return FTS_CORRUPT_VTAB;

1808 }

1809

1810 while( zCsr<zEnd && (piFirst \|\| piLast) ){

1811 int cmp; /* memcmp() result */

1812 int nSuffix; /* Size of term suffix */

1813 int nPrefix = 0; /* Size of term prefix */

1814 int nBuffer; /* Total term size */

1815

1816 /* Load the next term on the node into zBuffer. Use realloc() to expand

1817 ** the size of zBuffer if required. */

1818 if( !isFirstTerm ){

1819 zCsr += fts3GetVarint32(zCsr, &nPrefix);

1820 }

1821 isFirstTerm = 0;

1822 zCsr += fts3GetVarint32(zCsr, &nSuffix);

1823

1824 if( nPrefix<0 \|\| nSuffix<0 \|\| &zCsr[nSuffix]>zEnd ){

1825 rc = FTS_CORRUPT_VTAB;

1826 goto finish_scan;

1827 }

1828 if( nPrefix+nSuffix>nAlloc ){

1829 char *zNew;

1830 nAlloc = (nPrefix+nSuffix) * 2;

1831 zNew = (char *)sqlite3_realloc(zBuffer, nAlloc);

1832 if( !zNew ){

1833 rc = SQLITE_NOMEM;

1834 goto finish_scan;

1835 }

1836 zBuffer = zNew;

1837 }

1838 assert( zBuffer );

1839 memcpy(&zBuffer[nPrefix], zCsr, nSuffix);

1840 nBuffer = nPrefix + nSuffix;

1841 zCsr += nSuffix;

1842

1843 /* Compare the term we are searching for with the term just loaded from

1844 ** the interior node. If the specified term is greater than or equal

1845 ** to the term from the interior node, then all terms on the sub-tree

1846 ** headed by node iChild are smaller than zTerm. No need to search

1847 ** iChild.

1848 **

1849 ** If the interior node term is larger than the specified term, then

1850 ** the tree headed by iChild may contain the specified term.

1851 */

1852 cmp = memcmp(zTerm, zBuffer, (nBuffer>nTerm ? nTerm : nBuffer));

1853 if( piFirst && (cmp<0 \|\| (cmp==0 && nBuffer>nTerm)) ){

1854 *piFirst = iChild;

1855 piFirst = 0;

1856 }

1857

1858 if( piLast && cmp<0 ){

1859 *piLast = iChild;

1860 piLast = 0;

1861 }

1862

1863 iChild++;

1864 };

1865

1866 if( piFirst ) *piFirst = iChild;

1867 if( piLast ) *piLast = iChild;

1868

1869 finish_scan:

1870 sqlite3_free(zBuffer);

1871 return rc;

1872 }

1873

1874

1875 /*

1876 ** The buffer pointed to by argument zNode (size nNode bytes) contains an

1877 ** interior node of a b-tree segment. The zTerm buffer (size nTerm bytes)

1878 ** contains a term. This function searches the sub-tree headed by the zNode

1879 ** node for the range of leaf nodes that may contain the specified term

1880 ** or terms for which the specified term is a prefix.

1881 **

1882 ** If piLeaf is not NULL, then *piLeaf is set to the blockid of the

1883 ** left-most leaf node in the tree that may contain the specified term.

1884 ** If piLeaf2 is not NULL, then *piLeaf2 is set to the blockid of the

1885 ** right-most leaf node that may contain a term for which the specified

1886 ** term is a prefix.

1887 **

1888 ** It is possible that the range of returned leaf nodes does not contain

1889 ** the specified term or any terms for which it is a prefix. However, if the

1890 ** segment does contain any such terms, they are stored within the identified

1891 ** range. Because this function only inspects interior segment nodes (and

1892 ** never loads leaf nodes into memory), it is not possible to be sure.

1893 **

1894 ** If an error occurs, an error code other than SQLITE_OK is returned.

1895 */

1896 static int fts3SelectLeaf(

1897 Fts3Table p, / Virtual table handle */

1898 const char zTerm, / Term to select leaves for */

1899 int nTerm, /* Size of term zTerm in bytes */

1900 const char zNode, / Buffer containing segment interior node */

1901 int nNode, /* Size of buffer at zNode */

1902 sqlite3_int64 piLeaf, / Selected leaf node */

1903 sqlite3_int64 piLeaf2 / Selected leaf node */

1904 ){

1905 int rc = SQLITE_OK; /* Return code */

1906 int iHeight; /* Height of this node in tree */

1907

1908 assert( piLeaf \|\| piLeaf2 );

1909

1910 fts3GetVarint32(zNode, &iHeight);

1911 rc = fts3ScanInteriorNode(zTerm, nTerm, zNode, nNode, piLeaf, piLeaf2);

1912 assert( !piLeaf2 \|\| !piLeaf \|\| rc!=SQLITE_OK \|\| (piLeaf<=piLeaf2) );

1913

1914 if( rc==SQLITE_OK && iHeight>1 ){

1915 char zBlob = 0; / Blob read from %_segments table */

1916 int nBlob = 0; /* Size of zBlob in bytes */

1917

1918 if( piLeaf && piLeaf2 && (piLeaf!=piLeaf2) ){

1919 rc = sqlite3Fts3ReadBlock(p, *piLeaf, &zBlob, &nBlob, 0);

1920 if( rc==SQLITE_OK ){

1921 rc = fts3SelectLeaf(p, zTerm, nTerm, zBlob, nBlob, piLeaf, 0);

1922 }

1923 sqlite3_free(zBlob);

1924 piLeaf = 0;

1925 zBlob = 0;

1926 }

1927

1928 if( rc==SQLITE_OK ){

1929 rc = sqlite3Fts3ReadBlock(p, piLeaf?piLeaf:piLeaf2, &zBlob, &nBlob, 0);

1930 }

1931 if( rc==SQLITE_OK ){

1932 rc = fts3SelectLeaf(p, zTerm, nTerm, zBlob, nBlob, piLeaf, piLeaf2);

1933 }

1934 sqlite3_free(zBlob);

1935 }

1936

1937 return rc;

1938 }

1939

1940 /*

1941 ** This function is used to create delta-encoded serialized lists of FTS3

1942 ** varints. Each call to this function appends a single varint to a list.

1943 */

1944 static void fts3PutDeltaVarint(

1945 char *pp, / IN/OUT: Output pointer */

1946 sqlite3_int64 piPrev, / IN/OUT: Previous value written to list */

1947 sqlite3_int64 iVal /* Write this value to the list */

1948 ){

1949 assert( iVal-piPrev > 0 \|\| (piPrev==0 && iVal==0) );

1950 pp += sqlite3Fts3PutVarint(pp, iVal-*piPrev);

1951 *piPrev = iVal;

1952 }

1953

1954 /*

1955 ** When this function is called, *ppPoslist is assumed to point to the

1956 ** start of a position-list. After it returns, *ppPoslist points to the

1957 ** first byte after the position-list.

1958 **

1959 ** A position list is list of positions (delta encoded) and columns for

1960 ** a single document record of a doclist. So, in other words, this

1961 ** routine advances *ppPoslist so that it points to the next docid in

1962 ** the doclist, or to the first byte past the end of the doclist.

1963 **

1964 ** If pp is not NULL, then the contents of the position list are copied

1965 ** to pp. pp is set to point to the first byte past the last byte copied

1966 ** before this function returns.

1967 */

1968 static void fts3PoslistCopy(char pp, char ppPoslist){

1969 char pEnd = ppPoslist;

1970 char c = 0;

1971

1972 /* The end of a position list is marked by a zero encoded as an FTS3

1973 ** varint. A single POS_END (0) byte. Except, if the 0 byte is preceded by

1974 ** a byte with the 0x80 bit set, then it is not a varint 0, but the tail

1975 ** of some other, multi-byte, value.

1976 **

1977 ** The following while-loop moves pEnd to point to the first byte that is not

1978 ** immediately preceded by a byte with the 0x80 bit set. Then increments

1979 ** pEnd once more so that it points to the byte immediately following the

1980 ** last byte in the position-list.

1981 */

1982 while( *pEnd \| c ){

1983 c = *pEnd++ & 0x80;

1984 testcase( c!=0 && (*pEnd)==0 );

1985 }

1986 pEnd++; /* Advance past the POS_END terminator byte */

1987

1988 if( pp ){

1989 int n = (int)(pEnd - *ppPoslist);

1990 char p = pp;

1991 memcpy(p, *ppPoslist, n);

1992 p += n;

1993 *pp = p;

1994 }

1995 *ppPoslist = pEnd;

1996 }

1997

1998 /*

1999 ** When this function is called, *ppPoslist is assumed to point to the

2000 ** start of a column-list. After it returns, *ppPoslist points to the

2001 ** to the terminator (POS_COLUMN or POS_END) byte of the column-list.

2002 **

2003 ** A column-list is list of delta-encoded positions for a single column

2004 ** within a single document within a doclist.

2005 **

2006 ** The column-list is terminated either by a POS_COLUMN varint (1) or

2007 ** a POS_END varint (0). This routine leaves *ppPoslist pointing to

2008 ** the POS_COLUMN or POS_END that terminates the column-list.

2009 **

2010 ** If pp is not NULL, then the contents of the column-list are copied

2011 ** to pp. pp is set to point to the first byte past the last byte copied

2012 ** before this function returns. The POS_COLUMN or POS_END terminator

2013 ** is not copied into *pp.

2014 */

2015 static void fts3ColumnlistCopy(char pp, char ppPoslist){

2016 char pEnd = ppPoslist;

2017 char c = 0;

2018

2019 /* A column-list is terminated by either a 0x01 or 0x00 byte that is

2020 ** not part of a multi-byte varint.

2021 */

2022 while( 0xFE & (*pEnd \| c) ){

2023 c = *pEnd++ & 0x80;

2024 testcase( c!=0 && ((*pEnd)&0xfe)==0 );

2025 }

2026 if( pp ){

2027 int n = (int)(pEnd - *ppPoslist);

2028 char p = pp;

2029 memcpy(p, *ppPoslist, n);

2030 p += n;

2031 *pp = p;

2032 }

2033 *ppPoslist = pEnd;

2034 }

2035

2036 /*

2037 ** Value used to signify the end of an position-list. This is safe because

2038 ** it is not possible to have a document with 2^31 terms.

2039 */

2040 #define POSITION_LIST_END 0x7fffffff

2041

2042 /*

2043 ** This function is used to help parse position-lists. When this function is

2044 ** called, *pp may point to the start of the next varint in the position-list

2045 ** being parsed, or it may point to 1 byte past the end of the position-list

2046 (in which case pp will be a terminator bytes POS_END (0) or

2047 ** (1)).

2048 **

2049 ** If pp points past the end of the current position-list, set pi to

2050 ** POSITION_LIST_END and return. Otherwise, read the next varint from *pp,

2051 ** increment the current value of pi by the value read, and set pp to

2052 ** point to the next value before returning.

2053 **

2054 ** Before calling this routine *pi must be initialized to the value of

2055 ** the previous position, or zero if we are reading the first position

2056 ** in the position-list. Because positions are delta-encoded, the value

2057 ** of the previous position is needed in order to compute the value of

2058 ** the next position.

2059 */

2060 static void fts3ReadNextPos(

2061 char *pp, / IN/OUT: Pointer into position-list buffer */

2062 sqlite3_int64 pi / IN/OUT: Value read from position-list */

2063 ){

2064 if( (**pp)&0xFE ){

2065 fts3GetDeltaVarint(pp, pi);

2066 *pi -= 2;

2067 }else{

2068 *pi = POSITION_LIST_END;

2069 }

2070 }

2071

2072 /*

2073 ** If parameter iCol is not 0, write an POS_COLUMN (1) byte followed by

2074 ** the value of iCol encoded as a varint to *pp. This will start a new

2075 ** column list.

2076 **

2077 ** Set *pp to point to the byte just after the last byte written before

2078 ** returning (do not modify it if iCol==0). Return the total number of bytes

2079 ** written (0 if iCol==0).

2080 */

2081 static int fts3PutColNumber(char **pp, int iCol){

2082 int n = 0; /* Number of bytes written */

2083 if( iCol ){

2084 char p = pp; /* Output pointer */

2085 n = 1 + sqlite3Fts3PutVarint(&p[1], iCol);

2086 *p = 0x01;

2087 *pp = &p[n];

2088 }

2089 return n;

2090 }

2091

2092 /*

2093 ** Compute the union of two position lists. The output written

2094 ** into pp contains all positions of both pp1 and *pp2 in sorted

2095 ** order and with any duplicates removed. All pointers are

2096 ** updated appropriately. The caller is responsible for insuring

2097 ** that there is enough space in *pp to hold the complete output.

2098 */

2099 static void fts3PoslistMerge(

2100 char *pp, / Output buffer */

2101 char *pp1, / Left input list */

2102 char *pp2 / Right input list */

2103 ){

2104 char p = pp;

2105 char p1 = pp1;

2106 char p2 = pp2;

2107

2108 while( p1 \|\| p2 ){

2109 int iCol1; /* The current column index in pp1 */

2110 int iCol2; /* The current column index in pp2 */

2111

2112 if( *p1==POS_COLUMN ) fts3GetVarint32(&p1[1], &iCol1);

2113 else if( *p1==POS_END ) iCol1 = POSITION_LIST_END;

2114 else iCol1 = 0;

2115

2116 if( *p2==POS_COLUMN ) fts3GetVarint32(&p2[1], &iCol2);

2117 else if( *p2==POS_END ) iCol2 = POSITION_LIST_END;

2118 else iCol2 = 0;

2119

2120 if( iCol1==iCol2 ){

2121 sqlite3_int64 i1 = 0; /* Last position from pp1 */

2122 sqlite3_int64 i2 = 0; /* Last position from pp2 */

2123 sqlite3_int64 iPrev = 0;

2124 int n = fts3PutColNumber(&p, iCol1);

2125 p1 += n;

2126 p2 += n;

2127

2128 /* At this point, both p1 and p2 point to the start of column-lists

2129 ** for the same column (the column with index iCol1 and iCol2).

2130 ** A column-list is a list of non-negative delta-encoded varints, each

2131 ** incremented by 2 before being stored. Each list is terminated by a

2132 ** POS_END (0) or POS_COLUMN (1). The following block merges the two lists

2133 ** and writes the results to buffer p. p is left pointing to the byte

2134 ** after the list written. No terminator (POS_END or POS_COLUMN) is

2135 ** written to the output.

2136 */

2137 fts3GetDeltaVarint(&p1, &i1);

2138 fts3GetDeltaVarint(&p2, &i2);

2139 do {

2140 fts3PutDeltaVarint(&p, &iPrev, (i1<i2) ? i1 : i2);

2141 iPrev -= 2;

2142 if( i1==i2 ){

2143 fts3ReadNextPos(&p1, &i1);

2144 fts3ReadNextPos(&p2, &i2);

2145 }else if( i1<i2 ){

2146 fts3ReadNextPos(&p1, &i1);

2147 }else{

2148 fts3ReadNextPos(&p2, &i2);

2149 }

2150 }while( i1!=POSITION_LIST_END \|\| i2!=POSITION_LIST_END );

2151 }else if( iCol1<iCol2 ){

2152 p1 += fts3PutColNumber(&p, iCol1);

2153 fts3ColumnlistCopy(&p, &p1);

2154 }else{

2155 p2 += fts3PutColNumber(&p, iCol2);

2156 fts3ColumnlistCopy(&p, &p2);

2157 }

2158 }

2159

2160 *p++ = POS_END;

2161 *pp = p;

2162 *pp1 = p1 + 1;

2163 *pp2 = p2 + 1;

2164 }

2165

2166 /*

2167 ** This function is used to merge two position lists into one. When it is

2168 ** called, pp1 and pp2 must both point to position lists. A position-list is

2169 ** the part of a doclist that follows each document id. For example, if a row

2170 ** contains:

2171 **

2172 ** 'a b c'\|'x y z'\|'a b b a'

2173 **

2174 ** Then the position list for this row for token 'b' would consist of:

2175 **

2176 ** 0x02 0x01 0x02 0x03 0x03 0x00

2177 **

2178 ** When this function returns, both pp1 and pp2 are left pointing to the

2179 ** byte following the 0x00 terminator of their respective position lists.

2180 **

2181 ** If isSaveLeft is 0, an entry is added to the output position list for

2182 ** each position in *pp2 for which there exists one or more positions in

2183 ** pp1 so that (pos(pp2)>pos(pp1) && pos(pp2)-pos(*pp1)<=nToken). i.e.

2184 ** when the pp1 token appears before the pp2 token, but not more than nToken

2185 ** slots before it.

2186 **

2187 ** e.g. nToken==1 searches for adjacent positions.

2188 */

2189 static int fts3PoslistPhraseMerge(

2190 char *pp, / IN/OUT: Preallocated output buffer */

2191 int nToken, /* Maximum difference in token positions */

2192 int isSaveLeft, /* Save the left position */

2193 int isExact, /* If pp1 is exactly nTokens before pp2 */

2194 char *pp1, / IN/OUT: Left input list */

2195 char *pp2 / IN/OUT: Right input list */

2196 ){

2197 char p = pp;

2198 char p1 = pp1;

2199 char p2 = pp2;

2200 int iCol1 = 0;

2201 int iCol2 = 0;

2202

2203 /* Never set both isSaveLeft and isExact for the same invocation. */

2204 assert( isSaveLeft==0 \|\| isExact==0 );

2205

2206 assert( p!=0 && p1!=0 && p2!=0 );

2207 if( *p1==POS_COLUMN ){

2208 p1++;

2209 p1 += fts3GetVarint32(p1, &iCol1);

2210 }

2211 if( *p2==POS_COLUMN ){

2212 p2++;

2213 p2 += fts3GetVarint32(p2, &iCol2);

2214 }

2215

2216 while( 1 ){

2217 if( iCol1==iCol2 ){

2218 char *pSave = p;

2219 sqlite3_int64 iPrev = 0;

2220 sqlite3_int64 iPos1 = 0;

2221 sqlite3_int64 iPos2 = 0;

2222

2223 if( iCol1 ){

2224 *p++ = POS_COLUMN;

2225 p += sqlite3Fts3PutVarint(p, iCol1);

2226 }

2227

2228 assert( p1!=POS_END && p1!=POS_COLUMN );

2229 assert( p2!=POS_END && p2!=POS_COLUMN );

2230 fts3GetDeltaVarint(&p1, &iPos1); iPos1 -= 2;

2231 fts3GetDeltaVarint(&p2, &iPos2); iPos2 -= 2;

2232

2233 while( 1 ){

2234 if( iPos2==iPos1+nToken

2235 \|\| (isExact==0 && iPos2>iPos1 && iPos2<=iPos1+nToken)

2236 ){

2237 sqlite3_int64 iSave;

2238 iSave = isSaveLeft ? iPos1 : iPos2;

2239 fts3PutDeltaVarint(&p, &iPrev, iSave+2); iPrev -= 2;

2240 pSave = 0;

2241 assert( p );

2242 }

2243 if( (!isSaveLeft && iPos2<=(iPos1+nToken)) \|\| iPos2<=iPos1 ){

2244 if( (*p2&0xFE)==0 ) break;

2245 fts3GetDeltaVarint(&p2, &iPos2); iPos2 -= 2;

2246 }else{

2247 if( (*p1&0xFE)==0 ) break;

2248 fts3GetDeltaVarint(&p1, &iPos1); iPos1 -= 2;

2249 }

2250 }

2251

2252 if( pSave ){

2253 assert( pp && p );

2254 p = pSave;

2255 }

2256

2257 fts3ColumnlistCopy(0, &p1);

2258 fts3ColumnlistCopy(0, &p2);

2259 assert( (p1&0xFE)==0 && (p2&0xFE)==0 );

2260 if( 0==p1 \|\| 0==p2 ) break;

2261

2262 p1++;

2263 p1 += fts3GetVarint32(p1, &iCol1);

2264 p2++;

2265 p2 += fts3GetVarint32(p2, &iCol2);

2266 }

2267

2268 /* Advance pointer p1 or p2 (whichever corresponds to the smaller of

2269 ** iCol1 and iCol2) so that it points to either the 0x00 that marks the

2270 ** end of the position list, or the 0x01 that precedes the next

2271 ** column-number in the position list.

2272 */

2273 else if( iCol1<iCol2 ){

2274 fts3ColumnlistCopy(0, &p1);

2275 if( 0==*p1 ) break;

2276 p1++;

2277 p1 += fts3GetVarint32(p1, &iCol1);

2278 }else{

2279 fts3ColumnlistCopy(0, &p2);

2280 if( 0==*p2 ) break;

2281 p2++;

2282 p2 += fts3GetVarint32(p2, &iCol2);

2283 }

2284 }

2285

2286 fts3PoslistCopy(0, &p2);

2287 fts3PoslistCopy(0, &p1);

2288 *pp1 = p1;

2289 *pp2 = p2;

2290 if( *pp==p ){

2291 return 0;

2292 }

2293 *p++ = 0x00;

2294 *pp = p;

2295 return 1;

2296 }

2297

2298 /*

2299 ** Merge two position-lists as required by the NEAR operator. The argument

2300 ** position lists correspond to the left and right phrases of an expression

2301 ** like:

2302 **

2303 ** "phrase 1" NEAR "phrase number 2"

2304 **

2305 ** Position list *pp1 corresponds to the left-hand side of the NEAR

2306 ** expression and *pp2 to the right. As usual, the indexes in the position

2307 ** lists are the offsets of the last token in each phrase (tokens "1" and "2"

2308 ** in the example above).

2309 **

2310 ** The output position list - written to pp - is a copy of pp2 with those

2311 ** entries that are not sufficiently NEAR entries in *pp1 removed.

2312 */

2313 static int fts3PoslistNearMerge(

2314 char *pp, / Output buffer */

2315 char aTmp, / Temporary buffer space */

2316 int nRight, /* Maximum difference in token positions */

2317 int nLeft, /* Maximum difference in token positions */

2318 char *pp1, / IN/OUT: Left input list */

2319 char *pp2 / IN/OUT: Right input list */

2320 ){

2321 char p1 = pp1;

2322 char p2 = pp2;

2323

2324 char *pTmp1 = aTmp;

2325 char *pTmp2;

2326 char *aTmp2;

2327 int res = 1;

2328

2329 fts3PoslistPhraseMerge(&pTmp1, nRight, 0, 0, pp1, pp2);

2330 aTmp2 = pTmp2 = pTmp1;

2331 *pp1 = p1;

2332 *pp2 = p2;

2333 fts3PoslistPhraseMerge(&pTmp2, nLeft, 1, 0, pp2, pp1);

2334 if( pTmp1!=aTmp && pTmp2!=aTmp2 ){

2335 fts3PoslistMerge(pp, &aTmp, &aTmp2);

2336 }else if( pTmp1!=aTmp ){

2337 fts3PoslistCopy(pp, &aTmp);

2338 }else if( pTmp2!=aTmp2 ){

2339 fts3PoslistCopy(pp, &aTmp2);

2340 }else{

2341 res = 0;

2342 }

2343

2344 return res;

2345 }

2346

2347 /*

2348 ** An instance of this function is used to merge together the (potentially

2349 ** large number of) doclists for each term that matches a prefix query.

2350 ** See function fts3TermSelectMerge() for details.

2351 */

2352 typedef struct TermSelect TermSelect;

2353 struct TermSelect {

2354 char aaOutput[16]; / Malloc'd output buffers */

2355 int anOutput[16]; /* Size each output buffer in bytes */

2356 };

2357

2358 /*

2359 ** This function is used to read a single varint from a buffer. Parameter

2360 ** pEnd points 1 byte past the end of the buffer. When this function is

2361 ** called, if *pp points to pEnd or greater, then the end of the buffer

2362 ** has been reached. In this case *pp is set to 0 and the function returns.

2363 **

2364 ** If *pp does not point to or past pEnd, then a single varint is read

2365 ** from pp. pp is then set to point 1 byte past the end of the read varint.

2366 **

2367 ** If bDescIdx is false, the value read is added to *pVal before returning.

2368 ** If it is true, the value read is subtracted from *pVal before this

2369 ** function returns.

2370 */

2371 static void fts3GetDeltaVarint3(

2372 char *pp, / IN/OUT: Point to read varint from */

2373 char pEnd, / End of buffer */

2374 int bDescIdx, /* True if docids are descending */

2375 sqlite3_int64 pVal / IN/OUT: Integer value */

2376 ){

2377 if( *pp>=pEnd ){

2378 *pp = 0;

2379 }else{

2380 sqlite3_int64 iVal;

2381 pp += sqlite3Fts3GetVarint(pp, &iVal);

2382 if( bDescIdx ){

2383 *pVal -= iVal;

2384 }else{

2385 *pVal += iVal;

2386 }

2387 }

2388 }

2389

2390 /*

2391 ** This function is used to write a single varint to a buffer. The varint

2392 ** is written to pp. Before returning, pp is set to point 1 byte past the

2393 ** end of the value written.

2394 **

2395 ** If *pbFirst is zero when this function is called, the value written to

2396 ** the buffer is that of parameter iVal.

2397 **

2398 ** If *pbFirst is non-zero when this function is called, then the value

2399 ** written is either (iVal-piPrev) (if bDescIdx is zero) or (piPrev-iVal)

2400 ** (if bDescIdx is non-zero).

2401 **

2402 ** Before returning, this function always sets pbFirst to 1 and piPrev

2403 ** to the value of parameter iVal.

2404 */

2405 static void fts3PutDeltaVarint3(

2406 char *pp, / IN/OUT: Output pointer */

2407 int bDescIdx, /* True for descending docids */

2408 sqlite3_int64 piPrev, / IN/OUT: Previous value written to list */

2409 int pbFirst, / IN/OUT: True after first int written */

2410 sqlite3_int64 iVal /* Write this value to the list */

2411 ){

2412 sqlite3_int64 iWrite;

2413 if( bDescIdx==0 \|\| *pbFirst==0 ){

2414 iWrite = iVal - *piPrev;

2415 }else{

2416 iWrite = *piPrev - iVal;

2417 }

2418 assert( pbFirst \|\| piPrev==0 );

2419 assert( *pbFirst==0 \|\| iWrite>0 );

2420 pp += sqlite3Fts3PutVarint(pp, iWrite);

2421 *piPrev = iVal;

2422 *pbFirst = 1;

2423 }

2424

2425

2426 /*

2427 ** This macro is used by various functions that merge doclists. The two

2428 ** arguments are 64-bit docid values. If the value of the stack variable

2429 ** bDescDoclist is 0 when this macro is invoked, then it returns (i1-i2).

2430 ** Otherwise, (i2-i1).

2431 **

2432 ** Using this makes it easier to write code that can merge doclists that are

2433 ** sorted in either ascending or descending order.

2434 */

2435 #define DOCID_CMP(i1, i2) ((bDescDoclist?-1:1) * (i1-i2))

2436

2437 /*

2438 ** This function does an "OR" merge of two doclists (output contains all

2439 ** positions contained in either argument doclist). If the docids in the

2440 ** input doclists are sorted in ascending order, parameter bDescDoclist

2441 ** should be false. If they are sorted in ascending order, it should be

2442 ** passed a non-zero value.

2443 **

2444 ** If no error occurs, *paOut is set to point at an sqlite3_malloc'd buffer

2445 ** containing the output doclist and SQLITE_OK is returned. In this case

2446 ** *pnOut is set to the number of bytes in the output doclist.

2447 **

2448 ** If an error occurs, an SQLite error code is returned. The output values

2449 ** are undefined in this case.

2450 */

2451 static int fts3DoclistOrMerge(

2452 int bDescDoclist, /* True if arguments are desc */

2453 char a1, int n1, / First doclist */

2454 char a2, int n2, / Second doclist */

2455 char *paOut, int pnOut /* OUT: Malloc'd doclist */

2456 ){

2457 sqlite3_int64 i1 = 0;

2458 sqlite3_int64 i2 = 0;

2459 sqlite3_int64 iPrev = 0;

2460 char *pEnd1 = &a1[n1];

2461 char *pEnd2 = &a2[n2];

2462 char *p1 = a1;

2463 char *p2 = a2;

2464 char *p;

2465 char *aOut;

2466 int bFirstOut = 0;

2467

2468 *paOut = 0;

2469 *pnOut = 0;

2470

2471 /* Allocate space for the output. Both the input and output doclists

2472 ** are delta encoded. If they are in ascending order (bDescDoclist==0),

2473 ** then the first docid in each list is simply encoded as a varint. For

2474 ** each subsequent docid, the varint stored is the difference between the

2475 ** current and previous docid (a positive number - since the list is in

2476 ** ascending order).

2477 **

2478 ** The first docid written to the output is therefore encoded using the

2479 ** same number of bytes as it is in whichever of the input lists it is

2480 ** read from. And each subsequent docid read from the same input list

2481 ** consumes either the same or less bytes as it did in the input (since

2482 ** the difference between it and the previous value in the output must

2483 ** be a positive value less than or equal to the delta value read from

2484 ** the input list). The same argument applies to all but the first docid

2485 ** read from the 'other' list. And to the contents of all position lists

2486 ** that will be copied and merged from the input to the output.

2487 **

2488 ** However, if the first docid copied to the output is a negative number,

2489 ** then the encoding of the first docid from the 'other' input list may

2490 ** be larger in the output than it was in the input (since the delta value

2491 ** may be a larger positive integer than the actual docid).

2492 **

2493 ** The space required to store the output is therefore the sum of the

2494 ** sizes of the two inputs, plus enough space for exactly one of the input

2495 ** docids to grow.

2496 **

2497 ** A symetric argument may be made if the doclists are in descending

2498 ** order.

2499 */

2500 aOut = sqlite3_malloc(n1+n2+FTS3_VARINT_MAX-1);

2501 if( !aOut ) return SQLITE_NOMEM;

2502

2503 p = aOut;

2504 fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1);

2505 fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2);

2506 while( p1 \|\| p2 ){

2507 sqlite3_int64 iDiff = DOCID_CMP(i1, i2);

2508

2509 if( p2 && p1 && iDiff==0 ){

2510 fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i1);

2511 fts3PoslistMerge(&p, &p1, &p2);

2512 fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);

2513 fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);

2514 }else if( !p2 \|\| (p1 && iDiff<0) ){

2515 fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i1);

2516 fts3PoslistCopy(&p, &p1);

2517 fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);

2518 }else{

2519 fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i2);

2520 fts3PoslistCopy(&p, &p2);

2521 fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);

2522 }

2523 }

2524

2525 *paOut = aOut;

2526 *pnOut = (int)(p-aOut);

2527 assert( *pnOut<=n1+n2+FTS3_VARINT_MAX-1 );

2528 return SQLITE_OK;

2529 }

2530

2531 /*

2532 ** This function does a "phrase" merge of two doclists. In a phrase merge,

2533 ** the output contains a copy of each position from the right-hand input

2534 ** doclist for which there is a position in the left-hand input doclist

2535 ** exactly nDist tokens before it.

2536 **

2537 ** If the docids in the input doclists are sorted in ascending order,

2538 ** parameter bDescDoclist should be false. If they are sorted in ascending

2539 ** order, it should be passed a non-zero value.

2540 **

2541 ** The right-hand input doclist is overwritten by this function.

2542 */

2543 static int fts3DoclistPhraseMerge(

2544 int bDescDoclist, /* True if arguments are desc */

2545 int nDist, /* Distance from left to right (1=adjacent) */

2546 char aLeft, int nLeft, / Left doclist */

2547 char *paRight, int pnRight /* IN/OUT: Right/output doclist */

2548 ){

2549 sqlite3_int64 i1 = 0;

2550 sqlite3_int64 i2 = 0;

2551 sqlite3_int64 iPrev = 0;

2552 char aRight = paRight;

2553 char *pEnd1 = &aLeft[nLeft];

2554 char pEnd2 = &aRight[pnRight];

2555 char *p1 = aLeft;

2556 char *p2 = aRight;

2557 char *p;

2558 int bFirstOut = 0;

2559 char *aOut;

2560

2561 assert( nDist>0 );

2562 if( bDescDoclist ){

2563 aOut = sqlite3_malloc(*pnRight + FTS3_VARINT_MAX);

2564 if( aOut==0 ) return SQLITE_NOMEM;

2565 }else{

2566 aOut = aRight;

2567 }

2568 p = aOut;

2569

2570 fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1);

2571 fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2);

2572

2573 while( p1 && p2 ){

2574 sqlite3_int64 iDiff = DOCID_CMP(i1, i2);

2575 if( iDiff==0 ){

2576 char *pSave = p;

2577 sqlite3_int64 iPrevSave = iPrev;

2578 int bFirstOutSave = bFirstOut;

2579

2580 fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i1);

2581 if( 0==fts3PoslistPhraseMerge(&p, nDist, 0, 1, &p1, &p2) ){

2582 p = pSave;

2583 iPrev = iPrevSave;

2584 bFirstOut = bFirstOutSave;

2585 }

2586 fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);

2587 fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);

2588 }else if( iDiff<0 ){

2589 fts3PoslistCopy(0, &p1);

2590 fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);

2591 }else{

2592 fts3PoslistCopy(0, &p2);

2593 fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);

2594 }

2595 }

2596

2597 *pnRight = (int)(p - aOut);

2598 if( bDescDoclist ){

2599 sqlite3_free(aRight);

2600 *paRight = aOut;

2601 }

2602

2603 return SQLITE_OK;

2604 }

2605

2606 /*

2607 ** Argument pList points to a position list nList bytes in size. This

2608 ** function checks to see if the position list contains any entries for

2609 ** a token in position 0 (of any column). If so, it writes argument iDelta

2610 ** to the output buffer pOut, followed by a position list consisting only

2611 ** of the entries from pList at position 0, and terminated by an 0x00 byte.

2612 ** The value returned is the number of bytes written to pOut (if any).

2613 */

2614 int sqlite3Fts3FirstFilter(

2615 sqlite3_int64 iDelta, /* Varint that may be written to pOut */

2616 char pList, / Position list (no 0x00 term) */

2617 int nList, /* Size of pList in bytes */

2618 char pOut / Write output here */

2619 ){

2620 int nOut = 0;

2621 int bWritten = 0; /* True once iDelta has been written */

2622 char *p = pList;

2623 char *pEnd = &pList[nList];

2624

2625 if( *p!=0x01 ){

2626 if( *p==0x02 ){

2627 nOut += sqlite3Fts3PutVarint(&pOut[nOut], iDelta);

2628 pOut[nOut++] = 0x02;

2629 bWritten = 1;

2630 }

2631 fts3ColumnlistCopy(0, &p);

2632 }

2633

2634 while( p<pEnd && *p==0x01 ){

2635 sqlite3_int64 iCol;

2636 p++;

2637 p += sqlite3Fts3GetVarint(p, &iCol);

2638 if( *p==0x02 ){

2639 if( bWritten==0 ){

2640 nOut += sqlite3Fts3PutVarint(&pOut[nOut], iDelta);

2641 bWritten = 1;

2642 }

2643 pOut[nOut++] = 0x01;

2644 nOut += sqlite3Fts3PutVarint(&pOut[nOut], iCol);

2645 pOut[nOut++] = 0x02;

2646 }

2647 fts3ColumnlistCopy(0, &p);

2648 }

2649 if( bWritten ){

2650 pOut[nOut++] = 0x00;

2651 }

2652

2653 return nOut;

2654 }

2655

2656

2657 /*

2658 ** Merge all doclists in the TermSelect.aaOutput[] array into a single

2659 ** doclist stored in TermSelect.aaOutput[0]. If successful, delete all

2660 ** other doclists (except the aaOutput[0] one) and return SQLITE_OK.

2661 **

2662 ** If an OOM error occurs, return SQLITE_NOMEM. In this case it is

2663 ** the responsibility of the caller to free any doclists left in the

2664 ** TermSelect.aaOutput[] array.

2665 */

2666 static int fts3TermSelectFinishMerge(Fts3Table p, TermSelect pTS){

2667 char *aOut = 0;

2668 int nOut = 0;

2669 int i;

2670

2671 /* Loop through the doclists in the aaOutput[] array. Merge them all

2672 ** into a single doclist.

2673 */

2674 for(i=0; i<SizeofArray(pTS->aaOutput); i++){

2675 if( pTS->aaOutput[i] ){

2676 if( !aOut ){

2677 aOut = pTS->aaOutput[i];

2678 nOut = pTS->anOutput[i];

2679 pTS->aaOutput[i] = 0;

2680 }else{

2681 int nNew;

2682 char *aNew;

2683

2684 int rc = fts3DoclistOrMerge(p->bDescIdx,

2685 pTS->aaOutput[i], pTS->anOutput[i], aOut, nOut, &aNew, &nNew

2686 );

2687 if( rc!=SQLITE_OK ){

2688 sqlite3_free(aOut);

2689 return rc;

2690 }

2691

2692 sqlite3_free(pTS->aaOutput[i]);

2693 sqlite3_free(aOut);

2694 pTS->aaOutput[i] = 0;

2695 aOut = aNew;

2696 nOut = nNew;

2697 }

2698 }

2699 }

2700

2701 pTS->aaOutput[0] = aOut;

2702 pTS->anOutput[0] = nOut;

2703 return SQLITE_OK;

2704 }

2705

2706 /*

2707 ** Merge the doclist aDoclist/nDoclist into the TermSelect object passed

2708 ** as the first argument. The merge is an "OR" merge (see function

2709 ** fts3DoclistOrMerge() for details).

2710 **

2711 ** This function is called with the doclist for each term that matches

2712 ** a queried prefix. It merges all these doclists into one, the doclist

2713 ** for the specified prefix. Since there can be a very large number of

2714 ** doclists to merge, the merging is done pair-wise using the TermSelect

2715 ** object.

2716 **

2717 ** This function returns SQLITE_OK if the merge is successful, or an

2718 ** SQLite error code (SQLITE_NOMEM) if an error occurs.

2719 */

2720 static int fts3TermSelectMerge(

2721 Fts3Table p, / FTS table handle */

2722 TermSelect pTS, / TermSelect object to merge into */

2723 char aDoclist, / Pointer to doclist */

2724 int nDoclist /* Size of aDoclist in bytes */

2725 ){

2726 if( pTS->aaOutput[0]==0 ){

2727 /* If this is the first term selected, copy the doclist to the output

2728 ** buffer using memcpy().

2729 **

2730 ** Add FTS3_VARINT_MAX bytes of unused space to the end of the

2731 ** allocation. This is so as to ensure that the buffer is big enough

2732 ** to hold the current doclist AND'd with any other doclist. If the

2733 ** doclists are stored in order=ASC order, this padding would not be

2734 ** required (since the size of [doclistA AND doclistB] is always less

2735 ** than or equal to the size of [doclistA] in that case). But this is

2736 ** not true for order=DESC. For example, a doclist containing (1, -1)

2737 ** may be smaller than (-1), as in the first example the -1 may be stored

2738 ** as a single-byte delta, whereas in the second it must be stored as a

2739 ** FTS3_VARINT_MAX byte varint.

2740 **

2741 ** Similar padding is added in the fts3DoclistOrMerge() function.

2742 */

2743 pTS->aaOutput[0] = sqlite3_malloc(nDoclist + FTS3_VARINT_MAX + 1);

2744 pTS->anOutput[0] = nDoclist;

2745 if( pTS->aaOutput[0] ){

2746 memcpy(pTS->aaOutput[0], aDoclist, nDoclist);

2747 }else{

2748 return SQLITE_NOMEM;

2749 }

2750 }else{

2751 char *aMerge = aDoclist;

2752 int nMerge = nDoclist;

2753 int iOut;

2754

2755 for(iOut=0; iOut<SizeofArray(pTS->aaOutput); iOut++){

2756 if( pTS->aaOutput[iOut]==0 ){

2757 assert( iOut>0 );

2758 pTS->aaOutput[iOut] = aMerge;

2759 pTS->anOutput[iOut] = nMerge;

2760 break;

2761 }else{

2762 char *aNew;

2763 int nNew;

2764

2765 int rc = fts3DoclistOrMerge(p->bDescIdx, aMerge, nMerge,

2766 pTS->aaOutput[iOut], pTS->anOutput[iOut], &aNew, &nNew

2767 );

2768 if( rc!=SQLITE_OK ){

2769 if( aMerge!=aDoclist ) sqlite3_free(aMerge);

2770 return rc;

2771 }

2772

2773 if( aMerge!=aDoclist ) sqlite3_free(aMerge);

2774 sqlite3_free(pTS->aaOutput[iOut]);

2775 pTS->aaOutput[iOut] = 0;

2776

2777 aMerge = aNew;

2778 nMerge = nNew;

2779 if( (iOut+1)==SizeofArray(pTS->aaOutput) ){

2780 pTS->aaOutput[iOut] = aMerge;

2781 pTS->anOutput[iOut] = nMerge;

2782 }

2783 }

2784 }

2785 }

2786 return SQLITE_OK;

2787 }

2788

2789 /*

2790 ** Append SegReader object pNew to the end of the pCsr->apSegment[] array.

2791 */

2792 static int fts3SegReaderCursorAppend(

2793 Fts3MultiSegReader *pCsr,

2794 Fts3SegReader *pNew

2795 ){

2796 if( (pCsr->nSegment%16)==0 ){

2797 Fts3SegReader **apNew;

2798 int nByte = (pCsr->nSegment + 16)sizeof(Fts3SegReader);

2799 apNew = (Fts3SegReader **)sqlite3_realloc(pCsr->apSegment, nByte);

2800 if( !apNew ){

2801 sqlite3Fts3SegReaderFree(pNew);

2802 return SQLITE_NOMEM;

2803 }

2804 pCsr->apSegment = apNew;

2805 }

2806 pCsr->apSegment[pCsr->nSegment++] = pNew;

2807 return SQLITE_OK;

2808 }

2809

2810 /*

2811 ** Add seg-reader objects to the Fts3MultiSegReader object passed as the

2812 ** 8th argument.

2813 **

2814 ** This function returns SQLITE_OK if successful, or an SQLite error code

2815 ** otherwise.

2816 */

2817 static int fts3SegReaderCursor(

2818 Fts3Table p, / FTS3 table handle */

2819 int iLangid, /* Language id */

2820 int iIndex, /* Index to search (from 0 to p->nIndex-1) */

2821 int iLevel, /* Level of segments to scan */

2822 const char zTerm, / Term to query for */

2823 int nTerm, /* Size of zTerm in bytes */

2824 int isPrefix, /* True for a prefix search */

2825 int isScan, /* True to scan from zTerm to EOF */

2826 Fts3MultiSegReader pCsr / Cursor object to populate */

2827 ){

2828 int rc = SQLITE_OK; /* Error code */

2829 sqlite3_stmt pStmt = 0; / Statement to iterate through segments */

2830 int rc2; /* Result of sqlite3_reset() */

2831

2832 /* If iLevel is less than 0 and this is not a scan, include a seg-reader

2833 ** for the pending-terms. If this is a scan, then this call must be being

2834 ** made by an fts4aux module, not an FTS table. In this case calling

2835 ** Fts3SegReaderPending might segfault, as the data structures used by

2836 ** fts4aux are not completely populated. So it's easiest to filter these

2837 ** calls out here. */

2838 if( iLevel<0 && p->aIndex ){

2839 Fts3SegReader *pSeg = 0;

2840 rc = sqlite3Fts3SegReaderPending(p, iIndex, zTerm, nTerm, isPrefix\|\|isScan, &pSeg);

2841 if( rc==SQLITE_OK && pSeg ){

2842 rc = fts3SegReaderCursorAppend(pCsr, pSeg);

2843 }

2844 }

2845

2846 if( iLevel!=FTS3_SEGCURSOR_PENDING ){

2847 if( rc==SQLITE_OK ){

2848 rc = sqlite3Fts3AllSegdirs(p, iLangid, iIndex, iLevel, &pStmt);

2849 }

2850

2851 while( rc==SQLITE_OK && SQLITE_ROW==(rc = sqlite3_step(pStmt)) ){

2852 Fts3SegReader *pSeg = 0;

2853

2854 /* Read the values returned by the SELECT into local variables. */

2855 sqlite3_int64 iStartBlock = sqlite3_column_int64(pStmt, 1);

2856 sqlite3_int64 iLeavesEndBlock = sqlite3_column_int64(pStmt, 2);

2857 sqlite3_int64 iEndBlock = sqlite3_column_int64(pStmt, 3);

2858 int nRoot = sqlite3_column_bytes(pStmt, 4);

2859 char const *zRoot = sqlite3_column_blob(pStmt, 4);

2860

2861 /* If zTerm is not NULL, and this segment is not stored entirely on its

2862 ** root node, the range of leaves scanned can be reduced. Do this. */

2863 if( iStartBlock && zTerm ){

2864 sqlite3_int64 *pi = (isPrefix ? &iLeavesEndBlock : 0);

2865 rc = fts3SelectLeaf(p, zTerm, nTerm, zRoot, nRoot, &iStartBlock, pi);

2866 if( rc!=SQLITE_OK ) goto finished;

2867 if( isPrefix==0 && isScan==0 ) iLeavesEndBlock = iStartBlock;

2868 }

2869

2870 rc = sqlite3Fts3SegReaderNew(pCsr->nSegment+1,

2871 (isPrefix==0 && isScan==0),

2872 iStartBlock, iLeavesEndBlock,

2873 iEndBlock, zRoot, nRoot, &pSeg

2874 );

2875 if( rc!=SQLITE_OK ) goto finished;

2876 rc = fts3SegReaderCursorAppend(pCsr, pSeg);

2877 }

2878 }

2879

2880 finished:

2881 rc2 = sqlite3_reset(pStmt);

2882 if( rc==SQLITE_DONE ) rc = rc2;

2883

2884 return rc;

2885 }

2886

2887 /*

2888 ** Set up a cursor object for iterating through a full-text index or a

2889 ** single level therein.

2890 */

2891 int sqlite3Fts3SegReaderCursor(

2892 Fts3Table p, / FTS3 table handle */

2893 int iLangid, /* Language-id to search */

2894 int iIndex, /* Index to search (from 0 to p->nIndex-1) */

2895 int iLevel, /* Level of segments to scan */

2896 const char zTerm, / Term to query for */

2897 int nTerm, /* Size of zTerm in bytes */

2898 int isPrefix, /* True for a prefix search */

2899 int isScan, /* True to scan from zTerm to EOF */

2900 Fts3MultiSegReader pCsr / Cursor object to populate */

2901 ){

2902 assert( iIndex>=0 && iIndex<p->nIndex );

2903 assert( iLevel==FTS3_SEGCURSOR_ALL

2904 \|\| iLevel==FTS3_SEGCURSOR_PENDING

2905 \|\| iLevel>=0

2906 );

2907 assert( iLevel<FTS3_SEGDIR_MAXLEVEL );

2908 assert( FTS3_SEGCURSOR_ALL<0 && FTS3_SEGCURSOR_PENDING<0 );

2909 assert( isPrefix==0 \|\| isScan==0 );

2910

2911 memset(pCsr, 0, sizeof(Fts3MultiSegReader));

2912 return fts3SegReaderCursor(

2913 p, iLangid, iIndex, iLevel, zTerm, nTerm, isPrefix, isScan, pCsr

2914 );

2915 }

2916

2917 /*

2918 ** In addition to its current configuration, have the Fts3MultiSegReader

2919 ** passed as the 4th argument also scan the doclist for term zTerm/nTerm.

2920 **

2921 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.

2922 */

2923 static int fts3SegReaderCursorAddZero(

2924 Fts3Table p, / FTS virtual table handle */

2925 int iLangid,

2926 const char zTerm, / Term to scan doclist of */

2927 int nTerm, /* Number of bytes in zTerm */

2928 Fts3MultiSegReader pCsr / Fts3MultiSegReader to modify */

2929 ){

2930 return fts3SegReaderCursor(p,

2931 iLangid, 0, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 0, 0,pCsr

2932 );

2933 }

2934

2935 /*

2936 ** Open an Fts3MultiSegReader to scan the doclist for term zTerm/nTerm. Or,

2937 ** if isPrefix is true, to scan the doclist for all terms for which

2938 ** zTerm/nTerm is a prefix. If successful, return SQLITE_OK and write

2939 ** a pointer to the new Fts3MultiSegReader to *ppSegcsr. Otherwise, return

2940 ** an SQLite error code.

2941 **

2942 ** It is the responsibility of the caller to free this object by eventually

2943 ** passing it to fts3SegReaderCursorFree()

2944 **

2945 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.

2946 ** Output parameter *ppSegcsr is set to 0 if an error occurs.

2947 */

2948 static int fts3TermSegReaderCursor(

2949 Fts3Cursor pCsr, / Virtual table cursor handle */

2950 const char zTerm, / Term to query for */

2951 int nTerm, /* Size of zTerm in bytes */

2952 int isPrefix, /* True for a prefix search */

2953 Fts3MultiSegReader *ppSegcsr / OUT: Allocated seg-reader cursor */

2954 ){

2955 Fts3MultiSegReader pSegcsr; / Object to allocate and return */

2956 int rc = SQLITE_NOMEM; /* Return code */

2957

2958 pSegcsr = sqlite3_malloc(sizeof(Fts3MultiSegReader));

2959 if( pSegcsr ){

2960 int i;

2961 int bFound = 0; /* True once an index has been found */

2962 Fts3Table p = (Fts3Table )pCsr->base.pVtab;

2963

2964 if( isPrefix ){

2965 for(i=1; bFound==0 && i<p->nIndex; i++){

2966 if( p->aIndex[i].nPrefix==nTerm ){

2967 bFound = 1;

2968 rc = sqlite3Fts3SegReaderCursor(p, pCsr->iLangid,

2969 i, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 0, 0, pSegcsr

2970 );

2971 pSegcsr->bLookup = 1;

2972 }

2973 }

2974

2975 for(i=1; bFound==0 && i<p->nIndex; i++){

2976 if( p->aIndex[i].nPrefix==nTerm+1 ){

2977 bFound = 1;

2978 rc = sqlite3Fts3SegReaderCursor(p, pCsr->iLangid,

2979 i, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 1, 0, pSegcsr

2980 );

2981 if( rc==SQLITE_OK ){

2982 rc = fts3SegReaderCursorAddZero(

2983 p, pCsr->iLangid, zTerm, nTerm, pSegcsr

2984 );

2985 }

2986 }

2987 }

2988 }

2989

2990 if( bFound==0 ){

2991 rc = sqlite3Fts3SegReaderCursor(p, pCsr->iLangid,

2992 0, FTS3_SEGCURSOR_ALL, zTerm, nTerm, isPrefix, 0, pSegcsr

2993 );

2994 pSegcsr->bLookup = !isPrefix;

2995 }

2996 }

2997

2998 *ppSegcsr = pSegcsr;

2999 return rc;

3000 }

3001

3002 /*

3003 ** Free an Fts3MultiSegReader allocated by fts3TermSegReaderCursor().

3004 */

3005 static void fts3SegReaderCursorFree(Fts3MultiSegReader *pSegcsr){

3006 sqlite3Fts3SegReaderFinish(pSegcsr);

3007 sqlite3_free(pSegcsr);

3008 }

3009

3010 /*

3011 ** This function retrieves the doclist for the specified term (or term

3012 ** prefix) from the database.

3013 */

3014 static int fts3TermSelect(

3015 Fts3Table p, / Virtual table handle */

3016 Fts3PhraseToken pTok, / Token to query for */

3017 int iColumn, /* Column to query (or -ve for all columns) */

3018 int pnOut, / OUT: Size of buffer at ppOut /

3019 char *ppOut / OUT: Malloced result buffer */

3020 ){

3021 int rc; /* Return code */

3022 Fts3MultiSegReader pSegcsr; / Seg-reader cursor for this term */

3023 TermSelect tsc; /* Object for pair-wise doclist merging */

3024 Fts3SegFilter filter; /* Segment term filter configuration */

3025

3026 pSegcsr = pTok->pSegcsr;

3027 memset(&tsc, 0, sizeof(TermSelect));

3028

3029 filter.flags = FTS3_SEGMENT_IGNORE_EMPTY \| FTS3_SEGMENT_REQUIRE_POS

3030 \| (pTok->isPrefix ? FTS3_SEGMENT_PREFIX : 0)

3031 \| (pTok->bFirst ? FTS3_SEGMENT_FIRST : 0)

3032 \| (iColumn<p->nColumn ? FTS3_SEGMENT_COLUMN_FILTER : 0);

3033 filter.iCol = iColumn;

3034 filter.zTerm = pTok->z;

3035 filter.nTerm = pTok->n;

3036

3037 rc = sqlite3Fts3SegReaderStart(p, pSegcsr, &filter);

3038 while( SQLITE_OK==rc

3039 && SQLITE_ROW==(rc = sqlite3Fts3SegReaderStep(p, pSegcsr))

3040 ){

3041 rc = fts3TermSelectMerge(p, &tsc, pSegcsr->aDoclist, pSegcsr->nDoclist);

3042 }

3043

3044 if( rc==SQLITE_OK ){

3045 rc = fts3TermSelectFinishMerge(p, &tsc);

3046 }

3047 if( rc==SQLITE_OK ){

3048 *ppOut = tsc.aaOutput[0];

3049 *pnOut = tsc.anOutput[0];

3050 }else{

3051 int i;

3052 for(i=0; i<SizeofArray(tsc.aaOutput); i++){

3053 sqlite3_free(tsc.aaOutput[i]);

3054 }

3055 }

3056

3057 fts3SegReaderCursorFree(pSegcsr);

3058 pTok->pSegcsr = 0;

3059 return rc;

3060 }

3061

3062 /*

3063 ** This function counts the total number of docids in the doclist stored

3064 ** in buffer aList[], size nList bytes.

3065 **

3066 ** If the isPoslist argument is true, then it is assumed that the doclist

3067 ** contains a position-list following each docid. Otherwise, it is assumed

3068 ** that the doclist is simply a list of docids stored as delta encoded

3069 ** varints.

3070 */

3071 static int fts3DoclistCountDocids(char *aList, int nList){

3072 int nDoc = 0; /* Return value */

3073 if( aList ){

3074 char aEnd = &aList[nList]; / Pointer to one byte after EOF */

3075 char p = aList; / Cursor */

3076 while( p<aEnd ){

3077 nDoc++;

3078 while( (p++)&0x80 ); / Skip docid varint */

3079 fts3PoslistCopy(0, &p); /* Skip over position list */

3080 }

3081 }

3082

3083 return nDoc;

3084 }

3085

3086 /*

3087 ** Advance the cursor to the next row in the %_content table that

3088 ** matches the search criteria. For a MATCH search, this will be

3089 ** the next row that matches. For a full-table scan, this will be

3090 ** simply the next row in the %_content table. For a docid lookup,

3091 ** this routine simply sets the EOF flag.

3092 **

3093 ** Return SQLITE_OK if nothing goes wrong. SQLITE_OK is returned

3094 ** even if we reach end-of-file. The fts3EofMethod() will be called

3095 ** subsequently to determine whether or not an EOF was hit.

3096 */

3097 static int fts3NextMethod(sqlite3_vtab_cursor *pCursor){

3098 int rc;

3099 Fts3Cursor pCsr = (Fts3Cursor )pCursor;

3100 if( pCsr->eSearch==FTS3_DOCID_SEARCH \|\| pCsr->eSearch==FTS3_FULLSCAN_SEARCH ){

3101 if( SQLITE_ROW!=sqlite3_step(pCsr->pStmt) ){

3102 pCsr->isEof = 1;

3103 rc = sqlite3_reset(pCsr->pStmt);

3104 }else{

3105 pCsr->iPrevId = sqlite3_column_int64(pCsr->pStmt, 0);

3106 rc = SQLITE_OK;

3107 }

3108 }else{

3109 rc = fts3EvalNext((Fts3Cursor *)pCursor);

3110 }

3111 assert( ((Fts3Table *)pCsr->base.pVtab)->pSegments==0 );

3112 return rc;

3113 }

3114

3115 /*

3116 ** The following are copied from sqliteInt.h.

3117 **

3118 ** Constants for the largest and smallest possible 64-bit signed integers.

3119 ** These macros are designed to work correctly on both 32-bit and 64-bit

3120 ** compilers.

3121 */

3122 #ifndef SQLITE_AMALGAMATION

3123 # define LARGEST_INT64 (0xffffffff\|(((sqlite3_int64)0x7fffffff)<<32))

3124 # define SMALLEST_INT64 (((sqlite3_int64)-1) - LARGEST_INT64)

3125 #endif

3126

3127 /*

3128 ** If the numeric type of argument pVal is "integer", then return it

3129 ** converted to a 64-bit signed integer. Otherwise, return a copy of

3130 ** the second parameter, iDefault.

3131 */

3132 static sqlite3_int64 fts3DocidRange(sqlite3_value *pVal, i64 iDefault){

3133 if( pVal ){

3134 int eType = sqlite3_value_numeric_type(pVal);

3135 if( eType==SQLITE_INTEGER ){

3136 return sqlite3_value_int64(pVal);

3137 }

3138 }

3139 return iDefault;

3140 }

3141

3142 /*

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

3144 ** the virtual table xFilter method documentation for additional

3145 ** information.

3146 **

3147 ** If idxNum==FTS3_FULLSCAN_SEARCH then do a full table scan against

3148 ** the %_content table.

3149 **

3150 ** If idxNum==FTS3_DOCID_SEARCH then do a docid lookup for a single entry

3151 ** in the %_content table.

3152 **

3153 ** If idxNum>=FTS3_FULLTEXT_SEARCH then use the full text index. The

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

3155 ** number idxNum-FTS3_FULLTEXT_SEARCH, 0 indexed. argv[0] is the right-hand

3156 ** side of the MATCH operator.

3157 */

3158 static int fts3FilterMethod(

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

3160 int idxNum, /* Strategy index */

3161 const char idxStr, / Unused */

3162 int nVal, /* Number of elements in apVal */

3163 sqlite3_value *apVal / Arguments for the indexing scheme */

3164 ){

3165 int rc = SQLITE_OK;

3166 char zSql; / SQL statement used to access %_content */

3167 int eSearch;

3168 Fts3Table p = (Fts3Table )pCursor->pVtab;

3169 Fts3Cursor pCsr = (Fts3Cursor )pCursor;

3170

3171 sqlite3_value pCons = 0; / The MATCH or rowid constraint, if any */

3172 sqlite3_value pLangid = 0; / The "langid = ?" constraint, if any */

3173 sqlite3_value pDocidGe = 0; / The "docid >= ?" constraint, if any */

3174 sqlite3_value pDocidLe = 0; / The "docid <= ?" constraint, if any */

3175 int iIdx;

3176

3177 UNUSED_PARAMETER(idxStr);

3178 UNUSED_PARAMETER(nVal);

3179

3180 eSearch = (idxNum & 0x0000FFFF);

3181 assert( eSearch>=0 && eSearch<=(FTS3_FULLTEXT_SEARCH+p->nColumn) );

3182 assert( p->pSegments==0 );

3183

3184 /* Collect arguments into local variables */

3185 iIdx = 0;

3186 if( eSearch!=FTS3_FULLSCAN_SEARCH ) pCons = apVal[iIdx++];

3187 if( idxNum & FTS3_HAVE_LANGID ) pLangid = apVal[iIdx++];

3188 if( idxNum & FTS3_HAVE_DOCID_GE ) pDocidGe = apVal[iIdx++];

3189 if( idxNum & FTS3_HAVE_DOCID_LE ) pDocidLe = apVal[iIdx++];

3190 assert( iIdx==nVal );

3191

3192 /* In case the cursor has been used before, clear it now. */

3193 sqlite3_finalize(pCsr->pStmt);

3194 sqlite3_free(pCsr->aDoclist);

3195 sqlite3Fts3MIBufferFree(pCsr->pMIBuffer);

3196 sqlite3Fts3ExprFree(pCsr->pExpr);

3197 memset(&pCursor[1], 0, sizeof(Fts3Cursor)-sizeof(sqlite3_vtab_cursor));

3198

3199 /* Set the lower and upper bounds on docids to return */

3200 pCsr->iMinDocid = fts3DocidRange(pDocidGe, SMALLEST_INT64);

3201 pCsr->iMaxDocid = fts3DocidRange(pDocidLe, LARGEST_INT64);

3202

3203 if( idxStr ){

3204 pCsr->bDesc = (idxStr[0]=='D');

3205 }else{

3206 pCsr->bDesc = p->bDescIdx;

3207 }

3208 pCsr->eSearch = (i16)eSearch;

3209

3210 if( eSearch!=FTS3_DOCID_SEARCH && eSearch!=FTS3_FULLSCAN_SEARCH ){

3211 int iCol = eSearch-FTS3_FULLTEXT_SEARCH;

3212 const char zQuery = (const char )sqlite3_value_text(pCons);

3213

3214 if( zQuery==0 && sqlite3_value_type(pCons)!=SQLITE_NULL ){

3215 return SQLITE_NOMEM;

3216 }

3217

3218 pCsr->iLangid = 0;

3219 if( pLangid ) pCsr->iLangid = sqlite3_value_int(pLangid);

3220

3221 assert( p->base.zErrMsg==0 );

3222 rc = sqlite3Fts3ExprParse(p->pTokenizer, pCsr->iLangid,

3223 p->azColumn, p->bFts4, p->nColumn, iCol, zQuery, -1, &pCsr->pExpr,

3224 &p->base.zErrMsg

3225 );

3226 if( rc!=SQLITE_OK ){

3227 return rc;

3228 }

3229

3230 rc = fts3EvalStart(pCsr);

3231 sqlite3Fts3SegmentsClose(p);

3232 if( rc!=SQLITE_OK ) return rc;

3233 pCsr->pNextId = pCsr->aDoclist;

3234 pCsr->iPrevId = 0;

3235 }

3236

3237 /* Compile a SELECT statement for this cursor. For a full-table-scan, the

3238 ** statement loops through all rows of the %_content table. For a

3239 ** full-text query or docid lookup, the statement retrieves a single

3240 ** row by docid.

3241 */

3242 if( eSearch==FTS3_FULLSCAN_SEARCH ){

3243 if( pDocidGe \|\| pDocidLe ){

3244 zSql = sqlite3_mprintf(

3245 "SELECT %s WHERE rowid BETWEEN %lld AND %lld ORDER BY rowid %s",

3246 p->zReadExprlist, pCsr->iMinDocid, pCsr->iMaxDocid,

3247 (pCsr->bDesc ? "DESC" : "ASC")

3248 );

3249 }else{

3250 zSql = sqlite3_mprintf("SELECT %s ORDER BY rowid %s",

3251 p->zReadExprlist, (pCsr->bDesc ? "DESC" : "ASC")

3252 );

3253 }

3254 if( zSql ){

3255 rc = sqlite3_prepare_v2(p->db, zSql, -1, &pCsr->pStmt, 0);

3256 sqlite3_free(zSql);

3257 }else{

3258 rc = SQLITE_NOMEM;

3259 }

3260 }else if( eSearch==FTS3_DOCID_SEARCH ){

3261 rc = fts3CursorSeekStmt(pCsr, &pCsr->pStmt);

3262 if( rc==SQLITE_OK ){

3263 rc = sqlite3_bind_value(pCsr->pStmt, 1, pCons);

3264 }

3265 }

3266 if( rc!=SQLITE_OK ) return rc;

3267

3268 return fts3NextMethod(pCursor);

3269 }

3270

3271 /*

3272 ** This is the xEof method of the virtual table. SQLite calls this

3273 ** routine to find out if it has reached the end of a result set.

3274 */

3275 static int fts3EofMethod(sqlite3_vtab_cursor *pCursor){

3276 return ((Fts3Cursor *)pCursor)->isEof;

3277 }

3278

3279 /*

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

3281 ** retrieve the rowid for the current row of the result set. fts3

3282 ** exposes %_content.docid as the rowid for the virtual table. The

3283 ** rowid should be written to *pRowid.

3284 */

3285 static int fts3RowidMethod(sqlite3_vtab_cursor pCursor, sqlite_int64 pRowid){

3286 Fts3Cursor pCsr = (Fts3Cursor ) pCursor;

3287 *pRowid = pCsr->iPrevId;

3288 return SQLITE_OK;

3289 }

3290

3291 /*

3292 ** This is the xColumn method, called by SQLite to request a value from

3293 ** the row that the supplied cursor currently points to.

3294 **

3295 ** If:

3296 **

3297 ** (iCol < p->nColumn) -> The value of the iCol'th user column.

3298 ** (iCol == p->nColumn) -> Magic column with the same name as the table.

3299 ** (iCol == p->nColumn+1) -> Docid column

3300 ** (iCol == p->nColumn+2) -> Langid column

3301 */

3302 static int fts3ColumnMethod(

3303 sqlite3_vtab_cursor pCursor, / Cursor to retrieve value from */

3304 sqlite3_context pCtx, / Context for sqlite3_result_xxx() calls */

3305 int iCol /* Index of column to read value from */

3306 ){

3307 int rc = SQLITE_OK; /* Return Code */

3308 Fts3Cursor pCsr = (Fts3Cursor ) pCursor;

3309 Fts3Table p = (Fts3Table )pCursor->pVtab;

3310

3311 /* The column value supplied by SQLite must be in range. */

3312 assert( iCol>=0 && iCol<=p->nColumn+2 );

3313

3314 if( iCol==p->nColumn+1 ){

3315 /* This call is a request for the "docid" column. Since "docid" is an

3316 ** alias for "rowid", use the xRowid() method to obtain the value.

3317 */

3318 sqlite3_result_int64(pCtx, pCsr->iPrevId);

3319 }else if( iCol==p->nColumn ){

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

3321 ** Return a blob which is a pointer to the cursor. */

3322 sqlite3_result_blob(pCtx, &pCsr, sizeof(pCsr), SQLITE_TRANSIENT);

3323 }else if( iCol==p->nColumn+2 && pCsr->pExpr ){

3324 sqlite3_result_int64(pCtx, pCsr->iLangid);

3325 }else{

3326 /* The requested column is either a user column (one that contains

3327 ** indexed data), or the language-id column. */

3328 rc = fts3CursorSeek(0, pCsr);

3329

3330 if( rc==SQLITE_OK ){

3331 if( iCol==p->nColumn+2 ){

3332 int iLangid = 0;

3333 if( p->zLanguageid ){

3334 iLangid = sqlite3_column_int(pCsr->pStmt, p->nColumn+1);

3335 }

3336 sqlite3_result_int(pCtx, iLangid);

3337 }else if( sqlite3_data_count(pCsr->pStmt)>(iCol+1) ){

3338 sqlite3_result_value(pCtx, sqlite3_column_value(pCsr->pStmt, iCol+1));

3339 }

3340 }

3341 }

3342

3343 assert( ((Fts3Table *)pCsr->base.pVtab)->pSegments==0 );

3344 return rc;

3345 }

3346

3347 /*

3348 ** This function is the implementation of the xUpdate callback used by

3349 ** FTS3 virtual tables. It is invoked by SQLite each time a row is to be

3350 ** inserted, updated or deleted.

3351 */

3352 static int fts3UpdateMethod(

3353 sqlite3_vtab pVtab, / Virtual table handle */

3354 int nArg, /* Size of argument array */

3355 sqlite3_value *apVal, / Array of arguments */

3356 sqlite_int64 pRowid / OUT: The affected (or effected) rowid */

3357 ){

3358 return sqlite3Fts3UpdateMethod(pVtab, nArg, apVal, pRowid);

3359 }

3360

3361 /*

3362 ** Implementation of xSync() method. Flush the contents of the pending-terms

3363 ** hash-table to the database.

3364 */

3365 static int fts3SyncMethod(sqlite3_vtab *pVtab){

3366

3367 /* Following an incremental-merge operation, assuming that the input

3368 ** segments are not completely consumed (the usual case), they are updated

3369 ** in place to remove the entries that have already been merged. This

3370 ** involves updating the leaf block that contains the smallest unmerged

3371 ** entry and each block (if any) between the leaf and the root node. So

3372 ** if the height of the input segment b-trees is N, and input segments

3373 ** are merged eight at a time, updating the input segments at the end

3374 ** of an incremental-merge requires writing (8*(1+N)) blocks. N is usually

3375 ** small - often between 0 and 2. So the overhead of the incremental

3376 ** merge is somewhere between 8 and 24 blocks. To avoid this overhead

3377 ** dwarfing the actual productive work accomplished, the incremental merge

3378 ** is only attempted if it will write at least 64 leaf blocks. Hence

3379 ** nMinMerge.

3380 **

3381 ** Of course, updating the input segments also involves deleting a bunch

3382 ** of blocks from the segments table. But this is not considered overhead

3383 ** as it would also be required by a crisis-merge that used the same input

3384 ** segments.

3385 */

3386 const u32 nMinMerge = 64; /* Minimum amount of incr-merge work to do */

3387

3388 Fts3Table p = (Fts3Table)pVtab;

3389 int rc = sqlite3Fts3PendingTermsFlush(p);

3390

3391 if( rc==SQLITE_OK

3392 && p->nLeafAdd>(nMinMerge/16)

3393 && p->nAutoincrmerge && p->nAutoincrmerge!=0xff

3394 ){

3395 int mxLevel = 0; /* Maximum relative level value in db */

3396 int A; /* Incr-merge parameter A */

3397

3398 rc = sqlite3Fts3MaxLevel(p, &mxLevel);

3399 assert( rc==SQLITE_OK \|\| mxLevel==0 );

3400 A = p->nLeafAdd * mxLevel;

3401 A += (A/2);

3402 if( A>(int)nMinMerge ) rc = sqlite3Fts3Incrmerge(p, A, p->nAutoincrmerge);

3403 }

3404 sqlite3Fts3SegmentsClose(p);

3405 return rc;

3406 }

3407

3408 /*

3409 ** If it is currently unknown whether or not the FTS table has an %_stat

3410 ** table (if p->bHasStat==2), attempt to determine this (set p->bHasStat

3411 ** to 0 or 1). Return SQLITE_OK if successful, or an SQLite error code

3412 ** if an error occurs.

3413 */

3414 static int fts3SetHasStat(Fts3Table *p){

3415 int rc = SQLITE_OK;

3416 if( p->bHasStat==2 ){

3417 const char *zFmt ="SELECT 1 FROM %Q.sqlite_master WHERE tbl_name='%q_stat'";

3418 char *zSql = sqlite3_mprintf(zFmt, p->zDb, p->zName);

3419 if( zSql ){

3420 sqlite3_stmt *pStmt = 0;

3421 rc = sqlite3_prepare_v2(p->db, zSql, -1, &pStmt, 0);

3422 if( rc==SQLITE_OK ){

3423 int bHasStat = (sqlite3_step(pStmt)==SQLITE_ROW);

3424 rc = sqlite3_finalize(pStmt);

3425 if( rc==SQLITE_OK ) p->bHasStat = bHasStat;

3426 }

3427 sqlite3_free(zSql);

3428 }else{

3429 rc = SQLITE_NOMEM;

3430 }

3431 }

3432 return rc;

3433 }

3434

3435 /*

3436 ** Implementation of xBegin() method.

3437 */

3438 static int fts3BeginMethod(sqlite3_vtab *pVtab){

3439 Fts3Table p = (Fts3Table)pVtab;

3440 UNUSED_PARAMETER(pVtab);

3441 assert( p->pSegments==0 );

3442 assert( p->nPendingData==0 );

3443 assert( p->inTransaction!=1 );

3444 TESTONLY( p->inTransaction = 1 );

3445 TESTONLY( p->mxSavepoint = -1; );

3446 p->nLeafAdd = 0;

3447 return fts3SetHasStat(p);

3448 }

3449

3450 /*

3451 ** Implementation of xCommit() method. This is a no-op. The contents of

3452 ** the pending-terms hash-table have already been flushed into the database

3453 ** by fts3SyncMethod().

3454 */

3455 static int fts3CommitMethod(sqlite3_vtab *pVtab){

3456 TESTONLY( Fts3Table p = (Fts3Table)pVtab );

3457 UNUSED_PARAMETER(pVtab);

3458 assert( p->nPendingData==0 );

3459 assert( p->inTransaction!=0 );

3460 assert( p->pSegments==0 );

3461 TESTONLY( p->inTransaction = 0 );

3462 TESTONLY( p->mxSavepoint = -1; );

3463 return SQLITE_OK;

3464 }

3465

3466 /*

3467 ** Implementation of xRollback(). Discard the contents of the pending-terms

3468 ** hash-table. Any changes made to the database are reverted by SQLite.

3469 */

3470 static int fts3RollbackMethod(sqlite3_vtab *pVtab){

3471 Fts3Table p = (Fts3Table)pVtab;

3472 sqlite3Fts3PendingTermsClear(p);

3473 assert( p->inTransaction!=0 );

3474 TESTONLY( p->inTransaction = 0 );

3475 TESTONLY( p->mxSavepoint = -1; );

3476 return SQLITE_OK;

3477 }

3478

3479 /*

3480 ** When called, *ppPoslist must point to the byte immediately following the

3481 ** end of a position-list. i.e. ( (*ppPoslist)[-1]==POS_END ). This function

3482 ** moves *ppPoslist so that it instead points to the first byte of the

3483 ** same position list.

3484 */

3485 static void fts3ReversePoslist(char pStart, char *ppPoslist){

3486 char p = &(ppPoslist)[-2];

3487 char c = 0;

3488

3489 /* Skip backwards passed any trailing 0x00 bytes added by NearTrim() */

3490 while( p>pStart && (c=*p--)==0 );

3491

3492 /* Search backwards for a varint with value zero (the end of the previous

3493 ** poslist). This is an 0x00 byte preceded by some byte that does not

3494 ** have the 0x80 bit set. */

3495 while( p>pStart && (*p & 0x80) \| c ){

3496 c = *p--;

3497 }

3498 assert( p==pStart \|\| c==0 );

3499

3500 /* At this point p points to that preceding byte without the 0x80 bit

3501 ** set. So to find the start of the poslist, skip forward 2 bytes then

3502 ** over a varint.

3503 **

3504 ** Normally. The other case is that p==pStart and the poslist to return

3505 ** is the first in the doclist. In this case do not skip forward 2 bytes.

3506 ** The second part of the if condition (c==0 && *ppPoslist>&p[2])

3507 ** is required for cases where the first byte of a doclist and the

3508 ** doclist is empty. For example, if the first docid is 10, a doclist

3509 ** that begins with:

3510 **

3511 ** 0x0A 0x00 <next docid delta varint>

3512 */

3513 if( p>pStart \|\| (c==0 && *ppPoslist>&p[2]) ){ p = &p[2]; }

3514 while( *p++&0x80 );

3515 *ppPoslist = p;

3516 }

3517

3518 /*

3519 ** Helper function used by the implementation of the overloaded snippet(),

3520 ** offsets() and optimize() SQL functions.

3521 **

3522 ** If the value passed as the third argument is a blob of size

3523 ** sizeof(Fts3Cursor*), then the blob contents are copied to the

3524 ** output variable *ppCsr and SQLITE_OK is returned. Otherwise, an error

3525 ** message is written to context pContext and SQLITE_ERROR returned. The

3526 ** string passed via zFunc is used as part of the error message.

3527 */

3528 static int fts3FunctionArg(

3529 sqlite3_context pContext, / SQL function call context */

3530 const char zFunc, / Function name */

3531 sqlite3_value pVal, / argv[0] passed to function */

3532 Fts3Cursor *ppCsr / OUT: Store cursor handle here */

3533 ){

3534 Fts3Cursor *pRet;

3535 if( sqlite3_value_type(pVal)!=SQLITE_BLOB

3536 \|\| sqlite3_value_bytes(pVal)!=sizeof(Fts3Cursor *)

3537 ){

3538 char *zErr = sqlite3_mprintf("illegal first argument to %s", zFunc);

3539 sqlite3_result_error(pContext, zErr, -1);

3540 sqlite3_free(zErr);

3541 return SQLITE_ERROR;

3542 }

3543 memcpy(&pRet, sqlite3_value_blob(pVal), sizeof(Fts3Cursor *));

3544 *ppCsr = pRet;

3545 return SQLITE_OK;

3546 }

3547

3548 /*

3549 ** Implementation of the snippet() function for FTS3

3550 */

3551 static void fts3SnippetFunc(

3552 sqlite3_context pContext, / SQLite function call context */

3553 int nVal, /* Size of apVal[] array */

3554 sqlite3_value *apVal / Array of arguments */

3555 ){

3556 Fts3Cursor pCsr; / Cursor handle passed through apVal[0] */

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

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

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

3560 int iCol = -1;

3561 int nToken = 15; /* Default number of tokens in snippet */

3562

3563 /* There must be at least one argument passed to this function (otherwise

3564 ** the non-overloaded version would have been called instead of this one).

3565 */

3566 assert( nVal>=1 );

3567

3568 if( nVal>6 ){

3569 sqlite3_result_error(pContext,

3570 "wrong number of arguments to function snippet()", -1);

3571 return;

3572 }

3573 if( fts3FunctionArg(pContext, "snippet", apVal[0], &pCsr) ) return;

3574

3575 switch( nVal ){

3576 case 6: nToken = sqlite3_value_int(apVal[5]);

3577 case 5: iCol = sqlite3_value_int(apVal[4]);

3578 case 4: zEllipsis = (const char*)sqlite3_value_text(apVal[3]);

3579 case 3: zEnd = (const char*)sqlite3_value_text(apVal[2]);

3580 case 2: zStart = (const char*)sqlite3_value_text(apVal[1]);

3581 }

3582 if( !zEllipsis \|\| !zEnd \|\| !zStart ){

3583 sqlite3_result_error_nomem(pContext);

3584 }else if( nToken==0 ){

3585 sqlite3_result_text(pContext, "", -1, SQLITE_STATIC);

3586 }else if( SQLITE_OK==fts3CursorSeek(pContext, pCsr) ){

3587 sqlite3Fts3Snippet(pContext, pCsr, zStart, zEnd, zEllipsis, iCol, nToken);

3588 }

3589 }

3590

3591 /*

3592 ** Implementation of the offsets() function for FTS3

3593 */

3594 static void fts3OffsetsFunc(

3595 sqlite3_context pContext, / SQLite function call context */

3596 int nVal, /* Size of argument array */

3597 sqlite3_value *apVal / Array of arguments */

3598 ){

3599 Fts3Cursor pCsr; / Cursor handle passed through apVal[0] */

3600

3601 UNUSED_PARAMETER(nVal);

3602

3603 assert( nVal==1 );

3604 if( fts3FunctionArg(pContext, "offsets", apVal[0], &pCsr) ) return;

3605 assert( pCsr );

3606 if( SQLITE_OK==fts3CursorSeek(pContext, pCsr) ){

3607 sqlite3Fts3Offsets(pContext, pCsr);

3608 }

3609 }

3610

3611 /*

3612 ** Implementation of the special optimize() function for FTS3. This

3613 ** function merges all segments in the database to a single segment.

3614 ** Example usage is:

3615 **

3616 ** SELECT optimize(t) FROM t LIMIT 1;

3617 **

3618 ** where 't' is the name of an FTS3 table.

3619 */

3620 static void fts3OptimizeFunc(

3621 sqlite3_context pContext, / SQLite function call context */

3622 int nVal, /* Size of argument array */

3623 sqlite3_value *apVal / Array of arguments */

3624 ){

3625 int rc; /* Return code */

3626 Fts3Table p; / Virtual table handle */

3627 Fts3Cursor pCursor; / Cursor handle passed through apVal[0] */

3628

3629 UNUSED_PARAMETER(nVal);

3630

3631 assert( nVal==1 );

3632 if( fts3FunctionArg(pContext, "optimize", apVal[0], &pCursor) ) return;

3633 p = (Fts3Table *)pCursor->base.pVtab;

3634 assert( p );

3635

3636 rc = sqlite3Fts3Optimize(p);

3637

3638 switch( rc ){

3639 case SQLITE_OK:

3640 sqlite3_result_text(pContext, "Index optimized", -1, SQLITE_STATIC);

3641 break;

3642 case SQLITE_DONE:

3643 sqlite3_result_text(pContext, "Index already optimal", -1, SQLITE_STATIC);

3644 break;

3645 default:

3646 sqlite3_result_error_code(pContext, rc);

3647 break;

3648 }

3649 }

3650

3651 /*

3652 ** Implementation of the matchinfo() function for FTS3

3653 */

3654 static void fts3MatchinfoFunc(

3655 sqlite3_context pContext, / SQLite function call context */

3656 int nVal, /* Size of argument array */

3657 sqlite3_value *apVal / Array of arguments */

3658 ){

3659 Fts3Cursor pCsr; / Cursor handle passed through apVal[0] */

3660 assert( nVal==1 \|\| nVal==2 );

3661 if( SQLITE_OK==fts3FunctionArg(pContext, "matchinfo", apVal[0], &pCsr) ){

3662 const char *zArg = 0;

3663 if( nVal>1 ){

3664 zArg = (const char *)sqlite3_value_text(apVal[1]);

3665 }

3666 sqlite3Fts3Matchinfo(pContext, pCsr, zArg);

3667 }

3668 }

3669

3670 /*

3671 ** This routine implements the xFindFunction method for the FTS3

3672 ** virtual table.

3673 */

3674 static int fts3FindFunctionMethod(

3675 sqlite3_vtab pVtab, / Virtual table handle */

3676 int nArg, /* Number of SQL function arguments */

3677 const char zName, / Name of SQL function */

3678 void (*pxFunc)(sqlite3_context,int,sqlite3_value*), / OUT: Result */

3679 void *ppArg / Unused */

3680 ){

3681 struct Overloaded {

3682 const char *zName;

3683 void (xFunc)(sqlite3_context,int,sqlite3_value**);

3684 } aOverload[] = {

3685 { "snippet", fts3SnippetFunc },

3686 { "offsets", fts3OffsetsFunc },

3687 { "optimize", fts3OptimizeFunc },

3688 { "matchinfo", fts3MatchinfoFunc },

3689 };

3690 int i; /* Iterator variable */

3691

3692 UNUSED_PARAMETER(pVtab);

3693 UNUSED_PARAMETER(nArg);

3694 UNUSED_PARAMETER(ppArg);

3695

3696 for(i=0; i<SizeofArray(aOverload); i++){

3697 if( strcmp(zName, aOverload[i].zName)==0 ){

3698 *pxFunc = aOverload[i].xFunc;

3699 return 1;

3700 }

3701 }

3702

3703 /* No function of the specified name was found. Return 0. */

3704 return 0;

3705 }

3706

3707 /*

3708 ** Implementation of FTS3 xRename method. Rename an fts3 table.

3709 */

3710 static int fts3RenameMethod(

3711 sqlite3_vtab pVtab, / Virtual table handle */

3712 const char zName / New name of table */

3713 ){

3714 Fts3Table p = (Fts3Table )pVtab;

3715 sqlite3 db = p->db; / Database connection */

3716 int rc; /* Return Code */

3717

3718 /* At this point it must be known if the %_stat table exists or not.

3719 ** So bHasStat may not be 2. */

3720 rc = fts3SetHasStat(p);

3721

3722 /* As it happens, the pending terms table is always empty here. This is

3723 ** because an "ALTER TABLE RENAME TABLE" statement inside a transaction

3724 ** always opens a savepoint transaction. And the xSavepoint() method

3725 ** flushes the pending terms table. But leave the (no-op) call to

3726 ** PendingTermsFlush() in in case that changes.

3727 */

3728 assert( p->nPendingData==0 );

3729 if( rc==SQLITE_OK ){

3730 rc = sqlite3Fts3PendingTermsFlush(p);

3731 }

3732

3733 if( p->zContentTbl==0 ){

3734 fts3DbExec(&rc, db,

3735 "ALTER TABLE %Q.'%q_content' RENAME TO '%q_content';",

3736 p->zDb, p->zName, zName

3737 );

3738 }

3739

3740 if( p->bHasDocsize ){

3741 fts3DbExec(&rc, db,

3742 "ALTER TABLE %Q.'%q_docsize' RENAME TO '%q_docsize';",

3743 p->zDb, p->zName, zName

3744 );

3745 }

3746 if( p->bHasStat ){

3747 fts3DbExec(&rc, db,

3748 "ALTER TABLE %Q.'%q_stat' RENAME TO '%q_stat';",

3749 p->zDb, p->zName, zName

3750 );

3751 }

3752 fts3DbExec(&rc, db,

3753 "ALTER TABLE %Q.'%q_segments' RENAME TO '%q_segments';",

3754 p->zDb, p->zName, zName

3755 );

3756 fts3DbExec(&rc, db,

3757 "ALTER TABLE %Q.'%q_segdir' RENAME TO '%q_segdir';",

3758 p->zDb, p->zName, zName

3759 );

3760 return rc;

3761 }

3762

3763 /*

3764 ** The xSavepoint() method.

3765 **

3766 ** Flush the contents of the pending-terms table to disk.

3767 */

3768 static int fts3SavepointMethod(sqlite3_vtab *pVtab, int iSavepoint){

3769 int rc = SQLITE_OK;

3770 UNUSED_PARAMETER(iSavepoint);

3771 assert( ((Fts3Table *)pVtab)->inTransaction );

3772 assert( ((Fts3Table *)pVtab)->mxSavepoint < iSavepoint );

3773 TESTONLY( ((Fts3Table *)pVtab)->mxSavepoint = iSavepoint );

3774 if( ((Fts3Table *)pVtab)->bIgnoreSavepoint==0 ){

3775 rc = fts3SyncMethod(pVtab);

3776 }

3777 return rc;

3778 }

3779

3780 /*

3781 ** The xRelease() method.

3782 **

3783 ** This is a no-op.

3784 */

3785 static int fts3ReleaseMethod(sqlite3_vtab *pVtab, int iSavepoint){

3786 TESTONLY( Fts3Table p = (Fts3Table)pVtab );

3787 UNUSED_PARAMETER(iSavepoint);

3788 UNUSED_PARAMETER(pVtab);

3789 assert( p->inTransaction );

3790 assert( p->mxSavepoint >= iSavepoint );

3791 TESTONLY( p->mxSavepoint = iSavepoint-1 );

3792 return SQLITE_OK;

3793 }

3794

3795 /*

3796 ** The xRollbackTo() method.

3797 **

3798 ** Discard the contents of the pending terms table.

3799 */

3800 static int fts3RollbackToMethod(sqlite3_vtab *pVtab, int iSavepoint){

3801 Fts3Table p = (Fts3Table)pVtab;

3802 UNUSED_PARAMETER(iSavepoint);

3803 assert( p->inTransaction );

3804 assert( p->mxSavepoint >= iSavepoint );

3805 TESTONLY( p->mxSavepoint = iSavepoint );

3806 sqlite3Fts3PendingTermsClear(p);

3807 return SQLITE_OK;

3808 }

3809

3810 static const sqlite3_module fts3Module = {

3811 /* iVersion */ 2,

3812 /* xCreate */ fts3CreateMethod,

3813 /* xConnect */ fts3ConnectMethod,

3814 /* xBestIndex */ fts3BestIndexMethod,

3815 /* xDisconnect */ fts3DisconnectMethod,

3816 /* xDestroy */ fts3DestroyMethod,

3817 /* xOpen */ fts3OpenMethod,

3818 /* xClose */ fts3CloseMethod,

3819 /* xFilter */ fts3FilterMethod,

3820 /* xNext */ fts3NextMethod,

3821 /* xEof */ fts3EofMethod,

3822 /* xColumn */ fts3ColumnMethod,

3823 /* xRowid */ fts3RowidMethod,

3824 /* xUpdate */ fts3UpdateMethod,

3825 /* xBegin */ fts3BeginMethod,

3826 /* xSync */ fts3SyncMethod,

3827 /* xCommit */ fts3CommitMethod,

3828 /* xRollback */ fts3RollbackMethod,

3829 /* xFindFunction */ fts3FindFunctionMethod,

3830 /* xRename */ fts3RenameMethod,

3831 /* xSavepoint */ fts3SavepointMethod,

3832 /* xRelease */ fts3ReleaseMethod,

3833 /* xRollbackTo */ fts3RollbackToMethod,

3834 };

3835

3836 /*

3837 ** This function is registered as the module destructor (called when an

3838 ** FTS3 enabled database connection is closed). It frees the memory

3839 ** allocated for the tokenizer hash table.

3840 */

3841 static void hashDestroy(void *p){

3842 Fts3Hash pHash = (Fts3Hash )p;

3843 sqlite3Fts3HashClear(pHash);

3844 sqlite3_free(pHash);

3845 }

3846

3847 /*

3848 ** The fts3 built-in tokenizers - "simple", "porter" and "icu"- are

3849 ** implemented in files fts3_tokenizer1.c, fts3_porter.c and fts3_icu.c

3850 ** respectively. The following three forward declarations are for functions

3851 ** declared in these files used to retrieve the respective implementations.

3852 **

3853 ** Calling sqlite3Fts3SimpleTokenizerModule() sets the value pointed

3854 ** to by the argument to point to the "simple" tokenizer implementation.

3855 ** And so on.

3856 */

3857 void sqlite3Fts3SimpleTokenizerModule(sqlite3_tokenizer_module const**ppModule);

3858 void sqlite3Fts3PorterTokenizerModule(sqlite3_tokenizer_module const**ppModule);

3859 #ifndef SQLITE_DISABLE_FTS3_UNICODE

3860 void sqlite3Fts3UnicodeTokenizer(sqlite3_tokenizer_module const**ppModule);

3861 #endif

3862 #ifdef SQLITE_ENABLE_ICU

3863 void sqlite3Fts3IcuTokenizerModule(sqlite3_tokenizer_module const**ppModule);

3864 #endif

3865

3866 /*

3867 ** Initialize the fts3 extension. If this extension is built as part

3868 ** of the sqlite library, then this function is called directly by

3869 ** SQLite. If fts3 is built as a dynamically loadable extension, this

3870 ** function is called by the sqlite3_extension_init() entry point.

3871 */

3872 int sqlite3Fts3Init(sqlite3 *db){

3873 int rc = SQLITE_OK;

3874 Fts3Hash *pHash = 0;

3875 const sqlite3_tokenizer_module *pSimple = 0;

3876 const sqlite3_tokenizer_module *pPorter = 0;

3877 #ifndef SQLITE_DISABLE_FTS3_UNICODE

3878 const sqlite3_tokenizer_module *pUnicode = 0;

3879 #endif

3880

3881 #ifdef SQLITE_ENABLE_ICU

3882 const sqlite3_tokenizer_module *pIcu = 0;

3883 sqlite3Fts3IcuTokenizerModule(&pIcu);

3884 #endif

3885

3886 #ifndef SQLITE_DISABLE_FTS3_UNICODE

3887 sqlite3Fts3UnicodeTokenizer(&pUnicode);

3888 #endif

3889

3890 #ifdef SQLITE_TEST

3891 rc = sqlite3Fts3InitTerm(db);

3892 if( rc!=SQLITE_OK ) return rc;

3893 #endif

3894

3895 rc = sqlite3Fts3InitAux(db);

3896 if( rc!=SQLITE_OK ) return rc;

3897

3898 sqlite3Fts3SimpleTokenizerModule(&pSimple);

3899 sqlite3Fts3PorterTokenizerModule(&pPorter);

3900

3901 /* Allocate and initialize the hash-table used to store tokenizers. */

3902 pHash = sqlite3_malloc(sizeof(Fts3Hash));

3903 if( !pHash ){

3904 rc = SQLITE_NOMEM;

3905 }else{

3906 sqlite3Fts3HashInit(pHash, FTS3_HASH_STRING, 1);

3907 }

3908

3909 /* Load the built-in tokenizers into the hash table */

3910 if( rc==SQLITE_OK ){

3911 if( sqlite3Fts3HashInsert(pHash, "simple", 7, (void *)pSimple)

3912 \|\| sqlite3Fts3HashInsert(pHash, "porter", 7, (void *)pPorter)

3913

3914 #ifndef SQLITE_DISABLE_FTS3_UNICODE

3915 \|\| sqlite3Fts3HashInsert(pHash, "unicode61", 10, (void *)pUnicode)

3916 #endif

3917 #ifdef SQLITE_ENABLE_ICU

3918 \|\| (pIcu && sqlite3Fts3HashInsert(pHash, "icu", 4, (void *)pIcu))

3919 #endif

3920 ){

3921 rc = SQLITE_NOMEM;

3922 }

3923 }

3924

3925 #ifdef SQLITE_TEST

3926 if( rc==SQLITE_OK ){

3927 rc = sqlite3Fts3ExprInitTestInterface(db);

3928 }

3929 #endif

3930

3931 /* Create the virtual table wrapper around the hash-table and overload

3932 ** the two scalar functions. If this is successful, register the

3933 ** module with sqlite.

3934 */

3935 if( SQLITE_OK==rc

3936 && SQLITE_OK==(rc = sqlite3Fts3InitHashTable(db, pHash, "fts3_tokenizer"))

3937 && SQLITE_OK==(rc = sqlite3_overload_function(db, "snippet", -1))

3938 && SQLITE_OK==(rc = sqlite3_overload_function(db, "offsets", 1))

3939 && SQLITE_OK==(rc = sqlite3_overload_function(db, "matchinfo", 1))

3940 && SQLITE_OK==(rc = sqlite3_overload_function(db, "matchinfo", 2))

3941 && SQLITE_OK==(rc = sqlite3_overload_function(db, "optimize", 1))

3942 ){

3943 rc = sqlite3_create_module_v2(

3944 db, "fts3", &fts3Module, (void *)pHash, hashDestroy

3945 );

3946 if( rc==SQLITE_OK ){

3947 rc = sqlite3_create_module_v2(

3948 db, "fts4", &fts3Module, (void *)pHash, 0

3949 );

3950 }

3951 if( rc==SQLITE_OK ){

3952 rc = sqlite3Fts3InitTok(db, (void *)pHash);

3953 }

3954 return rc;

3955 }

3956

3957

3958 /* An error has occurred. Delete the hash table and return the error code. */

3959 assert( rc!=SQLITE_OK );

3960 if( pHash ){

3961 sqlite3Fts3HashClear(pHash);

3962 sqlite3_free(pHash);

3963 }

3964 return rc;

3965 }

3966

3967 /*

3968 ** Allocate an Fts3MultiSegReader for each token in the expression headed

3969 ** by pExpr.

3970 **

3971 ** An Fts3SegReader object is a cursor that can seek or scan a range of

3972 ** entries within a single segment b-tree. An Fts3MultiSegReader uses multiple

3973 ** Fts3SegReader objects internally to provide an interface to seek or scan

3974 ** within the union of all segments of a b-tree. Hence the name.

3975 **

3976 ** If the allocated Fts3MultiSegReader just seeks to a single entry in a

3977 ** segment b-tree (if the term is not a prefix or it is a prefix for which

3978 ** there exists prefix b-tree of the right length) then it may be traversed

3979 ** and merged incrementally. Otherwise, it has to be merged into an in-memory

3980 ** doclist and then traversed.

3981 */

3982 static void fts3EvalAllocateReaders(

3983 Fts3Cursor pCsr, / FTS cursor handle */

3984 Fts3Expr pExpr, / Allocate readers for this expression */

3985 int pnToken, / OUT: Total number of tokens in phrase. */

3986 int pnOr, / OUT: Total number of OR nodes in expr. */

3987 int pRc / IN/OUT: Error code */

3988 ){

3989 if( pExpr && SQLITE_OK==*pRc ){

3990 if( pExpr->eType==FTSQUERY_PHRASE ){

3991 int i;

3992 int nToken = pExpr->pPhrase->nToken;

3993 *pnToken += nToken;

3994 for(i=0; i<nToken; i++){

3995 Fts3PhraseToken *pToken = &pExpr->pPhrase->aToken[i];

3996 int rc = fts3TermSegReaderCursor(pCsr,

3997 pToken->z, pToken->n, pToken->isPrefix, &pToken->pSegcsr

3998 );

3999 if( rc!=SQLITE_OK ){

4000 *pRc = rc;

4001 return;

4002 }

4003 }

4004 assert( pExpr->pPhrase->iDoclistToken==0 );

4005 pExpr->pPhrase->iDoclistToken = -1;

4006 }else{

4007 *pnOr += (pExpr->eType==FTSQUERY_OR);

4008 fts3EvalAllocateReaders(pCsr, pExpr->pLeft, pnToken, pnOr, pRc);

4009 fts3EvalAllocateReaders(pCsr, pExpr->pRight, pnToken, pnOr, pRc);

4010 }

4011 }

4012 }

4013

4014 /*

4015 ** Arguments pList/nList contain the doclist for token iToken of phrase p.

4016 ** It is merged into the main doclist stored in p->doclist.aAll/nAll.

4017 **

4018 ** This function assumes that pList points to a buffer allocated using

4019 ** sqlite3_malloc(). This function takes responsibility for eventually

4020 ** freeing the buffer.

4021 **

4022 ** SQLITE_OK is returned if successful, or SQLITE_NOMEM if an error occurs.

4023 */

4024 static int fts3EvalPhraseMergeToken(

4025 Fts3Table pTab, / FTS Table pointer */

4026 Fts3Phrase p, / Phrase to merge pList/nList into */

4027 int iToken, /* Token pList/nList corresponds to */

4028 char pList, / Pointer to doclist */

4029 int nList /* Number of bytes in pList */

4030 ){

4031 int rc = SQLITE_OK;

4032 assert( iToken!=p->iDoclistToken );

4033

4034 if( pList==0 ){

4035 sqlite3_free(p->doclist.aAll);

4036 p->doclist.aAll = 0;

4037 p->doclist.nAll = 0;

4038 }

4039

4040 else if( p->iDoclistToken<0 ){

4041 p->doclist.aAll = pList;

4042 p->doclist.nAll = nList;

4043 }

4044

4045 else if( p->doclist.aAll==0 ){

4046 sqlite3_free(pList);

4047 }

4048

4049 else {

4050 char *pLeft;

4051 char *pRight;

4052 int nLeft;

4053 int nRight;

4054 int nDiff;

4055

4056 if( p->iDoclistToken<iToken ){

4057 pLeft = p->doclist.aAll;

4058 nLeft = p->doclist.nAll;

4059 pRight = pList;

4060 nRight = nList;

4061 nDiff = iToken - p->iDoclistToken;

4062 }else{

4063 pRight = p->doclist.aAll;

4064 nRight = p->doclist.nAll;

4065 pLeft = pList;

4066 nLeft = nList;

4067 nDiff = p->iDoclistToken - iToken;

4068 }

4069

4070 rc = fts3DoclistPhraseMerge(

4071 pTab->bDescIdx, nDiff, pLeft, nLeft, &pRight, &nRight

4072 );

4073 sqlite3_free(pLeft);

4074 p->doclist.aAll = pRight;

4075 p->doclist.nAll = nRight;

4076 }

4077

4078 if( iToken>p->iDoclistToken ) p->iDoclistToken = iToken;

4079 return rc;

4080 }

4081

4082 /*

4083 ** Load the doclist for phrase p into p->doclist.aAll/nAll. The loaded doclist

4084 ** does not take deferred tokens into account.

4085 **

4086 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.

4087 */

4088 static int fts3EvalPhraseLoad(

4089 Fts3Cursor pCsr, / FTS Cursor handle */

4090 Fts3Phrase p / Phrase object */

4091 ){

4092 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

4093 int iToken;

4094 int rc = SQLITE_OK;

4095

4096 for(iToken=0; rc==SQLITE_OK && iToken<p->nToken; iToken++){

4097 Fts3PhraseToken *pToken = &p->aToken[iToken];

4098 assert( pToken->pDeferred==0 \|\| pToken->pSegcsr==0 );

4099

4100 if( pToken->pSegcsr ){

4101 int nThis = 0;

4102 char *pThis = 0;

4103 rc = fts3TermSelect(pTab, pToken, p->iColumn, &nThis, &pThis);

4104 if( rc==SQLITE_OK ){

4105 rc = fts3EvalPhraseMergeToken(pTab, p, iToken, pThis, nThis);

4106 }

4107 }

4108 assert( pToken->pSegcsr==0 );

4109 }

4110

4111 return rc;

4112 }

4113

4114 /*

4115 ** This function is called on each phrase after the position lists for

4116 ** any deferred tokens have been loaded into memory. It updates the phrases

4117 ** current position list to include only those positions that are really

4118 ** instances of the phrase (after considering deferred tokens). If this

4119 ** means that the phrase does not appear in the current row, doclist.pList

4120 ** and doclist.nList are both zeroed.

4121 **

4122 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.

4123 */

4124 static int fts3EvalDeferredPhrase(Fts3Cursor pCsr, Fts3Phrase pPhrase){

4125 int iToken; /* Used to iterate through phrase tokens */

4126 char aPoslist = 0; / Position list for deferred tokens */

4127 int nPoslist = 0; /* Number of bytes in aPoslist */

4128 int iPrev = -1; /* Token number of previous deferred token */

4129

4130 assert( pPhrase->doclist.bFreeList==0 );

4131

4132 for(iToken=0; iToken<pPhrase->nToken; iToken++){

4133 Fts3PhraseToken *pToken = &pPhrase->aToken[iToken];

4134 Fts3DeferredToken *pDeferred = pToken->pDeferred;

4135

4136 if( pDeferred ){

4137 char *pList;

4138 int nList;

4139 int rc = sqlite3Fts3DeferredTokenList(pDeferred, &pList, &nList);

4140 if( rc!=SQLITE_OK ) return rc;

4141

4142 if( pList==0 ){

4143 sqlite3_free(aPoslist);

4144 pPhrase->doclist.pList = 0;

4145 pPhrase->doclist.nList = 0;

4146 return SQLITE_OK;

4147

4148 }else if( aPoslist==0 ){

4149 aPoslist = pList;

4150 nPoslist = nList;

4151

4152 }else{

4153 char *aOut = pList;

4154 char *p1 = aPoslist;

4155 char *p2 = aOut;

4156

4157 assert( iPrev>=0 );

4158 fts3PoslistPhraseMerge(&aOut, iToken-iPrev, 0, 1, &p1, &p2);

4159 sqlite3_free(aPoslist);

4160 aPoslist = pList;

4161 nPoslist = (int)(aOut - aPoslist);

4162 if( nPoslist==0 ){

4163 sqlite3_free(aPoslist);

4164 pPhrase->doclist.pList = 0;

4165 pPhrase->doclist.nList = 0;

4166 return SQLITE_OK;

4167 }

4168 }

4169 iPrev = iToken;

4170 }

4171 }

4172

4173 if( iPrev>=0 ){

4174 int nMaxUndeferred = pPhrase->iDoclistToken;

4175 if( nMaxUndeferred<0 ){

4176 pPhrase->doclist.pList = aPoslist;

4177 pPhrase->doclist.nList = nPoslist;

4178 pPhrase->doclist.iDocid = pCsr->iPrevId;

4179 pPhrase->doclist.bFreeList = 1;

4180 }else{

4181 int nDistance;

4182 char *p1;

4183 char *p2;

4184 char *aOut;

4185

4186 if( nMaxUndeferred>iPrev ){

4187 p1 = aPoslist;

4188 p2 = pPhrase->doclist.pList;

4189 nDistance = nMaxUndeferred - iPrev;

4190 }else{

4191 p1 = pPhrase->doclist.pList;

4192 p2 = aPoslist;

4193 nDistance = iPrev - nMaxUndeferred;

4194 }

4195

4196 aOut = (char *)sqlite3_malloc(nPoslist+8);

4197 if( !aOut ){

4198 sqlite3_free(aPoslist);

4199 return SQLITE_NOMEM;

4200 }

4201

4202 pPhrase->doclist.pList = aOut;

4203 if( fts3PoslistPhraseMerge(&aOut, nDistance, 0, 1, &p1, &p2) ){

4204 pPhrase->doclist.bFreeList = 1;

4205 pPhrase->doclist.nList = (int)(aOut - pPhrase->doclist.pList);

4206 }else{

4207 sqlite3_free(aOut);

4208 pPhrase->doclist.pList = 0;

4209 pPhrase->doclist.nList = 0;

4210 }

4211 sqlite3_free(aPoslist);

4212 }

4213 }

4214

4215 return SQLITE_OK;

4216 }

4217

4218 /*

4219 ** Maximum number of tokens a phrase may have to be considered for the

4220 ** incremental doclists strategy.

4221 */

4222 #define MAX_INCR_PHRASE_TOKENS 4

4223

4224 /*

4225 ** This function is called for each Fts3Phrase in a full-text query

4226 ** expression to initialize the mechanism for returning rows. Once this

4227 ** function has been called successfully on an Fts3Phrase, it may be

4228 ** used with fts3EvalPhraseNext() to iterate through the matching docids.

4229 **

4230 ** If parameter bOptOk is true, then the phrase may (or may not) use the

4231 ** incremental loading strategy. Otherwise, the entire doclist is loaded into

4232 ** memory within this call.

4233 **

4234 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.

4235 */

4236 static int fts3EvalPhraseStart(Fts3Cursor pCsr, int bOptOk, Fts3Phrase p){

4237 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

4238 int rc = SQLITE_OK; /* Error code */

4239 int i;

4240

4241 /* Determine if doclists may be loaded from disk incrementally. This is

4242 ** possible if the bOptOk argument is true, the FTS doclists will be

4243 ** scanned in forward order, and the phrase consists of

4244 ** MAX_INCR_PHRASE_TOKENS or fewer tokens, none of which are are "^first"

4245 ** tokens or prefix tokens that cannot use a prefix-index. */

4246 int bHaveIncr = 0;

4247 int bIncrOk = (bOptOk

4248 && pCsr->bDesc==pTab->bDescIdx

4249 && p->nToken<=MAX_INCR_PHRASE_TOKENS && p->nToken>0

4250 #ifdef SQLITE_TEST

4251 && pTab->bNoIncrDoclist==0

4252 #endif

4253 );

4254 for(i=0; bIncrOk==1 && i<p->nToken; i++){

4255 Fts3PhraseToken *pToken = &p->aToken[i];

4256 if( pToken->bFirst \|\| (pToken->pSegcsr!=0 && !pToken->pSegcsr->bLookup) ){

4257 bIncrOk = 0;

4258 }

4259 if( pToken->pSegcsr ) bHaveIncr = 1;

4260 }

4261

4262 if( bIncrOk && bHaveIncr ){

4263 /* Use the incremental approach. */

4264 int iCol = (p->iColumn >= pTab->nColumn ? -1 : p->iColumn);

4265 for(i=0; rc==SQLITE_OK && i<p->nToken; i++){

4266 Fts3PhraseToken *pToken = &p->aToken[i];

4267 Fts3MultiSegReader *pSegcsr = pToken->pSegcsr;

4268 if( pSegcsr ){

4269 rc = sqlite3Fts3MsrIncrStart(pTab, pSegcsr, iCol, pToken->z, pToken->n);

4270 }

4271 }

4272 p->bIncr = 1;

4273 }else{

4274 /* Load the full doclist for the phrase into memory. */

4275 rc = fts3EvalPhraseLoad(pCsr, p);

4276 p->bIncr = 0;

4277 }

4278

4279 assert( rc!=SQLITE_OK \|\| p->nToken<1 \|\| p->aToken[0].pSegcsr==0 \|\| p->bIncr );

4280 return rc;

4281 }

4282

4283 /*

4284 ** This function is used to iterate backwards (from the end to start)

4285 ** through doclists. It is used by this module to iterate through phrase

4286 ** doclists in reverse and by the fts3_write.c module to iterate through

4287 ** pending-terms lists when writing to databases with "order=desc".

4288 **

4289 ** The doclist may be sorted in ascending (parameter bDescIdx==0) or

4290 ** descending (parameter bDescIdx==1) order of docid. Regardless, this

4291 ** function iterates from the end of the doclist to the beginning.

4292 */

4293 void sqlite3Fts3DoclistPrev(

4294 int bDescIdx, /* True if the doclist is desc */

4295 char aDoclist, / Pointer to entire doclist */

4296 int nDoclist, /* Length of aDoclist in bytes */

4297 char *ppIter, / IN/OUT: Iterator pointer */

4298 sqlite3_int64 piDocid, / IN/OUT: Docid pointer */

4299 int pnList, / OUT: List length pointer */

4300 u8 pbEof / OUT: End-of-file flag */

4301 ){

4302 char p = ppIter;

4303

4304 assert( nDoclist>0 );

4305 assert( *pbEof==0 );

4306 assert( p \|\| *piDocid==0 );

4307 assert( !p \|\| (p>aDoclist && p<&aDoclist[nDoclist]) );

4308

4309 if( p==0 ){

4310 sqlite3_int64 iDocid = 0;

4311 char *pNext = 0;

4312 char *pDocid = aDoclist;

4313 char *pEnd = &aDoclist[nDoclist];

4314 int iMul = 1;

4315

4316 while( pDocid<pEnd ){

4317 sqlite3_int64 iDelta;

4318 pDocid += sqlite3Fts3GetVarint(pDocid, &iDelta);

4319 iDocid += (iMul * iDelta);

4320 pNext = pDocid;

4321 fts3PoslistCopy(0, &pDocid);

4322 while( pDocid<pEnd && *pDocid==0 ) pDocid++;

4323 iMul = (bDescIdx ? -1 : 1);

4324 }

4325

4326 *pnList = (int)(pEnd - pNext);

4327 *ppIter = pNext;

4328 *piDocid = iDocid;

4329 }else{

4330 int iMul = (bDescIdx ? -1 : 1);

4331 sqlite3_int64 iDelta;

4332 fts3GetReverseVarint(&p, aDoclist, &iDelta);

4333 piDocid -= (iMul iDelta);

4334

4335 if( p==aDoclist ){

4336 *pbEof = 1;

4337 }else{

4338 char *pSave = p;

4339 fts3ReversePoslist(aDoclist, &p);

4340 *pnList = (int)(pSave - p);

4341 }

4342 *ppIter = p;

4343 }

4344 }

4345

4346 /*

4347 ** Iterate forwards through a doclist.

4348 */

4349 void sqlite3Fts3DoclistNext(

4350 int bDescIdx, /* True if the doclist is desc */

4351 char aDoclist, / Pointer to entire doclist */

4352 int nDoclist, /* Length of aDoclist in bytes */

4353 char *ppIter, / IN/OUT: Iterator pointer */

4354 sqlite3_int64 piDocid, / IN/OUT: Docid pointer */

4355 u8 pbEof / OUT: End-of-file flag */

4356 ){

4357 char p = ppIter;

4358

4359 assert( nDoclist>0 );

4360 assert( *pbEof==0 );

4361 assert( p \|\| *piDocid==0 );

4362 assert( !p \|\| (p>=aDoclist && p<=&aDoclist[nDoclist]) );

4363

4364 if( p==0 ){

4365 p = aDoclist;

4366 p += sqlite3Fts3GetVarint(p, piDocid);

4367 }else{

4368 fts3PoslistCopy(0, &p);

4369 while( p<&aDoclist[nDoclist] && *p==0 ) p++;

4370 if( p>=&aDoclist[nDoclist] ){

4371 *pbEof = 1;

4372 }else{

4373 sqlite3_int64 iVar;

4374 p += sqlite3Fts3GetVarint(p, &iVar);

4375 piDocid += ((bDescIdx ? -1 : 1) iVar);

4376 }

4377 }

4378

4379 *ppIter = p;

4380 }

4381

4382 /*

4383 ** Advance the iterator pDL to the next entry in pDL->aAll/nAll. Set *pbEof

4384 ** to true if EOF is reached.

4385 */

4386 static void fts3EvalDlPhraseNext(

4387 Fts3Table *pTab,

4388 Fts3Doclist *pDL,

4389 u8 *pbEof

4390 ){

4391 char pIter; / Used to iterate through aAll */

4392 char pEnd = &pDL->aAll[pDL->nAll]; / 1 byte past end of aAll */

4393

4394 if( pDL->pNextDocid ){

4395 pIter = pDL->pNextDocid;

4396 }else{

4397 pIter = pDL->aAll;

4398 }

4399

4400 if( pIter>=pEnd ){

4401 /* We have already reached the end of this doclist. EOF. */

4402 *pbEof = 1;

4403 }else{

4404 sqlite3_int64 iDelta;

4405 pIter += sqlite3Fts3GetVarint(pIter, &iDelta);

4406 if( pTab->bDescIdx==0 \|\| pDL->pNextDocid==0 ){

4407 pDL->iDocid += iDelta;

4408 }else{

4409 pDL->iDocid -= iDelta;

4410 }

4411 pDL->pList = pIter;

4412 fts3PoslistCopy(0, &pIter);

4413 pDL->nList = (int)(pIter - pDL->pList);

4414

4415 /* pIter now points just past the 0x00 that terminates the position-

4416 ** list for document pDL->iDocid. However, if this position-list was

4417 ** edited in place by fts3EvalNearTrim(), then pIter may not actually

4418 ** point to the start of the next docid value. The following line deals

4419 ** with this case by advancing pIter past the zero-padding added by

4420 ** fts3EvalNearTrim(). */

4421 while( pIter<pEnd && *pIter==0 ) pIter++;

4422

4423 pDL->pNextDocid = pIter;

4424 assert( pIter>=&pDL->aAll[pDL->nAll] \|\| *pIter );

4425 *pbEof = 0;

4426 }

4427 }

4428

4429 /*

4430 ** Helper type used by fts3EvalIncrPhraseNext() and incrPhraseTokenNext().

4431 */

4432 typedef struct TokenDoclist TokenDoclist;

4433 struct TokenDoclist {

4434 int bIgnore;

4435 sqlite3_int64 iDocid;

4436 char *pList;

4437 int nList;

4438 };

4439

4440 /*

4441 ** Token pToken is an incrementally loaded token that is part of a

4442 ** multi-token phrase. Advance it to the next matching document in the

4443 ** database and populate output variable *p with the details of the new

4444 ** entry. Or, if the iterator has reached EOF, set *pbEof to true.

4445 **

4446 ** If an error occurs, return an SQLite error code. Otherwise, return

4447 ** SQLITE_OK.

4448 */

4449 static int incrPhraseTokenNext(

4450 Fts3Table pTab, / Virtual table handle */

4451 Fts3Phrase pPhrase, / Phrase to advance token of */

4452 int iToken, /* Specific token to advance */

4453 TokenDoclist p, / OUT: Docid and doclist for new entry */

4454 u8 pbEof / OUT: True if iterator is at EOF */

4455 ){

4456 int rc = SQLITE_OK;

4457

4458 if( pPhrase->iDoclistToken==iToken ){

4459 assert( p->bIgnore==0 );

4460 assert( pPhrase->aToken[iToken].pSegcsr==0 );

4461 fts3EvalDlPhraseNext(pTab, &pPhrase->doclist, pbEof);

4462 p->pList = pPhrase->doclist.pList;

4463 p->nList = pPhrase->doclist.nList;

4464 p->iDocid = pPhrase->doclist.iDocid;

4465 }else{

4466 Fts3PhraseToken *pToken = &pPhrase->aToken[iToken];

4467 assert( pToken->pDeferred==0 );

4468 assert( pToken->pSegcsr \|\| pPhrase->iDoclistToken>=0 );

4469 if( pToken->pSegcsr ){

4470 assert( p->bIgnore==0 );

4471 rc = sqlite3Fts3MsrIncrNext(

4472 pTab, pToken->pSegcsr, &p->iDocid, &p->pList, &p->nList

4473 );

4474 if( p->pList==0 ) *pbEof = 1;

4475 }else{

4476 p->bIgnore = 1;

4477 }

4478 }

4479

4480 return rc;

4481 }

4482

4483

4484 /*

4485 ** The phrase iterator passed as the second argument:

4486 **

4487 ** * features at least one token that uses an incremental doclist, and

4488 **

4489 ** * does not contain any deferred tokens.

4490 **

4491 ** Advance it to the next matching documnent in the database and populate

4492 ** the Fts3Doclist.pList and nList fields.

4493 **

4494 ** If there is no "next" entry and no error occurs, then *pbEof is set to

4495 ** 1 before returning. Otherwise, if no error occurs and the iterator is

4496 ** successfully advanced, *pbEof is set to 0.

4497 **

4498 ** If an error occurs, return an SQLite error code. Otherwise, return

4499 ** SQLITE_OK.

4500 */

4501 static int fts3EvalIncrPhraseNext(

4502 Fts3Cursor pCsr, / FTS Cursor handle */

4503 Fts3Phrase p, / Phrase object to advance to next docid */

4504 u8 pbEof / OUT: Set to 1 if EOF */

4505 ){

4506 int rc = SQLITE_OK;

4507 Fts3Doclist *pDL = &p->doclist;

4508 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

4509 u8 bEof = 0;

4510

4511 /* This is only called if it is guaranteed that the phrase has at least

4512 ** one incremental token. In which case the bIncr flag is set. */

4513 assert( p->bIncr==1 );

4514

4515 if( p->nToken==1 && p->bIncr ){

4516 rc = sqlite3Fts3MsrIncrNext(pTab, p->aToken[0].pSegcsr,

4517 &pDL->iDocid, &pDL->pList, &pDL->nList

4518 );

4519 if( pDL->pList==0 ) bEof = 1;

4520 }else{

4521 int bDescDoclist = pCsr->bDesc;

4522 struct TokenDoclist a[MAX_INCR_PHRASE_TOKENS];

4523

4524 memset(a, 0, sizeof(a));

4525 assert( p->nToken<=MAX_INCR_PHRASE_TOKENS );

4526 assert( p->iDoclistToken<MAX_INCR_PHRASE_TOKENS );

4527

4528 while( bEof==0 ){

4529 int bMaxSet = 0;

4530 sqlite3_int64 iMax = 0; /* Largest docid for all iterators */

4531 int i; /* Used to iterate through tokens */

4532

4533 /* Advance the iterator for each token in the phrase once. */

4534 for(i=0; rc==SQLITE_OK && i<p->nToken && bEof==0; i++){

4535 rc = incrPhraseTokenNext(pTab, p, i, &a[i], &bEof);

4536 if( a[i].bIgnore==0 && (bMaxSet==0 \|\| DOCID_CMP(iMax, a[i].iDocid)<0) ){

4537 iMax = a[i].iDocid;

4538 bMaxSet = 1;

4539 }

4540 }

4541 assert( rc!=SQLITE_OK \|\| (p->nToken>=1 && a[p->nToken-1].bIgnore==0) );

4542 assert( rc!=SQLITE_OK \|\| bMaxSet );

4543

4544 /* Keep advancing iterators until they all point to the same document */

4545 for(i=0; i<p->nToken; i++){

4546 while( rc==SQLITE_OK && bEof==0

4547 && a[i].bIgnore==0 && DOCID_CMP(a[i].iDocid, iMax)<0

4548 ){

4549 rc = incrPhraseTokenNext(pTab, p, i, &a[i], &bEof);

4550 if( DOCID_CMP(a[i].iDocid, iMax)>0 ){

4551 iMax = a[i].iDocid;

4552 i = 0;

4553 }

4554 }

4555 }

4556

4557 /* Check if the current entries really are a phrase match */

4558 if( bEof==0 ){

4559 int nList = 0;

4560 int nByte = a[p->nToken-1].nList;

4561 char *aDoclist = sqlite3_malloc(nByte+1);

4562 if( !aDoclist ) return SQLITE_NOMEM;

4563 memcpy(aDoclist, a[p->nToken-1].pList, nByte+1);

4564

4565 for(i=0; i<(p->nToken-1); i++){

4566 if( a[i].bIgnore==0 ){

4567 char *pL = a[i].pList;

4568 char *pR = aDoclist;

4569 char *pOut = aDoclist;

4570 int nDist = p->nToken-1-i;

4571 int res = fts3PoslistPhraseMerge(&pOut, nDist, 0, 1, &pL, &pR);

4572 if( res==0 ) break;

4573 nList = (int)(pOut - aDoclist);

4574 }

4575 }

4576 if( i==(p->nToken-1) ){

4577 pDL->iDocid = iMax;

4578 pDL->pList = aDoclist;

4579 pDL->nList = nList;

4580 pDL->bFreeList = 1;

4581 break;

4582 }

4583 sqlite3_free(aDoclist);

4584 }

4585 }

4586 }

4587

4588 *pbEof = bEof;

4589 return rc;

4590 }

4591

4592 /*

4593 ** Attempt to move the phrase iterator to point to the next matching docid.

4594 ** If an error occurs, return an SQLite error code. Otherwise, return

4595 ** SQLITE_OK.

4596 **

4597 ** If there is no "next" entry and no error occurs, then *pbEof is set to

4598 ** 1 before returning. Otherwise, if no error occurs and the iterator is

4599 ** successfully advanced, *pbEof is set to 0.

4600 */

4601 static int fts3EvalPhraseNext(

4602 Fts3Cursor pCsr, / FTS Cursor handle */

4603 Fts3Phrase p, / Phrase object to advance to next docid */

4604 u8 pbEof / OUT: Set to 1 if EOF */

4605 ){

4606 int rc = SQLITE_OK;

4607 Fts3Doclist *pDL = &p->doclist;

4608 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

4609

4610 if( p->bIncr ){

4611 rc = fts3EvalIncrPhraseNext(pCsr, p, pbEof);

4612 }else if( pCsr->bDesc!=pTab->bDescIdx && pDL->nAll ){

4613 sqlite3Fts3DoclistPrev(pTab->bDescIdx, pDL->aAll, pDL->nAll,

4614 &pDL->pNextDocid, &pDL->iDocid, &pDL->nList, pbEof

4615 );

4616 pDL->pList = pDL->pNextDocid;

4617 }else{

4618 fts3EvalDlPhraseNext(pTab, pDL, pbEof);

4619 }

4620

4621 return rc;

4622 }

4623

4624 /*

4625 **

4626 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.

4627 ** Otherwise, fts3EvalPhraseStart() is called on all phrases within the

4628 ** expression. Also the Fts3Expr.bDeferred variable is set to true for any

4629 ** expressions for which all descendent tokens are deferred.

4630 **

4631 ** If parameter bOptOk is zero, then it is guaranteed that the

4632 ** Fts3Phrase.doclist.aAll/nAll variables contain the entire doclist for

4633 ** each phrase in the expression (subject to deferred token processing).

4634 ** Or, if bOptOk is non-zero, then one or more tokens within the expression

4635 ** may be loaded incrementally, meaning doclist.aAll/nAll is not available.

4636 **

4637 ** If an error occurs within this function, *pRc is set to an SQLite error

4638 ** code before returning.

4639 */

4640 static void fts3EvalStartReaders(

4641 Fts3Cursor pCsr, / FTS Cursor handle */

4642 Fts3Expr pExpr, / Expression to initialize phrases in */

4643 int pRc / IN/OUT: Error code */

4644 ){

4645 if( pExpr && SQLITE_OK==*pRc ){

4646 if( pExpr->eType==FTSQUERY_PHRASE ){

4647 int nToken = pExpr->pPhrase->nToken;

4648 if( nToken ){

4649 int i;

4650 for(i=0; i<nToken; i++){

4651 if( pExpr->pPhrase->aToken[i].pDeferred==0 ) break;

4652 }

4653 pExpr->bDeferred = (i==nToken);

4654 }

4655 *pRc = fts3EvalPhraseStart(pCsr, 1, pExpr->pPhrase);

4656 }else{

4657 fts3EvalStartReaders(pCsr, pExpr->pLeft, pRc);

4658 fts3EvalStartReaders(pCsr, pExpr->pRight, pRc);

4659 pExpr->bDeferred = (pExpr->pLeft->bDeferred && pExpr->pRight->bDeferred);

4660 }

4661 }

4662 }

4663

4664 /*

4665 ** An array of the following structures is assembled as part of the process

4666 ** of selecting tokens to defer before the query starts executing (as part

4667 ** of the xFilter() method). There is one element in the array for each

4668 ** token in the FTS expression.

4669 **

4670 ** Tokens are divided into AND/NEAR clusters. All tokens in a cluster belong

4671 ** to phrases that are connected only by AND and NEAR operators (not OR or

4672 ** NOT). When determining tokens to defer, each AND/NEAR cluster is considered

4673 ** separately. The root of a tokens AND/NEAR cluster is stored in

4674 ** Fts3TokenAndCost.pRoot.

4675 */

4676 typedef struct Fts3TokenAndCost Fts3TokenAndCost;

4677 struct Fts3TokenAndCost {

4678 Fts3Phrase pPhrase; / The phrase the token belongs to */

4679 int iToken; /* Position of token in phrase */

4680 Fts3PhraseToken pToken; / The token itself */

4681 Fts3Expr pRoot; / Root of NEAR/AND cluster */

4682 int nOvfl; /* Number of overflow pages to load doclist */

4683 int iCol; /* The column the token must match */

4684 };

4685

4686 /*

4687 ** This function is used to populate an allocated Fts3TokenAndCost array.

4688 **

4689 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.

4690 ** Otherwise, if an error occurs during execution, *pRc is set to an

4691 ** SQLite error code.

4692 */

4693 static void fts3EvalTokenCosts(

4694 Fts3Cursor pCsr, / FTS Cursor handle */

4695 Fts3Expr pRoot, / Root of current AND/NEAR cluster */

4696 Fts3Expr pExpr, / Expression to consider */

4697 Fts3TokenAndCost *ppTC, / Write new entries to (ppTC)++ */

4698 Fts3Expr **ppOr, / Write new OR root to (ppOr)++ */

4699 int pRc / IN/OUT: Error code */

4700 ){

4701 if( *pRc==SQLITE_OK ){

4702 if( pExpr->eType==FTSQUERY_PHRASE ){

4703 Fts3Phrase *pPhrase = pExpr->pPhrase;

4704 int i;

4705 for(i=0; *pRc==SQLITE_OK && i<pPhrase->nToken; i++){

4706 Fts3TokenAndCost pTC = (ppTC)++;

4707 pTC->pPhrase = pPhrase;

4708 pTC->iToken = i;

4709 pTC->pRoot = pRoot;

4710 pTC->pToken = &pPhrase->aToken[i];

4711 pTC->iCol = pPhrase->iColumn;

4712 *pRc = sqlite3Fts3MsrOvfl(pCsr, pTC->pToken->pSegcsr, &pTC->nOvfl);

4713 }

4714 }else if( pExpr->eType!=FTSQUERY_NOT ){

4715 assert( pExpr->eType==FTSQUERY_OR

4716 \|\| pExpr->eType==FTSQUERY_AND

4717 \|\| pExpr->eType==FTSQUERY_NEAR

4718 );

4719 assert( pExpr->pLeft && pExpr->pRight );

4720 if( pExpr->eType==FTSQUERY_OR ){

4721 pRoot = pExpr->pLeft;

4722 **ppOr = pRoot;

4723 (*ppOr)++;

4724 }

4725 fts3EvalTokenCosts(pCsr, pRoot, pExpr->pLeft, ppTC, ppOr, pRc);

4726 if( pExpr->eType==FTSQUERY_OR ){

4727 pRoot = pExpr->pRight;

4728 **ppOr = pRoot;

4729 (*ppOr)++;

4730 }

4731 fts3EvalTokenCosts(pCsr, pRoot, pExpr->pRight, ppTC, ppOr, pRc);

4732 }

4733 }

4734 }

4735

4736 /*

4737 ** Determine the average document (row) size in pages. If successful,

4738 ** write this value to *pnPage and return SQLITE_OK. Otherwise, return

4739 ** an SQLite error code.

4740 **

4741 ** The average document size in pages is calculated by first calculating

4742 ** determining the average size in bytes, B. If B is less than the amount

4743 ** of data that will fit on a single leaf page of an intkey table in

4744 ** this database, then the average docsize is 1. Otherwise, it is 1 plus

4745 ** the number of overflow pages consumed by a record B bytes in size.

4746 */

4747 static int fts3EvalAverageDocsize(Fts3Cursor pCsr, int pnPage){

4748 if( pCsr->nRowAvg==0 ){

4749 /* The average document size, which is required to calculate the cost

4750 ** of each doclist, has not yet been determined. Read the required

4751 ** data from the %_stat table to calculate it.

4752 **

4753 ** Entry 0 of the %_stat table is a blob containing (nCol+1) FTS3

4754 ** varints, where nCol is the number of columns in the FTS3 table.

4755 ** The first varint is the number of documents currently stored in

4756 ** the table. The following nCol varints contain the total amount of

4757 ** data stored in all rows of each column of the table, from left

4758 ** to right.

4759 */

4760 int rc;

4761 Fts3Table p = (Fts3Table)pCsr->base.pVtab;

4762 sqlite3_stmt *pStmt;

4763 sqlite3_int64 nDoc = 0;

4764 sqlite3_int64 nByte = 0;

4765 const char *pEnd;

4766 const char *a;

4767

4768 rc = sqlite3Fts3SelectDoctotal(p, &pStmt);

4769 if( rc!=SQLITE_OK ) return rc;

4770 a = sqlite3_column_blob(pStmt, 0);

4771 assert( a );

4772

4773 pEnd = &a[sqlite3_column_bytes(pStmt, 0)];

4774 a += sqlite3Fts3GetVarint(a, &nDoc);

4775 while( a<pEnd ){

4776 a += sqlite3Fts3GetVarint(a, &nByte);

4777 }

4778 if( nDoc==0 \|\| nByte==0 ){

4779 sqlite3_reset(pStmt);

4780 return FTS_CORRUPT_VTAB;

4781 }

4782

4783 pCsr->nDoc = nDoc;

4784 pCsr->nRowAvg = (int)(((nByte / nDoc) + p->nPgsz) / p->nPgsz);

4785 assert( pCsr->nRowAvg>0 );

4786 rc = sqlite3_reset(pStmt);

4787 if( rc!=SQLITE_OK ) return rc;

4788 }

4789

4790 *pnPage = pCsr->nRowAvg;

4791 return SQLITE_OK;

4792 }

4793

4794 /*

4795 ** This function is called to select the tokens (if any) that will be

4796 ** deferred. The array aTC[] has already been populated when this is

4797 ** called.

4798 **

4799 ** This function is called once for each AND/NEAR cluster in the

4800 ** expression. Each invocation determines which tokens to defer within

4801 ** the cluster with root node pRoot. See comments above the definition

4802 ** of struct Fts3TokenAndCost for more details.

4803 **

4804 ** If no error occurs, SQLITE_OK is returned and sqlite3Fts3DeferToken()

4805 ** called on each token to defer. Otherwise, an SQLite error code is

4806 ** returned.

4807 */

4808 static int fts3EvalSelectDeferred(

4809 Fts3Cursor pCsr, / FTS Cursor handle */

4810 Fts3Expr pRoot, / Consider tokens with this root node */

4811 Fts3TokenAndCost aTC, / Array of expression tokens and costs */

4812 int nTC /* Number of entries in aTC[] */

4813 ){

4814 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

4815 int nDocSize = 0; /* Number of pages per doc loaded */

4816 int rc = SQLITE_OK; /* Return code */

4817 int ii; /* Iterator variable for various purposes */

4818 int nOvfl = 0; /* Total overflow pages used by doclists */

4819 int nToken = 0; /* Total number of tokens in cluster */

4820

4821 int nMinEst = 0; /* The minimum count for any phrase so far. */

4822 int nLoad4 = 1; /* (Phrases that will be loaded)^4. */

4823

4824 /* Tokens are never deferred for FTS tables created using the content=xxx

4825 ** option. The reason being that it is not guaranteed that the content

4826 ** table actually contains the same data as the index. To prevent this from

4827 ** causing any problems, the deferred token optimization is completely

4828 ** disabled for content=xxx tables. */

4829 if( pTab->zContentTbl ){

4830 return SQLITE_OK;

4831 }

4832

4833 /* Count the tokens in this AND/NEAR cluster. If none of the doclists

4834 ** associated with the tokens spill onto overflow pages, or if there is

4835 ** only 1 token, exit early. No tokens to defer in this case. */

4836 for(ii=0; ii<nTC; ii++){

4837 if( aTC[ii].pRoot==pRoot ){

4838 nOvfl += aTC[ii].nOvfl;

4839 nToken++;

4840 }

4841 }

4842 if( nOvfl==0 \|\| nToken<2 ) return SQLITE_OK;

4843

4844 /* Obtain the average docsize (in pages). */

4845 rc = fts3EvalAverageDocsize(pCsr, &nDocSize);

4846 assert( rc!=SQLITE_OK \|\| nDocSize>0 );

4847

4848

4849 /* Iterate through all tokens in this AND/NEAR cluster, in ascending order

4850 ** of the number of overflow pages that will be loaded by the pager layer

4851 ** to retrieve the entire doclist for the token from the full-text index.

4852 ** Load the doclists for tokens that are either:

4853 **

4854 ** a. The cheapest token in the entire query (i.e. the one visited by the

4855 ** first iteration of this loop), or

4856 **

4857 ** b. Part of a multi-token phrase.

4858 **

4859 ** After each token doclist is loaded, merge it with the others from the

4860 ** same phrase and count the number of documents that the merged doclist

4861 ** contains. Set variable "nMinEst" to the smallest number of documents in

4862 ** any phrase doclist for which 1 or more token doclists have been loaded.

4863 ** Let nOther be the number of other phrases for which it is certain that

4864 ** one or more tokens will not be deferred.

4865 **

4866 ** Then, for each token, defer it if loading the doclist would result in

4867 ** loading N or more overflow pages into memory, where N is computed as:

4868 **

4869 ** (nMinEst + 4^nOther - 1) / (4^nOther)

4870 */

4871 for(ii=0; ii<nToken && rc==SQLITE_OK; ii++){

4872 int iTC; /* Used to iterate through aTC[] array. */

4873 Fts3TokenAndCost pTC = 0; / Set to cheapest remaining token. */

4874

4875 /* Set pTC to point to the cheapest remaining token. */

4876 for(iTC=0; iTC<nTC; iTC++){

4877 if( aTC[iTC].pToken && aTC[iTC].pRoot==pRoot

4878 && (!pTC \|\| aTC[iTC].nOvfl<pTC->nOvfl)

4879 ){

4880 pTC = &aTC[iTC];

4881 }

4882 }

4883 assert( pTC );

4884

4885 if( ii && pTC->nOvfl>=((nMinEst+(nLoad4/4)-1)/(nLoad4/4))*nDocSize ){

4886 /* The number of overflow pages to load for this (and therefore all

4887 ** subsequent) tokens is greater than the estimated number of pages

4888 ** that will be loaded if all subsequent tokens are deferred.

4889 */

4890 Fts3PhraseToken *pToken = pTC->pToken;

4891 rc = sqlite3Fts3DeferToken(pCsr, pToken, pTC->iCol);

4892 fts3SegReaderCursorFree(pToken->pSegcsr);

4893 pToken->pSegcsr = 0;

4894 }else{

4895 /* Set nLoad4 to the value of (4^nOther) for the next iteration of the

4896 ** for-loop. Except, limit the value to 2^24 to prevent it from

4897 ** overflowing the 32-bit integer it is stored in. */

4898 if( ii<12 ) nLoad4 = nLoad4*4;

4899

4900 if( ii==0 \|\| (pTC->pPhrase->nToken>1 && ii!=nToken-1) ){

4901 /* Either this is the cheapest token in the entire query, or it is

4902 ** part of a multi-token phrase. Either way, the entire doclist will

4903 ** (eventually) be loaded into memory. It may as well be now. */

4904 Fts3PhraseToken *pToken = pTC->pToken;

4905 int nList = 0;

4906 char *pList = 0;

4907 rc = fts3TermSelect(pTab, pToken, pTC->iCol, &nList, &pList);

4908 assert( rc==SQLITE_OK \|\| pList==0 );

4909 if( rc==SQLITE_OK ){

4910 rc = fts3EvalPhraseMergeToken(

4911 pTab, pTC->pPhrase, pTC->iToken,pList,nList

4912 );

4913 }

4914 if( rc==SQLITE_OK ){

4915 int nCount;

4916 nCount = fts3DoclistCountDocids(

4917 pTC->pPhrase->doclist.aAll, pTC->pPhrase->doclist.nAll

4918 );

4919 if( ii==0 \|\| nCount<nMinEst ) nMinEst = nCount;

4920 }

4921 }

4922 }

4923 pTC->pToken = 0;

4924 }

4925

4926 return rc;

4927 }

4928

4929 /*

4930 ** This function is called from within the xFilter method. It initializes

4931 ** the full-text query currently stored in pCsr->pExpr. To iterate through

4932 ** the results of a query, the caller does:

4933 **

4934 ** fts3EvalStart(pCsr);

4935 ** while( 1 ){

4936 ** fts3EvalNext(pCsr);

4937 ** if( pCsr->bEof ) break;

4938 ** ... return row pCsr->iPrevId to the caller ...

4939 ** }

4940 */

4941 static int fts3EvalStart(Fts3Cursor *pCsr){

4942 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

4943 int rc = SQLITE_OK;

4944 int nToken = 0;

4945 int nOr = 0;

4946

4947 /* Allocate a MultiSegReader for each token in the expression. */

4948 fts3EvalAllocateReaders(pCsr, pCsr->pExpr, &nToken, &nOr, &rc);

4949

4950 /* Determine which, if any, tokens in the expression should be deferred. */

4951 #ifndef SQLITE_DISABLE_FTS4_DEFERRED

4952 if( rc==SQLITE_OK && nToken>1 && pTab->bFts4 ){

4953 Fts3TokenAndCost *aTC;

4954 Fts3Expr **apOr;

4955 aTC = (Fts3TokenAndCost *)sqlite3_malloc(

4956 sizeof(Fts3TokenAndCost) * nToken

4957 + sizeof(Fts3Expr ) nOr * 2

4958 );

4959 apOr = (Fts3Expr **)&aTC[nToken];

4960

4961 if( !aTC ){

4962 rc = SQLITE_NOMEM;

4963 }else{

4964 int ii;

4965 Fts3TokenAndCost *pTC = aTC;

4966 Fts3Expr **ppOr = apOr;

4967

4968 fts3EvalTokenCosts(pCsr, 0, pCsr->pExpr, &pTC, &ppOr, &rc);

4969 nToken = (int)(pTC-aTC);

4970 nOr = (int)(ppOr-apOr);

4971

4972 if( rc==SQLITE_OK ){

4973 rc = fts3EvalSelectDeferred(pCsr, 0, aTC, nToken);

4974 for(ii=0; rc==SQLITE_OK && ii<nOr; ii++){

4975 rc = fts3EvalSelectDeferred(pCsr, apOr[ii], aTC, nToken);

4976 }

4977 }

4978

4979 sqlite3_free(aTC);

4980 }

4981 }

4982 #endif

4983

4984 fts3EvalStartReaders(pCsr, pCsr->pExpr, &rc);

4985 return rc;

4986 }

4987

4988 /*

4989 ** Invalidate the current position list for phrase pPhrase.

4990 */

4991 static void fts3EvalInvalidatePoslist(Fts3Phrase *pPhrase){

4992 if( pPhrase->doclist.bFreeList ){

4993 sqlite3_free(pPhrase->doclist.pList);

4994 }

4995 pPhrase->doclist.pList = 0;

4996 pPhrase->doclist.nList = 0;

4997 pPhrase->doclist.bFreeList = 0;

4998 }

4999

5000 /*

5001 ** This function is called to edit the position list associated with

5002 ** the phrase object passed as the fifth argument according to a NEAR

5003 ** condition. For example:

5004 **

5005 ** abc NEAR/5 "def ghi"

5006 **

5007 ** Parameter nNear is passed the NEAR distance of the expression (5 in

5008 ** the example above). When this function is called, *paPoslist points to

5009 ** the position list, and *pnToken is the number of phrase tokens in, the

5010 ** phrase on the other side of the NEAR operator to pPhrase. For example,

5011 ** if pPhrase refers to the "def ghi" phrase, then *paPoslist points to

5012 ** the position list associated with phrase "abc".

5013 **

5014 ** All positions in the pPhrase position list that are not sufficiently

5015 ** close to a position in the *paPoslist position list are removed. If this

5016 ** leaves 0 positions, zero is returned. Otherwise, non-zero.

5017 **

5018 ** Before returning, *paPoslist is set to point to the position lsit

5019 ** associated with pPhrase. And *pnToken is set to the number of tokens in

5020 ** pPhrase.

5021 */

5022 static int fts3EvalNearTrim(

5023 int nNear, /* NEAR distance. As in "NEAR/nNear". */

5024 char aTmp, / Temporary space to use */

5025 char *paPoslist, / IN/OUT: Position list */

5026 int pnToken, / IN/OUT: Tokens in phrase of paPoslist /

5027 Fts3Phrase pPhrase / The phrase object to trim the doclist of */

5028 ){

5029 int nParam1 = nNear + pPhrase->nToken;

5030 int nParam2 = nNear + *pnToken;

5031 int nNew;

5032 char *p2;

5033 char *pOut;

5034 int res;

5035

5036 assert( pPhrase->doclist.pList );

5037

5038 p2 = pOut = pPhrase->doclist.pList;

5039 res = fts3PoslistNearMerge(

5040 &pOut, aTmp, nParam1, nParam2, paPoslist, &p2

5041 );

5042 if( res ){

5043 nNew = (int)(pOut - pPhrase->doclist.pList) - 1;

5044 assert( pPhrase->doclist.pList[nNew]=='\0' );

5045 assert( nNew<=pPhrase->doclist.nList && nNew>0 );

5046 memset(&pPhrase->doclist.pList[nNew], 0, pPhrase->doclist.nList - nNew);

5047 pPhrase->doclist.nList = nNew;

5048 *paPoslist = pPhrase->doclist.pList;

5049 *pnToken = pPhrase->nToken;

5050 }

5051

5052 return res;

5053 }

5054

5055 /*

5056 ** This function is a no-op if *pRc is other than SQLITE_OK when it is called.

5057 ** Otherwise, it advances the expression passed as the second argument to

5058 ** point to the next matching row in the database. Expressions iterate through

5059 ** matching rows in docid order. Ascending order if Fts3Cursor.bDesc is zero,

5060 ** or descending if it is non-zero.

5061 **

5062 ** If an error occurs, *pRc is set to an SQLite error code. Otherwise, if

5063 ** successful, the following variables in pExpr are set:

5064 **

5065 ** Fts3Expr.bEof (non-zero if EOF - there is no next row)

5066 ** Fts3Expr.iDocid (valid if bEof==0. The docid of the next row)

5067 **

5068 ** If the expression is of type FTSQUERY_PHRASE, and the expression is not

5069 ** at EOF, then the following variables are populated with the position list

5070 ** for the phrase for the visited row:

5071 **

5072 ** FTs3Expr.pPhrase->doclist.nList (length of pList in bytes)

5073 ** FTs3Expr.pPhrase->doclist.pList (pointer to position list)

5074 **

5075 ** It says above that this function advances the expression to the next

5076 ** matching row. This is usually true, but there are the following exceptions:

5077 **

5078 ** 1. Deferred tokens are not taken into account. If a phrase consists

5079 ** entirely of deferred tokens, it is assumed to match every row in

5080 ** the db. In this case the position-list is not populated at all.

5081 **

5082 ** Or, if a phrase contains one or more deferred tokens and one or

5083 ** more non-deferred tokens, then the expression is advanced to the

5084 ** next possible match, considering only non-deferred tokens. In other

5085 ** words, if the phrase is "A B C", and "B" is deferred, the expression

5086 ** is advanced to the next row that contains an instance of "A * C",

5087 ** where "*" may match any single token. The position list in this case

5088 ** is populated as for "A * C" before returning.

5089 **

5090 ** 2. NEAR is treated as AND. If the expression is "x NEAR y", it is

5091 ** advanced to point to the next row that matches "x AND y".

5092 **

5093 ** See sqlite3Fts3EvalTestDeferred() for details on testing if a row is

5094 ** really a match, taking into account deferred tokens and NEAR operators.

5095 */

5096 static void fts3EvalNextRow(

5097 Fts3Cursor pCsr, / FTS Cursor handle */

5098 Fts3Expr pExpr, / Expr. to advance to next matching row */

5099 int pRc / IN/OUT: Error code */

5100 ){

5101 if( *pRc==SQLITE_OK ){

5102 int bDescDoclist = pCsr->bDesc; /* Used by DOCID_CMP() macro */

5103 assert( pExpr->bEof==0 );

5104 pExpr->bStart = 1;

5105

5106 switch( pExpr->eType ){

5107 case FTSQUERY_NEAR:

5108 case FTSQUERY_AND: {

5109 Fts3Expr *pLeft = pExpr->pLeft;

5110 Fts3Expr *pRight = pExpr->pRight;

5111 assert( !pLeft->bDeferred \|\| !pRight->bDeferred );

5112

5113 if( pLeft->bDeferred ){

5114 /* LHS is entirely deferred. So we assume it matches every row.

5115 ** Advance the RHS iterator to find the next row visited. */

5116 fts3EvalNextRow(pCsr, pRight, pRc);

5117 pExpr->iDocid = pRight->iDocid;

5118 pExpr->bEof = pRight->bEof;

5119 }else if( pRight->bDeferred ){

5120 /* RHS is entirely deferred. So we assume it matches every row.

5121 ** Advance the LHS iterator to find the next row visited. */

5122 fts3EvalNextRow(pCsr, pLeft, pRc);

5123 pExpr->iDocid = pLeft->iDocid;

5124 pExpr->bEof = pLeft->bEof;

5125 }else{

5126 /* Neither the RHS or LHS are deferred. */

5127 fts3EvalNextRow(pCsr, pLeft, pRc);

5128 fts3EvalNextRow(pCsr, pRight, pRc);

5129 while( !pLeft->bEof && !pRight->bEof && *pRc==SQLITE_OK ){

5130 sqlite3_int64 iDiff = DOCID_CMP(pLeft->iDocid, pRight->iDocid);

5131 if( iDiff==0 ) break;

5132 if( iDiff<0 ){

5133 fts3EvalNextRow(pCsr, pLeft, pRc);

5134 }else{

5135 fts3EvalNextRow(pCsr, pRight, pRc);

5136 }

5137 }

5138 pExpr->iDocid = pLeft->iDocid;

5139 pExpr->bEof = (pLeft->bEof \|\| pRight->bEof);

5140 if( pExpr->eType==FTSQUERY_NEAR && pExpr->bEof ){

5141 if( pRight->pPhrase && pRight->pPhrase->doclist.aAll ){

5142 Fts3Doclist *pDl = &pRight->pPhrase->doclist;

5143 while( *pRc==SQLITE_OK && pRight->bEof==0 ){

5144 memset(pDl->pList, 0, pDl->nList);

5145 fts3EvalNextRow(pCsr, pRight, pRc);

5146 }

5147 }

5148 if( pLeft->pPhrase && pLeft->pPhrase->doclist.aAll ){

5149 Fts3Doclist *pDl = &pLeft->pPhrase->doclist;

5150 while( *pRc==SQLITE_OK && pLeft->bEof==0 ){

5151 memset(pDl->pList, 0, pDl->nList);

5152 fts3EvalNextRow(pCsr, pLeft, pRc);

5153 }

5154 }

5155 }

5156 }

5157 break;

5158 }

5159

5160 case FTSQUERY_OR: {

5161 Fts3Expr *pLeft = pExpr->pLeft;

5162 Fts3Expr *pRight = pExpr->pRight;

5163 sqlite3_int64 iCmp = DOCID_CMP(pLeft->iDocid, pRight->iDocid);

5164

5165 assert( pLeft->bStart \|\| pLeft->iDocid==pRight->iDocid );

5166 assert( pRight->bStart \|\| pLeft->iDocid==pRight->iDocid );

5167

5168 if( pRight->bEof \|\| (pLeft->bEof==0 && iCmp<0) ){

5169 fts3EvalNextRow(pCsr, pLeft, pRc);

5170 }else if( pLeft->bEof \|\| (pRight->bEof==0 && iCmp>0) ){

5171 fts3EvalNextRow(pCsr, pRight, pRc);

5172 }else{

5173 fts3EvalNextRow(pCsr, pLeft, pRc);

5174 fts3EvalNextRow(pCsr, pRight, pRc);

5175 }

5176

5177 pExpr->bEof = (pLeft->bEof && pRight->bEof);

5178 iCmp = DOCID_CMP(pLeft->iDocid, pRight->iDocid);

5179 if( pRight->bEof \|\| (pLeft->bEof==0 && iCmp<0) ){

5180 pExpr->iDocid = pLeft->iDocid;

5181 }else{

5182 pExpr->iDocid = pRight->iDocid;

5183 }

5184

5185 break;

5186 }

5187

5188 case FTSQUERY_NOT: {

5189 Fts3Expr *pLeft = pExpr->pLeft;

5190 Fts3Expr *pRight = pExpr->pRight;

5191

5192 if( pRight->bStart==0 ){

5193 fts3EvalNextRow(pCsr, pRight, pRc);

5194 assert( *pRc!=SQLITE_OK \|\| pRight->bStart );

5195 }

5196

5197 fts3EvalNextRow(pCsr, pLeft, pRc);

5198 if( pLeft->bEof==0 ){

5199 while( !*pRc

5200 && !pRight->bEof

5201 && DOCID_CMP(pLeft->iDocid, pRight->iDocid)>0

5202 ){

5203 fts3EvalNextRow(pCsr, pRight, pRc);

5204 }

5205 }

5206 pExpr->iDocid = pLeft->iDocid;

5207 pExpr->bEof = pLeft->bEof;

5208 break;

5209 }

5210

5211 default: {

5212 Fts3Phrase *pPhrase = pExpr->pPhrase;

5213 fts3EvalInvalidatePoslist(pPhrase);

5214 *pRc = fts3EvalPhraseNext(pCsr, pPhrase, &pExpr->bEof);

5215 pExpr->iDocid = pPhrase->doclist.iDocid;

5216 break;

5217 }

5218 }

5219 }

5220 }

5221

5222 /*

5223 ** If *pRc is not SQLITE_OK, or if pExpr is not the root node of a NEAR

5224 ** cluster, then this function returns 1 immediately.

5225 **

5226 ** Otherwise, it checks if the current row really does match the NEAR

5227 ** expression, using the data currently stored in the position lists

5228 ** (Fts3Expr->pPhrase.doclist.pList/nList) for each phrase in the expression.

5229 **

5230 ** If the current row is a match, the position list associated with each

5231 ** phrase in the NEAR expression is edited in place to contain only those

5232 ** phrase instances sufficiently close to their peers to satisfy all NEAR

5233 ** constraints. In this case it returns 1. If the NEAR expression does not

5234 ** match the current row, 0 is returned. The position lists may or may not

5235 ** be edited if 0 is returned.

5236 */

5237 static int fts3EvalNearTest(Fts3Expr pExpr, int pRc){

5238 int res = 1;

5239

5240 /* The following block runs if pExpr is the root of a NEAR query.

5241 ** For example, the query:

5242 **

5243 ** "w" NEAR "x" NEAR "y" NEAR "z"

5244 **

5245 ** which is represented in tree form as:

5246 **

5247 ** \|

5248 ** +--NEAR--+ <-- root of NEAR query

5249 ** \| \|

5250 ** +--NEAR--+ "z"

5251 ** \| \|

5252 ** +--NEAR--+ "y"

5253 ** \| \|

5254 ** "w" "x"

5255 **

5256 ** The right-hand child of a NEAR node is always a phrase. The

5257 ** left-hand child may be either a phrase or a NEAR node. There are

5258 ** no exceptions to this - it's the way the parser in fts3_expr.c works.

5259 */

5260 if( *pRc==SQLITE_OK

5261 && pExpr->eType==FTSQUERY_NEAR

5262 && pExpr->bEof==0

5263 && (pExpr->pParent==0 \|\| pExpr->pParent->eType!=FTSQUERY_NEAR)

5264 ){

5265 Fts3Expr *p;

5266 int nTmp = 0; /* Bytes of temp space */

5267 char aTmp; / Temp space for PoslistNearMerge() */

5268

5269 /* Allocate temporary working space. */

5270 for(p=pExpr; p->pLeft; p=p->pLeft){

5271 nTmp += p->pRight->pPhrase->doclist.nList;

5272 }

5273 nTmp += p->pPhrase->doclist.nList;

5274 if( nTmp==0 ){

5275 res = 0;

5276 }else{

5277 aTmp = sqlite3_malloc(nTmp*2);

5278 if( !aTmp ){

5279 *pRc = SQLITE_NOMEM;

5280 res = 0;

5281 }else{

5282 char *aPoslist = p->pPhrase->doclist.pList;

5283 int nToken = p->pPhrase->nToken;

5284

5285 for(p=p->pParent;res && p && p->eType==FTSQUERY_NEAR; p=p->pParent){

5286 Fts3Phrase *pPhrase = p->pRight->pPhrase;

5287 int nNear = p->nNear;

5288 res = fts3EvalNearTrim(nNear, aTmp, &aPoslist, &nToken, pPhrase);

5289 }

5290

5291 aPoslist = pExpr->pRight->pPhrase->doclist.pList;

5292 nToken = pExpr->pRight->pPhrase->nToken;

5293 for(p=pExpr->pLeft; p && res; p=p->pLeft){

5294 int nNear;

5295 Fts3Phrase *pPhrase;

5296 assert( p->pParent && p->pParent->pLeft==p );

5297 nNear = p->pParent->nNear;

5298 pPhrase = (

5299 p->eType==FTSQUERY_NEAR ? p->pRight->pPhrase : p->pPhrase

5300 );

5301 res = fts3EvalNearTrim(nNear, aTmp, &aPoslist, &nToken, pPhrase);

5302 }

5303 }

5304

5305 sqlite3_free(aTmp);

5306 }

5307 }

5308

5309 return res;

5310 }

5311

5312 /*

5313 ** This function is a helper function for sqlite3Fts3EvalTestDeferred().

5314 ** Assuming no error occurs or has occurred, It returns non-zero if the

5315 ** expression passed as the second argument matches the row that pCsr

5316 ** currently points to, or zero if it does not.

5317 **

5318 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.

5319 ** If an error occurs during execution of this function, *pRc is set to

5320 ** the appropriate SQLite error code. In this case the returned value is

5321 ** undefined.

5322 */

5323 static int fts3EvalTestExpr(

5324 Fts3Cursor pCsr, / FTS cursor handle */

5325 Fts3Expr pExpr, / Expr to test. May or may not be root. */

5326 int pRc / IN/OUT: Error code */

5327 ){

5328 int bHit = 1; /* Return value */

5329 if( *pRc==SQLITE_OK ){

5330 switch( pExpr->eType ){

5331 case FTSQUERY_NEAR:

5332 case FTSQUERY_AND:

5333 bHit = (

5334 fts3EvalTestExpr(pCsr, pExpr->pLeft, pRc)

5335 && fts3EvalTestExpr(pCsr, pExpr->pRight, pRc)

5336 && fts3EvalNearTest(pExpr, pRc)

5337 );

5338

5339 /* If the NEAR expression does not match any rows, zero the doclist for

5340 ** all phrases involved in the NEAR. This is because the snippet(),

5341 ** offsets() and matchinfo() functions are not supposed to recognize

5342 ** any instances of phrases that are part of unmatched NEAR queries.

5343 ** For example if this expression:

5344 **

5345 ** ... MATCH 'a OR (b NEAR c)'

5346 **

5347 ** is matched against a row containing:

5348 **

5349 ** 'a b d e'

5350 **

5351 ** then any snippet() should ony highlight the "a" term, not the "b"

5352 ** (as "b" is part of a non-matching NEAR clause).

5353 */

5354 if( bHit==0

5355 && pExpr->eType==FTSQUERY_NEAR

5356 && (pExpr->pParent==0 \|\| pExpr->pParent->eType!=FTSQUERY_NEAR)

5357 ){

5358 Fts3Expr *p;

5359 for(p=pExpr; p->pPhrase==0; p=p->pLeft){

5360 if( p->pRight->iDocid==pCsr->iPrevId ){

5361 fts3EvalInvalidatePoslist(p->pRight->pPhrase);

5362 }

5363 }

5364 if( p->iDocid==pCsr->iPrevId ){

5365 fts3EvalInvalidatePoslist(p->pPhrase);

5366 }

5367 }

5368

5369 break;

5370

5371 case FTSQUERY_OR: {

5372 int bHit1 = fts3EvalTestExpr(pCsr, pExpr->pLeft, pRc);

5373 int bHit2 = fts3EvalTestExpr(pCsr, pExpr->pRight, pRc);

5374 bHit = bHit1 \|\| bHit2;

5375 break;

5376 }

5377

5378 case FTSQUERY_NOT:

5379 bHit = (

5380 fts3EvalTestExpr(pCsr, pExpr->pLeft, pRc)

5381 && !fts3EvalTestExpr(pCsr, pExpr->pRight, pRc)

5382 );

5383 break;

5384

5385 default: {

5386 #ifndef SQLITE_DISABLE_FTS4_DEFERRED

5387 if( pCsr->pDeferred

5388 && (pExpr->iDocid==pCsr->iPrevId \|\| pExpr->bDeferred)

5389 ){

5390 Fts3Phrase *pPhrase = pExpr->pPhrase;

5391 assert( pExpr->bDeferred \|\| pPhrase->doclist.bFreeList==0 );

5392 if( pExpr->bDeferred ){

5393 fts3EvalInvalidatePoslist(pPhrase);

5394 }

5395 *pRc = fts3EvalDeferredPhrase(pCsr, pPhrase);

5396 bHit = (pPhrase->doclist.pList!=0);

5397 pExpr->iDocid = pCsr->iPrevId;

5398 }else

5399 #endif

5400 {

5401 bHit = (pExpr->bEof==0 && pExpr->iDocid==pCsr->iPrevId);

5402 }

5403 break;

5404 }

5405 }

5406 }

5407 return bHit;

5408 }

5409

5410 /*

5411 ** This function is called as the second part of each xNext operation when

5412 ** iterating through the results of a full-text query. At this point the

5413 ** cursor points to a row that matches the query expression, with the

5414 ** following caveats:

5415 **

5416 ** * Up until this point, "NEAR" operators in the expression have been

5417 ** treated as "AND".

5418 **

5419 ** * Deferred tokens have not yet been considered.

5420 **

5421 ** If *pRc is not SQLITE_OK when this function is called, it immediately

5422 ** returns 0. Otherwise, it tests whether or not after considering NEAR

5423 ** operators and deferred tokens the current row is still a match for the

5424 ** expression. It returns 1 if both of the following are true:

5425 **

5426 ** 1. *pRc is SQLITE_OK when this function returns, and

5427 **

5428 ** 2. After scanning the current FTS table row for the deferred tokens,

5429 ** it is determined that the row does not match the query.

5430 **

5431 ** Or, if no error occurs and it seems the current row does match the FTS

5432 ** query, return 0.

5433 */

5434 int sqlite3Fts3EvalTestDeferred(Fts3Cursor pCsr, int pRc){

5435 int rc = *pRc;

5436 int bMiss = 0;

5437 if( rc==SQLITE_OK ){

5438

5439 /* If there are one or more deferred tokens, load the current row into

5440 ** memory and scan it to determine the position list for each deferred

5441 ** token. Then, see if this row is really a match, considering deferred

5442 ** tokens and NEAR operators (neither of which were taken into account

5443 ** earlier, by fts3EvalNextRow()).

5444 */

5445 if( pCsr->pDeferred ){

5446 rc = fts3CursorSeek(0, pCsr);

5447 if( rc==SQLITE_OK ){

5448 rc = sqlite3Fts3CacheDeferredDoclists(pCsr);

5449 }

5450 }

5451 bMiss = (0==fts3EvalTestExpr(pCsr, pCsr->pExpr, &rc));

5452

5453 /* Free the position-lists accumulated for each deferred token above. */

5454 sqlite3Fts3FreeDeferredDoclists(pCsr);

5455 *pRc = rc;

5456 }

5457 return (rc==SQLITE_OK && bMiss);

5458 }

5459

5460 /*

5461 ** Advance to the next document that matches the FTS expression in

5462 ** Fts3Cursor.pExpr.

5463 */

5464 static int fts3EvalNext(Fts3Cursor *pCsr){

5465 int rc = SQLITE_OK; /* Return Code */

5466 Fts3Expr *pExpr = pCsr->pExpr;

5467 assert( pCsr->isEof==0 );

5468 if( pExpr==0 ){

5469 pCsr->isEof = 1;

5470 }else{

5471 do {

5472 if( pCsr->isRequireSeek==0 ){

5473 sqlite3_reset(pCsr->pStmt);

5474 }

5475 assert( sqlite3_data_count(pCsr->pStmt)==0 );

5476 fts3EvalNextRow(pCsr, pExpr, &rc);

5477 pCsr->isEof = pExpr->bEof;

5478 pCsr->isRequireSeek = 1;

5479 pCsr->isMatchinfoNeeded = 1;

5480 pCsr->iPrevId = pExpr->iDocid;

5481 }while( pCsr->isEof==0 && sqlite3Fts3EvalTestDeferred(pCsr, &rc) );

5482 }

5483

5484 /* Check if the cursor is past the end of the docid range specified

5485 ** by Fts3Cursor.iMinDocid/iMaxDocid. If so, set the EOF flag. */

5486 if( rc==SQLITE_OK && (

5487 (pCsr->bDesc==0 && pCsr->iPrevId>pCsr->iMaxDocid)

5488 \|\| (pCsr->bDesc!=0 && pCsr->iPrevId<pCsr->iMinDocid)

5489 )){

5490 pCsr->isEof = 1;

5491 }

5492

5493 return rc;

5494 }

5495

5496 /*

5497 ** Restart interation for expression pExpr so that the next call to

5498 ** fts3EvalNext() visits the first row. Do not allow incremental

5499 ** loading or merging of phrase doclists for this iteration.

5500 **

5501 ** If *pRc is other than SQLITE_OK when this function is called, it is

5502 ** a no-op. If an error occurs within this function, *pRc is set to an

5503 ** SQLite error code before returning.

5504 */

5505 static void fts3EvalRestart(

5506 Fts3Cursor *pCsr,

5507 Fts3Expr *pExpr,

5508 int *pRc

5509 ){

5510 if( pExpr && *pRc==SQLITE_OK ){

5511 Fts3Phrase *pPhrase = pExpr->pPhrase;

5512

5513 if( pPhrase ){

5514 fts3EvalInvalidatePoslist(pPhrase);

5515 if( pPhrase->bIncr ){

5516 int i;

5517 for(i=0; i<pPhrase->nToken; i++){

5518 Fts3PhraseToken *pToken = &pPhrase->aToken[i];

5519 assert( pToken->pDeferred==0 );

5520 if( pToken->pSegcsr ){

5521 sqlite3Fts3MsrIncrRestart(pToken->pSegcsr);

5522 }

5523 }

5524 *pRc = fts3EvalPhraseStart(pCsr, 0, pPhrase);

5525 }

5526 pPhrase->doclist.pNextDocid = 0;

5527 pPhrase->doclist.iDocid = 0;

5528 pPhrase->pOrPoslist = 0;

5529 }

5530

5531 pExpr->iDocid = 0;

5532 pExpr->bEof = 0;

5533 pExpr->bStart = 0;

5534

5535 fts3EvalRestart(pCsr, pExpr->pLeft, pRc);

5536 fts3EvalRestart(pCsr, pExpr->pRight, pRc);

5537 }

5538 }

5539

5540 /*

5541 ** After allocating the Fts3Expr.aMI[] array for each phrase in the

5542 ** expression rooted at pExpr, the cursor iterates through all rows matched

5543 ** by pExpr, calling this function for each row. This function increments

5544 ** the values in Fts3Expr.aMI[] according to the position-list currently

5545 ** found in Fts3Expr.pPhrase->doclist.pList for each of the phrase

5546 ** expression nodes.

5547 */

5548 static void fts3EvalUpdateCounts(Fts3Expr *pExpr){

5549 if( pExpr ){

5550 Fts3Phrase *pPhrase = pExpr->pPhrase;

5551 if( pPhrase && pPhrase->doclist.pList ){

5552 int iCol = 0;

5553 char *p = pPhrase->doclist.pList;

5554

5555 assert( *p );

5556 while( 1 ){

5557 u8 c = 0;

5558 int iCnt = 0;

5559 while( 0xFE & (*p \| c) ){

5560 if( (c&0x80)==0 ) iCnt++;

5561 c = *p++ & 0x80;

5562 }

5563

5564 /* aMI[iCol*3 + 1] = Number of occurrences

5565 ** aMI[iCol*3 + 2] = Number of rows containing at least one instance

5566 */

5567 pExpr->aMI[iCol*3 + 1] += iCnt;

5568 pExpr->aMI[iCol*3 + 2] += (iCnt>0);

5569 if( *p==0x00 ) break;

5570 p++;

5571 p += fts3GetVarint32(p, &iCol);

5572 }

5573 }

5574

5575 fts3EvalUpdateCounts(pExpr->pLeft);

5576 fts3EvalUpdateCounts(pExpr->pRight);

5577 }

5578 }

5579

5580 /*

5581 ** Expression pExpr must be of type FTSQUERY_PHRASE.

5582 **

5583 ** If it is not already allocated and populated, this function allocates and

5584 ** populates the Fts3Expr.aMI[] array for expression pExpr. If pExpr is part

5585 ** of a NEAR expression, then it also allocates and populates the same array

5586 ** for all other phrases that are part of the NEAR expression.

5587 **

5588 ** SQLITE_OK is returned if the aMI[] array is successfully allocated and

5589 ** populated. Otherwise, if an error occurs, an SQLite error code is returned.

5590 */

5591 static int fts3EvalGatherStats(

5592 Fts3Cursor pCsr, / Cursor object */

5593 Fts3Expr pExpr / FTSQUERY_PHRASE expression */

5594 ){

5595 int rc = SQLITE_OK; /* Return code */

5596

5597 assert( pExpr->eType==FTSQUERY_PHRASE );

5598 if( pExpr->aMI==0 ){

5599 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

5600 Fts3Expr pRoot; / Root of NEAR expression */

5601 Fts3Expr p; / Iterator used for several purposes */

5602

5603 sqlite3_int64 iPrevId = pCsr->iPrevId;

5604 sqlite3_int64 iDocid;

5605 u8 bEof;

5606

5607 /* Find the root of the NEAR expression */

5608 pRoot = pExpr;

5609 while( pRoot->pParent && pRoot->pParent->eType==FTSQUERY_NEAR ){

5610 pRoot = pRoot->pParent;

5611 }

5612 iDocid = pRoot->iDocid;

5613 bEof = pRoot->bEof;

5614 assert( pRoot->bStart );

5615

5616 /* Allocate space for the aMSI[] array of each FTSQUERY_PHRASE node */

5617 for(p=pRoot; p; p=p->pLeft){

5618 Fts3Expr *pE = (p->eType==FTSQUERY_PHRASE?p:p->pRight);

5619 assert( pE->aMI==0 );

5620 pE->aMI = (u32 )sqlite3_malloc(pTab->nColumn 3 * sizeof(u32));

5621 if( !pE->aMI ) return SQLITE_NOMEM;

5622 memset(pE->aMI, 0, pTab->nColumn * 3 * sizeof(u32));

5623 }

5624

5625 fts3EvalRestart(pCsr, pRoot, &rc);

5626

5627 while( pCsr->isEof==0 && rc==SQLITE_OK ){

5628

5629 do {

5630 /* Ensure the %_content statement is reset. */

5631 if( pCsr->isRequireSeek==0 ) sqlite3_reset(pCsr->pStmt);

5632 assert( sqlite3_data_count(pCsr->pStmt)==0 );

5633

5634 /* Advance to the next document */

5635 fts3EvalNextRow(pCsr, pRoot, &rc);

5636 pCsr->isEof = pRoot->bEof;

5637 pCsr->isRequireSeek = 1;

5638 pCsr->isMatchinfoNeeded = 1;

5639 pCsr->iPrevId = pRoot->iDocid;

5640 }while( pCsr->isEof==0

5641 && pRoot->eType==FTSQUERY_NEAR

5642 && sqlite3Fts3EvalTestDeferred(pCsr, &rc)

5643 );

5644

5645 if( rc==SQLITE_OK && pCsr->isEof==0 ){

5646 fts3EvalUpdateCounts(pRoot);

5647 }

5648 }

5649

5650 pCsr->isEof = 0;

5651 pCsr->iPrevId = iPrevId;

5652

5653 if( bEof ){

5654 pRoot->bEof = bEof;

5655 }else{

5656 /* Caution: pRoot may iterate through docids in ascending or descending

5657 ** order. For this reason, even though it seems more defensive, the

5658 ** do loop can not be written:

5659 **

5660 ** do {...} while( pRoot->iDocid<iDocid && rc==SQLITE_OK );

5661 */

5662 fts3EvalRestart(pCsr, pRoot, &rc);

5663 do {

5664 fts3EvalNextRow(pCsr, pRoot, &rc);

5665 assert( pRoot->bEof==0 );

5666 }while( pRoot->iDocid!=iDocid && rc==SQLITE_OK );

5667 }

5668 }

5669 return rc;

5670 }

5671

5672 /*

5673 ** This function is used by the matchinfo() module to query a phrase

5674 ** expression node for the following information:

5675 **

5676 ** 1. The total number of occurrences of the phrase in each column of

5677 ** the FTS table (considering all rows), and

5678 **

5679 ** 2. For each column, the number of rows in the table for which the

5680 ** column contains at least one instance of the phrase.

5681 **

5682 ** If no error occurs, SQLITE_OK is returned and the values for each column

5683 ** written into the array aiOut as follows:

5684 **

5685 ** aiOut[iCol*3 + 1] = Number of occurrences

5686 ** aiOut[iCol*3 + 2] = Number of rows containing at least one instance

5687 **

5688 ** Caveats:

5689 **

5690 ** * If a phrase consists entirely of deferred tokens, then all output

5691 ** values are set to the number of documents in the table. In other

5692 ** words we assume that very common tokens occur exactly once in each

5693 ** column of each row of the table.

5694 **

5695 ** * If a phrase contains some deferred tokens (and some non-deferred

5696 ** tokens), count the potential occurrence identified by considering

5697 ** the non-deferred tokens instead of actual phrase occurrences.

5698 **

5699 ** * If the phrase is part of a NEAR expression, then only phrase instances

5700 ** that meet the NEAR constraint are included in the counts.

5701 */

5702 int sqlite3Fts3EvalPhraseStats(

5703 Fts3Cursor pCsr, / FTS cursor handle */

5704 Fts3Expr pExpr, / Phrase expression */

5705 u32 aiOut / Array to write results into (see above) */

5706 ){

5707 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

5708 int rc = SQLITE_OK;

5709 int iCol;

5710

5711 if( pExpr->bDeferred && pExpr->pParent->eType!=FTSQUERY_NEAR ){

5712 assert( pCsr->nDoc>0 );

5713 for(iCol=0; iCol<pTab->nColumn; iCol++){

5714 aiOut[iCol*3 + 1] = (u32)pCsr->nDoc;

5715 aiOut[iCol*3 + 2] = (u32)pCsr->nDoc;

5716 }

5717 }else{

5718 rc = fts3EvalGatherStats(pCsr, pExpr);

5719 if( rc==SQLITE_OK ){

5720 assert( pExpr->aMI );

5721 for(iCol=0; iCol<pTab->nColumn; iCol++){

5722 aiOut[iCol3 + 1] = pExpr->aMI[iCol3 + 1];

5723 aiOut[iCol3 + 2] = pExpr->aMI[iCol3 + 2];

5724 }

5725 }

5726 }

5727

5728 return rc;

5729 }

5730

5731 /*

5732 ** The expression pExpr passed as the second argument to this function

5733 ** must be of type FTSQUERY_PHRASE.

5734 **

5735 ** The returned value is either NULL or a pointer to a buffer containing

5736 ** a position-list indicating the occurrences of the phrase in column iCol

5737 ** of the current row.

5738 **

5739 ** More specifically, the returned buffer contains 1 varint for each

5740 ** occurrence of the phrase in the column, stored using the normal (delta+2)

5741 ** compression and is terminated by either an 0x01 or 0x00 byte. For example,

5742 ** if the requested column contains "a b X c d X X" and the position-list

5743 ** for 'X' is requested, the buffer returned may contain:

5744 **

5745 ** 0x04 0x05 0x03 0x01 or 0x04 0x05 0x03 0x00

5746 **

5747 ** This function works regardless of whether or not the phrase is deferred,

5748 ** incremental, or neither.

5749 */

5750 int sqlite3Fts3EvalPhrasePoslist(

5751 Fts3Cursor pCsr, / FTS3 cursor object */

5752 Fts3Expr pExpr, / Phrase to return doclist for */

5753 int iCol, /* Column to return position list for */

5754 char *ppOut / OUT: Pointer to position list */

5755 ){

5756 Fts3Phrase *pPhrase = pExpr->pPhrase;

5757 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

5758 char *pIter;

5759 int iThis;

5760 sqlite3_int64 iDocid;

5761

5762 /* If this phrase is applies specifically to some column other than

5763 ** column iCol, return a NULL pointer. */

5764 *ppOut = 0;

5765 assert( iCol>=0 && iCol<pTab->nColumn );

5766 if( (pPhrase->iColumn<pTab->nColumn && pPhrase->iColumn!=iCol) ){

5767 return SQLITE_OK;

5768 }

5769

5770 iDocid = pExpr->iDocid;

5771 pIter = pPhrase->doclist.pList;

5772 if( iDocid!=pCsr->iPrevId \|\| pExpr->bEof ){

5773 int rc = SQLITE_OK;

5774 int bDescDoclist = pTab->bDescIdx; /* For DOCID_CMP macro */

5775 int bOr = 0;

5776 u8 bTreeEof = 0;

5777 Fts3Expr p; / Used to iterate from pExpr to root */

5778 Fts3Expr pNear; / Most senior NEAR ancestor (or pExpr) */

5779 int bMatch;

5780

5781 /* Check if this phrase descends from an OR expression node. If not,

5782 ** return NULL. Otherwise, the entry that corresponds to docid

5783 ** pCsr->iPrevId may lie earlier in the doclist buffer. Or, if the

5784 ** tree that the node is part of has been marked as EOF, but the node

5785 ** itself is not EOF, then it may point to an earlier entry. */

5786 pNear = pExpr;

5787 for(p=pExpr->pParent; p; p=p->pParent){

5788 if( p->eType==FTSQUERY_OR ) bOr = 1;

5789 if( p->eType==FTSQUERY_NEAR ) pNear = p;

5790 if( p->bEof ) bTreeEof = 1;

5791 }

5792 if( bOr==0 ) return SQLITE_OK;

5793

5794 /* This is the descendent of an OR node. In this case we cannot use

5795 ** an incremental phrase. Load the entire doclist for the phrase

5796 ** into memory in this case. */

5797 if( pPhrase->bIncr ){

5798 int bEofSave = pNear->bEof;

5799 fts3EvalRestart(pCsr, pNear, &rc);

5800 while( rc==SQLITE_OK && !pNear->bEof ){

5801 fts3EvalNextRow(pCsr, pNear, &rc);

5802 if( bEofSave==0 && pNear->iDocid==iDocid ) break;

5803 }

5804 assert( rc!=SQLITE_OK \|\| pPhrase->bIncr==0 );

5805 }

5806 if( bTreeEof ){

5807 while( rc==SQLITE_OK && !pNear->bEof ){

5808 fts3EvalNextRow(pCsr, pNear, &rc);

5809 }

5810 }

5811 if( rc!=SQLITE_OK ) return rc;

5812

5813 bMatch = 1;

5814 for(p=pNear; p; p=p->pLeft){

5815 u8 bEof = 0;

5816 Fts3Expr *pTest = p;

5817 Fts3Phrase *pPh;

5818 assert( pTest->eType==FTSQUERY_NEAR \|\| pTest->eType==FTSQUERY_PHRASE );

5819 if( pTest->eType==FTSQUERY_NEAR ) pTest = pTest->pRight;

5820 assert( pTest->eType==FTSQUERY_PHRASE );

5821 pPh = pTest->pPhrase;

5822

5823 pIter = pPh->pOrPoslist;

5824 iDocid = pPh->iOrDocid;

5825 if( pCsr->bDesc==bDescDoclist ){

5826 bEof = !pPh->doclist.nAll \|\|

5827 (pIter >= (pPh->doclist.aAll + pPh->doclist.nAll));

5828 while( (pIter==0 \|\| DOCID_CMP(iDocid, pCsr->iPrevId)<0 ) && bEof==0 ){

5829 sqlite3Fts3DoclistNext(

5830 bDescDoclist, pPh->doclist.aAll, pPh->doclist.nAll,

5831 &pIter, &iDocid, &bEof

5832 );

5833 }

5834 }else{

5835 bEof = !pPh->doclist.nAll \|\| (pIter && pIter<=pPh->doclist.aAll);

5836 while( (pIter==0 \|\| DOCID_CMP(iDocid, pCsr->iPrevId)>0 ) && bEof==0 ){

5837 int dummy;

5838 sqlite3Fts3DoclistPrev(

5839 bDescDoclist, pPh->doclist.aAll, pPh->doclist.nAll,

5840 &pIter, &iDocid, &dummy, &bEof

5841 );

5842 }

5843 }

5844 pPh->pOrPoslist = pIter;

5845 pPh->iOrDocid = iDocid;

5846 if( bEof \|\| iDocid!=pCsr->iPrevId ) bMatch = 0;

5847 }

5848

5849 if( bMatch ){

5850 pIter = pPhrase->pOrPoslist;

5851 }else{

5852 pIter = 0;

5853 }

5854 }

5855 if( pIter==0 ) return SQLITE_OK;

5856

5857 if( *pIter==0x01 ){

5858 pIter++;

5859 pIter += fts3GetVarint32(pIter, &iThis);

5860 }else{

5861 iThis = 0;

5862 }

5863 while( iThis<iCol ){

5864 fts3ColumnlistCopy(0, &pIter);

5865 if( *pIter==0x00 ) return SQLITE_OK;

5866 pIter++;

5867 pIter += fts3GetVarint32(pIter, &iThis);

5868 }

5869 if( *pIter==0x00 ){

5870 pIter = 0;

5871 }

5872

5873 *ppOut = ((iCol==iThis)?pIter:0);

5874 return SQLITE_OK;

5875 }

5876

5877 /*

5878 ** Free all components of the Fts3Phrase structure that were allocated by

5879 ** the eval module. Specifically, this means to free:

5880 **

5881 ** * the contents of pPhrase->doclist, and

5882 ** * any Fts3MultiSegReader objects held by phrase tokens.

5883 */

5884 void sqlite3Fts3EvalPhraseCleanup(Fts3Phrase *pPhrase){

5885 if( pPhrase ){

5886 int i;

5887 sqlite3_free(pPhrase->doclist.aAll);

5888 fts3EvalInvalidatePoslist(pPhrase);

5889 memset(&pPhrase->doclist, 0, sizeof(Fts3Doclist));

5890 for(i=0; i<pPhrase->nToken; i++){

5891 fts3SegReaderCursorFree(pPhrase->aToken[i].pSegcsr);

5892 pPhrase->aToken[i].pSegcsr = 0;

5893 }

5894 }

5895 }

5896

5897

5898 /*

5899 ** Return SQLITE_CORRUPT_VTAB.

5900 */

5901 #ifdef SQLITE_DEBUG

5902 int sqlite3Fts3Corrupt(){

5903 return SQLITE_CORRUPT_VTAB;

5904 }

5905 #endif

5906

5907 #if !SQLITE_CORE

5908 /*

5909 ** Initialize API pointer table, if required.

5910 */

5911 #ifdef _WIN32

5912 __declspec(dllexport)

5913 #endif

5914 int sqlite3_fts3_init(

5915 sqlite3 *db,

5916 char **pzErrMsg,

5917 const sqlite3_api_routines *pApi

5918 ){

5919 SQLITE_EXTENSION_INIT2(pApi)

5920 return sqlite3Fts3Init(db);

5921 }

5922 #endif

5923

5924 #endif

OLD	NEW

« no previous file with comments | « third_party/sqlite/sqlite-src-3100200/ext/fts3/fts3.h ('k') | third_party/sqlite/sqlite-src-3100200/ext/fts3/fts3Int.h » ('j') | no next file with comments »