third_party/sqlite/sqlite-src-3080704/ext/fts3/fts3.c - Issue 2363173002: [sqlite] Remove obsolete reference version 3.8.7.4.

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

Issue 2363173002: [sqlite] Remove obsolete reference version 3.8.7.4. (Closed)

Patch Set: Created 4 years, 2 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 /*

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

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

319 ** The number of bytes written is returned.

320 */

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

322 unsigned char q = (unsigned char ) p;

323 sqlite_uint64 vu = v;

324 do{

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

326 vu >>= 7;

327 }while( vu!=0 );

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

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

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

331 }

332

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

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

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

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

337 v = (*ptr++); \

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

339

340 /*

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

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

343 ** The value is stored in *v.

344 */

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

346 const char *pStart = p;

347 u32 a;

348 u64 b;

349 int shift;

350

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

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

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

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

355 b = (a & 0x0FFFFFFF );

356

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

358 u64 c = *p++;

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

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

361 }

362 *v = b;

363 return (int)(p - pStart);

364 }

365

366 /*

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

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

369 */

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

371 u32 a;

372

373 #ifndef fts3GetVarint32

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

375 #else

376 a = (*p++);

377 assert( a & 0x80 );

378 #endif

379

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

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

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

383 a = (a & 0x0FFFFFFF );

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

385 return 5;

386 }

387

388 /*

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

390 */

391 int sqlite3Fts3VarintLen(sqlite3_uint64 v){

392 int i = 0;

393 do{

394 i++;

395 v >>= 7;

396 }while( v!=0 );

397 return i;

398 }

399

400 /*

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

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

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

404 ** is a no-op.

405 **

406 ** Examples:

407 **

408 ** "abc" becomes abc

409 ** 'xyz' becomes xyz

410 ** [pqr] becomes pqr

411 ** `mno` becomes mno

412 **

413 */

414 void sqlite3Fts3Dequote(char *z){

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

416

417 quote = z[0];

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

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

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

421

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

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

424

425 while( ALWAYS(z[iIn]) ){

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

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

428 z[iOut++] = quote;

429 iIn += 2;

430 }else{

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

432 }

433 }

434 z[iOut] = '\0';

435 }

436 }

437

438 /*

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

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

441 ** to *pVal.

442 */

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

444 sqlite3_int64 iVal;

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

446 *pVal += iVal;

447 }

448

449 /*

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

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

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

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

454 **

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

456 ** varint is part of.

457 */

458 static void fts3GetReverseVarint(

459 char **pp,

460 char *pStart,

461 sqlite3_int64 *pVal

462 ){

463 sqlite3_int64 iVal;

464 char *p;

465

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

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

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

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

470 p++;

471 *pp = p;

472

473 sqlite3Fts3GetVarint(p, &iVal);

474 *pVal = iVal;

475 }

476

477 /*

478 ** The xDisconnect() virtual table method.

479 */

480 static int fts3DisconnectMethod(sqlite3_vtab *pVtab){

481 Fts3Table p = (Fts3Table )pVtab;

482 int i;

483

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

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

486

487 /* Free any prepared statements held */

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

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

490 }

491 sqlite3_free(p->zSegmentsTbl);

492 sqlite3_free(p->zReadExprlist);

493 sqlite3_free(p->zWriteExprlist);

494 sqlite3_free(p->zContentTbl);

495 sqlite3_free(p->zLanguageid);

496

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

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

499

500 sqlite3_free(p);

501 return SQLITE_OK;

502 }

503

504 /*

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

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

507 ** into *pRc.

508 **

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

510 */

511 static void fts3DbExec(

512 int pRc, / Success code */

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

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

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

516 ){

517 va_list ap;

518 char *zSql;

519 if( *pRc ) return;

520 va_start(ap, zFormat);

521 zSql = sqlite3_vmprintf(zFormat, ap);

522 va_end(ap);

523 if( zSql==0 ){

524 *pRc = SQLITE_NOMEM;

525 }else{

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

527 sqlite3_free(zSql);

528 }

529 }

530

531 /*

532 ** The xDestroy() virtual table method.

533 */

534 static int fts3DestroyMethod(sqlite3_vtab *pVtab){

535 Fts3Table p = (Fts3Table )pVtab;

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

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

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

539

540 /* Drop the shadow tables */

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

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

543 }

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

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

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

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

548

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

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

551 ** Otherwise, return an SQLite error code.

552 */

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

554 }

555

556

557 /*

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

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

560 ** and xCreate() methods.

561 **

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

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

564 ** before returning.

565 */

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

567 if( *pRc==SQLITE_OK ){

568 int i; /* Iterator variable */

569 int rc; /* Return code */

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

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

572 const char *zLanguageid;

573

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

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

576

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

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

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

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

581 }

582

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

584 zSql = sqlite3_mprintf(

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

586 zCols, p->zName, zLanguageid

587 );

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

589 rc = SQLITE_NOMEM;

590 }else{

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

592 }

593

594 sqlite3_free(zSql);

595 sqlite3_free(zCols);

596 *pRc = rc;

597 }

598 }

599

600 /*

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

602 */

603 void sqlite3Fts3CreateStatTable(int pRc, Fts3Table p){

604 fts3DbExec(pRc, p->db,

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

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

607 p->zDb, p->zName

608 );

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

610 }

611

612 /*

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

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

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

616 **

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

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

619 ** %_stat tables required by FTS4.

620 */

621 static int fts3CreateTables(Fts3Table *p){

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

623 int i; /* Iterator variable */

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

625

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

627 const char *zLanguageid = p->zLanguageid;

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

629

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

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

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

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

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

635 }

636 if( zLanguageid && zContentCols ){

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

638 }

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

640

641 /* Create the content table */

642 fts3DbExec(&rc, db,

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

644 p->zDb, p->zName, zContentCols

645 );

646 sqlite3_free(zContentCols);

647 }

648

649 /* Create other tables */

650 fts3DbExec(&rc, db,

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

652 p->zDb, p->zName

653 );

654 fts3DbExec(&rc, db,

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

656 "level INTEGER,"

657 "idx INTEGER,"

658 "start_block INTEGER,"

659 "leaves_end_block INTEGER,"

660 "end_block INTEGER,"

661 "root BLOB,"

662 "PRIMARY KEY(level, idx)"

663 ");",

664 p->zDb, p->zName

665 );

666 if( p->bHasDocsize ){

667 fts3DbExec(&rc, db,

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

669 p->zDb, p->zName

670 );

671 }

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

673 if( p->bHasStat ){

674 sqlite3Fts3CreateStatTable(&rc, p);

675 }

676 return rc;

677 }

678

679 /*

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

681 **

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

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

684 ** before returning.

685 */

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

687 if( *pRc==SQLITE_OK ){

688 int rc; /* Return code */

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

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

691

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

693 if( !zSql ){

694 rc = SQLITE_NOMEM;

695 }else{

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

697 if( rc==SQLITE_OK ){

698 sqlite3_step(pStmt);

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

700 rc = sqlite3_finalize(pStmt);

701 }else if( rc==SQLITE_AUTH ){

702 p->nPgsz = 1024;

703 rc = SQLITE_OK;

704 }

705 }

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

707 sqlite3_free(zSql);

708 *pRc = rc;

709 }

710 }

711

712 /*

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

714 **

715 ** <key> = <value>

716 **

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

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

719 */

720 static int fts3IsSpecialColumn(

721 const char *z,

722 int *pnKey,

723 char **pzValue

724 ){

725 char *zValue;

726 const char *zCsr = z;

727

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

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

730 zCsr++;

731 }

732

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

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

735 if( zValue ){

736 sqlite3Fts3Dequote(zValue);

737 }

738 *pzValue = zValue;

739 return 1;

740 }

741

742 /*

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

744 */

745 static void fts3Appendf(

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

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

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

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

750 ){

751 if( *pRc==SQLITE_OK ){

752 va_list ap;

753 char *z;

754 va_start(ap, zFormat);

755 z = sqlite3_vmprintf(zFormat, ap);

756 va_end(ap);

757 if( z && *pz ){

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

759 sqlite3_free(z);

760 z = z2;

761 }

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

763 sqlite3_free(*pz);

764 *pz = z;

765 }

766 }

767

768 /*

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

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

771 **

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

773 **

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

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

776 ** memory.

777 */

778 static char fts3QuoteId(char const zInput){

779 int nRet;

780 char *zRet;

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

782 zRet = sqlite3_malloc(nRet);

783 if( zRet ){

784 int i;

785 char *z = zRet;

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

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

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

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

790 }

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

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

793 }

794 return zRet;

795 }

796

797 /*

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

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

800 **

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

802 **

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

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

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

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

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

808 ** string is returned:

809 **

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

811 **

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

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

814 **

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

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

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

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

819 */

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

821 char *zRet = 0;

822 char *zFree = 0;

823 char *zFunction;

824 int i;

825

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

827 if( !zFunc ){

828 zFunction = "";

829 }else{

830 zFree = zFunction = fts3QuoteId(zFunc);

831 }

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

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

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

835 }

836 if( p->zLanguageid ){

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

838 }

839 sqlite3_free(zFree);

840 }else{

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

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

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

844 }

845 if( p->zLanguageid ){

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

847 }

848 }

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

850 p->zDb,

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

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

853 );

854 return zRet;

855 }

856

857 /*

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

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

860 ** user-defined text column).

861 **

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

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

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

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

866 **

867 ** "?, zip(?), zip(?), zip(?)"

868 **

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

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

871 **

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

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

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

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

876 */

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

878 char *zRet = 0;

879 char *zFree = 0;

880 char *zFunction;

881 int i;

882

883 if( !zFunc ){

884 zFunction = "";

885 }else{

886 zFree = zFunction = fts3QuoteId(zFunc);

887 }

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

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

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

891 }

892 if( p->zLanguageid ){

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

894 }

895 sqlite3_free(zFree);

896 return zRet;

897 }

898

899 /*

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

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

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

903 ** the integer value.

904 **

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

906 **

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

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

909 **

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

911 */

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

913 const char p; / Iterator pointer */

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

915

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

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

918 }

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

920 *pnOut = nInt;

921 *pp = p;

922 return SQLITE_OK;

923 }

924

925 /*

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

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

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

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

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

931 **

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

933 ** specified, or NULL otherwise.

934 **

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

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

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

938 **

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

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

941 */

942 static int fts3PrefixParameter(

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

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

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

946 ){

947 struct Fts3Index aIndex; / Allocated array */

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

949

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

951 const char *p;

952 nIndex++;

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

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

955 }

956 }

957

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

959 *apIndex = aIndex;

960 *pnIndex = nIndex;

961 if( !aIndex ){

962 return SQLITE_NOMEM;

963 }

964

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

966 if( zParam ){

967 const char *p = zParam;

968 int i;

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

970 int nPrefix;

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

972 aIndex[i].nPrefix = nPrefix;

973 p++;

974 }

975 }

976

977 return SQLITE_OK;

978 }

979

980 /*

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

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

983 ** of the new FTS4 table.

984 **

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

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

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

988 ** as follows:

989 **

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

991 **

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

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

994 **

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

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

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

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

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

1000 **

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

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

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

1004 */

1005 static int fts3ContentColumns(

1006 sqlite3 db, / Database handle */

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

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

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

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

1011 int pnStr / OUT: Bytes of string content */

1012 ){

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

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

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

1016

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

1018 if( !zSql ){

1019 rc = SQLITE_NOMEM;

1020 }else{

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

1022 }

1023 sqlite3_free(zSql);

1024

1025 if( rc==SQLITE_OK ){

1026 const char *azCol; / Output array */

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

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

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

1030

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

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

1033 ** nul-terminator byte. */

1034 nCol = sqlite3_column_count(pStmt);

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

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

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

1038 }

1039

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

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

1042 if( azCol==0 ){

1043 rc = SQLITE_NOMEM;

1044 }else{

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

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

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

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

1049 memcpy(p, zCol, n);

1050 azCol[i] = p;

1051 p += n;

1052 }

1053 }

1054 sqlite3_finalize(pStmt);

1055

1056 /* Set the output variables. */

1057 *pnCol = nCol;

1058 *pnStr = nStr;

1059 *pazCol = azCol;

1060 }

1061

1062 return rc;

1063 }

1064

1065 /*

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

1067 ** methods of the FTS3 virtual table.

1068 **

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

1070 **

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

1072 ** argv[1] -> database name

1073 ** argv[2] -> table name

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

1075 */

1076 static int fts3InitVtab(

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

1078 sqlite3 db, / The SQLite database connection */

1079 void pAux, / Hash table containing tokenizers */

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

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

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

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

1084 ){

1085 Fts3Hash pHash = (Fts3Hash )pAux;

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

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

1088 int i; /* Iterator variable */

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

1090 int iCol; /* Column index */

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

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

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

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

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

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

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

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

1099

1100 int nIndex; /* Size of aIndex[] array */

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

1102

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

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

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

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

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

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

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

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

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

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

1113

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

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

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

1117 );

1118

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

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

1121

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

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

1124 if( aCol ){

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

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

1127 }

1128 if( azNotindexed ){

1129 memset(azNotindexed, 0, nByte);

1130 }

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

1132 rc = SQLITE_NOMEM;

1133 goto fts3_init_out;

1134 }

1135

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

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

1138 ** does the following:

1139 **

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

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

1142 ** of the column names.

1143 **

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

1145 ** initializes the tokenizer pTokenizer.

1146 */

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

1148 char const *z = argv[i];

1149 int nKey;

1150 char *zVal;

1151

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

1153 if( !pTokenizer

1154 && strlen(z)>8

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

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

1157 ){

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

1159 }

1160

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

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

1163 struct Fts4Option {

1164 const char *zOpt;

1165 int nOpt;

1166 } aFts4Opt[] = {

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

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

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

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

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

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

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

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

1175 };

1176

1177 int iOpt;

1178 if( !zVal ){

1179 rc = SQLITE_NOMEM;

1180 }else{

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

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

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

1184 break;

1185 }

1186 }

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

1188 *pzErr = sqlite3_mprintf("unrecognized parameter: %s", z);

1189 rc = SQLITE_ERROR;

1190 }else{

1191 switch( iOpt ){

1192 case 0: /* MATCHINFO */

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

1194 *pzErr = sqlite3_mprintf("unrecognized matchinfo: %s", zVal);

1195 rc = SQLITE_ERROR;

1196 }

1197 bNoDocsize = 1;

1198 break;

1199

1200 case 1: /* PREFIX */

1201 sqlite3_free(zPrefix);

1202 zPrefix = zVal;

1203 zVal = 0;

1204 break;

1205

1206 case 2: /* COMPRESS */

1207 sqlite3_free(zCompress);

1208 zCompress = zVal;

1209 zVal = 0;

1210 break;

1211

1212 case 3: /* UNCOMPRESS */

1213 sqlite3_free(zUncompress);

1214 zUncompress = zVal;

1215 zVal = 0;

1216 break;

1217

1218 case 4: /* ORDER */

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

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

1221 ){

1222 *pzErr = sqlite3_mprintf("unrecognized order: %s", zVal);

1223 rc = SQLITE_ERROR;

1224 }

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

1226 break;

1227

1228 case 5: /* CONTENT */

1229 sqlite3_free(zContent);

1230 zContent = zVal;

1231 zVal = 0;

1232 break;

1233

1234 case 6: /* LANGUAGEID */

1235 assert( iOpt==6 );

1236 sqlite3_free(zLanguageid);

1237 zLanguageid = zVal;

1238 zVal = 0;

1239 break;

1240

1241 case 7: /* NOTINDEXED */

1242 azNotindexed[nNotindexed++] = zVal;

1243 zVal = 0;

1244 break;

1245 }

1246 }

1247 sqlite3_free(zVal);

1248 }

1249 }

1250

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

1252 else {

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

1254 aCol[nCol++] = z;

1255 }

1256 }

1257

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

1259 **

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

1261 **

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

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

1264 */

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

1266 sqlite3_free(zCompress);

1267 sqlite3_free(zUncompress);

1268 zCompress = 0;

1269 zUncompress = 0;

1270 if( nCol==0 ){

1271 sqlite3_free((void*)aCol);

1272 aCol = 0;

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

1274

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

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

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

1278 int j;

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

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

1281 int k;

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

1283 nCol--;

1284 break;

1285 }

1286 }

1287 }

1288 }

1289 }

1290 if( rc!=SQLITE_OK ) goto fts3_init_out;

1291

1292 if( nCol==0 ){

1293 assert( nString==0 );

1294 aCol[0] = "content";

1295 nString = 8;

1296 nCol = 1;

1297 }

1298

1299 if( pTokenizer==0 ){

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

1301 if( rc!=SQLITE_OK ) goto fts3_init_out;

1302 }

1303 assert( pTokenizer );

1304

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

1306 if( rc==SQLITE_ERROR ){

1307 assert( zPrefix );

1308 *pzErr = sqlite3_mprintf("error parsing prefix parameter: %s", zPrefix);

1309 }

1310 if( rc!=SQLITE_OK ) goto fts3_init_out;

1311

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

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

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

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

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

1317 nName + /* zName */

1318 nDb + /* zDb */

1319 nString; /* Space for azColumn strings */

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

1321 if( p==0 ){

1322 rc = SQLITE_NOMEM;

1323 goto fts3_init_out;

1324 }

1325 memset(p, 0, nByte);

1326 p->db = db;

1327 p->nColumn = nCol;

1328 p->nPendingData = 0;

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

1330 p->pTokenizer = pTokenizer;

1331 p->nMaxPendingData = FTS3_MAX_PENDING_DATA;

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

1333 p->bHasStat = isFts4;

1334 p->bFts4 = isFts4;

1335 p->bDescIdx = bDescIdx;

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

1337 p->zContentTbl = zContent;

1338 p->zLanguageid = zLanguageid;

1339 zContent = 0;

1340 zLanguageid = 0;

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

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

1343

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

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

1346 p->nIndex = nIndex;

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

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

1349 }

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

1351

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

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

1354 p->zName = zCsr;

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

1356 zCsr += nName;

1357 p->zDb = zCsr;

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

1359 zCsr += nDb;

1360

1361 /* Fill in the azColumn array */

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

1363 char *z;

1364 int n = 0;

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

1366 memcpy(zCsr, z, n);

1367 zCsr[n] = '\0';

1368 sqlite3Fts3Dequote(zCsr);

1369 p->azColumn[iCol] = zCsr;

1370 zCsr += n+1;

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

1372 }

1373

1374 /* Fill in the abNotindexed array */

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

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

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

1378 char *zNot = azNotindexed[i];

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

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

1381 ){

1382 p->abNotindexed[iCol] = 1;

1383 sqlite3_free(zNot);

1384 azNotindexed[i] = 0;

1385 }

1386 }

1387 }

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

1389 if( azNotindexed[i] ){

1390 *pzErr = sqlite3_mprintf("no such column: %s", azNotindexed[i]);

1391 rc = SQLITE_ERROR;

1392 }

1393 }

1394

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

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

1397 rc = SQLITE_ERROR;

1398 *pzErr = sqlite3_mprintf("missing %s parameter in fts4 constructor", zMiss);

1399 }

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

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

1402 if( rc!=SQLITE_OK ) goto fts3_init_out;

1403

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

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

1406 */

1407 if( isCreate ){

1408 rc = fts3CreateTables(p);

1409 }

1410

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

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

1413 */

1414 if( !isFts4 && !isCreate ){

1415 p->bHasStat = 2;

1416 }

1417

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

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

1420 fts3DatabasePageSize(&rc, p);

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

1422

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

1424 fts3DeclareVtab(&rc, p);

1425

1426 fts3_init_out:

1427 sqlite3_free(zPrefix);

1428 sqlite3_free(aIndex);

1429 sqlite3_free(zCompress);

1430 sqlite3_free(zUncompress);

1431 sqlite3_free(zContent);

1432 sqlite3_free(zLanguageid);

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

1434 sqlite3_free((void *)aCol);

1435 sqlite3_free((void *)azNotindexed);

1436 if( rc!=SQLITE_OK ){

1437 if( p ){

1438 fts3DisconnectMethod((sqlite3_vtab *)p);

1439 }else if( pTokenizer ){

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

1441 }

1442 }else{

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

1444 *ppVTab = &p->base;

1445 }

1446 return rc;

1447 }

1448

1449 /*

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

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

1452 */

1453 static int fts3ConnectMethod(

1454 sqlite3 db, / Database connection */

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

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

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

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

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

1460 ){

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

1462 }

1463 static int fts3CreateMethod(

1464 sqlite3 db, / Database connection */

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

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

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

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

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

1470 ){

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

1472 }

1473

1474 /*

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

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

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

1478 */

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

1480 #if SQLITE_VERSION_NUMBER>=3008002

1481 if( sqlite3_libversion_number()>=3008002 ){

1482 pIdxInfo->estimatedRows = nRow;

1483 }

1484 #endif

1485 }

1486

1487 /*

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

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

1490 **

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

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

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

1494 */

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

1496 Fts3Table p = (Fts3Table )pVTab;

1497 int i; /* Iterator variable */

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

1499

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

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

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

1503 int iIdx;

1504

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

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

1507 ** strategy is possible.

1508 */

1509 pInfo->idxNum = FTS3_FULLSCAN_SEARCH;

1510 pInfo->estimatedCost = 5000000;

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

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

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

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

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

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

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

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

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

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

1521 pInfo->idxNum = FTS3_FULLSCAN_SEARCH;

1522 pInfo->estimatedCost = 1e50;

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

1524 return SQLITE_OK;

1525 }

1526 continue;

1527 }

1528

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

1530

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

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

1533 pInfo->idxNum = FTS3_DOCID_SEARCH;

1534 pInfo->estimatedCost = 1.0;

1535 iCons = i;

1536 }

1537

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

1539 **

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

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

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

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

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

1545 ** context" error.

1546 */

1547 if( pCons->op==SQLITE_INDEX_CONSTRAINT_MATCH

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

1549 ){

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

1551 pInfo->estimatedCost = 2.0;

1552 iCons = i;

1553 }

1554

1555 /* Equality constraint on the langid column */

1556 if( pCons->op==SQLITE_INDEX_CONSTRAINT_EQ

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

1558 ){

1559 iLangidCons = i;

1560 }

1561

1562 if( bDocid ){

1563 switch( pCons->op ){

1564 case SQLITE_INDEX_CONSTRAINT_GE:

1565 case SQLITE_INDEX_CONSTRAINT_GT:

1566 iDocidGe = i;

1567 break;

1568

1569 case SQLITE_INDEX_CONSTRAINT_LE:

1570 case SQLITE_INDEX_CONSTRAINT_LT:

1571 iDocidLe = i;

1572 break;

1573 }

1574 }

1575 }

1576

1577 iIdx = 1;

1578 if( iCons>=0 ){

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

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

1581 }

1582 if( iLangidCons>=0 ){

1583 pInfo->idxNum \|= FTS3_HAVE_LANGID;

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

1585 }

1586 if( iDocidGe>=0 ){

1587 pInfo->idxNum \|= FTS3_HAVE_DOCID_GE;

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

1589 }

1590 if( iDocidLe>=0 ){

1591 pInfo->idxNum \|= FTS3_HAVE_DOCID_LE;

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

1593 }

1594

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

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

1597 */

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

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

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

1601 if( pOrder->desc ){

1602 pInfo->idxStr = "DESC";

1603 }else{

1604 pInfo->idxStr = "ASC";

1605 }

1606 pInfo->orderByConsumed = 1;

1607 }

1608 }

1609

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

1611 return SQLITE_OK;

1612 }

1613

1614 /*

1615 ** Implementation of xOpen method.

1616 */

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

1618 sqlite3_vtab_cursor pCsr; / Allocated cursor */

1619

1620 UNUSED_PARAMETER(pVTab);

1621

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

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

1624 ** if the allocation fails, return SQLITE_NOMEM.

1625 */

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

1627 if( !pCsr ){

1628 return SQLITE_NOMEM;

1629 }

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

1631 return SQLITE_OK;

1632 }

1633

1634 /*

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

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

1637 */

1638 static int fts3CloseMethod(sqlite3_vtab_cursor *pCursor){

1639 Fts3Cursor pCsr = (Fts3Cursor )pCursor;

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

1641 sqlite3_finalize(pCsr->pStmt);

1642 sqlite3Fts3ExprFree(pCsr->pExpr);

1643 sqlite3Fts3FreeDeferredTokens(pCsr);

1644 sqlite3_free(pCsr->aDoclist);

1645 sqlite3_free(pCsr->aMatchinfo);

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

1647 sqlite3_free(pCsr);

1648 return SQLITE_OK;

1649 }

1650

1651 /*

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

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

1654 **

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

1656 **

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

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

1659 **

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

1661 */

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

1663 int rc = SQLITE_OK;

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

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

