| 1 |
/* |
| 2 |
** 2014 May 31 |
| 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 |
|
| 15 |
#include "fts5Int.h" |
| 16 |
#include <math.h> /* amalgamator: keep */ |
| 17 |
|
| 18 |
/* |
| 19 |
** Object used to iterate through all "coalesced phrase instances" in |
| 20 |
** a single column of the current row. If the phrase instances in the |
| 21 |
** column being considered do not overlap, this object simply iterates |
| 22 |
** through them. Or, if they do overlap (share one or more tokens in |
| 23 |
** common), each set of overlapping instances is treated as a single |
| 24 |
** match. See documentation for the highlight() auxiliary function for |
| 25 |
** details. |
| 26 |
** |
| 27 |
** Usage is: |
| 28 |
** |
| 29 |
** for(rc = fts5CInstIterNext(pApi, pFts, iCol, &iter); |
| 30 |
** (rc==SQLITE_OK && 0==fts5CInstIterEof(&iter); |
| 31 |
** rc = fts5CInstIterNext(&iter) |
| 32 |
** ){ |
| 33 |
** printf("instance starts at %d, ends at %d\n", iter.iStart, iter.iEnd); |
| 34 |
** } |
| 35 |
** |
| 36 |
*/ |
| 37 |
typedef struct CInstIter CInstIter; |
| 38 |
struct CInstIter { |
| 39 |
const Fts5ExtensionApi *pApi; /* API offered by current FTS version */ |
| 40 |
Fts5Context *pFts; /* First arg to pass to pApi functions */ |
| 41 |
int iCol; /* Column to search */ |
| 42 |
int iInst; /* Next phrase instance index */ |
| 43 |
int nInst; /* Total number of phrase instances */ |
| 44 |
|
| 45 |
/* Output variables */ |
| 46 |
int iStart; /* First token in coalesced phrase instance */ |
| 47 |
int iEnd; /* Last token in coalesced phrase instance */ |
| 48 |
}; |
| 49 |
|
| 50 |
/* |
| 51 |
** Advance the iterator to the next coalesced phrase instance. Return |
| 52 |
** an SQLite error code if an error occurs, or SQLITE_OK otherwise. |
| 53 |
*/ |
| 54 |
static int fts5CInstIterNext(CInstIter *pIter){ |
| 55 |
int rc = SQLITE_OK; |
| 56 |
pIter->iStart = -1; |
| 57 |
pIter->iEnd = -1; |
| 58 |
|
| 59 |
while( rc==SQLITE_OK && pIter->iInst<pIter->nInst ){ |
| 60 |
int ip; int ic; int io; |
| 61 |
rc = pIter->pApi->xInst(pIter->pFts, pIter->iInst, &ip, &ic, &io); |
| 62 |
if( rc==SQLITE_OK ){ |
| 63 |
if( ic==pIter->iCol ){ |
| 64 |
int iEnd = io - 1 + pIter->pApi->xPhraseSize(pIter->pFts, ip); |
| 65 |
if( pIter->iStart<0 ){ |
| 66 |
pIter->iStart = io; |
| 67 |
pIter->iEnd = iEnd; |
| 68 |
}else if( io<=pIter->iEnd ){ |
| 69 |
if( iEnd>pIter->iEnd ) pIter->iEnd = iEnd; |
| 70 |
}else{ |
| 71 |
break; |
| 72 |
} |
| 73 |
} |
| 74 |
pIter->iInst++; |
| 75 |
} |
| 76 |
} |
| 77 |
|
| 78 |
return rc; |
| 79 |
} |
| 80 |
|
| 81 |
/* |
| 82 |
** Initialize the iterator object indicated by the final parameter to |
| 83 |
** iterate through coalesced phrase instances in column iCol. |
| 84 |
*/ |
| 85 |
static int fts5CInstIterInit( |
| 86 |
const Fts5ExtensionApi *pApi, |
| 87 |
Fts5Context *pFts, |
| 88 |
int iCol, |
| 89 |
CInstIter *pIter |
| 90 |
){ |
| 91 |
int rc; |
| 92 |
|
| 93 |
memset(pIter, 0, sizeof(CInstIter)); |
| 94 |
pIter->pApi = pApi; |
| 95 |
pIter->pFts = pFts; |
| 96 |
pIter->iCol = iCol; |
| 97 |
rc = pApi->xInstCount(pFts, &pIter->nInst); |
| 98 |
|
| 99 |
if( rc==SQLITE_OK ){ |
| 100 |
rc = fts5CInstIterNext(pIter); |
| 101 |
} |
| 102 |
|
| 103 |
return rc; |
| 104 |
} |
| 105 |
|
| 106 |
|
| 107 |
|
| 108 |
/************************************************************************* |
| 109 |
** Start of highlight() implementation. |
| 110 |
*/ |
| 111 |
typedef struct HighlightContext HighlightContext; |
| 112 |
struct HighlightContext { |
| 113 |
/* Constant parameters to fts5HighlightCb() */ |
| 114 |
int iRangeStart; /* First token to include */ |
| 115 |
int iRangeEnd; /* If non-zero, last token to include */ |
| 116 |
const char *zOpen; /* Opening highlight */ |
| 117 |
const char *zClose; /* Closing highlight */ |
| 118 |
const char *zIn; /* Input text */ |
| 119 |
int nIn; /* Size of input text in bytes */ |
| 120 |
|
| 121 |
/* Variables modified by fts5HighlightCb() */ |
| 122 |
CInstIter iter; /* Coalesced Instance Iterator */ |
| 123 |
int iPos; /* Current token offset in zIn[] */ |
| 124 |
int iOff; /* Have copied up to this offset in zIn[] */ |
| 125 |
int bOpen; /* True if highlight is open */ |
| 126 |
char *zOut; /* Output value */ |
| 127 |
}; |
| 128 |
|
| 129 |
/* |
| 130 |
** Append text to the HighlightContext output string - p->zOut. Argument |
| 131 |
** z points to a buffer containing n bytes of text to append. If n is |
| 132 |
** negative, everything up until the first '\0' is appended to the output. |
| 133 |
** |
| 134 |
** If *pRc is set to any value other than SQLITE_OK when this function is |
| 135 |
** called, it is a no-op. If an error (i.e. an OOM condition) is encountered, |
| 136 |
** *pRc is set to an error code before returning. |
| 137 |
*/ |
| 138 |
static void fts5HighlightAppend( |
| 139 |
int *pRc, |
| 140 |
HighlightContext *p, |
| 141 |
const char *z, int n |
| 142 |
){ |
| 143 |
if( *pRc==SQLITE_OK && z ){ |
| 144 |
if( n<0 ) n = (int)strlen(z); |
| 145 |
p->zOut = sqlite3_mprintf("%z%.*s", p->zOut, n, z); |
| 146 |
if( p->zOut==0 ) *pRc = SQLITE_NOMEM; |
| 147 |
} |
| 148 |
} |
| 149 |
|
| 150 |
/* |
| 151 |
** Tokenizer callback used by implementation of highlight() function. |
| 152 |
*/ |
| 153 |
static int fts5HighlightCb( |
| 154 |
void *pContext, /* Pointer to HighlightContext object */ |
| 155 |
int tflags, /* Mask of FTS5_TOKEN_* flags */ |
| 156 |
const char *pToken, /* Buffer containing token */ |
| 157 |
int nToken, /* Size of token in bytes */ |
| 158 |
int iStartOff, /* Start byte offset of token */ |
| 159 |
int iEndOff /* End byte offset of token */ |
| 160 |
){ |
| 161 |
HighlightContext *p = (HighlightContext*)pContext; |
| 162 |
int rc = SQLITE_OK; |
| 163 |
int iPos; |
| 164 |
|
| 165 |
UNUSED_PARAM2(pToken, nToken); |
| 166 |
|
| 167 |
if( tflags & FTS5_TOKEN_COLOCATED ) return SQLITE_OK; |
| 168 |
iPos = p->iPos++; |
| 169 |
|
| 170 |
if( p->iRangeEnd>=0 ){ |
| 171 |
if( iPos<p->iRangeStart || iPos>p->iRangeEnd ) return SQLITE_OK; |
| 172 |
if( p->iRangeStart && iPos==p->iRangeStart ) p->iOff = iStartOff; |
| 173 |
} |
| 174 |
|
| 175 |
/* If the parenthesis is open, and this token is not part of the current |
| 176 |
** phrase, and the starting byte offset of this token is past the point |
| 177 |
** that has currently been copied into the output buffer, close the |
| 178 |
** parenthesis. */ |
| 179 |
if( p->bOpen |
| 180 |
&& (iPos<=p->iter.iStart || p->iter.iStart<0) |
| 181 |
&& iStartOff>p->iOff |
| 182 |
){ |
| 183 |
fts5HighlightAppend(&rc, p, p->zClose, -1); |
| 184 |
p->bOpen = 0; |
| 185 |
} |
| 186 |
|
| 187 |
/* If this is the start of a new phrase, and the highlight is not open: |
| 188 |
** |
| 189 |
** * copy text from the input up to the start of the phrase, and |
| 190 |
** * open the highlight. |
| 191 |
*/ |
| 192 |
if( iPos==p->iter.iStart && p->bOpen==0 ){ |
| 193 |
fts5HighlightAppend(&rc, p, &p->zIn[p->iOff], iStartOff - p->iOff); |
| 194 |
fts5HighlightAppend(&rc, p, p->zOpen, -1); |
| 195 |
p->iOff = iStartOff; |
| 196 |
p->bOpen = 1; |
| 197 |
} |
| 198 |
|
| 199 |
if( iPos==p->iter.iEnd ){ |
| 200 |
if( p->bOpen==0 ){ |
| 201 |
assert( p->iRangeEnd>=0 ); |
| 202 |
fts5HighlightAppend(&rc, p, p->zOpen, -1); |
| 203 |
p->bOpen = 1; |
| 204 |
} |
| 205 |
fts5HighlightAppend(&rc, p, &p->zIn[p->iOff], iEndOff - p->iOff); |
| 206 |
p->iOff = iEndOff; |
| 207 |
|
| 208 |
if( rc==SQLITE_OK ){ |
| 209 |
rc = fts5CInstIterNext(&p->iter); |
| 210 |
} |
| 211 |
} |
| 212 |
|
| 213 |
if( iPos==p->iRangeEnd ){ |
| 214 |
if( p->bOpen ){ |
| 215 |
if( p->iter.iStart>=0 && iPos>=p->iter.iStart ){ |
| 216 |
fts5HighlightAppend(&rc, p, &p->zIn[p->iOff], iEndOff - p->iOff); |
| 217 |
p->iOff = iEndOff; |
| 218 |
} |
| 219 |
fts5HighlightAppend(&rc, p, p->zClose, -1); |
| 220 |
p->bOpen = 0; |
| 221 |
} |
| 222 |
fts5HighlightAppend(&rc, p, &p->zIn[p->iOff], iEndOff - p->iOff); |
| 223 |
p->iOff = iEndOff; |
| 224 |
} |
| 225 |
|
| 226 |
return rc; |
| 227 |
} |
| 228 |
|
| 229 |
|
| 230 |
/* |
| 231 |
** Implementation of highlight() function. |
| 232 |
*/ |
| 233 |
static void fts5HighlightFunction( |
| 234 |
const Fts5ExtensionApi *pApi, /* API offered by current FTS version */ |
| 235 |
Fts5Context *pFts, /* First arg to pass to pApi functions */ |
| 236 |
sqlite3_context *pCtx, /* Context for returning result/error */ |
| 237 |
int nVal, /* Number of values in apVal[] array */ |
| 238 |
sqlite3_value **apVal /* Array of trailing arguments */ |
| 239 |
){ |
| 240 |
HighlightContext ctx; |
| 241 |
int rc; |
| 242 |
int iCol; |
| 243 |
|
| 244 |
if( nVal!=3 ){ |
| 245 |
const char *zErr = "wrong number of arguments to function highlight()"; |
| 246 |
sqlite3_result_error(pCtx, zErr, -1); |
| 247 |
return; |
| 248 |
} |
| 249 |
|
| 250 |
iCol = sqlite3_value_int(apVal[0]); |
| 251 |
memset(&ctx, 0, sizeof(HighlightContext)); |
| 252 |
ctx.zOpen = (const char*)sqlite3_value_text(apVal[1]); |
| 253 |
ctx.zClose = (const char*)sqlite3_value_text(apVal[2]); |
| 254 |
ctx.iRangeEnd = -1; |
| 255 |
rc = pApi->xColumnText(pFts, iCol, &ctx.zIn, &ctx.nIn); |
| 256 |
if( rc==SQLITE_RANGE ){ |
| 257 |
sqlite3_result_text(pCtx, "", -1, SQLITE_STATIC); |
| 258 |
rc = SQLITE_OK; |
| 259 |
}else if( ctx.zIn ){ |
| 260 |
const char *pLoc = 0; /* Locale of column iCol */ |
| 261 |
int nLoc = 0; /* Size of pLoc in bytes */ |
| 262 |
if( rc==SQLITE_OK ){ |
| 263 |
rc = fts5CInstIterInit(pApi, pFts, iCol, &ctx.iter); |
| 264 |
} |
| 265 |
|
| 266 |
if( rc==SQLITE_OK ){ |
| 267 |
rc = pApi->xColumnLocale(pFts, iCol, &pLoc, &nLoc); |
| 268 |
} |
| 269 |
if( rc==SQLITE_OK ){ |
| 270 |
rc = pApi->xTokenize_v2( |
| 271 |
pFts, ctx.zIn, ctx.nIn, pLoc, nLoc, (void*)&ctx, fts5HighlightCb |
| 272 |
); |
| 273 |
} |
| 274 |
if( ctx.bOpen ){ |
| 275 |
fts5HighlightAppend(&rc, &ctx, ctx.zClose, -1); |
| 276 |
} |
| 277 |
fts5HighlightAppend(&rc, &ctx, &ctx.zIn[ctx.iOff], ctx.nIn - ctx.iOff); |
| 278 |
|
| 279 |
if( rc==SQLITE_OK ){ |
| 280 |
sqlite3_result_text(pCtx, (const char*)ctx.zOut, -1, SQLITE_TRANSIENT); |
| 281 |
} |
| 282 |
sqlite3_free(ctx.zOut); |
| 283 |
} |
| 284 |
if( rc!=SQLITE_OK ){ |
| 285 |
sqlite3_result_error_code(pCtx, rc); |
| 286 |
} |
| 287 |
} |
| 288 |
/* |
| 289 |
** End of highlight() implementation. |
| 290 |
**************************************************************************/ |
| 291 |
|
| 292 |
/* |
| 293 |
** Context object passed to the fts5SentenceFinderCb() function. |
| 294 |
*/ |
| 295 |
typedef struct Fts5SFinder Fts5SFinder; |
| 296 |
struct Fts5SFinder { |
| 297 |
int iPos; /* Current token position */ |
| 298 |
int nFirstAlloc; /* Allocated size of aFirst[] */ |
| 299 |
int nFirst; /* Number of entries in aFirst[] */ |
| 300 |
int *aFirst; /* Array of first token in each sentence */ |
| 301 |
const char *zDoc; /* Document being tokenized */ |
| 302 |
}; |
| 303 |
|
| 304 |
/* |
| 305 |
** Add an entry to the Fts5SFinder.aFirst[] array. Grow the array if |
| 306 |
** necessary. Return SQLITE_OK if successful, or SQLITE_NOMEM if an |
| 307 |
** error occurs. |
| 308 |
*/ |
| 309 |
static int fts5SentenceFinderAdd(Fts5SFinder *p, int iAdd){ |
| 310 |
if( p->nFirstAlloc==p->nFirst ){ |
| 311 |
int nNew = p->nFirstAlloc ? p->nFirstAlloc*2 : 64; |
| 312 |
int *aNew; |
| 313 |
|
| 314 |
aNew = (int*)sqlite3_realloc64(p->aFirst, nNew*sizeof(int)); |
| 315 |
if( aNew==0 ) return SQLITE_NOMEM; |
| 316 |
p->aFirst = aNew; |
| 317 |
p->nFirstAlloc = nNew; |
| 318 |
} |
| 319 |
p->aFirst[p->nFirst++] = iAdd; |
| 320 |
return SQLITE_OK; |
| 321 |
} |
| 322 |
|
| 323 |
/* |
| 324 |
** This function is an xTokenize() callback used by the auxiliary snippet() |
| 325 |
** function. Its job is to identify tokens that are the first in a sentence. |
| 326 |
** For each such token, an entry is added to the SFinder.aFirst[] array. |
| 327 |
*/ |
| 328 |
static int fts5SentenceFinderCb( |
| 329 |
void *pContext, /* Pointer to HighlightContext object */ |
| 330 |
int tflags, /* Mask of FTS5_TOKEN_* flags */ |
| 331 |
const char *pToken, /* Buffer containing token */ |
| 332 |
int nToken, /* Size of token in bytes */ |
| 333 |
int iStartOff, /* Start offset of token */ |
| 334 |
int iEndOff /* End offset of token */ |
| 335 |
){ |
| 336 |
int rc = SQLITE_OK; |
| 337 |
|
| 338 |
UNUSED_PARAM2(pToken, nToken); |
| 339 |
UNUSED_PARAM(iEndOff); |
| 340 |
|
| 341 |
if( (tflags & FTS5_TOKEN_COLOCATED)==0 ){ |
| 342 |
Fts5SFinder *p = (Fts5SFinder*)pContext; |
| 343 |
if( p->iPos>0 ){ |
| 344 |
int i; |
| 345 |
char c = 0; |
| 346 |
for(i=iStartOff-1; i>=0; i--){ |
| 347 |
c = p->zDoc[i]; |
| 348 |
if( c!=' ' && c!='\t' && c!='\n' && c!='\r' ) break; |
| 349 |
} |
| 350 |
if( i!=iStartOff-1 && (c=='.' || c==':') ){ |
| 351 |
rc = fts5SentenceFinderAdd(p, p->iPos); |
| 352 |
} |
| 353 |
}else{ |
| 354 |
rc = fts5SentenceFinderAdd(p, 0); |
| 355 |
} |
| 356 |
p->iPos++; |
| 357 |
} |
| 358 |
return rc; |
| 359 |
} |
| 360 |
|
| 361 |
static int fts5SnippetScore( |
| 362 |
const Fts5ExtensionApi *pApi, /* API offered by current FTS version */ |
| 363 |
Fts5Context *pFts, /* First arg to pass to pApi functions */ |
| 364 |
int nDocsize, /* Size of column in tokens */ |
| 365 |
unsigned char *aSeen, /* Array with one element per query phrase */ |
| 366 |
int iCol, /* Column to score */ |
| 367 |
int iPos, /* Starting offset to score */ |
| 368 |
int nToken, /* Max tokens per snippet */ |
| 369 |
int *pnScore, /* OUT: Score */ |
| 370 |
int *piPos /* OUT: Adjusted offset */ |
| 371 |
){ |
| 372 |
int rc; |
| 373 |
int i; |
| 374 |
int ip = 0; |
| 375 |
int ic = 0; |
| 376 |
int iOff = 0; |
| 377 |
int iFirst = -1; |
| 378 |
int nInst; |
| 379 |
int nScore = 0; |
| 380 |
int iLast = 0; |
| 381 |
sqlite3_int64 iEnd = (sqlite3_int64)iPos + nToken; |
| 382 |
|
| 383 |
rc = pApi->xInstCount(pFts, &nInst); |
| 384 |
for(i=0; i<nInst && rc==SQLITE_OK; i++){ |
| 385 |
rc = pApi->xInst(pFts, i, &ip, &ic, &iOff); |
| 386 |
if( rc==SQLITE_OK && ic==iCol && iOff>=iPos && iOff<iEnd ){ |
| 387 |
nScore += (aSeen[ip] ? 1 : 1000); |
| 388 |
aSeen[ip] = 1; |
| 389 |
if( iFirst<0 ) iFirst = iOff; |
| 390 |
iLast = iOff + pApi->xPhraseSize(pFts, ip); |
| 391 |
} |
| 392 |
} |
| 393 |
|
| 394 |
*pnScore = nScore; |
| 395 |
if( piPos ){ |
| 396 |
sqlite3_int64 iAdj = iFirst - (nToken - (iLast-iFirst)) / 2; |
| 397 |
if( (iAdj+nToken)>nDocsize ) iAdj = nDocsize - nToken; |
| 398 |
if( iAdj<0 ) iAdj = 0; |
| 399 |
*piPos = (int)iAdj; |
| 400 |
} |
| 401 |
|
| 402 |
return rc; |
| 403 |
} |
| 404 |
|
| 405 |
/* |
| 406 |
** Return the value in pVal interpreted as utf-8 text. Except, if pVal |
| 407 |
** contains a NULL value, return a pointer to a static string zero |
| 408 |
** bytes in length instead of a NULL pointer. |
| 409 |
*/ |
| 410 |
static const char *fts5ValueToText(sqlite3_value *pVal){ |
| 411 |
const char *zRet = (const char*)sqlite3_value_text(pVal); |
| 412 |
return zRet ? zRet : ""; |
| 413 |
} |
| 414 |
|
| 415 |
/* |
| 416 |
** Implementation of snippet() function. |
| 417 |
*/ |
| 418 |
static void fts5SnippetFunction( |
| 419 |
const Fts5ExtensionApi *pApi, /* API offered by current FTS version */ |
| 420 |
Fts5Context *pFts, /* First arg to pass to pApi functions */ |
| 421 |
sqlite3_context *pCtx, /* Context for returning result/error */ |
| 422 |
int nVal, /* Number of values in apVal[] array */ |
| 423 |
sqlite3_value **apVal /* Array of trailing arguments */ |
| 424 |
){ |
| 425 |
HighlightContext ctx; |
| 426 |
int rc = SQLITE_OK; /* Return code */ |
| 427 |
int iCol; /* 1st argument to snippet() */ |
| 428 |
const char *zEllips; /* 4th argument to snippet() */ |
| 429 |
int nToken; /* 5th argument to snippet() */ |
| 430 |
int nInst = 0; /* Number of instance matches this row */ |
| 431 |
int i; /* Used to iterate through instances */ |
| 432 |
int nPhrase; /* Number of phrases in query */ |
| 433 |
unsigned char *aSeen; /* Array of "seen instance" flags */ |
| 434 |
int iBestCol; /* Column containing best snippet */ |
| 435 |
int iBestStart = 0; /* First token of best snippet */ |
| 436 |
int nBestScore = 0; /* Score of best snippet */ |
| 437 |
int nColSize = 0; /* Total size of iBestCol in tokens */ |
| 438 |
Fts5SFinder sFinder; /* Used to find the beginnings of sentences */ |
| 439 |
int nCol; |
| 440 |
|
| 441 |
if( nVal!=5 ){ |
| 442 |
const char *zErr = "wrong number of arguments to function snippet()"; |
| 443 |
sqlite3_result_error(pCtx, zErr, -1); |
| 444 |
return; |
| 445 |
} |
| 446 |
|
| 447 |
nCol = pApi->xColumnCount(pFts); |
| 448 |
memset(&ctx, 0, sizeof(HighlightContext)); |
| 449 |
iCol = sqlite3_value_int(apVal[0]); |
| 450 |
ctx.zOpen = fts5ValueToText(apVal[1]); |
| 451 |
ctx.zClose = fts5ValueToText(apVal[2]); |
| 452 |
ctx.iRangeEnd = -1; |
| 453 |
zEllips = fts5ValueToText(apVal[3]); |
| 454 |
nToken = sqlite3_value_int(apVal[4]); |
| 455 |
|
| 456 |
iBestCol = (iCol>=0 ? iCol : 0); |
| 457 |
nPhrase = pApi->xPhraseCount(pFts); |
| 458 |
aSeen = sqlite3_malloc64(nPhrase); |
| 459 |
if( aSeen==0 ){ |
| 460 |
rc = SQLITE_NOMEM; |
| 461 |
} |
| 462 |
if( rc==SQLITE_OK ){ |
| 463 |
rc = pApi->xInstCount(pFts, &nInst); |
| 464 |
} |
| 465 |
|
| 466 |
memset(&sFinder, 0, sizeof(Fts5SFinder)); |
| 467 |
for(i=0; i<nCol; i++){ |
| 468 |
if( iCol<0 || iCol==i ){ |
| 469 |
const char *pLoc = 0; /* Locale of column iCol */ |
| 470 |
int nLoc = 0; /* Size of pLoc in bytes */ |
| 471 |
int nDoc; |
| 472 |
int nDocsize; |
| 473 |
int ii; |
| 474 |
sFinder.iPos = 0; |
| 475 |
sFinder.nFirst = 0; |
| 476 |
rc = pApi->xColumnText(pFts, i, &sFinder.zDoc, &nDoc); |
| 477 |
if( rc!=SQLITE_OK ) break; |
| 478 |
rc = pApi->xColumnLocale(pFts, i, &pLoc, &nLoc); |
| 479 |
if( rc!=SQLITE_OK ) break; |
| 480 |
rc = pApi->xTokenize_v2(pFts, |
| 481 |
sFinder.zDoc, nDoc, pLoc, nLoc, (void*)&sFinder, fts5SentenceFinderCb |
| 482 |
); |
| 483 |
if( rc!=SQLITE_OK ) break; |
| 484 |
rc = pApi->xColumnSize(pFts, i, &nDocsize); |
| 485 |
if( rc!=SQLITE_OK ) break; |
| 486 |
|
| 487 |
for(ii=0; rc==SQLITE_OK && ii<nInst; ii++){ |
| 488 |
int ip, ic, io; |
| 489 |
int iAdj; |
| 490 |
int nScore; |
| 491 |
int jj; |
| 492 |
|
| 493 |
rc = pApi->xInst(pFts, ii, &ip, &ic, &io); |
| 494 |
if( ic!=i ) continue; |
| 495 |
if( io>nDocsize ) rc = FTS5_CORRUPT; |
| 496 |
if( rc!=SQLITE_OK ) continue; |
| 497 |
memset(aSeen, 0, nPhrase); |
| 498 |
rc = fts5SnippetScore(pApi, pFts, nDocsize, aSeen, i, |
| 499 |
io, nToken, &nScore, &iAdj |
| 500 |
); |
| 501 |
if( rc==SQLITE_OK && nScore>nBestScore ){ |
| 502 |
nBestScore = nScore; |
| 503 |
iBestCol = i; |
| 504 |
iBestStart = iAdj; |
| 505 |
nColSize = nDocsize; |
| 506 |
} |
| 507 |
|
| 508 |
if( rc==SQLITE_OK && sFinder.nFirst && nDocsize>nToken ){ |
| 509 |
for(jj=0; jj<(sFinder.nFirst-1); jj++){ |
| 510 |
if( sFinder.aFirst[jj+1]>io ) break; |
| 511 |
} |
| 512 |
|
| 513 |
if( sFinder.aFirst[jj]<io ){ |
| 514 |
memset(aSeen, 0, nPhrase); |
| 515 |
rc = fts5SnippetScore(pApi, pFts, nDocsize, aSeen, i, |
| 516 |
sFinder.aFirst[jj], nToken, &nScore, 0 |
| 517 |
); |
| 518 |
|
| 519 |
nScore += (sFinder.aFirst[jj]==0 ? 120 : 100); |
| 520 |
if( rc==SQLITE_OK && nScore>nBestScore ){ |
| 521 |
nBestScore = nScore; |
| 522 |
iBestCol = i; |
| 523 |
iBestStart = sFinder.aFirst[jj]; |
| 524 |
nColSize = nDocsize; |
| 525 |
} |
| 526 |
} |
| 527 |
} |
| 528 |
} |
| 529 |
} |
| 530 |
} |
| 531 |
|
| 532 |
if( rc==SQLITE_OK ){ |
| 533 |
rc = pApi->xColumnText(pFts, iBestCol, &ctx.zIn, &ctx.nIn); |
| 534 |
} |
| 535 |
if( rc==SQLITE_OK && nColSize==0 ){ |
| 536 |
rc = pApi->xColumnSize(pFts, iBestCol, &nColSize); |
| 537 |
} |
| 538 |
if( ctx.zIn ){ |
| 539 |
const char *pLoc = 0; /* Locale of column iBestCol */ |
| 540 |
int nLoc = 0; /* Bytes in pLoc */ |
| 541 |
|
| 542 |
if( rc==SQLITE_OK ){ |
| 543 |
rc = fts5CInstIterInit(pApi, pFts, iBestCol, &ctx.iter); |
| 544 |
} |
| 545 |
|
| 546 |
ctx.iRangeStart = iBestStart; |
| 547 |
ctx.iRangeEnd = iBestStart + nToken - 1; |
| 548 |
|
| 549 |
if( iBestStart>0 ){ |
| 550 |
fts5HighlightAppend(&rc, &ctx, zEllips, -1); |
| 551 |
} |
| 552 |
|
| 553 |
/* Advance iterator ctx.iter so that it points to the first coalesced |
| 554 |
** phrase instance at or following position iBestStart. */ |
| 555 |
while( ctx.iter.iStart>=0 && ctx.iter.iStart<iBestStart && rc==SQLITE_OK ){ |
| 556 |
rc = fts5CInstIterNext(&ctx.iter); |
| 557 |
} |
| 558 |
|
| 559 |
if( rc==SQLITE_OK ){ |
| 560 |
rc = pApi->xColumnLocale(pFts, iBestCol, &pLoc, &nLoc); |
| 561 |
} |
| 562 |
if( rc==SQLITE_OK ){ |
| 563 |
rc = pApi->xTokenize_v2( |
| 564 |
pFts, ctx.zIn, ctx.nIn, pLoc, nLoc, (void*)&ctx,fts5HighlightCb |
| 565 |
); |
| 566 |
} |
| 567 |
if( ctx.bOpen ){ |
| 568 |
fts5HighlightAppend(&rc, &ctx, ctx.zClose, -1); |
| 569 |
} |
| 570 |
if( ctx.iRangeEnd>=(nColSize-1) ){ |
| 571 |
fts5HighlightAppend(&rc, &ctx, &ctx.zIn[ctx.iOff], ctx.nIn - ctx.iOff); |
| 572 |
}else{ |
| 573 |
fts5HighlightAppend(&rc, &ctx, zEllips, -1); |
| 574 |
} |
| 575 |
} |
| 576 |
if( rc==SQLITE_OK ){ |
| 577 |
sqlite3_result_text(pCtx, (const char*)ctx.zOut, -1, SQLITE_TRANSIENT); |
| 578 |
}else{ |
| 579 |
sqlite3_result_error_code(pCtx, rc); |
| 580 |
} |
| 581 |
sqlite3_free(ctx.zOut); |
| 582 |
sqlite3_free(aSeen); |
| 583 |
sqlite3_free(sFinder.aFirst); |
| 584 |
} |
| 585 |
|
| 586 |
/************************************************************************/ |
| 587 |
|
| 588 |
/* |
| 589 |
** The first time the bm25() function is called for a query, an instance |
| 590 |
** of the following structure is allocated and populated. |
| 591 |
*/ |
| 592 |
typedef struct Fts5Bm25Data Fts5Bm25Data; |
| 593 |
struct Fts5Bm25Data { |
| 594 |
int nPhrase; /* Number of phrases in query */ |
| 595 |
double avgdl; /* Average number of tokens in each row */ |
| 596 |
double *aIDF; /* IDF for each phrase */ |
| 597 |
double *aFreq; /* Array used to calculate phrase freq. */ |
| 598 |
}; |
| 599 |
|
| 600 |
/* |
| 601 |
** Callback used by fts5Bm25GetData() to count the number of rows in the |
| 602 |
** table matched by each individual phrase within the query. |
| 603 |
*/ |
| 604 |
static int fts5CountCb( |
| 605 |
const Fts5ExtensionApi *pApi, |
| 606 |
Fts5Context *pFts, |
| 607 |
void *pUserData /* Pointer to sqlite3_int64 variable */ |
| 608 |
){ |
| 609 |
sqlite3_int64 *pn = (sqlite3_int64*)pUserData; |
| 610 |
UNUSED_PARAM2(pApi, pFts); |
| 611 |
(*pn)++; |
| 612 |
return SQLITE_OK; |
| 613 |
} |
| 614 |
|
| 615 |
/* |
| 616 |
** Set *ppData to point to the Fts5Bm25Data object for the current query. |
| 617 |
** If the object has not already been allocated, allocate and populate it |
| 618 |
** now. |
| 619 |
*/ |
| 620 |
static int fts5Bm25GetData( |
| 621 |
const Fts5ExtensionApi *pApi, |
| 622 |
Fts5Context *pFts, |
| 623 |
Fts5Bm25Data **ppData /* OUT: bm25-data object for this query */ |
| 624 |
){ |
| 625 |
int rc = SQLITE_OK; /* Return code */ |
| 626 |
Fts5Bm25Data *p; /* Object to return */ |
| 627 |
|
| 628 |
p = (Fts5Bm25Data*)pApi->xGetAuxdata(pFts, 0); |
| 629 |
if( p==0 ){ |
| 630 |
int nPhrase; /* Number of phrases in query */ |
| 631 |
sqlite3_int64 nRow = 0; /* Number of rows in table */ |
| 632 |
sqlite3_int64 nToken = 0; /* Number of tokens in table */ |
| 633 |
sqlite3_int64 nByte; /* Bytes of space to allocate */ |
| 634 |
int i; |
| 635 |
|
| 636 |
/* Allocate the Fts5Bm25Data object */ |
| 637 |
nPhrase = pApi->xPhraseCount(pFts); |
| 638 |
nByte = sizeof(Fts5Bm25Data) + nPhrase*2*sizeof(double); |
| 639 |
p = (Fts5Bm25Data*)sqlite3_malloc64(nByte); |
| 640 |
if( p==0 ){ |
| 641 |
rc = SQLITE_NOMEM; |
| 642 |
}else{ |
| 643 |
memset(p, 0, (size_t)nByte); |
| 644 |
p->nPhrase = nPhrase; |
| 645 |
p->aIDF = (double*)&p[1]; |
| 646 |
p->aFreq = &p->aIDF[nPhrase]; |
| 647 |
} |
| 648 |
|
| 649 |
/* Calculate the average document length for this FTS5 table */ |
| 650 |
if( rc==SQLITE_OK ) rc = pApi->xRowCount(pFts, &nRow); |
| 651 |
assert( rc!=SQLITE_OK || nRow>0 ); |
| 652 |
if( rc==SQLITE_OK ) rc = pApi->xColumnTotalSize(pFts, -1, &nToken); |
| 653 |
if( rc==SQLITE_OK ) p->avgdl = (double)nToken / (double)nRow; |
| 654 |
|
| 655 |
/* Calculate an IDF for each phrase in the query */ |
| 656 |
for(i=0; rc==SQLITE_OK && i<nPhrase; i++){ |
| 657 |
sqlite3_int64 nHit = 0; |
| 658 |
rc = pApi->xQueryPhrase(pFts, i, (void*)&nHit, fts5CountCb); |
| 659 |
if( rc==SQLITE_OK ){ |
| 660 |
/* Calculate the IDF (Inverse Document Frequency) for phrase i. |
| 661 |
** This is done using the standard BM25 formula as found on wikipedia: |
| 662 |
** |
| 663 |
** IDF = log( (N - nHit + 0.5) / (nHit + 0.5) ) |
| 664 |
** |
| 665 |
** where "N" is the total number of documents in the set and nHit |
| 666 |
** is the number that contain at least one instance of the phrase |
| 667 |
** under consideration. |
| 668 |
** |
| 669 |
** The problem with this is that if (N < 2*nHit), the IDF is |
| 670 |
** negative. Which is undesirable. So the minimum allowable IDF is |
| 671 |
** (1e-6) - roughly the same as a term that appears in just over |
| 672 |
** half of set of 5,000,000 documents. */ |
| 673 |
double idf = log( (nRow - nHit + 0.5) / (nHit + 0.5) ); |
| 674 |
if( idf<=0.0 ) idf = 1e-6; |
| 675 |
p->aIDF[i] = idf; |
| 676 |
} |
| 677 |
} |
| 678 |
|
| 679 |
if( rc!=SQLITE_OK ){ |
| 680 |
sqlite3_free(p); |
| 681 |
}else{ |
| 682 |
rc = pApi->xSetAuxdata(pFts, p, sqlite3_free); |
| 683 |
} |
| 684 |
if( rc!=SQLITE_OK ) p = 0; |
| 685 |
} |
| 686 |
*ppData = p; |
| 687 |
return rc; |
| 688 |
} |
| 689 |
|
| 690 |
/* |
| 691 |
** Implementation of bm25() function. |
| 692 |
*/ |
| 693 |
static void fts5Bm25Function( |
| 694 |
const Fts5ExtensionApi *pApi, /* API offered by current FTS version */ |
| 695 |
Fts5Context *pFts, /* First arg to pass to pApi functions */ |
| 696 |
sqlite3_context *pCtx, /* Context for returning result/error */ |
| 697 |
int nVal, /* Number of values in apVal[] array */ |
| 698 |
sqlite3_value **apVal /* Array of trailing arguments */ |
| 699 |
){ |
| 700 |
const double k1 = 1.2; /* Constant "k1" from BM25 formula */ |
| 701 |
const double b = 0.75; /* Constant "b" from BM25 formula */ |
| 702 |
int rc; /* Error code */ |
| 703 |
double score = 0.0; /* SQL function return value */ |
| 704 |
Fts5Bm25Data *pData; /* Values allocated/calculated once only */ |
| 705 |
int i; /* Iterator variable */ |
| 706 |
int nInst = 0; /* Value returned by xInstCount() */ |
| 707 |
double D = 0.0; /* Total number of tokens in row */ |
| 708 |
double *aFreq = 0; /* Array of phrase freq. for current row */ |
| 709 |
|
| 710 |
/* Calculate the phrase frequency (symbol "f(qi,D)" in the documentation) |
| 711 |
** for each phrase in the query for the current row. */ |
| 712 |
rc = fts5Bm25GetData(pApi, pFts, &pData); |
| 713 |
if( rc==SQLITE_OK ){ |
| 714 |
aFreq = pData->aFreq; |
| 715 |
memset(aFreq, 0, sizeof(double) * pData->nPhrase); |
| 716 |
rc = pApi->xInstCount(pFts, &nInst); |
| 717 |
} |
| 718 |
for(i=0; rc==SQLITE_OK && i<nInst; i++){ |
| 719 |
int ip; int ic; int io; |
| 720 |
rc = pApi->xInst(pFts, i, &ip, &ic, &io); |
| 721 |
if( rc==SQLITE_OK ){ |
| 722 |
double w = (nVal > ic) ? sqlite3_value_double(apVal[ic]) : 1.0; |
| 723 |
aFreq[ip] += w; |
| 724 |
} |
| 725 |
} |
| 726 |
|
| 727 |
/* Figure out the total size of the current row in tokens. */ |
| 728 |
if( rc==SQLITE_OK ){ |
| 729 |
int nTok; |
| 730 |
rc = pApi->xColumnSize(pFts, -1, &nTok); |
| 731 |
D = (double)nTok; |
| 732 |
} |
| 733 |
|
| 734 |
/* Determine and return the BM25 score for the current row. Or, if an |
| 735 |
** error has occurred, throw an exception. */ |
| 736 |
if( rc==SQLITE_OK ){ |
| 737 |
for(i=0; i<pData->nPhrase; i++){ |
| 738 |
score += pData->aIDF[i] * ( |
| 739 |
( aFreq[i] * (k1 + 1.0) ) / |
| 740 |
( aFreq[i] + k1 * (1 - b + b * D / pData->avgdl) ) |
| 741 |
); |
| 742 |
} |
| 743 |
sqlite3_result_double(pCtx, -1.0 * score); |
| 744 |
}else{ |
| 745 |
sqlite3_result_error_code(pCtx, rc); |
| 746 |
} |
| 747 |
} |
| 748 |
|
| 749 |
/* |
| 750 |
** Implementation of fts5_get_locale() function. |
| 751 |
*/ |
| 752 |
static void fts5GetLocaleFunction( |
| 753 |
const Fts5ExtensionApi *pApi, /* API offered by current FTS version */ |
| 754 |
Fts5Context *pFts, /* First arg to pass to pApi functions */ |
| 755 |
sqlite3_context *pCtx, /* Context for returning result/error */ |
| 756 |
int nVal, /* Number of values in apVal[] array */ |
| 757 |
sqlite3_value **apVal /* Array of trailing arguments */ |
| 758 |
){ |
| 759 |
int iCol = 0; |
| 760 |
int eType = 0; |
| 761 |
int rc = SQLITE_OK; |
| 762 |
const char *zLocale = 0; |
| 763 |
int nLocale = 0; |
| 764 |
|
| 765 |
/* xColumnLocale() must be available */ |
| 766 |
assert( pApi->iVersion>=4 ); |
| 767 |
|
| 768 |
if( nVal!=1 ){ |
| 769 |
const char *z = "wrong number of arguments to function fts5_get_locale()"; |
| 770 |
sqlite3_result_error(pCtx, z, -1); |
| 771 |
return; |
| 772 |
} |
| 773 |
|
| 774 |
eType = sqlite3_value_numeric_type(apVal[0]); |
| 775 |
if( eType!=SQLITE_INTEGER ){ |
| 776 |
const char *z = "non-integer argument passed to function fts5_get_locale()"; |
| 777 |
sqlite3_result_error(pCtx, z, -1); |
| 778 |
return; |
| 779 |
} |
| 780 |
|
| 781 |
iCol = sqlite3_value_int(apVal[0]); |
| 782 |
if( iCol<0 || iCol>=pApi->xColumnCount(pFts) ){ |
| 783 |
sqlite3_result_error_code(pCtx, SQLITE_RANGE); |
| 784 |
return; |
| 785 |
} |
| 786 |
|
| 787 |
rc = pApi->xColumnLocale(pFts, iCol, &zLocale, &nLocale); |
| 788 |
if( rc!=SQLITE_OK ){ |
| 789 |
sqlite3_result_error_code(pCtx, rc); |
| 790 |
return; |
| 791 |
} |
| 792 |
|
| 793 |
sqlite3_result_text(pCtx, zLocale, nLocale, SQLITE_TRANSIENT); |
| 794 |
} |
| 795 |
|
| 796 |
int sqlite3Fts5AuxInit(fts5_api *pApi){ |
| 797 |
struct Builtin { |
| 798 |
const char *zFunc; /* Function name (nul-terminated) */ |
| 799 |
void *pUserData; /* User-data pointer */ |
| 800 |
fts5_extension_function xFunc;/* Callback function */ |
| 801 |
void (*xDestroy)(void*); /* Destructor function */ |
| 802 |
} aBuiltin [] = { |
| 803 |
{ "snippet", 0, fts5SnippetFunction, 0 }, |
| 804 |
{ "highlight", 0, fts5HighlightFunction, 0 }, |
| 805 |
{ "bm25", 0, fts5Bm25Function, 0 }, |
| 806 |
{ "fts5_get_locale", 0, fts5GetLocaleFunction, 0 }, |
| 807 |
}; |
| 808 |
int rc = SQLITE_OK; /* Return code */ |
| 809 |
int i; /* To iterate through builtin functions */ |
| 810 |
|
| 811 |
for(i=0; rc==SQLITE_OK && i<ArraySize(aBuiltin); i++){ |
| 812 |
rc = pApi->xCreateFunction(pApi, |
| 813 |
aBuiltin[i].zFunc, |
| 814 |
aBuiltin[i].pUserData, |
| 815 |
aBuiltin[i].xFunc, |
| 816 |
aBuiltin[i].xDestroy |
| 817 |
); |
| 818 |
} |
| 819 |
|
| 820 |
return rc; |
| 821 |
} |