/ Changes On Branch fts5
Login

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

Changes In Branch fts5 Excluding Merge-Ins

This is equivalent to a diff from f6a88ccc to 7635c680

2016-03-29
21:19
Fix some code and test coverage issues in fts5_index.c. (Leaf check-in: 7635c680 user: dan tags: fts5)
10:14
Version 3.12.0 (check-in: e9bb4cf4 user: drh tags: trunk, release, version-3.12.0)
2016-03-28
20:13
Add further tests for savepoint rollback. Fix various code issues and add missing comments in fts5_index.c. (check-in: a805c6f7 user: dan tags: fts5)
14:57
Open a statement transaction for "CREATE VIRTUAL TABLE" statements in order to ensure that if the xCreate() call fails, changes made to the sqlite_master and possibly other tables are rolled back. (Closed-Leaf check-in: d0a3853b user: dan tags: vcreate-stmt)
11:01
Fix the multiplexor so that it does not assume that the xGetLastError method is non-NULL in the child VFS. (check-in: f6a88ccc user: drh tags: trunk)
2016-03-26
15:36
More changes to the shellN.test scripts to get them working on all variations of Windows. (check-in: 8213c2f5 user: drh tags: trunk)

Changes to ext/fts5/fts5Int.h.

342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
...
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
#define sqlite3Fts5IterEof(x) ((x)->bEof)

/*
** Values used as part of the flags argument passed to IndexQuery().
*/
#define FTS5INDEX_QUERY_PREFIX     0x0001   /* Prefix query */
#define FTS5INDEX_QUERY_DESC       0x0002   /* Docs in descending rowid order */
#define FTS5INDEX_QUERY_TEST_NOIDX 0x0004   /* Do not use prefix index */
#define FTS5INDEX_QUERY_SCAN       0x0008   /* Scan query (fts5vocab) */

/* The following are used internally by the fts5_index.c module. They are
** defined here only to make it easier to avoid clashes with the flags
** above. */
#define FTS5INDEX_QUERY_SKIPEMPTY  0x0010
#define FTS5INDEX_QUERY_NOOUTPUT   0x0020
................................................................................

/* 
** Called during virtual module initialization to register UDF 
** fts5_decode() with SQLite 
*/
int sqlite3Fts5IndexInit(sqlite3*);

int sqlite3Fts5IndexSetCookie(Fts5Index*, int);

/*
** Return the total number of entries read from the %_data table by 
** this connection since it was created.
*/
int sqlite3Fts5IndexReads(Fts5Index *p);

int sqlite3Fts5IndexReinit(Fts5Index *p);
int sqlite3Fts5IndexOptimize(Fts5Index *p);
int sqlite3Fts5IndexMerge(Fts5Index *p, int nMerge);
int sqlite3Fts5IndexReset(Fts5Index *p);

int sqlite3Fts5IndexLoadConfig(Fts5Index *p);



/*
** End of interface to code in fts5_index.c.
**************************************************************************/

/**************************************************************************
** Interface to code in fts5_varint.c. 







<







 







|










|


>
>







342
343
344
345
346
347
348

349
350
351
352
353
354
355
...
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
#define sqlite3Fts5IterEof(x) ((x)->bEof)

/*
** Values used as part of the flags argument passed to IndexQuery().
*/
#define FTS5INDEX_QUERY_PREFIX     0x0001   /* Prefix query */
#define FTS5INDEX_QUERY_DESC       0x0002   /* Docs in descending rowid order */

#define FTS5INDEX_QUERY_SCAN       0x0008   /* Scan query (fts5vocab) */

/* The following are used internally by the fts5_index.c module. They are
** defined here only to make it easier to avoid clashes with the flags
** above. */
#define FTS5INDEX_QUERY_SKIPEMPTY  0x0010
#define FTS5INDEX_QUERY_NOOUTPUT   0x0020
................................................................................

/* 
** Called during virtual module initialization to register UDF 
** fts5_decode() with SQLite 
*/
int sqlite3Fts5IndexInit(sqlite3*);

int sqlite3Fts5IndexIncrCookie(Fts5Index*);

/*
** Return the total number of entries read from the %_data table by 
** this connection since it was created.
*/
int sqlite3Fts5IndexReads(Fts5Index *p);

int sqlite3Fts5IndexReinit(Fts5Index *p);
int sqlite3Fts5IndexOptimize(Fts5Index *p);
int sqlite3Fts5IndexMerge(Fts5Index *p, int nMerge);
int sqlite3Fts5IndexNewTrans(Fts5Index *p);

int sqlite3Fts5IndexLoadConfig(Fts5Index *p);

void sqlite3Fts5IndexCloseReader(Fts5Index*);

/*
** End of interface to code in fts5_index.c.
**************************************************************************/

/**************************************************************************
** Interface to code in fts5_varint.c. 

Changes to ext/fts5/fts5_index.c.

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
...
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
...
202
203
204
205
206
207
208















209
210
211
212
213
214
215
...
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
...
301
302
303
304
305
306
307

308
309
310
311
312





313
314
315
316
317
318
319
...
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
...
524
525
526
527
528
529
530







531
532
533
534
535
536
537
...
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
...
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
...
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
....
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
....
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
....
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
....
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
....
3019
3020
3021
3022
3023
3024
3025














3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
3038
3039
3040
3041
3042
3043
3044
3045
3046
....
3411
3412
3413
3414
3415
3416
3417
3418
3419
3420
3421
3422
3423
3424
3425
3426
....
3466
3467
3468
3469
3470
3471
3472
3473
3474
3475
3476
3477
3478
3479
3480
3481
3482
3483
3484
3485
3486
3487
3488
3489
3490
3491
3492
3493
....
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
3723
....
3732
3733
3734
3735
3736
3737
3738




3739
3740
3741
3742


3743
3744
3745
3746
3747
3748
3749
3750
3751
3752
3753
3754
3755
3756
3757
3758
....
3793
3794
3795
3796
3797
3798
3799
3800
3801
3802
3803
3804
3805
3806
3807
3808
3809
3810
3811
3812
3813
3814
3815
3816
3817
3818
3819
3820
3821
3822
3823
3824
3825
3826
3827
3828
3829
3830
3831
3832
3833
3834
3835
3836
3837
3838
3839
3840
3841
3842
3843

3844
3845
3846
3847
3848
3849
3850
3851
3852
3853
3854
3855
3856
3857
3858
....
3861
3862
3863
3864
3865
3866
3867
3868
3869
3870
3871
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889

3890
3891
3892
3893
3894
3895
3896
3897
3898
3899
3900
3901
3902
3903
3904
3905
3906
3907
3908
3909
3910
3911
3912
3913
3914
3915
3916
3917
3918
3919



3920
3921
3922
3923
3924
3925
3926
3927
3928
3929
3930
3931
3932
3933
3934
3935
3936
3937
3938
3939
3940
3941
3942
3943
3944
3945
3946
3947
3948
3949
3950
3951
3952
3953
3954
3955
3956
3957
3958
3959
3960
3961
3962
3963
3964

3965
3966
3967
3968
3969
3970
3971
3972



3973
3974
3975
3976
3977

3978
3979
3980
3981
3982
3983
3984
3985
3986
3987
3988
3989
3990
3991
3992
3993
3994
3995
3996
3997
3998
3999
4000
4001
4002
4003
4004
4005
4006
4007
4008
4009
4010
4011
4012
4013
4014
4015
4016
4017
4018
4019
4020
4021
4022
4023
4024
4025
4026
4027
4028
4029
4030
4031
4032
4033
4034




4035
4036
4037
4038
4039
4040
4041
4042
4043
4044
4045
4046
4047
4048
4049
4050
4051
4052
4053
4054
4055
4056
4057
4058
4059
4060
4061
4062
4063
4064
4065
4066
4067
4068
4069
4070
4071
4072
4073
4074
4075
4076
4077
4078
4079
4080


4081
4082
4083
4084
4085
4086
4087
....
4132
4133
4134
4135
4136
4137
4138





4139
4140
4141
4142
4143
4144
4145
4146
4147
4148





4149



4150
4151
4152
4153
4154
4155
4156
4157
4158
4159
4160
4161
4162
....
4175
4176
4177
4178
4179
4180
4181
4182
4183
4184
4185
4186
4187
4188
4189
....
4210
4211
4212
4213
4214
4215
4216
4217
4218
4219
4220
4221
4222
4223
4224
....
4235
4236
4237
4238
4239
4240
4241
4242
4243
4244
4245
4246
4247
4248
4249
4250
4251
4252
4253
4254
4255
4256
4257
....
4368
4369
4370
4371
4372
4373
4374





4375
4376
4377
4378
4379
4380
4381
....
4386
4387
4388
4389
4390
4391
4392
4393
4394
4395
4396
4397
4398
4399
4400
4401
4402
4403
4404
4405
4406
4407
4408
4409
4410
4411
....
4418
4419
4420
4421
4422
4423
4424
4425
4426
4427
4428
4429
4430
4431

4432
4433
4434
4435
4436


4437
4438
4439
4440
4441
4442
4443
4444
4445
4446
4447
4448
4449
4450
4451
4452
4453
4454
4455
4456
4457
4458
4459
4460
4461
4462
4463
4464
4465
4466
4467
4468
4469
4470
4471
4472
4473
4474
4475
4476
4477
4478
4479
4480
4481
4482
4483
4484
4485
4486
4487
4488
4489
4490
4491
4492
4493
4494
4495
4496
4497
4498
4499
4500
4501
4502
4503
4504
4505
4506
4507
4508
4509
4510
4511
4512
4513
4514
4515
4516
4517
4518
4519
4520
4521
4522
4523
4524
4525
4526
4527
4528
4529
4530
4531
4532
4533
4534
4535
4536
4537
4538
4539
4540
4541
4542
4543
4544
4545
4546
4547
4548
4549
4550
4551
4552
4553
4554
4555
4556
4557
4558
4559
4560
4561
4562
4563
4564
4565
4566
4567
4568
4569
4570
4571
4572
4573
4574
4575
4576
4577
4578
4579

4580
4581





4582
4583
4584
4585
4586
4587
4588
4589
4590
4591
4592
4593
4594
4595
4596
4597
4598
4599
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
4614
4615
4616
4617
4618
4619
4620


4621
4622
4623
4624
4625
4626
4627
4628
4629
4630
....
4647
4648
4649
4650
4651
4652
4653












4654
4655
4656
4657
4658
4659
4660
....
4703
4704
4705
4706
4707
4708
4709







4710
4711
4712
4713
4714
4715
4716
4717
4718
4719








4720
4721
4722
4723
4724
4725
4726
....
4728
4729
4730
4731
4732
4733
4734
4735


4736
4737
4738
4739
4740
4741
4742
....
4755
4756
4757
4758
4759
4760
4761






4762
4763
4764
4765
4766
4767
4768
4769
4770
4771
4772
4773
4774
4775
4776
4777
4778
4779
4780
4781
4782
4783
4784
4785
4786
4787
4788
4789
4790
4791
4792
4793
4794
4795
4796
4797
4798
4799
4800
4801
4802
4803
4804










4805
4806
4807
4808
4809
4810
4811
....
4851
4852
4853
4854
4855
4856
4857



















4858
4859
4860
4861
4862
4863
4864
....
4973
4974
4975
4976
4977
4978
4979





4980
4981
4982
4983
4984
4985
4986
4987
4988
4989
4990
4991
4992
4993
....
4995
4996
4997
4998
4999
5000
5001

5002
5003
5004
5005
5006
5007
5008
5009
5010
5011
5012
....
5016
5017
5018
5019
5020
5021
5022
5023
5024
5025
5026
5027
5028
5029
5030
....
5100
5101
5102
5103
5104
5105
5106
5107
5108
5109
5110
5111
5112
5113
5114
5115
5116
5117
5118
5119
5120

5121
5122
5123
5124
5125
5126
5127
5128
5129
5130
5131
5132
5133
5134
5135
....
5153
5154
5155
5156
5157
5158
5159
5160

5161
5162
5163

5164
5165
5166
5167
5168
5169
5170
5171
5172
5173
5174
....
5263
5264
5265
5266
5267
5268
5269


5270
5271
5272
5273
5274
5275
5276
....
5292
5293
5294
5295
5296
5297
5298
5299

5300


5301
5302
5303
5304
5305
5306
5307
5308
5309
5310
5311
5312
5313
5314
5315
5316
5317
5318
5319
5320
5321
5322
5323
5324
5325
5326



5327
5328
5329
5330
5331
5332
5333
....
5340
5341
5342
5343
5344
5345
5346
5347
5348
5349
5350
5351
5352
5353
5354
5355
5356
5357
5358
5359
5360
5361
5362
5363
5364
5365
5366
5367
5368
5369
5370
5371
5372
5373
....
5381
5382
5383
5384
5385
5386
5387
5388
5389
5390
5391
5392
5393
5394
5395
....
5405
5406
5407
5408
5409
5410
5411



5412
5413
5414
5415
5416
5417
5418
....
5421
5422
5423
5424
5425
5426
5427
5428
5429
5430
5431
5432
5433
5434
5435
....
5453
5454
5455
5456
5457
5458
5459
5460





5461
5462
5463
5464
5465
5466
5467
5468
5469
5470
5471
5472
5473
5474
5475
5476
5477
5478
5479
5480
5481
5482
5483
5484
5485
5486
5487
5488
5489
5490
5491
5492
5493
5494
5495
5496
5497
5498
5499
5500
5501
5502
5503
5504
5505
5506
5507
5508


5509
5510
5511
5512
5513
5514
5515
....
5656
5657
5658
5659
5660
5661
5662


5663
5664
5665
5666
5667
5668
5669
5670
5671
5672
5673
5674

5675
5676
5677
5678
5679
5680
5681
....
6385
6386
6387
6388
6389
6390
6391
6392
6393
6394
6395
6396
6397
6398
6399
6400
6401
6402
6403
6404
6405
6406
6407
6408
6409
6410
6411
6412
6413
6414
6415
6416
6417
6418
6419
6420
6421
6422
6423
6424
6425
6426
6427
6428
6429
6430
6431
6432
....
6439
6440
6441
6442
6443
6444
6445
6446
6447
6448
6449
6450
6451
6452
6453
6454
6455
6456
6457
6458
6459
6460
6461
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
******************************************************************************
**
** Low level access to the FTS index stored in the database file. The 
** routines in this file file implement all read and write access to the
** %_data table. Other parts of the system access this functionality via
** the interface defined in fts5Int.h.
*/


#include "fts5Int.h"

/*
** Overview:
**
** The %_data table contains all the FTS indexes for an FTS5 virtual table.
** As well as the main term index, there may be up to 31 prefix indexes.
** The format is similar to FTS3/4, except that:

**
**   * all segment b-tree leaf data is stored in fixed size page records 
**     (e.g. 1000 bytes). A single doclist may span multiple pages. Care is 
**     taken to ensure it is possible to iterate in either direction through 
**     the entries in a doclist, or to seek to a specific entry within a 
**     doclist, without loading it into memory.
**
................................................................................
**   * large doclists that span many pages have associated "doclist index"
**     records that contain a copy of the first rowid on each page spanned by
**     the doclist. This is used to speed up seek operations, and merges of
**     large doclists with very small doclists.
**
**   * extra fields in the "structure record" record the state of ongoing
**     incremental merge operations.
**
*/


#define FTS5_OPT_WORK_UNIT  1000  /* Number of leaf pages per optimize step */
#define FTS5_WORK_UNIT      64    /* Number of leaf pages in unit of work */

#define FTS5_MIN_DLIDX_SIZE 4     /* Add dlidx if this many empty pages */

#define FTS5_MAIN_PREFIX '0'

#if FTS5_MAX_PREFIX_INDEXES > 31
# error "FTS5_MAX_PREFIX_INDEXES is too large"
#endif

/*
** Details:

**
** The %_data table managed by this module,
**
**     CREATE TABLE %_data(id INTEGER PRIMARY KEY, block BLOB);
**
** , contains the following 5 types of records. See the comments surrounding
** the FTS5_*_ROWID macros below for a description of how %_data rowids are 
** assigned to each fo them.
**
** 1. Structure Records:
**
**   The set of segments that make up an index - the index structure - are
**   recorded in a single record within the %_data table. The record consists
**   of a single 32-bit configuration cookie value followed by a list of 
**   SQLite varints. If the FTS table features more than one index (because
................................................................................
**
**       + the first term on each page is stored in the same way as the
**         very first term of the segment:
**
**             varint : size of first term
**             blob:    first term data
**
** 5. Segment doclist indexes:
**
**   Doclist indexes are themselves b-trees, however they usually consist of
**   a single leaf record only. The format of each doclist index leaf page 
**   is:
**
**     * Flags byte. Bits are:
**         0x01: Clear if leaf is also the root page, otherwise set.
................................................................................
**
**     * Copy of first rowid on page indicated by previous field. As a varint.
**
**     * A list of delta-encoded varints - the first rowid on each subsequent
**       child page. 
**
*/
















/*
** Rowids for the averages and structure records in the %_data table.
*/
#define FTS5_AVERAGES_ROWID     1    /* Rowid used for the averages record */
#define FTS5_STRUCTURE_ROWID   10    /* The structure record */

................................................................................
#define FTS5_DATA_PADDING 20

typedef struct Fts5Data Fts5Data;
typedef struct Fts5DlidxIter Fts5DlidxIter;
typedef struct Fts5DlidxLvl Fts5DlidxLvl;
typedef struct Fts5DlidxWriter Fts5DlidxWriter;
typedef struct Fts5Iter Fts5Iter;
typedef struct Fts5PageWriter Fts5PageWriter;
typedef struct Fts5SegIter Fts5SegIter;
typedef struct Fts5DoclistIter Fts5DoclistIter;
typedef struct Fts5SegWriter Fts5SegWriter;
typedef struct Fts5Structure Fts5Structure;
typedef struct Fts5StructureLevel Fts5StructureLevel;
typedef struct Fts5StructureSegment Fts5StructureSegment;

................................................................................
  sqlite3_stmt *pWriter;          /* "INSERT ... %_data VALUES(?,?)" */
  sqlite3_stmt *pDeleter;         /* "DELETE FROM %_data ... id>=? AND id<=?" */
  sqlite3_stmt *pIdxWriter;       /* "INSERT ... %_idx VALUES(?,?,?,?)" */
  sqlite3_stmt *pIdxDeleter;      /* "DELETE FROM %_idx WHERE segid=? */
  sqlite3_stmt *pIdxSelect;
  int nRead;                      /* Total number of blocks read */


  sqlite3_stmt *pDataVersion;
  i64 iStructVersion;             /* data_version when pStruct read */
  Fts5Structure *pStruct;         /* Current db structure (or NULL) */
};






struct Fts5DoclistIter {
  u8 *aEof;                       /* Pointer to 1 byte past end of doclist */

  /* Output variables. aPoslist==0 at EOF */
  i64 iRowid;
  u8 *aPoslist;
  int nPoslist;
................................................................................
  int nLevel;                     /* Number of levels in this index */
  Fts5StructureLevel aLevel[1];   /* Array of nLevel level objects */
};

/*
** An object of type Fts5SegWriter is used to write to segments.
*/
struct Fts5PageWriter {
  int pgno;                       /* Page number for this page */
  int iPrevPgidx;                 /* Previous value written into pgidx */
  Fts5Buffer buf;                 /* Buffer containing leaf data */
  Fts5Buffer pgidx;               /* Buffer containing page-index */
  Fts5Buffer term;                /* Buffer containing previous term on page */
};
struct Fts5DlidxWriter {
  int pgno;                       /* Page number for this page */
  int bPrevValid;                 /* True if iPrev is valid */
  i64 iPrev;                      /* Previous rowid value written to page */
  Fts5Buffer buf;                 /* Buffer containing page data */
};
struct Fts5SegWriter {
  int iSegid;                     /* Segid to write to */
  Fts5PageWriter writer;          /* PageWriter object */





  i64 iPrevRowid;                 /* Previous rowid written to current leaf */
  u8 bFirstRowidInDoclist;        /* True if next rowid is first in doclist */
  u8 bFirstRowidInPage;           /* True if next rowid is first in page */
  /* TODO1: Can use (writer.pgidx.n==0) instead of bFirstTermInPage */
  u8 bFirstTermInPage;            /* True if next term will be first in leaf */
  int nLeafWritten;               /* Number of leaf pages written */
  int nEmpty;                     /* Number of contiguous term-less nodes */

  int nDlidx;                     /* Allocated size of aDlidx[] array */
  Fts5DlidxWriter *aDlidx;        /* Array of Fts5DlidxWriter objects */

  /* Values to insert into the %_idx table */
................................................................................
  u8 bSkipEmpty;                  /* True to skip deleted entries */

  i64 iSwitchRowid;               /* Firstest rowid of other than aFirst[1] */
  Fts5CResult *aFirst;            /* Current merge state (see above) */
  Fts5SegIter aSeg[1];            /* Array of segment iterators */
};









/*
** An instance of the following type is used to iterate through the contents
** of a doclist-index record.
**
** pData:
**   Record containing the doclist-index data.
................................................................................
  fts5GetVarint32(&pLeaf->p[pLeaf->szLeaf], ret);
  return ret;
}

/*
** Close the read-only blob handle, if it is open.
*/
static void fts5CloseReader(Fts5Index *p){
  if( p->pReader ){
    sqlite3_blob *pReader = p->pReader;
    p->pReader = 0;
    sqlite3_blob_close(pReader);
  }
}

................................................................................
      ** is required.  */
      sqlite3_blob *pBlob = p->pReader;
      p->pReader = 0;
      rc = sqlite3_blob_reopen(pBlob, iRowid);
      assert( p->pReader==0 );
      p->pReader = pBlob;
      if( rc!=SQLITE_OK ){
        fts5CloseReader(p);
      }
      if( rc==SQLITE_ABORT ) rc = SQLITE_OK;
    }

    /* If the blob handle is not open at this point, open it and seek 
    ** to the requested entry.  */
    if( p->pReader==0 && rc==SQLITE_OK ){
................................................................................
      pRet = 0;
    }
  }

  return pRet;
}









static i64 fts5IndexDataVersion(Fts5Index *p){
  i64 iVersion = 0;

  if( p->rc==SQLITE_OK ){
    if( p->pDataVersion==0 ){
      p->rc = fts5IndexPrepareStmt(p, &p->pDataVersion, 
          sqlite3_mprintf("PRAGMA %Q.data_version", p->pConfig->zDb)
          );
      if( p->rc ) return 0;
    }

    if( SQLITE_ROW==sqlite3_step(p->pDataVersion) ){
      iVersion = sqlite3_column_int64(p->pDataVersion, 0);
    }
    p->rc = sqlite3_reset(p->pDataVersion);
  }

  return iVersion;
}














