SQLite

  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;

  assert( sqlite3_mutex_held(pBt->mutex) );
  if( pgno>btreePagecount(pBt) ){
    return SQLITE_CORRUPT_BKPT;
  }

  rc = getAndInitPage(pBt, pgno, &pPage, 0);
  if( rc ) return rc;
  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);
    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 );
    *pnChange += pPage->nCell;
  }
  if( freePageFlag ){
    freePage(pPage, &rc);
  }else if( (rc = sqlite3PagerWrite(pPage->pDbPage))==0 ){
    zeroPage(pPage, pPage->aData[hdr] | PTF_LEAF);
  }

cleardatabasepage_out:
  releasePage(pPage);
  return rc;
}

  pNew->iOffset = 0;
  pNew->selFlags = p->selFlags & ~SF_UsesEphemeral;
  pNew->pRightmost = 0;
  pNew->addrOpenEphm[0] = -1;
  pNew->addrOpenEphm[1] = -1;
  pNew->addrOpenEphm[2] = -1;
  pNew->pWith = withDup(db, p->pWith);
  pNew->pRecurse = p->pRecurse;
  return pNew;
}
#else
Select *sqlite3SelectDup(sqlite3 *db, Select *p, int flags){
  assert( p==0 );
  return 0;
}

      sqlite3VdbeAddOp3(v, OP_IdxDelete, iParm, regResult, nColumn);
      break;
    }
#endif

    /* Store the result as data using a unique key.
    */
    case SRT_DistTable:
    case SRT_Table:
    case SRT_EphemTab: {
      int r1 = sqlite3GetTempReg(pParse);
      testcase( eDest==SRT_Table );
      testcase( eDest==SRT_EphemTab );
      sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nColumn, r1);
#ifndef SQLITE_OMIT_CTE
      if( eDest==SRT_DistTable ){
        /* If the destination is DistTable, then cursor (iParm+1) is open
        ** on an ephemeral index. If the current row is already present
        ** in the index, do not write it to the output. If not, add the
        ** current row to the index and proceed with writing it to the
        ** output table as well.  */
        int addr = sqlite3VdbeCurrentAddr(v) + 4;
        sqlite3VdbeAddOp4Int(v, OP_Found, iParm+1, addr, r1, 0);
        sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm+1, r1);
        assert( pOrderBy==0 );
      }
#endif
      if( pOrderBy ){
        pushOntoSorter(pParse, pOrderBy, p, r1);
      }else{
        int r2 = sqlite3GetTempReg(pParse);
        sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, r2);
        sqlite3VdbeAddOp3(v, OP_Insert, iParm, r1, r2);
        sqlite3VdbeChangeP5(v, OPFLAG_APPEND);

  int iSub2;            /* EQP id of right-hand query */
#endif

  /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs.  Only
  ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT.
  */
  assert( p && p->pPrior );  /* Calling function guarantees this much */
  assert( p->pRecurse==0 || p->op==TK_ALL || p->op==TK_UNION );
  db = pParse->db;
  pPrior = p->pPrior;
  assert( pPrior->pRightmost!=pPrior );
  assert( pPrior->pRightmost==p->pRightmost );
  dest = *pDest;
  if( pPrior->pOrderBy ){
    sqlite3ErrorMsg(pParse,"ORDER BY clause should come after %s not before",

    }else{
      sqlite3ErrorMsg(pParse, "SELECTs to the left and right of %s"
        " do not have the same number of result columns", selectOpName(p->op));
    }
    rc = 1;
    goto multi_select_end;
  }

  /* If this is a recursive query, check that there is no ORDER BY or
  ** LIMIT clause. Neither of these are supported.  */
  assert( p->pOffset==0 || p->pLimit );
  if( p->pRecurse && (p->pOrderBy || p->pLimit) ){
    sqlite3ErrorMsg(pParse, "%s in a recursive query is not allowed",
        p->pOrderBy ? "ORDER BY" : "LIMIT"
    );
    goto multi_select_end;
  }

  /* Compound SELECTs that have an ORDER BY clause are handled separately.
  */
  if( p->pOrderBy ){
    return multiSelectOrderBy(pParse, p, pDest);
  }

