SQLite

        pNew->pRight = p->pRight ?
                       exprDup(db, p->pRight, EXPRDUP_REDUCE, &zAlloc) : 0;
      }
      if( pzBuffer ){
        *pzBuffer = zAlloc;
      }
    }else{
      if( ExprHasProperty(p, EP_Reduced|EP_TokenOnly) ){
        pNew->pWin = 0;
      }else{
        pNew->pWin = winDup(db, p->pWin);
      }
      if( !ExprHasProperty(p, EP_TokenOnly|EP_Leaf) ){
        if( pNew->op==TK_SELECT_COLUMN ){
          pNew->pLeft = p->pLeft;
          assert( p->iColumn==0 || p->pRight==0 );
          assert( p->pRight==0  || p->pRight==p->pLeft );
        }else{
          pNew->pLeft = sqlite3ExprDup(db, p->pLeft, 0);

      sqlite3_result_error_nomem(context);
    }else{    
      sqlite3_result_text(context, sqlite3StrAccumFinish(pAccum), -1, 
                          sqlite3_free);
    }
  }
}
static void groupConcatValue(sqlite3_context *context){
  sqlite3_str *pAccum;
  pAccum = (sqlite3_str*)sqlite3_aggregate_context(context, 0);
  if( pAccum ){
    if( pAccum->accError==SQLITE_TOOBIG ){
      sqlite3_result_error_toobig(context);
    }else if( pAccum->accError==SQLITE_NOMEM ){
      sqlite3_result_error_nomem(context);
    }else{    
      const char *zText = sqlite3_str_value(pAccum);
      sqlite3_result_text(context, zText, -1, SQLITE_TRANSIENT);
    }
  }
}

