SQLite4
Changes On Branch matchinfo
Not logged in

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

Changes In Branch matchinfo Excluding Merge-Ins

This is equivalent to a diff from 7bc0e58875 to 201233ee64

2013-01-09
18:15
Merge matchinfo branch with trunk. check-in: dbbce4e438 user: dan tags: trunk
18:09
Fix a few compiler warnings and test failures. Leaf check-in: 201233ee64 user: dan tags: matchinfo
17:16
Fixes for snippet function and tests. Add API to determine the number of tokens in an FTS query phrase. check-in: 0d5a640f1f user: dan tags: matchinfo
2013-01-01
19:56
Add APIs to allow fts5 to be augmented with ranking and snippet functions. Does not work yet. check-in: a235305d42 user: dan tags: matchinfo
19:02
Add the sqlite4_kvfactory typedef to the interface and use that typedef throughout the implementation. This check-in also includes some unrelated cleanup of the sqlite4.h file. check-in: a2630e5d90 user: drh tags: trunk
18:41
Fix a memory leak in fts5.c. check-in: 7bc0e58875 user: dan tags: trunk
18:24
Add files "mem.h" and "mem.c". These are not currently linked into the build and have never been tested. At the moment they should be considered working notes, not real code. The code contained in these files might get folded into the build, or it might be deleted. check-in: e9efc61a51 user: drh tags: trunk

Changes to src/expr.c.

2586
2587
2588
2589
2590
2591
2592



2593
2594
2595
2596
2597
2598
2599
          pColl = sqlite4ExprCollSeq(pParse, pFarg->a[i].pExpr);
        }
      }
      if( pDef->flags & SQLITE4_FUNC_NEEDCOLL ){
        if( !pColl ) pColl = db->pDfltColl; 
        sqlite4VdbeAddOp4(v, OP_CollSeq, 0, 0, 0, (char *)pColl, P4_COLLSEQ);
      }



      sqlite4VdbeAddOp4(v, OP_Function, constMask, r1, target,
                        (char*)pDef, P4_FUNCDEF);
      sqlite4VdbeChangeP5(v, (u8)nFarg);
      if( nFarg ){
        sqlite4ReleaseTempRange(pParse, r1, nFarg);
      }
      break;







>
>
>







2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
          pColl = sqlite4ExprCollSeq(pParse, pFarg->a[i].pExpr);
        }
      }
      if( pDef->flags & SQLITE4_FUNC_NEEDCOLL ){
        if( !pColl ) pColl = db->pDfltColl; 
        sqlite4VdbeAddOp4(v, OP_CollSeq, 0, 0, 0, (char *)pColl, P4_COLLSEQ);
      }
      if( pDef->bMatchinfo ){
        sqlite4VdbeAddOp1(v, OP_Mifunction, pFarg->a[0].pExpr->iTable);
      }
      sqlite4VdbeAddOp4(v, OP_Function, constMask, r1, target,
                        (char*)pDef, P4_FUNCDEF);
      sqlite4VdbeChangeP5(v, (u8)nFarg);
      if( nFarg ){
        sqlite4ReleaseTempRange(pParse, r1, nFarg);
      }
      break;

Changes to src/fts5.c.

10
11
12
13
14
15
16































































17
18
19
20
21
22
23
..
76
77
78
79
80
81
82
83
84
85
86
87

88
89
90
91

92
93
94
95
96
97
98
...
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
...
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
...
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
...
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
...
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
...
688
689
690
691
692
693
694

695
696
697
698
699
700
701
...
744
745
746
747
748
749
750















751
752
753
754
755
756
757
...
758
759
760
761
762
763
764

765
766
767
768
769
770
771
...
813
814
815
816
817
818
819

820
821
822
823
824
825
826
...
881
882
883
884
885
886
887











888
889
890
891
892
893
894
895
896
897
898
899
900
901
....
1030
1031
1032
1033
1034
1035
1036

1037
1038
1039
1040
1041
1042
1043
....
1090
1091
1092
1093
1094
1095
1096

1097
1098


1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
....
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139

1140
1141
1142


1143
1144











1145
1146
1147
1148
1149
1150
1151
....
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
....
1187
1188
1189
1190
1191
1192
1193












































































































































1194
1195
1196
1197
1198
1199
1200
....
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213



1214
1215
1216
1217
1218
1219
1220


1221
1222

1223
1224
1225
1226
1227
1228
1229
....
1232
1233
1234
1235
1236
1237
1238
1239

1240
1241
1242
1243
1244
1245











1246

1247
1248
1249
1250
1251
1252
1253
1254


1255
1256
1257
1258
1259
1260
1261
....
1269
1270
1271
1272
1273
1274
1275
1276















































1277




1278
1279
1280
1281
1282
1283
1284
....
1295
1296
1297
1298
1299
1300
1301

1302
1303
1304
1305
1306
1307
1308
....
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
....
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
....
1439
1440
1441
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
1471
....
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
....
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
....
1898
1899
1900
1901
1902
1903
1904
1905
1906










1907

1908

1909
1910
1911
1912
1913
1914
1915
....
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
....
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
....
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
....
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
....
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
....
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
....
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
....
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224



2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237

2238
2239

2240
2241
2242


2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
....
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
....
2294
2295
2296
2297
2298
2299
2300






























































































































































































































































































































































































































































































































2301
2302
2303
2304
2305
2306
2307
**
*************************************************************************
*/

#include "sqliteInt.h"
#include "vdbeInt.h"
































































/*
** Default distance value for NEAR operators.
*/
#define FTS5_DEFAULT_NEAR 10

/*
** Token types used by expression parser.
................................................................................
**   expr := expr NOT expr
**   expr := expr AND expr
**   expr := expr OR  expr
**   expr := LP expr RP
*/

/*
** Context object used by expression parser.
*/
typedef struct Fts5Expr Fts5Expr;
typedef struct Fts5ExprNode Fts5ExprNode;
typedef struct Fts5List Fts5List;

typedef struct Fts5Parser Fts5Parser;
typedef struct Fts5ParserToken Fts5ParserToken;
typedef struct Fts5Phrase Fts5Phrase;
typedef struct Fts5Prefix Fts5Prefix;

typedef struct Fts5Str Fts5Str;
typedef struct Fts5Token Fts5Token;


struct Fts5ParserToken {
  int eType;                      /* Token type */
  int n;                          /* Size of z[] in bytes */
................................................................................
  Fts5ExprNode *pLeft;
  Fts5ExprNode *pRight;
  const u8 *aPk;                  /* Primary key of current entry (or null) */
  int nPk;                        /* Size of aPk[] in bytes */
};

struct Fts5Expr {
  Fts5ExprNode *pRoot;


};

/*
** FTS5 specific cursor data.
*/
struct Fts5Cursor {
  sqlite4 *db;
  Fts5Info *pInfo;
  Fts5Expr *pExpr;                /* MATCH expression for this cursor */


  KVByteArray *aKey;              /* Buffer for primary key */
  int nKeyAlloc;                  /* Bytes allocated at aKey[] */




















};

/*
** This type is used when reading (decoding) an instance-list.
*/
typedef struct InstanceList InstanceList;
struct InstanceList {
  u8 *aList;
  int nList;
  int iList;

  /* The current entry */
  int iCol;
  int iWeight;
  int iOff;
};












/*
** Return true for EOF, or false if the next entry is valid.
*/
static int fts5InstanceListNext(InstanceList *p){
  int i = p->iList;
  int bRet = 1;
................................................................................
    u32 iVal;
    i += getVarint32(&p->aList[i], iVal);
    if( (iVal & 0x03)==0x01 ){
      p->iCol = (iVal>>2);
      p->iOff = 0;
    }
    else if( (iVal & 0x03)==0x03 ){
      p->iWeight = (iVal>>2);
    }
    else{
      p->iOff += (iVal>>1);
      bRet = 0;
    }
  }
  if( bRet ){
................................................................................
static int fts5InstanceListEof(InstanceList *p){
  return (p->aList==0);
}

static void fts5InstanceListAppend(
  InstanceList *p,                /* Instance list to append to */
  int iCol,                       /* Column of new entry */
  int iWeight,                    /* Weight of new entry */
  int iOff                        /* Offset of new entry */
){
  assert( iCol>=p->iCol );
  assert( iCol>p->iCol || iOff>=p->iOff );

  if( iCol!=p->iCol ){
    p->iList += putVarint32(&p->aList[p->iList], (iCol<<2)|0x01);
    p->iCol = iCol;
    p->iOff = 0;
  }

  if( iWeight!=p->iWeight ){
    p->iList += putVarint32(&p->aList[p->iList], (iWeight<<2)|0x03);
    p->iWeight = iWeight;
  }

  p->iList += putVarint32(&p->aList[p->iList], (iOff-p->iOff)<<1);
  p->iOff = iOff;

  assert( p->iList<=p->nList );
}
................................................................................
}

/*
** Callback for fts5CountTokens().
*/
static int fts5CountTokensCb(
  void *pCtx, 
  int iWeight, 
  int iOff, 
  const char *z, int n,
  int iSrc, int nSrc
){
  (*((int *)pCtx))++;
  return 0;
}
................................................................................
struct AppendTokensCtx {
  Fts5Parser *pParse;
  Fts5Str *pStr;
};

static int fts5AppendTokensCb(
  void *pCtx, 
  int iWeight, 
  int iOff, 
  const char *z, int n, 
  int iSrc, int nSrc
){
  struct AppendTokensCtx *p = (struct AppendTokensCtx *)pCtx;
  Fts5Parser *pParse = p->pParse;
  Fts5Token *pToken;
................................................................................
    sqlite4DbFree(db, pNode);
  }
}

static void fts5ExpressionFree(sqlite4 *db, Fts5Expr *pExpr){
  if( pExpr ){
    fts5FreeExprNode(db, pExpr->pRoot);

    sqlite4DbFree(db, pExpr);
  }
}

typedef struct ExprHier ExprHier;
struct ExprHier {
  Fts5ExprNode **ppNode;
................................................................................
  *pp = pNode;
  (*paHier)[*pnHier].ppNode = &pNode->pRight;
  (*paHier)[*pnHier].nOpen = 0;
  (*pnHier)++;

  return SQLITE4_OK;
}
















static int fts5ParseExpression(
  sqlite4 *db,                    /* Database handle */
  Fts5Tokenizer *pTokenizer,      /* Tokenizer module */
  sqlite4_tokenizer *p,           /* Tokenizer instance */
  int iRoot,                      /* Root page number of FTS index */
  char **azCol,                   /* Array of column names (nul-term'd) */
................................................................................
  int nCol,                       /* Size of array azCol[] */
  const char *zExpr,              /* FTS expression text */
  Fts5Expr **ppExpr,              /* OUT: Expression object */
  char **pzErr                    /* OUT: Error message */
){
  int rc = SQLITE4_OK;
  Fts5Parser sParse;

  int nExpr;
  int i;
  Fts5Expr *pExpr;

  int nHier = 0;
  int nHierAlloc = 0;
  ExprHier *aHier = 0;
................................................................................
            rc = SQLITE4_NOMEM;
          }else{
            pNode->eType = TOKEN_PRIMITIVE;
            pNode->pPhrase = pPhrase;
            *pp = pNode;
          }
        }

        break;
      }

      case TOKEN_AND:
      case TOKEN_OR:
      case TOKEN_NOT: {
        Fts5ExprNode **pp = aHier[nHier-1].ppNode;
................................................................................

  if( rc==SQLITE4_OK && *aHier[nHier-1].ppNode==0 ){
    rc = SQLITE4_ERROR;
  }
  for(i=0; rc==SQLITE4_OK && i<nHier; i++){
    if( aHier[i].nOpen>0 ) rc = SQLITE4_ERROR;
  }












  if( rc!=SQLITE4_OK ){
    fts5ExpressionFree(db, pExpr);
    *pzErr = sParse.zErr;
  }else{
    *ppExpr = pExpr;
  }
  sqlite4DbFree(db, aHier);
  return rc;
}

/*
** Search for the Fts5Tokenizer object named zName. Return a pointer to it
** if it exists, or NULL otherwise.
................................................................................
          ExprListItem *pItem = &pArgs->a[j];
          if( pItem->zName ) break;
          nByte += sqlite4Strlen30(pItem->pExpr->u.zToken) + 1;
        }
        nByte += sizeof(char *) * (j-i);
        pFts->azTokenizer = (char **)sqlite4DbMallocZero(pParse->db, nByte);
        if( pFts->azTokenizer==0 ) return;


        pSpace = (char *)&pFts->azTokenizer[j-i];
        for(j=i; j<pArgs->nExpr; j++){
          ExprListItem *pItem = &pArgs->a[j];
          if( pItem->zName && j>i ){
            break;
          }else{
................................................................................
** sqlite4DbRealloc().
*/
typedef struct TokenizeCtx TokenizeCtx;
typedef struct TokenizeTerm TokenizeTerm;
struct TokenizeCtx {
  int rc;
  int iCol;

  sqlite4 *db;
  int nMax;


  Hash hash;
};
struct TokenizeTerm {
  int iWeight;                    /* Weight of previous entry */
  int iCol;                       /* Column containing previous entry */
  int iOff;                       /* Token offset of previous entry */
  int nToken;                     /* Size of token in bytes */
  int nData;                      /* Bytes of data in value */
  int nAlloc;                     /* Bytes of data allocated */
};

................................................................................
  a = &(((unsigned char *)&pTerm[1])[pTerm->nToken+pTerm->nData]);
  pTerm->nData += putVarint32(a, iVal);
  return pTerm;
}

static int fts5TokenizeCb(
  void *pCtx, 
  int iWeight, 
  int iOff,
  const char *zToken, 
  int nToken, 
  int iSrc, 
  int nSrc
){
  TokenizeCtx *p = (TokenizeCtx *)pCtx;

  TokenizeTerm *pTerm = 0;
  TokenizeTerm *pOrig = 0;



  if( nToken>p->nMax ) p->nMax = nToken;












  pTerm = (TokenizeTerm *)sqlite4HashFind(&p->hash, zToken, nToken);
  if( pTerm==0 ){
    /* Size the initial allocation so that it fits in the lookaside buffer */
    int nAlloc = sizeof(TokenizeTerm) + nToken + 32;

    pTerm = sqlite4DbMallocZero(p->db, nAlloc);
    if( pTerm ){
................................................................................
        pTerm = 0;
      }
      if( pTerm==0 ) goto tokenize_cb_out;
    }
  }
  pOrig = pTerm;

  if( iWeight!=pTerm->iWeight ){
    pTerm = fts5TokenizeAppendInt(p, pTerm, (iWeight << 2) | 0x00000003);
    if( !pTerm ) goto tokenize_cb_out;
    pTerm->iWeight = iWeight;
  }

  if( pTerm && p->iCol!=pTerm->iCol ){
    pTerm = fts5TokenizeAppendInt(p, pTerm, (p->iCol << 2) | 0x00000001);
    if( !pTerm ) goto tokenize_cb_out;
    pTerm->iCol = p->iCol;
    pTerm->iOff = 0;
................................................................................
  if( !pTerm ){
    p->rc = SQLITE4_NOMEM;
    return 1;
  }

  return 0;
}













































































































































/*
** Update an fts index.
*/
int sqlite4Fts5Update(
  sqlite4 *db,                    /* Database handle */
  Fts5Info *pInfo,                /* Description of fts index to update */
................................................................................
  int bDel,                       /* True for a delete, false for insert */
  char **pzErr                    /* OUT: Error message */
){
  int i;
  int rc = SQLITE4_OK;
  KVStore *pStore;
  TokenizeCtx sCtx;
  u8 *aKey = 0;
  int nKey = 0;
  int nTnum = 0;
  u32 dummy = 0;




  const u8 *pPK;
  int nPK;
  HashElem *pElem;

  pStore = db->aDb[pInfo->iDb].pKV;
  sCtx.rc = SQLITE4_OK;


  sCtx.db = db;
  sCtx.nMax = 0;

  sqlite4HashInit(db->pEnv, &sCtx.hash, 1);

  pPK = (const u8 *)sqlite4_value_blob(pKey);
  nPK = sqlite4_value_bytes(pKey);
  
  nTnum = getVarint32(pPK, dummy);
  nPK -= nTnum;
................................................................................
  for(i=0; rc==SQLITE4_OK && i<pInfo->nCol; i++){
    sqlite4_value *pArg = (sqlite4_value *)(&aArg[i]);
    if( pArg->flags & MEM_Str ){
      const char *zText;
      int nText;

      zText = (const char *)sqlite4_value_text(pArg);
      nText = sqlite4_value_bytes(pArg); sCtx.iCol = i;

      rc = pInfo->pTokenizer->xTokenize(
          &sCtx, pInfo->p, zText, nText, fts5TokenizeCb
      );
    }
  }












  nKey = sqlite4VarintLen(pInfo->iRoot) + 2 + sCtx.nMax + nPK;

  aKey = sqlite4DbMallocRaw(db, nKey);
  if( aKey==0 ) rc = SQLITE4_NOMEM;

  for(pElem=sqliteHashFirst(&sCtx.hash); pElem; pElem=sqliteHashNext(pElem)){
    TokenizeTerm *pTerm = (TokenizeTerm *)sqliteHashData(pElem);
    if( rc==SQLITE4_OK ){
      int nToken = sqliteHashKeysize(pElem);
      char *zToken = (char *)sqliteHashKey(pElem);



      nKey = putVarint32(aKey, pInfo->iRoot);
      aKey[nKey++] = 0x24;
      memcpy(&aKey[nKey], zToken, nToken);
      nKey += nToken;
      aKey[nKey++] = 0x00;
      memcpy(&aKey[nKey], pPK, nPK);
................................................................................
        const KVByteArray *aData = (const KVByteArray *)&pTerm[1];
        aData += pTerm->nToken;
        rc = sqlite4KVStoreReplace(pStore, aKey, nKey, aData, pTerm->nData);
      }
    }
    sqlite4DbFree(db, pTerm);
  }
  















































  sqlite4DbFree(db, aKey);




  sqlite4HashClear(&sCtx.hash);
  return rc;
}

static Fts5Info *fts5InfoCreate(Parse *pParse, Index *pIdx, int bCol){
  sqlite4 *db = pParse->db;
  Fts5Info *pInfo;                /* p4 argument for FtsUpdate opcode */
................................................................................
    nByte += nCol * sizeof(char *);
  }

  pInfo = sqlite4DbMallocZero(db, nByte);
  if( pInfo ){
    pInfo->iDb = sqlite4SchemaToIndex(db, pIdx->pSchema);
    pInfo->iRoot = pIdx->tnum;

    pInfo->nCol = pIdx->pTable->nCol;
    fts5TokenizerCreate(pParse, pIdx->pFts, &pInfo->pTokenizer, &pInfo->p);

    if( pInfo->p==0 ){
      assert( pParse->nErr );
      sqlite4DbFree(db, pInfo);
      pInfo = 0;
................................................................................
**   * the weight assigned to the instance,
**   * the column number, and
**   * the term offset.
*/
static i64 fts5TermInstanceCksum(
  const u8 *aTerm, int nTerm,
  const u8 *aPk, int nPk,
  int iWeight,
  int iCol,
  int iOff
){
  int i;
  i64 cksum = 0;

  /* Add the term to the checksum */
................................................................................

  /* Add the primary key blob to the checksum */
  for(i=0; i<nPk; i++){
    cksum += (cksum << 3) + aPk[i];
  }

  /* Add the weight, column number and offset (in that order) to the checksum */
  cksum += (cksum << 3) + iWeight;
  cksum += (cksum << 3) + iCol;
  cksum += (cksum << 3) + iOff;

  return cksum;
}


................................................................................
  u8 const *aVal; int nVal;       /* List of token instances */
  u8 const *aToken; int nToken;   /* Token for this entry */
  u8 const *aPk; int nPk;         /* Entry primary key blob */
  InstanceList sList;             /* Used to iterate through pVal */
  int nTnum;
  u32 tnum;


  aKey = (const u8 *)sqlite4_value_blob(pKey);
  nKey = sqlite4_value_bytes(pKey);
  aVal = (const u8 *)sqlite4_value_blob(pVal);
  nVal = sqlite4_value_bytes(pVal);

  /* Find the token and primary key blobs for this entry. */
  nTnum = getVarint32(aKey, tnum);

  aToken = &aKey[nTnum+1];
  nToken = sqlite4Strlen30((const char *)aToken);
  aPk = &aToken[nToken+1];
  nPk = (&aKey[nKey] - aPk);

  fts5InstanceListInit((u8 *)aVal, nVal, &sList);
  while( 0==fts5InstanceListNext(&sList) ){
    i64 v = fts5TermInstanceCksum(
        aPk, nPk, aToken, nToken, sList.iWeight, sList.iCol, sList.iOff
    );
    cksum = cksum ^ v;

  }

  *piCksum = cksum;
  return SQLITE4_OK;
}

typedef struct CksumCtx CksumCtx;
................................................................................
  int nPK;
  int iCol;
  i64 cksum;
};

