SQLite

Check-in [dd41155bc7]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:The first simple test-case appears to be working now.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | word-fuzzer
Files: files | file ages | folders
SHA1: dd41155bc7459cafc1a2d5c75233193abfbac05d
User & Date: drh 2011-03-29 18:21:59.753
Context
2011-03-29
23:41
Add support for rowid. (check-in: 2cf4158ff0 user: drh tags: word-fuzzer)
18:21
The first simple test-case appears to be working now. (check-in: dd41155bc7 user: drh tags: word-fuzzer)
14:08
Further improvements to the fuzzer. It still is not quite working. Pausing to work on other things.... (check-in: 5f2f2fce40 user: drh tags: word-fuzzer)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/test_fuzzer.c.
251
252
253
254
255
256
257



258
259
260
261

262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281





























282
283
284
285
286
287
288
  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;







>
>
>
|
|
|
|
>


<

















>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267

268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
  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);
  }
  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;
}

#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, fuzzerCost(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;
311
312
313
314
315
316
317
318


319
320
321
322
323
324
325
      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;







|
>
>







343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
      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;
413
414
415
416
417
418
419
420
421
422
423
424
425
426

427
428
429
430







431
432
433
434
435
436
437
  }

  /* 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
  ** nothing left to be output. */
  pCur->rLimit = (fuzzer_cost)0;
  return SQLITE_OK;
}







|
|


<
<

>




>
>
>
>
>
>
>







447
448
449
450
451
452
453
454
455
456
457


458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
  }

  /* 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 = pStem = fuzzerInsert(pStem->pNext, pStem);
      if( (rc = fuzzerSeen(pCur, pStem))!=0 ){
        if( rc<0 ) return SQLITE_NOMEM;
        continue;


      }
      return SQLITE_OK;  /* New word found */
    }
    pCur->pStem = pStem->pNext;
    pStem->pNext = pCur->pDone;
    pCur->pDone = pStem;
    if( pCur->pStem ){
      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;
}
Changes to test/fuzzer1.test.
37
38
39
40
41
42
43
44
45
46
47
  }
} {}

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


finish_test







|



37
38
39
40
41
42
43
44
45
46
47
  }
} {}

do_test fuzzer1-1.3 {
  db eval {
    SELECT word, distance FROM f1 WHERE word MATCH 'abcde'
  }
} {abcde 0 abcda 1 ebcde 10 ebcda 11 abcdo 100 ebcdo 110 obcde 110 obcda 111 obcdo 210}


finish_test