SQLite

  $(TOP)/src/test_backup.c \
  $(TOP)/src/test_btree.c \
  $(TOP)/src/test_config.c \
  $(TOP)/src/test_demovfs.c \
  $(TOP)/src/test_devsym.c \
  $(TOP)/src/test_fs.c \
  $(TOP)/src/test_func.c \

  $(TOP)/src/test_hexio.c \
  $(TOP)/src/test_init.c \
  $(TOP)/src/test_intarray.c \
  $(TOP)/src/test_journal.c \
  $(TOP)/src/test_malloc.c \
  $(TOP)/src/test_multiplex.c \
  $(TOP)/src/test_mutex.c \
  $(TOP)/src/test_onefile.c \
  $(TOP)/src/test_osinst.c \
  $(TOP)/src/test_pcache.c \
  $(TOP)/src/test_quota.c \

  $(TOP)/src/test_rtree.c \
  $(TOP)/src/test_schema.c \
  $(TOP)/src/test_server.c \
  $(TOP)/src/test_superlock.c \
  $(TOP)/src/test_syscall.c \
  $(TOP)/src/test_stat.c \
  $(TOP)/src/test_tclvar.c \
  $(TOP)/src/test_thread.c \
  $(TOP)/src/test_vfs.c \

  $(TOP)/src/test_wsd.c       \
  $(TOP)/ext/fts3/fts3_term.c \
  $(TOP)/ext/fts3/fts3_test.c 

# Statically linked extensions
#
TESTSRC += \
  $(TOP)/ext/misc/amatch.c \
  $(TOP)/ext/misc/closure.c \
  $(TOP)/ext/misc/fuzzer.c \
  $(TOP)/ext/misc/ieee754.c \
  $(TOP)/ext/misc/nextchar.c \
  $(TOP)/ext/misc/regexp.c \
  $(TOP)/ext/misc/spellfix.c \
  $(TOP)/ext/misc/wholenumber.c

# Source code to the library files needed by the test fixture
#
TESTSRC2 = \
  $(TOP)/src/attach.c \
  $(TOP)/src/backup.c \
  $(TOP)/src/bitvec.c \
  $(TOP)/src/btree.c \

  $(TOP)\src\test_backup.c \
  $(TOP)\src\test_btree.c \
  $(TOP)\src\test_config.c \
  $(TOP)\src\test_demovfs.c \
  $(TOP)\src\test_devsym.c \
  $(TOP)\src\test_fs.c \
  $(TOP)\src\test_func.c \

  $(TOP)\src\test_hexio.c \
  $(TOP)\src\test_init.c \
  $(TOP)\src\test_intarray.c \
  $(TOP)\src\test_journal.c \
  $(TOP)\src\test_malloc.c \
  $(TOP)\src\test_multiplex.c \
  $(TOP)\src\test_mutex.c \
  $(TOP)\src\test_onefile.c \
  $(TOP)\src\test_osinst.c \
  $(TOP)\src\test_pcache.c \
  $(TOP)\src\test_quota.c \

  $(TOP)\src\test_rtree.c \
  $(TOP)\src\test_schema.c \
  $(TOP)\src\test_server.c \
  $(TOP)\src\test_superlock.c \
  $(TOP)\src\test_syscall.c \
  $(TOP)\src\test_stat.c \
  $(TOP)\src\test_tclvar.c \
  $(TOP)\src\test_thread.c \
  $(TOP)\src\test_vfs.c \

  $(TOP)\src\test_wsd.c \
  $(TOP)\ext\fts3\fts3_term.c \
  $(TOP)\ext\fts3\fts3_test.c

# Statically linked extensions
#
TESTEXT = \
  $(TOP)\ext\misc\amatch.c \
  $(TOP)\ext\misc\closure.c \
  $(TOP)\ext\misc\fuzzer.c \
  $(TOP)\ext\misc\ieee754.c \
  $(TOP)\ext\misc\nextchar.c \
  $(TOP)\ext\misc\regexp.c \
  $(TOP)\ext\misc\spellfix.c \
  $(TOP)\ext\misc\wholenumber.c


# Source code to the library files needed by the test fixture
#
TESTSRC2 = \
  $(TOP)\src\attach.c \
  $(TOP)\src\backup.c \
  $(TOP)\src\bitvec.c \

# fixture.  Otherwise link against libsqlite3.lib.  (This distinction is
# necessary because the test fixture requires non-API symbols which are
# hidden when the library is built via the amalgamation).
#
TESTFIXTURE_FLAGS = -DTCLSH=1 -DSQLITE_TEST=1 -DSQLITE_CRASH_TEST=1
TESTFIXTURE_FLAGS = $(TESTFIXTURE_FLAGS) -DSQLITE_SERVER=1 -DSQLITE_PRIVATE="" -DSQLITE_CORE

TESTFIXTURE_SRC0 = $(TESTEXT) $(TESTSRC2) libsqlite3.lib
TESTFIXTURE_SRC1 = $(TESTEXT) sqlite3.c
!IF $(USE_AMALGAMATION)==0
TESTFIXTURE_SRC = $(TESTSRC) $(TOP)\src\tclsqlite.c $(TESTFIXTURE_SRC0)
!ELSE
TESTFIXTURE_SRC = $(TESTSRC) $(TOP)\src\tclsqlite.c $(TESTFIXTURE_SRC1)
!ENDIF

testfixture.exe:	$(TESTFIXTURE_SRC) $(LIBRESOBJS) $(HDR)

/*
** 2013-03-14
**
** 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.
**
*************************************************************************
**
** This file contains code for a demonstration virtual table that finds
** "approximate matches" - strings from a finite set that are nearly the
** same as a single input string.  The virtual table is called "amatch".
**
** A amatch virtual table is created like this:
**
**     CREATE VIRTUAL TABLE f USING approximate_match(
**        vocabulary_table=<tablename>,      -- V
**        vocabulary_word=<columnname>,      -- W
**        vocabulary_language=<columnname>,  -- L
**        edit_distances=<edit-cost-table>
**     );
**
** When it is created, the new amatch table must be supplied with the
** the name of a table V and columns V.W and V.L such that 
**
**     SELECT W FROM V WHERE L=$language
**
** returns the allowed vocabulary for the match.  If the "vocabulary_language"
** or L columnname is left unspecified or is an empty string, then no
** filtering of the vocabulary by language is performed. 
**
** For efficiency, it is essential that the vocabulary table be indexed:
**
**     CREATE vocab_index ON V(W)
**
** A separate edit-cost-table provides scoring information that defines 
** what it means for one string to be "close" to another.
**
** The edit-cost-table must contain exactly four columns (more precisely,
** the statement "SELECT * FROM <edit-cost-table>" must return records
** that consist of four columns). It does not matter what the columns are
** named. 
**
** Each row in the edit-cost-table represents a single character
** transformation going from user input to the vocabulary. The leftmost 
** column of the row (column 0) contains an integer identifier of the
** language to which the transformation rule belongs (see "MULTIPLE LANGUAGES"
** below). The second column of the row (column 1) contains the input
** character or characters - the characters of user input. The third 
** column contains characters as they appear in the vocabulary table.
** And the fourth column contains the integer cost of making the
** transformation. For example:
**
**    CREATE TABLE f_data(iLang, cFrom, cTo, Cost);
**    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, '', 'a', 100);
**    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, 'b', '', 87);
**    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, 'o', 'oe', 38);
**    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, 'oe', 'o', 40);
**
** The first row inserted into the edit-cost-table by the SQL script
** above indicates that the cost of having an extra 'a' in the vocabulary
** table that is missing in the user input 100.  (All costs are integers.
** Overall cost must not exceed 16777216.)  The second INSERT statement 
** creates a rule saying that the cost of having a single letter 'b' in
** user input which is missing in the vocabulary table is 87.  The third
** INSERT statement mean that the cost of matching an 'o' in user input 
** against an 'oe' in the vocabulary table is 38.  And so forth.
**
** The following rules are special:
**
**    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, '?', '', 97);
**    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, '', '?', 98);
**    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, '?', '?', 99);
**
** The '?' to '' rule is the cost of having any single character in the input
** that is not found in the vocabular.  The '' to '?' rule is the cost of
** having a character in the vocabulary table that is missing from input.
** And the '?' to '?' rule is the cost of doing an arbitrary character
** substitution.  These three generic rules apply across all languages.
** In other words, the iLang field is ignored for the generic substitution
** rules.  If more than one cost is given for a generic substitution rule,
** then the lowest cost is used.
**
** Once it has been created, the amatch virtual table can be queried
** as follows:
**
**    SELECT word, distance FROM f
**     WHERE word MATCH 'abcdefg'
**       AND distance<200;
**
** This query outputs the strings contained in the T(F) field that
** are close to "abcdefg" and in order of increasing distance.  No string
** is output more than once.  If there are multiple ways to transform the
** target string ("abcdefg") into a string in the vocabulary table then
** the lowest cost transform is the one that is returned.  In this example,
** the search is limited to strings with a total distance of less than 200.
**
** For efficiency, it is important to put tight bounds on the distance.
** The time and memory space needed to perform this query is exponential
** in the maximum distance.  A good rule of thumb is to limit the distance
** to no more than 1.5 or 2 times the maximum cost of any rule in the
** edit-cost-table.
**
** The amatch is a read-only table.  Any attempt to DELETE, INSERT, or
** UPDATE on a amatch table will throw an error.
**
** It is important to put some kind of a limit on the amatch output.  This
** can be either in the form of a LIMIT clause at the end of the query,
** or better, a "distance<NNN" constraint where NNN is some number.  The
** running time and memory requirement is exponential in the value of NNN 
** so you want to make sure that NNN is not too big.  A value of NNN that
** is about twice the average transformation cost seems to give good results.
**
** The amatch table can be useful for tasks such as spelling correction.
** Suppose all allowed words are in table vocabulary(w).  Then one would create
** an amatch virtual table like this:
**
**   CREATE VIRTUAL TABLE ex1 USING amatch(
**       vocabtable=vocabulary,
**       vocabcolumn=w,
**       edit_distances=ec1
**   );
**
** Then given an input word $word, look up close spellings this way:
**
**   SELECT word, distance FROM ex1
**    WHERE word MATCH $word AND distance<200;
**
** MULTIPLE LANGUAGES
**
** Normally, the "iLang" value associated with all character transformations
** in the edit-cost-table is zero. However, if required, the amatch 
** virtual table allows multiple languages to be defined. Each query uses 
** only a single iLang value.   This allows, for example, a single 
** amatch table to support multiple languages.
**
** By default, only the rules with iLang=0 are used. To specify an 
** alternative language, a "language = ?" expression must be added to the
** WHERE clause of a SELECT, where ? is the integer identifier of the desired 
** language. For example:
**
**   SELECT word, distance FROM ex1
**    WHERE word MATCH $word
**      AND distance<=200
**      AND language=1 -- Specify use language 1 instead of 0
**
** If no "language = ?" constraint is specified in the WHERE clause, language
** 0 is used.
**
** LIMITS
**
** The maximum language number is 2147483647.  The maximum length of either
** of the strings in the second or third column of the amatch data table
** is 50 bytes.  The maximum cost on a rule is 1000.
*/
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <ctype.h>

/*
** Forward declaration of objects used by this implementation
*/
typedef struct amatch_vtab amatch_vtab;
typedef struct amatch_cursor amatch_cursor;
typedef struct amatch_rule amatch_rule;
typedef struct amatch_word amatch_word;
typedef struct amatch_avl amatch_avl;


/*****************************************************************************
** AVL Tree implementation
*/
/*
** Objects that want to be members of the AVL tree should embedded an
** instance of this structure.
*/
struct amatch_avl {
  amatch_word *pWord;   /* Points to the object being stored in the tree */
  char *zKey;           /* Key.  zero-terminated string.  Must be unique */
  amatch_avl *pBefore;  /* Other elements less than zKey */
  amatch_avl *pAfter;   /* Other elements greater than zKey */
  amatch_avl *pUp;      /* Parent element */
  short int height;     /* Height of this node.  Leaf==1 */
  short int imbalance;  /* Height difference between pBefore and pAfter */
};

/* Recompute the amatch_avl.height and amatch_avl.imbalance fields for p.
** Assume that the children of p have correct heights.
*/
static void amatchAvlRecomputeHeight(amatch_avl *p){
  short int hBefore = p->pBefore ? p->pBefore->height : 0;
  short int hAfter = p->pAfter ? p->pAfter->height : 0;
  p->imbalance = hBefore - hAfter;  /* -: pAfter higher.  +: pBefore higher */
  p->height = (hBefore>hAfter ? hBefore : hAfter)+1;
}

/*
**     P                B
**    / \              / \
**   B   Z    ==>     X   P
**  / \                  / \
** X   Y                Y   Z
**
*/
static amatch_avl *amatchAvlRotateBefore(amatch_avl *pP){
  amatch_avl *pB = pP->pBefore;
  amatch_avl *pY = pB->pAfter;
  pB->pUp = pP->pUp;
  pB->pAfter = pP;
  pP->pUp = pB;
  pP->pBefore = pY;
  if( pY ) pY->pUp = pP;
  amatchAvlRecomputeHeight(pP);
  amatchAvlRecomputeHeight(pB);
  return pB;
}

/*
**     P                A
**    / \              / \
**   X   A    ==>     P   Z
**      / \          / \
**     Y   Z        X   Y
**
*/
static amatch_avl *amatchAvlRotateAfter(amatch_avl *pP){
  amatch_avl *pA = pP->pAfter;
  amatch_avl *pY = pA->pBefore;
  pA->pUp = pP->pUp;
  pA->pBefore = pP;
  pP->pUp = pA;
  pP->pAfter = pY;
  if( pY ) pY->pUp = pP;
  amatchAvlRecomputeHeight(pP);
  amatchAvlRecomputeHeight(pA);
  return pA;
}

/*
** Return a pointer to the pBefore or pAfter pointer in the parent
** of p that points to p.  Or if p is the root node, return pp.
*/
static amatch_avl **amatchAvlFromPtr(amatch_avl *p, amatch_avl **pp){
  amatch_avl *pUp = p->pUp;
  if( pUp==0 ) return pp;
  if( pUp->pAfter==p ) return &pUp->pAfter;
  return &pUp->pBefore;
}

/*
** Rebalance all nodes starting with p and working up to the root.
** Return the new root.
*/
static amatch_avl *amatchAvlBalance(amatch_avl *p){
  amatch_avl *pTop = p;
  amatch_avl **pp;
  while( p ){
    amatchAvlRecomputeHeight(p);
    if( p->imbalance>=2 ){
      amatch_avl *pB = p->pBefore;
      if( pB->imbalance<0 ) p->pBefore = amatchAvlRotateAfter(pB);
      pp = amatchAvlFromPtr(p,&p);
      p = *pp = amatchAvlRotateBefore(p);
    }else if( p->imbalance<=(-2) ){
      amatch_avl *pA = p->pAfter;
      if( pA->imbalance>0 ) p->pAfter = amatchAvlRotateBefore(pA);
      pp = amatchAvlFromPtr(p,&p);
      p = *pp = amatchAvlRotateAfter(p);
    }
    pTop = p;
    p = p->pUp;
  }
  return pTop;
}

/* Search the tree rooted at p for an entry with zKey.  Return a pointer
** to the entry or return NULL.
*/
static amatch_avl *amatchAvlSearch(amatch_avl *p, const char *zKey){
  int c;
  while( p && (c = strcmp(zKey, p->zKey))!=0 ){
    p = (c<0) ? p->pBefore : p->pAfter;
  }
  return p;
}

/* Find the first node (the one with the smallest key).
*/
static amatch_avl *amatchAvlFirst(amatch_avl *p){
  if( p ) while( p->pBefore ) p = p->pBefore;
  return p;
}

#if 0 /* NOT USED */
/* Return the node with the next larger key after p.
*/
static amatch_avl *amatchAvlNext(amatch_avl *p){
  amatch_avl *pPrev = 0;
  while( p && p->pAfter==pPrev ){
    pPrev = p;
    p = p->pUp;
  }
  if( p && pPrev==0 ){
    p = amatchAvlFirst(p->pAfter);
  }
  return p;
}
#endif

#if 0 /* NOT USED */
/* Verify AVL tree integrity
*/
static int amatchAvlIntegrity(amatch_avl *pHead){
  amatch_avl *p;
  if( pHead==0 ) return 1;
  if( (p = pHead->pBefore)!=0 ){
    assert( p->pUp==pHead );
    assert( amatchAvlIntegrity(p) );
    assert( strcmp(p->zKey, pHead->zKey)<0 );
    while( p->pAfter ) p = p->pAfter;
    assert( strcmp(p->zKey, pHead->zKey)<0 );
  }
  if( (p = pHead->pAfter)!=0 ){
    assert( p->pUp==pHead );
    assert( amatchAvlIntegrity(p) );
    assert( strcmp(p->zKey, pHead->zKey)>0 );
    p = amatchAvlFirst(p);
    assert( strcmp(p->zKey, pHead->zKey)>0 );
  }
  return 1;
}
static int amatchAvlIntegrity2(amatch_avl *pHead){
  amatch_avl *p, *pNext;
  for(p=amatchAvlFirst(pHead); p; p=pNext){
    pNext = amatchAvlNext(p);
    if( pNext==0 ) break;
    assert( strcmp(p->zKey, pNext->zKey)<0 );
  }
  return 1;
}
#endif

/* Insert a new node pNew.  Return NULL on success.  If the key is not
** unique, then do not perform the insert but instead leave pNew unchanged
** and return a pointer to an existing node with the same key.
*/
static amatch_avl *amatchAvlInsert(amatch_avl **ppHead, amatch_avl *pNew){
  int c;
  amatch_avl *p = *ppHead;
  if( p==0 ){
    p = pNew;
    pNew->pUp = 0;
  }else{
    while( p ){
      c = strcmp(pNew->zKey, p->zKey);
      if( c<0 ){
        if( p->pBefore ){
          p = p->pBefore;
        }else{
          p->pBefore = pNew;
          pNew->pUp = p;
          break;
        }
      }else if( c>0 ){
        if( p->pAfter ){
          p = p->pAfter;
        }else{
          p->pAfter = pNew;
          pNew->pUp = p;
          break;
        }
      }else{
        return p;
      }
    }
  }
  pNew->pBefore = 0;
  pNew->pAfter = 0;
  pNew->height = 1;
  pNew->imbalance = 0;
  *ppHead = amatchAvlBalance(p);
  /* assert( amatchAvlIntegrity(*ppHead) ); */
  /* assert( amatchAvlIntegrity2(*ppHead) ); */
  return 0;
}

/* Remove node pOld from the tree.  pOld must be an element of the tree or
** the AVL tree will become corrupt.
*/
static void amatchAvlRemove(amatch_avl **ppHead, amatch_avl *pOld){
  amatch_avl **ppParent;
  amatch_avl *pBalance;
  /* assert( amatchAvlSearch(*ppHead, pOld->zKey)==pOld ); */
  ppParent = amatchAvlFromPtr(pOld, ppHead);
  if( pOld->pBefore==0 && pOld->pAfter==0 ){
    *ppParent = 0;
    pBalance = pOld->pUp;
  }else if( pOld->pBefore && pOld->pAfter ){
    amatch_avl *pX, *pY;
    pX = amatchAvlFirst(pOld->pAfter);
    *amatchAvlFromPtr(pX, 0) = pX->pAfter;
    if( pX->pAfter ) pX->pAfter->pUp = pX->pUp;
    pBalance = pX->pUp;
    pX->pAfter = pOld->pAfter;
    if( pX->pAfter ){
      pX->pAfter->pUp = pX;
    }else{
      assert( pBalance==pOld );
      pBalance = pX;
    }
    pX->pBefore = pY = pOld->pBefore;
    if( pY ) pY->pUp = pX;
    pX->pUp = pOld->pUp;
    *ppParent = pX;
  }else if( pOld->pBefore==0 ){
    *ppParent = pBalance = pOld->pAfter;
    pBalance->pUp = pOld->pUp;
  }else if( pOld->pAfter==0 ){
    *ppParent = pBalance = pOld->pBefore;
    pBalance->pUp = pOld->pUp;
  }
  *ppHead = amatchAvlBalance(pBalance);
  pOld->pUp = 0;
  pOld->pBefore = 0;
  pOld->pAfter = 0;
  /* assert( amatchAvlIntegrity(*ppHead) ); */
  /* assert( amatchAvlIntegrity2(*ppHead) ); */
}
/*
** End of the AVL Tree implementation
******************************************************************************/


