SQLite

  rc = sqlite3_declare_vtab(db, Tcl_GetString(objv[2]));
  if( rc!=SQLITE_OK ){
    Tcl_SetResult(interp, (char *)sqlite3_errmsg(db), TCL_VOLATILE);
    return TCL_ERROR;
  }
  return TCL_OK;
}

#include "test_spellfix.c"

/*
** Register the spellfix virtual table module.
*/
static int register_spellfix_module(
  ClientData clientData,
  Tcl_Interp *interp,
  int objc,
  Tcl_Obj *CONST objv[]
){
  static sqlite3_module aMod[3];
  int iMod;
  sqlite3 *db;

  if( objc!=2 ){
    Tcl_WrongNumArgs(interp, 1, objv, "DB");
    return TCL_ERROR;
  }
  if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;

  sqlite3Spellfix1Register(db);
  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 },
     { "register_spellfix_module",   register_spellfix_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);
  }
#endif

**                  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)
**
** 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

** 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:
**
**    key = spellfix1_phonehash(lower(spellfix1_translit(X)))
**
** 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.
**

#else
# include <string.h>
# include <stdio.h>
# include <stdlib.h>
# include "sqlite3ext.h"
  SQLITE_EXTENSION_INIT1
#endif /* !SQLITE_CORE */
#include <ctype.h>

/*
** 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
**   3   'C'       Other fricatives or back stops:  C G J K Q S X Z
**   4   'D'       Alveolar stops:  D T
**   5   'H'       Letter H at the beginning of a word
**   6   'L'       Glide:  L
**   7   'R'       Semivowel:  R
**   8   'M'       Nasals:  M N
**   9   'W'       Letter W at the beginning of a word
**   10  'Y'       Letter Y at the beginning of a word.
**   11  '9'       A digit: 0 1 2 3 4 5 6 7 8 9
**   12  ' '       White space
**   13  '?'       Other.
*/
#define CCLASS_SILENT         0
#define CCLASS_VOWEL          1
#define CCLASS_B              2
#define CCLASS_C              3
#define CCLASS_D              4
#define CCLASS_H              5
#define CCLASS_L              6
#define CCLASS_R              7
#define CCLASS_M              8
#define CCLASS_W              9
#define CCLASS_Y             10
#define CCLASS_DIGIT         11
#define CCLASS_SPACE         12
#define CCLASS_OTHER         13

/*
** The following table gives the character class for non-initial ASCII
** characters.
*/
static const unsigned char midClass[] = {

 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_SPACE,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_SPACE,    /*   */ CCLASS_SPACE,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_SPACE,
 /* ! */ CCLASS_OTHER,    /* " */ CCLASS_OTHER,   /* # */ CCLASS_OTHER,
 /* $ */ CCLASS_OTHER,    /* % */ CCLASS_OTHER,   /* & */ CCLASS_OTHER,
 /* ' */ CCLASS_SILENT,   /* ( */ CCLASS_OTHER,   /* ) */ CCLASS_OTHER,
 /* * */ CCLASS_OTHER,    /* + */ CCLASS_OTHER,   /* , */ CCLASS_OTHER,
 /* - */ CCLASS_OTHER,    /* . */ CCLASS_OTHER,   /* / */ CCLASS_OTHER,
 /* 0 */ CCLASS_DIGIT,    /* 1 */ CCLASS_DIGIT,   /* 2 */ CCLASS_DIGIT,
 /* 3 */ CCLASS_DIGIT,    /* 4 */ CCLASS_DIGIT,   /* 5 */ CCLASS_DIGIT,
 /* 6 */ CCLASS_DIGIT,    /* 7 */ CCLASS_DIGIT,   /* 8 */ CCLASS_DIGIT,
 /* 9 */ CCLASS_DIGIT,    /* : */ CCLASS_OTHER,   /* ; */ CCLASS_OTHER,
 /* < */ CCLASS_OTHER,    /* = */ CCLASS_OTHER,   /* > */ CCLASS_OTHER,
 /* ? */ CCLASS_OTHER,    /* @ */ CCLASS_OTHER,   /* A */ CCLASS_VOWEL,
 /* B */ CCLASS_B,        /* C */ CCLASS_C,       /* D */ CCLASS_D,
 /* E */ CCLASS_VOWEL,    /* F */ CCLASS_B,       /* G */ CCLASS_C,
 /* H */ CCLASS_SILENT,   /* I */ CCLASS_VOWEL,   /* J */ CCLASS_C,
 /* K */ CCLASS_C,        /* L */ CCLASS_L,       /* M */ CCLASS_M,
 /* N */ CCLASS_M,        /* O */ CCLASS_VOWEL,   /* P */ CCLASS_B,
 /* Q */ CCLASS_C,        /* R */ CCLASS_R,       /* S */ CCLASS_C,
 /* T */ CCLASS_D,        /* U */ CCLASS_VOWEL,   /* V */ CCLASS_B,
 /* W */ CCLASS_SILENT,   /* X */ CCLASS_C,       /* Y */ CCLASS_VOWEL,
 /* Z */ CCLASS_C,        /* [ */ CCLASS_OTHER,   /* \ */ CCLASS_OTHER,
 /* ] */ CCLASS_OTHER,    /* ^ */ CCLASS_OTHER,   /* _ */ CCLASS_OTHER,
 /* ` */ CCLASS_OTHER,    /* a */ CCLASS_VOWEL,   /* b */ CCLASS_B,
 /* c */ CCLASS_C,        /* d */ CCLASS_D,       /* e */ CCLASS_VOWEL,
 /* f */ CCLASS_B,        /* g */ CCLASS_C,       /* h */ CCLASS_SILENT,
 /* i */ CCLASS_VOWEL,    /* j */ CCLASS_C,       /* k */ CCLASS_C,
 /* l */ CCLASS_L,        /* m */ CCLASS_M,       /* n */ CCLASS_M,
 /* o */ CCLASS_VOWEL,    /* p */ CCLASS_B,       /* q */ CCLASS_C,
 /* r */ CCLASS_R,        /* s */ CCLASS_C,       /* t */ CCLASS_D,
 /* u */ CCLASS_VOWEL,    /* v */ CCLASS_B,       /* w */ CCLASS_SILENT,
 /* x */ CCLASS_C,        /* y */ CCLASS_VOWEL,   /* z */ CCLASS_C,
 /* { */ CCLASS_OTHER,    /* | */ CCLASS_OTHER,   /* } */ CCLASS_OTHER,
 /* ~ */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   
};

/* 
** This tables gives the character class for ASCII characters that form the
** initial character of a word.  The only difference from midClass is with
** the letters H, W, and Y.
*/
static const unsigned char initClass[] = {
 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_SPACE,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_SPACE,    /*   */ CCLASS_SPACE,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_OTHER,
 /*   */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   /*   */ CCLASS_SPACE,
 /* ! */ CCLASS_OTHER,    /* " */ CCLASS_OTHER,   /* # */ CCLASS_OTHER,
 /* $ */ CCLASS_OTHER,    /* % */ CCLASS_OTHER,   /* & */ CCLASS_OTHER,
 /* ' */ CCLASS_OTHER,    /* ( */ CCLASS_OTHER,   /* ) */ CCLASS_OTHER,
 /* * */ CCLASS_OTHER,    /* + */ CCLASS_OTHER,   /* , */ CCLASS_OTHER,
 /* - */ CCLASS_OTHER,    /* . */ CCLASS_OTHER,   /* / */ CCLASS_OTHER,
 /* 0 */ CCLASS_DIGIT,    /* 1 */ CCLASS_DIGIT,   /* 2 */ CCLASS_DIGIT,
 /* 3 */ CCLASS_DIGIT,    /* 4 */ CCLASS_DIGIT,   /* 5 */ CCLASS_DIGIT,
 /* 6 */ CCLASS_DIGIT,    /* 7 */ CCLASS_DIGIT,   /* 8 */ CCLASS_DIGIT,
 /* 9 */ CCLASS_DIGIT,    /* : */ CCLASS_OTHER,   /* ; */ CCLASS_OTHER,
 /* < */ CCLASS_OTHER,    /* = */ CCLASS_OTHER,   /* > */ CCLASS_OTHER,
 /* ? */ CCLASS_OTHER,    /* @ */ CCLASS_OTHER,   /* A */ CCLASS_VOWEL,
 /* B */ CCLASS_B,        /* C */ CCLASS_C,       /* D */ CCLASS_D,
 /* E */ CCLASS_VOWEL,    /* F */ CCLASS_B,       /* G */ CCLASS_C,
 /* H */ CCLASS_SILENT,   /* I */ CCLASS_VOWEL,   /* J */ CCLASS_C,
 /* K */ CCLASS_C,        /* L */ CCLASS_L,       /* M */ CCLASS_M,
 /* N */ CCLASS_M,        /* O */ CCLASS_VOWEL,   /* P */ CCLASS_B,
 /* Q */ CCLASS_C,        /* R */ CCLASS_R,       /* S */ CCLASS_C,
 /* T */ CCLASS_D,        /* U */ CCLASS_VOWEL,   /* V */ CCLASS_B,
 /* W */ CCLASS_W,        /* X */ CCLASS_C,       /* Y */ CCLASS_Y,
 /* Z */ CCLASS_C,        /* [ */ CCLASS_OTHER,   /* \ */ CCLASS_OTHER,
 /* ] */ CCLASS_OTHER,    /* ^ */ CCLASS_OTHER,   /* _ */ CCLASS_OTHER,
 /* ` */ CCLASS_OTHER,    /* a */ CCLASS_VOWEL,   /* b */ CCLASS_B,
 /* c */ CCLASS_C,        /* d */ CCLASS_D,       /* e */ CCLASS_VOWEL,
 /* f */ CCLASS_B,        /* g */ CCLASS_C,       /* h */ CCLASS_SILENT,
 /* i */ CCLASS_VOWEL,    /* j */ CCLASS_C,       /* k */ CCLASS_C,
 /* l */ CCLASS_L,        /* m */ CCLASS_M,       /* n */ CCLASS_M,
 /* o */ CCLASS_VOWEL,    /* p */ CCLASS_B,       /* q */ CCLASS_C,
 /* r */ CCLASS_R,        /* s */ CCLASS_C,       /* t */ CCLASS_D,
 /* u */ CCLASS_VOWEL,    /* v */ CCLASS_B,       /* w */ CCLASS_W,
 /* x */ CCLASS_C,        /* y */ CCLASS_Y,       /* z */ CCLASS_C,
 /* { */ CCLASS_OTHER,    /* | */ CCLASS_OTHER,   /* } */ CCLASS_OTHER,
 /* ~ */ CCLASS_OTHER,    /*   */ CCLASS_OTHER,   
};

