SQLite

  sqlite3_int64 iVal              /* Write this value to the list */
){
  assert( iVal-*piPrev > 0 || (*piPrev==0 && iVal==0) );
  *pp += sqlite3Fts3PutVarint(*pp, iVal-*piPrev);
  *piPrev = iVal;
}

/*
** When this function is called, *ppPoslist is assumed to point to the 
** start of a position-list.
*/
static void fts3PoslistCopy(char **pp, char **ppPoslist){
  char *pEnd = *ppPoslist;
  char c = 0;

  /* The end of a position list is marked by a zero encoded as an FTS3 
  ** varint. A single 0x00 byte. Except, if the 0x00 byte is preceded by
  ** a byte with the 0x80 bit set, then it is not a varint 0, but the tail
  ** of some other, multi-byte, value.
  **
  ** The following block moves pEnd to point to the first byte that is not 
  ** immediately preceded by a byte with the 0x80 bit set. Then increments
  ** pEnd once more so that it points to the byte immediately following the
  ** last byte in the position-list.
  */
  while( *pEnd | c ) c = *pEnd++ & 0x80;
  pEnd++;

  if( pp ){
    int n = (int)(pEnd - *ppPoslist);
    char *p = *pp;
    memcpy(p, *ppPoslist, n);
    p += n;
    *pp = p;
  }

    char *p = *pp;
    memcpy(p, *ppPoslist, n);
    p += n;
    *pp = p;
  }
  *ppPoslist = pEnd;
}

/*
** This function is used to count the entries in a column-list (delta-encoded
** list of term offsets within a single column of a single row).
*/
static int fts3ColumnlistCount(char **ppCollist){
  char *pEnd = *ppCollist;
  char c = 0;
  int nEntry = 0;

  /* A column-list is terminated by either a 0x01 or 0x00. */
  while( 0xFE & (*pEnd | c) ){
    c = *pEnd++ & 0x80;
    if( !c ) nEntry++;
  }

  *ppCollist = pEnd;
  return nEntry;
}

/*
** Value used to signify the end of an offset-list. This is safe because
** it is not possible to have a document with 2^31 terms.
*/
#define OFFSET_LIST_END 0x7fffffff