#ifndef SQLITE_OMIT_CTE
  if( p->pRecurse ){
    int nCol = p->pEList->nExpr;
    int addrNext;
    int addrSwap;
    int iCont, iBreak;
    int tmp1, tmp2;               /* Cursors used to access temporary tables */
    int tmp3 = 0;                 /* To ensure unique results if UNION */
    int eDest = SRT_Table;
    SelectDest tmp2dest;

    iBreak = sqlite3VdbeMakeLabel(v);
    iCont = sqlite3VdbeMakeLabel(v);

    tmp1 = pParse->nTab++;
    tmp2 = pParse->nTab++;
    if( p->op==TK_UNION ){
      eDest = SRT_DistTable;
      tmp3 = pParse->nTab++;
    }
    sqlite3SelectDestInit(&tmp2dest, eDest, tmp2);

    sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tmp1, nCol);
    sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tmp2, nCol);
    if( tmp3 ){
      p->addrOpenEphm[0] = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tmp3, 0);
      p->selFlags |= SF_UsesEphemeral;
    }

    /* Store the results of the initial SELECT in tmp2. */
    rc = sqlite3Select(pParse, pPrior, &tmp2dest);
    if( rc ) goto multi_select_end;

    /* Clear tmp1. Then switch the contents of tmp1 and tmp2. Then teturn 
    ** the contents of tmp1 to the caller. Or, if tmp1 is empty at this
    ** point, the recursive query has finished - jump to address iBreak.  */
    addrSwap = sqlite3VdbeAddOp2(v, OP_SwapCursors, tmp1, tmp2);
    sqlite3VdbeAddOp2(v, OP_Rewind, tmp1, iBreak);
    addrNext = sqlite3VdbeCurrentAddr(v);
    selectInnerLoop(pParse, p, p->pEList, tmp1, p->pEList->nExpr,
        0, 0, &dest, iCont, iBreak);
    sqlite3VdbeResolveLabel(v, iCont);
    sqlite3VdbeAddOp2(v, OP_Next, tmp1, addrNext);

    /* Execute the recursive SELECT. Store the results in tmp2. While this
    ** SELECT is running, the contents of tmp1 are read by recursive 
    ** references to the current CTE.  */
    p->pPrior = 0;
    p->pRecurse->tnum = tmp1;
    p->pRecurse->tabFlags |= TF_Recursive;
    rc = sqlite3Select(pParse, p, &tmp2dest);
    p->pRecurse->tabFlags &= ~TF_Recursive;
    p->pPrior = pPrior;
    if( rc ) goto multi_select_end;

    sqlite3VdbeAddOp2(v, OP_Goto, 0, addrSwap);
    sqlite3VdbeResolveLabel(v, iBreak);
  }else
