SQLite

Check-in [c34f31dbd7]
Login

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

Overview
Comment:Fix problems with "RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING" window frames.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | exp-window-functions
Files: files | file ages | folders
SHA3-256: c34f31dbd79891249ee9485e91f6ea558ee1db62e04fb0fff2c051612b8fa5e7
User & Date: dan 2018-06-13 20:29:38.362
Context
2018-06-14
14:27
Improve comments and code legibility in new file window.c. (check-in: bb915854d4 user: dan tags: exp-window-functions)
2018-06-13
20:29
Fix problems with "RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING" window frames. (check-in: c34f31dbd7 user: dan tags: exp-window-functions)
2018-06-12
20:53
Fix another issue to do with window-functions in aggregate queries. (check-in: 6413e38a17 user: dan tags: exp-window-functions)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/window.c.
822
823
824
825
826
827
828

829
830
831
832
833
834
835
836
837
838
839
840






841
842
843
844









845
846
847
848
849
850
851
  }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;
}







static void windowAggInit(Parse *pParse, Window *pMWin){
  Window *pWin;
  for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
    Vdbe *v = sqlite3GetVdbe(pParse);









    FuncDef *p = pWin->pFunc;
    if( (p->funcFlags & SQLITE_FUNC_MINMAX) && pWin->eStart!=TK_UNBOUNDED ){
      ExprList *pList = pWin->pOwner->x.pList;
      KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pList, 0, 0);
      pWin->csrApp = pParse->nTab++;
      pWin->regApp = pParse->nMem+1;
      pParse->nMem += 3;







>












>
>
>
>
>
>
|

<
|
>
>
>
>
>
>
>
>
>







822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849

850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
  }else{
    sqlite3WindowDelete(pParse->db, pWin);
  }
}

/*
** 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->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;
}


/*
** This is called by code in select.c before it calls sqlite3WhereBegin()
** to begin iterating through the sub-query results. It is used to allocate
** and initialize registers and cursors used by sqlite3WindowCodeStep().
*/
void sqlite3WindowCodeInit(Parse *pParse, Window *pMWin){
  Window *pWin;

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

  for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
    FuncDef *p = pWin->pFunc;
    if( (p->funcFlags & SQLITE_FUNC_MINMAX) && pWin->eStart!=TK_UNBOUNDED ){
      ExprList *pList = pWin->pOwner->x.pList;
      KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pList, 0, 0);
      pWin->csrApp = pParse->nTab++;
      pWin->regApp = pParse->nMem+1;
      pParse->nMem += 3;
870
871
872
873
874
875
876
877

878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901

902
903




904
905
906
907
908
909
910
911
912














913
914
915
916
917
918
919
920
921
922
923
924
925
926
      assert( pMWin->iEphCsr );
      pWin->csrApp = pParse->nTab++;
      sqlite3VdbeAddOp2(v, OP_OpenDup, pWin->csrApp, pMWin->iEphCsr);
    }
  }
}

void sqlite3WindowCodeInit(Parse *pParse, Window *pWin){

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

static void windowCheckFrameValue(Parse *pParse, int reg, int bEnd){
  static const char *azErr[] = {
    "frame starting offset must be a non-negative integer",
    "frame ending offset must be a non-negative integer"
  };
  Vdbe *v = sqlite3GetVdbe(pParse);
  int regZero = ++pParse->nMem;

  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(
  Parse *pParse, 
  Window *pMWin, 
  int csr,
  int bInverse, 
  int reg,
  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;







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






|
<





>


>
>
>
>








|
>
>
>
>
>
>
>
>
>
>
>
>
>
>



|
|
|
|







885
886
887
888
889
890
891

892
893
894
895
896






897
898
899
900
901
902
903
904

905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
      assert( pMWin->iEphCsr );
      pWin->csrApp = pParse->nTab++;
      sqlite3VdbeAddOp2(v, OP_OpenDup, pWin->csrApp, pMWin->iEphCsr);
    }
  }
}


