SQLite

Check-in [5206ca6005]
Login

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

Overview
Comment:Have fts5 store rowids in ascending order. Query speed is virtually the same regardless of rowid order, and ascending order makes some insert optimizations easier.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | fts5
Files: files | file ages | folders
SHA1: 5206ca6005bfa9dfc7346d4b89430c9748d32c10
User & Date: dan 2015-01-24 19:57:03.097
Context
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: f704bc059e user: dan tags: fts5)
2015-01-24
19:57
Have fts5 store rowids in ascending order. Query speed is virtually the same regardless of rowid order, and ascending order makes some insert optimizations easier. (check-in: 5206ca6005 user: dan tags: fts5)
2015-01-23
17:43
Fix compression of keys stored on internal segment b-tree nodes by fts5. (check-in: 51444f67c0 user: dan tags: fts5)
Changes
Unified Diff Show Whitespace Changes Patch
Changes to ext/fts5/fts5.c.
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
  }
  *ppCsr = (sqlite3_vtab_cursor*)pCsr;
  return rc;
}

static int fts5StmtType(int idxNum){
  if( FTS5_PLAN(idxNum)==FTS5_PLAN_SCAN ){
    return (idxNum&FTS5_ORDER_ASC) ? FTS5_STMT_SCAN_ASC : FTS5_STMT_SCAN_DESC;
  }
  return FTS5_STMT_LOOKUP;
}

/*
** This function is called after the cursor passed as the only argument
** is moved to point at a different row. It clears all cached data 







|







501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
  }
  *ppCsr = (sqlite3_vtab_cursor*)pCsr;
  return rc;
}

static int fts5StmtType(int idxNum){
  if( FTS5_PLAN(idxNum)==FTS5_PLAN_SCAN ){
    return (idxNum&FTS5_ORDER_DESC) ? FTS5_STMT_SCAN_DESC : FTS5_STMT_SCAN_ASC;
  }
  return FTS5_STMT_LOOKUP;
}

/*
** This function is called after the cursor passed as the only argument
** is moved to point at a different row. It clears all cached data 
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
      }
      break;
  }
  
  return rc;
}

static int fts5CursorFirstSorted(Fts5Table *pTab, Fts5Cursor *pCsr, int bAsc){
  Fts5Config *pConfig = pTab->pConfig;
  Fts5Sorter *pSorter;
  int nPhrase;
  int nByte;
  int rc = SQLITE_OK;
  char *zSql;
  const char *zRank = pCsr->zRank;







|







648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
      }
      break;
  }
  
  return rc;
}

static int fts5CursorFirstSorted(Fts5Table *pTab, Fts5Cursor *pCsr, int bDesc){
  Fts5Config *pConfig = pTab->pConfig;
  Fts5Sorter *pSorter;
  int nPhrase;
  int nByte;
  int rc = SQLITE_OK;
  char *zSql;
  const char *zRank = pCsr->zRank;
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
  ** table, saving it creates a circular reference.
  **
  ** If SQLite a built-in statement cache, this wouldn't be a problem. */
  zSql = sqlite3_mprintf("SELECT rowid, rank FROM %Q.%Q ORDER BY %s(%s%s%s) %s",
      pConfig->zDb, pConfig->zName, zRank, pConfig->zName,
      (zRankArgs ? ", " : ""),
      (zRankArgs ? zRankArgs : ""),
      bAsc ? "ASC" : "DESC"
  );
  if( zSql==0 ){
    rc = SQLITE_NOMEM;
  }else{
    rc = sqlite3_prepare_v2(pConfig->db, zSql, -1, &pSorter->pStmt, 0);
    sqlite3_free(zSql);
  }







|







676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
  ** table, saving it creates a circular reference.
  **
  ** If SQLite a built-in statement cache, this wouldn't be a problem. */
  zSql = sqlite3_mprintf("SELECT rowid, rank FROM %Q.%Q ORDER BY %s(%s%s%s) %s",
      pConfig->zDb, pConfig->zName, zRank, pConfig->zName,
      (zRankArgs ? ", " : ""),
      (zRankArgs ? zRankArgs : ""),
      bDesc ? "DESC" : "ASC"
  );
  if( zSql==0 ){
    rc = SQLITE_NOMEM;
  }else{
    rc = sqlite3_prepare_v2(pConfig->db, zSql, -1, &pSorter->pStmt, 0);
    sqlite3_free(zSql);
  }
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
    sqlite3_free(pSorter);
    pCsr->pSorter = 0;
  }

  return rc;
}

static int fts5CursorFirst(Fts5Table *pTab, Fts5Cursor *pCsr, int bAsc){
  int rc;
  rc = sqlite3Fts5ExprFirst(pCsr->pExpr, pTab->pIndex, bAsc);
  if( sqlite3Fts5ExprEof(pCsr->pExpr) ){
    CsrFlagSet(pCsr, FTS5CSR_EOF);
  }
  fts5CsrNewrow(pCsr);
  return rc;
}








|

|







702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
    sqlite3_free(pSorter);
    pCsr->pSorter = 0;
  }

  return rc;
}

static int fts5CursorFirst(Fts5Table *pTab, Fts5Cursor *pCsr, int bDesc){
  int rc;
  rc = sqlite3Fts5ExprFirst(pCsr->pExpr, pTab->pIndex, bDesc);
  if( sqlite3Fts5ExprEof(pCsr->pExpr) ){
    CsrFlagSet(pCsr, FTS5CSR_EOF);
  }
  fts5CsrNewrow(pCsr);
  return rc;
}