/*
** Various types.
**
** amatch_cost is the "cost" of an edit operation.
**
** amatch_len is the length of a matching string.  
**
** amatch_langid is an ruleset identifier.
*/
typedef int amatch_cost;
typedef signed char amatch_len;
typedef int amatch_langid;

/*
** Limits
*/
#define AMATCH_MX_LENGTH          50  /* Maximum length of a rule string */
#define AMATCH_MX_LANGID  2147483647  /* Maximum rule ID */
#define AMATCH_MX_COST          1000  /* Maximum single-rule cost */

/*
** A match or partial match
*/
struct amatch_word {
  amatch_word *pNext;   /* Next on a list of all amatch_words */
  amatch_avl sCost;     /* Linkage of this node into the cost tree */
  amatch_avl sWord;     /* Linkage of this node into the word tree */
  amatch_cost rCost;    /* Cost of the match so far */
  int iSeq;             /* Sequence number */
  char zCost[10];       /* Cost key (text rendering of rCost) */
  short int nMatch;     /* Input characters matched */
  char zWord[4];        /* Text of the word.  Extra space appended as needed */
};

/*
** Each transformation rule is stored as an instance of this object.
** All rules are kept on a linked list sorted by rCost.
*/
struct amatch_rule {
  amatch_rule *pNext;      /* Next rule in order of increasing rCost */
  char *zFrom;             /* Transform from (a string from user input) */
  amatch_cost rCost;       /* Cost of this transformation */
  amatch_langid iLang;     /* The langauge to which this rule belongs */
  amatch_len nFrom, nTo;   /* Length of the zFrom and zTo strings */
  char zTo[4];             /* Tranform to V.W value (extra space appended) */
};

/* 
** A amatch virtual-table object 
*/
struct amatch_vtab {
  sqlite3_vtab base;         /* Base class - must be first */
  char *zClassName;          /* Name of this class.  Default: "amatch" */
  char *zDb;                 /* Name of database.  (ex: "main") */
  char *zSelf;               /* Name of this virtual table */
  char *zCostTab;            /* Name of edit-cost-table */
  char *zVocabTab;           /* Name of vocabulary table */
  char *zVocabWord;          /* Name of vocabulary table word column */
  char *zVocabLang;          /* Name of vocabulary table language column */
  amatch_rule *pRule;        /* All active rules in this amatch */
  amatch_cost rIns;          /* Generic insertion cost  '' -> ? */
  amatch_cost rDel;          /* Generic deletion cost  ? -> '' */
  amatch_cost rSub;          /* Generic substitution cost ? -> ? */
  sqlite3 *db;               /* The database connection */
  sqlite3_stmt *pVCheck;     /* Query to check zVocabTab */
  int nCursor;               /* Number of active cursors */
};

/* A amatch cursor object */
struct amatch_cursor {
  sqlite3_vtab_cursor base;  /* Base class - must be first */
  sqlite3_int64 iRowid;      /* The rowid of the current word */
  amatch_langid iLang;       /* Use this language ID */
  amatch_cost rLimit;        /* Maximum cost of any term */
  int nBuf;                  /* Space allocated for zBuf */
  int oomErr;                /* True following an OOM error */
  int nWord;                 /* Number of amatch_word objects */
  char *zBuf;                /* Temp-use buffer space */
  char *zInput;              /* Input word to match against */
  amatch_vtab *pVtab;        /* The virtual table this cursor belongs to */
  amatch_word *pAllWords;    /* List of all amatch_word objects */
  amatch_word *pCurrent;     /* Most recent solution */
  amatch_avl *pCost;         /* amatch_word objects keyed by iCost */
  amatch_avl *pWord;         /* amatch_word objects keyed by zWord */
};

/*
** The two input rule lists are both sorted in order of increasing
** cost.  Merge them together into a single list, sorted by cost, and
** return a pointer to the head of that list.
*/
static amatch_rule *amatchMergeRules(amatch_rule *pA, amatch_rule *pB){
  amatch_rule head;
  amatch_rule *pTail;

  pTail =  &head;
  while( pA && pB ){
    if( pA->rCost<=pB->rCost ){
      pTail->pNext = pA;
      pTail = pA;
      pA = pA->pNext;
    }else{
      pTail->pNext = pB;
      pTail = pB;
      pB = pB->pNext;
    }
  }
  if( pA==0 ){
    pTail->pNext = pB;
  }else{
    pTail->pNext = pA;
  }
  return head.pNext;
}

/*
** Statement pStmt currently points to a row in the amatch data table. This
** function allocates and populates a amatch_rule structure according to
** the content of the row.
**
** If successful, *ppRule is set to point to the new object and SQLITE_OK
** is returned. Otherwise, *ppRule is zeroed, *pzErr may be set to point
** to an error message and an SQLite error code returned.
*/
static int amatchLoadOneRule(
  amatch_vtab *p,                 /* Fuzzer virtual table handle */
  sqlite3_stmt *pStmt,            /* Base rule on statements current row */
  amatch_rule **ppRule,           /* OUT: New rule object */
  char **pzErr                    /* OUT: Error message */
){
  sqlite3_int64 iLang = sqlite3_column_int64(pStmt, 0);
  const char *zFrom = (const char *)sqlite3_column_text(pStmt, 1);
  const char *zTo = (const char *)sqlite3_column_text(pStmt, 2);
  amatch_cost rCost = sqlite3_column_int(pStmt, 3);

  int rc = SQLITE_OK;             /* Return code */
  int nFrom;                      /* Size of string zFrom, in bytes */
  int nTo;                        /* Size of string zTo, in bytes */
  amatch_rule *pRule = 0;         /* New rule object to return */

  if( zFrom==0 ) zFrom = "";
  if( zTo==0 ) zTo = "";
  nFrom = (int)strlen(zFrom);
  nTo = (int)strlen(zTo);

  /* Silently ignore null transformations */
  if( strcmp(zFrom, zTo)==0 ){
    if( zFrom[0]=='?' && zFrom[1]==0 ){
      if( p->rSub==0 || p->rSub>rCost ) p->rSub = rCost;
    }
    *ppRule = 0;
    return SQLITE_OK;
  }

  if( rCost<=0 || rCost>AMATCH_MX_COST ){
    *pzErr = sqlite3_mprintf("%s: cost must be between 1 and %d", 
        p->zClassName, AMATCH_MX_COST
    );
    rc = SQLITE_ERROR;
  }else
  if( nFrom>AMATCH_MX_LENGTH || nTo>AMATCH_MX_LENGTH ){
    *pzErr = sqlite3_mprintf("%s: maximum string length is %d", 
        p->zClassName, AMATCH_MX_LENGTH
    );
    rc = SQLITE_ERROR;    
  }else
  if( iLang<0 || iLang>AMATCH_MX_LANGID ){
    *pzErr = sqlite3_mprintf("%s: iLang must be between 0 and %d", 
        p->zClassName, AMATCH_MX_LANGID
    );
    rc = SQLITE_ERROR;    
  }else
  if( strcmp(zFrom,"")==0 && strcmp(zTo,"?")==0 ){
    if( p->rIns==0 || p->rIns>rCost ) p->rIns = rCost;
  }else
  if( strcmp(zFrom,"?")==0 && strcmp(zTo,"")==0 ){
    if( p->rDel==0 || p->rDel>rCost ) p->rDel = rCost;
  }else
  {
    pRule = sqlite3_malloc( sizeof(*pRule) + nFrom + nTo );
    if( pRule==0 ){
      rc = SQLITE_NOMEM;
    }else{
      memset(pRule, 0, sizeof(*pRule));
      pRule->zFrom = &pRule->zTo[nTo+1];
      pRule->nFrom = nFrom;
      memcpy(pRule->zFrom, zFrom, nFrom+1);
      memcpy(pRule->zTo, zTo, nTo+1);
      pRule->nTo = nTo;
      pRule->rCost = rCost;
      pRule->iLang = (int)iLang;
    }
  }

  *ppRule = pRule;
  return rc;
}

/*
** Free all the content in the edit-cost-table
*/
static void amatchFreeRules(amatch_vtab *p){
  while( p->pRule ){
    amatch_rule *pRule = p->pRule;
    p->pRule = pRule->pNext;
    sqlite3_free(pRule);
  }
  p->pRule = 0;
}

/*
** Load the content of the amatch data table into memory.
*/
static int amatchLoadRules(
  sqlite3 *db,                    /* Database handle */
  amatch_vtab *p,                 /* Virtual amatch table to configure */
  char **pzErr                    /* OUT: Error message */
){
  int rc = SQLITE_OK;             /* Return code */
  char *zSql;                     /* SELECT used to read from rules table */
  amatch_rule *pHead = 0;

  zSql = sqlite3_mprintf("SELECT * FROM %Q.%Q", p->zDb, p->zCostTab);
  if( zSql==0 ){
    rc = SQLITE_NOMEM;
  }else{
    int rc2;                      /* finalize() return code */
    sqlite3_stmt *pStmt = 0;
    rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0);
    if( rc!=SQLITE_OK ){
      *pzErr = sqlite3_mprintf("%s: %s", p->zClassName, sqlite3_errmsg(db));
    }else if( sqlite3_column_count(pStmt)!=4 ){
      *pzErr = sqlite3_mprintf("%s: %s has %d columns, expected 4",
          p->zClassName, p->zCostTab, sqlite3_column_count(pStmt)
      );
      rc = SQLITE_ERROR;
    }else{
      while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pStmt) ){
        amatch_rule *pRule = 0;
        rc = amatchLoadOneRule(p, pStmt, &pRule, pzErr);
        if( pRule ){
          pRule->pNext = pHead;
          pHead = pRule;
        }
      }
    }
    rc2 = sqlite3_finalize(pStmt);
    if( rc==SQLITE_OK ) rc = rc2;
  }
  sqlite3_free(zSql);

  /* All rules are now in a singly linked list starting at pHead. This
  ** block sorts them by cost and then sets amatch_vtab.pRule to point to 
  ** point to the head of the sorted list.
  */
  if( rc==SQLITE_OK ){
    unsigned int i;
    amatch_rule *pX;
    amatch_rule *a[15];
    for(i=0; i<sizeof(a)/sizeof(a[0]); i++) a[i] = 0;
    while( (pX = pHead)!=0 ){
      pHead = pX->pNext;
      pX->pNext = 0;
      for(i=0; a[i] && i<sizeof(a)/sizeof(a[0])-1; i++){
        pX = amatchMergeRules(a[i], pX);
        a[i] = 0;
      }
      a[i] = amatchMergeRules(a[i], pX);
    }
    for(pX=a[0], i=1; i<sizeof(a)/sizeof(a[0]); i++){
      pX = amatchMergeRules(a[i], pX);
    }
    p->pRule = amatchMergeRules(p->pRule, pX);
  }else{
    /* An error has occurred. Setting p->pRule to point to the head of the
    ** allocated list ensures that the list will be cleaned up in this case.
    */
    assert( p->pRule==0 );
    p->pRule = pHead;
  }

  return rc;
}

/*
** This function converts an SQL quoted string into an unquoted string
** and returns a pointer to a buffer allocated using sqlite3_malloc() 
** containing the result. The caller should eventually free this buffer
** using sqlite3_free.
**
** Examples:
**
**     "abc"   becomes   abc
**     'xyz'   becomes   xyz
**     [pqr]   becomes   pqr
**     `mno`   becomes   mno
*/
static char *amatchDequote(const char *zIn){
  int nIn;                        /* Size of input string, in bytes */
  char *zOut;                     /* Output (dequoted) string */

  nIn = (int)strlen(zIn);
  zOut = sqlite3_malloc(nIn+1);
  if( zOut ){
    char q = zIn[0];              /* Quote character (if any ) */

    if( q!='[' && q!= '\'' && q!='"' && q!='`' ){
      memcpy(zOut, zIn, nIn+1);
    }else{
      int iOut = 0;               /* Index of next byte to write to output */
      int iIn;                    /* Index of next byte to read from input */

      if( q=='[' ) q = ']';
      for(iIn=1; iIn<nIn; iIn++){
        if( zIn[iIn]==q ) iIn++;
        zOut[iOut++] = zIn[iIn];
      }
    }
    assert( (int)strlen(zOut)<=nIn );
  }
  return zOut;
}

/*
** Deallocate the pVCheck prepared statement.
*/
static void amatchVCheckClear(amatch_vtab *p){
  if( p->pVCheck ){
    sqlite3_finalize(p->pVCheck);
    p->pVCheck = 0;
  }
}

/*
** Deallocate an amatch_vtab object
*/
static void amatchFree(amatch_vtab *p){
  if( p ){
    amatchFreeRules(p);
    amatchVCheckClear(p);
    sqlite3_free(p->zClassName);
    sqlite3_free(p->zDb);
    sqlite3_free(p->zCostTab);
    sqlite3_free(p->zVocabTab);
    sqlite3_free(p->zVocabWord);
    sqlite3_free(p->zVocabLang);
    memset(p, 0, sizeof(*p));
    sqlite3_free(p);
  }
}

/*
** xDisconnect/xDestroy method for the amatch module.
*/
static int amatchDisconnect(sqlite3_vtab *pVtab){
  amatch_vtab *p = (amatch_vtab*)pVtab;
  assert( p->nCursor==0 );
  amatchFree(p);
  return SQLITE_OK;
}

/*
** Check to see if the argument is of the form:
**
**       KEY = VALUE
**
** If it is, return a pointer to the first character of VALUE.
** If not, return NULL.  Spaces around the = are ignored.
*/
static const char *amatchValueOfKey(const char *zKey, const char *zStr){
  int nKey = (int)strlen(zKey);
  int nStr = (int)strlen(zStr);
  int i;
  if( nStr<nKey+1 ) return 0;
  if( memcmp(zStr, zKey, nKey)!=0 ) return 0;
  for(i=nKey; isspace(zStr[i]); i++){}
  if( zStr[i]!='=' ) return 0;
  i++;
  while( isspace(zStr[i]) ){ i++; }
  return zStr+i;
}

/*
** xConnect/xCreate method for the amatch module. Arguments are:
**
**   argv[0]    -> module name  ("approximate_match")
**   argv[1]    -> database name
**   argv[2]    -> table name
**   argv[3...] -> arguments
*/
static int amatchConnect(
  sqlite3 *db,
  void *pAux,
  int argc, const char *const*argv,
  sqlite3_vtab **ppVtab,
  char **pzErr
){
  int rc = SQLITE_OK;             /* Return code */
  amatch_vtab *pNew = 0;          /* New virtual table */
  const char *zModule = argv[0];
  const char *zDb = argv[1];
  const char *zVal;
  int i;

  (void)pAux;
  *ppVtab = 0;
  pNew = sqlite3_malloc( sizeof(*pNew) );
  if( pNew==0 ) return SQLITE_NOMEM;
  rc = SQLITE_NOMEM;
  memset(pNew, 0, sizeof(*pNew));
  pNew->db = db;
  pNew->zClassName = sqlite3_mprintf("%s", zModule);
  if( pNew->zClassName==0 ) goto amatchConnectError;
  pNew->zDb = sqlite3_mprintf("%s", zDb);
  if( pNew->zDb==0 ) goto amatchConnectError;
  pNew->zSelf = sqlite3_mprintf("%s", argv[2]);
  if( pNew->zSelf==0 ) goto amatchConnectError;
  for(i=3; i<argc; i++){
    zVal = amatchValueOfKey("vocabulary_table", argv[i]);
    if( zVal ){
      sqlite3_free(pNew->zVocabTab);
      pNew->zVocabTab = amatchDequote(zVal);
      if( pNew->zVocabTab==0 ) goto amatchConnectError;
      continue;
    }
    zVal = amatchValueOfKey("vocabulary_word", argv[i]);
    if( zVal ){
      sqlite3_free(pNew->zVocabWord);
      pNew->zVocabWord = amatchDequote(zVal);
      if( pNew->zVocabWord==0 ) goto amatchConnectError;
      continue;
    }
    zVal = amatchValueOfKey("vocabulary_language", argv[i]);
    if( zVal ){
      sqlite3_free(pNew->zVocabLang);
      pNew->zVocabLang = amatchDequote(zVal);
      if( pNew->zVocabLang==0 ) goto amatchConnectError;
      continue;
    }
    zVal = amatchValueOfKey("edit_distances", argv[i]);
    if( zVal ){
      sqlite3_free(pNew->zCostTab);
      pNew->zCostTab = amatchDequote(zVal);
      if( pNew->zCostTab==0 ) goto amatchConnectError;
      continue;
    }
    *pzErr = sqlite3_mprintf("unrecognized argument: [%s]\n", argv[i]);
    amatchFree(pNew);
    *ppVtab = 0;
    return SQLITE_ERROR;
  }
  rc = SQLITE_OK;
  if( pNew->zCostTab==0 ){
    *pzErr = sqlite3_mprintf("no edit_distances table specified");
    rc = SQLITE_ERROR;
  }else{
    rc = amatchLoadRules(db, pNew, pzErr);
  }
  if( rc==SQLITE_OK ){
    rc = sqlite3_declare_vtab(db,
           "CREATE TABLE x(word,distance,language,"
           "command HIDDEN,nword HIDDEN)"
         );
#define AMATCH_COL_WORD       0
#define AMATCH_COL_DISTANCE   1
#define AMATCH_COL_LANGUAGE   2
#define AMATCH_COL_COMMAND    3
#define AMATCH_COL_NWORD      4
  }
  if( rc!=SQLITE_OK ){
    amatchFree(pNew);
  }
  *ppVtab = &pNew->base;
  return rc;

amatchConnectError:
  amatchFree(pNew);
  return rc;
}

/*
** Open a new amatch cursor.
*/
static int amatchOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
  amatch_vtab *p = (amatch_vtab*)pVTab;
  amatch_cursor *pCur;
  pCur = sqlite3_malloc( sizeof(*pCur) );
  if( pCur==0 ) return SQLITE_NOMEM;
  memset(pCur, 0, sizeof(*pCur));
  pCur->pVtab = p;
  *ppCursor = &pCur->base;
  p->nCursor++;
  return SQLITE_OK;
}

/*
** Free up all the memory allocated by a cursor.  Set it rLimit to 0
** to indicate that it is at EOF.
*/
static void amatchClearCursor(amatch_cursor *pCur){
  amatch_word *pWord, *pNextWord;
  for(pWord=pCur->pAllWords; pWord; pWord=pNextWord){
    pNextWord = pWord->pNext;
    sqlite3_free(pWord);
  }
  pCur->pAllWords = 0;
  sqlite3_free(pCur->zInput);
  pCur->zInput = 0;
  pCur->pCost = 0;
  pCur->pWord = 0;
  pCur->pCurrent = 0;
  pCur->rLimit = 1000000;
  pCur->iLang = 0;
  pCur->nWord = 0;
}

/*
** Close a amatch cursor.
*/
static int amatchClose(sqlite3_vtab_cursor *cur){
  amatch_cursor *pCur = (amatch_cursor *)cur;
  amatchClearCursor(pCur);
  pCur->pVtab->nCursor--;
  sqlite3_free(pCur);
  return SQLITE_OK;
}