#endif

  /* Generate code for the left and right SELECT statements.
  */
  switch( p->op ){
    case TK_ALL: {
      int addr = 0;
      int nLimit;

static void ctePop(Parse *pParse, struct Cte *pCte){
  if( pCte ){
    assert( pParse->pCte==pCte );
    pParse->pCte = pCte->pOuterCte;
  }
}

static int withExpand(
  Walker *pWalker, 
  struct SrcList_item *pFrom,
  struct Cte *pCte
){
  Table *pTab;
  Parse *pParse = pWalker->pParse;
  sqlite3 *db = pParse->db;

  assert( pFrom->pSelect==0 );
  assert( pFrom->pTab==0 );

  if( pCte==pParse->pCte && (pTab = pCte->pTab) ){
    /* This is the recursive part of a recursive CTE */
    pFrom->pTab = pTab;
    pTab->nRef++;
  }else{
    ExprList *pEList;
    Select *pSel;
    int bRecursive;

    pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));
    if( pTab==0 ) return WRC_Abort;
    pTab->nRef = 1;
    pTab->zName = sqlite3MPrintf(db, "sqlite_sq_%p", (void*)pTab);
    pTab->iPKey = -1;
    pTab->nRowEst = 1048576;
    pTab->tabFlags |= TF_Ephemeral;
    pFrom->pSelect = sqlite3SelectDup(db, pCte->pSelect, 0);
    if( db->mallocFailed ) return SQLITE_NOMEM;
    assert( pFrom->pSelect );

    if( ctePush(pParse, pCte) ) return WRC_Abort;
    pSel = pFrom->pSelect;
    bRecursive = (pSel->op==TK_ALL || pSel->op==TK_UNION);
    if( bRecursive ){
      assert( pSel->pPrior );
      sqlite3WalkSelect(pWalker, pSel->pPrior);
    }else{
      sqlite3WalkSelect(pWalker, pSel);
    }

    if( pCte->pCols ){
      pEList = pCte->pCols;
    }else{
      Select *pLeft;
      for(pLeft=pSel; pLeft->pPrior; pLeft=pLeft->pPrior);
      pEList = pLeft->pEList;
    }
    selectColumnsFromExprList(pParse, pEList, &pTab->nCol, &pTab->aCol);

    if( bRecursive ){
      int nRef = pTab->nRef;
      pCte->pTab = pTab;
      sqlite3WalkSelect(pWalker, pSel);
      pCte->pTab = 0;
      if( pTab->nRef > nRef){
        pSel->pRecurse = pTab;
        assert( pTab->tnum==0 );
      }
    }

    ctePop(pParse, pCte);
  }

  return SQLITE_OK;
}

/*
** This routine is a Walker callback for "expanding" a SELECT statement.
** "Expanding" means to do the following:
**
**    (1)  Make sure VDBE cursor numbers have been assigned to every
**         element of the FROM clause.

      ** to go further. */
      assert( i==0 );
      return WRC_Prune;
    }
#ifndef SQLITE_OMIT_CTE
    pCte = searchWith(pParse, pFrom);
    if( pCte ){

      if( withExpand(pWalker, pFrom, pCte) ) return WRC_Abort;
    }else
#endif
    if( pFrom->zName==0 ){
#ifndef SQLITE_OMIT_SUBQUERY

      Select *pSel = pFrom->pSelect;
      /* A sub-query in the FROM clause of a SELECT */
      assert( pSel!=0 );
      assert( pFrom->pTab==0 );

      sqlite3WalkSelect(pWalker, pSel);

      pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));
      if( pTab==0 ) return WRC_Abort;
      pTab->nRef = 1;
      pTab->zName = sqlite3MPrintf(db, "sqlite_sq_%p", (void*)pTab);
      while( pSel->pPrior ){ pSel = pSel->pPrior; }





      selectColumnsFromExprList(pParse, pSel->pEList, &pTab->nCol, &pTab->aCol);
      pTab->iPKey = -1;
      pTab->nRowEst = 1048576;
      pTab->tabFlags |= TF_Ephemeral;
#endif
    }else{
      /* An ordinary table or view name in the FROM clause */
      assert( pFrom->pTab==0 );

    pParse = pWalker->pParse;
    pTabList = p->pSrc;
    for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){
      Table *pTab = pFrom->pTab;
      if( ALWAYS(pTab!=0) && (pTab->tabFlags & TF_Ephemeral)!=0 ){
        /* A sub-query in the FROM clause of a SELECT */
        Select *pSel = pFrom->pSelect;
        if( pSel ){
          while( pSel->pPrior ) pSel = pSel->pPrior;
          selectAddColumnTypeAndCollation(pParse, pTab, pSel);
        }
      }
    }
  }
  return WRC_Continue;
}
#endif

