/ Check-in [3972a787]
Login

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

Overview
Comment:Fix various issues to do with deferred tokens, NEAR expressions and matchinfo().
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | fts3-prefix-search
Files: files | file ages | folders
SHA1: 3972a787df5ec253b99b148385655e7b68d851fa
User & Date: dan 2011-06-08 18:39:07
Context
2011-06-09
10:48
Fix problems to do with using both OR and NEAR operators in a single expression. check-in: 4e8dd19e user: dan tags: fts3-prefix-search
2011-06-08
18:39
Fix various issues to do with deferred tokens, NEAR expressions and matchinfo(). check-in: 3972a787 user: dan tags: fts3-prefix-search
2011-06-07
18:35
Have NEAR queries use incremental merging. Fix issues surrounding the deferred token optimization. check-in: 9d10a684 user: dan tags: fts3-prefix-search
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/fts3/fts3.c.

1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
....
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
....
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
....
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
....
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
....
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
....
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
....
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
....
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
....
3324
3325
3326
3327
3328
3329
3330
3331
3332
3333
3334
3335
3336
3337
3338
....
3446
3447
3448
3449
3450
3451
3452
3453
3454
3455
3456
3457
3458
3459
3460
3461
3462
3463
3464
3465
....
3561
3562
3563
3564
3565
3566
3567
3568

3569
3570
3571
3572
3573
3574
3575
3576
3577
3578
3579
3580
3581
3582
3583
3584
3585
3586
3587
3588









3589

3590
3591
3592
3593
3594
3595
3596
....
3613
3614
3615
3616
3617
3618
3619
3620
3621
3622
3623
3624
3625
3626
3627
3628
3629
3630
3631
3632
3633
3634
3635
3636
3637
3638
3639
3640
3641
3642
3643
3644
3645
3646
3647
3648
3649
3650
3651
3652
3653
3654
3655
3656
3657
3658
3659
3660
3661
3662
3663
3664
3665
3666
3667
3668
3669
3670
3671
3672
3673
3674
3675
3676
3677
3678
3679
3680
3681
3682
3683
3684
3685
3686
3687
3688
3689
3690
3691
3692
3693
3694
3695
3696
3697
3698
3699
3700
3701
3702
3703
3704
3705
3706
3707
3708
3709
3710
....
3773
3774
3775
3776
3777
3778
3779

3780
3781
3782
3783
3784
3785
3786
....
3898
3899
3900
3901
3902
3903
3904
3905
3906
3907
3908
3909
3910
3911
3912

3913
3914
3915
3916
3917
3918
3919
3920
3921
3922
3923
3924
3925
3926
3927
3928
3929
3930
3931
3932
3933
3934
3935
3936
3937
3938
3939
3940
3941
3942
3943
3944
3945
3946
3947
3948
3949
3950
3951
3952
3953
3954
3955
3956
3957
3958
3959
3960
3961
3962
3963
3964
3965
3966
3967
3968
....
3982
3983
3984
3985
3986
3987
3988

3989
3990
3991
3992
3993
3994
3995
3996

3997




3998
3999

4000
4001
4002
4003
4004
4005
4006
....
4301
4302
4303
4304
4305
4306
4307












































































































































4308
4309
4310
4311


4312
4313
4314


4315
4316
4317


4318
4319
4320


4321
4322
4323
4324
4325
















4326
4327
4328
4329
4330
4331

4332

4333
4334

4335
4336
4337
4338
4339
4340




4341
4342
4343
4344
4345
4346
4347
4348
4349
4350
4351
4352
4353
4354
4355
4356
4357
4358
4359
4360
4361

4362

4363



4364
4365
4366
4367
4368
4369
4370
4371
4372
4373
4374
4375
4376
4377
4378
4379
4380
4381
4382
4383
  ** database. TODO: For xConnect(), it could verify that said tables exist.
  */
  if( isCreate ){
    rc = fts3CreateTables(p);
  }

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

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

fts3_init_out:
................................................................................
  *pbFirst = 1;
}

#define COMPARE_DOCID(i1, i2) ((bDescIdx?-1:1) * (i1-i2))

static int fts3DoclistOrMerge(
  int bDescIdx,                   /* True if arguments are desc */
  u8 *a1, int n1,                 /* First doclist */
  u8 *a2, int n2,                 /* Second doclist */
  u8 **paOut, int *pnOut          /* OUT: Malloc'd doclist */
){
  sqlite3_int64 i1 = 0;
  sqlite3_int64 i2 = 0;
  sqlite3_int64 iPrev = 0;
  char *pEnd1 = &a1[n1];
  char *pEnd2 = &a2[n2];
  char *p1 = a1;
  char *p2 = a2;
  char *p;
  int nOut;
  char *aOut;
  int bFirstOut = 0;

  *paOut = 0;
  *pnOut = 0;
  aOut = sqlite3_malloc(n1+n2);
  if( !aOut ) return SQLITE_NOMEM;
................................................................................
  *pnOut = (p-aOut);
  return SQLITE_OK;
}

static void fts3DoclistPhraseMerge(
  int bDescIdx,                   /* True if arguments are desc */
  int nDist,                      /* Distance from left to right (1=adjacent) */
  u8 *aLeft, int nLeft,           /* Left doclist */
  u8 *aRight, int *pnRight        /* IN/OUT: Right/output doclist */
){
  sqlite3_int64 i1 = 0;
  sqlite3_int64 i2 = 0;
  sqlite3_int64 iPrev = 0;
  char *pEnd1 = &aLeft[nLeft];
  char *pEnd2 = &aRight[*pnRight];
  char *p1 = aLeft;
................................................................................
      fts3PoslistCopy(0, &p2);
      fts3GetDeltaVarint3(&p2, pEnd2, bDescIdx, &i2);
    }
  }

  *pnRight = p - aOut;
}

/*
** This function merges two doclists according to the requirements of a
** NEAR operator.
*/
static int fts3DoclistNearMerge(
  int bDescIdx,
  int nNear,                      /* Parameter to NEAR operator */
  int nTokenLeft,                 /* Number of tokens in LHS phrase arg */
  char *aLeft,                    /* Doclist for LHS (incl. positions) */
  int nLeft,                      /* Size of LHS doclist in bytes */
  int nTokenRight,                /* As nTokenLeft */
  char *aRight,                   /* As aLeft */
  int nRight,                     /* As nRight */
  char **paOut,                   /* OUT: Results of merge (malloced) */
  int *pnOut                      /* OUT: Sized of output buffer */
){
  char *aOut;                     /* Buffer to write output doclist to */
  char *aTmp;                     /* Temp buffer used by PoslistNearMerge() */

  sqlite3_int64 i1 = 0;
  sqlite3_int64 i2 = 0;
  sqlite3_int64 iPrev = 0;
  int bFirstOut = 0;

  char *pEnd1 = &aLeft[nLeft];
  char *pEnd2 = &aRight[nRight];
  char *p1 = aLeft;
  char *p2 = aRight;
  char *p;

  int nParam1 = nNear+nTokenRight;
  int nParam2 = nNear+nTokenLeft;

  p = aOut = sqlite3_malloc(nLeft+nRight+1);
  aTmp = sqlite3_malloc(2*(nLeft+nRight+1));
  if( !aOut || !aTmp ){
    sqlite3_free(aOut);
    sqlite3_free(aTmp);
    *paOut = 0;
    *pnOut = 0;
    return SQLITE_NOMEM;
  }

  fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1);
  fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2);

  while( p1 && p2 ){
    sqlite3_int64 iDiff = COMPARE_DOCID(i1, i2);
    if( iDiff==0 ){
      char *pSave = p;
      sqlite3_int64 iPrevSave = iPrev;
      int bFirstOutSave = bFirstOut;
      fts3PutDeltaVarint3(&p, bDescIdx, &iPrev, &bFirstOut, i1);
      if( !fts3PoslistNearMerge(&p, aTmp, nParam1, nParam2, &p1, &p2) ){
        p = pSave;
        iPrev = iPrevSave;
        bFirstOut = bFirstOutSave;
      }

      fts3GetDeltaVarint3(&p1, pEnd1, bDescIdx, &i1);
      fts3GetDeltaVarint3(&p2, pEnd2, bDescIdx, &i2);
    }else if( iDiff<0 ){
      fts3PoslistCopy(0, &p1);
      fts3GetDeltaVarint3(&p1, pEnd1, bDescIdx, &i1);
    }else{
      fts3PoslistCopy(0, &p2);
      fts3GetDeltaVarint3(&p2, pEnd2, bDescIdx, &i2);
    }
  }

  sqlite3_free(aTmp);
  *paOut = aOut;
  *pnOut = p - aOut;
  return SQLITE_OK;
}



