SQLite

** This is an SQLite module implementing full-text search.
*/

#include "fts5Int.h"

typedef struct Fts5Table Fts5Table;
typedef struct Fts5Cursor Fts5Cursor;
typedef struct Fts5Global Fts5Global;
typedef struct Fts5Auxiliary Fts5Auxiliary;

/*
** A single object of this type is allocated when the FTS5 module is 
** registered with a database handle. It is used to store pointers to
** all registered FTS5 extensions - tokenizers and auxiliary functions.
*/
struct Fts5Global {
  sqlite3 *db;                    /* Associated database connection */ 
  i64 iNextId;                    /* Used to allocate unique cursor ids */
  Fts5Auxiliary *pAux;            /* First in list of all aux. functions */
  Fts5Cursor *pCsr;               /* First in list of all open cursors */
};

/*
** Each auxiliary function registered with the FTS5 module is represented
** by an object of the following type. All such objects are stored as part
** of the Fts5Global.pAux list.
*/
struct Fts5Auxiliary {
  Fts5Global *pGlobal;            /* Global context for this function */
  char *zFunc;                    /* Function name (nul-terminated) */
  void *pUserData;                /* User-data pointer */
  fts5_extension_function xFunc;  /* Callback function */
  void (*xDestroy)(void*);        /* Destructor function */
  Fts5Auxiliary *pNext;           /* Next registered auxiliary function */
};

/*
** Virtual-table object.
*/
struct Fts5Table {
  sqlite3_vtab base;              /* Base class used by SQLite core */
  Fts5Config *pConfig;            /* Virtual table configuration */
  Fts5Index *pIndex;              /* Full-text index */
  Fts5Storage *pStorage;          /* Document store */
  Fts5Global *pGlobal;            /* Global (connection wide) data */
};

struct Fts5MatchPhrase {
  Fts5Buffer *pPoslist;           /* Pointer to current poslist */
  int nTerm;                      /* Size of phrase in terms */
};

/*
** Virtual-table cursor object.
*/
struct Fts5Cursor {
  sqlite3_vtab_cursor base;       /* Base class used by SQLite core */
  int idxNum;                     /* idxNum passed to xFilter() */
  sqlite3_stmt *pStmt;            /* Statement used to read %_content */
  int bEof;                       /* True at EOF */
  Fts5Expr *pExpr;                /* Expression for MATCH queries */
  int bSeekRequired;              /* True if seek is required */
  Fts5Cursor *pNext;              /* Next cursor in Fts5Cursor.pCsr list */

  /* Variables used by auxiliary functions */
  i64 iCsrId;                     /* Cursor id */
  Fts5Auxiliary *pAux;            /* Currently executing function */
};

/*
** Close a virtual table handle opened by fts5InitVtab(). If the bDestroy
** argument is non-zero, attempt delete the shadow tables from teh database
*/
static int fts5FreeVtab(Fts5Table *pTab, int bDestroy){

  if( rc==SQLITE_OK ){
    pTab = (Fts5Table*)sqlite3_malloc(sizeof(Fts5Table));
    if( pTab==0 ){
      rc = SQLITE_NOMEM;
    }else{
      memset(pTab, 0, sizeof(Fts5Table));
      pTab->pConfig = pConfig;
      pTab->pGlobal = (Fts5Global*)pAux;
    }
  }

  /* Open the index sub-system */
  if( rc==SQLITE_OK ){
    rc = sqlite3Fts5IndexOpen(pConfig, bCreate, &pTab->pIndex, pzErr);
  }

  return SQLITE_OK;
}

/*
** Implementation of xOpen method.
*/
static int fts5OpenMethod(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCsr){
  Fts5Table *pTab = (Fts5Table*)pVTab;
  Fts5Cursor *pCsr;               /* New cursor object */
  int rc = SQLITE_OK;             /* Return code */

  pCsr = (Fts5Cursor*)sqlite3_malloc(sizeof(Fts5Cursor));
  if( pCsr ){
    Fts5Global *pGlobal = pTab->pGlobal;
    memset(pCsr, 0, sizeof(Fts5Cursor));
    pCsr->pNext = pGlobal->pCsr;
    pGlobal->pCsr = pCsr;
    pCsr->iCsrId = ++pGlobal->iNextId;
  }else{
    rc = SQLITE_NOMEM;
  }
  *ppCsr = (sqlite3_vtab_cursor*)pCsr;
  return rc;
}

/*
** Close the cursor.  For additional information see the documentation
** on the xClose method of the virtual table interface.
*/
static int fts5CloseMethod(sqlite3_vtab_cursor *pCursor){
  Fts5Table *pTab = (Fts5Table*)(pCursor->pVtab);
  Fts5Cursor *pCsr = (Fts5Cursor*)pCursor;
  Fts5Cursor **pp;
  if( pCsr->pStmt ){
    int eStmt = fts5StmtType(pCsr->idxNum);
    sqlite3Fts5StorageStmtRelease(pTab->pStorage, eStmt, pCsr->pStmt);
  }
  sqlite3Fts5ExprFree(pCsr->pExpr);

  /* Remove the cursor from the Fts5Global.pCsr list */
  for(pp=&pTab->pGlobal->pCsr; (*pp)!=pCsr; pp=&(*pp)->pNext);
  *pp = pCsr->pNext;

  sqlite3_free(pCsr);
  return SQLITE_OK;
}


/*
** Advance the cursor to the next row in the table that matches the 

  }else{
    *pRowid = sqlite3Fts5ExprRowid(pCsr->pExpr);
  }

  return SQLITE_OK;
}

/*

** If the cursor requires seeking (bSeekRequired flag is set), seek it.
** Return SQLITE_OK if no error occurs, or an SQLite error code otherwise.
*/
static int fts5SeekCursor(Fts5Cursor *pCsr){






  int rc = SQLITE_OK;


  if( pCsr->bSeekRequired ){
    assert( pCsr->pExpr );
    sqlite3_reset(pCsr->pStmt);
    sqlite3_bind_int64(pCsr->pStmt, 1, sqlite3Fts5ExprRowid(pCsr->pExpr));
    rc = sqlite3_step(pCsr->pStmt);
    if( rc==SQLITE_ROW ){
      rc = SQLITE_OK;
    }else{
      rc = sqlite3_reset(pCsr->pStmt);
      if( rc==SQLITE_OK ){
        rc = SQLITE_CORRUPT_VTAB;
      }
    }
  }
  return rc;
}