#endif
  Trigger *pTrigger;   /* List of triggers stored in pSchema */
  Schema *pSchema;     /* Schema that contains this table */
  Table *pNextZombie;  /* Next on the Parse.pZombieTab list */
};

/*
** Allowed values for Table.tabFlags.
*/
#define TF_Readonly        0x01    /* Read-only system table */
#define TF_Ephemeral       0x02    /* An ephemeral table */
#define TF_HasPrimaryKey   0x04    /* Table has a primary key */
#define TF_Autoincrement   0x08    /* Integer primary key is autoincrement */
#define TF_Virtual         0x10    /* Is a virtual table */
#define TF_WithoutRowid    0x20    /* No rowid used. PRIMARY KEY is the key */
#define TF_Recursive       0x40    /* Recursive reference within CTE */


/*
** Test to see whether or not a table is a virtual table.  This is
** done as a macro so that it will be optimized out when virtual
** table support is omitted from the build.
*/

** enough information about the compound query is known at that point.
** The KeyInfo for addrOpenTran[0] and [1] contains collating sequences
** for the result set.  The KeyInfo for addrOpenEphm[2] contains collating
** sequences for the ORDER BY clause.
*/
struct Select {
  ExprList *pEList;      /* The fields of the result */
  Table *pRecurse;       /* Non-NULL for the recursive part of recursive CTE */
  u8 op;                 /* One of: TK_UNION TK_ALL TK_INTERSECT TK_EXCEPT */
  u16 selFlags;          /* Various SF_* values */
  int iLimit, iOffset;   /* Memory registers holding LIMIT & OFFSET counters */
  int addrOpenEphm[3];   /* OP_OpenEphem opcodes related to this select */
  u64 nSelectRow;        /* Estimated number of result rows */
  SrcList *pSrc;         /* The FROM clause */
  Expr *pWhere;          /* The WHERE clause */

#define SRT_Output       5  /* Output each row of result */
#define SRT_Mem          6  /* Store result in a memory cell */
#define SRT_Set          7  /* Store results as keys in an index */
#define SRT_Table        8  /* Store result as data with an automatic rowid */
#define SRT_EphemTab     9  /* Create transient tab and store like SRT_Table */
#define SRT_Coroutine   10  /* Generate a single row of result */
#define SRT_DistTable   11  /* Like SRT_TABLE, but unique results only */

/*
** An instance of this object describes where to put of the results of
** a SELECT statement.
*/
struct SelectDest {
  u8 eDest;         /* How to dispose of the results.  On of SRT_* above. */

  int nCte;                       /* Number of CTEs */
  With *pOuter;                   /* Containing WITH clause, or NULL */
  struct Cte {
    char *zName;                  /* Name of this CTE */
    ExprList *pCols;              /* List of explicit column names, or NULL */
    Select *pSelect;              /* The contents of the CTE */
    struct Cte *pOuterCte;
    Table *pTab;
  } a[1];
};

/*
** Assuming zIn points to the first byte of a UTF-8 character,
** advance zIn to point to the first byte of the next UTF-8 character.
*/

      rc = sqlite3BtreeCursor(pCx->pBt, MASTER_ROOT, 1, 0, pCx->pCursor);
      pCx->isTable = 1;
    }
  }
  pCx->isOrdered = (pOp->p5!=BTREE_UNORDERED);
  break;
}

/* Opcode: OpenEphreader P1 P2 * * *
**
** P2 is a cursor opened by the OpenEphemeral opcode. This opcode opens
** a new read-only cursor named P1 that accesses the same epheremal table 
** as P2.
*/
case OP_OpenEphreader: {
  VdbeCursor *pEph;
  VdbeCursor *pCx;
  Pgno pgno;

  pEph = p->apCsr[pOp->p2];
  pCx = allocateCursor(p, pOp->p1, pEph->nField, -1, 1);
  if( pCx==0 ) goto no_mem;
  pCx->nullRow = 1;
  pCx->pKeyInfo = pEph->pKeyInfo;
  pCx->isTable = pEph->isTable;
  pCx->isOrdered = pEph->isOrdered;
  pgno = MASTER_ROOT + !pCx->isTable;
  rc = sqlite3BtreeCursor(pEph->pBt, pgno, 0, pCx->pKeyInfo, pCx->pCursor);
  break;
}

