/ Check-in [bdc58fd2]
Login

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

Overview
Comment:Add a snippet() function to fts5.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | fts5
Files: files | file ages | folders
SHA1: bdc58fd28a63ac9632c3df6c7768a9a236566605
User & Date: dan 2014-07-23 19:31:56
Context
2014-07-25
20:30
Add extension apis xRowCount, xQueryPhrase, xSetAuxdata and xGetAuxdata. And a ranking function that uses all of the above. check-in: c4d50428 user: dan tags: fts5
2014-07-23
19:31
Add a snippet() function to fts5. check-in: bdc58fd2 user: dan tags: fts5
2014-07-21
15:45
Fix DELETE and UPDATE operations on fts5 tables. check-in: d44d3a85 user: dan tags: fts5
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/fts5/fts5.c.

682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
  return rc;
}

static int fts5ApiPoslist(
  Fts5Context *pCtx, 
  int iPhrase, 
  int *pi, 
  int *piCol, 
  int *piOff
){
  Fts5Cursor *pCsr = (Fts5Cursor*)pCtx;
  const u8 *a; int n;             /* Poslist for phrase iPhrase */
  n = sqlite3Fts5ExprPoslist(pCsr->pExpr, iPhrase, &a);
  return sqlite3Fts5PoslistNext(a, n, pi, piCol, piOff);
}

static void fts5ApiCallback(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){







|
<




|







682
683
684
685
686
687
688
689

690
691
692
693
694
695
696
697
698
699
700
701
  return rc;
}

static int fts5ApiPoslist(
  Fts5Context *pCtx, 
  int iPhrase, 
  int *pi, 
  i64 *piPos 

){
  Fts5Cursor *pCsr = (Fts5Cursor*)pCtx;
  const u8 *a; int n;             /* Poslist for phrase iPhrase */
  n = sqlite3Fts5ExprPoslist(pCsr->pExpr, iPhrase, &a);
  return sqlite3Fts5PoslistNext64(a, n, pi, piPos);
}

