| 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) */ |