869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
  int idxNum,                     /* Strategy index */
  const char *idxStr,             /* Unused */
  int nVal,                       /* Number of elements in apVal */
  sqlite3_value **apVal           /* Arguments for the indexing scheme */
){
  Fts5Table *pTab = (Fts5Table*)(pCursor->pVtab);
  Fts5Cursor *pCsr = (Fts5Cursor*)pCursor;
  int bAsc = ((idxNum & FTS5_ORDER_ASC) ? 1 : 0);
  int rc = SQLITE_OK;

  assert( nVal<=2 );
  assert( pCsr->pStmt==0 );
  assert( pCsr->pExpr==0 );
  assert( pCsr->csrflags==0 );
  assert( pCsr->pRank==0 );
  assert( pCsr->zRank==0 );
  assert( pCsr->zRankArgs==0 );

  if( pTab->pSortCsr ){
    /* If pSortCsr is non-NULL, then this call is being made as part of 
    ** processing for a "... MATCH <expr> ORDER BY rank" query (ePlan is
    ** set to FTS5_PLAN_SORTED_MATCH). pSortCsr is the cursor that will
    ** return results to the user for this query. The current cursor 
    ** (pCursor) is used to execute the query issued by function 
    ** fts5CursorFirstSorted() above.  */
    assert( FTS5_PLAN(idxNum)==FTS5_PLAN_SCAN );
    pCsr->idxNum = FTS5_PLAN_SOURCE;
    pCsr->pExpr = pTab->pSortCsr->pExpr;
    rc = fts5CursorFirst(pTab, pCsr, bAsc);
  }else{
    int ePlan = FTS5_PLAN(idxNum);
    pCsr->idxNum = idxNum;
    if( ePlan==FTS5_PLAN_MATCH || ePlan==FTS5_PLAN_SORTED_MATCH ){
      const char *zExpr = (const char*)sqlite3_value_text(apVal[0]);

      rc = fts5CursorParseRank(pTab->pConfig, pCsr, (nVal==2 ? apVal[1] : 0));
      if( rc==SQLITE_OK ){
        if( zExpr[0]=='*' ){
          /* The user has issued a query of the form "MATCH '*...'". This
          ** indicates that the MATCH expression is not a full text query,
          ** but a request for an internal parameter.  */
          rc = fts5SpecialMatch(pTab, pCsr, &zExpr[1]);
        }else{
          char **pzErr = &pTab->base.zErrMsg;
          rc = sqlite3Fts5ExprNew(pTab->pConfig, zExpr, &pCsr->pExpr, pzErr);
          if( rc==SQLITE_OK ){
            if( ePlan==FTS5_PLAN_MATCH ){
              rc = fts5CursorFirst(pTab, pCsr, bAsc);
            }else{
              rc = fts5CursorFirstSorted(pTab, pCsr, bAsc);
            }
          }
        }
      }
    }else{
      /* This is either a full-table scan (ePlan==FTS5_PLAN_SCAN) or a lookup
      ** by rowid (ePlan==FTS5_PLAN_ROWID).  */







|




















|


















|

|







869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
  int idxNum,                     /* Strategy index */
  const char *idxStr,             /* Unused */
  int nVal,                       /* Number of elements in apVal */
  sqlite3_value **apVal           /* Arguments for the indexing scheme */
){
  Fts5Table *pTab = (Fts5Table*)(pCursor->pVtab);
  Fts5Cursor *pCsr = (Fts5Cursor*)pCursor;
  int bDesc = ((idxNum & FTS5_ORDER_DESC) ? 1 : 0);
  int rc = SQLITE_OK;

  assert( nVal<=2 );
  assert( pCsr->pStmt==0 );
  assert( pCsr->pExpr==0 );
  assert( pCsr->csrflags==0 );
  assert( pCsr->pRank==0 );
  assert( pCsr->zRank==0 );
  assert( pCsr->zRankArgs==0 );

  if( pTab->pSortCsr ){
    /* If pSortCsr is non-NULL, then this call is being made as part of 
    ** processing for a "... MATCH <expr> ORDER BY rank" query (ePlan is
    ** set to FTS5_PLAN_SORTED_MATCH). pSortCsr is the cursor that will
    ** return results to the user for this query. The current cursor 
    ** (pCursor) is used to execute the query issued by function 
    ** fts5CursorFirstSorted() above.  */
    assert( FTS5_PLAN(idxNum)==FTS5_PLAN_SCAN );
    pCsr->idxNum = FTS5_PLAN_SOURCE;
    pCsr->pExpr = pTab->pSortCsr->pExpr;
    rc = fts5CursorFirst(pTab, pCsr, bDesc);
  }else{
    int ePlan = FTS5_PLAN(idxNum);
    pCsr->idxNum = idxNum;
    if( ePlan==FTS5_PLAN_MATCH || ePlan==FTS5_PLAN_SORTED_MATCH ){
      const char *zExpr = (const char*)sqlite3_value_text(apVal[0]);

      rc = fts5CursorParseRank(pTab->pConfig, pCsr, (nVal==2 ? apVal[1] : 0));
      if( rc==SQLITE_OK ){
        if( zExpr[0]=='*' ){
          /* The user has issued a query of the form "MATCH '*...'". This
          ** indicates that the MATCH expression is not a full text query,
          ** but a request for an internal parameter.  */
          rc = fts5SpecialMatch(pTab, pCsr, &zExpr[1]);
        }else{
          char **pzErr = &pTab->base.zErrMsg;
          rc = sqlite3Fts5ExprNew(pTab->pConfig, zExpr, &pCsr->pExpr, pzErr);
          if( rc==SQLITE_OK ){
            if( ePlan==FTS5_PLAN_MATCH ){
              rc = fts5CursorFirst(pTab, pCsr, bDesc);
            }else{
              rc = fts5CursorFirstSorted(pTab, pCsr, bDesc);
            }
          }
        }
      }
    }else{
      /* This is either a full-table scan (ePlan==FTS5_PLAN_SCAN) or a lookup
      ** by rowid (ePlan==FTS5_PLAN_ROWID).  */
Changes to ext/fts5/fts5Int.h.
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
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_ASC    0x0002       /* Docs in ascending rowid order */

/*
** Create/destroy an Fts5Index object.
*/
int sqlite3Fts5IndexOpen(Fts5Config *pConfig, int bCreate, Fts5Index**, char**);
int sqlite3Fts5IndexClose(Fts5Index *p, int bDestroy);








|







225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
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);

361
362
363
364
365
366
367







368
369
370
371
372
373
374
**************************************************************************/

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







>
>
>
>
>
>
>







361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
**************************************************************************/

/**************************************************************************
** 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(
391
392
393
394
395
396
397





398
399
400
401
402
403
404
  Fts5Hash*,
  void *pCtx,
  int (*xTerm)(void*, const char*, int),
  int (*xEntry)(void*, i64, const u8*, int),
  int (*xTermDone)(void*)
);








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

/**************************************************************************







>
>
>
>
>







398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
  Fts5Hash*,
  void *pCtx,
  int (*xTerm)(void*, const char*, int),
  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.
**************************************************************************/

/**************************************************************************
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
  Fts5Config *pConfig, 
  const char *zExpr,
  Fts5Expr **ppNew, 
  char **pzErr
);

/*
** for(rc = sqlite3Fts5ExprFirst(pExpr, pIdx, bAsc);
**     rc==SQLITE_OK && 0==sqlite3Fts5ExprEof(pExpr);
**     rc = sqlite3Fts5ExprNext(pExpr)
** ){
**   // The document with rowid iRowid matches the expression!
**   i64 iRowid = sqlite3Fts5ExprRowid(pExpr);
** }
*/
int sqlite3Fts5ExprFirst(Fts5Expr*, Fts5Index *pIdx, int bAsc);
int sqlite3Fts5ExprNext(Fts5Expr*);
int sqlite3Fts5ExprEof(Fts5Expr*);
i64 sqlite3Fts5ExprRowid(Fts5Expr*);

void sqlite3Fts5ExprFree(Fts5Expr*);

/* Called during startup to register a UDF with SQLite */







|







|







478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
  Fts5Config *pConfig, 
  const char *zExpr,
  Fts5Expr **ppNew, 
  char **pzErr
);

/*
** for(rc = sqlite3Fts5ExprFirst(pExpr, pIdx, bDesc);
**     rc==SQLITE_OK && 0==sqlite3Fts5ExprEof(pExpr);
**     rc = sqlite3Fts5ExprNext(pExpr)
** ){
**   // The document with rowid iRowid matches the expression!
**   i64 iRowid = sqlite3Fts5ExprRowid(pExpr);
** }
*/
int sqlite3Fts5ExprFirst(Fts5Expr*, Fts5Index *pIdx, int bDesc);
int sqlite3Fts5ExprNext(Fts5Expr*);
int sqlite3Fts5ExprEof(Fts5Expr*);
i64 sqlite3Fts5ExprRowid(Fts5Expr*);

void sqlite3Fts5ExprFree(Fts5Expr*);

/* Called during startup to register a UDF with SQLite */
Changes to ext/fts5/fts5_expr.c.
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void *sqlite3Fts5ParserAlloc(void *(*mallocProc)(size_t));
void sqlite3Fts5ParserFree(void*, void (*freeProc)(void*));
void sqlite3Fts5Parser(void*, int, Fts5Token, Fts5Parse*);

struct Fts5Expr {
  Fts5Index *pIndex;
  Fts5ExprNode *pRoot;
  int bAsc;
  int nPhrase;                    /* Number of phrases in expression */
  Fts5ExprPhrase **apExprPhrase;  /* Pointers to phrase objects */
};

/*
** eType:
**   Expression node type. Always one of:







|







28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void *sqlite3Fts5ParserAlloc(void *(*mallocProc)(size_t));
void sqlite3Fts5ParserFree(void*, void (*freeProc)(void*));
void sqlite3Fts5Parser(void*, int, Fts5Token, Fts5Parse*);

struct Fts5Expr {
  Fts5Index *pIndex;
  Fts5ExprNode *pRoot;
  int bDesc;                      /* Iterate in descending docid order */
  int nPhrase;                    /* Number of phrases in expression */
  Fts5ExprPhrase **apExprPhrase;  /* Pointers to phrase objects */
};

/*
** eType:
**   Expression node type. Always one of:
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
    }
  }

  return SQLITE_OK;
}

/*
** Advance iterator pIter until it points to a value equal to or smaller
** than the initial value of *piMin. If this means the iterator points
** to a value smaller than *piMin, update *piMin to the new smallest value.
**
** If the iterator reaches EOF, set *pbEof to true before returning. If
** an error occurs, set *pRc to an error code. If either *pbEof or *pRc
** are set, return a non-zero value. Otherwise, return zero.
*/
static int fts5ExprAdvanceto(
  Fts5IndexIter *pIter,           /* Iterator to advance */
  int bAsc,                       /* True if iterator is "rowid ASC" */
  i64 *piLast,                    /* IN/OUT: Lastest rowid seen so far */
  int *pRc,                       /* OUT: Error code */
  int *pbEof                      /* OUT: Set to true if EOF */
){
  i64 iLast = *piLast;
  i64 iRowid;

  iRowid = sqlite3Fts5IterRowid(pIter);
  if( (bAsc==0 && iRowid>iLast) || (bAsc && iRowid<iLast) ){
    sqlite3Fts5IterNextFrom(pIter, iLast);
    if( sqlite3Fts5IterEof(pIter) ){
      *pbEof = 1;
      return 1;
    }
    iRowid = sqlite3Fts5IterRowid(pIter);
    assert( (bAsc==0 && iRowid<=iLast) || (bAsc==1 && iRowid>=iLast) );
  }
  *piLast = iRowid;

  return 0;
}

/*







|
|
|







|








|






|







596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
    }
  }

  return SQLITE_OK;
}

/*
** Advance iterator pIter until it points to a value equal to or laster
** than the initial value of *piLast. If this means the iterator points
** to a value laster than *piLast, update *piLast to the new lastest value.
**
** If the iterator reaches EOF, set *pbEof to true before returning. If
** an error occurs, set *pRc to an error code. If either *pbEof or *pRc
** are set, return a non-zero value. Otherwise, return zero.
*/
static int fts5ExprAdvanceto(
  Fts5IndexIter *pIter,           /* Iterator to advance */
  int bDesc,                      /* True if iterator is "rowid DESC" */
  i64 *piLast,                    /* IN/OUT: Lastest rowid seen so far */
  int *pRc,                       /* OUT: Error code */
  int *pbEof                      /* OUT: Set to true if EOF */
){
  i64 iLast = *piLast;
  i64 iRowid;

  iRowid = sqlite3Fts5IterRowid(pIter);
  if( (bDesc==0 && iLast>iRowid) || (bDesc && iLast<iRowid) ){
    sqlite3Fts5IterNextFrom(pIter, iLast);
    if( sqlite3Fts5IterEof(pIter) ){
      *pbEof = 1;
      return 1;
    }
    iRowid = sqlite3Fts5IterRowid(pIter);
    assert( (bDesc==0 && iRowid>=iLast) || (bDesc==1 && iRowid<=iLast) );
  }
  *piLast = iRowid;

  return 0;
}

/*
652
653
654
655
656
657
658
659
660
661
662
663
664

665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
){
  Fts5ExprNearset *pNear = pNode->pNear;
  int rc = SQLITE_OK;
  int i, j;                       /* Phrase and token index, respectively */
  i64 iLast;                      /* Lastest rowid any iterator points to */
  int bMatch;                     /* True if all terms are at the same rowid */

  /* Set iLast, the lastest rowid any iterator points to. If the iterator
  ** skips through rowids in the default descending order, this means the
  ** minimum rowid. Or, if the iterator is "ORDER BY rowid ASC", then it
  ** means the maximum rowid.  */
  iLast = sqlite3Fts5IterRowid(pNear->apPhrase[0]->aTerm[0].pIter);
  if( bFromValid && (iFrom>iLast)==(pExpr->bAsc!=0) ){

    iLast = iFrom;
  }

  do {
    bMatch = 1;
    for(i=0; i<pNear->nPhrase; i++){
      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
      for(j=0; j<pPhrase->nTerm; j++){
        Fts5IndexIter *pIter = pPhrase->aTerm[j].pIter;
        i64 iRowid = sqlite3Fts5IterRowid(pIter);
        if( iRowid!=iLast ) bMatch = 0;
        if( fts5ExprAdvanceto(pIter, pExpr->bAsc, &iLast, &rc, &pNode->bEof) ){
          return rc;
        }
      }
    }
  }while( bMatch==0 );

  pNode->iRowid = iLast;







|
|
|
|

|
>











|







652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
){
  Fts5ExprNearset *pNear = pNode->pNear;
  int rc = SQLITE_OK;
  int i, j;                       /* Phrase and token index, respectively */
  i64 iLast;                      /* Lastest rowid any iterator points to */
  int bMatch;                     /* True if all terms are at the same rowid */

  /* Initialize iLast, the "lastest" rowid any iterator points to. If the
  ** iterator skips through rowids in the default ascending order, this means
  ** the maximum rowid. Or, if the iterator is "ORDER BY rowid DESC", then it
  ** means the minimum rowid.  */
  iLast = sqlite3Fts5IterRowid(pNear->apPhrase[0]->aTerm[0].pIter);
  if( bFromValid && (iFrom>iLast)==(pExpr->bDesc==0) ){
    assert( pExpr->bDesc || iFrom>=iLast );
    iLast = iFrom;
  }

  do {
    bMatch = 1;
    for(i=0; i<pNear->nPhrase; i++){
      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
      for(j=0; j<pPhrase->nTerm; j++){
        Fts5IndexIter *pIter = pPhrase->aTerm[j].pIter;
        i64 iRowid = sqlite3Fts5IterRowid(pIter);
        if( iRowid!=iLast ) bMatch = 0;
        if( fts5ExprAdvanceto(pIter, pExpr->bDesc, &iLast, &rc, &pNode->bEof) ){
          return rc;
        }
      }
    }
  }while( bMatch==0 );

  pNode->iRowid = iLast;
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
  for(i=0; rc==SQLITE_OK && i<pNear->nPhrase; i++){
    pPhrase = pNear->apPhrase[i];
    for(j=0; j<pPhrase->nTerm; j++){
      pTerm = &pPhrase->aTerm[j];
      rc = sqlite3Fts5IndexQuery(
          pExpr->pIndex, pTerm->zTerm, strlen(pTerm->zTerm),
          (pTerm->bPrefix ? FTS5INDEX_QUERY_PREFIX : 0) |
          (pExpr->bAsc ? FTS5INDEX_QUERY_ASC : 0),
          &pTerm->pIter
      );
      assert( rc==SQLITE_OK || pTerm->pIter==0 );
      if( pTerm->pIter==0 || sqlite3Fts5IterEof(pTerm->pIter) ){
        pNode->bEof = 1;
        break;
      }







|







771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
  for(i=0; rc==SQLITE_OK && i<pNear->nPhrase; i++){
    pPhrase = pNear->apPhrase[i];
    for(j=0; j<pPhrase->nTerm; j++){
      pTerm = &pPhrase->aTerm[j];
      rc = sqlite3Fts5IndexQuery(
          pExpr->pIndex, pTerm->zTerm, strlen(pTerm->zTerm),
          (pTerm->bPrefix ? FTS5INDEX_QUERY_PREFIX : 0) |
          (pExpr->bDesc ? FTS5INDEX_QUERY_DESC : 0),
          &pTerm->pIter
      );
      assert( rc==SQLITE_OK || pTerm->pIter==0 );
      if( pTerm->pIter==0 || sqlite3Fts5IterEof(pTerm->pIter) ){
        pNode->bEof = 1;
        break;
      }
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
static int fts5NodeCompare(
  Fts5Expr *pExpr,
  Fts5ExprNode *p1, 
  Fts5ExprNode *p2
){
  if( p2->bEof ) return -1;
  if( p1->bEof ) return +1;
  if( pExpr->bAsc ){
    if( p1->iRowid<p2->iRowid ) return -1;
    return (p1->iRowid > p2->iRowid);
  }else{
    if( p1->iRowid>p2->iRowid ) return -1;
    return (p1->iRowid < p2->iRowid);
  }
}







|







807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
static int fts5NodeCompare(
  Fts5Expr *pExpr,
  Fts5ExprNode *p1, 
  Fts5ExprNode *p2
){
  if( p2->bEof ) return -1;
  if( p1->bEof ) return +1;
  if( pExpr->bDesc==0 ){
    if( p1->iRowid<p2->iRowid ) return -1;
    return (p1->iRowid > p2->iRowid);
  }else{
    if( p1->iRowid>p2->iRowid ) return -1;
    return (p1->iRowid < p2->iRowid);
  }
}
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
        break;
      }

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


        while( p1->bEof==0 && p2->bEof==0 && p2->iRowid!=p1->iRowid ){
          Fts5ExprNode *pAdv;
          assert( pExpr->bAsc==0 || pExpr->bAsc==1 );
          if( pExpr->bAsc==(p1->iRowid < p2->iRowid) ){
            pAdv = p1;
            if( bFromValid==0 || pExpr->bAsc==(p2->iRowid > iFrom) ){
              iFrom = p2->iRowid;
            }
          }else{
            pAdv = p2;
            if( bFromValid==0 || pExpr->bAsc==(p1->iRowid > iFrom) ){
              iFrom = p1->iRowid;
            }
          }
          rc = fts5ExprNodeNext(pExpr, pAdv, 1, iFrom);
          if( rc!=SQLITE_OK ) break;
        }
        if( p1->bEof || p2->bEof ){







<


|
|

|




|







908
909
910
911
912
913
914

915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
        break;
      }

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


        while( p1->bEof==0 && p2->bEof==0 && p2->iRowid!=p1->iRowid ){
          Fts5ExprNode *pAdv;
          assert( pExpr->bDesc==0 || pExpr->bDesc==1 );
          if( pExpr->bDesc==(p1->iRowid > p2->iRowid) ){
            pAdv = p1;
            if( bFromValid==0 || pExpr->bDesc==(p2->iRowid < iFrom) ){
              iFrom = p2->iRowid;
            }
          }else{
            pAdv = p2;
            if( bFromValid==0 || pExpr->bDesc==(p1->iRowid < iFrom) ){
              iFrom = p1->iRowid;
            }
          }
          rc = fts5ExprNodeNext(pExpr, pAdv, 1, iFrom);
          if( rc!=SQLITE_OK ) break;
        }
        if( p1->bEof || p2->bEof ){
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
  return rc;
}



/*
** Begin iterating through the set of documents in index pIdx matched by
** the MATCH expression passed as the first argument. If the "bAsc" parameter
** is passed a non-zero value, iteration is in ascending rowid order. Or,
** if it is zero, in descending order.
**
** Return SQLITE_OK if successful, or an SQLite error code otherwise. It
** is not considered an error if the query does not match any documents.
*/
int sqlite3Fts5ExprFirst(Fts5Expr *p, Fts5Index *pIdx, int bAsc){
  int rc = SQLITE_OK;
  if( p->pRoot ){
    p->pIndex = pIdx;
    p->bAsc = bAsc;
    rc = fts5ExprNodeFirst(p, p->pRoot);
  }
  return rc;
}

/*
** Move to the next document 







|
|
|




|



|







999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
  return rc;
}



/*
** Begin iterating through the set of documents in index pIdx matched by
** the MATCH expression passed as the first argument. If the "bDesc" parameter
** is passed a non-zero value, iteration is in descending rowid order. Or,
** if it is zero, in ascending order.
**
** Return SQLITE_OK if successful, or an SQLite error code otherwise. It
** is not considered an error if the query does not match any documents.
*/
int sqlite3Fts5ExprFirst(Fts5Expr *p, Fts5Index *pIdx, int bDesc){
  int rc = SQLITE_OK;
  if( p->pRoot ){
    p->pIndex = pIdx;
    p->bDesc = bDesc;
    rc = fts5ExprNodeFirst(p, p->pRoot);
  }
  return rc;
}

/*
** Move to the next document 
Changes to ext/fts5/fts5_hash.c.
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66










67
68
69
70
71
72
73
** 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 iRowidOff;                  /* Offset of last rowid written */
  int nData;                      /* Total bytes of data (incl. structure) */

  int iCol;                       /* Column of last value written */
  int iPos;                       /* Position of last value written */
  i64 iRowid;                     /* Rowid of last value written */
  char zKey[0];                   /* Nul-terminated entry key */
};












/*
** Allocate a new hash table.
*/
int sqlite3Fts5HashNew(Fts5Hash **ppNew, int *pnByte){
  int rc = SQLITE_OK;
  Fts5Hash *pNew;







|








>
>
>
>
>
>
>
>
>
>







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
** 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 */
  i64 iRowid;                     /* Rowid of last value written */
  char zKey[0];                   /* Nul-terminated entry key */
};

/*
** Format value iVal as a 4-byte varint and write it to buffer a[]. 4 bytes
** are used even if the value could fit in a smaller amount of space. 
*/
static void fts5Put4ByteVarint(u8 *a, int iVal){
  a[0] = (0x80 | (u8)(iVal >> 21));
  a[1] = (0x80 | (u8)(iVal >> 14));
  a[2] = (0x80 | (u8)(iVal >>  7));
  a[3] = (0x7F & (u8)(iVal));
}

/*
** Allocate a new hash table.
*/
int sqlite3Fts5HashNew(Fts5Hash **ppNew, int *pnByte){
  int rc = SQLITE_OK;
  Fts5Hash *pNew;
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

  sqlite3_free(apOld);
  pHash->nSlot = nNew;
  pHash->aSlot = apNew;
  return SQLITE_OK;
}

/*
** Store the 32-bit integer passed as the second argument in buffer p.
*/
static int fts5PutNativeInt(u8 *p, int i){
  assert( sizeof(i)==4 );
  memcpy(p, &i, sizeof(i));
  return sizeof(i);
}

/*
** Read and return the 32-bit integer stored in buffer p.
*/
static int fts5GetNativeU32(u8 *p){
  int i;
  assert( sizeof(i)==4 );
  memcpy(&i, p, sizeof(i));
  return i;
}

int sqlite3Fts5HashWrite(
  Fts5Hash *pHash,
  i64 iRowid,                     /* Rowid for this entry */
  int iCol,                       /* Column token appears in (-ve -> delete) */
  int iPos,                       /* Position of token within column */
  const char *pToken, int nToken  /* Token to add or remove to or from index */
){
  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 object */
  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;







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












|







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

  sqlite3_free(apOld);
  pHash->nSlot = nNew;
  pHash->aSlot = apNew;
  return SQLITE_OK;
}




















int sqlite3Fts5HashWrite(
  Fts5Hash *pHash,
  i64 iRowid,                     /* Rowid for this entry */
  int iCol,                       /* Column token appears in (-ve -> delete) */
  int iPos,                       /* Position of token within column */
  const char *pToken, int nToken  /* Token to add or remove to or from index */
){
  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;
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

    p = (Fts5HashEntry*)sqlite3_malloc(nByte);
    if( !p ) return SQLITE_NOMEM;
    memset(p, 0, sizeof(Fts5HashEntry));
    p->nAlloc = nByte;
    memcpy(p->zKey, pToken, nToken);
    p->zKey[nToken] = '\0';
    p->iRowidOff = p->nData = nToken + 1 + sizeof(Fts5HashEntry);
    p->nData += sqlite3PutVarint(&((u8*)p)[p->nData], iRowid);


    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:
  **
  **     + 4 bytes for the previous entry size field,
  **     + 9 bytes for a new rowid,

  **     + 1 byte for a "new column" byte,
  **     + 3 bytes for a new column number (16-bit max) as a varint,
  **     + 5 bytes for the new position offset (32-bit max).
  */
  if( (p->nAlloc - p->nData) < (4 + 9 + 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
  ** entry, and the new rowid for this entry.  */
  if( iRowid!=p->iRowid ){


    p->nData += fts5PutNativeInt(&pPtr[p->nData], p->nData - p->iRowidOff);
    p->iRowidOff = p->nData;
    p->nData += sqlite3PutVarint(&pPtr[p->nData], iRowid);
    p->iCol = 0;
    p->iPos = 0;
    p->iRowid = iRowid;
  }

  if( iCol>=0 ){
    /* Append a new column value, if necessary */







|

>
>




<






<

>




|
















>
>
|
|
|







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

    p = (Fts5HashEntry*)sqlite3_malloc(nByte);
    if( !p ) return SQLITE_NOMEM;
    memset(p, 0, sizeof(Fts5HashEntry));
    p->nAlloc = nByte;
    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:
  **

  **     + 9 bytes for a new rowid,
  **     + 4 bytes reserved for the "poslist size" varint.
  **     + 1 byte for a "new column" byte,
  **     + 3 bytes for a new column number (16-bit max) as a varint,
  **     + 5 bytes for the new position offset (32-bit max).
  */
  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
  ** entry, and the new rowid for this entry.  */
  if( iRowid!=p->iRowid ){
    assert( p->iSzPoslist>0 );
    fts5Put4ByteVarint(&pPtr[p->iSzPoslist], p->nData - p->iSzPoslist - 4);
    p->nData += sqlite3PutVarint(&pPtr[p->nData], iRowid - p->iRowid);
    p->iSzPoslist = p->nData;
    p->nData += 4;
    p->iCol = 0;
    p->iPos = 0;
    p->iRowid = iRowid;
  }

  if( iCol>=0 ){
    /* Append a new column value, if necessary */
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
  int rc;

  rc = fts5HashEntrySort(pHash, &pList);
  if( rc==SQLITE_OK ){
    while( pList ){
      Fts5HashEntry *pNext = pList->pNext;
      if( rc==SQLITE_OK ){
        u8 *pPtr = (u8*)pList;
        int nKey = strlen(pList->zKey);
        int iOff = pList->iRowidOff;

        int iEnd = sizeof(Fts5HashEntry) + nKey + 1;
        int nByte = pList->nData - pList->iRowidOff;




        rc = xTerm(pCtx, pList->zKey, nKey);


        while( rc==SQLITE_OK && iOff ){


          int nVarint;
          i64 iRowid;
          nVarint = getVarint(&pPtr[iOff], (u64*)&iRowid);
          rc = xEntry(pCtx, iRowid, &pPtr[iOff+nVarint], nByte-nVarint);
          if( iOff==iEnd ){
            iOff = 0;
          }else{
            nByte = fts5GetNativeU32(&pPtr[iOff-sizeof(int)]);
            iOff = iOff - sizeof(int) - nByte;
          }
        }

        if( rc==SQLITE_OK ){
          rc = xTermDone(pCtx);
        }
      }
      sqlite3_free(pList);
      pList = pNext;
    }
  }
  return rc;
}










|
|
|
>
|
|
>
>

>

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

|
>
|
<
<








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


  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;

        /* Fill in the final poslist size field */
        fts5Put4ByteVarint(&pPtr[pList->iSzPoslist], nSz);

        /* Issue the new-term callback */
        rc = xTerm(pCtx, pList->zKey, nKey);

        /* Issue the xEntry callbacks */
        while( rc==SQLITE_OK && iOff<pList->nData ){
          i64 iDelta;             /* Rowid delta value */
          int nPoslist;           /* Size of position list in bytes */
          iOff += getVarint(&pPtr[iOff], (u64*)&iDelta);
          iRowid += iDelta;
          iOff += fts5GetVarint32(&pPtr[iOff], nPoslist);
          rc = xEntry(pCtx, iRowid, &pPtr[iOff], nPoslist);

          iOff += nPoslist;



          }

        /* Issue the term-done callback */
        if( rc==SQLITE_OK ) rc = xTermDone(pCtx);


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



Changes to ext/fts5/fts5_index.c.
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
**     incremental merge operations.
**
*/

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

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

/*
** Details:
**
** The %_data table managed by this module,
**
**     CREATE TABLE %_data(id INTEGER PRIMARY KEY, block BLOB);







|







40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
**     incremental merge operations.
**
*/

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

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

/*
** Details:
**
** The %_data table managed by this module,
**
**     CREATE TABLE %_data(id INTEGER PRIMARY KEY, block BLOB);
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
** 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;







<







266
267
268
269
270
271
272

273
274
275
276
277
278
279
** 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;
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
  sqlite3_blob *pReader;          /* RO incr-blob open on %_data table */
  sqlite3_stmt *pWriter;          /* "INSERT ... %_data VALUES(?,?)" */
  sqlite3_stmt *pDeleter;         /* "DELETE FROM %_data ... id>=? AND id<=?" */
  int nRead;                      /* Total number of blocks read */
};

struct Fts5DoclistIter {
  int bAsc;
  u8 *a;
  int n;
  int i;

  /* Output variables. aPoslist==0 at EOF */
  i64 iRowid;
  u8 *aPoslist;







|







306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
  sqlite3_blob *pReader;          /* RO incr-blob open on %_data table */
  sqlite3_stmt *pWriter;          /* "INSERT ... %_data VALUES(?,?)" */
  sqlite3_stmt *pDeleter;         /* "DELETE FROM %_data ... id>=? AND id<=?" */
  int nRead;                      /* Total number of blocks read */
};

struct Fts5DoclistIter {
  int bDesc;                      /* True for DESC order, false for ASC */
  u8 *a;
  int n;
  int i;

  /* Output variables. aPoslist==0 at EOF */
  i64 iRowid;
  u8 *aPoslist;
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
  Fts5Index *pIndex;
  Fts5Structure *pStruct;
  Fts5MultiSegIter *pMulti;
  Fts5DoclistIter *pDoclist;
  Fts5Buffer poslist;             /* Buffer containing current poslist */
};

/*
** A single record read from the %_data table.
*/
struct Fts5Data {
  u8 *p;                          /* Pointer to buffer containing record */
  int n;                          /* Size of record in bytes */
  int nRef;                       /* Ref count */
};

/*
** The contents of the "structure" record for each index are represented
** using an Fts5Structure record in memory. Which uses instances of the 
** other Fts5StructureXXX types as components.
*/
struct Fts5StructureSegment {
  int iSegid;                     /* Segment id */







<
<
<
<
<
<
<
<
<







328
329
330
331
332
333
334









335
336
337
338
339
340
341
  Fts5Index *pIndex;
  Fts5Structure *pStruct;
  Fts5MultiSegIter *pMulti;
  Fts5DoclistIter *pDoclist;
  Fts5Buffer poslist;             /* Buffer containing current poslist */
};










/*
** The contents of the "structure" record for each index are represented
** using an Fts5Structure record in memory. Which uses instances of the 
** other Fts5StructureXXX types as components.
*/
struct Fts5StructureSegment {
  int iSegid;                     /* Segment id */
1478
1479
1480
1481
1482
1483
1484





1485
1486
1487
1488
1489
1490
1491
*/
static void fts5DlidxIterFree(Fts5DlidxIter *pIter){
  if( pIter ){
    fts5DataRelease(pIter->pData);
    sqlite3_free(pIter);
  }
}






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







>
>
>
>
>







1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
*/
static void fts5DlidxIterFree(Fts5DlidxIter *pIter){
  if( pIter ){
    fts5DataRelease(pIter->pData);
    sqlite3_free(pIter);
  }
}

static void fts5LeafHeader(Fts5Data *pLeaf, int *piRowid, int *piTerm){
  *piRowid = (int)fts5GetU16(&pLeaf->p[0]);
  *piTerm = (int)fts5GetU16(&pLeaf->p[2]);
}

/*
** 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 */
1499
1500
1501
1502
1503
1504
1505



1506



1507

1508
1509
1510
1511
1512
1513
1514
    );
  }else{
    pIter->pLeaf = 0;
  }
}

/*



** Leave pIter->iLeafOffset as the offset to the size field of the first



** position list. The position list belonging to document pIter->iRowid.

*/
static void fts5SegIterLoadTerm(Fts5Index *p, Fts5SegIter *pIter, int nKeep){
  u8 *a = pIter->pLeaf->p;        /* Buffer to read data from */
  int iOff = pIter->iLeafOffset;  /* Offset to read at */
  int nNew;                       /* Bytes of new data */

  iOff += fts5GetVarint32(&a[iOff], nNew);







>
>
>
|
>
>
>
|
>







1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
    );
  }else{
    pIter->pLeaf = 0;
  }
}

/*
** Fts5SegIter.iLeafOffset currently points to the first byte of the 
** "nSuffix" field of a term. Function parameter nKeep contains the value
** of the "nPrefix" field (if there was one - it is passed 0 if this is
** the first term in the segment).
**
** This function populates (Fts5SegIter.term) and (Fts5SegIter.iRowid)
** accordingly and leaves (Fts5SegIter.iLeafOffset) set to the offset to 
** the size field of the first position list. The position list belonging 
** to document (Fts5SegIter.iRowid).
*/
static void fts5SegIterLoadTerm(Fts5Index *p, Fts5SegIter *pIter, int nKeep){
  u8 *a = pIter->pLeaf->p;        /* Buffer to read data from */
  int iOff = pIter->iLeafOffset;  /* Offset to read at */
  int nNew;                       /* Bytes of new data */

  iOff += fts5GetVarint32(&a[iOff], nNew);
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
  if( p->rc==SQLITE_OK ){
    u8 *a = pIter->pLeaf->p;
    pIter->iLeafOffset = fts5GetU16(&a[2]);
    fts5SegIterLoadTerm(p, pIter, 0);
  }
}

static void fts5LeafHeader(Fts5Data *pLeaf, int *piRowid, int *piTerm){
  *piRowid = (int)fts5GetU16(&pLeaf->p[0]);
  *piTerm = (int)fts5GetU16(&pLeaf->p[2]);
}

/*
** This function is only ever called on iterators created by calls to
** Fts5IndexQuery() with the FTS5INDEX_QUERY_ASC flag set.
**
** When this function is called, iterator pIter points to the first rowid
** on the current leaf associated with the term being queried. This function
** advances it to point to the last such rowid and, if necessary, initializes







<
<
<
<
<







1567
1568
1569
1570
1571
1572
1573





1574
1575
1576
1577
1578
1579
1580
  if( p->rc==SQLITE_OK ){
    u8 *a = pIter->pLeaf->p;
    pIter->iLeafOffset = fts5GetU16(&a[2]);
    fts5SegIterLoadTerm(p, pIter, 0);
  }
}






/*
** This function is only ever called on iterators created by calls to
** Fts5IndexQuery() with the FTS5INDEX_QUERY_ASC flag set.
**
** When this function is called, iterator pIter points to the first rowid
** on the current leaf associated with the term being queried. This function
** advances it to point to the last such rowid and, if necessary, initializes
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
    int nPos;

    i += fts5GetVarint32(&a[i], nPos);
    i += nPos;
    if( i>=n ) break;
    i += getVarint(&a[i], (u64*)&iDelta);
    if( iDelta==0 ) break;
    pIter->iRowid -= iDelta;

    if( iRowidOffset>=pIter->nRowidOffset ){
      int nNew = pIter->nRowidOffset + 8;
      int *aNew = (int*)sqlite3_realloc(pIter->aRowidOffset, nNew*sizeof(int));
      if( aNew==0 ){
        p->rc = SQLITE_NOMEM;
        break;







|







1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
    int nPos;

    i += fts5GetVarint32(&a[i], nPos);
    i += nPos;
    if( i>=n ) break;
    i += getVarint(&a[i], (u64*)&iDelta);
    if( iDelta==0 ) break;
    pIter->iRowid += iDelta;

    if( iRowidOffset>=pIter->nRowidOffset ){
      int nNew = pIter->nRowidOffset + 8;
      int *aNew = (int*)sqlite3_realloc(pIter->aRowidOffset, nNew*sizeof(int));
      if( aNew==0 ){
        p->rc = SQLITE_NOMEM;
        break;
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
  int bRet = 0;
  Fts5Data *pLeaf = pIter->pLeaf;
  if( p->rc==SQLITE_OK && pLeaf ){
    if( pIter->iLeafOffset<pLeaf->n ){
      bRet = (pLeaf->p[pIter->iLeafOffset]==0x00);
    }else{
      Fts5Data *pNew = fts5DataRead(p, FTS5_SEGMENT_ROWID(
            pIter->iIdx, pIter->pSeg->iSegid, 0, pIter->iLeafPgno
      ));
      if( pNew ){
        bRet = (pNew->p[4]==0x00);
        fts5DataRelease(pNew);
      }
    }
  }







|







1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
  int bRet = 0;
  Fts5Data *pLeaf = pIter->pLeaf;
  if( p->rc==SQLITE_OK && pLeaf ){
    if( pIter->iLeafOffset<pLeaf->n ){
      bRet = (pLeaf->p[pIter->iLeafOffset]==0x00);
    }else{
      Fts5Data *pNew = fts5DataRead(p, FTS5_SEGMENT_ROWID(
            pIter->iIdx, pIter->pSeg->iSegid, 0, pIter->iLeafPgno+1
      ));
      if( pNew ){
        bRet = (pNew->p[4]==0x00);
        fts5DataRelease(pNew);
      }
    }
  }
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
        i64 iDelta;
        pIter->iRowidOffset--;

        pIter->iLeafOffset = iOff = pIter->aRowidOffset[pIter->iRowidOffset];
        iOff += fts5GetVarint32(&a[iOff], nPos);
        iOff += nPos;
        getVarint(&a[iOff], (u64*)&iDelta);
        pIter->iRowid += iDelta;
      }else{
        fts5SegIterReverseNewPage(p, pIter);
      }
    }else{
      Fts5Data *pLeaf = pIter->pLeaf;
      int iOff;
      int bNewTerm = 0;







|







1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
        i64 iDelta;
        pIter->iRowidOffset--;

        pIter->iLeafOffset = iOff = pIter->aRowidOffset[pIter->iRowidOffset];
        iOff += fts5GetVarint32(&a[iOff], nPos);
        iOff += nPos;
        getVarint(&a[iOff], (u64*)&iDelta);
        pIter->iRowid -= iDelta;
      }else{
        fts5SegIterReverseNewPage(p, pIter);
      }
    }else{
      Fts5Data *pLeaf = pIter->pLeaf;
      int iOff;
      int bNewTerm = 0;
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
          if( iOff>=n ){
            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;







|







1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
          if( iOff>=n ){
            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;
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
  Fts5SegIter *pIter              /* Object to populate */
){
  int iPg = 1;
  int h;
  int bGe = ((flags & FTS5INDEX_QUERY_PREFIX) && iIdx==0);
  int bDlidx = 0;                 /* True if there is a doclist-index */

  assert( bGe==0 || (flags & FTS5INDEX_QUERY_ASC)==0 );
  assert( pTerm && nTerm );
  memset(pIter, 0, sizeof(*pIter));
  pIter->pSeg = pSeg;
  pIter->iIdx = iIdx;

  /* This block sets stack variable iPg to the leaf page number that may
  ** contain term (pTerm/nTerm), if it is present in the segment. */







|







1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
  Fts5SegIter *pIter              /* Object to populate */
){
  int iPg = 1;
  int h;
  int bGe = ((flags & FTS5INDEX_QUERY_PREFIX) && iIdx==0);
  int bDlidx = 0;                 /* True if there is a doclist-index */

  assert( bGe==0 || (flags & FTS5INDEX_QUERY_DESC)==0 );
  assert( pTerm && nTerm );
  memset(pIter, 0, sizeof(*pIter));
  pIter->pSeg = pSeg;
  pIter->iIdx = iIdx;

  /* This block sets stack variable iPg to the leaf page number that may
  ** contain term (pTerm/nTerm), if it is present in the segment. */
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
      pIter->pLeaf = 0;
    }
  }

  if( p->rc==SQLITE_OK && bGe==0 ){
    pIter->flags |= FTS5_SEGITER_ONETERM;
    if( pIter->pLeaf ){
      if( flags & FTS5INDEX_QUERY_ASC ){
        pIter->flags |= FTS5_SEGITER_REVERSE;
      }
      if( bDlidx ){
        fts5SegIterLoadDlidx(p, iIdx, pIter);
      }
      if( flags & FTS5INDEX_QUERY_ASC ){
        fts5SegIterReverse(p, iIdx, pIter);
      }
    }
  }
}