/* 
** This is the xColumn method, called by SQLite to request a value from
** the row that the supplied cursor currently points to.
*/
static int fts5ColumnMethod(
  sqlite3_vtab_cursor *pCursor,   /* Cursor to retrieve value from */
  sqlite3_context *pCtx,          /* Context for sqlite3_result_xxx() calls */
  int iCol                        /* Index of column to read value from */
){
  Fts5Config *pConfig = ((Fts5Table*)(pCursor->pVtab))->pConfig;
  Fts5Cursor *pCsr = (Fts5Cursor*)pCursor;
  int rc = SQLITE_OK;
  
  assert( pCsr->bEof==0 );

  if( iCol==pConfig->nCol ){
    /* User is requesting the value of the special column with the same name
    ** as the table. Return the cursor integer id number. This value is only
    ** useful in that it may be passed as the first argument to an FTS5
    ** auxiliary function.  */
    sqlite3_result_int64(pCtx, pCsr->iCsrId);
  }else{
    rc = fts5SeekCursor(pCsr);
    if( rc==SQLITE_OK ){
      sqlite3_result_value(pCtx, sqlite3_column_value(pCsr->pStmt, iCol+1));
    }
  }
  return rc;
}

/*
** This function is called to handle an FTS INSERT command. In other words,
** an INSERT statement of the form:

*/
static int fts5RollbackMethod(sqlite3_vtab *pVtab){
  Fts5Table *pTab = (Fts5Table*)pVtab;
  int rc;
  rc = sqlite3Fts5IndexRollback(pTab->pIndex);
  return rc;
}

static void *fts5ApiUserData(Fts5Context *pCtx){
  Fts5Cursor *pCsr = (Fts5Cursor*)pCtx;
  return pCsr->pAux->pUserData;
}

static int fts5ApiColumnCount(Fts5Context *pCtx){
  Fts5Cursor *pCsr = (Fts5Cursor*)pCtx;
  return ((Fts5Table*)(pCsr->base.pVtab))->pConfig->nCol;
}

static int fts5ApiColumnAvgSize(Fts5Context *pCtx, int iCol, int *pnToken){
  assert( 0 );
  return 0;
}

static int fts5ApiTokenize(
  Fts5Context *pCtx, 
  const char *pText, int nText, 
  void *pUserData,
  int (*xToken)(void*, const char*, int, int, int, int)
){
  assert( 0 );
  return SQLITE_OK;
}

static int fts5ApiPhraseCount(Fts5Context *pCtx){
  Fts5Cursor *pCsr = (Fts5Cursor*)pCtx;
  return sqlite3Fts5ExprPhraseCount(pCsr->pExpr);
}

static int fts5ApiPhraseSize(Fts5Context *pCtx, int iPhrase){
  Fts5Cursor *pCsr = (Fts5Cursor*)pCtx;
  return sqlite3Fts5ExprPhraseSize(pCsr->pExpr, iPhrase);
}

static sqlite3_int64 fts5ApiRowid(Fts5Context *pCtx){
  Fts5Cursor *pCsr = (Fts5Cursor*)pCtx;
  return sqlite3Fts5ExprRowid(pCsr->pExpr);
}

static int fts5ApiColumnText(
  Fts5Context *pCtx, 
  int iCol, 
  const char **pz, 
  int *pn
){
  Fts5Cursor *pCsr = (Fts5Cursor*)pCtx;
  int rc = fts5SeekCursor(pCsr);
  if( rc==SQLITE_OK ){
    *pz = (const char*)sqlite3_column_text(pCsr->pStmt, iCol);
    *pn = sqlite3_column_bytes(pCsr->pStmt, iCol);
  }
  return rc;
}

static int fts5ApiColumnSize(Fts5Context *pCtx, int iCol, int *pnToken){
  assert( 0 );
  return 0;
}

static int fts5ApiPoslist(
  Fts5Context *pCtx, 
  int iPhrase, 
  int *pi, 
  int *piCol, 
  int *piOff
){
  Fts5Cursor *pCsr = (Fts5Cursor*)pCtx;
  const u8 *a; int n;             /* Poslist for phrase iPhrase */
  n = sqlite3Fts5ExprPoslist(pCsr->pExpr, iPhrase, &a);
  return sqlite3Fts5PoslistNext(a, n, pi, piCol, piOff);
}

static void fts5ApiCallback(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  static const Fts5ExtensionApi sApi = {
    1,                            /* iVersion */
    fts5ApiUserData,
    fts5ApiColumnCount,
    fts5ApiColumnAvgSize,
    fts5ApiTokenize,
    fts5ApiPhraseCount,
    fts5ApiPhraseSize,
    fts5ApiRowid,
    fts5ApiColumnText,
    fts5ApiColumnSize,
    fts5ApiPoslist,
  };

  Fts5Auxiliary *pAux;
  Fts5Cursor *pCsr;
  i64 iCsrId;

  assert( argc>=1 );
  pAux = (Fts5Auxiliary*)sqlite3_user_data(context);
  iCsrId = sqlite3_value_int64(argv[0]);

  for(pCsr=pAux->pGlobal->pCsr; pCsr; pCsr=pCsr->pNext){
    if( pCsr->iCsrId==iCsrId ) break;
  }
  if( pCsr==0 ){
    char *zErr = sqlite3_mprintf("no such cursor: %lld", iCsrId);
    sqlite3_result_error(context, zErr, -1);
  }else{
    assert( pCsr->pAux==0 );
    pCsr->pAux = pAux;
    pAux->xFunc(&sApi, (Fts5Context*)pCsr, context, argc-1, &argv[1]);
    pCsr->pAux = 0;
  }
}