1666 char *zSql;

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

1668 if( !zSql ) return SQLITE_NOMEM;

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

1670 sqlite3_free(zSql);

1671 }

1672 *ppStmt = pCsr->pStmt;

1673 return rc;

1674 }

1675

1676 /*

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

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

1679 ** SQLITE_OK on success.

1680 */

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

1682 int rc = SQLITE_OK;

1683 if( pCsr->isRequireSeek ){

1684 sqlite3_stmt *pStmt = 0;

1685

1686 rc = fts3CursorSeekStmt(pCsr, &pStmt);

1687 if( rc==SQLITE_OK ){

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

1689 pCsr->isRequireSeek = 0;

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

1691 return SQLITE_OK;

1692 }else{

1693 rc = sqlite3_reset(pCsr->pStmt);

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

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

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

1697 ** The data structures are corrupt. */

1698 rc = FTS_CORRUPT_VTAB;

1699 pCsr->isEof = 1;

1700 }

1701 }

1702 }

1703 }

1704

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

1706 sqlite3_result_error_code(pContext, rc);

1707 }

1708 return rc;

1709 }

1710

1711 /*

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

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

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

1715 ** passed in zTerm/nTerm.

1716 **

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

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

1719 **

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

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

1722 ** a prefix.

1723 **

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

1725 */

1726 static int fts3ScanInteriorNode(

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

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

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

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

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

1732 sqlite3_int64 piLast / OUT: Selected child node */

1733 ){

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

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

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

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

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

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

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

1741

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

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

1744 ** node into variable iChild.

1745 **

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

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

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

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

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

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

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

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

1754 */

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

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

1757 if( zCsr>zEnd ){

1758 return FTS_CORRUPT_VTAB;

1759 }

1760

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

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

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

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

1765 int nBuffer; /* Total term size */

1766

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

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

1769 if( !isFirstTerm ){

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

1771 }

1772 isFirstTerm = 0;

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

1774

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

1776 rc = FTS_CORRUPT_VTAB;

1777 goto finish_scan;

1778 }

1779 if( nPrefix+nSuffix>nAlloc ){

1780 char *zNew;

1781 nAlloc = (nPrefix+nSuffix) * 2;

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

1783 if( !zNew ){

1784 rc = SQLITE_NOMEM;

1785 goto finish_scan;

1786 }

1787 zBuffer = zNew;

1788 }

1789 assert( zBuffer );

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

1791 nBuffer = nPrefix + nSuffix;

1792 zCsr += nSuffix;

1793

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

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

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

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

1798 ** iChild.

1799 **

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

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

1802 */

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

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

1805 *piFirst = iChild;

1806 piFirst = 0;

1807 }

1808

1809 if( piLast && cmp<0 ){

1810 *piLast = iChild;

1811 piLast = 0;

1812 }

1813

1814 iChild++;

1815 };

1816

1817 if( piFirst ) *piFirst = iChild;

1818 if( piLast ) *piLast = iChild;

1819

1820 finish_scan:

1821 sqlite3_free(zBuffer);

1822 return rc;

1823 }

1824

1825

1826 /*

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

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

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

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

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

1832 **

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

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

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

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

1837 ** term is a prefix.

1838 **

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

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

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

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

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

1844 **

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

1846 */

1847 static int fts3SelectLeaf(

1848 Fts3Table p, / Virtual table handle */

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

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

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

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

1853 sqlite3_int64 piLeaf, / Selected leaf node */

1854 sqlite3_int64 piLeaf2 / Selected leaf node */

1855 ){

1856 int rc; /* Return code */

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

1858

1859 assert( piLeaf \|\| piLeaf2 );

1860

1861 fts3GetVarint32(zNode, &iHeight);

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

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

1864

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

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

1867 int nBlob; /* Size of zBlob in bytes */

1868

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

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

1871 if( rc==SQLITE_OK ){

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

1873 }

1874 sqlite3_free(zBlob);

1875 piLeaf = 0;

1876 zBlob = 0;

1877 }

1878

1879 if( rc==SQLITE_OK ){

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

1881 }

1882 if( rc==SQLITE_OK ){

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

1884 }

1885 sqlite3_free(zBlob);

1886 }

1887

1888 return rc;

1889 }

1890

1891 /*

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

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

1894 */

1895 static void fts3PutDeltaVarint(

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

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

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

1899 ){

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

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

1902 *piPrev = iVal;

1903 }

1904

1905 /*

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

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

1908 ** first byte after the position-list.

1909 **

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

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

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

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

1914 **

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

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

1917 ** before this function returns.

1918 */

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

1920 char pEnd = ppPoslist;

1921 char c = 0;

1922

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

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

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

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

1927 **

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

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

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

1931 ** last byte in the position-list.

1932 */

1933 while( *pEnd \| c ){

1934 c = *pEnd++ & 0x80;

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

1936 }

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

1938

1939 if( pp ){

1940 int n = (int)(pEnd - *ppPoslist);

1941 char p = pp;

1942 memcpy(p, *ppPoslist, n);

1943 p += n;

1944 *pp = p;

1945 }

1946 *ppPoslist = pEnd;

1947 }

1948

1949 /*

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

1951 ** start of a column-list. After it returns, *ppPoslist points to the

1952 ** to the terminator (POS_COLUMN or POS_END) byte of the column-list.

1953 **

1954 ** A column-list is list of delta-encoded positions for a single column

1955 ** within a single document within a doclist.

1956 **

1957 ** The column-list is terminated either by a POS_COLUMN varint (1) or

1958 ** a POS_END varint (0). This routine leaves *ppPoslist pointing to

1959 ** the POS_COLUMN or POS_END that terminates the column-list.

1960 **

1961 ** If pp is not NULL, then the contents of the column-list are copied

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

1963 ** before this function returns. The POS_COLUMN or POS_END terminator

1964 ** is not copied into *pp.

1965 */

1966 static void fts3ColumnlistCopy(char pp, char ppPoslist){

1967 char pEnd = ppPoslist;

1968 char c = 0;

1969

1970 /* A column-list is terminated by either a 0x01 or 0x00 byte that is

1971 ** not part of a multi-byte varint.

1972 */

1973 while( 0xFE & (*pEnd \| c) ){

1974 c = *pEnd++ & 0x80;

1975 testcase( c!=0 && ((*pEnd)&0xfe)==0 );

1976 }

1977 if( pp ){

1978 int n = (int)(pEnd - *ppPoslist);

1979 char p = pp;

1980 memcpy(p, *ppPoslist, n);

1981 p += n;

1982 *pp = p;

1983 }

1984 *ppPoslist = pEnd;

1985 }

1986

1987 /*

1988 ** Value used to signify the end of an position-list. This is safe because

1989 ** it is not possible to have a document with 2^31 terms.

1990 */

1991 #define POSITION_LIST_END 0x7fffffff

1992

1993 /*

1994 ** This function is used to help parse position-lists. When this function is

1995 ** called, *pp may point to the start of the next varint in the position-list

1996 ** being parsed, or it may point to 1 byte past the end of the position-list

1997 (in which case pp will be a terminator bytes POS_END (0) or

1998 ** (1)).

1999 **

2000 ** If pp points past the end of the current position-list, set pi to

2001 ** POSITION_LIST_END and return. Otherwise, read the next varint from *pp,

2002 ** increment the current value of pi by the value read, and set pp to

2003 ** point to the next value before returning.

2004 **

2005 ** Before calling this routine *pi must be initialized to the value of

2006 ** the previous position, or zero if we are reading the first position

2007 ** in the position-list. Because positions are delta-encoded, the value

2008 ** of the previous position is needed in order to compute the value of

2009 ** the next position.

2010 */

2011 static void fts3ReadNextPos(

2012 char *pp, / IN/OUT: Pointer into position-list buffer */

2013 sqlite3_int64 pi / IN/OUT: Value read from position-list */

2014 ){

2015 if( (**pp)&0xFE ){

2016 fts3GetDeltaVarint(pp, pi);

2017 *pi -= 2;

2018 }else{

2019 *pi = POSITION_LIST_END;

2020 }

2021 }

2022

2023 /*

2024 ** If parameter iCol is not 0, write an POS_COLUMN (1) byte followed by

2025 ** the value of iCol encoded as a varint to *pp. This will start a new

2026 ** column list.

2027 **

2028 ** Set *pp to point to the byte just after the last byte written before

2029 ** returning (do not modify it if iCol==0). Return the total number of bytes

2030 ** written (0 if iCol==0).

2031 */

2032 static int fts3PutColNumber(char **pp, int iCol){

2033 int n = 0; /* Number of bytes written */

2034 if( iCol ){

2035 char p = pp; /* Output pointer */

2036 n = 1 + sqlite3Fts3PutVarint(&p[1], iCol);

2037 *p = 0x01;

2038 *pp = &p[n];

2039 }

2040 return n;

2041 }

2042

2043 /*

2044 ** Compute the union of two position lists. The output written

2045 ** into pp contains all positions of both pp1 and *pp2 in sorted

2046 ** order and with any duplicates removed. All pointers are

2047 ** updated appropriately. The caller is responsible for insuring

2048 ** that there is enough space in *pp to hold the complete output.

2049 */

2050 static void fts3PoslistMerge(

2051 char *pp, / Output buffer */

2052 char *pp1, / Left input list */

2053 char *pp2 / Right input list */

2054 ){

2055 char p = pp;

2056 char p1 = pp1;

2057 char p2 = pp2;

2058

2059 while( p1 \|\| p2 ){

2060 int iCol1; /* The current column index in pp1 */

2061 int iCol2; /* The current column index in pp2 */

2062

2063 if( *p1==POS_COLUMN ) fts3GetVarint32(&p1[1], &iCol1);

2064 else if( *p1==POS_END ) iCol1 = POSITION_LIST_END;

2065 else iCol1 = 0;

2066

2067 if( *p2==POS_COLUMN ) fts3GetVarint32(&p2[1], &iCol2);

2068 else if( *p2==POS_END ) iCol2 = POSITION_LIST_END;

2069 else iCol2 = 0;

2070

2071 if( iCol1==iCol2 ){

2072 sqlite3_int64 i1 = 0; /* Last position from pp1 */

2073 sqlite3_int64 i2 = 0; /* Last position from pp2 */

2074 sqlite3_int64 iPrev = 0;

2075 int n = fts3PutColNumber(&p, iCol1);

2076 p1 += n;

2077 p2 += n;

2078

2079 /* At this point, both p1 and p2 point to the start of column-lists

2080 ** for the same column (the column with index iCol1 and iCol2).

2081 ** A column-list is a list of non-negative delta-encoded varints, each

2082 ** incremented by 2 before being stored. Each list is terminated by a

2083 ** POS_END (0) or POS_COLUMN (1). The following block merges the two lists

2084 ** and writes the results to buffer p. p is left pointing to the byte

2085 ** after the list written. No terminator (POS_END or POS_COLUMN) is

2086 ** written to the output.

2087 */

2088 fts3GetDeltaVarint(&p1, &i1);

2089 fts3GetDeltaVarint(&p2, &i2);

2090 do {

2091 fts3PutDeltaVarint(&p, &iPrev, (i1<i2) ? i1 : i2);

2092 iPrev -= 2;

2093 if( i1==i2 ){

2094 fts3ReadNextPos(&p1, &i1);

2095 fts3ReadNextPos(&p2, &i2);

2096 }else if( i1<i2 ){

2097 fts3ReadNextPos(&p1, &i1);

2098 }else{

2099 fts3ReadNextPos(&p2, &i2);

2100 }

2101 }while( i1!=POSITION_LIST_END \|\| i2!=POSITION_LIST_END );

2102 }else if( iCol1<iCol2 ){

2103 p1 += fts3PutColNumber(&p, iCol1);

2104 fts3ColumnlistCopy(&p, &p1);

2105 }else{

2106 p2 += fts3PutColNumber(&p, iCol2);

2107 fts3ColumnlistCopy(&p, &p2);

2108 }

2109 }

2110

2111 *p++ = POS_END;

2112 *pp = p;

2113 *pp1 = p1 + 1;

2114 *pp2 = p2 + 1;

2115 }

2116

2117 /*

2118 ** This function is used to merge two position lists into one. When it is

2119 ** called, pp1 and pp2 must both point to position lists. A position-list is

2120 ** the part of a doclist that follows each document id. For example, if a row

2121 ** contains:

2122 **

2123 ** 'a b c'\|'x y z'\|'a b b a'

2124 **

2125 ** Then the position list for this row for token 'b' would consist of:

2126 **

2127 ** 0x02 0x01 0x02 0x03 0x03 0x00

2128 **

2129 ** When this function returns, both pp1 and pp2 are left pointing to the

2130 ** byte following the 0x00 terminator of their respective position lists.

2131 **

2132 ** If isSaveLeft is 0, an entry is added to the output position list for

2133 ** each position in *pp2 for which there exists one or more positions in

2134 ** pp1 so that (pos(pp2)>pos(pp1) && pos(pp2)-pos(*pp1)<=nToken). i.e.

2135 ** when the pp1 token appears before the pp2 token, but not more than nToken

2136 ** slots before it.

2137 **

2138 ** e.g. nToken==1 searches for adjacent positions.

2139 */

2140 static int fts3PoslistPhraseMerge(

2141 char *pp, / IN/OUT: Preallocated output buffer */

2142 int nToken, /* Maximum difference in token positions */

2143 int isSaveLeft, /* Save the left position */

2144 int isExact, /* If pp1 is exactly nTokens before pp2 */

2145 char *pp1, / IN/OUT: Left input list */

2146 char *pp2 / IN/OUT: Right input list */

2147 ){

2148 char p = pp;

2149 char p1 = pp1;

2150 char p2 = pp2;

2151 int iCol1 = 0;

2152 int iCol2 = 0;

2153

2154 /* Never set both isSaveLeft and isExact for the same invocation. */

2155 assert( isSaveLeft==0 \|\| isExact==0 );

2156

2157 assert( p!=0 && p1!=0 && p2!=0 );

2158 if( *p1==POS_COLUMN ){

2159 p1++;

2160 p1 += fts3GetVarint32(p1, &iCol1);

2161 }

2162 if( *p2==POS_COLUMN ){

2163 p2++;

2164 p2 += fts3GetVarint32(p2, &iCol2);

2165 }

2166

2167 while( 1 ){

2168 if( iCol1==iCol2 ){

2169 char *pSave = p;

2170 sqlite3_int64 iPrev = 0;

2171 sqlite3_int64 iPos1 = 0;

2172 sqlite3_int64 iPos2 = 0;

2173

2174 if( iCol1 ){

2175 *p++ = POS_COLUMN;

2176 p += sqlite3Fts3PutVarint(p, iCol1);

2177 }

2178

2179 assert( p1!=POS_END && p1!=POS_COLUMN );

2180 assert( p2!=POS_END && p2!=POS_COLUMN );

2181 fts3GetDeltaVarint(&p1, &iPos1); iPos1 -= 2;

2182 fts3GetDeltaVarint(&p2, &iPos2); iPos2 -= 2;

2183

2184 while( 1 ){

2185 if( iPos2==iPos1+nToken

2186 \|\| (isExact==0 && iPos2>iPos1 && iPos2<=iPos1+nToken)

2187 ){

2188 sqlite3_int64 iSave;

2189 iSave = isSaveLeft ? iPos1 : iPos2;

2190 fts3PutDeltaVarint(&p, &iPrev, iSave+2); iPrev -= 2;

2191 pSave = 0;

2192 assert( p );

2193 }

2194 if( (!isSaveLeft && iPos2<=(iPos1+nToken)) \|\| iPos2<=iPos1 ){

2195 if( (*p2&0xFE)==0 ) break;

2196 fts3GetDeltaVarint(&p2, &iPos2); iPos2 -= 2;

2197 }else{

2198 if( (*p1&0xFE)==0 ) break;

2199 fts3GetDeltaVarint(&p1, &iPos1); iPos1 -= 2;

2200 }

2201 }

2202

2203 if( pSave ){

2204 assert( pp && p );

2205 p = pSave;

2206 }

2207

2208 fts3ColumnlistCopy(0, &p1);

2209 fts3ColumnlistCopy(0, &p2);

2210 assert( (p1&0xFE)==0 && (p2&0xFE)==0 );

2211 if( 0==p1 \|\| 0==p2 ) break;

2212

2213 p1++;

2214 p1 += fts3GetVarint32(p1, &iCol1);

2215 p2++;

2216 p2 += fts3GetVarint32(p2, &iCol2);

2217 }

2218

2219 /* Advance pointer p1 or p2 (whichever corresponds to the smaller of

2220 ** iCol1 and iCol2) so that it points to either the 0x00 that marks the

2221 ** end of the position list, or the 0x01 that precedes the next

2222 ** column-number in the position list.

2223 */

2224 else if( iCol1<iCol2 ){

2225 fts3ColumnlistCopy(0, &p1);

2226 if( 0==*p1 ) break;

2227 p1++;

2228 p1 += fts3GetVarint32(p1, &iCol1);

2229 }else{

2230 fts3ColumnlistCopy(0, &p2);

2231 if( 0==*p2 ) break;

2232 p2++;

2233 p2 += fts3GetVarint32(p2, &iCol2);

2234 }

2235 }

2236

2237 fts3PoslistCopy(0, &p2);

2238 fts3PoslistCopy(0, &p1);

2239 *pp1 = p1;

2240 *pp2 = p2;

2241 if( *pp==p ){

2242 return 0;

2243 }

2244 *p++ = 0x00;

2245 *pp = p;

2246 return 1;

2247 }

2248

2249 /*

2250 ** Merge two position-lists as required by the NEAR operator. The argument

2251 ** position lists correspond to the left and right phrases of an expression

2252 ** like:

2253 **

2254 ** "phrase 1" NEAR "phrase number 2"

2255 **

2256 ** Position list *pp1 corresponds to the left-hand side of the NEAR

2257 ** expression and *pp2 to the right. As usual, the indexes in the position

2258 ** lists are the offsets of the last token in each phrase (tokens "1" and "2"

2259 ** in the example above).

2260 **

2261 ** The output position list - written to pp - is a copy of pp2 with those

2262 ** entries that are not sufficiently NEAR entries in *pp1 removed.

2263 */

2264 static int fts3PoslistNearMerge(

2265 char *pp, / Output buffer */

2266 char aTmp, / Temporary buffer space */

2267 int nRight, /* Maximum difference in token positions */

2268 int nLeft, /* Maximum difference in token positions */

2269 char *pp1, / IN/OUT: Left input list */

2270 char *pp2 / IN/OUT: Right input list */

2271 ){

2272 char p1 = pp1;

2273 char p2 = pp2;

2274

2275 char *pTmp1 = aTmp;

2276 char *pTmp2;

2277 char *aTmp2;

2278 int res = 1;

2279

2280 fts3PoslistPhraseMerge(&pTmp1, nRight, 0, 0, pp1, pp2);

2281 aTmp2 = pTmp2 = pTmp1;

2282 *pp1 = p1;

2283 *pp2 = p2;

2284 fts3PoslistPhraseMerge(&pTmp2, nLeft, 1, 0, pp2, pp1);

2285 if( pTmp1!=aTmp && pTmp2!=aTmp2 ){

2286 fts3PoslistMerge(pp, &aTmp, &aTmp2);

2287 }else if( pTmp1!=aTmp ){

2288 fts3PoslistCopy(pp, &aTmp);

2289 }else if( pTmp2!=aTmp2 ){

2290 fts3PoslistCopy(pp, &aTmp2);

2291 }else{

2292 res = 0;

2293 }

2294

2295 return res;

2296 }

2297

2298 /*

2299 ** An instance of this function is used to merge together the (potentially

2300 ** large number of) doclists for each term that matches a prefix query.

2301 ** See function fts3TermSelectMerge() for details.

2302 */

2303 typedef struct TermSelect TermSelect;

2304 struct TermSelect {

2305 char aaOutput[16]; / Malloc'd output buffers */

2306 int anOutput[16]; /* Size each output buffer in bytes */

2307 };

2308

2309 /*

2310 ** This function is used to read a single varint from a buffer. Parameter

2311 ** pEnd points 1 byte past the end of the buffer. When this function is

2312 ** called, if *pp points to pEnd or greater, then the end of the buffer

2313 ** has been reached. In this case *pp is set to 0 and the function returns.

2314 **

2315 ** If *pp does not point to or past pEnd, then a single varint is read

2316 ** from pp. pp is then set to point 1 byte past the end of the read varint.

2317 **

2318 ** If bDescIdx is false, the value read is added to *pVal before returning.

2319 ** If it is true, the value read is subtracted from *pVal before this

2320 ** function returns.

2321 */

2322 static void fts3GetDeltaVarint3(

2323 char *pp, / IN/OUT: Point to read varint from */

2324 char pEnd, / End of buffer */

2325 int bDescIdx, /* True if docids are descending */

2326 sqlite3_int64 pVal / IN/OUT: Integer value */

2327 ){

2328 if( *pp>=pEnd ){

2329 *pp = 0;

2330 }else{

2331 sqlite3_int64 iVal;

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

2333 if( bDescIdx ){

2334 *pVal -= iVal;

2335 }else{

2336 *pVal += iVal;

2337 }

2338 }

2339 }

2340

2341 /*

2342 ** This function is used to write a single varint to a buffer. The varint

2343 ** is written to pp. Before returning, pp is set to point 1 byte past the

2344 ** end of the value written.

2345 **

2346 ** If *pbFirst is zero when this function is called, the value written to

2347 ** the buffer is that of parameter iVal.

2348 **

2349 ** If *pbFirst is non-zero when this function is called, then the value

2350 ** written is either (iVal-piPrev) (if bDescIdx is zero) or (piPrev-iVal)

2351 ** (if bDescIdx is non-zero).

2352 **

2353 ** Before returning, this function always sets pbFirst to 1 and piPrev

2354 ** to the value of parameter iVal.

2355 */

2356 static void fts3PutDeltaVarint3(

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

2358 int bDescIdx, /* True for descending docids */

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

2360 int pbFirst, / IN/OUT: True after first int written */

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

2362 ){

2363 sqlite3_int64 iWrite;

2364 if( bDescIdx==0 \|\| *pbFirst==0 ){

2365 iWrite = iVal - *piPrev;

2366 }else{

2367 iWrite = *piPrev - iVal;

2368 }

2369 assert( pbFirst \|\| piPrev==0 );

2370 assert( *pbFirst==0 \|\| iWrite>0 );

2371 pp += sqlite3Fts3PutVarint(pp, iWrite);

2372 *piPrev = iVal;

2373 *pbFirst = 1;

2374 }

2375

2376

2377 /*

2378 ** This macro is used by various functions that merge doclists. The two

2379 ** arguments are 64-bit docid values. If the value of the stack variable

2380 ** bDescDoclist is 0 when this macro is invoked, then it returns (i1-i2).

2381 ** Otherwise, (i2-i1).

2382 **

2383 ** Using this makes it easier to write code that can merge doclists that are

2384 ** sorted in either ascending or descending order.

2385 */

2386 #define DOCID_CMP(i1, i2) ((bDescDoclist?-1:1) * (i1-i2))

2387

2388 /*

2389 ** This function does an "OR" merge of two doclists (output contains all

2390 ** positions contained in either argument doclist). If the docids in the

2391 ** input doclists are sorted in ascending order, parameter bDescDoclist

2392 ** should be false. If they are sorted in ascending order, it should be

2393 ** passed a non-zero value.

2394 **

2395 ** If no error occurs, *paOut is set to point at an sqlite3_malloc'd buffer

2396 ** containing the output doclist and SQLITE_OK is returned. In this case

2397 ** *pnOut is set to the number of bytes in the output doclist.

2398 **

2399 ** If an error occurs, an SQLite error code is returned. The output values

2400 ** are undefined in this case.

2401 */

