Allow only a single recursive reference in a recursive CTE. Also require that this reference is not part of a sub-query.

FossilOrigin-Name: a296b73360d34c9364eceb2cc09a9a92adc4abb8

5 files changed, 51 insertions, 74 deletions

diff --git a/src/expr.c b/src/expr.c
index 897da77ed..0614be1cf 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -1065,7 +1065,6 @@ 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 c5fb15cd8..d70d815a2 100644
--- a/src/select.c
+++ b/src/select.c
@@ -1744,7 +1744,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 );
+  assert( (p->selFlags & SF_Recursive)==0 || p->op==TK_ALL || p->op==TK_UNION );
   db = pParse->db;
   pPrior = p->pPrior;
   assert( pPrior->pRightmost!=pPrior );
@@ -1794,27 +1794,36 @@ static int multiSelect(
   /* 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) ){
+  if( (p->selFlags & SF_Recursive) && (p->pOrderBy || p->pLimit) ){
     sqlite3ErrorMsg(pParse, "%s in a recursive query is not allowed",
         p->pOrderBy ? "ORDER BY" : "LIMIT"
     );
     goto multi_select_end;
   }
 
-  if( p->pRecurse ){
+  if( p->selFlags & SF_Recursive ){
+    SrcList *pSrc = p->pSrc;
     int nCol = p->pEList->nExpr;
     int addrNext;
     int addrSwap;
     int iCont, iBreak;
-    int tmp1, tmp2;               /* Cursors used to access temporary tables */
+    int tmp1;                     /* Intermediate table */
+    int tmp2;                     /* Next intermediate table */
     int tmp3 = 0;                 /* To ensure unique results if UNION */
     int eDest = SRT_Table;
     SelectDest tmp2dest;
+    int i;
 
     iBreak = sqlite3VdbeMakeLabel(v);
     iCont = sqlite3VdbeMakeLabel(v);
 
-    tmp1 = pParse->nTab++;
+    for(i=0; ALWAYS(i<pSrc->nSrc); i++){
+      if( pSrc->a[i].isRecursive ){
+        tmp1 = pSrc->a[i].iCursor;
+        break;
+      }
+    }
+
     tmp2 = pParse->nTab++;
     if( p->op==TK_UNION ){
       eDest = SRT_DistTable;
@@ -1848,11 +1857,7 @@ static int multiSelect(
     ** SELECT is running, the contents of tmp1 are read by recursive 
     ** references to the current CTE.  */
     p->pPrior = 0;
-    p->pRecurse->tnum = tmp1;
-    assert( (p->pRecurse->tabFlags & TF_Recursive)==0 );
-    p->pRecurse->tabFlags |= TF_Recursive;
     rc = sqlite3Select(pParse, p, &tmp2dest);
-    p->pRecurse->tabFlags &= ~TF_Recursive;
     assert( p->pPrior==0 );
     p->pPrior = pPrior;
     if( rc ) goto multi_select_end;
@@ -3009,8 +3014,8 @@ static int flattenSubquery(
   if( pSub->pLimit && (p->selFlags & SF_Distinct)!=0 ){
      return 0;         /* Restriction (21) */
   }
-  if( pSub->pRecurse ) return 0;                         /* Restriction (22)  */
-  if( p->pRecurse && pSub->pPrior ) return 0;            /* Restriction (23)  */
+  if( pSub->selFlags & SF_Recursive ) return 0;          /* Restriction (22)  */
+  if( (p->selFlags & SF_Recursive) && pSub->pPrior ) return 0;       /* (23)  */
 
   /* OBSOLETE COMMENT 1:
   ** Restriction 3:  If the subquery is a join, make sure the subquery is 
@@ -3593,19 +3598,10 @@ static int withExpand(
   assert( pFrom->pTab==0 );
 
   pCte = searchWith(pParse->pWith, pFrom);
-  if( pCte==0 ){
-    /* no-op */
-  }else if( pCte==pParse->pCte && (pTab = pCte->pTab) ){
-    /* This is the recursive part of a recursive CTE */
-    assert( pFrom->pTab==0 && pFrom->isRecursive==0 && pFrom->pSelect==0 );
-    pFrom->pTab = pTab;
-    pFrom->isRecursive = 1;
-    pTab->nRef++;
-  }else{
+  if( pCte ){
     ExprList *pEList;
     Select *pSel;
     Select *pLeft;                /* Left-most SELECT statement */
-    int bRecursive;
 
     pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));
     if( pTab==0 ) return WRC_Abort;
@@ -3618,15 +3614,36 @@ static int withExpand(
     if( db->mallocFailed ) return SQLITE_NOMEM;
     assert( pFrom->pSelect );
 
-    if( ctePush(pParse, pCte) ) return WRC_Abort;
+    /* Check if this is a recursive CTE. */
     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( pSel->op==TK_ALL || pSel->op==TK_UNION ){
+      int i;
+      SrcList *pSrc = pFrom->pSelect->pSrc;
+      for(i=0; i<pSrc->nSrc; i++){
+        struct SrcList_item *pItem = &pSrc->a[i];
+        if( pItem->zDatabase==0 
+         && pItem->zName!=0 
+         && 0==sqlite3StrICmp(pItem->zName, pCte->zName)
+          ){
+          pItem->pTab = pTab;
+          pItem->isRecursive = 1;
+          pTab->nRef++;
+          pSel->selFlags |= SF_Recursive;
+        }
+      }
+    }
+
+    /* Only one recursive reference is permitted. */ 
+    if( pTab->nRef>2 ){
+      sqlite3ErrorMsg(
+          pParse, "multiple recursive references in cte: %s", pCte->zName
+      );
+      return WRC_Abort;
     }
+    assert( pTab->nRef==1 || ((pSel->selFlags&SF_Recursive) && pTab->nRef==2 ));
+
+    if( ctePush(pParse, pCte) ) return WRC_Abort;
+    sqlite3WalkSelect(pWalker, pTab->nRef==2 ? pSel->pPrior : pSel);
 
     for(pLeft=pSel; pLeft->pPrior; pLeft=pLeft->pPrior);
     pEList = pLeft->pEList;
@@ -3639,20 +3656,9 @@ static int withExpand(
       }
       pEList = pCte->pCols;
     }
-
     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 );
-      }
-    }
-
+    if( pSel->selFlags & SF_Recursive ) sqlite3WalkSelect(pWalker, pSel);
     ctePop(pParse, pCte);
   }
 