/*
** Merge all doclists in the TermSelect.aaOutput[] array into a single
** doclist stored in TermSelect.aaOutput[0]. If successful, delete all
** other doclists (except the aaOutput[0] one) and return SQLITE_OK.
**
................................................................................
    if( pTS->aaOutput[i] ){
      if( !aOut ){
        aOut = pTS->aaOutput[i];
        nOut = pTS->anOutput[i];
        pTS->aaOutput[i] = 0;
      }else{
        int nNew;
        u8 *aNew;

        int rc = fts3DoclistOrMerge(p->bDescIdx, 
            pTS->aaOutput[i], pTS->anOutput[i], aOut, nOut, &aNew, &nNew
        );
        if( rc!=SQLITE_OK ){
          sqlite3_free(aOut);
          return rc;
................................................................................
    for(iOut=0; iOut<SizeofArray(pTS->aaOutput); iOut++){
      if( pTS->aaOutput[iOut]==0 ){
        assert( iOut>0 );
        pTS->aaOutput[iOut] = aMerge;
        pTS->anOutput[iOut] = nMerge;
        break;
      }else{
        u8 *aNew;
        int nNew;

        int rc = fts3DoclistOrMerge(p->bDescIdx, aMerge, nMerge, 
            pTS->aaOutput[iOut], pTS->anOutput[iOut], &aNew, &nNew
        );
        if( rc!=SQLITE_OK ){
          if( aMerge!=aDoclist ) sqlite3_free(aMerge);
................................................................................
){
  Fts3MultiSegReader *pSegcsr;   /* Object to allocate and return */
  int rc = SQLITE_NOMEM;          /* Return code */

  pSegcsr = sqlite3_malloc(sizeof(Fts3MultiSegReader));
  if( pSegcsr ){
    int i;
    int nCost = 0;
    int bFound = 0;               /* True once an index has been found */
    Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;

    if( isPrefix ){
      for(i=1; bFound==0 && i<p->nIndex; i++){
        if( p->aIndex[i].nPrefix==nTerm ){
          bFound = 1;
................................................................................

    if( bFound==0 ){
      rc = sqlite3Fts3SegReaderCursor(
          p, 0, FTS3_SEGCURSOR_ALL, zTerm, nTerm, isPrefix, 0, pSegcsr
      );
      pSegcsr->bLookup = !isPrefix;
    }
    for(i=0; rc==SQLITE_OK && i<pSegcsr->nSegment; i++){
      rc = sqlite3Fts3SegReaderCost(pCsr, pSegcsr->apSegment[i], &nCost);
    }
    pSegcsr->nCost = nCost;
  }

  *ppSegcsr = pSegcsr;
  return rc;
}

static void fts3SegReaderCursorFree(Fts3MultiSegReader *pSegcsr){
................................................................................
    "ALTER TABLE %Q.'%q_segdir'   RENAME TO '%q_segdir';",
    p->zDb, p->zName, zName
  );
  return rc;
}

static int fts3SavepointMethod(sqlite3_vtab *pVtab, int iSavepoint){
  Fts3Table *p = (Fts3Table*)pVtab;
  UNUSED_PARAMETER(iSavepoint);
  assert( p->inTransaction );
  assert( p->mxSavepoint < iSavepoint );
  TESTONLY( p->mxSavepoint = iSavepoint );
  return fts3SyncMethod(pVtab);
}
static int fts3ReleaseMethod(sqlite3_vtab *pVtab, int iSavepoint){
  TESTONLY( Fts3Table *p = (Fts3Table*)pVtab );
  UNUSED_PARAMETER(iSavepoint);
  UNUSED_PARAMETER(pVtab);
  assert( p->inTransaction );
................................................................................
  }else{
    sqlite3_free(aDoclist);
  }
  return rc;
}

static int fts3EvalDeferredPhrase(Fts3Cursor *pCsr, Fts3Phrase *pPhrase){
  Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
  int iToken;
  int rc = SQLITE_OK;

  int nMaxUndeferred = -1;
  char *aPoslist = 0;
  int nPoslist = 0;
  int iPrev = -1;
................................................................................
** This function is called for each Fts3Phrase in a full-text query 
** expression to initialize the mechanism for returning rows. Once this
** function has been called successfully on an Fts3Phrase, it may be
** used with fts3EvalPhraseNext() to iterate through the matching docids.
*/
static int fts3EvalPhraseStart(Fts3Cursor *pCsr, int bOptOk, Fts3Phrase *p){
  int rc;
  Fts3Doclist *pList = &p->doclist;
  Fts3PhraseToken *pFirst = &p->aToken[0];
  Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;

  assert( pList->aAll==0 );

  if( pCsr->bDesc==pTab->bDescIdx && bOptOk==1 && p->nToken==1 
   && pFirst->pSegcsr && pFirst->pSegcsr->bLookup 
  ){
    /* Use the incremental approach. */
    int iCol = (p->iColumn >= pTab->nColumn ? -1 : p->iColumn);
    rc = sqlite3Fts3MsrIncrStart(
        pTab, pFirst->pSegcsr, iCol, pFirst->z, pFirst->n);
................................................................................
    }
  }else if( pCsr->bDesc!=pTab->bDescIdx && pDL->nAll ){
    sqlite3Fts3DoclistPrev(pTab->bDescIdx, pDL->aAll, pDL->nAll, 
        &pDL->pNextDocid, &pDL->iDocid, &pDL->nList, pbEof
    );
    pDL->pList = pDL->pNextDocid;
  }else{
    char *pIter;

    if( pDL->pNextDocid ){
      pIter = pDL->pNextDocid;
    }else{
      pIter = pDL->aAll;
    }

    if( pIter>=&pDL->aAll[pDL->nAll] ){
      /* We have already reached the end of this doclist. EOF. */
      *pbEof = 1;
    }else{
      sqlite3_int64 iDelta;
      pIter += sqlite3Fts3GetVarint(pIter, &iDelta);
      if( pTab->bDescIdx==0 || pDL->pNextDocid==0 ){
        pDL->iDocid += iDelta;
      }else{
        pDL->iDocid -= iDelta;
      }
      pDL->pList = pIter;
      fts3PoslistCopy(0, &pIter);
      pDL->nList = (pIter - pDL->pList);









      pDL->pNextDocid = pIter;

      *pbEof = 0;
    }
  }

  return rc;
}

................................................................................
      fts3EvalStartReaders(pCsr, pExpr->pLeft, bOptOk, pRc);
      fts3EvalStartReaders(pCsr, pExpr->pRight, bOptOk, pRc);
      pExpr->bDeferred = (pExpr->pLeft->bDeferred && pExpr->pRight->bDeferred);
    }
  }
}

static void fts3EvalNearMerge(
  int bDescIdx,
  Fts3Expr *p1,
  Fts3Expr *p2,
  int nNear,
  int *pRc
){
  if( *pRc==SQLITE_OK ){
    int rc;                         /* Return code */
    Fts3Phrase *pLeft = p1->pPhrase;
    Fts3Phrase *pRight = p2->pPhrase;
  
    assert( p2->eType==FTSQUERY_PHRASE && pLeft );
    assert( p2->eType==FTSQUERY_PHRASE && pRight );
  
    if( pLeft->doclist.aAll==0 ){
      sqlite3_free(pRight->doclist.aAll);
      pRight->doclist.aAll = 0;
      pRight->doclist.nAll = 0;
    }else if( pRight->doclist.aAll ){
      char *aOut;                 /* Buffer in which to assemble new doclist */
      int nOut;                   /* Size of buffer aOut in bytes */
  
      *pRc = fts3DoclistNearMerge(bDescIdx, nNear, 
          pLeft->nToken, pLeft->doclist.aAll, pLeft->doclist.nAll,
          pRight->nToken, pRight->doclist.aAll, pRight->doclist.nAll,
          &aOut, &nOut
      );
      sqlite3_free(pRight->doclist.aAll);
      pRight->doclist.aAll = aOut;
      pRight->doclist.nAll = nOut;
    }
  }
}

static void fts3EvalNearTrim(Fts3Cursor *pCsr, Fts3Expr *pExpr, int *pRc){

  if( pExpr && SQLITE_OK==*pRc ){
    if( pExpr->eType==FTSQUERY_NEAR ){
      Fts3Expr *pLeft = pExpr->pLeft;
      int nPhrase = 2;
      Fts3Expr **aPhrase;

      assert( pLeft );
      assert( pExpr->pRight );
      assert( pExpr->pRight->eType==FTSQUERY_PHRASE );

      while( pLeft->eType!=FTSQUERY_PHRASE ){
        assert( pLeft->eType==FTSQUERY_NEAR );
        assert( pLeft->pRight->eType==FTSQUERY_PHRASE );
        pLeft = pLeft->pLeft;
        nPhrase++;
      }

      aPhrase = (Fts3Expr **)sqlite3_malloc(sizeof(Fts3Expr *) * nPhrase);
      if( !aPhrase ){
        *pRc = SQLITE_NOMEM;
      }else{
        Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
        int i = 1;
        aPhrase[0] = pLeft;
        do {
          pLeft = pLeft->pParent;
          aPhrase[i++] = pLeft->pRight;
        }while( pLeft!=pExpr );

        for(i=0; i<(nPhrase-1); i++){
          int nNear = aPhrase[i+1]->pParent->nNear;
          fts3EvalNearMerge(p->bDescIdx, aPhrase[i], aPhrase[i+1], nNear, pRc);
        }
        for(i=nPhrase-2; i>=0; i--){
          int nNear = aPhrase[i+1]->pParent->nNear;
          fts3EvalNearMerge(p->bDescIdx, aPhrase[i+1], aPhrase[i], nNear, pRc);
        }

        sqlite3_free(aPhrase);
      }

    }else{
      fts3EvalNearTrim(pCsr, pExpr->pLeft, pRc);
      fts3EvalNearTrim(pCsr, pExpr->pRight, pRc);
    }
  }
}