static int fts5CksumCb(
  void *pCtx, 
  int iWeight, 
  int iOff,
  const char *zToken, 
  int nToken, 
  int iSrc, 
  int nSrc
){
  CksumCtx *p = (CksumCtx *)pCtx;
  i64 cksum;

  cksum = fts5TermInstanceCksum(p->pPK, p->nPK, 
      (const u8 *)zToken, nToken, iWeight, p->iCol, iOff
  );

  p->cksum = (p->cksum ^ cksum);
  return 0;
}

int sqlite4Fts5RowCksum(
................................................................................
      fts5InstanceListNext(&in2);
    }else if( in1.iCol<in2.iCol || (in1.iCol==in2.iCol && in1.iOff<in2.iOff) ){
      pAdv = &in1;
    }else{
      pAdv = &in2;
    }

    fts5InstanceListAppend(&out, pAdv->iCol, pAdv->iWeight, pAdv->iOff);
    fts5InstanceListNext(pAdv);
  }

  if( bFree ){
    sqlite4DbFree(db, p1->aData);
    sqlite4DbFree(db, p2->aData);
  }
................................................................................
/*
** Open a cursor for each token in the expression.
*/
static int fts5OpenCursors(sqlite4 *db, Fts5Info *pInfo, Fts5Cursor *pCsr){
  return fts5OpenExprCursors(db, pInfo, pCsr->pExpr->pRoot);
}

void sqlite4Fts5Close(sqlite4 *db, Fts5Cursor *pCsr){
  if( pCsr ){










    fts5ExpressionFree(db, pCsr->pExpr);

    sqlite4DbFree(db, pCsr->aKey);

    sqlite4DbFree(db, pCsr);
  }
}

static int fts5TokenAdvanceToMatch(
  InstanceList *p,
  InstanceList *pFirst,
................................................................................
      return 0;
    }
  }

  return (p->iCol==pFirst->iCol && p->iOff==iReq);
}

static int fts5StringFindInstances(Fts5Cursor *pCsr, int iCol, Fts5Str *pStr){
  sqlite4 *db = pCsr->db;
  int i;
  int rc = SQLITE4_OK;
  int bEof = 0;
  int nByte = sizeof(InstanceList) * pStr->nToken;
  InstanceList *aIn;
  InstanceList out;

................................................................................
  while( rc==SQLITE4_OK && bEof==0 ){
    for(i=1; i<pStr->nToken; i++){
      int bMatch = fts5TokenAdvanceToMatch(&aIn[i], &aIn[0], i, &bEof);
      if( bMatch==0 || bEof ) break;
    }
    if( i==pStr->nToken && (iCol<0 || aIn[0].iCol==iCol) ){
      /* Record a match here */
      fts5InstanceListAppend(&out, aIn[0].iCol, aIn[0].iWeight, aIn[0].iOff);
    }
    bEof = fts5InstanceListNext(&aIn[0]);
  }

  pStr->nList = out.iList;
  sqlite4DbFree(db, aIn);

................................................................................
  if( p1->iCol==p2->iCol && p1->iOff<p2->iOff && (p1->iOff+nNear)>=p2->iOff ){
    return 1;
  }
  return 0;
}

static int fts5StringNearTrim(
  Fts5Cursor *pCsr,               /* Cursor object that owns both strings */
  Fts5Str *pTrim,                 /* Trim this instance list */
  Fts5Str *pNext,                 /* According to this one */
  int nNear
){
  if( pNext->nList==0 ){
    pTrim->nList = 0;
  }else{
................................................................................

    while( bEof==0 ){
      if( fts5IsNear(&near, &in, nTrail) 
       || fts5IsNear(&in, &near, nLead)
      ){
        /* The current position is a match. Append an entry to the output
        ** and advance the input cursor. */
        fts5InstanceListAppend(&out, in.iCol, in.iWeight, in.iOff);
        bEof = fts5InstanceListNext(&in);
      }else{
        if( near.iCol<in.iCol || (near.iCol==in.iCol && near.iOff<in.iOff) ){
          bEof = fts5InstanceListNext(&near);
        }else if( near.iCol==in.iCol && near.iOff==in.iOff ){
          bEof = fts5InstanceListNext(&in);
          if( fts5IsNear(&near, &in, nTrail) ){
            fts5InstanceListAppend(&out, near.iCol, near.iWeight, near.iOff);
          }
        }else{
          bEof = fts5InstanceListNext(&in);
        }
      }
    }

................................................................................
** is set to true before returning.
**
** If the cursors do not point to a match, then *ppAdvance is set to
** the token of the individual cursor that should be advanced before
** retrying this function.
*/
static int fts5PhraseIsMatch(
  Fts5Cursor *pCsr,               /* Cursor that owns this string */
  Fts5Phrase *pPhrase,            /* Phrase to test */
  int *pbMatch,                   /* OUT: True for a match, false otherwise */
  Fts5Token **ppAdvance           /* OUT: Token to advance before retrying */
){
  const u8 *aPk1 = 0;
  int nPk1 = 0;
  int rc = SQLITE4_OK;
................................................................................

  /* At this point, it is established that all of the token cursors in the
  ** phrase point to an entry with the same primary key. Now figure out if
  ** the various string constraints are met. Along the way, synthesize a 
  ** position list for each Fts5Str object.  */
  for(i=0; rc==SQLITE4_OK && i<pPhrase->nStr; i++){
    Fts5Str *pStr = &pPhrase->aStr[i];
    rc = fts5StringFindInstances(pCsr, pPhrase->iCol, pStr);
  }

  /* Trim the instance lists according to any NEAR constraints.  */
  for(i=1; rc==SQLITE4_OK && i<pPhrase->nStr; i++){
    int n = pPhrase->aiNear[i-1];
    rc = fts5StringNearTrim(pCsr, &pPhrase->aStr[i], &pPhrase->aStr[i-1], n);
  }
  for(i=pPhrase->nStr-1; rc==SQLITE4_OK && i>0; i--){
    int n = pPhrase->aiNear[i-1];
    rc = fts5StringNearTrim(pCsr, &pPhrase->aStr[i-1], &pPhrase->aStr[i], n);
  }

  *pbMatch = (pPhrase->aStr[0].nList>0);
  return rc;
}

static int fts5PhraseAdvanceToMatch(Fts5Cursor *pCsr, Fts5Phrase *pPhrase){
  int rc;
  do {
    int bMatch;
    Fts5Token *pAdvance = 0;
    rc = fts5PhraseIsMatch(pCsr, pPhrase, &bMatch, &pAdvance);
    if( rc!=SQLITE4_OK || bMatch ) break;
    rc = fts5TokenAdvance(pCsr->db, pAdvance);
  }while( rc==SQLITE4_OK );
  return rc;
}

static int fts5ExprAdvance(Fts5Cursor *pCsr, Fts5ExprNode *p, int bFirst){
  int rc = SQLITE4_OK;

  switch( p->eType ){
    case TOKEN_PRIMITIVE: {
      Fts5Phrase *pPhrase = p->pPhrase;
      if( bFirst==0 ){
        rc = fts5TokenAdvance(pCsr->db, &pPhrase->aStr[0].aToken[0]);
      }
      if( rc==SQLITE4_OK ) rc = fts5PhraseAdvanceToMatch(pCsr, pPhrase);
      if( rc==SQLITE4_OK ){
        rc = fts5TokenPk(&pPhrase->aStr[0].aToken[0], &p->aPk, &p->nPk);
      }else{
        p->aPk = 0;
        p->nPk = 0;
        if( rc==SQLITE4_NOTFOUND ) rc = SQLITE4_OK;
      }
      break;
    }

    case TOKEN_AND:
      p->aPk = 0;
      p->nPk = 0;
      rc = fts5ExprAdvance(pCsr, p->pLeft, bFirst);
      if( rc==SQLITE4_OK ) rc = fts5ExprAdvance(pCsr, p->pRight, bFirst);
      while( rc==SQLITE4_OK && p->pLeft->aPk && p->pRight->aPk ){
        int res = fts5KeyCompare(
            p->pLeft->aPk, p->pLeft->nPk, p->pRight->aPk, p->pRight->nPk
        );
        if( res<0 ){
          rc = fts5ExprAdvance(pCsr, p->pLeft, 0);
        }else if( res>0 ){
          rc = fts5ExprAdvance(pCsr, p->pRight, 0);
        }else{
          p->aPk = p->pLeft->aPk;
          p->nPk = p->pLeft->nPk;
          break;
        }
      }
      break;
................................................................................
      int res = 0;
      if( bFirst==0 ){
        res = fts5KeyCompare(
            p->pLeft->aPk, p->pLeft->nPk, p->pRight->aPk, p->pRight->nPk
        );
      }
        
      if( res<=0 ) rc = fts5ExprAdvance(pCsr, p->pLeft, bFirst);
      if( rc==SQLITE4_OK && res>=0 ){
        rc = fts5ExprAdvance(pCsr, p->pRight, bFirst);
      }

      res = fts5KeyCompare(
          p->pLeft->aPk, p->pLeft->nPk, p->pRight->aPk, p->pRight->nPk
      );
      if( res>0 ){
        p->aPk = p->pRight->aPk;
................................................................................


    default: assert( p->eType==TOKEN_NOT );

      p->aPk = 0;
      p->nPk = 0;

      rc = fts5ExprAdvance(pCsr, p->pLeft, bFirst);
      if( bFirst && rc==SQLITE4_OK ){
        rc = fts5ExprAdvance(pCsr, p->pRight, bFirst);
      }

      while( rc==SQLITE4_OK && p->pLeft->aPk && p->pRight->aPk ){
        int res = fts5KeyCompare(
            p->pLeft->aPk, p->pLeft->nPk, p->pRight->aPk, p->pRight->nPk
        );
        if( res<0 ){
          break;
        }else if( res>0 ){
          rc = fts5ExprAdvance(pCsr, p->pRight, 0);
        }else{
          rc = fts5ExprAdvance(pCsr, p->pLeft, 0);
        }
      }

      p->aPk = p->pLeft->aPk;
      p->nPk = p->pLeft->nPk;
      break;
  }

  assert( rc!=SQLITE4_NOTFOUND );
  return rc;
}

int sqlite4Fts5Next(Fts5Cursor *pCsr){



  return fts5ExprAdvance(pCsr, pCsr->pExpr->pRoot, 0);
}

int sqlite4Fts5Open(
  sqlite4 *db,                    /* Database handle */
  Fts5Info *pInfo,                /* Index description */
  const char *zMatch,             /* Match expression */
  int bDesc,                      /* True to iterate in desc. order of PK */
  Fts5Cursor **ppCsr,             /* OUT: New FTS cursor object */
  char **pzErr                    /* OUT: Error message */
){
  int rc = SQLITE4_OK;
  Fts5Cursor *pCsr;


  pCsr = sqlite4DbMallocZero(db, sizeof(Fts5Cursor));

  if( !pCsr ){
    rc = SQLITE4_NOMEM;
  }else{


    pCsr->pInfo = pInfo;
    pCsr->db = db;
    rc = fts5ParseExpression(db, pInfo->pTokenizer, pInfo->p, 
        pInfo->iRoot, pInfo->azCol, pInfo->nCol, zMatch, &pCsr->pExpr, pzErr
    );
  }

  if( rc==SQLITE4_OK ){
    /* Open a KV cursor for each term in the expression. Set each cursor
    ** to point to the first entry in the range it will scan.  */
    rc = fts5OpenCursors(db, pInfo, pCsr);
  }
  if( rc!=SQLITE4_OK ){
    sqlite4Fts5Close(db, pCsr);
    pCsr = 0;
  }else{
    rc = fts5ExprAdvance(pCsr, pCsr->pExpr->pRoot, 1);
  }
  *ppCsr = pCsr;
  return rc;
}

/*
** Return true if the cursor passed as the second argument currently points
................................................................................
*/
int sqlite4Fts5Valid(Fts5Cursor *pCsr){
  return( pCsr->pExpr->pRoot->aPk!=0 );
}

int sqlite4Fts5Pk(
  Fts5Cursor *pCsr, 
  int iTbl, 
  KVByteArray **paKey, 
  KVSize *pnKey
){
  int i;
  int nReq;
  const u8 *aPk;
  int nPk;

................................................................................
  i = putVarint32(pCsr->aKey, iTbl);
  memcpy(&pCsr->aKey[i], aPk, nPk);

  *paKey = pCsr->aKey;
  *pnKey = nReq;
  return SQLITE4_OK;
}































































































































































































































































































































































































































































































































/**************************************************************************
***************************************************************************
** Below this point is test code.
*/
#ifdef SQLITE4_TEST
static int fts5PrintExprNode(sqlite4 *, const char **, Fts5ExprNode *, char **);







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







 







|




>




>







 







|
>
>









<
>


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













|


>
>
>
>
>
>
>
>
>
>
>







 







|







 







|











|
|
|







 







|







 







|







 







>







 







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







 







>







 







>







 







>
>
>
>
>
>
>
>
>
>
>




|
|
|







 







>







 







>


>
>



|







 







|







>



>
>


>
>
>
>
>
>
>
>
>
>
>







 







|
|

|







 







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







 







<
<


>
>
>






<
>
>

<
>







 







|
>






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






>
>







 







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







 







>







 







|







 







|







 







<







>
|
|
|
|

|
|
|
|
|
|
>







 







|










|







 







|







 







|

>
>
>
>
>
>
>
>
>
>

>

>







 







|
<







 







|







 







<







 







|







|







 







|







 







|





|



|






|




|

|




|






|

|













|
|





|

|







 







|

|







 







|

|









|

|













>
>
>
|












>

|
>



>
>













|


|







 







|
|







 







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







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
...
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
...
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
...
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
...
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
...
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
...
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
...
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
...
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
...
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
...
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
...
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
....
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
....
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
....
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
....
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
....
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
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
1436
1437
1438
1439
1440
1441
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
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
....
1488
1489
1490
1491
1492
1493
1494


1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505

1506
1507
1508

1509
1510
1511
1512
1513
1514
1515
1516
....
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
....
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
....
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
....
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
....
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
....
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
....
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
....
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
....
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
....
2292
2293
2294
2295
2296
2297
2298
2299

2300
2301
2302
2303
2304
2305
2306
....
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
....
2354
2355
2356
2357
2358
2359
2360

2361
2362
2363
2364
2365
2366
2367
....
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
....
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
....
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
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
....
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
....
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
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
....
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
....
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
2778
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
3038
3039
3040
3041
3042
3043
3044
3045
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
3074
3075
3076
3077
3078
3079
3080
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183
3184
3185
3186
3187
3188
3189
**
*************************************************************************
*/

#include "sqliteInt.h"
#include "vdbeInt.h"

/* 
** Stream numbers must be lower than this.
**
** For optimization purposes, it is assumed that a given tokenizer uses
** a set of contiguous stream numbers starting with 0. And that most
** tokens belong to stream 0.
**
** The hard limit is 63 (due to the format of "row size" records).
*/
#define SQLITE4_FTS5_NSTREAM 32

/*
** Records stored within the index:
**
** Row size record:
**   There is one "row size" record in the index for each row in the
**   indexed table. The "row size" record contains the number of tokens
**   in the associated row for each combination of a stream and column
**   number (i.e. contains the data required to find the number of
**   tokens associated with stream S present in column C of the row for
**   all S and C).
**
**   The key for the row size record is a single 0x00 byte followed by
**   a copy of the PK blob for the table row. 
**
**   The value is a series of varints. Each column of the table is
**   represented by one or more varints packed into the array.
**
**   If a column contains only stream 0 tokens, then it is represented
**   by a single varint - (nToken << 1), where nToken is the number of
**   stream 0 tokens stored in the column.
**
**   Or, if the column contains tokens from multiple streams, the first
**   varint contains a bitmask indicating which of the streams are present
**   (stored as ((bitmask << 1) | 0x01)). Following the bitmask is a
**   varint containing the number of tokens for each stream present, in
**   ascending order of stream number.
**
**   TODO: The format above is not currently implemented! Instead, there
**   is a simpler place-holder format (which consumes more space).
**
** Global size record:
**   There is a single "global size" record stored in the database. The
**   database key for this record is a single byte - 0x00.
**
**   The data for this record is a series of varint values. The first 
**   varint is the total number of rows in the table. The subsequent
**   varints make up a "row size" record containing the total number of
**   tokens for each S/C combination in all rows of the table.
**
** FTS index records:
**   The FTS index records implement the following mapping:
**
**       (token, document-pk) -> (list of instances)
**
**   The key for each index record is in the same format as the keys for
**   regular text indexes. An 0x24 byte, followed by the utf-8 representation
**   of the token, followed by 0x00, followed by the PK blob for the table
**   row.
**
**   TODO: Describe value format.
*/

/*
** Default distance value for NEAR operators.
*/
#define FTS5_DEFAULT_NEAR 10

/*
** Token types used by expression parser.
................................................................................
**   expr := expr NOT expr
**   expr := expr AND expr
**   expr := expr OR  expr
**   expr := LP expr RP
*/

/*
** Structure types used by this module.
*/
typedef struct Fts5Expr Fts5Expr;
typedef struct Fts5ExprNode Fts5ExprNode;
typedef struct Fts5List Fts5List;
typedef struct Fts5MatchIter Fts5MatchIter;
typedef struct Fts5Parser Fts5Parser;
typedef struct Fts5ParserToken Fts5ParserToken;
typedef struct Fts5Phrase Fts5Phrase;
typedef struct Fts5Prefix Fts5Prefix;
typedef struct Fts5Size Fts5Size;
typedef struct Fts5Str Fts5Str;
typedef struct Fts5Token Fts5Token;


struct Fts5ParserToken {
  int eType;                      /* Token type */
  int n;                          /* Size of z[] in bytes */
................................................................................
  Fts5ExprNode *pLeft;
  Fts5ExprNode *pRight;
  const u8 *aPk;                  /* Primary key of current entry (or null) */
  int nPk;                        /* Size of aPk[] in bytes */
};

struct Fts5Expr {
  Fts5ExprNode *pRoot;            /* Root node of expression */
  int nPhrase;                    /* Number of Fts5Str objects in query */
  Fts5Str **apPhrase;             /* All Fts5Str objects */
};

/*
** FTS5 specific cursor data.
*/
struct Fts5Cursor {
  sqlite4 *db;
  Fts5Info *pInfo;
  Fts5Expr *pExpr;                /* MATCH expression for this cursor */

  char *zExpr;                    /* Full text of MATCH expression */
  KVByteArray *aKey;              /* Buffer for primary key */
  int nKeyAlloc;                  /* Bytes allocated at aKey[] */

  KVCursor *pCsr;                 /* Cursor used to retrive values */
  Mem *aMem;                      /* Array of column values */
  int bMemValid;                  /* True if contents of aMem[] are valid */

  Fts5Size *pSz;                  /* Local size data */
  Fts5Size *pGlobal;              /* Global size data */
  i64 nGlobal;                    /* Total number of rows in table */
  int *anRow;

  Fts5MatchIter *pIter;           /* Used by mi_match_detail() */
};

/*
** A deserialized 'size record' (see above).
*/
struct Fts5Size {
  int nCol;                       /* Number of columns in indexed table */
  int nStream;                    /* Number of streams */
  i64 *aSz;                       /* Token count for each C/S */
};

/*
** This type is used when reading (decoding) an instance-list.
*/
typedef struct InstanceList InstanceList;
struct InstanceList {
  u8 *aList;
  int nList;
  int iList;

  /* The current entry */
  int iCol;
  int iStream;
  int iOff;
};

/*
** An instance of this structure is used by the sqlite4_mi_match_detail()
** API to iterate through matches. 
*/
struct Fts5MatchIter {
  int bValid;                     /* True if aList[] is current row */
  int iCurrent;                   /* Current index in aList[] (or -1) */
  int iMatch;                     /* Current iMatch value */
  InstanceList *aList;            /* One iterator for each phrase in expr */
};

/*
** Return true for EOF, or false if the next entry is valid.
*/
static int fts5InstanceListNext(InstanceList *p){
  int i = p->iList;
  int bRet = 1;
................................................................................
    u32 iVal;
    i += getVarint32(&p->aList[i], iVal);
    if( (iVal & 0x03)==0x01 ){
      p->iCol = (iVal>>2);
      p->iOff = 0;
    }
    else if( (iVal & 0x03)==0x03 ){
      p->iStream = (iVal>>2);
    }
    else{
      p->iOff += (iVal>>1);
      bRet = 0;
    }
  }
  if( bRet ){
................................................................................
static int fts5InstanceListEof(InstanceList *p){
  return (p->aList==0);
}

static void fts5InstanceListAppend(
  InstanceList *p,                /* Instance list to append to */
  int iCol,                       /* Column of new entry */
  int iStream,                    /* Weight of new entry */
  int iOff                        /* Offset of new entry */
){
  assert( iCol>=p->iCol );
  assert( iCol>p->iCol || iOff>=p->iOff );

  if( iCol!=p->iCol ){
    p->iList += putVarint32(&p->aList[p->iList], (iCol<<2)|0x01);
    p->iCol = iCol;
    p->iOff = 0;
  }

  if( iStream!=p->iStream ){
    p->iList += putVarint32(&p->aList[p->iList], (iStream<<2)|0x03);
    p->iStream = iStream;
  }

  p->iList += putVarint32(&p->aList[p->iList], (iOff-p->iOff)<<1);
  p->iOff = iOff;

  assert( p->iList<=p->nList );
}
................................................................................
}

/*
** Callback for fts5CountTokens().
*/
static int fts5CountTokensCb(
  void *pCtx, 
  int iStream, 
  int iOff, 
  const char *z, int n,
  int iSrc, int nSrc
){
  (*((int *)pCtx))++;
  return 0;
}
................................................................................
struct AppendTokensCtx {
  Fts5Parser *pParse;
  Fts5Str *pStr;
};

static int fts5AppendTokensCb(
  void *pCtx, 
  int iStream, 
  int iOff, 
  const char *z, int n, 
  int iSrc, int nSrc
){
  struct AppendTokensCtx *p = (struct AppendTokensCtx *)pCtx;
  Fts5Parser *pParse = p->pParse;
  Fts5Token *pToken;
................................................................................
    sqlite4DbFree(db, pNode);
  }
}

static void fts5ExpressionFree(sqlite4 *db, Fts5Expr *pExpr){
  if( pExpr ){
    fts5FreeExprNode(db, pExpr->pRoot);
    sqlite4DbFree(db, pExpr->apPhrase);
    sqlite4DbFree(db, pExpr);
  }
}

typedef struct ExprHier ExprHier;
struct ExprHier {
  Fts5ExprNode **ppNode;
................................................................................
  *pp = pNode;
  (*paHier)[*pnHier].ppNode = &pNode->pRight;
  (*paHier)[*pnHier].nOpen = 0;
  (*pnHier)++;

  return SQLITE4_OK;
}

static void fts5FindStrings(Fts5ExprNode *p, Fts5Str ***papStr){
  if( p ){
    if( p->eType==TOKEN_PRIMITIVE ){
      int i;
      Fts5Str *aStr = p->pPhrase->aStr;
      for(i=0; i<p->pPhrase->nStr; i++){
        **papStr = &aStr[i];
        (*papStr)++;
      }
    }
    fts5FindStrings(p->pLeft, papStr);
    fts5FindStrings(p->pRight, papStr);
  }
}

static int fts5ParseExpression(
  sqlite4 *db,                    /* Database handle */
  Fts5Tokenizer *pTokenizer,      /* Tokenizer module */
  sqlite4_tokenizer *p,           /* Tokenizer instance */
  int iRoot,                      /* Root page number of FTS index */
  char **azCol,                   /* Array of column names (nul-term'd) */
................................................................................
  int nCol,                       /* Size of array azCol[] */
  const char *zExpr,              /* FTS expression text */
  Fts5Expr **ppExpr,              /* OUT: Expression object */
  char **pzErr                    /* OUT: Error message */
){
  int rc = SQLITE4_OK;
  Fts5Parser sParse;
  int nStr = 0;
  int nExpr;
  int i;
  Fts5Expr *pExpr;

  int nHier = 0;
  int nHierAlloc = 0;
  ExprHier *aHier = 0;
................................................................................
            rc = SQLITE4_NOMEM;
          }else{
            pNode->eType = TOKEN_PRIMITIVE;
            pNode->pPhrase = pPhrase;
            *pp = pNode;
          }
        }
        nStr += pPhrase->nStr;
        break;
      }

      case TOKEN_AND:
      case TOKEN_OR:
      case TOKEN_NOT: {
        Fts5ExprNode **pp = aHier[nHier-1].ppNode;
................................................................................

  if( rc==SQLITE4_OK && *aHier[nHier-1].ppNode==0 ){
    rc = SQLITE4_ERROR;
  }
  for(i=0; rc==SQLITE4_OK && i<nHier; i++){
    if( aHier[i].nOpen>0 ) rc = SQLITE4_ERROR;
  }

  if( rc==SQLITE4_OK ){
    pExpr->nPhrase = nStr;
    pExpr->apPhrase = (Fts5Str**)sqlite4DbMallocZero(db, sizeof(Fts5Str*)*nStr);
    if( pExpr->apPhrase==0 ){
      rc = SQLITE4_NOMEM;
    }else{
      Fts5Str **a = pExpr->apPhrase;
      fts5FindStrings(pExpr->pRoot, &a);
    }
  }

  if( rc!=SQLITE4_OK ){
    fts5ExpressionFree(db, pExpr);
    *pzErr = sParse.zErr;
    pExpr = 0;
  }
  *ppExpr = pExpr;
  sqlite4DbFree(db, aHier);
  return rc;
}

