| 1 |
/* |
| 2 |
** 2011 March 24 |
| 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 |
** Code for a demonstration virtual table that generates variations |
| 14 |
** on an input word at increasing edit distances from the original. |
| 15 |
** |
| 16 |
** A fuzzer virtual table is created like this: |
| 17 |
** |
| 18 |
** CREATE VIRTUAL TABLE f USING fuzzer(<fuzzer-data-table>); |
| 19 |
** |
| 20 |
** When it is created, the new fuzzer table must be supplied with the |
| 21 |
** name of a "fuzzer data table", which must reside in the same database |
| 22 |
** file as the new fuzzer table. The fuzzer data table contains the various |
| 23 |
** transformations and their costs that the fuzzer logic uses to generate |
| 24 |
** variations. |
| 25 |
** |
| 26 |
** The fuzzer data table must contain exactly four columns (more precisely, |
| 27 |
** the statement "SELECT * FROM <fuzzer_data_table>" must return records |
| 28 |
** that consist of four columns). It does not matter what the columns are |
| 29 |
** named. |
| 30 |
** |
| 31 |
** Each row in the fuzzer data table represents a single character |
| 32 |
** transformation. The left most column of the row (column 0) contains an |
| 33 |
** integer value - the identifier of the ruleset to which the transformation |
| 34 |
** rule belongs (see "MULTIPLE RULE SETS" below). The second column of the |
| 35 |
** row (column 0) contains the input character or characters. The third |
| 36 |
** column contains the output character or characters. And the fourth column |
| 37 |
** contains the integer cost of making the transformation. For example: |
| 38 |
** |
| 39 |
** CREATE TABLE f_data(ruleset, cFrom, cTo, Cost); |
| 40 |
** INSERT INTO f_data(ruleset, cFrom, cTo, Cost) VALUES(0, '', 'a', 100); |
| 41 |
** INSERT INTO f_data(ruleset, cFrom, cTo, Cost) VALUES(0, 'b', '', 87); |
| 42 |
** INSERT INTO f_data(ruleset, cFrom, cTo, Cost) VALUES(0, 'o', 'oe', 38); |
| 43 |
** INSERT INTO f_data(ruleset, cFrom, cTo, Cost) VALUES(0, 'oe', 'o', 40); |
| 44 |
** |
| 45 |
** The first row inserted into the fuzzer data table by the SQL script |
| 46 |
** above indicates that the cost of inserting a letter 'a' is 100. (All |
| 47 |
** costs are integers. We recommend that costs be scaled so that the |
| 48 |
** average cost is around 100.) The second INSERT statement creates a rule |
| 49 |
** saying that the cost of deleting a single letter 'b' is 87. The third |
| 50 |
** and fourth INSERT statements mean that the cost of transforming a |
| 51 |
** single letter "o" into the two-letter sequence "oe" is 38 and that the |
| 52 |
** cost of transforming "oe" back into "o" is 40. |
| 53 |
** |
| 54 |
** The contents of the fuzzer data table are loaded into main memory when |
| 55 |
** a fuzzer table is first created, and may be internally reloaded by the |
| 56 |
** system at any subsequent time. Therefore, the fuzzer data table should be |
| 57 |
** populated before the fuzzer table is created and not modified thereafter. |
| 58 |
** If you do need to modify the contents of the fuzzer data table, it is |
| 59 |
** recommended that the associated fuzzer table be dropped, the fuzzer data |
| 60 |
** table edited, and the fuzzer table recreated within a single transaction. |
| 61 |
** Alternatively, the fuzzer data table can be edited then the database |
| 62 |
** connection can be closed and reopened. |
| 63 |
** |
| 64 |
** Once it has been created, the fuzzer table can be queried as follows: |
| 65 |
** |
| 66 |
** SELECT word, distance FROM f |
| 67 |
** WHERE word MATCH 'abcdefg' |
| 68 |
** AND distance<200; |
| 69 |
** |
| 70 |
** This first query outputs the string "abcdefg" and all strings that |
| 71 |
** can be derived from that string by applying the specified transformations. |
| 72 |
** The strings are output together with their total transformation cost |
| 73 |
** (called "distance") and appear in order of increasing cost. No string |
| 74 |
** is output more than once. If there are multiple ways to transform the |
| 75 |
** target string into the output string then the lowest cost transform is |
| 76 |
** the one that is returned. In the example, the search is limited to |
| 77 |
** strings with a total distance of less than 200. |
| 78 |
** |
| 79 |
** The fuzzer is a read-only table. Any attempt to DELETE, INSERT, or |
| 80 |
** UPDATE on a fuzzer table will throw an error. |
| 81 |
** |
| 82 |
** It is important to put some kind of a limit on the fuzzer output. This |
| 83 |
** can be either in the form of a LIMIT clause at the end of the query, |
| 84 |
** or better, a "distance<NNN" constraint where NNN is some number. The |
| 85 |
** running time and memory requirement is exponential in the value of NNN |
| 86 |
** so you want to make sure that NNN is not too big. A value of NNN that |
| 87 |
** is about twice the average transformation cost seems to give good results. |
| 88 |
** |
| 89 |
** The fuzzer table can be useful for tasks such as spelling correction. |
| 90 |
** Suppose there is a second table vocabulary(w) where the w column contains |
| 91 |
** all correctly spelled words. Let $word be a word you want to look up. |
| 92 |
** |
| 93 |
** SELECT vocabulary.w FROM f, vocabulary |
| 94 |
** WHERE f.word MATCH $word |
| 95 |
** AND f.distance<=200 |
| 96 |
** AND f.word=vocabulary.w |
| 97 |
** LIMIT 20 |
| 98 |
** |
| 99 |
** The query above gives the 20 closest words to the $word being tested. |
| 100 |
** (Note that for good performance, the vocabulary.w column should be |
| 101 |
** indexed.) |
| 102 |
** |
| 103 |
** A similar query can be used to find all words in the dictionary that |
| 104 |
** begin with some prefix $prefix: |
| 105 |
** |
| 106 |
** SELECT vocabulary.w FROM f, vocabulary |
| 107 |
** WHERE f.word MATCH $prefix |
| 108 |
** AND f.distance<=200 |
| 109 |
** AND vocabulary.w BETWEEN f.word AND (f.word || x'F7BFBFBF') |
| 110 |
** LIMIT 50 |
| 111 |
** |
| 112 |
** This last query will show up to 50 words out of the vocabulary that |
| 113 |
** match or nearly match the $prefix. |
| 114 |
** |
| 115 |
** MULTIPLE RULE SETS |
| 116 |
** |
| 117 |
** Normally, the "ruleset" value associated with all character transformations |
| 118 |
** in the fuzzer data table is zero. However, if required, the fuzzer table |
| 119 |
** allows multiple rulesets to be defined. Each query uses only a single |
| 120 |
** ruleset. This allows, for example, a single fuzzer table to support |
| 121 |
** multiple languages. |
| 122 |
** |
| 123 |
** By default, only the rules from ruleset 0 are used. To specify an |
| 124 |
** alternative ruleset, a "ruleset = ?" expression must be added to the |
| 125 |
** WHERE clause of a SELECT, where ? is the identifier of the desired |
| 126 |
** ruleset. For example: |
| 127 |
** |
| 128 |
** SELECT vocabulary.w FROM f, vocabulary |
| 129 |
** WHERE f.word MATCH $word |
| 130 |
** AND f.distance<=200 |
| 131 |
** AND f.word=vocabulary.w |
| 132 |
** AND f.ruleset=1 -- Specify the ruleset to use here |
| 133 |
** LIMIT 20 |
| 134 |
** |
| 135 |
** If no "ruleset = ?" constraint is specified in the WHERE clause, ruleset |
| 136 |
** 0 is used. |
| 137 |
** |
| 138 |
** LIMITS |
| 139 |
** |
| 140 |
** The maximum ruleset number is 2147483647. The maximum length of either |
| 141 |
** of the strings in the second or third column of the fuzzer data table |
| 142 |
** is 50 bytes. The maximum cost on a rule is 1000. |
| 143 |
*/ |
| 144 |
#include "sqlite3ext.h" |
| 145 |
SQLITE_EXTENSION_INIT1 |
| 146 |
|
| 147 |
/* If SQLITE_DEBUG is not defined, disable assert statements. */ |
| 148 |
#if !defined(NDEBUG) && !defined(SQLITE_DEBUG) |
| 149 |
# define NDEBUG |
| 150 |
#endif |
| 151 |
|
| 152 |
#include <stdlib.h> |
| 153 |
#include <string.h> |
| 154 |
#include <assert.h> |
| 155 |
#include <stdio.h> |
| 156 |
|
| 157 |
#ifndef SQLITE_OMIT_VIRTUALTABLE |
| 158 |
|
| 159 |
/* |
| 160 |
** Forward declaration of objects used by this implementation |
| 161 |
*/ |
| 162 |
typedef struct fuzzer_vtab fuzzer_vtab; |
| 163 |
typedef struct fuzzer_cursor fuzzer_cursor; |
| 164 |
typedef struct fuzzer_rule fuzzer_rule; |
| 165 |
typedef struct fuzzer_seen fuzzer_seen; |
| 166 |
typedef struct fuzzer_stem fuzzer_stem; |
| 167 |
|
| 168 |
/* |
| 169 |
** Various types. |
| 170 |
** |
| 171 |
** fuzzer_cost is the "cost" of an edit operation. |
| 172 |
** |
| 173 |
** fuzzer_len is the length of a matching string. |
| 174 |
** |
| 175 |
** fuzzer_ruleid is an ruleset identifier. |
| 176 |
*/ |
| 177 |
typedef int fuzzer_cost; |
| 178 |
typedef signed char fuzzer_len; |
| 179 |
typedef int fuzzer_ruleid; |
| 180 |
|
| 181 |
/* |
| 182 |
** Limits |
| 183 |
*/ |
| 184 |
#define FUZZER_MX_LENGTH 50 /* Maximum length of a rule string */ |
| 185 |
#define FUZZER_MX_RULEID 2147483647 /* Maximum rule ID */ |
| 186 |
#define FUZZER_MX_COST 1000 /* Maximum single-rule cost */ |
| 187 |
#define FUZZER_MX_OUTPUT_LENGTH 100 /* Maximum length of an output string */ |
| 188 |
|
| 189 |
|
| 190 |
/* |
| 191 |
** Each transformation rule is stored as an instance of this object. |
| 192 |
** All rules are kept on a linked list sorted by rCost. |
| 193 |
*/ |
| 194 |
struct fuzzer_rule { |
| 195 |
fuzzer_rule *pNext; /* Next rule in order of increasing rCost */ |
| 196 |
char *zFrom; /* Transform from */ |
| 197 |
fuzzer_cost rCost; /* Cost of this transformation */ |
| 198 |
fuzzer_len nFrom, nTo; /* Length of the zFrom and zTo strings */ |
| 199 |
fuzzer_ruleid iRuleset; /* The rule set to which this rule belongs */ |
| 200 |
char zTo[4]; /* Transform to (extra space appended) */ |
| 201 |
}; |
| 202 |
|
| 203 |
/* |
| 204 |
** A stem object is used to generate variants. It is also used to record |
| 205 |
** previously generated outputs. |
| 206 |
** |
| 207 |
** Every stem is added to a hash table as it is output. Generation of |
| 208 |
** duplicate stems is suppressed. |
| 209 |
** |
| 210 |
** Active stems (those that might generate new outputs) are kept on a linked |
| 211 |
** list sorted by increasing cost. The cost is the sum of rBaseCost and |
| 212 |
** pRule->rCost. |
| 213 |
*/ |
| 214 |
struct fuzzer_stem { |
| 215 |
char *zBasis; /* Word being fuzzed */ |
| 216 |
const fuzzer_rule *pRule; /* Current rule to apply */ |
| 217 |
fuzzer_stem *pNext; /* Next stem in rCost order */ |
| 218 |
fuzzer_stem *pHash; /* Next stem with same hash on zBasis */ |
| 219 |
fuzzer_cost rBaseCost; /* Base cost of getting to zBasis */ |
| 220 |
fuzzer_cost rCostX; /* Precomputed rBaseCost + pRule->rCost */ |
| 221 |
fuzzer_len nBasis; /* Length of the zBasis string */ |
| 222 |
fuzzer_len n; /* Apply pRule at this character offset */ |
| 223 |
}; |
| 224 |
|
| 225 |
/* |
| 226 |
** A fuzzer virtual-table object |
| 227 |
*/ |
| 228 |
struct fuzzer_vtab { |
| 229 |
sqlite3_vtab base; /* Base class - must be first */ |
| 230 |
char *zClassName; /* Name of this class. Default: "fuzzer" */ |
| 231 |
fuzzer_rule *pRule; /* All active rules in this fuzzer */ |
| 232 |
int nCursor; /* Number of active cursors */ |
| 233 |
}; |
| 234 |
|
| 235 |
#define FUZZER_HASH 4001 /* Hash table size */ |
| 236 |
#define FUZZER_NQUEUE 20 /* Number of slots on the stem queue */ |
| 237 |
|
| 238 |
/* A fuzzer cursor object */ |
| 239 |
struct fuzzer_cursor { |
| 240 |
sqlite3_vtab_cursor base; /* Base class - must be first */ |
| 241 |
sqlite3_int64 iRowid; /* The rowid of the current word */ |
| 242 |
fuzzer_vtab *pVtab; /* The virtual table this cursor belongs to */ |
| 243 |
fuzzer_cost rLimit; /* Maximum cost of any term */ |
| 244 |
fuzzer_stem *pStem; /* Stem with smallest rCostX */ |
| 245 |
fuzzer_stem *pDone; /* Stems already processed to completion */ |
| 246 |
fuzzer_stem *aQueue[FUZZER_NQUEUE]; /* Queue of stems with higher rCostX */ |
| 247 |
int mxQueue; /* Largest used index in aQueue[] */ |
| 248 |
char *zBuf; /* Temporary use buffer */ |
| 249 |
int nBuf; /* Bytes allocated for zBuf */ |
| 250 |
int nStem; /* Number of stems allocated */ |
| 251 |
int iRuleset; /* Only process rules from this ruleset */ |
| 252 |
fuzzer_rule nullRule; /* Null rule used first */ |
| 253 |
fuzzer_stem *apHash[FUZZER_HASH]; /* Hash of previously generated terms */ |
| 254 |
}; |
| 255 |
|
| 256 |
/* |
| 257 |
** The two input rule lists are both sorted in order of increasing |
| 258 |
** cost. Merge them together into a single list, sorted by cost, and |
| 259 |
** return a pointer to the head of that list. |
| 260 |
*/ |
| 261 |
static fuzzer_rule *fuzzerMergeRules(fuzzer_rule *pA, fuzzer_rule *pB){ |
| 262 |
fuzzer_rule head; |
| 263 |
fuzzer_rule *pTail; |
| 264 |
|
| 265 |
pTail = &head; |
| 266 |
while( pA && pB ){ |
| 267 |
if( pA->rCost<=pB->rCost ){ |
| 268 |
pTail->pNext = pA; |
| 269 |
pTail = pA; |
| 270 |
pA = pA->pNext; |
| 271 |
}else{ |
| 272 |
pTail->pNext = pB; |
| 273 |
pTail = pB; |
| 274 |
pB = pB->pNext; |
| 275 |
} |
| 276 |
} |
| 277 |
if( pA==0 ){ |
| 278 |
pTail->pNext = pB; |
| 279 |
}else{ |
| 280 |
pTail->pNext = pA; |
| 281 |
} |
| 282 |
return head.pNext; |
| 283 |
} |
| 284 |
|
| 285 |
/* |
| 286 |
** Statement pStmt currently points to a row in the fuzzer data table. This |
| 287 |
** function allocates and populates a fuzzer_rule structure according to |
| 288 |
** the content of the row. |
| 289 |
** |
| 290 |
** If successful, *ppRule is set to point to the new object and SQLITE_OK |
| 291 |
** is returned. Otherwise, *ppRule is zeroed, *pzErr may be set to point |
| 292 |
** to an error message and an SQLite error code returned. |
| 293 |
*/ |
| 294 |
static int fuzzerLoadOneRule( |
| 295 |
fuzzer_vtab *p, /* Fuzzer virtual table handle */ |
| 296 |
sqlite3_stmt *pStmt, /* Base rule on statements current row */ |
| 297 |
fuzzer_rule **ppRule, /* OUT: New rule object */ |
| 298 |
char **pzErr /* OUT: Error message */ |
| 299 |
){ |
| 300 |
sqlite3_int64 iRuleset = sqlite3_column_int64(pStmt, 0); |
| 301 |
const char *zFrom = (const char *)sqlite3_column_text(pStmt, 1); |
| 302 |
const char *zTo = (const char *)sqlite3_column_text(pStmt, 2); |
| 303 |
int nCost = sqlite3_column_int(pStmt, 3); |
| 304 |
|
| 305 |
int rc = SQLITE_OK; /* Return code */ |
| 306 |
int nFrom; /* Size of string zFrom, in bytes */ |
| 307 |
int nTo; /* Size of string zTo, in bytes */ |
| 308 |
fuzzer_rule *pRule = 0; /* New rule object to return */ |
| 309 |
|
| 310 |
if( zFrom==0 ) zFrom = ""; |
| 311 |
if( zTo==0 ) zTo = ""; |
| 312 |
nFrom = (int)strlen(zFrom); |
| 313 |
nTo = (int)strlen(zTo); |
| 314 |
|
| 315 |
/* Silently ignore null transformations */ |
| 316 |
if( strcmp(zFrom, zTo)==0 ){ |
| 317 |
*ppRule = 0; |
| 318 |
return SQLITE_OK; |
| 319 |
} |
| 320 |
|
| 321 |
if( nCost<=0 || nCost>FUZZER_MX_COST ){ |
| 322 |
*pzErr = sqlite3_mprintf("%s: cost must be between 1 and %d", |
| 323 |
p->zClassName, FUZZER_MX_COST |
| 324 |
); |
| 325 |
rc = SQLITE_ERROR; |
| 326 |
}else |
| 327 |
if( nFrom>FUZZER_MX_LENGTH || nTo>FUZZER_MX_LENGTH ){ |
| 328 |
*pzErr = sqlite3_mprintf("%s: maximum string length is %d", |
| 329 |
p->zClassName, FUZZER_MX_LENGTH |
| 330 |
); |
| 331 |
rc = SQLITE_ERROR; |
| 332 |
}else |
| 333 |
if( iRuleset<0 || iRuleset>FUZZER_MX_RULEID ){ |
| 334 |
*pzErr = sqlite3_mprintf("%s: ruleset must be between 0 and %d", |
| 335 |
p->zClassName, FUZZER_MX_RULEID |
| 336 |
); |
| 337 |
rc = SQLITE_ERROR; |
| 338 |
}else{ |
| 339 |
|
| 340 |
pRule = sqlite3_malloc64( sizeof(*pRule) + nFrom + nTo ); |
| 341 |
if( pRule==0 ){ |
| 342 |
rc = SQLITE_NOMEM; |
| 343 |
}else{ |
| 344 |
memset(pRule, 0, sizeof(*pRule)); |
| 345 |
pRule->zFrom = pRule->zTo; |
| 346 |
pRule->zFrom += nTo + 1; |
| 347 |
pRule->nFrom = (fuzzer_len)nFrom; |
| 348 |
memcpy(pRule->zFrom, zFrom, nFrom+1); |
| 349 |
memcpy(pRule->zTo, zTo, nTo+1); |
| 350 |
pRule->nTo = (fuzzer_len)nTo; |
| 351 |
pRule->rCost = nCost; |
| 352 |
pRule->iRuleset = (int)iRuleset; |
| 353 |
} |
| 354 |
} |
| 355 |
|
| 356 |
*ppRule = pRule; |
| 357 |
return rc; |
| 358 |
} |
| 359 |
|
| 360 |
/* |
| 361 |
** Load the content of the fuzzer data table into memory. |
| 362 |
*/ |
| 363 |
static int fuzzerLoadRules( |
| 364 |
sqlite3 *db, /* Database handle */ |
| 365 |
fuzzer_vtab *p, /* Virtual fuzzer table to configure */ |
| 366 |
const char *zDb, /* Database containing rules data */ |
| 367 |
const char *zData, /* Table containing rules data */ |
| 368 |
char **pzErr /* OUT: Error message */ |
| 369 |
){ |
| 370 |
int rc = SQLITE_OK; /* Return code */ |
| 371 |
char *zSql; /* SELECT used to read from rules table */ |
| 372 |
fuzzer_rule *pHead = 0; |
| 373 |
|
| 374 |
zSql = sqlite3_mprintf("SELECT * FROM %Q.%Q", zDb, zData); |
| 375 |
if( zSql==0 ){ |
| 376 |
rc = SQLITE_NOMEM; |
| 377 |
}else{ |
| 378 |
int rc2; /* finalize() return code */ |
| 379 |
sqlite3_stmt *pStmt = 0; |
| 380 |
rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0); |
| 381 |
if( rc!=SQLITE_OK ){ |
| 382 |
*pzErr = sqlite3_mprintf("%s: %s", p->zClassName, sqlite3_errmsg(db)); |
| 383 |
}else if( sqlite3_column_count(pStmt)!=4 ){ |
| 384 |
*pzErr = sqlite3_mprintf("%s: %s has %d columns, expected 4", |
| 385 |
p->zClassName, zData, sqlite3_column_count(pStmt) |
| 386 |
); |
| 387 |
rc = SQLITE_ERROR; |
| 388 |
}else{ |
| 389 |
while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pStmt) ){ |
| 390 |
fuzzer_rule *pRule = 0; |
| 391 |
rc = fuzzerLoadOneRule(p, pStmt, &pRule, pzErr); |
| 392 |
if( pRule ){ |
| 393 |
pRule->pNext = pHead; |
| 394 |
pHead = pRule; |
| 395 |
} |
| 396 |
} |
| 397 |
} |
| 398 |
rc2 = sqlite3_finalize(pStmt); |
| 399 |
if( rc==SQLITE_OK ) rc = rc2; |
| 400 |
} |
| 401 |
sqlite3_free(zSql); |
| 402 |
|
| 403 |
/* All rules are now in a singly linked list starting at pHead. This |
| 404 |
** block sorts them by cost and then sets fuzzer_vtab.pRule to point to |
| 405 |
** point to the head of the sorted list. |
| 406 |
*/ |
| 407 |
if( rc==SQLITE_OK ){ |
| 408 |
unsigned int i; |
| 409 |
fuzzer_rule *pX; |
| 410 |
fuzzer_rule *a[15]; |
| 411 |
for(i=0; i<sizeof(a)/sizeof(a[0]); i++) a[i] = 0; |
| 412 |
while( (pX = pHead)!=0 ){ |
| 413 |
pHead = pX->pNext; |
| 414 |
pX->pNext = 0; |
| 415 |
for(i=0; a[i] && i<sizeof(a)/sizeof(a[0])-1; i++){ |
| 416 |
pX = fuzzerMergeRules(a[i], pX); |
| 417 |
a[i] = 0; |
| 418 |
} |
| 419 |
a[i] = fuzzerMergeRules(a[i], pX); |
| 420 |
} |
| 421 |
for(pX=a[0], i=1; i<sizeof(a)/sizeof(a[0]); i++){ |
| 422 |
pX = fuzzerMergeRules(a[i], pX); |
| 423 |
} |
| 424 |
p->pRule = fuzzerMergeRules(p->pRule, pX); |
| 425 |
}else{ |
| 426 |
/* An error has occurred. Setting p->pRule to point to the head of the |
| 427 |
** allocated list ensures that the list will be cleaned up in this case. |
| 428 |
*/ |
| 429 |
assert( p->pRule==0 ); |
| 430 |
p->pRule = pHead; |
| 431 |
} |
| 432 |
|
| 433 |
return rc; |
| 434 |
} |
| 435 |
|
| 436 |
/* |
| 437 |
** This function converts an SQL quoted string into an unquoted string |
| 438 |
** and returns a pointer to a buffer allocated using sqlite3_malloc() |
| 439 |
** containing the result. The caller should eventually free this buffer |
| 440 |
** using sqlite3_free. |
| 441 |
** |
| 442 |
** Examples: |
| 443 |
** |
| 444 |
** "abc" becomes abc |
| 445 |
** 'xyz' becomes xyz |
| 446 |
** [pqr] becomes pqr |
| 447 |
** `mno` becomes mno |
| 448 |
*/ |
| 449 |
static char *fuzzerDequote(const char *zIn){ |
| 450 |
sqlite3_int64 nIn; /* Size of input string, in bytes */ |
| 451 |
char *zOut; /* Output (dequoted) string */ |
| 452 |
|
| 453 |
nIn = strlen(zIn); |
| 454 |
zOut = sqlite3_malloc64(nIn+1); |
| 455 |
if( zOut ){ |
| 456 |
char q = zIn[0]; /* Quote character (if any ) */ |
| 457 |
|
| 458 |
if( q!='[' && q!= '\'' && q!='"' && q!='`' ){ |
| 459 |
memcpy(zOut, zIn, (size_t)(nIn+1)); |
| 460 |
}else{ |
| 461 |
int iOut = 0; /* Index of next byte to write to output */ |
| 462 |
int iIn; /* Index of next byte to read from input */ |
| 463 |
|
| 464 |
if( q=='[' ) q = ']'; |
| 465 |
for(iIn=1; iIn<nIn; iIn++){ |
| 466 |
if( zIn[iIn]==q ) iIn++; |
| 467 |
zOut[iOut++] = zIn[iIn]; |
| 468 |
} |
| 469 |
} |
| 470 |
assert( (int)strlen(zOut)<=nIn ); |
| 471 |
} |
| 472 |
return zOut; |
| 473 |
} |
| 474 |
|
| 475 |
/* |
| 476 |
** xDisconnect/xDestroy method for the fuzzer module. |
| 477 |
*/ |
| 478 |
static int fuzzerDisconnect(sqlite3_vtab *pVtab){ |
| 479 |
fuzzer_vtab *p = (fuzzer_vtab*)pVtab; |
| 480 |
assert( p->nCursor==0 ); |
| 481 |
while( p->pRule ){ |
| 482 |
fuzzer_rule *pRule = p->pRule; |
| 483 |
p->pRule = pRule->pNext; |
| 484 |
sqlite3_free(pRule); |
| 485 |
} |
| 486 |
sqlite3_free(p); |
| 487 |
return SQLITE_OK; |
| 488 |
} |
| 489 |
|
| 490 |
/* |
| 491 |
** xConnect/xCreate method for the fuzzer module. Arguments are: |
| 492 |
** |
| 493 |
** argv[0] -> module name ("fuzzer") |
| 494 |
** argv[1] -> database name |
| 495 |
** argv[2] -> table name |
| 496 |
** argv[3] -> fuzzer rule table name |
| 497 |
*/ |
| 498 |
static int fuzzerConnect( |
| 499 |
sqlite3 *db, |
| 500 |
void *pAux, |
| 501 |
int argc, const char *const*argv, |
| 502 |
sqlite3_vtab **ppVtab, |
| 503 |
char **pzErr |
| 504 |
){ |
| 505 |
int rc = SQLITE_OK; /* Return code */ |
| 506 |
fuzzer_vtab *pNew = 0; /* New virtual table */ |
| 507 |
const char *zModule = argv[0]; |
| 508 |
const char *zDb = argv[1]; |
| 509 |
|
| 510 |
if( argc!=4 ){ |
| 511 |
*pzErr = sqlite3_mprintf( |
| 512 |
"%s: wrong number of CREATE VIRTUAL TABLE arguments", zModule |
| 513 |
); |
| 514 |
rc = SQLITE_ERROR; |
| 515 |
}else{ |
| 516 |
sqlite3_int64 nModule; /* Length of zModule, in bytes */ |
| 517 |
|
| 518 |
nModule = strlen(zModule); |
| 519 |
pNew = sqlite3_malloc64( sizeof(*pNew) + nModule + 1); |
| 520 |
if( pNew==0 ){ |
| 521 |
rc = SQLITE_NOMEM; |
| 522 |
}else{ |
| 523 |
char *zTab; /* Dequoted name of fuzzer data table */ |
| 524 |
|
| 525 |
memset(pNew, 0, sizeof(*pNew)); |
| 526 |
pNew->zClassName = (char*)&pNew[1]; |
| 527 |
memcpy(pNew->zClassName, zModule, (size_t)(nModule+1)); |
| 528 |
|
| 529 |
zTab = fuzzerDequote(argv[3]); |
| 530 |
if( zTab==0 ){ |
| 531 |
rc = SQLITE_NOMEM; |
| 532 |
}else{ |
| 533 |
rc = fuzzerLoadRules(db, pNew, zDb, zTab, pzErr); |
| 534 |
sqlite3_free(zTab); |
| 535 |
} |
| 536 |
|
| 537 |
if( rc==SQLITE_OK ){ |
| 538 |
rc = sqlite3_declare_vtab(db, "CREATE TABLE x(word,distance,ruleset)"); |
| 539 |
} |
| 540 |
if( rc!=SQLITE_OK ){ |
| 541 |
fuzzerDisconnect((sqlite3_vtab *)pNew); |
| 542 |
pNew = 0; |
| 543 |
}else{ |
| 544 |
sqlite3_vtab_config(db, SQLITE_VTAB_INNOCUOUS); |
| 545 |
} |
| 546 |
} |
| 547 |
} |
| 548 |
|
| 549 |
*ppVtab = (sqlite3_vtab *)pNew; |
| 550 |
return rc; |
| 551 |
} |
| 552 |
|
| 553 |
/* |
| 554 |
** Open a new fuzzer cursor. |
| 555 |
*/ |
| 556 |
static int fuzzerOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){ |
| 557 |
fuzzer_vtab *p = (fuzzer_vtab*)pVTab; |
| 558 |
fuzzer_cursor *pCur; |
| 559 |
pCur = sqlite3_malloc64( sizeof(*pCur) ); |
| 560 |
if( pCur==0 ) return SQLITE_NOMEM; |
| 561 |
memset(pCur, 0, sizeof(*pCur)); |
| 562 |
pCur->pVtab = p; |
| 563 |
*ppCursor = &pCur->base; |
| 564 |
p->nCursor++; |
| 565 |
return SQLITE_OK; |
| 566 |
} |
| 567 |
|
| 568 |
/* |
| 569 |
** Free all stems in a list. |
| 570 |
*/ |
| 571 |
static void fuzzerClearStemList(fuzzer_stem *pStem){ |
| 572 |
while( pStem ){ |
| 573 |
fuzzer_stem *pNext = pStem->pNext; |
| 574 |
sqlite3_free(pStem); |
| 575 |
pStem = pNext; |
| 576 |
} |
| 577 |
} |
| 578 |
|
| 579 |
/* |
| 580 |
** Free up all the memory allocated by a cursor. Set it rLimit to 0 |
| 581 |
** to indicate that it is at EOF. |
| 582 |
*/ |
| 583 |
static void fuzzerClearCursor(fuzzer_cursor *pCur, int clearHash){ |
| 584 |
int i; |
| 585 |
fuzzerClearStemList(pCur->pStem); |
| 586 |
fuzzerClearStemList(pCur->pDone); |
| 587 |
for(i=0; i<FUZZER_NQUEUE; i++) fuzzerClearStemList(pCur->aQueue[i]); |
| 588 |
pCur->rLimit = (fuzzer_cost)0; |
| 589 |
if( clearHash && pCur->nStem ){ |
| 590 |
pCur->mxQueue = 0; |
| 591 |
pCur->pStem = 0; |
| 592 |
pCur->pDone = 0; |
| 593 |
memset(pCur->aQueue, 0, sizeof(pCur->aQueue)); |
| 594 |
memset(pCur->apHash, 0, sizeof(pCur->apHash)); |
| 595 |
} |
| 596 |
pCur->nStem = 0; |
| 597 |
} |
| 598 |
|
| 599 |
/* |
| 600 |
** Close a fuzzer cursor. |
| 601 |
*/ |
| 602 |
static int fuzzerClose(sqlite3_vtab_cursor *cur){ |
| 603 |
fuzzer_cursor *pCur = (fuzzer_cursor *)cur; |
| 604 |
fuzzerClearCursor(pCur, 0); |
| 605 |
sqlite3_free(pCur->zBuf); |
| 606 |
pCur->pVtab->nCursor--; |
| 607 |
sqlite3_free(pCur); |
| 608 |
return SQLITE_OK; |
| 609 |
} |
| 610 |
|
| 611 |
/* |
| 612 |
** Compute the current output term for a fuzzer_stem. |
| 613 |
*/ |
| 614 |
static int fuzzerRender( |
| 615 |
fuzzer_stem *pStem, /* The stem to be rendered */ |
| 616 |
char **pzBuf, /* Write results into this buffer. realloc if needed */ |
| 617 |
int *pnBuf /* Size of the buffer */ |
| 618 |
){ |
| 619 |
const fuzzer_rule *pRule = pStem->pRule; |
| 620 |
sqlite3_int64 n; /* Size of output term without nul-term */ |
| 621 |
char *z; /* Buffer to assemble output term in */ |
| 622 |
|
| 623 |
n = pStem->nBasis + pRule->nTo - pRule->nFrom; |
| 624 |
if( (*pnBuf)<n+1 ){ |
| 625 |
(*pzBuf) = sqlite3_realloc64((*pzBuf), n+100); |
| 626 |
if( (*pzBuf)==0 ) return SQLITE_NOMEM; |
| 627 |
(*pnBuf) = n+100; |
| 628 |
} |
| 629 |
n = pStem->n; |
| 630 |
z = *pzBuf; |
| 631 |
if( n<0 ){ |
| 632 |
memcpy(z, pStem->zBasis, pStem->nBasis+1); |
| 633 |
}else{ |
| 634 |
memcpy(z, pStem->zBasis, n); |
| 635 |
memcpy(&z[n], pRule->zTo, pRule->nTo); |
| 636 |
memcpy(&z[n+pRule->nTo], &pStem->zBasis[n+pRule->nFrom], |
| 637 |
pStem->nBasis-n-pRule->nFrom+1); |
| 638 |
} |
| 639 |
|
| 640 |
assert( z[pStem->nBasis + pRule->nTo - pRule->nFrom]==0 ); |
| 641 |
return SQLITE_OK; |
| 642 |
} |
| 643 |
|
| 644 |
/* |
| 645 |
** Compute a hash on zBasis. |
| 646 |
*/ |
| 647 |
static unsigned int fuzzerHash(const char *z){ |
| 648 |
unsigned int h = 0; |
| 649 |
while( *z ){ h = (h<<3) ^ (h>>29) ^ *(z++); } |
| 650 |
return h % FUZZER_HASH; |
| 651 |
} |
| 652 |
|
| 653 |
/* |
| 654 |
** Current cost of a stem |
| 655 |
*/ |
| 656 |
static fuzzer_cost fuzzerCost(fuzzer_stem *pStem){ |
| 657 |
return pStem->rCostX = pStem->rBaseCost + pStem->pRule->rCost; |
| 658 |
} |
| 659 |
|
| 660 |
#if 0 |
| 661 |
/* |
| 662 |
** Print a description of a fuzzer_stem on stderr. |
| 663 |
*/ |
| 664 |
static void fuzzerStemPrint( |
| 665 |
const char *zPrefix, |
| 666 |
fuzzer_stem *pStem, |
| 667 |
const char *zSuffix |
| 668 |
){ |
| 669 |
if( pStem->n<0 ){ |
| 670 |
fprintf(stderr, "%s[%s](%d)-->self%s", |
| 671 |
zPrefix, |
| 672 |
pStem->zBasis, pStem->rBaseCost, |
| 673 |
zSuffix |
| 674 |
); |
| 675 |
}else{ |
| 676 |
char *zBuf = 0; |
| 677 |
int nBuf = 0; |
| 678 |
if( fuzzerRender(pStem, &zBuf, &nBuf)!=SQLITE_OK ) return; |
| 679 |
fprintf(stderr, "%s[%s](%d)-->{%s}(%d)%s", |
| 680 |
zPrefix, |
| 681 |
pStem->zBasis, pStem->rBaseCost, zBuf, pStem->, |
| 682 |
zSuffix |
| 683 |
); |
| 684 |
sqlite3_free(zBuf); |
| 685 |
} |
| 686 |
} |
| 687 |
#endif |
| 688 |
|
| 689 |
/* |
| 690 |
** Return 1 if the string to which the cursor is point has already |
| 691 |
** been emitted. Return 0 if not. Return -1 on a memory allocation |
| 692 |
** failures. |
| 693 |
*/ |
| 694 |
static int fuzzerSeen(fuzzer_cursor *pCur, fuzzer_stem *pStem){ |
| 695 |
unsigned int h; |
| 696 |
fuzzer_stem *pLookup; |
| 697 |
|
| 698 |
if( fuzzerRender(pStem, &pCur->zBuf, &pCur->nBuf)==SQLITE_NOMEM ){ |
| 699 |
return -1; |
| 700 |
} |
| 701 |
h = fuzzerHash(pCur->zBuf); |
| 702 |
pLookup = pCur->apHash[h]; |
| 703 |
while( pLookup && strcmp(pLookup->zBasis, pCur->zBuf)!=0 ){ |
| 704 |
pLookup = pLookup->pHash; |
| 705 |
} |
| 706 |
return pLookup!=0; |
| 707 |
} |
| 708 |
|
| 709 |
/* |
| 710 |
** If argument pRule is NULL, this function returns false. |
| 711 |
** |
| 712 |
** Otherwise, it returns true if rule pRule should be skipped. A rule |
| 713 |
** should be skipped if it does not belong to rule-set iRuleset, or if |
| 714 |
** applying it to stem pStem would create a string longer than |
| 715 |
** FUZZER_MX_OUTPUT_LENGTH bytes. |
| 716 |
*/ |
| 717 |
static int fuzzerSkipRule( |
| 718 |
const fuzzer_rule *pRule, /* Determine whether or not to skip this */ |
| 719 |
fuzzer_stem *pStem, /* Stem rule may be applied to */ |
| 720 |
int iRuleset /* Rule-set used by the current query */ |
| 721 |
){ |
| 722 |
return pRule && ( |
| 723 |
(pRule->iRuleset!=iRuleset) |
| 724 |
|| (pStem->nBasis + pRule->nTo - pRule->nFrom)>FUZZER_MX_OUTPUT_LENGTH |
| 725 |
); |
| 726 |
} |
| 727 |
|
| 728 |
/* |
| 729 |
** Advance a fuzzer_stem to its next value. Return 0 if there are |
| 730 |
** no more values that can be generated by this fuzzer_stem. Return |
| 731 |
** -1 on a memory allocation failure. |
| 732 |
*/ |
| 733 |
static int fuzzerAdvance(fuzzer_cursor *pCur, fuzzer_stem *pStem){ |
| 734 |
const fuzzer_rule *pRule; |
| 735 |
while( (pRule = pStem->pRule)!=0 ){ |
| 736 |
assert( pRule==&pCur->nullRule || pRule->iRuleset==pCur->iRuleset ); |
| 737 |
while( pStem->n < pStem->nBasis - pRule->nFrom ){ |
| 738 |
pStem->n++; |
| 739 |
if( pRule->nFrom==0 |
| 740 |
|| memcmp(&pStem->zBasis[pStem->n], pRule->zFrom, pRule->nFrom)==0 |
| 741 |
){ |
| 742 |
/* Found a rewrite case. Make sure it is not a duplicate */ |
| 743 |
int rc = fuzzerSeen(pCur, pStem); |
| 744 |
if( rc<0 ) return -1; |
| 745 |
if( rc==0 ){ |
| 746 |
fuzzerCost(pStem); |
| 747 |
return 1; |
| 748 |
} |
| 749 |
} |
| 750 |
} |
| 751 |
pStem->n = -1; |
| 752 |
do{ |
| 753 |
pRule = pRule->pNext; |
| 754 |
}while( fuzzerSkipRule(pRule, pStem, pCur->iRuleset) ); |
| 755 |
pStem->pRule = pRule; |
| 756 |
if( pRule && fuzzerCost(pStem)>pCur->rLimit ) pStem->pRule = 0; |
| 757 |
} |
| 758 |
return 0; |
| 759 |
} |
| 760 |
|
| 761 |
/* |
| 762 |
** The two input stem lists are both sorted in order of increasing |
| 763 |
** rCostX. Merge them together into a single list, sorted by rCostX, and |
| 764 |
** return a pointer to the head of that new list. |
| 765 |
*/ |
| 766 |
static fuzzer_stem *fuzzerMergeStems(fuzzer_stem *pA, fuzzer_stem *pB){ |
| 767 |
fuzzer_stem head; |
| 768 |
fuzzer_stem *pTail; |
| 769 |
|
| 770 |
pTail = &head; |
| 771 |
while( pA && pB ){ |
| 772 |
if( pA->rCostX<=pB->rCostX ){ |
| 773 |
pTail->pNext = pA; |
| 774 |
pTail = pA; |
| 775 |
pA = pA->pNext; |
| 776 |
}else{ |
| 777 |
pTail->pNext = pB; |
| 778 |
pTail = pB; |
| 779 |
pB = pB->pNext; |
| 780 |
} |
| 781 |
} |
| 782 |
if( pA==0 ){ |
| 783 |
pTail->pNext = pB; |
| 784 |
}else{ |
| 785 |
pTail->pNext = pA; |
| 786 |
} |
| 787 |
return head.pNext; |
| 788 |
} |
| 789 |
|
| 790 |
/* |
| 791 |
** Load pCur->pStem with the lowest-cost stem. Return a pointer |
| 792 |
** to the lowest-cost stem. |
| 793 |
*/ |
| 794 |
static fuzzer_stem *fuzzerLowestCostStem(fuzzer_cursor *pCur){ |
| 795 |
fuzzer_stem *pBest, *pX; |
| 796 |
int iBest; |
| 797 |
int i; |
| 798 |
|
| 799 |
if( pCur->pStem==0 ){ |
| 800 |
iBest = -1; |
| 801 |
pBest = 0; |
| 802 |
for(i=0; i<=pCur->mxQueue; i++){ |
| 803 |
pX = pCur->aQueue[i]; |
| 804 |
if( pX==0 ) continue; |
| 805 |
if( pBest==0 || pBest->rCostX>pX->rCostX ){ |
| 806 |
pBest = pX; |
| 807 |
iBest = i; |
| 808 |
} |
| 809 |
} |
| 810 |
if( pBest ){ |
| 811 |
pCur->aQueue[iBest] = pBest->pNext; |
| 812 |
pBest->pNext = 0; |
| 813 |
pCur->pStem = pBest; |
| 814 |
} |
| 815 |
} |
| 816 |
return pCur->pStem; |
| 817 |
} |
| 818 |
|
| 819 |
/* |
| 820 |
** Insert pNew into queue of pending stems. Then find the stem |
| 821 |
** with the lowest rCostX and move it into pCur->pStem. |
| 822 |
** list. The insert is done such the pNew is in the correct order |
| 823 |
** according to fuzzer_stem.zBaseCost+fuzzer_stem.pRule->rCost. |
| 824 |
*/ |
| 825 |
static fuzzer_stem *fuzzerInsert(fuzzer_cursor *pCur, fuzzer_stem *pNew){ |
| 826 |
fuzzer_stem *pX; |
| 827 |
int i; |
| 828 |
|
| 829 |
/* If pCur->pStem exists and is greater than pNew, then make pNew |
| 830 |
** the new pCur->pStem and insert the old pCur->pStem instead. |
| 831 |
*/ |
| 832 |
if( (pX = pCur->pStem)!=0 && pX->rCostX>pNew->rCostX ){ |
| 833 |
pNew->pNext = 0; |
| 834 |
pCur->pStem = pNew; |
| 835 |
pNew = pX; |
| 836 |
} |
| 837 |
|
| 838 |
/* Insert the new value */ |
| 839 |
pNew->pNext = 0; |
| 840 |
pX = pNew; |
| 841 |
for(i=0; i<=pCur->mxQueue; i++){ |
| 842 |
if( pCur->aQueue[i] ){ |
| 843 |
pX = fuzzerMergeStems(pX, pCur->aQueue[i]); |
| 844 |
pCur->aQueue[i] = 0; |
| 845 |
}else{ |
| 846 |
pCur->aQueue[i] = pX; |
| 847 |
break; |
| 848 |
} |
| 849 |
} |
| 850 |
if( i>pCur->mxQueue ){ |
| 851 |
if( i<FUZZER_NQUEUE ){ |
| 852 |
pCur->mxQueue = i; |
| 853 |
pCur->aQueue[i] = pX; |
| 854 |
}else{ |
| 855 |
assert( pCur->mxQueue==FUZZER_NQUEUE-1 ); |
| 856 |
pX = fuzzerMergeStems(pX, pCur->aQueue[FUZZER_NQUEUE-1]); |
| 857 |
pCur->aQueue[FUZZER_NQUEUE-1] = pX; |
| 858 |
} |
| 859 |
} |
| 860 |
|
| 861 |
return fuzzerLowestCostStem(pCur); |
| 862 |
} |
| 863 |
|
| 864 |
/* |
| 865 |
** Allocate a new fuzzer_stem. Add it to the hash table but do not |
| 866 |
** link it into either the pCur->pStem or pCur->pDone lists. |
| 867 |
*/ |
| 868 |
static fuzzer_stem *fuzzerNewStem( |
| 869 |
fuzzer_cursor *pCur, |
| 870 |
const char *zWord, |
| 871 |
fuzzer_cost rBaseCost |
| 872 |
){ |
| 873 |
fuzzer_stem *pNew; |
| 874 |
fuzzer_rule *pRule; |
| 875 |
unsigned int h; |
| 876 |
|
| 877 |
pNew = sqlite3_malloc64( sizeof(*pNew) + strlen(zWord) + 1 ); |
| 878 |
if( pNew==0 ) return 0; |
| 879 |
memset(pNew, 0, sizeof(*pNew)); |
| 880 |
pNew->zBasis = (char*)&pNew[1]; |
| 881 |
pNew->nBasis = (fuzzer_len)strlen(zWord); |
| 882 |
memcpy(pNew->zBasis, zWord, pNew->nBasis+1); |
| 883 |
pRule = pCur->pVtab->pRule; |
| 884 |
while( fuzzerSkipRule(pRule, pNew, pCur->iRuleset) ){ |
| 885 |
pRule = pRule->pNext; |
| 886 |
} |
| 887 |
pNew->pRule = pRule; |
| 888 |
pNew->n = -1; |
| 889 |
pNew->rBaseCost = pNew->rCostX = rBaseCost; |
| 890 |
h = fuzzerHash(pNew->zBasis); |
| 891 |
pNew->pHash = pCur->apHash[h]; |
| 892 |
pCur->apHash[h] = pNew; |
| 893 |
pCur->nStem++; |
| 894 |
return pNew; |
| 895 |
} |
| 896 |
|
| 897 |
|
| 898 |
/* |
| 899 |
** Advance a cursor to its next row of output |
| 900 |
*/ |
| 901 |
static int fuzzerNext(sqlite3_vtab_cursor *cur){ |
| 902 |
fuzzer_cursor *pCur = (fuzzer_cursor*)cur; |
| 903 |
int rc; |
| 904 |
fuzzer_stem *pStem, *pNew; |
| 905 |
|
| 906 |
pCur->iRowid++; |
| 907 |
|
| 908 |
/* Use the element the cursor is currently point to to create |
| 909 |
** a new stem and insert the new stem into the priority queue. |
| 910 |
*/ |
| 911 |
pStem = pCur->pStem; |
| 912 |
if( pStem->rCostX>0 ){ |
| 913 |
rc = fuzzerRender(pStem, &pCur->zBuf, &pCur->nBuf); |
| 914 |
if( rc==SQLITE_NOMEM ) return SQLITE_NOMEM; |
| 915 |
pNew = fuzzerNewStem(pCur, pCur->zBuf, pStem->rCostX); |
| 916 |
if( pNew ){ |
| 917 |
if( fuzzerAdvance(pCur, pNew)==0 ){ |
| 918 |
pNew->pNext = pCur->pDone; |
| 919 |
pCur->pDone = pNew; |
| 920 |
}else{ |
| 921 |
if( fuzzerInsert(pCur, pNew)==pNew ){ |
| 922 |
return SQLITE_OK; |
| 923 |
} |
| 924 |
} |
| 925 |
}else{ |
| 926 |
return SQLITE_NOMEM; |
| 927 |
} |
| 928 |
} |
| 929 |
|
| 930 |
/* Adjust the priority queue so that the first element of the |
| 931 |
** stem list is the next lowest cost word. |
| 932 |
*/ |
| 933 |
while( (pStem = pCur->pStem)!=0 ){ |
| 934 |
int res = fuzzerAdvance(pCur, pStem); |
| 935 |
if( res<0 ){ |
| 936 |
return SQLITE_NOMEM; |
| 937 |
}else if( res>0 ){ |
| 938 |
pCur->pStem = 0; |
| 939 |
pStem = fuzzerInsert(pCur, pStem); |
| 940 |
if( (rc = fuzzerSeen(pCur, pStem))!=0 ){ |
| 941 |
if( rc<0 ) return SQLITE_NOMEM; |
| 942 |
continue; |
| 943 |
} |
| 944 |
return SQLITE_OK; /* New word found */ |
| 945 |
} |
| 946 |
pCur->pStem = 0; |
| 947 |
pStem->pNext = pCur->pDone; |
| 948 |
pCur->pDone = pStem; |
| 949 |
if( fuzzerLowestCostStem(pCur) ){ |
| 950 |
rc = fuzzerSeen(pCur, pCur->pStem); |
| 951 |
if( rc<0 ) return SQLITE_NOMEM; |
| 952 |
if( rc==0 ){ |
| 953 |
return SQLITE_OK; |
| 954 |
} |
| 955 |
} |
| 956 |
} |
| 957 |
|
| 958 |
/* Reach this point only if queue has been exhausted and there is |
| 959 |
** nothing left to be output. */ |
| 960 |
pCur->rLimit = (fuzzer_cost)0; |
| 961 |
return SQLITE_OK; |
| 962 |
} |
| 963 |
|
| 964 |
/* |
| 965 |
** Called to "rewind" a cursor back to the beginning so that |
| 966 |
** it starts its output over again. Always called at least once |
| 967 |
** prior to any fuzzerColumn, fuzzerRowid, or fuzzerEof call. |
| 968 |
*/ |
| 969 |
static int fuzzerFilter( |
| 970 |
sqlite3_vtab_cursor *pVtabCursor, |
| 971 |
int idxNum, const char *idxStr, |
| 972 |
int argc, sqlite3_value **argv |
| 973 |
){ |
| 974 |
fuzzer_cursor *pCur = (fuzzer_cursor *)pVtabCursor; |
| 975 |
const char *zWord = ""; |
| 976 |
fuzzer_stem *pStem; |
| 977 |
int idx; |
| 978 |
|
| 979 |
fuzzerClearCursor(pCur, 1); |
| 980 |
pCur->rLimit = 2147483647; |
| 981 |
idx = 0; |
| 982 |
if( idxNum & 1 ){ |
| 983 |
zWord = (const char*)sqlite3_value_text(argv[0]); |
| 984 |
idx++; |
| 985 |
} |
| 986 |
if( idxNum & 2 ){ |
| 987 |
pCur->rLimit = (fuzzer_cost)sqlite3_value_int(argv[idx]); |
| 988 |
idx++; |
| 989 |
} |
| 990 |
if( idxNum & 4 ){ |
| 991 |
pCur->iRuleset = (fuzzer_cost)sqlite3_value_int(argv[idx]); |
| 992 |
idx++; |
| 993 |
} |
| 994 |
pCur->nullRule.pNext = pCur->pVtab->pRule; |
| 995 |
pCur->nullRule.rCost = 0; |
| 996 |
pCur->nullRule.nFrom = 0; |
| 997 |
pCur->nullRule.nTo = 0; |
| 998 |
pCur->nullRule.zFrom = ""; |
| 999 |
pCur->iRowid = 1; |
| 1000 |
assert( pCur->pStem==0 ); |
| 1001 |
|
| 1002 |
/* If the query term is longer than FUZZER_MX_OUTPUT_LENGTH bytes, this |
| 1003 |
** query will return zero rows. */ |
| 1004 |
if( (int)strlen(zWord)<FUZZER_MX_OUTPUT_LENGTH ){ |
| 1005 |
pCur->pStem = pStem = fuzzerNewStem(pCur, zWord, (fuzzer_cost)0); |
| 1006 |
if( pStem==0 ) return SQLITE_NOMEM; |
| 1007 |
pStem->pRule = &pCur->nullRule; |
| 1008 |
pStem->n = pStem->nBasis; |
| 1009 |
}else{ |
| 1010 |
pCur->rLimit = 0; |
| 1011 |
} |
| 1012 |
|
| 1013 |
return SQLITE_OK; |
| 1014 |
} |
| 1015 |
|
| 1016 |
/* |
| 1017 |
** Only the word and distance columns have values. All other columns |
| 1018 |
** return NULL |
| 1019 |
*/ |
| 1020 |
static int fuzzerColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){ |
| 1021 |
fuzzer_cursor *pCur = (fuzzer_cursor*)cur; |
| 1022 |
if( i==0 ){ |
| 1023 |
/* the "word" column */ |
| 1024 |
if( fuzzerRender(pCur->pStem, &pCur->zBuf, &pCur->nBuf)==SQLITE_NOMEM ){ |
| 1025 |
return SQLITE_NOMEM; |
| 1026 |
} |
| 1027 |
sqlite3_result_text(ctx, pCur->zBuf, -1, SQLITE_TRANSIENT); |
| 1028 |
}else if( i==1 ){ |
| 1029 |
/* the "distance" column */ |
| 1030 |
sqlite3_result_int(ctx, pCur->pStem->rCostX); |
| 1031 |
}else{ |
| 1032 |
/* All other columns are NULL */ |
| 1033 |
sqlite3_result_null(ctx); |
| 1034 |
} |
| 1035 |
return SQLITE_OK; |
| 1036 |
} |
| 1037 |
|
| 1038 |
/* |
| 1039 |
** The rowid. |
| 1040 |
*/ |
| 1041 |
static int fuzzerRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){ |
| 1042 |
fuzzer_cursor *pCur = (fuzzer_cursor*)cur; |
| 1043 |
*pRowid = pCur->iRowid; |
| 1044 |
return SQLITE_OK; |
| 1045 |
} |
| 1046 |
|
| 1047 |
/* |
| 1048 |
** When the fuzzer_cursor.rLimit value is 0 or less, that is a signal |
| 1049 |
** that the cursor has nothing more to output. |
| 1050 |
*/ |
| 1051 |
static int fuzzerEof(sqlite3_vtab_cursor *cur){ |
| 1052 |
fuzzer_cursor *pCur = (fuzzer_cursor*)cur; |
| 1053 |
return pCur->rLimit<=(fuzzer_cost)0; |
| 1054 |
} |
| 1055 |
|
| 1056 |
/* |
| 1057 |
** Search for terms of these forms: |
| 1058 |
** |
| 1059 |
** (A) word MATCH $str |
| 1060 |
** (B1) distance < $value |
| 1061 |
** (B2) distance <= $value |
| 1062 |
** (C) ruleid == $ruleid |
| 1063 |
** |
| 1064 |
** The distance< and distance<= are both treated as distance<=. |
| 1065 |
** The query plan number is a bit vector: |
| 1066 |
** |
| 1067 |
** bit 1: Term of the form (A) found |
| 1068 |
** bit 2: Term like (B1) or (B2) found |
| 1069 |
** bit 3: Term like (C) found |
| 1070 |
** |
| 1071 |
** If bit-1 is set, $str is always in filter.argv[0]. If bit-2 is set |
| 1072 |
** then $value is in filter.argv[0] if bit-1 is clear and is in |
| 1073 |
** filter.argv[1] if bit-1 is set. If bit-3 is set, then $ruleid is |
| 1074 |
** in filter.argv[0] if bit-1 and bit-2 are both zero, is in |
| 1075 |
** filter.argv[1] if exactly one of bit-1 and bit-2 are set, and is in |
| 1076 |
** filter.argv[2] if both bit-1 and bit-2 are set. |
| 1077 |
*/ |
| 1078 |
static int fuzzerBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){ |
| 1079 |
int iPlan = 0; |
| 1080 |
int iDistTerm = -1; |
| 1081 |
int iRulesetTerm = -1; |
| 1082 |
int i; |
| 1083 |
int seenMatch = 0; |
| 1084 |
const struct sqlite3_index_constraint *pConstraint; |
| 1085 |
double rCost = 1e12; |
| 1086 |
|
| 1087 |
pConstraint = pIdxInfo->aConstraint; |
| 1088 |
for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){ |
| 1089 |
if( pConstraint->iColumn==0 |
| 1090 |
&& pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH ){ |
| 1091 |
seenMatch = 1; |
| 1092 |
} |
| 1093 |
if( pConstraint->usable==0 ) continue; |
| 1094 |
if( (iPlan & 1)==0 |
| 1095 |
&& pConstraint->iColumn==0 |
| 1096 |
&& pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH |
| 1097 |
){ |
| 1098 |
iPlan |= 1; |
| 1099 |
pIdxInfo->aConstraintUsage[i].argvIndex = 1; |
| 1100 |
pIdxInfo->aConstraintUsage[i].omit = 1; |
| 1101 |
rCost /= 1e6; |
| 1102 |
} |
| 1103 |
if( (iPlan & 2)==0 |
| 1104 |
&& pConstraint->iColumn==1 |
| 1105 |
&& (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT |
| 1106 |
|| pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE) |
| 1107 |
){ |
| 1108 |
iPlan |= 2; |
| 1109 |
iDistTerm = i; |
| 1110 |
rCost /= 10.0; |
| 1111 |
} |
| 1112 |
if( (iPlan & 4)==0 |
| 1113 |
&& pConstraint->iColumn==2 |
| 1114 |
&& pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ |
| 1115 |
){ |
| 1116 |
iPlan |= 4; |
| 1117 |
pIdxInfo->aConstraintUsage[i].omit = 1; |
| 1118 |
iRulesetTerm = i; |
| 1119 |
rCost /= 10.0; |
| 1120 |
} |
| 1121 |
} |
| 1122 |
if( iPlan & 2 ){ |
| 1123 |
pIdxInfo->aConstraintUsage[iDistTerm].argvIndex = 1+((iPlan&1)!=0); |
| 1124 |
} |
| 1125 |
if( iPlan & 4 ){ |
| 1126 |
int idx = 1; |
| 1127 |
if( iPlan & 1 ) idx++; |
| 1128 |
if( iPlan & 2 ) idx++; |
| 1129 |
pIdxInfo->aConstraintUsage[iRulesetTerm].argvIndex = idx; |
| 1130 |
} |
| 1131 |
pIdxInfo->idxNum = iPlan; |
| 1132 |
if( pIdxInfo->nOrderBy==1 |
| 1133 |
&& pIdxInfo->aOrderBy[0].iColumn==1 |
| 1134 |
&& pIdxInfo->aOrderBy[0].desc==0 |
| 1135 |
){ |
| 1136 |
pIdxInfo->orderByConsumed = 1; |
| 1137 |
} |
| 1138 |
if( seenMatch && (iPlan&1)==0 ) rCost = 1e99; |
| 1139 |
pIdxInfo->estimatedCost = rCost; |
| 1140 |
|
| 1141 |
return SQLITE_OK; |
| 1142 |
} |
| 1143 |
|
| 1144 |
/* |
| 1145 |
** A virtual table module that implements the "fuzzer". |
| 1146 |
*/ |
| 1147 |
static sqlite3_module fuzzerModule = { |
| 1148 |
0, /* iVersion */ |
| 1149 |
fuzzerConnect, |
| 1150 |
fuzzerConnect, |
| 1151 |
fuzzerBestIndex, |
| 1152 |
fuzzerDisconnect, |
| 1153 |
fuzzerDisconnect, |
| 1154 |
fuzzerOpen, /* xOpen - open a cursor */ |
| 1155 |
fuzzerClose, /* xClose - close a cursor */ |
| 1156 |
fuzzerFilter, /* xFilter - configure scan constraints */ |
| 1157 |
fuzzerNext, /* xNext - advance a cursor */ |
| 1158 |
fuzzerEof, /* xEof - check for end of scan */ |
| 1159 |
fuzzerColumn, /* xColumn - read data */ |
| 1160 |
fuzzerRowid, /* xRowid - read data */ |
| 1161 |
0, /* xUpdate */ |
| 1162 |
0, /* xBegin */ |
| 1163 |
0, /* xSync */ |
| 1164 |
0, /* xCommit */ |
| 1165 |
0, /* xRollback */ |
| 1166 |
0, /* xFindMethod */ |
| 1167 |
0, /* xRename */ |
| 1168 |
0, /* xSavepoint */ |
| 1169 |
0, /* xRelease */ |
| 1170 |
0, /* xRollbackTo */ |
| 1171 |
0, /* xShadowName */ |
| 1172 |
0 /* xIntegrity */ |
| 1173 |
}; |
| 1174 |
|
| 1175 |
#endif /* SQLITE_OMIT_VIRTUALTABLE */ |
| 1176 |
|
| 1177 |
|
| 1178 |
#ifdef _WIN32 |
| 1179 |
__declspec(dllexport) |
| 1180 |
#endif |
| 1181 |
int sqlite3_fuzzer_init( |
| 1182 |
sqlite3 *db, |
| 1183 |
char **pzErrMsg, |
| 1184 |
const sqlite3_api_routines *pApi |
| 1185 |
){ |
| 1186 |
int rc = SQLITE_OK; |
| 1187 |
SQLITE_EXTENSION_INIT2(pApi); |
| 1188 |
#ifndef SQLITE_OMIT_VIRTUALTABLE |
| 1189 |
rc = sqlite3_create_module(db, "fuzzer", &fuzzerModule, 0); |
| 1190 |
#endif |
| 1191 |
return rc; |
| 1192 |
} |