/ Check-in [5ae0ba44]
Login

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

Overview
Comment:Experimental changes to fts4 to try to selectively avoid loading very large doclists.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | experimental
Files: files | file ages | folders
SHA1: 5ae0ba447a561e3b6637b52f9b83a9fc683d2572
User & Date: dan 2010-10-19 14:08:00
Context
2010-10-20
18:56
Updates to FTS4 to improve performance and make more accurate cost estimates for prefix terms. check-in: d0a450ce user: dan tags: experimental
2010-10-19
14:08
Experimental changes to fts4 to try to selectively avoid loading very large doclists. check-in: 5ae0ba44 user: dan tags: experimental
2010-10-14
01:17
Avoid taking locks on unused database connections when committing a read transaction. check-in: c0ee614f user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/fts3/fts3.c.

442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
...
509
510
511
512
513
514
515




516
517


518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542

543
544
545
546
547
548
549
...
634
635
636
637
638
639
640































641
642
643
644
645
646
647
...
759
760
761
762
763
764
765
766
767

768
769


770
771


772
773
774
775
776
777
778
779
780


781
782
783
784
785
786
787
...
889
890
891
892
893
894
895

896
897
898
899
900
901
902
...
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
....
1282
1283
1284
1285
1286
1287
1288




















1289
1290
1291
1292
1293

1294
1295
1296
1297
1298
1299
1300
1301
1302




1303
1304
1305
1306
1307
1308
1309
....
1324
1325
1326
1327
1328
1329
1330

1331

1332
1333
1334
1335
1336
1337
1338
....
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
....
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
....
1743
1744
1745
1746
1747
1748
1749





























1750
1751
1752


1753
1754
1755
1756
1757
1758
1759











1760





































1761
1762
1763

1764
1765
1766
1767
1768
1769

1770
1771
1772
1773
1774
1775
1776

1777


1778
1779
1780
1781
1782
1783

1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798

1799

1800
1801
1802
1803
1804
1805
1806
....
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841

1842
1843
1844
1845
1846


1847
1848
1849
1850
1851




1852



1853

1854
1855

























1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877

1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888








































1889
1890
1891






1892











1893
1894






1895
1896
1897

1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908

1909








1910
1911
1912
1913
1914











1915
1916
1917

































1918





1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931








1932
1933
1934
1935
1936
1937
1938










1939


1940





1941



1942
1943
1944




1945
1946
1947
1948
1949
1950
1951
....
2013
2014
2015
2016
2017
2018
2019
2020





















































































2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
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
2063
2064
2065
2066
2067
2068
....
2112
2113
2114
2115
2116
2117
2118



































































2119
2120
2121
2122
2123
2124
2125
....
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
....
2202
2203
2204
2205
2206
2207
2208
2209

2210
2211



2212


















2213
2214
2215
2216
2217
2218
2219
....
2330
2331
2332
2333
2334
2335
2336
2337


2338


2339
2340
2341
2342
2343
2344
2345

  assert( p->nPendingData==0 );

  /* Free any prepared statements held */
  for(i=0; i<SizeofArray(p->aStmt); i++){
    sqlite3_finalize(p->aStmt[i]);
  }
  for(i=0; i<p->nLeavesStmt; i++){
    sqlite3_finalize(p->aLeavesStmt[i]);
  }
  sqlite3_free(p->zSelectLeaves);
  sqlite3_free(p->aLeavesStmt);

  /* Invoke the tokenizer destructor to free the tokenizer. */
  p->pTokenizer->pModule->xDestroy(p->pTokenizer);

  sqlite3_free(p);
  return SQLITE_OK;
}

/*
** Construct one or more SQL statements from the format string given
** and then evaluate those statements.  The success code is writting
** into *pRc.
**
** If *pRc is initially non-zero then this routine is a no-op.
*/
static void fts3DbExec(
  int *pRc,              /* Success code */
  sqlite3 *db,           /* Database in which to run SQL */
................................................................................
}


/*
** Invoke sqlite3_declare_vtab() to declare the schema for the FTS3 table
** passed as the first argument. This is done as part of the xConnect()
** and xCreate() methods.




*/
static int fts3DeclareVtab(Fts3Table *p){


  int i;                          /* Iterator variable */
  int rc;                         /* Return code */
  char *zSql;                     /* SQL statement passed to declare_vtab() */
  char *zCols;                    /* List of user defined columns */

  /* Create a list of user columns for the virtual table */
  zCols = sqlite3_mprintf("%Q, ", p->azColumn[0]);
  for(i=1; zCols && i<p->nColumn; i++){
    zCols = sqlite3_mprintf("%z%Q, ", zCols, p->azColumn[i]);
  }

  /* Create the whole "CREATE TABLE" statement to pass to SQLite */
  zSql = sqlite3_mprintf(
      "CREATE TABLE x(%s %Q HIDDEN, docid HIDDEN)", zCols, p->zName
  );

  if( !zCols || !zSql ){
    rc = SQLITE_NOMEM;
  }else{
    rc = sqlite3_declare_vtab(p->db, zSql);
  }

  sqlite3_free(zSql);
  sqlite3_free(zCols);
  return rc;

}

/*
** Create the backing store tables (%_content, %_segments and %_segdir)
** required by the FTS3 table passed as the only argument. This is done
** as part of the vtab xCreate() method.
**
................................................................................
    zDb, zName, zSuffix
  );    
  rc = sqlite3_exec(db, zSql, fts3TableExistsCallback, &res, 0);
  sqlite3_free(zSql);
  *pResult = (u8)(res & 0xff);
  if( rc!=SQLITE_ABORT ) *pRc = rc;
}
































/*
** This function is the implementation of both the xConnect and xCreate
** methods of the FTS3 virtual table.
**
** The argv[] array contains the following:
**
................................................................................
    p->bHasDocsize = argv[0][3]=='4';
    rc = fts3CreateTables(p);
  }else{
    rc = SQLITE_OK;
    fts3TableExists(&rc, db, argv[1], argv[2], "_content", &p->bHasContent);
    fts3TableExists(&rc, db, argv[1], argv[2], "_docsize", &p->bHasDocsize);
  }
  if( rc!=SQLITE_OK ) goto fts3_init_out;


  rc = fts3DeclareVtab(p);
  if( rc!=SQLITE_OK ) goto fts3_init_out;



  *ppVTab = &p->base;



fts3_init_out:
  assert( p || (pTokenizer && rc!=SQLITE_OK) );
  if( rc!=SQLITE_OK ){
    if( p ){
      fts3DisconnectMethod((sqlite3_vtab *)p);
    }else{
      pTokenizer->pModule->xDestroy(pTokenizer);
    }


  }
  return rc;
}

/*
** The xConnect() and xCreate() methods for the virtual table. All the
** work is done in function fts3InitVtab().
................................................................................
** Close the cursor.  For additional information see the documentation
** on the xClose method of the virtual table interface.
*/
static int fulltextClose(sqlite3_vtab_cursor *pCursor){
  Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;
  sqlite3_finalize(pCsr->pStmt);
  sqlite3Fts3ExprFree(pCsr->pExpr);

  sqlite3_free(pCsr->aDoclist);
  sqlite3_free(pCsr->aMatchinfo);
  sqlite3_free(pCsr);
  return SQLITE_OK;
}

/*
................................................................................
      return rc;
    }
  }else{
    return SQLITE_OK;
  }
}

/*
** Advance the cursor to the next row in the %_content table that
** matches the search criteria.  For a MATCH search, this will be
** the next row that matches.  For a full-table scan, this will be
** simply the next row in the %_content table.  For a docid lookup,
** this routine simply sets the EOF flag.
**
** Return SQLITE_OK if nothing goes wrong.  SQLITE_OK is returned
** even if we reach end-of-file.  The fts3EofMethod() will be called
** subsequently to determine whether or not an EOF was hit.
*/
static int fts3NextMethod(sqlite3_vtab_cursor *pCursor){
  int rc = SQLITE_OK;             /* Return code */
  Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;

  if( pCsr->aDoclist==0 ){
    if( SQLITE_ROW!=sqlite3_step(pCsr->pStmt) ){
      pCsr->isEof = 1;
      rc = sqlite3_reset(pCsr->pStmt);
    }
  }else if( pCsr->pNextId>=&pCsr->aDoclist[pCsr->nDoclist] ){
    pCsr->isEof = 1;
  }else{
    sqlite3_reset(pCsr->pStmt);
    fts3GetDeltaVarint(&pCsr->pNextId, &pCsr->iPrevId);
    pCsr->isRequireSeek = 1;
    pCsr->isMatchinfoNeeded = 1;
  }
  return rc;
}


