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: const char **azCol; /* Array of column names for fts3 table */
96: int bFts4; /* True to allow FTS4-only syntax */
97: int nCol; /* Number of entries in azCol[] */
98: int iDefaultCol; /* Default column to query */
99: int isNot; /* True if getNextNode() sees a unary - */
100: sqlite3_context *pCtx; /* Write error message here */
101: int nNest; /* Number of nested brackets */
102: };
103:
104: /*
105: ** This function is equivalent to the standard isspace() function.
106: **
107: ** The standard isspace() can be awkward to use safely, because although it
108: ** is defined to accept an argument of type int, its behaviour when passed
109: ** an integer that falls outside of the range of the unsigned char type
110: ** is undefined (and sometimes, "undefined" means segfault). This wrapper
111: ** is defined to accept an argument of type char, and always returns 0 for
112: ** any values that fall outside of the range of the unsigned char type (i.e.
113: ** negative values).
114: */
115: static int fts3isspace(char c){
116: return c==' ' || c=='\t' || c=='\n' || c=='\r' || c=='\v' || c=='\f';
117: }
118:
119: /*
120: ** Allocate nByte bytes of memory using sqlite3_malloc(). If successful,
121: ** zero the memory before returning a pointer to it. If unsuccessful,
122: ** return NULL.
123: */
124: static void *fts3MallocZero(int nByte){
125: void *pRet = sqlite3_malloc(nByte);
126: if( pRet ) memset(pRet, 0, nByte);
127: return pRet;
128: }
129:
130:
131: /*
132: ** Extract the next token from buffer z (length n) using the tokenizer
133: ** and other information (column names etc.) in pParse. Create an Fts3Expr
134: ** structure of type FTSQUERY_PHRASE containing a phrase consisting of this
135: ** single token and set *ppExpr to point to it. If the end of the buffer is
136: ** reached before a token is found, set *ppExpr to zero. It is the
137: ** responsibility of the caller to eventually deallocate the allocated
138: ** Fts3Expr structure (if any) by passing it to sqlite3_free().
139: **
140: ** Return SQLITE_OK if successful, or SQLITE_NOMEM if a memory allocation
141: ** fails.
142: */
143: static int getNextToken(
144: ParseContext *pParse, /* fts3 query parse context */
145: int iCol, /* Value for Fts3Phrase.iColumn */
146: const char *z, int n, /* Input string */
147: Fts3Expr **ppExpr, /* OUT: expression */
148: int *pnConsumed /* OUT: Number of bytes consumed */
149: ){
150: sqlite3_tokenizer *pTokenizer = pParse->pTokenizer;
151: sqlite3_tokenizer_module const *pModule = pTokenizer->pModule;
152: int rc;
153: sqlite3_tokenizer_cursor *pCursor;
154: Fts3Expr *pRet = 0;
155: int nConsumed = 0;
156:
157: rc = pModule->xOpen(pTokenizer, z, n, &pCursor);
158: if( rc==SQLITE_OK ){
159: const char *zToken;
160: int nToken, iStart, iEnd, iPosition;
161: int nByte; /* total space to allocate */
162:
163: pCursor->pTokenizer = pTokenizer;
164: rc = pModule->xNext(pCursor, &zToken, &nToken, &iStart, &iEnd, &iPosition);
165:
166: if( rc==SQLITE_OK ){
167: nByte = sizeof(Fts3Expr) + sizeof(Fts3Phrase) + nToken;
168: pRet = (Fts3Expr *)fts3MallocZero(nByte);
169: if( !pRet ){
170: rc = SQLITE_NOMEM;
171: }else{
172: pRet->eType = FTSQUERY_PHRASE;
173: pRet->pPhrase = (Fts3Phrase *)&pRet[1];
174: pRet->pPhrase->nToken = 1;
175: pRet->pPhrase->iColumn = iCol;
176: pRet->pPhrase->aToken[0].n = nToken;
177: pRet->pPhrase->aToken[0].z = (char *)&pRet->pPhrase[1];
178: memcpy(pRet->pPhrase->aToken[0].z, zToken, nToken);
179:
180: if( iEnd<n && z[iEnd]=='*' ){
181: pRet->pPhrase->aToken[0].isPrefix = 1;
182: iEnd++;
183: }
184:
185: while( 1 ){
186: if( !sqlite3_fts3_enable_parentheses
187: && iStart>0 && z[iStart-1]=='-'
188: ){
189: pParse->isNot = 1;
190: iStart--;
191: }else if( pParse->bFts4 && iStart>0 && z[iStart-1]=='^' ){
192: pRet->pPhrase->aToken[0].bFirst = 1;
193: iStart--;
194: }else{
195: break;
196: }
197: }
198:
199: }
200: nConsumed = iEnd;
201: }
202:
203: pModule->xClose(pCursor);
204: }
205:
206: *pnConsumed = nConsumed;
207: *ppExpr = pRet;
208: return rc;
209: }
210:
211:
212: /*
213: ** Enlarge a memory allocation. If an out-of-memory allocation occurs,
214: ** then free the old allocation.
215: */
216: static void *fts3ReallocOrFree(void *pOrig, int nNew){
217: void *pRet = sqlite3_realloc(pOrig, nNew);
218: if( !pRet ){
219: sqlite3_free(pOrig);
220: }
221: return pRet;
222: }
223:
224: /*
225: ** Buffer zInput, length nInput, contains the contents of a quoted string
226: ** that appeared as part of an fts3 query expression. Neither quote character
227: ** is included in the buffer. This function attempts to tokenize the entire
228: ** input buffer and create an Fts3Expr structure of type FTSQUERY_PHRASE
229: ** containing the results.
230: **
231: ** If successful, SQLITE_OK is returned and *ppExpr set to point at the
232: ** allocated Fts3Expr structure. Otherwise, either SQLITE_NOMEM (out of memory
233: ** error) or SQLITE_ERROR (tokenization error) is returned and *ppExpr set
234: ** to 0.
235: */
236: static int getNextString(
237: ParseContext *pParse, /* fts3 query parse context */
238: const char *zInput, int nInput, /* Input string */
239: Fts3Expr **ppExpr /* OUT: expression */
240: ){
241: sqlite3_tokenizer *pTokenizer = pParse->pTokenizer;
242: sqlite3_tokenizer_module const *pModule = pTokenizer->pModule;
243: int rc;
244: Fts3Expr *p = 0;
245: sqlite3_tokenizer_cursor *pCursor = 0;
246: char *zTemp = 0;
247: int nTemp = 0;
248:
249: const int nSpace = sizeof(Fts3Expr) + sizeof(Fts3Phrase);
250: int nToken = 0;
251:
252: /* The final Fts3Expr data structure, including the Fts3Phrase,
253: ** Fts3PhraseToken structures token buffers are all stored as a single
254: ** allocation so that the expression can be freed with a single call to
255: ** sqlite3_free(). Setting this up requires a two pass approach.
256: **
257: ** The first pass, in the block below, uses a tokenizer cursor to iterate
258: ** through the tokens in the expression. This pass uses fts3ReallocOrFree()
259: ** to assemble data in two dynamic buffers:
260: **
261: ** Buffer p: Points to the Fts3Expr structure, followed by the Fts3Phrase
262: ** structure, followed by the array of Fts3PhraseToken
263: ** structures. This pass only populates the Fts3PhraseToken array.
264: **
265: ** Buffer zTemp: Contains copies of all tokens.
266: **
267: ** The second pass, in the block that begins "if( rc==SQLITE_DONE )" below,
268: ** appends buffer zTemp to buffer p, and fills in the Fts3Expr and Fts3Phrase
269: ** structures.
270: */
271: rc = pModule->xOpen(pTokenizer, zInput, nInput, &pCursor);
272: if( rc==SQLITE_OK ){
273: int ii;
274: pCursor->pTokenizer = pTokenizer;
275: for(ii=0; rc==SQLITE_OK; ii++){
276: const char *zByte;
277: int nByte, iBegin, iEnd, iPos;
278: rc = pModule->xNext(pCursor, &zByte, &nByte, &iBegin, &iEnd, &iPos);
279: if( rc==SQLITE_OK ){
280: Fts3PhraseToken *pToken;
281:
282: p = fts3ReallocOrFree(p, nSpace + ii*sizeof(Fts3PhraseToken));
283: if( !p ) goto no_mem;
284:
285: zTemp = fts3ReallocOrFree(zTemp, nTemp + nByte);
286: if( !zTemp ) goto no_mem;
287:
288: assert( nToken==ii );
289: pToken = &((Fts3Phrase *)(&p[1]))->aToken[ii];
290: memset(pToken, 0, sizeof(Fts3PhraseToken));
291:
292: memcpy(&zTemp[nTemp], zByte, nByte);
293: nTemp += nByte;
294:
295: pToken->n = nByte;
296: pToken->isPrefix = (iEnd<nInput && zInput[iEnd]=='*');
297: pToken->bFirst = (iBegin>0 && zInput[iBegin-1]=='^');
298: nToken = ii+1;
299: }
300: }
301:
302: pModule->xClose(pCursor);
303: pCursor = 0;
304: }
305:
306: if( rc==SQLITE_DONE ){
307: int jj;
308: char *zBuf = 0;
309:
310: p = fts3ReallocOrFree(p, nSpace + nToken*sizeof(Fts3PhraseToken) + nTemp);
311: if( !p ) goto no_mem;
312: memset(p, 0, (char *)&(((Fts3Phrase *)&p[1])->aToken[0])-(char *)p);
313: p->eType = FTSQUERY_PHRASE;
314: p->pPhrase = (Fts3Phrase *)&p[1];
315: p->pPhrase->iColumn = pParse->iDefaultCol;
316: p->pPhrase->nToken = nToken;
317:
318: zBuf = (char *)&p->pPhrase->aToken[nToken];
319: if( zTemp ){
320: memcpy(zBuf, zTemp, nTemp);
321: sqlite3_free(zTemp);
322: }else{
323: assert( nTemp==0 );
324: }
325:
326: for(jj=0; jj<p->pPhrase->nToken; jj++){
327: p->pPhrase->aToken[jj].z = zBuf;
328: zBuf += p->pPhrase->aToken[jj].n;
329: }
330: rc = SQLITE_OK;
331: }
332:
333: *ppExpr = p;
334: return rc;
335: no_mem:
336:
337: if( pCursor ){
338: pModule->xClose(pCursor);
339: }
340: sqlite3_free(zTemp);
341: sqlite3_free(p);
342: *ppExpr = 0;
343: return SQLITE_NOMEM;
344: }
345:
346: /*
347: ** Function getNextNode(), which is called by fts3ExprParse(), may itself
348: ** call fts3ExprParse(). So this forward declaration is required.
349: */
350: static int fts3ExprParse(ParseContext *, const char *, int, Fts3Expr **, int *);
351:
352: /*
353: ** The output variable *ppExpr is populated with an allocated Fts3Expr
354: ** structure, or set to 0 if the end of the input buffer is reached.
355: **
356: ** Returns an SQLite error code. SQLITE_OK if everything works, SQLITE_NOMEM
357: ** if a malloc failure occurs, or SQLITE_ERROR if a parse error is encountered.
358: ** If SQLITE_ERROR is returned, pContext is populated with an error message.
359: */
360: static int getNextNode(
361: ParseContext *pParse, /* fts3 query parse context */
362: const char *z, int n, /* Input string */
363: Fts3Expr **ppExpr, /* OUT: expression */
364: int *pnConsumed /* OUT: Number of bytes consumed */
365: ){
366: static const struct Fts3Keyword {
367: char *z; /* Keyword text */
368: unsigned char n; /* Length of the keyword */
369: unsigned char parenOnly; /* Only valid in paren mode */
370: unsigned char eType; /* Keyword code */
371: } aKeyword[] = {
372: { "OR" , 2, 0, FTSQUERY_OR },
373: { "AND", 3, 1, FTSQUERY_AND },
374: { "NOT", 3, 1, FTSQUERY_NOT },
375: { "NEAR", 4, 0, FTSQUERY_NEAR }
376: };
377: int ii;
378: int iCol;
379: int iColLen;
380: int rc;
381: Fts3Expr *pRet = 0;
382:
383: const char *zInput = z;
384: int nInput = n;
385:
386: pParse->isNot = 0;
387:
388: /* Skip over any whitespace before checking for a keyword, an open or
389: ** close bracket, or a quoted string.
390: */
391: while( nInput>0 && fts3isspace(*zInput) ){
392: nInput--;
393: zInput++;
394: }
395: if( nInput==0 ){
396: return SQLITE_DONE;
397: }
398:
399: /* See if we are dealing with a keyword. */
400: for(ii=0; ii<(int)(sizeof(aKeyword)/sizeof(struct Fts3Keyword)); ii++){
401: const struct Fts3Keyword *pKey = &aKeyword[ii];
402:
403: if( (pKey->parenOnly & ~sqlite3_fts3_enable_parentheses)!=0 ){
404: continue;
405: }
406:
407: if( nInput>=pKey->n && 0==memcmp(zInput, pKey->z, pKey->n) ){
408: int nNear = SQLITE_FTS3_DEFAULT_NEAR_PARAM;
409: int nKey = pKey->n;
410: char cNext;
411:
412: /* If this is a "NEAR" keyword, check for an explicit nearness. */
413: if( pKey->eType==FTSQUERY_NEAR ){
414: assert( nKey==4 );
415: if( zInput[4]=='/' && zInput[5]>='0' && zInput[5]<='9' ){
416: nNear = 0;
417: for(nKey=5; zInput[nKey]>='0' && zInput[nKey]<='9'; nKey++){
418: nNear = nNear * 10 + (zInput[nKey] - '0');
419: }
420: }
421: }
422:
423: /* At this point this is probably a keyword. But for that to be true,
424: ** the next byte must contain either whitespace, an open or close
425: ** parenthesis, a quote character, or EOF.
426: */
427: cNext = zInput[nKey];
428: if( fts3isspace(cNext)
429: || cNext=='"' || cNext=='(' || cNext==')' || cNext==0
430: ){
431: pRet = (Fts3Expr *)fts3MallocZero(sizeof(Fts3Expr));
432: if( !pRet ){
433: return SQLITE_NOMEM;
434: }
435: pRet->eType = pKey->eType;
436: pRet->nNear = nNear;
437: *ppExpr = pRet;
438: *pnConsumed = (int)((zInput - z) + nKey);
439: return SQLITE_OK;
440: }
441:
442: /* Turns out that wasn't a keyword after all. This happens if the
443: ** user has supplied a token such as "ORacle". Continue.
444: */
445: }
446: }
447:
448: /* Check for an open bracket. */
449: if( sqlite3_fts3_enable_parentheses ){
450: if( *zInput=='(' ){
451: int nConsumed;
452: pParse->nNest++;
453: rc = fts3ExprParse(pParse, &zInput[1], nInput-1, ppExpr, &nConsumed);
454: if( rc==SQLITE_OK && !*ppExpr ){
455: rc = SQLITE_DONE;
456: }
457: *pnConsumed = (int)((zInput - z) + 1 + nConsumed);
458: return rc;
459: }
460:
461: /* Check for a close bracket. */
462: if( *zInput==')' ){
463: pParse->nNest--;
464: *pnConsumed = (int)((zInput - z) + 1);
465: return SQLITE_DONE;
466: }
467: }
468:
469: /* See if we are dealing with a quoted phrase. If this is the case, then
470: ** search for the closing quote and pass the whole string to getNextString()
471: ** for processing. This is easy to do, as fts3 has no syntax for escaping
472: ** a quote character embedded in a string.
473: */
474: if( *zInput=='"' ){
475: for(ii=1; ii<nInput && zInput[ii]!='"'; ii++);
476: *pnConsumed = (int)((zInput - z) + ii + 1);
477: if( ii==nInput ){
478: return SQLITE_ERROR;
479: }
480: return getNextString(pParse, &zInput[1], ii-1, ppExpr);
481: }
482:
483:
484: /* If control flows to this point, this must be a regular token, or
485: ** the end of the input. Read a regular token using the sqlite3_tokenizer
486: ** interface. Before doing so, figure out if there is an explicit
487: ** column specifier for the token.
488: **
489: ** TODO: Strangely, it is not possible to associate a column specifier
490: ** with a quoted phrase, only with a single token. Not sure if this was
491: ** an implementation artifact or an intentional decision when fts3 was
492: ** first implemented. Whichever it was, this module duplicates the
493: ** limitation.
494: */
495: iCol = pParse->iDefaultCol;
496: iColLen = 0;
497: for(ii=0; ii<pParse->nCol; ii++){
498: const char *zStr = pParse->azCol[ii];
499: int nStr = (int)strlen(zStr);
500: if( nInput>nStr && zInput[nStr]==':'
501: && sqlite3_strnicmp(zStr, zInput, nStr)==0
502: ){
503: iCol = ii;
504: iColLen = (int)((zInput - z) + nStr + 1);
505: break;
506: }
507: }
508: rc = getNextToken(pParse, iCol, &z[iColLen], n-iColLen, ppExpr, pnConsumed);
509: *pnConsumed += iColLen;
510: return rc;
511: }
512:
513: /*
514: ** The argument is an Fts3Expr structure for a binary operator (any type
515: ** except an FTSQUERY_PHRASE). Return an integer value representing the
516: ** precedence of the operator. Lower values have a higher precedence (i.e.
517: ** group more tightly). For example, in the C language, the == operator
518: ** groups more tightly than ||, and would therefore have a higher precedence.
519: **
520: ** When using the new fts3 query syntax (when SQLITE_ENABLE_FTS3_PARENTHESIS
521: ** is defined), the order of the operators in precedence from highest to
522: ** lowest is:
523: **
524: ** NEAR
525: ** NOT
526: ** AND (including implicit ANDs)
527: ** OR
528: **
529: ** Note that when using the old query syntax, the OR operator has a higher
530: ** precedence than the AND operator.
531: */
532: static int opPrecedence(Fts3Expr *p){
533: assert( p->eType!=FTSQUERY_PHRASE );
534: if( sqlite3_fts3_enable_parentheses ){
535: return p->eType;
536: }else if( p->eType==FTSQUERY_NEAR ){
537: return 1;
538: }else if( p->eType==FTSQUERY_OR ){
539: return 2;
540: }
541: assert( p->eType==FTSQUERY_AND );
542: return 3;
543: }
544:
545: /*
546: ** Argument ppHead contains a pointer to the current head of a query
547: ** expression tree being parsed. pPrev is the expression node most recently
548: ** inserted into the tree. This function adds pNew, which is always a binary
549: ** operator node, into the expression tree based on the relative precedence
550: ** of pNew and the existing nodes of the tree. This may result in the head
551: ** of the tree changing, in which case *ppHead is set to the new root node.
552: */
553: static void insertBinaryOperator(
554: Fts3Expr **ppHead, /* Pointer to the root node of a tree */
555: Fts3Expr *pPrev, /* Node most recently inserted into the tree */
556: Fts3Expr *pNew /* New binary node to insert into expression tree */
557: ){
558: Fts3Expr *pSplit = pPrev;
559: while( pSplit->pParent && opPrecedence(pSplit->pParent)<=opPrecedence(pNew) ){
560: pSplit = pSplit->pParent;
561: }
562:
563: if( pSplit->pParent ){
564: assert( pSplit->pParent->pRight==pSplit );
565: pSplit->pParent->pRight = pNew;
566: pNew->pParent = pSplit->pParent;
567: }else{
568: *ppHead = pNew;
569: }
570: pNew->pLeft = pSplit;
571: pSplit->pParent = pNew;
572: }
573:
574: /*
575: ** Parse the fts3 query expression found in buffer z, length n. This function
576: ** returns either when the end of the buffer is reached or an unmatched
577: ** closing bracket - ')' - is encountered.
578: **
579: ** If successful, SQLITE_OK is returned, *ppExpr is set to point to the
580: ** parsed form of the expression and *pnConsumed is set to the number of
581: ** bytes read from buffer z. Otherwise, *ppExpr is set to 0 and SQLITE_NOMEM
582: ** (out of memory error) or SQLITE_ERROR (parse error) is returned.
583: */
584: static int fts3ExprParse(
585: ParseContext *pParse, /* fts3 query parse context */
586: const char *z, int n, /* Text of MATCH query */
587: Fts3Expr **ppExpr, /* OUT: Parsed query structure */
588: int *pnConsumed /* OUT: Number of bytes consumed */
589: ){
590: Fts3Expr *pRet = 0;
591: Fts3Expr *pPrev = 0;
592: Fts3Expr *pNotBranch = 0; /* Only used in legacy parse mode */
593: int nIn = n;
594: const char *zIn = z;
595: int rc = SQLITE_OK;
596: int isRequirePhrase = 1;
597:
598: while( rc==SQLITE_OK ){
599: Fts3Expr *p = 0;
600: int nByte = 0;
601: rc = getNextNode(pParse, zIn, nIn, &p, &nByte);
602: if( rc==SQLITE_OK ){
603: int isPhrase;
604:
605: if( !sqlite3_fts3_enable_parentheses
606: && p->eType==FTSQUERY_PHRASE && pParse->isNot
607: ){
608: /* Create an implicit NOT operator. */
609: Fts3Expr *pNot = fts3MallocZero(sizeof(Fts3Expr));
610: if( !pNot ){
611: sqlite3Fts3ExprFree(p);
612: rc = SQLITE_NOMEM;
613: goto exprparse_out;
614: }
615: pNot->eType = FTSQUERY_NOT;
616: pNot->pRight = p;
617: if( pNotBranch ){
618: pNot->pLeft = pNotBranch;
619: }
620: pNotBranch = pNot;
621: p = pPrev;
622: }else{
623: int eType = p->eType;
624: isPhrase = (eType==FTSQUERY_PHRASE || p->pLeft);
625:
626: /* The isRequirePhrase variable is set to true if a phrase or
627: ** an expression contained in parenthesis is required. If a
628: ** binary operator (AND, OR, NOT or NEAR) is encounted when
629: ** isRequirePhrase is set, this is a syntax error.
630: */
631: if( !isPhrase && isRequirePhrase ){
632: sqlite3Fts3ExprFree(p);
633: rc = SQLITE_ERROR;
634: goto exprparse_out;
635: }
636:
637: if( isPhrase && !isRequirePhrase ){
638: /* Insert an implicit AND operator. */
639: Fts3Expr *pAnd;
640: assert( pRet && pPrev );
641: pAnd = fts3MallocZero(sizeof(Fts3Expr));
642: if( !pAnd ){
643: sqlite3Fts3ExprFree(p);
644: rc = SQLITE_NOMEM;
645: goto exprparse_out;
646: }
647: pAnd->eType = FTSQUERY_AND;
648: insertBinaryOperator(&pRet, pPrev, pAnd);
649: pPrev = pAnd;
650: }
651:
652: /* This test catches attempts to make either operand of a NEAR
653: ** operator something other than a phrase. For example, either of
654: ** the following:
655: **
656: ** (bracketed expression) NEAR phrase
657: ** phrase NEAR (bracketed expression)
658: **
659: ** Return an error in either case.
660: */
661: if( pPrev && (
662: (eType==FTSQUERY_NEAR && !isPhrase && pPrev->eType!=FTSQUERY_PHRASE)
663: || (eType!=FTSQUERY_PHRASE && isPhrase && pPrev->eType==FTSQUERY_NEAR)
664: )){
665: sqlite3Fts3ExprFree(p);
666: rc = SQLITE_ERROR;
667: goto exprparse_out;
668: }
669:
670: if( isPhrase ){
671: if( pRet ){
672: assert( pPrev && pPrev->pLeft && pPrev->pRight==0 );
673: pPrev->pRight = p;
674: p->pParent = pPrev;
675: }else{
676: pRet = p;
677: }
678: }else{
679: insertBinaryOperator(&pRet, pPrev, p);
680: }
681: isRequirePhrase = !isPhrase;
682: }
683: assert( nByte>0 );
684: }
685: assert( rc!=SQLITE_OK || (nByte>0 && nByte<=nIn) );
686: nIn -= nByte;
687: zIn += nByte;
688: pPrev = p;
689: }
690:
691: if( rc==SQLITE_DONE && pRet && isRequirePhrase ){
692: rc = SQLITE_ERROR;
693: }
694:
695: if( rc==SQLITE_DONE ){
696: rc = SQLITE_OK;
697: if( !sqlite3_fts3_enable_parentheses && pNotBranch ){
698: if( !pRet ){
699: rc = SQLITE_ERROR;
700: }else{
701: Fts3Expr *pIter = pNotBranch;
702: while( pIter->pLeft ){
703: pIter = pIter->pLeft;
704: }
705: pIter->pLeft = pRet;
706: pRet = pNotBranch;
707: }
708: }
709: }
710: *pnConsumed = n - nIn;
711:
712: exprparse_out:
713: if( rc!=SQLITE_OK ){
714: sqlite3Fts3ExprFree(pRet);
715: sqlite3Fts3ExprFree(pNotBranch);
716: pRet = 0;
717: }
718: *ppExpr = pRet;
719: return rc;
720: }
721:
722: /*
723: ** Parameters z and n contain a pointer to and length of a buffer containing
724: ** an fts3 query expression, respectively. This function attempts to parse the
725: ** query expression and create a tree of Fts3Expr structures representing the
726: ** parsed expression. If successful, *ppExpr is set to point to the head
727: ** of the parsed expression tree and SQLITE_OK is returned. If an error
728: ** occurs, either SQLITE_NOMEM (out-of-memory error) or SQLITE_ERROR (parse
729: ** error) is returned and *ppExpr is set to 0.
730: **
731: ** If parameter n is a negative number, then z is assumed to point to a
732: ** nul-terminated string and the length is determined using strlen().
733: **
734: ** The first parameter, pTokenizer, is passed the fts3 tokenizer module to
735: ** use to normalize query tokens while parsing the expression. The azCol[]
736: ** array, which is assumed to contain nCol entries, should contain the names
737: ** of each column in the target fts3 table, in order from left to right.
738: ** Column names must be nul-terminated strings.
739: **
740: ** The iDefaultCol parameter should be passed the index of the table column
741: ** that appears on the left-hand-side of the MATCH operator (the default
742: ** column to match against for tokens for which a column name is not explicitly
743: ** specified as part of the query string), or -1 if tokens may by default
744: ** match any table column.
745: */
746: int sqlite3Fts3ExprParse(
747: sqlite3_tokenizer *pTokenizer, /* Tokenizer module */
748: char **azCol, /* Array of column names for fts3 table */
749: int bFts4, /* True to allow FTS4-only syntax */
750: int nCol, /* Number of entries in azCol[] */
751: int iDefaultCol, /* Default column to query */
752: const char *z, int n, /* Text of MATCH query */
753: Fts3Expr **ppExpr /* OUT: Parsed query structure */
754: ){
755: int nParsed;
756: int rc;
757: ParseContext sParse;
758: sParse.pTokenizer = pTokenizer;
759: sParse.azCol = (const char **)azCol;
760: sParse.nCol = nCol;
761: sParse.iDefaultCol = iDefaultCol;
762: sParse.nNest = 0;
763: sParse.bFts4 = bFts4;
764: if( z==0 ){
765: *ppExpr = 0;
766: return SQLITE_OK;
767: }
768: if( n<0 ){
769: n = (int)strlen(z);
770: }
771: rc = fts3ExprParse(&sParse, z, n, ppExpr, &nParsed);
772:
773: /* Check for mismatched parenthesis */
774: if( rc==SQLITE_OK && sParse.nNest ){
775: rc = SQLITE_ERROR;
776: sqlite3Fts3ExprFree(*ppExpr);
777: *ppExpr = 0;
778: }
779:
780: return rc;
781: }
782:
783: /*
784: ** Free a parsed fts3 query expression allocated by sqlite3Fts3ExprParse().
785: */
786: void sqlite3Fts3ExprFree(Fts3Expr *p){
787: if( p ){
788: assert( p->eType==FTSQUERY_PHRASE || p->pPhrase==0 );
789: sqlite3Fts3ExprFree(p->pLeft);
790: sqlite3Fts3ExprFree(p->pRight);
791: sqlite3Fts3EvalPhraseCleanup(p->pPhrase);
792: sqlite3_free(p->aMI);
793: sqlite3_free(p);
794: }
795: }
796:
797: /****************************************************************************
798: *****************************************************************************
799: ** Everything after this point is just test code.
800: */
801:
802: #ifdef SQLITE_TEST
803:
804: #include <stdio.h>
805:
806: /*
807: ** Function to query the hash-table of tokenizers (see README.tokenizers).
808: */
809: static int queryTestTokenizer(
810: sqlite3 *db,
811: const char *zName,
812: const sqlite3_tokenizer_module **pp
813: ){
814: int rc;
815: sqlite3_stmt *pStmt;
816: const char zSql[] = "SELECT fts3_tokenizer(?)";
817:
818: *pp = 0;
819: rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0);
820: if( rc!=SQLITE_OK ){
821: return rc;
822: }
823:
824: sqlite3_bind_text(pStmt, 1, zName, -1, SQLITE_STATIC);
825: if( SQLITE_ROW==sqlite3_step(pStmt) ){
826: if( sqlite3_column_type(pStmt, 0)==SQLITE_BLOB ){
827: memcpy((void *)pp, sqlite3_column_blob(pStmt, 0), sizeof(*pp));
828: }
829: }
830:
831: return sqlite3_finalize(pStmt);
832: }
833:
834: /*
835: ** Return a pointer to a buffer containing a text representation of the
836: ** expression passed as the first argument. The buffer is obtained from
837: ** sqlite3_malloc(). It is the responsibility of the caller to use
838: ** sqlite3_free() to release the memory. If an OOM condition is encountered,
839: ** NULL is returned.
840: **
841: ** If the second argument is not NULL, then its contents are prepended to
842: ** the returned expression text and then freed using sqlite3_free().
843: */
844: static char *exprToString(Fts3Expr *pExpr, char *zBuf){
845: switch( pExpr->eType ){
846: case FTSQUERY_PHRASE: {
847: Fts3Phrase *pPhrase = pExpr->pPhrase;
848: int i;
849: zBuf = sqlite3_mprintf(
850: "%zPHRASE %d 0", zBuf, pPhrase->iColumn);
851: for(i=0; zBuf && i<pPhrase->nToken; i++){
852: zBuf = sqlite3_mprintf("%z %.*s%s", zBuf,
853: pPhrase->aToken[i].n, pPhrase->aToken[i].z,
854: (pPhrase->aToken[i].isPrefix?"+":"")
855: );
856: }
857: return zBuf;
858: }
859:
860: case FTSQUERY_NEAR:
861: zBuf = sqlite3_mprintf("%zNEAR/%d ", zBuf, pExpr->nNear);
862: break;
863: case FTSQUERY_NOT:
864: zBuf = sqlite3_mprintf("%zNOT ", zBuf);
865: break;
866: case FTSQUERY_AND:
867: zBuf = sqlite3_mprintf("%zAND ", zBuf);
868: break;
869: case FTSQUERY_OR:
870: zBuf = sqlite3_mprintf("%zOR ", zBuf);
871: break;
872: }
873:
874: if( zBuf ) zBuf = sqlite3_mprintf("%z{", zBuf);
875: if( zBuf ) zBuf = exprToString(pExpr->pLeft, zBuf);
876: if( zBuf ) zBuf = sqlite3_mprintf("%z} {", zBuf);
877:
878: if( zBuf ) zBuf = exprToString(pExpr->pRight, zBuf);
879: if( zBuf ) zBuf = sqlite3_mprintf("%z}", zBuf);
880:
881: return zBuf;
882: }
883:
884: /*
885: ** This is the implementation of a scalar SQL function used to test the
886: ** expression parser. It should be called as follows:
887: **
888: ** fts3_exprtest(<tokenizer>, <expr>, <column 1>, ...);
889: **
890: ** The first argument, <tokenizer>, is the name of the fts3 tokenizer used
891: ** to parse the query expression (see README.tokenizers). The second argument
892: ** is the query expression to parse. Each subsequent argument is the name
893: ** of a column of the fts3 table that the query expression may refer to.
894: ** For example:
895: **
896: ** SELECT fts3_exprtest('simple', 'Bill col2:Bloggs', 'col1', 'col2');
897: */
898: static void fts3ExprTest(
899: sqlite3_context *context,
900: int argc,
901: sqlite3_value **argv
902: ){
903: sqlite3_tokenizer_module const *pModule = 0;
904: sqlite3_tokenizer *pTokenizer = 0;
905: int rc;
906: char **azCol = 0;
907: const char *zExpr;
908: int nExpr;
909: int nCol;
910: int ii;
911: Fts3Expr *pExpr;
912: char *zBuf = 0;
913: sqlite3 *db = sqlite3_context_db_handle(context);
914:
915: if( argc<3 ){
916: sqlite3_result_error(context,
917: "Usage: fts3_exprtest(tokenizer, expr, col1, ...", -1
918: );
919: return;
920: }
921:
922: rc = queryTestTokenizer(db,
923: (const char *)sqlite3_value_text(argv[0]), &pModule);
924: if( rc==SQLITE_NOMEM ){
925: sqlite3_result_error_nomem(context);
926: goto exprtest_out;
927: }else if( !pModule ){
928: sqlite3_result_error(context, "No such tokenizer module", -1);
929: goto exprtest_out;
930: }
931:
932: rc = pModule->xCreate(0, 0, &pTokenizer);
933: assert( rc==SQLITE_NOMEM || rc==SQLITE_OK );
934: if( rc==SQLITE_NOMEM ){
935: sqlite3_result_error_nomem(context);
936: goto exprtest_out;
937: }
938: pTokenizer->pModule = pModule;
939:
940: zExpr = (const char *)sqlite3_value_text(argv[1]);
941: nExpr = sqlite3_value_bytes(argv[1]);
942: nCol = argc-2;
943: azCol = (char **)sqlite3_malloc(nCol*sizeof(char *));
944: if( !azCol ){
945: sqlite3_result_error_nomem(context);
946: goto exprtest_out;
947: }
948: for(ii=0; ii<nCol; ii++){
949: azCol[ii] = (char *)sqlite3_value_text(argv[ii+2]);
950: }
951:
952: rc = sqlite3Fts3ExprParse(
953: pTokenizer, azCol, 0, nCol, nCol, zExpr, nExpr, &pExpr
954: );
955: if( rc!=SQLITE_OK && rc!=SQLITE_NOMEM ){
956: sqlite3_result_error(context, "Error parsing expression", -1);
957: }else if( rc==SQLITE_NOMEM || !(zBuf = exprToString(pExpr, 0)) ){
958: sqlite3_result_error_nomem(context);
959: }else{
960: sqlite3_result_text(context, zBuf, -1, SQLITE_TRANSIENT);
961: sqlite3_free(zBuf);
962: }
963:
964: sqlite3Fts3ExprFree(pExpr);
965:
966: exprtest_out:
967: if( pModule && pTokenizer ){
968: rc = pModule->xDestroy(pTokenizer);
969: }
970: sqlite3_free(azCol);
971: }
972:
973: /*
974: ** Register the query expression parser test function fts3_exprtest()
975: ** with database connection db.
976: */
977: int sqlite3Fts3ExprInitTestInterface(sqlite3* db){
978: return sqlite3_create_function(
979: db, "fts3_exprtest", -1, SQLITE_UTF8, 0, fts3ExprTest, 0, 0
980: );
981: }
982:
983: #endif
984: #endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3) */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to fts3_expr.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sqlite3 / ext / fts3