/*
** Render a 24-bit unsigned integer as a 4-byte base-64 number.
*/
static void amatchEncodeInt(int x, char *z){
  static const char a[] = 
    "0123456789"
    "ABCDEFGHIJ"
    "KLMNOPQRST"
    "UVWXYZ^abc"
    "defghijklm"
    "nopqrstuvw"
    "xyz~";
  z[0] = a[(x>>18)&0x3f];
  z[1] = a[(x>>12)&0x3f];
  z[2] = a[(x>>6)&0x3f];
  z[3] = a[x&0x3f];
}

/*
** Write the zCost[] field for a amatch_word object
*/
static void amatchWriteCost(amatch_word *pWord){
  amatchEncodeInt(pWord->rCost, pWord->zCost);
  amatchEncodeInt(pWord->iSeq, pWord->zCost+4);
  pWord->zCost[8] = 0;
}

/*
** Add a new amatch_word object to the queue.
**
** If a prior amatch_word object with the same zWord, and nMatch
** already exists, update its rCost (if the new rCost is less) but
** otherwise leave it unchanged.  Do not add a duplicate.
**
** Do nothing if the cost exceeds threshold.
*/
static void amatchAddWord(
  amatch_cursor *pCur,
  amatch_cost rCost,
  int nMatch,
  const char *zWordBase,
  const char *zWordTail
){
  amatch_word *pWord;
  amatch_avl *pNode;
  amatch_avl *pOther;
  int nBase, nTail;
  char zBuf[4];
  
  if( rCost>pCur->rLimit ){
    return;
  }
  nBase = (int)strlen(zWordBase);
  nTail = (int)strlen(zWordTail);
  if( nBase+nTail+3>pCur->nBuf ){
    pCur->nBuf = nBase+nTail+100;
    pCur->zBuf = sqlite3_realloc(pCur->zBuf, pCur->nBuf);
    if( pCur->zBuf==0 ){
      pCur->nBuf = 0;
      return;
    }
  }
  amatchEncodeInt(nMatch, zBuf);
  memcpy(pCur->zBuf, zBuf+2, 2);
  memcpy(pCur->zBuf+2, zWordBase, nBase);
  memcpy(pCur->zBuf+2+nBase, zWordTail, nTail+1);
  pNode = amatchAvlSearch(pCur->pWord, pCur->zBuf);
  if( pNode ){
    pWord = pNode->pWord;
    if( pWord->rCost>rCost ){
#ifdef AMATCH_TRACE_1
      printf("UPDATE [%s][%.*s^%s] %d (\"%s\" \"%s\")\n",
             pWord->zWord+2, pWord->nMatch, pCur->zInput, pCur->zInput,
             pWord->rCost, pWord->zWord, pWord->zCost);
#endif
      amatchAvlRemove(&pCur->pCost, &pWord->sCost);
      pWord->rCost = rCost;
      amatchWriteCost(pWord);
#ifdef AMATCH_TRACE_1
      printf("  ---> %d (\"%s\" \"%s\")\n",
             pWord->rCost, pWord->zWord, pWord->zCost);
#endif
      pOther = amatchAvlInsert(&pCur->pCost, &pWord->sCost);
      assert( pOther==0 ); (void)pOther;
    }
    return;
  }
  pWord = sqlite3_malloc( sizeof(*pWord) + nBase + nTail - 1 );
  if( pWord==0 ) return;
  memset(pWord, 0, sizeof(*pWord));
  pWord->rCost = rCost;
  pWord->iSeq = pCur->nWord++;
  amatchWriteCost(pWord);
  pWord->nMatch = nMatch;
  pWord->pNext = pCur->pAllWords;
  pCur->pAllWords = pWord;
  pWord->sCost.zKey = pWord->zCost;
  pWord->sCost.pWord = pWord;
  pOther = amatchAvlInsert(&pCur->pCost, &pWord->sCost);
  assert( pOther==0 ); (void)pOther;
  pWord->sWord.zKey = pWord->zWord;
  pWord->sWord.pWord = pWord;
  strcpy(pWord->zWord, pCur->zBuf);
  pOther = amatchAvlInsert(&pCur->pWord, &pWord->sWord);
  assert( pOther==0 ); (void)pOther;
#ifdef AMATCH_TRACE_1
  printf("INSERT [%s][%.*s^%s] %d (\"%s\" \"%s\")\n", pWord->zWord+2,
       pWord->nMatch, pCur->zInput, pCur->zInput+pWord->nMatch, rCost,
       pWord->zWord, pWord->zCost);
#endif
}

/*
** Advance a cursor to its next row of output
*/
static int amatchNext(sqlite3_vtab_cursor *cur){
  amatch_cursor *pCur = (amatch_cursor*)cur;
  amatch_word *pWord = 0;
  amatch_avl *pNode;
  int isMatch = 0;
  amatch_vtab *p = pCur->pVtab;
  int nWord;
  int rc;
  int i;
  const char *zW;
  amatch_rule *pRule;
  char *zBuf = 0;
  char nBuf = 0;
  char zNext[8];
  char zNextIn[8];
  int nNextIn;

  if( p->pVCheck==0 ){
    char *zSql;
    if( p->zVocabLang && p->zVocabLang[0] ){
      zSql = sqlite3_mprintf(
          "SELECT \"%s\" FROM \"%s\"",
          " WHERE \"%w\">=?1 AND \"%w\"=?2"
          " ORDER BY 1",
          p->zVocabWord, p->zVocabTab,
          p->zVocabWord, p->zVocabLang
      );
    }else{
      zSql = sqlite3_mprintf(
          "SELECT \"%s\" FROM \"%s\""
          " WHERE \"%w\">=?1"
          " ORDER BY 1",
          p->zVocabWord, p->zVocabTab,
          p->zVocabWord
      );
    }
    rc = sqlite3_prepare_v2(p->db, zSql, -1, &p->pVCheck, 0);
    sqlite3_free(zSql);
    if( rc ) return rc;
  }
  sqlite3_bind_int(p->pVCheck, 2, pCur->iLang);

  do{
    pNode = amatchAvlFirst(pCur->pCost);
    if( pNode==0 ){
      pWord = 0;
      break;
    }
    pWord = pNode->pWord;
    amatchAvlRemove(&pCur->pCost, &pWord->sCost);

#ifdef AMATCH_TRACE_1
    printf("PROCESS [%s][%.*s^%s] %d (\"%s\" \"%s\")\n",
       pWord->zWord+2, pWord->nMatch, pCur->zInput, pCur->zInput+pWord->nMatch,
       pWord->rCost, pWord->zWord, pWord->zCost);
#endif
    nWord = (int)strlen(pWord->zWord+2);
    if( nWord+20>nBuf ){
      nBuf = nWord+100;
      zBuf = sqlite3_realloc(zBuf, nBuf);
      if( zBuf==0 ) return SQLITE_NOMEM;
    }
    strcpy(zBuf, pWord->zWord+2);
    zNext[0] = 0;
    zNextIn[0] = pCur->zInput[pWord->nMatch];
    if( zNextIn[0] ){
      for(i=1; i<=4 && (pCur->zInput[pWord->nMatch+i]&0xc0)==0x80; i++){
        zNextIn[i] = pCur->zInput[pWord->nMatch+i];
      }
      zNextIn[i] = 0;
      nNextIn = i;
    }else{
      nNextIn = 0;
    }

    if( zNextIn[0] && zNextIn[0]!='*' ){
      sqlite3_reset(p->pVCheck);
      strcat(zBuf, zNextIn);
      sqlite3_bind_text(p->pVCheck, 1, zBuf, nWord+nNextIn, SQLITE_STATIC);
      rc = sqlite3_step(p->pVCheck);
      if( rc==SQLITE_ROW ){
        zW = (const char*)sqlite3_column_text(p->pVCheck, 0);
        if( strncmp(zBuf, zW, nWord+nNextIn)==0 ){
          amatchAddWord(pCur, pWord->rCost, pWord->nMatch+nNextIn, zBuf, "");
        }
      }
      zBuf[nWord] = 0;
    }

    while( 1 ){
      strcpy(zBuf+nWord, zNext);
      sqlite3_reset(p->pVCheck);
      sqlite3_bind_text(p->pVCheck, 1, zBuf, -1, SQLITE_TRANSIENT);
      rc = sqlite3_step(p->pVCheck);
      if( rc!=SQLITE_ROW ) break;
      zW = (const char*)sqlite3_column_text(p->pVCheck, 0);
      strcpy(zBuf+nWord, zNext);
      if( strncmp(zW, zBuf, nWord)!=0 ) break;
      if( (zNextIn[0]=='*' && zNextIn[1]==0)
       || (zNextIn[0]==0 && zW[nWord]==0)
      ){
        isMatch = 1;
        zNextIn[0] = 0;
        nNextIn = 0;
        break;
      }
      zNext[0] = zW[nWord];
      for(i=1; i<=4 && (zW[nWord+i]&0xc0)==0x80; i++){
        zNext[i] = zW[nWord+i];
      }
      zNext[i] = 0;
      zBuf[nWord] = 0;
      if( p->rIns>0 ){
        amatchAddWord(pCur, pWord->rCost+p->rIns, pWord->nMatch, 
                      zBuf, zNext);
      }
      if( p->rSub>0 ){
        amatchAddWord(pCur, pWord->rCost+p->rSub, pWord->nMatch+nNextIn, 
                      zBuf, zNext);
      }
      if( p->rIns<0 && p->rSub<0 ) break;
      zNext[i-1]++;  /* FIX ME */
    }
    sqlite3_reset(p->pVCheck);

    if( p->rDel>0 ){
      zBuf[nWord] = 0;
      amatchAddWord(pCur, pWord->rCost+p->rDel, pWord->nMatch+nNextIn,
                    zBuf, "");
    }

    for(pRule=p->pRule; pRule; pRule=pRule->pNext){
      if( pRule->iLang!=pCur->iLang ) continue;
      if( strncmp(pRule->zFrom, pCur->zInput+pWord->nMatch, pRule->nFrom)==0 ){
        amatchAddWord(pCur, pWord->rCost+pRule->rCost,
                      pWord->nMatch+pRule->nFrom, pWord->zWord+2, pRule->zTo);
      }
    }
  }while( !isMatch );
  pCur->pCurrent = pWord;
  sqlite3_free(zBuf);
  return SQLITE_OK;
}

/*
** Called to "rewind" a cursor back to the beginning so that
** it starts its output over again.  Always called at least once
** prior to any amatchColumn, amatchRowid, or amatchEof call.
*/
static int amatchFilter(
  sqlite3_vtab_cursor *pVtabCursor, 
  int idxNum, const char *idxStr,
  int argc, sqlite3_value **argv
){
  amatch_cursor *pCur = (amatch_cursor *)pVtabCursor;
  const char *zWord = "*";
  int idx;

  amatchClearCursor(pCur);
  idx = 0;
  if( idxNum & 1 ){
    zWord = (const char*)sqlite3_value_text(argv[0]);
    idx++;
  }
  if( idxNum & 2 ){
    pCur->rLimit = (amatch_cost)sqlite3_value_int(argv[idx]);
    idx++;
  }
  if( idxNum & 4 ){
    pCur->iLang = (amatch_cost)sqlite3_value_int(argv[idx]);
    idx++;
  }
  pCur->zInput = sqlite3_mprintf("%s", zWord);
  if( pCur->zInput==0 ) return SQLITE_NOMEM;
  amatchAddWord(pCur, 0, 0, "", "");
  amatchNext(pVtabCursor);

  return SQLITE_OK;
}

/*
** Only the word and distance columns have values.  All other columns
** return NULL
*/
static int amatchColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
  amatch_cursor *pCur = (amatch_cursor*)cur;
  switch( i ){
    case AMATCH_COL_WORD: {
      sqlite3_result_text(ctx, pCur->pCurrent->zWord+2, -1, SQLITE_STATIC);
      break;
    }
    case AMATCH_COL_DISTANCE: {
      sqlite3_result_int(ctx, pCur->pCurrent->rCost);
      break;
    }
    case AMATCH_COL_LANGUAGE: {
      sqlite3_result_int(ctx, pCur->iLang);
      break;
    }
    case AMATCH_COL_NWORD: {
      sqlite3_result_int(ctx, pCur->nWord);
      break;
    }
    default: {
      sqlite3_result_null(ctx);
      break;
    }
  }
  return SQLITE_OK;
}

/*
** The rowid.
*/
static int amatchRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
  amatch_cursor *pCur = (amatch_cursor*)cur;
  *pRowid = pCur->iRowid;
  return SQLITE_OK;
}

/*
** EOF indicator
*/
static int amatchEof(sqlite3_vtab_cursor *cur){
  amatch_cursor *pCur = (amatch_cursor*)cur;
  return pCur->pCurrent==0;
}

/*
** Search for terms of these forms:
**
**   (A)    word MATCH $str
**   (B1)   distance < $value
**   (B2)   distance <= $value
**   (C)    language == $language
**
** The distance< and distance<= are both treated as distance<=.
** The query plan number is a bit vector:
**
**   bit 1:   Term of the form (A) found
**   bit 2:   Term like (B1) or (B2) found
**   bit 3:   Term like (C) found
**
** If bit-1 is set, $str is always in filter.argv[0].  If bit-2 is set
** then $value is in filter.argv[0] if bit-1 is clear and is in 
** filter.argv[1] if bit-1 is set.  If bit-3 is set, then $ruleid is
** in filter.argv[0] if bit-1 and bit-2 are both zero, is in
** filter.argv[1] if exactly one of bit-1 and bit-2 are set, and is in
** filter.argv[2] if both bit-1 and bit-2 are set.
*/
static int amatchBestIndex(
  sqlite3_vtab *tab,
  sqlite3_index_info *pIdxInfo
){
  int iPlan = 0;
  int iDistTerm = -1;
  int iLangTerm = -1;
  int i;
  const struct sqlite3_index_constraint *pConstraint;

  (void)tab;
  pConstraint = pIdxInfo->aConstraint;
  for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
    if( pConstraint->usable==0 ) continue;
    if( (iPlan & 1)==0 
     && pConstraint->iColumn==0
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH
    ){
      iPlan |= 1;
      pIdxInfo->aConstraintUsage[i].argvIndex = 1;
      pIdxInfo->aConstraintUsage[i].omit = 1;
    }
    if( (iPlan & 2)==0
     && pConstraint->iColumn==1
     && (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT
           || pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE)
    ){
      iPlan |= 2;
      iDistTerm = i;
    }
    if( (iPlan & 4)==0
     && pConstraint->iColumn==2
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
    ){
      iPlan |= 4;
      pIdxInfo->aConstraintUsage[i].omit = 1;
      iLangTerm = i;
    }
  }
  if( iPlan & 2 ){
    pIdxInfo->aConstraintUsage[iDistTerm].argvIndex = 1+((iPlan&1)!=0);
  }
  if( iPlan & 4 ){
    int idx = 1;
    if( iPlan & 1 ) idx++;
    if( iPlan & 2 ) idx++;
    pIdxInfo->aConstraintUsage[iLangTerm].argvIndex = idx;
  }
  pIdxInfo->idxNum = iPlan;
  if( pIdxInfo->nOrderBy==1
   && pIdxInfo->aOrderBy[0].iColumn==1
   && pIdxInfo->aOrderBy[0].desc==0
  ){
    pIdxInfo->orderByConsumed = 1;
  }
  pIdxInfo->estimatedCost = (double)10000;
   
  return SQLITE_OK;
}

/*
** The xUpdate() method.  
**
** This implementation disallows DELETE and UPDATE.  The only thing
** allowed is INSERT into the "command" column.
*/
static int amatchUpdate(
  sqlite3_vtab *pVTab,
  int argc,
  sqlite3_value **argv,
  sqlite_int64 *pRowid
){
  amatch_vtab *p = (amatch_vtab*)pVTab;
  const unsigned char *zCmd;
  (void)pRowid;
  if( argc==1 ){
    pVTab->zErrMsg = sqlite3_mprintf("DELETE from %s is not allowed", 
                                      p->zSelf);
    return SQLITE_ERROR;
  }
  if( sqlite3_value_type(argv[0])!=SQLITE_NULL ){
    pVTab->zErrMsg = sqlite3_mprintf("UPDATE of %s is not allowed", 
                                      p->zSelf);
    return SQLITE_ERROR;
  }
  if( sqlite3_value_type(argv[2+AMATCH_COL_WORD])!=SQLITE_NULL
   || sqlite3_value_type(argv[2+AMATCH_COL_DISTANCE])!=SQLITE_NULL
   || sqlite3_value_type(argv[2+AMATCH_COL_LANGUAGE])!=SQLITE_NULL
  ){
    pVTab->zErrMsg = sqlite3_mprintf(
            "INSERT INTO %s allowed for column [command] only", p->zSelf);
    return SQLITE_ERROR;
  }
  zCmd = sqlite3_value_text(argv[2+AMATCH_COL_COMMAND]);
  if( zCmd==0 ) return SQLITE_OK;
  
  return SQLITE_OK;
}

/*
** A virtual table module that implements the "approximate_match".
*/
static sqlite3_module amatchModule = {
  0,                      /* iVersion */
  amatchConnect,          /* xCreate */
  amatchConnect,          /* xConnect */
  amatchBestIndex,        /* xBestIndex */
  amatchDisconnect,       /* xDisconnect */
  amatchDisconnect,       /* xDestroy */
  amatchOpen,             /* xOpen - open a cursor */
  amatchClose,            /* xClose - close a cursor */
  amatchFilter,           /* xFilter - configure scan constraints */
  amatchNext,             /* xNext - advance a cursor */
  amatchEof,              /* xEof - check for end of scan */
  amatchColumn,           /* xColumn - read data */
  amatchRowid,            /* xRowid - read data */
  amatchUpdate,           /* xUpdate */
  0,                      /* xBegin */
  0,                      /* xSync */
  0,                      /* xCommit */
  0,                      /* xRollback */
  0,                      /* xFindMethod */
  0,                      /* xRename */
  0,                      /* xSavepoint */
  0,                      /* xRelease */
  0                       /* xRollbackTo */
};

/*
** Register the amatch virtual table
*/
#ifdef _WIN32
__declspec(dllexport)
#endif
int sqlite3_amatch_init(
  sqlite3 *db, 
  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  int rc = SQLITE_OK;
  SQLITE_EXTENSION_INIT2(pApi);
  (void)pzErrMsg;  /* Not used */
  rc = sqlite3_create_module(db, "approximate_match", &amatchModule, 0);
  return rc;
}