/*
** The buffer pointed to by argument zNode (size nNode bytes) contains the
** root node of a b-tree segment. The segment is guaranteed to be at least
** one level high (i.e. the root node is not also a leaf). If successful,
** this function locates the leaf node of the segment that may contain the 
................................................................................
  *pp = p;
  *pp1 = p1 + 1;
  *pp2 = p2 + 1;
}

/*
** nToken==1 searches for adjacent positions.




















*/
static int fts3PoslistPhraseMerge(
  char **pp,                      /* Output buffer */
  int nToken,                     /* Maximum difference in token positions */
  int isSaveLeft,                 /* Save the left position */

  char **pp1,                     /* Left input list */
  char **pp2                      /* Right input list */
){
  char *p = (pp ? *pp : 0);
  char *p1 = *pp1;
  char *p2 = *pp2;

  int iCol1 = 0;
  int iCol2 = 0;




  assert( *p1!=0 && *p2!=0 );
  if( *p1==POS_COLUMN ){ 
    p1++;
    p1 += sqlite3Fts3GetVarint32(p1, &iCol1);
  }
  if( *p2==POS_COLUMN ){ 
    p2++;
................................................................................

      assert( *p1!=POS_END && *p1!=POS_COLUMN );
      assert( *p2!=POS_END && *p2!=POS_COLUMN );
      fts3GetDeltaVarint(&p1, &iPos1); iPos1 -= 2;
      fts3GetDeltaVarint(&p2, &iPos2); iPos2 -= 2;

      while( 1 ){

        if( iPos2>iPos1 && iPos2<=iPos1+nToken ){

          sqlite3_int64 iSave;
          if( !pp ){
            fts3PoslistCopy(0, &p2);
            fts3PoslistCopy(0, &p1);
            *pp1 = p1;
            *pp2 = p2;
            return 1;
................................................................................
  char **pp1,                     /* IN/OUT: Left input list */
  char **pp2                      /* IN/OUT: Right input list */
){
  char *p1 = *pp1;
  char *p2 = *pp2;

  if( !pp ){
    if( fts3PoslistPhraseMerge(0, nRight, 0, pp1, pp2) ) return 1;
    *pp1 = p1;
    *pp2 = p2;
    return fts3PoslistPhraseMerge(0, nLeft, 0, pp2, pp1);
  }else{
    char *pTmp1 = aTmp;
    char *pTmp2;
    char *aTmp2;
    int res = 1;

    fts3PoslistPhraseMerge(&pTmp1, nRight, 0, pp1, pp2);
    aTmp2 = pTmp2 = pTmp1;
    *pp1 = p1;
    *pp2 = p2;
    fts3PoslistPhraseMerge(&pTmp2, nLeft, 1, pp2, pp1);
    if( pTmp1!=aTmp && pTmp2!=aTmp2 ){
      fts3PoslistMerge(pp, &aTmp, &aTmp2);
    }else if( pTmp1!=aTmp ){
      fts3PoslistCopy(pp, &aTmp);
    }else if( pTmp2!=aTmp2 ){
      fts3PoslistCopy(pp, &aTmp2);
    }else{
................................................................................
    case MERGE_PHRASE: {
      char **ppPos = (mergetype==MERGE_PHRASE ? 0 : &p);
      while( p1 && p2 ){
        if( i1==i2 ){
          char *pSave = p;
          sqlite3_int64 iPrevSave = iPrev;
          fts3PutDeltaVarint(&p, &iPrev, i1);
          if( 0==fts3PoslistPhraseMerge(ppPos, 1, 0, &p1, &p2) ){
            p = pSave;
            iPrev = iPrevSave;
          }
          fts3GetDeltaVarint2(&p1, pEnd1, &i1);
          fts3GetDeltaVarint2(&p2, pEnd2, &i2);
        }else if( i1<i2 ){
          fts3PoslistCopy(0, &p1);
................................................................................
        pTS->anOutput[iOut] = nMerge;
      }
    }
  }
  return SQLITE_OK;
}






























/*
** This function retreives the doclist for the specified term (or term
** prefix) from the database. 


**
** The returned doclist may be in one of two formats, depending on the 
** value of parameter isReqPos. If isReqPos is zero, then the doclist is
** a sorted list of delta-compressed docids (a bare doclist). If isReqPos
** is non-zero, then the returned list is in the same format as is stored 
** in the database without the found length specifier at the start of on-disk
** doclists.











*/





































static int fts3TermSelect(
  Fts3Table *p,                   /* Virtual table handle */
  int iColumn,                    /* Column to query (or -ve for all columns) */

  const char *zTerm,              /* Term to query for */
  int nTerm,                      /* Size of zTerm in bytes */
  int isPrefix,                   /* True for a prefix search */
  int isReqPos,                   /* True to include position lists in output */
  int *pnOut,                     /* OUT: Size of buffer at *ppOut */
  char **ppOut                    /* OUT: Malloced result buffer */

){
  int i;
  TermSelect tsc;
  Fts3SegFilter filter;           /* Segment term filter configuration */
  Fts3SegReader **apSegment;      /* Array of segments to read data from */
  int nSegment = 0;               /* Size of apSegment array */
  int nAlloc = 16;                /* Allocated size of segment array */

  int rc;                         /* Return code */


  sqlite3_stmt *pStmt = 0;        /* SQL statement to scan %_segdir table */
  int iAge = 0;                   /* Used to assign ages to segments */

  apSegment = (Fts3SegReader **)sqlite3_malloc(sizeof(Fts3SegReader*)*nAlloc);
  if( !apSegment ) return SQLITE_NOMEM;
  rc = sqlite3Fts3SegReaderPending(p, zTerm, nTerm, isPrefix, &apSegment[0]);

  if( rc!=SQLITE_OK ) goto finished;
  if( apSegment[0] ){
    nSegment = 1;
  }

  /* Loop through the entire %_segdir table. For each segment, create a
  ** Fts3SegReader to iterate through the subset of the segment leaves
  ** that may contain a term that matches zTerm/nTerm. For non-prefix
  ** searches, this is always a single leaf. For prefix searches, this
  ** may be a contiguous block of leaves.
  **
  ** The code in this loop does not actually load any leaves into memory
  ** (unless the root node happens to be a leaf). It simply examines the
  ** b-tree structure to determine which leaves need to be inspected.
  */

  rc = sqlite3Fts3AllSegdirs(p, &pStmt);

  while( rc==SQLITE_OK && SQLITE_ROW==(rc = sqlite3_step(pStmt)) ){
    Fts3SegReader *pNew = 0;
    int nRoot = sqlite3_column_bytes(pStmt, 4);
    char const *zRoot = sqlite3_column_blob(pStmt, 4);
    if( sqlite3_column_int64(pStmt, 1)==0 ){
      /* The entire segment is stored on the root node (which must be a
      ** leaf). Do not bother inspecting any data in this case, just
................................................................................
      rc2 = sqlite3Fts3ReadBlock(p, 0, 0, 0);
      if( rc==SQLITE_OK ){
        rc = rc2;
      }
    }
    iAge++;

    /* If a new Fts3SegReader was allocated, add it to the apSegment array. */
    assert( pNew!=0 || rc!=SQLITE_OK );
    if( pNew ){
      if( nSegment==nAlloc ){
        Fts3SegReader **pArray;
        nAlloc += 16;
        pArray = (Fts3SegReader **)sqlite3_realloc(
            apSegment, nAlloc*sizeof(Fts3SegReader *)
        );
        if( !pArray ){

          sqlite3Fts3SegReaderFree(p, pNew);
          rc = SQLITE_NOMEM;
          goto finished;
        }
        apSegment = pArray;


      }
      apSegment[nSegment++] = pNew;
    }
  }
  if( rc!=SQLITE_DONE ){




    assert( rc!=SQLITE_OK );



    goto finished;

  }


























  memset(&tsc, 0, sizeof(TermSelect));
  tsc.isReqPos = isReqPos;

  filter.flags = FTS3_SEGMENT_IGNORE_EMPTY 
        | (isPrefix ? FTS3_SEGMENT_PREFIX : 0)
        | (isReqPos ? FTS3_SEGMENT_REQUIRE_POS : 0)
        | (iColumn<p->nColumn ? FTS3_SEGMENT_COLUMN_FILTER : 0);
  filter.iCol = iColumn;
  filter.zTerm = zTerm;
  filter.nTerm = nTerm;

  rc = sqlite3Fts3SegReaderIterate(p, apSegment, nSegment, &filter,
      fts3TermSelectCb, (void *)&tsc
  );
  if( rc==SQLITE_OK ){
    rc = fts3TermSelectMerge(&tsc);
  }

  if( rc==SQLITE_OK ){
    *ppOut = tsc.aaOutput[0];
    *pnOut = tsc.anOutput[0];
  }else{

    for(i=0; i<SizeofArray(tsc.aaOutput); i++){
      sqlite3_free(tsc.aaOutput[i]);
    }
  }

finished:
  sqlite3_reset(pStmt);
  for(i=0; i<nSegment; i++){
    sqlite3Fts3SegReaderFree(p, apSegment[i]);
  }
  sqlite3_free(apSegment);








































  return rc;
}



















/* 
** Return a DocList corresponding to the phrase *pPhrase.






*/
static int fts3PhraseSelect(
  Fts3Table *p,                   /* Virtual table handle */

  Fts3Phrase *pPhrase,            /* Phrase to return a doclist for */
  int isReqPos,                   /* True if output should contain positions */
  char **paOut,                   /* OUT: Pointer to malloc'd result buffer */
  int *pnOut                      /* OUT: Size of buffer at *paOut */
){
  char *pOut = 0;
  int nOut = 0;
  int rc = SQLITE_OK;
  int ii;
  int iCol = pPhrase->iColumn;
  int isTermPos = (pPhrase->nToken>1 || isReqPos);










  for(ii=0; ii<pPhrase->nToken; ii++){
    struct PhraseToken *pTok = &pPhrase->aToken[ii];
    char *z = pTok->z;            /* Next token of the phrase */
    int n = pTok->n;              /* Size of z in bytes */
    int isPrefix = pTok->isPrefix;/* True if token is a prefix */











    char *pList;                  /* Pointer to token doclist */
    int nList;                    /* Size of buffer at pList */


































    rc = fts3TermSelect(p, iCol, z, n, isPrefix, isTermPos, &nList, &pList);





    if( rc!=SQLITE_OK ) break;

    if( ii==0 ){
      pOut = pList;
      nOut = nList;
    }else{
      /* Merge the new term list and the current output. If this is the
      ** last term in the phrase, and positions are not required in the
      ** output of this function, the positions can be dropped as part
      ** of this merge. Either way, the result of this merge will be
      ** smaller than nList bytes. The code in fts3DoclistMerge() is written
      ** so that it is safe to use pList as the output as well as an input
      ** in this case.








      */
      int mergetype = MERGE_POS_PHRASE;
      if( ii==pPhrase->nToken-1 && !isReqPos ){
        mergetype = MERGE_PHRASE;
      }
      fts3DoclistMerge(mergetype, 0, 0, pList, &nOut, pOut, nOut, pList, nList);
      sqlite3_free(pOut);










      pOut = pList;


    }





    assert( nOut==0 || pOut!=0 );



  }

  if( rc==SQLITE_OK ){




    *paOut = pOut;
    *pnOut = nOut;
  }else{
    sqlite3_free(pOut);
  }
  return rc;
}
................................................................................
    );
    sqlite3_free(pLeft->aDoclist);
    pLeft->aDoclist = aOut;
    pLeft->nDoclist = nOut;
  }
  return rc;
}






















































































/*
** Evaluate the full-text expression pExpr against fts3 table pTab. Store
** the resulting doclist in *paOut and *pnOut.  This routine mallocs for
** the space needed to store the output.  The caller is responsible for
** freeing the space when it has finished.
*/
static int evalFts3Expr(
  Fts3Table *p,                   /* Virtual table handle */
  Fts3Expr *pExpr,                /* Parsed fts3 expression */
  char **paOut,                   /* OUT: Pointer to malloc'd result buffer */
  int *pnOut,                     /* OUT: Size of buffer at *paOut */
  int isReqPos                    /* Require positions in output buffer */
){
  int rc = SQLITE_OK;             /* Return code */

  /* Zero the output parameters. */
  *paOut = 0;
  *pnOut = 0;

  if( pExpr ){




    assert( pExpr->eType==FTSQUERY_PHRASE 
         || pExpr->eType==FTSQUERY_NEAR 
         || isReqPos==0
    );

    if( pExpr->eType==FTSQUERY_PHRASE ){
      rc = fts3PhraseSelect(p, pExpr->pPhrase, 
          isReqPos || (pExpr->pParent && pExpr->pParent->eType==FTSQUERY_NEAR),
          paOut, pnOut
      );




































    }else{























      char *aLeft;
      char *aRight;
      int nLeft;
      int nRight;







      if( 0==(rc = evalFts3Expr(p, pExpr->pRight, &aRight, &nRight, isReqPos))
       && 0==(rc = evalFts3Expr(p, pExpr->pLeft, &aLeft, &nLeft, isReqPos))
      ){
        assert( pExpr->eType==FTSQUERY_NEAR || pExpr->eType==FTSQUERY_OR     
            || pExpr->eType==FTSQUERY_AND  || pExpr->eType==FTSQUERY_NOT
        );
        switch( pExpr->eType ){
          case FTSQUERY_NEAR: {
            Fts3Expr *pLeft;
            Fts3Expr *pRight;
            int mergetype = isReqPos ? MERGE_POS_NEAR : MERGE_NEAR;
           
            if( pExpr->pParent && pExpr->pParent->eType==FTSQUERY_NEAR ){
................................................................................
      }
      sqlite3_free(aRight);
    }
  }

  return rc;
}




































































/*
** This is the xFilter interface for the virtual table.  See
** the virtual table xFilter method documentation for additional
** information.
**
** If idxNum==FTS3_FULLSCAN_SEARCH then do a full table scan against
................................................................................

  /* In case the cursor has been used before, clear it now. */
  sqlite3_finalize(pCsr->pStmt);
  sqlite3_free(pCsr->aDoclist);
  sqlite3Fts3ExprFree(pCsr->pExpr);
  memset(&pCursor[1], 0, sizeof(Fts3Cursor)-sizeof(sqlite3_vtab_cursor));

  /* Compile a SELECT statement for this cursor. For a full-table-scan, the
  ** statement loops through all rows of the %_content table. For a
  ** full-text query or docid lookup, the statement retrieves a single
  ** row by docid.
  */
  zSql = sqlite3_mprintf(azSql[idxNum==FTS3_FULLSCAN_SEARCH], p->zDb, p->zName);
  if( !zSql ){
    rc = SQLITE_NOMEM;
  }else{
    rc = sqlite3_prepare_v2(p->db, zSql, -1, &pCsr->pStmt, 0);
    sqlite3_free(zSql);
  }
  if( rc!=SQLITE_OK ) return rc;
  pCsr->eSearch = (i16)idxNum;

  if( idxNum==FTS3_DOCID_SEARCH ){
    rc = sqlite3_bind_value(pCsr->pStmt, 1, apVal[0]);
  }else if( idxNum!=FTS3_FULLSCAN_SEARCH ){
    int iCol = idxNum-FTS3_FULLTEXT_SEARCH;
    const char *zQuery = (const char *)sqlite3_value_text(apVal[0]);

    if( zQuery==0 && sqlite3_value_type(apVal[0])!=SQLITE_NULL ){
      return SQLITE_NOMEM;
    }

................................................................................
      }
      return rc;
    }

    rc = sqlite3Fts3ReadLock(p);
    if( rc!=SQLITE_OK ) return rc;

    rc = evalFts3Expr(p, pCsr->pExpr, &pCsr->aDoclist, &pCsr->nDoclist, 0);

    pCsr->pNextId = pCsr->aDoclist;
    pCsr->iPrevId = 0;



  }



















  if( rc!=SQLITE_OK ) return rc;
  return fts3NextMethod(pCursor);
}

/* 
** This is the xEof method of the virtual table. SQLite calls this 
................................................................................

/*
** Load the doclist associated with expression pExpr to pExpr->aDoclist.
** The loaded doclist contains positions as well as the document ids.
** This is used by the matchinfo(), snippet() and offsets() auxillary
** functions.
*/
int sqlite3Fts3ExprLoadDoclist(Fts3Table *pTab, Fts3Expr *pExpr){


  return evalFts3Expr(pTab, pExpr, &pExpr->aDoclist, &pExpr->nDoclist, 1);


}

/*
** After ExprLoadDoclist() (see above) has been called, this function is
** used to iterate/search through the position lists that make up the doclist
** stored in pExpr->aDoclist.
*/







<
<
<
|
<










|







 







>
>
>
>

<
>
>
|
|
|
|

|
|
|
|
|

|
|
|
|
<
|
|
|
|
|

|
|
|
>







 







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







 







<

>
|
|
>
>

<
>
>









>
>







 







>







 







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

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







 







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


|


>
|
|




<


>
>
>
>







 







>
|
>







 







|


|






|



|







 







|







 







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

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

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



<
<
<
>

<
<
<
<
<
<
>

>
>



|
<
|
>
|
<
<







<
<
<
<

>
|
>







 







|

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

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




|



|
|

|
|









>





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



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


>
>
>
>
>
>


<
>











>

>
>
>
>
>
>
>
>

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



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






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

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

>
>
>



>
>
>
>







 








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






|
|












>
>
>
>




>

|



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





>
>
>
>
>
>
|
|

<
<
<







 







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







 







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







 







|
>


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







 







|
>
>
|
>
>







442
443
444
445
446
447
448



449

450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
...
505
506
507
508
509
510
511
512
513
514
515
516

517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533

534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
...
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
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
...
791
792
793
794
795
796
797

798
799
800
801
802
803
804

805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
...
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
...
964
965
966
967
968
969
970














971















972
973
974
975
976
977
978
....
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329

1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
....
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
....
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
....
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
....
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814


1815
1816
1817






1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867


1868
1869
1870
1871



1872
1873






1874
1875
1876
1877
1878
1879
1880
1881

1882
1883
1884


1885
1886
1887
1888
1889
1890
1891




1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
....
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930

1931





1932
1933


1934

1935
1936
1937

1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005

2006
2007
2008
2009

2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
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
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080

2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104



2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
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
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
....
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475



2476
2477
2478
2479
2480
2481
2482
....
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
....
2644
2645
2646
2647
2648
2649
2650















2651


2652
2653
2654
2655
2656
2657
2658
....
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
....
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835

  assert( p->nPendingData==0 );

  /* Free any prepared statements held */
  for(i=0; i<SizeofArray(p->aStmt); i++){
    sqlite3_finalize(p->aStmt[i]);
  }



  sqlite3_free(p->zSegmentsTbl);


  /* Invoke the tokenizer destructor to free the tokenizer. */
  p->pTokenizer->pModule->xDestroy(p->pTokenizer);

  sqlite3_free(p);
  return SQLITE_OK;
}

/*
** Construct one or more SQL statements from the format string given
** and then evaluate those statements. The success code is written
** into *pRc.
**
** If *pRc is initially non-zero then this routine is a no-op.
*/
static void fts3DbExec(
  int *pRc,              /* Success code */
  sqlite3 *db,           /* Database in which to run SQL */
................................................................................
}


/*
** Invoke sqlite3_declare_vtab() to declare the schema for the FTS3 table
** passed as the first argument. This is done as part of the xConnect()
** and xCreate() methods.
**
** If *pRc is non-zero when this function is called, it is a no-op. 
** Otherwise, if an error occurs, an SQLite error code is stored in *pRc
** before returning.
*/

static void fts3DeclareVtab(int *pRc, Fts3Table *p){
  if( *pRc==SQLITE_OK ){
    int i;                        /* Iterator variable */
    int rc;                       /* Return code */
    char *zSql;                   /* SQL statement passed to declare_vtab() */
    char *zCols;                  /* List of user defined columns */

    /* Create a list of user columns for the virtual table */
    zCols = sqlite3_mprintf("%Q, ", p->azColumn[0]);
    for(i=1; zCols && i<p->nColumn; i++){
      zCols = sqlite3_mprintf("%z%Q, ", zCols, p->azColumn[i]);
    }

    /* Create the whole "CREATE TABLE" statement to pass to SQLite */
    zSql = sqlite3_mprintf(
        "CREATE TABLE x(%s %Q HIDDEN, docid HIDDEN)", zCols, p->zName
    );

    if( !zCols || !zSql ){
      rc = SQLITE_NOMEM;
    }else{
      rc = sqlite3_declare_vtab(p->db, zSql);
    }

    sqlite3_free(zSql);
    sqlite3_free(zCols);
    *pRc = rc;
  }
}

/*
** Create the backing store tables (%_content, %_segments and %_segdir)
** required by the FTS3 table passed as the only argument. This is done
** as part of the vtab xCreate() method.
**
................................................................................
    zDb, zName, zSuffix
  );    
  rc = sqlite3_exec(db, zSql, fts3TableExistsCallback, &res, 0);
  sqlite3_free(zSql);
  *pResult = (u8)(res & 0xff);
  if( rc!=SQLITE_ABORT ) *pRc = rc;
}

/*
** Store the current database page-size in bytes in p->nPgsz.
**
** If *pRc is non-zero when this function is called, it is a no-op. 
** Otherwise, if an error occurs, an SQLite error code is stored in *pRc
** before returning.
*/
static void fts3DatabasePageSize(int *pRc, Fts3Table *p){
  if( *pRc==SQLITE_OK ){
    int rc;                       /* Return code */
    char *zSql;                   /* SQL text "PRAGMA %Q.page_size" */
    sqlite3_stmt *pStmt;          /* Compiled "PRAGMA %Q.page_size" statement */
  
    zSql = sqlite3_mprintf("PRAGMA %Q.page_size", p->zDb);
    if( !zSql ){
      rc = SQLITE_NOMEM;
    }else{
      rc = sqlite3_prepare(p->db, zSql, -1, &pStmt, 0);
      if( rc==SQLITE_OK ){
        if( SQLITE_ROW==sqlite3_step(pStmt) ){
          p->nPgsz = sqlite3_column_int(pStmt, 0);
        }
        rc = sqlite3_finalize(pStmt);
      }
    }
    assert( p->nPgsz>0 || rc!=SQLITE_OK );
    sqlite3_free(zSql);
    *pRc = rc;
  }
}

/*
** This function is the implementation of both the xConnect and xCreate
** methods of the FTS3 virtual table.
**
** The argv[] array contains the following:
**
................................................................................
    p->bHasDocsize = argv[0][3]=='4';
    rc = fts3CreateTables(p);
  }else{
    rc = SQLITE_OK;
    fts3TableExists(&rc, db, argv[1], argv[2], "_content", &p->bHasContent);
    fts3TableExists(&rc, db, argv[1], argv[2], "_docsize", &p->bHasDocsize);
  }


  /* Figure out the page-size for the database. This is required in order to
  ** estimate the cost of loading large doclists from the database (see 
  ** function sqlite3Fts3SegReaderCost() for details).
  */
  fts3DatabasePageSize(&rc, p);


  /* Declare the table schema to SQLite. */
  fts3DeclareVtab(&rc, p);

fts3_init_out:
  assert( p || (pTokenizer && rc!=SQLITE_OK) );
  if( rc!=SQLITE_OK ){
    if( p ){
      fts3DisconnectMethod((sqlite3_vtab *)p);
    }else{
      pTokenizer->pModule->xDestroy(pTokenizer);
    }
  }else{
    *ppVTab = &p->base;
  }
  return rc;
}

/*
** The xConnect() and xCreate() methods for the virtual table. All the
** work is done in function fts3InitVtab().
................................................................................
** Close the cursor.  For additional information see the documentation
** on the xClose method of the virtual table interface.
*/
static int fulltextClose(sqlite3_vtab_cursor *pCursor){
  Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;
  sqlite3_finalize(pCsr->pStmt);
  sqlite3Fts3ExprFree(pCsr->pExpr);
  sqlite3Fts3FreeDeferredTokens(pCsr);
  sqlite3_free(pCsr->aDoclist);
  sqlite3_free(pCsr->aMatchinfo);
  sqlite3_free(pCsr);
  return SQLITE_OK;
}

/*
................................................................................
      return rc;
    }
  }else{
    return SQLITE_OK;
  }
}

































/*
** The buffer pointed to by argument zNode (size nNode bytes) contains the
** root node of a b-tree segment. The segment is guaranteed to be at least
** one level high (i.e. the root node is not also a leaf). If successful,
** this function locates the leaf node of the segment that may contain the 
................................................................................
  *pp = p;
  *pp1 = p1 + 1;
  *pp2 = p2 + 1;
}

/*
** nToken==1 searches for adjacent positions.
**
** This function is used to merge two position lists into one. When it is
** called, *pp1 and *pp2 must both point to position lists. A position-list is
** the part of a doclist that follows each document id. For example, if a row
** contains:
**
**     'a b c'|'x y z'|'a b b a'
**
** Then the position list for this row for token 'b' would consist of:
**
**     0x02 0x01 0x02 0x03 0x03 0x00
**
** When this function returns, both *pp1 and *pp2 are left pointing to the
** byte following the 0x00 terminator of their respective position lists.
**
** If isSaveLeft is 0, an entry is added to the output position list for 
** each position in *pp2 for which there exists one or more positions in
** *pp1 so that (pos(*pp2)>pos(*pp1) && pos(*pp2)-pos(*pp1)<=nToken). i.e.
** when the *pp1 token appears before the *pp2 token, but not more than nToken
** slots before it.
*/
static int fts3PoslistPhraseMerge(
  char **pp,                      /* IN/OUT: Preallocated output buffer */
  int nToken,                     /* Maximum difference in token positions */
  int isSaveLeft,                 /* Save the left position */
  int isExact,                    /* If *pp1 is exactly nTokens before *pp2 */
  char **pp1,                     /* IN/OUT: Left input list */
  char **pp2                      /* IN/OUT: Right input list */
){
  char *p = (pp ? *pp : 0);
  char *p1 = *pp1;
  char *p2 = *pp2;

  int iCol1 = 0;
  int iCol2 = 0;

  /* Never set both isSaveLeft and isExact for the same invocation. */
  assert( isSaveLeft==0 || isExact==0 );

  assert( *p1!=0 && *p2!=0 );
  if( *p1==POS_COLUMN ){ 
    p1++;
    p1 += sqlite3Fts3GetVarint32(p1, &iCol1);
  }
  if( *p2==POS_COLUMN ){ 
    p2++;
................................................................................

      assert( *p1!=POS_END && *p1!=POS_COLUMN );
      assert( *p2!=POS_END && *p2!=POS_COLUMN );
      fts3GetDeltaVarint(&p1, &iPos1); iPos1 -= 2;
      fts3GetDeltaVarint(&p2, &iPos2); iPos2 -= 2;

      while( 1 ){
        if( iPos2==iPos1+nToken 
         || (isExact==0 && iPos2>iPos1 && iPos2<=iPos1+nToken) 
        ){
          sqlite3_int64 iSave;
          if( !pp ){
            fts3PoslistCopy(0, &p2);
            fts3PoslistCopy(0, &p1);
            *pp1 = p1;
            *pp2 = p2;
            return 1;
................................................................................
  char **pp1,                     /* IN/OUT: Left input list */
  char **pp2                      /* IN/OUT: Right input list */
){
  char *p1 = *pp1;
  char *p2 = *pp2;

  if( !pp ){
    if( fts3PoslistPhraseMerge(0, nRight, 0, 0, pp1, pp2) ) return 1;
    *pp1 = p1;
    *pp2 = p2;
    return fts3PoslistPhraseMerge(0, nLeft, 0, 0, pp2, pp1);
  }else{
    char *pTmp1 = aTmp;
    char *pTmp2;
    char *aTmp2;
    int res = 1;

    fts3PoslistPhraseMerge(&pTmp1, nRight, 0, 0, pp1, pp2);
    aTmp2 = pTmp2 = pTmp1;
    *pp1 = p1;
    *pp2 = p2;
    fts3PoslistPhraseMerge(&pTmp2, nLeft, 1, 0, pp2, pp1);
    if( pTmp1!=aTmp && pTmp2!=aTmp2 ){
      fts3PoslistMerge(pp, &aTmp, &aTmp2);
    }else if( pTmp1!=aTmp ){
      fts3PoslistCopy(pp, &aTmp);
    }else if( pTmp2!=aTmp2 ){
      fts3PoslistCopy(pp, &aTmp2);
    }else{
................................................................................
    case MERGE_PHRASE: {
      char **ppPos = (mergetype==MERGE_PHRASE ? 0 : &p);
      while( p1 && p2 ){
        if( i1==i2 ){
          char *pSave = p;
          sqlite3_int64 iPrevSave = iPrev;
          fts3PutDeltaVarint(&p, &iPrev, i1);
          if( 0==fts3PoslistPhraseMerge(ppPos, nParam1, 0, 1, &p1, &p2) ){
            p = pSave;
            iPrev = iPrevSave;
          }
          fts3GetDeltaVarint2(&p1, pEnd1, &i1);
          fts3GetDeltaVarint2(&p2, pEnd2, &i2);
        }else if( i1<i2 ){
          fts3PoslistCopy(0, &p1);
................................................................................
        pTS->anOutput[iOut] = nMerge;
      }
    }
  }
  return SQLITE_OK;
}

static int fts3DeferredTermSelect(
  Fts3DeferredToken *pToken,      /* Phrase token */
  int isTermPos,                  /* True to include positions */
  int *pnOut,                     /* OUT: Size of list */
  char **ppOut                    /* OUT: Body of list */
){
  char *aSource;
  int nSource;

  aSource = sqlite3Fts3DeferredDoclist(pToken, &nSource);
  if( !aSource ){
    *pnOut = 0;
    *ppOut = 0;
  }else if( isTermPos ){
    *ppOut = sqlite3_malloc(nSource);
    if( !*ppOut ) return SQLITE_NOMEM;
    memcpy(*ppOut, aSource, nSource);
    *pnOut = nSource;
  }else{
    sqlite3_int64 docid;
    *pnOut = sqlite3Fts3GetVarint(aSource, &docid);
    *ppOut = sqlite3_malloc(*pnOut);
    if( !*ppOut ) return SQLITE_NOMEM;
    sqlite3Fts3PutVarint(*ppOut, docid);
  }

  return SQLITE_OK;
}

/*


** An Fts3SegReaderArray is used to store an array of Fts3SegReader objects.
** Elements are added to the array using fts3SegReaderArrayAdd(). 
*/






struct Fts3SegReaderArray {
  int nSegment;                   /* Number of valid entries in apSegment[] */
  int nAlloc;                     /* Allocated size of apSegment[] */
  int nCost;                      /* The cost of executing SegReaderIterate() */
  Fts3SegReader *apSegment[1];    /* Array of seg-reader objects */
};


/*
** Free an Fts3SegReaderArray object. Also free all seg-readers in the
** array (using sqlite3Fts3SegReaderFree()).
*/
static void fts3SegReaderArrayFree(Fts3SegReaderArray *pArray){
  if( pArray ){
    int i;
    for(i=0; i<pArray->nSegment; i++){
      sqlite3Fts3SegReaderFree(0, pArray->apSegment[i]);
    }
    sqlite3_free(pArray);
  }
}

static int fts3SegReaderArrayAdd(
  Fts3SegReaderArray **ppArray, 
  Fts3SegReader *pNew
){
  Fts3SegReaderArray *pArray = *ppArray;

  if( !pArray || pArray->nAlloc==pArray->nSegment ){
    int nNew = (pArray ? pArray->nAlloc+16 : 16);
    pArray = (Fts3SegReaderArray *)sqlite3_realloc(pArray, 
        sizeof(Fts3SegReaderArray) + (nNew-1) * sizeof(Fts3SegReader*)
    );
    if( !pArray ){
      sqlite3Fts3SegReaderFree(0, pNew);
      return SQLITE_NOMEM;
    }
    if( nNew==16 ){
      pArray->nSegment = 0;
      pArray->nCost = 0;
    }
    pArray->nAlloc = nNew;
    *ppArray = pArray;
  }

  pArray->apSegment[pArray->nSegment++] = pNew;
  return SQLITE_OK;
}

static int fts3TermSegReaderArray(


  Fts3Cursor *pCsr,               /* Virtual table cursor handle */
  const char *zTerm,              /* Term to query for */
  int nTerm,                      /* Size of zTerm in bytes */
  int isPrefix,                   /* True for a prefix search */



  Fts3SegReaderArray **ppArray    /* OUT: Allocated seg-reader array */
){






  Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
  int rc;                         /* Return code */
  Fts3SegReaderArray *pArray = 0; /* Array object to build */
  Fts3SegReader *pReader = 0;     /* Seg-reader to add to pArray */ 
  sqlite3_stmt *pStmt = 0;        /* SQL statement to scan %_segdir table */
  int iAge = 0;                   /* Used to assign ages to segments */

  /* Allocate a seg-reader to scan the pending terms, if any. */

  rc = sqlite3Fts3SegReaderPending(p, zTerm, nTerm, isPrefix, &pReader);
  if( rc==SQLITE_OK && pReader ) {
    rc = fts3SegReaderArrayAdd(&pArray, pReader);


  }

  /* Loop through the entire %_segdir table. For each segment, create a
  ** Fts3SegReader to iterate through the subset of the segment leaves
  ** that may contain a term that matches zTerm/nTerm. For non-prefix
  ** searches, this is always a single leaf. For prefix searches, this
  ** may be a contiguous block of leaves.




  */
  if( rc==SQLITE_OK ){
    rc = sqlite3Fts3AllSegdirs(p, &pStmt);
  }
  while( rc==SQLITE_OK && SQLITE_ROW==(rc = sqlite3_step(pStmt)) ){
    Fts3SegReader *pNew = 0;
    int nRoot = sqlite3_column_bytes(pStmt, 4);
    char const *zRoot = sqlite3_column_blob(pStmt, 4);
    if( sqlite3_column_int64(pStmt, 1)==0 ){
      /* The entire segment is stored on the root node (which must be a
      ** leaf). Do not bother inspecting any data in this case, just
................................................................................
      rc2 = sqlite3Fts3ReadBlock(p, 0, 0, 0);
      if( rc==SQLITE_OK ){
        rc = rc2;
      }
    }
    iAge++;

    /* If a new Fts3SegReader was allocated, add it to the array. */
    assert( pNew!=0 || rc!=SQLITE_OK );
    if( rc==SQLITE_OK ){

      rc = fts3SegReaderArrayAdd(&pArray, pNew);





    }else{
      sqlite3Fts3SegReaderFree(p, pNew);


    }

    if( rc==SQLITE_OK ){
      rc = sqlite3Fts3SegReaderCost(pCsr, pNew, &pArray->nCost);
    }

  }

  if( rc==SQLITE_DONE ){
    rc = sqlite3_reset(pStmt);
  }else{
    sqlite3_reset(pStmt);
  }
  if( rc!=SQLITE_OK ){
    fts3SegReaderArrayFree(pArray);
    pArray = 0;
  }
  *ppArray = pArray;
  return rc;
}

/*
** This function retreives the doclist for the specified term (or term
** prefix) from the database. 
**
** The returned doclist may be in one of two formats, depending on the 
** value of parameter isReqPos. If isReqPos is zero, then the doclist is
** a sorted list of delta-compressed docids (a bare doclist). If isReqPos
** is non-zero, then the returned list is in the same format as is stored 
** in the database without the found length specifier at the start of on-disk
** doclists.
*/
static int fts3TermSelect(
  Fts3Table *p,                   /* Virtual table handle */
  Fts3PhraseToken *pTok,          /* Token to query for */
  int iColumn,                    /* Column to query (or -ve for all columns) */
  int isReqPos,                   /* True to include position lists in output */
  int *pnOut,                     /* OUT: Size of buffer at *ppOut */
  char **ppOut                    /* OUT: Malloced result buffer */
){
  int rc;                         /* Return code */
  Fts3SegReaderArray *pArray;     /* Seg-reader array for this term */
  TermSelect tsc;               /* Context object for fts3TermSelectCb() */
  Fts3SegFilter filter;         /* Segment term filter configuration */

  pArray = pTok->pArray;
  memset(&tsc, 0, sizeof(TermSelect));
  tsc.isReqPos = isReqPos;

  filter.flags = FTS3_SEGMENT_IGNORE_EMPTY 
        | (pTok->isPrefix ? FTS3_SEGMENT_PREFIX : 0)
        | (isReqPos ? FTS3_SEGMENT_REQUIRE_POS : 0)
        | (iColumn<p->nColumn ? FTS3_SEGMENT_COLUMN_FILTER : 0);
  filter.iCol = iColumn;
  filter.zTerm = pTok->z;
  filter.nTerm = pTok->n;

  rc = sqlite3Fts3SegReaderIterate(p, pArray->apSegment, pArray->nSegment, 
      &filter, fts3TermSelectCb, (void *)&tsc
  );
  if( rc==SQLITE_OK ){
    rc = fts3TermSelectMerge(&tsc);
  }

  if( rc==SQLITE_OK ){
    *ppOut = tsc.aaOutput[0];
    *pnOut = tsc.anOutput[0];
  }else{
    int i;
    for(i=0; i<SizeofArray(tsc.aaOutput); i++){
      sqlite3_free(tsc.aaOutput[i]);
    }
  }


  fts3SegReaderArrayFree(pArray);
  pTok->pArray = 0;
  return rc;
}


static int fts3DoclistCountDocids(int isPoslist, char *aList, int nList){
  int nDoc = 0;                   /* Return value */
  if( aList ){
    char *aEnd = &aList[nList];   /* Pointer to one byte after EOF */
    char *p = aList;              /* Cursor */
    sqlite3_int64 dummy;          /* For Fts3GetVarint() */
  
    while( p<aEnd ){
      nDoc++;
      p += sqlite3Fts3GetVarint(p, &dummy);
      if( isPoslist ) fts3PoslistCopy(0, &p);
    }
  }

  return nDoc;
}

/*
** Call sqlite3Fts3DeferToken() for each token in the expression pExpr.
*/
static int fts3DeferExpression(Fts3Cursor *pCsr, Fts3Expr *pExpr){
  int rc = SQLITE_OK;
  if( pExpr ){
    rc = fts3DeferExpression(pCsr, pExpr->pLeft);
    if( rc==SQLITE_OK ){
      rc = fts3DeferExpression(pCsr, pExpr->pRight);
    }
    if( pExpr->eType==FTSQUERY_PHRASE ){
      int iCol = pExpr->pPhrase->iColumn;
      int i;
      pExpr->bDeferred = 1;
      for(i=0; rc==SQLITE_OK && i<pExpr->pPhrase->nToken; i++){
        Fts3PhraseToken *pToken = &pExpr->pPhrase->aToken[i];
        if( pToken->pDeferred==0 ){
          rc = sqlite3Fts3DeferToken(pCsr, pToken, iCol);
        }
      }
    }
  }
  return rc;
}

static void fts3DoclistStripPositions(char *aList, int *pnList){
  if( aList ){
    char *aEnd = &aList[*pnList]; /* Pointer to one byte after EOF */
    char *p = aList;              /* Input cursor */
    char *pOut = aList;           /* Output cursor */
    sqlite3_int64 iPrev = 0;
  
    while( p<aEnd ){
      sqlite3_int64 delta;
      p += sqlite3Fts3GetVarint(p, &delta);
      fts3PoslistCopy(0, &p);
      pOut += sqlite3Fts3PutVarint(pOut, delta);
    }

    *pnList = (pOut - aList);
  }
}

/* 
** Return a DocList corresponding to the phrase *pPhrase.
**
** If this function returns SQLITE_OK, but *pnOut is set to a negative value,
** then no tokens in the phrase were looked up in the full-text index. This
** is only possible when this function is called from within xFilter(). The
** caller should assume that all documents match the phrase. The actual
** filtering will take place in xNext().
*/
static int fts3PhraseSelect(

  Fts3Cursor *pCsr,               /* Virtual table cursor handle */
  Fts3Phrase *pPhrase,            /* Phrase to return a doclist for */
  int isReqPos,                   /* True if output should contain positions */
  char **paOut,                   /* OUT: Pointer to malloc'd result buffer */
  int *pnOut                      /* OUT: Size of buffer at *paOut */
){
  char *pOut = 0;
  int nOut = 0;
  int rc = SQLITE_OK;
  int ii;
  int iCol = pPhrase->iColumn;
  int isTermPos = (pPhrase->nToken>1 || isReqPos);
  Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;

  int iPrevTok = 0;
  int nDoc = 0;

  /* If this is an xFilter() evaluation, create a segment-reader for each
  ** phrase token. Or, if this is an xNest() or snippet/offsets/matchinfo
  ** evaluation, only create segment-readers if there are no Fts3DeferredToken
  ** objects attached to the phrase-tokens.
  */
  for(ii=0; ii<pPhrase->nToken; ii++){
    Fts3PhraseToken *pTok = &pPhrase->aToken[ii];



    if( pTok->pArray==0 && (pCsr->doDeferred==0 || pTok->pDeferred==0) ){
      rc = fts3TermSegReaderArray(
          pCsr, pTok->z, pTok->n, pTok->isPrefix, &pTok->pArray
      );
      if( rc!=SQLITE_OK ) return rc;
    }
  }

  for(ii=0; ii<pPhrase->nToken; ii++){
    Fts3PhraseToken *pTok;        /* Token to find doclist for */
    int iTok;                     /* The token being queried this iteration */
    char *pList;                  /* Pointer to token doclist */
    int nList;                    /* Size of buffer at pList */

    /* Select a token to process. If this is an xFilter() call, then tokens 
    ** are processed in order from least to most costly. Otherwise, tokens 
    ** are processed in the order in which they occur in the phrase.
    */
    if( pCsr->doDeferred || isReqPos ){
      iTok = ii;
      pTok = &pPhrase->aToken[iTok];
    }else{
      int nMinCost = 0x7FFFFFFF;
      int jj;

      /* Find the remaining token with the lowest cost. */
      for(jj=0; jj<pPhrase->nToken; jj++){
        Fts3SegReaderArray *pArray = pPhrase->aToken[jj].pArray;
        if( pArray && pArray->nCost<nMinCost ){
          iTok = jj;
          nMinCost = pArray->nCost;
        }
      }
      pTok = &pPhrase->aToken[iTok];

      /* This branch is taken if it is determined that loading the doclist
      ** for the next token would require more IO than loading all documents
      ** currently identified by doclist pOut/nOut. No further doclists will
      ** be loaded from the full-text index for this phrase.
      */
      if( nMinCost>nDoc && ii>0 ){
        rc = fts3DeferExpression(pCsr, pCsr->pExpr);
        break;
      }
    }

    if( pCsr->doDeferred && pTok->pDeferred ){
      rc = fts3DeferredTermSelect(pTok->pDeferred, isTermPos, &nList, &pList);
    }else{
      assert( pTok->pArray );
      rc = fts3TermSelect(p, pTok, iCol, isTermPos, &nList, &pList);
    }
    assert( rc!=SQLITE_OK || pCsr->doDeferred || pTok->pArray==0 );
    if( rc!=SQLITE_OK ) break;

    if( ii==0 ){
      pOut = pList;
      nOut = nList;
    }else{
      /* Merge the new term list and the current output. */






      char *aLeft, *aRight;
      int nLeft, nRight;
      int nDist;
      int mt;

      /* If this is the final token of the phrase, and positions were not
      ** requested by the caller, use MERGE_PHRASE instead of POS_PHRASE.
      ** This drops the position information from the output list.
      */
      mt = MERGE_POS_PHRASE;
      if( ii==pPhrase->nToken-1 && !isReqPos ) mt = MERGE_PHRASE;




      assert( iPrevTok!=iTok );
      if( iPrevTok<iTok ){
        aLeft = pOut;
        nLeft = nOut;
        aRight = pList;
        nRight = nList;
        nDist = iTok-iPrevTok;
      }else{
        aRight = pOut;
        nRight = nOut;
        aLeft = pList;
        nLeft = nList;
        nDist = iPrevTok-iTok;
      }
      pOut = aRight;
     
      fts3DoclistMerge(mt, nDist, 0, pOut, &nOut, aLeft, nLeft, aRight, nRight);
      sqlite3_free(aLeft);
    }
    assert( nOut==0 || pOut!=0 );

    iPrevTok = iTok;
    nDoc = fts3DoclistCountDocids(ii<(pPhrase->nToken-1), pOut, nOut);
  }

  if( rc==SQLITE_OK ){
    if( ii!=pPhrase->nToken ){
      assert( pCsr->doDeferred==0 && isReqPos==0 );
      fts3DoclistStripPositions(pOut, &nOut);
    }
    *paOut = pOut;
    *pnOut = nOut;
  }else{
    sqlite3_free(pOut);
  }
  return rc;
}
................................................................................
    );
    sqlite3_free(pLeft->aDoclist);
    pLeft->aDoclist = aOut;
    pLeft->nDoclist = nOut;
  }
  return rc;
}

typedef struct ExprAndCost ExprAndCost;
struct ExprAndCost {
  Fts3Expr *pExpr;
  int nCost;
};

int fts3ExprCost(Fts3Expr *pExpr){
  int nCost;                      /* Return value */
  if( pExpr->eType==FTSQUERY_PHRASE ){
    Fts3Phrase *pPhrase = pExpr->pPhrase;
    int ii;
    nCost = 0;
    for(ii=0; ii<pPhrase->nToken; ii++){
      nCost += pPhrase->aToken[ii].pArray->nCost;
    }
  }else{
    nCost = fts3ExprCost(pExpr->pLeft) + fts3ExprCost(pExpr->pRight);
  }
  return nCost;
}

static void fts3ExprAssignCosts(
  Fts3Expr *pExpr,                /* Expression to create seg-readers for */
  ExprAndCost **ppExprCost        /* OUT: Write to *ppExprCost */
){
  if( pExpr->eType==FTSQUERY_AND ){
    fts3ExprAssignCosts(pExpr->pLeft, ppExprCost);
    fts3ExprAssignCosts(pExpr->pRight, ppExprCost);
  }else{
    (*ppExprCost)->pExpr = pExpr;
    (*ppExprCost)->nCost = fts3ExprCost(pExpr);;
    (*ppExprCost)++;
  }
}

static int fts3ExprAllocateSegReaders(
  Fts3Cursor *pCsr,               /* FTS3 table */
  Fts3Expr *pExpr,                /* Expression to create seg-readers for */
  int *pnExpr                     /* OUT: Number of AND'd expressions */
){
  int rc = SQLITE_OK;             /* Return code */

  if( pCsr->doDeferred ) return SQLITE_OK;
  if( pnExpr && pExpr->eType!=FTSQUERY_AND ){
    (*pnExpr)++;
    pnExpr = 0;
  }

  if( pExpr->eType==FTSQUERY_PHRASE ){
    Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
    Fts3Phrase *pPhrase = pExpr->pPhrase;
    int ii;

    for(ii=0; rc==SQLITE_OK && ii<pPhrase->nToken; ii++){
      Fts3PhraseToken *pTok = &pPhrase->aToken[ii];
      if( pTok->pArray==0 ){
        rc = fts3TermSegReaderArray(
            pCsr, pTok->z, pTok->n, pTok->isPrefix, &pTok->pArray
        );
      }
    }
  }else{ 
    rc = fts3ExprAllocateSegReaders(pCsr, pExpr->pLeft, pnExpr);
    if( rc==SQLITE_OK ){
      rc = fts3ExprAllocateSegReaders(pCsr, pExpr->pRight, pnExpr);
    }
  }
  return rc;
}

static void fts3ExprFreeSegReaders(Fts3Expr *pExpr){
  if( pExpr ){
    Fts3Phrase *pPhrase = pExpr->pPhrase;
    if( pPhrase ){
      int kk;
      for(kk=0; kk<pPhrase->nToken; kk++){
        fts3SegReaderArrayFree(pPhrase->aToken[kk].pArray);
        pPhrase->aToken[kk].pArray = 0;
      }
    }
    fts3ExprFreeSegReaders(pExpr->pLeft);
    fts3ExprFreeSegReaders(pExpr->pRight);
  }
}

/*
** Evaluate the full-text expression pExpr against fts3 table pTab. Store
** the resulting doclist in *paOut and *pnOut.  This routine mallocs for
** the space needed to store the output.  The caller is responsible for
** freeing the space when it has finished.
*/
static int fts3EvalExpr(
  Fts3Cursor *p,                  /* Virtual table cursor handle */
  Fts3Expr *pExpr,                /* Parsed fts3 expression */
  char **paOut,                   /* OUT: Pointer to malloc'd result buffer */
  int *pnOut,                     /* OUT: Size of buffer at *paOut */
  int isReqPos                    /* Require positions in output buffer */
){
  int rc = SQLITE_OK;             /* Return code */

  /* Zero the output parameters. */
  *paOut = 0;
  *pnOut = 0;

  if( pExpr ){
    assert( pExpr->eType==FTSQUERY_NEAR   || pExpr->eType==FTSQUERY_OR     
         || pExpr->eType==FTSQUERY_AND    || pExpr->eType==FTSQUERY_NOT
         || pExpr->eType==FTSQUERY_PHRASE
    );
    assert( pExpr->eType==FTSQUERY_PHRASE 
         || pExpr->eType==FTSQUERY_NEAR 
         || isReqPos==0
    );

    if( pExpr->eType==FTSQUERY_PHRASE ){
      rc = fts3PhraseSelect(p, pExpr->pPhrase,
          isReqPos || (pExpr->pParent && pExpr->pParent->eType==FTSQUERY_NEAR),
          paOut, pnOut
      );
      fts3ExprFreeSegReaders(pExpr);
    }else if( p->doDeferred==0 && pExpr->eType==FTSQUERY_AND ){
      ExprAndCost *aExpr = 0;     /* Array of AND'd expressions and costs */
      int nExpr = 0;              /* Size of aExpr[] */
      char *aRet = 0;             /* Doclist to return to caller */
      int nRet = 0;               /* Length of aRet[] in bytes */
      int nDoc = 0x7FFFFFFF;

      assert( !isReqPos );

      rc = fts3ExprAllocateSegReaders(p, pExpr, &nExpr);
      if( rc==SQLITE_OK ){
        aExpr = sqlite3_malloc(sizeof(ExprAndCost) * nExpr);
        if( !aExpr ) rc = SQLITE_NOMEM;
      }
      if( rc==SQLITE_OK ){
        int ii;                   /* Used to iterate through expressions */

        fts3ExprAssignCosts(pExpr, &aExpr);
        aExpr -= nExpr;
        for(ii=0; ii<nExpr; ii++){
          char *aNew;
          int nNew;
          int jj;
          ExprAndCost *pBest = 0;
  
          for(jj=0; jj<nExpr; jj++){
            ExprAndCost *pCand = &aExpr[jj];
            if( pCand->pExpr && (pBest==0 || pCand->nCost<pBest->nCost) ){
              pBest = pCand;
            }
          }
  
          if( pBest->nCost>nDoc ){
            rc = fts3DeferExpression(p, p->pExpr);
            break;
          }else{
            rc = fts3EvalExpr(p, pBest->pExpr, &aNew, &nNew, 0);
            if( rc!=SQLITE_OK ) break;
            pBest->pExpr = 0;
            if( ii==0 ){
              aRet = aNew;
              nRet = nNew;
            }else{
              fts3DoclistMerge(
                  MERGE_AND, 0, 0, aRet, &nRet, aRet, nRet, aNew, nNew
              );
              sqlite3_free(aNew);
            }
            nDoc = fts3DoclistCountDocids(0, aRet, nRet);
          }
        }
      }

      *paOut = aRet;
      *pnOut = nRet;
      sqlite3_free(aExpr);
      fts3ExprFreeSegReaders(pExpr);

    }else{
      char *aLeft;
      char *aRight;
      int nLeft;
      int nRight;

      assert( pExpr->eType==FTSQUERY_NEAR 
           || pExpr->eType==FTSQUERY_OR
           || pExpr->eType==FTSQUERY_NOT
           || (pExpr->eType==FTSQUERY_AND && p->doDeferred)
      );

      if( 0==(rc = fts3EvalExpr(p, pExpr->pRight, &aRight, &nRight, isReqPos))
       && 0==(rc = fts3EvalExpr(p, pExpr->pLeft, &aLeft, &nLeft, isReqPos))
      ){



        switch( pExpr->eType ){
          case FTSQUERY_NEAR: {
            Fts3Expr *pLeft;
            Fts3Expr *pRight;
            int mergetype = isReqPos ? MERGE_POS_NEAR : MERGE_NEAR;
           
            if( pExpr->pParent && pExpr->pParent->eType==FTSQUERY_NEAR ){
................................................................................
      }
      sqlite3_free(aRight);
    }
  }

  return rc;
}

/*
**
*/
static int fts3EvalDeferred(Fts3Cursor *pCsr, int *pbRes){
  int rc = SQLITE_OK;
  if( pCsr->pDeferred==0 ){
    *pbRes = 1;
  }else{
    rc = fts3CursorSeek(0, pCsr);
    if( rc==SQLITE_OK ){
      sqlite3Fts3FreeDeferredDoclists(pCsr);
      rc = sqlite3Fts3CacheDeferredDoclists(pCsr);
    }
    if( rc==SQLITE_OK ){
      char *a = 0;
      int n = 0;
      pCsr->doDeferred = 1;
      rc = fts3EvalExpr(pCsr, pCsr->pExpr, &a, &n, 0);
      pCsr->doDeferred = 0;
      assert( n>=0 );
      *pbRes = (n>0);
      sqlite3_free(a);
    }
  }
  return rc;
}

/*
** Advance the cursor to the next row in the %_content table that
** matches the search criteria.  For a MATCH search, this will be
** the next row that matches. For a full-table scan, this will be
** simply the next row in the %_content table.  For a docid lookup,
** this routine simply sets the EOF flag.
**
** Return SQLITE_OK if nothing goes wrong.  SQLITE_OK is returned
** even if we reach end-of-file.  The fts3EofMethod() will be called
** subsequently to determine whether or not an EOF was hit.
*/
static int fts3NextMethod(sqlite3_vtab_cursor *pCursor){
  int res;
  int rc = SQLITE_OK;             /* Return code */
  Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;

  do {
    if( pCsr->aDoclist==0 ){
      if( SQLITE_ROW!=sqlite3_step(pCsr->pStmt) ){
        pCsr->isEof = 1;
        rc = sqlite3_reset(pCsr->pStmt);
        break;
      }
      pCsr->iPrevId = sqlite3_column_int64(pCsr->pStmt, 0);
    }else{
      if( pCsr->pNextId>=&pCsr->aDoclist[pCsr->nDoclist] ){
        pCsr->isEof = 1;
        break;
      }
      sqlite3_reset(pCsr->pStmt);
      fts3GetDeltaVarint(&pCsr->pNextId, &pCsr->iPrevId);
      pCsr->isRequireSeek = 1;
      pCsr->isMatchinfoNeeded = 1;
    }
  }while( SQLITE_OK==(rc = fts3EvalDeferred(pCsr, &res)) && res==0 );

  return rc;
}


/*
** This is the xFilter interface for the virtual table.  See
** the virtual table xFilter method documentation for additional
** information.
**
** If idxNum==FTS3_FULLSCAN_SEARCH then do a full table scan against
................................................................................

  /* In case the cursor has been used before, clear it now. */
  sqlite3_finalize(pCsr->pStmt);
  sqlite3_free(pCsr->aDoclist);
  sqlite3Fts3ExprFree(pCsr->pExpr);
  memset(&pCursor[1], 0, sizeof(Fts3Cursor)-sizeof(sqlite3_vtab_cursor));
















  if( idxNum!=FTS3_DOCID_SEARCH && idxNum!=FTS3_FULLSCAN_SEARCH ){


    int iCol = idxNum-FTS3_FULLTEXT_SEARCH;
    const char *zQuery = (const char *)sqlite3_value_text(apVal[0]);

    if( zQuery==0 && sqlite3_value_type(apVal[0])!=SQLITE_NULL ){
      return SQLITE_NOMEM;
    }

................................................................................
      }
      return rc;
    }

    rc = sqlite3Fts3ReadLock(p);
    if( rc!=SQLITE_OK ) return rc;

    rc = fts3EvalExpr(pCsr, pCsr->pExpr, &pCsr->aDoclist, &pCsr->nDoclist, 0);
    if( rc!=SQLITE_OK ) return rc;
    pCsr->pNextId = pCsr->aDoclist;
    pCsr->iPrevId = 0;
    if( pCsr->nDoclist<0 ){
      assert( pCsr->aDoclist==0 );
      idxNum = FTS3_FULLSCAN_SEARCH;
    }
  }

  /* Compile a SELECT statement for this cursor. For a full-table-scan, the
  ** statement loops through all rows of the %_content table. For a
  ** full-text query or docid lookup, the statement retrieves a single
  ** row by docid.
  */
  zSql = sqlite3_mprintf(azSql[idxNum==FTS3_FULLSCAN_SEARCH], p->zDb, p->zName);
  if( !zSql ){
    rc = SQLITE_NOMEM;
  }else{
    rc = sqlite3_prepare_v2(p->db, zSql, -1, &pCsr->pStmt, 0);
    sqlite3_free(zSql);
  }
  if( rc==SQLITE_OK && idxNum==FTS3_DOCID_SEARCH ){
    rc = sqlite3_bind_value(pCsr->pStmt, 1, apVal[0]);
  }
  pCsr->eSearch = (i16)idxNum;

  if( rc!=SQLITE_OK ) return rc;
  return fts3NextMethod(pCursor);
}

/* 
** This is the xEof method of the virtual table. SQLite calls this 
................................................................................

/*
** Load the doclist associated with expression pExpr to pExpr->aDoclist.
** The loaded doclist contains positions as well as the document ids.
** This is used by the matchinfo(), snippet() and offsets() auxillary
** functions.
*/
int sqlite3Fts3ExprLoadDoclist(Fts3Cursor *pCsr, Fts3Expr *pExpr){
  int rc;
  pCsr->doDeferred = 1;
  rc = fts3EvalExpr(pCsr, pExpr, &pExpr->aDoclist, &pExpr->nDoclist, 1);
  pCsr->doDeferred = 0;
  return rc;
}

/*
** After ExprLoadDoclist() (see above) has been called, this function is
** used to iterate/search through the position lists that make up the doclist
** stored in pExpr->aDoclist.
*/

Changes to ext/fts3/fts3Int.h.

92
93
94
95
96
97
98




99
100
101
102
103
104
105
106
107
...
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
...
156
157
158
159
160
161
162

163
164
165
166
167
168



169
170
171
172
173
174
175
...
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
...
220
221
222
223
224
225
226


227
228
229
230
231
232
233
...
271
272
273
274
275
276
277






278
279
280
281
282
283
284
...
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
#define UNUSED_PARAMETER(x) (void)(x)
#endif

typedef struct Fts3Table Fts3Table;
typedef struct Fts3Cursor Fts3Cursor;
typedef struct Fts3Expr Fts3Expr;
typedef struct Fts3Phrase Fts3Phrase;




typedef struct Fts3SegReader Fts3SegReader;
typedef struct Fts3SegFilter Fts3SegFilter;

/*
** A connection to a fulltext index is an instance of the following
** structure. The xCreate and xConnect methods create an instance
** of this structure and xDestroy and xDisconnect free that instance.
** All other methods receive a pointer to the structure as one of their
** arguments.
................................................................................
  sqlite3_tokenizer *pTokenizer;  /* tokenizer for inserts and queries */

  /* Precompiled statements used by the implementation. Each of these 
  ** statements is run and reset within a single virtual table API call. 
  */
  sqlite3_stmt *aStmt[25];

  /* Pointer to string containing the SQL:
  **
  ** "SELECT block FROM %_segments WHERE blockid BETWEEN ? AND ? 
  **    ORDER BY blockid"
  */
  char *zSelectLeaves;
  int nLeavesStmt;                /* Valid statements in aLeavesStmt */
  int nLeavesTotal;               /* Total number of prepared leaves stmts */
  int nLeavesAlloc;               /* Allocated size of aLeavesStmt */
  sqlite3_stmt **aLeavesStmt;     /* Array of prepared zSelectLeaves stmts */

  int nNodeSize;                  /* Soft limit for node size */
  u8 bHasContent;                 /* True if %_content table exists */
  u8 bHasDocsize;                 /* True if %_docsize table exists */

  /* The following hash table is used to buffer pending index updates during
  ** transactions. Variable nPendingData estimates the memory size of the 
  ** pending data, including hash table overhead, but not malloc overhead. 
................................................................................
struct Fts3Cursor {
  sqlite3_vtab_cursor base;       /* Base class used by SQLite core */
  i16 eSearch;                    /* Search strategy (see below) */
  u8 isEof;                       /* True if at End Of Results */
  u8 isRequireSeek;               /* True if must seek pStmt to %_content row */
  sqlite3_stmt *pStmt;            /* Prepared statement in use by the cursor */
  Fts3Expr *pExpr;                /* Parsed MATCH query string */

  sqlite3_int64 iPrevId;          /* Previous id read from aDoclist */
  char *pNextId;                  /* Pointer into the body of aDoclist */
  char *aDoclist;                 /* List of docids for full-text queries */
  int nDoclist;                   /* Size of buffer at aDoclist */
  int isMatchinfoNeeded;          /* True when aMatchinfo[] needs filling in */
  u32 *aMatchinfo;                /* Information about most recent match */



};

/*
** The Fts3Cursor.eSearch member is always set to one of the following.
** Actualy, Fts3Cursor.eSearch can be greater than or equal to
** FTS3_FULLTEXT_SEARCH.  If so, then Fts3Cursor.eSearch - 2 is the index
** of the column to be searched.  For example, in
................................................................................
#define FTS3_FULLSCAN_SEARCH 0    /* Linear scan of %_content table */
#define FTS3_DOCID_SEARCH    1    /* Lookup by rowid on %_content table */
#define FTS3_FULLTEXT_SEARCH 2    /* Full-text index search */

/*
** A "phrase" is a sequence of one or more tokens that must match in
** sequence.  A single token is the base case and the most common case.
** For a sequence of tokens contained in "...", nToken will be the number
** of tokens in the string.
*/









struct Fts3Phrase {
  int nToken;                /* Number of tokens in the phrase */
  int iColumn;               /* Index of column this phrase must match */
  int isNot;                 /* Phrase prefixed by unary not (-) operator */
  struct PhraseToken {
    char *z;                 /* Text of the token */
    int n;                   /* Number of bytes in buffer pointed to by z */
    int isPrefix;            /* True if token ends in with a "*" character */
  } aToken[1];               /* One entry for each token in the phrase */
};

/*
** A tree of these objects forms the RHS of a MATCH operator.
**
** If Fts3Expr.eType is either FTSQUERY_NEAR or FTSQUERY_PHRASE and isLoaded
** is true, then aDoclist points to a malloced buffer, size nDoclist bytes, 
................................................................................
struct Fts3Expr {
  int eType;                 /* One of the FTSQUERY_XXX values defined below */
  int nNear;                 /* Valid if eType==FTSQUERY_NEAR */
  Fts3Expr *pParent;         /* pParent->pLeft==this or pParent->pRight==this */
  Fts3Expr *pLeft;           /* Left operand */
  Fts3Expr *pRight;          /* Right operand */
  Fts3Phrase *pPhrase;       /* Valid if eType==FTSQUERY_PHRASE */



  int isLoaded;              /* True if aDoclist/nDoclist are initialized. */
  char *aDoclist;            /* Buffer containing doclist */
  int nDoclist;              /* Size of aDoclist in bytes */

  sqlite3_int64 iCurrent;
  char *pCurrent;
................................................................................
);
int sqlite3Fts3ReadBlock(Fts3Table*, sqlite3_int64, char const**, int*);
int sqlite3Fts3AllSegdirs(Fts3Table*, sqlite3_stmt **);
int sqlite3Fts3MatchinfoDocsizeLocal(Fts3Cursor*, u32*);
int sqlite3Fts3MatchinfoDocsizeGlobal(Fts3Cursor*, u32*);
int sqlite3Fts3ReadLock(Fts3Table *);







/* Flags allowed as part of the 4th argument to SegmentReaderIterate() */
#define FTS3_SEGMENT_REQUIRE_POS   0x00000001
#define FTS3_SEGMENT_IGNORE_EMPTY  0x00000002
#define FTS3_SEGMENT_COLUMN_FILTER 0x00000004
#define FTS3_SEGMENT_PREFIX        0x00000008

/* Type passed as 4th argument to SegmentReaderIterate() */
................................................................................
int sqlite3Fts3PutVarint(char *, sqlite3_int64);
int sqlite3Fts3GetVarint(const char *, sqlite_int64 *);
int sqlite3Fts3GetVarint32(const char *, int *);
int sqlite3Fts3VarintLen(sqlite3_uint64);
void sqlite3Fts3Dequote(char *);

char *sqlite3Fts3FindPositions(Fts3Expr *, sqlite3_int64, int);
int sqlite3Fts3ExprLoadDoclist(Fts3Table *, Fts3Expr *);
int sqlite3Fts3ExprNearTrim(Fts3Expr *, Fts3Expr *, int);

/* fts3_tokenizer.c */
const char *sqlite3Fts3NextToken(const char *, int *);
int sqlite3Fts3InitHashTable(sqlite3 *, Fts3Hash *, const char *);
int sqlite3Fts3InitTokenizer(Fts3Hash *pHash, 
  const char *, sqlite3_tokenizer **, const char **, char **







>
>
>
>

|







 







|
|
<
<
<
<
<
<
<
<
<







 







>






>
>
>







 







|
|

>
>
>
>
>
>
>
>
>




<
<
<
<
|







 







>
>







 







>
>
>
>
>
>







 







|







92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
...
120
121
122
123
124
125
126
127
128









129
130
131
132
133
134
135
...
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
...
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
...
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
...
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
...
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
#define UNUSED_PARAMETER(x) (void)(x)
#endif

typedef struct Fts3Table Fts3Table;
typedef struct Fts3Cursor Fts3Cursor;
typedef struct Fts3Expr Fts3Expr;
typedef struct Fts3Phrase Fts3Phrase;
typedef struct Fts3PhraseToken Fts3PhraseToken;

typedef struct Fts3SegFilter Fts3SegFilter;
typedef struct Fts3DeferredToken Fts3DeferredToken;
typedef struct Fts3SegReader Fts3SegReader;
typedef struct Fts3SegReaderArray Fts3SegReaderArray;

/*
** A connection to a fulltext index is an instance of the following
** structure. The xCreate and xConnect methods create an instance
** of this structure and xDestroy and xDisconnect free that instance.
** All other methods receive a pointer to the structure as one of their
** arguments.
................................................................................
  sqlite3_tokenizer *pTokenizer;  /* tokenizer for inserts and queries */

  /* Precompiled statements used by the implementation. Each of these 
  ** statements is run and reset within a single virtual table API call. 
  */
  sqlite3_stmt *aStmt[25];

  char *zSegmentsTbl;             /* Name of %_segments table */
  int nPgsz;                      /* Page size for host database */









  int nNodeSize;                  /* Soft limit for node size */
  u8 bHasContent;                 /* True if %_content table exists */
  u8 bHasDocsize;                 /* True if %_docsize table exists */

  /* The following hash table is used to buffer pending index updates during
  ** transactions. Variable nPendingData estimates the memory size of the 
  ** pending data, including hash table overhead, but not malloc overhead. 
................................................................................
struct Fts3Cursor {
  sqlite3_vtab_cursor base;       /* Base class used by SQLite core */
  i16 eSearch;                    /* Search strategy (see below) */
  u8 isEof;                       /* True if at End Of Results */
  u8 isRequireSeek;               /* True if must seek pStmt to %_content row */
  sqlite3_stmt *pStmt;            /* Prepared statement in use by the cursor */
  Fts3Expr *pExpr;                /* Parsed MATCH query string */
  Fts3DeferredToken *pDeferred;   /* Deferred search tokens, if any */
  sqlite3_int64 iPrevId;          /* Previous id read from aDoclist */
  char *pNextId;                  /* Pointer into the body of aDoclist */
  char *aDoclist;                 /* List of docids for full-text queries */
  int nDoclist;                   /* Size of buffer at aDoclist */
  int isMatchinfoNeeded;          /* True when aMatchinfo[] needs filling in */
  u32 *aMatchinfo;                /* Information about most recent match */

  int doDeferred;
  int nRowAvg;                    /* Average size of database rows, in pages */
};

/*
** The Fts3Cursor.eSearch member is always set to one of the following.
** Actualy, Fts3Cursor.eSearch can be greater than or equal to
** FTS3_FULLTEXT_SEARCH.  If so, then Fts3Cursor.eSearch - 2 is the index
** of the column to be searched.  For example, in
................................................................................
#define FTS3_FULLSCAN_SEARCH 0    /* Linear scan of %_content table */
#define FTS3_DOCID_SEARCH    1    /* Lookup by rowid on %_content table */
#define FTS3_FULLTEXT_SEARCH 2    /* Full-text index search */

/*
** A "phrase" is a sequence of one or more tokens that must match in
** sequence.  A single token is the base case and the most common case.
** For a sequence of tokens contained in double-quotes (i.e. "one two three")
** nToken will be the number of tokens in the string.
*/

struct Fts3PhraseToken {
  char *z;                        /* Text of the token */
  int n;                          /* Number of bytes in buffer z */
  int isPrefix;                   /* True if token ends with a "*" character */
  Fts3SegReaderArray *pArray;
  Fts3DeferredToken *pDeferred;
};

struct Fts3Phrase {
  int nToken;                /* Number of tokens in the phrase */
  int iColumn;               /* Index of column this phrase must match */
  int isNot;                 /* Phrase prefixed by unary not (-) operator */




  Fts3PhraseToken aToken[1]; /* One entry for each token in the phrase */
};

/*
** A tree of these objects forms the RHS of a MATCH operator.
**
** If Fts3Expr.eType is either FTSQUERY_NEAR or FTSQUERY_PHRASE and isLoaded
** is true, then aDoclist points to a malloced buffer, size nDoclist bytes, 
................................................................................
struct Fts3Expr {
  int eType;                 /* One of the FTSQUERY_XXX values defined below */
  int nNear;                 /* Valid if eType==FTSQUERY_NEAR */
  Fts3Expr *pParent;         /* pParent->pLeft==this or pParent->pRight==this */
  Fts3Expr *pLeft;           /* Left operand */
  Fts3Expr *pRight;          /* Right operand */
  Fts3Phrase *pPhrase;       /* Valid if eType==FTSQUERY_PHRASE */

  int bDeferred;

  int isLoaded;              /* True if aDoclist/nDoclist are initialized. */
  char *aDoclist;            /* Buffer containing doclist */
  int nDoclist;              /* Size of aDoclist in bytes */

  sqlite3_int64 iCurrent;
  char *pCurrent;
................................................................................
);
int sqlite3Fts3ReadBlock(Fts3Table*, sqlite3_int64, char const**, int*);
int sqlite3Fts3AllSegdirs(Fts3Table*, sqlite3_stmt **);
int sqlite3Fts3MatchinfoDocsizeLocal(Fts3Cursor*, u32*);
int sqlite3Fts3MatchinfoDocsizeGlobal(Fts3Cursor*, u32*);
int sqlite3Fts3ReadLock(Fts3Table *);

void sqlite3Fts3FreeDeferredTokens(Fts3Cursor *);
int sqlite3Fts3DeferToken(Fts3Cursor *, Fts3PhraseToken *, int);
int sqlite3Fts3CacheDeferredDoclists(Fts3Cursor *);
void sqlite3Fts3FreeDeferredDoclists(Fts3Cursor *);
char *sqlite3Fts3DeferredDoclist(Fts3DeferredToken *, int *);

/* Flags allowed as part of the 4th argument to SegmentReaderIterate() */
#define FTS3_SEGMENT_REQUIRE_POS   0x00000001
#define FTS3_SEGMENT_IGNORE_EMPTY  0x00000002
#define FTS3_SEGMENT_COLUMN_FILTER 0x00000004
#define FTS3_SEGMENT_PREFIX        0x00000008

/* Type passed as 4th argument to SegmentReaderIterate() */
................................................................................
int sqlite3Fts3PutVarint(char *, sqlite3_int64);
int sqlite3Fts3GetVarint(const char *, sqlite_int64 *);
int sqlite3Fts3GetVarint32(const char *, int *);
int sqlite3Fts3VarintLen(sqlite3_uint64);
void sqlite3Fts3Dequote(char *);

char *sqlite3Fts3FindPositions(Fts3Expr *, sqlite3_int64, int);
int sqlite3Fts3ExprLoadDoclist(Fts3Cursor *, Fts3Expr *);
int sqlite3Fts3ExprNearTrim(Fts3Expr *, Fts3Expr *, int);

/* fts3_tokenizer.c */
const char *sqlite3Fts3NextToken(const char *, int *);
int sqlite3Fts3InitHashTable(sqlite3 *, Fts3Hash *, const char *);
int sqlite3Fts3InitTokenizer(Fts3Hash *pHash, 
  const char *, sqlite3_tokenizer **, const char **, char **

Changes to ext/fts3/fts3_expr.c.

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
...
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
    pCursor->pTokenizer = pTokenizer;
    for(ii=0; rc==SQLITE_OK; ii++){
      const char *zToken;
      int nToken, iBegin, iEnd, iPos;
      rc = pModule->xNext(pCursor, &zToken, &nToken, &iBegin, &iEnd, &iPos);
      if( rc==SQLITE_OK ){
        int nByte = sizeof(Fts3Expr) + sizeof(Fts3Phrase);
        p = fts3ReallocOrFree(p, nByte+ii*sizeof(struct PhraseToken));
        zTemp = fts3ReallocOrFree(zTemp, nTemp + nToken);
        if( !p || !zTemp ){
          goto no_mem;
        }
        if( ii==0 ){
          memset(p, 0, nByte);
          p->pPhrase = (Fts3Phrase *)&p[1];
        }
        p->pPhrase = (Fts3Phrase *)&p[1];
        p->pPhrase->nToken = ii+1;
        p->pPhrase->aToken[ii].n = nToken;


        memcpy(&zTemp[nTemp], zToken, nToken);
        nTemp += nToken;
        if( iEnd<nInput && zInput[iEnd]=='*' ){
          p->pPhrase->aToken[ii].isPrefix = 1;
        }else{
          p->pPhrase->aToken[ii].isPrefix = 0;
        }
................................................................................
  }

  if( rc==SQLITE_DONE ){
    int jj;
    char *zNew = NULL;
    int nNew = 0;
    int nByte = sizeof(Fts3Expr) + sizeof(Fts3Phrase);
    nByte += (p?(p->pPhrase->nToken-1):0) * sizeof(struct PhraseToken);
    p = fts3ReallocOrFree(p, nByte + nTemp);
    if( !p ){
      goto no_mem;
    }
    if( zTemp ){
      zNew = &(((char *)p)[nByte]);
      memcpy(zNew, zTemp, nTemp);







|











>
>







 







|







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
...
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
    pCursor->pTokenizer = pTokenizer;
    for(ii=0; rc==SQLITE_OK; ii++){
      const char *zToken;
      int nToken, iBegin, iEnd, iPos;
      rc = pModule->xNext(pCursor, &zToken, &nToken, &iBegin, &iEnd, &iPos);
      if( rc==SQLITE_OK ){
        int nByte = sizeof(Fts3Expr) + sizeof(Fts3Phrase);
        p = fts3ReallocOrFree(p, nByte+ii*sizeof(Fts3PhraseToken));
        zTemp = fts3ReallocOrFree(zTemp, nTemp + nToken);
        if( !p || !zTemp ){
          goto no_mem;
        }
        if( ii==0 ){
          memset(p, 0, nByte);
          p->pPhrase = (Fts3Phrase *)&p[1];
        }
        p->pPhrase = (Fts3Phrase *)&p[1];
        p->pPhrase->nToken = ii+1;
        p->pPhrase->aToken[ii].n = nToken;
        p->pPhrase->aToken[ii].pDeferred = 0;
        p->pPhrase->aToken[ii].pArray = 0;
        memcpy(&zTemp[nTemp], zToken, nToken);
        nTemp += nToken;
        if( iEnd<nInput && zInput[iEnd]=='*' ){
          p->pPhrase->aToken[ii].isPrefix = 1;
        }else{
          p->pPhrase->aToken[ii].isPrefix = 0;
        }
................................................................................
  }

  if( rc==SQLITE_DONE ){
    int jj;
    char *zNew = NULL;
    int nNew = 0;
    int nByte = sizeof(Fts3Expr) + sizeof(Fts3Phrase);
    nByte += (p?(p->pPhrase->nToken-1):0) * sizeof(Fts3PhraseToken);
    p = fts3ReallocOrFree(p, nByte + nTemp);
    if( !p ){
      goto no_mem;
    }
    if( zTemp ){
      zNew = &(((char *)p)[nByte]);
      memcpy(zNew, zTemp, nTemp);

Changes to ext/fts3/fts3_snippet.c.

20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
...
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
...
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271

/*
** Used as an fts3ExprIterate() context when loading phrase doclists to
** Fts3Expr.aDoclist[]/nDoclist.
*/
typedef struct LoadDoclistCtx LoadDoclistCtx;
struct LoadDoclistCtx {
  Fts3Table *pTab;                /* FTS3 Table */
  int nPhrase;                    /* Number of phrases seen so far */
  int nToken;                     /* Number of tokens seen so far */
};

/*
** The following types are used as part of the implementation of the 
** fts3BestSnippet() routine.
................................................................................

  UNUSED_PARAMETER(iPhrase);

  p->nPhrase++;
  p->nToken += pExpr->pPhrase->nToken;

  if( pExpr->isLoaded==0 ){
    rc = sqlite3Fts3ExprLoadDoclist(p->pTab, pExpr);
    pExpr->isLoaded = 1;
    if( rc==SQLITE_OK ){
      rc = fts3ExprNearTrim(pExpr);
    }
  }

  return rc;
................................................................................
static int fts3ExprLoadDoclists(
  Fts3Cursor *pCsr,               /* Fts3 cursor for current query */
  int *pnPhrase,                  /* OUT: Number of phrases in query */
  int *pnToken                    /* OUT: Number of tokens in query */
){
  int rc;                         /* Return Code */
  LoadDoclistCtx sCtx = {0,0,0};  /* Context for fts3ExprIterate() */
  sCtx.pTab = (Fts3Table *)pCsr->base.pVtab;
  rc = fts3ExprIterate(pCsr->pExpr, fts3ExprLoadDoclistsCb1, (void *)&sCtx);
  if( rc==SQLITE_OK ){
    (void)fts3ExprIterate(pCsr->pExpr, fts3ExprLoadDoclistsCb2, 0);
  }
  if( pnPhrase ) *pnPhrase = sCtx.nPhrase;
  if( pnToken ) *pnToken = sCtx.nToken;
  return rc;







|







 







|







 







|







20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
...
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
...
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271

/*
** Used as an fts3ExprIterate() context when loading phrase doclists to
** Fts3Expr.aDoclist[]/nDoclist.
*/
typedef struct LoadDoclistCtx LoadDoclistCtx;
struct LoadDoclistCtx {
  Fts3Cursor *pCsr;               /* FTS3 Cursor */
  int nPhrase;                    /* Number of phrases seen so far */
  int nToken;                     /* Number of tokens seen so far */
};

/*
** The following types are used as part of the implementation of the 
** fts3BestSnippet() routine.
................................................................................

  UNUSED_PARAMETER(iPhrase);

  p->nPhrase++;
  p->nToken += pExpr->pPhrase->nToken;

  if( pExpr->isLoaded==0 ){
    rc = sqlite3Fts3ExprLoadDoclist(p->pCsr, pExpr);
    pExpr->isLoaded = 1;
    if( rc==SQLITE_OK ){
      rc = fts3ExprNearTrim(pExpr);
    }
  }

  return rc;
................................................................................
static int fts3ExprLoadDoclists(
  Fts3Cursor *pCsr,               /* Fts3 cursor for current query */
  int *pnPhrase,                  /* OUT: Number of phrases in query */
  int *pnToken                    /* OUT: Number of tokens in query */
){
  int rc;                         /* Return Code */
  LoadDoclistCtx sCtx = {0,0,0};  /* Context for fts3ExprIterate() */
  sCtx.pCsr = pCsr;
  rc = fts3ExprIterate(pCsr->pExpr, fts3ExprLoadDoclistsCb1, (void *)&sCtx);
  if( rc==SQLITE_OK ){
    (void)fts3ExprIterate(pCsr->pExpr, fts3ExprLoadDoclistsCb2, 0);
  }
  if( pnPhrase ) *pnPhrase = sCtx.nPhrase;
  if( pnToken ) *pnToken = sCtx.nToken;
  return rc;

Changes to ext/fts3/fts3_write.c.

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
..
81
82
83
84
85
86
87

88
89
90
91
92
93
94
...
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
...
781
782
783
784
785
786
787






























788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805

806

807
808
809
810
811
812
813
...
815
816
817
818
819
820
821
822




823




824
825
826
827
828
829
830


831
832











833
834
835
836
837
838
839
...
909
910
911
912
913
914
915
916
917
918
919






920
921
922
923
924
925













926
927





































928
929

930


























931
932


933
934
935

936
937
938
939
940
941
942
...
957
958
959
960
961
962
963

964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
....
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
....
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
....
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
....
2515
2516
2517
2518
2519
2520
2521



















































































































































2522
2523
2524
2525
2526
2527
2528
  char *aData;
  int nSpace;
  sqlite3_int64 iLastDocid;
  sqlite3_int64 iLastCol;
  sqlite3_int64 iLastPos;
};












/*
** An instance of this structure is used to iterate through the terms on
** a contiguous set of segment b-tree leaf nodes. Although the details of
** this structure are only manipulated by code in this file, opaque handles
** of type Fts3SegReader* are also used by code in fts3.c to iterate through
** terms when querying the full-text index. See functions:
**
**   sqlite3Fts3SegReaderNew()
**   sqlite3Fts3SegReaderFree()

**   sqlite3Fts3SegReaderIterate()
**
** Methods used to manipulate Fts3SegReader structures:
**
**   fts3SegReaderNext()
**   fts3SegReaderFirstDocid()
**   fts3SegReaderNextDocid()
*/
struct Fts3SegReader {
  int iIdx;                       /* Index within level, or 0x7FFFFFFF for PT */

  sqlite3_int64 iStartBlock;

  sqlite3_int64 iEndBlock;
  sqlite3_stmt *pStmt;            /* SQL Statement to access leaf nodes */



  char *aNode;                    /* Pointer to node data (or NULL) */
  int nNode;                      /* Size of buffer at aNode (or 0) */
  int nTermAlloc;                 /* Allocated size of zTerm buffer */
  Fts3HashElem **ppNextElem;

  /* Variables set by fts3SegReaderNext(). These may be read directly
  ** by the caller. They are valid from the time SegmentReaderNew() returns
................................................................................

  /* The following variables are used to iterate through the current doclist */
  char *pOffsetList;
  sqlite3_int64 iDocid;
};

#define fts3SegReaderIsPending(p) ((p)->ppNextElem!=0)


/*
** An instance of this structure is used to create a segment b-tree in the
** database. The internal details of this type are only accessed by the
** following functions:
**
**   fts3SegWriterAdd()
................................................................................
** Tokenize the nul-terminated string zText and add all tokens to the
** pending-terms hash-table. The docid used is that currently stored in
** p->iPrevDocid, and the column is specified by argument iCol.
**
** If successful, SQLITE_OK is returned. Otherwise, an SQLite error code.
*/
static int fts3PendingTermsAdd(
  Fts3Table *p,          /* FTS table into which text will be inserted */
  const char *zText,     /* Text of document to be inseted */
  int iCol,              /* Column number into which text is inserted */
  u32 *pnWord            /* OUT: Number of tokens inserted */
){
  int rc;
  int iStart;
  int iEnd;
  int iPos;
  int nWord = 0;

................................................................................
    }else{
      *piIdx = iNext;
    }
  }

  return rc;
}































/*
** Move the iterator passed as the first argument to the next term in the
** segment. If successful, SQLITE_OK is returned. If there is no next term,
** SQLITE_DONE. Otherwise, an SQLite error code.
*/
static int fts3SegReaderNext(Fts3SegReader *pReader){
  char *pNext;                    /* Cursor variable */
  int nPrefix;                    /* Number of bytes in term prefix */
  int nSuffix;                    /* Number of bytes in term suffix */

  if( !pReader->aDoclist ){
    pNext = pReader->aNode;
  }else{
    pNext = &pReader->aDoclist[pReader->nDoclist];
  }

  if( !pNext || pNext>=&pReader->aNode[pReader->nNode] ){

    int rc;

    if( fts3SegReaderIsPending(pReader) ){
      Fts3HashElem *pElem = *(pReader->ppNextElem);
      if( pElem==0 ){
        pReader->aNode = 0;
      }else{
        PendingList *pList = (PendingList *)fts3HashData(pElem);
        pReader->zTerm = (char *)fts3HashKey(pElem);
................................................................................
        pReader->nNode = pReader->nDoclist = pList->nData + 1;
        pReader->aNode = pReader->aDoclist = pList->aData;
        pReader->ppNextElem++;
        assert( pReader->aNode );
      }
      return SQLITE_OK;
    }
    if( !pReader->pStmt ){




      pReader->aNode = 0;




      return SQLITE_OK;
    }
    rc = sqlite3_step(pReader->pStmt);
    if( rc!=SQLITE_ROW ){
      pReader->aNode = 0;
      return (rc==SQLITE_DONE ? SQLITE_OK : rc);
    }


    pReader->nNode = sqlite3_column_bytes(pReader->pStmt, 0);
    pReader->aNode = (char *)sqlite3_column_blob(pReader->pStmt, 0);











    pNext = pReader->aNode;
  }
  
  pNext += sqlite3Fts3GetVarint32(pNext, &nPrefix);
  pNext += sqlite3Fts3GetVarint32(pNext, &nSuffix);

  if( nPrefix+nSuffix>pReader->nTermAlloc ){
................................................................................
    pReader->pOffsetList = 0;
  }else{
    sqlite3_int64 iDelta;
    pReader->pOffsetList = p + sqlite3Fts3GetVarint(p, &iDelta);
    pReader->iDocid += iDelta;
  }
}

/*
** Free all allocations associated with the iterator passed as the 
** second argument.






*/
void sqlite3Fts3SegReaderFree(Fts3Table *p, Fts3SegReader *pReader){
  if( pReader ){
    if( pReader->pStmt ){
      /* Move the leaf-range SELECT statement to the aLeavesStmt[] array,
      ** so that it can be reused when required by another query.













      */
      assert( p->nLeavesStmt<p->nLeavesTotal );





































      sqlite3_reset(pReader->pStmt);
      p->aLeavesStmt[p->nLeavesStmt++] = pReader->pStmt;

    }


























    if( !fts3SegReaderIsPending(pReader) ){
      sqlite3_free(pReader->zTerm);


    }
    sqlite3_free(pReader);
  }

}

/*
** Allocate a new SegReader object.
*/
int sqlite3Fts3SegReaderNew(
  Fts3Table *p,                   /* Virtual table handle */
................................................................................
  }

  pReader = (Fts3SegReader *)sqlite3_malloc(sizeof(Fts3SegReader) + nExtra);
  if( !pReader ){
    return SQLITE_NOMEM;
  }
  memset(pReader, 0, sizeof(Fts3SegReader));

  pReader->iStartBlock = iStartLeaf;
  pReader->iIdx = iAge;
  pReader->iEndBlock = iEndBlock;

  if( nExtra ){
    /* The entire segment is stored in the root node. */
    pReader->aNode = (char *)&pReader[1];
    pReader->nNode = nRoot;
    memcpy(pReader->aNode, zRoot, nRoot);
  }else{
    /* If the text of the SQL statement to iterate through a contiguous
    ** set of entries in the %_segments table has not yet been composed,
    ** compose it now.
    */
    if( !p->zSelectLeaves ){
      p->zSelectLeaves = sqlite3_mprintf(
          "SELECT block FROM %Q.'%q_segments' WHERE blockid BETWEEN ? AND ? "
          "ORDER BY blockid", p->zDb, p->zName
      );
      if( !p->zSelectLeaves ){
        rc = SQLITE_NOMEM;
        goto finished;
      }
    }

    /* If there are no free statements in the aLeavesStmt[] array, prepare
    ** a new statement now. Otherwise, reuse a prepared statement from
    ** aLeavesStmt[].
    */
    if( p->nLeavesStmt==0 ){
      if( p->nLeavesTotal==p->nLeavesAlloc ){
        int nNew = p->nLeavesAlloc + 16;
        sqlite3_stmt **aNew = (sqlite3_stmt **)sqlite3_realloc(
            p->aLeavesStmt, nNew*sizeof(sqlite3_stmt *)
        );
        if( !aNew ){
          rc = SQLITE_NOMEM;
          goto finished;
        }
        p->nLeavesAlloc = nNew;
        p->aLeavesStmt = aNew;
      }
      rc = sqlite3_prepare_v2(p->db, p->zSelectLeaves, -1, &pReader->pStmt, 0);
      if( rc!=SQLITE_OK ){
        goto finished;
      }
      p->nLeavesTotal++;
    }else{
      pReader->pStmt = p->aLeavesStmt[--p->nLeavesStmt];
    }

    /* Bind the start and end leaf blockids to the prepared SQL statement. */
    sqlite3_bind_int64(pReader->pStmt, 1, iStartLeaf);
    sqlite3_bind_int64(pReader->pStmt, 2, iEndLeaf);
  }
  rc = fts3SegReaderNext(pReader);

 finished:
  if( rc==SQLITE_OK ){
    *ppReader = pReader;
  }else{
    sqlite3Fts3SegReaderFree(p, pReader);
  }
................................................................................
    if( !pReader ){
      rc = SQLITE_NOMEM;
    }else{
      memset(pReader, 0, nByte);
      pReader->iIdx = 0x7FFFFFFF;
      pReader->ppNextElem = (Fts3HashElem **)&pReader[1];
      memcpy(pReader->ppNextElem, aElem, nElem*sizeof(Fts3HashElem *));
      fts3SegReaderNext(pReader);
    }
  }

  if( isPrefix ){
    sqlite3_free(aElem);
  }
  *ppReader = pReader;
................................................................................
  */
  if( pFilter->zTerm ){
    int nTerm = pFilter->nTerm;
    const char *zTerm = pFilter->zTerm;
    for(i=0; i<nSegment; i++){
      Fts3SegReader *pSeg = apSegment[i];
      while( fts3SegReaderTermCmp(pSeg, zTerm, nTerm)<0 ){
        rc = fts3SegReaderNext(pSeg);
        if( rc!=SQLITE_OK ) goto finished; }
    }
  }

  fts3SegReaderSort(apSegment, nSegment, nSegment, fts3SegReaderCmp);
  while( apSegment[0]->aNode ){
    int nTerm = apSegment[0]->nTerm;
................................................................................
    ** term (if such a term exists in the index) has already been made.
    */
    if( pFilter->zTerm && !isPrefix ){
      goto finished;
    }

    for(i=0; i<nMerge; i++){
      rc = fts3SegReaderNext(apSegment[i]);
      if( rc!=SQLITE_OK ) goto finished;
    }
    fts3SegReaderSort(apSegment, nSegment, nMerge, fts3SegReaderCmp);
  }

 finished:
  sqlite3_free(aBuffer);
................................................................................
#endif
  }else{
    rc = SQLITE_ERROR;
  }

  return rc;
}




















































































































































/*
** This function does the work for the xUpdate method of FTS3 virtual
** tables.
*/
int sqlite3Fts3UpdateMethod(
  sqlite3_vtab *pVtab,            /* FTS3 vtab object */







>
>
>
>
>
>
>
>
>
>
>









>










>
|
>
|
<
>
>
>







 







>







 







|
|
|
|







 







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






|











>

>







 







<
>
>
>
>
|
>
>
>
>


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







 









|
|
>
>
>
>
>
>

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

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

<

>







 







>

|








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







 







|







 







|







 







|







 







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







38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

80
81
82
83
84
85
86
87
88
89
..
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
...
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
...
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
...
864
865
866
867
868
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
...
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992




993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006

1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044

1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077

1078
1079
1080
1081
1082
1083
1084
1085
1086
....
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119











1120
































1121
1122
1123
1124
1125
1126
1127
1128
....
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
....
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
....
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
....
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
  char *aData;
  int nSpace;
  sqlite3_int64 iLastDocid;
  sqlite3_int64 iLastCol;
  sqlite3_int64 iLastPos;
};


/*
** Each cursor has a (possibly empty) linked list of the following objects.
*/
struct Fts3DeferredToken {
  Fts3PhraseToken *pToken;        /* Pointer to corresponding expr token */
  int iCol;                       /* Column token must occur in */
  Fts3DeferredToken *pNext;       /* Next in list of deferred tokens */
  PendingList *pList;             /* Doclist is assembled here */
};

/*
** An instance of this structure is used to iterate through the terms on
** a contiguous set of segment b-tree leaf nodes. Although the details of
** this structure are only manipulated by code in this file, opaque handles
** of type Fts3SegReader* are also used by code in fts3.c to iterate through
** terms when querying the full-text index. See functions:
**
**   sqlite3Fts3SegReaderNew()
**   sqlite3Fts3SegReaderFree()
**   sqlite3Fts3SegReaderCost()
**   sqlite3Fts3SegReaderIterate()
**
** Methods used to manipulate Fts3SegReader structures:
**
**   fts3SegReaderNext()
**   fts3SegReaderFirstDocid()
**   fts3SegReaderNextDocid()
*/
struct Fts3SegReader {
  int iIdx;                       /* Index within level, or 0x7FFFFFFF for PT */

  sqlite3_int64 iStartBlock;      /* Rowid of first leaf block to traverse */
  sqlite3_int64 iLeafEndBlock;    /* Rowid of final leaf block to traverse */
  sqlite3_int64 iEndBlock;        /* Rowid of final block in segment (or 0) */

  sqlite3_int64 iCurrentBlock;    /* Current leaf block (or 0) */
  sqlite3_blob *pBlob;            /* Blob open on iStartBlock */

  char *aNode;                    /* Pointer to node data (or NULL) */
  int nNode;                      /* Size of buffer at aNode (or 0) */
  int nTermAlloc;                 /* Allocated size of zTerm buffer */
  Fts3HashElem **ppNextElem;

  /* Variables set by fts3SegReaderNext(). These may be read directly
  ** by the caller. They are valid from the time SegmentReaderNew() returns
................................................................................

  /* The following variables are used to iterate through the current doclist */
  char *pOffsetList;
  sqlite3_int64 iDocid;
};

#define fts3SegReaderIsPending(p) ((p)->ppNextElem!=0)
#define fts3SegReaderIsRootOnly(p) ((p)->aNode==(char *)&(p)[1])

/*
** An instance of this structure is used to create a segment b-tree in the
** database. The internal details of this type are only accessed by the
** following functions:
**
**   fts3SegWriterAdd()
................................................................................
** Tokenize the nul-terminated string zText and add all tokens to the
** pending-terms hash-table. The docid used is that currently stored in
** p->iPrevDocid, and the column is specified by argument iCol.
**
** If successful, SQLITE_OK is returned. Otherwise, an SQLite error code.
*/
static int fts3PendingTermsAdd(
  Fts3Table *p,                   /* Table into which text will be inserted */
  const char *zText,              /* Text of document to be inserted */
  int iCol,                       /* Column into which text is being inserted */
  u32 *pnWord                     /* OUT: Number of tokens inserted */
){
  int rc;
  int iStart;
  int iEnd;
  int iPos;
  int nWord = 0;

................................................................................
    }else{
      *piIdx = iNext;
    }
  }

  return rc;
}

/*
** The %_segments table is declared as follows:
**
**   CREATE TABLE %_segments(blockid INTEGER PRIMARY KEY, block BLOB)
**
** This function opens a read-only blob handle on the "block" column of
** row iSegment of the %_segments table associated with FTS3 table p.
**
** If all goes well, SQLITE_OK is returned and *ppBlob set to the 
** read-only blob handle. It is the responsibility of the caller to call
** sqlite3_blob_close() on the blob handle. Or, if an error occurs, an
** SQLite error code is returned and *ppBlob is either not modified or
** set to 0.
*/
static int fts3OpenSegmentsBlob(
  Fts3Table *p,                   /* FTS3 table handle */
  sqlite3_int64 iSegment,         /* Rowid in %_segments table */
  sqlite3_blob **ppBlob           /* OUT: Read-only blob handle */
){
  if( 0==p->zSegmentsTbl
   && 0==(p->zSegmentsTbl = sqlite3_mprintf("%s_segments", p->zName))
  ) {
    return SQLITE_NOMEM;
  }
  return sqlite3_blob_open(
     p->db, p->zDb, p->zSegmentsTbl, "block", iSegment, 0, ppBlob
  );
}


/*
** Move the iterator passed as the first argument to the next term in the
** segment. If successful, SQLITE_OK is returned. If there is no next term,
** SQLITE_DONE. Otherwise, an SQLite error code.
*/
static int fts3SegReaderNext(Fts3Table *p, Fts3SegReader *pReader){
  char *pNext;                    /* Cursor variable */
  int nPrefix;                    /* Number of bytes in term prefix */
  int nSuffix;                    /* Number of bytes in term suffix */

  if( !pReader->aDoclist ){
    pNext = pReader->aNode;
  }else{
    pNext = &pReader->aDoclist[pReader->nDoclist];
  }

  if( !pNext || pNext>=&pReader->aNode[pReader->nNode] ){
    sqlite3_blob *pBlob;
    int rc;

    if( fts3SegReaderIsPending(pReader) ){
      Fts3HashElem *pElem = *(pReader->ppNextElem);
      if( pElem==0 ){
        pReader->aNode = 0;
      }else{
        PendingList *pList = (PendingList *)fts3HashData(pElem);
        pReader->zTerm = (char *)fts3HashKey(pElem);
................................................................................
        pReader->nNode = pReader->nDoclist = pList->nData + 1;
        pReader->aNode = pReader->aDoclist = pList->aData;
        pReader->ppNextElem++;
        assert( pReader->aNode );
      }
      return SQLITE_OK;
    }


    if( !fts3SegReaderIsRootOnly(pReader) ){
      sqlite3_free(pReader->aNode);
    }
    pReader->aNode = 0;

    /* If iCurrentBlock>=iLeafEndBlock, this is an EOF condition. All leaf 
    ** blocks have already been traversed.  */
    if( pReader->iCurrentBlock>=pReader->iLeafEndBlock ){
      return SQLITE_OK;
    }





    rc = fts3OpenSegmentsBlob(p, ++pReader->iCurrentBlock, &pBlob);
    if( rc==SQLITE_OK ){
      pReader->nNode = sqlite3_blob_bytes(pBlob);
      pReader->aNode = (char *)sqlite3_malloc(pReader->nNode);
      if( pReader->aNode ){
        rc = sqlite3_blob_read(pBlob, pReader->aNode, pReader->nNode, 0);
      }else{
        rc = SQLITE_NOMEM;
      }
      sqlite3_blob_close(pBlob);
    }

    if( rc!=SQLITE_OK ){
      return rc;
    }
    pNext = pReader->aNode;
  }
  
  pNext += sqlite3Fts3GetVarint32(pNext, &nPrefix);
  pNext += sqlite3Fts3GetVarint32(pNext, &nSuffix);

  if( nPrefix+nSuffix>pReader->nTermAlloc ){
................................................................................
    pReader->pOffsetList = 0;
  }else{
    sqlite3_int64 iDelta;
    pReader->pOffsetList = p + sqlite3Fts3GetVarint(p, &iDelta);
    pReader->iDocid += iDelta;
  }
}

/*
** This function is called to estimate the amount of data that will be 
** loaded from the disk If SegReaderIterate() is called on this seg-reader,
** in units of average document size.
** 
** This can be used as follows: If the caller has a small doclist that 
** contains references to N documents, and is considering merging it with
** a large doclist (size X "average documents"), it may opt not to load
** the large doclist if X>N.
*/
int sqlite3Fts3SegReaderCost(




  Fts3Cursor *pCsr,               /* FTS3 cursor handle */
  Fts3SegReader *pReader,         /* Segment-reader handle */
  int *pnCost                     /* IN/OUT: Number of bytes read */
){
  Fts3Table *p = (Fts3Table*)pCsr->base.pVtab;
  int rc = SQLITE_OK;             /* Return code */
  int nCost = 0;                  /* Cost in bytes to return */
  sqlite3_int64 iLeaf;            /* Used to iterate through required leaves */
  int pgsz = p->nPgsz;            /* Database page size */

  /* If this seg-reader is reading the pending-terms table, or if all data
  ** for the segment is stored on the root page of the b-tree, then the cost
  ** is zero. In this case all required data is already in main memory.
  */

  if( p->bHasDocsize 
   && !fts3SegReaderIsPending(pReader) 
   && !fts3SegReaderIsRootOnly(pReader) 
  ){
    sqlite3_blob *pBlob = 0;

    if( pCsr->nRowAvg==0 ){
      /* The average document size, which is required to calculate the cost
      ** of each doclist, has not yet been determined. Read the required 
      ** data from the %_stat table to calculate it.
      **
      ** Entry 0 of the %_stat table is a blob containing (nCol+1) FTS3 
      ** varints, where nCol is the number of columns in the FTS3 table.
      ** The first varint is the number of documents currently stored in
      ** the table. The following nCol varints contain the total amount of
      ** data stored in all rows of each column of the table, from left
      ** to right.
      */
      sqlite3_stmt *pStmt;
      rc = fts3SqlStmt(p, SQL_SELECT_DOCTOTAL, &pStmt, 0);
      if( rc ) return rc;
      if( sqlite3_step(pStmt)==SQLITE_ROW ){
        sqlite3_int64 nDoc = 0;
        sqlite3_int64 nByte = 0;
        const char *a = sqlite3_column_blob(pStmt, 0);
        if( a ){
          const char *pEnd = &a[sqlite3_column_bytes(pStmt, 0)];
          a += sqlite3Fts3GetVarint(a, &nDoc);
          while( a<pEnd ){
            sqlite3_int64 nVarint;
            a += sqlite3Fts3GetVarint(a, &nVarint);
            nByte += nVarint;
          }
        }

        pCsr->nRowAvg = (((nByte / nDoc) + pgsz - 1) / pgsz);
      }
      rc = sqlite3_reset(pStmt);

      if( rc!=SQLITE_OK || pCsr->nRowAvg==0 ) return rc;
    }

    rc = fts3OpenSegmentsBlob(p, pReader->iStartBlock, &pBlob);
    if( rc==SQLITE_OK ){
      /* Assume that a blob flows over onto overflow pages if it is larger
      ** than (pgsz-35) bytes in size (the file-format documentation
      ** confirms this).
      */
      int nBlob = sqlite3_blob_bytes(pBlob);
      if( (nBlob+35)>pgsz ){
        int nOvfl = (nBlob + 34)/pgsz;
        nCost += ((nOvfl + pCsr->nRowAvg - 1)/pCsr->nRowAvg);
      }
    }
    assert( rc==SQLITE_OK || pBlob==0 );
    sqlite3_blob_close(pBlob);
  }

  *pnCost += nCost;
  return rc;
}

/*
** Free all allocations associated with the iterator passed as the 
** second argument.
*/
void sqlite3Fts3SegReaderFree(Fts3Table *p, Fts3SegReader *pReader){
  if( pReader && !fts3SegReaderIsPending(pReader) ){
    sqlite3_free(pReader->zTerm);
    if( !fts3SegReaderIsRootOnly(pReader) ){
      sqlite3_free(pReader->aNode);
    }

  }
  sqlite3_free(pReader);
}

/*
** Allocate a new SegReader object.
*/
int sqlite3Fts3SegReaderNew(
  Fts3Table *p,                   /* Virtual table handle */
................................................................................
  }

  pReader = (Fts3SegReader *)sqlite3_malloc(sizeof(Fts3SegReader) + nExtra);
  if( !pReader ){
    return SQLITE_NOMEM;
  }
  memset(pReader, 0, sizeof(Fts3SegReader));
  pReader->iIdx = iAge;
  pReader->iStartBlock = iStartLeaf;
  pReader->iLeafEndBlock = iEndLeaf;
  pReader->iEndBlock = iEndBlock;

  if( nExtra ){
    /* The entire segment is stored in the root node. */
    pReader->aNode = (char *)&pReader[1];
    pReader->nNode = nRoot;
    memcpy(pReader->aNode, zRoot, nRoot);
  }else{
    pReader->iCurrentBlock = iStartLeaf-1;











  }
































  rc = fts3SegReaderNext(p, pReader);

 finished:
  if( rc==SQLITE_OK ){
    *ppReader = pReader;
  }else{
    sqlite3Fts3SegReaderFree(p, pReader);
  }
................................................................................
    if( !pReader ){
      rc = SQLITE_NOMEM;
    }else{
      memset(pReader, 0, nByte);
      pReader->iIdx = 0x7FFFFFFF;
      pReader->ppNextElem = (Fts3HashElem **)&pReader[1];
      memcpy(pReader->ppNextElem, aElem, nElem*sizeof(Fts3HashElem *));
      fts3SegReaderNext(p, pReader);
    }
  }

  if( isPrefix ){
    sqlite3_free(aElem);
  }
  *ppReader = pReader;
................................................................................
  */
  if( pFilter->zTerm ){
    int nTerm = pFilter->nTerm;
    const char *zTerm = pFilter->zTerm;
    for(i=0; i<nSegment; i++){
      Fts3SegReader *pSeg = apSegment[i];
      while( fts3SegReaderTermCmp(pSeg, zTerm, nTerm)<0 ){
        rc = fts3SegReaderNext(p, pSeg);
        if( rc!=SQLITE_OK ) goto finished; }
    }
  }

  fts3SegReaderSort(apSegment, nSegment, nSegment, fts3SegReaderCmp);
  while( apSegment[0]->aNode ){
    int nTerm = apSegment[0]->nTerm;
................................................................................
    ** term (if such a term exists in the index) has already been made.
    */
    if( pFilter->zTerm && !isPrefix ){
      goto finished;
    }

    for(i=0; i<nMerge; i++){
      rc = fts3SegReaderNext(p, apSegment[i]);
      if( rc!=SQLITE_OK ) goto finished;
    }
    fts3SegReaderSort(apSegment, nSegment, nMerge, fts3SegReaderCmp);
  }

 finished:
  sqlite3_free(aBuffer);
................................................................................
#endif
  }else{
    rc = SQLITE_ERROR;
  }

  return rc;
}

