SQLite

** Code for demonstartion virtual table that generates variations
** on an input word at increasing edit distances from the original.
*/
#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;

  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) */
};

/*
** 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_cost rBaseCost;     /* Base cost of getting to zBasis */

  sqlite3_vtab_cursor base;  /* Base class - must be first */
  fuzzer_vtab *pVtab;        /* The virtual table this cursor belongs to */
  fuzzer_cost rLimit;        /* Maximum cost of any term */
  fuzzer_stem *pStem;        /* Sorted list of stems for generating new terms */
  fuzzer_stem *pDone;        /* Stems already processed to completion */
  char *zBuf;                /* Temporary use buffer */
  int nBuf;                  /* Bytes allocated for zBuf */
  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,

  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 ){
    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;
      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);
  }
  p->nCursor++;
  return SQLITE_OK;
}

/*
** Free up all the memory allocated by a cursor.  Set it rLimit to 0
** to indicate that it is at EOF.
*/

** 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;
  char *z;

  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;

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

  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->rBaseCost + pStem->pRule->rCost;
}

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

/*
** 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 ){
    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 ) return 1;  
      }
    }
    pStem->n = -1;
    pStem->pRule = pRule->pNext;
    if( pStem->pRule && fuzzerCost(pStem)>pCur->rLimit ) pStem->pRule = 0;
  }
  return 0;
}

/*
** Insert pNew into the list at pList.  Return a pointer to the new
** 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_stem *pList, fuzzer_stem *pNew){
  fuzzer_cost c1;

  if( pList==0 ){
    pNew->pNext = 0;
    return pNew;
  }
  c1 = fuzzerCost(pNew);
  if( c1 <= fuzzerCost(pList) ){
    pNew->pNext = pList;
    return pNew;
  }else{
    fuzzer_stem *pPrev;
    pPrev = pList;

}


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

  /* 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( fuzzerCost(pStem)>0 ){
    rc = fuzzerRender(pStem, &pCur->zBuf, &pCur->nBuf);
    if( rc==SQLITE_NOMEM ) return SQLITE_NOMEM;
    pNew = fuzzerNewStem(pCur, pCur->zBuf, fuzzerCost(pStem));
    if( pNew ){
      if( fuzzerAdvance(pCur, pNew)==0 ){
        pNew->pNext = pCur->pDone;
        pCur->pDone = pNew;
      }else{
        pCur->pStem = fuzzerInsert(pStem, pNew);
        if( pCur->pStem==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 ){
    if( fuzzerAdvance(pCur, pStem) ){
      pCur->pStem = fuzzerInsert(pStem->pNext, pStem);
      if( pCur->pStem!=pStem && (rc = fuzzerSeen(pCur, pStem))!=0 ){
        if( rc<0 ) return SQLITE_NOMEM;
        continue;
      }else{
        return SQLITE_OK;  /* New word found */
      }
    }
    pCur->pStem = pStem->pNext;
    pStem->pNext = pCur->pDone;
    pCur->pDone = pStem;
  }

  /* Reach this point only if queue has been exhausted and there is

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;
  fuzzer_stem *pStem;

  fuzzerClearCursor(pCur, 1);
  pCur->rLimit = 2147483647;
  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]);
  }
  if( zWord==0 ) zWord = "";
  pCur->pStem = pStem = fuzzerNewStem(pCur, zWord, (fuzzer_cost)0);
  if( pStem==0 ) return SQLITE_NOMEM;
  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;
  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, fuzzerCost(pCur->pStem));
  }else{

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

} {1 {fuzzer virtual tables must be TEMP}}
do_test fuzzer1-1.1 {
  db eval {CREATE VIRTUAL TABLE temp.f1 USING fuzzer;}
} {}
do_test fuzzer1-1.2 {
  db eval {
    INSERT INTO f1(cfrom, cto, cost) VALUES('e','a',1);
    INSERT INTO f1(cfrom, cto, cost) VALUES('a','e',10);
    INSERT INTO f1(cfrom, cto, cost) VALUES('e','o',100);
  }
} {}

do_test fuzzer1-1.3 {
  db eval {
    SELECT word, distance FROM f1 WHERE word MATCH 'abcde'
  }