SQLite4  Check-in [f3ac136843]

*/

#include "sqliteInt.h"
#include "vdbeInt.h"

/* 
** Stream numbers must be lower than this.
**
** For optimization purposes, it is assumed that a given tokenizer uses
** a set of contiguous stream numbers starting with 0. And that most
** tokens belong to stream 0.
**
** The hard limit is 63 (due to the format of "row size" records).
*/
#define SQLITE4_FTS5_NSTREAM 32

/*
** Records stored within the index:
**
** Row size record:
**   There is one "row size" record in the index for each row in the
**   indexed table. The "row size" record contains the number of tokens

**
**   The data for this record is a series of varint values. The first 
**   varint is the total number of rows in the table. The subsequent
**   varints make up a "row size" record containing the total number of
**   tokens for each S/C combination in all rows of the table.
**
** FTS index records:

**   The FTS index records implement the following mapping:
**
**       (token, document-pk) -> (list of instances)
**
**   The key for each index record is in the same format as the keys for
**   regular text indexes. An 0x24 byte, followed by the utf-8 representation
**   of the token, followed by 0x00, followed by the PK blob for the table
**   row.
**
**   TODO: Describe value format.
*/

/*
** Default distance value for NEAR operators.
*/
#define FTS5_DEFAULT_NEAR 10

typedef struct Fts5Expr Fts5Expr;
typedef struct Fts5ExprNode Fts5ExprNode;
typedef struct Fts5List Fts5List;
typedef struct Fts5Parser Fts5Parser;
typedef struct Fts5ParserToken Fts5ParserToken;
typedef struct Fts5Phrase Fts5Phrase;
typedef struct Fts5Prefix Fts5Prefix;
typedef struct Fts5Size Fts5Size;
typedef struct Fts5Str Fts5Str;
typedef struct Fts5Token Fts5Token;


struct Fts5ParserToken {
  int eType;                      /* Token type */
  int n;                          /* Size of z[] in bytes */

  char *zExpr;                    /* Full text of MATCH expression */
  KVByteArray *aKey;              /* Buffer for primary key */
  int nKeyAlloc;                  /* Bytes allocated at aKey[] */

  KVCursor *pCsr;                 /* Cursor used to retrive values */
  Mem *aMem;                      /* Array of column values */

  Fts5Size *pSz;                  /* Local size data */
  Fts5Size *pGlobal;              /* Global size data */
  i64 nGlobal;                    /* Total number of rows in table */
  int *anRow;

#if 1
  i64 *aGlobal;

  /* Size of each column of current row (in tokens). */
  int bSzValid;
  int *aSz;
#endif
};

/*
** A deserialized 'size record' (see above).
*/
struct Fts5Size {
  int nCol;                       /* Number of columns in indexed table */
  int nStream;                    /* Number of streams */
  i64 *aSz;                       /* Token count for each C/S */
};

/*
** This type is used when reading (decoding) an instance-list.
*/
typedef struct InstanceList InstanceList;
struct InstanceList {
  u8 *aList;
  int nList;
  int iList;

  /* The current entry */
  int iCol;
  int iStream;
  int iOff;
};

