[sql] Import reference version of SQLite 3.8.7.4.

third_party/sqlite/sqlite-src-3080704/ext/misc/fuzzer.c

 /*
 ** 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 demonstartion virtual table that generates variations
+** 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 temp.f USING fuzzer;
+**     CREATE VIRTUAL TABLE f USING fuzzer(<fuzzer-data-table>);
 **
-** The name of the new virtual table in the example above is "f".
-** Note that all fuzzer virtual tables must be TEMP tables.  The
-** "temp." prefix in front of the table name is required when the
-** table is being created.  The "temp." prefix can be omitted when
-** using the table as long as the name is unambiguous.
+** 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.
 **
-** Before being used, the fuzzer needs to be programmed by giving it
-** character transformations and a cost associated with each transformation.
-** Examples:
+** 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. 
 **
-**    INSERT INTO f(cFrom,cTo,Cost) VALUES('','a',100);
+** 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:
 **
-** The above statement says 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.)
+**    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);
 **
-**    INSERT INTO f(cFrom,cTo,Cost) VALUES('b','',87);
-**
-** The above statement says that the cost of deleting a single letter
-** 'b' is 87.
-**
-**    INSERT INTO f(cFrom,cTo,Cost) VALUES('o','oe',38);
-**    INSERT INTO f(cFrom,cTo,Cost) VALUES('oe','o',40);
-**
-** This third example says that the cost of transforming the single
-** letter "o" into the two-letter sequence "oe" is 38 and that the
+** 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.
 **
-** After all the transformation costs have been set, the fuzzer table
-** can be queried as follows:
+** 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.
@@ skipping 12 matching lines @@
 ** 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 "sqlite3.h"
+#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;
 
 /*
-** Type of the "cost" of an edit operation.  Might be changed to
-** "float" or "double" or "sqlite3_int64" in the future.
+** 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 */
-  fuzzer_cost rCost;         /* Cost of this transformation */
-  int nFrom, nTo;            /* Length of the zFrom and zTo strings */
-  char *zFrom;               /* Transform from */
-  char zTo[4];               /* Transform to (extra space appended) */
+  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 */
-  int nBasis;                /* Length of the zBasis string */
   const fuzzer_rule *pRule;  /* Current rule to apply */
-  int n;                     /* Apply pRule at this character offset */
+  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_stem *pNext;        /* Next stem in rCost order */
-  fuzzer_stem *pHash;        /* Next stem with same hash on zBasis */
+  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 */
-  fuzzer_rule *pNewRule;     /* New rules to add when last cursor expires */
   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 */
 };
 
-/* Methods for the fuzzer module */
-static int fuzzerConnect(
-  sqlite3 *db,
-  void *pAux,
-  int argc, const char *const*argv,
-  sqlite3_vtab **ppVtab,
-  char **pzErr
-){
-  fuzzer_vtab *pNew;
-  int n;
-  if( strcmp(argv[1],"temp")!=0 ){
-    *pzErr = sqlite3_mprintf("%s virtual tables must be TEMP", argv[0]);
-    return SQLITE_ERROR;
-  }
-  n = strlen(argv[0]) + 1;
-  pNew = sqlite3_malloc( sizeof(*pNew) + n );
-  if( pNew==0 ) return SQLITE_NOMEM;
-  pNew->zClassName = (char*)&pNew[1];
-  memcpy(pNew->zClassName, argv[0], n);
-  sqlite3_declare_vtab(db, "CREATE TABLE x(word,distance,cFrom,cTo,cost)");
-  memset(pNew, 0, sizeof(*pNew));
-  *ppVtab = &pNew->base;
-  return SQLITE_OK;
-}
-/* Note that for this virtual table, the xCreate and xConnect
-** methods are identical. */
-
-static int fuzzerDisconnect(sqlite3_vtab *pVtab){
-  fuzzer_vtab *p = (fuzzer_vtab*)pVtab;
-  assert( p->nCursor==0 );
-  do{
-    while( p->pRule ){
-      fuzzer_rule *pRule = p->pRule;
-      p->pRule = pRule->pNext;
-      sqlite3_free(pRule);
-    }
-    p->pRule = p->pNewRule;
-    p->pNewRule = 0;
-  }while( p->pRule );
-  sqlite3_free(p);
-  return SQLITE_OK;
-}
-/* The xDisconnect and xDestroy methods are also the same */
-
 /*
 ** 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;
+}
 
 /*
-** Open a new fuzzer cursor.
+** Load the content of the fuzzer data table into memory.
 */