@@ -3715,6 +3721,8 @@ static int selectExpander(Walker *pWalker, Select *p){
   */
   for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){
     Table *pTab;
+    assert( pFrom->isRecursive==0 || pFrom->pTab );
+    if( pFrom->isRecursive ) continue;
     if( pFrom->pTab!=0 ){
       /* This statement has already been prepared.  There is no need
       ** to go further. */
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 733dad2d8..43a1a57b0 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -2131,7 +2131,6 @@ 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 */
@@ -2165,6 +2164,7 @@ struct Select {
 #define SF_Materialize     0x0100  /* Force materialization of views */
 #define SF_NestedFrom      0x0200  /* Part of a parenthesized FROM clause */
 #define SF_MaybeConvert    0x0400  /* Need convertCompoundSelectToSubquery() */
+#define SF_Recursive       0x0800  /* The recursive part of a recursive CTE */
 
 
 /*
@@ -2640,7 +2640,7 @@ int sqlite3WalkSelectFrom(Walker*, Select*);
 #define WRC_Abort       2   /* Abandon the tree walk */
 
 /*
-** An instance of this structure represents a set of on or more CTEs
+** An instance of this structure represents a set of one or more CTEs
 ** (common table expressions) created by a single WITH clause.
 */
 struct With {
@@ -2651,7 +2651,6 @@ struct With {
     ExprList *pCols;                /* List of explicit column names, or NULL */
     Select *pSelect;                /* The definition of this CTE */
     struct Cte *pOuterCte;          /* Next WITH clause in outer context */
-    Table *pTab;                    /* Table object for this CTE */
   } a[1];
 };
 
diff --git a/src/vdbe.c b/src/vdbe.c
index 301707677..9af4a62d7 100644
--- a/src/vdbe.c
+++ b/src/vdbe.c
@@ -3370,29 +3370,6 @@ case OP_OpenEphemeral: {
 }
 
 #ifndef SQLITE_OMIT_CTE
-/* 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
diff --git a/src/where.c b/src/where.c
index f1cf29b2e..52bf46a74 100644
--- a/src/where.c
+++ b/src/where.c
@@ -5654,13 +5654,7 @@ WhereInfo *sqlite3WhereBegin(
     iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
     pLoop = pLevel->pWLoop;
     if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){
-#ifndef SQLITE_OMIT_CTE
-      if( pTab->tabFlags & TF_Recursive ){
-        int iCur = pTabItem->iCursor;
-        sqlite3VdbeAddOp2(v, OP_OpenEphreader, iCur, pTab->tnum);
-      }
-#endif
-      /* Otherwise do nothing */
+      /* Do nothing */
     }else
 #ifndef SQLITE_OMIT_VIRTUALTABLE
     if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 ){