/*
** Return true for EOF, or false if the next entry is valid.
*/
static int fts5InstanceListNext(InstanceList *p){
  int i = p->iList;
  int bRet = 1;
  
  while( bRet && i<p->nList ){
    u32 iVal;
    i += getVarint32(&p->aList[i], iVal);
    if( (iVal & 0x03)==0x01 ){
      p->iCol = (iVal>>2);
      p->iOff = 0;
    }
    else if( (iVal & 0x03)==0x03 ){
      p->iStream = (iVal>>2);
    }
    else{
      p->iOff += (iVal>>1);
      bRet = 0;
    }
  }
  if( bRet ){

static int fts5InstanceListEof(InstanceList *p){
  return (p->aList==0);
}

static void fts5InstanceListAppend(
  InstanceList *p,                /* Instance list to append to */
  int iCol,                       /* Column of new entry */
  int iStream,                    /* Weight of new entry */
  int iOff                        /* Offset of new entry */
){
  assert( iCol>=p->iCol );
  assert( iCol>p->iCol || iOff>=p->iOff );

  if( iCol!=p->iCol ){
    p->iList += putVarint32(&p->aList[p->iList], (iCol<<2)|0x01);
    p->iCol = iCol;
    p->iOff = 0;
  }

  if( iStream!=p->iStream ){
    p->iList += putVarint32(&p->aList[p->iList], (iStream<<2)|0x03);
    p->iStream = iStream;
  }

  p->iList += putVarint32(&p->aList[p->iList], (iOff-p->iOff)<<1);
  p->iOff = iOff;

  assert( p->iList<=p->nList );
}

}

/*
** Callback for fts5CountTokens().
*/
static int fts5CountTokensCb(
  void *pCtx, 
  int iStream, 
  int iOff, 
  const char *z, int n,
  int iSrc, int nSrc
){
  (*((int *)pCtx))++;
  return 0;
}

struct AppendTokensCtx {
  Fts5Parser *pParse;
  Fts5Str *pStr;
};

static int fts5AppendTokensCb(
  void *pCtx, 
  int iStream, 
  int iOff, 
  const char *z, int n, 
  int iSrc, int nSrc
){
  struct AppendTokensCtx *p = (struct AppendTokensCtx *)pCtx;
  Fts5Parser *pParse = p->pParse;
  Fts5Token *pToken;

** sqlite4DbRealloc().
*/
typedef struct TokenizeCtx TokenizeCtx;
typedef struct TokenizeTerm TokenizeTerm;
struct TokenizeCtx {
  int rc;
  int iCol;
  int nCol;                       /* Number of columns in table */
  sqlite4 *db;
  int nMax;
  i64 *aSz;                       /* Number of tokens in each column/stream */
  int nStream;                    /* Number of streams in document */
  Hash hash;
};
struct TokenizeTerm {
  int iStream;                    /* Weight of previous entry */
  int iCol;                       /* Column containing previous entry */
  int iOff;                       /* Token offset of previous entry */
  int nToken;                     /* Size of token in bytes */
  int nData;                      /* Bytes of data in value */
  int nAlloc;                     /* Bytes of data allocated */
};

  a = &(((unsigned char *)&pTerm[1])[pTerm->nToken+pTerm->nData]);
  pTerm->nData += putVarint32(a, iVal);
  return pTerm;
}

static int fts5TokenizeCb(
  void *pCtx, 
  int iStream, 
  int iOff,
  const char *zToken, 
  int nToken, 
  int iSrc, 
  int nSrc
){
  TokenizeCtx *p = (TokenizeCtx *)pCtx;
  sqlite4 *db = p->db;
  TokenizeTerm *pTerm = 0;
  TokenizeTerm *pOrig = 0;

  /* TODO: Error here if iStream is out of range */

  if( nToken>p->nMax ) p->nMax = nToken;

  if( iStream>=p->nStream ){
    int nOld = p->nStream;
    int nNew = 4;
    while( nNew<=iStream ) nNew = nNew*2;
    p->aSz = (i64*)sqlite4DbReallocOrFree(db, p->aSz, nNew*p->nCol*sizeof(i64));
    if( p->aSz==0 ) goto tokenize_cb_out;
    memset(&p->aSz[p->nStream * p->nCol], 0, (nNew-nOld)*p->nCol*sizeof(i64));
  }
  p->aSz[iStream*p->nCol + p->iCol]++;

  pTerm = (TokenizeTerm *)sqlite4HashFind(&p->hash, zToken, nToken);
  if( pTerm==0 ){
    /* Size the initial allocation so that it fits in the lookaside buffer */
    int nAlloc = sizeof(TokenizeTerm) + nToken + 32;

    pTerm = sqlite4DbMallocZero(p->db, nAlloc);

        pTerm = 0;
      }
      if( pTerm==0 ) goto tokenize_cb_out;
    }
  }
  pOrig = pTerm;

  if( iStream!=pTerm->iStream ){
    pTerm = fts5TokenizeAppendInt(p, pTerm, (iStream << 2) | 0x00000003);
    if( !pTerm ) goto tokenize_cb_out;
    pTerm->iStream = iStream;
  }

  if( pTerm && p->iCol!=pTerm->iCol ){
    pTerm = fts5TokenizeAppendInt(p, pTerm, (p->iCol << 2) | 0x00000001);
    if( !pTerm ) goto tokenize_cb_out;
    pTerm->iCol = p->iCol;
    pTerm->iOff = 0;

    p->rc = SQLITE4_NOMEM;
    return 1;
  }

  return 0;
}

