getAndInitPage_error:
  if( pCur ) pCur->iPage--;
  testcase( pgno==0 );
  assert( pgno!=0 || rc==SQLITE_CORRUPT );
  return rc;
}












/*
** Release a MemPage.  This should be called once for each prior
** call to btreeGetPage.
*/
static void releasePageNotNull(MemPage *pPage){
  assert( pPage->aData );
  assert( pPage->pBt );
................................................................................
** This function returns SQLITE_CORRUPT if the page-header flags field of
** the new child page does not match the flags field of the parent (i.e.
** if an intkey page appears to be the parent of a non-intkey page, or
** vice-versa).
*/
static int moveToChild(BtCursor *pCur, u32 newPgno){
  BtShared *pBt = pCur->pBt;


  assert( cursorOwnsBtShared(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  assert( pCur->iPage<BTCURSOR_MAX_DEPTH );
  assert( pCur->iPage>=0 );
  if( pCur->iPage>=(BTCURSOR_MAX_DEPTH-1) ){
    return SQLITE_CORRUPT_BKPT;
  }
  pCur->info.nSize = 0;
  pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
  pCur->aiIdx[pCur->iPage++] = pCur->ix;
  pCur->ix = 0;
  return getAndInitPage(pBt, newPgno, &pCur->apPage[pCur->iPage],
                        pCur, pCur->curPagerFlags);




}

#ifdef SQLITE_DEBUG
/*
** Page pParent is an internal (non-leaf) tree page. This function 
** asserts that page number iChild is the left-child if the iIdx'th
** cell in page pParent. Or, if iIdx is equal to the total number of
................................................................................
    assert( pCur->iPage==(-1) );
    rc = getAndInitPage(pCur->pBtree->pBt, pCur->pgnoRoot, &pCur->apPage[0],
                        0, pCur->curPagerFlags);
    if( rc!=SQLITE_OK ){
      pCur->eState = CURSOR_INVALID;
       return rc;
    }

    pCur->iPage = 0;
    pCur->curIntKey = pCur->apPage[0]->intKey;
  }
  pRoot = pCur->apPage[0];
  assert( pRoot->pgno==pCur->pgnoRoot );

  /* If pCur->pKeyInfo is not NULL, then the caller that opened this cursor
................................................................................
** SQLITE_NOMEM.
*/
static int balance_nonroot(
  MemPage *pParent,               /* Parent page of siblings being balanced */
  int iParentIdx,                 /* Index of "the page" in pParent */
  u8 *aOvflSpace,                 /* page-size bytes of space for parent ovfl */
  int isRoot,                     /* True if pParent is a root-page */
  int bBulk                       /* True if this call is part of a bulk load */

){
  BtShared *pBt;               /* The whole database */
  int nMaxCells = 0;           /* Allocated size of apCell, szCell, aFrom. */
  int nNew = 0;                /* Number of pages in apNew[] */
  int nOld;                    /* Number of pages in apOld[] */
  int i, j, k;                 /* Loop counters */
  int nxDiv;                   /* Next divider slot in pParent->aCell[] */
................................................................................
  pgno = get4byte(pRight);
  while( 1 ){
    rc = getAndInitPage(pBt, pgno, &apOld[i], 0, 0);
    if( rc ){
      memset(apOld, 0, (i+1)*sizeof(MemPage*));
      goto balance_cleanup;
    }


    nMaxCells += 1+apOld[i]->nCell+apOld[i]->nOverflow;
    if( (i--)==0 ) break;

    if( pParent->nOverflow && i+nxDiv==pParent->aiOvfl[0] ){
      apDiv[i] = pParent->apOvfl[0];
      pgno = get4byte(apDiv[i]);
      szNew[i] = pParent->xCellSize(pParent, apDiv[i]);
................................................................................
          ** has completed, it is safe to release the pSpace buffer used by
          ** the previous call, as the overflow cell data will have been 
          ** copied either into the body of a database page or into the new
          ** pSpace buffer passed to the latter call to balance_nonroot().
          */
          u8 *pSpace = sqlite3PageMalloc(pCur->pBt->pageSize);
          rc = balance_nonroot(pParent, iIdx, pSpace, iPage==1,
                               pCur->hints&BTREE_BULKLOAD);
          if( pFree ){
            /* If pFree is not NULL, it points to the pSpace buffer used 
            ** by a previous call to balance_nonroot(). Its contents are
            ** now stored either on real database pages or within the 
            ** new pSpace buffer, so it may be safely freed here. */
            sqlite3PageFree(pFree);
          }
................................................................................
** Erase the given database page and all its children.  Return
** the page to the freelist.
*/
static int clearDatabasePage(
  BtShared *pBt,           /* The BTree that contains the table */
  Pgno pgno,               /* Page number to clear */
  int freePageFlag,        /* Deallocate page if true */
  int *pnChange            /* Add number of Cells freed to this counter */

){
  MemPage *pPage;
  int rc;
  unsigned char *pCell;
  int i;
  int hdr;
  CellInfo info;
................................................................................

  assert( sqlite3_mutex_held(pBt->mutex) );
  if( pgno>btreePagecount(pBt) ){
    return SQLITE_CORRUPT_BKPT;
  }
  rc = getAndInitPage(pBt, pgno, &pPage, 0, 0);
  if( rc ) return rc;

  if( pPage->bBusy ){
    rc = SQLITE_CORRUPT_BKPT;
    goto cleardatabasepage_out;
  }
  pPage->bBusy = 1;
  hdr = pPage->hdrOffset;
  for(i=0; i<pPage->nCell; i++){
    pCell = findCell(pPage, i);
    if( !pPage->leaf ){
      rc = clearDatabasePage(pBt, get4byte(pCell), 1, pnChange);
      if( rc ) goto cleardatabasepage_out;
    }
    rc = clearCell(pPage, pCell, &info);
    if( rc ) goto cleardatabasepage_out;
  }
  if( !pPage->leaf ){

    rc = clearDatabasePage(pBt, get4byte(&pPage->aData[hdr+8]), 1, pnChange);

    if( rc ) goto cleardatabasepage_out;
  }else if( pnChange ){
    assert( pPage->intKey || CORRUPT_DB );
    testcase( !pPage->intKey );
    *pnChange += pPage->nCell;
  }
  if( freePageFlag ){
................................................................................
  rc = saveAllCursors(pBt, (Pgno)iTable, 0);

  if( SQLITE_OK==rc ){
    /* Invalidate all incrblob cursors open on table iTable (assuming iTable
    ** is the root of a table b-tree - if it is not, the following call is
    ** a no-op).  */
    invalidateIncrblobCursors(p, (Pgno)iTable, 0, 1);
    rc = clearDatabasePage(pBt, (Pgno)iTable, 0, pnChange);
  }
  sqlite3BtreeLeave(p);
  return rc;
}

/*
** Delete all information from the single table that pCur is open on.

getAndInitPage_error:
  if( pCur ) pCur->iPage--;
  testcase( pgno==0 );
  assert( pgno!=0 || rc==SQLITE_CORRUPT );
  return rc;
}

#ifndef SQLITE_OMIT_CONCURRENT
/* 
** Set the value of the MemPage.pgnoRoot variable, if it exists.
*/
static void setMempageRoot(MemPage *pPg, u32 pgnoRoot){
  pPg->pgnoRoot = pgnoRoot;
}
#else
# define setMempageRoot(x,y)
#endif

/*
** Release a MemPage.  This should be called once for each prior
** call to btreeGetPage.
*/
static void releasePageNotNull(MemPage *pPage){
  assert( pPage->aData );
  assert( pPage->pBt );
................................................................................
** This function returns SQLITE_CORRUPT if the page-header flags field of
** the new child page does not match the flags field of the parent (i.e.
** if an intkey page appears to be the parent of a non-intkey page, or
** vice-versa).
*/
static int moveToChild(BtCursor *pCur, u32 newPgno){
  BtShared *pBt = pCur->pBt;
  int rc;

  assert( cursorOwnsBtShared(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  assert( pCur->iPage<BTCURSOR_MAX_DEPTH );
  assert( pCur->iPage>=0 );
  if( pCur->iPage>=(BTCURSOR_MAX_DEPTH-1) ){
    return SQLITE_CORRUPT_BKPT;
  }
  pCur->info.nSize = 0;
  pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
  pCur->aiIdx[pCur->iPage++] = pCur->ix;
  pCur->ix = 0;
  rc = getAndInitPage(pBt, newPgno, &pCur->apPage[pCur->iPage],
                        pCur, pCur->curPagerFlags);
  if( rc==SQLITE_OK ){
    setMempageRoot(pCur->apPage[pCur->iPage], pCur->pgnoRoot);
  }
  return rc;
}

#ifdef SQLITE_DEBUG
/*
** Page pParent is an internal (non-leaf) tree page. This function 
** asserts that page number iChild is the left-child if the iIdx'th
** cell in page pParent. Or, if iIdx is equal to the total number of
................................................................................
    assert( pCur->iPage==(-1) );
    rc = getAndInitPage(pCur->pBtree->pBt, pCur->pgnoRoot, &pCur->apPage[0],
                        0, pCur->curPagerFlags);
    if( rc!=SQLITE_OK ){
      pCur->eState = CURSOR_INVALID;
       return rc;
    }
    setMempageRoot(pCur->apPage[0], pCur->pgnoRoot);
    pCur->iPage = 0;
    pCur->curIntKey = pCur->apPage[0]->intKey;
  }
  pRoot = pCur->apPage[0];
  assert( pRoot->pgno==pCur->pgnoRoot );

  /* If pCur->pKeyInfo is not NULL, then the caller that opened this cursor
................................................................................
** SQLITE_NOMEM.
*/
static int balance_nonroot(
  MemPage *pParent,               /* Parent page of siblings being balanced */
  int iParentIdx,                 /* Index of "the page" in pParent */
  u8 *aOvflSpace,                 /* page-size bytes of space for parent ovfl */
  int isRoot,                     /* True if pParent is a root-page */
  int bBulk,                      /* True if this call is part of a bulk load */
  Pgno pgnoRoot                   /* Root page of b-tree being balanced */
){
  BtShared *pBt;               /* The whole database */
  int nMaxCells = 0;           /* Allocated size of apCell, szCell, aFrom. */
  int nNew = 0;                /* Number of pages in apNew[] */
  int nOld;                    /* Number of pages in apOld[] */
  int i, j, k;                 /* Loop counters */
  int nxDiv;                   /* Next divider slot in pParent->aCell[] */
................................................................................
  pgno = get4byte(pRight);
  while( 1 ){
    rc = getAndInitPage(pBt, pgno, &apOld[i], 0, 0);
    if( rc ){
      memset(apOld, 0, (i+1)*sizeof(MemPage*));
      goto balance_cleanup;
    }
    setMempageRoot(apOld[i], pgnoRoot);

    nMaxCells += 1+apOld[i]->nCell+apOld[i]->nOverflow;
    if( (i--)==0 ) break;

    if( pParent->nOverflow && i+nxDiv==pParent->aiOvfl[0] ){
      apDiv[i] = pParent->apOvfl[0];
      pgno = get4byte(apDiv[i]);
      szNew[i] = pParent->xCellSize(pParent, apDiv[i]);
................................................................................
          ** has completed, it is safe to release the pSpace buffer used by
          ** the previous call, as the overflow cell data will have been 
          ** copied either into the body of a database page or into the new
          ** pSpace buffer passed to the latter call to balance_nonroot().
          */
          u8 *pSpace = sqlite3PageMalloc(pCur->pBt->pageSize);
          rc = balance_nonroot(pParent, iIdx, pSpace, iPage==1,
                               pCur->hints&BTREE_BULKLOAD, pCur->pgnoRoot);
          if( pFree ){
            /* If pFree is not NULL, it points to the pSpace buffer used 
            ** by a previous call to balance_nonroot(). Its contents are
            ** now stored either on real database pages or within the 
            ** new pSpace buffer, so it may be safely freed here. */
            sqlite3PageFree(pFree);
          }
................................................................................
** Erase the given database page and all its children.  Return
** the page to the freelist.
*/
static int clearDatabasePage(
  BtShared *pBt,           /* The BTree that contains the table */
  Pgno pgno,               /* Page number to clear */
  int freePageFlag,        /* Deallocate page if true */
  int *pnChange,           /* Add number of Cells freed to this counter */
  Pgno pgnoRoot
){
  MemPage *pPage;
  int rc;
  unsigned char *pCell;
  int i;
  int hdr;
  CellInfo info;
................................................................................

  assert( sqlite3_mutex_held(pBt->mutex) );
  if( pgno>btreePagecount(pBt) ){
    return SQLITE_CORRUPT_BKPT;
  }
  rc = getAndInitPage(pBt, pgno, &pPage, 0, 0);
  if( rc ) return rc;
  setMempageRoot(pPage, pgnoRoot);
  if( pPage->bBusy ){
    rc = SQLITE_CORRUPT_BKPT;
    goto cleardatabasepage_out;
  }
  pPage->bBusy = 1;
  hdr = pPage->hdrOffset;
  for(i=0; i<pPage->nCell; i++){
    pCell = findCell(pPage, i);
    if( !pPage->leaf ){
      rc = clearDatabasePage(pBt, get4byte(pCell), 1, pnChange, pgnoRoot);
      if( rc ) goto cleardatabasepage_out;
    }
    rc = clearCell(pPage, pCell, &info);
    if( rc ) goto cleardatabasepage_out;
  }
  if( !pPage->leaf ){
    rc = clearDatabasePage(
        pBt, get4byte(&pPage->aData[hdr+8]), 1, pnChange, pgnoRoot
    );
    if( rc ) goto cleardatabasepage_out;
  }else if( pnChange ){
    assert( pPage->intKey || CORRUPT_DB );
    testcase( !pPage->intKey );
    *pnChange += pPage->nCell;
  }
  if( freePageFlag ){
................................................................................
  rc = saveAllCursors(pBt, (Pgno)iTable, 0);

  if( SQLITE_OK==rc ){
    /* Invalidate all incrblob cursors open on table iTable (assuming iTable
    ** is the root of a table b-tree - if it is not, the following call is
    ** a no-op).  */
    invalidateIncrblobCursors(p, (Pgno)iTable, 0, 1);
    rc = clearDatabasePage(pBt, (Pgno)iTable, 0, pnChange, (Pgno)iTable);
  }
  sqlite3BtreeLeave(p);
  return rc;
}

/*
** Delete all information from the single table that pCur is open on.

  u8 *aData;           /* Pointer to disk image of the page data */
  u8 *aDataEnd;        /* One byte past the end of usable data */
  u8 *aCellIdx;        /* The cell index area */
  u8 *aDataOfst;       /* Same as aData for leaves.  aData+4 for interior */
  DbPage *pDbPage;     /* Pager page handle */
  u16 (*xCellSize)(MemPage*,u8*);             /* cellSizePtr method */
  void (*xParseCell)(MemPage*,u8*,CellInfo*); /* btreeParseCell method */



};

/*
** A linked list of the following structures is stored at BtShared.pLock.
** Locks are added (or upgraded from READ_LOCK to WRITE_LOCK) when a cursor 
** is opened on the table with root page BtShared.iTable. Locks are removed
** from this list when a transaction is committed or rolled back, or when

  u8 *aData;           /* Pointer to disk image of the page data */
  u8 *aDataEnd;        /* One byte past the end of usable data */
  u8 *aCellIdx;        /* The cell index area */
  u8 *aDataOfst;       /* Same as aData for leaves.  aData+4 for interior */
  DbPage *pDbPage;     /* Pager page handle */
  u16 (*xCellSize)(MemPage*,u8*);             /* cellSizePtr method */
  void (*xParseCell)(MemPage*,u8*,CellInfo*); /* btreeParseCell method */
#ifndef SQLITE_OMIT_CONCURRENT
  u32 pgnoRoot;        /* Root page of b-tree that this page belongs to */
#endif
};

/*
** A linked list of the following structures is stored at BtShared.pLock.
** Locks are added (or upgraded from READ_LOCK to WRITE_LOCK) when a cursor 
** is opened on the table with root page BtShared.iTable. Locks are removed
** from this list when a transaction is committed or rolled back, or when

** When a rollback occurs, the value of K is decreased. Hash table entries
** that correspond to frames greater than the new K value are removed
** from the hash table at this point.
*/
#ifndef SQLITE_OMIT_WAL

#include "wal.h"


/*
** Trace output macros
*/
#if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
int sqlite3WalTrace = 0;
# define WALTRACE(X)  if(sqlite3WalTrace) sqlite3DebugPrintf X
................................................................................
              sz = (sz&0xfe00) + ((sz&0x0001)<<16);
              iOffset = walFrameOffset(i+iZero, sz) + WAL_FRAME_HDRSIZE + 40;
              rc = sqlite3OsRead(pWal->pWalFd, aNew, sizeof(aNew), iOffset);
              if( rc==SQLITE_OK && memcmp(aOld, aNew, sizeof(aNew)) ){
                rc = SQLITE_BUSY_SNAPSHOT;
              }
            }else if( sqlite3BitvecTestNotNull(pAllRead, aPgno[i]) ){










              sqlite3_log(SQLITE_OK,
                  "cannot commit CONCURRENT transaction (conflict at page %d)",


                  (int)aPgno[i]


              );
              rc = SQLITE_BUSY_SNAPSHOT;

            }else if( (pPg = sqlite3PagerLookup(pPager, aPgno[i])) ){
              /* Page aPgno[i], which is present in the pager cache, has been
              ** modified since the current CONCURRENT transaction was started.
              ** However it was not read by the current transaction, so is not
              ** a conflict. There are two possibilities: (a) the page was
              ** allocated at the of the file by the current transaction or 
              ** (b) was present in the cache at the start of the transaction.

** When a rollback occurs, the value of K is decreased. Hash table entries
** that correspond to frames greater than the new K value are removed
** from the hash table at this point.
*/
#ifndef SQLITE_OMIT_WAL

#include "wal.h"
#include "btreeInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
int sqlite3WalTrace = 0;
# define WALTRACE(X)  if(sqlite3WalTrace) sqlite3DebugPrintf X
................................................................................
              sz = (sz&0xfe00) + ((sz&0x0001)<<16);
              iOffset = walFrameOffset(i+iZero, sz) + WAL_FRAME_HDRSIZE + 40;
              rc = sqlite3OsRead(pWal->pWalFd, aNew, sizeof(aNew), iOffset);
              if( rc==SQLITE_OK && memcmp(aOld, aNew, sizeof(aNew)) ){
                rc = SQLITE_BUSY_SNAPSHOT;
              }
            }else if( sqlite3BitvecTestNotNull(pAllRead, aPgno[i]) ){
              PgHdr *pPg = 0;
              rc = sqlite3PagerGet(pPage1->pPager, aPgno[i], &pPg, 0);
              if( rc==SQLITE_OK ){
                Pgno pgnoRoot = 0;
                int bWrite = -1;
                if( pPg ){
                  pgnoRoot = ((MemPage*)sqlite3PagerGetExtra(pPg))->pgnoRoot;
                  bWrite = sqlite3PagerIswriteable(pPg);
                  sqlite3PagerUnref(pPg);
                }
                sqlite3_log(SQLITE_OK,
                  "cannot commit CONCURRENT transaction "
                  "- conflict at page %d "
                  "(%s page; part of b-tree with root page %d)",
                  (int)aPgno[i], 
                  (bWrite==0?"read-only":(bWrite>0?"read/write":"unknown")),
                  (int)pgnoRoot
                );
                rc = SQLITE_BUSY_SNAPSHOT;
              }
            }else if( (pPg = sqlite3PagerLookup(pPager, aPgno[i])) ){
              /* Page aPgno[i], which is present in the pager cache, has been
              ** modified since the current CONCURRENT transaction was started.
              ** However it was not read by the current transaction, so is not
              ** a conflict. There are two possibilities: (a) the page was
              ** allocated at the of the file by the current transaction or 
              ** (b) was present in the cache at the start of the transaction.

# 2017 May 26
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
source $testdir/lock_common.tcl
source $testdir/wal_common.tcl
set ::testprefix concurrent5

ifcapable !concurrent {
  finish_test
  return
}

db close
sqlite3_shutdown
test_sqlite3_log [list lappend ::log]
set ::log [list]

sqlite3 db test.db

proc do_test_conflict_msg {tn msg} {
  set msg "cannot commit CONCURRENT transaction - [string trim $msg]"
  uplevel [list do_test $tn {lindex $::log end} $msg]
}

do_execsql_test 1.0 {
  PRAGMA journal_mode = wal;
  CREATE TABLE t1(x, y);
  CREATE TABLE t2(c);
  WITH s(i) AS (SELECT 1 UNION ALL SELECT i+1 FROM s WHERE i<100)
  INSERT INTO t1 SELECT randomblob(400), randomblob(400) FROM s;
} {wal}

sqlite3 db2 test.db

do_test 1.1.1 {
  set ::log [list]
  db2 eval {
    BEGIN CONCURRENT;
      SELECT count(*) FROM t1;
      INSERT INTO t2 VALUES(10);
  }

  db eval {
    INSERT INTO t1 VALUES(randomblob(200), randomblob(200));
  }

  catchsql COMMIT db2
} {1 {database is locked}}
do_test_conflict_msg 1.1.2 {
  conflict at page 2 (read-only page; part of b-tree with root page 2)
}

do_test 1.2.1 {
  set ::log [list]
  db2 eval {
    ROLLBACK;
    BEGIN CONCURRENT;
      INSERT INTO t1 VALUES(11, 12);
  }

  db eval {
    INSERT INTO t1 VALUES(12, 11);
  }

  catchsql COMMIT db2
} {1 {database is locked}}

do_test_conflict_msg 1.2.2 {
  conflict at page 105 (read/write page; part of b-tree with root page 2)
}

do_test 1.3.1 {
  set ::log [list]
  db2 eval {
    ROLLBACK;
    BEGIN CONCURRENT;
      INSERT INTO t2 VALUES('x');
  }

  db eval {
    INSERT INTO t2 VALUES('y');
  }

  catchsql COMMIT db2
} {1 {database is locked}}

do_test_conflict_msg 1.3.2 {
  conflict at page 3 (read/write page; part of b-tree with root page 3)
}

db close
db2 close
sqlite3_shutdown
test_sqlite3_log 
sqlite3_initialize
finish_test