ext/misc/amatch.c

   1 /*
   2 ** 2013-03-14
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 *************************************************************************
  12 **
  13 ** This file contains code for a demonstration virtual table that finds
  14 ** "approximate matches" - strings from a finite set that are nearly the
  15 ** same as a single input string.  The virtual table is called "amatch".
  16 **
  17 ** A amatch virtual table is created like this:
  18 **
  19 **     CREATE VIRTUAL TABLE f USING approximate_match(
  20 **        vocabulary_table=<tablename>,      -- V
  21 **        vocabulary_word=<columnname>,      -- W
  22 **        vocabulary_language=<columnname>,  -- L
  23 **        edit_distances=<edit-cost-table>
  24 **     );
  25 **
  26 ** When it is created, the new amatch table must be supplied with the
  27 ** the name of a table V and columns V.W and V.L such that
  28 **
  29 **     SELECT W FROM V WHERE L=$language
  30 **
  31 ** returns the allowed vocabulary for the match.  If the "vocabulary_language"
  32 ** or L columnname is left unspecified or is an empty string, then no
  33 ** filtering of the vocabulary by language is performed.
  34 **
  35 ** For efficiency, it is essential that the vocabulary table be indexed:
  36 **
  37 **     CREATE vocab_index ON V(W)
  38 **
  39 ** A separate edit-cost-table provides scoring information that defines
  40 ** what it means for one string to be "close" to another.
  41 **
  42 ** The edit-cost-table must contain exactly four columns (more precisely,
  43 ** the statement "SELECT * FROM <edit-cost-table>" must return records
  44 ** that consist of four columns). It does not matter what the columns are
  45 ** named.
  46 **
  47 ** Each row in the edit-cost-table represents a single character
  48 ** transformation going from user input to the vocabulary. The leftmost
  49 ** column of the row (column 0) contains an integer identifier of the
  50 ** language to which the transformation rule belongs (see "MULTIPLE LANGUAGES"
  51 ** below). The second column of the row (column 1) contains the input
  52 ** character or characters - the characters of user input. The third
  53 ** column contains characters as they appear in the vocabulary table.
  54 ** And the fourth column contains the integer cost of making the
  55 ** transformation. For example:
  56 **
  57 **    CREATE TABLE f_data(iLang, cFrom, cTo, Cost);
  58 **    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, '', 'a', 100);
  59 **    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, 'b', '', 87);
  60 **    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, 'o', 'oe', 38);
  61 **    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, 'oe', 'o', 40);
  62 **
  63 ** The first row inserted into the edit-cost-table by the SQL script
  64 ** above indicates that the cost of having an extra 'a' in the vocabulary
  65 ** table that is missing in the user input 100.  (All costs are integers.
  66 ** Overall cost must not exceed 16777216.)  The second INSERT statement
  67 ** creates a rule saying that the cost of having a single letter 'b' in
  68 ** user input which is missing in the vocabulary table is 87.  The third
  69 ** INSERT statement mean that the cost of matching an 'o' in user input
  70 ** against an 'oe' in the vocabulary table is 38.  And so forth.
  71 **
  72 ** The following rules are special:
  73 **
  74 **    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, '?', '', 97);
  75 **    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, '', '?', 98);
  76 **    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, '?', '?', 99);
  77 **
  78 ** The '?' to '' rule is the cost of having any single character in the input
  79 ** that is not found in the vocabular.  The '' to '?' rule is the cost of
  80 ** having a character in the vocabulary table that is missing from input.
  81 ** And the '?' to '?' rule is the cost of doing an arbitrary character
  82 ** substitution.  These three generic rules apply across all languages.
  83 ** In other words, the iLang field is ignored for the generic substitution
  84 ** rules.  If more than one cost is given for a generic substitution rule,
  85 ** then the lowest cost is used.
  86 **
  87 ** Once it has been created, the amatch virtual table can be queried
  88 ** as follows:
  89 **
  90 **    SELECT word, distance FROM f
  91 **     WHERE word MATCH 'abcdefg'
  92 **       AND distance<200;
  93 **
  94 ** This query outputs the strings contained in the T(F) field that
  95 ** are close to "abcdefg" and in order of increasing distance.  No string
  96 ** is output more than once.  If there are multiple ways to transform the
  97 ** target string ("abcdefg") into a string in the vocabulary table then
  98 ** the lowest cost transform is the one that is returned.  In this example,
  99 ** the search is limited to strings with a total distance of less than 200.
 100 **
 101 ** For efficiency, it is important to put tight bounds on the distance.
 102 ** The time and memory space needed to perform this query is exponential
 103 ** in the maximum distance.  A good rule of thumb is to limit the distance
 104 ** to no more than 1.5 or 2 times the maximum cost of any rule in the
 105 ** edit-cost-table.
 106 **
 107 ** The amatch is a read-only table.  Any attempt to DELETE, INSERT, or
 108 ** UPDATE on a amatch table will throw an error.
 109 **
 110 ** It is important to put some kind of a limit on the amatch output.  This
 111 ** can be either in the form of a LIMIT clause at the end of the query,
 112 ** or better, a "distance<NNN" constraint where NNN is some number.  The
 113 ** running time and memory requirement is exponential in the value of NNN
 114 ** so you want to make sure that NNN is not too big.  A value of NNN that
 115 ** is about twice the average transformation cost seems to give good results.
 116 **
 117 ** The amatch table can be useful for tasks such as spelling correction.
 118 ** Suppose all allowed words are in table vocabulary(w).  Then one would create
 119 ** an amatch virtual table like this:
 120 **
 121 **   CREATE VIRTUAL TABLE ex1 USING amatch(
 122 **       vocabtable=vocabulary,
 123 **       vocabcolumn=w,
 124 **       edit_distances=ec1
 125 **   );
 126 **
 127 ** Then given an input word $word, look up close spellings this way:
 128 **
 129 **   SELECT word, distance FROM ex1
 130 **    WHERE word MATCH $word AND distance<200;
 131 **
 132 ** MULTIPLE LANGUAGES
 133 **
 134 ** Normally, the "iLang" value associated with all character transformations
 135 ** in the edit-cost-table is zero. However, if required, the amatch
 136 ** virtual table allows multiple languages to be defined. Each query uses
 137 ** only a single iLang value.   This allows, for example, a single
 138 ** amatch table to support multiple languages.
 139 **
 140 ** By default, only the rules with iLang=0 are used. To specify an
 141 ** alternative language, a "language = ?" expression must be added to the
 142 ** WHERE clause of a SELECT, where ? is the integer identifier of the desired
 143 ** language. For example:
 144 **
 145 **   SELECT word, distance FROM ex1
 146 **    WHERE word MATCH $word
 147 **      AND distance<=200
 148 **      AND language=1 -- Specify use language 1 instead of 0
 149 **
 150 ** If no "language = ?" constraint is specified in the WHERE clause, language
 151 ** 0 is used.
 152 **
 153 ** LIMITS
 154 **
 155 ** The maximum language number is 2147483647.  The maximum length of either
 156 ** of the strings in the second or third column of the amatch data table
 157 ** is 50 bytes.  The maximum cost on a rule is 1000.
 158 */
 159 #include "sqlite3ext.h"
 160 SQLITE_EXTENSION_INIT1
 161 #include <stdlib.h>
 162 #include <string.h>
 163 #include <assert.h>
 164 #include <stdio.h>
 165 #include <ctype.h>
 166
 167 #ifndef SQLITE_OMIT_VIRTUALTABLE
 168
 169 /*
 170 ** Forward declaration of objects used by this implementation
 171 */
 172 typedef struct amatch_vtab amatch_vtab;
 173 typedef struct amatch_cursor amatch_cursor;
 174 typedef struct amatch_rule amatch_rule;
 175 typedef struct amatch_word amatch_word;
 176 typedef struct amatch_avl amatch_avl;
 177
 178
 179 /*****************************************************************************
 180 ** AVL Tree implementation
 181 */
 182 /*
 183 ** Objects that want to be members of the AVL tree should embedded an
 184 ** instance of this structure.
 185 */
 186 struct amatch_avl {
 187   amatch_word *pWord;   /* Points to the object being stored in the tree */
 188   char *zKey;           /* Key.  zero-terminated string.  Must be unique */
 189   amatch_avl *pBefore;  /* Other elements less than zKey */
 190   amatch_avl *pAfter;   /* Other elements greater than zKey */
 191   amatch_avl *pUp;      /* Parent element */
 192   short int height;     /* Height of this node.  Leaf==1 */
 193   short int imbalance;  /* Height difference between pBefore and pAfter */
 194 };
 195
 196 /* Recompute the amatch_avl.height and amatch_avl.imbalance fields for p.
 197 ** Assume that the children of p have correct heights.
 198 */
 199 static void amatchAvlRecomputeHeight(amatch_avl *p){
 200   short int hBefore = p->pBefore ? p->pBefore->height : 0;
 201   short int hAfter = p->pAfter ? p->pAfter->height : 0;
 202   p->imbalance = hBefore - hAfter;  /* -: pAfter higher.  +: pBefore higher */
 203   p->height = (hBefore>hAfter ? hBefore : hAfter)+1;
 204 }
 205
 206 /*
 207 **     P                B
 208 **    / \              / \
 209 **   B   Z    ==>     X   P
 210 **  / \                  / \
 211 ** X   Y                Y   Z
 212 **
 213 */
 214 static amatch_avl *amatchAvlRotateBefore(amatch_avl *pP){
 215   amatch_avl *pB = pP->pBefore;
 216   amatch_avl *pY = pB->pAfter;
 217   pB->pUp = pP->pUp;
 218   pB->pAfter = pP;
 219   pP->pUp = pB;
 220   pP->pBefore = pY;
 221   if( pY ) pY->pUp = pP;
 222   amatchAvlRecomputeHeight(pP);
 223   amatchAvlRecomputeHeight(pB);
 224   return pB;
 225 }
 226
 227 /*
 228 **     P                A
 229 **    / \              / \
 230 **   X   A    ==>     P   Z
 231 **      / \          / \
 232 **     Y   Z        X   Y
 233 **
 234 */
 235 static amatch_avl *amatchAvlRotateAfter(amatch_avl *pP){
 236   amatch_avl *pA = pP->pAfter;
 237   amatch_avl *pY = pA->pBefore;
 238   pA->pUp = pP->pUp;
 239   pA->pBefore = pP;
 240   pP->pUp = pA;
 241   pP->pAfter = pY;
 242   if( pY ) pY->pUp = pP;
 243   amatchAvlRecomputeHeight(pP);
 244   amatchAvlRecomputeHeight(pA);
 245   return pA;
 246 }
 247
 248 /*
 249 ** Return a pointer to the pBefore or pAfter pointer in the parent
 250 ** of p that points to p.  Or if p is the root node, return pp.
 251 */
 252 static amatch_avl **amatchAvlFromPtr(amatch_avl *p, amatch_avl **pp){
 253   amatch_avl *pUp = p->pUp;
 254   if( pUp==0 ) return pp;
 255   if( pUp->pAfter==p ) return &pUp->pAfter;
 256   return &pUp->pBefore;
 257 }
 258
 259 /*
 260 ** Rebalance all nodes starting with p and working up to the root.
 261 ** Return the new root.
 262 */
 263 static amatch_avl *amatchAvlBalance(amatch_avl *p){
 264   amatch_avl *pTop = p;
 265   amatch_avl **pp;
 266   while( p ){
 267     amatchAvlRecomputeHeight(p);
 268     if( p->imbalance>=2 ){
 269       amatch_avl *pB = p->pBefore;
 270       if( pB->imbalance<0 ) p->pBefore = amatchAvlRotateAfter(pB);
 271       pp = amatchAvlFromPtr(p,&p);
 272       p = *pp = amatchAvlRotateBefore(p);
 273     }else if( p->imbalance<=(-2) ){
 274       amatch_avl *pA = p->pAfter;
 275       if( pA->imbalance>0 ) p->pAfter = amatchAvlRotateBefore(pA);
 276       pp = amatchAvlFromPtr(p,&p);
 277       p = *pp = amatchAvlRotateAfter(p);
 278     }
 279     pTop = p;
 280     p = p->pUp;
 281   }
 282   return pTop;
 283 }
 284
 285 /* Search the tree rooted at p for an entry with zKey.  Return a pointer
 286 ** to the entry or return NULL.
 287 */
 288 static amatch_avl *amatchAvlSearch(amatch_avl *p, const char *zKey){
 289   int c;
 290   while( p && (c = strcmp(zKey, p->zKey))!=0 ){
 291     p = (c<0) ? p->pBefore : p->pAfter;
 292   }
 293   return p;
 294 }
 295
 296 /* Find the first node (the one with the smallest key).
 297 */
 298 static amatch_avl *amatchAvlFirst(amatch_avl *p){
 299   if( p ) while( p->pBefore ) p = p->pBefore;
 300   return p;
 301 }
 302
 303 #if 0 /* NOT USED */
 304 /* Return the node with the next larger key after p.
 305 */
 306 static amatch_avl *amatchAvlNext(amatch_avl *p){
 307   amatch_avl *pPrev = 0;
 308   while( p && p->pAfter==pPrev ){
 309     pPrev = p;
 310     p = p->pUp;
 311   }
 312   if( p && pPrev==0 ){
 313     p = amatchAvlFirst(p->pAfter);
 314   }
 315   return p;
 316 }
 317 #endif
 318
 319 #if 0 /* NOT USED */
 320 /* Verify AVL tree integrity
 321 */
 322 static int amatchAvlIntegrity(amatch_avl *pHead){
 323   amatch_avl *p;
 324   if( pHead==0 ) return 1;
 325   if( (p = pHead->pBefore)!=0 ){
 326     assert( p->pUp==pHead );
 327     assert( amatchAvlIntegrity(p) );
 328     assert( strcmp(p->zKey, pHead->zKey)<0 );
 329     while( p->pAfter ) p = p->pAfter;
 330     assert( strcmp(p->zKey, pHead->zKey)<0 );
 331   }
 332   if( (p = pHead->pAfter)!=0 ){
 333     assert( p->pUp==pHead );
 334     assert( amatchAvlIntegrity(p) );
 335     assert( strcmp(p->zKey, pHead->zKey)>0 );
 336     p = amatchAvlFirst(p);
 337     assert( strcmp(p->zKey, pHead->zKey)>0 );
 338   }
 339   return 1;
 340 }
 341 static int amatchAvlIntegrity2(amatch_avl *pHead){
 342   amatch_avl *p, *pNext;
 343   for(p=amatchAvlFirst(pHead); p; p=pNext){
 344     pNext = amatchAvlNext(p);
 345     if( pNext==0 ) break;
 346     assert( strcmp(p->zKey, pNext->zKey)<0 );
 347   }
 348   return 1;
 349 }
 350 #endif
 351
 352 /* Insert a new node pNew.  Return NULL on success.  If the key is not
 353 ** unique, then do not perform the insert but instead leave pNew unchanged
 354 ** and return a pointer to an existing node with the same key.
 355 */
 356 static amatch_avl *amatchAvlInsert(amatch_avl **ppHead, amatch_avl *pNew){
 357   int c;
 358   amatch_avl *p = *ppHead;
 359   if( p==0 ){
 360     p = pNew;
 361     pNew->pUp = 0;
 362   }else{
 363     while( p ){
 364       c = strcmp(pNew->zKey, p->zKey);
 365       if( c<0 ){
 366         if( p->pBefore ){
 367           p = p->pBefore;
 368         }else{
 369           p->pBefore = pNew;
 370           pNew->pUp = p;
 371           break;
 372         }
 373       }else if( c>0 ){
 374         if( p->pAfter ){
 375           p = p->pAfter;
 376         }else{
 377           p->pAfter = pNew;
 378           pNew->pUp = p;
 379           break;
 380         }
 381       }else{
 382         return p;
 383       }
 384     }
 385   }
 386   pNew->pBefore = 0;
 387   pNew->pAfter = 0;
 388   pNew->height = 1;
 389   pNew->imbalance = 0;
 390   *ppHead = amatchAvlBalance(p);
 391   /* assert( amatchAvlIntegrity(*ppHead) ); */
 392   /* assert( amatchAvlIntegrity2(*ppHead) ); */
 393   return 0;
 394 }
 395
 396 /* Remove node pOld from the tree.  pOld must be an element of the tree or
 397 ** the AVL tree will become corrupt.
 398 */
 399 static void amatchAvlRemove(amatch_avl **ppHead, amatch_avl *pOld){
 400   amatch_avl **ppParent;
 401   amatch_avl *pBalance = 0;
 402   /* assert( amatchAvlSearch(*ppHead, pOld->zKey)==pOld ); */
 403   ppParent = amatchAvlFromPtr(pOld, ppHead);
 404   if( pOld->pBefore==0 && pOld->pAfter==0 ){
 405     *ppParent = 0;
 406     pBalance = pOld->pUp;
 407   }else if( pOld->pBefore && pOld->pAfter ){
 408     amatch_avl *pX, *pY;
 409     pX = amatchAvlFirst(pOld->pAfter);
 410     *amatchAvlFromPtr(pX, 0) = pX->pAfter;
 411     if( pX->pAfter ) pX->pAfter->pUp = pX->pUp;
 412     pBalance = pX->pUp;
 413     pX->pAfter = pOld->pAfter;
 414     if( pX->pAfter ){
 415       pX->pAfter->pUp = pX;
 416     }else{
 417       assert( pBalance==pOld );
 418       pBalance = pX;
 419     }
 420     pX->pBefore = pY = pOld->pBefore;
 421     if( pY ) pY->pUp = pX;
 422     pX->pUp = pOld->pUp;
 423     *ppParent = pX;
 424   }else if( pOld->pBefore==0 ){
 425     *ppParent = pBalance = pOld->pAfter;
 426     pBalance->pUp = pOld->pUp;
 427   }else if( pOld->pAfter==0 ){
 428     *ppParent = pBalance = pOld->pBefore;
 429     pBalance->pUp = pOld->pUp;
 430   }
 431   *ppHead = amatchAvlBalance(pBalance);
 432   pOld->pUp = 0;
 433   pOld->pBefore = 0;
 434   pOld->pAfter = 0;
 435   /* assert( amatchAvlIntegrity(*ppHead) ); */
 436   /* assert( amatchAvlIntegrity2(*ppHead) ); */
 437 }
 438 /*
 439 ** End of the AVL Tree implementation
 440 ******************************************************************************/
 441
 442
 443 /*
 444 ** Various types.
 445 **
 446 ** amatch_cost is the "cost" of an edit operation.
 447 **
 448 ** amatch_len is the length of a matching string.
 449 **
 450 ** amatch_langid is an ruleset identifier.
 451 */
 452 typedef int amatch_cost;
 453 typedef signed char amatch_len;
 454 typedef int amatch_langid;
 455
 456 /*
 457 ** Limits
 458 */
 459 #define AMATCH_MX_LENGTH          50  /* Maximum length of a rule string */
 460 #define AMATCH_MX_LANGID  2147483647  /* Maximum rule ID */
 461 #define AMATCH_MX_COST          1000  /* Maximum single-rule cost */
 462
 463 /*
 464 ** A match or partial match
 465 */
 466 struct amatch_word {
 467   amatch_word *pNext;   /* Next on a list of all amatch_words */
 468   amatch_avl sCost;     /* Linkage of this node into the cost tree */
 469   amatch_avl sWord;     /* Linkage of this node into the word tree */
 470   amatch_cost rCost;    /* Cost of the match so far */
 471   int iSeq;             /* Sequence number */
 472   char zCost[10];       /* Cost key (text rendering of rCost) */
 473   short int nMatch;     /* Input characters matched */
 474   char zWord[4];        /* Text of the word.  Extra space appended as needed */
 475 };
 476
 477 /*
 478 ** Each transformation rule is stored as an instance of this object.
 479 ** All rules are kept on a linked list sorted by rCost.
 480 */
 481 struct amatch_rule {
 482   amatch_rule *pNext;      /* Next rule in order of increasing rCost */
 483   char *zFrom;             /* Transform from (a string from user input) */
 484   amatch_cost rCost;       /* Cost of this transformation */
 485   amatch_langid iLang;     /* The langauge to which this rule belongs */
 486   amatch_len nFrom, nTo;   /* Length of the zFrom and zTo strings */
 487   char zTo[4];             /* Tranform to V.W value (extra space appended) */
 488 };
 489
 490 /*
 491 ** A amatch virtual-table object
 492 */
 493 struct amatch_vtab {
 494   sqlite3_vtab base;         /* Base class - must be first */
 495   char *zClassName;          /* Name of this class.  Default: "amatch" */
 496   char *zDb;                 /* Name of database.  (ex: "main") */
 497   char *zSelf;               /* Name of this virtual table */
 498   char *zCostTab;            /* Name of edit-cost-table */
 499   char *zVocabTab;           /* Name of vocabulary table */
 500   char *zVocabWord;          /* Name of vocabulary table word column */
 501   char *zVocabLang;          /* Name of vocabulary table language column */
 502   amatch_rule *pRule;        /* All active rules in this amatch */
 503   amatch_cost rIns;          /* Generic insertion cost  '' -> ? */
 504   amatch_cost rDel;          /* Generic deletion cost  ? -> '' */
 505   amatch_cost rSub;          /* Generic substitution cost ? -> ? */
 506   sqlite3 *db;               /* The database connection */
 507   sqlite3_stmt *pVCheck;     /* Query to check zVocabTab */
 508   int nCursor;               /* Number of active cursors */
 509 };
 510
 511 /* A amatch cursor object */
 512 struct amatch_cursor {
 513   sqlite3_vtab_cursor base;  /* Base class - must be first */
 514   sqlite3_int64 iRowid;      /* The rowid of the current word */
 515   amatch_langid iLang;       /* Use this language ID */
 516   amatch_cost rLimit;        /* Maximum cost of any term */
 517   int nBuf;                  /* Space allocated for zBuf */
 518   int oomErr;                /* True following an OOM error */
 519   int nWord;                 /* Number of amatch_word objects */
 520   char *zBuf;                /* Temp-use buffer space */
 521   char *zInput;              /* Input word to match against */
 522   amatch_vtab *pVtab;        /* The virtual table this cursor belongs to */
 523   amatch_word *pAllWords;    /* List of all amatch_word objects */
 524   amatch_word *pCurrent;     /* Most recent solution */
 525   amatch_avl *pCost;         /* amatch_word objects keyed by iCost */
 526   amatch_avl *pWord;         /* amatch_word objects keyed by zWord */
 527 };
 528
 529 /*
 530 ** The two input rule lists are both sorted in order of increasing
 531 ** cost.  Merge them together into a single list, sorted by cost, and
 532 ** return a pointer to the head of that list.
 533 */
 534 static amatch_rule *amatchMergeRules(amatch_rule *pA, amatch_rule *pB){
 535   amatch_rule head;
 536   amatch_rule *pTail;
 537
 538   pTail =  &head;
 539   while( pA && pB ){
 540     if( pA->rCost<=pB->rCost ){
 541       pTail->pNext = pA;
 542       pTail = pA;
 543       pA = pA->pNext;
 544     }else{
 545       pTail->pNext = pB;
 546       pTail = pB;
 547       pB = pB->pNext;
 548     }
 549   }
 550   if( pA==0 ){
 551     pTail->pNext = pB;
 552   }else{
 553     pTail->pNext = pA;
 554   }
 555   return head.pNext;
 556 }
 557
 558 /*
 559 ** Statement pStmt currently points to a row in the amatch data table. This
 560 ** function allocates and populates a amatch_rule structure according to
 561 ** the content of the row.
 562 **
 563 ** If successful, *ppRule is set to point to the new object and SQLITE_OK
 564 ** is returned. Otherwise, *ppRule is zeroed, *pzErr may be set to point
 565 ** to an error message and an SQLite error code returned.
 566 */
 567 static int amatchLoadOneRule(
 568   amatch_vtab *p,                 /* Fuzzer virtual table handle */
 569   sqlite3_stmt *pStmt,            /* Base rule on statements current row */
 570   amatch_rule **ppRule,           /* OUT: New rule object */
 571   char **pzErr                    /* OUT: Error message */
 572 ){
 573   sqlite3_int64 iLang = sqlite3_column_int64(pStmt, 0);
 574   const char *zFrom = (const char *)sqlite3_column_text(pStmt, 1);
 575   const char *zTo = (const char *)sqlite3_column_text(pStmt, 2);
 576   amatch_cost rCost = sqlite3_column_int(pStmt, 3);
 577
 578   int rc = SQLITE_OK;             /* Return code */
 579   int nFrom;                      /* Size of string zFrom, in bytes */
 580   int nTo;                        /* Size of string zTo, in bytes */
 581   amatch_rule *pRule = 0;         /* New rule object to return */
 582
 583   if( zFrom==0 ) zFrom = "";
 584   if( zTo==0 ) zTo = "";
 585   nFrom = (int)strlen(zFrom);
 586   nTo = (int)strlen(zTo);
 587
 588   /* Silently ignore null transformations */
 589   if( strcmp(zFrom, zTo)==0 ){
 590     if( zFrom[0]=='?' && zFrom[1]==0 ){
 591       if( p->rSub==0 || p->rSub>rCost ) p->rSub = rCost;
 592     }
 593     *ppRule = 0;
 594     return SQLITE_OK;
 595   }
 596
 597   if( rCost<=0 || rCost>AMATCH_MX_COST ){
 598     *pzErr = sqlite3_mprintf("%s: cost must be between 1 and %d",
 599         p->zClassName, AMATCH_MX_COST
 600     );
 601     rc = SQLITE_ERROR;
 602   }else
 603   if( nFrom>AMATCH_MX_LENGTH || nTo>AMATCH_MX_LENGTH ){
 604     *pzErr = sqlite3_mprintf("%s: maximum string length is %d",
 605         p->zClassName, AMATCH_MX_LENGTH
 606     );
 607     rc = SQLITE_ERROR;
 608   }else
 609   if( iLang<0 || iLang>AMATCH_MX_LANGID ){
 610     *pzErr = sqlite3_mprintf("%s: iLang must be between 0 and %d",
 611         p->zClassName, AMATCH_MX_LANGID
 612     );
 613     rc = SQLITE_ERROR;
 614   }else
 615   if( strcmp(zFrom,"")==0 && strcmp(zTo,"?")==0 ){
 616     if( p->rIns==0 || p->rIns>rCost ) p->rIns = rCost;
 617   }else
 618   if( strcmp(zFrom,"?")==0 && strcmp(zTo,"")==0 ){
 619     if( p->rDel==0 || p->rDel>rCost ) p->rDel = rCost;
 620   }else
 621   {
 622     pRule = sqlite3_malloc( sizeof(*pRule) + nFrom + nTo );
 623     if( pRule==0 ){
 624       rc = SQLITE_NOMEM;
 625     }else{
 626       memset(pRule, 0, sizeof(*pRule));
 627       pRule->zFrom = &pRule->zTo[nTo+1];
 628       pRule->nFrom = (amatch_len)nFrom;
 629       memcpy(pRule->zFrom, zFrom, nFrom+1);
 630       memcpy(pRule->zTo, zTo, nTo+1);
 631       pRule->nTo = (amatch_len)nTo;
 632       pRule->rCost = rCost;
 633       pRule->iLang = (int)iLang;
 634     }
 635   }
 636
 637   *ppRule = pRule;
 638   return rc;
 639 }
 640
 641 /*
 642 ** Free all the content in the edit-cost-table
 643 */
 644 static void amatchFreeRules(amatch_vtab *p){
 645   while( p->pRule ){
 646     amatch_rule *pRule = p->pRule;
 647     p->pRule = pRule->pNext;
 648     sqlite3_free(pRule);
 649   }
 650   p->pRule = 0;
 651 }
 652
 653 /*
 654 ** Load the content of the amatch data table into memory.
 655 */
 656 static int amatchLoadRules(
 657   sqlite3 *db,                    /* Database handle */
 658   amatch_vtab *p,                 /* Virtual amatch table to configure */
 659   char **pzErr                    /* OUT: Error message */
 660 ){
 661   int rc = SQLITE_OK;             /* Return code */
 662   char *zSql;                     /* SELECT used to read from rules table */
 663   amatch_rule *pHead = 0;
 664
 665   zSql = sqlite3_mprintf("SELECT * FROM %Q.%Q", p->zDb, p->zCostTab);
 666   if( zSql==0 ){
 667     rc = SQLITE_NOMEM;
 668   }else{
 669     int rc2;                      /* finalize() return code */
 670     sqlite3_stmt *pStmt = 0;
 671     rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0);
 672     if( rc!=SQLITE_OK ){
 673       *pzErr = sqlite3_mprintf("%s: %s", p->zClassName, sqlite3_errmsg(db));
 674     }else if( sqlite3_column_count(pStmt)!=4 ){
 675       *pzErr = sqlite3_mprintf("%s: %s has %d columns, expected 4",
 676           p->zClassName, p->zCostTab, sqlite3_column_count(pStmt)
 677       );
 678       rc = SQLITE_ERROR;
 679     }else{
 680       while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pStmt) ){
 681         amatch_rule *pRule = 0;
 682         rc = amatchLoadOneRule(p, pStmt, &pRule, pzErr);
 683         if( pRule ){
 684           pRule->pNext = pHead;
 685           pHead = pRule;
 686         }
 687       }
 688     }
 689     rc2 = sqlite3_finalize(pStmt);
 690     if( rc==SQLITE_OK ) rc = rc2;
 691   }
 692   sqlite3_free(zSql);
 693
 694   /* All rules are now in a singly linked list starting at pHead. This
 695   ** block sorts them by cost and then sets amatch_vtab.pRule to point to
 696   ** point to the head of the sorted list.
 697   */
 698   if( rc==SQLITE_OK ){
 699     unsigned int i;
 700     amatch_rule *pX;
 701     amatch_rule *a[15];
 702     for(i=0; i<sizeof(a)/sizeof(a[0]); i++) a[i] = 0;
 703     while( (pX = pHead)!=0 ){
 704       pHead = pX->pNext;
 705       pX->pNext = 0;
 706       for(i=0; a[i] && i<sizeof(a)/sizeof(a[0])-1; i++){
 707         pX = amatchMergeRules(a[i], pX);
 708         a[i] = 0;
 709       }
 710       a[i] = amatchMergeRules(a[i], pX);
 711     }
 712     for(pX=a[0], i=1; i<sizeof(a)/sizeof(a[0]); i++){
 713       pX = amatchMergeRules(a[i], pX);
 714     }
 715     p->pRule = amatchMergeRules(p->pRule, pX);
 716   }else{
 717     /* An error has occurred. Setting p->pRule to point to the head of the
 718     ** allocated list ensures that the list will be cleaned up in this case.
 719     */
 720     assert( p->pRule==0 );
 721     p->pRule = pHead;
 722   }
 723
 724   return rc;
 725 }
 726
 727 /*
 728 ** This function converts an SQL quoted string into an unquoted string
 729 ** and returns a pointer to a buffer allocated using sqlite3_malloc()
 730 ** containing the result. The caller should eventually free this buffer
 731 ** using sqlite3_free.
 732 **
 733 ** Examples:
 734 **
 735 **     "abc"   becomes   abc
 736 **     'xyz'   becomes   xyz
 737 **     [pqr]   becomes   pqr
 738 **     `mno`   becomes   mno
 739 */
 740 static char *amatchDequote(const char *zIn){
 741   int nIn;                        /* Size of input string, in bytes */
 742   char *zOut;                     /* Output (dequoted) string */
 743
 744   nIn = (int)strlen(zIn);
 745   zOut = sqlite3_malloc(nIn+1);
 746   if( zOut ){
 747     char q = zIn[0];              /* Quote character (if any ) */
 748
 749     if( q!='[' && q!= '\'' && q!='"' && q!='`' ){
 750       memcpy(zOut, zIn, nIn+1);
 751     }else{
 752       int iOut = 0;               /* Index of next byte to write to output */
 753       int iIn;                    /* Index of next byte to read from input */
 754
 755       if( q=='[' ) q = ']';
 756       for(iIn=1; iIn<nIn; iIn++){
 757         if( zIn[iIn]==q ) iIn++;
 758         zOut[iOut++] = zIn[iIn];
 759       }
 760     }
 761     assert( (int)strlen(zOut)<=nIn );
 762   }
 763   return zOut;
 764 }
 765
 766 /*
 767 ** Deallocate the pVCheck prepared statement.
 768 */
 769 static void amatchVCheckClear(amatch_vtab *p){
 770   if( p->pVCheck ){
 771     sqlite3_finalize(p->pVCheck);
 772     p->pVCheck = 0;
 773   }
 774 }
 775
 776 /*
 777 ** Deallocate an amatch_vtab object
 778 */
 779 static void amatchFree(amatch_vtab *p){
 780   if( p ){
 781     amatchFreeRules(p);
 782     amatchVCheckClear(p);
 783     sqlite3_free(p->zClassName);
 784     sqlite3_free(p->zDb);
 785     sqlite3_free(p->zCostTab);
 786     sqlite3_free(p->zVocabTab);
 787     sqlite3_free(p->zVocabWord);
 788     sqlite3_free(p->zVocabLang);
 789     sqlite3_free(p->zSelf);
 790     memset(p, 0, sizeof(*p));
 791     sqlite3_free(p);
 792   }
 793 }
 794
 795 /*
 796 ** xDisconnect/xDestroy method for the amatch module.
 797 */
 798 static int amatchDisconnect(sqlite3_vtab *pVtab){
 799   amatch_vtab *p = (amatch_vtab*)pVtab;
 800   assert( p->nCursor==0 );
 801   amatchFree(p);
 802   return SQLITE_OK;
 803 }
 804
 805 /*
 806 ** Check to see if the argument is of the form:
 807 **
 808 **       KEY = VALUE
 809 **
 810 ** If it is, return a pointer to the first character of VALUE.
 811 ** If not, return NULL.  Spaces around the = are ignored.
 812 */
 813 static const char *amatchValueOfKey(const char *zKey, const char *zStr){
 814   int nKey = (int)strlen(zKey);
 815   int nStr = (int)strlen(zStr);
 816   int i;
 817   if( nStr<nKey+1 ) return 0;
 818   if( memcmp(zStr, zKey, nKey)!=0 ) return 0;
 819   for(i=nKey; isspace((unsigned char)zStr[i]); i++){}
 820   if( zStr[i]!='=' ) return 0;
 821   i++;
 822   while( isspace((unsigned char)zStr[i]) ){ i++; }
 823   return zStr+i;
 824 }
 825
 826 /*
 827 ** xConnect/xCreate method for the amatch module. Arguments are:
 828 **
 829 **   argv[0]    -> module name  ("approximate_match")
 830 **   argv[1]    -> database name
 831 **   argv[2]    -> table name
 832 **   argv[3...] -> arguments
 833 */
 834 static int amatchConnect(
 835   sqlite3 *db,
 836   void *pAux,
 837   int argc, const char *const*argv,
 838   sqlite3_vtab **ppVtab,
 839   char **pzErr
 840 ){
 841   int rc = SQLITE_OK;             /* Return code */
 842   amatch_vtab *pNew = 0;          /* New virtual table */
 843   const char *zModule = argv[0];
 844   const char *zDb = argv[1];
 845   const char *zVal;
 846   int i;
 847
 848   (void)pAux;
 849   *ppVtab = 0;
 850   pNew = sqlite3_malloc( sizeof(*pNew) );
 851   if( pNew==0 ) return SQLITE_NOMEM;
 852   rc = SQLITE_NOMEM;
 853   memset(pNew, 0, sizeof(*pNew));
 854   pNew->db = db;
 855   pNew->zClassName = sqlite3_mprintf("%s", zModule);
 856   if( pNew->zClassName==0 ) goto amatchConnectError;
 857   pNew->zDb = sqlite3_mprintf("%s", zDb);
 858   if( pNew->zDb==0 ) goto amatchConnectError;
 859   pNew->zSelf = sqlite3_mprintf("%s", argv[2]);
 860   if( pNew->zSelf==0 ) goto amatchConnectError;
 861   for(i=3; i<argc; i++){
 862     zVal = amatchValueOfKey("vocabulary_table", argv[i]);
 863     if( zVal ){
 864       sqlite3_free(pNew->zVocabTab);
 865       pNew->zVocabTab = amatchDequote(zVal);
 866       if( pNew->zVocabTab==0 ) goto amatchConnectError;
 867       continue;
 868     }
 869     zVal = amatchValueOfKey("vocabulary_word", argv[i]);
 870     if( zVal ){
 871       sqlite3_free(pNew->zVocabWord);
 872       pNew->zVocabWord = amatchDequote(zVal);
 873       if( pNew->zVocabWord==0 ) goto amatchConnectError;
 874       continue;
 875     }
 876     zVal = amatchValueOfKey("vocabulary_language", argv[i]);
 877     if( zVal ){
 878       sqlite3_free(pNew->zVocabLang);
 879       pNew->zVocabLang = amatchDequote(zVal);
 880       if( pNew->zVocabLang==0 ) goto amatchConnectError;
 881       continue;
 882     }
 883     zVal = amatchValueOfKey("edit_distances", argv[i]);
 884     if( zVal ){
 885       sqlite3_free(pNew->zCostTab);
 886       pNew->zCostTab = amatchDequote(zVal);
 887       if( pNew->zCostTab==0 ) goto amatchConnectError;
 888       continue;
 889     }
 890     *pzErr = sqlite3_mprintf("unrecognized argument: [%s]\n", argv[i]);
 891     amatchFree(pNew);
 892     *ppVtab = 0;
 893     return SQLITE_ERROR;
 894   }
 895   rc = SQLITE_OK;
 896   if( pNew->zCostTab==0 ){
 897     *pzErr = sqlite3_mprintf("no edit_distances table specified");
 898     rc = SQLITE_ERROR;
 899   }else{
 900     rc = amatchLoadRules(db, pNew, pzErr);
 901   }
 902   if( rc==SQLITE_OK ){
 903     rc = sqlite3_declare_vtab(db,
 904            "CREATE TABLE x(word,distance,language,"
 905            "command HIDDEN,nword HIDDEN)"
 906          );
 907 #define AMATCH_COL_WORD       0
 908 #define AMATCH_COL_DISTANCE   1
 909 #define AMATCH_COL_LANGUAGE   2
 910 #define AMATCH_COL_COMMAND    3
 911 #define AMATCH_COL_NWORD      4
 912   }
 913   if( rc!=SQLITE_OK ){
 914     amatchFree(pNew);
 915   }
 916   *ppVtab = &pNew->base;
 917   return rc;
 918
 919 amatchConnectError:
 920   amatchFree(pNew);
 921   return rc;
 922 }
 923
 924 /*
 925 ** Open a new amatch cursor.
 926 */
 927 static int amatchOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
 928   amatch_vtab *p = (amatch_vtab*)pVTab;
 929   amatch_cursor *pCur;
 930   pCur = sqlite3_malloc( sizeof(*pCur) );
 931   if( pCur==0 ) return SQLITE_NOMEM;
 932   memset(pCur, 0, sizeof(*pCur));
 933   pCur->pVtab = p;
 934   *ppCursor = &pCur->base;
 935   p->nCursor++;
 936   return SQLITE_OK;
 937 }
 938
 939 /*
 940 ** Free up all the memory allocated by a cursor.  Set it rLimit to 0
 941 ** to indicate that it is at EOF.
 942 */
 943 static void amatchClearCursor(amatch_cursor *pCur){
 944   amatch_word *pWord, *pNextWord;
 945   for(pWord=pCur->pAllWords; pWord; pWord=pNextWord){
 946     pNextWord = pWord->pNext;
 947     sqlite3_free(pWord);
 948   }
 949   pCur->pAllWords = 0;
 950   sqlite3_free(pCur->zInput);
 951   pCur->zInput = 0;
 952   sqlite3_free(pCur->zBuf);
 953   pCur->zBuf = 0;
 954   pCur->nBuf = 0;
 955   pCur->pCost = 0;
 956   pCur->pWord = 0;
 957   pCur->pCurrent = 0;
 958   pCur->rLimit = 1000000;
 959   pCur->iLang = 0;
 960   pCur->nWord = 0;
 961 }
 962
 963 /*
 964 ** Close a amatch cursor.
 965 */
 966 static int amatchClose(sqlite3_vtab_cursor *cur){
 967   amatch_cursor *pCur = (amatch_cursor *)cur;
 968   amatchClearCursor(pCur);
 969   pCur->pVtab->nCursor--;
 970   sqlite3_free(pCur);
 971   return SQLITE_OK;
 972 }
 973
 974 /*
 975 ** Render a 24-bit unsigned integer as a 4-byte base-64 number.
 976 */
 977 static void amatchEncodeInt(int x, char *z){
 978   static const char a[] =
 979     "0123456789"
 980     "ABCDEFGHIJ"
 981     "KLMNOPQRST"
 982     "UVWXYZ^abc"
 983     "defghijklm"
 984     "nopqrstuvw"
 985     "xyz~";
 986   z[0] = a[(x>>18)&0x3f];
 987   z[1] = a[(x>>12)&0x3f];
 988   z[2] = a[(x>>6)&0x3f];
 989   z[3] = a[x&0x3f];
 990 }
 991
 992 /*
 993 ** Write the zCost[] field for a amatch_word object
 994 */
 995 static void amatchWriteCost(amatch_word *pWord){
 996   amatchEncodeInt(pWord->rCost, pWord->zCost);
 997   amatchEncodeInt(pWord->iSeq, pWord->zCost+4);
 998   pWord->zCost[8] = 0;
 999 }