/*
** A "PRECEDING <expr>" (bEnd==0) or "FOLLOWING <expr>" (bEnd==1) has just 
** been evaluated and the result left in register reg. This function generates
** VM code to check that the value is a non-negative integer and throws
** an exception if it is not.






*/
static void windowCheckFrameValue(Parse *pParse, int reg, int bEnd){
  static const char *azErr[] = {
    "frame starting offset must be a non-negative integer",
    "frame ending offset must be a non-negative integer"
  };
  Vdbe *v = sqlite3GetVdbe(pParse);
  int regZero = sqlite3GetTempReg(pParse);

  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);
  sqlite3ReleaseTempReg(pParse, regZero);
}

/*
** Return the number of arguments passed to the window-function associated
** with the object passed as the only argument to this function.
*/
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. Or, for built-in window functions
** that do not use the standard function API, generate the required
** inline VM code.
**
** If argument csr is greater than or equal to 0, then argument reg is
** the first register in an array of registers guaranteed to be large
** enough to hold the array of arguments for each function. In this case
** the arguments are extracted from the current row of csr into the
** array of registers before invoking OP_AggStep.
**
** Or, if csr is less than zero, then the array of registers at reg is
** already populated with all columns from the current row of the sub-query.
**
** If argument regPartSize is non-zero, then it is a register containing the
** number of rows in the current partition.
*/
static void windowAggStep(
  Parse *pParse, 
  Window *pMWin,                  /* Linked list of window functions */
  int csr,                        /* Read arguments from this cursor */
  int bInverse,                   /* True to invoke xInverse instead of xStep */
  int reg,                        /* Array of registers */
  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;
993
994
995
996
997
998
999






1000
1001
1002
1003
1004
1005
1006
      sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
      sqlite3VdbeChangeP5(v, (u8)nArg);
      if( addrIf ) sqlite3VdbeJumpHere(v, addrIf);
    }
  }
}







static void windowAggFinal(Parse *pParse, Window *pMWin, int bFinal){
  Vdbe *v = sqlite3GetVdbe(pParse);
  Window *pWin;

  for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
    if( (pWin->pFunc->funcFlags & SQLITE_FUNC_MINMAX) 
     && pWin->eStart!=TK_UNBOUNDED 







>
>
>
>
>
>







1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
      sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
      sqlite3VdbeChangeP5(v, (u8)nArg);
      if( addrIf ) sqlite3VdbeJumpHere(v, addrIf);
    }
  }
}

/*
** Generate VM code to invoke either xValue() (bFinal==0) or xFinalize()
** (bFinal==1) for each window function in the linked list starting at
** pMWin. Or, for built-in window-functions that do not use the standard
** API, generate the equivalent VM code.
*/
static void windowAggFinal(Parse *pParse, Window *pMWin, int bFinal){
  Vdbe *v = sqlite3GetVdbe(pParse);
  Window *pWin;

  for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
    if( (pWin->pFunc->funcFlags & SQLITE_FUNC_MINMAX) 
     && pWin->eStart!=TK_UNBOUNDED 
1025
1026
1027
1028
1029
1030
1031





1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
      }else{
        sqlite3VdbeChangeP3(v, -1, pWin->regResult);
      }
    }
  }
}






static void windowPartitionCache(
  Parse *pParse,
  Select *p,
  WhereInfo *pWInfo,
  int regFlushPart,
  int lblFlushPart,
  int *pRegSize
){
  Window *pMWin = p->pWin;
  Vdbe *v = sqlite3GetVdbe(pParse);
  Window *pWin;
  int iSubCsr = p->pSrc->a[0].iCursor;
  int nSub = p->pSrc->a[0].pTab->nCol;
  int k;







>
>
>
>
>


|
|
|
|
|







1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
      }else{
        sqlite3VdbeChangeP3(v, -1, pWin->regResult);
      }
    }
  }
}

