/ Check-in [0e225b15]
Login

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

Overview
Comment:Fix some problems with transactions that both read and write an fts5 table.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | fts5
Files: files | file ages | folders
SHA1:0e225b15357765f132c3364b222f9931a608a5b2
User & Date: dan 2015-01-29 20:59:34
Context
2015-01-31
15:23
Minor optimizations to fts5 writes. check-in: 1fffe51f user: dan tags: fts5
2015-01-29
20:59
Fix some problems with transactions that both read and write an fts5 table. check-in: 0e225b15 user: dan tags: fts5
2015-01-27
20:41
Fix a problem with fts5 doclist-indexes that occured if the first rowid of the first non-term page of a doclist is zero. check-in: f704bc05 user: dan tags: fts5
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/fts5/fts5Int.h.

224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
...
255
256
257
258
259
260
261
262

263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
...
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
...
401
402
403
404
405
406
407
408













409
410
411
412
413
414
415

typedef struct Fts5Index Fts5Index;
typedef struct Fts5IndexIter Fts5IndexIter;

/*
** 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 */

/*
** Create/destroy an Fts5Index object.
*/
int sqlite3Fts5IndexOpen(Fts5Config *pConfig, int bCreate, Fts5Index**, char**);
int sqlite3Fts5IndexClose(Fts5Index *p, int bDestroy);
................................................................................
  Fts5Index *p,                   /* FTS index to query */
  const char *pToken, int nToken, /* Token (or prefix) to query for */
  int flags,                      /* Mask of FTS5INDEX_QUERY_X flags */
  Fts5IndexIter **ppIter
);

/*
** Docid list iteration.

*/
int sqlite3Fts5IterEof(Fts5IndexIter*);
int sqlite3Fts5IterNext(Fts5IndexIter*);
int sqlite3Fts5IterNextFrom(Fts5IndexIter*, i64 iMatch);
i64 sqlite3Fts5IterRowid(Fts5IndexIter*);

/*
** Obtain the position list that corresponds to the current position.
*/
int sqlite3Fts5IterPoslist(Fts5IndexIter*, const u8 **pp, int *pn);

/*
** Close an iterator opened by sqlite3Fts5IndexQuery().
*/
void sqlite3Fts5IterClose(Fts5IndexIter*);

................................................................................
**************************************************************************/

/**************************************************************************
** Interface to code in fts5_hash.c. 
*/
typedef struct Fts5Hash Fts5Hash;

typedef struct Fts5Data Fts5Data;
struct Fts5Data {
  u8 *p;                          /* Pointer to buffer containing record */
  int n;                          /* Size of record in bytes */
  int nRef;                       /* Ref count */
};

/*
** Create a hash table, free a hash table.
*/
int sqlite3Fts5HashNew(Fts5Hash**, int *pnSize);
void sqlite3Fts5HashFree(Fts5Hash*);

int sqlite3Fts5HashWrite(
................................................................................
  int (*xEntry)(void*, i64, const u8*, int),
  int (*xTermDone)(void*)
);

int sqlite3Fts5HashQuery(
  Fts5Hash*,                      /* Hash table to query */
  const char *pTerm, int nTerm,   /* Query term */
  Fts5Data **ppData               /* OUT: Query result */













);


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








|







 







|
>





<
<
<
<







 







<
<
<
<
<
<
<







 







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







224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
...
255
256
257
258
259
260
261
262
263
264
265
266
267
268




269
270
271
272
273
274
275
...
358
359
360
361
362
363
364







365
366
367
368
369
370
371
...
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418

typedef struct Fts5Index Fts5Index;
typedef struct Fts5IndexIter Fts5IndexIter;

/*
** 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 */

/*
** Create/destroy an Fts5Index object.
*/
int sqlite3Fts5IndexOpen(Fts5Config *pConfig, int bCreate, Fts5Index**, char**);
int sqlite3Fts5IndexClose(Fts5Index *p, int bDestroy);
................................................................................
  Fts5Index *p,                   /* FTS index to query */
  const char *pToken, int nToken, /* Token (or prefix) to query for */
  int flags,                      /* Mask of FTS5INDEX_QUERY_X flags */
  Fts5IndexIter **ppIter
);

/*
** The various operations on open token or token prefix iterators opened
** using sqlite3Fts5IndexQuery().
*/
int sqlite3Fts5IterEof(Fts5IndexIter*);
int sqlite3Fts5IterNext(Fts5IndexIter*);
int sqlite3Fts5IterNextFrom(Fts5IndexIter*, i64 iMatch);
i64 sqlite3Fts5IterRowid(Fts5IndexIter*);




int sqlite3Fts5IterPoslist(Fts5IndexIter*, const u8 **pp, int *pn);

/*
** Close an iterator opened by sqlite3Fts5IndexQuery().
*/
void sqlite3Fts5IterClose(Fts5IndexIter*);

................................................................................
**************************************************************************/

/**************************************************************************
** Interface to code in fts5_hash.c. 
*/
typedef struct Fts5Hash Fts5Hash;








/*
** Create a hash table, free a hash table.
*/
int sqlite3Fts5HashNew(Fts5Hash**, int *pnSize);
void sqlite3Fts5HashFree(Fts5Hash*);

int sqlite3Fts5HashWrite(
................................................................................
  int (*xEntry)(void*, i64, const u8*, int),
  int (*xTermDone)(void*)
);

int sqlite3Fts5HashQuery(
  Fts5Hash*,                      /* Hash table to query */
  const char *pTerm, int nTerm,   /* Query term */
  const char **ppDoclist,         /* OUT: Pointer to doclist for pTerm */
  int *pnDoclist                  /* OUT: Size of doclist in bytes */
);

void sqlite3Fts5HashScanInit(
  Fts5Hash*,                      /* Hash table to query */
  const char *pTerm, int nTerm    /* Query prefix */
);
void sqlite3Fts5HashScanNext(Fts5Hash*);
int sqlite3Fts5HashScanEof(Fts5Hash*);
void sqlite3Fts5HashScanEntry(Fts5Hash *,
  const char **pzTerm,            /* OUT: term (nul-terminated) */
  const char **ppDoclist,         /* OUT: pointer to doclist */
  int *pnDoclist                  /* OUT: size of doclist in bytes */
);


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

Changes to ext/fts5/fts5_buffer.c.

70
71
72
73
74
75
76

77
78
79
80
81
82
83
*/
void sqlite3Fts5BufferAppendBlob(
  int *pRc,
  Fts5Buffer *pBuf, 
  int nData, 
  const u8 *pData
){

  if( sqlite3Fts5BufferGrow(pRc, pBuf, nData) ) return;
  memcpy(&pBuf->p[pBuf->n], pData, nData);
  pBuf->n += nData;
}

/*
** Append the nul-terminated string zStr to the buffer pBuf. This function







>







70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
*/
void sqlite3Fts5BufferAppendBlob(
  int *pRc,
  Fts5Buffer *pBuf, 
  int nData, 
  const u8 *pData
){
  assert( nData>=0 );
  if( sqlite3Fts5BufferGrow(pRc, pBuf, nData) ) return;
  memcpy(&pBuf->p[pBuf->n], pData, nData);
  pBuf->n += nData;
}

/*
** Append the nul-terminated string zStr to the buffer pBuf. This function

Changes to ext/fts5/fts5_hash.c.

23
24
25
26
27
28
29

30
31
32
33
34
35
36
..
48
49
50
51
52
53
54
55

56
57
58
59
60
61
62
...
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
...
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
...
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
...
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
...
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
...
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
...
318
319
320
321
322
323
324
325




326
327
328
329
330
331
332
333
334
335
336
337

338

339
340
341
342
343
344
345
346

347
348
349
350
351
352
353
...
364
365
366
367
368
369
370
371
372

373
374
375
376
377
378
379
380
381
...
401
402
403
404
405
406
407
408



































































*/


