SQLite

struct TreeView {
  int iLevel;             /* Which level of the tree we are on */
  u8  bLine[100];         /* Draw vertical in column i if bLine[i] is true */
};
#endif /* SQLITE_DEBUG */

/*
** This object is used in various ways, all related to window functions
**
**   (1) A single instance of this structure is attached to the
**       the Expr.pWin field for each window function in an expression tree.
**       This object holds the information contained in the OVER clause,
**       plus additional fields used during code generation.
**
**   (2) All window functions in a single SELECT form a linked-list
**       attached to Select.pWin.  The Window.pFunc and Window.pExpr
**       fields point back to the expression that is the window function.
**
**   (3) The terms of the WINDOW clause of a SELECT are instances of this
**       object on a linked list attached to Select.pWinDefn.
**
** The uses (1) and (2) are really the same Window object that just happens
** to be accessible in two different ways.  Use case (3) are separate objects.
*/
struct Window {
  char *zName;            /* Name of window (may be NULL) */
  char *zBase;            /* Name of base window for chaining (may be NULL) */
  ExprList *pPartition;   /* PARTITION BY clause */
  ExprList *pOrderBy;     /* ORDER BY clause */
  u8 eFrmType;            /* TK_RANGE, TK_GROUPS, TK_ROWS, or 0 */
  u8 eStart;              /* UNBOUNDED, CURRENT, PRECEDING or FOLLOWING */
  u8 eEnd;                /* UNBOUNDED, CURRENT, PRECEDING or FOLLOWING */
  u8 bImplicitFrame;      /* True if frame was implicitly specified */
  u8 eExclude;            /* TK_NO, TK_CURRENT, TK_TIES, TK_GROUP, or 0 */
  Expr *pStart;           /* Expression for "<expr> PRECEDING" */
  Expr *pEnd;             /* Expression for "<expr> FOLLOWING" */
  Window *pNextWin;       /* Next window function belonging to this SELECT */
  Expr *pFilter;          /* The FILTER expression */
  FuncDef *pFunc;         /* The function */
  int iEphCsr;            /* Partition buffer or Peer buffer */
  int regAccum;

#endif /* SQLITE_OMIT_WINDOWFUNC */

#ifndef SQLITE_OMIT_WINDOWFUNC
/*
** Generate a human-readable explanation for a Window object
*/
void sqlite3TreeViewWindow(TreeView *pView, const Window *pWin, u8 more){
  int nElement = 0;
  pView = sqlite3TreeViewPush(pView, more);
  if( pWin->zName ){
    sqlite3TreeViewLine(pView, "OVER %s", pWin->zName);
  }else{
    sqlite3TreeViewLine(pView, "OVER");
  }
  if( pWin->pFilter )  nElement++;
  if( pWin->zBase )    nElement++;
  if( pWin->pOrderBy ) nElement++;
  if( pWin->eFrmType ) nElement++;
  if( pWin->eExclude ) nElement++;
  if( pWin->pFilter ){
    sqlite3TreeViewItem(pView, "FILTER", (--nElement)>0);
    sqlite3TreeViewExpr(pView, pWin->pFilter, 0);
    sqlite3TreeViewPop(pView);
  }
  if( pWin->zBase ){
    sqlite3TreeViewPush(pView, (--nElement)>0);
    sqlite3TreeViewLine(pView, "window: %s", pWin->zBase);
    sqlite3TreeViewPop(pView);
  }
  if( pWin->pPartition ){
    sqlite3TreeViewExprList(pView, pWin->pPartition, nElement>0,"PARTITION-BY");
  }
  if( pWin->pOrderBy ){
    sqlite3TreeViewExprList(pView, pWin->pOrderBy, (--nElement)>0, "ORDER-BY");
  }
  if( pWin->eFrmType ){
    const char *zFrmType = "ROWS";
    if( pWin->eFrmType==TK_RANGE ) zFrmType = "RANGE";
    if( pWin->eFrmType==TK_GROUPS ) zFrmType = "GROUPS";
    sqlite3TreeViewItem(pView, zFrmType, (--nElement)>0);
    sqlite3TreeViewBound(pView, pWin->eStart, pWin->pStart, 1);
    sqlite3TreeViewBound(pView, pWin->eEnd, pWin->pEnd, 0);
    sqlite3TreeViewPop(pView);
  }
  if( pWin->eExclude ){
    char zBuf[30];
    const char *zExclude;
    switch( pWin->eExclude ){
      case TK_NO:      zExclude = "NO OTHERS";   break;
      case TK_CURRENT: zExclude = "CURRENT ROW"; break;
      case TK_GROUP:   zExclude = "GROUP";       break;
      case TK_TIES:    zExclude = "TIES";        break;
      default:
        sqlite3_snprintf(sizeof(zBuf),zBuf,"invalid(%d)", pWin->eExclude);
        zExclude = zBuf;
        break;
    }
    sqlite3TreeViewPush(pView, 0);
    sqlite3TreeViewLine(pView, "EXCLUDE %s", zExclude);
    sqlite3TreeViewPop(pView);
  }
  sqlite3TreeViewPop(pView);
}
#endif /* SQLITE_OMIT_WINDOWFUNC */

#ifndef SQLITE_OMIT_WINDOWFUNC
/*
** Generate a human-readable explanation for a Window Function object

*/
void sqlite3WindowUpdate(
  Parse *pParse, 
  Window *pList,                  /* List of named windows for this SELECT */
  Window *pWin,                   /* Window frame to update */
  FuncDef *pFunc                  /* Window function definition */
){
  if( pWin->zName && pWin->eFrmType==0 ){
    Window *p = windowFind(pParse, pList, pWin->zName);
    if( p==0 ) return;
    pWin->pPartition = sqlite3ExprListDup(pParse->db, p->pPartition, 0);
    pWin->pOrderBy = sqlite3ExprListDup(pParse->db, p->pOrderBy, 0);
    pWin->pStart = sqlite3ExprDup(pParse->db, p->pStart, 0);
    pWin->pEnd = sqlite3ExprDup(pParse->db, p->pEnd, 0);
    pWin->eStart = p->eStart;
    pWin->eEnd = p->eEnd;
    pWin->eFrmType = p->eFrmType;
    pWin->eExclude = p->eExclude;
  }else{
    sqlite3WindowChain(pParse, pWin, pList);
  }
  if( (pWin->eFrmType==TK_RANGE)
   && (pWin->pStart || pWin->pEnd) 
   && (pWin->pOrderBy==0 || pWin->pOrderBy->nExpr!=1)
  ){
    sqlite3ErrorMsg(pParse, 
      "RANGE with offset PRECEDING/FOLLOWING requires one ORDER BY expression"
    );
  }else
  if( pFunc->funcFlags & SQLITE_FUNC_WINDOW ){
    sqlite3 *db = pParse->db;
    if( pWin->pFilter ){
      sqlite3ErrorMsg(pParse, 
          "FILTER clause may only be used with aggregate window functions"
      );
    }else{
      struct WindowUpdate {
        const char *zFunc;
        int eFrmType;
        int eStart;
        int eEnd;
      } aUp[] = {
        { row_numberName,   TK_ROWS,   TK_UNBOUNDED, TK_CURRENT }, 
        { dense_rankName,   TK_RANGE,  TK_UNBOUNDED, TK_CURRENT }, 
        { rankName,         TK_RANGE,  TK_UNBOUNDED, TK_CURRENT }, 
        { percent_rankName, TK_GROUPS, TK_CURRENT,   TK_UNBOUNDED }, 
        { cume_distName,    TK_GROUPS, TK_FOLLOWING, TK_UNBOUNDED }, 
        { ntileName,        TK_ROWS,   TK_CURRENT,   TK_UNBOUNDED }, 
        { leadName,         TK_ROWS,   TK_UNBOUNDED, TK_UNBOUNDED }, 
        { lagName,          TK_ROWS,   TK_UNBOUNDED, TK_CURRENT }, 
      };
      int i;
      for(i=0; i<ArraySize(aUp); i++){
        if( pFunc->zName==aUp[i].zFunc ){
          sqlite3ExprDelete(db, pWin->pStart);
          sqlite3ExprDelete(db, pWin->pEnd);
          pWin->pEnd = pWin->pStart = 0;
          pWin->eFrmType = aUp[i].eFrmType;
          pWin->eStart = aUp[i].eStart;
          pWin->eEnd = aUp[i].eEnd;
          pWin->eExclude = 0;
          if( pWin->eStart==TK_FOLLOWING ){
            pWin->pStart = sqlite3Expr(db, TK_INTEGER, "1");
          }
          break;

}

/*
** Allocate and return a new Window object describing a Window Definition.
*/
Window *sqlite3WindowAlloc(
  Parse *pParse,    /* Parsing context */
  int eType,        /* Frame type. TK_RANGE, TK_ROWS, TK_GROUPS, or 0 */
  int eStart,       /* Start type: CURRENT, PRECEDING, FOLLOWING, UNBOUNDED */
  Expr *pStart,     /* Start window size if TK_PRECEDING or FOLLOWING */
  int eEnd,         /* End type: CURRENT, FOLLOWING, TK_UNBOUNDED, PRECEDING */
  Expr *pEnd,       /* End window size if TK_FOLLOWING or PRECEDING */
  u8 eExclude       /* EXCLUDE clause */
){
  Window *pWin = 0;

  ){
    sqlite3ErrorMsg(pParse, "unsupported frame specification");
    goto windowAllocErr;
  }

  pWin = (Window*)sqlite3DbMallocZero(pParse->db, sizeof(Window));
  if( pWin==0 ) goto windowAllocErr;
  pWin->eFrmType = eType;
  pWin->eStart = eStart;
  pWin->eEnd = eEnd;
  if( eExclude==0 && OptimizationDisabled(pParse->db, SQLITE_QueryFlattener) ){
    eExclude = TK_NO;
  }
  pWin->eExclude = eExclude;
  pWin->bImplicitFrame = bImplicitFrame;

}

/*
** Return 0 if the two window objects are identical, or non-zero otherwise.
** Identical window objects can be processed in a single scan.
*/
int sqlite3WindowCompare(Parse *pParse, Window *p1, Window *p2){
  if( p1->eFrmType!=p2->eFrmType ) return 1;
  if( p1->eStart!=p2->eStart ) return 1;
  if( p1->eEnd!=p2->eEnd ) return 1;
  if( p1->eExclude!=p2->eExclude ) 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;

  Parse *pParse = p->pParse;
  Window *pMWin = p->pMWin;
  int ret = 0;
  Vdbe *v = p->pVdbe;
  int addrIf = 0; 
  int addrContinue = 0;
  int addrGoto = 0;
  int bPeer = (pMWin->eFrmType!=TK_ROWS);

  int lblDone = sqlite3VdbeMakeLabel(pParse);
  int addrNextRange = 0;

  /* Special case - WINDOW_AGGINVERSE is always a no-op if the frame
  ** starts with UNBOUNDED PRECEDING. */
  if( op==WINDOW_AGGINVERSE && pMWin->eStart==TK_UNBOUNDED ){
    assert( regCountdown==0 && jumpOnEof==0 );
    return 0;
  }

  if( regCountdown>0 ){
    if( pMWin->eFrmType==TK_RANGE ){
      addrNextRange = sqlite3VdbeCurrentAddr(v);
      assert( op==WINDOW_AGGINVERSE || op==WINDOW_AGGSTEP );
      if( op==WINDOW_AGGINVERSE ){
        if( pMWin->eStart==TK_FOLLOWING ){
          windowCodeRangeTest(
              p, OP_Le, p->current.csr, regCountdown, p->start.csr, lblDone
          );

    pNew = sqlite3DbMallocZero(db, sizeof(Window));
    if( pNew ){
      pNew->zName = sqlite3DbStrDup(db, p->zName);
      pNew->pFilter = sqlite3ExprDup(db, p->pFilter, 0);
      pNew->pFunc = p->pFunc;
      pNew->pPartition = sqlite3ExprListDup(db, p->pPartition, 0);
      pNew->pOrderBy = sqlite3ExprListDup(db, p->pOrderBy, 0);
      pNew->eFrmType = p->eFrmType;
      pNew->eEnd = p->eEnd;
      pNew->eStart = p->eStart;
      pNew->eExclude = p->eExclude;
      pNew->pStart = sqlite3ExprDup(db, p->pStart, 0);
      pNew->pEnd = sqlite3ExprDup(db, p->pEnd, 0);
      pNew->pOwner = pOwner;
    }

  ** are four options - they may never be deleted (eDelete==0), they may 
  ** be deleted as soon as they are no longer part of the window frame
  ** (eDelete==WINDOW_AGGINVERSE), they may be deleted as after the row 
  ** has been returned to the caller (WINDOW_RETURN_ROW), or they may
  ** be deleted after they enter the frame (WINDOW_AGGSTEP). */
  switch( pMWin->eStart ){
    case TK_FOLLOWING:
      if( pMWin->eFrmType!=TK_RANGE
       && windowExprGtZero(pParse, pMWin->pStart)
      ){
        s.eDelete = WINDOW_RETURN_ROW;
      }
      break;
    case TK_UNBOUNDED:
      if( windowCacheFrame(pMWin)==0 ){
        if( pMWin->eEnd==TK_PRECEDING ){
          if( pMWin->eFrmType!=TK_RANGE
           && windowExprGtZero(pParse, pMWin->pEnd)
          ){
            s.eDelete = WINDOW_AGGSTEP;
          }
        }else{
          s.eDelete = WINDOW_RETURN_ROW;
        }
      }
      break;

  if( pMWin->eEnd==TK_PRECEDING || pMWin->eEnd==TK_FOLLOWING ){
    regEnd = ++pParse->nMem;
  }

  /* If this is not a "ROWS BETWEEN ..." frame, then allocate arrays of
  ** registers to store copies of the ORDER BY expressions (peer values) 
  ** for the main loop, and for each cursor (start, current and end). */
  if( pMWin->eFrmType!=TK_ROWS ){
    int nPeer = (pOrderBy ? pOrderBy->nExpr : 0);
    regNewPeer = regNew + pMWin->nBufferCol;
    if( pMWin->pPartition ) regNewPeer += pMWin->pPartition->nExpr;
    regPeer = pParse->nMem+1;       pParse->nMem += nPeer;
    s.start.reg = pParse->nMem+1;   pParse->nMem += nPeer;
    s.current.reg = pParse->nMem+1; pParse->nMem += nPeer;
    s.end.reg = pParse->nMem+1;     pParse->nMem += nPeer;

  VdbeCoverage(v);

  /* This block is run for the first row of each partition */
  s.regArg = windowInitAccum(pParse, pMWin);

  if( regStart ){
    sqlite3ExprCode(pParse, pMWin->pStart, regStart);
    windowCheckValue(pParse, regStart, 0 + (pMWin->eFrmType==TK_RANGE ? 3 : 0));
  }
  if( regEnd ){
    sqlite3ExprCode(pParse, pMWin->pEnd, regEnd);
    windowCheckValue(pParse, regEnd, 1 + (pMWin->eFrmType==TK_RANGE ? 3 : 0));
  }

  if( pMWin->eStart==pMWin->eEnd && regStart ){
    int op = ((pMWin->eStart==TK_FOLLOWING) ? OP_Ge : OP_Le);
    int addrGe = sqlite3VdbeAddOp3(v, op, regStart, 0, regEnd);
    VdbeCoverage(v);
    windowAggFinal(&s, 0);
    sqlite3VdbeAddOp2(v, OP_Rewind, s.current.csr, 1);
    VdbeCoverageNeverTaken(v);
    windowReturnOneRow(&s);
    sqlite3VdbeAddOp1(v, OP_ResetSorter, s.current.csr);
    sqlite3VdbeAddOp2(v, OP_Goto, 0, lblWhereEnd);
    sqlite3VdbeJumpHere(v, addrGe);
  }
  if( pMWin->eStart==TK_FOLLOWING && pMWin->eFrmType!=TK_RANGE && regEnd ){
    assert( pMWin->eEnd==TK_FOLLOWING );
    sqlite3VdbeAddOp3(v, OP_Subtract, regStart, regEnd, regStart);
  }

  if( pMWin->eStart!=TK_UNBOUNDED ){
    sqlite3VdbeAddOp2(v, OP_Rewind, s.start.csr, 1);
    VdbeCoverageNeverTaken(v);

  sqlite3VdbeJumpHere(v, addrNe);
  if( regPeer ){
    windowIfNewPeer(pParse, pOrderBy, regNewPeer, regPeer, lblWhereEnd);
  }
  if( pMWin->eStart==TK_FOLLOWING ){
    windowCodeOp(&s, WINDOW_AGGSTEP, 0, 0);
    if( pMWin->eEnd!=TK_UNBOUNDED ){
      if( pMWin->eFrmType==TK_RANGE ){
        int lbl = sqlite3VdbeMakeLabel(pParse);
        int addrNext = sqlite3VdbeCurrentAddr(v);
        windowCodeRangeTest(&s, OP_Ge, s.current.csr, regEnd, s.end.csr, lbl);
        windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0);
        windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 0);
        sqlite3VdbeAddOp2(v, OP_Goto, 0, addrNext);
        sqlite3VdbeResolveLabel(v, lbl);

    windowCodeOp(&s, WINDOW_AGGSTEP, regEnd, 0);
    windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 0);
    windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0);
  }else{
    int addr = 0;
    windowCodeOp(&s, WINDOW_AGGSTEP, 0, 0);
    if( pMWin->eEnd!=TK_UNBOUNDED ){
      if( pMWin->eFrmType==TK_RANGE ){
        int lbl = 0;
        addr = sqlite3VdbeCurrentAddr(v);
        if( regEnd ){
          lbl = sqlite3VdbeMakeLabel(pParse);
          windowCodeRangeTest(&s, OP_Ge, s.current.csr, regEnd, s.end.csr, lbl);
        }
        windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 0);

    windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 0);
  }else if( pMWin->eStart==TK_FOLLOWING ){
    int addrStart;
    int addrBreak1;
    int addrBreak2;
    int addrBreak3;
    windowCodeOp(&s, WINDOW_AGGSTEP, 0, 0);
    if( pMWin->eFrmType==TK_RANGE ){
      addrStart = sqlite3VdbeCurrentAddr(v);
      addrBreak2 = windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 1);
      addrBreak1 = windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 1);
    }else
    if( pMWin->eEnd==TK_UNBOUNDED ){
      addrStart = sqlite3VdbeCurrentAddr(v);
      addrBreak1 = windowCodeOp(&s, WINDOW_RETURN_ROW, regStart, 1);