/*
** Search for the Fts5Tokenizer object named zName. Return a pointer to it
** if it exists, or NULL otherwise.
................................................................................
          ExprListItem *pItem = &pArgs->a[j];
          if( pItem->zName ) break;
          nByte += sqlite4Strlen30(pItem->pExpr->u.zToken) + 1;
        }
        nByte += sizeof(char *) * (j-i);
        pFts->azTokenizer = (char **)sqlite4DbMallocZero(pParse->db, nByte);
        if( pFts->azTokenizer==0 ) return;
        pFts->nTokenizer = (j-i);

        pSpace = (char *)&pFts->azTokenizer[j-i];
        for(j=i; j<pArgs->nExpr; j++){
          ExprListItem *pItem = &pArgs->a[j];
          if( pItem->zName && j>i ){
            break;
          }else{
................................................................................
** sqlite4DbRealloc().
*/
typedef struct TokenizeCtx TokenizeCtx;
typedef struct TokenizeTerm TokenizeTerm;
struct TokenizeCtx {
  int rc;
  int iCol;
  int nCol;                       /* Number of columns in table */
  sqlite4 *db;
  int nMax;
  i64 *aSz;                       /* Number of tokens in each column/stream */
  int nStream;                    /* Number of streams in document */
  Hash hash;
};
struct TokenizeTerm {
  int iStream;                    /* Weight of previous entry */
  int iCol;                       /* Column containing previous entry */
  int iOff;                       /* Token offset of previous entry */
  int nToken;                     /* Size of token in bytes */
  int nData;                      /* Bytes of data in value */
  int nAlloc;                     /* Bytes of data allocated */
};

................................................................................
  a = &(((unsigned char *)&pTerm[1])[pTerm->nToken+pTerm->nData]);
  pTerm->nData += putVarint32(a, iVal);
  return pTerm;
}

static int fts5TokenizeCb(
  void *pCtx, 
  int iStream, 
  int iOff,
  const char *zToken, 
  int nToken, 
  int iSrc, 
  int nSrc
){
  TokenizeCtx *p = (TokenizeCtx *)pCtx;
  sqlite4 *db = p->db;
  TokenizeTerm *pTerm = 0;
  TokenizeTerm *pOrig = 0;

  /* TODO: Error here if iStream is out of range */

  if( nToken>p->nMax ) p->nMax = nToken;

  if( iStream>=p->nStream ){
    int nOld = p->nStream;
    int nNew = 4;
    while( nNew<=iStream ) nNew = nNew*2;
    p->aSz = (i64*)sqlite4DbReallocOrFree(db, p->aSz, nNew*p->nCol*sizeof(i64));
    if( p->aSz==0 ) goto tokenize_cb_out;
    memset(&p->aSz[nOld * p->nCol], 0, (nNew-nOld)*p->nCol*sizeof(i64));
    p->nStream = nNew;
  }
  p->aSz[iStream*p->nCol + p->iCol]++;

  pTerm = (TokenizeTerm *)sqlite4HashFind(&p->hash, zToken, nToken);
  if( pTerm==0 ){
    /* Size the initial allocation so that it fits in the lookaside buffer */
    int nAlloc = sizeof(TokenizeTerm) + nToken + 32;

    pTerm = sqlite4DbMallocZero(p->db, nAlloc);
    if( pTerm ){
................................................................................
        pTerm = 0;
      }
      if( pTerm==0 ) goto tokenize_cb_out;
    }
  }
  pOrig = pTerm;

  if( iStream!=pTerm->iStream ){
    pTerm = fts5TokenizeAppendInt(p, pTerm, (iStream << 2) | 0x00000003);
    if( !pTerm ) goto tokenize_cb_out;
    pTerm->iStream = iStream;
  }

  if( pTerm && p->iCol!=pTerm->iCol ){
    pTerm = fts5TokenizeAppendInt(p, pTerm, (p->iCol << 2) | 0x00000001);
    if( !pTerm ) goto tokenize_cb_out;
    pTerm->iCol = p->iCol;
    pTerm->iOff = 0;
................................................................................
  if( !pTerm ){
    p->rc = SQLITE4_NOMEM;
    return 1;
  }

  return 0;
}

static int fts5LoadSizeRecord(
  sqlite4 *db,                    /* Database handle */
  u8 *aKey, int nKey,             /* KVStore key */
  int nMinStream,                 /* Space for at least this many streams */
  Fts5Info *pInfo,                /* Info record */
  i64 *pnRow,                     /* non-NULL when reading global record */
  Fts5Size **ppSz                 /* OUT: Loaded size record */
){
  Fts5Size *pSz = 0;              /* Size object */
  KVCursor *pCsr = 0;             /* Cursor used to read global record */
  int rc;

  rc = sqlite4KVStoreOpenCursor(db->aDb[pInfo->iDb].pKV, &pCsr);
  if( rc==SQLITE4_OK ){
    rc = sqlite4KVCursorSeek(pCsr, aKey, nKey, 0);
    if( rc==SQLITE4_NOTFOUND ){
      if( pnRow ){
        int nByte = sizeof(Fts5Size) + sizeof(i64) * pInfo->nCol * nMinStream;
        pSz = sqlite4DbMallocZero(db, nByte);
        if( pSz==0 ){
          rc = SQLITE4_NOMEM;
        }else{
          pSz->aSz = (i64 *)&pSz[1];
          pSz->nStream = nMinStream;
          pSz->nCol = pInfo->nCol;
          *pnRow = 0;
          rc = SQLITE4_OK;
        }
      }else{
        rc = SQLITE4_CORRUPT_BKPT;
      }
    }else if( rc==SQLITE4_OK ){
      const u8 *aData = 0;
      int nData = 0;
      rc = sqlite4KVCursorData(pCsr, 0, -1, &aData, &nData);
      if( rc==SQLITE4_OK ){
        int iOff = 0;
        int nStream = 0;
        int nAlloc;

        /* If pnRow is not NULL, then this is the global record. Read the
        ** number of documents in the table from the start of the record. */
        if( pnRow ){
          iOff += sqlite4GetVarint(&aData[iOff], (u64 *)pnRow);
        }
        iOff += getVarint32(&aData[iOff], nStream);
        nAlloc = (nStream < nMinStream ? nMinStream : nStream);

        pSz = sqlite4DbMallocZero(db, 
            sizeof(Fts5Size) + sizeof(i64) * pInfo->nCol * nAlloc
        );
        if( pSz==0 ){
          rc = SQLITE4_NOMEM;
        }else{
          int iCol = 0;
          pSz->aSz = (i64 *)&pSz[1];
          pSz->nCol = pInfo->nCol;
          pSz->nStream = nAlloc;
          while( iOff<nData ){
            int i;
            i64 *aSz = &pSz->aSz[iCol*nAlloc];
            for(i=0; i<nStream; i++){
              iOff += sqlite4GetVarint(&aData[iOff], (u64*)&aSz[i]);
            }
            iCol++;
          }
        }
      }
    }
    sqlite4KVCursorClose(pCsr);
  }

  *ppSz = pSz;
  return rc;
}

static int fts5StoreSizeRecord(
  KVStore *p,
  u8 *aKey, int nKey,
  Fts5Size *pSz, 
  i64 nRow, 
  u8 *a                           /* Space to serialize record in */
){
  int iOff = 0;
  int iCol;

  if( nRow>=0 ){
    iOff += sqlite4PutVarint(&a[iOff], nRow);
  }
  iOff += sqlite4PutVarint(&a[iOff], pSz->nStream);

  for(iCol=0; iCol<pSz->nCol; iCol++){
    int i;
    for(i=0; i<pSz->nStream; i++){
      iOff += sqlite4PutVarint(&a[iOff], pSz->aSz[i*pSz->nCol+iCol]);
    }
  }

  return sqlite4KVStoreReplace(p, aKey, nKey, a, iOff);
}

static int fts5CsrLoadGlobal(Fts5Cursor *pCsr){
  int rc = SQLITE4_OK;
  if( pCsr->pGlobal==0 ){
    int nKey;
    u8 aKey[10];
    nKey = putVarint32(aKey, pCsr->pInfo->iRoot);
    aKey[nKey++] = 0x00;
    rc = fts5LoadSizeRecord(
        pCsr->db, aKey, nKey, 0, pCsr->pInfo, &pCsr->nGlobal, &pCsr->pGlobal
    );
  }
  return rc;
}

static int fts5CsrLoadSz(Fts5Cursor *pCsr){
  int rc = SQLITE4_OK;
  if( pCsr->pSz==0 ){
    sqlite4 *db = pCsr->db;
    Fts5Info *pInfo = pCsr->pInfo;
    u8 *aKey;
    int nKey = 0;
    int nPk = pCsr->pExpr->pRoot->nPk;

    aKey = (u8 *)sqlite4DbMallocZero(db, 10 + nPk);
    if( !aKey ) return SQLITE4_NOMEM;

    nKey = putVarint32(aKey, pInfo->iRoot);
    aKey[nKey++] = 0x00;
    memcpy(&aKey[nKey], pCsr->pExpr->pRoot->aPk, nPk);
    nKey += nPk;

    rc = fts5LoadSizeRecord(pCsr->db, aKey, nKey, 0, pInfo, 0, &pCsr->pSz);
    sqlite4DbFree(db, aKey);
  }

  return rc;
}


/*
** Update an fts index.
*/
int sqlite4Fts5Update(
  sqlite4 *db,                    /* Database handle */
  Fts5Info *pInfo,                /* Description of fts index to update */
................................................................................
  int bDel,                       /* True for a delete, false for insert */
  char **pzErr                    /* OUT: Error message */
){
  int i;
  int rc = SQLITE4_OK;
  KVStore *pStore;
  TokenizeCtx sCtx;


  int nTnum = 0;
  u32 dummy = 0;

  u8 *aSpace = 0;
  int nSpace = 0;

  const u8 *pPK;
  int nPK;
  HashElem *pElem;

  pStore = db->aDb[pInfo->iDb].pKV;


  memset(&sCtx, 0, sizeof(sCtx));
  sCtx.db = db;

  sCtx.nCol = pInfo->nCol;
  sqlite4HashInit(db->pEnv, &sCtx.hash, 1);

  pPK = (const u8 *)sqlite4_value_blob(pKey);
  nPK = sqlite4_value_bytes(pKey);
  
  nTnum = getVarint32(pPK, dummy);
  nPK -= nTnum;
................................................................................
  for(i=0; rc==SQLITE4_OK && i<pInfo->nCol; i++){
    sqlite4_value *pArg = (sqlite4_value *)(&aArg[i]);
    if( pArg->flags & MEM_Str ){
      const char *zText;
      int nText;

      zText = (const char *)sqlite4_value_text(pArg);
      nText = sqlite4_value_bytes(pArg); 
      sCtx.iCol = i;
      rc = pInfo->pTokenizer->xTokenize(
          &sCtx, pInfo->p, zText, nText, fts5TokenizeCb
      );
    }
  }

  /* Allocate enough space to serialize all the stuff that needs to
  ** be inserted into the database. Specifically:
  **
  **   * Space for index record keys,
  **   * space for the size record and key for this document, and
  **   * space for the updated global size record for the document set.
  **
  ** To make it easier, the below allocates enough space to simultaneously
  ** store the largest index record key and the largest possible global
  ** size record.
  */
  nSpace = (sqlite4VarintLen(pInfo->iRoot) + 2 + sCtx.nMax + nPK) + 
           (9 * (2 + pInfo->nCol * sCtx.nStream));
  aSpace = sqlite4DbMallocRaw(db, nSpace);
  if( aSpace==0 ) rc = SQLITE4_NOMEM;

  for(pElem=sqliteHashFirst(&sCtx.hash); pElem; pElem=sqliteHashNext(pElem)){
    TokenizeTerm *pTerm = (TokenizeTerm *)sqliteHashData(pElem);
    if( rc==SQLITE4_OK ){
      int nToken = sqliteHashKeysize(pElem);
      char *zToken = (char *)sqliteHashKey(pElem);
      u8 *aKey = aSpace;
      int nKey;

      nKey = putVarint32(aKey, pInfo->iRoot);
      aKey[nKey++] = 0x24;
      memcpy(&aKey[nKey], zToken, nToken);
      nKey += nToken;
      aKey[nKey++] = 0x00;
      memcpy(&aKey[nKey], pPK, nPK);
................................................................................
        const KVByteArray *aData = (const KVByteArray *)&pTerm[1];
        aData += pTerm->nToken;
        rc = sqlite4KVStoreReplace(pStore, aKey, nKey, aData, pTerm->nData);
      }
    }
    sqlite4DbFree(db, pTerm);
  }

  /* Write the size record into the db */
  if( rc==SQLITE4_OK ){
    u8 *aKey = aSpace;
    int nKey;

    nKey = putVarint32(aKey, pInfo->iRoot);
    aKey[nKey++] = 0x00;
    memcpy(&aKey[nKey], pPK, nPK);
    nKey += nPK;

    if( bDel==0 ){
      Fts5Size sSz;
      sSz.nCol = pInfo->nCol;
      sSz.nStream = sCtx.nStream;
      sSz.aSz = sCtx.aSz;
      rc = fts5StoreSizeRecord(pStore, aKey, nKey, &sSz, -1, &aKey[nKey]);
    }else{
      rc = sqlite4KVStoreReplace(pStore, aKey, nKey, 0, -1);
    }
  }

  /* Update the global record */
  if( rc==SQLITE4_OK ){
    Fts5Size *pSz;                /* Deserialized global size record */
    i64 nRow;                     /* Number of rows in indexed table */
    u8 *aKey = aSpace;            /* Space to format the global record key */
    int nKey;                     /* Size of global record key in bytes */

    nKey = putVarint32(aKey, pInfo->iRoot);
    aKey[nKey++] = 0x00;
    rc = fts5LoadSizeRecord(db, aKey, nKey, sCtx.nStream, pInfo, &nRow, &pSz);
    assert( rc!=SQLITE4_OK || pSz->nStream>=sCtx.nStream );

    if( rc==SQLITE4_OK ){
      int iCol;
      for(iCol=0; iCol<pSz->nCol; iCol++){
        int iStr;
        i64 *aIn = &sCtx.aSz[iCol * sCtx.nStream];
        i64 *aOut = &pSz->aSz[iCol * pSz->nStream];
        for(iStr=0; iStr<sCtx.nStream; iStr++){
          aOut[iStr] += (aIn[iStr] * (bDel?-1:1));
        }
      }
      nRow += (bDel?-1:1);
      rc = fts5StoreSizeRecord(pStore, aKey, nKey, pSz, nRow, &aKey[nKey]);
    }

    sqlite4DbFree(db, pSz);
  }
  
  sqlite4DbFree(db, aSpace);
  sqlite4DbFree(db, sCtx.aSz);
  sqlite4HashClear(&sCtx.hash);
  return rc;
}