static int fts5LoadSizeRecord(
  sqlite4 *db,                    /* Database handle */
  u8 *aKey, int nKey,             /* KVStore key */
  int nMinStream,                 /* Space for at least this many streams */
  Fts5Info *pInfo,                /* Info record */
  i64 *pnRow,                     /* non-NULL when reading global record */
  Fts5Size **ppSz                 /* OUT: Loaded size record */
){
  Fts5Size *pSz = 0;              /* Size object */
  KVCursor *pCsr = 0;             /* Cursor used to read global record */
  int rc;



  rc = sqlite4KVStoreOpenCursor(db->aDb[pInfo->iDb].pKV, &pCsr);
  if( rc==SQLITE4_OK ){
    rc = sqlite4KVCursorSeek(pCsr, aKey, nKey, 0);
    if( rc==SQLITE4_NOTFOUND ){
      rc = SQLITE4_CORRUPT_BKPT;

    }else if( rc==SQLITE4_OK ){
      const u8 *aData = 0;
      int nData = 0;
      rc = sqlite4KVCursorData(pCsr, 0, -1, &aData, &nData);
      if( rc==SQLITE4_OK ){
        int iOff = 0;
        int nStream = 0;
        int nAlloc;

        /* If pnRow is not NULL, then this is the global record. Read the
        ** number of documents in the table from the start of the record. */
        if( pnRow ){
          iOff += sqlite4GetVarint(&aData[iOff], (u64 *)pnRow);
        }
        iOff += getVarint32(&aData[iOff], nStream);
        nAlloc = (nStream < nMinStream ? nMinStream : nStream);

        pSz = sqlite4DbMallocZero(db, 
            sizeof(Fts5Size) + sizeof(i64) * pInfo->nCol * nAlloc
        );
        if( pSz==0 ){
          rc = SQLITE4_NOMEM;
        }else{
          int iCol = 0;
          pSz->nCol = pInfo->nCol;
          pSz->nStream = nAlloc;
          while( iOff<nData ){
            int i;
            i64 *aSz = &pSz->aSz[iCol*nAlloc];
            for(i=0; i<nStream; i++){
              iOff += sqlite4GetVarint(&aData[iOff], (u64*)&aSz[i]);
            }
            iCol++;
          }
        }
      }
    }
    sqlite4KVCursorClose(pCsr);
  }

  *ppSz = pSz;
  return rc;
}

static int fts5StoreSizeRecord(
  KVStore *p,
  u8 *aKey, int nKey,
  Fts5Size *pSz, 
  i64 nRow, 
  u8 *a                           /* Space to serialize record in */
){
  int iOff = 0;
  int iCol;

  if( nRow>=0 ){
    iOff += sqlite4PutVarint(&a[iOff], nRow);
  }
  iOff += sqlite4PutVarint(&a[iOff], pSz->nStream);
  for(iCol=0; iCol<pSz->nCol; iCol++){
    int i;
    for(i=0; i<pSz->nStream; i++){
      iOff += sqlite4PutVarint(&a[iOff], pSz->aSz[iCol*pSz->nCol+i]);
    }
  }

  return sqlite4KVStoreReplace(p, aKey, nKey, a, iOff);
}

static int fts5CsrLoadGlobal(Fts5Cursor *pCsr){
  int rc = SQLITE4_OK;
  if( pCsr->pGlobal==0 ){
    int nKey;

    u8 aKey[10];
    nKey = putVarint32(aKey, pCsr->pInfo->iRoot);
    aKey[nKey++] = 0x00;

    rc = fts5LoadSizeRecord(

        pCsr->db, aKey, nKey, 0, pCsr->pInfo, &pCsr->nGlobal, &pCsr->pGlobal
    );
  }
  return rc;
}

static int fts5CsrLoadSz(Fts5Cursor *pCsr){
  int rc = SQLITE4_OK;
  if( pCsr->pSz==0 ){
    sqlite4 *db = pCsr->db;
    Fts5Info *pInfo = pCsr->pInfo;


    u8 *aKey;
    int nKey = 0;
    int nPk = pCsr->pExpr->pRoot->nPk;


    aKey = (u8 *)sqlite4DbMallocZero(db, 10 + nPk);
    if( !aKey ) return SQLITE4_NOMEM;

    nKey = putVarint32(aKey, pInfo->iRoot);
    aKey[nKey++] = 0x00;
    memcpy(&aKey[nKey], pCsr->pExpr->pRoot->aPk, nPk);
    nKey += nPk;



    rc = fts5LoadSizeRecord(pCsr->db, aKey, nKey, 0, pInfo, 0, &pCsr->pSz);















    sqlite4DbFree(db, aKey);
  }

  return rc;
}


