Merge tag 'upstream/2.2.1'

Upstream version 2.2.1
# gpg: Signature made Tue 13 Aug 2013 03:42:56 PM EDT using RSA key ID 374BBE81
# gpg: Good signature from "Hans-Christoph Steiner <hans@at.or.at>"
# gpg:                 aka "[jpeg image of size 5408]"
# gpg:                 aka "Hans-Christoph Steiner <hs420@nyu.edu>"
# gpg:                 aka "Hans-Christoph Steiner <hans@eds.org>"
# gpg:                 aka "Hans-Christoph Steiner <hans@guardianproject.info>"
# gpg:                 aka "Hans-Christoph Steiner <hansi@nyu.edu>"
# gpg:                 aka "Hans-Christoph Steiner <hans@guardianproject.info>"

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