typedef struct Fts3TokenAndCost Fts3TokenAndCost;
struct Fts3TokenAndCost {
  Fts3PhraseToken *pToken;
  Fts3Expr *pRoot;
  int nOvfl;
  int iCol;
................................................................................
      a += sqlite3Fts3GetVarint(a, &nByte);
    }
    if( nDoc==0 || nByte==0 ){
      sqlite3_reset(pStmt);
      return SQLITE_CORRUPT_VTAB;
    }


    pCsr->nRowAvg = (int)(((nByte / nDoc) + p->nPgsz) / p->nPgsz);
    assert( pCsr->nRowAvg>0 ); 
    rc = sqlite3_reset(pStmt);
    if( rc!=SQLITE_OK ) return rc;
  }

  *pnPage = pCsr->nRowAvg;
................................................................................
    );
    apOr = (Fts3Expr **)&aTC[nToken];

    if( !aTC ){
      rc = SQLITE_NOMEM;
    }else{
      int ii;
      int nDocSize;
      Fts3TokenAndCost *pTC = aTC;
      Fts3Expr **ppOr = apOr;

      fts3EvalTokenCosts(pCsr, 0, pExpr, &pTC, &ppOr, &rc);
      nToken = pTC-aTC;
      nOr = ppOr-apOr;


      rc = fts3EvalSelectDeferred(pCsr, 0, aTC, nToken);
      for(ii=0; rc==SQLITE_OK && ii<nOr; ii++){
        rc = fts3EvalSelectDeferred(pCsr, apOr[ii], aTC, nToken);
      }

#if 0
      for(ii=0; rc==SQLITE_OK && ii<nToken; ii++){
        int jj;
        pTC = 0;
        for(jj=0; jj<nToken; jj++){
          if( aTC[jj].pToken && (!pTC || aTC[jj].nOvfl<pTC->nOvfl) ){
            pTC = &aTC[jj];
          }
        }
        assert( pTC );


        /* At this point pTC points to the cheapest remaining token. */
        if( ii==0 ){
          if( pTC->nOvfl ){
            nDocEst = (pTC->nOvfl * pTab->nPgsz + pTab->nPgsz) / 10;
          }else{
            /* TODO: Fix this so that the doclist need not be read twice. */
            Fts3PhraseToken *pToken = pTC->pToken;
            int nList = 0;
            char *pList = 0;
            rc = fts3TermSelect(pTab, pToken, pTC->iCol, 1, &nList, &pList);
            if( rc==SQLITE_OK ){
              nDocEst = fts3DoclistCountDocids(1, pList, nList);
            }
            sqlite3_free(pList);
            if( rc==SQLITE_OK ){
              rc = sqlite3Fts3TermSegReaderCursor(pCsr, 
                pToken->z, pToken->n, pToken->isPrefix, &pToken->pSegcsr
              );
            }
          }
        }else{
          if( pTC->nOvfl>=(nDocEst*nDocSize) ){
            Fts3PhraseToken *pToken = pTC->pToken;
            rc = sqlite3Fts3DeferToken(pCsr, pToken, pTC->iCol);
            fts3SegReaderCursorFree(pToken->pSegcsr);
            pToken->pSegcsr = 0;
          }
          nDocEst = 1 + (nDocEst/4);
        }
        pTC->pToken = 0;
      }
#endif

      sqlite3_free(aTC);
    }
  }

  fts3EvalStartReaders(pCsr, pExpr, bOptOk, &rc);
  return rc;
................................................................................
  char *aTmp,                     /* Temporary space to use */
  char **paPoslist,               /* IN/OUT: Position list */
  int *pnToken,                   /* IN/OUT: Tokens in phrase of *paPoslist */
  Fts3Phrase *pPhrase             /* The phrase object to trim the doclist of */
){
  int nParam1 = nNear + pPhrase->nToken;
  int nParam2 = nNear + *pnToken;

  char *p2; 
  char *pOut; 
  int res;

  p2 = pOut = pPhrase->doclist.pList;
  res = fts3PoslistNearMerge(
    &pOut, aTmp, nParam1, nParam2, paPoslist, &p2
  );

  pPhrase->doclist.nList = pOut - pPhrase->doclist.pList;




  *paPoslist = pPhrase->doclist.pList;
  *pnToken = pPhrase->nToken;


  return res;
}

static int fts3EvalNearTest(Fts3Expr *pExpr, int *pRc){
  int res = 1;

................................................................................
      pCsr->isMatchinfoNeeded = 1;
      pCsr->iPrevId = pExpr->iDocid;
    }while( pCsr->isEof==0 && fts3EvalLoadDeferred(pCsr, &rc) );
  }
  return rc;
}













































































































































/*
** Return a pointer to the entire doclist, including positions, associated 
** with the phrase passed as the second argument. It is illegal to call
** this function if the phrase consists entirely of deferred tokens.


**
** TODO: This function is only used by the code for the matchinfo('x')
** auxiliary function - to obtain the following two values:


**
**   1. The total number of times the phrase appears in each column in all 
**      rows in the FTS table.


**
**   2. For each column, the total number of rows in the FTS table for which
**      the phrase appears at least once in the column.


**
** It would be better if there was an sqlite3Fts3EvalXXX() function 
** specifically to retrieve these values. If that were done, the concept
** of which tokens are deferred or incremental would be entirely encapsulated
** within the sqlite3Fts3EvalXXX()/fts3EvalXXX() functions in this file.
















*/
int sqlite3Fts3EvalPhraseDoclist(
  Fts3Cursor *pCsr,               /* FTS3 cursor object */
  Fts3Expr *pExpr,                /* Phrase to return doclist for */
  const char **ppList,            /* OUT: Buffer containing doclist */
  int *pnList                     /* OUT: Size of returned buffer, in bytes */

){

  int rc = SQLITE_OK;
  Fts3Phrase *pPhrase = pExpr->pPhrase;


  /* It is illegal to call this function if the phrase is entirely deferred
  ** (it may contain some deferred tokens, but must also contain at least
  ** one token for which the doclist may be read from the full-text index). 
  */
  assert( !pExpr->bDeferred );





  if( pPhrase->bIncr ){
    /* This phrase was being loaded from disk incrementally. But the 
    ** matchinfo() function requires that the entire doclist be loaded into
    ** memory. This block loads the doclist into memory and modifies the
    ** Fts3Phrase structure so that it does not use the incremental strategy.
    */
    TESTONLY( int bEof = pExpr->bEof; )
    TESTONLY( int bStart = pExpr->bStart; )
    sqlite3_int64 iDocid = pExpr->iDocid;

    sqlite3Fts3EvalPhraseCleanup(pPhrase);
    pExpr->iDocid = 0;

    rc = sqlite3Fts3EvalStart(pCsr, pExpr, 0);
    assert( pExpr->bEof==bEof );
    assert( pExpr->bStart==bStart );
    assert( rc!=SQLITE_OK || pPhrase->bIncr==0 );
    if( pExpr->bStart && !pExpr->bEof ){
      pExpr->bStart = 0;
      while( rc==SQLITE_OK && (pExpr->bStart==0 || pExpr->iDocid!=iDocid) ){

        fts3EvalNext(pCsr, pExpr, &rc);

        assert( !pExpr->bEof );



      }
    }
  }

  if( rc==SQLITE_OK 
   && pExpr->pParent 
   && pExpr->pParent->eType==FTSQUERY_NEAR 
  ){

  }

  *pnList = pPhrase->doclist.nAll;
  *ppList = pPhrase->doclist.aAll;
  return rc;
}