static void fts5ApiCallback(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){

Changes to ext/fts5/fts5.h.

65
66
67
68
69
70
71


72
73
74
75
76
77
78
..
87
88
89
90
91
92
93
94
95
96



97
98
99
100
101
**
** xRowid:
**   Returns the rowid of the current row.
**
** xPoslist:
**   Iterate through instances of phrase iPhrase in the current row. 
**


** xTokenize:
**   Tokenize text using the tokenizer belonging to the FTS5 table.
*/
struct Fts5ExtensionApi {
  int iVersion;                   /* Currently always set to 1 */

  void *(*xUserData)(Fts5Context*);
................................................................................

  int (*xPhraseCount)(Fts5Context*);
  int (*xPhraseSize)(Fts5Context*, int iPhrase);

  sqlite3_int64 (*xRowid)(Fts5Context*);
  int (*xColumnText)(Fts5Context*, int iCol, const char **pz, int *pn);
  int (*xColumnSize)(Fts5Context*, int iCol, int *pnToken);
  int (*xPoslist)(Fts5Context*, int iPhrase, int *pi, int *piCol, int *piOff);
};




/* 
** CUSTOM AUXILIARY FUNCTIONS
*************************************************************************/
#endif /* _FTS5_H */








>
>







 







|


>
>
>





65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
..
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
**
** xRowid:
**   Returns the rowid of the current row.
**
** xPoslist:
**   Iterate through instances of phrase iPhrase in the current row. 
**
**   At EOF, a non-zero value is returned and output variable iPos set to -1.
**
** xTokenize:
**   Tokenize text using the tokenizer belonging to the FTS5 table.
*/
struct Fts5ExtensionApi {
  int iVersion;                   /* Currently always set to 1 */

  void *(*xUserData)(Fts5Context*);
................................................................................

  int (*xPhraseCount)(Fts5Context*);
  int (*xPhraseSize)(Fts5Context*, int iPhrase);

  sqlite3_int64 (*xRowid)(Fts5Context*);
  int (*xColumnText)(Fts5Context*, int iCol, const char **pz, int *pn);
  int (*xColumnSize)(Fts5Context*, int iCol, int *pnToken);
  int (*xPoslist)(Fts5Context*, int iPhrase, int *pi, sqlite3_int64 *piPos);
};

#define FTS5_POS2COLUMN(iPos) (int)(iPos >> 32)
#define FTS5_POS2OFFSET(iPos) (int)(iPos & 0xFFFFFFFF)

/* 
** CUSTOM AUXILIARY FUNCTIONS
*************************************************************************/
#endif /* _FTS5_H */

Changes to ext/fts5/fts5_aux.c.

9
10
11
12
13
14
15






















































































































































































































































































































































16



























































17
18
19
20
21
22
23
...
142
143
144
145
146
147
148
149
150
151
152
153
154


155
156
157
158
159
160
161
**    May you share freely, never taking more than you give.
**
******************************************************************************
*/

#include "fts5Int.h"























































































































































































































































































































































static void fts5SnippetFunction(



























































  const Fts5ExtensionApi *pApi,   /* API offered by current FTS version */
  Fts5Context *pFts,              /* First arg to pass to pApi functions */
  sqlite3_context *pCtx,          /* Context for returning result/error */
  int nVal,                       /* Number of values in apVal[] array */
  sqlite3_value **apVal           /* Array of trailing arguments */
){
  assert( 0 );
................................................................................
    Fts5Buffer s3;
    memset(&s3, 0, sizeof(s3));


    for(i=0; i<nPhrase; i++){
      Fts5Buffer s2;                  /* List of positions for phrase/column */
      int j = 0;
      int iOff = 0;
      int iCol = 0;
      int nElem = 0;

      memset(&s2, 0, sizeof(s2));
      while( 0==pApi->xPoslist(pFts, i, &j, &iCol, &iOff) ){


        if( nElem!=0 ) sqlite3Fts5BufferAppendPrintf(&rc, &s2, " ");
        sqlite3Fts5BufferAppendPrintf(&rc, &s2, "%d.%d", iCol, iOff);
        nElem++;
      }

      if( i!=0 ){
        sqlite3Fts5BufferAppendPrintf(&rc, &s3, " ");







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

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







 







|
<



|
>
>







9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
...
543
544
545
546
547
548
549
550

551
552
553
554
555
556
557
558
559
560
561
562
563
**    May you share freely, never taking more than you give.
**
******************************************************************************
*/

#include "fts5Int.h"

typedef struct SnippetPhrase SnippetPhrase;
typedef struct SnippetIter SnippetIter;
typedef struct SnippetCtx SnippetCtx;

struct SnippetPhrase {
  u64 mask;                       /* Current mask */
  int nToken;                     /* Tokens in this phrase */
  int i;                          /* Current offset in phrase poslist */
  i64 iPos;                       /* Next position in phrase (-ve -> EOF) */
};

struct SnippetIter {
  i64 iLast;                      /* Last token position of current snippet */
  int nScore;                     /* Score of current snippet */

  const Fts5ExtensionApi *pApi;
  Fts5Context *pFts;
  u64 szmask;                     /* Mask used to on SnippetPhrase.mask */
  int nPhrase;                    /* Number of phrases */
  SnippetPhrase aPhrase[0];       /* Array of size nPhrase */
};

struct SnippetCtx {
  int iFirst;                     /* Offset of first token to record */
  int nToken;                     /* Size of aiStart[] and aiEnd[] arrays */
  int iSeen;                      /* Set to largest offset seen */
  int *aiStart; 
  int *aiEnd;
};

static int fts5SnippetCallback(
  void *pContext,                 /* Pointer to Fts5Buffer object */
  const char *pToken,             /* Buffer containing token */
  int nToken,                     /* Size of token in bytes */
  int iStart,                     /* Start offset of token */
  int iEnd,                       /* End offset of token */
  int iPos                        /* Position offset of token */
){
  int rc = SQLITE_OK;
  SnippetCtx *pCtx = (SnippetCtx*)pContext;
  int iOff = iPos - pCtx->iFirst;

  if( iOff>=0 ){
    if( iOff < pCtx->nToken ){
      pCtx->aiStart[iOff] = iStart;
      pCtx->aiEnd[iOff] = iEnd;
    }
    pCtx->iSeen = iPos;
    if( iOff>=pCtx->nToken ) rc = SQLITE_DONE;
  }

  return rc;
}

/*
** Set pIter->nScore to the score for the current entry.
*/
static void fts5SnippetCalculateScore(SnippetIter *pIter){
  int i;
  int nScore = 0;
  assert( pIter->iLast>=0 );

  for(i=0; i<pIter->nPhrase; i++){
    SnippetPhrase *p = &pIter->aPhrase[i];
    u64 mask = p->mask;
    if( mask ){
      u64 j;
      nScore += 1000;
      for(j=1; j & pIter->szmask; j<<=1){
        if( mask & j ) nScore++;
      }
    }
  }

  pIter->nScore = nScore;
}

/*
** Allocate a new snippet iter.
*/
static int fts5SnippetIterNew(
  const Fts5ExtensionApi *pApi,   /* API offered by current FTS version */
  Fts5Context *pFts,              /* First arg to pass to pApi functions */
  int nToken,                     /* Number of tokens in snippets */
  SnippetIter **ppIter            /* OUT: New object */
){
  int i;                          /* Counter variable */
  SnippetIter *pIter;             /* New iterator object */
  int nByte;                      /* Bytes of space to allocate */
  int nPhrase;                    /* Number of phrases in query */

  *ppIter = 0;
  nPhrase = pApi->xPhraseCount(pFts);
  nByte = sizeof(SnippetIter) + nPhrase * sizeof(SnippetPhrase);
  pIter = (SnippetIter*)sqlite3_malloc(nByte);
  if( pIter==0 ) return SQLITE_NOMEM;
  memset(pIter, 0, nByte);

  pIter->nPhrase = nPhrase;
  pIter->pApi = pApi;
  pIter->pFts = pFts;
  pIter->szmask = ((u64)1 << nToken) - 1;
  assert( nToken<=63 );

  for(i=0; i<nPhrase; i++){
    pIter->aPhrase[i].nToken = pApi->xPhraseSize(pFts, i);
  }

  *ppIter = pIter;
  return SQLITE_OK;
}

/*
** Set the iterator to point to the first candidate snippet.
*/
static void fts5SnippetIterFirst(SnippetIter *pIter){
  const Fts5ExtensionApi *pApi = pIter->pApi;
  Fts5Context *pFts = pIter->pFts;
  int i;                          /* Used to iterate through phrases */
  SnippetPhrase *pMin = 0;        /* Phrase with first match */

  memset(pIter->aPhrase, 0, sizeof(SnippetPhrase) * pIter->nPhrase);

  for(i=0; i<pIter->nPhrase; i++){
    SnippetPhrase *p = &pIter->aPhrase[i];
    p->nToken = pApi->xPhraseSize(pFts, i);
    pApi->xPoslist(pFts, i, &p->i, &p->iPos);
    if( p->iPos>=0 && (pMin==0 || p->iPos<pMin->iPos) ){
      pMin = p;
    }
  }
  assert( pMin );

  pIter->iLast = pMin->iPos + pMin->nToken - 1;
  pMin->mask = 0x01;
  pApi->xPoslist(pFts, pMin - pIter->aPhrase, &pMin->i, &pMin->iPos);
  fts5SnippetCalculateScore(pIter);
}

/*
** Advance the snippet iterator to the next candidate snippet.
*/
static void fts5SnippetIterNext(SnippetIter *pIter){
  const Fts5ExtensionApi *pApi = pIter->pApi;
  Fts5Context *pFts = pIter->pFts;
  int nPhrase = pIter->nPhrase;
  int i;                          /* Used to iterate through phrases */
  SnippetPhrase *pMin = 0;

  for(i=0; i<nPhrase; i++){
    SnippetPhrase *p = &pIter->aPhrase[i];
    if( p->iPos>=0 && (pMin==0 || p->iPos<pMin->iPos) ) pMin = p;
  }

  if( pMin==0 ){
    /* pMin==0 indicates that the SnippetIter is at EOF. */
    pIter->iLast = -1;
  }else{
    i64 nShift = pMin->iPos - pIter->iLast;
    assert( nShift>=0 );
    for(i=0; i<nPhrase; i++){
      SnippetPhrase *p = &pIter->aPhrase[i];
      if( nShift>=63 ){
        p->mask = 0;
      }else{
        p->mask = p->mask << (int)nShift;
        p->mask &= pIter->szmask;
      }
    }

    pIter->iLast = pMin->iPos;
    pMin->mask |= 0x01;
    fts5SnippetCalculateScore(pIter);
    pApi->xPoslist(pFts, pMin - pIter->aPhrase, &pMin->i, &pMin->iPos);
  }
}

static void fts5SnippetIterFree(SnippetIter *pIter){
  if( pIter ){
    sqlite3_free(pIter);
  }
}

static int fts5SnippetText(
  const Fts5ExtensionApi *pApi,   /* API offered by current FTS version */
  Fts5Context *pFts,              /* First arg to pass to pApi functions */
  SnippetIter *pIter,             /* Snippet to write to buffer */
  int nToken,                     /* Size of desired snippet in tokens */
  const char *zStart,
  const char *zFinal,
  const char *zEllip,
  Fts5Buffer *pBuf                /* Write output to this buffer */
){
  SnippetCtx ctx;
  int i;
  u64 all = 0;
  const char *zCol;               /* Column text to extract snippet from */
  int nCol;                       /* Size of column text in bytes */
  int rc;
  int nShift;

  rc = pApi->xColumnText(pFts, FTS5_POS2COLUMN(pIter->iLast), &zCol, &nCol);
  if( rc!=SQLITE_OK ) return rc;

  /* At this point pIter->iLast is the offset of the last token in the
  ** proposed snippet. However, in all cases pIter->iLast contains the
  ** final token of one of the phrases. This makes the snippet look
  ** unbalanced. For example:
  **
  **     "...x x x x x <b>term</b>..."
  **
  ** It is better to increase iLast a little so that the snippet looks
  ** more like:
  **
  **     "...x x x <b>term</b> y y..."
  **
  ** The problem is that there is no easy way to discover whether or not
  ** how many tokens are present in the column following "term". 
  */

  /* Set variable nShift to the number of tokens by which the snippet
  ** should be shifted, assuming there are sufficient tokens to the right
  ** of iLast in the column value.  */
  for(i=0; i<pIter->nPhrase; i++){
    int iToken;
    for(iToken=0; iToken<pIter->aPhrase[i].nToken; iToken++){
      all |= (pIter->aPhrase[i].mask << iToken);
    }
  }
  for(i=nToken-1; i>=0; i--){
    if( all & ((u64)1 << i) ) break;
  }
  assert( i>=0 );
  nShift = (nToken - i) / 2;

  memset(&ctx, 0, sizeof(SnippetCtx));
  ctx.nToken = nToken + nShift;
  ctx.iFirst = FTS5_POS2OFFSET(pIter->iLast) - nToken + 1;
  if( ctx.iFirst<0 ){
    nShift += ctx.iFirst;
    if( nShift<0 ) nShift = 0;
    ctx.iFirst = 0;
  }
  ctx.aiStart = (int*)sqlite3_malloc(sizeof(int) * ctx.nToken * 2);
  if( ctx.aiStart==0 ) return SQLITE_NOMEM;
  ctx.aiEnd = &ctx.aiStart[ctx.nToken];

  rc = pApi->xTokenize(pFts, zCol, nCol, (void*)&ctx, fts5SnippetCallback);
  if( rc==SQLITE_OK ){
    int i1;                       /* First token from input to include */
    int i2;                       /* Last token from input to include */

    int iPrint;
    int iMatchto;
    int iBit0;
    int iLast;

    int *aiStart = ctx.aiStart - ctx.iFirst;
    int *aiEnd = ctx.aiEnd - ctx.iFirst;

    /* Ideally we want to start the snippet with token (ctx.iFirst + nShift).
    ** However, this is only possible if there are sufficient tokens within
    ** the column. This block sets variables i1 and i2 to the first and last
    ** input tokens to include in the snippet.  */
    if( (ctx.iFirst + nShift + nToken)<=ctx.iSeen ){
      i1 = ctx.iFirst + nShift;
      i2 = i1 + nToken - 1;
    }else{
      i2 = ctx.iSeen;
      i1 = ctx.iSeen - nToken + 1;
      assert( i1>=0 || ctx.iFirst==0 );
      if( i1<0 ) i1 = 0;
    }

    /* If required, append the preceding ellipsis. */
    if( i1>0 ) sqlite3Fts5BufferAppendPrintf(&rc, pBuf, "%s", zEllip);

    iLast = FTS5_POS2OFFSET(pIter->iLast);
    iPrint = i1;
    iMatchto = -1;

    for(i=i1; i<=i2; i++){

      /* Check if this is the first token of any phrase match. */
      int ip;
      for(ip=0; ip<pIter->nPhrase; ip++){
        SnippetPhrase *pPhrase = &pIter->aPhrase[ip];
        u64 m = (1 << (iLast - i - pPhrase->nToken + 1));

        if( i<=iLast && (pPhrase->mask & m) ){
          if( iMatchto<0 ){
            sqlite3Fts5BufferAppendPrintf(&rc, pBuf, "%.*s%s",
                aiStart[i] - aiStart[iPrint],
                &zCol[aiStart[iPrint]],
                zStart
            );
            iPrint = i;
          }
          if( i>iMatchto ) iMatchto = i + pPhrase->nToken - 1;
        }
      }

      if( i==iMatchto ){
        sqlite3Fts5BufferAppendPrintf(&rc, pBuf, "%.*s%s",
            aiEnd[i] - aiStart[iPrint],
            &zCol[aiStart[iPrint]],
            zFinal
        );
        iMatchto = -1;
        iPrint = i+1;

        if( i<i2 ){
          sqlite3Fts5BufferAppendPrintf(&rc, pBuf, "%.*s",
              aiStart[i+1] - aiEnd[i],
              &zCol[aiEnd[i]]
          );
        }
      }
    }

    if( iPrint<=i2 ){
      sqlite3Fts5BufferAppendPrintf(&rc, pBuf, "%.*s", 
          aiEnd[i2] - aiStart[iPrint], 
          &zCol[aiStart[iPrint]]
      );
      if( iMatchto>=0 ){
        sqlite3Fts5BufferAppendString(&rc, pBuf, zFinal);
      }
    }

    /* If required, append the trailing ellipsis. */
    if( i2<ctx.iSeen ) sqlite3Fts5BufferAppendString(&rc, pBuf, zEllip);
  }

  sqlite3_free(ctx.aiStart);
  return rc;
}

/*
** A default snippet() implementation. This is compatible with the FTS3
** snippet() function.
*/
static void fts5SnippetFunction(
  const Fts5ExtensionApi *pApi,   /* API offered by current FTS version */
  Fts5Context *pFts,              /* First arg to pass to pApi functions */
  sqlite3_context *pCtx,          /* Context for returning result/error */
  int nVal,                       /* Number of values in apVal[] array */
  sqlite3_value **apVal           /* Array of trailing arguments */
){
  const char *zStart = "<b>";
  const char *zFinal = "</b>";
  const char *zEllip = "<b>...</b>";
  int nToken = -15;
  int nAbs;
  int nFrag;                      /* Number of fragments to return */
  int rc;
  SnippetIter *pIter = 0;

  if( nVal>=1 ) zStart = (const char*)sqlite3_value_text(apVal[0]);
  if( nVal>=2 ) zFinal = (const char*)sqlite3_value_text(apVal[1]);
  if( nVal>=3 ) zEllip = (const char*)sqlite3_value_text(apVal[2]);
  if( nVal>=4 ){
    nToken = sqlite3_value_int(apVal[3]);
    if( nToken==0 ) nToken = -15;
  }
  nAbs = nToken * (nToken<0 ? -1 : 1);

  rc = fts5SnippetIterNew(pApi, pFts, nAbs, &pIter);
  if( rc==SQLITE_OK ){
    Fts5Buffer buf;               /* Result buffer */
    int nBestScore = 0;           /* Score of best snippet found */
    int n;                        /* Size of column snippet is from in bytes */
    int i;                        /* Used to iterate through phrases */

    for(fts5SnippetIterFirst(pIter); 
        pIter->iLast>=0; 
        fts5SnippetIterNext(pIter)
    ){
      if( pIter->nScore>nBestScore ) nBestScore = pIter->nScore;
    }
    for(fts5SnippetIterFirst(pIter); 
        pIter->iLast>=0; 
        fts5SnippetIterNext(pIter)
    ){
      if( pIter->nScore==nBestScore ) break;
    }

    memset(&buf, 0, sizeof(Fts5Buffer));
    rc = fts5SnippetText(pApi, pFts, pIter, nAbs, zStart, zFinal, zEllip, &buf);
    if( rc==SQLITE_OK ){
      sqlite3_result_text(pCtx, (const char*)buf.p, buf.n, SQLITE_TRANSIENT);
    }
    sqlite3_free(buf.p);
  }

  fts5SnippetIterFree(pIter);
  if( rc!=SQLITE_OK ){
    sqlite3_result_error_code(pCtx, rc);
  }
}

static void fts5Bm25Function(
  const Fts5ExtensionApi *pApi,   /* API offered by current FTS version */
  Fts5Context *pFts,              /* First arg to pass to pApi functions */
  sqlite3_context *pCtx,          /* Context for returning result/error */
  int nVal,                       /* Number of values in apVal[] array */
  sqlite3_value **apVal           /* Array of trailing arguments */
){
  assert( 0 );
................................................................................
    Fts5Buffer s3;
    memset(&s3, 0, sizeof(s3));


    for(i=0; i<nPhrase; i++){
      Fts5Buffer s2;                  /* List of positions for phrase/column */
      int j = 0;
      i64 iPos = 0;

      int nElem = 0;

      memset(&s2, 0, sizeof(s2));
      while( 0==pApi->xPoslist(pFts, i, &j, &iPos) ){
        int iOff = FTS5_POS2OFFSET(iPos);
        int iCol = FTS5_POS2COLUMN(iPos);
        if( nElem!=0 ) sqlite3Fts5BufferAppendPrintf(&rc, &s2, " ");
        sqlite3Fts5BufferAppendPrintf(&rc, &s2, "%d.%d", iCol, iOff);
        nElem++;
      }

      if( i!=0 ){
        sqlite3Fts5BufferAppendPrintf(&rc, &s3, " ");

Changes to ext/fts5/fts5_buffer.c.

142
143
144
145
146
147
148

149
150
151
152
153
154
155
  const u8 *a, int n,             /* Buffer containing poslist */
  int *pi,                        /* IN/OUT: Offset within a[] */
  i64 *piOff                      /* IN/OUT: Current offset */
){
  int i = *pi;
  if( i>=n ){
    /* EOF */

    return 1;  
  }else{
    i64 iOff = *piOff;
    int iVal;
    i += getVarint32(&a[i], iVal);
    if( iVal==1 ){
      i += getVarint32(&a[i], iVal);







>







142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
  const u8 *a, int n,             /* Buffer containing poslist */
  int *pi,                        /* IN/OUT: Offset within a[] */
  i64 *piOff                      /* IN/OUT: Current offset */
){
  int i = *pi;
  if( i>=n ){
    /* EOF */
    *piOff = -1;
    return 1;  
  }else{
    i64 iOff = *piOff;
    int iVal;
    i += getVarint32(&a[i], iVal);
    if( iVal==1 ){
      i += getVarint32(&a[i], iVal);

Changes to ext/fts5/fts5_expr.c.

385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
  Fts5NearTrimmer *a = aStatic;

  Fts5ExprPhrase **apPhrase = pNear->apPhrase;

  int i;
  int rc = SQLITE_OK;
  int bMatch;
  i64 iMax;

  assert( pNear->nPhrase>1 );

  /* If the aStatic[] array is not large enough, allocate a large array
  ** using sqlite3_malloc(). This approach could be improved upon. */
  if( pNear->nPhrase>(sizeof(aStatic) / sizeof(aStatic[0])) ){
    int nByte = sizeof(Fts5LookaheadReader) * pNear->nPhrase;







<







385
386
387
388
389
390
391

392
393
394
395
396
397
398
  Fts5NearTrimmer *a = aStatic;

  Fts5ExprPhrase **apPhrase = pNear->apPhrase;

  int i;
  int rc = SQLITE_OK;
  int bMatch;


  assert( pNear->nPhrase>1 );

  /* If the aStatic[] array is not large enough, allocate a large array
  ** using sqlite3_malloc(). This approach could be improved upon. */
  if( pNear->nPhrase>(sizeof(aStatic) / sizeof(aStatic[0])) ){
    int nByte = sizeof(Fts5LookaheadReader) * pNear->nPhrase;

Changes to ext/fts5/fts5_storage.c.

481
482
483
484
485
486
487























488
489
490
491
492
493
494
495

496
497
498
499
500
501
502
...
508
509
510
511
512
513
514

515
516
517
518
519
520
521
522
523
524
525
526


527
528
529
530
531




532
533
534
535
536
537
538
539
540


541
542
543
544
545
546
547
548
549


550

551
552
553
554






















555
556
557
558
559
560
561
562

563
564
565
566
567
568
569
  /* Write the averages record */
  if( rc==SQLITE_OK ){
    rc = fts5StorageSaveTotals(p);
  }

  return rc;
}
























/*
** Context object used by sqlite3Fts5StorageIntegrity().
*/
typedef struct Fts5IntegrityCtx Fts5IntegrityCtx;
struct Fts5IntegrityCtx {
  i64 iRowid;
  int iCol;

  u64 cksum;
  Fts5Config *pConfig;
};

/*
** Tokenization callback used by integrity check.
*/
................................................................................
  int iEnd,                       /* End offset of token */
  int iPos                        /* Position offset of token */
){
  Fts5IntegrityCtx *pCtx = (Fts5IntegrityCtx*)pContext;
  pCtx->cksum ^= sqlite3Fts5IndexCksum(
      pCtx->pConfig, pCtx->iRowid, pCtx->iCol, iPos, pToken, nToken
  );

  return SQLITE_OK;
}

/*
** Check that the contents of the FTS index match that of the %_content
** table. Return SQLITE_OK if they do, or SQLITE_CORRUPT if not. Return
** some other SQLite error code if an error occurs while attempting to
** determine this.
*/
int sqlite3Fts5StorageIntegrity(Fts5Storage *p){
  Fts5Config *pConfig = p->pConfig;
  int rc;                         /* Return code */


  Fts5IntegrityCtx ctx;
  sqlite3_stmt *pScan;

  memset(&ctx, 0, sizeof(Fts5IntegrityCtx));
  ctx.pConfig = p->pConfig;





  /* Generate the expected index checksum based on the contents of the
  ** %_content table. This block stores the checksum in ctx.cksum. */
  rc = fts5StorageGetStmt(p, FTS5_STMT_SCAN_ASC, &pScan);
  if( rc==SQLITE_OK ){
    int rc2;
    while( SQLITE_ROW==sqlite3_step(pScan) ){
      int i;
      ctx.iRowid = sqlite3_column_int64(pScan, 0);


      for(i=0; rc==SQLITE_OK && i<pConfig->nCol; i++){
        ctx.iCol = i;
        rc = sqlite3Fts5Tokenize(
            pConfig, 
            (const char*)sqlite3_column_text(pScan, i+1),
            sqlite3_column_bytes(pScan, i+1),
            (void*)&ctx,
            fts5StorageIntegrityCallback
        );


      }

    }
    rc2 = sqlite3_reset(pScan);
    if( rc==SQLITE_OK ) rc = rc2;
  }























  /* Pass the expected checksum down to the FTS index module. It will
  ** verify, amongst other things, that it matches the checksum generated by
  ** inspecting the index itself.  */
  if( rc==SQLITE_OK ){
    rc = sqlite3Fts5IndexIntegrityCheck(p->pIndex, ctx.cksum);
  }


  return rc;
}

/*
** Obtain an SQLite statement handle that may be used to read data from the
** %_content table.
*/







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








>







 







>












>
>





>
>
>
>









>
>









>
>

>




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








>







481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
...
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
  /* Write the averages record */
  if( rc==SQLITE_OK ){
    rc = fts5StorageSaveTotals(p);
  }

  return rc;
}

static int fts5StorageCount(Fts5Storage *p, const char *zSuffix, i64 *pnRow){
  Fts5Config *pConfig = p->pConfig;
  char *zSql;
  int rc;

  zSql = sqlite3_mprintf("SELECT count(*) FROM %Q.'%q_%s'", 
      pConfig->zDb, pConfig->zName, zSuffix
  );
  if( zSql==0 ){
    rc = SQLITE_NOMEM;
  }else{
    sqlite3_stmt *pCnt = 0;
    rc = sqlite3_prepare_v2(pConfig->db, zSql, -1, &pCnt, 0);
    if( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pCnt) ){
      *pnRow = sqlite3_column_int64(pCnt, 0);
    }
    rc = sqlite3_finalize(pCnt);
  }

  sqlite3_free(zSql);
  return rc;
}

/*
** Context object used by sqlite3Fts5StorageIntegrity().
*/
typedef struct Fts5IntegrityCtx Fts5IntegrityCtx;
struct Fts5IntegrityCtx {
  i64 iRowid;
  int iCol;
  int szCol;
  u64 cksum;
  Fts5Config *pConfig;
};

/*
** Tokenization callback used by integrity check.
*/
................................................................................
  int iEnd,                       /* End offset of token */
  int iPos                        /* Position offset of token */
){
  Fts5IntegrityCtx *pCtx = (Fts5IntegrityCtx*)pContext;
  pCtx->cksum ^= sqlite3Fts5IndexCksum(
      pCtx->pConfig, pCtx->iRowid, pCtx->iCol, iPos, pToken, nToken
  );
  pCtx->szCol = iPos+1;
  return SQLITE_OK;
}

/*
** Check that the contents of the FTS index match that of the %_content
** table. Return SQLITE_OK if they do, or SQLITE_CORRUPT if not. Return
** some other SQLite error code if an error occurs while attempting to
** determine this.
*/
int sqlite3Fts5StorageIntegrity(Fts5Storage *p){
  Fts5Config *pConfig = p->pConfig;
  int rc;                         /* Return code */
  int *aColSize;                  /* Array of size pConfig->nCol */
  i64 *aTotalSize;                /* Array of size pConfig->nCol */
  Fts5IntegrityCtx ctx;
  sqlite3_stmt *pScan;

  memset(&ctx, 0, sizeof(Fts5IntegrityCtx));
  ctx.pConfig = p->pConfig;
  aTotalSize = (i64*)sqlite3_malloc(pConfig->nCol * (sizeof(int)+sizeof(i64)));
  if( !aTotalSize ) return SQLITE_NOMEM;
  aColSize = (int*)&aTotalSize[pConfig->nCol];
  memset(aTotalSize, 0, sizeof(i64) * pConfig->nCol);

  /* Generate the expected index checksum based on the contents of the
  ** %_content table. This block stores the checksum in ctx.cksum. */
  rc = fts5StorageGetStmt(p, FTS5_STMT_SCAN_ASC, &pScan);
  if( rc==SQLITE_OK ){
    int rc2;
    while( SQLITE_ROW==sqlite3_step(pScan) ){
      int i;
      ctx.iRowid = sqlite3_column_int64(pScan, 0);
      ctx.szCol = 0;
      rc = sqlite3Fts5StorageDocsize(p, ctx.iRowid, aColSize);
      for(i=0; rc==SQLITE_OK && i<pConfig->nCol; i++){
        ctx.iCol = i;
        rc = sqlite3Fts5Tokenize(
            pConfig, 
            (const char*)sqlite3_column_text(pScan, i+1),
            sqlite3_column_bytes(pScan, i+1),
            (void*)&ctx,
            fts5StorageIntegrityCallback
        );
        if( ctx.szCol!=aColSize[i] ) rc = SQLITE_CORRUPT_VTAB;
        aTotalSize[i] += ctx.szCol;
      }
      if( rc!=SQLITE_OK ) break;
    }
    rc2 = sqlite3_reset(pScan);
    if( rc==SQLITE_OK ) rc = rc2;
  }

  /* Test that the "totals" (sometimes called "averages") record looks Ok */
  if( rc==SQLITE_OK ){
    int i;
    rc = fts5StorageLoadTotals(p);
    for(i=0; rc==SQLITE_OK && i<pConfig->nCol; i++){
      if( p->aTotalSize[i]!=aTotalSize[i] ) rc = SQLITE_CORRUPT_VTAB;
    }
  }

  /* Check that the %_docsize and %_content tables contain the expected
  ** number of rows.  */
  if( rc==SQLITE_OK ){
    i64 nRow;
    rc = fts5StorageCount(p, "content", &nRow);
    if( rc==SQLITE_OK && nRow!=p->nTotalRow ) rc = SQLITE_CORRUPT_VTAB;
  }
  if( rc==SQLITE_OK ){
    i64 nRow;
    rc = fts5StorageCount(p, "docsize", &nRow);
    if( rc==SQLITE_OK && nRow!=p->nTotalRow ) rc = SQLITE_CORRUPT_VTAB;
  }

  /* Pass the expected checksum down to the FTS index module. It will
  ** verify, amongst other things, that it matches the checksum generated by
  ** inspecting the index itself.  */
  if( rc==SQLITE_OK ){
    rc = sqlite3Fts5IndexIntegrityCheck(p->pIndex, ctx.cksum);
  }

  sqlite3_free(aTotalSize);
  return rc;
}

/*
** Obtain an SQLite statement handle that may be used to read data from the
** %_content table.
*/

Added test/fts5af.test.





















































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
# 2014 June 17
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#*************************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is testing the FTS5 module.
# 
# More specifically, the tests in this file focus on the built-in 
# snippet() function.
#

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

# If SQLITE_ENABLE_FTS3 is defined, omit this file.
ifcapable !fts3 {
  finish_test
  return
}


do_execsql_test 1.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(x, y);
}


foreach {tn doc res} {

  1.1 {X o o o o o o} {[X] o o o o o o}
  1.2 {o X o o o o o} {o [X] o o o o o}
  1.3 {o o X o o o o} {o o [X] o o o o}
  1.4 {o o o X o o o} {o o o [X] o o o}
  1.5 {o o o o X o o} {o o o o [X] o o}
  1.6 {o o o o o X o} {o o o o o [X] o}
  1.7 {o o o o o o X} {o o o o o o [X]}

  2.1 {X o o o o o o o} {[X] o o o o o o...}
  2.2 {o X o o o o o o} {o [X] o o o o o...}
  2.3 {o o X o o o o o} {o o [X] o o o o...}
  2.4 {o o o X o o o o} {o o o [X] o o o...}
  2.5 {o o o o X o o o} {...o o o [X] o o o}
  2.6 {o o o o o X o o} {...o o o o [X] o o}
  2.7 {o o o o o o X o} {...o o o o o [X] o}
  2.8 {o o o o o o o X} {...o o o o o o [X]}

  3.1 {X o o o o o o o o} {[X] o o o o o o...}
  3.2 {o X o o o o o o o} {o [X] o o o o o...}
  3.3 {o o X o o o o o o} {o o [X] o o o o...}
  3.4 {o o o X o o o o o} {o o o [X] o o o...}
  3.5 {o o o o X o o o o} {...o o o [X] o o o...}
  3.6 {o o o o o X o o o} {...o o o [X] o o o}
  3.7 {o o o o o o X o o} {...o o o o [X] o o}
  3.8 {o o o o o o o X o} {...o o o o o [X] o}
  3.9 {o o o o o o o o X} {...o o o o o o [X]}

  4.1 {X o o o o o X o o} {[X] o o o o o [X]...}
  4.2 {o X o o o o o X o} {...[X] o o o o o [X]...}
  4.3 {o o X o o o o o X} {...[X] o o o o o [X]}

  5.1 {X o o o o X o o o} {[X] o o o o [X] o...}
  5.2 {o X o o o o X o o} {...[X] o o o o [X] o...}
  5.3 {o o X o o o o X o} {...[X] o o o o [X] o}
  5.4 {o o o X o o o o X} {...o [X] o o o o [X]}

  6.1 {X o o o X o o o} {[X] o o o [X] o o...}
  6.2 {o X o o o X o o o} {o [X] o o o [X] o...}
  6.3 {o o X o o o X o o} {...o [X] o o o [X] o...}
  6.4 {o o o X o o o X o} {...o [X] o o o [X] o}
  6.5 {o o o o X o o o X} {...o o [X] o o o [X]}

  7.1 {X o o X o o o o o} {[X] o o [X] o o o...}
  7.2 {o X o o X o o o o} {o [X] o o [X] o o...}
  7.3 {o o X o o X o o o} {...o [X] o o [X] o o...}
  7.4 {o o o X o o X o o} {...o [X] o o [X] o o}
  7.5 {o o o o X o o X o} {...o o [X] o o [X] o}
  7.6 {o o o o o X o o X} {...o o o [X] o o [X]}
} {
  do_execsql_test 1.$tn.1 {
    DELETE FROM t1;
    INSERT INTO t1 VALUES($doc, NULL);
    SELECT snippet(t1, '[', ']', '...', 7) FROM t1 WHERE t1 MATCH 'X';
  } [list $res]

  do_execsql_test 1.$tn.2 {
    DELETE FROM t1;
    INSERT INTO t1 VALUES(NULL, $doc);
    SELECT snippet(t1, '[', ']', '...', 7) FROM t1 WHERE t1 MATCH 'X';
  } [list $res]
}

foreach {tn doc res} {
  1.1 {X Y o o o o o} {[X Y] o o o o o}
  1.2 {o X Y o o o o} {o [X Y] o o o o}
  1.3 {o o X Y o o o} {o o [X Y] o o o}
  1.4 {o o o X Y o o} {o o o [X Y] o o}
  1.5 {o o o o X Y o} {o o o o [X Y] o}
  1.6 {o o o o o X Y} {o o o o o [X Y]}

  2.1 {X Y o o o o o o} {[X Y] o o o o o...}
  2.2 {o X Y o o o o o} {o [X Y] o o o o...}
  2.3 {o o X Y o o o o} {o o [X Y] o o o...}
  2.4 {o o o X Y o o o} {...o o [X Y] o o o}
  2.5 {o o o o X Y o o} {...o o o [X Y] o o}
  2.6 {o o o o o X Y o} {...o o o o [X Y] o}
  2.7 {o o o o o o X Y} {...o o o o o [X Y]}

  3.1 {X Y o o o o o o o} {[X Y] o o o o o...}
  3.2 {o X Y o o o o o o} {o [X Y] o o o o...}
  3.3 {o o X Y o o o o o} {o o [X Y] o o o...}
  3.4 {o o o X Y o o o o} {...o o [X Y] o o o...}
  3.5 {o o o o X Y o o o} {...o o [X Y] o o o}
  3.6 {o o o o o X Y o o} {...o o o [X Y] o o}
  3.7 {o o o o o o X Y o} {...o o o o [X Y] o}
  3.8 {o o o o o o o X Y} {...o o o o o [X Y]}

} {
  do_execsql_test 2.$tn.1 {
    DELETE FROM t1;
    INSERT INTO t1 VALUES($doc, NULL);
    SELECT snippet(t1, '[', ']', '...', 7) FROM t1 WHERE t1 MATCH 'X+Y';
  } [list $res]

  do_execsql_test 2.$tn.2 {
    DELETE FROM t1;
    INSERT INTO t1 VALUES(NULL, $doc);
    SELECT snippet(t1, '[', ']', '...', 7) FROM t1 WHERE t1 MATCH 'X+Y';
  } [list $res]
}

finish_test

Changes to test/permutations.test.

222
223
224
225
226
227
228

229
230
231
232
233
234
235
  fts4growth.test fts4growth2.test
}

test_suite "fts5" -prefix "" -description {
  All FTS5 tests.
} -files {
  fts5aa.test fts5ab.test fts5ac.test fts5ad.test fts5ae.test fts5ea.test

}

test_suite "nofaultsim" -prefix "" -description {
  "Very" quick test suite. Runs in less than 5 minutes on a workstation. 
  This test suite is the same as the "quick" tests, except that some files
  that test malloc and IO errors are omitted.
} -files [







>







222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
  fts4growth.test fts4growth2.test
}

test_suite "fts5" -prefix "" -description {
  All FTS5 tests.
} -files {
  fts5aa.test fts5ab.test fts5ac.test fts5ad.test fts5ae.test fts5ea.test
  fts5af.test
}

test_suite "nofaultsim" -prefix "" -description {
  "Very" quick test suite. Runs in less than 5 minutes on a workstation. 
  This test suite is the same as the "quick" tests, except that some files
  that test malloc and IO errors are omitted.
} -files [