/*







|





|







1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
      pIter->pLeaf = 0;
    }
  }

  if( p->rc==SQLITE_OK && bGe==0 ){
    pIter->flags |= FTS5_SEGITER_ONETERM;
    if( pIter->pLeaf ){
      if( flags & FTS5INDEX_QUERY_DESC ){
        pIter->flags |= FTS5_SEGITER_REVERSE;
      }
      if( bDlidx ){
        fts5SegIterLoadDlidx(p, iIdx, pIter);
      }
      if( flags & FTS5INDEX_QUERY_DESC ){
        fts5SegIterReverse(p, iIdx, pIter);
      }
    }
  }
}

/*
2038
2039
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
    iRes = i1;
  }else{
    int res = fts5BufferCompare(&p1->term, &p2->term);
    if( res==0 ){
      assert( i2>i1 );
      assert( i2!=0 );
      if( p1->iRowid==p2->iRowid ) return i2;
      res = ((p1->iRowid < p2->iRowid)==pIter->bRev) ? -1 : +1;
    }
    assert( res!=0 );
    if( res<0 ){
      iRes = i1;
    }else{
      iRes = i2;
    }
  }

  pIter->aFirst[iOut] = iRes;
  return 0;
}

/*
** Free the iterator object passed as the second argument.
*/
static void fts5MultiIterFree(Fts5Index *p, Fts5MultiSegIter *pIter){
  if( pIter ){
    int i;
    for(i=0; i<pIter->nSeg; i++){
      fts5SegIterClear(&pIter->aSeg[i]);
    }
    sqlite3_free(pIter);
  }
}

