SQLite

Check-in [16352d3654]
Login

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

Overview
Comment:Fix issues with position lists and NEAR constraints.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | fts5
Files: files | file ages | folders
SHA1: 16352d3654d5672cd0251db51dbe19f779373feb
User & Date: dan 2014-07-18 19:59:00.547
Context
2014-07-19
15:35
Fixes for the xColumnSize() fts5 extension API. (check-in: 43fcb84472 user: dan tags: fts5)
2014-07-18
19:59
Fix issues with position lists and NEAR constraints. (check-in: 16352d3654 user: dan tags: fts5)
2014-07-17
15:14
Fix a problem with position list processing for OR queries. (check-in: 5808f30fae user: dan tags: fts5)
Changes
Unified Diff Ignore Whitespace Patch
Changes to ext/fts5/fts5Int.h.
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
  const u8 *a, int n,             /* Poslist buffer to iterate through */
  Fts5PoslistReader *pIter        /* Iterator object to initialize */
);
int sqlite3Fts5PoslistReaderNext(Fts5PoslistReader*);

typedef struct Fts5PoslistWriter Fts5PoslistWriter;
struct Fts5PoslistWriter {
  int iCol;
  int iOff;
};
int sqlite3Fts5PoslistWriterAppend(Fts5Buffer*, Fts5PoslistWriter*, i64);

int sqlite3Fts5PoslistNext(
  const u8 *a, int n,             /* Buffer containing poslist */
  int *pi,                        /* IN/OUT: Offset within a[] */
  int *piCol,                     /* IN/OUT: Current column */
  int *piOff                      /* IN/OUT: Current token offset */
);







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

/**************************************************************************
** Interface to code in fts5_index.c. fts5_index.c contains contains code







|
<









>
>
>
>
>
>







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
  const u8 *a, int n,             /* Poslist buffer to iterate through */
  Fts5PoslistReader *pIter        /* Iterator object to initialize */
);
int sqlite3Fts5PoslistReaderNext(Fts5PoslistReader*);

typedef struct Fts5PoslistWriter Fts5PoslistWriter;
struct Fts5PoslistWriter {
  i64 iPrev;

};
int sqlite3Fts5PoslistWriterAppend(Fts5Buffer*, Fts5PoslistWriter*, i64);

int sqlite3Fts5PoslistNext(
  const u8 *a, int n,             /* Buffer containing poslist */
  int *pi,                        /* IN/OUT: Offset within a[] */
  int *piCol,                     /* IN/OUT: Current column */
  int *piOff                      /* IN/OUT: Current token offset */
);

int sqlite3Fts5PoslistNext64(
  const u8 *a, int n,             /* Buffer containing poslist */
  int *pi,                        /* IN/OUT: Offset within a[] */
  i64 *piOff                      /* IN/OUT: Current offset */
);

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

/**************************************************************************
** Interface to code in fts5_index.c. fts5_index.c contains contains code
Changes to ext/fts5/fts5_buffer.c.
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
  int nData, 
  const u8 *pData
){
  pBuf->n = 0;
  sqlite3Fts5BufferAppendBlob(pRc, pBuf, nData, pData);
}


























/*
** Advance the iterator object passed as the only argument. Return true
** if the iterator reaches EOF, or false otherwise.
*/
int sqlite3Fts5PoslistReaderNext(Fts5PoslistReader *pIter){
  if( pIter->i>=pIter->n ){
    pIter->bEof = 1;
  }else{
    int iVal;
    pIter->i += getVarint32(&pIter->a[pIter->i], iVal);
    if( iVal==1 ){
      pIter->i += getVarint32(&pIter->a[pIter->i], iVal);
      if( pIter->iCol>=0 && iVal>pIter->iCol ){
        pIter->bEof = 1;
      }else{
        pIter->iPos = ((u64)iVal << 32);
        pIter->i += getVarint32(&pIter->a[pIter->i], iVal);
      }
    }
    pIter->iPos += (iVal-2);
  }
  return pIter->bEof;
}