/*
** Return the deferred doclist associated with deferred token pDeferred.
** This function assumes that sqlite3Fts3CacheDeferredDoclists() has already
** been called to allocate and populate the doclist.
*/
char *sqlite3Fts3DeferredDoclist(Fts3DeferredToken *pDeferred, int *pnByte){
  if( pDeferred->pList ){
    *pnByte = pDeferred->pList->nData;
    return pDeferred->pList->aData;
  }
  *pnByte = 0;
  return 0;
}

/*
** Helper fucntion for FreeDeferredDoclists(). This function removes all
** references to deferred doclists from within the tree of Fts3Expr 
** structures headed by 
*/
static void fts3DeferredDoclistClear(Fts3Expr *pExpr){
  if( pExpr ){
    fts3DeferredDoclistClear(pExpr->pLeft);
    fts3DeferredDoclistClear(pExpr->pRight);
    if( pExpr->bDeferred && pExpr->isLoaded ){
      sqlite3_free(pExpr->aDoclist);
      pExpr->isLoaded = 0;
      pExpr->aDoclist = 0;
      pExpr->nDoclist = 0;
      pExpr->pCurrent = 0;
      pExpr->iCurrent = 0;
    }
  }
}

/*
** Delete all cached deferred doclists. Deferred doclists are cached
** (allocated) by the sqlite3Fts3CacheDeferredDoclists() function.
*/
void sqlite3Fts3FreeDeferredDoclists(Fts3Cursor *pCsr){
  Fts3DeferredToken *pDef;
  for(pDef=pCsr->pDeferred; pDef; pDef=pDef->pNext){
    sqlite3_free(pDef->pList);
    pDef->pList = 0;
  }
  fts3DeferredDoclistClear(pCsr->pExpr);
}