struct Fts5Hash {
  int *pnByte;                    /* Pointer to bytes counter */
  int nEntry;                     /* Number of entries currently in hash */
  int nSlot;                      /* Size of aSlot[] array */

  Fts5HashEntry **aSlot;          /* Array of hash slots */
};

/*
** Each entry in the hash table is represented by an object of the 
** following type. Each object, its key (zKey[]) and its current data
** are stored in a single memory allocation. The position list data 
................................................................................
**   Offset of last rowid written to data area. Relative to first byte of
**   structure.
**
** nData:
**   Bytes of data written since iRowidOff.
*/
struct Fts5HashEntry {
  Fts5HashEntry *pNext;           /* Next hash entry with same hash-key */

  
  int nAlloc;                     /* Total size of allocation */
  int iSzPoslist;                 /* Offset of space for 4-byte poslist size */
  int nData;                      /* Total bytes of data (incl. structure) */

  int iCol;                       /* Column of last value written */
  int iPos;                       /* Position of last value written */
................................................................................
*/
void sqlite3Fts5HashClear(Fts5Hash *pHash){
  int i;
  for(i=0; i<pHash->nSlot; i++){
    Fts5HashEntry *pNext;
    Fts5HashEntry *pSlot;
    for(pSlot=pHash->aSlot[i]; pSlot; pSlot=pNext){
      pNext = pSlot->pNext;
      sqlite3_free(pSlot);
    }
  }
  memset(pHash->aSlot, 0, pHash->nSlot * sizeof(Fts5HashEntry*));
  pHash->nEntry = 0;
}

................................................................................
  if( !apNew ) return SQLITE_NOMEM;
  memset(apNew, 0, nNew*sizeof(Fts5HashEntry*));

  for(i=0; i<pHash->nSlot; i++){
    while( apOld[i] ){
      int iHash;
      Fts5HashEntry *p = apOld[i];
      apOld[i] = p->pNext;
      iHash = fts5HashKey(nNew, p->zKey, strlen(p->zKey));
      p->pNext = apNew[iHash];
      apNew[iHash] = p;
    }
  }

  sqlite3_free(apOld);
  pHash->nSlot = nNew;
  pHash->aSlot = apNew;
................................................................................
){
  unsigned int iHash = fts5HashKey(pHash->nSlot, pToken, nToken);
  Fts5HashEntry *p;
  u8 *pPtr;
  int nIncr = 0;                  /* Amount to increment (*pHash->pnByte) by */

  /* Attempt to locate an existing hash entry */
  for(p=pHash->aSlot[iHash]; p; p=p->pNext){
    if( memcmp(p->zKey, pToken, nToken)==0 && p->zKey[nToken]==0 ) break;
  }

  /* If an existing hash entry cannot be found, create a new one. */
  if( p==0 ){
    int nByte = sizeof(Fts5HashEntry) + nToken + 1 + 64;
    if( nByte<128 ) nByte = 128;
................................................................................
    memcpy(p->zKey, pToken, nToken);
    p->zKey[nToken] = '\0';
    p->nData = nToken + 1 + sizeof(Fts5HashEntry);
    p->nData += sqlite3PutVarint(&((u8*)p)[p->nData], iRowid);
    p->iSzPoslist = p->nData;
    p->nData += 4;
    p->iRowid = iRowid;
    p->pNext = pHash->aSlot[iHash];
    pHash->aSlot[iHash] = p;
    pHash->nEntry++;
    nIncr += p->nData;
  }

  /* Check there is enough space to append a new entry. Worst case scenario
  ** is:
................................................................................
  if( (p->nAlloc - p->nData) < (9 + 4 + 1 + 3 + 5) ){
    int nNew = p->nAlloc * 2;
    Fts5HashEntry *pNew;
    Fts5HashEntry **pp;
    pNew = (Fts5HashEntry*)sqlite3_realloc(p, nNew);
    if( pNew==0 ) return SQLITE_NOMEM;
    pNew->nAlloc = nNew;
    for(pp=&pHash->aSlot[iHash]; *pp!=p; pp=&(*pp)->pNext);
    *pp = pNew;
    p = pNew;
  }
  pPtr = (u8*)p;
  nIncr -= p->nData;

  /* If this is a new rowid, append the 4-byte size field for the previous
................................................................................
    }else{
      int i = 0;
      while( p1->zKey[i]==p2->zKey[i] ) i++;

      if( ((u8)p1->zKey[i])>((u8)p2->zKey[i]) ){
        /* p2 is smaller */
        *ppOut = p2;
        ppOut = &p2->pNext;
        p2 = p2->pNext;
      }else{
        /* p1 is smaller */
        *ppOut = p1;
        ppOut = &p1->pNext;
        p1 = p1->pNext;
      }
      *ppOut = 0;
    }
  }

  return pRet;
}
................................................................................

/*
** Extract all tokens from hash table iHash and link them into a list
** in sorted order. The hash table is cleared before returning. It is
** the responsibility of the caller to free the elements of the returned
** list.
*/
static int fts5HashEntrySort(Fts5Hash *pHash, Fts5HashEntry **ppSorted){




  const int nMergeSlot = 32;
  Fts5HashEntry **ap;
  Fts5HashEntry *pList;
  int iSlot;
  int i;

  *ppSorted = 0;
  ap = sqlite3_malloc(sizeof(Fts5HashEntry*) * nMergeSlot);
  if( !ap ) return SQLITE_NOMEM;
  memset(ap, 0, sizeof(Fts5HashEntry*) * nMergeSlot);

  for(iSlot=0; iSlot<pHash->nSlot; iSlot++){

    while( pHash->aSlot[iSlot] ){

      Fts5HashEntry *pEntry = pHash->aSlot[iSlot];
      pHash->aSlot[iSlot] = pEntry->pNext;
      pEntry->pNext = 0;
      for(i=0; ap[i]; i++){
        pEntry = fts5HashEntryMerge(pEntry, ap[i]);
        ap[i] = 0;
      }
      ap[i] = pEntry;

    }
  }

  pList = 0;
  for(i=0; i<nMergeSlot; i++){
    pList = fts5HashEntryMerge(pList, ap[i]);
  }
................................................................................
  int (*xTerm)(void*, const char*, int),
  int (*xEntry)(void*, i64, const u8*, int),
  int (*xTermDone)(void*)
){
  Fts5HashEntry *pList;
  int rc;

  rc = fts5HashEntrySort(pHash, &pList);
  if( rc==SQLITE_OK ){

    while( pList ){
      Fts5HashEntry *pNext = pList->pNext;
      if( rc==SQLITE_OK ){
        const int nSz = pList->nData - pList->iSzPoslist - 4;
        const int nKey = strlen(pList->zKey);
        i64 iRowid = 0;
        u8 *pPtr = (u8*)pList;
        int iOff = sizeof(Fts5HashEntry) + nKey + 1;

................................................................................
      }
      sqlite3_free(pList);
      pList = pNext;
    }
  }
  return rc;
}











































































>







 







|
>







 







|







 







|

|







 







|







 







|







 







|







 







|
|



|
|







 







|
>
>
>
>












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







 







|

>

|







 








>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
..
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
...
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
...
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
...
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
...
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
...
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
...
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
...
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347

348
349
350
351
352
353
354
355
356
357
358
359
360
361
...
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
...
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
*/