/*
** Mapping from the character class number (0-13) to a symbol for each
** character class.  Note that initClass[] can be used to map the class
** symbol back into the class number.
*/
static const unsigned char className[] = ".ABCDHLRMWY9 ?";

/*
** Generate a "phonetic hash" from a string of ASCII characters
** in zIn[0..nIn-1].
**
**   * Map characters by character class as defined above.
**   * Omit double-letters
**   * Omit vowels beside R and L
**   * Omit T when followed by CH
**   * Omit W when followed by R
**   * Omit D when followed by J or G
**   * Omit K in KN or G in GN at the beginning of a word
**
** Space to hold the result is obtained from sqlite3_malloc()
**
** Return NULL if memory allocation fails.  
*/
static unsigned char *phoneticHash(const unsigned char *zIn, int nIn){
  unsigned char *zOut = sqlite3_malloc( nIn + 1 );
  int i;
  int nOut = 0;
  char cPrev = 0x77;
  char cPrevX = 0x77;
  const unsigned char *aClass = initClass;

  if( zOut==0 ) return 0;
  if( nIn>2 ){
    switch( zIn[0] ){
      case 'g': 
      case 'k': {
        if( zIn[1]=='n' ){ zIn++; nIn--; }
        break;
      }
    }
  }
  if( zIn[0]=='k' && zIn[1]=='n' ){ zIn++, nIn--; }
  for(i=0; i<nIn; i++){
    unsigned char c = zIn[i];
    if( i+1<nIn ){
      if( c=='w' && zIn[i+1]=='r' ) continue;
      if( c=='d' && (zIn[i+1]=='j' || zIn[i+1]=='g') ) continue;
      if( i+2<nIn ){
        if( c=='t' && zIn[i+1]=='c' && zIn[i+2]=='h' ) continue;
      }
    }
    c = aClass[c&0x7f];
    if( c==CCLASS_SPACE ) continue;
    if( c==CCLASS_OTHER && cPrev!=CCLASS_DIGIT ) continue;
    if( c==CCLASS_VOWEL && (cPrevX==CCLASS_R || cPrevX==CCLASS_L) ){
       continue; /* No vowels beside L or R */ 
    }
    if( (c==CCLASS_R || c==CCLASS_L) && cPrevX==CCLASS_VOWEL ){
       nOut--;   /* No vowels beside L or R */
    }
    cPrev = c;
    if( c==CCLASS_SILENT ) continue;
    cPrevX = c;
    if( c==CCLASS_SPACE ) continue;
    aClass = midClass;
    c = className[c];
    if( c!=zOut[nOut-1] ) zOut[nOut++] = c;
  }
  zOut[nOut] = 0;
  return zOut;
}

/*
** This is an SQL function wrapper around phoneticHash().  See
** the description of phoneticHash() for additional information.
*/
static void phoneticHashSqlFunc(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  const unsigned char *zIn;
  unsigned char *zOut;

  zIn = sqlite3_value_text(argv[0]);
  if( zIn==0 ) return;
  zOut = phoneticHash(zIn, sqlite3_value_bytes(argv[0]));
  if( zOut==0 ){
    sqlite3_result_error_nomem(context);
  }else{
    sqlite3_result_text(context, (char*)zOut, -1, sqlite3_free);
  }
}

/*
** Return the character class number for a character given its
** context.
*/
static char characterClass(char cPrev, char c){
  return cPrev==0 ? initClass[c&0x7f] : midClass[c&0x7f];
}