/*
** Free all entries in the pCsr->pDeffered list. Entries are added to 
** this list using sqlite3Fts3DeferToken().
*/
void sqlite3Fts3FreeDeferredTokens(Fts3Cursor *pCsr){
  Fts3DeferredToken *pDef;
  Fts3DeferredToken *pNext;
  for(pDef=pCsr->pDeferred; pDef; pDef=pNext){
    pNext = pDef->pNext;
    sqlite3_free(pDef->pList);
    sqlite3_free(pDef);
  }
  pCsr->pDeferred = 0;
}

/*
** Generate deferred-doclists for all tokens in the pCsr->pDeferred list
** based on the row that pCsr currently points to.
**
** A deferred-doclist is like any other doclist with position information
** included, except that it only contains entries for a single row of the
** table, not for all rows.
*/
int sqlite3Fts3CacheDeferredDoclists(Fts3Cursor *pCsr){
  int rc = SQLITE_OK;             /* Return code */
  if( pCsr->pDeferred ){
    int i;                        /* Used to iterate through table columns */
    sqlite3_int64 iDocid;         /* Docid of the row pCsr points to */
    Fts3DeferredToken *pDef;      /* Used to iterate through deferred tokens */
  
    Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
    sqlite3_tokenizer *pT = p->pTokenizer;
    sqlite3_tokenizer_module const *pModule = pT->pModule;
   
    assert( pCsr->isRequireSeek==0 );
    iDocid = sqlite3_column_int64(pCsr->pStmt, 0);
  
    for(i=0; i<p->nColumn && rc==SQLITE_OK; i++){
      const char *zText = sqlite3_column_text(pCsr->pStmt, i+1);
      sqlite3_tokenizer_cursor *pTC = 0;
  
      rc = pModule->xOpen(pT, zText, -1, &pTC);
      while( rc==SQLITE_OK ){
        char const *zToken;       /* Buffer containing token */
        int nToken;               /* Number of bytes in token */
        int iDum1, iDum2;         /* Dummy variables */
        int iPos;                 /* Position of token in zText */
  
        pTC->pTokenizer = pT;
        rc = pModule->xNext(pTC, &zToken, &nToken, &iDum1, &iDum2, &iPos);
        for(pDef=pCsr->pDeferred; pDef && rc==SQLITE_OK; pDef=pDef->pNext){
          Fts3PhraseToken *pPT = pDef->pToken;
          if( (pDef->iCol>=p->nColumn || pDef->iCol==i)
           && (pPT->n==nToken || (pPT->isPrefix && pPT->n<nToken))
           && (0==memcmp(zToken, pPT->z, pPT->n))
          ){
            fts3PendingListAppend(&pDef->pList, iDocid, i, iPos, &rc);
          }
        }
      }
      if( pTC ) pModule->xClose(pTC);
      if( rc==SQLITE_DONE ) rc = SQLITE_OK;
    }
  
    for(pDef=pCsr->pDeferred; pDef && rc==SQLITE_OK; pDef=pDef->pNext){
      if( pDef->pList ){
        rc = fts3PendingListAppendVarint(&pDef->pList, 0);
      }
    }
  }

  return rc;
}

