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