int sqlite3Fts5PoslistReaderInit(
  int iCol,                       /* If (iCol>=0), this column only */
  const u8 *a, int n,             /* Poslist buffer to iterate through */







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






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







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
  int nData, 
  const u8 *pData
){
  pBuf->n = 0;
  sqlite3Fts5BufferAppendBlob(pRc, pBuf, nData, pData);
}

int sqlite3Fts5PoslistNext64(
  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);
      iOff = ((i64)iVal) << 32;
      i += getVarint32(&a[i], iVal);
    }
    *piOff = iOff + (iVal-2);
    *pi = i;
    return 0;
  }
}


/*
** Advance the iterator object passed as the only argument. Return true
** if the iterator reaches EOF, or false otherwise.
*/
int sqlite3Fts5PoslistReaderNext(Fts5PoslistReader *pIter){
  if( sqlite3Fts5PoslistNext64(pIter->a, pIter->n, &pIter->i, &pIter->iPos) 
   || (pIter->iCol>=0 && (pIter->iPos >> 32) > pIter->iCol)



  ){


    pIter->bEof = 1;






  }
  return pIter->bEof;
}

int sqlite3Fts5PoslistReaderInit(
  int iCol,                       /* If (iCol>=0), this column only */
  const u8 *a, int n,             /* Poslist buffer to iterate through */
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
}

int sqlite3Fts5PoslistWriterAppend(
  Fts5Buffer *pBuf, 
  Fts5PoslistWriter *pWriter,
  i64 iPos
){

  int rc = SQLITE_OK;
  int iCol = (int)(iPos >> 32);
  int iOff = (iPos & 0x7FFFFFFF);

  if( iCol!=pWriter->iCol ){
    fts5BufferAppendVarint(&rc, pBuf, 1);
    fts5BufferAppendVarint(&rc, pBuf, iCol);
    pWriter->iCol = iCol;
    pWriter->iOff = 0;
  }
  fts5BufferAppendVarint(&rc, pBuf, (iOff - pWriter->iOff) + 2);

  return rc;
}

int sqlite3Fts5PoslistNext(
  const u8 *a, int n,             /* Buffer containing poslist */
  int *pi,                        /* IN/OUT: Offset within a[] */
  int *piCol,                     /* IN/OUT: Current column */







>

<
<
|
<

|
<
|

|
|







192
193
194
195
196
197
198
199
200


201

202
203

204
205
206
207
208
209
210
211
212
213
214
}

int sqlite3Fts5PoslistWriterAppend(
  Fts5Buffer *pBuf, 
  Fts5PoslistWriter *pWriter,
  i64 iPos
){
  static const i64 colmask = ((i64)(0x7FFFFFFF)) << 32;
  int rc = SQLITE_OK;


  if( (iPos & colmask) != (pWriter->iPrev & colmask) ){

    fts5BufferAppendVarint(&rc, pBuf, 1);
    fts5BufferAppendVarint(&rc, pBuf, (iPos >> 32));

    pWriter->iPrev = (iPos & colmask);
  }
  fts5BufferAppendVarint(&rc, pBuf, (iPos - pWriter->iPrev) + 2);
  pWriter->iPrev = iPos;
  return rc;
}

