| 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 |
} |