/*
** Return the cost of inserting or deleting character c immediately
** following character cPrev.  If cPrev==0, that means c is the first
** character of the word.
*/
static int insertOrDeleteCost(char cPrev, char c, char cNext){
  char classC = characterClass(cPrev, c);
  char classCprev;

  if( classC==CCLASS_SILENT ){
    /* Insert or delete "silent" characters such as H or W */
    return 1;
  }
  if( cPrev==c ){
    /* Repeated characters, or miss a repeat */
    return 10;
  }
  if( classC==CCLASS_VOWEL && (cPrev=='r' || cNext=='r') ){
    return 20;  /* Insert a vowel before or after 'r' */
  }
  classCprev = characterClass(cPrev, cPrev);
  if( classC==classCprev ){
    if( classC==CCLASS_VOWEL ){
      /* Remove or add a new vowel to a vowel cluster */
      return 15;
    }else{

** Smaller numbers mean a closer match.
**
** Negative values indicate an error:
**    -1  One of the inputs is NULL
**    -2  Non-ASCII characters on input
**    -3  Unable to allocate memory 
*/
static int editdist1(const char *zA, const char *zB, int iLangId){
  int nA, nB;            /* Number of characters in zA[] and zB[] */
  int xA, xB;            /* Loop counters for zA[] and zB[] */
  char cA, cB;           /* Current character of zA and zB */
  char cAprev, cBprev;   /* Previous character of zA and zB */
  char cAnext, cBnext;   /* Next character in zA and zB */
  int d;                 /* North-west cost value */
  int dc = 0;            /* North-west character value */
  int res;               /* Final result */
  int *m;                /* The cost matrix */
  char *cx;              /* Corresponding character values */
  int *toFree = 0;       /* Malloced space */
  int mStack[60+15];     /* Stack space to use if not too much is needed */

    if( zB[nB]>127 ) return -2;
  }

  /* Special processing if either string is empty */
  if( nA==0 ){
    cBprev = dc;
    for(xB=res=0; (cB = zB[xB])!=0; xB++){
      res += insertOrDeleteCost(cBprev, cB, zB[xB+1])/FINAL_INS_COST_DIV;
      cBprev = cB;
    }
    return res;
  }
  if( nB==0 ){
    cAprev = dc;
    for(xA=res=0; (cA = zA[xA])!=0; xA++){
      res += insertOrDeleteCost(cAprev, cA, zA[xA+1]);
      cAprev = cA;
    }
    return res;
  }

  /* A is a prefix of B */
  if( zA[0]=='*' && zA[1]==0 ) return 0;

  cx = (char*)&m[nB+1];

  /* Compute the Wagner edit distance */
  m[0] = 0;
  cx[0] = dc;
  cBprev = dc;
  for(xB=1; xB<=nB; xB++){
    cBnext = zB[xB];
    cB = zB[xB-1];
    cx[xB] = cB;
    m[xB] = m[xB-1] + insertOrDeleteCost(cBprev, cB, cBnext);
    cBprev = cB;
  }
  cAprev = dc;
  for(xA=1; xA<=nA; xA++){
    int lastA = (xA==nA);
    cA = zA[xA-1];
    cAnext = zA[xA];
    if( cA=='*' && lastA ) break;
    d = m[0];
    dc = cx[0];
    m[0] = d + insertOrDeleteCost(cAprev, cA, cAnext);
    cBprev = 0;
    for(xB=1; xB<=nB; xB++){
      int totalCost, insCost, delCost, subCost, ncx;
      cB = zB[xB-1];
      cBnext = zB[xB];

      /* Cost to insert cB */
      insCost = insertOrDeleteCost(cx[xB-1], cB, cBnext);
      if( lastA ) insCost /= FINAL_INS_COST_DIV;

      /* Cost to delete cA */
      delCost = insertOrDeleteCost(cx[xB], cA, cBnext);

      /* Cost to substitute cA->cB */
      subCost = substituteCost(cx[xB-1], cA, cB);

      /* Best cost */
      totalCost = insCost + m[xB-1];
      ncx = cB;

      cx[xB] = ncx;
      cBprev = cB;
    }
    cAprev = cA;
  }

  /* Free the wagner matrix and return the result */
  if( cA=='*' ){
    res = m[1];
    for(xB=1; xB<=nB; xB++){
      if( m[xB]<res ) res = m[xB];
    }
  }else{
    res = m[nB];
  }
  sqlite3_free(toFree);
  return res;
}

/*
** Function:    editdist(A,B)
**              editdist(A,B,langid)
**
** Return the cost of transforming string A into string B.  Both strings
** must be pure ASCII text.  If A ends with '*' then it is assumed to be
** a prefix of B and extra characters on the end of B have minimal additional
** cost.
*/
static void editdistSqlFunc(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  int langid = argc==2 ? 0 : sqlite3_value_int(argv[2]);
  int res = editdist1(
                    (const char*)sqlite3_value_text(argv[0]),
                    (const char*)sqlite3_value_text(argv[1]),
                    langid);
  if( res<0 ){
    if( res==(-3) ){
      sqlite3_result_error_nomem(context);
    }else if( res==(-2) ){
      sqlite3_result_error(context, "non-ASCII input to editdist()", -1);
    }else{
      sqlite3_result_error(context, "NULL input to editdist()", -1);
    }
  }else{ 
    sqlite3_result_int(context, res);
  }
}

/* End of the fixed-cost edit distance implementation
******************************************************************************
*****************************************************************************
** Begin: Configurable cost unicode edit distance routines
*/
/* Forward declaration of structures */
typedef struct EditDist3Cost EditDist3Cost;
typedef struct EditDist3Config EditDist3Config;
typedef struct EditDist3Point EditDist3Point;
typedef struct EditDist3From EditDist3From;
typedef struct EditDist3FromString EditDist3FromString;
typedef struct EditDist3To EditDist3To;
typedef struct EditDist3ToString EditDist3ToString;
typedef struct EditDist3Lang EditDist3Lang;


/*
** An entry in the edit cost table
*/
struct EditDist3Cost {
  EditDist3Cost *pNext;     /* Next cost element */
  u8 nFrom;                 /* Number of bytes in aFrom */
  u8 nTo;                   /* Number of bytes in aTo */
  u16 iCost;                /* Cost of this transformation */
  char a[4]    ;            /* FROM string followed by TO string */
  /* Additional TO and FROM string bytes appended as necessary */
};

/*
** Edit costs for a particular language ID 
*/
struct EditDist3Lang {
  int iLang;             /* Language ID */
  int iInsCost;          /* Default insertion cost */
  int iDelCost;          /* Default deletion cost */
  int iSubCost;          /* Default substitution cost */
  EditDist3Cost *pCost;  /* Costs */
};


/*
** The default EditDist3Lang object, with default costs.
*/
static const EditDist3Lang editDist3Lang = { 0, 100, 100, 150, 0 };

/*
** Complete configuration
*/
struct EditDist3Config {
  int nLang;             /* Number of language IDs.  Size of a[] */
  EditDist3Lang *a;      /* One for each distinct language ID */
};

/*
** Extra information about each character in the FROM string.
*/
struct EditDist3From {
  int nSubst;              /* Number of substitution cost entries */
  int nDel;                /* Number of deletion cost entries */
  int nByte;               /* Number of bytes in this character */
  EditDist3Cost **apSubst; /* Array of substitution costs for this element */
  EditDist3Cost **apDel;   /* Array of deletion cost entries */
};

/*
** A precompiled FROM string.
*
** In the common case we expect the FROM string to be reused multiple times.
** In other words, the common case will be to measure the edit distance
** from a single origin string to multiple target strings.
*/
struct EditDist3FromString {
  char *z;                 /* The complete text of the FROM string */
  int n;                   /* Number of characters in the FROM string */
  int isPrefix;            /* True if ends with '*' character */
  EditDist3From *a;        /* Extra info about each char of the FROM string */
};

/*
** Extra information about each character in the TO string.
*/
struct EditDist3To {
  int nIns;                /* Number of insertion cost entries */
  int nByte;               /* Number of bytes in this character */
  EditDist3Cost **apIns;   /* Array of deletion cost entries */
};

/*
** A precompiled FROM string
*/
struct EditDist3ToString {
  char *z;                 /* The complete text of the TO string */
  int n;                   /* Number of characters in the TO string */
  EditDist3To *a;          /* Extra info about each char of the TO string */
};

/*
** Clear or delete an instance of the object that records all edit-distance
** weights.
*/
static void editDist3ConfigClear(EditDist3Config *p){
  int i;
  if( p==0 ) return;
  for(i=0; i<p->nLang; i++){
    EditDist3Cost *pCost, *pNext;
    pCost = p->a[i].pCost;
    while( pCost ){
      pNext = pCost->pNext;
      sqlite3_free(pCost);
      pCost = pNext;
    }
  }
  sqlite3_free(p->a);
  memset(p, 0, sizeof(*p));
}
static void editDist3ConfigDelete(void *pIn){
  EditDist3Config *p = (EditDist3Config*)pIn;
  editDist3ConfigClear(p);
  sqlite3_free(p);
}

/*
** Load all edit-distance weights from a table.
*/
static int editDist3ConfigLoad(
  EditDist3Config *p,      /* The edit distance configuration to load */
  sqlite3 *db,            /* Load from this database */
  const char *zTable      /* Name of the table from which to load */
){
  sqlite3_stmt *pStmt;
  int rc;
  char *zSql;
  int iLangPrev = -9999;
  EditDist3Lang *pLang;

  zSql = sqlite3_mprintf("SELECT iLang, cFrom, cTo, iCost"
                         " FROM \"%w\" WHERE iLang>=0 ORDER BY iLang", zTable);
  if( zSql==0 ) return SQLITE_NOMEM;
  rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
  sqlite3_free(zSql);
  if( rc ) return rc;
  editDist3ConfigClear(p);
  while( sqlite3_step(pStmt)==SQLITE_ROW ){
    int iLang = sqlite3_column_int(pStmt, 0);
    const char *zFrom = (const char*)sqlite3_column_text(pStmt, 1);
    int nFrom = sqlite3_column_bytes(pStmt, 1);
    const char *zTo = (const char*)sqlite3_column_text(pStmt, 2);
    int nTo = sqlite3_column_bytes(pStmt, 2);
    int iCost = sqlite3_column_int(pStmt, 3);

    if( nFrom>100 || nFrom<0 || nTo>100 || nTo<0 ) continue;
    if( iCost<0 ) continue;
    if( iLang!=iLangPrev ){
      EditDist3Lang *pNew;
      p->nLang++;
      pNew = sqlite3_realloc(p->a, p->nLang*sizeof(p->a[0]));
      if( pNew==0 ){ rc = SQLITE_NOMEM; break; }
      p->a = pNew;
      pLang = &p->a[p->nLang-1];
      pLang->iLang = iLang;
      pLang->iInsCost = 100;
      pLang->iDelCost = 100;
      pLang->iSubCost = 200;
      pLang->pCost = 0;
      iLangPrev = iLang;
    }
    if( nFrom==1 && zFrom[0]=='?' && nTo==0 ){
      pLang->iDelCost = iCost;
    }else if( nFrom==0 && nTo==1 && zTo[0]=='?' ){
      pLang->iInsCost = iCost;
    }else if( nFrom==1 && nTo==1 && zFrom[0]=='?' && zTo[0]=='?' ){
      pLang->iSubCost = iCost;
    }else{
      EditDist3Cost *pCost;
      int nExtra = nFrom + nTo - 4;
      if( nExtra<0 ) nExtra = 0;
      pCost = sqlite3_malloc( sizeof(*pCost) + nExtra );
      if( pCost==0 ){ rc = SQLITE_NOMEM; break; }
      pCost->nFrom = nFrom;
      pCost->nTo = nTo;
      pCost->iCost = iCost;
      memcpy(pCost->a, zFrom, nFrom);
      memcpy(pCost->a + nFrom, zTo, nTo);
      pCost->pNext = pLang->pCost;
      pLang->pCost = pCost; 
    }
  }
  sqlite3_finalize(pStmt);
  return rc;
}

/*
** Return the length (in bytes) of a utf-8 character.  Or return a maximum
** of N.
*/
static int utf8Len(unsigned char c, int N){
  int len = 1;
  if( c>0x7f ){
    if( (c&0xe0)==0xc0 ){
      len = 2;
    }else if( (c&0xf0)==0xe0 ){
      len = 3;
    }else{
      len = 4;
    }
  }
  if( len>N ) len = N;
  return len;
}

/*
** Return TRUE (non-zero) of the To side of the given cost matches
** the given string.
*/
static int matchTo(EditDist3Cost *p, const char *z, int n){
  if( p->nTo>n ) return 0;
  if( memcmp(p->a+p->nFrom, z, p->nTo)!=0 ) return 0;
  return 1;
}

/*
** Return TRUE (non-zero) of the To side of the given cost matches
** the given string.
*/
static int matchFrom(EditDist3Cost *p, const char *z, int n){
  if( p->nFrom>n ) return 0;
  if( memcmp(p->a, z, p->nFrom)!=0 ) return 0;
  return 1;
}

/*
** Return TRUE (non-zero) of the next FROM character and the next TO
** character are the same.
*/
static int matchFromTo(
  EditDist3FromString *pStr,  /* Left hand string */
  int n1,                     /* Index of comparison character on the left */
  const char *z2,             /* Right-handl comparison character */
  int n2                      /* Bytes remaining in z2[] */
){
  int b1 = pStr->a[n1].nByte;
  if( b1>n2 ) return 0;
  if( memcmp(pStr->z+n1, z2, b1)!=0 ) return 0;
  return 1;
}

/*
** Delete an EditDist3FromString objecct
*/
static void editDist3FromStringDelete(EditDist3FromString *p){
  int i;
  if( p ){
    for(i=0; i<p->n; i++){
      sqlite3_free(p->a[i].apDel);
      sqlite3_free(p->a[i].apSubst);
    }
    sqlite3_free(p);
  }
}

/*
** Create a EditDist3FromString object.
*/
static EditDist3FromString *editDist3FromStringNew(
  const EditDist3Lang *pLang,
  const char *z,
  int n
){
  EditDist3FromString *pStr;
  EditDist3Cost *p;
  int i;

  if( n<0 ) n = (int)strlen(z);
  pStr = sqlite3_malloc( sizeof(*pStr) + sizeof(pStr->a[0])*n + n + 1 );
  if( pStr==0 ) return 0;
  pStr->a = (EditDist3From*)&pStr[1];
  pStr->n = n;
  pStr->z = (char*)&pStr->a[n];
  memcpy(pStr->z, z, n+1);
  if( n && z[n-1]=='*' ){
    pStr->isPrefix = 1;
    n--;
    pStr->n--;
    pStr->z[n] = 0;
  }else{
    pStr->isPrefix = 0;
  }

  for(i=0; i<n; i++){
    EditDist3From *pFrom = &pStr->a[i];
    memset(pFrom, 0, sizeof(*pFrom));
    pFrom->nByte = utf8Len((unsigned char)z[i], n-i);
    for(p=pLang->pCost; p; p=p->pNext){
      EditDist3Cost **apNew;
      if( i+p->nFrom>n ) continue;
      if( matchFrom(p, z+i, n-i)==0 ) continue;
      if( p->nTo==0 ){
        apNew = sqlite3_realloc(pFrom->apDel,
                                sizeof(*apNew)*(pFrom->nDel+1));
        if( apNew==0 ) break;
        pFrom->apDel = apNew;
        apNew[pFrom->nDel++] = p;
      }else{
        apNew = sqlite3_realloc(pFrom->apSubst,
                                sizeof(*apNew)*(pFrom->nSubst+1));
        if( apNew==0 ) break;
        pFrom->apSubst = apNew;
        apNew[pFrom->nSubst++] = p;
      }
    }
    if( p ){
      editDist3FromStringDelete(pStr);
      pStr = 0;
      break;
    }
  }
  return pStr;
}

/*
** Return the number of bytes in the common prefix of two UTF8 strings.
** Only complete characters are considered.
*/
static int editDist3PrefixLen(const char *z1, const char *z2){
  int n = 0;
  while( z1[n] && z1[n]==z2[n] ){ n++; }
  while( n && (z1[n]&0xc0)==0x80 ){ n--; }
  return n;
}

/*
** Return the number of bytes in the common suffix of two UTF8 strings.
** Only complete characters are considered.
*/
static int editDist3SuffixLen(const char *z1, int n1, const char *z2, int n2){
  int origN1 = n1;
  while( n1>0 && n2>0 && z1[n1-1]==z2[n2-1] ){ n1--; n2--; }
  while( n1<origN1 && (z1[n1]&0xc0)==0x80 ){ n1++; n2++; }
  return origN1 - n1;
}

/*
** Update entry m[i] such that it is the minimum of its current value
** and m[j]+iCost.
**
** If the iCost is 1,000,000 or greater, then consider the cost to be
** infinite and skip the update.
*/
static void updateCost(
  unsigned int *m,
  int i,
  int j,
  int iCost
){
  int b;
  if( iCost<10000 ){
    b = m[j] + iCost;
    if( b<m[i] ) m[i] = b;
  }
}

/* Compute the edit distance between two strings.
**
** If an error occurs, return a negative number which is the error code.
*/
static int editDist3Core(
  EditDist3FromString *pFrom,  /* The FROM string */
  const char *z2,              /* The TO string */
  int n2,                      /* Length of the TO string */
  const EditDist3Lang *pLang   /* Edit weights for a particular language ID */
){
  int k, n;
  int i1, b1;
  int i2, b2;
  EditDist3FromString f = *pFrom;
  EditDist3To *a2;
  unsigned int *m;
  int szRow;
  EditDist3Cost *p;
  int res;

#if 0
  /* Remove comment prefix and suffix */
  n = editDist3PrefixLen(f.z, z2);
  if( f.n==n2 && n2==n ) return 0;  /* Identical strings */
  f.n -= n;
  f.z += n;
  f.a += n;
  n2 -= n;
  z2 += n;
  if( f.isPrefix==0 ){
    n = editDist3SuffixLen(f.z, f.n, z2, n2);
    f.n -= n;
    n2 -= n;
  }
#endif

  /* allocate the Wagner matrix and the aTo[] array for the TO string */
  n = (f.n+1)*(n2+1);
  n = (n+1)&~1;
  m = sqlite3_malloc( n*sizeof(m[0]) + sizeof(a2[0])*n2 );
  if( m==0 ) return -1;            /* Out of memory */
  a2 = (EditDist3To*)&m[n];
  memset(a2, 0, sizeof(a2[0])*n2);

  /* Fill in the a1[] matrix for all characters of the TO string */
  for(i2=0; i2<n2; i2++){
    a2[i2].nByte = utf8Len((unsigned char)z2[i2], n2-i2);
    for(p=pLang->pCost; p; p=p->pNext){
      EditDist3Cost **apNew;
      if( p->nFrom>0 ) continue;
      if( i2+p->nTo>n2 ) continue;
      if( matchTo(p, z2+i2, n2-i2)==0 ) continue;
      a2[i2].nIns++;
      apNew = sqlite3_realloc(a2[i2].apIns, sizeof(*apNew)*a2[i2].nIns);
      if( apNew==0 ){
        res = -1;  /* Out of memory */
        goto editDist3Abort;
      }
      a2[i2].apIns = apNew;
      a2[i2].apIns[a2[i2].nIns-1] = p;
    }
  }

  /* Prepare to compute the minimum edit distance */
  szRow = f.n+1;
  memset(m, 0x01, (n2+1)*szRow*sizeof(m[0]));
  m[0] = 0;

  /* First fill in the top-row of the matrix with FROM deletion costs */
  for(i1=0; i1<f.n; i1 += b1){
    b1 = f.a[i1].nByte;
    updateCost(m, i1+b1, i1, pLang->iDelCost);
    for(k=0; k<f.a[i1].nDel; k++){
      p = f.a[i1].apDel[k];
      updateCost(m, i1+p->nFrom, i1, p->iCost);
    }
  }

  /* Fill in all subsequent rows, top-to-bottom, left-to-right */
  for(i2=0; i2<n2; i2 += b2){
    int rx;      /* Starting index for current row */
    int rxp;     /* Starting index for previous row */
    b2 = a2[i2].nByte;
    rx = szRow*(i2+b2);
    rxp = szRow*i2;
    updateCost(m, rx, rxp, pLang->iInsCost);
    for(k=0; k<a2[i2].nIns; k++){
      p = a2[i2].apIns[k];
      updateCost(m, szRow*(i2+p->nTo), rxp, p->iCost);
    }
    for(i1=0; i1<f.n; i1+=b1){
      int cx;    /* Index of current cell */
      int cxp;   /* Index of cell immediately to the left */
      int cxd;   /* Index of cell to the left and one row above */
      int cxu;   /* Index of cell immediately above */
      b1 = f.a[i1].nByte;
      cxp = rx + i1;
      cx = cxp + b1;
      cxd = rxp + i1;
      cxu = cxd + b1;
      updateCost(m, cx, cxp, pLang->iDelCost);
      for(k=0; k<f.a[i1].nDel; k++){
        p = f.a[i1].apDel[k];
        updateCost(m, cxp+p->nFrom, cxp, p->iCost);
      }
      updateCost(m, cx, cxu, pLang->iInsCost);
      if( matchFromTo(&f, i1, z2+i2, n2-i2) ){
        updateCost(m, cx, cxd, 0);
      }
      updateCost(m, cx, cxd, pLang->iSubCost);
      for(k=0; k<f.a[i1].nSubst; k++){
        p = f.a[i1].apSubst[k];
        if( matchTo(p, z2+i2, n2-i2) ){
          updateCost(m, cxd+p->nFrom+szRow*p->nTo, cxd, p->iCost);
        }
      }
    }
  }

#if 0
  printf("         ^");
  for(i1=0; i1<f.n; i1++) printf(" %c-%2x", f.z[i1], f.z[i1]&0xff);
  printf("\n   ^:");
  for(i1=0; i1<szRow; i1++){
    int v = m[i1];
    if( v>9999 ) printf(" ****");
    else         printf(" %4d", v);
  }
  printf("\n");
  for(i2=0; i2<n2; i2++){
    printf("%c-%02x:", z2[i2], z2[i2]&0xff);
    for(i1=0; i1<szRow; i1++){
      int v = m[(i2+1)*szRow+i1];
      if( v>9999 ) printf(" ****");
      else         printf(" %4d", v);
    }
    printf("\n");
  }
#endif

  /* Free memory allocations and return the result */
  res = (int)m[szRow*(n2+1)-1];
  if( f.isPrefix ){
    for(i2=f.n; i2<n2; i2++){
      int b = m[szRow*i2-1];
      if( b<res ) res = b;
    }
  }

editDist3Abort:
  for(i2=0; i2<n2; i2++) sqlite3_free(a2[i2].apIns);
  sqlite3_free(m);
  return res;
}

/*
** Get an appropriate EditDist3Lang object.
*/
static const EditDist3Lang *editDist3FindLang(
  EditDist3Config *pConfig,
  int iLang
){
  int i;
  for(i=0; i<pConfig->nLang; i++){
    if( pConfig->a[i].iLang==iLang ) return &pConfig->a[i];
  }
  return &editDist3Lang;
}

/*
** Function:    editdist3(A,B,iLang)
**              editdist3(tablename)
**
** Return the cost of transforming string A into string B using edit
** weights for iLang.
**
** The second form loads edit weights into memory from a table.
*/
static void editDist3SqlFunc(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  EditDist3Config *pConfig = (EditDist3Config*)sqlite3_user_data(context);
  sqlite3 *db = sqlite3_context_db_handle(context);
  int rc;
  if( argc==1 ){
    const char *zTable = (const char*)sqlite3_value_text(argv[0]);
    rc = editDist3ConfigLoad(pConfig, db, zTable);
    if( rc ) sqlite3_result_error_code(context, rc);
  }else{
    const char *zA = (const char*)sqlite3_value_text(argv[0]);
    const char *zB = (const char*)sqlite3_value_text(argv[1]);
    int nA = sqlite3_value_bytes(argv[0]);
    int nB = sqlite3_value_bytes(argv[1]);
    int iLang = argc==3 ? sqlite3_value_int(argv[2]) : 0;
    const EditDist3Lang *pLang = editDist3FindLang(pConfig, iLang);
    EditDist3FromString *pFrom;
    int dist;

    pFrom = editDist3FromStringNew(pLang, zA, nA);
    if( pFrom==0 ){
      sqlite3_result_error_nomem(context);
      return;
    }
    dist = editDist3Core(pFrom, zB, nB, pLang);
    editDist3FromStringDelete(pFrom);
    sqlite3_result_int(context, dist);
  } 
}

/*
** Register the editDist3 function with SQLite
*/
static int editDist3Install(sqlite3 *db){
  int rc;
  EditDist3Config *pConfig = sqlite3_malloc( sizeof(*pConfig) );
  if( pConfig==0 ) return SQLITE_NOMEM;
  memset(pConfig, 0, sizeof(*pConfig));
  rc = sqlite3_create_function_v2(db, "editdist3",
              2, SQLITE_UTF8, pConfig, editDist3SqlFunc, 0, 0, 0);
  if( rc==SQLITE_OK ){
    rc = sqlite3_create_function_v2(db, "editdist3",
                3, SQLITE_UTF8, pConfig, editDist3SqlFunc, 0, 0, 0);
  }
  if( rc==SQLITE_OK ){
    rc = sqlite3_create_function_v2(db, "editdist3",
                1, SQLITE_UTF8, pConfig, editDist3SqlFunc, 0, 0,
                editDist3ConfigDelete);
  }else{
    sqlite3_free(pConfig);
  }
  return rc;
}
/* End configurable cost unicode edit distance routines
******************************************************************************
******************************************************************************
** Begin transliterate unicode-to-ascii implementation
*/

#if !SQLITE_AMALGAMATION
/*
** This lookup table is used to help decode the first byte of
** a multi-byte UTF8 character.
*/
static const unsigned char sqlite3Utf8Trans1[] = {
  0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
  0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,

  { 0x0423,  0x55, 0x00 },  /* У to U */
  { 0x0424,  0x46, 0x00 },  /* Ф to F */
  { 0x0425,  0x4b, 0x68 },  /* Х to Kh */
  { 0x0426,  0x54, 0x63 },  /* Ц to Tc */
  { 0x0427,  0x43, 0x68 },  /* Ч to Ch */
  { 0x0428,  0x53, 0x68 },  /* Ш to Sh */
  { 0x0429,  0x53, 0x68 },  /* Щ to Shch */
  { 0x042A,  0x61, 0x00 },  /*  to A */
  { 0x042B,  0x59, 0x00 },  /* Ы to Y */
  { 0x042C,  0x59, 0x00 },  /*  to Y */
  { 0x042D,  0x45, 0x00 },  /* Э to E */
  { 0x042E,  0x49, 0x75 },  /* Ю to Iu */
  { 0x042F,  0x49, 0x61 },  /* Я to Ia */
  { 0x0430,  0x61, 0x00 },  /* а to a */
  { 0x0431,  0x62, 0x00 },  /* б to b */
  { 0x0432,  0x76, 0x00 },  /* в to v */
  { 0x0433,  0x67, 0x00 },  /* г to g */

  { 0x0443,  0x75, 0x00 },  /* у to u */
  { 0x0444,  0x66, 0x00 },  /* ф to f */
  { 0x0445,  0x6b, 0x68 },  /* х to kh */
  { 0x0446,  0x74, 0x63 },  /* ц to tc */
  { 0x0447,  0x63, 0x68 },  /* ч to ch */
  { 0x0448,  0x73, 0x68 },  /* ш to sh */
  { 0x0449,  0x73, 0x68 },  /* щ to shch */
  { 0x044A,  0x61, 0x00 },  /*  to a */
  { 0x044B,  0x79, 0x00 },  /* ы to y */
  { 0x044C,  0x79, 0x00 },  /*  to y */
  { 0x044D,  0x65, 0x00 },  /* э to e */
  { 0x044E,  0x69, 0x75 },  /* ю to iu */
  { 0x044F,  0x69, 0x61 },  /* я to ia */
  { 0x0450,  0x65, 0x00 },  /* ѐ to e */
  { 0x0451,  0x65, 0x00 },  /* ё to e */
  { 0x0452,  0x64, 0x00 },  /* ђ to d */
  { 0x0453,  0x67, 0x00 },  /* ѓ to g */

    case SCRIPT_CYRILLIC:  res = 220; break;
    case SCRIPT_GREEK:     res = 200; break;
    default:               res = 998; break;
  }
  sqlite3_result_int(context, res);
}

/* End transliterate
******************************************************************************
******************************************************************************
** Begin Polloc & Zamora SPEEDCOP style keying functions.
*/
/*
** The Pollock & Zamora skeleton function.  Move all consonants to the
** front and all vowels to the end, removing duplicates.  Except if the
** first letter is a vowel then it remains as the first letter.
*/
static void pollockSkeletonKey(const char *zIn, char *zOut){
  int i, j;
  unsigned char c;
  char seen[26];
  static const unsigned char isVowel[] = { 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0,
    0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 };
  memset(seen, 0, sizeof(seen));
  for(i=j=0; (c = (unsigned char)zIn[i])!=0; i++){
    if( c<'a' || c>'z' ) continue;
    if( j>0 || isVowel[c-'a'] ) continue;
    if( seen[c-'a'] ) continue;
    seen[c-'a'] = 1;
    zOut[j++] = c;
  }
  for(i=0; (c = (unsigned char)zIn[i])!=0; i++){
    if( c<'a' || c>'z' ) continue;
    if( seen[c-'a'] ) continue;
    if( !isVowel[c-'a'] ) continue;
    seen[c-'a'] = 1;
    zOut[j++] = c;
  }
  zOut[j] = 0;
}

/*
** Function:    pollock_skeleton(X)
**
** Return the Pollock and Zamora skeleton key for a string X of all
** lower-case letters.
*/
static void pollockSkeletonSqlFunc(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  const char *zIn = (const char*)sqlite3_value_text(argv[0]);
  int nIn = sqlite3_value_bytes(argv[0]);
  char *zOut;
  if( zIn ){
    zOut = sqlite3_malloc( nIn + 1 );
    if( zOut==0 ){
      sqlite3_result_error_nomem(context);
    }else{
      pollockSkeletonKey(zIn, zOut);
      sqlite3_result_text(context, (char*)zOut, -1, sqlite3_free);
    }
  }
}  

/*
** The Pollock & Zamora omission key.
**
** The key consists of unique consonants in the following order:
**
**         jkqxzvwybfmgpdhclntsr
**
** These are followed by unique vowels in input order.
*/
static void pollockOmissionKey(const char *zIn, char *zOut){
  int i, j;
  unsigned char c;
  char seen[26];
  static const unsigned char isVowel[] = { 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0,
    0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 };
  static const unsigned char constOrder[] = "jkqxzvwybfmgpdhclntsr";

  memset(seen, 0, sizeof(seen));
  for(i=j=0; (c = (unsigned char)zIn[i])!=0; i++){
    if( c<'a' || c>'z' ) continue;
    if( isVowel[c-'a'] ) continue;
    if( seen[c-'a'] ) continue;
    seen[c-'a'] = 1;
  }
  for(i=0; (c = constOrder[i])!=0; i++){
    if( seen[c-'a'] ) zOut[j++] = c;
  }
  for(i=0; (c = (unsigned char)zIn[i])!=0; i++){
    if( c<'a' || c>'z' ) continue;
    if( seen[c-'a'] ) continue;
    if( !isVowel[c-'a'] ) continue;
    seen[c-'a'] = 1;
    zOut[j++] = c;
  }
  zOut[j] = 0;
}

/*
** Function:    pollock_omission(X)
**
** Return the Pollock and Zamora omission key for a string X of all
** lower-case letters.
*/
static void pollockOmissionSqlFunc(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  const char *zIn = (const char*)sqlite3_value_text(argv[0]);
  int nIn = sqlite3_value_bytes(argv[0]);
  char *zOut;
  if( zIn ){
    zOut = sqlite3_malloc( nIn + 1 );
    if( zOut==0 ){
      sqlite3_result_error_nomem(context);
    }else{
      pollockOmissionKey(zIn, zOut);
      sqlite3_result_text(context, (char*)zOut, -1, sqlite3_free);
    }
  }
}  


/* End SPEEDCOP keying functions
******************************************************************************
******************************************************************************
** Begin spellfix1 virtual table.
*/

/* Maximum length of a phonehash used for querying the shadow table */
#define SPELLFIX_MX_HASH  8

/* Maximum number of hash strings to examine per query */
#define SPELLFIX_MX_RUN   8

typedef struct spellfix1_vtab spellfix1_vtab;
typedef struct spellfix1_cursor spellfix1_cursor;

/* Fuzzy-search virtual table object */
struct spellfix1_vtab {
  sqlite3_vtab base;         /* Base class - must be first */
  sqlite3 *db;               /* Database connection */
  char *zDbName;             /* Name of database holding this table */
  char *zTableName;          /* Name of the virtual table */
  char *zCostTable;          /* Table holding edit-distance cost numbers */
  EditDist3Config *pConfig3; /* Parsed edit distance costs */
};

/* Fuzzy-search cursor object */
struct spellfix1_cursor {
  sqlite3_vtab_cursor base;    /* Base class - must be first */
  spellfix1_vtab *pVTab;       /* The table to which this cursor belongs */
  int nRow;                    /* Number of rows of content */
  int nAlloc;                  /* Number of allocated rows */
  int iRow;                    /* Current row of content */
  int iLang;                   /* Value of the lang= constraint */
  int iTop;                    /* Value of the top= constraint */
  int iScope;                  /* Value of the scope= constraint */
  int nSearch;                 /* Number of vocabulary items checked */
  struct spellfix1_row {       /* For each row of content */
    sqlite3_int64 iRowid;         /* Rowid for this row */
    char *zWord;                  /* Text for this row */
    int iRank;                    /* Rank for this row */
    int iDistance;                /* Distance from pattern for this row */
    int iScore;                   /* Score for sorting */
    char zHash[SPELLFIX_MX_HASH]; /* the phonehash used for this match */
  } *a; 
};

/*
** Construct one or more SQL statements from the format string given
** and then evaluate those statements. The success code is written
** into *pRc.

  if( isDestroy ){
    sqlite3 *db = p->db;
    spellfix1DbExec(&rc, db, "DROP TABLE IF EXISTS \"%w\".\"%w_vocab\"",
                  p->zDbName, p->zTableName);
  }
  if( rc==SQLITE_OK ){
    sqlite3_free(p->zTableName);
    editDist3ConfigDelete(p->pConfig3);
    sqlite3_free(p->zCostTable);
    sqlite3_free(p);
  }
  return rc;
}
static int spellfix1Disconnect(sqlite3_vtab *pVTab){
  return spellfix1Uninit(0, pVTab);
}
static int spellfix1Destroy(sqlite3_vtab *pVTab){
  return spellfix1Uninit(1, pVTab);
}

/*
** Make a copy of a string.  Remove leading and trailing whitespace
** and dequote it.
*/
static char *spellfix1Dequote(const char *zIn){
  char *zOut;
  int i, j;
  char c;
  while( isspace(zIn[0]) ) zIn++;
  zOut = sqlite3_mprintf("%s", zIn);
  if( zOut==0 ) return 0;
  i = (int)strlen(zOut);
  while( i>0 && isspace(zOut[i-1]) ){ i--; }
  zOut[i] = 0;
  c = zOut[0];
  if( c=='\'' || c=='"' ){
    for(i=1, j=0; zOut[i]; i++){
      zOut[j++] = zOut[i];
      if( zOut[i]==c ){
        if( zOut[i+1]==c ){
          i++;
        }else{
          zOut[j-1] = 0;
          break;
        }
      }
    }
  }
  return zOut;
}


/*
** xConnect/xCreate method for the spellfix1 module. Arguments are:
**
**   argv[0]   -> module name  ("spellfix1")
**   argv[1]   -> database name
**   argv[2]   -> table name

){
  spellfix1_vtab *pNew = 0;
  const char *zModule = argv[0];
  const char *zDbName = argv[1];
  const char *zTableName = argv[2];
  int nDbName;
  int rc = SQLITE_OK;
  int i;

  if( argc<3 ){
    *pzErr = sqlite3_mprintf(
        "%s: wrong number of CREATE VIRTUAL TABLE arguments", argv[0]
    );
    rc = SQLITE_ERROR;
  }else{

      pNew->zTableName = sqlite3_mprintf("%s", zTableName);
      pNew->db = db;
      if( pNew->zTableName==0 ){
        rc = SQLITE_NOMEM;
      }else{
        rc = sqlite3_declare_vtab(db, 
             "CREATE TABLE x(word,rank,distance,langid,"
             "score, phonehash,top HIDDEN,scope HIDDEN,srchcnt HIDDEN,"
             "soundslike HIDDEN,command HIDDEN)"
        );
#define SPELLFIX_COL_WORD            0
#define SPELLFIX_COL_RANK            1
#define SPELLFIX_COL_DISTANCE        2
#define SPELLFIX_COL_LANGID          3
#define SPELLFIX_COL_SCORE           4
#define SPELLFIX_COL_PHONEHASH       5
#define SPELLFIX_COL_TOP             6
#define SPELLFIX_COL_SCOPE           7
#define SPELLFIX_COL_SRCHCNT         8
#define SPELLFIX_COL_SOUNDSLIKE      9
#define SPELLFIX_COL_COMMAND        10
      }
      if( rc==SQLITE_OK && isCreate ){
        sqlite3_uint64 r;
        spellfix1DbExec(&rc, db,
           "CREATE TABLE IF NOT EXISTS \"%w\".\"%w_vocab\"(\n"
           "  id INTEGER PRIMARY KEY,\n"
           "  rank INT,\n"
           "  langid INT,\n"
           "  word TEXT,\n"
           "  k1 TEXT,\n"
           "  k2 TEXT\n"
           ");\n",
           zDbName, zTableName
        );
        sqlite3_randomness(sizeof(r), &r);
        spellfix1DbExec(&rc, db,
           "CREATE INDEX IF NOT EXISTS \"%w\".\"%w_index_%llx\" "
              "ON \"%w_vocab\"(langid,k2);",
           zDbName, zModule, r, zTableName
        );
      }
      for(i=3; rc==SQLITE_OK && i<argc; i++){
        if( memcmp(argv[i],"edit_cost_table=",16)==0 && pNew->zCostTable==0 ){
          pNew->zCostTable = spellfix1Dequote(&argv[i][16]);
          if( pNew->zCostTable==0 ) rc = SQLITE_NOMEM;
          continue;
        }
        rc = SQLITE_ERROR; 
      }
    }
  }

  *ppVTab = (sqlite3_vtab *)pNew;
  return rc;
}

  sqlite3_vtab **ppVTab,
  char **pzErr
){
  return spellfix1Init(1, db, pAux, argc, argv, ppVTab, pzErr);
}

/*
** Clear all of the content from a cursor.

*/
static void spellfix1ResetCursor(spellfix1_cursor *pCur){
  int i;
  for(i=0; i<pCur->nRow; i++){
    sqlite3_free(pCur->a[i].zWord);
  }


  pCur->nRow = 0;
  pCur->iRow = 0;
  pCur->nSearch = 0;
}

/*
** Resize the cursor to hold up to N rows of content
*/
static void spellfix1ResizeCursor(spellfix1_cursor *pCur, int N){
  struct spellfix1_row *aNew;
  assert( N>=pCur->nRow );
  aNew = sqlite3_realloc(pCur->a, sizeof(pCur->a[0])*N);
  if( aNew==0 && N>0 ){
    spellfix1ResetCursor(pCur);
    sqlite3_free(pCur->a);
    pCur->nAlloc = 0;
    pCur->a = 0;
  }else{
    pCur->nAlloc = N;
    pCur->a = aNew;
  }
}


/*
** Close a fuzzy-search cursor.
*/
static int spellfix1Close(sqlite3_vtab_cursor *cur){
  spellfix1_cursor *pCur = (spellfix1_cursor *)cur;
  spellfix1ResetCursor(pCur);
  spellfix1ResizeCursor(pCur, 0);
  sqlite3_free(pCur);
  return SQLITE_OK;
}

/*
** Search for terms of these forms:
**
**   (A)    word MATCH $str
**   (B)    langid == $langid
**   (C)    top = $top
**   (D)    scope = $scope
**   (E)    distance < $distance
**   (F)    distance <= $distance
**
** The plan number is a bit mask formed with these bits:
**
**   0x01   (A) is found
**   0x02   (B) is found
**   0x04   (C) is found
**   0x08   (D) is found
**   0x10   (E) is found
**   0x20   (F) is found
**
** filter.argv[*] values contains $str, $langid, $top, and $scope,
** if specified and in that order.
*/
static int spellfix1BestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
  int iPlan = 0;
  int iLangTerm = -1;
  int iTopTerm = -1;
  int iScopeTerm = -1;
  int iDistTerm = -1;
  int i;
  const struct sqlite3_index_constraint *pConstraint;
  pConstraint = pIdxInfo->aConstraint;
  for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
    if( pConstraint->usable==0 ) continue;

    /* Terms of the form:  word MATCH $str */
    if( (iPlan & 1)==0 
     && pConstraint->iColumn==SPELLFIX_COL_WORD
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH
    ){
      iPlan |= 1;
      pIdxInfo->aConstraintUsage[i].argvIndex = 1;
      pIdxInfo->aConstraintUsage[i].omit = 1;
    }

    /* Terms of the form:  langid = $langid  */
    if( (iPlan & 2)==0
     && pConstraint->iColumn==SPELLFIX_COL_LANGID
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
    ){
      iPlan |= 2;
      iLangTerm = i;
    }

    /* Terms of the form:  top = $top */
    if( (iPlan & 4)==0
     && pConstraint->iColumn==SPELLFIX_COL_TOP
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
    ){
      iPlan |= 4;
      iTopTerm = i;
    }

    /* Terms of the form:  scope = $scope */
    if( (iPlan & 8)==0
     && pConstraint->iColumn==SPELLFIX_COL_SCOPE
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
    ){
      iPlan |= 8;
      iScopeTerm = i;
    }

    /* Terms of the form:  distance < $dist or distance <= $dist */
    if( (iPlan & (16|32))==0
     && pConstraint->iColumn==SPELLFIX_COL_DISTANCE
     && (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT
          || pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE)
    ){
      iPlan |= pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT ? 16 : 32;
      iDistTerm = i;
    }
  }
  if( iPlan&1 ){
    int idx = 2;
    pIdxInfo->idxNum = iPlan;
    if( pIdxInfo->nOrderBy==1
     && pIdxInfo->aOrderBy[0].iColumn==4
     && pIdxInfo->aOrderBy[0].desc==0

      pIdxInfo->aConstraintUsage[iTopTerm].argvIndex = idx++;
      pIdxInfo->aConstraintUsage[iTopTerm].omit = 1;
    }
    if( iPlan&8 ){
      pIdxInfo->aConstraintUsage[iScopeTerm].argvIndex = idx++;
      pIdxInfo->aConstraintUsage[iScopeTerm].omit = 1;
    }
    if( iPlan&(16|32) ){
      pIdxInfo->aConstraintUsage[iDistTerm].argvIndex = idx++;
      pIdxInfo->aConstraintUsage[iDistTerm].omit = 1;
    }
    pIdxInfo->estimatedCost = (double)10000;
  }else{
    pIdxInfo->idxNum = 0;
    pIdxInfo->estimatedCost = (double)10000000;
  }
  return SQLITE_OK;
}