/*
** Read, deserialize and return the structure record.
**
** The Fts5Structure.aLevel[] and each Fts5StructureLevel.aSeg[] array
** are over-allocated as described for function fts5StructureDecode() 
** above.
**
** If an error occurs, NULL is returned and an error code left in the
** Fts5Index handle. If an error has already occurred when this function
** is called, it is a no-op.
*/
static Fts5Structure *fts5StructureRead(Fts5Index *p){

  if( p->pStruct==0 ){
    p->iStructVersion = fts5IndexDataVersion(p);
    if( p->rc==SQLITE_OK ){
      p->pStruct = fts5StructureReadUncached(p);
    }
  }

#if 0
  else{
    Fts5Structure *pTest = fts5StructureReadUncached(p);
    if( pTest ){
      int i, j;
      assert_nc( p->pStruct->nSegment==pTest->nSegment );
................................................................................

/*
** Return true if the iterator passed as the second argument currently
** points to a delete marker. A delete marker is an entry with a 0 byte
** position-list.
*/
static int fts5MultiIterIsEmpty(Fts5Index *p, Fts5Iter *pIter){
  Fts5SegIter *pSeg = &pIter->aSeg[pIter->aFirst[1].iFirst];
  return (p->rc==SQLITE_OK && pSeg->pLeaf && pSeg->nPos==0);
}

/*
** Advance iterator pIter to the next entry.
**
** This version of fts5SegIterNext() is only used by reverse iterators.
................................................................................
** This function is a no-op unless SQLITE_DEBUG is defined when this module
** is compiled. In that case, this function is essentially an assert() 
** statement used to verify that the contents of the pIter->aFirst[] array
** are correct.
*/
static void fts5AssertMultiIterSetup(Fts5Index *p, Fts5Iter *pIter){
  if( p->rc==SQLITE_OK ){
    Fts5SegIter *pFirst = &pIter->aSeg[ pIter->aFirst[1].iFirst ];
    int i;

    assert( (pFirst->pLeaf==0)==pIter->base.bEof );

    /* Check that pIter->iSwitchRowid is set correctly. */
    for(i=0; i<pIter->nSeg; i++){
      Fts5SegIter *p1 = &pIter->aSeg[i];
................................................................................
  return 0;
}

/*
** Set the pIter->bEof variable based on the state of the sub-iterators.
*/
static void fts5MultiIterSetEof(Fts5Iter *pIter){
  Fts5SegIter *pSeg = &pIter->aSeg[ pIter->aFirst[1].iFirst ];
  pIter->base.bEof = pSeg->pLeaf==0;
  pIter->iSwitchRowid = pSeg->iRowid;
}

/*
** Move the iterator to the next entry. 
**
................................................................................
    }

    if( pSeg->pLeaf==0 || bNewTerm 
     || fts5MultiIterAdvanceRowid(pIter, iFirst, &pSeg)
    ){
      fts5MultiIterAdvanced(p, pIter, iFirst, 1);
      fts5MultiIterSetEof(pIter);
      pSeg = &pIter->aSeg[pIter->aFirst[1].iFirst];
      if( pSeg->pLeaf==0 ) return;
    }

    fts5AssertMultiIterSetup(p, pIter);
    assert( pSeg==&pIter->aSeg[pIter->aFirst[1].iFirst] && pSeg->pLeaf );
    if( pIter->bSkipEmpty==0 || pSeg->nPos ){
      pIter->xSetOutputs(pIter, pSeg);
      return;
    }
    bUseFrom = 0;
  }
}
................................................................................
          }
        }
      }
    }while( i<nChunk );
  }
}















static void fts5ChunkIterate(
  Fts5Index *p,                   /* Index object */
  Fts5SegIter *pSeg,              /* Poslist of this iterator */
  void *pCtx,                     /* Context pointer for xChunk callback */
  void (*xChunk)(Fts5Index*, void*, const u8*, int)
){
  int nRem = pSeg->nPos;          /* Number of bytes still to come */
  Fts5Data *pData = 0;
  u8 *pChunk = &pSeg->pLeaf->p[pSeg->iLeafOffset];
  int nChunk = MIN(nRem, pSeg->pLeaf->szLeaf - pSeg->iLeafOffset);
  int pgno = pSeg->iLeafPgno;
  int pgnoSave = 0;

  /* This function does notmwork with detail=none databases. */
  assert( p->pConfig->eDetail!=FTS5_DETAIL_NONE );

  if( (pSeg->flags & FTS5_SEGITER_REVERSE)==0 ){
    pgnoSave = pgno+1;
  }

  while( 1 ){
................................................................................
    }
    fts5MultiIterSetEof(pNew);
    fts5AssertMultiIterSetup(p, pNew);

    if( pNew->bSkipEmpty && fts5MultiIterIsEmpty(p, pNew) ){
      fts5MultiIterNext(p, pNew, 0, 0);
    }else if( pNew->base.bEof==0 ){
      Fts5SegIter *pSeg = &pNew->aSeg[pNew->aFirst[1].iFirst];
      pNew->xSetOutputs(pNew, pSeg);
    }

  }else{
    fts5MultiIterFree(pNew);
    *ppOut = 0;
  }
}
................................................................................
}

/*
** Return true if the iterator is at EOF or if an error has occurred. 
** False otherwise.
*/
static int fts5MultiIterEof(Fts5Index *p, Fts5Iter *pIter){
  assert( p->rc 
      || (pIter->aSeg[ pIter->aFirst[1].iFirst ].pLeaf==0)==pIter->base.bEof 
  );
  return (p->rc || pIter->base.bEof);
}

/*
** Return the rowid of the entry that the iterator currently points
** to. If the iterator points to EOF when this function is called the
** results are undefined.
*/
static i64 fts5MultiIterRowid(Fts5Iter *pIter){
  assert( pIter->aSeg[ pIter->aFirst[1].iFirst ].pLeaf );
  return pIter->aSeg[ pIter->aFirst[1].iFirst ].iRowid;
}

/*
** Move the iterator to the next entry at or following iMatch.
*/
static void fts5MultiIterNextFrom(
  Fts5Index *p, 
................................................................................
static void fts5WriteBtreeTerm(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5SegWriter *pWriter,         /* Writer object */
  int nTerm, const u8 *pTerm      /* First term on new page */
){
  fts5WriteFlushBtree(p, pWriter);
  fts5BufferSet(&p->rc, &pWriter->btterm, nTerm, pTerm);
  pWriter->iBtPage = pWriter->writer.pgno;
}

/*
** This function is called when flushing a leaf page that contains no
** terms at all to disk.
*/
static void fts5WriteBtreeNoTerm(
................................................................................
    sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx->buf, 0);
  }

  /* Increment the "number of sequential leaves without a term" counter. */
  pWriter->nEmpty++;
}





static i64 fts5DlidxExtractFirstRowid(Fts5Buffer *pBuf){
  i64 iRowid;
  int iOff;



  iOff = 1 + fts5GetVarint(&pBuf->p[1], (u64*)&iRowid);
  fts5GetVarint(&pBuf->p[iOff], (u64*)&iRowid);
  return iRowid;
}

/*
** Rowid iRowid has just been appended to the current leaf page. It is the
** first on the page. This function appends an appropriate entry to the current
** doclist-index.
*/
static void fts5WriteDlidxAppend(
  Fts5Index *p, 
  Fts5SegWriter *pWriter, 
  i64 iRowid
){
  int i;
................................................................................
    }else{
      bDone = 1;
    }

    if( pDlidx->bPrevValid ){
      iVal = iRowid - pDlidx->iPrev;
    }else{
      i64 iPgno = (i==0 ? pWriter->writer.pgno : pDlidx[-1].pgno);
      assert( pDlidx->buf.n==0 );
      sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx->buf, !bDone);
      sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx->buf, iPgno);
      iVal = iRowid;
    }

    sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx->buf, iVal);
    pDlidx->bPrevValid = 1;
    pDlidx->iPrev = iRowid;
  }
}

static void fts5WriteFlushLeaf(Fts5Index *p, Fts5SegWriter *pWriter){
  static const u8 zero[] = { 0x00, 0x00, 0x00, 0x00 };
  Fts5PageWriter *pPage = &pWriter->writer;
  i64 iRowid;

static int nCall = 0;
nCall++;

  assert( (pPage->pgidx.n==0)==(pWriter->bFirstTermInPage) );

  /* Set the szLeaf header field. */
  assert( 0==fts5GetU16(&pPage->buf.p[2]) );
  fts5PutU16(&pPage->buf.p[2], (u16)pPage->buf.n);

  if( pWriter->bFirstTermInPage ){
    /* No term was written to this page. */
    assert( pPage->pgidx.n==0 );
    fts5WriteBtreeNoTerm(p, pWriter);
  }else{
    /* Append the pgidx to the page buffer. Set the szLeaf header field. */
    fts5BufferAppendBlob(&p->rc, &pPage->buf, pPage->pgidx.n, pPage->pgidx.p);
  }

  /* Write the page out to disk */
  iRowid = FTS5_SEGMENT_ROWID(pWriter->iSegid, pPage->pgno);
  fts5DataWrite(p, iRowid, pPage->buf.p, pPage->buf.n);

  /* Initialize the next page. */
  fts5BufferZero(&pPage->buf);
  fts5BufferZero(&pPage->pgidx);
  fts5BufferAppendBlob(&p->rc, &pPage->buf, 4, zero);

  pPage->iPrevPgidx = 0;
  pPage->pgno++;

  /* Increase the leaves written counter */
  pWriter->nLeafWritten++;

  /* The new leaf holds no terms or rowids */
  pWriter->bFirstTermInPage = 1;
  pWriter->bFirstRowidInPage = 1;
}

/*
** Append term pTerm/nTerm to the segment being written by the writer passed
** as the second argument.
**
................................................................................
*/
static void fts5WriteAppendTerm(
  Fts5Index *p, 
  Fts5SegWriter *pWriter,
  int nTerm, const u8 *pTerm 
){
  int nPrefix;                    /* Bytes of prefix compression for term */
  Fts5PageWriter *pPage = &pWriter->writer;
  Fts5Buffer *pPgidx = &pWriter->writer.pgidx;

  assert( p->rc==SQLITE_OK );
  assert( pPage->buf.n>=4 );
  assert( pPage->buf.n>4 || pWriter->bFirstTermInPage );

  /* If the current leaf page is full, flush it to disk. */
  if( (pPage->buf.n + pPgidx->n + nTerm + 2)>=p->pConfig->pgsz ){
    if( pPage->buf.n>4 ){
      fts5WriteFlushLeaf(p, pWriter);
    }
    fts5BufferGrow(&p->rc, &pPage->buf, nTerm+FTS5_DATA_PADDING);
  }
  
  /* TODO1: Updating pgidx here. */
  pPgidx->n += sqlite3Fts5PutVarint(
      &pPgidx->p[pPgidx->n], pPage->buf.n - pPage->iPrevPgidx
  );
  pPage->iPrevPgidx = pPage->buf.n;
#if 0
  fts5PutU16(&pPgidx->p[pPgidx->n], pPage->buf.n);

  pPgidx->n += 2;
#endif

  if( pWriter->bFirstTermInPage ){
    nPrefix = 0;
    if( pPage->pgno!=1 ){
      /* This is the first term on a leaf that is not the leftmost leaf in
      ** the segment b-tree. In this case it is necessary to add a term to
      ** the b-tree hierarchy that is (a) larger than the largest term 
      ** already written to the segment and (b) smaller than or equal to
      ** this term. In other words, a prefix of (pTerm/nTerm) that is one
      ** byte longer than the longest prefix (pTerm/nTerm) shares with the
      ** previous term. 
      **
      ** Usually, the previous term is available in pPage->term. The exception
      ** is if this is the first term written in an incremental-merge step.
      ** In this case the previous term is not available, so just write a
      ** copy of (pTerm/nTerm) into the parent node. This is slightly
      ** inefficient, but still correct.  */
      int n = nTerm;
      if( pPage->term.n ){
        n = 1 + fts5PrefixCompress(pPage->term.n, pPage->term.p, pTerm);
      }
      fts5WriteBtreeTerm(p, pWriter, n, pTerm);
      pPage = &pWriter->writer;
    }
  }else{
    nPrefix = fts5PrefixCompress(pPage->term.n, pPage->term.p, pTerm);
    fts5BufferAppendVarint(&p->rc, &pPage->buf, nPrefix);
  }




  /* Append the number of bytes of new data, then the term data itself
  ** to the page. */
  fts5BufferAppendVarint(&p->rc, &pPage->buf, nTerm - nPrefix);
  fts5BufferAppendBlob(&p->rc, &pPage->buf, nTerm - nPrefix, &pTerm[nPrefix]);

  /* Update the Fts5PageWriter.term field. */
  fts5BufferSet(&p->rc, &pPage->term, nTerm, pTerm);
  pWriter->bFirstTermInPage = 0;

  pWriter->bFirstRowidInPage = 0;
  pWriter->bFirstRowidInDoclist = 1;

  assert( p->rc || (pWriter->nDlidx>0 && pWriter->aDlidx[0].buf.n==0) );
  pWriter->aDlidx[0].pgno = pPage->pgno;
}

/*
** Append a rowid and position-list size field to the writers output. 
*/
static void fts5WriteAppendRowid(
  Fts5Index *p, 
  Fts5SegWriter *pWriter,
  i64 iRowid
){
  if( p->rc==SQLITE_OK ){
    Fts5PageWriter *pPage = &pWriter->writer;

    if( (pPage->buf.n + pPage->pgidx.n)>=p->pConfig->pgsz ){
      fts5WriteFlushLeaf(p, pWriter);
    }

    /* If this is to be the first rowid written to the page, set the 
    ** rowid-pointer in the page-header. Also append a value to the dlidx
    ** buffer, in case a doclist-index is required.  */
    if( pWriter->bFirstRowidInPage ){
      fts5PutU16(pPage->buf.p, (u16)pPage->buf.n);
      fts5WriteDlidxAppend(p, pWriter, iRowid);
    }

    /* Write the rowid. */
    if( pWriter->bFirstRowidInDoclist || pWriter->bFirstRowidInPage ){
      fts5BufferAppendVarint(&p->rc, &pPage->buf, iRowid);
    }else{
      assert( p->rc || iRowid>pWriter->iPrevRowid );

      fts5BufferAppendVarint(&p->rc, &pPage->buf, iRowid - pWriter->iPrevRowid);
    }
    pWriter->iPrevRowid = iRowid;
    pWriter->bFirstRowidInDoclist = 0;
    pWriter->bFirstRowidInPage = 0;
  }
}




static void fts5WriteAppendPoslistData(
  Fts5Index *p, 
  Fts5SegWriter *pWriter, 
  const u8 *aData, 
  int nData

){
  Fts5PageWriter *pPage = &pWriter->writer;
  const u8 *a = aData;
  int n = nData;
  
  assert( p->pConfig->pgsz>0 );
  while( p->rc==SQLITE_OK 
     && (pPage->buf.n + pPage->pgidx.n + n)>=p->pConfig->pgsz 
  ){
    int nReq = p->pConfig->pgsz - pPage->buf.n - pPage->pgidx.n;
    int nCopy = 0;
    while( nCopy<nReq ){
      i64 dummy;
      nCopy += fts5GetVarint(&a[nCopy], (u64*)&dummy);
    }
    fts5BufferAppendBlob(&p->rc, &pPage->buf, nCopy, a);
    a += nCopy;
    n -= nCopy;
    fts5WriteFlushLeaf(p, pWriter);
  }
  if( n>0 ){
    fts5BufferAppendBlob(&p->rc, &pPage->buf, n, a);
  }
}

/*
** Flush any data cached by the writer object to the database. Free any
** allocations associated with the writer.
*/
static void fts5WriteFinish(
  Fts5Index *p, 
  Fts5SegWriter *pWriter,         /* Writer object */
  int *pnLeaf                     /* OUT: Number of leaf pages in b-tree */
){
  int i;
  Fts5PageWriter *pLeaf = &pWriter->writer;
  if( p->rc==SQLITE_OK ){
    assert( pLeaf->pgno>=1 );
    if( pLeaf->buf.n>4 ){
      fts5WriteFlushLeaf(p, pWriter);
    }
    *pnLeaf = pLeaf->pgno-1;
    if( pLeaf->pgno>1 ){
      fts5WriteFlushBtree(p, pWriter);
    }
  }
  fts5BufferFree(&pLeaf->term);
  fts5BufferFree(&pLeaf->buf);
  fts5BufferFree(&pLeaf->pgidx);
  fts5BufferFree(&pWriter->btterm);

  for(i=0; i<pWriter->nDlidx; i++){
    sqlite3Fts5BufferFree(&pWriter->aDlidx[i].buf);
  }
  sqlite3_free(pWriter->aDlidx);
}





static void fts5WriteInit(
  Fts5Index *p, 
  Fts5SegWriter *pWriter, 
  int iSegid
){
  const int nBuffer = p->pConfig->pgsz + FTS5_DATA_PADDING;

  memset(pWriter, 0, sizeof(Fts5SegWriter));
  pWriter->iSegid = iSegid;

  fts5WriteDlidxGrow(p, pWriter, 1);
  pWriter->writer.pgno = 1;
  pWriter->bFirstTermInPage = 1;
  pWriter->iBtPage = 1;

  assert( pWriter->writer.buf.n==0 );
  assert( pWriter->writer.pgidx.n==0 );

  /* Grow the two buffers to pgsz + padding bytes in size. */
  sqlite3Fts5BufferSize(&p->rc, &pWriter->writer.pgidx, nBuffer);
  sqlite3Fts5BufferSize(&p->rc, &pWriter->writer.buf, nBuffer);

  if( p->pIdxWriter==0 ){
    Fts5Config *pConfig = p->pConfig;
    fts5IndexPrepareStmt(p, &p->pIdxWriter, sqlite3_mprintf(
          "INSERT INTO '%q'.'%q_idx'(segid,term,pgno) VALUES(?,?,?)", 
          pConfig->zDb, pConfig->zName
    ));
  }

  if( p->rc==SQLITE_OK ){
    /* Initialize the 4-byte leaf-page header to 0x00. */
    memset(pWriter->writer.buf.p, 0, 4);
    pWriter->writer.buf.n = 4;

    /* Bind the current output segment id to the index-writer. This is an
    ** optimization over binding the same value over and over as rows are
    ** inserted into %_idx by the current writer.  */
    sqlite3_bind_int(p->pIdxWriter, 1, pWriter->iSegid);
  }
}

/*
** Iterator pIter was used to iterate through the input segments of on an
** incremental merge operation. This function is called if the incremental
** merge step has finished but the input has not been completely exhausted.


*/
static void fts5TrimSegments(Fts5Index *p, Fts5Iter *pIter){
  int i;
  Fts5Buffer buf;
  memset(&buf, 0, sizeof(Fts5Buffer));
  for(i=0; i<pIter->nSeg; i++){
    Fts5SegIter *pSeg = &pIter->aSeg[i];
................................................................................
        fts5DataWrite(p, iLeafRowid, buf.p, buf.n);
      }
    }
  }
  fts5BufferFree(&buf);
}






static void fts5MergeChunkCallback(
  Fts5Index *p, 
  void *pCtx, 
  const u8 *pChunk, int nChunk
){
  Fts5SegWriter *pWriter = (Fts5SegWriter*)pCtx;
  fts5WriteAppendPoslistData(p, pWriter, pChunk, nChunk);
}

/*





**



*/
static void fts5IndexMergeLevel(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5Structure **ppStruct,       /* IN/OUT: Stucture of index */
  int iLvl,                       /* Level to read input from */
  int *pnRem                      /* Write up to this many output leaves */
){
  Fts5Structure *pStruct = *ppStruct;
  Fts5StructureLevel *pLvl = &pStruct->aLevel[iLvl];
  Fts5StructureLevel *pLvlOut;
  Fts5Iter *pIter = 0;       /* Iterator to read input data */
  int nRem = pnRem ? *pnRem : 0;  /* Output leaf pages left to write */
  int nInput;                     /* Number of input segments */
................................................................................
  if( pLvl->nMerge ){
    pLvlOut = &pStruct->aLevel[iLvl+1];
    assert( pLvlOut->nSeg>0 );
    nInput = pLvl->nMerge;
    pSeg = &pLvlOut->aSeg[pLvlOut->nSeg-1];

    fts5WriteInit(p, &writer, pSeg->iSegid);
    writer.writer.pgno = pSeg->pgnoLast+1;
    writer.iBtPage = 0;
  }else{
    int iSegid = fts5AllocateSegid(p, pStruct);

    /* Extend the Fts5Structure object as required to ensure the output
    ** segment exists. */
    if( iLvl==pStruct->nLevel-1 ){
................................................................................
  bOldest = (pLvlOut->nSeg==1 && pStruct->nLevel==iLvl+2);

  assert( iLvl>=0 );
  for(fts5MultiIterNew(p, pStruct, flags, 0, 0, 0, iLvl, nInput, &pIter);
      fts5MultiIterEof(p, pIter)==0;
      fts5MultiIterNext(p, pIter, 0, 0)
  ){
    Fts5SegIter *pSegIter = &pIter->aSeg[ pIter->aFirst[1].iFirst ];
    int nPos;                     /* position-list size field value */
    int nTerm;
    const u8 *pTerm;

    /* Check for key annihilation. */
    if( pSegIter->nPos==0 && (bOldest || pSegIter->bDel==0) ) continue;

................................................................................

    /* Append the rowid to the output */
    /* WRITEPOSLISTSIZE */
    fts5WriteAppendRowid(p, &writer, fts5MultiIterRowid(pIter));

    if( eDetail==FTS5_DETAIL_NONE ){
      if( pSegIter->bDel ){
        fts5BufferAppendVarint(&p->rc, &writer.writer.buf, 0);
        if( pSegIter->nPos>0 ){
          fts5BufferAppendVarint(&p->rc, &writer.writer.buf, 0);
        }
      }
    }else{
      /* Append the position-list data to the output */
      nPos = pSegIter->nPos*2 + pSegIter->bDel;
      fts5BufferAppendVarint(&p->rc, &writer.writer.buf, nPos);
      fts5ChunkIterate(p, pSegIter, (void*)&writer, fts5MergeChunkCallback);
    }
  }

  /* Flush the last leaf page to disk. Set the output segment b-tree height
  ** and last leaf page number at the same time.  */
  fts5WriteFinish(p, &writer, &pSeg->pgnoLast);
................................................................................
    pStruct->nWriteCounter += nLeaf;
    nRem = (int)(p->nWorkUnit * nWork * pStruct->nLevel);

    fts5IndexMerge(p, ppStruct, nRem, p->pConfig->nAutomerge);
  }
}






static void fts5IndexCrisismerge(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5Structure **ppStruct        /* IN/OUT: Current structure of index */
){
  const int nCrisis = p->pConfig->nCrisisMerge;
  Fts5Structure *pStruct = *ppStruct;
  int iLvl = 0;
................................................................................
    assert( p->rc!=SQLITE_OK || pStruct->nLevel>(iLvl+1) );
    fts5StructurePromote(p, iLvl+1, pStruct);
    iLvl++;
  }
  *ppStruct = pStruct;
}