/*
** 2013-04-16
**
** 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.
**
*************************************************************************
**
** This file contains code for a virtual table that finds the transitive
** closure of a parent/child relationship in a real table.  The virtual 
** table is called "transitive_closure".
**
** A transitive_closure virtual table is created like this:
**
**     CREATE VIRTUAL TABLE x USING transitive_closure(
**        tablename=<tablename>,      -- T
**        idcolumn=<columnname>,      -- X
**        parentcolumn=<columnname>   -- P
**     );
**
** When it is created, the new transitive_closure table may be supplied 
** with default values for the name of a table T and columns T.X and T.P.
** The T.X and T.P columns must contain integers.  The ideal case is for 
** T.X to be the INTEGER PRIMARY KEY.  The T.P column should reference
** the T.X column. The row referenced by T.P is the parent of the current row.
**
** The tablename, idcolumn, and parentcolumn supplied by the CREATE VIRTUAL
** TABLE statement may be overridden in individual queries by including
** terms like tablename='newtable', idcolumn='id2', or 
** parentcolumn='parent3' in the WHERE clause of the query.
**
** For efficiency, it is essential that there be an index on the P column:
**
**    CREATE Tidx1 ON T(P)
**
** Suppose a specific instance of the closure table is as follows:
**
**    CREATE VIRTUAL TABLE ct1 USING transitive_closure(
**       tablename='group',
**       idcolumn='groupId',
**       parentcolumn='parentId'
**    );
**
** Such an instance of the transitive_closure virtual table would be
** appropriate for walking a tree defined using a table like this, for example:
**
**    CREATE TABLE group(
**      groupId INTEGER PRIMARY KEY,
**      parentId INTEGER REFERENCES group
**    );
**    CREATE INDEX group_idx1 ON group(parentId);
**
** The group table above would presumably have other application-specific
** fields.  The key point here is that rows of the group table form a
** tree.  The purpose of the ct1 virtual table is to easily extract
** branches of that tree.
**
** Once it has been created, the ct1 virtual table can be queried
** as follows:
**
**    SELECT * FROM element
**     WHERE element.groupId IN (SELECT id FROM ct1 WHERE root=?1);
**
** The above query will return all elements that are part of group ?1
** or children of group ?1 or grand-children of ?1 and so forth for all
** descendents of group ?1.  The same query can be formulated as a join:
**
**    SELECT element.* FROM element, ct1
**     WHERE element.groupid=ct1.id
**       AND ct1.root=?1;
**
** The depth of the transitive_closure (the number of generations of
** parent/child relations to follow) can be limited by setting "depth"
** column in the WHERE clause.  So, for example, the following query
** finds only children and grandchildren but no further descendents:
**
**    SELECT element.* FROM element, ct1
**     WHERE element.groupid=ct1.id
**       AND ct1.root=?1
**       AND ct1.depth<=2;
**
** The "ct1.depth<=2" term could be a strict equality "ct1.depth=2" in
** order to find only the grandchildren of ?1, not ?1 itself or the
** children of ?1.
** 
** The root=?1 term must be supplied in WHERE clause or else the query
** of the ct1 virtual table will return an empty set.  The tablename,
** idcolumn, and parentcolumn attributes can be overridden in the WHERE
** clause if desired.  So, for example, the ct1 table could be repurposed
** to find ancestors rather than descendents by inverting the roles of
** the idcolumn and parentcolumn:
**
**    SELECT element.* FROM element, ct1
**     WHERE element.groupid=ct1.id
**       AND ct1.root=?1
**       AND ct1.idcolumn='parentId'
**       AND ct1.parentcolumn='groupId';
**
** Multiple calls to ct1 could be combined.  For example, the following
** query finds all elements that "cousins" of groupId ?1.  That is to say
** elements where the groupId is a grandchild of the grandparent of ?1.
** (This definition of "cousins" also includes siblings and self.)
**
**    SELECT element.* FROM element, ct1
**     WHERE element.groupId=ct1.id
**       AND ct1.depth=2
**       AND ct1.root IN (SELECT id FROM ct1
**                         WHERE root=?1
**                           AND depth=2
**                           AND idcolumn='parentId'
**                           AND parentcolumn='groupId');
**
** In our example, the group.groupId column is unique and thus the
** subquery will return exactly one row.  For that reason, the IN
** operator could be replaced by "=" to get the same result.  But
** in the general case where the idcolumn is not unique, an IN operator
** would be required for this kind of query.
**
** Note that because the tablename, idcolumn, and parentcolumn can
** all be specified in the query, it is possible for an application
** to define a single transitive_closure virtual table for use on lots
** of different hierarchy tables.  One might say:
**
**     CREATE VIRTUAL TABLE temp.closure USING transitive_closure;
**
** As each database connection is being opened.  Then the application
** would always have a "closure" virtual table handy to use for querying.
**
**    SELECT element.* FROM element, closure
**     WHERE element.groupid=ct1.id
**       AND closure.root=?1
**       AND closure.tablename='group'
**       AND closure.idname='groupId'
**       AND closure.parentname='parentId';
**
** See the documentation at http://www.sqlite.org/loadext.html for information
** on how to compile and use loadable extensions such as this one.
*/
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <ctype.h>

/*
** Forward declaration of objects used by this implementation
*/
typedef struct closure_vtab closure_vtab;
typedef struct closure_cursor closure_cursor;
typedef struct closure_queue closure_queue;
typedef struct closure_avl closure_avl;

/*****************************************************************************
** AVL Tree implementation
*/
/*
** Objects that want to be members of the AVL tree should embedded an
** instance of this structure.
*/
struct closure_avl {
  sqlite3_int64 id;     /* Id of this entry in the table */
  int iGeneration;      /* Which generation is this entry part of */
  closure_avl *pList;   /* A linked list of nodes */
  closure_avl *pBefore; /* Other elements less than id */
  closure_avl *pAfter;  /* Other elements greater than id */
  closure_avl *pUp;     /* Parent element */
  short int height;     /* Height of this node.  Leaf==1 */
  short int imbalance;  /* Height difference between pBefore and pAfter */
};

/* Recompute the closure_avl.height and closure_avl.imbalance fields for p.
** Assume that the children of p have correct heights.
*/
static void closureAvlRecomputeHeight(closure_avl *p){
  short int hBefore = p->pBefore ? p->pBefore->height : 0;
  short int hAfter = p->pAfter ? p->pAfter->height : 0;
  p->imbalance = hBefore - hAfter;  /* -: pAfter higher.  +: pBefore higher */
  p->height = (hBefore>hAfter ? hBefore : hAfter)+1;
}

/*
**     P                B
**    / \              / \
**   B   Z    ==>     X   P
**  / \                  / \
** X   Y                Y   Z
**
*/
static closure_avl *closureAvlRotateBefore(closure_avl *pP){
  closure_avl *pB = pP->pBefore;
  closure_avl *pY = pB->pAfter;
  pB->pUp = pP->pUp;
  pB->pAfter = pP;
  pP->pUp = pB;
  pP->pBefore = pY;
  if( pY ) pY->pUp = pP;
  closureAvlRecomputeHeight(pP);
  closureAvlRecomputeHeight(pB);
  return pB;
}

/*
**     P                A
**    / \              / \
**   X   A    ==>     P   Z
**      / \          / \
**     Y   Z        X   Y
**
*/
static closure_avl *closureAvlRotateAfter(closure_avl *pP){
  closure_avl *pA = pP->pAfter;
  closure_avl *pY = pA->pBefore;
  pA->pUp = pP->pUp;
  pA->pBefore = pP;
  pP->pUp = pA;
  pP->pAfter = pY;
  if( pY ) pY->pUp = pP;
  closureAvlRecomputeHeight(pP);
  closureAvlRecomputeHeight(pA);
  return pA;
}

/*
** Return a pointer to the pBefore or pAfter pointer in the parent
** of p that points to p.  Or if p is the root node, return pp.
*/
static closure_avl **closureAvlFromPtr(closure_avl *p, closure_avl **pp){
  closure_avl *pUp = p->pUp;
  if( pUp==0 ) return pp;
  if( pUp->pAfter==p ) return &pUp->pAfter;
  return &pUp->pBefore;
}

/*
** Rebalance all nodes starting with p and working up to the root.
** Return the new root.
*/
static closure_avl *closureAvlBalance(closure_avl *p){
  closure_avl *pTop = p;
  closure_avl **pp;
  while( p ){
    closureAvlRecomputeHeight(p);
    if( p->imbalance>=2 ){
      closure_avl *pB = p->pBefore;
      if( pB->imbalance<0 ) p->pBefore = closureAvlRotateAfter(pB);
      pp = closureAvlFromPtr(p,&p);
      p = *pp = closureAvlRotateBefore(p);
    }else if( p->imbalance<=(-2) ){
      closure_avl *pA = p->pAfter;
      if( pA->imbalance>0 ) p->pAfter = closureAvlRotateBefore(pA);
      pp = closureAvlFromPtr(p,&p);
      p = *pp = closureAvlRotateAfter(p);
    }
    pTop = p;
    p = p->pUp;
  }
  return pTop;
}

/* Search the tree rooted at p for an entry with id.  Return a pointer
** to the entry or return NULL.
*/
static closure_avl *closureAvlSearch(closure_avl *p, sqlite3_int64 id){
  while( p && id!=p->id ){
    p = (id<p->id) ? p->pBefore : p->pAfter;
  }
  return p;
}

/* Find the first node (the one with the smallest key).
*/
static closure_avl *closureAvlFirst(closure_avl *p){
  if( p ) while( p->pBefore ) p = p->pBefore;
  return p;
}

/* Return the node with the next larger key after p.
*/
closure_avl *closureAvlNext(closure_avl *p){
  closure_avl *pPrev = 0;
  while( p && p->pAfter==pPrev ){
    pPrev = p;
    p = p->pUp;
  }
  if( p && pPrev==0 ){
    p = closureAvlFirst(p->pAfter);
  }
  return p;
}
	
/* Insert a new node pNew.  Return NULL on success.  If the key is not
** unique, then do not perform the insert but instead leave pNew unchanged
** and return a pointer to an existing node with the same key.
*/
static closure_avl *closureAvlInsert(
  closure_avl **ppHead,  /* Head of the tree */
  closure_avl *pNew      /* New node to be inserted */
){
  closure_avl *p = *ppHead;
  if( p==0 ){
    p = pNew;
    pNew->pUp = 0;
  }else{
    while( p ){
      if( pNew->id<p->id ){
        if( p->pBefore ){
          p = p->pBefore;
        }else{
          p->pBefore = pNew;
          pNew->pUp = p;
          break;
        }
      }else if( pNew->id>p->id ){
        if( p->pAfter ){
          p = p->pAfter;
        }else{
          p->pAfter = pNew;
          pNew->pUp = p;
          break;
        }
      }else{
        return p;
      }
    }
  }
  pNew->pBefore = 0;
  pNew->pAfter = 0;
  pNew->height = 1;
  pNew->imbalance = 0;
  *ppHead = closureAvlBalance(p);
  return 0;
}

/* Walk the tree can call xDestroy on each node
*/
static void closureAvlDestroy(closure_avl *p, void (*xDestroy)(closure_avl*)){
  if( p ){
    closureAvlDestroy(p->pBefore, xDestroy);
    closureAvlDestroy(p->pAfter, xDestroy);
    xDestroy(p);
  }
}
/*
** End of the AVL Tree implementation
******************************************************************************/

/* 
** A closure virtual-table object 
*/
struct closure_vtab {
  sqlite3_vtab base;         /* Base class - must be first */
  char *zDb;                 /* Name of database.  (ex: "main") */
  char *zSelf;               /* Name of this virtual table */
  char *zTableName;          /* Name of table holding parent/child relation */
  char *zIdColumn;           /* Name of ID column of zTableName */
  char *zParentColumn;       /* Name of PARENT column in zTableName */
  sqlite3 *db;               /* The database connection */
  int nCursor;               /* Number of pending cursors */
};

/* A closure cursor object */
struct closure_cursor {
  sqlite3_vtab_cursor base;  /* Base class - must be first */
  closure_vtab *pVtab;       /* The virtual table this cursor belongs to */
  char *zTableName;          /* Name of table holding parent/child relation */
  char *zIdColumn;           /* Name of ID column of zTableName */
  char *zParentColumn;       /* Name of PARENT column in zTableName */
  closure_avl *pCurrent;     /* Current element of output */
  closure_avl *pClosure;     /* The complete closure tree */
};

/* A queue of AVL nodes */
struct closure_queue {
  closure_avl *pFirst;       /* Oldest node on the queue */
  closure_avl *pLast;        /* Youngest node on the queue */
};

/*
** Add a node to the end of the queue
*/
static void queuePush(closure_queue *pQueue, closure_avl *pNode){
  pNode->pList = 0;
  if( pQueue->pLast ){
    pQueue->pLast->pList = pNode;
  }else{
    pQueue->pFirst = pNode;
  }
  pQueue->pLast = pNode;
}

/*
** Extract the oldest element (the front element) from the queue.
*/
static closure_avl *queuePull(closure_queue *pQueue){
  closure_avl *p = pQueue->pFirst;
  if( p ){
    pQueue->pFirst = p->pList;
    if( pQueue->pFirst==0 ) pQueue->pLast = 0;
  }
  return p;
}

/*
** This function converts an SQL quoted string into an unquoted string
** and returns a pointer to a buffer allocated using sqlite3_malloc() 
** containing the result. The caller should eventually free this buffer
** using sqlite3_free.
**
** Examples:
**
**     "abc"   becomes   abc
**     'xyz'   becomes   xyz
**     [pqr]   becomes   pqr
**     `mno`   becomes   mno
*/
static char *closureDequote(const char *zIn){
  int nIn;                        /* Size of input string, in bytes */
  char *zOut;                     /* Output (dequoted) string */

  nIn = (int)strlen(zIn);
  zOut = sqlite3_malloc(nIn+1);
  if( zOut ){
    char q = zIn[0];              /* Quote character (if any ) */

    if( q!='[' && q!= '\'' && q!='"' && q!='`' ){
      memcpy(zOut, zIn, nIn+1);
    }else{
      int iOut = 0;               /* Index of next byte to write to output */
      int iIn;                    /* Index of next byte to read from input */

      if( q=='[' ) q = ']';
      for(iIn=1; iIn<nIn; iIn++){
        if( zIn[iIn]==q ) iIn++;
        zOut[iOut++] = zIn[iIn];
      }
    }
    assert( (int)strlen(zOut)<=nIn );
  }
  return zOut;
}

/*
** Deallocate an closure_vtab object
*/
static void closureFree(closure_vtab *p){
  if( p ){
    sqlite3_free(p->zDb);
    sqlite3_free(p->zSelf);
    sqlite3_free(p->zTableName);
    sqlite3_free(p->zIdColumn);
    sqlite3_free(p->zParentColumn);
    memset(p, 0, sizeof(*p));
    sqlite3_free(p);
  }
}

/*
** xDisconnect/xDestroy method for the closure module.
*/
static int closureDisconnect(sqlite3_vtab *pVtab){
  closure_vtab *p = (closure_vtab*)pVtab;
  assert( p->nCursor==0 );
  closureFree(p);
  return SQLITE_OK;
}

/*
** Check to see if the argument is of the form:
**
**       KEY = VALUE
**
** If it is, return a pointer to the first character of VALUE.
** If not, return NULL.  Spaces around the = are ignored.
*/
static const char *closureValueOfKey(const char *zKey, const char *zStr){
  int nKey = (int)strlen(zKey);
  int nStr = (int)strlen(zStr);
  int i;
  if( nStr<nKey+1 ) return 0;
  if( memcmp(zStr, zKey, nKey)!=0 ) return 0;
  for(i=nKey; isspace(zStr[i]); i++){}
  if( zStr[i]!='=' ) return 0;
  i++;
  while( isspace(zStr[i]) ){ i++; }
  return zStr+i;
}

/*
** xConnect/xCreate method for the closure module. Arguments are:
**
**   argv[0]    -> module name  ("approximate_match")
**   argv[1]    -> database name
**   argv[2]    -> table name
**   argv[3...] -> arguments
*/
static int closureConnect(
  sqlite3 *db,
  void *pAux,
  int argc, const char *const*argv,
  sqlite3_vtab **ppVtab,
  char **pzErr
){
  int rc = SQLITE_OK;              /* Return code */
  closure_vtab *pNew = 0;          /* New virtual table */
  const char *zDb = argv[1];
  const char *zVal;
  int i;

  (void)pAux;
  *ppVtab = 0;
  pNew = sqlite3_malloc( sizeof(*pNew) );
  if( pNew==0 ) return SQLITE_NOMEM;
  rc = SQLITE_NOMEM;
  memset(pNew, 0, sizeof(*pNew));
  pNew->db = db;
  pNew->zDb = sqlite3_mprintf("%s", zDb);
  if( pNew->zDb==0 ) goto closureConnectError;
  pNew->zSelf = sqlite3_mprintf("%s", argv[2]);
  if( pNew->zSelf==0 ) goto closureConnectError;
  for(i=3; i<argc; i++){
    zVal = closureValueOfKey("tablename", argv[i]);
    if( zVal ){
      sqlite3_free(pNew->zTableName);
      pNew->zTableName = closureDequote(zVal);
      if( pNew->zTableName==0 ) goto closureConnectError;
      continue;
    }
    zVal = closureValueOfKey("idcolumn", argv[i]);
    if( zVal ){
      sqlite3_free(pNew->zIdColumn);
      pNew->zIdColumn = closureDequote(zVal);
      if( pNew->zIdColumn==0 ) goto closureConnectError;
      continue;
    }
    zVal = closureValueOfKey("parentcolumn", argv[i]);
    if( zVal ){
      sqlite3_free(pNew->zParentColumn);
      pNew->zParentColumn = closureDequote(zVal);
      if( pNew->zParentColumn==0 ) goto closureConnectError;
      continue;
    }
    *pzErr = sqlite3_mprintf("unrecognized argument: [%s]\n", argv[i]);
    closureFree(pNew);
    *ppVtab = 0;
    return SQLITE_ERROR;
  }
  rc = sqlite3_declare_vtab(db,
         "CREATE TABLE x(id,depth,root HIDDEN,tablename HIDDEN,"
                        "idcolumn HIDDEN,parentcolumn HIDDEN)"
       );
#define CLOSURE_COL_ID              0
#define CLOSURE_COL_DEPTH           1
#define CLOSURE_COL_ROOT            2
#define CLOSURE_COL_TABLENAME       3
#define CLOSURE_COL_IDCOLUMN        4
#define CLOSURE_COL_PARENTCOLUMN    5
  if( rc!=SQLITE_OK ){
    closureFree(pNew);
  }
  *ppVtab = &pNew->base;
  return rc;

closureConnectError:
  closureFree(pNew);
  return rc;
}

/*
** Open a new closure cursor.
*/
static int closureOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
  closure_vtab *p = (closure_vtab*)pVTab;
  closure_cursor *pCur;
  pCur = sqlite3_malloc( sizeof(*pCur) );
  if( pCur==0 ) return SQLITE_NOMEM;
  memset(pCur, 0, sizeof(*pCur));
  pCur->pVtab = p;
  *ppCursor = &pCur->base;
  p->nCursor++;
  return SQLITE_OK;
}

/*
** Free up all the memory allocated by a cursor.  Set it rLimit to 0
** to indicate that it is at EOF.
*/
static void closureClearCursor(closure_cursor *pCur){
  closureAvlDestroy(pCur->pClosure, (void(*)(closure_avl*))sqlite3_free);
  sqlite3_free(pCur->zTableName);
  sqlite3_free(pCur->zIdColumn);
  sqlite3_free(pCur->zParentColumn);
  pCur->zTableName = 0;
  pCur->zIdColumn = 0;
  pCur->zParentColumn = 0;
  pCur->pCurrent = 0;
  pCur->pClosure = 0;
}

/*
** Close a closure cursor.
*/
static int closureClose(sqlite3_vtab_cursor *cur){
  closure_cursor *pCur = (closure_cursor *)cur;
  closureClearCursor(pCur);
  pCur->pVtab->nCursor--;
  sqlite3_free(pCur);
  return SQLITE_OK;
}

/*
** Advance a cursor to its next row of output
*/
static int closureNext(sqlite3_vtab_cursor *cur){
  closure_cursor *pCur = (closure_cursor*)cur;
  pCur->pCurrent = closureAvlNext(pCur->pCurrent);
  return SQLITE_OK;
}

/*
** Allocate and insert a node
*/
static int closureInsertNode(
  closure_queue *pQueue,  /* Add new node to this queue */
  closure_cursor *pCur,   /* The cursor into which to add the node */
  sqlite3_int64 id,       /* The node ID */
  int iGeneration         /* The generation number for this node */
){
  closure_avl *pNew = sqlite3_malloc( sizeof(*pNew) );
  if( pNew==0 ) return SQLITE_NOMEM;
  memset(pNew, 0, sizeof(*pNew));
  pNew->id = id;
  pNew->iGeneration = iGeneration;
  closureAvlInsert(&pCur->pClosure, pNew);
  queuePush(pQueue, pNew);
  return SQLITE_OK;
}