int sqlite3Fts5PoslistNext(
  const u8 *a, int n,             /* Buffer containing poslist */
  int *pi,                        /* IN/OUT: Offset within a[] */
  int *piCol,                     /* IN/OUT: Current column */
Changes to ext/fts5/fts5_expr.c.
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
*/
struct Fts5ExprNode {
  int eType;                      /* Node type */
  Fts5ExprNode *pLeft;            /* Left hand child node */
  Fts5ExprNode *pRight;           /* Right hand child node */
  Fts5ExprNearset *pNear;         /* For FTS5_STRING - cluster of phrases */
  int bEof;                       /* True at EOF */
  i64 iRowid;
};

/*
** An instance of the following structure represents a single search term
** or term prefix.
*/
struct Fts5ExprTerm {
  int bPrefix;                    /* True for a prefix term */
  char *zTerm;                    /* nul-terminated term */
  Fts5IndexIter *pIter;           /* Iterator for this term */
};

/*
** A phrase. One or more terms that must appear in a contiguous sequence
** within a document for it to match.
*/
struct Fts5ExprPhrase {

  Fts5Buffer poslist;             /* Current position list */
  int nTerm;                      /* Number of entries in aTerm[] */
  Fts5ExprTerm aTerm[0];          /* Terms that make up this phrase */
};

/*
** One or more phrases that must appear within a certain token distance of







|

















>







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
*/
struct Fts5ExprNode {
  int eType;                      /* Node type */
  Fts5ExprNode *pLeft;            /* Left hand child node */
  Fts5ExprNode *pRight;           /* Right hand child node */
  Fts5ExprNearset *pNear;         /* For FTS5_STRING - cluster of phrases */
  int bEof;                       /* True at EOF */
  i64 iRowid;                     /* Current rowid */
};

/*
** An instance of the following structure represents a single search term
** or term prefix.
*/
struct Fts5ExprTerm {
  int bPrefix;                    /* True for a prefix term */
  char *zTerm;                    /* nul-terminated term */
  Fts5IndexIter *pIter;           /* Iterator for this term */
};

/*
** A phrase. One or more terms that must appear in a contiguous sequence
** within a document for it to match.
*/
struct Fts5ExprPhrase {
  Fts5ExprNode *pNode;            /* FTS5_STRING node this phrase is part of */
  Fts5Buffer poslist;             /* Current position list */
  int nTerm;                      /* Number of entries in aTerm[] */
  Fts5ExprTerm aTerm[0];          /* Terms that make up this phrase */
};

/*
** One or more phrases that must appear within a certain token distance of
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
*/
static int fts5ExprPhraseIsMatch(
  Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
  int iCol,                       /* If >=0, search for matches in iCol only */
  Fts5ExprPhrase *pPhrase,        /* Phrase object to initialize */
  int *pbMatch                    /* OUT: Set to true if really a match */
){
  Fts5PoslistWriter writer = {0, 0};
  Fts5PoslistReader aStatic[4];
  Fts5PoslistReader *aIter = aStatic;
  int i;
  int rc = SQLITE_OK;

  fts5BufferZero(&pPhrase->poslist);








|







263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
*/
static int fts5ExprPhraseIsMatch(
  Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
  int iCol,                       /* If >=0, search for matches in iCol only */
  Fts5ExprPhrase *pPhrase,        /* Phrase object to initialize */
  int *pbMatch                    /* OUT: Set to true if really a match */
){
  Fts5PoslistWriter writer = {0};
  Fts5PoslistReader aStatic[4];
  Fts5PoslistReader *aIter = aStatic;
  int i;
  int rc = SQLITE_OK;

  fts5BufferZero(&pPhrase->poslist);

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

 ismatch_out:
  *pbMatch = (pPhrase->poslist.n>0);
  if( aIter!=aStatic ) sqlite3_free(aIter);
  return rc;
}










































/*
** The near-set object passed as the first argument contains more than
** one phrase. All phrases currently point to the same row. The
** Fts5ExprPhrase.poslist buffers are populated accordingly. This function
** tests if the current row contains instances of each phrase sufficiently
** close together to meet the NEAR constraint. Output variable *pbMatch
** is set to true if it does, or false otherwise.
**
** If no error occurs, SQLITE_OK is returned. Or, if an error does occur,
** an SQLite error code. If a value other than SQLITE_OK is returned, the
** final value of *pbMatch is undefined.
**
** TODO: This function should also edit the position lists associated
** with each phrase to remove any phrase instances that are not part of
** a set of intances that collectively matches the NEAR constraint.
*/
static int fts5ExprNearIsMatch(Fts5ExprNearset *pNear, int *pbMatch){
  Fts5PoslistReader aStatic[4];

  Fts5PoslistReader *aIter = aStatic;


  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(Fts5PoslistReader) * pNear->nPhrase;
    aIter = (Fts5PoslistReader*)sqlite3_malloc(nByte);
    if( !aIter ) return SQLITE_NOMEM;



  }

  /* Initialize a term iterator for each phrase */







  for(i=0; i<pNear->nPhrase; i++){
    Fts5Buffer *pPoslist = &pNear->apPhrase[i]->poslist; 
    sqlite3Fts5PoslistReaderInit(-1, pPoslist->p, pPoslist->n, &aIter[i]);


  }








  iMax = aIter[0].iPos;
  do {
    bMatch = 1;
    for(i=0; i<pNear->nPhrase; i++){
      Fts5PoslistReader *pPos = &aIter[i];
      i64 iMin = iMax - pNear->apPhrase[i]->nTerm - pNear->nNear;
      if( pPos->iPos<iMin || pPos->iPos>iMax ){
        bMatch = 0;
        while( pPos->iPos<iMin ){
          if( sqlite3Fts5PoslistReaderNext(pPos) ) goto ismatch_out;
        }
        if( pPos->iPos>iMax ) iMax = pPos->iPos;
      }
    }
  }while( bMatch==0 );





















 ismatch_out:
  *pbMatch = bMatch;
  if( aIter!=aStatic ) sqlite3_free(aIter);
  return rc;
}

/*
** Advance each term iterator in each phrase in pNear. If any reach EOF, 
** set output variable *pbEof to true before returning.
*/







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


















|
>
|
>
>










|
|
|
>
>
>


|
>
>
>
>
>
>
>

|
|
>
>


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


|
|







319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474

 ismatch_out:
  *pbMatch = (pPhrase->poslist.n>0);
  if( aIter!=aStatic ) sqlite3_free(aIter);
  return rc;
}