** that they sort in order of increasing distance.
*/
static int spellfix1RowCompare(const void *A, const void *B){
  const struct spellfix1_row *a = (const struct spellfix1_row*)A;
  const struct spellfix1_row *b = (const struct spellfix1_row*)B;
  return a->iScore - b->iScore;
}

/*
** A structure used to pass information from spellfix1FilterForMatch()
** into spellfix1RunQuery().
*/
typedef struct MatchQuery {
  spellfix1_cursor *pCur;          /* The cursor being queried */
  sqlite3_stmt *pStmt;             /* shadow table query statment */
  char zHash[SPELLFIX_MX_HASH];    /* The current phonehash for zPattern */
  const char *zPattern;            /* Transliterated input string */
  int nPattern;                    /* Length of zPattern */
  EditDist3FromString *pMatchStr3; /* Original unicode string */
  EditDist3Config *pConfig3;       /* Edit-distance cost coefficients */
  const EditDist3Lang *pLang;      /* The selected language coefficients */
  int iLang;                       /* The language id */
  int iScope;                      /* Default scope */
  int iMaxDist;                    /* Maximum allowed edit distance, or -1 */
  int rc;                          /* Error code */
  int nRun;                  /* Number of prior runs for the same zPattern */
  char azPrior[SPELLFIX_MX_RUN][SPELLFIX_MX_HASH];  /* Prior hashes */
} MatchQuery;

