SQLite
Check-in [4d08e74d34]
Not logged in
Overview
SHA1 Hash:4d08e74d34e82f3be588049c9576a5c1008435e7
Date: 2013-04-26 06:58:06
User: dan
Comment:Merge latest trunk changes.
Tags And Properties
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to Makefile.in

357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390












391
392
393
394
395
396
397
  $(TOP)/src/test_backup.c \
  $(TOP)/src/test_btree.c \
  $(TOP)/src/test_config.c \
  $(TOP)/src/test_demovfs.c \
  $(TOP)/src/test_devsym.c \
  $(TOP)/src/test_fs.c \
  $(TOP)/src/test_func.c \
  $(TOP)/src/test_fuzzer.c \
  $(TOP)/src/test_hexio.c \
  $(TOP)/src/test_init.c \
  $(TOP)/src/test_intarray.c \
  $(TOP)/src/test_journal.c \
  $(TOP)/src/test_malloc.c \
  $(TOP)/src/test_multiplex.c \
  $(TOP)/src/test_mutex.c \
  $(TOP)/src/test_onefile.c \
  $(TOP)/src/test_osinst.c \
  $(TOP)/src/test_pcache.c \
  $(TOP)/src/test_quota.c \
  $(TOP)/src/test_regexp.c \
  $(TOP)/src/test_rtree.c \
  $(TOP)/src/test_schema.c \
  $(TOP)/src/test_server.c \
  $(TOP)/src/test_superlock.c \
  $(TOP)/src/test_syscall.c \
  $(TOP)/src/test_stat.c \
  $(TOP)/src/test_tclvar.c \
  $(TOP)/src/test_thread.c \
  $(TOP)/src/test_vfs.c \
  $(TOP)/src/test_wholenumber.c \
  $(TOP)/src/test_wsd.c       \
  $(TOP)/ext/fts3/fts3_term.c \
  $(TOP)/ext/fts3/fts3_test.c 













# Source code to the library files needed by the test fixture
#
TESTSRC2 = \
  $(TOP)/src/attach.c \
  $(TOP)/src/backup.c \
  $(TOP)/src/bitvec.c \
  $(TOP)/src/btree.c \







<











<









<




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







357
358
359
360
361
362
363

364
365
366
367
368
369
370
371
372
373
374

375
376
377
378
379
380
381
382
383

384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
  $(TOP)/src/test_backup.c \
  $(TOP)/src/test_btree.c \
  $(TOP)/src/test_config.c \
  $(TOP)/src/test_demovfs.c \
  $(TOP)/src/test_devsym.c \
  $(TOP)/src/test_fs.c \
  $(TOP)/src/test_func.c \

  $(TOP)/src/test_hexio.c \
  $(TOP)/src/test_init.c \
  $(TOP)/src/test_intarray.c \
  $(TOP)/src/test_journal.c \
  $(TOP)/src/test_malloc.c \
  $(TOP)/src/test_multiplex.c \
  $(TOP)/src/test_mutex.c \
  $(TOP)/src/test_onefile.c \
  $(TOP)/src/test_osinst.c \
  $(TOP)/src/test_pcache.c \
  $(TOP)/src/test_quota.c \

  $(TOP)/src/test_rtree.c \
  $(TOP)/src/test_schema.c \
  $(TOP)/src/test_server.c \
  $(TOP)/src/test_superlock.c \
  $(TOP)/src/test_syscall.c \
  $(TOP)/src/test_stat.c \
  $(TOP)/src/test_tclvar.c \
  $(TOP)/src/test_thread.c \
  $(TOP)/src/test_vfs.c \

  $(TOP)/src/test_wsd.c       \
  $(TOP)/ext/fts3/fts3_term.c \
  $(TOP)/ext/fts3/fts3_test.c 

# Statically linked extensions
#
TESTSRC += \
  $(TOP)/ext/misc/amatch.c \
  $(TOP)/ext/misc/closure.c \
  $(TOP)/ext/misc/fuzzer.c \
  $(TOP)/ext/misc/ieee754.c \
  $(TOP)/ext/misc/nextchar.c \
  $(TOP)/ext/misc/regexp.c \
  $(TOP)/ext/misc/spellfix.c \
  $(TOP)/ext/misc/wholenumber.c

# Source code to the library files needed by the test fixture
#
TESTSRC2 = \
  $(TOP)/src/attach.c \
  $(TOP)/src/backup.c \
  $(TOP)/src/bitvec.c \
  $(TOP)/src/btree.c \

Changes to Makefile.msc

677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709













710
711
712
713
714
715
716
....
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
  $(TOP)\src\test_backup.c \
  $(TOP)\src\test_btree.c \
  $(TOP)\src\test_config.c \
  $(TOP)\src\test_demovfs.c \
  $(TOP)\src\test_devsym.c \
  $(TOP)\src\test_fs.c \
  $(TOP)\src\test_func.c \
  $(TOP)\src\test_fuzzer.c \
  $(TOP)\src\test_hexio.c \
  $(TOP)\src\test_init.c \
  $(TOP)\src\test_intarray.c \
  $(TOP)\src\test_journal.c \
  $(TOP)\src\test_malloc.c \
  $(TOP)\src\test_multiplex.c \
  $(TOP)\src\test_mutex.c \
  $(TOP)\src\test_onefile.c \
  $(TOP)\src\test_osinst.c \
  $(TOP)\src\test_pcache.c \
  $(TOP)\src\test_quota.c \
  $(TOP)\src\test_regexp.c \
  $(TOP)\src\test_rtree.c \
  $(TOP)\src\test_schema.c \
  $(TOP)\src\test_server.c \
  $(TOP)\src\test_superlock.c \
  $(TOP)\src\test_syscall.c \
  $(TOP)\src\test_stat.c \
  $(TOP)\src\test_tclvar.c \
  $(TOP)\src\test_thread.c \
  $(TOP)\src\test_vfs.c \
  $(TOP)\src\test_wholenumber.c \
  $(TOP)\src\test_wsd.c \
  $(TOP)\ext\fts3\fts3_term.c \
  $(TOP)\ext\fts3\fts3_test.c














# Source code to the library files needed by the test fixture
#
TESTSRC2 = \
  $(TOP)\src\attach.c \
  $(TOP)\src\backup.c \
  $(TOP)\src\bitvec.c \
................................................................................
# fixture.  Otherwise link against libsqlite3.lib.  (This distinction is
# necessary because the test fixture requires non-API symbols which are
# hidden when the library is built via the amalgamation).
#
TESTFIXTURE_FLAGS = -DTCLSH=1 -DSQLITE_TEST=1 -DSQLITE_CRASH_TEST=1
TESTFIXTURE_FLAGS = $(TESTFIXTURE_FLAGS) -DSQLITE_SERVER=1 -DSQLITE_PRIVATE="" -DSQLITE_CORE

TESTFIXTURE_SRC0 = $(TESTSRC2) libsqlite3.lib
TESTFIXTURE_SRC1 = sqlite3.c
!IF $(USE_AMALGAMATION)==0
TESTFIXTURE_SRC = $(TESTSRC) $(TOP)\src\tclsqlite.c $(TESTFIXTURE_SRC0)
!ELSE
TESTFIXTURE_SRC = $(TESTSRC) $(TOP)\src\tclsqlite.c $(TESTFIXTURE_SRC1)
!ENDIF

testfixture.exe:	$(TESTFIXTURE_SRC) $(LIBRESOBJS) $(HDR)







<











<









<



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







 







|
|







677
678
679
680
681
682
683

684
685
686
687
688
689
690
691
692
693
694

695
696
697
698
699
700
701
702
703

704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
....
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
  $(TOP)\src\test_backup.c \
  $(TOP)\src\test_btree.c \
  $(TOP)\src\test_config.c \
  $(TOP)\src\test_demovfs.c \
  $(TOP)\src\test_devsym.c \
  $(TOP)\src\test_fs.c \
  $(TOP)\src\test_func.c \

  $(TOP)\src\test_hexio.c \
  $(TOP)\src\test_init.c \
  $(TOP)\src\test_intarray.c \
  $(TOP)\src\test_journal.c \
  $(TOP)\src\test_malloc.c \
  $(TOP)\src\test_multiplex.c \
  $(TOP)\src\test_mutex.c \
  $(TOP)\src\test_onefile.c \
  $(TOP)\src\test_osinst.c \
  $(TOP)\src\test_pcache.c \
  $(TOP)\src\test_quota.c \

  $(TOP)\src\test_rtree.c \
  $(TOP)\src\test_schema.c \
  $(TOP)\src\test_server.c \
  $(TOP)\src\test_superlock.c \
  $(TOP)\src\test_syscall.c \
  $(TOP)\src\test_stat.c \
  $(TOP)\src\test_tclvar.c \
  $(TOP)\src\test_thread.c \
  $(TOP)\src\test_vfs.c \

  $(TOP)\src\test_wsd.c \
  $(TOP)\ext\fts3\fts3_term.c \
  $(TOP)\ext\fts3\fts3_test.c

# Statically linked extensions
#
TESTEXT = \
  $(TOP)\ext\misc\amatch.c \
  $(TOP)\ext\misc\closure.c \
  $(TOP)\ext\misc\fuzzer.c \
  $(TOP)\ext\misc\ieee754.c \
  $(TOP)\ext\misc\nextchar.c \
  $(TOP)\ext\misc\regexp.c \
  $(TOP)\ext\misc\spellfix.c \
  $(TOP)\ext\misc\wholenumber.c


# Source code to the library files needed by the test fixture
#
TESTSRC2 = \
  $(TOP)\src\attach.c \
  $(TOP)\src\backup.c \
  $(TOP)\src\bitvec.c \
................................................................................
# fixture.  Otherwise link against libsqlite3.lib.  (This distinction is
# necessary because the test fixture requires non-API symbols which are
# hidden when the library is built via the amalgamation).
#
TESTFIXTURE_FLAGS = -DTCLSH=1 -DSQLITE_TEST=1 -DSQLITE_CRASH_TEST=1
TESTFIXTURE_FLAGS = $(TESTFIXTURE_FLAGS) -DSQLITE_SERVER=1 -DSQLITE_PRIVATE="" -DSQLITE_CORE

TESTFIXTURE_SRC0 = $(TESTEXT) $(TESTSRC2) libsqlite3.lib
TESTFIXTURE_SRC1 = $(TESTEXT) sqlite3.c
!IF $(USE_AMALGAMATION)==0
TESTFIXTURE_SRC = $(TESTSRC) $(TOP)\src\tclsqlite.c $(TESTFIXTURE_SRC0)
!ELSE
TESTFIXTURE_SRC = $(TESTSRC) $(TOP)\src\tclsqlite.c $(TESTFIXTURE_SRC1)
!ENDIF

testfixture.exe:	$(TESTFIXTURE_SRC) $(LIBRESOBJS) $(HDR)

Added ext/misc/amatch.c











































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
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
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
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
438
439
440
441
442
443
444
445
446
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
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
/*
** 2013-03-14
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
**
** This file contains code for a demonstration virtual table that finds
** "approximate matches" - strings from a finite set that are nearly the
** same as a single input string.  The virtual table is called "amatch".
**
** A amatch virtual table is created like this:
**
**     CREATE VIRTUAL TABLE f USING approximate_match(
**        vocabulary_table=<tablename>,      -- V
**        vocabulary_word=<columnname>,      -- W
**        vocabulary_language=<columnname>,  -- L
**        edit_distances=<edit-cost-table>
**     );
**
** When it is created, the new amatch table must be supplied with the
** the name of a table V and columns V.W and V.L such that 
**
**     SELECT W FROM V WHERE L=$language
**
** returns the allowed vocabulary for the match.  If the "vocabulary_language"
** or L columnname is left unspecified or is an empty string, then no
** filtering of the vocabulary by language is performed. 
**
** For efficiency, it is essential that the vocabulary table be indexed:
**
**     CREATE vocab_index ON V(W)
**
** A separate edit-cost-table provides scoring information that defines 
** what it means for one string to be "close" to another.
**
** The edit-cost-table must contain exactly four columns (more precisely,
** the statement "SELECT * FROM <edit-cost-table>" must return records
** that consist of four columns). It does not matter what the columns are
** named. 
**
** Each row in the edit-cost-table represents a single character
** transformation going from user input to the vocabulary. The leftmost 
** column of the row (column 0) contains an integer identifier of the
** language to which the transformation rule belongs (see "MULTIPLE LANGUAGES"
** below). The second column of the row (column 1) contains the input
** character or characters - the characters of user input. The third 
** column contains characters as they appear in the vocabulary table.
** And the fourth column contains the integer cost of making the
** transformation. For example:
**
**    CREATE TABLE f_data(iLang, cFrom, cTo, Cost);
**    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, '', 'a', 100);
**    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, 'b', '', 87);
**    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, 'o', 'oe', 38);
**    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, 'oe', 'o', 40);
**
** The first row inserted into the edit-cost-table by the SQL script
** above indicates that the cost of having an extra 'a' in the vocabulary
** table that is missing in the user input 100.  (All costs are integers.
** Overall cost must not exceed 16777216.)  The second INSERT statement 
** creates a rule saying that the cost of having a single letter 'b' in
** user input which is missing in the vocabulary table is 87.  The third
** INSERT statement mean that the cost of matching an 'o' in user input 
** against an 'oe' in the vocabulary table is 38.  And so forth.
**
** The following rules are special:
**
**    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, '?', '', 97);
**    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, '', '?', 98);
**    INSERT INTO f_data(iLang, cFrom, cTo, Cost) VALUES(0, '?', '?', 99);
**
** The '?' to '' rule is the cost of having any single character in the input
** that is not found in the vocabular.  The '' to '?' rule is the cost of
** having a character in the vocabulary table that is missing from input.
** And the '?' to '?' rule is the cost of doing an arbitrary character
** substitution.  These three generic rules apply across all languages.
** In other words, the iLang field is ignored for the generic substitution
** rules.  If more than one cost is given for a generic substitution rule,
** then the lowest cost is used.
**
** Once it has been created, the amatch virtual table can be queried
** as follows:
**
**    SELECT word, distance FROM f
**     WHERE word MATCH 'abcdefg'
**       AND distance<200;
**
** This query outputs the strings contained in the T(F) field that
** are close to "abcdefg" and in order of increasing distance.  No string
** is output more than once.  If there are multiple ways to transform the
** target string ("abcdefg") into a string in the vocabulary table then
** the lowest cost transform is the one that is returned.  In this example,
** the search is limited to strings with a total distance of less than 200.
**
** For efficiency, it is important to put tight bounds on the distance.
** The time and memory space needed to perform this query is exponential
** in the maximum distance.  A good rule of thumb is to limit the distance
** to no more than 1.5 or 2 times the maximum cost of any rule in the
** edit-cost-table.
**
** The amatch is a read-only table.  Any attempt to DELETE, INSERT, or
** UPDATE on a amatch table will throw an error.
**
** It is important to put some kind of a limit on the amatch output.  This
** can be either in the form of a LIMIT clause at the end of the query,
** or better, a "distance<NNN" constraint where NNN is some number.  The
** running time and memory requirement is exponential in the value of NNN 
** so you want to make sure that NNN is not too big.  A value of NNN that
** is about twice the average transformation cost seems to give good results.
**
** The amatch table can be useful for tasks such as spelling correction.
** Suppose all allowed words are in table vocabulary(w).  Then one would create
** an amatch virtual table like this:
**
**   CREATE VIRTUAL TABLE ex1 USING amatch(
**       vocabtable=vocabulary,
**       vocabcolumn=w,
**       edit_distances=ec1
**   );
**
** Then given an input word $word, look up close spellings this way:
**
**   SELECT word, distance FROM ex1
**    WHERE word MATCH $word AND distance<200;
**
** MULTIPLE LANGUAGES
**
** Normally, the "iLang" value associated with all character transformations
** in the edit-cost-table is zero. However, if required, the amatch 
** virtual table allows multiple languages to be defined. Each query uses 
** only a single iLang value.   This allows, for example, a single 
** amatch table to support multiple languages.
**
** By default, only the rules with iLang=0 are used. To specify an 
** alternative language, a "language = ?" expression must be added to the
** WHERE clause of a SELECT, where ? is the integer identifier of the desired 
** language. For example:
**
**   SELECT word, distance FROM ex1
**    WHERE word MATCH $word
**      AND distance<=200
**      AND language=1 -- Specify use language 1 instead of 0
**
** If no "language = ?" constraint is specified in the WHERE clause, language
** 0 is used.
**
** LIMITS
**
** The maximum language number is 2147483647.  The maximum length of either
** of the strings in the second or third column of the amatch data table
** is 50 bytes.  The maximum cost on a rule is 1000.
*/
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <ctype.h>

/*
** Forward declaration of objects used by this implementation
*/
typedef struct amatch_vtab amatch_vtab;
typedef struct amatch_cursor amatch_cursor;
typedef struct amatch_rule amatch_rule;
typedef struct amatch_word amatch_word;
typedef struct amatch_avl amatch_avl;


/*****************************************************************************
** AVL Tree implementation
*/
/*
** Objects that want to be members of the AVL tree should embedded an
** instance of this structure.
*/
struct amatch_avl {
  amatch_word *pWord;   /* Points to the object being stored in the tree */
  char *zKey;           /* Key.  zero-terminated string.  Must be unique */
  amatch_avl *pBefore;  /* Other elements less than zKey */
  amatch_avl *pAfter;   /* Other elements greater than zKey */
  amatch_avl *pUp;      /* Parent element */
  short int height;     /* Height of this node.  Leaf==1 */
  short int imbalance;  /* Height difference between pBefore and pAfter */
};

/* Recompute the amatch_avl.height and amatch_avl.imbalance fields for p.
** Assume that the children of p have correct heights.
*/
static void amatchAvlRecomputeHeight(amatch_avl *p){
  short int hBefore = p->pBefore ? p->pBefore->height : 0;
  short int hAfter = p->pAfter ? p->pAfter->height : 0;
  p->imbalance = hBefore - hAfter;  /* -: pAfter higher.  +: pBefore higher */
  p->height = (hBefore>hAfter ? hBefore : hAfter)+1;
}

/*
**     P                B
**    / \              / \
**   B   Z    ==>     X   P
**  / \                  / \
** X   Y                Y   Z
**
*/
static amatch_avl *amatchAvlRotateBefore(amatch_avl *pP){
  amatch_avl *pB = pP->pBefore;
  amatch_avl *pY = pB->pAfter;
  pB->pUp = pP->pUp;
  pB->pAfter = pP;
  pP->pUp = pB;
  pP->pBefore = pY;
  if( pY ) pY->pUp = pP;
  amatchAvlRecomputeHeight(pP);
  amatchAvlRecomputeHeight(pB);
  return pB;
}

/*
**     P                A
**    / \              / \
**   X   A    ==>     P   Z
**      / \          / \
**     Y   Z        X   Y
**
*/
static amatch_avl *amatchAvlRotateAfter(amatch_avl *pP){
  amatch_avl *pA = pP->pAfter;
  amatch_avl *pY = pA->pBefore;
  pA->pUp = pP->pUp;
  pA->pBefore = pP;
  pP->pUp = pA;
  pP->pAfter = pY;
  if( pY ) pY->pUp = pP;
  amatchAvlRecomputeHeight(pP);
  amatchAvlRecomputeHeight(pA);
  return pA;
}

/*
** Return a pointer to the pBefore or pAfter pointer in the parent
** of p that points to p.  Or if p is the root node, return pp.
*/
static amatch_avl **amatchAvlFromPtr(amatch_avl *p, amatch_avl **pp){
  amatch_avl *pUp = p->pUp;
  if( pUp==0 ) return pp;
  if( pUp->pAfter==p ) return &pUp->pAfter;
  return &pUp->pBefore;
}

/*
** Rebalance all nodes starting with p and working up to the root.
** Return the new root.
*/
static amatch_avl *amatchAvlBalance(amatch_avl *p){
  amatch_avl *pTop = p;
  amatch_avl **pp;
  while( p ){
    amatchAvlRecomputeHeight(p);
    if( p->imbalance>=2 ){
      amatch_avl *pB = p->pBefore;
      if( pB->imbalance<0 ) p->pBefore = amatchAvlRotateAfter(pB);
      pp = amatchAvlFromPtr(p,&p);
      p = *pp = amatchAvlRotateBefore(p);
    }else if( p->imbalance<=(-2) ){
      amatch_avl *pA = p->pAfter;
      if( pA->imbalance>0 ) p->pAfter = amatchAvlRotateBefore(pA);
      pp = amatchAvlFromPtr(p,&p);
      p = *pp = amatchAvlRotateAfter(p);
    }
    pTop = p;
    p = p->pUp;
  }
  return pTop;
}

/* Search the tree rooted at p for an entry with zKey.  Return a pointer
** to the entry or return NULL.
*/
static amatch_avl *amatchAvlSearch(amatch_avl *p, const char *zKey){
  int c;
  while( p && (c = strcmp(zKey, p->zKey))!=0 ){
    p = (c<0) ? p->pBefore : p->pAfter;
  }
  return p;
}

/* Find the first node (the one with the smallest key).
*/
static amatch_avl *amatchAvlFirst(amatch_avl *p){
  if( p ) while( p->pBefore ) p = p->pBefore;
  return p;
}

#if 0 /* NOT USED */
/* Return the node with the next larger key after p.
*/
static amatch_avl *amatchAvlNext(amatch_avl *p){
  amatch_avl *pPrev = 0;
  while( p && p->pAfter==pPrev ){
    pPrev = p;
    p = p->pUp;
  }
  if( p && pPrev==0 ){
    p = amatchAvlFirst(p->pAfter);
  }
  return p;
}
#endif

#if 0 /* NOT USED */
/* Verify AVL tree integrity
*/
static int amatchAvlIntegrity(amatch_avl *pHead){
  amatch_avl *p;
  if( pHead==0 ) return 1;
  if( (p = pHead->pBefore)!=0 ){
    assert( p->pUp==pHead );
    assert( amatchAvlIntegrity(p) );
    assert( strcmp(p->zKey, pHead->zKey)<0 );
    while( p->pAfter ) p = p->pAfter;
    assert( strcmp(p->zKey, pHead->zKey)<0 );
  }
  if( (p = pHead->pAfter)!=0 ){
    assert( p->pUp==pHead );
    assert( amatchAvlIntegrity(p) );
    assert( strcmp(p->zKey, pHead->zKey)>0 );
    p = amatchAvlFirst(p);
    assert( strcmp(p->zKey, pHead->zKey)>0 );
  }
  return 1;
}
static int amatchAvlIntegrity2(amatch_avl *pHead){
  amatch_avl *p, *pNext;
  for(p=amatchAvlFirst(pHead); p; p=pNext){
    pNext = amatchAvlNext(p);
    if( pNext==0 ) break;
    assert( strcmp(p->zKey, pNext->zKey)<0 );
  }
  return 1;
}
#endif

/* Insert a new node pNew.  Return NULL on success.  If the key is not
** unique, then do not perform the insert but instead leave pNew unchanged
** and return a pointer to an existing node with the same key.
*/
static amatch_avl *amatchAvlInsert(amatch_avl **ppHead, amatch_avl *pNew){
  int c;
  amatch_avl *p = *ppHead;
  if( p==0 ){
    p = pNew;
    pNew->pUp = 0;
  }else{
    while( p ){
      c = strcmp(pNew->zKey, p->zKey);
      if( c<0 ){
        if( p->pBefore ){
          p = p->pBefore;
        }else{
          p->pBefore = pNew;
          pNew->pUp = p;
          break;
        }
      }else if( c>0 ){
        if( p->pAfter ){
          p = p->pAfter;
        }else{
          p->pAfter = pNew;
          pNew->pUp = p;
          break;
        }
      }else{
        return p;
      }
    }
  }
  pNew->pBefore = 0;
  pNew->pAfter = 0;
  pNew->height = 1;
  pNew->imbalance = 0;
  *ppHead = amatchAvlBalance(p);
  /* assert( amatchAvlIntegrity(*ppHead) ); */
  /* assert( amatchAvlIntegrity2(*ppHead) ); */
  return 0;
}