/*
** This routine implements the xFindFunction method for the FTS3
** virtual table.
*/
static int fts5FindFunctionMethod(
  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                    /* OUT: User data for *pxFunc */
){
  Fts5Table *pTab = (Fts5Table*)pVtab;
  Fts5Auxiliary *pAux;

  for(pAux=pTab->pGlobal->pAux; pAux; pAux=pAux->pNext){
    if( sqlite3_stricmp(zName, pAux->zFunc)==0 ){
      *pxFunc = fts5ApiCallback;
      *ppArg = (void*)pAux;
      return 1;
    }
  }

  /* No function of the specified name was found. Return 0. */
  return 0;
}

/*
** Implementation of FTS3 xRename method. Rename an fts5 table.
*/

**
** Discard the contents of the pending terms table.
*/
static int fts5RollbackToMethod(sqlite3_vtab *pVtab, int iSavepoint){
  return SQLITE_OK;
}


/*
** Register a new auxiliary function with global context pGlobal.
*/
int sqlite3Fts5CreateAux(

  Fts5Global *pGlobal,            /* Global context (one per db handle) */
  const char *zName,              /* Name of new function */
  void *pUserData,                /* User data for aux. function */
  fts5_extension_function xFunc,  /* Aux. function implementation */
  void(*xDestroy)(void*)          /* Destructor for pUserData */

){
  int rc = sqlite3_overload_function(pGlobal->db, zName, -1);
  if( rc==SQLITE_OK ){
    Fts5Auxiliary *pAux;
    int nByte;                      /* Bytes of space to allocate */

    nByte = sizeof(Fts5Auxiliary) + strlen(zName) + 1;
    pAux = (Fts5Auxiliary*)sqlite3_malloc(nByte);
    if( pAux ){
      memset(pAux, 0, nByte);
      pAux->zFunc = (char*)&pAux[1];
      strcpy(pAux->zFunc, zName);
      pAux->pGlobal = pGlobal;
      pAux->pUserData = pUserData;
      pAux->xFunc = xFunc;
      pAux->xDestroy = xDestroy;
      pAux->pNext = pGlobal->pAux;
      pGlobal->pAux = pAux;
    }else{
      rc = SQLITE_NOMEM;
    }
  }

  return rc;
}

static void fts5ModuleDestroy(void *pCtx){
  Fts5Auxiliary *pAux;
  Fts5Auxiliary *pNext;
  Fts5Global *pGlobal = (Fts5Global*)pCtx;
  for(pAux=pGlobal->pAux; pAux; pAux=pNext){
    pNext = pAux->pNext;
    if( pAux->xDestroy ){
      pAux->xDestroy(pAux->pUserData);
    }
    sqlite3_free(pAux);
  }
  sqlite3_free(pGlobal);
}


int sqlite3Fts5Init(sqlite3 *db){
  static const sqlite3_module fts5Mod = {
    /* iVersion      */ 2,
    /* xCreate       */ fts5CreateMethod,
    /* xConnect      */ fts5ConnectMethod,
    /* xBestIndex    */ fts5BestIndexMethod,
    /* xDisconnect   */ fts5DisconnectMethod,
    /* xDestroy      */ fts5DestroyMethod,
    /* xOpen         */ fts5OpenMethod,
    /* xClose        */ fts5CloseMethod,
    /* xFilter       */ fts5FilterMethod,
    /* xNext         */ fts5NextMethod,
    /* xEof          */ fts5EofMethod,
    /* xColumn       */ fts5ColumnMethod,
    /* xRowid        */ fts5RowidMethod,
    /* xUpdate       */ fts5UpdateMethod,
    /* xBegin        */ fts5BeginMethod,
    /* xSync         */ fts5SyncMethod,
    /* xCommit       */ fts5CommitMethod,
    /* xRollback     */ fts5RollbackMethod,
    /* xFindFunction */ fts5FindFunctionMethod,
    /* xRename       */ fts5RenameMethod,
    /* xSavepoint    */ fts5SavepointMethod,
    /* xRelease      */ fts5ReleaseMethod,
    /* xRollbackTo   */ fts5RollbackToMethod,
  };

  int rc;
  Fts5Global *pGlobal = 0;
  pGlobal = (Fts5Global*)sqlite3_malloc(sizeof(Fts5Global));

  if( pGlobal==0 ){
    rc = SQLITE_NOMEM;
  }else{
    void *p = (void*)pGlobal;
    memset(pGlobal, 0, sizeof(Fts5Global));
    pGlobal->db = db;
    rc = sqlite3_create_module_v2(db, "fts5", &fts5Mod, p, fts5ModuleDestroy);
    if( rc==SQLITE_OK ) rc = sqlite3Fts5IndexInit(db);
    if( rc==SQLITE_OK ) rc = sqlite3Fts5ExprInit(db);
    if( rc==SQLITE_OK ) rc = sqlite3Fts5AuxInit(pGlobal);
  }
  return rc;
}

/*
** 2014 May 31
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
******************************************************************************
**
** Interfaces to extend FTS5. Using the interfaces defined in this file, 
** FTS5 may be extended with:
**
**     * custom tokenizers, and
**     * custom auxiliary functions.
*/


#ifndef _FTS5_H
#define _FTS5_H

#include "sqlite3.h"

/*************************************************************************
** CUSTOM AUXILIARY FUNCTIONS
**
** Virtual table implemenations may overload SQL functions by implementing
** the sqlite3_module.xFindFunction() method.
*/

typedef struct Fts5ExtensionApi Fts5ExtensionApi;
typedef struct Fts5Context Fts5Context;

typedef void (*fts5_extension_function)(
  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 */
);

