Add code to handle recursive CTEs.

FossilOrigin-Name: a5c2a54a07d35166911abc792008c05dea897742

6 files changed, 222 insertions, 20 deletions

diff --git a/src/btree.c b/src/btree.c
index 20bed057e..e28a97c84 100644
--- a/src/btree.c
+++ b/src/btree.c
@@ -7350,6 +7350,7 @@ static int clearDatabasePage(
   int rc;
   unsigned char *pCell;
   int i;
+  int hdr;
 
   assert( sqlite3_mutex_held(pBt->mutex) );
   if( pgno>btreePagecount(pBt) ){
@@ -7358,6 +7359,7 @@ static int clearDatabasePage(
 
   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 ){
@@ -7368,7 +7370,7 @@ static int clearDatabasePage(
     if( rc ) goto cleardatabasepage_out;
   }
   if( !pPage->leaf ){
-    rc = clearDatabasePage(pBt, get4byte(&pPage->aData[8]), 1, pnChange);
+    rc = clearDatabasePage(pBt, get4byte(&pPage->aData[hdr+8]), 1, pnChange);
     if( rc ) goto cleardatabasepage_out;
   }else if( pnChange ){
     assert( pPage->intKey );
@@ -7377,7 +7379,7 @@ static int clearDatabasePage(
   if( freePageFlag ){
     freePage(pPage, &rc);
   }else if( (rc = sqlite3PagerWrite(pPage->pDbPage))==0 ){
-    zeroPage(pPage, pPage->aData[0] | PTF_LEAF);
+    zeroPage(pPage, pPage->aData[hdr] | PTF_LEAF);
   }
 
 cleardatabasepage_out:
diff --git a/src/expr.c b/src/expr.c
index d0ea28002..e271e4679 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -1055,6 +1055,7 @@ Select *sqlite3SelectDup(sqlite3 *db, Select *p, int flags){
   pNew->addrOpenEphm[1] = -1;
   pNew->addrOpenEphm[2] = -1;
   pNew->pWith = withDup(db, p->pWith);
+  pNew->pRecurse = p->pRecurse;
   return pNew;
 }
 #else
diff --git a/src/select.c b/src/select.c
index b054489b0..0db4b0180 100644
--- a/src/select.c
+++ b/src/select.c
@@ -691,12 +691,26 @@ static void selectInnerLoop(
 
     /* 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{
@@ -1729,6 +1743,7 @@ static int multiSelect(
   ** 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 );
@@ -1774,12 +1789,82 @@ static int multiSelect(
     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 ){
@@ -3449,6 +3534,73 @@ static void ctePop(Parse *pParse, struct Cte *pCte){
   }
 }
 
+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.
@@ -3515,31 +3667,22 @@ static int selectExpander(Walker *pWalker, Select *p){
 #ifndef SQLITE_OMIT_CTE
     pCte = searchWith(pParse, pFrom);
     if( pCte ){
-      pFrom->pSelect = sqlite3SelectDup(db, pCte->pSelect, 0);
-      if( pFrom->pSelect==0 ) return WRC_Abort;
-    }
+      if( withExpand(pWalker, pFrom, pCte) ) return WRC_Abort;
+    }else
 #endif
-    if( pFrom->zName==0 || pCte ){
+    if( pFrom->zName==0 ){
 #ifndef SQLITE_OMIT_SUBQUERY
-      ExprList *pEList;
       Select *pSel = pFrom->pSelect;
       /* A sub-query in the FROM clause of a SELECT */
       assert( pSel!=0 );
       assert( pFrom->pTab==0 );
-      if( ctePush(pParse, pCte) ) return WRC_Abort;
       sqlite3WalkSelect(pWalker, pSel);
-      ctePop(pParse, pCte);
       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; }
-      if( pCte && pCte->pCols ){
-        pEList = pCte->pCols;
-      }else{
-        pEList = pSel->pEList;
-      }
-      selectColumnsFromExprList(pParse, pEList, &pTab->nCol, &pTab->aCol);
+      selectColumnsFromExprList(pParse, pSel->pEList, &pTab->nCol, &pTab->aCol);
       pTab->iPKey = -1;
       pTab->nRowEst = 1048576;
       pTab->tabFlags |= TF_Ephemeral;
@@ -3831,9 +3974,10 @@ static int selectAddSubqueryTypeInfo(Walker *pWalker, Select *p){
       if( ALWAYS(pTab!=0) && (pTab->tabFlags & TF_Ephemeral)!=0 ){
         /* A sub-query in the FROM clause of a SELECT */
         Select *pSel = pFrom->pSelect;
-        assert( pSel );
-        while( pSel->pPrior ) pSel = pSel->pPrior;
-        selectAddColumnTypeAndCollation(pParse, pTab, pSel);
+        if( pSel ){
+          while( pSel->pPrior ) pSel = pSel->pPrior;
+          selectAddColumnTypeAndCollation(pParse, pTab, pSel);
+        }
       }
     }
   }
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 6bd65592b..c7f0609ba 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -1429,7 +1429,7 @@ struct Table {
 };
 
 /*
-** Allowed values for Tabe.tabFlags.
+** Allowed values for Table.tabFlags.
 */
 #define TF_Readonly        0x01    /* Read-only system table */
 #define TF_Ephemeral       0x02    /* An ephemeral table */
@@ -1437,6 +1437,7 @@ struct Table {
 #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 */
 
 
 /*
@@ -2129,6 +2130,7 @@ struct NameContext {
 */
 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 */
@@ -2182,6 +2184,7 @@ struct Select {
 #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
@@ -2647,6 +2650,7 @@ struct With {
     ExprList *pCols;              /* List of explicit column names, or NULL */
     Select *pSelect;              /* The contents of the CTE */
     struct Cte *pOuterCte;
+    Table *pTab;
   } a[1];
 };
 
diff --git a/src/vdbe.c b/src/vdbe.c
index 286bc45ba..ffb4dd19b 100644
--- a/src/vdbe.c
+++ b/src/vdbe.c
@@ -3369,6 +3369,53 @@ case OP_OpenEphemeral: {
   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
diff --git a/src/where.c b/src/where.c
index d5444a605..8827faa83 100644
--- a/src/where.c
+++ b/src/where.c
@@ -5653,7 +5653,11 @@ WhereInfo *sqlite3WhereBegin(
     iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
     pLoop = pLevel->pWLoop;
     if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){
-      /* Do nothing */
+      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 ){