/*
** Add an entry for token pToken to the pCsr->pDeferred list.
*/
int sqlite3Fts3DeferToken(
  Fts3Cursor *pCsr,               /* Fts3 table cursor */
  Fts3PhraseToken *pToken,        /* Token to defer */
  int iCol                        /* Column that token must appear in (or -1) */
){
  Fts3DeferredToken *pDeferred;
  pDeferred = sqlite3_malloc(sizeof(*pDeferred));
  if( !pDeferred ){
    return SQLITE_NOMEM;
  }
  memset(pDeferred, 0, sizeof(*pDeferred));
  pDeferred->pToken = pToken;
  pDeferred->pNext = pCsr->pDeferred; 
  pDeferred->iCol = iCol;
  pCsr->pDeferred = pDeferred;

  assert( pToken->pDeferred==0 );
  pToken->pDeferred = pDeferred;

  return SQLITE_OK;
}


/*
** This function does the work for the xUpdate method of FTS3 virtual
** tables.
*/
int sqlite3Fts3UpdateMethod(
  sqlite3_vtab *pVtab,            /* FTS3 vtab object */

Added ext/fts3/fts3speed.tcl.























































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123


#--------------------------------------------------------------------------
# This script contains several sub-programs used to test FTS3/FTS4 
# performance. It does not run the queries directly, but generates SQL
# scripts that can be run using the shell tool.
#
# The following cases are tested:
#
#   1. Inserting documents into an FTS3 table.
#   2. Optimizing an FTS3 table (i.e. "INSERT INTO t1 VALUES('optimize')").
#   3. Deleting documents from an FTS3 table.
#   4. Querying FTS3 tables.
#

# Number of tokens in vocabulary. And number of tokens in each document.
#
set VOCAB_SIZE  2000
set DOC_SIZE     100

set NUM_INSERTS 1000
set NUM_SELECTS 1000

# Force everything in this script to be deterministic.
#
expr {srand(0)}

proc usage {} {
  puts stderr "Usage: $::argv0 <rows> <selects>"
  exit -1
}

proc sql {sql} {
  puts $::fd $sql
}


# Return a list of $nWord randomly generated tokens each between 2 and 10
# characters in length.
#
proc build_vocab {nWord} {
  set ret [list]
  set chars [list a b c d e f g h i j k l m n o p q r s t u v w x y z]
  for {set i 0} {$i<$nWord} {incr i} {
    set len [expr {int((rand()*9.0)+2)}]
    set term ""
    for {set j 0} {$j<$len} {incr j} {
      append term [lindex $chars [expr {int(rand()*[llength $chars])}]]
    }
    lappend ret $term
  }
  set ret
}

proc select_term {} {
  set n [llength $::vocab]
  set t [expr int(rand()*$n*3)]
  if {$t>=2*$n} { set t [expr {($t-2*$n)/100}] }
  if {$t>=$n} { set t [expr {($t-$n)/10}] }
  lindex $::vocab $t
}

proc select_doc {nTerm} {
  set ret [list]
  for {set i 0} {$i<$nTerm} {incr i} {
    lappend ret [select_term]
  }
  set ret
}

proc test_1 {nInsert} {
  sql "PRAGMA synchronous = OFF;"
  sql "DROP TABLE IF EXISTS t1;"
  sql "CREATE VIRTUAL TABLE t1 USING fts4;"
  for {set i 0} {$i < $nInsert} {incr i} {
    set doc [select_doc $::DOC_SIZE]
    #sql "INSERT INTO t1 VALUES('$doc');"
    sql "\"$doc\""
  }
}

proc test_2 {} {
  sql "INSERT INTO t1(t1) VALUES('optimize');"
}

proc test_3 {nSelect} {
  for {set i 0} {$i < $nSelect} {incr i} {
    sql "SELECT count(*) FROM t1 WHERE t1 MATCH '[select_term]';"
  }
}

proc test_4 {nSelect} {
  for {set i 0} {$i < $nSelect} {incr i} {
    sql "SELECT count(*) FROM t1 WHERE t1 MATCH '[select_term] [select_term]';"
  }
}

if {[llength $argv]!=0} usage

set ::vocab [build_vocab $::VOCAB_SIZE]

set ::fd [open fts3speed_insert.sql w]
test_1 $NUM_INSERTS
close $::fd

set ::fd [open fts3speed_select.sql w]
test_3 $NUM_SELECTS
close $::fd

set ::fd [open fts3speed_select2.sql w]
test_4 $NUM_SELECTS
close $::fd

set ::fd [open fts3speed_optimize.sql w]
test_2
close $::fd

puts "Success. Created files:"
puts "  fts3speed_insert.sql"
puts "  fts3speed_select.sql"
puts "  fts3speed_select2.sql"
puts "  fts3speed_optimize.sql"

Changes to test/fts3ah.test.

1
2
3





4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# 2006 October 31 (scaaarey)
#
# The author disclaims copyright to this source code.





#
#*************************************************************************
# This file implements regression tests for SQLite library.  The focus
# here is testing correct handling of excessively long terms.
#
# $Id: fts3ah.test,v 1.1 2007/08/20 17:38:42 shess Exp $
#

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

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

# Generate a term of len copies of char.
proc bigterm {char len} {
  for {set term ""} {$len>0} {incr len -1} {
    append term $char
  }
  return $term
}

# Generate a document of bigterms based on characters from the list
# chars.
proc bigtermdoc {chars len} {
  set doc ""
  foreach char $chars {
    append doc " " [bigterm $char $len]
  }
  return $doc
}

set len 5000
set doc1 [bigtermdoc {a b c d} $len]
set doc2 [bigtermdoc {b d e f} $len]
set doc3 [bigtermdoc {a c e} $len]

set aterm [bigterm a $len]
set bterm [bigterm b $len]
set xterm [bigterm x $len]

db eval {
  CREATE VIRTUAL TABLE t1 USING fts3(content);
  INSERT INTO t1 (rowid, content) VALUES(1, $doc1);
  INSERT INTO t1 (rowid, content) VALUES(2, $doc2);
  INSERT INTO t1 (rowid, content) VALUES(3, $doc3);
}
|

|
>
>
>
>
>



|
<
<





|





<
<
<
<
<
<
<
<





|









|
|
|







1
2
3
4
5
6
7
8
9
10
11
12


13
14
15
16
17
18
19
20
21
22
23








24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# 2006 October 31 
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#*************************************************************************
# This file implements regression tests for SQLite library.  The focus
# here is testing correct handling of very long terms.


#

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

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









# Generate a document of bigterms based on characters from the list
# chars.
proc bigtermdoc {chars len} {
  set doc ""
  foreach char $chars {
    append doc " " [string repeat $char $len]
  }
  return $doc
}

set len 5000
set doc1 [bigtermdoc {a b c d} $len]
set doc2 [bigtermdoc {b d e f} $len]
set doc3 [bigtermdoc {a c e} $len]

set aterm [string repeat a $len]
set bterm [string repeat b $len]
set xterm [string repeat x $len]

db eval {
  CREATE VIRTUAL TABLE t1 USING fts3(content);
  INSERT INTO t1 (rowid, content) VALUES(1, $doc1);
  INSERT INTO t1 (rowid, content) VALUES(2, $doc2);
  INSERT INTO t1 (rowid, content) VALUES(3, $doc3);
}

Changes to test/fts3cov.test.

78
79
80
81
82
83
84
85

86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
      INSERT INTO t1 VALUES('What makes her in the wood so late,');
      INSERT INTO t1 VALUES('A furlong from the castle gate?');
      INSERT INTO t1 VALUES('She had dreams all yesternight');
      INSERT INTO t1 VALUES('Of her own betrothed knight;');
      INSERT INTO t1 VALUES('And she in the midnight wood will pray');
      INSERT INTO t1 VALUES('For the weal of her lover that''s far away.');
    COMMIT;


    INSERT INTO t1(t1) VALUES('optimize');
    SELECT substr(hex(root), 1, 2) FROM t1_segdir;
  }
} {03}