/*
** xColumnCount:
**   Returns the number of columns in the FTS5 table.
**
** xPhraseCount:
**   Returns the number of phrases in the current query expression.
**
** xPhraseSize:
**   Returns the number of tokens in phrase iPhrase of the query. Phrases
**   are numbered starting from zero.
**
** xRowid:
**   Returns the rowid of the current row.
**
** xPoslist:
**   Iterate through instances of phrase iPhrase in the current row. 
*/
struct Fts5ExtensionApi {
  int iVersion;                   /* Currently always set to 1 */

  void *(*xUserData)(Fts5Context*);

  int (*xColumnCount)(Fts5Context*);
  int (*xColumnAvgSize)(Fts5Context*, int iCol, int *pnToken);
  int (*xTokenize)(Fts5Context*, 
    const char *pText, int nText, /* Text to tokenize */
    void *pCtx,                   /* Context passed to xToken() */
    int (*xToken)(void*, const char*, int, int, int, int)    /* Callback */
  );

  int (*xPhraseCount)(Fts5Context*);
  int (*xPhraseSize)(Fts5Context*, int iPhrase);

  sqlite3_int64 (*xRowid)(Fts5Context*);
  int (*xColumnText)(Fts5Context*, int iCol, const char **pz, int *pn);
  int (*xColumnSize)(Fts5Context*, int iCol, int *pnToken);
  int (*xPoslist)(Fts5Context*, int iPhrase, int *pi, int *piCol, int *piOff);
};

/* 
** CUSTOM AUXILIARY FUNCTIONS
*************************************************************************/
#endif /* _FTS5_H */

**
******************************************************************************
**
*/
#ifndef _FTS5INT_H
#define _FTS5INT_H

#include "fts5.h"
#include "sqliteInt.h"
#include "fts3_tokenizer.h"


/*
** Maximum number of prefix indexes on single FTS5 table. This must be
** less than 32. If it is set to anything large than that, an #error

typedef struct Fts5PoslistWriter Fts5PoslistWriter;
struct Fts5PoslistWriter {
  int iCol;
  int iOff;
};
int sqlite3Fts5PoslistWriterAppend(Fts5Buffer*, Fts5PoslistWriter*, i64);

int sqlite3Fts5PoslistNext(
  const u8 *a, int n,             /* Buffer containing poslist */
  int *pi,                        /* IN/OUT: Offset within a[] */
  int *piCol,                     /* IN/OUT: Current column */
  int *piOff                      /* IN/OUT: Current token offset */
);

/*
** End of interface to code in fts5_buffer.c.
**************************************************************************/

/**************************************************************************
** Interface to code in fts5_index.c. fts5_index.c contains contains code

i64 sqlite3Fts5ExprRowid(Fts5Expr*);

void sqlite3Fts5ExprFree(Fts5Expr*);

/* Called during startup to register a UDF with SQLite */
int sqlite3Fts5ExprInit(sqlite3*);

int sqlite3Fts5ExprPhraseCount(Fts5Expr*);
int sqlite3Fts5ExprPhraseSize(Fts5Expr*, int iPhrase);
int sqlite3Fts5ExprPoslist(Fts5Expr*, int, const u8 **);

/*******************************************
** The fts5_expr.c API above this point is used by the other hand-written
** C code in this module. The interfaces below this point are called by
** the parser code in fts5parse.y.  */

void sqlite3Fts5ParseError(Fts5Parse *pParse, const char *zFmt, ...);

void sqlite3Fts5ParseSetDistance(Fts5Parse*, Fts5ExprNearset*, Fts5Token*);
void sqlite3Fts5ParseSetColumn(Fts5Parse*, Fts5ExprNearset*, Fts5Token*);
void sqlite3Fts5ParseFinished(Fts5Parse *pParse, Fts5ExprNode *p);
void sqlite3Fts5ParseNear(Fts5Parse *pParse, Fts5Token*);


/*
** End of interface to code in fts5_expr.c.
**************************************************************************/


/**************************************************************************
** Interface to code in fts5.c. 
*/
typedef struct Fts5Global Fts5Global;

int sqlite3Fts5CreateAux(
    Fts5Global*, 
    const char*, 
    void*, 
    fts5_extension_function, 
    void(*)(void*)
);
/*
** End of interface to code in fts5.c.
**************************************************************************/


/**************************************************************************
** Interface to code in fts5_aux.c. 
*/

int sqlite3Fts5AuxInit(Fts5Global*);
/*
** End of interface to code in fts5_expr.c.
**************************************************************************/

#endif

/*
** 2014 May 31
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
******************************************************************************
*/

#include "fts5Int.h"

static void fts5SnippetFunction(
  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 */
){
  assert( 0 );
}