2402 static int fts3DoclistOrMerge(

2403 int bDescDoclist, /* True if arguments are desc */

2404 char a1, int n1, / First doclist */

2405 char a2, int n2, / Second doclist */

2406 char *paOut, int pnOut /* OUT: Malloc'd doclist */

2407 ){

2408 sqlite3_int64 i1 = 0;

2409 sqlite3_int64 i2 = 0;

2410 sqlite3_int64 iPrev = 0;

2411 char *pEnd1 = &a1[n1];

2412 char *pEnd2 = &a2[n2];

2413 char *p1 = a1;

2414 char *p2 = a2;

2415 char *p;

2416 char *aOut;

2417 int bFirstOut = 0;

2418

2419 *paOut = 0;

2420 *pnOut = 0;

2421

2422 /* Allocate space for the output. Both the input and output doclists

2423 ** are delta encoded. If they are in ascending order (bDescDoclist==0),

2424 ** then the first docid in each list is simply encoded as a varint. For

2425 ** each subsequent docid, the varint stored is the difference between the

2426 ** current and previous docid (a positive number - since the list is in

2427 ** ascending order).

2428 **

2429 ** The first docid written to the output is therefore encoded using the

2430 ** same number of bytes as it is in whichever of the input lists it is

2431 ** read from. And each subsequent docid read from the same input list

2432 ** consumes either the same or less bytes as it did in the input (since

2433 ** the difference between it and the previous value in the output must

2434 ** be a positive value less than or equal to the delta value read from

2435 ** the input list). The same argument applies to all but the first docid

2436 ** read from the 'other' list. And to the contents of all position lists

2437 ** that will be copied and merged from the input to the output.

2438 **

2439 ** However, if the first docid copied to the output is a negative number,

2440 ** then the encoding of the first docid from the 'other' input list may

2441 ** be larger in the output than it was in the input (since the delta value

2442 ** may be a larger positive integer than the actual docid).

2443 **

2444 ** The space required to store the output is therefore the sum of the

2445 ** sizes of the two inputs, plus enough space for exactly one of the input

2446 ** docids to grow.

2447 **

2448 ** A symetric argument may be made if the doclists are in descending

2449 ** order.

2450 */

2451 aOut = sqlite3_malloc(n1+n2+FTS3_VARINT_MAX-1);

2452 if( !aOut ) return SQLITE_NOMEM;

2453

2454 p = aOut;

2455 fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1);

2456 fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2);

2457 while( p1 \|\| p2 ){

2458 sqlite3_int64 iDiff = DOCID_CMP(i1, i2);

2459

2460 if( p2 && p1 && iDiff==0 ){

2461 fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i1);

2462 fts3PoslistMerge(&p, &p1, &p2);

2463 fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);

2464 fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);

2465 }else if( !p2 \|\| (p1 && iDiff<0) ){

2466 fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i1);

2467 fts3PoslistCopy(&p, &p1);

2468 fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);

2469 }else{

2470 fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i2);

2471 fts3PoslistCopy(&p, &p2);

2472 fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);

2473 }

2474 }

2475

2476 *paOut = aOut;

2477 *pnOut = (int)(p-aOut);

2478 assert( *pnOut<=n1+n2+FTS3_VARINT_MAX-1 );

2479 return SQLITE_OK;

2480 }

2481

2482 /*

2483 ** This function does a "phrase" merge of two doclists. In a phrase merge,

2484 ** the output contains a copy of each position from the right-hand input

2485 ** doclist for which there is a position in the left-hand input doclist

2486 ** exactly nDist tokens before it.

2487 **

2488 ** If the docids in the input doclists are sorted in ascending order,

2489 ** parameter bDescDoclist should be false. If they are sorted in ascending

2490 ** order, it should be passed a non-zero value.

2491 **

2492 ** The right-hand input doclist is overwritten by this function.

2493 */

2494 static void fts3DoclistPhraseMerge(

2495 int bDescDoclist, /* True if arguments are desc */

2496 int nDist, /* Distance from left to right (1=adjacent) */

2497 char aLeft, int nLeft, / Left doclist */

2498 char aRight, int pnRight /* IN/OUT: Right/output doclist */

2499 ){

2500 sqlite3_int64 i1 = 0;

2501 sqlite3_int64 i2 = 0;

2502 sqlite3_int64 iPrev = 0;

2503 char *pEnd1 = &aLeft[nLeft];

2504 char pEnd2 = &aRight[pnRight];

2505 char *p1 = aLeft;

2506 char *p2 = aRight;

2507 char *p;

2508 int bFirstOut = 0;

2509 char *aOut = aRight;

2510

2511 assert( nDist>0 );

2512

2513 p = aOut;

2514 fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1);

2515 fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2);

2516

2517 while( p1 && p2 ){

2518 sqlite3_int64 iDiff = DOCID_CMP(i1, i2);

2519 if( iDiff==0 ){

2520 char *pSave = p;

2521 sqlite3_int64 iPrevSave = iPrev;

2522 int bFirstOutSave = bFirstOut;

2523

2524 fts3PutDeltaVarint3(&p, bDescDoclist, &iPrev, &bFirstOut, i1);

2525 if( 0==fts3PoslistPhraseMerge(&p, nDist, 0, 1, &p1, &p2) ){

2526 p = pSave;

2527 iPrev = iPrevSave;

2528 bFirstOut = bFirstOutSave;

2529 }

2530 fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);

2531 fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);

2532 }else if( iDiff<0 ){

2533 fts3PoslistCopy(0, &p1);

2534 fts3GetDeltaVarint3(&p1, pEnd1, bDescDoclist, &i1);

2535 }else{

2536 fts3PoslistCopy(0, &p2);

2537 fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);

2538 }

2539 }

2540

2541 *pnRight = (int)(p - aOut);

2542 }

2543

2544 /*

2545 ** Argument pList points to a position list nList bytes in size. This

2546 ** function checks to see if the position list contains any entries for

2547 ** a token in position 0 (of any column). If so, it writes argument iDelta

2548 ** to the output buffer pOut, followed by a position list consisting only

2549 ** of the entries from pList at position 0, and terminated by an 0x00 byte.

2550 ** The value returned is the number of bytes written to pOut (if any).

2551 */

2552 int sqlite3Fts3FirstFilter(

2553 sqlite3_int64 iDelta, /* Varint that may be written to pOut */

2554 char pList, / Position list (no 0x00 term) */

2555 int nList, /* Size of pList in bytes */

2556 char pOut / Write output here */

2557 ){

2558 int nOut = 0;

2559 int bWritten = 0; /* True once iDelta has been written */

2560 char *p = pList;

2561 char *pEnd = &pList[nList];

2562

2563 if( *p!=0x01 ){

2564 if( *p==0x02 ){

2565 nOut += sqlite3Fts3PutVarint(&pOut[nOut], iDelta);

2566 pOut[nOut++] = 0x02;

2567 bWritten = 1;

2568 }

2569 fts3ColumnlistCopy(0, &p);

2570 }

2571

2572 while( p<pEnd && *p==0x01 ){

2573 sqlite3_int64 iCol;

2574 p++;

2575 p += sqlite3Fts3GetVarint(p, &iCol);

2576 if( *p==0x02 ){

2577 if( bWritten==0 ){

2578 nOut += sqlite3Fts3PutVarint(&pOut[nOut], iDelta);

2579 bWritten = 1;

2580 }

2581 pOut[nOut++] = 0x01;

2582 nOut += sqlite3Fts3PutVarint(&pOut[nOut], iCol);

2583 pOut[nOut++] = 0x02;

2584 }

2585 fts3ColumnlistCopy(0, &p);

2586 }

2587 if( bWritten ){

2588 pOut[nOut++] = 0x00;

2589 }

2590

2591 return nOut;

2592 }

2593

2594

2595 /*

2596 ** Merge all doclists in the TermSelect.aaOutput[] array into a single

2597 ** doclist stored in TermSelect.aaOutput[0]. If successful, delete all

2598 ** other doclists (except the aaOutput[0] one) and return SQLITE_OK.

2599 **

2600 ** If an OOM error occurs, return SQLITE_NOMEM. In this case it is

2601 ** the responsibility of the caller to free any doclists left in the

2602 ** TermSelect.aaOutput[] array.

2603 */

2604 static int fts3TermSelectFinishMerge(Fts3Table p, TermSelect pTS){

2605 char *aOut = 0;

2606 int nOut = 0;

2607 int i;

2608

2609 /* Loop through the doclists in the aaOutput[] array. Merge them all

2610 ** into a single doclist.

2611 */

2612 for(i=0; i<SizeofArray(pTS->aaOutput); i++){

2613 if( pTS->aaOutput[i] ){

2614 if( !aOut ){

2615 aOut = pTS->aaOutput[i];

2616 nOut = pTS->anOutput[i];

2617 pTS->aaOutput[i] = 0;

2618 }else{

2619 int nNew;

2620 char *aNew;

2621

2622 int rc = fts3DoclistOrMerge(p->bDescIdx,

2623 pTS->aaOutput[i], pTS->anOutput[i], aOut, nOut, &aNew, &nNew

2624 );

2625 if( rc!=SQLITE_OK ){

2626 sqlite3_free(aOut);

2627 return rc;

2628 }

2629

2630 sqlite3_free(pTS->aaOutput[i]);

2631 sqlite3_free(aOut);

2632 pTS->aaOutput[i] = 0;

2633 aOut = aNew;

2634 nOut = nNew;

2635 }

2636 }

2637 }

2638

2639 pTS->aaOutput[0] = aOut;

2640 pTS->anOutput[0] = nOut;

2641 return SQLITE_OK;

2642 }

2643

2644 /*

2645 ** Merge the doclist aDoclist/nDoclist into the TermSelect object passed

2646 ** as the first argument. The merge is an "OR" merge (see function

2647 ** fts3DoclistOrMerge() for details).

2648 **

2649 ** This function is called with the doclist for each term that matches

2650 ** a queried prefix. It merges all these doclists into one, the doclist

2651 ** for the specified prefix. Since there can be a very large number of

2652 ** doclists to merge, the merging is done pair-wise using the TermSelect

2653 ** object.

2654 **

2655 ** This function returns SQLITE_OK if the merge is successful, or an

2656 ** SQLite error code (SQLITE_NOMEM) if an error occurs.

2657 */

2658 static int fts3TermSelectMerge(

2659 Fts3Table p, / FTS table handle */

2660 TermSelect pTS, / TermSelect object to merge into */

2661 char aDoclist, / Pointer to doclist */

2662 int nDoclist /* Size of aDoclist in bytes */

2663 ){

2664 if( pTS->aaOutput[0]==0 ){

2665 /* If this is the first term selected, copy the doclist to the output

2666 ** buffer using memcpy(). */

2667 pTS->aaOutput[0] = sqlite3_malloc(nDoclist);

2668 pTS->anOutput[0] = nDoclist;

2669 if( pTS->aaOutput[0] ){

2670 memcpy(pTS->aaOutput[0], aDoclist, nDoclist);

2671 }else{

2672 return SQLITE_NOMEM;

2673 }

2674 }else{

2675 char *aMerge = aDoclist;

2676 int nMerge = nDoclist;

2677 int iOut;

2678

2679 for(iOut=0; iOut<SizeofArray(pTS->aaOutput); iOut++){

2680 if( pTS->aaOutput[iOut]==0 ){

2681 assert( iOut>0 );

2682 pTS->aaOutput[iOut] = aMerge;

2683 pTS->anOutput[iOut] = nMerge;

2684 break;

2685 }else{

2686 char *aNew;

2687 int nNew;

2688

2689 int rc = fts3DoclistOrMerge(p->bDescIdx, aMerge, nMerge,

2690 pTS->aaOutput[iOut], pTS->anOutput[iOut], &aNew, &nNew

2691 );

2692 if( rc!=SQLITE_OK ){

2693 if( aMerge!=aDoclist ) sqlite3_free(aMerge);

2694 return rc;

2695 }

2696

2697 if( aMerge!=aDoclist ) sqlite3_free(aMerge);

2698 sqlite3_free(pTS->aaOutput[iOut]);

2699 pTS->aaOutput[iOut] = 0;

2700

2701 aMerge = aNew;

2702 nMerge = nNew;

2703 if( (iOut+1)==SizeofArray(pTS->aaOutput) ){

2704 pTS->aaOutput[iOut] = aMerge;

2705 pTS->anOutput[iOut] = nMerge;

2706 }

2707 }

2708 }

2709 }

2710 return SQLITE_OK;

2711 }

2712

2713 /*

2714 ** Append SegReader object pNew to the end of the pCsr->apSegment[] array.

2715 */

2716 static int fts3SegReaderCursorAppend(

2717 Fts3MultiSegReader *pCsr,

2718 Fts3SegReader *pNew

2719 ){

2720 if( (pCsr->nSegment%16)==0 ){

2721 Fts3SegReader **apNew;

2722 int nByte = (pCsr->nSegment + 16)sizeof(Fts3SegReader);

2723 apNew = (Fts3SegReader **)sqlite3_realloc(pCsr->apSegment, nByte);

2724 if( !apNew ){

2725 sqlite3Fts3SegReaderFree(pNew);

2726 return SQLITE_NOMEM;

2727 }

2728 pCsr->apSegment = apNew;

2729 }

2730 pCsr->apSegment[pCsr->nSegment++] = pNew;

2731 return SQLITE_OK;

2732 }

2733

2734 /*

2735 ** Add seg-reader objects to the Fts3MultiSegReader object passed as the

2736 ** 8th argument.

2737 **

2738 ** This function returns SQLITE_OK if successful, or an SQLite error code

2739 ** otherwise.

2740 */

2741 static int fts3SegReaderCursor(

2742 Fts3Table p, / FTS3 table handle */

2743 int iLangid, /* Language id */

2744 int iIndex, /* Index to search (from 0 to p->nIndex-1) */

2745 int iLevel, /* Level of segments to scan */

2746 const char zTerm, / Term to query for */

2747 int nTerm, /* Size of zTerm in bytes */

2748 int isPrefix, /* True for a prefix search */

2749 int isScan, /* True to scan from zTerm to EOF */

2750 Fts3MultiSegReader pCsr / Cursor object to populate */

2751 ){

2752 int rc = SQLITE_OK; /* Error code */

2753 sqlite3_stmt pStmt = 0; / Statement to iterate through segments */

2754 int rc2; /* Result of sqlite3_reset() */

2755

2756 /* If iLevel is less than 0 and this is not a scan, include a seg-reader

2757 ** for the pending-terms. If this is a scan, then this call must be being

2758 ** made by an fts4aux module, not an FTS table. In this case calling

2759 ** Fts3SegReaderPending might segfault, as the data structures used by

2760 ** fts4aux are not completely populated. So it's easiest to filter these

2761 ** calls out here. */

2762 if( iLevel<0 && p->aIndex ){

2763 Fts3SegReader *pSeg = 0;

2764 rc = sqlite3Fts3SegReaderPending(p, iIndex, zTerm, nTerm, isPrefix, &pSeg);

2765 if( rc==SQLITE_OK && pSeg ){

2766 rc = fts3SegReaderCursorAppend(pCsr, pSeg);

2767 }

2768 }

2769

2770 if( iLevel!=FTS3_SEGCURSOR_PENDING ){

2771 if( rc==SQLITE_OK ){

2772 rc = sqlite3Fts3AllSegdirs(p, iLangid, iIndex, iLevel, &pStmt);

2773 }

2774

2775 while( rc==SQLITE_OK && SQLITE_ROW==(rc = sqlite3_step(pStmt)) ){

2776 Fts3SegReader *pSeg = 0;

2777

2778 /* Read the values returned by the SELECT into local variables. */

2779 sqlite3_int64 iStartBlock = sqlite3_column_int64(pStmt, 1);

2780 sqlite3_int64 iLeavesEndBlock = sqlite3_column_int64(pStmt, 2);

2781 sqlite3_int64 iEndBlock = sqlite3_column_int64(pStmt, 3);

2782 int nRoot = sqlite3_column_bytes(pStmt, 4);

2783 char const *zRoot = sqlite3_column_blob(pStmt, 4);

2784

2785 /* If zTerm is not NULL, and this segment is not stored entirely on its

2786 ** root node, the range of leaves scanned can be reduced. Do this. */

2787 if( iStartBlock && zTerm ){

2788 sqlite3_int64 *pi = (isPrefix ? &iLeavesEndBlock : 0);

2789 rc = fts3SelectLeaf(p, zTerm, nTerm, zRoot, nRoot, &iStartBlock, pi);

2790 if( rc!=SQLITE_OK ) goto finished;

2791 if( isPrefix==0 && isScan==0 ) iLeavesEndBlock = iStartBlock;

2792 }

2793

2794 rc = sqlite3Fts3SegReaderNew(pCsr->nSegment+1,

2795 (isPrefix==0 && isScan==0),

2796 iStartBlock, iLeavesEndBlock,

2797 iEndBlock, zRoot, nRoot, &pSeg

2798 );

2799 if( rc!=SQLITE_OK ) goto finished;

2800 rc = fts3SegReaderCursorAppend(pCsr, pSeg);

2801 }

2802 }

2803

2804 finished:

2805 rc2 = sqlite3_reset(pStmt);

2806 if( rc==SQLITE_DONE ) rc = rc2;

2807

2808 return rc;

2809 }

2810

2811 /*

2812 ** Set up a cursor object for iterating through a full-text index or a

2813 ** single level therein.

2814 */

2815 int sqlite3Fts3SegReaderCursor(

2816 Fts3Table p, / FTS3 table handle */

2817 int iLangid, /* Language-id to search */

2818 int iIndex, /* Index to search (from 0 to p->nIndex-1) */

2819 int iLevel, /* Level of segments to scan */

2820 const char zTerm, / Term to query for */

2821 int nTerm, /* Size of zTerm in bytes */

2822 int isPrefix, /* True for a prefix search */

2823 int isScan, /* True to scan from zTerm to EOF */

2824 Fts3MultiSegReader pCsr / Cursor object to populate */

2825 ){

2826 assert( iIndex>=0 && iIndex<p->nIndex );

2827 assert( iLevel==FTS3_SEGCURSOR_ALL

2828 \|\| iLevel==FTS3_SEGCURSOR_PENDING

2829 \|\| iLevel>=0

2830 );

2831 assert( iLevel<FTS3_SEGDIR_MAXLEVEL );

2832 assert( FTS3_SEGCURSOR_ALL<0 && FTS3_SEGCURSOR_PENDING<0 );

2833 assert( isPrefix==0 \|\| isScan==0 );

2834

2835 memset(pCsr, 0, sizeof(Fts3MultiSegReader));

2836 return fts3SegReaderCursor(

2837 p, iLangid, iIndex, iLevel, zTerm, nTerm, isPrefix, isScan, pCsr

2838 );

2839 }

2840

2841 /*

2842 ** In addition to its current configuration, have the Fts3MultiSegReader

2843 ** passed as the 4th argument also scan the doclist for term zTerm/nTerm.

2844 **

2845 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.

2846 */

2847 static int fts3SegReaderCursorAddZero(

2848 Fts3Table p, / FTS virtual table handle */

2849 int iLangid,

2850 const char zTerm, / Term to scan doclist of */

2851 int nTerm, /* Number of bytes in zTerm */

2852 Fts3MultiSegReader pCsr / Fts3MultiSegReader to modify */

2853 ){

2854 return fts3SegReaderCursor(p,

2855 iLangid, 0, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 0, 0,pCsr

2856 );

2857 }

2858

2859 /*

2860 ** Open an Fts3MultiSegReader to scan the doclist for term zTerm/nTerm. Or,

2861 ** if isPrefix is true, to scan the doclist for all terms for which

2862 ** zTerm/nTerm is a prefix. If successful, return SQLITE_OK and write

2863 ** a pointer to the new Fts3MultiSegReader to *ppSegcsr. Otherwise, return

2864 ** an SQLite error code.

2865 **

2866 ** It is the responsibility of the caller to free this object by eventually

2867 ** passing it to fts3SegReaderCursorFree()

2868 **

2869 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.

2870 ** Output parameter *ppSegcsr is set to 0 if an error occurs.

2871 */

2872 static int fts3TermSegReaderCursor(

2873 Fts3Cursor pCsr, / Virtual table cursor handle */

2874 const char zTerm, / Term to query for */

2875 int nTerm, /* Size of zTerm in bytes */

2876 int isPrefix, /* True for a prefix search */

2877 Fts3MultiSegReader *ppSegcsr / OUT: Allocated seg-reader cursor */

2878 ){

2879 Fts3MultiSegReader pSegcsr; / Object to allocate and return */

2880 int rc = SQLITE_NOMEM; /* Return code */

2881

2882 pSegcsr = sqlite3_malloc(sizeof(Fts3MultiSegReader));

2883 if( pSegcsr ){

2884 int i;

2885 int bFound = 0; /* True once an index has been found */

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

2887

2888 if( isPrefix ){

2889 for(i=1; bFound==0 && i<p->nIndex; i++){

2890 if( p->aIndex[i].nPrefix==nTerm ){

2891 bFound = 1;

2892 rc = sqlite3Fts3SegReaderCursor(p, pCsr->iLangid,

2893 i, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 0, 0, pSegcsr

2894 );

2895 pSegcsr->bLookup = 1;

2896 }

2897 }

2898

2899 for(i=1; bFound==0 && i<p->nIndex; i++){

2900 if( p->aIndex[i].nPrefix==nTerm+1 ){

2901 bFound = 1;

2902 rc = sqlite3Fts3SegReaderCursor(p, pCsr->iLangid,

2903 i, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 1, 0, pSegcsr

2904 );

2905 if( rc==SQLITE_OK ){

2906 rc = fts3SegReaderCursorAddZero(

2907 p, pCsr->iLangid, zTerm, nTerm, pSegcsr

2908 );

2909 }

2910 }

2911 }

2912 }

2913

2914 if( bFound==0 ){

2915 rc = sqlite3Fts3SegReaderCursor(p, pCsr->iLangid,

2916 0, FTS3_SEGCURSOR_ALL, zTerm, nTerm, isPrefix, 0, pSegcsr

2917 );

2918 pSegcsr->bLookup = !isPrefix;

2919 }

2920 }

2921

2922 *ppSegcsr = pSegcsr;

2923 return rc;

2924 }

2925

2926 /*

2927 ** Free an Fts3MultiSegReader allocated by fts3TermSegReaderCursor().

2928 */

2929 static void fts3SegReaderCursorFree(Fts3MultiSegReader *pSegcsr){

2930 sqlite3Fts3SegReaderFinish(pSegcsr);

2931 sqlite3_free(pSegcsr);

2932 }

2933

2934 /*

2935 ** This function retrieves the doclist for the specified term (or term

2936 ** prefix) from the database.

2937 */

2938 static int fts3TermSelect(

2939 Fts3Table p, / Virtual table handle */

2940 Fts3PhraseToken pTok, / Token to query for */

2941 int iColumn, /* Column to query (or -ve for all columns) */

2942 int pnOut, / OUT: Size of buffer at ppOut /

2943 char *ppOut / OUT: Malloced result buffer */

2944 ){

2945 int rc; /* Return code */

2946 Fts3MultiSegReader pSegcsr; / Seg-reader cursor for this term */

2947 TermSelect tsc; /* Object for pair-wise doclist merging */

2948 Fts3SegFilter filter; /* Segment term filter configuration */

2949

2950 pSegcsr = pTok->pSegcsr;

2951 memset(&tsc, 0, sizeof(TermSelect));

2952

2953 filter.flags = FTS3_SEGMENT_IGNORE_EMPTY \| FTS3_SEGMENT_REQUIRE_POS

2954 \| (pTok->isPrefix ? FTS3_SEGMENT_PREFIX : 0)

2955 \| (pTok->bFirst ? FTS3_SEGMENT_FIRST : 0)

2956 \| (iColumn<p->nColumn ? FTS3_SEGMENT_COLUMN_FILTER : 0);

2957 filter.iCol = iColumn;

2958 filter.zTerm = pTok->z;

2959 filter.nTerm = pTok->n;

2960

2961 rc = sqlite3Fts3SegReaderStart(p, pSegcsr, &filter);

2962 while( SQLITE_OK==rc

2963 && SQLITE_ROW==(rc = sqlite3Fts3SegReaderStep(p, pSegcsr))

2964 ){

2965 rc = fts3TermSelectMerge(p, &tsc, pSegcsr->aDoclist, pSegcsr->nDoclist);

2966 }

2967

2968 if( rc==SQLITE_OK ){

2969 rc = fts3TermSelectFinishMerge(p, &tsc);

2970 }

2971 if( rc==SQLITE_OK ){

2972 *ppOut = tsc.aaOutput[0];

2973 *pnOut = tsc.anOutput[0];

2974 }else{

2975 int i;

2976 for(i=0; i<SizeofArray(tsc.aaOutput); i++){

2977 sqlite3_free(tsc.aaOutput[i]);

2978 }

2979 }

2980

2981 fts3SegReaderCursorFree(pSegcsr);

2982 pTok->pSegcsr = 0;

2983 return rc;

2984 }

2985

2986 /*

2987 ** This function counts the total number of docids in the doclist stored

2988 ** in buffer aList[], size nList bytes.

2989 **

2990 ** If the isPoslist argument is true, then it is assumed that the doclist

2991 ** contains a position-list following each docid. Otherwise, it is assumed

2992 ** that the doclist is simply a list of docids stored as delta encoded

2993 ** varints.

2994 */

2995 static int fts3DoclistCountDocids(char *aList, int nList){

2996 int nDoc = 0; /* Return value */

2997 if( aList ){

2998 char aEnd = &aList[nList]; / Pointer to one byte after EOF */

2999 char p = aList; / Cursor */

3000 while( p<aEnd ){

3001 nDoc++;

3002 while( (p++)&0x80 ); / Skip docid varint */

3003 fts3PoslistCopy(0, &p); /* Skip over position list */

3004 }

3005 }

3006

3007 return nDoc;

3008 }