/*

  int bDel,                       /* True for a delete, false for insert */
  char **pzErr                    /* OUT: Error message */
){
  int i;
  int rc = SQLITE4_OK;
  KVStore *pStore;
  TokenizeCtx sCtx;


  int nTnum = 0;
  u32 dummy = 0;

  u8 *aSpace = 0;
  int nSpace = 0;

  const u8 *pPK;
  int nPK;
  HashElem *pElem;

  pStore = db->aDb[pInfo->iDb].pKV;

  memset(&sCtx, 0, sizeof(sCtx));
  sCtx.db = db;
  sCtx.nCol = pInfo->nCol;
  sqlite4HashInit(db->pEnv, &sCtx.hash, 1);

  pPK = (const u8 *)sqlite4_value_blob(pKey);
  nPK = sqlite4_value_bytes(pKey);
  
  nTnum = getVarint32(pPK, dummy);
  nPK -= nTnum;
  pPK += nTnum;




  for(i=0; rc==SQLITE4_OK && i<pInfo->nCol; i++){
    sqlite4_value *pArg = (sqlite4_value *)(&aArg[i]);
    if( pArg->flags & MEM_Str ){
      const char *zText;
      int nText;

      zText = (const char *)sqlite4_value_text(pArg);
      nText = sqlite4_value_bytes(pArg); 
      sCtx.iCol = i;
      rc = pInfo->pTokenizer->xTokenize(
          &sCtx, pInfo->p, zText, nText, fts5TokenizeCb
      );
    }
  }

  /* Allocate enough space to serialize all the stuff that needs to
  ** be inserted into the database. Specifically:
  **
  **   * Space for index record keys,
  **   * space for the size record and key for this document, and
  **   * space for the updated global size record for the document set.
  **
  ** To make it easier, the below allocates enough space to simultaneously
  ** store the largest index record key and the largest possible global
  ** size record.
  */
  nSpace = (sqlite4VarintLen(pInfo->iRoot) + 2 + sCtx.nMax + nPK) + 
           (9 * (2 + pInfo->nCol * sCtx.nStream));
  aSpace = sqlite4DbMallocRaw(db, nSpace);
  if( aSpace==0 ) rc = SQLITE4_NOMEM;

  for(pElem=sqliteHashFirst(&sCtx.hash); pElem; pElem=sqliteHashNext(pElem)){
    TokenizeTerm *pTerm = (TokenizeTerm *)sqliteHashData(pElem);
    if( rc==SQLITE4_OK ){
      int nToken = sqliteHashKeysize(pElem);
      char *zToken = (char *)sqliteHashKey(pElem);
      u8 *aKey = aSpace;
      int nKey;

      nKey = putVarint32(aKey, pInfo->iRoot);
      aKey[nKey++] = 0x24;
      memcpy(&aKey[nKey], zToken, nToken);
      nKey += nToken;
      aKey[nKey++] = 0x00;
      memcpy(&aKey[nKey], pPK, nPK);

        aData += pTerm->nToken;
        rc = sqlite4KVStoreReplace(pStore, aKey, nKey, aData, pTerm->nData);
      }
    }
    sqlite4DbFree(db, pTerm);
  }

  /* Write the size record into the db */
  if( rc==SQLITE4_OK ){
    u8 *aKey = aSpace;
    int nKey;

    nKey = putVarint32(aKey, pInfo->iRoot);
    aKey[nKey++] = 0x00;
    memcpy(&aKey[nKey], pPK, nPK);
    nKey += nPK;

    if( bDel==0 ){
      Fts5Size sSz;
      sSz.nCol = pInfo->nCol;
      sSz.nStream = sCtx.nStream;
      sSz.aSz = sCtx.aSz;
      rc = fts5StoreSizeRecord(pStore, aKey, nKey, &sSz, -1, &aKey[nKey]);
    }else{





      rc = sqlite4KVStoreReplace(pStore, aKey, nKey, 0, -1);
    }
  }

  /* Update the global record */
  if( rc==SQLITE4_OK ){
    Fts5Size *pSz;                /* Deserialized global size record */
    i64 nRow;                     /* Number of rows in indexed table */
    u8 *aKey = aSpace;            /* Space to format the global record key */
    int nKey;                     /* Size of global record key in bytes */

    nKey = putVarint32(aKey, pInfo->iRoot);
    aKey[nKey++] = 0x00;
    rc = fts5LoadSizeRecord(db, aKey, nKey, sCtx.nStream, pInfo, &nRow, &pSz);
    assert( rc!=SQLITE4_OK || pSz->nStream>=sCtx.nStream );


    if( rc==SQLITE4_OK ){

      int iCol;
      for(iCol=0; iCol<pSz->nCol; iCol++){
        int iStr;

        i64 *aIn = &sCtx.aSz[iCol * sCtx.nStream];
        i64 *aOut = &pSz->aSz[iCol * pSz->nStream];
        for(iStr=0; iStr<sCtx.nStream; iStr++){
          aOut[iStr] += (aIn[iStr] * (bDel?-1:1));
        }




      }
      nRow += (bDel?-1:1);
      rc = fts5StoreSizeRecord(pStore, aKey, nKey, pSz, nRow, &aKey[nKey]);
    }


    sqlite4DbFree(db, pSz);
  }
  
  sqlite4DbFree(db, aSpace);
  sqlite4DbFree(db, sCtx.aSz);
  sqlite4HashClear(&sCtx.hash);
  return rc;
}