static void fts5TestFunction(
  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 */
){
  Fts5Buffer s;                   /* Build up text to return here */
  int nCol;                       /* Number of columns in table */
  int nPhrase;                    /* Number of phrases in query */
  i64 iRowid;                     /* Rowid of current row */
  const char *zReq = 0;
  int rc = SQLITE_OK;
  int i;

  if( nVal>=1 ){
    zReq = (const char*)sqlite3_value_text(apVal[0]);
  }

  memset(&s, 0, sizeof(Fts5Buffer));

  if( zReq==0 ){
    sqlite3Fts5BufferAppendPrintf(&rc, &s, "columncount ");
  }
  if( 0==zReq || 0==sqlite3_stricmp(zReq, "columncount") ){
    nCol = pApi->xColumnCount(pFts);
    sqlite3Fts5BufferAppendPrintf(&rc, &s, "%d", nCol);
  }

  if( zReq==0 ){
    sqlite3Fts5BufferAppendPrintf(&rc, &s, " phrasecount ");
  }
  nPhrase = pApi->xPhraseCount(pFts);
  if( 0==zReq || 0==sqlite3_stricmp(zReq, "phrasecount") ){
    sqlite3Fts5BufferAppendPrintf(&rc, &s, "%d", nPhrase);
  }

  if( zReq==0 ){
    sqlite3Fts5BufferAppendPrintf(&rc, &s, " phrasesize ");
  }
  if( 0==zReq || 0==sqlite3_stricmp(zReq, "phrasesize") ){
    if( nPhrase==1 ){
      int nSize = pApi->xPhraseSize(pFts, 0);
      sqlite3Fts5BufferAppendPrintf(&rc, &s, "%d", nSize);
    }else{
      sqlite3Fts5BufferAppendPrintf(&rc, &s, "{");
      for(i=0; i<nPhrase; i++){
        int nSize = pApi->xPhraseSize(pFts, i);
        sqlite3Fts5BufferAppendPrintf(&rc, &s, "%s%d", (i==0?"":" "), nSize);
      }
      sqlite3Fts5BufferAppendPrintf(&rc, &s, "}");
    }
  }

  if( zReq==0 ){
    sqlite3Fts5BufferAppendPrintf(&rc, &s, " poslist ");
  }
  if( 0==zReq || 0==sqlite3_stricmp(zReq, "poslist") ){
    sqlite3Fts5BufferAppendPrintf(&rc, &s, "{");
    for(i=0; i<nPhrase; i++){
      int j = 0;
      int iOff = 0;
      int iCol = 0;
      int bFirst = 1;
      sqlite3Fts5BufferAppendPrintf(&rc, &s, "%s{", (i==0?"":" "));
      while( 0==pApi->xPoslist(pFts, i, &j, &iCol, &iOff) ){
        sqlite3Fts5BufferAppendPrintf(
            &rc, &s, "%s%d.%d", (bFirst?"":" "), iCol, iOff
        );
        bFirst = 0;
      }
      sqlite3Fts5BufferAppendPrintf(&rc, &s, "}");
    }
    sqlite3Fts5BufferAppendPrintf(&rc, &s, "}");
  }

  if( zReq==0 ){
    sqlite3Fts5BufferAppendPrintf(&rc, &s, " rowid ");
  }
  if( 0==zReq || 0==sqlite3_stricmp(zReq, "rowid") ){
    iRowid = pApi->xRowid(pFts);
    sqlite3Fts5BufferAppendPrintf(&rc, &s, "%lld", iRowid);
  }

  if( rc==SQLITE_OK ){
    sqlite3_result_text(pCtx, (const char*)s.p, -1, SQLITE_TRANSIENT);
  }else{
    sqlite3_result_error_code(pCtx, rc);
  }
  sqlite3Fts5BufferFree(&s);
}

int sqlite3Fts5AuxInit(Fts5Global *pGlobal){
  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 [] = {
    { "snippet", 0, fts5SnippetFunction, 0 },
    { "fts5_test", 0, fts5TestFunction, 0 },
  };

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

  for(i=0; rc==SQLITE_OK && i<sizeof(aBuiltin)/sizeof(aBuiltin[0]); i++){
    rc = sqlite3Fts5CreateAux(pGlobal, 
        aBuiltin[i].zFunc,
        aBuiltin[i].pUserData,
        aBuiltin[i].xFunc,
        aBuiltin[i].xDestroy
    );
  }

  return rc;
}

    pWriter->iCol = iCol;
    pWriter->iOff = 0;
  }
  fts5BufferAppendVarint(&rc, pBuf, (iOff - pWriter->iOff) + 2);

  return rc;
}

int sqlite3Fts5PoslistNext(
  const u8 *a, int n,             /* Buffer containing poslist */
  int *pi,                        /* IN/OUT: Offset within a[] */
  int *piCol,                     /* IN/OUT: Current column */
  int *piOff                      /* IN/OUT: Current token offset */
){
  int i = *pi;
  int iVal;
  if( i>=n ){
    /* EOF */
    return 1;  
  }
  i += getVarint32(&a[i], iVal);
  if( iVal==1 ){
    i += getVarint32(&a[i], iVal);
    *piCol = iVal;
    *piOff = 0;
    i += getVarint32(&a[i], iVal);
  }
  *piOff += (iVal-2);
  *pi = i;
  return 0;
}

void sqlite3Fts5ParserFree(void*, void (*freeProc)(void*));
void sqlite3Fts5Parser(void*, int, Fts5Token, Fts5Parse*);

struct Fts5Expr {
  Fts5Index *pIndex;
  Fts5ExprNode *pRoot;
  int bAsc;
  int nPhrase;                    /* Number of phrases in expression */
  Fts5ExprPhrase **apPhrase;      /* Pointers to phrase objects */
};

/*
** eType:
**   Expression node type. Always one of:
**
**       FTS5_AND                 (pLeft, pRight valid)

/*
** Parse context.
*/
struct Fts5Parse {
  Fts5Config *pConfig;
  char *zErr;
  int rc;
  int nPhrase;                    /* Size of apPhrase array */
  Fts5ExprPhrase **apPhrase;      /* Array of all phrases */
  Fts5ExprNode *pExpr;            /* Result of a successful parse */
};