static int fts5IndexReturn(Fts5Index *p){
  int rc = p->rc;
  p->rc = SQLITE_OK;
  return rc;
}

typedef struct Fts5FlushCtx Fts5FlushCtx;
struct Fts5FlushCtx {
  Fts5Index *pIdx;
  Fts5SegWriter writer; 
};

/*
** Buffer aBuf[] contains a list of varints, all small enough to fit
** in a 32-bit integer. Return the size of the largest prefix of this 
** list nMax bytes or less in size.
*/
static int fts5PoslistPrefix(const u8 *aBuf, int nMax){
  int ret;
................................................................................
      ret += i;
    }
  }
  return ret;
}

/*
** Flush the contents of in-memory hash table iHash to a new level-0 
** segment on disk. Also update the corresponding structure record.
**
** If an error occurs, set the Fts5Index.rc error code. If an error has 
** already occurred, this function is a no-op.
*/
static void fts5FlushOneHash(Fts5Index *p){

  Fts5Hash *pHash = p->pHash;
  Fts5Structure *pStruct;
  int iSegid;
  int pgnoLast = 0;                 /* Last leaf page number in segment */



  /* Obtain a reference to the index structure and allocate a new segment-id
  ** for the new level-0 segment.  */
  pStruct = fts5StructureRead(p);
  iSegid = fts5AllocateSegid(p, pStruct);
  fts5StructureInvalidate(p);

  if( iSegid ){
    const int pgsz = p->pConfig->pgsz;
    int eDetail = p->pConfig->eDetail;
    Fts5StructureSegment *pSeg;   /* New segment within pStruct */
    Fts5Buffer *pBuf;             /* Buffer in which to assemble leaf page */
    Fts5Buffer *pPgidx;           /* Buffer in which to assemble pgidx */

    Fts5SegWriter writer;
    fts5WriteInit(p, &writer, iSegid);

    pBuf = &writer.writer.buf;
    pPgidx = &writer.writer.pgidx;

    /* fts5WriteInit() should have initialized the buffers to (most likely)
    ** the maximum space required. */
    assert( p->rc || pBuf->nSpace>=(pgsz + FTS5_DATA_PADDING) );
    assert( p->rc || pPgidx->nSpace>=(pgsz + FTS5_DATA_PADDING) );

    /* Begin scanning through hash table entries. This loop runs once for each
    ** term/doclist currently stored within the hash table. */
    if( p->rc==SQLITE_OK ){
      p->rc = sqlite3Fts5HashScanInit(pHash, 0, 0);
    }
    while( p->rc==SQLITE_OK && 0==sqlite3Fts5HashScanEof(pHash) ){
      const char *zTerm;          /* Buffer containing term */
      const u8 *pDoclist;         /* Pointer to doclist for this term */
      int nDoclist;               /* Size of doclist in bytes */

      /* Write the term for this entry to disk. */
      sqlite3Fts5HashScanEntry(pHash, &zTerm, &pDoclist, &nDoclist);
      fts5WriteAppendTerm(p, &writer, (int)strlen(zTerm), (const u8*)zTerm);

      assert( writer.bFirstRowidInPage==0 );
      if( pgsz>=(pBuf->n + pPgidx->n + nDoclist + 1) ){
        /* The entire doclist will fit on the current leaf. */
        fts5BufferSafeAppendBlob(pBuf, pDoclist, nDoclist);
      }else{
        i64 iRowid = 0;
        i64 iDelta = 0;
        int iOff = 0;

        /* The entire doclist will not fit on this leaf. The following 
        ** loop iterates through the poslists that make up the current 
        ** doclist.  */
        while( p->rc==SQLITE_OK && iOff<nDoclist ){
          iOff += fts5GetVarint(&pDoclist[iOff], (u64*)&iDelta);
          iRowid += iDelta;
          
          if( writer.bFirstRowidInPage ){
            fts5PutU16(&pBuf->p[0], (u16)pBuf->n);   /* first rowid on page */
            pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], iRowid);
            writer.bFirstRowidInPage = 0;
            fts5WriteDlidxAppend(p, &writer, iRowid);
          }else{
            pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], iDelta);
          }
          assert( pBuf->n<=pBuf->nSpace );

          if( eDetail==FTS5_DETAIL_NONE ){
            if( iOff<nDoclist && pDoclist[iOff]==0 ){
              pBuf->p[pBuf->n++] = 0;
              iOff++;
              if( iOff<nDoclist && pDoclist[iOff]==0 ){
                pBuf->p[pBuf->n++] = 0;
                iOff++;
              }
            }
            if( (pBuf->n + pPgidx->n)>=pgsz ){
              fts5WriteFlushLeaf(p, &writer);
            }
          }else{
            int bDummy;
            int nPos;
            int nCopy = fts5GetPoslistSize(&pDoclist[iOff], &nPos, &bDummy);
            nCopy += nPos;
            if( (pBuf->n + pPgidx->n + nCopy) <= pgsz ){
              /* The entire poslist will fit on the current leaf. So copy
              ** it in one go. */
              fts5BufferSafeAppendBlob(pBuf, &pDoclist[iOff], nCopy);
            }else{
              /* The entire poslist will not fit on this leaf. So it needs
              ** to be broken into sections. The only qualification being
              ** that each varint must be stored contiguously.  */
              const u8 *pPoslist = &pDoclist[iOff];
              int iPos = 0;
              while( p->rc==SQLITE_OK ){
                int nSpace = pgsz - pBuf->n - pPgidx->n;
                int n = 0;
                if( (nCopy - iPos)<=nSpace ){
                  n = nCopy - iPos;
                }else{
                  n = fts5PoslistPrefix(&pPoslist[iPos], nSpace);
                }
                assert( n>0 );
                fts5BufferSafeAppendBlob(pBuf, &pPoslist[iPos], n);
                iPos += n;
                if( (pBuf->n + pPgidx->n)>=pgsz ){
                  fts5WriteFlushLeaf(p, &writer);
                }
                if( iPos>=nCopy ) break;
              }
            }
            iOff += nCopy;
          }
        }
      }

      /* TODO2: Doclist terminator written here. */
      /* pBuf->p[pBuf->n++] = '\0'; */
      assert( pBuf->n<=pBuf->nSpace );
      sqlite3Fts5HashScanNext(pHash);
    }
    sqlite3Fts5HashClear(pHash);
    fts5WriteFinish(p, &writer, &pgnoLast);

    /* Update the Fts5Structure. It is written back to the database by the
    ** fts5StructureRelease() call below.  */
    if( pStruct->nLevel==0 ){
      fts5StructureAddLevel(&p->rc, &pStruct);
    }
    fts5StructureExtendLevel(&p->rc, pStruct, 0, 1, 0);
    if( p->rc==SQLITE_OK ){
      pSeg = &pStruct->aLevel[0].aSeg[ pStruct->aLevel[0].nSeg++ ];
      pSeg->iSegid = iSegid;
      pSeg->pgnoFirst = 1;
      pSeg->pgnoLast = pgnoLast;
      pStruct->nSegment++;
    }
    fts5StructurePromote(p, 0, pStruct);
  }

  fts5IndexAutomerge(p, &pStruct, pgnoLast);
  fts5IndexCrisismerge(p, &pStruct);
  fts5StructureWrite(p, pStruct);
  fts5StructureRelease(pStruct);
}


/*
** Flush any data stored in the in-memory hash tables to the database.





*/
static void fts5IndexFlush(Fts5Index *p){
  /* Unless it is empty, flush the hash table to disk */
  if( p->nPendingData ){
    assert( p->pHash );
    p->nPendingData = 0;
    fts5FlushOneHash(p);
  }
}

static Fts5Structure *fts5IndexOptimizeStruct(
  Fts5Index *p, 
  Fts5Structure *pStruct
){
  Fts5Structure *pNew = 0;
  int nByte = sizeof(Fts5Structure);
  int nSeg = pStruct->nSegment;
  int i;

  /* Figure out if this structure requires optimization. A structure does
  ** not require optimization if either:
  **
  **  + it consists of fewer than two segments, or 
  **  + all segments are on the same level, or
  **  + all segments except one are currently inputs to a merge operation.
  **
  ** In the first case, return NULL. In the second, increment the ref-count
  ** on *pStruct and return a copy of the pointer to it.
  */
  if( nSeg<2 ) return 0;
  for(i=0; i<pStruct->nLevel; i++){
    int nThis = pStruct->aLevel[i].nSeg;
    if( nThis==nSeg || (nThis==nSeg-1 && pStruct->aLevel[i].nMerge==nThis) ){
      fts5StructureRef(pStruct);
      return pStruct;
    }
    assert( pStruct->aLevel[i].nMerge<=nThis );
  }



  nByte += (pStruct->nLevel+1) * sizeof(Fts5StructureLevel);
  pNew = (Fts5Structure*)sqlite3Fts5MallocZero(&p->rc, nByte);

  if( pNew ){
    Fts5StructureLevel *pLvl;
    nByte = nSeg * sizeof(Fts5StructureSegment);
    pNew->nLevel = pStruct->nLevel+1;
    pNew->nRef = 1;
    pNew->nWriteCounter = pStruct->nWriteCounter;
    pLvl = &pNew->aLevel[pStruct->nLevel];
................................................................................
      pNew = 0;
    }
  }

  return pNew;
}













int sqlite3Fts5IndexOptimize(Fts5Index *p){
  Fts5Structure *pStruct;
  Fts5Structure *pNew = 0;

  assert( p->rc==SQLITE_OK );
  fts5IndexFlush(p);
  pStruct = fts5StructureRead(p);
................................................................................
      }
    }
    fts5StructureRelease(pStruct);
  }
  return fts5IndexReturn(p);
}








static void fts5AppendRowid(
  Fts5Index *p,
  i64 iDelta,
  Fts5Iter *pUnused,
  Fts5Buffer *pBuf
){
  UNUSED_PARAM(pUnused);
  fts5BufferAppendVarint(&p->rc, pBuf, iDelta);
}









static void fts5AppendPoslist(
  Fts5Index *p,
  i64 iDelta,
  Fts5Iter *pMulti,
  Fts5Buffer *pBuf
){
  int nData = pMulti->base.nData;
................................................................................
  if( p->rc==SQLITE_OK && 0==fts5BufferGrow(&p->rc, pBuf, nData+9+9) ){
    fts5BufferSafeAppendVarint(pBuf, iDelta);
    fts5BufferSafeAppendVarint(pBuf, nData*2);
    fts5BufferSafeAppendBlob(pBuf, pMulti->base.pData, nData);
  }
}




static void fts5DoclistIterNext(Fts5DoclistIter *pIter){
  u8 *p = pIter->aPoslist + pIter->nSize + pIter->nPoslist;

  assert( pIter->aPoslist );
  if( p>=pIter->aEof ){
    pIter->aPoslist = 0;
  }else{
................................................................................
      pIter->nSize = 1;
    }

    pIter->aPoslist = p;
  }
}







static void fts5DoclistIterInit(
  Fts5Buffer *pBuf, 
  Fts5DoclistIter *pIter
){
  memset(pIter, 0, sizeof(*pIter));
  pIter->aPoslist = pBuf->p;
  pIter->aEof = &pBuf->p[pBuf->n];
  fts5DoclistIterNext(pIter);
}

#if 0
/*
** Append a doclist to buffer pBuf.
**
** This function assumes that space within the buffer has already been
** allocated.
*/
static void fts5MergeAppendDocid(
  Fts5Buffer *pBuf,               /* Buffer to write to */
  i64 *piLastRowid,               /* IN/OUT: Previous rowid written (if any) */
  i64 iRowid                      /* Rowid to append */
){
  assert( pBuf->n!=0 || (*piLastRowid)==0 );
  fts5BufferSafeAppendVarint(pBuf, iRowid - *piLastRowid);
  *piLastRowid = iRowid;
}
#endif

#define fts5MergeAppendDocid(pBuf, iLastRowid, iRowid) {       \
  assert( (pBuf)->n!=0 || (iLastRowid)==0 );                   \
  fts5BufferSafeAppendVarint((pBuf), (iRowid) - (iLastRowid)); \
  (iLastRowid) = (iRowid);                                     \
}

/*
** Swap the contents of buffer *p1 with that of *p2.
*/
static void fts5BufferSwap(Fts5Buffer *p1, Fts5Buffer *p2){
  Fts5Buffer tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}











static void fts5NextRowid(Fts5Buffer *pBuf, int *piOff, i64 *piRowid){
  int i = *piOff;
  if( i>=pBuf->n ){
    *piOff = -1;
  }else{
    u64 iVal;
    *piOff = i + sqlite3Fts5GetVarint(&pBuf->p[i], &iVal);
................................................................................
      fts5NextRowid(p2, &i2, &iRowid2);
    }
  }

  fts5BufferSwap(&out, p1);
  fts5BufferFree(&out);
}




