3009

3010 /*

3011 ** Advance the cursor to the next row in the %_content table that

3012 ** matches the search criteria. For a MATCH search, this will be

3013 ** the next row that matches. For a full-table scan, this will be

3014 ** simply the next row in the %_content table. For a docid lookup,

3015 ** this routine simply sets the EOF flag.

3016 **

3017 ** Return SQLITE_OK if nothing goes wrong. SQLITE_OK is returned

3018 ** even if we reach end-of-file. The fts3EofMethod() will be called

3019 ** subsequently to determine whether or not an EOF was hit.

3020 */

3021 static int fts3NextMethod(sqlite3_vtab_cursor *pCursor){

3022 int rc;

3023 Fts3Cursor pCsr = (Fts3Cursor )pCursor;

3024 if( pCsr->eSearch==FTS3_DOCID_SEARCH \|\| pCsr->eSearch==FTS3_FULLSCAN_SEARCH ){

3025 if( SQLITE_ROW!=sqlite3_step(pCsr->pStmt) ){

3026 pCsr->isEof = 1;

3027 rc = sqlite3_reset(pCsr->pStmt);

3028 }else{

3029 pCsr->iPrevId = sqlite3_column_int64(pCsr->pStmt, 0);

3030 rc = SQLITE_OK;

3031 }

3032 }else{

3033 rc = fts3EvalNext((Fts3Cursor *)pCursor);

3034 }

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

3036 return rc;

3037 }

3038

3039 /*

3040 ** The following are copied from sqliteInt.h.

3041 **

3042 ** Constants for the largest and smallest possible 64-bit signed integers.

3043 ** These macros are designed to work correctly on both 32-bit and 64-bit

3044 ** compilers.

3045 */

3046 #ifndef SQLITE_AMALGAMATION

3047 # define LARGEST_INT64 (0xffffffff\|(((sqlite3_int64)0x7fffffff)<<32))

3048 # define SMALLEST_INT64 (((sqlite3_int64)-1) - LARGEST_INT64)

3049 #endif

3050

3051 /*

3052 ** If the numeric type of argument pVal is "integer", then return it

3053 ** converted to a 64-bit signed integer. Otherwise, return a copy of

3054 ** the second parameter, iDefault.

3055 */

3056 static sqlite3_int64 fts3DocidRange(sqlite3_value *pVal, i64 iDefault){

3057 if( pVal ){

3058 int eType = sqlite3_value_numeric_type(pVal);

3059 if( eType==SQLITE_INTEGER ){

3060 return sqlite3_value_int64(pVal);

3061 }

3062 }

3063 return iDefault;

3064 }

3065

3066 /*

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

3068 ** the virtual table xFilter method documentation for additional

3069 ** information.

3070 **

3071 ** If idxNum==FTS3_FULLSCAN_SEARCH then do a full table scan against

3072 ** the %_content table.

3073 **

3074 ** If idxNum==FTS3_DOCID_SEARCH then do a docid lookup for a single entry

3075 ** in the %_content table.

3076 **

3077 ** If idxNum>=FTS3_FULLTEXT_SEARCH then use the full text index. The

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

3079 ** number idxNum-FTS3_FULLTEXT_SEARCH, 0 indexed. argv[0] is the right-hand

3080 ** side of the MATCH operator.

3081 */

3082 static int fts3FilterMethod(

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

3084 int idxNum, /* Strategy index */

3085 const char idxStr, / Unused */

3086 int nVal, /* Number of elements in apVal */

3087 sqlite3_value *apVal / Arguments for the indexing scheme */

3088 ){

3089 int rc;

3090 char zSql; / SQL statement used to access %_content */

3091 int eSearch;

3092 Fts3Table p = (Fts3Table )pCursor->pVtab;

3093 Fts3Cursor pCsr = (Fts3Cursor )pCursor;

3094

3095 sqlite3_value pCons = 0; / The MATCH or rowid constraint, if any */

3096 sqlite3_value pLangid = 0; / The "langid = ?" constraint, if any */

3097 sqlite3_value pDocidGe = 0; / The "docid >= ?" constraint, if any */

3098 sqlite3_value pDocidLe = 0; / The "docid <= ?" constraint, if any */

3099 int iIdx;

3100

3101 UNUSED_PARAMETER(idxStr);

3102 UNUSED_PARAMETER(nVal);

3103

3104 eSearch = (idxNum & 0x0000FFFF);

3105 assert( eSearch>=0 && eSearch<=(FTS3_FULLTEXT_SEARCH+p->nColumn) );

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

3107

3108 /* Collect arguments into local variables */

3109 iIdx = 0;

3110 if( eSearch!=FTS3_FULLSCAN_SEARCH ) pCons = apVal[iIdx++];

3111 if( idxNum & FTS3_HAVE_LANGID ) pLangid = apVal[iIdx++];

3112 if( idxNum & FTS3_HAVE_DOCID_GE ) pDocidGe = apVal[iIdx++];

3113 if( idxNum & FTS3_HAVE_DOCID_LE ) pDocidLe = apVal[iIdx++];

3114 assert( iIdx==nVal );

3115

3116 /* In case the cursor has been used before, clear it now. */

3117 sqlite3_finalize(pCsr->pStmt);

3118 sqlite3_free(pCsr->aDoclist);

3119 sqlite3_free(pCsr->aMatchinfo);

3120 sqlite3Fts3ExprFree(pCsr->pExpr);

3121 memset(&pCursor[1], 0, sizeof(Fts3Cursor)-sizeof(sqlite3_vtab_cursor));

3122

3123 /* Set the lower and upper bounds on docids to return */

3124 pCsr->iMinDocid = fts3DocidRange(pDocidGe, SMALLEST_INT64);

3125 pCsr->iMaxDocid = fts3DocidRange(pDocidLe, LARGEST_INT64);

3126

3127 if( idxStr ){

3128 pCsr->bDesc = (idxStr[0]=='D');

3129 }else{

3130 pCsr->bDesc = p->bDescIdx;

3131 }

3132 pCsr->eSearch = (i16)eSearch;

3133

3134 if( eSearch!=FTS3_DOCID_SEARCH && eSearch!=FTS3_FULLSCAN_SEARCH ){

3135 int iCol = eSearch-FTS3_FULLTEXT_SEARCH;

3136 const char zQuery = (const char )sqlite3_value_text(pCons);

3137

3138 if( zQuery==0 && sqlite3_value_type(pCons)!=SQLITE_NULL ){

3139 return SQLITE_NOMEM;

3140 }

3141

3142 pCsr->iLangid = 0;

3143 if( pLangid ) pCsr->iLangid = sqlite3_value_int(pLangid);

3144

3145 assert( p->base.zErrMsg==0 );

3146 rc = sqlite3Fts3ExprParse(p->pTokenizer, pCsr->iLangid,

3147 p->azColumn, p->bFts4, p->nColumn, iCol, zQuery, -1, &pCsr->pExpr,

3148 &p->base.zErrMsg

3149 );

3150 if( rc!=SQLITE_OK ){

3151 return rc;

3152 }

3153

3154 rc = fts3EvalStart(pCsr);

3155 sqlite3Fts3SegmentsClose(p);

3156 if( rc!=SQLITE_OK ) return rc;

3157 pCsr->pNextId = pCsr->aDoclist;

3158 pCsr->iPrevId = 0;

3159 }

3160

3161 /* Compile a SELECT statement for this cursor. For a full-table-scan, the

3162 ** statement loops through all rows of the %_content table. For a

3163 ** full-text query or docid lookup, the statement retrieves a single

3164 ** row by docid.

3165 */

3166 if( eSearch==FTS3_FULLSCAN_SEARCH ){

3167 zSql = sqlite3_mprintf(

3168 "SELECT %s ORDER BY rowid %s",

3169 p->zReadExprlist, (pCsr->bDesc ? "DESC" : "ASC")

3170 );

3171 if( zSql ){

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

3173 sqlite3_free(zSql);

3174 }else{

3175 rc = SQLITE_NOMEM;

3176 }

3177 }else if( eSearch==FTS3_DOCID_SEARCH ){

3178 rc = fts3CursorSeekStmt(pCsr, &pCsr->pStmt);

3179 if( rc==SQLITE_OK ){

3180 rc = sqlite3_bind_value(pCsr->pStmt, 1, pCons);

3181 }

3182 }

3183 if( rc!=SQLITE_OK ) return rc;

3184

3185 return fts3NextMethod(pCursor);

3186 }

3187

3188 /*

3189 ** This is the xEof method of the virtual table. SQLite calls this

3190 ** routine to find out if it has reached the end of a result set.

3191 */

3192 static int fts3EofMethod(sqlite3_vtab_cursor *pCursor){

3193 return ((Fts3Cursor *)pCursor)->isEof;

3194 }

3195

3196 /*

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

3198 ** retrieve the rowid for the current row of the result set. fts3

3199 ** exposes %_content.docid as the rowid for the virtual table. The

3200 ** rowid should be written to *pRowid.

3201 */

3202 static int fts3RowidMethod(sqlite3_vtab_cursor pCursor, sqlite_int64 pRowid){

3203 Fts3Cursor pCsr = (Fts3Cursor ) pCursor;

3204 *pRowid = pCsr->iPrevId;

3205 return SQLITE_OK;

3206 }

3207

3208 /*

3209 ** This is the xColumn method, called by SQLite to request a value from

3210 ** the row that the supplied cursor currently points to.

3211 **

3212 ** If:

3213 **

3214 ** (iCol < p->nColumn) -> The value of the iCol'th user column.

3215 ** (iCol == p->nColumn) -> Magic column with the same name as the table.

3216 ** (iCol == p->nColumn+1) -> Docid column

3217 ** (iCol == p->nColumn+2) -> Langid column

3218 */

3219 static int fts3ColumnMethod(

3220 sqlite3_vtab_cursor pCursor, / Cursor to retrieve value from */

3221 sqlite3_context pCtx, / Context for sqlite3_result_xxx() calls */

3222 int iCol /* Index of column to read value from */

3223 ){

3224 int rc = SQLITE_OK; /* Return Code */

3225 Fts3Cursor pCsr = (Fts3Cursor ) pCursor;

3226 Fts3Table p = (Fts3Table )pCursor->pVtab;

3227

3228 /* The column value supplied by SQLite must be in range. */

3229 assert( iCol>=0 && iCol<=p->nColumn+2 );

3230

3231 if( iCol==p->nColumn+1 ){

3232 /* This call is a request for the "docid" column. Since "docid" is an

3233 ** alias for "rowid", use the xRowid() method to obtain the value.

3234 */

3235 sqlite3_result_int64(pCtx, pCsr->iPrevId);

3236 }else if( iCol==p->nColumn ){

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

3238 ** Return a blob which is a pointer to the cursor. */

3239 sqlite3_result_blob(pCtx, &pCsr, sizeof(pCsr), SQLITE_TRANSIENT);

3240 }else if( iCol==p->nColumn+2 && pCsr->pExpr ){

3241 sqlite3_result_int64(pCtx, pCsr->iLangid);

3242 }else{

3243 /* The requested column is either a user column (one that contains

3244 ** indexed data), or the language-id column. */

3245 rc = fts3CursorSeek(0, pCsr);

3246

3247 if( rc==SQLITE_OK ){

3248 if( iCol==p->nColumn+2 ){

3249 int iLangid = 0;

3250 if( p->zLanguageid ){

3251 iLangid = sqlite3_column_int(pCsr->pStmt, p->nColumn+1);

3252 }

3253 sqlite3_result_int(pCtx, iLangid);

3254 }else if( sqlite3_data_count(pCsr->pStmt)>(iCol+1) ){

3255 sqlite3_result_value(pCtx, sqlite3_column_value(pCsr->pStmt, iCol+1));

3256 }

3257 }

3258 }

3259

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

3261 return rc;

3262 }

3263

3264 /*

3265 ** This function is the implementation of the xUpdate callback used by

3266 ** FTS3 virtual tables. It is invoked by SQLite each time a row is to be

3267 ** inserted, updated or deleted.

3268 */

3269 static int fts3UpdateMethod(

3270 sqlite3_vtab pVtab, / Virtual table handle */

3271 int nArg, /* Size of argument array */

3272 sqlite3_value *apVal, / Array of arguments */

3273 sqlite_int64 pRowid / OUT: The affected (or effected) rowid */

3274 ){

3275 return sqlite3Fts3UpdateMethod(pVtab, nArg, apVal, pRowid);

3276 }

3277

3278 /*

3279 ** Implementation of xSync() method. Flush the contents of the pending-terms

3280 ** hash-table to the database.

3281 */

3282 static int fts3SyncMethod(sqlite3_vtab *pVtab){

3283

3284 /* Following an incremental-merge operation, assuming that the input

3285 ** segments are not completely consumed (the usual case), they are updated

3286 ** in place to remove the entries that have already been merged. This

3287 ** involves updating the leaf block that contains the smallest unmerged

3288 ** entry and each block (if any) between the leaf and the root node. So

3289 ** if the height of the input segment b-trees is N, and input segments

3290 ** are merged eight at a time, updating the input segments at the end

3291 ** of an incremental-merge requires writing (8*(1+N)) blocks. N is usually

3292 ** small - often between 0 and 2. So the overhead of the incremental

3293 ** merge is somewhere between 8 and 24 blocks. To avoid this overhead

3294 ** dwarfing the actual productive work accomplished, the incremental merge

3295 ** is only attempted if it will write at least 64 leaf blocks. Hence

3296 ** nMinMerge.

3297 **

3298 ** Of course, updating the input segments also involves deleting a bunch

3299 ** of blocks from the segments table. But this is not considered overhead

3300 ** as it would also be required by a crisis-merge that used the same input

3301 ** segments.

3302 */

3303 const u32 nMinMerge = 64; /* Minimum amount of incr-merge work to do */

3304

3305 Fts3Table p = (Fts3Table)pVtab;

3306 int rc = sqlite3Fts3PendingTermsFlush(p);

3307

3308 if( rc==SQLITE_OK

3309 && p->nLeafAdd>(nMinMerge/16)

3310 && p->nAutoincrmerge && p->nAutoincrmerge!=0xff

3311 ){

3312 int mxLevel = 0; /* Maximum relative level value in db */

3313 int A; /* Incr-merge parameter A */

3314

3315 rc = sqlite3Fts3MaxLevel(p, &mxLevel);

3316 assert( rc==SQLITE_OK \|\| mxLevel==0 );

3317 A = p->nLeafAdd * mxLevel;

3318 A += (A/2);

3319 if( A>(int)nMinMerge ) rc = sqlite3Fts3Incrmerge(p, A, p->nAutoincrmerge);

3320 }

3321 sqlite3Fts3SegmentsClose(p);

3322 return rc;

3323 }

3324

3325 /*

3326 ** If it is currently unknown whether or not the FTS table has an %_stat

3327 ** table (if p->bHasStat==2), attempt to determine this (set p->bHasStat

3328 ** to 0 or 1). Return SQLITE_OK if successful, or an SQLite error code

3329 ** if an error occurs.

3330 */

3331 static int fts3SetHasStat(Fts3Table *p){

3332 int rc = SQLITE_OK;

3333 if( p->bHasStat==2 ){

3334 const char *zFmt ="SELECT 1 FROM %Q.sqlite_master WHERE tbl_name='%q_stat'";

3335 char *zSql = sqlite3_mprintf(zFmt, p->zDb, p->zName);

3336 if( zSql ){

3337 sqlite3_stmt *pStmt = 0;

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

3339 if( rc==SQLITE_OK ){

3340 int bHasStat = (sqlite3_step(pStmt)==SQLITE_ROW);

3341 rc = sqlite3_finalize(pStmt);

3342 if( rc==SQLITE_OK ) p->bHasStat = bHasStat;

3343 }

3344 sqlite3_free(zSql);

3345 }else{

3346 rc = SQLITE_NOMEM;

3347 }

3348 }

3349 return rc;

3350 }

3351

3352 /*

3353 ** Implementation of xBegin() method.

3354 */

3355 static int fts3BeginMethod(sqlite3_vtab *pVtab){

3356 Fts3Table p = (Fts3Table)pVtab;

3357 UNUSED_PARAMETER(pVtab);

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

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

3360 assert( p->inTransaction!=1 );

3361 TESTONLY( p->inTransaction = 1 );

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

3363 p->nLeafAdd = 0;

3364 return fts3SetHasStat(p);

3365 }

3366

3367 /*

3368 ** Implementation of xCommit() method. This is a no-op. The contents of

3369 ** the pending-terms hash-table have already been flushed into the database

3370 ** by fts3SyncMethod().

3371 */

3372 static int fts3CommitMethod(sqlite3_vtab *pVtab){

3373 TESTONLY( Fts3Table p = (Fts3Table)pVtab );

3374 UNUSED_PARAMETER(pVtab);

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

3376 assert( p->inTransaction!=0 );

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

3378 TESTONLY( p->inTransaction = 0 );

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

3380 return SQLITE_OK;

3381 }

3382

3383 /*

3384 ** Implementation of xRollback(). Discard the contents of the pending-terms

3385 ** hash-table. Any changes made to the database are reverted by SQLite.

3386 */

3387 static int fts3RollbackMethod(sqlite3_vtab *pVtab){

3388 Fts3Table p = (Fts3Table)pVtab;

3389 sqlite3Fts3PendingTermsClear(p);

3390 assert( p->inTransaction!=0 );

3391 TESTONLY( p->inTransaction = 0 );

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

3393 return SQLITE_OK;

3394 }

3395

3396 /*

3397 ** When called, *ppPoslist must point to the byte immediately following the

3398 ** end of a position-list. i.e. ( (*ppPoslist)[-1]==POS_END ). This function

3399 ** moves *ppPoslist so that it instead points to the first byte of the

3400 ** same position list.

3401 */

3402 static void fts3ReversePoslist(char pStart, char *ppPoslist){

3403 char p = &(ppPoslist)[-2];

3404 char c = 0;

3405

3406 while( p>pStart && (c=*p--)==0 );

3407 while( p>pStart && (*p & 0x80) \| c ){

3408 c = *p--;

3409 }

3410 if( p>pStart ){ p = &p[2]; }

3411 while( *p++&0x80 );

3412 *ppPoslist = p;

3413 }

3414

3415 /*

3416 ** Helper function used by the implementation of the overloaded snippet(),

3417 ** offsets() and optimize() SQL functions.

3418 **

3419 ** If the value passed as the third argument is a blob of size

3420 ** sizeof(Fts3Cursor*), then the blob contents are copied to the

3421 ** output variable *ppCsr and SQLITE_OK is returned. Otherwise, an error

3422 ** message is written to context pContext and SQLITE_ERROR returned. The

3423 ** string passed via zFunc is used as part of the error message.

3424 */

3425 static int fts3FunctionArg(

3426 sqlite3_context pContext, / SQL function call context */

3427 const char zFunc, / Function name */

3428 sqlite3_value pVal, / argv[0] passed to function */

3429 Fts3Cursor *ppCsr / OUT: Store cursor handle here */

3430 ){

3431 Fts3Cursor *pRet;

3432 if( sqlite3_value_type(pVal)!=SQLITE_BLOB

3433 \|\| sqlite3_value_bytes(pVal)!=sizeof(Fts3Cursor *)

3434 ){

3435 char *zErr = sqlite3_mprintf("illegal first argument to %s", zFunc);

3436 sqlite3_result_error(pContext, zErr, -1);

3437 sqlite3_free(zErr);

3438 return SQLITE_ERROR;

3439 }

3440 memcpy(&pRet, sqlite3_value_blob(pVal), sizeof(Fts3Cursor *));

3441 *ppCsr = pRet;

3442 return SQLITE_OK;

3443 }

3444

3445 /*

3446 ** Implementation of the snippet() function for FTS3

3447 */

3448 static void fts3SnippetFunc(

3449 sqlite3_context pContext, / SQLite function call context */

3450 int nVal, /* Size of apVal[] array */

3451 sqlite3_value *apVal / Array of arguments */

3452 ){

3453 Fts3Cursor pCsr; / Cursor handle passed through apVal[0] */

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

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

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

3457 int iCol = -1;

3458 int nToken = 15; /* Default number of tokens in snippet */

3459

3460 /* There must be at least one argument passed to this function (otherwise

3461 ** the non-overloaded version would have been called instead of this one).

3462 */

3463 assert( nVal>=1 );

3464

3465 if( nVal>6 ){

3466 sqlite3_result_error(pContext,

3467 "wrong number of arguments to function snippet()", -1);

3468 return;

3469 }

3470 if( fts3FunctionArg(pContext, "snippet", apVal[0], &pCsr) ) return;

3471

3472 switch( nVal ){

3473 case 6: nToken = sqlite3_value_int(apVal[5]);

3474 case 5: iCol = sqlite3_value_int(apVal[4]);

3475 case 4: zEllipsis = (const char*)sqlite3_value_text(apVal[3]);

3476 case 3: zEnd = (const char*)sqlite3_value_text(apVal[2]);

3477 case 2: zStart = (const char*)sqlite3_value_text(apVal[1]);

3478 }

3479 if( !zEllipsis \|\| !zEnd \|\| !zStart ){

3480 sqlite3_result_error_nomem(pContext);

3481 }else if( SQLITE_OK==fts3CursorSeek(pContext, pCsr) ){

3482 sqlite3Fts3Snippet(pContext, pCsr, zStart, zEnd, zEllipsis, iCol, nToken);

3483 }

3484 }

3485

3486 /*

3487 ** Implementation of the offsets() function for FTS3

3488 */

3489 static void fts3OffsetsFunc(

3490 sqlite3_context pContext, / SQLite function call context */

3491 int nVal, /* Size of argument array */

3492 sqlite3_value *apVal / Array of arguments */

3493 ){

3494 Fts3Cursor pCsr; / Cursor handle passed through apVal[0] */

3495

3496 UNUSED_PARAMETER(nVal);

3497

3498 assert( nVal==1 );

3499 if( fts3FunctionArg(pContext, "offsets", apVal[0], &pCsr) ) return;

3500 assert( pCsr );

3501 if( SQLITE_OK==fts3CursorSeek(pContext, pCsr) ){

3502 sqlite3Fts3Offsets(pContext, pCsr);

3503 }

3504 }

3505

3506 /*

3507 ** Implementation of the special optimize() function for FTS3. This

3508 ** function merges all segments in the database to a single segment.

3509 ** Example usage is:

3510 **

3511 ** SELECT optimize(t) FROM t LIMIT 1;

3512 **

3513 ** where 't' is the name of an FTS3 table.

3514 */

3515 static void fts3OptimizeFunc(

3516 sqlite3_context pContext, / SQLite function call context */

3517 int nVal, /* Size of argument array */

3518 sqlite3_value *apVal / Array of arguments */

3519 ){

3520 int rc; /* Return code */

3521 Fts3Table p; / Virtual table handle */

3522 Fts3Cursor pCursor; / Cursor handle passed through apVal[0] */

3523

3524 UNUSED_PARAMETER(nVal);

3525

3526 assert( nVal==1 );

3527 if( fts3FunctionArg(pContext, "optimize", apVal[0], &pCursor) ) return;

3528 p = (Fts3Table *)pCursor->base.pVtab;

3529 assert( p );

3530

3531 rc = sqlite3Fts3Optimize(p);

3532

3533 switch( rc ){

3534 case SQLITE_OK:

3535 sqlite3_result_text(pContext, "Index optimized", -1, SQLITE_STATIC);

3536 break;

3537 case SQLITE_DONE:

3538 sqlite3_result_text(pContext, "Index already optimal", -1, SQLITE_STATIC);

3539 break;

3540 default:

3541 sqlite3_result_error_code(pContext, rc);

3542 break;

3543 }

3544 }

3545

3546 /*

3547 ** Implementation of the matchinfo() function for FTS3

3548 */

3549 static void fts3MatchinfoFunc(

3550 sqlite3_context pContext, / SQLite function call context */

3551 int nVal, /* Size of argument array */

3552 sqlite3_value *apVal / Array of arguments */

3553 ){

3554 Fts3Cursor pCsr; / Cursor handle passed through apVal[0] */

3555 assert( nVal==1 \|\| nVal==2 );

3556 if( SQLITE_OK==fts3FunctionArg(pContext, "matchinfo", apVal[0], &pCsr) ){

3557 const char *zArg = 0;

3558 if( nVal>1 ){

3559 zArg = (const char *)sqlite3_value_text(apVal[1]);

3560 }

3561 sqlite3Fts3Matchinfo(pContext, pCsr, zArg);

3562 }

3563 }

3564