void sqlite3Fts5ParseError(Fts5Parse *pParse, const char *zFmt, ...){
  if( pParse->rc==SQLITE_OK ){
    va_list ap;
    va_start(ap, zFmt);

  if( sParse.rc==SQLITE_OK ){
    *ppNew = pNew = sqlite3_malloc(sizeof(Fts5Expr));
    if( pNew==0 ){
      sParse.rc = SQLITE_NOMEM;
    }else{
      pNew->pRoot = sParse.pExpr;
      pNew->pIndex = 0;
      pNew->apPhrase = sParse.apPhrase;
      pNew->nPhrase = sParse.nPhrase;
      sParse.apPhrase = 0;
    }
  }

  sqlite3_free(sParse.apPhrase);
  *pzErr = sParse.zErr;
  return sParse.rc;
}

/*
** Free the expression node object passed as the only argument.
*/

/*
** Free the expression object passed as the only argument.
*/
void sqlite3Fts5ExprFree(Fts5Expr *p){
  if( p ){
    sqlite3Fts5ParseNodeFree(p->pRoot);
    sqlite3_free(p->apPhrase);
    sqlite3_free(p);
  }
}

/*
** All individual term iterators in pPhrase are guaranteed to be valid and
** pointing to the same rowid when this function is called. This function 

  Fts5Token *pToken,              /* String to tokenize */
  int bPrefix                     /* True if there is a trailing "*" */
){
  Fts5Config *pConfig = pParse->pConfig;
  TokenCtx sCtx;                  /* Context object passed to callback */
  int rc;                         /* Tokenize return code */
  char *z = 0;

  if( pPhrase==0 ){
    if( (pParse->nPhrase % 8)==0 ){
      int nByte = sizeof(Fts5ExprPhrase*) * (pParse->nPhrase + 8);
      Fts5ExprPhrase **apNew;
      apNew = (Fts5ExprPhrase**)sqlite3_realloc(pParse->apPhrase, nByte);
      if( apNew==0 ) return 0;
      pParse->apPhrase = apNew;
    }
    pParse->nPhrase++;
  }

  pParse->rc = fts5ParseStringFromToken(pToken, &z);
  if( z==0 ) return 0;
  sqlite3Fts5Dequote(z);

  memset(&sCtx, 0, sizeof(TokenCtx));
  sCtx.pPhrase = pPhrase;
  rc = sqlite3Fts5Tokenize(pConfig, z, strlen(z), &sCtx, fts5ParseTokenize);
  if( rc ){
    pParse->rc = rc;
    fts5ExprPhraseFree(sCtx.pPhrase);
    sCtx.pPhrase = 0;
  }else if( sCtx.pPhrase->nTerm>0 ){
    sCtx.pPhrase->aTerm[sCtx.pPhrase->nTerm-1].bPrefix = bPrefix;
  }


  pParse->apPhrase[pParse->nPhrase-1] = sCtx.pPhrase;
  sqlite3_free(z);
  return sCtx.pPhrase;
}

/*
** Token pTok has appeared in a MATCH expression where the NEAR operator
** is expected. If token pTok does not contain "NEAR", store an error

  for(i=0; rc==SQLITE_OK && i<(sizeof(aFunc) / sizeof(aFunc[0])); i++){
    struct Fts5ExprFunc *p = &aFunc[i];
    rc = sqlite3_create_function(db, p->z, -1, SQLITE_UTF8, p->p, p->x, 0, 0);
  }

  return rc;
}

/*
** Return the number of phrases in expression pExpr.
*/
int sqlite3Fts5ExprPhraseCount(Fts5Expr *pExpr){
  return pExpr->nPhrase;
}

/*
** Return the number of terms in the iPhrase'th phrase in pExpr.
*/
int sqlite3Fts5ExprPhraseSize(Fts5Expr *pExpr, int iPhrase){
  if( iPhrase<0 || iPhrase>=pExpr->nPhrase ) return 0;
  return pExpr->apPhrase[iPhrase]->nTerm;
}

/*
** This function is used to access the current position list for phrase
** iPhrase.
*/
int sqlite3Fts5ExprPoslist(Fts5Expr *pExpr, int iPhrase, const u8 **pa){
  if( iPhrase<0 || iPhrase>=pExpr->nPhrase ){
    *pa = 0;
    return 0;
  }else{
    Fts5ExprPhrase *pPhrase = pExpr->apPhrase[iPhrase];
    *pa = pPhrase->poslist.p;
    return pPhrase->poslist.n;
  }
}

/*
** 2014 May 31
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
******************************************************************************
**
*/


// All token codes are small integers with #defines that begin with "TK_"
%token_prefix FTS5_

// The type of the data attached to each token is Token.  This is also the
// default type for non-terminals.
//
%token_type {Fts5Token}
%default_type {Fts5Token}

// The generated parser function takes a 4th argument as follows:
%extra_argument {Fts5Parse *pParse}

// This code runs whenever there is a syntax error
//
%syntax_error {
  sqlite3Fts5ParseError(
    pParse, "fts5: syntax error near \"%.*s\"",TOKEN.n,TOKEN.p
  );
}
%stack_overflow {
  assert( 0 );
}

// The name of the generated procedure that implements the parser
// is as follows:
%name sqlite3Fts5Parser

// The following text is included near the beginning of the C source
// code file that implements the parser.
//
%include {
#include "fts5Int.h"
#include "fts5parse.h"

/*
** Disable all error recovery processing in the parser push-down
** automaton.
*/
#define YYNOERRORRECOVERY 1

/*
** Make yytestcase() the same as testcase()
*/
#define yytestcase(X) testcase(X)

} // end %include

%left OR.
%left AND.
%left NOT.
%left COLON.

input ::= expr(X). { sqlite3Fts5ParseFinished(pParse, X); }

%type cnearset    {Fts5ExprNode*}
%type expr        {Fts5ExprNode*}
%type exprlist    {Fts5ExprNode*}
%destructor cnearset { sqlite3Fts5ParseNodeFree($$); }
%destructor expr     { sqlite3Fts5ParseNodeFree($$); }
%destructor exprlist { sqlite3Fts5ParseNodeFree($$); }

expr(A) ::= expr(X) AND expr(Y). {
  A = sqlite3Fts5ParseNode(pParse, FTS5_AND, X, Y, 0);
}
expr(A) ::= expr(X) OR expr(Y). {
  A = sqlite3Fts5ParseNode(pParse, FTS5_OR, X, Y, 0);
}
expr(A) ::= expr(X) NOT expr(Y). {
  A = sqlite3Fts5ParseNode(pParse, FTS5_NOT, X, Y, 0);
}

expr(A) ::= LP expr(X) RP. {A = X;}
expr(A) ::= exprlist(X).   {A = X;}

exprlist(A) ::= cnearset(X). {A = X;}
exprlist(A) ::= exprlist(X) cnearset(Y). {
  A = sqlite3Fts5ParseNode(pParse, FTS5_AND, X, Y, 0);
}