static Fts5Info *fts5InfoCreate(Parse *pParse, Index *pIdx, int bCol){
  sqlite4 *db = pParse->db;
  Fts5Info *pInfo;                /* p4 argument for FtsUpdate opcode */
................................................................................
    nByte += nCol * sizeof(char *);
  }

  pInfo = sqlite4DbMallocZero(db, nByte);
  if( pInfo ){
    pInfo->iDb = sqlite4SchemaToIndex(db, pIdx->pSchema);
    pInfo->iRoot = pIdx->tnum;
    pInfo->iTbl = sqlite4FindPrimaryKey(pIdx->pTable, 0)->tnum;
    pInfo->nCol = pIdx->pTable->nCol;
    fts5TokenizerCreate(pParse, pIdx->pFts, &pInfo->pTokenizer, &pInfo->p);

    if( pInfo->p==0 ){
      assert( pParse->nErr );
      sqlite4DbFree(db, pInfo);
      pInfo = 0;
................................................................................
**   * the weight assigned to the instance,
**   * the column number, and
**   * the term offset.
*/
static i64 fts5TermInstanceCksum(
  const u8 *aTerm, int nTerm,
  const u8 *aPk, int nPk,
  int iStream,
  int iCol,
  int iOff
){
  int i;
  i64 cksum = 0;

  /* Add the term to the checksum */
................................................................................

  /* Add the primary key blob to the checksum */
  for(i=0; i<nPk; i++){
    cksum += (cksum << 3) + aPk[i];
  }

  /* Add the weight, column number and offset (in that order) to the checksum */
  cksum += (cksum << 3) + iStream;
  cksum += (cksum << 3) + iCol;
  cksum += (cksum << 3) + iOff;

  return cksum;
}


................................................................................
  u8 const *aVal; int nVal;       /* List of token instances */
  u8 const *aToken; int nToken;   /* Token for this entry */
  u8 const *aPk; int nPk;         /* Entry primary key blob */
  InstanceList sList;             /* Used to iterate through pVal */
  int nTnum;
  u32 tnum;


  aKey = (const u8 *)sqlite4_value_blob(pKey);
  nKey = sqlite4_value_bytes(pKey);
  aVal = (const u8 *)sqlite4_value_blob(pVal);
  nVal = sqlite4_value_bytes(pVal);

  /* Find the token and primary key blobs for this entry. */
  nTnum = getVarint32(aKey, tnum);
  if( aKey[nTnum]!=0 ){
    aToken = &aKey[nTnum+1];
    nToken = sqlite4Strlen30((const char *)aToken);
    aPk = &aToken[nToken+1];
    nPk = (&aKey[nKey] - aPk);

    fts5InstanceListInit((u8 *)aVal, nVal, &sList);
    while( 0==fts5InstanceListNext(&sList) ){
      i64 v = fts5TermInstanceCksum(
          aPk, nPk, aToken, nToken, sList.iStream, sList.iCol, sList.iOff
          );
      cksum = cksum ^ v;
    }
  }

  *piCksum = cksum;
  return SQLITE4_OK;
}

typedef struct CksumCtx CksumCtx;
................................................................................
  int nPK;
  int iCol;
  i64 cksum;
};

static int fts5CksumCb(
  void *pCtx, 
  int iStream, 
  int iOff,
  const char *zToken, 
  int nToken, 
  int iSrc, 
  int nSrc
){
  CksumCtx *p = (CksumCtx *)pCtx;
  i64 cksum;

  cksum = fts5TermInstanceCksum(p->pPK, p->nPK, 
      (const u8 *)zToken, nToken, iStream, p->iCol, iOff
  );

  p->cksum = (p->cksum ^ cksum);
  return 0;
}

int sqlite4Fts5RowCksum(
................................................................................
      fts5InstanceListNext(&in2);
    }else if( in1.iCol<in2.iCol || (in1.iCol==in2.iCol && in1.iOff<in2.iOff) ){
      pAdv = &in1;
    }else{
      pAdv = &in2;
    }

    fts5InstanceListAppend(&out, pAdv->iCol, pAdv->iStream, pAdv->iOff);
    fts5InstanceListNext(pAdv);
  }

  if( bFree ){
    sqlite4DbFree(db, p1->aData);
    sqlite4DbFree(db, p2->aData);
  }
................................................................................
/*
** Open a cursor for each token in the expression.
*/
static int fts5OpenCursors(sqlite4 *db, Fts5Info *pInfo, Fts5Cursor *pCsr){
  return fts5OpenExprCursors(db, pInfo, pCsr->pExpr->pRoot);
}

void sqlite4Fts5Close(Fts5Cursor *pCsr){
  if( pCsr ){
    sqlite4 *db = pCsr->db;
    if( pCsr->aMem ){
      int i;
      for(i=0; i<pCsr->pInfo->nCol; i++){
        sqlite4DbFree(db, pCsr->aMem[i].zMalloc);
      }
      sqlite4DbFree(db, pCsr->aMem);
    }

    sqlite4KVCursorClose(pCsr->pCsr);
    fts5ExpressionFree(db, pCsr->pExpr);
    sqlite4DbFree(db, pCsr->pIter);
    sqlite4DbFree(db, pCsr->aKey);
    sqlite4DbFree(db, pCsr->anRow);
    sqlite4DbFree(db, pCsr);
  }
}

static int fts5TokenAdvanceToMatch(
  InstanceList *p,
  InstanceList *pFirst,
................................................................................
      return 0;
    }
  }

  return (p->iCol==pFirst->iCol && p->iOff==iReq);
}

static int fts5StringFindInstances(sqlite4 *db, int iCol, Fts5Str *pStr){

  int i;
  int rc = SQLITE4_OK;
  int bEof = 0;
  int nByte = sizeof(InstanceList) * pStr->nToken;
  InstanceList *aIn;
  InstanceList out;

................................................................................
  while( rc==SQLITE4_OK && bEof==0 ){
    for(i=1; i<pStr->nToken; i++){
      int bMatch = fts5TokenAdvanceToMatch(&aIn[i], &aIn[0], i, &bEof);
      if( bMatch==0 || bEof ) break;
    }
    if( i==pStr->nToken && (iCol<0 || aIn[0].iCol==iCol) ){
      /* Record a match here */
      fts5InstanceListAppend(&out, aIn[0].iCol, aIn[0].iStream, aIn[0].iOff);
    }
    bEof = fts5InstanceListNext(&aIn[0]);
  }

  pStr->nList = out.iList;
  sqlite4DbFree(db, aIn);

................................................................................
  if( p1->iCol==p2->iCol && p1->iOff<p2->iOff && (p1->iOff+nNear)>=p2->iOff ){
    return 1;
  }
  return 0;
}