/*
** This function generates VM code to invoke the sub-routine at address
** lblFlushPart once for each partition with the entire partition cached in
** the Window.iEphCsr temp table.
*/
static void windowPartitionCache(
  Parse *pParse,
  Select *p,                      /* The rewritten SELECT statement */
  WhereInfo *pWInfo,              /* WhereInfo to call WhereEnd() on */
  int regFlushPart,               /* Register to use with Gosub lblFlushPart */
  int lblFlushPart,               /* Subroutine to Gosub to */
  int *pRegSize                   /* OUT: Register containing partition size */
){
  Window *pMWin = p->pWin;
  Vdbe *v = sqlite3GetVdbe(pParse);
  Window *pWin;
  int iSubCsr = p->pSrc->a[0].iCursor;
  int nSub = p->pSrc->a[0].pTab->nCol;
  int k;
1081
1082
1083
1084
1085
1086
1087













1088
1089
1090
1091
1092
1093
1094
  /* End of the input loop */
  sqlite3WhereEnd(pWInfo);

  /* Invoke "flush_partition" to deal with the final (or only) partition */
  sqlite3VdbeAddOp2(v, OP_Gosub, regFlushPart, lblFlushPart);
}














static void windowReturnOneRow(
  Parse *pParse,
  Window *pMWin,
  int regGosub,
  int addrGosub
){
  Vdbe *v = sqlite3GetVdbe(pParse);







>
>
>
>
>
>
>
>
>
>
>
>
>







1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
  /* End of the input loop */
  sqlite3WhereEnd(pWInfo);

  /* Invoke "flush_partition" to deal with the final (or only) partition */
  sqlite3VdbeAddOp2(v, OP_Gosub, regFlushPart, lblFlushPart);
}

/*
** Invoke the sub-routine at regGosub (generated by code in select.c) to
** return the current row of Window.iEphCsr. If all window functions are
** aggregate window functions that use the standard API, a single
** OP_Gosub instruction is all that this routine generates. Extra VM code
** for per-row processing is only generated for the following built-in window
** functions:
**
**   nth_value()
**   first_value()
**   lag()
**   lead()
*/
static void windowReturnOneRow(
  Parse *pParse,
  Window *pMWin,
  int regGosub,
  int addrGosub
){
  Vdbe *v = sqlite3GetVdbe(pParse);
1144
1145
1146
1147
1148
1149
1150















1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
      sqlite3VdbeResolveLabel(v, lbl);
      sqlite3ReleaseTempReg(pParse, tmpReg);
    }
  }
  sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
}
















static void windowReturnRows(
  Parse *pParse,
  Window *pMWin,
  int regCtr,
  int bFinal,
  int regGosub,
  int addrGosub,
  int regInvArg,
  int regInvSize
){
  int addr;
  Vdbe *v = sqlite3GetVdbe(pParse);
  windowAggFinal(pParse, pMWin, 0);
  addr = sqlite3VdbeAddOp3(v, OP_IfPos, regCtr, sqlite3VdbeCurrentAddr(v)+2 ,1);
  sqlite3VdbeAddOp2(v, OP_Goto, 0, 0);
  windowReturnOneRow(pParse, pMWin, regGosub, addrGosub);







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>


|
|
<
|
|
|
|







1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220

1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
      sqlite3VdbeResolveLabel(v, lbl);
      sqlite3ReleaseTempReg(pParse, tmpReg);
    }
  }
  sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
}