typedef struct Fts5LookaheadReader Fts5LookaheadReader;
struct Fts5LookaheadReader {
  const u8 *a;                    /* Buffer containing position list */
  int n;                          /* Size of buffer a[] in bytes */
  int i;                          /* Current offset in position list */
  i64 iPos;                       /* Current position */
  i64 iLookahead;                 /* Next position */
};

#define FTS5_LOOKAHEAD_EOF (((i64)1) << 62)

static int fts5LookaheadReaderNext(Fts5LookaheadReader *p){
  p->iPos = p->iLookahead;
  if( sqlite3Fts5PoslistNext64(p->a, p->n, &p->i, &p->iLookahead) ){
    p->iLookahead = FTS5_LOOKAHEAD_EOF;
  }
  return (p->iPos==FTS5_LOOKAHEAD_EOF);
}

static int fts5LookaheadReaderInit(
  const u8 *a, int n,             /* Buffer to read position list from */
  Fts5LookaheadReader *p          /* Iterator object to initialize */
){
  memset(p, 0, sizeof(Fts5LookaheadReader));
  p->a = a;
  p->n = n;
  fts5LookaheadReaderNext(p);
  return fts5LookaheadReaderNext(p);
}

static int fts5LookaheadReaderEof(Fts5LookaheadReader *p){
  return (p->iPos==FTS5_LOOKAHEAD_EOF);
}

typedef struct Fts5NearTrimmer Fts5NearTrimmer;
struct Fts5NearTrimmer {
  Fts5LookaheadReader reader;     /* Input iterator */
  Fts5PoslistWriter writer;       /* Writer context */
  Fts5Buffer *pOut;               /* Output poslist */
};

