Index: third_party/sqlite/sqlite-src-3100200/ext/fts5/fts5_expr.c |
diff --git a/third_party/sqlite/sqlite-src-3100200/ext/fts5/fts5_expr.c b/third_party/sqlite/sqlite-src-3100200/ext/fts5/fts5_expr.c |
new file mode 100644 |
index 0000000000000000000000000000000000000000..a747a64c9bdf94fb08d998c83c5631678a9d0560 |
--- /dev/null |
+++ b/third_party/sqlite/sqlite-src-3100200/ext/fts5/fts5_expr.c |
@@ -0,0 +1,2237 @@ |
+/* |
+** 2014 May 31 |
+** |
+** The author disclaims copyright to this source code. In place of |
+** a legal notice, here is a blessing: |
+** |
+** May you do good and not evil. |
+** May you find forgiveness for yourself and forgive others. |
+** May you share freely, never taking more than you give. |
+** |
+****************************************************************************** |
+** |
+*/ |
+ |
+ |
+ |
+#include "fts5Int.h" |
+#include "fts5parse.h" |
+ |
+/* |
+** All token types in the generated fts5parse.h file are greater than 0. |
+*/ |
+#define FTS5_EOF 0 |
+ |
+#define FTS5_LARGEST_INT64 (0xffffffff|(((i64)0x7fffffff)<<32)) |
+ |
+typedef struct Fts5ExprTerm Fts5ExprTerm; |
+ |
+/* |
+** Functions generated by lemon from fts5parse.y. |
+*/ |
+void *sqlite3Fts5ParserAlloc(void *(*mallocProc)(u64)); |
+void sqlite3Fts5ParserFree(void*, void (*freeProc)(void*)); |
+void sqlite3Fts5Parser(void*, int, Fts5Token, Fts5Parse*); |
+#ifndef NDEBUG |
+#include <stdio.h> |
+void sqlite3Fts5ParserTrace(FILE*, char*); |
+#endif |
+ |
+ |
+struct Fts5Expr { |
+ Fts5Index *pIndex; |
+ Fts5ExprNode *pRoot; |
+ int bDesc; /* Iterate in descending rowid order */ |
+ int nPhrase; /* Number of phrases in expression */ |
+ Fts5ExprPhrase **apExprPhrase; /* Pointers to phrase objects */ |
+}; |
+ |
+/* |
+** eType: |
+** Expression node type. Always one of: |
+** |
+** FTS5_AND (nChild, apChild valid) |
+** FTS5_OR (nChild, apChild valid) |
+** FTS5_NOT (nChild, apChild valid) |
+** FTS5_STRING (pNear valid) |
+** FTS5_TERM (pNear valid) |
+*/ |
+struct Fts5ExprNode { |
+ int eType; /* Node type */ |
+ int bEof; /* True at EOF */ |
+ int bNomatch; /* True if entry is not a match */ |
+ |
+ i64 iRowid; /* Current rowid */ |
+ Fts5ExprNearset *pNear; /* For FTS5_STRING - cluster of phrases */ |
+ |
+ /* Child nodes. For a NOT node, this array always contains 2 entries. For |
+ ** AND or OR nodes, it contains 2 or more entries. */ |
+ int nChild; /* Number of child nodes */ |
+ Fts5ExprNode *apChild[1]; /* Array of child nodes */ |
+}; |
+ |
+#define Fts5NodeIsString(p) ((p)->eType==FTS5_TERM || (p)->eType==FTS5_STRING) |
+ |
+/* |
+** An instance of the following structure represents a single search term |
+** or term prefix. |
+*/ |
+struct Fts5ExprTerm { |
+ int bPrefix; /* True for a prefix term */ |
+ char *zTerm; /* nul-terminated term */ |
+ Fts5IndexIter *pIter; /* Iterator for this term */ |
+ Fts5ExprTerm *pSynonym; /* Pointer to first in list of synonyms */ |
+}; |
+ |
+/* |
+** A phrase. One or more terms that must appear in a contiguous sequence |
+** within a document for it to match. |
+*/ |
+struct Fts5ExprPhrase { |
+ Fts5ExprNode *pNode; /* FTS5_STRING node this phrase is part of */ |
+ Fts5Buffer poslist; /* Current position list */ |
+ int nTerm; /* Number of entries in aTerm[] */ |
+ Fts5ExprTerm aTerm[1]; /* Terms that make up this phrase */ |
+}; |
+ |
+/* |
+** One or more phrases that must appear within a certain token distance of |
+** each other within each matching document. |
+*/ |
+struct Fts5ExprNearset { |
+ int nNear; /* NEAR parameter */ |
+ Fts5Colset *pColset; /* Columns to search (NULL -> all columns) */ |
+ int nPhrase; /* Number of entries in aPhrase[] array */ |
+ Fts5ExprPhrase *apPhrase[1]; /* Array of phrase pointers */ |
+}; |
+ |
+ |
+/* |
+** Parse context. |
+*/ |
+struct Fts5Parse { |
+ Fts5Config *pConfig; |
+ char *zErr; |
+ int rc; |
+ int nPhrase; /* Size of apPhrase array */ |
+ Fts5ExprPhrase **apPhrase; /* Array of all phrases */ |
+ Fts5ExprNode *pExpr; /* Result of a successful parse */ |
+}; |
+ |
+void sqlite3Fts5ParseError(Fts5Parse *pParse, const char *zFmt, ...){ |
+ va_list ap; |
+ va_start(ap, zFmt); |
+ if( pParse->rc==SQLITE_OK ){ |
+ pParse->zErr = sqlite3_vmprintf(zFmt, ap); |
+ pParse->rc = SQLITE_ERROR; |
+ } |
+ va_end(ap); |
+} |
+ |
+static int fts5ExprIsspace(char t){ |
+ return t==' ' || t=='\t' || t=='\n' || t=='\r'; |
+} |
+ |
+/* |
+** Read the first token from the nul-terminated string at *pz. |
+*/ |
+static int fts5ExprGetToken( |
+ Fts5Parse *pParse, |
+ const char **pz, /* IN/OUT: Pointer into buffer */ |
+ Fts5Token *pToken |
+){ |
+ const char *z = *pz; |
+ int tok; |
+ |
+ /* Skip past any whitespace */ |
+ while( fts5ExprIsspace(*z) ) z++; |
+ |
+ pToken->p = z; |
+ pToken->n = 1; |
+ switch( *z ){ |
+ case '(': tok = FTS5_LP; break; |
+ case ')': tok = FTS5_RP; break; |
+ case '{': tok = FTS5_LCP; break; |
+ case '}': tok = FTS5_RCP; break; |
+ case ':': tok = FTS5_COLON; break; |
+ case ',': tok = FTS5_COMMA; break; |
+ case '+': tok = FTS5_PLUS; break; |
+ case '*': tok = FTS5_STAR; break; |
+ case '\0': tok = FTS5_EOF; break; |
+ |
+ case '"': { |
+ const char *z2; |
+ tok = FTS5_STRING; |
+ |
+ for(z2=&z[1]; 1; z2++){ |
+ if( z2[0]=='"' ){ |
+ z2++; |
+ if( z2[0]!='"' ) break; |
+ } |
+ if( z2[0]=='\0' ){ |
+ sqlite3Fts5ParseError(pParse, "unterminated string"); |
+ return FTS5_EOF; |
+ } |
+ } |
+ pToken->n = (z2 - z); |
+ break; |
+ } |
+ |
+ default: { |
+ const char *z2; |
+ if( sqlite3Fts5IsBareword(z[0])==0 ){ |
+ sqlite3Fts5ParseError(pParse, "fts5: syntax error near \"%.1s\"", z); |
+ return FTS5_EOF; |
+ } |
+ tok = FTS5_STRING; |
+ for(z2=&z[1]; sqlite3Fts5IsBareword(*z2); z2++); |
+ pToken->n = (z2 - z); |
+ if( pToken->n==2 && memcmp(pToken->p, "OR", 2)==0 ) tok = FTS5_OR; |
+ if( pToken->n==3 && memcmp(pToken->p, "NOT", 3)==0 ) tok = FTS5_NOT; |
+ if( pToken->n==3 && memcmp(pToken->p, "AND", 3)==0 ) tok = FTS5_AND; |
+ break; |
+ } |
+ } |
+ |
+ *pz = &pToken->p[pToken->n]; |
+ return tok; |
+} |
+ |
+static void *fts5ParseAlloc(u64 t){ return sqlite3_malloc((int)t); } |
+static void fts5ParseFree(void *p){ sqlite3_free(p); } |
+ |
+int sqlite3Fts5ExprNew( |
+ Fts5Config *pConfig, /* FTS5 Configuration */ |
+ const char *zExpr, /* Expression text */ |
+ Fts5Expr **ppNew, |
+ char **pzErr |
+){ |
+ Fts5Parse sParse; |
+ Fts5Token token; |
+ const char *z = zExpr; |
+ int t; /* Next token type */ |
+ void *pEngine; |
+ Fts5Expr *pNew; |
+ |
+ *ppNew = 0; |
+ *pzErr = 0; |
+ memset(&sParse, 0, sizeof(sParse)); |
+ pEngine = sqlite3Fts5ParserAlloc(fts5ParseAlloc); |
+ if( pEngine==0 ){ return SQLITE_NOMEM; } |
+ sParse.pConfig = pConfig; |
+ |
+ do { |
+ t = fts5ExprGetToken(&sParse, &z, &token); |
+ sqlite3Fts5Parser(pEngine, t, token, &sParse); |
+ }while( sParse.rc==SQLITE_OK && t!=FTS5_EOF ); |
+ sqlite3Fts5ParserFree(pEngine, fts5ParseFree); |
+ |
+ assert( sParse.rc!=SQLITE_OK || sParse.zErr==0 ); |
+ if( sParse.rc==SQLITE_OK ){ |
+ *ppNew = pNew = sqlite3_malloc(sizeof(Fts5Expr)); |
+ if( pNew==0 ){ |
+ sParse.rc = SQLITE_NOMEM; |
+ sqlite3Fts5ParseNodeFree(sParse.pExpr); |
+ }else{ |
+ pNew->pRoot = sParse.pExpr; |
+ pNew->pIndex = 0; |
+ pNew->apExprPhrase = sParse.apPhrase; |
+ pNew->nPhrase = sParse.nPhrase; |
+ sParse.apPhrase = 0; |
+ } |
+ } |
+ |
+ sqlite3_free(sParse.apPhrase); |
+ *pzErr = sParse.zErr; |
+ return sParse.rc; |
+} |
+ |
+/* |
+** Free the expression node object passed as the only argument. |
+*/ |
+void sqlite3Fts5ParseNodeFree(Fts5ExprNode *p){ |
+ if( p ){ |
+ int i; |
+ for(i=0; i<p->nChild; i++){ |
+ sqlite3Fts5ParseNodeFree(p->apChild[i]); |
+ } |
+ sqlite3Fts5ParseNearsetFree(p->pNear); |
+ sqlite3_free(p); |
+ } |
+} |
+ |
+/* |
+** Free the expression object passed as the only argument. |
+*/ |
+void sqlite3Fts5ExprFree(Fts5Expr *p){ |
+ if( p ){ |
+ sqlite3Fts5ParseNodeFree(p->pRoot); |
+ sqlite3_free(p->apExprPhrase); |
+ sqlite3_free(p); |
+ } |
+} |
+ |
+/* |
+** Argument pTerm must be a synonym iterator. Return the current rowid |
+** that it points to. |
+*/ |
+static i64 fts5ExprSynonymRowid(Fts5ExprTerm *pTerm, int bDesc, int *pbEof){ |
+ i64 iRet = 0; |
+ int bRetValid = 0; |
+ Fts5ExprTerm *p; |
+ |
+ assert( pTerm->pSynonym ); |
+ assert( bDesc==0 || bDesc==1 ); |
+ for(p=pTerm; p; p=p->pSynonym){ |
+ if( 0==sqlite3Fts5IterEof(p->pIter) ){ |
+ i64 iRowid = sqlite3Fts5IterRowid(p->pIter); |
+ if( bRetValid==0 || (bDesc!=(iRowid<iRet)) ){ |
+ iRet = iRowid; |
+ bRetValid = 1; |
+ } |
+ } |
+ } |
+ |
+ if( pbEof && bRetValid==0 ) *pbEof = 1; |
+ return iRet; |
+} |
+ |
+/* |
+** Argument pTerm must be a synonym iterator. |
+*/ |
+static int fts5ExprSynonymPoslist( |
+ Fts5ExprTerm *pTerm, |
+ Fts5Colset *pColset, |
+ i64 iRowid, |
+ int *pbDel, /* OUT: Caller should sqlite3_free(*pa) */ |
+ u8 **pa, int *pn |
+){ |
+ Fts5PoslistReader aStatic[4]; |
+ Fts5PoslistReader *aIter = aStatic; |
+ int nIter = 0; |
+ int nAlloc = 4; |
+ int rc = SQLITE_OK; |
+ Fts5ExprTerm *p; |
+ |
+ assert( pTerm->pSynonym ); |
+ for(p=pTerm; p; p=p->pSynonym){ |
+ Fts5IndexIter *pIter = p->pIter; |
+ if( sqlite3Fts5IterEof(pIter)==0 && sqlite3Fts5IterRowid(pIter)==iRowid ){ |
+ const u8 *a; |
+ int n; |
+ i64 dummy; |
+ rc = sqlite3Fts5IterPoslist(pIter, pColset, &a, &n, &dummy); |
+ if( rc!=SQLITE_OK ) goto synonym_poslist_out; |
+ if( nIter==nAlloc ){ |
+ int nByte = sizeof(Fts5PoslistReader) * nAlloc * 2; |
+ Fts5PoslistReader *aNew = (Fts5PoslistReader*)sqlite3_malloc(nByte); |
+ if( aNew==0 ){ |
+ rc = SQLITE_NOMEM; |
+ goto synonym_poslist_out; |
+ } |
+ memcpy(aNew, aIter, sizeof(Fts5PoslistReader) * nIter); |
+ nAlloc = nAlloc*2; |
+ if( aIter!=aStatic ) sqlite3_free(aIter); |
+ aIter = aNew; |
+ } |
+ sqlite3Fts5PoslistReaderInit(a, n, &aIter[nIter]); |
+ assert( aIter[nIter].bEof==0 ); |
+ nIter++; |
+ } |
+ } |
+ |
+ assert( *pbDel==0 ); |
+ if( nIter==1 ){ |
+ *pa = (u8*)aIter[0].a; |
+ *pn = aIter[0].n; |
+ }else{ |
+ Fts5PoslistWriter writer = {0}; |
+ Fts5Buffer buf = {0,0,0}; |
+ i64 iPrev = -1; |
+ while( 1 ){ |
+ int i; |
+ i64 iMin = FTS5_LARGEST_INT64; |
+ for(i=0; i<nIter; i++){ |
+ if( aIter[i].bEof==0 ){ |
+ if( aIter[i].iPos==iPrev ){ |
+ if( sqlite3Fts5PoslistReaderNext(&aIter[i]) ) continue; |
+ } |
+ if( aIter[i].iPos<iMin ){ |
+ iMin = aIter[i].iPos; |
+ } |
+ } |
+ } |
+ if( iMin==FTS5_LARGEST_INT64 || rc!=SQLITE_OK ) break; |
+ rc = sqlite3Fts5PoslistWriterAppend(&buf, &writer, iMin); |
+ iPrev = iMin; |
+ } |
+ if( rc ){ |
+ sqlite3_free(buf.p); |
+ }else{ |
+ *pa = buf.p; |
+ *pn = buf.n; |
+ *pbDel = 1; |
+ } |
+ } |
+ |
+ synonym_poslist_out: |
+ if( aIter!=aStatic ) sqlite3_free(aIter); |
+ return rc; |
+} |
+ |
+ |
+/* |
+** All individual term iterators in pPhrase are guaranteed to be valid and |
+** pointing to the same rowid when this function is called. This function |
+** checks if the current rowid really is a match, and if so populates |
+** the pPhrase->poslist buffer accordingly. Output parameter *pbMatch |
+** is set to true if this is really a match, or false otherwise. |
+** |
+** SQLITE_OK is returned if an error occurs, or an SQLite error code |
+** otherwise. It is not considered an error code if the current rowid is |
+** not a match. |
+*/ |
+static int fts5ExprPhraseIsMatch( |
+ Fts5ExprNode *pNode, /* Node pPhrase belongs to */ |
+ Fts5Colset *pColset, /* Restrict matches to these columns */ |
+ Fts5ExprPhrase *pPhrase, /* Phrase object to initialize */ |
+ int *pbMatch /* OUT: Set to true if really a match */ |
+){ |
+ Fts5PoslistWriter writer = {0}; |
+ Fts5PoslistReader aStatic[4]; |
+ Fts5PoslistReader *aIter = aStatic; |
+ int i; |
+ int rc = SQLITE_OK; |
+ |
+ fts5BufferZero(&pPhrase->poslist); |
+ |
+ /* If the aStatic[] array is not large enough, allocate a large array |
+ ** using sqlite3_malloc(). This approach could be improved upon. */ |
+ if( pPhrase->nTerm>(int)ArraySize(aStatic) ){ |
+ int nByte = sizeof(Fts5PoslistReader) * pPhrase->nTerm; |
+ aIter = (Fts5PoslistReader*)sqlite3_malloc(nByte); |
+ if( !aIter ) return SQLITE_NOMEM; |
+ } |
+ memset(aIter, 0, sizeof(Fts5PoslistReader) * pPhrase->nTerm); |
+ |
+ /* Initialize a term iterator for each term in the phrase */ |
+ for(i=0; i<pPhrase->nTerm; i++){ |
+ Fts5ExprTerm *pTerm = &pPhrase->aTerm[i]; |
+ i64 dummy; |
+ int n = 0; |
+ int bFlag = 0; |
+ const u8 *a = 0; |
+ if( pTerm->pSynonym ){ |
+ rc = fts5ExprSynonymPoslist( |
+ pTerm, pColset, pNode->iRowid, &bFlag, (u8**)&a, &n |
+ ); |
+ }else{ |
+ rc = sqlite3Fts5IterPoslist(pTerm->pIter, pColset, &a, &n, &dummy); |
+ } |
+ if( rc!=SQLITE_OK ) goto ismatch_out; |
+ sqlite3Fts5PoslistReaderInit(a, n, &aIter[i]); |
+ aIter[i].bFlag = (u8)bFlag; |
+ if( aIter[i].bEof ) goto ismatch_out; |
+ } |
+ |
+ while( 1 ){ |
+ int bMatch; |
+ i64 iPos = aIter[0].iPos; |
+ do { |
+ bMatch = 1; |
+ for(i=0; i<pPhrase->nTerm; i++){ |
+ Fts5PoslistReader *pPos = &aIter[i]; |
+ i64 iAdj = iPos + i; |
+ if( pPos->iPos!=iAdj ){ |
+ bMatch = 0; |
+ while( pPos->iPos<iAdj ){ |
+ if( sqlite3Fts5PoslistReaderNext(pPos) ) goto ismatch_out; |
+ } |
+ if( pPos->iPos>iAdj ) iPos = pPos->iPos-i; |
+ } |
+ } |
+ }while( bMatch==0 ); |
+ |
+ /* Append position iPos to the output */ |
+ rc = sqlite3Fts5PoslistWriterAppend(&pPhrase->poslist, &writer, iPos); |
+ if( rc!=SQLITE_OK ) goto ismatch_out; |
+ |
+ for(i=0; i<pPhrase->nTerm; i++){ |
+ if( sqlite3Fts5PoslistReaderNext(&aIter[i]) ) goto ismatch_out; |
+ } |
+ } |
+ |
+ ismatch_out: |
+ *pbMatch = (pPhrase->poslist.n>0); |
+ for(i=0; i<pPhrase->nTerm; i++){ |
+ if( aIter[i].bFlag ) sqlite3_free((u8*)aIter[i].a); |
+ } |
+ if( aIter!=aStatic ) sqlite3_free(aIter); |
+ return rc; |
+} |
+ |
+typedef struct Fts5LookaheadReader Fts5LookaheadReader; |
+struct Fts5LookaheadReader { |
+ const u8 *a; /* Buffer containing position list */ |
+ int n; /* Size of buffer a[] in bytes */ |
+ int i; /* Current offset in position list */ |
+ i64 iPos; /* Current position */ |
+ i64 iLookahead; /* Next position */ |
+}; |
+ |
+#define FTS5_LOOKAHEAD_EOF (((i64)1) << 62) |
+ |
+static int fts5LookaheadReaderNext(Fts5LookaheadReader *p){ |
+ p->iPos = p->iLookahead; |
+ if( sqlite3Fts5PoslistNext64(p->a, p->n, &p->i, &p->iLookahead) ){ |
+ p->iLookahead = FTS5_LOOKAHEAD_EOF; |
+ } |
+ return (p->iPos==FTS5_LOOKAHEAD_EOF); |
+} |
+ |
+static int fts5LookaheadReaderInit( |
+ const u8 *a, int n, /* Buffer to read position list from */ |
+ Fts5LookaheadReader *p /* Iterator object to initialize */ |
+){ |
+ memset(p, 0, sizeof(Fts5LookaheadReader)); |
+ p->a = a; |
+ p->n = n; |
+ fts5LookaheadReaderNext(p); |
+ return fts5LookaheadReaderNext(p); |
+} |
+ |
+#if 0 |
+static int fts5LookaheadReaderEof(Fts5LookaheadReader *p){ |
+ return (p->iPos==FTS5_LOOKAHEAD_EOF); |
+} |
+#endif |
+ |
+typedef struct Fts5NearTrimmer Fts5NearTrimmer; |
+struct Fts5NearTrimmer { |
+ Fts5LookaheadReader reader; /* Input iterator */ |
+ Fts5PoslistWriter writer; /* Writer context */ |
+ Fts5Buffer *pOut; /* Output poslist */ |
+}; |
+ |
+/* |
+** The near-set object passed as the first argument contains more than |
+** one phrase. All phrases currently point to the same row. The |
+** Fts5ExprPhrase.poslist buffers are populated accordingly. This function |
+** tests if the current row contains instances of each phrase sufficiently |
+** close together to meet the NEAR constraint. Non-zero is returned if it |
+** does, or zero otherwise. |
+** |
+** If in/out parameter (*pRc) is set to other than SQLITE_OK when this |
+** function is called, it is a no-op. Or, if an error (e.g. SQLITE_NOMEM) |
+** occurs within this function (*pRc) is set accordingly before returning. |
+** The return value is undefined in both these cases. |
+** |
+** If no error occurs and non-zero (a match) is returned, the position-list |
+** of each phrase object is edited to contain only those entries that |
+** meet the constraint before returning. |
+*/ |
+static int fts5ExprNearIsMatch(int *pRc, Fts5ExprNearset *pNear){ |
+ Fts5NearTrimmer aStatic[4]; |
+ Fts5NearTrimmer *a = aStatic; |
+ Fts5ExprPhrase **apPhrase = pNear->apPhrase; |
+ |
+ int i; |
+ int rc = *pRc; |
+ int bMatch; |
+ |
+ assert( pNear->nPhrase>1 ); |
+ |
+ /* If the aStatic[] array is not large enough, allocate a large array |
+ ** using sqlite3_malloc(). This approach could be improved upon. */ |
+ if( pNear->nPhrase>(int)ArraySize(aStatic) ){ |
+ int nByte = sizeof(Fts5NearTrimmer) * pNear->nPhrase; |
+ a = (Fts5NearTrimmer*)sqlite3Fts5MallocZero(&rc, nByte); |
+ }else{ |
+ memset(aStatic, 0, sizeof(aStatic)); |
+ } |
+ if( rc!=SQLITE_OK ){ |
+ *pRc = rc; |
+ return 0; |
+ } |
+ |
+ /* Initialize a lookahead iterator for each phrase. After passing the |
+ ** buffer and buffer size to the lookaside-reader init function, zero |
+ ** the phrase poslist buffer. The new poslist for the phrase (containing |
+ ** the same entries as the original with some entries removed on account |
+ ** of the NEAR constraint) is written over the original even as it is |
+ ** being read. This is safe as the entries for the new poslist are a |
+ ** subset of the old, so it is not possible for data yet to be read to |
+ ** be overwritten. */ |
+ for(i=0; i<pNear->nPhrase; i++){ |
+ Fts5Buffer *pPoslist = &apPhrase[i]->poslist; |
+ fts5LookaheadReaderInit(pPoslist->p, pPoslist->n, &a[i].reader); |
+ pPoslist->n = 0; |
+ a[i].pOut = pPoslist; |
+ } |
+ |
+ while( 1 ){ |
+ int iAdv; |
+ i64 iMin; |
+ i64 iMax; |
+ |
+ /* This block advances the phrase iterators until they point to a set of |
+ ** entries that together comprise a match. */ |
+ iMax = a[0].reader.iPos; |
+ do { |
+ bMatch = 1; |
+ for(i=0; i<pNear->nPhrase; i++){ |
+ Fts5LookaheadReader *pPos = &a[i].reader; |
+ iMin = iMax - pNear->apPhrase[i]->nTerm - pNear->nNear; |
+ if( pPos->iPos<iMin || pPos->iPos>iMax ){ |
+ bMatch = 0; |
+ while( pPos->iPos<iMin ){ |
+ if( fts5LookaheadReaderNext(pPos) ) goto ismatch_out; |
+ } |
+ if( pPos->iPos>iMax ) iMax = pPos->iPos; |
+ } |
+ } |
+ }while( bMatch==0 ); |
+ |
+ /* Add an entry to each output position list */ |
+ for(i=0; i<pNear->nPhrase; i++){ |
+ i64 iPos = a[i].reader.iPos; |
+ Fts5PoslistWriter *pWriter = &a[i].writer; |
+ if( a[i].pOut->n==0 || iPos!=pWriter->iPrev ){ |
+ sqlite3Fts5PoslistWriterAppend(a[i].pOut, pWriter, iPos); |
+ } |
+ } |
+ |
+ iAdv = 0; |
+ iMin = a[0].reader.iLookahead; |
+ for(i=0; i<pNear->nPhrase; i++){ |
+ if( a[i].reader.iLookahead < iMin ){ |
+ iMin = a[i].reader.iLookahead; |
+ iAdv = i; |
+ } |
+ } |
+ if( fts5LookaheadReaderNext(&a[iAdv].reader) ) goto ismatch_out; |
+ } |
+ |
+ ismatch_out: { |
+ int bRet = a[0].pOut->n>0; |
+ *pRc = rc; |
+ if( a!=aStatic ) sqlite3_free(a); |
+ return bRet; |
+ } |
+} |
+ |
+/* |
+** Advance the first term iterator in the first phrase of pNear. Set output |
+** variable *pbEof to true if it reaches EOF or if an error occurs. |
+** |
+** Return SQLITE_OK if successful, or an SQLite error code if an error |
+** occurs. |
+*/ |
+static int fts5ExprNearAdvanceFirst( |
+ Fts5Expr *pExpr, /* Expression pPhrase belongs to */ |
+ Fts5ExprNode *pNode, /* FTS5_STRING or FTS5_TERM node */ |
+ int bFromValid, |
+ i64 iFrom |
+){ |
+ Fts5ExprTerm *pTerm = &pNode->pNear->apPhrase[0]->aTerm[0]; |
+ int rc = SQLITE_OK; |
+ |
+ if( pTerm->pSynonym ){ |
+ int bEof = 1; |
+ Fts5ExprTerm *p; |
+ |
+ /* Find the firstest rowid any synonym points to. */ |
+ i64 iRowid = fts5ExprSynonymRowid(pTerm, pExpr->bDesc, 0); |
+ |
+ /* Advance each iterator that currently points to iRowid. Or, if iFrom |
+ ** is valid - each iterator that points to a rowid before iFrom. */ |
+ for(p=pTerm; p; p=p->pSynonym){ |
+ if( sqlite3Fts5IterEof(p->pIter)==0 ){ |
+ i64 ii = sqlite3Fts5IterRowid(p->pIter); |
+ if( ii==iRowid |
+ || (bFromValid && ii!=iFrom && (ii>iFrom)==pExpr->bDesc) |
+ ){ |
+ if( bFromValid ){ |
+ rc = sqlite3Fts5IterNextFrom(p->pIter, iFrom); |
+ }else{ |
+ rc = sqlite3Fts5IterNext(p->pIter); |
+ } |
+ if( rc!=SQLITE_OK ) break; |
+ if( sqlite3Fts5IterEof(p->pIter)==0 ){ |
+ bEof = 0; |
+ } |
+ }else{ |
+ bEof = 0; |
+ } |
+ } |
+ } |
+ |
+ /* Set the EOF flag if either all synonym iterators are at EOF or an |
+ ** error has occurred. */ |
+ pNode->bEof = (rc || bEof); |
+ }else{ |
+ Fts5IndexIter *pIter = pTerm->pIter; |
+ |
+ assert( Fts5NodeIsString(pNode) ); |
+ if( bFromValid ){ |
+ rc = sqlite3Fts5IterNextFrom(pIter, iFrom); |
+ }else{ |
+ rc = sqlite3Fts5IterNext(pIter); |
+ } |
+ |
+ pNode->bEof = (rc || sqlite3Fts5IterEof(pIter)); |
+ } |
+ |
+ return rc; |
+} |
+ |
+/* |
+** Advance iterator pIter until it points to a value equal to or laster |
+** than the initial value of *piLast. If this means the iterator points |
+** to a value laster than *piLast, update *piLast to the new lastest value. |
+** |
+** If the iterator reaches EOF, set *pbEof to true before returning. If |
+** an error occurs, set *pRc to an error code. If either *pbEof or *pRc |
+** are set, return a non-zero value. Otherwise, return zero. |
+*/ |
+static int fts5ExprAdvanceto( |
+ Fts5IndexIter *pIter, /* Iterator to advance */ |
+ int bDesc, /* True if iterator is "rowid DESC" */ |
+ i64 *piLast, /* IN/OUT: Lastest rowid seen so far */ |
+ int *pRc, /* OUT: Error code */ |
+ int *pbEof /* OUT: Set to true if EOF */ |
+){ |
+ i64 iLast = *piLast; |
+ i64 iRowid; |
+ |
+ iRowid = sqlite3Fts5IterRowid(pIter); |
+ if( (bDesc==0 && iLast>iRowid) || (bDesc && iLast<iRowid) ){ |
+ int rc = sqlite3Fts5IterNextFrom(pIter, iLast); |
+ if( rc || sqlite3Fts5IterEof(pIter) ){ |
+ *pRc = rc; |
+ *pbEof = 1; |
+ return 1; |
+ } |
+ iRowid = sqlite3Fts5IterRowid(pIter); |
+ assert( (bDesc==0 && iRowid>=iLast) || (bDesc==1 && iRowid<=iLast) ); |
+ } |
+ *piLast = iRowid; |
+ |
+ return 0; |
+} |
+ |
+static int fts5ExprSynonymAdvanceto( |
+ Fts5ExprTerm *pTerm, /* Term iterator to advance */ |
+ int bDesc, /* True if iterator is "rowid DESC" */ |
+ i64 *piLast, /* IN/OUT: Lastest rowid seen so far */ |
+ int *pRc /* OUT: Error code */ |
+){ |
+ int rc = SQLITE_OK; |
+ i64 iLast = *piLast; |
+ Fts5ExprTerm *p; |
+ int bEof = 0; |
+ |
+ for(p=pTerm; rc==SQLITE_OK && p; p=p->pSynonym){ |
+ if( sqlite3Fts5IterEof(p->pIter)==0 ){ |
+ i64 iRowid = sqlite3Fts5IterRowid(p->pIter); |
+ if( (bDesc==0 && iLast>iRowid) || (bDesc && iLast<iRowid) ){ |
+ rc = sqlite3Fts5IterNextFrom(p->pIter, iLast); |
+ } |
+ } |
+ } |
+ |
+ if( rc!=SQLITE_OK ){ |
+ *pRc = rc; |
+ bEof = 1; |
+ }else{ |
+ *piLast = fts5ExprSynonymRowid(pTerm, bDesc, &bEof); |
+ } |
+ return bEof; |
+} |
+ |
+ |
+static int fts5ExprNearTest( |
+ int *pRc, |
+ Fts5Expr *pExpr, /* Expression that pNear is a part of */ |
+ Fts5ExprNode *pNode /* The "NEAR" node (FTS5_STRING) */ |
+){ |
+ Fts5ExprNearset *pNear = pNode->pNear; |
+ int rc = *pRc; |
+ int i; |
+ |
+ /* Check that each phrase in the nearset matches the current row. |
+ ** Populate the pPhrase->poslist buffers at the same time. If any |
+ ** phrase is not a match, break out of the loop early. */ |
+ for(i=0; rc==SQLITE_OK && i<pNear->nPhrase; i++){ |
+ Fts5ExprPhrase *pPhrase = pNear->apPhrase[i]; |
+ if( pPhrase->nTerm>1 || pPhrase->aTerm[0].pSynonym || pNear->pColset ){ |
+ int bMatch = 0; |
+ rc = fts5ExprPhraseIsMatch(pNode, pNear->pColset, pPhrase, &bMatch); |
+ if( bMatch==0 ) break; |
+ }else{ |
+ rc = sqlite3Fts5IterPoslistBuffer( |
+ pPhrase->aTerm[0].pIter, &pPhrase->poslist |
+ ); |
+ } |
+ } |
+ |
+ *pRc = rc; |
+ if( i==pNear->nPhrase && (i==1 || fts5ExprNearIsMatch(pRc, pNear)) ){ |
+ return 1; |
+ } |
+ |
+ return 0; |
+} |
+ |
+static int fts5ExprTokenTest( |
+ Fts5Expr *pExpr, /* Expression that pNear is a part of */ |
+ Fts5ExprNode *pNode /* The "NEAR" node (FTS5_TERM) */ |
+){ |
+ /* As this "NEAR" object is actually a single phrase that consists |
+ ** of a single term only, grab pointers into the poslist managed by the |
+ ** fts5_index.c iterator object. This is much faster than synthesizing |
+ ** a new poslist the way we have to for more complicated phrase or NEAR |
+ ** expressions. */ |
+ Fts5ExprNearset *pNear = pNode->pNear; |
+ Fts5ExprPhrase *pPhrase = pNear->apPhrase[0]; |
+ Fts5IndexIter *pIter = pPhrase->aTerm[0].pIter; |
+ Fts5Colset *pColset = pNear->pColset; |
+ int rc; |
+ |
+ assert( pNode->eType==FTS5_TERM ); |
+ assert( pNear->nPhrase==1 && pPhrase->nTerm==1 ); |
+ assert( pPhrase->aTerm[0].pSynonym==0 ); |
+ |
+ rc = sqlite3Fts5IterPoslist(pIter, pColset, |
+ (const u8**)&pPhrase->poslist.p, &pPhrase->poslist.n, &pNode->iRowid |
+ ); |
+ pNode->bNomatch = (pPhrase->poslist.n==0); |
+ return rc; |
+} |
+ |
+/* |
+** All individual term iterators in pNear are guaranteed to be valid when |
+** this function is called. This function checks if all term iterators |
+** point to the same rowid, and if not, advances them until they do. |
+** If an EOF is reached before this happens, *pbEof is set to true before |
+** returning. |
+** |
+** SQLITE_OK is returned if an error occurs, or an SQLite error code |
+** otherwise. It is not considered an error code if an iterator reaches |
+** EOF. |
+*/ |
+static int fts5ExprNearNextMatch( |
+ Fts5Expr *pExpr, /* Expression pPhrase belongs to */ |
+ Fts5ExprNode *pNode |
+){ |
+ Fts5ExprNearset *pNear = pNode->pNear; |
+ Fts5ExprPhrase *pLeft = pNear->apPhrase[0]; |
+ int rc = SQLITE_OK; |
+ i64 iLast; /* Lastest rowid any iterator points to */ |
+ int i, j; /* Phrase and token index, respectively */ |
+ int bMatch; /* True if all terms are at the same rowid */ |
+ const int bDesc = pExpr->bDesc; |
+ |
+ /* Check that this node should not be FTS5_TERM */ |
+ assert( pNear->nPhrase>1 |
+ || pNear->apPhrase[0]->nTerm>1 |
+ || pNear->apPhrase[0]->aTerm[0].pSynonym |
+ ); |
+ |
+ /* Initialize iLast, the "lastest" rowid any iterator points to. If the |
+ ** iterator skips through rowids in the default ascending order, this means |
+ ** the maximum rowid. Or, if the iterator is "ORDER BY rowid DESC", then it |
+ ** means the minimum rowid. */ |
+ if( pLeft->aTerm[0].pSynonym ){ |
+ iLast = fts5ExprSynonymRowid(&pLeft->aTerm[0], bDesc, 0); |
+ }else{ |
+ iLast = sqlite3Fts5IterRowid(pLeft->aTerm[0].pIter); |
+ } |
+ |
+ do { |
+ bMatch = 1; |
+ for(i=0; i<pNear->nPhrase; i++){ |
+ Fts5ExprPhrase *pPhrase = pNear->apPhrase[i]; |
+ for(j=0; j<pPhrase->nTerm; j++){ |
+ Fts5ExprTerm *pTerm = &pPhrase->aTerm[j]; |
+ if( pTerm->pSynonym ){ |
+ i64 iRowid = fts5ExprSynonymRowid(pTerm, bDesc, 0); |
+ if( iRowid==iLast ) continue; |
+ bMatch = 0; |
+ if( fts5ExprSynonymAdvanceto(pTerm, bDesc, &iLast, &rc) ){ |
+ pNode->bEof = 1; |
+ return rc; |
+ } |
+ }else{ |
+ Fts5IndexIter *pIter = pPhrase->aTerm[j].pIter; |
+ i64 iRowid = sqlite3Fts5IterRowid(pIter); |
+ if( iRowid==iLast ) continue; |
+ bMatch = 0; |
+ if( fts5ExprAdvanceto(pIter, bDesc, &iLast, &rc, &pNode->bEof) ){ |
+ return rc; |
+ } |
+ } |
+ } |
+ } |
+ }while( bMatch==0 ); |
+ |
+ pNode->iRowid = iLast; |
+ pNode->bNomatch = (0==fts5ExprNearTest(&rc, pExpr, pNode)); |
+ |
+ return rc; |
+} |
+ |
+/* |
+** Initialize all term iterators in the pNear object. If any term is found |
+** to match no documents at all, return immediately without initializing any |
+** further iterators. |
+*/ |
+static int fts5ExprNearInitAll( |
+ Fts5Expr *pExpr, |
+ Fts5ExprNode *pNode |
+){ |
+ Fts5ExprNearset *pNear = pNode->pNear; |
+ int i, j; |
+ int rc = SQLITE_OK; |
+ |
+ for(i=0; rc==SQLITE_OK && i<pNear->nPhrase; i++){ |
+ Fts5ExprPhrase *pPhrase = pNear->apPhrase[i]; |
+ for(j=0; j<pPhrase->nTerm; j++){ |
+ Fts5ExprTerm *pTerm = &pPhrase->aTerm[j]; |
+ Fts5ExprTerm *p; |
+ int bEof = 1; |
+ |
+ for(p=pTerm; p && rc==SQLITE_OK; p=p->pSynonym){ |
+ if( p->pIter ){ |
+ sqlite3Fts5IterClose(p->pIter); |
+ p->pIter = 0; |
+ } |
+ rc = sqlite3Fts5IndexQuery( |
+ pExpr->pIndex, p->zTerm, (int)strlen(p->zTerm), |
+ (pTerm->bPrefix ? FTS5INDEX_QUERY_PREFIX : 0) | |
+ (pExpr->bDesc ? FTS5INDEX_QUERY_DESC : 0), |
+ pNear->pColset, |
+ &p->pIter |
+ ); |
+ assert( rc==SQLITE_OK || p->pIter==0 ); |
+ if( p->pIter && 0==sqlite3Fts5IterEof(p->pIter) ){ |
+ bEof = 0; |
+ } |
+ } |
+ |
+ if( bEof ){ |
+ pNode->bEof = 1; |
+ return rc; |
+ } |
+ } |
+ } |
+ |
+ return rc; |
+} |
+ |
+/* fts5ExprNodeNext() calls fts5ExprNodeNextMatch(). And vice-versa. */ |
+static int fts5ExprNodeNextMatch(Fts5Expr*, Fts5ExprNode*); |
+ |
+ |
+/* |
+** If pExpr is an ASC iterator, this function returns a value with the |
+** same sign as: |
+** |
+** (iLhs - iRhs) |
+** |
+** Otherwise, if this is a DESC iterator, the opposite is returned: |
+** |
+** (iRhs - iLhs) |
+*/ |
+static int fts5RowidCmp( |
+ Fts5Expr *pExpr, |
+ i64 iLhs, |
+ i64 iRhs |
+){ |
+ assert( pExpr->bDesc==0 || pExpr->bDesc==1 ); |
+ if( pExpr->bDesc==0 ){ |
+ if( iLhs<iRhs ) return -1; |
+ return (iLhs > iRhs); |
+ }else{ |
+ if( iLhs>iRhs ) return -1; |
+ return (iLhs < iRhs); |
+ } |
+} |
+ |
+static void fts5ExprSetEof(Fts5ExprNode *pNode){ |
+ int i; |
+ pNode->bEof = 1; |
+ for(i=0; i<pNode->nChild; i++){ |
+ fts5ExprSetEof(pNode->apChild[i]); |
+ } |
+} |
+ |
+static void fts5ExprNodeZeroPoslist(Fts5ExprNode *pNode){ |
+ if( pNode->eType==FTS5_STRING || pNode->eType==FTS5_TERM ){ |
+ Fts5ExprNearset *pNear = pNode->pNear; |
+ int i; |
+ for(i=0; i<pNear->nPhrase; i++){ |
+ Fts5ExprPhrase *pPhrase = pNear->apPhrase[i]; |
+ pPhrase->poslist.n = 0; |
+ } |
+ }else{ |
+ int i; |
+ for(i=0; i<pNode->nChild; i++){ |
+ fts5ExprNodeZeroPoslist(pNode->apChild[i]); |
+ } |
+ } |
+} |
+ |
+ |
+static int fts5ExprNodeNext(Fts5Expr*, Fts5ExprNode*, int, i64); |
+ |
+/* |
+** Argument pNode is an FTS5_AND node. |
+*/ |
+static int fts5ExprAndNextRowid( |
+ Fts5Expr *pExpr, /* Expression pPhrase belongs to */ |
+ Fts5ExprNode *pAnd /* FTS5_AND node to advance */ |
+){ |
+ int iChild; |
+ i64 iLast = pAnd->iRowid; |
+ int rc = SQLITE_OK; |
+ int bMatch; |
+ |
+ assert( pAnd->bEof==0 ); |
+ do { |
+ pAnd->bNomatch = 0; |
+ bMatch = 1; |
+ for(iChild=0; iChild<pAnd->nChild; iChild++){ |
+ Fts5ExprNode *pChild = pAnd->apChild[iChild]; |
+ if( 0 && pChild->eType==FTS5_STRING ){ |
+ /* TODO */ |
+ }else{ |
+ int cmp = fts5RowidCmp(pExpr, iLast, pChild->iRowid); |
+ if( cmp>0 ){ |
+ /* Advance pChild until it points to iLast or laster */ |
+ rc = fts5ExprNodeNext(pExpr, pChild, 1, iLast); |
+ if( rc!=SQLITE_OK ) return rc; |
+ } |
+ } |
+ |
+ /* If the child node is now at EOF, so is the parent AND node. Otherwise, |
+ ** the child node is guaranteed to have advanced at least as far as |
+ ** rowid iLast. So if it is not at exactly iLast, pChild->iRowid is the |
+ ** new lastest rowid seen so far. */ |
+ assert( pChild->bEof || fts5RowidCmp(pExpr, iLast, pChild->iRowid)<=0 ); |
+ if( pChild->bEof ){ |
+ fts5ExprSetEof(pAnd); |
+ bMatch = 1; |
+ break; |
+ }else if( iLast!=pChild->iRowid ){ |
+ bMatch = 0; |
+ iLast = pChild->iRowid; |
+ } |
+ |
+ if( pChild->bNomatch ){ |
+ pAnd->bNomatch = 1; |
+ } |
+ } |
+ }while( bMatch==0 ); |
+ |
+ if( pAnd->bNomatch && pAnd!=pExpr->pRoot ){ |
+ fts5ExprNodeZeroPoslist(pAnd); |
+ } |
+ pAnd->iRowid = iLast; |
+ return SQLITE_OK; |
+} |
+ |
+ |
+/* |
+** Compare the values currently indicated by the two nodes as follows: |
+** |
+** res = (*p1) - (*p2) |
+** |
+** Nodes that point to values that come later in the iteration order are |
+** considered to be larger. Nodes at EOF are the largest of all. |
+** |
+** This means that if the iteration order is ASC, then numerically larger |
+** rowids are considered larger. Or if it is the default DESC, numerically |
+** smaller rowids are larger. |
+*/ |
+static int fts5NodeCompare( |
+ Fts5Expr *pExpr, |
+ Fts5ExprNode *p1, |
+ Fts5ExprNode *p2 |
+){ |
+ if( p2->bEof ) return -1; |
+ if( p1->bEof ) return +1; |
+ return fts5RowidCmp(pExpr, p1->iRowid, p2->iRowid); |
+} |
+ |
+/* |
+** Advance node iterator pNode, part of expression pExpr. If argument |
+** bFromValid is zero, then pNode is advanced exactly once. Or, if argument |
+** bFromValid is non-zero, then pNode is advanced until it is at or past |
+** rowid value iFrom. Whether "past" means "less than" or "greater than" |
+** depends on whether this is an ASC or DESC iterator. |
+*/ |
+static int fts5ExprNodeNext( |
+ Fts5Expr *pExpr, |
+ Fts5ExprNode *pNode, |
+ int bFromValid, |
+ i64 iFrom |
+){ |
+ int rc = SQLITE_OK; |
+ |
+ if( pNode->bEof==0 ){ |
+ switch( pNode->eType ){ |
+ case FTS5_STRING: { |
+ rc = fts5ExprNearAdvanceFirst(pExpr, pNode, bFromValid, iFrom); |
+ break; |
+ }; |
+ |
+ case FTS5_TERM: { |
+ Fts5IndexIter *pIter = pNode->pNear->apPhrase[0]->aTerm[0].pIter; |
+ if( bFromValid ){ |
+ rc = sqlite3Fts5IterNextFrom(pIter, iFrom); |
+ }else{ |
+ rc = sqlite3Fts5IterNext(pIter); |
+ } |
+ if( rc==SQLITE_OK && sqlite3Fts5IterEof(pIter)==0 ){ |
+ assert( rc==SQLITE_OK ); |
+ rc = fts5ExprTokenTest(pExpr, pNode); |
+ }else{ |
+ pNode->bEof = 1; |
+ } |
+ return rc; |
+ }; |
+ |
+ case FTS5_AND: { |
+ Fts5ExprNode *pLeft = pNode->apChild[0]; |
+ rc = fts5ExprNodeNext(pExpr, pLeft, bFromValid, iFrom); |
+ break; |
+ } |
+ |
+ case FTS5_OR: { |
+ int i; |
+ i64 iLast = pNode->iRowid; |
+ |
+ for(i=0; rc==SQLITE_OK && i<pNode->nChild; i++){ |
+ Fts5ExprNode *p1 = pNode->apChild[i]; |
+ assert( p1->bEof || fts5RowidCmp(pExpr, p1->iRowid, iLast)>=0 ); |
+ if( p1->bEof==0 ){ |
+ if( (p1->iRowid==iLast) |
+ || (bFromValid && fts5RowidCmp(pExpr, p1->iRowid, iFrom)<0) |
+ ){ |
+ rc = fts5ExprNodeNext(pExpr, p1, bFromValid, iFrom); |
+ } |
+ } |
+ } |
+ |
+ break; |
+ } |
+ |
+ default: assert( pNode->eType==FTS5_NOT ); { |
+ assert( pNode->nChild==2 ); |
+ rc = fts5ExprNodeNext(pExpr, pNode->apChild[0], bFromValid, iFrom); |
+ break; |
+ } |
+ } |
+ |
+ if( rc==SQLITE_OK ){ |
+ rc = fts5ExprNodeNextMatch(pExpr, pNode); |
+ } |
+ } |
+ |
+ /* Assert that if bFromValid was true, either: |
+ ** |
+ ** a) an error occurred, or |
+ ** b) the node is now at EOF, or |
+ ** c) the node is now at or past rowid iFrom. |
+ */ |
+ assert( bFromValid==0 |
+ || rc!=SQLITE_OK /* a */ |
+ || pNode->bEof /* b */ |
+ || pNode->iRowid==iFrom || pExpr->bDesc==(pNode->iRowid<iFrom) /* c */ |
+ ); |
+ |
+ return rc; |
+} |
+ |
+ |
+/* |
+** If pNode currently points to a match, this function returns SQLITE_OK |
+** without modifying it. Otherwise, pNode is advanced until it does point |
+** to a match or EOF is reached. |
+*/ |
+static int fts5ExprNodeNextMatch( |
+ Fts5Expr *pExpr, /* Expression of which pNode is a part */ |
+ Fts5ExprNode *pNode /* Expression node to test */ |
+){ |
+ int rc = SQLITE_OK; |
+ if( pNode->bEof==0 ){ |
+ switch( pNode->eType ){ |
+ |
+ case FTS5_STRING: { |
+ /* Advance the iterators until they all point to the same rowid */ |
+ rc = fts5ExprNearNextMatch(pExpr, pNode); |
+ break; |
+ } |
+ |
+ case FTS5_TERM: { |
+ rc = fts5ExprTokenTest(pExpr, pNode); |
+ break; |
+ } |
+ |
+ case FTS5_AND: { |
+ rc = fts5ExprAndNextRowid(pExpr, pNode); |
+ break; |
+ } |
+ |
+ case FTS5_OR: { |
+ Fts5ExprNode *pNext = pNode->apChild[0]; |
+ int i; |
+ |
+ for(i=1; i<pNode->nChild; i++){ |
+ Fts5ExprNode *pChild = pNode->apChild[i]; |
+ int cmp = fts5NodeCompare(pExpr, pNext, pChild); |
+ if( cmp>0 || (cmp==0 && pChild->bNomatch==0) ){ |
+ pNext = pChild; |
+ } |
+ } |
+ pNode->iRowid = pNext->iRowid; |
+ pNode->bEof = pNext->bEof; |
+ pNode->bNomatch = pNext->bNomatch; |
+ break; |
+ } |
+ |
+ default: assert( pNode->eType==FTS5_NOT ); { |
+ Fts5ExprNode *p1 = pNode->apChild[0]; |
+ Fts5ExprNode *p2 = pNode->apChild[1]; |
+ assert( pNode->nChild==2 ); |
+ |
+ while( rc==SQLITE_OK && p1->bEof==0 ){ |
+ int cmp = fts5NodeCompare(pExpr, p1, p2); |
+ if( cmp>0 ){ |
+ rc = fts5ExprNodeNext(pExpr, p2, 1, p1->iRowid); |
+ cmp = fts5NodeCompare(pExpr, p1, p2); |
+ } |
+ assert( rc!=SQLITE_OK || cmp<=0 ); |
+ if( cmp || p2->bNomatch ) break; |
+ rc = fts5ExprNodeNext(pExpr, p1, 0, 0); |
+ } |
+ pNode->bEof = p1->bEof; |
+ pNode->iRowid = p1->iRowid; |
+ break; |
+ } |
+ } |
+ } |
+ return rc; |
+} |
+ |
+ |
+/* |
+** Set node pNode, which is part of expression pExpr, to point to the first |
+** match. If there are no matches, set the Node.bEof flag to indicate EOF. |
+** |
+** Return an SQLite error code if an error occurs, or SQLITE_OK otherwise. |
+** It is not an error if there are no matches. |
+*/ |
+static int fts5ExprNodeFirst(Fts5Expr *pExpr, Fts5ExprNode *pNode){ |
+ int rc = SQLITE_OK; |
+ pNode->bEof = 0; |
+ |
+ if( Fts5NodeIsString(pNode) ){ |
+ /* Initialize all term iterators in the NEAR object. */ |
+ rc = fts5ExprNearInitAll(pExpr, pNode); |
+ }else{ |
+ int i; |
+ for(i=0; i<pNode->nChild && rc==SQLITE_OK; i++){ |
+ rc = fts5ExprNodeFirst(pExpr, pNode->apChild[i]); |
+ } |
+ pNode->iRowid = pNode->apChild[0]->iRowid; |
+ } |
+ |
+ if( rc==SQLITE_OK ){ |
+ rc = fts5ExprNodeNextMatch(pExpr, pNode); |
+ } |
+ return rc; |
+} |
+ |
+ |
+/* |
+** Begin iterating through the set of documents in index pIdx matched by |
+** the MATCH expression passed as the first argument. If the "bDesc" |
+** parameter is passed a non-zero value, iteration is in descending rowid |
+** order. Or, if it is zero, in ascending order. |
+** |
+** If iterating in ascending rowid order (bDesc==0), the first document |
+** visited is that with the smallest rowid that is larger than or equal |
+** to parameter iFirst. Or, if iterating in ascending order (bDesc==1), |
+** then the first document visited must have a rowid smaller than or |
+** equal to iFirst. |
+** |
+** Return SQLITE_OK if successful, or an SQLite error code otherwise. It |
+** is not considered an error if the query does not match any documents. |
+*/ |
+int sqlite3Fts5ExprFirst(Fts5Expr *p, Fts5Index *pIdx, i64 iFirst, int bDesc){ |
+ Fts5ExprNode *pRoot = p->pRoot; |
+ int rc = SQLITE_OK; |
+ if( pRoot ){ |
+ p->pIndex = pIdx; |
+ p->bDesc = bDesc; |
+ rc = fts5ExprNodeFirst(p, pRoot); |
+ |
+ /* If not at EOF but the current rowid occurs earlier than iFirst in |
+ ** the iteration order, move to document iFirst or later. */ |
+ if( pRoot->bEof==0 && fts5RowidCmp(p, pRoot->iRowid, iFirst)<0 ){ |
+ rc = fts5ExprNodeNext(p, pRoot, 1, iFirst); |
+ } |
+ |
+ /* If the iterator is not at a real match, skip forward until it is. */ |
+ while( pRoot->bNomatch && rc==SQLITE_OK && pRoot->bEof==0 ){ |
+ rc = fts5ExprNodeNext(p, pRoot, 0, 0); |
+ } |
+ } |
+ return rc; |
+} |
+ |
+/* |
+** Move to the next document |
+** |
+** Return SQLITE_OK if successful, or an SQLite error code otherwise. It |
+** is not considered an error if the query does not match any documents. |
+*/ |
+int sqlite3Fts5ExprNext(Fts5Expr *p, i64 iLast){ |
+ int rc; |
+ Fts5ExprNode *pRoot = p->pRoot; |
+ do { |
+ rc = fts5ExprNodeNext(p, pRoot, 0, 0); |
+ }while( pRoot->bNomatch && pRoot->bEof==0 && rc==SQLITE_OK ); |
+ if( fts5RowidCmp(p, pRoot->iRowid, iLast)>0 ){ |
+ pRoot->bEof = 1; |
+ } |
+ return rc; |
+} |
+ |
+int sqlite3Fts5ExprEof(Fts5Expr *p){ |
+ return (p->pRoot==0 || p->pRoot->bEof); |
+} |
+ |
+i64 sqlite3Fts5ExprRowid(Fts5Expr *p){ |
+ return p->pRoot->iRowid; |
+} |
+ |
+static int fts5ParseStringFromToken(Fts5Token *pToken, char **pz){ |
+ int rc = SQLITE_OK; |
+ *pz = sqlite3Fts5Strndup(&rc, pToken->p, pToken->n); |
+ return rc; |
+} |
+ |
+/* |
+** Free the phrase object passed as the only argument. |
+*/ |
+static void fts5ExprPhraseFree(Fts5ExprPhrase *pPhrase){ |
+ if( pPhrase ){ |
+ int i; |
+ for(i=0; i<pPhrase->nTerm; i++){ |
+ Fts5ExprTerm *pSyn; |
+ Fts5ExprTerm *pNext; |
+ Fts5ExprTerm *pTerm = &pPhrase->aTerm[i]; |
+ sqlite3_free(pTerm->zTerm); |
+ sqlite3Fts5IterClose(pTerm->pIter); |
+ |
+ for(pSyn=pTerm->pSynonym; pSyn; pSyn=pNext){ |
+ pNext = pSyn->pSynonym; |
+ sqlite3Fts5IterClose(pSyn->pIter); |
+ sqlite3_free(pSyn); |
+ } |
+ } |
+ if( pPhrase->poslist.nSpace>0 ) fts5BufferFree(&pPhrase->poslist); |
+ sqlite3_free(pPhrase); |
+ } |
+} |
+ |
+/* |
+** If argument pNear is NULL, then a new Fts5ExprNearset object is allocated |
+** and populated with pPhrase. Or, if pNear is not NULL, phrase pPhrase is |
+** appended to it and the results returned. |
+** |
+** If an OOM error occurs, both the pNear and pPhrase objects are freed and |
+** NULL returned. |
+*/ |
+Fts5ExprNearset *sqlite3Fts5ParseNearset( |
+ Fts5Parse *pParse, /* Parse context */ |
+ Fts5ExprNearset *pNear, /* Existing nearset, or NULL */ |
+ Fts5ExprPhrase *pPhrase /* Recently parsed phrase */ |
+){ |
+ const int SZALLOC = 8; |
+ Fts5ExprNearset *pRet = 0; |
+ |
+ if( pParse->rc==SQLITE_OK ){ |
+ if( pPhrase==0 ){ |
+ return pNear; |
+ } |
+ if( pNear==0 ){ |
+ int nByte = sizeof(Fts5ExprNearset) + SZALLOC * sizeof(Fts5ExprPhrase*); |
+ pRet = sqlite3_malloc(nByte); |
+ if( pRet==0 ){ |
+ pParse->rc = SQLITE_NOMEM; |
+ }else{ |
+ memset(pRet, 0, nByte); |
+ } |
+ }else if( (pNear->nPhrase % SZALLOC)==0 ){ |
+ int nNew = pNear->nPhrase + SZALLOC; |
+ int nByte = sizeof(Fts5ExprNearset) + nNew * sizeof(Fts5ExprPhrase*); |
+ |
+ pRet = (Fts5ExprNearset*)sqlite3_realloc(pNear, nByte); |
+ if( pRet==0 ){ |
+ pParse->rc = SQLITE_NOMEM; |
+ } |
+ }else{ |
+ pRet = pNear; |
+ } |
+ } |
+ |
+ if( pRet==0 ){ |
+ assert( pParse->rc!=SQLITE_OK ); |
+ sqlite3Fts5ParseNearsetFree(pNear); |
+ sqlite3Fts5ParsePhraseFree(pPhrase); |
+ }else{ |
+ pRet->apPhrase[pRet->nPhrase++] = pPhrase; |
+ } |
+ return pRet; |
+} |
+ |
+typedef struct TokenCtx TokenCtx; |
+struct TokenCtx { |
+ Fts5ExprPhrase *pPhrase; |
+ int rc; |
+}; |
+ |
+/* |
+** Callback for tokenizing terms used by ParseTerm(). |
+*/ |
+static int fts5ParseTokenize( |
+ void *pContext, /* Pointer to Fts5InsertCtx object */ |
+ int tflags, /* Mask of FTS5_TOKEN_* flags */ |
+ const char *pToken, /* Buffer containing token */ |
+ int nToken, /* Size of token in bytes */ |
+ int iUnused1, /* Start offset of token */ |
+ int iUnused2 /* End offset of token */ |
+){ |
+ int rc = SQLITE_OK; |
+ const int SZALLOC = 8; |
+ TokenCtx *pCtx = (TokenCtx*)pContext; |
+ Fts5ExprPhrase *pPhrase = pCtx->pPhrase; |
+ |
+ /* If an error has already occurred, this is a no-op */ |
+ if( pCtx->rc!=SQLITE_OK ) return pCtx->rc; |
+ |
+ assert( pPhrase==0 || pPhrase->nTerm>0 ); |
+ if( pPhrase && (tflags & FTS5_TOKEN_COLOCATED) ){ |
+ Fts5ExprTerm *pSyn; |
+ int nByte = sizeof(Fts5ExprTerm) + nToken+1; |
+ pSyn = (Fts5ExprTerm*)sqlite3_malloc(nByte); |
+ if( pSyn==0 ){ |
+ rc = SQLITE_NOMEM; |
+ }else{ |
+ memset(pSyn, 0, nByte); |
+ pSyn->zTerm = (char*)&pSyn[1]; |
+ memcpy(pSyn->zTerm, pToken, nToken); |
+ pSyn->pSynonym = pPhrase->aTerm[pPhrase->nTerm-1].pSynonym; |
+ pPhrase->aTerm[pPhrase->nTerm-1].pSynonym = pSyn; |
+ } |
+ }else{ |
+ Fts5ExprTerm *pTerm; |
+ if( pPhrase==0 || (pPhrase->nTerm % SZALLOC)==0 ){ |
+ Fts5ExprPhrase *pNew; |
+ int nNew = SZALLOC + (pPhrase ? pPhrase->nTerm : 0); |
+ |
+ pNew = (Fts5ExprPhrase*)sqlite3_realloc(pPhrase, |
+ sizeof(Fts5ExprPhrase) + sizeof(Fts5ExprTerm) * nNew |
+ ); |
+ if( pNew==0 ){ |
+ rc = SQLITE_NOMEM; |
+ }else{ |
+ if( pPhrase==0 ) memset(pNew, 0, sizeof(Fts5ExprPhrase)); |
+ pCtx->pPhrase = pPhrase = pNew; |
+ pNew->nTerm = nNew - SZALLOC; |
+ } |
+ } |
+ |
+ if( rc==SQLITE_OK ){ |
+ pTerm = &pPhrase->aTerm[pPhrase->nTerm++]; |
+ memset(pTerm, 0, sizeof(Fts5ExprTerm)); |
+ pTerm->zTerm = sqlite3Fts5Strndup(&rc, pToken, nToken); |
+ } |
+ } |
+ |
+ pCtx->rc = rc; |
+ return rc; |
+} |
+ |
+ |
+/* |
+** Free the phrase object passed as the only argument. |
+*/ |
+void sqlite3Fts5ParsePhraseFree(Fts5ExprPhrase *pPhrase){ |
+ fts5ExprPhraseFree(pPhrase); |
+} |
+ |
+/* |
+** Free the phrase object passed as the second argument. |
+*/ |
+void sqlite3Fts5ParseNearsetFree(Fts5ExprNearset *pNear){ |
+ if( pNear ){ |
+ int i; |
+ for(i=0; i<pNear->nPhrase; i++){ |
+ fts5ExprPhraseFree(pNear->apPhrase[i]); |
+ } |
+ sqlite3_free(pNear->pColset); |
+ sqlite3_free(pNear); |
+ } |
+} |
+ |
+void sqlite3Fts5ParseFinished(Fts5Parse *pParse, Fts5ExprNode *p){ |
+ assert( pParse->pExpr==0 ); |
+ pParse->pExpr = p; |
+} |
+ |
+/* |
+** This function is called by the parser to process a string token. The |
+** string may or may not be quoted. In any case it is tokenized and a |
+** phrase object consisting of all tokens returned. |
+*/ |
+Fts5ExprPhrase *sqlite3Fts5ParseTerm( |
+ Fts5Parse *pParse, /* Parse context */ |
+ Fts5ExprPhrase *pAppend, /* Phrase to append to */ |
+ Fts5Token *pToken, /* String to tokenize */ |
+ int bPrefix /* True if there is a trailing "*" */ |
+){ |
+ Fts5Config *pConfig = pParse->pConfig; |
+ TokenCtx sCtx; /* Context object passed to callback */ |
+ int rc; /* Tokenize return code */ |
+ char *z = 0; |
+ |
+ memset(&sCtx, 0, sizeof(TokenCtx)); |
+ sCtx.pPhrase = pAppend; |
+ |
+ rc = fts5ParseStringFromToken(pToken, &z); |
+ if( rc==SQLITE_OK ){ |
+ int flags = FTS5_TOKENIZE_QUERY | (bPrefix ? FTS5_TOKENIZE_QUERY : 0); |
+ int n; |
+ sqlite3Fts5Dequote(z); |
+ n = (int)strlen(z); |
+ rc = sqlite3Fts5Tokenize(pConfig, flags, z, n, &sCtx, fts5ParseTokenize); |
+ } |
+ sqlite3_free(z); |
+ if( rc || (rc = sCtx.rc) ){ |
+ pParse->rc = rc; |
+ fts5ExprPhraseFree(sCtx.pPhrase); |
+ sCtx.pPhrase = 0; |
+ }else if( sCtx.pPhrase ){ |
+ |
+ if( pAppend==0 ){ |
+ if( (pParse->nPhrase % 8)==0 ){ |
+ int nByte = sizeof(Fts5ExprPhrase*) * (pParse->nPhrase + 8); |
+ Fts5ExprPhrase **apNew; |
+ apNew = (Fts5ExprPhrase**)sqlite3_realloc(pParse->apPhrase, nByte); |
+ if( apNew==0 ){ |
+ pParse->rc = SQLITE_NOMEM; |
+ fts5ExprPhraseFree(sCtx.pPhrase); |
+ return 0; |
+ } |
+ pParse->apPhrase = apNew; |
+ } |
+ pParse->nPhrase++; |
+ } |
+ |
+ pParse->apPhrase[pParse->nPhrase-1] = sCtx.pPhrase; |
+ assert( sCtx.pPhrase->nTerm>0 ); |
+ sCtx.pPhrase->aTerm[sCtx.pPhrase->nTerm-1].bPrefix = bPrefix; |
+ } |
+ |
+ return sCtx.pPhrase; |
+} |
+ |
+/* |
+** Create a new FTS5 expression by cloning phrase iPhrase of the |
+** expression passed as the second argument. |
+*/ |
+int sqlite3Fts5ExprClonePhrase( |
+ Fts5Config *pConfig, |
+ Fts5Expr *pExpr, |
+ int iPhrase, |
+ Fts5Expr **ppNew |
+){ |
+ int rc = SQLITE_OK; /* Return code */ |
+ Fts5ExprPhrase *pOrig; /* The phrase extracted from pExpr */ |
+ int i; /* Used to iterate through phrase terms */ |
+ |
+ Fts5Expr *pNew = 0; /* Expression to return via *ppNew */ |
+ |
+ TokenCtx sCtx = {0,0}; /* Context object for fts5ParseTokenize */ |
+ |
+ |
+ pOrig = pExpr->apExprPhrase[iPhrase]; |
+ |
+ pNew = (Fts5Expr*)sqlite3Fts5MallocZero(&rc, sizeof(Fts5Expr)); |
+ if( rc==SQLITE_OK ){ |
+ pNew->apExprPhrase = (Fts5ExprPhrase**)sqlite3Fts5MallocZero(&rc, |
+ sizeof(Fts5ExprPhrase*)); |
+ } |
+ if( rc==SQLITE_OK ){ |
+ pNew->pRoot = (Fts5ExprNode*)sqlite3Fts5MallocZero(&rc, |
+ sizeof(Fts5ExprNode)); |
+ } |
+ if( rc==SQLITE_OK ){ |
+ pNew->pRoot->pNear = (Fts5ExprNearset*)sqlite3Fts5MallocZero(&rc, |
+ sizeof(Fts5ExprNearset) + sizeof(Fts5ExprPhrase*)); |
+ } |
+ |
+ for(i=0; rc==SQLITE_OK && i<pOrig->nTerm; i++){ |
+ int tflags = 0; |
+ Fts5ExprTerm *p; |
+ for(p=&pOrig->aTerm[i]; p && rc==SQLITE_OK; p=p->pSynonym){ |
+ const char *zTerm = p->zTerm; |
+ rc = fts5ParseTokenize((void*)&sCtx, tflags, zTerm, (int)strlen(zTerm), |
+ 0, 0); |
+ tflags = FTS5_TOKEN_COLOCATED; |
+ } |
+ if( rc==SQLITE_OK ){ |
+ sCtx.pPhrase->aTerm[i].bPrefix = pOrig->aTerm[i].bPrefix; |
+ } |
+ } |
+ |
+ if( rc==SQLITE_OK ){ |
+ /* All the allocations succeeded. Put the expression object together. */ |
+ pNew->pIndex = pExpr->pIndex; |
+ pNew->nPhrase = 1; |
+ pNew->apExprPhrase[0] = sCtx.pPhrase; |
+ pNew->pRoot->pNear->apPhrase[0] = sCtx.pPhrase; |
+ pNew->pRoot->pNear->nPhrase = 1; |
+ sCtx.pPhrase->pNode = pNew->pRoot; |
+ |
+ if( pOrig->nTerm==1 && pOrig->aTerm[0].pSynonym==0 ){ |
+ pNew->pRoot->eType = FTS5_TERM; |
+ }else{ |
+ pNew->pRoot->eType = FTS5_STRING; |
+ } |
+ }else{ |
+ sqlite3Fts5ExprFree(pNew); |
+ fts5ExprPhraseFree(sCtx.pPhrase); |
+ pNew = 0; |
+ } |
+ |
+ *ppNew = pNew; |
+ return rc; |
+} |
+ |
+ |
+/* |
+** Token pTok has appeared in a MATCH expression where the NEAR operator |
+** is expected. If token pTok does not contain "NEAR", store an error |
+** in the pParse object. |
+*/ |
+void sqlite3Fts5ParseNear(Fts5Parse *pParse, Fts5Token *pTok){ |
+ if( pTok->n!=4 || memcmp("NEAR", pTok->p, 4) ){ |
+ sqlite3Fts5ParseError( |
+ pParse, "fts5: syntax error near \"%.*s\"", pTok->n, pTok->p |
+ ); |
+ } |
+} |
+ |
+void sqlite3Fts5ParseSetDistance( |
+ Fts5Parse *pParse, |
+ Fts5ExprNearset *pNear, |
+ Fts5Token *p |
+){ |
+ int nNear = 0; |
+ int i; |
+ if( p->n ){ |
+ for(i=0; i<p->n; i++){ |
+ char c = (char)p->p[i]; |
+ if( c<'0' || c>'9' ){ |
+ sqlite3Fts5ParseError( |
+ pParse, "expected integer, got \"%.*s\"", p->n, p->p |
+ ); |
+ return; |
+ } |
+ nNear = nNear * 10 + (p->p[i] - '0'); |
+ } |
+ }else{ |
+ nNear = FTS5_DEFAULT_NEARDIST; |
+ } |
+ pNear->nNear = nNear; |
+} |
+ |
+/* |
+** The second argument passed to this function may be NULL, or it may be |
+** an existing Fts5Colset object. This function returns a pointer to |
+** a new colset object containing the contents of (p) with new value column |
+** number iCol appended. |
+** |
+** If an OOM error occurs, store an error code in pParse and return NULL. |
+** The old colset object (if any) is not freed in this case. |
+*/ |
+static Fts5Colset *fts5ParseColset( |
+ Fts5Parse *pParse, /* Store SQLITE_NOMEM here if required */ |
+ Fts5Colset *p, /* Existing colset object */ |
+ int iCol /* New column to add to colset object */ |
+){ |
+ int nCol = p ? p->nCol : 0; /* Num. columns already in colset object */ |
+ Fts5Colset *pNew; /* New colset object to return */ |
+ |
+ assert( pParse->rc==SQLITE_OK ); |
+ assert( iCol>=0 && iCol<pParse->pConfig->nCol ); |
+ |
+ pNew = sqlite3_realloc(p, sizeof(Fts5Colset) + sizeof(int)*nCol); |
+ if( pNew==0 ){ |
+ pParse->rc = SQLITE_NOMEM; |
+ }else{ |
+ int *aiCol = pNew->aiCol; |
+ int i, j; |
+ for(i=0; i<nCol; i++){ |
+ if( aiCol[i]==iCol ) return pNew; |
+ if( aiCol[i]>iCol ) break; |
+ } |
+ for(j=nCol; j>i; j--){ |
+ aiCol[j] = aiCol[j-1]; |
+ } |
+ aiCol[i] = iCol; |
+ pNew->nCol = nCol+1; |
+ |
+#ifndef NDEBUG |
+ /* Check that the array is in order and contains no duplicate entries. */ |
+ for(i=1; i<pNew->nCol; i++) assert( pNew->aiCol[i]>pNew->aiCol[i-1] ); |
+#endif |
+ } |
+ |
+ return pNew; |
+} |
+ |
+Fts5Colset *sqlite3Fts5ParseColset( |
+ Fts5Parse *pParse, /* Store SQLITE_NOMEM here if required */ |
+ Fts5Colset *pColset, /* Existing colset object */ |
+ Fts5Token *p |
+){ |
+ Fts5Colset *pRet = 0; |
+ int iCol; |
+ char *z; /* Dequoted copy of token p */ |
+ |
+ z = sqlite3Fts5Strndup(&pParse->rc, p->p, p->n); |
+ if( pParse->rc==SQLITE_OK ){ |
+ Fts5Config *pConfig = pParse->pConfig; |
+ sqlite3Fts5Dequote(z); |
+ for(iCol=0; iCol<pConfig->nCol; iCol++){ |
+ if( 0==sqlite3_stricmp(pConfig->azCol[iCol], z) ) break; |
+ } |
+ if( iCol==pConfig->nCol ){ |
+ sqlite3Fts5ParseError(pParse, "no such column: %s", z); |
+ }else{ |
+ pRet = fts5ParseColset(pParse, pColset, iCol); |
+ } |
+ sqlite3_free(z); |
+ } |
+ |
+ if( pRet==0 ){ |
+ assert( pParse->rc!=SQLITE_OK ); |
+ sqlite3_free(pColset); |
+ } |
+ |
+ return pRet; |
+} |
+ |
+void sqlite3Fts5ParseSetColset( |
+ Fts5Parse *pParse, |
+ Fts5ExprNearset *pNear, |
+ Fts5Colset *pColset |
+){ |
+ if( pNear ){ |
+ pNear->pColset = pColset; |
+ }else{ |
+ sqlite3_free(pColset); |
+ } |
+} |
+ |
+static void fts5ExprAddChildren(Fts5ExprNode *p, Fts5ExprNode *pSub){ |
+ if( p->eType!=FTS5_NOT && pSub->eType==p->eType ){ |
+ int nByte = sizeof(Fts5ExprNode*) * pSub->nChild; |
+ memcpy(&p->apChild[p->nChild], pSub->apChild, nByte); |
+ p->nChild += pSub->nChild; |
+ sqlite3_free(pSub); |
+ }else{ |
+ p->apChild[p->nChild++] = pSub; |
+ } |
+} |
+ |
+/* |
+** Allocate and return a new expression object. If anything goes wrong (i.e. |
+** OOM error), leave an error code in pParse and return NULL. |
+*/ |
+Fts5ExprNode *sqlite3Fts5ParseNode( |
+ Fts5Parse *pParse, /* Parse context */ |
+ int eType, /* FTS5_STRING, AND, OR or NOT */ |
+ Fts5ExprNode *pLeft, /* Left hand child expression */ |
+ Fts5ExprNode *pRight, /* Right hand child expression */ |
+ Fts5ExprNearset *pNear /* For STRING expressions, the near cluster */ |
+){ |
+ Fts5ExprNode *pRet = 0; |
+ |
+ if( pParse->rc==SQLITE_OK ){ |
+ int nChild = 0; /* Number of children of returned node */ |
+ int nByte; /* Bytes of space to allocate for this node */ |
+ |
+ assert( (eType!=FTS5_STRING && !pNear) |
+ || (eType==FTS5_STRING && !pLeft && !pRight) |
+ ); |
+ if( eType==FTS5_STRING && pNear==0 ) return 0; |
+ if( eType!=FTS5_STRING && pLeft==0 ) return pRight; |
+ if( eType!=FTS5_STRING && pRight==0 ) return pLeft; |
+ |
+ if( eType==FTS5_NOT ){ |
+ nChild = 2; |
+ }else if( eType==FTS5_AND || eType==FTS5_OR ){ |
+ nChild = 2; |
+ if( pLeft->eType==eType ) nChild += pLeft->nChild-1; |
+ if( pRight->eType==eType ) nChild += pRight->nChild-1; |
+ } |
+ |
+ nByte = sizeof(Fts5ExprNode) + sizeof(Fts5ExprNode*)*(nChild-1); |
+ pRet = (Fts5ExprNode*)sqlite3Fts5MallocZero(&pParse->rc, nByte); |
+ |
+ if( pRet ){ |
+ pRet->eType = eType; |
+ pRet->pNear = pNear; |
+ if( eType==FTS5_STRING ){ |
+ int iPhrase; |
+ for(iPhrase=0; iPhrase<pNear->nPhrase; iPhrase++){ |
+ pNear->apPhrase[iPhrase]->pNode = pRet; |
+ } |
+ if( pNear->nPhrase==1 |
+ && pNear->apPhrase[0]->nTerm==1 |
+ && pNear->apPhrase[0]->aTerm[0].pSynonym==0 |
+ ){ |
+ pRet->eType = FTS5_TERM; |
+ } |
+ }else{ |
+ fts5ExprAddChildren(pRet, pLeft); |
+ fts5ExprAddChildren(pRet, pRight); |
+ } |
+ } |
+ } |
+ |
+ if( pRet==0 ){ |
+ assert( pParse->rc!=SQLITE_OK ); |
+ sqlite3Fts5ParseNodeFree(pLeft); |
+ sqlite3Fts5ParseNodeFree(pRight); |
+ sqlite3Fts5ParseNearsetFree(pNear); |
+ } |
+ return pRet; |
+} |
+ |
+static char *fts5ExprTermPrint(Fts5ExprTerm *pTerm){ |
+ int nByte = 0; |
+ Fts5ExprTerm *p; |
+ char *zQuoted; |
+ |
+ /* Determine the maximum amount of space required. */ |
+ for(p=pTerm; p; p=p->pSynonym){ |
+ nByte += (int)strlen(pTerm->zTerm) * 2 + 3 + 2; |
+ } |
+ zQuoted = sqlite3_malloc(nByte); |
+ |
+ if( zQuoted ){ |
+ int i = 0; |
+ for(p=pTerm; p; p=p->pSynonym){ |
+ char *zIn = p->zTerm; |
+ zQuoted[i++] = '"'; |
+ while( *zIn ){ |
+ if( *zIn=='"' ) zQuoted[i++] = '"'; |
+ zQuoted[i++] = *zIn++; |
+ } |
+ zQuoted[i++] = '"'; |
+ if( p->pSynonym ) zQuoted[i++] = '|'; |
+ } |
+ if( pTerm->bPrefix ){ |
+ zQuoted[i++] = ' '; |
+ zQuoted[i++] = '*'; |
+ } |
+ zQuoted[i++] = '\0'; |
+ } |
+ return zQuoted; |
+} |
+ |
+static char *fts5PrintfAppend(char *zApp, const char *zFmt, ...){ |
+ char *zNew; |
+ va_list ap; |
+ va_start(ap, zFmt); |
+ zNew = sqlite3_vmprintf(zFmt, ap); |
+ va_end(ap); |
+ if( zApp && zNew ){ |
+ char *zNew2 = sqlite3_mprintf("%s%s", zApp, zNew); |
+ sqlite3_free(zNew); |
+ zNew = zNew2; |
+ } |
+ sqlite3_free(zApp); |
+ return zNew; |
+} |
+ |
+/* |
+** Compose a tcl-readable representation of expression pExpr. Return a |
+** pointer to a buffer containing that representation. It is the |
+** responsibility of the caller to at some point free the buffer using |
+** sqlite3_free(). |
+*/ |
+static char *fts5ExprPrintTcl( |
+ Fts5Config *pConfig, |
+ const char *zNearsetCmd, |
+ Fts5ExprNode *pExpr |
+){ |
+ char *zRet = 0; |
+ if( pExpr->eType==FTS5_STRING || pExpr->eType==FTS5_TERM ){ |
+ Fts5ExprNearset *pNear = pExpr->pNear; |
+ int i; |
+ int iTerm; |
+ |
+ zRet = fts5PrintfAppend(zRet, "%s ", zNearsetCmd); |
+ if( zRet==0 ) return 0; |
+ if( pNear->pColset ){ |
+ int *aiCol = pNear->pColset->aiCol; |
+ int nCol = pNear->pColset->nCol; |
+ if( nCol==1 ){ |
+ zRet = fts5PrintfAppend(zRet, "-col %d ", aiCol[0]); |
+ }else{ |
+ zRet = fts5PrintfAppend(zRet, "-col {%d", aiCol[0]); |
+ for(i=1; i<pNear->pColset->nCol; i++){ |
+ zRet = fts5PrintfAppend(zRet, " %d", aiCol[i]); |
+ } |
+ zRet = fts5PrintfAppend(zRet, "} "); |
+ } |
+ if( zRet==0 ) return 0; |
+ } |
+ |
+ if( pNear->nPhrase>1 ){ |
+ zRet = fts5PrintfAppend(zRet, "-near %d ", pNear->nNear); |
+ if( zRet==0 ) return 0; |
+ } |
+ |
+ zRet = fts5PrintfAppend(zRet, "--"); |
+ if( zRet==0 ) return 0; |
+ |
+ for(i=0; i<pNear->nPhrase; i++){ |
+ Fts5ExprPhrase *pPhrase = pNear->apPhrase[i]; |
+ |
+ zRet = fts5PrintfAppend(zRet, " {"); |
+ for(iTerm=0; zRet && iTerm<pPhrase->nTerm; iTerm++){ |
+ char *zTerm = pPhrase->aTerm[iTerm].zTerm; |
+ zRet = fts5PrintfAppend(zRet, "%s%s", iTerm==0?"":" ", zTerm); |
+ } |
+ |
+ if( zRet ) zRet = fts5PrintfAppend(zRet, "}"); |
+ if( zRet==0 ) return 0; |
+ } |
+ |
+ }else{ |
+ char const *zOp = 0; |
+ int i; |
+ switch( pExpr->eType ){ |
+ case FTS5_AND: zOp = "AND"; break; |
+ case FTS5_NOT: zOp = "NOT"; break; |
+ default: |
+ assert( pExpr->eType==FTS5_OR ); |
+ zOp = "OR"; |
+ break; |
+ } |
+ |
+ zRet = sqlite3_mprintf("%s", zOp); |
+ for(i=0; zRet && i<pExpr->nChild; i++){ |
+ char *z = fts5ExprPrintTcl(pConfig, zNearsetCmd, pExpr->apChild[i]); |
+ if( !z ){ |
+ sqlite3_free(zRet); |
+ zRet = 0; |
+ }else{ |
+ zRet = fts5PrintfAppend(zRet, " [%z]", z); |
+ } |
+ } |
+ } |
+ |
+ return zRet; |
+} |
+ |
+static char *fts5ExprPrint(Fts5Config *pConfig, Fts5ExprNode *pExpr){ |
+ char *zRet = 0; |
+ if( pExpr->eType==FTS5_STRING || pExpr->eType==FTS5_TERM ){ |
+ Fts5ExprNearset *pNear = pExpr->pNear; |
+ int i; |
+ int iTerm; |
+ |
+ if( pNear->pColset ){ |
+ int iCol = pNear->pColset->aiCol[0]; |
+ zRet = fts5PrintfAppend(zRet, "%s : ", pConfig->azCol[iCol]); |
+ if( zRet==0 ) return 0; |
+ } |
+ |
+ if( pNear->nPhrase>1 ){ |
+ zRet = fts5PrintfAppend(zRet, "NEAR("); |
+ if( zRet==0 ) return 0; |
+ } |
+ |
+ for(i=0; i<pNear->nPhrase; i++){ |
+ Fts5ExprPhrase *pPhrase = pNear->apPhrase[i]; |
+ if( i!=0 ){ |
+ zRet = fts5PrintfAppend(zRet, " "); |
+ if( zRet==0 ) return 0; |
+ } |
+ for(iTerm=0; iTerm<pPhrase->nTerm; iTerm++){ |
+ char *zTerm = fts5ExprTermPrint(&pPhrase->aTerm[iTerm]); |
+ if( zTerm ){ |
+ zRet = fts5PrintfAppend(zRet, "%s%s", iTerm==0?"":" + ", zTerm); |
+ sqlite3_free(zTerm); |
+ } |
+ if( zTerm==0 || zRet==0 ){ |
+ sqlite3_free(zRet); |
+ return 0; |
+ } |
+ } |
+ } |
+ |
+ if( pNear->nPhrase>1 ){ |
+ zRet = fts5PrintfAppend(zRet, ", %d)", pNear->nNear); |
+ if( zRet==0 ) return 0; |
+ } |
+ |
+ }else{ |
+ char const *zOp = 0; |
+ int i; |
+ |
+ switch( pExpr->eType ){ |
+ case FTS5_AND: zOp = " AND "; break; |
+ case FTS5_NOT: zOp = " NOT "; break; |
+ default: |
+ assert( pExpr->eType==FTS5_OR ); |
+ zOp = " OR "; |
+ break; |
+ } |
+ |
+ for(i=0; i<pExpr->nChild; i++){ |
+ char *z = fts5ExprPrint(pConfig, pExpr->apChild[i]); |
+ if( z==0 ){ |
+ sqlite3_free(zRet); |
+ zRet = 0; |
+ }else{ |
+ int e = pExpr->apChild[i]->eType; |
+ int b = (e!=FTS5_STRING && e!=FTS5_TERM); |
+ zRet = fts5PrintfAppend(zRet, "%s%s%z%s", |
+ (i==0 ? "" : zOp), |
+ (b?"(":""), z, (b?")":"") |
+ ); |
+ } |
+ if( zRet==0 ) break; |
+ } |
+ } |
+ |
+ return zRet; |
+} |
+ |
+/* |
+** The implementation of user-defined scalar functions fts5_expr() (bTcl==0) |
+** and fts5_expr_tcl() (bTcl!=0). |
+*/ |
+static void fts5ExprFunction( |
+ sqlite3_context *pCtx, /* Function call context */ |
+ int nArg, /* Number of args */ |
+ sqlite3_value **apVal, /* Function arguments */ |
+ int bTcl |
+){ |
+ Fts5Global *pGlobal = (Fts5Global*)sqlite3_user_data(pCtx); |
+ sqlite3 *db = sqlite3_context_db_handle(pCtx); |
+ const char *zExpr = 0; |
+ char *zErr = 0; |
+ Fts5Expr *pExpr = 0; |
+ int rc; |
+ int i; |
+ |
+ const char **azConfig; /* Array of arguments for Fts5Config */ |
+ const char *zNearsetCmd = "nearset"; |
+ int nConfig; /* Size of azConfig[] */ |
+ Fts5Config *pConfig = 0; |
+ int iArg = 1; |
+ |
+ if( nArg<1 ){ |
+ zErr = sqlite3_mprintf("wrong number of arguments to function %s", |
+ bTcl ? "fts5_expr_tcl" : "fts5_expr" |
+ ); |
+ sqlite3_result_error(pCtx, zErr, -1); |
+ sqlite3_free(zErr); |
+ return; |
+ } |
+ |
+ if( bTcl && nArg>1 ){ |
+ zNearsetCmd = (const char*)sqlite3_value_text(apVal[1]); |
+ iArg = 2; |
+ } |
+ |
+ nConfig = 3 + (nArg-iArg); |
+ azConfig = (const char**)sqlite3_malloc(sizeof(char*) * nConfig); |
+ if( azConfig==0 ){ |
+ sqlite3_result_error_nomem(pCtx); |
+ return; |
+ } |
+ azConfig[0] = 0; |
+ azConfig[1] = "main"; |
+ azConfig[2] = "tbl"; |
+ for(i=3; iArg<nArg; iArg++){ |
+ azConfig[i++] = (const char*)sqlite3_value_text(apVal[iArg]); |
+ } |
+ |
+ zExpr = (const char*)sqlite3_value_text(apVal[0]); |
+ |
+ rc = sqlite3Fts5ConfigParse(pGlobal, db, nConfig, azConfig, &pConfig, &zErr); |
+ if( rc==SQLITE_OK ){ |
+ rc = sqlite3Fts5ExprNew(pConfig, zExpr, &pExpr, &zErr); |
+ } |
+ if( rc==SQLITE_OK ){ |
+ char *zText; |
+ if( pExpr->pRoot==0 ){ |
+ zText = sqlite3_mprintf(""); |
+ }else if( bTcl ){ |
+ zText = fts5ExprPrintTcl(pConfig, zNearsetCmd, pExpr->pRoot); |
+ }else{ |
+ zText = fts5ExprPrint(pConfig, pExpr->pRoot); |
+ } |
+ if( zText==0 ){ |
+ rc = SQLITE_NOMEM; |
+ }else{ |
+ sqlite3_result_text(pCtx, zText, -1, SQLITE_TRANSIENT); |
+ sqlite3_free(zText); |
+ } |
+ } |
+ |
+ if( rc!=SQLITE_OK ){ |
+ if( zErr ){ |
+ sqlite3_result_error(pCtx, zErr, -1); |
+ sqlite3_free(zErr); |
+ }else{ |
+ sqlite3_result_error_code(pCtx, rc); |
+ } |
+ } |
+ sqlite3_free((void *)azConfig); |
+ sqlite3Fts5ConfigFree(pConfig); |
+ sqlite3Fts5ExprFree(pExpr); |
+} |
+ |
+static void fts5ExprFunctionHr( |
+ sqlite3_context *pCtx, /* Function call context */ |
+ int nArg, /* Number of args */ |
+ sqlite3_value **apVal /* Function arguments */ |
+){ |
+ fts5ExprFunction(pCtx, nArg, apVal, 0); |
+} |
+static void fts5ExprFunctionTcl( |
+ sqlite3_context *pCtx, /* Function call context */ |
+ int nArg, /* Number of args */ |
+ sqlite3_value **apVal /* Function arguments */ |
+){ |
+ fts5ExprFunction(pCtx, nArg, apVal, 1); |
+} |
+ |
+/* |
+** The implementation of an SQLite user-defined-function that accepts a |
+** single integer as an argument. If the integer is an alpha-numeric |
+** unicode code point, 1 is returned. Otherwise 0. |
+*/ |
+static void fts5ExprIsAlnum( |
+ sqlite3_context *pCtx, /* Function call context */ |
+ int nArg, /* Number of args */ |
+ sqlite3_value **apVal /* Function arguments */ |
+){ |
+ int iCode; |
+ if( nArg!=1 ){ |
+ sqlite3_result_error(pCtx, |
+ "wrong number of arguments to function fts5_isalnum", -1 |
+ ); |
+ return; |
+ } |
+ iCode = sqlite3_value_int(apVal[0]); |
+ sqlite3_result_int(pCtx, sqlite3Fts5UnicodeIsalnum(iCode)); |
+} |
+ |
+static void fts5ExprFold( |
+ sqlite3_context *pCtx, /* Function call context */ |
+ int nArg, /* Number of args */ |
+ sqlite3_value **apVal /* Function arguments */ |
+){ |
+ if( nArg!=1 && nArg!=2 ){ |
+ sqlite3_result_error(pCtx, |
+ "wrong number of arguments to function fts5_fold", -1 |
+ ); |
+ }else{ |
+ int iCode; |
+ int bRemoveDiacritics = 0; |
+ iCode = sqlite3_value_int(apVal[0]); |
+ if( nArg==2 ) bRemoveDiacritics = sqlite3_value_int(apVal[1]); |
+ sqlite3_result_int(pCtx, sqlite3Fts5UnicodeFold(iCode, bRemoveDiacritics)); |
+ } |
+} |
+ |
+/* |
+** This is called during initialization to register the fts5_expr() scalar |
+** UDF with the SQLite handle passed as the only argument. |
+*/ |
+int sqlite3Fts5ExprInit(Fts5Global *pGlobal, sqlite3 *db){ |
+ struct Fts5ExprFunc { |
+ const char *z; |
+ void (*x)(sqlite3_context*,int,sqlite3_value**); |
+ } aFunc[] = { |
+ { "fts5_expr", fts5ExprFunctionHr }, |
+ { "fts5_expr_tcl", fts5ExprFunctionTcl }, |
+ { "fts5_isalnum", fts5ExprIsAlnum }, |
+ { "fts5_fold", fts5ExprFold }, |
+ }; |
+ int i; |
+ int rc = SQLITE_OK; |
+ void *pCtx = (void*)pGlobal; |
+ |
+ for(i=0; rc==SQLITE_OK && i<(int)ArraySize(aFunc); i++){ |
+ struct Fts5ExprFunc *p = &aFunc[i]; |
+ rc = sqlite3_create_function(db, p->z, -1, SQLITE_UTF8, pCtx, p->x, 0, 0); |
+ } |
+ |
+ /* Avoid a warning indicating that sqlite3Fts5ParserTrace() is unused */ |
+#ifndef NDEBUG |
+ (void)sqlite3Fts5ParserTrace; |
+#endif |
+ |
+ return rc; |
+} |
+ |
+/* |
+** Return the number of phrases in expression pExpr. |
+*/ |
+int sqlite3Fts5ExprPhraseCount(Fts5Expr *pExpr){ |
+ return (pExpr ? pExpr->nPhrase : 0); |
+} |
+ |
+/* |
+** Return the number of terms in the iPhrase'th phrase in pExpr. |
+*/ |
+int sqlite3Fts5ExprPhraseSize(Fts5Expr *pExpr, int iPhrase){ |
+ if( iPhrase<0 || iPhrase>=pExpr->nPhrase ) return 0; |
+ return pExpr->apExprPhrase[iPhrase]->nTerm; |
+} |
+ |
+/* |
+** This function is used to access the current position list for phrase |
+** iPhrase. |
+*/ |
+int sqlite3Fts5ExprPoslist(Fts5Expr *pExpr, int iPhrase, const u8 **pa){ |
+ int nRet; |
+ Fts5ExprPhrase *pPhrase = pExpr->apExprPhrase[iPhrase]; |
+ Fts5ExprNode *pNode = pPhrase->pNode; |
+ if( pNode->bEof==0 && pNode->iRowid==pExpr->pRoot->iRowid ){ |
+ *pa = pPhrase->poslist.p; |
+ nRet = pPhrase->poslist.n; |
+ }else{ |
+ *pa = 0; |
+ nRet = 0; |
+ } |
+ return nRet; |
+} |