Debian Codegraph @

ext/misc/spellfix.c

raw
1 /*
2 ** 2012 April 10
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 module implements the spellfix1 VIRTUAL TABLE that can be used
14 ** to search a large vocabulary for close matches. See separate
15 ** documentation (http://sqlite.org/spellfix1.html) for details.
16 */
17 #include "sqlite3ext.h"
18 SQLITE_EXTENSION_INIT1
19
20 #ifndef SQLITE_AMALGAMATION
21 # if !defined(NDEBUG) && !defined(SQLITE_DEBUG)
22 # define NDEBUG 1
23 # endif
24 # if defined(NDEBUG) && defined(SQLITE_DEBUG)
25 # undef NDEBUG
26 # endif
27 # include <string.h>
28 # include <stdio.h>
29 # include <stdlib.h>
30 # include <assert.h>
31 # define ALWAYS(X) 1
32 # define NEVER(X) 0
33 typedef unsigned char u8;
34 typedef unsigned short u16;
35 typedef sqlite3_int64 i64;
36 #endif
37 #include <ctype.h>
38
39 #ifndef SQLITE_OMIT_VIRTUALTABLE
40
41 /*
42 ** Character classes for ASCII characters:
43 **
44 ** 0 '' Silent letters: H W
45 ** 1 'A' Any vowel: A E I O U (Y)
46 ** 2 'B' A bilabeal stop or fricative: B F P V W
47 ** 3 'C' Other fricatives or back stops: C G J K Q S X Z
48 ** 4 'D' Alveolar stops: D T
49 ** 5 'H' Letter H at the beginning of a word
50 ** 6 'L' Glide: L
51 ** 7 'R' Semivowel: R
52 ** 8 'M' Nasals: M N
53 ** 9 'Y' Letter Y at the beginning of a word.
54 ** 10 '9' Digits: 0 1 2 3 4 5 6 7 8 9
55 ** 11 ' ' White space
56 ** 12 '?' Other.
57 */
58 #define CCLASS_SILENT 0
59 #define CCLASS_VOWEL 1
60 #define CCLASS_B 2
61 #define CCLASS_C 3
62 #define CCLASS_D 4
63 #define CCLASS_H 5
64 #define CCLASS_L 6
65 #define CCLASS_R 7
66 #define CCLASS_M 8
67 #define CCLASS_Y 9
68 #define CCLASS_DIGIT 10
69 #define CCLASS_SPACE 11
70 #define CCLASS_OTHER 12
71
72 /*
73 ** The following table gives the character class for non-initial ASCII
74 ** characters.
75 */
76 static const unsigned char midClass[] = {
77 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
78 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
79 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
80 /* */ CCLASS_SPACE, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
81 /* */ CCLASS_SPACE, /* */ CCLASS_SPACE, /* */ CCLASS_OTHER,
82 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
83 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
84 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
85 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
86 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
87 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_SPACE,
88 /* ! */ CCLASS_OTHER, /* " */ CCLASS_OTHER, /* # */ CCLASS_OTHER,
89 /* $ */ CCLASS_OTHER, /* % */ CCLASS_OTHER, /* & */ CCLASS_OTHER,
90 /* ' */ CCLASS_SILENT, /* ( */ CCLASS_OTHER, /* ) */ CCLASS_OTHER,
91 /* * */ CCLASS_OTHER, /* + */ CCLASS_OTHER, /* , */ CCLASS_OTHER,
92 /* - */ CCLASS_OTHER, /* . */ CCLASS_OTHER, /* / */ CCLASS_OTHER,
93 /* 0 */ CCLASS_DIGIT, /* 1 */ CCLASS_DIGIT, /* 2 */ CCLASS_DIGIT,
94 /* 3 */ CCLASS_DIGIT, /* 4 */ CCLASS_DIGIT, /* 5 */ CCLASS_DIGIT,
95 /* 6 */ CCLASS_DIGIT, /* 7 */ CCLASS_DIGIT, /* 8 */ CCLASS_DIGIT,
96 /* 9 */ CCLASS_DIGIT, /* : */ CCLASS_OTHER, /* ; */ CCLASS_OTHER,
97 /* < */ CCLASS_OTHER, /* = */ CCLASS_OTHER, /* > */ CCLASS_OTHER,
98 /* ? */ CCLASS_OTHER, /* @ */ CCLASS_OTHER, /* A */ CCLASS_VOWEL,
99 /* B */ CCLASS_B, /* C */ CCLASS_C, /* D */ CCLASS_D,
100 /* E */ CCLASS_VOWEL, /* F */ CCLASS_B, /* G */ CCLASS_C,
101 /* H */ CCLASS_SILENT, /* I */ CCLASS_VOWEL, /* J */ CCLASS_C,
102 /* K */ CCLASS_C, /* L */ CCLASS_L, /* M */ CCLASS_M,
103 /* N */ CCLASS_M, /* O */ CCLASS_VOWEL, /* P */ CCLASS_B,
104 /* Q */ CCLASS_C, /* R */ CCLASS_R, /* S */ CCLASS_C,
105 /* T */ CCLASS_D, /* U */ CCLASS_VOWEL, /* V */ CCLASS_B,
106 /* W */ CCLASS_B, /* X */ CCLASS_C, /* Y */ CCLASS_VOWEL,
107 /* Z */ CCLASS_C, /* [ */ CCLASS_OTHER, /* \ */ CCLASS_OTHER,
108 /* ] */ CCLASS_OTHER, /* ^ */ CCLASS_OTHER, /* _ */ CCLASS_OTHER,
109 /* ` */ CCLASS_OTHER, /* a */ CCLASS_VOWEL, /* b */ CCLASS_B,
110 /* c */ CCLASS_C, /* d */ CCLASS_D, /* e */ CCLASS_VOWEL,
111 /* f */ CCLASS_B, /* g */ CCLASS_C, /* h */ CCLASS_SILENT,
112 /* i */ CCLASS_VOWEL, /* j */ CCLASS_C, /* k */ CCLASS_C,
113 /* l */ CCLASS_L, /* m */ CCLASS_M, /* n */ CCLASS_M,
114 /* o */ CCLASS_VOWEL, /* p */ CCLASS_B, /* q */ CCLASS_C,
115 /* r */ CCLASS_R, /* s */ CCLASS_C, /* t */ CCLASS_D,
116 /* u */ CCLASS_VOWEL, /* v */ CCLASS_B, /* w */ CCLASS_B,
117 /* x */ CCLASS_C, /* y */ CCLASS_VOWEL, /* z */ CCLASS_C,
118 /* { */ CCLASS_OTHER, /* | */ CCLASS_OTHER, /* } */ CCLASS_OTHER,
119 /* ~ */ CCLASS_OTHER, /* */ CCLASS_OTHER,
120 };
121 /*
122 ** This tables gives the character class for ASCII characters that form the
123 ** initial character of a word. The only difference from midClass is with
124 ** the letters H, W, and Y.
125 */
126 static const unsigned char initClass[] = {
127 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
128 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
129 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
130 /* */ CCLASS_SPACE, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
131 /* */ CCLASS_SPACE, /* */ CCLASS_SPACE, /* */ CCLASS_OTHER,
132 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
133 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
134 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
135 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
136 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER,
137 /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_SPACE,
138 /* ! */ CCLASS_OTHER, /* " */ CCLASS_OTHER, /* # */ CCLASS_OTHER,
139 /* $ */ CCLASS_OTHER, /* % */ CCLASS_OTHER, /* & */ CCLASS_OTHER,
140 /* ' */ CCLASS_OTHER, /* ( */ CCLASS_OTHER, /* ) */ CCLASS_OTHER,
141 /* * */ CCLASS_OTHER, /* + */ CCLASS_OTHER, /* , */ CCLASS_OTHER,
142 /* - */ CCLASS_OTHER, /* . */ CCLASS_OTHER, /* / */ CCLASS_OTHER,
143 /* 0 */ CCLASS_DIGIT, /* 1 */ CCLASS_DIGIT, /* 2 */ CCLASS_DIGIT,
144 /* 3 */ CCLASS_DIGIT, /* 4 */ CCLASS_DIGIT, /* 5 */ CCLASS_DIGIT,
145 /* 6 */ CCLASS_DIGIT, /* 7 */ CCLASS_DIGIT, /* 8 */ CCLASS_DIGIT,
146 /* 9 */ CCLASS_DIGIT, /* : */ CCLASS_OTHER, /* ; */ CCLASS_OTHER,
147 /* < */ CCLASS_OTHER, /* = */ CCLASS_OTHER, /* > */ CCLASS_OTHER,
148 /* ? */ CCLASS_OTHER, /* @ */ CCLASS_OTHER, /* A */ CCLASS_VOWEL,
149 /* B */ CCLASS_B, /* C */ CCLASS_C, /* D */ CCLASS_D,
150 /* E */ CCLASS_VOWEL, /* F */ CCLASS_B, /* G */ CCLASS_C,
151 /* H */ CCLASS_SILENT, /* I */ CCLASS_VOWEL, /* J */ CCLASS_C,
152 /* K */ CCLASS_C, /* L */ CCLASS_L, /* M */ CCLASS_M,
153 /* N */ CCLASS_M, /* O */ CCLASS_VOWEL, /* P */ CCLASS_B,
154 /* Q */ CCLASS_C, /* R */ CCLASS_R, /* S */ CCLASS_C,
155 /* T */ CCLASS_D, /* U */ CCLASS_VOWEL, /* V */ CCLASS_B,
156 /* W */ CCLASS_B, /* X */ CCLASS_C, /* Y */ CCLASS_Y,
157 /* Z */ CCLASS_C, /* [ */ CCLASS_OTHER, /* \ */ CCLASS_OTHER,
158 /* ] */ CCLASS_OTHER, /* ^ */ CCLASS_OTHER, /* _ */ CCLASS_OTHER,
159 /* ` */ CCLASS_OTHER, /* a */ CCLASS_VOWEL, /* b */ CCLASS_B,
160 /* c */ CCLASS_C, /* d */ CCLASS_D, /* e */ CCLASS_VOWEL,
161 /* f */ CCLASS_B, /* g */ CCLASS_C, /* h */ CCLASS_SILENT,
162 /* i */ CCLASS_VOWEL, /* j */ CCLASS_C, /* k */ CCLASS_C,
163 /* l */ CCLASS_L, /* m */ CCLASS_M, /* n */ CCLASS_M,
164 /* o */ CCLASS_VOWEL, /* p */ CCLASS_B, /* q */ CCLASS_C,
165 /* r */ CCLASS_R, /* s */ CCLASS_C, /* t */ CCLASS_D,
166 /* u */ CCLASS_VOWEL, /* v */ CCLASS_B, /* w */ CCLASS_B,
167 /* x */ CCLASS_C, /* y */ CCLASS_Y, /* z */ CCLASS_C,
168 /* { */ CCLASS_OTHER, /* | */ CCLASS_OTHER, /* } */ CCLASS_OTHER,
169 /* ~ */ CCLASS_OTHER, /* */ CCLASS_OTHER,
170 };
171
172 /*
173 ** Mapping from the character class number (0-13) to a symbol for each
174 ** character class. Note that initClass[] can be used to map the class
175 ** symbol back into the class number.
176 */
177 static const unsigned char className[] = ".ABCDHLRMY9 ?";
178
179 /*
180 ** Generate a "phonetic hash" from a string of ASCII characters
181 ** in zIn[0..nIn-1].
182 **
183 ** * Map characters by character class as defined above.
184 ** * Omit double-letters
185 ** * Omit vowels beside R and L
186 ** * Omit T when followed by CH
187 ** * Omit W when followed by R
188 ** * Omit D when followed by J or G
189 ** * Omit K in KN or G in GN at the beginning of a word
190 **
191 ** Space to hold the result is obtained from sqlite3_malloc()
192 **
193 ** Return NULL if memory allocation fails.
194 */
195 static unsigned char *phoneticHash(const unsigned char *zIn, int nIn){
196 unsigned char *zOut = sqlite3_malloc64( (i64)nIn + 1 );
197 int i;
198 int nOut = 0;
199 char cPrev = 0x77;
200 char cPrevX = 0x77;
201 const unsigned char *aClass = initClass;
202
203 if( zOut==0 ) return 0;
204 if( nIn>2 ){
205 switch( zIn[0] ){
206 case 'g':
207 case 'k': {
208 if( zIn[1]=='n' ){ zIn++; nIn--; }
209 break;
210 }
211 }
212 }
213 for(i=0; i<nIn; i++){
214 unsigned char c = zIn[i];
215 if( i+1<nIn ){
216 if( c=='w' && zIn[i+1]=='r' ) continue;
217 if( c=='d' && (zIn[i+1]=='j' || zIn[i+1]=='g') ) continue;
218 if( i+2<nIn ){
219 if( c=='t' && zIn[i+1]=='c' && zIn[i+2]=='h' ) continue;
220 }
221 }
222 c = aClass[c&0x7f];
223 if( c==CCLASS_SPACE ) continue;
224 if( c==CCLASS_OTHER && cPrev!=CCLASS_DIGIT ) continue;
225 aClass = midClass;
226 if( c==CCLASS_VOWEL && (cPrevX==CCLASS_R || cPrevX==CCLASS_L) ){
227 continue; /* No vowels beside L or R */
228 }
229 if( (c==CCLASS_R || c==CCLASS_L) && cPrevX==CCLASS_VOWEL ){
230 nOut--; /* No vowels beside L or R */
231 }
232 cPrev = c;
233 if( c==CCLASS_SILENT ) continue;
234 cPrevX = c;
235 c = className[c];
236 assert( nOut>=0 );
237 if( nOut==0 || c!=zOut[nOut-1] ) zOut[nOut++] = c;
238 }
239 zOut[nOut] = 0;
240 return zOut;
241 }
242
243 /*
244 ** This is an SQL function wrapper around phoneticHash(). See
245 ** the description of phoneticHash() for additional information.
246 */
247 static void phoneticHashSqlFunc(
248 sqlite3_context *context,
249 int argc,
250 sqlite3_value **argv
251 ){
252 const unsigned char *zIn;
253 unsigned char *zOut;
254
255 zIn = sqlite3_value_text(argv[0]);
256 if( zIn==0 ) return;
257 zOut = phoneticHash(zIn, sqlite3_value_bytes(argv[0]));
258 if( zOut==0 ){
259 sqlite3_result_error_nomem(context);
260 }else{
261 sqlite3_result_text(context, (char*)zOut, -1, sqlite3_free);
262 }
263 }
264
265 /*
266 ** Return the character class number for a character given its
267 ** context.
268 */
269 static char characterClass(char cPrev, char c){
270 return cPrev==0 ? initClass[c&0x7f] : midClass[c&0x7f];
271 }
272
273 /*
274 ** Return the cost of inserting or deleting character c immediately
275 ** following character cPrev. If cPrev==0, that means c is the first
276 ** character of the word.
277 */
278 static int insertOrDeleteCost(char cPrev, char c, char cNext){
279 char classC = characterClass(cPrev, c);
280 char classCprev;
281
282 if( classC==CCLASS_SILENT ){
283 /* Insert or delete "silent" characters such as H or W */
284 return 1;
285 }
286 if( cPrev==c ){
287 /* Repeated characters, or miss a repeat */
288 return 10;
289 }
290 if( classC==CCLASS_VOWEL && (cPrev=='r' || cNext=='r') ){
291 return 20; /* Insert a vowel before or after 'r' */
292 }
293 classCprev = characterClass(cPrev, cPrev);
294 if( classC==classCprev ){
295 if( classC==CCLASS_VOWEL ){
296 /* Remove or add a new vowel to a vowel cluster */
297 return 15;
298 }else{
299 /* Remove or add a consonant not in the same class */
300 return 50;
301 }
302 }
303
304 /* any other character insertion or deletion */
305 return 100;
306 }
307
308 /*
309 ** Divide the insertion cost by this factor when appending to the
310 ** end of the word.
311 */
312 #define FINAL_INS_COST_DIV 4
313
314 /*
315 ** Return the cost of substituting cTo in place of cFrom assuming
316 ** the previous character is cPrev. If cPrev==0 then cTo is the first
317 ** character of the word.
318 */
319 static int substituteCost(char cPrev, char cFrom, char cTo){
320 char classFrom, classTo;
321 if( cFrom==cTo ){
322 /* Exact match */
323 return 0;
324 }
325 if( cFrom==(cTo^0x20) && ((cTo>='A' && cTo<='Z') || (cTo>='a' && cTo<='z')) ){
326 /* differ only in case */
327 return 0;
328 }
329 classFrom = characterClass(cPrev, cFrom);
330 classTo = characterClass(cPrev, cTo);
331 if( classFrom==classTo ){
332 /* Same character class */
333 return 40;
334 }
335 if( classFrom>=CCLASS_B && classFrom<=CCLASS_Y
336 && classTo>=CCLASS_B && classTo<=CCLASS_Y ){
337 /* Convert from one consonant to another, but in a different class */
338 return 75;
339 }
340 /* Any other subsitution */
341 return 100;
342 }
343
344 /*
345 ** Given two strings zA and zB which are pure ASCII, return the cost
346 ** of transforming zA into zB. If zA ends with '*' assume that it is
347 ** a prefix of zB and give only minimal penalty for extra characters
348 ** on the end of zB.
349 **
350 ** Smaller numbers mean a closer match.
351 **
352 ** Negative values indicate an error:
353 ** -1 One of the inputs is NULL
354 ** -2 Non-ASCII characters on input
355 ** -3 Unable to allocate memory
356 ** -4 Inputs too large
357 **
358 ** If pnMatch is not NULL, then *pnMatch is set to the number of bytes
359 ** of zB that matched the pattern in zA. If zA does not end with a '*',
360 ** then this value is always the number of bytes in zB (i.e. strlen(zB)).
361 ** If zA does end in a '*', then it is the number of bytes in the prefix
362 ** of zB that was deemed to match zA.
363 */
364 static int editdist1(const char *zA, const char *zB, int *pnMatch){
365 unsigned int nA, nB; /* Number of characters in zA[] and zB[] */
366 unsigned int xA, xB; /* Loop counters for zA[] and zB[] */
367 char cA = 0, cB; /* Current character of zA and zB */
368 char cAprev, cBprev; /* Previous character of zA and zB */
369 char cAnext, cBnext; /* Next character in zA and zB */
370 int d; /* North-west cost value */
371 int dc = 0; /* North-west character value */
372 int res; /* Final result */
373 int *m; /* The cost matrix */
374 char *cx; /* Corresponding character values */
375 int *toFree = 0; /* Malloced space */
376 int nMatch = 0;
377 int mStack[60+15]; /* Stack space to use if not too much is needed */
378
379 /* Early out if either input is NULL */
380 if( zA==0 || zB==0 ) return -1;
381
382 /* Skip any common prefix */
383 while( zA[0] && zA[0]==zB[0] ){ dc = zA[0]; zA++; zB++; nMatch++; }
384 if( pnMatch ) *pnMatch = nMatch;
385 if( zA[0]==0 && zB[0]==0 ) return 0;
386
387 #if 0
388 printf("A=\"%s\" B=\"%s\" dc=%c\n", zA, zB, dc?dc:' ');
389 #endif
390
391 /* Verify input strings and measure their lengths */
392 for(nA=0; zA[nA]; nA++){
393 if( zA[nA]&0x80 ) return -2;
394 }
395 if( nA>=100000 ) return -4;
396 for(nB=0; zB[nB]; nB++){
397 if( zB[nB]&0x80 ) return -2;
398 }
399 if( nB>=100000 ) return -4;
400
401 /* Special processing if either string is empty */
402 if( nA==0 ){
403 cBprev = (char)dc;
404 for(xB=res=0; (cB = zB[xB])!=0; xB++){
405 res += insertOrDeleteCost(cBprev, cB, zB[xB+1])/FINAL_INS_COST_DIV;
406 cBprev = cB;
407 }
408 return res;
409 }
410 if( nB==0 ){
411 cAprev = (char)dc;
412 for(xA=res=0; (cA = zA[xA])!=0; xA++){
413 res += insertOrDeleteCost(cAprev, cA, zA[xA+1]);
414 cAprev = cA;
415 }
416 return res;
417 }
418
419 /* A is a prefix of B */
420 if( zA[0]=='*' && zA[1]==0 ) return 0;
421
422 /* Allocate and initialize the Wagner matrix */
423 if( nB<(sizeof(mStack)*4)/(sizeof(mStack[0])*5) ){
424 m = mStack;
425 }else{
426 m = toFree = sqlite3_malloc64( ((i64)nB+1)*5LL*sizeof(m[0])/4 );
427 if( m==0 ) return -3;
428 }
429 cx = (char*)&m[nB+1];
430
431 /* Compute the Wagner edit distance */
432 m[0] = 0;
433 cx[0] = (char)dc;
434 cBprev = (char)dc;
435 for(xB=1; xB<=nB; xB++){
436 cBnext = zB[xB];
437 cB = zB[xB-1];
438 cx[xB] = cB;
439 m[xB] = m[xB-1] + insertOrDeleteCost(cBprev, cB, cBnext);
440 cBprev = cB;
441 }
442 cAprev = (char)dc;
443 for(xA=1; xA<=nA; xA++){
444 int lastA = (xA==nA);
445 cA = zA[xA-1];
446 cAnext = zA[xA];
447 if( cA=='*' && lastA ) break;
448 d = m[0];
449 dc = cx[0];
450 m[0] = d + insertOrDeleteCost(cAprev, cA, cAnext);
451 cBprev = 0;
452 for(xB=1; xB<=nB; xB++){
453 int totalCost, insCost, delCost, subCost, ncx;
454 cB = zB[xB-1];
455 cBnext = zB[xB];
456
457 /* Cost to insert cB */
458 insCost = insertOrDeleteCost(cx[xB-1], cB, cBnext);
459 if( lastA ) insCost /= FINAL_INS_COST_DIV;
460
461 /* Cost to delete cA */
462 delCost = insertOrDeleteCost(cx[xB], cA, cBnext);
463
464 /* Cost to substitute cA->cB */
465 subCost = substituteCost(cx[xB-1], cA, cB);
466
467 /* Best cost */
468 totalCost = insCost + m[xB-1];
469 ncx = cB;
470 if( (delCost + m[xB])<totalCost ){
471 totalCost = delCost + m[xB];
472 ncx = cA;
473 }
474 if( (subCost + d)<totalCost ){
475 totalCost = subCost + d;
476 }
477
478 #if 0
479 printf("%d,%d d=%4d u=%4d r=%4d dc=%c cA=%c cB=%c"
480 " ins=%4d del=%4d sub=%4d t=%4d ncx=%c\n",
481 xA, xB, d, m[xB], m[xB-1], dc?dc:' ', cA, cB,
482 insCost, delCost, subCost, totalCost, ncx?ncx:' ');
483 #endif
484
485 /* Update the matrix */
486 d = m[xB];
487 dc = cx[xB];
488 m[xB] = totalCost;
489 cx[xB] = (char)ncx;
490 cBprev = cB;
491 }
492 cAprev = cA;
493 }
494
495 /* Free the wagner matrix and return the result */
496 if( cA=='*' ){
497 res = m[1];
498 for(xB=1; xB<=nB; xB++){
499 if( m[xB]<res ){
500 res = m[xB];
501 if( pnMatch ) *pnMatch = xB+nMatch;
502 }
503 }
504 }else{
505 res = m[nB];
506 /* In the current implementation, pnMatch is always NULL if zA does
507 ** not end in "*" */
508 assert( pnMatch==0 );
509 }
510 sqlite3_free(toFree);
511 return res;
512 }
513
514 /*
515 ** Function: editdist(A,B)
516 **
517 ** Return the cost of transforming string A into string B. Both strings
518 ** must be pure ASCII text. If A ends with '*' then it is assumed to be
519 ** a prefix of B and extra characters on the end of B have minimal additional
520 ** cost.
521 */
522 static void editdistSqlFunc(
523 sqlite3_context *context,
524 int argc,
525 sqlite3_value **argv
526 ){
527 int res = editdist1(
528 (const char*)sqlite3_value_text(argv[0]),
529 (const char*)sqlite3_value_text(argv[1]),
530 0);
531 if( res<0 ){
532 if( res==(-3) ){
533 sqlite3_result_error_nomem(context);
534 }else if( res==(-4) ){
535 sqlite3_result_error_toobig(context);
536 }else if( res==(-2) ){
537 sqlite3_result_error(context, "non-ASCII input to editdist()", -1);
538 }else{
539 sqlite3_result_error(context, "NULL input to editdist()", -1);
540 }
541 }else{
542 sqlite3_result_int(context, res);
543 }
544 }
545
546 /* End of the fixed-cost edit distance implementation
547 ******************************************************************************
548 *****************************************************************************
549 ** Begin: Configurable cost unicode edit distance routines
550 */
551 /* Forward declaration of structures */
552 typedef struct EditDist3Cost EditDist3Cost;
553 typedef struct EditDist3Config EditDist3Config;
554 typedef struct EditDist3Point EditDist3Point;
555 typedef struct EditDist3From EditDist3From;
556 typedef struct EditDist3FromString EditDist3FromString;
557 typedef struct EditDist3To EditDist3To;
558 typedef struct EditDist3ToString EditDist3ToString;
559 typedef struct EditDist3Lang EditDist3Lang;
560
561
562 /*
563 ** An entry in the edit cost table
564 */
565 struct EditDist3Cost {
566 EditDist3Cost *pNext; /* Next cost element */
567 u8 nFrom; /* Number of bytes in aFrom */
568 u8 nTo; /* Number of bytes in aTo */
569 u16 iCost; /* Cost of this transformation */
570 char a[4] ; /* FROM string followed by TO string */
571 /* Additional TO and FROM string bytes appended as necessary */
572 };
573
574 /*
575 ** Edit costs for a particular language ID
576 */
577 struct EditDist3Lang {
578 int iLang; /* Language ID */
579 int iInsCost; /* Default insertion cost */
580 int iDelCost; /* Default deletion cost */
581 int iSubCost; /* Default substitution cost */
582 EditDist3Cost *pCost; /* Costs */
583 };
584
585
586 /*
587 ** The default EditDist3Lang object, with default costs.
588 */
589 static const EditDist3Lang editDist3Lang = { 0, 100, 100, 150, 0 };
590
591 /*
592 ** Complete configuration
593 */
594 struct EditDist3Config {
595 int nLang; /* Number of language IDs. Size of a[] */
596 EditDist3Lang *a; /* One for each distinct language ID */
597 };
598
599 /*
600 ** Extra information about each character in the FROM string.
601 */
602 struct EditDist3From {
603 int nSubst; /* Number of substitution cost entries */
604 int nDel; /* Number of deletion cost entries */
605 int nByte; /* Number of bytes in this character */
606 EditDist3Cost **apSubst; /* Array of substitution costs for this element */
607 EditDist3Cost **apDel; /* Array of deletion cost entries */
608 };
609
610 /*
611 ** A precompiled FROM string.
612 *
613 ** In the common case we expect the FROM string to be reused multiple times.
614 ** In other words, the common case will be to measure the edit distance
615 ** from a single origin string to multiple target strings.
616 */
617 struct EditDist3FromString {
618 char *z; /* The complete text of the FROM string */
619 int n; /* Number of characters in the FROM string */
620 int isPrefix; /* True if ends with '*' character */
621 EditDist3From *a; /* Extra info about each char of the FROM string */
622 };
623
624 /*
625 ** Extra information about each character in the TO string.
626 */
627 struct EditDist3To {
628 int nIns; /* Number of insertion cost entries */
629 int nByte; /* Number of bytes in this character */
630 EditDist3Cost **apIns; /* Array of deletion cost entries */
631 };
632
633 /*
634 ** A precompiled FROM string
635 */
636 struct EditDist3ToString {
637 char *z; /* The complete text of the TO string */
638 int n; /* Number of characters in the TO string */
639 EditDist3To *a; /* Extra info about each char of the TO string */
640 };
641
642 /*
643 ** Clear or delete an instance of the object that records all edit-distance
644 ** weights.
645 */
646 static void editDist3ConfigClear(EditDist3Config *p){
647 int i;
648 if( p==0 ) return;
649 for(i=0; i<p->nLang; i++){
650 EditDist3Cost *pCost, *pNext;
651 pCost = p->a[i].pCost;
652 while( pCost ){
653 pNext = pCost->pNext;
654 sqlite3_free(pCost);
655 pCost = pNext;
656 }
657 }
658 sqlite3_free(p->a);
659 memset(p, 0, sizeof(*p));
660 }
661 static void editDist3ConfigDelete(void *pIn){
662 EditDist3Config *p = (EditDist3Config*)pIn;
663 editDist3ConfigClear(p);
664 sqlite3_free(p);
665 }
666
667 /* Compare the FROM values of two EditDist3Cost objects, for sorting.
668 ** Return negative, zero, or positive if the A is less than, equal to,
669 ** or greater than B.
670 */
671 static int editDist3CostCompare(EditDist3Cost *pA, EditDist3Cost *pB){
672 int n = pA->nFrom;
673 int rc;
674 if( n>pB->nFrom ) n = pB->nFrom;
675 rc = strncmp(pA->a, pB->a, n);
676 if( rc==0 ) rc = pA->nFrom - pB->nFrom;
677 return rc;
678 }
679
680 /*
681 ** Merge together two sorted lists of EditDist3Cost objects, in order
682 ** of increasing FROM.
683 */
684 static EditDist3Cost *editDist3CostMerge(
685 EditDist3Cost *pA,
686 EditDist3Cost *pB
687 ){
688 EditDist3Cost *pHead = 0;
689 EditDist3Cost **ppTail = &pHead;
690 EditDist3Cost *p;
691 while( pA && pB ){
692 if( editDist3CostCompare(pA,pB)<=0 ){
693 p = pA;
694 pA = pA->pNext;
695 }else{
696 p = pB;
697 pB = pB->pNext;
698 }
699 *ppTail = p;
700 ppTail = &p->pNext;
701 }
702 if( pA ){
703 *ppTail = pA;
704 }else{
705 *ppTail = pB;
706 }
707 return pHead;
708 }
709
710 /*
711 ** Sort a list of EditDist3Cost objects into order of increasing FROM
712 */
713 static EditDist3Cost *editDist3CostSort(EditDist3Cost *pList){
714 EditDist3Cost *ap[60], *p;
715 int i;
716 int mx = 0;
717 ap[0] = 0;
718 ap[1] = 0;
719 while( pList ){
720 p = pList;
721 pList = p->pNext;
722 p->pNext = 0;
723 for(i=0; ap[i]; i++){
724 p = editDist3CostMerge(ap[i],p);
725 ap[i] = 0;
726 }
727 ap[i] = p;
728 if( i>mx ){
729 mx = i;
730 ap[i+1] = 0;
731 }
732 }
733 p = 0;
734 for(i=0; i<=mx; i++){
735 if( ap[i] ) p = editDist3CostMerge(p,ap[i]);
736 }
737 return p;
738 }
739
740 /*
741 ** Load all edit-distance weights from a table.
742 */
743 static int editDist3ConfigLoad(
744 EditDist3Config *p, /* The edit distance configuration to load */
745 sqlite3 *db, /* Load from this database */
746 const char *zTable /* Name of the table from which to load */
747 ){
748 sqlite3_stmt *pStmt;
749 int rc, rc2;
750 char *zSql;
751 int iLangPrev = -9999;
752 EditDist3Lang *pLang = 0;
753
754 zSql = sqlite3_mprintf("SELECT iLang, cFrom, cTo, iCost"
755 " FROM \"%w\" WHERE iLang>=0 ORDER BY iLang", zTable);
756 if( zSql==0 ) return SQLITE_NOMEM;
757 rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
758 sqlite3_free(zSql);
759 if( rc ) return rc;
760 editDist3ConfigClear(p);
761 while( sqlite3_step(pStmt)==SQLITE_ROW ){
762 int iLang = sqlite3_column_int(pStmt, 0);
763 const char *zFrom = (const char*)sqlite3_column_text(pStmt, 1);
764 int nFrom = zFrom ? sqlite3_column_bytes(pStmt, 1) : 0;
765 const char *zTo = (const char*)sqlite3_column_text(pStmt, 2);
766 int nTo = zTo ? sqlite3_column_bytes(pStmt, 2) : 0;
767 int iCost = sqlite3_column_int(pStmt, 3);
768
769 assert( zFrom!=0 || nFrom==0 );
770 assert( zTo!=0 || nTo==0 );
771 if( nFrom>100 || nTo>100 ) continue;
772 if( iCost<0 ) continue;
773 if( iCost>=10000 ) continue; /* Costs above 10K are considered infinite */
774 if( pLang==0 || iLang!=iLangPrev ){
775 EditDist3Lang *pNew;
776 pNew = sqlite3_realloc64(p->a, ((i64)p->nLang+1)*sizeof(p->a[0]));
777 if( pNew==0 ){ rc = SQLITE_NOMEM; break; }
778 p->a = pNew;
779 pLang = &p->a[p->nLang];
780 p->nLang++;
781 pLang->iLang = iLang;
782 pLang->iInsCost = 100;
783 pLang->iDelCost = 100;
784 pLang->iSubCost = 150;
785 pLang->pCost = 0;
786 iLangPrev = iLang;
787 }
788 if( nFrom==1 && zFrom[0]=='?' && nTo==0 ){
789 pLang->iDelCost = iCost;
790 }else if( nFrom==0 && nTo==1 && zTo[0]=='?' ){
791 pLang->iInsCost = iCost;
792 }else if( nFrom==1 && nTo==1 && zFrom[0]=='?' && zTo[0]=='?' ){
793 pLang->iSubCost = iCost;
794 }else{
795 EditDist3Cost *pCost;
796 int nExtra = nFrom + nTo - 4;
797 if( nExtra<0 ) nExtra = 0;
798 pCost = sqlite3_malloc64( sizeof(*pCost) + nExtra );
799 if( pCost==0 ){ rc = SQLITE_NOMEM; break; }
800 pCost->nFrom = (u8)nFrom;
801 pCost->nTo = (u8)nTo;
802 pCost->iCost = (u16)iCost;
803 memcpy(pCost->a, zFrom, nFrom);
804 memcpy(pCost->a + nFrom, zTo, nTo);
805 pCost->pNext = pLang->pCost;
806 pLang->pCost = pCost;
807 }
808 }
809 rc2 = sqlite3_finalize(pStmt);
810 if( rc==SQLITE_OK ) rc = rc2;
811 if( rc==SQLITE_OK ){
812 int iLang;
813 for(iLang=0; iLang<p->nLang; iLang++){
814 p->a[iLang].pCost = editDist3CostSort(p->a[iLang].pCost);
815 }
816 }
817 return rc;
818 }
819
820 /*
821 ** Return the length (in bytes) of a utf-8 character. Or return a maximum
822 ** of N.
823 */
824 static int utf8Len(unsigned char c, int N){
825 int len = 1;
826 if( c>0x7f ){
827 if( (c&0xe0)==0xc0 ){
828 len = 2;
829 }else if( (c&0xf0)==0xe0 ){
830 len = 3;
831 }else{
832 len = 4;
833 }
834 }
835 if( len>N ) len = N;
836 return len;
837 }
838
839 /*
840 ** Return TRUE (non-zero) if the To side of the given cost matches
841 ** the given string.
842 */
843 static int matchTo(EditDist3Cost *p, const char *z, int n){
844 assert( n>0 );
845 if( p->a[p->nFrom]!=z[0] ) return 0;
846 if( p->nTo>n ) return 0;
847 if( strncmp(p->a+p->nFrom, z, p->nTo)!=0 ) return 0;
848 return 1;
849 }
850
851 /*
852 ** Return TRUE (non-zero) if the From side of the given cost matches
853 ** the given string.
854 */
855 static int matchFrom(EditDist3Cost *p, const char *z, int n){
856 assert( p->nFrom<=n );
857 if( p->nFrom ){
858 if( p->a[0]!=z[0] ) return 0;
859 if( strncmp(p->a, z, p->nFrom)!=0 ) return 0;
860 }
861 return 1;
862 }
863
864 /*
865 ** Return TRUE (non-zero) of the next FROM character and the next TO
866 ** character are the same.
867 */
868 static int matchFromTo(
869 EditDist3FromString *pStr, /* Left hand string */
870 int n1, /* Index of comparison character on the left */
871 const char *z2, /* Right-handl comparison character */
872 int n2 /* Bytes remaining in z2[] */
873 ){
874 int b1 = pStr->a[n1].nByte;
875 if( b1>n2 ) return 0;
876 assert( b1>0 );
877 if( pStr->z[n1]!=z2[0] ) return 0;
878 if( strncmp(pStr->z+n1, z2, b1)!=0 ) return 0;
879 return 1;
880 }
881
882 /*
883 ** Delete an EditDist3FromString objecct
884 */
885 static void editDist3FromStringDelete(EditDist3FromString *p){
886 int i;
887 if( p ){
888 for(i=0; i<p->n; i++){
889 sqlite3_free(p->a[i].apDel);
890 sqlite3_free(p->a[i].apSubst);
891 }
892 sqlite3_free(p);
893 }
894 }
895
896 /*
897 ** Create a EditDist3FromString object.
898 */
899 static EditDist3FromString *editDist3FromStringNew(
900 const EditDist3Lang *pLang,
901 const char *z,
902 int n
903 ){
904 EditDist3FromString *pStr;
905 EditDist3Cost *p;
906 int i;
907
908 if( z==0 ) return 0;
909 if( n<0 ) n = (int)strlen(z);
910 pStr = sqlite3_malloc64( sizeof(*pStr) + sizeof(pStr->a[0])*n + (i64)n + 1 );
911 if( pStr==0 ) return 0;
912 pStr->a = (EditDist3From*)&pStr[1];
913 memset(pStr->a, 0, sizeof(pStr->a[0])*n);
914 pStr->n = n;
915 pStr->z = (char*)&pStr->a[n];
916 memcpy(pStr->z, z, n+1);
917 if( n && z[n-1]=='*' ){
918 pStr->isPrefix = 1;
919 n--;
920 pStr->n--;
921 pStr->z[n] = 0;
922 }else{
923 pStr->isPrefix = 0;
924 }
925
926 for(i=0; i<n; i++){
927 EditDist3From *pFrom = &pStr->a[i];
928 memset(pFrom, 0, sizeof(*pFrom));
929 pFrom->nByte = utf8Len((unsigned char)z[i], n-i);
930 for(p=pLang->pCost; p; p=p->pNext){
931 EditDist3Cost **apNew;
932 if( i+p->nFrom>n ) continue;
933 if( matchFrom(p, z+i, n-i)==0 ) continue;
934 if( p->nTo==0 ){
935 apNew = sqlite3_realloc64(pFrom->apDel,
936 sizeof(*apNew)*((i64)pFrom->nDel+1));
937 if( apNew==0 ) break;
938 pFrom->apDel = apNew;
939 apNew[pFrom->nDel++] = p;
940 }else{
941 apNew = sqlite3_realloc64(pFrom->apSubst,
942 sizeof(*apNew)*((i64)pFrom->nSubst+1));
943 if( apNew==0 ) break;
944 pFrom->apSubst = apNew;
945 apNew[pFrom->nSubst++] = p;
946 }
947 }
948 if( p ){
949 editDist3FromStringDelete(pStr);
950 pStr = 0;
951 break;
952 }
953 }
954 return pStr;
955 }
956
957 /*
958 ** Update entry m[i] such that it is the minimum of its current value
959 ** and m[j]+iCost.
960 */
961 static void updateCost(
962 unsigned int *m,
963 int i,
964 int j,
965 int iCost
966 ){
967 unsigned int b;
968 assert( iCost>=0 );
969 assert( iCost<10000 );
970 b = m[j] + iCost;
971 if( b<m[i] ) m[i] = b;
972 }
973
974 /*
975 ** How much stack space (int bytes) to use for Wagner matrix in
976 ** editDist3Core(). If more space than this is required, the entire
977 ** matrix is taken from the heap. To reduce the load on the memory
978 ** allocator, make this value as large as practical for the
979 ** architecture in use.
980 */
981 #ifndef SQLITE_SPELLFIX_STACKALLOC_SZ
982 # define SQLITE_SPELLFIX_STACKALLOC_SZ (1024)
983 #endif
984
985 /* Compute the edit distance between two strings.
986 **
987 ** If an error occurs, return a negative number which is the error code.
988 **
989 ** If pnMatch is not NULL, then *pnMatch is set to the number of characters
990 ** (not bytes) in z2 that matched the search pattern in *pFrom. If pFrom does
991 ** not contain the pattern for a prefix-search, then this is always the number
992 ** of characters in z2. If pFrom does contain a prefix search pattern, then
993 ** it is the number of characters in the prefix of z2 that was deemed to
994 ** match pFrom.
995 */
996 static int editDist3Core(
997 EditDist3FromString *pFrom, /* The FROM string */
998 const char *z2, /* The TO string */
999 int n2, /* Length of the TO string */
1000 const EditDist3Lang *pLang, /* Edit weights for a particular language ID */
1001 int *pnMatch /* OUT: Characters in matched prefix */
1002 ){
1003 int k, n;
1004 int i1, b1;
1005 int i2, b2;
1006 EditDist3FromString f = *pFrom;
1007 EditDist3To *a2;
1008 unsigned int *m;
1009 unsigned int *pToFree;
1010 int szRow;
1011 EditDist3Cost *p;
1012 int res;
1013 sqlite3_uint64 nByte;
1014 unsigned int stackSpace[SQLITE_SPELLFIX_STACKALLOC_SZ/sizeof(unsigned int)];
1015
1016 /* allocate the Wagner matrix and the aTo[] array for the TO string */
1017 if( n2>10000 ) return -2;
1018 if( f.n>10000 ) return -2;
1019 n = (f.n+1)*(n2+1);
1020 n = (n+1)&~1;
1021 nByte = n*sizeof(m[0]) + sizeof(a2[0])*n2;
1022 if( nByte<=sizeof(stackSpace) ){
1023 m = stackSpace;
1024 pToFree = 0;
1025 }else{
1026 m = pToFree = sqlite3_malloc64( nByte );
1027 if( m==0 ) return -1; /* Out of memory */
1028 }
1029 a2 = (EditDist3To*)&m[n];
1030 memset(a2, 0, sizeof(a2[0])*n2);
1031
1032 /* Fill in the a1[] matrix for all characters of the TO string */
1033 for(i2=0; i2<n2; i2++){
1034 a2[i2].nByte = utf8Len((unsigned char)z2[i2], n2-i2);
1035 for(p=pLang->pCost; p; p=p->pNext){
1036 EditDist3Cost **apNew;
1037 if( p->nFrom>0 ) break;
1038 if( i2+p->nTo>n2 ) continue;
1039 if( p->a[0]>z2[i2] ) break;
1040 if( matchTo(p, z2+i2, n2-i2)==0 ) continue;
1041 a2[i2].nIns++;
1042 apNew = sqlite3_realloc64(a2[i2].apIns, sizeof(*apNew)*a2[i2].nIns);
1043 if( apNew==0 ){
1044 res = -1; /* Out of memory */
1045 goto editDist3Abort;
1046 }
1047 a2[i2].apIns = apNew;
1048 a2[i2].apIns[a2[i2].nIns-1] = p;
1049 }
1050 }
1051
1052 /* Prepare to compute the minimum edit distance */
1053 szRow = f.n+1;
1054 memset(m, 0x01, (n2+1)*szRow*sizeof(m[0]));
1055 m[0] = 0;
1056
1057 /* First fill in the top-row of the matrix with FROM deletion costs */
1058 for(i1=0; i1<f.n; i1 += b1){
1059 b1 = f.a[i1].nByte;
1060 updateCost(m, i1+b1, i1, pLang->iDelCost);
1061 for(k=0; k<f.a[i1].nDel; k++){
1062 p = f.a[i1].apDel[k];
1063 updateCost(m, i1+p->nFrom, i1, p->iCost);
1064 }
1065 }
1066
1067 /* Fill in all subsequent rows, top-to-bottom, left-to-right */
1068 for(i2=0; i2<n2; i2 += b2){
1069 int rx; /* Starting index for current row */
1070 int rxp; /* Starting index for previous row */
1071 b2 = a2[i2].nByte;
1072 rx = szRow*(i2+b2);
1073 rxp = szRow*i2;
1074 updateCost(m, rx, rxp, pLang->iInsCost);
1075 for(k=0; k<a2[i2].nIns; k++){
1076 p = a2[i2].apIns[k];
1077 updateCost(m, szRow*(i2+p->nTo), rxp, p->iCost);
1078 }
1079 for(i1=0; i1<f.n; i1+=b1){
1080 int cx; /* Index of current cell */
1081 int cxp; /* Index of cell immediately to the left */
1082 int cxd; /* Index of cell to the left and one row above */
1083 int cxu; /* Index of cell immediately above */
1084 b1 = f.a[i1].nByte;
1085 cxp = rx + i1;
1086 cx = cxp + b1;
1087 cxd = rxp + i1;
1088 cxu = cxd + b1;
1089 updateCost(m, cx, cxp, pLang->iDelCost);
1090 for(k=0; k<f.a[i1].nDel; k++){
1091 p = f.a[i1].apDel[k];
1092 updateCost(m, cxp+p->nFrom, cxp, p->iCost);
1093 }
1094 updateCost(m, cx, cxu, pLang->iInsCost);
1095 if( matchFromTo(&f, i1, z2+i2, n2-i2) ){
1096 updateCost(m, cx, cxd, 0);
1097 }
1098 updateCost(m, cx, cxd, pLang->iSubCost);
1099 for(k=0; k<f.a[i1].nSubst; k++){
1100 p = f.a[i1].apSubst[k];
1101 if( matchTo(p, z2+i2, n2-i2) ){
1102 updateCost(m, cxd+p->nFrom+szRow*p->nTo, cxd, p->iCost);
1103 }
1104 }
1105 }
1106 }
1107
1108 #if 0 /* Enable for debugging */
1109 printf(" ^");
1110 for(i1=0; i1<f.n; i1++) printf(" %c-%2x", f.z[i1], f.z[i1]&0xff);
1111 printf("\n ^:");
1112 for(i1=0; i1<szRow; i1++){
1113 int v = m[i1];
1114 if( v>9999 ) printf(" ****");
1115 else printf(" %4d", v);
1116 }
1117 printf("\n");
1118 for(i2=0; i2<n2; i2++){
1119 printf("%c-%02x:", z2[i2], z2[i2]&0xff);
1120 for(i1=0; i1<szRow; i1++){
1121 int v = m[(i2+1)*szRow+i1];
1122 if( v>9999 ) printf(" ****");
1123 else printf(" %4d", v);
1124 }
1125 printf("\n");
1126 }
1127 #endif
1128
1129 /* Free memory allocations and return the result */
1130 res = (int)m[szRow*(n2+1)-1];
1131 n = n2;
1132 if( f.isPrefix ){
1133 for(i2=1; i2<=n2; i2++){
1134 int b = m[szRow*i2-1];
1135 if( b<=res ){
1136 res = b;
1137 n = i2 - 1;
1138 }
1139 }
1140 }
1141 if( pnMatch ){
1142 int nExtra = 0;
1143 for(k=0; k<n; k++){
1144 if( (z2[k] & 0xc0)==0x80 ) nExtra++;
1145 }
1146 *pnMatch = n - nExtra;
1147 }
1148
1149 editDist3Abort:
1150 for(i2=0; i2<n2; i2++) sqlite3_free(a2[i2].apIns);
1151 sqlite3_free(pToFree);
1152 return res;
1153 }
1154
1155 /*
1156 ** Get an appropriate EditDist3Lang object.
1157 */
1158 static const EditDist3Lang *editDist3FindLang(
1159 EditDist3Config *pConfig,
1160 int iLang
1161 ){
1162 int i;
1163 for(i=0; i<pConfig->nLang; i++){
1164 if( pConfig->a[i].iLang==iLang ) return &pConfig->a[i];
1165 }
1166 return &editDist3Lang;
1167 }
1168
1169 /*
1170 ** Function: editdist3(A,B,iLang)
1171 ** editdist3(tablename)
1172 **
1173 ** Return the cost of transforming string A into string B using edit
1174 ** weights for iLang.
1175 **
1176 ** The second form loads edit weights into memory from a table.
1177 */
1178 static void editDist3SqlFunc(
1179 sqlite3_context *context,
1180 int argc,
1181 sqlite3_value **argv
1182 ){
1183 EditDist3Config *pConfig = (EditDist3Config*)sqlite3_user_data(context);
1184 sqlite3 *db = sqlite3_context_db_handle(context);
1185 int rc;
1186 if( argc==1 ){
1187 const char *zTable = (const char*)sqlite3_value_text(argv[0]);
1188 rc = editDist3ConfigLoad(pConfig, db, zTable);
1189 if( rc ) sqlite3_result_error_code(context, rc);
1190 }else{
1191 const char *zA = (const char*)sqlite3_value_text(argv[0]);
1192 const char *zB = (const char*)sqlite3_value_text(argv[1]);
1193 int nA = sqlite3_value_bytes(argv[0]);
1194 int nB = sqlite3_value_bytes(argv[1]);
1195 int iLang = argc==3 ? sqlite3_value_int(argv[2]) : 0;
1196 const EditDist3Lang *pLang = editDist3FindLang(pConfig, iLang);
1197 EditDist3FromString *pFrom;
1198 int dist;
1199
1200 pFrom = editDist3FromStringNew(pLang, zA, nA);
1201 if( pFrom==0 ){
1202 sqlite3_result_error_nomem(context);
1203 return;
1204 }
1205 dist = editDist3Core(pFrom, zB, nB, pLang, 0);
1206 editDist3FromStringDelete(pFrom);
1207 if( dist==(-1) ){
1208 sqlite3_result_error_nomem(context);
1209 }else if( dist==(-2) ){
1210 sqlite3_result_error_toobig(context);
1211 }else{
1212 sqlite3_result_int(context, dist);
1213 }
1214 }
1215 }
1216
1217 /*
1218 ** Register the editDist3 function with SQLite
1219 */
1220 static int editDist3Install(sqlite3 *db){
1221 int rc;
1222 EditDist3Config *pConfig = sqlite3_malloc64( sizeof(*pConfig) );
1223 if( pConfig==0 ) return SQLITE_NOMEM;
1224 memset(pConfig, 0, sizeof(*pConfig));
1225 rc = sqlite3_create_function_v2(db, "editdist3",
1226 2, SQLITE_UTF8|SQLITE_DETERMINISTIC, pConfig,
1227 editDist3SqlFunc, 0, 0, 0);
1228 if( rc==SQLITE_OK ){
1229 rc = sqlite3_create_function_v2(db, "editdist3",
1230 3, SQLITE_UTF8|SQLITE_DETERMINISTIC, pConfig,
1231 editDist3SqlFunc, 0, 0, 0);
1232 }
1233 if( rc==SQLITE_OK ){
1234 rc = sqlite3_create_function_v2(db, "editdist3",
1235 1, SQLITE_UTF8|SQLITE_DETERMINISTIC, pConfig,
1236 editDist3SqlFunc, 0, 0, editDist3ConfigDelete);
1237 }else{
1238 sqlite3_free(pConfig);
1239 }
1240 return rc;
1241 }
1242 /* End configurable cost unicode edit distance routines
1243 ******************************************************************************
1244 ******************************************************************************
1245 ** Begin transliterate unicode-to-ascii implementation
1246 */
1247
1248 #if !SQLITE_AMALGAMATION
1249 /*
1250 ** This lookup table is used to help decode the first byte of
1251 ** a multi-byte UTF8 character.
1252 */
1253 static const unsigned char sqlite3Utf8Trans1[] = {
1254 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
1255 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
1256 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
1257 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
1258 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
1259 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
1260 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
1261 0x00, 0x01, 0x02, 0x03, 0x00, 0x01, 0x00, 0x00,
1262 };
1263 #endif
1264
1265 /*
1266 ** Return the value of the first UTF-8 character in the string.
1267 */
1268 static int utf8Read(const unsigned char *z, int n, int *pSize){
1269 int c, i;
1270
1271 /* All callers to this routine (in the current implementation)
1272 ** always have n>0. */
1273 if( NEVER(n==0) ){
1274 c = i = 0;
1275 }else{
1276 c = z[0];
1277 i = 1;
1278 if( c>=0xc0 ){
1279 c = sqlite3Utf8Trans1[c-0xc0];
1280 while( i<n && (z[i] & 0xc0)==0x80 ){
1281 c = (c<<6) + (0x3f & z[i++]);
1282 }
1283 }
1284 }
1285 *pSize = i;
1286 return c;
1287 }
1288
1289 /*
1290 ** Return the number of characters in the utf-8 string in the nIn byte
1291 ** buffer pointed to by zIn.
1292 */
1293 static int utf8Charlen(const char *zIn, int nIn){
1294 int i;
1295 int nChar = 0;
1296 for(i=0; i<nIn; nChar++){
1297 int sz;
1298 utf8Read((const unsigned char *)&zIn[i], nIn-i, &sz);
1299 i += sz;
1300 }
1301 return nChar;
1302 }
1303
1304 typedef struct Transliteration Transliteration;
1305 struct Transliteration {
1306 unsigned short int cFrom;
1307 unsigned char cTo0, cTo1, cTo2, cTo3;
1308 #ifdef SQLITE_SPELLFIX_5BYTE_MAPPINGS
1309 unsigned char cTo4;
1310 #endif
1311 };
1312
1313 /*
1314 ** Table of translations from unicode characters into ASCII.
1315 */
1316 static const Transliteration translit[] = {
1317 { 0x00A0, 0x20, 0x00, 0x00, 0x00 }, /*   to */
1318 { 0x00B5, 0x75, 0x00, 0x00, 0x00 }, /* µ to u */
1319 { 0x00C0, 0x41, 0x00, 0x00, 0x00 }, /* À to A */
1320 { 0x00C1, 0x41, 0x00, 0x00, 0x00 }, /* Á to A */
1321 { 0x00C2, 0x41, 0x00, 0x00, 0x00 }, /* Â to A */
1322 { 0x00C3, 0x41, 0x00, 0x00, 0x00 }, /* Ã to A */
1323 { 0x00C4, 0x41, 0x65, 0x00, 0x00 }, /* Ä to Ae */
1324 { 0x00C5, 0x41, 0x61, 0x00, 0x00 }, /* Å to Aa */
1325 { 0x00C6, 0x41, 0x45, 0x00, 0x00 }, /* Æ to AE */
1326 { 0x00C7, 0x43, 0x00, 0x00, 0x00 }, /* Ç to C */
1327 { 0x00C8, 0x45, 0x00, 0x00, 0x00 }, /* È to E */
1328 { 0x00C9, 0x45, 0x00, 0x00, 0x00 }, /* É to E */
1329 { 0x00CA, 0x45, 0x00, 0x00, 0x00 }, /* Ê to E */
1330 { 0x00CB, 0x45, 0x00, 0x00, 0x00 }, /* Ë to E */
1331 { 0x00CC, 0x49, 0x00, 0x00, 0x00 }, /* Ì to I */
1332 { 0x00CD, 0x49, 0x00, 0x00, 0x00 }, /* Í to I */
1333 { 0x00CE, 0x49, 0x00, 0x00, 0x00 }, /* Î to I */
1334 { 0x00CF, 0x49, 0x00, 0x00, 0x00 }, /* Ï to I */
1335 { 0x00D0, 0x44, 0x00, 0x00, 0x00 }, /* Ð to D */
1336 { 0x00D1, 0x4E, 0x00, 0x00, 0x00 }, /* Ñ to N */
1337 { 0x00D2, 0x4F, 0x00, 0x00, 0x00 }, /* Ò to O */
1338 { 0x00D3, 0x4F, 0x00, 0x00, 0x00 }, /* Ó to O */
1339 { 0x00D4, 0x4F, 0x00, 0x00, 0x00 }, /* Ô to O */
1340 { 0x00D5, 0x4F, 0x00, 0x00, 0x00 }, /* Õ to O */
1341 { 0x00D6, 0x4F, 0x65, 0x00, 0x00 }, /* Ö to Oe */
1342 { 0x00D7, 0x78, 0x00, 0x00, 0x00 }, /* × to x */
1343 { 0x00D8, 0x4F, 0x00, 0x00, 0x00 }, /* Ø to O */
1344 { 0x00D9, 0x55, 0x00, 0x00, 0x00 }, /* Ù to U */
1345 { 0x00DA, 0x55, 0x00, 0x00, 0x00 }, /* Ú to U */
1346 { 0x00DB, 0x55, 0x00, 0x00, 0x00 }, /* Û to U */
1347 { 0x00DC, 0x55, 0x65, 0x00, 0x00 }, /* Ü to Ue */
1348 { 0x00DD, 0x59, 0x00, 0x00, 0x00 }, /* Ý to Y */
1349 { 0x00DE, 0x54, 0x68, 0x00, 0x00 }, /* Þ to Th */
1350 { 0x00DF, 0x73, 0x73, 0x00, 0x00 }, /* ß to ss */
1351 { 0x00E0, 0x61, 0x00, 0x00, 0x00 }, /* à to a */
1352 { 0x00E1, 0x61, 0x00, 0x00, 0x00 }, /* á to a */
1353 { 0x00E2, 0x61, 0x00, 0x00, 0x00 }, /* â to a */
1354 { 0x00E3, 0x61, 0x00, 0x00, 0x00 }, /* ã to a */
1355 { 0x00E4, 0x61, 0x65, 0x00, 0x00 }, /* ä to ae */
1356 { 0x00E5, 0x61, 0x61, 0x00, 0x00 }, /* å to aa */
1357 { 0x00E6, 0x61, 0x65, 0x00, 0x00 }, /* æ to ae */
1358 { 0x00E7, 0x63, 0x00, 0x00, 0x00 }, /* ç to c */
1359 { 0x00E8, 0x65, 0x00, 0x00, 0x00 }, /* è to e */
1360 { 0x00E9, 0x65, 0x00, 0x00, 0x00 }, /* é to e */
1361 { 0x00EA, 0x65, 0x00, 0x00, 0x00 }, /* ê to e */
1362 { 0x00EB, 0x65, 0x00, 0x00, 0x00 }, /* ë to e */
1363 { 0x00EC, 0x69, 0x00, 0x00, 0x00 }, /* ì to i */
1364 { 0x00ED, 0x69, 0x00, 0x00, 0x00 }, /* í to i */
1365 { 0x00EE, 0x69, 0x00, 0x00, 0x00 }, /* î to i */
1366 { 0x00EF, 0x69, 0x00, 0x00, 0x00 }, /* ï to i */
1367 { 0x00F0, 0x64, 0x00, 0x00, 0x00 }, /* ð to d */
1368 { 0x00F1, 0x6E, 0x00, 0x00, 0x00 }, /* ñ to n */
1369 { 0x00F2, 0x6F, 0x00, 0x00, 0x00 }, /* ò to o */
1370 { 0x00F3, 0x6F, 0x00, 0x00, 0x00 }, /* ó to o */
1371 { 0x00F4, 0x6F, 0x00, 0x00, 0x00 }, /* ô to o */
1372 { 0x00F5, 0x6F, 0x00, 0x00, 0x00 }, /* õ to o */
1373 { 0x00F6, 0x6F, 0x65, 0x00, 0x00 }, /* ö to oe */
1374 { 0x00F7, 0x3A, 0x00, 0x00, 0x00 }, /* ÷ to : */
1375 { 0x00F8, 0x6F, 0x00, 0x00, 0x00 }, /* ø to o */
1376 { 0x00F9, 0x75, 0x00, 0x00, 0x00 }, /* ù to u */
1377 { 0x00FA, 0x75, 0x00, 0x00, 0x00 }, /* ú to u */
1378 { 0x00FB, 0x75, 0x00, 0x00, 0x00 }, /* û to u */
1379 { 0x00FC, 0x75, 0x65, 0x00, 0x00 }, /* ü to ue */
1380 { 0x00FD, 0x79, 0x00, 0x00, 0x00 }, /* ý to y */
1381 { 0x00FE, 0x74, 0x68, 0x00, 0x00 }, /* þ to th */
1382 { 0x00FF, 0x79, 0x00, 0x00, 0x00 }, /* ÿ to y */
1383 { 0x0100, 0x41, 0x00, 0x00, 0x00 }, /* Ā to A */
1384 { 0x0101, 0x61, 0x00, 0x00, 0x00 }, /* ā to a */
1385 { 0x0102, 0x41, 0x00, 0x00, 0x00 }, /* Ă to A */
1386 { 0x0103, 0x61, 0x00, 0x00, 0x00 }, /* ă to a */
1387 { 0x0104, 0x41, 0x00, 0x00, 0x00 }, /* Ą to A */
1388 { 0x0105, 0x61, 0x00, 0x00, 0x00 }, /* ą to a */
1389 { 0x0106, 0x43, 0x00, 0x00, 0x00 }, /* Ć to C */
1390 { 0x0107, 0x63, 0x00, 0x00, 0x00 }, /* ć to c */
1391 { 0x0108, 0x43, 0x68, 0x00, 0x00 }, /* Ĉ to Ch */
1392 { 0x0109, 0x63, 0x68, 0x00, 0x00 }, /* ĉ to ch */
1393 { 0x010A, 0x43, 0x00, 0x00, 0x00 }, /* Ċ to C */
1394 { 0x010B, 0x63, 0x00, 0x00, 0x00 }, /* ċ to c */
1395 { 0x010C, 0x43, 0x00, 0x00, 0x00 }, /* Č to C */
1396 { 0x010D, 0x63, 0x00, 0x00, 0x00 }, /* č to c */
1397 { 0x010E, 0x44, 0x00, 0x00, 0x00 }, /* Ď to D */
1398 { 0x010F, 0x64, 0x00, 0x00, 0x00 }, /* ď to d */
1399 { 0x0110, 0x44, 0x00, 0x00, 0x00 }, /* Đ to D */
1400 { 0x0111, 0x64, 0x00, 0x00, 0x00 }, /* đ to d */
1401 { 0x0112, 0x45, 0x00, 0x00, 0x00 }, /* Ē to E */
1402 { 0x0113, 0x65, 0x00, 0x00, 0x00 }, /* ē to e */
1403 { 0x0114, 0x45, 0x00, 0x00, 0x00 }, /* Ĕ to E */
1404 { 0x0115, 0x65, 0x00, 0x00, 0x00 }, /* ĕ to e */
1405 { 0x0116, 0x45, 0x00, 0x00, 0x00 }, /* Ė to E */
1406 { 0x0117, 0x65, 0x00, 0x00, 0x00 }, /* ė to e */
1407 { 0x0118, 0x45, 0x00, 0x00, 0x00 }, /* Ę to E */
1408 { 0x0119, 0x65, 0x00, 0x00, 0x00 }, /* ę to e */
1409 { 0x011A, 0x45, 0x00, 0x00, 0x00 }, /* Ě to E */
1410 { 0x011B, 0x65, 0x00, 0x00, 0x00 }, /* ě to e */
1411 { 0x011C, 0x47, 0x68, 0x00, 0x00 }, /* Ĝ to Gh */
1412 { 0x011D, 0x67, 0x68, 0x00, 0x00 }, /* ĝ to gh */
1413 { 0x011E, 0x47, 0x00, 0x00, 0x00 }, /* Ğ to G */
1414 { 0x011F, 0x67, 0x00, 0x00, 0x00 }, /* ğ to g */
1415 { 0x0120, 0x47, 0x00, 0x00, 0x00 }, /* Ġ to G */
1416 { 0x0121, 0x67, 0x00, 0x00, 0x00 }, /* ġ to g */
1417 { 0x0122, 0x47, 0x00, 0x00, 0x00 }, /* Ģ to G */
1418 { 0x0123, 0x67, 0x00, 0x00, 0x00 }, /* ģ to g */
1419 { 0x0124, 0x48, 0x68, 0x00, 0x00 }, /* Ĥ to Hh */
1420 { 0x0125, 0x68, 0x68, 0x00, 0x00 }, /* ĥ to hh */
1421 { 0x0126, 0x48, 0x00, 0x00, 0x00 }, /* Ħ to H */
1422 { 0x0127, 0x68, 0x00, 0x00, 0x00 }, /* ħ to h */
1423 { 0x0128, 0x49, 0x00, 0x00, 0x00 }, /* Ĩ to I */
1424 { 0x0129, 0x69, 0x00, 0x00, 0x00 }, /* ĩ to i */
1425 { 0x012A, 0x49, 0x00, 0x00, 0x00 }, /* Ī to I */
1426 { 0x012B, 0x69, 0x00, 0x00, 0x00 }, /* ī to i */
1427 { 0x012C, 0x49, 0x00, 0x00, 0x00 }, /* Ĭ to I */
1428 { 0x012D, 0x69, 0x00, 0x00, 0x00 }, /* ĭ to i */
1429 { 0x012E, 0x49, 0x00, 0x00, 0x00 }, /* Į to I */
1430 { 0x012F, 0x69, 0x00, 0x00, 0x00 }, /* į to i */
1431 { 0x0130, 0x49, 0x00, 0x00, 0x00 }, /* İ to I */
1432 { 0x0131, 0x69, 0x00, 0x00, 0x00 }, /* ı to i */
1433 { 0x0132, 0x49, 0x4A, 0x00, 0x00 }, /* IJ to IJ */
1434 { 0x0133, 0x69, 0x6A, 0x00, 0x00 }, /* ij to ij */
1435 { 0x0134, 0x4A, 0x68, 0x00, 0x00 }, /* Ĵ to Jh */
1436 { 0x0135, 0x6A, 0x68, 0x00, 0x00 }, /* ĵ to jh */
1437 { 0x0136, 0x4B, 0x00, 0x00, 0x00 }, /* Ķ to K */
1438 { 0x0137, 0x6B, 0x00, 0x00, 0x00 }, /* ķ to k */
1439 { 0x0138, 0x6B, 0x00, 0x00, 0x00 }, /* ĸ to k */
1440 { 0x0139, 0x4C, 0x00, 0x00, 0x00 }, /* Ĺ to L */
1441 { 0x013A, 0x6C, 0x00, 0x00, 0x00 }, /* ĺ to l */
1442 { 0x013B, 0x4C, 0x00, 0x00, 0x00 }, /* Ļ to L */
1443 { 0x013C, 0x6C, 0x00, 0x00, 0x00 }, /* ļ to l */
1444 { 0x013D, 0x4C, 0x00, 0x00, 0x00 }, /* Ľ to L */
1445 { 0x013E, 0x6C, 0x00, 0x00, 0x00 }, /* ľ to l */
1446 { 0x013F, 0x4C, 0x2E, 0x00, 0x00 }, /* Ŀ to L. */
1447 { 0x0140, 0x6C, 0x2E, 0x00, 0x00 }, /* ŀ to l. */
1448 { 0x0141, 0x4C, 0x00, 0x00, 0x00 }, /* Ł to L */
1449 { 0x0142, 0x6C, 0x00, 0x00, 0x00 }, /* ł to l */
1450 { 0x0143, 0x4E, 0x00, 0x00, 0x00 }, /* Ń to N */
1451 { 0x0144, 0x6E, 0x00, 0x00, 0x00 }, /* ń to n */
1452 { 0x0145, 0x4E, 0x00, 0x00, 0x00 }, /* Ņ to N */
1453 { 0x0146, 0x6E, 0x00, 0x00, 0x00 }, /* ņ to n */
1454 { 0x0147, 0x4E, 0x00, 0x00, 0x00 }, /* Ň to N */
1455 { 0x0148, 0x6E, 0x00, 0x00, 0x00 }, /* ň to n */
1456 { 0x0149, 0x27, 0x6E, 0x00, 0x00 }, /* ʼn to 'n */
1457 { 0x014A, 0x4E, 0x47, 0x00, 0x00 }, /* Ŋ to NG */
1458 { 0x014B, 0x6E, 0x67, 0x00, 0x00 }, /* ŋ to ng */
1459 { 0x014C, 0x4F, 0x00, 0x00, 0x00 }, /* Ō to O */
1460 { 0x014D, 0x6F, 0x00, 0x00, 0x00 }, /* ō to o */
1461 { 0x014E, 0x4F, 0x00, 0x00, 0x00 }, /* Ŏ to O */
1462 { 0x014F, 0x6F, 0x00, 0x00, 0x00 }, /* ŏ to o */
1463 { 0x0150, 0x4F, 0x00, 0x00, 0x00 }, /* Ő to O */
1464 { 0x0151, 0x6F, 0x00, 0x00, 0x00 }, /* ő to o */
1465 { 0x0152, 0x4F, 0x45, 0x00, 0x00 }, /* Œ to OE */
1466 { 0x0153, 0x6F, 0x65, 0x00, 0x00 }, /* œ to oe */
1467 { 0x0154, 0x52, 0x00, 0x00, 0x00 }, /* Ŕ to R */
1468 { 0x0155, 0x72, 0x00, 0x00, 0x00 }, /* ŕ to r */
1469 { 0x0156, 0x52, 0x00, 0x00, 0x00 }, /* Ŗ to R */
1470 { 0x0157, 0x72, 0x00, 0x00, 0x00 }, /* ŗ to r */
1471 { 0x0158, 0x52, 0x00, 0x00, 0x00 }, /* Ř to R */
1472 { 0x0159, 0x72, 0x00, 0x00, 0x00 }, /* ř to r */
1473 { 0x015A, 0x53, 0x00, 0x00, 0x00 }, /* Ś to S */
1474 { 0x015B, 0x73, 0x00, 0x00, 0x00 }, /* ś to s */
1475 { 0x015C, 0x53, 0x68, 0x00, 0x00 }, /* Ŝ to Sh */
1476 { 0x015D, 0x73, 0x68, 0x00, 0x00 }, /* ŝ to sh */
1477 { 0x015E, 0x53, 0x00, 0x00, 0x00 }, /* Ş to S */
1478 { 0x015F, 0x73, 0x00, 0x00, 0x00 }, /* ş to s */
1479 { 0x0160, 0x53, 0x00, 0x00, 0x00 }, /* Š to S */
1480 { 0x0161, 0x73, 0x00, 0x00, 0x00 }, /* š to s */
1481 { 0x0162, 0x54, 0x00, 0x00, 0x00 }, /* Ţ to T */
1482 { 0x0163, 0x74, 0x00, 0x00, 0x00 }, /* ţ to t */
1483 { 0x0164, 0x54, 0x00, 0x00, 0x00 }, /* Ť to T */
1484 { 0x0165, 0x74, 0x00, 0x00, 0x00 }, /* ť to t */
1485 { 0x0166, 0x54, 0x00, 0x00, 0x00 }, /* Ŧ to T */
1486 { 0x0167, 0x74, 0x00, 0x00, 0x00 }, /* ŧ to t */
1487 { 0x0168, 0x55, 0x00, 0x00, 0x00 }, /* Ũ to U */
1488 { 0x0169, 0x75, 0x00, 0x00, 0x00 }, /* ũ to u */
1489 { 0x016A, 0x55, 0x00, 0x00, 0x00 }, /* Ū to U */
1490 { 0x016B, 0x75, 0x00, 0x00, 0x00 }, /* ū to u */
1491 { 0x016C, 0x55, 0x00, 0x00, 0x00 }, /* Ŭ to U */
1492 { 0x016D, 0x75, 0x00, 0x00, 0x00 }, /* ŭ to u */
1493 { 0x016E, 0x55, 0x00, 0x00, 0x00 }, /* Ů to U */
1494 { 0x016F, 0x75, 0x00, 0x00, 0x00 }, /* ů to u */
1495 { 0x0170, 0x55, 0x00, 0x00, 0x00 }, /* Ű to U */
1496 { 0x0171, 0x75, 0x00, 0x00, 0x00 }, /* ű to u */
1497 { 0x0172, 0x55, 0x00, 0x00, 0x00 }, /* Ų to U */
1498 { 0x0173, 0x75, 0x00, 0x00, 0x00 }, /* ų to u */
1499 { 0x0174, 0x57, 0x00, 0x00, 0x00 }, /* Ŵ to W */
1500 { 0x0175, 0x77, 0x00, 0x00, 0x00 }, /* ŵ to w */
1501 { 0x0176, 0x59, 0x00, 0x00, 0x00 }, /* Ŷ to Y */
1502 { 0x0177, 0x79, 0x00, 0x00, 0x00 }, /* ŷ to y */
1503 { 0x0178, 0x59, 0x00, 0x00, 0x00 }, /* Ÿ to Y */
1504 { 0x0179, 0x5A, 0x00, 0x00, 0x00 }, /* Ź to Z */
1505 { 0x017A, 0x7A, 0x00, 0x00, 0x00 }, /* ź to z */
1506 { 0x017B, 0x5A, 0x00, 0x00, 0x00 }, /* Ż to Z */
1507 { 0x017C, 0x7A, 0x00, 0x00, 0x00 }, /* ż to z */
1508 { 0x017D, 0x5A, 0x00, 0x00, 0x00 }, /* Ž to Z */
1509 { 0x017E, 0x7A, 0x00, 0x00, 0x00 }, /* ž to z */
1510 { 0x017F, 0x73, 0x00, 0x00, 0x00 }, /* ſ to s */
1511 { 0x0192, 0x66, 0x00, 0x00, 0x00 }, /* ƒ to f */
1512 { 0x0218, 0x53, 0x00, 0x00, 0x00 }, /* Ș to S */
1513 { 0x0219, 0x73, 0x00, 0x00, 0x00 }, /* ș to s */
1514 { 0x021A, 0x54, 0x00, 0x00, 0x00 }, /* Ț to T */
1515 { 0x021B, 0x74, 0x00, 0x00, 0x00 }, /* ț to t */
1516 { 0x0386, 0x41, 0x00, 0x00, 0x00 }, /* Ά to A */
1517 { 0x0388, 0x45, 0x00, 0x00, 0x00 }, /* Έ to E */
1518 { 0x0389, 0x49, 0x00, 0x00, 0x00 }, /* Ή to I */
1519 { 0x038A, 0x49, 0x00, 0x00, 0x00 }, /* Ί to I */
1520 { 0x038C, 0x4f, 0x00, 0x00, 0x00 }, /* Ό to O */
1521 { 0x038E, 0x59, 0x00, 0x00, 0x00 }, /* Ύ to Y */
1522 { 0x038F, 0x4f, 0x00, 0x00, 0x00 }, /* Ώ to O */
1523 { 0x0390, 0x69, 0x00, 0x00, 0x00 }, /* ΐ to i */
1524 { 0x0391, 0x41, 0x00, 0x00, 0x00 }, /* Α to A */
1525 { 0x0392, 0x42, 0x00, 0x00, 0x00 }, /* Β to B */
1526 { 0x0393, 0x47, 0x00, 0x00, 0x00 }, /* Γ to G */
1527 { 0x0394, 0x44, 0x00, 0x00, 0x00 }, /* Δ to D */
1528 { 0x0395, 0x45, 0x00, 0x00, 0x00 }, /* Ε to E */
1529 { 0x0396, 0x5a, 0x00, 0x00, 0x00 }, /* Ζ to Z */
1530 { 0x0397, 0x49, 0x00, 0x00, 0x00 }, /* Η to I */
1531 { 0x0398, 0x54, 0x68, 0x00, 0x00 }, /* Θ to Th */
1532 { 0x0399, 0x49, 0x00, 0x00, 0x00 }, /* Ι to I */
1533 { 0x039A, 0x4b, 0x00, 0x00, 0x00 }, /* Κ to K */
1534 { 0x039B, 0x4c, 0x00, 0x00, 0x00 }, /* Λ to L */
1535 { 0x039C, 0x4d, 0x00, 0x00, 0x00 }, /* Μ to M */
1536 { 0x039D, 0x4e, 0x00, 0x00, 0x00 }, /* Ν to N */
1537 { 0x039E, 0x58, 0x00, 0x00, 0x00 }, /* Ξ to X */
1538 { 0x039F, 0x4f, 0x00, 0x00, 0x00 }, /* Ο to O */
1539 { 0x03A0, 0x50, 0x00, 0x00, 0x00 }, /* Π to P */
1540 { 0x03A1, 0x52, 0x00, 0x00, 0x00 }, /* Ρ to R */
1541 { 0x03A3, 0x53, 0x00, 0x00, 0x00 }, /* Σ to S */
1542 { 0x03A4, 0x54, 0x00, 0x00, 0x00 }, /* Τ to T */
1543 { 0x03A5, 0x59, 0x00, 0x00, 0x00 }, /* Υ to Y */
1544 { 0x03A6, 0x46, 0x00, 0x00, 0x00 }, /* Φ to F */
1545 { 0x03A7, 0x43, 0x68, 0x00, 0x00 }, /* Χ to Ch */
1546 { 0x03A8, 0x50, 0x73, 0x00, 0x00 }, /* Ψ to Ps */
1547 { 0x03A9, 0x4f, 0x00, 0x00, 0x00 }, /* Ω to O */
1548 { 0x03AA, 0x49, 0x00, 0x00, 0x00 }, /* Ϊ to I */
1549 { 0x03AB, 0x59, 0x00, 0x00, 0x00 }, /* Ϋ to Y */
1550 { 0x03AC, 0x61, 0x00, 0x00, 0x00 }, /* ά to a */
1551 { 0x03AD, 0x65, 0x00, 0x00, 0x00 }, /* έ to e */
1552 { 0x03AE, 0x69, 0x00, 0x00, 0x00 }, /* ή to i */
1553 { 0x03AF, 0x69, 0x00, 0x00, 0x00 }, /* ί to i */
1554 { 0x03B1, 0x61, 0x00, 0x00, 0x00 }, /* α to a */
1555 { 0x03B2, 0x62, 0x00, 0x00, 0x00 }, /* β to b */
1556 { 0x03B3, 0x67, 0x00, 0x00, 0x00 }, /* γ to g */
1557 { 0x03B4, 0x64, 0x00, 0x00, 0x00 }, /* δ to d */
1558 { 0x03B5, 0x65, 0x00, 0x00, 0x00 }, /* ε to e */
1559 { 0x03B6, 0x7a, 0x00, 0x00, 0x00 }, /* ζ to z */
1560 { 0x03B7, 0x69, 0x00, 0x00, 0x00 }, /* η to i */
1561 { 0x03B8, 0x74, 0x68, 0x00, 0x00 }, /* θ to th */
1562 { 0x03B9, 0x69, 0x00, 0x00, 0x00 }, /* ι to i */
1563 { 0x03BA, 0x6b, 0x00, 0x00, 0x00 }, /* κ to k */
1564 { 0x03BB, 0x6c, 0x00, 0x00, 0x00 }, /* λ to l */
1565 { 0x03BC, 0x6d, 0x00, 0x00, 0x00 }, /* μ to m */
1566 { 0x03BD, 0x6e, 0x00, 0x00, 0x00 }, /* ν to n */
1567 { 0x03BE, 0x78, 0x00, 0x00, 0x00 }, /* ξ to x */
1568 { 0x03BF, 0x6f, 0x00, 0x00, 0x00 }, /* ο to o */
1569 { 0x03C0, 0x70, 0x00, 0x00, 0x00 }, /* π to p */
1570 { 0x03C1, 0x72, 0x00, 0x00, 0x00 }, /* ρ to r */
1571 { 0x03C3, 0x73, 0x00, 0x00, 0x00 }, /* σ to s */
1572 { 0x03C4, 0x74, 0x00, 0x00, 0x00 }, /* τ to t */
1573 { 0x03C5, 0x79, 0x00, 0x00, 0x00 }, /* υ to y */
1574 { 0x03C6, 0x66, 0x00, 0x00, 0x00 }, /* φ to f */
1575 { 0x03C7, 0x63, 0x68, 0x00, 0x00 }, /* χ to ch */
1576 { 0x03C8, 0x70, 0x73, 0x00, 0x00 }, /* ψ to ps */
1577 { 0x03C9, 0x6f, 0x00, 0x00, 0x00 }, /* ω to o */
1578 { 0x03CA, 0x69, 0x00, 0x00, 0x00 }, /* ϊ to i */
1579 { 0x03CB, 0x79, 0x00, 0x00, 0x00 }, /* ϋ to y */
1580 { 0x03CC, 0x6f, 0x00, 0x00, 0x00 }, /* ό to o */
1581 { 0x03CD, 0x79, 0x00, 0x00, 0x00 }, /* ύ to y */
1582 { 0x03CE, 0x69, 0x00, 0x00, 0x00 }, /* ώ to i */
1583 { 0x0400, 0x45, 0x00, 0x00, 0x00 }, /* Ѐ to E */
1584 { 0x0401, 0x45, 0x00, 0x00, 0x00 }, /* Ё to E */
1585 { 0x0402, 0x44, 0x00, 0x00, 0x00 }, /* Ђ to D */
1586 { 0x0403, 0x47, 0x00, 0x00, 0x00 }, /* Ѓ to G */
1587 { 0x0404, 0x45, 0x00, 0x00, 0x00 }, /* Є to E */
1588 { 0x0405, 0x5a, 0x00, 0x00, 0x00 }, /* Ѕ to Z */
1589 { 0x0406, 0x49, 0x00, 0x00, 0x00 }, /* І to I */
1590 { 0x0407, 0x49, 0x00, 0x00, 0x00 }, /* Ї to I */
1591 { 0x0408, 0x4a, 0x00, 0x00, 0x00 }, /* Ј to J */
1592 { 0x0409, 0x49, 0x00, 0x00, 0x00 }, /* Љ to I */
1593 { 0x040A, 0x4e, 0x00, 0x00, 0x00 }, /* Њ to N */
1594 { 0x040B, 0x44, 0x00, 0x00, 0x00 }, /* Ћ to D */
1595 { 0x040C, 0x4b, 0x00, 0x00, 0x00 }, /* Ќ to K */
1596 { 0x040D, 0x49, 0x00, 0x00, 0x00 }, /* Ѝ to I */
1597 { 0x040E, 0x55, 0x00, 0x00, 0x00 }, /* Ў to U */
1598 { 0x040F, 0x44, 0x00, 0x00, 0x00 }, /* Џ to D */
1599 { 0x0410, 0x41, 0x00, 0x00, 0x00 }, /* А to A */
1600 { 0x0411, 0x42, 0x00, 0x00, 0x00 }, /* Б to B */
1601 { 0x0412, 0x56, 0x00, 0x00, 0x00 }, /* В to V */
1602 { 0x0413, 0x47, 0x00, 0x00, 0x00 }, /* Г to G */
1603 { 0x0414, 0x44, 0x00, 0x00, 0x00 }, /* Д to D */
1604 { 0x0415, 0x45, 0x00, 0x00, 0x00 }, /* Е to E */
1605 { 0x0416, 0x5a, 0x68, 0x00, 0x00 }, /* Ж to Zh */
1606 { 0x0417, 0x5a, 0x00, 0x00, 0x00 }, /* З to Z */
1607 { 0x0418, 0x49, 0x00, 0x00, 0x00 }, /* И to I */
1608 { 0x0419, 0x49, 0x00, 0x00, 0x00 }, /* Й to I */
1609 { 0x041A, 0x4b, 0x00, 0x00, 0x00 }, /* К to K */
1610 { 0x041B, 0x4c, 0x00, 0x00, 0x00 }, /* Л to L */
1611 { 0x041C, 0x4d, 0x00, 0x00, 0x00 }, /* М to M */
1612 { 0x041D, 0x4e, 0x00, 0x00, 0x00 }, /* Н to N */
1613 { 0x041E, 0x4f, 0x00, 0x00, 0x00 }, /* О to O */
1614 { 0x041F, 0x50, 0x00, 0x00, 0x00 }, /* П to P */
1615 { 0x0420, 0x52, 0x00, 0x00, 0x00 }, /* Р to R */
1616 { 0x0421, 0x53, 0x00, 0x00, 0x00 }, /* С to S */
1617 { 0x0422, 0x54, 0x00, 0x00, 0x00 }, /* Т to T */
1618 { 0x0423, 0x55, 0x00, 0x00, 0x00 }, /* У to U */
1619 { 0x0424, 0x46, 0x00, 0x00, 0x00 }, /* Ф to F */
1620 { 0x0425, 0x4b, 0x68, 0x00, 0x00 }, /* Х to Kh */
1621 { 0x0426, 0x54, 0x63, 0x00, 0x00 }, /* Ц to Tc */
1622 { 0x0427, 0x43, 0x68, 0x00, 0x00 }, /* Ч to Ch */
1623 { 0x0428, 0x53, 0x68, 0x00, 0x00 }, /* Ш to Sh */
1624 { 0x0429, 0x53, 0x68, 0x63, 0x68 }, /* Щ to Shch */
1625 { 0x042A, 0x61, 0x00, 0x00, 0x00 }, /* to A */
1626 { 0x042B, 0x59, 0x00, 0x00, 0x00 }, /* Ы to Y */
1627 { 0x042C, 0x59, 0x00, 0x00, 0x00 }, /* to Y */
1628 { 0x042D, 0x45, 0x00, 0x00, 0x00 }, /* Э to E */
1629 { 0x042E, 0x49, 0x75, 0x00, 0x00 }, /* Ю to Iu */
1630 { 0x042F, 0x49, 0x61, 0x00, 0x00 }, /* Я to Ia */
1631 { 0x0430, 0x61, 0x00, 0x00, 0x00 }, /* а to a */
1632 { 0x0431, 0x62, 0x00, 0x00, 0x00 }, /* б to b */
1633 { 0x0432, 0x76, 0x00, 0x00, 0x00 }, /* в to v */
1634 { 0x0433, 0x67, 0x00, 0x00, 0x00 }, /* г to g */
1635 { 0x0434, 0x64, 0x00, 0x00, 0x00 }, /* д to d */
1636 { 0x0435, 0x65, 0x00, 0x00, 0x00 }, /* е to e */
1637 { 0x0436, 0x7a, 0x68, 0x00, 0x00 }, /* ж to zh */
1638 { 0x0437, 0x7a, 0x00, 0x00, 0x00 }, /* з to z */
1639 { 0x0438, 0x69, 0x00, 0x00, 0x00 }, /* и to i */
1640 { 0x0439, 0x69, 0x00, 0x00, 0x00 }, /* й to i */
1641 { 0x043A, 0x6b, 0x00, 0x00, 0x00 }, /* к to k */
1642 { 0x043B, 0x6c, 0x00, 0x00, 0x00 }, /* л to l */
1643 { 0x043C, 0x6d, 0x00, 0x00, 0x00 }, /* м to m */
1644 { 0x043D, 0x6e, 0x00, 0x00, 0x00 }, /* н to n */
1645 { 0x043E, 0x6f, 0x00, 0x00, 0x00 }, /* о to o */
1646 { 0x043F, 0x70, 0x00, 0x00, 0x00 }, /* п to p */
1647 { 0x0440, 0x72, 0x00, 0x00, 0x00 }, /* р to r */
1648 { 0x0441, 0x73, 0x00, 0x00, 0x00 }, /* с to s */
1649 { 0x0442, 0x74, 0x00, 0x00, 0x00 }, /* т to t */
1650 { 0x0443, 0x75, 0x00, 0x00, 0x00 }, /* у to u */
1651 { 0x0444, 0x66, 0x00, 0x00, 0x00 }, /* ф to f */
1652 { 0x0445, 0x6b, 0x68, 0x00, 0x00 }, /* х to kh */
1653 { 0x0446, 0x74, 0x63, 0x00, 0x00 }, /* ц to tc */
1654 { 0x0447, 0x63, 0x68, 0x00, 0x00 }, /* ч to ch */
1655 { 0x0448, 0x73, 0x68, 0x00, 0x00 }, /* ш to sh */
1656 { 0x0449, 0x73, 0x68, 0x63, 0x68 }, /* щ to shch */
1657 { 0x044A, 0x61, 0x00, 0x00, 0x00 }, /* to a */
1658 { 0x044B, 0x79, 0x00, 0x00, 0x00 }, /* ы to y */
1659 { 0x044C, 0x79, 0x00, 0x00, 0x00 }, /* to y */
1660 { 0x044D, 0x65, 0x00, 0x00, 0x00 }, /* э to e */
1661 { 0x044E, 0x69, 0x75, 0x00, 0x00 }, /* ю to iu */
1662 { 0x044F, 0x69, 0x61, 0x00, 0x00 }, /* я to ia */
1663 { 0x0450, 0x65, 0x00, 0x00, 0x00 }, /* ѐ to e */
1664 { 0x0451, 0x65, 0x00, 0x00, 0x00 }, /* ё to e */
1665 { 0x0452, 0x64, 0x00, 0x00, 0x00 }, /* ђ to d */
1666 { 0x0453, 0x67, 0x00, 0x00, 0x00 }, /* ѓ to g */
1667 { 0x0454, 0x65, 0x00, 0x00, 0x00 }, /* є to e */
1668 { 0x0455, 0x7a, 0x00, 0x00, 0x00 }, /* ѕ to z */
1669 { 0x0456, 0x69, 0x00, 0x00, 0x00 }, /* і to i */
1670 { 0x0457, 0x69, 0x00, 0x00, 0x00 }, /* ї to i */
1671 { 0x0458, 0x6a, 0x00, 0x00, 0x00 }, /* ј to j */
1672 { 0x0459, 0x69, 0x00, 0x00, 0x00 }, /* љ to i */
1673 { 0x045A, 0x6e, 0x00, 0x00, 0x00 }, /* њ to n */
1674 { 0x045B, 0x64, 0x00, 0x00, 0x00 }, /* ћ to d */
1675 { 0x045C, 0x6b, 0x00, 0x00, 0x00 }, /* ќ to k */
1676 { 0x045D, 0x69, 0x00, 0x00, 0x00 }, /* ѝ to i */
1677 { 0x045E, 0x75, 0x00, 0x00, 0x00 }, /* ў to u */
1678 { 0x045F, 0x64, 0x00, 0x00, 0x00 }, /* џ to d */
1679 { 0x1E02, 0x42, 0x00, 0x00, 0x00 }, /* Ḃ to B */
1680 { 0x1E03, 0x62, 0x00, 0x00, 0x00 }, /* ḃ to b */
1681 { 0x1E0A, 0x44, 0x00, 0x00, 0x00 }, /* Ḋ to D */
1682 { 0x1E0B, 0x64, 0x00, 0x00, 0x00 }, /* ḋ to d */
1683 { 0x1E1E, 0x46, 0x00, 0x00, 0x00 }, /* Ḟ to F */
1684 { 0x1E1F, 0x66, 0x00, 0x00, 0x00 }, /* ḟ to f */
1685 { 0x1E40, 0x4D, 0x00, 0x00, 0x00 }, /* Ṁ to M */
1686 { 0x1E41, 0x6D, 0x00, 0x00, 0x00 }, /* ṁ to m */
1687 { 0x1E56, 0x50, 0x00, 0x00, 0x00 }, /* Ṗ to P */
1688 { 0x1E57, 0x70, 0x00, 0x00, 0x00 }, /* ṗ to p */
1689 { 0x1E60, 0x53, 0x00, 0x00, 0x00 }, /* Ṡ to S */
1690 { 0x1E61, 0x73, 0x00, 0x00, 0x00 }, /* ṡ to s */
1691 { 0x1E6A, 0x54, 0x00, 0x00, 0x00 }, /* Ṫ to T */
1692 { 0x1E6B, 0x74, 0x00, 0x00, 0x00 }, /* ṫ to t */
1693 { 0x1E80, 0x57, 0x00, 0x00, 0x00 }, /* Ẁ to W */
1694 { 0x1E81, 0x77, 0x00, 0x00, 0x00 }, /* ẁ to w */
1695 { 0x1E82, 0x57, 0x00, 0x00, 0x00 }, /* Ẃ to W */
1696 { 0x1E83, 0x77, 0x00, 0x00, 0x00 }, /* ẃ to w */
1697 { 0x1E84, 0x57, 0x00, 0x00, 0x00 }, /* Ẅ to W */
1698 { 0x1E85, 0x77, 0x00, 0x00, 0x00 }, /* ẅ to w */
1699 { 0x1EF2, 0x59, 0x00, 0x00, 0x00 }, /* Ỳ to Y */
1700 { 0x1EF3, 0x79, 0x00, 0x00, 0x00 }, /* ỳ to y */
1701 { 0xFB00, 0x66, 0x66, 0x00, 0x00 }, /* ff to ff */
1702 { 0xFB01, 0x66, 0x69, 0x00, 0x00 }, /* fi to fi */
1703 { 0xFB02, 0x66, 0x6C, 0x00, 0x00 }, /* fl to fl */
1704 { 0xFB05, 0x73, 0x74, 0x00, 0x00 }, /* ſt to st */
1705 { 0xFB06, 0x73, 0x74, 0x00, 0x00 }, /* st to st */
1706 };
1707
1708 static const Transliteration *spellfixFindTranslit(int c, int *pxTop){
1709 *pxTop = (sizeof(translit)/sizeof(translit[0])) - 1;
1710 return translit;
1711 }
1712
1713 /*
1714 ** Convert the input string from UTF-8 into pure ASCII by converting
1715 ** all non-ASCII characters to some combination of characters in the
1716 ** ASCII subset.
1717 **
1718 ** The returned string might contain more characters than the input.
1719 **
1720 ** Space to hold the returned string comes from sqlite3_malloc() and
1721 ** should be freed by the caller.
1722 */
1723 static unsigned char *transliterate(const unsigned char *zIn, int nIn){
1724 #ifdef SQLITE_SPELLFIX_5BYTE_MAPPINGS
1725 unsigned char *zOut = sqlite3_malloc64( (i64)nIn*5 + 1 );
1726 #else
1727 unsigned char *zOut = sqlite3_malloc64( (i64)nIn*4 + 1 );
1728 #endif
1729 int c, sz, nOut;
1730 if( zOut==0 ) return 0;
1731 nOut = 0;
1732 while( nIn>0 ){
1733 c = utf8Read(zIn, nIn, &sz);
1734 zIn += sz;
1735 nIn -= sz;
1736 if( c<=127 ){
1737 zOut[nOut++] = (unsigned char)c;
1738 }else{
1739 int xTop, xBtm, x;
1740 const Transliteration *tbl = spellfixFindTranslit(c, &xTop);
1741 xBtm = 0;
1742 while( xTop>=xBtm ){
1743 x = (xTop + xBtm)/2;
1744 if( tbl[x].cFrom==c ){
1745 zOut[nOut++] = tbl[x].cTo0;
1746 if( tbl[x].cTo1 ){
1747 zOut[nOut++] = tbl[x].cTo1;
1748 if( tbl[x].cTo2 ){
1749 zOut[nOut++] = tbl[x].cTo2;
1750 if( tbl[x].cTo3 ){
1751 zOut[nOut++] = tbl[x].cTo3;
1752 #ifdef SQLITE_SPELLFIX_5BYTE_MAPPINGS
1753 if( tbl[x].cTo4 ){
1754 zOut[nOut++] = tbl[x].cTo4;
1755 }
1756 #endif /* SQLITE_SPELLFIX_5BYTE_MAPPINGS */
1757 }
1758 }
1759 }
1760 c = 0;
1761 break;
1762 }else if( tbl[x].cFrom>c ){
1763 xTop = x-1;
1764 }else{
1765 xBtm = x+1;
1766 }
1767 }
1768 if( c ) zOut[nOut++] = '?';
1769 }
1770 }
1771 zOut[nOut] = 0;
1772 return zOut;
1773 }
1774
1775 /*
1776 ** Return the number of characters in the shortest prefix of the input
1777 ** string that transliterates to an ASCII string nTrans bytes or longer.
1778 ** Or, if the transliteration of the input string is less than nTrans
1779 ** bytes in size, return the number of characters in the input string.
1780 */
1781 static int translen_to_charlen(const char *zIn, int nIn, int nTrans){
1782 int i, c, sz, nOut;
1783 int nChar;
1784
1785 i = nOut = 0;
1786 for(nChar=0; i<nIn && nOut<nTrans; nChar++){
1787 c = utf8Read((const unsigned char *)&zIn[i], nIn-i, &sz);
1788 i += sz;
1789
1790 nOut++;
1791 if( c>=128 ){
1792 int xTop, xBtm, x;
1793 const Transliteration *tbl = spellfixFindTranslit(c, &xTop);
1794 xBtm = 0;
1795 while( xTop>=xBtm ){
1796 x = (xTop + xBtm)/2;
1797 if( tbl[x].cFrom==c ){
1798 if( tbl[x].cTo1 ){
1799 nOut++;
1800 if( tbl[x].cTo2 ){
1801 nOut++;
1802 if( tbl[x].cTo3 ){
1803 nOut++;
1804 }
1805 }
1806 }
1807 break;
1808 }else if( tbl[x].cFrom>c ){
1809 xTop = x-1;
1810 }else{
1811 xBtm = x+1;
1812 }
1813 }
1814 }
1815 }
1816
1817 return nChar;
1818 }
1819
1820
1821 /*
1822 ** spellfix1_translit(X)
1823 **
1824 ** Convert a string that contains non-ASCII Roman characters into
1825 ** pure ASCII.
1826 */
1827 static void transliterateSqlFunc(
1828 sqlite3_context *context,
1829 int argc,
1830 sqlite3_value **argv
1831 ){
1832 const unsigned char *zIn = sqlite3_value_text(argv[0]);
1833 int nIn = sqlite3_value_bytes(argv[0]);
1834 unsigned char *zOut = transliterate(zIn, nIn);
1835 if( zOut==0 ){
1836 sqlite3_result_error_nomem(context);
1837 }else{
1838 sqlite3_result_text(context, (char*)zOut, -1, sqlite3_free);
1839 }
1840 }
1841
1842 /*
1843 ** spellfix1_scriptcode(X)
1844 **
1845 ** Try to determine the dominant script used by the word X and return
1846 ** its ISO 15924 numeric code.
1847 **
1848 ** The current implementation only understands the following scripts:
1849 **
1850 ** 215 (Latin)
1851 ** 220 (Cyrillic)
1852 ** 200 (Greek)
1853 **
1854 ** This routine will return 998 if the input X contains characters from
1855 ** two or more of the above scripts or 999 if X contains no characters
1856 ** from any of the above scripts.
1857 */
1858 static void scriptCodeSqlFunc(
1859 sqlite3_context *context,
1860 int argc,
1861 sqlite3_value **argv
1862 ){
1863 const unsigned char *zIn = sqlite3_value_text(argv[0]);
1864 int nIn = sqlite3_value_bytes(argv[0]);
1865 int c, sz;
1866 int scriptMask = 0;
1867 int res;
1868 int seenDigit = 0;
1869 # define SCRIPT_LATIN 0x0001
1870 # define SCRIPT_CYRILLIC 0x0002
1871 # define SCRIPT_GREEK 0x0004
1872 # define SCRIPT_HEBREW 0x0008
1873 # define SCRIPT_ARABIC 0x0010
1874
1875 while( nIn>0 ){
1876 c = utf8Read(zIn, nIn, &sz);
1877 zIn += sz;
1878 nIn -= sz;
1879 if( c<0x02af ){
1880 if( c>=0x80 || midClass[c&0x7f]<CCLASS_DIGIT ){
1881 scriptMask |= SCRIPT_LATIN;
1882 }else if( c>='0' && c<='9' ){
1883 seenDigit = 1;
1884 }
1885 }else if( c>=0x0400 && c<=0x04ff ){
1886 scriptMask |= SCRIPT_CYRILLIC;
1887 }else if( c>=0x0386 && c<=0x03ce ){
1888 scriptMask |= SCRIPT_GREEK;
1889 }else if( c>=0x0590 && c<=0x05ff ){
1890 scriptMask |= SCRIPT_HEBREW;
1891 }else if( c>=0x0600 && c<=0x06ff ){
1892 scriptMask |= SCRIPT_ARABIC;
1893 }
1894 }
1895 if( scriptMask==0 && seenDigit ) scriptMask = SCRIPT_LATIN;
1896 switch( scriptMask ){
1897 case 0: res = 999; break;
1898 case SCRIPT_LATIN: res = 215; break;
1899 case SCRIPT_CYRILLIC: res = 220; break;
1900 case SCRIPT_GREEK: res = 200; break;
1901 case SCRIPT_HEBREW: res = 125; break;
1902 case SCRIPT_ARABIC: res = 160; break;
1903 default: res = 998; break;
1904 }
1905 sqlite3_result_int(context, res);
1906 }
1907
1908 /* End transliterate
1909 ******************************************************************************
1910 ******************************************************************************
1911 ** Begin spellfix1 virtual table.
1912 */
1913
1914 /* Maximum length of a phonehash used for querying the shadow table */
1915 #define SPELLFIX_MX_HASH 32
1916
1917 /* Maximum number of hash strings to examine per query */
1918 #define SPELLFIX_MX_RUN 1
1919
1920 typedef struct spellfix1_vtab spellfix1_vtab;
1921 typedef struct spellfix1_cursor spellfix1_cursor;
1922
1923 /* Fuzzy-search virtual table object */
1924 struct spellfix1_vtab {
1925 sqlite3_vtab base; /* Base class - must be first */
1926 sqlite3 *db; /* Database connection */
1927 char *zDbName; /* Name of database holding this table */
1928 char *zTableName; /* Name of the virtual table */
1929 char *zCostTable; /* Table holding edit-distance cost numbers */
1930 EditDist3Config *pConfig3; /* Parsed edit distance costs */
1931 };
1932
1933 /* Fuzzy-search cursor object */
1934 struct spellfix1_cursor {
1935 sqlite3_vtab_cursor base; /* Base class - must be first */
1936 spellfix1_vtab *pVTab; /* The table to which this cursor belongs */
1937 char *zPattern; /* rhs of MATCH clause */
1938 int idxNum; /* idxNum value passed to xFilter() */
1939 int nRow; /* Number of rows of content */
1940 int nAlloc; /* Number of allocated rows */
1941 int iRow; /* Current row of content */
1942 int iLang; /* Value of the langid= constraint */
1943 int iTop; /* Value of the top= constraint */
1944 int iScope; /* Value of the scope= constraint */
1945 int nSearch; /* Number of vocabulary items checked */
1946 sqlite3_stmt *pFullScan; /* Shadow query for a full table scan */
1947 struct spellfix1_row { /* For each row of content */
1948 sqlite3_int64 iRowid; /* Rowid for this row */
1949 char *zWord; /* Text for this row */
1950 int iRank; /* Rank for this row */
1951 int iDistance; /* Distance from pattern for this row */
1952 int iScore; /* Score for sorting */
1953 int iMatchlen; /* Value of matchlen column (or -1) */
1954 char zHash[SPELLFIX_MX_HASH]; /* the phonehash used for this match */
1955 } *a;
1956 };
1957
1958 /*
1959 ** Construct one or more SQL statements from the format string given
1960 ** and then evaluate those statements. The success code is written
1961 ** into *pRc.
1962 **
1963 ** If *pRc is initially non-zero then this routine is a no-op.
1964 */
1965 static void spellfix1DbExec(
1966 int *pRc, /* Success code */
1967 sqlite3 *db, /* Database in which to run SQL */
1968 const char *zFormat, /* Format string for SQL */
1969 ... /* Arguments to the format string */
1970 ){
1971 va_list ap;
1972 char *zSql;
1973 if( *pRc ) return;
1974 va_start(ap, zFormat);
1975 zSql = sqlite3_vmprintf(zFormat, ap);
1976 va_end(ap);
1977 if( zSql==0 ){
1978 *pRc = SQLITE_NOMEM;
1979 }else{
1980 *pRc = sqlite3_exec(db, zSql, 0, 0, 0);
1981 sqlite3_free(zSql);
1982 }
1983 }
1984
1985 /*
1986 ** xDisconnect/xDestroy method for the fuzzy-search module.
1987 */
1988 static int spellfix1Uninit(int isDestroy, sqlite3_vtab *pVTab){
1989 spellfix1_vtab *p = (spellfix1_vtab*)pVTab;
1990 int rc = SQLITE_OK;
1991 if( isDestroy ){
1992 sqlite3 *db = p->db;
1993 spellfix1DbExec(&rc, db, "DROP TABLE IF EXISTS \"%w\".\"%w_vocab\"",
1994 p->zDbName, p->zTableName);
1995 }
1996 if( rc==SQLITE_OK ){
1997 sqlite3_free(p->zTableName);
1998 editDist3ConfigDelete(p->pConfig3);
1999 sqlite3_free(p->zCostTable);
2000 sqlite3_free(p);
2001 }
2002 return rc;
2003 }
2004 static int spellfix1Disconnect(sqlite3_vtab *pVTab){
2005 return spellfix1Uninit(0, pVTab);
2006 }
2007 static int spellfix1Destroy(sqlite3_vtab *pVTab){
2008 return spellfix1Uninit(1, pVTab);
2009 }
2010
2011 /*
2012 ** Make a copy of a string. Remove leading and trailing whitespace
2013 ** and dequote it.
2014 */
2015 static char *spellfix1Dequote(const char *zIn){
2016 char *zOut;
2017 int i, j;
2018 char c;
2019 while( isspace((unsigned char)zIn[0]) ) zIn++;
2020 zOut = sqlite3_mprintf("%s", zIn);
2021 if( zOut==0 ) return 0;
2022 i = (int)strlen(zOut);
2023 #if 0 /* The parser will never leave spaces at the end */
2024 while( i>0 && isspace(zOut[i-1]) ){ i--; }
2025 #endif
2026 zOut[i] = 0;
2027 c = zOut[0];
2028 if( c=='\'' || c=='"' ){
2029 for(i=1, j=0; ALWAYS(zOut[i]); i++){
2030 zOut[j++] = zOut[i];
2031 if( zOut[i]==c ){
2032 if( zOut[i+1]==c ){
2033 i++;
2034 }else{
2035 zOut[j-1] = 0;
2036 break;
2037 }
2038 }
2039 }
2040 }
2041 return zOut;
2042 }
2043
2044
2045 /*
2046 ** xConnect/xCreate method for the spellfix1 module. Arguments are:
2047 **
2048 ** argv[0] -> module name ("spellfix1")
2049 ** argv[1] -> database name
2050 ** argv[2] -> table name
2051 ** argv[3].. -> optional arguments (i.e. "edit_cost_table" parameter)
2052 */
2053 static int spellfix1Init(
2054 int isCreate,
2055 sqlite3 *db,
2056 void *pAux,
2057 int argc, const char *const*argv,
2058 sqlite3_vtab **ppVTab,
2059 char **pzErr
2060 ){
2061 spellfix1_vtab *pNew = 0;
2062 /* const char *zModule = argv[0]; // not used */
2063 const char *zDbName = argv[1];
2064 const char *zTableName = argv[2];
2065 int nDbName;
2066 int rc = SQLITE_OK;
2067 int i;
2068
2069 nDbName = (int)strlen(zDbName);
2070 pNew = sqlite3_malloc64( sizeof(*pNew) + (i64)nDbName + 1);
2071 if( pNew==0 ){
2072 rc = SQLITE_NOMEM;
2073 }else{
2074 memset(pNew, 0, sizeof(*pNew));
2075 pNew->zDbName = (char*)&pNew[1];
2076 memcpy(pNew->zDbName, zDbName, nDbName+1);
2077 pNew->zTableName = sqlite3_mprintf("%s", zTableName);
2078 pNew->db = db;
2079 if( pNew->zTableName==0 ){
2080 rc = SQLITE_NOMEM;
2081 }else{
2082 sqlite3_vtab_config(db, SQLITE_VTAB_INNOCUOUS);
2083 rc = sqlite3_declare_vtab(db,
2084 "CREATE TABLE x(word,rank,distance,langid, "
2085 "score, matchlen, phonehash HIDDEN, "
2086 "top HIDDEN, scope HIDDEN, srchcnt HIDDEN, "
2087 "soundslike HIDDEN, command HIDDEN)"
2088 );
2089 #define SPELLFIX_COL_WORD 0
2090 #define SPELLFIX_COL_RANK 1
2091 #define SPELLFIX_COL_DISTANCE 2
2092 #define SPELLFIX_COL_LANGID 3
2093 #define SPELLFIX_COL_SCORE 4
2094 #define SPELLFIX_COL_MATCHLEN 5
2095 #define SPELLFIX_COL_PHONEHASH 6
2096 #define SPELLFIX_COL_TOP 7
2097 #define SPELLFIX_COL_SCOPE 8
2098 #define SPELLFIX_COL_SRCHCNT 9
2099 #define SPELLFIX_COL_SOUNDSLIKE 10
2100 #define SPELLFIX_COL_COMMAND 11
2101 }
2102 if( rc==SQLITE_OK && isCreate ){
2103 spellfix1DbExec(&rc, db,
2104 "CREATE TABLE IF NOT EXISTS \"%w\".\"%w_vocab\"(\n"
2105 " id INTEGER PRIMARY KEY,\n"
2106 " rank INT,\n"
2107 " langid INT,\n"
2108 " word TEXT,\n"
2109 " k1 TEXT,\n"
2110 " k2 TEXT\n"
2111 ");\n",
2112 zDbName, zTableName
2113 );
2114 spellfix1DbExec(&rc, db,
2115 "CREATE INDEX IF NOT EXISTS \"%w\".\"%w_vocab_index_langid_k2\" "
2116 "ON \"%w_vocab\"(langid,k2);",
2117 zDbName, zTableName, zTableName
2118 );
2119 }
2120 for(i=3; rc==SQLITE_OK && i<argc; i++){
2121 if( strncmp(argv[i],"edit_cost_table=",16)==0 && pNew->zCostTable==0 ){
2122 pNew->zCostTable = spellfix1Dequote(&argv[i][16]);
2123 if( pNew->zCostTable==0 ) rc = SQLITE_NOMEM;
2124 continue;
2125 }
2126 *pzErr = sqlite3_mprintf("bad argument to spellfix1(): \"%s\"", argv[i]);
2127 rc = SQLITE_ERROR;
2128 }
2129 }
2130
2131 if( rc && pNew ){
2132 *ppVTab = 0;
2133 spellfix1Uninit(0, &pNew->base);
2134 }else{
2135 *ppVTab = (sqlite3_vtab *)pNew;
2136 }
2137 return rc;
2138 }
2139
2140 /*
2141 ** The xConnect and xCreate methods
2142 */
2143 static int spellfix1Connect(
2144 sqlite3 *db,
2145 void *pAux,
2146 int argc, const char *const*argv,
2147 sqlite3_vtab **ppVTab,
2148 char **pzErr
2149 ){
2150 return spellfix1Init(0, db, pAux, argc, argv, ppVTab, pzErr);
2151 }
2152 static int spellfix1Create(
2153 sqlite3 *db,
2154 void *pAux,
2155 int argc, const char *const*argv,
2156 sqlite3_vtab **ppVTab,
2157 char **pzErr
2158 ){
2159 return spellfix1Init(1, db, pAux, argc, argv, ppVTab, pzErr);
2160 }
2161
2162 /*
2163 ** Clear all of the content from a cursor.
2164 */
2165 static void spellfix1ResetCursor(spellfix1_cursor *pCur){
2166 int i;
2167 for(i=0; i<pCur->nRow; i++){
2168 sqlite3_free(pCur->a[i].zWord);
2169 }
2170 pCur->nRow = 0;
2171 pCur->iRow = 0;
2172 pCur->nSearch = 0;
2173 if( pCur->pFullScan ){
2174 sqlite3_finalize(pCur->pFullScan);
2175 pCur->pFullScan = 0;
2176 }
2177 }
2178
2179 /*
2180 ** Resize the cursor to hold up to N rows of content
2181 */
2182 static void spellfix1ResizeCursor(spellfix1_cursor *pCur, int N){
2183 struct spellfix1_row *aNew;
2184 assert( N>=pCur->nRow );
2185 aNew = sqlite3_realloc64(pCur->a, sizeof(pCur->a[0])*N);
2186 if( aNew==0 && N>0 ){
2187 spellfix1ResetCursor(pCur);
2188 sqlite3_free(pCur->a);
2189 pCur->nAlloc = 0;
2190 pCur->a = 0;
2191 }else{
2192 pCur->nAlloc = N;
2193 pCur->a = aNew;
2194 }
2195 }
2196
2197
2198 /*
2199 ** Close a fuzzy-search cursor.
2200 */
2201 static int spellfix1Close(sqlite3_vtab_cursor *cur){
2202 spellfix1_cursor *pCur = (spellfix1_cursor *)cur;
2203 spellfix1ResetCursor(pCur);
2204 spellfix1ResizeCursor(pCur, 0);
2205 sqlite3_free(pCur->zPattern);
2206 sqlite3_free(pCur);
2207 return SQLITE_OK;
2208 }
2209
2210 #define SPELLFIX_IDXNUM_MATCH 0x01 /* word MATCH $str */
2211 #define SPELLFIX_IDXNUM_LANGID 0x02 /* langid == $langid */
2212 #define SPELLFIX_IDXNUM_TOP 0x04 /* top = $top */
2213 #define SPELLFIX_IDXNUM_SCOPE 0x08 /* scope = $scope */
2214 #define SPELLFIX_IDXNUM_DISTLT 0x10 /* distance < $distance */
2215 #define SPELLFIX_IDXNUM_DISTLE 0x20 /* distance <= $distance */
2216 #define SPELLFIX_IDXNUM_ROWID 0x40 /* rowid = $rowid */
2217 #define SPELLFIX_IDXNUM_DIST (0x10|0x20) /* DISTLT and DISTLE */
2218
2219 /*
2220 **
2221 ** The plan number is a bitmask of the SPELLFIX_IDXNUM_* values defined
2222 ** above.
2223 **
2224 ** filter.argv[*] values contains $str, $langid, $top, $scope and $rowid
2225 ** if specified and in that order.
2226 */
2227 static int spellfix1BestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
2228 int iPlan = 0;
2229 int iLangTerm = -1;
2230 int iTopTerm = -1;
2231 int iScopeTerm = -1;
2232 int iDistTerm = -1;
2233 int iRowidTerm = -1;
2234 int i;
2235 const struct sqlite3_index_constraint *pConstraint;
2236 pConstraint = pIdxInfo->aConstraint;
2237 for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
2238 if( pConstraint->usable==0 ) continue;
2239
2240 /* Terms of the form: word MATCH $str */
2241 if( (iPlan & SPELLFIX_IDXNUM_MATCH)==0
2242 && pConstraint->iColumn==SPELLFIX_COL_WORD
2243 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH
2244 ){
2245 iPlan |= SPELLFIX_IDXNUM_MATCH;
2246 pIdxInfo->aConstraintUsage[i].argvIndex = 1;
2247 pIdxInfo->aConstraintUsage[i].omit = 1;
2248 }
2249
2250 /* Terms of the form: langid = $langid */
2251 if( (iPlan & SPELLFIX_IDXNUM_LANGID)==0
2252 && pConstraint->iColumn==SPELLFIX_COL_LANGID
2253 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
2254 ){
2255 iPlan |= SPELLFIX_IDXNUM_LANGID;
2256 iLangTerm = i;
2257 }
2258
2259 /* Terms of the form: top = $top */
2260 if( (iPlan & SPELLFIX_IDXNUM_TOP)==0
2261 && pConstraint->iColumn==SPELLFIX_COL_TOP
2262 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
2263 ){
2264 iPlan |= SPELLFIX_IDXNUM_TOP;
2265 iTopTerm = i;
2266 }
2267
2268 /* Terms of the form: scope = $scope */
2269 if( (iPlan & SPELLFIX_IDXNUM_SCOPE)==0
2270 && pConstraint->iColumn==SPELLFIX_COL_SCOPE
2271 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
2272 ){
2273 iPlan |= SPELLFIX_IDXNUM_SCOPE;
2274 iScopeTerm = i;
2275 }
2276
2277 /* Terms of the form: distance < $dist or distance <= $dist */
2278 if( (iPlan & SPELLFIX_IDXNUM_DIST)==0
2279 && pConstraint->iColumn==SPELLFIX_COL_DISTANCE
2280 && (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT
2281 || pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE)
2282 ){
2283 if( pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT ){
2284 iPlan |= SPELLFIX_IDXNUM_DISTLT;
2285 }else{
2286 iPlan |= SPELLFIX_IDXNUM_DISTLE;
2287 }
2288 iDistTerm = i;
2289 }
2290
2291 /* Terms of the form: distance < $dist or distance <= $dist */
2292 if( (iPlan & SPELLFIX_IDXNUM_ROWID)==0
2293 && pConstraint->iColumn<0
2294 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
2295 ){
2296 iPlan |= SPELLFIX_IDXNUM_ROWID;
2297 iRowidTerm = i;
2298 }
2299 }
2300 if( iPlan&SPELLFIX_IDXNUM_MATCH ){
2301 int idx = 2;
2302 pIdxInfo->idxNum = iPlan;
2303 if( pIdxInfo->nOrderBy==1
2304 && pIdxInfo->aOrderBy[0].iColumn==SPELLFIX_COL_SCORE
2305 && pIdxInfo->aOrderBy[0].desc==0
2306 ){
2307 pIdxInfo->orderByConsumed = 1; /* Default order by iScore */
2308 }
2309 if( iPlan&SPELLFIX_IDXNUM_LANGID ){
2310 pIdxInfo->aConstraintUsage[iLangTerm].argvIndex = idx++;
2311 pIdxInfo->aConstraintUsage[iLangTerm].omit = 1;
2312 }
2313 if( iPlan&SPELLFIX_IDXNUM_TOP ){
2314 pIdxInfo->aConstraintUsage[iTopTerm].argvIndex = idx++;
2315 pIdxInfo->aConstraintUsage[iTopTerm].omit = 1;
2316 }
2317 if( iPlan&SPELLFIX_IDXNUM_SCOPE ){
2318 pIdxInfo->aConstraintUsage[iScopeTerm].argvIndex = idx++;
2319 pIdxInfo->aConstraintUsage[iScopeTerm].omit = 1;
2320 }
2321 if( iPlan&SPELLFIX_IDXNUM_DIST ){
2322 pIdxInfo->aConstraintUsage[iDistTerm].argvIndex = idx++;
2323 pIdxInfo->aConstraintUsage[iDistTerm].omit = 1;
2324 }
2325 pIdxInfo->estimatedCost = 1e5;
2326 }else if( (iPlan & SPELLFIX_IDXNUM_ROWID) ){
2327 pIdxInfo->idxNum = SPELLFIX_IDXNUM_ROWID;
2328 pIdxInfo->aConstraintUsage[iRowidTerm].argvIndex = 1;
2329 pIdxInfo->aConstraintUsage[iRowidTerm].omit = 1;
2330 pIdxInfo->estimatedCost = 5;
2331 }else{
2332 pIdxInfo->idxNum = 0;
2333 pIdxInfo->estimatedCost = 1e50;
2334 }
2335 return SQLITE_OK;
2336 }
2337
2338 /*
2339 ** Open a new fuzzy-search cursor.
2340 */
2341 static int spellfix1Open(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
2342 spellfix1_vtab *p = (spellfix1_vtab*)pVTab;
2343 spellfix1_cursor *pCur;
2344 pCur = sqlite3_malloc64( sizeof(*pCur) );
2345 if( pCur==0 ) return SQLITE_NOMEM;
2346 memset(pCur, 0, sizeof(*pCur));
2347 pCur->pVTab = p;
2348 *ppCursor = &pCur->base;
2349 return SQLITE_OK;
2350 }
2351
2352 /*
2353 ** Adjust a distance measurement by the words rank in order to show
2354 ** preference to common words.
2355 */
2356 static int spellfix1Score(int iDistance, int iRank){
2357 int iLog2;
2358 for(iLog2=0; iRank>0; iLog2++, iRank>>=1){}
2359 return iDistance + 32 - iLog2;
2360 }
2361
2362 /*
2363 ** Compare two spellfix1_row objects for sorting purposes in qsort() such
2364 ** that they sort in order of increasing distance.
2365 */
2366 static int SQLITE_CDECL spellfix1RowCompare(const void *A, const void *B){
2367 const struct spellfix1_row *a = (const struct spellfix1_row*)A;
2368 const struct spellfix1_row *b = (const struct spellfix1_row*)B;
2369 return a->iScore - b->iScore;
2370 }
2371
2372 /*
2373 ** A structure used to pass information from spellfix1FilterForMatch()
2374 ** into spellfix1RunQuery().
2375 */
2376 typedef struct MatchQuery {
2377 spellfix1_cursor *pCur; /* The cursor being queried */
2378 sqlite3_stmt *pStmt; /* shadow table query statment */
2379 char zHash[SPELLFIX_MX_HASH]; /* The current phonehash for zPattern */
2380 const char *zPattern; /* Transliterated input string */
2381 int nPattern; /* Length of zPattern */
2382 EditDist3FromString *pMatchStr3; /* Original unicode string */
2383 EditDist3Config *pConfig3; /* Edit-distance cost coefficients */
2384 const EditDist3Lang *pLang; /* The selected language coefficients */
2385 int iLang; /* The language id */
2386 int iScope; /* Default scope */
2387 int iMaxDist; /* Maximum allowed edit distance, or -1 */
2388 int rc; /* Error code */
2389 int nRun; /* Number of prior runs for the same zPattern */
2390 char azPrior[SPELLFIX_MX_RUN][SPELLFIX_MX_HASH]; /* Prior hashes */
2391 } MatchQuery;
2392
2393 /*
2394 ** Run a query looking for the best matches against zPattern using
2395 ** zHash as the character class seed hash.
2396 */
2397 static void spellfix1RunQuery(MatchQuery *p, const char *zQuery, int nQuery){
2398 const char *zK1;
2399 const char *zWord;
2400 int iDist;
2401 int iRank;
2402 int iScore;
2403 int iWorst = 0;
2404 int idx;
2405 int idxWorst = -1;
2406 int i;
2407 int iScope = p->iScope;
2408 spellfix1_cursor *pCur = p->pCur;
2409 sqlite3_stmt *pStmt = p->pStmt;
2410 char zHash1[SPELLFIX_MX_HASH];
2411 char zHash2[SPELLFIX_MX_HASH];
2412 char *zClass;
2413 int nClass;
2414 int rc;
2415
2416 if( pCur->a==0 || p->rc ) return; /* Prior memory allocation failure */
2417 zClass = (char*)phoneticHash((unsigned char*)zQuery, nQuery);
2418 if( zClass==0 ){
2419 p->rc = SQLITE_NOMEM;
2420 return;
2421 }
2422 nClass = (int)strlen(zClass);
2423 if( nClass>SPELLFIX_MX_HASH-2 ){
2424 nClass = SPELLFIX_MX_HASH-2;
2425 zClass[nClass] = 0;
2426 }
2427 if( nClass<=iScope ){
2428 if( nClass>2 ){
2429 iScope = nClass-1;
2430 }else{
2431 iScope = nClass;
2432 }
2433 }
2434 memcpy(zHash1, zClass, iScope);
2435 sqlite3_free(zClass);
2436 zHash1[iScope] = 0;
2437 memcpy(zHash2, zHash1, iScope);
2438 zHash2[iScope] = 'Z';
2439 zHash2[iScope+1] = 0;
2440 #if SPELLFIX_MX_RUN>1
2441 for(i=0; i<p->nRun; i++){
2442 if( strcmp(p->azPrior[i], zHash1)==0 ) return;
2443 }
2444 #endif
2445 assert( p->nRun<SPELLFIX_MX_RUN );
2446 memcpy(p->azPrior[p->nRun++], zHash1, iScope+1);
2447 if( sqlite3_bind_text(pStmt, 1, zHash1, -1, SQLITE_STATIC)==SQLITE_NOMEM
2448 || sqlite3_bind_text(pStmt, 2, zHash2, -1, SQLITE_STATIC)==SQLITE_NOMEM
2449 ){
2450 p->rc = SQLITE_NOMEM;
2451 return;
2452 }
2453 #if SPELLFIX_MX_RUN>1
2454 for(i=0; i<pCur->nRow; i++){
2455 if( pCur->a[i].iScore>iWorst ){
2456 iWorst = pCur->a[i].iScore;
2457 idxWorst = i;
2458 }
2459 }
2460 #endif
2461 while( sqlite3_step(pStmt)==SQLITE_ROW ){
2462 int iMatchlen = -1;
2463 iRank = sqlite3_column_int(pStmt, 2);
2464 if( p->pMatchStr3 ){
2465 int nWord = sqlite3_column_bytes(pStmt, 1);
2466 zWord = (const char*)sqlite3_column_text(pStmt, 1);
2467 iDist = editDist3Core(p->pMatchStr3, zWord, nWord, p->pLang, &iMatchlen);
2468 }else{
2469 zK1 = (const char*)sqlite3_column_text(pStmt, 3);
2470 if( zK1==0 ) continue;
2471 iDist = editdist1(p->zPattern, zK1, 0);
2472 }
2473 if( iDist<0 ){
2474 p->rc = iDist==(-4) ? SQLITE_TOOBIG : SQLITE_NOMEM;
2475 break;
2476 }
2477 pCur->nSearch++;
2478
2479 /* If there is a "distance < $dist" or "distance <= $dist" constraint,
2480 ** check if this row meets it. If not, jump back up to the top of the
2481 ** loop to process the next row. Otherwise, if the row does match the
2482 ** distance constraint, check if the pCur->a[] array is already full.
2483 ** If it is and no explicit "top = ?" constraint was present in the
2484 ** query, grow the array to ensure there is room for the new entry. */
2485 assert( (p->iMaxDist>=0)==((pCur->idxNum & SPELLFIX_IDXNUM_DIST) ? 1 : 0) );
2486 if( p->iMaxDist>=0 ){
2487 if( iDist>p->iMaxDist ) continue;
2488 if( pCur->nRow>=pCur->nAlloc && (pCur->idxNum & SPELLFIX_IDXNUM_TOP)==0 ){
2489 spellfix1ResizeCursor(pCur, pCur->nAlloc*2 + 10);
2490 if( pCur->a==0 ) break;
2491 }
2492 }
2493
2494 iScore = spellfix1Score(iDist,iRank);
2495 if( pCur->nRow<pCur->nAlloc ){
2496 idx = pCur->nRow;
2497 }else if( iScore<iWorst ){
2498 idx = idxWorst;
2499 sqlite3_free(pCur->a[idx].zWord);
2500 }else{
2501 continue;
2502 }
2503
2504 pCur->a[idx].zWord = sqlite3_mprintf("%s", sqlite3_column_text(pStmt, 1));
2505 if( pCur->a[idx].zWord==0 ){
2506 p->rc = SQLITE_NOMEM;
2507 break;
2508 }
2509 pCur->a[idx].iRowid = sqlite3_column_int64(pStmt, 0);
2510 pCur->a[idx].iRank = iRank;
2511 pCur->a[idx].iDistance = iDist;
2512 pCur->a[idx].iScore = iScore;
2513 pCur->a[idx].iMatchlen = iMatchlen;
2514 memcpy(pCur->a[idx].zHash, zHash1, iScope+1);
2515 if( pCur->nRow<pCur->nAlloc ) pCur->nRow++;
2516 if( pCur->nRow==pCur->nAlloc ){
2517 iWorst = pCur->a[0].iScore;
2518 idxWorst = 0;
2519 for(i=1; i<pCur->nRow; i++){
2520 iScore = pCur->a[i].iScore;
2521 if( iWorst<iScore ){
2522 iWorst = iScore;
2523 idxWorst = i;
2524 }
2525 }
2526 }
2527 }
2528 rc = sqlite3_reset(pStmt);
2529 if( rc ) p->rc = rc;
2530 }
2531
2532 /*
2533 ** This version of the xFilter method work if the MATCH term is present
2534 ** and we are doing a scan.
2535 */
2536 static int spellfix1FilterForMatch(
2537 spellfix1_cursor *pCur,
2538 int argc,
2539 sqlite3_value **argv
2540 ){
2541 int idxNum = pCur->idxNum;
2542 const unsigned char *zMatchThis; /* RHS of the MATCH operator */
2543 EditDist3FromString *pMatchStr3 = 0; /* zMatchThis as an editdist string */
2544 char *zPattern; /* Transliteration of zMatchThis */
2545 int nPattern; /* Length of zPattern */
2546 int iLimit = 20; /* Max number of rows of output */
2547 int iScope = 3; /* Use this many characters of zClass */
2548 int iLang = 0; /* Language code */
2549 char *zSql; /* SQL of shadow table query */
2550 sqlite3_stmt *pStmt = 0; /* Shadow table query */
2551 int rc; /* Result code */
2552 int idx = 1; /* Next available filter parameter */
2553 spellfix1_vtab *p = pCur->pVTab; /* The virtual table that owns pCur */
2554 MatchQuery x; /* For passing info to RunQuery() */
2555
2556 /* Load the cost table if we have not already done so */
2557 if( p->zCostTable!=0 && p->pConfig3==0 ){
2558 p->pConfig3 = sqlite3_malloc64( sizeof(p->pConfig3[0]) );
2559 if( p->pConfig3==0 ) return SQLITE_NOMEM;
2560 memset(p->pConfig3, 0, sizeof(p->pConfig3[0]));
2561 rc = editDist3ConfigLoad(p->pConfig3, p->db, p->zCostTable);
2562 if( rc ) return rc;
2563 }
2564 memset(&x, 0, sizeof(x));
2565 x.iScope = 3; /* Default scope if none specified by "WHERE scope=N" */
2566 x.iMaxDist = -1; /* Maximum allowed edit distance */
2567
2568 if( idxNum&2 ){
2569 iLang = sqlite3_value_int(argv[idx++]);
2570 }
2571 if( idxNum&4 ){
2572 iLimit = sqlite3_value_int(argv[idx++]);
2573 if( iLimit<1 ) iLimit = 1;
2574 }
2575 if( idxNum&8 ){
2576 x.iScope = sqlite3_value_int(argv[idx++]);
2577 if( x.iScope<1 ) x.iScope = 1;
2578 if( x.iScope>SPELLFIX_MX_HASH-2 ) x.iScope = SPELLFIX_MX_HASH-2;
2579 }
2580 if( idxNum&(16|32) ){
2581 x.iMaxDist = sqlite3_value_int(argv[idx++]);
2582 if( idxNum&16 ) x.iMaxDist--;
2583 if( x.iMaxDist<0 ) x.iMaxDist = 0;
2584 }
2585 spellfix1ResetCursor(pCur);
2586 spellfix1ResizeCursor(pCur, iLimit);
2587 zMatchThis = sqlite3_value_text(argv[0]);
2588 if( zMatchThis==0 ) return SQLITE_OK;
2589 if( p->pConfig3 ){
2590 x.pLang = editDist3FindLang(p->pConfig3, iLang);
2591 pMatchStr3 = editDist3FromStringNew(x.pLang, (const char*)zMatchThis, -1);
2592 if( pMatchStr3==0 ){
2593 x.rc = SQLITE_NOMEM;
2594 goto filter_exit;
2595 }
2596 }else{
2597 x.pLang = 0;
2598 }
2599 zPattern = (char*)transliterate(zMatchThis, sqlite3_value_bytes(argv[0]));
2600 sqlite3_free(pCur->zPattern);
2601 pCur->zPattern = zPattern;
2602 if( zPattern==0 ){
2603 x.rc = SQLITE_NOMEM;
2604 goto filter_exit;
2605 }
2606 nPattern = (int)strlen(zPattern);
2607 if( zPattern[nPattern-1]=='*' ) nPattern--;
2608 zSql = sqlite3_mprintf(
2609 "SELECT id, word, rank, coalesce(k1,word)"
2610 " FROM \"%w\".\"%w_vocab\""
2611 " WHERE langid=%d AND k2>=?1 AND k2<?2",
2612 p->zDbName, p->zTableName, iLang
2613 );
2614 if( zSql==0 ){
2615 x.rc = SQLITE_NOMEM;
2616 pStmt = 0;
2617 goto filter_exit;
2618 }
2619 rc = sqlite3_prepare_v2(p->db, zSql, -1, &pStmt, 0);
2620 sqlite3_free(zSql);
2621 pCur->iLang = iLang;
2622 x.pCur = pCur;
2623 x.pStmt = pStmt;
2624 x.zPattern = zPattern;
2625 x.nPattern = nPattern;
2626 x.pMatchStr3 = pMatchStr3;
2627 x.iLang = iLang;
2628 x.rc = rc;
2629 x.pConfig3 = p->pConfig3;
2630 if( x.rc==SQLITE_OK ){
2631 spellfix1RunQuery(&x, zPattern, nPattern);
2632 }
2633
2634 if( pCur->a ){
2635 qsort(pCur->a, pCur->nRow, sizeof(pCur->a[0]), spellfix1RowCompare);
2636 pCur->iTop = iLimit;
2637 pCur->iScope = iScope;
2638 }else{
2639 x.rc = SQLITE_NOMEM;
2640 }
2641
2642 filter_exit:
2643 sqlite3_finalize(pStmt);
2644 editDist3FromStringDelete(pMatchStr3);
2645 return x.rc;
2646 }
2647
2648 /*
2649 ** This version of xFilter handles a full-table scan case
2650 */
2651 static int spellfix1FilterForFullScan(
2652 spellfix1_cursor *pCur,
2653 int argc,
2654 sqlite3_value **argv
2655 ){
2656 int rc = SQLITE_OK;
2657 int idxNum = pCur->idxNum;
2658 char *zSql;
2659 spellfix1_vtab *pVTab = pCur->pVTab;
2660 spellfix1ResetCursor(pCur);
2661 assert( idxNum==0 || idxNum==64 );
2662 zSql = sqlite3_mprintf(
2663 "SELECT word, rank, NULL, langid, id FROM \"%w\".\"%w_vocab\"%s",
2664 pVTab->zDbName, pVTab->zTableName,
2665 ((idxNum & 64) ? " WHERE rowid=?" : "")
2666 );
2667 if( zSql==0 ) return SQLITE_NOMEM;
2668 rc = sqlite3_prepare_v2(pVTab->db, zSql, -1, &pCur->pFullScan, 0);
2669 sqlite3_free(zSql);
2670 if( rc==SQLITE_OK && (idxNum & 64) ){
2671 assert( argc==1 );
2672 rc = sqlite3_bind_value(pCur->pFullScan, 1, argv[0]);
2673 }
2674 pCur->nRow = pCur->iRow = 0;
2675 if( rc==SQLITE_OK ){
2676 rc = sqlite3_step(pCur->pFullScan);
2677 if( rc==SQLITE_ROW ){ pCur->iRow = -1; rc = SQLITE_OK; }
2678 if( rc==SQLITE_DONE ){ rc = SQLITE_OK; }
2679 }else{
2680 pCur->iRow = 0;
2681 }
2682 return rc;
2683 }
2684
2685
2686 /*
2687 ** Called to "rewind" a cursor back to the beginning so that
2688 ** it starts its output over again. Always called at least once
2689 ** prior to any spellfix1Column, spellfix1Rowid, or spellfix1Eof call.
2690 */
2691 static int spellfix1Filter(
2692 sqlite3_vtab_cursor *cur,
2693 int idxNum, const char *idxStr,
2694 int argc, sqlite3_value **argv
2695 ){
2696 spellfix1_cursor *pCur = (spellfix1_cursor *)cur;
2697 int rc;
2698 pCur->idxNum = idxNum;
2699 if( idxNum & 1 ){
2700 rc = spellfix1FilterForMatch(pCur, argc, argv);
2701 }else{
2702 rc = spellfix1FilterForFullScan(pCur, argc, argv);
2703 }
2704 return rc;
2705 }
2706
2707
2708 /*
2709 ** Advance a cursor to its next row of output
2710 */
2711 static int spellfix1Next(sqlite3_vtab_cursor *cur){
2712 spellfix1_cursor *pCur = (spellfix1_cursor *)cur;
2713 int rc = SQLITE_OK;
2714 if( pCur->iRow < pCur->nRow ){
2715 if( pCur->pFullScan ){
2716 rc = sqlite3_step(pCur->pFullScan);
2717 if( rc!=SQLITE_ROW ) pCur->iRow = pCur->nRow;
2718 if( rc==SQLITE_ROW || rc==SQLITE_DONE ) rc = SQLITE_OK;
2719 }else{
2720 pCur->iRow++;
2721 }
2722 }
2723 return rc;
2724 }
2725
2726 /*
2727 ** Return TRUE if we are at the end-of-file
2728 */
2729 static int spellfix1Eof(sqlite3_vtab_cursor *cur){
2730 spellfix1_cursor *pCur = (spellfix1_cursor *)cur;
2731 return pCur->iRow>=pCur->nRow;
2732 }
2733
2734 /*
2735 ** Return columns from the current row.
2736 */
2737 static int spellfix1Column(
2738 sqlite3_vtab_cursor *cur,
2739 sqlite3_context *ctx,
2740 int i
2741 ){
2742 spellfix1_cursor *pCur = (spellfix1_cursor*)cur;
2743 if( pCur->pFullScan ){
2744 if( i<=SPELLFIX_COL_LANGID ){
2745 sqlite3_result_value(ctx, sqlite3_column_value(pCur->pFullScan, i));
2746 }else{
2747 sqlite3_result_null(ctx);
2748 }
2749 return SQLITE_OK;
2750 }
2751 switch( i ){
2752 case SPELLFIX_COL_WORD: {
2753 sqlite3_result_text(ctx, pCur->a[pCur->iRow].zWord, -1, SQLITE_STATIC);
2754 break;
2755 }
2756 case SPELLFIX_COL_RANK: {
2757 sqlite3_result_int(ctx, pCur->a[pCur->iRow].iRank);
2758 break;
2759 }
2760 case SPELLFIX_COL_DISTANCE: {
2761 sqlite3_result_int(ctx, pCur->a[pCur->iRow].iDistance);
2762 break;
2763 }
2764 case SPELLFIX_COL_LANGID: {
2765 sqlite3_result_int(ctx, pCur->iLang);
2766 break;
2767 }
2768 case SPELLFIX_COL_SCORE: {
2769 sqlite3_result_int(ctx, pCur->a[pCur->iRow].iScore);
2770 break;
2771 }
2772 case SPELLFIX_COL_MATCHLEN: {
2773 int iMatchlen = pCur->a[pCur->iRow].iMatchlen;
2774 if( iMatchlen<0 ){
2775 int nPattern = (int)strlen(pCur->zPattern);
2776 char *zWord = pCur->a[pCur->iRow].zWord;
2777 int nWord = (int)strlen(zWord);
2778
2779 if( nPattern>0 && pCur->zPattern[nPattern-1]=='*' ){
2780 char *zTranslit;
2781 int res;
2782 zTranslit = (char *)transliterate((unsigned char *)zWord, nWord);
2783 if( !zTranslit ) return SQLITE_NOMEM;
2784 res = editdist1(pCur->zPattern, zTranslit, &iMatchlen);
2785 sqlite3_free(zTranslit);
2786 if( res<0 ) return res==(-4) ? SQLITE_TOOBIG : SQLITE_NOMEM;
2787 iMatchlen = translen_to_charlen(zWord, nWord, iMatchlen);
2788 }else{
2789 iMatchlen = utf8Charlen(zWord, nWord);
2790 }
2791 }
2792
2793 sqlite3_result_int(ctx, iMatchlen);
2794 break;
2795 }
2796 case SPELLFIX_COL_PHONEHASH: {
2797 sqlite3_result_text(ctx, pCur->a[pCur->iRow].zHash, -1, SQLITE_STATIC);
2798 break;
2799 }
2800 case SPELLFIX_COL_TOP: {
2801 sqlite3_result_int(ctx, pCur->iTop);
2802 break;
2803 }
2804 case SPELLFIX_COL_SCOPE: {
2805 sqlite3_result_int(ctx, pCur->iScope);
2806 break;
2807 }
2808 case SPELLFIX_COL_SRCHCNT: {
2809 sqlite3_result_int(ctx, pCur->nSearch);
2810 break;
2811 }
2812 default: {
2813 sqlite3_result_null(ctx);
2814 break;
2815 }
2816 }
2817 return SQLITE_OK;
2818 }
2819
2820 /*
2821 ** The rowid.
2822 */
2823 static int spellfix1Rowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
2824 spellfix1_cursor *pCur = (spellfix1_cursor*)cur;
2825 if( pCur->pFullScan ){
2826 *pRowid = sqlite3_column_int64(pCur->pFullScan, 4);
2827 }else{
2828 *pRowid = pCur->a[pCur->iRow].iRowid;
2829 }
2830 return SQLITE_OK;
2831 }
2832
2833 /*
2834 ** This function is called by the xUpdate() method. It returns a string
2835 ** containing the conflict mode that xUpdate() should use for the current
2836 ** operation. One of: "ROLLBACK", "IGNORE", "ABORT" or "REPLACE".
2837 */
2838 static const char *spellfix1GetConflict(sqlite3 *db){
2839 static const char *azConflict[] = {
2840 /* Note: Instead of "FAIL" - "ABORT". */
2841 "ROLLBACK", "IGNORE", "ABORT", "ABORT", "REPLACE"
2842 };
2843 int eConflict = sqlite3_vtab_on_conflict(db);
2844
2845 assert( eConflict==SQLITE_ROLLBACK || eConflict==SQLITE_IGNORE
2846 || eConflict==SQLITE_FAIL || eConflict==SQLITE_ABORT
2847 || eConflict==SQLITE_REPLACE
2848 );
2849 assert( SQLITE_ROLLBACK==1 );
2850 assert( SQLITE_IGNORE==2 );
2851 assert( SQLITE_FAIL==3 );
2852 assert( SQLITE_ABORT==4 );
2853 assert( SQLITE_REPLACE==5 );
2854
2855 return azConflict[eConflict-1];
2856 }
2857
2858 /*
2859 ** The xUpdate() method.
2860 */
2861 static int spellfix1Update(
2862 sqlite3_vtab *pVTab,
2863 int argc,
2864 sqlite3_value **argv,
2865 sqlite_int64 *pRowid
2866 ){
2867 int rc = SQLITE_OK;
2868 sqlite3_int64 rowid, newRowid;
2869 spellfix1_vtab *p = (spellfix1_vtab*)pVTab;
2870 sqlite3 *db = p->db;
2871
2872 if( argc==1 ){
2873 /* A delete operation on the rowid given by argv[0] */
2874 rowid = *pRowid = sqlite3_value_int64(argv[0]);
2875 spellfix1DbExec(&rc, db, "DELETE FROM \"%w\".\"%w_vocab\" "
2876 " WHERE id=%lld",
2877 p->zDbName, p->zTableName, rowid);
2878 }else{
2879 const unsigned char *zWord = sqlite3_value_text(argv[SPELLFIX_COL_WORD+2]);
2880 int nWord = sqlite3_value_bytes(argv[SPELLFIX_COL_WORD+2]);
2881 int iLang = sqlite3_value_int(argv[SPELLFIX_COL_LANGID+2]);
2882 int iRank = sqlite3_value_int(argv[SPELLFIX_COL_RANK+2]);
2883 const unsigned char *zSoundslike =
2884 sqlite3_value_text(argv[SPELLFIX_COL_SOUNDSLIKE+2]);
2885 int nSoundslike = sqlite3_value_bytes(argv[SPELLFIX_COL_SOUNDSLIKE+2]);
2886 char *zK1, *zK2;
2887 int i;
2888 char c;
2889 const char *zConflict = spellfix1GetConflict(db);
2890
2891 if( zWord==0 ){
2892 /* Inserts of the form: INSERT INTO table(command) VALUES('xyzzy');
2893 ** cause zWord to be NULL, so we look at the "command" column to see
2894 ** what special actions to take */
2895 const char *zCmd =
2896 (const char*)sqlite3_value_text(argv[SPELLFIX_COL_COMMAND+2]);
2897 if( zCmd==0 ){
2898 pVTab->zErrMsg = sqlite3_mprintf("NOT NULL constraint failed: %s.word",
2899 p->zTableName);
2900 return SQLITE_CONSTRAINT_NOTNULL;
2901 }
2902 if( strcmp(zCmd,"reset")==0 ){
2903 /* Reset the edit cost table (if there is one). */
2904 editDist3ConfigDelete(p->pConfig3);
2905 p->pConfig3 = 0;
2906 return SQLITE_OK;
2907 }
2908 if( strncmp(zCmd,"edit_cost_table=",16)==0 ){
2909 editDist3ConfigDelete(p->pConfig3);
2910 p->pConfig3 = 0;
2911 sqlite3_free(p->zCostTable);
2912 p->zCostTable = spellfix1Dequote(zCmd+16);
2913 if( p->zCostTable==0 ) return SQLITE_NOMEM;
2914 if( p->zCostTable[0]==0 || sqlite3_stricmp(p->zCostTable,"null")==0 ){
2915 sqlite3_free(p->zCostTable);
2916 p->zCostTable = 0;
2917 }
2918 return SQLITE_OK;
2919 }
2920 pVTab->zErrMsg = sqlite3_mprintf("unknown value for %s.command: \"%w\"",
2921 p->zTableName, zCmd);
2922 return SQLITE_ERROR;
2923 }
2924 if( iRank<1 ) iRank = 1;
2925 if( zSoundslike ){
2926 zK1 = (char*)transliterate(zSoundslike, nSoundslike);
2927 }else{
2928 zK1 = (char*)transliterate(zWord, nWord);
2929 }
2930 if( zK1==0 ) return SQLITE_NOMEM;
2931 for(i=0; (c = zK1[i])!=0; i++){
2932 if( c>='A' && c<='Z' ) zK1[i] += 'a' - 'A';
2933 }
2934 zK2 = (char*)phoneticHash((const unsigned char*)zK1, i);
2935 if( zK2==0 ){
2936 sqlite3_free(zK1);
2937 return SQLITE_NOMEM;
2938 }
2939 if( sqlite3_value_type(argv[0])==SQLITE_NULL ){
2940 if( sqlite3_value_type(argv[1])==SQLITE_NULL ){
2941 spellfix1DbExec(&rc, db,
2942 "INSERT INTO \"%w\".\"%w_vocab\"(rank,langid,word,k1,k2) "
2943 "VALUES(%d,%d,%Q,nullif(%Q,%Q),%Q)",
2944 p->zDbName, p->zTableName,
2945 iRank, iLang, zWord, zK1, zWord, zK2
2946 );
2947 }else{
2948 newRowid = sqlite3_value_int64(argv[1]);
2949 spellfix1DbExec(&rc, db,
2950 "INSERT OR %s INTO \"%w\".\"%w_vocab\"(id,rank,langid,word,k1,k2) "
2951 "VALUES(%lld,%d,%d,%Q,nullif(%Q,%Q),%Q)",
2952 zConflict, p->zDbName, p->zTableName,
2953 newRowid, iRank, iLang, zWord, zK1, zWord, zK2
2954 );
2955 }
2956 *pRowid = sqlite3_last_insert_rowid(db);
2957 }else{
2958 rowid = sqlite3_value_int64(argv[0]);
2959 newRowid = *pRowid = sqlite3_value_int64(argv[1]);
2960 spellfix1DbExec(&rc, db,
2961 "UPDATE OR %s \"%w\".\"%w_vocab\" SET id=%lld, rank=%d, langid=%d,"
2962 " word=%Q, k1=nullif(%Q,%Q), k2=%Q WHERE id=%lld",
2963 zConflict, p->zDbName, p->zTableName, newRowid, iRank, iLang,
2964 zWord, zK1, zWord, zK2, rowid
2965 );
2966 }
2967 sqlite3_free(zK1);
2968 sqlite3_free(zK2);
2969 }
2970 return rc;
2971 }
2972
2973 /*
2974 ** Rename the spellfix1 table.
2975 */
2976 static int spellfix1Rename(sqlite3_vtab *pVTab, const char *zNew){
2977 spellfix1_vtab *p = (spellfix1_vtab*)pVTab;
2978 sqlite3 *db = p->db;
2979 int rc = SQLITE_OK;
2980 char *zNewName = sqlite3_mprintf("%s", zNew);
2981 if( zNewName==0 ){
2982 return SQLITE_NOMEM;
2983 }
2984 spellfix1DbExec(&rc, db,
2985 "ALTER TABLE \"%w\".\"%w_vocab\" RENAME TO \"%w_vocab\"",
2986 p->zDbName, p->zTableName, zNewName
2987 );
2988 if( rc==SQLITE_OK ){
2989 sqlite3_free(p->zTableName);
2990 p->zTableName = zNewName;
2991 }else{
2992 sqlite3_free(zNewName);
2993 }
2994 return rc;
2995 }
2996
2997
2998 /*
2999 ** A virtual table module that provides fuzzy search.
3000 */
3001 static sqlite3_module spellfix1Module = {
3002 0, /* iVersion */
3003 spellfix1Create, /* xCreate - handle CREATE VIRTUAL TABLE */
3004 spellfix1Connect, /* xConnect - reconnected to an existing table */
3005 spellfix1BestIndex, /* xBestIndex - figure out how to do a query */
3006 spellfix1Disconnect, /* xDisconnect - close a connection */
3007 spellfix1Destroy, /* xDestroy - handle DROP TABLE */
3008 spellfix1Open, /* xOpen - open a cursor */
3009 spellfix1Close, /* xClose - close a cursor */
3010 spellfix1Filter, /* xFilter - configure scan constraints */
3011 spellfix1Next, /* xNext - advance a cursor */
3012 spellfix1Eof, /* xEof - check for end of scan */
3013 spellfix1Column, /* xColumn - read data */
3014 spellfix1Rowid, /* xRowid - read data */
3015 spellfix1Update, /* xUpdate */
3016 0, /* xBegin */
3017 0, /* xSync */
3018 0, /* xCommit */
3019 0, /* xRollback */
3020 0, /* xFindMethod */
3021 spellfix1Rename, /* xRename */
3022 0, /* xSavepoint */
3023 0, /* xRelease */
3024 0, /* xRollbackTo */
3025 0, /* xShadowName */
3026 0 /* xIntegrity */
3027 };
3028
3029 /*
3030 ** Register the various functions and the virtual table.
3031 */
3032 static int spellfix1Register(sqlite3 *db){
3033 int rc = SQLITE_OK;
3034 unsigned int i;
3035 rc = sqlite3_create_function(db, "spellfix1_translit", 1,
3036 SQLITE_UTF8|SQLITE_DETERMINISTIC, 0,
3037 transliterateSqlFunc, 0, 0);
3038 if( rc==SQLITE_OK ){
3039 rc = sqlite3_create_function(db, "spellfix1_editdist", 2,
3040 SQLITE_UTF8|SQLITE_DETERMINISTIC, 0,
3041 editdistSqlFunc, 0, 0);
3042 }
3043 if( rc==SQLITE_OK ){
3044 rc = sqlite3_create_function(db, "spellfix1_phonehash", 1,
3045 SQLITE_UTF8|SQLITE_DETERMINISTIC, 0,
3046 phoneticHashSqlFunc, 0, 0);
3047 }
3048 if( rc==SQLITE_OK ){
3049 rc = sqlite3_create_function(db, "spellfix1_scriptcode", 1,
3050 SQLITE_UTF8|SQLITE_DETERMINISTIC, 0,
3051 scriptCodeSqlFunc, 0, 0);
3052 }
3053 if( rc==SQLITE_OK ){
3054 rc = sqlite3_create_module(db, "spellfix1", &spellfix1Module, 0);
3055 }
3056 if( rc==SQLITE_OK ){
3057 rc = editDist3Install(db);
3058 }
3059
3060 /* Verify sanity of the translit[] table */
3061 for(i=0; i<sizeof(translit)/sizeof(translit[0])-1; i++){
3062 assert( translit[i].cFrom<translit[i+1].cFrom );
3063 }
3064
3065 return rc;
3066 }
3067
3068 #endif /* SQLITE_OMIT_VIRTUALTABLE */
3069
3070 /*
3071 ** Extension load function.
3072 */
3073 #ifdef _WIN32
3074 __declspec(dllexport)
3075 #endif
3076 int sqlite3_spellfix_init(
3077 sqlite3 *db,
3078 char **pzErrMsg,
3079 const sqlite3_api_routines *pApi
3080 ){
3081 SQLITE_EXTENSION_INIT2(pApi);
3082 #ifndef SQLITE_OMIT_VIRTUALTABLE
3083 return spellfix1Register(db);
3084 #endif
3085 return SQLITE_OK;
3086 }