3565 /*

3566 ** This routine implements the xFindFunction method for the FTS3

3567 ** virtual table.

3568 */

3569 static int fts3FindFunctionMethod(

3570 sqlite3_vtab pVtab, / Virtual table handle */

3571 int nArg, /* Number of SQL function arguments */

3572 const char zName, / Name of SQL function */

3573 void (*pxFunc)(sqlite3_context,int,sqlite3_value*), / OUT: Result */

3574 void *ppArg / Unused */

3575 ){

3576 struct Overloaded {

3577 const char *zName;

3578 void (xFunc)(sqlite3_context,int,sqlite3_value**);

3579 } aOverload[] = {

3580 { "snippet", fts3SnippetFunc },

3581 { "offsets", fts3OffsetsFunc },

3582 { "optimize", fts3OptimizeFunc },

3583 { "matchinfo", fts3MatchinfoFunc },

3584 };

3585 int i; /* Iterator variable */

3586

3587 UNUSED_PARAMETER(pVtab);

3588 UNUSED_PARAMETER(nArg);

3589 UNUSED_PARAMETER(ppArg);

3590

3591 for(i=0; i<SizeofArray(aOverload); i++){

3592 if( strcmp(zName, aOverload[i].zName)==0 ){

3593 *pxFunc = aOverload[i].xFunc;

3594 return 1;

3595 }

3596 }

3597

3598 /* No function of the specified name was found. Return 0. */

3599 return 0;

3600 }

3601

3602 /*

3603 ** Implementation of FTS3 xRename method. Rename an fts3 table.

3604 */

3605 static int fts3RenameMethod(

3606 sqlite3_vtab pVtab, / Virtual table handle */

3607 const char zName / New name of table */

3608 ){

3609 Fts3Table p = (Fts3Table )pVtab;

3610 sqlite3 db = p->db; / Database connection */

3611 int rc; /* Return Code */

3612

3613 /* At this point it must be known if the %_stat table exists or not.

3614 ** So bHasStat may not be 2. */

3615 rc = fts3SetHasStat(p);

3616

3617 /* As it happens, the pending terms table is always empty here. This is

3618 ** because an "ALTER TABLE RENAME TABLE" statement inside a transaction

3619 ** always opens a savepoint transaction. And the xSavepoint() method

3620 ** flushes the pending terms table. But leave the (no-op) call to

3621 ** PendingTermsFlush() in in case that changes.

3622 */

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

3624 if( rc==SQLITE_OK ){

3625 rc = sqlite3Fts3PendingTermsFlush(p);

3626 }

3627

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

3629 fts3DbExec(&rc, db,

3630 "ALTER TABLE %Q.'%q_content' RENAME TO '%q_content';",

3631 p->zDb, p->zName, zName

3632 );

3633 }

3634

3635 if( p->bHasDocsize ){

3636 fts3DbExec(&rc, db,

3637 "ALTER TABLE %Q.'%q_docsize' RENAME TO '%q_docsize';",

3638 p->zDb, p->zName, zName

3639 );

3640 }

3641 if( p->bHasStat ){

3642 fts3DbExec(&rc, db,

3643 "ALTER TABLE %Q.'%q_stat' RENAME TO '%q_stat';",

3644 p->zDb, p->zName, zName

3645 );

3646 }

3647 fts3DbExec(&rc, db,

3648 "ALTER TABLE %Q.'%q_segments' RENAME TO '%q_segments';",

3649 p->zDb, p->zName, zName

3650 );

3651 fts3DbExec(&rc, db,

3652 "ALTER TABLE %Q.'%q_segdir' RENAME TO '%q_segdir';",

3653 p->zDb, p->zName, zName

3654 );

3655 return rc;

3656 }

3657

3658 /*

3659 ** The xSavepoint() method.

3660 **

3661 ** Flush the contents of the pending-terms table to disk.

3662 */

3663 static int fts3SavepointMethod(sqlite3_vtab *pVtab, int iSavepoint){

3664 int rc = SQLITE_OK;

3665 UNUSED_PARAMETER(iSavepoint);

3666 assert( ((Fts3Table *)pVtab)->inTransaction );

3667 assert( ((Fts3Table *)pVtab)->mxSavepoint < iSavepoint );

3668 TESTONLY( ((Fts3Table *)pVtab)->mxSavepoint = iSavepoint );

3669 if( ((Fts3Table *)pVtab)->bIgnoreSavepoint==0 ){

3670 rc = fts3SyncMethod(pVtab);

3671 }

3672 return rc;

3673 }

3674

3675 /*

3676 ** The xRelease() method.

3677 **

3678 ** This is a no-op.

3679 */

3680 static int fts3ReleaseMethod(sqlite3_vtab *pVtab, int iSavepoint){

3681 TESTONLY( Fts3Table p = (Fts3Table)pVtab );

3682 UNUSED_PARAMETER(iSavepoint);

3683 UNUSED_PARAMETER(pVtab);

3684 assert( p->inTransaction );

3685 assert( p->mxSavepoint >= iSavepoint );

3686 TESTONLY( p->mxSavepoint = iSavepoint-1 );

3687 return SQLITE_OK;

3688 }

3689

3690 /*

3691 ** The xRollbackTo() method.

3692 **

3693 ** Discard the contents of the pending terms table.

3694 */

3695 static int fts3RollbackToMethod(sqlite3_vtab *pVtab, int iSavepoint){

3696 Fts3Table p = (Fts3Table)pVtab;

3697 UNUSED_PARAMETER(iSavepoint);

3698 assert( p->inTransaction );

3699 assert( p->mxSavepoint >= iSavepoint );

3700 TESTONLY( p->mxSavepoint = iSavepoint );

3701 sqlite3Fts3PendingTermsClear(p);

3702 return SQLITE_OK;

3703 }

3704

3705 static const sqlite3_module fts3Module = {

3706 /* iVersion */ 2,

3707 /* xCreate */ fts3CreateMethod,

3708 /* xConnect */ fts3ConnectMethod,

3709 /* xBestIndex */ fts3BestIndexMethod,

3710 /* xDisconnect */ fts3DisconnectMethod,

3711 /* xDestroy */ fts3DestroyMethod,

3712 /* xOpen */ fts3OpenMethod,

3713 /* xClose */ fts3CloseMethod,

3714 /* xFilter */ fts3FilterMethod,

3715 /* xNext */ fts3NextMethod,

3716 /* xEof */ fts3EofMethod,

3717 /* xColumn */ fts3ColumnMethod,

3718 /* xRowid */ fts3RowidMethod,

3719 /* xUpdate */ fts3UpdateMethod,

3720 /* xBegin */ fts3BeginMethod,

3721 /* xSync */ fts3SyncMethod,

3722 /* xCommit */ fts3CommitMethod,

3723 /* xRollback */ fts3RollbackMethod,

3724 /* xFindFunction */ fts3FindFunctionMethod,

3725 /* xRename */ fts3RenameMethod,

3726 /* xSavepoint */ fts3SavepointMethod,

3727 /* xRelease */ fts3ReleaseMethod,

3728 /* xRollbackTo */ fts3RollbackToMethod,

3729 };

3730

3731 /*

3732 ** This function is registered as the module destructor (called when an

3733 ** FTS3 enabled database connection is closed). It frees the memory

3734 ** allocated for the tokenizer hash table.

3735 */

3736 static void hashDestroy(void *p){

3737 Fts3Hash pHash = (Fts3Hash )p;

3738 sqlite3Fts3HashClear(pHash);

3739 sqlite3_free(pHash);

3740 }

3741

3742 /*

3743 ** The fts3 built-in tokenizers - "simple", "porter" and "icu"- are

3744 ** implemented in files fts3_tokenizer1.c, fts3_porter.c and fts3_icu.c

3745 ** respectively. The following three forward declarations are for functions

3746 ** declared in these files used to retrieve the respective implementations.

3747 **

3748 ** Calling sqlite3Fts3SimpleTokenizerModule() sets the value pointed

3749 ** to by the argument to point to the "simple" tokenizer implementation.

3750 ** And so on.

3751 */

3752 void sqlite3Fts3SimpleTokenizerModule(sqlite3_tokenizer_module const**ppModule);

3753 void sqlite3Fts3PorterTokenizerModule(sqlite3_tokenizer_module const**ppModule);

3754 #ifndef SQLITE_DISABLE_FTS3_UNICODE

3755 void sqlite3Fts3UnicodeTokenizer(sqlite3_tokenizer_module const**ppModule);

3756 #endif

3757 #ifdef SQLITE_ENABLE_ICU

3758 void sqlite3Fts3IcuTokenizerModule(sqlite3_tokenizer_module const**ppModule);

3759 #endif

3760

3761 /*

3762 ** Initialize the fts3 extension. If this extension is built as part

3763 ** of the sqlite library, then this function is called directly by

3764 ** SQLite. If fts3 is built as a dynamically loadable extension, this

3765 ** function is called by the sqlite3_extension_init() entry point.

3766 */

3767 int sqlite3Fts3Init(sqlite3 *db){

3768 int rc = SQLITE_OK;

3769 Fts3Hash *pHash = 0;

3770 const sqlite3_tokenizer_module *pSimple = 0;

3771 const sqlite3_tokenizer_module *pPorter = 0;

3772 #ifndef SQLITE_DISABLE_FTS3_UNICODE

3773 const sqlite3_tokenizer_module *pUnicode = 0;

3774 #endif

3775

3776 #ifdef SQLITE_ENABLE_ICU

3777 const sqlite3_tokenizer_module *pIcu = 0;

3778 sqlite3Fts3IcuTokenizerModule(&pIcu);

3779 #endif

3780

3781 #ifndef SQLITE_DISABLE_FTS3_UNICODE

3782 sqlite3Fts3UnicodeTokenizer(&pUnicode);

3783 #endif

3784

3785 #ifdef SQLITE_TEST

3786 rc = sqlite3Fts3InitTerm(db);

3787 if( rc!=SQLITE_OK ) return rc;

3788 #endif

3789

3790 rc = sqlite3Fts3InitAux(db);

3791 if( rc!=SQLITE_OK ) return rc;

3792

3793 sqlite3Fts3SimpleTokenizerModule(&pSimple);

3794 sqlite3Fts3PorterTokenizerModule(&pPorter);

3795

3796 /* Allocate and initialize the hash-table used to store tokenizers. */

3797 pHash = sqlite3_malloc(sizeof(Fts3Hash));

3798 if( !pHash ){

3799 rc = SQLITE_NOMEM;

3800 }else{

3801 sqlite3Fts3HashInit(pHash, FTS3_HASH_STRING, 1);

3802 }

3803

3804 /* Load the built-in tokenizers into the hash table */

3805 if( rc==SQLITE_OK ){

3806 if( sqlite3Fts3HashInsert(pHash, "simple", 7, (void *)pSimple)

3807 \|\| sqlite3Fts3HashInsert(pHash, "porter", 7, (void *)pPorter)

3808

3809 #ifndef SQLITE_DISABLE_FTS3_UNICODE

3810 \|\| sqlite3Fts3HashInsert(pHash, "unicode61", 10, (void *)pUnicode)

3811 #endif

3812 #ifdef SQLITE_ENABLE_ICU

3813 \|\| (pIcu && sqlite3Fts3HashInsert(pHash, "icu", 4, (void *)pIcu))

3814 #endif

3815 ){

3816 rc = SQLITE_NOMEM;

3817 }

3818 }

3819

3820 #ifdef SQLITE_TEST

3821 if( rc==SQLITE_OK ){

3822 rc = sqlite3Fts3ExprInitTestInterface(db);

3823 }

3824 #endif

3825

3826 /* Create the virtual table wrapper around the hash-table and overload

3827 ** the two scalar functions. If this is successful, register the

3828 ** module with sqlite.

3829 */

3830 if( SQLITE_OK==rc

3831 && SQLITE_OK==(rc = sqlite3Fts3InitHashTable(db, pHash, "fts3_tokenizer"))

3832 && SQLITE_OK==(rc = sqlite3_overload_function(db, "snippet", -1))

3833 && SQLITE_OK==(rc = sqlite3_overload_function(db, "offsets", 1))

3834 && SQLITE_OK==(rc = sqlite3_overload_function(db, "matchinfo", 1))

3835 && SQLITE_OK==(rc = sqlite3_overload_function(db, "matchinfo", 2))

3836 && SQLITE_OK==(rc = sqlite3_overload_function(db, "optimize", 1))

3837 ){

3838 rc = sqlite3_create_module_v2(

3839 db, "fts3", &fts3Module, (void *)pHash, hashDestroy

3840 );

3841 if( rc==SQLITE_OK ){

3842 rc = sqlite3_create_module_v2(

3843 db, "fts4", &fts3Module, (void *)pHash, 0

3844 );

3845 }

3846 if( rc==SQLITE_OK ){

3847 rc = sqlite3Fts3InitTok(db, (void *)pHash);

3848 }

3849 return rc;

3850 }

3851

3852

3853 /* An error has occurred. Delete the hash table and return the error code. */

3854 assert( rc!=SQLITE_OK );

3855 if( pHash ){

3856 sqlite3Fts3HashClear(pHash);

3857 sqlite3_free(pHash);

3858 }

3859 return rc;

3860 }

3861

3862 /*

3863 ** Allocate an Fts3MultiSegReader for each token in the expression headed

3864 ** by pExpr.

3865 **

3866 ** An Fts3SegReader object is a cursor that can seek or scan a range of

3867 ** entries within a single segment b-tree. An Fts3MultiSegReader uses multiple

3868 ** Fts3SegReader objects internally to provide an interface to seek or scan

3869 ** within the union of all segments of a b-tree. Hence the name.

3870 **

3871 ** If the allocated Fts3MultiSegReader just seeks to a single entry in a

3872 ** segment b-tree (if the term is not a prefix or it is a prefix for which

3873 ** there exists prefix b-tree of the right length) then it may be traversed

3874 ** and merged incrementally. Otherwise, it has to be merged into an in-memory

3875 ** doclist and then traversed.

3876 */

3877 static void fts3EvalAllocateReaders(

3878 Fts3Cursor pCsr, / FTS cursor handle */

3879 Fts3Expr pExpr, / Allocate readers for this expression */

3880 int pnToken, / OUT: Total number of tokens in phrase. */

3881 int pnOr, / OUT: Total number of OR nodes in expr. */

3882 int pRc / IN/OUT: Error code */

3883 ){

3884 if( pExpr && SQLITE_OK==*pRc ){

3885 if( pExpr->eType==FTSQUERY_PHRASE ){

3886 int i;

3887 int nToken = pExpr->pPhrase->nToken;

3888 *pnToken += nToken;

3889 for(i=0; i<nToken; i++){

3890 Fts3PhraseToken *pToken = &pExpr->pPhrase->aToken[i];

3891 int rc = fts3TermSegReaderCursor(pCsr,

3892 pToken->z, pToken->n, pToken->isPrefix, &pToken->pSegcsr

3893 );

3894 if( rc!=SQLITE_OK ){

3895 *pRc = rc;

3896 return;

3897 }

3898 }

3899 assert( pExpr->pPhrase->iDoclistToken==0 );

3900 pExpr->pPhrase->iDoclistToken = -1;

3901 }else{

3902 *pnOr += (pExpr->eType==FTSQUERY_OR);

3903 fts3EvalAllocateReaders(pCsr, pExpr->pLeft, pnToken, pnOr, pRc);

3904 fts3EvalAllocateReaders(pCsr, pExpr->pRight, pnToken, pnOr, pRc);

3905 }

3906 }

3907 }

3908

3909 /*

3910 ** Arguments pList/nList contain the doclist for token iToken of phrase p.

3911 ** It is merged into the main doclist stored in p->doclist.aAll/nAll.

3912 **

3913 ** This function assumes that pList points to a buffer allocated using

3914 ** sqlite3_malloc(). This function takes responsibility for eventually

3915 ** freeing the buffer.

3916 */

3917 static void fts3EvalPhraseMergeToken(

3918 Fts3Table pTab, / FTS Table pointer */

3919 Fts3Phrase p, / Phrase to merge pList/nList into */

3920 int iToken, /* Token pList/nList corresponds to */

3921 char pList, / Pointer to doclist */

3922 int nList /* Number of bytes in pList */

3923 ){

3924 assert( iToken!=p->iDoclistToken );

3925

3926 if( pList==0 ){

3927 sqlite3_free(p->doclist.aAll);

3928 p->doclist.aAll = 0;

3929 p->doclist.nAll = 0;

3930 }

3931

3932 else if( p->iDoclistToken<0 ){

3933 p->doclist.aAll = pList;

3934 p->doclist.nAll = nList;

3935 }

3936

3937 else if( p->doclist.aAll==0 ){

3938 sqlite3_free(pList);

3939 }

3940

3941 else {

3942 char *pLeft;

3943 char *pRight;

3944 int nLeft;

3945 int nRight;

3946 int nDiff;

3947

3948 if( p->iDoclistToken<iToken ){

3949 pLeft = p->doclist.aAll;

3950 nLeft = p->doclist.nAll;

3951 pRight = pList;

3952 nRight = nList;

3953 nDiff = iToken - p->iDoclistToken;

3954 }else{

3955 pRight = p->doclist.aAll;

3956 nRight = p->doclist.nAll;

3957 pLeft = pList;

3958 nLeft = nList;

3959 nDiff = p->iDoclistToken - iToken;

3960 }

3961

3962 fts3DoclistPhraseMerge(pTab->bDescIdx, nDiff, pLeft, nLeft, pRight,&nRight);

3963 sqlite3_free(pLeft);

3964 p->doclist.aAll = pRight;

3965 p->doclist.nAll = nRight;

3966 }

3967

3968 if( iToken>p->iDoclistToken ) p->iDoclistToken = iToken;

3969 }

3970

3971 /*

3972 ** Load the doclist for phrase p into p->doclist.aAll/nAll. The loaded doclist

3973 ** does not take deferred tokens into account.

3974 **

3975 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.

3976 */

3977 static int fts3EvalPhraseLoad(

3978 Fts3Cursor pCsr, / FTS Cursor handle */

3979 Fts3Phrase p / Phrase object */

3980 ){

3981 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

3982 int iToken;

3983 int rc = SQLITE_OK;

3984

3985 for(iToken=0; rc==SQLITE_OK && iToken<p->nToken; iToken++){

3986 Fts3PhraseToken *pToken = &p->aToken[iToken];

3987 assert( pToken->pDeferred==0 \|\| pToken->pSegcsr==0 );

3988

3989 if( pToken->pSegcsr ){

3990 int nThis = 0;

3991 char *pThis = 0;

3992 rc = fts3TermSelect(pTab, pToken, p->iColumn, &nThis, &pThis);

3993 if( rc==SQLITE_OK ){

3994 fts3EvalPhraseMergeToken(pTab, p, iToken, pThis, nThis);

3995 }

3996 }

3997 assert( pToken->pSegcsr==0 );

3998 }

3999

4000 return rc;

4001 }

4002

4003 /*

4004 ** This function is called on each phrase after the position lists for

4005 ** any deferred tokens have been loaded into memory. It updates the phrases

4006 ** current position list to include only those positions that are really

4007 ** instances of the phrase (after considering deferred tokens). If this

4008 ** means that the phrase does not appear in the current row, doclist.pList

4009 ** and doclist.nList are both zeroed.

4010 **

4011 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.

4012 */

4013 static int fts3EvalDeferredPhrase(Fts3Cursor pCsr, Fts3Phrase pPhrase){

4014 int iToken; /* Used to iterate through phrase tokens */

4015 char aPoslist = 0; / Position list for deferred tokens */

4016 int nPoslist = 0; /* Number of bytes in aPoslist */

4017 int iPrev = -1; /* Token number of previous deferred token */

4018

4019 assert( pPhrase->doclist.bFreeList==0 );

4020

4021 for(iToken=0; iToken<pPhrase->nToken; iToken++){

4022 Fts3PhraseToken *pToken = &pPhrase->aToken[iToken];

4023 Fts3DeferredToken *pDeferred = pToken->pDeferred;

4024

4025 if( pDeferred ){

4026 char *pList;

4027 int nList;

4028 int rc = sqlite3Fts3DeferredTokenList(pDeferred, &pList, &nList);

4029 if( rc!=SQLITE_OK ) return rc;

4030

4031 if( pList==0 ){

4032 sqlite3_free(aPoslist);

4033 pPhrase->doclist.pList = 0;

4034 pPhrase->doclist.nList = 0;

4035 return SQLITE_OK;

4036

4037 }else if( aPoslist==0 ){

4038 aPoslist = pList;

4039 nPoslist = nList;

4040

4041 }else{

4042 char *aOut = pList;

4043 char *p1 = aPoslist;

4044 char *p2 = aOut;

4045

4046 assert( iPrev>=0 );

4047 fts3PoslistPhraseMerge(&aOut, iToken-iPrev, 0, 1, &p1, &p2);

4048 sqlite3_free(aPoslist);

4049 aPoslist = pList;

4050 nPoslist = (int)(aOut - aPoslist);

4051 if( nPoslist==0 ){

4052 sqlite3_free(aPoslist);

4053 pPhrase->doclist.pList = 0;

4054 pPhrase->doclist.nList = 0;

4055 return SQLITE_OK;

4056 }

4057 }

4058 iPrev = iToken;

4059 }

4060 }

4061

4062 if( iPrev>=0 ){

4063 int nMaxUndeferred = pPhrase->iDoclistToken;

4064 if( nMaxUndeferred<0 ){

4065 pPhrase->doclist.pList = aPoslist;

4066 pPhrase->doclist.nList = nPoslist;

4067 pPhrase->doclist.iDocid = pCsr->iPrevId;

4068 pPhrase->doclist.bFreeList = 1;

4069 }else{

4070 int nDistance;

4071 char *p1;

4072 char *p2;

4073 char *aOut;

4074

4075 if( nMaxUndeferred>iPrev ){

4076 p1 = aPoslist;

4077 p2 = pPhrase->doclist.pList;

4078 nDistance = nMaxUndeferred - iPrev;

4079 }else{

4080 p1 = pPhrase->doclist.pList;

4081 p2 = aPoslist;

4082 nDistance = iPrev - nMaxUndeferred;

4083 }

4084

4085 aOut = (char *)sqlite3_malloc(nPoslist+8);

4086 if( !aOut ){

4087 sqlite3_free(aPoslist);

4088 return SQLITE_NOMEM;

4089 }

4090

4091 pPhrase->doclist.pList = aOut;

4092 if( fts3PoslistPhraseMerge(&aOut, nDistance, 0, 1, &p1, &p2) ){

4093 pPhrase->doclist.bFreeList = 1;

4094 pPhrase->doclist.nList = (int)(aOut - pPhrase->doclist.pList);

4095 }else{

4096 sqlite3_free(aOut);

4097 pPhrase->doclist.pList = 0;

4098 pPhrase->doclist.nList = 0;

4099 }

4100 sqlite3_free(aPoslist);

4101 }

4102 }

4103

4104 return SQLITE_OK;

4105 }

4106

4107 /*

4108 ** Maximum number of tokens a phrase may have to be considered for the

4109 ** incremental doclists strategy.

4110 */

4111 #define MAX_INCR_PHRASE_TOKENS 4

4112

4113 /*

4114 ** This function is called for each Fts3Phrase in a full-text query

4115 ** expression to initialize the mechanism for returning rows. Once this

4116 ** function has been called successfully on an Fts3Phrase, it may be

4117 ** used with fts3EvalPhraseNext() to iterate through the matching docids.

4118 **

4119 ** If parameter bOptOk is true, then the phrase may (or may not) use the

4120 ** incremental loading strategy. Otherwise, the entire doclist is loaded into

4121 ** memory within this call.

4122 **

4123 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.

4124 */