static void fts5MultiIterAdvanced(
  Fts5Index *p,                   /* FTS5 backend to iterate within */
  Fts5MultiSegIter *pIter,        /* Iterator to update aFirst[] array for */
  int iChanged,                   /* Index of sub-iterator just advanced */
  int iMinset                     /* Minimum entry in aFirst[] to set */
){
  int i;
  for(i=(pIter->nSeg+iChanged)/2; i>=iMinset && p->rc==SQLITE_OK; i=i/2){
    int iEq;
    if( (iEq = fts5MultiIterDoCompare(pIter, i)) ){
      fts5SegIterNext(p, &pIter->aSeg[iEq]);
      i = pIter->nSeg + iEq;
    }
  }
}

/*
** Move the seg-iter so that it points to the first rowid on page iLeafPgno.
** It is an error if leaf iLeafPgno contains no rowid.
*/
static void fts5SegIterGotoPage(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5SegIter *pIter,             /* Iterator to advance */







|













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







2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055





























2056
2057
2058
2059
2060
2061
2062
    iRes = i1;
  }else{
    int res = fts5BufferCompare(&p1->term, &p2->term);
    if( res==0 ){
      assert( i2>i1 );
      assert( i2!=0 );
      if( p1->iRowid==p2->iRowid ) return i2;
      res = ((p1->iRowid > p2->iRowid)==pIter->bRev) ? -1 : +1;
    }
    assert( res!=0 );
    if( res<0 ){
      iRes = i1;
    }else{
      iRes = i2;
    }
  }

  pIter->aFirst[iOut] = iRes;
  return 0;
}






























/*
** Move the seg-iter so that it points to the first rowid on page iLeafPgno.
** It is an error if leaf iLeafPgno contains no rowid.
*/
static void fts5SegIterGotoPage(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5SegIter *pIter,             /* Iterator to advance */
2166
2167
2168
2169
2170
2171
2172






























2173
2174
2175
2176
2177
2178
2179
    if( pIter->pLeaf==0 ) break;
    if( bRev==0 && pIter->iRowid<=iMatch ) break;
    if( bRev!=0 && pIter->iRowid>=iMatch ) break;
    bMove = 1;
  }
}































/*
** Move the iterator to the next entry. 
**
** If an error occurs, an error code is left in Fts5Index.rc. It is not 
** considered an error if the iterator reaches EOF, or if it is already at 
** EOF when this function is called.
*/







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







2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
    if( pIter->pLeaf==0 ) break;
    if( bRev==0 && pIter->iRowid<=iMatch ) break;
    if( bRev!=0 && pIter->iRowid>=iMatch ) break;
    bMove = 1;
  }
}


/*
** Free the iterator object passed as the second argument.
*/
static void fts5MultiIterFree(Fts5Index *p, Fts5MultiSegIter *pIter){
  if( pIter ){
    int i;
    for(i=0; i<pIter->nSeg; i++){
      fts5SegIterClear(&pIter->aSeg[i]);
    }
    sqlite3_free(pIter);
  }
}

static void fts5MultiIterAdvanced(
  Fts5Index *p,                   /* FTS5 backend to iterate within */
  Fts5MultiSegIter *pIter,        /* Iterator to update aFirst[] array for */
  int iChanged,                   /* Index of sub-iterator just advanced */
  int iMinset                     /* Minimum entry in aFirst[] to set */
){
  int i;
  for(i=(pIter->nSeg+iChanged)/2; i>=iMinset && p->rc==SQLITE_OK; i=i/2){
    int iEq;
    if( (iEq = fts5MultiIterDoCompare(pIter, i)) ){
      fts5SegIterNext(p, &pIter->aSeg[iEq]);
      i = pIter->nSeg + iEq;
    }
  }
}

/*
** Move the iterator to the next entry. 
**
** If an error occurs, an error code is left in Fts5Index.rc. It is not 
** considered an error if the iterator reaches EOF, or if it is already at 
** EOF when this function is called.
*/
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
      sizeof(Fts5SegIter) * nSlot +       /* pNew->aSeg[] */
      sizeof(u16) * nSlot                 /* pNew->aFirst[] */
  );
  if( pNew==0 ) return;
  pNew->nSeg = nSlot;
  pNew->aSeg = (Fts5SegIter*)&pNew[1];
  pNew->aFirst = (u16*)&pNew->aSeg[nSlot];
  pNew->bRev = (0!=(flags & FTS5INDEX_QUERY_ASC));
  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--){







|







2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
      sizeof(Fts5SegIter) * nSlot +       /* pNew->aSeg[] */
      sizeof(u16) * nSlot                 /* pNew->aFirst[] */
  );
  if( pNew==0 ) return;
  pNew->nSeg = nSlot;
  pNew->aSeg = (Fts5SegIter*)&pNew[1];
  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--){
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
  i64 iMatch
){
  while( 1 ){
    i64 iRowid;
    fts5MultiIterNext(p, pIter, 1, iMatch);
    if( fts5MultiIterEof(p, pIter) ) break;
    iRowid = fts5MultiIterRowid(pIter);
    if( pIter->bRev==0 && iRowid<=iMatch ) break;
    if( pIter->bRev!=0 && iRowid>=iMatch ) break;
  }
}

/*
** Return a pointer to a buffer containing the term associated with the 
** entry that the iterator currently points to.
*/







|
|







2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
  i64 iMatch
){
  while( 1 ){
    i64 iRowid;
    fts5MultiIterNext(p, pIter, 1, iMatch);
    if( fts5MultiIterEof(p, pIter) ) break;
    iRowid = fts5MultiIterRowid(pIter);
    if( pIter->bRev==0 && iRowid>=iMatch ) break;
    if( pIter->bRev!=0 && iRowid<=iMatch ) break;
  }
}

/*
** Return a pointer to a buffer containing the term associated with the 
** entry that the iterator currently points to.
*/
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
      fts5WriteDlidxAppend(p, pWriter, iRowid);
    }

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

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







|
|







2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
      fts5WriteDlidxAppend(p, pWriter, iRowid);
    }

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

    if( pPage->buf.n>=p->pConfig->pgsz ){
      fts5WriteFlushLeaf(p, pWriter);
3707
3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
3723
3724
3725
3726
3727
3728
3729
3730
3731
3732
3733
3734
3735
3736
3737
3738
3739
3740
3741
3742
3743
3744
3745
3746
3747
3748
3749
3750
3751
3752
3753
3754
3755
3756
3757
3758
3759
3760
3761
3762
3763
3764
3765
3766
3767
3768
3769
3770
3771
3772
3773
3774
3775
3776
3777
3778
3779
3780
3781
3782
3783
3784
3785
3786
3787
3788
3789
3790
3791
3792
3793
3794
3795
3796
3797
3798
3799
3800
3801
3802
3803
3804
3805
3806
3807
3808
3809
3810
3811
3812
3813
3814
3815
3816
3817
3818
3819
}

