Merge the nested aggregate query enhancements into trunk.

FossilOrigin-Name: d4cd6017c9875947a05b1dc36538d4272fb18739

5 files changed, 115 insertions, 40 deletions

diff --git a/src/expr.c b/src/expr.c
index 790aa45f3..89172f94b 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -3123,9 +3123,12 @@ void sqlite3ExplainExpr(Vdbe *pOut, Expr *pExpr){
       }else{
         pFarg = pExpr->x.pList;
       }
-      sqlite3ExplainPrintf(pOut, "%sFUNCTION:%s(",
-                           op==TK_AGG_FUNCTION ? "AGG_" : "",
-                           pExpr->u.zToken);
+      if( op==TK_AGG_FUNCTION ){
+        sqlite3ExplainPrintf(pOut, "AGG_FUNCTION%d:%s(",
+                             pExpr->op2, pExpr->u.zToken);
+      }else{
+        sqlite3ExplainPrintf(pOut, "FUNCTION:%s(", pExpr->u.zToken);
+      }
       if( pFarg ){
         sqlite3ExplainExprList(pOut, pFarg);
       }
@@ -3816,38 +3819,60 @@ int sqlite3ExprListCompare(ExprList *pA, ExprList *pB){
 }
 
 /*
-** This is the expression callback for sqlite3FunctionUsesOtherSrc().
-**
-** Determine if an expression references any table other than one of the
-** tables in pWalker->u.pSrcList and abort if it does.
+** An instance of the following structure is used by the tree walker
+** to count references to table columns in the arguments of an 
+** aggregate function, in order to implement the
+** sqlite3FunctionThisSrc() routine.
+*/
+struct SrcCount {
+  SrcList *pSrc;   /* One particular FROM clause in a nested query */
+  int nThis;       /* Number of references to columns in pSrcList */
+  int nOther;      /* Number of references to columns in other FROM clauses */
+};
+
+/*
+** Count the number of references to columns.
 */