/*
** Invoke the code generated by windowReturnOneRow() and, optionally, the
** xInverse() function for each window function, for one or more rows
** from the Window.iEphCsr temp table. This routine generates VM code
** similar to:
**
**   while( regCtr>0 ){
**     regCtr--;
**     windowReturnOneRow()
**     if( bInverse ){
**       AggStep (xInverse)
**     }
**     Next (Window.iEphCsr)
**   }
*/
static void windowReturnRows(
  Parse *pParse,
  Window *pMWin,                  /* List of window functions */
  int regCtr,                     /* Register containing number of rows */

  int regGosub,                   /* Register for Gosub addrGosub */
  int addrGosub,                  /* Address of sub-routine for ReturnOneRow */
  int regInvArg,                  /* Array of registers for xInverse args */
  int regInvSize                  /* Register containing size of partition */
){
  int addr;
  Vdbe *v = sqlite3GetVdbe(pParse);
  windowAggFinal(pParse, pMWin, 0);
  addr = sqlite3VdbeAddOp3(v, OP_IfPos, regCtr, sqlite3VdbeCurrentAddr(v)+2 ,1);
  sqlite3VdbeAddOp2(v, OP_Goto, 0, 0);
  windowReturnOneRow(pParse, pMWin, regGosub, addrGosub);
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
  int addrIfPos1;
  int addrIfPos2;

  int regPeer = 0;                 /* Number of peers in current group */
  int regPeerVal = 0;              /* Array of values identifying peer group */
  int iPeer = 0;                   /* Column offset in eph-table of peer vals */
  int nPeerVal;                    /* Number of peer values */
  int bRange = 0;
  int regSize = 0;

  assert( pMWin->eStart==TK_PRECEDING 
       || pMWin->eStart==TK_CURRENT 
       || pMWin->eStart==TK_FOLLOWING 
       || pMWin->eStart==TK_UNBOUNDED 
  );
  assert( pMWin->eEnd==TK_FOLLOWING 
       || pMWin->eEnd==TK_CURRENT 
       || pMWin->eEnd==TK_UNBOUNDED 
       || pMWin->eEnd==TK_PRECEDING 
  );

  if( pMWin->eType==TK_RANGE 
   && pMWin->eStart==TK_CURRENT 
   && pMWin->eEnd==TK_UNBOUNDED
  ){
    bRange = 1;
  }

  /* Allocate register and label for the "flush_partition" sub-routine. */
  regFlushPart = ++pParse->nMem;
  lblFlushPart = sqlite3VdbeMakeLabel(v);
  lblFlushDone = sqlite3VdbeMakeLabel(v);

  regStart = ++pParse->nMem;
  regEnd = ++pParse->nMem;







<













<
<
<
<
<
<
<







1410
1411
1412
1413
1414
1415
1416

1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429







1430
1431
1432
1433
1434
1435
1436
  int addrIfPos1;
  int addrIfPos2;

  int regPeer = 0;                 /* Number of peers in current group */
  int regPeerVal = 0;              /* Array of values identifying peer group */
  int iPeer = 0;                   /* Column offset in eph-table of peer vals */
  int nPeerVal;                    /* Number of peer values */

  int regSize = 0;

  assert( pMWin->eStart==TK_PRECEDING 
       || pMWin->eStart==TK_CURRENT 
       || pMWin->eStart==TK_FOLLOWING 
       || pMWin->eStart==TK_UNBOUNDED 
  );
  assert( pMWin->eEnd==TK_FOLLOWING 
       || pMWin->eEnd==TK_CURRENT 
       || pMWin->eEnd==TK_UNBOUNDED 
       || pMWin->eEnd==TK_PRECEDING 
  );








  /* Allocate register and label for the "flush_partition" sub-routine. */
  regFlushPart = ++pParse->nMem;
  lblFlushPart = sqlite3VdbeMakeLabel(v);
  lblFlushDone = sqlite3VdbeMakeLabel(v);

  regStart = ++pParse->nMem;
  regEnd = ++pParse->nMem;
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519

  if( pMWin->eEnd==TK_FOLLOWING ){
    addrIfPos1 = sqlite3VdbeAddOp3(v, OP_IfPos, regEnd, 0 , 1);
  }
  if( pMWin->eStart==TK_FOLLOWING ){
    addrIfPos2 = sqlite3VdbeAddOp3(v, OP_IfPos, regStart, 0 , 1);
  }
  if( bRange ){
    assert( pMWin->eStart==TK_CURRENT && pMWin->pOrderBy );
    regPeer = ++pParse->nMem;
    regPeerVal = pParse->nMem+1;
    iPeer = pMWin->nBufferCol + (pMWin->pPartition?pMWin->pPartition->nExpr:0);
    nPeerVal = pMWin->pOrderBy->nExpr;
    pParse->nMem += (2 * nPeerVal);
    for(k=0; k<nPeerVal; k++){
      sqlite3VdbeAddOp3(v, OP_Column, pMWin->iEphCsr, iPeer+k, regPeerVal+k);
    }
    sqlite3VdbeAddOp2(v, OP_Integer, 0, regPeer);
  }

  windowAggFinal(pParse, pMWin, 0);
  if( bRange ){
    sqlite3VdbeAddOp2(v, OP_AddImm, regPeer, 1);
  }
  windowReturnOneRow(pParse, pMWin, regGosub, addrGosub);
  sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, sqlite3VdbeCurrentAddr(v)+2);
  sqlite3VdbeAddOp2(v, OP_Goto, 0, lblFlushDone);
  if( bRange ){
    KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pMWin->pOrderBy,0,0);
    int addrJump = sqlite3VdbeCurrentAddr(v)-4;
    for(k=0; k<nPeerVal; k++){
      int iOut = regPeerVal + nPeerVal + k;
      sqlite3VdbeAddOp3(v, OP_Column, pMWin->iEphCsr, iPeer+k, iOut);
    }
    sqlite3VdbeAddOp3(v, OP_Compare, regPeerVal, regPeerVal+nPeerVal, nPeerVal);
    sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
    addr = sqlite3VdbeCurrentAddr(v)+1;
    sqlite3VdbeAddOp3(v, OP_Jump, addr, addrJump, addr);
  }
  if( pMWin->eStart==TK_FOLLOWING ){
    sqlite3VdbeJumpHere(v, addrIfPos2);
  }

  if( pMWin->eStart==TK_CURRENT 
   || pMWin->eStart==TK_PRECEDING 
   || pMWin->eStart==TK_FOLLOWING 
  ){
    int addrJumpHere = 0;
    if( pMWin->eStart==TK_PRECEDING ){
      addrJumpHere = sqlite3VdbeAddOp3(v, OP_IfPos, regStart, 0 , 1);
    }
    if( bRange ){
      sqlite3VdbeAddOp3(v, OP_IfPos, regPeer, sqlite3VdbeCurrentAddr(v)+2, 1);
      addrJumpHere = sqlite3VdbeAddOp0(v, OP_Goto);
    }
    sqlite3VdbeAddOp2(v, OP_Next, csrStart, sqlite3VdbeCurrentAddr(v)+1);
    windowAggStep(pParse, pMWin, csrStart, 1, regArg, regSize);
    if( bRange ){
      sqlite3VdbeAddOp2(v, OP_Goto, 0, addrJumpHere-1);
    }
    if( addrJumpHere ){
      sqlite3VdbeJumpHere(v, addrJumpHere);
    }
  }
  if( pMWin->eEnd==TK_FOLLOWING ){
    sqlite3VdbeJumpHere(v, addrIfPos1);
  }