struct Fts5Hash {
  int *pnByte;                    /* Pointer to bytes counter */
  int nEntry;                     /* Number of entries currently in hash */
  int nSlot;                      /* Size of aSlot[] array */
  Fts5HashEntry *pScan;           /* Current ordered scan item */
  Fts5HashEntry **aSlot;          /* Array of hash slots */
};

/*
** Each entry in the hash table is represented by an object of the 
** following type. Each object, its key (zKey[]) and its current data
** are stored in a single memory allocation. The position list data 
................................................................................
**   Offset of last rowid written to data area. Relative to first byte of
**   structure.
**
** nData:
**   Bytes of data written since iRowidOff.
*/
struct Fts5HashEntry {
  Fts5HashEntry *pHashNext;       /* Next hash entry with same hash-key */
  Fts5HashEntry *pScanNext;       /* Next entry in sorted order */
  
  int nAlloc;                     /* Total size of allocation */
  int iSzPoslist;                 /* Offset of space for 4-byte poslist size */
  int nData;                      /* Total bytes of data (incl. structure) */

  int iCol;                       /* Column of last value written */
  int iPos;                       /* Position of last value written */
................................................................................
*/
void sqlite3Fts5HashClear(Fts5Hash *pHash){
  int i;
  for(i=0; i<pHash->nSlot; i++){
    Fts5HashEntry *pNext;
    Fts5HashEntry *pSlot;
    for(pSlot=pHash->aSlot[i]; pSlot; pSlot=pNext){
      pNext = pSlot->pHashNext;
      sqlite3_free(pSlot);
    }
  }
  memset(pHash->aSlot, 0, pHash->nSlot * sizeof(Fts5HashEntry*));
  pHash->nEntry = 0;
}

................................................................................
  if( !apNew ) return SQLITE_NOMEM;
  memset(apNew, 0, nNew*sizeof(Fts5HashEntry*));

  for(i=0; i<pHash->nSlot; i++){
    while( apOld[i] ){
      int iHash;
      Fts5HashEntry *p = apOld[i];
      apOld[i] = p->pHashNext;
      iHash = fts5HashKey(nNew, p->zKey, strlen(p->zKey));
      p->pHashNext = apNew[iHash];
      apNew[iHash] = p;
    }
  }

  sqlite3_free(apOld);
  pHash->nSlot = nNew;
  pHash->aSlot = apNew;
................................................................................
){
  unsigned int iHash = fts5HashKey(pHash->nSlot, pToken, nToken);
  Fts5HashEntry *p;
  u8 *pPtr;
  int nIncr = 0;                  /* Amount to increment (*pHash->pnByte) by */

  /* Attempt to locate an existing hash entry */
  for(p=pHash->aSlot[iHash]; p; p=p->pHashNext){
    if( memcmp(p->zKey, pToken, nToken)==0 && p->zKey[nToken]==0 ) break;
  }

  /* If an existing hash entry cannot be found, create a new one. */
  if( p==0 ){
    int nByte = sizeof(Fts5HashEntry) + nToken + 1 + 64;
    if( nByte<128 ) nByte = 128;
................................................................................
    memcpy(p->zKey, pToken, nToken);
    p->zKey[nToken] = '\0';
    p->nData = nToken + 1 + sizeof(Fts5HashEntry);
    p->nData += sqlite3PutVarint(&((u8*)p)[p->nData], iRowid);
    p->iSzPoslist = p->nData;
    p->nData += 4;
    p->iRowid = iRowid;
    p->pHashNext = pHash->aSlot[iHash];
    pHash->aSlot[iHash] = p;
    pHash->nEntry++;
    nIncr += p->nData;
  }

  /* Check there is enough space to append a new entry. Worst case scenario
  ** is:
................................................................................
  if( (p->nAlloc - p->nData) < (9 + 4 + 1 + 3 + 5) ){
    int nNew = p->nAlloc * 2;
    Fts5HashEntry *pNew;
    Fts5HashEntry **pp;
    pNew = (Fts5HashEntry*)sqlite3_realloc(p, nNew);
    if( pNew==0 ) return SQLITE_NOMEM;
    pNew->nAlloc = nNew;
    for(pp=&pHash->aSlot[iHash]; *pp!=p; pp=&(*pp)->pHashNext);
    *pp = pNew;
    p = pNew;
  }
  pPtr = (u8*)p;
  nIncr -= p->nData;

  /* If this is a new rowid, append the 4-byte size field for the previous
................................................................................
    }else{
      int i = 0;
      while( p1->zKey[i]==p2->zKey[i] ) i++;

      if( ((u8)p1->zKey[i])>((u8)p2->zKey[i]) ){
        /* p2 is smaller */
        *ppOut = p2;
        ppOut = &p2->pScanNext;
        p2 = p2->pScanNext;
      }else{
        /* p1 is smaller */
        *ppOut = p1;
        ppOut = &p1->pScanNext;
        p1 = p1->pScanNext;
      }
      *ppOut = 0;
    }
  }

  return pRet;
}
................................................................................

/*
** Extract all tokens from hash table iHash and link them into a list
** in sorted order. The hash table is cleared before returning. It is
** the responsibility of the caller to free the elements of the returned
** list.
*/
static int fts5HashEntrySort(
  Fts5Hash *pHash, 
  const char *pTerm, int nTerm,   /* Query prefix, if any */
  Fts5HashEntry **ppSorted
){
  const int nMergeSlot = 32;
  Fts5HashEntry **ap;
  Fts5HashEntry *pList;
  int iSlot;
  int i;

  *ppSorted = 0;
  ap = sqlite3_malloc(sizeof(Fts5HashEntry*) * nMergeSlot);
  if( !ap ) return SQLITE_NOMEM;
  memset(ap, 0, sizeof(Fts5HashEntry*) * nMergeSlot);

  for(iSlot=0; iSlot<pHash->nSlot; iSlot++){
    Fts5HashEntry *pIter;
    for(pIter=pHash->aSlot[iSlot]; pIter; pIter=pIter->pHashNext){
      if( pTerm==0 || 0==memcmp(pIter->zKey, pTerm, nTerm) ){
        Fts5HashEntry *pEntry = pIter;

        pEntry->pScanNext = 0;
        for(i=0; ap[i]; i++){
          pEntry = fts5HashEntryMerge(pEntry, ap[i]);
          ap[i] = 0;
        }
        ap[i] = pEntry;
      }
    }
  }

  pList = 0;
  for(i=0; i<nMergeSlot; i++){
    pList = fts5HashEntryMerge(pList, ap[i]);
  }
................................................................................
  int (*xTerm)(void*, const char*, int),
  int (*xEntry)(void*, i64, const u8*, int),
  int (*xTermDone)(void*)
){
  Fts5HashEntry *pList;
  int rc;

  rc = fts5HashEntrySort(pHash, 0, 0, &pList);
  if( rc==SQLITE_OK ){
    memset(pHash->aSlot, 0, sizeof(Fts5HashEntry*) * pHash->nSlot);
    while( pList ){
      Fts5HashEntry *pNext = pList->pScanNext;
      if( rc==SQLITE_OK ){
        const int nSz = pList->nData - pList->iSzPoslist - 4;
        const int nKey = strlen(pList->zKey);
        i64 iRowid = 0;
        u8 *pPtr = (u8*)pList;
        int iOff = sizeof(Fts5HashEntry) + nKey + 1;

................................................................................
      }
      sqlite3_free(pList);
      pList = pNext;
    }
  }
  return rc;
}

