/ Check-in [088009ef]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Fix a bug in CTE handling discovered by LibFuzzer that can cause an infinite loop in the query planner.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 088009efdd56160bb4eee0fbd829a529b141274e
User & Date: dan 2015-11-07 18:07:15
Context
2015-11-07
18:32
Enhance the sqldiff utility to deal gracefully with ALTER TABLE ADD COLUMN. check-in: 7ea036ac user: drh tags: trunk
18:07
Fix a bug in CTE handling discovered by LibFuzzer that can cause an infinite loop in the query planner. check-in: 088009ef user: dan tags: trunk
17:51
Add test cases for WITH clauses. Closed-Leaf check-in: e7e65c75 user: dan tags: infinite-with-loop-bug
01:19
The OPFLAG_SEEKEQ optimization is only applicable to equality comparisons against an index, not against a rowid table. check-in: 0f5b147d user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/select.c.

  3968   3968   ** then return a pointer to the CTE definition for that table. Otherwise
  3969   3969   ** return NULL.
  3970   3970   **
  3971   3971   ** If a non-NULL value is returned, set *ppContext to point to the With
  3972   3972   ** object that the returned CTE belongs to.
  3973   3973   */
  3974   3974   static struct Cte *searchWith(
  3975         -  With *pWith,                    /* Current outermost WITH clause */
         3975  +  With *pWith,                    /* Current innermost WITH clause */
  3976   3976     struct SrcList_item *pItem,     /* FROM clause element to resolve */
  3977   3977     With **ppContext                /* OUT: WITH clause return value belongs to */
  3978   3978   ){
  3979   3979     const char *zName;
  3980   3980     if( pItem->zDatabase==0 && (zName = pItem->zName)!=0 ){
  3981   3981       With *p;
  3982   3982       for(p=pWith; p; p=p->pOuter){
................................................................................
  3999   3999   ** onto the top of the stack. If argument bFree is true, then this
  4000   4000   ** WITH clause will never be popped from the stack. In this case it
  4001   4001   ** should be freed along with the Parse object. In other cases, when
  4002   4002   ** bFree==0, the With object will be freed along with the SELECT 
  4003   4003   ** statement with which it is associated.
  4004   4004   */
  4005   4005   void sqlite3WithPush(Parse *pParse, With *pWith, u8 bFree){
  4006         -  assert( bFree==0 || pParse->pWith==0 );
         4006  +  assert( bFree==0 || (pParse->pWith==0 && pParse->pWithToFree==0) );
  4007   4007     if( pWith ){
         4008  +    assert( pParse->pWith!=pWith );
  4008   4009       pWith->pOuter = pParse->pWith;
  4009   4010       pParse->pWith = pWith;
  4010         -    pParse->bFreeWith = bFree;
         4011  +    if( bFree ) pParse->pWithToFree = pWith;
  4011   4012     }
  4012   4013   }
  4013   4014   
  4014   4015   /*
  4015   4016   ** This function checks if argument pFrom refers to a CTE declared by 
  4016   4017   ** a WITH clause on the stack currently maintained by the parser. And,
  4017   4018   ** if currently processing a CTE expression, if it is a recursive
................................................................................
  4096   4097       }
  4097   4098       assert( pTab->nRef==1 || ((pSel->selFlags&SF_Recursive) && pTab->nRef==2 ));
  4098   4099   
  4099   4100       pCte->zCteErr = "circular reference: %s";
  4100   4101       pSavedWith = pParse->pWith;
  4101   4102       pParse->pWith = pWith;
  4102   4103       sqlite3WalkSelect(pWalker, bMayRecursive ? pSel->pPrior : pSel);
         4104  +    pParse->pWith = pWith;
  4103   4105   
  4104   4106       for(pLeft=pSel; pLeft->pPrior; pLeft=pLeft->pPrior);
  4105   4107       pEList = pLeft->pEList;
  4106   4108       if( pCte->pCols ){
  4107   4109         if( pEList && pEList->nExpr!=pCte->pCols->nExpr ){
  4108   4110           sqlite3ErrorMsg(pParse, "table %s has %d values for %d columns",
  4109   4111               pCte->zName, pEList->nExpr, pCte->pCols->nExpr

Changes to src/sqliteInt.h.

  2750   2750     ** using offsetof(Parse,nVar) so the nVar field must be the first field
  2751   2751     ** in the recursive region.
  2752   2752     ************************************************************************/
  2753   2753   
  2754   2754     int nVar;                 /* Number of '?' variables seen in the SQL so far */
  2755   2755     int nzVar;                /* Number of available slots in azVar[] */
  2756   2756     u8 iPkSortOrder;          /* ASC or DESC for INTEGER PRIMARY KEY */
  2757         -  u8 bFreeWith;             /* True if pWith should be freed with parser */
  2758   2757     u8 explain;               /* True if the EXPLAIN flag is found on the query */
  2759   2758   #ifndef SQLITE_OMIT_VIRTUALTABLE
  2760   2759     u8 declareVtab;           /* True if inside sqlite3_declare_vtab() */
  2761   2760     int nVtabLock;            /* Number of virtual tables to lock */
  2762   2761   #endif
  2763   2762     int nAlias;               /* Number of aliased result set columns */
  2764   2763     int nHeight;              /* Expression tree height of current sub-select */
................................................................................
  2777   2776   #ifndef SQLITE_OMIT_VIRTUALTABLE
  2778   2777     Token sArg;               /* Complete text of a module argument */
  2779   2778     Table **apVtabLock;       /* Pointer to virtual tables needing locking */
  2780   2779   #endif
  2781   2780     Table *pZombieTab;        /* List of Table objects to delete after code gen */
  2782   2781     TriggerPrg *pTriggerPrg;  /* Linked list of coded triggers */
  2783   2782     With *pWith;              /* Current WITH clause, or NULL */
         2783  +  With *pWithToFree;        /* Free this WITH object at the end of the parse */
  2784   2784   };
  2785   2785   
  2786   2786   /*
  2787   2787   ** Return true if currently inside an sqlite3_declare_vtab() call.
  2788   2788   */
  2789   2789   #ifdef SQLITE_OMIT_VIRTUALTABLE
  2790   2790     #define IN_DECLARE_VTAB 0
................................................................................
  3267   3267     void *sqlite3TestTextToPtr(const char*);
  3268   3268   #endif
  3269   3269   
  3270   3270   #if defined(SQLITE_DEBUG)
  3271   3271     void sqlite3TreeViewExpr(TreeView*, const Expr*, u8);
  3272   3272     void sqlite3TreeViewExprList(TreeView*, const ExprList*, u8, const char*);
  3273   3273     void sqlite3TreeViewSelect(TreeView*, const Select*, u8);
         3274  +  void sqlite3TreeViewWith(TreeView*, const With*, u8);
  3274   3275   #endif
  3275   3276   
  3276   3277   
  3277   3278   void sqlite3SetString(char **, sqlite3*, const char*);
  3278   3279   void sqlite3ErrorMsg(Parse*, const char*, ...);
  3279   3280   int sqlite3Dequote(char*);
  3280   3281   int sqlite3KeywordCode(const unsigned char*, int);

Changes to src/tokenize.c.

   506    506       /* If the pParse->declareVtab flag is set, do not delete any table 
   507    507       ** structure built up in pParse->pNewTable. The calling code (see vtab.c)
   508    508       ** will take responsibility for freeing the Table structure.
   509    509       */
   510    510       sqlite3DeleteTable(db, pParse->pNewTable);
   511    511     }
   512    512   
   513         -  if( pParse->bFreeWith ) sqlite3WithDelete(db, pParse->pWith);
          513  +  sqlite3WithDelete(db, pParse->pWithToFree);
   514    514     sqlite3DeleteTrigger(db, pParse->pNewTrigger);
   515    515     for(i=pParse->nzVar-1; i>=0; i--) sqlite3DbFree(db, pParse->azVar[i]);
   516    516     sqlite3DbFree(db, pParse->azVar);
   517    517     while( pParse->pAinc ){
   518    518       AutoincInfo *p = pParse->pAinc;
   519    519       pParse->pAinc = p->pNext;
   520    520       sqlite3DbFree(db, p);

Changes to src/treeview.c.

    75     75   ** Shorthand for starting a new tree item that consists of a single label
    76     76   */
    77     77   static void sqlite3TreeViewItem(TreeView *p, const char *zLabel,u8 moreFollows){
    78     78     p = sqlite3TreeViewPush(p, moreFollows);
    79     79     sqlite3TreeViewLine(p, "%s", zLabel);
    80     80   }
    81     81   
           82  +/*
           83  +** Generate a human-readable description of a WITH clause.
           84  +*/
           85  +void sqlite3TreeViewWith(TreeView *pView, const With *pWith, u8 moreToFollow){
           86  +  int i;
           87  +  if( pWith==0 ) return;
           88  +  if( pWith->nCte==0 ) return;
           89  +  if( pWith->pOuter ){
           90  +    sqlite3TreeViewLine(pView, "WITH (0x%p, pOuter=0x%p)",pWith,pWith->pOuter);
           91  +  }else{
           92  +    sqlite3TreeViewLine(pView, "WITH (0x%p)", pWith);
           93  +  }
           94  +  if( pWith->nCte>0 ){
           95  +    pView = sqlite3TreeViewPush(pView, 1);
           96  +    for(i=0; i<pWith->nCte; i++){
           97  +      StrAccum x;
           98  +      char zLine[1000];
           99  +      const struct Cte *pCte = &pWith->a[i];
          100  +      sqlite3StrAccumInit(&x, 0, zLine, sizeof(zLine), 0);
          101  +      sqlite3XPrintf(&x, 0, "%s", pCte->zName);
          102  +      if( pCte->pCols && pCte->pCols->nExpr>0 ){
          103  +        char cSep = '(';
          104  +        int j;
          105  +        for(j=0; j<pCte->pCols->nExpr; j++){
          106  +          sqlite3XPrintf(&x, 0, "%c%s", cSep, pCte->pCols->a[j].zName);
          107  +          cSep = ',';
          108  +        }
          109  +        sqlite3XPrintf(&x, 0, ")");
          110  +      }
          111  +      sqlite3XPrintf(&x, 0, " AS");
          112  +      sqlite3StrAccumFinish(&x);
          113  +      sqlite3TreeViewItem(pView, zLine, i<pWith->nCte-1);
          114  +      sqlite3TreeViewSelect(pView, pCte->pSelect, 0);
          115  +      sqlite3TreeViewPop(pView);
          116  +    }
          117  +    sqlite3TreeViewPop(pView);
          118  +  }
          119  +}
          120  +
    82    121   
    83    122   /*
    84    123   ** Generate a human-readable description of a the Select object.
    85    124   */
    86    125   void sqlite3TreeViewSelect(TreeView *pView, const Select *p, u8 moreToFollow){
    87    126     int n = 0;
    88    127     int cnt = 0;
    89    128     pView = sqlite3TreeViewPush(pView, moreToFollow);
          129  +  if( p->pWith ){
          130  +    sqlite3TreeViewWith(pView, p->pWith, 1);
          131  +    cnt = 1;
          132  +    sqlite3TreeViewPush(pView, 1);
          133  +  }
    90    134     do{
    91    135       sqlite3TreeViewLine(pView, "SELECT%s%s (0x%p) selFlags=0x%x",
    92    136         ((p->selFlags & SF_Distinct) ? " DISTINCT" : ""),
    93    137         ((p->selFlags & SF_Aggregate) ? " agg_flag" : ""), p, p->selFlags
    94    138       );
    95    139       if( cnt++ ) sqlite3TreeViewPop(pView);
    96    140       if( p->pPrior ){

Changes to test/with1.test.

   860    860   # 2015-07-05:  Do not allow aggregate recursive queries
   861    861   #
   862    862   do_catchsql_test 16.1 {
   863    863     WITH RECURSIVE
   864    864       i(x) AS (VALUES(1) UNION SELECT count(*) FROM i)
   865    865     SELECT * FROM i;
   866    866   } {1 {recursive aggregate queries not supported}}
          867  +
          868  +#-------------------------------------------------------------------------
          869  +do_execsql_test 17.1 {
          870  +  WITH x(a) AS (
          871  +    WITH y(b) AS (SELECT 10)
          872  +    SELECT 9 UNION ALL SELECT * FROM y
          873  +  )
          874  +  SELECT * FROM x
          875  +} {9 10}
          876  +
          877  +do_execsql_test 17.2 {
          878  +  WITH x AS (
          879  +    WITH y(b) AS (SELECT 10)
          880  +    SELECT * FROM y UNION ALL SELECT * FROM y
          881  +  )
          882  +  SELECT * FROM x
          883  +} {10 10}
          884  +
          885  +do_test 17.2 {
          886  +  db eval {
          887  +    WITH x AS (
          888  +        WITH y(b) AS (SELECT 10)
          889  +        SELECT * FROM y UNION ALL SELECT * FROM y
          890  +    )
          891  +    SELECT * FROM x
          892  +  } A {
          893  +    # no op
          894  +  }
          895  +  set A(*)
          896  +} {b}
          897  +
          898  +do_catchsql_test 17.3 {
          899  +  WITH i AS (
          900  +    WITH j AS (SELECT 5)
          901  +    SELECT 5 FROM i UNION SELECT 8 FROM i
          902  +  )
          903  +  SELECT * FROM i;
          904  +} {1 {circular reference: i}}
          905  +
          906  +do_catchsql_test 17.4 {
          907  +  WITH i AS (
          908  +    WITH j AS (SELECT 5)
          909  +    SELECT 5 FROM t1 UNION SELECT 8 FROM t11
          910  +  )
          911  +  SELECT * FROM i;
          912  +} {1 {no such table: t11}}
          913  +
          914  +do_execsql_test 17.5 {
          915  +  WITH 
          916  +  x1 AS (SELECT 10),
          917  +  x2 AS (SELECT * FROM x1),
          918  +  x3 AS (
          919  +    WITH x1 AS (SELECT 11)
          920  +    SELECT * FROM x2 UNION ALL SELECT * FROM x2
          921  +  )
          922  +  SELECT * FROM x3;
          923  +} {10 10}
          924  +
          925  +do_execsql_test 17.6 {
          926  +  WITH 
          927  +  x1 AS (SELECT 10),
          928  +  x2 AS (SELECT * FROM x1),
          929  +  x3 AS (
          930  +    WITH x1 AS (SELECT 11)
          931  +    SELECT * FROM x2 UNION ALL SELECT * FROM x1
          932  +  )
          933  +  SELECT * FROM x3;
          934  +} {10 11}
          935  +
          936  +do_execsql_test 17.7 {
          937  +  WITH 
          938  +  x1 AS (SELECT 10),
          939  +  x2 AS (SELECT * FROM x1),
          940  +  x3 AS (
          941  +    WITH 
          942  +      x1 AS ( SELECT 11 ),
          943  +      x4 AS ( SELECT * FROM x2 )
          944  +    SELECT * FROM x4 UNION ALL SELECT * FROM x1
          945  +  )
          946  +  SELECT * FROM x3;
          947  +} {10 11}
          948  +
          949  +do_execsql_test 17.8 {
          950  +  WITH 
          951  +  x1 AS (SELECT 10),
          952  +  x2 AS (SELECT * FROM x1),
          953  +  x3 AS (
          954  +    WITH 
          955  +      x1 AS ( SELECT 11 ),
          956  +      x4 AS ( SELECT * FROM x2 )
          957  +    SELECT * FROM x4 UNION ALL SELECT * FROM x1
          958  +  )
          959  +  SELECT * FROM x3;
          960  +} {10 11}
          961  +
          962  +do_execsql_test 17.9 {
          963  +  WITH 
          964  +  x1 AS (SELECT 10),
          965  +  x2 AS (SELECT 11),
          966  +  x3 AS (
          967  +    SELECT * FROM x1 UNION ALL SELECT * FROM x2
          968  +  ),
          969  +  x4 AS (
          970  +    WITH 
          971  +    x1 AS (SELECT 12),
          972  +    x2 AS (SELECT 13)
          973  +    SELECT * FROM x3
          974  +  )
          975  +  SELECT * FROM x4;
          976  +} {10 11}
   867    977   
   868    978   finish_test

Added test/with3.test.

            1  +# 2015-11-07
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +# This file implements regression tests for SQLite library.  The
           12  +# focus of this file is testing the WITH clause.
           13  +#
           14  +
           15  +set testdir [file dirname $argv0]
           16  +source $testdir/tester.tcl
           17  +set ::testprefix with3
           18  +
           19  +ifcapable {!cte} {
           20  +  finish_test
           21  +  return
           22  +}
           23  +
           24  +# Test problems found by Kostya Serebryany using 
           25  +# LibFuzzer.  (http://llvm.org/docs/LibFuzzer.html)
           26  +#
           27  +do_catchsql_test 1.0 {
           28  +  WITH i(x) AS (
           29  +    WITH j AS (SELECT 10)
           30  +    SELECT 5 FROM t0 UNION SELECT 8 FROM m
           31  +  )
           32  +  SELECT * FROM i;
           33  +} {1 {no such table: m}}
           34  +
           35  +# Additional test cases that came out of the work to
           36  +# fix for Kostya's problem.
           37  +#
           38  +do_execsql_test 2.0 {
           39  + WITH
           40  +  x1 AS (SELECT 10),
           41  +  x2 AS (SELECT 11),
           42  +  x3 AS (
           43  +    SELECT * FROM x1 UNION ALL SELECT * FROM x2
           44  +  ),
           45  +  x4 AS (
           46  +    WITH
           47  +    x1 AS (SELECT 12),
           48  +    x2 AS (SELECT 13)
           49  +    SELECT * FROM x3
           50  +  )
           51  +  SELECT * FROM x4;
           52  +
           53  +} {10 11}
           54  +
           55  +do_execsql_test 2.1 {
           56  +  CREATE TABLE t1(x);
           57  +  WITH
           58  +    x1(a) AS (values(100))
           59  +  INSERT INTO t1(x)
           60  +    SELECT * FROM (WITH x2(y) AS (SELECT * FROM x1) SELECT y+a FROM x1, x2);
           61  +  SELECT * FROM t1;
           62  +} {200}
           63  +
           64  +finish_test