<
<
<
<
<
<
<
<
<
<
<
<
<

<
<
<



<
<
<
<
<
<
<
<
<
<
<
<












<
<
<
<


<
<
<







1510
1511
1512
1513
1514
1515
1516













1517



1518
1519
1520












1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532




1533
1534



1535
1536
1537
1538
1539
1540
1541

  if( pMWin->eEnd==TK_FOLLOWING ){
    addrIfPos1 = sqlite3VdbeAddOp3(v, OP_IfPos, regEnd, 0 , 1);
  }
  if( pMWin->eStart==TK_FOLLOWING ){
    addrIfPos2 = sqlite3VdbeAddOp3(v, OP_IfPos, regStart, 0 , 1);
  }













  windowAggFinal(pParse, pMWin, 0);



  windowReturnOneRow(pParse, pMWin, regGosub, addrGosub);
  sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, sqlite3VdbeCurrentAddr(v)+2);
  sqlite3VdbeAddOp2(v, OP_Goto, 0, lblFlushDone);












  if( pMWin->eStart==TK_FOLLOWING ){
    sqlite3VdbeJumpHere(v, addrIfPos2);
  }

  if( pMWin->eStart==TK_CURRENT 
   || pMWin->eStart==TK_PRECEDING 
   || pMWin->eStart==TK_FOLLOWING 
  ){
    int addrJumpHere = 0;
    if( pMWin->eStart==TK_PRECEDING ){
      addrJumpHere = sqlite3VdbeAddOp3(v, OP_IfPos, regStart, 0 , 1);
    }




    sqlite3VdbeAddOp2(v, OP_Next, csrStart, sqlite3VdbeCurrentAddr(v)+1);
    windowAggStep(pParse, pMWin, csrStart, 1, regArg, regSize);



    if( addrJumpHere ){
      sqlite3VdbeJumpHere(v, addrJumpHere);
    }
  }
  if( pMWin->eEnd==TK_FOLLOWING ){
    sqlite3VdbeJumpHere(v, addrIfPos1);
  }
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592


