SQLite

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 {

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

  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;
}

/*

  pNew = sqlite3_malloc( sizeof(*pNew) + strlen(zWord) + 1 );
  if( pNew==0 ) return 0;
  memset(pNew, 0, sizeof(*pNew));
  pNew->zBasis = (char*)&pNew[1];
  pNew->nBasis = 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];

    }
  }

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

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

  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.

ifcapable !vtab {
  finish_test
  return
}

set ::testprefix fuzzer1

# Test of test code. Only here to make the coverage metric better.
do_test 0.1 {
  list [catch { register_fuzzer_module a b c } msg] $msg
} {1 {wrong # args: should be "register_fuzzer_module DB"}}

register_fuzzer_module db

# Check configuration errors.
#
do_catchsql_test fuzzer1-1.1 {
  CREATE VIRTUAL TABLE f USING fuzzer;
} {1 {fuzzer: wrong number of CREATE VIRTUAL TABLE arguments}}

  SELECT word FROM x3 WHERE ruleset=1 AND word MATCH 'a' ORDER BY word ASC;
} {a t u v}

do_execsql_test 8.2.14 {
  SELECT word FROM x3 WHERE ruleset=1 AND word MATCH 'a' ORDER BY word DESC;
} {v u t a}

#-------------------------------------------------------------------------
#
do_execsql_test 9.1 {
  CREATE TABLE x4_rules(a, b, c, d);
  INSERT INTO x4_rules VALUES(0, 'a', 'b', 10);
  INSERT INTO x4_rules VALUES(0, 'a', 'c', 11);
  INSERT INTO x4_rules VALUES(0, 'bx', 'zz', 20);
  INSERT INTO x4_rules VALUES(0, 'cx', 'yy', 15);
  INSERT INTO x4_rules VALUES(0, 'zz', '!!', 50);
  CREATE VIRTUAL TABLE x4 USING fuzzer(x4_rules);
}

do_execsql_test 9.2 {
  SELECT word, distance FROM x4 WHERE word MATCH 'ax';
} {ax 0 bx 10 cx 11 yy 26 zz 30 !! 80}


do_execsql_test 10.1 {
  CREATE TABLE x5_rules(a, b, c, d);
  CREATE VIRTUAL TABLE x5 USING fuzzer(x5_rules);
}

do_execsql_test 10.2 {
  SELECT word, distance FROM x5 WHERE word MATCH 
    'aaaaaaaaaXaaaaaaaaaXaaaaaaaaaXaaaaaaaaaXaaaaaaaaa' || 
    'aaaaaaaaaXaaaaaaaaaXaaaaaaaaaXaaaaaaaaaXaaaaaaaaa' || 
    'aaaaaaaaaXaaaaaaaaaXaaaaaaaaaXaaaaaaaaaXaaaaaaaaa'
} {}

do_execsql_test 10.3 {
  INSERT INTO x5_rules VALUES(0, 'a', '0.1.2.3.4.5.6.7.8.9.a', 1);
  DROP TABLE x5;
  CREATE VIRTUAL TABLE x5 USING fuzzer(x5_rules);
  SELECT length(word) FROM x5 WHERE word MATCH 'a' LIMIT 50;
} {1 21 41 61 81}

finish_test

    CREATE TABLE x1_rules(ruleset, cFrom, cTo, cost);
    INSERT INTO x1_rules VALUES(0, 'a', 'b', 1);
    INSERT INTO x1_rules VALUES(0, 'a', 'c', 2);
    INSERT INTO x1_rules VALUES(0, 'a', 'd', 3);
  }
  faultsim_save_and_close
} {}

do_faultsim_test 1 -prep {
  faultsim_restore_and_reopen
  register_fuzzer_module db
} -body {
  execsql { 
    CREATE VIRTUAL TABLE x1 USING fuzzer(x1_rules);
    SELECT word FROM x1 WHERE word MATCH 'xax';
  }
} -test {
  faultsim_test_result {0 {xax xbx xcx xdx}}               \
                       {1 {vtable constructor failed: x1}}
}

do_test 2-pre1 {
  faultsim_delete_and_reopen
  register_fuzzer_module db
  execsql {
    CREATE TABLE x2_rules(ruleset, cFrom, cTo, cost);
    INSERT INTO x2_rules VALUES(0, 'a', 'x', 1);
    INSERT INTO x2_rules VALUES(0, 'b', 'x', 2);
    INSERT INTO x2_rules VALUES(0, 'c', 'x', 3);
    CREATE VIRTUAL TABLE x2 USING fuzzer(x2_rules);
  }
  faultsim_save_and_close
} {}

do_faultsim_test 2 -prep {
  faultsim_restore_and_reopen
  register_fuzzer_module db
} -body {
  execsql { 
    SELECT count(*) FROM x2 WHERE word MATCH 'abc';
  }
} -test {
  faultsim_test_result {0 8} {1 {vtable constructor failed: x2}}
}

do_test 3-pre1 {
  faultsim_delete_and_reopen
  execsql {
    CREATE TABLE x1_rules(ruleset, cFrom, cTo, cost);
    INSERT INTO x1_rules VALUES(0, 'a', 
      '123456789012345678901234567890a1234567890123456789', 10
    );
  }
  faultsim_save_and_close
} {}

do_faultsim_test 3 -prep {
  faultsim_restore_and_reopen
  register_fuzzer_module db
} -body {
  execsql { 
    CREATE VIRTUAL TABLE x1 USING fuzzer(x1_rules);
    SELECT count(*) FROM (SELECT * FROM x1 WHERE word MATCH 'a' LIMIT 2);
  }
} -test {
  faultsim_test_result {0 2} {1 {vtable constructor failed: x1}}
}


finish_test