/*
** The expression pExpr passed as the second argument to this function
** must be of type FTSQUERY_PHRASE. 
**







|
<
<







 







|
|
|









<







 







|
|







 







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







 







|







 







|







 







<







 







<
<
<
<







 







<

|
|
|







 







<







 







<



|
<







 







|
>






|













>
>
>
>
>
>
>
>
>

>







 







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







 







>







 







<







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







 







>








>
|
>
>
>
>
|
|
>







 







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

<
<
<
>
>

<
<
>
>

<
<
>
>

<
<
>
>

<
<
<
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

|
|
|
<
<
>

>

<
>

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




<
<
<
<
<
<
<
<
<







1118
1119
1120
1121
1122
1123
1124
1125


1126
1127
1128
1129
1130
1131
1132
....
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977

1978
1979
1980
1981
1982
1983
1984
....
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
....
2055
2056
2057
2058
2059
2060
2061













































































2062
2063
2064
2065
2066
2067
2068
....
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
....
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
....
2319
2320
2321
2322
2323
2324
2325

2326
2327
2328
2329
2330
2331
2332
....
2351
2352
2353
2354
2355
2356
2357




2358
2359
2360
2361
2362
2363
2364
....
2964
2965
2966
2967
2968
2969
2970

2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
....
3238
3239
3240
3241
3242
3243
3244

3245
3246
3247
3248
3249
3250
3251
....
3359
3360
3361
3362
3363
3364
3365

3366
3367
3368
3369

3370
3371
3372
3373
3374
3375
3376
....
3472
3473
3474
3475
3476
3477
3478
3479
3480
3481
3482
3483
3484
3485
3486
3487
3488
3489
3490
3491
3492
3493
3494
3495
3496
3497
3498
3499
3500
3501
3502
3503
3504
3505
3506
3507
3508
3509
3510
3511
3512
3513
3514
3515
3516
3517
3518
....
3535
3536
3537
3538
3539
3540
3541




















































































3542
3543
3544
3545
3546
3547
3548
....
3611
3612
3613
3614
3615
3616
3617
3618
3619
3620
3621
3622
3623
3624
3625
....
3737
3738
3739
3740
3741
3742
3743

3744
3745
3746
3747
3748
3749
3750
3751
3752
3753
3754
3755
3756












































3757
3758
3759
3760
3761
3762
3763
....
3777
3778
3779
3780
3781
3782
3783
3784
3785
3786
3787
3788
3789
3790
3791
3792
3793
3794
3795
3796
3797
3798
3799
3800
3801
3802
3803
3804
3805
3806
3807
3808
....
4103
4104
4105
4106
4107
4108
4109
4110
4111
4112
4113
4114
4115
4116
4117
4118
4119
4120
4121
4122
4123
4124
4125
4126
4127
4128
4129
4130
4131
4132
4133
4134
4135
4136
4137
4138
4139
4140
4141
4142
4143
4144
4145
4146
4147
4148
4149
4150
4151
4152
4153
4154
4155
4156
4157
4158
4159
4160
4161
4162
4163
4164
4165
4166
4167
4168
4169
4170
4171
4172
4173
4174
4175
4176
4177
4178
4179
4180
4181
4182
4183
4184
4185
4186
4187
4188
4189
4190
4191
4192
4193
4194
4195
4196
4197
4198
4199
4200
4201
4202
4203
4204
4205
4206
4207
4208
4209
4210
4211
4212
4213
4214
4215
4216
4217
4218
4219
4220
4221
4222
4223
4224
4225
4226
4227
4228
4229
4230
4231
4232
4233
4234
4235
4236
4237
4238
4239
4240
4241
4242
4243
4244
4245
4246
4247
4248
4249
4250



4251
4252
4253


4254
4255
4256


4257
4258
4259


4260
4261
4262




4263
4264
4265
4266
4267
4268
4269
4270
4271
4272
4273
4274
4275
4276
4277
4278
4279
4280
4281
4282


4283
4284
4285
4286

4287
4288




4289
4290
4291
4292
4293
4294




















4295
4296
4297
4298
4299
4300
4301
4302
4303
4304
4305









4306
4307
4308
4309
4310
4311
4312
  ** database. TODO: For xConnect(), it could verify that said tables exist.
  */
  if( isCreate ){
    rc = fts3CreateTables(p);
  }

  /* Figure out the page-size for the database. This is required in order to
  ** estimate the cost of loading large doclists from the database.  */


  fts3DatabasePageSize(&rc, p);
  p->nNodeSize = p->nPgsz-35;

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

fts3_init_out:
................................................................................
  *pbFirst = 1;
}

#define COMPARE_DOCID(i1, i2) ((bDescIdx?-1:1) * (i1-i2))

static int fts3DoclistOrMerge(
  int bDescIdx,                   /* True if arguments are desc */
  char *a1, int n1,               /* First doclist */
  char *a2, int n2,               /* Second doclist */
  char **paOut, int *pnOut        /* OUT: Malloc'd doclist */
){
  sqlite3_int64 i1 = 0;
  sqlite3_int64 i2 = 0;
  sqlite3_int64 iPrev = 0;
  char *pEnd1 = &a1[n1];
  char *pEnd2 = &a2[n2];
  char *p1 = a1;
  char *p2 = a2;
  char *p;

  char *aOut;
  int bFirstOut = 0;

  *paOut = 0;
  *pnOut = 0;
  aOut = sqlite3_malloc(n1+n2);
  if( !aOut ) return SQLITE_NOMEM;
................................................................................
  *pnOut = (p-aOut);
  return SQLITE_OK;
}

static void fts3DoclistPhraseMerge(
  int bDescIdx,                   /* True if arguments are desc */
  int nDist,                      /* Distance from left to right (1=adjacent) */
  char *aLeft, int nLeft,         /* Left doclist */
  char *aRight, int *pnRight      /* IN/OUT: Right/output doclist */
){
  sqlite3_int64 i1 = 0;
  sqlite3_int64 i2 = 0;
  sqlite3_int64 iPrev = 0;
  char *pEnd1 = &aLeft[nLeft];
  char *pEnd2 = &aRight[*pnRight];
  char *p1 = aLeft;
................................................................................
      fts3PoslistCopy(0, &p2);
      fts3GetDeltaVarint3(&p2, pEnd2, bDescIdx, &i2);
    }
  }

  *pnRight = p - aOut;
}















































































/*
** Merge all doclists in the TermSelect.aaOutput[] array into a single
** doclist stored in TermSelect.aaOutput[0]. If successful, delete all
** other doclists (except the aaOutput[0] one) and return SQLITE_OK.
**
................................................................................
    if( pTS->aaOutput[i] ){
      if( !aOut ){
        aOut = pTS->aaOutput[i];
        nOut = pTS->anOutput[i];
        pTS->aaOutput[i] = 0;
      }else{
        int nNew;
        char *aNew;

        int rc = fts3DoclistOrMerge(p->bDescIdx, 
            pTS->aaOutput[i], pTS->anOutput[i], aOut, nOut, &aNew, &nNew
        );
        if( rc!=SQLITE_OK ){
          sqlite3_free(aOut);
          return rc;
................................................................................
    for(iOut=0; iOut<SizeofArray(pTS->aaOutput); iOut++){
      if( pTS->aaOutput[iOut]==0 ){
        assert( iOut>0 );
        pTS->aaOutput[iOut] = aMerge;
        pTS->anOutput[iOut] = nMerge;
        break;
      }else{
        char *aNew;
        int nNew;

        int rc = fts3DoclistOrMerge(p->bDescIdx, aMerge, nMerge, 
            pTS->aaOutput[iOut], pTS->anOutput[iOut], &aNew, &nNew
        );
        if( rc!=SQLITE_OK ){
          if( aMerge!=aDoclist ) sqlite3_free(aMerge);
................................................................................
){
  Fts3MultiSegReader *pSegcsr;   /* Object to allocate and return */
  int rc = SQLITE_NOMEM;          /* Return code */

  pSegcsr = sqlite3_malloc(sizeof(Fts3MultiSegReader));
  if( pSegcsr ){
    int i;

    int bFound = 0;               /* True once an index has been found */
    Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;

    if( isPrefix ){
      for(i=1; bFound==0 && i<p->nIndex; i++){
        if( p->aIndex[i].nPrefix==nTerm ){
          bFound = 1;
................................................................................

    if( bFound==0 ){
      rc = sqlite3Fts3SegReaderCursor(
          p, 0, FTS3_SEGCURSOR_ALL, zTerm, nTerm, isPrefix, 0, pSegcsr
      );
      pSegcsr->bLookup = !isPrefix;
    }




  }

  *ppSegcsr = pSegcsr;
  return rc;
}

static void fts3SegReaderCursorFree(Fts3MultiSegReader *pSegcsr){
................................................................................
    "ALTER TABLE %Q.'%q_segdir'   RENAME TO '%q_segdir';",
    p->zDb, p->zName, zName
  );
  return rc;
}

static int fts3SavepointMethod(sqlite3_vtab *pVtab, int iSavepoint){

  UNUSED_PARAMETER(iSavepoint);
  assert( ((Fts3Table *)pVtab)->inTransaction );
  assert( ((Fts3Table *)pVtab)->mxSavepoint < iSavepoint );
  TESTONLY( ((Fts3Table *)pVtab)->mxSavepoint = iSavepoint );
  return fts3SyncMethod(pVtab);
}
static int fts3ReleaseMethod(sqlite3_vtab *pVtab, int iSavepoint){
  TESTONLY( Fts3Table *p = (Fts3Table*)pVtab );
  UNUSED_PARAMETER(iSavepoint);
  UNUSED_PARAMETER(pVtab);
  assert( p->inTransaction );
................................................................................
  }else{
    sqlite3_free(aDoclist);
  }
  return rc;
}