1593
1594
1595
1596

1597
1598


1599
1600
1601
1602
1603
1604
1605
**
**     ResetSorter (csr)
**     Return
**
** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
** RANGE BETWEEN CURRENT ROW AND CURRENT ROW 
**
**   TODO.
*/
static void windowCodeCacheStep(
  Parse *pParse, 
  Select *p,
  WhereInfo *pWInfo,
  int regGosub, 
  int addrGosub
){
  Window *pMWin = p->pWin;
  Vdbe *v = sqlite3GetVdbe(pParse);
  Window *pWin;
  int k;
  int addr;
  ExprList *pPart = pMWin->pPartition;
  ExprList *pOrderBy = pMWin->pOrderBy;
  int nPeer = pOrderBy->nExpr;
  int regNewPeer;

  int addrGoto;                   /* Address of Goto used to jump flush_par.. */
  int addrRewind;                 /* Address of Rewind that starts loop */
  int regFlushPart;
  int lblFlushPart;
  int csrLead;
  int regCtr;
  int regArg;                     /* Register array to martial function args */
  int regSize;
  int nArg;



  assert( (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_CURRENT) 
       || (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_UNBOUNDED) 
       || (pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_CURRENT) 

  );



  regNewPeer = pParse->nMem+1;
  pParse->nMem += nPeer;

  /* Allocate register and label for the "flush_partition" sub-routine. */
  regFlushPart = ++pParse->nMem;
  lblFlushPart = sqlite3VdbeMakeLabel(v);








<
<



















|







>
>




>


>
>







1579
1580
1581
1582
1583
1584
1585


1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
**
**     ResetSorter (csr)
**     Return
**
** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
** RANGE BETWEEN CURRENT ROW AND CURRENT ROW 


*/
static void windowCodeCacheStep(
  Parse *pParse, 
  Select *p,
  WhereInfo *pWInfo,
  int regGosub, 
  int addrGosub
){
  Window *pMWin = p->pWin;
  Vdbe *v = sqlite3GetVdbe(pParse);
  Window *pWin;
  int k;
  int addr;
  ExprList *pPart = pMWin->pPartition;
  ExprList *pOrderBy = pMWin->pOrderBy;
  int nPeer = pOrderBy->nExpr;
  int regNewPeer;

  int addrGoto;                   /* Address of Goto used to jump flush_par.. */
  int addrNext;                   /* Jump here for next iteration of loop */
  int regFlushPart;
  int lblFlushPart;
  int csrLead;
  int regCtr;
  int regArg;                     /* Register array to martial function args */
  int regSize;
  int nArg;
  int bReverse;
  int lblEmpty;

  assert( (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_CURRENT) 
       || (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_UNBOUNDED) 
       || (pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_CURRENT) 
       || (pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_UNBOUNDED) 
  );

  lblEmpty = sqlite3VdbeMakeLabel(v);
  bReverse = (pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_UNBOUNDED);
  regNewPeer = pParse->nMem+1;
  pParse->nMem += nPeer;

  /* Allocate register and label for the "flush_partition" sub-routine. */
  regFlushPart = ++pParse->nMem;
  lblFlushPart = sqlite3VdbeMakeLabel(v);

1614
1615
1616
1617
1618
1619
1620
1621
1622
1623








1624
1625
1626
1627
1628
1629
1630
1631
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
  sqlite3VdbeAddOp2(v, OP_Once, 0, sqlite3VdbeCurrentAddr(v)+2);
  sqlite3VdbeAddOp2(v, OP_OpenDup, csrLead, pMWin->iEphCsr);

  /* Initialize the accumulator register for each window function to NULL */
  regArg = windowInitAccum(pParse, pMWin);

  sqlite3VdbeAddOp2(v, OP_Integer, 0, regCtr);
  addrRewind = sqlite3VdbeAddOp1(v, OP_Rewind, csrLead);
  sqlite3VdbeAddOp1(v, OP_Rewind, pMWin->iEphCsr);









  if( pOrderBy && pMWin->eEnd==TK_CURRENT ){
    int bCurrent = (pMWin->eEnd==TK_CURRENT && pMWin->eStart==TK_CURRENT);
    int addrJump = 0;             /* Address of OP_Jump below */
    if( pMWin->eType==TK_RANGE ){
      int iOff = pMWin->nBufferCol + (pPart ? pPart->nExpr : 0);
      int regPeer = pMWin->regPart + (pPart ? pPart->nExpr : 0);
      KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pOrderBy, 0, 0);
      for(k=0; k<nPeer; k++){
        sqlite3VdbeAddOp3(v, OP_Column, csrLead, iOff+k, regNewPeer+k);
      }
      addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPeer, regPeer, nPeer);
      sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
      addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);
      sqlite3VdbeAddOp3(v, OP_Copy, regNewPeer, regPeer, nPeer-1);
    }

    windowReturnRows(pParse, pMWin, regCtr, 0, regGosub, addrGosub, 
        (bCurrent ? regArg : 0), (bCurrent ? regSize : 0)
    );
    if( addrJump ) sqlite3VdbeJumpHere(v, addrJump);
  }


  windowAggStep(pParse, pMWin, csrLead, 0, regArg, regSize);

  sqlite3VdbeAddOp2(v, OP_AddImm, regCtr, 1);
  sqlite3VdbeAddOp2(v, OP_Next, csrLead, addrRewind+2);

  windowReturnRows(pParse, pMWin, regCtr, 1, regGosub, addrGosub, 0, 0);

  sqlite3VdbeJumpHere(v, addrRewind);
  sqlite3VdbeJumpHere(v, addrRewind+1);
  sqlite3VdbeAddOp1(v, OP_ResetSorter, pMWin->iEphCsr);
  sqlite3VdbeAddOp1(v, OP_Return, regFlushPart);

  /* Jump to here to skip over flush_partition */
  sqlite3VdbeJumpHere(v, addrGoto);
}