/* Remove node pOld from the tree.  pOld must be an element of the tree or
** the AVL tree will become corrupt.
*/
static void amatchAvlRemove(amatch_avl **ppHead, amatch_avl *pOld){
  amatch_avl **ppParent;
  amatch_avl *pBalance;
  /* assert( amatchAvlSearch(*ppHead, pOld->zKey)==pOld ); */
  ppParent = amatchAvlFromPtr(pOld, ppHead);
  if( pOld->pBefore==0 && pOld->pAfter==0 ){
    *ppParent = 0;
    pBalance = pOld->pUp;
  }else if( pOld->pBefore && pOld->pAfter ){
    amatch_avl *pX, *pY;
    pX = amatchAvlFirst(pOld->pAfter);
    *amatchAvlFromPtr(pX, 0) = pX->pAfter;
    if( pX->pAfter ) pX->pAfter->pUp = pX->pUp;
    pBalance = pX->pUp;
    pX->pAfter = pOld->pAfter;
    if( pX->pAfter ){
      pX->pAfter->pUp = pX;
    }else{
      assert( pBalance==pOld );
      pBalance = pX;
    }
    pX->pBefore = pY = pOld->pBefore;
    if( pY ) pY->pUp = pX;
    pX->pUp = pOld->pUp;
    *ppParent = pX;
  }else if( pOld->pBefore==0 ){
    *ppParent = pBalance = pOld->pAfter;
    pBalance->pUp = pOld->pUp;
  }else if( pOld->pAfter==0 ){
    *ppParent = pBalance = pOld->pBefore;
    pBalance->pUp = pOld->pUp;
  }
  *ppHead = amatchAvlBalance(pBalance);
  pOld->pUp = 0;
  pOld->pBefore = 0;
  pOld->pAfter = 0;
  /* assert( amatchAvlIntegrity(*ppHead) ); */
  /* assert( amatchAvlIntegrity2(*ppHead) ); */
}
/*
** End of the AVL Tree implementation
******************************************************************************/


/*
** Various types.
**
** amatch_cost is the "cost" of an edit operation.
**
** amatch_len is the length of a matching string.  
**
** amatch_langid is an ruleset identifier.
*/
typedef int amatch_cost;
typedef signed char amatch_len;
typedef int amatch_langid;

/*
** Limits
*/
#define AMATCH_MX_LENGTH          50  /* Maximum length of a rule string */
#define AMATCH_MX_LANGID  2147483647  /* Maximum rule ID */
#define AMATCH_MX_COST          1000  /* Maximum single-rule cost */

/*
** A match or partial match
*/
struct amatch_word {
  amatch_word *pNext;   /* Next on a list of all amatch_words */
  amatch_avl sCost;     /* Linkage of this node into the cost tree */
  amatch_avl sWord;     /* Linkage of this node into the word tree */
  amatch_cost rCost;    /* Cost of the match so far */
  int iSeq;             /* Sequence number */
  char zCost[10];       /* Cost key (text rendering of rCost) */
  short int nMatch;     /* Input characters matched */
  char zWord[4];        /* Text of the word.  Extra space appended as needed */
};

/*
** Each transformation rule is stored as an instance of this object.
** All rules are kept on a linked list sorted by rCost.
*/
struct amatch_rule {
  amatch_rule *pNext;      /* Next rule in order of increasing rCost */
  char *zFrom;             /* Transform from (a string from user input) */
  amatch_cost rCost;       /* Cost of this transformation */
  amatch_langid iLang;     /* The langauge to which this rule belongs */
  amatch_len nFrom, nTo;   /* Length of the zFrom and zTo strings */
  char zTo[4];             /* Tranform to V.W value (extra space appended) */
};

/* 
** A amatch virtual-table object 
*/
struct amatch_vtab {
  sqlite3_vtab base;         /* Base class - must be first */
  char *zClassName;          /* Name of this class.  Default: "amatch" */
  char *zDb;                 /* Name of database.  (ex: "main") */
  char *zSelf;               /* Name of this virtual table */
  char *zCostTab;            /* Name of edit-cost-table */
  char *zVocabTab;           /* Name of vocabulary table */
  char *zVocabWord;          /* Name of vocabulary table word column */
  char *zVocabLang;          /* Name of vocabulary table language column */
  amatch_rule *pRule;        /* All active rules in this amatch */
  amatch_cost rIns;          /* Generic insertion cost  '' -> ? */
  amatch_cost rDel;          /* Generic deletion cost  ? -> '' */
  amatch_cost rSub;          /* Generic substitution cost ? -> ? */
  sqlite3 *db;               /* The database connection */
  sqlite3_stmt *pVCheck;     /* Query to check zVocabTab */
  int nCursor;               /* Number of active cursors */
};

/* A amatch cursor object */
struct amatch_cursor {
  sqlite3_vtab_cursor base;  /* Base class - must be first */
  sqlite3_int64 iRowid;      /* The rowid of the current word */
  amatch_langid iLang;       /* Use this language ID */
  amatch_cost rLimit;        /* Maximum cost of any term */
  int nBuf;                  /* Space allocated for zBuf */
  int oomErr;                /* True following an OOM error */
  int nWord;                 /* Number of amatch_word objects */
  char *zBuf;                /* Temp-use buffer space */
  char *zInput;              /* Input word to match against */
  amatch_vtab *pVtab;        /* The virtual table this cursor belongs to */
  amatch_word *pAllWords;    /* List of all amatch_word objects */
  amatch_word *pCurrent;     /* Most recent solution */
  amatch_avl *pCost;         /* amatch_word objects keyed by iCost */
  amatch_avl *pWord;         /* amatch_word objects keyed by zWord */
};

/*
** The two input rule lists are both sorted in order of increasing
** cost.  Merge them together into a single list, sorted by cost, and
** return a pointer to the head of that list.
*/
static amatch_rule *amatchMergeRules(amatch_rule *pA, amatch_rule *pB){
  amatch_rule head;
  amatch_rule *pTail;

  pTail =  &head;
  while( pA && pB ){
    if( pA->rCost<=pB->rCost ){
      pTail->pNext = pA;
      pTail = pA;
      pA = pA->pNext;
    }else{
      pTail->pNext = pB;
      pTail = pB;
      pB = pB->pNext;
    }
  }
  if( pA==0 ){
    pTail->pNext = pB;
  }else{
    pTail->pNext = pA;
  }
  return head.pNext;
}

/*
** Statement pStmt currently points to a row in the amatch data table. This
** function allocates and populates a amatch_rule structure according to
** the content of the row.
**
** If successful, *ppRule is set to point to the new object and SQLITE_OK
** is returned. Otherwise, *ppRule is zeroed, *pzErr may be set to point
** to an error message and an SQLite error code returned.
*/
static int amatchLoadOneRule(
  amatch_vtab *p,                 /* Fuzzer virtual table handle */
  sqlite3_stmt *pStmt,            /* Base rule on statements current row */
  amatch_rule **ppRule,           /* OUT: New rule object */
  char **pzErr                    /* OUT: Error message */
){
  sqlite3_int64 iLang = sqlite3_column_int64(pStmt, 0);
  const char *zFrom = (const char *)sqlite3_column_text(pStmt, 1);
  const char *zTo = (const char *)sqlite3_column_text(pStmt, 2);
  amatch_cost rCost = sqlite3_column_int(pStmt, 3);

  int rc = SQLITE_OK;             /* Return code */
  int nFrom;                      /* Size of string zFrom, in bytes */
  int nTo;                        /* Size of string zTo, in bytes */
  amatch_rule *pRule = 0;         /* New rule object to return */

  if( zFrom==0 ) zFrom = "";
  if( zTo==0 ) zTo = "";
  nFrom = (int)strlen(zFrom);
  nTo = (int)strlen(zTo);

  /* Silently ignore null transformations */
  if( strcmp(zFrom, zTo)==0 ){
    if( zFrom[0]=='?' && zFrom[1]==0 ){
      if( p->rSub==0 || p->rSub>rCost ) p->rSub = rCost;
    }
    *ppRule = 0;
    return SQLITE_OK;
  }

  if( rCost<=0 || rCost>AMATCH_MX_COST ){
    *pzErr = sqlite3_mprintf("%s: cost must be between 1 and %d", 
        p->zClassName, AMATCH_MX_COST
    );
    rc = SQLITE_ERROR;
  }else
  if( nFrom>AMATCH_MX_LENGTH || nTo>AMATCH_MX_LENGTH ){
    *pzErr = sqlite3_mprintf("%s: maximum string length is %d", 
        p->zClassName, AMATCH_MX_LENGTH
    );
    rc = SQLITE_ERROR;    
  }else
  if( iLang<0 || iLang>AMATCH_MX_LANGID ){
    *pzErr = sqlite3_mprintf("%s: iLang must be between 0 and %d", 
        p->zClassName, AMATCH_MX_LANGID
    );
    rc = SQLITE_ERROR;    
  }else
  if( strcmp(zFrom,"")==0 && strcmp(zTo,"?")==0 ){
    if( p->rIns==0 || p->rIns>rCost ) p->rIns = rCost;
  }else
  if( strcmp(zFrom,"?")==0 && strcmp(zTo,"")==0 ){
    if( p->rDel==0 || p->rDel>rCost ) p->rDel = rCost;
  }else
  {
    pRule = sqlite3_malloc( sizeof(*pRule) + nFrom + nTo );
    if( pRule==0 ){
      rc = SQLITE_NOMEM;
    }else{
      memset(pRule, 0, sizeof(*pRule));
      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->iLang = (int)iLang;
    }
  }

  *ppRule = pRule;
  return rc;
}

/*
** Free all the content in the edit-cost-table
*/
static void amatchFreeRules(amatch_vtab *p){
  while( p->pRule ){
    amatch_rule *pRule = p->pRule;
    p->pRule = pRule->pNext;
    sqlite3_free(pRule);
  }
  p->pRule = 0;
}

/*
** Load the content of the amatch data table into memory.
*/
static int amatchLoadRules(
  sqlite3 *db,                    /* Database handle */
  amatch_vtab *p,                 /* Virtual amatch table to configure */
  char **pzErr                    /* OUT: Error message */
){
  int rc = SQLITE_OK;             /* Return code */
  char *zSql;                     /* SELECT used to read from rules table */
  amatch_rule *pHead = 0;

  zSql = sqlite3_mprintf("SELECT * FROM %Q.%Q", p->zDb, p->zCostTab);
  if( zSql==0 ){
    rc = SQLITE_NOMEM;
  }else{
    int rc2;                      /* finalize() return code */
    sqlite3_stmt *pStmt = 0;
    rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0);
    if( rc!=SQLITE_OK ){
      *pzErr = sqlite3_mprintf("%s: %s", p->zClassName, sqlite3_errmsg(db));
    }else if( sqlite3_column_count(pStmt)!=4 ){
      *pzErr = sqlite3_mprintf("%s: %s has %d columns, expected 4",
          p->zClassName, p->zCostTab, sqlite3_column_count(pStmt)
      );
      rc = SQLITE_ERROR;
    }else{
      while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pStmt) ){
        amatch_rule *pRule = 0;
        rc = amatchLoadOneRule(p, pStmt, &pRule, pzErr);
        if( pRule ){
          pRule->pNext = pHead;
          pHead = pRule;
        }
      }
    }
    rc2 = sqlite3_finalize(pStmt);
    if( rc==SQLITE_OK ) rc = rc2;
  }
  sqlite3_free(zSql);

  /* All rules are now in a singly linked list starting at pHead. This
  ** block sorts them by cost and then sets amatch_vtab.pRule to point to 
  ** point to the head of the sorted list.
  */
  if( rc==SQLITE_OK ){
    unsigned int i;
    amatch_rule *pX;
    amatch_rule *a[15];
    for(i=0; i<sizeof(a)/sizeof(a[0]); i++) a[i] = 0;
    while( (pX = pHead)!=0 ){
      pHead = pX->pNext;
      pX->pNext = 0;
      for(i=0; a[i] && i<sizeof(a)/sizeof(a[0])-1; i++){
        pX = amatchMergeRules(a[i], pX);
        a[i] = 0;
      }
      a[i] = amatchMergeRules(a[i], pX);
    }
    for(pX=a[0], i=1; i<sizeof(a)/sizeof(a[0]); i++){
      pX = amatchMergeRules(a[i], pX);
    }
    p->pRule = amatchMergeRules(p->pRule, pX);
  }else{
    /* An error has occurred. Setting p->pRule to point to the head of the
    ** allocated list ensures that the list will be cleaned up in this case.
    */
    assert( p->pRule==0 );
    p->pRule = pHead;
  }

  return rc;
}

/*
** This function converts an SQL quoted string into an unquoted string
** and returns a pointer to a buffer allocated using sqlite3_malloc() 
** containing the result. The caller should eventually free this buffer
** using sqlite3_free.
**
** Examples:
**
**     "abc"   becomes   abc
**     'xyz'   becomes   xyz
**     [pqr]   becomes   pqr
**     `mno`   becomes   mno
*/
static char *amatchDequote(const char *zIn){
  int nIn;                        /* Size of input string, in bytes */
  char *zOut;                     /* Output (dequoted) string */

  nIn = (int)strlen(zIn);
  zOut = sqlite3_malloc(nIn+1);
  if( zOut ){
    char q = zIn[0];              /* Quote character (if any ) */

    if( q!='[' && q!= '\'' && q!='"' && q!='`' ){
      memcpy(zOut, zIn, nIn+1);
    }else{
      int iOut = 0;               /* Index of next byte to write to output */
      int iIn;                    /* Index of next byte to read from input */

      if( q=='[' ) q = ']';
      for(iIn=1; iIn<nIn; iIn++){
        if( zIn[iIn]==q ) iIn++;
        zOut[iOut++] = zIn[iIn];
      }
    }
    assert( (int)strlen(zOut)<=nIn );
  }
  return zOut;
}

/*
** Deallocate the pVCheck prepared statement.
*/
static void amatchVCheckClear(amatch_vtab *p){
  if( p->pVCheck ){
    sqlite3_finalize(p->pVCheck);
    p->pVCheck = 0;
  }
}

/*
** Deallocate an amatch_vtab object
*/
static void amatchFree(amatch_vtab *p){
  if( p ){
    amatchFreeRules(p);
    amatchVCheckClear(p);
    sqlite3_free(p->zClassName);
    sqlite3_free(p->zDb);
    sqlite3_free(p->zCostTab);
    sqlite3_free(p->zVocabTab);
    sqlite3_free(p->zVocabWord);
    sqlite3_free(p->zVocabLang);
    memset(p, 0, sizeof(*p));
    sqlite3_free(p);
  }
}

/*
** xDisconnect/xDestroy method for the amatch module.
*/
static int amatchDisconnect(sqlite3_vtab *pVtab){
  amatch_vtab *p = (amatch_vtab*)pVtab;
  assert( p->nCursor==0 );
  amatchFree(p);
  return SQLITE_OK;
}

/*
** Check to see if the argument is of the form:
**
**       KEY = VALUE
**
** If it is, return a pointer to the first character of VALUE.
** If not, return NULL.  Spaces around the = are ignored.
*/
static const char *amatchValueOfKey(const char *zKey, const char *zStr){
  int nKey = (int)strlen(zKey);
  int nStr = (int)strlen(zStr);
  int i;
  if( nStr<nKey+1 ) return 0;
  if( memcmp(zStr, zKey, nKey)!=0 ) return 0;
  for(i=nKey; isspace(zStr[i]); i++){}
  if( zStr[i]!='=' ) return 0;
  i++;
  while( isspace(zStr[i]) ){ i++; }
  return zStr+i;
}

/*
** xConnect/xCreate method for the amatch module. Arguments are:
**
**   argv[0]    -> module name  ("approximate_match")
**   argv[1]    -> database name
**   argv[2]    -> table name
**   argv[3...] -> arguments
*/
static int amatchConnect(
  sqlite3 *db,
  void *pAux,
  int argc, const char *const*argv,
  sqlite3_vtab **ppVtab,
  char **pzErr
){
  int rc = SQLITE_OK;             /* Return code */
  amatch_vtab *pNew = 0;          /* New virtual table */
  const char *zModule = argv[0];
  const char *zDb = argv[1];
  const char *zVal;
  int i;

  (void)pAux;
  *ppVtab = 0;
  pNew = sqlite3_malloc( sizeof(*pNew) );
  if( pNew==0 ) return SQLITE_NOMEM;
  rc = SQLITE_NOMEM;
  memset(pNew, 0, sizeof(*pNew));
  pNew->db = db;
  pNew->zClassName = sqlite3_mprintf("%s", zModule);
  if( pNew->zClassName==0 ) goto amatchConnectError;
  pNew->zDb = sqlite3_mprintf("%s", zDb);
  if( pNew->zDb==0 ) goto amatchConnectError;
  pNew->zSelf = sqlite3_mprintf("%s", argv[2]);
  if( pNew->zSelf==0 ) goto amatchConnectError;
  for(i=3; i<argc; i++){
    zVal = amatchValueOfKey("vocabulary_table", argv[i]);
    if( zVal ){
      sqlite3_free(pNew->zVocabTab);
      pNew->zVocabTab = amatchDequote(zVal);
      if( pNew->zVocabTab==0 ) goto amatchConnectError;
      continue;
    }
    zVal = amatchValueOfKey("vocabulary_word", argv[i]);
    if( zVal ){
      sqlite3_free(pNew->zVocabWord);
      pNew->zVocabWord = amatchDequote(zVal);
      if( pNew->zVocabWord==0 ) goto amatchConnectError;
      continue;
    }
    zVal = amatchValueOfKey("vocabulary_language", argv[i]);
    if( zVal ){
      sqlite3_free(pNew->zVocabLang);
      pNew->zVocabLang = amatchDequote(zVal);
      if( pNew->zVocabLang==0 ) goto amatchConnectError;
      continue;
    }
    zVal = amatchValueOfKey("edit_distances", argv[i]);
    if( zVal ){
      sqlite3_free(pNew->zCostTab);
      pNew->zCostTab = amatchDequote(zVal);
      if( pNew->zCostTab==0 ) goto amatchConnectError;
      continue;
    }
    *pzErr = sqlite3_mprintf("unrecognized argument: [%s]\n", argv[i]);
    amatchFree(pNew);
    *ppVtab = 0;
    return SQLITE_ERROR;
  }
  rc = SQLITE_OK;
  if( pNew->zCostTab==0 ){
    *pzErr = sqlite3_mprintf("no edit_distances table specified");
    rc = SQLITE_ERROR;
  }else{
    rc = amatchLoadRules(db, pNew, pzErr);
  }
  if( rc==SQLITE_OK ){
    rc = sqlite3_declare_vtab(db,
           "CREATE TABLE x(word,distance,language,"
           "command HIDDEN,nword HIDDEN)"
         );
#define AMATCH_COL_WORD       0
#define AMATCH_COL_DISTANCE   1
#define AMATCH_COL_LANGUAGE   2
#define AMATCH_COL_COMMAND    3
#define AMATCH_COL_NWORD      4
  }
  if( rc!=SQLITE_OK ){
    amatchFree(pNew);
  }
  *ppVtab = &pNew->base;
  return rc;

amatchConnectError:
  amatchFree(pNew);
  return rc;
}

/*
** Open a new amatch cursor.
*/
static int amatchOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
  amatch_vtab *p = (amatch_vtab*)pVTab;
  amatch_cursor *pCur;
  pCur = sqlite3_malloc( sizeof(*pCur) );
  if( pCur==0 ) return SQLITE_NOMEM;
  memset(pCur, 0, sizeof(*pCur));
  pCur->pVtab = p;
  *ppCursor = &pCur->base;
  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.
*/
static void amatchClearCursor(amatch_cursor *pCur){
  amatch_word *pWord, *pNextWord;
  for(pWord=pCur->pAllWords; pWord; pWord=pNextWord){
    pNextWord = pWord->pNext;
    sqlite3_free(pWord);
  }
  pCur->pAllWords = 0;
  sqlite3_free(pCur->zInput);
  pCur->zInput = 0;
  pCur->pCost = 0;
  pCur->pWord = 0;
  pCur->pCurrent = 0;
  pCur->rLimit = 1000000;
  pCur->iLang = 0;
  pCur->nWord = 0;
}

/*
** Close a amatch cursor.
*/
static int amatchClose(sqlite3_vtab_cursor *cur){
  amatch_cursor *pCur = (amatch_cursor *)cur;
  amatchClearCursor(pCur);
  pCur->pVtab->nCursor--;
  sqlite3_free(pCur);
  return SQLITE_OK;
}

/*
** Render a 24-bit unsigned integer as a 4-byte base-64 number.
*/
static void amatchEncodeInt(int x, char *z){
  static const char a[] = 
    "0123456789"
    "ABCDEFGHIJ"
    "KLMNOPQRST"
    "UVWXYZ^abc"
    "defghijklm"
    "nopqrstuvw"
    "xyz~";
  z[0] = a[(x>>18)&0x3f];
  z[1] = a[(x>>12)&0x3f];
  z[2] = a[(x>>6)&0x3f];
  z[3] = a[x&0x3f];
}

/*
** Write the zCost[] field for a amatch_word object
*/
static void amatchWriteCost(amatch_word *pWord){
  amatchEncodeInt(pWord->rCost, pWord->zCost);
  amatchEncodeInt(pWord->iSeq, pWord->zCost+4);
  pWord->zCost[8] = 0;
}

/*
** Add a new amatch_word object to the queue.
**
** If a prior amatch_word object with the same zWord, and nMatch
** already exists, update its rCost (if the new rCost is less) but
** otherwise leave it unchanged.  Do not add a duplicate.
**
** Do nothing if the cost exceeds threshold.
*/
static void amatchAddWord(
  amatch_cursor *pCur,
  amatch_cost rCost,
  int nMatch,
  const char *zWordBase,
  const char *zWordTail
){
  amatch_word *pWord;
  amatch_avl *pNode;
  amatch_avl *pOther;
  int nBase, nTail;
  char zBuf[4];
  
  if( rCost>pCur->rLimit ){
    return;
  }
  nBase = (int)strlen(zWordBase);
  nTail = (int)strlen(zWordTail);
  if( nBase+nTail+3>pCur->nBuf ){
    pCur->nBuf = nBase+nTail+100;
    pCur->zBuf = sqlite3_realloc(pCur->zBuf, pCur->nBuf);
    if( pCur->zBuf==0 ){
      pCur->nBuf = 0;
      return;
    }
  }
  amatchEncodeInt(nMatch, zBuf);
  memcpy(pCur->zBuf, zBuf+2, 2);
  memcpy(pCur->zBuf+2, zWordBase, nBase);
  memcpy(pCur->zBuf+2+nBase, zWordTail, nTail+1);
  pNode = amatchAvlSearch(pCur->pWord, pCur->zBuf);
  if( pNode ){
    pWord = pNode->pWord;
    if( pWord->rCost>rCost ){
#ifdef AMATCH_TRACE_1
      printf("UPDATE [%s][%.*s^%s] %d (\"%s\" \"%s\")\n",
             pWord->zWord+2, pWord->nMatch, pCur->zInput, pCur->zInput,
             pWord->rCost, pWord->zWord, pWord->zCost);
#endif
      amatchAvlRemove(&pCur->pCost, &pWord->sCost);
      pWord->rCost = rCost;
      amatchWriteCost(pWord);
#ifdef AMATCH_TRACE_1
      printf("  ---> %d (\"%s\" \"%s\")\n",
             pWord->rCost, pWord->zWord, pWord->zCost);
#endif
      pOther = amatchAvlInsert(&pCur->pCost, &pWord->sCost);
      assert( pOther==0 ); (void)pOther;
    }
    return;
  }
  pWord = sqlite3_malloc( sizeof(*pWord) + nBase + nTail - 1 );
  if( pWord==0 ) return;
  memset(pWord, 0, sizeof(*pWord));
  pWord->rCost = rCost;
  pWord->iSeq = pCur->nWord++;
  amatchWriteCost(pWord);
  pWord->nMatch = nMatch;
  pWord->pNext = pCur->pAllWords;
  pCur->pAllWords = pWord;
  pWord->sCost.zKey = pWord->zCost;
  pWord->sCost.pWord = pWord;
  pOther = amatchAvlInsert(&pCur->pCost, &pWord->sCost);
  assert( pOther==0 ); (void)pOther;
  pWord->sWord.zKey = pWord->zWord;
  pWord->sWord.pWord = pWord;
  strcpy(pWord->zWord, pCur->zBuf);
  pOther = amatchAvlInsert(&pCur->pWord, &pWord->sWord);
  assert( pOther==0 ); (void)pOther;
#ifdef AMATCH_TRACE_1
  printf("INSERT [%s][%.*s^%s] %d (\"%s\" \"%s\")\n", pWord->zWord+2,
       pWord->nMatch, pCur->zInput, pCur->zInput+pWord->nMatch, rCost,
       pWord->zWord, pWord->zCost);
#endif
}