static Fts5Info *fts5InfoCreate(Parse *pParse, Index *pIdx, int bCol){
  sqlite4 *db = pParse->db;

**   * the weight assigned to the instance,
**   * the column number, and
**   * the term offset.
*/
static i64 fts5TermInstanceCksum(
  const u8 *aTerm, int nTerm,
  const u8 *aPk, int nPk,
  int iStream,
  int iCol,
  int iOff
){
  int i;
  i64 cksum = 0;

  /* Add the term to the checksum */
  for(i=0; i<nTerm; i++){
    cksum += (cksum << 3) + aTerm[i];
  }

  /* Add the primary key blob to the checksum */
  for(i=0; i<nPk; i++){
    cksum += (cksum << 3) + aPk[i];
  }

  /* Add the weight, column number and offset (in that order) to the checksum */
  cksum += (cksum << 3) + iStream;
  cksum += (cksum << 3) + iCol;
  cksum += (cksum << 3) + iOff;

  return cksum;
}

  nToken = sqlite4Strlen30((const char *)aToken);
  aPk = &aToken[nToken+1];
  nPk = (&aKey[nKey] - aPk);

  fts5InstanceListInit((u8 *)aVal, nVal, &sList);
  while( 0==fts5InstanceListNext(&sList) ){
    i64 v = fts5TermInstanceCksum(
        aPk, nPk, aToken, nToken, sList.iStream, sList.iCol, sList.iOff
    );
    cksum = cksum ^ v;
  }

  *piCksum = cksum;
  return SQLITE4_OK;
}

typedef struct CksumCtx CksumCtx;
struct CksumCtx {
  const u8 *pPK;
  int nPK;
  int iCol;
  i64 cksum;
};

static int fts5CksumCb(
  void *pCtx, 
  int iStream, 
  int iOff,
  const char *zToken, 
  int nToken, 
  int iSrc, 
  int nSrc
){
  CksumCtx *p = (CksumCtx *)pCtx;
  i64 cksum;

  cksum = fts5TermInstanceCksum(p->pPK, p->nPK, 
      (const u8 *)zToken, nToken, iStream, p->iCol, iOff
  );

  p->cksum = (p->cksum ^ cksum);
  return 0;
}

int sqlite4Fts5RowCksum(

      fts5InstanceListNext(&in2);
    }else if( in1.iCol<in2.iCol || (in1.iCol==in2.iCol && in1.iOff<in2.iOff) ){
      pAdv = &in1;
    }else{
      pAdv = &in2;
    }

    fts5InstanceListAppend(&out, pAdv->iCol, pAdv->iStream, pAdv->iOff);
    fts5InstanceListNext(pAdv);
  }

  if( bFree ){
    sqlite4DbFree(db, p1->aData);
    sqlite4DbFree(db, p2->aData);
  }

  while( rc==SQLITE4_OK && bEof==0 ){
    for(i=1; i<pStr->nToken; i++){
      int bMatch = fts5TokenAdvanceToMatch(&aIn[i], &aIn[0], i, &bEof);
      if( bMatch==0 || bEof ) break;
    }
    if( i==pStr->nToken && (iCol<0 || aIn[0].iCol==iCol) ){
      /* Record a match here */
      fts5InstanceListAppend(&out, aIn[0].iCol, aIn[0].iStream, aIn[0].iOff);
    }
    bEof = fts5InstanceListNext(&aIn[0]);
  }

  pStr->nList = out.iList;
  sqlite4DbFree(db, aIn);

    while( bEof==0 ){
      if( fts5IsNear(&near, &in, nTrail) 
       || fts5IsNear(&in, &near, nLead)
      ){
        /* The current position is a match. Append an entry to the output
        ** and advance the input cursor. */
        fts5InstanceListAppend(&out, in.iCol, in.iStream, in.iOff);
        bEof = fts5InstanceListNext(&in);
      }else{
        if( near.iCol<in.iCol || (near.iCol==in.iCol && near.iOff<in.iOff) ){
          bEof = fts5InstanceListNext(&near);
        }else if( near.iCol==in.iCol && near.iOff==in.iOff ){
          bEof = fts5InstanceListNext(&in);
          if( fts5IsNear(&near, &in, nTrail) ){
            fts5InstanceListAppend(&out, near.iCol, near.iStream, near.iOff);
          }
        }else{
          bEof = fts5InstanceListNext(&in);
        }
      }
    }

  }

  assert( rc!=SQLITE4_NOTFOUND );
  return rc;
}

int sqlite4Fts5Next(Fts5Cursor *pCsr){
  sqlite4DbFree(pCsr->db, pCsr->pSz);
  pCsr->pSz = 0;
  return fts5ExprAdvance(pCsr->db, pCsr->pExpr->pRoot, 0);
}

int sqlite4Fts5Open(
  sqlite4 *db,                    /* Database handle */
  Fts5Info *pInfo,                /* Index description */
  const char *zMatch,             /* Match expression */

  memcpy(&pCsr->aKey[i], aPk, nPk);

  *paKey = pCsr->aKey;
  *pnKey = nReq;
  return SQLITE4_OK;
}

int sqlite4_mi_column_count(sqlite4_context *pCtx, int *pn){
  int rc = SQLITE4_OK;
  if( pCtx->pFts ){
    *pn = pCtx->pFts->pInfo->nCol;
  }else{
    rc = SQLITE4_MISUSE;
  }
  return rc;
}