4125 static int fts3EvalPhraseStart(Fts3Cursor pCsr, int bOptOk, Fts3Phrase p){

4126 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

4127 int rc = SQLITE_OK; /* Error code */

4128 int i;

4129

4130 /* Determine if doclists may be loaded from disk incrementally. This is

4131 ** possible if the bOptOk argument is true, the FTS doclists will be

4132 ** scanned in forward order, and the phrase consists of

4133 ** MAX_INCR_PHRASE_TOKENS or fewer tokens, none of which are are "^first"

4134 ** tokens or prefix tokens that cannot use a prefix-index. */

4135 int bHaveIncr = 0;

4136 int bIncrOk = (bOptOk

4137 && pCsr->bDesc==pTab->bDescIdx

4138 && p->nToken<=MAX_INCR_PHRASE_TOKENS && p->nToken>0

4139 && p->nToken<=MAX_INCR_PHRASE_TOKENS && p->nToken>0

4140 #ifdef SQLITE_TEST

4141 && pTab->bNoIncrDoclist==0

4142 #endif

4143 );

4144 for(i=0; bIncrOk==1 && i<p->nToken; i++){

4145 Fts3PhraseToken *pToken = &p->aToken[i];

4146 if( pToken->bFirst \|\| (pToken->pSegcsr!=0 && !pToken->pSegcsr->bLookup) ){

4147 bIncrOk = 0;

4148 }

4149 if( pToken->pSegcsr ) bHaveIncr = 1;

4150 }

4151

4152 if( bIncrOk && bHaveIncr ){

4153 /* Use the incremental approach. */

4154 int iCol = (p->iColumn >= pTab->nColumn ? -1 : p->iColumn);

4155 for(i=0; rc==SQLITE_OK && i<p->nToken; i++){

4156 Fts3PhraseToken *pToken = &p->aToken[i];

4157 Fts3MultiSegReader *pSegcsr = pToken->pSegcsr;

4158 if( pSegcsr ){

4159 rc = sqlite3Fts3MsrIncrStart(pTab, pSegcsr, iCol, pToken->z, pToken->n);

4160 }

4161 }

4162 p->bIncr = 1;

4163 }else{

4164 /* Load the full doclist for the phrase into memory. */

4165 rc = fts3EvalPhraseLoad(pCsr, p);

4166 p->bIncr = 0;

4167 }

4168

4169 assert( rc!=SQLITE_OK \|\| p->nToken<1 \|\| p->aToken[0].pSegcsr==0 \|\| p->bIncr );

4170 return rc;

4171 }

4172

4173 /*

4174 ** This function is used to iterate backwards (from the end to start)

4175 ** through doclists. It is used by this module to iterate through phrase

4176 ** doclists in reverse and by the fts3_write.c module to iterate through

4177 ** pending-terms lists when writing to databases with "order=desc".

4178 **

4179 ** The doclist may be sorted in ascending (parameter bDescIdx==0) or

4180 ** descending (parameter bDescIdx==1) order of docid. Regardless, this

4181 ** function iterates from the end of the doclist to the beginning.

4182 */

4183 void sqlite3Fts3DoclistPrev(

4184 int bDescIdx, /* True if the doclist is desc */

4185 char aDoclist, / Pointer to entire doclist */

4186 int nDoclist, /* Length of aDoclist in bytes */

4187 char *ppIter, / IN/OUT: Iterator pointer */

4188 sqlite3_int64 piDocid, / IN/OUT: Docid pointer */

4189 int pnList, / OUT: List length pointer */

4190 u8 pbEof / OUT: End-of-file flag */

4191 ){

4192 char p = ppIter;

4193

4194 assert( nDoclist>0 );

4195 assert( *pbEof==0 );

4196 assert( p \|\| *piDocid==0 );

4197 assert( !p \|\| (p>aDoclist && p<&aDoclist[nDoclist]) );

4198

4199 if( p==0 ){

4200 sqlite3_int64 iDocid = 0;

4201 char *pNext = 0;

4202 char *pDocid = aDoclist;

4203 char *pEnd = &aDoclist[nDoclist];

4204 int iMul = 1;

4205

4206 while( pDocid<pEnd ){

4207 sqlite3_int64 iDelta;

4208 pDocid += sqlite3Fts3GetVarint(pDocid, &iDelta);

4209 iDocid += (iMul * iDelta);

4210 pNext = pDocid;

4211 fts3PoslistCopy(0, &pDocid);

4212 while( pDocid<pEnd && *pDocid==0 ) pDocid++;

4213 iMul = (bDescIdx ? -1 : 1);

4214 }

4215

4216 *pnList = (int)(pEnd - pNext);

4217 *ppIter = pNext;

4218 *piDocid = iDocid;

4219 }else{

4220 int iMul = (bDescIdx ? -1 : 1);

4221 sqlite3_int64 iDelta;

4222 fts3GetReverseVarint(&p, aDoclist, &iDelta);

4223 piDocid -= (iMul iDelta);

4224

4225 if( p==aDoclist ){

4226 *pbEof = 1;

4227 }else{

4228 char *pSave = p;

4229 fts3ReversePoslist(aDoclist, &p);

4230 *pnList = (int)(pSave - p);

4231 }

4232 *ppIter = p;

4233 }

4234 }

4235

4236 /*

4237 ** Iterate forwards through a doclist.

4238 */

4239 void sqlite3Fts3DoclistNext(

4240 int bDescIdx, /* True if the doclist is desc */

4241 char aDoclist, / Pointer to entire doclist */

4242 int nDoclist, /* Length of aDoclist in bytes */

4243 char *ppIter, / IN/OUT: Iterator pointer */

4244 sqlite3_int64 piDocid, / IN/OUT: Docid pointer */

4245 u8 pbEof / OUT: End-of-file flag */

4246 ){

4247 char p = ppIter;

4248

4249 assert( nDoclist>0 );

4250 assert( *pbEof==0 );

4251 assert( p \|\| *piDocid==0 );

4252 assert( !p \|\| (p>=aDoclist && p<=&aDoclist[nDoclist]) );

4253

4254 if( p==0 ){

4255 p = aDoclist;

4256 p += sqlite3Fts3GetVarint(p, piDocid);

4257 }else{

4258 fts3PoslistCopy(0, &p);

4259 if( p>=&aDoclist[nDoclist] ){

4260 *pbEof = 1;

4261 }else{

4262 sqlite3_int64 iVar;

4263 p += sqlite3Fts3GetVarint(p, &iVar);

4264 piDocid += ((bDescIdx ? -1 : 1) iVar);

4265 }

4266 }

4267

4268 *ppIter = p;

4269 }

4270

4271 /*

4272 ** Advance the iterator pDL to the next entry in pDL->aAll/nAll. Set *pbEof

4273 ** to true if EOF is reached.

4274 */

4275 static void fts3EvalDlPhraseNext(

4276 Fts3Table *pTab,

4277 Fts3Doclist *pDL,

4278 u8 *pbEof

4279 ){

4280 char pIter; / Used to iterate through aAll */

4281 char pEnd = &pDL->aAll[pDL->nAll]; / 1 byte past end of aAll */

4282

4283 if( pDL->pNextDocid ){

4284 pIter = pDL->pNextDocid;

4285 }else{

4286 pIter = pDL->aAll;

4287 }

4288

4289 if( pIter>=pEnd ){

4290 /* We have already reached the end of this doclist. EOF. */

4291 *pbEof = 1;

4292 }else{

4293 sqlite3_int64 iDelta;

4294 pIter += sqlite3Fts3GetVarint(pIter, &iDelta);

4295 if( pTab->bDescIdx==0 \|\| pDL->pNextDocid==0 ){

4296 pDL->iDocid += iDelta;

4297 }else{

4298 pDL->iDocid -= iDelta;

4299 }

4300 pDL->pList = pIter;

4301 fts3PoslistCopy(0, &pIter);

4302 pDL->nList = (int)(pIter - pDL->pList);

4303

4304 /* pIter now points just past the 0x00 that terminates the position-

4305 ** list for document pDL->iDocid. However, if this position-list was

4306 ** edited in place by fts3EvalNearTrim(), then pIter may not actually

4307 ** point to the start of the next docid value. The following line deals

4308 ** with this case by advancing pIter past the zero-padding added by

4309 ** fts3EvalNearTrim(). */

4310 while( pIter<pEnd && *pIter==0 ) pIter++;

4311

4312 pDL->pNextDocid = pIter;

4313 assert( pIter>=&pDL->aAll[pDL->nAll] \|\| *pIter );

4314 *pbEof = 0;

4315 }

4316 }

4317

4318 /*

4319 ** Helper type used by fts3EvalIncrPhraseNext() and incrPhraseTokenNext().

4320 */

4321 typedef struct TokenDoclist TokenDoclist;

4322 struct TokenDoclist {

4323 int bIgnore;

4324 sqlite3_int64 iDocid;

4325 char *pList;

4326 int nList;

4327 };

4328

4329 /*

4330 ** Token pToken is an incrementally loaded token that is part of a

4331 ** multi-token phrase. Advance it to the next matching document in the

4332 ** database and populate output variable *p with the details of the new

4333 ** entry. Or, if the iterator has reached EOF, set *pbEof to true.

4334 **

4335 ** If an error occurs, return an SQLite error code. Otherwise, return

4336 ** SQLITE_OK.

4337 */

4338 static int incrPhraseTokenNext(

4339 Fts3Table pTab, / Virtual table handle */

4340 Fts3Phrase pPhrase, / Phrase to advance token of */

4341 int iToken, /* Specific token to advance */

4342 TokenDoclist p, / OUT: Docid and doclist for new entry */

4343 u8 pbEof / OUT: True if iterator is at EOF */

4344 ){

4345 int rc = SQLITE_OK;

4346

4347 if( pPhrase->iDoclistToken==iToken ){

4348 assert( p->bIgnore==0 );

4349 assert( pPhrase->aToken[iToken].pSegcsr==0 );

4350 fts3EvalDlPhraseNext(pTab, &pPhrase->doclist, pbEof);

4351 p->pList = pPhrase->doclist.pList;

4352 p->nList = pPhrase->doclist.nList;

4353 p->iDocid = pPhrase->doclist.iDocid;

4354 }else{

4355 Fts3PhraseToken *pToken = &pPhrase->aToken[iToken];

4356 assert( pToken->pDeferred==0 );

4357 assert( pToken->pSegcsr \|\| pPhrase->iDoclistToken>=0 );

4358 if( pToken->pSegcsr ){

4359 assert( p->bIgnore==0 );

4360 rc = sqlite3Fts3MsrIncrNext(

4361 pTab, pToken->pSegcsr, &p->iDocid, &p->pList, &p->nList

4362 );

4363 if( p->pList==0 ) *pbEof = 1;

4364 }else{

4365 p->bIgnore = 1;

4366 }

4367 }

4368

4369 return rc;

4370 }

4371

4372

4373 /*

4374 ** The phrase iterator passed as the second argument:

4375 **

4376 ** * features at least one token that uses an incremental doclist, and

4377 **

4378 ** * does not contain any deferred tokens.

4379 **

4380 ** Advance it to the next matching documnent in the database and populate

4381 ** the Fts3Doclist.pList and nList fields.

4382 **

4383 ** If there is no "next" entry and no error occurs, then *pbEof is set to

4384 ** 1 before returning. Otherwise, if no error occurs and the iterator is

4385 ** successfully advanced, *pbEof is set to 0.

4386 **

4387 ** If an error occurs, return an SQLite error code. Otherwise, return

4388 ** SQLITE_OK.

4389 */

4390 static int fts3EvalIncrPhraseNext(

4391 Fts3Cursor pCsr, / FTS Cursor handle */

4392 Fts3Phrase p, / Phrase object to advance to next docid */

4393 u8 pbEof / OUT: Set to 1 if EOF */

4394 ){

4395 int rc = SQLITE_OK;

4396 Fts3Doclist *pDL = &p->doclist;

4397 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

4398 u8 bEof = 0;

4399

4400 /* This is only called if it is guaranteed that the phrase has at least

4401 ** one incremental token. In which case the bIncr flag is set. */

4402 assert( p->bIncr==1 );

4403

4404 if( p->nToken==1 && p->bIncr ){

4405 rc = sqlite3Fts3MsrIncrNext(pTab, p->aToken[0].pSegcsr,

4406 &pDL->iDocid, &pDL->pList, &pDL->nList

4407 );

4408 if( pDL->pList==0 ) bEof = 1;

4409 }else{

4410 int bDescDoclist = pCsr->bDesc;

4411 struct TokenDoclist a[MAX_INCR_PHRASE_TOKENS];

4412

4413 memset(a, 0, sizeof(a));

4414 assert( p->nToken<=MAX_INCR_PHRASE_TOKENS );

4415 assert( p->iDoclistToken<MAX_INCR_PHRASE_TOKENS );

4416

4417 while( bEof==0 ){

4418 int bMaxSet = 0;

4419 sqlite3_int64 iMax = 0; /* Largest docid for all iterators */

4420 int i; /* Used to iterate through tokens */

4421

4422 /* Advance the iterator for each token in the phrase once. */

4423 for(i=0; rc==SQLITE_OK && i<p->nToken && bEof==0; i++){

4424 rc = incrPhraseTokenNext(pTab, p, i, &a[i], &bEof);

4425 if( a[i].bIgnore==0 && (bMaxSet==0 \|\| DOCID_CMP(iMax, a[i].iDocid)<0) ){

4426 iMax = a[i].iDocid;

4427 bMaxSet = 1;

4428 }

4429 }

4430 assert( rc!=SQLITE_OK \|\| (p->nToken>=1 && a[p->nToken-1].bIgnore==0) );

4431 assert( rc!=SQLITE_OK \|\| bMaxSet );

4432

4433 /* Keep advancing iterators until they all point to the same document */

4434 for(i=0; i<p->nToken; i++){

4435 while( rc==SQLITE_OK && bEof==0

4436 && a[i].bIgnore==0 && DOCID_CMP(a[i].iDocid, iMax)<0

4437 ){

4438 rc = incrPhraseTokenNext(pTab, p, i, &a[i], &bEof);

4439 if( DOCID_CMP(a[i].iDocid, iMax)>0 ){

4440 iMax = a[i].iDocid;

4441 i = 0;

4442 }

4443 }

4444 }

4445

4446 /* Check if the current entries really are a phrase match */

4447 if( bEof==0 ){

4448 int nList = 0;

4449 int nByte = a[p->nToken-1].nList;

4450 char *aDoclist = sqlite3_malloc(nByte+1);

4451 if( !aDoclist ) return SQLITE_NOMEM;

4452 memcpy(aDoclist, a[p->nToken-1].pList, nByte+1);

4453

4454 for(i=0; i<(p->nToken-1); i++){

4455 if( a[i].bIgnore==0 ){

4456 char *pL = a[i].pList;

4457 char *pR = aDoclist;

4458 char *pOut = aDoclist;

4459 int nDist = p->nToken-1-i;

4460 int res = fts3PoslistPhraseMerge(&pOut, nDist, 0, 1, &pL, &pR);

4461 if( res==0 ) break;

4462 nList = (int)(pOut - aDoclist);

4463 }

4464 }

4465 if( i==(p->nToken-1) ){

4466 pDL->iDocid = iMax;

4467 pDL->pList = aDoclist;

4468 pDL->nList = nList;

4469 pDL->bFreeList = 1;

4470 break;

4471 }

4472 sqlite3_free(aDoclist);

4473 }

4474 }

4475 }

4476

4477 *pbEof = bEof;

4478 return rc;

4479 }

4480

4481 /*

4482 ** Attempt to move the phrase iterator to point to the next matching docid.

4483 ** If an error occurs, return an SQLite error code. Otherwise, return

4484 ** SQLITE_OK.

4485 **

4486 ** If there is no "next" entry and no error occurs, then *pbEof is set to

4487 ** 1 before returning. Otherwise, if no error occurs and the iterator is

4488 ** successfully advanced, *pbEof is set to 0.

4489 */

4490 static int fts3EvalPhraseNext(

4491 Fts3Cursor pCsr, / FTS Cursor handle */

4492 Fts3Phrase p, / Phrase object to advance to next docid */

4493 u8 pbEof / OUT: Set to 1 if EOF */

4494 ){

4495 int rc = SQLITE_OK;

4496 Fts3Doclist *pDL = &p->doclist;

4497 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

4498

4499 if( p->bIncr ){

4500 rc = fts3EvalIncrPhraseNext(pCsr, p, pbEof);

4501 }else if( pCsr->bDesc!=pTab->bDescIdx && pDL->nAll ){

4502 sqlite3Fts3DoclistPrev(pTab->bDescIdx, pDL->aAll, pDL->nAll,

4503 &pDL->pNextDocid, &pDL->iDocid, &pDL->nList, pbEof

4504 );

4505 pDL->pList = pDL->pNextDocid;

4506 }else{

4507 fts3EvalDlPhraseNext(pTab, pDL, pbEof);

4508 }

4509

4510 return rc;

4511 }

4512

4513 /*

4514 **

4515 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.

4516 ** Otherwise, fts3EvalPhraseStart() is called on all phrases within the

4517 ** expression. Also the Fts3Expr.bDeferred variable is set to true for any

4518 ** expressions for which all descendent tokens are deferred.

4519 **

4520 ** If parameter bOptOk is zero, then it is guaranteed that the

4521 ** Fts3Phrase.doclist.aAll/nAll variables contain the entire doclist for

4522 ** each phrase in the expression (subject to deferred token processing).

4523 ** Or, if bOptOk is non-zero, then one or more tokens within the expression

4524 ** may be loaded incrementally, meaning doclist.aAll/nAll is not available.

4525 **

4526 ** If an error occurs within this function, *pRc is set to an SQLite error

4527 ** code before returning.

4528 */

4529 static void fts3EvalStartReaders(

4530 Fts3Cursor pCsr, / FTS Cursor handle */

4531 Fts3Expr pExpr, / Expression to initialize phrases in */

4532 int pRc / IN/OUT: Error code */

4533 ){

4534 if( pExpr && SQLITE_OK==*pRc ){

4535 if( pExpr->eType==FTSQUERY_PHRASE ){

4536 int i;

4537 int nToken = pExpr->pPhrase->nToken;

4538 for(i=0; i<nToken; i++){

4539 if( pExpr->pPhrase->aToken[i].pDeferred==0 ) break;

4540 }

4541 pExpr->bDeferred = (i==nToken);

4542 *pRc = fts3EvalPhraseStart(pCsr, 1, pExpr->pPhrase);

4543 }else{

4544 fts3EvalStartReaders(pCsr, pExpr->pLeft, pRc);

4545 fts3EvalStartReaders(pCsr, pExpr->pRight, pRc);

4546 pExpr->bDeferred = (pExpr->pLeft->bDeferred && pExpr->pRight->bDeferred);

4547 }

4548 }

4549 }

4550

4551 /*

4552 ** An array of the following structures is assembled as part of the process

4553 ** of selecting tokens to defer before the query starts executing (as part

4554 ** of the xFilter() method). There is one element in the array for each

4555 ** token in the FTS expression.

4556 **

4557 ** Tokens are divided into AND/NEAR clusters. All tokens in a cluster belong

4558 ** to phrases that are connected only by AND and NEAR operators (not OR or

4559 ** NOT). When determining tokens to defer, each AND/NEAR cluster is considered

4560 ** separately. The root of a tokens AND/NEAR cluster is stored in

4561 ** Fts3TokenAndCost.pRoot.

4562 */

4563 typedef struct Fts3TokenAndCost Fts3TokenAndCost;

4564 struct Fts3TokenAndCost {

4565 Fts3Phrase pPhrase; / The phrase the token belongs to */

4566 int iToken; /* Position of token in phrase */

4567 Fts3PhraseToken pToken; / The token itself */

4568 Fts3Expr pRoot; / Root of NEAR/AND cluster */

4569 int nOvfl; /* Number of overflow pages to load doclist */

4570 int iCol; /* The column the token must match */

4571 };

4572

4573 /*

4574 ** This function is used to populate an allocated Fts3TokenAndCost array.

4575 **

4576 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.

4577 ** Otherwise, if an error occurs during execution, *pRc is set to an

4578 ** SQLite error code.

4579 */

4580 static void fts3EvalTokenCosts(

4581 Fts3Cursor pCsr, / FTS Cursor handle */

4582 Fts3Expr pRoot, / Root of current AND/NEAR cluster */

4583 Fts3Expr pExpr, / Expression to consider */

4584 Fts3TokenAndCost *ppTC, / Write new entries to (ppTC)++ */

4585 Fts3Expr **ppOr, / Write new OR root to (ppOr)++ */

4586 int pRc / IN/OUT: Error code */

4587 ){

4588 if( *pRc==SQLITE_OK ){

4589 if( pExpr->eType==FTSQUERY_PHRASE ){

4590 Fts3Phrase *pPhrase = pExpr->pPhrase;

4591 int i;

4592 for(i=0; *pRc==SQLITE_OK && i<pPhrase->nToken; i++){

4593 Fts3TokenAndCost pTC = (ppTC)++;

4594 pTC->pPhrase = pPhrase;

4595 pTC->iToken = i;

4596 pTC->pRoot = pRoot;

4597 pTC->pToken = &pPhrase->aToken[i];

4598 pTC->iCol = pPhrase->iColumn;

4599 *pRc = sqlite3Fts3MsrOvfl(pCsr, pTC->pToken->pSegcsr, &pTC->nOvfl);

4600 }

4601 }else if( pExpr->eType!=FTSQUERY_NOT ){

4602 assert( pExpr->eType==FTSQUERY_OR

4603 \|\| pExpr->eType==FTSQUERY_AND

4604 \|\| pExpr->eType==FTSQUERY_NEAR

4605 );

4606 assert( pExpr->pLeft && pExpr->pRight );

4607 if( pExpr->eType==FTSQUERY_OR ){

4608 pRoot = pExpr->pLeft;

4609 **ppOr = pRoot;

4610 (*ppOr)++;

4611 }

4612 fts3EvalTokenCosts(pCsr, pRoot, pExpr->pLeft, ppTC, ppOr, pRc);

4613 if( pExpr->eType==FTSQUERY_OR ){

4614 pRoot = pExpr->pRight;

4615 **ppOr = pRoot;

4616 (*ppOr)++;

4617 }

4618 fts3EvalTokenCosts(pCsr, pRoot, pExpr->pRight, ppTC, ppOr, pRc);

4619 }

4620 }

4621 }

4622

4623 /*

4624 ** Determine the average document (row) size in pages. If successful,

4625 ** write this value to *pnPage and return SQLITE_OK. Otherwise, return

4626 ** an SQLite error code.

4627 **

4628 ** The average document size in pages is calculated by first calculating

4629 ** determining the average size in bytes, B. If B is less than the amount

4630 ** of data that will fit on a single leaf page of an intkey table in

4631 ** this database, then the average docsize is 1. Otherwise, it is 1 plus

4632 ** the number of overflow pages consumed by a record B bytes in size.

4633 */

4634 static int fts3EvalAverageDocsize(Fts3Cursor pCsr, int pnPage){

4635 if( pCsr->nRowAvg==0 ){

4636 /* The average document size, which is required to calculate the cost

4637 ** of each doclist, has not yet been determined. Read the required

4638 ** data from the %_stat table to calculate it.

4639 **

4640 ** Entry 0 of the %_stat table is a blob containing (nCol+1) FTS3

4641 ** varints, where nCol is the number of columns in the FTS3 table.

4642 ** The first varint is the number of documents currently stored in

4643 ** the table. The following nCol varints contain the total amount of

4644 ** data stored in all rows of each column of the table, from left

4645 ** to right.

4646 */

4647 int rc;

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

4649 sqlite3_stmt *pStmt;

4650 sqlite3_int64 nDoc = 0;

4651 sqlite3_int64 nByte = 0;

4652 const char *pEnd;

4653 const char *a;

4654

4655 rc = sqlite3Fts3SelectDoctotal(p, &pStmt);

4656 if( rc!=SQLITE_OK ) return rc;

4657 a = sqlite3_column_blob(pStmt, 0);

4658 assert( a );

4659

4660 pEnd = &a[sqlite3_column_bytes(pStmt, 0)];

4661 a += sqlite3Fts3GetVarint(a, &nDoc);

4662 while( a<pEnd ){

4663 a += sqlite3Fts3GetVarint(a, &nByte);

4664 }

4665 if( nDoc==0 \|\| nByte==0 ){

4666 sqlite3_reset(pStmt);

4667 return FTS_CORRUPT_VTAB;

4668 }

4669

4670 pCsr->nDoc = nDoc;

4671 pCsr->nRowAvg = (int)(((nByte / nDoc) + p->nPgsz) / p->nPgsz);

4672 assert( pCsr->nRowAvg>0 );

4673 rc = sqlite3_reset(pStmt);

4674 if( rc!=SQLITE_OK ) return rc;

4675 }

4676

4677 *pnPage = pCsr->nRowAvg;

4678 return SQLITE_OK;

4679 }

4680

4681 /*

4682 ** This function is called to select the tokens (if any) that will be

4683 ** deferred. The array aTC[] has already been populated when this is

4684 ** called.

4685 **

4686 ** This function is called once for each AND/NEAR cluster in the

4687 ** expression. Each invocation determines which tokens to defer within

4688 ** the cluster with root node pRoot. See comments above the definition

4689 ** of struct Fts3TokenAndCost for more details.

4690 **

4691 ** If no error occurs, SQLITE_OK is returned and sqlite3Fts3DeferToken()

4692 ** called on each token to defer. Otherwise, an SQLite error code is

4693 ** returned.

4694 */