/*
** Called to "rewind" a cursor back to the beginning so that
** it starts its output over again.  Always called at least once
** prior to any closureColumn, closureRowid, or closureEof call.
**
** This routine actually computes the closure.
**
** See the comment at the beginning of closureBestIndex() for a 
** description of the meaning of idxNum.  The idxStr parameter is
** not used.
*/
static int closureFilter(
  sqlite3_vtab_cursor *pVtabCursor, 
  int idxNum, const char *idxStr,
  int argc, sqlite3_value **argv
){
  closure_cursor *pCur = (closure_cursor *)pVtabCursor;
  closure_vtab *pVtab = pCur->pVtab;
  sqlite3_int64 iRoot;
  int mxGen = 999999999;
  char *zSql;
  sqlite3_stmt *pStmt;
  closure_avl *pAvl;
  int rc = SQLITE_OK;
  const char *zTableName = pVtab->zTableName;
  const char *zIdColumn = pVtab->zIdColumn;
  const char *zParentColumn = pVtab->zParentColumn;
  closure_queue sQueue;

  (void)idxStr;  /* Unused parameter */
  (void)argc;    /* Unused parameter */
  closureClearCursor(pCur);
  memset(&sQueue, 0, sizeof(sQueue));
  if( (idxNum & 1)==0 ){
    /* No root=$root in the WHERE clause.  Return an empty set */
    return SQLITE_OK;
  }
  iRoot = sqlite3_value_int64(argv[0]);
  if( (idxNum & 0x000f0)!=0 ){
    mxGen = sqlite3_value_int(argv[(idxNum>>4)&0x0f]);
    if( (idxNum & 0x00002)!=0 ) mxGen--;
  }
  if( (idxNum & 0x00f00)!=0 ){
    zTableName = (const char*)sqlite3_value_text(argv[(idxNum>>8)&0x0f]);
    pCur->zTableName = sqlite3_mprintf("%s", zTableName);
  }
  if( (idxNum & 0x0f000)!=0 ){
    zIdColumn = (const char*)sqlite3_value_text(argv[(idxNum>>12)&0x0f]);
    pCur->zIdColumn = sqlite3_mprintf("%s", zIdColumn);
  }
  if( (idxNum & 0x0f0000)!=0 ){
    zParentColumn = (const char*)sqlite3_value_text(argv[(idxNum>>16)&0x0f]);
    pCur->zParentColumn = sqlite3_mprintf("%s", zParentColumn);
  }

  zSql = sqlite3_mprintf(
       "SELECT \"%w\".\"%w\" FROM \"%w\" WHERE \"%w\".\"%w\"=?1",
       zTableName, zIdColumn, zTableName, zTableName, zParentColumn);
  if( zSql==0 ){
    return SQLITE_NOMEM;
  }else{
    rc = sqlite3_prepare_v2(pVtab->db, zSql, -1, &pStmt, 0);
    sqlite3_free(zSql);
    if( rc ){
      sqlite3_free(pVtab->base.zErrMsg);
      pVtab->base.zErrMsg = sqlite3_mprintf("%s", sqlite3_errmsg(pVtab->db));
      return rc;
    }
  }
  if( rc==SQLITE_OK ){
    rc = closureInsertNode(&sQueue, pCur, iRoot, 0);
  }
  while( (pAvl = queuePull(&sQueue))!=0 ){
    if( pAvl->iGeneration>=mxGen ) continue;
    sqlite3_bind_int64(pStmt, 1, pAvl->id);
    while( rc==SQLITE_OK && sqlite3_step(pStmt)==SQLITE_ROW ){
      if( sqlite3_column_type(pStmt,0)==SQLITE_INTEGER ){
        sqlite3_int64 iNew = sqlite3_column_int64(pStmt, 0);
        if( closureAvlSearch(pCur->pClosure, iNew)==0 ){
          rc = closureInsertNode(&sQueue, pCur, iNew, pAvl->iGeneration+1);
        }
      }
    }
    sqlite3_reset(pStmt);
  }
  sqlite3_finalize(pStmt);
  if( rc==SQLITE_OK ){
    pCur->pCurrent = closureAvlFirst(pCur->pClosure);
  }

  return rc;
}

/*
** Only the word and distance columns have values.  All other columns
** return NULL
*/
static int closureColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
  closure_cursor *pCur = (closure_cursor*)cur;
  switch( i ){
    case CLOSURE_COL_ID: {
      sqlite3_result_int64(ctx, pCur->pCurrent->id);
      break;
    }
    case CLOSURE_COL_DEPTH: {
      sqlite3_result_int(ctx, pCur->pCurrent->iGeneration);
      break;
    }
    case CLOSURE_COL_ROOT: {
      sqlite3_result_null(ctx);
      break;
    }
    case CLOSURE_COL_TABLENAME: {
      sqlite3_result_text(ctx,
         pCur->zTableName ? pCur->zTableName : pCur->pVtab->zTableName,
         -1, SQLITE_TRANSIENT);
      break;
    }
    case CLOSURE_COL_IDCOLUMN: {
      sqlite3_result_text(ctx,
         pCur->zIdColumn ? pCur->zIdColumn : pCur->pVtab->zIdColumn,
         -1, SQLITE_TRANSIENT);
      break;
    }
    case CLOSURE_COL_PARENTCOLUMN: {
      sqlite3_result_text(ctx,
         pCur->zParentColumn ? pCur->zParentColumn : pCur->pVtab->zParentColumn,
         -1, SQLITE_TRANSIENT);
      break;
    }
  }
  return SQLITE_OK;
}

/*
** The rowid.  For the closure table, this is the same as the "id" column.
*/
static int closureRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
  closure_cursor *pCur = (closure_cursor*)cur;
  *pRowid = pCur->pCurrent->id;
  return SQLITE_OK;
}

/*
** EOF indicator
*/
static int closureEof(sqlite3_vtab_cursor *cur){
  closure_cursor *pCur = (closure_cursor*)cur;
  return pCur->pCurrent==0;
}

/*
** Search for terms of these forms:
**
**   (A)    root = $root
**   (B1)   depth < $depth
**   (B2)   depth <= $depth
**   (B3)   depth = $depth
**   (C)    tablename = $tablename
**   (D)    idcolumn = $idcolumn
**   (E)    parentcolumn = $parentcolumn
**
** 
**
**   idxNum       meaning
**   ----------   ------------------------------------------------------
**   0x00000001   Term of the form (A) found
**   0x00000002   The term of bit-2 is like (B1)
**   0x000000f0   Index in filter.argv[] of $depth.  0 if not used.
**   0x00000f00   Index in filter.argv[] of $tablename.  0 if not used.
**   0x0000f000   Index in filter.argv[] of $idcolumn.  0 if not used
**   0x000f0000   Index in filter.argv[] of $parentcolumn.  0 if not used.
**
** There must be a term of type (A).  If there is not, then the index type
** is 0 and the query will return an empty set.
*/
static int closureBestIndex(
  sqlite3_vtab *pTab,             /* The virtual table */
  sqlite3_index_info *pIdxInfo    /* Information about the query */
){
  int iPlan = 0;
  int i;
  int idx = 1;
  const struct sqlite3_index_constraint *pConstraint;
  closure_vtab *pVtab = (closure_vtab*)pTab;

  pConstraint = pIdxInfo->aConstraint;
  for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
    if( pConstraint->usable==0 ) continue;
    if( (iPlan & 1)==0 
     && pConstraint->iColumn==CLOSURE_COL_ROOT
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
    ){
      iPlan |= 1;
      pIdxInfo->aConstraintUsage[i].argvIndex = 1;
      pIdxInfo->aConstraintUsage[i].omit = 1;
    }
    if( (iPlan & 0x0000f0)==0
     && pConstraint->iColumn==CLOSURE_COL_DEPTH
     && (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT
           || pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE
           || pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ)
    ){
      iPlan |= idx<<4;
      pIdxInfo->aConstraintUsage[i].argvIndex = ++idx;
      if( pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT ) iPlan |= 0x000002;
    }
    if( (iPlan & 0x000f00)==0
     && pConstraint->iColumn==CLOSURE_COL_TABLENAME
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
    ){
      iPlan |= idx<<8;
      pIdxInfo->aConstraintUsage[i].argvIndex = ++idx;
      pIdxInfo->aConstraintUsage[i].omit = 1;
    }
    if( (iPlan & 0x00f000)==0
     && pConstraint->iColumn==CLOSURE_COL_IDCOLUMN
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
    ){
      iPlan |= idx<<12;
      pIdxInfo->aConstraintUsage[i].argvIndex = ++idx;
      pIdxInfo->aConstraintUsage[i].omit = 1;
    }
    if( (iPlan & 0x0f0000)==0
     && pConstraint->iColumn==CLOSURE_COL_PARENTCOLUMN
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
    ){
      iPlan |= idx<<16;
      pIdxInfo->aConstraintUsage[i].argvIndex = ++idx;
      pIdxInfo->aConstraintUsage[i].omit = 1;
    }
  }
  if( (pVtab->zTableName==0    && (iPlan & 0x000f00)==0)
   || (pVtab->zIdColumn==0     && (iPlan & 0x00f000)==0)
   || (pVtab->zParentColumn==0 && (iPlan & 0x0f0000)==0)
  ){
    /* All of tablename, idcolumn, and parentcolumn must be specified
    ** in either the CREATE VIRTUAL TABLE or in the WHERE clause constraints
    ** or else the result is an empty set. */
    iPlan = 0;
  }
  pIdxInfo->idxNum = iPlan;
  if( pIdxInfo->nOrderBy==1
   && pIdxInfo->aOrderBy[0].iColumn==CLOSURE_COL_ID
   && pIdxInfo->aOrderBy[0].desc==0
  ){
    pIdxInfo->orderByConsumed = 1;
  }
  pIdxInfo->estimatedCost = (double)10000;
   
  return SQLITE_OK;
}

/*
** A virtual table module that implements the "approximate_match".
*/
static sqlite3_module closureModule = {
  0,                      /* iVersion */
  closureConnect,         /* xCreate */
  closureConnect,         /* xConnect */
  closureBestIndex,       /* xBestIndex */
  closureDisconnect,      /* xDisconnect */
  closureDisconnect,      /* xDestroy */
  closureOpen,            /* xOpen - open a cursor */
  closureClose,           /* xClose - close a cursor */
  closureFilter,          /* xFilter - configure scan constraints */
  closureNext,            /* xNext - advance a cursor */
  closureEof,             /* xEof - check for end of scan */
  closureColumn,          /* xColumn - read data */
  closureRowid,           /* xRowid - read data */
  0,                      /* xUpdate */
  0,                      /* xBegin */
  0,                      /* xSync */
  0,                      /* xCommit */
  0,                      /* xRollback */
  0,                      /* xFindMethod */
  0,                      /* xRename */
  0,                      /* xSavepoint */
  0,                      /* xRelease */
  0                       /* xRollbackTo */
};

/*
** Register the closure virtual table
*/
#ifdef _WIN32
__declspec(dllexport)
#endif
int sqlite3_closure_init(
  sqlite3 *db, 
  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  int rc = SQLITE_OK;
  SQLITE_EXTENSION_INIT2(pApi);
  (void)pzErrMsg;
  rc = sqlite3_create_module(db, "transitive_closure", &closureModule, 0);
  return rc;
}

<title>The editdist3 algorithm</title>

The editdist3 algorithm is a function that computes the minimum edit distance
(a.k.a. the Levenshtein distance) between two input strings.  Features of
editdist3 include:

   *   It works with unicode (UTF8) text.

   *   A table of insertion, deletion, and substitution costs can be 
       provided by the application.

   *   Multi-character insertsions, deletions, and substitutions can be
       enumerated in the cost table.

<h2>The COST table</h2>

To program the costs of editdist3, create a table such as the following:

<blockquote><pre>
CREATE TABLE editcost(
  iLang INT,   -- The language ID
  cFrom TEXT,  -- Convert text from this
  cTo   TEXT,  -- Convert text into this
  iCost INT    -- The cost of doing the conversionnn
);
</pre></blockquote>

The cost table can be named anything you want - it does not have to be called
"editcost".  And the table can contain additional columns.  However, it the
table must contain the four columns show above, with exactly the names shown.

The iLang column is a non-negative integer that identifies a set of costs
appropriate for a particular language.  The editdist3 function will only use
a single iLang value for any given edit-distance computation.  The default
value is 0.  It is recommended that applications that only need to use a
single langauge always use iLang==0 for all entries.

The iCost column is the numeric cost of transforming cFrom into cTo.  This
value should be a non-negative integer, and should probably be less than 100.
The default single-character insertion and deletion costs are 100 and the
default single-character to single-character substitution cost is 150.  A
cost of 10000 or more is considered "infinite" and causes the rule to be
ignored.

The cFrom and cTo columns show edit transformation strings.  Either or both
columns may contain more than one character.  Or either column (but not both)
may hold an empty string.  When cFrom is empty, that is the cost of inserting
cTo.  When cTo is empty, that is the cost of deleting cFrom.

In the spellfix1 algorithm, cFrom is the text as the user entered it and
cTo is the correctly spelled text as it exists in the database.  The goal
of the editdist3 algorithm is to determine how close the user-entered text is
to the dictionary text.

There are three special-case entries in the cost table:

<table border=1>
<tr><th>cFrom</th><th>cTo</th><th>Meaning</th></tr>
<tr><td>''</td><td>'?'</td><td>The default insertion cost</td></tr>
<tr><td>'?'</td><td>''</td><td>The default deletion cost</td></tr>
<tr><td>'?'</td><td>'?'</td><td>The default substitution cost</td></tr>
</table>

If any of the special-case entries shows above are omitted, then the
value of 100 is used for insertion and deletion and 150 is used for
substitution.  To disable the default insertion, deletion, and/or substitution
set their respective cost to 10000 or more.

Other entries in the cost table specific transforms for particular characters.
The cost of specific transforms should be less than the default costs, or else
the default costs will take precedence and the specific transforms will never 
be used.

Some example, cost table entries:

<blockquote><pre>
INSERT INTO editcost(iLang, cFrom, cTo, iCost)
VALUES(0, 'a', 'ä', 5);
</pre></blockquote>

The rule above says that the letter "a" in user input can be matched against
the letter "ä" in the dictionary with a penalty of 5.

<blockquote><pre>
INSERT INTO editcost(iLang, cFrom, cTo, iCost)
VALUES(0, 'ss', 'ß', 8);
</pre></blockquote>

The number of characters in cFrom and cTo do not need to be the same.  The
rule above says that "ss" on user input will match "ß" with a penalty of 8.

<h2>Experimenting with the editcost3() function</h2>

The [./spellfix1.wiki | spellfix1 virtual table]
uses editdist3 if the "edit_cost_table=TABLE" option
is specified as an argument when the spellfix1 virtual table is created.  
But editdist3 can also be tested directly using the built-in "editdist3()"
SQL function.  The editdist3() SQL function has 3 forms:

  1.  editdist3('TABLENAME');
  2.  editdist3('string1', 'string2');
  3.  editdist3('string1', 'string2', langid);

The first form loads the edit distance coefficients from a table called
'TABLENAME'.  Any prior coefficients are discarded.  So when experimenting
with weights and the weight table changes, simply rerun the single-argument
form of editdist3() to reload revised coefficients.  Note that the 
edit distance
weights used by the editdist3() SQL function are independent from the
weights used by the spellfix1 virtual table.

The second and third forms return the computed edit distance between strings
'string1' and "string2'.  In the second form, an language id of 0 is used.
The language id is specified in the third form.

**
** LIMITS
**
** The maximum ruleset number is 2147483647.  The maximum length of either
** of the strings in the second or third column of the fuzzer data table
** is 50 bytes.  The maximum cost on a rule is 1000.
*/
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1

/* If SQLITE_DEBUG is not defined, disable assert statements. */
#if !defined(NDEBUG) && !defined(SQLITE_DEBUG)
# define NDEBUG
#endif


#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>

#ifndef SQLITE_OMIT_VIRTUALTABLE

  0,                           /* xFindMethod */
  0,                           /* xRename */
};

#endif /* SQLITE_OMIT_VIRTUALTABLE */







#ifdef _WIN32

__declspec(dllexport)
#endif


int sqlite3_fuzzer_init(



  sqlite3 *db, 


  char **pzErrMsg, 




  const sqlite3_api_routines *pApi



){







  int rc = SQLITE_OK;

  SQLITE_EXTENSION_INIT2(pApi);
  rc = sqlite3_create_module(db, "fuzzer", &fuzzerModule, 0);
















  return rc;
}

/*
** 2013-04-17
**
** 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.
**
******************************************************************************
**
** This SQLite extension implements functions for the exact display
** and input of IEEE754 Binary64 floating-point numbers.
**
**   ieee754(X)
**   ieee754(Y,Z)
**
** In the first form, the value X should be a floating-point number.
** The function will return a string of the form 'ieee754(Y,Z)' where
** Y and Z are integers such that X==Y*pow(w.0,Z).
**
** In the second form, Y and Z are integers which are the mantissa and
** base-2 exponent of a new floating point number.  The function returns
** a floating-point value equal to Y*pow(2.0,Z).
**
** Examples:
**
**     ieee754(2.0)       ->     'ieee754(2,0)'
**     ieee754(45.25)     ->     'ieee754(181,-2)'
**     ieee754(2, 0)      ->     2.0
**     ieee754(181, -2)   ->     45.25
*/
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1
#include <assert.h>
#include <string.h>

/*
** Implementation of the ieee754() function
*/
static void ieee754func(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  if( argc==1 ){
    sqlite3_int64 m, a;
    double r;
    int e;
    int isNeg;
    char zResult[100];
    assert( sizeof(m)==sizeof(r) );
    if( sqlite3_value_type(argv[0])!=SQLITE_FLOAT ) return;
    r = sqlite3_value_double(argv[0]);
    if( r<0.0 ){
      isNeg = 1;
      r = -r;
    }else{
      isNeg = 0;
    }
    memcpy(&a,&r,sizeof(a));
    if( a==0 ){
      e = 0;
      m = 0;
    }else{
      e = a>>52;
      m = a & ((((sqlite3_int64)1)<<52)-1);
      m |= ((sqlite3_int64)1)<<52;
      while( e<1075 && m>0 && (m&1)==0 ){
        m >>= 1;
        e++;
      }
      if( isNeg ) m = -m;
    }
    sqlite3_snprintf(sizeof(zResult), zResult, "ieee754(%lld,%d)",
                     m, e-1075);
    sqlite3_result_text(context, zResult, -1, SQLITE_TRANSIENT);
  }else if( argc==2 ){
    sqlite3_int64 m, e, a;
    double r;
    int isNeg = 0;
    m = sqlite3_value_int64(argv[0]);
    e = sqlite3_value_int64(argv[1]);
    if( m<0 ){
      isNeg = 1;
      m = -m;
      if( m<0 ) return;
    }else if( m==0 && e>1000 && e<1000 ){
      sqlite3_result_double(context, 0.0);
      return;
    }
    while( (m>>32)&0xffe00000 ){
      m >>= 1;
      e++;
    }
    while( ((m>>32)&0xfff00000)==0 ){
      m <<= 1;
      e--;
    }
    e += 1075;
    if( e<0 ) e = m = 0;
    if( e>0x7ff ) m = 0;
    a = m & ((((sqlite3_int64)1)<<52)-1);
    a |= e<<52;
    if( isNeg ) a |= ((sqlite3_int64)1)<<63;
    memcpy(&r, &a, sizeof(r));
    sqlite3_result_double(context, r);
  }
}


#ifdef _WIN32
__declspec(dllexport)
#endif
int sqlite3_ieee_init(
  sqlite3 *db, 
  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  int rc = SQLITE_OK;
  SQLITE_EXTENSION_INIT2(pApi);
  (void)pzErrMsg;  /* Unused parameter */
  rc = sqlite3_create_function(db, "ieee754", 1, SQLITE_UTF8, 0,
                               ieee754func, 0, 0);
  if( rc==SQLITE_OK ){
    rc = sqlite3_create_function(db, "ieee754", 2, SQLITE_UTF8, 0,
                                 ieee754func, 0, 0);
  }
  return rc;
}