cnearset(A) ::= nearset(X). { 
  A = sqlite3Fts5ParseNode(pParse, FTS5_STRING, 0, 0, X); 
}
cnearset(A) ::= STRING(X) COLON nearset(Y). { 
  sqlite3Fts5ParseSetColumn(pParse, Y, &X);
  A = sqlite3Fts5ParseNode(pParse, FTS5_STRING, 0, 0, Y); 
}

%type nearset     {Fts5ExprNearset*}
%type nearphrases {Fts5ExprNearset*}
%destructor nearset { sqlite3Fts5ParseNearsetFree($$); }
%destructor nearphrases { sqlite3Fts5ParseNearsetFree($$); }

nearset(A) ::= phrase(X). { A = sqlite3Fts5ParseNearset(pParse, 0, X); }
nearset(A) ::= STRING(X) LP nearphrases(Y) neardist_opt(Z) RP. {
  sqlite3Fts5ParseNear(pParse, &X);
  sqlite3Fts5ParseSetDistance(pParse, Y, &Z);
  A = Y;
}

nearphrases(A) ::= phrase(X). { 
  A = sqlite3Fts5ParseNearset(pParse, 0, X); 
}
nearphrases(A) ::= nearphrases(X) phrase(Y). {
  A = sqlite3Fts5ParseNearset(pParse, X, Y);
}

/*
** The optional ", <integer>" at the end of the NEAR() arguments.
*/
neardist_opt(A) ::= . { A.p = 0; A.n = 0; }
neardist_opt(A) ::= COMMA STRING(X). { A = X; }

/*
** A phrase. A set of primitives connected by "+" operators. Examples:
**
**     "the" + "quick brown" + fo *
**     "the quick brown fo" *
**     the+quick+brown+fo*
*/
%type phrase {Fts5ExprPhrase*}
%destructor phrase { sqlite3Fts5ParsePhraseFree($$); }

phrase(A) ::= phrase(X) PLUS STRING(Y) star_opt(Z). { 
  A = sqlite3Fts5ParseTerm(pParse, X, &Y, Z);
}
phrase(A) ::= STRING(Y) star_opt(Z). { 
  A = sqlite3Fts5ParseTerm(pParse, 0, &Y, Z);
}

/*
** Optional "*" character.
*/
%type star_opt {int}

star_opt(A) ::= STAR. { A = 1; }
star_opt(A) ::= . { A = 0; }

         random.o resolve.o rowset.o rtree.o select.o status.o \
         table.o tokenize.o trigger.o \
         update.o util.o vacuum.o \
         vdbeapi.o vdbeaux.o vdbeblob.o vdbemem.o vdbesort.o \
	 vdbetrace.o wal.o walker.o where.o utf.o vtab.o

LIBOBJ += fts5.o
LIBOBJ += fts5_aux.o
LIBOBJ += fts5_buffer.o
LIBOBJ += fts5_config.o
LIBOBJ += fts5_expr.o
LIBOBJ += fts5_index.o
LIBOBJ += fts5_storage.o
LIBOBJ += fts5parse.o

  $(TOP)/ext/fts3/fts3_hash.h \
  $(TOP)/ext/fts3/fts3_tokenizer.h
EXTHDR += \
  $(TOP)/ext/rtree/rtree.h
EXTHDR += \
  $(TOP)/ext/icu/sqliteicu.h
EXTHDR += \
  $(TOP)/ext/fts5/fts5Int.h  \
  $(TOP)/ext/fts5/fts5.h 

# This is the default Makefile target.  The objects listed here
# are what get build when you type just "make" with no arguments.
#
all:	sqlite3.h libsqlite3.a sqlite3$(EXE)

libsqlite3.a:	$(LIBOBJ)

rtree.o:	$(TOP)/ext/rtree/rtree.c $(HDR) $(EXTHDR)
	$(TCCX) -DSQLITE_CORE -c $(TOP)/ext/rtree/rtree.c


# FTS5 things
#
fts5_aux.o:	$(TOP)/ext/fts5/fts5_aux.c $(HDR) $(EXTHDR)
	$(TCCX) -DSQLITE_CORE -c $(TOP)/ext/fts5/fts5_aux.c

fts5_buffer.o:	$(TOP)/ext/fts5/fts5_buffer.c $(HDR) $(EXTHDR)
	$(TCCX) -DSQLITE_CORE -c $(TOP)/ext/fts5/fts5_buffer.c

fts5_config.o:	$(TOP)/ext/fts5/fts5_config.c $(HDR) $(EXTHDR)
	$(TCCX) -DSQLITE_CORE -c $(TOP)/ext/fts5/fts5_config.c

fts5_expr.o:	$(TOP)/ext/fts5/fts5_expr.c $(HDR) $(EXTHDR)

do_test 1.1 {
  foreach {id x y} $data {
    execsql { INSERT INTO xx(rowid, x, y) VALUES($id, $x, $y) }
  }
} {}

proc phrasematch {phrase value} {
  if {[string first $phrase $value]>=0} { return 1 }


  return 0
}

# Usage:
#
proc nearmatch {nNear phraselist value} {
  set nPhrase [llength $phraselist]

    }
  }
  return $bMatch
}