4695 static int fts3EvalSelectDeferred(

4696 Fts3Cursor pCsr, / FTS Cursor handle */

4697 Fts3Expr pRoot, / Consider tokens with this root node */

4698 Fts3TokenAndCost aTC, / Array of expression tokens and costs */

4699 int nTC /* Number of entries in aTC[] */

4700 ){

4701 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

4702 int nDocSize = 0; /* Number of pages per doc loaded */

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

4704 int ii; /* Iterator variable for various purposes */

4705 int nOvfl = 0; /* Total overflow pages used by doclists */

4706 int nToken = 0; /* Total number of tokens in cluster */

4707

4708 int nMinEst = 0; /* The minimum count for any phrase so far. */

4709 int nLoad4 = 1; /* (Phrases that will be loaded)^4. */

4710

4711 /* Tokens are never deferred for FTS tables created using the content=xxx

4712 ** option. The reason being that it is not guaranteed that the content

4713 ** table actually contains the same data as the index. To prevent this from

4714 ** causing any problems, the deferred token optimization is completely

4715 ** disabled for content=xxx tables. */

4716 if( pTab->zContentTbl ){

4717 return SQLITE_OK;

4718 }

4719

4720 /* Count the tokens in this AND/NEAR cluster. If none of the doclists

4721 ** associated with the tokens spill onto overflow pages, or if there is

4722 ** only 1 token, exit early. No tokens to defer in this case. */

4723 for(ii=0; ii<nTC; ii++){

4724 if( aTC[ii].pRoot==pRoot ){

4725 nOvfl += aTC[ii].nOvfl;

4726 nToken++;

4727 }

4728 }

4729 if( nOvfl==0 \|\| nToken<2 ) return SQLITE_OK;

4730

4731 /* Obtain the average docsize (in pages). */

4732 rc = fts3EvalAverageDocsize(pCsr, &nDocSize);

4733 assert( rc!=SQLITE_OK \|\| nDocSize>0 );

4734

4735

4736 /* Iterate through all tokens in this AND/NEAR cluster, in ascending order

4737 ** of the number of overflow pages that will be loaded by the pager layer

4738 ** to retrieve the entire doclist for the token from the full-text index.

4739 ** Load the doclists for tokens that are either:

4740 **

4741 ** a. The cheapest token in the entire query (i.e. the one visited by the

4742 ** first iteration of this loop), or

4743 **

4744 ** b. Part of a multi-token phrase.

4745 **

4746 ** After each token doclist is loaded, merge it with the others from the

4747 ** same phrase and count the number of documents that the merged doclist

4748 ** contains. Set variable "nMinEst" to the smallest number of documents in

4749 ** any phrase doclist for which 1 or more token doclists have been loaded.

4750 ** Let nOther be the number of other phrases for which it is certain that

4751 ** one or more tokens will not be deferred.

4752 **

4753 ** Then, for each token, defer it if loading the doclist would result in

4754 ** loading N or more overflow pages into memory, where N is computed as:

4755 **

4756 ** (nMinEst + 4^nOther - 1) / (4^nOther)

4757 */

4758 for(ii=0; ii<nToken && rc==SQLITE_OK; ii++){

4759 int iTC; /* Used to iterate through aTC[] array. */

4760 Fts3TokenAndCost pTC = 0; / Set to cheapest remaining token. */

4761

4762 /* Set pTC to point to the cheapest remaining token. */

4763 for(iTC=0; iTC<nTC; iTC++){

4764 if( aTC[iTC].pToken && aTC[iTC].pRoot==pRoot

4765 && (!pTC \|\| aTC[iTC].nOvfl<pTC->nOvfl)

4766 ){

4767 pTC = &aTC[iTC];

4768 }

4769 }

4770 assert( pTC );

4771

4772 if( ii && pTC->nOvfl>=((nMinEst+(nLoad4/4)-1)/(nLoad4/4))*nDocSize ){

4773 /* The number of overflow pages to load for this (and therefore all

4774 ** subsequent) tokens is greater than the estimated number of pages

4775 ** that will be loaded if all subsequent tokens are deferred.

4776 */

4777 Fts3PhraseToken *pToken = pTC->pToken;

4778 rc = sqlite3Fts3DeferToken(pCsr, pToken, pTC->iCol);

4779 fts3SegReaderCursorFree(pToken->pSegcsr);

4780 pToken->pSegcsr = 0;

4781 }else{

4782 /* Set nLoad4 to the value of (4^nOther) for the next iteration of the

4783 ** for-loop. Except, limit the value to 2^24 to prevent it from

4784 ** overflowing the 32-bit integer it is stored in. */

4785 if( ii<12 ) nLoad4 = nLoad4*4;

4786

4787 if( ii==0 \|\| (pTC->pPhrase->nToken>1 && ii!=nToken-1) ){

4788 /* Either this is the cheapest token in the entire query, or it is

4789 ** part of a multi-token phrase. Either way, the entire doclist will

4790 ** (eventually) be loaded into memory. It may as well be now. */

4791 Fts3PhraseToken *pToken = pTC->pToken;

4792 int nList = 0;

4793 char *pList = 0;

4794 rc = fts3TermSelect(pTab, pToken, pTC->iCol, &nList, &pList);

4795 assert( rc==SQLITE_OK \|\| pList==0 );

4796 if( rc==SQLITE_OK ){

4797 int nCount;

4798 fts3EvalPhraseMergeToken(pTab, pTC->pPhrase, pTC->iToken,pList,nList);

4799 nCount = fts3DoclistCountDocids(

4800 pTC->pPhrase->doclist.aAll, pTC->pPhrase->doclist.nAll

4801 );

4802 if( ii==0 \|\| nCount<nMinEst ) nMinEst = nCount;

4803 }

4804 }

4805 }

4806 pTC->pToken = 0;

4807 }

4808

4809 return rc;

4810 }

4811

4812 /*

4813 ** This function is called from within the xFilter method. It initializes

4814 ** the full-text query currently stored in pCsr->pExpr. To iterate through

4815 ** the results of a query, the caller does:

4816 **

4817 ** fts3EvalStart(pCsr);

4818 ** while( 1 ){

4819 ** fts3EvalNext(pCsr);

4820 ** if( pCsr->bEof ) break;

4821 ** ... return row pCsr->iPrevId to the caller ...

4822 ** }

4823 */

4824 static int fts3EvalStart(Fts3Cursor *pCsr){

4825 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

4826 int rc = SQLITE_OK;

4827 int nToken = 0;

4828 int nOr = 0;

4829

4830 /* Allocate a MultiSegReader for each token in the expression. */

4831 fts3EvalAllocateReaders(pCsr, pCsr->pExpr, &nToken, &nOr, &rc);

4832

4833 /* Determine which, if any, tokens in the expression should be deferred. */

4834 #ifndef SQLITE_DISABLE_FTS4_DEFERRED

4835 if( rc==SQLITE_OK && nToken>1 && pTab->bFts4 ){

4836 Fts3TokenAndCost *aTC;

4837 Fts3Expr **apOr;

4838 aTC = (Fts3TokenAndCost *)sqlite3_malloc(

4839 sizeof(Fts3TokenAndCost) * nToken

4840 + sizeof(Fts3Expr ) nOr * 2

4841 );

4842 apOr = (Fts3Expr **)&aTC[nToken];

4843

4844 if( !aTC ){

4845 rc = SQLITE_NOMEM;

4846 }else{

4847 int ii;

4848 Fts3TokenAndCost *pTC = aTC;

4849 Fts3Expr **ppOr = apOr;

4850

4851 fts3EvalTokenCosts(pCsr, 0, pCsr->pExpr, &pTC, &ppOr, &rc);

4852 nToken = (int)(pTC-aTC);

4853 nOr = (int)(ppOr-apOr);

4854

4855 if( rc==SQLITE_OK ){

4856 rc = fts3EvalSelectDeferred(pCsr, 0, aTC, nToken);

4857 for(ii=0; rc==SQLITE_OK && ii<nOr; ii++){

4858 rc = fts3EvalSelectDeferred(pCsr, apOr[ii], aTC, nToken);

4859 }

4860 }

4861

4862 sqlite3_free(aTC);

4863 }

4864 }

4865 #endif

4866

4867 fts3EvalStartReaders(pCsr, pCsr->pExpr, &rc);

4868 return rc;

4869 }

4870

4871 /*

4872 ** Invalidate the current position list for phrase pPhrase.

4873 */

4874 static void fts3EvalInvalidatePoslist(Fts3Phrase *pPhrase){

4875 if( pPhrase->doclist.bFreeList ){

4876 sqlite3_free(pPhrase->doclist.pList);

4877 }

4878 pPhrase->doclist.pList = 0;

4879 pPhrase->doclist.nList = 0;

4880 pPhrase->doclist.bFreeList = 0;

4881 }

4882

4883 /*

4884 ** This function is called to edit the position list associated with

4885 ** the phrase object passed as the fifth argument according to a NEAR

4886 ** condition. For example:

4887 **

4888 ** abc NEAR/5 "def ghi"

4889 **

4890 ** Parameter nNear is passed the NEAR distance of the expression (5 in

4891 ** the example above). When this function is called, *paPoslist points to

4892 ** the position list, and *pnToken is the number of phrase tokens in, the

4893 ** phrase on the other side of the NEAR operator to pPhrase. For example,

4894 ** if pPhrase refers to the "def ghi" phrase, then *paPoslist points to

4895 ** the position list associated with phrase "abc".

4896 **

4897 ** All positions in the pPhrase position list that are not sufficiently

4898 ** close to a position in the *paPoslist position list are removed. If this

4899 ** leaves 0 positions, zero is returned. Otherwise, non-zero.

4900 **

4901 ** Before returning, *paPoslist is set to point to the position lsit

4902 ** associated with pPhrase. And *pnToken is set to the number of tokens in

4903 ** pPhrase.

4904 */

4905 static int fts3EvalNearTrim(

4906 int nNear, /* NEAR distance. As in "NEAR/nNear". */

4907 char aTmp, / Temporary space to use */

4908 char *paPoslist, / IN/OUT: Position list */

4909 int pnToken, / IN/OUT: Tokens in phrase of paPoslist /

4910 Fts3Phrase pPhrase / The phrase object to trim the doclist of */

4911 ){

4912 int nParam1 = nNear + pPhrase->nToken;

4913 int nParam2 = nNear + *pnToken;

4914 int nNew;

4915 char *p2;

4916 char *pOut;

4917 int res;

4918

4919 assert( pPhrase->doclist.pList );

4920

4921 p2 = pOut = pPhrase->doclist.pList;

4922 res = fts3PoslistNearMerge(

4923 &pOut, aTmp, nParam1, nParam2, paPoslist, &p2

4924 );

4925 if( res ){

4926 nNew = (int)(pOut - pPhrase->doclist.pList) - 1;

4927 assert( pPhrase->doclist.pList[nNew]=='\0' );

4928 assert( nNew<=pPhrase->doclist.nList && nNew>0 );

4929 memset(&pPhrase->doclist.pList[nNew], 0, pPhrase->doclist.nList - nNew);

4930 pPhrase->doclist.nList = nNew;

4931 *paPoslist = pPhrase->doclist.pList;

4932 *pnToken = pPhrase->nToken;

4933 }

4934

4935 return res;

4936 }

4937

4938 /*

4939 ** This function is a no-op if *pRc is other than SQLITE_OK when it is called.

4940 ** Otherwise, it advances the expression passed as the second argument to

4941 ** point to the next matching row in the database. Expressions iterate through

4942 ** matching rows in docid order. Ascending order if Fts3Cursor.bDesc is zero,

4943 ** or descending if it is non-zero.

4944 **

4945 ** If an error occurs, *pRc is set to an SQLite error code. Otherwise, if

4946 ** successful, the following variables in pExpr are set:

4947 **

4948 ** Fts3Expr.bEof (non-zero if EOF - there is no next row)

4949 ** Fts3Expr.iDocid (valid if bEof==0. The docid of the next row)

4950 **

4951 ** If the expression is of type FTSQUERY_PHRASE, and the expression is not

4952 ** at EOF, then the following variables are populated with the position list

4953 ** for the phrase for the visited row:

4954 **

4955 ** FTs3Expr.pPhrase->doclist.nList (length of pList in bytes)

4956 ** FTs3Expr.pPhrase->doclist.pList (pointer to position list)

4957 **

4958 ** It says above that this function advances the expression to the next

4959 ** matching row. This is usually true, but there are the following exceptions:

4960 **

4961 ** 1. Deferred tokens are not taken into account. If a phrase consists

4962 ** entirely of deferred tokens, it is assumed to match every row in

4963 ** the db. In this case the position-list is not populated at all.

4964 **

4965 ** Or, if a phrase contains one or more deferred tokens and one or

4966 ** more non-deferred tokens, then the expression is advanced to the

4967 ** next possible match, considering only non-deferred tokens. In other

4968 ** words, if the phrase is "A B C", and "B" is deferred, the expression

4969 ** is advanced to the next row that contains an instance of "A * C",

4970 ** where "*" may match any single token. The position list in this case

4971 ** is populated as for "A * C" before returning.

4972 **

4973 ** 2. NEAR is treated as AND. If the expression is "x NEAR y", it is

4974 ** advanced to point to the next row that matches "x AND y".

4975 **

4976 ** See fts3EvalTestDeferredAndNear() for details on testing if a row is

4977 ** really a match, taking into account deferred tokens and NEAR operators.

4978 */

4979 static void fts3EvalNextRow(

4980 Fts3Cursor pCsr, / FTS Cursor handle */

4981 Fts3Expr pExpr, / Expr. to advance to next matching row */

4982 int pRc / IN/OUT: Error code */

4983 ){

4984 if( *pRc==SQLITE_OK ){

4985 int bDescDoclist = pCsr->bDesc; /* Used by DOCID_CMP() macro */

4986 assert( pExpr->bEof==0 );

4987 pExpr->bStart = 1;

4988

4989 switch( pExpr->eType ){

4990 case FTSQUERY_NEAR:

4991 case FTSQUERY_AND: {

4992 Fts3Expr *pLeft = pExpr->pLeft;

4993 Fts3Expr *pRight = pExpr->pRight;

4994 assert( !pLeft->bDeferred \|\| !pRight->bDeferred );

4995

4996 if( pLeft->bDeferred ){

4997 /* LHS is entirely deferred. So we assume it matches every row.

4998 ** Advance the RHS iterator to find the next row visited. */

4999 fts3EvalNextRow(pCsr, pRight, pRc);

5000 pExpr->iDocid = pRight->iDocid;

5001 pExpr->bEof = pRight->bEof;

5002 }else if( pRight->bDeferred ){

5003 /* RHS is entirely deferred. So we assume it matches every row.

5004 ** Advance the LHS iterator to find the next row visited. */

5005 fts3EvalNextRow(pCsr, pLeft, pRc);

5006 pExpr->iDocid = pLeft->iDocid;

5007 pExpr->bEof = pLeft->bEof;

5008 }else{

5009 /* Neither the RHS or LHS are deferred. */

5010 fts3EvalNextRow(pCsr, pLeft, pRc);

5011 fts3EvalNextRow(pCsr, pRight, pRc);

5012 while( !pLeft->bEof && !pRight->bEof && *pRc==SQLITE_OK ){

5013 sqlite3_int64 iDiff = DOCID_CMP(pLeft->iDocid, pRight->iDocid);

5014 if( iDiff==0 ) break;

5015 if( iDiff<0 ){

5016 fts3EvalNextRow(pCsr, pLeft, pRc);

5017 }else{

5018 fts3EvalNextRow(pCsr, pRight, pRc);

5019 }

5020 }

5021 pExpr->iDocid = pLeft->iDocid;

5022 pExpr->bEof = (pLeft->bEof \|\| pRight->bEof);

5023 }

5024 break;

5025 }

5026

5027 case FTSQUERY_OR: {

5028 Fts3Expr *pLeft = pExpr->pLeft;

5029 Fts3Expr *pRight = pExpr->pRight;

5030 sqlite3_int64 iCmp = DOCID_CMP(pLeft->iDocid, pRight->iDocid);

5031

5032 assert( pLeft->bStart \|\| pLeft->iDocid==pRight->iDocid );

5033 assert( pRight->bStart \|\| pLeft->iDocid==pRight->iDocid );

5034

5035 if( pRight->bEof \|\| (pLeft->bEof==0 && iCmp<0) ){

5036 fts3EvalNextRow(pCsr, pLeft, pRc);

5037 }else if( pLeft->bEof \|\| (pRight->bEof==0 && iCmp>0) ){

5038 fts3EvalNextRow(pCsr, pRight, pRc);

5039 }else{

5040 fts3EvalNextRow(pCsr, pLeft, pRc);

5041 fts3EvalNextRow(pCsr, pRight, pRc);

5042 }

5043

5044 pExpr->bEof = (pLeft->bEof && pRight->bEof);

5045 iCmp = DOCID_CMP(pLeft->iDocid, pRight->iDocid);

5046 if( pRight->bEof \|\| (pLeft->bEof==0 && iCmp<0) ){

5047 pExpr->iDocid = pLeft->iDocid;

5048 }else{

5049 pExpr->iDocid = pRight->iDocid;

5050 }

5051

5052 break;

5053 }

5054

5055 case FTSQUERY_NOT: {

5056 Fts3Expr *pLeft = pExpr->pLeft;

5057 Fts3Expr *pRight = pExpr->pRight;

5058

5059 if( pRight->bStart==0 ){

5060 fts3EvalNextRow(pCsr, pRight, pRc);

5061 assert( *pRc!=SQLITE_OK \|\| pRight->bStart );

5062 }

5063

5064 fts3EvalNextRow(pCsr, pLeft, pRc);

5065 if( pLeft->bEof==0 ){

5066 while( !*pRc

5067 && !pRight->bEof

5068 && DOCID_CMP(pLeft->iDocid, pRight->iDocid)>0

5069 ){

5070 fts3EvalNextRow(pCsr, pRight, pRc);

5071 }

5072 }

5073 pExpr->iDocid = pLeft->iDocid;

5074 pExpr->bEof = pLeft->bEof;

5075 break;

5076 }

5077

5078 default: {

5079 Fts3Phrase *pPhrase = pExpr->pPhrase;

5080 fts3EvalInvalidatePoslist(pPhrase);

5081 *pRc = fts3EvalPhraseNext(pCsr, pPhrase, &pExpr->bEof);

5082 pExpr->iDocid = pPhrase->doclist.iDocid;

5083 break;

5084 }

5085 }

5086 }

5087 }

5088

5089 /*

5090 ** If *pRc is not SQLITE_OK, or if pExpr is not the root node of a NEAR

5091 ** cluster, then this function returns 1 immediately.

5092 **

5093 ** Otherwise, it checks if the current row really does match the NEAR

5094 ** expression, using the data currently stored in the position lists

5095 ** (Fts3Expr->pPhrase.doclist.pList/nList) for each phrase in the expression.

5096 **

5097 ** If the current row is a match, the position list associated with each

5098 ** phrase in the NEAR expression is edited in place to contain only those

5099 ** phrase instances sufficiently close to their peers to satisfy all NEAR

5100 ** constraints. In this case it returns 1. If the NEAR expression does not

5101 ** match the current row, 0 is returned. The position lists may or may not

5102 ** be edited if 0 is returned.

5103 */

5104 static int fts3EvalNearTest(Fts3Expr pExpr, int pRc){

5105 int res = 1;

5106

5107 /* The following block runs if pExpr is the root of a NEAR query.

5108 ** For example, the query:

5109 **

5110 ** "w" NEAR "x" NEAR "y" NEAR "z"

5111 **

5112 ** which is represented in tree form as:

5113 **

5114 ** \|

5115 ** +--NEAR--+ <-- root of NEAR query

5116 ** \| \|

5117 ** +--NEAR--+ "z"

5118 ** \| \|

5119 ** +--NEAR--+ "y"

5120 ** \| \|

5121 ** "w" "x"

5122 **

5123 ** The right-hand child of a NEAR node is always a phrase. The

5124 ** left-hand child may be either a phrase or a NEAR node. There are

5125 ** no exceptions to this - it's the way the parser in fts3_expr.c works.

5126 */

5127 if( *pRc==SQLITE_OK

5128 && pExpr->eType==FTSQUERY_NEAR

5129 && pExpr->bEof==0

5130 && (pExpr->pParent==0 \|\| pExpr->pParent->eType!=FTSQUERY_NEAR)

5131 ){

5132 Fts3Expr *p;

5133 int nTmp = 0; /* Bytes of temp space */

5134 char aTmp; / Temp space for PoslistNearMerge() */

5135

5136 /* Allocate temporary working space. */

5137 for(p=pExpr; p->pLeft; p=p->pLeft){

5138 nTmp += p->pRight->pPhrase->doclist.nList;

5139 }

5140 nTmp += p->pPhrase->doclist.nList;

5141 if( nTmp==0 ){

5142 res = 0;

5143 }else{

5144 aTmp = sqlite3_malloc(nTmp*2);

5145 if( !aTmp ){

5146 *pRc = SQLITE_NOMEM;

5147 res = 0;

5148 }else{

5149 char *aPoslist = p->pPhrase->doclist.pList;

5150 int nToken = p->pPhrase->nToken;

5151

5152 for(p=p->pParent;res && p && p->eType==FTSQUERY_NEAR; p=p->pParent){

5153 Fts3Phrase *pPhrase = p->pRight->pPhrase;

5154 int nNear = p->nNear;

5155 res = fts3EvalNearTrim(nNear, aTmp, &aPoslist, &nToken, pPhrase);

5156 }

5157

5158 aPoslist = pExpr->pRight->pPhrase->doclist.pList;

5159 nToken = pExpr->pRight->pPhrase->nToken;

5160 for(p=pExpr->pLeft; p && res; p=p->pLeft){

5161 int nNear;

5162 Fts3Phrase *pPhrase;

5163 assert( p->pParent && p->pParent->pLeft==p );

5164 nNear = p->pParent->nNear;

5165 pPhrase = (

5166 p->eType==FTSQUERY_NEAR ? p->pRight->pPhrase : p->pPhrase

5167 );

5168 res = fts3EvalNearTrim(nNear, aTmp, &aPoslist, &nToken, pPhrase);

5169 }

5170 }

5171

5172 sqlite3_free(aTmp);

5173 }

5174 }

5175

5176 return res;

5177 }

5178

5179 /*

5180 ** This function is a helper function for fts3EvalTestDeferredAndNear().

5181 ** Assuming no error occurs or has occurred, It returns non-zero if the

5182 ** expression passed as the second argument matches the row that pCsr

5183 ** currently points to, or zero if it does not.

5184 **

5185 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.

5186 ** If an error occurs during execution of this function, *pRc is set to

5187 ** the appropriate SQLite error code. In this case the returned value is

5188 ** undefined.

5189 */

5190 static int fts3EvalTestExpr(

5191 Fts3Cursor pCsr, / FTS cursor handle */

5192 Fts3Expr pExpr, / Expr to test. May or may not be root. */

5193 int pRc / IN/OUT: Error code */

5194 ){

5195 int bHit = 1; /* Return value */

5196 if( *pRc==SQLITE_OK ){

5197 switch( pExpr->eType ){

5198 case FTSQUERY_NEAR:

5199 case FTSQUERY_AND:

5200 bHit = (

5201 fts3EvalTestExpr(pCsr, pExpr->pLeft, pRc)

5202 && fts3EvalTestExpr(pCsr, pExpr->pRight, pRc)

5203 && fts3EvalNearTest(pExpr, pRc)

5204 );

5205

5206 /* If the NEAR expression does not match any rows, zero the doclist for

5207 ** all phrases involved in the NEAR. This is because the snippet(),

5208 ** offsets() and matchinfo() functions are not supposed to recognize

5209 ** any instances of phrases that are part of unmatched NEAR queries.

5210 ** For example if this expression:

5211 **

5212 ** ... MATCH 'a OR (b NEAR c)'

5213 **

5214 ** is matched against a row containing:

5215 **

5216 ** 'a b d e'

5217 **

5218 ** then any snippet() should ony highlight the "a" term, not the "b"

5219 ** (as "b" is part of a non-matching NEAR clause).

5220 */

5221 if( bHit==0

5222 && pExpr->eType==FTSQUERY_NEAR

5223 && (pExpr->pParent==0 \|\| pExpr->pParent->eType!=FTSQUERY_NEAR)

5224 ){

5225 Fts3Expr *p;

5226 for(p=pExpr; p->pPhrase==0; p=p->pLeft){

5227 if( p->pRight->iDocid==pCsr->iPrevId ){

5228 fts3EvalInvalidatePoslist(p->pRight->pPhrase);

5229 }

5230 }

5231 if( p->iDocid==pCsr->iPrevId ){

5232 fts3EvalInvalidatePoslist(p->pPhrase);

5233 }

5234 }

5235

5236 break;

5237

5238 case FTSQUERY_OR: {

5239 int bHit1 = fts3EvalTestExpr(pCsr, pExpr->pLeft, pRc);

5240 int bHit2 = fts3EvalTestExpr(pCsr, pExpr->pRight, pRc);

5241 bHit = bHit1 \|\| bHit2;

5242 break;

5243 }

5244

5245 case FTSQUERY_NOT:

5246 bHit = (

5247 fts3EvalTestExpr(pCsr, pExpr->pLeft, pRc)

5248 && !fts3EvalTestExpr(pCsr, pExpr->pRight, pRc)

5249 );

5250 break;

5251

5252 default: {

5253 #ifndef SQLITE_DISABLE_FTS4_DEFERRED

5254 if( pCsr->pDeferred

5255 && (pExpr->iDocid==pCsr->iPrevId \|\| pExpr->bDeferred)

5256 ){

5257 Fts3Phrase *pPhrase = pExpr->pPhrase;

5258 assert( pExpr->bDeferred \|\| pPhrase->doclist.bFreeList==0 );

5259 if( pExpr->bDeferred ){

5260 fts3EvalInvalidatePoslist(pPhrase);

5261 }

5262 *pRc = fts3EvalDeferredPhrase(pCsr, pPhrase);

5263 bHit = (pPhrase->doclist.pList!=0);

5264 pExpr->iDocid = pCsr->iPrevId;

5265 }else

5266 #endif

5267 {

5268 bHit = (pExpr->bEof==0 && pExpr->iDocid==pCsr->iPrevId);

5269 }

5270 break;

5271 }

5272 }

5273 }

5274 return bHit;

5275 }

