wasCSharpSQLite – Blame information for rev 1

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