static int fts3EvalDeferredPhrase(Fts3Cursor *pCsr, Fts3Phrase *pPhrase){

  int iToken;
  int rc = SQLITE_OK;

  int nMaxUndeferred = -1;
  char *aPoslist = 0;
  int nPoslist = 0;
  int iPrev = -1;
................................................................................
** This function is called for each Fts3Phrase in a full-text query 
** expression to initialize the mechanism for returning rows. Once this
** function has been called successfully on an Fts3Phrase, it may be
** used with fts3EvalPhraseNext() to iterate through the matching docids.
*/
static int fts3EvalPhraseStart(Fts3Cursor *pCsr, int bOptOk, Fts3Phrase *p){
  int rc;

  Fts3PhraseToken *pFirst = &p->aToken[0];
  Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;

  assert( p->doclist.aAll==0 );

  if( pCsr->bDesc==pTab->bDescIdx && bOptOk==1 && p->nToken==1 
   && pFirst->pSegcsr && pFirst->pSegcsr->bLookup 
  ){
    /* Use the incremental approach. */
    int iCol = (p->iColumn >= pTab->nColumn ? -1 : p->iColumn);
    rc = sqlite3Fts3MsrIncrStart(
        pTab, pFirst->pSegcsr, iCol, pFirst->z, pFirst->n);
................................................................................
    }
  }else if( pCsr->bDesc!=pTab->bDescIdx && pDL->nAll ){
    sqlite3Fts3DoclistPrev(pTab->bDescIdx, pDL->aAll, pDL->nAll, 
        &pDL->pNextDocid, &pDL->iDocid, &pDL->nList, pbEof
    );
    pDL->pList = pDL->pNextDocid;
  }else{
    char *pIter;                            /* Used to iterate through aAll */
    char *pEnd = &pDL->aAll[pDL->nAll];     /* 1 byte past end of aAll */
    if( pDL->pNextDocid ){
      pIter = pDL->pNextDocid;
    }else{
      pIter = pDL->aAll;
    }

    if( pIter>=pEnd ){
      /* We have already reached the end of this doclist. EOF. */
      *pbEof = 1;
    }else{
      sqlite3_int64 iDelta;
      pIter += sqlite3Fts3GetVarint(pIter, &iDelta);
      if( pTab->bDescIdx==0 || pDL->pNextDocid==0 ){
        pDL->iDocid += iDelta;
      }else{
        pDL->iDocid -= iDelta;
      }
      pDL->pList = pIter;
      fts3PoslistCopy(0, &pIter);
      pDL->nList = (pIter - pDL->pList);

      /* pIter now points just past the 0x00 that terminates the position-
      ** list for document pDL->iDocid. However, if this position-list was
      ** edited in place by fts3EvalNearTrim2(), then pIter may not actually
      ** point to the start of the next docid value. The following line deals
      ** with this case by advancing pIter past the zero-padding added by
      ** fts3EvalNearTrim2().  */
      while( pIter<pEnd && *pIter==0 ) pIter++;

      pDL->pNextDocid = pIter;
      assert( *pIter || pIter>=&pDL->aAll[pDL->nAll] );
      *pbEof = 0;
    }
  }

  return rc;
}

................................................................................
      fts3EvalStartReaders(pCsr, pExpr->pLeft, bOptOk, pRc);
      fts3EvalStartReaders(pCsr, pExpr->pRight, bOptOk, pRc);
      pExpr->bDeferred = (pExpr->pLeft->bDeferred && pExpr->pRight->bDeferred);
    }
  }
}






















































































typedef struct Fts3TokenAndCost Fts3TokenAndCost;
struct Fts3TokenAndCost {
  Fts3PhraseToken *pToken;
  Fts3Expr *pRoot;
  int nOvfl;
  int iCol;
................................................................................
      a += sqlite3Fts3GetVarint(a, &nByte);
    }
    if( nDoc==0 || nByte==0 ){
      sqlite3_reset(pStmt);
      return SQLITE_CORRUPT_VTAB;
    }

    pCsr->nDoc = nDoc;
    pCsr->nRowAvg = (int)(((nByte / nDoc) + p->nPgsz) / p->nPgsz);
    assert( pCsr->nRowAvg>0 ); 
    rc = sqlite3_reset(pStmt);
    if( rc!=SQLITE_OK ) return rc;
  }

  *pnPage = pCsr->nRowAvg;
................................................................................
    );
    apOr = (Fts3Expr **)&aTC[nToken];

    if( !aTC ){
      rc = SQLITE_NOMEM;
    }else{
      int ii;

      Fts3TokenAndCost *pTC = aTC;
      Fts3Expr **ppOr = apOr;

      fts3EvalTokenCosts(pCsr, 0, pExpr, &pTC, &ppOr, &rc);
      nToken = pTC-aTC;
      nOr = ppOr-apOr;

      if( rc==SQLITE_OK ){
        rc = fts3EvalSelectDeferred(pCsr, 0, aTC, nToken);
        for(ii=0; rc==SQLITE_OK && ii<nOr; ii++){
          rc = fts3EvalSelectDeferred(pCsr, apOr[ii], aTC, nToken);
        }
      }













































      sqlite3_free(aTC);
    }
  }

  fts3EvalStartReaders(pCsr, pExpr, bOptOk, &rc);
  return rc;
................................................................................
  char *aTmp,                     /* Temporary space to use */
  char **paPoslist,               /* IN/OUT: Position list */
  int *pnToken,                   /* IN/OUT: Tokens in phrase of *paPoslist */
  Fts3Phrase *pPhrase             /* The phrase object to trim the doclist of */
){
  int nParam1 = nNear + pPhrase->nToken;
  int nParam2 = nNear + *pnToken;
  int nNew;
  char *p2; 
  char *pOut; 
  int res;

  p2 = pOut = pPhrase->doclist.pList;
  res = fts3PoslistNearMerge(
    &pOut, aTmp, nParam1, nParam2, paPoslist, &p2
  );
  if( res ){
    nNew = (pOut - pPhrase->doclist.pList) - 1;
    assert( pPhrase->doclist.pList[nNew]=='\0' );
    assert( nNew<=pPhrase->doclist.nList && nNew>0 );
    memset(&pPhrase->doclist.pList[nNew], 0, pPhrase->doclist.nList - nNew);
    pPhrase->doclist.nList = nNew;
    *paPoslist = pPhrase->doclist.pList;
    *pnToken = pPhrase->nToken;
  }

  return res;
}

static int fts3EvalNearTest(Fts3Expr *pExpr, int *pRc){
  int res = 1;

................................................................................
      pCsr->isMatchinfoNeeded = 1;
      pCsr->iPrevId = pExpr->iDocid;
    }while( pCsr->isEof==0 && fts3EvalLoadDeferred(pCsr, &rc) );
  }
  return rc;
}

static void fts3EvalRestart(
  Fts3Cursor *pCsr,
  Fts3Expr *pExpr,
  int *pRc
){
  if( pExpr && *pRc==SQLITE_OK ){
    Fts3Phrase *pPhrase = pExpr->pPhrase;

    if( pPhrase ){
      fts3EvalFreeDeferredDoclist(pPhrase);
      if( pPhrase->bIncr ){
        sqlite3Fts3EvalPhraseCleanup(pPhrase);
        memset(&pPhrase->doclist, 0, sizeof(Fts3Doclist));
        *pRc = sqlite3Fts3EvalStart(pCsr, pExpr, 0);
      }else{
        pPhrase->doclist.pNextDocid = 0;
        pPhrase->doclist.iDocid = 0;
      }
    }

    pExpr->iDocid = 0;
    pExpr->bEof = 0;
    pExpr->bStart = 0;

    fts3EvalRestart(pCsr, pExpr->pLeft, pRc);
    fts3EvalRestart(pCsr, pExpr->pRight, pRc);
  }
}

static void fts3EvalUpdateCounts(
  Fts3Cursor *pCsr,
  Fts3Expr *pExpr,
  int *pRc
){
  if( pExpr && *pRc==SQLITE_OK ){
    Fts3Phrase *pPhrase = pExpr->pPhrase;
    if( pPhrase && pPhrase->doclist.pList ){
      int iCol = 0;
      char *p = pPhrase->doclist.pList;

      assert( *p );
      while( 1 ){
        u8 c = 0;
        int iCnt = 0;
        while( 0xFE & (*p | c) ){
          if( (c&0x80)==0 ) iCnt++;
          c = *p++ & 0x80;
        }

        /* aMI[iCol*3 + 1] = Number of occurrences
        ** aMI[iCol*3 + 2] = Number of rows containing at least one instance
        */
        pExpr->aMI[iCol*3 + 1] += iCnt;
        pExpr->aMI[iCol*3 + 2] += (iCnt>0);
        if( *p==0x00 ) break;
        p++;
        p += sqlite3Fts3GetVarint32(p, &iCol);
      }
    }

    fts3EvalUpdateCounts(pCsr, pExpr->pLeft, pRc);
    fts3EvalUpdateCounts(pCsr, pExpr->pRight, pRc);
  }
}

static int fts3EvalNearStats(
  Fts3Cursor *pCsr,
  Fts3Expr *pExpr
){
  int rc = SQLITE_OK;             /* Return code */

  assert( pExpr->eType==FTSQUERY_PHRASE );
  if( pExpr->aMI==0 ){
    Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
    Fts3Expr *pRoot;                /* Root of NEAR expression */
    Fts3Expr *p;                    /* Iterator used for several purposes */

    sqlite3_int64 iPrevId = pCsr->iPrevId;
    sqlite3_int64 iDocid;
    u8 bEof;

    /* Find the root of the NEAR expression */
    pRoot = pExpr;
    while( pRoot->pParent && pRoot->pParent->eType==FTSQUERY_NEAR ){
      pRoot = pRoot->pParent;
    }
    iDocid = pRoot->iDocid;
    bEof = pRoot->bEof;

    /* Allocate space for the aMSI[] array of each FTSQUERY_PHRASE node */
    for(p=pRoot; p; p=p->pLeft){
      Fts3Expr *pE = (p->eType==FTSQUERY_PHRASE?p:p->pRight);
      assert( pE->aMI==0 );
      pE->aMI = (u32 *)sqlite3_malloc(pTab->nColumn * 3 * sizeof(u32));
      if( !pE->aMI ) return SQLITE_NOMEM;
      memset(pE->aMI, 0, pTab->nColumn * 3 * sizeof(u32));
    }

    fts3EvalRestart(pCsr, pRoot, &rc);

    while( pCsr->isEof==0 && rc==SQLITE_OK ){

      do {
        /* Ensure the %_content statement is reset. */
        if( pCsr->isRequireSeek==0 ) sqlite3_reset(pCsr->pStmt);
        assert( sqlite3_data_count(pCsr->pStmt)==0 );

        /* Advance to the next document */
        fts3EvalNext(pCsr, pRoot, &rc);
        pCsr->isEof = pRoot->bEof;
        pCsr->isRequireSeek = 1;
        pCsr->isMatchinfoNeeded = 1;
        pCsr->iPrevId = pRoot->iDocid;
      }while( pCsr->isEof==0 
           && pRoot->eType==FTSQUERY_NEAR 
           && fts3EvalLoadDeferred(pCsr, &rc) 
      );

      if( pCsr->isEof==0 ){
        fts3EvalUpdateCounts(pCsr, pRoot, &rc);
      }
    }

    pCsr->isEof = 0;
    pCsr->iPrevId = iPrevId;

    if( bEof ){
      pRoot->bEof = bEof;
    }else{
      fts3EvalRestart(pCsr, pRoot, &rc);
      while( pRoot->iDocid<iDocid && rc==SQLITE_OK ){
        fts3EvalNext(pCsr, pRoot, &rc);
        assert( pRoot->bEof==0 );
      }
      fts3EvalLoadDeferred(pCsr, &rc);
    }
  }
  return rc;
}