static void fts5DoclistIterNext(Fts5DoclistIter *pIter){
  if( pIter->i<pIter->n ){
    if( pIter->i ){
      i64 iDelta;
      pIter->i += getVarint(&pIter->a[pIter->i], (u64*)&iDelta);
      if( pIter->bAsc ){
        pIter->iRowid += iDelta;
      }else{
        pIter->iRowid -= iDelta;
      }
    }else{
      pIter->i += getVarint(&pIter->a[pIter->i], (u64*)&pIter->iRowid);
    }
    pIter->i += fts5GetVarint32(&pIter->a[pIter->i], pIter->nPoslist);
    pIter->aPoslist = &pIter->a[pIter->i];
    pIter->i += pIter->nPoslist;
  }else{
    pIter->aPoslist = 0;
  }
}

static void fts5DoclistIterInit(
  Fts5Buffer *pBuf, 
  int bAsc, 
  Fts5DoclistIter *pIter
){
  memset(pIter, 0, sizeof(*pIter));
  pIter->a = pBuf->p;
  pIter->n = pBuf->n;
  pIter->bAsc = bAsc;
  fts5DoclistIterNext(pIter);
}

/*
** Append a doclist to buffer pBuf.
*/
static void fts5MergeAppendDocid(
  int *pRc,                       /* IN/OUT: Error code */
  int bAsc,
  Fts5Buffer *pBuf,               /* Buffer to write to */
  i64 *piLastRowid,               /* IN/OUT: Previous rowid written (if any) */
  i64 iRowid                      /* Rowid to append */
){
  if( pBuf->n==0 ){
    fts5BufferAppendVarint(pRc, pBuf, iRowid);
  }else if( bAsc==0 ){
    fts5BufferAppendVarint(pRc, pBuf, *piLastRowid - iRowid);
  }else{
    fts5BufferAppendVarint(pRc, pBuf, iRowid - *piLastRowid);
  }
  *piLastRowid = iRowid;
}

