Debian Codegraph @

ext/fts5/fts5_expr.c

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