Debian Codegraph @

ext/fts3/fts3_expr.c

raw
1 /*
2 ** 2008 Nov 28
3 **
4 ** The author disclaims copyright to this source code. In place of
5 ** a legal notice, here is a blessing:
6 **
7 ** May you do good and not evil.
8 ** May you find forgiveness for yourself and forgive others.
9 ** May you share freely, never taking more than you give.
10 **
11 ******************************************************************************
12 **
13 ** This module contains code that implements a parser for fts3 query strings
14 ** (the right-hand argument to the MATCH operator). Because the supported
15 ** syntax is relatively simple, the whole tokenizer/parser system is
16 ** hand-coded.
17 */
18 #include "fts3Int.h"
19 #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)
20
21 /*
22 ** By default, this module parses the legacy syntax that has been
23 ** traditionally used by fts3. Or, if SQLITE_ENABLE_FTS3_PARENTHESIS
24 ** is defined, then it uses the new syntax. The differences between
25 ** the new and the old syntaxes are:
26 **
27 ** a) The new syntax supports parenthesis. The old does not.
28 **
29 ** b) The new syntax supports the AND and NOT operators. The old does not.
30 **
31 ** c) The old syntax supports the "-" token qualifier. This is not
32 ** supported by the new syntax (it is replaced by the NOT operator).
33 **
34 ** d) When using the old syntax, the OR operator has a greater precedence
35 ** than an implicit AND. When using the new, both implicity and explicit
36 ** AND operators have a higher precedence than OR.
37 **
38 ** If compiled with SQLITE_TEST defined, then this module exports the
39 ** symbol "int sqlite3_fts3_enable_parentheses". Setting this variable
40 ** to zero causes the module to use the old syntax. If it is set to
41 ** non-zero the new syntax is activated. This is so both syntaxes can
42 ** be tested using a single build of testfixture.
43 **
44 ** The following describes the syntax supported by the fts3 MATCH
45 ** operator in a similar format to that used by the lemon parser
46 ** generator. This module does not use actually lemon, it uses a
47 ** custom parser.
48 **
49 ** query ::= andexpr (OR andexpr)*.
50 **
51 ** andexpr ::= notexpr (AND? notexpr)*.
52 **
53 ** notexpr ::= nearexpr (NOT nearexpr|-TOKEN)*.
54 ** notexpr ::= LP query RP.
55 **
56 ** nearexpr ::= phrase (NEAR distance_opt nearexpr)*.
57 **
58 ** distance_opt ::= .
59 ** distance_opt ::= / INTEGER.
60 **
61 ** phrase ::= TOKEN.
62 ** phrase ::= COLUMN:TOKEN.
63 ** phrase ::= "TOKEN TOKEN TOKEN...".
64 */
65
66 #ifdef SQLITE_TEST
67 int sqlite3_fts3_enable_parentheses = 0;
68 #else
69 # ifdef SQLITE_ENABLE_FTS3_PARENTHESIS
70 # define sqlite3_fts3_enable_parentheses 1
71 # else
72 # define sqlite3_fts3_enable_parentheses 0
73 # endif
74 #endif
75
76 /*
77 ** Default span for NEAR operators.
78 */
79 #define SQLITE_FTS3_DEFAULT_NEAR_PARAM 10
80
81 #include <string.h>
82 #include <assert.h>
83
84 /*
85 ** isNot:
86 ** This variable is used by function getNextNode(). When getNextNode() is
87 ** called, it sets ParseContext.isNot to true if the 'next node' is a
88 ** FTSQUERY_PHRASE with a unary "-" attached to it. i.e. "mysql" in the
89 ** FTS3 query "sqlite -mysql". Otherwise, ParseContext.isNot is set to
90 ** zero.
91 */
92 typedef struct ParseContext ParseContext;
93 struct ParseContext {
94 sqlite3_tokenizer *pTokenizer; /* Tokenizer module */
95 int iLangid; /* Language id used with tokenizer */
96 const char **azCol; /* Array of column names for fts3 table */
97 int bFts4; /* True to allow FTS4-only syntax */
98 int nCol; /* Number of entries in azCol[] */
99 int iDefaultCol; /* Default column to query */
100 int isNot; /* True if getNextNode() sees a unary - */
101 sqlite3_context *pCtx; /* Write error message here */
102 int nNest; /* Number of nested brackets */
103 };
104
105 /*
106 ** This function is equivalent to the standard isspace() function.
107 **
108 ** The standard isspace() can be awkward to use safely, because although it
109 ** is defined to accept an argument of type int, its behavior when passed
110 ** an integer that falls outside of the range of the unsigned char type
111 ** is undefined (and sometimes, "undefined" means segfault). This wrapper
112 ** is defined to accept an argument of type char, and always returns 0 for
113 ** any values that fall outside of the range of the unsigned char type (i.e.
114 ** negative values).
115 */
116 static int fts3isspace(char c){
117 return c==' ' || c=='\t' || c=='\n' || c=='\r' || c=='\v' || c=='\f';
118 }
119
120 /*
121 ** Allocate nByte bytes of memory using sqlite3_malloc(). If successful,
122 ** zero the memory before returning a pointer to it. If unsuccessful,
123 ** return NULL.
124 */
125 void *sqlite3Fts3MallocZero(sqlite3_int64 nByte){
126 void *pRet = sqlite3_malloc64(nByte);
127 if( pRet ) memset(pRet, 0, nByte);
128 return pRet;
129 }
130
131 int sqlite3Fts3OpenTokenizer(
132 sqlite3_tokenizer *pTokenizer,
133 int iLangid,
134 const char *z,
135 int n,
136 sqlite3_tokenizer_cursor **ppCsr
137 ){
138 sqlite3_tokenizer_module const *pModule = pTokenizer->pModule;
139 sqlite3_tokenizer_cursor *pCsr = 0;
140 int rc;
141
142 rc = pModule->xOpen(pTokenizer, z, n, &pCsr);
143 assert( rc==SQLITE_OK || pCsr==0 );
144 if( rc==SQLITE_OK ){
145 pCsr->pTokenizer = pTokenizer;
146 if( pModule->iVersion>=1 ){
147 rc = pModule->xLanguageid(pCsr, iLangid);
148 if( rc!=SQLITE_OK ){
149 pModule->xClose(pCsr);
150 pCsr = 0;
151 }
152 }
153 }
154 *ppCsr = pCsr;
155 return rc;
156 }
157
158 /*
159 ** Function getNextNode(), which is called by fts3ExprParse(), may itself
160 ** call fts3ExprParse(). So this forward declaration is required.
161 */
162 static int fts3ExprParse(ParseContext *, const char *, int, Fts3Expr **, int *);
163
164 /*
165 ** Search buffer z[], size n, for a '"' character. Or, if enable_parenthesis
166 ** is defined, search for '(' and ')' as well. Return the index of the first
167 ** such character in the buffer. If there is no such character, return -1.
168 */
169 static int findBarredChar(const char *z, int n){
170 int ii;
171 for(ii=0; ii<n; ii++){
172 if( (z[ii]=='"')
173 || (sqlite3_fts3_enable_parentheses && (z[ii]=='(' || z[ii]==')'))
174 ){
175 return ii;
176 }
177 }
178 return -1;
179 }
180
181 /*
182 ** Extract the next token from buffer z (length n) using the tokenizer
183 ** and other information (column names etc.) in pParse. Create an Fts3Expr
184 ** structure of type FTSQUERY_PHRASE containing a phrase consisting of this
185 ** single token and set *ppExpr to point to it. If the end of the buffer is
186 ** reached before a token is found, set *ppExpr to zero. It is the
187 ** responsibility of the caller to eventually deallocate the allocated
188 ** Fts3Expr structure (if any) by passing it to sqlite3_free().
189 **
190 ** Return SQLITE_OK if successful, or SQLITE_NOMEM if a memory allocation
191 ** fails.
192 */
193 static int getNextToken(
194 ParseContext *pParse, /* fts3 query parse context */
195 int iCol, /* Value for Fts3Phrase.iColumn */
196 const char *z, int n, /* Input string */
197 Fts3Expr **ppExpr, /* OUT: expression */
198 int *pnConsumed /* OUT: Number of bytes consumed */
199 ){
200 sqlite3_tokenizer *pTokenizer = pParse->pTokenizer;
201 sqlite3_tokenizer_module const *pModule = pTokenizer->pModule;
202 int rc;
203 sqlite3_tokenizer_cursor *pCursor;
204 Fts3Expr *pRet = 0;
205
206 *pnConsumed = n;
207 rc = sqlite3Fts3OpenTokenizer(pTokenizer, pParse->iLangid, z, n, &pCursor);
208 if( rc==SQLITE_OK ){
209 const char *zToken;
210 int nToken = 0, iStart = 0, iEnd = 0, iPosition = 0;
211 sqlite3_int64 nByte; /* total space to allocate */
212
213 rc = pModule->xNext(pCursor, &zToken, &nToken, &iStart, &iEnd, &iPosition);
214 if( rc==SQLITE_OK ){
215 /* Check that this tokenization did not gobble up any " characters. Or,
216 ** if enable_parenthesis is true, that it did not gobble up any
217 ** open or close parenthesis characters either. If it did, call
218 ** getNextToken() again, but pass only that part of the input buffer
219 ** up to the first such character. */
220 int iBarred = findBarredChar(z, iEnd);
221 if( iBarred>=0 ){
222 pModule->xClose(pCursor);
223 return getNextToken(pParse, iCol, z, iBarred, ppExpr, pnConsumed);
224 }
225
226 nByte = sizeof(Fts3Expr) + SZ_FTS3PHRASE(1) + nToken;
227 pRet = (Fts3Expr *)sqlite3Fts3MallocZero(nByte);
228 if( !pRet ){
229 rc = SQLITE_NOMEM;
230 }else{
231 pRet->eType = FTSQUERY_PHRASE;
232 pRet->pPhrase = (Fts3Phrase *)&pRet[1];
233 pRet->pPhrase->nToken = 1;
234 pRet->pPhrase->iColumn = iCol;
235 pRet->pPhrase->aToken[0].n = nToken;
236 pRet->pPhrase->aToken[0].z = (char*)&pRet->pPhrase->aToken[1];
237 memcpy(pRet->pPhrase->aToken[0].z, zToken, nToken);
238
239 if( iEnd<n && z[iEnd]=='*' ){
240 pRet->pPhrase->aToken[0].isPrefix = 1;
241 iEnd++;
242 }
243
244 while( 1 ){
245 if( !sqlite3_fts3_enable_parentheses
246 && iStart>0 && z[iStart-1]=='-'
247 ){
248 pParse->isNot = 1;
249 iStart--;
250 }else if( pParse->bFts4 && iStart>0 && z[iStart-1]=='^' ){
251 pRet->pPhrase->aToken[0].bFirst = 1;
252 iStart--;
253 }else{
254 break;
255 }
256 }
257
258 }
259 *pnConsumed = iEnd;
260 }else if( n && rc==SQLITE_DONE ){
261 int iBarred = findBarredChar(z, n);
262 if( iBarred>=0 ){
263 *pnConsumed = iBarred;
264 }
265 rc = SQLITE_OK;
266 }
267
268 pModule->xClose(pCursor);
269 }
270
271 *ppExpr = pRet;
272 return rc;
273 }
274
275
276 /*
277 ** Enlarge a memory allocation. If an out-of-memory allocation occurs,
278 ** then free the old allocation.
279 */
280 static void *fts3ReallocOrFree(void *pOrig, sqlite3_int64 nNew){
281 void *pRet = sqlite3_realloc64(pOrig, nNew);
282 if( !pRet ){
283 sqlite3_free(pOrig);
284 }
285 return pRet;
286 }
287
288 /*
289 ** Buffer zInput, length nInput, contains the contents of a quoted string
290 ** that appeared as part of an fts3 query expression. Neither quote character
291 ** is included in the buffer. This function attempts to tokenize the entire
292 ** input buffer and create an Fts3Expr structure of type FTSQUERY_PHRASE
293 ** containing the results.
294 **
295 ** If successful, SQLITE_OK is returned and *ppExpr set to point at the
296 ** allocated Fts3Expr structure. Otherwise, either SQLITE_NOMEM (out of memory
297 ** error) or SQLITE_ERROR (tokenization error) is returned and *ppExpr set
298 ** to 0.
299 */
300 static int getNextString(
301 ParseContext *pParse, /* fts3 query parse context */
302 const char *zInput, int nInput, /* Input string */
303 Fts3Expr **ppExpr /* OUT: expression */
304 ){
305 sqlite3_tokenizer *pTokenizer = pParse->pTokenizer;
306 sqlite3_tokenizer_module const *pModule = pTokenizer->pModule;
307 int rc;
308 Fts3Expr *p = 0;
309 sqlite3_tokenizer_cursor *pCursor = 0;
310 char *zTemp = 0;
311 i64 nTemp = 0;
312
313 const int nSpace = sizeof(Fts3Expr) + SZ_FTS3PHRASE(1);
314 int nToken = 0;
315
316 /* The final Fts3Expr data structure, including the Fts3Phrase,
317 ** Fts3PhraseToken structures token buffers are all stored as a single
318 ** allocation so that the expression can be freed with a single call to
319 ** sqlite3_free(). Setting this up requires a two pass approach.
320 **
321 ** The first pass, in the block below, uses a tokenizer cursor to iterate
322 ** through the tokens in the expression. This pass uses fts3ReallocOrFree()
323 ** to assemble data in two dynamic buffers:
324 **
325 ** Buffer p: Points to the Fts3Expr structure, followed by the Fts3Phrase
326 ** structure, followed by the array of Fts3PhraseToken
327 ** structures. This pass only populates the Fts3PhraseToken array.
328 **
329 ** Buffer zTemp: Contains copies of all tokens.
330 **
331 ** The second pass, in the block that begins "if( rc==SQLITE_DONE )" below,
332 ** appends buffer zTemp to buffer p, and fills in the Fts3Expr and Fts3Phrase
333 ** structures.
334 */
335 rc = sqlite3Fts3OpenTokenizer(
336 pTokenizer, pParse->iLangid, zInput, nInput, &pCursor);
337 if( rc==SQLITE_OK ){
338 int ii;
339 for(ii=0; rc==SQLITE_OK; ii++){
340 const char *zByte;
341 int nByte = 0, iBegin = 0, iEnd = 0, iPos = 0;
342 rc = pModule->xNext(pCursor, &zByte, &nByte, &iBegin, &iEnd, &iPos);
343 if( rc==SQLITE_OK ){
344 Fts3PhraseToken *pToken;
345
346 p = fts3ReallocOrFree(p, nSpace + ii*sizeof(Fts3PhraseToken));
347 zTemp = fts3ReallocOrFree(zTemp, nTemp + nByte);
348 if( !zTemp || !p ){
349 rc = SQLITE_NOMEM;
350 goto getnextstring_out;
351 }
352
353 assert( nToken==ii );
354 pToken = &((Fts3Phrase *)(&p[1]))->aToken[ii];
355 memset(pToken, 0, sizeof(Fts3PhraseToken));
356
357 memcpy(&zTemp[nTemp], zByte, nByte);
358 nTemp += nByte;
359
360 pToken->n = nByte;
361 pToken->isPrefix = (iEnd<nInput && zInput[iEnd]=='*');
362 pToken->bFirst = (iBegin>0 && zInput[iBegin-1]=='^');
363 nToken = ii+1;
364 }
365 }
366 }
367
368 if( rc==SQLITE_DONE ){
369 int jj;
370 char *zBuf = 0;
371
372 p = fts3ReallocOrFree(p, nSpace + nToken*sizeof(Fts3PhraseToken) + nTemp);
373 if( !p ){
374 rc = SQLITE_NOMEM;
375 goto getnextstring_out;
376 }
377 memset(p, 0, (char *)&(((Fts3Phrase *)&p[1])->aToken[0])-(char *)p);
378 p->eType = FTSQUERY_PHRASE;
379 p->pPhrase = (Fts3Phrase *)&p[1];
380 p->pPhrase->iColumn = pParse->iDefaultCol;
381 p->pPhrase->nToken = nToken;
382
383 zBuf = (char *)&p->pPhrase->aToken[nToken];
384 assert( nTemp==0 || zTemp );
385 if( zTemp ){
386 memcpy(zBuf, zTemp, nTemp);
387 }
388
389 for(jj=0; jj<p->pPhrase->nToken; jj++){
390 p->pPhrase->aToken[jj].z = zBuf;
391 zBuf += p->pPhrase->aToken[jj].n;
392 }
393 rc = SQLITE_OK;
394 }
395
396 getnextstring_out:
397 if( pCursor ){
398 pModule->xClose(pCursor);
399 }
400 sqlite3_free(zTemp);
401 if( rc!=SQLITE_OK ){
402 sqlite3_free(p);
403 p = 0;
404 }
405 *ppExpr = p;
406 return rc;
407 }
408
409 /*
410 ** The output variable *ppExpr is populated with an allocated Fts3Expr
411 ** structure, or set to 0 if the end of the input buffer is reached.
412 **
413 ** Returns an SQLite error code. SQLITE_OK if everything works, SQLITE_NOMEM
414 ** if a malloc failure occurs, or SQLITE_ERROR if a parse error is encountered.
415 ** If SQLITE_ERROR is returned, pContext is populated with an error message.
416 */
417 static int getNextNode(
418 ParseContext *pParse, /* fts3 query parse context */
419 const char *z, int n, /* Input string */
420 Fts3Expr **ppExpr, /* OUT: expression */
421 int *pnConsumed /* OUT: Number of bytes consumed */
422 ){
423 static const struct Fts3Keyword {
424 char *z; /* Keyword text */
425 unsigned char n; /* Length of the keyword */
426 unsigned char parenOnly; /* Only valid in paren mode */
427 unsigned char eType; /* Keyword code */
428 } aKeyword[] = {
429 { "OR" , 2, 0, FTSQUERY_OR },
430 { "AND", 3, 1, FTSQUERY_AND },
431 { "NOT", 3, 1, FTSQUERY_NOT },
432 { "NEAR", 4, 0, FTSQUERY_NEAR }
433 };
434 int ii;
435 int iCol;
436 int iColLen;
437 int rc;
438 Fts3Expr *pRet = 0;
439
440 const char *zInput = z;
441 int nInput = n;
442
443 pParse->isNot = 0;
444
445 /* Skip over any whitespace before checking for a keyword, an open or
446 ** close bracket, or a quoted string.
447 */
448 while( nInput>0 && fts3isspace(*zInput) ){
449 nInput--;
450 zInput++;
451 }
452 if( nInput==0 ){
453 return SQLITE_DONE;
454 }
455
456 /* See if we are dealing with a keyword. */
457 for(ii=0; ii<(int)(sizeof(aKeyword)/sizeof(struct Fts3Keyword)); ii++){
458 const struct Fts3Keyword *pKey = &aKeyword[ii];
459
460 if( (pKey->parenOnly & ~sqlite3_fts3_enable_parentheses)!=0 ){
461 continue;
462 }
463
464 if( nInput>=pKey->n && 0==memcmp(zInput, pKey->z, pKey->n) ){
465 int nNear = SQLITE_FTS3_DEFAULT_NEAR_PARAM;
466 int nKey = pKey->n;
467 char cNext;
468
469 /* If this is a "NEAR" keyword, check for an explicit nearness. */
470 if( pKey->eType==FTSQUERY_NEAR ){
471 assert( nKey==4 );
472 if( zInput[4]=='/' && zInput[5]>='0' && zInput[5]<='9' ){
473 nKey += 1+sqlite3Fts3ReadInt(&zInput[nKey+1], &nNear);
474 if( nNear>=1000000000 ) nNear = 1000000000;
475 }
476 }
477
478 /* At this point this is probably a keyword. But for that to be true,
479 ** the next byte must contain either whitespace, an open or close
480 ** parenthesis, a quote character, or EOF.
481 */
482 cNext = zInput[nKey];
483 if( fts3isspace(cNext)
484 || cNext=='"' || cNext=='(' || cNext==')' || cNext==0
485 ){
486 pRet = (Fts3Expr *)sqlite3Fts3MallocZero(sizeof(Fts3Expr));
487 if( !pRet ){
488 return SQLITE_NOMEM;
489 }
490 pRet->eType = pKey->eType;
491 pRet->nNear = nNear;
492 *ppExpr = pRet;
493 *pnConsumed = (int)((zInput - z) + nKey);
494 return SQLITE_OK;
495 }
496
497 /* Turns out that wasn't a keyword after all. This happens if the
498 ** user has supplied a token such as "ORacle". Continue.
499 */
500 }
501 }
502
503 /* See if we are dealing with a quoted phrase. If this is the case, then
504 ** search for the closing quote and pass the whole string to getNextString()
505 ** for processing. This is easy to do, as fts3 has no syntax for escaping
506 ** a quote character embedded in a string.
507 */
508 if( *zInput=='"' ){
509 for(ii=1; ii<nInput && zInput[ii]!='"'; ii++);
510 *pnConsumed = (int)((zInput - z) + ii + 1);
511 if( ii==nInput ){
512 return SQLITE_ERROR;
513 }
514 return getNextString(pParse, &zInput[1], ii-1, ppExpr);
515 }
516
517 if( sqlite3_fts3_enable_parentheses ){
518 if( *zInput=='(' ){
519 int nConsumed = 0;
520 pParse->nNest++;
521 #if !defined(SQLITE_MAX_EXPR_DEPTH)
522 if( pParse->nNest>1000 ) return SQLITE_ERROR;
523 #elif SQLITE_MAX_EXPR_DEPTH>0
524 if( pParse->nNest>SQLITE_MAX_EXPR_DEPTH ) return SQLITE_ERROR;
525 #endif
526 rc = fts3ExprParse(pParse, zInput+1, nInput-1, ppExpr, &nConsumed);
527 *pnConsumed = (int)(zInput - z) + 1 + nConsumed;
528 return rc;
529 }else if( *zInput==')' ){
530 pParse->nNest--;
531 *pnConsumed = (int)((zInput - z) + 1);
532 *ppExpr = 0;
533 return SQLITE_DONE;
534 }
535 }
536
537 /* If control flows to this point, this must be a regular token, or
538 ** the end of the input. Read a regular token using the sqlite3_tokenizer
539 ** interface. Before doing so, figure out if there is an explicit
540 ** column specifier for the token.
541 **
542 ** TODO: Strangely, it is not possible to associate a column specifier
543 ** with a quoted phrase, only with a single token. Not sure if this was
544 ** an implementation artifact or an intentional decision when fts3 was
545 ** first implemented. Whichever it was, this module duplicates the
546 ** limitation.
547 */
548 iCol = pParse->iDefaultCol;
549 iColLen = 0;
550 for(ii=0; ii<pParse->nCol; ii++){
551 const char *zStr = pParse->azCol[ii];
552 int nStr = (int)strlen(zStr);
553 if( nInput>nStr && zInput[nStr]==':'
554 && sqlite3_strnicmp(zStr, zInput, nStr)==0
555 ){
556 iCol = ii;
557 iColLen = (int)((zInput - z) + nStr + 1);
558 break;
559 }
560 }
561 rc = getNextToken(pParse, iCol, &z[iColLen], n-iColLen, ppExpr, pnConsumed);
562 *pnConsumed += iColLen;
563 return rc;
564 }
565
566 /*
567 ** The argument is an Fts3Expr structure for a binary operator (any type
568 ** except an FTSQUERY_PHRASE). Return an integer value representing the
569 ** precedence of the operator. Lower values have a higher precedence (i.e.
570 ** group more tightly). For example, in the C language, the == operator
571 ** groups more tightly than ||, and would therefore have a higher precedence.
572 **
573 ** When using the new fts3 query syntax (when SQLITE_ENABLE_FTS3_PARENTHESIS
574 ** is defined), the order of the operators in precedence from highest to
575 ** lowest is:
576 **
577 ** NEAR
578 ** NOT
579 ** AND (including implicit ANDs)
580 ** OR
581 **
582 ** Note that when using the old query syntax, the OR operator has a higher
583 ** precedence than the AND operator.
584 */
585 static int opPrecedence(Fts3Expr *p){
586 assert( p->eType!=FTSQUERY_PHRASE );
587 if( sqlite3_fts3_enable_parentheses ){
588 return p->eType;
589 }else if( p->eType==FTSQUERY_NEAR ){
590 return 1;
591 }else if( p->eType==FTSQUERY_OR ){
592 return 2;
593 }
594 assert( p->eType==FTSQUERY_AND );
595 return 3;
596 }
597
598 /*
599 ** Argument ppHead contains a pointer to the current head of a query
600 ** expression tree being parsed. pPrev is the expression node most recently
601 ** inserted into the tree. This function adds pNew, which is always a binary
602 ** operator node, into the expression tree based on the relative precedence
603 ** of pNew and the existing nodes of the tree. This may result in the head
604 ** of the tree changing, in which case *ppHead is set to the new root node.
605 */
606 static void insertBinaryOperator(
607 Fts3Expr **ppHead, /* Pointer to the root node of a tree */
608 Fts3Expr *pPrev, /* Node most recently inserted into the tree */
609 Fts3Expr *pNew /* New binary node to insert into expression tree */
610 ){
611 Fts3Expr *pSplit = pPrev;
612 while( pSplit->pParent && opPrecedence(pSplit->pParent)<=opPrecedence(pNew) ){
613 pSplit = pSplit->pParent;
614 }
615
616 if( pSplit->pParent ){
617 assert( pSplit->pParent->pRight==pSplit );
618 pSplit->pParent->pRight = pNew;
619 pNew->pParent = pSplit->pParent;
620 }else{
621 *ppHead = pNew;
622 }
623 pNew->pLeft = pSplit;
624 pSplit->pParent = pNew;
625 }
626
627 /*
628 ** Parse the fts3 query expression found in buffer z, length n. This function
629 ** returns either when the end of the buffer is reached or an unmatched
630 ** closing bracket - ')' - is encountered.
631 **
632 ** If successful, SQLITE_OK is returned, *ppExpr is set to point to the
633 ** parsed form of the expression and *pnConsumed is set to the number of
634 ** bytes read from buffer z. Otherwise, *ppExpr is set to 0 and SQLITE_NOMEM
635 ** (out of memory error) or SQLITE_ERROR (parse error) is returned.
636 */
637 static int fts3ExprParse(
638 ParseContext *pParse, /* fts3 query parse context */
639 const char *z, int n, /* Text of MATCH query */
640 Fts3Expr **ppExpr, /* OUT: Parsed query structure */
641 int *pnConsumed /* OUT: Number of bytes consumed */
642 ){
643 Fts3Expr *pRet = 0;
644 Fts3Expr *pPrev = 0;
645 Fts3Expr *pNotBranch = 0; /* Only used in legacy parse mode */
646 int nIn = n;
647 const char *zIn = z;
648 int rc = SQLITE_OK;
649 int isRequirePhrase = 1;
650
651 while( rc==SQLITE_OK ){
652 Fts3Expr *p = 0;
653 int nByte = 0;
654
655 rc = getNextNode(pParse, zIn, nIn, &p, &nByte);
656 assert( nByte>0 || (rc!=SQLITE_OK && p==0) );
657 if( rc==SQLITE_OK ){
658 if( p ){
659 int isPhrase;
660
661 if( !sqlite3_fts3_enable_parentheses
662 && p->eType==FTSQUERY_PHRASE && pParse->isNot
663 ){
664 /* Create an implicit NOT operator. */
665 Fts3Expr *pNot = sqlite3Fts3MallocZero(sizeof(Fts3Expr));
666 if( !pNot ){
667 sqlite3Fts3ExprFree(p);
668 rc = SQLITE_NOMEM;
669 goto exprparse_out;
670 }
671 pNot->eType = FTSQUERY_NOT;
672 pNot->pRight = p;
673 p->pParent = pNot;
674 if( pNotBranch ){
675 pNot->pLeft = pNotBranch;
676 pNotBranch->pParent = pNot;
677 }
678 pNotBranch = pNot;
679 p = pPrev;
680 }else{
681 int eType = p->eType;
682 isPhrase = (eType==FTSQUERY_PHRASE || p->pLeft);
683
684 /* The isRequirePhrase variable is set to true if a phrase or
685 ** an expression contained in parenthesis is required. If a
686 ** binary operator (AND, OR, NOT or NEAR) is encountered when
687 ** isRequirePhrase is set, this is a syntax error.
688 */
689 if( !isPhrase && isRequirePhrase ){
690 sqlite3Fts3ExprFree(p);
691 rc = SQLITE_ERROR;
692 goto exprparse_out;
693 }
694
695 if( isPhrase && !isRequirePhrase ){
696 /* Insert an implicit AND operator. */
697 Fts3Expr *pAnd;
698 assert( pRet && pPrev );
699 pAnd = sqlite3Fts3MallocZero(sizeof(Fts3Expr));
700 if( !pAnd ){
701 sqlite3Fts3ExprFree(p);
702 rc = SQLITE_NOMEM;
703 goto exprparse_out;
704 }
705 pAnd->eType = FTSQUERY_AND;
706 insertBinaryOperator(&pRet, pPrev, pAnd);
707 pPrev = pAnd;
708 }
709
710 /* This test catches attempts to make either operand of a NEAR
711 ** operator something other than a phrase. For example, either of
712 ** the following:
713 **
714 ** (bracketed expression) NEAR phrase
715 ** phrase NEAR (bracketed expression)
716 **
717 ** Return an error in either case.
718 */
719 if( pPrev && (
720 (eType==FTSQUERY_NEAR && !isPhrase && pPrev->eType!=FTSQUERY_PHRASE)
721 || (eType!=FTSQUERY_PHRASE && isPhrase && pPrev->eType==FTSQUERY_NEAR)
722 )){
723 sqlite3Fts3ExprFree(p);
724 rc = SQLITE_ERROR;
725 goto exprparse_out;
726 }
727
728 if( isPhrase ){
729 if( pRet ){
730 assert( pPrev && pPrev->pLeft && pPrev->pRight==0 );
731 pPrev->pRight = p;
732 p->pParent = pPrev;
733 }else{
734 pRet = p;
735 }
736 }else{
737 insertBinaryOperator(&pRet, pPrev, p);
738 }
739 isRequirePhrase = !isPhrase;
740 }
741 pPrev = p;
742 }
743 assert( nByte>0 );
744 }
745 assert( rc!=SQLITE_OK || (nByte>0 && nByte<=nIn) );
746 nIn -= nByte;
747 zIn += nByte;
748 }
749
750 if( rc==SQLITE_DONE && pRet && isRequirePhrase ){
751 rc = SQLITE_ERROR;
752 }
753
754 if( rc==SQLITE_DONE ){
755 rc = SQLITE_OK;
756 if( !sqlite3_fts3_enable_parentheses && pNotBranch ){
757 if( !pRet ){
758 rc = SQLITE_ERROR;
759 }else{
760 Fts3Expr *pIter = pNotBranch;
761 while( pIter->pLeft ){
762 pIter = pIter->pLeft;
763 }
764 pIter->pLeft = pRet;
765 pRet->pParent = pIter;
766 pRet = pNotBranch;
767 }
768 }
769 }
770 *pnConsumed = n - nIn;
771
772 exprparse_out:
773 if( rc!=SQLITE_OK ){
774 sqlite3Fts3ExprFree(pRet);
775 sqlite3Fts3ExprFree(pNotBranch);
776 pRet = 0;
777 }
778 *ppExpr = pRet;
779 return rc;
780 }
781
782 /*
783 ** Return SQLITE_ERROR if the maximum depth of the expression tree passed
784 ** as the only argument is more than nMaxDepth.
785 */
786 static int fts3ExprCheckDepth(Fts3Expr *p, int nMaxDepth){
787 int rc = SQLITE_OK;
788 if( p ){
789 if( nMaxDepth<0 ){
790 rc = SQLITE_TOOBIG;
791 }else{
792 rc = fts3ExprCheckDepth(p->pLeft, nMaxDepth-1);
793 if( rc==SQLITE_OK ){
794 rc = fts3ExprCheckDepth(p->pRight, nMaxDepth-1);
795 }
796 }
797 }
798 return rc;
799 }
800
801 /*
802 ** This function attempts to transform the expression tree at (*pp) to
803 ** an equivalent but more balanced form. The tree is modified in place.
804 ** If successful, SQLITE_OK is returned and (*pp) set to point to the
805 ** new root expression node.
806 **
807 ** nMaxDepth is the maximum allowable depth of the balanced sub-tree.
808 **
809 ** Otherwise, if an error occurs, an SQLite error code is returned and
810 ** expression (*pp) freed.
811 */
812 static int fts3ExprBalance(Fts3Expr **pp, int nMaxDepth){
813 int rc = SQLITE_OK; /* Return code */
814 Fts3Expr *pRoot = *pp; /* Initial root node */
815 Fts3Expr *pFree = 0; /* List of free nodes. Linked by pParent. */
816 int eType = pRoot->eType; /* Type of node in this tree */
817
818 if( nMaxDepth==0 ){
819 rc = SQLITE_ERROR;
820 }
821
822 if( rc==SQLITE_OK ){
823 if( (eType==FTSQUERY_AND || eType==FTSQUERY_OR) ){
824 Fts3Expr **apLeaf;
825 apLeaf = (Fts3Expr **)sqlite3_malloc64(sizeof(Fts3Expr *) * nMaxDepth);
826 if( 0==apLeaf ){
827 rc = SQLITE_NOMEM;
828 }else{
829 memset(apLeaf, 0, sizeof(Fts3Expr *) * nMaxDepth);
830 }
831
832 if( rc==SQLITE_OK ){
833 int i;
834 Fts3Expr *p;
835
836 /* Set $p to point to the left-most leaf in the tree of eType nodes. */
837 for(p=pRoot; p->eType==eType; p=p->pLeft){
838 assert( p->pParent==0 || p->pParent->pLeft==p );
839 assert( p->pLeft && p->pRight );
840 }
841
842 /* This loop runs once for each leaf in the tree of eType nodes. */
843 while( 1 ){
844 int iLvl;
845 Fts3Expr *pParent = p->pParent; /* Current parent of p */
846
847 assert( pParent==0 || pParent->pLeft==p );
848 p->pParent = 0;
849 if( pParent ){
850 pParent->pLeft = 0;
851 }else{
852 pRoot = 0;
853 }
854 rc = fts3ExprBalance(&p, nMaxDepth-1);
855 if( rc!=SQLITE_OK ) break;
856
857 for(iLvl=0; p && iLvl<nMaxDepth; iLvl++){
858 if( apLeaf[iLvl]==0 ){
859 apLeaf[iLvl] = p;
860 p = 0;
861 }else{
862 assert( pFree );
863 pFree->pLeft = apLeaf[iLvl];
864 pFree->pRight = p;
865 pFree->pLeft->pParent = pFree;
866 pFree->pRight->pParent = pFree;
867
868 p = pFree;
869 pFree = pFree->pParent;
870 p->pParent = 0;
871 apLeaf[iLvl] = 0;
872 }
873 }
874 if( p ){
875 sqlite3Fts3ExprFree(p);
876 rc = SQLITE_TOOBIG;
877 break;
878 }
879
880 /* If that was the last leaf node, break out of the loop */
881 if( pParent==0 ) break;
882
883 /* Set $p to point to the next leaf in the tree of eType nodes */
884 for(p=pParent->pRight; p->eType==eType; p=p->pLeft);
885
886 /* Remove pParent from the original tree. */
887 assert( pParent->pParent==0 || pParent->pParent->pLeft==pParent );
888 pParent->pRight->pParent = pParent->pParent;
889 if( pParent->pParent ){
890 pParent->pParent->pLeft = pParent->pRight;
891 }else{
892 assert( pParent==pRoot );
893 pRoot = pParent->pRight;
894 }
895
896 /* Link pParent into the free node list. It will be used as an
897 ** internal node of the new tree. */
898 pParent->pParent = pFree;
899 pFree = pParent;
900 }
901
902 if( rc==SQLITE_OK ){
903 p = 0;
904 for(i=0; i<nMaxDepth; i++){
905 if( apLeaf[i] ){
906 if( p==0 ){
907 p = apLeaf[i];
908 p->pParent = 0;
909 }else{
910 assert( pFree!=0 );
911 pFree->pRight = p;
912 pFree->pLeft = apLeaf[i];
913 pFree->pLeft->pParent = pFree;
914 pFree->pRight->pParent = pFree;
915
916 p = pFree;
917 pFree = pFree->pParent;
918 p->pParent = 0;
919 }
920 }
921 }
922 pRoot = p;
923 }else{
924 /* An error occurred. Delete the contents of the apLeaf[] array
925 ** and pFree list. Everything else is cleaned up by the call to
926 ** sqlite3Fts3ExprFree(pRoot) below. */
927 Fts3Expr *pDel;
928 for(i=0; i<nMaxDepth; i++){
929 sqlite3Fts3ExprFree(apLeaf[i]);
930 }
931 while( (pDel=pFree)!=0 ){
932 pFree = pDel->pParent;
933 sqlite3_free(pDel);
934 }
935 }
936
937 assert( pFree==0 );
938 sqlite3_free( apLeaf );
939 }
940 }else if( eType==FTSQUERY_NOT ){
941 Fts3Expr *pLeft = pRoot->pLeft;
942 Fts3Expr *pRight = pRoot->pRight;
943
944 pRoot->pLeft = 0;
945 pRoot->pRight = 0;
946 pLeft->pParent = 0;
947 pRight->pParent = 0;
948
949 rc = fts3ExprBalance(&pLeft, nMaxDepth-1);
950 if( rc==SQLITE_OK ){
951 rc = fts3ExprBalance(&pRight, nMaxDepth-1);
952 }
953
954 if( rc!=SQLITE_OK ){
955 sqlite3Fts3ExprFree(pRight);
956 sqlite3Fts3ExprFree(pLeft);
957 }else{
958 assert( pLeft && pRight );
959 pRoot->pLeft = pLeft;
960 pLeft->pParent = pRoot;
961 pRoot->pRight = pRight;
962 pRight->pParent = pRoot;
963 }
964 }
965 }
966
967 if( rc!=SQLITE_OK ){
968 sqlite3Fts3ExprFree(pRoot);
969 pRoot = 0;
970 }
971 *pp = pRoot;
972 return rc;
973 }
974
975 /*
976 ** This function is similar to sqlite3Fts3ExprParse(), with the following
977 ** differences:
978 **
979 ** 1. It does not do expression rebalancing.
980 ** 2. It does not check that the expression does not exceed the
981 ** maximum allowable depth.
982 ** 3. Even if it fails, *ppExpr may still be set to point to an
983 ** expression tree. It should be deleted using sqlite3Fts3ExprFree()
984 ** in this case.
985 */
986 static int fts3ExprParseUnbalanced(
987 sqlite3_tokenizer *pTokenizer, /* Tokenizer module */
988 int iLangid, /* Language id for tokenizer */
989 char **azCol, /* Array of column names for fts3 table */
990 int bFts4, /* True to allow FTS4-only syntax */
991 int nCol, /* Number of entries in azCol[] */
992 int iDefaultCol, /* Default column to query */
993 const char *z, int n, /* Text of MATCH query */
994 Fts3Expr **ppExpr /* OUT: Parsed query structure */
995 ){
996 int nParsed;
997 int rc;
998 ParseContext sParse;
999
1000 memset(&sParse, 0, sizeof(ParseContext));
1001 sParse.pTokenizer = pTokenizer;
1002 sParse.iLangid = iLangid;
1003 sParse.azCol = (const char **)azCol;
1004 sParse.nCol = nCol;
1005 sParse.iDefaultCol = iDefaultCol;
1006 sParse.bFts4 = bFts4;
1007 if( z==0 ){
1008 *ppExpr = 0;
1009 return SQLITE_OK;
1010 }
1011 if( n<0 ){
1012 n = (int)strlen(z);
1013 }
1014 rc = fts3ExprParse(&sParse, z, n, ppExpr, &nParsed);
1015 assert( rc==SQLITE_OK || *ppExpr==0 );
1016
1017 /* Check for mismatched parenthesis */
1018 if( rc==SQLITE_OK && sParse.nNest ){
1019 rc = SQLITE_ERROR;
1020 }
1021
1022 return rc;
1023 }
1024
1025 /*
1026 ** Parameters z and n contain a pointer to and length of a buffer containing
1027 ** an fts3 query expression, respectively. This function attempts to parse the
1028 ** query expression and create a tree of Fts3Expr structures representing the
1029 ** parsed expression. If successful, *ppExpr is set to point to the head
1030 ** of the parsed expression tree and SQLITE_OK is returned. If an error
1031 ** occurs, either SQLITE_NOMEM (out-of-memory error) or SQLITE_ERROR (parse
1032 ** error) is returned and *ppExpr is set to 0.
1033 **
1034 ** If parameter n is a negative number, then z is assumed to point to a
1035 ** nul-terminated string and the length is determined using strlen().
1036 **
1037 ** The first parameter, pTokenizer, is passed the fts3 tokenizer module to
1038 ** use to normalize query tokens while parsing the expression. The azCol[]
1039 ** array, which is assumed to contain nCol entries, should contain the names
1040 ** of each column in the target fts3 table, in order from left to right.
1041 ** Column names must be nul-terminated strings.
1042 **
1043 ** The iDefaultCol parameter should be passed the index of the table column
1044 ** that appears on the left-hand-side of the MATCH operator (the default
1045 ** column to match against for tokens for which a column name is not explicitly
1046 ** specified as part of the query string), or -1 if tokens may by default
1047 ** match any table column.
1048 */
1049 int sqlite3Fts3ExprParse(
1050 sqlite3_tokenizer *pTokenizer, /* Tokenizer module */
1051 int iLangid, /* Language id for tokenizer */
1052 char **azCol, /* Array of column names for fts3 table */
1053 int bFts4, /* True to allow FTS4-only syntax */
1054 int nCol, /* Number of entries in azCol[] */
1055 int iDefaultCol, /* Default column to query */
1056 const char *z, int n, /* Text of MATCH query */
1057 Fts3Expr **ppExpr, /* OUT: Parsed query structure */
1058 char **pzErr /* OUT: Error message (sqlite3_malloc) */
1059 ){
1060 int rc = fts3ExprParseUnbalanced(
1061 pTokenizer, iLangid, azCol, bFts4, nCol, iDefaultCol, z, n, ppExpr
1062 );
1063
1064 /* Rebalance the expression. And check that its depth does not exceed
1065 ** SQLITE_FTS3_MAX_EXPR_DEPTH. */
1066 if( rc==SQLITE_OK && *ppExpr ){
1067 rc = fts3ExprBalance(ppExpr, SQLITE_FTS3_MAX_EXPR_DEPTH);
1068 if( rc==SQLITE_OK ){
1069 rc = fts3ExprCheckDepth(*ppExpr, SQLITE_FTS3_MAX_EXPR_DEPTH);
1070 }
1071 }
1072
1073 if( rc!=SQLITE_OK ){
1074 sqlite3Fts3ExprFree(*ppExpr);
1075 *ppExpr = 0;
1076 if( rc==SQLITE_TOOBIG ){
1077 sqlite3Fts3ErrMsg(pzErr,
1078 "FTS expression tree is too large (maximum depth %d)",
1079 SQLITE_FTS3_MAX_EXPR_DEPTH
1080 );
1081 rc = SQLITE_ERROR;
1082 }else if( rc==SQLITE_ERROR ){
1083 sqlite3Fts3ErrMsg(pzErr, "malformed MATCH expression: [%s]", z);
1084 }
1085 }
1086
1087 return rc;
1088 }
1089
1090 /*
1091 ** Free a single node of an expression tree.
1092 */
1093 static void fts3FreeExprNode(Fts3Expr *p){
1094 assert( p->eType==FTSQUERY_PHRASE || p->pPhrase==0 );
1095 sqlite3Fts3EvalPhraseCleanup(p->pPhrase);
1096 sqlite3_free(p->aMI);
1097 sqlite3_free(p);
1098 }
1099
1100 /*
1101 ** Free a parsed fts3 query expression allocated by sqlite3Fts3ExprParse().
1102 **
1103 ** This function would be simpler if it recursively called itself. But
1104 ** that would mean passing a sufficiently large expression to ExprParse()
1105 ** could cause a stack overflow.
1106 */
1107 void sqlite3Fts3ExprFree(Fts3Expr *pDel){
1108 Fts3Expr *p;
1109 assert( pDel==0 || pDel->pParent==0 );
1110 for(p=pDel; p && (p->pLeft||p->pRight); p=(p->pLeft ? p->pLeft : p->pRight)){
1111 assert( p->pParent==0 || p==p->pParent->pRight || p==p->pParent->pLeft );
1112 }
1113 while( p ){
1114 Fts3Expr *pParent = p->pParent;
1115 fts3FreeExprNode(p);
1116 if( pParent && p==pParent->pLeft && pParent->pRight ){
1117 p = pParent->pRight;
1118 while( p && (p->pLeft || p->pRight) ){
1119 assert( p==p->pParent->pRight || p==p->pParent->pLeft );
1120 p = (p->pLeft ? p->pLeft : p->pRight);
1121 }
1122 }else{
1123 p = pParent;
1124 }
1125 }
1126 }
1127
1128 /****************************************************************************
1129 *****************************************************************************
1130 ** Everything after this point is just test code.
1131 */
1132
1133 #ifdef SQLITE_TEST
1134
1135 #include <stdio.h>
1136
1137 /*
1138 ** Return a pointer to a buffer containing a text representation of the
1139 ** expression passed as the first argument. The buffer is obtained from
1140 ** sqlite3_malloc(). It is the responsibility of the caller to use
1141 ** sqlite3_free() to release the memory. If an OOM condition is encountered,
1142 ** NULL is returned.
1143 **
1144 ** If the second argument is not NULL, then its contents are prepended to
1145 ** the returned expression text and then freed using sqlite3_free().
1146 */
1147 static char *exprToString(Fts3Expr *pExpr, char *zBuf){
1148 if( pExpr==0 ){
1149 return sqlite3_mprintf("");
1150 }
1151 switch( pExpr->eType ){
1152 case FTSQUERY_PHRASE: {
1153 Fts3Phrase *pPhrase = pExpr->pPhrase;
1154 int i;
1155 zBuf = sqlite3_mprintf(
1156 "%zPHRASE %d 0", zBuf, pPhrase->iColumn);
1157 for(i=0; zBuf && i<pPhrase->nToken; i++){
1158 zBuf = sqlite3_mprintf("%z %.*s%s", zBuf,
1159 pPhrase->aToken[i].n, pPhrase->aToken[i].z,
1160 (pPhrase->aToken[i].isPrefix?"+":"")
1161 );
1162 }
1163 return zBuf;
1164 }
1165
1166 case FTSQUERY_NEAR:
1167 zBuf = sqlite3_mprintf("%zNEAR/%d ", zBuf, pExpr->nNear);
1168 break;
1169 case FTSQUERY_NOT:
1170 zBuf = sqlite3_mprintf("%zNOT ", zBuf);
1171 break;
1172 case FTSQUERY_AND:
1173 zBuf = sqlite3_mprintf("%zAND ", zBuf);
1174 break;
1175 case FTSQUERY_OR:
1176 zBuf = sqlite3_mprintf("%zOR ", zBuf);
1177 break;
1178 }
1179
1180 if( zBuf ) zBuf = sqlite3_mprintf("%z{", zBuf);
1181 if( zBuf ) zBuf = exprToString(pExpr->pLeft, zBuf);
1182 if( zBuf ) zBuf = sqlite3_mprintf("%z} {", zBuf);
1183
1184 if( zBuf ) zBuf = exprToString(pExpr->pRight, zBuf);
1185 if( zBuf ) zBuf = sqlite3_mprintf("%z}", zBuf);
1186
1187 return zBuf;
1188 }
1189
1190 /*
1191 ** This is the implementation of a scalar SQL function used to test the
1192 ** expression parser. It should be called as follows:
1193 **
1194 ** fts3_exprtest(<tokenizer>, <expr>, <column 1>, ...);
1195 **
1196 ** The first argument, <tokenizer>, is the name of the fts3 tokenizer used
1197 ** to parse the query expression (see README.tokenizers). The second argument
1198 ** is the query expression to parse. Each subsequent argument is the name
1199 ** of a column of the fts3 table that the query expression may refer to.
1200 ** For example:
1201 **
1202 ** SELECT fts3_exprtest('simple', 'Bill col2:Bloggs', 'col1', 'col2');
1203 */
1204 static void fts3ExprTestCommon(
1205 int bRebalance,
1206 sqlite3_context *context,
1207 int argc,
1208 sqlite3_value **argv
1209 ){
1210 sqlite3_tokenizer *pTokenizer = 0;
1211 int rc;
1212 char **azCol = 0;
1213 const char *zExpr;
1214 int nExpr;
1215 int nCol;
1216 int ii;
1217 Fts3Expr *pExpr;
1218 char *zBuf = 0;
1219 Fts3Hash *pHash = (Fts3Hash*)sqlite3_user_data(context);
1220 const char *zTokenizer = 0;
1221 char *zErr = 0;
1222
1223 if( argc<3 ){
1224 sqlite3_result_error(context,
1225 "Usage: fts3_exprtest(tokenizer, expr, col1, ...", -1
1226 );
1227 return;
1228 }
1229
1230 zTokenizer = (const char*)sqlite3_value_text(argv[0]);
1231 rc = sqlite3Fts3InitTokenizer(pHash, zTokenizer, &pTokenizer, &zErr);
1232 if( rc!=SQLITE_OK ){
1233 if( rc==SQLITE_NOMEM ){
1234 sqlite3_result_error_nomem(context);
1235 }else{
1236 sqlite3_result_error(context, zErr, -1);
1237 }
1238 sqlite3_free(zErr);
1239 return;
1240 }
1241
1242 zExpr = (const char *)sqlite3_value_text(argv[1]);
1243 nExpr = sqlite3_value_bytes(argv[1]);
1244 nCol = argc-2;
1245 azCol = (char **)sqlite3_malloc64(nCol*sizeof(char *));
1246 if( !azCol ){
1247 sqlite3_result_error_nomem(context);
1248 goto exprtest_out;
1249 }
1250 for(ii=0; ii<nCol; ii++){
1251 azCol[ii] = (char *)sqlite3_value_text(argv[ii+2]);
1252 }
1253
1254 if( bRebalance ){
1255 char *zDummy = 0;
1256 rc = sqlite3Fts3ExprParse(
1257 pTokenizer, 0, azCol, 0, nCol, nCol, zExpr, nExpr, &pExpr, &zDummy
1258 );
1259 assert( rc==SQLITE_OK || pExpr==0 );
1260 sqlite3_free(zDummy);
1261 }else{
1262 rc = fts3ExprParseUnbalanced(
1263 pTokenizer, 0, azCol, 0, nCol, nCol, zExpr, nExpr, &pExpr
1264 );
1265 }
1266
1267 if( rc!=SQLITE_OK && rc!=SQLITE_NOMEM ){
1268 sqlite3_result_error(context, "Error parsing expression", -1);
1269 }else if( rc==SQLITE_NOMEM || !(zBuf = exprToString(pExpr, 0)) ){
1270 sqlite3_result_error_nomem(context);
1271 }else{
1272 sqlite3_result_text(context, zBuf, -1, SQLITE_TRANSIENT);
1273 sqlite3_free(zBuf);
1274 }
1275
1276 sqlite3Fts3ExprFree(pExpr);
1277
1278 exprtest_out:
1279 if( pTokenizer ){
1280 rc = pTokenizer->pModule->xDestroy(pTokenizer);
1281 }
1282 sqlite3_free(azCol);
1283 }
1284
1285 static void fts3ExprTest(
1286 sqlite3_context *context,
1287 int argc,
1288 sqlite3_value **argv
1289 ){
1290 fts3ExprTestCommon(0, context, argc, argv);
1291 }
1292 static void fts3ExprTestRebalance(
1293 sqlite3_context *context,
1294 int argc,
1295 sqlite3_value **argv
1296 ){
1297 fts3ExprTestCommon(1, context, argc, argv);
1298 }
1299
1300 /*
1301 ** Register the query expression parser test function fts3_exprtest()
1302 ** with database connection db.
1303 */
1304 int sqlite3Fts3ExprInitTestInterface(sqlite3 *db, Fts3Hash *pHash){
1305 int rc = sqlite3_create_function(
1306 db, "fts3_exprtest", -1, SQLITE_UTF8, (void*)pHash, fts3ExprTest, 0, 0
1307 );
1308 if( rc==SQLITE_OK ){
1309 rc = sqlite3_create_function(db, "fts3_exprtest_rebalance",
1310 -1, SQLITE_UTF8, (void*)pHash, fts3ExprTestRebalance, 0, 0
1311 );
1312 }
1313 return rc;
1314 }
1315
1316 #endif
1317 #endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3) */