Annotation of embedaddon/sqlite3/src/test_fuzzer.c, revision 1.1.1.1
1.1 misho 1: /*
2: ** 2011 March 24
3: **
4: ** The author disclaims copyright to this source code. In place of
5: ** a legal notice, here is a blessing:
6: **
7: ** May you do good and not evil.
8: ** May you find forgiveness for yourself and forgive others.
9: ** May you share freely, never taking more than you give.
10: **
11: *************************************************************************
12: **
13: ** Code for demonstartion virtual table that generates variations
14: ** on an input word at increasing edit distances from the original.
15: **
16: ** A fuzzer virtual table is created like this:
17: **
18: ** CREATE VIRTUAL TABLE temp.f USING fuzzer;
19: **
20: ** The name of the new virtual table in the example above is "f".
21: ** Note that all fuzzer virtual tables must be TEMP tables. The
22: ** "temp." prefix in front of the table name is required when the
23: ** table is being created. The "temp." prefix can be omitted when
24: ** using the table as long as the name is unambiguous.
25: **
26: ** Before being used, the fuzzer needs to be programmed by giving it
27: ** character transformations and a cost associated with each transformation.
28: ** Examples:
29: **
30: ** INSERT INTO f(cFrom,cTo,Cost) VALUES('','a',100);
31: **
32: ** The above statement says that the cost of inserting a letter 'a' is
33: ** 100. (All costs are integers. We recommend that costs be scaled so
34: ** that the average cost is around 100.)
35: **
36: ** INSERT INTO f(cFrom,cTo,Cost) VALUES('b','',87);
37: **
38: ** The above statement says that the cost of deleting a single letter
39: ** 'b' is 87.
40: **
41: ** INSERT INTO f(cFrom,cTo,Cost) VALUES('o','oe',38);
42: ** INSERT INTO f(cFrom,cTo,Cost) VALUES('oe','o',40);
43: **
44: ** This third example says that the cost of transforming the single
45: ** letter "o" into the two-letter sequence "oe" is 38 and that the
46: ** cost of transforming "oe" back into "o" is 40.
47: **
48: ** After all the transformation costs have been set, the fuzzer table
49: ** can be queried as follows:
50: **
51: ** SELECT word, distance FROM f
52: ** WHERE word MATCH 'abcdefg'
53: ** AND distance<200;
54: **
55: ** This first query outputs the string "abcdefg" and all strings that
56: ** can be derived from that string by appling the specified transformations.
57: ** The strings are output together with their total transformation cost
58: ** (called "distance") and appear in order of increasing cost. No string
59: ** is output more than once. If there are multiple ways to transform the
60: ** target string into the output string then the lowest cost transform is
61: ** the one that is returned. In the example, the search is limited to
62: ** strings with a total distance of less than 200.
63: **
64: ** It is important to put some kind of a limit on the fuzzer output. This
65: ** can be either in the form of a LIMIT clause at the end of the query,
66: ** or better, a "distance<NNN" constraint where NNN is some number. The
67: ** running time and memory requirement is exponential in the value of NNN
68: ** so you want to make sure that NNN is not too big. A value of NNN that
69: ** is about twice the average transformation cost seems to give good results.
70: **
71: ** The fuzzer table can be useful for tasks such as spelling correction.
72: ** Suppose there is a second table vocabulary(w) where the w column contains
73: ** all correctly spelled words. Let $word be a word you want to look up.
74: **
75: ** SELECT vocabulary.w FROM f, vocabulary
76: ** WHERE f.word MATCH $word
77: ** AND f.distance<=200
78: ** AND f.word=vocabulary.w
79: ** LIMIT 20
80: **
81: ** The query above gives the 20 closest words to the $word being tested.
82: ** (Note that for good performance, the vocubulary.w column should be
83: ** indexed.)
84: **
85: ** A similar query can be used to find all words in the dictionary that
86: ** begin with some prefix $prefix:
87: **
88: ** SELECT vocabulary.w FROM f, vocabulary
89: ** WHERE f.word MATCH $prefix
90: ** AND f.distance<=200
91: ** AND vocabulary.w BETWEEN f.word AND (f.word || x'F7BFBFBF')
92: ** LIMIT 50
93: **
94: ** This last query will show up to 50 words out of the vocabulary that
95: ** match or nearly match the $prefix.
96: */
97: #include "sqlite3.h"
98: #include <stdlib.h>
99: #include <string.h>
100: #include <assert.h>
101: #include <stdio.h>
102:
103: #ifndef SQLITE_OMIT_VIRTUALTABLE
104:
105: /*
106: ** Forward declaration of objects used by this implementation
107: */
108: typedef struct fuzzer_vtab fuzzer_vtab;
109: typedef struct fuzzer_cursor fuzzer_cursor;
110: typedef struct fuzzer_rule fuzzer_rule;
111: typedef struct fuzzer_seen fuzzer_seen;
112: typedef struct fuzzer_stem fuzzer_stem;
113:
114: /*
115: ** Type of the "cost" of an edit operation. Might be changed to
116: ** "float" or "double" or "sqlite3_int64" in the future.
117: */
118: typedef int fuzzer_cost;
119:
120:
121: /*
122: ** Each transformation rule is stored as an instance of this object.
123: ** All rules are kept on a linked list sorted by rCost.
124: */
125: struct fuzzer_rule {
126: fuzzer_rule *pNext; /* Next rule in order of increasing rCost */
127: fuzzer_cost rCost; /* Cost of this transformation */
128: int nFrom, nTo; /* Length of the zFrom and zTo strings */
129: char *zFrom; /* Transform from */
130: char zTo[4]; /* Transform to (extra space appended) */
131: };
132:
133: /*
134: ** A stem object is used to generate variants. It is also used to record
135: ** previously generated outputs.
136: **
137: ** Every stem is added to a hash table as it is output. Generation of
138: ** duplicate stems is suppressed.
139: **
140: ** Active stems (those that might generate new outputs) are kepts on a linked
141: ** list sorted by increasing cost. The cost is the sum of rBaseCost and
142: ** pRule->rCost.
143: */
144: struct fuzzer_stem {
145: char *zBasis; /* Word being fuzzed */
146: int nBasis; /* Length of the zBasis string */
147: const fuzzer_rule *pRule; /* Current rule to apply */
148: int n; /* Apply pRule at this character offset */
149: fuzzer_cost rBaseCost; /* Base cost of getting to zBasis */
150: fuzzer_cost rCostX; /* Precomputed rBaseCost + pRule->rCost */
151: fuzzer_stem *pNext; /* Next stem in rCost order */
152: fuzzer_stem *pHash; /* Next stem with same hash on zBasis */
153: };
154:
155: /*
156: ** A fuzzer virtual-table object
157: */
158: struct fuzzer_vtab {
159: sqlite3_vtab base; /* Base class - must be first */
160: char *zClassName; /* Name of this class. Default: "fuzzer" */
161: fuzzer_rule *pRule; /* All active rules in this fuzzer */
162: fuzzer_rule *pNewRule; /* New rules to add when last cursor expires */
163: int nCursor; /* Number of active cursors */
164: };
165:
166: #define FUZZER_HASH 4001 /* Hash table size */
167: #define FUZZER_NQUEUE 20 /* Number of slots on the stem queue */
168:
169: /* A fuzzer cursor object */
170: struct fuzzer_cursor {
171: sqlite3_vtab_cursor base; /* Base class - must be first */
172: sqlite3_int64 iRowid; /* The rowid of the current word */
173: fuzzer_vtab *pVtab; /* The virtual table this cursor belongs to */
174: fuzzer_cost rLimit; /* Maximum cost of any term */
175: fuzzer_stem *pStem; /* Stem with smallest rCostX */
176: fuzzer_stem *pDone; /* Stems already processed to completion */
177: fuzzer_stem *aQueue[FUZZER_NQUEUE]; /* Queue of stems with higher rCostX */
178: int mxQueue; /* Largest used index in aQueue[] */
179: char *zBuf; /* Temporary use buffer */
180: int nBuf; /* Bytes allocated for zBuf */
181: int nStem; /* Number of stems allocated */
182: fuzzer_rule nullRule; /* Null rule used first */
183: fuzzer_stem *apHash[FUZZER_HASH]; /* Hash of previously generated terms */
184: };
185:
186: /* Methods for the fuzzer module */
187: static int fuzzerConnect(
188: sqlite3 *db,
189: void *pAux,
190: int argc, const char *const*argv,
191: sqlite3_vtab **ppVtab,
192: char **pzErr
193: ){
194: fuzzer_vtab *pNew;
195: int n;
196: if( strcmp(argv[1],"temp")!=0 ){
197: *pzErr = sqlite3_mprintf("%s virtual tables must be TEMP", argv[0]);
198: return SQLITE_ERROR;
199: }
200: n = strlen(argv[0]) + 1;
201: pNew = sqlite3_malloc( sizeof(*pNew) + n );
202: if( pNew==0 ) return SQLITE_NOMEM;
203: pNew->zClassName = (char*)&pNew[1];
204: memcpy(pNew->zClassName, argv[0], n);
205: sqlite3_declare_vtab(db, "CREATE TABLE x(word,distance,cFrom,cTo,cost)");
206: memset(pNew, 0, sizeof(*pNew));
207: *ppVtab = &pNew->base;
208: return SQLITE_OK;
209: }
210: /* Note that for this virtual table, the xCreate and xConnect
211: ** methods are identical. */
212:
213: static int fuzzerDisconnect(sqlite3_vtab *pVtab){
214: fuzzer_vtab *p = (fuzzer_vtab*)pVtab;
215: assert( p->nCursor==0 );
216: do{
217: while( p->pRule ){
218: fuzzer_rule *pRule = p->pRule;
219: p->pRule = pRule->pNext;
220: sqlite3_free(pRule);
221: }
222: p->pRule = p->pNewRule;
223: p->pNewRule = 0;
224: }while( p->pRule );
225: sqlite3_free(p);
226: return SQLITE_OK;
227: }
228: /* The xDisconnect and xDestroy methods are also the same */
229:
230: /*
231: ** The two input rule lists are both sorted in order of increasing
232: ** cost. Merge them together into a single list, sorted by cost, and
233: ** return a pointer to the head of that list.
234: */
235: static fuzzer_rule *fuzzerMergeRules(fuzzer_rule *pA, fuzzer_rule *pB){
236: fuzzer_rule head;
237: fuzzer_rule *pTail;
238:
239: pTail = &head;
240: while( pA && pB ){
241: if( pA->rCost<=pB->rCost ){
242: pTail->pNext = pA;
243: pTail = pA;
244: pA = pA->pNext;
245: }else{
246: pTail->pNext = pB;
247: pTail = pB;
248: pB = pB->pNext;
249: }
250: }
251: if( pA==0 ){
252: pTail->pNext = pB;
253: }else{
254: pTail->pNext = pA;
255: }
256: return head.pNext;
257: }
258:
259:
260: /*
261: ** Open a new fuzzer cursor.
262: */
263: static int fuzzerOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
264: fuzzer_vtab *p = (fuzzer_vtab*)pVTab;
265: fuzzer_cursor *pCur;
266: pCur = sqlite3_malloc( sizeof(*pCur) );
267: if( pCur==0 ) return SQLITE_NOMEM;
268: memset(pCur, 0, sizeof(*pCur));
269: pCur->pVtab = p;
270: *ppCursor = &pCur->base;
271: if( p->nCursor==0 && p->pNewRule ){
272: unsigned int i;
273: fuzzer_rule *pX;
274: fuzzer_rule *a[15];
275: for(i=0; i<sizeof(a)/sizeof(a[0]); i++) a[i] = 0;
276: while( (pX = p->pNewRule)!=0 ){
277: p->pNewRule = pX->pNext;
278: pX->pNext = 0;
279: for(i=0; a[i] && i<sizeof(a)/sizeof(a[0])-1; i++){
280: pX = fuzzerMergeRules(a[i], pX);
281: a[i] = 0;
282: }
283: a[i] = fuzzerMergeRules(a[i], pX);
284: }
285: for(pX=a[0], i=1; i<sizeof(a)/sizeof(a[0]); i++){
286: pX = fuzzerMergeRules(a[i], pX);
287: }
288: p->pRule = fuzzerMergeRules(p->pRule, pX);
289: }
290: p->nCursor++;
291: return SQLITE_OK;
292: }
293:
294: /*
295: ** Free all stems in a list.
296: */
297: static void fuzzerClearStemList(fuzzer_stem *pStem){
298: while( pStem ){
299: fuzzer_stem *pNext = pStem->pNext;
300: sqlite3_free(pStem);
301: pStem = pNext;
302: }
303: }
304:
305: /*
306: ** Free up all the memory allocated by a cursor. Set it rLimit to 0
307: ** to indicate that it is at EOF.
308: */
309: static void fuzzerClearCursor(fuzzer_cursor *pCur, int clearHash){
310: int i;
311: fuzzerClearStemList(pCur->pStem);
312: fuzzerClearStemList(pCur->pDone);
313: for(i=0; i<FUZZER_NQUEUE; i++) fuzzerClearStemList(pCur->aQueue[i]);
314: pCur->rLimit = (fuzzer_cost)0;
315: if( clearHash && pCur->nStem ){
316: pCur->mxQueue = 0;
317: pCur->pStem = 0;
318: pCur->pDone = 0;
319: memset(pCur->aQueue, 0, sizeof(pCur->aQueue));
320: memset(pCur->apHash, 0, sizeof(pCur->apHash));
321: }
322: pCur->nStem = 0;
323: }
324:
325: /*
326: ** Close a fuzzer cursor.
327: */
328: static int fuzzerClose(sqlite3_vtab_cursor *cur){
329: fuzzer_cursor *pCur = (fuzzer_cursor *)cur;
330: fuzzerClearCursor(pCur, 0);
331: sqlite3_free(pCur->zBuf);
332: pCur->pVtab->nCursor--;
333: sqlite3_free(pCur);
334: return SQLITE_OK;
335: }
336:
337: /*
338: ** Compute the current output term for a fuzzer_stem.
339: */
340: static int fuzzerRender(
341: fuzzer_stem *pStem, /* The stem to be rendered */
342: char **pzBuf, /* Write results into this buffer. realloc if needed */
343: int *pnBuf /* Size of the buffer */
344: ){
345: const fuzzer_rule *pRule = pStem->pRule;
346: int n;
347: char *z;
348:
349: n = pStem->nBasis + pRule->nTo - pRule->nFrom;
350: if( (*pnBuf)<n+1 ){
351: (*pzBuf) = sqlite3_realloc((*pzBuf), n+100);
352: if( (*pzBuf)==0 ) return SQLITE_NOMEM;
353: (*pnBuf) = n+100;
354: }
355: n = pStem->n;
356: z = *pzBuf;
357: if( n<0 ){
358: memcpy(z, pStem->zBasis, pStem->nBasis+1);
359: }else{
360: memcpy(z, pStem->zBasis, n);
361: memcpy(&z[n], pRule->zTo, pRule->nTo);
362: memcpy(&z[n+pRule->nTo], &pStem->zBasis[n+pRule->nFrom],
363: pStem->nBasis-n-pRule->nFrom+1);
364: }
365: return SQLITE_OK;
366: }
367:
368: /*
369: ** Compute a hash on zBasis.
370: */
371: static unsigned int fuzzerHash(const char *z){
372: unsigned int h = 0;
373: while( *z ){ h = (h<<3) ^ (h>>29) ^ *(z++); }
374: return h % FUZZER_HASH;
375: }
376:
377: /*
378: ** Current cost of a stem
379: */
380: static fuzzer_cost fuzzerCost(fuzzer_stem *pStem){
381: return pStem->rCostX = pStem->rBaseCost + pStem->pRule->rCost;
382: }
383:
384: #if 0
385: /*
386: ** Print a description of a fuzzer_stem on stderr.
387: */
388: static void fuzzerStemPrint(
389: const char *zPrefix,
390: fuzzer_stem *pStem,
391: const char *zSuffix
392: ){
393: if( pStem->n<0 ){
394: fprintf(stderr, "%s[%s](%d)-->self%s",
395: zPrefix,
396: pStem->zBasis, pStem->rBaseCost,
397: zSuffix
398: );
399: }else{
400: char *zBuf = 0;
401: int nBuf = 0;
402: if( fuzzerRender(pStem, &zBuf, &nBuf)!=SQLITE_OK ) return;
403: fprintf(stderr, "%s[%s](%d)-->{%s}(%d)%s",
404: zPrefix,
405: pStem->zBasis, pStem->rBaseCost, zBuf, pStem->,
406: zSuffix
407: );
408: sqlite3_free(zBuf);
409: }
410: }
411: #endif
412:
413: /*
414: ** Return 1 if the string to which the cursor is point has already
415: ** been emitted. Return 0 if not. Return -1 on a memory allocation
416: ** failures.
417: */
418: static int fuzzerSeen(fuzzer_cursor *pCur, fuzzer_stem *pStem){
419: unsigned int h;
420: fuzzer_stem *pLookup;
421:
422: if( fuzzerRender(pStem, &pCur->zBuf, &pCur->nBuf)==SQLITE_NOMEM ){
423: return -1;
424: }
425: h = fuzzerHash(pCur->zBuf);
426: pLookup = pCur->apHash[h];
427: while( pLookup && strcmp(pLookup->zBasis, pCur->zBuf)!=0 ){
428: pLookup = pLookup->pHash;
429: }
430: return pLookup!=0;
431: }
432:
433: /*
434: ** Advance a fuzzer_stem to its next value. Return 0 if there are
435: ** no more values that can be generated by this fuzzer_stem. Return
436: ** -1 on a memory allocation failure.
437: */
438: static int fuzzerAdvance(fuzzer_cursor *pCur, fuzzer_stem *pStem){
439: const fuzzer_rule *pRule;
440: while( (pRule = pStem->pRule)!=0 ){
441: while( pStem->n < pStem->nBasis - pRule->nFrom ){
442: pStem->n++;
443: if( pRule->nFrom==0
444: || memcmp(&pStem->zBasis[pStem->n], pRule->zFrom, pRule->nFrom)==0
445: ){
446: /* Found a rewrite case. Make sure it is not a duplicate */
447: int rc = fuzzerSeen(pCur, pStem);
448: if( rc<0 ) return -1;
449: if( rc==0 ){
450: fuzzerCost(pStem);
451: return 1;
452: }
453: }
454: }
455: pStem->n = -1;
456: pStem->pRule = pRule->pNext;
457: if( pStem->pRule && fuzzerCost(pStem)>pCur->rLimit ) pStem->pRule = 0;
458: }
459: return 0;
460: }
461:
462: /*
463: ** The two input stem lists are both sorted in order of increasing
464: ** rCostX. Merge them together into a single list, sorted by rCostX, and
465: ** return a pointer to the head of that new list.
466: */
467: static fuzzer_stem *fuzzerMergeStems(fuzzer_stem *pA, fuzzer_stem *pB){
468: fuzzer_stem head;
469: fuzzer_stem *pTail;
470:
471: pTail = &head;
472: while( pA && pB ){
473: if( pA->rCostX<=pB->rCostX ){
474: pTail->pNext = pA;
475: pTail = pA;
476: pA = pA->pNext;
477: }else{
478: pTail->pNext = pB;
479: pTail = pB;
480: pB = pB->pNext;
481: }
482: }
483: if( pA==0 ){
484: pTail->pNext = pB;
485: }else{
486: pTail->pNext = pA;
487: }
488: return head.pNext;
489: }
490:
491: /*
492: ** Load pCur->pStem with the lowest-cost stem. Return a pointer
493: ** to the lowest-cost stem.
494: */
495: static fuzzer_stem *fuzzerLowestCostStem(fuzzer_cursor *pCur){
496: fuzzer_stem *pBest, *pX;
497: int iBest;
498: int i;
499:
500: if( pCur->pStem==0 ){
501: iBest = -1;
502: pBest = 0;
503: for(i=0; i<=pCur->mxQueue; i++){
504: pX = pCur->aQueue[i];
505: if( pX==0 ) continue;
506: if( pBest==0 || pBest->rCostX>pX->rCostX ){
507: pBest = pX;
508: iBest = i;
509: }
510: }
511: if( pBest ){
512: pCur->aQueue[iBest] = pBest->pNext;
513: pBest->pNext = 0;
514: pCur->pStem = pBest;
515: }
516: }
517: return pCur->pStem;
518: }
519:
520: /*
521: ** Insert pNew into queue of pending stems. Then find the stem
522: ** with the lowest rCostX and move it into pCur->pStem.
523: ** list. The insert is done such the pNew is in the correct order
524: ** according to fuzzer_stem.zBaseCost+fuzzer_stem.pRule->rCost.
525: */
526: static fuzzer_stem *fuzzerInsert(fuzzer_cursor *pCur, fuzzer_stem *pNew){
527: fuzzer_stem *pX;
528: int i;
529:
530: /* If pCur->pStem exists and is greater than pNew, then make pNew
531: ** the new pCur->pStem and insert the old pCur->pStem instead.
532: */
533: if( (pX = pCur->pStem)!=0 && pX->rCostX>pNew->rCostX ){
534: pNew->pNext = 0;
535: pCur->pStem = pNew;
536: pNew = pX;
537: }
538:
539: /* Insert the new value */
540: pNew->pNext = 0;
541: pX = pNew;
542: for(i=0; i<=pCur->mxQueue; i++){
543: if( pCur->aQueue[i] ){
544: pX = fuzzerMergeStems(pX, pCur->aQueue[i]);
545: pCur->aQueue[i] = 0;
546: }else{
547: pCur->aQueue[i] = pX;
548: break;
549: }
550: }
551: if( i>pCur->mxQueue ){
552: if( i<FUZZER_NQUEUE ){
553: pCur->mxQueue = i;
554: pCur->aQueue[i] = pX;
555: }else{
556: assert( pCur->mxQueue==FUZZER_NQUEUE-1 );
557: pX = fuzzerMergeStems(pX, pCur->aQueue[FUZZER_NQUEUE-1]);
558: pCur->aQueue[FUZZER_NQUEUE-1] = pX;
559: }
560: }
561:
562: return fuzzerLowestCostStem(pCur);
563: }
564:
565: /*
566: ** Allocate a new fuzzer_stem. Add it to the hash table but do not
567: ** link it into either the pCur->pStem or pCur->pDone lists.
568: */
569: static fuzzer_stem *fuzzerNewStem(
570: fuzzer_cursor *pCur,
571: const char *zWord,
572: fuzzer_cost rBaseCost
573: ){
574: fuzzer_stem *pNew;
575: unsigned int h;
576:
577: pNew = sqlite3_malloc( sizeof(*pNew) + strlen(zWord) + 1 );
578: if( pNew==0 ) return 0;
579: memset(pNew, 0, sizeof(*pNew));
580: pNew->zBasis = (char*)&pNew[1];
581: pNew->nBasis = strlen(zWord);
582: memcpy(pNew->zBasis, zWord, pNew->nBasis+1);
583: pNew->pRule = pCur->pVtab->pRule;
584: pNew->n = -1;
585: pNew->rBaseCost = pNew->rCostX = rBaseCost;
586: h = fuzzerHash(pNew->zBasis);
587: pNew->pHash = pCur->apHash[h];
588: pCur->apHash[h] = pNew;
589: pCur->nStem++;
590: return pNew;
591: }
592:
593:
594: /*
595: ** Advance a cursor to its next row of output
596: */
597: static int fuzzerNext(sqlite3_vtab_cursor *cur){
598: fuzzer_cursor *pCur = (fuzzer_cursor*)cur;
599: int rc;
600: fuzzer_stem *pStem, *pNew;
601:
602: pCur->iRowid++;
603:
604: /* Use the element the cursor is currently point to to create
605: ** a new stem and insert the new stem into the priority queue.
606: */
607: pStem = pCur->pStem;
608: if( pStem->rCostX>0 ){
609: rc = fuzzerRender(pStem, &pCur->zBuf, &pCur->nBuf);
610: if( rc==SQLITE_NOMEM ) return SQLITE_NOMEM;
611: pNew = fuzzerNewStem(pCur, pCur->zBuf, pStem->rCostX);
612: if( pNew ){
613: if( fuzzerAdvance(pCur, pNew)==0 ){
614: pNew->pNext = pCur->pDone;
615: pCur->pDone = pNew;
616: }else{
617: if( fuzzerInsert(pCur, pNew)==pNew ){
618: return SQLITE_OK;
619: }
620: }
621: }else{
622: return SQLITE_NOMEM;
623: }
624: }
625:
626: /* Adjust the priority queue so that the first element of the
627: ** stem list is the next lowest cost word.
628: */
629: while( (pStem = pCur->pStem)!=0 ){
630: if( fuzzerAdvance(pCur, pStem) ){
631: pCur->pStem = 0;
632: pStem = fuzzerInsert(pCur, pStem);
633: if( (rc = fuzzerSeen(pCur, pStem))!=0 ){
634: if( rc<0 ) return SQLITE_NOMEM;
635: continue;
636: }
637: return SQLITE_OK; /* New word found */
638: }
639: pCur->pStem = 0;
640: pStem->pNext = pCur->pDone;
641: pCur->pDone = pStem;
642: if( fuzzerLowestCostStem(pCur) ){
643: rc = fuzzerSeen(pCur, pCur->pStem);
644: if( rc<0 ) return SQLITE_NOMEM;
645: if( rc==0 ){
646: return SQLITE_OK;
647: }
648: }
649: }
650:
651: /* Reach this point only if queue has been exhausted and there is
652: ** nothing left to be output. */
653: pCur->rLimit = (fuzzer_cost)0;
654: return SQLITE_OK;
655: }
656:
657: /*
658: ** Called to "rewind" a cursor back to the beginning so that
659: ** it starts its output over again. Always called at least once
660: ** prior to any fuzzerColumn, fuzzerRowid, or fuzzerEof call.
661: */
662: static int fuzzerFilter(
663: sqlite3_vtab_cursor *pVtabCursor,
664: int idxNum, const char *idxStr,
665: int argc, sqlite3_value **argv
666: ){
667: fuzzer_cursor *pCur = (fuzzer_cursor *)pVtabCursor;
668: const char *zWord = 0;
669: fuzzer_stem *pStem;
670:
671: fuzzerClearCursor(pCur, 1);
672: pCur->rLimit = 2147483647;
673: if( idxNum==1 ){
674: zWord = (const char*)sqlite3_value_text(argv[0]);
675: }else if( idxNum==2 ){
676: pCur->rLimit = (fuzzer_cost)sqlite3_value_int(argv[0]);
677: }else if( idxNum==3 ){
678: zWord = (const char*)sqlite3_value_text(argv[0]);
679: pCur->rLimit = (fuzzer_cost)sqlite3_value_int(argv[1]);
680: }
681: if( zWord==0 ) zWord = "";
682: pCur->pStem = pStem = fuzzerNewStem(pCur, zWord, (fuzzer_cost)0);
683: if( pStem==0 ) return SQLITE_NOMEM;
684: pCur->nullRule.pNext = pCur->pVtab->pRule;
685: pCur->nullRule.rCost = 0;
686: pCur->nullRule.nFrom = 0;
687: pCur->nullRule.nTo = 0;
688: pCur->nullRule.zFrom = "";
689: pStem->pRule = &pCur->nullRule;
690: pStem->n = pStem->nBasis;
691: pCur->iRowid = 1;
692: return SQLITE_OK;
693: }
694:
695: /*
696: ** Only the word and distance columns have values. All other columns
697: ** return NULL
698: */
699: static int fuzzerColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
700: fuzzer_cursor *pCur = (fuzzer_cursor*)cur;
701: if( i==0 ){
702: /* the "word" column */
703: if( fuzzerRender(pCur->pStem, &pCur->zBuf, &pCur->nBuf)==SQLITE_NOMEM ){
704: return SQLITE_NOMEM;
705: }
706: sqlite3_result_text(ctx, pCur->zBuf, -1, SQLITE_TRANSIENT);
707: }else if( i==1 ){
708: /* the "distance" column */
709: sqlite3_result_int(ctx, pCur->pStem->rCostX);
710: }else{
711: /* All other columns are NULL */
712: sqlite3_result_null(ctx);
713: }
714: return SQLITE_OK;
715: }
716:
717: /*
718: ** The rowid.
719: */
720: static int fuzzerRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
721: fuzzer_cursor *pCur = (fuzzer_cursor*)cur;
722: *pRowid = pCur->iRowid;
723: return SQLITE_OK;
724: }
725:
726: /*
727: ** When the fuzzer_cursor.rLimit value is 0 or less, that is a signal
728: ** that the cursor has nothing more to output.
729: */
730: static int fuzzerEof(sqlite3_vtab_cursor *cur){
731: fuzzer_cursor *pCur = (fuzzer_cursor*)cur;
732: return pCur->rLimit<=(fuzzer_cost)0;
733: }
734:
735: /*
736: ** Search for terms of these forms:
737: **
738: ** word MATCH $str
739: ** distance < $value
740: ** distance <= $value
741: **
742: ** The distance< and distance<= are both treated as distance<=.
743: ** The query plan number is as follows:
744: **
745: ** 0: None of the terms above are found
746: ** 1: There is a "word MATCH" term with $str in filter.argv[0].
747: ** 2: There is a "distance<" term with $value in filter.argv[0].
748: ** 3: Both "word MATCH" and "distance<" with $str in argv[0] and
749: ** $value in argv[1].
750: */
751: static int fuzzerBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
752: int iPlan = 0;
753: int iDistTerm = -1;
754: int i;
755: const struct sqlite3_index_constraint *pConstraint;
756: pConstraint = pIdxInfo->aConstraint;
757: for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
758: if( pConstraint->usable==0 ) continue;
759: if( (iPlan & 1)==0
760: && pConstraint->iColumn==0
761: && pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH
762: ){
763: iPlan |= 1;
764: pIdxInfo->aConstraintUsage[i].argvIndex = 1;
765: pIdxInfo->aConstraintUsage[i].omit = 1;
766: }
767: if( (iPlan & 2)==0
768: && pConstraint->iColumn==1
769: && (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT
770: || pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE)
771: ){
772: iPlan |= 2;
773: iDistTerm = i;
774: }
775: }
776: if( iPlan==2 ){
777: pIdxInfo->aConstraintUsage[iDistTerm].argvIndex = 1;
778: }else if( iPlan==3 ){
779: pIdxInfo->aConstraintUsage[iDistTerm].argvIndex = 2;
780: }
781: pIdxInfo->idxNum = iPlan;
782: if( pIdxInfo->nOrderBy==1
783: && pIdxInfo->aOrderBy[0].iColumn==1
784: && pIdxInfo->aOrderBy[0].desc==0
785: ){
786: pIdxInfo->orderByConsumed = 1;
787: }
788: pIdxInfo->estimatedCost = (double)10000;
789:
790: return SQLITE_OK;
791: }
792:
793: /*
794: ** Disallow all attempts to DELETE or UPDATE. Only INSERTs are allowed.
795: **
796: ** On an insert, the cFrom, cTo, and cost columns are used to construct
797: ** a new rule. All other columns are ignored. The rule is ignored
798: ** if cFrom and cTo are identical. A NULL value for cFrom or cTo is
799: ** interpreted as an empty string. The cost must be positive.
800: */
801: static int fuzzerUpdate(
802: sqlite3_vtab *pVTab,
803: int argc,
804: sqlite3_value **argv,
805: sqlite_int64 *pRowid
806: ){
807: fuzzer_vtab *p = (fuzzer_vtab*)pVTab;
808: fuzzer_rule *pRule;
809: const char *zFrom;
810: int nFrom;
811: const char *zTo;
812: int nTo;
813: fuzzer_cost rCost;
814: if( argc!=7 ){
815: sqlite3_free(pVTab->zErrMsg);
816: pVTab->zErrMsg = sqlite3_mprintf("cannot delete from a %s virtual table",
817: p->zClassName);
818: return SQLITE_CONSTRAINT;
819: }
820: if( sqlite3_value_type(argv[0])!=SQLITE_NULL ){
821: sqlite3_free(pVTab->zErrMsg);
822: pVTab->zErrMsg = sqlite3_mprintf("cannot update a %s virtual table",
823: p->zClassName);
824: return SQLITE_CONSTRAINT;
825: }
826: zFrom = (char*)sqlite3_value_text(argv[4]);
827: if( zFrom==0 ) zFrom = "";
828: zTo = (char*)sqlite3_value_text(argv[5]);
829: if( zTo==0 ) zTo = "";
830: if( strcmp(zFrom,zTo)==0 ){
831: /* Silently ignore null transformations */
832: return SQLITE_OK;
833: }
834: rCost = sqlite3_value_int(argv[6]);
835: if( rCost<=0 ){
836: sqlite3_free(pVTab->zErrMsg);
837: pVTab->zErrMsg = sqlite3_mprintf("cost must be positive");
838: return SQLITE_CONSTRAINT;
839: }
840: nFrom = strlen(zFrom);
841: nTo = strlen(zTo);
842: pRule = sqlite3_malloc( sizeof(*pRule) + nFrom + nTo );
843: if( pRule==0 ){
844: return SQLITE_NOMEM;
845: }
846: pRule->zFrom = &pRule->zTo[nTo+1];
847: pRule->nFrom = nFrom;
848: memcpy(pRule->zFrom, zFrom, nFrom+1);
849: memcpy(pRule->zTo, zTo, nTo+1);
850: pRule->nTo = nTo;
851: pRule->rCost = rCost;
852: pRule->pNext = p->pNewRule;
853: p->pNewRule = pRule;
854: return SQLITE_OK;
855: }
856:
857: /*
858: ** A virtual table module that provides read-only access to a
859: ** Tcl global variable namespace.
860: */
861: static sqlite3_module fuzzerModule = {
862: 0, /* iVersion */
863: fuzzerConnect,
864: fuzzerConnect,
865: fuzzerBestIndex,
866: fuzzerDisconnect,
867: fuzzerDisconnect,
868: fuzzerOpen, /* xOpen - open a cursor */
869: fuzzerClose, /* xClose - close a cursor */
870: fuzzerFilter, /* xFilter - configure scan constraints */
871: fuzzerNext, /* xNext - advance a cursor */
872: fuzzerEof, /* xEof - check for end of scan */
873: fuzzerColumn, /* xColumn - read data */
874: fuzzerRowid, /* xRowid - read data */
875: fuzzerUpdate, /* xUpdate - INSERT */
876: 0, /* xBegin */
877: 0, /* xSync */
878: 0, /* xCommit */
879: 0, /* xRollback */
880: 0, /* xFindMethod */
881: 0, /* xRename */
882: };
883:
884: #endif /* SQLITE_OMIT_VIRTUALTABLE */
885:
886:
887: /*
888: ** Register the fuzzer virtual table
889: */
890: int fuzzer_register(sqlite3 *db){
891: int rc = SQLITE_OK;
892: #ifndef SQLITE_OMIT_VIRTUALTABLE
893: rc = sqlite3_create_module(db, "fuzzer", &fuzzerModule, 0);
894: #endif
895: return rc;
896: }
897:
898: #ifdef SQLITE_TEST
899: #include <tcl.h>
900: /*
901: ** Decode a pointer to an sqlite3 object.
902: */
903: extern int getDbPointer(Tcl_Interp *interp, const char *zA, sqlite3 **ppDb);
904:
905: /*
906: ** Register the echo virtual table module.
907: */
908: static int register_fuzzer_module(
909: ClientData clientData, /* Pointer to sqlite3_enable_XXX function */
910: Tcl_Interp *interp, /* The TCL interpreter that invoked this command */
911: int objc, /* Number of arguments */
912: Tcl_Obj *CONST objv[] /* Command arguments */
913: ){
914: sqlite3 *db;
915: if( objc!=2 ){
916: Tcl_WrongNumArgs(interp, 1, objv, "DB");
917: return TCL_ERROR;
918: }
919: if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;
920: fuzzer_register(db);
921: return TCL_OK;
922: }
923:
924:
925: /*
926: ** Register commands with the TCL interpreter.
927: */
928: int Sqlitetestfuzzer_Init(Tcl_Interp *interp){
929: static struct {
930: char *zName;
931: Tcl_ObjCmdProc *xProc;
932: void *clientData;
933: } aObjCmd[] = {
934: { "register_fuzzer_module", register_fuzzer_module, 0 },
935: };
936: int i;
937: for(i=0; i<sizeof(aObjCmd)/sizeof(aObjCmd[0]); i++){
938: Tcl_CreateObjCommand(interp, aObjCmd[i].zName,
939: aObjCmd[i].xProc, aObjCmd[i].clientData, 0);
940: }
941: return TCL_OK;
942: }
943:
944: #endif /* SQLITE_TEST */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to test_fuzzer.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sqlite3 / src