/*
** Advance a cursor to its next row of output
*/
static int amatchNext(sqlite3_vtab_cursor *cur){
  amatch_cursor *pCur = (amatch_cursor*)cur;
  amatch_word *pWord = 0;
  amatch_avl *pNode;
  int isMatch = 0;
  amatch_vtab *p = pCur->pVtab;
  int nWord;
  int rc;
  int i;
  const char *zW;
  amatch_rule *pRule;
  char *zBuf = 0;
  char nBuf = 0;
  char zNext[8];
  char zNextIn[8];
  int nNextIn;

  if( p->pVCheck==0 ){
    char *zSql;
    if( p->zVocabLang && p->zVocabLang[0] ){
      zSql = sqlite3_mprintf(
          "SELECT \"%s\" FROM \"%s\"",
          " WHERE \"%w\">=?1 AND \"%w\"=?2"
          " ORDER BY 1",
          p->zVocabWord, p->zVocabTab,
          p->zVocabWord, p->zVocabLang
      );
    }else{
      zSql = sqlite3_mprintf(
          "SELECT \"%s\" FROM \"%s\""
          " WHERE \"%w\">=?1"
          " ORDER BY 1",
          p->zVocabWord, p->zVocabTab,
          p->zVocabWord
      );
    }
    rc = sqlite3_prepare_v2(p->db, zSql, -1, &p->pVCheck, 0);
    sqlite3_free(zSql);
    if( rc ) return rc;
  }
  sqlite3_bind_int(p->pVCheck, 2, pCur->iLang);

  do{
    pNode = amatchAvlFirst(pCur->pCost);
    if( pNode==0 ){
      pWord = 0;
      break;
    }
    pWord = pNode->pWord;
    amatchAvlRemove(&pCur->pCost, &pWord->sCost);

#ifdef AMATCH_TRACE_1
    printf("PROCESS [%s][%.*s^%s] %d (\"%s\" \"%s\")\n",
       pWord->zWord+2, pWord->nMatch, pCur->zInput, pCur->zInput+pWord->nMatch,
       pWord->rCost, pWord->zWord, pWord->zCost);
#endif
    nWord = (int)strlen(pWord->zWord+2);
    if( nWord+20>nBuf ){
      nBuf = nWord+100;
      zBuf = sqlite3_realloc(zBuf, nBuf);
      if( zBuf==0 ) return SQLITE_NOMEM;
    }
    strcpy(zBuf, pWord->zWord+2);
    zNext[0] = 0;
    zNextIn[0] = pCur->zInput[pWord->nMatch];
    if( zNextIn[0] ){
      for(i=1; i<=4 && (pCur->zInput[pWord->nMatch+i]&0xc0)==0x80; i++){
        zNextIn[i] = pCur->zInput[pWord->nMatch+i];
      }
      zNextIn[i] = 0;
      nNextIn = i;
    }else{
      nNextIn = 0;
    }

    if( zNextIn[0] && zNextIn[0]!='*' ){
      sqlite3_reset(p->pVCheck);
      strcat(zBuf, zNextIn);
      sqlite3_bind_text(p->pVCheck, 1, zBuf, nWord+nNextIn, SQLITE_STATIC);
      rc = sqlite3_step(p->pVCheck);
      if( rc==SQLITE_ROW ){
        zW = (const char*)sqlite3_column_text(p->pVCheck, 0);
        if( strncmp(zBuf, zW, nWord+nNextIn)==0 ){
          amatchAddWord(pCur, pWord->rCost, pWord->nMatch+nNextIn, zBuf, "");
        }
      }
      zBuf[nWord] = 0;
    }

    while( 1 ){
      strcpy(zBuf+nWord, zNext);
      sqlite3_reset(p->pVCheck);
      sqlite3_bind_text(p->pVCheck, 1, zBuf, -1, SQLITE_TRANSIENT);
      rc = sqlite3_step(p->pVCheck);
      if( rc!=SQLITE_ROW ) break;
      zW = (const char*)sqlite3_column_text(p->pVCheck, 0);
      strcpy(zBuf+nWord, zNext);
      if( strncmp(zW, zBuf, nWord)!=0 ) break;
      if( (zNextIn[0]=='*' && zNextIn[1]==0)
       || (zNextIn[0]==0 && zW[nWord]==0)
      ){
        isMatch = 1;
        zNextIn[0] = 0;
        nNextIn = 0;
        break;
      }
      zNext[0] = zW[nWord];
      for(i=1; i<=4 && (zW[nWord+i]&0xc0)==0x80; i++){
        zNext[i] = zW[nWord+i];
      }
      zNext[i] = 0;
      zBuf[nWord] = 0;
      if( p->rIns>0 ){
        amatchAddWord(pCur, pWord->rCost+p->rIns, pWord->nMatch, 
                      zBuf, zNext);
      }
      if( p->rSub>0 ){
        amatchAddWord(pCur, pWord->rCost+p->rSub, pWord->nMatch+nNextIn, 
                      zBuf, zNext);
      }
      if( p->rIns<0 && p->rSub<0 ) break;
      zNext[i-1]++;  /* FIX ME */
    }
    sqlite3_reset(p->pVCheck);

    if( p->rDel>0 ){
      zBuf[nWord] = 0;
      amatchAddWord(pCur, pWord->rCost+p->rDel, pWord->nMatch+nNextIn,
                    zBuf, "");
    }

    for(pRule=p->pRule; pRule; pRule=pRule->pNext){
      if( pRule->iLang!=pCur->iLang ) continue;
      if( strncmp(pRule->zFrom, pCur->zInput+pWord->nMatch, pRule->nFrom)==0 ){
        amatchAddWord(pCur, pWord->rCost+pRule->rCost,
                      pWord->nMatch+pRule->nFrom, pWord->zWord+2, pRule->zTo);
      }
    }
  }while( !isMatch );
  pCur->pCurrent = pWord;
  sqlite3_free(zBuf);
  return SQLITE_OK;
}

/*
** Called to "rewind" a cursor back to the beginning so that
** it starts its output over again.  Always called at least once
** prior to any amatchColumn, amatchRowid, or amatchEof call.
*/
static int amatchFilter(
  sqlite3_vtab_cursor *pVtabCursor, 
  int idxNum, const char *idxStr,
  int argc, sqlite3_value **argv
){
  amatch_cursor *pCur = (amatch_cursor *)pVtabCursor;
  const char *zWord = "*";
  int idx;

  amatchClearCursor(pCur);
  idx = 0;
  if( idxNum & 1 ){
    zWord = (const char*)sqlite3_value_text(argv[0]);
    idx++;
  }
  if( idxNum & 2 ){
    pCur->rLimit = (amatch_cost)sqlite3_value_int(argv[idx]);
    idx++;
  }
  if( idxNum & 4 ){
    pCur->iLang = (amatch_cost)sqlite3_value_int(argv[idx]);
    idx++;
  }
  pCur->zInput = sqlite3_mprintf("%s", zWord);
  if( pCur->zInput==0 ) return SQLITE_NOMEM;
  amatchAddWord(pCur, 0, 0, "", "");
  amatchNext(pVtabCursor);

  return SQLITE_OK;
}

/*
** Only the word and distance columns have values.  All other columns
** return NULL
*/
static int amatchColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
  amatch_cursor *pCur = (amatch_cursor*)cur;
  switch( i ){
    case AMATCH_COL_WORD: {
      sqlite3_result_text(ctx, pCur->pCurrent->zWord+2, -1, SQLITE_STATIC);
      break;
    }
    case AMATCH_COL_DISTANCE: {
      sqlite3_result_int(ctx, pCur->pCurrent->rCost);
      break;
    }
    case AMATCH_COL_LANGUAGE: {
      sqlite3_result_int(ctx, pCur->iLang);
      break;
    }
    case AMATCH_COL_NWORD: {
      sqlite3_result_int(ctx, pCur->nWord);
      break;
    }
    default: {
      sqlite3_result_null(ctx);
      break;
    }
  }
  return SQLITE_OK;
}

/*
** The rowid.
*/
static int amatchRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
  amatch_cursor *pCur = (amatch_cursor*)cur;
  *pRowid = pCur->iRowid;
  return SQLITE_OK;
}

/*
** EOF indicator
*/
static int amatchEof(sqlite3_vtab_cursor *cur){
  amatch_cursor *pCur = (amatch_cursor*)cur;
  return pCur->pCurrent==0;
}

/*
** Search for terms of these forms:
**
**   (A)    word MATCH $str
**   (B1)   distance < $value
**   (B2)   distance <= $value
**   (C)    language == $language
**
** The distance< and distance<= are both treated as distance<=.
** The query plan number is a bit vector:
**
**   bit 1:   Term of the form (A) found
**   bit 2:   Term like (B1) or (B2) found
**   bit 3:   Term like (C) found
**
** If bit-1 is set, $str is always in filter.argv[0].  If bit-2 is set
** then $value is in filter.argv[0] if bit-1 is clear and is in 
** filter.argv[1] if bit-1 is set.  If bit-3 is set, then $ruleid is
** in filter.argv[0] if bit-1 and bit-2 are both zero, is in
** filter.argv[1] if exactly one of bit-1 and bit-2 are set, and is in
** filter.argv[2] if both bit-1 and bit-2 are set.
*/
static int amatchBestIndex(
  sqlite3_vtab *tab,
  sqlite3_index_info *pIdxInfo
){
  int iPlan = 0;
  int iDistTerm = -1;
  int iLangTerm = -1;
  int i;
  const struct sqlite3_index_constraint *pConstraint;

  (void)tab;
  pConstraint = pIdxInfo->aConstraint;
  for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
    if( pConstraint->usable==0 ) continue;
    if( (iPlan & 1)==0 
     && pConstraint->iColumn==0
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH
    ){
      iPlan |= 1;
      pIdxInfo->aConstraintUsage[i].argvIndex = 1;
      pIdxInfo->aConstraintUsage[i].omit = 1;
    }
    if( (iPlan & 2)==0
     && pConstraint->iColumn==1
     && (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT
           || pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE)
    ){
      iPlan |= 2;
      iDistTerm = i;
    }
    if( (iPlan & 4)==0
     && pConstraint->iColumn==2
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
    ){
      iPlan |= 4;
      pIdxInfo->aConstraintUsage[i].omit = 1;
      iLangTerm = i;
    }
  }
  if( iPlan & 2 ){
    pIdxInfo->aConstraintUsage[iDistTerm].argvIndex = 1+((iPlan&1)!=0);
  }
  if( iPlan & 4 ){
    int idx = 1;
    if( iPlan & 1 ) idx++;
    if( iPlan & 2 ) idx++;
    pIdxInfo->aConstraintUsage[iLangTerm].argvIndex = idx;
  }
  pIdxInfo->idxNum = iPlan;
  if( pIdxInfo->nOrderBy==1
   && pIdxInfo->aOrderBy[0].iColumn==1
   && pIdxInfo->aOrderBy[0].desc==0
  ){
    pIdxInfo->orderByConsumed = 1;
  }
  pIdxInfo->estimatedCost = (double)10000;
   
  return SQLITE_OK;
}

/*
** The xUpdate() method.  
**
** This implementation disallows DELETE and UPDATE.  The only thing
** allowed is INSERT into the "command" column.
*/
static int amatchUpdate(
  sqlite3_vtab *pVTab,
  int argc,
  sqlite3_value **argv,
  sqlite_int64 *pRowid
){
  amatch_vtab *p = (amatch_vtab*)pVTab;
  const unsigned char *zCmd;
  (void)pRowid;
  if( argc==1 ){
    pVTab->zErrMsg = sqlite3_mprintf("DELETE from %s is not allowed", 
                                      p->zSelf);
    return SQLITE_ERROR;
  }
  if( sqlite3_value_type(argv[0])!=SQLITE_NULL ){
    pVTab->zErrMsg = sqlite3_mprintf("UPDATE of %s is not allowed", 
                                      p->zSelf);
    return SQLITE_ERROR;
  }
  if( sqlite3_value_type(argv[2+AMATCH_COL_WORD])!=SQLITE_NULL
   || sqlite3_value_type(argv[2+AMATCH_COL_DISTANCE])!=SQLITE_NULL
   || sqlite3_value_type(argv[2+AMATCH_COL_LANGUAGE])!=SQLITE_NULL
  ){
    pVTab->zErrMsg = sqlite3_mprintf(
            "INSERT INTO %s allowed for column [command] only", p->zSelf);
    return SQLITE_ERROR;
  }
  zCmd = sqlite3_value_text(argv[2+AMATCH_COL_COMMAND]);
  if( zCmd==0 ) return SQLITE_OK;
  
  return SQLITE_OK;
}

/*
** A virtual table module that implements the "approximate_match".
*/
static sqlite3_module amatchModule = {
  0,                      /* iVersion */
  amatchConnect,          /* xCreate */
  amatchConnect,          /* xConnect */
  amatchBestIndex,        /* xBestIndex */
  amatchDisconnect,       /* xDisconnect */
  amatchDisconnect,       /* xDestroy */
  amatchOpen,             /* xOpen - open a cursor */
  amatchClose,            /* xClose - close a cursor */
  amatchFilter,           /* xFilter - configure scan constraints */
  amatchNext,             /* xNext - advance a cursor */
  amatchEof,              /* xEof - check for end of scan */
  amatchColumn,           /* xColumn - read data */
  amatchRowid,            /* xRowid - read data */
  amatchUpdate,           /* xUpdate */
  0,                      /* xBegin */
  0,                      /* xSync */
  0,                      /* xCommit */
  0,                      /* xRollback */
  0,                      /* xFindMethod */
  0,                      /* xRename */
  0,                      /* xSavepoint */
  0,                      /* xRelease */
  0                       /* xRollbackTo */
};

/*
** Register the amatch virtual table
*/
#ifdef _WIN32
__declspec(dllexport)
#endif
int sqlite3_amatch_init(
  sqlite3 *db, 
  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  int rc = SQLITE_OK;
  SQLITE_EXTENSION_INIT2(pApi);
  (void)pzErrMsg;  /* Not used */
  rc = sqlite3_create_module(db, "approximate_match", &amatchModule, 0);
  return rc;
}

Added ext/misc/closure.c





























































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
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
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
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
438
439
440
441
442
443
444
445
446
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
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
/*
** 2013-04-16
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
**
** This file contains code for a virtual table that finds the transitive
** closure of a parent/child relationship in a real table.  The virtual 
** table is called "transitive_closure".
**
** A transitive_closure virtual table is created like this:
**
**     CREATE VIRTUAL TABLE x USING transitive_closure(
**        tablename=<tablename>,      -- T
**        idcolumn=<columnname>,      -- X
**        parentcolumn=<columnname>   -- P
**     );
**
** When it is created, the new transitive_closure table may be supplied 
** with default values for the name of a table T and columns T.X and T.P.
** The T.X and T.P columns must contain integers.  The ideal case is for 
** T.X to be the INTEGER PRIMARY KEY.  The T.P column should reference
** the T.X column. The row referenced by T.P is the parent of the current row.
**
** The tablename, idcolumn, and parentcolumn supplied by the CREATE VIRTUAL
** TABLE statement may be overridden in individual queries by including
** terms like tablename='newtable', idcolumn='id2', or 
** parentcolumn='parent3' in the WHERE clause of the query.
**
** For efficiency, it is essential that there be an index on the P column:
**
**    CREATE Tidx1 ON T(P)
**
** Suppose a specific instance of the closure table is as follows:
**
**    CREATE VIRTUAL TABLE ct1 USING transitive_closure(
**       tablename='group',
**       idcolumn='groupId',
**       parentcolumn='parentId'
**    );
**
** Such an instance of the transitive_closure virtual table would be
** appropriate for walking a tree defined using a table like this, for example:
**
**    CREATE TABLE group(
**      groupId INTEGER PRIMARY KEY,
**      parentId INTEGER REFERENCES group
**    );
**    CREATE INDEX group_idx1 ON group(parentId);
**
** The group table above would presumably have other application-specific
** fields.  The key point here is that rows of the group table form a
** tree.  The purpose of the ct1 virtual table is to easily extract
** branches of that tree.
**
** Once it has been created, the ct1 virtual table can be queried
** as follows:
**
**    SELECT * FROM element
**     WHERE element.groupId IN (SELECT id FROM ct1 WHERE root=?1);
**
** The above query will return all elements that are part of group ?1
** or children of group ?1 or grand-children of ?1 and so forth for all
** descendents of group ?1.  The same query can be formulated as a join:
**
**    SELECT element.* FROM element, ct1
**     WHERE element.groupid=ct1.id
**       AND ct1.root=?1;
**
** The depth of the transitive_closure (the number of generations of
** parent/child relations to follow) can be limited by setting "depth"
** column in the WHERE clause.  So, for example, the following query
** finds only children and grandchildren but no further descendents:
**
**    SELECT element.* FROM element, ct1
**     WHERE element.groupid=ct1.id
**       AND ct1.root=?1
**       AND ct1.depth<=2;
**
** The "ct1.depth<=2" term could be a strict equality "ct1.depth=2" in
** order to find only the grandchildren of ?1, not ?1 itself or the
** children of ?1.
** 
** The root=?1 term must be supplied in WHERE clause or else the query
** of the ct1 virtual table will return an empty set.  The tablename,
** idcolumn, and parentcolumn attributes can be overridden in the WHERE
** clause if desired.  So, for example, the ct1 table could be repurposed
** to find ancestors rather than descendents by inverting the roles of
** the idcolumn and parentcolumn:
**
**    SELECT element.* FROM element, ct1
**     WHERE element.groupid=ct1.id
**       AND ct1.root=?1
**       AND ct1.idcolumn='parentId'
**       AND ct1.parentcolumn='groupId';
**
** Multiple calls to ct1 could be combined.  For example, the following
** query finds all elements that "cousins" of groupId ?1.  That is to say
** elements where the groupId is a grandchild of the grandparent of ?1.
** (This definition of "cousins" also includes siblings and self.)
**
**    SELECT element.* FROM element, ct1
**     WHERE element.groupId=ct1.id
**       AND ct1.depth=2
**       AND ct1.root IN (SELECT id FROM ct1
**                         WHERE root=?1
**                           AND depth=2
**                           AND idcolumn='parentId'
**                           AND parentcolumn='groupId');
**
** In our example, the group.groupId column is unique and thus the
** subquery will return exactly one row.  For that reason, the IN
** operator could be replaced by "=" to get the same result.  But
** in the general case where the idcolumn is not unique, an IN operator
** would be required for this kind of query.
**
** Note that because the tablename, idcolumn, and parentcolumn can
** all be specified in the query, it is possible for an application
** to define a single transitive_closure virtual table for use on lots
** of different hierarchy tables.  One might say:
**
**     CREATE VIRTUAL TABLE temp.closure USING transitive_closure;
**
** As each database connection is being opened.  Then the application
** would always have a "closure" virtual table handy to use for querying.
**
**    SELECT element.* FROM element, closure
**     WHERE element.groupid=ct1.id
**       AND closure.root=?1
**       AND closure.tablename='group'
**       AND closure.idname='groupId'
**       AND closure.parentname='parentId';
**
** See the documentation at http://www.sqlite.org/loadext.html for information
** on how to compile and use loadable extensions such as this one.
*/
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <ctype.h>

/*
** Forward declaration of objects used by this implementation
*/
typedef struct closure_vtab closure_vtab;
typedef struct closure_cursor closure_cursor;
typedef struct closure_queue closure_queue;
typedef struct closure_avl closure_avl;

/*****************************************************************************
** AVL Tree implementation
*/
/*
** Objects that want to be members of the AVL tree should embedded an
** instance of this structure.
*/
struct closure_avl {
  sqlite3_int64 id;     /* Id of this entry in the table */
  int iGeneration;      /* Which generation is this entry part of */
  closure_avl *pList;   /* A linked list of nodes */
  closure_avl *pBefore; /* Other elements less than id */
  closure_avl *pAfter;  /* Other elements greater than id */
  closure_avl *pUp;     /* Parent element */
  short int height;     /* Height of this node.  Leaf==1 */
  short int imbalance;  /* Height difference between pBefore and pAfter */
};

/* Recompute the closure_avl.height and closure_avl.imbalance fields for p.
** Assume that the children of p have correct heights.
*/
static void closureAvlRecomputeHeight(closure_avl *p){
  short int hBefore = p->pBefore ? p->pBefore->height : 0;
  short int hAfter = p->pAfter ? p->pAfter->height : 0;
  p->imbalance = hBefore - hAfter;  /* -: pAfter higher.  +: pBefore higher */
  p->height = (hBefore>hAfter ? hBefore : hAfter)+1;
}

/*
**     P                B
**    / \              / \
**   B   Z    ==>     X   P
**  / \                  / \
** X   Y                Y   Z
**
*/
static closure_avl *closureAvlRotateBefore(closure_avl *pP){
  closure_avl *pB = pP->pBefore;
  closure_avl *pY = pB->pAfter;
  pB->pUp = pP->pUp;
  pB->pAfter = pP;
  pP->pUp = pB;
  pP->pBefore = pY;
  if( pY ) pY->pUp = pP;
  closureAvlRecomputeHeight(pP);
  closureAvlRecomputeHeight(pB);
  return pB;
}

/*
**     P                A
**    / \              / \
**   X   A    ==>     P   Z
**      / \          / \
**     Y   Z        X   Y
**
*/
static closure_avl *closureAvlRotateAfter(closure_avl *pP){
  closure_avl *pA = pP->pAfter;
  closure_avl *pY = pA->pBefore;
  pA->pUp = pP->pUp;
  pA->pBefore = pP;
  pP->pUp = pA;
  pP->pAfter = pY;
  if( pY ) pY->pUp = pP;
  closureAvlRecomputeHeight(pP);
  closureAvlRecomputeHeight(pA);
  return pA;
}

/*
** Return a pointer to the pBefore or pAfter pointer in the parent
** of p that points to p.  Or if p is the root node, return pp.
*/
static closure_avl **closureAvlFromPtr(closure_avl *p, closure_avl **pp){
  closure_avl *pUp = p->pUp;
  if( pUp==0 ) return pp;
  if( pUp->pAfter==p ) return &pUp->pAfter;
  return &pUp->pBefore;
}

/*
** Rebalance all nodes starting with p and working up to the root.
** Return the new root.
*/
static closure_avl *closureAvlBalance(closure_avl *p){
  closure_avl *pTop = p;
  closure_avl **pp;
  while( p ){
    closureAvlRecomputeHeight(p);
    if( p->imbalance>=2 ){
      closure_avl *pB = p->pBefore;
      if( pB->imbalance<0 ) p->pBefore = closureAvlRotateAfter(pB);
      pp = closureAvlFromPtr(p,&p);
      p = *pp = closureAvlRotateBefore(p);
    }else if( p->imbalance<=(-2) ){
      closure_avl *pA = p->pAfter;
      if( pA->imbalance>0 ) p->pAfter = closureAvlRotateBefore(pA);
      pp = closureAvlFromPtr(p,&p);
      p = *pp = closureAvlRotateAfter(p);
    }
    pTop = p;
    p = p->pUp;
  }
  return pTop;
}

/* Search the tree rooted at p for an entry with id.  Return a pointer
** to the entry or return NULL.
*/
static closure_avl *closureAvlSearch(closure_avl *p, sqlite3_int64 id){
  while( p && id!=p->id ){
    p = (id<p->id) ? p->pBefore : p->pAfter;
  }
  return p;
}

/* Find the first node (the one with the smallest key).
*/
static closure_avl *closureAvlFirst(closure_avl *p){
  if( p ) while( p->pBefore ) p = p->pBefore;
  return p;
}

/* Return the node with the next larger key after p.
*/
closure_avl *closureAvlNext(closure_avl *p){
  closure_avl *pPrev = 0;
  while( p && p->pAfter==pPrev ){
    pPrev = p;
    p = p->pUp;
  }
  if( p && pPrev==0 ){
    p = closureAvlFirst(p->pAfter);
  }
  return p;
}
	
/* Insert a new node pNew.  Return NULL on success.  If the key is not
** unique, then do not perform the insert but instead leave pNew unchanged
** and return a pointer to an existing node with the same key.
*/
static closure_avl *closureAvlInsert(
  closure_avl **ppHead,  /* Head of the tree */
  closure_avl *pNew      /* New node to be inserted */
){
  closure_avl *p = *ppHead;
  if( p==0 ){
    p = pNew;
    pNew->pUp = 0;
  }else{
    while( p ){
      if( pNew->id<p->id ){
        if( p->pBefore ){
          p = p->pBefore;
        }else{
          p->pBefore = pNew;
          pNew->pUp = p;
          break;
        }
      }else if( pNew->id>p->id ){
        if( p->pAfter ){
          p = p->pAfter;
        }else{
          p->pAfter = pNew;
          pNew->pUp = p;
          break;
        }
      }else{
        return p;
      }
    }
  }
  pNew->pBefore = 0;
  pNew->pAfter = 0;
  pNew->height = 1;
  pNew->imbalance = 0;
  *ppHead = closureAvlBalance(p);
  return 0;
}