/*



** This function is used by the matchinfo() module to query a phrase 
** expression node for the following information:
**


**   1. The total number of occurrences of the phrase in each column of 
**      the FTS table (considering all rows), and
**


**   2. For each column, the number of rows in the table for which the
**      column contains at least one instance of the phrase.
**


** If no error occurs, SQLITE_OK is returned and the values for each column
** written into the array aiOut as follows:
**




**   aiOut[iCol*3 + 1] = Number of occurrences
**   aiOut[iCol*3 + 2] = Number of rows containing at least one instance
**
** Caveats:
**
**   * If a phrase consists entirely of deferred tokens, then all output 
**     values are set to the number of documents in the table. In other
**     words we assume that very common tokens occur exactly once in each 
**     column of each row of the table.
**
**   * If a phrase contains some deferred tokens (and some non-deferred 
**     tokens), count the potential occurrence identified by considering
**     the non-deferred tokens instead of actual phrase occurrences.
**
**   * If the phrase is part of a NEAR expression, then only phrase instances
**     that meet the NEAR constraint are included in the counts.
*/
int sqlite3Fts3EvalPhraseStats(
  Fts3Cursor *pCsr,               /* FTS cursor handle */
  Fts3Expr *pExpr,                /* Phrase expression */


  u32 *aiOut                      /* Array to write results into (see above) */
){
  Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
  int rc = SQLITE_OK;

  int iCol;





  if( pExpr->bDeferred ){
    assert( pCsr->nDoc>0 );
    for(iCol=0; iCol<pTab->nColumn; iCol++){
      aiOut[iCol*3 + 1] = pCsr->nDoc;
      aiOut[iCol*3 + 2] = pCsr->nDoc;
    }




















  }else{
    rc = fts3EvalNearStats(pCsr, pExpr);
    if( rc==SQLITE_OK ){
      assert( pExpr->aMI );
      for(iCol=0; iCol<pTab->nColumn; iCol++){
        aiOut[iCol*3 + 1] = pExpr->aMI[iCol*3 + 1];
        aiOut[iCol*3 + 2] = pExpr->aMI[iCol*3 + 2];
      }
    }
  }










  return rc;
}

/*
** The expression pExpr passed as the second argument to this function
** must be of type FTSQUERY_PHRASE. 
**

Changes to ext/fts3/fts3Int.h.

236
237
238
239
240
241
242

243
244
245
246
247
248
249
...
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
...
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
...
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
...
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
  sqlite3_int64 iPrevId;          /* Previous id read from aDoclist */
  char *pNextId;                  /* Pointer into the body of aDoclist */
  char *aDoclist;                 /* List of docids for full-text queries */
  int nDoclist;                   /* Size of buffer at aDoclist */
  u8 bDesc;                       /* True to sort in descending order */
  int eEvalmode;                  /* An FTS3_EVAL_XX constant */
  int nRowAvg;                    /* Average size of database rows, in pages */


  int isMatchinfoNeeded;          /* True when aMatchinfo[] needs filling in */
  u32 *aMatchinfo;                /* Information about most recent match */
  int nMatchinfo;                 /* Number of elements in aMatchinfo[] */
  char *zMatchinfo;               /* Matchinfo specification */
};

................................................................................
**
** If Fts3Expr.eType is FTSQUERY_PHRASE and isLoaded is true, then aDoclist 
** points to a malloced buffer, size nDoclist bytes, containing the results 
** of this phrase query in FTS3 doclist format. As usual, the initial 
** "Length" field found in doclists stored on disk is omitted from this 
** buffer.
**
** Variable pCurrent always points to the start of a docid field within
** aDoclist. Since the doclist is usually scanned in docid order, this can
** be used to accelerate seeking to the required docid within the doclist.








*/
struct Fts3Expr {
  int eType;                 /* One of the FTSQUERY_XXX values defined below */
  int nNear;                 /* Valid if eType==FTSQUERY_NEAR */
  Fts3Expr *pParent;         /* pParent->pLeft==this or pParent->pRight==this */
  Fts3Expr *pLeft;           /* Left operand */
  Fts3Expr *pRight;          /* Right operand */
................................................................................
  Fts3Phrase *pPhrase;       /* Valid if eType==FTSQUERY_PHRASE */

  /* The following are used by the fts3_eval.c module. */
  sqlite3_int64 iDocid;      /* Current docid */
  u8 bEof;                   /* True this expression is at EOF already */
  u8 bStart;                 /* True if iDocid is valid */
  u8 bDeferred;              /* True if this expression is entirely deferred */


};

/*
** Candidate values for Fts3Query.eType. Note that the order of the first
** four values is in order of precedence when parsing expressions. For 
** example, the following:
**
................................................................................
void sqlite3Fts3PendingTermsClear(Fts3Table *);
int sqlite3Fts3Optimize(Fts3Table *);
int sqlite3Fts3SegReaderNew(int, sqlite3_int64,
  sqlite3_int64, sqlite3_int64, const char *, int, Fts3SegReader**);
int sqlite3Fts3SegReaderPending(
  Fts3Table*,int,const char*,int,int,Fts3SegReader**);
void sqlite3Fts3SegReaderFree(Fts3SegReader *);
int sqlite3Fts3SegReaderCost(Fts3Cursor *, Fts3SegReader *, int *);
int sqlite3Fts3AllSegdirs(Fts3Table*, int, int, sqlite3_stmt **);
int sqlite3Fts3ReadLock(Fts3Table *);
int sqlite3Fts3ReadBlock(Fts3Table*, sqlite3_int64, char **, int*, int*);

int sqlite3Fts3SelectDoctotal(Fts3Table *, sqlite3_stmt **);
int sqlite3Fts3SelectDocsize(Fts3Table *, sqlite3_int64, sqlite3_stmt **);

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

/* Special values interpreted by sqlite3SegReaderCursor() */
#define FTS3_SEGCURSOR_PENDING        -1
#define FTS3_SEGCURSOR_ALL            -2

int sqlite3Fts3SegReaderStart(Fts3Table*, Fts3MultiSegReader*, Fts3SegFilter*);
................................................................................
int sqlite3Fts3PutVarint(char *, sqlite3_int64);
int sqlite3Fts3GetVarint(const char *, sqlite_int64 *);
int sqlite3Fts3GetVarint32(const char *, int *);
int sqlite3Fts3VarintLen(sqlite3_uint64);
void sqlite3Fts3Dequote(char *);
void sqlite3Fts3DoclistPrev(int,char*,int,char**,sqlite3_int64*,int*,u8*);

int sqlite3Fts3ExprLoadDoclist(Fts3Cursor *, Fts3Expr *);
int sqlite3Fts3ExprNearTrim(Fts3Expr *, Fts3Expr *, int);

/* fts3_tokenizer.c */
const char *sqlite3Fts3NextToken(const char *, int *);
int sqlite3Fts3InitHashTable(sqlite3 *, Fts3Hash *, const char *);
int sqlite3Fts3InitTokenizer(Fts3Hash *pHash, const char *, 
    sqlite3_tokenizer **, char **
);
................................................................................
  Fts3Cursor *pCsr,               /* Virtual table cursor handle */
  const char *zTerm,              /* Term to query for */
  int nTerm,                      /* Size of zTerm in bytes */
  int isPrefix,                   /* True for a prefix search */
  Fts3MultiSegReader **ppSegcsr   /* OUT: Allocated seg-reader cursor */
);

int sqlite3Fts3EvalPhraseCache(Fts3Cursor *, Fts3Phrase *);
sqlite3_int64 sqlite3Fts3EvalDocid(Fts3Cursor *, Fts3Expr *);
int sqlite3Fts3EvalPhraseDoclist(Fts3Cursor*, Fts3Expr*, const char**,int*);
void sqlite3Fts3EvalPhraseCleanup(Fts3Phrase *);

int sqlite3Fts3EvalStart(Fts3Cursor *, Fts3Expr *, int);
int sqlite3Fts3EvalNext(Fts3Cursor *pCsr);

int sqlite3Fts3MsrIncrStart(
    Fts3Table*, Fts3MultiSegReader*, int, const char*, int);







>







 







|
|
|
>
>
>
>
>
>
>
>







 







>
>







 







<











<







 







|
<







 







<
<
<







236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
...
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
...
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
...
446
447
448
449
450
451
452
453