/*
** The near-set object passed as the first argument contains more than
** one phrase. All phrases currently point to the same row. The
** Fts5ExprPhrase.poslist buffers are populated accordingly. This function
** tests if the current row contains instances of each phrase sufficiently
** close together to meet the NEAR constraint. Output variable *pbMatch
** is set to true if it does, or false otherwise.
**
** If no error occurs, SQLITE_OK is returned. Or, if an error does occur,
** an SQLite error code. If a value other than SQLITE_OK is returned, the
** final value of *pbMatch is undefined.
**
** TODO: This function should also edit the position lists associated
** with each phrase to remove any phrase instances that are not part of
** a set of intances that collectively matches the NEAR constraint.
*/
static int fts5ExprNearIsMatch(Fts5ExprNearset *pNear, int *pbMatch){
  Fts5NearTrimmer aStatic[4];
  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;
    a = (Fts5NearTrimmer*)sqlite3_malloc(nByte);
    if( !a ) return SQLITE_NOMEM;
    memset(a, 0, nByte);
  }else{
    memset(aStatic, 0, sizeof(aStatic));
  }

  /* Initialize a lookahead iterator for each phrase. After passing the
  ** buffer and buffer size to the lookaside-reader init function, zero
  ** the phrase poslist buffer. The new poslist for the phrase (containing
  ** the same entries as the original with some entries removed on account 
  ** of the NEAR constraint) is written over the original even as it is
  ** being read. This is safe as the entries for the new poslist are a
  ** subset of the old, so it is not possible for data yet to be read to
  ** be overwritten.  */
  for(i=0; i<pNear->nPhrase; i++){
    Fts5Buffer *pPoslist = &apPhrase[i]->poslist;
    fts5LookaheadReaderInit(pPoslist->p, pPoslist->n, &a[i].reader);
    pPoslist->n = 0;
    a[i].pOut = pPoslist;
  }

  while( 1 ){
    int iAdv;
    i64 iMin;
    i64 iMax;

    /* This block advances the phrase iterators until they point to a set of
    ** entries that together comprise a match.  */
    iMax = a[0].reader.iPos;
    do {
      bMatch = 1;
      for(i=0; i<pNear->nPhrase; i++){
        Fts5LookaheadReader *pPos = &a[i].reader;
        iMin = iMax - pNear->apPhrase[i]->nTerm - pNear->nNear;
        if( pPos->iPos<iMin || pPos->iPos>iMax ){
          bMatch = 0;
          while( pPos->iPos<iMin ){
            if( fts5LookaheadReaderNext(pPos) ) goto ismatch_out;
          }
          if( pPos->iPos>iMax ) iMax = pPos->iPos;
        }
      }
    }while( bMatch==0 );

    /* Add an entry to each output position list */
    for(i=0; i<pNear->nPhrase; i++){
      i64 iPos = a[i].reader.iPos;
      Fts5PoslistWriter *pWriter = &a[i].writer;
      if( a[i].pOut->n==0 || iPos!=pWriter->iPrev ){
        sqlite3Fts5PoslistWriterAppend(a[i].pOut, pWriter, iPos);
      }
    }

    iAdv = 0;
    iMin = a[0].reader.iLookahead;
    for(i=0; i<pNear->nPhrase; i++){
      if( a[i].reader.iLookahead < iMin ){
        iMin = a[i].reader.iLookahead;
        iAdv = i;
      }
    }
    if( fts5LookaheadReaderNext(&a[iAdv].reader) ) goto ismatch_out;
  }

 ismatch_out:
  *pbMatch = (a[0].pOut->n>0);
  if( a!=aStatic ) sqlite3_free(a);
  return rc;
}

