SQLite

#ifdef SQLITE_DEBUG
static int fts5Corrupt() { return SQLITE_CORRUPT_VTAB; }
# define FTS5_CORRUPT fts5Corrupt()
#else
# define FTS5_CORRUPT SQLITE_CORRUPT_VTAB
#endif

#ifdef SQLITE_DEBUG
static int fts5MissingData() { return 0; }
#else
# define fts5MissingData() 
#endif


typedef struct Fts5BtreeIter Fts5BtreeIter;
typedef struct Fts5BtreeIterLevel Fts5BtreeIterLevel;
typedef struct Fts5ChunkIter Fts5ChunkIter;
typedef struct Fts5Data Fts5Data;
typedef struct Fts5MultiSegIter Fts5MultiSegIter;
typedef struct Fts5NodeIter Fts5NodeIter;

  int nData;
  int iOff;

  /* Output variables */
  Fts5Buffer term;
  int nEmpty;
  int iChild;
  int bDlidx;
};

/*
** An Fts5BtreeIter object is used to iterate through all entries in the
** b-tree hierarchy belonging to a single fts5 segment. In this case the
** "b-tree hierarchy" is all b-tree nodes except leaves. Each entry in the
** b-tree hierarchy consists of the following:

  Fts5BtreeIterLevel *aLvl;       /* Level for each tier of b-tree */

  /* Output variables */
  Fts5Buffer term;                /* Current term */
  int iLeaf;                      /* Leaf containing terms >= current term */
  int nEmpty;                     /* Number of "empty" leaves following iLeaf */
  int bEof;                       /* Set to true at EOF */
  int bDlidx;                     /* True if there exists a dlidx */
};

