ext/fts5/fts5_aux.c

   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   CInstIter iter;                 /* Coalesced Instance Iterator */
 114   int iPos;                       /* Current token offset in zIn[] */
 115   int iRangeStart;                /* First token to include */
 116   int iRangeEnd;                  /* If non-zero, last token to include */
 117   const char *zOpen;              /* Opening highlight */
 118   const char *zClose;             /* Closing highlight */
 119   const char *zIn;                /* Input text */
 120   int nIn;                        /* Size of input text in bytes */
 121   int iOff;                       /* Current offset within zIn[] */
 122   char *zOut;                     /* Output value */
 123 };
 124
 125 /*
 126 ** Append text to the HighlightContext output string - p->zOut. Argument
 127 ** z points to a buffer containing n bytes of text to append. If n is
 128 ** negative, everything up until the first '\0' is appended to the output.
 129 **
 130 ** If *pRc is set to any value other than SQLITE_OK when this function is
 131 ** called, it is a no-op. If an error (i.e. an OOM condition) is encountered,
 132 ** *pRc is set to an error code before returning.
 133 */
 134 static void fts5HighlightAppend(
 135   int *pRc,
 136   HighlightContext *p,
 137   const char *z, int n
 138 ){
 139   if( *pRc==SQLITE_OK && z ){
 140     if( n<0 ) n = (int)strlen(z);
 141     p->zOut = sqlite3_mprintf("%z%.*s", p->zOut, n, z);
 142     if( p->zOut==0 ) *pRc = SQLITE_NOMEM;
 143   }
 144 }
 145
 146 /*
 147 ** Tokenizer callback used by implementation of highlight() function.
 148 */
 149 static int fts5HighlightCb(
 150   void *pContext,                 /* Pointer to HighlightContext object */
 151   int tflags,                     /* Mask of FTS5_TOKEN_* flags */
 152   const char *pToken,             /* Buffer containing token */
 153   int nToken,                     /* Size of token in bytes */
 154   int iStartOff,                  /* Start offset of token */
 155   int iEndOff                     /* End offset of token */
 156 ){
 157   HighlightContext *p = (HighlightContext*)pContext;
 158   int rc = SQLITE_OK;
 159   int iPos;
 160
 161   UNUSED_PARAM2(pToken, nToken);
 162
 163   if( tflags & FTS5_TOKEN_COLOCATED ) return SQLITE_OK;
 164   iPos = p->iPos++;
 165
 166   if( p->iRangeEnd>=0 ){
 167     if( iPos<p->iRangeStart || iPos>p->iRangeEnd ) return SQLITE_OK;
 168     if( p->iRangeStart && iPos==p->iRangeStart ) p->iOff = iStartOff;
 169   }
 170
 171   if( iPos==p->iter.iStart ){
 172     fts5HighlightAppend(&rc, p, &p->zIn[p->iOff], iStartOff - p->iOff);
 173     fts5HighlightAppend(&rc, p, p->zOpen, -1);
 174     p->iOff = iStartOff;
 175   }
 176
 177   if( iPos==p->iter.iEnd ){
 178     if( p->iRangeEnd>=0 && p->iter.iStart<p->iRangeStart ){
 179       fts5HighlightAppend(&rc, p, p->zOpen, -1);
 180     }
 181     fts5HighlightAppend(&rc, p, &p->zIn[p->iOff], iEndOff - p->iOff);
 182     fts5HighlightAppend(&rc, p, p->zClose, -1);
 183     p->iOff = iEndOff;
 184     if( rc==SQLITE_OK ){
 185       rc = fts5CInstIterNext(&p->iter);
 186     }
 187   }
 188
 189   if( p->iRangeEnd>=0 && iPos==p->iRangeEnd ){
 190     fts5HighlightAppend(&rc, p, &p->zIn[p->iOff], iEndOff - p->iOff);
 191     p->iOff = iEndOff;
 192     if( iPos>=p->iter.iStart && iPos<p->iter.iEnd ){
 193       fts5HighlightAppend(&rc, p, p->zClose, -1);
 194     }
 195   }
 196
 197   return rc;
 198 }
 199
 200 /*
 201 ** Implementation of highlight() function.
 202 */
 203 static void fts5HighlightFunction(
 204   const Fts5ExtensionApi *pApi,   /* API offered by current FTS version */
 205   Fts5Context *pFts,              /* First arg to pass to pApi functions */
 206   sqlite3_context *pCtx,          /* Context for returning result/error */
 207   int nVal,                       /* Number of values in apVal[] array */
 208   sqlite3_value **apVal           /* Array of trailing arguments */
 209 ){
 210   HighlightContext ctx;
 211   int rc;
 212   int iCol;
 213
 214   if( nVal!=3 ){
 215     const char *zErr = "wrong number of arguments to function highlight()";
 216     sqlite3_result_error(pCtx, zErr, -1);
 217     return;
 218   }
 219
 220   iCol = sqlite3_value_int(apVal[0]);
 221   memset(&ctx, 0, sizeof(HighlightContext));
 222   ctx.zOpen = (const char*)sqlite3_value_text(apVal[1]);
 223   ctx.zClose = (const char*)sqlite3_value_text(apVal[2]);
 224   ctx.iRangeEnd = -1;
 225   rc = pApi->xColumnText(pFts, iCol, &ctx.zIn, &ctx.nIn);
 226
 227   if( ctx.zIn ){
 228     if( rc==SQLITE_OK ){
 229       rc = fts5CInstIterInit(pApi, pFts, iCol, &ctx.iter);
 230     }
 231
 232     if( rc==SQLITE_OK ){
 233       rc = pApi->xTokenize(pFts, ctx.zIn, ctx.nIn, (void*)&ctx,fts5HighlightCb);
 234     }
 235     fts5HighlightAppend(&rc, &ctx, &ctx.zIn[ctx.iOff], ctx.nIn - ctx.iOff);
 236
 237     if( rc==SQLITE_OK ){
 238       sqlite3_result_text(pCtx, (const char*)ctx.zOut, -1, SQLITE_TRANSIENT);
 239     }
 240     sqlite3_free(ctx.zOut);
 241   }
 242   if( rc!=SQLITE_OK ){
 243     sqlite3_result_error_code(pCtx, rc);
 244   }
 245 }
 246 /*
 247 ** End of highlight() implementation.
 248 **************************************************************************/
 249
 250 /*
 251 ** Context object passed to the fts5SentenceFinderCb() function.
 252 */
 253 typedef struct Fts5SFinder Fts5SFinder;
 254 struct Fts5SFinder {
 255   int iPos;                       /* Current token position */
 256   int nFirstAlloc;                /* Allocated size of aFirst[] */
 257   int nFirst;                     /* Number of entries in aFirst[] */
 258   int *aFirst;                    /* Array of first token in each sentence */
 259   const char *zDoc;               /* Document being tokenized */
 260 };
 261
 262 /*
 263 ** Add an entry to the Fts5SFinder.aFirst[] array. Grow the array if
 264 ** necessary. Return SQLITE_OK if successful, or SQLITE_NOMEM if an
 265 ** error occurs.
 266 */
 267 static int fts5SentenceFinderAdd(Fts5SFinder *p, int iAdd){
 268   if( p->nFirstAlloc==p->nFirst ){
 269     int nNew = p->nFirstAlloc ? p->nFirstAlloc*2 : 64;
 270     int *aNew;
 271
 272     aNew = (int*)sqlite3_realloc64(p->aFirst, nNew*sizeof(int));
 273     if( aNew==0 ) return SQLITE_NOMEM;
 274     p->aFirst = aNew;
 275     p->nFirstAlloc = nNew;
 276   }
 277   p->aFirst[p->nFirst++] = iAdd;
 278   return SQLITE_OK;
 279 }
 280
 281 /*
 282 ** This function is an xTokenize() callback used by the auxiliary snippet()
 283 ** function. Its job is to identify tokens that are the first in a sentence.
 284 ** For each such token, an entry is added to the SFinder.aFirst[] array.
 285 */
 286 static int fts5SentenceFinderCb(
 287   void *pContext,                 /* Pointer to HighlightContext object */
 288   int tflags,                     /* Mask of FTS5_TOKEN_* flags */
 289   const char *pToken,             /* Buffer containing token */
 290   int nToken,                     /* Size of token in bytes */
 291   int iStartOff,                  /* Start offset of token */
 292   int iEndOff                     /* End offset of token */
 293 ){
 294   int rc = SQLITE_OK;
 295
 296   UNUSED_PARAM2(pToken, nToken);
 297   UNUSED_PARAM(iEndOff);
 298
 299   if( (tflags & FTS5_TOKEN_COLOCATED)==0 ){
 300     Fts5SFinder *p = (Fts5SFinder*)pContext;
 301     if( p->iPos>0 ){
 302       int i;
 303       char c = 0;
 304       for(i=iStartOff-1; i>=0; i--){
 305         c = p->zDoc[i];
 306         if( c!=' ' && c!='\t' && c!='\n' && c!='\r' ) break;
 307       }
 308       if( i!=iStartOff-1 && (c=='.' || c==':') ){
 309         rc = fts5SentenceFinderAdd(p, p->iPos);
 310       }
 311     }else{
 312       rc = fts5SentenceFinderAdd(p, 0);
 313     }
 314     p->iPos++;
 315   }
 316   return rc;
 317 }
 318
 319 static int fts5SnippetScore(
 320   const Fts5ExtensionApi *pApi,   /* API offered by current FTS version */
 321   Fts5Context *pFts,              /* First arg to pass to pApi functions */
 322   int nDocsize,                   /* Size of column in tokens */
 323   unsigned char *aSeen,           /* Array with one element per query phrase */
 324   int iCol,                       /* Column to score */
 325   int iPos,                       /* Starting offset to score */
 326   int nToken,                     /* Max tokens per snippet */
 327   int *pnScore,                   /* OUT: Score */
 328   int *piPos                      /* OUT: Adjusted offset */
 329 ){
 330   int rc;
 331   int i;
 332   int ip = 0;
 333   int ic = 0;
 334   int iOff = 0;
 335   int iFirst = -1;
 336   int nInst;
 337   int nScore = 0;
 338   int iLast = 0;
 339   sqlite3_int64 iEnd = (sqlite3_int64)iPos + nToken;
 340
 341   rc = pApi->xInstCount(pFts, &nInst);
 342   for(i=0; i<nInst && rc==SQLITE_OK; i++){
 343     rc = pApi->xInst(pFts, i, &ip, &ic, &iOff);
 344     if( rc==SQLITE_OK && ic==iCol && iOff>=iPos && iOff<iEnd ){
 345       nScore += (aSeen[ip] ? 1 : 1000);
 346       aSeen[ip] = 1;
 347       if( iFirst<0 ) iFirst = iOff;
 348       iLast = iOff + pApi->xPhraseSize(pFts, ip);
 349     }
 350   }
 351
 352   *pnScore = nScore;
 353   if( piPos ){
 354     sqlite3_int64 iAdj = iFirst - (nToken - (iLast-iFirst)) / 2;
 355     if( (iAdj+nToken)>nDocsize ) iAdj = nDocsize - nToken;
 356     if( iAdj<0 ) iAdj = 0;
 357     *piPos = (int)iAdj;
 358   }
 359
 360   return rc;
 361 }
 362
 363 /*
 364 ** Return the value in pVal interpreted as utf-8 text. Except, if pVal
 365 ** contains a NULL value, return a pointer to a static string zero
 366 ** bytes in length instead of a NULL pointer.
 367 */
 368 static const char *fts5ValueToText(sqlite3_value *pVal){
 369   const char *zRet = (const char*)sqlite3_value_text(pVal);
 370   return zRet ? zRet : "";
 371 }
 372
 373 /*
 374 ** Implementation of snippet() function.
 375 */
 376 static void fts5SnippetFunction(
 377   const Fts5ExtensionApi *pApi,   /* API offered by current FTS version */
 378   Fts5Context *pFts,              /* First arg to pass to pApi functions */
 379   sqlite3_context *pCtx,          /* Context for returning result/error */
 380   int nVal,                       /* Number of values in apVal[] array */
 381   sqlite3_value **apVal           /* Array of trailing arguments */
 382 ){
 383   HighlightContext ctx;
 384   int rc = SQLITE_OK;             /* Return code */
 385   int iCol;                       /* 1st argument to snippet() */
 386   const char *zEllips;            /* 4th argument to snippet() */
 387   int nToken;                     /* 5th argument to snippet() */
 388   int nInst = 0;                  /* Number of instance matches this row */
 389   int i;                          /* Used to iterate through instances */
 390   int nPhrase;                    /* Number of phrases in query */
 391   unsigned char *aSeen;           /* Array of "seen instance" flags */
 392   int iBestCol;                   /* Column containing best snippet */
 393   int iBestStart = 0;             /* First token of best snippet */
 394   int nBestScore = 0;             /* Score of best snippet */
 395   int nColSize = 0;               /* Total size of iBestCol in tokens */
 396   Fts5SFinder sFinder;            /* Used to find the beginnings of sentences */
 397   int nCol;
 398
 399   if( nVal!=5 ){
 400     const char *zErr = "wrong number of arguments to function snippet()";
 401     sqlite3_result_error(pCtx, zErr, -1);
 402     return;
 403   }
 404
 405   nCol = pApi->xColumnCount(pFts);
 406   memset(&ctx, 0, sizeof(HighlightContext));
 407   iCol = sqlite3_value_int(apVal[0]);
 408   ctx.zOpen = fts5ValueToText(apVal[1]);
 409   ctx.zClose = fts5ValueToText(apVal[2]);
 410   ctx.iRangeEnd = -1;
 411   zEllips = fts5ValueToText(apVal[3]);
 412   nToken = sqlite3_value_int(apVal[4]);
 413
 414   iBestCol = (iCol>=0 ? iCol : 0);
 415   nPhrase = pApi->xPhraseCount(pFts);
 416   aSeen = sqlite3_malloc(nPhrase);
 417   if( aSeen==0 ){
 418     rc = SQLITE_NOMEM;
 419   }
 420   if( rc==SQLITE_OK ){
 421     rc = pApi->xInstCount(pFts, &nInst);
 422   }
 423
 424   memset(&sFinder, 0, sizeof(Fts5SFinder));
 425   for(i=0; i<nCol; i++){
 426     if( iCol<0 || iCol==i ){
 427       int nDoc;
 428       int nDocsize;
 429       int ii;
 430       sFinder.iPos = 0;
 431       sFinder.nFirst = 0;
 432       rc = pApi->xColumnText(pFts, i, &sFinder.zDoc, &nDoc);
 433       if( rc!=SQLITE_OK ) break;
 434       rc = pApi->xTokenize(pFts,
 435           sFinder.zDoc, nDoc, (void*)&sFinder,fts5SentenceFinderCb
 436       );
 437       if( rc!=SQLITE_OK ) break;
 438       rc = pApi->xColumnSize(pFts, i, &nDocsize);
 439       if( rc!=SQLITE_OK ) break;
 440
 441       for(ii=0; rc==SQLITE_OK && ii<nInst; ii++){
 442         int ip, ic, io;
 443         int iAdj;
 444         int nScore;
 445         int jj;
 446
 447         rc = pApi->xInst(pFts, ii, &ip, &ic, &io);
 448         if( ic!=i ) continue;
 449         if( io>nDocsize ) rc = FTS5_CORRUPT;
 450         if( rc!=SQLITE_OK ) continue;
 451         memset(aSeen, 0, nPhrase);
 452         rc = fts5SnippetScore(pApi, pFts, nDocsize, aSeen, i,
 453             io, nToken, &nScore, &iAdj
 454         );
 455         if( rc==SQLITE_OK && nScore>nBestScore ){
 456           nBestScore = nScore;
 457           iBestCol = i;
 458           iBestStart = iAdj;
 459           nColSize = nDocsize;
 460         }
 461
 462         if( rc==SQLITE_OK && sFinder.nFirst && nDocsize>nToken ){
 463           for(jj=0; jj<(sFinder.nFirst-1); jj++){
 464             if( sFinder.aFirst[jj+1]>io ) break;
 465           }
 466
 467           if( sFinder.aFirst[jj]<io ){
 468             memset(aSeen, 0, nPhrase);
 469             rc = fts5SnippetScore(pApi, pFts, nDocsize, aSeen, i,
 470               sFinder.aFirst[jj], nToken, &nScore, 0
 471             );
 472
 473             nScore += (sFinder.aFirst[jj]==0 ? 120 : 100);
 474             if( rc==SQLITE_OK && nScore>nBestScore ){
 475               nBestScore = nScore;
 476               iBestCol = i;
 477               iBestStart = sFinder.aFirst[jj];
 478               nColSize = nDocsize;
 479             }
 480           }
 481         }
 482       }
 483     }
 484   }
 485
 486   if( rc==SQLITE_OK ){
 487     rc = pApi->xColumnText(pFts, iBestCol, &ctx.zIn, &ctx.nIn);
 488   }
 489   if( rc==SQLITE_OK && nColSize==0 ){
 490     rc = pApi->xColumnSize(pFts, iBestCol, &nColSize);
 491   }
 492   if( ctx.zIn ){
 493     if( rc==SQLITE_OK ){
 494       rc = fts5CInstIterInit(pApi, pFts, iBestCol, &ctx.iter);
 495     }
 496
 497     ctx.iRangeStart = iBestStart;
 498     ctx.iRangeEnd = iBestStart + nToken - 1;
 499
 500     if( iBestStart>0 ){
 501       fts5HighlightAppend(&rc, &ctx, zEllips, -1);
 502     }
 503
 504     /* Advance iterator ctx.iter so that it points to the first coalesced
 505     ** phrase instance at or following position iBestStart. */
 506     while( ctx.iter.iStart>=0 && ctx.iter.iStart<iBestStart && rc==SQLITE_OK ){
 507       rc = fts5CInstIterNext(&ctx.iter);
 508     }
 509
 510     if( rc==SQLITE_OK ){
 511       rc = pApi->xTokenize(pFts, ctx.zIn, ctx.nIn, (void*)&ctx,fts5HighlightCb);
 512     }
 513     if( ctx.iRangeEnd>=(nColSize-1) ){
 514       fts5HighlightAppend(&rc, &ctx, &ctx.zIn[ctx.iOff], ctx.nIn - ctx.iOff);
 515     }else{
 516       fts5HighlightAppend(&rc, &ctx, zEllips, -1);
 517     }
 518   }
 519   if( rc==SQLITE_OK ){
 520     sqlite3_result_text(pCtx, (const char*)ctx.zOut, -1, SQLITE_TRANSIENT);
 521   }else{
 522     sqlite3_result_error_code(pCtx, rc);
 523   }
 524   sqlite3_free(ctx.zOut);
 525   sqlite3_free(aSeen);
 526   sqlite3_free(sFinder.aFirst);
 527 }
 528
 529 /************************************************************************/
 530
 531 /*
 532 ** The first time the bm25() function is called for a query, an instance
 533 ** of the following structure is allocated and populated.
 534 */
 535 typedef struct Fts5Bm25Data Fts5Bm25Data;
 536 struct Fts5Bm25Data {
 537   int nPhrase;                    /* Number of phrases in query */
 538   double avgdl;                   /* Average number of tokens in each row */
 539   double *aIDF;                   /* IDF for each phrase */
 540   double *aFreq;                  /* Array used to calculate phrase freq. */
 541 };
 542
 543 /*
 544 ** Callback used by fts5Bm25GetData() to count the number of rows in the
 545 ** table matched by each individual phrase within the query.
 546 */
 547 static int fts5CountCb(
 548   const Fts5ExtensionApi *pApi,
 549   Fts5Context *pFts,
 550   void *pUserData                 /* Pointer to sqlite3_int64 variable */
 551 ){
 552   sqlite3_int64 *pn = (sqlite3_int64*)pUserData;
 553   UNUSED_PARAM2(pApi, pFts);
 554   (*pn)++;
 555   return SQLITE_OK;
 556 }
 557
 558 /*
 559 ** Set *ppData to point to the Fts5Bm25Data object for the current query.
 560 ** If the object has not already been allocated, allocate and populate it
 561 ** now.
 562 */
 563 static int fts5Bm25GetData(
 564   const Fts5ExtensionApi *pApi,
 565   Fts5Context *pFts,
 566   Fts5Bm25Data **ppData           /* OUT: bm25-data object for this query */
 567 ){
 568   int rc = SQLITE_OK;             /* Return code */
 569   Fts5Bm25Data *p;                /* Object to return */
 570
 571   p = (Fts5Bm25Data*)pApi->xGetAuxdata(pFts, 0);
 572   if( p==0 ){
 573     int nPhrase;                  /* Number of phrases in query */
 574     sqlite3_int64 nRow = 0;       /* Number of rows in table */
 575     sqlite3_int64 nToken = 0;     /* Number of tokens in table */
 576     sqlite3_int64 nByte;          /* Bytes of space to allocate */
 577     int i;
 578
 579     /* Allocate the Fts5Bm25Data object */
 580     nPhrase = pApi->xPhraseCount(pFts);
 581     nByte = sizeof(Fts5Bm25Data) + nPhrase*2*sizeof(double);
 582     p = (Fts5Bm25Data*)sqlite3_malloc64(nByte);
 583     if( p==0 ){
 584       rc = SQLITE_NOMEM;
 585     }else{
 586       memset(p, 0, (size_t)nByte);
 587       p->nPhrase = nPhrase;
 588       p->aIDF = (double*)&p[1];
 589       p->aFreq = &p->aIDF[nPhrase];
 590     }
 591
 592     /* Calculate the average document length for this FTS5 table */
 593     if( rc==SQLITE_OK ) rc = pApi->xRowCount(pFts, &nRow);
 594     assert( rc!=SQLITE_OK || nRow>0 );
 595     if( rc==SQLITE_OK ) rc = pApi->xColumnTotalSize(pFts, -1, &nToken);
 596     if( rc==SQLITE_OK ) p->avgdl = (double)nToken  / (double)nRow;
 597
 598     /* Calculate an IDF for each phrase in the query */
 599     for(i=0; rc==SQLITE_OK && i<nPhrase; i++){
 600       sqlite3_int64 nHit = 0;
 601       rc = pApi->xQueryPhrase(pFts, i, (void*)&nHit, fts5CountCb);
 602       if( rc==SQLITE_OK ){
 603         /* Calculate the IDF (Inverse Document Frequency) for phrase i.
 604         ** This is done using the standard BM25 formula as found on wikipedia:
 605         **
 606         **   IDF = log( (N - nHit + 0.5) / (nHit + 0.5) )
 607         **
 608         ** where "N" is the total number of documents in the set and nHit
 609         ** is the number that contain at least one instance of the phrase
 610         ** under consideration.
 611         **
 612         ** The problem with this is that if (N < 2*nHit), the IDF is
 613         ** negative. Which is undesirable. So the mimimum allowable IDF is
 614         ** (1e-6) - roughly the same as a term that appears in just over
 615         ** half of set of 5,000,000 documents.  */
 616         double idf = log( (nRow - nHit + 0.5) / (nHit + 0.5) );
 617         if( idf<=0.0 ) idf = 1e-6;
 618         p->aIDF[i] = idf;
 619       }
 620     }
 621
 622     if( rc!=SQLITE_OK ){
 623       sqlite3_free(p);
 624     }else{
 625       rc = pApi->xSetAuxdata(pFts, p, sqlite3_free);
 626     }
 627     if( rc!=SQLITE_OK ) p = 0;
 628   }
 629   *ppData = p;
 630   return rc;
 631 }
 632
 633 /*
 634 ** Implementation of bm25() function.
 635 */
 636 static void fts5Bm25Function(
 637   const Fts5ExtensionApi *pApi,   /* API offered by current FTS version */
 638   Fts5Context *pFts,              /* First arg to pass to pApi functions */
 639   sqlite3_context *pCtx,          /* Context for returning result/error */
 640   int nVal,                       /* Number of values in apVal[] array */
 641   sqlite3_value **apVal           /* Array of trailing arguments */
 642 ){
 643   const double k1 = 1.2;          /* Constant "k1" from BM25 formula */
 644   const double b = 0.75;          /* Constant "b" from BM25 formula */
 645   int rc;                         /* Error code */
 646   double score = 0.0;             /* SQL function return value */
 647   Fts5Bm25Data *pData;            /* Values allocated/calculated once only */
 648   int i;                          /* Iterator variable */
 649   int nInst = 0;                  /* Value returned by xInstCount() */
 650   double D = 0.0;                 /* Total number of tokens in row */
 651   double *aFreq = 0;              /* Array of phrase freq. for current row */
 652
 653   /* Calculate the phrase frequency (symbol "f(qi,D)" in the documentation)
 654   ** for each phrase in the query for the current row. */
 655   rc = fts5Bm25GetData(pApi, pFts, &pData);
 656   if( rc==SQLITE_OK ){
 657     aFreq = pData->aFreq;
 658     memset(aFreq, 0, sizeof(double) * pData->nPhrase);
 659     rc = pApi->xInstCount(pFts, &nInst);
 660   }
 661   for(i=0; rc==SQLITE_OK && i<nInst; i++){
 662     int ip; int ic; int io;
 663     rc = pApi->xInst(pFts, i, &ip, &ic, &io);
 664     if( rc==SQLITE_OK ){
 665       double w = (nVal > ic) ? sqlite3_value_double(apVal[ic]) : 1.0;
 666       aFreq[ip] += w;
 667     }
 668   }
 669
 670   /* Figure out the total size of the current row in tokens. */
 671   if( rc==SQLITE_OK ){
 672     int nTok;
 673     rc = pApi->xColumnSize(pFts, -1, &nTok);
 674     D = (double)nTok;
 675   }
 676
 677   /* Determine and return the BM25 score for the current row. Or, if an
 678   ** error has occurred, throw an exception. */
 679   if( rc==SQLITE_OK ){
 680     for(i=0; i<pData->nPhrase; i++){
 681       score += pData->aIDF[i] * (
 682           ( aFreq[i] * (k1 + 1.0) ) /
 683           ( aFreq[i] + k1 * (1 - b + b * D / pData->avgdl) )
 684       );
 685     }
 686     sqlite3_result_double(pCtx, -1.0 * score);
 687   }else{
 688     sqlite3_result_error_code(pCtx, rc);
 689   }
 690 }
 691
 692 int sqlite3Fts5AuxInit(fts5_api *pApi){
 693   struct Builtin {
 694     const char *zFunc;            /* Function name (nul-terminated) */
 695     void *pUserData;              /* User-data pointer */
 696     fts5_extension_function xFunc;/* Callback function */
 697     void (*xDestroy)(void*);      /* Destructor function */
 698   } aBuiltin [] = {
 699     { "snippet",   0, fts5SnippetFunction, 0 },
 700     { "highlight", 0, fts5HighlightFunction, 0 },
 701     { "bm25",      0, fts5Bm25Function,    0 },
 702   };
 703   int rc = SQLITE_OK;             /* Return code */
 704   int i;                          /* To iterate through builtin functions */
 705
 706   for(i=0; rc==SQLITE_OK && i<ArraySize(aBuiltin); i++){
 707     rc = pApi->xCreateFunction(pApi,
 708         aBuiltin[i].zFunc,
 709         aBuiltin[i].pUserData,
 710         aBuiltin[i].xFunc,
 711         aBuiltin[i].xDestroy
 712     );
 713   }
 714
 715   return rc;
 716 }