Debian Codegraph @

ext/fts5/fts5_aux.c

raw
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 }