/*
** Buffers p1 and p2 contain doclists. This function merges the content
** of the two doclists together and sets buffer p1 to the result before
** returning.
**
** If an error occurs, an error code is left in p->rc. If an error has
................................................................................

    fts5BufferSet(&p->rc, p1, out.n, out.p);
    fts5BufferFree(&tmp);
    fts5BufferFree(&out);
  }
}






static void fts5SetupPrefixIter(
  Fts5Index *p,                   /* Index to read from */
  int bDesc,                      /* True for "ORDER BY rowid DESC" */
  const u8 *pToken,               /* Buffer containing prefix to match */
  int nToken,                     /* Size of buffer pToken in bytes */
  Fts5Colset *pColset,            /* Restrict matches to these columns */
  Fts5Iter **ppIter          /* OUT: New iterator */
){
  Fts5Structure *pStruct;
  Fts5Buffer *aBuf;
  const int nBuf = 32;

  void (*xMerge)(Fts5Index*, Fts5Buffer*, Fts5Buffer*);
  void (*xAppend)(Fts5Index*, i64, Fts5Iter*, Fts5Buffer*);
................................................................................
    xMerge = fts5MergeRowidLists;
    xAppend = fts5AppendRowid;
  }else{
    xMerge = fts5MergePrefixLists;
    xAppend = fts5AppendPoslist;
  }


  aBuf = (Fts5Buffer*)fts5IdxMalloc(p, sizeof(Fts5Buffer)*nBuf);
  pStruct = fts5StructureRead(p);

  if( aBuf && pStruct ){
    const int flags = FTS5INDEX_QUERY_SCAN 
                    | FTS5INDEX_QUERY_SKIPEMPTY 
                    | FTS5INDEX_QUERY_NOOUTPUT;
    int i;
    i64 iLastRowid = 0;
    Fts5Iter *p1 = 0;     /* Iterator used to gather data from index */
    Fts5Data *pData;
................................................................................
    memset(&doclist, 0, sizeof(doclist));
    fts5MultiIterNew(p, pStruct, flags, pColset, pToken, nToken, -1, 0, &p1);
    fts5IterSetOutputCb(&p->rc, p1);
    for( /* no-op */ ;
        fts5MultiIterEof(p, p1)==0;
        fts5MultiIterNext2(p, p1, &bNewTerm)
    ){
      Fts5SegIter *pSeg = &p1->aSeg[ p1->aFirst[1].iFirst ];
      int nTerm = pSeg->term.n;
      const u8 *pTerm = pSeg->term.p;
      p1->xSetOutputs(p1, pSeg);

      assert_nc( memcmp(pToken, pTerm, MIN(nToken, nTerm))<=0 );
      if( bNewTerm ){
        if( nTerm<nToken || memcmp(pToken, pTerm, nToken) ) break;
................................................................................

/*
** Commit data to disk.
*/
int sqlite3Fts5IndexSync(Fts5Index *p, int bCommit){
  assert( p->rc==SQLITE_OK );
  fts5IndexFlush(p);
  if( bCommit ) fts5CloseReader(p);
  return fts5IndexReturn(p);
}

/*
** Discard any data stored in the in-memory hash tables. Do not write it
** to the database. Additionally, assume that the contents of the %_data
** table may have changed on disk. So any in-memory caches of %_data 
** records must be invalidated.
*/
int sqlite3Fts5IndexRollback(Fts5Index *p){
  fts5CloseReader(p);
  fts5IndexDiscardData(p);
  fts5StructureInvalidate(p);

  /* assert( p->rc==SQLITE_OK ); */
  return SQLITE_OK;
}

/*
** The %_data table is completely empty when this function is called. This
** function populates it with the initial structure objects for each index,
** and the initial version of the "averages" record (a zero-byte blob).
*/
int sqlite3Fts5IndexReinit(Fts5Index *p){
  Fts5Structure s;
  fts5StructureInvalidate(p);
  memset(&s, 0, sizeof(Fts5Structure));
  fts5DataWrite(p, FTS5_AVERAGES_ROWID, (const u8*)"", 0);
  fts5StructureWrite(p, &s);
................................................................................
  Fts5Index *p;                   /* New object */

  *pp = p = (Fts5Index*)sqlite3Fts5MallocZero(&rc, sizeof(Fts5Index));
  if( rc==SQLITE_OK ){
    p->pConfig = pConfig;
    p->nWorkUnit = FTS5_WORK_UNIT;
    p->zDataTbl = sqlite3Fts5Mprintf(&rc, "%s_data", pConfig->zName);
    if( p->zDataTbl && bCreate ){

      rc = sqlite3Fts5CreateTable(
          pConfig, "data", "id INTEGER PRIMARY KEY, block BLOB", 0, pzErr
      );

      if( rc==SQLITE_OK ){
        rc = sqlite3Fts5CreateTable(pConfig, "idx", 
            "segid, term, pgno, PRIMARY KEY(segid, term)", 
            1, pzErr
        );
      }
      if( rc==SQLITE_OK ){
        rc = sqlite3Fts5IndexReinit(p);
      }
    }
  }
................................................................................
  assert( (iCol<0)==p->bDelete );

  /* Add the entry to the main terms index. */
  rc = sqlite3Fts5HashWrite(
      p->pHash, p->iWriteRowid, iCol, iPos, FTS5_MAIN_PREFIX, pToken, nToken
  );



  for(i=0; i<pConfig->nPrefix && rc==SQLITE_OK; i++){
    const int nChar = pConfig->aPrefix[i];
    int nByte = sqlite3Fts5IndexCharlenToBytelen(pToken, nToken, nChar);
    if( nByte ){
      rc = sqlite3Fts5HashWrite(p->pHash, 
          p->iWriteRowid, iCol, iPos, (char)(FTS5_MAIN_PREFIX+i+1), pToken,
          nByte
................................................................................
  Fts5Colset *pColset,            /* Match these columns only */
  Fts5IndexIter **ppIter          /* OUT: New iterator object */
){
  Fts5Config *pConfig = p->pConfig;
  Fts5Iter *pRet = 0;
  Fts5Buffer buf = {0, 0, 0};

  /* If the QUERY_SCAN flag is set, all other flags must be clear. */

  assert( (flags & FTS5INDEX_QUERY_SCAN)==0 || flags==FTS5INDEX_QUERY_SCAN );



  if( sqlite3Fts5BufferSize(&p->rc, &buf, nToken+1)==0 ){
    int iIdx = 0;                 /* Index to search */
    memcpy(&buf.p[1], pToken, nToken);

    /* Figure out which index to search and set iIdx accordingly. If this
    ** is a prefix query for which there is no prefix index, set iIdx to
    ** greater than pConfig->nPrefix to indicate that the query will be
    ** satisfied by scanning multiple terms in the main index.
    **
    ** If the QUERY_TEST_NOIDX flag was specified, then this must be a
    ** prefix-query. Instead of using a prefix-index (if one exists), 
    ** evaluate the prefix query using the main FTS index. This is used
    ** for internal sanity checking by the integrity-check in debug 
    ** mode only.  */
#ifdef SQLITE_DEBUG
    if( pConfig->bPrefixIndex==0 || (flags & FTS5INDEX_QUERY_TEST_NOIDX) ){
      assert( flags & FTS5INDEX_QUERY_PREFIX );
      iIdx = 1+pConfig->nPrefix;
    }else
#endif
    if( flags & FTS5INDEX_QUERY_PREFIX ){
      int nChar = fts5IndexCharlen(pToken, nToken);
      for(iIdx=1; iIdx<=pConfig->nPrefix; iIdx++){
        if( pConfig->aPrefix[iIdx-1]==nChar ) break;
      }



    }

    if( iIdx<=pConfig->nPrefix ){
      /* Straight index lookup */
      Fts5Structure *pStruct = fts5StructureRead(p);
      buf.p[0] = (u8)(FTS5_MAIN_PREFIX + iIdx);
      if( pStruct ){
................................................................................
      /* Scan multiple terms in the main index */
      int bDesc = (flags & FTS5INDEX_QUERY_DESC)!=0;
      buf.p[0] = FTS5_MAIN_PREFIX;
      fts5SetupPrefixIter(p, bDesc, buf.p, nToken+1, pColset, &pRet);
      assert( p->rc!=SQLITE_OK || pRet->pColset==0 );
      fts5IterSetOutputCb(&p->rc, pRet);
      if( p->rc==SQLITE_OK ){
        Fts5SegIter *pSeg = &pRet->aSeg[pRet->aFirst[1].iFirst];
        if( pSeg->pLeaf ) pRet->xSetOutputs(pRet, pSeg);
      }
    }

    if( p->rc ){
      sqlite3Fts5IterClose(&pRet->base);
      pRet = 0;
      fts5CloseReader(p);
    }

    *ppIter = &pRet->base;
    sqlite3Fts5BufferFree(&buf);
  }
  return fts5IndexReturn(p);
}

/*
** Return true if the iterator passed as the only argument is at EOF.
*/
/*
** Move to the next matching rowid. 
*/
int sqlite3Fts5IterNext(Fts5IndexIter *pIndexIter){
  Fts5Iter *pIter = (Fts5Iter*)pIndexIter;
  assert( pIter->pIndex->rc==SQLITE_OK );
  fts5MultiIterNext(pIter->pIndex, pIter, 0, 0);
................................................................................
  Fts5Iter *pIter = (Fts5Iter*)pIndexIter;
  Fts5Index *p = pIter->pIndex;

  assert( pIter->pIndex->rc==SQLITE_OK );

  fts5MultiIterNext(p, pIter, 0, 0);
  if( p->rc==SQLITE_OK ){
    Fts5SegIter *pSeg = &pIter->aSeg[ pIter->aFirst[1].iFirst ];
    if( pSeg->pLeaf && pSeg->term.p[0]!=FTS5_MAIN_PREFIX ){
      fts5DataRelease(pSeg->pLeaf);
      pSeg->pLeaf = 0;
      pIter->base.bEof = 1;
    }
  }

................................................................................
  Fts5Iter *pIter = (Fts5Iter*)pIndexIter;
  fts5MultiIterNextFrom(pIter->pIndex, pIter, iMatch);
  return fts5IndexReturn(pIter->pIndex);
}

/*
** Return the current term.



*/
const char *sqlite3Fts5IterTerm(Fts5IndexIter *pIndexIter, int *pn){
  int n;
  const char *z = (const char*)fts5MultiIterTerm((Fts5Iter*)pIndexIter, &n);
  *pn = n-1;
  return &z[1];
}
................................................................................
** Close an iterator opened by an earlier call to sqlite3Fts5IndexQuery().
*/
void sqlite3Fts5IterClose(Fts5IndexIter *pIndexIter){
  if( pIndexIter ){
    Fts5Iter *pIter = (Fts5Iter*)pIndexIter;
    Fts5Index *pIndex = pIter->pIndex;
    fts5MultiIterFree(pIter);
    fts5CloseReader(pIndex);
  }
}

/*
** Read and decode the "averages" record from the database. 
**
** Parameter anSize must point to an array of size nCol, where nCol is
................................................................................

  fts5DataRelease(pData);
  return fts5IndexReturn(p);
}

/*
** Replace the current "averages" record with the contents of the buffer 
** supplied as the second argument.





*/
int sqlite3Fts5IndexSetAverages(Fts5Index *p, const u8 *pData, int nData){
  assert( p->rc==SQLITE_OK );
  fts5DataWrite(p, FTS5_AVERAGES_ROWID, pData, nData);
  return fts5IndexReturn(p);
}

/*
** Return the total number of blocks this module has read from the %_data
** table since it was created.
*/
int sqlite3Fts5IndexReads(Fts5Index *p){
  return p->nRead;
}

/*
** Set the 32-bit cookie value stored at the start of all structure 
** records to the value passed as the second argument.
**
** Return SQLITE_OK if successful, or an SQLite error code if an error
** occurs.
*/
int sqlite3Fts5IndexSetCookie(Fts5Index *p, int iNew){
  int rc;                              /* Return code */
  Fts5Config *pConfig = p->pConfig;    /* Configuration object */
  u8 aCookie[4];                       /* Binary representation of iNew */
  sqlite3_blob *pBlob = 0;

  assert( p->rc==SQLITE_OK );
  sqlite3Fts5Put32(aCookie, iNew);

  rc = sqlite3_blob_open(pConfig->db, pConfig->zDb, p->zDataTbl, 
      "block", FTS5_STRUCTURE_ROWID, 1, &pBlob
  );
  if( rc==SQLITE_OK ){
    sqlite3_blob_write(pBlob, aCookie, 4, 0);
    rc = sqlite3_blob_close(pBlob);
  }

  return rc;
}

int sqlite3Fts5IndexLoadConfig(Fts5Index *p){
  Fts5Structure *pStruct;
  pStruct = fts5StructureRead(p);
  fts5StructureRelease(pStruct);
  return fts5IndexReturn(p);
}




/*************************************************************************
**************************************************************************
** Below this point is the implementation of the integrity-check 
** functionality.
*/
................................................................................
    ** the index is disabled are the same. In both ASC and DESC order. 
    **
    ** This check may only be performed if the hash table is empty. This
    ** is because the hash table only supports a single scan query at
    ** a time, and the multi-iter loop from which this function is called
    ** is already performing such a scan. */
    if( p->nPendingData==0 ){


      if( iIdx>0 && rc==SQLITE_OK ){
        int f = flags|FTS5INDEX_QUERY_TEST_NOIDX;
        ck2 = 0;
        rc = fts5QueryCksum(p, iIdx, zTerm, nTerm, f, &ck2);
        if( rc==SQLITE_OK && ck1!=ck2 ) rc = FTS5_CORRUPT;
      }
      if( iIdx>0 && rc==SQLITE_OK ){
        int f = flags|FTS5INDEX_QUERY_TEST_NOIDX|FTS5INDEX_QUERY_DESC;
        ck2 = 0;
        rc = fts5QueryCksum(p, iIdx, zTerm, nTerm, f, &ck2);
        if( rc==SQLITE_OK && ck1!=ck2 ) rc = FTS5_CORRUPT;
      }

    }

    cksum3 ^= ck1;
    fts5BufferSet(&rc, pPrev, n, (const u8*)z);

    if( rc==SQLITE_OK && cksum3!=expected ){
      rc = FTS5_CORRUPT;
................................................................................
    sqlite3_result_text(pCtx, (const char*)s.p, s.n, SQLITE_TRANSIENT);
  }else{
    sqlite3_result_error_code(pCtx, rc);
  }
  fts5BufferFree(&s);
}

/*
** The implementation of user-defined scalar function fts5_rowid().
*/
static void fts5RowidFunction(
  sqlite3_context *pCtx,          /* Function call context */
  int nArg,                       /* Number of args (always 2) */
  sqlite3_value **apVal           /* Function arguments */
){
  const char *zArg;
  if( nArg==0 ){
    sqlite3_result_error(pCtx, "should be: fts5_rowid(subject, ....)", -1);
  }else{
    zArg = (const char*)sqlite3_value_text(apVal[0]);
    if( 0==sqlite3_stricmp(zArg, "segment") ){
      i64 iRowid;
      int segid, pgno;
      if( nArg!=3 ){
        sqlite3_result_error(pCtx, 
            "should be: fts5_rowid('segment', segid, pgno))", -1
        );
      }else{
        segid = sqlite3_value_int(apVal[1]);
        pgno = sqlite3_value_int(apVal[2]);
        iRowid = FTS5_SEGMENT_ROWID(segid, pgno);
        sqlite3_result_int64(pCtx, iRowid);
      }
    }else{
      sqlite3_result_error(pCtx, 
        "first arg to fts5_rowid() must be 'segment'" , -1
      );
    }
  }
}

/*
** This is called as part of registering the FTS5 module with database
** connection db. It registers several user-defined scalar functions useful
** with FTS5.
**
** If successful, SQLITE_OK is returned. If an error occurs, some other
** SQLite error code is returned instead.
................................................................................
  if( rc==SQLITE_OK ){
    rc = sqlite3_create_function(
        db, "fts5_decode_none", 2, 
        SQLITE_UTF8, (void*)db, fts5DecodeFunction, 0, 0
    );
  }

  if( rc==SQLITE_OK ){
    rc = sqlite3_create_function(
        db, "fts5_rowid", -1, SQLITE_UTF8, 0, fts5RowidFunction, 0, 0
    );
  }
  return rc;
}


int sqlite3Fts5IndexReset(Fts5Index *p){
  assert( p->pStruct==0 || p->iStructVersion!=0 );
  if( fts5IndexDataVersion(p)!=p->iStructVersion ){
    fts5StructureInvalidate(p);
  }
  return fts5IndexReturn(p);
}







|
|








|
|
|
>







 







<



<
<
<
<
<
<
<
<
<
<
<

<
>





|

|







 







|







 







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







 







<







 







>
|




>
>
>
>
>







 







<
<
<
<
<
<
<








|
>
>
>
>
>



<
<







 







>
>
>
>
>
>
>







 







|







 







|







 







>
>
>
>
>
>
>
>







|











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













<
<
<
<
|
<
<







 







|







 







|







 







|







 







|




|







 







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













|







 







<
|







 







<
|
<









|
|







 







|







 







>
>
>
>




>
>







|
|







 







|












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



|



|
|


|
|
|
>
|
|





<







 







|
|


|
<


|
|


|

|
<
<
<
<
<
<
<
>
|
<
<
<

|








|





|
|


<


|
|

>
>
>



|
|

|
|
<





|











<

|







|





|


>
|







>
>
>


|
|
<
>

<





|

|





|





|













<

|
|


|
|



|
|
|








>
>
>
>











|
<


|
|


|
|











|
|












>
>







 







>
>
>
>
>










>
>
>
>
>

>
>
>





|







 







|







 







|







 







|

|





|







 







>
>
>
>
>







 







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







 







|
<




|
>
|
|
|
|

>
>
|
|
|
|
|

|
|
|
|
|
|

|
|

|
|

|
|
|
|

|
|
|
|
|
|
|
|
|

|
|
|

|
|
|
|
|
|
|
|

|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|

|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|

|
|
|
|
|
|
|

|
|
|
|
|
|
|
|
|
|
|
|
|
|
|

|
|
|
|
|
|
>

<
>
>
>
>
>

<
<
<
<
<
<
<
<
<

|
|






|
|





|
|
<










>
>


<







 







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







 







>
>
>
>
>
>
>










>
>
>
>
>
>
>
>







 







|
>
>







 







>
>
>
>
>
>










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









>
>
>
>
>
>
>
>
>
>







 







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







 







>
>
>
>
>






|







 







>



|







 







|







 







|










|


>






|
|







 







|
>
|
|
|
>


|
<







 







>
>







 







|
>

>
>










|
|
<
<
<
<
<
<
<
<
<





>
>
>







 







|







|








<
<
<







 







|







 







>
>
>







 







|







 







|
>
>
>
>
>









|






|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
>
>







 







>
>

<

|



<

|


>







 







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







 







<
<
<
<
<



<
<
<
<
<
<
<
<
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
...
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
...
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
...
262
263
264
265
266
267
268

269
270
271
272
273
274
275
...
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
...
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
...
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
...
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
...
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
...
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
....
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
....
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
....
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
....
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
....
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
3074
3075
3076
3077
3078
3079
3080
3081
3082
3083
3084
3085
3086
3087
....
3452
3453
3454
3455
3456
3457
3458

3459
3460
3461
3462
3463
3464
3465
3466
....
3506
3507
3508
3509
3510
3511
3512

3513

3514
3515
3516
3517
3518
3519
3520
3521
3522
3523
3524
3525
3526
3527
3528
3529
3530
3531
....
3747
3748
3749
3750
3751
3752
3753
3754
3755
3756
3757
3758
3759
3760
3761
....
3770
3771
3772
3773
3774
3775
3776
3777
3778
3779
3780
3781
3782
3783
3784
3785
3786
3787
3788
3789
3790
3791
3792
3793
3794
3795
3796
3797
3798
3799
3800
3801
3802
....
3837
3838
3839
3840
3841
3842
3843
3844
3845
3846
3847
3848
3849
3850
3851
3852
3853
3854
3855
3856
3857
3858
3859
3860
3861
3862
3863
3864
3865
3866
3867
3868
3869
3870



3871
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889
3890
3891
3892

3893
3894
3895
3896
3897
3898
3899
....
3902
3903
3904
3905
3906
3907
3908
3909
3910
3911
3912
3913

3914
3915
3916
3917
3918
3919
3920
3921
3922







3923
3924



3925
3926
3927
3928
3929
3930
3931
3932
3933
3934
3935
3936
3937
3938
3939
3940
3941
3942
3943
3944

3945
3946
3947
3948
3949
3950
3951
3952
3953
3954
3955
3956
3957
3958
3959
3960

3961
3962
3963
3964
3965
3966
3967
3968
3969
3970
3971
3972
3973
3974
3975
3976
3977

3978
3979
3980
3981
3982
3983
3984
3985
3986
3987
3988
3989
3990
3991
3992
3993
3994
3995
3996
3997
3998
3999
4000
4001
4002
4003
4004
4005
4006
4007
4008
4009
4010
4011

4012
4013

4014
4015
4016
4017
4018
4019
4020
4021
4022
4023
4024
4025
4026
4027
4028
4029
4030
4031
4032
4033
4034
4035
4036
4037
4038
4039
4040
4041
4042
4043
4044
4045
4046

4047
4048
4049
4050
4051
4052
4053
4054
4055
4056
4057
4058
4059
4060
4061
4062
4063
4064
4065
4066
4067
4068
4069
4070
4071
4072
4073
4074
4075
4076
4077
4078
4079
4080
4081
4082
4083

4084
4085
4086
4087
4088
4089
4090
4091
4092
4093
4094
4095
4096
4097
4098
4099
4100
4101
4102
4103
4104
4105
4106
4107
4108
4109
4110
4111
4112
4113
4114
4115
4116
4117
4118
4119
4120
4121
4122
4123
4124
4125
....
4170
4171
4172
4173
4174
4175
4176
4177
4178
4179
4180
4181
4182
4183
4184
4185
4186
4187
4188
4189
4190
4191
4192
4193
4194
4195
4196
4197
4198
4199
4200
4201
4202
4203
4204
4205
4206
4207
4208
4209
4210
4211
4212
4213
....
4226
4227
4228
4229
4230
4231
4232
4233
4234
4235
4236
4237
4238
4239
4240
....
4261
4262
4263
4264
4265
4266
4267
4268
4269
4270
4271
4272
4273
4274
4275
....
4286
4287
4288
4289
4290
4291
4292
4293
4294
4295
4296
4297
4298
4299
4300
4301
4302
4303
4304
4305
4306
4307
4308
....
4419
4420
4421
4422
4423
4424
4425
4426
4427
4428
4429
4430
4431
4432
4433
4434
4435
4436
4437
....
4442
4443
4444
4445
4446
4447
4448












4449
4450
4451
4452
4453
4454
4455
....
4462
4463
4464
4465
4466
4467
4468
4469

4470
4471
4472
4473
4474
4475
4476
4477
4478
4479
4480
4481
4482
4483
4484
4485
4486
4487
4488
4489
4490
4491
4492
4493
4494
4495
4496
4497
4498
4499
4500
4501
4502
4503
4504
4505
4506
4507
4508
4509
4510
4511
4512
4513
4514
4515
4516
4517
4518
4519
4520
4521
4522
4523
4524
4525
4526
4527
4528
4529
4530
4531
4532
4533
4534
4535
4536
4537
4538
4539
4540
4541
4542
4543
4544
4545
4546
4547
4548
4549
4550
4551
4552
4553
4554
4555
4556
4557
4558
4559
4560
4561
4562
4563
4564
4565
4566
4567
4568
4569
4570
4571
4572
4573
4574
4575
4576
4577
4578
4579
4580
4581
4582
4583
4584
4585
4586
4587
4588
4589
4590
4591
4592
4593
4594
4595
4596
4597
4598
4599
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
4614
4615
4616
4617
4618
4619
4620
4621
4622
4623
4624
4625
4626
4627

4628
4629
4630
4631
4632
4633









4634
4635
4636
4637
4638
4639
4640
4641
4642
4643
4644
4645
4646
4647
4648
4649
4650
4651

4652
4653
4654
4655
4656
4657
4658
4659
4660
4661
4662
4663
4664
4665

4666
4667
4668
4669
4670
4671
4672
....
4689
4690
4691
4692
4693
4694
4695
4696
4697
4698
4699
4700
4701
4702
4703
4704
4705
4706
4707
4708
4709
4710
4711
4712
4713
4714
....
4757
4758
4759
4760
4761
4762
4763
4764
4765
4766
4767
4768
4769
4770
4771
4772
4773
4774
4775
4776
4777
4778
4779
4780
4781
4782
4783
4784
4785
4786
4787
4788
4789
4790
4791
4792
4793
4794
4795
....
4797
4798
4799
4800
4801
4802
4803
4804
4805
4806
4807
4808
4809
4810
4811
4812
4813
....
4826
4827
4828
4829
4830
4831
4832
4833
4834
4835
4836
4837
4838
4839
4840
4841
4842
4843
4844
4845
4846
4847
4848
























4849
4850
4851
4852
4853
4854
4855
4856
4857
4858
4859
4860
4861
4862
4863
4864
4865
4866
4867
4868
4869
4870
4871
4872
4873
4874
....
4914
4915
4916
4917
4918
4919
4920
4921
4922
4923
4924
4925
4926
4927
4928
4929
4930
4931
4932
4933
4934
4935
4936
4937
4938
4939
4940
4941
4942
4943
4944
4945
4946
....
5055
5056
5057
5058
5059
5060
5061
5062
5063
5064
5065
5066
5067
5068
5069
5070
5071
5072
5073
5074
5075
5076
5077
5078
5079
5080
....
5082
5083
5084
5085
5086
5087
5088
5089
5090
5091
5092
5093
5094
5095
5096
5097
5098
5099
5100
....
5104
5105
5106
5107
5108
5109
5110
5111
5112
5113
5114
5115
5116
5117
5118
....
5188
5189
5190
5191
5192
5193
5194
5195
5196
5197
5198
5199
5200
5201
5202
5203
5204
5205
5206
5207
5208
5209
5210
5211
5212
5213
5214
5215
5216
5217
5218
5219
5220
5221
5222
5223
5224
....
5242
5243
5244
5245
5246
5247
5248
5249
5250
5251
5252
5253
5254
5255
5256
5257

5258
5259
5260
5261
5262
5263
5264
....
5353
5354
5355
5356
5357
5358
5359
5360
5361
5362
5363
5364
5365
5366
5367
5368
....
5384
5385
5386
5387
5388
5389
5390
5391
5392
5393
5394
5395
5396
5397
5398
5399
5400
5401
5402
5403
5404
5405
5406
5407









5408
5409
5410
5411
5412
5413
5414
5415
5416
5417
5418
5419
5420
5421
5422
....
5429
5430
5431
5432
5433
5434
5435
5436
5437
5438
5439
5440
5441
5442
5443
5444
5445
5446
5447
5448
5449
5450
5451
5452



5453
5454
5455
5456
5457
5458
5459
....
5467
5468
5469
5470
5471
5472
5473
5474
5475
5476
5477
5478
5479
5480
5481
....
5491
5492
5493
5494
5495
5496
5497
5498
5499
5500
5501
5502
5503
5504
5505
5506
5507
....
5510
5511
5512
5513
5514
5515
5516
5517
5518
5519
5520
5521
5522
5523
5524
....
5542
5543
5544
5545
5546
5547
5548
5549
5550
5551
5552
5553
5554
5555
5556
5557
5558
5559
5560
5561
5562
5563
5564
5565
5566
5567
5568
5569
5570
5571
5572
5573
5574
5575
5576
5577
5578
5579
5580
5581
5582
5583
5584
5585
5586
5587
5588
5589
5590
5591
5592
5593
5594
5595
5596
5597
5598
5599
5600
5601
5602
5603
5604
5605
5606
5607
5608
5609
5610
5611
....
5752
5753
5754
5755
5756
5757
5758
5759
5760
5761

5762
5763
5764
5765
5766

5767
5768
5769
5770
5771
5772
5773
5774
5775
5776
5777
5778
....
6482
6483
6484
6485
6486
6487
6488


































6489
6490
6491
6492
6493
6494
6495
....
6502
6503
6504
6505
6506
6507
6508





6509
6510
6511








**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
******************************************************************************
**
** Low level access to the FTS index stored in the database file. The 
** routines in this file file implement all read and write access to the
** %_data and %_idx tables. Other parts of the system access this 
** functionality via the interface defined in fts5Int.h.
*/


#include "fts5Int.h"

/*
** Overview:
**
** The %_data table contains the FTS index for an FTS5 virtual table.
** All entries, for terms and prefixes, are stored in a single data
** structure. The format is similar to FTS3/4, but differs in the 
** following ways:
**
**   * all segment b-tree leaf data is stored in fixed size page records 
**     (e.g. 1000 bytes). A single doclist may span multiple pages. Care is 
**     taken to ensure it is possible to iterate in either direction through 
**     the entries in a doclist, or to seek to a specific entry within a 
**     doclist, without loading it into memory.
**
................................................................................
**   * large doclists that span many pages have associated "doclist index"
**     records that contain a copy of the first rowid on each page spanned by
**     the doclist. This is used to speed up seek operations, and merges of
**     large doclists with very small doclists.
**
**   * extra fields in the "structure record" record the state of ongoing
**     incremental merge operations.

*/













/*

** Contents of %_data table:
**
** The %_data table managed by this module,
**
**     CREATE TABLE %_data(id INTEGER PRIMARY KEY, block BLOB);
**
** , contains the following 4 types of records. See the comments surrounding
** the FTS5_*_ROWID macros below for a description of how %_data rowids are 
** assigned to each of them.
**
** 1. Structure Records:
**
**   The set of segments that make up an index - the index structure - are
**   recorded in a single record within the %_data table. The record consists
**   of a single 32-bit configuration cookie value followed by a list of 
**   SQLite varints. If the FTS table features more than one index (because
................................................................................
**
**       + the first term on each page is stored in the same way as the
**         very first term of the segment:
**
**             varint : size of first term
**             blob:    first term data
**
** 4. Segment doclist indexes:
**
**   Doclist indexes are themselves b-trees, however they usually consist of
**   a single leaf record only. The format of each doclist index leaf page 
**   is:
**
**     * Flags byte. Bits are:
**         0x01: Clear if leaf is also the root page, otherwise set.
................................................................................
**
**     * Copy of first rowid on page indicated by previous field. As a varint.
**
**     * A list of delta-encoded varints - the first rowid on each subsequent
**       child page. 
**
*/


#define FTS5_OPT_WORK_UNIT  1000  /* Number of leaf pages per optimize step */
#define FTS5_WORK_UNIT      64    /* Number of leaf pages in unit of work */
#define FTS5_MIN_DLIDX_SIZE 4     /* Add dlidx if this many empty pages */

/* All entries for regular terms in the FTS index are prefixed with '0'.
** Entries for the first prefix index are prefixed with '1'. And so on, 
** up to ('0'+31).  */
#define FTS5_MAIN_PREFIX '0'

#if FTS5_MAX_PREFIX_INDEXES > 31
# error "FTS5_MAX_PREFIX_INDEXES is too large"
#endif


/*
** Rowids for the averages and structure records in the %_data table.
*/
#define FTS5_AVERAGES_ROWID     1    /* Rowid used for the averages record */
#define FTS5_STRUCTURE_ROWID   10    /* The structure record */

................................................................................
#define FTS5_DATA_PADDING 20

typedef struct Fts5Data Fts5Data;
typedef struct Fts5DlidxIter Fts5DlidxIter;
typedef struct Fts5DlidxLvl Fts5DlidxLvl;
typedef struct Fts5DlidxWriter Fts5DlidxWriter;
typedef struct Fts5Iter Fts5Iter;

typedef struct Fts5SegIter Fts5SegIter;
typedef struct Fts5DoclistIter Fts5DoclistIter;
typedef struct Fts5SegWriter Fts5SegWriter;
typedef struct Fts5Structure Fts5Structure;
typedef struct Fts5StructureLevel Fts5StructureLevel;
typedef struct Fts5StructureSegment Fts5StructureSegment;

................................................................................
  sqlite3_stmt *pWriter;          /* "INSERT ... %_data VALUES(?,?)" */
  sqlite3_stmt *pDeleter;         /* "DELETE FROM %_data ... id>=? AND id<=?" */
  sqlite3_stmt *pIdxWriter;       /* "INSERT ... %_idx VALUES(?,?,?,?)" */
  sqlite3_stmt *pIdxDeleter;      /* "DELETE FROM %_idx WHERE segid=? */
  sqlite3_stmt *pIdxSelect;
  int nRead;                      /* Total number of blocks read */

  /* In-memory cache of the 'structure' record */
  sqlite3_stmt *pDataVersion;     /* PRAGMA <db>.data_version */
  i64 iStructVersion;             /* data_version when pStruct read */
  Fts5Structure *pStruct;         /* Current db structure (or NULL) */
};

/*
** An iterator of this sort is used to iterate through a doclist stored
** entirely in memory. See functions fts5DoclistIterInit() and
** fts5DoclistIterNext() for details. 
*/
struct Fts5DoclistIter {
  u8 *aEof;                       /* Pointer to 1 byte past end of doclist */

  /* Output variables. aPoslist==0 at EOF */
  i64 iRowid;
  u8 *aPoslist;
  int nPoslist;
................................................................................
  int nLevel;                     /* Number of levels in this index */
  Fts5StructureLevel aLevel[1];   /* Array of nLevel level objects */
};

/*
** An object of type Fts5SegWriter is used to write to segments.
*/







struct Fts5DlidxWriter {
  int pgno;                       /* Page number for this page */
  int bPrevValid;                 /* True if iPrev is valid */
  i64 iPrev;                      /* Previous rowid value written to page */
  Fts5Buffer buf;                 /* Buffer containing page data */
};
struct Fts5SegWriter {
  int iSegid;                     /* Segid to write to */
  int pgno;                       /* Page number for current leaf page */
  int iPrevPgidx;                 /* Previous value written into pgidx */
  Fts5Buffer buf;                 /* Buffer of current leaf page data */
  Fts5Buffer pgidx;               /* Buffer of current leaf page-index */
  Fts5Buffer term;                /* Buffer containing previous term on leaf */

  i64 iPrevRowid;                 /* Previous rowid written to current leaf */
  u8 bFirstRowidInDoclist;        /* True if next rowid is first in doclist */
  u8 bFirstRowidInPage;           /* True if next rowid is first in page */


  int nLeafWritten;               /* Number of leaf pages written */
  int nEmpty;                     /* Number of contiguous term-less nodes */

  int nDlidx;                     /* Allocated size of aDlidx[] array */
  Fts5DlidxWriter *aDlidx;        /* Array of Fts5DlidxWriter objects */

  /* Values to insert into the %_idx table */
................................................................................
  u8 bSkipEmpty;                  /* True to skip deleted entries */

  i64 iSwitchRowid;               /* Firstest rowid of other than aFirst[1] */
  Fts5CResult *aFirst;            /* Current merge state (see above) */
  Fts5SegIter aSeg[1];            /* Array of segment iterators */
};


/*
** Given pointer "x" to an Fts5Iter structure, return a pointer the the
** current first component segment iterator.
*/
#define fts5IterSegment(x) (&(x)->aSeg [ (x)->aFirst[1].iFirst ])


/*
** An instance of the following type is used to iterate through the contents
** of a doclist-index record.
**
** pData:
**   Record containing the doclist-index data.
................................................................................
  fts5GetVarint32(&pLeaf->p[pLeaf->szLeaf], ret);
  return ret;
}

/*
** Close the read-only blob handle, if it is open.
*/
void sqlite3Fts5IndexCloseReader(Fts5Index *p){
  if( p->pReader ){
    sqlite3_blob *pReader = p->pReader;
    p->pReader = 0;
    sqlite3_blob_close(pReader);
  }
}

................................................................................
      ** is required.  */
      sqlite3_blob *pBlob = p->pReader;
      p->pReader = 0;
      rc = sqlite3_blob_reopen(pBlob, iRowid);
      assert( p->pReader==0 );
      p->pReader = pBlob;
      if( rc!=SQLITE_OK ){
        sqlite3Fts5IndexCloseReader(p);
      }
      if( rc==SQLITE_ABORT ) rc = SQLITE_OK;
    }

    /* If the blob handle is not open at this point, open it and seek 
    ** to the requested entry.  */
    if( p->pReader==0 && rc==SQLITE_OK ){
................................................................................
      pRet = 0;
    }
  }

  return pRet;
}

/*
** Execute "PRAGMA db.data_version" and return the integer value that 
** it returns.
**
** This function returns 0 if Fts5Index.rc is set to other than SQLITE_OK
** when it is called. If an error occurs while executing the PRAGMA,
** Fts5Index.rc is set to an SQLite error code before returning.
*/
static i64 fts5IndexDataVersion(Fts5Index *p){
  i64 iVersion = 0;

  if( p->rc==SQLITE_OK ){
    if( p->pDataVersion==0 ){
      p->rc = fts5IndexPrepareStmt(p, &p->pDataVersion, 
          sqlite3_mprintf("PRAGMA %Q.data_version", p->pConfig->zDb)
      );
      if( p->rc ) return 0;
    }

    if( SQLITE_ROW==sqlite3_step(p->pDataVersion) ){
      iVersion = sqlite3_column_int64(p->pDataVersion, 0);
    }
    p->rc = sqlite3_reset(p->pDataVersion);
  }

  return iVersion;
}

/*
** If there is currently no cache of the index structure in memory, load
** one from the database.
*/
static void fts5StructureCache(Fts5Index *p){
  if( p->pStruct==0 ){
    p->iStructVersion = fts5IndexDataVersion(p);
    if( p->rc==SQLITE_OK ){
      p->pStruct = fts5StructureReadUncached(p);
    }
  }
}

/*
** Read, deserialize and return the structure record.
**
** The Fts5Structure.aLevel[] and each Fts5StructureLevel.aSeg[] array
** are over-allocated as described for function fts5StructureDecode() 
** above.
**
** If an error occurs, NULL is returned and an error code left in the
** Fts5Index handle. If an error has already occurred when this function
** is called, it is a no-op.
*/
static Fts5Structure *fts5StructureRead(Fts5Index *p){




  fts5StructureCache(p);



#if 0
  else{
    Fts5Structure *pTest = fts5StructureReadUncached(p);
    if( pTest ){
      int i, j;
      assert_nc( p->pStruct->nSegment==pTest->nSegment );
................................................................................

/*
** Return true if the iterator passed as the second argument currently
** points to a delete marker. A delete marker is an entry with a 0 byte
** position-list.
*/
static int fts5MultiIterIsEmpty(Fts5Index *p, Fts5Iter *pIter){
  Fts5SegIter *pSeg = fts5IterSegment(pIter);
  return (p->rc==SQLITE_OK && pSeg->pLeaf && pSeg->nPos==0);
}

/*
** Advance iterator pIter to the next entry.
**
** This version of fts5SegIterNext() is only used by reverse iterators.
................................................................................
** This function is a no-op unless SQLITE_DEBUG is defined when this module
** is compiled. In that case, this function is essentially an assert() 
** statement used to verify that the contents of the pIter->aFirst[] array
** are correct.
*/
static void fts5AssertMultiIterSetup(Fts5Index *p, Fts5Iter *pIter){
  if( p->rc==SQLITE_OK ){
    Fts5SegIter *pFirst = fts5IterSegment(pIter);
    int i;

    assert( (pFirst->pLeaf==0)==pIter->base.bEof );

    /* Check that pIter->iSwitchRowid is set correctly. */
    for(i=0; i<pIter->nSeg; i++){
      Fts5SegIter *p1 = &pIter->aSeg[i];
................................................................................
  return 0;
}

/*
** Set the pIter->bEof variable based on the state of the sub-iterators.
*/
static void fts5MultiIterSetEof(Fts5Iter *pIter){
  Fts5SegIter *pSeg = fts5IterSegment(pIter);
  pIter->base.bEof = pSeg->pLeaf==0;
  pIter->iSwitchRowid = pSeg->iRowid;
}

/*
** Move the iterator to the next entry. 
**
................................................................................
    }

    if( pSeg->pLeaf==0 || bNewTerm 
     || fts5MultiIterAdvanceRowid(pIter, iFirst, &pSeg)
    ){
      fts5MultiIterAdvanced(p, pIter, iFirst, 1);
      fts5MultiIterSetEof(pIter);
      pSeg = fts5IterSegment(pIter);
      if( pSeg->pLeaf==0 ) return;
    }

    fts5AssertMultiIterSetup(p, pIter);
    assert( pSeg==fts5IterSegment(pIter) && pSeg->pLeaf );
    if( pIter->bSkipEmpty==0 || pSeg->nPos ){
      pIter->xSetOutputs(pIter, pSeg);
      return;
    }
    bUseFrom = 0;
  }
}
................................................................................
          }
        }
      }
    }while( i<nChunk );
  }
}

/*
** This function is used to extract the position list associated with
** the entry that segment iterator pSeg currently points to. If the
** entire position list resides on a single leaf page, then this 
** function invokes the xChunk callback exactly once. Or, if the position
** list spans multiple leaves, xChunk is invoked once for each leaf.
**
** The first argument passed to the xChunk callback is a copy of the Fts5Index
** pointer passed as the first argument to this function. Similarly, the 
** second argument passed to xChunk is a copy of the third parameter passed
** to this function. The third and fourth arguments passed to xChunk are
** a pointer to a blob containing part of the position list and the size
** in bytes there of.
*/
static void fts5ChunkIterate(
  Fts5Index *p,                   /* Index object */
  Fts5SegIter *pSeg,              /* Poslist of this iterator */
  void *pCtx,                     /* Context pointer for xChunk callback */
  void (*xChunk)(Fts5Index*, void*, const u8*, int)
){
  int nRem = pSeg->nPos;          /* Number of bytes still to come */
  Fts5Data *pData = 0;
  u8 *pChunk = &pSeg->pLeaf->p[pSeg->iLeafOffset];
  int nChunk = MIN(nRem, pSeg->pLeaf->szLeaf - pSeg->iLeafOffset);
  int pgno = pSeg->iLeafPgno;
  int pgnoSave = 0;

  /* This function does not work with detail=none databases. */
  assert( p->pConfig->eDetail!=FTS5_DETAIL_NONE );

  if( (pSeg->flags & FTS5_SEGITER_REVERSE)==0 ){
    pgnoSave = pgno+1;
  }

  while( 1 ){
................................................................................
    }
    fts5MultiIterSetEof(pNew);
    fts5AssertMultiIterSetup(p, pNew);

    if( pNew->bSkipEmpty && fts5MultiIterIsEmpty(p, pNew) ){
      fts5MultiIterNext(p, pNew, 0, 0);
    }else if( pNew->base.bEof==0 ){

      pNew->xSetOutputs(pNew, fts5IterSegment(pNew));
    }

  }else{
    fts5MultiIterFree(pNew);
    *ppOut = 0;
  }
}
................................................................................
}

/*
** Return true if the iterator is at EOF or if an error has occurred. 
** False otherwise.
*/
static int fts5MultiIterEof(Fts5Index *p, Fts5Iter *pIter){

  assert( p->rc || (fts5IterSegment(pIter)->pLeaf==0)==pIter->base.bEof );

  return (p->rc || pIter->base.bEof);
}

/*
** Return the rowid of the entry that the iterator currently points
** to. If the iterator points to EOF when this function is called the
** results are undefined.
*/
static i64 fts5MultiIterRowid(Fts5Iter *pIter){
  assert( fts5IterSegment(pIter)->pLeaf );
  return fts5IterSegment(pIter)->iRowid;
}

/*
** Move the iterator to the next entry at or following iMatch.
*/
static void fts5MultiIterNextFrom(
  Fts5Index *p, 
................................................................................
static void fts5WriteBtreeTerm(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5SegWriter *pWriter,         /* Writer object */
  int nTerm, const u8 *pTerm      /* First term on new page */
){
  fts5WriteFlushBtree(p, pWriter);
  fts5BufferSet(&p->rc, &pWriter->btterm, nTerm, pTerm);
  pWriter->iBtPage = pWriter->pgno;
}

/*
** This function is called when flushing a leaf page that contains no
** terms at all to disk.
*/
static void fts5WriteBtreeNoTerm(
................................................................................
    sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx->buf, 0);
  }

  /* Increment the "number of sequential leaves without a term" counter. */
  pWriter->nEmpty++;
}

/*
** Buffer pBuf contains a doclist-index page. Return the first rowid 
** value on the page.
*/
static i64 fts5DlidxExtractFirstRowid(Fts5Buffer *pBuf){
  i64 iRowid;
  int iOff;

  /* Skip past the flags byte and the page number of the left-most child
  ** page to the first rowid.  */
  iOff = 1 + fts5GetVarint(&pBuf->p[1], (u64*)&iRowid);
  fts5GetVarint(&pBuf->p[iOff], (u64*)&iRowid);
  return iRowid;
}

/*
** Rowid iRowid has just been appended to the current leaf page. It is the
** first on the page. This function appends an appropriate entry to the
** current doclist-index.
*/
static void fts5WriteDlidxAppend(
  Fts5Index *p, 
  Fts5SegWriter *pWriter, 
  i64 iRowid
){
  int i;
................................................................................
    }else{
      bDone = 1;
    }

    if( pDlidx->bPrevValid ){
      iVal = iRowid - pDlidx->iPrev;
    }else{
      i64 iPgno = (i==0 ? pWriter->pgno : pDlidx[-1].pgno);
      assert( pDlidx->buf.n==0 );
      sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx->buf, !bDone);
      sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx->buf, iPgno);
      iVal = iRowid;
    }

    sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx->buf, iVal);
    pDlidx->bPrevValid = 1;
    pDlidx->iPrev = iRowid;
  }
}

