SQLite

  fts5SnippetIterFree(pIter);
  if( rc!=SQLITE_OK ){
    sqlite3_result_error_code(pCtx, rc);
  }
}


/*
** Context object passed by fts5GatherTotals() to xQueryPhrase callback
** fts5GatherCallback().
*/
struct Fts5GatherCtx {
  int nCol;                       /* Number of columns in FTS table */
  int iPhrase;                    /* Phrase currently under investigation */
  int *anVal;                     /* Array to populate */
};

/*
** Callback used by fts5GatherTotals() with the xQueryPhrase() API.
*/
static int fts5GatherCallback(
  const Fts5ExtensionApi *pApi, 
  Fts5Context *pFts,
  void *pUserData                 /* Pointer to Fts5GatherCtx object */
){
  struct Fts5GatherCtx *p = (struct Fts5GatherCtx*)pUserData;
  int i = 0;
  int iPrev = -1;
  i64 iPos = 0;

  while( 0==pApi->xPoslist(pFts, 0, &i, &iPos) ){
    int iCol = FTS5_POS2COLUMN(iPos);
    if( iCol!=iPrev ){

){
  int rc = SQLITE_OK;
  int *anVal = 0;
  int i;                          /* For iterating through expression phrases */
  int nPhrase = pApi->xPhraseCount(pFts);
  int nCol = pApi->xColumnCount(pFts);
  int nByte = nCol * nPhrase * sizeof(int);
  struct Fts5GatherCtx sCtx;

  sCtx.nCol = nCol;
  anVal = sCtx.anVal = (int*)sqlite3_malloc(nByte);
  if( anVal==0 ){
    rc = SQLITE_NOMEM;
  }else{
    memset(anVal, 0, nByte);

  *panVal = anVal;
  return rc;
}

typedef struct Fts5Bm25Context Fts5Bm25Context;
struct Fts5Bm25Context {
  int nPhrase;                    /* Number of phrases in query */
  int nCol;                       /* Number of columns in FTS table */
  double *aIDF;                   /* Array of IDF values */
  double *aAvg;                   /* Average size of each column in tokens */
};

static int fts5Bm25GetContext(
  const Fts5ExtensionApi *pApi,   /* API offered by current FTS version */
  Fts5Context *pFts,              /* First arg to pass to pApi functions */
  Fts5Bm25Context **pp            /* OUT: Context object */


){


  Fts5Bm25Context *p;
  int rc = SQLITE_OK;


  p = pApi->xGetAuxdata(pFts, 0);
  if( p==0 ){
    int *anVal = 0;
    int ic;                       /* For iterating through columns */
    int ip;                       /* For iterating through phrases */
    i64 nRow;                     /* Total number of rows in table */
    int nPhrase = pApi->xPhraseCount(pFts);
    int nCol = pApi->xColumnCount(pFts);
    int nByte = sizeof(Fts5Bm25Context) 
              + sizeof(double) * nPhrase * nCol       /* aIDF[] */
              + sizeof(double) * nCol;                /* aAvg[] */

    p = (Fts5Bm25Context*)sqlite3_malloc(nByte);
    if( p==0 ){
      rc = SQLITE_NOMEM;
    }else{
      memset(p, 0, nByte);
      p->aAvg = (double*)&p[1];
      p->aIDF = (double*)&p->aAvg[nCol];
      p->nCol = nCol;
      p->nPhrase = nPhrase;
    }

    if( rc==SQLITE_OK ){
      rc = pApi->xRowCount(pFts, &nRow); 
      assert( nRow>0 || rc!=SQLITE_OK );
      if( nRow<2 ) nRow = 2;
    }

    for(ic=0; rc==SQLITE_OK && ic<nCol; ic++){
      i64 nToken = 0;
      rc = pApi->xColumnTotalSize(pFts, ic, &nToken);
      p->aAvg[ic] = (double)nToken / (double)nRow;
    }

    if( rc==SQLITE_OK ){
      rc = fts5GatherTotals(pApi, pFts, &anVal);
    }
    for(ic=0; ic<nCol; ic++){
      for(ip=0; rc==SQLITE_OK && ip<nPhrase; ip++){
        /* Calculate the IDF (Inverse Document Frequency) for phrase ip
        ** in column ic. This is done using the standard BM25 formula as
        ** found on wikipedia:
        **
        **   IDF = log( (N - nHit + 0.5) / (nHit + 0.5) )
        **
        ** where "N" is the total number of documents in the set and nHit
        ** is the number that contain at least one instance of the phrase
        ** under consideration.
        **
        ** The problem with this is that if (N < 2*nHit), the IDF is 
        ** negative. Which is undesirable. So the mimimum allowable IDF is
        ** (1e-6) - roughly the same as a term that appears in just over
        ** half of set of 5,000,000 documents.  */
        int idx = ip * nCol + ic; /* Index in aIDF[] and anVal[] arrays */
        int nHit = anVal[idx];    /* Number of docs matching "ic: ip" */

        p->aIDF[idx] = log( (0.5 + nRow - nHit) / (0.5 + nHit) );
        if( p->aIDF[idx]<=0.0 ) p->aIDF[idx] = 1e-6;
        assert( p->aIDF[idx]>=0.0 );
      }
    }

    sqlite3_free(anVal);
    if( rc==SQLITE_OK ){
      rc = pApi->xSetAuxdata(pFts, p, sqlite3_free);
    }
    if( rc!=SQLITE_OK ){
      sqlite3_free(p);
      p = 0;
    }
  }

  *pp = p;
  return rc;
}

static void fts5Bm25DebugContext(
  int *pRc,                       /* IN/OUT: Return code */
  Fts5Buffer *pBuf,               /* Buffer to populate */
  Fts5Bm25Context *p              /* Context object to decode */
){
  int ip;
  int ic;

  sqlite3Fts5BufferAppendString(pRc, pBuf, "idf ");
  if( p->nPhrase>1 || p->nCol>1 ){
    sqlite3Fts5BufferAppendString(pRc, pBuf, "{");
  }
  for(ip=0; ip<p->nPhrase; ip++){
    if( ip>0 ) sqlite3Fts5BufferAppendString(pRc, pBuf, " ");
    if( p->nCol>1 ) sqlite3Fts5BufferAppendString(pRc, pBuf, "{");
    for(ic=0; ic<p->nCol; ic++){
      if( ic>0 ) sqlite3Fts5BufferAppendString(pRc, pBuf, " ");
      sqlite3Fts5BufferAppendPrintf(pRc, pBuf, "%f", p->aIDF[ip*p->nCol+ic]);
    }
    if( p->nCol>1 ) sqlite3Fts5BufferAppendString(pRc, pBuf, "}");
  }
  if( p->nPhrase>1 || p->nCol>1 ){
    sqlite3Fts5BufferAppendString(pRc, pBuf, "}");
  }

  sqlite3Fts5BufferAppendString(pRc, pBuf, " avgdl ");
  if( p->nCol>1 ) sqlite3Fts5BufferAppendString(pRc, pBuf, "{");
  for(ic=0; ic<p->nCol; ic++){
    if( ic>0 ) sqlite3Fts5BufferAppendString(pRc, pBuf, " ");
    sqlite3Fts5BufferAppendPrintf(pRc, pBuf, "%f", p->aAvg[ic]);
  }
  if( p->nCol>1 ) sqlite3Fts5BufferAppendString(pRc, pBuf, "}");
}

static void fts5Bm25DebugRow(
  int *pRc, 
  Fts5Buffer *pBuf, 
  Fts5Bm25Context *p, 
  const Fts5ExtensionApi *pApi, 
  Fts5Context *pFts
){
}

static void fts5Bm25Function(
  const Fts5ExtensionApi *pApi,   /* API offered by current FTS version */
  Fts5Context *pFts,              /* First arg to pass to pApi functions */
  sqlite3_context *pCtx,          /* Context for returning result/error */
  int nVal,                       /* Number of values in apVal[] array */
  sqlite3_value **apVal           /* Array of trailing arguments */
){
  const double k1 = 1.2;
  const double B = 0.75;
  int rc = SQLITE_OK;
  Fts5Bm25Context *p;

  rc = fts5Bm25GetContext(pApi, pFts, &p);

  if( rc==SQLITE_OK ){
    /* If the bDebug flag is set, instead of returning a numeric rank, this
    ** function returns a text value showing how the rank is calculated. */
    Fts5Buffer debug;
    int bDebug = (pApi->xUserData(pFts)!=0);
    memset(&debug, 0, sizeof(Fts5Buffer));

    int ip;
    double score = 0.0;

    if( bDebug ){
      fts5Bm25DebugContext(&rc, &debug, p);
      fts5Bm25DebugRow(&rc, &debug, p, pApi, pFts);
    }

    for(ip=0; rc==SQLITE_OK && ip<p->nPhrase; ip++){
      int iPrev = 0;
      int nHit = 0;
      int i = 0;
      i64 iPos = 0;

      while( rc==SQLITE_OK ){
        int bDone = pApi->xPoslist(pFts, ip, &i, &iPos);
        int iCol = FTS5_POS2COLUMN(iPos);
        if( (iCol!=iPrev || bDone) && nHit>0 ){
          int sz = 0;
          int idx = ip * p->nCol + iPrev;
          double bm25;
          rc = pApi->xColumnSize(pFts, iPrev, &sz);

          bm25 = (p->aIDF[idx] * nHit * (k1+1.0)) /
            (nHit + k1 * (1.0 - B + B * sz / p->aAvg[iPrev]));


          score = score + bm25;
          nHit = 0;
        }
        if( bDone ) break;
        nHit++;
        iPrev = iCol;
      }
    }

    if( rc==SQLITE_OK ){
      if( bDebug ){
        sqlite3_result_text(pCtx, (const char*)debug.p, -1, SQLITE_TRANSIENT);
      }else{
        sqlite3_result_double(pCtx, score);
      }
    }
    sqlite3_free(debug.p);
  }

  if( rc!=SQLITE_OK ){
    sqlite3_result_error_code(pCtx, rc);
  }
}

  struct Builtin {
    const char *zFunc;            /* Function name (nul-terminated) */
    void *pUserData;              /* User-data pointer */
    fts5_extension_function xFunc;/* Callback function */
    void (*xDestroy)(void*);      /* Destructor function */
  } aBuiltin [] = {
    { "bm25",      0, fts5Bm25Function,    0 },
    { "bm25debug", (void*)1, fts5Bm25Function,    0 },
    { "snippet",   0, fts5SnippetFunction, 0 },
    { "fts5_test", 0, fts5TestFunction,    0 },
  };

  int rc = SQLITE_OK;             /* Return code */
  int i;                          /* To iterate through builtin functions */

  } [list $res]
}

do_execsql_test 7.4 {
  SELECT fts5_test(t7, 'rowcount') FROM t7 WHERE t7 MATCH 'a';
} {5 5 5 5}

#do_execsql_test 7.4 {
#  SELECT rowid, bm25debug(t7) FROM t7 WHERE t7 MATCH 'a';
#} {5 5 5 5}
#

#-------------------------------------------------------------------------
#
do_test 8.1 {
  execsql { CREATE VIRTUAL TABLE t8 USING fts5(x, y) }
  foreach {rowid x y} {
     0 {A o}   {o o o C o o o o o o o o}
     1 {o o B} {o o o C C o o o o o o o}
     2 {A o o} {o o o o D D o o o o o o}
     3 {o B}   {o o o o o D o o o o o o}
     4 {E o G} {H o o o o o o o o o o o}
     5 {F o G} {I o J o o o o o o o o o}
     6 {E o o} {H o J o o o o o o o o o}
     7 {o o o} {o o o o o o o o o o o o}
     9 {o o o} {o o o o o o o o o o o o}
  } {
    execsql { INSERT INTO t8(rowid, x, y) VALUES($rowid, $x, $y) }
  }
} {}

foreach {tn q res} {
  1 {a} {0 2}
  2 {b} {3 1}
  3 {c} {1 0}
  4 {d} {2 3}
  5 {g AND (e OR f)} {5 4}
  6 {j AND (h OR i)} {5 6}
} {
  do_execsql_test 8.2.$tn {
    SELECT rowid FROM t8 WHERE t8 MATCH $q ORDER BY bm25(t8) DESC;
  } $res
}


finish_test