/ Check-in [0cd55e98]
Login

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

Overview
Comment:Clarify the relationship between a Window object and its associated Expr.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | exp-window-functions
Files: files | file ages | folders
SHA3-256:0cd55e98a478740032f5569ddc00fa5b0e063e90db6e00ac7598c9b7c2fffeee
User & Date: dan 2018-06-11 20:50:25
Context
2018-06-12
18:40
Fix some problems with using window-functions in aggregate queries. check-in: fe7081e0 user: dan tags: exp-window-functions
2018-06-11
20:50
Clarify the relationship between a Window object and its associated Expr. check-in: 0cd55e98 user: dan tags: exp-window-functions
18:16
Fix handling of window frames containing negative number of rows. e.g. "ROWS x PRECEDING AND y PRECEDING" where (x<y). check-in: b6d9c7ed user: dan tags: exp-window-functions
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/expr.c.

1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
      if( pzBuffer ){
        *pzBuffer = zAlloc;
      }
    }else{
      if( ExprHasProperty(p, EP_Reduced|EP_TokenOnly) ){
        pNew->pWin = 0;
      }else{
        pNew->pWin = sqlite3WindowDup(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{







|







1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
      if( pzBuffer ){
        *pzBuffer = zAlloc;
      }
    }else{
      if( ExprHasProperty(p, EP_Reduced|EP_TokenOnly) ){
        pNew->pWin = 0;
      }else{
        pNew->pWin = sqlite3WindowDup(db, pNew, 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{

Changes to src/resolve.c.

796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
          sqlite3WindowUpdate(pParse, pSel->pWinDefn, pExpr->pWin, pDef);
          if( 0==pSel->pWin 
           || 0==sqlite3WindowCompare(pParse, pSel->pWin, pExpr->pWin) 
          ){
            pExpr->pWin->pNextWin = pSel->pWin;
            pSel->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;







<
<







796
797
798
799
800
801
802


803
804
805
806
807
808
809
          sqlite3WindowUpdate(pParse, pSel->pWinDefn, pExpr->pWin, pDef);
          if( 0==pSel->pWin 
           || 0==sqlite3WindowCompare(pParse, pSel->pWin, pExpr->pWin) 
          ){
            pExpr->pWin->pNextWin = pSel->pWin;
            pSel->pWin = pExpr->pWin;
          }


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

Changes to src/sqliteInt.h.

3484
3485
3486
3487
3488
3489
3490
3491
3492
3493
3494
3495
3496
3497
3498
....
3509
3510
3511
3512
3513
3514
3515
3516
3517
3518
3519
3520
3521
3522
3523
  Expr *pStart;           /* Expression for "<expr> PRECEDING" */
  Expr *pEnd;             /* Expression for "<expr> FOLLOWING" */

  Window *pNextWin;       /* Next window function belonging to this SELECT */

  Expr *pFilter;
  FuncDef *pFunc;
  int nArg;

  int iEphCsr;            /* Temp table used by this window */
  int regAccum;
  int regResult;

  int csrApp;             /* Function cursor (used by min/max) */
  int regApp;             /* Function register (also used by min/max) */
................................................................................
void sqlite3WindowAttach(Parse*, Expr*, Window*);
int sqlite3WindowCompare(Parse*, Window*, Window*);
void sqlite3WindowCodeInit(Parse*, Window*);
void sqlite3WindowCodeStep(Parse*, Select*, WhereInfo*, int, int);
int sqlite3WindowRewrite(Parse*, Select*);
int sqlite3ExpandSubquery(Parse*, struct SrcList_item*);
void sqlite3WindowUpdate(Parse*, Window*, Window*, FuncDef*);
Window *sqlite3WindowDup(sqlite3 *db, Window *p);

/*
** 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 ){                              \







<







 







|







3484
3485
3486
3487
3488
3489
3490

3491
3492
3493
3494
3495
3496
3497
....
3508
3509
3510
3511
3512
3513
3514
3515
3516
3517
3518
3519
3520
3521
3522
  Expr *pStart;           /* Expression for "<expr> PRECEDING" */
  Expr *pEnd;             /* Expression for "<expr> FOLLOWING" */

  Window *pNextWin;       /* Next window function belonging to this SELECT */

  Expr *pFilter;
  FuncDef *pFunc;


  int iEphCsr;            /* Temp table used by this window */
  int regAccum;
  int regResult;

  int csrApp;             /* Function cursor (used by min/max) */
  int regApp;             /* Function register (also used by min/max) */
................................................................................
void sqlite3WindowAttach(Parse*, Expr*, Window*);
int sqlite3WindowCompare(Parse*, Window*, Window*);
void sqlite3WindowCodeInit(Parse*, Window*);
void sqlite3WindowCodeStep(Parse*, Select*, WhereInfo*, int, int);
int sqlite3WindowRewrite(Parse*, Select*);
int sqlite3ExpandSubquery(Parse*, struct SrcList_item*);
void sqlite3WindowUpdate(Parse*, Window*, Window*, FuncDef*);
Window *sqlite3WindowDup(sqlite3 *db, Expr *pOwner, Window *p);

/*
** 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 ){                              \

Changes to src/window.c.

22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

42
43
44
45
46
47
48
..
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
..
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
...
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
...
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
...
177
178
179
180
181
182
183



184
185
186
187
188
189
190
...
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
...
239
240
241
242
243
244
245



246
247
248
249
250
251
252
...
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
...
292
293
294
295
296
297
298
299

300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
...
433
434
435
436
437
438
439

440
441
442
443
444
445
446
...
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
...
680
681
682
683
684
685
686

687
688
689
690
691
692
693
...
761
762
763
764
765
766
767





768
769
770
771
772
773
774
...
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
...
828
829
830
831
832
833
834

835
836
837
838
839
840
841
842
843
844
845
846
...
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
...
971
972
973
974
975
976
977

978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
....
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
....
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678

1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740

1741
1742
1743

1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
....
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781

1782
1783
1784
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
  i64 *p = (i64*)sqlite3_aggregate_context(pCtx, sizeof(*p));
  if( p ) (*p)++;
}
static void row_numberInverseFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void row_numberValueFunc(sqlite3_context *pCtx){
  i64 *p = (i64*)sqlite3_aggregate_context(pCtx, sizeof(*p));
  sqlite3_result_int64(pCtx, (p ? *p : 0));
}

/*
** Context object type used by rank() and dense_rank().

*/
struct CallCount {
  i64 nValue;
  i64 nStep;
  i64 nTotal;
};

................................................................................
  int nArg,
  sqlite3_value **apArg
){
  struct CallCount *p;
  p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
  if( p ) p->nStep = 1;
}
static void dense_rankInverseFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void dense_rankValueFunc(sqlite3_context *pCtx){
  struct CallCount *p;
................................................................................
  if( p ){
    p->nStep++;
    if( p->nValue==0 ){
      p->nValue = p->nStep;
    }
  }
}
static void rankInverseFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void rankValueFunc(sqlite3_context *pCtx){
  struct CallCount *p;
................................................................................
    }
    p->nStep++;
    if( p->nValue==0 ){
      p->nValue = p->nStep;
    }
  }
}
static void percent_rankInverseFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void percent_rankValueFunc(sqlite3_context *pCtx){
  struct CallCount *p;
................................................................................
  if( p ){
    if( p->nTotal==0 ){
      p->nTotal = sqlite3_value_int64(apArg[0]);
    }
    p->nStep++;
  }
}
static void cume_distInverseFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void cume_distValueFunc(sqlite3_context *pCtx){
  struct CallCount *p;
................................................................................
  p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
  if( p ){
    double r = (double)(p->nStep) / (double)(p->nTotal);
    sqlite3_result_double(pCtx, r);
  }
}




struct NtileCtx {
  i64 nTotal;                     /* Total rows in partition */
  i64 nParam;                     /* Parameter passed to ntile(N) */
  i64 iRow;                       /* Current row */
};

/*
................................................................................
            pCtx, "argument of ntile must be a positive integer", -1
        );
      }
    }
    p->iRow++;
  }
}
static void ntileInverseFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void ntileValueFunc(sqlite3_context *pCtx){
  struct NtileCtx *p;
................................................................................
      }else{
        sqlite3_result_int64(pCtx, 1 + nLarge + (iRow-iSmall)/nSize);
      }
    }
  }
}




struct LastValueCtx {
  sqlite3_value *pVal;
  int nVal;
};

/*
** Implementation of last_value().
................................................................................
  p = (struct LastValueCtx *)sqlite3_aggregate_context(pCtx, sizeof(*p));
  if( p ){
    sqlite3_value_free(p->pVal);
    p->pVal = sqlite3_value_dup(apArg[0]);
    p->nVal++;
  }
}
static void last_valueInverseFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
  struct LastValueCtx *p;
  p = (struct LastValueCtx *)sqlite3_aggregate_context(pCtx, sizeof(*p));
  if( p ){
................................................................................
  if( p && p->pVal ){
    sqlite3_result_value(pCtx, p->pVal);
    sqlite3_value_free(p->pVal);
    p->pVal = 0;
  }
}

static void nth_valueStepFunc(

  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void nth_valueInverseFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void nth_valueValueFunc(sqlite3_context *pCtx){
}

static void first_valueStepFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void first_valueInverseFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void first_valueValueFunc(sqlite3_context *pCtx){
}

static void leadStepFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void leadInverseFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void leadValueFunc(sqlite3_context *pCtx){
}

static void lagStepFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void lagInverseFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void lagValueFunc(sqlite3_context *pCtx){
}

#define WINDOWFUNC(name,nArg,extra) {                                      \
  nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0,                      \
  name ## StepFunc, name ## ValueFunc, name ## ValueFunc,                  \
  name ## InverseFunc, #name                                               \
}

#define WINDOWFUNCF(name,nArg,extra) {                                     \
  nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0,                      \
  name ## StepFunc, name ## FinalizeFunc, name ## ValueFunc,               \
  name ## InverseFunc, #name                                               \
}

/*
** Register those built-in window functions that are not also aggregates.
*/
void sqlite3WindowFunctions(void){
  static FuncDef aWindowFuncs[] = {
................................................................................
      sqlite3ExprDelete(db, pWin->pEnd);
      pWin->pStart = pWin->pEnd = 0;
      pWin->eType = TK_RANGE;
      pWin->eStart = TK_UNBOUNDED;
      pWin->eEnd = TK_CURRENT;
    }
  }

}

typedef struct WindowRewrite WindowRewrite;
struct WindowRewrite {
  Window *pWin;
  ExprList *pSub;
};
................................................................................
    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: {
................................................................................

  return pWin;
}

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.
................................................................................

  sqlite3VdbeAddOp2(v, OP_Integer, 0, regZero);
  sqlite3VdbeAddOp2(v, OP_MustBeInt, reg, sqlite3VdbeCurrentAddr(v)+2);
  sqlite3VdbeAddOp3(v, OP_Ge, regZero, sqlite3VdbeCurrentAddr(v)+2, reg);
  sqlite3VdbeAddOp2(v, OP_Halt, SQLITE_ERROR, OE_Abort);
  sqlite3VdbeAppendP4(v, (void*)azErr[bEnd], P4_STATIC);
}






/*
** Generate VM code to invoke either xStep() (if bInverse is 0) or 
** xInverse (if bInverse is non-zero) for each window function in the 
** linked list starting at pMWin.
*/
static void windowAggStep(
................................................................................
  int regPartSize                 /* Register containing size of partition */
){
  Vdbe *v = sqlite3GetVdbe(pParse);
  Window *pWin;
  for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
    int flags = pWin->pFunc->funcFlags;
    int regArg;
    int nArg = pWin->nArg;

    if( csr>=0 ){
      int i;
      for(i=0; i<pWin->nArg; i++){
        sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol+i, reg+i);
      }
      regArg = reg;
      if( flags & SQLITE_FUNC_WINDOW_SIZE ){
        if( nArg==0 ){
          regArg = regPartSize;
        }else{
................................................................................
           || pWin->pFunc->xSFunc==lagStepFunc 
    ){
      /* no-op */
    }else{
      int addrIf = 0;
      if( pWin->pFilter ){
        int regTmp;

        if( csr>0 ){
          regTmp = sqlite3GetTempReg(pParse);
          sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol+pWin->nArg,regTmp);
        }else{
          regTmp = regArg + pWin->nArg;
        }
        addrIf = sqlite3VdbeAddOp3(v, OP_IfNot, regTmp, 0, 1);
        if( csr>0 ){
          sqlite3ReleaseTempReg(pParse, regTmp);
        }
      }
      if( pWin->pFunc->funcFlags & SQLITE_FUNC_NEEDCOLL ){
................................................................................
        sqlite3VdbeAddOp1(v, OP_ResetSorter, pWin->csrApp);
      }
    }else if( pWin->regApp ){
    }else{
      if( bFinal==0 ){
        sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regResult);
      }
      sqlite3VdbeAddOp2(v, OP_AggFinal, pWin->regAccum, pWin->nArg);
      sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
      if( bFinal ){
        sqlite3VdbeAddOp2(v, OP_Copy, pWin->regAccum, pWin->regResult);
        sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
      }else{
        sqlite3VdbeChangeP3(v, -1, pWin->regResult);
      }
................................................................................
      sqlite3VdbeAddOp3(v, OP_Gt, pWin->regApp+1, lbl, tmpReg);
      sqlite3VdbeAddOp3(v, OP_SeekRowid, csr, lbl, tmpReg);
      sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol, pWin->regResult);
      sqlite3VdbeResolveLabel(v, lbl);
      sqlite3ReleaseTempReg(pParse, tmpReg);
    }
    else if( pFunc->xSFunc==leadStepFunc || pFunc->xSFunc==lagStepFunc ){

      int iEph = pWin->iEphCsr;
      int csr = pWin->csrApp;
      int lbl = sqlite3VdbeMakeLabel(v);
      int tmpReg = sqlite3GetTempReg(pParse);

      if( pWin->nArg<3 ){
        sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regResult);
      }else{
        sqlite3VdbeAddOp3(v, OP_Column, iEph, pWin->iArgCol+2, pWin->regResult);
      }
      sqlite3VdbeAddOp2(v, OP_Rowid, iEph, tmpReg);
      if( pWin->nArg<2 ){
        int val = (pFunc->xSFunc==leadStepFunc ? 1 : -1);
        sqlite3VdbeAddOp2(v, OP_AddImm, tmpReg, val);
      }else{
        int op = (pFunc->xSFunc==leadStepFunc ? OP_Add : OP_Subtract);
        int tmpReg2 = sqlite3GetTempReg(pParse);
        sqlite3VdbeAddOp3(v, OP_Column, iEph, pWin->iArgCol+1, tmpReg2);
        sqlite3VdbeAddOp3(v, op, tmpReg2, tmpReg, tmpReg);
................................................................................
static int windowInitAccum(Parse *pParse, Window *pMWin){
  Vdbe *v = sqlite3GetVdbe(pParse);
  int regArg;
  int nArg = 0;
  Window *pWin;
  for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
    sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
    nArg = MAX(nArg, pWin->nArg);
    if( pWin->pFunc->xSFunc==nth_valueStepFunc
     || pWin->pFunc->xSFunc==first_valueStepFunc 
    ){
      sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp);
      sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp+1);
    }
  }
................................................................................

  windowAggFinal(pParse, pMWin, 1);
  sqlite3VdbeAddOp2(v, OP_Rewind, pMWin->iEphCsr,sqlite3VdbeCurrentAddr(v)+3);
  sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
  sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, sqlite3VdbeCurrentAddr(v)-1);
}