/*
** Flush the writer's current leaf page to disk. Initialize various
** fields ready for the next leaf page.
*/
static void fts5WriteFlushLeaf(Fts5Index *p, Fts5SegWriter *pWriter){
  i64 iRowid;

  /* Set the szLeaf header field. */
  assert( 0==fts5GetU16(&pWriter->buf.p[2]) );
  fts5PutU16(&pWriter->buf.p[2], (u16)pWriter->buf.n);

  if( pWriter->pgidx.n==0 ){
    /* No term was written to this page. */
    assert( pWriter->pgidx.n==0 );



    fts5WriteBtreeNoTerm(p, pWriter);
  }else{
    /* Append the pgidx to the page buffer. Set the szLeaf header field. */
    fts5BufferSafeAppendBlob(&pWriter->buf, pWriter->pgidx.p, pWriter->pgidx.n);
  }

  /* Write the page out to disk */
  iRowid = FTS5_SEGMENT_ROWID(pWriter->iSegid, pWriter->pgno);
  fts5DataWrite(p, iRowid, pWriter->buf.p, pWriter->buf.n);

  /* Initialize the next page. */
  fts5BufferZero(&pWriter->buf);
  fts5BufferZero(&pWriter->pgidx);
  memset(pWriter->buf.p, 0, 4);
  pWriter->buf.n = 4;
  pWriter->iPrevPgidx = 0;
  pWriter->pgno++;

  /* Increase the leaves written counter */
  pWriter->nLeafWritten++;

  /* The new leaf holds no terms or rowids */

  pWriter->bFirstRowidInPage = 1;
}

/*
** Append term pTerm/nTerm to the segment being written by the writer passed
** as the second argument.
**
................................................................................
*/
static void fts5WriteAppendTerm(
  Fts5Index *p, 
  Fts5SegWriter *pWriter,
  int nTerm, const u8 *pTerm 
){
  int nPrefix;                    /* Bytes of prefix compression for term */
  int iOff;
  Fts5Buffer *pPgidx = &pWriter->pgidx;

  assert( p->rc==SQLITE_OK );
  assert( pWriter->buf.n>=4 );


  /* If the current leaf page is full, flush it to disk. */
  if( (pWriter->buf.n + pPgidx->n + nTerm + 2)>=p->pConfig->pgsz ){
    if( pWriter->buf.n>4 ){
      fts5WriteFlushLeaf(p, pWriter);
    }
    fts5BufferGrow(&p->rc, &pWriter->buf, nTerm+FTS5_DATA_PADDING);
  }








  iOff = pWriter->buf.n;
  if( pPgidx->n==0 ){



    nPrefix = 0;
    if( pWriter->pgno!=1 ){
      /* This is the first term on a leaf that is not the leftmost leaf in
      ** the segment b-tree. In this case it is necessary to add a term to
      ** the b-tree hierarchy that is (a) larger than the largest term 
      ** already written to the segment and (b) smaller than or equal to
      ** this term. In other words, a prefix of (pTerm/nTerm) that is one
      ** byte longer than the longest prefix (pTerm/nTerm) shares with the
      ** previous term. 
      **
      ** Usually, the previous term is available in pWriter->term. The exception
      ** is if this is the first term written in an incremental-merge step.
      ** In this case the previous term is not available, so just write a
      ** copy of (pTerm/nTerm) into the parent node. This is slightly
      ** inefficient, but still correct.  */
      int n = nTerm;
      if( pWriter->term.n ){
        n = 1 + fts5PrefixCompress(pWriter->term.n, pWriter->term.p, pTerm);
      }
      fts5WriteBtreeTerm(p, pWriter, n, pTerm);

    }
  }else{
    nPrefix = fts5PrefixCompress(pWriter->term.n, pWriter->term.p, pTerm);
    fts5BufferAppendVarint(&p->rc, &pWriter->buf, nPrefix);
  }

  fts5BufferSafeAppendVarint(pPgidx, iOff - pWriter->iPrevPgidx);
  pWriter->iPrevPgidx = iOff;

  /* Append the number of bytes of new data, then the term data itself
  ** to the page. */
  fts5BufferAppendVarint(&p->rc, &pWriter->buf, nTerm - nPrefix);
  fts5BufferAppendBlob(&p->rc, &pWriter->buf, nTerm - nPrefix, &pTerm[nPrefix]);

  /* Update the Fts5SegWriter.term field. */
  fts5BufferSet(&p->rc, &pWriter->term, nTerm, pTerm);


  pWriter->bFirstRowidInPage = 0;
  pWriter->bFirstRowidInDoclist = 1;

  assert( p->rc || (pWriter->nDlidx>0 && pWriter->aDlidx[0].buf.n==0) );
  pWriter->aDlidx[0].pgno = pWriter->pgno;
}

/*
** Append a rowid and position-list size field to the writers output. 
*/
static void fts5WriteAppendRowid(
  Fts5Index *p, 
  Fts5SegWriter *pWriter,
  i64 iRowid
){
  if( p->rc==SQLITE_OK ){


    if( (pWriter->buf.n + pWriter->pgidx.n)>=p->pConfig->pgsz ){
      fts5WriteFlushLeaf(p, pWriter);
    }

    /* If this is to be the first rowid written to the page, set the 
    ** rowid-pointer in the page-header. Also append a value to the dlidx
    ** buffer, in case a doclist-index is required.  */
    if( pWriter->bFirstRowidInPage ){
      fts5PutU16(pWriter->buf.p, (u16)pWriter->buf.n);
      fts5WriteDlidxAppend(p, pWriter, iRowid);
    }

    /* Write the rowid. */
    if( pWriter->bFirstRowidInDoclist || pWriter->bFirstRowidInPage ){
      fts5BufferSafeAppendVarint(&pWriter->buf, iRowid);
    }else{
      assert( p->rc || iRowid>pWriter->iPrevRowid );
      assert( pWriter->buf.n+9 <= pWriter->buf.nSpace );
      fts5BufferSafeAppendVarint(&pWriter->buf, iRowid - pWriter->iPrevRowid);
    }
    pWriter->iPrevRowid = iRowid;
    pWriter->bFirstRowidInDoclist = 0;
    pWriter->bFirstRowidInPage = 0;
  }
}

/*
** Append position list data to the writers output.
*/
static void fts5WriteAppendPoslistData(
  Fts5Index *p, 
  Fts5SegWriter *pWriter,         /* Writer object to write to the output of */
  const u8 *aData,                /* Buffer containing data to append */

  int nData                       /* Size of buffer aData[] in bytes */
){

  const u8 *a = aData;
  int n = nData;
  
  assert( p->pConfig->pgsz>0 );
  while( p->rc==SQLITE_OK 
     && (pWriter->buf.n + pWriter->pgidx.n + n)>=p->pConfig->pgsz 
  ){
    int nReq = p->pConfig->pgsz - pWriter->buf.n - pWriter->pgidx.n;
    int nCopy = 0;
    while( nCopy<nReq ){
      i64 dummy;
      nCopy += fts5GetVarint(&a[nCopy], (u64*)&dummy);
    }
    fts5BufferAppendBlob(&p->rc, &pWriter->buf, nCopy, a);
    a += nCopy;
    n -= nCopy;
    fts5WriteFlushLeaf(p, pWriter);
  }
  if( n>0 ){
    fts5BufferAppendBlob(&p->rc, &pWriter->buf, n, a);
  }
}

/*
** Flush any data cached by the writer object to the database. Free any
** allocations associated with the writer.
*/
static void fts5WriteFinish(
  Fts5Index *p, 
  Fts5SegWriter *pWriter,         /* Writer object */
  int *pnLeaf                     /* OUT: Number of leaf pages in b-tree */
){
  int i;

  if( p->rc==SQLITE_OK ){
    assert( pWriter->pgno>=1 );
    if( pWriter->buf.n>4 ){
      fts5WriteFlushLeaf(p, pWriter);
    }
    *pnLeaf = pWriter->pgno-1;
    if( pWriter->pgno>1 ){
      fts5WriteFlushBtree(p, pWriter);
    }
  }
  fts5BufferFree(&pWriter->term);
  fts5BufferFree(&pWriter->buf);
  fts5BufferFree(&pWriter->pgidx);
  fts5BufferFree(&pWriter->btterm);

  for(i=0; i<pWriter->nDlidx; i++){
    sqlite3Fts5BufferFree(&pWriter->aDlidx[i].buf);
  }
  sqlite3_free(pWriter->aDlidx);
}

/*
** Initialize the Fts5SegWriter object indicated by the second argument
** to write to the segment with seg-id iSegid.
*/
static void fts5WriteInit(
  Fts5Index *p, 
  Fts5SegWriter *pWriter, 
  int iSegid
){
  const int nBuffer = p->pConfig->pgsz + FTS5_DATA_PADDING;

  memset(pWriter, 0, sizeof(Fts5SegWriter));
  pWriter->iSegid = iSegid;

  fts5WriteDlidxGrow(p, pWriter, 1);
  pWriter->pgno = 1;

  pWriter->iBtPage = 1;

  assert( pWriter->buf.n==0 );
  assert( pWriter->pgidx.n==0 );

  /* Grow the two buffers to pgsz + padding bytes in size. */
  sqlite3Fts5BufferSize(&p->rc, &pWriter->pgidx, nBuffer);
  sqlite3Fts5BufferSize(&p->rc, &pWriter->buf, nBuffer);

  if( p->pIdxWriter==0 ){
    Fts5Config *pConfig = p->pConfig;
    fts5IndexPrepareStmt(p, &p->pIdxWriter, sqlite3_mprintf(
          "INSERT INTO '%q'.'%q_idx'(segid,term,pgno) VALUES(?,?,?)", 
          pConfig->zDb, pConfig->zName
    ));
  }

  if( p->rc==SQLITE_OK ){
    /* Initialize the 4-byte leaf-page header to 0x00. */
    memset(pWriter->buf.p, 0, 4);
    pWriter->buf.n = 4;

    /* Bind the current output segment id to the index-writer. This is an
    ** optimization over binding the same value over and over as rows are
    ** inserted into %_idx by the current writer.  */
    sqlite3_bind_int(p->pIdxWriter, 1, pWriter->iSegid);
  }
}