/*
** Buffers p1 and p2 contain doclists. This function merges the content
** of the two doclists together and sets buffer p1 to the result before
** returning.
**
** If an error occurs, an error code is left in p->rc. If an error has
** already occurred, this function is a no-op.
*/
static void fts5MergePrefixLists(
  Fts5Index *p,                   /* FTS5 backend object */
  int bAsc,
  Fts5Buffer *p1,                 /* First list to merge */
  Fts5Buffer *p2                  /* Second list to merge */
){
  if( p2->n ){
    i64 iLastRowid = 0;
    Fts5DoclistIter i1;
    Fts5DoclistIter i2;
    Fts5Buffer out;
    Fts5Buffer tmp;
    memset(&out, 0, sizeof(out));
    memset(&tmp, 0, sizeof(tmp));

    fts5DoclistIterInit(p1, bAsc, &i1);
    fts5DoclistIterInit(p2, bAsc, &i2);
    while( i1.aPoslist!=0 || i2.aPoslist!=0 ){
      if( i2.aPoslist==0 || (i1.aPoslist && 
           ( (!bAsc && i1.iRowid>i2.iRowid) || (bAsc && i1.iRowid<i2.iRowid) )
      )){
        /* Copy entry from i1 */
        fts5MergeAppendDocid(&p->rc, bAsc, &out, &iLastRowid, i1.iRowid);
        fts5BufferAppendVarint(&p->rc, &out, i1.nPoslist);
        fts5BufferAppendBlob(&p->rc, &out, i1.nPoslist, i1.aPoslist);
        fts5DoclistIterNext(&i1);
      }
      else if( i1.aPoslist==0 || i2.iRowid!=i1.iRowid ){
        /* Copy entry from i2 */
        fts5MergeAppendDocid(&p->rc, bAsc, &out, &iLastRowid, i2.iRowid);
        fts5BufferAppendVarint(&p->rc, &out, i2.nPoslist);
        fts5BufferAppendBlob(&p->rc, &out, i2.nPoslist, i2.aPoslist);
        fts5DoclistIterNext(&i2);
      }
      else{
        Fts5PoslistReader r1;
        Fts5PoslistReader r2;
        Fts5PoslistWriter writer;

        memset(&writer, 0, sizeof(writer));

        /* Merge the two position lists. */ 
        fts5MergeAppendDocid(&p->rc, bAsc, &out, &iLastRowid, i2.iRowid);
        fts5BufferZero(&tmp);
        sqlite3Fts5PoslistReaderInit(-1, i1.aPoslist, i1.nPoslist, &r1);
        sqlite3Fts5PoslistReaderInit(-1, i2.aPoslist, i2.nPoslist, &r2);
        while( p->rc==SQLITE_OK && (r1.bEof==0 || r2.bEof==0) ){
          i64 iNew;
          if( r2.bEof || (r1.bEof==0 && r1.iPos<r2.iPos) ){
            iNew = r1.iPos;







|
|

|














|





|








|






|

















|












|
|


|


|






|












|







3705
3706
3707
3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
3723
3724
3725
3726
3727
3728
3729
3730
3731
3732
3733
3734
3735
3736
3737
3738
3739
3740
3741
3742
3743
3744
3745
3746
3747
3748
3749
3750
3751
3752
3753
3754
3755
3756
3757
3758
3759
3760
3761
3762
3763
3764
3765
3766
3767
3768
3769
3770
3771
3772
3773
3774
3775
3776
3777
3778
3779
3780
3781
3782
3783
3784
3785
3786
3787
3788
3789
3790
3791
3792
3793
3794
3795
3796
3797
3798
3799
3800
3801
3802
3803
3804
3805
3806
3807
3808
3809
3810
3811
3812
3813
3814
3815
3816
3817
}

static void fts5DoclistIterNext(Fts5DoclistIter *pIter){
  if( pIter->i<pIter->n ){
    if( pIter->i ){
      i64 iDelta;
      pIter->i += getVarint(&pIter->a[pIter->i], (u64*)&iDelta);
      if( pIter->bDesc ){
        pIter->iRowid -= iDelta;
      }else{
        pIter->iRowid += iDelta;
      }
    }else{
      pIter->i += getVarint(&pIter->a[pIter->i], (u64*)&pIter->iRowid);
    }
    pIter->i += fts5GetVarint32(&pIter->a[pIter->i], pIter->nPoslist);
    pIter->aPoslist = &pIter->a[pIter->i];
    pIter->i += pIter->nPoslist;
  }else{
    pIter->aPoslist = 0;
  }
}

static void fts5DoclistIterInit(
  Fts5Buffer *pBuf, 
  int bDesc, 
  Fts5DoclistIter *pIter
){
  memset(pIter, 0, sizeof(*pIter));
  pIter->a = pBuf->p;
  pIter->n = pBuf->n;
  pIter->bDesc = bDesc;
  fts5DoclistIterNext(pIter);
}

/*
** Append a doclist to buffer pBuf.
*/
static void fts5MergeAppendDocid(
  int *pRc,                       /* IN/OUT: Error code */
  int bDesc,
  Fts5Buffer *pBuf,               /* Buffer to write to */
  i64 *piLastRowid,               /* IN/OUT: Previous rowid written (if any) */
  i64 iRowid                      /* Rowid to append */
){
  if( pBuf->n==0 ){
    fts5BufferAppendVarint(pRc, pBuf, iRowid);
  }else if( bDesc ){
    fts5BufferAppendVarint(pRc, pBuf, *piLastRowid - iRowid);
  }else{
    fts5BufferAppendVarint(pRc, pBuf, iRowid - *piLastRowid);
  }
  *piLastRowid = iRowid;
}

/*
** Buffers p1 and p2 contain doclists. This function merges the content
** of the two doclists together and sets buffer p1 to the result before
** returning.
**
** If an error occurs, an error code is left in p->rc. If an error has
** already occurred, this function is a no-op.
*/
static void fts5MergePrefixLists(
  Fts5Index *p,                   /* FTS5 backend object */
  int bDesc,
  Fts5Buffer *p1,                 /* First list to merge */
  Fts5Buffer *p2                  /* Second list to merge */
){
  if( p2->n ){
    i64 iLastRowid = 0;
    Fts5DoclistIter i1;
    Fts5DoclistIter i2;
    Fts5Buffer out;
    Fts5Buffer tmp;
    memset(&out, 0, sizeof(out));
    memset(&tmp, 0, sizeof(tmp));

    fts5DoclistIterInit(p1, bDesc, &i1);
    fts5DoclistIterInit(p2, bDesc, &i2);
    while( i1.aPoslist!=0 || i2.aPoslist!=0 ){
      if( i2.aPoslist==0 || (i1.aPoslist && 
           ( (bDesc && i1.iRowid>i2.iRowid) || (!bDesc && i1.iRowid<i2.iRowid) )
      )){
        /* Copy entry from i1 */
        fts5MergeAppendDocid(&p->rc, bDesc, &out, &iLastRowid, i1.iRowid);
        fts5BufferAppendVarint(&p->rc, &out, i1.nPoslist);
        fts5BufferAppendBlob(&p->rc, &out, i1.nPoslist, i1.aPoslist);
        fts5DoclistIterNext(&i1);
      }
      else if( i1.aPoslist==0 || i2.iRowid!=i1.iRowid ){
        /* Copy entry from i2 */
        fts5MergeAppendDocid(&p->rc, bDesc, &out, &iLastRowid, i2.iRowid);
        fts5BufferAppendVarint(&p->rc, &out, i2.nPoslist);
        fts5BufferAppendBlob(&p->rc, &out, i2.nPoslist, i2.aPoslist);
        fts5DoclistIterNext(&i2);
      }
      else{
        Fts5PoslistReader r1;
        Fts5PoslistReader r2;
        Fts5PoslistWriter writer;

        memset(&writer, 0, sizeof(writer));

        /* Merge the two position lists. */ 
        fts5MergeAppendDocid(&p->rc, bDesc, &out, &iLastRowid, i2.iRowid);
        fts5BufferZero(&tmp);
        sqlite3Fts5PoslistReaderInit(-1, i1.aPoslist, i1.nPoslist, &r1);
        sqlite3Fts5PoslistReaderInit(-1, i2.aPoslist, i2.nPoslist, &r2);
        while( p->rc==SQLITE_OK && (r1.bEof==0 || r2.bEof==0) ){
          i64 iNew;
          if( r2.bEof || (r1.bEof==0 && r1.iPos<r2.iPos) ){
            iNew = r1.iPos;
3843
3844
3845
3846
3847
3848
3849
3850
3851
3852
3853
3854
3855
3856
3857
  Fts5Buffer tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

static void fts5SetupPrefixIter(
  Fts5Index *p,                   /* Index to read from */
  int bAsc,                       /* True for "ORDER BY rowid ASC" */
  const u8 *pToken,               /* Buffer containing prefix to match */
  int nToken,                     /* Size of buffer pToken in bytes */
  Fts5IndexIter *pIter            /* Populate this object */
){
  Fts5Structure *pStruct;
  Fts5Buffer *aBuf;
  const int nBuf = 32;







|







3841
3842
3843
3844
3845
3846
3847
3848
3849
3850
3851
3852
3853
3854
3855
  Fts5Buffer tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

static void fts5SetupPrefixIter(
  Fts5Index *p,                   /* Index to read from */
  int bDesc,                      /* True for "ORDER BY rowid DESC" */
  const u8 *pToken,               /* Buffer containing prefix to match */
  int nToken,                     /* Size of buffer pToken in bytes */
  Fts5IndexIter *pIter            /* Populate this object */
){
  Fts5Structure *pStruct;
  Fts5Buffer *aBuf;
  const int nBuf = 32;
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889
3890
3891
3892
3893
3894
3895
3896
3897
3898
3899
3900
3901
3902
3903
3904
3905
3906
3907
3908
3909
3910
3911
3912
3913
3914
3915
3916
3917
3918
3919
3920
3921
3922
3923
3924
      i64 iRowid = fts5MultiIterRowid(p1);
      int nTerm;
      const u8 *pTerm = fts5MultiIterTerm(p1, &nTerm);
      assert( memcmp(pToken, pTerm, MIN(nToken, nTerm))<=0 );
      if( nTerm<nToken || memcmp(pToken, pTerm, nToken) ) break;

      if( doclist.n>0 
       && ((!bAsc && iRowid>=iLastRowid) || (bAsc && iRowid<=iLastRowid))
      ){

        for(i=0; p->rc==SQLITE_OK && doclist.n; i++){
          assert( i<nBuf );
          if( aBuf[i].n==0 ){
            fts5BufferSwap(&doclist, &aBuf[i]);
            fts5BufferZero(&doclist);
          }else{
            fts5MergePrefixLists(p, bAsc, &doclist, &aBuf[i]);
            fts5BufferZero(&aBuf[i]);
          }
        }
      }
      if( doclist.n==0 ){
        fts5BufferAppendVarint(&p->rc, &doclist, iRowid);
      }else if( bAsc==0 ){
        fts5BufferAppendVarint(&p->rc, &doclist, iLastRowid - iRowid);
      }else{
        fts5BufferAppendVarint(&p->rc, &doclist, iRowid - iLastRowid);
      }
      iLastRowid = iRowid;
      fts5MultiIterPoslist(p, p1, 1, &doclist);
    }

    for(i=0; i<nBuf; i++){
      fts5MergePrefixLists(p, bAsc, &doclist, &aBuf[i]);
      fts5BufferFree(&aBuf[i]);
    }
    fts5MultiIterFree(p, p1);

    pDoclist = (Fts5DoclistIter*)fts5IdxMalloc(p, sizeof(Fts5DoclistIter));
    if( !pDoclist ){
      fts5BufferFree(&doclist);
    }else{
      pIter->pDoclist = pDoclist;
      fts5DoclistIterInit(&doclist, bAsc, pIter->pDoclist);
    }
  }

  fts5StructureRelease(pStruct);
  sqlite3_free(aBuf);
}








|








|






|









|









|







3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889
3890
3891
3892
3893
3894
3895
3896
3897
3898
3899
3900
3901
3902
3903
3904
3905
3906
3907
3908
3909
3910
3911
3912
3913
3914
3915
3916
3917
3918
3919
3920
3921
3922
      i64 iRowid = fts5MultiIterRowid(p1);
      int nTerm;
      const u8 *pTerm = fts5MultiIterTerm(p1, &nTerm);
      assert( memcmp(pToken, pTerm, MIN(nToken, nTerm))<=0 );
      if( nTerm<nToken || memcmp(pToken, pTerm, nToken) ) break;

      if( doclist.n>0 
       && ((!bDesc && iRowid<=iLastRowid) || (bDesc && iRowid>=iLastRowid))
      ){

        for(i=0; p->rc==SQLITE_OK && doclist.n; i++){
          assert( i<nBuf );
          if( aBuf[i].n==0 ){
            fts5BufferSwap(&doclist, &aBuf[i]);
            fts5BufferZero(&doclist);
          }else{
            fts5MergePrefixLists(p, bDesc, &doclist, &aBuf[i]);
            fts5BufferZero(&aBuf[i]);
          }
        }
      }
      if( doclist.n==0 ){
        fts5BufferAppendVarint(&p->rc, &doclist, iRowid);
      }else if( bDesc ){
        fts5BufferAppendVarint(&p->rc, &doclist, iLastRowid - iRowid);
      }else{
        fts5BufferAppendVarint(&p->rc, &doclist, iRowid - iLastRowid);
      }
      iLastRowid = iRowid;
      fts5MultiIterPoslist(p, p1, 1, &doclist);
    }

    for(i=0; i<nBuf; i++){
      fts5MergePrefixLists(p, bDesc, &doclist, &aBuf[i]);
      fts5BufferFree(&aBuf[i]);
    }
    fts5MultiIterFree(p, p1);

    pDoclist = (Fts5DoclistIter*)fts5IdxMalloc(p, sizeof(Fts5DoclistIter));
    if( !pDoclist ){
      fts5BufferFree(&doclist);
    }else{
      pIter->pDoclist = pDoclist;
      fts5DoclistIterInit(&doclist, bDesc, pIter->pDoclist);
    }
  }

  fts5StructureRelease(pStruct);
  sqlite3_free(aBuf);
}

4269
4270
4271
4272
4273
4274
4275
4276
4277
4278
4279
4280
4281
4282
4283
4284
      pRet->pStruct = fts5StructureRead(p, iIdx);
      if( pRet->pStruct ){
        fts5MultiIterNew(p, pRet->pStruct, 
            iIdx, 1, flags, (const u8*)pToken, nToken, -1, 0, &pRet->pMulti
        );
      }
    }else{
      int bAsc = (flags & FTS5INDEX_QUERY_ASC)!=0;
      fts5SetupPrefixIter(p, bAsc, (const u8*)pToken, nToken, pRet);
    }
  }

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







|
|







4267
4268
4269
4270
4271
4272
4273
4274
4275
4276
4277
4278
4279
4280
4281
4282
      pRet->pStruct = fts5StructureRead(p, iIdx);
      if( pRet->pStruct ){
        fts5MultiIterNew(p, pRet->pStruct, 
            iIdx, 1, flags, (const u8*)pToken, nToken, -1, 0, &pRet->pMulti
        );
      }
    }else{
      int bDesc = (flags & FTS5INDEX_QUERY_DESC)!=0;
      fts5SetupPrefixIter(p, bDesc, (const u8*)pToken, nToken, pRet);
    }
  }

  if( p->rc ){
    sqlite3Fts5IterClose(pRet);
    pRet = 0;
  }
4317
4318
4319
4320
4321
4322
4323
4324
4325
4326
4327
4328
4329
4330
4331
4332
** matching rowid that occurs at or after iMatch. The definition of "at 
** or after" depends on whether this iterator iterates in ascending or 
** descending rowid order.
*/
static void fts5DoclistIterNextFrom(Fts5DoclistIter *p, i64 iMatch){
  do{
    i64 iRowid = p->iRowid;
    if( p->bAsc!=0 && iRowid>=iMatch ) break;
    if( p->bAsc==0 && iRowid<=iMatch ) break;
    fts5DoclistIterNext(p);
  }while( p->aPoslist );
}

/*
** Move to the next matching rowid that occurs at or after iMatch. The
** definition of "at or after" depends on whether this iterator iterates







|
|







4315
4316
4317
4318
4319
4320
4321
4322
4323
4324
4325
4326
4327
4328
4329
4330
** matching rowid that occurs at or after iMatch. The definition of "at 
** or after" depends on whether this iterator iterates in ascending or 
** descending rowid order.
*/
static void fts5DoclistIterNextFrom(Fts5DoclistIter *p, i64 iMatch){
  do{
    i64 iRowid = p->iRowid;
    if( p->bDesc==0 && iRowid>=iMatch ) break;
    if( p->bDesc!=0 && iRowid<=iMatch ) break;
    fts5DoclistIterNext(p);
  }while( p->aPoslist );
}

/*
** Move to the next matching rowid that occurs at or after iMatch. The
** definition of "at or after" depends on whether this iterator iterates
4598
4599
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
    int nPos;
    iOff += fts5GetVarint32(&a[iOff], nPos);
    iOff += fts5DecodePoslist(pRc, pBuf, &a[iOff], MIN(n-iOff, nPos));
    if( iOff<n ){
      i64 iDelta;
      iOff += sqlite3GetVarint(&a[iOff], (u64*)&iDelta);
      if( iDelta==0 ) return iOff;
      iDocid -= iDelta;
      sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " rowid=%lld", iDocid);
    }
  }

  return iOff;
}








|







4596
4597
4598
4599
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
    int nPos;
    iOff += fts5GetVarint32(&a[iOff], nPos);
    iOff += fts5DecodePoslist(pRc, pBuf, &a[iOff], MIN(n-iOff, nPos));
    if( iOff<n ){
      i64 iDelta;
      iOff += sqlite3GetVarint(&a[iOff], (u64*)&iDelta);
      if( iDelta==0 ) return iOff;
      iDocid += iDelta;
      sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " rowid=%lld", iDocid);
    }
  }

  return iOff;
}

4687
4688
4689
4690
4691
4692
4693
4694
4695
4696
4697
4698
4699
4700
4701
        iOff = iRowidOff;
      }else if( iTermOff ){
        iOff = iTermOff;
      }else{
        iOff = n;
      }
      fts5DecodePoslist(&rc, &s, &a[4], iOff-4);


      assert( iRowidOff==0 || iOff==iRowidOff );
      if( iRowidOff ){
        iOff += fts5DecodeDoclist(&rc, &s, &a[iOff], n-iOff);
      }

      assert( iTermOff==0 || iOff==iTermOff );







<







4685
4686
4687
4688
4689
4690
4691

4692
4693
4694
4695
4696
4697
4698
        iOff = iRowidOff;
      }else if( iTermOff ){
        iOff = iTermOff;
      }else{
        iOff = n;
      }
      fts5DecodePoslist(&rc, &s, &a[4], iOff-4);


      assert( iRowidOff==0 || iOff==iRowidOff );
      if( iRowidOff ){
        iOff += fts5DecodeDoclist(&rc, &s, &a[iOff], n-iOff);
      }

      assert( iTermOff==0 || iOff==iTermOff );
Changes to ext/fts5/test/fts5aa.test.
181
182
183
184
185
186
187

188

189
190
191
192
193
194
195
      set y [doc]
      set z [doc]
      set rowid [expr int(rand() * 100)]
      execsql { REPLACE INTO t1(rowid,x,y,z) VALUES($rowid, $x, $y, $z) }
    }
    execsql { INSERT INTO t1(t1) VALUES('integrity-check'); }
  } {}

}


#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 8.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(x, prefix="1,2,3");
  INSERT INTO t1(t1, rank) VALUES('pgsz', 32);







>

>







181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
      set y [doc]
      set z [doc]
      set rowid [expr int(rand() * 100)]
      execsql { REPLACE INTO t1(rowid,x,y,z) VALUES($rowid, $x, $y, $z) }
    }
    execsql { INSERT INTO t1(t1) VALUES('integrity-check'); }
  } {}
  if {$i==2} break
}
#db eval {SELECT rowid, fts5_decode(rowid, block) aS r FROM t1_data} {puts $r}

#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 8.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(x, prefix="1,2,3");
  INSERT INTO t1(t1, rank) VALUES('pgsz', 32);
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
do_execsql_test 13.1 {
  CREATE VIRTUAL TABLE t1 USING fts5(x);
  INSERT INTO t1(rowid, x) VALUES(1, 'o n e'), (2, 't w o');
} {}

do_execsql_test 13.2 {
  SELECT rowid FROM t1 WHERE t1 MATCH 'o';
} {2 1}

do_execsql_test 13.4 {
  DELETE FROM t1 WHERE rowid=2;
} {}

do_execsql_test 13.5 {
  SELECT rowid FROM t1 WHERE t1 MATCH 'o';







|







310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
do_execsql_test 13.1 {
  CREATE VIRTUAL TABLE t1 USING fts5(x);
  INSERT INTO t1(rowid, x) VALUES(1, 'o n e'), (2, 't w o');
} {}

do_execsql_test 13.2 {
  SELECT rowid FROM t1 WHERE t1 MATCH 'o';
} {1 2}

do_execsql_test 13.4 {
  DELETE FROM t1 WHERE rowid=2;
} {}

do_execsql_test 13.5 {
  SELECT rowid FROM t1 WHERE t1 MATCH 'o';
Changes to ext/fts5/test/fts5ab.test.
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
  CREATE VIRTUAL TABLE t1 USING fts5(a, b);
  INSERT INTO t1 VALUES('hello', 'world');
  INSERT INTO t1 VALUES('one two', 'three four');
  INSERT INTO t1(rowid, a, b) VALUES(45, 'forty', 'five');
}

do_execsql_test 1.1 {
  SELECT * FROM t1;
} { forty five {one two} {three four} hello world }

do_execsql_test 1.2 {
  SELECT rowid FROM t1;
} {45 2 1}

do_execsql_test 1.3 {
  SELECT rowid FROM t1 ORDER BY rowid ASC;
} {1 2 45}

do_execsql_test 1.4 {







|



|







26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
  CREATE VIRTUAL TABLE t1 USING fts5(a, b);
  INSERT INTO t1 VALUES('hello', 'world');
  INSERT INTO t1 VALUES('one two', 'three four');
  INSERT INTO t1(rowid, a, b) VALUES(45, 'forty', 'five');
}

do_execsql_test 1.1 {
  SELECT * FROM t1 ORDER BY rowid DESC;
} { forty five {one two} {three four} hello world }

do_execsql_test 1.2 {
  SELECT rowid FROM t1 ORDER BY rowid DESC;
} {45 2 1}

do_execsql_test 1.3 {
  SELECT rowid FROM t1 ORDER BY rowid ASC;
} {1 2 45}

do_execsql_test 1.4 {
86
87
88
89
90
91
92
93





94
95
96
97
98
99
100
  5  e    {5 4}
  6  f    {4}
  7  g    {4}
  8  x    {6}
  9  y    {6}
  10 z    {6}
} {
  do_execsql_test 2.7.$tn { SELECT rowid FROM t1 WHERE t1 MATCH $expr } $res





}

#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 3.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(a,b);







|
>
>
>
>
>







86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
  5  e    {5 4}
  6  f    {4}
  7  g    {4}
  8  x    {6}
  9  y    {6}
  10 z    {6}
} {
  do_execsql_test 2.7.$tn.1 { 
    SELECT rowid FROM t1 WHERE t1 MATCH $expr ORDER BY rowid DESC
  } $res
  do_execsql_test 2.7.$tn.2 { 
    SELECT rowid FROM t1 WHERE t1 MATCH $expr ORDER BY rowid ASC
  } [lsort -integer $res]
}

#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 3.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(a,b);
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
  3 {abase + abash} {1}
  4 {abash + abase} {9}
  5 {abaft + abashing} {8 5}
  6 {abandon + abandoning} {10}
  7 {"abashing abases abasement abaft abashing"} {8}
} {
  do_execsql_test 3.2.$tn {
    SELECT rowid FROM t1 WHERE t1 MATCH $expr
  } $res
}

do_execsql_test 3.3 {
  SELECT rowid FROM t1 WHERE t1 MATCH 'NEAR(aback abate, 2)'
} {6}

foreach {tn expr res} {
  1 {abash} {1 3 5 9}
  2 {abase} {1 3 4 9}
  3 {abase + abash} {1}
  4 {abash + abase} {9}
  5 {abaft + abashing} {5 8}
  6 {abandon + abandoning} {10}
  7 {"abashing abases abasement abaft abashing"} {8}
} {
  do_execsql_test 3.4.$tn {
    SELECT rowid FROM t1 WHERE t1 MATCH $expr ORDER BY rowid ASC
  } $res
}

#-------------------------------------------------------------------------
# Documents with more than 2M tokens.
#

do_execsql_test 4.0 {
  CREATE VIRTUAL TABLE s1 USING fts5(x);
}
foreach {tn doc} [list \
  1 [string repeat {a x } 1500000]       \
  2 "[string repeat {a a } 1500000] x"   \
] {
  do_execsql_test 4.$tn { INSERT INTO s1 VALUES($doc) }
}

do_execsql_test 4.3 {
  SELECT rowid FROM s1 WHERE s1 MATCH 'x'
} {2 1}

do_execsql_test 4.4 {
  SELECT rowid FROM s1 WHERE s1 MATCH '"a x"'
} {2 1}

#-------------------------------------------------------------------------
# Check that a special case of segment promotion works. The case is where
# a new segment is written to level L, but the oldest segment within level
# (L-2) is larger than it.
#
do_execsql_test 5.0 {







|

















|



















|



|







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
  3 {abase + abash} {1}
  4 {abash + abase} {9}
  5 {abaft + abashing} {8 5}
  6 {abandon + abandoning} {10}
  7 {"abashing abases abasement abaft abashing"} {8}
} {
  do_execsql_test 3.2.$tn {
    SELECT rowid FROM t1 WHERE t1 MATCH $expr ORDER BY rowid DESC
  } $res
}

do_execsql_test 3.3 {
  SELECT rowid FROM t1 WHERE t1 MATCH 'NEAR(aback abate, 2)'
} {6}

foreach {tn expr res} {
  1 {abash} {1 3 5 9}
  2 {abase} {1 3 4 9}
  3 {abase + abash} {1}
  4 {abash + abase} {9}
  5 {abaft + abashing} {5 8}
  6 {abandon + abandoning} {10}
  7 {"abashing abases abasement abaft abashing"} {8}
} {
  do_execsql_test 3.4.$tn {
    SELECT rowid FROM t1 WHERE t1 MATCH $expr
  } $res
}

#-------------------------------------------------------------------------
# Documents with more than 2M tokens.
#

do_execsql_test 4.0 {
  CREATE VIRTUAL TABLE s1 USING fts5(x);
}
foreach {tn doc} [list \
  1 [string repeat {a x } 1500000]       \
  2 "[string repeat {a a } 1500000] x"   \
] {
  do_execsql_test 4.$tn { INSERT INTO s1 VALUES($doc) }
}

do_execsql_test 4.3 {
  SELECT rowid FROM s1 WHERE s1 MATCH 'x'
} {1 2}

do_execsql_test 4.4 {
  SELECT rowid FROM s1 WHERE s1 MATCH '"a x"'
} {1 2}

#-------------------------------------------------------------------------
# Check that a special case of segment promotion works. The case is where
# a new segment is written to level L, but the oldest segment within level
# (L-2) is larger than it.
#
do_execsql_test 5.0 {
229
230
231
232
233
234
235

















236
237
238
} {0 1}

do_test 5.4 {
  execsql { INSERT INTO s2 VALUES(rnddoc(160)) }
  fts5_level_segs s2
} {2 0}



















finish_test








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



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
} {0 1}

do_test 5.4 {
  execsql { INSERT INTO s2 VALUES(rnddoc(160)) }
  fts5_level_segs s2
} {2 0}

#-------------------------------------------------------------------------
#
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

Changes to ext/fts5/test/fts5ac.test.
130
131
132
133
134
135
136

137
138
139
140
141
142
143
    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) }
  }

} {}

# Usage:
#
#   poslist aCol ?-pc VARNAME? ?-near N? ?-col C? -- phrase1 phrase2...
#
proc poslist {aCol args} {







>







130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
    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} {
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
# formatted as follows:
#
#   <rowid> {<phrase 0 matches> <phrase 1 matches>...}
#
# where each <phrase X matches> element is a list of phrase matches in the
# same form as returned by auxiliary scalar function fts5_test().
#
proc matchdata {bPos expr {bAsc 0}} {

  set tclexpr [db one {SELECT fts5_expr_tcl($expr, 'nearset $cols', 'x', 'y')}]
  set res [list]

  #puts $tclexpr
  foreach {id x y} $::data {
    set cols [list $x $y]







|







250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
# formatted as follows:
#
#   <rowid> {<phrase 0 matches> <phrase 1 matches>...}
#
# where each <phrase X matches> element is a list of phrase matches in the
# same form as returned by auxiliary scalar function fts5_test().
#
proc matchdata {bPos expr {bAsc 1}} {

  set tclexpr [db one {SELECT fts5_expr_tcl($expr, 'nearset $cols', 'x', 'y')}]
  set res [list]

  #puts $tclexpr
  foreach {id x y} $::data {
    set cols [list $x $y]
303
304
305
306
307
308
309


310
311
312
313
314
315
316

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"







>
>







304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319

sqlite3_fts5_create_function db fts5_test_poslist fts5_test_poslist

#-------------------------------------------------------------------------
# Test phrase queries.
#
foreach {tn phrase} {
  8 "c"

  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"
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
#-------------------------------------------------------------------------
#
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} {
  0 {SELECT rowid FROM xx WHERE xx MATCH $expr}
  1 {SELECT rowid FROM xx WHERE xx MATCH $expr ORDER BY rowid ASC}
} {
  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) }







|
|







399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
#-------------------------------------------------------------------------
#
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) }
Changes to ext/fts5/test/fts5ad.test.
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
foreach {tn match res} {
  1 {c*} {1}
  2 {i*} {3 2}
  3 {t*} {3 1}
  4 {r*} {3 1}
} {
  do_execsql_test 1.$tn {
    SELECT rowid FROM yy WHERE yy MATCH $match
  } $res
}

foreach {tn match res} {
  5 {c*} {1}
  6 {i*} {2 3}
  7 {t*} {1 3}
  8 {r*} {1 3}
} {
  do_execsql_test 1.$tn {
    SELECT rowid FROM yy WHERE yy MATCH $match ORDER BY rowid ASC
  } $res
}

foreach {T create} {
  2 {
    CREATE VIRTUAL TABLE t1 USING fts5(a, b);
    INSERT INTO t1(t1, rank) VALUES('pgsz', 32);







|










|







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
foreach {tn match res} {
  1 {c*} {1}
  2 {i*} {3 2}
  3 {t*} {3 1}
  4 {r*} {3 1}
} {
  do_execsql_test 1.$tn {
    SELECT rowid FROM yy WHERE yy MATCH $match ORDER BY rowid DESC
  } $res
}

foreach {tn match res} {
  5 {c*} {1}
  6 {i*} {2 3}
  7 {t*} {1 3}
  8 {r*} {1 3}
} {
  do_execsql_test 1.$tn {
    SELECT rowid FROM yy WHERE yy MATCH $match
  } $res
}

foreach {T create} {
  2 {
    CREATE VIRTUAL TABLE t1 USING fts5(a, b);
    INSERT INTO t1(t1, rank) VALUES('pgsz', 32);
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
      }
      if {$bMatch} { lappend ret $rowid }
    }
    return $ret
  }
  
  foreach {bAsc sql} {
    0 {SELECT rowid FROM t1 WHERE t1 MATCH $prefix}
    1 {SELECT rowid FROM t1 WHERE t1 MATCH $prefix ORDER BY rowid ASC}
  } {
    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*}







|
|







190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
      }
      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*}
Changes to ext/fts5/test/fts5ae.test.
105
106
107
108
109
110
111
112
113

114
115
116
117
118
119
120

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_poslist(t3) 
  FROM t3 WHERE t3 MATCH 'a OR b AND c';
} {
  3 0.0.5 
  1 {0.0.6 1.0.9 0.0.10 0.0.12 1.0.15 2.1.2}

}

#-------------------------------------------------------------------------
# 
do_execsql_test 4.0 {
  CREATE VIRTUAL TABLE t4 USING fts5(x, y);
  INSERT INTO t4 







<

>







105
106
107
108
109
110
111

112
113
114
115
116
117
118
119
120

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_poslist(t3) 
  FROM t3 WHERE t3 MATCH 'a OR b AND c';
} {

  1 {0.0.6 1.0.9 0.0.10 0.0.12 1.0.15 2.1.2}
  3 0.0.5 
}

#-------------------------------------------------------------------------
# 
do_execsql_test 4.0 {
  CREATE VIRTUAL TABLE t4 USING fts5(x, y);
  INSERT INTO t4 
186
187
188
189
190
191
192
193
194

195
196
197
198
199
200
201
  INSERT INTO t6 VALUES('There are more', 'things in heaven and earth');
  INSERT INTO t6 VALUES(', Horatio, Than are', 'dreamt of in your philosophy.');
}

do_execsql_test 6.2 {
  SELECT rowid, fts5_test_tokenize(t6) FROM t6 WHERE t6 MATCH 't*'
} {
  2 {{horatio than are} {dreamt of in your philosophy}}
  1 {{there are more} {things in heaven and earth}}

}

#-------------------------------------------------------------------------
# Test the xQueryPhrase() API
#
reset_db
fts5_aux_test_functions db







<

>







186
187
188
189
190
191
192

193
194
195
196
197
198
199
200
201
  INSERT INTO t6 VALUES('There are more', 'things in heaven and earth');
  INSERT INTO t6 VALUES(', Horatio, Than are', 'dreamt of in your philosophy.');
}

do_execsql_test 6.2 {
  SELECT rowid, fts5_test_tokenize(t6) FROM t6 WHERE t6 MATCH 't*'
} {

  1 {{there are more} {things in heaven and earth}}
  2 {{horatio than are} {dreamt of in your philosophy}}
}

#-------------------------------------------------------------------------
# Test the xQueryPhrase() API
#
reset_db
fts5_aux_test_functions db
Changes to ext/fts5/test/fts5ak.test.
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
  INSERT INTO ft1 VALUES('i d i g c d c h b f');
  INSERT INTO ft1 VALUES('g d a e h a b c f j');
}

do_execsql_test 1.2 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'e';
} {
  {g d a [e] h a b c f j}

  {i c c f a d g h j [e]}
  {j f c [e] d a h j d b}
  {i a d [e] g j g d a a}
  {d c j d c j b c g [e]}
  {[e] j a [e] f h b f h h}
}

do_execsql_test 1.3 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'h + d';
} {
  {j f [h d] g h i b d f} 
  {[h d] b j c c g a c a}

}

do_execsql_test 1.4 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'd + d';
} {
  {i [d d] a g i b g [d d]}
}

do_execsql_test 1.5 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'e e e'
} {
  {g d a [e] h a b c f j}

  {i c c f a d g h j [e]}
  {j f c [e] d a h j d b}
  {i a d [e] g j g d a a}
  {d c j d c j b c g [e]}
  {[e] j a [e] f h b f h h}
}

do_execsql_test 1.6 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'd + d d + d';
} {
  {i [d d] a g i b g [d d]}
}







|
>
|

|
<
|





<

>











|
>
|

|
<
|







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
  INSERT INTO ft1 VALUES('i d i g c d c h b f');
  INSERT INTO ft1 VALUES('g d a e h a b c f j');
}

do_execsql_test 1.2 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'e';
} {
  {[e] j a [e] f h b f h h}
  {d c j d c j b c g [e]}
  {i a d [e] g j g d a a}
  {j f c [e] d a h j d b}
  {i c c f a d g h j [e]}

  {g d a [e] h a b c f j}
}

do_execsql_test 1.3 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'h + d';
} {

  {[h d] b j c c g a c a}
  {j f [h d] g h i b d f} 
}

do_execsql_test 1.4 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'd + d';
} {
  {i [d d] a g i b g [d d]}
}

do_execsql_test 1.5 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'e e e'
} {
  {[e] j a [e] f h b f h h}
  {d c j d c j b c g [e]}
  {i a d [e] g j g d a a}
  {j f c [e] d a h j d b}
  {i c c f a d g h j [e]}

  {g d a [e] h a b c f j}
}

do_execsql_test 1.6 {
  SELECT highlight(ft1, 0, '[', ']') FROM ft1 WHERE ft1 MATCH 'd + d d + d';
} {
  {i [d d] a g i b g [d d]}
}
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

  -- The following SELECT statement returns these three rows:
  --   '[a b c] x [c d e]'
  --   '[a b c] [c d e]'
  --   '[a b c d e]'
  SELECT highlight(ft, 0, '[', ']') FROM ft WHERE ft MATCH 'a+b+c AND c+d+e';
} {
  {[a b c d e]}
  {[a b c] [c d e]}
  {[a b c] x [c d e]}
}


finish_test








|

|





129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

  -- The following SELECT statement returns these three rows:
  --   '[a b c] x [c d e]'
  --   '[a b c] [c d e]'
  --   '[a b c d e]'
  SELECT highlight(ft, 0, '[', ']') FROM ft WHERE ft MATCH 'a+b+c AND c+d+e';
} {
  {[a b c] x [c d e]}
  {[a b c] [c d e]}
  {[a b c d e]}
}


finish_test

Changes to ext/fts5/test/fts5al.test.
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
} {{123 456} {123 456}}

proc rowidtest {cmd} { $cmd xRowid }
sqlite3_fts5_create_function db rowidtest rowidtest

do_execsql_test 3.3.1 {
  SELECT rowidtest(t1) FROM t1 WHERE t1 MATCH 'q'
} {2 1}

proc insttest {cmd} {
  set res [list]
  for {set i 0} {$i < [$cmd xInstCount]} {incr i} {
    lappend res [$cmd xInst $i]
  }
  set res
}
sqlite3_fts5_create_function db insttest insttest

do_execsql_test 3.4.1 {
  SELECT insttest(t1) FROM t1 WHERE t1 MATCH 'q'
} {
  {{0 0 5}} 
  {{0 0 0}}
}

do_execsql_test 3.4.2 {
  SELECT insttest(t1) FROM t1 WHERE t1 MATCH 'r+e OR w'
} {
  {{0 0 2} {1 0 4}} 
  {{1 0 1}}

}

proc coltest {cmd} {
  list [$cmd xColumnSize 0] [$cmd xColumnText 0]
}
sqlite3_fts5_create_function db coltest coltest

do_execsql_test 3.5.1 {
  SELECT coltest(t1) FROM t1 WHERE t1 MATCH 'q'
} {

  {6 {y t r e w q}} {6 {q w e r t y}}
}

#-------------------------------------------------------------------------
# Tests for remapping the "rank" column.
#
#   4.1.*: Mapped to a function with no arguments.
#   4.2.*: Mapped to a function with one or more arguments.







|













|
|





<

>










>
|







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
} {{123 456} {123 456}}

proc rowidtest {cmd} { $cmd xRowid }
sqlite3_fts5_create_function db rowidtest rowidtest

do_execsql_test 3.3.1 {
  SELECT rowidtest(t1) FROM t1 WHERE t1 MATCH 'q'
} {1 2}

proc insttest {cmd} {
  set res [list]
  for {set i 0} {$i < [$cmd xInstCount]} {incr i} {
    lappend res [$cmd xInst $i]
  }
  set res
}
sqlite3_fts5_create_function db insttest insttest

do_execsql_test 3.4.1 {
  SELECT insttest(t1) FROM t1 WHERE t1 MATCH 'q'
} {
  {{0 0 0}}
  {{0 0 5}} 
}

do_execsql_test 3.4.2 {
  SELECT insttest(t1) FROM t1 WHERE t1 MATCH 'r+e OR w'
} {

  {{1 0 1}}
  {{0 0 2} {1 0 4}} 
}

proc coltest {cmd} {
  list [$cmd xColumnSize 0] [$cmd xColumnText 0]
}
sqlite3_fts5_create_function db coltest coltest

do_execsql_test 3.5.1 {
  SELECT coltest(t1) FROM t1 WHERE t1 MATCH 'q'
} {
  {6 {q w e r t y}}
  {6 {y t r e w q}} 
}

#-------------------------------------------------------------------------
# Tests for remapping the "rank" column.
#
#   4.1.*: Mapped to a function with no arguments.
#   4.2.*: Mapped to a function with one or more arguments.
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
}

do_execsql_test 4.1.3 {
  SELECT rowid, rank FROM t2 
  WHERE t2 MATCH 'a' AND rank MATCH 'firstinst()'
  ORDER BY rank DESC
} {
  5 103  9 102  6 9  10 8  3 6  2 4  7 0  1 0 
}

do_execsql_test 4.1.4 {
  INSERT INTO t2(t2, rank) VALUES('rank', 'firstinst()');
  SELECT rowid, rank FROM t2 WHERE t2 MATCH 'a' ORDER BY rowid ASC
} {
  1 0 2 4 3 6   5  103
  6 9 7 0 9 102 10 8
}

do_execsql_test 4.1.5 {
  SELECT rowid, rank FROM t2 WHERE t2 MATCH 'a' ORDER BY rank DESC
} {
  5 103  9 102  6 9  10 8  3 6  2 4  7 0  1 0 
}

do_execsql_test 4.1.6 {
  INSERT INTO t2(t2, rank) VALUES('rank', 'firstinst (    ) ');
  SELECT rowid, rank FROM t2 WHERE t2 MATCH 'a' ORDER BY rank DESC
} {
  5 103  9 102  6 9  10 8  3 6  2 4  7 0  1 0 
}

proc rowidplus {cmd ival} { 
  expr [$cmd xRowid] + $ival
}
sqlite3_fts5_create_function db rowidplus rowidplus








|













|






|







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
}

do_execsql_test 4.1.3 {
  SELECT rowid, rank FROM t2 
  WHERE t2 MATCH 'a' AND rank MATCH 'firstinst()'
  ORDER BY rank DESC
} {
  5 103  9 102  6 9  10 8  3 6  2 4  1 0  7 0  
}

do_execsql_test 4.1.4 {
  INSERT INTO t2(t2, rank) VALUES('rank', 'firstinst()');
  SELECT rowid, rank FROM t2 WHERE t2 MATCH 'a' ORDER BY rowid ASC
} {
  1 0 2 4 3 6   5  103
  6 9 7 0 9 102 10 8
}

do_execsql_test 4.1.5 {
  SELECT rowid, rank FROM t2 WHERE t2 MATCH 'a' ORDER BY rank DESC
} {
  5 103  9 102  6 9  10 8  3 6  2 4  1 0  7 0  
}

do_execsql_test 4.1.6 {
  INSERT INTO t2(t2, rank) VALUES('rank', 'firstinst (    ) ');
  SELECT rowid, rank FROM t2 WHERE t2 MATCH 'a' ORDER BY rank DESC
} {
  5 103  9 102  6 9  10 8  3 6  2 4   1 0  7 0  
}

proc rowidplus {cmd ival} { 
  expr [$cmd xRowid] + $ival
}
sqlite3_fts5_create_function db rowidplus rowidplus

253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
breakpoint

do_execsql_test 4.3.2 {
  SELECT * FROM t3
  WHERE t3 MATCH 'a' AND rank MATCH 'rowidmod(4)' 
  ORDER BY rank ASC
} {
  {a four} {a five} {a one} {a two} {a three}
}
do_execsql_test 4.3.3 {
  SELECT *, rank FROM t3
  WHERE t3 MATCH 'a' AND rank MATCH 'rowidmod(3)' 
  ORDER BY rank ASC
} {
  {a three} 0 {a four} 1 {a one} 1 {a five} 2 {a two} 2
}


finish_test








|






|





254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
breakpoint

do_execsql_test 4.3.2 {
  SELECT * FROM t3
  WHERE t3 MATCH 'a' AND rank MATCH 'rowidmod(4)' 
  ORDER BY rank ASC
} {
  {a four} {a one} {a five} {a two} {a three}
}
do_execsql_test 4.3.3 {
  SELECT *, rank FROM t3
  WHERE t3 MATCH 'a' AND rank MATCH 'rowidmod(3)' 
  ORDER BY rank ASC
} {
  {a three} 0 {a one} 1 {a four} 1 {a two} 2 {a five} 2 
}


finish_test

Changes to ext/fts5/test/fts5content.test.
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
  INSERT INTO f1(rowid, a, b) VALUES(1, 'one',   'o n e');
  INSERT INTO f1(rowid, a, b) VALUES(2, 'two',   't w o');
  INSERT INTO f1(rowid, a, b) VALUES(3, 'three', 't h r e e');
}

do_execsql_test 1.2 {
  SELECT rowid FROM f1 WHERE f1 MATCH 'o';
} {2 1}

do_execsql_test 1.3 {
  INSERT INTO f1(a, b) VALUES('four',   'f o u r');
  SELECT rowid FROM f1 WHERE f1 MATCH 'o';
} {4 2 1}

do_execsql_test 1.4 {
  SELECT rowid, a, b FROM f1 WHERE f1 MATCH 'o';
} {4 {} {} 2 {} {} 1 {} {}}

do_execsql_test 1.5 {
  SELECT rowid, highlight(f1, 0, '[', ']') FROM f1 WHERE f1 MATCH 'o';
} {4 {} 2 {} 1 {}}

do_execsql_test 1.6 {
  SELECT rowid, highlight(f1, 0, '[', ']') IS NULL FROM f1 WHERE f1 MATCH 'o';
} {4 1 2 1 1 1}

do_execsql_test 1.7 {
  SELECT rowid, snippet(f1, -1, '[', ']', '...', 5) IS NULL 
  FROM f1 WHERE f1 MATCH 'o';
} {4 1 2 1 1 1}

do_execsql_test 1.8 {
  SELECT rowid, snippet(f1, 1, '[', ']', '...', 5) IS NULL 
  FROM f1 WHERE f1 MATCH 'o';
} {4 1 2 1 1 1}

do_execsql_test 1.9 {
  SELECT rowid FROM f1;
} {4 3 2 1}

do_execsql_test 1.10 {
  SELECT * FROM f1;
} {{} {}  {} {}  {} {}  {} {}}

do_execsql_test 1.11 {
  SELECT rowid, a, b FROM f1 ORDER BY rowid ASC;







|




|



|



|



|




|




|



|







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
  INSERT INTO f1(rowid, a, b) VALUES(1, 'one',   'o n e');
  INSERT INTO f1(rowid, a, b) VALUES(2, 'two',   't w o');
  INSERT INTO f1(rowid, a, b) VALUES(3, 'three', 't h r e e');
}

do_execsql_test 1.2 {
  SELECT rowid FROM f1 WHERE f1 MATCH 'o';
} {1 2}

do_execsql_test 1.3 {
  INSERT INTO f1(a, b) VALUES('four',   'f o u r');
  SELECT rowid FROM f1 WHERE f1 MATCH 'o';
} {1 2 4}

do_execsql_test 1.4 {
  SELECT rowid, a, b FROM f1 WHERE f1 MATCH 'o';
} {1 {} {} 2 {} {} 4 {} {}}

do_execsql_test 1.5 {
  SELECT rowid, highlight(f1, 0, '[', ']') FROM f1 WHERE f1 MATCH 'o';
} {1 {} 2 {} 4 {}}

do_execsql_test 1.6 {
  SELECT rowid, highlight(f1, 0, '[', ']') IS NULL FROM f1 WHERE f1 MATCH 'o';
} {1 1 2 1 4 1}

do_execsql_test 1.7 {
  SELECT rowid, snippet(f1, -1, '[', ']', '...', 5) IS NULL 
  FROM f1 WHERE f1 MATCH 'o';
} {1 1 2 1 4 1}

do_execsql_test 1.8 {
  SELECT rowid, snippet(f1, 1, '[', ']', '...', 5) IS NULL 
  FROM f1 WHERE f1 MATCH 'o';
} {1 1 2 1 4 1}

do_execsql_test 1.9 {
  SELECT rowid FROM f1;
} {1 2 3 4}

do_execsql_test 1.10 {
  SELECT * FROM f1;
} {{} {}  {} {}  {} {}  {} {}}

do_execsql_test 1.11 {
  SELECT rowid, a, b FROM f1 ORDER BY rowid ASC;
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

do_execsql_test 1.15 {
  INSERT INTO f1(f1, rowid, a, b) VALUES('delete', 2, 'two', 't w o');
} {}

do_execsql_test 1.16 {
  SELECT rowid FROM f1 WHERE f1 MATCH 'o';
} {4 1}

do_execsql_test 1.17 {
  SELECT rowid FROM f1;
} {4 3 1}

#-------------------------------------------------------------------------
# External content tables
#
reset_db
do_execsql_test 2.1 {
  -- Create a table. And an external content fts5 table to index it.







|



|







81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

do_execsql_test 1.15 {
  INSERT INTO f1(f1, rowid, a, b) VALUES('delete', 2, 'two', 't w o');
} {}

do_execsql_test 1.16 {
  SELECT rowid FROM f1 WHERE f1 MATCH 'o';
} {1 4}

do_execsql_test 1.17 {
  SELECT rowid FROM f1;
} {1 3 4}

#-------------------------------------------------------------------------
# External content tables
#
reset_db
do_execsql_test 2.1 {
  -- Create a table. And an external content fts5 table to index it.
Changes to ext/fts5/test/fts5corrupt.test.
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
  catchsql { INSERT INTO t1(t1) VALUES('integrity-check') }
} {1 {database disk image is malformed}}

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



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

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

do_test 2.1 {
  db transaction {
    for {set i 0} {$i < 20} {incr i} {
      execsql { INSERT INTO t2 VALUES('xxxxxxxxxx') }
    }
    for {set i 0} {$i < 20} {incr i} {
      execsql { INSERT INTO t2 VALUES('xxxxxxxxxzzzz') }
    }
  }
} {}
db eval {SELECT rowid, fts5_decode(rowid, block) aS r FROM t2_data} {puts $r}



finish_test








<

>


|

>

<
|
|
<
<
|

<

|
>
>



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
  catchsql { INSERT INTO t1(t1) VALUES('integrity-check') }
} {1 {database disk image is malformed}}

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



#--------------------------------------------------------------------
#
do_execsql_test 2.0 {
  CREATE VIRTUAL TABLE t2 USING fts5(x);
  INSERT INTO t2(t2, rank) VALUES('pgsz', 64);
}
db func rnddoc fts5_rnddoc
do_test 2.1 {

  for {set i 0} {$i < 500} {incr i} {
    execsql { INSERT INTO t2 VALUES(rnddoc(50)) }


    execsql { INSERT INTO t2(t2) VALUES('integrity-check') }
    }

} {}

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

finish_test

Changes to ext/fts5/test/fts5fault1.test.
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
  INSERT INTO t2 VALUES('k fe fd rd a gi ho kk', 'ng m c r d ml rm r');
}
faultsim_save_and_close

foreach {tn expr res} {
  1 { dk  }           7
  2 { m f }           1
  3 { f*  }           {10 9 8 6 5 4 3 1}
  4 { m OR f }        {10 9 8 5 4 1}
  5 { sn + gh }       {5}
  6 { "sn gh" }       {5}
  7 { NEAR(r a, 5) }  {9}
  8 { m* f* }         {10 9 8 6 4 1}
  9 { m* + f* }       {8 1}
} {
  do_faultsim_test 4.$tn -prep {
    faultsim_restore_and_reopen
  } -body "
    execsql { SELECT rowid FROM t2 WHERE t2 MATCH '$expr' }
  " -test "
    faultsim_test_result {[list 0 $res]}







|
|



|
|







86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
  INSERT INTO t2 VALUES('k fe fd rd a gi ho kk', 'ng m c r d ml rm r');
}
faultsim_save_and_close

foreach {tn expr res} {
  1 { dk  }           7
  2 { m f }           1
  3 { f*  }           {1 3 4 5 6 8 9 10}
  4 { m OR f }        {1 4 5 8 9 10}
  5 { sn + gh }       {5}
  6 { "sn gh" }       {5}
  7 { NEAR(r a, 5) }  {9}
  8 { m* f* }         {1 4 6 8 9 10}
  9 { m* + f* }       {1 8}
} {
  do_faultsim_test 4.$tn -prep {
    faultsim_restore_and_reopen
  } -body "
    execsql { SELECT rowid FROM t2 WHERE t2 MATCH '$expr' }
  " -test "
    faultsim_test_result {[list 0 $res]}
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312

reset_db
db func rnddoc rnddoc

do_test 8.0 {
  execsql { CREATE VIRTUAL TABLE x1 USING fts5(a) }
  set ::res [list]
  for {set i 100} {$i>0} {incr i -1} {
    execsql { INSERT INTO x1 VALUES( rnddoc(50) ) }
    lappend ::res $i
  }
} {}

do_faultsim_test 8.1 -faults oom* -prep {
} -body {







|







298
299
300
301
302
303
304
305
306
307
308
309
310
311
312

reset_db
db func rnddoc rnddoc

do_test 8.0 {
  execsql { CREATE VIRTUAL TABLE x1 USING fts5(a) }
  set ::res [list]
  for {set i 1} {$i<100} {incr i 1} {
    execsql { INSERT INTO x1 VALUES( rnddoc(50) ) }
    lappend ::res $i
  }
} {}

do_faultsim_test 8.1 -faults oom* -prep {
} -body {
Changes to ext/fts5/test/fts5rowid.test.
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
  }
  foreach str $strlist { execsql { INSERT INTO x4 VALUES($str) } }
  execsql COMMIT
} {}

do_execsql_test 5.1 {
  SELECT rowid FROM x4 WHERE x4 MATCH 'a'
} {4 3 2 1}

set res [db one {SELECT count(*) FROM x4_data}]
do_execsql_test 5.2 {
  SELECT count(fts5_decode(rowid, block)) FROM x4_data;
} $res

finish_test







|







168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
  }
  foreach str $strlist { execsql { INSERT INTO x4 VALUES($str) } }
  execsql COMMIT
} {}

do_execsql_test 5.1 {
  SELECT rowid FROM x4 WHERE x4 MATCH 'a'
} {1 2 3 4}

set res [db one {SELECT count(*) FROM x4_data}]
do_execsql_test 5.2 {
  SELECT count(fts5_decode(rowid, block)) FROM x4_data;
} $res

finish_test