static int fts5StringNearTrim(

  Fts5Str *pTrim,                 /* Trim this instance list */
  Fts5Str *pNext,                 /* According to this one */
  int nNear
){
  if( pNext->nList==0 ){
    pTrim->nList = 0;
  }else{
................................................................................

    while( bEof==0 ){
      if( fts5IsNear(&near, &in, nTrail) 
       || fts5IsNear(&in, &near, nLead)
      ){
        /* The current position is a match. Append an entry to the output
        ** and advance the input cursor. */
        fts5InstanceListAppend(&out, in.iCol, in.iStream, in.iOff);
        bEof = fts5InstanceListNext(&in);
      }else{
        if( near.iCol<in.iCol || (near.iCol==in.iCol && near.iOff<in.iOff) ){
          bEof = fts5InstanceListNext(&near);
        }else if( near.iCol==in.iCol && near.iOff==in.iOff ){
          bEof = fts5InstanceListNext(&in);
          if( fts5IsNear(&near, &in, nTrail) ){
            fts5InstanceListAppend(&out, near.iCol, near.iStream, near.iOff);
          }
        }else{
          bEof = fts5InstanceListNext(&in);
        }
      }
    }

................................................................................
** is set to true before returning.
**
** If the cursors do not point to a match, then *ppAdvance is set to
** the token of the individual cursor that should be advanced before
** retrying this function.
*/
static int fts5PhraseIsMatch(
  sqlite4 *db,                    /* Database handle */
  Fts5Phrase *pPhrase,            /* Phrase to test */
  int *pbMatch,                   /* OUT: True for a match, false otherwise */
  Fts5Token **ppAdvance           /* OUT: Token to advance before retrying */
){
  const u8 *aPk1 = 0;
  int nPk1 = 0;
  int rc = SQLITE4_OK;
................................................................................

  /* At this point, it is established that all of the token cursors in the
  ** phrase point to an entry with the same primary key. Now figure out if
  ** the various string constraints are met. Along the way, synthesize a 
  ** position list for each Fts5Str object.  */
  for(i=0; rc==SQLITE4_OK && i<pPhrase->nStr; i++){
    Fts5Str *pStr = &pPhrase->aStr[i];
    rc = fts5StringFindInstances(db, pPhrase->iCol, pStr);
  }

  /* Trim the instance lists according to any NEAR constraints.  */
  for(i=1; rc==SQLITE4_OK && i<pPhrase->nStr; i++){
    int n = pPhrase->aiNear[i-1];
    rc = fts5StringNearTrim(&pPhrase->aStr[i], &pPhrase->aStr[i-1], n);
  }
  for(i=pPhrase->nStr-1; rc==SQLITE4_OK && i>0; i--){
    int n = pPhrase->aiNear[i-1];
    rc = fts5StringNearTrim(&pPhrase->aStr[i-1], &pPhrase->aStr[i], n);
  }

  *pbMatch = (pPhrase->aStr[0].nList>0);
  return rc;
}

static int fts5PhraseAdvanceToMatch(sqlite4 *db, Fts5Phrase *pPhrase){
  int rc;
  do {
    int bMatch;
    Fts5Token *pAdvance = 0;
    rc = fts5PhraseIsMatch(db, pPhrase, &bMatch, &pAdvance);
    if( rc!=SQLITE4_OK || bMatch ) break;
    rc = fts5TokenAdvance(db, pAdvance);
  }while( rc==SQLITE4_OK );
  return rc;
}

static int fts5ExprAdvance(sqlite4 *db, Fts5ExprNode *p, int bFirst){
  int rc = SQLITE4_OK;

  switch( p->eType ){
    case TOKEN_PRIMITIVE: {
      Fts5Phrase *pPhrase = p->pPhrase;
      if( bFirst==0 ){
        rc = fts5TokenAdvance(db, &pPhrase->aStr[0].aToken[0]);
      }
      if( rc==SQLITE4_OK ) rc = fts5PhraseAdvanceToMatch(db, pPhrase);
      if( rc==SQLITE4_OK ){
        rc = fts5TokenPk(&pPhrase->aStr[0].aToken[0], &p->aPk, &p->nPk);
      }else{
        p->aPk = 0;
        p->nPk = 0;
        if( rc==SQLITE4_NOTFOUND ) rc = SQLITE4_OK;
      }
      break;
    }

    case TOKEN_AND:
      p->aPk = 0;
      p->nPk = 0;
      rc = fts5ExprAdvance(db, p->pLeft, bFirst);
      if( rc==SQLITE4_OK ) rc = fts5ExprAdvance(db, p->pRight, bFirst);
      while( rc==SQLITE4_OK && p->pLeft->aPk && p->pRight->aPk ){
        int res = fts5KeyCompare(
            p->pLeft->aPk, p->pLeft->nPk, p->pRight->aPk, p->pRight->nPk
        );
        if( res<0 ){
          rc = fts5ExprAdvance(db, p->pLeft, 0);
        }else if( res>0 ){
          rc = fts5ExprAdvance(db, p->pRight, 0);
        }else{
          p->aPk = p->pLeft->aPk;
          p->nPk = p->pLeft->nPk;
          break;
        }
      }
      break;
................................................................................
      int res = 0;
      if( bFirst==0 ){
        res = fts5KeyCompare(
            p->pLeft->aPk, p->pLeft->nPk, p->pRight->aPk, p->pRight->nPk
        );
      }
        
      if( res<=0 ) rc = fts5ExprAdvance(db, p->pLeft, bFirst);
      if( rc==SQLITE4_OK && res>=0 ){
        rc = fts5ExprAdvance(db, p->pRight, bFirst);
      }

      res = fts5KeyCompare(
          p->pLeft->aPk, p->pLeft->nPk, p->pRight->aPk, p->pRight->nPk
      );
      if( res>0 ){
        p->aPk = p->pRight->aPk;
................................................................................


    default: assert( p->eType==TOKEN_NOT );

      p->aPk = 0;
      p->nPk = 0;

      rc = fts5ExprAdvance(db, p->pLeft, bFirst);
      if( bFirst && rc==SQLITE4_OK ){
        rc = fts5ExprAdvance(db, p->pRight, bFirst);
      }

      while( rc==SQLITE4_OK && p->pLeft->aPk && p->pRight->aPk ){
        int res = fts5KeyCompare(
            p->pLeft->aPk, p->pLeft->nPk, p->pRight->aPk, p->pRight->nPk
        );
        if( res<0 ){
          break;
        }else if( res>0 ){
          rc = fts5ExprAdvance(db, p->pRight, 0);
        }else{
          rc = fts5ExprAdvance(db, p->pLeft, 0);
        }
      }

      p->aPk = p->pLeft->aPk;
      p->nPk = p->pLeft->nPk;
      break;
  }

  assert( rc!=SQLITE4_NOTFOUND );
  return rc;
}

int sqlite4Fts5Next(Fts5Cursor *pCsr){
  sqlite4DbFree(pCsr->db, pCsr->pSz);
  pCsr->pSz = 0;
  pCsr->bMemValid = 0;
  return fts5ExprAdvance(pCsr->db, pCsr->pExpr->pRoot, 0);
}

int sqlite4Fts5Open(
  sqlite4 *db,                    /* Database handle */
  Fts5Info *pInfo,                /* Index description */
  const char *zMatch,             /* Match expression */
  int bDesc,                      /* True to iterate in desc. order of PK */
  Fts5Cursor **ppCsr,             /* OUT: New FTS cursor object */
  char **pzErr                    /* OUT: Error message */
){
  int rc = SQLITE4_OK;
  Fts5Cursor *pCsr;
  int nMatch = sqlite4Strlen30(zMatch);

  pCsr = sqlite4DbMallocZero(db, sizeof(Fts5Cursor) + nMatch + 1);

  if( !pCsr ){
    rc = SQLITE4_NOMEM;
  }else{
    pCsr->zExpr = (char *)&pCsr[1];
    memcpy(pCsr->zExpr, zMatch, nMatch);
    pCsr->pInfo = pInfo;
    pCsr->db = db;
    rc = fts5ParseExpression(db, pInfo->pTokenizer, pInfo->p, 
        pInfo->iRoot, pInfo->azCol, pInfo->nCol, zMatch, &pCsr->pExpr, pzErr
    );
  }

  if( rc==SQLITE4_OK ){
    /* Open a KV cursor for each term in the expression. Set each cursor
    ** to point to the first entry in the range it will scan.  */
    rc = fts5OpenCursors(db, pInfo, pCsr);
  }
  if( rc!=SQLITE4_OK ){
    sqlite4Fts5Close(pCsr);
    pCsr = 0;
  }else{
    rc = fts5ExprAdvance(db, pCsr->pExpr->pRoot, 1);
  }
  *ppCsr = pCsr;
  return rc;
}

/*
** Return true if the cursor passed as the second argument currently points
................................................................................
*/
int sqlite4Fts5Valid(Fts5Cursor *pCsr){
  return( pCsr->pExpr->pRoot->aPk!=0 );
}

int sqlite4Fts5Pk(
  Fts5Cursor *pCsr, 
  int iTbl,
  KVByteArray **paKey,
  KVSize *pnKey
){
  int i;
  int nReq;
  const u8 *aPk;
  int nPk;

................................................................................
  i = putVarint32(pCsr->aKey, iTbl);
  memcpy(&pCsr->aKey[i], aPk, nPk);

  *paKey = pCsr->aKey;
  *pnKey = nReq;
  return SQLITE4_OK;
}

int sqlite4_mi_column_count(sqlite4_context *pCtx, int *pn){
  int rc = SQLITE4_OK;
  if( pCtx->pFts ){
    *pn = pCtx->pFts->pInfo->nCol;
  }else{
    rc = SQLITE4_MISUSE;
  }
  return rc;
}

int sqlite4_mi_phrase_count(sqlite4_context *pCtx, int *pn){
  int rc = SQLITE4_OK;
  if( pCtx->pFts ){
    *pn = pCtx->pFts->pExpr->nPhrase;
  }else{
    rc = SQLITE4_MISUSE;
  }
  return rc;
}

int sqlite4_mi_phrase_token_count(sqlite4_context *pCtx, int iP, int *pn){
  int rc = SQLITE4_OK;
  if( pCtx->pFts ){
    Fts5Expr *pExpr = pCtx->pFts->pExpr;
    if( iP>pExpr->nPhrase || iP<0 ){
      *pn = 0;
    }else{
      *pn = pExpr->apPhrase[iP]->nToken;
    }
  }else{
    rc = SQLITE4_MISUSE;
  }
  return rc;
}

int sqlite4_mi_stream_count(sqlite4_context *pCtx, int *pn){
  int rc = SQLITE4_OK;
  Fts5Cursor *pCsr = pCtx->pFts;
  if( pCsr ){
    rc = fts5CsrLoadGlobal(pCtx->pFts);
    if( rc==SQLITE4_OK ) *pn = pCsr->pGlobal->nStream;
  }else{
    rc = SQLITE4_MISUSE;
  }
  return rc;
}

static int fts5GetSize(Fts5Size *pSz, int iC, int iS){
  int nToken = 0;
  int i;

  if( iC<0 && iS<0 ){
    int nFin = pSz->nCol * pSz->nStream;
    for(i=0; i<nFin; i++) nToken += pSz->aSz[i];
  }else if( iC<0 ){
    for(i=0; i<pSz->nCol; i++) nToken += pSz->aSz[i*pSz->nStream + iS];
  }else if( iS<0 ){
    for(i=0; i<pSz->nStream; i++) nToken += pSz->aSz[pSz->nStream*iC + i];
  }else if( iC<pSz->nCol && iS<pSz->nStream ){
    nToken = pSz->aSz[iC * pSz->nStream + iS];
  }

  return nToken;
}

int sqlite4_mi_size(sqlite4_context *pCtx, int iC, int iS, int *pn){
  int rc = SQLITE4_OK;
  Fts5Cursor *pCsr = pCtx->pFts;

  if( pCsr==0 ){
    rc = SQLITE4_MISUSE;
  }else{
    rc = fts5CsrLoadSz(pCsr);
    if( rc==SQLITE4_OK ){
      *pn = fts5GetSize(pCsr->pSz, iC, iS);
    }
  }
  return rc;
}

int sqlite4_mi_total_size(sqlite4_context *pCtx, int iC, int iS, int *pn){
  int rc = SQLITE4_OK;
  Fts5Cursor *pCsr = pCtx->pFts;

  if( pCsr==0 ){
    rc = SQLITE4_MISUSE;
  }else{
    rc = fts5CsrLoadGlobal(pCsr);
    if( rc==SQLITE4_OK ){
      *pn = fts5GetSize(pCsr->pGlobal, iC, iS);
    }
  }
  return rc;
}

int sqlite4_mi_total_rows(sqlite4_context *pCtx, int *pn){
  int rc = SQLITE4_OK;
  Fts5Cursor *pCsr = pCtx->pFts;
  if( pCsr==0 ){
    rc = SQLITE4_MISUSE;
  }else{
    rc = fts5CsrLoadGlobal(pCsr);
    if( rc==SQLITE4_OK ) *pn = pCsr->nGlobal;
  }
  return rc;
}

int sqlite4_mi_column_value(
  sqlite4_context *pCtx, 
  int iCol, 
  sqlite4_value **ppVal
){
  int rc = SQLITE4_OK;
  Fts5Cursor *pCsr = pCtx->pFts;
  if( pCsr==0 ){
    rc = SQLITE4_MISUSE;
  }else{
    if( pCsr->bMemValid==0 ){
      sqlite4 *db = pCsr->db;

      Fts5Info *pInfo = pCsr->pInfo;
      if( pCsr->aMem==0 ){
        int nByte = sizeof(Mem) * pInfo->nCol;
        pCsr->aMem = (Mem *)sqlite4DbMallocZero(db, nByte);
        if( pCsr->aMem==0 ){
          rc = SQLITE4_NOMEM;
        }else{
          int i;
          for(i=0; i<pInfo->nCol; i++){
            pCsr->aMem[i].db = db;
          }
        }
      }

      if( pCsr->pCsr==0 && rc==SQLITE4_OK ){
        KVStore *pStore = db->aDb[pInfo->iDb].pKV;
        rc = sqlite4KVStoreOpenCursor(pStore, &pCsr->pCsr);
      }

      if( rc==SQLITE4_OK ){
        u8 *aKey = 0; int nKey;     /* Primary key for current row */
        const u8 *aData; int nData; /* Data record for current row */

        rc = sqlite4Fts5Pk(pCsr, pInfo->iTbl, &aKey, &nKey);
        if( rc==SQLITE4_OK ){
          rc = sqlite4KVCursorSeek(pCsr->pCsr, aKey, nKey, 0);
          if( rc==SQLITE4_NOTFOUND ){
            rc = SQLITE4_CORRUPT_BKPT;
          }
        }

        if( rc==SQLITE4_OK ){
          rc = sqlite4KVCursorData(pCsr->pCsr, 0, -1, &aData, &nData);
        }

        if( rc==SQLITE4_OK ){
          int i;
          ValueDecoder *pCodec;   /* The decoder object */

          rc = sqlite4VdbeCreateDecoder(db, aData, nData, pInfo->nCol, &pCodec);
          for(i=0; rc==SQLITE4_OK && i<pInfo->nCol; i++){
            rc = sqlite4VdbeDecodeValue(pCodec, i, 0, &pCsr->aMem[i]);
          }
          sqlite4VdbeDestroyDecoder(pCodec);
        }

        if( rc==SQLITE4_OK ) pCsr->bMemValid = 1;
      }
    }

    if( rc==SQLITE4_OK ){
      assert( pCsr->bMemValid );
      *ppVal = &pCsr->aMem[iCol];
    }
  }

  return rc;
}

int sqlite4_mi_tokenize(
  sqlite4_context *pCtx,
  const char *zText,
  int nText,
  void *p,
  int(*x)(void *, int, int, const char *, int, int, int)
){
  int rc = SQLITE4_OK;
  Fts5Cursor *pCsr = pCtx->pFts;

  if( pCsr==0 ){
    rc = SQLITE4_MISUSE;
  }else{
    Fts5Info *pInfo = pCsr->pInfo;
    rc = pInfo->pTokenizer->xTokenize(p, pInfo->p, zText, nText, x);
  }
  return rc;
}

static Fts5Str *fts5FindStr(Fts5ExprNode *p, int *piStr){
  Fts5Str *pRet = 0;
  if( p->eType==TOKEN_PRIMITIVE ){
    int iStr = *piStr;
    if( iStr<p->pPhrase->nStr ){
      pRet = &p->pPhrase->aStr[iStr];
    }else{
      *piStr = iStr - p->pPhrase->nStr;
    }
  }else{
    pRet = fts5FindStr(p->pLeft, piStr);
    if( pRet==0 ) pRet = fts5FindStr(p->pRight, piStr);
  }
  return pRet;
}

int sqlite4_mi_match_count(
  sqlite4_context *pCtx, 
  int iC,
  int iS,
  int iPhrase,
  int *pnMatch
){
  int rc = SQLITE4_OK;
  Fts5Cursor *pCsr = pCtx->pFts;
  if( pCsr ){
    int nMatch = 0;
    Fts5Str *pStr;
    int iCopy = iPhrase;
    InstanceList sList;

    pStr = fts5FindStr(pCsr->pExpr->pRoot, &iCopy);
    assert( pStr );

    fts5InstanceListInit(pStr->aList, pStr->nList, &sList);
    while( 0==fts5InstanceListNext(&sList) ){
      if( (iC<0 || sList.iCol==iC) && (iS<0 || sList.iStream==iS) ) nMatch++;
    }
    *pnMatch = nMatch;
  }else{
    rc = SQLITE4_MISUSE;
  }
  return rc;
}

int sqlite4_mi_match_offset(
  sqlite4_context *pCtx, 
  int iCol, 
  int iPhrase, 
  int iMatch, 
  int *piOff
){
  return SQLITE4_OK;
}

int sqlite4_mi_total_match_count(
  sqlite4_context *pCtx,
  int iCol,
  int iPhrase,
  int *pnMatch,
  int *pnDoc,
  int *pnRelevant
){
  return SQLITE4_OK;
}

static void fts5StrLoadRowcounts(Fts5Str *pStr, int nStream, int *anRow){
  u32 mask = 0;
  int iPrevCol = 0;
  InstanceList sList;

  fts5InstanceListInit(pStr->aList, pStr->nList, &sList);
  while( 0==fts5InstanceListNext(&sList) ){
    if( sList.iCol!=iPrevCol ) mask = 0;
    if( (mask & (1<<sList.iStream))==0 ){
      anRow[sList.iCol * nStream + sList.iStream]++;
      mask |= (1<<sList.iStream);
      iPrevCol = sList.iCol;
    }
  }
}

static int fts5ExprLoadRowcounts(
  sqlite4 *db, 
  Fts5Info *pInfo,
  int nStream,
  Fts5ExprNode *pNode, 
  int **panRow
){
  int rc = SQLITE4_OK;

  if( pNode ){
    if( pNode->eType==TOKEN_PRIMITIVE ){
      int *anRow = *panRow;
      Fts5Phrase *pPhrase = pNode->pPhrase;

      rc = fts5ExprAdvance(db, pNode, 1);
      while( rc==SQLITE4_OK ){
        int nIncr =  pInfo->nCol * nStream;      /* Values for each Fts5Str */
        int i;
        for(i=0; i<pPhrase->nStr; i++){
          fts5StrLoadRowcounts(&pPhrase->aStr[i], nStream, &anRow[i*nIncr]);
        }
        rc = fts5ExprAdvance(db, pNode, 0);
      }

      *panRow = &anRow[pInfo->nCol * nStream * pPhrase->nStr];
    }

    if( rc==SQLITE4_OK ){
      rc = fts5ExprLoadRowcounts(db, pInfo, nStream, pNode->pLeft, panRow);
    }
    if( rc==SQLITE4_OK ){
      rc = fts5ExprLoadRowcounts(db, pInfo, nStream, pNode->pRight, panRow);
    }
  }

  return rc;
}

static int fts5CsrLoadRowcounts(Fts5Cursor *pCsr){
  int rc = SQLITE4_OK;

  if( pCsr->anRow==0 ){
    int nStream = pCsr->pGlobal->nStream;
    sqlite4 *db = pCsr->db;
    Fts5Expr *pCopy;
    Fts5Expr *pExpr = pCsr->pExpr;
    Fts5Info *pInfo = pCsr->pInfo;
    int *anRow;

    pCsr->anRow = anRow = (int *)sqlite4DbMallocZero(db, 
        pExpr->nPhrase * pInfo->nCol * pCsr->pGlobal->nStream * sizeof(int)
    );
    if( !anRow ) return SQLITE4_NOMEM;

    rc = fts5ParseExpression(db, pInfo->pTokenizer, pInfo->p, 
        pInfo->iRoot, pInfo->azCol, pInfo->nCol, pCsr->zExpr, &pCopy, 0
    );
    if( rc==SQLITE4_OK ){
      rc = fts5OpenExprCursors(db, pInfo, pExpr->pRoot);
    }
    if( rc==SQLITE4_OK ){
      rc = fts5ExprLoadRowcounts(db, pInfo, nStream, pCopy->pRoot, &anRow);
    }

    fts5ExpressionFree(db, pCopy);
  }

  return rc;
}

int sqlite4_mi_row_count(
  sqlite4_context *pCtx,          /* Context object passed to mi function */
  int iC,                         /* Specific column (or -ve for all columns) */
  int iS,                         /* Specific stream (or -ve for all streams) */
  int iP,                         /* Specific phrase */
  int *pn                         /* Total number of rows containing C/S/P */
){
  int rc = SQLITE4_OK;
  Fts5Cursor *pCsr = pCtx->pFts;
  if( pCsr==0 ){
    rc = SQLITE4_MISUSE;
  }else{
    rc = fts5CsrLoadGlobal(pCsr);
    if( rc==SQLITE4_OK ) rc = fts5CsrLoadRowcounts(pCsr);

    if( rc==SQLITE4_OK ){
      int i;
      int nRow = 0;
      int nStream = pCsr->pGlobal->nStream;
      int nCol = pCsr->pInfo->nCol;
      int *aRow = &pCsr->anRow[iP * nStream * nCol];

      if( iC<0 && iS<0 ){
        int nFin = nCol * nStream;
        for(i=0; i<nFin; i++) nRow += aRow[i];
      }else if( iC<0 ){
        for(i=0; i<nCol; i++) nRow += aRow[i*nStream + iS];
      }else if( iS<0 ){
        for(i=0; i<nStream; i++) nRow += aRow[nStream*iC + iS];
      }else if( iC<nCol && iS<nStream ){
        nRow = aRow[iC * nStream + iS];
      }

      *pn = nRow;
    }
  }
  return rc;
}

static void fts5IterSetCurrent(Fts5MatchIter *pIter, int nList){
  InstanceList *pBest = 0;
  int i;

  for(i=0; i<nList; i++){
    InstanceList *p = &pIter->aList[i];
    if( fts5InstanceListEof(p)==0 ){
      if( (pBest==0)
       || (p->iCol<pBest->iCol)
       || (p->iCol==pBest->iCol && p->iOff<pBest->iOff)
      ){
        pBest = p;
      }
    }
  }

  if( pBest==0 ){
    pIter->iCurrent = -1;
  }else{
    pIter->iCurrent = pBest - pIter->aList;
  }
}

static void fts5InitExprIterator(
  const u8 *aPk, 
  int nPk, 
  Fts5ExprNode *p,
  Fts5MatchIter *pIter
){
  if( p ){
    if( p->eType==TOKEN_PRIMITIVE ){
      if( p->nPk==nPk && 0==memcmp(aPk, p->aPk, nPk) ){
        int i;
        for(i=0; i<p->pPhrase->nStr; i++){
          Fts5Str *pStr = &p->pPhrase->aStr[i];
          InstanceList *pList = &pIter->aList[pIter->iCurrent++];
          fts5InstanceListInit(pStr->aList, pStr->nList, pList);
          fts5InstanceListNext(pList);
        }
      }else{
        memset(&pIter->aList[pIter->iCurrent], 0, sizeof(InstanceList));
        pIter->iCurrent += p->pPhrase->nStr;
      }
    }
    fts5InitExprIterator(aPk, nPk, p->pLeft, pIter);
    fts5InitExprIterator(aPk, nPk, p->pRight, pIter);
  }
}

static void fts5InitIterator(Fts5Cursor *pCsr){
  Fts5MatchIter *pIter = pCsr->pIter;
  Fts5ExprNode *pRoot = pCsr->pExpr->pRoot;

  pIter->iCurrent = 0;
  fts5InitExprIterator(pRoot->aPk, pRoot->nPk, pRoot, pIter);
  pIter->iMatch = 0;
  pIter->bValid = 1;
  fts5IterSetCurrent(pIter, pCsr->pExpr->nPhrase);
}

int sqlite4_mi_match_detail(
  sqlite4_context *pCtx,          /* Context object passed to mi function */
  int iMatch,                     /* Index of match */
  int *piOff,                     /* OUT: Token offset of match */
  int *piC,                       /* OUT: Column number of match iMatch */
  int *piS,                       /* OUT: Stream number of match iMatch */
  int *piP                        /* OUT: Phrase number of match iMatch */
){
  int rc = SQLITE4_OK;
  Fts5Cursor *pCsr = pCtx->pFts;
  if( pCsr==0 ){
    rc = SQLITE4_MISUSE;
  }else{
    int nPhrase = pCsr->pExpr->nPhrase;
    Fts5MatchIter *pIter = pCsr->pIter;
    if( pIter==0 ){
      pCsr->pIter = pIter = (Fts5MatchIter *)sqlite4DbMallocZero(
          pCsr->db, sizeof(Fts5MatchIter) + sizeof(InstanceList)*nPhrase
      );
      if( pIter ){
        pIter->aList = (InstanceList *)&pIter[1];
      }else{
        rc = SQLITE4_NOMEM;
      }
    }

    if( rc==SQLITE4_OK && (pIter->bValid==0 || iMatch<pIter->iMatch) ){
      fts5InitIterator(pCsr);
#if 0
      int i;
      for(i=0; i<pCsr->pExpr->nPhrase; i++){
        Fts5Str *pStr = pCsr->pExpr->apPhrase[i];
        fts5InstanceListInit(pStr->aList, pStr->nList, &pIter->aList[i]);
        fts5InstanceListNext(&pIter->aList[i]);
      }
      pIter->iMatch = 0;
      fts5IterSetCurrent(pIter, pCsr->pExpr->nPhrase);
#endif
    }

    if( rc==SQLITE4_OK ){
      assert( pIter->iMatch<=iMatch );
      while( pIter->iCurrent>=0 && pIter->iMatch<iMatch ){
        fts5InstanceListNext(&pIter->aList[pIter->iCurrent]);
        fts5IterSetCurrent(pIter, pCsr->pExpr->nPhrase);
        pIter->iMatch++;
      }
      if( pIter->iCurrent<0 ){
        rc = SQLITE4_NOTFOUND;
      }else{
        InstanceList *p = &pIter->aList[pIter->iCurrent];
        *piOff = p->iOff;
        *piC = p->iCol;
        *piS = p->iStream;
        *piP = pIter->iCurrent;
      }
    }
  }
  return rc;
}

/**************************************************************************
***************************************************************************
** Below this point is test code.
*/
#ifdef SQLITE4_TEST
static int fts5PrintExprNode(sqlite4 *, const char **, Fts5ExprNode *, char **);

Changes to src/fts5func.c.

6
7
8
9
10
11
12
13








14






15
16
17
18
19
20
21
..
23
24
25
26
27
28
29
30
31





















































































































































32
33

34






35
36








































































































































































































































































37
38
39
40
41
42
43
44
..
71
72
73
74
75
76
77






78
79
80
**
**    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.
**
*************************************************************************
*/









#include "sqliteInt.h"







static int fts5SimpleCreate(
  void *pCtx, 
  const char **azArg, 
  int nArg, 
  sqlite4_tokenizer **pp
){
................................................................................
  return SQLITE4_OK;
}

static int fts5SimpleDestroy(sqlite4_tokenizer *p){
  return SQLITE4_OK;
}

static char fts5Tolower(char c){
  if( c>='A' && c<='Z' ) c = c + ('a' - 'A');





















































































































































  return c;
}








static int fts5SimpleTokenize(
  void *pCtx, 








































































































































































































































































  sqlite4_tokenizer *p,
  const char *zDoc,
  int nDoc,
  int(*x)(void*, int, int, const char*, int, int, int)
){
  sqlite4_env *pEnv = (sqlite4_env *)p;
  char *aBuf;
  int nBuf;
................................................................................
  sqlite4_env *pEnv = sqlite4_db_env(db);

  rc = sqlite4_create_tokenizer(db, "simple", (void *)pEnv, 
      fts5SimpleCreate, fts5SimpleTokenize, fts5SimpleDestroy
  );
  if( rc!=SQLITE4_OK ) return rc;







  return rc;
}









>
>
>
>
>
>
>
>

>
>
>
>
>
>







 







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

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







 







>
>
>
>
>
>



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
..
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
...
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
**
**    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.
**
*************************************************************************
*/

/*
** The BM25 and BM25F implementations in this file are based on information
** found in:
**
**   Stephen Robertson and Hugo Zaragoza: "The Probablistic Relevance
**   Framework: BM25 and Beyond", 2009.
*/

#include "sqliteInt.h"
#include <math.h>                 /* temporary: For log() */

static char fts5Tolower(char c){
  if( c>='A' && c<='Z' ) c = c + ('a' - 'A');
  return c;
}

static int fts5SimpleCreate(
  void *pCtx, 
  const char **azArg, 
  int nArg, 
  sqlite4_tokenizer **pp
){
................................................................................
  return SQLITE4_OK;
}

static int fts5SimpleDestroy(sqlite4_tokenizer *p){
  return SQLITE4_OK;
}

typedef struct Fts5RankCtx Fts5RankCtx;
struct Fts5RankCtx {
  sqlite4 *db;
  double avgdl;                   /* Average document size in tokens */
  int nPhrase;                    /* Number of phrases in query */
  double *aIdf;                   /* IDF weights for each phrase in query */
};

static void fts5RankFreeCtx(void *pCtx){
  if( pCtx ){
    Fts5RankCtx *p = (Fts5RankCtx *)pCtx;
    sqlite4DbFree(p->db, p);
  }
}

/*
** A BM25 based ranking function for fts5.
**
** This is based on the information in the Robertson/Zaragoza paper 
** referenced above. As there is no way to provide relevance feedback 
** IDF weights (equation 3.3 in R/Z) are used instead of RSJ for each phrase.
** The rest of the implementation is as presented in equation 3.15.
**
** R and Z observe that the experimental evidence suggests that reasonable
** values for free parameters "b" and "k1" are often in the ranges 
** (0.5 < b < 0.8) and (1.2 < k1 < 2), although the optimal values depend
** on the nature of both the documents and queries. The implementation
** below sets each parameter to the midpoint of the suggested range.
*/
static void fts5Rank(sqlite4_context *pCtx, int nArg, sqlite4_value **apArg){
  const double b = 0.65;
  const double k1 = 1.6;

  int rc = SQLITE4_OK;            /* Error code */
  Fts5RankCtx *p;                 /* Structure to store reusable values */
  int i;                          /* Used to iterate through phrases */
  double rank = 0.0;              /* UDF return value */

  p = sqlite4_get_auxdata(pCtx, 0);
  if( p==0 ){
    sqlite4 *db = sqlite4_context_db_handle(pCtx);
    int nPhrase;                  /* Number of phrases in query expression */
    int nByte;                    /* Number of bytes of data to allocate */

    sqlite4_mi_phrase_count(pCtx, &nPhrase);
    nByte = sizeof(Fts5RankCtx) + nPhrase * sizeof(double);
    p = (Fts5RankCtx *)sqlite4DbMallocZero(db, nByte);
    sqlite4_set_auxdata(pCtx, 0, (void *)p, fts5RankFreeCtx);
    p = sqlite4_get_auxdata(pCtx, 0);

    if( !p ){
      rc = SQLITE4_NOMEM;
    }else{
      int N;                      /* Total number of docs in collection */
      int ni;                     /* Number of docs with phrase i */

      p->db = db;
      p->nPhrase = nPhrase;
      p->aIdf = (double *)&p[1];

      /* Determine the IDF weight for each phrase in the query. */
      rc = sqlite4_mi_total_rows(pCtx, &N);
      for(i=0; rc==SQLITE4_OK && i<nPhrase; i++){
        rc = sqlite4_mi_row_count(pCtx, -1, -1, i, &ni);
        if( rc==SQLITE4_OK ){
          p->aIdf[i] = log((0.5 + N - ni) / (0.5 + ni));
        }
      }

      /* Determine the average document length */
      if( rc==SQLITE4_OK ){
        int nTotal;
        rc = sqlite4_mi_total_size(pCtx, -1, -1, &nTotal);
        if( rc==SQLITE4_OK ){
          p->avgdl = (double)nTotal / (double)N;
        }
      }
    }
  }

  for(i=0; rc==SQLITE4_OK && i<p->nPhrase; i++){
    int tf;                     /* Occurences of phrase i in row (term freq.) */
    int dl;                     /* Tokens in this row (document length) */
    double L;                   /* Normalized document length */
    double prank;               /* Contribution to rank of this phrase */

    /* Set variable tf to the total number of occurrences of phrase iPhrase
    ** in this row (within any column). And dl to the number of tokens in
    ** the current row (again, in any column).  */
    rc = sqlite4_mi_match_count(pCtx, -1, -1, i, &tf); 
    if( rc==SQLITE4_OK ) rc = sqlite4_mi_size(pCtx, -1, -1, &dl); 

    /* Calculate the normalized document length */
    L = (double)dl / p->avgdl;

    /* Calculate the contribution to the rank made by this phrase. Then
    ** add it to variable rank.  */
    prank = (p->aIdf[i] * tf) / (k1 * ( (1.0 - b) + b * L) + tf);
    rank += prank;
  }

  if( rc==SQLITE4_OK ){
    sqlite4_result_double(pCtx, rank);
  }else{
    sqlite4_result_error_code(pCtx, rc);
  }
}

typedef struct Snippet Snippet;
typedef struct SnippetText SnippetText;

struct Snippet {
  int iCol;
  int iOff;
  u64 hlmask;
};

struct SnippetText {
  char *zOut;                     /* Pointer to snippet text */
  int nOut;                       /* Size of zOut in bytes */
  int nAlloc;                     /* Bytes of space allocated at zOut */
};

typedef struct SnippetCtx SnippetCtx;
struct SnippetCtx {
  sqlite4 *db;                    /* Database handle */
  int nToken;                     /* Number of tokens in snippet */
  int iOff;                       /* First token in snippet */
  u64 mask;                       /* Snippet mask. Highlight these terms */
  const char *zStart;
  const char *zEnd;
  const char *zEllipses;

  SnippetText *pOut;

  int iFrom;
  int iTo;
  const char *zText;              /* Document to extract snippet from */
  int rc;                         /* Set to NOMEM if OOM is encountered */
};

static void fts5SnippetAppend(SnippetCtx *p, const char *z, int n){
  if( p->rc==SQLITE4_OK ){
    SnippetText *pOut = p->pOut;
    if( n<0 ) n = strlen(z);
    if( (pOut->nOut + n) > pOut->nAlloc ){
      int nNew = (pOut->nOut+n) * 2;

      pOut->zOut = sqlite4DbReallocOrFree(p->db, pOut->zOut, nNew);
      if( pOut->zOut==0 ){
        p->rc = SQLITE4_NOMEM;
        return;
      }
      pOut->nAlloc = sqlite4DbMallocSize(p->db, pOut->zOut);
    }

    memcpy(&pOut->zOut[pOut->nOut], z, n);
    pOut->nOut += n;
  }
}

static int fts5SnippetCb(
  void *pCtx, 
  int iStream, 
  int iOff, 
  const char *z, int n,
  int iSrc, int nSrc
){
  SnippetCtx *p = (SnippetCtx *)pCtx;

  if( iOff<p->iOff ){
    return 0;
  }else if( iOff>=(p->iOff + p->nToken) ){
    fts5SnippetAppend(p, &p->zText[p->iFrom], p->iTo - p->iFrom);
    fts5SnippetAppend(p, "...", 3);
    p->iFrom = -1;
    return 1;
  }else{
    int bHighlight;               /* True to highlight term */

    bHighlight = (p->mask & (1 << (iOff-p->iOff)));

    if( p->iFrom==0 && p->iOff!=0 ){
      p->iFrom = iSrc;
      if( p->pOut->nOut==0 ) fts5SnippetAppend(p, p->zEllipses, -1);
    }

    if( bHighlight ){
      fts5SnippetAppend(p, &p->zText[p->iFrom], iSrc - p->iFrom);
      fts5SnippetAppend(p, p->zStart, -1);
      fts5SnippetAppend(p, &p->zText[iSrc], nSrc);
      fts5SnippetAppend(p, p->zEnd, -1);
      p->iTo = p->iFrom = iSrc+nSrc;
    }else{
      p->iTo = iSrc + nSrc;
    }
  }

  return 0;
}

static int fts5SnippetText(
  sqlite4_context *pCtx, 
  Snippet *pSnip,
  SnippetText *pText,
  int nToken,
  const char *zStart,
  const char *zEnd,
  const char *zEllipses
){
  int rc;
  sqlite4_value *pVal = 0;

  u64 mask = pSnip->hlmask;
  int iOff = pSnip->iOff;
  int iCol = pSnip->iCol;

  rc = sqlite4_mi_column_value(pCtx, iCol, &pVal);
  if( rc==SQLITE4_OK ){
    SnippetCtx sCtx;
    int nText;

    nText = sqlite4_value_bytes(pVal);
    memset(&sCtx, 0, sizeof(sCtx));
    sCtx.zText = (const char *)sqlite4_value_text(pVal);
    sCtx.db = sqlite4_context_db_handle(pCtx);
    sCtx.nToken = nToken;
    sCtx.iOff = iOff;
    sCtx.mask = mask;
    sCtx.zStart = zStart;
    sCtx.zEnd = zEnd;
    sCtx.zEllipses = zEllipses;
    sCtx.pOut = pText;

    sqlite4_mi_tokenize(pCtx, sCtx.zText, nText, &sCtx, fts5SnippetCb);
    if( sCtx.rc==SQLITE4_OK && sCtx.iFrom>0 ){
      fts5SnippetAppend(&sCtx, &sCtx.zText[sCtx.iFrom], nText - sCtx.iFrom);
    }
    rc = sCtx.rc;
  }

  return rc;
}

static int fts5BestSnippet(
  sqlite4_context *pCtx,          /* Context snippet() was called in */
  int iColumn,                    /* In this column (-1 means any column) */
  u64 *pMask,                     /* IN/OUT: Mask of high-priority phrases */
  int nToken,                     /* Number of tokens in requested snippet */
  Snippet *pSnip                  /* Populate this object */
){
  sqlite4 *db = sqlite4_context_db_handle(pCtx);
  int nPhrase;
  int rc = SQLITE4_OK;
  int i;
  int iPrev = 0;
  int iPrevCol = 0;
  u64 *aMask;
  u64 mask = *pMask;
  u64 allmask = 0;

  int iBestOff = nToken-1;
  int iBestCol = (iColumn >= 0 ? iColumn : 0);
  int nBest = 0;
  u64 hlmask = 0;                 /* Highlight mask associated with iBestOff */
  u64 missmask = 0;               /* Mask of missing terms in iBestOff snip. */

  sqlite4_mi_phrase_count(pCtx, &nPhrase);
  aMask = sqlite4DbMallocZero(db, sizeof(u64) * nPhrase);
  if( !aMask ) return SQLITE4_NOMEM;

  /* Iterate through all matches for all phrases */
  for(i=0; rc==SQLITE4_OK; i++){
    int iOff;
    int iCol;
    int iStream;
    int iPhrase;

    rc = sqlite4_mi_match_detail(pCtx, i, &iOff, &iCol, &iStream, &iPhrase);
    if( rc==SQLITE4_OK ){
      u64 tmask = 0;
      u64 miss = 0;
      int iMask;
      int nShift; 
      int nScore = 0;

      int nPTok;
      int iPTok;

      if( iColumn>=0 && iColumn!=iCol ) continue;

      allmask |= (1 << iPhrase);

      nShift = ((iPrevCol==iCol) ? (iOff-iPrev) : 100);

      for(iMask=0; iMask<nPhrase; iMask++){
        if( nShift<64){
          aMask[iMask] = aMask[iMask] >> nShift;
        }else{
          aMask[iMask] = 0;
        }
      }
      sqlite4_mi_phrase_token_count(pCtx, iPhrase, &nPTok);
      for(iPTok=0; iPTok<nPTok; iPTok++){
        aMask[iPhrase] = aMask[iPhrase] | (1<<(nToken-1+iPTok));
      }

      for(iMask=0; iMask<nPhrase; iMask++){
        if( aMask[iMask] ){
          nScore += (((1 << iMask) & mask) ? 100 : 1);
        }else{
          miss |= (1 << iMask);
        }
        tmask = tmask | aMask[iMask];
      }

      if( nScore>nBest ){
        hlmask = tmask;
        missmask = miss;
        nBest = nScore;
        iBestOff = iOff;
        iBestCol = iCol;
      }

      iPrev = iOff;
      iPrevCol = iCol;
    }
  }
  if( rc==SQLITE4_NOTFOUND ) rc = SQLITE4_OK;

  pSnip->iOff = iBestOff-nToken+1;
  pSnip->iCol = iBestCol;
  pSnip->hlmask = hlmask;
  *pMask = mask & missmask & allmask;

  sqlite4DbFree(db, aMask);
  return rc;
}

static void fts5SnippetImprove(
  sqlite4_context *pCtx, 
  int nToken,                     /* Size of required snippet */
  int nSz,                        /* Total size of column in tokens */
  Snippet *pSnip
){
  int i;
  int nLead = 0;
  int nShift = 0;

  u64 mask = pSnip->hlmask;
  int iOff = pSnip->iOff;

  if( mask==0 ) return;
  assert( mask & (1 << (nToken-1)) );

  for(i=0; (mask & (1<<i))==0; i++);
  nLead = i;

  nShift = (nLead/2);
  if( iOff+nShift > nSz-nToken ) nShift = (nSz-nToken) - iOff;
  if( iOff+nShift < 0 ) nShift = -1 * iOff;

  iOff += nShift;
  mask = mask >> nShift;

  pSnip->iOff = iOff;
  pSnip->hlmask = mask;
}

static void fts5Snippet(sqlite4_context *pCtx, int nArg, sqlite4_value **apArg){
  Snippet aSnip[4];
  int nSnip;
  int iCol = -1;
  int nToken = -15;
  int rc;
  int nPhrase;

  const char *zStart = "<b>";
  const char *zEnd = "</b>";
  const char *zEllipses = "...";

  if( nArg>0 ) zStart = (const char *)sqlite4_value_text(apArg[0]);
  if( nArg>1 ) zEnd = (const char *)sqlite4_value_text(apArg[1]);
  if( nArg>2 ) zEllipses = (const char *)sqlite4_value_text(apArg[2]);
  if( nArg>3 ) iCol = sqlite4_value_int(apArg[3]);
  if( nArg>4 ) nToken = sqlite4_value_int(apArg[4]);

  rc = sqlite4_mi_phrase_count(pCtx, &nPhrase);
  for(nSnip=1; rc==SQLITE4_OK && nSnip<5; nSnip = ((nSnip==2) ? 3 : (nSnip+1))){
    int nTok;
    int i;
    u64 mask = ((u64)1 << nPhrase) - 1;

    if( nToken<0 ){
      nTok = nToken * -1;
    }else{
      nTok = (nToken + (nSnip-1)) / nSnip;
    }

    memset(aSnip, 0, sizeof(aSnip));
    for(i=0; rc==SQLITE4_OK && i<nSnip; i++){
      rc = fts5BestSnippet(pCtx, iCol, &mask, nTok, &aSnip[i]);
    }
    if( mask==0 || nSnip==4 ){
      SnippetText text = {0, 0, 0};
      for(i=0; rc==SQLITE4_OK && i<nSnip; i++){
        int nSz;
        rc = sqlite4_mi_size(pCtx, aSnip[i].iCol, -1, &nSz);
        if( rc==SQLITE4_OK ){
          fts5SnippetImprove(pCtx, nTok, nSz, &aSnip[i]);
          rc = fts5SnippetText(
              pCtx, &aSnip[i], &text, nTok, zStart, zEnd, zEllipses
          );
        }
      }
      sqlite4_result_text(pCtx, text.zOut, text.nOut, SQLITE4_TRANSIENT);
      sqlite4DbFree(sqlite4_context_db_handle(pCtx), text.zOut);
      break;
    }
  }

  if( rc!=SQLITE4_OK ){
    sqlite4_result_error_code(pCtx, rc);
  }
}

static int fts5SimpleTokenize(
  void *pCtx, sqlite4_tokenizer *p,
  const char *zDoc,
  int nDoc,
  int(*x)(void*, int, int, const char*, int, int, int)
){
  sqlite4_env *pEnv = (sqlite4_env *)p;
  char *aBuf;
  int nBuf;
................................................................................
  sqlite4_env *pEnv = sqlite4_db_env(db);

  rc = sqlite4_create_tokenizer(db, "simple", (void *)pEnv, 
      fts5SimpleCreate, fts5SimpleTokenize, fts5SimpleDestroy
  );
  if( rc!=SQLITE4_OK ) return rc;

  rc = sqlite4_create_mi_function(db, "rank", 0, SQLITE4_UTF8, 0, fts5Rank, 0);
  if( rc!=SQLITE4_OK ) return rc;

  rc = sqlite4_create_mi_function(
      db, "snippet", -1, SQLITE4_UTF8, 0, fts5Snippet, 0
  );
  return rc;
}

Changes to src/main.c.

1048
1049
1050
1051
1052
1053
1054
























1055
1056
1057
1058
1059
1060
1061
  if( pArg && pArg->nRef==0 ){
    assert( rc!=SQLITE4_OK );
    xDestroy(p);
    sqlite4DbFree(db, pArg);
  }

 out:
























  rc = sqlite4ApiExit(db, rc);
  sqlite4_mutex_leave(db->mutex);
  return rc;
}

#ifndef SQLITE4_OMIT_UTF16
int sqlite4_create_function16(







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







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
  if( pArg && pArg->nRef==0 ){
    assert( rc!=SQLITE4_OK );
    xDestroy(p);
    sqlite4DbFree(db, pArg);
  }

 out:
  rc = sqlite4ApiExit(db, rc);
  sqlite4_mutex_leave(db->mutex);
  return rc;
}

int sqlite4_create_mi_function(
  sqlite4 *db,
  const char *zFunc,
  int nArg,
  int enc,
  void *p,
  void (*xFunc)(sqlite4_context*,int,sqlite4_value **),
  void (*xDestroy)(void *)
){
  int rc;
  int n;

  n = nArg + (nArg>=0);
  sqlite4_mutex_enter(db->mutex);
  rc = sqlite4_create_function_v2(db, zFunc, n, enc, p, xFunc, 0,0,xDestroy);
  if( rc==SQLITE4_OK ){
    FuncDef *p = sqlite4FindFunction(db, zFunc, -1, n, enc, 0);
    p->bMatchinfo = 1;
  }
  rc = sqlite4ApiExit(db, rc);
  sqlite4_mutex_leave(db->mutex);
  return rc;
}

#ifndef SQLITE4_OMIT_UTF16
int sqlite4_create_function16(

Changes to src/resolve.c.

431
432
433
434
435
436
437




























438
439
440
441
442
443
444
...
612
613
614
615
616
617
618





619
620
621


622
623
624
625
626
627
628
    testcase( iCol==BMS );
    testcase( iCol==BMS-1 );
    pItem->colUsed |= ((Bitmask)1)<<(iCol>=BMS ? BMS-1 : iCol);
    ExprSetProperty(p, EP_Resolved);
  }
  return p;
}





























static void resolveMatch(Parse *pParse, NameContext *pNC, Expr *pExpr){
  Expr *pLeft = pExpr->pLeft;
  SrcList *pSrc = pNC->pSrcList;
  SrcListItem *pItem;
  char *zLhs;
  int i;
................................................................................
             nId, zId);
        pNC->nErr++;
      }
      if( is_agg ){
        pExpr->op = TK_AGG_FUNCTION;
        pNC->hasAgg = 1;
      }





      if( is_agg ) pNC->allowAgg = 0;
      sqlite4WalkExprList(pWalker, pList);
      if( is_agg ) pNC->allowAgg = 1;


      /* FIX ME:  Compute pExpr->affinity based on the expected return
      ** type of the function 
      */
      return WRC_Prune;
    }