int sqlite4_mi_phrase_count(sqlite4_context *pCtx, int *pn){
  int rc = SQLITE4_OK;
  if( pCtx->pFts ){
    *pn = pCtx->pFts->pExpr->nPhrase;
  }else{
    rc = SQLITE4_MISUSE;
  }
  return rc;
}

int sqlite4_mi_stream_count(sqlite4_context *pCtx, int *pn){
  int rc = SQLITE4_OK;
  Fts5Cursor *pCsr = pCtx->pFts;
  if( pCsr ){
    rc = fts5CsrLoadGlobal(pCtx->pFts);
    if( rc==SQLITE4_OK ) *pn = pCsr->pGlobal->nStream;
  }else{
    rc = SQLITE4_MISUSE;
  }
  return rc;
}

static int fts5GetSize(Fts5Size *pSz, int iC, int iS){
  int nToken = 0;
  int i;

  if( iC<0 && iS<0 ){
    int nFin = pSz->nCol * pSz->nStream;
    for(i=0; i<nFin; i++) nToken += pSz->aSz[i];
  }else if( iC<0 ){
    for(i=0; i<pSz->nCol; i++) nToken += pSz->aSz[i*pSz->nStream + iS];
  }else if( iS<0 ){
    for(i=0; i<pSz->nStream; i++) nToken += pSz->aSz[pSz->nStream*iC + iS];
  }else if( iC<pSz->nCol && iS<pSz->nStream ){
    nToken = pSz->aSz[iC * pSz->nStream + iS];
  }

  return nToken;
}

int sqlite4_mi_size(sqlite4_context *pCtx, int iC, int iS, int *pn){
  int rc = SQLITE4_OK;
  Fts5Cursor *pCsr = pCtx->pFts;

  if( pCsr==0 ){
    rc = SQLITE4_MISUSE;
  }else{
    rc = fts5CsrLoadSz(pCsr);
    if( rc==SQLITE4_OK ){
      *pn = fts5GetSize(pCsr->pSz, iC, iS);
    }
  }
  return rc;
}

int sqlite4_mi_total_size(sqlite4_context *pCtx, int iC, int iS, int *pn){
  int rc = SQLITE4_OK;
  Fts5Cursor *pCsr = pCtx->pFts;

  if( pCsr==0 ){
    rc = SQLITE4_MISUSE;
  }else{

    rc = fts5CsrLoadGlobal(pCsr);
    if( rc==SQLITE4_OK ){
      *pn = fts5GetSize(pCsr->pGlobal, iC, iS);

    }
  }
  return rc;
}

int sqlite4_mi_total_rows(sqlite4_context *pCtx, int *pn){
  int rc = SQLITE4_OK;
  Fts5Cursor *pCsr = pCtx->pFts;
  if( pCsr==0 ){
    rc = SQLITE4_MISUSE;
  }else{
    rc = fts5CsrLoadGlobal(pCsr);
    if( rc==SQLITE4_OK ) *pn = pCsr->nGlobal;
  }
  return rc;
}


int sqlite4_mi_column_value(
  sqlite4_context *pCtx, 
  int iCol, 
  sqlite4_value **ppVal
){
  int rc = SQLITE4_OK;
  if( pCtx->pFts ){
  }else{










    rc = SQLITE4_MISUSE;
  }
  return rc;
}

static Fts5Str *fts5FindStr(Fts5ExprNode *p, int *piStr){
  Fts5Str *pRet = 0;

    if( pRet==0 ) pRet = fts5FindStr(p->pRight, piStr);
  }
  return pRet;
}

int sqlite4_mi_match_count(
  sqlite4_context *pCtx, 
  int iC,
  int iS,
  int iPhrase,
  int *pnMatch
){
  int rc = SQLITE4_OK;
  Fts5Cursor *pCsr = pCtx->pFts;
  if( pCsr ){
    int nMatch = 0;
    Fts5Str *pStr;
    int iCopy = iPhrase;
    InstanceList sList;

    pStr = fts5FindStr(pCsr->pExpr->pRoot, &iCopy);
    assert( pStr );

    fts5InstanceListInit(pStr->aList, pStr->nList, &sList);
    while( 0==fts5InstanceListNext(&sList) ){
      if( (iC<0 || sList.iCol==iC) && (iS<0 || sList.iStream==iS) ) nMatch++;
    }
    *pnMatch = nMatch;
  }else{
    rc = SQLITE4_MISUSE;
  }
  return rc;
}

  int *pnMatch,
  int *pnDoc,
  int *pnRelevant
){
  return SQLITE4_OK;
}