|
|

>
>
>
>
>
>
>
>
|
|














|





>
|
>

|

|

|
<







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
  sqlite3VdbeAddOp2(v, OP_Once, 0, sqlite3VdbeCurrentAddr(v)+2);
  sqlite3VdbeAddOp2(v, OP_OpenDup, csrLead, pMWin->iEphCsr);

  /* Initialize the accumulator register for each window function to NULL */
  regArg = windowInitAccum(pParse, pMWin);

  sqlite3VdbeAddOp2(v, OP_Integer, 0, regCtr);
  sqlite3VdbeAddOp2(v, OP_Rewind, csrLead, lblEmpty);
  sqlite3VdbeAddOp2(v, OP_Rewind, pMWin->iEphCsr, lblEmpty);

  if( bReverse ){
    int addr = sqlite3VdbeCurrentAddr(v);
    windowAggStep(pParse, pMWin, csrLead, 0, regArg, regSize);
    sqlite3VdbeAddOp2(v, OP_Next, csrLead, addr);
    sqlite3VdbeAddOp2(v, OP_Rewind, csrLead, lblEmpty);
  }
  addrNext = sqlite3VdbeCurrentAddr(v);

  if( pOrderBy && (pMWin->eEnd==TK_CURRENT || pMWin->eStart==TK_CURRENT) ){
    int bCurrent = (pMWin->eStart==TK_CURRENT);
    int addrJump = 0;             /* Address of OP_Jump below */
    if( pMWin->eType==TK_RANGE ){
      int iOff = pMWin->nBufferCol + (pPart ? pPart->nExpr : 0);
      int regPeer = pMWin->regPart + (pPart ? pPart->nExpr : 0);
      KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pOrderBy, 0, 0);
      for(k=0; k<nPeer; k++){
        sqlite3VdbeAddOp3(v, OP_Column, csrLead, iOff+k, regNewPeer+k);
      }
      addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPeer, regPeer, nPeer);
      sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
      addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);
      sqlite3VdbeAddOp3(v, OP_Copy, regNewPeer, regPeer, nPeer-1);
    }

    windowReturnRows(pParse, pMWin, regCtr, regGosub, addrGosub, 
        (bCurrent ? regArg : 0), (bCurrent ? regSize : 0)
    );
    if( addrJump ) sqlite3VdbeJumpHere(v, addrJump);
  }

  if( bReverse==0 ){
    windowAggStep(pParse, pMWin, csrLead, 0, regArg, regSize);
  }
  sqlite3VdbeAddOp2(v, OP_AddImm, regCtr, 1);
  sqlite3VdbeAddOp2(v, OP_Next, csrLead, addrNext);

  windowReturnRows(pParse, pMWin, regCtr, regGosub, addrGosub, 0, 0);

  sqlite3VdbeResolveLabel(v, lblEmpty);

  sqlite3VdbeAddOp1(v, OP_ResetSorter, pMWin->iEphCsr);
  sqlite3VdbeAddOp1(v, OP_Return, regFlushPart);

  /* Jump to here to skip over flush_partition */
  sqlite3VdbeJumpHere(v, addrGoto);
}