Window *sqlite3WindowDup(sqlite3 *db, Window *p){
  Window *pNew = 0;
  if( p ){
    pNew = sqlite3DbMallocZero(db, sizeof(Window));
    if( pNew ){
      pNew->pFilter = sqlite3ExprDup(db, p->pFilter, 0);
      pNew->pPartition = sqlite3ExprListDup(db, p->pPartition, 0);
      pNew->pOrderBy = sqlite3ExprListDup(db, p->pOrderBy, 0);
      pNew->eType = p->eType;
      pNew->eEnd = p->eEnd;
      pNew->eStart = p->eStart;
      pNew->pStart = sqlite3ExprDup(db, pNew->pStart, 0);
      pNew->pEnd = sqlite3ExprDup(db, pNew->pEnd, 0);

    }
  }
  return pNew;
}

/*
** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
**
**   As above, except take no action for a "new peer". Invoke
**   the sub-routine once only for each partition.
**
** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
**
**   As above, except that the "new peer" condition is handled in the
**   same way as "new partition" (so there is no "else if" block).
**
** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
**
**   One way is to just reverse the sort order and do as for BETWEEN 
**   UNBOUNDED PRECEDING AND CURRENT ROW. But that is not quite the same for
**   things like group_concat(). And perhaps other user defined aggregates 
**   as well.
**
**   ...
**     if( new partition ){
**       Gosub flush_partition;
**       ResetSorter eph-table
**     }
**     AggStep
**     Insert (record into eph-table)
**   sqlite3WhereEnd()
**   Gosub flush_partition
**
**  flush_partition:
**   OpenDup (csr -> csr2)
**   foreach (record in eph-table) {
**     if( new peer ){
**       while( csr2!=csr ){
**         AggStep (xInverse)
**         Next (csr2)
**       }
**     }
**     AggFinal (xValue)
**     Gosub addrGosub
**   }
**
**========================================================================
**
** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
**   ...
**     if( new partition ){
**       AggFinal (xFinalize)
**     }
**     AggStep
**     AggFinal (xValue)
**     Gosub addrGosub
**   sqlite3WhereEnd()
**
*/
void sqlite3WindowCodeStep(
  Parse *pParse, 
  Select *p,

  WhereInfo *pWInfo,
  int regGosub, 
  int addrGosub

){
  Window *pMWin = p->pWin;
  Window *pWin;

  /*
  ** Call windowCodeRowExprStep() for all window modes *except*:
  **
  **   RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
  **   RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
  **   RANGE BETWEEN CURRENT ROW AND CURRENT ROW
  **   ROWS  BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
  */
  if( (pMWin->eType==TK_ROWS 
................................................................................
   && (pMWin->eStart!=TK_UNBOUNDED||pMWin->eEnd!=TK_CURRENT||!pMWin->pOrderBy))
   || (pMWin->eStart==TK_CURRENT&&pMWin->eEnd==TK_UNBOUNDED&&pMWin->pOrderBy)
  ){
    windowCodeRowExprStep(pParse, p, pWInfo, regGosub, addrGosub);
    return;
  }

  /*
  ** Call windowCodeCacheStep() if there is a window function that requires
  ** that the entire partition be cached in a temp table before any rows
  ** are returned.
  */
  for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
    FuncDef *pFunc = pWin->pFunc;
    if( (pFunc->funcFlags & SQLITE_FUNC_WINDOW_SIZE)
     || (pFunc->xSFunc==nth_valueStepFunc)
     || (pFunc->xSFunc==first_valueStepFunc)
     || (pFunc->xSFunc==leadStepFunc)
     || (pFunc->xSFunc==lagStepFunc)
    ){
      windowCodeCacheStep(pParse, p, pWInfo, regGosub, addrGosub);
      return;
    }
  }


  windowCodeDefaultStep(pParse, p, pWInfo, regGosub, addrGosub);
}