static void fts5StrLoadRowcounts(Fts5Str *pStr, int nStream, int *anRow){







  u32 mask = 0;














  int iPrevCol = 0;

  InstanceList sList;

  fts5InstanceListInit(pStr->aList, pStr->nList, &sList);
  while( 0==fts5InstanceListNext(&sList) ){
    if( sList.iCol!=iPrevCol ) mask = 0;
    if( (mask & (1<<sList.iStream))==0 ){
      anRow[sList.iCol * nStream + sList.iStream]++;
      mask |= (1<<sList.iStream);
      iPrevCol = sList.iCol;
    }
  }
}

static int fts5ExprLoadRowcounts(
  sqlite4 *db, 
  Fts5Info *pInfo,
  int nStream,
  Fts5ExprNode *pNode, 
  int **panRow
){
  int rc = SQLITE4_OK;

  if( pNode ){
    if( pNode->eType==TOKEN_PRIMITIVE ){
      int *anRow = *panRow;
      Fts5Phrase *pPhrase = pNode->pPhrase;

      rc = fts5ExprAdvance(db, pNode, 1);
      while( rc==SQLITE4_OK ){
        int nIncr =  pInfo->nCol * nStream;      /* Values for each Fts5Str */
        int i;
        for(i=0; i<pPhrase->nStr; i++){
          fts5StrLoadRowcounts(&pPhrase->aStr[i], nStream, &anRow[i*nIncr]);
        }
        rc = fts5ExprAdvance(db, pNode, 0);
      }

      *panRow = &anRow[pInfo->nCol * nStream * pPhrase->nStr];
    }

    if( rc==SQLITE4_OK ){
      rc = fts5ExprLoadRowcounts(db, pInfo, nStream, pNode->pLeft, panRow);
    }
    if( rc==SQLITE4_OK ){
      rc = fts5ExprLoadRowcounts(db, pInfo, nStream, pNode->pRight, panRow);
    }
  }

  return rc;
}

static int fts5CsrLoadRowcounts(Fts5Cursor *pCsr){
  int rc = SQLITE4_OK;

  if( pCsr->anRow==0 ){
    int nStream = pCsr->pGlobal->nStream;
    sqlite4 *db = pCsr->db;
    Fts5Expr *pCopy;
    Fts5Expr *pExpr = pCsr->pExpr;
    Fts5Info *pInfo = pCsr->pInfo;
    int *anRow;

    pCsr->anRow = anRow = (int *)sqlite4DbMallocZero(db, 
        pExpr->nPhrase * pInfo->nCol * pCsr->pGlobal->nStream * sizeof(int)
    );
    if( !anRow ) return SQLITE4_NOMEM;

    rc = fts5ParseExpression(db, pInfo->pTokenizer, pInfo->p, 
        pInfo->iRoot, pInfo->azCol, pInfo->nCol, pCsr->zExpr, &pCopy, 0
    );
    if( rc==SQLITE4_OK ){
      rc = fts5OpenExprCursors(db, pInfo, pExpr->pRoot);
    }

    if( rc==SQLITE4_OK ){
      rc = fts5ExprLoadRowcounts(db, pInfo, nStream, pCopy->pRoot, &anRow);
    }

    fts5ExpressionFree(db, pCopy);
  }

  return rc;
}

int sqlite4_mi_row_count(
  sqlite4_context *pCtx,          /* Context object passed to mi function */
  int iC,                         /* Specific column (or -ve for all columns) */
  int iS,                         /* Specific stream (or -ve for all streams) */
  int iP,                         /* Specific phrase */
  int *pn                         /* Total number of rows containing C/S/P */
){
  int rc = SQLITE4_OK;

  Fts5Cursor *pCsr = pCtx->pFts;



  if( pCsr==0 ){

    rc = SQLITE4_MISUSE;
  }else{
    rc = fts5CsrLoadGlobal(pCsr);
    if( rc==SQLITE4_OK ) rc = fts5CsrLoadRowcounts(pCsr);



    if( rc==SQLITE4_OK ){



      int i;
      int nRow = 0;
      int nStream = pCsr->pGlobal->nStream;
      int nCol = pCsr->pInfo->nCol;
      int *aRow = &pCsr->anRow[iP * nStream * nCol];

      if( iC<0 && iS<0 ){
        int nFin = nCol * nStream;
        for(i=0; i<nFin; i++) nRow += aRow[i];
      }else if( iC<0 ){
        for(i=0; i<nCol; i++) nRow += aRow[i*nStream + iS];
      }else if( iS<0 ){
        for(i=0; i<nStream; i++) nRow += aRow[nStream*iC + iS];
      }else if( iC<nCol && iS<nStream ){
        nRow = aRow[iC * nStream + iS];
      }



      *pn = nRow;


    }



  }
  return rc;
}