# Test the "missing entry" case:
do_test fts3cov-2.1 {
  set root [db one {SELECT root FROM t1_segdir}]
  read_fts3varint [string range $root 1 end] left_child
  execsql { DELETE FROM t1_segments WHERE blockid = $left_child }
} {}
do_error_test fts3cov-2.2 {
  SELECT * FROM t1 WHERE t1 MATCH 'c*'
} {database disk image is malformed}

# Test the "replaced with NULL" case:
do_test fts3cov-2.3 {
  execsql { INSERT INTO t1_segments VALUES($left_child, NULL) }
} {}
do_error_test fts3cov-2.4 {
  SELECT * FROM t1 WHERE t1 MATCH 'cloud'
} {database disk image is malformed}

#--------------------------------------------------------------------------
# The following tests are to test the effects of OOM errors while storing
# terms in the pending-hash table. Specifically, while creating doclist
# blobs to store in the table. More specifically, to test OOM errors while







|
>






|




|




|


|







78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
      INSERT INTO t1 VALUES('What makes her in the wood so late,');
      INSERT INTO t1 VALUES('A furlong from the castle gate?');
      INSERT INTO t1 VALUES('She had dreams all yesternight');
      INSERT INTO t1 VALUES('Of her own betrothed knight;');
      INSERT INTO t1 VALUES('And she in the midnight wood will pray');
      INSERT INTO t1 VALUES('For the weal of her lover that''s far away.');
    COMMIT;
  }
  execsql {
    INSERT INTO t1(t1) VALUES('optimize');
    SELECT substr(hex(root), 1, 2) FROM t1_segdir;
  }
} {03}