/* Walk the tree can call xDestroy on each node
*/
static void closureAvlDestroy(closure_avl *p, void (*xDestroy)(closure_avl*)){
  if( p ){
    closureAvlDestroy(p->pBefore, xDestroy);
    closureAvlDestroy(p->pAfter, xDestroy);
    xDestroy(p);
  }
}
/*
** End of the AVL Tree implementation
******************************************************************************/

/* 
** A closure virtual-table object 
*/
struct closure_vtab {
  sqlite3_vtab base;         /* Base class - must be first */
  char *zDb;                 /* Name of database.  (ex: "main") */
  char *zSelf;               /* Name of this virtual table */
  char *zTableName;          /* Name of table holding parent/child relation */
  char *zIdColumn;           /* Name of ID column of zTableName */
  char *zParentColumn;       /* Name of PARENT column in zTableName */
  sqlite3 *db;               /* The database connection */
  int nCursor;               /* Number of pending cursors */
};

/* A closure cursor object */
struct closure_cursor {
  sqlite3_vtab_cursor base;  /* Base class - must be first */
  closure_vtab *pVtab;       /* The virtual table this cursor belongs to */
  char *zTableName;          /* Name of table holding parent/child relation */
  char *zIdColumn;           /* Name of ID column of zTableName */
  char *zParentColumn;       /* Name of PARENT column in zTableName */
  closure_avl *pCurrent;     /* Current element of output */
  closure_avl *pClosure;     /* The complete closure tree */
};

/* A queue of AVL nodes */
struct closure_queue {
  closure_avl *pFirst;       /* Oldest node on the queue */
  closure_avl *pLast;        /* Youngest node on the queue */
};

/*
** Add a node to the end of the queue
*/
static void queuePush(closure_queue *pQueue, closure_avl *pNode){
  pNode->pList = 0;
  if( pQueue->pLast ){
    pQueue->pLast->pList = pNode;
  }else{
    pQueue->pFirst = pNode;
  }
  pQueue->pLast = pNode;
}

/*
** Extract the oldest element (the front element) from the queue.
*/
static closure_avl *queuePull(closure_queue *pQueue){
  closure_avl *p = pQueue->pFirst;
  if( p ){
    pQueue->pFirst = p->pList;
    if( pQueue->pFirst==0 ) pQueue->pLast = 0;
  }
  return p;
}

/*
** This function converts an SQL quoted string into an unquoted string
** and returns a pointer to a buffer allocated using sqlite3_malloc() 
** containing the result. The caller should eventually free this buffer
** using sqlite3_free.
**
** Examples:
**
**     "abc"   becomes   abc
**     'xyz'   becomes   xyz
**     [pqr]   becomes   pqr
**     `mno`   becomes   mno
*/
static char *closureDequote(const char *zIn){
  int nIn;                        /* Size of input string, in bytes */
  char *zOut;                     /* Output (dequoted) string */

  nIn = (int)strlen(zIn);
  zOut = sqlite3_malloc(nIn+1);
  if( zOut ){
    char q = zIn[0];              /* Quote character (if any ) */

    if( q!='[' && q!= '\'' && q!='"' && q!='`' ){
      memcpy(zOut, zIn, nIn+1);
    }else{
      int iOut = 0;               /* Index of next byte to write to output */
      int iIn;                    /* Index of next byte to read from input */

      if( q=='[' ) q = ']';
      for(iIn=1; iIn<nIn; iIn++){
        if( zIn[iIn]==q ) iIn++;
        zOut[iOut++] = zIn[iIn];
      }
    }
    assert( (int)strlen(zOut)<=nIn );
  }
  return zOut;
}

/*
** Deallocate an closure_vtab object
*/
static void closureFree(closure_vtab *p){
  if( p ){
    sqlite3_free(p->zDb);
    sqlite3_free(p->zSelf);
    sqlite3_free(p->zTableName);
    sqlite3_free(p->zIdColumn);
    sqlite3_free(p->zParentColumn);
    memset(p, 0, sizeof(*p));
    sqlite3_free(p);
  }
}

/*
** xDisconnect/xDestroy method for the closure module.
*/
static int closureDisconnect(sqlite3_vtab *pVtab){
  closure_vtab *p = (closure_vtab*)pVtab;
  assert( p->nCursor==0 );
  closureFree(p);
  return SQLITE_OK;
}

/*
** Check to see if the argument is of the form:
**
**       KEY = VALUE
**
** If it is, return a pointer to the first character of VALUE.
** If not, return NULL.  Spaces around the = are ignored.
*/
static const char *closureValueOfKey(const char *zKey, const char *zStr){
  int nKey = (int)strlen(zKey);
  int nStr = (int)strlen(zStr);
  int i;
  if( nStr<nKey+1 ) return 0;
  if( memcmp(zStr, zKey, nKey)!=0 ) return 0;
  for(i=nKey; isspace(zStr[i]); i++){}
  if( zStr[i]!='=' ) return 0;
  i++;
  while( isspace(zStr[i]) ){ i++; }
  return zStr+i;
}

/*
** xConnect/xCreate method for the closure module. Arguments are:
**
**   argv[0]    -> module name  ("approximate_match")
**   argv[1]    -> database name
**   argv[2]    -> table name
**   argv[3...] -> arguments
*/
static int closureConnect(
  sqlite3 *db,
  void *pAux,
  int argc, const char *const*argv,
  sqlite3_vtab **ppVtab,
  char **pzErr
){
  int rc = SQLITE_OK;              /* Return code */
  closure_vtab *pNew = 0;          /* New virtual table */
  const char *zDb = argv[1];
  const char *zVal;
  int i;

  (void)pAux;
  *ppVtab = 0;
  pNew = sqlite3_malloc( sizeof(*pNew) );
  if( pNew==0 ) return SQLITE_NOMEM;
  rc = SQLITE_NOMEM;
  memset(pNew, 0, sizeof(*pNew));
  pNew->db = db;
  pNew->zDb = sqlite3_mprintf("%s", zDb);
  if( pNew->zDb==0 ) goto closureConnectError;
  pNew->zSelf = sqlite3_mprintf("%s", argv[2]);
  if( pNew->zSelf==0 ) goto closureConnectError;
  for(i=3; i<argc; i++){
    zVal = closureValueOfKey("tablename", argv[i]);
    if( zVal ){
      sqlite3_free(pNew->zTableName);
      pNew->zTableName = closureDequote(zVal);
      if( pNew->zTableName==0 ) goto closureConnectError;
      continue;
    }
    zVal = closureValueOfKey("idcolumn", argv[i]);
    if( zVal ){
      sqlite3_free(pNew->zIdColumn);
      pNew->zIdColumn = closureDequote(zVal);
      if( pNew->zIdColumn==0 ) goto closureConnectError;
      continue;
    }
    zVal = closureValueOfKey("parentcolumn", argv[i]);
    if( zVal ){
      sqlite3_free(pNew->zParentColumn);
      pNew->zParentColumn = closureDequote(zVal);
      if( pNew->zParentColumn==0 ) goto closureConnectError;
      continue;
    }
    *pzErr = sqlite3_mprintf("unrecognized argument: [%s]\n", argv[i]);
    closureFree(pNew);
    *ppVtab = 0;
    return SQLITE_ERROR;
  }
  rc = sqlite3_declare_vtab(db,
         "CREATE TABLE x(id,depth,root HIDDEN,tablename HIDDEN,"
                        "idcolumn HIDDEN,parentcolumn HIDDEN)"
       );
#define CLOSURE_COL_ID              0
#define CLOSURE_COL_DEPTH           1
#define CLOSURE_COL_ROOT            2
#define CLOSURE_COL_TABLENAME       3
#define CLOSURE_COL_IDCOLUMN        4
#define CLOSURE_COL_PARENTCOLUMN    5
  if( rc!=SQLITE_OK ){
    closureFree(pNew);
  }
  *ppVtab = &pNew->base;
  return rc;

closureConnectError:
  closureFree(pNew);
  return rc;
}

/*
** Open a new closure cursor.
*/
static int closureOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
  closure_vtab *p = (closure_vtab*)pVTab;
  closure_cursor *pCur;
  pCur = sqlite3_malloc( sizeof(*pCur) );
  if( pCur==0 ) return SQLITE_NOMEM;
  memset(pCur, 0, sizeof(*pCur));
  pCur->pVtab = p;
  *ppCursor = &pCur->base;
  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.
*/
static void closureClearCursor(closure_cursor *pCur){
  closureAvlDestroy(pCur->pClosure, (void(*)(closure_avl*))sqlite3_free);
  sqlite3_free(pCur->zTableName);
  sqlite3_free(pCur->zIdColumn);
  sqlite3_free(pCur->zParentColumn);
  pCur->zTableName = 0;
  pCur->zIdColumn = 0;
  pCur->zParentColumn = 0;
  pCur->pCurrent = 0;
  pCur->pClosure = 0;
}

/*
** Close a closure cursor.
*/
static int closureClose(sqlite3_vtab_cursor *cur){
  closure_cursor *pCur = (closure_cursor *)cur;
  closureClearCursor(pCur);
  pCur->pVtab->nCursor--;
  sqlite3_free(pCur);
  return SQLITE_OK;
}

/*
** Advance a cursor to its next row of output
*/
static int closureNext(sqlite3_vtab_cursor *cur){
  closure_cursor *pCur = (closure_cursor*)cur;
  pCur->pCurrent = closureAvlNext(pCur->pCurrent);
  return SQLITE_OK;
}

/*
** Allocate and insert a node
*/
static int closureInsertNode(
  closure_queue *pQueue,  /* Add new node to this queue */
  closure_cursor *pCur,   /* The cursor into which to add the node */
  sqlite3_int64 id,       /* The node ID */
  int iGeneration         /* The generation number for this node */
){
  closure_avl *pNew = sqlite3_malloc( sizeof(*pNew) );
  if( pNew==0 ) return SQLITE_NOMEM;
  memset(pNew, 0, sizeof(*pNew));
  pNew->id = id;
  pNew->iGeneration = iGeneration;
  closureAvlInsert(&pCur->pClosure, pNew);
  queuePush(pQueue, pNew);
  return SQLITE_OK;
}

/*
** Called to "rewind" a cursor back to the beginning so that
** it starts its output over again.  Always called at least once
** prior to any closureColumn, closureRowid, or closureEof call.
**
** This routine actually computes the closure.
**
** See the comment at the beginning of closureBestIndex() for a 
** description of the meaning of idxNum.  The idxStr parameter is
** not used.
*/
static int closureFilter(
  sqlite3_vtab_cursor *pVtabCursor, 
  int idxNum, const char *idxStr,
  int argc, sqlite3_value **argv
){
  closure_cursor *pCur = (closure_cursor *)pVtabCursor;
  closure_vtab *pVtab = pCur->pVtab;
  sqlite3_int64 iRoot;
  int mxGen = 999999999;
  char *zSql;
  sqlite3_stmt *pStmt;
  closure_avl *pAvl;
  int rc = SQLITE_OK;
  const char *zTableName = pVtab->zTableName;
  const char *zIdColumn = pVtab->zIdColumn;
  const char *zParentColumn = pVtab->zParentColumn;
  closure_queue sQueue;

  (void)idxStr;  /* Unused parameter */
  (void)argc;    /* Unused parameter */
  closureClearCursor(pCur);
  memset(&sQueue, 0, sizeof(sQueue));
  if( (idxNum & 1)==0 ){
    /* No root=$root in the WHERE clause.  Return an empty set */
    return SQLITE_OK;
  }
  iRoot = sqlite3_value_int64(argv[0]);
  if( (idxNum & 0x000f0)!=0 ){
    mxGen = sqlite3_value_int(argv[(idxNum>>4)&0x0f]);
    if( (idxNum & 0x00002)!=0 ) mxGen--;
  }
  if( (idxNum & 0x00f00)!=0 ){
    zTableName = (const char*)sqlite3_value_text(argv[(idxNum>>8)&0x0f]);
    pCur->zTableName = sqlite3_mprintf("%s", zTableName);
  }
  if( (idxNum & 0x0f000)!=0 ){
    zIdColumn = (const char*)sqlite3_value_text(argv[(idxNum>>12)&0x0f]);
    pCur->zIdColumn = sqlite3_mprintf("%s", zIdColumn);
  }
  if( (idxNum & 0x0f0000)!=0 ){
    zParentColumn = (const char*)sqlite3_value_text(argv[(idxNum>>16)&0x0f]);
    pCur->zParentColumn = sqlite3_mprintf("%s", zParentColumn);
  }

  zSql = sqlite3_mprintf(
       "SELECT \"%w\".\"%w\" FROM \"%w\" WHERE \"%w\".\"%w\"=?1",
       zTableName, zIdColumn, zTableName, zTableName, zParentColumn);
  if( zSql==0 ){
    return SQLITE_NOMEM;
  }else{
    rc = sqlite3_prepare_v2(pVtab->db, zSql, -1, &pStmt, 0);
    sqlite3_free(zSql);
    if( rc ){
      sqlite3_free(pVtab->base.zErrMsg);
      pVtab->base.zErrMsg = sqlite3_mprintf("%s", sqlite3_errmsg(pVtab->db));
      return rc;
    }
  }
  if( rc==SQLITE_OK ){
    rc = closureInsertNode(&sQueue, pCur, iRoot, 0);
  }
  while( (pAvl = queuePull(&sQueue))!=0 ){
    if( pAvl->iGeneration>=mxGen ) continue;
    sqlite3_bind_int64(pStmt, 1, pAvl->id);
    while( rc==SQLITE_OK && sqlite3_step(pStmt)==SQLITE_ROW ){
      if( sqlite3_column_type(pStmt,0)==SQLITE_INTEGER ){
        sqlite3_int64 iNew = sqlite3_column_int64(pStmt, 0);
        if( closureAvlSearch(pCur->pClosure, iNew)==0 ){
          rc = closureInsertNode(&sQueue, pCur, iNew, pAvl->iGeneration+1);
        }
      }
    }
    sqlite3_reset(pStmt);
  }
  sqlite3_finalize(pStmt);
  if( rc==SQLITE_OK ){
    pCur->pCurrent = closureAvlFirst(pCur->pClosure);
  }

  return rc;
}

/*
** Only the word and distance columns have values.  All other columns
** return NULL
*/
static int closureColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
  closure_cursor *pCur = (closure_cursor*)cur;
  switch( i ){
    case CLOSURE_COL_ID: {
      sqlite3_result_int64(ctx, pCur->pCurrent->id);
      break;
    }
    case CLOSURE_COL_DEPTH: {
      sqlite3_result_int(ctx, pCur->pCurrent->iGeneration);
      break;
    }
    case CLOSURE_COL_ROOT: {
      sqlite3_result_null(ctx);
      break;
    }
    case CLOSURE_COL_TABLENAME: {
      sqlite3_result_text(ctx,
         pCur->zTableName ? pCur->zTableName : pCur->pVtab->zTableName,
         -1, SQLITE_TRANSIENT);
      break;
    }
    case CLOSURE_COL_IDCOLUMN: {
      sqlite3_result_text(ctx,
         pCur->zIdColumn ? pCur->zIdColumn : pCur->pVtab->zIdColumn,
         -1, SQLITE_TRANSIENT);
      break;
    }
    case CLOSURE_COL_PARENTCOLUMN: {
      sqlite3_result_text(ctx,
         pCur->zParentColumn ? pCur->zParentColumn : pCur->pVtab->zParentColumn,
         -1, SQLITE_TRANSIENT);
      break;
    }
  }
  return SQLITE_OK;
}

/*
** The rowid.  For the closure table, this is the same as the "id" column.
*/
static int closureRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
  closure_cursor *pCur = (closure_cursor*)cur;
  *pRowid = pCur->pCurrent->id;
  return SQLITE_OK;
}

/*
** EOF indicator
*/
static int closureEof(sqlite3_vtab_cursor *cur){
  closure_cursor *pCur = (closure_cursor*)cur;
  return pCur->pCurrent==0;
}

/*
** Search for terms of these forms:
**
**   (A)    root = $root
**   (B1)   depth < $depth
**   (B2)   depth <= $depth
**   (B3)   depth = $depth
**   (C)    tablename = $tablename
**   (D)    idcolumn = $idcolumn
**   (E)    parentcolumn = $parentcolumn
**
** 
**
**   idxNum       meaning
**   ----------   ------------------------------------------------------
**   0x00000001   Term of the form (A) found
**   0x00000002   The term of bit-2 is like (B1)
**   0x000000f0   Index in filter.argv[] of $depth.  0 if not used.
**   0x00000f00   Index in filter.argv[] of $tablename.  0 if not used.
**   0x0000f000   Index in filter.argv[] of $idcolumn.  0 if not used
**   0x000f0000   Index in filter.argv[] of $parentcolumn.  0 if not used.
**
** There must be a term of type (A).  If there is not, then the index type
** is 0 and the query will return an empty set.
*/
static int closureBestIndex(
  sqlite3_vtab *pTab,             /* The virtual table */
  sqlite3_index_info *pIdxInfo    /* Information about the query */
){
  int iPlan = 0;
  int i;
  int idx = 1;
  const struct sqlite3_index_constraint *pConstraint;
  closure_vtab *pVtab = (closure_vtab*)pTab;

  pConstraint = pIdxInfo->aConstraint;
  for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
    if( pConstraint->usable==0 ) continue;
    if( (iPlan & 1)==0 
     && pConstraint->iColumn==CLOSURE_COL_ROOT
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
    ){
      iPlan |= 1;
      pIdxInfo->aConstraintUsage[i].argvIndex = 1;
      pIdxInfo->aConstraintUsage[i].omit = 1;
    }
    if( (iPlan & 0x0000f0)==0
     && pConstraint->iColumn==CLOSURE_COL_DEPTH
     && (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT
           || pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE
           || pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ)
    ){
      iPlan |= idx<<4;
      pIdxInfo->aConstraintUsage[i].argvIndex = ++idx;
      if( pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT ) iPlan |= 0x000002;
    }
    if( (iPlan & 0x000f00)==0
     && pConstraint->iColumn==CLOSURE_COL_TABLENAME
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
    ){
      iPlan |= idx<<8;
      pIdxInfo->aConstraintUsage[i].argvIndex = ++idx;
      pIdxInfo->aConstraintUsage[i].omit = 1;
    }
    if( (iPlan & 0x00f000)==0
     && pConstraint->iColumn==CLOSURE_COL_IDCOLUMN
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
    ){
      iPlan |= idx<<12;
      pIdxInfo->aConstraintUsage[i].argvIndex = ++idx;
      pIdxInfo->aConstraintUsage[i].omit = 1;
    }
    if( (iPlan & 0x0f0000)==0
     && pConstraint->iColumn==CLOSURE_COL_PARENTCOLUMN
     && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ
    ){
      iPlan |= idx<<16;
      pIdxInfo->aConstraintUsage[i].argvIndex = ++idx;
      pIdxInfo->aConstraintUsage[i].omit = 1;
    }
  }
  if( (pVtab->zTableName==0    && (iPlan & 0x000f00)==0)
   || (pVtab->zIdColumn==0     && (iPlan & 0x00f000)==0)
   || (pVtab->zParentColumn==0 && (iPlan & 0x0f0000)==0)
  ){
    /* All of tablename, idcolumn, and parentcolumn must be specified
    ** in either the CREATE VIRTUAL TABLE or in the WHERE clause constraints
    ** or else the result is an empty set. */
    iPlan = 0;
  }
  pIdxInfo->idxNum = iPlan;
  if( pIdxInfo->nOrderBy==1
   && pIdxInfo->aOrderBy[0].iColumn==CLOSURE_COL_ID
   && pIdxInfo->aOrderBy[0].desc==0
  ){
    pIdxInfo->orderByConsumed = 1;
  }
  pIdxInfo->estimatedCost = (double)10000;
   
  return SQLITE_OK;
}

/*
** A virtual table module that implements the "approximate_match".
*/
static sqlite3_module closureModule = {
  0,                      /* iVersion */
  closureConnect,         /* xCreate */
  closureConnect,         /* xConnect */
  closureBestIndex,       /* xBestIndex */
  closureDisconnect,      /* xDisconnect */
  closureDisconnect,      /* xDestroy */
  closureOpen,            /* xOpen - open a cursor */
  closureClose,           /* xClose - close a cursor */
  closureFilter,          /* xFilter - configure scan constraints */
  closureNext,            /* xNext - advance a cursor */
  closureEof,             /* xEof - check for end of scan */
  closureColumn,          /* xColumn - read data */
  closureRowid,           /* xRowid - read data */
  0,                      /* xUpdate */
  0,                      /* xBegin */
  0,                      /* xSync */
  0,                      /* xCommit */
  0,                      /* xRollback */
  0,                      /* xFindMethod */
  0,                      /* xRename */
  0,                      /* xSavepoint */
  0,                      /* xRelease */
  0                       /* xRollbackTo */
};

/*
** Register the closure virtual table
*/
#ifdef _WIN32
__declspec(dllexport)
#endif
int sqlite3_closure_init(
  sqlite3 *db, 
  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  int rc = SQLITE_OK;
  SQLITE_EXTENSION_INIT2(pApi);
  (void)pzErrMsg;
  rc = sqlite3_create_module(db, "transitive_closure", &closureModule, 0);
  return rc;
}

Added ext/misc/editdist3.wiki





































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
<title>The editdist3 algorithm</title>

The editdist3 algorithm is a function that computes the minimum edit distance
(a.k.a. the Levenshtein distance) between two input strings.  Features of
editdist3 include:

   *   It works with unicode (UTF8) text.

   *   A table of insertion, deletion, and substitution costs can be 
       provided by the application.

   *   Multi-character insertsions, deletions, and substitutions can be
       enumerated in the cost table.

<h2>The COST table</h2>

To program the costs of editdist3, create a table such as the following:

<blockquote><pre>
CREATE TABLE editcost(
  iLang INT,   -- The language ID
  cFrom TEXT,  -- Convert text from this
  cTo   TEXT,  -- Convert text into this
  iCost INT    -- The cost of doing the conversionnn
);
</pre></blockquote>

The cost table can be named anything you want - it does not have to be called
"editcost".  And the table can contain additional columns.  However, it the
table must contain the four columns show above, with exactly the names shown.

The iLang column is a non-negative integer that identifies a set of costs
appropriate for a particular language.  The editdist3 function will only use
a single iLang value for any given edit-distance computation.  The default
value is 0.  It is recommended that applications that only need to use a
single langauge always use iLang==0 for all entries.

The iCost column is the numeric cost of transforming cFrom into cTo.  This
value should be a non-negative integer, and should probably be less than 100.
The default single-character insertion and deletion costs are 100 and the
default single-character to single-character substitution cost is 150.  A
cost of 10000 or more is considered "infinite" and causes the rule to be
ignored.

The cFrom and cTo columns show edit transformation strings.  Either or both
columns may contain more than one character.  Or either column (but not both)
may hold an empty string.  When cFrom is empty, that is the cost of inserting
cTo.  When cTo is empty, that is the cost of deleting cFrom.

In the spellfix1 algorithm, cFrom is the text as the user entered it and
cTo is the correctly spelled text as it exists in the database.  The goal
of the editdist3 algorithm is to determine how close the user-entered text is
to the dictionary text.

There are three special-case entries in the cost table:

<table border=1>
<tr><th>cFrom</th><th>cTo</th><th>Meaning</th></tr>
<tr><td>''</td><td>'?'</td><td>The default insertion cost</td></tr>
<tr><td>'?'</td><td>''</td><td>The default deletion cost</td></tr>
<tr><td>'?'</td><td>'?'</td><td>The default substitution cost</td></tr>
</table>

If any of the special-case entries shows above are omitted, then the
value of 100 is used for insertion and deletion and 150 is used for
substitution.  To disable the default insertion, deletion, and/or substitution
set their respective cost to 10000 or more.

Other entries in the cost table specific transforms for particular characters.
The cost of specific transforms should be less than the default costs, or else
the default costs will take precedence and the specific transforms will never 
be used.

Some example, cost table entries:

<blockquote><pre>
INSERT INTO editcost(iLang, cFrom, cTo, iCost)
VALUES(0, 'a', 'ä', 5);
</pre></blockquote>

The rule above says that the letter "a" in user input can be matched against
the letter "ä" in the dictionary with a penalty of 5.

<blockquote><pre>
INSERT INTO editcost(iLang, cFrom, cTo, iCost)
VALUES(0, 'ss', 'ß', 8);
</pre></blockquote>

The number of characters in cFrom and cTo do not need to be the same.  The
rule above says that "ss" on user input will match "ß" with a penalty of 8.