** Evaluate the full-text expression pExpr against fts3 table pTab. Store
** the resulting doclist in *paOut and *pnOut.
*/
static int evalFts3Expr(
  Fts3Table *p,                   /* Virtual table handle */
  Fts3Expr *pExpr,                /* Parsed fts3 expression */
  char **paOut,                   /* OUT: Pointer to malloc'd result buffer */
  int *pnOut,                     /* OUT: Size of buffer at *paOut */
  int isReqPos                    /* Require positions in output buffer */
){
  int rc = SQLITE_OK;             /* Return code */

  /* Zero the output parameters. */
  *paOut = 0;
  *pnOut = 0;

  if( pExpr ){
    assert( pExpr->eType==FTSQUERY_PHRASE 
         || pExpr->eType==FTSQUERY_NEAR 
         || isReqPos==0
    );
    if( pExpr->eType==FTSQUERY_PHRASE ){
      rc = fts3PhraseSelect(p, pExpr->pPhrase, 
          isReqPos || (pExpr->pParent && pExpr->pParent->eType==FTSQUERY_NEAR),
          paOut, pnOut
      );
    }else{
      char *aLeft;
      char *aRight;
      int nLeft;
      int nRight;

      if( 0==(rc = evalFts3Expr(p, pExpr->pRight, &aRight, &nRight, isReqPos))
       && 0==(rc = evalFts3Expr(p, pExpr->pLeft, &aLeft, &nLeft, isReqPos))
      ){
        assert( pExpr->eType==FTSQUERY_NEAR || pExpr->eType==FTSQUERY_OR     
            || pExpr->eType==FTSQUERY_AND  || pExpr->eType==FTSQUERY_NOT
        );
        switch( pExpr->eType ){
          case FTSQUERY_NEAR: {
            Fts3Expr *pLeft;
            Fts3Expr *pRight;
            int mergetype = isReqPos ? MERGE_POS_NEAR : MERGE_NEAR;
            int nParam1;
            int nParam2;
            char *aBuffer;
           
            if( pExpr->pParent && pExpr->pParent->eType==FTSQUERY_NEAR ){
              mergetype = MERGE_POS_NEAR;
            }

    }

    rc = sqlite3Fts3ExprParse(p->pTokenizer, p->azColumn, p->nColumn, 
        iCol, zQuery, -1, &pCsr->pExpr
    );
    if( rc!=SQLITE_OK ) return rc;

    rc = evalFts3Expr(p, pCsr->pExpr, &pCsr->aDoclist, &pCsr->nDoclist, 0);
    pCsr->pNextId = pCsr->aDoclist;
    pCsr->iPrevId = 0;
  }

  if( rc!=SQLITE_OK ) return rc;
  return fts3NextMethod(pCursor);
}

** Implementation of xRollback(). Discard the contents of the pending-terms
** hash-table. Any changes made to the database are reverted by SQLite.
*/
static int fts3RollbackMethod(sqlite3_vtab *pVtab){
  sqlite3Fts3PendingTermsClear((Fts3Table *)pVtab);
  return SQLITE_OK;
}

/*
** The following flags affect the format of the blob of unsigned int values
** returned by the matchinfo() function. The format is defined as follows:
**
**   Integer 0: Number of 'simple queries' that make up the FTS3 query.
**   Integer 1: Number of columns in queried table.
**
** followed by the data for (query 0, column 0), (query 0, column 1) ...
** (query 1, column 0) and so on.
**
** The first integer in each data is the number of hits that the simple
** query has in the current column.
**
** If the GLOBALCOUNT flag is set, then this is followed by the total
** number of hits the simple query has in the current column of *all*
** selected rows.
**
** If the POSITIONLIST flag is set, then this is followed by <local-count>
** integers - the positions of each of the hits for the current column/query.
*/
#define FTS3_MATCHINFO_GLOBALCOUNT  0x00000001
#define FTS3_MATCHINFO_POSITIONLIST 0x00000002

typedef struct MatchInfo MatchInfo;
struct MatchInfo {
  int rc;                         /* Return code. SQLITE_OK if no error */
  sqlite3_int64 iDocid;           /* Docid of entry to return data for */
  Fts3Table *pTab;                /* FTS3 Virtual table */
  int flags;                      /* Output flags (see above) */
  int nQuery;                     /* Number of simple queries */

  /* Malloced output buffer */
  unsigned int *aOut;
  int nOut;
  int nAlloc;
};

static void fts3MatchInfoAppend(MatchInfo *pInfo, unsigned int iVal){
  if( pInfo->rc!=SQLITE_OK ) return;

  if( pInfo->nOut==pInfo->nAlloc ){
    int nNew = pInfo->nAlloc*2+100;
    unsigned int *aNew = (unsigned int *)sqlite3_realloc(
        pInfo->aOut, nNew * sizeof(unsigned int)
    );
    if( !aNew ){
      pInfo->rc = SQLITE_NOMEM;
      return;
    }
    pInfo->aOut = aNew;
    pInfo->nAlloc = nNew;
  }

  pInfo->aOut[pInfo->nOut++] = iVal;
}

/*
** Iterate through each simple query that makes up the query expression 
** implemented by the cursor passed as the first argument.
*/
static void fts3ExprMatchInfo(
  sqlite3_context *pCtx,
  Fts3Expr *pExpr,
  MatchInfo *pInfo
){
  int eType = pExpr->eType;
  if( eType==FTSQUERY_NOT || pInfo->rc ){
    return;
  }else if( eType!=FTSQUERY_PHRASE && eType!=FTSQUERY_NEAR ){
    assert( pExpr->pLeft && pExpr->pRight );
    fts3ExprMatchInfo(pCtx, pExpr->pLeft, pInfo);
    if( pInfo->rc==SQLITE_OK ){
      fts3ExprMatchInfo(pCtx, pExpr->pRight, pInfo);
    }
  }else{
    Fts3Table *pTab = pInfo->pTab;

    /* If it is not loaded already, load the doclist for this simple query
    ** from the FTS3 full-text index. 
    */
    if( pExpr->isLoaded==0 ){
      pInfo->rc = evalFts3Expr(pTab,pExpr,&pExpr->aDoclist,&pExpr->nDoclist,1);
      if( pInfo->rc ) return;
      pExpr->isLoaded = 1;
    }

    /* If aDoclist is not NULL, search for the doclist entry in pExpr->aDoclist
    ** associated with the docid pInfo->iDocid.
    */
    if( pExpr->aDoclist ){
      char *pEnd = &pExpr->aDoclist[pExpr->nDoclist];
      sqlite3_int64 iSearch = pInfo->iDocid;

      if( pExpr->pCurrent==0 ){
        assert( pExpr->iDocid==0 );
        pExpr->pCurrent = pExpr->aDoclist;
        fts3GetDeltaVarint(&pExpr->pCurrent, &pExpr->iDocid);
      }

      while( pExpr->iDocid<iSearch && pExpr->pCurrent<pEnd ){
        /* Skip pCurrent to the start of the next doclist entry */
        fts3PoslistCopy(0, &pExpr->pCurrent);
        if( pExpr->pCurrent<pEnd ){
          fts3GetDeltaVarint(&pExpr->pCurrent, &pExpr->iDocid);
        }
      }

      if( pExpr->iDocid==iSearch ){
        int i;
        for(i=0; i<pTab->nColumn; i++){
          unsigned int iLocalOff;

          /* Add space for the "local-count" field. */
          iLocalOff = pInfo->nOut;
          fts3MatchInfoAppend(pInfo, 0);
          if( pInfo->rc ) return;

          /* If the GLOBALCOUNT field is required, write the global-count
          ** value for this query/column to the output buffer.
          */
          if( pInfo->flags&FTS3_MATCHINFO_GLOBALCOUNT ){
            if( !pExpr->aHist ){
              char *pCsr = pExpr->aDoclist;

              /* Allocate a zeroed buffer to store the global-counts 
              ** corresponding to this simple query for each table column. 
              */
              int nByte = sizeof(unsigned int)*pTab->nColumn;
              pExpr->aHist = (unsigned int *)sqlite3_malloc(nByte);
              if( !pExpr->aHist ){
                pInfo->rc = SQLITE_NOMEM;
                return;
              }
              memset(pExpr->aHist, 0, nByte);

              /* Scan the entire doclist to populate Fts3Expr.aHist[]. */ 
              while( pCsr<pEnd ){
                while( *pCsr++ & 0x80 );
                while( *pCsr ){
                  sqlite3_int64 iCol = 0;
                  if( *pCsr==0x01 ) pCsr += sqlite3Fts3GetVarint(pCsr, &iCol);
                  pExpr->aHist[iCol] += fts3ColumnlistCount(&pCsr);
                }
                pCsr++;
              }
            }

            fts3MatchInfoAppend(pInfo, pExpr->aHist[i]);
          }

          if( i==0 ){
            if( *pExpr->pCurrent==0x01 ) continue;
          }else{
            sqlite3_int64 iCol;
            char *pList = pExpr->pCurrent;
            if( *pList==0x00 ) continue;
            pList++;
            pList += sqlite3Fts3GetVarint(pList, &iCol);
            if( iCol!=i ) continue;
            pExpr->pCurrent = pList;
          }

          if( pInfo->flags&FTS3_MATCHINFO_POSITIONLIST ){
            int nLocal = 0;
            sqlite3_int64 iOffset = 0;
            char *pList = pExpr->pCurrent;
            while( *pList&0xFE ){
              fts3GetDeltaVarint(&pList, &iOffset); iOffset -= 2;
              fts3MatchInfoAppend(pInfo, iOffset);
              nLocal++;
            }
            pExpr->pCurrent = pList;
            pInfo->aOut[iLocalOff] = nLocal;
          }else{
            pInfo->aOut[iLocalOff] = fts3ColumnlistCount(&pExpr->pCurrent);
          }
        }
        pExpr->pCurrent++;
        if( pExpr->pCurrent<pEnd ){
          fts3GetDeltaVarint(&pExpr->pCurrent, &pExpr->iDocid);
        }
      }
    }
    pInfo->nQuery++;
  }
}

/*
** Helper function used by the implementation of the overloaded snippet(),
** offsets() and optimize() SQL functions.
**
** If the value passed as the third argument is a blob of size
** sizeof(Fts3Cursor*), then the blob contents are copied to the 

      sqlite3_result_text(pContext, "Index already optimal", -1, SQLITE_STATIC);
      break;
    default:
      sqlite3_result_error_code(pContext, rc);
      break;
  }
}

/*
** Implementation of the matchinfo() function for FTS3
*/
static void fts3MatchinfoFunc(
  sqlite3_context *pContext,      /* SQLite function call context */
  int nVal,                       /* Size of argument array */
  sqlite3_value **apVal           /* Array of arguments */
){
  Fts3Cursor *pCsr;               /* Cursor handle passed through apVal[0] */
  int flags = 0;


  if( nVal==2 ){
    int i;
    const unsigned char *zFlags = sqlite3_value_text(apVal[1]);
    for(i=0; zFlags[i]; i++){
      switch( zFlags[i] ){
        case 'g': flags |= FTS3_MATCHINFO_GLOBALCOUNT; break;
        case 'p': flags |= FTS3_MATCHINFO_POSITIONLIST; break;
        default: {
          char zErr[18];
          memcpy(zErr, "Unknown flag: \"%c\"", 18);
          zErr[16] = (char)zFlags[i];
          sqlite3_result_error(pContext, zErr, -1);
          return;
        }
      }
    }
  }else if( nVal!=1 ){
    sqlite3_result_error(pContext,
        "wrong number of arguments to function matchinfo()", -1);
    return;
  }

  if( SQLITE_OK==fts3FunctionArg(pContext, "matchinfo", apVal[0], &pCsr) ){
    MatchInfo ctx;
    memset(&ctx, 0, sizeof(ctx));
    ctx.iDocid = pCsr->iPrevId;
    ctx.pTab = (Fts3Table *)pCsr->base.pVtab;
    ctx.flags = flags;

    fts3MatchInfoAppend(&ctx, 0);
    fts3MatchInfoAppend(&ctx, ctx.pTab->nColumn);

    /* Iterate through each of the 'simple' queries that make up the query
    ** expression. A 'simple' query is a phrase (including token and token 
    ** prefix) or NEAR query. 
    */
    fts3ExprMatchInfo(pContext, pCsr->pExpr, &ctx);
    if( ctx.rc ){
      sqlite3_free(ctx.aOut);
      sqlite3_result_error_code(pContext, ctx.rc);
    }else{
      int nByte = ctx.nOut*sizeof(unsigned int);
      ctx.aOut[0] = ctx.nQuery;
      sqlite3_result_blob(pContext, ctx.aOut, nByte, sqlite3_free);
    }
  }
}

/*
** This routine implements the xFindFunction method for the FTS3
** virtual table.
*/
static int fts3FindFunctionMethod(
  sqlite3_vtab *pVtab,            /* Virtual table handle */
  int nArg,                       /* Number of SQL function arguments */
  const char *zName,              /* Name of SQL function */
  void (**pxFunc)(sqlite3_context*,int,sqlite3_value**), /* OUT: Result */
  void **ppArg                    /* Unused */
){
  struct Overloaded {
    const char *zName;
    void (*xFunc)(sqlite3_context*,int,sqlite3_value**);
  } aOverload[] = {
    { "snippet", fts3SnippetFunc },
    { "offsets", fts3OffsetsFunc },
    { "optimize", fts3OptimizeFunc },
    { "matchinfo", fts3MatchinfoFunc },
  };
  int i;                          /* Iterator variable */

  UNUSED_PARAMETER(pVtab);
  UNUSED_PARAMETER(nArg);
  UNUSED_PARAMETER(ppArg);

  ** the two scalar functions. If this is successful, register the
  ** module with sqlite.
  */
  if( SQLITE_OK==rc 
   && SQLITE_OK==(rc = sqlite3Fts3InitHashTable(db, pHash, "fts3_tokenizer"))
   && SQLITE_OK==(rc = sqlite3_overload_function(db, "snippet", -1))
   && SQLITE_OK==(rc = sqlite3_overload_function(db, "offsets", 1))
   && SQLITE_OK==(rc = sqlite3_overload_function(db, "matchinfo", -1))
   && SQLITE_OK==(rc = sqlite3_overload_function(db, "optimize", 1))
  ){
    return sqlite3_create_module_v2(
        db, "fts3", &fts3Module, (void *)pHash, hashDestroy
    );
  }

    int n;                   /* Number of bytes in buffer pointed to by z */
    int isPrefix;            /* True if token ends in with a "*" character */
  } aToken[1];               /* One entry for each token in the phrase */
};

/*
** A tree of these objects forms the RHS of a MATCH operator.
**
** If Fts3Expr.eType is either FTSQUERY_NEAR or FTSQUERY_PHRASE and isLoaded
** is true, then aDoclist points to a malloced buffer, size nDoclist bytes, 
** containing the results of the NEAR or phrase query in FTS3 doclist
** format. As usual, the initial "Length" field found in doclists stored
** on disk is omitted from this buffer.
**
** Variable pCurrent always points to the start of a docid field within
** aDoclist. Since the doclist is usually scanned in docid order, this can
** be used to accelerate seeking to the required docid within the doclist.
*/
struct Fts3Expr {
  int eType;                 /* One of the FTSQUERY_XXX values defined below */
  int nNear;                 /* Valid if eType==FTSQUERY_NEAR */
  Fts3Expr *pParent;         /* pParent->pLeft==this or pParent->pRight==this */
  Fts3Expr *pLeft;           /* Left operand */
  Fts3Expr *pRight;          /* Right operand */
  Fts3Phrase *pPhrase;       /* Valid if eType==FTSQUERY_PHRASE */

  int isLoaded;
  sqlite3_int64 iDocid;
  char *aDoclist;
  int nDoclist;
  char *pCurrent;
  unsigned int *aHist;
};

/*
** Candidate values for Fts3Query.eType. Note that the order of the first
** four values is in order of precedence when parsing expressions. For 
** example, the following:
**

/*
** Free a parsed fts3 query expression allocated by sqlite3Fts3ExprParse().
*/
void sqlite3Fts3ExprFree(Fts3Expr *p){
  if( p ){
    sqlite3Fts3ExprFree(p->pLeft);
    sqlite3Fts3ExprFree(p->pRight);
    sqlite3_free(p->aDoclist);
    sqlite3_free(p->aHist);
    sqlite3_free(p);
  }
}

/****************************************************************************
*****************************************************************************
** Everything after this point is just test code.

  /* Tokenizer implementations will typically add additional fields */
};

struct sqlite3_tokenizer_cursor {
  sqlite3_tokenizer *pTokenizer;       /* Tokenizer for this cursor. */
  /* Tokenizer implementations will typically add additional fields */
};

int fts3_global_term_cnt(int iTerm, int iCol);
int fts3_term_cnt(int iTerm, int iCol);


#endif /* _FTS3_TOKENIZER_H_ */

  }
} {}