/*
** This routine does per-connection function registration.  Most
** of the built-in functions above are part of the global function set.
** This routine only deals with those that are not global.
*/
void sqlite3RegisterPerConnectionBuiltinFunctions(sqlite3 *db){

    VFUNCTION(last_insert_rowid, 0, 0, 0, last_insert_rowid),
    VFUNCTION(changes,           0, 0, 0, changes          ),
    VFUNCTION(total_changes,     0, 0, 0, total_changes    ),
    FUNCTION(replace,            3, 0, 0, replaceFunc      ),
    FUNCTION(zeroblob,           1, 0, 0, zeroblobFunc     ),
    FUNCTION(substr,             2, 0, 0, substrFunc       ),
    FUNCTION(substr,             3, 0, 0, substrFunc       ),
    WAGGREGATE(sum,               1, 0, 0, sumStep,         sumFinalize),
    WAGGREGATE(total,             1, 0, 0, sumStep,         totalFinalize    ),
    WAGGREGATE(avg,               1, 0, 0, sumStep,         avgFinalize    ),
    AGGREGATE2(count,            0, 0, 0, countStep,       countFinalize,
               SQLITE_FUNC_COUNT  ),
    WAGGREGATE(count,             1, 0, 0, countStep,       countFinalize  ),
    AGGREGATE(group_concat,      1, 0, 0, groupConcatStep, groupConcatFinalize,
        groupConcatValue),
    AGGREGATE(group_concat,      2, 0, 0, groupConcatStep, groupConcatFinalize,
        groupConcatValue),
  
    LIKEFUNC(glob, 2, &globInfo, SQLITE_FUNC_LIKE|SQLITE_FUNC_CASE),
#ifdef SQLITE_CASE_SENSITIVE_LIKE
    LIKEFUNC(like, 2, &likeInfoAlt, SQLITE_FUNC_LIKE|SQLITE_FUNC_CASE),
    LIKEFUNC(like, 3, &likeInfoAlt, SQLITE_FUNC_LIKE|SQLITE_FUNC_CASE),
#else
    LIKEFUNC(like, 2, &likeInfoNorm, SQLITE_FUNC_LIKE),

             nId, zId);
        pNC->nErr++;
      }
      if( is_agg ) pNC->ncFlags &= ~NC_AllowAgg;
      sqlite3WalkExprList(pWalker, pList);
      if( is_agg ){
        if( pExpr->pWin ){
          if( 0==pNC->pWin 
           || 0==sqlite3WindowCompare(pParse, pNC->pWin, pExpr->pWin) 
          ){
            pExpr->pWin->pNextWin = pNC->pWin;
            pNC->pWin = pExpr->pWin;
          }
          pExpr->pWin->pFunc = pDef;
          pExpr->pWin->nArg = (pExpr->x.pList ? pExpr->x.pList->nExpr : 0);

        }else{

          NameContext *pNC2 = pNC;
          pExpr->op = TK_AGG_FUNCTION;
          pExpr->op2 = 0;
          while( pNC2 && !sqlite3FunctionUsesThisSrc(pExpr, pNC2->pSrcList) ){
            pExpr->op2++;
            pNC2 = pNC2->pNext;
          }

static int selectWindowRewriteSelectCb(Walker *pWalker, Select *pSelect){
  return WRC_Prune;
}

static int selectWindowRewriteExprCb(Walker *pWalker, Expr *pExpr){
  struct WindowRewrite *p = pWalker->u.pRewrite;
  Parse *pParse = pWalker->pParse;


  switch( pExpr->op ){

    case TK_FUNCTION:
      if( pExpr->pWin==0 ){
        break;
      }else{
        Window *pWin;
        for(pWin=p->pWin; pWin; pWin=pWin->pNextWin){
          if( pExpr->pWin==pWin ){

            pExpr->pWin->pOwner = pExpr;
            return WRC_Prune;
          }
        }
      }
      /* Fall through.  */

    case TK_COLUMN: {
      Expr *pDup = sqlite3ExprDup(pParse->db, pExpr, 0);
      p->pSub = sqlite3ExprListAppend(pParse, p->pSub, pDup);
      if( p->pSub ){

      break;
    }

    default: /* no-op */
      break;
  }

  return WRC_Continue;
}

static int selectWindowRewriteEList(
  Parse *pParse, 
  Window *pWin,
  ExprList *pEList,               /* Rewrite expressions in this list */
  ExprList **ppSub                /* IN/OUT: Sub-select expression-list */

    SrcList *pSrc = p->pSrc;
    Expr *pWhere = p->pWhere;
    ExprList *pGroupBy = p->pGroupBy;
    Expr *pHaving = p->pHaving;
    ExprList *pSort = 0;

    ExprList *pSublist = 0;       /* Expression list for sub-query */
    Window *pMWin = p->pWin;      /* Master window object */
    Window *pWin;                 /* Window object iterator */

    p->pSrc = 0;
    p->pWhere = 0;
    p->pGroupBy = 0;
    p->pHaving = 0;




    /* Assign a cursor number for the ephemeral table used to buffer rows.
    ** The OpenEphemeral instruction is coded later, after it is known how
    ** many columns the table will have.  */
    pMWin->iEphCsr = pParse->nTab++;

    rc = selectWindowRewriteEList(pParse, pMWin, p->pEList, &pSublist);
    if( rc ) return rc;
    rc = selectWindowRewriteEList(pParse, pMWin, p->pOrderBy, &pSublist);
    if( rc ) return rc;
    pMWin->nBufferCol = (pSublist ? pSublist->nExpr : 0);

    /* Create the ORDER BY clause for the sub-select. This is the concatenation
    ** of the window PARTITION and ORDER BY clauses. Append the same 
    ** expressions to the sub-select expression list. They are required to
    ** figure out where boundaries for partitions and sets of peer rows.  */
    pSort = sqlite3ExprListDup(db, pMWin->pPartition, 0);
    if( pMWin->pOrderBy ){
      pSort = exprListAppendList(pParse, pSort, pMWin->pOrderBy);
    }
    pSublist = exprListAppendList(pParse, pSublist, pSort);

    /* Append the arguments passed to each window function to the
    ** sub-select expression list. Also allocate two registers for each
    ** window function - one for the accumulator, another for interim
    ** results.  */
    for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
      pWin->iArgCol = (pSublist ? pSublist->nExpr : 0);
      pSublist = exprListAppendList(pParse, pSublist, pWin->pOwner->x.pList);
      pWin->regAccum = ++pParse->nMem;
      pWin->regResult = ++pParse->nMem;
      sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
    }

    pSub = sqlite3SelectNew(
        pParse, pSublist, pSrc, pWhere, pGroupBy, pHaving, pSort, 0, 0
    );
    p->pSrc = sqlite3SrcListAppend(db, 0, 0, 0);
    if( p->pSrc ){
      int iTab;
      ExprList *pList = 0;
      p->pSrc->a[0].pSelect = pSub;
      sqlite3SrcListAssignCursors(pParse, p->pSrc);
      if( selectExpandSubquery(pParse, &p->pSrc->a[0]) ){
        rc = SQLITE_NOMEM;
      }else{
        pSub->selFlags |= SF_Expanded;
      }

    }

#if SELECTTRACE_ENABLED
    if( sqlite3SelectTrace & 0x108 ){
      SELECTTRACE(0x104,pParse,p, ("after window rewrite:\n"));
      sqlite3TreeViewSelect(0, p, 0);
    }
#endif

    sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pMWin->iEphCsr, pMWin->nBufferCol);

  }

  return rc;
}