/*
** Advance each term iterator in each phrase in pNear. If any reach EOF, 
** set output variable *pbEof to true before returning.
*/
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
  Fts5ExprNode *pNode
){
  int rc = SQLITE_OK;
  Fts5ExprNearset *pNear = pNode->pNear;
  while( 1 ){
    int i;

    /* Advance the iterators until they are a match */
    rc = fts5ExprNearNextRowidMatch(pExpr, pNode);
    if( pNode->bEof || rc!=SQLITE_OK ) break;

    for(i=0; i<pNear->nPhrase; i++){
      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
      if( pPhrase->nTerm>1 || pNear->iCol>=0 ){
        int bMatch = 0;







|







598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
  Fts5ExprNode *pNode
){
  int rc = SQLITE_OK;
  Fts5ExprNearset *pNear = pNode->pNear;
  while( 1 ){
    int i;

    /* Advance the iterators until they all point to the same rowid */
    rc = fts5ExprNearNextRowidMatch(pExpr, pNode);
    if( pNode->bEof || rc!=SQLITE_OK ) break;

    for(i=0; i<pNear->nPhrase; i++){
      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
      if( pPhrase->nTerm>1 || pNear->iCol>=0 ){
        int bMatch = 0;
541
542
543
544
545
546
547


548
549
550
551
552
553
554
      int bMatch = 1;
      if( pNear->nPhrase>1 ){
        rc = fts5ExprNearIsMatch(pNear, &bMatch);
      }
      if( rc!=SQLITE_OK || bMatch ) break;
    }



    rc = fts5ExprNearAdvanceAll(pExpr, pNear, &pNode->bEof);
    if( pNode->bEof || rc!=SQLITE_OK ) break;
  }

  return rc;
}








>
>







624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
      int bMatch = 1;
      if( pNear->nPhrase>1 ){
        rc = fts5ExprNearIsMatch(pNear, &bMatch);
      }
      if( rc!=SQLITE_OK || bMatch ) break;
    }

    /* If control flows to here, then the current rowid is not a match.
    ** Advance all term iterators in all phrases to the next rowid. */
    rc = fts5ExprNearAdvanceAll(pExpr, pNear, &pNode->bEof);
    if( pNode->bEof || rc!=SQLITE_OK ) break;
  }

  return rc;
}

656
657
658
659
660
661
662








663
664
665
666
667
668
669
    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeNextMatch(pExpr, pNode);
    }
  }

  return rc;
}









/*
**
*/
static int fts5ExprNodeNextMatch(Fts5Expr *pExpr, Fts5ExprNode *pNode){
  int rc = SQLITE_OK;
  if( pNode->bEof==0 ){







>
>
>
>
>
>
>
>







741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeNextMatch(pExpr, pNode);
    }
  }

  return rc;
}

static void fts5ExprSetEof(Fts5ExprNode *pNode){
  if( pNode ){
    pNode->bEof = 1;
    fts5ExprSetEof(pNode->pLeft);
    fts5ExprSetEof(pNode->pRight);
  }
}