/*
** 2013-02-28
**
** 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.
**
******************************************************************************
**
** This file contains code to implement the next_char(A,T,F,W) SQL function.
**
** The next_char(A,T,F,H) function finds all valid "next" characters for
** string A given the vocabulary in T.F.  The T.F field should be indexed.
** If the W value exists and is a non-empty string, then it is an SQL
** expression that limits the entries in T.F that will be considered.
**
** For example, suppose an application has a dictionary like this:
**
**   CREATE TABLE dictionary(word TEXT UNIQUE);
**
** Further suppose that for user keypad entry, it is desired to disable
** (gray out) keys that are not valid as the next character.  If the
** the user has previously entered (say) 'cha' then to find all allowed
** next characters (and thereby determine when keys should not be grayed
** out) run the following query:
**
**   SELECT next_char('cha','dictionary','word');
*/
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1
#include <string.h>

/*
** A structure to hold context of the next_char() computation across
** nested function calls.
*/
typedef struct nextCharContext nextCharContext;
struct nextCharContext {
  sqlite3 *db;                      /* Database connection */
  sqlite3_stmt *pStmt;              /* Prepared statement used to query */
  const unsigned char *zPrefix;     /* Prefix to scan */
  int nPrefix;                      /* Size of zPrefix in bytes */
  int nAlloc;                       /* Space allocated to aResult */
  int nUsed;                        /* Space used in aResult */
  unsigned int *aResult;            /* Array of next characters */
  int mallocFailed;                 /* True if malloc fails */
  int otherError;                   /* True for any other failure */
};

/*
** Append a result character if the character is not already in the
** result.
*/
static void nextCharAppend(nextCharContext *p, unsigned c){
  int i;
  for(i=0; i<p->nUsed; i++){
    if( p->aResult[i]==c ) return;
  }
  if( p->nUsed+1 > p->nAlloc ){
    unsigned int *aNew;
    int n = p->nAlloc*2 + 30;
    aNew = sqlite3_realloc(p->aResult, n*sizeof(unsigned int));
    if( aNew==0 ){
      p->mallocFailed = 1;
      return;
    }else{
      p->aResult = aNew;
      p->nAlloc = n;
    }
  }
  p->aResult[p->nUsed++] = c;
}

/*
** Write a character into z[] as UTF8.  Return the number of bytes needed
** to hold the character
*/
static int writeUtf8(unsigned char *z, unsigned c){
  if( c<0x00080 ){
    z[0] = (unsigned char)(c&0xff);
    return 1;
  }
  if( c<0x00800 ){
    z[0] = 0xC0 + (unsigned char)((c>>6)&0x1F);
    z[1] = 0x80 + (unsigned char)(c & 0x3F);
    return 2;
  }
  if( c<0x10000 ){
    z[0] = 0xE0 + (unsigned char)((c>>12)&0x0F);
    z[1] = 0x80 + (unsigned char)((c>>6) & 0x3F);
    z[2] = 0x80 + (unsigned char)(c & 0x3F);
    return 3;
  }
  z[0] = 0xF0 + (unsigned char)((c>>18) & 0x07);
  z[1] = 0x80 + (unsigned char)((c>>12) & 0x3F);
  z[2] = 0x80 + (unsigned char)((c>>6) & 0x3F);
  z[3] = 0x80 + (unsigned char)(c & 0x3F);
  return 4;
}

/*
** Read a UTF8 character out of z[] and write it into *pOut.  Return
** the number of bytes in z[] that were used to construct the character.
*/
static int readUtf8(const unsigned char *z, unsigned *pOut){
  static const unsigned char validBits[] = {
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
    0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
    0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
    0x00, 0x01, 0x02, 0x03, 0x00, 0x01, 0x00, 0x00,
  };
  unsigned c = z[0];
  if( c<0xc0 ){
    *pOut = c;
    return 1;
  }else{
    int n = 1;
    c = validBits[c-0xc0];
    while( (z[n] & 0xc0)==0x80 ){
      c = (c<<6) + (0x3f & z[n++]);
    }
    if( c<0x80 || (c&0xFFFFF800)==0xD800 || (c&0xFFFFFFFE)==0xFFFE ){
      c = 0xFFFD;
    }
    *pOut = c;
    return n;
  }
}

/*
** The nextCharContext structure has been set up.  Add all "next" characters
** to the result set.
*/
static void findNextChars(nextCharContext *p){
  unsigned cPrev = 0;
  unsigned char zPrev[8];
  int n, rc;
  
  for(;;){
    sqlite3_bind_text(p->pStmt, 1, (char*)p->zPrefix, p->nPrefix,
                      SQLITE_STATIC);
    n = writeUtf8(zPrev, cPrev+1);
    sqlite3_bind_text(p->pStmt, 2, (char*)zPrev, n, SQLITE_STATIC);
    rc = sqlite3_step(p->pStmt);
    if( rc==SQLITE_DONE ){
      sqlite3_reset(p->pStmt);
      return;
    }else if( rc!=SQLITE_ROW ){
      p->otherError = rc;
      return;
    }else{
      const unsigned char *zOut = sqlite3_column_text(p->pStmt, 0);
      unsigned cNext;
      n = readUtf8(zOut+p->nPrefix, &cNext);
      sqlite3_reset(p->pStmt);
      nextCharAppend(p, cNext);
      cPrev = cNext;
      if( p->mallocFailed ) return;
    }
  }
}


/*
** next_character(A,T,F,W)
**
** Return a string composted of all next possible characters after
** A for elements of T.F.  If W is supplied, then it is an SQL expression
** that limits the elements in T.F that are considered.
*/
static void nextCharFunc(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  nextCharContext c;
  const unsigned char *zTable = sqlite3_value_text(argv[1]);
  const unsigned char *zField = sqlite3_value_text(argv[2]);
  const unsigned char *zWhere;
  char *zSql;
  int rc;

  memset(&c, 0, sizeof(c));
  c.db = sqlite3_context_db_handle(context);
  c.zPrefix = sqlite3_value_text(argv[0]);
  c.nPrefix = sqlite3_value_bytes(argv[0]);
  if( zTable==0 || zField==0 || c.zPrefix==0 ) return;
  if( argc<4
   || (zWhere = sqlite3_value_text(argv[3]))==0
   || zWhere[0]==0
  ){
    zSql = sqlite3_mprintf(
        "SELECT \"%w\" FROM \"%w\""
        " WHERE \"%w\">=(?1 || ?2)"
        "   AND \"%w\"<=(?1 || char(1114111))" /* 1114111 == 0x10ffff */
        " ORDER BY 1 ASC LIMIT 1",
        zField, zTable, zField, zField);
  }else{
    zSql = sqlite3_mprintf(
        "SELECT \"%w\" FROM \"%w\""
        " WHERE \"%w\">=(?1 || ?2)"
        "   AND \"%w\"<=(?1 || char(1114111))" /* 1114111 == 0x10ffff */
        "   AND (%s)"
        " ORDER BY 1 ASC LIMIT 1",
        zField, zTable, zField, zField, zWhere);
  }
  if( zSql==0 ){
    sqlite3_result_error_nomem(context);
    return;
  }

  rc = sqlite3_prepare_v2(c.db, zSql, -1, &c.pStmt, 0);
  sqlite3_free(zSql);
  if( rc ){
    sqlite3_result_error(context, sqlite3_errmsg(c.db), -1);
    return;
  }
  findNextChars(&c);
  if( c.mallocFailed ){
    sqlite3_result_error_nomem(context);
  }else{
    unsigned char *pRes;
    pRes = sqlite3_malloc( c.nUsed*4 + 1 );
    if( pRes==0 ){
      sqlite3_result_error_nomem(context);
    }else{
      int i;
      int n = 0;
      for(i=0; i<c.nUsed; i++){
        n += writeUtf8(pRes+n, c.aResult[i]);
      }
      pRes[n] = 0;
      sqlite3_result_text(context, (const char*)pRes, n, sqlite3_free);
    }
  }
  sqlite3_finalize(c.pStmt);
  sqlite3_free(c.aResult);
}

#ifdef _WIN32
__declspec(dllexport)
#endif
int sqlite3_nextchar_init(
  sqlite3 *db, 
  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  int rc = SQLITE_OK;
  SQLITE_EXTENSION_INIT2(pApi);
  (void)pzErrMsg;  /* Unused parameter */
  rc = sqlite3_create_function(db, "next_char", 3, SQLITE_UTF8, 0,
                               nextCharFunc, 0, 0);
  if( rc==SQLITE_OK ){
    rc = sqlite3_create_function(db, "next_char", 4, SQLITE_UTF8, 0,
                                 nextCharFunc, 0, 0);
  }
  return rc;
}

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
******************************************************************************
**
** The code in this file implements a compact but reasonably
** efficient regular-expression matcher for posix extended regular
** expressions against UTF8 text.
**
** This file is an SQLite extension.  It registers a single function
** named "regexp(A,B)" where A is the regular expression and B is the
** string to be matched.  By registering this function, SQLite will also
** then implement the "B regexp A" operator.  Note that with the function
** the regular expression comes first, but with the operator it comes
** second.
**
**  The following regular expression syntax is supported:
**
**     X*      zero or more occurrences of X
**     X+      one or more occurrences of X
**     X?      zero or one occurrences of X
**     X{p,q}  between p and q occurrences of X
**     (X)     match X
**     X|Y     X or Y

** exhibits exponential behavior.  Note that the X{p,q} operator expands
** to p copies of X following by q-p copies of X? and that the size of the
** regular expression in the O(N*M) performance bound is computed after
** this expansion.
*/
#include <string.h>
#include <stdlib.h>
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1

/*
** The following #defines change the names of some functions implemented in
** this file to prevent name collisions with C-library functions of the
** same name.
*/
#define re_match   sqlite3re_match
#define re_compile sqlite3re_compile
#define re_free    sqlite3re_free

/* The end-of-input character */
#define RE_EOF            0    /* End of input */

/* The NFA is implemented as sequence of opcodes taken from the following
** set.  Each opcode has a single integer argument.
*/

static int re_space_char(int c){
  return c==' ' || c=='\t' || c=='\n' || c=='\r' || c=='\v' || c=='\f';
}

/* Run a compiled regular expression on the zero-terminated input
** string zIn[].  Return true on a match and false if there is no match.
*/
static int re_match(ReCompiled *pRe, const unsigned char *zIn, int nIn){
  ReStateSet aStateSet[2], *pThis, *pNext;
  ReStateNumber aSpace[100];
  ReStateNumber *pToFree;
  unsigned int i = 0;
  unsigned int iSwap = 0;
  int c = RE_EOF+1;
  int cPrev = 0;

  zStr = (const unsigned char*)sqlite3_value_text(argv[1]);
  if( zStr!=0 ){
    sqlite3_result_int(context, re_match(pRe, zStr, -1));
  }
}

/*
** Invoke this routine to register the regexp() function with the
** SQLite database connection.







*/







#ifdef _WIN32
__declspec(dllexport)

#endif


int sqlite3_regexp_init(

  sqlite3 *db, 
  char **pzErrMsg, 

  const sqlite3_api_routines *pApi

){







  int rc = SQLITE_OK;

  SQLITE_EXTENSION_INIT2(pApi);



  rc = sqlite3_create_function(db, "regexp", 2, SQLITE_UTF8, 0,
                                 re_sql_func, 0, 0);
  return rc;
}

**
*************************************************************************
**
** This module implements the spellfix1 VIRTUAL TABLE that can be used
** to search a large vocabulary for close matches.  See separate
** documentation files (spellfix1.wiki and editdist3.wiki) for details.
*/

#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1

#ifndef SQLITE_AMALGAMATION
# include <string.h>
# include <stdio.h>
# include <stdlib.h>

# include <assert.h>
# define ALWAYS(X)  1
# define NEVER(X)   0
  typedef unsigned char u8;
  typedef unsigned short u16;


# include <ctype.h>
#endif

/*
** Character classes for ASCII characters:
**
**   0   ''        Silent letters:   H W
**   1   'A'       Any vowel:   A E I O U (Y)
**   2   'B'       A bilabeal stop or fricative:  B F P V W

  for(i=0; i<sizeof(translit)/sizeof(translit[0])-1; i++){
    assert( translit[i].cFrom<translit[i+1].cFrom );
  }

  return rc;
}












/*
** Extension load function.
*/
#ifdef _WIN32
__declspec(dllexport)
#endif
int sqlite3_spellfix_init(
  sqlite3 *db, 
  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  SQLITE_EXTENSION_INIT2(pApi);
  return spellfix1Register(db);
}

<title>The Spellfix1 Virtual Table</title>

This spellfix1 virtual table is used to search
a large vocabulary for close matches.  For example, spellfix1
can be used to suggest corrections to misspelled words.  Or,
it could be used with FTS4 to do full-text search using potentially
misspelled words.

Create an instance of the spellfix1 virtual table like this:

<blockquote><pre>
CREATE VIRTUAL TABLE demo USING spellfix1;
</pre></blockquote>

The "spellfix1" term is the name of this module and must be entered as
shown.  The "demo" term is the
name of the virtual table you will be creating and can be altered
to suit the needs of your application.  The virtual table is initially
empty.  In order for the virtual table to be useful, you will need to
populate it with your vocabulary.  Suppose you
have a list of words in a table named "big_vocabulary".  Then do this:

<blockquote><pre>
INSERT INTO demo(word) SELECT word FROM big_vocabulary;
</pre></blockquote>

If you intend to use this virtual table in cooperation with an FTS4
table (for spelling correctly of search terms) then you might extract
the vocabulary using an fts3aux table:

<blockquote><pre>
INSERT INTO demo(word) SELECT term FROM search_aux WHERE col='*';
</pre></blockquote>

You can also provide the virtual table with a "rank" for each word.
The "rank" is an estimate of how common the word is.  Larger numbers
mean the word is more common.  If you omit the rank when populating
the table, then a rank of 1 is assumed.  But if you have rank 
information, you can supply it and the virtual table will show a
slight preference for selecting more commonly used terms.  To
populate the rank from an fts4aux table "search_aux" do something
like this:

<blockquote><pre>
INSERT INTO demo(word,rank)
   SELECT term, documents FROM search_aux WHERE col='*';
</pre></blockquote>

To query the virtual table, include a MATCH operator in the WHERE
clause.  For example:

<blockquote><pre>
SELECT word FROM demo WHERE word MATCH 'kennasaw';
</pre></blockquote>