/*
** Iterator pIter was used to iterate through the input segments of on an
** incremental merge operation. This function is called if the incremental
** merge step has finished but the input has not been completely exhausted.
** It removes (DELETEs) any input segment leaves that are no longer required
** from the database.
*/
static void fts5TrimSegments(Fts5Index *p, Fts5Iter *pIter){
  int i;
  Fts5Buffer buf;
  memset(&buf, 0, sizeof(Fts5Buffer));
  for(i=0; i<pIter->nSeg; i++){
    Fts5SegIter *pSeg = &pIter->aSeg[i];
................................................................................
        fts5DataWrite(p, iLeafRowid, buf.p, buf.n);
      }
    }
  }
  fts5BufferFree(&buf);
}

/*
** This function is used as an fts5ChunkIterate() callback when merging
** levels. The chunk passed to this function is appended to the output
** segment.
*/
static void fts5MergeChunkCallback(
  Fts5Index *p, 
  void *pCtx, 
  const u8 *pChunk, int nChunk
){
  Fts5SegWriter *pWriter = (Fts5SegWriter*)pCtx;
  fts5WriteAppendPoslistData(p, pWriter, pChunk, nChunk);
}

/*
** This function reads data from level iLvl of structure (*ppStruct) and
** writes it into a segment on level (iLvl+1). If (*ppStruct) indicates
** that there is already such a merge underway, this function continues
** it. Otherwise, a new merge is started. (*ppStruct) is updated with the
** results of the merge before this function returns.
**
** When this function is called in/out parameter *pnRem contains the maximum
** number of leaf pages to write to the database. *pnRem is decremented by
** the actual number of pages written before this function returns.
*/
static void fts5IndexMergeLevel(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5Structure **ppStruct,       /* IN/OUT: Stucture of index */
  int iLvl,                       /* Level to read input from */
  int *pnRem                      /* IN/OUT: Write this many output leaves */
){
  Fts5Structure *pStruct = *ppStruct;
  Fts5StructureLevel *pLvl = &pStruct->aLevel[iLvl];
  Fts5StructureLevel *pLvlOut;
  Fts5Iter *pIter = 0;       /* Iterator to read input data */
  int nRem = pnRem ? *pnRem : 0;  /* Output leaf pages left to write */
  int nInput;                     /* Number of input segments */
................................................................................
  if( pLvl->nMerge ){
    pLvlOut = &pStruct->aLevel[iLvl+1];
    assert( pLvlOut->nSeg>0 );
    nInput = pLvl->nMerge;
    pSeg = &pLvlOut->aSeg[pLvlOut->nSeg-1];

    fts5WriteInit(p, &writer, pSeg->iSegid);
    writer.pgno = pSeg->pgnoLast+1;
    writer.iBtPage = 0;
  }else{
    int iSegid = fts5AllocateSegid(p, pStruct);

    /* Extend the Fts5Structure object as required to ensure the output
    ** segment exists. */
    if( iLvl==pStruct->nLevel-1 ){
................................................................................
  bOldest = (pLvlOut->nSeg==1 && pStruct->nLevel==iLvl+2);

  assert( iLvl>=0 );
  for(fts5MultiIterNew(p, pStruct, flags, 0, 0, 0, iLvl, nInput, &pIter);
      fts5MultiIterEof(p, pIter)==0;
      fts5MultiIterNext(p, pIter, 0, 0)
  ){
    Fts5SegIter *pSegIter = fts5IterSegment(pIter);
    int nPos;                     /* position-list size field value */
    int nTerm;
    const u8 *pTerm;

    /* Check for key annihilation. */
    if( pSegIter->nPos==0 && (bOldest || pSegIter->bDel==0) ) continue;

................................................................................

    /* Append the rowid to the output */
    /* WRITEPOSLISTSIZE */
    fts5WriteAppendRowid(p, &writer, fts5MultiIterRowid(pIter));

    if( eDetail==FTS5_DETAIL_NONE ){
      if( pSegIter->bDel ){
        fts5BufferAppendVarint(&p->rc, &writer.buf, 0);
        if( pSegIter->nPos>0 ){
          fts5BufferAppendVarint(&p->rc, &writer.buf, 0);
        }
      }
    }else{
      /* Append the position-list data to the output */
      nPos = pSegIter->nPos*2 + pSegIter->bDel;
      fts5BufferAppendVarint(&p->rc, &writer.buf, nPos);
      fts5ChunkIterate(p, pSegIter, (void*)&writer, fts5MergeChunkCallback);
    }
  }

  /* Flush the last leaf page to disk. Set the output segment b-tree height
  ** and last leaf page number at the same time.  */
  fts5WriteFinish(p, &writer, &pSeg->pgnoLast);
................................................................................
    pStruct->nWriteCounter += nLeaf;
    nRem = (int)(p->nWorkUnit * nWork * pStruct->nLevel);

    fts5IndexMerge(p, ppStruct, nRem, p->pConfig->nAutomerge);
  }
}

/*
** This function is called when a new level 0 segment has just been written
** to the database. If any crisis-merge operations are required as a result,
** they are performed here.
*/
static void fts5IndexCrisismerge(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5Structure **ppStruct        /* IN/OUT: Current structure of index */
){
  const int nCrisis = p->pConfig->nCrisisMerge;
  Fts5Structure *pStruct = *ppStruct;
  int iLvl = 0;
................................................................................
    assert( p->rc!=SQLITE_OK || pStruct->nLevel>(iLvl+1) );
    fts5StructurePromote(p, iLvl+1, pStruct);
    iLvl++;
  }
  *ppStruct = pStruct;
}













/*
** Buffer aBuf[] contains a list of varints, all small enough to fit
** in a 32-bit integer. Return the size of the largest prefix of this 
** list nMax bytes or less in size.
*/
static int fts5PoslistPrefix(const u8 *aBuf, int nMax){
  int ret;
................................................................................
      ret += i;
    }
  }
  return ret;
}

/*
** Flush any data stored in the in-memory hash tables to the database.

**
** If an error occurs, set the Fts5Index.rc error code. If an error has 
** already occurred, this function is a no-op.
*/
static void fts5IndexFlush(Fts5Index *p){
  if( p->nPendingData ){
    Fts5Hash *pHash = p->pHash;
    Fts5Structure *pStruct;
    int iSegid;
    int pgnoLast = 0;                 /* Last leaf page number in segment */

    p->nPendingData = 0;

    /* Obtain a reference to the index structure and allocate a new segment-id
    ** for the new level-0 segment.  */
    pStruct = fts5StructureRead(p);
    iSegid = fts5AllocateSegid(p, pStruct);
    fts5StructureInvalidate(p);

    if( iSegid ){
      const int pgsz = p->pConfig->pgsz;
      int eDetail = p->pConfig->eDetail;
      Fts5StructureSegment *pSeg;   /* New segment within pStruct */
      Fts5Buffer *pBuf;             /* Buffer in which to assemble leaf page */
      Fts5Buffer *pPgidx;           /* Buffer in which to assemble pgidx */

      Fts5SegWriter writer;
      fts5WriteInit(p, &writer, iSegid);

      pBuf = &writer.buf;
      pPgidx = &writer.pgidx;

      /* fts5WriteInit() should have initialized the buffers to (most likely)
      ** the maximum space required. */
      assert( p->rc || pBuf->nSpace>=(pgsz + FTS5_DATA_PADDING) );
      assert( p->rc || pPgidx->nSpace>=(pgsz + FTS5_DATA_PADDING) );

      /* Begin scanning through hash table entries. This loop runs once for each
      ** term/doclist currently stored within the hash table. */
      if( p->rc==SQLITE_OK ){
        p->rc = sqlite3Fts5HashScanInit(pHash, 0, 0);
      }
      while( p->rc==SQLITE_OK && 0==sqlite3Fts5HashScanEof(pHash) ){
        const char *zTerm;          /* Buffer containing term */
        const u8 *pDoclist;         /* Pointer to doclist for this term */
        int nDoclist;               /* Size of doclist in bytes */

        /* Write the term for this entry to disk. */
        sqlite3Fts5HashScanEntry(pHash, &zTerm, &pDoclist, &nDoclist);
        fts5WriteAppendTerm(p, &writer, (int)strlen(zTerm), (const u8*)zTerm);

        assert( writer.bFirstRowidInPage==0 );
        if( pgsz>=(pBuf->n + pPgidx->n + nDoclist + 1) ){
          /* The entire doclist will fit on the current leaf. */
          fts5BufferSafeAppendBlob(pBuf, pDoclist, nDoclist);
        }else{
          i64 iRowid = 0;
          i64 iDelta = 0;
          int iOff = 0;

          /* The entire doclist will not fit on this leaf. The following 
          ** loop iterates through the poslists that make up the current 
          ** doclist.  */
          while( p->rc==SQLITE_OK && iOff<nDoclist ){
            iOff += fts5GetVarint(&pDoclist[iOff], (u64*)&iDelta);
            iRowid += iDelta;
            
            if( writer.bFirstRowidInPage ){
              fts5PutU16(&pBuf->p[0], (u16)pBuf->n);   /* first rowid on page */
              pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], iRowid);
              writer.bFirstRowidInPage = 0;
              fts5WriteDlidxAppend(p, &writer, iRowid);
            }else{
              pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], iDelta);
            }
            assert( pBuf->n<=pBuf->nSpace );

            if( eDetail==FTS5_DETAIL_NONE ){
              if( iOff<nDoclist && pDoclist[iOff]==0 ){
                pBuf->p[pBuf->n++] = 0;
                iOff++;
                if( iOff<nDoclist && pDoclist[iOff]==0 ){
                  pBuf->p[pBuf->n++] = 0;
                  iOff++;
                }
              }
              if( (pBuf->n + pPgidx->n)>=pgsz ){
                fts5WriteFlushLeaf(p, &writer);
              }
            }else{
              int bDummy;
              int nPos;
              int nCopy = fts5GetPoslistSize(&pDoclist[iOff], &nPos, &bDummy);
              nCopy += nPos;
              if( (pBuf->n + pPgidx->n + nCopy) <= pgsz ){
                /* The entire poslist will fit on the current leaf. So copy
                ** it in one go. */
                fts5BufferSafeAppendBlob(pBuf, &pDoclist[iOff], nCopy);
              }else{
                /* The entire poslist will not fit on this leaf. So it needs
                ** to be broken into sections. The only qualification being
                ** that each varint must be stored contiguously.  */
                const u8 *pPoslist = &pDoclist[iOff];
                int iPos = 0;
                while( p->rc==SQLITE_OK ){
                  int nSpace = pgsz - pBuf->n - pPgidx->n;
                  int n = 0;
                  if( (nCopy - iPos)<=nSpace ){
                    n = nCopy - iPos;
                  }else{
                    n = fts5PoslistPrefix(&pPoslist[iPos], nSpace);
                  }
                  assert( n>0 );
                  fts5BufferSafeAppendBlob(pBuf, &pPoslist[iPos], n);
                  iPos += n;
                  if( (pBuf->n + pPgidx->n)>=pgsz ){
                    fts5WriteFlushLeaf(p, &writer);
                  }
                  if( iPos>=nCopy ) break;
                }
              }
              iOff += nCopy;
            }
          }
        }

        /* TODO2: Doclist terminator written here. */
        /* pBuf->p[pBuf->n++] = '\0'; */
        assert( pBuf->n<=pBuf->nSpace );
        sqlite3Fts5HashScanNext(pHash);
      }
      sqlite3Fts5HashClear(pHash);
      fts5WriteFinish(p, &writer, &pgnoLast);

      /* Update the Fts5Structure. It is written back to the database by the
      ** fts5StructureRelease() call below.  */
      if( pStruct->nLevel==0 ){
        fts5StructureAddLevel(&p->rc, &pStruct);
      }
      fts5StructureExtendLevel(&p->rc, pStruct, 0, 1, 0);
      if( p->rc==SQLITE_OK ){
        pSeg = &pStruct->aLevel[0].aSeg[ pStruct->aLevel[0].nSeg++ ];
        pSeg->iSegid = iSegid;
        pSeg->pgnoFirst = 1;
        pSeg->pgnoLast = pgnoLast;
        pStruct->nSegment++;
      }
      fts5StructurePromote(p, 0, pStruct);
    }

    fts5IndexAutomerge(p, &pStruct, pgnoLast);
    fts5IndexCrisismerge(p, &pStruct);
    fts5StructureWrite(p, pStruct);
    fts5StructureRelease(pStruct);
  }
}

/*

** If argument pStruct contains fewer than two segments, NULL is returned.
**
** Otherwise, this function returns a structure reference containing all the
** same segments as argument pStruct, but arranged within levels so that
** running the merge sub-routines merges all content into a single segment.
*/









static Fts5Structure *fts5IndexOptimizeStruct(
  Fts5Index *p,                   /* Index object */
  Fts5Structure *pStruct          /* Structure to optimize */
){
  Fts5Structure *pNew = 0;
  int nByte = sizeof(Fts5Structure);
  int nSeg = pStruct->nSegment;
  int i;

  /* First figure out if this structure requires optimization. A structure 
  ** does not require optimization if either:
  **
  **  + it consists of fewer than two segments, or 
  **  + all segments are on the same level, or
  **  + all segments except one are currently inputs to a merge operation.
  **
  ** In the first case, return NULL. In the second and third, increment the
  ** ref-count on *pStruct and return a copy of the pointer to it.  */

  if( nSeg<2 ) return 0;
  for(i=0; i<pStruct->nLevel; i++){
    int nThis = pStruct->aLevel[i].nSeg;
    if( nThis==nSeg || (nThis==nSeg-1 && pStruct->aLevel[i].nMerge==nThis) ){
      fts5StructureRef(pStruct);
      return pStruct;
    }
    assert( pStruct->aLevel[i].nMerge<=nThis );
  }

  /* Allocate a new structure. Copy all segments from pStruct to level nMax+1
  ** of the new structure, where nMax is the largest level in pStruct.  */
  nByte += (pStruct->nLevel+1) * sizeof(Fts5StructureLevel);
  pNew = (Fts5Structure*)sqlite3Fts5MallocZero(&p->rc, nByte);

  if( pNew ){
    Fts5StructureLevel *pLvl;
    nByte = nSeg * sizeof(Fts5StructureSegment);
    pNew->nLevel = pStruct->nLevel+1;
    pNew->nRef = 1;
    pNew->nWriteCounter = pStruct->nWriteCounter;
    pLvl = &pNew->aLevel[pStruct->nLevel];
................................................................................
      pNew = 0;
    }
  }

  return pNew;
}

/*
** Return from an Fts5Index API function that may have set the error code.
*/
static int fts5IndexReturn(Fts5Index *p){
  int rc = p->rc;
  p->rc = SQLITE_OK;
  return rc;
}

/*
** The implementation of the special "VALUES('optimize')" command.
*/
int sqlite3Fts5IndexOptimize(Fts5Index *p){
  Fts5Structure *pStruct;
  Fts5Structure *pNew = 0;

  assert( p->rc==SQLITE_OK );
  fts5IndexFlush(p);
  pStruct = fts5StructureRead(p);
................................................................................
      }
    }
    fts5StructureRelease(pStruct);
  }
  return fts5IndexReturn(p);
}

/*
** Append varint iDelta to buffer pBuf.
**
** This function is a no-op if Fts5Index.rc is set to other than SQLITE_OK
** when it is called. If an error occurs, Fts5Index.rc is set to an SQLite
** error code before returning.
*/
static void fts5AppendRowid(
  Fts5Index *p,
  i64 iDelta,
  Fts5Iter *pUnused,
  Fts5Buffer *pBuf
){
  UNUSED_PARAM(pUnused);
  fts5BufferAppendVarint(&p->rc, pBuf, iDelta);
}

/*
** Append varint iDelta to buffer pBuf. Then append a copy of the poslist
** currently pointed to by iterator pMulti.
**
** This function is a no-op if Fts5Index.rc is set to other than SQLITE_OK
** when it is called. If an error occurs, Fts5Index.rc is set to an SQLite
** error code before returning.
*/
static void fts5AppendPoslist(
  Fts5Index *p,
  i64 iDelta,
  Fts5Iter *pMulti,
  Fts5Buffer *pBuf
){
  int nData = pMulti->base.nData;
................................................................................
  if( p->rc==SQLITE_OK && 0==fts5BufferGrow(&p->rc, pBuf, nData+9+9) ){
    fts5BufferSafeAppendVarint(pBuf, iDelta);
    fts5BufferSafeAppendVarint(pBuf, nData*2);
    fts5BufferSafeAppendBlob(pBuf, pMulti->base.pData, nData);
  }
}

/*
** Advance iterator pIter to the next rowid in its doclist.
*/
static void fts5DoclistIterNext(Fts5DoclistIter *pIter){
  u8 *p = pIter->aPoslist + pIter->nSize + pIter->nPoslist;

  assert( pIter->aPoslist );
  if( p>=pIter->aEof ){
    pIter->aPoslist = 0;
  }else{
................................................................................
      pIter->nSize = 1;
    }

    pIter->aPoslist = p;
  }
}

/*
** Buffer pBuf contains a doclist. Set up the structure pointed to by 
** pIter to iterate through it. The iterator points to the first rowid
** in the doclist (or EOF if the doclist is empty) when this function
** returns.
*/
static void fts5DoclistIterInit(
  Fts5Buffer *pBuf, 
  Fts5DoclistIter *pIter
){
  memset(pIter, 0, sizeof(*pIter));
  pIter->aPoslist = pBuf->p;
  pIter->aEof = &pBuf->p[pBuf->n];
  fts5DoclistIterNext(pIter);
}

























/*
** Swap the contents of buffer *p1 with that of *p2.
*/
static void fts5BufferSwap(Fts5Buffer *p1, Fts5Buffer *p2){
  Fts5Buffer tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

/*
** Buffer pBuf contains a delta-encoded list of rowids (the sort stored by
** detail=none tables). 
**
** When this function is called, *piOff must be set to the byte offset of a
** varint within this list, and *piRowid to the value of the previous
** rowid in the list. If there are no more rowids in the list, *piOff is
** set to -1 before returning. Otherwise, *piRowid is set to the next
** rowid in the list and *piOff to the offset of the rowid following it.
*/
static void fts5NextRowid(Fts5Buffer *pBuf, int *piOff, i64 *piRowid){
  int i = *piOff;
  if( i>=pBuf->n ){
    *piOff = -1;
  }else{
    u64 iVal;
    *piOff = i + sqlite3Fts5GetVarint(&pBuf->p[i], &iVal);
................................................................................
      fts5NextRowid(p2, &i2, &iRowid2);
    }
  }

  fts5BufferSwap(&out, p1);
  fts5BufferFree(&out);
}

/*
** This macro is used by fts5MergePrefixLists(). The arguments passed should 
** be of the following types:
**
**   Fts5Buffer *pBuf,            // Buffer to write to
**   i64 iLastRowid,              // IN/OUT: Previous rowid written (if any)
**   i64 iRowid                   // Rowid to append
**
** This function appends a single rowid to the doclist stored in pBuf. The
** value of the rowid appended is iRowid. IN/OUT parameter iLastRowid
** should be set to the value of the previous rowid stored in the doclist
** when this macro is invoked. It is set to a copy of iRowid by this macro.
*/
#define fts5MergeAppendDocid(pBuf, iLastRowid, iRowid) {       \
  assert( (pBuf)->n!=0 || (iLastRowid)==0 );                   \
  fts5BufferSafeAppendVarint((pBuf), (iRowid) - (iLastRowid)); \
  (iLastRowid) = (iRowid);                                     \
}