|











|
>







 







|







 







|







 







|







 







|







 







>
>
>







 







|







 







>
>
>







 







|







 







<
>
|
|
|
<
<
|
|
<
<
<
<
|
<
<
|
<
<
<
<
<
|
<
<
<
<
<
|
<
<
|
|
<
<
<
<
<
<
<
<
<
<
|
<
<
|
|
<
<
<
<
<
<
<
<
<
<
|
|
<



|





|







 







>







 







|







 







>







 







>
>
>
>
>







 







|



|







 







>


|

|







 







|







 







>





|





|







 







|







 







|












>






<
|
|
|
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<


|
<
>
|
|
<
>




<
|







 







<
|

|
<













>



22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
..
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
..
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
...
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
...
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
...
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
...
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
...
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
...
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
...
299
300
301
302
303
304
305

306
307
308
309


310
311




312


313





314





315


316
317










318


319
320










321
322

323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
...
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
...
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
...
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
...
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
...
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
...
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
...
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
...
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
....
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
....
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658

1659
1660
1661
1662



















1663



























1664
1665
1666

1667
1668
1669

1670
1671
1672
1673
1674

1675
1676
1677
1678
1679
1680
1681
1682
....
1683
1684
1685
1686
1687
1688
1689

1690
1691
1692

1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
  i64 *p = (i64*)sqlite3_aggregate_context(pCtx, sizeof(*p));
  if( p ) (*p)++;
}
static void row_numberInvFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void row_numberValueFunc(sqlite3_context *pCtx){
  i64 *p = (i64*)sqlite3_aggregate_context(pCtx, sizeof(*p));
  sqlite3_result_int64(pCtx, (p ? *p : 0));
}

