| OLD | NEW |
|---|
| (Empty) |
| 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 appling 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 vocubulary.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 kepts 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_malloc( 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 = nFrom; | |
| 348 memcpy(pRule->zFrom, zFrom, nFrom+1); | |
| 349 memcpy(pRule->zTo, zTo, nTo+1); | |
| 350 pRule->nTo = 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 int nIn; /* Size of input string, in bytes */ | |
| 451 char *zOut; /* Output (dequoted) string */ | |
| 452 | |
| 453 nIn = (int)strlen(zIn); | |
| 454 zOut = sqlite3_malloc(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, 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 int nModule; /* Length of zModule, in bytes */ | |
| 517 | |
| 518 nModule = (int)strlen(zModule); | |
| 519 pNew = sqlite3_malloc( 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, 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 } | |
| 544 } | |
| 545 } | |
| 546 | |
| 547 *ppVtab = (sqlite3_vtab *)pNew; | |
| 548 return rc; | |
| 549 } | |
| 550 | |
| 551 /* | |
| 552 ** Open a new fuzzer cursor. | |
| 553 */ | |
| 554 static int fuzzerOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){ | |
| 555 fuzzer_vtab *p = (fuzzer_vtab*)pVTab; | |
| 556 fuzzer_cursor *pCur; | |
| 557 pCur = sqlite3_malloc( sizeof(*pCur) ); | |
| 558 if( pCur==0 ) return SQLITE_NOMEM; | |
| 559 memset(pCur, 0, sizeof(*pCur)); | |
| 560 pCur->pVtab = p; | |
| 561 *ppCursor = &pCur->base; | |
| 562 p->nCursor++; | |
| 563 return SQLITE_OK; | |
| 564 } | |
| 565 | |
| 566 /* | |
| 567 ** Free all stems in a list. | |
| 568 */ | |
| 569 static void fuzzerClearStemList(fuzzer_stem *pStem){ | |
| 570 while( pStem ){ | |
| 571 fuzzer_stem *pNext = pStem->pNext; | |
| 572 sqlite3_free(pStem); | |
| 573 pStem = pNext; | |
| 574 } | |
| 575 } | |
| 576 | |
| 577 /* | |
| 578 ** Free up all the memory allocated by a cursor. Set it rLimit to 0 | |
| 579 ** to indicate that it is at EOF. | |
| 580 */ | |
| 581 static void fuzzerClearCursor(fuzzer_cursor *pCur, int clearHash){ | |
| 582 int i; | |
| 583 fuzzerClearStemList(pCur->pStem); | |
| 584 fuzzerClearStemList(pCur->pDone); | |
| 585 for(i=0; i<FUZZER_NQUEUE; i++) fuzzerClearStemList(pCur->aQueue[i]); | |
| 586 pCur->rLimit = (fuzzer_cost)0; | |
| 587 if( clearHash && pCur->nStem ){ | |
| 588 pCur->mxQueue = 0; | |
| 589 pCur->pStem = 0; | |
| 590 pCur->pDone = 0; | |
| 591 memset(pCur->aQueue, 0, sizeof(pCur->aQueue)); | |
| 592 memset(pCur->apHash, 0, sizeof(pCur->apHash)); | |
| 593 } | |
| 594 pCur->nStem = 0; | |
| 595 } | |
| 596 | |
| 597 /* | |
| 598 ** Close a fuzzer cursor. | |
| 599 */ | |
| 600 static int fuzzerClose(sqlite3_vtab_cursor *cur){ | |
| 601 fuzzer_cursor *pCur = (fuzzer_cursor *)cur; | |
| 602 fuzzerClearCursor(pCur, 0); | |
| 603 sqlite3_free(pCur->zBuf); | |
| 604 pCur->pVtab->nCursor--; | |
| 605 sqlite3_free(pCur); | |
| 606 return SQLITE_OK; | |
| 607 } | |
| 608 | |
| 609 /* | |
| 610 ** Compute the current output term for a fuzzer_stem. | |
| 611 */ | |
| 612 static int fuzzerRender( | |
| 613 fuzzer_stem *pStem, /* The stem to be rendered */ | |
| 614 char **pzBuf, /* Write results into this buffer. realloc if needed */ | |
| 615 int *pnBuf /* Size of the buffer */ | |
| 616 ){ | |
| 617 const fuzzer_rule *pRule = pStem->pRule; | |
| 618 int n; /* Size of output term without nul-term */ | |
| 619 char *z; /* Buffer to assemble output term in */ | |
| 620 | |
| 621 n = pStem->nBasis + pRule->nTo - pRule->nFrom; | |
| 622 if( (*pnBuf)<n+1 ){ | |
| 623 (*pzBuf) = sqlite3_realloc((*pzBuf), n+100); | |
| 624 if( (*pzBuf)==0 ) return SQLITE_NOMEM; | |
| 625 (*pnBuf) = n+100; | |
| 626 } | |
| 627 n = pStem->n; | |
| 628 z = *pzBuf; | |
| 629 if( n<0 ){ | |
| 630 memcpy(z, pStem->zBasis, pStem->nBasis+1); | |
| 631 }else{ | |
| 632 memcpy(z, pStem->zBasis, n); | |
| 633 memcpy(&z[n], pRule->zTo, pRule->nTo); | |
| 634 memcpy(&z[n+pRule->nTo], &pStem->zBasis[n+pRule->nFrom], | |
| 635 pStem->nBasis-n-pRule->nFrom+1); | |
| 636 } | |
| 637 | |
| 638 assert( z[pStem->nBasis + pRule->nTo - pRule->nFrom]==0 ); | |
| 639 return SQLITE_OK; | |
| 640 } | |
| 641 | |
| 642 /* | |
| 643 ** Compute a hash on zBasis. | |
| 644 */ | |
| 645 static unsigned int fuzzerHash(const char *z){ | |
| 646 unsigned int h = 0; | |
| 647 while( *z ){ h = (h<<3) ^ (h>>29) ^ *(z++); } | |
| 648 return h % FUZZER_HASH; | |
| 649 } | |
| 650 | |
| 651 /* | |
| 652 ** Current cost of a stem | |
| 653 */ | |
| 654 static fuzzer_cost fuzzerCost(fuzzer_stem *pStem){ | |
| 655 return pStem->rCostX = pStem->rBaseCost + pStem->pRule->rCost; | |
| 656 } | |
| 657 | |
| 658 #if 0 | |
| 659 /* | |
| 660 ** Print a description of a fuzzer_stem on stderr. | |
| 661 */ | |
| 662 static void fuzzerStemPrint( | |
| 663 const char *zPrefix, | |
| 664 fuzzer_stem *pStem, | |
| 665 const char *zSuffix | |
| 666 ){ | |
| 667 if( pStem->n<0 ){ | |
| 668 fprintf(stderr, "%s[%s](%d)-->self%s", | |
| 669 zPrefix, | |
| 670 pStem->zBasis, pStem->rBaseCost, | |
| 671 zSuffix | |
| 672 ); | |
| 673 }else{ | |
| 674 char *zBuf = 0; | |
| 675 int nBuf = 0; | |
| 676 if( fuzzerRender(pStem, &zBuf, &nBuf)!=SQLITE_OK ) return; | |
| 677 fprintf(stderr, "%s[%s](%d)-->{%s}(%d)%s", | |
| 678 zPrefix, | |
| 679 pStem->zBasis, pStem->rBaseCost, zBuf, pStem->, | |
| 680 zSuffix | |
| 681 ); | |
| 682 sqlite3_free(zBuf); | |
| 683 } | |
| 684 } | |
| 685 #endif | |
| 686 | |
| 687 /* | |
| 688 ** Return 1 if the string to which the cursor is point has already | |
| 689 ** been emitted. Return 0 if not. Return -1 on a memory allocation | |
| 690 ** failures. | |
| 691 */ | |
| 692 static int fuzzerSeen(fuzzer_cursor *pCur, fuzzer_stem *pStem){ | |
| 693 unsigned int h; | |
| 694 fuzzer_stem *pLookup; | |
| 695 | |
| 696 if( fuzzerRender(pStem, &pCur->zBuf, &pCur->nBuf)==SQLITE_NOMEM ){ | |
| 697 return -1; | |
| 698 } | |
| 699 h = fuzzerHash(pCur->zBuf); | |
| 700 pLookup = pCur->apHash[h]; | |
| 701 while( pLookup && strcmp(pLookup->zBasis, pCur->zBuf)!=0 ){ | |
| 702 pLookup = pLookup->pHash; | |
| 703 } | |
| 704 return pLookup!=0; | |
| 705 } | |
| 706 | |
| 707 /* | |
| 708 ** If argument pRule is NULL, this function returns false. | |
| 709 ** | |
| 710 ** Otherwise, it returns true if rule pRule should be skipped. A rule | |
| 711 ** should be skipped if it does not belong to rule-set iRuleset, or if | |
| 712 ** applying it to stem pStem would create a string longer than | |
| 713 ** FUZZER_MX_OUTPUT_LENGTH bytes. | |
| 714 */ | |
| 715 static int fuzzerSkipRule( | |
| 716 const fuzzer_rule *pRule, /* Determine whether or not to skip this */ | |
| 717 fuzzer_stem *pStem, /* Stem rule may be applied to */ | |
| 718 int iRuleset /* Rule-set used by the current query */ | |
| 719 ){ | |
| 720 return pRule && ( | |
| 721 (pRule->iRuleset!=iRuleset) | |
| 722 || (pStem->nBasis + pRule->nTo - pRule->nFrom)>FUZZER_MX_OUTPUT_LENGTH | |
| 723 ); | |
| 724 } | |
| 725 | |
| 726 /* | |
| 727 ** Advance a fuzzer_stem to its next value. Return 0 if there are | |
| 728 ** no more values that can be generated by this fuzzer_stem. Return | |
| 729 ** -1 on a memory allocation failure. | |
| 730 */ | |
| 731 static int fuzzerAdvance(fuzzer_cursor *pCur, fuzzer_stem *pStem){ | |
| 732 const fuzzer_rule *pRule; | |
| 733 while( (pRule = pStem->pRule)!=0 ){ | |
| 734 assert( pRule==&pCur->nullRule || pRule->iRuleset==pCur->iRuleset ); | |
| 735 while( pStem->n < pStem->nBasis - pRule->nFrom ){ | |
| 736 pStem->n++; | |
| 737 if( pRule->nFrom==0 | |
| 738 || memcmp(&pStem->zBasis[pStem->n], pRule->zFrom, pRule->nFrom)==0 | |
| 739 ){ | |
| 740 /* Found a rewrite case. Make sure it is not a duplicate */ | |
| 741 int rc = fuzzerSeen(pCur, pStem); | |
| 742 if( rc<0 ) return -1; | |
| 743 if( rc==0 ){ | |
| 744 fuzzerCost(pStem); | |
| 745 return 1; | |
| 746 } | |
| 747 } | |
| 748 } | |
| 749 pStem->n = -1; | |
| 750 do{ | |
| 751 pRule = pRule->pNext; | |
| 752 }while( fuzzerSkipRule(pRule, pStem, pCur->iRuleset) ); | |
| 753 pStem->pRule = pRule; | |
| 754 if( pRule && fuzzerCost(pStem)>pCur->rLimit ) pStem->pRule = 0; | |
| 755 } | |
| 756 return 0; | |
| 757 } | |
| 758 | |
| 759 /* | |
| 760 ** The two input stem lists are both sorted in order of increasing | |
| 761 ** rCostX. Merge them together into a single list, sorted by rCostX, and | |
| 762 ** return a pointer to the head of that new list. | |
| 763 */ | |
| 764 static fuzzer_stem *fuzzerMergeStems(fuzzer_stem *pA, fuzzer_stem *pB){ | |
| 765 fuzzer_stem head; | |
| 766 fuzzer_stem *pTail; | |
| 767 | |
| 768 pTail = &head; | |
| 769 while( pA && pB ){ | |
| 770 if( pA->rCostX<=pB->rCostX ){ | |
| 771 pTail->pNext = pA; | |
| 772 pTail = pA; | |
| 773 pA = pA->pNext; | |
| 774 }else{ | |
| 775 pTail->pNext = pB; | |
| 776 pTail = pB; | |
| 777 pB = pB->pNext; | |
| 778 } | |
| 779 } | |
| 780 if( pA==0 ){ | |
| 781 pTail->pNext = pB; | |
| 782 }else{ | |
| 783 pTail->pNext = pA; | |
| 784 } | |
| 785 return head.pNext; | |
| 786 } | |
| 787 | |
| 788 /* | |
| 789 ** Load pCur->pStem with the lowest-cost stem. Return a pointer | |
| 790 ** to the lowest-cost stem. | |
| 791 */ | |
| 792 static fuzzer_stem *fuzzerLowestCostStem(fuzzer_cursor *pCur){ | |
| 793 fuzzer_stem *pBest, *pX; | |
| 794 int iBest; | |
| 795 int i; | |
| 796 | |
| 797 if( pCur->pStem==0 ){ | |
| 798 iBest = -1; | |
| 799 pBest = 0; | |
| 800 for(i=0; i<=pCur->mxQueue; i++){ | |
| 801 pX = pCur->aQueue[i]; | |
| 802 if( pX==0 ) continue; | |
| 803 if( pBest==0 || pBest->rCostX>pX->rCostX ){ | |
| 804 pBest = pX; | |
| 805 iBest = i; | |
| 806 } | |
| 807 } | |
| 808 if( pBest ){ | |
| 809 pCur->aQueue[iBest] = pBest->pNext; | |
| 810 pBest->pNext = 0; | |
| 811 pCur->pStem = pBest; | |
| 812 } | |
| 813 } | |
| 814 return pCur->pStem; | |
| 815 } | |
| 816 | |
| 817 /* | |
| 818 ** Insert pNew into queue of pending stems. Then find the stem | |
| 819 ** with the lowest rCostX and move it into pCur->pStem. | |
| 820 ** list. The insert is done such the pNew is in the correct order | |
| 821 ** according to fuzzer_stem.zBaseCost+fuzzer_stem.pRule->rCost. | |
| 822 */ | |
| 823 static fuzzer_stem *fuzzerInsert(fuzzer_cursor *pCur, fuzzer_stem *pNew){ | |
| 824 fuzzer_stem *pX; | |
| 825 int i; | |
| 826 | |
| 827 /* If pCur->pStem exists and is greater than pNew, then make pNew | |
| 828 ** the new pCur->pStem and insert the old pCur->pStem instead. | |
| 829 */ | |
| 830 if( (pX = pCur->pStem)!=0 && pX->rCostX>pNew->rCostX ){ | |
| 831 pNew->pNext = 0; | |
| 832 pCur->pStem = pNew; | |
| 833 pNew = pX; | |
| 834 } | |
| 835 | |
| 836 /* Insert the new value */ | |
| 837 pNew->pNext = 0; | |
| 838 pX = pNew; | |
| 839 for(i=0; i<=pCur->mxQueue; i++){ | |
| 840 if( pCur->aQueue[i] ){ | |
| 841 pX = fuzzerMergeStems(pX, pCur->aQueue[i]); | |
| 842 pCur->aQueue[i] = 0; | |
| 843 }else{ | |
| 844 pCur->aQueue[i] = pX; | |
| 845 break; | |
| 846 } | |
| 847 } | |
| 848 if( i>pCur->mxQueue ){ | |
| 849 if( i<FUZZER_NQUEUE ){ | |
| 850 pCur->mxQueue = i; | |
| 851 pCur->aQueue[i] = pX; | |
| 852 }else{ | |
| 853 assert( pCur->mxQueue==FUZZER_NQUEUE-1 ); | |
| 854 pX = fuzzerMergeStems(pX, pCur->aQueue[FUZZER_NQUEUE-1]); | |
| 855 pCur->aQueue[FUZZER_NQUEUE-1] = pX; | |
| 856 } | |
| 857 } | |
| 858 | |
| 859 return fuzzerLowestCostStem(pCur); | |
| 860 } | |
| 861 | |
| 862 /* | |
| 863 ** Allocate a new fuzzer_stem. Add it to the hash table but do not | |
| 864 ** link it into either the pCur->pStem or pCur->pDone lists. | |
| 865 */ | |
| 866 static fuzzer_stem *fuzzerNewStem( | |
| 867 fuzzer_cursor *pCur, | |
| 868 const char *zWord, | |
| 869 fuzzer_cost rBaseCost | |
| 870 ){ | |
| 871 fuzzer_stem *pNew; | |
| 872 fuzzer_rule *pRule; | |
| 873 unsigned int h; | |
| 874 | |
| 875 pNew = sqlite3_malloc( sizeof(*pNew) + (int)strlen(zWord) + 1 ); | |
| 876 if( pNew==0 ) return 0; | |
| 877 memset(pNew, 0, sizeof(*pNew)); | |
| 878 pNew->zBasis = (char*)&pNew[1]; | |
| 879 pNew->nBasis = (fuzzer_len)strlen(zWord); | |
| 880 memcpy(pNew->zBasis, zWord, pNew->nBasis+1); | |
| 881 pRule = pCur->pVtab->pRule; | |
| 882 while( fuzzerSkipRule(pRule, pNew, pCur->iRuleset) ){ | |
| 883 pRule = pRule->pNext; | |
| 884 } | |
| 885 pNew->pRule = pRule; | |
| 886 pNew->n = -1; | |
| 887 pNew->rBaseCost = pNew->rCostX = rBaseCost; | |
| 888 h = fuzzerHash(pNew->zBasis); | |
| 889 pNew->pHash = pCur->apHash[h]; | |
| 890 pCur->apHash[h] = pNew; | |
| 891 pCur->nStem++; | |
| 892 return pNew; | |
| 893 } | |
| 894 | |
| 895 | |
| 896 /* | |
| 897 ** Advance a cursor to its next row of output | |
| 898 */ | |
| 899 static int fuzzerNext(sqlite3_vtab_cursor *cur){ | |
| 900 fuzzer_cursor *pCur = (fuzzer_cursor*)cur; | |
| 901 int rc; | |
| 902 fuzzer_stem *pStem, *pNew; | |
| 903 | |
| 904 pCur->iRowid++; | |
| 905 | |
| 906 /* Use the element the cursor is currently point to to create | |
| 907 ** a new stem and insert the new stem into the priority queue. | |
| 908 */ | |
| 909 pStem = pCur->pStem; | |
| 910 if( pStem->rCostX>0 ){ | |
| 911 rc = fuzzerRender(pStem, &pCur->zBuf, &pCur->nBuf); | |
| 912 if( rc==SQLITE_NOMEM ) return SQLITE_NOMEM; | |
| 913 pNew = fuzzerNewStem(pCur, pCur->zBuf, pStem->rCostX); | |
| 914 if( pNew ){ | |
| 915 if( fuzzerAdvance(pCur, pNew)==0 ){ | |
| 916 pNew->pNext = pCur->pDone; | |
| 917 pCur->pDone = pNew; | |
| 918 }else{ | |
| 919 if( fuzzerInsert(pCur, pNew)==pNew ){ | |
| 920 return SQLITE_OK; | |
| 921 } | |
| 922 } | |
| 923 }else{ | |
| 924 return SQLITE_NOMEM; | |
| 925 } | |
| 926 } | |
| 927 | |
| 928 /* Adjust the priority queue so that the first element of the | |
| 929 ** stem list is the next lowest cost word. | |
| 930 */ | |
| 931 while( (pStem = pCur->pStem)!=0 ){ | |
| 932 int res = fuzzerAdvance(pCur, pStem); | |
| 933 if( res<0 ){ | |
| 934 return SQLITE_NOMEM; | |
| 935 }else if( res>0 ){ | |
| 936 pCur->pStem = 0; | |
| 937 pStem = fuzzerInsert(pCur, pStem); | |
| 938 if( (rc = fuzzerSeen(pCur, pStem))!=0 ){ | |
| 939 if( rc<0 ) return SQLITE_NOMEM; | |
| 940 continue; | |
| 941 } | |
| 942 return SQLITE_OK; /* New word found */ | |
| 943 } | |
| 944 pCur->pStem = 0; | |
| 945 pStem->pNext = pCur->pDone; | |
| 946 pCur->pDone = pStem; | |
| 947 if( fuzzerLowestCostStem(pCur) ){ | |
| 948 rc = fuzzerSeen(pCur, pCur->pStem); | |
| 949 if( rc<0 ) return SQLITE_NOMEM; | |
| 950 if( rc==0 ){ | |
| 951 return SQLITE_OK; | |
| 952 } | |
| 953 } | |
| 954 } | |
| 955 | |
| 956 /* Reach this point only if queue has been exhausted and there is | |
| 957 ** nothing left to be output. */ | |
| 958 pCur->rLimit = (fuzzer_cost)0; | |
| 959 return SQLITE_OK; | |
| 960 } | |
| 961 | |
| 962 /* | |
| 963 ** Called to "rewind" a cursor back to the beginning so that | |
| 964 ** it starts its output over again. Always called at least once | |
| 965 ** prior to any fuzzerColumn, fuzzerRowid, or fuzzerEof call. | |
| 966 */ | |
| 967 static int fuzzerFilter( | |
| 968 sqlite3_vtab_cursor *pVtabCursor, | |
| 969 int idxNum, const char *idxStr, | |
| 970 int argc, sqlite3_value **argv | |
| 971 ){ | |
| 972 fuzzer_cursor *pCur = (fuzzer_cursor *)pVtabCursor; | |
| 973 const char *zWord = ""; | |
| 974 fuzzer_stem *pStem; | |
| 975 int idx; | |
| 976 | |
| 977 fuzzerClearCursor(pCur, 1); | |
| 978 pCur->rLimit = 2147483647; | |
| 979 idx = 0; | |
| 980 if( idxNum & 1 ){ | |
| 981 zWord = (const char*)sqlite3_value_text(argv[0]); | |
| 982 idx++; | |
| 983 } | |
| 984 if( idxNum & 2 ){ | |
| 985 pCur->rLimit = (fuzzer_cost)sqlite3_value_int(argv[idx]); | |
| 986 idx++; | |
| 987 } | |
| 988 if( idxNum & 4 ){ | |
| 989 pCur->iRuleset = (fuzzer_cost)sqlite3_value_int(argv[idx]); | |
| 990 idx++; | |
| 991 } | |
| 992 pCur->nullRule.pNext = pCur->pVtab->pRule; | |
| 993 pCur->nullRule.rCost = 0; | |
| 994 pCur->nullRule.nFrom = 0; | |
| 995 pCur->nullRule.nTo = 0; | |
| 996 pCur->nullRule.zFrom = ""; | |
| 997 pCur->iRowid = 1; | |
| 998 assert( pCur->pStem==0 ); | |
| 999 | |
| 1000 /* If the query term is longer than FUZZER_MX_OUTPUT_LENGTH bytes, this | |
| 1001 ** query will return zero rows. */ | |
| 1002 if( (int)strlen(zWord)<FUZZER_MX_OUTPUT_LENGTH ){ | |
| 1003 pCur->pStem = pStem = fuzzerNewStem(pCur, zWord, (fuzzer_cost)0); | |
| 1004 if( pStem==0 ) return SQLITE_NOMEM; | |
| 1005 pStem->pRule = &pCur->nullRule; | |
| 1006 pStem->n = pStem->nBasis; | |
| 1007 }else{ | |
| 1008 pCur->rLimit = 0; | |
| 1009 } | |
| 1010 | |
| 1011 return SQLITE_OK; | |
| 1012 } | |
| 1013 | |
| 1014 /* | |
| 1015 ** Only the word and distance columns have values. All other columns | |
| 1016 ** return NULL | |
| 1017 */ | |
| 1018 static int fuzzerColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){ | |
| 1019 fuzzer_cursor *pCur = (fuzzer_cursor*)cur; | |
| 1020 if( i==0 ){ | |
| 1021 /* the "word" column */ | |
| 1022 if( fuzzerRender(pCur->pStem, &pCur->zBuf, &pCur->nBuf)==SQLITE_NOMEM ){ | |
| 1023 return SQLITE_NOMEM; | |
| 1024 } | |
| 1025 sqlite3_result_text(ctx, pCur->zBuf, -1, SQLITE_TRANSIENT); | |
| 1026 }else if( i==1 ){ | |
| 1027 /* the "distance" column */ | |
| 1028 sqlite3_result_int(ctx, pCur->pStem->rCostX); | |
| 1029 }else{ | |
| 1030 /* All other columns are NULL */ | |
| 1031 sqlite3_result_null(ctx); | |
| 1032 } | |
| 1033 return SQLITE_OK; | |
| 1034 } | |
| 1035 | |
| 1036 /* | |
| 1037 ** The rowid. | |
| 1038 */ | |
| 1039 static int fuzzerRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){ | |
| 1040 fuzzer_cursor *pCur = (fuzzer_cursor*)cur; | |
| 1041 *pRowid = pCur->iRowid; | |
| 1042 return SQLITE_OK; | |
| 1043 } | |
| 1044 | |
| 1045 /* | |
| 1046 ** When the fuzzer_cursor.rLimit value is 0 or less, that is a signal | |
| 1047 ** that the cursor has nothing more to output. | |
| 1048 */ | |
| 1049 static int fuzzerEof(sqlite3_vtab_cursor *cur){ | |
| 1050 fuzzer_cursor *pCur = (fuzzer_cursor*)cur; | |
| 1051 return pCur->rLimit<=(fuzzer_cost)0; | |
| 1052 } | |
| 1053 | |
| 1054 /* | |
| 1055 ** Search for terms of these forms: | |
| 1056 ** | |
| 1057 ** (A) word MATCH $str | |
| 1058 ** (B1) distance < $value | |
| 1059 ** (B2) distance <= $value | |
| 1060 ** (C) ruleid == $ruleid | |
| 1061 ** | |
| 1062 ** The distance< and distance<= are both treated as distance<=. | |
| 1063 ** The query plan number is a bit vector: | |
| 1064 ** | |
| 1065 ** bit 1: Term of the form (A) found | |
| 1066 ** bit 2: Term like (B1) or (B2) found | |
| 1067 ** bit 3: Term like (C) found | |
| 1068 ** | |
| 1069 ** If bit-1 is set, $str is always in filter.argv[0]. If bit-2 is set | |
| 1070 ** then $value is in filter.argv[0] if bit-1 is clear and is in | |
| 1071 ** filter.argv[1] if bit-1 is set. If bit-3 is set, then $ruleid is | |
| 1072 ** in filter.argv[0] if bit-1 and bit-2 are both zero, is in | |
| 1073 ** filter.argv[1] if exactly one of bit-1 and bit-2 are set, and is in | |
| 1074 ** filter.argv[2] if both bit-1 and bit-2 are set. | |
| 1075 */ | |
| 1076 static int fuzzerBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){ | |
| 1077 int iPlan = 0; | |
| 1078 int iDistTerm = -1; | |
| 1079 int iRulesetTerm = -1; | |
| 1080 int i; | |
| 1081 int seenMatch = 0; | |
| 1082 const struct sqlite3_index_constraint *pConstraint; | |
| 1083 double rCost = 1e12; | |
| 1084 | |
| 1085 pConstraint = pIdxInfo->aConstraint; | |
| 1086 for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){ | |
| 1087 if( pConstraint->iColumn==0 | |
| 1088 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH ){ | |
| 1089 seenMatch = 1; | |
| 1090 } | |
| 1091 if( pConstraint->usable==0 ) continue; | |
| 1092 if( (iPlan & 1)==0 | |
| 1093 && pConstraint->iColumn==0 | |
| 1094 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH | |
| 1095 ){ | |
| 1096 iPlan |= 1; | |
| 1097 pIdxInfo->aConstraintUsage[i].argvIndex = 1; | |
| 1098 pIdxInfo->aConstraintUsage[i].omit = 1; | |
| 1099 rCost /= 1e6; | |
| 1100 } | |
| 1101 if( (iPlan & 2)==0 | |
| 1102 && pConstraint->iColumn==1 | |
| 1103 && (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT | |
| 1104 || pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE) | |
| 1105 ){ | |
| 1106 iPlan |= 2; | |
| 1107 iDistTerm = i; | |
| 1108 rCost /= 10.0; | |
| 1109 } | |
| 1110 if( (iPlan & 4)==0 | |
| 1111 && pConstraint->iColumn==2 | |
| 1112 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ | |
| 1113 ){ | |
| 1114 iPlan |= 4; | |
| 1115 pIdxInfo->aConstraintUsage[i].omit = 1; | |
| 1116 iRulesetTerm = i; | |
| 1117 rCost /= 10.0; | |
| 1118 } | |
| 1119 } | |
| 1120 if( iPlan & 2 ){ | |
| 1121 pIdxInfo->aConstraintUsage[iDistTerm].argvIndex = 1+((iPlan&1)!=0); | |
| 1122 } | |
| 1123 if( iPlan & 4 ){ | |
| 1124 int idx = 1; | |
| 1125 if( iPlan & 1 ) idx++; | |
| 1126 if( iPlan & 2 ) idx++; | |
| 1127 pIdxInfo->aConstraintUsage[iRulesetTerm].argvIndex = idx; | |
| 1128 } | |
| 1129 pIdxInfo->idxNum = iPlan; | |
| 1130 if( pIdxInfo->nOrderBy==1 | |
| 1131 && pIdxInfo->aOrderBy[0].iColumn==1 | |
| 1132 && pIdxInfo->aOrderBy[0].desc==0 | |
| 1133 ){ | |
| 1134 pIdxInfo->orderByConsumed = 1; | |
| 1135 } | |
| 1136 if( seenMatch && (iPlan&1)==0 ) rCost = 1e99; | |
| 1137 pIdxInfo->estimatedCost = rCost; | |
| 1138 | |
| 1139 return SQLITE_OK; | |
| 1140 } | |
| 1141 | |
| 1142 /* | |
| 1143 ** A virtual table module that implements the "fuzzer". | |
| 1144 */ | |
| 1145 static sqlite3_module fuzzerModule = { | |
| 1146 0, /* iVersion */ | |
| 1147 fuzzerConnect, | |
| 1148 fuzzerConnect, | |
| 1149 fuzzerBestIndex, | |
| 1150 fuzzerDisconnect, | |
| 1151 fuzzerDisconnect, | |
| 1152 fuzzerOpen, /* xOpen - open a cursor */ | |
| 1153 fuzzerClose, /* xClose - close a cursor */ | |
| 1154 fuzzerFilter, /* xFilter - configure scan constraints */ | |
| 1155 fuzzerNext, /* xNext - advance a cursor */ | |
| 1156 fuzzerEof, /* xEof - check for end of scan */ | |
| 1157 fuzzerColumn, /* xColumn - read data */ | |
| 1158 fuzzerRowid, /* xRowid - read data */ | |
| 1159 0, /* xUpdate */ | |
| 1160 0, /* xBegin */ | |
| 1161 0, /* xSync */ | |
| 1162 0, /* xCommit */ | |
| 1163 0, /* xRollback */ | |
| 1164 0, /* xFindMethod */ | |
| 1165 0, /* xRename */ | |
| 1166 }; | |
| 1167 | |
| 1168 #endif /* SQLITE_OMIT_VIRTUALTABLE */ | |
| 1169 | |
| 1170 | |
| 1171 #ifdef _WIN32 | |
| 1172 __declspec(dllexport) | |
| 1173 #endif | |
| 1174 int sqlite3_fuzzer_init( | |
| 1175 sqlite3 *db, | |
| 1176 char **pzErrMsg, | |
| 1177 const sqlite3_api_routines *pApi | |
| 1178 ){ | |
| 1179 int rc = SQLITE_OK; | |
| 1180 SQLITE_EXTENSION_INIT2(pApi); | |
| 1181 #ifndef SQLITE_OMIT_VIRTUALTABLE | |
| 1182 rc = sqlite3_create_module(db, "fuzzer", &fuzzerModule, 0); | |
| 1183 #endif | |
| 1184 return rc; | |
| 1185 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2846743003:
[sql] Remove SQLite 3.10.2 reference directory. (Closed)