static void fts5PutU16(u8 *aOut, u16 iVal){
  aOut[0] = (iVal>>8);
  aOut[1] = (iVal&0xFF);
}

      Fts5Config *pConfig = p->pConfig;
      rc = sqlite3_blob_open(pConfig->db, 
          pConfig->zDb, p->zDataTbl, "block", iRowid, 0, &p->pReader
      );
    }else{
      rc = sqlite3_blob_reopen(p->pReader, iRowid);
    }

    if( rc ) fts5MissingData();

    if( rc==SQLITE_OK ){
      int nByte = sqlite3_blob_bytes(p->pReader);
      if( pBuf ){
        fts5BufferZero(pBuf);
        fts5BufferGrow(&rc, pBuf, nByte);
        rc = sqlite3_blob_read(p->pReader, pBuf->p, nByte, 0);

/*
** If the pIter->iOff offset currently points to an entry indicating one
** or more term-less nodes, advance past it and set pIter->nEmpty to
** the number of empty child nodes.
*/
static void fts5NodeIterGobbleNEmpty(Fts5NodeIter *pIter){
  if( pIter->iOff<pIter->nData && 0==(pIter->aData[pIter->iOff] & 0xfe) ){
    pIter->bDlidx = pIter->aData[pIter->iOff] & 0x01;
    pIter->iOff++;
    pIter->iOff += getVarint32(&pIter->aData[pIter->iOff], pIter->nEmpty);
  }else{
    pIter->nEmpty = 0;
    pIter->bDlidx = 0;
  }
}

/*
** Advance to the next entry within the node.
*/
static void fts5NodeIterNext(int *pRc, Fts5NodeIter *pIter){

/*
** If an "nEmpty" record must be written to the b-tree before the next
** term, write it now.
*/
static void fts5WriteBtreeNEmpty(Fts5Index *p, Fts5SegWriter *pWriter){
  if( pWriter->nEmpty ){
    int bFlag = 0;
    Fts5PageWriter *pPg = &pWriter->aWriter[1];
    int bFlag = 0;
    Fts5PageWriter *pPg;
    pPg = &pWriter->aWriter[1];
    if( pWriter->nEmpty>=FTS5_MIN_DLIDX_SIZE ){
      i64 iKey = FTS5_DOCLIST_IDX_ROWID(
          pWriter->iIdx, pWriter->iSegid, 
          pWriter->aWriter[0].pgno - 1 - pWriter->nEmpty
      );
      assert( pWriter->dlidx.n>0 );
      fts5DataWrite(p, iKey, pWriter->dlidx.p, pWriter->dlidx.n);
      bFlag = 1;
    }
    fts5BufferAppendVarint(&p->rc, &pPg->buf, bFlag);
    fts5BufferAppendVarint(&p->rc, &pPg->buf, pWriter->nEmpty);
    pWriter->nEmpty = 0;
  }

  /* Whether or not it was written to disk, zero the doclist index at this
  ** point */
  sqlite3Fts5BufferZero(&pWriter->dlidx);
  pWriter->bDlidxPrevValid = 0;
}

static void fts5WriteBtreeGrow(Fts5Index *p, Fts5SegWriter *pWriter){
  Fts5PageWriter *aNew;
  Fts5PageWriter *pNew;
  int nNew = sizeof(Fts5PageWriter) * (pWriter->nWriter+1);

  aNew = (Fts5PageWriter*)sqlite3_realloc(pWriter->aWriter, nNew);
  if( aNew==0 ) return;

  pNew = &aNew[pWriter->nWriter];
  memset(pNew, 0, sizeof(Fts5PageWriter));
  pNew->pgno = 1;
  fts5BufferAppendVarint(&p->rc, &pNew->buf, 1);

  pWriter->nWriter++;
  pWriter->aWriter = aNew;
}

/*
** This is called once for each leaf page except the first that contains
** at least one term. Argument (nTerm/pTerm) is the split-key - a term that
** is larger than all terms written to earlier leaves, and equal to or
** smaller than the first term on the new leaf.
**
** If an error occurs, an error code is left in Fts5Index.rc. If an error
** has already occurred when this function is called, it is a no-op.
*/
static void fts5WriteBtreeTerm(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5SegWriter *pWriter,         /* Writer object */
  int nTerm, const u8 *pTerm      /* First term on new page */
){
  int iHeight;
  for(iHeight=1; 1; iHeight++){
    Fts5PageWriter *pPage;

    if( iHeight>=pWriter->nWriter ){
      Fts5PageWriter *aNew;
      fts5WriteBtreeGrow(p, pWriter);
      Fts5PageWriter *pNew;
      int nNew = sizeof(Fts5PageWriter) * (pWriter->nWriter+1);
      aNew = (Fts5PageWriter*)sqlite3_realloc(pWriter->aWriter, nNew);
      if( aNew==0 ) return;
      if( p->rc ) return;

      pNew = &aNew[pWriter->nWriter];
      memset(pNew, 0, sizeof(Fts5PageWriter));
      pNew->pgno = 1;
      fts5BufferAppendVarint(&p->rc, &pNew->buf, 1);

      pWriter->nWriter++;
      pWriter->aWriter = aNew;
    }
    pPage = &pWriter->aWriter[iHeight];

    fts5WriteBtreeNEmpty(p, pWriter);

    if( pPage->buf.n>=p->pgsz ){
      /* pPage will be written to disk. The term will be written into the

static void fts5WriteFlushLeaf(Fts5Index *p, Fts5SegWriter *pWriter){
  static const u8 zero[] = { 0x00, 0x00, 0x00, 0x00 };
  Fts5PageWriter *pPage = &pWriter->aWriter[0];
  i64 iRowid;

  if( pPage->term.n==0 ){
    /* No term was written to this page. */
    assert( 0==fts5GetU16(&pPage->buf.p[2]) );
    fts5WriteBtreeNoTerm(p, pWriter);
  }

  /* Write the current page to the db. */
  iRowid = FTS5_SEGMENT_ROWID(pWriter->iIdx, pWriter->iSegid, 0, pPage->pgno);
  fts5DataWrite(p, iRowid, pPage->buf.p, pPage->buf.n);

  Fts5Index *p, 
  Fts5SegWriter *pWriter,         /* Writer object */
  int *pnHeight,                  /* OUT: Height of the b-tree */
  int *pnLeaf                     /* OUT: Number of leaf pages in b-tree */
){
  int i;
  *pnLeaf = pWriter->aWriter[0].pgno;
  *pnHeight = pWriter->nWriter;
  fts5WriteFlushLeaf(p, pWriter);
  if( pWriter->nWriter==1 && pWriter->nEmpty>=FTS5_MIN_DLIDX_SIZE ){
    fts5WriteBtreeGrow(p, pWriter);
  }
  if( pWriter->nWriter>1 ){
    fts5WriteBtreeNEmpty(p, pWriter);
  }
  *pnHeight = pWriter->nWriter;

  for(i=1; i<pWriter->nWriter; i++){
    Fts5PageWriter *pPg = &pWriter->aWriter[i];
    i64 iRow = FTS5_SEGMENT_ROWID(pWriter->iIdx, pWriter->iSegid, i, pPg->pgno);
    fts5DataWrite(p, iRow, pPg->buf.p, pPg->buf.n);
  }
  for(i=0; i<pWriter->nWriter; i++){
    Fts5PageWriter *pPg = &pWriter->aWriter[i];

  if( pIter->nLvl==0 || p->rc ){
    pIter->bEof = 1;
    pIter->iLeaf = pSeg->pgnoLast;
  }else{
    pIter->nEmpty = pIter->aLvl[0].s.nEmpty;
    pIter->iLeaf = pIter->aLvl[0].s.iChild;
    pIter->bDlidx = pIter->aLvl[0].s.bDlidx;
  }
}

static void fts5BtreeIterNext(Fts5BtreeIter *pIter){
  Fts5Index *p = pIter->p;
  int i;

      if( pLvl->pData ){
        fts5NodeIterInit(pLvl->pData->p, pLvl->pData->n, &pLvl->s);
      }
    }
  }

  pIter->nEmpty = pIter->aLvl[0].s.nEmpty;
  pIter->bDlidx = pIter->aLvl[0].s.bDlidx;
  pIter->iLeaf = pIter->aLvl[0].s.iChild;
  assert( p->rc==SQLITE_OK || pIter->bEof );
}

static void fts5BtreeIterFree(Fts5BtreeIter *pIter){
  int i;
  for(i=0; i<pIter->nLvl; i++){
    Fts5BtreeIterLevel *pLvl = &pIter->aLvl[i];
    fts5NodeIterFree(&pLvl->s);
    if( pLvl->pData ){
      fts5DataRelease(pLvl->pData);
      pLvl->pData = 0;
    }
  }
  sqlite3_free(pIter->aLvl);
  fts5BufferFree(&pIter->term);
}

typedef struct DoclistIdxIter DoclistIdxIter;
struct DoclistIdxIter {
  Fts5Data *pDlidx;             /* Data for doclist index, if any */
  int iOff;                     /* Current offset into pDlidx */
  int bRowidValid;              /* iRowid is valid */

  int bZero;                    /* True if current leaf has no rowid */
  i64 iRowid;                   /* If bZero==0, first rowid on leaf */
};

/*
** Return non-zero if EOF is reached.
*/
static int fts5IndexDoclistIterNext(DoclistIdxIter *pIter){
  i64 iVal;
  if( pIter->iOff>=pIter->pDlidx->n ) return 1;
  pIter->iOff += getVarint(&pIter->pDlidx->p[pIter->iOff], (u64*)&iVal);
  if( iVal==0 ){
    pIter->bZero = 1;
  }else{
    pIter->bZero = 0;
    if( pIter->bRowidValid ){
      pIter->iRowid -= iVal;
    }else{
      pIter->bRowidValid = 1;
      pIter->iRowid = iVal;
    }
  }
  return 0;
}

static void fts5IndexIntegrityCheckSegment(
  Fts5Index *p,                   /* FTS5 backend object */
  int iIdx,                       /* Index that pSeg is a part of */
  Fts5StructureSegment *pSeg      /* Segment to check internal consistency */
){
  Fts5BtreeIter iter;             /* Used to iterate through b-tree hierarchy */

  /* Iterate through the b-tree hierarchy.  */
  for(fts5BtreeIterInit(p, iIdx, pSeg, &iter);
      iter.bEof==0;
      fts5BtreeIterNext(&iter)
  ){
    i64 iRow;                     /* Rowid for this leaf */
    Fts5Data *pLeaf;              /* Data for this leaf */
    int iOff;                     /* Offset of first term on leaf */
    int i;                        /* Used to iterate through empty leaves */
    DoclistIdxIter dliter;        /* For iterating through any doclist index */

    /* If the leaf in question has already been trimmed from the segment, 
    ** ignore this b-tree entry. Otherwise, load it into memory. */
    if( iter.iLeaf<pSeg->pgnoFirst ) continue;
    iRow = FTS5_SEGMENT_ROWID(iIdx, pSeg->iSegid, 0, iter.iLeaf);
    pLeaf = fts5DataRead(p, iRow);
    if( pLeaf==0 ) break;

      if( res==0 ) res = nTerm - iter.term.n;
      if( res<0 ){
        p->rc = FTS5_CORRUPT;
      }
    }
    fts5DataRelease(pLeaf);
    if( p->rc ) break;

    memset(&dliter, 0, sizeof(DoclistIdxIter));
    if( iter.bDlidx ){
      i64 iDlidxRowid = FTS5_DOCLIST_IDX_ROWID(iIdx, pSeg->iSegid, iter.iLeaf);
      dliter.pDlidx = fts5DataRead(p, iDlidxRowid);
    }

    /* Now check that the iter.nEmpty leaves following the current leaf
    ** (a) exist and (b) contain no terms. */
    for(i=1; i<=iter.nEmpty; i++){
      pLeaf = fts5DataRead(p, iRow+i);
      if( pLeaf && 0!=fts5GetU16(&pLeaf->p[2]) ){
        p->rc = FTS5_CORRUPT;
      }
      if( pLeaf && dliter.pDlidx ){
        if( fts5IndexDoclistIterNext(&dliter) ){
          p->rc = FTS5_CORRUPT;
        }else{
          int iRowidOff = fts5GetU16(&pLeaf->p[0]);
          if( dliter.bZero ){
            if( iRowidOff!=0 ) p->rc = FTS5_CORRUPT;
          }else{
            i64 iRowid;
            getVarint(&pLeaf->p[iRowidOff], (u64*)&iRowid);
            if( iRowid!=dliter.iRowid ) p->rc = FTS5_CORRUPT;
          }
        }
      }
      fts5DataRelease(pLeaf);
    }
    fts5DataRelease(dliter.pDlidx);
  }

  if( p->rc==SQLITE_OK && iter.iLeaf!=pSeg->pgnoLast ){
    p->rc = FTS5_CORRUPT;
  }

  fts5BtreeIterFree(&iter);

  a = sqlite3_value_blob(apVal[1]);
  fts5DecodeRowid(iRowid, &iIdx, &iSegid, &iHeight, &iPgno);

  if( iHeight==FTS5_SEGMENT_MAX_HEIGHT ){
    int i = 0;
    i64 iPrev;
    sqlite3Fts5BufferAppendPrintf(&rc, &s, "(dlidx idx=%d segid=%d pgno=%d)",
        iIdx, iSegid, iHeight, iPgno
        iIdx, iSegid, iPgno
    );
    if( n>0 ){
      i = getVarint(&a[i], (u64*)&iPrev);
      sqlite3Fts5BufferAppendPrintf(&rc, &s, " %lld", iPrev);
    }
    while( i<n ){
      i64 iVal;

          sqlite3Fts5BufferAppendPrintf(&rc, &s, " left=%d", ss.iChild);
        }else{
          sqlite3Fts5BufferAppendPrintf(&rc,&s, " \"%.*s\"", 
              ss.term.n, ss.term.p
          );
        }
        if( ss.nEmpty ){
          sqlite3Fts5BufferAppendPrintf(&rc, &s, " empty=%d", ss.nEmpty);
          sqlite3Fts5BufferAppendPrintf(&rc, &s, " empty=%d%s", ss.nEmpty,
              ss.bDlidx ? "*" : ""
          );
        }
      }
      fts5NodeIterFree(&ss);
    }
  }
  
  if( rc==SQLITE_OK ){

  SELECT rowid FROM t1 WHERE t1 MATCH 'y AND x'
} [lsort -integer -decr $Y]

do_execsql_test 1.3 {
  INSERT INTO t1(t1) VALUES('integrity-check');
}

do_execsql_test 1.4 {
  SELECT count(*) FROM t1_data
}


finish_test

  fts4growth.test fts4growth2.test
}

test_suite "fts5" -prefix "" -description {
  All FTS5 tests.
} -files {
  fts5aa.test fts5ab.test fts5ac.test fts5ad.test fts5ae.test fts5ea.test
  fts5af.test fts5ag.test
  fts5af.test fts5ag.test fts5ah.test
}

test_suite "nofaultsim" -prefix "" -description {
  "Very" quick test suite. Runs in less than 5 minutes on a workstation. 
  This test suite is the same as the "quick" tests, except that some files
  that test malloc and IO errors are omitted.
} -files [