/*
** Run a query looking for the best matches against zPattern using
** zHash as the character class seed hash.
*/
static void spellfix1RunQuery(MatchQuery *p, const char *zQuery, int nQuery){
  const char *zK1;
  const char *zWord;
  int iDist;
  int iRank;
  int iScore;
  int iWorst = 0;
  int idx;
  int idxWorst = -1;
  int i;
  int iScope = p->iScope;
  spellfix1_cursor *pCur = p->pCur;
  sqlite3_stmt *pStmt = p->pStmt;
  char zHash1[SPELLFIX_MX_HASH];
  char zHash2[SPELLFIX_MX_HASH];
  char *zClass;
  int nClass;

  if( pCur->a==0 || p->rc ) return;   /* Prior memory allocation failure */
  if( p->nRun>=SPELLFIX_MX_RUN ) return;
  zClass = (char*)phoneticHash((unsigned char*)zQuery, nQuery);
  if( zClass==0 ){
    p->rc = SQLITE_NOMEM;
    return;
  }
  nClass = strlen(zClass);
  if( nClass>SPELLFIX_MX_HASH-2 ){
    nClass = SPELLFIX_MX_HASH-2;
    zClass[nClass] = 0;
  }
  if( nClass<=iScope ){
    if( nClass>2 ){
      iScope = nClass-1;
    }else{
      iScope = nClass;
    }
  }
  memcpy(zHash1, zClass, iScope);
  sqlite3_free(zClass);
  zHash1[iScope] = 0;
  memcpy(zHash2, zHash1, iScope);
  zHash2[iScope] = 'Z';
  zHash2[iScope+1] = 0;
  for(i=0; i<p->nRun; i++){
    if( strcmp(p->azPrior[i], zHash1)==0 ) return;
  }
  memcpy(p->azPrior[p->nRun++], zHash1, iScope+1);
  sqlite3_bind_text(pStmt, 1, zHash1, -1, SQLITE_STATIC);
  sqlite3_bind_text(pStmt, 2, zHash2, -1, SQLITE_STATIC);
  for(i=0; i<pCur->nRow; i++){
    if( pCur->a[i].iScore>iWorst ){
      iWorst = pCur->a[i].iScore;
      idxWorst = i;
    }
  }
  while( sqlite3_step(pStmt)==SQLITE_ROW ){
    iRank = sqlite3_column_int(pStmt, 2);
    if( p->pMatchStr3 ){
      int nWord = sqlite3_column_bytes(pStmt, 1);
      zWord = (const char*)sqlite3_column_text(pStmt, 1);
      iDist = editDist3Core(p->pMatchStr3, zWord, nWord, p->pLang);
    }else{
      zK1 = (const char*)sqlite3_column_text(pStmt, 3);
      if( zK1==0 ) continue;
      iDist = editdist1(p->zPattern, zK1, pCur->iLang);
    }
    pCur->nSearch++;
    iScore = spellfix1Score(iDist,iRank);
    if( p->iMaxDist>=0 ){
      if( iDist>p->iMaxDist ) continue;
      if( pCur->nRow>=pCur->nAlloc-1 ){
        spellfix1ResizeCursor(pCur, pCur->nAlloc*2 + 10);
        if( pCur->a==0 ) break;
      }
      idx = pCur->nRow;
    }else if( pCur->nRow<pCur->nAlloc ){
      idx = pCur->nRow;
    }else if( iScore<iWorst ){
      idx = idxWorst;
      sqlite3_free(pCur->a[idx].zWord);
    }else{
      continue;
    }
    pCur->a[idx].zWord = sqlite3_mprintf("%s", sqlite3_column_text(pStmt, 1));
    pCur->a[idx].iRowid = sqlite3_column_int64(pStmt, 0);
    pCur->a[idx].iRank = iRank;
    pCur->a[idx].iDistance = iDist;
    pCur->a[idx].iScore = iScore;
    memcpy(pCur->a[idx].zHash, zHash1, iScope+1);
    if( pCur->nRow<pCur->nAlloc ) pCur->nRow++;
    if( pCur->nRow==pCur->nAlloc ){
      iWorst = pCur->a[0].iScore;
      idxWorst = 0;
      for(i=1; i<pCur->nRow; i++){
        iScore = pCur->a[i].iScore;
        if( iWorst<iScore ){
          iWorst = iScore;
          idxWorst = i;
        }
      }
    }
  }
  sqlite3_reset(pStmt);
}