/*
**
*/
static int fts5ExprNodeNextMatch(Fts5Expr *pExpr, Fts5ExprNode *pNode){
  int rc = SQLITE_OK;
  if( pNode->bEof==0 ){
684
685
686
687
688
689
690
691


692
693
694
695
696
697
698
            pAdv = (p1->iRowid < p2->iRowid) ? p1 : p2;
          }else{
            pAdv = (p1->iRowid > p2->iRowid) ? p1 : p2;
          }
          rc = fts5ExprNodeNext(pExpr, pAdv);
          if( rc!=SQLITE_OK ) break;
        }
        pNode->bEof = p1->bEof || p2->bEof;


        pNode->iRowid = p1->iRowid;
        break;
      }

      case FTS5_OR: {
        Fts5ExprNode *p1 = pNode->pLeft;
        Fts5ExprNode *p2 = pNode->pRight;







|
>
>







777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
            pAdv = (p1->iRowid < p2->iRowid) ? p1 : p2;
          }else{
            pAdv = (p1->iRowid > p2->iRowid) ? p1 : p2;
          }
          rc = fts5ExprNodeNext(pExpr, pAdv);
          if( rc!=SQLITE_OK ) break;
        }
        if( p1->bEof || p2->bEof ){
          fts5ExprSetEof(pNode);
        }
        pNode->iRowid = p1->iRowid;
        break;
      }

      case FTS5_OR: {
        Fts5ExprNode *p1 = pNode->pLeft;
        Fts5ExprNode *p2 = pNode->pRight;
1086
1087
1088
1089
1090
1091
1092






1093
1094
1095
1096
1097
1098
1099
      pParse->rc = SQLITE_NOMEM;
    }else{
      memset(pRet, 0, sizeof(*pRet));
      pRet->eType = eType;
      pRet->pLeft = pLeft;
      pRet->pRight = pRight;
      pRet->pNear = pNear;






    }
  }

  if( pRet==0 ){
    assert( pParse->rc!=SQLITE_OK );
    sqlite3Fts5ParseNodeFree(pLeft);
    sqlite3Fts5ParseNodeFree(pRight);







>
>
>
>
>
>







1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
      pParse->rc = SQLITE_NOMEM;
    }else{
      memset(pRet, 0, sizeof(*pRet));
      pRet->eType = eType;
      pRet->pLeft = pLeft;
      pRet->pRight = pRight;
      pRet->pNear = pNear;
      if( eType==FTS5_STRING ){
        int iPhrase;
        for(iPhrase=0; iPhrase<pNear->nPhrase; iPhrase++){
          pNear->apPhrase[iPhrase]->pNode = pRet;
        }
      }
    }
  }

  if( pRet==0 ){
    assert( pParse->rc!=SQLITE_OK );
    sqlite3Fts5ParseNodeFree(pLeft);
    sqlite3Fts5ParseNodeFree(pRight);
1394
1395
1396
1397
1398
1399
1400

1401
1402
1403
1404
1405
1406
1407
1408
1409
/*
** This function is used to access the current position list for phrase
** iPhrase.
*/
int sqlite3Fts5ExprPoslist(Fts5Expr *pExpr, int iPhrase, const u8 **pa){
  if( iPhrase>=0 && iPhrase<pExpr->nPhrase ){
    Fts5ExprPhrase *pPhrase = pExpr->apPhrase[iPhrase];

    if( sqlite3Fts5IterRowid(pPhrase->aTerm[0].pIter)==pExpr->pRoot->iRowid ){
      *pa = pPhrase->poslist.p;
      return pPhrase->poslist.n;
    }
  }
  *pa = 0;
  return 0;
}








>
|








1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
/*
** This function is used to access the current position list for phrase
** iPhrase.
*/
int sqlite3Fts5ExprPoslist(Fts5Expr *pExpr, int iPhrase, const u8 **pa){
  if( iPhrase>=0 && iPhrase<pExpr->nPhrase ){
    Fts5ExprPhrase *pPhrase = pExpr->apPhrase[iPhrase];
    Fts5ExprNode *pNode = pPhrase->pNode;
    if( pNode->bEof==0 && pNode->iRowid==pExpr->pRoot->iRowid ){
      *pa = pPhrase->poslist.p;
      return pPhrase->poslist.n;
    }
  }
  *pa = 0;
  return 0;
}

Changes to test/fts5ac.test.
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
  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"


} {
  set res [matchdata 1 $expr]




































  do_execsql_test 2.1.$tn.[llength $res] { 
    SELECT rowid, fts5_test(xx, 'poslist') FROM xx WHERE xx match $expr
  } $res
}


do_test 2.1  { poslist {{a b c}} -- a } {0.0}
do_test 2.2  { poslist {{a b c}} -- c } {0.2}

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

#-------------------------------------------------------------------------
#
foreach {bAsc sql} {
  0 {SELECT rowid FROM xx WHERE xx MATCH $expr}
  1 {SELECT rowid FROM xx WHERE xx MATCH $expr ORDER BY rowid ASC}







>


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




<
|
|




|







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
  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(xx, 'poslist') 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(xx, 'poslist') 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(xx, 'poslist') FROM xx WHERE xx match $expr
  } $res
}


do_test 4.1  { poslist {{a b c}} -- a } {0.0}
do_test 4.2  { poslist {{a b c}} -- c } {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]
}

#-------------------------------------------------------------------------
#
foreach {bAsc sql} {
  0 {SELECT rowid FROM xx WHERE xx MATCH $expr}
  1 {SELECT rowid FROM xx WHERE xx MATCH $expr ORDER BY rowid ASC}
352
353
354
355
356
357
358
359
360
361
362
363
364
    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 4.$bAsc.$tn.[llength $res] $sql $res
  }
}

finish_test








|





388
389
390
391
392
393
394
395
396
397
398
399
400
    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

Added test/fts5ae.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
# 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.
#
#

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