/*
** Context object type used by rank(), dense_rank(), percent_rank() and
** cume_dist().
*/
struct CallCount {
  i64 nValue;
  i64 nStep;
  i64 nTotal;
};

................................................................................
  int nArg,
  sqlite3_value **apArg
){
  struct CallCount *p;
  p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
  if( p ) p->nStep = 1;
}
static void dense_rankInvFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void dense_rankValueFunc(sqlite3_context *pCtx){
  struct CallCount *p;
................................................................................
  if( p ){
    p->nStep++;
    if( p->nValue==0 ){
      p->nValue = p->nStep;
    }
  }
}
static void rankInvFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void rankValueFunc(sqlite3_context *pCtx){
  struct CallCount *p;
................................................................................
    }
    p->nStep++;
    if( p->nValue==0 ){
      p->nValue = p->nStep;
    }
  }
}
static void percent_rankInvFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void percent_rankValueFunc(sqlite3_context *pCtx){
  struct CallCount *p;
................................................................................
  if( p ){
    if( p->nTotal==0 ){
      p->nTotal = sqlite3_value_int64(apArg[0]);
    }
    p->nStep++;
  }
}
static void cume_distInvFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void cume_distValueFunc(sqlite3_context *pCtx){
  struct CallCount *p;
................................................................................
  p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
  if( p ){
    double r = (double)(p->nStep) / (double)(p->nTotal);
    sqlite3_result_double(pCtx, r);
  }
}