<h2>Experimenting with the editcost3() function</h2>

The [./spellfix1.wiki | spellfix1 virtual table]
uses editdist3 if the "edit_cost_table=TABLE" option
is specified as an argument when the spellfix1 virtual table is created.  
But editdist3 can also be tested directly using the built-in "editdist3()"
SQL function.  The editdist3() SQL function has 3 forms:

  1.  editdist3('TABLENAME');
  2.  editdist3('string1', 'string2');
  3.  editdist3('string1', 'string2', langid);

The first form loads the edit distance coefficients from a table called
'TABLENAME'.  Any prior coefficients are discarded.  So when experimenting
with weights and the weight table changes, simply rerun the single-argument
form of editdist3() to reload revised coefficients.  Note that the 
edit distance
weights used by the editdist3() SQL function are independent from the
weights used by the spellfix1 virtual table.

The second and third forms return the computed edit distance between strings
'string1' and "string2'.  In the second form, an language id of 0 is used.
The language id is specified in the third form.

Name change from src/test_fuzzer.c to ext/misc/fuzzer.c

137
138
139
140
141
142
143


144
145
146
147
148
149
150
151
152
153
154
155
156
157
....
1151
1152
1153
1154
1155
1156
1157
1158

1159
1160


1161



1162
1163

1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
**
** LIMITS
**
** The maximum ruleset number is 2147483647.  The maximum length of either
** of the strings in the second or third column of the fuzzer data table
** is 50 bytes.  The maximum cost on a rule is 1000.
*/



/* If SQLITE_DEBUG is not defined, disable assert statements. */
#if !defined(NDEBUG) && !defined(SQLITE_DEBUG)
# define NDEBUG
#endif

#include "sqlite3.h"
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>

#ifndef SQLITE_OMIT_VIRTUALTABLE

................................................................................
  0,                           /* xFindMethod */
  0,                           /* xRename */
};

#endif /* SQLITE_OMIT_VIRTUALTABLE */


/*

** Register the fuzzer virtual table
*/


int fuzzer_register(sqlite3 *db){



  int rc = SQLITE_OK;
#ifndef SQLITE_OMIT_VIRTUALTABLE

  rc = sqlite3_create_module(db, "fuzzer", &fuzzerModule, 0);
#endif
  return rc;
}

#ifdef SQLITE_TEST
#include <tcl.h>
/*
** Decode a pointer to an sqlite3 object.
*/
extern int getDbPointer(Tcl_Interp *interp, const char *zA, sqlite3 **ppDb);

/*
** Register the echo virtual table module.
*/
static int register_fuzzer_module(
  ClientData clientData, /* Pointer to sqlite3_enable_XXX function */
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int objc,              /* Number of arguments */
  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.
*/
int Sqlitetestfuzzer_Init(Tcl_Interp *interp){
  static struct {
     char *zName;
     Tcl_ObjCmdProc *xProc;
     void *clientData;
  } aObjCmd[] = {
     { "register_fuzzer_module",   register_fuzzer_module, 0 },
  };
  int i;
  for(i=0; i<sizeof(aObjCmd)/sizeof(aObjCmd[0]); i++){
    Tcl_CreateObjCommand(interp, aObjCmd[i].zName, 
        aObjCmd[i].xProc, aObjCmd[i].clientData, 0);
  }
  return TCL_OK;
}

#endif /* SQLITE_TEST */







>
>






<







 







<
>
|
<
>
>
|
>
>
>

<
>

<


<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

152
153
154
155
156
157
158
....
1152
1153
1154
1155
1156
1157
1158

1159
1160

1161
1162
1163
1164
1165
1166
1167

1168
1169

1170
1171
















































**
** LIMITS
**
** The maximum ruleset number is 2147483647.  The maximum length of either
** of the strings in the second or third column of the fuzzer data table
** is 50 bytes.  The maximum cost on a rule is 1000.
*/
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1

/* If SQLITE_DEBUG is not defined, disable assert statements. */
#if !defined(NDEBUG) && !defined(SQLITE_DEBUG)
# define NDEBUG
#endif


#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>

#ifndef SQLITE_OMIT_VIRTUALTABLE

................................................................................
  0,                           /* xFindMethod */
  0,                           /* xRename */
};

#endif /* SQLITE_OMIT_VIRTUALTABLE */



#ifdef _WIN32
__declspec(dllexport)

#endif
int sqlite3_fuzzer_init(
  sqlite3 *db, 
  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  int rc = SQLITE_OK;

  SQLITE_EXTENSION_INIT2(pApi);
  rc = sqlite3_create_module(db, "fuzzer", &fuzzerModule, 0);

  return rc;
}
















































Added ext/misc/ieee754.c







































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
/*
** 2013-04-17
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
******************************************************************************
**
** This SQLite extension implements functions for the exact display
** and input of IEEE754 Binary64 floating-point numbers.
**
**   ieee754(X)
**   ieee754(Y,Z)
**
** In the first form, the value X should be a floating-point number.
** The function will return a string of the form 'ieee754(Y,Z)' where
** Y and Z are integers such that X==Y*pow(w.0,Z).
**
** In the second form, Y and Z are integers which are the mantissa and
** base-2 exponent of a new floating point number.  The function returns
** a floating-point value equal to Y*pow(2.0,Z).
**
** Examples:
**
**     ieee754(2.0)       ->     'ieee754(2,0)'
**     ieee754(45.25)     ->     'ieee754(181,-2)'
**     ieee754(2, 0)      ->     2.0
**     ieee754(181, -2)   ->     45.25
*/
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1
#include <assert.h>
#include <string.h>

/*
** Implementation of the ieee754() function
*/
static void ieee754func(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  if( argc==1 ){
    sqlite3_int64 m, a;
    double r;
    int e;
    int isNeg;
    char zResult[100];
    assert( sizeof(m)==sizeof(r) );
    if( sqlite3_value_type(argv[0])!=SQLITE_FLOAT ) return;
    r = sqlite3_value_double(argv[0]);
    if( r<0.0 ){
      isNeg = 1;
      r = -r;
    }else{
      isNeg = 0;
    }
    memcpy(&a,&r,sizeof(a));
    if( a==0 ){
      e = 0;
      m = 0;
    }else{
      e = a>>52;
      m = a & ((((sqlite3_int64)1)<<52)-1);
      m |= ((sqlite3_int64)1)<<52;
      while( e<1075 && m>0 && (m&1)==0 ){
        m >>= 1;
        e++;
      }
      if( isNeg ) m = -m;
    }
    sqlite3_snprintf(sizeof(zResult), zResult, "ieee754(%lld,%d)",
                     m, e-1075);
    sqlite3_result_text(context, zResult, -1, SQLITE_TRANSIENT);
  }else if( argc==2 ){
    sqlite3_int64 m, e, a;
    double r;
    int isNeg = 0;
    m = sqlite3_value_int64(argv[0]);
    e = sqlite3_value_int64(argv[1]);
    if( m<0 ){
      isNeg = 1;
      m = -m;
      if( m<0 ) return;
    }else if( m==0 && e>1000 && e<1000 ){
      sqlite3_result_double(context, 0.0);
      return;
    }
    while( (m>>32)&0xffe00000 ){
      m >>= 1;
      e++;
    }
    while( ((m>>32)&0xfff00000)==0 ){
      m <<= 1;
      e--;
    }
    e += 1075;
    if( e<0 ) e = m = 0;
    if( e>0x7ff ) m = 0;
    a = m & ((((sqlite3_int64)1)<<52)-1);
    a |= e<<52;
    if( isNeg ) a |= ((sqlite3_int64)1)<<63;
    memcpy(&r, &a, sizeof(r));
    sqlite3_result_double(context, r);
  }
}


#ifdef _WIN32
__declspec(dllexport)
#endif
int sqlite3_ieee_init(
  sqlite3 *db, 
  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  int rc = SQLITE_OK;
  SQLITE_EXTENSION_INIT2(pApi);
  (void)pzErrMsg;  /* Unused parameter */
  rc = sqlite3_create_function(db, "ieee754", 1, SQLITE_UTF8, 0,
                               ieee754func, 0, 0);
  if( rc==SQLITE_OK ){
    rc = sqlite3_create_function(db, "ieee754", 2, SQLITE_UTF8, 0,
                                 ieee754func, 0, 0);
  }
  return rc;
}

Added ext/misc/nextchar.c



















































































































































































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
/*
** 2013-02-28
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
******************************************************************************
**
** This file contains code to implement the next_char(A,T,F,W) SQL function.
**
** The next_char(A,T,F,H) function finds all valid "next" characters for
** string A given the vocabulary in T.F.  The T.F field should be indexed.
** If the W value exists and is a non-empty string, then it is an SQL
** expression that limits the entries in T.F that will be considered.
**
** For example, suppose an application has a dictionary like this:
**
**   CREATE TABLE dictionary(word TEXT UNIQUE);
**
** Further suppose that for user keypad entry, it is desired to disable
** (gray out) keys that are not valid as the next character.  If the
** the user has previously entered (say) 'cha' then to find all allowed
** next characters (and thereby determine when keys should not be grayed
** out) run the following query:
**
**   SELECT next_char('cha','dictionary','word');
*/
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1
#include <string.h>

/*
** A structure to hold context of the next_char() computation across
** nested function calls.
*/
typedef struct nextCharContext nextCharContext;
struct nextCharContext {
  sqlite3 *db;                      /* Database connection */
  sqlite3_stmt *pStmt;              /* Prepared statement used to query */
  const unsigned char *zPrefix;     /* Prefix to scan */
  int nPrefix;                      /* Size of zPrefix in bytes */
  int nAlloc;                       /* Space allocated to aResult */
  int nUsed;                        /* Space used in aResult */
  unsigned int *aResult;            /* Array of next characters */
  int mallocFailed;                 /* True if malloc fails */
  int otherError;                   /* True for any other failure */
};

/*
** Append a result character if the character is not already in the
** result.
*/
static void nextCharAppend(nextCharContext *p, unsigned c){
  int i;
  for(i=0; i<p->nUsed; i++){
    if( p->aResult[i]==c ) return;
  }
  if( p->nUsed+1 > p->nAlloc ){
    unsigned int *aNew;
    int n = p->nAlloc*2 + 30;
    aNew = sqlite3_realloc(p->aResult, n*sizeof(unsigned int));
    if( aNew==0 ){
      p->mallocFailed = 1;
      return;
    }else{
      p->aResult = aNew;
      p->nAlloc = n;
    }
  }
  p->aResult[p->nUsed++] = c;
}

/*
** Write a character into z[] as UTF8.  Return the number of bytes needed
** to hold the character
*/
static int writeUtf8(unsigned char *z, unsigned c){
  if( c<0x00080 ){
    z[0] = (unsigned char)(c&0xff);
    return 1;
  }
  if( c<0x00800 ){
    z[0] = 0xC0 + (unsigned char)((c>>6)&0x1F);
    z[1] = 0x80 + (unsigned char)(c & 0x3F);
    return 2;
  }
  if( c<0x10000 ){
    z[0] = 0xE0 + (unsigned char)((c>>12)&0x0F);
    z[1] = 0x80 + (unsigned char)((c>>6) & 0x3F);
    z[2] = 0x80 + (unsigned char)(c & 0x3F);
    return 3;
  }
  z[0] = 0xF0 + (unsigned char)((c>>18) & 0x07);
  z[1] = 0x80 + (unsigned char)((c>>12) & 0x3F);
  z[2] = 0x80 + (unsigned char)((c>>6) & 0x3F);
  z[3] = 0x80 + (unsigned char)(c & 0x3F);
  return 4;
}

/*
** Read a UTF8 character out of z[] and write it into *pOut.  Return
** the number of bytes in z[] that were used to construct the character.
*/
static int readUtf8(const unsigned char *z, unsigned *pOut){
  static const unsigned char validBits[] = {
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
    0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
    0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
    0x00, 0x01, 0x02, 0x03, 0x00, 0x01, 0x00, 0x00,
  };
  unsigned c = z[0];
  if( c<0xc0 ){
    *pOut = c;
    return 1;
  }else{
    int n = 1;
    c = validBits[c-0xc0];
    while( (z[n] & 0xc0)==0x80 ){
      c = (c<<6) + (0x3f & z[n++]);
    }
    if( c<0x80 || (c&0xFFFFF800)==0xD800 || (c&0xFFFFFFFE)==0xFFFE ){
      c = 0xFFFD;
    }
    *pOut = c;
    return n;
  }
}

/*
** The nextCharContext structure has been set up.  Add all "next" characters
** to the result set.
*/
static void findNextChars(nextCharContext *p){
  unsigned cPrev = 0;
  unsigned char zPrev[8];
  int n, rc;
  
  for(;;){
    sqlite3_bind_text(p->pStmt, 1, (char*)p->zPrefix, p->nPrefix,
                      SQLITE_STATIC);
    n = writeUtf8(zPrev, cPrev+1);
    sqlite3_bind_text(p->pStmt, 2, (char*)zPrev, n, SQLITE_STATIC);
    rc = sqlite3_step(p->pStmt);
    if( rc==SQLITE_DONE ){
      sqlite3_reset(p->pStmt);
      return;
    }else if( rc!=SQLITE_ROW ){
      p->otherError = rc;
      return;
    }else{
      const unsigned char *zOut = sqlite3_column_text(p->pStmt, 0);
      unsigned cNext;
      n = readUtf8(zOut+p->nPrefix, &cNext);
      sqlite3_reset(p->pStmt);
      nextCharAppend(p, cNext);
      cPrev = cNext;
      if( p->mallocFailed ) return;
    }
  }
}


/*
** next_character(A,T,F,W)
**
** Return a string composted of all next possible characters after
** A for elements of T.F.  If W is supplied, then it is an SQL expression
** that limits the elements in T.F that are considered.
*/
static void nextCharFunc(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  nextCharContext c;
  const unsigned char *zTable = sqlite3_value_text(argv[1]);
  const unsigned char *zField = sqlite3_value_text(argv[2]);
  const unsigned char *zWhere;
  char *zSql;
  int rc;

  memset(&c, 0, sizeof(c));
  c.db = sqlite3_context_db_handle(context);
  c.zPrefix = sqlite3_value_text(argv[0]);
  c.nPrefix = sqlite3_value_bytes(argv[0]);
  if( zTable==0 || zField==0 || c.zPrefix==0 ) return;
  if( argc<4
   || (zWhere = sqlite3_value_text(argv[3]))==0
   || zWhere[0]==0
  ){
    zSql = sqlite3_mprintf(
        "SELECT \"%w\" FROM \"%w\""
        " WHERE \"%w\">=(?1 || ?2)"
        "   AND \"%w\"<=(?1 || char(1114111))" /* 1114111 == 0x10ffff */
        " ORDER BY 1 ASC LIMIT 1",
        zField, zTable, zField, zField);
  }else{
    zSql = sqlite3_mprintf(
        "SELECT \"%w\" FROM \"%w\""
        " WHERE \"%w\">=(?1 || ?2)"
        "   AND \"%w\"<=(?1 || char(1114111))" /* 1114111 == 0x10ffff */
        "   AND (%s)"
        " ORDER BY 1 ASC LIMIT 1",
        zField, zTable, zField, zField, zWhere);
  }
  if( zSql==0 ){
    sqlite3_result_error_nomem(context);
    return;
  }

  rc = sqlite3_prepare_v2(c.db, zSql, -1, &c.pStmt, 0);
  sqlite3_free(zSql);
  if( rc ){
    sqlite3_result_error(context, sqlite3_errmsg(c.db), -1);
    return;
  }
  findNextChars(&c);
  if( c.mallocFailed ){
    sqlite3_result_error_nomem(context);
  }else{
    unsigned char *pRes;
    pRes = sqlite3_malloc( c.nUsed*4 + 1 );
    if( pRes==0 ){
      sqlite3_result_error_nomem(context);
    }else{
      int i;
      int n = 0;
      for(i=0; i<c.nUsed; i++){
        n += writeUtf8(pRes+n, c.aResult[i]);
      }
      pRes[n] = 0;
      sqlite3_result_text(context, (const char*)pRes, n, sqlite3_free);
    }
  }
  sqlite3_finalize(c.pStmt);
  sqlite3_free(c.aResult);
}

#ifdef _WIN32
__declspec(dllexport)
#endif
int sqlite3_nextchar_init(
  sqlite3 *db, 
  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  int rc = SQLITE_OK;
  SQLITE_EXTENSION_INIT2(pApi);
  (void)pzErrMsg;  /* Unused parameter */
  rc = sqlite3_create_function(db, "next_char", 3, SQLITE_UTF8, 0,
                               nextCharFunc, 0, 0);
  if( rc==SQLITE_OK ){
    rc = sqlite3_create_function(db, "next_char", 4, SQLITE_UTF8, 0,
                                 nextCharFunc, 0, 0);
  }
  return rc;
}

Name change from src/test_regexp.c to ext/misc/regexp.c

8
9
10
11
12
13
14
15









16
17
18
19
20
21
22
..
45
46
47
48
49
50
51
52










53
54
55
56
57
58
59
...
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
...
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730




731





732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
******************************************************************************
**
** The code in this file implements a compact but reasonably
** efficient regular-expression matcher for posix extended regular
** expressions against UTF8 text.  The following syntax is supported:









**
**     X*      zero or more occurrences of X
**     X+      one or more occurrences of X
**     X?      zero or one occurrences of X
**     X{p,q}  between p and q occurrences of X
**     (X)     match X
**     X|Y     X or Y
................................................................................
** exhibits exponential behavior.  Note that the X{p,q} operator expands
** to p copies of X following by q-p copies of X? and that the size of the
** regular expression in the O(N*M) performance bound is computed after
** this expansion.
*/
#include <string.h>
#include <stdlib.h>
#include "sqlite3.h"











/* The end-of-input character */
#define RE_EOF            0    /* End of input */

/* The NFA is implemented as sequence of opcodes taken from the following
** set.  Each opcode has a single integer argument.
*/
................................................................................
static int re_space_char(int c){
  return c==' ' || c=='\t' || c=='\n' || c=='\r' || c=='\v' || c=='\f';
}

/* Run a compiled regular expression on the zero-terminated input
** string zIn[].  Return true on a match and false if there is no match.
*/
int re_match(ReCompiled *pRe, const unsigned char *zIn, int nIn){
  ReStateSet aStateSet[2], *pThis, *pNext;
  ReStateNumber aSpace[100];
  ReStateNumber *pToFree;
  unsigned int i = 0;
  unsigned int iSwap = 0;
  int c = RE_EOF+1;
  int cPrev = 0;
................................................................................
  zStr = (const unsigned char*)sqlite3_value_text(argv[1]);
  if( zStr!=0 ){
    sqlite3_result_int(context, re_match(pRe, zStr, -1));
  }
}

/*
** Invoke this routine in order to install the REGEXP function in an
** SQLite database connection.
**
** Use:
**
**      sqlite3_auto_extension(sqlite3_add_regexp_func);
**
** to cause this extension to be automatically loaded into each new
** database connection.
*/




int sqlite3_add_regexp_func(sqlite3 *db){





  return sqlite3_create_function(db, "regexp", 2, SQLITE_UTF8, 0,
                                 re_sql_func, 0, 0);
}


/***************************** Test Code ***********************************/
#ifdef SQLITE_TEST
#include <tcl.h>
extern int getDbPointer(Tcl_Interp *interp, const char *zA, sqlite3 **ppDb);

/* Implementation of the TCL command:
**
**      sqlite3_add_regexp_func $DB
*/
static int tclSqlite3AddRegexpFunc(
  void * clientData,
  Tcl_Interp *interp,
  int objc,
  Tcl_Obj *CONST objv[]
){
  sqlite3 *db;
  if( objc!=2 ){
    Tcl_WrongNumArgs(interp, 1, objv, "DB");
    return TCL_ERROR;
  }
  if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;
  sqlite3_add_regexp_func(db);
  return TCL_OK;
}

/* Register the sqlite3_add_regexp_func TCL command with the TCL interpreter.
*/
int Sqlitetestregexp_Init(Tcl_Interp *interp){
  Tcl_CreateObjCommand(interp, "sqlite3_add_regexp_func",
                       tclSqlite3AddRegexpFunc, 0, 0);
  return TCL_OK;
}
#endif /* SQLITE_TEST */
/**************************** End Of Test Code *******************************/







|
>
>
>
>
>
>
>
>
>







 







|
>
>
>
>
>
>
>
>
>
>







 







|







 







|

<
<
<
<
<
<
<

>
>
>
>
|
>
>
>
>
>
|

<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
|

<
<
<
<
<
<
<
<
<
<
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
..
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
...
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
...
733
734
735
736
737
738
739
740
741







742
743
744
745
746
747
748
749
750
751
752
753
754

























755
756










**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
******************************************************************************
**
** The code in this file implements a compact but reasonably
** efficient regular-expression matcher for posix extended regular
** expressions against UTF8 text.
**
** This file is an SQLite extension.  It registers a single function
** named "regexp(A,B)" where A is the regular expression and B is the
** string to be matched.  By registering this function, SQLite will also
** then implement the "B regexp A" operator.  Note that with the function
** the regular expression comes first, but with the operator it comes
** second.
**
**  The following regular expression syntax is supported:
**
**     X*      zero or more occurrences of X
**     X+      one or more occurrences of X
**     X?      zero or one occurrences of X
**     X{p,q}  between p and q occurrences of X
**     (X)     match X
**     X|Y     X or Y
................................................................................
** exhibits exponential behavior.  Note that the X{p,q} operator expands
** to p copies of X following by q-p copies of X? and that the size of the
** regular expression in the O(N*M) performance bound is computed after
** this expansion.
*/
#include <string.h>
#include <stdlib.h>
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1

/*
** The following #defines change the names of some functions implemented in
** this file to prevent name collisions with C-library functions of the
** same name.
*/
#define re_match   sqlite3re_match
#define re_compile sqlite3re_compile
#define re_free    sqlite3re_free

/* The end-of-input character */
#define RE_EOF            0    /* End of input */

/* The NFA is implemented as sequence of opcodes taken from the following
** set.  Each opcode has a single integer argument.
*/
................................................................................
static int re_space_char(int c){
  return c==' ' || c=='\t' || c=='\n' || c=='\r' || c=='\v' || c=='\f';
}

/* Run a compiled regular expression on the zero-terminated input
** string zIn[].  Return true on a match and false if there is no match.
*/
static int re_match(ReCompiled *pRe, const unsigned char *zIn, int nIn){
  ReStateSet aStateSet[2], *pThis, *pNext;
  ReStateNumber aSpace[100];
  ReStateNumber *pToFree;
  unsigned int i = 0;
  unsigned int iSwap = 0;
  int c = RE_EOF+1;
  int cPrev = 0;
................................................................................
  zStr = (const unsigned char*)sqlite3_value_text(argv[1]);
  if( zStr!=0 ){
    sqlite3_result_int(context, re_match(pRe, zStr, -1));
  }
}

/*
** Invoke this routine to register the regexp() function with the
** SQLite database connection.







*/
#ifdef _WIN32
__declspec(dllexport)
#endif
int sqlite3_regexp_init(
  sqlite3 *db, 
  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  int rc = SQLITE_OK;
  SQLITE_EXTENSION_INIT2(pApi);
  rc = sqlite3_create_function(db, "regexp", 2, SQLITE_UTF8, 0,
                                 re_sql_func, 0, 0);

























  return rc;
}










Name change from src/test_spellfix.c to ext/misc/spellfix.c

10
11
12
13
14
15
16
17
18
19

20
21
22
23
24
25
26
27
28
29
30
31

32
33
34
35
36
37
38
....
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838



2839
2840
2841
2842
2843
2844
2845
2846
2847
**
*************************************************************************
**
** This module implements the spellfix1 VIRTUAL TABLE that can be used
** to search a large vocabulary for close matches.  See separate
** documentation files (spellfix1.wiki and editdist3.wiki) for details.
*/
#if SQLITE_CORE
# include "sqliteInt.h"
#else

# include <string.h>
# include <stdio.h>
# include <stdlib.h>
# include "sqlite3ext.h"
# include <assert.h>
# define ALWAYS(X)  1
# define NEVER(X)   0
  typedef unsigned char u8;
  typedef unsigned short u16;
  SQLITE_EXTENSION_INIT1
#endif /* !SQLITE_CORE */
#include <ctype.h>