-static int exprUsesOtherSrc(Walker *pWalker, Expr *pExpr){
-  if( pExpr->op==TK_COLUMN || pExpr->op==TK_AGG_COLUMN ){
+static int exprSrcCount(Walker *pWalker, Expr *pExpr){
+  /* The NEVER() on the second term is because sqlite3FunctionUsesThisSrc()
+  ** is always called before sqlite3ExprAnalyzeAggregates() and so the
+  ** TK_COLUMNs have not yet been converted into TK_AGG_COLUMN.  If
+  ** sqlite3FunctionUsesThisSrc() is used differently in the future, the
+  ** NEVER() will need to be removed. */
+  if( pExpr->op==TK_COLUMN || NEVER(pExpr->op==TK_AGG_COLUMN) ){
     int i;
-    SrcList *pSrc = pWalker->u.pSrcList;
+    struct SrcCount *p = pWalker->u.pSrcCount;
+    SrcList *pSrc = p->pSrc;
     for(i=0; i<pSrc->nSrc; i++){
-      if( pExpr->iTable==pSrc->a[i].iCursor ) return WRC_Continue;
+      if( pExpr->iTable==pSrc->a[i].iCursor ) break;
+    }
+    if( i<pSrc->nSrc ){
+      p->nThis++;
+    }else{
+      p->nOther++;
     }
-    return WRC_Abort;
-  }else{
-    return WRC_Continue;
   }
+  return WRC_Continue;
 }
 
 /*
-** Determine if any of the arguments to the pExpr Function references
-** any SrcList other than pSrcList.  Return true if they do.  Return
-** false if pExpr has no argument or has only constant arguments or
-** only references tables named in pSrcList.
+** Determine if any of the arguments to the pExpr Function reference
+** pSrcList.  Return true if they do.  Also return true if the function
+** has no arguments or has only constant arguments.  Return false if pExpr
+** references columns but not columns of tables found in pSrcList.
 */
-static int sqlite3FunctionUsesOtherSrc(Expr *pExpr, SrcList *pSrcList){
+int sqlite3FunctionUsesThisSrc(Expr *pExpr, SrcList *pSrcList){
   Walker w;
+  struct SrcCount cnt;
   assert( pExpr->op==TK_AGG_FUNCTION );
   memset(&w, 0, sizeof(w));
-  w.xExprCallback = exprUsesOtherSrc;
-  w.u.pSrcList = pSrcList;
-  if( sqlite3WalkExprList(&w, pExpr->x.pList)!=WRC_Continue ) return 1;
-  return 0;
+  w.xExprCallback = exprSrcCount;
+  w.u.pSrcCount = &cnt;
+  cnt.pSrc = pSrcList;
+  cnt.nThis = 0;
+  cnt.nOther = 0;
+  sqlite3WalkExprList(&w, pExpr->x.pList);
+  return cnt.nThis>0 || cnt.nOther==0;
 }
 
 /*
@@ -3966,7 +3991,7 @@ static int analyzeAggregate(Walker *pWalker, Expr *pExpr){
     }
     case TK_AGG_FUNCTION: {
       if( (pNC->ncFlags & NC_InAggFunc)==0
-       && !sqlite3FunctionUsesOtherSrc(pExpr, pSrcList)
+       && pWalker->walkerDepth==pExpr->op2
       ){
         /* Check to see if pExpr is a duplicate of another aggregate 
         ** function that is already in the pAggInfo structure
diff --git a/src/resolve.c b/src/resolve.c
index a66f88fdc..b87d231ac 100644
--- a/src/resolve.c
+++ b/src/resolve.c
@@ -19,6 +19,29 @@
 #include <string.h>
 
 /*
+** Walk the expression tree pExpr and increase the aggregate function
+** depth (the Expr.op2 field) by N on every TK_AGG_FUNCTION node.
+** This needs to occur when copying a TK_AGG_FUNCTION node from an
+** outer query into an inner subquery.
+**
+** incrAggFunctionDepth(pExpr,n) is the main routine.  incrAggDepth(..)
+** is a helper function - a callback for the tree walker.
+*/
+static int incrAggDepth(Walker *pWalker, Expr *pExpr){
+  if( pExpr->op==TK_AGG_FUNCTION ) pExpr->op2 += pWalker->u.i;
+  return WRC_Continue;
+}
+static void incrAggFunctionDepth(Expr *pExpr, int N){
+  if( N>0 ){
+    Walker w;
+    memset(&w, 0, sizeof(w));
+    w.xExprCallback = incrAggDepth;
+    w.u.i = N;
+    sqlite3WalkExpr(&w, pExpr);
+  }
+}
+
+/*
 ** Turn the pExpr expression into an alias for the iCol-th column of the
 ** result set in pEList.
 **
@@ -44,13 +67,20 @@
 ** The result of random()%5 in the GROUP BY clause is probably different
 ** from the result in the result-set.  We might fix this someday.  Or
 ** then again, we might not...
+**
+** The nSubquery parameter specifies how many levels of subquery the
+** alias is removed from the original expression.  The usually value is
+** zero but it might be more if the alias is contained within a subquery
+** of the original expression.  The Expr.op2 field of TK_AGG_FUNCTION
+** structures must be increased by the nSubquery amount.
 */
 static void resolveAlias(
   Parse *pParse,         /* Parsing context */
   ExprList *pEList,      /* A result set */
   int iCol,              /* A column in the result set.  0..pEList->nExpr-1 */
   Expr *pExpr,           /* Transform this into an alias to the result set */
-  const char *zType      /* "GROUP" or "ORDER" or "" */
+  const char *zType,     /* "GROUP" or "ORDER" or "" */
+  int nSubquery          /* Number of subqueries that the label is moving */
 ){
   Expr *pOrig;           /* The iCol-th column of the result set */
   Expr *pDup;            /* Copy of pOrig */
@@ -63,6 +93,7 @@ static void resolveAlias(
   db = pParse->db;
   if( pOrig->op!=TK_COLUMN && zType[0]!='G' ){
     pDup = sqlite3ExprDup(db, pOrig, 0);
+    incrAggFunctionDepth(pDup, nSubquery);
     pDup = sqlite3PExpr(pParse, TK_AS, pDup, 0, 0);
     if( pDup==0 ) return;
     if( pEList->a[iCol].iAlias==0 ){
@@ -151,9 +182,10 @@ static int lookupName(
   NameContext *pNC,    /* The name context used to resolve the name */
   Expr *pExpr          /* Make this EXPR node point to the selected column */
 ){
-  int i, j;            /* Loop counters */
+  int i, j;                         /* Loop counters */
   int cnt = 0;                      /* Number of matching column names */
   int cntTab = 0;                   /* Number of matching table names */
+  int nSubquery = 0;                /* How many levels of subquery */
   sqlite3 *db = pParse->db;         /* The database connection */
   struct SrcList_item *pItem;       /* Use for looping over pSrcList items */
   struct SrcList_item *pMatch = 0;  /* The matching pSrcList item */
@@ -315,7 +347,7 @@ static int lookupName(
             sqlite3ErrorMsg(pParse, "misuse of aliased aggregate %s", zAs);
             return WRC_Abort;
           }
-          resolveAlias(pParse, pEList, j, pExpr, "");
+          resolveAlias(pParse, pEList, j, pExpr, "", nSubquery);
           cnt = 1;
           pMatch = 0;
           assert( zTab==0 && zDb==0 );
@@ -329,6 +361,7 @@ static int lookupName(
     */
     if( cnt==0 ){
       pNC = pNC->pNext;
+      nSubquery++;
     }
   }
 
@@ -568,13 +601,19 @@ static int resolveExprStep(Walker *pWalker, Expr *pExpr){
              nId, zId);
         pNC->nErr++;
       }
+      if( is_agg ) pNC->ncFlags &= ~NC_AllowAgg;
+      sqlite3WalkExprList(pWalker, pList);
       if( is_agg ){
+        NameContext *pNC2 = pNC;
         pExpr->op = TK_AGG_FUNCTION;
-        pNC->ncFlags |= NC_HasAgg;
+        pExpr->op2 = 0;
+        while( pNC2 && !sqlite3FunctionUsesThisSrc(pExpr, pNC2->pSrcList) ){
+          pExpr->op2++;
+          pNC2 = pNC2->pNext;
+        }
+        if( pNC2 ) pNC2->ncFlags |= NC_HasAgg;
+        pNC->ncFlags |= NC_AllowAgg;
       }
-      if( is_agg ) pNC->ncFlags &= ~NC_AllowAgg;
-      sqlite3WalkExprList(pWalker, pList);
-      if( is_agg ) pNC->ncFlags |= NC_AllowAgg;
       /* FIX ME:  Compute pExpr->affinity based on the expected return
       ** type of the function 
       */
@@ -853,7 +892,7 @@ int sqlite3ResolveOrderGroupBy(
         resolveOutOfRangeError(pParse, zType, i+1, pEList->nExpr);
         return 1;
       }
-      resolveAlias(pParse, pEList, pItem->iOrderByCol-1, pItem->pExpr, zType);
+      resolveAlias(pParse, pEList, pItem->iOrderByCol-1, pItem->pExpr, zType,0);
     }
   }
   return 0;
diff --git a/src/select.c b/src/select.c
index 491356acb..a4bb2d496 100644
--- a/src/select.c
+++ b/src/select.c
@@ -3149,7 +3149,7 @@ static Table *isSimpleCount(Select *p, AggInfo *pAggInfo){
 
   if( IsVirtual(pTab) ) return 0;
   if( pExpr->op!=TK_AGG_FUNCTION ) return 0;
-  if( pAggInfo->nFunc==0 ) return 0;
+  if( NEVER(pAggInfo->nFunc==0) ) return 0;
   if( (pAggInfo->aFunc[0].pFunc->flags&SQLITE_FUNC_COUNT)==0 ) return 0;
   if( pExpr->flags&EP_Distinct ) return 0;
 
@@ -3521,7 +3521,7 @@ static void sqlite3SelectAddTypeInfo(Parse *pParse, Select *pSelect){
 
 
 /*
-** This routine sets of a SELECT statement for processing.  The
+** This routine sets up a SELECT statement for processing.  The
 ** following is accomplished:
 **
 **     *  VDBE Cursor numbers are assigned to all FROM-clause terms.
@@ -3553,7 +3553,8 @@ void sqlite3SelectPrep(
 **
 ** The aggregate accumulator is a set of memory cells that hold
 ** intermediate results while calculating an aggregate.  This
-** routine simply stores NULLs in all of those memory cells.
+** routine generates code that stores NULLs in all of those memory
+** cells.
 */
 static void resetAccumulator(Parse *pParse, AggInfo *pAggInfo){
   Vdbe *v = pParse->pVdbe;
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index b3cdb2363..443eaa403 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -1690,8 +1690,9 @@ struct Expr {
   i16 iAgg;              /* Which entry in pAggInfo->aCol[] or ->aFunc[] */
   i16 iRightJoinTable;   /* If EP_FromJoin, the right table of the join */
   u8 flags2;             /* Second set of flags.  EP2_... */
-  u8 op2;                /* If a TK_REGISTER, the original value of Expr.op */
-                         /* If TK_COLUMN, the value of p5 for OP_Column */
+  u8 op2;                /* TK_REGISTER: original value of Expr.op
+                         ** TK_COLUMN: the value of p5 for OP_Column
+                         ** TK_AGG_FUNCTION: nesting depth */
   AggInfo *pAggInfo;     /* Used by TK_AGG_COLUMN and TK_AGG_FUNCTION */
   Table *pTab;           /* Table for TK_COLUMN expressions. */
 #if SQLITE_MAX_EXPR_DEPTH>0
@@ -2498,10 +2499,12 @@ struct Walker {
   int (*xExprCallback)(Walker*, Expr*);     /* Callback for expressions */
   int (*xSelectCallback)(Walker*,Select*);  /* Callback for SELECTs */
   Parse *pParse;                            /* Parser context.  */
+  int walkerDepth;                          /* Number of subqueries */
   union {                                   /* Extra data for callback */
     NameContext *pNC;                          /* Naming context */
     int i;                                     /* Integer value */
     SrcList *pSrcList;                         /* FROM clause */
+    struct SrcCount *pSrcCount;                /* Counting column references */
   } u;
 };
 
@@ -2835,6 +2838,7 @@ int sqlite3ExprCompare(Expr*, Expr*);
 int sqlite3ExprListCompare(ExprList*, ExprList*);
 void sqlite3ExprAnalyzeAggregates(NameContext*, Expr*);
 void sqlite3ExprAnalyzeAggList(NameContext*,ExprList*);
+int sqlite3FunctionUsesThisSrc(Expr*, SrcList*);
 Vdbe *sqlite3GetVdbe(Parse*);
 void sqlite3PrngSaveState(void);
 void sqlite3PrngRestoreState(void);
diff --git a/src/walker.c b/src/walker.c
index c95a9c169..eab96ea24 100644
--- a/src/walker.c
+++ b/src/walker.c
@@ -125,12 +125,18 @@ int sqlite3WalkSelect(Walker *pWalker, Select *p){
   int rc;
   if( p==0 || pWalker->xSelectCallback==0 ) return WRC_Continue;
   rc = WRC_Continue;
-  while( p  ){
+  pWalker->walkerDepth++;
+  while( p ){
     rc = pWalker->xSelectCallback(pWalker, p);
     if( rc ) break;
-    if( sqlite3WalkSelectExpr(pWalker, p) ) return WRC_Abort;
-    if( sqlite3WalkSelectFrom(pWalker, p) ) return WRC_Abort;
+    if( sqlite3WalkSelectExpr(pWalker, p)
+     || sqlite3WalkSelectFrom(pWalker, p)
+    ){
+      pWalker->walkerDepth--;
+      return WRC_Abort;
+    }
     p = p->pPrior;
   }
+  pWalker->walkerDepth--;
   return rc & WRC_Abort;
 }