454
455
456
457
458
459
460
...
484
485
486
487
488
489
490



491
492
493
494
495
496
497
  sqlite3_int64 iPrevId;          /* Previous id read from aDoclist */
  char *pNextId;                  /* Pointer into the body of aDoclist */
  char *aDoclist;                 /* List of docids for full-text queries */
  int nDoclist;                   /* Size of buffer at aDoclist */
  u8 bDesc;                       /* True to sort in descending order */
  int eEvalmode;                  /* An FTS3_EVAL_XX constant */
  int nRowAvg;                    /* Average size of database rows, in pages */
  int nDoc;                       /* Documents in table */

  int isMatchinfoNeeded;          /* True when aMatchinfo[] needs filling in */
  u32 *aMatchinfo;                /* Information about most recent match */
  int nMatchinfo;                 /* Number of elements in aMatchinfo[] */
  char *zMatchinfo;               /* Matchinfo specification */
};

................................................................................
**
** If Fts3Expr.eType is FTSQUERY_PHRASE and isLoaded is true, then aDoclist 
** points to a malloced buffer, size nDoclist bytes, containing the results 
** of this phrase query in FTS3 doclist format. As usual, the initial 
** "Length" field found in doclists stored on disk is omitted from this 
** buffer.
**
** Variable aMI is used only for FTSQUERY_NEAR nodes to store the global
** matchinfo data. If it is not NULL, it points to an array of size nCol*3,
** where nCol is the number of columns in the queried FTS table. The array
** is populated as follows:
**
**   aMI[iCol*3 + 0] = Undefined
**   aMI[iCol*3 + 1] = Number of occurrences
**   aMI[iCol*3 + 2] = Number of rows containing at least one instance
**
** The aMI array is allocated using sqlite3_malloc(). It should be freed 
** when the expression node is.
*/
struct Fts3Expr {
  int eType;                 /* One of the FTSQUERY_XXX values defined below */
  int nNear;                 /* Valid if eType==FTSQUERY_NEAR */
  Fts3Expr *pParent;         /* pParent->pLeft==this or pParent->pRight==this */
  Fts3Expr *pLeft;           /* Left operand */
  Fts3Expr *pRight;          /* Right operand */
................................................................................
  Fts3Phrase *pPhrase;       /* Valid if eType==FTSQUERY_PHRASE */

  /* The following are used by the fts3_eval.c module. */
  sqlite3_int64 iDocid;      /* Current docid */
  u8 bEof;                   /* True this expression is at EOF already */
  u8 bStart;                 /* True if iDocid is valid */
  u8 bDeferred;              /* True if this expression is entirely deferred */

  u32 *aMI;
};

/*
** Candidate values for Fts3Query.eType. Note that the order of the first
** four values is in order of precedence when parsing expressions. For 
** example, the following:
**
................................................................................
void sqlite3Fts3PendingTermsClear(Fts3Table *);
int sqlite3Fts3Optimize(Fts3Table *);
int sqlite3Fts3SegReaderNew(int, sqlite3_int64,
  sqlite3_int64, sqlite3_int64, const char *, int, Fts3SegReader**);
int sqlite3Fts3SegReaderPending(
  Fts3Table*,int,const char*,int,int,Fts3SegReader**);
void sqlite3Fts3SegReaderFree(Fts3SegReader *);

int sqlite3Fts3AllSegdirs(Fts3Table*, int, int, sqlite3_stmt **);
int sqlite3Fts3ReadLock(Fts3Table *);
int sqlite3Fts3ReadBlock(Fts3Table*, sqlite3_int64, char **, int*, int*);

int sqlite3Fts3SelectDoctotal(Fts3Table *, sqlite3_stmt **);
int sqlite3Fts3SelectDocsize(Fts3Table *, sqlite3_int64, sqlite3_stmt **);

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

void sqlite3Fts3SegmentsClose(Fts3Table *);

/* Special values interpreted by sqlite3SegReaderCursor() */
#define FTS3_SEGCURSOR_PENDING        -1
#define FTS3_SEGCURSOR_ALL            -2

int sqlite3Fts3SegReaderStart(Fts3Table*, Fts3MultiSegReader*, Fts3SegFilter*);
................................................................................
int sqlite3Fts3PutVarint(char *, sqlite3_int64);
int sqlite3Fts3GetVarint(const char *, sqlite_int64 *);
int sqlite3Fts3GetVarint32(const char *, int *);
int sqlite3Fts3VarintLen(sqlite3_uint64);
void sqlite3Fts3Dequote(char *);
void sqlite3Fts3DoclistPrev(int,char*,int,char**,sqlite3_int64*,int*,u8*);

int sqlite3Fts3EvalPhraseStats(Fts3Cursor *, Fts3Expr *, u32 *);


/* fts3_tokenizer.c */
const char *sqlite3Fts3NextToken(const char *, int *);
int sqlite3Fts3InitHashTable(sqlite3 *, Fts3Hash *, const char *);
int sqlite3Fts3InitTokenizer(Fts3Hash *pHash, const char *, 
    sqlite3_tokenizer **, char **
);
................................................................................
  Fts3Cursor *pCsr,               /* Virtual table cursor handle */
  const char *zTerm,              /* Term to query for */
  int nTerm,                      /* Size of zTerm in bytes */
  int isPrefix,                   /* True for a prefix search */
  Fts3MultiSegReader **ppSegcsr   /* OUT: Allocated seg-reader cursor */
);




void sqlite3Fts3EvalPhraseCleanup(Fts3Phrase *);

int sqlite3Fts3EvalStart(Fts3Cursor *, Fts3Expr *, int);
int sqlite3Fts3EvalNext(Fts3Cursor *pCsr);

int sqlite3Fts3MsrIncrStart(
    Fts3Table*, Fts3MultiSegReader*, int, const char*, int);

Changes to ext/fts3/fts3_expr.c.

765
766
767
768
769
770
771

772
773
774
775
776
777
778
*/
void sqlite3Fts3ExprFree(Fts3Expr *p){
  if( p ){
    assert( p->eType==FTSQUERY_PHRASE || p->pPhrase==0 );
    sqlite3Fts3ExprFree(p->pLeft);
    sqlite3Fts3ExprFree(p->pRight);
    sqlite3Fts3EvalPhraseCleanup(p->pPhrase);

    sqlite3_free(p);
  }
}

/****************************************************************************
*****************************************************************************
** Everything after this point is just test code.







>







765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
*/
void sqlite3Fts3ExprFree(Fts3Expr *p){
  if( p ){
    assert( p->eType==FTSQUERY_PHRASE || p->pPhrase==0 );
    sqlite3Fts3ExprFree(p->pLeft);
    sqlite3Fts3ExprFree(p->pRight);
    sqlite3Fts3EvalPhraseCleanup(p->pPhrase);
    sqlite3_free(p->aMI);
    sqlite3_free(p);
  }
}

/****************************************************************************
*****************************************************************************
** Everything after this point is just test code.

Changes to ext/fts3/fts3_snippet.c.

716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
...
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
    if( !c ) nEntry++;
  }

  *ppCollist = pEnd;
  return nEntry;
}

static void fts3LoadColumnlistCounts(char **pp, u32 *aOut, int isGlobal){
  char *pCsr = *pp;
  while( *pCsr ){
    int nHit;
    sqlite3_int64 iCol = 0;
    if( *pCsr==0x01 ){
      pCsr++;
      pCsr += sqlite3Fts3GetVarint(pCsr, &iCol);
    }
    nHit = fts3ColumnlistCount(&pCsr);
    assert( nHit>0 );
    if( isGlobal ){
      aOut[iCol*3+1]++;
    }
    aOut[iCol*3] += nHit;
  }
  pCsr++;
  *pp = pCsr;
}

/*
** fts3ExprIterate() callback used to collect the "global" matchinfo stats
** for a single query. 
**
** fts3ExprIterate() callback to load the 'global' elements of a
** FTS3_MATCHINFO_HITS matchinfo array. The global stats are those elements 
** of the matchinfo array that are constant for all rows returned by the 
................................................................................
*/
static int fts3ExprGlobalHitsCb(
  Fts3Expr *pExpr,                /* Phrase expression node */
  int iPhrase,                    /* Phrase number (numbered from zero) */
  void *pCtx                      /* Pointer to MatchInfo structure */
){
  MatchInfo *p = (MatchInfo *)pCtx;
  u32 *aOut = &p->aMatchinfo[3*iPhrase*p->nCol];

  if( pExpr->bDeferred ){
    int iCol;                   /* Column index */
    for(iCol=0; iCol<p->nCol; iCol++){
      aOut[iCol*3 + 1] = (u32)p->nDoc;
      aOut[iCol*3 + 2] = (u32)p->nDoc;
    }
  }else{
    char *pIter;
    char *pEnd;
    int n;
    int rc = sqlite3Fts3EvalPhraseDoclist(
        p->pCursor, pExpr, (const char **)&pIter, &n
    );
    if( rc!=SQLITE_OK ) return rc;
    pEnd = &pIter[n];

    /* Fill in the global hit count matrix row for this phrase. */
    while( pIter<pEnd ){
      while( *pIter++ & 0x80 );      /* Skip past docid. */
      fts3LoadColumnlistCounts(&pIter, &aOut[1], 1);
    }
  }

  return SQLITE_OK;
}

