third_party/sqlite/src/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;
 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 = nFrom;
 629       memcpy(pRule->zFrom, zFrom, nFrom+1);
 630       memcpy(pRule->zTo, zTo, nTo+1);
 631       pRule->nTo = 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(zStr[i]); i++){}
 820   if( zStr[i]!='=' ) return 0;
 821   i++;
 822   while( isspace(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 /*
1002 ** Add a new amatch_word object to the queue.
1003 **
1004 ** If a prior amatch_word object with the same zWord, and nMatch
1005 ** already exists, update its rCost (if the new rCost is less) but
1006 ** otherwise leave it unchanged.  Do not add a duplicate.
1007 **
1008 ** Do nothing if the cost exceeds threshold.
1009 */
1010 static void amatchAddWord(
1011   amatch_cursor *pCur,
1012   amatch_cost rCost,
1013   int nMatch,
1014   const char *zWordBase,
1015   const char *zWordTail
1016 ){
1017   amatch_word *pWord;
1018   amatch_avl *pNode;
1019   amatch_avl *pOther;
1020   int nBase, nTail;
1021   char zBuf[4];
1022
1023   if( rCost>pCur->rLimit ){
1024     return;
1025   }
1026   nBase = (int)strlen(zWordBase);
1027   nTail = (int)strlen(zWordTail);
1028   if( nBase+nTail+3>pCur->nBuf ){
1029     pCur->nBuf = nBase+nTail+100;
1030     pCur->zBuf = sqlite3_realloc(pCur->zBuf, pCur->nBuf);
1031     if( pCur->zBuf==0 ){
1032       pCur->nBuf = 0;
1033       return;
1034     }
1035   }
1036   amatchEncodeInt(nMatch, zBuf);
1037   memcpy(pCur->zBuf, zBuf+2, 2);
1038   memcpy(pCur->zBuf+2, zWordBase, nBase);
1039   memcpy(pCur->zBuf+2+nBase, zWordTail, nTail+1);
1040   pNode = amatchAvlSearch(pCur->pWord, pCur->zBuf);
1041   if( pNode ){
1042     pWord = pNode->pWord;
1043     if( pWord->rCost>rCost ){
1044 #ifdef AMATCH_TRACE_1
1045       printf("UPDATE [%s][%.*s^%s] %d (\"%s\" \"%s\")\n",
1046              pWord->zWord+2, pWord->nMatch, pCur->zInput, pCur->zInput,
1047              pWord->rCost, pWord->zWord, pWord->zCost);
1048 #endif
1049       amatchAvlRemove(&pCur->pCost, &pWord->sCost);
1050       pWord->rCost = rCost;
1051       amatchWriteCost(pWord);
1052 #ifdef AMATCH_TRACE_1
1053       printf("  ---> %d (\"%s\" \"%s\")\n",
1054              pWord->rCost, pWord->zWord, pWord->zCost);
1055 #endif
1056       pOther = amatchAvlInsert(&pCur->pCost, &pWord->sCost);
1057       assert( pOther==0 ); (void)pOther;
1058     }
1059     return;
1060   }
1061   pWord = sqlite3_malloc( sizeof(*pWord) + nBase + nTail - 1 );
1062   if( pWord==0 ) return;
1063   memset(pWord, 0, sizeof(*pWord));
1064   pWord->rCost = rCost;
1065   pWord->iSeq = pCur->nWord++;
1066   amatchWriteCost(pWord);
1067   pWord->nMatch = nMatch;
1068   pWord->pNext = pCur->pAllWords;
1069   pCur->pAllWords = pWord;
1070   pWord->sCost.zKey = pWord->zCost;
1071   pWord->sCost.pWord = pWord;
1072   pOther = amatchAvlInsert(&pCur->pCost, &pWord->sCost);
1073   assert( pOther==0 ); (void)pOther;
1074   pWord->sWord.zKey = pWord->zWord;
1075   pWord->sWord.pWord = pWord;
1076   strcpy(pWord->zWord, pCur->zBuf);
1077   pOther = amatchAvlInsert(&pCur->pWord, &pWord->sWord);
1078   assert( pOther==0 ); (void)pOther;
1079 #ifdef AMATCH_TRACE_1
1080   printf("INSERT [%s][%.*s^%s] %d (\"%s\" \"%s\")\n", pWord->zWord+2,
1081        pWord->nMatch, pCur->zInput, pCur->zInput+pWord->nMatch, rCost,
1082        pWord->zWord, pWord->zCost);
1083 #endif
1084 }
1085
1086 /*
1087 ** Advance a cursor to its next row of output
1088 */
1089 static int amatchNext(sqlite3_vtab_cursor *cur){
1090   amatch_cursor *pCur = (amatch_cursor*)cur;
1091   amatch_word *pWord = 0;
1092   amatch_avl *pNode;
1093   int isMatch = 0;
1094   amatch_vtab *p = pCur->pVtab;
1095   int nWord;
1096   int rc;
1097   int i;
1098   const char *zW;
1099   amatch_rule *pRule;
1100   char *zBuf = 0;
1101   char nBuf = 0;
1102   char zNext[8];
1103   char zNextIn[8];
1104   int nNextIn;
1105
1106   if( p->pVCheck==0 ){
1107     char *zSql;
1108     if( p->zVocabLang && p->zVocabLang[0] ){
1109       zSql = sqlite3_mprintf(
1110           "SELECT \"%w\" FROM \"%w\"",
1111           " WHERE \"%w\">=?1 AND \"%w\"=?2"
1112           " ORDER BY 1",
1113           p->zVocabWord, p->zVocabTab,
1114           p->zVocabWord, p->zVocabLang
1115       );
1116     }else{
1117       zSql = sqlite3_mprintf(
1118           "SELECT \"%w\" FROM \"%w\""
1119           " WHERE \"%w\">=?1"
1120           " ORDER BY 1",
1121           p->zVocabWord, p->zVocabTab,
1122           p->zVocabWord
1123       );
1124     }
1125     rc = sqlite3_prepare_v2(p->db, zSql, -1, &p->pVCheck, 0);
1126     sqlite3_free(zSql);
1127     if( rc ) return rc;
1128   }
1129   sqlite3_bind_int(p->pVCheck, 2, pCur->iLang);
1130
1131   do{
1132     pNode = amatchAvlFirst(pCur->pCost);
1133     if( pNode==0 ){
1134       pWord = 0;
1135       break;
1136     }
1137     pWord = pNode->pWord;
1138     amatchAvlRemove(&pCur->pCost, &pWord->sCost);
1139
1140 #ifdef AMATCH_TRACE_1
1141     printf("PROCESS [%s][%.*s^%s] %d (\"%s\" \"%s\")\n",
1142        pWord->zWord+2, pWord->nMatch, pCur->zInput, pCur->zInput+pWord->nMatch,
1143        pWord->rCost, pWord->zWord, pWord->zCost);
1144 #endif
1145     nWord = (int)strlen(pWord->zWord+2);
1146     if( nWord+20>nBuf ){
1147       nBuf = nWord+100;
1148       zBuf = sqlite3_realloc(zBuf, nBuf);
1149       if( zBuf==0 ) return SQLITE_NOMEM;
1150     }
1151     strcpy(zBuf, pWord->zWord+2);
1152     zNext[0] = 0;
1153     zNextIn[0] = pCur->zInput[pWord->nMatch];
1154     if( zNextIn[0] ){
1155       for(i=1; i<=4 && (pCur->zInput[pWord->nMatch+i]&0xc0)==0x80; i++){
1156         zNextIn[i] = pCur->zInput[pWord->nMatch+i];
1157       }
1158       zNextIn[i] = 0;
1159       nNextIn = i;
1160     }else{
1161       nNextIn = 0;
1162     }
1163
1164     if( zNextIn[0] && zNextIn[0]!='*' ){
1165       sqlite3_reset(p->pVCheck);
1166       strcat(zBuf, zNextIn);
1167       sqlite3_bind_text(p->pVCheck, 1, zBuf, nWord+nNextIn, SQLITE_STATIC);
1168       rc = sqlite3_step(p->pVCheck);
1169       if( rc==SQLITE_ROW ){
1170         zW = (const char*)sqlite3_column_text(p->pVCheck, 0);
1171         if( strncmp(zBuf, zW, nWord+nNextIn)==0 ){
1172           amatchAddWord(pCur, pWord->rCost, pWord->nMatch+nNextIn, zBuf, "");
1173         }
1174       }
1175       zBuf[nWord] = 0;
1176     }
1177
1178     while( 1 ){
1179       strcpy(zBuf+nWord, zNext);
1180       sqlite3_reset(p->pVCheck);
1181       sqlite3_bind_text(p->pVCheck, 1, zBuf, -1, SQLITE_TRANSIENT);
1182       rc = sqlite3_step(p->pVCheck);
1183       if( rc!=SQLITE_ROW ) break;
1184       zW = (const char*)sqlite3_column_text(p->pVCheck, 0);
1185       strcpy(zBuf+nWord, zNext);
1186       if( strncmp(zW, zBuf, nWord)!=0 ) break;
1187       if( (zNextIn[0]=='*' && zNextIn[1]==0)
1188        || (zNextIn[0]==0 && zW[nWord]==0)
1189       ){
1190         isMatch = 1;
1191         zNextIn[0] = 0;
1192         nNextIn = 0;
1193         break;
1194       }
1195       zNext[0] = zW[nWord];
1196       for(i=1; i<=4 && (zW[nWord+i]&0xc0)==0x80; i++){
1197         zNext[i] = zW[nWord+i];
1198       }
1199       zNext[i] = 0;
1200       zBuf[nWord] = 0;
1201       if( p->rIns>0 ){
1202         amatchAddWord(pCur, pWord->rCost+p->rIns, pWord->nMatch,
1203                       zBuf, zNext);
1204       }
1205       if( p->rSub>0 ){
1206         amatchAddWord(pCur, pWord->rCost+p->rSub, pWord->nMatch+nNextIn,
1207                       zBuf, zNext);
1208       }
1209       if( p->rIns<0 && p->rSub<0 ) break;
1210       zNext[i-1]++;  /* FIX ME */
1211     }
1212     sqlite3_reset(p->pVCheck);
1213
1214     if( p->rDel>0 ){
1215       zBuf[nWord] = 0;
1216       amatchAddWord(pCur, pWord->rCost+p->rDel, pWord->nMatch+nNextIn,
1217                     zBuf, "");
1218     }
1219
1220     for(pRule=p->pRule; pRule; pRule=pRule->pNext){
1221       if( pRule->iLang!=pCur->iLang ) continue;
1222       if( strncmp(pRule->zFrom, pCur->zInput+pWord->nMatch, pRule->nFrom)==0 ){
1223         amatchAddWord(pCur, pWord->rCost+pRule->rCost,
1224                       pWord->nMatch+pRule->nFrom, pWord->zWord+2, pRule->zTo);
1225       }
1226     }
1227   }while( !isMatch );
1228   pCur->pCurrent = pWord;
1229   sqlite3_free(zBuf);
1230   return SQLITE_OK;
1231 }
1232
1233 /*
1234 ** Called to "rewind" a cursor back to the beginning so that
1235 ** it starts its output over again.  Always called at least once
1236 ** prior to any amatchColumn, amatchRowid, or amatchEof call.
1237 */
1238 static int amatchFilter(
1239   sqlite3_vtab_cursor *pVtabCursor,
1240   int idxNum, const char *idxStr,
1241   int argc, sqlite3_value **argv
1242 ){
1243   amatch_cursor *pCur = (amatch_cursor *)pVtabCursor;
1244   const char *zWord = "*";
1245   int idx;
1246
1247   amatchClearCursor(pCur);
1248   idx = 0;
1249   if( idxNum & 1 ){
1250     zWord = (const char*)sqlite3_value_text(argv[0]);
1251     idx++;
1252   }
1253   if( idxNum & 2 ){
1254     pCur->rLimit = (amatch_cost)sqlite3_value_int(argv[idx]);
1255     idx++;
1256   }
1257   if( idxNum & 4 ){
1258     pCur->iLang = (amatch_cost)sqlite3_value_int(argv[idx]);
1259     idx++;
1260   }
1261   pCur->zInput = sqlite3_mprintf("%s", zWord);
1262   if( pCur->zInput==0 ) return SQLITE_NOMEM;
1263   amatchAddWord(pCur, 0, 0, "", "");
1264   amatchNext(pVtabCursor);
1265
1266   return SQLITE_OK;
1267 }
1268
1269 /*
1270 ** Only the word and distance columns have values.  All other columns
1271 ** return NULL
1272 */
1273 static int amatchColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
1274   amatch_cursor *pCur = (amatch_cursor*)cur;
1275   switch( i ){
1276     case AMATCH_COL_WORD: {
1277       sqlite3_result_text(ctx, pCur->pCurrent->zWord+2, -1, SQLITE_STATIC);
1278       break;
1279     }
1280     case AMATCH_COL_DISTANCE: {
1281       sqlite3_result_int(ctx, pCur->pCurrent->rCost);
1282       break;
1283     }
1284     case AMATCH_COL_LANGUAGE: {
1285       sqlite3_result_int(ctx, pCur->iLang);
1286       break;
1287     }
1288     case AMATCH_COL_NWORD: {
1289       sqlite3_result_int(ctx, pCur->nWord);
1290       break;
1291     }
1292     default: {
1293       sqlite3_result_null(ctx);
1294       break;
1295     }
1296   }
1297   return SQLITE_OK;
1298 }
1299
1300 /*
1301 ** The rowid.
1302 */
1303 static int amatchRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
1304   amatch_cursor *pCur = (amatch_cursor*)cur;
1305   *pRowid = pCur->iRowid;
1306   return SQLITE_OK;
1307 }
1308
1309 /*
1310 ** EOF indicator
1311 */
1312 static int amatchEof(sqlite3_vtab_cursor *cur){
1313   amatch_cursor *pCur = (amatch_cursor*)cur;
1314   return pCur->pCurrent==0;
1315 }
1316
1317 /*
1318 ** Search for terms of these forms:
1319 **
1320 **   (A)    word MATCH $str
1321 **   (B1)   distance < $value
1322 **   (B2)   distance <= $value
1323 **   (C)    language == $language
1324 **
1325 ** The distance< and distance<= are both treated as distance<=.
1326 ** The query plan number is a bit vector:
1327 **
1328 **   bit 1:   Term of the form (A) found
1329 **   bit 2:   Term like (B1) or (B2) found
1330 **   bit 3:   Term like (C) found
1331 **
1332 ** If bit-1 is set, $str is always in filter.argv[0].  If bit-2 is set
1333 ** then $value is in filter.argv[0] if bit-1 is clear and is in
1334 ** filter.argv[1] if bit-1 is set.  If bit-3 is set, then $ruleid is
1335 ** in filter.argv[0] if bit-1 and bit-2 are both zero, is in
1336 ** filter.argv[1] if exactly one of bit-1 and bit-2 are set, and is in
1337 ** filter.argv[2] if both bit-1 and bit-2 are set.
1338 */
1339 static int amatchBestIndex(
1340   sqlite3_vtab *tab,
1341   sqlite3_index_info *pIdxInfo
1342 ){
1343   int iPlan = 0;
1344   int iDistTerm = -1;
1345   int iLangTerm = -1;
1346   int i;
1347   const struct sqlite3_index_constraint *pConstraint;
1348
1349   (void)tab;
1350   pConstraint = pIdxInfo->aConstraint;
1351   for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
1352     if( pConstraint->usable==0 ) continue;
1353     if( (iPlan & 1)==0
1354      && pConstraint->iColumn==0
1355      && pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH
1356     ){
1357       iPlan |= 1;
1358       pIdxInfo->aConstraintUsage[i].argvIndex = 1;
1359       pIdxInfo->aConstraintUsage[i].omit = 1;
1360     }
1361     if( (iPlan & 2)==0
1362      && pConstraint->iColumn==1
1363      && (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT
1364            || pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE)
1365     ){
1366       iPlan |= 2;
1367       iDistTerm = i;
1368     }
1369     if( (iPlan & 4)==0
1370      && pConstraint->iColumn==2
1371      && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
1372     ){
1373       iPlan |= 4;
1374       pIdxInfo->aConstraintUsage[i].omit = 1;
1375       iLangTerm = i;
1376     }
1377   }
1378   if( iPlan & 2 ){
1379     pIdxInfo->aConstraintUsage[iDistTerm].argvIndex = 1+((iPlan&1)!=0);
1380   }
1381   if( iPlan & 4 ){
1382     int idx = 1;
1383     if( iPlan & 1 ) idx++;
1384     if( iPlan & 2 ) idx++;
1385     pIdxInfo->aConstraintUsage[iLangTerm].argvIndex = idx;
1386   }
1387   pIdxInfo->idxNum = iPlan;
1388   if( pIdxInfo->nOrderBy==1
1389    && pIdxInfo->aOrderBy[0].iColumn==1
1390    && pIdxInfo->aOrderBy[0].desc==0
1391   ){
1392     pIdxInfo->orderByConsumed = 1;
1393   }
1394   pIdxInfo->estimatedCost = (double)10000;
1395
1396   return SQLITE_OK;
1397 }
1398
1399 /*
1400 ** The xUpdate() method.
1401 **
1402 ** This implementation disallows DELETE and UPDATE.  The only thing
1403 ** allowed is INSERT into the "command" column.
1404 */
1405 static int amatchUpdate(
1406   sqlite3_vtab *pVTab,
1407   int argc,
1408   sqlite3_value **argv,
1409   sqlite_int64 *pRowid
1410 ){
1411   amatch_vtab *p = (amatch_vtab*)pVTab;
1412   const unsigned char *zCmd;
1413   (void)pRowid;
1414   if( argc==1 ){
1415     pVTab->zErrMsg = sqlite3_mprintf("DELETE from %s is not allowed",
1416                                       p->zSelf);
1417     return SQLITE_ERROR;
1418   }
1419   if( sqlite3_value_type(argv[0])!=SQLITE_NULL ){
1420     pVTab->zErrMsg = sqlite3_mprintf("UPDATE of %s is not allowed",
1421                                       p->zSelf);
1422     return SQLITE_ERROR;
1423   }
1424   if( sqlite3_value_type(argv[2+AMATCH_COL_WORD])!=SQLITE_NULL
1425    || sqlite3_value_type(argv[2+AMATCH_COL_DISTANCE])!=SQLITE_NULL
1426    || sqlite3_value_type(argv[2+AMATCH_COL_LANGUAGE])!=SQLITE_NULL
1427   ){
1428     pVTab->zErrMsg = sqlite3_mprintf(
1429             "INSERT INTO %s allowed for column [command] only", p->zSelf);
1430     return SQLITE_ERROR;
1431   }
1432   zCmd = sqlite3_value_text(argv[2+AMATCH_COL_COMMAND]);
1433   if( zCmd==0 ) return SQLITE_OK;
1434
1435   return SQLITE_OK;
1436 }
1437
1438 /*
1439 ** A virtual table module that implements the "approximate_match".
1440 */
1441 static sqlite3_module amatchModule = {
1442   0,                      /* iVersion */
1443   amatchConnect,          /* xCreate */
1444   amatchConnect,          /* xConnect */
1445   amatchBestIndex,        /* xBestIndex */
1446   amatchDisconnect,       /* xDisconnect */
1447   amatchDisconnect,       /* xDestroy */
1448   amatchOpen,             /* xOpen - open a cursor */
1449   amatchClose,            /* xClose - close a cursor */
1450   amatchFilter,           /* xFilter - configure scan constraints */
1451   amatchNext,             /* xNext - advance a cursor */
1452   amatchEof,              /* xEof - check for end of scan */
1453   amatchColumn,           /* xColumn - read data */
1454   amatchRowid,            /* xRowid - read data */
1455   amatchUpdate,           /* xUpdate */
1456   0,                      /* xBegin */
1457   0,                      /* xSync */
1458   0,                      /* xCommit */
1459   0,                      /* xRollback */
1460   0,                      /* xFindMethod */
1461   0,                      /* xRename */
1462   0,                      /* xSavepoint */
1463   0,                      /* xRelease */
1464   0                       /* xRollbackTo */
1465 };
1466
1467 #endif /* SQLITE_OMIT_VIRTUALTABLE */
1468
1469 /*
1470 ** Register the amatch virtual table
1471 */
1472 #ifdef _WIN32
1473 __declspec(dllexport)
1474 #endif
1475 int sqlite3_amatch_init(
1476   sqlite3 *db,
1477   char **pzErrMsg,
1478   const sqlite3_api_routines *pApi
1479 ){
1480   int rc = SQLITE_OK;
1481   SQLITE_EXTENSION_INIT2(pApi);
1482   (void)pzErrMsg;  /* Not used */
1483 #ifndef SQLITE_OMIT_VIRTUALTABLE
1484   rc = sqlite3_create_module(db, "approximate_match", &amatchModule, 0);
1485 #endif /* SQLITE_OMIT_VIRTUALTABLE */
1486   return rc;
1487 }