/*
** Context object for ntile() window function.
*/
struct NtileCtx {
  i64 nTotal;                     /* Total rows in partition */
  i64 nParam;                     /* Parameter passed to ntile(N) */
  i64 iRow;                       /* Current row */
};

/*
................................................................................
            pCtx, "argument of ntile must be a positive integer", -1
        );
      }
    }
    p->iRow++;
  }
}
static void ntileInvFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
}
static void ntileValueFunc(sqlite3_context *pCtx){
  struct NtileCtx *p;
................................................................................
      }else{
        sqlite3_result_int64(pCtx, 1 + nLarge + (iRow-iSmall)/nSize);
      }
    }
  }
}

/*
** Context object for last_value() window function.
*/
struct LastValueCtx {
  sqlite3_value *pVal;
  int nVal;
};

/*
** Implementation of last_value().
................................................................................
  p = (struct LastValueCtx *)sqlite3_aggregate_context(pCtx, sizeof(*p));
  if( p ){
    sqlite3_value_free(p->pVal);
    p->pVal = sqlite3_value_dup(apArg[0]);
    p->nVal++;
  }
}
static void last_valueInvFunc(
  sqlite3_context *pCtx, 
  int nArg,
  sqlite3_value **apArg
){
  struct LastValueCtx *p;
  p = (struct LastValueCtx *)sqlite3_aggregate_context(pCtx, sizeof(*p));
  if( p ){
................................................................................
  if( p && p->pVal ){
    sqlite3_result_value(pCtx, p->pVal);
    sqlite3_value_free(p->pVal);
    p->pVal = 0;
  }
}


/*
** No-op implementations of nth_value(), first_value(), lead() and lag().
** These are all implemented inline using VDBE instructions. 
*/