# 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(a, b);
  INSERT INTO t1(t1) VALUES('pgsz=32');
}

do_execsql_test 1.1 {
  INSERT INTO t1 VALUES('hello', 'world');
  SELECT rowid FROM t1 WHERE t1 MATCH 'hello' ORDER BY rowid ASC;
} {1}

do_execsql_test 1.2 {
  INSERT INTO t1 VALUES('world', 'hello');
  SELECT rowid FROM t1 WHERE t1 MATCH 'hello' ORDER BY rowid ASC;
} {1 2}

do_execsql_test 1.3 {
  INSERT INTO t1 VALUES('world', 'world');
  SELECT rowid FROM t1 WHERE t1 MATCH 'hello' ORDER BY rowid ASC;
} {1 2}

do_execsql_test 1.4.1 {
  INSERT INTO t1 VALUES('hello', 'hello');
}

do_execsql_test 1.4.2 {
  SELECT rowid FROM t1 WHERE t1 MATCH 'hello' ORDER BY rowid ASC;
} {1 2 4}


#-------------------------------------------------------------------------
# 
do_execsql_test 2.0 {
  CREATE VIRTUAL TABLE t2 USING fts5(x, y);
  INSERT INTO t2 VALUES('u t l w w m s', 'm f m o l t k o p e');
  INSERT INTO t2 VALUES('f g q e l n d m z x q', 'z s i i i m f w w f n g p');
}

do_execsql_test 2.1 {
  SELECT rowid, fts5_test(t2, 'poslist') FROM t2 
  WHERE t2 MATCH 'm' ORDER BY rowid;
} {
  1 {{0.5 1.0 1.2}} 
  2 {{0.7 1.5}}
}

do_execsql_test 2.2 {
  SELECT rowid, fts5_test(t2, 'poslist') FROM t2 
  WHERE t2 MATCH 'u OR q' ORDER BY rowid;
} {
  1 {0.0 {}}
  2 {{} {0.2 0.10}}
}

do_execsql_test 2.3 {
  SELECT rowid, fts5_test(t2, 'poslist') FROM t2 
  WHERE t2 MATCH 'y:o' ORDER BY rowid;
} {
  1 {{1.3 1.7}}
}

#-------------------------------------------------------------------------
# 
do_execsql_test 3.0 {
  CREATE VIRTUAL TABLE t3 USING fts5(x, y);
  INSERT INTO t3 VALUES( 'j f h o x x a z g b a f a m i b', 'j z c z y x w t');
  INSERT INTO t3 VALUES( 'r c', '');
}

do_execsql_test 3.1 {
  SELECT rowid, fts5_test(t3, 'poslist') FROM t3 WHERE t3 MATCH 'NEAR(a b)';
} {
  1 {{0.6 0.10 0.12} {0.9 0.15}}
}

do_execsql_test 3.2 {
  SELECT rowid, fts5_test(t3, 'poslist') FROM t3 WHERE t3 MATCH 'NEAR(r c)';
} {
  2 {0.0 0.1}
}

do_execsql_test 3.3 {
  INSERT INTO t3 
  VALUES('k x j r m a d o i z j', 'r t t t f e b r x i v j v g o');
  SELECT rowid, fts5_test(t3, 'poslist') 
  FROM t3 WHERE t3 MATCH 'a OR b AND c';
} {
  3 {0.5 {} {}} 
  1 {{0.6 0.10 0.12} {0.9 0.15} 1.2}
}

#-------------------------------------------------------------------------
# 
do_execsql_test 4.0 {
  CREATE VIRTUAL TABLE t4 USING fts5(x, y);
  INSERT INTO t4 
  VALUES('k x j r m a d o i z j', 'r t t t f e b r x i v j v g o');
}

breakpoint
do_execsql_test 4.1 {
  SELECT rowid, fts5_test(t4, 'poslist') FROM t4 WHERE t4 MATCH 'a OR b AND c';
} {
  1 {0.5 {} {}} 
}

#93 {0.5 1.6 {}}


finish_test