1000
1001 /* Circumvent compiler warnings about the use of strcpy() by supplying
1002 ** our own implementation.
1003 */
1004 static void amatchStrcpy(char *dest, const char *src){
1005   while( (*(dest++) = *(src++))!=0 ){}
1006 }
1007 static void amatchStrcat(char *dest, const char *src){
1008   while( *dest ) dest++;
1009   amatchStrcpy(dest, src);
1010 }
1011
1012 /*
1013 ** Add a new amatch_word object to the queue.
1014 **
1015 ** If a prior amatch_word object with the same zWord, and nMatch
1016 ** already exists, update its rCost (if the new rCost is less) but
1017 ** otherwise leave it unchanged.  Do not add a duplicate.
1018 **
1019 ** Do nothing if the cost exceeds threshold.
1020 */
1021 static void amatchAddWord(
1022   amatch_cursor *pCur,
1023   amatch_cost rCost,
1024   int nMatch,
1025   const char *zWordBase,
1026   const char *zWordTail
1027 ){
1028   amatch_word *pWord;
1029   amatch_avl *pNode;
1030   amatch_avl *pOther;
1031   int nBase, nTail;
1032   char zBuf[4];
1033
1034   if( rCost>pCur->rLimit ){
1035     return;
1036   }
1037   nBase = (int)strlen(zWordBase);
1038   nTail = (int)strlen(zWordTail);
1039   if( nBase+nTail+3>pCur->nBuf ){
1040     pCur->nBuf = nBase+nTail+100;
1041     pCur->zBuf = sqlite3_realloc(pCur->zBuf, pCur->nBuf);
1042     if( pCur->zBuf==0 ){
1043       pCur->nBuf = 0;
1044       return;
1045     }
1046   }
1047   amatchEncodeInt(nMatch, zBuf);
1048   memcpy(pCur->zBuf, zBuf+2, 2);
1049   memcpy(pCur->zBuf+2, zWordBase, nBase);
1050   memcpy(pCur->zBuf+2+nBase, zWordTail, nTail+1);
1051   pNode = amatchAvlSearch(pCur->pWord, pCur->zBuf);
1052   if( pNode ){
1053     pWord = pNode->pWord;
1054     if( pWord->rCost>rCost ){
1055 #ifdef AMATCH_TRACE_1
1056       printf("UPDATE [%s][%.*s^%s] %d (\"%s\" \"%s\")\n",
1057              pWord->zWord+2, pWord->nMatch, pCur->zInput, pCur->zInput,
1058              pWord->rCost, pWord->zWord, pWord->zCost);
1059 #endif
1060       amatchAvlRemove(&pCur->pCost, &pWord->sCost);
1061       pWord->rCost = rCost;
1062       amatchWriteCost(pWord);
1063 #ifdef AMATCH_TRACE_1
1064       printf("  ---> %d (\"%s\" \"%s\")\n",
1065              pWord->rCost, pWord->zWord, pWord->zCost);
1066 #endif
1067       pOther = amatchAvlInsert(&pCur->pCost, &pWord->sCost);
1068       assert( pOther==0 ); (void)pOther;
1069     }
1070     return;
1071   }
1072   pWord = sqlite3_malloc( sizeof(*pWord) + nBase + nTail - 1 );
1073   if( pWord==0 ) return;
1074   memset(pWord, 0, sizeof(*pWord));
1075   pWord->rCost = rCost;
1076   pWord->iSeq = pCur->nWord++;
1077   amatchWriteCost(pWord);
1078   pWord->nMatch = (short)nMatch;
1079   pWord->pNext = pCur->pAllWords;
1080   pCur->pAllWords = pWord;
1081   pWord->sCost.zKey = pWord->zCost;
1082   pWord->sCost.pWord = pWord;
1083   pOther = amatchAvlInsert(&pCur->pCost, &pWord->sCost);
1084   assert( pOther==0 ); (void)pOther;
1085   pWord->sWord.zKey = pWord->zWord;
1086   pWord->sWord.pWord = pWord;
1087   amatchStrcpy(pWord->zWord, pCur->zBuf);
1088   pOther = amatchAvlInsert(&pCur->pWord, &pWord->sWord);
1089   assert( pOther==0 ); (void)pOther;
1090 #ifdef AMATCH_TRACE_1
1091   printf("INSERT [%s][%.*s^%s] %d (\"%s\" \"%s\")\n", pWord->zWord+2,
1092        pWord->nMatch, pCur->zInput, pCur->zInput+pWord->nMatch, rCost,
1093        pWord->zWord, pWord->zCost);
1094 #endif
1095 }
1096
1097
1098 /*
1099 ** Advance a cursor to its next row of output
1100 */
1101 static int amatchNext(sqlite3_vtab_cursor *cur){
1102   amatch_cursor *pCur = (amatch_cursor*)cur;
1103   amatch_word *pWord = 0;
1104   amatch_avl *pNode;
1105   int isMatch = 0;
1106   amatch_vtab *p = pCur->pVtab;
1107   int nWord;
1108   int rc;
1109   int i;
1110   const char *zW;
1111   amatch_rule *pRule;
1112   char *zBuf = 0;
1113   char nBuf = 0;
1114   char zNext[8];
1115   char zNextIn[8];
1116   int nNextIn;
1117
1118   if( p->pVCheck==0 ){
1119     char *zSql;
1120     if( p->zVocabLang && p->zVocabLang[0] ){
1121       zSql = sqlite3_mprintf(
1122           "SELECT \"%w\" FROM \"%w\"",
1123           " WHERE \"%w\">=?1 AND \"%w\"=?2"
1124           " ORDER BY 1",
1125           p->zVocabWord, p->zVocabTab,
1126           p->zVocabWord, p->zVocabLang
1127       );
1128     }else{
1129       zSql = sqlite3_mprintf(
1130           "SELECT \"%w\" FROM \"%w\""
1131           " WHERE \"%w\">=?1"
1132           " ORDER BY 1",
1133           p->zVocabWord, p->zVocabTab,
1134           p->zVocabWord
1135       );
1136     }
1137     rc = sqlite3_prepare_v2(p->db, zSql, -1, &p->pVCheck, 0);
1138     sqlite3_free(zSql);
1139     if( rc ) return rc;
1140   }
1141   sqlite3_bind_int(p->pVCheck, 2, pCur->iLang);
1142
1143   do{
1144     pNode = amatchAvlFirst(pCur->pCost);
1145     if( pNode==0 ){
1146       pWord = 0;
1147       break;
1148     }
1149     pWord = pNode->pWord;
1150     amatchAvlRemove(&pCur->pCost, &pWord->sCost);
1151
1152 #ifdef AMATCH_TRACE_1
1153     printf("PROCESS [%s][%.*s^%s] %d (\"%s\" \"%s\")\n",
1154        pWord->zWord+2, pWord->nMatch, pCur->zInput, pCur->zInput+pWord->nMatch,
1155        pWord->rCost, pWord->zWord, pWord->zCost);
1156 #endif
1157     nWord = (int)strlen(pWord->zWord+2);
1158     if( nWord+20>nBuf ){
1159       nBuf = (char)(nWord+100);
1160       zBuf = sqlite3_realloc(zBuf, nBuf);
1161       if( zBuf==0 ) return SQLITE_NOMEM;
1162     }
1163     amatchStrcpy(zBuf, pWord->zWord+2);
1164     zNext[0] = 0;
1165     zNextIn[0] = pCur->zInput[pWord->nMatch];
1166     if( zNextIn[0] ){
1167       for(i=1; i<=4 && (pCur->zInput[pWord->nMatch+i]&0xc0)==0x80; i++){
1168         zNextIn[i] = pCur->zInput[pWord->nMatch+i];
1169       }
1170       zNextIn[i] = 0;
1171       nNextIn = i;
1172     }else{
1173       nNextIn = 0;
1174     }
1175
1176     if( zNextIn[0] && zNextIn[0]!='*' ){
1177       sqlite3_reset(p->pVCheck);
1178       amatchStrcat(zBuf, zNextIn);
1179       sqlite3_bind_text(p->pVCheck, 1, zBuf, nWord+nNextIn, SQLITE_STATIC);
1180       rc = sqlite3_step(p->pVCheck);
1181       if( rc==SQLITE_ROW ){
1182         zW = (const char*)sqlite3_column_text(p->pVCheck, 0);
1183         if( strncmp(zBuf, zW, nWord+nNextIn)==0 ){
1184           amatchAddWord(pCur, pWord->rCost, pWord->nMatch+nNextIn, zBuf, "");
1185         }
1186       }
1187       zBuf[nWord] = 0;
1188     }
1189
1190     while( 1 ){
1191       amatchStrcpy(zBuf+nWord, zNext);
1192       sqlite3_reset(p->pVCheck);
1193       sqlite3_bind_text(p->pVCheck, 1, zBuf, -1, SQLITE_TRANSIENT);
1194       rc = sqlite3_step(p->pVCheck);
1195       if( rc!=SQLITE_ROW ) break;
1196       zW = (const char*)sqlite3_column_text(p->pVCheck, 0);
1197       amatchStrcpy(zBuf+nWord, zNext);
1198       if( strncmp(zW, zBuf, nWord)!=0 ) break;
1199       if( (zNextIn[0]=='*' && zNextIn[1]==0)
1200        || (zNextIn[0]==0 && zW[nWord]==0)
1201       ){
1202         isMatch = 1;
1203         zNextIn[0] = 0;
1204         nNextIn = 0;
1205         break;
1206       }
1207       zNext[0] = zW[nWord];
1208       for(i=1; i<=4 && (zW[nWord+i]&0xc0)==0x80; i++){
1209         zNext[i] = zW[nWord+i];
1210       }
1211       zNext[i] = 0;
1212       zBuf[nWord] = 0;
1213       if( p->rIns>0 ){
1214         amatchAddWord(pCur, pWord->rCost+p->rIns, pWord->nMatch,
1215                       zBuf, zNext);
1216       }
1217       if( p->rSub>0 ){
1218         amatchAddWord(pCur, pWord->rCost+p->rSub, pWord->nMatch+nNextIn,
1219                       zBuf, zNext);
1220       }
1221       if( p->rIns<0 && p->rSub<0 ) break;
1222       zNext[i-1]++;  /* FIX ME */
1223     }
1224     sqlite3_reset(p->pVCheck);
1225
1226     if( p->rDel>0 ){
1227       zBuf[nWord] = 0;
1228       amatchAddWord(pCur, pWord->rCost+p->rDel, pWord->nMatch+nNextIn,
1229                     zBuf, "");
1230     }
1231
1232     for(pRule=p->pRule; pRule; pRule=pRule->pNext){
1233       if( pRule->iLang!=pCur->iLang ) continue;
1234       if( strncmp(pRule->zFrom, pCur->zInput+pWord->nMatch, pRule->nFrom)==0 ){
1235         amatchAddWord(pCur, pWord->rCost+pRule->rCost,
1236                       pWord->nMatch+pRule->nFrom, pWord->zWord+2, pRule->zTo);
1237       }
1238     }
1239   }while( !isMatch );
1240   pCur->pCurrent = pWord;
1241   sqlite3_free(zBuf);
1242   return SQLITE_OK;
1243 }
1244
1245 /*
1246 ** Called to "rewind" a cursor back to the beginning so that
1247 ** it starts its output over again.  Always called at least once
1248 ** prior to any amatchColumn, amatchRowid, or amatchEof call.
1249 */
1250 static int amatchFilter(
1251   sqlite3_vtab_cursor *pVtabCursor,
1252   int idxNum, const char *idxStr,
1253   int argc, sqlite3_value **argv
1254 ){
1255   amatch_cursor *pCur = (amatch_cursor *)pVtabCursor;
1256   const char *zWord = "*";
1257   int idx;
1258
1259   amatchClearCursor(pCur);
1260   idx = 0;
1261   if( idxNum & 1 ){
1262     zWord = (const char*)sqlite3_value_text(argv[0]);
1263     idx++;
1264   }
1265   if( idxNum & 2 ){
1266     pCur->rLimit = (amatch_cost)sqlite3_value_int(argv[idx]);
1267     idx++;
1268   }
1269   if( idxNum & 4 ){
1270     pCur->iLang = (amatch_cost)sqlite3_value_int(argv[idx]);
1271     idx++;
1272   }
1273   pCur->zInput = sqlite3_mprintf("%s", zWord);
1274   if( pCur->zInput==0 ) return SQLITE_NOMEM;
1275   amatchAddWord(pCur, 0, 0, "", "");
1276   amatchNext(pVtabCursor);
1277
1278   return SQLITE_OK;
1279 }
1280
1281 /*
1282 ** Only the word and distance columns have values.  All other columns
1283 ** return NULL
1284 */
1285 static int amatchColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
1286   amatch_cursor *pCur = (amatch_cursor*)cur;
1287   switch( i ){
1288     case AMATCH_COL_WORD: {
1289       sqlite3_result_text(ctx, pCur->pCurrent->zWord+2, -1, SQLITE_STATIC);
1290       break;
1291     }
1292     case AMATCH_COL_DISTANCE: {
1293       sqlite3_result_int(ctx, pCur->pCurrent->rCost);
1294       break;
1295     }
1296     case AMATCH_COL_LANGUAGE: {
1297       sqlite3_result_int(ctx, pCur->iLang);
1298       break;
1299     }
1300     case AMATCH_COL_NWORD: {
1301       sqlite3_result_int(ctx, pCur->nWord);
1302       break;
1303     }
1304     default: {
1305       sqlite3_result_null(ctx);
1306       break;
1307     }
1308   }
1309   return SQLITE_OK;
1310 }
1311
1312 /*
1313 ** The rowid.
1314 */
1315 static int amatchRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
1316   amatch_cursor *pCur = (amatch_cursor*)cur;
1317   *pRowid = pCur->iRowid;
1318   return SQLITE_OK;
1319 }
1320
1321 /*
1322 ** EOF indicator
1323 */
1324 static int amatchEof(sqlite3_vtab_cursor *cur){
1325   amatch_cursor *pCur = (amatch_cursor*)cur;
1326   return pCur->pCurrent==0;
1327 }
1328
1329 /*
1330 ** Search for terms of these forms:
1331 **
1332 **   (A)    word MATCH $str
1333 **   (B1)   distance < $value
1334 **   (B2)   distance <= $value
1335 **   (C)    language == $language
1336 **
1337 ** The distance< and distance<= are both treated as distance<=.
1338 ** The query plan number is a bit vector:
1339 **
1340 **   bit 1:   Term of the form (A) found
1341 **   bit 2:   Term like (B1) or (B2) found
1342 **   bit 3:   Term like (C) found
1343 **
1344 ** If bit-1 is set, $str is always in filter.argv[0].  If bit-2 is set
1345 ** then $value is in filter.argv[0] if bit-1 is clear and is in
1346 ** filter.argv[1] if bit-1 is set.  If bit-3 is set, then $ruleid is
1347 ** in filter.argv[0] if bit-1 and bit-2 are both zero, is in
1348 ** filter.argv[1] if exactly one of bit-1 and bit-2 are set, and is in
1349 ** filter.argv[2] if both bit-1 and bit-2 are set.
1350 */
1351 static int amatchBestIndex(
1352   sqlite3_vtab *tab,
1353   sqlite3_index_info *pIdxInfo
1354 ){
1355   int iPlan = 0;
1356   int iDistTerm = -1;
1357   int iLangTerm = -1;
1358   int i;
1359   const struct sqlite3_index_constraint *pConstraint;
1360
1361   (void)tab;
1362   pConstraint = pIdxInfo->aConstraint;
1363   for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
1364     if( pConstraint->usable==0 ) continue;
1365     if( (iPlan & 1)==0
1366      && pConstraint->iColumn==0
1367      && pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH
1368     ){
1369       iPlan |= 1;
1370       pIdxInfo->aConstraintUsage[i].argvIndex = 1;
1371       pIdxInfo->aConstraintUsage[i].omit = 1;
1372     }
1373     if( (iPlan & 2)==0
1374      && pConstraint->iColumn==1
1375      && (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT
1376            || pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE)
1377     ){
1378       iPlan |= 2;
1379       iDistTerm = i;
1380     }
1381     if( (iPlan & 4)==0
1382      && pConstraint->iColumn==2
1383      && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
1384     ){
1385       iPlan |= 4;
1386       pIdxInfo->aConstraintUsage[i].omit = 1;
1387       iLangTerm = i;
1388     }
1389   }
1390   if( iPlan & 2 ){
1391     pIdxInfo->aConstraintUsage[iDistTerm].argvIndex = 1+((iPlan&1)!=0);
1392   }
1393   if( iPlan & 4 ){
1394     int idx = 1;
1395     if( iPlan & 1 ) idx++;
1396     if( iPlan & 2 ) idx++;
1397     pIdxInfo->aConstraintUsage[iLangTerm].argvIndex = idx;
1398   }
1399   pIdxInfo->idxNum = iPlan;
1400   if( pIdxInfo->nOrderBy==1
1401    && pIdxInfo->aOrderBy[0].iColumn==1
1402    && pIdxInfo->aOrderBy[0].desc==0
1403   ){
1404     pIdxInfo->orderByConsumed = 1;
1405   }
1406   pIdxInfo->estimatedCost = (double)10000;
1407
1408   return SQLITE_OK;
1409 }
1410
1411 /*
1412 ** The xUpdate() method.
1413 **
1414 ** This implementation disallows DELETE and UPDATE.  The only thing
1415 ** allowed is INSERT into the "command" column.
1416 */
1417 static int amatchUpdate(
1418   sqlite3_vtab *pVTab,
1419   int argc,
1420   sqlite3_value **argv,
1421   sqlite_int64 *pRowid
1422 ){
1423   amatch_vtab *p = (amatch_vtab*)pVTab;
1424   const unsigned char *zCmd;
1425   (void)pRowid;
1426   if( argc==1 ){
1427     pVTab->zErrMsg = sqlite3_mprintf("DELETE from %s is not allowed",
1428                                       p->zSelf);
1429     return SQLITE_ERROR;
1430   }
1431   if( sqlite3_value_type(argv[0])!=SQLITE_NULL ){
1432     pVTab->zErrMsg = sqlite3_mprintf("UPDATE of %s is not allowed",
1433                                       p->zSelf);
1434     return SQLITE_ERROR;
1435   }
1436   if( sqlite3_value_type(argv[2+AMATCH_COL_WORD])!=SQLITE_NULL
1437    || sqlite3_value_type(argv[2+AMATCH_COL_DISTANCE])!=SQLITE_NULL
1438    || sqlite3_value_type(argv[2+AMATCH_COL_LANGUAGE])!=SQLITE_NULL
1439   ){
1440     pVTab->zErrMsg = sqlite3_mprintf(
1441             "INSERT INTO %s allowed for column [command] only", p->zSelf);
1442     return SQLITE_ERROR;
1443   }
1444   zCmd = sqlite3_value_text(argv[2+AMATCH_COL_COMMAND]);
1445   if( zCmd==0 ) return SQLITE_OK;
1446
1447   return SQLITE_OK;
1448 }
1449
1450 /*
1451 ** A virtual table module that implements the "approximate_match".
1452 */
1453 static sqlite3_module amatchModule = {
1454   0,                      /* iVersion */
1455   amatchConnect,          /* xCreate */
1456   amatchConnect,          /* xConnect */
1457   amatchBestIndex,        /* xBestIndex */
1458   amatchDisconnect,       /* xDisconnect */
1459   amatchDisconnect,       /* xDestroy */
1460   amatchOpen,             /* xOpen - open a cursor */
1461   amatchClose,            /* xClose - close a cursor */
1462   amatchFilter,           /* xFilter - configure scan constraints */
1463   amatchNext,             /* xNext - advance a cursor */
1464   amatchEof,              /* xEof - check for end of scan */
1465   amatchColumn,           /* xColumn - read data */
1466   amatchRowid,            /* xRowid - read data */
1467   amatchUpdate,           /* xUpdate */
1468   0,                      /* xBegin */
1469   0,                      /* xSync */
1470   0,                      /* xCommit */
1471   0,                      /* xRollback */
1472   0,                      /* xFindMethod */
1473   0,                      /* xRename */
1474   0,                      /* xSavepoint */
1475   0,                      /* xRelease */
1476   0                       /* xRollbackTo */
1477 };
1478
1479 #endif /* SQLITE_OMIT_VIRTUALTABLE */
1480
1481 /*
1482 ** Register the amatch virtual table
1483 */
1484 #ifdef _WIN32
1485 __declspec(dllexport)
1486 #endif
1487 int sqlite3_amatch_init(
1488   sqlite3 *db,
1489   char **pzErrMsg,
1490   const sqlite3_api_routines *pApi
1491 ){
1492   int rc = SQLITE_OK;
1493   SQLITE_EXTENSION_INIT2(pApi);
1494   (void)pzErrMsg;  /* Not used */
1495 #ifndef SQLITE_OMIT_VIRTUALTABLE
1496   rc = sqlite3_create_module(db, "approximate_match", &amatchModule, 0);
1497 #endif /* SQLITE_OMIT_VIRTUALTABLE */
1498   return rc;
1499 }