/*
** Query the hash table for a doclist associated with term pTerm/nTerm.
*/
int sqlite3Fts5HashQuery(
  Fts5Hash *pHash,                /* Hash table to query */
  const char *pTerm, int nTerm,   /* Query term */
  const char **ppDoclist,         /* OUT: Pointer to doclist for pTerm */
  int *pnDoclist                  /* OUT: Size of doclist in bytes */
){
  unsigned int iHash = fts5HashKey(pHash->nSlot, pTerm, nTerm);
  Fts5HashEntry *p;

  for(p=pHash->aSlot[iHash]; p; p=p->pHashNext){
    if( memcmp(p->zKey, pTerm, nTerm)==0 && p->zKey[nTerm]==0 ) break;
  }

  if( p ){
    u8 *pPtr = (u8*)p;
    fts5Put4ByteVarint(&pPtr[p->iSzPoslist], p->nData - p->iSzPoslist - 4);
    *ppDoclist = &p->zKey[nTerm+1];
    *pnDoclist = p->nData - (sizeof(*p) + nTerm + 1);
  }else{
    *ppDoclist = 0;
    *pnDoclist = 0;
  }

  return SQLITE_OK;
}

void sqlite3Fts5HashScanInit(
  Fts5Hash *p,                    /* Hash table to query */
  const char *pTerm, int nTerm    /* Query prefix */
){
  fts5HashEntrySort(p, pTerm, nTerm, &p->pScan);
}

void sqlite3Fts5HashScanNext(Fts5Hash *p){
  if( p->pScan ){
    p->pScan = p->pScan->pScanNext;
  }
}

int sqlite3Fts5HashScanEof(Fts5Hash *p){
  return (p->pScan==0);
}

void sqlite3Fts5HashScanEntry(
  Fts5Hash *pHash,
  const char **pzTerm,            /* OUT: term (nul-terminated) */
  const char **ppDoclist,         /* OUT: pointer to doclist */
  int *pnDoclist                  /* OUT: size of doclist in bytes */
){
  Fts5HashEntry *p;
  if( (p = pHash->pScan) ){
    u8 *pPtr = (u8*)p;
    int nTerm = strlen(p->zKey);
    fts5Put4ByteVarint(&pPtr[p->iSzPoslist], p->nData - p->iSzPoslist - 4);
    *pzTerm = p->zKey;
    *ppDoclist = &p->zKey[nTerm+1];
    *pnDoclist = p->nData - (sizeof(*p) + nTerm + 1);
  }else{
    *pzTerm = 0;
    *ppDoclist = 0;
    *pnDoclist = 0;
  }
}

Changes to ext/fts5/fts5_index.c.

270
271
272
273
274
275
276

277
278
279
280
281
282
283
284
285
286
287






288
289
290
291
292
293
294
....
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
....
1770
1771
1772
1773
1774
1775
1776




















1777
1778
1779
1780
1781
1782
1783
....
2013
2014
2015
2016
2017
2018
2019




















































2020
2021
2022
2023
2024
2025
2026
....
2257
2258
2259
2260
2261
2262
2263

2264
2265
2266
2267
2268
2269
2270
....
2276
2277
2278
2279
2280
2281
2282





2283
2284
2285
2286
2287
2288
2289
....
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414






2415


2416
2417
2418
2419
2420
2421
2422
....
3096
3097
3098
3099
3100
3101
3102

3103
3104
3105
3106
3107
3108
3109
** without overreading if the records are corrupt.
*/
#define FTS5_DATA_ZERO_PADDING 8

typedef struct Fts5BtreeIter Fts5BtreeIter;
typedef struct Fts5BtreeIterLevel Fts5BtreeIterLevel;
typedef struct Fts5ChunkIter Fts5ChunkIter;

typedef struct Fts5DlidxIter Fts5DlidxIter;
typedef struct Fts5MultiSegIter Fts5MultiSegIter;
typedef struct Fts5NodeIter Fts5NodeIter;
typedef struct Fts5PageWriter Fts5PageWriter;
typedef struct Fts5PosIter Fts5PosIter;
typedef struct Fts5SegIter Fts5SegIter;
typedef struct Fts5DoclistIter Fts5DoclistIter;
typedef struct Fts5SegWriter Fts5SegWriter;
typedef struct Fts5Structure Fts5Structure;
typedef struct Fts5StructureLevel Fts5StructureLevel;
typedef struct Fts5StructureSegment Fts5StructureSegment;







/*
** One object per %_data table.
*/
struct Fts5Index {
  Fts5Config *pConfig;            /* Virtual table configuration */
  char *zDataTbl;                 /* Name of %_data table */
................................................................................
** Load the next leaf page into the segment iterator.
*/
static void fts5SegIterNextPage(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5SegIter *pIter              /* Iterator to advance to next page */
){
  Fts5StructureSegment *pSeg = pIter->pSeg;
  if( pIter->pLeaf ) fts5DataRelease(pIter->pLeaf);
  pIter->iLeafPgno++;
  if( pIter->iLeafPgno<=pSeg->pgnoLast ){
    pIter->pLeaf = fts5DataRead(p, 
        FTS5_SEGMENT_ROWID(pIter->iIdx, pSeg->iSegid, 0, pIter->iLeafPgno)
    );
  }else{
    pIter->pLeaf = 0;
................................................................................
            fts5SegIterNextPage(p, pIter);
            pIter->iLeafOffset = 4;
          }else if( iOff!=fts5GetU16(&a[2]) ){
            pIter->iLeafOffset += fts5GetVarint32(&a[iOff], nKeep);
          }
        }else{
          pIter->iRowid += iDelta;




















        }
      }else{
        iOff = 0;
        /* Next entry is not on the current page */
        while( iOff==0 ){
          fts5SegIterNextPage(p, pIter);
          pLeaf = pIter->pLeaf;
................................................................................
      }
      if( flags & FTS5INDEX_QUERY_DESC ){
        fts5SegIterReverse(p, iIdx, pIter);
      }
    }
  }
}





















