-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;
-  if( p->nCursor==0 && p->pNewRule ){
+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 = p->pNewRule)!=0 ){
-      p->pNewRule = pX->pNext;
+    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;
@@ skipping 36 matching lines @@
 
 /*
 ** 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;
-  char *z;
+  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;
@@ skipping 42 matching lines @@
 */
 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 ){
+  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;
-    pStem->pRule = pRule->pNext;
-    if( pStem->pRule && fuzzerCost(pStem)>pCur->rLimit ) pStem->pRule = 0;
+    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){
@@ skipping 97 matching lines @@
 /*
 ** 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) + strlen(zWord) + 1 );
+  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 = strlen(zWord);
+  pNew->nBasis = (int)strlen(zWord);
   memcpy(pNew->zBasis, zWord, pNew->nBasis+1);
-  pNew->pRule = pCur->pVtab->pRule;
+  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;
 }
 
 
@@ skipping 26 matching lines @@
       }
     }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 ){
-    if( fuzzerAdvance(pCur, pStem) ){
+    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;
@@ skipping 17 matching lines @@
 ** 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 = 0;
+  const char *zWord = "";
   fuzzer_stem *pStem;
+  int idx;
 
   fuzzerClearCursor(pCur, 1);
   pCur->rLimit = 2147483647;
-  if( idxNum==1 ){
+  idx = 0;
+  if( idxNum & 1 ){
     zWord = (const char*)sqlite3_value_text(argv[0]);
-  }else if( idxNum==2 ){
-    pCur->rLimit = (fuzzer_cost)sqlite3_value_int(argv[0]);
-  }else if( idxNum==3 ){
-    zWord = (const char*)sqlite3_value_text(argv[0]);
-    pCur->rLimit = (fuzzer_cost)sqlite3_value_int(argv[1]);
+    idx++;
   }
-  if( zWord==0 ) zWord = "";
-  pCur->pStem = pStem = fuzzerNewStem(pCur, zWord, (fuzzer_cost)0);
-  if( pStem==0 ) return SQLITE_NOMEM;
+  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 = "";
-  pStem->pRule = &pCur->nullRule;
-  pStem->n = pStem->nBasis;
   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 ){
@@ skipping 26 matching lines @@
 ** 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:
 **
-**       word MATCH $str
-**       distance < $value
-**       distance <= $value
+**   (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 as follows:
+** The query plan number is a bit vector:
 **
-**   0:    None of the terms above are found
-**   1:    There is a "word MATCH" term with $str in filter.argv[0].
-**   2:    There is a "distance<" term with $value in filter.argv[0].
-**   3:    Both "word MATCH" and "distance<" with $str in argv[0] and
-**         $value in argv[1].
+**   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;
+  int seenMatch = 0;
   const struct sqlite3_index_constraint *pConstraint;
+  double rCost = 1e12;
+
   pConstraint = pIdxInfo->aConstraint;
   for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
+    if( pConstraint->iColumn==0
+     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH ){
+      seenMatch = 1;
+    }
     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;
+      rCost /= 1e6;
     }
     if( (iPlan & 2)==0
      && pConstraint->iColumn==1
      && (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT
            || pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE)
     ){
       iPlan |= 2;
       iDistTerm = i;
+      rCost /= 10.0;
+    }
+    if( (iPlan & 4)==0
+     && pConstraint->iColumn==2
+     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
+    ){
+      iPlan |= 4;
+      pIdxInfo->aConstraintUsage[i].omit = 1;
+      iRulesetTerm = i;
+      rCost /= 10.0;
     }
   }
-  if( iPlan==2 ){
-    pIdxInfo->aConstraintUsage[iDistTerm].argvIndex = 1;
-  }else if( iPlan==3 ){
-    pIdxInfo->aConstraintUsage[iDistTerm].argvIndex = 2;
+  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;
+  if( seenMatch && (iPlan&1)==0 ) rCost = 1e99;
+  pIdxInfo->estimatedCost = rCost;
    
   return SQLITE_OK;
 }
 
 /*
-** Disallow all attempts to DELETE or UPDATE.  Only INSERTs are allowed.
-**
-** On an insert, the cFrom, cTo, and cost columns are used to construct
-** a new rule.   All other columns are ignored.  The rule is ignored
-** if cFrom and cTo are identical.  A NULL value for cFrom or cTo is
-** interpreted as an empty string.  The cost must be positive.
-*/
-static int fuzzerUpdate(
-  sqlite3_vtab *pVTab,
-  int argc,
-  sqlite3_value **argv,
-  sqlite_int64 *pRowid
-){
-  fuzzer_vtab *p = (fuzzer_vtab*)pVTab;
-  fuzzer_rule *pRule;
-  const char *zFrom;
-  int nFrom;
-  const char *zTo;
-  int nTo;
-  fuzzer_cost rCost;
-  if( argc!=7 ){
-    sqlite3_free(pVTab->zErrMsg);
-    pVTab->zErrMsg = sqlite3_mprintf("cannot delete from a %s virtual table",
-                                     p->zClassName);
-    return SQLITE_CONSTRAINT;
-  }
-  if( sqlite3_value_type(argv[0])!=SQLITE_NULL ){
-    sqlite3_free(pVTab->zErrMsg);
-    pVTab->zErrMsg = sqlite3_mprintf("cannot update a %s virtual table",
-                                     p->zClassName);
-    return SQLITE_CONSTRAINT;
-  }
-  zFrom = (char*)sqlite3_value_text(argv[4]);
-  if( zFrom==0 ) zFrom = "";
-  zTo = (char*)sqlite3_value_text(argv[5]);
-  if( zTo==0 ) zTo = "";
-  if( strcmp(zFrom,zTo)==0 ){
-    /* Silently ignore null transformations */
-    return SQLITE_OK;
-  }
-  rCost = sqlite3_value_int(argv[6]);
-  if( rCost<=0 ){
-    sqlite3_free(pVTab->zErrMsg);
-    pVTab->zErrMsg = sqlite3_mprintf("cost must be positive");
-    return SQLITE_CONSTRAINT;    
-  }
-  nFrom = strlen(zFrom);
-  nTo = strlen(zTo);
-  pRule = sqlite3_malloc( sizeof(*pRule) + nFrom + nTo );
-  if( pRule==0 ){
-    return SQLITE_NOMEM;
-  }
-  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 = rCost;
-  pRule->pNext = p->pNewRule;
-  p->pNewRule = pRule;
-  return SQLITE_OK;
-}
-
-/*
-** A virtual table module that provides read-only access to a
-** Tcl global variable namespace.
+** 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 */
-  fuzzerUpdate,                /* xUpdate - INSERT */
+  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){
+#ifdef _WIN32
+__declspec(dllexport)
+#endif
+int sqlite3_fuzzer_init(
+  sqlite3 *db, 
+  char **pzErrMsg, 
+  const sqlite3_api_routines *pApi
+){
   int rc = SQLITE_OK;
+  SQLITE_EXTENSION_INIT2(pApi);
 #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;
-  }
-  if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;
-  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 */