/*

** 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.

*/

#include "sqlite3ext.h"

SQLITE_EXTENSION_INIT1

/* If SQLITE_DEBUG is not defined, disable assert statements. */

#if !defined(NDEBUG) && !defined(SQLITE_DEBUG)

# define NDEBUG

#endif

#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. */