do_test fts3query-3.2 {
  execsql { SELECT docid FROM foobar WHERE description MATCH '"high sp d"' }
} {}

proc mit {blob} {
  set scan(littleEndian) i*
  set scan(bigEndian) I*
  binary scan $blob $scan($::tcl_platform(byteOrder)) r
  return $r
}
db func mit mit

do_test fts3query-3.3 {
  execsql { SELECT mit(matchinfo(foobar)) FROM foobar WHERE foobar MATCH 'the' }
} {{1 1 3}}
do_test fts3query-3.4 {
  execsql { 
    SELECT mit(matchinfo(foobar, 'g')) FROM foobar WHERE foobar MATCH 'the' 
  }
} {{1 1 3 3}}
do_test fts3query-3.5 {
  execsql { 
    SELECT mit(matchinfo(foobar, 'p')) FROM foobar WHERE foobar MATCH 'the' 
  }
} {{1 1 3 27 74 79}}
do_test fts3query-3.5 {
  execsql { 
    SELECT mit(matchinfo(foobar, 'pg')) FROM foobar WHERE foobar MATCH 'the' 
  }
} {{1 1 3 3 27 74 79}}

finish_test

proc simple_phrase {zPrefix} {
  set ret [list]

  set reg [string map {* {[^ ]*}} $zPrefix]
  set reg " $reg "

  foreach key [lsort -integer [array names ::t1]] {
    set value $::t1($key)
    set cnt [list]
    foreach col $value {
      if {[regexp $reg " $col "]} { lappend ret $key ; break }
    }
  }

  #lsort -uniq -integer $ret
  set ret
}