# Test the "missing entry" case:
do_test fts3cov-2.2 {
  set root [db one {SELECT root FROM t1_segdir}]
  read_fts3varint [string range $root 1 end] left_child
  execsql { DELETE FROM t1_segments WHERE blockid = $left_child }
} {}
do_error_test fts3cov-2.3 {
  SELECT * FROM t1 WHERE t1 MATCH 'c*'
} {database disk image is malformed}

# Test the "replaced with NULL" case:
do_test fts3cov-2.4 {
  execsql { INSERT INTO t1_segments VALUES($left_child, NULL) }
} {}
do_error_test fts3cov-2.5 {
  SELECT * FROM t1 WHERE t1 MATCH 'cloud'
} {database disk image is malformed}

#--------------------------------------------------------------------------
# The following tests are to test the effects of OOM errors while storing
# terms in the pending-hash table. Specifically, while creating doclist
# blobs to store in the table. More specifically, to test OOM errors while

Added test/fts3defer.test.

















































































































































































































































































































































































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
# 2010 October 15
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************

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

ifcapable !fts3 {
  finish_test
  return
}

set ::testprefix fts3defer

#--------------------------------------------------------------------------
# Test cases fts3defer-1.* are the "warm body" cases. The database contains
# one row with 15000 instances of the token "a". This makes the doclist for
# "a" so large that FTS3 will avoid loading it in most cases.
#
# To show this, test cases fts3defer-1.2.* execute a bunch of FTS3 queries
# involving token "a". Then, fts3defer-1.3.* replaces the doclist for token
# "a" with all zeroes and fts3defer-1.4.* repeats the tests from 1.2. If
# the tests still work, we can conclude that the doclist for "a" was not
# used.
# 

set aaa [string repeat "a " 15000]

do_execsql_test 1.1 {
  CREATE VIRTUAL TABLE t1 USING fts4;
  BEGIN;
    INSERT INTO t1 VALUES('this is a dog');
    INSERT INTO t1 VALUES('an instance of a phrase');
    INSERT INTO t1 VALUES('an instance of a longer phrase');
    INSERT INTO t1 VALUES($aaa);
  COMMIT;
} {}

set tests {
  1  {SELECT rowid FROM t1 WHERE t1 MATCH '"a dog"'}                 {1}
  2  {SELECT rowid FROM t1 WHERE t1 MATCH '"is a dog"'}              {1}
  3  {SELECT rowid FROM t1 WHERE t1 MATCH '"a longer phrase"'}       {3}
  4  {SELECT snippet(t1) FROM t1 WHERE t1 MATCH '"a longer phrase"'}  
     {"an instance of <b>a</b> <b>longer</b> <b>phrase</b>"}
  5  {SELECT rowid FROM t1 WHERE t1 MATCH 'a dog'}                   {1}
}

do_select_tests 1.2 $tests

do_execsql_test 1.3 {
  SELECT count(*) FROM t1_segments WHERE length(block)>10000;
  UPDATE t1_segments 
    SET block = zeroblob(length(block)) 
    WHERE length(block)>10000;
} {1}

do_select_tests 1.4 $tests

# Drop the table. It is corrupt now anyhow, so not useful for subsequent tests.
#
do_execsql_test 1.5 { DROP TABLE t1 }

