Fix a bug in CTE handling discovered by LibFuzzer that can cause an infinite loop in the query planner.

FossilOrigin-Name: 088009efdd56160bb4eee0fbd829a529b141274e

8 files changed, 240 insertions, 17 deletions

diff --git a/manifest b/manifest
index 782863019..b2a16a739 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C The\sOPFLAG_SEEKEQ\soptimization\sis\sonly\sapplicable\sto\sequality\scomparisons\nagainst\san\sindex,\snot\sagainst\sa\srowid\stable.
-D 2015-11-07T01:19:00.997
+C Fix\sa\sbug\sin\sCTE\shandling\sdiscovered\sby\sLibFuzzer\sthat\scan\scause\san\sinfinite\sloop\sin\sthe\squery\splanner.
+D 2015-11-07T18:07:15.260
 F Makefile.in 3a705bb4bd12e194212ddbdbf068310d17153cdb
 F Makefile.linux-gcc 7bc79876b875010e8c8f9502eb935ca92aa3c434
 F Makefile.msc 702d3e98f3afc6587a78481257f3c4c900efc3a4
@@ -340,12 +340,12 @@ F src/printf.c 0c4bcdd1c2e2521024f0a69cb5eb334f86b3652a
 F src/random.c ba2679f80ec82c4190062d756f22d0c358180696
 F src/resolve.c 1954a0f01bf65d78d7d559aea3d5c67f33376d91
 F src/rowset.c eccf6af6d620aaa4579bd3b72c1b6395d9e9fa1e
-F src/select.c 167b4e9058bc8e997d18d6b6b20ecbb0c9c457af
+F src/select.c 00a2a10d4298a685d0eeb05b09ef018a2bd81bf8
 F src/shell.c d25df04168d6ba5a4fa05bdbf859df667f9eb621
 F src/sqlite.h.in 3cfc86c55e57c63d86b9e1e92869e2bfb162ca8e
 F src/sqlite3.rc 992c9f5fb8285ae285d6be28240a7e8d3a7f2bad
 F src/sqlite3ext.h 4b66e3e3435da4b4c8c83696d0349f0c503b3924
-F src/sqliteInt.h 12ff325b433c4ded39995b74b01b78aacc19805a
+F src/sqliteInt.h bc6d24460fe544323517630b1e20539146379077
 F src/sqliteLimit.h 216557999cb45f2e3578ed53ebefe228d779cb46
 F src/status.c 70912d7be68e9e2dbc4010c93d344af61d4c59ba
 F src/table.c 51b46b2a62d1b3a959633d593b89bab5e2c9155e
@@ -396,8 +396,8 @@ F src/test_vfs.c 3b65d42e18b262805716bd96178c81da8f2d9283
 F src/test_vfstrace.c bab9594adc976cbe696ff3970728830b4c5ed698
 F src/test_wsd.c 41cadfd9d97fe8e3e4e44f61a4a8ccd6f7ca8fe9
 F src/threads.c bbfb74450643cb5372a43ad4f6cffd7e9dfcecb0
-F src/tokenize.c 338bc8f7c9dd103188952cda7964696bacac6d22
-F src/treeview.c 154f0acc622fa3514de8777dcedf4c8a8802b4ce
+F src/tokenize.c b05b63e224a12531813efda3bcc73e9438958745
+F src/treeview.c 78842e90c1f71269e7a73a1d4221b6fe360bab66
 F src/trigger.c 322f23aad694e8f31d384dcfa386d52a48d3c52f
 F src/update.c 40e51cd0883cb5bfd6abb7d8a7cd8aa47fab2945
 F src/utf.c fc6b889ba0779b7722634cdeaa25f1930d93820c
@@ -1329,8 +1329,9 @@ F test/wild001.test bca33f499866f04c24510d74baf1e578d4e44b1c
 F test/win32heap.test ea19770974795cff26e11575e12d422dbd16893c
 F test/win32lock.test fbf107c91d8f5512be5a5b87c4c42ab9fdd54972
 F test/win32longpath.test 169c75a3b2e43481f4a62122510210c67b08f26d
-F test/with1.test a1e8660be88e2eb4648f8860f831d1e38b5b5443
+F test/with1.test 05c8fc7f809f178a8a0519f02c21fe430948c895
 F test/with2.test 2b40da883658eb74ad8ad06afabe11a408e7fb87
+F test/with3.test 511bacdbe41c49cf34f9fd1bd3245fe1575bca98
 F test/withM.test e97f2a8c506ab3ea9eab94e6f6072f6cc924c991
 F test/without_rowid1.test 1a7b9bd51b899928d327052df9741d2fe8dbe701
 F test/without_rowid2.test af260339f79d13cb220288b67cd287fbcf81ad99