/*
** Character classes for ASCII characters:
**
**   0   ''        Silent letters:   H W
**   1   'A'       Any vowel:   A E I O U (Y)
**   2   'B'       A bilabeal stop or fricative:  B F P V W
................................................................................
  for(i=0; i<sizeof(translit)/sizeof(translit[0])-1; i++){
    assert( translit[i].cFrom<translit[i+1].cFrom );
  }

  return rc;
}

#if SQLITE_CORE || defined(SQLITE_TEST)
/*
** Register the spellfix1 virtual table and its associated functions.
*/
int sqlite3_spellfix1_register(sqlite3 *db){
  return spellfix1Register(db);
}
#endif


#if !SQLITE_CORE
/*
** Extension load function.
*/



int sqlite3_spellfix1_init(
  sqlite3 *db, 
  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  SQLITE_EXTENSION_INIT2(pApi);
  return spellfix1Register(db);
}
#endif /* !SQLITE_CORE */







|
|
|
>



<





<
<
|
>







 







<
<
<
<
<
<
<
<
<
<
<



>
>
>
|







<
10
11
12
13
14
15
16
17
18
19
20
21
22
23

24
25
26
27
28


29
30
31
32
33
34
35
36
37
....
2817
2818
2819
2820
2821
2822
2823











2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837

**
*************************************************************************
**
** This module implements the spellfix1 VIRTUAL TABLE that can be used
** to search a large vocabulary for close matches.  See separate
** documentation files (spellfix1.wiki and editdist3.wiki) for details.
*/
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1

#ifndef SQLITE_AMALGAMATION
# include <string.h>
# include <stdio.h>
# include <stdlib.h>

# include <assert.h>
# define ALWAYS(X)  1
# define NEVER(X)   0
  typedef unsigned char u8;
  typedef unsigned short u16;


# include <ctype.h>
#endif

/*
** Character classes for ASCII characters:
**
**   0   ''        Silent letters:   H W
**   1   'A'       Any vowel:   A E I O U (Y)
**   2   'B'       A bilabeal stop or fricative:  B F P V W
................................................................................
  for(i=0; i<sizeof(translit)/sizeof(translit[0])-1; i++){
    assert( translit[i].cFrom<translit[i+1].cFrom );
  }

  return rc;
}












/*
** Extension load function.
*/
#ifdef _WIN32
__declspec(dllexport)
#endif
int sqlite3_spellfix_init(
  sqlite3 *db, 
  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  SQLITE_EXTENSION_INIT2(pApi);
  return spellfix1Register(db);
}

Added ext/misc/spellfix1.wiki

































































































































































































































































































































































































































































































































































































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
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
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
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
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
<title>The Spellfix1 Virtual Table</title>

This spellfix1 virtual table is used to search
a large vocabulary for close matches.  For example, spellfix1
can be used to suggest corrections to misspelled words.  Or,
it could be used with FTS4 to do full-text search using potentially
misspelled words.

Create an instance of the spellfix1 virtual table like this:

<blockquote><pre>
CREATE VIRTUAL TABLE demo USING spellfix1;
</pre></blockquote>

The "spellfix1" term is the name of this module and must be entered as
shown.  The "demo" term is the
name of the virtual table you will be creating and can be altered
to suit the needs of your application.  The virtual table is initially
empty.  In order for the virtual table to be useful, you will need to
populate it with your vocabulary.  Suppose you
have a list of words in a table named "big_vocabulary".  Then do this:

<blockquote><pre>
INSERT INTO demo(word) SELECT word FROM big_vocabulary;
</pre></blockquote>

If you intend to use this virtual table in cooperation with an FTS4
table (for spelling correctly of search terms) then you might extract
the vocabulary using an fts3aux table:

<blockquote><pre>
INSERT INTO demo(word) SELECT term FROM search_aux WHERE col='*';
</pre></blockquote>

You can also provide the virtual table with a "rank" for each word.
The "rank" is an estimate of how common the word is.  Larger numbers
mean the word is more common.  If you omit the rank when populating
the table, then a rank of 1 is assumed.  But if you have rank 
information, you can supply it and the virtual table will show a
slight preference for selecting more commonly used terms.  To
populate the rank from an fts4aux table "search_aux" do something
like this:

<blockquote><pre>
INSERT INTO demo(word,rank)
   SELECT term, documents FROM search_aux WHERE col='*';
</pre></blockquote>

To query the virtual table, include a MATCH operator in the WHERE
clause.  For example:

<blockquote><pre>
SELECT word FROM demo WHERE word MATCH 'kennasaw';
</pre></blockquote>

Using a dataset of American place names (derived from
[http://geonames.usgs.gov/domestic/download_data.htm]) the query above
returns 20 results beginning with:

<blockquote><pre>
kennesaw
kenosha
kenesaw
kenaga
keanak
</pre></blockquote>

If you append the character '*' to the end of the pattern, then
a prefix search is performed.  For example:

<blockquote><pre>
SELECT word FROM demo WHERE word MATCH 'kennes*';
</pre></blockquote>

Yields 20 results beginning with:

<blockquote><pre>
kennesaw
kennestone
kenneson
kenneys
keanes
keenes
</pre></blockquote>

<h2>Search Refinements</h2>

By default, the spellfix1 table returns no more than 20 results.
(It might return less than 20 if there were fewer good matches.)
You can change the upper bound on the number of returned rows by
adding a "top=N" term to the WHERE clause of your query, where N
is the new maximum.  For example, to see the 5 best matches:

<blockquote><pre>
SELECT word FROM demo WHERE word MATCH 'kennes*' AND top=5;
</pre></blockquote>

Each entry in the spellfix1 virtual table is associated with a
a particular language, identified by the integer "langid" column.
The default langid is 0 and if no other actions are taken, the
entire vocabulary is a part of the 0 language.  But if your application
needs to operate in multiple languages, then you can specify different
vocabulary items for each language by specifying the langid field
when populating the table.  For example:

<blockquote><pre>
INSERT INTO demo(word,langid) SELECT word, 0 FROM en_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 1 FROM de_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 2 FROM fr_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 3 FROM ru_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 4 FROM cn_vocabulary;
</pre></blockquote>

After the virtual table has been populated with items from multiple
languages, specify the language of interest using a "langid=N" term
in the WHERE clause of the query:

<blockquote><pre>
SELECT word FROM demo WHERE word MATCH 'hildes*' AND langid=1;
</pre></blockquote>

Note that if you do not include the "langid=N" term in the WHERE clause,
the search will be against language 0 (English in the example above.)
All spellfix1 searches are against a single language id.  There is no
way to search all languages at once.
 

<h2>Virtual Table Details</h2>

The virtual table actually has a unique rowid with seven columns plus five
extra hidden columns.  The columns are as follows:

<blockquote><dl>
<dt><b>rowid</b><dd>
A unique integer number associated with each
vocabulary item in the table.  This can be used
as a foreign key on other tables in the database.

<dt><b>word</b><dd>
The text of the word that matches the pattern.
Both word and pattern can contains unicode characters
and can be mixed case.

<dt><b>rank</b><dd>
This is the rank of the word, as specified in the
original INSERT statement.


<dt><b>distance</b><dd>
This is an edit distance or Levensthein distance going
from the pattern to the word.

<dt><b>langid</b><dd>
This is the language-id of the word.  All queries are
against a single language-id, which defaults to 0.
For any given query this value is the same on all rows.

<dt><b>score</b><dd>
The score is a combination of rank and distance.  The
idea is that a lower score is better.  The virtual table
attempts to find words with the lowest score and 
by default (unless overridden by ORDER BY) returns
results in order of increasing score.

<dt><b>matchlen</b><dd>
In a prefix search, the matchlen is the number of characters in
the string that match against the prefix.  For a non-prefix search,
this is the same as length(word).

<dt><b>phonehash</b><dd>
This column shows the phonetic hash prefix that was used to restrict
the search.  For any given query, this column should be the same for
every row.  This information is available for diagnostic purposes and
is not normally considered useful in real applications.

<dt><b>top</b><dd>
(HIDDEN)  For any query, this value is the same on all
rows.  It is an integer which is the maximum number of
rows that will be output.  The actually number of rows
output might be less than this number, but it will never
be greater.  The default value for top is 20, but that
can be changed for each query by including a term of
the form "top=N" in the WHERE clause of the query.

<dt><b>scope</b><dd>
(HIDDEN)  For any query, this value is the same on all
rows.  The scope is a measure of how widely the virtual
table looks for matching words.  Smaller values of
scope cause a broader search.  The scope is normally
choosen automatically and is capped at 4.  Applications
can change the scope by including a term of the form
"scope=N" in the WHERE clause of the query.  Increasing
the scope will make the query run faster, but will reduce
the possible corrections.

<dt><b>srchcnt</b><dd>
(HIDDEN)  For any query, this value is the same on all
rows.  This value is an integer which is the number of
of words examined using the edit-distance algorithm to
find the top matches that are ultimately displayed.  This
value is for diagnostic use only.

<dt><b>soundslike</b><dd>
(HIDDEN)  When inserting vocabulary entries, this field
can be set to an spelling that matches what the word
sounds like.  See the DEALING WITH UNUSUAL AND DIFFICULT
SPELLINGS section below for details.

<dt><b>command</b><dd>
(HIDDEN)  The value of the "command" column is always NULL.  However,
applications can insert special strings into the "command" column in order
to provoke certain behaviors in the spellfix1 virtual table.
For example, inserting the string 'reset' into the "command" column
will cause the virtual table will reread its edit distance weights
(if there are any).
</dl></blockquote>

<h2>Algorithm</h2>

The spellfix1 virtual table creates a single
shadow table named "%_vocab" (where the % is replaced by the name of
the virtual table; Ex: "demo_vocab" for the "demo" virtual table).  
the shadow table contains the following columns:

<blockquote><dl>
<dt><b>id</b><dd>
The unique id (INTEGER PRIMARY KEY)

<dt><b>rank</b><dd>
The rank of word.

<dt><b>langid</b><dd>
The language id for this entry.

<dt><b>word</b><dd>
The original UTF8 text of the vocabulary word

<dt><b>k1</b><dd>
The word transliterated into lower-case ASCII.  
There is a standard table of mappings from non-ASCII
characters into ASCII.  Examples: "æ" -> "ae",
"þ" -> "th", "ß" -> "ss", "á" -> "a", ...  The
accessory function spellfix1_translit(X) will do
the non-ASCII to ASCII mapping.  The built-in lower(X)
function will convert to lower-case.  Thus:
k1 = lower(spellfix1_translit(word)).

<dt><b>k2</b><dd>
This field holds a phonetic code derived from k1.  Letters
that have similar sounds are mapped into the same symbol.
For example, all vowels and vowel clusters become the
single symbol "A".  And the letters "p", "b", "f", and
"v" all become "B".  All nasal sounds are represented
as "N".  And so forth.  The mapping is base on
ideas found in Soundex, Metaphone, and other
long-standing phonetic matching systems.  This key can
be generated by the function spellfix1_phonehash(X).  
Hence: k2 = spellfix1_phonehash(k1)
</dl></blockquote>

There is also a function for computing the Wagner edit distance or the
Levenshtein distance between a pattern and a word.  This function
is exposed as spellfix1_editdist(X,Y).  The edit distance function
returns the "cost" of converting X into Y.  Some transformations
cost more than others.  Changing one vowel into a different vowel,
for example is relatively cheap, as is doubling a constant, or
omitting the second character of a double-constant.  Other transformations
or more expensive.  The idea is that the edit distance function returns
a low cost of words that are similar and a higher cost for words
that are futher apart.  In this implementation, the maximum cost
of any single-character edit (delete, insert, or substitute) is 100,
with lower costs for some edits (such as transforming vowels).

The "score" for a comparison is the edit distance between the pattern
and the word, adjusted down by the base-2 logorithm of the word rank.
For example, a match with distance 100 but rank 1000 would have a
score of 122 (= 100 - log2(1000) + 32) where as a match with distance
100 with a rank of 1 would have a score of 131 (100 - log2(1) + 32).
(NB:  The constant 32 is added to each score to keep it from going
negative in case the edit distance is zero.)  In this way, frequently
used words get a slightly lower cost which tends to move them toward
the top of the list of alternative spellings.

A straightforward implementation of a spelling corrector would be
to compare the search term against every word in the vocabulary
and select the 20 with the lowest scores.  However, there will 
typically be hundreds of thousands or millions of words in the
vocabulary, and so this approach is not fast enough.

Suppose the term that is being spell-corrected is X.  To limit
the search space, X is converted to a k2-like key using the
equivalent of:

<blockquote><pre>
   key = spellfix1_phonehash(lower(spellfix1_translit(X)))
</pre></blockquote>

This key is then limited to "scope" characters.  The default scope
value is 4, but an alternative scope can be specified using the
"scope=N" term in the WHERE clause.  After the key has been truncated,
the edit distance is run against every term in the vocabulary that
has a k2 value that begins with the abbreviated key.

For example, suppose the input word is "Paskagula".  The phonetic 
key is "BACACALA" which is then truncated to 4 characters "BACA".
The edit distance is then run on the 4980 entries (out of
272,597 entries total) of the vocabulary whose k2 values begin with
BACA, yielding "Pascagoula" as the best match.

Only terms of the vocabulary with a matching langid are searched.
Hence, the same table can contain entries from multiple languages
and only the requested language will be used.  The default langid
is 0.

<h2>Configurable Edit Distance</h2>

The built-in Wagner edit-distance function with fixed weights can be
replaced by the [./editdist3.wiki | editdist3()] edit-distance function
with application-defined weights and support for unicode, by specifying
the "edit_cost_table=<i>TABLENAME</i>" parameter to the spellfix1 module
when the virtual table is created.
For example:

<blockquote><pre>
CREATE VIRTUAL TABLE demo2 USING spellfix1(edit_cost_table=APPCOST);
</pre></blockquote>

In the example above, the APPCOST table would be interrogated to find
the edit distance coefficients.  It is the presence of the "edit_cost_table="
parameter to the spellfix1 module name that causes editdist3() to be used
in place of the built-in edit distance function.

The edit distance coefficients are normally read from the APPCOST table
once and there after stored in memory.  Hence, run-time changes to the
APPCOST table will not normally effect the edit distance results.
However, inserting the special string 'reset' into the "command" column of the
virtual table causes the edit distance coefficients to be reread the
APPCOST table.  Hence, applications should run a SQL statement similar
to the following when changes to the APPCOST table occur:

<blockquote>
INSERT INTO demo2(command) VALUES('reset');
</blockquote>

The tables used for edit distance costs can be changed using a command
like the following:

<blockquote>
INSERT INTO demo2(command) VALUES('edit_cost_table=APPCOST2');
</blockquote>

In the example above, any prior edit distance costs would be discarded and
all future queries would use the costs found in the APPCOST2 table.  If the
name of the table specified by the "edit_cost_table" command is "NULL", then
theh built-in Wagner edit-distance function will be used instead of the
editdist3() function in all future queries.

<h2>Dealing With Unusual And Difficult Spellings</h2>

The algorithm above works quite well for most cases, but there are
exceptions.  These exceptions can be dealt with by making additional
entries in the virtual table using the "soundslike" column.

For example, many words of Greek origin begin with letters "ps" where
the "p" is silent.  Ex:  psalm, pseudonym, psoriasis, psyche.  In
another example, many Scottish surnames can be spelled with an
initial "Mac" or "Mc".  Thus, "MacKay" and "McKay" are both pronounced
the same.

Accommodation can be made for words that are not spelled as they
sound by making additional entries into the virtual table for the
same word, but adding an alternative spelling in the "soundslike"
column.  For example, the canonical entry for "psalm" would be this:

<blockquote><pre>
  INSERT INTO demo(word) VALUES('psalm');
</pre></blockquote>

To enhance the ability to correct the spelling of "salm" into
"psalm", make an addition entry like this:

<blockquote><pre>
  INSERT INTO demo(word,soundslike) VALUES('psalm','salm');
</pre></blockquote>

It is ok to make multiple entries for the same word as long as
each entry has a different soundslike value.  Note that if no
soundslike value is specified, the soundslike defaults to the word
itself.

Listed below are some cases where it might make sense to add additional
soundslike entries.  The specific entries will depend on the application
and the target language.

  *   Silent "p" in words beginning with "ps":  psalm, psyche

  *   Silent "p" in words beginning with "pn":  pneumonia, pneumatic

  *   Silent "p" in words beginning with "pt":  pterodactyl, ptolemaic

  *   Silent "d" in words beginning with "dj":  djinn, Djikarta

  *   Silent "k" in words beginning with "kn":  knight, Knuthson

  *   Silent "g" in words beginning with "gn":  gnarly, gnome, gnat

  *   "Mac" versus "Mc" beginning Scottish surnames

  *   "Tch" sounds in Slavic words:  Tchaikovsky vs. Chaykovsky

  *   The letter "j" pronounced like "h" in Spanish:  LaJolla

  *   Words beginning with "wr" versus "r":  write vs. rite

  *   Miscellanous problem words such as "debt", "tsetse",
      "Nguyen", "Van Nuyes".

<h2>Auxiliary Functions</h2>

The source code module that implements the spellfix1 virtual table also
implements several SQL functions that might be useful to applications
that employ spellfix1 or for testing or diagnostic work while developing
applications that use spellfix1.  The following auxiliary functions are
available:

<blockquote><dl>
<dt><b>editdist3(P,W)<br>editdist2(P,W,L)<br>editdist3(T)</b><dd>
These routines provide direct access to the version of the Wagner
edit-distance function that allows for application-defined weights
on edit operations.  The first two forms of this function compare
pattern P against word W and return the edit distance.  In the first
function, the langid is assumed to be 0 and in the second, the
langid is given by the L parameter.  The third form of this function
reloads edit distance coefficience from the table named by T.

<dt><b>spellfix1_editdist(P,W)</b><dd>
This routine provides access to the built-in Wagner edit-distance
function that uses default, fixed costs.  The value returned is
the edit distance needed to transform W into P.

<dt><b>spellfix1_phonehash(X)</b><dd>
This routine constructs a phonetic hash of the pure ascii input word X
and returns that hash.  This routine is used internally by spellfix1 in
order to transform the K1 column of the shadow table into the K2
column.

<dt><b>spellfix1_scriptcode(X)</b><dd>
Given an input string X, this routine attempts to determin the dominant
script of that input and returns the ISO-15924 numeric code for that
script.  The current implementation understands the following scripts:
<ul>
<li> 215 - Latin
<li> 220 - Cyrillic
<li> 200 - Greek
</ul>
Additional language codes might be added in future releases.

<dt><b>spellfix1_translit(X)</b><dd>
This routine transliterates unicode text into pure ascii, returning
the pure ascii representation of the input text X.  This is the function
that is used internally to transform vocabulary words into the K1
column of the shadow table.

</dl></blockquote>

Name change from src/test_wholenumber.c to ext/misc/wholenumber.c

18
19
20
21
22
23
24
25

26
27
28
29
30
31
32
...
246
247
248
249
250
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
**     CREATE VIRTUAL TABLE nums USING wholenumber;
**     SELECT value FROM nums WHERE value<10;
**
** Results in:
**
**     1 2 3 4 5 6 7 8 9
*/
#include "sqlite3.h"

#include <assert.h>
#include <string.h>

#ifndef SQLITE_OMIT_VIRTUALTABLE


/* A wholenumber cursor object */
................................................................................
  0,                         /* xRollback */
  0,                         /* xFindMethod */
  0,                         /* xRename */
};

#endif /* SQLITE_OMIT_VIRTUALTABLE */


/*


** Register the wholenumber virtual table
*/

int wholenumber_register(sqlite3 *db){



  int rc = SQLITE_OK;

#ifndef SQLITE_OMIT_VIRTUALTABLE
  rc = sqlite3_create_module(db, "wholenumber", &wholenumberModule, 0);
#endif
  return rc;
}

#ifdef SQLITE_TEST
#include <tcl.h>
/*
** Decode a pointer to an sqlite3 object.
*/
extern int getDbPointer(Tcl_Interp *interp, const char *zA, sqlite3 **ppDb);

/*
** Register the echo virtual table module.
*/
static int register_wholenumber_module(
  ClientData clientData, /* Pointer to sqlite3_enable_XXX function */
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int objc,              /* Number of arguments */
  Tcl_Obj *CONST objv[]  /* Command arguments */
){
  sqlite3 *db;
  if( objc!=2 ){
    Tcl_WrongNumArgs(interp, 1, objv, "DB");
    return TCL_ERROR;
  }
  if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;
  wholenumber_register(db);
  return TCL_OK;
}


/*
** Register commands with the TCL interpreter.
*/
int Sqlitetestwholenumber_Init(Tcl_Interp *interp){
  static struct {
     char *zName;
     Tcl_ObjCmdProc *xProc;
     void *clientData;
  } aObjCmd[] = {
     { "register_wholenumber_module",   register_wholenumber_module, 0 },
  };
  int i;
  for(i=0; i<sizeof(aObjCmd)/sizeof(aObjCmd[0]); i++){
    Tcl_CreateObjCommand(interp, aObjCmd[i].zName, 
        aObjCmd[i].xProc, aObjCmd[i].clientData, 0);
  }
  return TCL_OK;
}

#endif /* SQLITE_TEST */







|
>







 







<
<
>
>
|
<
>
|
>
>
>

>





<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
...
247
248
249
250
251
252
253


254
255
256

257
258
259
260
261
262
263
264
265
266
267
268
















































**     CREATE VIRTUAL TABLE nums USING wholenumber;
**     SELECT value FROM nums WHERE value<10;
**
** Results in:
**
**     1 2 3 4 5 6 7 8 9
*/
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1
#include <assert.h>
#include <string.h>

#ifndef SQLITE_OMIT_VIRTUALTABLE


/* A wholenumber cursor object */
................................................................................
  0,                         /* xRollback */
  0,                         /* xFindMethod */
  0,                         /* xRename */
};

#endif /* SQLITE_OMIT_VIRTUALTABLE */



#ifdef _WIN32
__declspec(dllexport)
#endif

int sqlite3_wholenumber_init(
  sqlite3 *db, 
  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  int rc = SQLITE_OK;
  SQLITE_EXTENSION_INIT2(pApi);
#ifndef SQLITE_OMIT_VIRTUALTABLE
  rc = sqlite3_create_module(db, "wholenumber", &wholenumberModule, 0);
#endif
  return rc;
}
















































Changes to main.mk

240
241
242
243
244
245
246
247
248
249
250
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
  $(TOP)/src/test_backup.c \
  $(TOP)/src/test_btree.c \
  $(TOP)/src/test_config.c \
  $(TOP)/src/test_demovfs.c \
  $(TOP)/src/test_devsym.c \
  $(TOP)/src/test_fs.c \
  $(TOP)/src/test_func.c \
  $(TOP)/src/test_fuzzer.c \
  $(TOP)/src/test_hexio.c \
  $(TOP)/src/test_init.c \
  $(TOP)/src/test_intarray.c \
  $(TOP)/src/test_journal.c \
  $(TOP)/src/test_malloc.c \
  $(TOP)/src/test_multiplex.c \
  $(TOP)/src/test_mutex.c \
  $(TOP)/src/test_onefile.c \
  $(TOP)/src/test_osinst.c \
  $(TOP)/src/test_pcache.c \
  $(TOP)/src/test_quota.c \
  $(TOP)/src/test_regexp.c \
  $(TOP)/src/test_rtree.c \
  $(TOP)/src/test_schema.c \
  $(TOP)/src/test_server.c \
  $(TOP)/src/test_stat.c \
  $(TOP)/src/test_sqllog.c \
  $(TOP)/src/test_superlock.c \
  $(TOP)/src/test_syscall.c \
  $(TOP)/src/test_tclvar.c \
  $(TOP)/src/test_thread.c \
  $(TOP)/src/test_vfs.c \
  $(TOP)/src/test_wholenumber.c \
  $(TOP)/src/test_wsd.c














#TESTSRC += $(TOP)/ext/fts2/fts2_tokenizer.c
#TESTSRC += $(TOP)/ext/fts3/fts3_tokenizer.c

TESTSRC2 = \
  $(TOP)/src/attach.c \
  $(TOP)/src/backup.c \







<











<










<

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







240
241
242
243
244
245
246

247
248
249
250
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
  $(TOP)/src/test_backup.c \
  $(TOP)/src/test_btree.c \
  $(TOP)/src/test_config.c \
  $(TOP)/src/test_demovfs.c \
  $(TOP)/src/test_devsym.c \
  $(TOP)/src/test_fs.c \
  $(TOP)/src/test_func.c \

  $(TOP)/src/test_hexio.c \
  $(TOP)/src/test_init.c \
  $(TOP)/src/test_intarray.c \
  $(TOP)/src/test_journal.c \
  $(TOP)/src/test_malloc.c \
  $(TOP)/src/test_multiplex.c \
  $(TOP)/src/test_mutex.c \
  $(TOP)/src/test_onefile.c \
  $(TOP)/src/test_osinst.c \
  $(TOP)/src/test_pcache.c \
  $(TOP)/src/test_quota.c \

  $(TOP)/src/test_rtree.c \
  $(TOP)/src/test_schema.c \
  $(TOP)/src/test_server.c \
  $(TOP)/src/test_stat.c \
  $(TOP)/src/test_sqllog.c \
  $(TOP)/src/test_superlock.c \
  $(TOP)/src/test_syscall.c \
  $(TOP)/src/test_tclvar.c \
  $(TOP)/src/test_thread.c \
  $(TOP)/src/test_vfs.c \

  $(TOP)/src/test_wsd.c