static void nth_valueStepFunc(sqlite3_context *pCtx, int n, sqlite3_value **a){}
static void nth_valueInvFunc(sqlite3_context *pCtx, int n, sqlite3_value **ap){}




static void nth_valueValueFunc(sqlite3_context *pCtx){}


static void first_valueStepFunc(sqlite3_context *p, int n, sqlite3_value **ap){}





static void first_valueInvFunc(sqlite3_context *p, int n, sqlite3_value **ap){}





static void first_valueValueFunc(sqlite3_context *pCtx){}


static void leadStepFunc(sqlite3_context *pCtx, int n, sqlite3_value **ap){}
static void leadInvFunc(sqlite3_context *pCtx, int n, sqlite3_value **ap){}










static void leadValueFunc(sqlite3_context *pCtx){}


static void lagStepFunc(sqlite3_context *pCtx, int n, sqlite3_value **ap){}
static void lagInvFunc(sqlite3_context *pCtx, int n, sqlite3_value **ap){}










static void lagValueFunc(sqlite3_context *pCtx){}


#define WINDOWFUNC(name,nArg,extra) {                                      \
  nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0,                      \
  name ## StepFunc, name ## ValueFunc, name ## ValueFunc,                  \
  name ## InvFunc, #name                                               \
}

#define WINDOWFUNCF(name,nArg,extra) {                                     \
  nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0,                      \
  name ## StepFunc, name ## FinalizeFunc, name ## ValueFunc,               \
  name ## InvFunc, #name                                               \
}

/*
** Register those built-in window functions that are not also aggregates.
*/
void sqlite3WindowFunctions(void){
  static FuncDef aWindowFuncs[] = {
................................................................................
      sqlite3ExprDelete(db, pWin->pEnd);
      pWin->pStart = pWin->pEnd = 0;
      pWin->eType = TK_RANGE;
      pWin->eStart = TK_UNBOUNDED;
      pWin->eEnd = TK_CURRENT;
    }
  }
  pWin->pFunc = pFunc;
}