@@ -1400,7 +1401,8 @@ F tool/vdbe_profile.tcl 246d0da094856d72d2c12efec03250d71639d19f
 F tool/warnings-clang.sh f6aa929dc20ef1f856af04a730772f59283631d4
 F tool/warnings.sh 48bd54594752d5be3337f12c72f28d2080cb630b
 F tool/win/sqlite.vsix deb315d026cc8400325c5863eef847784a219a2f
-P dd9a26ecdeaef7b0b9cbf4ff70448ab13a276b4e
-R 37fd8f25666e5cc61c467cdb94b7bb71
-U drh
-Z b3bf4f06c783a2156de71d3cb1963976
+P 0f5b147d1fe83c34d0fbeacc7422be94d8441bc1 e7e65c7559ed43e7065adc2ec1bd242bf187b7c3
+R 0a66e1cb90e0f88ea5b94da656f84e5f
+T +closed e7e65c7559ed43e7065adc2ec1bd242bf187b7c3
+U dan
+Z 97f5561994d709cf0287df4980640bc9
diff --git a/manifest.uuid b/manifest.uuid
index f7a057f39..576eda30a 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-0f5b147d1fe83c34d0fbeacc7422be94d8441bc1
\ No newline at end of file
+088009efdd56160bb4eee0fbd829a529b141274e
\ No newline at end of file
diff --git a/src/select.c b/src/select.c
index 8db983891..bd732e5bc 100644
--- a/src/select.c
+++ b/src/select.c
@@ -3972,7 +3972,7 @@ static int convertCompoundSelectToSubquery(Walker *pWalker, Select *p){
 ** object that the returned CTE belongs to.
 */
 static struct Cte *searchWith(
-  With *pWith,                    /* Current outermost WITH clause */
+  With *pWith,                    /* Current innermost WITH clause */
   struct SrcList_item *pItem,     /* FROM clause element to resolve */
   With **ppContext                /* OUT: WITH clause return value belongs to */
 ){
@@ -4003,11 +4003,12 @@ static struct Cte *searchWith(
 ** statement with which it is associated.
 */
 void sqlite3WithPush(Parse *pParse, With *pWith, u8 bFree){
-  assert( bFree==0 || pParse->pWith==0 );
+  assert( bFree==0 || (pParse->pWith==0 && pParse->pWithToFree==0) );
   if( pWith ){
+    assert( pParse->pWith!=pWith );
     pWith->pOuter = pParse->pWith;
     pParse->pWith = pWith;
-    pParse->bFreeWith = bFree;
+    if( bFree ) pParse->pWithToFree = pWith;
   }
 }
 
@@ -4100,6 +4101,7 @@ static int withExpand(
     pSavedWith = pParse->pWith;
     pParse->pWith = pWith;
     sqlite3WalkSelect(pWalker, bMayRecursive ? pSel->pPrior : pSel);
+    pParse->pWith = pWith;
 
     for(pLeft=pSel; pLeft->pPrior; pLeft=pLeft->pPrior);
     pEList = pLeft->pEList;
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 2b9ece78e..c65e0f205 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -2754,7 +2754,6 @@ struct Parse {
   int nVar;                 /* Number of '?' variables seen in the SQL so far */
   int nzVar;                /* Number of available slots in azVar[] */
   u8 iPkSortOrder;          /* ASC or DESC for INTEGER PRIMARY KEY */
-  u8 bFreeWith;             /* True if pWith should be freed with parser */
   u8 explain;               /* True if the EXPLAIN flag is found on the query */
 #ifndef SQLITE_OMIT_VIRTUALTABLE
   u8 declareVtab;           /* True if inside sqlite3_declare_vtab() */
@@ -2781,6 +2780,7 @@ struct Parse {
   Table *pZombieTab;        /* List of Table objects to delete after code gen */
   TriggerPrg *pTriggerPrg;  /* Linked list of coded triggers */
   With *pWith;              /* Current WITH clause, or NULL */
+  With *pWithToFree;        /* Free this WITH object at the end of the parse */
 };
 
 /*
@@ -3271,6 +3271,7 @@ char *sqlite3VMPrintf(sqlite3*,const char*, va_list);
   void sqlite3TreeViewExpr(TreeView*, const Expr*, u8);
   void sqlite3TreeViewExprList(TreeView*, const ExprList*, u8, const char*);
   void sqlite3TreeViewSelect(TreeView*, const Select*, u8);
+  void sqlite3TreeViewWith(TreeView*, const With*, u8);
 #endif
 
 
diff --git a/src/tokenize.c b/src/tokenize.c
index 9c1403bb2..f2b63b5cf 100644
--- a/src/tokenize.c
+++ b/src/tokenize.c
@@ -510,7 +510,7 @@ abort_parse:
     sqlite3DeleteTable(db, pParse->pNewTable);
   }
 
-  if( pParse->bFreeWith ) sqlite3WithDelete(db, pParse->pWith);
+  sqlite3WithDelete(db, pParse->pWithToFree);
   sqlite3DeleteTrigger(db, pParse->pNewTrigger);
   for(i=pParse->nzVar-1; i>=0; i--) sqlite3DbFree(db, pParse->azVar[i]);
   sqlite3DbFree(db, pParse->azVar);
diff --git a/src/treeview.c b/src/treeview.c
index 971de4e8b..a26e9e2b9 100644
--- a/src/treeview.c
+++ b/src/treeview.c
@@ -79,6 +79,45 @@ static void sqlite3TreeViewItem(TreeView *p, const char *zLabel,u8 moreFollows){
   sqlite3TreeViewLine(p, "%s", zLabel);
 }
 
+/*
+** Generate a human-readable description of a WITH clause.
+*/
+void sqlite3TreeViewWith(TreeView *pView, const With *pWith, u8 moreToFollow){
+  int i;
+  if( pWith==0 ) return;
+  if( pWith->nCte==0 ) return;
+  if( pWith->pOuter ){
+    sqlite3TreeViewLine(pView, "WITH (0x%p, pOuter=0x%p)",pWith,pWith->pOuter);
+  }else{
+    sqlite3TreeViewLine(pView, "WITH (0x%p)", pWith);
+  }
+  if( pWith->nCte>0 ){
+    pView = sqlite3TreeViewPush(pView, 1);
+    for(i=0; i<pWith->nCte; i++){
+      StrAccum x;
+      char zLine[1000];
+      const struct Cte *pCte = &pWith->a[i];
+      sqlite3StrAccumInit(&x, 0, zLine, sizeof(zLine), 0);
+      sqlite3XPrintf(&x, 0, "%s", pCte->zName);
+      if( pCte->pCols && pCte->pCols->nExpr>0 ){
+        char cSep = '(';
+        int j;
+        for(j=0; j<pCte->pCols->nExpr; j++){
+          sqlite3XPrintf(&x, 0, "%c%s", cSep, pCte->pCols->a[j].zName);
+          cSep = ',';
+        }
+        sqlite3XPrintf(&x, 0, ")");
+      }
+      sqlite3XPrintf(&x, 0, " AS");
+      sqlite3StrAccumFinish(&x);
+      sqlite3TreeViewItem(pView, zLine, i<pWith->nCte-1);
+      sqlite3TreeViewSelect(pView, pCte->pSelect, 0);
+      sqlite3TreeViewPop(pView);
+    }
+    sqlite3TreeViewPop(pView);
+  }
+}
+
 
 /*
 ** Generate a human-readable description of a the Select object.
@@ -87,6 +126,11 @@ void sqlite3TreeViewSelect(TreeView *pView, const Select *p, u8 moreToFollow){
   int n = 0;
   int cnt = 0;
   pView = sqlite3TreeViewPush(pView, moreToFollow);
+  if( p->pWith ){
+    sqlite3TreeViewWith(pView, p->pWith, 1);
+    cnt = 1;
+    sqlite3TreeViewPush(pView, 1);
+  }
   do{
     sqlite3TreeViewLine(pView, "SELECT%s%s (0x%p) selFlags=0x%x",
       ((p->selFlags & SF_Distinct) ? " DISTINCT" : ""),
diff --git a/test/with1.test b/test/with1.test
index 71eec61e7..d98f33dfb 100644
--- a/test/with1.test
+++ b/test/with1.test
@@ -865,4 +865,114 @@ do_catchsql_test 16.1 {
   SELECT * FROM i;
 } {1 {recursive aggregate queries not supported}}
 
+#-------------------------------------------------------------------------
+do_execsql_test 17.1 {
+  WITH x(a) AS (
+    WITH y(b) AS (SELECT 10)
+    SELECT 9 UNION ALL SELECT * FROM y
+  )
+  SELECT * FROM x
+} {9 10}
+
+do_execsql_test 17.2 {
+  WITH x AS (
+    WITH y(b) AS (SELECT 10)
+    SELECT * FROM y UNION ALL SELECT * FROM y
+  )
+  SELECT * FROM x
+} {10 10}
+
+do_test 17.2 {
+  db eval {
+    WITH x AS (
+        WITH y(b) AS (SELECT 10)
+        SELECT * FROM y UNION ALL SELECT * FROM y
+    )
+    SELECT * FROM x
+  } A {
+    # no op
+  }
+  set A(*)
+} {b}
+
+do_catchsql_test 17.3 {
+  WITH i AS (
+    WITH j AS (SELECT 5)
+    SELECT 5 FROM i UNION SELECT 8 FROM i
+  )
+  SELECT * FROM i;
+} {1 {circular reference: i}}
+
+do_catchsql_test 17.4 {
+  WITH i AS (
+    WITH j AS (SELECT 5)
+    SELECT 5 FROM t1 UNION SELECT 8 FROM t11
+  )
+  SELECT * FROM i;
+} {1 {no such table: t11}}
+
+do_execsql_test 17.5 {
+  WITH 
+  x1 AS (SELECT 10),
+  x2 AS (SELECT * FROM x1),
+  x3 AS (
+    WITH x1 AS (SELECT 11)
+    SELECT * FROM x2 UNION ALL SELECT * FROM x2
+  )
+  SELECT * FROM x3;
+} {10 10}
+
+do_execsql_test 17.6 {
+  WITH 
+  x1 AS (SELECT 10),
+  x2 AS (SELECT * FROM x1),
+  x3 AS (
+    WITH x1 AS (SELECT 11)
+    SELECT * FROM x2 UNION ALL SELECT * FROM x1
+  )
+  SELECT * FROM x3;
+} {10 11}
+
+do_execsql_test 17.7 {
+  WITH 
+  x1 AS (SELECT 10),
+  x2 AS (SELECT * FROM x1),
+  x3 AS (
+    WITH 
+      x1 AS ( SELECT 11 ),
+      x4 AS ( SELECT * FROM x2 )
+    SELECT * FROM x4 UNION ALL SELECT * FROM x1
+  )
+  SELECT * FROM x3;
+} {10 11}
+
+do_execsql_test 17.8 {
+  WITH 
+  x1 AS (SELECT 10),
+  x2 AS (SELECT * FROM x1),
+  x3 AS (
+    WITH 
+      x1 AS ( SELECT 11 ),
+      x4 AS ( SELECT * FROM x2 )
+    SELECT * FROM x4 UNION ALL SELECT * FROM x1
+  )
+  SELECT * FROM x3;
+} {10 11}
+
+do_execsql_test 17.9 {
+  WITH 
+  x1 AS (SELECT 10),
+  x2 AS (SELECT 11),
+  x3 AS (
+    SELECT * FROM x1 UNION ALL SELECT * FROM x2
+  ),
+  x4 AS (
+    WITH 
+    x1 AS (SELECT 12),
+    x2 AS (SELECT 13)
+    SELECT * FROM x3
+  )
+  SELECT * FROM x4;
+} {10 11}
+
 finish_test
diff --git a/test/with3.test b/test/with3.test
new file mode 100644
index 000000000..62e88441a
--- /dev/null
+++ b/test/with3.test
@@ -0,0 +1,64 @@
+# 2015-11-07
+#
+# 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.
+#
+#***********************************************************************
+# This file implements regression tests for SQLite library.  The
+# focus of this file is testing the WITH clause.
+#
+
+set testdir [file dirname $argv0]
+source $testdir/tester.tcl
+set ::testprefix with3
+
+ifcapable {!cte} {
+  finish_test
+  return
+}
+
+# Test problems found by Kostya Serebryany using 
+# LibFuzzer.  (http://llvm.org/docs/LibFuzzer.html)
+#
+do_catchsql_test 1.0 {
+  WITH i(x) AS (
+    WITH j AS (SELECT 10)
+    SELECT 5 FROM t0 UNION SELECT 8 FROM m
+  )
+  SELECT * FROM i;
+} {1 {no such table: m}}
+
+# Additional test cases that came out of the work to
+# fix for Kostya's problem.
+#
+do_execsql_test 2.0 {
+ WITH
+  x1 AS (SELECT 10),
+  x2 AS (SELECT 11),
+  x3 AS (
+    SELECT * FROM x1 UNION ALL SELECT * FROM x2
+  ),
+  x4 AS (
+    WITH
+    x1 AS (SELECT 12),
+    x2 AS (SELECT 13)
+    SELECT * FROM x3
+  )
+  SELECT * FROM x4;
+
+} {10 11}
+
+do_execsql_test 2.1 {
+  CREATE TABLE t1(x);
+  WITH
+    x1(a) AS (values(100))
+  INSERT INTO t1(x)
+    SELECT * FROM (WITH x2(y) AS (SELECT * FROM x1) SELECT y+a FROM x1, x2);
+  SELECT * FROM t1;
+} {200}
+
+finish_test