proc simple_token_matchinfo {zToken} {
  foreach key [lsort -integer [array names ::t1]] {
    set value $::t1($key)
    set cnt [list]
    foreach col $value {
      lappend cnt [llength [lsearch -all $col $zToken]]
    }
    if {[lindex [lsort $cnt] end]} {
      lappend ret $key [concat 1 3 $cnt]
    }
  }
  
  set ret
} 

proc simple_near {termlist nNear} {
  set ret [list]

  foreach {key value} [array get ::t1] {
    foreach v $value {

}
proc setop_and {A B} {
  foreach b $B { set n($b) {} }
  set ret [list]
  foreach a $A { if {[info exists n($a)]} {lappend ret $a} }
  return $ret
}

proc mit {blob} {
  set scan(littleEndian) i*
  set scan(bigEndian) I*
  binary scan $blob $scan($::tcl_platform(byteOrder)) r
  return $r
}
db func mit mit

set sqlite_fts3_enable_parentheses 1

foreach nodesize {50 500 1000 2000} {
  catch { array unset ::t1 }

  # Create the FTS3 table. Populate it (and the Tcl array) with 100 rows.
  #
  db transaction {
    catchsql { DROP TABLE t1 }
    execsql "CREATE VIRTUAL TABLE t1 USING fts3(a, b, c)"
    execsql "INSERT INTO t1(t1) VALUES('nodesize=$nodesize')"
    for {set i 0} {$i < 100} {incr i} { insert_row $i }
  }
  
  for {set iTest 1} {$iTest <= 100} {incr iTest} {
    catchsql COMMIT

    set DO_MALLOC_TEST 0
    set nRep 10
    if {$iTest==100 && $nodesize==50} { 
      set DO_MALLOC_TEST 1 
      set nRep 2

    # the database for the set of documents containing each of these terms
    # is the same as the result obtained by scanning the contents of the Tcl 
    # array for each term.
    #
    for {set i 0} {$i < 10} {incr i} {
      set term [random_term]
      do_select_test fts3rnd-1.$nodesize.$iTest.1.$i {
        SELECT docid, mit(matchinfo(t1)) FROM t1 WHERE t1 MATCH $term
      } [simple_token_matchinfo $term]
    }

    # This time, use the first two characters of each term as a term prefix
    # to query for. Test that querying the Tcl array produces the same results
    # as querying the FTS3 table for the prefix.
    #
    for {set i 0} {$i < $nRep} {incr i} {