1 /*
2 ** 2014 May 31
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 */
14
15
16
17 #include "fts5Int.h"
18 #include "fts5parse.h"
19
20 /*
21 ** All token types in the generated fts5parse.h file are greater than 0.
22 */
23 #define FTS5_EOF 0
24
25 #define FTS5_LARGEST_INT64 (0xffffffff|(((i64)0x7fffffff)<<32))
26
27 typedef struct Fts5ExprTerm Fts5ExprTerm;
28
29 /*
30 ** Functions generated by lemon from fts5parse.y.
31 */
32 void *sqlite3Fts5ParserAlloc(void *(*mallocProc)(u64));
33 void sqlite3Fts5ParserFree(void*, void (*freeProc)(void*));
34 void sqlite3Fts5Parser(void*, int, Fts5Token, Fts5Parse*);
35 #ifndef NDEBUG
36 #include <stdio.h>
37 void sqlite3Fts5ParserTrace(FILE*, char*);
38 #endif
39 int sqlite3Fts5ParserFallback(int);
40
41
42 struct Fts5Expr {
43 Fts5Index *pIndex;
44 Fts5Config *pConfig;
45 Fts5ExprNode *pRoot;
46 int bDesc; /* Iterate in descending rowid order */
47 int nPhrase; /* Number of phrases in expression */
48 Fts5ExprPhrase **apExprPhrase; /* Pointers to phrase objects */
49 };
50
51 /*
52 ** eType:
53 ** Expression node type. Always one of:
54 **
55 ** FTS5_AND (nChild, apChild valid)
56 ** FTS5_OR (nChild, apChild valid)
57 ** FTS5_NOT (nChild, apChild valid)
58 ** FTS5_STRING (pNear valid)
59 ** FTS5_TERM (pNear valid)
60 */
61 struct Fts5ExprNode {
62 int eType; /* Node type */
63 int bEof; /* True at EOF */
64 int bNomatch; /* True if entry is not a match */
65
66 /* Next method for this node. */
67 int (*xNext)(Fts5Expr*, Fts5ExprNode*, int, i64);
68
69 i64 iRowid; /* Current rowid */
70 Fts5ExprNearset *pNear; /* For FTS5_STRING - cluster of phrases */
71
72 /* Child nodes. For a NOT node, this array always contains 2 entries. For
73 ** AND or OR nodes, it contains 2 or more entries. */
74 int nChild; /* Number of child nodes */
75 Fts5ExprNode *apChild[1]; /* Array of child nodes */
76 };
77
78 #define Fts5NodeIsString(p) ((p)->eType==FTS5_TERM || (p)->eType==FTS5_STRING)
79
80 /*
81 ** Invoke the xNext method of an Fts5ExprNode object. This macro should be
82 ** used as if it has the same signature as the xNext() methods themselves.
83 */
84 #define fts5ExprNodeNext(a,b,c,d) (b)->xNext((a), (b), (c), (d))
85
86 /*
87 ** An instance of the following structure represents a single search term
88 ** or term prefix.
89 */
90 struct Fts5ExprTerm {
91 u8 bPrefix; /* True for a prefix term */
92 u8 bFirst; /* True if token must be first in column */
93 char *zTerm; /* nul-terminated term */
94 Fts5IndexIter *pIter; /* Iterator for this term */
95 Fts5ExprTerm *pSynonym; /* Pointer to first in list of synonyms */
96 };
97
98 /*
99 ** A phrase. One or more terms that must appear in a contiguous sequence
100 ** within a document for it to match.
101 */
102 struct Fts5ExprPhrase {
103 Fts5ExprNode *pNode; /* FTS5_STRING node this phrase is part of */
104 Fts5Buffer poslist; /* Current position list */
105 int nTerm; /* Number of entries in aTerm[] */
106 Fts5ExprTerm aTerm[1]; /* Terms that make up this phrase */
107 };
108
109 /*
110 ** One or more phrases that must appear within a certain token distance of
111 ** each other within each matching document.
112 */
113 struct Fts5ExprNearset {
114 int nNear; /* NEAR parameter */
115 Fts5Colset *pColset; /* Columns to search (NULL -> all columns) */
116 int nPhrase; /* Number of entries in aPhrase[] array */
117 Fts5ExprPhrase *apPhrase[1]; /* Array of phrase pointers */
118 };
119
120
121 /*
122 ** Parse context.
123 */
124 struct Fts5Parse {
125 Fts5Config *pConfig;
126 char *zErr;
127 int rc;
128 int nPhrase; /* Size of apPhrase array */
129 Fts5ExprPhrase **apPhrase; /* Array of all phrases */
130 Fts5ExprNode *pExpr; /* Result of a successful parse */
131 };
132
sqlite3Fts5ParseError(Fts5Parse * pParse,const char * zFmt,...)133 void sqlite3Fts5ParseError(Fts5Parse *pParse, const char *zFmt, ...){
134 va_list ap;
135 va_start(ap, zFmt);
136 if( pParse->rc==SQLITE_OK ){
137 pParse->zErr = sqlite3_vmprintf(zFmt, ap);
138 pParse->rc = SQLITE_ERROR;
139 }
140 va_end(ap);
141 }
142
fts5ExprIsspace(char t)143 static int fts5ExprIsspace(char t){
144 return t==' ' || t=='\t' || t=='\n' || t=='\r';
145 }
146
147 /*
148 ** Read the first token from the nul-terminated string at *pz.
149 */
fts5ExprGetToken(Fts5Parse * pParse,const char ** pz,Fts5Token * pToken)150 static int fts5ExprGetToken(
151 Fts5Parse *pParse,
152 const char **pz, /* IN/OUT: Pointer into buffer */
153 Fts5Token *pToken
154 ){
155 const char *z = *pz;
156 int tok;
157
158 /* Skip past any whitespace */
159 while( fts5ExprIsspace(*z) ) z++;
160
161 pToken->p = z;
162 pToken->n = 1;
163 switch( *z ){
164 case '(': tok = FTS5_LP; break;
165 case ')': tok = FTS5_RP; break;
166 case '{': tok = FTS5_LCP; break;
167 case '}': tok = FTS5_RCP; break;
168 case ':': tok = FTS5_COLON; break;
169 case ',': tok = FTS5_COMMA; break;
170 case '+': tok = FTS5_PLUS; break;
171 case '*': tok = FTS5_STAR; break;
172 case '-': tok = FTS5_MINUS; break;
173 case '^': tok = FTS5_CARET; break;
174 case '\0': tok = FTS5_EOF; break;
175
176 case '"': {
177 const char *z2;
178 tok = FTS5_STRING;
179
180 for(z2=&z[1]; 1; z2++){
181 if( z2[0]=='"' ){
182 z2++;
183 if( z2[0]!='"' ) break;
184 }
185 if( z2[0]=='\0' ){
186 sqlite3Fts5ParseError(pParse, "unterminated string");
187 return FTS5_EOF;
188 }
189 }
190 pToken->n = (z2 - z);
191 break;
192 }
193
194 default: {
195 const char *z2;
196 if( sqlite3Fts5IsBareword(z[0])==0 ){
197 sqlite3Fts5ParseError(pParse, "fts5: syntax error near \"%.1s\"", z);
198 return FTS5_EOF;
199 }
200 tok = FTS5_STRING;
201 for(z2=&z[1]; sqlite3Fts5IsBareword(*z2); z2++);
202 pToken->n = (z2 - z);
203 if( pToken->n==2 && memcmp(pToken->p, "OR", 2)==0 ) tok = FTS5_OR;
204 if( pToken->n==3 && memcmp(pToken->p, "NOT", 3)==0 ) tok = FTS5_NOT;
205 if( pToken->n==3 && memcmp(pToken->p, "AND", 3)==0 ) tok = FTS5_AND;
206 break;
207 }
208 }
209
210 *pz = &pToken->p[pToken->n];
211 return tok;
212 }
213
fts5ParseAlloc(u64 t)214 static void *fts5ParseAlloc(u64 t){ return sqlite3_malloc64((sqlite3_int64)t);}
fts5ParseFree(void * p)215 static void fts5ParseFree(void *p){ sqlite3_free(p); }
216
sqlite3Fts5ExprNew(Fts5Config * pConfig,int iCol,const char * zExpr,Fts5Expr ** ppNew,char ** pzErr)217 int sqlite3Fts5ExprNew(
218 Fts5Config *pConfig, /* FTS5 Configuration */
219 int iCol,
220 const char *zExpr, /* Expression text */
221 Fts5Expr **ppNew,
222 char **pzErr
223 ){
224 Fts5Parse sParse;
225 Fts5Token token;
226 const char *z = zExpr;
227 int t; /* Next token type */
228 void *pEngine;
229 Fts5Expr *pNew;
230
231 *ppNew = 0;
232 *pzErr = 0;
233 memset(&sParse, 0, sizeof(sParse));
234 pEngine = sqlite3Fts5ParserAlloc(fts5ParseAlloc);
235 if( pEngine==0 ){ return SQLITE_NOMEM; }
236 sParse.pConfig = pConfig;
237
238 do {
239 t = fts5ExprGetToken(&sParse, &z, &token);
240 sqlite3Fts5Parser(pEngine, t, token, &sParse);
241 }while( sParse.rc==SQLITE_OK && t!=FTS5_EOF );
242 sqlite3Fts5ParserFree(pEngine, fts5ParseFree);
243
244 /* If the LHS of the MATCH expression was a user column, apply the
245 ** implicit column-filter. */
246 if( iCol<pConfig->nCol && sParse.pExpr && sParse.rc==SQLITE_OK ){
247 int n = sizeof(Fts5Colset);
248 Fts5Colset *pColset = (Fts5Colset*)sqlite3Fts5MallocZero(&sParse.rc, n);
249 if( pColset ){
250 pColset->nCol = 1;
251 pColset->aiCol[0] = iCol;
252 sqlite3Fts5ParseSetColset(&sParse, sParse.pExpr, pColset);
253 }
254 }
255
256 assert( sParse.rc!=SQLITE_OK || sParse.zErr==0 );
257 if( sParse.rc==SQLITE_OK ){
258 *ppNew = pNew = sqlite3_malloc(sizeof(Fts5Expr));
259 if( pNew==0 ){
260 sParse.rc = SQLITE_NOMEM;
261 sqlite3Fts5ParseNodeFree(sParse.pExpr);
262 }else{
263 if( !sParse.pExpr ){
264 const int nByte = sizeof(Fts5ExprNode);
265 pNew->pRoot = (Fts5ExprNode*)sqlite3Fts5MallocZero(&sParse.rc, nByte);
266 if( pNew->pRoot ){
267 pNew->pRoot->bEof = 1;
268 }
269 }else{
270 pNew->pRoot = sParse.pExpr;
271 }
272 pNew->pIndex = 0;
273 pNew->pConfig = pConfig;
274 pNew->apExprPhrase = sParse.apPhrase;
275 pNew->nPhrase = sParse.nPhrase;
276 sParse.apPhrase = 0;
277 }
278 }else{
279 sqlite3Fts5ParseNodeFree(sParse.pExpr);
280 }
281
282 sqlite3_free(sParse.apPhrase);
283 *pzErr = sParse.zErr;
284 return sParse.rc;
285 }
286
287 /*
288 ** Free the expression node object passed as the only argument.
289 */
sqlite3Fts5ParseNodeFree(Fts5ExprNode * p)290 void sqlite3Fts5ParseNodeFree(Fts5ExprNode *p){
291 if( p ){
292 int i;
293 for(i=0; i<p->nChild; i++){
294 sqlite3Fts5ParseNodeFree(p->apChild[i]);
295 }
296 sqlite3Fts5ParseNearsetFree(p->pNear);
297 sqlite3_free(p);
298 }
299 }
300
301 /*
302 ** Free the expression object passed as the only argument.
303 */
sqlite3Fts5ExprFree(Fts5Expr * p)304 void sqlite3Fts5ExprFree(Fts5Expr *p){
305 if( p ){
306 sqlite3Fts5ParseNodeFree(p->pRoot);
307 sqlite3_free(p->apExprPhrase);
308 sqlite3_free(p);
309 }
310 }
311
sqlite3Fts5ExprAnd(Fts5Expr ** pp1,Fts5Expr * p2)312 int sqlite3Fts5ExprAnd(Fts5Expr **pp1, Fts5Expr *p2){
313 Fts5Parse sParse;
314 memset(&sParse, 0, sizeof(sParse));
315
316 if( *pp1 ){
317 Fts5Expr *p1 = *pp1;
318 int nPhrase = p1->nPhrase + p2->nPhrase;
319
320 p1->pRoot = sqlite3Fts5ParseNode(&sParse, FTS5_AND, p1->pRoot, p2->pRoot,0);
321 p2->pRoot = 0;
322
323 if( sParse.rc==SQLITE_OK ){
324 Fts5ExprPhrase **ap = (Fts5ExprPhrase**)sqlite3_realloc(
325 p1->apExprPhrase, nPhrase * sizeof(Fts5ExprPhrase*)
326 );
327 if( ap==0 ){
328 sParse.rc = SQLITE_NOMEM;
329 }else{
330 int i;
331 memmove(&ap[p2->nPhrase], ap, p1->nPhrase*sizeof(Fts5ExprPhrase*));
332 for(i=0; i<p2->nPhrase; i++){
333 ap[i] = p2->apExprPhrase[i];
334 }
335 p1->nPhrase = nPhrase;
336 p1->apExprPhrase = ap;
337 }
338 }
339 sqlite3_free(p2->apExprPhrase);
340 sqlite3_free(p2);
341 }else{
342 *pp1 = p2;
343 }
344
345 return sParse.rc;
346 }
347
348 /*
349 ** Argument pTerm must be a synonym iterator. Return the current rowid
350 ** that it points to.
351 */
fts5ExprSynonymRowid(Fts5ExprTerm * pTerm,int bDesc,int * pbEof)352 static i64 fts5ExprSynonymRowid(Fts5ExprTerm *pTerm, int bDesc, int *pbEof){
353 i64 iRet = 0;
354 int bRetValid = 0;
355 Fts5ExprTerm *p;
356
357 assert( pTerm->pSynonym );
358 assert( bDesc==0 || bDesc==1 );
359 for(p=pTerm; p; p=p->pSynonym){
360 if( 0==sqlite3Fts5IterEof(p->pIter) ){
361 i64 iRowid = p->pIter->iRowid;
362 if( bRetValid==0 || (bDesc!=(iRowid<iRet)) ){
363 iRet = iRowid;
364 bRetValid = 1;
365 }
366 }
367 }
368
369 if( pbEof && bRetValid==0 ) *pbEof = 1;
370 return iRet;
371 }
372
373 /*
374 ** Argument pTerm must be a synonym iterator.
375 */
fts5ExprSynonymList(Fts5ExprTerm * pTerm,i64 iRowid,Fts5Buffer * pBuf,u8 ** pa,int * pn)376 static int fts5ExprSynonymList(
377 Fts5ExprTerm *pTerm,
378 i64 iRowid,
379 Fts5Buffer *pBuf, /* Use this buffer for space if required */
380 u8 **pa, int *pn
381 ){
382 Fts5PoslistReader aStatic[4];
383 Fts5PoslistReader *aIter = aStatic;
384 int nIter = 0;
385 int nAlloc = 4;
386 int rc = SQLITE_OK;
387 Fts5ExprTerm *p;
388
389 assert( pTerm->pSynonym );
390 for(p=pTerm; p; p=p->pSynonym){
391 Fts5IndexIter *pIter = p->pIter;
392 if( sqlite3Fts5IterEof(pIter)==0 && pIter->iRowid==iRowid ){
393 if( pIter->nData==0 ) continue;
394 if( nIter==nAlloc ){
395 sqlite3_int64 nByte = sizeof(Fts5PoslistReader) * nAlloc * 2;
396 Fts5PoslistReader *aNew = (Fts5PoslistReader*)sqlite3_malloc64(nByte);
397 if( aNew==0 ){
398 rc = SQLITE_NOMEM;
399 goto synonym_poslist_out;
400 }
401 memcpy(aNew, aIter, sizeof(Fts5PoslistReader) * nIter);
402 nAlloc = nAlloc*2;
403 if( aIter!=aStatic ) sqlite3_free(aIter);
404 aIter = aNew;
405 }
406 sqlite3Fts5PoslistReaderInit(pIter->pData, pIter->nData, &aIter[nIter]);
407 assert( aIter[nIter].bEof==0 );
408 nIter++;
409 }
410 }
411
412 if( nIter==1 ){
413 *pa = (u8*)aIter[0].a;
414 *pn = aIter[0].n;
415 }else{
416 Fts5PoslistWriter writer = {0};
417 i64 iPrev = -1;
418 fts5BufferZero(pBuf);
419 while( 1 ){
420 int i;
421 i64 iMin = FTS5_LARGEST_INT64;
422 for(i=0; i<nIter; i++){
423 if( aIter[i].bEof==0 ){
424 if( aIter[i].iPos==iPrev ){
425 if( sqlite3Fts5PoslistReaderNext(&aIter[i]) ) continue;
426 }
427 if( aIter[i].iPos<iMin ){
428 iMin = aIter[i].iPos;
429 }
430 }
431 }
432 if( iMin==FTS5_LARGEST_INT64 || rc!=SQLITE_OK ) break;
433 rc = sqlite3Fts5PoslistWriterAppend(pBuf, &writer, iMin);
434 iPrev = iMin;
435 }
436 if( rc==SQLITE_OK ){
437 *pa = pBuf->p;
438 *pn = pBuf->n;
439 }
440 }
441
442 synonym_poslist_out:
443 if( aIter!=aStatic ) sqlite3_free(aIter);
444 return rc;
445 }
446
447
448 /*
449 ** All individual term iterators in pPhrase are guaranteed to be valid and
450 ** pointing to the same rowid when this function is called. This function
451 ** checks if the current rowid really is a match, and if so populates
452 ** the pPhrase->poslist buffer accordingly. Output parameter *pbMatch
453 ** is set to true if this is really a match, or false otherwise.
454 **
455 ** SQLITE_OK is returned if an error occurs, or an SQLite error code
456 ** otherwise. It is not considered an error code if the current rowid is
457 ** not a match.
458 */
fts5ExprPhraseIsMatch(Fts5ExprNode * pNode,Fts5ExprPhrase * pPhrase,int * pbMatch)459 static int fts5ExprPhraseIsMatch(
460 Fts5ExprNode *pNode, /* Node pPhrase belongs to */
461 Fts5ExprPhrase *pPhrase, /* Phrase object to initialize */
462 int *pbMatch /* OUT: Set to true if really a match */
463 ){
464 Fts5PoslistWriter writer = {0};
465 Fts5PoslistReader aStatic[4];
466 Fts5PoslistReader *aIter = aStatic;
467 int i;
468 int rc = SQLITE_OK;
469 int bFirst = pPhrase->aTerm[0].bFirst;
470
471 fts5BufferZero(&pPhrase->poslist);
472
473 /* If the aStatic[] array is not large enough, allocate a large array
474 ** using sqlite3_malloc(). This approach could be improved upon. */
475 if( pPhrase->nTerm>ArraySize(aStatic) ){
476 sqlite3_int64 nByte = sizeof(Fts5PoslistReader) * pPhrase->nTerm;
477 aIter = (Fts5PoslistReader*)sqlite3_malloc64(nByte);
478 if( !aIter ) return SQLITE_NOMEM;
479 }
480 memset(aIter, 0, sizeof(Fts5PoslistReader) * pPhrase->nTerm);
481
482 /* Initialize a term iterator for each term in the phrase */
483 for(i=0; i<pPhrase->nTerm; i++){
484 Fts5ExprTerm *pTerm = &pPhrase->aTerm[i];
485 int n = 0;
486 int bFlag = 0;
487 u8 *a = 0;
488 if( pTerm->pSynonym ){
489 Fts5Buffer buf = {0, 0, 0};
490 rc = fts5ExprSynonymList(pTerm, pNode->iRowid, &buf, &a, &n);
491 if( rc ){
492 sqlite3_free(a);
493 goto ismatch_out;
494 }
495 if( a==buf.p ) bFlag = 1;
496 }else{
497 a = (u8*)pTerm->pIter->pData;
498 n = pTerm->pIter->nData;
499 }
500 sqlite3Fts5PoslistReaderInit(a, n, &aIter[i]);
501 aIter[i].bFlag = (u8)bFlag;
502 if( aIter[i].bEof ) goto ismatch_out;
503 }
504
505 while( 1 ){
506 int bMatch;
507 i64 iPos = aIter[0].iPos;
508 do {
509 bMatch = 1;
510 for(i=0; i<pPhrase->nTerm; i++){
511 Fts5PoslistReader *pPos = &aIter[i];
512 i64 iAdj = iPos + i;
513 if( pPos->iPos!=iAdj ){
514 bMatch = 0;
515 while( pPos->iPos<iAdj ){
516 if( sqlite3Fts5PoslistReaderNext(pPos) ) goto ismatch_out;
517 }
518 if( pPos->iPos>iAdj ) iPos = pPos->iPos-i;
519 }
520 }
521 }while( bMatch==0 );
522
523 /* Append position iPos to the output */
524 if( bFirst==0 || FTS5_POS2OFFSET(iPos)==0 ){
525 rc = sqlite3Fts5PoslistWriterAppend(&pPhrase->poslist, &writer, iPos);
526 if( rc!=SQLITE_OK ) goto ismatch_out;
527 }
528
529 for(i=0; i<pPhrase->nTerm; i++){
530 if( sqlite3Fts5PoslistReaderNext(&aIter[i]) ) goto ismatch_out;
531 }
532 }
533
534 ismatch_out:
535 *pbMatch = (pPhrase->poslist.n>0);
536 for(i=0; i<pPhrase->nTerm; i++){
537 if( aIter[i].bFlag ) sqlite3_free((u8*)aIter[i].a);
538 }
539 if( aIter!=aStatic ) sqlite3_free(aIter);
540 return rc;
541 }
542
543 typedef struct Fts5LookaheadReader Fts5LookaheadReader;
544 struct Fts5LookaheadReader {
545 const u8 *a; /* Buffer containing position list */
546 int n; /* Size of buffer a[] in bytes */
547 int i; /* Current offset in position list */
548 i64 iPos; /* Current position */
549 i64 iLookahead; /* Next position */
550 };
551
552 #define FTS5_LOOKAHEAD_EOF (((i64)1) << 62)
553
fts5LookaheadReaderNext(Fts5LookaheadReader * p)554 static int fts5LookaheadReaderNext(Fts5LookaheadReader *p){
555 p->iPos = p->iLookahead;
556 if( sqlite3Fts5PoslistNext64(p->a, p->n, &p->i, &p->iLookahead) ){
557 p->iLookahead = FTS5_LOOKAHEAD_EOF;
558 }
559 return (p->iPos==FTS5_LOOKAHEAD_EOF);
560 }
561
fts5LookaheadReaderInit(const u8 * a,int n,Fts5LookaheadReader * p)562 static int fts5LookaheadReaderInit(
563 const u8 *a, int n, /* Buffer to read position list from */
564 Fts5LookaheadReader *p /* Iterator object to initialize */
565 ){
566 memset(p, 0, sizeof(Fts5LookaheadReader));
567 p->a = a;
568 p->n = n;
569 fts5LookaheadReaderNext(p);
570 return fts5LookaheadReaderNext(p);
571 }
572
573 typedef struct Fts5NearTrimmer Fts5NearTrimmer;
574 struct Fts5NearTrimmer {
575 Fts5LookaheadReader reader; /* Input iterator */
576 Fts5PoslistWriter writer; /* Writer context */
577 Fts5Buffer *pOut; /* Output poslist */
578 };
579
580 /*
581 ** The near-set object passed as the first argument contains more than
582 ** one phrase. All phrases currently point to the same row. The
583 ** Fts5ExprPhrase.poslist buffers are populated accordingly. This function
584 ** tests if the current row contains instances of each phrase sufficiently
585 ** close together to meet the NEAR constraint. Non-zero is returned if it
586 ** does, or zero otherwise.
587 **
588 ** If in/out parameter (*pRc) is set to other than SQLITE_OK when this
589 ** function is called, it is a no-op. Or, if an error (e.g. SQLITE_NOMEM)
590 ** occurs within this function (*pRc) is set accordingly before returning.
591 ** The return value is undefined in both these cases.
592 **
593 ** If no error occurs and non-zero (a match) is returned, the position-list
594 ** of each phrase object is edited to contain only those entries that
595 ** meet the constraint before returning.
596 */
fts5ExprNearIsMatch(int * pRc,Fts5ExprNearset * pNear)597 static int fts5ExprNearIsMatch(int *pRc, Fts5ExprNearset *pNear){
598 Fts5NearTrimmer aStatic[4];
599 Fts5NearTrimmer *a = aStatic;
600 Fts5ExprPhrase **apPhrase = pNear->apPhrase;
601
602 int i;
603 int rc = *pRc;
604 int bMatch;
605
606 assert( pNear->nPhrase>1 );
607
608 /* If the aStatic[] array is not large enough, allocate a large array
609 ** using sqlite3_malloc(). This approach could be improved upon. */
610 if( pNear->nPhrase>ArraySize(aStatic) ){
611 sqlite3_int64 nByte = sizeof(Fts5NearTrimmer) * pNear->nPhrase;
612 a = (Fts5NearTrimmer*)sqlite3Fts5MallocZero(&rc, nByte);
613 }else{
614 memset(aStatic, 0, sizeof(aStatic));
615 }
616 if( rc!=SQLITE_OK ){
617 *pRc = rc;
618 return 0;
619 }
620
621 /* Initialize a lookahead iterator for each phrase. After passing the
622 ** buffer and buffer size to the lookaside-reader init function, zero
623 ** the phrase poslist buffer. The new poslist for the phrase (containing
624 ** the same entries as the original with some entries removed on account
625 ** of the NEAR constraint) is written over the original even as it is
626 ** being read. This is safe as the entries for the new poslist are a
627 ** subset of the old, so it is not possible for data yet to be read to
628 ** be overwritten. */
629 for(i=0; i<pNear->nPhrase; i++){
630 Fts5Buffer *pPoslist = &apPhrase[i]->poslist;
631 fts5LookaheadReaderInit(pPoslist->p, pPoslist->n, &a[i].reader);
632 pPoslist->n = 0;
633 a[i].pOut = pPoslist;
634 }
635
636 while( 1 ){
637 int iAdv;
638 i64 iMin;
639 i64 iMax;
640
641 /* This block advances the phrase iterators until they point to a set of
642 ** entries that together comprise a match. */
643 iMax = a[0].reader.iPos;
644 do {
645 bMatch = 1;
646 for(i=0; i<pNear->nPhrase; i++){
647 Fts5LookaheadReader *pPos = &a[i].reader;
648 iMin = iMax - pNear->apPhrase[i]->nTerm - pNear->nNear;
649 if( pPos->iPos<iMin || pPos->iPos>iMax ){
650 bMatch = 0;
651 while( pPos->iPos<iMin ){
652 if( fts5LookaheadReaderNext(pPos) ) goto ismatch_out;
653 }
654 if( pPos->iPos>iMax ) iMax = pPos->iPos;
655 }
656 }
657 }while( bMatch==0 );
658
659 /* Add an entry to each output position list */
660 for(i=0; i<pNear->nPhrase; i++){
661 i64 iPos = a[i].reader.iPos;
662 Fts5PoslistWriter *pWriter = &a[i].writer;
663 if( a[i].pOut->n==0 || iPos!=pWriter->iPrev ){
664 sqlite3Fts5PoslistWriterAppend(a[i].pOut, pWriter, iPos);
665 }
666 }
667
668 iAdv = 0;
669 iMin = a[0].reader.iLookahead;
670 for(i=0; i<pNear->nPhrase; i++){
671 if( a[i].reader.iLookahead < iMin ){
672 iMin = a[i].reader.iLookahead;
673 iAdv = i;
674 }
675 }
676 if( fts5LookaheadReaderNext(&a[iAdv].reader) ) goto ismatch_out;
677 }
678
679 ismatch_out: {
680 int bRet = a[0].pOut->n>0;
681 *pRc = rc;
682 if( a!=aStatic ) sqlite3_free(a);
683 return bRet;
684 }
685 }
686
687 /*
688 ** Advance iterator pIter until it points to a value equal to or laster
689 ** than the initial value of *piLast. If this means the iterator points
690 ** to a value laster than *piLast, update *piLast to the new lastest value.
691 **
692 ** If the iterator reaches EOF, set *pbEof to true before returning. If
693 ** an error occurs, set *pRc to an error code. If either *pbEof or *pRc
694 ** are set, return a non-zero value. Otherwise, return zero.
695 */
fts5ExprAdvanceto(Fts5IndexIter * pIter,int bDesc,i64 * piLast,int * pRc,int * pbEof)696 static int fts5ExprAdvanceto(
697 Fts5IndexIter *pIter, /* Iterator to advance */
698 int bDesc, /* True if iterator is "rowid DESC" */
699 i64 *piLast, /* IN/OUT: Lastest rowid seen so far */
700 int *pRc, /* OUT: Error code */
701 int *pbEof /* OUT: Set to true if EOF */
702 ){
703 i64 iLast = *piLast;
704 i64 iRowid;
705
706 iRowid = pIter->iRowid;
707 if( (bDesc==0 && iLast>iRowid) || (bDesc && iLast<iRowid) ){
708 int rc = sqlite3Fts5IterNextFrom(pIter, iLast);
709 if( rc || sqlite3Fts5IterEof(pIter) ){
710 *pRc = rc;
711 *pbEof = 1;
712 return 1;
713 }
714 iRowid = pIter->iRowid;
715 assert( (bDesc==0 && iRowid>=iLast) || (bDesc==1 && iRowid<=iLast) );
716 }
717 *piLast = iRowid;
718
719 return 0;
720 }
721
fts5ExprSynonymAdvanceto(Fts5ExprTerm * pTerm,int bDesc,i64 * piLast,int * pRc)722 static int fts5ExprSynonymAdvanceto(
723 Fts5ExprTerm *pTerm, /* Term iterator to advance */
724 int bDesc, /* True if iterator is "rowid DESC" */
725 i64 *piLast, /* IN/OUT: Lastest rowid seen so far */
726 int *pRc /* OUT: Error code */
727 ){
728 int rc = SQLITE_OK;
729 i64 iLast = *piLast;
730 Fts5ExprTerm *p;
731 int bEof = 0;
732
733 for(p=pTerm; rc==SQLITE_OK && p; p=p->pSynonym){
734 if( sqlite3Fts5IterEof(p->pIter)==0 ){
735 i64 iRowid = p->pIter->iRowid;
736 if( (bDesc==0 && iLast>iRowid) || (bDesc && iLast<iRowid) ){
737 rc = sqlite3Fts5IterNextFrom(p->pIter, iLast);
738 }
739 }
740 }
741
742 if( rc!=SQLITE_OK ){
743 *pRc = rc;
744 bEof = 1;
745 }else{
746 *piLast = fts5ExprSynonymRowid(pTerm, bDesc, &bEof);
747 }
748 return bEof;
749 }
750
751
fts5ExprNearTest(int * pRc,Fts5Expr * pExpr,Fts5ExprNode * pNode)752 static int fts5ExprNearTest(
753 int *pRc,
754 Fts5Expr *pExpr, /* Expression that pNear is a part of */
755 Fts5ExprNode *pNode /* The "NEAR" node (FTS5_STRING) */
756 ){
757 Fts5ExprNearset *pNear = pNode->pNear;
758 int rc = *pRc;
759
760 if( pExpr->pConfig->eDetail!=FTS5_DETAIL_FULL ){
761 Fts5ExprTerm *pTerm;
762 Fts5ExprPhrase *pPhrase = pNear->apPhrase[0];
763 pPhrase->poslist.n = 0;
764 for(pTerm=&pPhrase->aTerm[0]; pTerm; pTerm=pTerm->pSynonym){
765 Fts5IndexIter *pIter = pTerm->pIter;
766 if( sqlite3Fts5IterEof(pIter)==0 ){
767 if( pIter->iRowid==pNode->iRowid && pIter->nData>0 ){
768 pPhrase->poslist.n = 1;
769 }
770 }
771 }
772 return pPhrase->poslist.n;
773 }else{
774 int i;
775
776 /* Check that each phrase in the nearset matches the current row.
777 ** Populate the pPhrase->poslist buffers at the same time. If any
778 ** phrase is not a match, break out of the loop early. */
779 for(i=0; rc==SQLITE_OK && i<pNear->nPhrase; i++){
780 Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
781 if( pPhrase->nTerm>1 || pPhrase->aTerm[0].pSynonym
782 || pNear->pColset || pPhrase->aTerm[0].bFirst
783 ){
784 int bMatch = 0;
785 rc = fts5ExprPhraseIsMatch(pNode, pPhrase, &bMatch);
786 if( bMatch==0 ) break;
787 }else{
788 Fts5IndexIter *pIter = pPhrase->aTerm[0].pIter;
789 fts5BufferSet(&rc, &pPhrase->poslist, pIter->nData, pIter->pData);
790 }
791 }
792
793 *pRc = rc;
794 if( i==pNear->nPhrase && (i==1 || fts5ExprNearIsMatch(pRc, pNear)) ){
795 return 1;
796 }
797 return 0;
798 }
799 }
800
801
802 /*
803 ** Initialize all term iterators in the pNear object. If any term is found
804 ** to match no documents at all, return immediately without initializing any
805 ** further iterators.
806 **
807 ** If an error occurs, return an SQLite error code. Otherwise, return
808 ** SQLITE_OK. It is not considered an error if some term matches zero
809 ** documents.
810 */
fts5ExprNearInitAll(Fts5Expr * pExpr,Fts5ExprNode * pNode)811 static int fts5ExprNearInitAll(
812 Fts5Expr *pExpr,
813 Fts5ExprNode *pNode
814 ){
815 Fts5ExprNearset *pNear = pNode->pNear;
816 int i;
817
818 assert( pNode->bNomatch==0 );
819 for(i=0; i<pNear->nPhrase; i++){
820 Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
821 if( pPhrase->nTerm==0 ){
822 pNode->bEof = 1;
823 return SQLITE_OK;
824 }else{
825 int j;
826 for(j=0; j<pPhrase->nTerm; j++){
827 Fts5ExprTerm *pTerm = &pPhrase->aTerm[j];
828 Fts5ExprTerm *p;
829 int bHit = 0;
830
831 for(p=pTerm; p; p=p->pSynonym){
832 int rc;
833 if( p->pIter ){
834 sqlite3Fts5IterClose(p->pIter);
835 p->pIter = 0;
836 }
837 rc = sqlite3Fts5IndexQuery(
838 pExpr->pIndex, p->zTerm, (int)strlen(p->zTerm),
839 (pTerm->bPrefix ? FTS5INDEX_QUERY_PREFIX : 0) |
840 (pExpr->bDesc ? FTS5INDEX_QUERY_DESC : 0),
841 pNear->pColset,
842 &p->pIter
843 );
844 assert( (rc==SQLITE_OK)==(p->pIter!=0) );
845 if( rc!=SQLITE_OK ) return rc;
846 if( 0==sqlite3Fts5IterEof(p->pIter) ){
847 bHit = 1;
848 }
849 }
850
851 if( bHit==0 ){
852 pNode->bEof = 1;
853 return SQLITE_OK;
854 }
855 }
856 }
857 }
858
859 pNode->bEof = 0;
860 return SQLITE_OK;
861 }
862
863 /*
864 ** If pExpr is an ASC iterator, this function returns a value with the
865 ** same sign as:
866 **
867 ** (iLhs - iRhs)
868 **
869 ** Otherwise, if this is a DESC iterator, the opposite is returned:
870 **
871 ** (iRhs - iLhs)
872 */
fts5RowidCmp(Fts5Expr * pExpr,i64 iLhs,i64 iRhs)873 static int fts5RowidCmp(
874 Fts5Expr *pExpr,
875 i64 iLhs,
876 i64 iRhs
877 ){
878 assert( pExpr->bDesc==0 || pExpr->bDesc==1 );
879 if( pExpr->bDesc==0 ){
880 if( iLhs<iRhs ) return -1;
881 return (iLhs > iRhs);
882 }else{
883 if( iLhs>iRhs ) return -1;
884 return (iLhs < iRhs);
885 }
886 }
887
fts5ExprSetEof(Fts5ExprNode * pNode)888 static void fts5ExprSetEof(Fts5ExprNode *pNode){
889 int i;
890 pNode->bEof = 1;
891 pNode->bNomatch = 0;
892 for(i=0; i<pNode->nChild; i++){
893 fts5ExprSetEof(pNode->apChild[i]);
894 }
895 }
896
fts5ExprNodeZeroPoslist(Fts5ExprNode * pNode)897 static void fts5ExprNodeZeroPoslist(Fts5ExprNode *pNode){
898 if( pNode->eType==FTS5_STRING || pNode->eType==FTS5_TERM ){
899 Fts5ExprNearset *pNear = pNode->pNear;
900 int i;
901 for(i=0; i<pNear->nPhrase; i++){
902 Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
903 pPhrase->poslist.n = 0;
904 }
905 }else{
906 int i;
907 for(i=0; i<pNode->nChild; i++){
908 fts5ExprNodeZeroPoslist(pNode->apChild[i]);
909 }
910 }
911 }
912
913
914
915 /*
916 ** Compare the values currently indicated by the two nodes as follows:
917 **
918 ** res = (*p1) - (*p2)
919 **
920 ** Nodes that point to values that come later in the iteration order are
921 ** considered to be larger. Nodes at EOF are the largest of all.
922 **
923 ** This means that if the iteration order is ASC, then numerically larger
924 ** rowids are considered larger. Or if it is the default DESC, numerically
925 ** smaller rowids are larger.
926 */
fts5NodeCompare(Fts5Expr * pExpr,Fts5ExprNode * p1,Fts5ExprNode * p2)927 static int fts5NodeCompare(
928 Fts5Expr *pExpr,
929 Fts5ExprNode *p1,
930 Fts5ExprNode *p2
931 ){
932 if( p2->bEof ) return -1;
933 if( p1->bEof ) return +1;
934 return fts5RowidCmp(pExpr, p1->iRowid, p2->iRowid);
935 }
936
937 /*
938 ** All individual term iterators in pNear are guaranteed to be valid when
939 ** this function is called. This function checks if all term iterators
940 ** point to the same rowid, and if not, advances them until they do.
941 ** If an EOF is reached before this happens, *pbEof is set to true before
942 ** returning.
943 **
944 ** SQLITE_OK is returned if an error occurs, or an SQLite error code
945 ** otherwise. It is not considered an error code if an iterator reaches
946 ** EOF.
947 */
fts5ExprNodeTest_STRING(Fts5Expr * pExpr,Fts5ExprNode * pNode)948 static int fts5ExprNodeTest_STRING(
949 Fts5Expr *pExpr, /* Expression pPhrase belongs to */
950 Fts5ExprNode *pNode
951 ){
952 Fts5ExprNearset *pNear = pNode->pNear;
953 Fts5ExprPhrase *pLeft = pNear->apPhrase[0];
954 int rc = SQLITE_OK;
955 i64 iLast; /* Lastest rowid any iterator points to */
956 int i, j; /* Phrase and token index, respectively */
957 int bMatch; /* True if all terms are at the same rowid */
958 const int bDesc = pExpr->bDesc;
959
960 /* Check that this node should not be FTS5_TERM */
961 assert( pNear->nPhrase>1
962 || pNear->apPhrase[0]->nTerm>1
963 || pNear->apPhrase[0]->aTerm[0].pSynonym
964 || pNear->apPhrase[0]->aTerm[0].bFirst
965 );
966
967 /* Initialize iLast, the "lastest" rowid any iterator points to. If the
968 ** iterator skips through rowids in the default ascending order, this means
969 ** the maximum rowid. Or, if the iterator is "ORDER BY rowid DESC", then it
970 ** means the minimum rowid. */
971 if( pLeft->aTerm[0].pSynonym ){
972 iLast = fts5ExprSynonymRowid(&pLeft->aTerm[0], bDesc, 0);
973 }else{
974 iLast = pLeft->aTerm[0].pIter->iRowid;
975 }
976
977 do {
978 bMatch = 1;
979 for(i=0; i<pNear->nPhrase; i++){
980 Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
981 for(j=0; j<pPhrase->nTerm; j++){
982 Fts5ExprTerm *pTerm = &pPhrase->aTerm[j];
983 if( pTerm->pSynonym ){
984 i64 iRowid = fts5ExprSynonymRowid(pTerm, bDesc, 0);
985 if( iRowid==iLast ) continue;
986 bMatch = 0;
987 if( fts5ExprSynonymAdvanceto(pTerm, bDesc, &iLast, &rc) ){
988 pNode->bNomatch = 0;
989 pNode->bEof = 1;
990 return rc;
991 }
992 }else{
993 Fts5IndexIter *pIter = pPhrase->aTerm[j].pIter;
994 if( pIter->iRowid==iLast || pIter->bEof ) continue;
995 bMatch = 0;
996 if( fts5ExprAdvanceto(pIter, bDesc, &iLast, &rc, &pNode->bEof) ){
997 return rc;
998 }
999 }
1000 }
1001 }
1002 }while( bMatch==0 );
1003
1004 pNode->iRowid = iLast;
1005 pNode->bNomatch = ((0==fts5ExprNearTest(&rc, pExpr, pNode)) && rc==SQLITE_OK);
1006 assert( pNode->bEof==0 || pNode->bNomatch==0 );
1007
1008 return rc;
1009 }
1010
1011 /*
1012 ** Advance the first term iterator in the first phrase of pNear. Set output
1013 ** variable *pbEof to true if it reaches EOF or if an error occurs.
1014 **
1015 ** Return SQLITE_OK if successful, or an SQLite error code if an error
1016 ** occurs.
1017 */
fts5ExprNodeNext_STRING(Fts5Expr * pExpr,Fts5ExprNode * pNode,int bFromValid,i64 iFrom)1018 static int fts5ExprNodeNext_STRING(
1019 Fts5Expr *pExpr, /* Expression pPhrase belongs to */
1020 Fts5ExprNode *pNode, /* FTS5_STRING or FTS5_TERM node */
1021 int bFromValid,
1022 i64 iFrom
1023 ){
1024 Fts5ExprTerm *pTerm = &pNode->pNear->apPhrase[0]->aTerm[0];
1025 int rc = SQLITE_OK;
1026
1027 pNode->bNomatch = 0;
1028 if( pTerm->pSynonym ){
1029 int bEof = 1;
1030 Fts5ExprTerm *p;
1031
1032 /* Find the firstest rowid any synonym points to. */
1033 i64 iRowid = fts5ExprSynonymRowid(pTerm, pExpr->bDesc, 0);
1034
1035 /* Advance each iterator that currently points to iRowid. Or, if iFrom
1036 ** is valid - each iterator that points to a rowid before iFrom. */
1037 for(p=pTerm; p; p=p->pSynonym){
1038 if( sqlite3Fts5IterEof(p->pIter)==0 ){
1039 i64 ii = p->pIter->iRowid;
1040 if( ii==iRowid
1041 || (bFromValid && ii!=iFrom && (ii>iFrom)==pExpr->bDesc)
1042 ){
1043 if( bFromValid ){
1044 rc = sqlite3Fts5IterNextFrom(p->pIter, iFrom);
1045 }else{
1046 rc = sqlite3Fts5IterNext(p->pIter);
1047 }
1048 if( rc!=SQLITE_OK ) break;
1049 if( sqlite3Fts5IterEof(p->pIter)==0 ){
1050 bEof = 0;
1051 }
1052 }else{
1053 bEof = 0;
1054 }
1055 }
1056 }
1057
1058 /* Set the EOF flag if either all synonym iterators are at EOF or an
1059 ** error has occurred. */
1060 pNode->bEof = (rc || bEof);
1061 }else{
1062 Fts5IndexIter *pIter = pTerm->pIter;
1063
1064 assert( Fts5NodeIsString(pNode) );
1065 if( bFromValid ){
1066 rc = sqlite3Fts5IterNextFrom(pIter, iFrom);
1067 }else{
1068 rc = sqlite3Fts5IterNext(pIter);
1069 }
1070
1071 pNode->bEof = (rc || sqlite3Fts5IterEof(pIter));
1072 }
1073
1074 if( pNode->bEof==0 ){
1075 assert( rc==SQLITE_OK );
1076 rc = fts5ExprNodeTest_STRING(pExpr, pNode);
1077 }
1078
1079 return rc;
1080 }
1081
1082
fts5ExprNodeTest_TERM(Fts5Expr * pExpr,Fts5ExprNode * pNode)1083 static int fts5ExprNodeTest_TERM(
1084 Fts5Expr *pExpr, /* Expression that pNear is a part of */
1085 Fts5ExprNode *pNode /* The "NEAR" node (FTS5_TERM) */
1086 ){
1087 /* As this "NEAR" object is actually a single phrase that consists
1088 ** of a single term only, grab pointers into the poslist managed by the
1089 ** fts5_index.c iterator object. This is much faster than synthesizing
1090 ** a new poslist the way we have to for more complicated phrase or NEAR
1091 ** expressions. */
1092 Fts5ExprPhrase *pPhrase = pNode->pNear->apPhrase[0];
1093 Fts5IndexIter *pIter = pPhrase->aTerm[0].pIter;
1094
1095 assert( pNode->eType==FTS5_TERM );
1096 assert( pNode->pNear->nPhrase==1 && pPhrase->nTerm==1 );
1097 assert( pPhrase->aTerm[0].pSynonym==0 );
1098
1099 pPhrase->poslist.n = pIter->nData;
1100 if( pExpr->pConfig->eDetail==FTS5_DETAIL_FULL ){
1101 pPhrase->poslist.p = (u8*)pIter->pData;
1102 }
1103 pNode->iRowid = pIter->iRowid;
1104 pNode->bNomatch = (pPhrase->poslist.n==0);
1105 return SQLITE_OK;
1106 }
1107
1108 /*
1109 ** xNext() method for a node of type FTS5_TERM.
1110 */
fts5ExprNodeNext_TERM(Fts5Expr * pExpr,Fts5ExprNode * pNode,int bFromValid,i64 iFrom)1111 static int fts5ExprNodeNext_TERM(
1112 Fts5Expr *pExpr,
1113 Fts5ExprNode *pNode,
1114 int bFromValid,
1115 i64 iFrom
1116 ){
1117 int rc;
1118 Fts5IndexIter *pIter = pNode->pNear->apPhrase[0]->aTerm[0].pIter;
1119
1120 assert( pNode->bEof==0 );
1121 if( bFromValid ){
1122 rc = sqlite3Fts5IterNextFrom(pIter, iFrom);
1123 }else{
1124 rc = sqlite3Fts5IterNext(pIter);
1125 }
1126 if( rc==SQLITE_OK && sqlite3Fts5IterEof(pIter)==0 ){
1127 rc = fts5ExprNodeTest_TERM(pExpr, pNode);
1128 }else{
1129 pNode->bEof = 1;
1130 pNode->bNomatch = 0;
1131 }
1132 return rc;
1133 }
1134
fts5ExprNodeTest_OR(Fts5Expr * pExpr,Fts5ExprNode * pNode)1135 static void fts5ExprNodeTest_OR(
1136 Fts5Expr *pExpr, /* Expression of which pNode is a part */
1137 Fts5ExprNode *pNode /* Expression node to test */
1138 ){
1139 Fts5ExprNode *pNext = pNode->apChild[0];
1140 int i;
1141
1142 for(i=1; i<pNode->nChild; i++){
1143 Fts5ExprNode *pChild = pNode->apChild[i];
1144 int cmp = fts5NodeCompare(pExpr, pNext, pChild);
1145 if( cmp>0 || (cmp==0 && pChild->bNomatch==0) ){
1146 pNext = pChild;
1147 }
1148 }
1149 pNode->iRowid = pNext->iRowid;
1150 pNode->bEof = pNext->bEof;
1151 pNode->bNomatch = pNext->bNomatch;
1152 }
1153
fts5ExprNodeNext_OR(Fts5Expr * pExpr,Fts5ExprNode * pNode,int bFromValid,i64 iFrom)1154 static int fts5ExprNodeNext_OR(
1155 Fts5Expr *pExpr,
1156 Fts5ExprNode *pNode,
1157 int bFromValid,
1158 i64 iFrom
1159 ){
1160 int i;
1161 i64 iLast = pNode->iRowid;
1162
1163 for(i=0; i<pNode->nChild; i++){
1164 Fts5ExprNode *p1 = pNode->apChild[i];
1165 assert( p1->bEof || fts5RowidCmp(pExpr, p1->iRowid, iLast)>=0 );
1166 if( p1->bEof==0 ){
1167 if( (p1->iRowid==iLast)
1168 || (bFromValid && fts5RowidCmp(pExpr, p1->iRowid, iFrom)<0)
1169 ){
1170 int rc = fts5ExprNodeNext(pExpr, p1, bFromValid, iFrom);
1171 if( rc!=SQLITE_OK ){
1172 pNode->bNomatch = 0;
1173 return rc;
1174 }
1175 }
1176 }
1177 }
1178
1179 fts5ExprNodeTest_OR(pExpr, pNode);
1180 return SQLITE_OK;
1181 }
1182
1183 /*
1184 ** Argument pNode is an FTS5_AND node.
1185 */
fts5ExprNodeTest_AND(Fts5Expr * pExpr,Fts5ExprNode * pAnd)1186 static int fts5ExprNodeTest_AND(
1187 Fts5Expr *pExpr, /* Expression pPhrase belongs to */
1188 Fts5ExprNode *pAnd /* FTS5_AND node to advance */
1189 ){
1190 int iChild;
1191 i64 iLast = pAnd->iRowid;
1192 int rc = SQLITE_OK;
1193 int bMatch;
1194
1195 assert( pAnd->bEof==0 );
1196 do {
1197 pAnd->bNomatch = 0;
1198 bMatch = 1;
1199 for(iChild=0; iChild<pAnd->nChild; iChild++){
1200 Fts5ExprNode *pChild = pAnd->apChild[iChild];
1201 int cmp = fts5RowidCmp(pExpr, iLast, pChild->iRowid);
1202 if( cmp>0 ){
1203 /* Advance pChild until it points to iLast or laster */
1204 rc = fts5ExprNodeNext(pExpr, pChild, 1, iLast);
1205 if( rc!=SQLITE_OK ){
1206 pAnd->bNomatch = 0;
1207 return rc;
1208 }
1209 }
1210
1211 /* If the child node is now at EOF, so is the parent AND node. Otherwise,
1212 ** the child node is guaranteed to have advanced at least as far as
1213 ** rowid iLast. So if it is not at exactly iLast, pChild->iRowid is the
1214 ** new lastest rowid seen so far. */
1215 assert( pChild->bEof || fts5RowidCmp(pExpr, iLast, pChild->iRowid)<=0 );
1216 if( pChild->bEof ){
1217 fts5ExprSetEof(pAnd);
1218 bMatch = 1;
1219 break;
1220 }else if( iLast!=pChild->iRowid ){
1221 bMatch = 0;
1222 iLast = pChild->iRowid;
1223 }
1224
1225 if( pChild->bNomatch ){
1226 pAnd->bNomatch = 1;
1227 }
1228 }
1229 }while( bMatch==0 );
1230
1231 if( pAnd->bNomatch && pAnd!=pExpr->pRoot ){
1232 fts5ExprNodeZeroPoslist(pAnd);
1233 }
1234 pAnd->iRowid = iLast;
1235 return SQLITE_OK;
1236 }
1237
fts5ExprNodeNext_AND(Fts5Expr * pExpr,Fts5ExprNode * pNode,int bFromValid,i64 iFrom)1238 static int fts5ExprNodeNext_AND(
1239 Fts5Expr *pExpr,
1240 Fts5ExprNode *pNode,
1241 int bFromValid,
1242 i64 iFrom
1243 ){
1244 int rc = fts5ExprNodeNext(pExpr, pNode->apChild[0], bFromValid, iFrom);
1245 if( rc==SQLITE_OK ){
1246 rc = fts5ExprNodeTest_AND(pExpr, pNode);
1247 }else{
1248 pNode->bNomatch = 0;
1249 }
1250 return rc;
1251 }
1252
fts5ExprNodeTest_NOT(Fts5Expr * pExpr,Fts5ExprNode * pNode)1253 static int fts5ExprNodeTest_NOT(
1254 Fts5Expr *pExpr, /* Expression pPhrase belongs to */
1255 Fts5ExprNode *pNode /* FTS5_NOT node to advance */
1256 ){
1257 int rc = SQLITE_OK;
1258 Fts5ExprNode *p1 = pNode->apChild[0];
1259 Fts5ExprNode *p2 = pNode->apChild[1];
1260 assert( pNode->nChild==2 );
1261
1262 while( rc==SQLITE_OK && p1->bEof==0 ){
1263 int cmp = fts5NodeCompare(pExpr, p1, p2);
1264 if( cmp>0 ){
1265 rc = fts5ExprNodeNext(pExpr, p2, 1, p1->iRowid);
1266 cmp = fts5NodeCompare(pExpr, p1, p2);
1267 }
1268 assert( rc!=SQLITE_OK || cmp<=0 );
1269 if( cmp || p2->bNomatch ) break;
1270 rc = fts5ExprNodeNext(pExpr, p1, 0, 0);
1271 }
1272 pNode->bEof = p1->bEof;
1273 pNode->bNomatch = p1->bNomatch;
1274 pNode->iRowid = p1->iRowid;
1275 if( p1->bEof ){
1276 fts5ExprNodeZeroPoslist(p2);
1277 }
1278 return rc;
1279 }
1280
fts5ExprNodeNext_NOT(Fts5Expr * pExpr,Fts5ExprNode * pNode,int bFromValid,i64 iFrom)1281 static int fts5ExprNodeNext_NOT(
1282 Fts5Expr *pExpr,
1283 Fts5ExprNode *pNode,
1284 int bFromValid,
1285 i64 iFrom
1286 ){
1287 int rc = fts5ExprNodeNext(pExpr, pNode->apChild[0], bFromValid, iFrom);
1288 if( rc==SQLITE_OK ){
1289 rc = fts5ExprNodeTest_NOT(pExpr, pNode);
1290 }
1291 if( rc!=SQLITE_OK ){
1292 pNode->bNomatch = 0;
1293 }
1294 return rc;
1295 }
1296
1297 /*
1298 ** If pNode currently points to a match, this function returns SQLITE_OK
1299 ** without modifying it. Otherwise, pNode is advanced until it does point
1300 ** to a match or EOF is reached.
1301 */
fts5ExprNodeTest(Fts5Expr * pExpr,Fts5ExprNode * pNode)1302 static int fts5ExprNodeTest(
1303 Fts5Expr *pExpr, /* Expression of which pNode is a part */
1304 Fts5ExprNode *pNode /* Expression node to test */
1305 ){
1306 int rc = SQLITE_OK;
1307 if( pNode->bEof==0 ){
1308 switch( pNode->eType ){
1309
1310 case FTS5_STRING: {
1311 rc = fts5ExprNodeTest_STRING(pExpr, pNode);
1312 break;
1313 }
1314
1315 case FTS5_TERM: {
1316 rc = fts5ExprNodeTest_TERM(pExpr, pNode);
1317 break;
1318 }
1319
1320 case FTS5_AND: {
1321 rc = fts5ExprNodeTest_AND(pExpr, pNode);
1322 break;
1323 }
1324
1325 case FTS5_OR: {
1326 fts5ExprNodeTest_OR(pExpr, pNode);
1327 break;
1328 }
1329
1330 default: assert( pNode->eType==FTS5_NOT ); {
1331 rc = fts5ExprNodeTest_NOT(pExpr, pNode);
1332 break;
1333 }
1334 }
1335 }
1336 return rc;
1337 }
1338
1339
1340 /*
1341 ** Set node pNode, which is part of expression pExpr, to point to the first
1342 ** match. If there are no matches, set the Node.bEof flag to indicate EOF.
1343 **
1344 ** Return an SQLite error code if an error occurs, or SQLITE_OK otherwise.
1345 ** It is not an error if there are no matches.
1346 */
fts5ExprNodeFirst(Fts5Expr * pExpr,Fts5ExprNode * pNode)1347 static int fts5ExprNodeFirst(Fts5Expr *pExpr, Fts5ExprNode *pNode){
1348 int rc = SQLITE_OK;
1349 pNode->bEof = 0;
1350 pNode->bNomatch = 0;
1351
1352 if( Fts5NodeIsString(pNode) ){
1353 /* Initialize all term iterators in the NEAR object. */
1354 rc = fts5ExprNearInitAll(pExpr, pNode);
1355 }else if( pNode->xNext==0 ){
1356 pNode->bEof = 1;
1357 }else{
1358 int i;
1359 int nEof = 0;
1360 for(i=0; i<pNode->nChild && rc==SQLITE_OK; i++){
1361 Fts5ExprNode *pChild = pNode->apChild[i];
1362 rc = fts5ExprNodeFirst(pExpr, pNode->apChild[i]);
1363 assert( pChild->bEof==0 || pChild->bEof==1 );
1364 nEof += pChild->bEof;
1365 }
1366 pNode->iRowid = pNode->apChild[0]->iRowid;
1367
1368 switch( pNode->eType ){
1369 case FTS5_AND:
1370 if( nEof>0 ) fts5ExprSetEof(pNode);
1371 break;
1372
1373 case FTS5_OR:
1374 if( pNode->nChild==nEof ) fts5ExprSetEof(pNode);
1375 break;
1376
1377 default:
1378 assert( pNode->eType==FTS5_NOT );
1379 pNode->bEof = pNode->apChild[0]->bEof;
1380 break;
1381 }
1382 }
1383
1384 if( rc==SQLITE_OK ){
1385 rc = fts5ExprNodeTest(pExpr, pNode);
1386 }
1387 return rc;
1388 }
1389
1390
1391 /*
1392 ** Begin iterating through the set of documents in index pIdx matched by
1393 ** the MATCH expression passed as the first argument. If the "bDesc"
1394 ** parameter is passed a non-zero value, iteration is in descending rowid
1395 ** order. Or, if it is zero, in ascending order.
1396 **
1397 ** If iterating in ascending rowid order (bDesc==0), the first document
1398 ** visited is that with the smallest rowid that is larger than or equal
1399 ** to parameter iFirst. Or, if iterating in ascending order (bDesc==1),
1400 ** then the first document visited must have a rowid smaller than or
1401 ** equal to iFirst.
1402 **
1403 ** Return SQLITE_OK if successful, or an SQLite error code otherwise. It
1404 ** is not considered an error if the query does not match any documents.
1405 */
sqlite3Fts5ExprFirst(Fts5Expr * p,Fts5Index * pIdx,i64 iFirst,int bDesc)1406 int sqlite3Fts5ExprFirst(Fts5Expr *p, Fts5Index *pIdx, i64 iFirst, int bDesc){
1407 Fts5ExprNode *pRoot = p->pRoot;
1408 int rc; /* Return code */
1409
1410 p->pIndex = pIdx;
1411 p->bDesc = bDesc;
1412 rc = fts5ExprNodeFirst(p, pRoot);
1413
1414 /* If not at EOF but the current rowid occurs earlier than iFirst in
1415 ** the iteration order, move to document iFirst or later. */
1416 if( rc==SQLITE_OK
1417 && 0==pRoot->bEof
1418 && fts5RowidCmp(p, pRoot->iRowid, iFirst)<0
1419 ){
1420 rc = fts5ExprNodeNext(p, pRoot, 1, iFirst);
1421 }
1422
1423 /* If the iterator is not at a real match, skip forward until it is. */
1424 while( pRoot->bNomatch ){
1425 assert( pRoot->bEof==0 && rc==SQLITE_OK );
1426 rc = fts5ExprNodeNext(p, pRoot, 0, 0);
1427 }
1428 return rc;
1429 }
1430
1431 /*
1432 ** Move to the next document
1433 **
1434 ** Return SQLITE_OK if successful, or an SQLite error code otherwise. It
1435 ** is not considered an error if the query does not match any documents.
1436 */
sqlite3Fts5ExprNext(Fts5Expr * p,i64 iLast)1437 int sqlite3Fts5ExprNext(Fts5Expr *p, i64 iLast){
1438 int rc;
1439 Fts5ExprNode *pRoot = p->pRoot;
1440 assert( pRoot->bEof==0 && pRoot->bNomatch==0 );
1441 do {
1442 rc = fts5ExprNodeNext(p, pRoot, 0, 0);
1443 assert( pRoot->bNomatch==0 || (rc==SQLITE_OK && pRoot->bEof==0) );
1444 }while( pRoot->bNomatch );
1445 if( fts5RowidCmp(p, pRoot->iRowid, iLast)>0 ){
1446 pRoot->bEof = 1;
1447 }
1448 return rc;
1449 }
1450
sqlite3Fts5ExprEof(Fts5Expr * p)1451 int sqlite3Fts5ExprEof(Fts5Expr *p){
1452 return p->pRoot->bEof;
1453 }
1454
sqlite3Fts5ExprRowid(Fts5Expr * p)1455 i64 sqlite3Fts5ExprRowid(Fts5Expr *p){
1456 return p->pRoot->iRowid;
1457 }
1458
fts5ParseStringFromToken(Fts5Token * pToken,char ** pz)1459 static int fts5ParseStringFromToken(Fts5Token *pToken, char **pz){
1460 int rc = SQLITE_OK;
1461 *pz = sqlite3Fts5Strndup(&rc, pToken->p, pToken->n);
1462 return rc;
1463 }
1464
1465 /*
1466 ** Free the phrase object passed as the only argument.
1467 */
fts5ExprPhraseFree(Fts5ExprPhrase * pPhrase)1468 static void fts5ExprPhraseFree(Fts5ExprPhrase *pPhrase){
1469 if( pPhrase ){
1470 int i;
1471 for(i=0; i<pPhrase->nTerm; i++){
1472 Fts5ExprTerm *pSyn;
1473 Fts5ExprTerm *pNext;
1474 Fts5ExprTerm *pTerm = &pPhrase->aTerm[i];
1475 sqlite3_free(pTerm->zTerm);
1476 sqlite3Fts5IterClose(pTerm->pIter);
1477 for(pSyn=pTerm->pSynonym; pSyn; pSyn=pNext){
1478 pNext = pSyn->pSynonym;
1479 sqlite3Fts5IterClose(pSyn->pIter);
1480 fts5BufferFree((Fts5Buffer*)&pSyn[1]);
1481 sqlite3_free(pSyn);
1482 }
1483 }
1484 if( pPhrase->poslist.nSpace>0 ) fts5BufferFree(&pPhrase->poslist);
1485 sqlite3_free(pPhrase);
1486 }
1487 }
1488
1489 /*
1490 ** Set the "bFirst" flag on the first token of the phrase passed as the
1491 ** only argument.
1492 */
sqlite3Fts5ParseSetCaret(Fts5ExprPhrase * pPhrase)1493 void sqlite3Fts5ParseSetCaret(Fts5ExprPhrase *pPhrase){
1494 if( pPhrase && pPhrase->nTerm ){
1495 pPhrase->aTerm[0].bFirst = 1;
1496 }
1497 }
1498
1499 /*
1500 ** If argument pNear is NULL, then a new Fts5ExprNearset object is allocated
1501 ** and populated with pPhrase. Or, if pNear is not NULL, phrase pPhrase is
1502 ** appended to it and the results returned.
1503 **
1504 ** If an OOM error occurs, both the pNear and pPhrase objects are freed and
1505 ** NULL returned.
1506 */
sqlite3Fts5ParseNearset(Fts5Parse * pParse,Fts5ExprNearset * pNear,Fts5ExprPhrase * pPhrase)1507 Fts5ExprNearset *sqlite3Fts5ParseNearset(
1508 Fts5Parse *pParse, /* Parse context */
1509 Fts5ExprNearset *pNear, /* Existing nearset, or NULL */
1510 Fts5ExprPhrase *pPhrase /* Recently parsed phrase */
1511 ){
1512 const int SZALLOC = 8;
1513 Fts5ExprNearset *pRet = 0;
1514
1515 if( pParse->rc==SQLITE_OK ){
1516 if( pPhrase==0 ){
1517 return pNear;
1518 }
1519 if( pNear==0 ){
1520 sqlite3_int64 nByte;
1521 nByte = sizeof(Fts5ExprNearset) + SZALLOC * sizeof(Fts5ExprPhrase*);
1522 pRet = sqlite3_malloc64(nByte);
1523 if( pRet==0 ){
1524 pParse->rc = SQLITE_NOMEM;
1525 }else{
1526 memset(pRet, 0, (size_t)nByte);
1527 }
1528 }else if( (pNear->nPhrase % SZALLOC)==0 ){
1529 int nNew = pNear->nPhrase + SZALLOC;
1530 sqlite3_int64 nByte;
1531
1532 nByte = sizeof(Fts5ExprNearset) + nNew * sizeof(Fts5ExprPhrase*);
1533 pRet = (Fts5ExprNearset*)sqlite3_realloc64(pNear, nByte);
1534 if( pRet==0 ){
1535 pParse->rc = SQLITE_NOMEM;
1536 }
1537 }else{
1538 pRet = pNear;
1539 }
1540 }
1541
1542 if( pRet==0 ){
1543 assert( pParse->rc!=SQLITE_OK );
1544 sqlite3Fts5ParseNearsetFree(pNear);
1545 sqlite3Fts5ParsePhraseFree(pPhrase);
1546 }else{
1547 if( pRet->nPhrase>0 ){
1548 Fts5ExprPhrase *pLast = pRet->apPhrase[pRet->nPhrase-1];
1549 assert( pLast==pParse->apPhrase[pParse->nPhrase-2] );
1550 if( pPhrase->nTerm==0 ){
1551 fts5ExprPhraseFree(pPhrase);
1552 pRet->nPhrase--;
1553 pParse->nPhrase--;
1554 pPhrase = pLast;
1555 }else if( pLast->nTerm==0 ){
1556 fts5ExprPhraseFree(pLast);
1557 pParse->apPhrase[pParse->nPhrase-2] = pPhrase;
1558 pParse->nPhrase--;
1559 pRet->nPhrase--;
1560 }
1561 }
1562 pRet->apPhrase[pRet->nPhrase++] = pPhrase;
1563 }
1564 return pRet;
1565 }
1566
1567 typedef struct TokenCtx TokenCtx;
1568 struct TokenCtx {
1569 Fts5ExprPhrase *pPhrase;
1570 int rc;
1571 };
1572
1573 /*
1574 ** Callback for tokenizing terms used by ParseTerm().
1575 */
fts5ParseTokenize(void * pContext,int tflags,const char * pToken,int nToken,int iUnused1,int iUnused2)1576 static int fts5ParseTokenize(
1577 void *pContext, /* Pointer to Fts5InsertCtx object */
1578 int tflags, /* Mask of FTS5_TOKEN_* flags */
1579 const char *pToken, /* Buffer containing token */
1580 int nToken, /* Size of token in bytes */
1581 int iUnused1, /* Start offset of token */
1582 int iUnused2 /* End offset of token */
1583 ){
1584 int rc = SQLITE_OK;
1585 const int SZALLOC = 8;
1586 TokenCtx *pCtx = (TokenCtx*)pContext;
1587 Fts5ExprPhrase *pPhrase = pCtx->pPhrase;
1588
1589 UNUSED_PARAM2(iUnused1, iUnused2);
1590
1591 /* If an error has already occurred, this is a no-op */
1592 if( pCtx->rc!=SQLITE_OK ) return pCtx->rc;
1593 if( nToken>FTS5_MAX_TOKEN_SIZE ) nToken = FTS5_MAX_TOKEN_SIZE;
1594
1595 if( pPhrase && pPhrase->nTerm>0 && (tflags & FTS5_TOKEN_COLOCATED) ){
1596 Fts5ExprTerm *pSyn;
1597 sqlite3_int64 nByte = sizeof(Fts5ExprTerm) + sizeof(Fts5Buffer) + nToken+1;
1598 pSyn = (Fts5ExprTerm*)sqlite3_malloc64(nByte);
1599 if( pSyn==0 ){
1600 rc = SQLITE_NOMEM;
1601 }else{
1602 memset(pSyn, 0, (size_t)nByte);
1603 pSyn->zTerm = ((char*)pSyn) + sizeof(Fts5ExprTerm) + sizeof(Fts5Buffer);
1604 memcpy(pSyn->zTerm, pToken, nToken);
1605 pSyn->pSynonym = pPhrase->aTerm[pPhrase->nTerm-1].pSynonym;
1606 pPhrase->aTerm[pPhrase->nTerm-1].pSynonym = pSyn;
1607 }
1608 }else{
1609 Fts5ExprTerm *pTerm;
1610 if( pPhrase==0 || (pPhrase->nTerm % SZALLOC)==0 ){
1611 Fts5ExprPhrase *pNew;
1612 int nNew = SZALLOC + (pPhrase ? pPhrase->nTerm : 0);
1613
1614 pNew = (Fts5ExprPhrase*)sqlite3_realloc64(pPhrase,
1615 sizeof(Fts5ExprPhrase) + sizeof(Fts5ExprTerm) * nNew
1616 );
1617 if( pNew==0 ){
1618 rc = SQLITE_NOMEM;
1619 }else{
1620 if( pPhrase==0 ) memset(pNew, 0, sizeof(Fts5ExprPhrase));
1621 pCtx->pPhrase = pPhrase = pNew;
1622 pNew->nTerm = nNew - SZALLOC;
1623 }
1624 }
1625
1626 if( rc==SQLITE_OK ){
1627 pTerm = &pPhrase->aTerm[pPhrase->nTerm++];
1628 memset(pTerm, 0, sizeof(Fts5ExprTerm));
1629 pTerm->zTerm = sqlite3Fts5Strndup(&rc, pToken, nToken);
1630 }
1631 }
1632
1633 pCtx->rc = rc;
1634 return rc;
1635 }
1636
1637
1638 /*
1639 ** Free the phrase object passed as the only argument.
1640 */
sqlite3Fts5ParsePhraseFree(Fts5ExprPhrase * pPhrase)1641 void sqlite3Fts5ParsePhraseFree(Fts5ExprPhrase *pPhrase){
1642 fts5ExprPhraseFree(pPhrase);
1643 }
1644
1645 /*
1646 ** Free the phrase object passed as the second argument.
1647 */
sqlite3Fts5ParseNearsetFree(Fts5ExprNearset * pNear)1648 void sqlite3Fts5ParseNearsetFree(Fts5ExprNearset *pNear){
1649 if( pNear ){
1650 int i;
1651 for(i=0; i<pNear->nPhrase; i++){
1652 fts5ExprPhraseFree(pNear->apPhrase[i]);
1653 }
1654 sqlite3_free(pNear->pColset);
1655 sqlite3_free(pNear);
1656 }
1657 }
1658
sqlite3Fts5ParseFinished(Fts5Parse * pParse,Fts5ExprNode * p)1659 void sqlite3Fts5ParseFinished(Fts5Parse *pParse, Fts5ExprNode *p){
1660 assert( pParse->pExpr==0 );
1661 pParse->pExpr = p;
1662 }
1663
1664 /*
1665 ** This function is called by the parser to process a string token. The
1666 ** string may or may not be quoted. In any case it is tokenized and a
1667 ** phrase object consisting of all tokens returned.
1668 */
sqlite3Fts5ParseTerm(Fts5Parse * pParse,Fts5ExprPhrase * pAppend,Fts5Token * pToken,int bPrefix)1669 Fts5ExprPhrase *sqlite3Fts5ParseTerm(
1670 Fts5Parse *pParse, /* Parse context */
1671 Fts5ExprPhrase *pAppend, /* Phrase to append to */
1672 Fts5Token *pToken, /* String to tokenize */
1673 int bPrefix /* True if there is a trailing "*" */
1674 ){
1675 Fts5Config *pConfig = pParse->pConfig;
1676 TokenCtx sCtx; /* Context object passed to callback */
1677 int rc; /* Tokenize return code */
1678 char *z = 0;
1679
1680 memset(&sCtx, 0, sizeof(TokenCtx));
1681 sCtx.pPhrase = pAppend;
1682
1683 rc = fts5ParseStringFromToken(pToken, &z);
1684 if( rc==SQLITE_OK ){
1685 int flags = FTS5_TOKENIZE_QUERY | (bPrefix ? FTS5_TOKENIZE_PREFIX : 0);
1686 int n;
1687 sqlite3Fts5Dequote(z);
1688 n = (int)strlen(z);
1689 rc = sqlite3Fts5Tokenize(pConfig, flags, z, n, &sCtx, fts5ParseTokenize);
1690 }
1691 sqlite3_free(z);
1692 if( rc || (rc = sCtx.rc) ){
1693 pParse->rc = rc;
1694 fts5ExprPhraseFree(sCtx.pPhrase);
1695 sCtx.pPhrase = 0;
1696 }else{
1697
1698 if( pAppend==0 ){
1699 if( (pParse->nPhrase % 8)==0 ){
1700 sqlite3_int64 nByte = sizeof(Fts5ExprPhrase*) * (pParse->nPhrase + 8);
1701 Fts5ExprPhrase **apNew;
1702 apNew = (Fts5ExprPhrase**)sqlite3_realloc64(pParse->apPhrase, nByte);
1703 if( apNew==0 ){
1704 pParse->rc = SQLITE_NOMEM;
1705 fts5ExprPhraseFree(sCtx.pPhrase);
1706 return 0;
1707 }
1708 pParse->apPhrase = apNew;
1709 }
1710 pParse->nPhrase++;
1711 }
1712
1713 if( sCtx.pPhrase==0 ){
1714 /* This happens when parsing a token or quoted phrase that contains
1715 ** no token characters at all. (e.g ... MATCH '""'). */
1716 sCtx.pPhrase = sqlite3Fts5MallocZero(&pParse->rc, sizeof(Fts5ExprPhrase));
1717 }else if( sCtx.pPhrase->nTerm ){
1718 sCtx.pPhrase->aTerm[sCtx.pPhrase->nTerm-1].bPrefix = (u8)bPrefix;
1719 }
1720 pParse->apPhrase[pParse->nPhrase-1] = sCtx.pPhrase;
1721 }
1722
1723 return sCtx.pPhrase;
1724 }
1725
1726 /*
1727 ** Create a new FTS5 expression by cloning phrase iPhrase of the
1728 ** expression passed as the second argument.
1729 */
sqlite3Fts5ExprClonePhrase(Fts5Expr * pExpr,int iPhrase,Fts5Expr ** ppNew)1730 int sqlite3Fts5ExprClonePhrase(
1731 Fts5Expr *pExpr,
1732 int iPhrase,
1733 Fts5Expr **ppNew
1734 ){
1735 int rc = SQLITE_OK; /* Return code */
1736 Fts5ExprPhrase *pOrig; /* The phrase extracted from pExpr */
1737 Fts5Expr *pNew = 0; /* Expression to return via *ppNew */
1738 TokenCtx sCtx = {0,0}; /* Context object for fts5ParseTokenize */
1739
1740 pOrig = pExpr->apExprPhrase[iPhrase];
1741 pNew = (Fts5Expr*)sqlite3Fts5MallocZero(&rc, sizeof(Fts5Expr));
1742 if( rc==SQLITE_OK ){
1743 pNew->apExprPhrase = (Fts5ExprPhrase**)sqlite3Fts5MallocZero(&rc,
1744 sizeof(Fts5ExprPhrase*));
1745 }
1746 if( rc==SQLITE_OK ){
1747 pNew->pRoot = (Fts5ExprNode*)sqlite3Fts5MallocZero(&rc,
1748 sizeof(Fts5ExprNode));
1749 }
1750 if( rc==SQLITE_OK ){
1751 pNew->pRoot->pNear = (Fts5ExprNearset*)sqlite3Fts5MallocZero(&rc,
1752 sizeof(Fts5ExprNearset) + sizeof(Fts5ExprPhrase*));
1753 }
1754 if( rc==SQLITE_OK ){
1755 Fts5Colset *pColsetOrig = pOrig->pNode->pNear->pColset;
1756 if( pColsetOrig ){
1757 sqlite3_int64 nByte;
1758 Fts5Colset *pColset;
1759 nByte = sizeof(Fts5Colset) + (pColsetOrig->nCol-1) * sizeof(int);
1760 pColset = (Fts5Colset*)sqlite3Fts5MallocZero(&rc, nByte);
1761 if( pColset ){
1762 memcpy(pColset, pColsetOrig, (size_t)nByte);
1763 }
1764 pNew->pRoot->pNear->pColset = pColset;
1765 }
1766 }
1767
1768 if( pOrig->nTerm ){
1769 int i; /* Used to iterate through phrase terms */
1770 for(i=0; rc==SQLITE_OK && i<pOrig->nTerm; i++){
1771 int tflags = 0;
1772 Fts5ExprTerm *p;
1773 for(p=&pOrig->aTerm[i]; p && rc==SQLITE_OK; p=p->pSynonym){
1774 const char *zTerm = p->zTerm;
1775 rc = fts5ParseTokenize((void*)&sCtx, tflags, zTerm, (int)strlen(zTerm),
1776 0, 0);
1777 tflags = FTS5_TOKEN_COLOCATED;
1778 }
1779 if( rc==SQLITE_OK ){
1780 sCtx.pPhrase->aTerm[i].bPrefix = pOrig->aTerm[i].bPrefix;
1781 sCtx.pPhrase->aTerm[i].bFirst = pOrig->aTerm[i].bFirst;
1782 }
1783 }
1784 }else{
1785 /* This happens when parsing a token or quoted phrase that contains
1786 ** no token characters at all. (e.g ... MATCH '""'). */
1787 sCtx.pPhrase = sqlite3Fts5MallocZero(&rc, sizeof(Fts5ExprPhrase));
1788 }
1789
1790 if( rc==SQLITE_OK ){
1791 /* All the allocations succeeded. Put the expression object together. */
1792 pNew->pIndex = pExpr->pIndex;
1793 pNew->pConfig = pExpr->pConfig;
1794 pNew->nPhrase = 1;
1795 pNew->apExprPhrase[0] = sCtx.pPhrase;
1796 pNew->pRoot->pNear->apPhrase[0] = sCtx.pPhrase;
1797 pNew->pRoot->pNear->nPhrase = 1;
1798 sCtx.pPhrase->pNode = pNew->pRoot;
1799
1800 if( pOrig->nTerm==1
1801 && pOrig->aTerm[0].pSynonym==0
1802 && pOrig->aTerm[0].bFirst==0
1803 ){
1804 pNew->pRoot->eType = FTS5_TERM;
1805 pNew->pRoot->xNext = fts5ExprNodeNext_TERM;
1806 }else{
1807 pNew->pRoot->eType = FTS5_STRING;
1808 pNew->pRoot->xNext = fts5ExprNodeNext_STRING;
1809 }
1810 }else{
1811 sqlite3Fts5ExprFree(pNew);
1812 fts5ExprPhraseFree(sCtx.pPhrase);
1813 pNew = 0;
1814 }
1815
1816 *ppNew = pNew;
1817 return rc;
1818 }
1819
1820
1821 /*
1822 ** Token pTok has appeared in a MATCH expression where the NEAR operator
1823 ** is expected. If token pTok does not contain "NEAR", store an error
1824 ** in the pParse object.
1825 */
sqlite3Fts5ParseNear(Fts5Parse * pParse,Fts5Token * pTok)1826 void sqlite3Fts5ParseNear(Fts5Parse *pParse, Fts5Token *pTok){
1827 if( pTok->n!=4 || memcmp("NEAR", pTok->p, 4) ){
1828 sqlite3Fts5ParseError(
1829 pParse, "fts5: syntax error near \"%.*s\"", pTok->n, pTok->p
1830 );
1831 }
1832 }
1833
sqlite3Fts5ParseSetDistance(Fts5Parse * pParse,Fts5ExprNearset * pNear,Fts5Token * p)1834 void sqlite3Fts5ParseSetDistance(
1835 Fts5Parse *pParse,
1836 Fts5ExprNearset *pNear,
1837 Fts5Token *p
1838 ){
1839 if( pNear ){
1840 int nNear = 0;
1841 int i;
1842 if( p->n ){
1843 for(i=0; i<p->n; i++){
1844 char c = (char)p->p[i];
1845 if( c<'0' || c>'9' ){
1846 sqlite3Fts5ParseError(
1847 pParse, "expected integer, got \"%.*s\"", p->n, p->p
1848 );
1849 return;
1850 }
1851 nNear = nNear * 10 + (p->p[i] - '0');
1852 }
1853 }else{
1854 nNear = FTS5_DEFAULT_NEARDIST;
1855 }
1856 pNear->nNear = nNear;
1857 }
1858 }
1859
1860 /*
1861 ** The second argument passed to this function may be NULL, or it may be
1862 ** an existing Fts5Colset object. This function returns a pointer to
1863 ** a new colset object containing the contents of (p) with new value column
1864 ** number iCol appended.
1865 **
1866 ** If an OOM error occurs, store an error code in pParse and return NULL.
1867 ** The old colset object (if any) is not freed in this case.
1868 */
fts5ParseColset(Fts5Parse * pParse,Fts5Colset * p,int iCol)1869 static Fts5Colset *fts5ParseColset(
1870 Fts5Parse *pParse, /* Store SQLITE_NOMEM here if required */
1871 Fts5Colset *p, /* Existing colset object */
1872 int iCol /* New column to add to colset object */
1873 ){
1874 int nCol = p ? p->nCol : 0; /* Num. columns already in colset object */
1875 Fts5Colset *pNew; /* New colset object to return */
1876
1877 assert( pParse->rc==SQLITE_OK );
1878 assert( iCol>=0 && iCol<pParse->pConfig->nCol );
1879
1880 pNew = sqlite3_realloc64(p, sizeof(Fts5Colset) + sizeof(int)*nCol);
1881 if( pNew==0 ){
1882 pParse->rc = SQLITE_NOMEM;
1883 }else{
1884 int *aiCol = pNew->aiCol;
1885 int i, j;
1886 for(i=0; i<nCol; i++){
1887 if( aiCol[i]==iCol ) return pNew;
1888 if( aiCol[i]>iCol ) break;
1889 }
1890 for(j=nCol; j>i; j--){
1891 aiCol[j] = aiCol[j-1];
1892 }
1893 aiCol[i] = iCol;
1894 pNew->nCol = nCol+1;
1895
1896 #ifndef NDEBUG
1897 /* Check that the array is in order and contains no duplicate entries. */
1898 for(i=1; i<pNew->nCol; i++) assert( pNew->aiCol[i]>pNew->aiCol[i-1] );
1899 #endif
1900 }
1901
1902 return pNew;
1903 }
1904
1905 /*
1906 ** Allocate and return an Fts5Colset object specifying the inverse of
1907 ** the colset passed as the second argument. Free the colset passed
1908 ** as the second argument before returning.
1909 */
sqlite3Fts5ParseColsetInvert(Fts5Parse * pParse,Fts5Colset * p)1910 Fts5Colset *sqlite3Fts5ParseColsetInvert(Fts5Parse *pParse, Fts5Colset *p){
1911 Fts5Colset *pRet;
1912 int nCol = pParse->pConfig->nCol;
1913
1914 pRet = (Fts5Colset*)sqlite3Fts5MallocZero(&pParse->rc,
1915 sizeof(Fts5Colset) + sizeof(int)*nCol
1916 );
1917 if( pRet ){
1918 int i;
1919 int iOld = 0;
1920 for(i=0; i<nCol; i++){
1921 if( iOld>=p->nCol || p->aiCol[iOld]!=i ){
1922 pRet->aiCol[pRet->nCol++] = i;
1923 }else{
1924 iOld++;
1925 }
1926 }
1927 }
1928
1929 sqlite3_free(p);
1930 return pRet;
1931 }
1932
sqlite3Fts5ParseColset(Fts5Parse * pParse,Fts5Colset * pColset,Fts5Token * p)1933 Fts5Colset *sqlite3Fts5ParseColset(
1934 Fts5Parse *pParse, /* Store SQLITE_NOMEM here if required */
1935 Fts5Colset *pColset, /* Existing colset object */
1936 Fts5Token *p
1937 ){
1938 Fts5Colset *pRet = 0;
1939 int iCol;
1940 char *z; /* Dequoted copy of token p */
1941
1942 z = sqlite3Fts5Strndup(&pParse->rc, p->p, p->n);
1943 if( pParse->rc==SQLITE_OK ){
1944 Fts5Config *pConfig = pParse->pConfig;
1945 sqlite3Fts5Dequote(z);
1946 for(iCol=0; iCol<pConfig->nCol; iCol++){
1947 if( 0==sqlite3_stricmp(pConfig->azCol[iCol], z) ) break;
1948 }
1949 if( iCol==pConfig->nCol ){
1950 sqlite3Fts5ParseError(pParse, "no such column: %s", z);
1951 }else{
1952 pRet = fts5ParseColset(pParse, pColset, iCol);
1953 }
1954 sqlite3_free(z);
1955 }
1956
1957 if( pRet==0 ){
1958 assert( pParse->rc!=SQLITE_OK );
1959 sqlite3_free(pColset);
1960 }
1961
1962 return pRet;
1963 }
1964
1965 /*
1966 ** If argument pOrig is NULL, or if (*pRc) is set to anything other than
1967 ** SQLITE_OK when this function is called, NULL is returned.
1968 **
1969 ** Otherwise, a copy of (*pOrig) is made into memory obtained from
1970 ** sqlite3Fts5MallocZero() and a pointer to it returned. If the allocation
1971 ** fails, (*pRc) is set to SQLITE_NOMEM and NULL is returned.
1972 */
fts5CloneColset(int * pRc,Fts5Colset * pOrig)1973 static Fts5Colset *fts5CloneColset(int *pRc, Fts5Colset *pOrig){
1974 Fts5Colset *pRet;
1975 if( pOrig ){
1976 sqlite3_int64 nByte = sizeof(Fts5Colset) + (pOrig->nCol-1) * sizeof(int);
1977 pRet = (Fts5Colset*)sqlite3Fts5MallocZero(pRc, nByte);
1978 if( pRet ){
1979 memcpy(pRet, pOrig, (size_t)nByte);
1980 }
1981 }else{
1982 pRet = 0;
1983 }
1984 return pRet;
1985 }
1986
1987 /*
1988 ** Remove from colset pColset any columns that are not also in colset pMerge.
1989 */
fts5MergeColset(Fts5Colset * pColset,Fts5Colset * pMerge)1990 static void fts5MergeColset(Fts5Colset *pColset, Fts5Colset *pMerge){
1991 int iIn = 0; /* Next input in pColset */
1992 int iMerge = 0; /* Next input in pMerge */
1993 int iOut = 0; /* Next output slot in pColset */
1994
1995 while( iIn<pColset->nCol && iMerge<pMerge->nCol ){
1996 int iDiff = pColset->aiCol[iIn] - pMerge->aiCol[iMerge];
1997 if( iDiff==0 ){
1998 pColset->aiCol[iOut++] = pMerge->aiCol[iMerge];
1999 iMerge++;
2000 iIn++;
2001 }else if( iDiff>0 ){
2002 iMerge++;
2003 }else{
2004 iIn++;
2005 }
2006 }
2007 pColset->nCol = iOut;
2008 }
2009
2010 /*
2011 ** Recursively apply colset pColset to expression node pNode and all of
2012 ** its decendents. If (*ppFree) is not NULL, it contains a spare copy
2013 ** of pColset. This function may use the spare copy and set (*ppFree) to
2014 ** zero, or it may create copies of pColset using fts5CloneColset().
2015 */
fts5ParseSetColset(Fts5Parse * pParse,Fts5ExprNode * pNode,Fts5Colset * pColset,Fts5Colset ** ppFree)2016 static void fts5ParseSetColset(
2017 Fts5Parse *pParse,
2018 Fts5ExprNode *pNode,
2019 Fts5Colset *pColset,
2020 Fts5Colset **ppFree
2021 ){
2022 if( pParse->rc==SQLITE_OK ){
2023 assert( pNode->eType==FTS5_TERM || pNode->eType==FTS5_STRING
2024 || pNode->eType==FTS5_AND || pNode->eType==FTS5_OR
2025 || pNode->eType==FTS5_NOT || pNode->eType==FTS5_EOF
2026 );
2027 if( pNode->eType==FTS5_STRING || pNode->eType==FTS5_TERM ){
2028 Fts5ExprNearset *pNear = pNode->pNear;
2029 if( pNear->pColset ){
2030 fts5MergeColset(pNear->pColset, pColset);
2031 if( pNear->pColset->nCol==0 ){
2032 pNode->eType = FTS5_EOF;
2033 pNode->xNext = 0;
2034 }
2035 }else if( *ppFree ){
2036 pNear->pColset = pColset;
2037 *ppFree = 0;
2038 }else{
2039 pNear->pColset = fts5CloneColset(&pParse->rc, pColset);
2040 }
2041 }else{
2042 int i;
2043 assert( pNode->eType!=FTS5_EOF || pNode->nChild==0 );
2044 for(i=0; i<pNode->nChild; i++){
2045 fts5ParseSetColset(pParse, pNode->apChild[i], pColset, ppFree);
2046 }
2047 }
2048 }
2049 }
2050
2051 /*
2052 ** Apply colset pColset to expression node pExpr and all of its descendents.
2053 */
sqlite3Fts5ParseSetColset(Fts5Parse * pParse,Fts5ExprNode * pExpr,Fts5Colset * pColset)2054 void sqlite3Fts5ParseSetColset(
2055 Fts5Parse *pParse,
2056 Fts5ExprNode *pExpr,
2057 Fts5Colset *pColset
2058 ){
2059 Fts5Colset *pFree = pColset;
2060 if( pParse->pConfig->eDetail==FTS5_DETAIL_NONE ){
2061 pParse->rc = SQLITE_ERROR;
2062 pParse->zErr = sqlite3_mprintf(
2063 "fts5: column queries are not supported (detail=none)"
2064 );
2065 }else{
2066 fts5ParseSetColset(pParse, pExpr, pColset, &pFree);
2067 }
2068 sqlite3_free(pFree);
2069 }
2070
fts5ExprAssignXNext(Fts5ExprNode * pNode)2071 static void fts5ExprAssignXNext(Fts5ExprNode *pNode){
2072 switch( pNode->eType ){
2073 case FTS5_STRING: {
2074 Fts5ExprNearset *pNear = pNode->pNear;
2075 if( pNear->nPhrase==1 && pNear->apPhrase[0]->nTerm==1
2076 && pNear->apPhrase[0]->aTerm[0].pSynonym==0
2077 && pNear->apPhrase[0]->aTerm[0].bFirst==0
2078 ){
2079 pNode->eType = FTS5_TERM;
2080 pNode->xNext = fts5ExprNodeNext_TERM;
2081 }else{
2082 pNode->xNext = fts5ExprNodeNext_STRING;
2083 }
2084 break;
2085 };
2086
2087 case FTS5_OR: {
2088 pNode->xNext = fts5ExprNodeNext_OR;
2089 break;
2090 };
2091
2092 case FTS5_AND: {
2093 pNode->xNext = fts5ExprNodeNext_AND;
2094 break;
2095 };
2096
2097 default: assert( pNode->eType==FTS5_NOT ); {
2098 pNode->xNext = fts5ExprNodeNext_NOT;
2099 break;
2100 };
2101 }
2102 }
2103
fts5ExprAddChildren(Fts5ExprNode * p,Fts5ExprNode * pSub)2104 static void fts5ExprAddChildren(Fts5ExprNode *p, Fts5ExprNode *pSub){
2105 if( p->eType!=FTS5_NOT && pSub->eType==p->eType ){
2106 int nByte = sizeof(Fts5ExprNode*) * pSub->nChild;
2107 memcpy(&p->apChild[p->nChild], pSub->apChild, nByte);
2108 p->nChild += pSub->nChild;
2109 sqlite3_free(pSub);
2110 }else{
2111 p->apChild[p->nChild++] = pSub;
2112 }
2113 }
2114
2115 /*
2116 ** Allocate and return a new expression object. If anything goes wrong (i.e.
2117 ** OOM error), leave an error code in pParse and return NULL.
2118 */
sqlite3Fts5ParseNode(Fts5Parse * pParse,int eType,Fts5ExprNode * pLeft,Fts5ExprNode * pRight,Fts5ExprNearset * pNear)2119 Fts5ExprNode *sqlite3Fts5ParseNode(
2120 Fts5Parse *pParse, /* Parse context */
2121 int eType, /* FTS5_STRING, AND, OR or NOT */
2122 Fts5ExprNode *pLeft, /* Left hand child expression */
2123 Fts5ExprNode *pRight, /* Right hand child expression */
2124 Fts5ExprNearset *pNear /* For STRING expressions, the near cluster */
2125 ){
2126 Fts5ExprNode *pRet = 0;
2127
2128 if( pParse->rc==SQLITE_OK ){
2129 int nChild = 0; /* Number of children of returned node */
2130 sqlite3_int64 nByte; /* Bytes of space to allocate for this node */
2131
2132 assert( (eType!=FTS5_STRING && !pNear)
2133 || (eType==FTS5_STRING && !pLeft && !pRight)
2134 );
2135 if( eType==FTS5_STRING && pNear==0 ) return 0;
2136 if( eType!=FTS5_STRING && pLeft==0 ) return pRight;
2137 if( eType!=FTS5_STRING && pRight==0 ) return pLeft;
2138
2139 if( eType==FTS5_NOT ){
2140 nChild = 2;
2141 }else if( eType==FTS5_AND || eType==FTS5_OR ){
2142 nChild = 2;
2143 if( pLeft->eType==eType ) nChild += pLeft->nChild-1;
2144 if( pRight->eType==eType ) nChild += pRight->nChild-1;
2145 }
2146
2147 nByte = sizeof(Fts5ExprNode) + sizeof(Fts5ExprNode*)*(nChild-1);
2148 pRet = (Fts5ExprNode*)sqlite3Fts5MallocZero(&pParse->rc, nByte);
2149
2150 if( pRet ){
2151 pRet->eType = eType;
2152 pRet->pNear = pNear;
2153 fts5ExprAssignXNext(pRet);
2154 if( eType==FTS5_STRING ){
2155 int iPhrase;
2156 for(iPhrase=0; iPhrase<pNear->nPhrase; iPhrase++){
2157 pNear->apPhrase[iPhrase]->pNode = pRet;
2158 if( pNear->apPhrase[iPhrase]->nTerm==0 ){
2159 pRet->xNext = 0;
2160 pRet->eType = FTS5_EOF;
2161 }
2162 }
2163
2164 if( pParse->pConfig->eDetail!=FTS5_DETAIL_FULL ){
2165 Fts5ExprPhrase *pPhrase = pNear->apPhrase[0];
2166 if( pNear->nPhrase!=1
2167 || pPhrase->nTerm>1
2168 || (pPhrase->nTerm>0 && pPhrase->aTerm[0].bFirst)
2169 ){
2170 assert( pParse->rc==SQLITE_OK );
2171 pParse->rc = SQLITE_ERROR;
2172 assert( pParse->zErr==0 );
2173 pParse->zErr = sqlite3_mprintf(
2174 "fts5: %s queries are not supported (detail!=full)",
2175 pNear->nPhrase==1 ? "phrase": "NEAR"
2176 );
2177 sqlite3_free(pRet);
2178 pRet = 0;
2179 }
2180 }
2181 }else{
2182 fts5ExprAddChildren(pRet, pLeft);
2183 fts5ExprAddChildren(pRet, pRight);
2184 }
2185 }
2186 }
2187
2188 if( pRet==0 ){
2189 assert( pParse->rc!=SQLITE_OK );
2190 sqlite3Fts5ParseNodeFree(pLeft);
2191 sqlite3Fts5ParseNodeFree(pRight);
2192 sqlite3Fts5ParseNearsetFree(pNear);
2193 }
2194 return pRet;
2195 }
2196
sqlite3Fts5ParseImplicitAnd(Fts5Parse * pParse,Fts5ExprNode * pLeft,Fts5ExprNode * pRight)2197 Fts5ExprNode *sqlite3Fts5ParseImplicitAnd(
2198 Fts5Parse *pParse, /* Parse context */
2199 Fts5ExprNode *pLeft, /* Left hand child expression */
2200 Fts5ExprNode *pRight /* Right hand child expression */
2201 ){
2202 Fts5ExprNode *pRet = 0;
2203 Fts5ExprNode *pPrev;
2204
2205 if( pParse->rc ){
2206 sqlite3Fts5ParseNodeFree(pLeft);
2207 sqlite3Fts5ParseNodeFree(pRight);
2208 }else{
2209
2210 assert( pLeft->eType==FTS5_STRING
2211 || pLeft->eType==FTS5_TERM
2212 || pLeft->eType==FTS5_EOF
2213 || pLeft->eType==FTS5_AND
2214 );
2215 assert( pRight->eType==FTS5_STRING
2216 || pRight->eType==FTS5_TERM
2217 || pRight->eType==FTS5_EOF
2218 );
2219
2220 if( pLeft->eType==FTS5_AND ){
2221 pPrev = pLeft->apChild[pLeft->nChild-1];
2222 }else{
2223 pPrev = pLeft;
2224 }
2225 assert( pPrev->eType==FTS5_STRING
2226 || pPrev->eType==FTS5_TERM
2227 || pPrev->eType==FTS5_EOF
2228 );
2229
2230 if( pRight->eType==FTS5_EOF ){
2231 assert( pParse->apPhrase[pParse->nPhrase-1]==pRight->pNear->apPhrase[0] );
2232 sqlite3Fts5ParseNodeFree(pRight);
2233 pRet = pLeft;
2234 pParse->nPhrase--;
2235 }
2236 else if( pPrev->eType==FTS5_EOF ){
2237 Fts5ExprPhrase **ap;
2238
2239 if( pPrev==pLeft ){
2240 pRet = pRight;
2241 }else{
2242 pLeft->apChild[pLeft->nChild-1] = pRight;
2243 pRet = pLeft;
2244 }
2245
2246 ap = &pParse->apPhrase[pParse->nPhrase-1-pRight->pNear->nPhrase];
2247 assert( ap[0]==pPrev->pNear->apPhrase[0] );
2248 memmove(ap, &ap[1], sizeof(Fts5ExprPhrase*)*pRight->pNear->nPhrase);
2249 pParse->nPhrase--;
2250
2251 sqlite3Fts5ParseNodeFree(pPrev);
2252 }
2253 else{
2254 pRet = sqlite3Fts5ParseNode(pParse, FTS5_AND, pLeft, pRight, 0);
2255 }
2256 }
2257
2258 return pRet;
2259 }
2260
fts5ExprTermPrint(Fts5ExprTerm * pTerm)2261 static char *fts5ExprTermPrint(Fts5ExprTerm *pTerm){
2262 sqlite3_int64 nByte = 0;
2263 Fts5ExprTerm *p;
2264 char *zQuoted;
2265
2266 /* Determine the maximum amount of space required. */
2267 for(p=pTerm; p; p=p->pSynonym){
2268 nByte += (int)strlen(pTerm->zTerm) * 2 + 3 + 2;
2269 }
2270 zQuoted = sqlite3_malloc64(nByte);
2271
2272 if( zQuoted ){
2273 int i = 0;
2274 for(p=pTerm; p; p=p->pSynonym){
2275 char *zIn = p->zTerm;
2276 zQuoted[i++] = '"';
2277 while( *zIn ){
2278 if( *zIn=='"' ) zQuoted[i++] = '"';
2279 zQuoted[i++] = *zIn++;
2280 }
2281 zQuoted[i++] = '"';
2282 if( p->pSynonym ) zQuoted[i++] = '|';
2283 }
2284 if( pTerm->bPrefix ){
2285 zQuoted[i++] = ' ';
2286 zQuoted[i++] = '*';
2287 }
2288 zQuoted[i++] = '\0';
2289 }
2290 return zQuoted;
2291 }
2292
fts5PrintfAppend(char * zApp,const char * zFmt,...)2293 static char *fts5PrintfAppend(char *zApp, const char *zFmt, ...){
2294 char *zNew;
2295 va_list ap;
2296 va_start(ap, zFmt);
2297 zNew = sqlite3_vmprintf(zFmt, ap);
2298 va_end(ap);
2299 if( zApp && zNew ){
2300 char *zNew2 = sqlite3_mprintf("%s%s", zApp, zNew);
2301 sqlite3_free(zNew);
2302 zNew = zNew2;
2303 }
2304 sqlite3_free(zApp);
2305 return zNew;
2306 }
2307
2308 /*
2309 ** Compose a tcl-readable representation of expression pExpr. Return a
2310 ** pointer to a buffer containing that representation. It is the
2311 ** responsibility of the caller to at some point free the buffer using
2312 ** sqlite3_free().
2313 */
fts5ExprPrintTcl(Fts5Config * pConfig,const char * zNearsetCmd,Fts5ExprNode * pExpr)2314 static char *fts5ExprPrintTcl(
2315 Fts5Config *pConfig,
2316 const char *zNearsetCmd,
2317 Fts5ExprNode *pExpr
2318 ){
2319 char *zRet = 0;
2320 if( pExpr->eType==FTS5_STRING || pExpr->eType==FTS5_TERM ){
2321 Fts5ExprNearset *pNear = pExpr->pNear;
2322 int i;
2323 int iTerm;
2324
2325 zRet = fts5PrintfAppend(zRet, "%s ", zNearsetCmd);
2326 if( zRet==0 ) return 0;
2327 if( pNear->pColset ){
2328 int *aiCol = pNear->pColset->aiCol;
2329 int nCol = pNear->pColset->nCol;
2330 if( nCol==1 ){
2331 zRet = fts5PrintfAppend(zRet, "-col %d ", aiCol[0]);
2332 }else{
2333 zRet = fts5PrintfAppend(zRet, "-col {%d", aiCol[0]);
2334 for(i=1; i<pNear->pColset->nCol; i++){
2335 zRet = fts5PrintfAppend(zRet, " %d", aiCol[i]);
2336 }
2337 zRet = fts5PrintfAppend(zRet, "} ");
2338 }
2339 if( zRet==0 ) return 0;
2340 }
2341
2342 if( pNear->nPhrase>1 ){
2343 zRet = fts5PrintfAppend(zRet, "-near %d ", pNear->nNear);
2344 if( zRet==0 ) return 0;
2345 }
2346
2347 zRet = fts5PrintfAppend(zRet, "--");
2348 if( zRet==0 ) return 0;
2349
2350 for(i=0; i<pNear->nPhrase; i++){
2351 Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
2352
2353 zRet = fts5PrintfAppend(zRet, " {");
2354 for(iTerm=0; zRet && iTerm<pPhrase->nTerm; iTerm++){
2355 char *zTerm = pPhrase->aTerm[iTerm].zTerm;
2356 zRet = fts5PrintfAppend(zRet, "%s%s", iTerm==0?"":" ", zTerm);
2357 if( pPhrase->aTerm[iTerm].bPrefix ){
2358 zRet = fts5PrintfAppend(zRet, "*");
2359 }
2360 }
2361
2362 if( zRet ) zRet = fts5PrintfAppend(zRet, "}");
2363 if( zRet==0 ) return 0;
2364 }
2365
2366 }else{
2367 char const *zOp = 0;
2368 int i;
2369 switch( pExpr->eType ){
2370 case FTS5_AND: zOp = "AND"; break;
2371 case FTS5_NOT: zOp = "NOT"; break;
2372 default:
2373 assert( pExpr->eType==FTS5_OR );
2374 zOp = "OR";
2375 break;
2376 }
2377
2378 zRet = sqlite3_mprintf("%s", zOp);
2379 for(i=0; zRet && i<pExpr->nChild; i++){
2380 char *z = fts5ExprPrintTcl(pConfig, zNearsetCmd, pExpr->apChild[i]);
2381 if( !z ){
2382 sqlite3_free(zRet);
2383 zRet = 0;
2384 }else{
2385 zRet = fts5PrintfAppend(zRet, " [%z]", z);
2386 }
2387 }
2388 }
2389
2390 return zRet;
2391 }
2392
fts5ExprPrint(Fts5Config * pConfig,Fts5ExprNode * pExpr)2393 static char *fts5ExprPrint(Fts5Config *pConfig, Fts5ExprNode *pExpr){
2394 char *zRet = 0;
2395 if( pExpr->eType==0 ){
2396 return sqlite3_mprintf("\"\"");
2397 }else
2398 if( pExpr->eType==FTS5_STRING || pExpr->eType==FTS5_TERM ){
2399 Fts5ExprNearset *pNear = pExpr->pNear;
2400 int i;
2401 int iTerm;
2402
2403 if( pNear->pColset ){
2404 int iCol = pNear->pColset->aiCol[0];
2405 zRet = fts5PrintfAppend(zRet, "%s : ", pConfig->azCol[iCol]);
2406 if( zRet==0 ) return 0;
2407 }
2408
2409 if( pNear->nPhrase>1 ){
2410 zRet = fts5PrintfAppend(zRet, "NEAR(");
2411 if( zRet==0 ) return 0;
2412 }
2413
2414 for(i=0; i<pNear->nPhrase; i++){
2415 Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
2416 if( i!=0 ){
2417 zRet = fts5PrintfAppend(zRet, " ");
2418 if( zRet==0 ) return 0;
2419 }
2420 for(iTerm=0; iTerm<pPhrase->nTerm; iTerm++){
2421 char *zTerm = fts5ExprTermPrint(&pPhrase->aTerm[iTerm]);
2422 if( zTerm ){
2423 zRet = fts5PrintfAppend(zRet, "%s%s", iTerm==0?"":" + ", zTerm);
2424 sqlite3_free(zTerm);
2425 }
2426 if( zTerm==0 || zRet==0 ){
2427 sqlite3_free(zRet);
2428 return 0;
2429 }
2430 }
2431 }
2432
2433 if( pNear->nPhrase>1 ){
2434 zRet = fts5PrintfAppend(zRet, ", %d)", pNear->nNear);
2435 if( zRet==0 ) return 0;
2436 }
2437
2438 }else{
2439 char const *zOp = 0;
2440 int i;
2441
2442 switch( pExpr->eType ){
2443 case FTS5_AND: zOp = " AND "; break;
2444 case FTS5_NOT: zOp = " NOT "; break;
2445 default:
2446 assert( pExpr->eType==FTS5_OR );
2447 zOp = " OR ";
2448 break;
2449 }
2450
2451 for(i=0; i<pExpr->nChild; i++){
2452 char *z = fts5ExprPrint(pConfig, pExpr->apChild[i]);
2453 if( z==0 ){
2454 sqlite3_free(zRet);
2455 zRet = 0;
2456 }else{
2457 int e = pExpr->apChild[i]->eType;
2458 int b = (e!=FTS5_STRING && e!=FTS5_TERM && e!=FTS5_EOF);
2459 zRet = fts5PrintfAppend(zRet, "%s%s%z%s",
2460 (i==0 ? "" : zOp),
2461 (b?"(":""), z, (b?")":"")
2462 );
2463 }
2464 if( zRet==0 ) break;
2465 }
2466 }
2467
2468 return zRet;
2469 }
2470
2471 /*
2472 ** The implementation of user-defined scalar functions fts5_expr() (bTcl==0)
2473 ** and fts5_expr_tcl() (bTcl!=0).
2474 */
fts5ExprFunction(sqlite3_context * pCtx,int nArg,sqlite3_value ** apVal,int bTcl)2475 static void fts5ExprFunction(
2476 sqlite3_context *pCtx, /* Function call context */
2477 int nArg, /* Number of args */
2478 sqlite3_value **apVal, /* Function arguments */
2479 int bTcl
2480 ){
2481 Fts5Global *pGlobal = (Fts5Global*)sqlite3_user_data(pCtx);
2482 sqlite3 *db = sqlite3_context_db_handle(pCtx);
2483 const char *zExpr = 0;
2484 char *zErr = 0;
2485 Fts5Expr *pExpr = 0;
2486 int rc;
2487 int i;
2488
2489 const char **azConfig; /* Array of arguments for Fts5Config */
2490 const char *zNearsetCmd = "nearset";
2491 int nConfig; /* Size of azConfig[] */
2492 Fts5Config *pConfig = 0;
2493 int iArg = 1;
2494
2495 if( nArg<1 ){
2496 zErr = sqlite3_mprintf("wrong number of arguments to function %s",
2497 bTcl ? "fts5_expr_tcl" : "fts5_expr"
2498 );
2499 sqlite3_result_error(pCtx, zErr, -1);
2500 sqlite3_free(zErr);
2501 return;
2502 }
2503
2504 if( bTcl && nArg>1 ){
2505 zNearsetCmd = (const char*)sqlite3_value_text(apVal[1]);
2506 iArg = 2;
2507 }
2508
2509 nConfig = 3 + (nArg-iArg);
2510 azConfig = (const char**)sqlite3_malloc64(sizeof(char*) * nConfig);
2511 if( azConfig==0 ){
2512 sqlite3_result_error_nomem(pCtx);
2513 return;
2514 }
2515 azConfig[0] = 0;
2516 azConfig[1] = "main";
2517 azConfig[2] = "tbl";
2518 for(i=3; iArg<nArg; iArg++){
2519 const char *z = (const char*)sqlite3_value_text(apVal[iArg]);
2520 azConfig[i++] = (z ? z : "");
2521 }
2522
2523 zExpr = (const char*)sqlite3_value_text(apVal[0]);
2524 if( zExpr==0 ) zExpr = "";
2525
2526 rc = sqlite3Fts5ConfigParse(pGlobal, db, nConfig, azConfig, &pConfig, &zErr);
2527 if( rc==SQLITE_OK ){
2528 rc = sqlite3Fts5ExprNew(pConfig, pConfig->nCol, zExpr, &pExpr, &zErr);
2529 }
2530 if( rc==SQLITE_OK ){
2531 char *zText;
2532 if( pExpr->pRoot->xNext==0 ){
2533 zText = sqlite3_mprintf("");
2534 }else if( bTcl ){
2535 zText = fts5ExprPrintTcl(pConfig, zNearsetCmd, pExpr->pRoot);
2536 }else{
2537 zText = fts5ExprPrint(pConfig, pExpr->pRoot);
2538 }
2539 if( zText==0 ){
2540 rc = SQLITE_NOMEM;
2541 }else{
2542 sqlite3_result_text(pCtx, zText, -1, SQLITE_TRANSIENT);
2543 sqlite3_free(zText);
2544 }
2545 }
2546
2547 if( rc!=SQLITE_OK ){
2548 if( zErr ){
2549 sqlite3_result_error(pCtx, zErr, -1);
2550 sqlite3_free(zErr);
2551 }else{
2552 sqlite3_result_error_code(pCtx, rc);
2553 }
2554 }
2555 sqlite3_free((void *)azConfig);
2556 sqlite3Fts5ConfigFree(pConfig);
2557 sqlite3Fts5ExprFree(pExpr);
2558 }
2559
fts5ExprFunctionHr(sqlite3_context * pCtx,int nArg,sqlite3_value ** apVal)2560 static void fts5ExprFunctionHr(
2561 sqlite3_context *pCtx, /* Function call context */
2562 int nArg, /* Number of args */
2563 sqlite3_value **apVal /* Function arguments */
2564 ){
2565 fts5ExprFunction(pCtx, nArg, apVal, 0);
2566 }
fts5ExprFunctionTcl(sqlite3_context * pCtx,int nArg,sqlite3_value ** apVal)2567 static void fts5ExprFunctionTcl(
2568 sqlite3_context *pCtx, /* Function call context */
2569 int nArg, /* Number of args */
2570 sqlite3_value **apVal /* Function arguments */
2571 ){
2572 fts5ExprFunction(pCtx, nArg, apVal, 1);
2573 }
2574
2575 /*
2576 ** The implementation of an SQLite user-defined-function that accepts a
2577 ** single integer as an argument. If the integer is an alpha-numeric
2578 ** unicode code point, 1 is returned. Otherwise 0.
2579 */
fts5ExprIsAlnum(sqlite3_context * pCtx,int nArg,sqlite3_value ** apVal)2580 static void fts5ExprIsAlnum(
2581 sqlite3_context *pCtx, /* Function call context */
2582 int nArg, /* Number of args */
2583 sqlite3_value **apVal /* Function arguments */
2584 ){
2585 int iCode;
2586 u8 aArr[32];
2587 if( nArg!=1 ){
2588 sqlite3_result_error(pCtx,
2589 "wrong number of arguments to function fts5_isalnum", -1
2590 );
2591 return;
2592 }
2593 memset(aArr, 0, sizeof(aArr));
2594 sqlite3Fts5UnicodeCatParse("L*", aArr);
2595 sqlite3Fts5UnicodeCatParse("N*", aArr);
2596 sqlite3Fts5UnicodeCatParse("Co", aArr);
2597 iCode = sqlite3_value_int(apVal[0]);
2598 sqlite3_result_int(pCtx, aArr[sqlite3Fts5UnicodeCategory((u32)iCode)]);
2599 }
2600
fts5ExprFold(sqlite3_context * pCtx,int nArg,sqlite3_value ** apVal)2601 static void fts5ExprFold(
2602 sqlite3_context *pCtx, /* Function call context */
2603 int nArg, /* Number of args */
2604 sqlite3_value **apVal /* Function arguments */
2605 ){
2606 if( nArg!=1 && nArg!=2 ){
2607 sqlite3_result_error(pCtx,
2608 "wrong number of arguments to function fts5_fold", -1
2609 );
2610 }else{
2611 int iCode;
2612 int bRemoveDiacritics = 0;
2613 iCode = sqlite3_value_int(apVal[0]);
2614 if( nArg==2 ) bRemoveDiacritics = sqlite3_value_int(apVal[1]);
2615 sqlite3_result_int(pCtx, sqlite3Fts5UnicodeFold(iCode, bRemoveDiacritics));
2616 }
2617 }
2618
2619 /*
2620 ** This is called during initialization to register the fts5_expr() scalar
2621 ** UDF with the SQLite handle passed as the only argument.
2622 */
sqlite3Fts5ExprInit(Fts5Global * pGlobal,sqlite3 * db)2623 int sqlite3Fts5ExprInit(Fts5Global *pGlobal, sqlite3 *db){
2624 struct Fts5ExprFunc {
2625 const char *z;
2626 void (*x)(sqlite3_context*,int,sqlite3_value**);
2627 } aFunc[] = {
2628 { "fts5_expr", fts5ExprFunctionHr },
2629 { "fts5_expr_tcl", fts5ExprFunctionTcl },
2630 { "fts5_isalnum", fts5ExprIsAlnum },
2631 { "fts5_fold", fts5ExprFold },
2632 };
2633 int i;
2634 int rc = SQLITE_OK;
2635 void *pCtx = (void*)pGlobal;
2636
2637 for(i=0; rc==SQLITE_OK && i<ArraySize(aFunc); i++){
2638 struct Fts5ExprFunc *p = &aFunc[i];
2639 rc = sqlite3_create_function(db, p->z, -1, SQLITE_UTF8, pCtx, p->x, 0, 0);
2640 }
2641
2642 /* Avoid warnings indicating that sqlite3Fts5ParserTrace() and
2643 ** sqlite3Fts5ParserFallback() are unused */
2644 #ifndef NDEBUG
2645 (void)sqlite3Fts5ParserTrace;
2646 #endif
2647 (void)sqlite3Fts5ParserFallback;
2648
2649 return rc;
2650 }
2651
2652 /*
2653 ** Return the number of phrases in expression pExpr.
2654 */
sqlite3Fts5ExprPhraseCount(Fts5Expr * pExpr)2655 int sqlite3Fts5ExprPhraseCount(Fts5Expr *pExpr){
2656 return (pExpr ? pExpr->nPhrase : 0);
2657 }
2658
2659 /*
2660 ** Return the number of terms in the iPhrase'th phrase in pExpr.
2661 */
sqlite3Fts5ExprPhraseSize(Fts5Expr * pExpr,int iPhrase)2662 int sqlite3Fts5ExprPhraseSize(Fts5Expr *pExpr, int iPhrase){
2663 if( iPhrase<0 || iPhrase>=pExpr->nPhrase ) return 0;
2664 return pExpr->apExprPhrase[iPhrase]->nTerm;
2665 }
2666
2667 /*
2668 ** This function is used to access the current position list for phrase
2669 ** iPhrase.
2670 */
sqlite3Fts5ExprPoslist(Fts5Expr * pExpr,int iPhrase,const u8 ** pa)2671 int sqlite3Fts5ExprPoslist(Fts5Expr *pExpr, int iPhrase, const u8 **pa){
2672 int nRet;
2673 Fts5ExprPhrase *pPhrase = pExpr->apExprPhrase[iPhrase];
2674 Fts5ExprNode *pNode = pPhrase->pNode;
2675 if( pNode->bEof==0 && pNode->iRowid==pExpr->pRoot->iRowid ){
2676 *pa = pPhrase->poslist.p;
2677 nRet = pPhrase->poslist.n;
2678 }else{
2679 *pa = 0;
2680 nRet = 0;
2681 }
2682 return nRet;
2683 }
2684
2685 struct Fts5PoslistPopulator {
2686 Fts5PoslistWriter writer;
2687 int bOk; /* True if ok to populate */
2688 int bMiss;
2689 };
2690
sqlite3Fts5ExprClearPoslists(Fts5Expr * pExpr,int bLive)2691 Fts5PoslistPopulator *sqlite3Fts5ExprClearPoslists(Fts5Expr *pExpr, int bLive){
2692 Fts5PoslistPopulator *pRet;
2693 pRet = sqlite3_malloc64(sizeof(Fts5PoslistPopulator)*pExpr->nPhrase);
2694 if( pRet ){
2695 int i;
2696 memset(pRet, 0, sizeof(Fts5PoslistPopulator)*pExpr->nPhrase);
2697 for(i=0; i<pExpr->nPhrase; i++){
2698 Fts5Buffer *pBuf = &pExpr->apExprPhrase[i]->poslist;
2699 Fts5ExprNode *pNode = pExpr->apExprPhrase[i]->pNode;
2700 assert( pExpr->apExprPhrase[i]->nTerm==1 );
2701 if( bLive &&
2702 (pBuf->n==0 || pNode->iRowid!=pExpr->pRoot->iRowid || pNode->bEof)
2703 ){
2704 pRet[i].bMiss = 1;
2705 }else{
2706 pBuf->n = 0;
2707 }
2708 }
2709 }
2710 return pRet;
2711 }
2712
2713 struct Fts5ExprCtx {
2714 Fts5Expr *pExpr;
2715 Fts5PoslistPopulator *aPopulator;
2716 i64 iOff;
2717 };
2718 typedef struct Fts5ExprCtx Fts5ExprCtx;
2719
2720 /*
2721 ** TODO: Make this more efficient!
2722 */
fts5ExprColsetTest(Fts5Colset * pColset,int iCol)2723 static int fts5ExprColsetTest(Fts5Colset *pColset, int iCol){
2724 int i;
2725 for(i=0; i<pColset->nCol; i++){
2726 if( pColset->aiCol[i]==iCol ) return 1;
2727 }
2728 return 0;
2729 }
2730
fts5ExprPopulatePoslistsCb(void * pCtx,int tflags,const char * pToken,int nToken,int iUnused1,int iUnused2)2731 static int fts5ExprPopulatePoslistsCb(
2732 void *pCtx, /* Copy of 2nd argument to xTokenize() */
2733 int tflags, /* Mask of FTS5_TOKEN_* flags */
2734 const char *pToken, /* Pointer to buffer containing token */
2735 int nToken, /* Size of token in bytes */
2736 int iUnused1, /* Byte offset of token within input text */
2737 int iUnused2 /* Byte offset of end of token within input text */
2738 ){
2739 Fts5ExprCtx *p = (Fts5ExprCtx*)pCtx;
2740 Fts5Expr *pExpr = p->pExpr;
2741 int i;
2742
2743 UNUSED_PARAM2(iUnused1, iUnused2);
2744
2745 if( nToken>FTS5_MAX_TOKEN_SIZE ) nToken = FTS5_MAX_TOKEN_SIZE;
2746 if( (tflags & FTS5_TOKEN_COLOCATED)==0 ) p->iOff++;
2747 for(i=0; i<pExpr->nPhrase; i++){
2748 Fts5ExprTerm *pTerm;
2749 if( p->aPopulator[i].bOk==0 ) continue;
2750 for(pTerm=&pExpr->apExprPhrase[i]->aTerm[0]; pTerm; pTerm=pTerm->pSynonym){
2751 int nTerm = (int)strlen(pTerm->zTerm);
2752 if( (nTerm==nToken || (nTerm<nToken && pTerm->bPrefix))
2753 && memcmp(pTerm->zTerm, pToken, nTerm)==0
2754 ){
2755 int rc = sqlite3Fts5PoslistWriterAppend(
2756 &pExpr->apExprPhrase[i]->poslist, &p->aPopulator[i].writer, p->iOff
2757 );
2758 if( rc ) return rc;
2759 break;
2760 }
2761 }
2762 }
2763 return SQLITE_OK;
2764 }
2765
sqlite3Fts5ExprPopulatePoslists(Fts5Config * pConfig,Fts5Expr * pExpr,Fts5PoslistPopulator * aPopulator,int iCol,const char * z,int n)2766 int sqlite3Fts5ExprPopulatePoslists(
2767 Fts5Config *pConfig,
2768 Fts5Expr *pExpr,
2769 Fts5PoslistPopulator *aPopulator,
2770 int iCol,
2771 const char *z, int n
2772 ){
2773 int i;
2774 Fts5ExprCtx sCtx;
2775 sCtx.pExpr = pExpr;
2776 sCtx.aPopulator = aPopulator;
2777 sCtx.iOff = (((i64)iCol) << 32) - 1;
2778
2779 for(i=0; i<pExpr->nPhrase; i++){
2780 Fts5ExprNode *pNode = pExpr->apExprPhrase[i]->pNode;
2781 Fts5Colset *pColset = pNode->pNear->pColset;
2782 if( (pColset && 0==fts5ExprColsetTest(pColset, iCol))
2783 || aPopulator[i].bMiss
2784 ){
2785 aPopulator[i].bOk = 0;
2786 }else{
2787 aPopulator[i].bOk = 1;
2788 }
2789 }
2790
2791 return sqlite3Fts5Tokenize(pConfig,
2792 FTS5_TOKENIZE_DOCUMENT, z, n, (void*)&sCtx, fts5ExprPopulatePoslistsCb
2793 );
2794 }
2795
fts5ExprClearPoslists(Fts5ExprNode * pNode)2796 static void fts5ExprClearPoslists(Fts5ExprNode *pNode){
2797 if( pNode->eType==FTS5_TERM || pNode->eType==FTS5_STRING ){
2798 pNode->pNear->apPhrase[0]->poslist.n = 0;
2799 }else{
2800 int i;
2801 for(i=0; i<pNode->nChild; i++){
2802 fts5ExprClearPoslists(pNode->apChild[i]);
2803 }
2804 }
2805 }
2806
fts5ExprCheckPoslists(Fts5ExprNode * pNode,i64 iRowid)2807 static int fts5ExprCheckPoslists(Fts5ExprNode *pNode, i64 iRowid){
2808 pNode->iRowid = iRowid;
2809 pNode->bEof = 0;
2810 switch( pNode->eType ){
2811 case FTS5_TERM:
2812 case FTS5_STRING:
2813 return (pNode->pNear->apPhrase[0]->poslist.n>0);
2814
2815 case FTS5_AND: {
2816 int i;
2817 for(i=0; i<pNode->nChild; i++){
2818 if( fts5ExprCheckPoslists(pNode->apChild[i], iRowid)==0 ){
2819 fts5ExprClearPoslists(pNode);
2820 return 0;
2821 }
2822 }
2823 break;
2824 }
2825
2826 case FTS5_OR: {
2827 int i;
2828 int bRet = 0;
2829 for(i=0; i<pNode->nChild; i++){
2830 if( fts5ExprCheckPoslists(pNode->apChild[i], iRowid) ){
2831 bRet = 1;
2832 }
2833 }
2834 return bRet;
2835 }
2836
2837 default: {
2838 assert( pNode->eType==FTS5_NOT );
2839 if( 0==fts5ExprCheckPoslists(pNode->apChild[0], iRowid)
2840 || 0!=fts5ExprCheckPoslists(pNode->apChild[1], iRowid)
2841 ){
2842 fts5ExprClearPoslists(pNode);
2843 return 0;
2844 }
2845 break;
2846 }
2847 }
2848 return 1;
2849 }
2850
sqlite3Fts5ExprCheckPoslists(Fts5Expr * pExpr,i64 iRowid)2851 void sqlite3Fts5ExprCheckPoslists(Fts5Expr *pExpr, i64 iRowid){
2852 fts5ExprCheckPoslists(pExpr->pRoot, iRowid);
2853 }
2854
2855 /*
2856 ** This function is only called for detail=columns tables.
2857 */
sqlite3Fts5ExprPhraseCollist(Fts5Expr * pExpr,int iPhrase,const u8 ** ppCollist,int * pnCollist)2858 int sqlite3Fts5ExprPhraseCollist(
2859 Fts5Expr *pExpr,
2860 int iPhrase,
2861 const u8 **ppCollist,
2862 int *pnCollist
2863 ){
2864 Fts5ExprPhrase *pPhrase = pExpr->apExprPhrase[iPhrase];
2865 Fts5ExprNode *pNode = pPhrase->pNode;
2866 int rc = SQLITE_OK;
2867
2868 assert( iPhrase>=0 && iPhrase<pExpr->nPhrase );
2869 assert( pExpr->pConfig->eDetail==FTS5_DETAIL_COLUMNS );
2870
2871 if( pNode->bEof==0
2872 && pNode->iRowid==pExpr->pRoot->iRowid
2873 && pPhrase->poslist.n>0
2874 ){
2875 Fts5ExprTerm *pTerm = &pPhrase->aTerm[0];
2876 if( pTerm->pSynonym ){
2877 Fts5Buffer *pBuf = (Fts5Buffer*)&pTerm->pSynonym[1];
2878 rc = fts5ExprSynonymList(
2879 pTerm, pNode->iRowid, pBuf, (u8**)ppCollist, pnCollist
2880 );
2881 }else{
2882 *ppCollist = pPhrase->aTerm[0].pIter->pData;
2883 *pnCollist = pPhrase->aTerm[0].pIter->nData;
2884 }
2885 }else{
2886 *ppCollist = 0;
2887 *pnCollist = 0;
2888 }
2889
2890 return rc;
2891 }
2892