# Usage:
#
#   poslist aCol ?-near N? ?-col C? -- phrase1 phrase2...
#
proc poslist {aCol args} {
  set O(-near) 10
  set O(-col)  -1

  set nOpt [lsearch -exact $args --]
  if {$nOpt<0} { error "no -- option" }

  foreach {k v} [lrange $args 0 [expr $nOpt-1]] {
    if {[info exists O($k)]==0} { error "unrecognized option $k" }
    set O($k) $v
  }

  # Set phraselist to be a list of phrases. nPhrase its length.
  set phraselist [lrange $args [expr $nOpt+1] end]
  set nPhrase [llength $phraselist]

  for {set j 0} {$j < [llength $aCol]} {incr j} {
    for {set i 0} {$i < $nPhrase} {incr i} { 
      set A($j,$i) [list]
    }
  }

  set iCol -1
  foreach col $aCol {
    incr iCol
    if {$O(-col)>=0 && $O(-col)!=$iCol} continue

    set nToken [llength $col]

    set iFL [expr $O(-near) >= $nToken ? $nToken - 1 : $O(-near)]
    for { } {$iFL < $nToken} {incr iFL} {
      for {set iPhrase 0} {$iPhrase<$nPhrase} {incr iPhrase} {
        set B($iPhrase) [list]

      }
      
      for {set iPhrase 0} {$iPhrase<$nPhrase} {incr iPhrase} {
        set p [lindex $phraselist $iPhrase]
        set nPm1 [expr {[llength $p] - 1}]
        set iFirst [expr $iFL - $O(-near) - [llength $p]]


        for {set i $iFirst} {$i <= $iFL} {incr i} {
          if {[lrange $col $i [expr $i+$nPm1]] == $p} { lappend B($iPhrase) $i }
        }
        if {[llength $B($iPhrase)] == 0} break
      }


      if {$iPhrase==$nPhrase} {
        for {set iPhrase 0} {$iPhrase<$nPhrase} {incr iPhrase} {

          set A($iCol,$iPhrase) [concat $A($iCol,$iPhrase) $B($iPhrase)]


          set A($iCol,$iPhrase) [lsort -integer -uniq $A($iCol,$iPhrase)]
        }
      }
    }

  }

  set res [list]
  for {set iPhrase 0} {$iPhrase<$nPhrase} {incr iPhrase} {
    set plist [list]
    for {set iCol 0} {$iCol < [llength $aCol]} {incr iCol} {
      foreach a $A($iCol,$iPhrase) {
        lappend plist "$iCol.$a"
      }
    }
    lappend res $plist
  }

  return $res
}

# Usage:
#
#   nearset aCol ?-near N? ?-col C? -- phrase1 phrase2...
#
proc nearset {args} {
  set plist [poslist {*}$args]
  return [expr [llength [lindex $plist 0]]>0]
}

# Argument $expr is an FTS5 match expression designed to be executed against
# an FTS5 table with the following schema:
# 
#   CREATE VIRTUAL TABLE xy USING fts5(x, y);
#
# Assuming the table contains the same records as stored int the global 
# $::data array (see above), this function returns a list containing one
# element for each match in the dataset. The elements are themselves lists
# formatted as follows:
#
#   <rowid> {<phrase 0 matches> <phrase 1 matches>...}
#
# where each <phrase X matches> element is a list of phrase matches in the
# same form as returned by auxiliary scalar function fts5_test().
#
proc matchdata {bPos expr {bAsc 0}} {

  set tclexpr [db one {SELECT fts5_expr_tcl($expr, 'nearset $cols', 'x', 'y')}]
  set res [list]

  #puts $tclexpr
  foreach {id x y} $::data {
    set cols [list $x $y]
    if $tclexpr {
      if {$bPos} {
        set N [regexp -all -inline {\[nearset [^\]]*\]} $tclexpr]
        set rowres [list]
        foreach phrase $N {
          set cmd "poslist [string range $phrase 9 end-1]"
          lappend rowres [eval $cmd]
        }
        if {[string first "\{" $rowres]<0} { set rowres "{{$rowres}}" }
        lappend res [list $id $rowres]
      } else {
        lappend res $id
      }
    }
  }

  if {$bAsc} {
    set res [lsort -integer -increasing -index 0 $res]
  } else {
    set res [lsort -integer -decreasing -index 0 $res]
  }

  return [concat {*}$res]
}


foreach {tn phrase} {
  1 "o"
  2 "b q"
  3 "e a e"
  4 "m d g q q b k b w f q q p p"
  5 "l o o l v v k"
  6 "a"
  7 "b"
  8 "c"
  9 "no"
  10 "L O O L V V K"
} {

  set expr "\"$phrase\""
  set res [matchdata 1 $expr]

  do_execsql_test 1.2.$tn.[llength $res] { 
    SELECT rowid, fts5_test(xx, 'poslist') FROM xx WHERE xx match $expr
  } $res
}

# Test the "nearmatch" commnad.
#
do_test 2.0 { nearmatch 2 {a b} {a x x b} } 1
do_test 2.1 { nearmatch 2 {b a} {a x x b} } 1
do_test 2.2 { nearmatch 1 {b a} {a x x b} } 0
do_test 2.3 { nearmatch 1 {"a b" "c d"} {x x a b x c d} } 1
do_test 2.4 { nearmatch 1 {"a b" "c d"} {x a b x x c d} } 0
do_test 2.5 { nearmatch 400 {a b} {a x x b} } 1
do_test 2.6 { nearmatch 0 {a} {a x x b} } 1
do_test 2.7 { nearmatch 0 {b} {a x x b} } 1

do_test 2.8  { poslist {{a b c}} -- a } {0.0}
do_test 2.9  { poslist {{a b c}} -- c } {0.2}


foreach {tn expr tclexpr} {
  1 {a b} {[N $x -- {a}] && [N $x -- {b}]}
} {
  do_execsql_test 3.$tn {SELECT fts5_expr_tcl($expr, 'N $x')} [list $tclexpr]
}

#-------------------------------------------------------------------------
#
foreach {bAsc sql} {
  0 {SELECT rowid FROM xx WHERE xx MATCH $expr}
  1 {SELECT rowid FROM xx WHERE xx MATCH $expr ORDER BY rowid ASC}
} {
  foreach {tn expr} {
    0.1 x

    1 { NEAR(r c) }
    2 { NEAR(r c, 5) }
    3 { NEAR(r c, 3) }
    4 { NEAR(r c, 2) }
    5 { NEAR(r c, 0) }
    6 { NEAR(a b c) }
    7 { NEAR(a b c, 8) }

    14b { a OR b }
    15 { a OR b AND c }
    16 { c AND b OR a }
    17 { c AND (b OR a) }
    18 { c NOT (b OR a) }
    19 { c NOT b OR a AND d }
  } {
    set res [matchdata 0 $expr $bAsc]
    do_execsql_test 4.$bAsc.$tn.[llength $res] $sql $res
  }
}



finish_test