5276

5277 /*

5278 ** This function is called as the second part of each xNext operation when

5279 ** iterating through the results of a full-text query. At this point the

5280 ** cursor points to a row that matches the query expression, with the

5281 ** following caveats:

5282 **

5283 ** * Up until this point, "NEAR" operators in the expression have been

5284 ** treated as "AND".

5285 **

5286 ** * Deferred tokens have not yet been considered.

5287 **

5288 ** If *pRc is not SQLITE_OK when this function is called, it immediately

5289 ** returns 0. Otherwise, it tests whether or not after considering NEAR

5290 ** operators and deferred tokens the current row is still a match for the

5291 ** expression. It returns 1 if both of the following are true:

5292 **

5293 ** 1. *pRc is SQLITE_OK when this function returns, and

5294 **

5295 ** 2. After scanning the current FTS table row for the deferred tokens,

5296 ** it is determined that the row does not match the query.

5297 **

5298 ** Or, if no error occurs and it seems the current row does match the FTS

5299 ** query, return 0.

5300 */

5301 static int fts3EvalTestDeferredAndNear(Fts3Cursor pCsr, int pRc){

5302 int rc = *pRc;

5303 int bMiss = 0;

5304 if( rc==SQLITE_OK ){

5305

5306 /* If there are one or more deferred tokens, load the current row into

5307 ** memory and scan it to determine the position list for each deferred

5308 ** token. Then, see if this row is really a match, considering deferred

5309 ** tokens and NEAR operators (neither of which were taken into account

5310 ** earlier, by fts3EvalNextRow()).

5311 */

5312 if( pCsr->pDeferred ){

5313 rc = fts3CursorSeek(0, pCsr);

5314 if( rc==SQLITE_OK ){

5315 rc = sqlite3Fts3CacheDeferredDoclists(pCsr);

5316 }

5317 }

5318 bMiss = (0==fts3EvalTestExpr(pCsr, pCsr->pExpr, &rc));

5319

5320 /* Free the position-lists accumulated for each deferred token above. */

5321 sqlite3Fts3FreeDeferredDoclists(pCsr);

5322 *pRc = rc;

5323 }

5324 return (rc==SQLITE_OK && bMiss);

5325 }

5326

5327 /*

5328 ** Advance to the next document that matches the FTS expression in

5329 ** Fts3Cursor.pExpr.

5330 */

5331 static int fts3EvalNext(Fts3Cursor *pCsr){

5332 int rc = SQLITE_OK; /* Return Code */

5333 Fts3Expr *pExpr = pCsr->pExpr;

5334 assert( pCsr->isEof==0 );

5335 if( pExpr==0 ){

5336 pCsr->isEof = 1;

5337 }else{

5338 do {

5339 if( pCsr->isRequireSeek==0 ){

5340 sqlite3_reset(pCsr->pStmt);

5341 }

5342 assert( sqlite3_data_count(pCsr->pStmt)==0 );

5343 fts3EvalNextRow(pCsr, pExpr, &rc);

5344 pCsr->isEof = pExpr->bEof;

5345 pCsr->isRequireSeek = 1;

5346 pCsr->isMatchinfoNeeded = 1;

5347 pCsr->iPrevId = pExpr->iDocid;

5348 }while( pCsr->isEof==0 && fts3EvalTestDeferredAndNear(pCsr, &rc) );

5349 }

5350

5351 /* Check if the cursor is past the end of the docid range specified

5352 ** by Fts3Cursor.iMinDocid/iMaxDocid. If so, set the EOF flag. */

5353 if( rc==SQLITE_OK && (

5354 (pCsr->bDesc==0 && pCsr->iPrevId>pCsr->iMaxDocid)

5355 \|\| (pCsr->bDesc!=0 && pCsr->iPrevId<pCsr->iMinDocid)

5356 )){

5357 pCsr->isEof = 1;

5358 }

5359

5360 return rc;

5361 }

5362

5363 /*

5364 ** Restart interation for expression pExpr so that the next call to

5365 ** fts3EvalNext() visits the first row. Do not allow incremental

5366 ** loading or merging of phrase doclists for this iteration.

5367 **

5368 ** If *pRc is other than SQLITE_OK when this function is called, it is

5369 ** a no-op. If an error occurs within this function, *pRc is set to an

5370 ** SQLite error code before returning.

5371 */

5372 static void fts3EvalRestart(

5373 Fts3Cursor *pCsr,

5374 Fts3Expr *pExpr,

5375 int *pRc

5376 ){

5377 if( pExpr && *pRc==SQLITE_OK ){

5378 Fts3Phrase *pPhrase = pExpr->pPhrase;

5379

5380 if( pPhrase ){

5381 fts3EvalInvalidatePoslist(pPhrase);

5382 if( pPhrase->bIncr ){

5383 int i;

5384 for(i=0; i<pPhrase->nToken; i++){

5385 Fts3PhraseToken *pToken = &pPhrase->aToken[i];

5386 assert( pToken->pDeferred==0 );

5387 if( pToken->pSegcsr ){

5388 sqlite3Fts3MsrIncrRestart(pToken->pSegcsr);

5389 }

5390 }

5391 *pRc = fts3EvalPhraseStart(pCsr, 0, pPhrase);

5392 }

5393 pPhrase->doclist.pNextDocid = 0;

5394 pPhrase->doclist.iDocid = 0;

5395 }

5396

5397 pExpr->iDocid = 0;

5398 pExpr->bEof = 0;

5399 pExpr->bStart = 0;

5400

5401 fts3EvalRestart(pCsr, pExpr->pLeft, pRc);

5402 fts3EvalRestart(pCsr, pExpr->pRight, pRc);

5403 }

5404 }

5405

5406 /*

5407 ** After allocating the Fts3Expr.aMI[] array for each phrase in the

5408 ** expression rooted at pExpr, the cursor iterates through all rows matched

5409 ** by pExpr, calling this function for each row. This function increments

5410 ** the values in Fts3Expr.aMI[] according to the position-list currently

5411 ** found in Fts3Expr.pPhrase->doclist.pList for each of the phrase

5412 ** expression nodes.

5413 */

5414 static void fts3EvalUpdateCounts(Fts3Expr *pExpr){

5415 if( pExpr ){

5416 Fts3Phrase *pPhrase = pExpr->pPhrase;

5417 if( pPhrase && pPhrase->doclist.pList ){

5418 int iCol = 0;

5419 char *p = pPhrase->doclist.pList;

5420

5421 assert( *p );

5422 while( 1 ){

5423 u8 c = 0;

5424 int iCnt = 0;

5425 while( 0xFE & (*p \| c) ){

5426 if( (c&0x80)==0 ) iCnt++;

5427 c = *p++ & 0x80;

5428 }

5429

5430 /* aMI[iCol*3 + 1] = Number of occurrences

5431 ** aMI[iCol*3 + 2] = Number of rows containing at least one instance

5432 */

5433 pExpr->aMI[iCol*3 + 1] += iCnt;

5434 pExpr->aMI[iCol*3 + 2] += (iCnt>0);

5435 if( *p==0x00 ) break;

5436 p++;

5437 p += fts3GetVarint32(p, &iCol);

5438 }

5439 }

5440

5441 fts3EvalUpdateCounts(pExpr->pLeft);

5442 fts3EvalUpdateCounts(pExpr->pRight);

5443 }

5444 }

5445

5446 /*

5447 ** Expression pExpr must be of type FTSQUERY_PHRASE.

5448 **

5449 ** If it is not already allocated and populated, this function allocates and

5450 ** populates the Fts3Expr.aMI[] array for expression pExpr. If pExpr is part

5451 ** of a NEAR expression, then it also allocates and populates the same array

5452 ** for all other phrases that are part of the NEAR expression.

5453 **

5454 ** SQLITE_OK is returned if the aMI[] array is successfully allocated and

5455 ** populated. Otherwise, if an error occurs, an SQLite error code is returned.

5456 */

5457 static int fts3EvalGatherStats(

5458 Fts3Cursor pCsr, / Cursor object */

5459 Fts3Expr pExpr / FTSQUERY_PHRASE expression */

5460 ){

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

5462

5463 assert( pExpr->eType==FTSQUERY_PHRASE );

5464 if( pExpr->aMI==0 ){

5465 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

5466 Fts3Expr pRoot; / Root of NEAR expression */

5467 Fts3Expr p; / Iterator used for several purposes */

5468

5469 sqlite3_int64 iPrevId = pCsr->iPrevId;

5470 sqlite3_int64 iDocid;

5471 u8 bEof;

5472

5473 /* Find the root of the NEAR expression */

5474 pRoot = pExpr;

5475 while( pRoot->pParent && pRoot->pParent->eType==FTSQUERY_NEAR ){

5476 pRoot = pRoot->pParent;

5477 }

5478 iDocid = pRoot->iDocid;

5479 bEof = pRoot->bEof;

5480 assert( pRoot->bStart );

5481

5482 /* Allocate space for the aMSI[] array of each FTSQUERY_PHRASE node */

5483 for(p=pRoot; p; p=p->pLeft){

5484 Fts3Expr *pE = (p->eType==FTSQUERY_PHRASE?p:p->pRight);

5485 assert( pE->aMI==0 );

5486 pE->aMI = (u32 )sqlite3_malloc(pTab->nColumn 3 * sizeof(u32));

5487 if( !pE->aMI ) return SQLITE_NOMEM;

5488 memset(pE->aMI, 0, pTab->nColumn * 3 * sizeof(u32));

5489 }

5490

5491 fts3EvalRestart(pCsr, pRoot, &rc);

5492

5493 while( pCsr->isEof==0 && rc==SQLITE_OK ){

5494

5495 do {

5496 /* Ensure the %_content statement is reset. */

5497 if( pCsr->isRequireSeek==0 ) sqlite3_reset(pCsr->pStmt);

5498 assert( sqlite3_data_count(pCsr->pStmt)==0 );

5499

5500 /* Advance to the next document */

5501 fts3EvalNextRow(pCsr, pRoot, &rc);

5502 pCsr->isEof = pRoot->bEof;

5503 pCsr->isRequireSeek = 1;

5504 pCsr->isMatchinfoNeeded = 1;

5505 pCsr->iPrevId = pRoot->iDocid;

5506 }while( pCsr->isEof==0

5507 && pRoot->eType==FTSQUERY_NEAR

5508 && fts3EvalTestDeferredAndNear(pCsr, &rc)

5509 );

5510

5511 if( rc==SQLITE_OK && pCsr->isEof==0 ){

5512 fts3EvalUpdateCounts(pRoot);

5513 }

5514 }

5515

5516 pCsr->isEof = 0;

5517 pCsr->iPrevId = iPrevId;

5518

5519 if( bEof ){

5520 pRoot->bEof = bEof;

5521 }else{

5522 /* Caution: pRoot may iterate through docids in ascending or descending

5523 ** order. For this reason, even though it seems more defensive, the

5524 ** do loop can not be written:

5525 **

5526 ** do {...} while( pRoot->iDocid<iDocid && rc==SQLITE_OK );

5527 */

5528 fts3EvalRestart(pCsr, pRoot, &rc);

5529 do {

5530 fts3EvalNextRow(pCsr, pRoot, &rc);

5531 assert( pRoot->bEof==0 );

5532 }while( pRoot->iDocid!=iDocid && rc==SQLITE_OK );

5533 fts3EvalTestDeferredAndNear(pCsr, &rc);

5534 }

5535 }

5536 return rc;

5537 }

5538

5539 /*

5540 ** This function is used by the matchinfo() module to query a phrase

5541 ** expression node for the following information:

5542 **

5543 ** 1. The total number of occurrences of the phrase in each column of

5544 ** the FTS table (considering all rows), and

5545 **

5546 ** 2. For each column, the number of rows in the table for which the

5547 ** column contains at least one instance of the phrase.

5548 **

5549 ** If no error occurs, SQLITE_OK is returned and the values for each column

5550 ** written into the array aiOut as follows:

5551 **

5552 ** aiOut[iCol*3 + 1] = Number of occurrences

5553 ** aiOut[iCol*3 + 2] = Number of rows containing at least one instance

5554 **

5555 ** Caveats:

5556 **

5557 ** * If a phrase consists entirely of deferred tokens, then all output

5558 ** values are set to the number of documents in the table. In other

5559 ** words we assume that very common tokens occur exactly once in each

5560 ** column of each row of the table.

5561 **

5562 ** * If a phrase contains some deferred tokens (and some non-deferred

5563 ** tokens), count the potential occurrence identified by considering

5564 ** the non-deferred tokens instead of actual phrase occurrences.

5565 **

5566 ** * If the phrase is part of a NEAR expression, then only phrase instances

5567 ** that meet the NEAR constraint are included in the counts.

5568 */

5569 int sqlite3Fts3EvalPhraseStats(

5570 Fts3Cursor pCsr, / FTS cursor handle */

5571 Fts3Expr pExpr, / Phrase expression */

5572 u32 aiOut / Array to write results into (see above) */

5573 ){

5574 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

5575 int rc = SQLITE_OK;

5576 int iCol;

5577

5578 if( pExpr->bDeferred && pExpr->pParent->eType!=FTSQUERY_NEAR ){

5579 assert( pCsr->nDoc>0 );

5580 for(iCol=0; iCol<pTab->nColumn; iCol++){

5581 aiOut[iCol*3 + 1] = (u32)pCsr->nDoc;

5582 aiOut[iCol*3 + 2] = (u32)pCsr->nDoc;

5583 }

5584 }else{

5585 rc = fts3EvalGatherStats(pCsr, pExpr);

5586 if( rc==SQLITE_OK ){

5587 assert( pExpr->aMI );

5588 for(iCol=0; iCol<pTab->nColumn; iCol++){

5589 aiOut[iCol3 + 1] = pExpr->aMI[iCol3 + 1];

5590 aiOut[iCol3 + 2] = pExpr->aMI[iCol3 + 2];

5591 }

5592 }

5593 }

5594

5595 return rc;

5596 }

5597

5598 /*

5599 ** The expression pExpr passed as the second argument to this function

5600 ** must be of type FTSQUERY_PHRASE.

5601 **

5602 ** The returned value is either NULL or a pointer to a buffer containing

5603 ** a position-list indicating the occurrences of the phrase in column iCol

5604 ** of the current row.

5605 **

5606 ** More specifically, the returned buffer contains 1 varint for each

5607 ** occurrence of the phrase in the column, stored using the normal (delta+2)

5608 ** compression and is terminated by either an 0x01 or 0x00 byte. For example,

5609 ** if the requested column contains "a b X c d X X" and the position-list

5610 ** for 'X' is requested, the buffer returned may contain:

5611 **

5612 ** 0x04 0x05 0x03 0x01 or 0x04 0x05 0x03 0x00

5613 **

5614 ** This function works regardless of whether or not the phrase is deferred,

5615 ** incremental, or neither.

5616 */

5617 int sqlite3Fts3EvalPhrasePoslist(

5618 Fts3Cursor pCsr, / FTS3 cursor object */

5619 Fts3Expr pExpr, / Phrase to return doclist for */

5620 int iCol, /* Column to return position list for */

5621 char *ppOut / OUT: Pointer to position list */

5622 ){

5623 Fts3Phrase *pPhrase = pExpr->pPhrase;

5624 Fts3Table pTab = (Fts3Table )pCsr->base.pVtab;

5625 char *pIter;

5626 int iThis;

5627 sqlite3_int64 iDocid;

5628

5629 /* If this phrase is applies specifically to some column other than

5630 ** column iCol, return a NULL pointer. */

5631 *ppOut = 0;

5632 assert( iCol>=0 && iCol<pTab->nColumn );

5633 if( (pPhrase->iColumn<pTab->nColumn && pPhrase->iColumn!=iCol) ){

5634 return SQLITE_OK;

5635 }

5636

5637 iDocid = pExpr->iDocid;

5638 pIter = pPhrase->doclist.pList;

5639 if( iDocid!=pCsr->iPrevId \|\| pExpr->bEof ){

5640 int bDescDoclist = pTab->bDescIdx; /* For DOCID_CMP macro */

5641 int iMul; /* +1 if csr dir matches index dir, else -1 */

5642 int bOr = 0;

5643 u8 bEof = 0;

5644 u8 bTreeEof = 0;

5645 Fts3Expr p; / Used to iterate from pExpr to root */

5646 Fts3Expr pNear; / Most senior NEAR ancestor (or pExpr) */

5647

5648 /* Check if this phrase descends from an OR expression node. If not,

5649 ** return NULL. Otherwise, the entry that corresponds to docid

5650 ** pCsr->iPrevId may lie earlier in the doclist buffer. Or, if the

5651 ** tree that the node is part of has been marked as EOF, but the node

5652 ** itself is not EOF, then it may point to an earlier entry. */

5653 pNear = pExpr;

5654 for(p=pExpr->pParent; p; p=p->pParent){

5655 if( p->eType==FTSQUERY_OR ) bOr = 1;

5656 if( p->eType==FTSQUERY_NEAR ) pNear = p;

5657 if( p->bEof ) bTreeEof = 1;

5658 }

5659 if( bOr==0 ) return SQLITE_OK;

5660

5661 /* This is the descendent of an OR node. In this case we cannot use

5662 ** an incremental phrase. Load the entire doclist for the phrase

5663 ** into memory in this case. */

5664 if( pPhrase->bIncr ){

5665 int rc = SQLITE_OK;

5666 int bEofSave = pExpr->bEof;

5667 fts3EvalRestart(pCsr, pExpr, &rc);

5668 while( rc==SQLITE_OK && !pExpr->bEof ){

5669 fts3EvalNextRow(pCsr, pExpr, &rc);

5670 if( bEofSave==0 && pExpr->iDocid==iDocid ) break;

5671 }

5672 pIter = pPhrase->doclist.pList;

5673 assert( rc!=SQLITE_OK \|\| pPhrase->bIncr==0 );

5674 if( rc!=SQLITE_OK ) return rc;

5675 }

5676

5677 iMul = ((pCsr->bDesc==bDescDoclist) ? 1 : -1);

5678 while( bTreeEof==1

5679 && pNear->bEof==0

5680 && (DOCID_CMP(pNear->iDocid, pCsr->iPrevId) * iMul)<0

5681 ){

5682 int rc = SQLITE_OK;

5683 fts3EvalNextRow(pCsr, pExpr, &rc);

5684 if( rc!=SQLITE_OK ) return rc;

5685 iDocid = pExpr->iDocid;

5686 pIter = pPhrase->doclist.pList;

5687 }

5688

5689 bEof = (pPhrase->doclist.nAll==0);

5690 assert( bDescDoclist==0 \|\| bDescDoclist==1 );

5691 assert( pCsr->bDesc==0 \|\| pCsr->bDesc==1 );

5692

5693 if( bEof==0 ){

5694 if( pCsr->bDesc==bDescDoclist ){

5695 int dummy;

5696 if( pNear->bEof ){

5697 /* This expression is already at EOF. So position it to point to the

5698 ** last entry in the doclist at pPhrase->doclist.aAll[]. Variable

5699 ** iDocid is already set for this entry, so all that is required is

5700 ** to set pIter to point to the first byte of the last position-list

5701 ** in the doclist.

5702 **

5703 ** It would also be correct to set pIter and iDocid to zero. In

5704 ** this case, the first call to sqltie3Fts4DoclistPrev() below

5705 ** would also move the iterator to point to the last entry in the

5706 ** doclist. However, this is expensive, as to do so it has to

5707 ** iterate through the entire doclist from start to finish (since

5708 ** it does not know the docid for the last entry). */

5709 pIter = &pPhrase->doclist.aAll[pPhrase->doclist.nAll-1];

5710 fts3ReversePoslist(pPhrase->doclist.aAll, &pIter);

5711 }

5712 while( (pIter==0 \|\| DOCID_CMP(iDocid, pCsr->iPrevId)>0 ) && bEof==0 ){

5713 sqlite3Fts3DoclistPrev(

5714 bDescDoclist, pPhrase->doclist.aAll, pPhrase->doclist.nAll,

5715 &pIter, &iDocid, &dummy, &bEof

5716 );

5717 }

5718 }else{

5719 if( pNear->bEof ){

5720 pIter = 0;

5721 iDocid = 0;

5722 }

5723 while( (pIter==0 \|\| DOCID_CMP(iDocid, pCsr->iPrevId)<0 ) && bEof==0 ){

5724 sqlite3Fts3DoclistNext(

5725 bDescDoclist, pPhrase->doclist.aAll, pPhrase->doclist.nAll,

5726 &pIter, &iDocid, &bEof

5727 );

5728 }

5729 }

5730 }

5731

5732 if( bEof \|\| iDocid!=pCsr->iPrevId ) pIter = 0;

5733 }

5734 if( pIter==0 ) return SQLITE_OK;

5735

5736 if( *pIter==0x01 ){

5737 pIter++;

5738 pIter += fts3GetVarint32(pIter, &iThis);

5739 }else{

5740 iThis = 0;

5741 }

5742 while( iThis<iCol ){

5743 fts3ColumnlistCopy(0, &pIter);

5744 if( *pIter==0x00 ) return 0;

5745 pIter++;

5746 pIter += fts3GetVarint32(pIter, &iThis);

5747 }

5748

5749 *ppOut = ((iCol==iThis)?pIter:0);

5750 return SQLITE_OK;

5751 }

5752

5753 /*

5754 ** Free all components of the Fts3Phrase structure that were allocated by

5755 ** the eval module. Specifically, this means to free:

5756 **

5757 ** * the contents of pPhrase->doclist, and

5758 ** * any Fts3MultiSegReader objects held by phrase tokens.

5759 */

5760 void sqlite3Fts3EvalPhraseCleanup(Fts3Phrase *pPhrase){

5761 if( pPhrase ){

5762 int i;

5763 sqlite3_free(pPhrase->doclist.aAll);

5764 fts3EvalInvalidatePoslist(pPhrase);

5765 memset(&pPhrase->doclist, 0, sizeof(Fts3Doclist));

5766 for(i=0; i<pPhrase->nToken; i++){

5767 fts3SegReaderCursorFree(pPhrase->aToken[i].pSegcsr);

5768 pPhrase->aToken[i].pSegcsr = 0;

5769 }

5770 }

5771 }

5772

5773

5774 /*

5775 ** Return SQLITE_CORRUPT_VTAB.

5776 */

5777 #ifdef SQLITE_DEBUG

5778 int sqlite3Fts3Corrupt(){

5779 return SQLITE_CORRUPT_VTAB;

5780 }

5781 #endif

5782

5783 #if !SQLITE_CORE

5784 /*

5785 ** Initialize API pointer table, if required.

5786 */

5787 #ifdef _WIN32

5788 __declspec(dllexport)

5789 #endif

5790 int sqlite3_fts3_init(

5791 sqlite3 *db,

5792 char **pzErrMsg,

5793 const sqlite3_api_routines *pApi

5794 ){

5795 SQLITE_EXTENSION_INIT2(pApi)

5796 return sqlite3Fts3Init(db);

5797 }

5798 #endif

5799

5800 #endif

OLD	NEW

« no previous file with comments | « third_party/sqlite/sqlite-src-3080704/ext/fts3/fts3.h ('k') | third_party/sqlite/sqlite-src-3080704/ext/fts3/fts3Int.h » ('j') | no next file with comments »