Using a dataset of American place names (derived from
[http://geonames.usgs.gov/domestic/download_data.htm]) the query above
returns 20 results beginning with:

<blockquote><pre>
kennesaw
kenosha
kenesaw
kenaga
keanak
</pre></blockquote>

If you append the character '*' to the end of the pattern, then
a prefix search is performed.  For example:

<blockquote><pre>
SELECT word FROM demo WHERE word MATCH 'kennes*';
</pre></blockquote>

Yields 20 results beginning with:

<blockquote><pre>
kennesaw
kennestone
kenneson
kenneys
keanes
keenes
</pre></blockquote>

<h2>Search Refinements</h2>

By default, the spellfix1 table returns no more than 20 results.
(It might return less than 20 if there were fewer good matches.)
You can change the upper bound on the number of returned rows by
adding a "top=N" term to the WHERE clause of your query, where N
is the new maximum.  For example, to see the 5 best matches:

<blockquote><pre>
SELECT word FROM demo WHERE word MATCH 'kennes*' AND top=5;
</pre></blockquote>

Each entry in the spellfix1 virtual table is associated with a
a particular language, identified by the integer "langid" column.
The default langid is 0 and if no other actions are taken, the
entire vocabulary is a part of the 0 language.  But if your application
needs to operate in multiple languages, then you can specify different
vocabulary items for each language by specifying the langid field
when populating the table.  For example:

<blockquote><pre>
INSERT INTO demo(word,langid) SELECT word, 0 FROM en_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 1 FROM de_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 2 FROM fr_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 3 FROM ru_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 4 FROM cn_vocabulary;
</pre></blockquote>

After the virtual table has been populated with items from multiple
languages, specify the language of interest using a "langid=N" term
in the WHERE clause of the query:

<blockquote><pre>
SELECT word FROM demo WHERE word MATCH 'hildes*' AND langid=1;
</pre></blockquote>

Note that if you do not include the "langid=N" term in the WHERE clause,
the search will be against language 0 (English in the example above.)
All spellfix1 searches are against a single language id.  There is no
way to search all languages at once.
 

<h2>Virtual Table Details</h2>

The virtual table actually has a unique rowid with seven columns plus five
extra hidden columns.  The columns are as follows:

<blockquote><dl>
<dt><b>rowid</b><dd>
A unique integer number associated with each
vocabulary item in the table.  This can be used
as a foreign key on other tables in the database.

<dt><b>word</b><dd>
The text of the word that matches the pattern.
Both word and pattern can contains unicode characters
and can be mixed case.

<dt><b>rank</b><dd>
This is the rank of the word, as specified in the
original INSERT statement.


<dt><b>distance</b><dd>
This is an edit distance or Levensthein distance going
from the pattern to the word.

<dt><b>langid</b><dd>
This is the language-id of the word.  All queries are
against a single language-id, which defaults to 0.
For any given query this value is the same on all rows.

<dt><b>score</b><dd>
The score is a combination of rank and distance.  The
idea is that a lower score is better.  The virtual table
attempts to find words with the lowest score and 
by default (unless overridden by ORDER BY) returns
results in order of increasing score.

<dt><b>matchlen</b><dd>
In a prefix search, the matchlen is the number of characters in
the string that match against the prefix.  For a non-prefix search,
this is the same as length(word).

<dt><b>phonehash</b><dd>
This column shows the phonetic hash prefix that was used to restrict
the search.  For any given query, this column should be the same for
every row.  This information is available for diagnostic purposes and
is not normally considered useful in real applications.

<dt><b>top</b><dd>
(HIDDEN)  For any query, this value is the same on all
rows.  It is an integer which is the maximum number of
rows that will be output.  The actually number of rows
output might be less than this number, but it will never
be greater.  The default value for top is 20, but that
can be changed for each query by including a term of
the form "top=N" in the WHERE clause of the query.

<dt><b>scope</b><dd>
(HIDDEN)  For any query, this value is the same on all
rows.  The scope is a measure of how widely the virtual
table looks for matching words.  Smaller values of
scope cause a broader search.  The scope is normally
choosen automatically and is capped at 4.  Applications
can change the scope by including a term of the form
"scope=N" in the WHERE clause of the query.  Increasing
the scope will make the query run faster, but will reduce
the possible corrections.

<dt><b>srchcnt</b><dd>
(HIDDEN)  For any query, this value is the same on all
rows.  This value is an integer which is the number of
of words examined using the edit-distance algorithm to
find the top matches that are ultimately displayed.  This
value is for diagnostic use only.

<dt><b>soundslike</b><dd>
(HIDDEN)  When inserting vocabulary entries, this field
can be set to an spelling that matches what the word
sounds like.  See the DEALING WITH UNUSUAL AND DIFFICULT
SPELLINGS section below for details.

<dt><b>command</b><dd>
(HIDDEN)  The value of the "command" column is always NULL.  However,
applications can insert special strings into the "command" column in order
to provoke certain behaviors in the spellfix1 virtual table.
For example, inserting the string 'reset' into the "command" column
will cause the virtual table will reread its edit distance weights
(if there are any).
</dl></blockquote>

<h2>Algorithm</h2>

The spellfix1 virtual table creates a single
shadow table named "%_vocab" (where the % is replaced by the name of
the virtual table; Ex: "demo_vocab" for the "demo" virtual table).  
the shadow table contains the following columns:

<blockquote><dl>
<dt><b>id</b><dd>
The unique id (INTEGER PRIMARY KEY)

<dt><b>rank</b><dd>
The rank of word.

<dt><b>langid</b><dd>
The language id for this entry.

<dt><b>word</b><dd>
The original UTF8 text of the vocabulary word

<dt><b>k1</b><dd>
The word transliterated into lower-case ASCII.  
There is a standard table of mappings from non-ASCII
characters into ASCII.  Examples: "æ" -> "ae",
"þ" -> "th", "ß" -> "ss", "á" -> "a", ...  The
accessory function spellfix1_translit(X) will do
the non-ASCII to ASCII mapping.  The built-in lower(X)
function will convert to lower-case.  Thus:
k1 = lower(spellfix1_translit(word)).

<dt><b>k2</b><dd>
This field holds a phonetic code derived from k1.  Letters
that have similar sounds are mapped into the same symbol.
For example, all vowels and vowel clusters become the
single symbol "A".  And the letters "p", "b", "f", and
"v" all become "B".  All nasal sounds are represented
as "N".  And so forth.  The mapping is base on
ideas found in Soundex, Metaphone, and other
long-standing phonetic matching systems.  This key can
be generated by the function spellfix1_phonehash(X).  
Hence: k2 = spellfix1_phonehash(k1)
</dl></blockquote>

There is also a function for computing the Wagner edit distance or the
Levenshtein distance between a pattern and a word.  This function
is exposed as spellfix1_editdist(X,Y).  The edit distance function
returns the "cost" of converting X into Y.  Some transformations
cost more than others.  Changing one vowel into a different vowel,
for example is relatively cheap, as is doubling a constant, or
omitting the second character of a double-constant.  Other transformations
or more expensive.  The idea is that the edit distance function returns
a low cost of words that are similar and a higher cost for words
that are futher apart.  In this implementation, the maximum cost
of any single-character edit (delete, insert, or substitute) is 100,
with lower costs for some edits (such as transforming vowels).

The "score" for a comparison is the edit distance between the pattern
and the word, adjusted down by the base-2 logorithm of the word rank.
For example, a match with distance 100 but rank 1000 would have a
score of 122 (= 100 - log2(1000) + 32) where as a match with distance
100 with a rank of 1 would have a score of 131 (100 - log2(1) + 32).
(NB:  The constant 32 is added to each score to keep it from going
negative in case the edit distance is zero.)  In this way, frequently
used words get a slightly lower cost which tends to move them toward
the top of the list of alternative spellings.

A straightforward implementation of a spelling corrector would be
to compare the search term against every word in the vocabulary
and select the 20 with the lowest scores.  However, there will 
typically be hundreds of thousands or millions of words in the
vocabulary, and so this approach is not fast enough.

Suppose the term that is being spell-corrected is X.  To limit
the search space, X is converted to a k2-like key using the
equivalent of:

<blockquote><pre>
   key = spellfix1_phonehash(lower(spellfix1_translit(X)))
</pre></blockquote>

This key is then limited to "scope" characters.  The default scope
value is 4, but an alternative scope can be specified using the
"scope=N" term in the WHERE clause.  After the key has been truncated,
the edit distance is run against every term in the vocabulary that
has a k2 value that begins with the abbreviated key.

For example, suppose the input word is "Paskagula".  The phonetic 
key is "BACACALA" which is then truncated to 4 characters "BACA".
The edit distance is then run on the 4980 entries (out of
272,597 entries total) of the vocabulary whose k2 values begin with
BACA, yielding "Pascagoula" as the best match.

Only terms of the vocabulary with a matching langid are searched.
Hence, the same table can contain entries from multiple languages
and only the requested language will be used.  The default langid
is 0.

<h2>Configurable Edit Distance</h2>

The built-in Wagner edit-distance function with fixed weights can be
replaced by the [./editdist3.wiki | editdist3()] edit-distance function
with application-defined weights and support for unicode, by specifying
the "edit_cost_table=<i>TABLENAME</i>" parameter to the spellfix1 module
when the virtual table is created.
For example:

<blockquote><pre>
CREATE VIRTUAL TABLE demo2 USING spellfix1(edit_cost_table=APPCOST);
</pre></blockquote>

In the example above, the APPCOST table would be interrogated to find
the edit distance coefficients.  It is the presence of the "edit_cost_table="
parameter to the spellfix1 module name that causes editdist3() to be used
in place of the built-in edit distance function.

The edit distance coefficients are normally read from the APPCOST table
once and there after stored in memory.  Hence, run-time changes to the
APPCOST table will not normally effect the edit distance results.
However, inserting the special string 'reset' into the "command" column of the
virtual table causes the edit distance coefficients to be reread the
APPCOST table.  Hence, applications should run a SQL statement similar
to the following when changes to the APPCOST table occur:

<blockquote>
INSERT INTO demo2(command) VALUES('reset');
</blockquote>

The tables used for edit distance costs can be changed using a command
like the following:

<blockquote>
INSERT INTO demo2(command) VALUES('edit_cost_table=APPCOST2');
</blockquote>

In the example above, any prior edit distance costs would be discarded and
all future queries would use the costs found in the APPCOST2 table.  If the
name of the table specified by the "edit_cost_table" command is "NULL", then
theh built-in Wagner edit-distance function will be used instead of the
editdist3() function in all future queries.

<h2>Dealing With Unusual And Difficult Spellings</h2>

The algorithm above works quite well for most cases, but there are
exceptions.  These exceptions can be dealt with by making additional
entries in the virtual table using the "soundslike" column.

For example, many words of Greek origin begin with letters "ps" where
the "p" is silent.  Ex:  psalm, pseudonym, psoriasis, psyche.  In
another example, many Scottish surnames can be spelled with an
initial "Mac" or "Mc".  Thus, "MacKay" and "McKay" are both pronounced
the same.

Accommodation can be made for words that are not spelled as they
sound by making additional entries into the virtual table for the
same word, but adding an alternative spelling in the "soundslike"
column.  For example, the canonical entry for "psalm" would be this:

<blockquote><pre>
  INSERT INTO demo(word) VALUES('psalm');
</pre></blockquote>

To enhance the ability to correct the spelling of "salm" into
"psalm", make an addition entry like this:

<blockquote><pre>
  INSERT INTO demo(word,soundslike) VALUES('psalm','salm');
</pre></blockquote>

It is ok to make multiple entries for the same word as long as
each entry has a different soundslike value.  Note that if no
soundslike value is specified, the soundslike defaults to the word
itself.

Listed below are some cases where it might make sense to add additional
soundslike entries.  The specific entries will depend on the application
and the target language.

  *   Silent "p" in words beginning with "ps":  psalm, psyche

  *   Silent "p" in words beginning with "pn":  pneumonia, pneumatic

  *   Silent "p" in words beginning with "pt":  pterodactyl, ptolemaic

  *   Silent "d" in words beginning with "dj":  djinn, Djikarta

  *   Silent "k" in words beginning with "kn":  knight, Knuthson

  *   Silent "g" in words beginning with "gn":  gnarly, gnome, gnat

  *   "Mac" versus "Mc" beginning Scottish surnames

  *   "Tch" sounds in Slavic words:  Tchaikovsky vs. Chaykovsky

  *   The letter "j" pronounced like "h" in Spanish:  LaJolla

  *   Words beginning with "wr" versus "r":  write vs. rite

  *   Miscellanous problem words such as "debt", "tsetse",
      "Nguyen", "Van Nuyes".

<h2>Auxiliary Functions</h2>

The source code module that implements the spellfix1 virtual table also
implements several SQL functions that might be useful to applications
that employ spellfix1 or for testing or diagnostic work while developing
applications that use spellfix1.  The following auxiliary functions are
available:

<blockquote><dl>
<dt><b>editdist3(P,W)<br>editdist2(P,W,L)<br>editdist3(T)</b><dd>
These routines provide direct access to the version of the Wagner
edit-distance function that allows for application-defined weights
on edit operations.  The first two forms of this function compare
pattern P against word W and return the edit distance.  In the first
function, the langid is assumed to be 0 and in the second, the
langid is given by the L parameter.  The third form of this function
reloads edit distance coefficience from the table named by T.

<dt><b>spellfix1_editdist(P,W)</b><dd>
This routine provides access to the built-in Wagner edit-distance
function that uses default, fixed costs.  The value returned is
the edit distance needed to transform W into P.

<dt><b>spellfix1_phonehash(X)</b><dd>
This routine constructs a phonetic hash of the pure ascii input word X
and returns that hash.  This routine is used internally by spellfix1 in
order to transform the K1 column of the shadow table into the K2
column.

<dt><b>spellfix1_scriptcode(X)</b><dd>
Given an input string X, this routine attempts to determin the dominant
script of that input and returns the ISO-15924 numeric code for that
script.  The current implementation understands the following scripts:
<ul>
<li> 215 - Latin
<li> 220 - Cyrillic
<li> 200 - Greek
</ul>
Additional language codes might be added in future releases.

<dt><b>spellfix1_translit(X)</b><dd>
This routine transliterates unicode text into pure ascii, returning
the pure ascii representation of the input text X.  This is the function
that is used internally to transform vocabulary words into the K1
column of the shadow table.

</dl></blockquote>

**     CREATE VIRTUAL TABLE nums USING wholenumber;
**     SELECT value FROM nums WHERE value<10;
**
** Results in:
**
**     1 2 3 4 5 6 7 8 9
*/
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1
#include <assert.h>
#include <string.h>

#ifndef SQLITE_OMIT_VIRTUALTABLE


/* A wholenumber cursor object */

  0,                         /* xRollback */
  0,                         /* xFindMethod */
  0,                         /* xRename */
};

#endif /* SQLITE_OMIT_VIRTUALTABLE */

#ifdef _WIN32

__declspec(dllexport)
#endif
int sqlite3_wholenumber_init(

  sqlite3 *db, 
  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  int rc = SQLITE_OK;
  SQLITE_EXTENSION_INIT2(pApi);
#ifndef SQLITE_OMIT_VIRTUALTABLE
  rc = sqlite3_create_module(db, "wholenumber", &wholenumberModule, 0);
#endif
  return rc;
}

  $(TOP)/src/test_backup.c \
  $(TOP)/src/test_btree.c \
  $(TOP)/src/test_config.c \
  $(TOP)/src/test_demovfs.c \
  $(TOP)/src/test_devsym.c \
  $(TOP)/src/test_fs.c \
  $(TOP)/src/test_func.c \

  $(TOP)/src/test_hexio.c \
  $(TOP)/src/test_init.c \
  $(TOP)/src/test_intarray.c \
  $(TOP)/src/test_journal.c \
  $(TOP)/src/test_malloc.c \
  $(TOP)/src/test_multiplex.c \
  $(TOP)/src/test_mutex.c \
  $(TOP)/src/test_onefile.c \
  $(TOP)/src/test_osinst.c \
  $(TOP)/src/test_pcache.c \
  $(TOP)/src/test_quota.c \

  $(TOP)/src/test_rtree.c \
  $(TOP)/src/test_schema.c \
  $(TOP)/src/test_server.c \
  $(TOP)/src/test_stat.c \
  $(TOP)/src/test_sqllog.c \
  $(TOP)/src/test_superlock.c \
  $(TOP)/src/test_syscall.c \
  $(TOP)/src/test_tclvar.c \
  $(TOP)/src/test_thread.c \
  $(TOP)/src/test_vfs.c \
  $(TOP)/src/test_wsd.c

# Extensions to be statically loaded.
#
TESTSRC += \
  $(TOP)/ext/misc/amatch.c \
  $(TOP)/ext/misc/closure.c \
  $(TOP)/ext/misc/fuzzer.c \
  $(TOP)/ext/misc/ieee754.c \
  $(TOP)/ext/misc/nextchar.c \
  $(TOP)/ext/misc/regexp.c \
  $(TOP)/ext/misc/spellfix.c \
  $(TOP)/ext/misc/wholenumber.c


#TESTSRC += $(TOP)/ext/fts2/fts2_tokenizer.c
#TESTSRC += $(TOP)/ext/fts3/fts3_tokenizer.c

TESTSRC2 = \
  $(TOP)/src/attach.c \
  $(TOP)/src/backup.c \

static int selectNodeIsConstant(Walker *pWalker, Select *NotUsed){
  UNUSED_PARAMETER(NotUsed);
  pWalker->u.i = 0;
  return WRC_Abort;
}
static int exprIsConst(Expr *p, int initFlag){
  Walker w;
  memset(&w, 0, sizeof(w));
  w.u.i = initFlag;
  w.xExprCallback = exprNodeIsConstant;
  w.xSelectCallback = selectNodeIsConstant;
  sqlite3WalkExpr(&w, p);
  return w.u.i;
}

** obtained for queries regardless of whether or not constants are
** precomputed into registers or if they are inserted in-line.
*/
void sqlite3ExprCodeConstants(Parse *pParse, Expr *pExpr){
  Walker w;
  if( pParse->cookieGoto ) return;
  if( OptimizationDisabled(pParse->db, SQLITE_FactorOutConst) ) return;
  memset(&w, 0, sizeof(w));
  w.xExprCallback = evalConstExpr;

  w.pParse = pParse;
  sqlite3WalkExpr(&w, pExpr);
}


/*
** Generate code that pushes the value of every element of the given

      return 1;
    }
    pParse->nHeight += pExpr->nHeight;
  }
#endif
  savedHasAgg = pNC->ncFlags & NC_HasAgg;
  pNC->ncFlags &= ~NC_HasAgg;
  memset(&w, 0, sizeof(w));
  w.xExprCallback = resolveExprStep;
  w.xSelectCallback = resolveSelectStep;
  w.pParse = pNC->pParse;
  w.u.pNC = pNC;
  sqlite3WalkExpr(&w, pExpr);
#if SQLITE_MAX_EXPR_DEPTH>0
  pNC->pParse->nHeight -= pExpr->nHeight;

  Parse *pParse,         /* The parser context */
  Select *p,             /* The SELECT statement being coded. */
  NameContext *pOuterNC  /* Name context for parent SELECT statement */
){
  Walker w;

  assert( p!=0 );
  memset(&w, 0, sizeof(w));
  w.xExprCallback = resolveExprStep;
  w.xSelectCallback = resolveSelectStep;
  w.pParse = pParse;
  w.u.pNC = pOuterNC;
  sqlite3WalkSelect(&w, p);
}

**
** If anything goes wrong, an error message is written into pParse.
** The calling function can detect the problem by looking at pParse->nErr
** and/or pParse->db->mallocFailed.
*/
static void sqlite3SelectExpand(Parse *pParse, Select *pSelect){
  Walker w;
  memset(&w, 0, sizeof(w));
  w.xSelectCallback = selectExpander;
  w.xExprCallback = exprWalkNoop;
  w.pParse = pParse;
  sqlite3WalkSelect(&w, pSelect);
}

** SELECT statement.
**
** Use this routine after name resolution.
*/
static void sqlite3SelectAddTypeInfo(Parse *pParse, Select *pSelect){
#ifndef SQLITE_OMIT_SUBQUERY
  Walker w;
  memset(&w, 0, sizeof(w));
  w.xSelectCallback = selectAddSubqueryTypeInfo;
  w.xExprCallback = exprWalkNoop;
  w.pParse = pParse;
  w.bSelectDepthFirst = 1;
  sqlite3WalkSelect(&w, pSelect);
#endif
}


/*
** This routine sets up a SELECT statement for processing.  The

      int retAddr;
      assert( pItem->addrFillSub==0 );
      pItem->regReturn = ++pParse->nMem;
      topAddr = sqlite3VdbeAddOp2(v, OP_Integer, 0, pItem->regReturn);
      pItem->addrFillSub = topAddr+1;
      VdbeNoopComment((v, "materialize %s", pItem->pTab->zName));
      if( pItem->isCorrelated==0 ){
        /* If the subquery is not correlated and if we are not inside of
        ** a trigger, then we only need to compute the value of the subquery
        ** once. */
        onceAddr = sqlite3CodeOnce(pParse);
      }
      sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor);
      explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);
      sqlite3Select(pParse, pSub, &dest);

    if( db==0 || SQLITE_OK!=sqlite3_errcode(db) ){
      fprintf(stderr,"Error: unable to open database \"%s\": %s\n", 
          p->zDbFilename, sqlite3_errmsg(db));
      exit(1);
    }
#ifndef SQLITE_OMIT_LOAD_EXTENSION
    sqlite3_enable_load_extension(p->db, 1);












#endif
  }
}

/*
** Do C-language style dequoting.
**

** Context pointer passed down through the tree-walk.
*/
struct Walker {
  int (*xExprCallback)(Walker*, Expr*);     /* Callback for expressions */
  int (*xSelectCallback)(Walker*,Select*);  /* Callback for SELECTs */
  Parse *pParse;                            /* Parser context.  */
  int walkerDepth;                          /* Number of subqueries */
  u8 bSelectDepthFirst;                     /* Do subqueries first */
  union {                                   /* Extra data for callback */
    NameContext *pNC;                          /* Naming context */
    int i;                                     /* Integer value */
    SrcList *pSrcList;                         /* FROM clause */
    struct SrcCount *pSrcCount;                /* Counting column references */
  } u;
};

    extern int Sqlitetestintarray_Init(Tcl_Interp*);
    extern int Sqlitetestvfs_Init(Tcl_Interp *);
    extern int Sqlitetestrtree_Init(Tcl_Interp*);
    extern int Sqlitequota_Init(Tcl_Interp*);
    extern int Sqlitemultiplex_Init(Tcl_Interp*);
    extern int SqliteSuperlock_Init(Tcl_Interp*);
    extern int SqlitetestSyscall_Init(Tcl_Interp*);




#if defined(SQLITE_ENABLE_FTS3) || defined(SQLITE_ENABLE_FTS4)
    extern int Sqlitetestfts3_Init(Tcl_Interp *interp);
#endif

#ifdef SQLITE_ENABLE_ZIPVFS
    extern int Zipvfs_Init(Tcl_Interp*);

    Sqlitetestintarray_Init(interp);
    Sqlitetestvfs_Init(interp);
    Sqlitetestrtree_Init(interp);
    Sqlitequota_Init(interp);
    Sqlitemultiplex_Init(interp);
    SqliteSuperlock_Init(interp);
    SqlitetestSyscall_Init(interp);




#if defined(SQLITE_ENABLE_FTS3) || defined(SQLITE_ENABLE_FTS4)
    Sqlitetestfts3_Init(interp);
#endif

    Tcl_CreateObjCommand(
        interp, "load_testfixture_extensions", init_all_cmd, 0, 0

      Tcl_AppendResult(interp, " ", aOpt[i].zOptName);
    }
    return TCL_ERROR;
  }
  sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS, db, mask);
  return TCL_OK;
}

typedef struct sqlite3_api_routines sqlite3_api_routines;
/*
**     load_static_extension DB NAME ...
**
** Load one or more statically linked extensions.
*/
static int tclLoadStaticExtensionCmd(
  void * clientData,
  Tcl_Interp *interp,
  int objc,
  Tcl_Obj *CONST objv[]
){
  extern int sqlite3_amatch_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_closure_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_fuzzer_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_ieee_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_nextchar_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_regexp_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_spellfix_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_wholenumber_init(sqlite3*,char**,const sqlite3_api_routines*);
  static const struct {
    const char *zExtName;
    int (*pInit)(sqlite3*,char**,const sqlite3_api_routines*);
  } aExtension[] = {
    { "amatch",                sqlite3_amatch_init               },
    { "closure",               sqlite3_closure_init              },
    { "fuzzer",                sqlite3_fuzzer_init               },
    { "ieee754",               sqlite3_ieee_init                 },
    { "nextchar",              sqlite3_nextchar_init             },
    { "regexp",                sqlite3_regexp_init               },
    { "spellfix",              sqlite3_spellfix_init             },
    { "wholenumber",           sqlite3_wholenumber_init          },
  };
  sqlite3 *db;
  const char *zName;
  int i, j, rc;
  char *zErrMsg = 0;
  if( objc<3 ){
    Tcl_WrongNumArgs(interp, 1, objv, "DB NAME ...");
    return TCL_ERROR;
  }
  if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;
  for(j=2; j<objc; j++){
    zName = Tcl_GetString(objv[j]);
    for(i=0; i<ArraySize(aExtension); i++){
      if( strcmp(zName, aExtension[i].zExtName)==0 ) break;
    }
    if( i>=ArraySize(aExtension) ){
      Tcl_AppendResult(interp, "no such extension: ", zName, (char*)0);
      return TCL_ERROR;
    }
    rc = aExtension[i].pInit(db, &zErrMsg, 0);
    if( rc!=SQLITE_OK || zErrMsg ){
      Tcl_AppendResult(interp, "initialization of ", zName, " failed: ", zErrMsg,
                       (char*)0);
      sqlite3_free(zErrMsg);
      return TCL_ERROR;
    }
  }
  return TCL_OK;
}