/*
** This version of the xFilter method work if the MATCH term is present
** and we are doing a scan.
*/
static int spellfix1FilterForMatch(
  spellfix1_cursor *pCur,
  int idxNum,
  int argc,
  sqlite3_value **argv
){
  const unsigned char *zMatchThis;   /* RHS of the MATCH operator */
  EditDist3FromString *pMatchStr3 = 0; /* zMatchThis as an editdist string */
  char *zPattern;                    /* Transliteration of zMatchThis */
  int nPattern;                      /* Length of zPattern */


  int iLimit = 20;                   /* Max number of rows of output */
  int iScope = 3;                    /* Use this many characters of zClass */
  int iLang = 0;                     /* Language code */
  char *zSql;                        /* SQL of shadow table query */

  sqlite3_stmt *pStmt;               /* Shadow table query */
  int rc;                            /* Result code */
  int idx = 1;                       /* Next available filter parameter */
  spellfix1_vtab *p = pCur->pVTab;   /* The virtual table that owns pCur */
  MatchQuery x;                      /* For passing info to RunQuery() */

  /* Load the cost table if we have not already done so */
  if( p->zCostTable!=0 && p->pConfig3==0 ){
    p->pConfig3 = sqlite3_malloc( sizeof(p->pConfig3[0]) );
    if( p->pConfig3==0 ) return SQLITE_NOMEM;
    memset(p->pConfig3, 0, sizeof(p->pConfig3[0]));
    rc = editDist3ConfigLoad(p->pConfig3, p->db, p->zCostTable);
    if( rc ) return rc;
  }
  memset(&x, 0, sizeof(x));
  x.iScope = 3;  /* Default scope if none specified by "WHERE scope=N" */
  x.iMaxDist = -1;   /* Maximum allowed edit distance */

  if( idxNum&2 ){
    iLang = sqlite3_value_int(argv[idx++]);
  }
  if( idxNum&4 ){
    iLimit = sqlite3_value_int(argv[idx++]);
    if( iLimit<1 ) iLimit = 1;
  }
  if( idxNum&8 ){
    x.iScope = sqlite3_value_int(argv[idx++]);
    if( x.iScope<1 ) x.iScope = 1;
    if( x.iScope>SPELLFIX_MX_HASH-2 ) x.iScope = SPELLFIX_MX_HASH-2;
  }
  if( idxNum&(16|32) ){
    x.iMaxDist = sqlite3_value_int(argv[idx++]);
    if( idxNum&16 ) x.iMaxDist--;
    if( x.iMaxDist<0 ) x.iMaxDist = 0;
  }
  spellfix1ResetCursor(pCur);
  spellfix1ResizeCursor(pCur, iLimit);
  zMatchThis = sqlite3_value_text(argv[0]);
  if( zMatchThis==0 ) return SQLITE_OK;
  if( p->pConfig3 ){
    x.pLang = editDist3FindLang(p->pConfig3, iLang);
    pMatchStr3 = editDist3FromStringNew(x.pLang, (const char*)zMatchThis, -1);
  }else{
    x.pLang = 0;
  }
  zPattern = (char*)transliterate(zMatchThis, sqlite3_value_bytes(argv[0]));
  if( zPattern==0 ) return SQLITE_NOMEM;
  nPattern = strlen(zPattern);
  if( zPattern[nPattern-1]=='*' ) nPattern--;








  zSql = sqlite3_mprintf(
     "SELECT id, word, rank, k1"
     "  FROM \"%w\".\"%w_vocab\""
     " WHERE langid=%d AND k2>=?1 AND k2<?2",
     p->zDbName, p->zTableName, iLang
  );
  rc = sqlite3_prepare_v2(p->db, zSql, -1, &pStmt, 0);
  sqlite3_free(zSql);
  pCur->iLang = iLang;
  x.pCur = pCur;
  x.pStmt = pStmt;
  x.zPattern = zPattern;
  x.nPattern = nPattern;
  x.pMatchStr3 = pMatchStr3;
  x.iLang = iLang;
  x.rc = rc;
  x.pConfig3 = p->pConfig3;
  if( x.rc==SQLITE_OK ){
    spellfix1RunQuery(&x, zPattern, nPattern);
  }















#if 0
  /* Convert "ght" to "t" in the original pattern and try again */





  if( x.rc==SQLITE_OK ){


    int i, j;                         /* Loop counters */
    char zQuery[50];                  /* Space for alternative query string */
    for(i=j=0; i<nPattern && i<sizeof(zQuery)-1; i++){
      char c = zPattern[i];

      if( c=='g' && i<nPattern-2 && zPattern[i+1]=='h' && zPattern[i+2]=='t' ){
        i += 2;
        c= 't';
      }
      zQuery[j++] = c;
    }
    zQuery[j] = 0;
    if( j<i ){
      spellfix1RunQuery(&x, zQuery, j);
    }
  }
#endif

  if( pCur->a ){
    qsort(pCur->a, pCur->nRow, sizeof(pCur->a[0]), spellfix1RowCompare);
    pCur->iTop = iLimit;
    pCur->iScope = iScope;
  }
  sqlite3_finalize(pStmt);
  sqlite3_free(zPattern);
  editDist3FromStringDelete(pMatchStr3);
  return pCur->a ? x.rc : SQLITE_NOMEM;
}

