Annotation of embedaddon/sqlite3/ext/fts3/fts3_snippet.c, revision 1.1
1.1 ! misho 1: /*
! 2: ** 2009 Oct 23
! 3: **
! 4: ** The author disclaims copyright to this source code. In place of
! 5: ** a legal notice, here is a blessing:
! 6: **
! 7: ** May you do good and not evil.
! 8: ** May you find forgiveness for yourself and forgive others.
! 9: ** May you share freely, never taking more than you give.
! 10: **
! 11: ******************************************************************************
! 12: */
! 13:
! 14: #include "fts3Int.h"
! 15: #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)
! 16:
! 17: #include <string.h>
! 18: #include <assert.h>
! 19:
! 20: /*
! 21: ** Characters that may appear in the second argument to matchinfo().
! 22: */
! 23: #define FTS3_MATCHINFO_NPHRASE 'p' /* 1 value */
! 24: #define FTS3_MATCHINFO_NCOL 'c' /* 1 value */
! 25: #define FTS3_MATCHINFO_NDOC 'n' /* 1 value */
! 26: #define FTS3_MATCHINFO_AVGLENGTH 'a' /* nCol values */
! 27: #define FTS3_MATCHINFO_LENGTH 'l' /* nCol values */
! 28: #define FTS3_MATCHINFO_LCS 's' /* nCol values */
! 29: #define FTS3_MATCHINFO_HITS 'x' /* 3*nCol*nPhrase values */
! 30:
! 31: /*
! 32: ** The default value for the second argument to matchinfo().
! 33: */
! 34: #define FTS3_MATCHINFO_DEFAULT "pcx"
! 35:
! 36:
! 37: /*
! 38: ** Used as an fts3ExprIterate() context when loading phrase doclists to
! 39: ** Fts3Expr.aDoclist[]/nDoclist.
! 40: */
! 41: typedef struct LoadDoclistCtx LoadDoclistCtx;
! 42: struct LoadDoclistCtx {
! 43: Fts3Cursor *pCsr; /* FTS3 Cursor */
! 44: int nPhrase; /* Number of phrases seen so far */
! 45: int nToken; /* Number of tokens seen so far */
! 46: };
! 47:
! 48: /*
! 49: ** The following types are used as part of the implementation of the
! 50: ** fts3BestSnippet() routine.
! 51: */
! 52: typedef struct SnippetIter SnippetIter;
! 53: typedef struct SnippetPhrase SnippetPhrase;
! 54: typedef struct SnippetFragment SnippetFragment;
! 55:
! 56: struct SnippetIter {
! 57: Fts3Cursor *pCsr; /* Cursor snippet is being generated from */
! 58: int iCol; /* Extract snippet from this column */
! 59: int nSnippet; /* Requested snippet length (in tokens) */
! 60: int nPhrase; /* Number of phrases in query */
! 61: SnippetPhrase *aPhrase; /* Array of size nPhrase */
! 62: int iCurrent; /* First token of current snippet */
! 63: };
! 64:
! 65: struct SnippetPhrase {
! 66: int nToken; /* Number of tokens in phrase */
! 67: char *pList; /* Pointer to start of phrase position list */
! 68: int iHead; /* Next value in position list */
! 69: char *pHead; /* Position list data following iHead */
! 70: int iTail; /* Next value in trailing position list */
! 71: char *pTail; /* Position list data following iTail */
! 72: };
! 73:
! 74: struct SnippetFragment {
! 75: int iCol; /* Column snippet is extracted from */
! 76: int iPos; /* Index of first token in snippet */
! 77: u64 covered; /* Mask of query phrases covered */
! 78: u64 hlmask; /* Mask of snippet terms to highlight */
! 79: };
! 80:
! 81: /*
! 82: ** This type is used as an fts3ExprIterate() context object while
! 83: ** accumulating the data returned by the matchinfo() function.
! 84: */
! 85: typedef struct MatchInfo MatchInfo;
! 86: struct MatchInfo {
! 87: Fts3Cursor *pCursor; /* FTS3 Cursor */
! 88: int nCol; /* Number of columns in table */
! 89: int nPhrase; /* Number of matchable phrases in query */
! 90: sqlite3_int64 nDoc; /* Number of docs in database */
! 91: u32 *aMatchinfo; /* Pre-allocated buffer */
! 92: };
! 93:
! 94:
! 95:
! 96: /*
! 97: ** The snippet() and offsets() functions both return text values. An instance
! 98: ** of the following structure is used to accumulate those values while the
! 99: ** functions are running. See fts3StringAppend() for details.
! 100: */
! 101: typedef struct StrBuffer StrBuffer;
! 102: struct StrBuffer {
! 103: char *z; /* Pointer to buffer containing string */
! 104: int n; /* Length of z in bytes (excl. nul-term) */
! 105: int nAlloc; /* Allocated size of buffer z in bytes */
! 106: };
! 107:
! 108:
! 109: /*
! 110: ** This function is used to help iterate through a position-list. A position
! 111: ** list is a list of unique integers, sorted from smallest to largest. Each
! 112: ** element of the list is represented by an FTS3 varint that takes the value
! 113: ** of the difference between the current element and the previous one plus
! 114: ** two. For example, to store the position-list:
! 115: **
! 116: ** 4 9 113
! 117: **
! 118: ** the three varints:
! 119: **
! 120: ** 6 7 106
! 121: **
! 122: ** are encoded.
! 123: **
! 124: ** When this function is called, *pp points to the start of an element of
! 125: ** the list. *piPos contains the value of the previous entry in the list.
! 126: ** After it returns, *piPos contains the value of the next element of the
! 127: ** list and *pp is advanced to the following varint.
! 128: */
! 129: static void fts3GetDeltaPosition(char **pp, int *piPos){
! 130: int iVal;
! 131: *pp += sqlite3Fts3GetVarint32(*pp, &iVal);
! 132: *piPos += (iVal-2);
! 133: }
! 134:
! 135: /*
! 136: ** Helper function for fts3ExprIterate() (see below).
! 137: */
! 138: static int fts3ExprIterate2(
! 139: Fts3Expr *pExpr, /* Expression to iterate phrases of */
! 140: int *piPhrase, /* Pointer to phrase counter */
! 141: int (*x)(Fts3Expr*,int,void*), /* Callback function to invoke for phrases */
! 142: void *pCtx /* Second argument to pass to callback */
! 143: ){
! 144: int rc; /* Return code */
! 145: int eType = pExpr->eType; /* Type of expression node pExpr */
! 146:
! 147: if( eType!=FTSQUERY_PHRASE ){
! 148: assert( pExpr->pLeft && pExpr->pRight );
! 149: rc = fts3ExprIterate2(pExpr->pLeft, piPhrase, x, pCtx);
! 150: if( rc==SQLITE_OK && eType!=FTSQUERY_NOT ){
! 151: rc = fts3ExprIterate2(pExpr->pRight, piPhrase, x, pCtx);
! 152: }
! 153: }else{
! 154: rc = x(pExpr, *piPhrase, pCtx);
! 155: (*piPhrase)++;
! 156: }
! 157: return rc;
! 158: }
! 159:
! 160: /*
! 161: ** Iterate through all phrase nodes in an FTS3 query, except those that
! 162: ** are part of a sub-tree that is the right-hand-side of a NOT operator.
! 163: ** For each phrase node found, the supplied callback function is invoked.
! 164: **
! 165: ** If the callback function returns anything other than SQLITE_OK,
! 166: ** the iteration is abandoned and the error code returned immediately.
! 167: ** Otherwise, SQLITE_OK is returned after a callback has been made for
! 168: ** all eligible phrase nodes.
! 169: */
! 170: static int fts3ExprIterate(
! 171: Fts3Expr *pExpr, /* Expression to iterate phrases of */
! 172: int (*x)(Fts3Expr*,int,void*), /* Callback function to invoke for phrases */
! 173: void *pCtx /* Second argument to pass to callback */
! 174: ){
! 175: int iPhrase = 0; /* Variable used as the phrase counter */
! 176: return fts3ExprIterate2(pExpr, &iPhrase, x, pCtx);
! 177: }
! 178:
! 179: /*
! 180: ** This is an fts3ExprIterate() callback used while loading the doclists
! 181: ** for each phrase into Fts3Expr.aDoclist[]/nDoclist. See also
! 182: ** fts3ExprLoadDoclists().
! 183: */
! 184: static int fts3ExprLoadDoclistsCb(Fts3Expr *pExpr, int iPhrase, void *ctx){
! 185: int rc = SQLITE_OK;
! 186: Fts3Phrase *pPhrase = pExpr->pPhrase;
! 187: LoadDoclistCtx *p = (LoadDoclistCtx *)ctx;
! 188:
! 189: UNUSED_PARAMETER(iPhrase);
! 190:
! 191: p->nPhrase++;
! 192: p->nToken += pPhrase->nToken;
! 193:
! 194: return rc;
! 195: }
! 196:
! 197: /*
! 198: ** Load the doclists for each phrase in the query associated with FTS3 cursor
! 199: ** pCsr.
! 200: **
! 201: ** If pnPhrase is not NULL, then *pnPhrase is set to the number of matchable
! 202: ** phrases in the expression (all phrases except those directly or
! 203: ** indirectly descended from the right-hand-side of a NOT operator). If
! 204: ** pnToken is not NULL, then it is set to the number of tokens in all
! 205: ** matchable phrases of the expression.
! 206: */
! 207: static int fts3ExprLoadDoclists(
! 208: Fts3Cursor *pCsr, /* Fts3 cursor for current query */
! 209: int *pnPhrase, /* OUT: Number of phrases in query */
! 210: int *pnToken /* OUT: Number of tokens in query */
! 211: ){
! 212: int rc; /* Return Code */
! 213: LoadDoclistCtx sCtx = {0,0,0}; /* Context for fts3ExprIterate() */
! 214: sCtx.pCsr = pCsr;
! 215: rc = fts3ExprIterate(pCsr->pExpr, fts3ExprLoadDoclistsCb, (void *)&sCtx);
! 216: if( pnPhrase ) *pnPhrase = sCtx.nPhrase;
! 217: if( pnToken ) *pnToken = sCtx.nToken;
! 218: return rc;
! 219: }
! 220:
! 221: static int fts3ExprPhraseCountCb(Fts3Expr *pExpr, int iPhrase, void *ctx){
! 222: (*(int *)ctx)++;
! 223: UNUSED_PARAMETER(pExpr);
! 224: UNUSED_PARAMETER(iPhrase);
! 225: return SQLITE_OK;
! 226: }
! 227: static int fts3ExprPhraseCount(Fts3Expr *pExpr){
! 228: int nPhrase = 0;
! 229: (void)fts3ExprIterate(pExpr, fts3ExprPhraseCountCb, (void *)&nPhrase);
! 230: return nPhrase;
! 231: }
! 232:
! 233: /*
! 234: ** Advance the position list iterator specified by the first two
! 235: ** arguments so that it points to the first element with a value greater
! 236: ** than or equal to parameter iNext.
! 237: */
! 238: static void fts3SnippetAdvance(char **ppIter, int *piIter, int iNext){
! 239: char *pIter = *ppIter;
! 240: if( pIter ){
! 241: int iIter = *piIter;
! 242:
! 243: while( iIter<iNext ){
! 244: if( 0==(*pIter & 0xFE) ){
! 245: iIter = -1;
! 246: pIter = 0;
! 247: break;
! 248: }
! 249: fts3GetDeltaPosition(&pIter, &iIter);
! 250: }
! 251:
! 252: *piIter = iIter;
! 253: *ppIter = pIter;
! 254: }
! 255: }
! 256:
! 257: /*
! 258: ** Advance the snippet iterator to the next candidate snippet.
! 259: */
! 260: static int fts3SnippetNextCandidate(SnippetIter *pIter){
! 261: int i; /* Loop counter */
! 262:
! 263: if( pIter->iCurrent<0 ){
! 264: /* The SnippetIter object has just been initialized. The first snippet
! 265: ** candidate always starts at offset 0 (even if this candidate has a
! 266: ** score of 0.0).
! 267: */
! 268: pIter->iCurrent = 0;
! 269:
! 270: /* Advance the 'head' iterator of each phrase to the first offset that
! 271: ** is greater than or equal to (iNext+nSnippet).
! 272: */
! 273: for(i=0; i<pIter->nPhrase; i++){
! 274: SnippetPhrase *pPhrase = &pIter->aPhrase[i];
! 275: fts3SnippetAdvance(&pPhrase->pHead, &pPhrase->iHead, pIter->nSnippet);
! 276: }
! 277: }else{
! 278: int iStart;
! 279: int iEnd = 0x7FFFFFFF;
! 280:
! 281: for(i=0; i<pIter->nPhrase; i++){
! 282: SnippetPhrase *pPhrase = &pIter->aPhrase[i];
! 283: if( pPhrase->pHead && pPhrase->iHead<iEnd ){
! 284: iEnd = pPhrase->iHead;
! 285: }
! 286: }
! 287: if( iEnd==0x7FFFFFFF ){
! 288: return 1;
! 289: }
! 290:
! 291: pIter->iCurrent = iStart = iEnd - pIter->nSnippet + 1;
! 292: for(i=0; i<pIter->nPhrase; i++){
! 293: SnippetPhrase *pPhrase = &pIter->aPhrase[i];
! 294: fts3SnippetAdvance(&pPhrase->pHead, &pPhrase->iHead, iEnd+1);
! 295: fts3SnippetAdvance(&pPhrase->pTail, &pPhrase->iTail, iStart);
! 296: }
! 297: }
! 298:
! 299: return 0;
! 300: }
! 301:
! 302: /*
! 303: ** Retrieve information about the current candidate snippet of snippet
! 304: ** iterator pIter.
! 305: */
! 306: static void fts3SnippetDetails(
! 307: SnippetIter *pIter, /* Snippet iterator */
! 308: u64 mCovered, /* Bitmask of phrases already covered */
! 309: int *piToken, /* OUT: First token of proposed snippet */
! 310: int *piScore, /* OUT: "Score" for this snippet */
! 311: u64 *pmCover, /* OUT: Bitmask of phrases covered */
! 312: u64 *pmHighlight /* OUT: Bitmask of terms to highlight */
! 313: ){
! 314: int iStart = pIter->iCurrent; /* First token of snippet */
! 315: int iScore = 0; /* Score of this snippet */
! 316: int i; /* Loop counter */
! 317: u64 mCover = 0; /* Mask of phrases covered by this snippet */
! 318: u64 mHighlight = 0; /* Mask of tokens to highlight in snippet */
! 319:
! 320: for(i=0; i<pIter->nPhrase; i++){
! 321: SnippetPhrase *pPhrase = &pIter->aPhrase[i];
! 322: if( pPhrase->pTail ){
! 323: char *pCsr = pPhrase->pTail;
! 324: int iCsr = pPhrase->iTail;
! 325:
! 326: while( iCsr<(iStart+pIter->nSnippet) ){
! 327: int j;
! 328: u64 mPhrase = (u64)1 << i;
! 329: u64 mPos = (u64)1 << (iCsr - iStart);
! 330: assert( iCsr>=iStart );
! 331: if( (mCover|mCovered)&mPhrase ){
! 332: iScore++;
! 333: }else{
! 334: iScore += 1000;
! 335: }
! 336: mCover |= mPhrase;
! 337:
! 338: for(j=0; j<pPhrase->nToken; j++){
! 339: mHighlight |= (mPos>>j);
! 340: }
! 341:
! 342: if( 0==(*pCsr & 0x0FE) ) break;
! 343: fts3GetDeltaPosition(&pCsr, &iCsr);
! 344: }
! 345: }
! 346: }
! 347:
! 348: /* Set the output variables before returning. */
! 349: *piToken = iStart;
! 350: *piScore = iScore;
! 351: *pmCover = mCover;
! 352: *pmHighlight = mHighlight;
! 353: }
! 354:
! 355: /*
! 356: ** This function is an fts3ExprIterate() callback used by fts3BestSnippet().
! 357: ** Each invocation populates an element of the SnippetIter.aPhrase[] array.
! 358: */
! 359: static int fts3SnippetFindPositions(Fts3Expr *pExpr, int iPhrase, void *ctx){
! 360: SnippetIter *p = (SnippetIter *)ctx;
! 361: SnippetPhrase *pPhrase = &p->aPhrase[iPhrase];
! 362: char *pCsr;
! 363:
! 364: pPhrase->nToken = pExpr->pPhrase->nToken;
! 365:
! 366: pCsr = sqlite3Fts3EvalPhrasePoslist(p->pCsr, pExpr, p->iCol);
! 367: if( pCsr ){
! 368: int iFirst = 0;
! 369: pPhrase->pList = pCsr;
! 370: fts3GetDeltaPosition(&pCsr, &iFirst);
! 371: assert( iFirst>=0 );
! 372: pPhrase->pHead = pCsr;
! 373: pPhrase->pTail = pCsr;
! 374: pPhrase->iHead = iFirst;
! 375: pPhrase->iTail = iFirst;
! 376: }else{
! 377: assert( pPhrase->pList==0 && pPhrase->pHead==0 && pPhrase->pTail==0 );
! 378: }
! 379:
! 380: return SQLITE_OK;
! 381: }
! 382:
! 383: /*
! 384: ** Select the fragment of text consisting of nFragment contiguous tokens
! 385: ** from column iCol that represent the "best" snippet. The best snippet
! 386: ** is the snippet with the highest score, where scores are calculated
! 387: ** by adding:
! 388: **
! 389: ** (a) +1 point for each occurence of a matchable phrase in the snippet.
! 390: **
! 391: ** (b) +1000 points for the first occurence of each matchable phrase in
! 392: ** the snippet for which the corresponding mCovered bit is not set.
! 393: **
! 394: ** The selected snippet parameters are stored in structure *pFragment before
! 395: ** returning. The score of the selected snippet is stored in *piScore
! 396: ** before returning.
! 397: */
! 398: static int fts3BestSnippet(
! 399: int nSnippet, /* Desired snippet length */
! 400: Fts3Cursor *pCsr, /* Cursor to create snippet for */
! 401: int iCol, /* Index of column to create snippet from */
! 402: u64 mCovered, /* Mask of phrases already covered */
! 403: u64 *pmSeen, /* IN/OUT: Mask of phrases seen */
! 404: SnippetFragment *pFragment, /* OUT: Best snippet found */
! 405: int *piScore /* OUT: Score of snippet pFragment */
! 406: ){
! 407: int rc; /* Return Code */
! 408: int nList; /* Number of phrases in expression */
! 409: SnippetIter sIter; /* Iterates through snippet candidates */
! 410: int nByte; /* Number of bytes of space to allocate */
! 411: int iBestScore = -1; /* Best snippet score found so far */
! 412: int i; /* Loop counter */
! 413:
! 414: memset(&sIter, 0, sizeof(sIter));
! 415:
! 416: /* Iterate through the phrases in the expression to count them. The same
! 417: ** callback makes sure the doclists are loaded for each phrase.
! 418: */
! 419: rc = fts3ExprLoadDoclists(pCsr, &nList, 0);
! 420: if( rc!=SQLITE_OK ){
! 421: return rc;
! 422: }
! 423:
! 424: /* Now that it is known how many phrases there are, allocate and zero
! 425: ** the required space using malloc().
! 426: */
! 427: nByte = sizeof(SnippetPhrase) * nList;
! 428: sIter.aPhrase = (SnippetPhrase *)sqlite3_malloc(nByte);
! 429: if( !sIter.aPhrase ){
! 430: return SQLITE_NOMEM;
! 431: }
! 432: memset(sIter.aPhrase, 0, nByte);
! 433:
! 434: /* Initialize the contents of the SnippetIter object. Then iterate through
! 435: ** the set of phrases in the expression to populate the aPhrase[] array.
! 436: */
! 437: sIter.pCsr = pCsr;
! 438: sIter.iCol = iCol;
! 439: sIter.nSnippet = nSnippet;
! 440: sIter.nPhrase = nList;
! 441: sIter.iCurrent = -1;
! 442: (void)fts3ExprIterate(pCsr->pExpr, fts3SnippetFindPositions, (void *)&sIter);
! 443:
! 444: /* Set the *pmSeen output variable. */
! 445: for(i=0; i<nList; i++){
! 446: if( sIter.aPhrase[i].pHead ){
! 447: *pmSeen |= (u64)1 << i;
! 448: }
! 449: }
! 450:
! 451: /* Loop through all candidate snippets. Store the best snippet in
! 452: ** *pFragment. Store its associated 'score' in iBestScore.
! 453: */
! 454: pFragment->iCol = iCol;
! 455: while( !fts3SnippetNextCandidate(&sIter) ){
! 456: int iPos;
! 457: int iScore;
! 458: u64 mCover;
! 459: u64 mHighlight;
! 460: fts3SnippetDetails(&sIter, mCovered, &iPos, &iScore, &mCover, &mHighlight);
! 461: assert( iScore>=0 );
! 462: if( iScore>iBestScore ){
! 463: pFragment->iPos = iPos;
! 464: pFragment->hlmask = mHighlight;
! 465: pFragment->covered = mCover;
! 466: iBestScore = iScore;
! 467: }
! 468: }
! 469:
! 470: sqlite3_free(sIter.aPhrase);
! 471: *piScore = iBestScore;
! 472: return SQLITE_OK;
! 473: }
! 474:
! 475:
! 476: /*
! 477: ** Append a string to the string-buffer passed as the first argument.
! 478: **
! 479: ** If nAppend is negative, then the length of the string zAppend is
! 480: ** determined using strlen().
! 481: */
! 482: static int fts3StringAppend(
! 483: StrBuffer *pStr, /* Buffer to append to */
! 484: const char *zAppend, /* Pointer to data to append to buffer */
! 485: int nAppend /* Size of zAppend in bytes (or -1) */
! 486: ){
! 487: if( nAppend<0 ){
! 488: nAppend = (int)strlen(zAppend);
! 489: }
! 490:
! 491: /* If there is insufficient space allocated at StrBuffer.z, use realloc()
! 492: ** to grow the buffer until so that it is big enough to accomadate the
! 493: ** appended data.
! 494: */
! 495: if( pStr->n+nAppend+1>=pStr->nAlloc ){
! 496: int nAlloc = pStr->nAlloc+nAppend+100;
! 497: char *zNew = sqlite3_realloc(pStr->z, nAlloc);
! 498: if( !zNew ){
! 499: return SQLITE_NOMEM;
! 500: }
! 501: pStr->z = zNew;
! 502: pStr->nAlloc = nAlloc;
! 503: }
! 504:
! 505: /* Append the data to the string buffer. */
! 506: memcpy(&pStr->z[pStr->n], zAppend, nAppend);
! 507: pStr->n += nAppend;
! 508: pStr->z[pStr->n] = '\0';
! 509:
! 510: return SQLITE_OK;
! 511: }
! 512:
! 513: /*
! 514: ** The fts3BestSnippet() function often selects snippets that end with a
! 515: ** query term. That is, the final term of the snippet is always a term
! 516: ** that requires highlighting. For example, if 'X' is a highlighted term
! 517: ** and '.' is a non-highlighted term, BestSnippet() may select:
! 518: **
! 519: ** ........X.....X
! 520: **
! 521: ** This function "shifts" the beginning of the snippet forward in the
! 522: ** document so that there are approximately the same number of
! 523: ** non-highlighted terms to the right of the final highlighted term as there
! 524: ** are to the left of the first highlighted term. For example, to this:
! 525: **
! 526: ** ....X.....X....
! 527: **
! 528: ** This is done as part of extracting the snippet text, not when selecting
! 529: ** the snippet. Snippet selection is done based on doclists only, so there
! 530: ** is no way for fts3BestSnippet() to know whether or not the document
! 531: ** actually contains terms that follow the final highlighted term.
! 532: */
! 533: static int fts3SnippetShift(
! 534: Fts3Table *pTab, /* FTS3 table snippet comes from */
! 535: int nSnippet, /* Number of tokens desired for snippet */
! 536: const char *zDoc, /* Document text to extract snippet from */
! 537: int nDoc, /* Size of buffer zDoc in bytes */
! 538: int *piPos, /* IN/OUT: First token of snippet */
! 539: u64 *pHlmask /* IN/OUT: Mask of tokens to highlight */
! 540: ){
! 541: u64 hlmask = *pHlmask; /* Local copy of initial highlight-mask */
! 542:
! 543: if( hlmask ){
! 544: int nLeft; /* Tokens to the left of first highlight */
! 545: int nRight; /* Tokens to the right of last highlight */
! 546: int nDesired; /* Ideal number of tokens to shift forward */
! 547:
! 548: for(nLeft=0; !(hlmask & ((u64)1 << nLeft)); nLeft++);
! 549: for(nRight=0; !(hlmask & ((u64)1 << (nSnippet-1-nRight))); nRight++);
! 550: nDesired = (nLeft-nRight)/2;
! 551:
! 552: /* Ideally, the start of the snippet should be pushed forward in the
! 553: ** document nDesired tokens. This block checks if there are actually
! 554: ** nDesired tokens to the right of the snippet. If so, *piPos and
! 555: ** *pHlMask are updated to shift the snippet nDesired tokens to the
! 556: ** right. Otherwise, the snippet is shifted by the number of tokens
! 557: ** available.
! 558: */
! 559: if( nDesired>0 ){
! 560: int nShift; /* Number of tokens to shift snippet by */
! 561: int iCurrent = 0; /* Token counter */
! 562: int rc; /* Return Code */
! 563: sqlite3_tokenizer_module *pMod;
! 564: sqlite3_tokenizer_cursor *pC;
! 565: pMod = (sqlite3_tokenizer_module *)pTab->pTokenizer->pModule;
! 566:
! 567: /* Open a cursor on zDoc/nDoc. Check if there are (nSnippet+nDesired)
! 568: ** or more tokens in zDoc/nDoc.
! 569: */
! 570: rc = pMod->xOpen(pTab->pTokenizer, zDoc, nDoc, &pC);
! 571: if( rc!=SQLITE_OK ){
! 572: return rc;
! 573: }
! 574: pC->pTokenizer = pTab->pTokenizer;
! 575: while( rc==SQLITE_OK && iCurrent<(nSnippet+nDesired) ){
! 576: const char *ZDUMMY; int DUMMY1, DUMMY2, DUMMY3;
! 577: rc = pMod->xNext(pC, &ZDUMMY, &DUMMY1, &DUMMY2, &DUMMY3, &iCurrent);
! 578: }
! 579: pMod->xClose(pC);
! 580: if( rc!=SQLITE_OK && rc!=SQLITE_DONE ){ return rc; }
! 581:
! 582: nShift = (rc==SQLITE_DONE)+iCurrent-nSnippet;
! 583: assert( nShift<=nDesired );
! 584: if( nShift>0 ){
! 585: *piPos += nShift;
! 586: *pHlmask = hlmask >> nShift;
! 587: }
! 588: }
! 589: }
! 590: return SQLITE_OK;
! 591: }
! 592:
! 593: /*
! 594: ** Extract the snippet text for fragment pFragment from cursor pCsr and
! 595: ** append it to string buffer pOut.
! 596: */
! 597: static int fts3SnippetText(
! 598: Fts3Cursor *pCsr, /* FTS3 Cursor */
! 599: SnippetFragment *pFragment, /* Snippet to extract */
! 600: int iFragment, /* Fragment number */
! 601: int isLast, /* True for final fragment in snippet */
! 602: int nSnippet, /* Number of tokens in extracted snippet */
! 603: const char *zOpen, /* String inserted before highlighted term */
! 604: const char *zClose, /* String inserted after highlighted term */
! 605: const char *zEllipsis, /* String inserted between snippets */
! 606: StrBuffer *pOut /* Write output here */
! 607: ){
! 608: Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
! 609: int rc; /* Return code */
! 610: const char *zDoc; /* Document text to extract snippet from */
! 611: int nDoc; /* Size of zDoc in bytes */
! 612: int iCurrent = 0; /* Current token number of document */
! 613: int iEnd = 0; /* Byte offset of end of current token */
! 614: int isShiftDone = 0; /* True after snippet is shifted */
! 615: int iPos = pFragment->iPos; /* First token of snippet */
! 616: u64 hlmask = pFragment->hlmask; /* Highlight-mask for snippet */
! 617: int iCol = pFragment->iCol+1; /* Query column to extract text from */
! 618: sqlite3_tokenizer_module *pMod; /* Tokenizer module methods object */
! 619: sqlite3_tokenizer_cursor *pC; /* Tokenizer cursor open on zDoc/nDoc */
! 620: const char *ZDUMMY; /* Dummy argument used with tokenizer */
! 621: int DUMMY1; /* Dummy argument used with tokenizer */
! 622:
! 623: zDoc = (const char *)sqlite3_column_text(pCsr->pStmt, iCol);
! 624: if( zDoc==0 ){
! 625: if( sqlite3_column_type(pCsr->pStmt, iCol)!=SQLITE_NULL ){
! 626: return SQLITE_NOMEM;
! 627: }
! 628: return SQLITE_OK;
! 629: }
! 630: nDoc = sqlite3_column_bytes(pCsr->pStmt, iCol);
! 631:
! 632: /* Open a token cursor on the document. */
! 633: pMod = (sqlite3_tokenizer_module *)pTab->pTokenizer->pModule;
! 634: rc = pMod->xOpen(pTab->pTokenizer, zDoc, nDoc, &pC);
! 635: if( rc!=SQLITE_OK ){
! 636: return rc;
! 637: }
! 638: pC->pTokenizer = pTab->pTokenizer;
! 639:
! 640: while( rc==SQLITE_OK ){
! 641: int iBegin; /* Offset in zDoc of start of token */
! 642: int iFin; /* Offset in zDoc of end of token */
! 643: int isHighlight; /* True for highlighted terms */
! 644:
! 645: rc = pMod->xNext(pC, &ZDUMMY, &DUMMY1, &iBegin, &iFin, &iCurrent);
! 646: if( rc!=SQLITE_OK ){
! 647: if( rc==SQLITE_DONE ){
! 648: /* Special case - the last token of the snippet is also the last token
! 649: ** of the column. Append any punctuation that occurred between the end
! 650: ** of the previous token and the end of the document to the output.
! 651: ** Then break out of the loop. */
! 652: rc = fts3StringAppend(pOut, &zDoc[iEnd], -1);
! 653: }
! 654: break;
! 655: }
! 656: if( iCurrent<iPos ){ continue; }
! 657:
! 658: if( !isShiftDone ){
! 659: int n = nDoc - iBegin;
! 660: rc = fts3SnippetShift(pTab, nSnippet, &zDoc[iBegin], n, &iPos, &hlmask);
! 661: isShiftDone = 1;
! 662:
! 663: /* Now that the shift has been done, check if the initial "..." are
! 664: ** required. They are required if (a) this is not the first fragment,
! 665: ** or (b) this fragment does not begin at position 0 of its column.
! 666: */
! 667: if( rc==SQLITE_OK && (iPos>0 || iFragment>0) ){
! 668: rc = fts3StringAppend(pOut, zEllipsis, -1);
! 669: }
! 670: if( rc!=SQLITE_OK || iCurrent<iPos ) continue;
! 671: }
! 672:
! 673: if( iCurrent>=(iPos+nSnippet) ){
! 674: if( isLast ){
! 675: rc = fts3StringAppend(pOut, zEllipsis, -1);
! 676: }
! 677: break;
! 678: }
! 679:
! 680: /* Set isHighlight to true if this term should be highlighted. */
! 681: isHighlight = (hlmask & ((u64)1 << (iCurrent-iPos)))!=0;
! 682:
! 683: if( iCurrent>iPos ) rc = fts3StringAppend(pOut, &zDoc[iEnd], iBegin-iEnd);
! 684: if( rc==SQLITE_OK && isHighlight ) rc = fts3StringAppend(pOut, zOpen, -1);
! 685: if( rc==SQLITE_OK ) rc = fts3StringAppend(pOut, &zDoc[iBegin], iFin-iBegin);
! 686: if( rc==SQLITE_OK && isHighlight ) rc = fts3StringAppend(pOut, zClose, -1);
! 687:
! 688: iEnd = iFin;
! 689: }
! 690:
! 691: pMod->xClose(pC);
! 692: return rc;
! 693: }
! 694:
! 695:
! 696: /*
! 697: ** This function is used to count the entries in a column-list (a
! 698: ** delta-encoded list of term offsets within a single column of a single
! 699: ** row). When this function is called, *ppCollist should point to the
! 700: ** beginning of the first varint in the column-list (the varint that
! 701: ** contains the position of the first matching term in the column data).
! 702: ** Before returning, *ppCollist is set to point to the first byte after
! 703: ** the last varint in the column-list (either the 0x00 signifying the end
! 704: ** of the position-list, or the 0x01 that precedes the column number of
! 705: ** the next column in the position-list).
! 706: **
! 707: ** The number of elements in the column-list is returned.
! 708: */
! 709: static int fts3ColumnlistCount(char **ppCollist){
! 710: char *pEnd = *ppCollist;
! 711: char c = 0;
! 712: int nEntry = 0;
! 713:
! 714: /* A column-list is terminated by either a 0x01 or 0x00. */
! 715: while( 0xFE & (*pEnd | c) ){
! 716: c = *pEnd++ & 0x80;
! 717: if( !c ) nEntry++;
! 718: }
! 719:
! 720: *ppCollist = pEnd;
! 721: return nEntry;
! 722: }
! 723:
! 724: /*
! 725: ** fts3ExprIterate() callback used to collect the "global" matchinfo stats
! 726: ** for a single query.
! 727: **
! 728: ** fts3ExprIterate() callback to load the 'global' elements of a
! 729: ** FTS3_MATCHINFO_HITS matchinfo array. The global stats are those elements
! 730: ** of the matchinfo array that are constant for all rows returned by the
! 731: ** current query.
! 732: **
! 733: ** Argument pCtx is actually a pointer to a struct of type MatchInfo. This
! 734: ** function populates Matchinfo.aMatchinfo[] as follows:
! 735: **
! 736: ** for(iCol=0; iCol<nCol; iCol++){
! 737: ** aMatchinfo[3*iPhrase*nCol + 3*iCol + 1] = X;
! 738: ** aMatchinfo[3*iPhrase*nCol + 3*iCol + 2] = Y;
! 739: ** }
! 740: **
! 741: ** where X is the number of matches for phrase iPhrase is column iCol of all
! 742: ** rows of the table. Y is the number of rows for which column iCol contains
! 743: ** at least one instance of phrase iPhrase.
! 744: **
! 745: ** If the phrase pExpr consists entirely of deferred tokens, then all X and
! 746: ** Y values are set to nDoc, where nDoc is the number of documents in the
! 747: ** file system. This is done because the full-text index doclist is required
! 748: ** to calculate these values properly, and the full-text index doclist is
! 749: ** not available for deferred tokens.
! 750: */
! 751: static int fts3ExprGlobalHitsCb(
! 752: Fts3Expr *pExpr, /* Phrase expression node */
! 753: int iPhrase, /* Phrase number (numbered from zero) */
! 754: void *pCtx /* Pointer to MatchInfo structure */
! 755: ){
! 756: MatchInfo *p = (MatchInfo *)pCtx;
! 757: return sqlite3Fts3EvalPhraseStats(
! 758: p->pCursor, pExpr, &p->aMatchinfo[3*iPhrase*p->nCol]
! 759: );
! 760: }
! 761:
! 762: /*
! 763: ** fts3ExprIterate() callback used to collect the "local" part of the
! 764: ** FTS3_MATCHINFO_HITS array. The local stats are those elements of the
! 765: ** array that are different for each row returned by the query.
! 766: */
! 767: static int fts3ExprLocalHitsCb(
! 768: Fts3Expr *pExpr, /* Phrase expression node */
! 769: int iPhrase, /* Phrase number */
! 770: void *pCtx /* Pointer to MatchInfo structure */
! 771: ){
! 772: MatchInfo *p = (MatchInfo *)pCtx;
! 773: int iStart = iPhrase * p->nCol * 3;
! 774: int i;
! 775:
! 776: for(i=0; i<p->nCol; i++){
! 777: char *pCsr;
! 778: pCsr = sqlite3Fts3EvalPhrasePoslist(p->pCursor, pExpr, i);
! 779: if( pCsr ){
! 780: p->aMatchinfo[iStart+i*3] = fts3ColumnlistCount(&pCsr);
! 781: }else{
! 782: p->aMatchinfo[iStart+i*3] = 0;
! 783: }
! 784: }
! 785:
! 786: return SQLITE_OK;
! 787: }
! 788:
! 789: static int fts3MatchinfoCheck(
! 790: Fts3Table *pTab,
! 791: char cArg,
! 792: char **pzErr
! 793: ){
! 794: if( (cArg==FTS3_MATCHINFO_NPHRASE)
! 795: || (cArg==FTS3_MATCHINFO_NCOL)
! 796: || (cArg==FTS3_MATCHINFO_NDOC && pTab->bHasStat)
! 797: || (cArg==FTS3_MATCHINFO_AVGLENGTH && pTab->bHasStat)
! 798: || (cArg==FTS3_MATCHINFO_LENGTH && pTab->bHasDocsize)
! 799: || (cArg==FTS3_MATCHINFO_LCS)
! 800: || (cArg==FTS3_MATCHINFO_HITS)
! 801: ){
! 802: return SQLITE_OK;
! 803: }
! 804: *pzErr = sqlite3_mprintf("unrecognized matchinfo request: %c", cArg);
! 805: return SQLITE_ERROR;
! 806: }
! 807:
! 808: static int fts3MatchinfoSize(MatchInfo *pInfo, char cArg){
! 809: int nVal; /* Number of integers output by cArg */
! 810:
! 811: switch( cArg ){
! 812: case FTS3_MATCHINFO_NDOC:
! 813: case FTS3_MATCHINFO_NPHRASE:
! 814: case FTS3_MATCHINFO_NCOL:
! 815: nVal = 1;
! 816: break;
! 817:
! 818: case FTS3_MATCHINFO_AVGLENGTH:
! 819: case FTS3_MATCHINFO_LENGTH:
! 820: case FTS3_MATCHINFO_LCS:
! 821: nVal = pInfo->nCol;
! 822: break;
! 823:
! 824: default:
! 825: assert( cArg==FTS3_MATCHINFO_HITS );
! 826: nVal = pInfo->nCol * pInfo->nPhrase * 3;
! 827: break;
! 828: }
! 829:
! 830: return nVal;
! 831: }
! 832:
! 833: static int fts3MatchinfoSelectDoctotal(
! 834: Fts3Table *pTab,
! 835: sqlite3_stmt **ppStmt,
! 836: sqlite3_int64 *pnDoc,
! 837: const char **paLen
! 838: ){
! 839: sqlite3_stmt *pStmt;
! 840: const char *a;
! 841: sqlite3_int64 nDoc;
! 842:
! 843: if( !*ppStmt ){
! 844: int rc = sqlite3Fts3SelectDoctotal(pTab, ppStmt);
! 845: if( rc!=SQLITE_OK ) return rc;
! 846: }
! 847: pStmt = *ppStmt;
! 848: assert( sqlite3_data_count(pStmt)==1 );
! 849:
! 850: a = sqlite3_column_blob(pStmt, 0);
! 851: a += sqlite3Fts3GetVarint(a, &nDoc);
! 852: if( nDoc==0 ) return FTS_CORRUPT_VTAB;
! 853: *pnDoc = (u32)nDoc;
! 854:
! 855: if( paLen ) *paLen = a;
! 856: return SQLITE_OK;
! 857: }
! 858:
! 859: /*
! 860: ** An instance of the following structure is used to store state while
! 861: ** iterating through a multi-column position-list corresponding to the
! 862: ** hits for a single phrase on a single row in order to calculate the
! 863: ** values for a matchinfo() FTS3_MATCHINFO_LCS request.
! 864: */
! 865: typedef struct LcsIterator LcsIterator;
! 866: struct LcsIterator {
! 867: Fts3Expr *pExpr; /* Pointer to phrase expression */
! 868: int iPosOffset; /* Tokens count up to end of this phrase */
! 869: char *pRead; /* Cursor used to iterate through aDoclist */
! 870: int iPos; /* Current position */
! 871: };
! 872:
! 873: /*
! 874: ** If LcsIterator.iCol is set to the following value, the iterator has
! 875: ** finished iterating through all offsets for all columns.
! 876: */
! 877: #define LCS_ITERATOR_FINISHED 0x7FFFFFFF;
! 878:
! 879: static int fts3MatchinfoLcsCb(
! 880: Fts3Expr *pExpr, /* Phrase expression node */
! 881: int iPhrase, /* Phrase number (numbered from zero) */
! 882: void *pCtx /* Pointer to MatchInfo structure */
! 883: ){
! 884: LcsIterator *aIter = (LcsIterator *)pCtx;
! 885: aIter[iPhrase].pExpr = pExpr;
! 886: return SQLITE_OK;
! 887: }
! 888:
! 889: /*
! 890: ** Advance the iterator passed as an argument to the next position. Return
! 891: ** 1 if the iterator is at EOF or if it now points to the start of the
! 892: ** position list for the next column.
! 893: */
! 894: static int fts3LcsIteratorAdvance(LcsIterator *pIter){
! 895: char *pRead = pIter->pRead;
! 896: sqlite3_int64 iRead;
! 897: int rc = 0;
! 898:
! 899: pRead += sqlite3Fts3GetVarint(pRead, &iRead);
! 900: if( iRead==0 || iRead==1 ){
! 901: pRead = 0;
! 902: rc = 1;
! 903: }else{
! 904: pIter->iPos += (int)(iRead-2);
! 905: }
! 906:
! 907: pIter->pRead = pRead;
! 908: return rc;
! 909: }
! 910:
! 911: /*
! 912: ** This function implements the FTS3_MATCHINFO_LCS matchinfo() flag.
! 913: **
! 914: ** If the call is successful, the longest-common-substring lengths for each
! 915: ** column are written into the first nCol elements of the pInfo->aMatchinfo[]
! 916: ** array before returning. SQLITE_OK is returned in this case.
! 917: **
! 918: ** Otherwise, if an error occurs, an SQLite error code is returned and the
! 919: ** data written to the first nCol elements of pInfo->aMatchinfo[] is
! 920: ** undefined.
! 921: */
! 922: static int fts3MatchinfoLcs(Fts3Cursor *pCsr, MatchInfo *pInfo){
! 923: LcsIterator *aIter;
! 924: int i;
! 925: int iCol;
! 926: int nToken = 0;
! 927:
! 928: /* Allocate and populate the array of LcsIterator objects. The array
! 929: ** contains one element for each matchable phrase in the query.
! 930: **/
! 931: aIter = sqlite3_malloc(sizeof(LcsIterator) * pCsr->nPhrase);
! 932: if( !aIter ) return SQLITE_NOMEM;
! 933: memset(aIter, 0, sizeof(LcsIterator) * pCsr->nPhrase);
! 934: (void)fts3ExprIterate(pCsr->pExpr, fts3MatchinfoLcsCb, (void*)aIter);
! 935:
! 936: for(i=0; i<pInfo->nPhrase; i++){
! 937: LcsIterator *pIter = &aIter[i];
! 938: nToken -= pIter->pExpr->pPhrase->nToken;
! 939: pIter->iPosOffset = nToken;
! 940: }
! 941:
! 942: for(iCol=0; iCol<pInfo->nCol; iCol++){
! 943: int nLcs = 0; /* LCS value for this column */
! 944: int nLive = 0; /* Number of iterators in aIter not at EOF */
! 945:
! 946: for(i=0; i<pInfo->nPhrase; i++){
! 947: LcsIterator *pIt = &aIter[i];
! 948: pIt->pRead = sqlite3Fts3EvalPhrasePoslist(pCsr, pIt->pExpr, iCol);
! 949: if( pIt->pRead ){
! 950: pIt->iPos = pIt->iPosOffset;
! 951: fts3LcsIteratorAdvance(&aIter[i]);
! 952: nLive++;
! 953: }
! 954: }
! 955:
! 956: while( nLive>0 ){
! 957: LcsIterator *pAdv = 0; /* The iterator to advance by one position */
! 958: int nThisLcs = 0; /* LCS for the current iterator positions */
! 959:
! 960: for(i=0; i<pInfo->nPhrase; i++){
! 961: LcsIterator *pIter = &aIter[i];
! 962: if( pIter->pRead==0 ){
! 963: /* This iterator is already at EOF for this column. */
! 964: nThisLcs = 0;
! 965: }else{
! 966: if( pAdv==0 || pIter->iPos<pAdv->iPos ){
! 967: pAdv = pIter;
! 968: }
! 969: if( nThisLcs==0 || pIter->iPos==pIter[-1].iPos ){
! 970: nThisLcs++;
! 971: }else{
! 972: nThisLcs = 1;
! 973: }
! 974: if( nThisLcs>nLcs ) nLcs = nThisLcs;
! 975: }
! 976: }
! 977: if( fts3LcsIteratorAdvance(pAdv) ) nLive--;
! 978: }
! 979:
! 980: pInfo->aMatchinfo[iCol] = nLcs;
! 981: }
! 982:
! 983: sqlite3_free(aIter);
! 984: return SQLITE_OK;
! 985: }
! 986:
! 987: /*
! 988: ** Populate the buffer pInfo->aMatchinfo[] with an array of integers to
! 989: ** be returned by the matchinfo() function. Argument zArg contains the
! 990: ** format string passed as the second argument to matchinfo (or the
! 991: ** default value "pcx" if no second argument was specified). The format
! 992: ** string has already been validated and the pInfo->aMatchinfo[] array
! 993: ** is guaranteed to be large enough for the output.
! 994: **
! 995: ** If bGlobal is true, then populate all fields of the matchinfo() output.
! 996: ** If it is false, then assume that those fields that do not change between
! 997: ** rows (i.e. FTS3_MATCHINFO_NPHRASE, NCOL, NDOC, AVGLENGTH and part of HITS)
! 998: ** have already been populated.
! 999: **
! 1000: ** Return SQLITE_OK if successful, or an SQLite error code if an error
! 1001: ** occurs. If a value other than SQLITE_OK is returned, the state the
! 1002: ** pInfo->aMatchinfo[] buffer is left in is undefined.
! 1003: */
! 1004: static int fts3MatchinfoValues(
! 1005: Fts3Cursor *pCsr, /* FTS3 cursor object */
! 1006: int bGlobal, /* True to grab the global stats */
! 1007: MatchInfo *pInfo, /* Matchinfo context object */
! 1008: const char *zArg /* Matchinfo format string */
! 1009: ){
! 1010: int rc = SQLITE_OK;
! 1011: int i;
! 1012: Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
! 1013: sqlite3_stmt *pSelect = 0;
! 1014:
! 1015: for(i=0; rc==SQLITE_OK && zArg[i]; i++){
! 1016:
! 1017: switch( zArg[i] ){
! 1018: case FTS3_MATCHINFO_NPHRASE:
! 1019: if( bGlobal ) pInfo->aMatchinfo[0] = pInfo->nPhrase;
! 1020: break;
! 1021:
! 1022: case FTS3_MATCHINFO_NCOL:
! 1023: if( bGlobal ) pInfo->aMatchinfo[0] = pInfo->nCol;
! 1024: break;
! 1025:
! 1026: case FTS3_MATCHINFO_NDOC:
! 1027: if( bGlobal ){
! 1028: sqlite3_int64 nDoc = 0;
! 1029: rc = fts3MatchinfoSelectDoctotal(pTab, &pSelect, &nDoc, 0);
! 1030: pInfo->aMatchinfo[0] = (u32)nDoc;
! 1031: }
! 1032: break;
! 1033:
! 1034: case FTS3_MATCHINFO_AVGLENGTH:
! 1035: if( bGlobal ){
! 1036: sqlite3_int64 nDoc; /* Number of rows in table */
! 1037: const char *a; /* Aggregate column length array */
! 1038:
! 1039: rc = fts3MatchinfoSelectDoctotal(pTab, &pSelect, &nDoc, &a);
! 1040: if( rc==SQLITE_OK ){
! 1041: int iCol;
! 1042: for(iCol=0; iCol<pInfo->nCol; iCol++){
! 1043: u32 iVal;
! 1044: sqlite3_int64 nToken;
! 1045: a += sqlite3Fts3GetVarint(a, &nToken);
! 1046: iVal = (u32)(((u32)(nToken&0xffffffff)+nDoc/2)/nDoc);
! 1047: pInfo->aMatchinfo[iCol] = iVal;
! 1048: }
! 1049: }
! 1050: }
! 1051: break;
! 1052:
! 1053: case FTS3_MATCHINFO_LENGTH: {
! 1054: sqlite3_stmt *pSelectDocsize = 0;
! 1055: rc = sqlite3Fts3SelectDocsize(pTab, pCsr->iPrevId, &pSelectDocsize);
! 1056: if( rc==SQLITE_OK ){
! 1057: int iCol;
! 1058: const char *a = sqlite3_column_blob(pSelectDocsize, 0);
! 1059: for(iCol=0; iCol<pInfo->nCol; iCol++){
! 1060: sqlite3_int64 nToken;
! 1061: a += sqlite3Fts3GetVarint(a, &nToken);
! 1062: pInfo->aMatchinfo[iCol] = (u32)nToken;
! 1063: }
! 1064: }
! 1065: sqlite3_reset(pSelectDocsize);
! 1066: break;
! 1067: }
! 1068:
! 1069: case FTS3_MATCHINFO_LCS:
! 1070: rc = fts3ExprLoadDoclists(pCsr, 0, 0);
! 1071: if( rc==SQLITE_OK ){
! 1072: rc = fts3MatchinfoLcs(pCsr, pInfo);
! 1073: }
! 1074: break;
! 1075:
! 1076: default: {
! 1077: Fts3Expr *pExpr;
! 1078: assert( zArg[i]==FTS3_MATCHINFO_HITS );
! 1079: pExpr = pCsr->pExpr;
! 1080: rc = fts3ExprLoadDoclists(pCsr, 0, 0);
! 1081: if( rc!=SQLITE_OK ) break;
! 1082: if( bGlobal ){
! 1083: if( pCsr->pDeferred ){
! 1084: rc = fts3MatchinfoSelectDoctotal(pTab, &pSelect, &pInfo->nDoc, 0);
! 1085: if( rc!=SQLITE_OK ) break;
! 1086: }
! 1087: rc = fts3ExprIterate(pExpr, fts3ExprGlobalHitsCb,(void*)pInfo);
! 1088: if( rc!=SQLITE_OK ) break;
! 1089: }
! 1090: (void)fts3ExprIterate(pExpr, fts3ExprLocalHitsCb,(void*)pInfo);
! 1091: break;
! 1092: }
! 1093: }
! 1094:
! 1095: pInfo->aMatchinfo += fts3MatchinfoSize(pInfo, zArg[i]);
! 1096: }
! 1097:
! 1098: sqlite3_reset(pSelect);
! 1099: return rc;
! 1100: }
! 1101:
! 1102:
! 1103: /*
! 1104: ** Populate pCsr->aMatchinfo[] with data for the current row. The
! 1105: ** 'matchinfo' data is an array of 32-bit unsigned integers (C type u32).
! 1106: */
! 1107: static int fts3GetMatchinfo(
! 1108: Fts3Cursor *pCsr, /* FTS3 Cursor object */
! 1109: const char *zArg /* Second argument to matchinfo() function */
! 1110: ){
! 1111: MatchInfo sInfo;
! 1112: Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
! 1113: int rc = SQLITE_OK;
! 1114: int bGlobal = 0; /* Collect 'global' stats as well as local */
! 1115:
! 1116: memset(&sInfo, 0, sizeof(MatchInfo));
! 1117: sInfo.pCursor = pCsr;
! 1118: sInfo.nCol = pTab->nColumn;
! 1119:
! 1120: /* If there is cached matchinfo() data, but the format string for the
! 1121: ** cache does not match the format string for this request, discard
! 1122: ** the cached data. */
! 1123: if( pCsr->zMatchinfo && strcmp(pCsr->zMatchinfo, zArg) ){
! 1124: assert( pCsr->aMatchinfo );
! 1125: sqlite3_free(pCsr->aMatchinfo);
! 1126: pCsr->zMatchinfo = 0;
! 1127: pCsr->aMatchinfo = 0;
! 1128: }
! 1129:
! 1130: /* If Fts3Cursor.aMatchinfo[] is NULL, then this is the first time the
! 1131: ** matchinfo function has been called for this query. In this case
! 1132: ** allocate the array used to accumulate the matchinfo data and
! 1133: ** initialize those elements that are constant for every row.
! 1134: */
! 1135: if( pCsr->aMatchinfo==0 ){
! 1136: int nMatchinfo = 0; /* Number of u32 elements in match-info */
! 1137: int nArg; /* Bytes in zArg */
! 1138: int i; /* Used to iterate through zArg */
! 1139:
! 1140: /* Determine the number of phrases in the query */
! 1141: pCsr->nPhrase = fts3ExprPhraseCount(pCsr->pExpr);
! 1142: sInfo.nPhrase = pCsr->nPhrase;
! 1143:
! 1144: /* Determine the number of integers in the buffer returned by this call. */
! 1145: for(i=0; zArg[i]; i++){
! 1146: nMatchinfo += fts3MatchinfoSize(&sInfo, zArg[i]);
! 1147: }
! 1148:
! 1149: /* Allocate space for Fts3Cursor.aMatchinfo[] and Fts3Cursor.zMatchinfo. */
! 1150: nArg = (int)strlen(zArg);
! 1151: pCsr->aMatchinfo = (u32 *)sqlite3_malloc(sizeof(u32)*nMatchinfo + nArg + 1);
! 1152: if( !pCsr->aMatchinfo ) return SQLITE_NOMEM;
! 1153:
! 1154: pCsr->zMatchinfo = (char *)&pCsr->aMatchinfo[nMatchinfo];
! 1155: pCsr->nMatchinfo = nMatchinfo;
! 1156: memcpy(pCsr->zMatchinfo, zArg, nArg+1);
! 1157: memset(pCsr->aMatchinfo, 0, sizeof(u32)*nMatchinfo);
! 1158: pCsr->isMatchinfoNeeded = 1;
! 1159: bGlobal = 1;
! 1160: }
! 1161:
! 1162: sInfo.aMatchinfo = pCsr->aMatchinfo;
! 1163: sInfo.nPhrase = pCsr->nPhrase;
! 1164: if( pCsr->isMatchinfoNeeded ){
! 1165: rc = fts3MatchinfoValues(pCsr, bGlobal, &sInfo, zArg);
! 1166: pCsr->isMatchinfoNeeded = 0;
! 1167: }
! 1168:
! 1169: return rc;
! 1170: }
! 1171:
! 1172: /*
! 1173: ** Implementation of snippet() function.
! 1174: */
! 1175: void sqlite3Fts3Snippet(
! 1176: sqlite3_context *pCtx, /* SQLite function call context */
! 1177: Fts3Cursor *pCsr, /* Cursor object */
! 1178: const char *zStart, /* Snippet start text - "<b>" */
! 1179: const char *zEnd, /* Snippet end text - "</b>" */
! 1180: const char *zEllipsis, /* Snippet ellipsis text - "<b>...</b>" */
! 1181: int iCol, /* Extract snippet from this column */
! 1182: int nToken /* Approximate number of tokens in snippet */
! 1183: ){
! 1184: Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
! 1185: int rc = SQLITE_OK;
! 1186: int i;
! 1187: StrBuffer res = {0, 0, 0};
! 1188:
! 1189: /* The returned text includes up to four fragments of text extracted from
! 1190: ** the data in the current row. The first iteration of the for(...) loop
! 1191: ** below attempts to locate a single fragment of text nToken tokens in
! 1192: ** size that contains at least one instance of all phrases in the query
! 1193: ** expression that appear in the current row. If such a fragment of text
! 1194: ** cannot be found, the second iteration of the loop attempts to locate
! 1195: ** a pair of fragments, and so on.
! 1196: */
! 1197: int nSnippet = 0; /* Number of fragments in this snippet */
! 1198: SnippetFragment aSnippet[4]; /* Maximum of 4 fragments per snippet */
! 1199: int nFToken = -1; /* Number of tokens in each fragment */
! 1200:
! 1201: if( !pCsr->pExpr ){
! 1202: sqlite3_result_text(pCtx, "", 0, SQLITE_STATIC);
! 1203: return;
! 1204: }
! 1205:
! 1206: for(nSnippet=1; 1; nSnippet++){
! 1207:
! 1208: int iSnip; /* Loop counter 0..nSnippet-1 */
! 1209: u64 mCovered = 0; /* Bitmask of phrases covered by snippet */
! 1210: u64 mSeen = 0; /* Bitmask of phrases seen by BestSnippet() */
! 1211:
! 1212: if( nToken>=0 ){
! 1213: nFToken = (nToken+nSnippet-1) / nSnippet;
! 1214: }else{
! 1215: nFToken = -1 * nToken;
! 1216: }
! 1217:
! 1218: for(iSnip=0; iSnip<nSnippet; iSnip++){
! 1219: int iBestScore = -1; /* Best score of columns checked so far */
! 1220: int iRead; /* Used to iterate through columns */
! 1221: SnippetFragment *pFragment = &aSnippet[iSnip];
! 1222:
! 1223: memset(pFragment, 0, sizeof(*pFragment));
! 1224:
! 1225: /* Loop through all columns of the table being considered for snippets.
! 1226: ** If the iCol argument to this function was negative, this means all
! 1227: ** columns of the FTS3 table. Otherwise, only column iCol is considered.
! 1228: */
! 1229: for(iRead=0; iRead<pTab->nColumn; iRead++){
! 1230: SnippetFragment sF = {0, 0, 0, 0};
! 1231: int iS;
! 1232: if( iCol>=0 && iRead!=iCol ) continue;
! 1233:
! 1234: /* Find the best snippet of nFToken tokens in column iRead. */
! 1235: rc = fts3BestSnippet(nFToken, pCsr, iRead, mCovered, &mSeen, &sF, &iS);
! 1236: if( rc!=SQLITE_OK ){
! 1237: goto snippet_out;
! 1238: }
! 1239: if( iS>iBestScore ){
! 1240: *pFragment = sF;
! 1241: iBestScore = iS;
! 1242: }
! 1243: }
! 1244:
! 1245: mCovered |= pFragment->covered;
! 1246: }
! 1247:
! 1248: /* If all query phrases seen by fts3BestSnippet() are present in at least
! 1249: ** one of the nSnippet snippet fragments, break out of the loop.
! 1250: */
! 1251: assert( (mCovered&mSeen)==mCovered );
! 1252: if( mSeen==mCovered || nSnippet==SizeofArray(aSnippet) ) break;
! 1253: }
! 1254:
! 1255: assert( nFToken>0 );
! 1256:
! 1257: for(i=0; i<nSnippet && rc==SQLITE_OK; i++){
! 1258: rc = fts3SnippetText(pCsr, &aSnippet[i],
! 1259: i, (i==nSnippet-1), nFToken, zStart, zEnd, zEllipsis, &res
! 1260: );
! 1261: }
! 1262:
! 1263: snippet_out:
! 1264: sqlite3Fts3SegmentsClose(pTab);
! 1265: if( rc!=SQLITE_OK ){
! 1266: sqlite3_result_error_code(pCtx, rc);
! 1267: sqlite3_free(res.z);
! 1268: }else{
! 1269: sqlite3_result_text(pCtx, res.z, -1, sqlite3_free);
! 1270: }
! 1271: }
! 1272:
! 1273:
! 1274: typedef struct TermOffset TermOffset;
! 1275: typedef struct TermOffsetCtx TermOffsetCtx;
! 1276:
! 1277: struct TermOffset {
! 1278: char *pList; /* Position-list */
! 1279: int iPos; /* Position just read from pList */
! 1280: int iOff; /* Offset of this term from read positions */
! 1281: };
! 1282:
! 1283: struct TermOffsetCtx {
! 1284: Fts3Cursor *pCsr;
! 1285: int iCol; /* Column of table to populate aTerm for */
! 1286: int iTerm;
! 1287: sqlite3_int64 iDocid;
! 1288: TermOffset *aTerm;
! 1289: };
! 1290:
! 1291: /*
! 1292: ** This function is an fts3ExprIterate() callback used by sqlite3Fts3Offsets().
! 1293: */
! 1294: static int fts3ExprTermOffsetInit(Fts3Expr *pExpr, int iPhrase, void *ctx){
! 1295: TermOffsetCtx *p = (TermOffsetCtx *)ctx;
! 1296: int nTerm; /* Number of tokens in phrase */
! 1297: int iTerm; /* For looping through nTerm phrase terms */
! 1298: char *pList; /* Pointer to position list for phrase */
! 1299: int iPos = 0; /* First position in position-list */
! 1300:
! 1301: UNUSED_PARAMETER(iPhrase);
! 1302: pList = sqlite3Fts3EvalPhrasePoslist(p->pCsr, pExpr, p->iCol);
! 1303: nTerm = pExpr->pPhrase->nToken;
! 1304: if( pList ){
! 1305: fts3GetDeltaPosition(&pList, &iPos);
! 1306: assert( iPos>=0 );
! 1307: }
! 1308:
! 1309: for(iTerm=0; iTerm<nTerm; iTerm++){
! 1310: TermOffset *pT = &p->aTerm[p->iTerm++];
! 1311: pT->iOff = nTerm-iTerm-1;
! 1312: pT->pList = pList;
! 1313: pT->iPos = iPos;
! 1314: }
! 1315:
! 1316: return SQLITE_OK;
! 1317: }
! 1318:
! 1319: /*
! 1320: ** Implementation of offsets() function.
! 1321: */
! 1322: void sqlite3Fts3Offsets(
! 1323: sqlite3_context *pCtx, /* SQLite function call context */
! 1324: Fts3Cursor *pCsr /* Cursor object */
! 1325: ){
! 1326: Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
! 1327: sqlite3_tokenizer_module const *pMod = pTab->pTokenizer->pModule;
! 1328: const char *ZDUMMY; /* Dummy argument used with xNext() */
! 1329: int NDUMMY; /* Dummy argument used with xNext() */
! 1330: int rc; /* Return Code */
! 1331: int nToken; /* Number of tokens in query */
! 1332: int iCol; /* Column currently being processed */
! 1333: StrBuffer res = {0, 0, 0}; /* Result string */
! 1334: TermOffsetCtx sCtx; /* Context for fts3ExprTermOffsetInit() */
! 1335:
! 1336: if( !pCsr->pExpr ){
! 1337: sqlite3_result_text(pCtx, "", 0, SQLITE_STATIC);
! 1338: return;
! 1339: }
! 1340:
! 1341: memset(&sCtx, 0, sizeof(sCtx));
! 1342: assert( pCsr->isRequireSeek==0 );
! 1343:
! 1344: /* Count the number of terms in the query */
! 1345: rc = fts3ExprLoadDoclists(pCsr, 0, &nToken);
! 1346: if( rc!=SQLITE_OK ) goto offsets_out;
! 1347:
! 1348: /* Allocate the array of TermOffset iterators. */
! 1349: sCtx.aTerm = (TermOffset *)sqlite3_malloc(sizeof(TermOffset)*nToken);
! 1350: if( 0==sCtx.aTerm ){
! 1351: rc = SQLITE_NOMEM;
! 1352: goto offsets_out;
! 1353: }
! 1354: sCtx.iDocid = pCsr->iPrevId;
! 1355: sCtx.pCsr = pCsr;
! 1356:
! 1357: /* Loop through the table columns, appending offset information to
! 1358: ** string-buffer res for each column.
! 1359: */
! 1360: for(iCol=0; iCol<pTab->nColumn; iCol++){
! 1361: sqlite3_tokenizer_cursor *pC; /* Tokenizer cursor */
! 1362: int iStart;
! 1363: int iEnd;
! 1364: int iCurrent;
! 1365: const char *zDoc;
! 1366: int nDoc;
! 1367:
! 1368: /* Initialize the contents of sCtx.aTerm[] for column iCol. There is
! 1369: ** no way that this operation can fail, so the return code from
! 1370: ** fts3ExprIterate() can be discarded.
! 1371: */
! 1372: sCtx.iCol = iCol;
! 1373: sCtx.iTerm = 0;
! 1374: (void)fts3ExprIterate(pCsr->pExpr, fts3ExprTermOffsetInit, (void *)&sCtx);
! 1375:
! 1376: /* Retreive the text stored in column iCol. If an SQL NULL is stored
! 1377: ** in column iCol, jump immediately to the next iteration of the loop.
! 1378: ** If an OOM occurs while retrieving the data (this can happen if SQLite
! 1379: ** needs to transform the data from utf-16 to utf-8), return SQLITE_NOMEM
! 1380: ** to the caller.
! 1381: */
! 1382: zDoc = (const char *)sqlite3_column_text(pCsr->pStmt, iCol+1);
! 1383: nDoc = sqlite3_column_bytes(pCsr->pStmt, iCol+1);
! 1384: if( zDoc==0 ){
! 1385: if( sqlite3_column_type(pCsr->pStmt, iCol+1)==SQLITE_NULL ){
! 1386: continue;
! 1387: }
! 1388: rc = SQLITE_NOMEM;
! 1389: goto offsets_out;
! 1390: }
! 1391:
! 1392: /* Initialize a tokenizer iterator to iterate through column iCol. */
! 1393: rc = pMod->xOpen(pTab->pTokenizer, zDoc, nDoc, &pC);
! 1394: if( rc!=SQLITE_OK ) goto offsets_out;
! 1395: pC->pTokenizer = pTab->pTokenizer;
! 1396:
! 1397: rc = pMod->xNext(pC, &ZDUMMY, &NDUMMY, &iStart, &iEnd, &iCurrent);
! 1398: while( rc==SQLITE_OK ){
! 1399: int i; /* Used to loop through terms */
! 1400: int iMinPos = 0x7FFFFFFF; /* Position of next token */
! 1401: TermOffset *pTerm = 0; /* TermOffset associated with next token */
! 1402:
! 1403: for(i=0; i<nToken; i++){
! 1404: TermOffset *pT = &sCtx.aTerm[i];
! 1405: if( pT->pList && (pT->iPos-pT->iOff)<iMinPos ){
! 1406: iMinPos = pT->iPos-pT->iOff;
! 1407: pTerm = pT;
! 1408: }
! 1409: }
! 1410:
! 1411: if( !pTerm ){
! 1412: /* All offsets for this column have been gathered. */
! 1413: rc = SQLITE_DONE;
! 1414: }else{
! 1415: assert( iCurrent<=iMinPos );
! 1416: if( 0==(0xFE&*pTerm->pList) ){
! 1417: pTerm->pList = 0;
! 1418: }else{
! 1419: fts3GetDeltaPosition(&pTerm->pList, &pTerm->iPos);
! 1420: }
! 1421: while( rc==SQLITE_OK && iCurrent<iMinPos ){
! 1422: rc = pMod->xNext(pC, &ZDUMMY, &NDUMMY, &iStart, &iEnd, &iCurrent);
! 1423: }
! 1424: if( rc==SQLITE_OK ){
! 1425: char aBuffer[64];
! 1426: sqlite3_snprintf(sizeof(aBuffer), aBuffer,
! 1427: "%d %d %d %d ", iCol, pTerm-sCtx.aTerm, iStart, iEnd-iStart
! 1428: );
! 1429: rc = fts3StringAppend(&res, aBuffer, -1);
! 1430: }else if( rc==SQLITE_DONE && pTab->zContentTbl==0 ){
! 1431: rc = FTS_CORRUPT_VTAB;
! 1432: }
! 1433: }
! 1434: }
! 1435: if( rc==SQLITE_DONE ){
! 1436: rc = SQLITE_OK;
! 1437: }
! 1438:
! 1439: pMod->xClose(pC);
! 1440: if( rc!=SQLITE_OK ) goto offsets_out;
! 1441: }
! 1442:
! 1443: offsets_out:
! 1444: sqlite3_free(sCtx.aTerm);
! 1445: assert( rc!=SQLITE_DONE );
! 1446: sqlite3Fts3SegmentsClose(pTab);
! 1447: if( rc!=SQLITE_OK ){
! 1448: sqlite3_result_error_code(pCtx, rc);
! 1449: sqlite3_free(res.z);
! 1450: }else{
! 1451: sqlite3_result_text(pCtx, res.z, res.n-1, sqlite3_free);
! 1452: }
! 1453: return;
! 1454: }
! 1455:
! 1456: /*
! 1457: ** Implementation of matchinfo() function.
! 1458: */
! 1459: void sqlite3Fts3Matchinfo(
! 1460: sqlite3_context *pContext, /* Function call context */
! 1461: Fts3Cursor *pCsr, /* FTS3 table cursor */
! 1462: const char *zArg /* Second arg to matchinfo() function */
! 1463: ){
! 1464: Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
! 1465: int rc;
! 1466: int i;
! 1467: const char *zFormat;
! 1468:
! 1469: if( zArg ){
! 1470: for(i=0; zArg[i]; i++){
! 1471: char *zErr = 0;
! 1472: if( fts3MatchinfoCheck(pTab, zArg[i], &zErr) ){
! 1473: sqlite3_result_error(pContext, zErr, -1);
! 1474: sqlite3_free(zErr);
! 1475: return;
! 1476: }
! 1477: }
! 1478: zFormat = zArg;
! 1479: }else{
! 1480: zFormat = FTS3_MATCHINFO_DEFAULT;
! 1481: }
! 1482:
! 1483: if( !pCsr->pExpr ){
! 1484: sqlite3_result_blob(pContext, "", 0, SQLITE_STATIC);
! 1485: return;
! 1486: }
! 1487:
! 1488: /* Retrieve matchinfo() data. */
! 1489: rc = fts3GetMatchinfo(pCsr, zFormat);
! 1490: sqlite3Fts3SegmentsClose(pTab);
! 1491:
! 1492: if( rc!=SQLITE_OK ){
! 1493: sqlite3_result_error_code(pContext, rc);
! 1494: }else{
! 1495: int n = pCsr->nMatchinfo * sizeof(u32);
! 1496: sqlite3_result_blob(pContext, pCsr->aMatchinfo, n, SQLITE_TRANSIENT);
! 1497: }
! 1498: }
! 1499:
! 1500: #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to fts3_snippet.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sqlite3 / ext / fts3