typedef struct WindowRewrite WindowRewrite;
struct WindowRewrite {
  Window *pWin;
  ExprList *pSub;
};
................................................................................
    case TK_FUNCTION:
      if( pExpr->pWin==0 ){
        break;
      }else{
        Window *pWin;
        for(pWin=p->pWin; pWin; pWin=pWin->pNextWin){
          if( pExpr->pWin==pWin ){
            assert( pWin->pOwner==pExpr );
            return WRC_Prune;
          }
        }
      }
      /* Fall through.  */

    case TK_COLUMN: {
................................................................................

  return pWin;
}

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

/*
** Return 0 if the two window objects are identical, or non-zero otherwise.
................................................................................

  sqlite3VdbeAddOp2(v, OP_Integer, 0, regZero);
  sqlite3VdbeAddOp2(v, OP_MustBeInt, reg, sqlite3VdbeCurrentAddr(v)+2);
  sqlite3VdbeAddOp3(v, OP_Ge, regZero, sqlite3VdbeCurrentAddr(v)+2, reg);
  sqlite3VdbeAddOp2(v, OP_Halt, SQLITE_ERROR, OE_Abort);
  sqlite3VdbeAppendP4(v, (void*)azErr[bEnd], P4_STATIC);
}

static int windowArgCount(Window *pWin){
  ExprList *pList = pWin->pOwner->x.pList;
  return (pList ? pList->nExpr : 0);
}

/*
** Generate VM code to invoke either xStep() (if bInverse is 0) or 
** xInverse (if bInverse is non-zero) for each window function in the 
** linked list starting at pMWin.
*/
static void windowAggStep(
................................................................................
  int regPartSize                 /* Register containing size of partition */
){
  Vdbe *v = sqlite3GetVdbe(pParse);
  Window *pWin;
  for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
    int flags = pWin->pFunc->funcFlags;
    int regArg;
    int nArg = windowArgCount(pWin);

    if( csr>=0 ){
      int i;
      for(i=0; i<nArg; i++){
        sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol+i, reg+i);
      }
      regArg = reg;
      if( flags & SQLITE_FUNC_WINDOW_SIZE ){
        if( nArg==0 ){
          regArg = regPartSize;
        }else{
................................................................................
           || pWin->pFunc->xSFunc==lagStepFunc 
    ){
      /* no-op */
    }else{
      int addrIf = 0;
      if( pWin->pFilter ){
        int regTmp;
        assert( nArg==pWin->pOwner->x.pList->nExpr );
        if( csr>0 ){
          regTmp = sqlite3GetTempReg(pParse);
          sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol+nArg,regTmp);
        }else{
          regTmp = regArg + nArg;
        }
        addrIf = sqlite3VdbeAddOp3(v, OP_IfNot, regTmp, 0, 1);
        if( csr>0 ){
          sqlite3ReleaseTempReg(pParse, regTmp);
        }
      }
      if( pWin->pFunc->funcFlags & SQLITE_FUNC_NEEDCOLL ){
................................................................................
        sqlite3VdbeAddOp1(v, OP_ResetSorter, pWin->csrApp);
      }
    }else if( pWin->regApp ){
    }else{
      if( bFinal==0 ){
        sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regResult);
      }
      sqlite3VdbeAddOp2(v, OP_AggFinal, pWin->regAccum, windowArgCount(pWin));
      sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
      if( bFinal ){
        sqlite3VdbeAddOp2(v, OP_Copy, pWin->regAccum, pWin->regResult);
        sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
      }else{
        sqlite3VdbeChangeP3(v, -1, pWin->regResult);
      }
................................................................................
      sqlite3VdbeAddOp3(v, OP_Gt, pWin->regApp+1, lbl, tmpReg);
      sqlite3VdbeAddOp3(v, OP_SeekRowid, csr, lbl, tmpReg);
      sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol, pWin->regResult);
      sqlite3VdbeResolveLabel(v, lbl);
      sqlite3ReleaseTempReg(pParse, tmpReg);
    }
    else if( pFunc->xSFunc==leadStepFunc || pFunc->xSFunc==lagStepFunc ){
      int nArg = pWin->pOwner->x.pList->nExpr;
      int iEph = pWin->iEphCsr;
      int csr = pWin->csrApp;
      int lbl = sqlite3VdbeMakeLabel(v);
      int tmpReg = sqlite3GetTempReg(pParse);

      if( nArg<3 ){
        sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regResult);
      }else{
        sqlite3VdbeAddOp3(v, OP_Column, iEph, pWin->iArgCol+2, pWin->regResult);
      }
      sqlite3VdbeAddOp2(v, OP_Rowid, iEph, tmpReg);
      if( nArg<2 ){
        int val = (pFunc->xSFunc==leadStepFunc ? 1 : -1);
        sqlite3VdbeAddOp2(v, OP_AddImm, tmpReg, val);
      }else{
        int op = (pFunc->xSFunc==leadStepFunc ? OP_Add : OP_Subtract);
        int tmpReg2 = sqlite3GetTempReg(pParse);
        sqlite3VdbeAddOp3(v, OP_Column, iEph, pWin->iArgCol+1, tmpReg2);
        sqlite3VdbeAddOp3(v, op, tmpReg2, tmpReg, tmpReg);
................................................................................
static int windowInitAccum(Parse *pParse, Window *pMWin){
  Vdbe *v = sqlite3GetVdbe(pParse);
  int regArg;
  int nArg = 0;
  Window *pWin;
  for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
    sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
    nArg = MAX(nArg, windowArgCount(pWin));
    if( pWin->pFunc->xSFunc==nth_valueStepFunc
     || pWin->pFunc->xSFunc==first_valueStepFunc 
    ){
      sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp);
      sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp+1);
    }
  }