/*
** This version of xFilter handles a full-table scan case
*/
static int spellfix1FilterForFullScan(
  spellfix1_cursor *pCur,
  int idxNum,
  int argc,
  sqlite3_value **argv
){
  spellfix1ResetCursor(pCur);
  spellfix1ResizeCursor(pCur, 0);
  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

/*
** Return columns from the current row.
*/
static int spellfix1Column(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
  spellfix1_cursor *pCur = (spellfix1_cursor*)cur;
  switch( i ){
    case SPELLFIX_COL_WORD: {
      sqlite3_result_text(ctx, pCur->a[pCur->iRow].zWord, -1, SQLITE_STATIC);
      break;
    }
    case SPELLFIX_COL_RANK: {
      sqlite3_result_int(ctx, pCur->a[pCur->iRow].iRank);
      break;
    }
    case SPELLFIX_COL_DISTANCE: {
      sqlite3_result_int(ctx, pCur->a[pCur->iRow].iDistance);
      break;
    }
    case SPELLFIX_COL_LANGID: {
      sqlite3_result_int(ctx, pCur->iLang);
      break;
    }
    case SPELLFIX_COL_SCORE: {
      sqlite3_result_int(ctx, pCur->a[pCur->iRow].iScore);
      break;
    }
    case SPELLFIX_COL_PHONEHASH: {
      sqlite3_result_text(ctx, pCur->a[pCur->iRow].zHash, -1, SQLITE_STATIC);
      break;
    }
    case SPELLFIX_COL_TOP: {
      sqlite3_result_int(ctx, pCur->iTop);
      break;
    }
    case SPELLFIX_COL_SCOPE: {
      sqlite3_result_int(ctx, pCur->iScope);
      break;
    }
    case SPELLFIX_COL_SRCHCNT: {
      sqlite3_result_int(ctx, pCur->nSearch);
      break;
    }
    default: {
      sqlite3_result_null(ctx);
      break;
    }

  if( argc==1 ){
    /* A delete operation on the rowid given by argv[0] */
    rowid = *pRowid = sqlite3_value_int64(argv[0]);
    spellfix1DbExec(&rc, db, "DELETE FROM \"%w\".\"%w_vocab\" "
                           " WHERE id=%lld",
                  p->zDbName, p->zTableName, rowid);
  }else{
    const unsigned char *zWord = sqlite3_value_text(argv[SPELLFIX_COL_WORD+2]);
    int nWord = sqlite3_value_bytes(argv[SPELLFIX_COL_WORD+2]);
    int iLang = sqlite3_value_int(argv[SPELLFIX_COL_LANGID+2]);
    int iRank = sqlite3_value_int(argv[SPELLFIX_COL_RANK+2]);
    const unsigned char *zSoundslike =
           sqlite3_value_text(argv[SPELLFIX_COL_SOUNDSLIKE+2]);
    int nSoundslike = sqlite3_value_bytes(argv[SPELLFIX_COL_SOUNDSLIKE+2]);
    char *zK1, *zK2;
    int i;
    char c;

    if( zWord==0 ){
      /* Inserts of the form:  INSERT INTO table(command) VALUES('xyzzy');
      ** cause zWord to be NULL, so we look at the "command" column to see
      ** what special actions to take */
      const char *zCmd = 
         (const char*)sqlite3_value_text(argv[SPELLFIX_COL_COMMAND+2]);
      if( zCmd==0 ){
        pVTab->zErrMsg = sqlite3_mprintf("%s.word may not be NULL",
                                         p->zTableName);
        return SQLITE_CONSTRAINT;
      }
      if( strcmp(zCmd,"reset")==0 ){
        /* Reset the  edit cost table (if there is one). */
        editDist3ConfigDelete(p->pConfig3);
        p->pConfig3 = 0;
        return SQLITE_OK;
      }
      pVTab->zErrMsg = sqlite3_mprintf("unknown value for %s.command: \"%w\"",
                                       p->zTableName, zCmd);
      return SQLITE_ERROR;
    }
    if( iRank<1 ) iRank = 1;
    if( zSoundslike ){
      zK1 = (char*)transliterate(zSoundslike, nSoundslike);
    }else{
      zK1 = (char*)transliterate(zWord, nWord);
    }
    if( zK1==0 ) return SQLITE_NOMEM;
    for(i=0; (c = zK1[i])!=0; i++){
       if( c>='A' && c<='Z' ) zK1[i] += 'a' - 'A';
    }
    zK2 = (char*)phoneticHash((const unsigned char*)zK1, i);
    if( zK2==0 ){
      sqlite3_free(zK1);
      return SQLITE_NOMEM;
    }
    if( sqlite3_value_type(argv[0])==SQLITE_NULL ){
      spellfix1DbExec(&rc, db,
             "INSERT INTO \"%w\".\"%w_vocab\"(rank,langid,word,k1,k2) "

static int spellfix1Register(sqlite3 *db){
  int nErr = 0;
  int i;
  nErr += sqlite3_create_function(db, "spellfix1_translit", 1, SQLITE_UTF8, 0,
                                  transliterateSqlFunc, 0, 0);
  nErr += sqlite3_create_function(db, "spellfix1_editdist", 2, SQLITE_UTF8, 0,
                                  editdistSqlFunc, 0, 0);
  nErr += sqlite3_create_function(db, "spellfix1_editdist", 3, SQLITE_UTF8, 0,
                                  editdistSqlFunc, 0, 0);
  nErr += sqlite3_create_function(db, "spellfix1_phonehash", 1, SQLITE_UTF8, 0,
                                  phoneticHashSqlFunc, 0, 0);
  nErr += sqlite3_create_function(db, "spellfix1_scriptcode", 1, SQLITE_UTF8, 0,
                                  scriptCodeSqlFunc, 0, 0);
  nErr += sqlite3_create_function(db, "pollock_skeleton", 1, SQLITE_UTF8, 0,
                                  pollockSkeletonSqlFunc, 0, 0);
  nErr += sqlite3_create_function(db, "pollock_omission", 1, SQLITE_UTF8, 0,
                                  pollockOmissionSqlFunc, 0, 0);
  nErr += sqlite3_create_module(db, "spellfix1", &spellfix1Module, 0);
  nErr += editDist3Install(db);

  /* Verify sanity of the translit[] table */
  for(i=0; i<sizeof(translit)/sizeof(translit[0])-1; i++){
    assert( translit[i].cFrom<translit[i+1].cFrom );
  }

  return nErr ? SQLITE_ERROR : SQLITE_OK;
}

#if SQLITE_CORE || defined(SQLITE_TEST)
/*
** Register the spellfix1 virtual table and its associated functions.