diff options
Diffstat (limited to 'src/test_fuzzer.c')
| -rw-r--r-- | src/test_fuzzer.c | 1215 |
1 files changed, 0 insertions, 1215 deletions
diff --git a/src/test_fuzzer.c b/src/test_fuzzer.c deleted file mode 100644 index 10496f2..0000000 --- a/src/test_fuzzer.c +++ /dev/null @@ -1,1215 +0,0 @@ -/* -** 2011 March 24 -** -** The author disclaims copyright to this source code. In place of -** a legal notice, here is a blessing: -** -** May you do good and not evil. -** May you find forgiveness for yourself and forgive others. -** May you share freely, never taking more than you give. -** -************************************************************************* -** -** Code for a demonstration virtual table that generates variations -** on an input word at increasing edit distances from the original. -** -** A fuzzer virtual table is created like this: -** -** CREATE VIRTUAL TABLE f USING fuzzer(<fuzzer-data-table>); -** -** When it is created, the new fuzzer table must be supplied with the -** name of a "fuzzer data table", which must reside in the same database -** file as the new fuzzer table. The fuzzer data table contains the various -** transformations and their costs that the fuzzer logic uses to generate -** variations. -** -** The fuzzer data table must contain exactly four columns (more precisely, -** the statement "SELECT * FROM <fuzzer_data_table>" must return records -** that consist of four columns). It does not matter what the columns are -** named. -** -** Each row in the fuzzer data table represents a single character -** transformation. The left most column of the row (column 0) contains an -** integer value - the identifier of the ruleset to which the transformation -** rule belongs (see "MULTIPLE RULE SETS" below). The second column of the -** row (column 0) contains the input character or characters. The third -** column contains the output character or characters. And the fourth column -** contains the integer cost of making the transformation. For example: -** -** CREATE TABLE f_data(ruleset, cFrom, cTo, Cost); -** INSERT INTO f_data(ruleset, cFrom, cTo, Cost) VALUES(0, '', 'a', 100); -** INSERT INTO f_data(ruleset, cFrom, cTo, Cost) VALUES(0, 'b', '', 87); -** INSERT INTO f_data(ruleset, cFrom, cTo, Cost) VALUES(0, 'o', 'oe', 38); -** INSERT INTO f_data(ruleset, cFrom, cTo, Cost) VALUES(0, 'oe', 'o', 40); -** -** The first row inserted into the fuzzer data table by the SQL script -** above indicates that the cost of inserting a letter 'a' is 100. (All -** costs are integers. We recommend that costs be scaled so that the -** average cost is around 100.) The second INSERT statement creates a rule -** saying that the cost of deleting a single letter 'b' is 87. The third -** and fourth INSERT statements mean that the cost of transforming a -** single letter "o" into the two-letter sequence "oe" is 38 and that the -** cost of transforming "oe" back into "o" is 40. -** -** The contents of the fuzzer data table are loaded into main memory when -** a fuzzer table is first created, and may be internally reloaded by the -** system at any subsequent time. Therefore, the fuzzer data table should be -** populated before the fuzzer table is created and not modified thereafter. -** If you do need to modify the contents of the fuzzer data table, it is -** recommended that the associated fuzzer table be dropped, the fuzzer data -** table edited, and the fuzzer table recreated within a single transaction. -** Alternatively, the fuzzer data table can be edited then the database -** connection can be closed and reopened. -** -** Once it has been created, the fuzzer table can be queried as follows: -** -** SELECT word, distance FROM f -** WHERE word MATCH 'abcdefg' -** AND distance<200; -** -** This first query outputs the string "abcdefg" and all strings that -** can be derived from that string by appling the specified transformations. -** The strings are output together with their total transformation cost -** (called "distance") and appear in order of increasing cost. No string -** is output more than once. If there are multiple ways to transform the -** target string into the output string then the lowest cost transform is -** the one that is returned. In the example, the search is limited to -** strings with a total distance of less than 200. -** -** The fuzzer is a read-only table. Any attempt to DELETE, INSERT, or -** UPDATE on a fuzzer table will throw an error. -** -** It is important to put some kind of a limit on the fuzzer output. This -** can be either in the form of a LIMIT clause at the end of the query, -** or better, a "distance<NNN" constraint where NNN is some number. The -** running time and memory requirement is exponential in the value of NNN -** so you want to make sure that NNN is not too big. A value of NNN that -** is about twice the average transformation cost seems to give good results. -** -** The fuzzer table can be useful for tasks such as spelling correction. -** Suppose there is a second table vocabulary(w) where the w column contains -** all correctly spelled words. Let $word be a word you want to look up. -** -** SELECT vocabulary.w FROM f, vocabulary -** WHERE f.word MATCH $word -** AND f.distance<=200 -** AND f.word=vocabulary.w -** LIMIT 20 -** -** The query above gives the 20 closest words to the $word being tested. -** (Note that for good performance, the vocubulary.w column should be -** indexed.) -** -** A similar query can be used to find all words in the dictionary that -** begin with some prefix $prefix: -** -** SELECT vocabulary.w FROM f, vocabulary -** WHERE f.word MATCH $prefix -** AND f.distance<=200 -** AND vocabulary.w BETWEEN f.word AND (f.word || x'F7BFBFBF') -** LIMIT 50 -** -** This last query will show up to 50 words out of the vocabulary that -** match or nearly match the $prefix. -** -** MULTIPLE RULE SETS -** -** Normally, the "ruleset" value associated with all character transformations -** in the fuzzer data table is zero. However, if required, the fuzzer table -** allows multiple rulesets to be defined. Each query uses only a single -** ruleset. This allows, for example, a single fuzzer table to support -** multiple languages. -** -** By default, only the rules from ruleset 0 are used. To specify an -** alternative ruleset, a "ruleset = ?" expression must be added to the -** WHERE clause of a SELECT, where ? is the identifier of the desired -** ruleset. For example: -** -** SELECT vocabulary.w FROM f, vocabulary -** WHERE f.word MATCH $word -** AND f.distance<=200 -** AND f.word=vocabulary.w -** AND f.ruleset=1 -- Specify the ruleset to use here -** LIMIT 20 -** -** If no "ruleset = ?" constraint is specified in the WHERE clause, ruleset -** 0 is used. -** -** LIMITS -** -** The maximum ruleset number is 2147483647. The maximum length of either -** of the strings in the second or third column of the fuzzer data table -** is 50 bytes. The maximum cost on a rule is 1000. -*/ - -/* If SQLITE_DEBUG is not defined, disable assert statements. */ -#if !defined(NDEBUG) && !defined(SQLITE_DEBUG) -# define NDEBUG -#endif - -#include "sqlite3.h" -#include <stdlib.h> -#include <string.h> -#include <assert.h> -#include <stdio.h> - -#ifndef SQLITE_OMIT_VIRTUALTABLE - -/* -** Forward declaration of objects used by this implementation -*/ -typedef struct fuzzer_vtab fuzzer_vtab; -typedef struct fuzzer_cursor fuzzer_cursor; -typedef struct fuzzer_rule fuzzer_rule; -typedef struct fuzzer_seen fuzzer_seen; -typedef struct fuzzer_stem fuzzer_stem; - -/* -** Various types. -** -** fuzzer_cost is the "cost" of an edit operation. -** -** fuzzer_len is the length of a matching string. -** -** fuzzer_ruleid is an ruleset identifier. -*/ -typedef int fuzzer_cost; -typedef signed char fuzzer_len; -typedef int fuzzer_ruleid; - -/* -** Limits -*/ -#define FUZZER_MX_LENGTH 50 /* Maximum length of a rule string */ -#define FUZZER_MX_RULEID 2147483647 /* Maximum rule ID */ -#define FUZZER_MX_COST 1000 /* Maximum single-rule cost */ -#define FUZZER_MX_OUTPUT_LENGTH 100 /* Maximum length of an output string */ - - -/* -** Each transformation rule is stored as an instance of this object. -** All rules are kept on a linked list sorted by rCost. -*/ -struct fuzzer_rule { - fuzzer_rule *pNext; /* Next rule in order of increasing rCost */ - char *zFrom; /* Transform from */ - fuzzer_cost rCost; /* Cost of this transformation */ - fuzzer_len nFrom, nTo; /* Length of the zFrom and zTo strings */ - fuzzer_ruleid iRuleset; /* The rule set to which this rule belongs */ - char zTo[4]; /* Transform to (extra space appended) */ -}; - -/* -** A stem object is used to generate variants. It is also used to record -** previously generated outputs. -** -** Every stem is added to a hash table as it is output. Generation of -** duplicate stems is suppressed. -** -** Active stems (those that might generate new outputs) are kepts on a linked -** list sorted by increasing cost. The cost is the sum of rBaseCost and -** pRule->rCost. -*/ -struct fuzzer_stem { - char *zBasis; /* Word being fuzzed */ - const fuzzer_rule *pRule; /* Current rule to apply */ - fuzzer_stem *pNext; /* Next stem in rCost order */ - fuzzer_stem *pHash; /* Next stem with same hash on zBasis */ - fuzzer_cost rBaseCost; /* Base cost of getting to zBasis */ - fuzzer_cost rCostX; /* Precomputed rBaseCost + pRule->rCost */ - fuzzer_len nBasis; /* Length of the zBasis string */ - fuzzer_len n; /* Apply pRule at this character offset */ -}; - -/* -** A fuzzer virtual-table object -*/ -struct fuzzer_vtab { - sqlite3_vtab base; /* Base class - must be first */ - char *zClassName; /* Name of this class. Default: "fuzzer" */ - fuzzer_rule *pRule; /* All active rules in this fuzzer */ - int nCursor; /* Number of active cursors */ -}; - -#define FUZZER_HASH 4001 /* Hash table size */ -#define FUZZER_NQUEUE 20 /* Number of slots on the stem queue */ - -/* A fuzzer cursor object */ -struct fuzzer_cursor { - sqlite3_vtab_cursor base; /* Base class - must be first */ - sqlite3_int64 iRowid; /* The rowid of the current word */ - fuzzer_vtab *pVtab; /* The virtual table this cursor belongs to */ - fuzzer_cost rLimit; /* Maximum cost of any term */ - fuzzer_stem *pStem; /* Stem with smallest rCostX */ - fuzzer_stem *pDone; /* Stems already processed to completion */ - fuzzer_stem *aQueue[FUZZER_NQUEUE]; /* Queue of stems with higher rCostX */ - int mxQueue; /* Largest used index in aQueue[] */ - char *zBuf; /* Temporary use buffer */ - int nBuf; /* Bytes allocated for zBuf */ - int nStem; /* Number of stems allocated */ - int iRuleset; /* Only process rules from this ruleset */ - fuzzer_rule nullRule; /* Null rule used first */ - fuzzer_stem *apHash[FUZZER_HASH]; /* Hash of previously generated terms */ -}; - -/* -** The two input rule lists are both sorted in order of increasing -** cost. Merge them together into a single list, sorted by cost, and -** return a pointer to the head of that list. -*/ -static fuzzer_rule *fuzzerMergeRules(fuzzer_rule *pA, fuzzer_rule *pB){ - fuzzer_rule head; - fuzzer_rule *pTail; - - pTail = &head; - while( pA && pB ){ - if( pA->rCost<=pB->rCost ){ - pTail->pNext = pA; - pTail = pA; - pA = pA->pNext; - }else{ - pTail->pNext = pB; - pTail = pB; - pB = pB->pNext; - } - } - if( pA==0 ){ - pTail->pNext = pB; - }else{ - pTail->pNext = pA; - } - return head.pNext; -} - -/* -** Statement pStmt currently points to a row in the fuzzer data table. This -** function allocates and populates a fuzzer_rule structure according to -** the content of the row. -** -** If successful, *ppRule is set to point to the new object and SQLITE_OK -** is returned. Otherwise, *ppRule is zeroed, *pzErr may be set to point -** to an error message and an SQLite error code returned. -*/ -static int fuzzerLoadOneRule( - fuzzer_vtab *p, /* Fuzzer virtual table handle */ - sqlite3_stmt *pStmt, /* Base rule on statements current row */ - fuzzer_rule **ppRule, /* OUT: New rule object */ - char **pzErr /* OUT: Error message */ -){ - sqlite3_int64 iRuleset = sqlite3_column_int64(pStmt, 0); - const char *zFrom = (const char *)sqlite3_column_text(pStmt, 1); - const char *zTo = (const char *)sqlite3_column_text(pStmt, 2); - int nCost = sqlite3_column_int(pStmt, 3); - - int rc = SQLITE_OK; /* Return code */ - int nFrom; /* Size of string zFrom, in bytes */ - int nTo; /* Size of string zTo, in bytes */ - fuzzer_rule *pRule = 0; /* New rule object to return */ - - if( zFrom==0 ) zFrom = ""; - if( zTo==0 ) zTo = ""; - nFrom = (int)strlen(zFrom); - nTo = (int)strlen(zTo); - - /* Silently ignore null transformations */ - if( strcmp(zFrom, zTo)==0 ){ - *ppRule = 0; - return SQLITE_OK; - } - - if( nCost<=0 || nCost>FUZZER_MX_COST ){ - *pzErr = sqlite3_mprintf("%s: cost must be between 1 and %d", - p->zClassName, FUZZER_MX_COST - ); - rc = SQLITE_ERROR; - }else - if( nFrom>FUZZER_MX_LENGTH || nTo>FUZZER_MX_LENGTH ){ - *pzErr = sqlite3_mprintf("%s: maximum string length is %d", - p->zClassName, FUZZER_MX_LENGTH - ); - rc = SQLITE_ERROR; - }else - if( iRuleset<0 || iRuleset>FUZZER_MX_RULEID ){ - *pzErr = sqlite3_mprintf("%s: ruleset must be between 0 and %d", - p->zClassName, FUZZER_MX_RULEID - ); - rc = SQLITE_ERROR; - }else{ - - pRule = sqlite3_malloc( sizeof(*pRule) + nFrom + nTo ); - if( pRule==0 ){ - rc = SQLITE_NOMEM; - }else{ - memset(pRule, 0, sizeof(*pRule)); - pRule->zFrom = &pRule->zTo[nTo+1]; - pRule->nFrom = nFrom; - memcpy(pRule->zFrom, zFrom, nFrom+1); - memcpy(pRule->zTo, zTo, nTo+1); - pRule->nTo = nTo; - pRule->rCost = nCost; - pRule->iRuleset = (int)iRuleset; - } - } - - *ppRule = pRule; - return rc; -} - -/* -** Load the content of the fuzzer data table into memory. -*/ -static int fuzzerLoadRules( - sqlite3 *db, /* Database handle */ - fuzzer_vtab *p, /* Virtual fuzzer table to configure */ - const char *zDb, /* Database containing rules data */ - const char *zData, /* Table containing rules data */ - char **pzErr /* OUT: Error message */ -){ - int rc = SQLITE_OK; /* Return code */ - char *zSql; /* SELECT used to read from rules table */ - fuzzer_rule *pHead = 0; - - zSql = sqlite3_mprintf("SELECT * FROM %Q.%Q", zDb, zData); - if( zSql==0 ){ - rc = SQLITE_NOMEM; - }else{ - int rc2; /* finalize() return code */ - sqlite3_stmt *pStmt = 0; - rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0); - if( rc!=SQLITE_OK ){ - *pzErr = sqlite3_mprintf("%s: %s", p->zClassName, sqlite3_errmsg(db)); - }else if( sqlite3_column_count(pStmt)!=4 ){ - *pzErr = sqlite3_mprintf("%s: %s has %d columns, expected 4", - p->zClassName, zData, sqlite3_column_count(pStmt) - ); - rc = SQLITE_ERROR; - }else{ - while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pStmt) ){ - fuzzer_rule *pRule = 0; - rc = fuzzerLoadOneRule(p, pStmt, &pRule, pzErr); - if( pRule ){ - pRule->pNext = pHead; - pHead = pRule; - } - } - } - rc2 = sqlite3_finalize(pStmt); - if( rc==SQLITE_OK ) rc = rc2; - } - sqlite3_free(zSql); - - /* All rules are now in a singly linked list starting at pHead. This - ** block sorts them by cost and then sets fuzzer_vtab.pRule to point to - ** point to the head of the sorted list. - */ - if( rc==SQLITE_OK ){ - unsigned int i; - fuzzer_rule *pX; - fuzzer_rule *a[15]; - for(i=0; i<sizeof(a)/sizeof(a[0]); i++) a[i] = 0; - while( (pX = pHead)!=0 ){ - pHead = pX->pNext; - pX->pNext = 0; - for(i=0; a[i] && i<sizeof(a)/sizeof(a[0])-1; i++){ - pX = fuzzerMergeRules(a[i], pX); - a[i] = 0; - } - a[i] = fuzzerMergeRules(a[i], pX); - } - for(pX=a[0], i=1; i<sizeof(a)/sizeof(a[0]); i++){ - pX = fuzzerMergeRules(a[i], pX); - } - p->pRule = fuzzerMergeRules(p->pRule, pX); - }else{ - /* An error has occurred. Setting p->pRule to point to the head of the - ** allocated list ensures that the list will be cleaned up in this case. - */ - assert( p->pRule==0 ); - p->pRule = pHead; - } - - return rc; -} - -/* -** This function converts an SQL quoted string into an unquoted string -** and returns a pointer to a buffer allocated using sqlite3_malloc() -** containing the result. The caller should eventually free this buffer -** using sqlite3_free. -** -** Examples: -** -** "abc" becomes abc -** 'xyz' becomes xyz -** [pqr] becomes pqr -** `mno` becomes mno -*/ -static char *fuzzerDequote(const char *zIn){ - int nIn; /* Size of input string, in bytes */ - char *zOut; /* Output (dequoted) string */ - - nIn = (int)strlen(zIn); - zOut = sqlite3_malloc(nIn+1); - if( zOut ){ - char q = zIn[0]; /* Quote character (if any ) */ - - if( q!='[' && q!= '\'' && q!='"' && q!='`' ){ - memcpy(zOut, zIn, nIn+1); - }else{ - int iOut = 0; /* Index of next byte to write to output */ - int iIn; /* Index of next byte to read from input */ - - if( q=='[' ) q = ']'; - for(iIn=1; iIn<nIn; iIn++){ - if( zIn[iIn]==q ) iIn++; - zOut[iOut++] = zIn[iIn]; - } - } - assert( (int)strlen(zOut)<=nIn ); - } - return zOut; -} - -/* -** xDisconnect/xDestroy method for the fuzzer module. -*/ -static int fuzzerDisconnect(sqlite3_vtab *pVtab){ - fuzzer_vtab *p = (fuzzer_vtab*)pVtab; - assert( p->nCursor==0 ); - while( p->pRule ){ - fuzzer_rule *pRule = p->pRule; - p->pRule = pRule->pNext; - sqlite3_free(pRule); - } - sqlite3_free(p); - return SQLITE_OK; -} - -/* -** xConnect/xCreate method for the fuzzer module. Arguments are: -** -** argv[0] -> module name ("fuzzer") -** argv[1] -> database name -** argv[2] -> table name -** argv[3] -> fuzzer rule table name -*/ -static int fuzzerConnect( - sqlite3 *db, - void *pAux, - int argc, const char *const*argv, - sqlite3_vtab **ppVtab, - char **pzErr -){ - int rc = SQLITE_OK; /* Return code */ - fuzzer_vtab *pNew = 0; /* New virtual table */ - const char *zModule = argv[0]; - const char *zDb = argv[1]; - - if( argc!=4 ){ - *pzErr = sqlite3_mprintf( - "%s: wrong number of CREATE VIRTUAL TABLE arguments", zModule - ); - rc = SQLITE_ERROR; - }else{ - int nModule; /* Length of zModule, in bytes */ - - nModule = (int)strlen(zModule); - pNew = sqlite3_malloc( sizeof(*pNew) + nModule + 1); - if( pNew==0 ){ - rc = SQLITE_NOMEM; - }else{ - char *zTab; /* Dequoted name of fuzzer data table */ - - memset(pNew, 0, sizeof(*pNew)); - pNew->zClassName = (char*)&pNew[1]; - memcpy(pNew->zClassName, zModule, nModule+1); - - zTab = fuzzerDequote(argv[3]); - if( zTab==0 ){ - rc = SQLITE_NOMEM; - }else{ - rc = fuzzerLoadRules(db, pNew, zDb, zTab, pzErr); - sqlite3_free(zTab); - } - - if( rc==SQLITE_OK ){ - rc = sqlite3_declare_vtab(db, "CREATE TABLE x(word,distance,ruleset)"); - } - if( rc!=SQLITE_OK ){ - fuzzerDisconnect((sqlite3_vtab *)pNew); - pNew = 0; - } - } - } - - *ppVtab = (sqlite3_vtab *)pNew; - return rc; -} - -/* -** Open a new fuzzer cursor. -*/ -static int fuzzerOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){ - fuzzer_vtab *p = (fuzzer_vtab*)pVTab; - fuzzer_cursor *pCur; - pCur = sqlite3_malloc( sizeof(*pCur) ); - if( pCur==0 ) return SQLITE_NOMEM; - memset(pCur, 0, sizeof(*pCur)); - pCur->pVtab = p; - *ppCursor = &pCur->base; - p->nCursor++; - return SQLITE_OK; -} - -/* -** Free all stems in a list. -*/ -static void fuzzerClearStemList(fuzzer_stem *pStem){ - while( pStem ){ - fuzzer_stem *pNext = pStem->pNext; - sqlite3_free(pStem); - pStem = pNext; - } -} - -/* -** Free up all the memory allocated by a cursor. Set it rLimit to 0 -** to indicate that it is at EOF. -*/ -static void fuzzerClearCursor(fuzzer_cursor *pCur, int clearHash){ - int i; - fuzzerClearStemList(pCur->pStem); - fuzzerClearStemList(pCur->pDone); - for(i=0; i<FUZZER_NQUEUE; i++) fuzzerClearStemList(pCur->aQueue[i]); - pCur->rLimit = (fuzzer_cost)0; - if( clearHash && pCur->nStem ){ - pCur->mxQueue = 0; - pCur->pStem = 0; - pCur->pDone = 0; - memset(pCur->aQueue, 0, sizeof(pCur->aQueue)); - memset(pCur->apHash, 0, sizeof(pCur->apHash)); - } - pCur->nStem = 0; -} - -/* -** Close a fuzzer cursor. -*/ -static int fuzzerClose(sqlite3_vtab_cursor *cur){ - fuzzer_cursor *pCur = (fuzzer_cursor *)cur; - fuzzerClearCursor(pCur, 0); - sqlite3_free(pCur->zBuf); - pCur->pVtab->nCursor--; - sqlite3_free(pCur); - return SQLITE_OK; -} - -/* -** Compute the current output term for a fuzzer_stem. -*/ -static int fuzzerRender( - fuzzer_stem *pStem, /* The stem to be rendered */ - char **pzBuf, /* Write results into this buffer. realloc if needed */ - int *pnBuf /* Size of the buffer */ -){ - const fuzzer_rule *pRule = pStem->pRule; - int n; /* Size of output term without nul-term */ - char *z; /* Buffer to assemble output term in */ - - n = pStem->nBasis + pRule->nTo - pRule->nFrom; - if( (*pnBuf)<n+1 ){ - (*pzBuf) = sqlite3_realloc((*pzBuf), n+100); - if( (*pzBuf)==0 ) return SQLITE_NOMEM; - (*pnBuf) = n+100; - } - n = pStem->n; - z = *pzBuf; - if( n<0 ){ - memcpy(z, pStem->zBasis, pStem->nBasis+1); - }else{ - memcpy(z, pStem->zBasis, n); - memcpy(&z[n], pRule->zTo, pRule->nTo); - memcpy(&z[n+pRule->nTo], &pStem->zBasis[n+pRule->nFrom], - pStem->nBasis-n-pRule->nFrom+1); - } - - assert( z[pStem->nBasis + pRule->nTo - pRule->nFrom]==0 ); - return SQLITE_OK; -} - -/* -** Compute a hash on zBasis. -*/ -static unsigned int fuzzerHash(const char *z){ - unsigned int h = 0; - while( *z ){ h = (h<<3) ^ (h>>29) ^ *(z++); } - return h % FUZZER_HASH; -} - -/* -** Current cost of a stem -*/ -static fuzzer_cost fuzzerCost(fuzzer_stem *pStem){ - return pStem->rCostX = pStem->rBaseCost + pStem->pRule->rCost; -} - -#if 0 -/* -** Print a description of a fuzzer_stem on stderr. -*/ -static void fuzzerStemPrint( - const char *zPrefix, - fuzzer_stem *pStem, - const char *zSuffix -){ - if( pStem->n<0 ){ - fprintf(stderr, "%s[%s](%d)-->self%s", - zPrefix, - pStem->zBasis, pStem->rBaseCost, - zSuffix - ); - }else{ - char *zBuf = 0; - int nBuf = 0; - if( fuzzerRender(pStem, &zBuf, &nBuf)!=SQLITE_OK ) return; - fprintf(stderr, "%s[%s](%d)-->{%s}(%d)%s", - zPrefix, - pStem->zBasis, pStem->rBaseCost, zBuf, pStem->, - zSuffix - ); - sqlite3_free(zBuf); - } -} -#endif - -/* -** Return 1 if the string to which the cursor is point has already -** been emitted. Return 0 if not. Return -1 on a memory allocation -** failures. -*/ -static int fuzzerSeen(fuzzer_cursor *pCur, fuzzer_stem *pStem){ - unsigned int h; - fuzzer_stem *pLookup; - - if( fuzzerRender(pStem, &pCur->zBuf, &pCur->nBuf)==SQLITE_NOMEM ){ - return -1; - } - h = fuzzerHash(pCur->zBuf); - pLookup = pCur->apHash[h]; - while( pLookup && strcmp(pLookup->zBasis, pCur->zBuf)!=0 ){ - pLookup = pLookup->pHash; - } - return pLookup!=0; -} - -/* -** If argument pRule is NULL, this function returns false. -** -** Otherwise, it returns true if rule pRule should be skipped. A rule -** should be skipped if it does not belong to rule-set iRuleset, or if -** applying it to stem pStem would create a string longer than -** FUZZER_MX_OUTPUT_LENGTH bytes. -*/ -static int fuzzerSkipRule( - const fuzzer_rule *pRule, /* Determine whether or not to skip this */ - fuzzer_stem *pStem, /* Stem rule may be applied to */ - int iRuleset /* Rule-set used by the current query */ -){ - return pRule && ( - (pRule->iRuleset!=iRuleset) - || (pStem->nBasis + pRule->nTo - pRule->nFrom)>FUZZER_MX_OUTPUT_LENGTH - ); -} - -/* -** Advance a fuzzer_stem to its next value. Return 0 if there are -** no more values that can be generated by this fuzzer_stem. Return -** -1 on a memory allocation failure. -*/ -static int fuzzerAdvance(fuzzer_cursor *pCur, fuzzer_stem *pStem){ - const fuzzer_rule *pRule; - while( (pRule = pStem->pRule)!=0 ){ - assert( pRule==&pCur->nullRule || pRule->iRuleset==pCur->iRuleset ); - while( pStem->n < pStem->nBasis - pRule->nFrom ){ - pStem->n++; - if( pRule->nFrom==0 - || memcmp(&pStem->zBasis[pStem->n], pRule->zFrom, pRule->nFrom)==0 - ){ - /* Found a rewrite case. Make sure it is not a duplicate */ - int rc = fuzzerSeen(pCur, pStem); - if( rc<0 ) return -1; - if( rc==0 ){ - fuzzerCost(pStem); - return 1; - } - } - } - pStem->n = -1; - do{ - pRule = pRule->pNext; - }while( fuzzerSkipRule(pRule, pStem, pCur->iRuleset) ); - pStem->pRule = pRule; - if( pRule && fuzzerCost(pStem)>pCur->rLimit ) pStem->pRule = 0; - } - return 0; -} - -/* -** The two input stem lists are both sorted in order of increasing -** rCostX. Merge them together into a single list, sorted by rCostX, and -** return a pointer to the head of that new list. -*/ -static fuzzer_stem *fuzzerMergeStems(fuzzer_stem *pA, fuzzer_stem *pB){ - fuzzer_stem head; - fuzzer_stem *pTail; - - pTail = &head; - while( pA && pB ){ - if( pA->rCostX<=pB->rCostX ){ - pTail->pNext = pA; - pTail = pA; - pA = pA->pNext; - }else{ - pTail->pNext = pB; - pTail = pB; - pB = pB->pNext; - } - } - if( pA==0 ){ - pTail->pNext = pB; - }else{ - pTail->pNext = pA; - } - return head.pNext; -} - -/* -** Load pCur->pStem with the lowest-cost stem. Return a pointer -** to the lowest-cost stem. -*/ -static fuzzer_stem *fuzzerLowestCostStem(fuzzer_cursor *pCur){ - fuzzer_stem *pBest, *pX; - int iBest; - int i; - - if( pCur->pStem==0 ){ - iBest = -1; - pBest = 0; - for(i=0; i<=pCur->mxQueue; i++){ - pX = pCur->aQueue[i]; - if( pX==0 ) continue; - if( pBest==0 || pBest->rCostX>pX->rCostX ){ - pBest = pX; - iBest = i; - } - } - if( pBest ){ - pCur->aQueue[iBest] = pBest->pNext; - pBest->pNext = 0; - pCur->pStem = pBest; - } - } - return pCur->pStem; -} - -/* -** Insert pNew into queue of pending stems. Then find the stem -** with the lowest rCostX and move it into pCur->pStem. -** list. The insert is done such the pNew is in the correct order -** according to fuzzer_stem.zBaseCost+fuzzer_stem.pRule->rCost. -*/ -static fuzzer_stem *fuzzerInsert(fuzzer_cursor *pCur, fuzzer_stem *pNew){ - fuzzer_stem *pX; - int i; - - /* If pCur->pStem exists and is greater than pNew, then make pNew - ** the new pCur->pStem and insert the old pCur->pStem instead. - */ - if( (pX = pCur->pStem)!=0 && pX->rCostX>pNew->rCostX ){ - pNew->pNext = 0; - pCur->pStem = pNew; - pNew = pX; - } - - /* Insert the new value */ - pNew->pNext = 0; - pX = pNew; - for(i=0; i<=pCur->mxQueue; i++){ - if( pCur->aQueue[i] ){ - pX = fuzzerMergeStems(pX, pCur->aQueue[i]); - pCur->aQueue[i] = 0; - }else{ - pCur->aQueue[i] = pX; - break; - } - } - if( i>pCur->mxQueue ){ - if( i<FUZZER_NQUEUE ){ - pCur->mxQueue = i; - pCur->aQueue[i] = pX; - }else{ - assert( pCur->mxQueue==FUZZER_NQUEUE-1 ); - pX = fuzzerMergeStems(pX, pCur->aQueue[FUZZER_NQUEUE-1]); - pCur->aQueue[FUZZER_NQUEUE-1] = pX; - } - } - - return fuzzerLowestCostStem(pCur); -} - -/* -** Allocate a new fuzzer_stem. Add it to the hash table but do not -** link it into either the pCur->pStem or pCur->pDone lists. -*/ -static fuzzer_stem *fuzzerNewStem( - fuzzer_cursor *pCur, - const char *zWord, - fuzzer_cost rBaseCost -){ - fuzzer_stem *pNew; - fuzzer_rule *pRule; - unsigned int h; - - pNew = sqlite3_malloc( sizeof(*pNew) + (int)strlen(zWord) + 1 ); - if( pNew==0 ) return 0; - memset(pNew, 0, sizeof(*pNew)); - pNew->zBasis = (char*)&pNew[1]; - pNew->nBasis = (int)strlen(zWord); - memcpy(pNew->zBasis, zWord, pNew->nBasis+1); - pRule = pCur->pVtab->pRule; - while( fuzzerSkipRule(pRule, pNew, pCur->iRuleset) ){ - pRule = pRule->pNext; - } - pNew->pRule = pRule; - pNew->n = -1; - pNew->rBaseCost = pNew->rCostX = rBaseCost; - h = fuzzerHash(pNew->zBasis); - pNew->pHash = pCur->apHash[h]; - pCur->apHash[h] = pNew; - pCur->nStem++; - return pNew; -} - - -/* -** Advance a cursor to its next row of output -*/ -static int fuzzerNext(sqlite3_vtab_cursor *cur){ - fuzzer_cursor *pCur = (fuzzer_cursor*)cur; - int rc; - fuzzer_stem *pStem, *pNew; - - pCur->iRowid++; - - /* Use the element the cursor is currently point to to create - ** a new stem and insert the new stem into the priority queue. - */ - pStem = pCur->pStem; - if( pStem->rCostX>0 ){ - rc = fuzzerRender(pStem, &pCur->zBuf, &pCur->nBuf); - if( rc==SQLITE_NOMEM ) return SQLITE_NOMEM; - pNew = fuzzerNewStem(pCur, pCur->zBuf, pStem->rCostX); - if( pNew ){ - if( fuzzerAdvance(pCur, pNew)==0 ){ - pNew->pNext = pCur->pDone; - pCur->pDone = pNew; - }else{ - if( fuzzerInsert(pCur, pNew)==pNew ){ - return SQLITE_OK; - } - } - }else{ - return SQLITE_NOMEM; - } - } - - /* Adjust the priority queue so that the first element of the - ** stem list is the next lowest cost word. - */ - while( (pStem = pCur->pStem)!=0 ){ - int res = fuzzerAdvance(pCur, pStem); - if( res<0 ){ - return SQLITE_NOMEM; - }else if( res>0 ){ - pCur->pStem = 0; - pStem = fuzzerInsert(pCur, pStem); - if( (rc = fuzzerSeen(pCur, pStem))!=0 ){ - if( rc<0 ) return SQLITE_NOMEM; - continue; - } - return SQLITE_OK; /* New word found */ - } - pCur->pStem = 0; - pStem->pNext = pCur->pDone; - pCur->pDone = pStem; - if( fuzzerLowestCostStem(pCur) ){ - rc = fuzzerSeen(pCur, pCur->pStem); - if( rc<0 ) return SQLITE_NOMEM; - if( rc==0 ){ - return SQLITE_OK; - } - } - } - - /* Reach this point only if queue has been exhausted and there is - ** nothing left to be output. */ - pCur->rLimit = (fuzzer_cost)0; - return SQLITE_OK; -} - -/* -** Called to "rewind" a cursor back to the beginning so that -** it starts its output over again. Always called at least once -** prior to any fuzzerColumn, fuzzerRowid, or fuzzerEof call. -*/ -static int fuzzerFilter( - sqlite3_vtab_cursor *pVtabCursor, - int idxNum, const char *idxStr, - int argc, sqlite3_value **argv -){ - fuzzer_cursor *pCur = (fuzzer_cursor *)pVtabCursor; - const char *zWord = ""; - fuzzer_stem *pStem; - int idx; - - fuzzerClearCursor(pCur, 1); - pCur->rLimit = 2147483647; - idx = 0; - if( idxNum & 1 ){ - zWord = (const char*)sqlite3_value_text(argv[0]); - idx++; - } - if( idxNum & 2 ){ - pCur->rLimit = (fuzzer_cost)sqlite3_value_int(argv[idx]); - idx++; - } - if( idxNum & 4 ){ - pCur->iRuleset = (fuzzer_cost)sqlite3_value_int(argv[idx]); - idx++; - } - pCur->nullRule.pNext = pCur->pVtab->pRule; - pCur->nullRule.rCost = 0; - pCur->nullRule.nFrom = 0; - pCur->nullRule.nTo = 0; - pCur->nullRule.zFrom = ""; - pCur->iRowid = 1; - assert( pCur->pStem==0 ); - - /* If the query term is longer than FUZZER_MX_OUTPUT_LENGTH bytes, this - ** query will return zero rows. */ - if( (int)strlen(zWord)<FUZZER_MX_OUTPUT_LENGTH ){ - pCur->pStem = pStem = fuzzerNewStem(pCur, zWord, (fuzzer_cost)0); - if( pStem==0 ) return SQLITE_NOMEM; - pStem->pRule = &pCur->nullRule; - pStem->n = pStem->nBasis; - }else{ - pCur->rLimit = 0; - } - - return SQLITE_OK; -} - -/* -** Only the word and distance columns have values. All other columns -** return NULL -*/ -static int fuzzerColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){ - fuzzer_cursor *pCur = (fuzzer_cursor*)cur; - if( i==0 ){ - /* the "word" column */ - if( fuzzerRender(pCur->pStem, &pCur->zBuf, &pCur->nBuf)==SQLITE_NOMEM ){ - return SQLITE_NOMEM; - } - sqlite3_result_text(ctx, pCur->zBuf, -1, SQLITE_TRANSIENT); - }else if( i==1 ){ - /* the "distance" column */ - sqlite3_result_int(ctx, pCur->pStem->rCostX); - }else{ - /* All other columns are NULL */ - sqlite3_result_null(ctx); - } - return SQLITE_OK; -} - -/* -** The rowid. -*/ -static int fuzzerRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){ - fuzzer_cursor *pCur = (fuzzer_cursor*)cur; - *pRowid = pCur->iRowid; - return SQLITE_OK; -} - -/* -** When the fuzzer_cursor.rLimit value is 0 or less, that is a signal -** that the cursor has nothing more to output. -*/ -static int fuzzerEof(sqlite3_vtab_cursor *cur){ - fuzzer_cursor *pCur = (fuzzer_cursor*)cur; - return pCur->rLimit<=(fuzzer_cost)0; -} - -/* -** Search for terms of these forms: -** -** (A) word MATCH $str -** (B1) distance < $value -** (B2) distance <= $value -** (C) ruleid == $ruleid -** -** The distance< and distance<= are both treated as distance<=. -** The query plan number is a bit vector: -** -** bit 1: Term of the form (A) found -** bit 2: Term like (B1) or (B2) found -** bit 3: Term like (C) found -** -** If bit-1 is set, $str is always in filter.argv[0]. If bit-2 is set -** then $value is in filter.argv[0] if bit-1 is clear and is in -** filter.argv[1] if bit-1 is set. If bit-3 is set, then $ruleid is -** in filter.argv[0] if bit-1 and bit-2 are both zero, is in -** filter.argv[1] if exactly one of bit-1 and bit-2 are set, and is in -** filter.argv[2] if both bit-1 and bit-2 are set. -*/ -static int fuzzerBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){ - int iPlan = 0; - int iDistTerm = -1; - int iRulesetTerm = -1; - int i; - const struct sqlite3_index_constraint *pConstraint; - pConstraint = pIdxInfo->aConstraint; - for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){ - if( pConstraint->usable==0 ) continue; - if( (iPlan & 1)==0 - && pConstraint->iColumn==0 - && pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH - ){ - iPlan |= 1; - pIdxInfo->aConstraintUsage[i].argvIndex = 1; - pIdxInfo->aConstraintUsage[i].omit = 1; - } - if( (iPlan & 2)==0 - && pConstraint->iColumn==1 - && (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT - || pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE) - ){ - iPlan |= 2; - iDistTerm = i; - } - if( (iPlan & 4)==0 - && pConstraint->iColumn==2 - && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ - ){ - iPlan |= 4; - pIdxInfo->aConstraintUsage[i].omit = 1; - iRulesetTerm = i; - } - } - if( iPlan & 2 ){ - pIdxInfo->aConstraintUsage[iDistTerm].argvIndex = 1+((iPlan&1)!=0); - } - if( iPlan & 4 ){ - int idx = 1; - if( iPlan & 1 ) idx++; - if( iPlan & 2 ) idx++; - pIdxInfo->aConstraintUsage[iRulesetTerm].argvIndex = idx; - } - pIdxInfo->idxNum = iPlan; - if( pIdxInfo->nOrderBy==1 - && pIdxInfo->aOrderBy[0].iColumn==1 - && pIdxInfo->aOrderBy[0].desc==0 - ){ - pIdxInfo->orderByConsumed = 1; - } - pIdxInfo->estimatedCost = (double)10000; - - return SQLITE_OK; -} - -/* -** A virtual table module that implements the "fuzzer". -*/ -static sqlite3_module fuzzerModule = { - 0, /* iVersion */ - fuzzerConnect, - fuzzerConnect, - fuzzerBestIndex, - fuzzerDisconnect, - fuzzerDisconnect, - fuzzerOpen, /* xOpen - open a cursor */ - fuzzerClose, /* xClose - close a cursor */ - fuzzerFilter, /* xFilter - configure scan constraints */ - fuzzerNext, /* xNext - advance a cursor */ - fuzzerEof, /* xEof - check for end of scan */ - fuzzerColumn, /* xColumn - read data */ - fuzzerRowid, /* xRowid - read data */ - 0, /* xUpdate */ - 0, /* xBegin */ - 0, /* xSync */ - 0, /* xCommit */ - 0, /* xRollback */ - 0, /* xFindMethod */ - 0, /* xRename */ -}; - -#endif /* SQLITE_OMIT_VIRTUALTABLE */ - - -/* -** Register the fuzzer virtual table -*/ -int fuzzer_register(sqlite3 *db){ - int rc = SQLITE_OK; -#ifndef SQLITE_OMIT_VIRTUALTABLE - rc = sqlite3_create_module(db, "fuzzer", &fuzzerModule, 0); -#endif - return rc; -} - -#ifdef SQLITE_TEST -#include <tcl.h> -/* -** Decode a pointer to an sqlite3 object. -*/ -extern int getDbPointer(Tcl_Interp *interp, const char *zA, sqlite3 **ppDb); - -/* -** Register the echo virtual table module. -*/ -static int register_fuzzer_module( - ClientData clientData, /* Pointer to sqlite3_enable_XXX function */ - Tcl_Interp *interp, /* The TCL interpreter that invoked this command */ - int objc, /* Number of arguments */ - Tcl_Obj *CONST objv[] /* Command arguments */ -){ - sqlite3 *db; - if( objc!=2 ){ - Tcl_WrongNumArgs(interp, 1, objv, "DB"); - return TCL_ERROR; - } - getDbPointer(interp, Tcl_GetString(objv[1]), &db); - fuzzer_register(db); - return TCL_OK; -} - - -/* -** Register commands with the TCL interpreter. -*/ -int Sqlitetestfuzzer_Init(Tcl_Interp *interp){ - static struct { - char *zName; - Tcl_ObjCmdProc *xProc; - void *clientData; - } aObjCmd[] = { - { "register_fuzzer_module", register_fuzzer_module, 0 }, - }; - int i; - for(i=0; i<sizeof(aObjCmd)/sizeof(aObjCmd[0]); i++){ - Tcl_CreateObjCommand(interp, aObjCmd[i].zName, - aObjCmd[i].xProc, aObjCmd[i].clientData, 0); - } - return TCL_OK; -} - -#endif /* SQLITE_TEST */ |