#ifndef SQLITE4_OMIT_SUBQUERY
    case TK_SELECT:







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







 







>
>
>
>
>
|
|
|
>
>







431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
...
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
    testcase( iCol==BMS );
    testcase( iCol==BMS-1 );
    pItem->colUsed |= ((Bitmask)1)<<(iCol>=BMS ? BMS-1 : iCol);
    ExprSetProperty(p, EP_Resolved);
  }
  return p;
}

static void resolveMatchArg(Parse *pParse, NameContext *pNC, Expr *pExpr){
  SrcList *pSrc = pNC->pSrcList;
  SrcListItem *pItem;
  char *zLhs;
  int i;
  Index *pIdx;

  if( pExpr->op!=TK_ID || pSrc==0 || pExpr==0 ){
    sqlite4ErrorMsg(pParse, "first argument xxx must be a table name");
    return;
  }
  zLhs = pExpr->u.zToken;

  for(i=0; i<pSrc->nSrc; i++){
    pItem = &pSrc->a[i];
    if( pItem->zAlias && sqlite4StrICmp(zLhs, pItem->zAlias)==0 ) break;
    if( pItem->zAlias==0 && sqlite4StrICmp(zLhs, pItem->zName)==0 ) break;
  }
  if( i==pSrc->nSrc ){
    sqlite4ErrorMsg(pParse, "no such table: %s", zLhs);
    return;
  }

  pExpr->op = TK_NULL;
  pExpr->iTable = pItem->iCursor;
  ExprSetProperty(pExpr, EP_Resolved);
}