/**************************************************************************
***************************************************************************
** Below this point is test code.

      int ni;                     /* Number of docs with phrase i */

      p->db = db;
      p->nPhrase = nPhrase;
      p->aIdf = (double *)&p[1];

      /* Determine the IDF weight for each phrase in the query. */
      rc = sqlite4_mi_total_rows(pCtx, &N);
      for(i=0; rc==SQLITE4_OK && i<nPhrase; i++){
        rc = sqlite4_mi_row_count(pCtx, -1, -1, i, &ni);
        if( rc==SQLITE4_OK ){
          p->aIdf[i] = log((0.5 + N - ni) / (0.5 + ni));
        }
      }

      /* Determine the average document length */
      if( rc==SQLITE4_OK ){
        int nTotal;
        rc = sqlite4_mi_total_size(pCtx, -1, -1, &nTotal);
        if( rc==SQLITE4_OK ){
          p->avgdl = (double)nTotal / (double)N;
        }
      }
    }
  }

  for(i=0; rc==SQLITE4_OK && i<p->nPhrase; i++){
    int tf;                     /* Occurences of phrase i in row (term freq.) */
    int dl;                     /* Tokens in this row (document length) */
    double L;                   /* Normalized document length */
    double prank;               /* Contribution to rank of this phrase */

    /* Set variable tf to the total number of occurrences of phrase iPhrase
    ** in this row (within any column). And dl to the number of tokens in
    ** the current row (again, in any column).  */
    rc = sqlite4_mi_match_count(pCtx, -1, -1, i, &tf); 
    if( rc==SQLITE4_OK ) rc = sqlite4_mi_size(pCtx, -1, -1, &dl); 

    /* Calculate the normalized document length */
    L = (double)dl / p->avgdl;

    /* Calculate the contribution to the rank made by this phrase. Then
    ** add it to variable rank.  */
    prank = (p->aIdf[i] * tf) / (k1 * ( (1.0 - b) + b * L) + tf);

/*
** Special functions that may be called from within matchinfo UDFs. All
** return an SQLite error code - SQLITE4_OK if successful, or some other
** error code otherwise.
**
** sqlite4_mi_column_count():
**   Set *pn to the number of columns in the queried table.
**
** sqlite4_mi_phrase_count():
**   Set *pn to the number of phrases in the query.
**
** sqlite4_mi_stream_count():
**   Set *pn to the number of streams in the FTS index.
**
** sqlite4_mi_size():
**   Set *pn to the number of tokens belonging to stream iS in the value 
**   stored in column iC of the current row. 
**
**   Either or both of iS and iC may be negative. If iC is negative, then the
**   output value is the total number of tokens for the specified stream (or
**   streams) across all table columns. Similarly, if iS is negative, the 
**   output value is the total number of tokens in the specified column or 
**   columns, regardless of stream.
**
** sqlite4_mi_total_size():
**   Similar to sqlite4_mi_size(), except the output parameter is set to
**   the total number of tokens belonging to the specified column(s) 
**   and stream(s) in all rows of the table, not just the current row.
**
** sqlite4_mi_total_rows():
**   Set *pn to the total number of rows in the indexed table.
**
** sqlite4_mi_row_count():
**   Set the output parameter to the total number of rows in the table that
**   contain at least one instance of the phrase identified by parameter
**   iP in the column(s) and stream(s) identified by parameters iC and iS.
**
** sqlite4_mi_match_count():
**   Set the output parameter to the total number of occurences of phrase
**   iP in the current row that belong to the column(s) and stream(s) 
**   identified by parameters iC and iS.
**
**   Parameter iP may also be negative. In this case, the output value is
**   set to the total number of occurrences of all query phrases in the
**   current row, subject to the constraints imposed by iC and iS.
**
** sqlite4_mi_match_detail():
**   This function may be used to iterate through all matches in the
**   current row in order of occurrence.
**
** sqlite4_mi_column_value():
**   Set *ppVal to point to an sqlite4_value object containing the value
**   read from column iCol of the current row. This object is valid until
**   the function callback returns.





































*/

int sqlite4_mi_column_count(sqlite4_context *, int *pn);
int sqlite4_mi_phrase_count(sqlite4_context *, int *pn);
int sqlite4_mi_stream_count(sqlite4_context *, int *pn);

int sqlite4_mi_total_size(sqlite4_context *, int iC, int iS, int *pn);
int sqlite4_mi_total_rows(sqlite4_context *, int *pn);

int sqlite4_mi_row_count(sqlite4_context *, int iC, int iS, int iP, int *pn);

int sqlite4_mi_size(sqlite4_context *, int iC, int iS, int *pn);
int sqlite4_mi_match_count(sqlite4_context *, int iC, int iS, int iP, int *pn);
int sqlite4_mi_match_detail(
    sqlite4_context *, int iMatch, int *piOff, int *piC, int *piS, int *piP
);
int sqlite4_mi_column_value(sqlite4_context *, int iCol, sqlite4_value **ppVal);



/*
** Undo the hack that converts floating point types to integer for
** builds on processors without floating point support.
*/
#ifdef SQLITE4_OMIT_FLOATING_POINT