/*
** fts3ExprIterate() callback used to collect the "local" part of the
** FTS3_MATCHINFO_HITS array. The local stats are those elements of the 
** array that are different for each row returned by the query.
*/







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







 







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







716
717
718
719
720
721
722




















723
724
725
726
727
728
729
...
749
750
751
752
753
754
755












756
757
758











759
760
761
762
763
764
765
    if( !c ) nEntry++;
  }

  *ppCollist = pEnd;
  return nEntry;
}





















/*
** fts3ExprIterate() callback used to collect the "global" matchinfo stats
** for a single query. 
**
** fts3ExprIterate() callback to load the 'global' elements of a
** FTS3_MATCHINFO_HITS matchinfo array. The global stats are those elements 
** of the matchinfo array that are constant for all rows returned by the 
................................................................................
*/
static int fts3ExprGlobalHitsCb(
  Fts3Expr *pExpr,                /* Phrase expression node */
  int iPhrase,                    /* Phrase number (numbered from zero) */
  void *pCtx                      /* Pointer to MatchInfo structure */
){
  MatchInfo *p = (MatchInfo *)pCtx;












  return sqlite3Fts3EvalPhraseStats(
      p->pCursor, pExpr, &p->aMatchinfo[3*iPhrase*p->nCol]
  );











}

/*
** fts3ExprIterate() callback used to collect the "local" part of the
** FTS3_MATCHINFO_HITS array. The local stats are those elements of the 
** array that are different for each row returned by the query.
*/

Changes to ext/fts3/fts3_write.c.

90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
....
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
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
....
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
....
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
** a contiguous set of segment b-tree leaf nodes. Although the details of
** this structure are only manipulated by code in this file, opaque handles
** of type Fts3SegReader* are also used by code in fts3.c to iterate through
** terms when querying the full-text index. See functions:
**
**   sqlite3Fts3SegReaderNew()
**   sqlite3Fts3SegReaderFree()
**   sqlite3Fts3SegReaderCost()
**   sqlite3Fts3SegReaderIterate()
**
** Methods used to manipulate Fts3SegReader structures:
**
**   fts3SegReaderNext()
**   fts3SegReaderFirstDocid()
**   fts3SegReaderNextDocid()
................................................................................
      }
    }
  }

  return SQLITE_OK;
}

/*
** This function is called to estimate the amount of data that will be 
** loaded from the disk If SegReaderIterate() is called on this seg-reader,
** in units of average document size.
** 
** This can be used as follows: If the caller has a small doclist that 
** contains references to N documents, and is considering merging it with
** a large doclist (size X "average documents"), it may opt not to load
** the large doclist if X>N.
*/
int sqlite3Fts3SegReaderCost(
  Fts3Cursor *pCsr,               /* FTS3 cursor handle */
  Fts3SegReader *pReader,         /* Segment-reader handle */
  int *pnCost                     /* IN/OUT: Number of bytes read */
){
  Fts3Table *p = (Fts3Table*)pCsr->base.pVtab;
  int rc = SQLITE_OK;             /* Return code */
  int nCost = 0;                  /* Cost in bytes to return */
  int pgsz = p->nPgsz;            /* Database page size */

  assert( pgsz>0 );

  /* If this seg-reader is reading the pending-terms table, or if all data
  ** for the segment is stored on the root page of the b-tree, then the cost
  ** is zero. In this case all required data is already in main memory.
  */
  if( p->bHasStat 
   && !fts3SegReaderIsPending(pReader) 
   && !fts3SegReaderIsRootOnly(pReader) 
  ){
    int nBlob = 0;
    sqlite3_int64 iBlock;

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

      rc = sqlite3Fts3SelectDoctotal(p, &pStmt);
      if( rc!=SQLITE_OK ) return rc;
      a = sqlite3_column_blob(pStmt, 0);
      assert( a );

      pEnd = &a[sqlite3_column_bytes(pStmt, 0)];
      a += sqlite3Fts3GetVarint(a, &nDoc);
      while( a<pEnd ){
        a += sqlite3Fts3GetVarint(a, &nByte);
      }
      if( nDoc==0 || nByte==0 ){
        sqlite3_reset(pStmt);
        return SQLITE_CORRUPT_VTAB;
      }

      pCsr->nRowAvg = (int)(((nByte / nDoc) + pgsz) / pgsz);
      assert( pCsr->nRowAvg>0 ); 
      rc = sqlite3_reset(pStmt);
      if( rc!=SQLITE_OK ) return rc;
    }

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

  *pnCost += nCost;
  return rc;
}

int sqlite3Fts3MsrOvfl(
  Fts3Cursor *pCsr, 
  Fts3MultiSegReader *pMsr,
  int *pnOvfl
){
  Fts3Table *p = (Fts3Table*)pCsr->base.pVtab;
................................................................................

  if( nMerge==0 ){
    *paPoslist = 0;
    return SQLITE_OK;
  }

  while( 1 ){
    int nSort;
    Fts3SegReader *pSeg;
    pSeg = pMsr->apSegment[0];

    if( pSeg->pOffsetList==0 ){
      *paPoslist = 0;
      break;
    }else{
................................................................................
  }else{
    rc = SQLITE_ERROR;
  }

  return rc;
}

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

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







<







 







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







 







<







 







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







90
91
92
93
94
95
96

97
98
99
100
101
102
103
....
1290
1291
1292
1293
1294
1295
1296

























































































1297
1298
1299
1300
1301
1302
1303
....
2322
2323
2324
2325
2326
2327
2328

2329
2330
2331
2332
2333
2334
2335
....
2863
2864
2865
2866
2867
2868
2869














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

**   sqlite3Fts3SegReaderIterate()
**
** Methods used to manipulate Fts3SegReader structures:
**
**   fts3SegReaderNext()
**   fts3SegReaderFirstDocid()
**   fts3SegReaderNextDocid()
................................................................................
      }
    }
  }

  return SQLITE_OK;
}



























































































int sqlite3Fts3MsrOvfl(
  Fts3Cursor *pCsr, 
  Fts3MultiSegReader *pMsr,
  int *pnOvfl
){
  Fts3Table *p = (Fts3Table*)pCsr->base.pVtab;
................................................................................

  if( nMerge==0 ){
    *paPoslist = 0;
    return SQLITE_OK;
  }

  while( 1 ){

    Fts3SegReader *pSeg;
    pSeg = pMsr->apSegment[0];

    if( pSeg->pOffsetList==0 ){
      *paPoslist = 0;
      break;
    }else{
................................................................................
  }else{
    rc = SQLITE_ERROR;
  }

  return rc;
}















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

Changes to test/fts3matchinfo.test.

240
241
242
243
244
245
246



247
248
249

250
251
252
253
254
255
256
do_matchinfo_test 4.2.3 t5 {t5 MATCH 'a b a'}       { s {3} }
do_matchinfo_test 4.2.4 t5 {t5 MATCH 'a a a'}       { s {3 1} }
do_matchinfo_test 4.2.5 t5 {t5 MATCH '"a b" "a b"'} { s {2} }
do_matchinfo_test 4.2.6 t5 {t5 MATCH 'a OR b'}      { s {1 2 1} }

do_execsql_test 4.3.0 "INSERT INTO t5 VALUES('x y [string repeat {b } 50000]')";




do_matchinfo_test 4.3.1 t5 {t5 MATCH 'a a'} { 
  x {{5 8 2   5 5 5} {3 8 2   3 5 5}}
  s {2 1} 

}

do_matchinfo_test 4.3.2 t5 {t5 MATCH 'a b'}         { s {2} }
do_matchinfo_test 4.3.3 t5 {t5 MATCH 'a b a'}       { s {3} }
do_matchinfo_test 4.3.4 t5 {t5 MATCH 'a a a'}       { s {3 1} }
do_matchinfo_test 4.3.5 t5 {t5 MATCH '"a b" "a b"'} { s {2} }
do_matchinfo_test 4.3.6 t5 {t5 MATCH 'a OR b'}      { s {1 2 1 1} }







>
>
>
|
|
|
>







240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
do_matchinfo_test 4.2.3 t5 {t5 MATCH 'a b a'}       { s {3} }
do_matchinfo_test 4.2.4 t5 {t5 MATCH 'a a a'}       { s {3 1} }
do_matchinfo_test 4.2.5 t5 {t5 MATCH '"a b" "a b"'} { s {2} }
do_matchinfo_test 4.2.6 t5 {t5 MATCH 'a OR b'}      { s {1 2 1} }

do_execsql_test 4.3.0 "INSERT INTO t5 VALUES('x y [string repeat {b } 50000]')";

# It used to be that the second 'a' token would be deferred. That doesn't
# work any longer.
if 0 {
  do_matchinfo_test 4.3.1 t5 {t5 MATCH 'a a'} { 
    x {{5 8 2   5 5 5} {3 8 2   3 5 5}}
    s {2 1} 
  }
}

do_matchinfo_test 4.3.2 t5 {t5 MATCH 'a b'}         { s {2} }
do_matchinfo_test 4.3.3 t5 {t5 MATCH 'a b a'}       { s {3} }
do_matchinfo_test 4.3.4 t5 {t5 MATCH 'a a a'}       { s {3 1} }
do_matchinfo_test 4.3.5 t5 {t5 MATCH '"a b" "a b"'} { s {2} }
do_matchinfo_test 4.3.6 t5 {t5 MATCH 'a OR b'}      { s {1 2 1 1} }