/*
** Generate code for the SELECT statement given in the p argument.  

    sqlite3VdbeChangeP5(v, BTREE_UNORDERED);
    sDistinct.eTnctType = WHERE_DISTINCT_UNORDERED;
  }else{
    sDistinct.eTnctType = WHERE_DISTINCT_NOOP;
  }

  if( !isAgg && pGroupBy==0 ){
    Window *pMWin = p->pWin;      /* Master window object (or NULL) */
    int regPart = 0;

    /* No aggregate functions and no GROUP BY clause */
    u16 wctrlFlags = (sDistinct.isTnct ? WHERE_WANT_DISTINCT : 0);
    assert( WHERE_USE_LIMIT==SF_FixedLimit );
    wctrlFlags |= p->selFlags & SF_FixedLimit;

    if( pMWin ){
      int nPart = (pMWin->pPartition ? pMWin->pPartition->nExpr : 0);
      nPart += (pMWin->pOrderBy ? pMWin->pOrderBy->nExpr : 0);
      if( nPart ){
        regPart = pParse->nMem+1;
        pParse->nMem += nPart;
        sqlite3VdbeAddOp3(v, OP_Null, 0, regPart, regPart+nPart-1);
      }
    }

    ** into an OP_Noop.
    */
    if( sSort.addrSortIndex>=0 && sSort.pOrderBy==0 ){
      sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);
    }

    assert( p->pEList==pEList );
    if( pMWin ){
      Window *pWin;
      int k;
      int iSubCsr = p->pSrc->a[0].iCursor;
      int nSub = p->pSrc->a[0].pTab->nCol;
      int reg = pParse->nMem+1;
      int regRecord = reg+nSub;
      int regRowid = regRecord+1;
      int regGosub = regRowid+1;
      int addr;
      int addrGosub;

      pParse->nMem += nSub + 3;

      /* Martial the row returned by the sub-select into an array of 
      ** registers. */
      for(k=0; k<nSub; k++){
        sqlite3VdbeAddOp3(v, OP_Column, iSubCsr, k, reg+k);
      }

      /* Check if this is the start of a new partition or peer group. */
      if( regPart ){
        ExprList *pPart = pMWin->pPartition;
        int nPart = (pPart ? pPart->nExpr : 0);
        ExprList *pOrderBy = pMWin->pOrderBy;
        int nPeer = (pOrderBy ? pOrderBy->nExpr : 0);
        int addrGoto = 0;
        int addrJump = 0;

        if( pPart ){
          int regNewPart = reg + pMWin->nBufferCol;
          KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pPart, 0, 0);
          addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPart, regPart, nPart);
          sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
          addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);
          for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
            sqlite3VdbeAddOp2(v, OP_AggFinal, pWin->regAccum, pWin->nArg);
            sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
            sqlite3VdbeAddOp2(v, OP_Copy, pWin->regAccum, pWin->regResult);
          }
          if( pOrderBy ){
            addrGoto = sqlite3VdbeAddOp0(v, OP_Goto);
          }
        }

        if( pOrderBy ){
          int regNewPeer = reg + pMWin->nBufferCol + nPart;
          int regPeer = regPart + nPart;

          KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pOrderBy, 0, 0);
          if( addrJump ) sqlite3VdbeJumpHere(v, addrJump);
          addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPeer, regPeer, nPeer);
          sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
          addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);
          for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
            sqlite3VdbeAddOp3(v, 
                OP_AggFinal, pWin->regAccum, pWin->nArg, pWin->regResult
            );
            sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
          }
          if( addrGoto ) sqlite3VdbeJumpHere(v, addrGoto);
        }

        addrGosub = sqlite3VdbeAddOp1(v, OP_Gosub, regGosub);
        sqlite3VdbeAddOp1(v, OP_ResetSorter, pMWin->iEphCsr);
        sqlite3VdbeAddOp3(
            v, OP_Copy, reg+pMWin->nBufferCol, regPart, nPart+nPeer-1
        );

        sqlite3VdbeJumpHere(v, addrJump);
      }

      /* Invoke step function for window functions */
      for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
        sqlite3VdbeAddOp3(v, OP_AggStep0, 0, reg+pWin->iArgCol, pWin->regAccum);
        sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
        sqlite3VdbeChangeP5(v, (u8)pWin->nArg);
      }

      /* Buffer the current row in the ephemeral table. */
      if( pMWin->nBufferCol>0 ){
        sqlite3VdbeAddOp3(v, OP_MakeRecord, reg, pMWin->nBufferCol, regRecord);
      }else{
        sqlite3VdbeAddOp2(v, OP_Blob, 0, regRecord);
        sqlite3VdbeAppendP4(v, (void*)"", 0);
      }
      sqlite3VdbeAddOp2(v, OP_NewRowid, pMWin->iEphCsr, regRowid);
      sqlite3VdbeAddOp3(v, OP_Insert, pMWin->iEphCsr, regRecord, regRowid);

      /* End the database scan loop. */
      sqlite3WhereEnd(pWInfo);

      for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
        sqlite3VdbeAddOp2(v, OP_AggFinal, pWin->regAccum, pWin->nArg);
        sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
        sqlite3VdbeAddOp2(v, OP_Copy, pWin->regAccum, pWin->regResult);
      }
      sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, sqlite3VdbeCurrentAddr(v)+2);

      sqlite3VdbeAddOp0(v, OP_Goto);
      if( regPart ){
        sqlite3VdbeJumpHere(v, addrGosub);
      }
      addr = sqlite3VdbeAddOp1(v, OP_Rewind, pMWin->iEphCsr);
      selectInnerLoop(pParse, p, -1, &sSort, &sDistinct, pDest, addr+1, 0);
      sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, addr+1);
      sqlite3VdbeJumpHere(v, addr);
      sqlite3VdbeAddOp1(v, OP_Return, regGosub);
      sqlite3VdbeJumpHere(v, addr-1);       /* OP_Goto jumps here */

    }else{
      /* Use the standard inner loop. */
      selectInnerLoop(pParse, p, -1, &sSort, &sDistinct, pDest,

   SQLITE_INT_TO_PTR(iArg), 0, xFunc, 0, 0, 0, #zName, {0} }
#define STR_FUNCTION(zName, nArg, pArg, bNC, xFunc) \
  {nArg, SQLITE_FUNC_SLOCHNG|SQLITE_UTF8|(bNC*SQLITE_FUNC_NEEDCOLL), \
   pArg, 0, xFunc, 0, 0, 0, #zName, }
#define LIKEFUNC(zName, nArg, arg, flags) \
  {nArg, SQLITE_FUNC_CONSTANT|SQLITE_UTF8|flags, \
   (void *)arg, 0, likeFunc, 0, 0, 0, #zName, {0} }
#define AGGREGATE(zName, nArg, arg, nc, xStep, xFinal, xValue) \
  {nArg, SQLITE_UTF8|(nc*SQLITE_FUNC_NEEDCOLL), \
   SQLITE_INT_TO_PTR(arg), 0, xStep,xFinal,xValue,0,#zName, {0}}
#define AGGREGATE2(zName, nArg, arg, nc, xStep, xFinal, extraFlags) \
  {nArg, SQLITE_UTF8|(nc*SQLITE_FUNC_NEEDCOLL)|extraFlags, \
   SQLITE_INT_TO_PTR(arg), 0, xStep,xFinal,xFinal,0,#zName, {0}}

#define WAGGREGATE(zName, nArg, arg, nc, xStep, xFinal) \
  {nArg, SQLITE_UTF8|(nc*SQLITE_FUNC_NEEDCOLL), \
   SQLITE_INT_TO_PTR(arg), 0, xStep,xFinal,xFinal,0,#zName, {0}}

/*
** All current savepoints are stored in a linked list starting at
** sqlite3.pSavepoint. The first element in the list is the most recently
** opened savepoint. Savepoints are added to the list by the vdbe
** OP_Savepoint instruction.
*/

  int nBufferCol;         /* Number of columns in buffer table */
  int iArgCol;            /* Offset of first argument for this function */
};

void sqlite3WindowDelete(sqlite3*, Window*);
Window *sqlite3WindowAlloc(Parse*, int, int, Expr*, int , Expr*);
void sqlite3WindowAttach(Parse*, Expr*, Window*);
int sqlite3WindowCompare(Parse*, Window*, Window*);

/*
** Assuming zIn points to the first byte of a UTF-8 character,
** advance zIn to point to the first byte of the next UTF-8 character.
*/
#define SQLITE_SKIP_UTF8(zIn) {                        \
  if( (*(zIn++))>=0xc0 ){                              \

void sqlite3WindowAttach(Parse *pParse, Expr *p, Window *pWin){
  if( p ){
    p->pWin = pWin;
  }else{
    sqlite3WindowDelete(pParse->db, pWin);
  }
}

/*
** Return 0 if the two window objects are identical, or non-zero otherwise.
*/
int sqlite3WindowCompare(Parse *pParse, Window *p1, Window *p2){
  if( p1->eType!=p2->eType ) return 1;
  if( p1->eStart!=p2->eStart ) return 1;
  if( p1->eEnd!=p2->eEnd ) return 1;
  if( sqlite3ExprCompare(pParse, p1->pStart, p2->pStart, -1) ) return 1;
  if( sqlite3ExprCompare(pParse, p1->pEnd, p2->pEnd, -1) ) return 1;
  if( sqlite3ExprListCompare(p1->pPartition, p2->pPartition, -1) ) return 1;
  if( sqlite3ExprListCompare(p1->pOrderBy, p2->pOrderBy, -1) ) return 1;
  return 0;
}

  1   9  1 
  2  12  2 
  3   8  3 
  4  10  5 
  5   5  7 
  6   6  9
}

do_execsql_test 4.9 {
  SELECT a, 
    sum(a) OVER (ORDER BY a), 
    avg(a) OVER (ORDER BY a) 
  FROM t2 ORDER BY a
} {
  0  0       0.0
  1  1       0.5
  2  3       1.0
  3  6       1.5
  4  10      2.0
  5  15      2.5
  6  21      3.0
}

do_execsql_test 4.10 {
  SELECT a, 
    count() OVER (ORDER BY a DESC),
    group_concat(a, '.') OVER (ORDER BY a DESC) 
  FROM t2 ORDER BY a DESC
} {
  6 1 6
  5 2 6.5
  4 3 6.5.4
  3 4 6.5.4.3
  2 5 6.5.4.3.2
  1 6 6.5.4.3.2.1
  0 7 6.5.4.3.2.1.0
}


finish_test