/*
** Buffers p1 and p2 contain doclists. This function merges the content
** of the two doclists together and sets buffer p1 to the result before
** returning.
**
** If an error occurs, an error code is left in p->rc. If an error has
................................................................................

    fts5BufferSet(&p->rc, p1, out.n, out.p);
    fts5BufferFree(&tmp);
    fts5BufferFree(&out);
  }
}

/*
** This function is used to prepare an iterator for a prefix query for
** which there is no prefix index. It assembles a doclist in memory
** and then sets up an Fts5Iter object to iterate through it.
*/
static void fts5SetupPrefixIter(
  Fts5Index *p,                   /* Index to read from */
  int bDesc,                      /* True for "ORDER BY rowid DESC" */
  const u8 *pToken,               /* Buffer containing prefix to match */
  int nToken,                     /* Size of buffer pToken in bytes */
  Fts5Colset *pColset,            /* Restrict matches to these columns */
  Fts5Iter **ppIter               /* OUT: New iterator */
){
  Fts5Structure *pStruct;
  Fts5Buffer *aBuf;
  const int nBuf = 32;

  void (*xMerge)(Fts5Index*, Fts5Buffer*, Fts5Buffer*);
  void (*xAppend)(Fts5Index*, i64, Fts5Iter*, Fts5Buffer*);
................................................................................
    xMerge = fts5MergeRowidLists;
    xAppend = fts5AppendRowid;
  }else{
    xMerge = fts5MergePrefixLists;
    xAppend = fts5AppendPoslist;
  }

  assert( p->pStruct );
  aBuf = (Fts5Buffer*)fts5IdxMalloc(p, sizeof(Fts5Buffer)*nBuf);
  pStruct = fts5StructureRead(p);

  if( aBuf ){
    const int flags = FTS5INDEX_QUERY_SCAN 
                    | FTS5INDEX_QUERY_SKIPEMPTY 
                    | FTS5INDEX_QUERY_NOOUTPUT;
    int i;
    i64 iLastRowid = 0;
    Fts5Iter *p1 = 0;     /* Iterator used to gather data from index */
    Fts5Data *pData;
................................................................................
    memset(&doclist, 0, sizeof(doclist));
    fts5MultiIterNew(p, pStruct, flags, pColset, pToken, nToken, -1, 0, &p1);
    fts5IterSetOutputCb(&p->rc, p1);
    for( /* no-op */ ;
        fts5MultiIterEof(p, p1)==0;
        fts5MultiIterNext2(p, p1, &bNewTerm)
    ){
      Fts5SegIter *pSeg = fts5IterSegment(p1);
      int nTerm = pSeg->term.n;
      const u8 *pTerm = pSeg->term.p;
      p1->xSetOutputs(p1, pSeg);

      assert_nc( memcmp(pToken, pTerm, MIN(nToken, nTerm))<=0 );
      if( bNewTerm ){
        if( nTerm<nToken || memcmp(pToken, pTerm, nToken) ) break;
................................................................................

/*
** Commit data to disk.
*/
int sqlite3Fts5IndexSync(Fts5Index *p, int bCommit){
  assert( p->rc==SQLITE_OK );
  fts5IndexFlush(p);
  if( bCommit ) sqlite3Fts5IndexCloseReader(p);
  return fts5IndexReturn(p);
}

/*
** Discard any data stored in the in-memory hash tables. Do not write it
** to the database. Additionally, assume that the contents of the %_data
** table may have changed on disk. So any in-memory caches of %_data 
** records must be invalidated.
*/
int sqlite3Fts5IndexRollback(Fts5Index *p){
  sqlite3Fts5IndexCloseReader(p);
  fts5IndexDiscardData(p);
  fts5StructureInvalidate(p);
  p->pConfig->iCookie = -1;
  /* assert( p->rc==SQLITE_OK ); */
  return SQLITE_OK;
}

/*
** The %_data table is completely empty when this function is called. This
** function populates it with the initial structure object and the initial
** version of the "averages" record (a zero-byte blob).
*/
int sqlite3Fts5IndexReinit(Fts5Index *p){
  Fts5Structure s;
  fts5StructureInvalidate(p);
  memset(&s, 0, sizeof(Fts5Structure));
  fts5DataWrite(p, FTS5_AVERAGES_ROWID, (const u8*)"", 0);
  fts5StructureWrite(p, &s);
................................................................................
  Fts5Index *p;                   /* New object */

  *pp = p = (Fts5Index*)sqlite3Fts5MallocZero(&rc, sizeof(Fts5Index));
  if( rc==SQLITE_OK ){
    p->pConfig = pConfig;
    p->nWorkUnit = FTS5_WORK_UNIT;
    p->zDataTbl = sqlite3Fts5Mprintf(&rc, "%s_data", pConfig->zName);
    if( bCreate ){
      if( rc==SQLITE_OK ){
        rc = sqlite3Fts5CreateTable(
            pConfig, "data", "id INTEGER PRIMARY KEY, block BLOB", 0, pzErr
        );
      }
      if( rc==SQLITE_OK ){
        rc = sqlite3Fts5CreateTable(pConfig, "idx", 
            "segid, term, pgno, PRIMARY KEY(segid, term)", 1, pzErr

        );
      }
      if( rc==SQLITE_OK ){
        rc = sqlite3Fts5IndexReinit(p);
      }
    }
  }
................................................................................
  assert( (iCol<0)==p->bDelete );

  /* Add the entry to the main terms index. */
  rc = sqlite3Fts5HashWrite(
      p->pHash, p->iWriteRowid, iCol, iPos, FTS5_MAIN_PREFIX, pToken, nToken
  );

  /* Add an entry for each of the prefix indexes that the token is large
  ** enough for (e.g. for which nChar>=nPrefix). */
  for(i=0; i<pConfig->nPrefix && rc==SQLITE_OK; i++){
    const int nChar = pConfig->aPrefix[i];
    int nByte = sqlite3Fts5IndexCharlenToBytelen(pToken, nToken, nChar);
    if( nByte ){
      rc = sqlite3Fts5HashWrite(p->pHash, 
          p->iWriteRowid, iCol, iPos, (char)(FTS5_MAIN_PREFIX+i+1), pToken,
          nByte
................................................................................
  Fts5Colset *pColset,            /* Match these columns only */
  Fts5IndexIter **ppIter          /* OUT: New iterator object */
){
  Fts5Config *pConfig = p->pConfig;
  Fts5Iter *pRet = 0;
  Fts5Buffer buf = {0, 0, 0};

  /* If the QUERY_SCAN flag is set, all other flags must be clear. This
  ** flag is used by the fts5vocab module only. */
  assert( (flags & FTS5INDEX_QUERY_SCAN)==0 || flags==FTS5INDEX_QUERY_SCAN );
  assert( p->rc==SQLITE_OK );
  assert( p->pStruct!=0 || (flags & FTS5INDEX_QUERY_PREFIX)==0 );

  if( sqlite3Fts5BufferSize(&p->rc, &buf, nToken+1)==0 ){
    int iIdx = 0;                 /* Index to search */
    memcpy(&buf.p[1], pToken, nToken);

    /* Figure out which index to search and set iIdx accordingly. If this
    ** is a prefix query for which there is no prefix index, set iIdx to
    ** greater than pConfig->nPrefix to indicate that the query will be
    ** satisfied by scanning multiple terms in the main index.
    **
    ** If the Fts5Config.bPrefixIndex debugging flag is set, do not use
    ** a prefix index even if a suitable one does exist.  */









    if( flags & FTS5INDEX_QUERY_PREFIX ){
      int nChar = fts5IndexCharlen(pToken, nToken);
      for(iIdx=1; iIdx<=pConfig->nPrefix; iIdx++){
        if( pConfig->aPrefix[iIdx-1]==nChar ) break;
      }
#ifdef SQLITE_DEBUG
      if( pConfig->bPrefixIndex==0 ) iIdx = 1+pConfig->nPrefix;
#endif
    }

    if( iIdx<=pConfig->nPrefix ){
      /* Straight index lookup */
      Fts5Structure *pStruct = fts5StructureRead(p);
      buf.p[0] = (u8)(FTS5_MAIN_PREFIX + iIdx);
      if( pStruct ){
................................................................................
      /* Scan multiple terms in the main index */
      int bDesc = (flags & FTS5INDEX_QUERY_DESC)!=0;
      buf.p[0] = FTS5_MAIN_PREFIX;
      fts5SetupPrefixIter(p, bDesc, buf.p, nToken+1, pColset, &pRet);
      assert( p->rc!=SQLITE_OK || pRet->pColset==0 );
      fts5IterSetOutputCb(&p->rc, pRet);
      if( p->rc==SQLITE_OK ){
        Fts5SegIter *pSeg = fts5IterSegment(pRet);
        if( pSeg->pLeaf ) pRet->xSetOutputs(pRet, pSeg);
      }
    }

    if( p->rc ){
      sqlite3Fts5IterClose(&pRet->base);
      pRet = 0;
      sqlite3Fts5IndexCloseReader(p);
    }

    *ppIter = &pRet->base;
    sqlite3Fts5BufferFree(&buf);
  }
  return fts5IndexReturn(p);
}




/*
** Move to the next matching rowid. 
*/
int sqlite3Fts5IterNext(Fts5IndexIter *pIndexIter){
  Fts5Iter *pIter = (Fts5Iter*)pIndexIter;
  assert( pIter->pIndex->rc==SQLITE_OK );
  fts5MultiIterNext(pIter->pIndex, pIter, 0, 0);
................................................................................
  Fts5Iter *pIter = (Fts5Iter*)pIndexIter;
  Fts5Index *p = pIter->pIndex;

  assert( pIter->pIndex->rc==SQLITE_OK );

  fts5MultiIterNext(p, pIter, 0, 0);
  if( p->rc==SQLITE_OK ){
    Fts5SegIter *pSeg = fts5IterSegment(pIter);
    if( pSeg->pLeaf && pSeg->term.p[0]!=FTS5_MAIN_PREFIX ){
      fts5DataRelease(pSeg->pLeaf);
      pSeg->pLeaf = 0;
      pIter->base.bEof = 1;
    }
  }

................................................................................
  Fts5Iter *pIter = (Fts5Iter*)pIndexIter;
  fts5MultiIterNextFrom(pIter->pIndex, pIter, iMatch);
  return fts5IndexReturn(pIter->pIndex);
}

/*
** Return the current term.
**
** This function is only called as part of the fts5vocab module - not as
** part of normal full-text query processing.
*/
const char *sqlite3Fts5IterTerm(Fts5IndexIter *pIndexIter, int *pn){
  int n;
  const char *z = (const char*)fts5MultiIterTerm((Fts5Iter*)pIndexIter, &n);
  *pn = n-1;
  return &z[1];
}
................................................................................
** Close an iterator opened by an earlier call to sqlite3Fts5IndexQuery().
*/
void sqlite3Fts5IterClose(Fts5IndexIter *pIndexIter){
  if( pIndexIter ){
    Fts5Iter *pIter = (Fts5Iter*)pIndexIter;
    Fts5Index *pIndex = pIter->pIndex;
    fts5MultiIterFree(pIter);
    sqlite3Fts5IndexCloseReader(pIndex);
  }
}

/*
** Read and decode the "averages" record from the database. 
**
** Parameter anSize must point to an array of size nCol, where nCol is
................................................................................

  fts5DataRelease(pData);
  return fts5IndexReturn(p);
}

/*
** Replace the current "averages" record with the contents of the buffer 
** supplied as the second argument. 
**
** The averages record consists of N+1 varints, where N is the number of
** columns in the fts5 table. The first varint is the total number of
** rows in the FTS table. The second varint is the total number of tokens 
** in the first column of the table, and so on.
*/
int sqlite3Fts5IndexSetAverages(Fts5Index *p, const u8 *pData, int nData){
  assert( p->rc==SQLITE_OK );
  fts5DataWrite(p, FTS5_AVERAGES_ROWID, pData, nData);
  return fts5IndexReturn(p);
}

/*
** Return the total number of blocks this module has read from the %_data
** table (since it was created by sqlite3Fts5IndexOpen).
*/
int sqlite3Fts5IndexReads(Fts5Index *p){
  return p->nRead;
}

/*
** Increment the value of the configuration cookie stored as the first 
** 32-bits of the structure record in the database. This is called after
** modifying the contents of the %_config table.
*/
int sqlite3Fts5IndexIncrCookie(Fts5Index *p){
  Fts5Structure *pStruct;
  pStruct = fts5StructureRead(p);
  p->pConfig->iCookie++;
  fts5StructureWrite(p, pStruct);
  fts5StructureRelease(pStruct);
  return fts5IndexReturn(p);
}

/*
** Ensure the contents of the %_config table have been loaded into memory.
*/
int sqlite3Fts5IndexLoadConfig(Fts5Index *p){
  fts5StructureCache(p);
  return fts5IndexReturn(p);
}

/*
** This is called when a new read or write transaction may be being opened.
** It ensures that the in-memory cache of the structure record is valid.
*/
int sqlite3Fts5IndexNewTrans(Fts5Index *p){
  assert( p->pStruct==0 || p->iStructVersion!=0 );
  assert( p->rc==SQLITE_OK );
  if( p->pConfig->iCookie<0 || fts5IndexDataVersion(p)!=p->iStructVersion ){
    fts5StructureInvalidate(p);
  }
  return fts5IndexReturn(p);
}



/*************************************************************************
**************************************************************************
** Below this point is the implementation of the integrity-check 
** functionality.
*/
................................................................................
    ** the index is disabled are the same. In both ASC and DESC order. 
    **
    ** This check may only be performed if the hash table is empty. This
    ** is because the hash table only supports a single scan query at
    ** a time, and the multi-iter loop from which this function is called
    ** is already performing such a scan. */
    if( p->nPendingData==0 ){
      int bSaved = p->pConfig->bPrefixIndex;
      p->pConfig->bPrefixIndex = 1;
      if( iIdx>0 && rc==SQLITE_OK ){

        ck2 = 0;
        rc = fts5QueryCksum(p, iIdx, zTerm, nTerm, flags, &ck2);
        if( rc==SQLITE_OK && ck1!=ck2 ) rc = FTS5_CORRUPT;
      }
      if( iIdx>0 && rc==SQLITE_OK ){

        ck2 = 0;
        rc = fts5QueryCksum(p, iIdx, zTerm, nTerm, flags, &ck2);
        if( rc==SQLITE_OK && ck1!=ck2 ) rc = FTS5_CORRUPT;
      }
      p->pConfig->bPrefixIndex = bSaved;
    }

    cksum3 ^= ck1;
    fts5BufferSet(&rc, pPrev, n, (const u8*)z);

    if( rc==SQLITE_OK && cksum3!=expected ){
      rc = FTS5_CORRUPT;
................................................................................
    sqlite3_result_text(pCtx, (const char*)s.p, s.n, SQLITE_TRANSIENT);
  }else{
    sqlite3_result_error_code(pCtx, rc);
  }
  fts5BufferFree(&s);
}



































/*
** This is called as part of registering the FTS5 module with database
** connection db. It registers several user-defined scalar functions useful
** with FTS5.
**
** If successful, SQLITE_OK is returned. If an error occurs, some other
** SQLite error code is returned instead.
................................................................................
  if( rc==SQLITE_OK ){
    rc = sqlite3_create_function(
        db, "fts5_decode_none", 2, 
        SQLITE_UTF8, (void*)db, fts5DecodeFunction, 0, 0
    );
  }






  return rc;
}









Changes to ext/fts5/fts5_main.c.

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
...
706
707
708
709
710
711
712

713
714
715
716
717
718
719
....
1585
1586
1587
1588
1589
1590
1591
1592

1593






1594
1595
1596
1597
1598
1599
1600
1601
}

static int fts5NewTransaction(Fts5Table *pTab){
  Fts5Cursor *pCsr;
  for(pCsr=pTab->pGlobal->pCsr; pCsr; pCsr=pCsr->pNext){
    if( pCsr->base.pVtab==(sqlite3_vtab*)pTab ) return SQLITE_OK;
  }
  return sqlite3Fts5StorageReset(pTab->pStorage);
}

/*
** Implementation of xOpen method.
*/
static int fts5OpenMethod(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCsr){
  Fts5Table *pTab = (Fts5Table*)pVTab;
  Fts5Config *pConfig = pTab->pConfig;
  Fts5Cursor *pCsr = 0;           /* New cursor object */
  int nByte;                      /* Bytes of space to allocate */
  int rc;                         /* Return code */

  rc = fts5NewTransaction(pTab);



  if( rc==SQLITE_OK ){
    nByte = sizeof(Fts5Cursor) + pConfig->nCol * sizeof(int);
    pCsr = (Fts5Cursor*)sqlite3_malloc(nByte);
    if( pCsr ){
      Fts5Global *pGlobal = pTab->pGlobal;
      memset(pCsr, 0, nByte);
      pCsr->aColumnSize = (int*)&pCsr[1];
................................................................................
      pCsr->pNext = pGlobal->pCsr;
      pGlobal->pCsr = pCsr;
      pCsr->iCsrId = ++pGlobal->iNextId;
    }else{
      rc = SQLITE_NOMEM;
    }
  }



  *ppCsr = (sqlite3_vtab_cursor*)pCsr;
  return rc;
}

static int fts5StmtType(Fts5Cursor *pCsr){
  if( pCsr->ePlan==FTS5_PLAN_SCAN ){
    return (pCsr->bDesc) ? FTS5_STMT_SCAN_DESC : FTS5_STMT_SCAN_ASC;
................................................................................

    fts5FreeCursorComponents(pCsr);
    /* Remove the cursor from the Fts5Global.pCsr list */
    for(pp=&pTab->pGlobal->pCsr; (*pp)!=pCsr; pp=&(*pp)->pNext);
    *pp = pCsr->pNext;

    sqlite3_free(pCsr);

  }
  return SQLITE_OK;
}

static int fts5SorterNext(Fts5Cursor *pCsr){
  Fts5Sorter *pSorter = pCsr->pSorter;
  int rc;
................................................................................
  return rc;
}

/*
** Implementation of xBegin() method. 
*/
static int fts5BeginMethod(sqlite3_vtab *pVtab){
  fts5CheckTransactionState((Fts5Table*)pVtab, FTS5_BEGIN, 0);

  fts5NewTransaction((Fts5Table*)pVtab);






  return SQLITE_OK;
}

/*
** Implementation of xCommit() method. This is a no-op. The contents of
** the pending-terms hash-table have already been flushed into the database
** by fts5SyncMethod().
*/







|













>
>
>







 







>
>
>







 







>







 







|
>
|
>
>
>
>
>
>
|







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
...
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
....
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
}

static int fts5NewTransaction(Fts5Table *pTab){
  Fts5Cursor *pCsr;
  for(pCsr=pTab->pGlobal->pCsr; pCsr; pCsr=pCsr->pNext){
    if( pCsr->base.pVtab==(sqlite3_vtab*)pTab ) return SQLITE_OK;
  }
  return sqlite3Fts5IndexNewTrans(pTab->pIndex);
}

/*
** Implementation of xOpen method.
*/
static int fts5OpenMethod(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCsr){
  Fts5Table *pTab = (Fts5Table*)pVTab;
  Fts5Config *pConfig = pTab->pConfig;
  Fts5Cursor *pCsr = 0;           /* New cursor object */
  int nByte;                      /* Bytes of space to allocate */
  int rc;                         /* Return code */

  rc = fts5NewTransaction(pTab);
  if( rc==SQLITE_OK ){
    rc = sqlite3Fts5IndexLoadConfig(pTab->pIndex);
  }
  if( rc==SQLITE_OK ){
    nByte = sizeof(Fts5Cursor) + pConfig->nCol * sizeof(int);
    pCsr = (Fts5Cursor*)sqlite3_malloc(nByte);
    if( pCsr ){
      Fts5Global *pGlobal = pTab->pGlobal;
      memset(pCsr, 0, nByte);
      pCsr->aColumnSize = (int*)&pCsr[1];
................................................................................
      pCsr->pNext = pGlobal->pCsr;
      pGlobal->pCsr = pCsr;
      pCsr->iCsrId = ++pGlobal->iNextId;
    }else{
      rc = SQLITE_NOMEM;
    }
  }
  if( rc!=SQLITE_OK ){
    sqlite3Fts5IndexCloseReader(pTab->pIndex);
  }
  *ppCsr = (sqlite3_vtab_cursor*)pCsr;
  return rc;
}

static int fts5StmtType(Fts5Cursor *pCsr){
  if( pCsr->ePlan==FTS5_PLAN_SCAN ){
    return (pCsr->bDesc) ? FTS5_STMT_SCAN_DESC : FTS5_STMT_SCAN_ASC;
................................................................................

    fts5FreeCursorComponents(pCsr);
    /* Remove the cursor from the Fts5Global.pCsr list */
    for(pp=&pTab->pGlobal->pCsr; (*pp)!=pCsr; pp=&(*pp)->pNext);
    *pp = pCsr->pNext;

    sqlite3_free(pCsr);
    sqlite3Fts5IndexCloseReader(pTab->pIndex);
  }
  return SQLITE_OK;
}

static int fts5SorterNext(Fts5Cursor *pCsr){
  Fts5Sorter *pSorter = pCsr->pSorter;
  int rc;
................................................................................
  return rc;
}

/*
** Implementation of xBegin() method. 
*/
static int fts5BeginMethod(sqlite3_vtab *pVtab){
  Fts5Table *pTab = (Fts5Table*)pVtab;
  int rc;
  rc = fts5NewTransaction(pTab);
  if( rc!=SQLITE_OK ){
    sqlite3Fts5IndexCloseReader(pTab->pIndex);
  }
#ifdef SQLITE_DEBUG
  if( rc==SQLITE_OK ) fts5CheckTransactionState(pTab, FTS5_BEGIN, 0);
#endif
  return rc;
}

/*
** Implementation of xCommit() method. This is a no-op. The contents of
** the pending-terms hash-table have already been flushed into the database
** by fts5SyncMethod().
*/

Changes to ext/fts5/fts5_storage.c.

637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
....
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
  return sqlite3Fts5IndexOptimize(p->pIndex);
}

int sqlite3Fts5StorageMerge(Fts5Storage *p, int nMerge){
  return sqlite3Fts5IndexMerge(p->pIndex, nMerge);
}

int sqlite3Fts5StorageReset(Fts5Storage *p){
  return sqlite3Fts5IndexReset(p->pIndex);
}

/*
** Allocate a new rowid. This is used for "external content" tables when
** a NULL value is inserted into the rowid column. The new rowid is allocated
** by inserting a dummy row into the %_docsize table. The dummy will be
** overwritten later.
**
** If the %_docsize table does not exist, SQLITE_MISMATCH is returned. In
................................................................................
    }else{
      sqlite3_bind_int(pReplace, 2, iVal);
    }
    sqlite3_step(pReplace);
    rc = sqlite3_reset(pReplace);
  }
  if( rc==SQLITE_OK && pVal ){
    int iNew = p->pConfig->iCookie + 1;
    rc = sqlite3Fts5IndexSetCookie(p->pIndex, iNew);
    if( rc==SQLITE_OK ){
      p->pConfig->iCookie = iNew;
    }
  }
  return rc;
}







<
<
<
<







 







<
|
<
<
<



637
638
639
640
641
642
643




644
645
646
647
648
649
650
....
1112
1113
1114
1115
1116
1117
1118

1119



1120
1121
1122
  return sqlite3Fts5IndexOptimize(p->pIndex);
}

int sqlite3Fts5StorageMerge(Fts5Storage *p, int nMerge){
  return sqlite3Fts5IndexMerge(p->pIndex, nMerge);
}





/*
** Allocate a new rowid. This is used for "external content" tables when
** a NULL value is inserted into the rowid column. The new rowid is allocated
** by inserting a dummy row into the %_docsize table. The dummy will be
** overwritten later.
**
** If the %_docsize table does not exist, SQLITE_MISMATCH is returned. In
................................................................................
    }else{
      sqlite3_bind_int(pReplace, 2, iVal);
    }
    sqlite3_step(pReplace);
    rc = sqlite3_reset(pReplace);
  }
  if( rc==SQLITE_OK && pVal ){

    rc = sqlite3Fts5IndexIncrCookie(p->pIndex);



  }
  return rc;
}

Changes to ext/fts5/test/fts5_common.tcl.

640
641
642
643
644
645
646
647







    }
  }
  sqlite3_fts5_create_tokenizer db tclnum tclnum_create
}
#
# End of tokenizer code.
#-------------------------------------------------------------------------
















>
>
>
>
>
>
>
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
    }
  }
  sqlite3_fts5_create_tokenizer db tclnum tclnum_create
}
#
# End of tokenizer code.
#-------------------------------------------------------------------------

proc fts5_rowid_func {segid pgno} { return [expr ($segid<<37) + $pgno] }
proc register_fts5_rowid {db} {
  $db func fts5_rowid -argcount 2 fts5_rowid_func
}



Changes to ext/fts5/test/fts5ai.test.

47
48
49
50
51
52
53
54



55























































56
57
58
    ROLLBACK TO one;
  COMMIT;
}

do_execsql_test 1.2 {
  INSERT INTO t1(t1) VALUES('integrity-check');
}
}




























































finish_test








|
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>



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
    ROLLBACK TO one;
  COMMIT;
}

do_execsql_test 1.2 {
  INSERT INTO t1(t1) VALUES('integrity-check');
}

#-------------------------------------------------------------------------
# Test that the in-memory configuration does not become inconsistent with
# respect to the on-disk configuration if a savepoint is rolled back.
#
proc posrowid {cmd} { $cmd xRowid }
proc negrowid {cmd} { expr -1 * [$cmd xRowid] }
sqlite3_fts5_create_function db posrowid posrowid
sqlite3_fts5_create_function db negrowid negrowid

do_execsql_test 2.1 {
  INSERT INTO t1(rowid, a) VALUES(1001, 'x y 1');
  INSERT INTO t1(rowid, a) VALUES(1002, 'x y 2');
  INSERT INTO t1(rowid, a) VALUES(1003, 'x y 3');
  BEGIN;
    INSERT INTO t1(t1, rank) VALUES('rank', 'posrowid()');
    SELECT a FROM t1('x') ORDER BY rank;
} {{x y 1} {x y 2} {x y 3}}

do_execsql_test 2.2 {
  SAVEPOINT abc;
    INSERT INTO t1(t1, rank) VALUES('rank', 'negrowid()');
    SELECT a FROM t1('x') ORDER BY rank;
} {{x y 3} {x y 2} {x y 1}}

do_execsql_test 2.3 {
  ROLLBACK TO abc;
    SELECT a FROM t1('x') ORDER BY rank;
  COMMIT;
} {{x y 1} {x y 2} {x y 3}}

#-------------------------------------------------------------------------
# Test that the in-memory structure does not become inconsistent with
# respect to the on-disk configuration if a savepoint is rolled back.
#
do_execsql_test 3.1 {
  CREATE VIRTUAL TABLE t2 USING fts5(x, detail=%DETAIL%);
  INSERT INTO t2 VALUES('a 1');
  INSERT INTO t2 VALUES('a 2');
  INSERT INTO t2 VALUES('a 3');
  SELECT count(*) FROM t2_data;
} {5}

do_execsql_test 3.2 {
  BEGIN;
    SAVEPOINT one;
      INSERT INTO t2(rowid, x) VALUES(8, 'a 8');
      INSERT INTO t2(rowid, x) VALUES(7, 'a 7');
      INSERT INTO t2(rowid, x) VALUES(6, 'a 6');
      SELECT count(*) FROM t2_data;
} {7}
do_execsql_test 3.3 { INSERT INTO t2(t2) VALUES('integrity-check') } {}

do_execsql_test 3.4 {
  ROLLBACK TO one;
      SELECT count(*) FROM t2_data;
} {5}
do_execsql_test 3.5 { INSERT INTO t2(t2) VALUES('integrity-check') } {}

} ;# foreach_detail_mode

finish_test

Changes to ext/fts5/test/fts5corrupt.test.

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
  fts5_level_segs t1
} {1}
db_save

do_execsql_test 1.2 { INSERT INTO t1(t1) VALUES('integrity-check') }
set segid [lindex [fts5_level_segids t1] 0]


do_test 1.3 {
  execsql {
    DELETE FROM t1_data WHERE rowid = fts5_rowid('segment', $segid, 4);
  }
  catchsql { INSERT INTO t1(t1) VALUES('integrity-check') }
} {1 {database disk image is malformed}}

do_test 1.4 {
  db_restore_and_reopen

  execsql {
    UPDATE t1_data set block = X'00000000' || substr(block, 5) WHERE
    rowid = fts5_rowid('segment', $segid, 4);
  }
  catchsql { INSERT INTO t1(t1) VALUES('integrity-check') }
} {1 {database disk image is malformed}}

db_restore_and_reopen
#db eval {SELECT rowid, fts5_decode(rowid, block) aS r FROM t1_data} {puts $r}








>


|






>


|







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
  fts5_level_segs t1
} {1}
db_save

do_execsql_test 1.2 { INSERT INTO t1(t1) VALUES('integrity-check') }
set segid [lindex [fts5_level_segids t1] 0]

register_fts5_rowid db
do_test 1.3 {
  execsql {
    DELETE FROM t1_data WHERE rowid = fts5_rowid($segid, 4);
  }
  catchsql { INSERT INTO t1(t1) VALUES('integrity-check') }
} {1 {database disk image is malformed}}

do_test 1.4 {
  db_restore_and_reopen
  register_fts5_rowid db
  execsql {
    UPDATE t1_data set block = X'00000000' || substr(block, 5) WHERE
    rowid = fts5_rowid($segid, 4);
  }
  catchsql { INSERT INTO t1(t1) VALUES('integrity-check') }
} {1 {database disk image is malformed}}

db_restore_and_reopen
#db eval {SELECT rowid, fts5_decode(rowid, block) aS r FROM t1_data} {puts $r}

Changes to ext/fts5/test/fts5fault4.test.

82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
}

set ::res [db eval {SELECT rowid, x1 FROM x1 WHERE x1 MATCH '*reads'}]

do_faultsim_test 4 -faults oom-* -body {
  db eval {SELECT rowid, x, x1 FROM x1 WHERE x1 MATCH '*reads'}
} -test {
  faultsim_test_result {0 {0 {} 3}}
}

#-------------------------------------------------------------------------
# An OOM within a query that uses a custom rank function.
#
reset_db
do_execsql_test 5.0 {







|







82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
}

set ::res [db eval {SELECT rowid, x1 FROM x1 WHERE x1 MATCH '*reads'}]

do_faultsim_test 4 -faults oom-* -body {
  db eval {SELECT rowid, x, x1 FROM x1 WHERE x1 MATCH '*reads'}
} -test {
  faultsim_test_result {0 {0 {} 4}}
}

#-------------------------------------------------------------------------
# An OOM within a query that uses a custom rank function.
#
reset_db
do_execsql_test 5.0 {

Added ext/fts5/test/fts5faultC.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
# 2016 March 26
#
# 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 is focused on OOM errors.
#

source [file join [file dirname [info script]] fts5_common.tcl]
source $testdir/malloc_common.tcl
set testprefix fts5faultC
return_if_no_fts5

if 1 {

#--------------------------------------------------------------------------
# Test that if an OOM error occurs while trying to set a configuration
# option, the in-memory and on-disk configurations are not left in an 
# inconsistent state.
#
proc posrowid {cmd} { $cmd xRowid }
proc negrowid {cmd} { expr -1 * [$cmd xRowid] }

sqlite3_fts5_create_function db posrowid posrowid
sqlite3_fts5_create_function db negrowid negrowid

do_execsql_test 1.0.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(x);
  INSERT INTO t1 VALUES('a b c');
  INSERT INTO t1 VALUES('d a d');
  INSERT INTO t1 VALUES('c b a');
}
do_execsql_test 1.0.1 {
  INSERT INTO t1(t1, rank) VALUES('rank', 'posrowid()');
  SELECT rowid FROM t1('a') ORDER BY rank;
} {1 2 3}
do_execsql_test 1.0.2 {
  INSERT INTO t1(t1, rank) VALUES('rank', 'negrowid()');
  SELECT rowid FROM t1('a') ORDER BY rank;
} {3 2 1}

faultsim_save_and_close 
do_faultsim_test 1.1 -faults oom-* -prep {
  faultsim_restore_and_reopen
  sqlite3_fts5_create_function db posrowid posrowid
  sqlite3_fts5_create_function db negrowid negrowid
  execsql { SELECT * FROM t1('*reads') }
} -body {
  execsql { INSERT INTO t1(t1, rank) VALUES('rank', 'posrowid()') }
} -test {

  faultsim_test_result [list 0 {}]
  sqlite3 db2 test.db
  set ex [db2 one { SELECT v FROM t1_config WHERE k='rank' }]
  switch -- $ex {
    "posrowid()" { set ex {1 2 3} }
    "negrowid()" { set ex {3 2 1} }
    default { error 1 }
  }
  
  set res [db eval { SELECT rowid FROM t1('a') ORDER BY rank }]
  if {$res != $ex} {
    error "2: expected {$ex} got {$res}"
  }
  db2 close
}


#--------------------------------------------------------------------------

reset_db
do_execsql_test 2.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(y);
}
do_faultsim_test 2.1 -faults * -prep {
  sqlite3 db test.db
  execsql { SELECT * FROM t1('x') }
} -body {
  execsql { SELECT * FROM t1('x') }
  execsql { SELECT * FROM t1('x') }
} -test {
  faultsim_test_result [list 0 {}]
}
do_faultsim_test 2.2 -faults * -prep {
  sqlite3 db test.db
  execsql { INSERT INTO t1 VALUES('yy') }
} -body {
  execsql { INSERT INTO t1 VALUES('yy') }
  execsql { INSERT INTO t1 VALUES('yy') }
} -test {
  faultsim_test_result [list 0 {}]
}

#--------------------------------------------------------------------------
}
reset_db
do_execsql_test 3.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(y);
}
faultsim_save_and_close
do_faultsim_test 3.1 -faults * -prep {
  faultsim_restore_and_reopen
  execsql { 
    BEGIN;
      INSERT INTO t1 VALUES('x y z');
      INSERT INTO t1 VALUES('a b c');
  }
} -body {
  execsql { INSERT INTO t1(t1) VALUES('optimize') }
} -test {
  faultsim_test_result [list 0 {}]
}

finish_test

Changes to ext/fts5/test/fts5rowid.test.

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
..
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#
# Tests of the scalar fts5_rowid() and fts5_decode() functions.
#

source [file join [file dirname [info script]] fts5_common.tcl]
set testprefix fts5rowid

# If SQLITE_ENABLE_FTS5 is defined, omit this file.
ifcapable !fts5 {
  finish_test
  return
}

do_catchsql_test 1.1 {
  SELECT fts5_rowid()
} {1 {should be: fts5_rowid(subject, ....)}}

do_catchsql_test 1.2 {
  SELECT fts5_rowid('segment')
} {1 {should be: fts5_rowid('segment', segid, pgno))}}

do_execsql_test 1.3 {
  SELECT fts5_rowid('segment', 1, 1)
} {137438953473}

do_catchsql_test 1.4 {
  SELECT fts5_rowid('nosucharg');
} {1 {first arg to fts5_rowid() must be 'segment'}} 


#-------------------------------------------------------------------------
# Tests of the fts5_decode() function.
#
reset_db

do_execsql_test 2.1 { 
  CREATE VIRTUAL TABLE x1 USING fts5(a, b);
  INSERT INTO x1(x1, rank) VALUES('pgsz', 32);
} {}

proc rnddoc {n} {
  set map [list 0 a  1 b  2 c  3 d  4 e  5 f  6 g  7 h  8 i  9 j]
................................................................................
# This is really a corruption test...
#do_execsql_test 2.7 {
#  UPDATE x1_data SET block = X'';
#  SELECT count(fts5_decode(rowid, block)) FROM x1_data;
#} $res

do_execsql_test 2.8 {
  SELECT fts5_decode(fts5_rowid('segment', 1000, 1), X'AB')
} {corrupt}

#-------------------------------------------------------------------------
# Tests with very large tokens.
#
set strlist [list \
  "[string repeat x 400]"                       \







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





>







 







|







11
12
13
14
15
16
17



18


















19
20
21
22
23
24
25
26
27
28
29
30
31
..
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#
# Tests of the scalar fts5_rowid() and fts5_decode() functions.
#

source [file join [file dirname [info script]] fts5_common.tcl]
set testprefix fts5rowid




return_if_no_fts5



















#-------------------------------------------------------------------------
# Tests of the fts5_decode() function.
#
reset_db
register_fts5_rowid db
do_execsql_test 2.1 { 
  CREATE VIRTUAL TABLE x1 USING fts5(a, b);
  INSERT INTO x1(x1, rank) VALUES('pgsz', 32);
} {}

proc rnddoc {n} {
  set map [list 0 a  1 b  2 c  3 d  4 e  5 f  6 g  7 h  8 i  9 j]
................................................................................
# This is really a corruption test...
#do_execsql_test 2.7 {
#  UPDATE x1_data SET block = X'';
#  SELECT count(fts5_decode(rowid, block)) FROM x1_data;
#} $res

do_execsql_test 2.8 {
  SELECT fts5_decode(fts5_rowid(1000, 1), X'AB')
} {corrupt}

#-------------------------------------------------------------------------
# Tests with very large tokens.
#
set strlist [list \
  "[string repeat x 400]"                       \

Changes to ext/fts5/test/fts5simple.test.

346
347
348
349
350
351
352
353
354
355
356
357
358
359
360

  WITH ii(i) AS ( SELECT 1 UNION ALL SELECT i+1 FROM ii WHERE i<10 )
  INSERT INTO x1 SELECT rnddoc(5) FROM ii;
}

do_execsql_test 14.4 {
  SELECT rowid, x, x1 FROM x1 WHERE x1 MATCH '*reads'
} {0 {} 3}

#-------------------------------------------------------------------------
reset_db
do_execsql_test 15.0 {
  CREATE VIRTUAL TABLE x2 USING fts5(x, prefix=1);
  INSERT INTO x2 VALUES('ab');
}







|







346
347
348
349
350
351
352
353
354
355
356
357
358
359
360

  WITH ii(i) AS ( SELECT 1 UNION ALL SELECT i+1 FROM ii WHERE i<10 )
  INSERT INTO x1 SELECT rnddoc(5) FROM ii;
}

do_execsql_test 14.4 {
  SELECT rowid, x, x1 FROM x1 WHERE x1 MATCH '*reads'
} {0 {} 4}

#-------------------------------------------------------------------------
reset_db
do_execsql_test 15.0 {
  CREATE VIRTUAL TABLE x2 USING fts5(x, prefix=1);
  INSERT INTO x2 VALUES('ab');
}

Changes to ext/fts5/test/fts5simple3.test.

51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
..
76
77
78
79
80
81
82
83













































84
85
    set vals [list]
    for {set i 1} {$i <= 998} {incr i} {
      lappend cols "c$i"
      lappend vals "'val$i'"
    }
    execsql "CREATE VIRTUAL TABLE t2 USING fts5(detail=%DETAIL%,[join $cols ,])"
  } {}
  
  do_test 2.2 {
    execsql "INSERT INTO t2 VALUES([join $vals ,])"
  } {}
  
  foreach {tn q res} {
    1 { c1:val1 }     1
    2 { c300:val300 } 1
    3 { c300:val1 } {}
    4 { c1:val300 } {}
  } {
    do_execsql_test 2.3.$tn {
................................................................................
  CREATE VIRTUAL TABLE x3 USING fts5(one);
  INSERT INTO x3 VALUES('a b c');
  INSERT INTO x3 VALUES('c b a');
  INSERT INTO x3 VALUES('o t t');
  SELECT * FROM x3('x OR y OR z');
}















































finish_test








|



|







 








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


51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
..
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
    set vals [list]
    for {set i 1} {$i <= 998} {incr i} {
      lappend cols "c$i"
      lappend vals "'val$i'"
    }
    execsql "CREATE VIRTUAL TABLE t2 USING fts5(detail=%DETAIL%,[join $cols ,])"
  } {}

  do_test 2.2 {
    execsql "INSERT INTO t2 VALUES([join $vals ,])"
  } {}
 
  foreach {tn q res} {
    1 { c1:val1 }     1
    2 { c300:val300 } 1
    3 { c300:val1 } {}
    4 { c1:val300 } {}
  } {
    do_execsql_test 2.3.$tn {
................................................................................
  CREATE VIRTUAL TABLE x3 USING fts5(one);
  INSERT INTO x3 VALUES('a b c');
  INSERT INTO x3 VALUES('c b a');
  INSERT INTO x3 VALUES('o t t');
  SELECT * FROM x3('x OR y OR z');
}


#-------------------------------------------------------------------------
# Check that if a CREATE VIRTUAL TABLE statement fails within a 
# transaction, any changes made to the database are reverted before
# continuing.
#
reset_db
do_catchsql_test 4.0 {
  BEGIN;
    CREATE VIRTUAL TABLE t1 USING fts5;
} {1 {vtable constructor failed: t1}}

do_execsql_test 4.1 { SELECT * FROM sqlite_master } {}
do_execsql_test 4.2 { COMMIT }
do_execsql_test 4.3 { SELECT * FROM sqlite_master } {}

#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 5.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(a);
  INSERT INTO t1 VALUES('vtable constructor failed');
} {}
do_execsql_test 5.1 {
  SELECT quote(block) FROM t1_data WHERE rowid=10;
} {
  X'000000000101010001010101'
}
do_test 5.3 {
  sqlite3 db2 test.db
  register_fts5_rowid db2
  db2 eval {
    UPDATE t1_data SET block = X'000000000101010001A7080101' WHERE rowid=10;
    UPDATE t1_data SET rowid=fts5_rowid(5000, 1) WHERE rowid=fts5_rowid(1,1);
    UPDATE t1_idx SET segid=5000 WHERE segid=1;
  }
  db2 close
} {}
do_execsql_test 5.4 {
  SELECT rowid FROM t1('cons*');
} {1}
breakpoint
do_execsql_test 5.5 {
  INSERT INTO t1 VALUES('hello world');
}

finish_test

Changes to ext/fts5/test/fts5synonym2.test.

38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
    }
  }

  list [sort_poslist $PL] $CL
}
sqlite3_fts5_create_function db fts5_test_bothlist fts5_test_bothlist

proc fts5_rowid {cmd} { expr [$cmd xColumnText -1] }
sqlite3_fts5_create_function db fts5_rowid fts5_rowid

do_execsql_test 1.$tok.0.1 "
  CREATE VIRTUAL TABLE ss USING fts5(a, b, 
       tokenize='tclnum $tok', detail=%DETAIL%);
  INSERT INTO ss(ss, rank) VALUES('rank', 'fts5_rowid()');
"

do_execsql_test 1.$tok.0.2 {
  INSERT INTO ss VALUES('5 5 five seven 3 seven i', '2 1 5 0 two 1 i');
  INSERT INTO ss VALUES('six ix iii 7 i vii iii', 'one seven nine 4 9 1 vi');
  INSERT INTO ss VALUES('6 viii i five six zero seven', '5 v iii iv iv 3');
  INSERT INTO ss VALUES('9 ii six 8 1 6', 'six 4 iv iv 7');







|
|




|







38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
    }
  }

  list [sort_poslist $PL] $CL
}
sqlite3_fts5_create_function db fts5_test_bothlist fts5_test_bothlist

proc rowid_func {cmd} { expr [$cmd xColumnText -1] }
sqlite3_fts5_create_function db rowid_func rowid_func

do_execsql_test 1.$tok.0.1 "
  CREATE VIRTUAL TABLE ss USING fts5(a, b, 
       tokenize='tclnum $tok', detail=%DETAIL%);
  INSERT INTO ss(ss, rank) VALUES('rank', 'rowid_func()');
"

do_execsql_test 1.$tok.0.2 {
  INSERT INTO ss VALUES('5 5 five seven 3 seven i', '2 1 5 0 two 1 i');
  INSERT INTO ss VALUES('six ix iii 7 i vii iii', 'one seven nine 4 9 1 vi');
  INSERT INTO ss VALUES('6 viii i five six zero seven', '5 v iii iv iv 3');
  INSERT INTO ss VALUES('9 ii six 8 1 6', 'six 4 iv iv 7');

Changes to ext/fts5/test/fts5version.test.

55
56
57
58
59
60
61



















62
63
64
do_test 1.7 {
  execsql { DELETE FROM t1_config WHERE k='version' }
  db close
  sqlite3 db test.db
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'a' }
} {1 {invalid fts5 file format (found 0, expected 4) - run 'rebuild'}}





















finish_test








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



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
do_test 1.7 {
  execsql { DELETE FROM t1_config WHERE k='version' }
  db close
  sqlite3 db test.db
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'a' }
} {1 {invalid fts5 file format (found 0, expected 4) - run 'rebuild'}}

#---------------------------------------------------------------------------

do_execsql_test 2.1 {
  CREATE VIRTUAL TABLE t2 USING fts5(two);
  INSERT INTO t2 VALUES('a b c d');
}

do_test 2.2 {
  sqlite3 db2 test.db
  execsql {
    INSERT INTO t2(t2, rank) VALUES('pgsz', 512);
    UPDATE t2_config SET v=5 WHERE k='version';
  } db2
  db2 close
} {}

do_catchsql_test 2.3 {
  SELECT * FROM t2('b + c');
} {1 {SQL logic error or missing database}}

finish_test

Changes to src/vdbeaux.c.

505
506
507
508
509
510
511



512
513
514
515
516
517
518
     || ((opcode==OP_Halt || opcode==OP_HaltIfNull) 
      && ((pOp->p1&0xff)==SQLITE_CONSTRAINT && pOp->p2==OE_Abort))
    ){
      hasAbort = 1;
      break;
    }
    if( opcode==OP_CreateTable ) hasCreateTable = 1;



    if( opcode==OP_InitCoroutine ) hasInitCoroutine = 1;
#ifndef SQLITE_OMIT_FOREIGN_KEY
    if( opcode==OP_FkCounter && pOp->p1==0 && pOp->p2==1 ){
      hasFkCounter = 1;
    }
#endif
  }







>
>
>







505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
     || ((opcode==OP_Halt || opcode==OP_HaltIfNull) 
      && ((pOp->p1&0xff)==SQLITE_CONSTRAINT && pOp->p2==OE_Abort))
    ){
      hasAbort = 1;
      break;
    }
    if( opcode==OP_CreateTable ) hasCreateTable = 1;
#ifndef SQLITE_OMIT_VIRTUALTABLE
    if( opcode==OP_VCreate ) hasAbort = 1;
#endif
    if( opcode==OP_InitCoroutine ) hasInitCoroutine = 1;
#ifndef SQLITE_OMIT_FOREIGN_KEY
    if( opcode==OP_FkCounter && pOp->p1==0 && pOp->p2==1 ){
      hasFkCounter = 1;
    }
#endif
  }

Changes to src/vtab.c.

312
313
314
315
316
317
318

319
320
321
322
323
324
325
  int ifNotExists       /* No error if the table already exists */
){
  int iDb;              /* The database the table is being created in */
  Table *pTable;        /* The new virtual table */
  sqlite3 *db;          /* Database connection */

  sqlite3StartTable(pParse, pName1, pName2, 0, 0, 1, ifNotExists);

  pTable = pParse->pNewTable;
  if( pTable==0 ) return;
  assert( 0==pTable->pIndex );

  db = pParse->db;
  iDb = sqlite3SchemaToIndex(db, pTable->pSchema);
  assert( iDb>=0 );







>







312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
  int ifNotExists       /* No error if the table already exists */
){
  int iDb;              /* The database the table is being created in */
  Table *pTable;        /* The new virtual table */
  sqlite3 *db;          /* Database connection */

  sqlite3StartTable(pParse, pName1, pName2, 0, 0, 1, ifNotExists);
  sqlite3MayAbort(pParse);
  pTable = pParse->pNewTable;
  if( pTable==0 ) return;
  assert( 0==pTable->pIndex );

  db = pParse->db;
  iDb = sqlite3SchemaToIndex(db, pTable->pSchema);
  assert( iDb>=0 );