/* Opcode: SwapCursors P1 P2 * * *
**
** Parameters P1 and P2 are both cursors opened by the OpenEphemeral
** opcode. This opcode deletes the contents of epheremal table P1,
** then renames P2 to P1 and P1 to P2. In other words, following this
** opcode cursor P2 is open on an empty table and P1 is open on the
** table that was initially accessed by P2.
*/
case OP_SwapCursors: {
  Mem tmp;
  VdbeCursor *pTmp;

  tmp = p->aMem[p->nMem - pOp->p1];
  p->aMem[p->nMem - pOp->p1] = p->aMem[p->nMem - pOp->p2];
  p->aMem[p->nMem - pOp->p2] = tmp;

  pTmp = p->apCsr[pOp->p1];
  p->apCsr[pOp->p1] = p->apCsr[pOp->p2];
  p->apCsr[pOp->p2] = pTmp;

  rc = sqlite3BtreeClearTable(pTmp->pBt, MASTER_ROOT + !pTmp->isTable, 0);
  break;
}

/* Opcode: SorterOpen P1 * * P4 *
**
** This opcode works like OP_OpenEphemeral except that it opens
** a transient index that is specifically designed to sort large
** tables using an external merge-sort algorithm.
*/

    struct SrcList_item *pTabItem;

    pTabItem = &pTabList->a[pLevel->iFrom];
    pTab = pTabItem->pTab;
    iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
    pLoop = pLevel->pWLoop;
    if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){
      if( pTab->tabFlags & TF_Recursive ){
        int iCur = pTabItem->iCursor;
        sqlite3VdbeAddOp2(v, OP_OpenEphreader, iCur, pTab->tnum);
      }
      /* Otherwise do nothing */
    }else
#ifndef SQLITE_OMIT_VIRTUALTABLE
    if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 ){
      const char *pVTab = (const char *)sqlite3GetVTable(db, pTab);
      int iCur = pTabItem->iCursor;
      sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB);
    }else if( IsVirtual(pTab) ){

} {1 3 2 4}

do_execsql_test 4.3 {
  WITH uset(a, b) AS ( SELECT 2, 8 UNION ALL SELECT 4, 9 )
  UPDATE t1 SET x = COALESCE( (SELECT b FROM uset WHERE a=x), x );
  SELECT * FROM t1;
} {1 3 8 9}

#-------------------------------------------------------------------------
#
do_execsql_test 5.1 {
  WITH i(x) AS ( VALUES(1) UNION ALL SELECT x+1 FROM i)
  SELECT x FROM i LIMIT 10;
} {1 2 3 4 5 6 7 8 9 10}

do_catchsql_test 5.2 {
  WITH i(x) AS ( VALUES(1) UNION ALL SELECT x+1 FROM i ORDER BY 1)
  SELECT x FROM i LIMIT 10;
} {1 {ORDER BY in a recursive query is not allowed}}

do_catchsql_test 5.3 {
  WITH i(x) AS ( VALUES(1) UNION ALL SELECT x+1 FROM i LIMIT 10 )
  SELECT x FROM i LIMIT 10;
} {1 {LIMIT in a recursive query is not allowed}}

do_execsql_test 5.4 {
  WITH i(x) AS ( VALUES(1) UNION ALL SELECT (x+1)%10 FROM i)
  SELECT x FROM i LIMIT 20;
} {1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0}

do_execsql_test 5.5 {
  WITH i(x) AS ( VALUES(1) UNION SELECT (x+1)%10 FROM i)
  SELECT x FROM i LIMIT 20;
} {1 2 3 4 5 6 7 8 9 0}

finish_test