................................................................................

  windowAggFinal(pParse, pMWin, 1);
  sqlite3VdbeAddOp2(v, OP_Rewind, pMWin->iEphCsr,sqlite3VdbeCurrentAddr(v)+3);
  sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
  sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, sqlite3VdbeCurrentAddr(v)-1);
}

Window *sqlite3WindowDup(sqlite3 *db, Expr *pOwner, Window *p){
  Window *pNew = 0;
  if( p ){
    pNew = sqlite3DbMallocZero(db, sizeof(Window));
    if( pNew ){
      pNew->pFilter = sqlite3ExprDup(db, p->pFilter, 0);
      pNew->pPartition = sqlite3ExprListDup(db, p->pPartition, 0);
      pNew->pOrderBy = sqlite3ExprListDup(db, p->pOrderBy, 0);
      pNew->eType = p->eType;
      pNew->eEnd = p->eEnd;
      pNew->eStart = p->eStart;
      pNew->pStart = sqlite3ExprDup(db, pNew->pStart, 0);
      pNew->pEnd = sqlite3ExprDup(db, pNew->pEnd, 0);
      pNew->pOwner = pOwner;
    }
  }
  return pNew;
}

/*

** sqlite3WhereBegin() has already been called for the SELECT statement 
** passed as the second argument when this function is invoked. It generates
** code to populate the Window.regResult register for each window function and
** invoke the sub-routine at instruction addrGosub once for each row.



















** This function calls sqlite3WhereEnd() before returning. 



























*/
void sqlite3WindowCodeStep(
  Parse *pParse,                  /* Parse context */

  Select *p,                      /* Rewritten SELECT statement */
  WhereInfo *pWInfo,              /* Context returned by sqlite3WhereBegin() */
  int regGosub,                   /* Register for OP_Gosub */

  int addrGosub                   /* OP_Gosub here to return each row */
){
  Window *pMWin = p->pWin;
  Window *pWin;


  /* Call windowCodeRowExprStep() for all window modes *except*:
  **
  **   RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
  **   RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
  **   RANGE BETWEEN CURRENT ROW AND CURRENT ROW
  **   ROWS  BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
  */
  if( (pMWin->eType==TK_ROWS 
................................................................................
   && (pMWin->eStart!=TK_UNBOUNDED||pMWin->eEnd!=TK_CURRENT||!pMWin->pOrderBy))
   || (pMWin->eStart==TK_CURRENT&&pMWin->eEnd==TK_UNBOUNDED&&pMWin->pOrderBy)
  ){
    windowCodeRowExprStep(pParse, p, pWInfo, regGosub, addrGosub);
    return;
  }


  /* Call windowCodeCacheStep() if there is a window function that requires
  ** that the entire partition be cached in a temp table before any rows
  ** are returned.  */

  for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
    FuncDef *pFunc = pWin->pFunc;
    if( (pFunc->funcFlags & SQLITE_FUNC_WINDOW_SIZE)
     || (pFunc->xSFunc==nth_valueStepFunc)
     || (pFunc->xSFunc==first_valueStepFunc)
     || (pFunc->xSFunc==leadStepFunc)
     || (pFunc->xSFunc==lagStepFunc)
    ){
      windowCodeCacheStep(pParse, p, pWInfo, regGosub, addrGosub);
      return;
    }
  }

  /* Otherwise, call windowCodeDefaultStep().  */
  windowCodeDefaultStep(pParse, p, pWInfo, regGosub, addrGosub);
}