/*
** Zero the iterator passed as the only argument.
*/
static void fts5SegIterClear(Fts5SegIter *pIter){
  fts5BufferFree(&pIter->term);
  fts5DataRelease(pIter->pLeaf);
................................................................................
  Fts5MultiSegIter *pNew;

  assert( (pTerm==0 && nTerm==0) || iLevel<0 );

  /* Allocate space for the new multi-seg-iterator. */
  if( iLevel<0 ){
    nSeg = fts5StructureCountSegments(pStruct);

  }else{
    nSeg = MIN(pStruct->aLevel[iLevel].nSeg, nSegment);
  }
  for(nSlot=2; nSlot<nSeg; nSlot=nSlot*2);
  *ppOut = pNew = fts5IdxMalloc(p, 
      sizeof(Fts5MultiSegIter) +          /* pNew */
      sizeof(Fts5SegIter) * nSlot +       /* pNew->aSeg[] */
................................................................................
  pNew->aFirst = (u16*)&pNew->aSeg[nSlot];
  pNew->bRev = (0!=(flags & FTS5INDEX_QUERY_DESC));
  pNew->bSkipEmpty = bSkipEmpty;

  /* Initialize each of the component segment iterators. */
  if( iLevel<0 ){
    Fts5StructureLevel *pEnd = &pStruct->aLevel[pStruct->nLevel];





    for(pLvl=&pStruct->aLevel[0]; pLvl<pEnd; pLvl++){
      for(iSeg=pLvl->nSeg-1; iSeg>=0; iSeg--){
        Fts5StructureSegment *pSeg = &pLvl->aSeg[iSeg];
        Fts5SegIter *pIter = &pNew->aSeg[iIter++];
        if( pTerm==0 ){
          fts5SegIterInit(p, iIdx, pSeg, pIter);
        }else{
................................................................................
** the size field is at offset iOff of leaf pLeaf. 
*/
static void fts5ChunkIterInit(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5SegIter *pSeg,              /* Segment iterator to read poslist from */
  Fts5ChunkIter *pIter            /* Initialize this object */
){
  int iId = pSeg->pSeg->iSegid;
  i64 rowid = FTS5_SEGMENT_ROWID(pSeg->iIdx, iId, 0, pSeg->iLeafPgno);
  Fts5Data *pLeaf = pSeg->pLeaf;
  int iOff = pSeg->iLeafOffset;

  memset(pIter, 0, sizeof(*pIter));






  pIter->iLeafRowid = rowid;


  if( iOff<pLeaf->n ){
    fts5DataReference(pLeaf);
    pIter->pLeaf = pLeaf;
  }else{
    pIter->nRem = 1;
    fts5ChunkIterNext(p, pIter);
    if( p->rc ) return;
................................................................................
  bOldest = (pLvlOut->nSeg==1 && pStruct->nLevel==iLvl+2);

#if 0
fprintf(stdout, "merging %d segments from level %d!", nInput, iLvl);
fflush(stdout);
#endif


  for(fts5MultiIterNew(p, pStruct, iIdx, 0, 0, 0, 0, iLvl, nInput, &pIter);
      fts5MultiIterEof(p, pIter)==0;
      fts5MultiIterNext(p, pIter, 0, 0)
  ){
    Fts5SegIter *pSeg = &pIter->aSeg[ pIter->aFirst[1] ];
    Fts5ChunkIter sPos;           /* Used to iterate through position list */








>











>
>
>
>
>
>







 







|







 







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







 







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







 







>







 







>
>
>
>
>







 







<
<




>
>
>
>
>
>
|
>
>







 







>







270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
....
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
....
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
....
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
....
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
....
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
....
2487
2488
2489
2490
2491
2492
2493


2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
....
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
** without overreading if the records are corrupt.
*/
#define FTS5_DATA_ZERO_PADDING 8

typedef struct Fts5BtreeIter Fts5BtreeIter;
typedef struct Fts5BtreeIterLevel Fts5BtreeIterLevel;
typedef struct Fts5ChunkIter Fts5ChunkIter;
typedef struct Fts5Data Fts5Data;
typedef struct Fts5DlidxIter Fts5DlidxIter;
typedef struct Fts5MultiSegIter Fts5MultiSegIter;
typedef struct Fts5NodeIter Fts5NodeIter;
typedef struct Fts5PageWriter Fts5PageWriter;
typedef struct Fts5PosIter Fts5PosIter;
typedef struct Fts5SegIter Fts5SegIter;
typedef struct Fts5DoclistIter Fts5DoclistIter;
typedef struct Fts5SegWriter Fts5SegWriter;
typedef struct Fts5Structure Fts5Structure;
typedef struct Fts5StructureLevel Fts5StructureLevel;
typedef struct Fts5StructureSegment Fts5StructureSegment;

struct Fts5Data {
  u8 *p;                          /* Pointer to buffer containing record */
  int n;                          /* Size of record in bytes */
  int nRef;                       /* Ref count */
};

/*
** One object per %_data table.
*/
struct Fts5Index {
  Fts5Config *pConfig;            /* Virtual table configuration */
  char *zDataTbl;                 /* Name of %_data table */
................................................................................
** Load the next leaf page into the segment iterator.
*/
static void fts5SegIterNextPage(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5SegIter *pIter              /* Iterator to advance to next page */
){
  Fts5StructureSegment *pSeg = pIter->pSeg;
  fts5DataRelease(pIter->pLeaf);
  pIter->iLeafPgno++;
  if( pIter->iLeafPgno<=pSeg->pgnoLast ){
    pIter->pLeaf = fts5DataRead(p, 
        FTS5_SEGMENT_ROWID(pIter->iIdx, pSeg->iSegid, 0, pIter->iLeafPgno)
    );
  }else{
    pIter->pLeaf = 0;
................................................................................
            fts5SegIterNextPage(p, pIter);
            pIter->iLeafOffset = 4;
          }else if( iOff!=fts5GetU16(&a[2]) ){
            pIter->iLeafOffset += fts5GetVarint32(&a[iOff], nKeep);
          }
        }else{
          pIter->iRowid += iDelta;
        }
      }else if( pIter->pSeg==0 ){
        const char *pList = 0;
        const char *zTerm;
        int nList;
        if( 0==(pIter->flags & FTS5_SEGITER_ONETERM) ){
          sqlite3Fts5HashScanNext(p->apHash[0]);
          sqlite3Fts5HashScanEntry(p->apHash[0], &zTerm, &pList, &nList);
        }
        if( pList==0 ){
          fts5DataRelease(pIter->pLeaf);
          pIter->pLeaf = 0;
        }else{
          pIter->pLeaf->p = (u8*)pList;
          pIter->pLeaf->n = nList;
          sqlite3Fts5BufferSet(&p->rc, &pIter->term, strlen(zTerm), (u8*)zTerm);
          pIter->iLeafOffset = getVarint((u8*)pList, (u64*)&pIter->iRowid);
          if( pIter->flags & FTS5_SEGITER_REVERSE ){
            fts5SegIterReverseInitPage(p, pIter);
          }
        }
      }else{
        iOff = 0;
        /* Next entry is not on the current page */
        while( iOff==0 ){
          fts5SegIterNextPage(p, pIter);
          pLeaf = pIter->pLeaf;
................................................................................
      }
      if( flags & FTS5INDEX_QUERY_DESC ){
        fts5SegIterReverse(p, iIdx, pIter);
      }
    }
  }
}

/*
** Initialize the object pIter to point to term pTerm/nTerm within the
** in-memory hash table iIdx. If there is no such term in the table, the 
** iterator is set to EOF.
**
** If an error occurs, Fts5Index.rc is set to an appropriate error code. If 
** an error has already occurred when this function is called, it is a no-op.
*/
static void fts5SegIterHashInit(
  Fts5Index *p,                   /* FTS5 backend */
  int iIdx,                       /* Config.aHash[] index of FTS index */
  const u8 *pTerm, int nTerm,     /* Term to seek to */
  int flags,                      /* Mask of FTS5INDEX_XXX flags */
  Fts5SegIter *pIter              /* Object to populate */
){
  Fts5Hash *pHash = p->apHash[iIdx];
  const char *pList = 0;
  int nList = 0;
  const u8 *z = 0;
  int n = 0;

  assert( pHash );

  if( pTerm==0 || (iIdx==0 && (flags & FTS5INDEX_QUERY_PREFIX)) ){
    sqlite3Fts5HashScanInit(pHash, (const char*)pTerm, nTerm);
    sqlite3Fts5HashScanEntry(pHash, (const char**)&z, &pList, &nList);
    n = (z ? strlen((const char*)z) : 0);
  }else{
    pIter->flags |= FTS5_SEGITER_ONETERM;
    sqlite3Fts5HashQuery(pHash, (const char*)pTerm, nTerm, &pList, &nList);
    z = pTerm;
    n = nTerm;
  }

  if( pList ){
    Fts5Data *pLeaf;
    sqlite3Fts5BufferSet(&p->rc, &pIter->term, n, z);
    pLeaf = fts5IdxMalloc(p, sizeof(Fts5Data));
    if( pLeaf==0 ) return;
    pLeaf->nRef = 1;
    pLeaf->p = (u8*)pList;
    pLeaf->n = nList;
    pIter->pLeaf = pLeaf;
    pIter->iLeafOffset = getVarint(pLeaf->p, (u64*)&pIter->iRowid);

    if( flags & FTS5INDEX_QUERY_DESC ){
      pIter->flags |= FTS5_SEGITER_REVERSE;
      fts5SegIterReverseInitPage(p, pIter);
    }
  }
}

/*
** Zero the iterator passed as the only argument.
*/
static void fts5SegIterClear(Fts5SegIter *pIter){
  fts5BufferFree(&pIter->term);
  fts5DataRelease(pIter->pLeaf);
................................................................................
  Fts5MultiSegIter *pNew;

  assert( (pTerm==0 && nTerm==0) || iLevel<0 );

  /* Allocate space for the new multi-seg-iterator. */
  if( iLevel<0 ){
    nSeg = fts5StructureCountSegments(pStruct);
    nSeg += (p->apHash ? 1 : 0);
  }else{
    nSeg = MIN(pStruct->aLevel[iLevel].nSeg, nSegment);
  }
  for(nSlot=2; nSlot<nSeg; nSlot=nSlot*2);
  *ppOut = pNew = fts5IdxMalloc(p, 
      sizeof(Fts5MultiSegIter) +          /* pNew */
      sizeof(Fts5SegIter) * nSlot +       /* pNew->aSeg[] */
................................................................................
  pNew->aFirst = (u16*)&pNew->aSeg[nSlot];
  pNew->bRev = (0!=(flags & FTS5INDEX_QUERY_DESC));
  pNew->bSkipEmpty = bSkipEmpty;

  /* Initialize each of the component segment iterators. */
  if( iLevel<0 ){
    Fts5StructureLevel *pEnd = &pStruct->aLevel[pStruct->nLevel];
    if( p->apHash ){
      /* Add a segment iterator for the current contents of the hash table. */
      Fts5SegIter *pIter = &pNew->aSeg[iIter++];
      fts5SegIterHashInit(p, iIdx, pTerm, nTerm, flags, pIter);
    }
    for(pLvl=&pStruct->aLevel[0]; pLvl<pEnd; pLvl++){
      for(iSeg=pLvl->nSeg-1; iSeg>=0; iSeg--){
        Fts5StructureSegment *pSeg = &pLvl->aSeg[iSeg];
        Fts5SegIter *pIter = &pNew->aSeg[iIter++];
        if( pTerm==0 ){
          fts5SegIterInit(p, iIdx, pSeg, pIter);
        }else{
................................................................................
** the size field is at offset iOff of leaf pLeaf. 
*/
static void fts5ChunkIterInit(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5SegIter *pSeg,              /* Segment iterator to read poslist from */
  Fts5ChunkIter *pIter            /* Initialize this object */
){


  Fts5Data *pLeaf = pSeg->pLeaf;
  int iOff = pSeg->iLeafOffset;

  memset(pIter, 0, sizeof(*pIter));
  /* If Fts5SegIter.pSeg is NULL, then this iterator iterates through data
  ** currently stored in a hash table. In this case there is no leaf-rowid
  ** to calculate.  */
  if( pSeg->pSeg ){
    int iId = pSeg->pSeg->iSegid;
    i64 rowid = FTS5_SEGMENT_ROWID(pSeg->iIdx, iId, 0, pSeg->iLeafPgno);
    pIter->iLeafRowid = rowid;
  }

  if( iOff<pLeaf->n ){
    fts5DataReference(pLeaf);
    pIter->pLeaf = pLeaf;
  }else{
    pIter->nRem = 1;
    fts5ChunkIterNext(p, pIter);
    if( p->rc ) return;
................................................................................
  bOldest = (pLvlOut->nSeg==1 && pStruct->nLevel==iLvl+2);

#if 0
fprintf(stdout, "merging %d segments from level %d!", nInput, iLvl);
fflush(stdout);
#endif

  assert( iLvl>=0 );
  for(fts5MultiIterNew(p, pStruct, iIdx, 0, 0, 0, 0, iLvl, nInput, &pIter);
      fts5MultiIterEof(p, pIter)==0;
      fts5MultiIterNext(p, pIter, 0, 0)
  ){
    Fts5SegIter *pSeg = &pIter->aSeg[ pIter->aFirst[1] ];
    Fts5ChunkIter sPos;           /* Used to iterate through position list */

Changes to ext/fts5/test/fts5ab.test.

243
244
245
246
247
248
249
250
251




252
253
254
255



256
257
258
259
260
do_execsql_test 6.0 {
  CREATE VIRTUAL TABLE s3 USING fts5(x);
  BEGIN;
    INSERT INTO s3 VALUES('a b c');
    INSERT INTO s3 VALUES('A B C');
}

do_execsql_test 6.1 {
  SELECT rowid FROM s3 WHERE s3 MATCH 'a'




} {2 1}

do_execsql_test 6.2 {
  COMMIT;



  SELECT rowid FROM s3 WHERE s3 MATCH 'a'
} {2 1}

finish_test








|

>
>
>
>




>
>
>

|



243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
do_execsql_test 6.0 {
  CREATE VIRTUAL TABLE s3 USING fts5(x);
  BEGIN;
    INSERT INTO s3 VALUES('a b c');
    INSERT INTO s3 VALUES('A B C');
}

do_execsql_test 6.1.1 {
  SELECT rowid FROM s3 WHERE s3 MATCH 'a'
} {1 2}

do_execsql_test 6.1.2 {
  SELECT rowid FROM s3 WHERE s3 MATCH 'a' ORDER BY rowid DESC
} {2 1}

do_execsql_test 6.2 {
  COMMIT;
}

do_execsql_test 6.3 {
  SELECT rowid FROM s3 WHERE s3 MATCH 'a'
} {1 2}

finish_test

Changes to ext/fts5/test/fts5ac.test.

18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
...
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
...
298
299
300
301
302
303
304






305
306



307










308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418







































419
420
421
422
423
424
425
426
427
428
429
430
431
432

433
434
435
436
437

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

do_execsql_test 1.0 {
  CREATE VIRTUAL TABLE xx USING fts5(x,y);
  INSERT INTO xx(xx, rank) VALUES('pgsz', 32);
}

set data {
    0   {p o q e z k z p n f y u z y n y}   {l o o l v v k}
    1   {p k h h p y l l h i p v n}         {p p l u r i f a j g e r r x w}
    2   {l s z j k i m p s}                 {l w e j t j e e i t w r o p o}
    3   {x g y m y m h p}                   {k j j b r e y y a k y}
    4   {q m a i y i z}                     {o w a g k x g j m w e u k}
    5   {k o a w y b s z}                   {s g l m m l m g p}
................................................................................
    95  {h b n j t k i h o q u}             {w n g i t o k c a m y p f l x c p}
    96  {f c x p y r b m o l m o a}         {p c a q s u n n x d c f a o}
    97  {u h h k m n k}                     {u b v n u a o c}
    98  {s p e t c z d f n w f}             {l s f j b l c e s h}
    99  {r c v w i v h a t a c v c r e}     {h h u m g o f b a e o}
}

do_test 1.1 {
  foreach {id x y} $data {
    execsql { INSERT INTO xx(rowid, x, y) VALUES($id, $x, $y) }
  }
  execsql { INSERT INTO xx(xx) VALUES('integrity-check') }
} {}

# Usage:
#
#   poslist aCol ?-pc VARNAME? ?-near N? ?-col C? -- phrase1 phrase2...
#
proc poslist {aCol args} {
  set O(-near) 10
  set O(-col)  -1
................................................................................
  set res [list]
  for {set i 0} {$i < [$cmd xInstCount]} {incr i} {
    lappend res [string map {{ } .} [$cmd xInst $i]]
  }
  set res
}







sqlite3_fts5_create_function db fts5_test_poslist fts5_test_poslist















#-------------------------------------------------------------------------
# Test phrase queries.
#
foreach {tn phrase} {
  1 "o"
  2 "b q"
  3 "e a e"
  4 "m d g q q b k b w f q q p p"
  5 "l o o l v v k"
  6 "a"
  7 "b"
  8 "c"
  9 "no"
  10 "L O O L V V K"
} {
  set expr "\"$phrase\""
  set res [matchdata 1 $expr]

  do_execsql_test 1.2.$tn.[llength $res] { 
    SELECT rowid, fts5_test_poslist(xx) FROM xx WHERE xx match $expr
  } $res
}

#-------------------------------------------------------------------------
# Test some AND and OR queries.
#
foreach {tn expr} {
  1.1 "a   AND b"
  1.2 "a+b AND c"
  1.3 "d+c AND u"
  1.4 "d+c AND u+d"

  2.1 "a   OR b"
  2.2 "a+b OR c"
  2.3 "d+c OR u"
  2.4 "d+c OR u+d"

  3.1 { a AND b AND c }
} {
  set res [matchdata 1 $expr]
  do_execsql_test 2.$tn.[llength $res] { 
    SELECT rowid, fts5_test_poslist(xx) FROM xx WHERE xx match $expr
  } $res
}

#-------------------------------------------------------------------------
# Queries on a specific column.
#
foreach {tn expr} {
  1 "x:a"
  2 "y:a"
  3 "x:b"
  4 "y:b"
} {
  set res [matchdata 1 $expr]
  do_execsql_test 3.$tn.[llength $res] { 
    SELECT rowid, fts5_test_poslist(xx) FROM xx WHERE xx match $expr
  } $res
}

#-------------------------------------------------------------------------
# Some NEAR queries.
#
foreach {tn expr} {
  1 "NEAR(a b)"
  2 "NEAR(r c)"
  2 { NEAR(r c, 5) }
  3 { NEAR(r c, 3) }
  4 { NEAR(r c, 2) }
  5 { NEAR(r c, 0) }
  6 { NEAR(a b c) }
  7 { NEAR(a b c, 8) }
  8  { x : NEAR(r c) }
  9  { y : NEAR(r c) }
} {
  set res [matchdata 1 $expr]
  do_execsql_test 4.1.$tn.[llength $res] { 
    SELECT rowid, fts5_test_poslist(xx) FROM xx WHERE xx match $expr
  } $res
}

do_test 4.1  { poslist {{a b c}} -- a } {0.0.0}
do_test 4.2  { poslist {{a b c}} -- c } {0.0.2}

foreach {tn expr tclexpr} {
  1 {a b} {[N $x -- {a}] && [N $x -- {b}]}
} {
  do_execsql_test 5.$tn {SELECT fts5_expr_tcl($expr, 'N $x')} [list $tclexpr]
}

#-------------------------------------------------------------------------
#
do_execsql_test 6.integrity {
  INSERT INTO xx(xx) VALUES('integrity-check');
}
#db eval {SELECT rowid, fts5_decode(rowid, block) aS r FROM xx_data} {puts $r}
foreach {bAsc sql} {
  1 {SELECT rowid FROM xx WHERE xx MATCH $expr}
  0 {SELECT rowid FROM xx WHERE xx MATCH $expr ORDER BY rowid DESC}
} {
  foreach {tn expr} {
    0.1 x
    1 { NEAR(r c) }
    2 { NEAR(r c, 5) }
    3 { NEAR(r c, 3) }
    4 { NEAR(r c, 2) }
    5 { NEAR(r c, 0) }
    6 { NEAR(a b c) }
    7 { NEAR(a b c, 8) }
    8  { x : NEAR(r c) }
    9  { y : NEAR(r c) }







































    10 { x : "r c" }
    11 { y : "r c" }
    12 { a AND b }
    13 { a AND b AND c }
    14a { a }
    14b { a OR b }
    15 { a OR b AND c }
    16 { c AND b OR a }
    17 { c AND (b OR a) }
    18 { c NOT (b OR a) }
    19 { c NOT b OR a AND d }
  } {
    set res [matchdata 0 $expr $bAsc]
    do_execsql_test 6.$bAsc.$tn.[llength $res] $sql $res

  }
}

finish_test








<
<
<
<
<







 







<
<
<
<
<
<
<







 







>
>
>
>
>
>
|

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

|
|
|
|

|
|
|
|
|
|
|
|

|
|
|
|

|
|
|
|
|
|
|

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

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








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





18
19
20
21
22
23
24





25
26
27
28
29
30
31
...
121
122
123
124
125
126
127







128
129
130
131
132
133
134
...
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380





































381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447

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






set data {
    0   {p o q e z k z p n f y u z y n y}   {l o o l v v k}
    1   {p k h h p y l l h i p v n}         {p p l u r i f a j g e r r x w}
    2   {l s z j k i m p s}                 {l w e j t j e e i t w r o p o}
    3   {x g y m y m h p}                   {k j j b r e y y a k y}
    4   {q m a i y i z}                     {o w a g k x g j m w e u k}
    5   {k o a w y b s z}                   {s g l m m l m g p}
................................................................................
    95  {h b n j t k i h o q u}             {w n g i t o k c a m y p f l x c p}
    96  {f c x p y r b m o l m o a}         {p c a q s u n n x d c f a o}
    97  {u h h k m n k}                     {u b v n u a o c}
    98  {s p e t c z d f n w f}             {l s f j b l c e s h}
    99  {r c v w i v h a t a c v c r e}     {h h u m g o f b a e o}
}








# Usage:
#
#   poslist aCol ?-pc VARNAME? ?-near N? ?-col C? -- phrase1 phrase2...
#
proc poslist {aCol args} {
  set O(-near) 10
  set O(-col)  -1
................................................................................
  set res [list]
  for {set i 0} {$i < [$cmd xInstCount]} {incr i} {
    lappend res [string map {{ } .} [$cmd xInst $i]]
  }
  set res
}


foreach {tn2 sql} {
  1  {}
  2  {BEGIN}
} {
  reset_db
  sqlite3_fts5_create_function db fts5_test_poslist fts5_test_poslist

  do_execsql_test 1.0 {
    CREATE VIRTUAL TABLE xx USING fts5(x,y);
    INSERT INTO xx(xx, rank) VALUES('pgsz', 32);
  }

  execsql $sql

  do_test $tn2.1.1 {
    foreach {id x y} $data {
      execsql { INSERT INTO xx(rowid, x, y) VALUES($id, $x, $y) }
    }
    execsql { INSERT INTO xx(xx) VALUES('integrity-check') }
  } {}

  #-------------------------------------------------------------------------
  # Test phrase queries.
  #
  foreach {tn phrase} {
    1 "o"
    2 "b q"
    3 "e a e"
    4 "m d g q q b k b w f q q p p"
    5 "l o o l v v k"
    6 "a"
    7 "b"
    8 "c"
    9 "no"
    10 "L O O L V V K"
  } {
    set expr "\"$phrase\""
    set res [matchdata 1 $expr]

    do_execsql_test $tn2.1.2.$tn.[llength $res] { 
      SELECT rowid, fts5_test_poslist(xx) FROM xx WHERE xx match $expr
    } $res
  }

  #-------------------------------------------------------------------------
  # Test some AND and OR queries.
  #
  foreach {tn expr} {
    1.1 "a   AND b"
    1.2 "a+b AND c"
    1.3 "d+c AND u"
    1.4 "d+c AND u+d"

    2.1 "a   OR b"
    2.2 "a+b OR c"
    2.3 "d+c OR u"
    2.4 "d+c OR u+d"

    3.1 { a AND b AND c }
  } {
    set res [matchdata 1 $expr]
    do_execsql_test $tn2.2.$tn.[llength $res] { 
      SELECT rowid, fts5_test_poslist(xx) FROM xx WHERE xx match $expr
    } $res
  }

  #-------------------------------------------------------------------------
  # Queries on a specific column.
  #
  foreach {tn expr} {
    1 "x:a"
    2 "y:a"
    3 "x:b"
    4 "y:b"
  } {
    set res [matchdata 1 $expr]
    do_execsql_test $tn2.3.$tn.[llength $res] { 
      SELECT rowid, fts5_test_poslist(xx) FROM xx WHERE xx match $expr
    } $res
  }

  #-------------------------------------------------------------------------
  # Some NEAR queries.
  #
  foreach {tn expr} {
    1 "NEAR(a b)"
    2 "NEAR(r c)"





































    2 { NEAR(r c, 5) }
    3 { NEAR(r c, 3) }
    4 { NEAR(r c, 2) }
    5 { NEAR(r c, 0) }
    6 { NEAR(a b c) }
    7 { NEAR(a b c, 8) }
    8  { x : NEAR(r c) }
    9  { y : NEAR(r c) }
  } {
    set res [matchdata 1 $expr]
    do_execsql_test $tn2.4.1.$tn.[llength $res] { 
      SELECT rowid, fts5_test_poslist(xx) FROM xx WHERE xx match $expr
    } $res
  }

  do_test $tn2.4.1  { poslist {{a b c}} -- a } {0.0.0}
  do_test $tn2.4.2  { poslist {{a b c}} -- c } {0.0.2}

  foreach {tn expr tclexpr} {
    1 {a b} {[N $x -- {a}] && [N $x -- {b}]}
  } {
    do_execsql_test $tn2.5.$tn {
      SELECT fts5_expr_tcl($expr, 'N $x')
    } [list $tclexpr]
  }

  #-------------------------------------------------------------------------
  #
  do_execsql_test $tn2.6.integrity {
    INSERT INTO xx(xx) VALUES('integrity-check');
  }
  #db eval {SELECT rowid, fts5_decode(rowid, block) aS r FROM xx_data} {puts $r}
  foreach {bAsc sql} {
    1 {SELECT rowid FROM xx WHERE xx MATCH $expr}
    0 {SELECT rowid FROM xx WHERE xx MATCH $expr ORDER BY rowid DESC}
  } {
    foreach {tn expr} {
      0.1 x
      1 { NEAR(r c) }
      2 { NEAR(r c, 5) }
      3 { NEAR(r c, 3) }
      4 { NEAR(r c, 2) }
      5 { NEAR(r c, 0) }
      6 { NEAR(a b c) }
      7 { NEAR(a b c, 8) }
      8  { x : NEAR(r c) }
      9  { y : NEAR(r c) }
      10 { x : "r c" }
      11 { y : "r c" }
      12 { a AND b }
      13 { a AND b AND c }
      14a { a }
      14b { a OR b }
      15 { a OR b AND c }
      16 { c AND b OR a }
      17 { c AND (b OR a) }
      18 { c NOT (b OR a) }
      19 { c NOT b OR a AND d }
    } {
      set res [matchdata 0 $expr $bAsc]
      do_execsql_test $tn2.6.$bAsc.$tn.[llength $res] $sql $res
    }
  }
}

finish_test

Changes to ext/fts5/test/fts5ad.test.

58
59
60
61
62
63
64












65
66
67
68
69
70
71
...
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
...
207
208
209
210
211
212
213

214
215
216


217
218
219
220
  }
  
  3 {
    CREATE VIRTUAL TABLE t1 USING fts5(a, b, prefix=1,2,3,4,5);
    INSERT INTO t1(t1, rank) VALUES('pgsz', 32);
  }













} {

  do_test $T.1 { 
    execsql { DROP TABLE IF EXISTS t1 }
    execsql $create
  } {}
  
................................................................................
      }
      if {$bMatch} { lappend ret $rowid }
    }
    return $ret
  }
  
  foreach {bAsc sql} {
    1 {SELECT rowid FROM t1 WHERE t1 MATCH $prefix}
    0 {SELECT rowid FROM t1 WHERE t1 MATCH $prefix ORDER BY rowid DESC}
  } {
    foreach {tn prefix} {
      1  {a*} 2 {ab*} 3 {abc*} 4 {abcd*} 5 {abcde*} 
      6  {f*} 7 {fg*} 8 {fgh*} 9 {fghi*} 10 {fghij*}
      11 {k*} 12 {kl*} 13 {klm*} 14 {klmn*} 15 {klmno*}
      16 {p*} 17 {pq*} 18 {pqr*} 19 {pqrs*} 20 {pqrst*}
      21 {u*} 22 {uv*} 23 {uvw*} 24 {uvwx*} 25 {uvwxy*} 26 {uvwxyz*}
................................................................................
      28 {a f*} 29 {a* f*} 30 {a* fghij*}
    } {
      set res [prefix_query $prefix]
      if {$bAsc} {
        set res [lsort -integer -increasing $res]
      }
      set n [llength $res]

      do_execsql_test $T.$bAsc.$tn.$n $sql $res
    }
  }


}

finish_test








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







 







|
|







 







>



>
>




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
...
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
...
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
  }
  
  3 {
    CREATE VIRTUAL TABLE t1 USING fts5(a, b, prefix=1,2,3,4,5);
    INSERT INTO t1(t1, rank) VALUES('pgsz', 32);
  }

  4 {
    CREATE VIRTUAL TABLE t1 USING fts5(a, b);
    INSERT INTO t1(t1, rank) VALUES('pgsz', 32);
    BEGIN;
  }
  
  5 {
    CREATE VIRTUAL TABLE t1 USING fts5(a, b, prefix=1,2,3,4,5);
    INSERT INTO t1(t1, rank) VALUES('pgsz', 32);
    BEGIN;
  }

} {

  do_test $T.1 { 
    execsql { DROP TABLE IF EXISTS t1 }
    execsql $create
  } {}
  
................................................................................
      }
      if {$bMatch} { lappend ret $rowid }
    }
    return $ret
  }
  
  foreach {bAsc sql} {
    0 {SELECT rowid FROM t1 WHERE t1 MATCH $prefix ORDER BY rowid DESC}
    1 {SELECT rowid FROM t1 WHERE t1 MATCH $prefix}
  } {
    foreach {tn prefix} {
      1  {a*} 2 {ab*} 3 {abc*} 4 {abcd*} 5 {abcde*} 
      6  {f*} 7 {fg*} 8 {fgh*} 9 {fghi*} 10 {fghij*}
      11 {k*} 12 {kl*} 13 {klm*} 14 {klmn*} 15 {klmno*}
      16 {p*} 17 {pq*} 18 {pqr*} 19 {pqrs*} 20 {pqrst*}
      21 {u*} 22 {uv*} 23 {uvw*} 24 {uvwx*} 25 {uvwxy*} 26 {uvwxyz*}
................................................................................
      28 {a f*} 29 {a* f*} 30 {a* fghij*}
    } {
      set res [prefix_query $prefix]
      if {$bAsc} {
        set res [lsort -integer -increasing $res]
      }
      set n [llength $res]
      if {$T==5} breakpoint 
      do_execsql_test $T.$bAsc.$tn.$n $sql $res
    }
  }

  catchsql COMMIT
}

finish_test