# Extensions to be statically loaded.
#
TESTSRC += \
  $(TOP)/ext/misc/amatch.c \
  $(TOP)/ext/misc/closure.c \
  $(TOP)/ext/misc/fuzzer.c \
  $(TOP)/ext/misc/ieee754.c \
  $(TOP)/ext/misc/nextchar.c \
  $(TOP)/ext/misc/regexp.c \
  $(TOP)/ext/misc/spellfix.c \
  $(TOP)/ext/misc/wholenumber.c


#TESTSRC += $(TOP)/ext/fts2/fts2_tokenizer.c
#TESTSRC += $(TOP)/ext/fts3/fts3_tokenizer.c

TESTSRC2 = \
  $(TOP)/src/attach.c \
  $(TOP)/src/backup.c \

Changes to src/expr.c

1210
1211
1212
1213
1214
1215
1216

1217
1218
1219
1220
1221
1222
1223
....
3424
3425
3426
3427
3428
3429
3430

3431
3432
3433
3434
3435
3436
3437
3438
3439
static int selectNodeIsConstant(Walker *pWalker, Select *NotUsed){
  UNUSED_PARAMETER(NotUsed);
  pWalker->u.i = 0;
  return WRC_Abort;
}
static int exprIsConst(Expr *p, int initFlag){
  Walker w;

  w.u.i = initFlag;
  w.xExprCallback = exprNodeIsConstant;
  w.xSelectCallback = selectNodeIsConstant;
  sqlite3WalkExpr(&w, p);
  return w.u.i;
}

................................................................................
** obtained for queries regardless of whether or not constants are
** precomputed into registers or if they are inserted in-line.
*/
void sqlite3ExprCodeConstants(Parse *pParse, Expr *pExpr){
  Walker w;
  if( pParse->cookieGoto ) return;
  if( OptimizationDisabled(pParse->db, SQLITE_FactorOutConst) ) return;

  w.xExprCallback = evalConstExpr;
  w.xSelectCallback = 0;
  w.pParse = pParse;
  sqlite3WalkExpr(&w, pExpr);
}


/*
** Generate code that pushes the value of every element of the given







>







 







>

<







1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
....
3425
3426
3427
3428
3429
3430
3431
3432
3433

3434
3435
3436
3437
3438
3439
3440
static int selectNodeIsConstant(Walker *pWalker, Select *NotUsed){
  UNUSED_PARAMETER(NotUsed);
  pWalker->u.i = 0;
  return WRC_Abort;
}
static int exprIsConst(Expr *p, int initFlag){
  Walker w;
  memset(&w, 0, sizeof(w));
  w.u.i = initFlag;
  w.xExprCallback = exprNodeIsConstant;
  w.xSelectCallback = selectNodeIsConstant;
  sqlite3WalkExpr(&w, p);
  return w.u.i;
}

................................................................................
** obtained for queries regardless of whether or not constants are
** precomputed into registers or if they are inserted in-line.
*/
void sqlite3ExprCodeConstants(Parse *pParse, Expr *pExpr){
  Walker w;
  if( pParse->cookieGoto ) return;
  if( OptimizationDisabled(pParse->db, SQLITE_FactorOutConst) ) return;
  memset(&w, 0, sizeof(w));
  w.xExprCallback = evalConstExpr;

  w.pParse = pParse;
  sqlite3WalkExpr(&w, pExpr);
}


/*
** Generate code that pushes the value of every element of the given

Changes to src/resolve.c

1279
1280
1281
1282
1283
1284
1285

1286
1287
1288
1289
1290
1291
1292
....
1319
1320
1321
1322
1323
1324
1325

1326
1327
1328
1329
1330
1331
      return 1;
    }
    pParse->nHeight += pExpr->nHeight;
  }
#endif
  savedHasAgg = pNC->ncFlags & NC_HasAgg;
  pNC->ncFlags &= ~NC_HasAgg;

  w.xExprCallback = resolveExprStep;
  w.xSelectCallback = resolveSelectStep;
  w.pParse = pNC->pParse;
  w.u.pNC = pNC;
  sqlite3WalkExpr(&w, pExpr);
#if SQLITE_MAX_EXPR_DEPTH>0
  pNC->pParse->nHeight -= pExpr->nHeight;
................................................................................
  Parse *pParse,         /* The parser context */
  Select *p,             /* The SELECT statement being coded. */
  NameContext *pOuterNC  /* Name context for parent SELECT statement */
){
  Walker w;

  assert( p!=0 );

  w.xExprCallback = resolveExprStep;
  w.xSelectCallback = resolveSelectStep;
  w.pParse = pParse;
  w.u.pNC = pOuterNC;
  sqlite3WalkSelect(&w, p);
}







>







 







>






1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
....
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
      return 1;
    }
    pParse->nHeight += pExpr->nHeight;
  }
#endif
  savedHasAgg = pNC->ncFlags & NC_HasAgg;
  pNC->ncFlags &= ~NC_HasAgg;
  memset(&w, 0, sizeof(w));
  w.xExprCallback = resolveExprStep;
  w.xSelectCallback = resolveSelectStep;
  w.pParse = pNC->pParse;
  w.u.pNC = pNC;
  sqlite3WalkExpr(&w, pExpr);
#if SQLITE_MAX_EXPR_DEPTH>0
  pNC->pParse->nHeight -= pExpr->nHeight;
................................................................................
  Parse *pParse,         /* The parser context */
  Select *p,             /* The SELECT statement being coded. */
  NameContext *pOuterNC  /* Name context for parent SELECT statement */
){
  Walker w;

  assert( p!=0 );
  memset(&w, 0, sizeof(w));
  w.xExprCallback = resolveExprStep;
  w.xSelectCallback = resolveSelectStep;
  w.pParse = pParse;
  w.u.pNC = pOuterNC;
  sqlite3WalkSelect(&w, p);
}

Changes to src/select.c

3572
3573
3574
3575
3576
3577
3578

3579
3580
3581
3582
3583
3584
3585
....
3630
3631
3632
3633
3634
3635
3636

3637
3638
3639

3640
3641
3642
3643
3644
3645
3646
....
4043
4044
4045
4046
4047
4048
4049
4050
4051
4052
4053
4054
4055
4056
4057
**
** If anything goes wrong, an error message is written into pParse.
** The calling function can detect the problem by looking at pParse->nErr
** and/or pParse->db->mallocFailed.
*/
static void sqlite3SelectExpand(Parse *pParse, Select *pSelect){
  Walker w;

  w.xSelectCallback = selectExpander;
  w.xExprCallback = exprWalkNoop;
  w.pParse = pParse;
  sqlite3WalkSelect(&w, pSelect);
}


................................................................................
** SELECT statement.
**
** Use this routine after name resolution.
*/
static void sqlite3SelectAddTypeInfo(Parse *pParse, Select *pSelect){
#ifndef SQLITE_OMIT_SUBQUERY
  Walker w;

  w.xSelectCallback = selectAddSubqueryTypeInfo;
  w.xExprCallback = exprWalkNoop;
  w.pParse = pParse;

  sqlite3WalkSelect(&w, pSelect);
#endif
}


/*
** This routine sets up a SELECT statement for processing.  The
................................................................................
      int retAddr;
      assert( pItem->addrFillSub==0 );
      pItem->regReturn = ++pParse->nMem;
      topAddr = sqlite3VdbeAddOp2(v, OP_Integer, 0, pItem->regReturn);
      pItem->addrFillSub = topAddr+1;
      VdbeNoopComment((v, "materialize %s", pItem->pTab->zName));
      if( pItem->isCorrelated==0 ){
        /* If the subquery is no correlated and if we are not inside of
        ** a trigger, then we only need to compute the value of the subquery
        ** once. */
        onceAddr = sqlite3CodeOnce(pParse);
      }
      sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor);
      explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);
      sqlite3Select(pParse, pSub, &dest);







>







 







>



>







 







|







3572
3573
3574
3575
3576
3577
3578
3579
3580
3581
3582
3583
3584
3585
3586
....
3631
3632
3633
3634
3635
3636
3637
3638
3639
3640
3641
3642
3643
3644
3645
3646
3647
3648
3649
....
4046
4047
4048
4049
4050
4051
4052
4053
4054
4055
4056
4057
4058
4059
4060
**
** If anything goes wrong, an error message is written into pParse.
** The calling function can detect the problem by looking at pParse->nErr
** and/or pParse->db->mallocFailed.
*/
static void sqlite3SelectExpand(Parse *pParse, Select *pSelect){
  Walker w;
  memset(&w, 0, sizeof(w));
  w.xSelectCallback = selectExpander;
  w.xExprCallback = exprWalkNoop;
  w.pParse = pParse;
  sqlite3WalkSelect(&w, pSelect);
}


................................................................................
** SELECT statement.
**
** Use this routine after name resolution.
*/
static void sqlite3SelectAddTypeInfo(Parse *pParse, Select *pSelect){
#ifndef SQLITE_OMIT_SUBQUERY
  Walker w;
  memset(&w, 0, sizeof(w));
  w.xSelectCallback = selectAddSubqueryTypeInfo;
  w.xExprCallback = exprWalkNoop;
  w.pParse = pParse;
  w.bSelectDepthFirst = 1;
  sqlite3WalkSelect(&w, pSelect);
#endif
}


/*
** This routine sets up a SELECT statement for processing.  The
................................................................................
      int retAddr;
      assert( pItem->addrFillSub==0 );
      pItem->regReturn = ++pParse->nMem;
      topAddr = sqlite3VdbeAddOp2(v, OP_Integer, 0, pItem->regReturn);
      pItem->addrFillSub = topAddr+1;
      VdbeNoopComment((v, "materialize %s", pItem->pTab->zName));
      if( pItem->isCorrelated==0 ){
        /* If the subquery is not correlated and if we are not inside of
        ** a trigger, then we only need to compute the value of the subquery
        ** once. */
        onceAddr = sqlite3CodeOnce(pParse);
      }
      sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor);
      explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);
      sqlite3Select(pParse, pSub, &dest);

Changes to src/shell.c

1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
    if( db==0 || SQLITE_OK!=sqlite3_errcode(db) ){
      fprintf(stderr,"Error: unable to open database \"%s\": %s\n", 
          p->zDbFilename, sqlite3_errmsg(db));
      exit(1);
    }
#ifndef SQLITE_OMIT_LOAD_EXTENSION
    sqlite3_enable_load_extension(p->db, 1);
#endif
#ifdef SQLITE_ENABLE_REGEXP
    {
      extern int sqlite3_add_regexp_func(sqlite3*);
      sqlite3_add_regexp_func(db);
    }
#endif
#ifdef SQLITE_ENABLE_SPELLFIX
    {
      extern int sqlite3_spellfix1_register(sqlite3*);
      sqlite3_spellfix1_register(db);
    }
#endif
  }
}

/*
** Do C-language style dequoting.
**







<
<
<
<
<
<
<
<
<
<
<
<







1476
1477
1478
1479
1480
1481
1482












1483
1484
1485
1486
1487
1488
1489
    if( db==0 || SQLITE_OK!=sqlite3_errcode(db) ){
      fprintf(stderr,"Error: unable to open database \"%s\": %s\n", 
          p->zDbFilename, sqlite3_errmsg(db));
      exit(1);
    }
#ifndef SQLITE_OMIT_LOAD_EXTENSION
    sqlite3_enable_load_extension(p->db, 1);












#endif
  }
}

/*
** Do C-language style dequoting.
**

Changes to src/sqliteInt.h

2584
2585
2586
2587
2588
2589
2590

2591
2592
2593
2594
2595
2596
2597
** Context pointer passed down through the tree-walk.
*/
struct Walker {
  int (*xExprCallback)(Walker*, Expr*);     /* Callback for expressions */
  int (*xSelectCallback)(Walker*,Select*);  /* Callback for SELECTs */
  Parse *pParse;                            /* Parser context.  */
  int walkerDepth;                          /* Number of subqueries */

  union {                                   /* Extra data for callback */
    NameContext *pNC;                          /* Naming context */
    int i;                                     /* Integer value */
    SrcList *pSrcList;                         /* FROM clause */
    struct SrcCount *pSrcCount;                /* Counting column references */
  } u;
};







>







2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
** Context pointer passed down through the tree-walk.
*/
struct Walker {
  int (*xExprCallback)(Walker*, Expr*);     /* Callback for expressions */
  int (*xSelectCallback)(Walker*,Select*);  /* Callback for SELECTs */
  Parse *pParse;                            /* Parser context.  */
  int walkerDepth;                          /* Number of subqueries */
  u8 bSelectDepthFirst;                     /* Do subqueries first */
  union {                                   /* Extra data for callback */
    NameContext *pNC;                          /* Naming context */
    int i;                                     /* Integer value */
    SrcList *pSrcList;                         /* FROM clause */
    struct SrcCount *pSrcCount;                /* Counting column references */
  } u;
};

Changes to src/tclsqlite.c

3679
3680
3681
3682
3683
3684
3685
3686
3687
3688
3689
3690
3691
3692
3693
3694
3695
....
3724
3725
3726
3727
3728
3729
3730
3731
3732
3733
3734
3735
3736
3737
3738
3739
3740
    extern int Sqlitetestintarray_Init(Tcl_Interp*);
    extern int Sqlitetestvfs_Init(Tcl_Interp *);
    extern int Sqlitetestrtree_Init(Tcl_Interp*);
    extern int Sqlitequota_Init(Tcl_Interp*);
    extern int Sqlitemultiplex_Init(Tcl_Interp*);
    extern int SqliteSuperlock_Init(Tcl_Interp*);
    extern int SqlitetestSyscall_Init(Tcl_Interp*);
    extern int Sqlitetestfuzzer_Init(Tcl_Interp*);
    extern int Sqlitetestwholenumber_Init(Tcl_Interp*);
    extern int Sqlitetestregexp_Init(Tcl_Interp*);

#if defined(SQLITE_ENABLE_FTS3) || defined(SQLITE_ENABLE_FTS4)
    extern int Sqlitetestfts3_Init(Tcl_Interp *interp);
#endif

#ifdef SQLITE_ENABLE_ZIPVFS
    extern int Zipvfs_Init(Tcl_Interp*);
................................................................................
    Sqlitetestintarray_Init(interp);
    Sqlitetestvfs_Init(interp);
    Sqlitetestrtree_Init(interp);
    Sqlitequota_Init(interp);
    Sqlitemultiplex_Init(interp);
    SqliteSuperlock_Init(interp);
    SqlitetestSyscall_Init(interp);
    Sqlitetestfuzzer_Init(interp);
    Sqlitetestwholenumber_Init(interp);
    Sqlitetestregexp_Init(interp);

#if defined(SQLITE_ENABLE_FTS3) || defined(SQLITE_ENABLE_FTS4)
    Sqlitetestfts3_Init(interp);
#endif

    Tcl_CreateObjCommand(
        interp, "load_testfixture_extensions", init_all_cmd, 0, 0







<
<
<







 







<
<
<







3679
3680
3681
3682
3683
3684
3685



3686
3687
3688
3689
3690
3691
3692
....
3721
3722
3723
3724
3725
3726
3727



3728
3729
3730
3731
3732
3733
3734
    extern int Sqlitetestintarray_Init(Tcl_Interp*);
    extern int Sqlitetestvfs_Init(Tcl_Interp *);
    extern int Sqlitetestrtree_Init(Tcl_Interp*);
    extern int Sqlitequota_Init(Tcl_Interp*);
    extern int Sqlitemultiplex_Init(Tcl_Interp*);
    extern int SqliteSuperlock_Init(Tcl_Interp*);
    extern int SqlitetestSyscall_Init(Tcl_Interp*);




#if defined(SQLITE_ENABLE_FTS3) || defined(SQLITE_ENABLE_FTS4)
    extern int Sqlitetestfts3_Init(Tcl_Interp *interp);
#endif

#ifdef SQLITE_ENABLE_ZIPVFS
    extern int Zipvfs_Init(Tcl_Interp*);
................................................................................
    Sqlitetestintarray_Init(interp);
    Sqlitetestvfs_Init(interp);
    Sqlitetestrtree_Init(interp);
    Sqlitequota_Init(interp);
    Sqlitemultiplex_Init(interp);
    SqliteSuperlock_Init(interp);
    SqlitetestSyscall_Init(interp);




#if defined(SQLITE_ENABLE_FTS3) || defined(SQLITE_ENABLE_FTS4)
    Sqlitetestfts3_Init(interp);
#endif

    Tcl_CreateObjCommand(
        interp, "load_testfixture_extensions", init_all_cmd, 0, 0

Changes to src/test1.c

6040
6041
6042
6043
6044
6045
6046































































6047
6048
6049
6050
6051
6052
6053
....
6262
6263
6264
6265
6266
6267
6268

6269
6270
6271
6272
6273
6274
6275
      Tcl_AppendResult(interp, " ", aOpt[i].zOptName);
    }
    return TCL_ERROR;
  }
  sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS, db, mask);
  return TCL_OK;
}
































































/*
** Register commands with the TCL interpreter.
*/
int Sqlitetest1_Init(Tcl_Interp *interp){
  extern int sqlite3_search_count;
  extern int sqlite3_found_count;
................................................................................
#ifndef SQLITE_OMIT_EXPLAIN
     { "print_explain_query_plan", test_print_eqp, 0  },
#endif
     { "sqlite3_test_control", test_test_control },
#if SQLITE_OS_UNIX
     { "getrusage", test_getrusage },
#endif

  };
  static int bitmask_size = sizeof(Bitmask)*8;
  int i;
  extern int sqlite3_sync_count, sqlite3_fullsync_count;
  extern int sqlite3_opentemp_count;
  extern int sqlite3_like_count;
  extern int sqlite3_xferopt_count;







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







 







>







6040
6041
6042
6043
6044
6045
6046
6047
6048
6049
6050
6051
6052
6053
6054
6055
6056
6057
6058
6059
6060
6061
6062
6063
6064
6065
6066
6067
6068
6069
6070
6071
6072
6073
6074
6075
6076
6077
6078
6079
6080
6081
6082
6083
6084
6085
6086
6087
6088
6089
6090
6091
6092
6093
6094
6095
6096
6097
6098
6099
6100
6101
6102
6103
6104
6105
6106
6107
6108
6109
6110
6111
6112
6113
6114
6115
6116
....
6325
6326
6327
6328
6329
6330
6331
6332
6333
6334
6335
6336
6337
6338
6339
      Tcl_AppendResult(interp, " ", aOpt[i].zOptName);
    }
    return TCL_ERROR;
  }
  sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS, db, mask);
  return TCL_OK;
}

typedef struct sqlite3_api_routines sqlite3_api_routines;
/*
**     load_static_extension DB NAME ...
**
** Load one or more statically linked extensions.
*/
static int tclLoadStaticExtensionCmd(
  void * clientData,
  Tcl_Interp *interp,
  int objc,
  Tcl_Obj *CONST objv[]
){
  extern int sqlite3_amatch_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_closure_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_fuzzer_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_ieee_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_nextchar_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_regexp_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_spellfix_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_wholenumber_init(sqlite3*,char**,const sqlite3_api_routines*);
  static const struct {
    const char *zExtName;
    int (*pInit)(sqlite3*,char**,const sqlite3_api_routines*);
  } aExtension[] = {
    { "amatch",                sqlite3_amatch_init               },
    { "closure",               sqlite3_closure_init              },
    { "fuzzer",                sqlite3_fuzzer_init               },
    { "ieee754",               sqlite3_ieee_init                 },
    { "nextchar",              sqlite3_nextchar_init             },
    { "regexp",                sqlite3_regexp_init               },
    { "spellfix",              sqlite3_spellfix_init             },
    { "wholenumber",           sqlite3_wholenumber_init          },
  };
  sqlite3 *db;
  const char *zName;
  int i, j, rc;
  char *zErrMsg = 0;
  if( objc<3 ){
    Tcl_WrongNumArgs(interp, 1, objv, "DB NAME ...");
    return TCL_ERROR;
  }
  if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;
  for(j=2; j<objc; j++){
    zName = Tcl_GetString(objv[j]);
    for(i=0; i<ArraySize(aExtension); i++){
      if( strcmp(zName, aExtension[i].zExtName)==0 ) break;
    }
    if( i>=ArraySize(aExtension) ){
      Tcl_AppendResult(interp, "no such extension: ", zName, (char*)0);
      return TCL_ERROR;
    }
    rc = aExtension[i].pInit(db, &zErrMsg, 0);
    if( rc!=SQLITE_OK || zErrMsg ){
      Tcl_AppendResult(interp, "initialization of ", zName, " failed: ", zErrMsg,
                       (char*)0);
      sqlite3_free(zErrMsg);
      return TCL_ERROR;
    }
  }
  return TCL_OK;
}


/*
** Register commands with the TCL interpreter.
*/
int Sqlitetest1_Init(Tcl_Interp *interp){
  extern int sqlite3_search_count;
  extern int sqlite3_found_count;
................................................................................
#ifndef SQLITE_OMIT_EXPLAIN
     { "print_explain_query_plan", test_print_eqp, 0  },
#endif
     { "sqlite3_test_control", test_test_control },
#if SQLITE_OS_UNIX
     { "getrusage", test_getrusage },
#endif
     { "load_static_extension", tclLoadStaticExtensionCmd },
  };
  static int bitmask_size = sizeof(Bitmask)*8;
  int i;
  extern int sqlite3_sync_count, sqlite3_fullsync_count;
  extern int sqlite3_opentemp_count;
  extern int sqlite3_like_count;
  extern int sqlite3_xferopt_count;

Changes to src/test8.c

1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
  if( rc!=SQLITE_OK ){
    Tcl_SetResult(interp, (char *)sqlite3_errmsg(db), TCL_VOLATILE);
    return TCL_ERROR;
  }
  return TCL_OK;
}

#include "test_spellfix.c"

/*
** Register the spellfix virtual table module.
*/
static int register_spellfix_module(
  ClientData clientData,
  Tcl_Interp *interp,
  int objc,
  Tcl_Obj *CONST objv[]
){
  sqlite3 *db;

  if( objc!=2 ){
    Tcl_WrongNumArgs(interp, 1, objv, "DB");
    return TCL_ERROR;
  }
  if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;

  sqlite3_spellfix1_register(db);
  return TCL_OK;
}

#endif /* ifndef SQLITE_OMIT_VIRTUALTABLE */

/*
** Register commands with the TCL interpreter.
*/
int Sqlitetest8_Init(Tcl_Interp *interp){
#ifndef SQLITE_OMIT_VIRTUALTABLE
  static struct {
     char *zName;
     Tcl_ObjCmdProc *xProc;
     void *clientData;
  } aObjCmd[] = {
     { "register_echo_module",       register_echo_module, 0 },
     { "register_spellfix_module",   register_spellfix_module, 0 },
     { "sqlite3_declare_vtab",       declare_vtab, 0 },
  };
  int i;
  for(i=0; i<sizeof(aObjCmd)/sizeof(aObjCmd[0]); i++){
    Tcl_CreateObjCommand(interp, aObjCmd[i].zName, 
        aObjCmd[i].xProc, aObjCmd[i].clientData, 0);
  }
#endif
  return TCL_OK;
}







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<













<










1366
1367
1368
1369
1370
1371
1372























1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385

1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
  if( rc!=SQLITE_OK ){
    Tcl_SetResult(interp, (char *)sqlite3_errmsg(db), TCL_VOLATILE);
    return TCL_ERROR;
  }
  return TCL_OK;
}
























#endif /* ifndef SQLITE_OMIT_VIRTUALTABLE */

/*
** Register commands with the TCL interpreter.
*/
int Sqlitetest8_Init(Tcl_Interp *interp){
#ifndef SQLITE_OMIT_VIRTUALTABLE
  static struct {
     char *zName;
     Tcl_ObjCmdProc *xProc;
     void *clientData;
  } aObjCmd[] = {
     { "register_echo_module",       register_echo_module, 0 },

     { "sqlite3_declare_vtab",       declare_vtab, 0 },
  };
  int i;
  for(i=0; i<sizeof(aObjCmd)/sizeof(aObjCmd[0]); i++){
    Tcl_CreateObjCommand(interp, aObjCmd[i].zName, 
        aObjCmd[i].xProc, aObjCmd[i].clientData, 0);
  }
#endif
  return TCL_OK;
}