static void resolveMatch(Parse *pParse, NameContext *pNC, Expr *pExpr){
  Expr *pLeft = pExpr->pLeft;
  SrcList *pSrc = pNC->pSrcList;
  SrcListItem *pItem;
  char *zLhs;
  int i;
................................................................................
             nId, zId);
        pNC->nErr++;
      }
      if( is_agg ){
        pExpr->op = TK_AGG_FUNCTION;
        pNC->hasAgg = 1;
      }

      if( pParse->nErr==0 ){
        if( pDef->bMatchinfo ){
          resolveMatchArg(pParse, pNC, n>0 ? pList->a[0].pExpr : 0);
        }
        if( is_agg ) pNC->allowAgg = 0;
        sqlite4WalkExprList(pWalker, pList);
        if( is_agg ) pNC->allowAgg = 1;
      }

      /* FIX ME:  Compute pExpr->affinity based on the expected return
      ** type of the function 
      */
      return WRC_Prune;
    }
#ifndef SQLITE4_OMIT_SUBQUERY
    case TK_SELECT:

Changes to src/sqlite.h.in.

4399
4400
4401
4402
4403
4404
4405
4406
4407










































































































4408
4409
4410
4411
4412
4413
4414
4415
4416
4417
4418
  int (*xTokenize)(void*, sqlite4_tokenizer*,
      const char*, int, 
      int(*x)(void *ctx, int iWeight, int iOff, 
              const char *zToken, int nToken, int iSrc, int nSrc)
  ),
  int (*xDestroy)(sqlite4_tokenizer *)
);

/*










































































































** Undo the hack that converts floating point types to integer for
** builds on processors without floating point support.
*/
#ifdef SQLITE4_OMIT_FLOATING_POINT
# undef double
#endif

#ifdef __cplusplus
}  /* End of the 'extern "C"' block */
#endif
#endif









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











4399
4400
4401
4402
4403
4404
4405
4406
4407
4408
4409
4410
4411
4412
4413
4414
4415
4416
4417
4418
4419
4420
4421
4422
4423
4424
4425
4426
4427
4428
4429
4430
4431
4432
4433
4434
4435
4436
4437
4438
4439
4440
4441
4442
4443
4444
4445
4446
4447
4448
4449
4450
4451
4452
4453
4454
4455
4456
4457
4458
4459
4460
4461
4462
4463
4464
4465
4466
4467
4468
4469
4470
4471
4472
4473
4474
4475
4476
4477
4478
4479
4480
4481
4482
4483
4484
4485
4486
4487
4488
4489
4490
4491
4492
4493
4494
4495
4496
4497
4498
4499
4500
4501
4502
4503
4504
4505
4506
4507
4508
4509
4510
4511
4512
4513
4514
4515
4516
4517
4518
4519
4520
4521
4522
4523
4524
  int (*xTokenize)(void*, sqlite4_tokenizer*,
      const char*, int, 
      int(*x)(void *ctx, int iWeight, int iOff, 
              const char *zToken, int nToken, int iSrc, int nSrc)
  ),
  int (*xDestroy)(sqlite4_tokenizer *)
);

/*
** CAPI4REF: Register a matchinfo function.
*/
int sqlite4_create_mi_function(
  sqlite4 *db,
  const char *zFunc,
  int nArg,
  int enc,
  void *p,
  void (*xFunc)(sqlite4_context*,int,sqlite4_value **),
  void (*xDestroy)(void *)
);

/*
** CAPIREF: Matchinfo APIs.
**
** Special functions that may be called from within matchinfo UDFs. All
** return an SQLite error code - SQLITE4_OK if successful, or some other
** error code otherwise.
**
** sqlite4_mi_column_count():
**   Set *pn to the number of columns in the queried table.
**
** sqlite4_mi_phrase_count():
**   Set *pn to the number of phrases in the query.
**
** sqlite4_mi_stream_count():
**   Set *pn to the number of streams in the FTS index.
**
** sqlite4_mi_phrase_token_count():
**   Set *pn to the number of tokens in phrase iP of the query.
**
** sqlite4_mi_size():
**   Set *pn to the number of tokens belonging to stream iS in the value 
**   stored in column iC of the current row. 
**
**   Either or both of iS and iC may be negative. If iC is negative, then the
**   output value is the total number of tokens for the specified stream (or
**   streams) across all table columns. Similarly, if iS is negative, the 
**   output value is the total number of tokens in the specified column or 
**   columns, regardless of stream.
**
** sqlite4_mi_total_size():
**   Similar to sqlite4_mi_size(), except the output parameter is set to
**   the total number of tokens belonging to the specified column(s) 
**   and stream(s) in all rows of the table, not just the current row.
**
** sqlite4_mi_total_rows():
**   Set *pn to the total number of rows in the indexed table.
**
** sqlite4_mi_row_count():
**   Set the output parameter to the total number of rows in the table that
**   contain at least one instance of the phrase identified by parameter
**   iP in the column(s) and stream(s) identified by parameters iC and iS.
**
** sqlite4_mi_match_count():
**   Set the output parameter to the total number of occurences of phrase
**   iP in the current row that belong to the column(s) and stream(s) 
**   identified by parameters iC and iS.
**
**   Parameter iP may also be negative. In this case, the output value is
**   set to the total number of occurrences of all query phrases in the
**   current row, subject to the constraints imposed by iC and iS.
**
** sqlite4_mi_match_detail():
**   This function is used to access the details of the iMatch'th match
**   (of any phrase) in the current row. Matches are sorted in order of
**   occurrence. If parameter iMatch is equal to or greater than the number 
**   of matches in the current row, SQLITE_NOTFOUND is returned. Otherwise,
**   unless an error occurs, SQLITE4_OK is returned and the *piOff, *piC, *piS,
**   and *piP output parameters are set to the token offset, column number,
**   stream number and phrase number respectively.
**
**   It is anticipated that this function be used to iterate through matches 
**   in order of occurrence. It is optimized so that it is fastest when 
**   called with the iMatch parameter set to 0, P or P+1, where P is the 
**   iMatch value passed to the previous call.
**
** sqlite4_mi_column_value():
**   Set *ppVal to point to an sqlite4_value object containing the value
**   read from column iCol of the current row. This object is valid until
**   the function callback returns.
*/
int sqlite4_mi_column_count(sqlite4_context *, int *pn);
int sqlite4_mi_phrase_count(sqlite4_context *, int *pn);
int sqlite4_mi_stream_count(sqlite4_context *, int *pn);
int sqlite4_mi_phrase_token_count(sqlite4_context *, int iP, int *pn);

int sqlite4_mi_total_size(sqlite4_context *, int iC, int iS, int *pn);
int sqlite4_mi_total_rows(sqlite4_context *, int *pn);

int sqlite4_mi_row_count(sqlite4_context *, int iC, int iS, int iP, int *pn);

int sqlite4_mi_size(sqlite4_context *, int iC, int iS, int *pn);
int sqlite4_mi_match_count(sqlite4_context *, int iC, int iS, int iP, int *pn);
int sqlite4_mi_match_detail(
    sqlite4_context *, int iMatch, int *piOff, int *piC, int *piS, int *piP
);
int sqlite4_mi_column_value(sqlite4_context *, int iC, sqlite4_value **ppVal);

int sqlite4_mi_tokenize(sqlite4_context *, const char *, int, void *,
  int(*x)(void *, int, int, const char *, int, int, int)
);



/*
** Undo the hack that converts floating point types to integer for
** builds on processors without floating point support.
*/
#ifdef SQLITE4_OMIT_FLOATING_POINT
# undef double
#endif

#ifdef __cplusplus
}  /* End of the 'extern "C"' block */
#endif
#endif

Changes to src/sqliteInt.h.

635
636
637
638
639
640
641

642
643
644
645
646
647
648
....
2484
2485
2486
2487
2488
2489
2490

2491
2492
2493
2494
2495
2496
2497
....
3275
3276
3277
3278
3279
3280
3281
3282






3283
  FuncDef *pSameName;  /* Next with a different name but the same hash */
  void (*xFunc)(sqlite4_context*,int,sqlite4_value**); /* Regular function */
  void (*xStep)(sqlite4_context*,int,sqlite4_value**); /* Aggregate step */
  void (*xFinalize)(sqlite4_context*);                /* Aggregate finalizer */
  char *zName;         /* SQL name of the function. */
  FuncDef *pNextName;  /* Next function with a different name */
  FuncDestructor *pDestructor;   /* Reference counted destructor function */

};

/*
** A table of SQL functions.  
**
** The content is a linked list of FuncDef structures with branches.  When
** there are two or more FuncDef objects with the same name, they are 
................................................................................
/*
** An instance of this structure is used as the p4 argument to some fts5
** related vdbe opcodes.
*/
struct Fts5Info {
  int iDb;                        /* Database containing this index */
  int iRoot;                      /* Root page number of index */

  int nCol;                       /* Number of columns in indexed table */
  char **azCol;                   /* Column names for table */
  Fts5Tokenizer *pTokenizer;      /* Tokenizer module */
  sqlite4_tokenizer *p;           /* Tokenizer instance */
};

int sqlite4WalkExpr(Walker*, Expr*);
................................................................................
void sqlite4Fts5FreeInfo(sqlite4 *db, Fts5Info *);
void sqlite4Fts5CodeUpdate(Parse *, Index *pIdx, int iRegPk, int iRegData, int);
void sqlite4Fts5CodeCksum(Parse *, Index *, int, int, int);
void sqlite4Fts5CodeQuery(Parse *, Index *, int, int, int);

int sqlite4Fts5Pk(Fts5Cursor *, int, KVByteArray **, KVSize *);
int sqlite4Fts5Next(Fts5Cursor *pCsr);







#endif /* _SQLITEINT_H_ */







>







 







>







 








>
>
>
>
>
>

635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
....
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
....
3277
3278
3279
3280
3281
3282
3283
3284
3285
3286
3287
3288
3289
3290
3291
  FuncDef *pSameName;  /* Next with a different name but the same hash */
  void (*xFunc)(sqlite4_context*,int,sqlite4_value**); /* Regular function */
  void (*xStep)(sqlite4_context*,int,sqlite4_value**); /* Aggregate step */
  void (*xFinalize)(sqlite4_context*);                /* Aggregate finalizer */
  char *zName;         /* SQL name of the function. */
  FuncDef *pNextName;  /* Next function with a different name */
  FuncDestructor *pDestructor;   /* Reference counted destructor function */
  u8 bMatchinfo;       /* True for matchinfo function */
};

/*
** A table of SQL functions.  
**
** The content is a linked list of FuncDef structures with branches.  When
** there are two or more FuncDef objects with the same name, they are 
................................................................................
/*
** An instance of this structure is used as the p4 argument to some fts5
** related vdbe opcodes.
*/
struct Fts5Info {
  int iDb;                        /* Database containing this index */
  int iRoot;                      /* Root page number of index */
  int iTbl;                       /* Root page number of indexed table */
  int nCol;                       /* Number of columns in indexed table */
  char **azCol;                   /* Column names for table */
  Fts5Tokenizer *pTokenizer;      /* Tokenizer module */
  sqlite4_tokenizer *p;           /* Tokenizer instance */
};

int sqlite4WalkExpr(Walker*, Expr*);
................................................................................
void sqlite4Fts5FreeInfo(sqlite4 *db, Fts5Info *);
void sqlite4Fts5CodeUpdate(Parse *, Index *pIdx, int iRegPk, int iRegData, int);
void sqlite4Fts5CodeCksum(Parse *, Index *, int, int, int);
void sqlite4Fts5CodeQuery(Parse *, Index *, int, int, int);

int sqlite4Fts5Pk(Fts5Cursor *, int, KVByteArray **, KVSize *);
int sqlite4Fts5Next(Fts5Cursor *pCsr);

int sqlite4Fts5EntryCksum(sqlite4 *, Fts5Info *, Mem *, Mem *, i64 *);
int sqlite4Fts5RowCksum(sqlite4 *, Fts5Info *, Mem *, Mem *, i64 *);
int sqlite4Fts5Open(sqlite4*, Fts5Info*, const char*, int, Fts5Cursor**,char**);
int sqlite4Fts5Valid(Fts5Cursor *);
void sqlite4Fts5Close(Fts5Cursor *);

#endif /* _SQLITEINT_H_ */

Changes to src/vdbe.c.

1285
1286
1287
1288
1289
1290
1291








1292
1293
1294
1295
1296
1297
1298
....
1340
1341
1342
1343
1344
1345
1346







1347
1348
1349
1350
1351
1352
1353
** to retrieve the collation sequence set by this opcode is not available
** publicly, only to user functions defined in func.c.
*/
case OP_CollSeq: {
  assert( pOp->p4type==P4_COLLSEQ );
  break;
}









/* Opcode: Function P1 P2 P3 P4 P5
**
** Invoke a user function (P4 is a pointer to a Function structure that
** defines the function) with P5 arguments taken from register P2 and
** successors.  The result of the function is stored in register P3.
** Register P3 must not be one of the function inputs.
................................................................................
    ctx.pFunc = ctx.pVdbeFunc->pFunc;
  }

  ctx.s.flags = MEM_Null;
  ctx.s.db = db;
  ctx.s.xDel = 0;
  ctx.s.zMalloc = 0;








  /* The output cell may already have a buffer allocated. Move
  ** the pointer to ctx.s so in case the user-function can use
  ** the already allocated buffer instead of allocating a new one.
  */
  sqlite4VdbeMemMove(&ctx.s, pOut);
  MemSetTypeFlag(&ctx.s, MEM_Null);







>
>
>
>
>
>
>
>







 







>
>
>
>
>
>
>







1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
....
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
** to retrieve the collation sequence set by this opcode is not available
** publicly, only to user functions defined in func.c.
*/
case OP_CollSeq: {
  assert( pOp->p4type==P4_COLLSEQ );
  break;
}

/* Opcode: Mifunction P1
*/
case OP_Mifunction: {
  pc++;
  pOp++;
  /* fall through to OP_Function */
};

/* Opcode: Function P1 P2 P3 P4 P5
**
** Invoke a user function (P4 is a pointer to a Function structure that
** defines the function) with P5 arguments taken from register P2 and
** successors.  The result of the function is stored in register P3.
** Register P3 must not be one of the function inputs.
................................................................................
    ctx.pFunc = ctx.pVdbeFunc->pFunc;
  }

  ctx.s.flags = MEM_Null;
  ctx.s.db = db;
  ctx.s.xDel = 0;
  ctx.s.zMalloc = 0;
  if( pOp[-1].opcode==OP_Mifunction ){
    ctx.pFts = p->apCsr[pOp[-1].p1]->pFts;
    apVal++;
    n--;
  }else{
    ctx.pFts = 0;
  }

  /* The output cell may already have a buffer allocated. Move
  ** the pointer to ctx.s so in case the user-function can use
  ** the already allocated buffer instead of allocating a new one.
  */
  sqlite4VdbeMemMove(&ctx.s, pOut);
  MemSetTypeFlag(&ctx.s, MEM_Null);

Changes to src/vdbeInt.h.

237
238
239
240
241
242
243

244
245
246
247
248
249
250
struct sqlite4_context {
  FuncDef *pFunc;       /* Pointer to function information.  MUST BE FIRST */
  VdbeFunc *pVdbeFunc;  /* Auxilary data, if created. */
  Mem s;                /* The return value is stored here */
  Mem *pMem;            /* Memory cell used to store aggregate context */
  int isError;          /* Error code returned by the function. */
  CollSeq *pColl;       /* Collating sequence */

};

/*
** An Explain object accumulates indented output which is helpful
** in describing recursive data structures.
*/
struct Explain {







>







237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
struct sqlite4_context {
  FuncDef *pFunc;       /* Pointer to function information.  MUST BE FIRST */
  VdbeFunc *pVdbeFunc;  /* Auxilary data, if created. */
  Mem s;                /* The return value is stored here */
  Mem *pMem;            /* Memory cell used to store aggregate context */
  int isError;          /* Error code returned by the function. */
  CollSeq *pColl;       /* Collating sequence */
  Fts5Cursor *pFts;     /* fts5 cursor for matchinfo functions */
};

/*
** An Explain object accumulates indented output which is helpful
** in describing recursive data structures.
*/
struct Explain {

Changes to src/vdbeaux.c.

1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
** Close a VDBE cursor and release all the resources that cursor 
** happens to hold.
*/
void sqlite4VdbeFreeCursor(Vdbe *p, VdbeCursor *pCx){
  if( pCx==0 ){
    return;
  }
  sqlite4Fts5Close(p->db, pCx->pFts);
  if( pCx->pKVCur ){
    sqlite4KVCursorClose(pCx->pKVCur);
  }
  if( pCx->pTmpKV ){
    sqlite4KVStoreClose(pCx->pTmpKV);
  }
#ifndef SQLITE4_OMIT_VIRTUALTABLE







|







1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
** Close a VDBE cursor and release all the resources that cursor 
** happens to hold.
*/
void sqlite4VdbeFreeCursor(Vdbe *p, VdbeCursor *pCx){
  if( pCx==0 ){
    return;
  }
  sqlite4Fts5Close(pCx->pFts);
  if( pCx->pKVCur ){
    sqlite4KVCursorClose(pCx->pKVCur);
  }
  if( pCx->pTmpKV ){
    sqlite4KVStoreClose(pCx->pTmpKV);
  }
#ifndef SQLITE4_OMIT_VIRTUALTABLE

Changes to src/where.c.

5225
5226
5227
5228
5229
5230
5231


















5232
5233
5234
5235
5236
5237
5238
5239
      while( pOp<pEnd ){
        if( pOp->p1==pLevel->iTabCur && pOp->opcode==OP_Column ){
          pOp->p1 = pLevel->iIdxCur;
        }
        pOp++;
      }
    }


















  }