#--------------------------------------------------------------------------
# These tests - fts3defer-2.* - are more rigorous. They test that for a
# variety of queries, FTS3 and FTS4 return the same results. And that 
# zeroing the very large doclists that FTS4 does not load does not change
# the results.
#
# They use the following pseudo-randomly generated document data. The
# tokens "zm" and "jk" are especially common in this dataset. Additionally,
# two documents are added to the pseudo-random data before it is loaded
# into FTS4 containing 100,000 instances of the "zm" and "jk" tokens. This
# makes the doclists for those tokens so large that FTS4 avoids loading them
# into memory if possible.
#
set data [list]
lappend data [string repeat "zm " 100000]
lappend data [string repeat "jk " 100000]
lappend data {*}{
  "zm zm agmckuiu uhzq nsab jk rrkx duszemmzl hyq jk"
  "jk uhzq zm zm rgpzmlnmd zm zk jk jk zm"
  "duszemmzl zm jk xldlpy zm jk sbptoa xh jk xldlpy"
  "zm xh zm xqf azavwm jk jk trqd rgpzmlnmd jk"
  "zm vwq urvysbnykk ubwrfqnbjf zk lsz jk doiwavhwwo jk jk"
  "jk xduvfhk orpfawpx zkhdvkw jk mjpavjuhw zm jk duszemmzl zm"
  "jk igju jk jk zm hmjf xh zm gwdfhwurx zk"
  "vgsld jk jk zm hrlipdm jn zm zsmhnf vgsld duszemmzl"
  "gtuiexzsu aayxpmve zm zm zm drir scpgna xh azavwm uhzq"
  "farlehdhq hkfoudzftq igju duszemmzl xnxhf ewle zm hrlipdm urvysbnykk kn"
  "xnxhf jk jk agmckuiu duszemmzl jk zm zm jk vgsld"
  "zm zm zm jk jk urvysbnykk ogttbykvt zm zm jk"
  "iasrqgqv zm azavwm zidhxhbtv jk jk mjpavjuhw zm zm ajmvcydy"
  "rgpzmlnmd tmt mjpavjuhw xh igju jk azavwm fibokdry vgsld ofm"
  "zm jk vgsld jk xh jk csjqxhgj drir jk pmrb"
  "xh jk jk zm rrkx duszemmzl mjpavjuhw xldlpy igju zm"
  "jk hkfoudzftq zf rrkx wdmy jupk jk zm urvysbnykk npywgdvgz"
  "zm jk zm zm zhbrzadb uenvbm aayxpmve urvysbnykk duszemmzl jk"
  "uenvbm jk zm fxw xh bdilwmjw mjpavjuhw uv jk zm"
  "nk jk bnhc pahlds jk igju dzadnqzprr jk jk jk"
  "uhzq uv zm duszemmzl tlqix jk jk xh jk zm"
  "jk zm agmckuiu urvysbnykk jk jk zm zm jk jk"
  "azavwm mjpavjuhw lsgshn trqd xldlpy ogyavjvv agmckuiu ryvwwhlbc jk jk"
  "tmt jk zk zm azavwm ofm acpgim bvgimjik iasrqgqv wuvajhwqz"
  "igju ogyavjvv xrbdak rrkx fibokdry zf ujfhmrllq jk zm hxgwvib"
  "zm pahlds jk uenvbm aayxpmve iaf hmjf xph vnlyvtkgx zm"
  "jk xnxhf igju jk xh jk nvfasfh zm js jk"
  "zm zm rwaj igju xr rrkx xnxhf nvfasfh skxbsqzvmt xatbxeqq"
  "vgsld zm ujfhmrllq uhzq ogyavjvv nsab azavwm zm vgsld jmfiqhwnjg"
  "ymjoym duszemmzl urvysbnykk azavwm jk jmfiqhwnjg bu qcdziqomqk vnlyvtkgx"
  "zm nbilqcnz dzadnqzprr xh bkfgzsxn urvysbnykk xrujfzxqf zm zf agmckuiu"
  "jk urvysbnykk nvfasfh zf xh zm zm qcdziqomqk qvxtclg wdmy"
  "fibokdry jk urvysbnykk jk xr osff zm cvnnsl zm vgsld"
  "jk mjpavjuhw hkfoudzftq jk zm xh xqf urvysbnykk jk iasrqgqv"
  "jk csjqxhgj duszemmzl iasrqgqv aayxpmve zm brsuoqww jk qpmhtvl wluvgsw"
  "jk mj azavwm jk zm jn dzadnqzprr zm jk uhzq"
  "zk xqf jupk fxw nbilqcnz zm jk jcpiwj tznlvbfcv nvfasfh"
  "jk jcpiwj zm xnxhf zm mjpavjuhw mj drir pa pvjrjlas"
  "duszemmzl dzadnqzprr jk swc duszemmzl tmt jk jk pahlds jk"
  "zk zm jk zm zm eczkjblu zm hi pmrb jk"
  "azavwm zm iz agmckuiu jk sntk jk duszemmzl duszemmzl zm"
  "jk zm jk eczkjblu urvysbnykk sk gnl jk ttvgf hmjf"
  "jk bnhc jjrxpjkb mjpavjuhw fibokdry igju jk zm zm xh"
  "wxe ogttbykvt uhzq xr iaf zf urvysbnykk aayxpmve oacaxgjoo mjpavjuhw"
  "gazrt jk ephknonq myjp uenvbm wuvajhwqz jk zm xnxhf nvfasfh"
  "zm aayxpmve csjqxhgj xnxhf xr jk aayxpmve xnxhf zm zm"
  "sokcyf zm ogyavjvv jk zm fibokdry zm jk igju igju"
  "vgsld bvgimjik xuprtlyle jk akmikrqyt jk aayxpmve hkfoudzftq ddjj ithtir"
  "zm uhzq ovkyevlgv zk uenvbm csjqxhgj jk vgsld pgybs jk"
  "zm agmckuiu zexh fibokdry jk uhzq bu tugflixoex xnxhf sk"
  "zm zf uenvbm jk azavwm zm zm agmckuiu zm jk"
  "rrkx jk zf jt zm oacaxgjoo fibokdry wdmy igju csjqxhgj"
  "hi igju zm jk zidhxhbtv dzadnqzprr jk jk trqd duszemmzl"
  "zm zm mjpavjuhw xrbdak qrvbjruc jk qzzqdxq guwq cvnnsl zm"
  "ithtir jk jk qcdziqomqk zm farlehdhq zm zm xrbdak jk"
  "ixfipk csjqxhgj azavwm sokcyf ttvgf vgsld jk sk xh zk"
  "nvfasfh azavwm zm zm zm fxw nvfasfh zk gnl trqd"
  "zm fibokdry csjqxhgj ofm dzadnqzprr jk akmikrqyt orpfawpx duszemmzl vwq"
  "csjqxhgj jk jk vgsld urvysbnykk jk nxum jk jk nxum"
  "zm hkfoudzftq jk ryvwwhlbc mjpavjuhw ephknonq jk zm ogyavjvv zm"
  "lwa hi xnxhf qdyerbws zk njtc jk uhzq zm jk"
  "trqd zm dzadnqzprr zm urvysbnykk jk lsz jk mjpavjuhw cmnnkna"
  "duszemmzl zk jk jk fibokdry jseuhjnzo zm aayxpmve zk jk"
  "fibokdry jk sviq qvxtclg wdmy jk doiwavhwwo zexh jk zm"
  "jupk zm xh jk mjpavjuhw zm jk nsab npywgdvgz duszemmzl"
  "zm igju zm zm nvfasfh eh hkfoudzftq fibokdry fxw xkblf"
  "jk zm jk jk zm xh zk abthnzcv zf csjqxhgj"
  "zm zm jk nkaotm urvysbnykk sbptoa bq jk ktxdty ubwrfqnbjf"
  "nvfasfh aayxpmve xdcuz zm tugflixoex jcpiwj zm mjpavjuhw fibokdry doiwavhwwo"
  "iaf jk mjpavjuhw zm duszemmzl jk jk uhzq pahlds fibokdry"
  "ddjj zk azavwm jk swc zm gjtexkv jk xh jk"
  "igju jk csjqxhgj zm jk dzadnqzprr duszemmzl ulvcbv jk jk"
  "jk fibokdry zm csjqxhgj jn zm zm zm zf uhzq"
  "duszemmzl jk xkblf zk hrlipdm aayxpmve uenvbm uhzq jk zf"
  "dzadnqzprr jk zm zdu nvfasfh zm jk urvysbnykk hmjf jk"
  "jk aayxpmve aserrdxm acpgim fibokdry jk drir wxe brsuoqww rrkx"
  "uhzq csjqxhgj nvfasfh jk rrkx qbamok trqd uenvbm sntk zm"
  "ps azavwm zkhdvkw jk zm jk jk zm csjqxhgj xedlrcfo"
  "jk jk ogyavjvv jk zm farlehdhq duszemmzl jk agitgxamxe jk"
  "qzzqdxq rwaj jk jk zm xqf jk uenvbm jk zk"
  "zm hxgwvib akmikrqyt zf agmckuiu uenvbm bq npywgdvgz azavwm jk"
  "zf jmfiqhwnjg js igju zm aayxpmve zm mbxnljomiv csjqxhgj nvfasfh"
  "zm jk jk gazrt jk jk lkc jk nvfasfh jk"
  "xldlpy orpfawpx zkhdvkw jk zm igju zm urvysbnykk dzadnqzprr mbxnljomiv"
  "urvysbnykk jk zk igju zm uenvbm jk zm ithtir jk"
  "zm zk zm zf ofm zm xdcuz dzadnqzprr zm vgsld"
  "sbptoa jk tugflixoex jk zm zm vgsld zm xh zm"
  "uhzq jk zk evvivo vgsld vniqnuynvf agmckuiu jk zm zm"
  "zm nvfasfh zm zm zm abthnzcv uenvbm jk zk dzadnqzprr"
  "zm azavwm igju qzzqdxq jk xnxhf abthnzcv jk nvfasfh zm"
  "qbamok fxw vgsld igju cmnnkna xnxhf vniqnuynvf zk xh zm"
  "nvfasfh zk zm mjpavjuhw dzadnqzprr jk jk duszemmzl xldlpy nvfasfh"
  "xnxhf sviq nsab npywgdvgz osff vgsld farlehdhq fibokdry wjbkhzsa hhac"
  "zm azavwm scpgna jk jk bq jk duszemmzl fibokdry ovkyevlgv"
  "csjqxhgj zm jk jk duszemmzl zk xh zm jk zf"
  "urvysbnykk dzadnqzprr csjqxhgj mjpavjuhw ubwrfqnbjf nkaotm jk jk zm drir"
  "nvfasfh xh igju zm wluvgsw jk zm srwwnezqk ewle ovnq"
  "jk nvfasfh eh ktxdty urvysbnykk vgsld zm jk eh uenvbm"
  "orpfawpx pahlds jk uhzq hi zm zm zf jk dzadnqzprr"
  "srwwnezqk csjqxhgj rbwzuf nvfasfh jcpiwj xldlpy nvfasfh jk vgsld wjybxmieki"
}



foreach {tn setup} {
  1 {
    set dmt_modes 0
    execsql { CREATE VIRTUAL TABLE t1 USING FTS3 }
    foreach doc $data { execsql { INSERT INTO t1 VALUES($doc) } }
  }
  2 {
    set dmt_modes 0
    execsql { CREATE VIRTUAL TABLE t1 USING FTS4 }
    foreach doc $data { execsql { INSERT INTO t1 VALUES($doc) } }
  }
  3 {
    set dmt_modes {0 1 2}
    execsql { CREATE VIRTUAL TABLE t1 USING FTS4 }
    foreach doc $data { execsql { INSERT INTO t1 VALUES($doc) } }
    execsql {
      UPDATE t1_segments
      SET block = zeroblob(length(block)) 
      WHERE length(block)>10000;
    }
  }
} {

  execsql { DROP TABLE IF EXISTS t1 }
  eval $setup
  set ::testprefix fts3defer-2.$tn
  set DO_MALLOC_TEST 0

  do_execsql_test 0 { 
    SELECT count(*) FROM t1_segments WHERE length(block)>10000 
  } {2}

  do_select_test 1.1 {
    SELECT rowid FROM t1 WHERE t1 MATCH 'jk xnxhf'
  } {13 29 40 47 48 52 63 92}
  do_select_test 1.2 {
    SELECT rowid FROM t1 WHERE t1 MATCH 'jk eh'
  } {100}
  do_select_test 1.3 {
    SELECT rowid FROM t1 WHERE t1 MATCH 'jk ubwrfqnbjf'
  } {7 70 98}
  do_select_test 1.4 {
    SELECT rowid FROM t1 WHERE t1 MATCH 'duszemmzl jk'
  } {3 5 8 10 13 18 20 23 32 37 41 43 55 60 65 67 72 74 76 81 94 96 97}
  do_select_test 1.5 {
    SELECT rowid FROM t1 WHERE t1 MATCH 'ubwrfqnbjf jk'
  } {7 70 98}
  do_select_test 1.6 {
    SELECT rowid FROM t1 WHERE t1 MATCH 'jk ubwrfqnbjf jk jk jk jk'
  } {7 70 98}
  do_select_test 1.7 {
    SELECT rowid FROM t1 WHERE t1 MATCH 'zm xnxhf'
  } {12 13 29 30 40 47 48 52 63 92 93}
  do_select_test 1.8 {
    SELECT rowid FROM t1 WHERE t1 MATCH 'zm eh'
  } {68 100}
  do_select_test 1.9 {
    SELECT rowid FROM t1 WHERE t1 MATCH 'zm ubwrfqnbjf'
  } {7 70 98}

  do_select_test 2.1 {
    SELECT rowid FROM t1 WHERE t1 MATCH '"zm agmckuiu"'
  } {3 24 52 53}
  do_select_test 2.2 {
    SELECT rowid FROM t1 WHERE t1 MATCH '"zm zf"'
  } {33 53 75 88 101}
  do_select_test 2.3 {
    SELECT rowid FROM t1 WHERE t1 MATCH '"zm aayxpmve"'
  } {48 65 84}
  do_select_test 2.4 {
    SELECT rowid FROM t1 WHERE t1 MATCH '"aayxpmve zm"'
  } {11 37 84}
  do_select_test 2.5 {
    SELECT rowid FROM t1 WHERE t1 MATCH '"jk azavwm"'
  } {16 53}
  do_select_test 2.6 {
    SELECT rowid FROM t1 WHERE t1 MATCH '"xh jk jk"'
  } {18}
  do_select_test 2.7 {
    SELECT rowid FROM t1 WHERE t1 MATCH '"zm jk vgsld"'
  } {13 17}

  do_select_test 3.1 {
    SELECT snippet(t1, '[', ']') FROM t1 WHERE t1 MATCH '"zm agmckuiu"'
  } {
    {zm [zm] [agmckuiu] uhzq nsab jk rrkx duszemmzl hyq jk} 
    {jk [zm] [agmckuiu] urvysbnykk jk jk zm zm jk jk} 
    {[zm] [agmckuiu] zexh fibokdry jk uhzq bu tugflixoex xnxhf sk} 
    {zm zf uenvbm jk azavwm zm [zm] [agmckuiu] zm jk}
  }

  do_select_test 3.2 {
    SELECT snippet(t1, '[', ']') FROM t1 WHERE t1 MATCH 'xnxhf jk'
  } {
    {[xnxhf] [jk] [jk] agmckuiu duszemmzl [jk] zm zm [jk] vgsld} 
    {[jk] [xnxhf] igju [jk] xh [jk] nvfasfh zm js [jk]} 
    {[jk] jcpiwj zm [xnxhf] zm mjpavjuhw mj drir pa pvjrjlas} 
    {gazrt [jk] ephknonq myjp uenvbm wuvajhwqz [jk] zm [xnxhf] nvfasfh} 
    {zm aayxpmve csjqxhgj [xnxhf] xr [jk] aayxpmve [xnxhf] zm zm} 
    {zm agmckuiu zexh fibokdry [jk] uhzq bu tugflixoex [xnxhf] sk} 
    {lwa hi [xnxhf] qdyerbws zk njtc [jk] uhzq zm [jk]} 
    {zm azavwm igju qzzqdxq [jk] [xnxhf] abthnzcv [jk] nvfasfh zm}
  }

  do_select_test 4.1 {
    SELECT offsets(t1) FROM t1 WHERE t1 MATCH '"jk uenvbm"'
  } {
    {0 0 10 2 0 1 13 6} {0 0 26 2 0 1 29 6}
  }

  do_select_test 4.2 {
    SELECT offsets(t1) FROM t1 WHERE t1 MATCH 'duszemmzl jk fibokdry'
  } {
    {0 2 3 8 0 1 36 2 0 0 58 9} 
    {0 0 0 9 0 1 13 2 0 1 16 2 0 2 19 8 0 1 53 2} 
    {0 1 4 2 0 0 20 9 0 1 30 2 0 1 33 2 0 2 48 8} 
    {0 1 17 2 0 1 20 2 0 1 26 2 0 0 29 9 0 2 39 8}
  }

  # The following block of tests runs normally with FTS3 or FTS4 without the
  # long doclists zeroed. And with OOM-injection for FTS4 with long doclists
  # zeroed. Change this by messing with the [set dmt_modes] commands above.
  #
  foreach DO_MALLOC_TEST $dmt_modes {
    
    # Phrase search.
    do_select_test 5.$DO_MALLOC_TEST.1 {
      SELECT rowid FROM t1 WHERE t1 MATCH '"jk mjpavjuhw"'
    } {8 15 36 64 67 72}

    # Multiple tokens search.
    do_select_test 5.$DO_MALLOC_TEST.2 {
      SELECT rowid FROM t1 WHERE t1 MATCH 'duszemmzl zm'
    } {3 5 8 10 12 13 18 20 23 37 43 55 60 65 67 72 74 81 94 96 97}

    # snippet() function with phrase.
    do_select_test 5.$DO_MALLOC_TEST.3 {
      SELECT snippet(t1, '[', ']') FROM t1 WHERE t1 MATCH '"zm aayxpmve"'
    } {
      {[zm] [aayxpmve] csjqxhgj xnxhf xr jk aayxpmve xnxhf zm zm} 
      {duszemmzl zk jk jk fibokdry jseuhjnzo [zm] [aayxpmve] zk jk} 
      {zf jmfiqhwnjg js igju [zm] [aayxpmve] zm mbxnljomiv csjqxhgj nvfasfh}
    }
    
    # snippet() function with multiple tokens.
    do_select_test 5.$DO_MALLOC_TEST.4 {
      SELECT snippet(t1, '[', ']') FROM t1 WHERE t1 MATCH 'zm zhbrzadb'
    } {
      {[zm] jk [zm] [zm] [zhbrzadb] uenvbm aayxpmve urvysbnykk duszemmzl jk}
    }
    
    # snippet() function with phrase.
    do_select_test 5.$DO_MALLOC_TEST.5 {
      SELECT offsets(t1) FROM t1 WHERE t1 MATCH '"zm aayxpmve"'
    } {
      {0 0 0 2 0 1 3 8} {0 0 38 2 0 1 41 8} {0 0 22 2 0 1 25 8}
    }
    
    # snippet() function with multiple tokens.
    do_select_test 5.$DO_MALLOC_TEST.6 {
      SELECT offsets(t1) FROM t1 WHERE t1 MATCH 'zm zhbrzadb'
    } {
      {0 0 0 2 0 0 6 2 0 0 9 2 0 1 12 8}
    }
  }
}


finish_test

Changes to test/malloc_common.tcl.

522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541






542
543
544
545
546
547
548
# by parameter $result, or (b) TCL throws an "out of memory" error.
#
# If DO_MALLOC_TEST is defined and set to zero, then the SELECT statement
# is executed just once. In this case the test case passes if the results
# match the expected results passed via parameter $result.
#
proc do_select_test {name sql result} {
  uplevel [list doPassiveTest 0 $name $sql [list 0 $result]]
}

proc do_restart_select_test {name sql result} {
  uplevel [list doPassiveTest 1 $name $sql [list 0 $result]]
}

proc do_error_test {name sql error} {
  uplevel [list doPassiveTest 0 $name $sql [list 1 $error]]
}

proc doPassiveTest {isRestart name sql catchres} {
  if {![info exists ::DO_MALLOC_TEST]} { set ::DO_MALLOC_TEST 1 }







  switch $::DO_MALLOC_TEST {
    0 { # No malloc failures.
      do_test $name [list set {} [uplevel [list catchsql $sql]]] $catchres
      return
    }
    1 { # Simulate transient failures.







|












>
>
>
>
>
>







522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
# by parameter $result, or (b) TCL throws an "out of memory" error.
#
# If DO_MALLOC_TEST is defined and set to zero, then the SELECT statement
# is executed just once. In this case the test case passes if the results
# match the expected results passed via parameter $result.
#
proc do_select_test {name sql result} {
  uplevel [list doPassiveTest 0 $name $sql [list 0 [list {*}$result]]]
}

proc do_restart_select_test {name sql result} {
  uplevel [list doPassiveTest 1 $name $sql [list 0 $result]]
}

proc do_error_test {name sql error} {
  uplevel [list doPassiveTest 0 $name $sql [list 1 $error]]
}

proc doPassiveTest {isRestart name sql catchres} {
  if {![info exists ::DO_MALLOC_TEST]} { set ::DO_MALLOC_TEST 1 }

  if {[info exists ::testprefix] 
   && [string is integer [string range $name 0 0]]
  } {
    set name $::testprefix.$name
  }

  switch $::DO_MALLOC_TEST {
    0 { # No malloc failures.
      do_test $name [list set {} [uplevel [list catchsql $sql]]] $catchres
      return
    }
    1 { # Simulate transient failures.

Changes to test/permutations.test.

162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
  All FTS3 tests except fts3malloc.test and fts3rnd.test.
} -files {
  fts3aa.test fts3ab.test fts3ac.test fts3ad.test fts3ae.test
  fts3af.test fts3ag.test fts3ah.test fts3ai.test fts3aj.test
  fts3ak.test fts3al.test fts3am.test fts3an.test fts3ao.test
  fts3atoken.test fts3b.test fts3c.test fts3cov.test fts3d.test
  fts3e.test fts3expr.test fts3expr2.test fts3near.test 
  fts3query.test fts3snippet.test
}


lappend ::testsuitelist xxx
#-------------------------------------------------------------------------
# Define the coverage related test suites:
#







|







162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
  All FTS3 tests except fts3malloc.test and fts3rnd.test.
} -files {
  fts3aa.test fts3ab.test fts3ac.test fts3ad.test fts3ae.test
  fts3af.test fts3ag.test fts3ah.test fts3ai.test fts3aj.test
  fts3ak.test fts3al.test fts3am.test fts3an.test fts3ao.test
  fts3atoken.test fts3b.test fts3c.test fts3cov.test fts3d.test
  fts3e.test fts3expr.test fts3expr2.test fts3near.test 
  fts3query.test fts3snippet.test fts3defer.test
}


lappend ::testsuitelist xxx
#-------------------------------------------------------------------------
# Define the coverage related test suites:
#