Changes to src/walker.c

109
110
111
112
113
114
115
116


117
118
119
120
121
122
123
124
125
126
127
128
129

130
131

132
133
134
135
136







137
138
139
140
141
142
  }
  return WRC_Continue;
} 

/*
** Call sqlite3WalkExpr() for every expression in Select statement p.
** Invoke sqlite3WalkSelect() for subqueries in the FROM clause and
** on the compound select chain, p->pPrior.


**
** Return WRC_Continue under normal conditions.  Return WRC_Abort if
** there is an abort request.
**
** If the Walker does not have an xSelectCallback() then this routine
** is a no-op returning WRC_Continue.
*/
int sqlite3WalkSelect(Walker *pWalker, Select *p){
  int rc;
  if( p==0 || pWalker->xSelectCallback==0 ) return WRC_Continue;
  rc = WRC_Continue;
  pWalker->walkerDepth++;
  while( p ){

    rc = pWalker->xSelectCallback(pWalker, p);
    if( rc ) break;

    if( sqlite3WalkSelectExpr(pWalker, p)
     || sqlite3WalkSelectFrom(pWalker, p)
    ){
      pWalker->walkerDepth--;
      return WRC_Abort;







    }
    p = p->pPrior;
  }
  pWalker->walkerDepth--;
  return rc & WRC_Abort;
}







|
>
>













>
|
|
>





>
>
>
>
>
>
>






109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
  }
  return WRC_Continue;
} 

/*
** Call sqlite3WalkExpr() for every expression in Select statement p.
** Invoke sqlite3WalkSelect() for subqueries in the FROM clause and
** on the compound select chain, p->pPrior.  Invoke the xSelectCallback()
** either before or after the walk of expressions and FROM clause, depending
** on whether pWalker->bSelectDepthFirst is false or true, respectively.
**
** Return WRC_Continue under normal conditions.  Return WRC_Abort if
** there is an abort request.
**
** If the Walker does not have an xSelectCallback() then this routine
** is a no-op returning WRC_Continue.
*/
int sqlite3WalkSelect(Walker *pWalker, Select *p){
  int rc;
  if( p==0 || pWalker->xSelectCallback==0 ) return WRC_Continue;
  rc = WRC_Continue;
  pWalker->walkerDepth++;
  while( p ){
    if( !pWalker->bSelectDepthFirst ){
       rc = pWalker->xSelectCallback(pWalker, p);
       if( rc ) break;
    }
    if( sqlite3WalkSelectExpr(pWalker, p)
     || sqlite3WalkSelectFrom(pWalker, p)
    ){
      pWalker->walkerDepth--;
      return WRC_Abort;
    }
    if( pWalker->bSelectDepthFirst ){
      rc = pWalker->xSelectCallback(pWalker, p);
      /* Depth-first search is currently only used for
      ** selectAddSubqueryTypeInfo() and that routine always returns
      ** WRC_Continue (0).  So the following branch is never taken. */
      if( NEVER(rc) ) break;
    }
    p = p->pPrior;
  }
  pWalker->walkerDepth--;
  return rc & WRC_Abort;
}

Changes to test/8_3_names.test

146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
  finish_test
  return
}
db close
forcedelete test.db
do_test 8_3_names-5.0 {
  sqlite3 db file:./test.db?8_3_names=1
  register_wholenumber_module db
  db eval {
    PRAGMA journal_mode=WAL;
    CREATE TABLE t1(x);
    CREATE VIRTUAL TABLE nums USING wholenumber;
    INSERT INTO t1 SELECT value FROM nums WHERE value BETWEEN 1 AND 1000;
    BEGIN;
    UPDATE t1 SET x=x*2;
  }
  sqlite3 db2 file:./test.db?8_3_names=1
  register_wholenumber_module db2
  db2 eval {
    BEGIN;
    SELECT sum(x) FROM t1;
  }
} {500500}

do_test 8_3_names-5.1 {







|









|







146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
  finish_test
  return
}
db close
forcedelete test.db
do_test 8_3_names-5.0 {
  sqlite3 db file:./test.db?8_3_names=1
  load_static_extension db wholenumber
  db eval {
    PRAGMA journal_mode=WAL;
    CREATE TABLE t1(x);
    CREATE VIRTUAL TABLE nums USING wholenumber;
    INSERT INTO t1 SELECT value FROM nums WHERE value BETWEEN 1 AND 1000;
    BEGIN;
    UPDATE t1 SET x=x*2;
  }
  sqlite3 db2 file:./test.db?8_3_names=1
  load_static_extension db2 wholenumber
  db2 eval {
    BEGIN;
    SELECT sum(x) FROM t1;
  }
} {500500}

do_test 8_3_names-5.1 {

Changes to test/analyze7.test

22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
  finish_test
  return
}

# Generate some test data
#
do_test analyze7-1.0 {
  register_wholenumber_module db
  execsql {
    CREATE TABLE t1(a,b,c,d);
    CREATE INDEX t1a ON t1(a);
    CREATE INDEX t1b ON t1(b);
    CREATE INDEX t1cd ON t1(c,d);
    CREATE VIRTUAL TABLE nums USING wholenumber;
    INSERT INTO t1 SELECT value, value, value/100, value FROM nums







|







22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
  finish_test
  return
}

# Generate some test data
#
do_test analyze7-1.0 {
  load_static_extension db wholenumber
  execsql {
    CREATE TABLE t1(a,b,c,d);
    CREATE INDEX t1a ON t1(a);
    CREATE INDEX t1b ON t1(b);
    CREATE INDEX t1cd ON t1(c,d);
    CREATE VIRTUAL TABLE nums USING wholenumber;
    INSERT INTO t1 SELECT value, value, value/100, value FROM nums

Added test/closure01.test

































































































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
# 2013-04-25
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# 
# Test cases for transitive_closure virtual table.

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix closure01

load_static_extension db closure

do_execsql_test 1.0 {
  BEGIN;
  CREATE TABLE t1(x INTEGER PRIMARY KEY, y INTEGER);
  CREATE INDEX t1y ON t1(y);
  INSERT INTO t1(x) VALUES(1),(2);
  INSERT INTO t1(x) SELECT x+2 FROM t1;
  INSERT INTO t1(x) SELECT x+4 FROM t1;
  INSERT INTO t1(x) SELECT x+8 FROM t1;
  INSERT INTO t1(x) SELECT x+16 FROM t1;
  INSERT INTO t1(x) SELECT x+32 FROM t1;
  INSERT INTO t1(x) SELECT x+64 FROM t1;
  INSERT INTO t1(x) SELECT x+128 FROM t1;
  INSERT INTO t1(x) SELECT x+256 FROM t1;
  INSERT INTO t1(x) SELECT x+512 FROM t1;
  INSERT INTO t1(x) SELECT x+1024 FROM t1;
  INSERT INTO t1(x) SELECT x+2048 FROM t1;
  INSERT INTO t1(x) SELECT x+4096 FROM t1;
  INSERT INTO t1(x) SELECT x+8192 FROM t1;
  INSERT INTO t1(x) SELECT x+16384 FROM t1;
  INSERT INTO t1(x) SELECT x+32768 FROM t1;
  INSERT INTO t1(x) SELECT x+65536 FROM t1;
  UPDATE t1 SET y=x/2 WHERE x>1;
  COMMIT;
  CREATE VIRTUAL TABLE cx 
   USING transitive_closure(tablename=t1, idcolumn=x, parentcolumn=y);
} {}

# The entire table
do_execsql_test 1.1 {
  SELECT count(*), depth FROM cx WHERE root=1 GROUP BY depth ORDER BY 1;
} {/1 0 1 17 2 1 4 2 8 3 16 4 .* 65536 16/}

# descendents of 32768
do_execsql_test 1.2 {
  SELECT * FROM cx WHERE root=32768 ORDER BY id;
} {32768 0 65536 1 65537 1 131072 2}

# descendents of 16384
do_execsql_test 1.3 {
  SELECT * FROM cx WHERE root=16384 AND depth<=2 ORDER BY id;
} {16384 0 32768 1 32769 1 65536 2 65537 2 65538 2 65539 2}

# children of 16384
do_execsql_test 1.4 {
  SELECT id, depth, root, tablename, idcolumn, parentcolumn FROM cx
   WHERE root=16384
     AND depth=1
   ORDER BY id;
} {32768 1 {} t1 x y 32769 1 {} t1 x y}

# great-grandparent of 16384
do_execsql_test 1.5 {
  SELECT id, depth, root, tablename, idcolumn, parentcolumn FROM cx
   WHERE root=16384
     AND depth=3
     AND idcolumn='Y'
     AND parentcolumn='X';
} {2048 3 {} t1 Y X}

# depth<5
do_execsql_test 1.6 {
  SELECT count(*), depth FROM cx WHERE root=1 AND depth<5
   GROUP BY depth ORDER BY 1;
} {1 0 2 1 4 2 8 3 16 4}

# depth<=5
do_execsql_test 1.7 {
  SELECT count(*), depth FROM cx WHERE root=1 AND depth<=5
   GROUP BY depth ORDER BY 1;
} {1 0 2 1 4 2 8 3 16 4 32 5}

# depth==5
do_execsql_test 1.8 {
  SELECT count(*), depth FROM cx WHERE root=1 AND depth=5
   GROUP BY depth ORDER BY 1;
} {32 5}

# depth BETWEEN 3 AND 5
do_execsql_test 1.9 {
  SELECT count(*), depth FROM cx WHERE root=1 AND depth BETWEEN 3 AND 5
   GROUP BY depth ORDER BY 1;
} {8 3 16 4 32 5}

# depth==5 with min() and max()
do_execsql_test 1.10 {
  SELECT count(*), min(id), max(id) FROM cx WHERE root=1 AND depth=5;
} {32 32 63}

# Create a much smaller table t2 with only 32 elements 
db eval {
  CREATE TABLE t2(x INTEGER PRIMARY KEY, y INTEGER);
  INSERT INTO t2 SELECT x, y FROM t1 WHERE x<32;
  CREATE INDEX t2y ON t2(y);
  CREATE VIRTUAL TABLE c2 
   USING transitive_closure(tablename=t2, idcolumn=x, parentcolumn=y);
}

# t2 full-table
do_execsql_test 2.1 {
  SELECT count(*), min(id), max(id) FROM c2 WHERE root=1;
} {31 1 31}
# t2 root=10
do_execsql_test 2.2 {
  SELECT id FROM c2 WHERE root=10;
} {10 20 21}
# t2 root=11
do_execsql_test 2.3 {
  SELECT id FROM c2 WHERE root=12;
} {12 24 25}
# t2 root IN [10,12]
do_execsql_test 2.4 {
  SELECT id FROM c2 WHERE root IN (10,12) ORDER BY id;
} {10 12 20 21 24 25}
# t2 root IN [10,12] (sorted)
do_execsql_test 2.5 {
  SELECT id FROM c2 WHERE root IN (10,12) ORDER BY +id;
} {10 12 20 21 24 25}

# t2 c2up from 20
do_execsql_test 3.0 {
  CREATE VIRTUAL TABLE c2up USING transitive_closure(
    tablename = t2,
    idcolumn = y,
    parentcolumn = x
  );
  SELECT id FROM c2up WHERE root=20;
} {1 2 5 10 20}

# cx as c2up
do_execsql_test 3.1 {
  SELECT id FROM cx
   WHERE root=20
     AND tablename='t2'
     AND idcolumn='y'
     AND parentcolumn='x';
} {1 2 5 10 20}

# t2 first cousins of 20
do_execsql_test 3.2 {
  SELECT DISTINCT id FROM c2
   WHERE root IN (SELECT id FROM c2up
                   WHERE root=20 AND depth<=2)
   ORDER BY id;
} {5 10 11 20 21 22 23}

# t2 first cousins of 20
do_execsql_test 3.3 {
  SELECT id FROM c2
   WHERE root=(SELECT id FROM c2up
               WHERE root=20 AND depth=2)
     AND depth=2
  EXCEPT
  SELECT id FROM c2
   WHERE root=(SELECT id FROM c2up
               WHERE root=20 AND depth=1)
     AND depth<=1
   ORDER BY id;
} {22 23}

# missing tablename.
do_test 4.1 {
  catchsql {
    SELECT id FROM cx
     WHERE root=20
       AND tablename='t3'
       AND idcolumn='y'
       AND parentcolumn='x';
  }
} {1 {no such table: t3}}

# missing idcolumn
do_test 4.2 {
  catchsql {
    SELECT id FROM cx
     WHERE root=20
       AND tablename='t2'
       AND idcolumn='xyz'
       AND parentcolumn='x';
  }
} {1 {no such column: t2.xyz}}

# missing parentcolumn
do_test 4.3 {
  catchsql {
    SELECT id FROM cx
     WHERE root=20
       AND tablename='t2'
       AND idcolumn='x'
       AND parentcolumn='pqr';
  }
} {1 {no such column: t2.pqr}}

# generic closure
do_execsql_test 5.1 {
  CREATE VIRTUAL TABLE temp.closure USING transitive_closure;
  SELECT id FROM closure
   WHERE root=1
     AND depth=3
     AND tablename='t1'
     AND idcolumn='x'
     AND parentcolumn='y'
  ORDER BY id;
} {8 9 10 11 12 13 14 15}

finish_test

Changes to test/fuzzer1.test

20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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}}








|
<
<
<
<
<







20
21
22
23
24
25
26
27





28
29
30
31
32
33
34
ifcapable !vtab {
  finish_test
  return
}

set ::testprefix fuzzer1

load_static_extension db fuzzer






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

Changes to test/fuzzerfault.test

13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
ifcapable !vtab { finish_test ; return }
set ::testprefix fuzzerfault

register_fuzzer_module db

do_test 1-pre1 {
  execsql {
    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);







|







13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
ifcapable !vtab { finish_test ; return }
set ::testprefix fuzzerfault

load_static_extension db fuzzer

do_test 1-pre1 {
  execsql {
    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);

Changes to test/memdb.test

361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
    DELETE FROM t5 WHERE x>0;
    SELECT * FROM t5;
  }
} {}

ifcapable subquery&&vtab {
  do_test memdb-7.1 {
    register_wholenumber_module db
    execsql {
      CREATE TABLE t6(x);
      CREATE VIRTUAL TABLE nums USING wholenumber;
      INSERT INTO t6 SELECT value FROM nums WHERE value BETWEEN 1 AND 256;
      SELECT count(*) FROM (SELECT DISTINCT x FROM t6);
    }
  } {256}







|







361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
    DELETE FROM t5 WHERE x>0;
    SELECT * FROM t5;
  }
} {}

ifcapable subquery&&vtab {
  do_test memdb-7.1 {
    load_static_extension db wholenumber
    execsql {
      CREATE TABLE t6(x);
      CREATE VIRTUAL TABLE nums USING wholenumber;
      INSERT INTO t6 SELECT value FROM nums WHERE value BETWEEN 1 AND 256;
      SELECT count(*) FROM (SELECT DISTINCT x FROM t6);
    }
  } {256}

Changes to test/regexp1.test

12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# This file implements test for the REGEXP operator in test_regexp.c.
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl

do_test regexp1-1.1 {
  sqlite3_add_regexp_func db
  db eval {
    CREATE TABLE t1(x INTEGER PRIMARY KEY, y TEXT);
    INSERT INTO t1 VALUES(1, 'For since by man came death,');
    INSERT INTO t1 VALUES(2, 'by man came also the resurrection of the dead.');
    INSERT INTO t1 VALUES(3, 'For as in Adam all die,');
    INSERT INTO t1 VALUES(4, 'even so in Christ shall all be made alive.');








|







12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# This file implements test for the REGEXP operator in test_regexp.c.
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl

do_test regexp1-1.1 {
  load_static_extension db regexp
  db eval {
    CREATE TABLE t1(x INTEGER PRIMARY KEY, y TEXT);
    INSERT INTO t1 VALUES(1, 'For since by man came death,');
    INSERT INTO t1 VALUES(2, 'by man came also the resurrection of the dead.');
    INSERT INTO t1 VALUES(3, 'For as in Adam all die,');
    INSERT INTO t1 VALUES(4, 'even so in Christ shall all be made alive.');

Changes to test/selectD.test

147
148
149
150
151
152
153
154



















155
    db eval {
      SELECT t1.*, t2.*, t3.*, t4.b
        FROM (t1 LEFT JOIN t2 USING(a)) JOIN (t3 LEFT JOIN t4 USING(a))
             ON t1.a=t3.a-111;
    }
  } {111 x1 111 x2 222 x3 {}}
}




















finish_test








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

147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
    db eval {
      SELECT t1.*, t2.*, t3.*, t4.b
        FROM (t1 LEFT JOIN t2 USING(a)) JOIN (t3 LEFT JOIN t4 USING(a))
             ON t1.a=t3.a-111;
    }
  } {111 x1 111 x2 222 x3 {}}
}

# The following test was added on 2013-04-24 in order to verify that
# the datatypes and affinities of sub-sub-queries are set prior to computing
# the datatypes and affinities of the parent sub-queries because the 
# latter computation depends on the former.
#
do_execsql_test selectD-4.1 {
  CREATE TABLE t41(a INTEGER PRIMARY KEY, b INTEGER);
  CREATE TABLE t42(d INTEGER PRIMARY KEY, e INTEGER);
  CREATE TABLE t43(f INTEGER PRIMARY KEY, g INTEGER);
  EXPLAIN QUERY PLAN
  SELECT * 
   FROM t41
   LEFT JOIN (SELECT count(*) AS cnt, x1.d
                FROM (t42 INNER JOIN t43 ON d=g) AS x1
               WHERE x1.d>5
               GROUP BY x1.d) AS x2
                  ON t41.b=x2.d;
} {/.*SEARCH SUBQUERY 1 AS x2 USING AUTOMATIC.*/}

finish_test

Changes to test/spellfix.test

12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
..
80
81
82
83
84
85
86




















87
88
89
90
91
92
93

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix spellfix

ifcapable !vtab { finish_test ; return }

register_spellfix_module db

set vocab {
rabbi rabbit rabbits rabble rabid rabies raccoon raccoons race raced racer
racers races racetrack racial racially racing rack racked racket racketeer
racketeering racketeers rackets racking racks radar radars radial radially
radian radiance radiant radiantly radiate radiated radiates radiating radiation
radiations radiator radiators radical radically radicals radices radii radio
................................................................................
} {
  do_execsql_test 1.2.$tn {
    SELECT word, matchlen FROM t1 WHERE word MATCH $word 
     ORDER BY score, word LIMIT 5
  } $res
}






















do_execsql_test 2.1 {
  CREATE VIRTUAL TABLE t2 USING spellfix1;
  INSERT INTO t2 (word, soundslike) VALUES('school', 'skuul');
  INSERT INTO t2 (word, soundslike) VALUES('psalm', 'sarm');
  SELECT word, matchlen FROM t2 WHERE word MATCH 'sar*' LIMIT 5;
} {psalm 4}







|







 







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







12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
..
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix spellfix

ifcapable !vtab { finish_test ; return }

load_static_extension db spellfix nextchar

set vocab {
rabbi rabbit rabbits rabble rabid rabies raccoon raccoons race raced racer
racers races racetrack racial racially racing rack racked racket racketeer
racketeering racketeers rackets racking racks radar radars radial radially
radian radiance radiant radiantly radiate radiated radiates radiating radiation
radiations radiator radiators radical radically radicals radices radii radio
................................................................................
} {
  do_execsql_test 1.2.$tn {
    SELECT word, matchlen FROM t1 WHERE word MATCH $word 
     ORDER BY score, word LIMIT 5
  } $res
}

# Tests of the next_char function.
#
do_test 1.10 {
  db eval {
    CREATE TABLE vocab(w TEXT PRIMARY KEY);
    INSERT INTO vocab SELECT word FROM t1;
  }
} {}
do_execsql_test 1.11 {
  SELECT next_char('re','vocab','w');
} {a}
do_execsql_test 1.12 {
  SELECT next_char('r','vocab','w');
} {ae}
do_execsql_test 1.13 {
  SELECT next_char('','vocab','w');
} {r}
do_test 1.14 {
  catchsql {SELECT next_char('','xyzzy','a')}
} {1 {no such table: xyzzy}}

do_execsql_test 2.1 {
  CREATE VIRTUAL TABLE t2 USING spellfix1;
  INSERT INTO t2 (word, soundslike) VALUES('school', 'skuul');
  INSERT INTO t2 (word, soundslike) VALUES('psalm', 'sarm');
  SELECT word, matchlen FROM t2 WHERE word MATCH 'sar*' LIMIT 5;
} {psalm 4}

Changes to test/tkt-2d1a5c67d.test

42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
    }
  } {wal A 3 4 B 1 2 C 1 2}
}

db close
forcedelete test.db test.db-wal
sqlite3 db test.db
register_wholenumber_module db
db eval {
  PRAGMA journal_mode=WAL;
  CREATE TABLE t1(a,b);
  CREATE INDEX t1b ON t1(b);
  CREATE TABLE t2(x,y);
  CREATE VIRTUAL TABLE nums USING wholenumber;
  INSERT INTO t2 SELECT value, randomblob(1000) FROM nums







|







42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
    }
  } {wal A 3 4 B 1 2 C 1 2}
}

db close
forcedelete test.db test.db-wal
sqlite3 db test.db
load_static_extension db wholenumber
db eval {
  PRAGMA journal_mode=WAL;
  CREATE TABLE t1(a,b);
  CREATE INDEX t1b ON t1(b);
  CREATE TABLE t2(x,y);
  CREATE VIRTUAL TABLE nums USING wholenumber;
  INSERT INTO t2 SELECT value, randomblob(1000) FROM nums

Changes to test/zerodamage.test

55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
  set ::max_journal_size 0
  proc xDeleteCallback {method file args} {
    set sz [file size $file]
    if {$sz>$::max_journal_size} {set ::max_journal_size $sz}
  }
  tv filter xDelete
  tv script xDeleteCallback
  register_wholenumber_module db
  db eval {
    PRAGMA page_size=1024;
    PRAGMA journal_mode=DELETE;
    PRAGMA cache_size=5;
    CREATE VIRTUAL TABLE nums USING wholenumber;
    CREATE TABLE t1(x, y);
    INSERT INTO t1 SELECT value, randomblob(100) FROM nums







|







55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
  set ::max_journal_size 0
  proc xDeleteCallback {method file args} {
    set sz [file size $file]
    if {$sz>$::max_journal_size} {set ::max_journal_size $sz}
  }
  tv filter xDelete
  tv script xDeleteCallback
  load_static_extension db wholenumber
  db eval {
    PRAGMA page_size=1024;
    PRAGMA journal_mode=DELETE;
    PRAGMA cache_size=5;
    CREATE VIRTUAL TABLE nums USING wholenumber;
    CREATE TABLE t1(x, y);
    INSERT INTO t1 SELECT value, randomblob(100) FROM nums

Changes to tool/build-shell.sh

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
make sqlite3.c
gcc -o sqlite3 -g -Os -I. \
   -DSQLITE_THREADSAFE=0 \
   -DSQLITE_ENABLE_VFSTRACE \
   -DSQLITE_ENABLE_STAT3 \
   -DSQLITE_ENABLE_FTS4 \
   -DSQLITE_ENABLE_RTREE \
   -DSQLITE_ENABLE_REGEXP \
   -DSQLITE_ENABLE_SPELLFIX -DSQLITE_CORE=1 \
   -DHAVE_READLINE \
   -DHAVE_USLEEP=1 \
   ../sqlite/src/shell.c \
   ../sqlite/src/test_regexp.c \
   ../sqlite/src/test_spellfix.c \
   ../sqlite/src/test_vfstrace.c \
   sqlite3.c -ldl -lreadline -lncurses







<
<



<
<


11
12
13
14
15
16
17


18
19
20


21
22
make sqlite3.c
gcc -o sqlite3 -g -Os -I. \
   -DSQLITE_THREADSAFE=0 \
   -DSQLITE_ENABLE_VFSTRACE \
   -DSQLITE_ENABLE_STAT3 \
   -DSQLITE_ENABLE_FTS4 \
   -DSQLITE_ENABLE_RTREE \


   -DHAVE_READLINE \
   -DHAVE_USLEEP=1 \
   ../sqlite/src/shell.c \


   ../sqlite/src/test_vfstrace.c \
   sqlite3.c -ldl -lreadline -lncurses