/*
** Register commands with the TCL interpreter.
*/
int Sqlitetest1_Init(Tcl_Interp *interp){
  extern int sqlite3_search_count;
  extern int sqlite3_found_count;

#ifndef SQLITE_OMIT_EXPLAIN
     { "print_explain_query_plan", test_print_eqp, 0  },
#endif
     { "sqlite3_test_control", test_test_control },
#if SQLITE_OS_UNIX
     { "getrusage", test_getrusage },
#endif
     { "load_static_extension", tclLoadStaticExtensionCmd },
  };
  static int bitmask_size = sizeof(Bitmask)*8;
  int i;
  extern int sqlite3_sync_count, sqlite3_fullsync_count;
  extern int sqlite3_opentemp_count;
  extern int sqlite3_like_count;
  extern int sqlite3_xferopt_count;

  if( rc!=SQLITE_OK ){
    Tcl_SetResult(interp, (char *)sqlite3_errmsg(db), TCL_VOLATILE);
    return TCL_ERROR;
  }
  return TCL_OK;
}
























#endif /* ifndef SQLITE_OMIT_VIRTUALTABLE */

/*
** Register commands with the TCL interpreter.
*/
int Sqlitetest8_Init(Tcl_Interp *interp){
#ifndef SQLITE_OMIT_VIRTUALTABLE
  static struct {
     char *zName;
     Tcl_ObjCmdProc *xProc;
     void *clientData;
  } aObjCmd[] = {
     { "register_echo_module",       register_echo_module, 0 },

     { "sqlite3_declare_vtab",       declare_vtab, 0 },
  };
  int i;
  for(i=0; i<sizeof(aObjCmd)/sizeof(aObjCmd[0]); i++){
    Tcl_CreateObjCommand(interp, aObjCmd[i].zName, 
        aObjCmd[i].xProc, aObjCmd[i].clientData, 0);
  }

  }
  return WRC_Continue;
} 

/*
** Call sqlite3WalkExpr() for every expression in Select statement p.
** Invoke sqlite3WalkSelect() for subqueries in the FROM clause and
** on the compound select chain, p->pPrior.  Invoke the xSelectCallback()
** either before or after the walk of expressions and FROM clause, depending
** on whether pWalker->bSelectDepthFirst is false or true, respectively.
**
** Return WRC_Continue under normal conditions.  Return WRC_Abort if
** there is an abort request.
**
** If the Walker does not have an xSelectCallback() then this routine
** is a no-op returning WRC_Continue.
*/
int sqlite3WalkSelect(Walker *pWalker, Select *p){
  int rc;
  if( p==0 || pWalker->xSelectCallback==0 ) return WRC_Continue;
  rc = WRC_Continue;
  pWalker->walkerDepth++;
  while( p ){
    if( !pWalker->bSelectDepthFirst ){
       rc = pWalker->xSelectCallback(pWalker, p);
       if( rc ) break;
    }
    if( sqlite3WalkSelectExpr(pWalker, p)
     || sqlite3WalkSelectFrom(pWalker, p)
    ){
      pWalker->walkerDepth--;
      return WRC_Abort;
    }
    if( pWalker->bSelectDepthFirst ){
      rc = pWalker->xSelectCallback(pWalker, p);
      /* Depth-first search is currently only used for
      ** selectAddSubqueryTypeInfo() and that routine always returns
      ** WRC_Continue (0).  So the following branch is never taken. */
      if( NEVER(rc) ) break;
    }
    p = p->pPrior;
  }
  pWalker->walkerDepth--;
  return rc & WRC_Abort;
}

  finish_test
  return
}
db close
forcedelete test.db
do_test 8_3_names-5.0 {
  sqlite3 db file:./test.db?8_3_names=1
  load_static_extension db wholenumber
  db eval {
    PRAGMA journal_mode=WAL;
    CREATE TABLE t1(x);
    CREATE VIRTUAL TABLE nums USING wholenumber;
    INSERT INTO t1 SELECT value FROM nums WHERE value BETWEEN 1 AND 1000;
    BEGIN;
    UPDATE t1 SET x=x*2;
  }
  sqlite3 db2 file:./test.db?8_3_names=1
  load_static_extension db2 wholenumber
  db2 eval {
    BEGIN;
    SELECT sum(x) FROM t1;
  }
} {500500}

do_test 8_3_names-5.1 {

  finish_test
  return
}

# Generate some test data
#
do_test analyze7-1.0 {
  load_static_extension db wholenumber
  execsql {
    CREATE TABLE t1(a,b,c,d);
    CREATE INDEX t1a ON t1(a);
    CREATE INDEX t1b ON t1(b);
    CREATE INDEX t1cd ON t1(c,d);
    CREATE VIRTUAL TABLE nums USING wholenumber;
    INSERT INTO t1 SELECT value, value, value/100, value FROM nums

# 2013-04-25
#
# 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.
#
#***********************************************************************
# 
# Test cases for transitive_closure virtual table.

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix closure01

load_static_extension db closure

do_execsql_test 1.0 {
  BEGIN;
  CREATE TABLE t1(x INTEGER PRIMARY KEY, y INTEGER);
  CREATE INDEX t1y ON t1(y);
  INSERT INTO t1(x) VALUES(1),(2);
  INSERT INTO t1(x) SELECT x+2 FROM t1;
  INSERT INTO t1(x) SELECT x+4 FROM t1;
  INSERT INTO t1(x) SELECT x+8 FROM t1;
  INSERT INTO t1(x) SELECT x+16 FROM t1;
  INSERT INTO t1(x) SELECT x+32 FROM t1;
  INSERT INTO t1(x) SELECT x+64 FROM t1;
  INSERT INTO t1(x) SELECT x+128 FROM t1;
  INSERT INTO t1(x) SELECT x+256 FROM t1;
  INSERT INTO t1(x) SELECT x+512 FROM t1;
  INSERT INTO t1(x) SELECT x+1024 FROM t1;
  INSERT INTO t1(x) SELECT x+2048 FROM t1;
  INSERT INTO t1(x) SELECT x+4096 FROM t1;
  INSERT INTO t1(x) SELECT x+8192 FROM t1;
  INSERT INTO t1(x) SELECT x+16384 FROM t1;
  INSERT INTO t1(x) SELECT x+32768 FROM t1;
  INSERT INTO t1(x) SELECT x+65536 FROM t1;
  UPDATE t1 SET y=x/2 WHERE x>1;
  COMMIT;
  CREATE VIRTUAL TABLE cx 
   USING transitive_closure(tablename=t1, idcolumn=x, parentcolumn=y);
} {}

# The entire table
do_execsql_test 1.1 {
  SELECT count(*), depth FROM cx WHERE root=1 GROUP BY depth ORDER BY 1;
} {/1 0 1 17 2 1 4 2 8 3 16 4 .* 65536 16/}

# descendents of 32768
do_execsql_test 1.2 {
  SELECT * FROM cx WHERE root=32768 ORDER BY id;
} {32768 0 65536 1 65537 1 131072 2}

# descendents of 16384
do_execsql_test 1.3 {
  SELECT * FROM cx WHERE root=16384 AND depth<=2 ORDER BY id;
} {16384 0 32768 1 32769 1 65536 2 65537 2 65538 2 65539 2}

# children of 16384
do_execsql_test 1.4 {
  SELECT id, depth, root, tablename, idcolumn, parentcolumn FROM cx
   WHERE root=16384
     AND depth=1
   ORDER BY id;
} {32768 1 {} t1 x y 32769 1 {} t1 x y}

# great-grandparent of 16384
do_execsql_test 1.5 {
  SELECT id, depth, root, tablename, idcolumn, parentcolumn FROM cx
   WHERE root=16384
     AND depth=3
     AND idcolumn='Y'
     AND parentcolumn='X';
} {2048 3 {} t1 Y X}

# depth<5
do_execsql_test 1.6 {
  SELECT count(*), depth FROM cx WHERE root=1 AND depth<5
   GROUP BY depth ORDER BY 1;
} {1 0 2 1 4 2 8 3 16 4}

# depth<=5
do_execsql_test 1.7 {
  SELECT count(*), depth FROM cx WHERE root=1 AND depth<=5
   GROUP BY depth ORDER BY 1;
} {1 0 2 1 4 2 8 3 16 4 32 5}

# depth==5
do_execsql_test 1.8 {
  SELECT count(*), depth FROM cx WHERE root=1 AND depth=5
   GROUP BY depth ORDER BY 1;
} {32 5}

# depth BETWEEN 3 AND 5
do_execsql_test 1.9 {
  SELECT count(*), depth FROM cx WHERE root=1 AND depth BETWEEN 3 AND 5
   GROUP BY depth ORDER BY 1;
} {8 3 16 4 32 5}

# depth==5 with min() and max()
do_execsql_test 1.10 {
  SELECT count(*), min(id), max(id) FROM cx WHERE root=1 AND depth=5;
} {32 32 63}

# Create a much smaller table t2 with only 32 elements 
db eval {
  CREATE TABLE t2(x INTEGER PRIMARY KEY, y INTEGER);
  INSERT INTO t2 SELECT x, y FROM t1 WHERE x<32;
  CREATE INDEX t2y ON t2(y);
  CREATE VIRTUAL TABLE c2 
   USING transitive_closure(tablename=t2, idcolumn=x, parentcolumn=y);
}

# t2 full-table
do_execsql_test 2.1 {
  SELECT count(*), min(id), max(id) FROM c2 WHERE root=1;
} {31 1 31}
# t2 root=10
do_execsql_test 2.2 {
  SELECT id FROM c2 WHERE root=10;
} {10 20 21}
# t2 root=11
do_execsql_test 2.3 {
  SELECT id FROM c2 WHERE root=12;
} {12 24 25}
# t2 root IN [10,12]
do_execsql_test 2.4 {
  SELECT id FROM c2 WHERE root IN (10,12) ORDER BY id;
} {10 12 20 21 24 25}
# t2 root IN [10,12] (sorted)
do_execsql_test 2.5 {
  SELECT id FROM c2 WHERE root IN (10,12) ORDER BY +id;
} {10 12 20 21 24 25}

# t2 c2up from 20
do_execsql_test 3.0 {
  CREATE VIRTUAL TABLE c2up USING transitive_closure(
    tablename = t2,
    idcolumn = y,
    parentcolumn = x
  );
  SELECT id FROM c2up WHERE root=20;
} {1 2 5 10 20}

# cx as c2up
do_execsql_test 3.1 {
  SELECT id FROM cx
   WHERE root=20
     AND tablename='t2'
     AND idcolumn='y'
     AND parentcolumn='x';
} {1 2 5 10 20}

# t2 first cousins of 20
do_execsql_test 3.2 {
  SELECT DISTINCT id FROM c2
   WHERE root IN (SELECT id FROM c2up
                   WHERE root=20 AND depth<=2)
   ORDER BY id;
} {5 10 11 20 21 22 23}

# t2 first cousins of 20
do_execsql_test 3.3 {
  SELECT id FROM c2
   WHERE root=(SELECT id FROM c2up
               WHERE root=20 AND depth=2)
     AND depth=2
  EXCEPT
  SELECT id FROM c2
   WHERE root=(SELECT id FROM c2up
               WHERE root=20 AND depth=1)
     AND depth<=1
   ORDER BY id;
} {22 23}

# missing tablename.
do_test 4.1 {
  catchsql {
    SELECT id FROM cx
     WHERE root=20
       AND tablename='t3'
       AND idcolumn='y'
       AND parentcolumn='x';
  }
} {1 {no such table: t3}}

# missing idcolumn
do_test 4.2 {
  catchsql {
    SELECT id FROM cx
     WHERE root=20
       AND tablename='t2'
       AND idcolumn='xyz'
       AND parentcolumn='x';
  }
} {1 {no such column: t2.xyz}}

# missing parentcolumn
do_test 4.3 {
  catchsql {
    SELECT id FROM cx
     WHERE root=20
       AND tablename='t2'
       AND idcolumn='x'
       AND parentcolumn='pqr';
  }
} {1 {no such column: t2.pqr}}

# generic closure
do_execsql_test 5.1 {
  CREATE VIRTUAL TABLE temp.closure USING transitive_closure;
  SELECT id FROM closure
   WHERE root=1
     AND depth=3
     AND tablename='t1'
     AND idcolumn='x'
     AND parentcolumn='y'
  ORDER BY id;
} {8 9 10 11 12 13 14 15}

finish_test

ifcapable !vtab {
  finish_test
  return
}

set ::testprefix fuzzer1





load_static_extension db fuzzer


# Check configuration errors.
#
do_catchsql_test fuzzer1-1.1 {
  CREATE VIRTUAL TABLE f USING fuzzer;
} {1 {fuzzer: wrong number of CREATE VIRTUAL TABLE arguments}}

#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
ifcapable !vtab { finish_test ; return }
set ::testprefix fuzzerfault

load_static_extension db fuzzer

do_test 1-pre1 {
  execsql {
    CREATE TABLE x1_rules(ruleset, cFrom, cTo, cost);
    INSERT INTO x1_rules VALUES(0, 'a', 'b', 1);
    INSERT INTO x1_rules VALUES(0, 'a', 'c', 2);
    INSERT INTO x1_rules VALUES(0, 'a', 'd', 3);

    DELETE FROM t5 WHERE x>0;
    SELECT * FROM t5;
  }
} {}

ifcapable subquery&&vtab {
  do_test memdb-7.1 {
    load_static_extension db wholenumber
    execsql {
      CREATE TABLE t6(x);
      CREATE VIRTUAL TABLE nums USING wholenumber;
      INSERT INTO t6 SELECT value FROM nums WHERE value BETWEEN 1 AND 256;
      SELECT count(*) FROM (SELECT DISTINCT x FROM t6);
    }
  } {256}

# This file implements test for the REGEXP operator in test_regexp.c.
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl

do_test regexp1-1.1 {
  load_static_extension db regexp
  db eval {
    CREATE TABLE t1(x INTEGER PRIMARY KEY, y TEXT);
    INSERT INTO t1 VALUES(1, 'For since by man came death,');
    INSERT INTO t1 VALUES(2, 'by man came also the resurrection of the dead.');
    INSERT INTO t1 VALUES(3, 'For as in Adam all die,');
    INSERT INTO t1 VALUES(4, 'even so in Christ shall all be made alive.');

    db eval {
      SELECT t1.*, t2.*, t3.*, t4.b
        FROM (t1 LEFT JOIN t2 USING(a)) JOIN (t3 LEFT JOIN t4 USING(a))
             ON t1.a=t3.a-111;
    }
  } {111 x1 111 x2 222 x3 {}}
}

# The following test was added on 2013-04-24 in order to verify that
# the datatypes and affinities of sub-sub-queries are set prior to computing
# the datatypes and affinities of the parent sub-queries because the 
# latter computation depends on the former.
#
do_execsql_test selectD-4.1 {
  CREATE TABLE t41(a INTEGER PRIMARY KEY, b INTEGER);
  CREATE TABLE t42(d INTEGER PRIMARY KEY, e INTEGER);
  CREATE TABLE t43(f INTEGER PRIMARY KEY, g INTEGER);
  EXPLAIN QUERY PLAN
  SELECT * 
   FROM t41
   LEFT JOIN (SELECT count(*) AS cnt, x1.d
                FROM (t42 INNER JOIN t43 ON d=g) AS x1
               WHERE x1.d>5
               GROUP BY x1.d) AS x2
                  ON t41.b=x2.d;
} {/.*SEARCH SUBQUERY 1 AS x2 USING AUTOMATIC.*/}

finish_test

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix spellfix

ifcapable !vtab { finish_test ; return }

load_static_extension db spellfix nextchar

set vocab {
rabbi rabbit rabbits rabble rabid rabies raccoon raccoons race raced racer
racers races racetrack racial racially racing rack racked racket racketeer
racketeering racketeers rackets racking racks radar radars radial radially
radian radiance radiant radiantly radiate radiated radiates radiating radiation
radiations radiator radiators radical radically radicals radices radii radio

} {
  do_execsql_test 1.2.$tn {
    SELECT word, matchlen FROM t1 WHERE word MATCH $word 
     ORDER BY score, word LIMIT 5
  } $res
}

# Tests of the next_char function.
#
do_test 1.10 {
  db eval {
    CREATE TABLE vocab(w TEXT PRIMARY KEY);
    INSERT INTO vocab SELECT word FROM t1;
  }
} {}
do_execsql_test 1.11 {
  SELECT next_char('re','vocab','w');
} {a}
do_execsql_test 1.12 {
  SELECT next_char('r','vocab','w');
} {ae}
do_execsql_test 1.13 {
  SELECT next_char('','vocab','w');
} {r}
do_test 1.14 {
  catchsql {SELECT next_char('','xyzzy','a')}
} {1 {no such table: xyzzy}}

do_execsql_test 2.1 {
  CREATE VIRTUAL TABLE t2 USING spellfix1;
  INSERT INTO t2 (word, soundslike) VALUES('school', 'skuul');
  INSERT INTO t2 (word, soundslike) VALUES('psalm', 'sarm');
  SELECT word, matchlen FROM t2 WHERE word MATCH 'sar*' LIMIT 5;
} {psalm 4}

    }
  } {wal A 3 4 B 1 2 C 1 2}
}

db close
forcedelete test.db test.db-wal
sqlite3 db test.db
load_static_extension db wholenumber
db eval {
  PRAGMA journal_mode=WAL;
  CREATE TABLE t1(a,b);
  CREATE INDEX t1b ON t1(b);
  CREATE TABLE t2(x,y);
  CREATE VIRTUAL TABLE nums USING wholenumber;
  INSERT INTO t2 SELECT value, randomblob(1000) FROM nums

  set ::max_journal_size 0
  proc xDeleteCallback {method file args} {
    set sz [file size $file]
    if {$sz>$::max_journal_size} {set ::max_journal_size $sz}
  }
  tv filter xDelete
  tv script xDeleteCallback
  load_static_extension db wholenumber
  db eval {
    PRAGMA page_size=1024;
    PRAGMA journal_mode=DELETE;
    PRAGMA cache_size=5;
    CREATE VIRTUAL TABLE nums USING wholenumber;
    CREATE TABLE t1(x, y);
    INSERT INTO t1 SELECT value, randomblob(100) FROM nums

make sqlite3.c
gcc -o sqlite3 -g -Os -I. \
   -DSQLITE_THREADSAFE=0 \
   -DSQLITE_ENABLE_VFSTRACE \
   -DSQLITE_ENABLE_STAT3 \
   -DSQLITE_ENABLE_FTS4 \
   -DSQLITE_ENABLE_RTREE \


   -DHAVE_READLINE \
   -DHAVE_USLEEP=1 \
   ../sqlite/src/shell.c \


   ../sqlite/src/test_vfstrace.c \
   sqlite3.c -ldl -lreadline -lncurses