  /* Final cleanup
  */
  pParse->nQueryLoop = pWInfo->savedNQueryLoop;
  whereInfoFree(db, pWInfo);
  return;
}







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








5225
5226
5227
5228
5229
5230
5231
5232
5233
5234
5235
5236
5237
5238
5239
5240
5241
5242
5243
5244
5245
5246
5247
5248
5249
5250
5251
5252
5253
5254
5255
5256
5257
      while( pOp<pEnd ){
        if( pOp->p1==pLevel->iTabCur && pOp->opcode==OP_Column ){
          pOp->p1 = pLevel->iIdxCur;
        }
        pOp++;
      }
    }

    if( (pLevel->plan.wsFlags & WHERE_INDEXED)
     && (pLevel->plan.u.pIdx->eIndexType==SQLITE4_INDEX_FTS5)
    ){
      VdbeOp *pOp;
      VdbeOp *pEnd;

      assert( pLevel->iTabCur!=pLevel->iIdxCur );
      pOp = sqlite4VdbeGetOp(v, pWInfo->iTop);
      pEnd = &pOp[sqlite4VdbeCurrentAddr(v) - pWInfo->iTop];

      while( pOp<pEnd ){
        if( pOp->p1==pLevel->iTabCur && pOp->opcode==OP_Mifunction ){
          pOp->p1 = pLevel->iIdxCur;
        }
        pOp++;
      }
    }
  }

  /* Final cleanup
  */
  pParse->nQueryLoop = pWInfo->savedNQueryLoop;
  whereInfoFree(db, pWInfo);
  return;
}

Changes to test/csr1.test.

73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
# tree to be flushed to disk, 
#
populate_db_2
do_execsql_test 3.1 {
  BEGIN;
    INSERT INTO t1 VALUES(10, randstr(910, 910));
}
do_test 3.2 { sqlite4_lsm_config db main autoflush } [expr 2*1024*1024]
do_test 3.3 { sqlite4_lsm_config db main autoflush 4096 } 4096

do_test 3.4 {
  set res [list]
  db eval { SELECT a, length(b) AS l FROM t1 } {
    lappend res $a $l
    # The following commit will flush the in-memory tree to disk.







|







73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
# tree to be flushed to disk, 
#
populate_db_2
do_execsql_test 3.1 {
  BEGIN;
    INSERT INTO t1 VALUES(10, randstr(910, 910));
}
do_test 3.2 { sqlite4_lsm_config db main autoflush } [expr 1*1024*1024]
do_test 3.3 { sqlite4_lsm_config db main autoflush 4096 } 4096

do_test 3.4 {
  set res [list]
  db eval { SELECT a, length(b) AS l FROM t1 } {
    lappend res $a $l
    # The following commit will flush the in-memory tree to disk.

Changes to test/fts5create.test.

70
71
72
73
74
75
76

77
78
79
80
81
82
83
84
  CREATE INDEX ft ON t2 USING fts5(tukenizer=simple);
} {1 {unrecognized argument: "tukenizer"}}

do_catchsql_test 2.3 { 
  CREATE INDEX ft ON t2 USING fts5("a b c");
} {1 {unrecognized argument: "a b c"}}


do_catchsql_test 2.4 { 
  CREATE INDEX ft ON t2 USING fts5(tokenizer="nosuch");
} {1 {no such tokenizer: "nosuch"}}

finish_test










>
|






<
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

  CREATE INDEX ft ON t2 USING fts5(tukenizer=simple);
} {1 {unrecognized argument: "tukenizer"}}

do_catchsql_test 2.3 { 
  CREATE INDEX ft ON t2 USING fts5("a b c");
} {1 {unrecognized argument: "a b c"}}

breakpoint
do_catchsql_test 2.4 {
  CREATE INDEX ft ON t2 USING fts5(tokenizer="nosuch");
} {1 {no such tokenizer: "nosuch"}}

finish_test



Changes to test/fts5query1.test.

130
131
132
133
134
135
136
137













































138
139
  2 {a:a}  {1}
  3 {b:a}  {2}
  4 {c:a}  {1 2}
  5 {a:a*} {1}
} {
  do_execsql_test 7.$tn {SELECT docid FROM t7 WHERE t7 MATCH $expr} $res
}














































finish_test









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


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
  2 {a:a}  {1}
  3 {b:a}  {2}
  4 {c:a}  {1 2}
  5 {a:a*} {1}
} {
  do_execsql_test 7.$tn {SELECT docid FROM t7 WHERE t7 MATCH $expr} $res
}

#-------------------------------------------------------------------------
#
do_execsql_test 8.0 {
  CREATE TABLE t8(a PRIMARY KEY, b, c);
  CREATE INDEX i8 ON t8 USING fts5();
  INSERT INTO t8 VALUES('one', 'a b c', 'a a a');
  INSERT INTO t8 VALUES('two', 'd e f', 'b b b');
}

#do_execsql_test 8.1 {
#  SELECT rank(t8) FROM t8 WHERE t8 MATCH 'b a'
#}

do_execsql_test 9.0 {
  CREATE TABLE t9(a PRIMARY KEY, b);
  CREATE INDEX i9 ON t9 USING fts5();
  INSERT INTO t9 VALUES('one', 
    '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 ' ||
    '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'
  );
}

#do_execsql_test 9.1 {
#  SELECT snippet(t9) FROM t9 WHERE t9 MATCH 'b'
#} 

do_execsql_test 10.1 {
  CREATE TABLE ft(content);
  CREATE INDEX fti ON ft USING fts5();
}
do_execsql_test 10.2 {
  INSERT INTO ft VALUES('a b c d e');
  INSERT INTO ft VALUES('f g h i j');
}
do_execsql_test 10.3 { SELECT rowid FROM ft WHERE ft MATCH 'c' } {1}
do_execsql_test 10.4 { SELECT rowid FROM ft WHERE ft MATCH 'f' } {2}

do_execsql_test 10.5 {
  DELETE FROM ft;
  CREATE TABLE ft2(a, b, c);
  CREATE INDEX fti2 ON ft2 USING fts5();
  INSERT INTO ft2 VALUES('1 2 3 4 5', '6 7 8 9 10', '11 12 13 14 15');
  SELECT snippet(ft2, '[', ']', '...', -1, 3) FROM ft2 WHERE ft2 MATCH '5';
} {{...3 4 [5]}}

finish_test

Added test/fts5snippet.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
# 2013 January 10
#
# 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.
#
#*************************************************************************
#
# The tests in this file test the FTS5 snippet() function.
#

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

# If SQLITE4_ENABLE_FTS3 is not defined, omit this file.
source $testdir/fts3_common.tcl

set DO_MALLOC_TEST 0

# Transform the list $L to its "normal" form. So that it can be compared to
# another list with the same set of elements using [string compare].
#
proc normalize {L} {
  set ret [list]
  foreach l $L {lappend ret $l}
  return $ret
}

# Document text used by a few tests. Contains the English names of all
# integers between 1 and 300.
#
set numbers [normalize {
  one two three four five six seven eight nine ten eleven twelve thirteen
  fourteen fifteen sixteen seventeen eighteen nineteen twenty twentyone
  twentytwo twentythree twentyfour twentyfive twentysix twentyseven
  twentyeight twentynine thirty thirtyone thirtytwo thirtythree thirtyfour
  thirtyfive thirtysix thirtyseven thirtyeight thirtynine forty fortyone
  fortytwo fortythree fortyfour fortyfive fortysix fortyseven fortyeight
  fortynine fifty fiftyone fiftytwo fiftythree fiftyfour fiftyfive fiftysix
  fiftyseven fiftyeight fiftynine sixty sixtyone sixtytwo sixtythree sixtyfour
  sixtyfive sixtysix sixtyseven sixtyeight sixtynine seventy seventyone
  seventytwo seventythree seventyfour seventyfive seventysix seventyseven
  seventyeight seventynine eighty eightyone eightytwo eightythree eightyfour
  eightyfive eightysix eightyseven eightyeight eightynine ninety ninetyone
  ninetytwo ninetythree ninetyfour ninetyfive ninetysix ninetyseven
  ninetyeight ninetynine onehundred onehundredone onehundredtwo
  onehundredthree onehundredfour onehundredfive onehundredsix onehundredseven
  onehundredeight onehundrednine onehundredten onehundredeleven
  onehundredtwelve onehundredthirteen onehundredfourteen onehundredfifteen
  onehundredsixteen onehundredseventeen onehundredeighteen onehundrednineteen
  onehundredtwenty onehundredtwentyone onehundredtwentytwo
  onehundredtwentythree onehundredtwentyfour onehundredtwentyfive
  onehundredtwentysix onehundredtwentyseven onehundredtwentyeight
  onehundredtwentynine onehundredthirty onehundredthirtyone
  onehundredthirtytwo onehundredthirtythree onehundredthirtyfour
  onehundredthirtyfive onehundredthirtysix onehundredthirtyseven
  onehundredthirtyeight onehundredthirtynine onehundredforty
  onehundredfortyone onehundredfortytwo onehundredfortythree
  onehundredfortyfour onehundredfortyfive onehundredfortysix
  onehundredfortyseven onehundredfortyeight onehundredfortynine
  onehundredfifty onehundredfiftyone onehundredfiftytwo onehundredfiftythree
  onehundredfiftyfour onehundredfiftyfive onehundredfiftysix
  onehundredfiftyseven onehundredfiftyeight onehundredfiftynine
  onehundredsixty onehundredsixtyone onehundredsixtytwo onehundredsixtythree
  onehundredsixtyfour onehundredsixtyfive onehundredsixtysix
  onehundredsixtyseven onehundredsixtyeight onehundredsixtynine
  onehundredseventy onehundredseventyone onehundredseventytwo
  onehundredseventythree onehundredseventyfour onehundredseventyfive
  onehundredseventysix onehundredseventyseven onehundredseventyeight
  onehundredseventynine onehundredeighty onehundredeightyone
  onehundredeightytwo onehundredeightythree onehundredeightyfour
  onehundredeightyfive onehundredeightysix onehundredeightyseven
  onehundredeightyeight onehundredeightynine onehundredninety
  onehundredninetyone onehundredninetytwo onehundredninetythree
  onehundredninetyfour onehundredninetyfive onehundredninetysix
  onehundredninetyseven onehundredninetyeight onehundredninetynine twohundred
  twohundredone twohundredtwo twohundredthree twohundredfour twohundredfive
  twohundredsix twohundredseven twohundredeight twohundrednine twohundredten
  twohundredeleven twohundredtwelve twohundredthirteen twohundredfourteen
  twohundredfifteen twohundredsixteen twohundredseventeen twohundredeighteen
  twohundrednineteen twohundredtwenty twohundredtwentyone twohundredtwentytwo
  twohundredtwentythree twohundredtwentyfour twohundredtwentyfive
  twohundredtwentysix twohundredtwentyseven twohundredtwentyeight
  twohundredtwentynine twohundredthirty twohundredthirtyone
  twohundredthirtytwo twohundredthirtythree twohundredthirtyfour
  twohundredthirtyfive twohundredthirtysix twohundredthirtyseven
  twohundredthirtyeight twohundredthirtynine twohundredforty
  twohundredfortyone twohundredfortytwo twohundredfortythree
  twohundredfortyfour twohundredfortyfive twohundredfortysix
  twohundredfortyseven twohundredfortyeight twohundredfortynine
  twohundredfifty twohundredfiftyone twohundredfiftytwo twohundredfiftythree
  twohundredfiftyfour twohundredfiftyfive twohundredfiftysix
  twohundredfiftyseven twohundredfiftyeight twohundredfiftynine
  twohundredsixty twohundredsixtyone twohundredsixtytwo twohundredsixtythree
  twohundredsixtyfour twohundredsixtyfive twohundredsixtysix
  twohundredsixtyseven twohundredsixtyeight twohundredsixtynine
  twohundredseventy twohundredseventyone twohundredseventytwo
  twohundredseventythree twohundredseventyfour twohundredseventyfive
  twohundredseventysix twohundredseventyseven twohundredseventyeight
  twohundredseventynine twohundredeighty twohundredeightyone
  twohundredeightytwo twohundredeightythree twohundredeightyfour
  twohundredeightyfive twohundredeightysix twohundredeightyseven
  twohundredeightyeight twohundredeightynine twohundredninety
  twohundredninetyone twohundredninetytwo twohundredninetythree
  twohundredninetyfour twohundredninetyfive twohundredninetysix
  twohundredninetyseven twohundredninetyeight twohundredninetynine
  threehundred
}]

foreach {DO_MALLOC_TEST enc} {
  0 utf8
  1 utf8
  1 utf16
} {
if {$DO_MALLOC_TEST || $enc=="utf16"} continue

  db close
  forcedelete test.db
  sqlite4 db test.db
  sqlite4_db_config_lookaside db 0 0 0
  db eval "PRAGMA encoding = \"$enc\""

  # Set variable $T to the test name prefix for this iteration of the loop.
  #
  set T "fts5snippet-$enc"
  
  ##########################################################################
  # Test the snippet function.
  #
  proc do_snippet_test {name expr iCol nTok args} {
    set res [list]
    foreach a $args { lappend res [string trim $a] }
    do_select_test $name {
      SELECT snippet(ft,'{','}','...',$iCol,$nTok) FROM ft WHERE ft MATCH $expr
    } $res
  }
  do_test $T.3.1 {
    execsql {
      DROP TABLE IF EXISTS ft;
      CREATE TABLE ft(content);
      CREATE INDEX fti ON ft USING fts5();

      INSERT INTO ft VALUES('one two three four five six seven eight nine ten');
    }
  } {}
  do_snippet_test $T.3.2  one    0 5 "{one} two three four five..."
  do_snippet_test $T.3.3  two    0 5 "one {two} three four five..."
  do_snippet_test $T.3.4  three  0 5 "one two {three} four five..."
  do_snippet_test $T.3.5  four   0 5 "...two three {four} five six..."
  do_snippet_test $T.3.6  five   0 5 "...three four {five} six seven..."
  do_snippet_test $T.3.7  six    0 5 "...four five {six} seven eight..."
  do_snippet_test $T.3.8  seven  0 5 "...five six {seven} eight nine..."
  do_snippet_test $T.3.9  eight  0 5 "...six seven {eight} nine ten"
  do_snippet_test $T.3.10 nine   0 5 "...six seven eight {nine} ten"
  do_snippet_test $T.3.11 ten    0 5 "...six seven eight nine {ten}"
  
  do_test $T.4.1 {
    execsql {
      INSERT INTO ft VALUES(
           'one two three four five '
        || 'six seven eight nine ten '
        || 'eleven twelve thirteen fourteen fifteen '
        || 'sixteen seventeen eighteen nineteen twenty '
        || 'one two three four five '
        || 'six seven eight nine ten '
        || 'eleven twelve thirteen fourteen fifteen '
        || 'sixteen seventeen eighteen nineteen twenty'
      );
    }
  } {}
  
  do_snippet_test $T.4.2 {one nine} 0 5 {
     {one} two three...eight {nine} ten
  } {
     {one} two three...eight {nine} ten...
  }
  
  do_snippet_test $T.4.3 {one nine} 0 -5 {
     {one} two three four five...six seven eight {nine} ten
  } {
     {one} two three four five...seven eight {nine} ten eleven...
  }
  do_snippet_test $T.4.3 {one nineteen} 0 -5 {
     ...eighteen {nineteen} twenty {one} two...
  }
  do_snippet_test $T.4.4 {two nineteen} 0 -5 {
     ...eighteen {nineteen} twenty one {two}...
  }
  do_snippet_test $T.4.5 {three nineteen} 0 -5 {
     ...{nineteen} twenty one two {three}...
  }
  
  do_snippet_test $T.4.6 {four nineteen} 0 -5 {
     ...two three {four} five six...seventeen eighteen {nineteen} twenty one...
  }
  do_snippet_test $T.4.7 {four NEAR nineteen} 0 -5 {
     ...seventeen eighteen {nineteen} twenty one...two three {four} five six...
  }
  
  do_snippet_test $T.4.8 {four nineteen} 0 5 {
     ...three {four} five...eighteen {nineteen} twenty...
  }
  do_snippet_test $T.4.9 {four NEAR nineteen} 0 5 {
     ...eighteen {nineteen} twenty...three {four} five...
  }
  do_snippet_test $T.4.10 {four NEAR nineteen} 0 -5 {
     ...seventeen eighteen {nineteen} twenty one...two three {four} five six...
  }
  do_snippet_test $T.4.11 {four NOT (nineteen+twentyone)} 0 5 {
     ...two three {four} five six...
  } {
     ...two three {four} five six...
  }
  do_snippet_test $T.4.12 {four OR nineteen NEAR twentyone} 0 5 {
     ...two three {four} five six...
  } {
     ...two three {four} five six...
  }
  
  do_test $T.5.1 {
    execsql {
      DROP TABLE IF EXISTS ft;
      CREATE TABLE ft(a, b, c);
      CREATE INDEX fti ON ft USING fts5();
      INSERT INTO ft VALUES(
        'one two three four five', 
        'four five six seven eight', 
        'seven eight nine ten eleven'
      );
    }
  } {}
  
  do_snippet_test $T.5.2 {five} -1 3 {...three four {five}}
  do_snippet_test $T.5.3 {five}  0 3 {...three four {five}}
  do_snippet_test $T.5.4 {five}  1 3 {four {five} six...}
  do_snippet_test $T.5.5 {five}  2 3 {seven eight nine...}
  
  do_test $T.5.6 {
    execsql { UPDATE ft SET b = NULL }
  } {}
  
  do_snippet_test $T.5.7  {five} -1 3 {...three four {five}}
  do_snippet_test $T.5.8  {five}  0 3 {...three four {five}}
  do_snippet_test $T.5.9  {five}  1 3 {}
  do_snippet_test $T.5.10 {five}  2 3 {seven eight nine...}
  
  do_snippet_test $T.5.11 {one "seven eight nine"} -1 -3 {
    {one} two three...{seven} {eight} {nine}...
  }

  do_test $T.6.1 {
    execsql {
      DROP TABLE IF EXISTS ft;
      CREATE TABLE ft(x);
      CREATE INDEX fti ON ft USING fts5();
      INSERT INTO ft VALUES($numbers);
    }
  } {}
  do_snippet_test $T.6.2 {
    one fifty onehundred onehundredfifty twohundredfifty threehundred
  } -1 4 {
    {one}...{fifty}...{onehundred}...{onehundredfifty}...
  }
  do_snippet_test $T.6.3 {
    one fifty onehundred onehundredfifty twohundredfifty threehundred
  } -1 -4 {
    {one} two three four...fortyeight fortynine {fifty} fiftyone...ninetyeight ninetynine {onehundred} onehundredone...onehundredfortyeight onehundredfortynine {onehundredfifty} onehundredfiftyone...
  }

  do_test $T.7.1 {
    execsql {
      BEGIN;
        DROP TABLE IF EXISTS ft;
        CREATE TABLE ft(x);
        CREATE INDEX fti ON ft USING fts5();
    }
    set testresults [list]
    for {set i 1} {$i < 150} {incr i} {
      set commas [string repeat , $i]
      execsql {INSERT INTO ft VALUES('one' || $commas || 'two')}
      lappend testresults "{one}$commas{two}"
    }
    execsql COMMIT
  } {}
  eval [list do_snippet_test $T.7.2 {one two} -1 3] $testresults
  
}

finish_test

Changes to test/permutations.test.

136
137
138
139
140
141
142

143
144
145
146
147
148
149
  simple.test simple2.test
  log3.test 
  lsm1.test lsm2.test
  csr1.test
  ckpt1.test
  mc1.test
  fts5expr1.test fts5query1.test fts5rnd1.test fts5create.test


  aggerror.test
  attach.test
  autoindex1.test
  badutf.test
  between.test
  bigrow.test







>







136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
  simple.test simple2.test
  log3.test 
  lsm1.test lsm2.test
  csr1.test
  ckpt1.test
  mc1.test
  fts5expr1.test fts5query1.test fts5rnd1.test fts5create.test
  fts5snippet.test

  aggerror.test
  attach.test
  autoindex1.test
  badutf.test
  between.test
  bigrow.test