1801
1802
1803
1804
1805
1806
1807





1808
1809
1810
1811
1812
1813
1814

  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);







>
>
>
>
>







1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853

  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);
}

/*
** Allocate and return a duplicate of the Window object indicated by the
** third argument. Set the Window.pOwner field of the new object to
** pOwner.
*/
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);
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856


1857
1858


1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874

1875



1876
1877
1878


  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);
}










|

|

|
<
<
<


|
<


|
>
>
|
|
>
>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
>
|
>
>
>
|
|
|
>
>
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885



1886
1887
1888

1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
  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;
  ExprList *pOrderBy = pMWin->pOrderBy;

  /* Call windowCodeRowExprStep() for all "ROWS" window modes except:
  **
  **   ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW



  */
  if( (pMWin->eType==TK_ROWS 
   && (pMWin->eStart!=TK_UNBOUNDED || pMWin->eEnd!=TK_CURRENT || !pOrderBy))

  ){
    windowCodeRowExprStep(pParse, p, pWInfo, regGosub, addrGosub);
  }else{
    Window *pWin;
    int bCache = 0;

    if( pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_UNBOUNDED && pOrderBy ){
      bCache = 1;
    }else{
      /* 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)
          ){
          bCache = 1;
          break;
        }
      }
    }

    /* Otherwise, call windowCodeDefaultStep().  */
    if( bCache ){
      windowCodeCacheStep(pParse, p, pWInfo, regGosub, addrGosub);
    }else{
      windowCodeDefaultStep(pParse, p, pWInfo, regGosub, addrGosub);
    }
  }
}

Changes to test/window4.tcl.
152
153
154
155
156
157
158






159
160
161
162
execsql_test 4.2 {
  SELECT max(b) OVER (ORDER BY max(c)) FROM ttt GROUP BY b;
}

execsql_test 4.3 {
  SELECT abs(max(b) OVER (ORDER BY b)) FROM ttt GROUP BY b;
}








finish_test








>
>
>
>
>
>




152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
execsql_test 4.2 {
  SELECT max(b) OVER (ORDER BY max(c)) FROM ttt GROUP BY b;
}

execsql_test 4.3 {
  SELECT abs(max(b) OVER (ORDER BY b)) FROM ttt GROUP BY b;
}

execsql_test 4.4 {
  SELECT sum(b) OVER (
    ORDER BY a RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
  ) FROM ttt;
}


finish_test

Changes to test/window4.test.
235
236
237
238
239
240
241






242
  SELECT max(b) OVER (ORDER BY max(c)) FROM ttt GROUP BY b;
} {1   2   3}

do_execsql_test 4.3 {
  SELECT abs(max(b) OVER (ORDER BY b)) FROM ttt GROUP BY b;
} {1   2   3}







finish_test







>
>
>
>
>
>

235
236
237
238
239
240
241
242
243
244
245
246
247
248
  SELECT max(b) OVER (ORDER BY max(c)) FROM ttt GROUP BY b;
} {1   2   3}

do_execsql_test 4.3 {
  SELECT abs(max(b) OVER (ORDER BY b)) FROM ttt GROUP BY b;
} {1   2   3}

do_execsql_test 4.4 {
  SELECT sum(b) OVER (
    ORDER BY a RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
  ) FROM ttt;
} {18   17   15   12   11   9   6   5   3}

finish_test