SQLite

series.c at [2f7eab38]
Login

File ext/misc/series.c artifact a6089b5e part of check-in 2f7eab38


     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    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
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
   100
   101
   102
   103
   104
   105
   106
   107
   108
   109
   110
   111
   112
   113
   114
   115
   116
   117
   118
   119
   120
   121
   122
   123
   124
   125
   126
   127
   128
   129
   130
   131
   132
   133
   134
   135
   136
   137
   138
   139
   140
   141
   142
   143
   144
   145
   146
   147
   148
   149
   150
   151
   152
   153
   154
   155
   156
   157
   158
   159
   160
   161
   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
   191
   192
   193
   194
   195
   196
   197
   198
   199
   200
   201
   202
   203
   204
   205
   206
   207
   208
   209
   210
   211
   212
   213
   214
   215
   216
   217
   218
   219
   220
   221
   222
   223
   224
   225
   226
   227
   228
   229
   230
   231
   232
   233
   234
   235
   236
   237
   238
   239
   240
   241
   242
   243
   244
   245
   246
   247
   248
   249
   250
   251
   252
   253
   254
   255
   256
   257
   258
   259
   260
   261
   262
   263
   264
   265
   266
   267
   268
   269
   270
   271
   272
   273
   274
   275
   276
   277
   278
   279
   280
   281
   282
   283
   284
   285
   286
   287
   288
   289
   290
   291
   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
   376
   377
   378
   379
   380
   381
   382
   383
   384
   385
   386
   387
   388
   389
   390
   391
   392
   393
   394
   395
   396
   397
   398
   399
   400
   401
   402
   403
   404
   405
   406
   407
   408
   409
   410
   411
   412
   413
   414
   415
   416
   417
   418
   419
   420
   421
   422
   423
   424
   425
   426
   427
   428
   429
   430
   431
   432
   433
   434
   435
   436
   437
   438
   439
   440
   441
   442
   443
   444
   445
   446
   447
   448
   449
   450
   451
   452
   453
   454
   455
   456
   457
   458
   459
   460
   461
   462
   463
   464
   465
   466
   467
   468
   469
   470
   471
   472
   473
   474
   475
   476
   477
   478
   479
   480
   481
   482
   483
   484
   485
   486
   487
   488
   489
   490
   491
   492
   493
   494
   495
   496
   497
   498
   499
   500
   501
   502
   503
   504
   505
   506
   507
   508
   509
   510
   511
   512
   513
   514
   515
   516
   517
   518
   519
   520
   521
   522
   523
   524
   525
   526
   527
   528
   529
   530
   531
   532
   533
   534
   535
   536
   537
   538
   539
   540
   541
   542
   543
   544
   545
   546
   547
   548
   549
   550
   551
   552
   553
   554
   555
   556
   557
   558
   559
   560
   561
   562
   563
   564
   565
   566
   567
   568
   569
   570
   571
   572
   573
   574
   575
   576
   577
   578
   579
   580
   581
   582
   583
   584
   585
   586
   587
   588
   589
   590
   591
   592
   593
   594
   595
   596
   597
   598
   599
   600
   601
   602
   603
   604
   605
   606
   607
   608
   609
   610
   611
   612
   613
   614
   615
   616
   617
   618
   619
   620
   621
   622
   623
   624
   625
   626
   627
   628
   629
   630
   631
   632
   633
   634
   635
   636
   637
   638
   639
   640
   641
   642
   643
   644
   645
   646
   647
   648
   649
   650
   651
   652
   653
   654
   655
   656
   657
   658
   659
   660
   661
   662
   663
   664
   665
   666
   667
   668
   669
   670
   671
   672
   673
   674
   675
   676
   677
   678
   679
   680
   681
   682
   683
   684
   685
   686
   687
   688
   689
   690
   691
   692
   693
   694
   695
   696
   697
   698
   699
   700
   701
   702
   703
   704
   705
   706
   707
   708
   709
   710
   711
   712
   713
   714
   715
   716
   717
   718
   719
   720
   721
   722
   723
   724
   725
   726
   727
   728
   729
   730
   731
   732
   733
   734
   735
   736
   737
   738
   739
   740
   741
   742
   743
   744
   745
   746
   747
   748
   749
   750
   751
   752
   753
   754
   755
   756
   757
   758
   759
   760
   761
   762
   763
   764
   765
   766
   767
   768
   769
   770
   771
   772
   773
   774
   775
   776
   777
   778
   779
   780
   781
   782
   783
   784
   785
   786
   787
   788
   789
   790
   791
   792
   793
   794
   795
   796
   797
   798
   799
   800
   801
   802
   803
   804
   805
   806
   807
   808
   809
   810
   811
   812
   813
   814
   815
   816
   817
   818
   819
   820
   821
   822
   823
   824
   825
   826
   827
   828
   829
   830
   831
   832
   833
/*
** 2015-08-18, 2023-04-28
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
**
** This file demonstrates how to create a table-valued-function using
** a virtual table.  This demo implements the generate_series() function
** which gives the same results as the eponymous function in PostgreSQL,
** within the limitation that its arguments are signed 64-bit integers.
**
** Considering its equivalents to generate_series(start,stop,step): A
** value V[n] sequence is produced for integer n ascending from 0 where
**  ( V[n] == start + n * step  &&  sgn(V[n] - stop) * sgn(step) >= 0 )
** for each produced value (independent of production time ordering.)
**
** All parameters must be either integer or convertable to integer.
** The start parameter is required.
** The stop parameter defaults to (1<<32)-1 (aka 4294967295 or 0xffffffff)
** The step parameter defaults to 1 and 0 is treated as 1.
**
** Examples:
**
**      SELECT * FROM generate_series(0,100,5);
**
** The query above returns integers from 0 through 100 counting by steps
** of 5.
**
**      SELECT * FROM generate_series(0,100);
**
** Integers from 0 through 100 with a step size of 1.
**
**      SELECT * FROM generate_series(20) LIMIT 10;
**
** Integers 20 through 29.
**
**      SELECT * FROM generate_series(0,-100,-5);
**
** Integers 0 -5 -10 ... -100.
**
**      SELECT * FROM generate_series(0,-1);
**
** Empty sequence.
**
** HOW IT WORKS
**
** The generate_series "function" is really a virtual table with the
** following schema:
**
**     CREATE TABLE generate_series(
**       value,
**       start HIDDEN,
**       stop HIDDEN,
**       step HIDDEN
**     );
**
** The virtual table also has a rowid, logically equivalent to n+1 where
** "n" is the ascending integer in the aforesaid production definition.
**
** Function arguments in queries against this virtual table are translated
** into equality constraints against successive hidden columns.  In other
** words, the following pairs of queries are equivalent to each other:
**
**    SELECT * FROM generate_series(0,100,5);
**    SELECT * FROM generate_series WHERE start=0 AND stop=100 AND step=5;
**
**    SELECT * FROM generate_series(0,100);
**    SELECT * FROM generate_series WHERE start=0 AND stop=100;
**
**    SELECT * FROM generate_series(20) LIMIT 10;
**    SELECT * FROM generate_series WHERE start=20 LIMIT 10;
**
** The generate_series virtual table implementation leaves the xCreate method
** set to NULL.  This means that it is not possible to do a CREATE VIRTUAL
** TABLE command with "generate_series" as the USING argument.  Instead, there
** is a single generate_series virtual table that is always available without
** having to be created first.
**
** The xBestIndex method looks for equality constraints against the hidden
** start, stop, and step columns, and if present, it uses those constraints
** to bound the sequence of generated values.  If the equality constraints
** are missing, it uses 0 for start, 4294967295 for stop, and 1 for step.
** xBestIndex returns a small cost when both start and stop are available,
** and a very large cost if either start or stop are unavailable.  This
** encourages the query planner to order joins such that the bounds of the
** series are well-defined.
**
** Update on 2024-08-22:
** xBestIndex now also looks for equality and inequality constraints against
** the value column and uses those constraints as additional bounds against
** the sequence range.  Thus, a query like this:
**
**     SELECT value FROM generate_series($SA,$EA)
**      WHERE value BETWEEN $SB AND $EB;
**
** Is logically the same as:
**
**     SELECT value FROM generate_series(max($SA,$SB),min($EA,$EB));
**
** Constraints on the value column can server as substitutes for constraints
** on the hidden start and stop columns.  So, the following two queries
** are equivalent:
**
**     SELECT value FROM generate_series($S,$E);
**     SELECT value FROM generate_series WHERE value BETWEEN $S and $E;
**
*/
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1
#include <assert.h>
#include <string.h>
#include <limits.h>

#ifndef SQLITE_OMIT_VIRTUALTABLE
/*
** Return that member of a generate_series(...) sequence whose 0-based
** index is ix. The 0th member is given by smBase. The sequence members
** progress per ix increment by smStep.
*/
static sqlite3_int64 genSeqMember(
  sqlite3_int64 smBase,
  sqlite3_int64 smStep,
  sqlite3_uint64 ix
){
  static const sqlite3_uint64 mxI64 =
      ((sqlite3_uint64)0x7fffffff)<<32 | 0xffffffff;
  if( ix>=mxI64 ){
    /* Get ix into signed i64 range. */
    ix -= mxI64;
    /* With 2's complement ALU, this next can be 1 step, but is split into
     * 2 for UBSAN's satisfaction (and hypothetical 1's complement ALUs.) */
    smBase += (mxI64/2) * smStep;
    smBase += (mxI64 - mxI64/2) * smStep;
  }
  /* Under UBSAN (or on 1's complement machines), must do this last term
   * in steps to avoid the dreaded (and harmless) signed multiply overlow. */
  if( ix>=2 ){
    sqlite3_int64 ix2 = (sqlite3_int64)ix/2;
    smBase += ix2*smStep;
    ix -= ix2;
  }
  return smBase + ((sqlite3_int64)ix)*smStep;
}

typedef unsigned char u8;

typedef struct SequenceSpec {
  sqlite3_int64 iOBase;        /* Original starting value ("start") */
  sqlite3_int64 iOTerm;        /* Original terminal value ("stop") */
  sqlite3_int64 iBase;         /* Starting value to actually use */
  sqlite3_int64 iTerm;         /* Terminal value to actually use */
  sqlite3_int64 iStep;         /* Increment ("step") */
  sqlite3_uint64 uSeqIndexMax; /* maximum sequence index (aka "n") */
  sqlite3_uint64 uSeqIndexNow; /* Current index during generation */
  sqlite3_int64 iValueNow;     /* Current value during generation */
  u8 isNotEOF;                 /* Sequence generation not exhausted */
  u8 isReversing;              /* Sequence is being reverse generated */
} SequenceSpec;

/*
** Prepare a SequenceSpec for use in generating an integer series
** given initialized iBase, iTerm and iStep values. Sequence is
** initialized per given isReversing. Other members are computed.
*/
static void setupSequence( SequenceSpec *pss ){
  int bSameSigns;
  pss->uSeqIndexMax = 0;
  pss->isNotEOF = 0;
  bSameSigns = (pss->iBase < 0)==(pss->iTerm < 0);
  if( pss->iTerm < pss->iBase ){
    sqlite3_uint64 nuspan = 0;
    if( bSameSigns ){
      nuspan = (sqlite3_uint64)(pss->iBase - pss->iTerm);
    }else{
      /* Under UBSAN (or on 1's complement machines), must do this in steps.
       * In this clause, iBase>=0 and iTerm<0 . */
      nuspan = 1;
      nuspan += pss->iBase;
      nuspan += -(pss->iTerm+1);
    }
    if( pss->iStep<0 ){
      pss->isNotEOF = 1;
      if( nuspan==ULONG_MAX ){
        pss->uSeqIndexMax = ( pss->iStep>LLONG_MIN )? nuspan/-pss->iStep : 1;
      }else if( pss->iStep>LLONG_MIN ){
        pss->uSeqIndexMax = nuspan/-pss->iStep;
      }
    }
  }else if( pss->iTerm > pss->iBase ){
    sqlite3_uint64 puspan = 0;
    if( bSameSigns ){
      puspan = (sqlite3_uint64)(pss->iTerm - pss->iBase);
    }else{
      /* Under UBSAN (or on 1's complement machines), must do this in steps.
       * In this clause, iTerm>=0 and iBase<0 . */
      puspan = 1;
      puspan += pss->iTerm;
      puspan += -(pss->iBase+1);
    }
    if( pss->iStep>0 ){
      pss->isNotEOF = 1;
      pss->uSeqIndexMax = puspan/pss->iStep;
    }
  }else if( pss->iTerm == pss->iBase ){
      pss->isNotEOF = 1;
      pss->uSeqIndexMax = 0;
  }
  pss->uSeqIndexNow = (pss->isReversing)? pss->uSeqIndexMax : 0;
  pss->iValueNow = (pss->isReversing)
    ? genSeqMember(pss->iBase, pss->iStep, pss->uSeqIndexMax)
    : pss->iBase;
}

/*
** Progress sequence generator to yield next value, if any.
** Leave its state to either yield next value or be at EOF.
** Return whether there is a next value, or 0 at EOF.
*/
static int progressSequence( SequenceSpec *pss ){
  if( !pss->isNotEOF ) return 0;
  if( pss->isReversing ){
    if( pss->uSeqIndexNow > 0 ){
      pss->uSeqIndexNow--;
      pss->iValueNow -= pss->iStep;
    }else{
      pss->isNotEOF = 0;
    }
  }else{
    if( pss->uSeqIndexNow < pss->uSeqIndexMax ){
      pss->uSeqIndexNow++;
      pss->iValueNow += pss->iStep;
    }else{
      pss->isNotEOF = 0;
    }
  }
  return pss->isNotEOF;
}

/* series_cursor is a subclass of sqlite3_vtab_cursor which will
** serve as the underlying representation of a cursor that scans
** over rows of the result
*/
typedef struct series_cursor series_cursor;
struct series_cursor {
  sqlite3_vtab_cursor base;  /* Base class - must be first */
  SequenceSpec ss;           /* (this) Derived class data */
};

/*
** The seriesConnect() method is invoked to create a new
** series_vtab that describes the generate_series virtual table.
**
** Think of this routine as the constructor for series_vtab objects.
**
** All this routine needs to do is:
**
**    (1) Allocate the series_vtab object and initialize all fields.
**
**    (2) Tell SQLite (via the sqlite3_declare_vtab() interface) what the
**        result set of queries against generate_series will look like.
*/
static int seriesConnect(
  sqlite3 *db,
  void *pUnused,
  int argcUnused, const char *const*argvUnused,
  sqlite3_vtab **ppVtab,
  char **pzErrUnused
){
  sqlite3_vtab *pNew;
  int rc;

/* Column numbers */
#define SERIES_COLUMN_VALUE 0
#define SERIES_COLUMN_START 1
#define SERIES_COLUMN_STOP  2
#define SERIES_COLUMN_STEP  3

  (void)pUnused;
  (void)argcUnused;
  (void)argvUnused;
  (void)pzErrUnused;
  rc = sqlite3_declare_vtab(db,
     "CREATE TABLE x(value,start hidden,stop hidden,step hidden)");
  if( rc==SQLITE_OK ){
    pNew = *ppVtab = sqlite3_malloc( sizeof(*pNew) );
    if( pNew==0 ) return SQLITE_NOMEM;
    memset(pNew, 0, sizeof(*pNew));
    sqlite3_vtab_config(db, SQLITE_VTAB_INNOCUOUS);
  }
  return rc;
}

/*
** This method is the destructor for series_cursor objects.
*/
static int seriesDisconnect(sqlite3_vtab *pVtab){
  sqlite3_free(pVtab);
  return SQLITE_OK;
}

/*
** Constructor for a new series_cursor object.
*/
static int seriesOpen(sqlite3_vtab *pUnused, sqlite3_vtab_cursor **ppCursor){
  series_cursor *pCur;
  (void)pUnused;
  pCur = sqlite3_malloc( sizeof(*pCur) );
  if( pCur==0 ) return SQLITE_NOMEM;
  memset(pCur, 0, sizeof(*pCur));
  *ppCursor = &pCur->base;
  return SQLITE_OK;
}

/*
** Destructor for a series_cursor.
*/
static int seriesClose(sqlite3_vtab_cursor *cur){
  sqlite3_free(cur);
  return SQLITE_OK;
}


/*
** Advance a series_cursor to its next row of output.
*/
static int seriesNext(sqlite3_vtab_cursor *cur){
  series_cursor *pCur = (series_cursor*)cur;
  progressSequence( & pCur->ss );
  return SQLITE_OK;
}

/*
** Return values of columns for the row at which the series_cursor
** is currently pointing.
*/
static int seriesColumn(
  sqlite3_vtab_cursor *cur,   /* The cursor */
  sqlite3_context *ctx,       /* First argument to sqlite3_result_...() */
  int i                       /* Which column to return */
){
  series_cursor *pCur = (series_cursor*)cur;
  sqlite3_int64 x = 0;
  switch( i ){
    case SERIES_COLUMN_START:  x = pCur->ss.iOBase;     break;
    case SERIES_COLUMN_STOP:   x = pCur->ss.iOTerm;     break;
    case SERIES_COLUMN_STEP:   x = pCur->ss.iStep;      break;
    default:                   x = pCur->ss.iValueNow;  break;
  }
  sqlite3_result_int64(ctx, x);
  return SQLITE_OK;
}

#ifndef LARGEST_UINT64
#define LARGEST_INT64  (0xffffffff|(((sqlite3_int64)0x7fffffff)<<32))
#define LARGEST_UINT64 (0xffffffff|(((sqlite3_uint64)0xffffffff)<<32))
#define SMALLEST_INT64 (((sqlite3_int64)-1) - LARGEST_INT64)
#endif

/*
** Return the rowid for the current row, logically equivalent to n+1 where
** "n" is the ascending integer in the aforesaid production definition.
*/
static int seriesRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
  series_cursor *pCur = (series_cursor*)cur;
  sqlite3_uint64 n = pCur->ss.uSeqIndexNow;
  *pRowid = (sqlite3_int64)((n<LARGEST_UINT64)? n+1 : 0);
  return SQLITE_OK;
}

/*
** Return TRUE if the cursor has been moved off of the last
** row of output.
*/
static int seriesEof(sqlite3_vtab_cursor *cur){
  series_cursor *pCur = (series_cursor*)cur;
  return !pCur->ss.isNotEOF;
}

/* True to cause run-time checking of the start=, stop=, and/or step=
** parameters.  The only reason to do this is for testing the
** constraint checking logic for virtual tables in the SQLite core.
*/
#ifndef SQLITE_SERIES_CONSTRAINT_VERIFY
# define SQLITE_SERIES_CONSTRAINT_VERIFY 0
#endif

/*
** This method is called to "rewind" the series_cursor object back
** to the first row of output.  This method is always called at least
** once prior to any call to seriesColumn() or seriesRowid() or
** seriesEof().
**
** The query plan selected by seriesBestIndex is passed in the idxNum
** parameter.  (idxStr is not used in this implementation.)  idxNum
** is a bitmask showing which constraints are available:
**
**   0x0001:    start=VALUE
**   0x0002:    stop=VALUE
**   0x0004:    step=VALUE
**   0x0008:    descending order
**   0x0010:    ascending order
**   0x0020:    LIMIT  VALUE
**   0x0040:    OFFSET  VALUE
**   0x0080:    value=VALUE
**   0x0100:    value>=VALUE
**   0x0200:    value>VALUE
**   0x1000:    value<=VALUE
**   0x2000:    value<VALUE
**
** This routine should initialize the cursor and position it so that it
** is pointing at the first row, or pointing off the end of the table
** (so that seriesEof() will return true) if the table is empty.
*/
static int seriesFilter(
  sqlite3_vtab_cursor *pVtabCursor,
  int idxNum, const char *idxStrUnused,
  int argc, sqlite3_value **argv
){
  series_cursor *pCur = (series_cursor *)pVtabCursor;
  int i = 0;
  int returnNoRows = 0;
  sqlite3_int64 iMin = SMALLEST_INT64;
  sqlite3_int64 iMax = LARGEST_INT64;
  sqlite3_int64 iLimit = 0;
  sqlite3_int64 iOffset = 0;

  (void)idxStrUnused;
  if( idxNum & 0x01 ){
    pCur->ss.iBase = sqlite3_value_int64(argv[i++]);
  }else{
    pCur->ss.iBase = 0;
  }
  if( idxNum & 0x02 ){
    pCur->ss.iTerm = sqlite3_value_int64(argv[i++]);
  }else{
    pCur->ss.iTerm = 0xffffffff;
  }
  if( idxNum & 0x04 ){
    pCur->ss.iStep = sqlite3_value_int64(argv[i++]);
    if( pCur->ss.iStep==0 ){
      pCur->ss.iStep = 1;
    }else if( pCur->ss.iStep<0 ){
      if( (idxNum & 0x10)==0 ) idxNum |= 0x08;
    }
  }else{
    pCur->ss.iStep = 1;
  }

  /* If there are constraints on the value column but there are
  ** no constraints on  the start, stop, and step columns, then
  ** initialize the default range to be the entire range of 64-bit signed
  ** integers.  This range will contracted by the value column constraints
  ** further below.
  */
  if( (idxNum & 0x05)==0 && (idxNum & 0x0380)!=0 ){
    pCur->ss.iBase = SMALLEST_INT64;
  }
  if( (idxNum & 0x06)==0 && (idxNum & 0x3080)!=0 ){
    pCur->ss.iTerm = LARGEST_INT64;
  }
  pCur->ss.iOBase = pCur->ss.iBase;
  pCur->ss.iOTerm = pCur->ss.iTerm;

  /* Extract the LIMIT and OFFSET values, but do not apply them yet.
  ** The range must first be constrained by the limits on value.
  */
  if( idxNum & 0x20 ){
    iLimit = sqlite3_value_int64(argv[i++]);
    if( idxNum & 0x40 ){
      iOffset = sqlite3_value_int64(argv[i++]);
    }
  }

  if( idxNum & 0x3380 ){
    /* Extract the maximum range of output values determined by
    ** constraints on the "value" column.
    */
    if( idxNum & 0x0080 ){
      iMin = iMax = sqlite3_value_int64(argv[i++]);
    }else{
      if( idxNum & 0x0300 ){
        iMin = sqlite3_value_int64(argv[i++]);
        if( idxNum & 0x0200 ){
          if( iMin==LARGEST_INT64 ){
            returnNoRows = 1;
          }else{
            iMin++;
          }
        }
      }
      if( idxNum & 0x3000 ){
        iMax = sqlite3_value_int64(argv[i++]);
        if( idxNum & 0x2000 ){
          if( iMax==SMALLEST_INT64 ){
            returnNoRows = 1;
          }else{
            iMax--;
          }
        }
      }
      if( iMin>iMax ){
        returnNoRows = 1;
      }
    }

    /* Try to reduce the range of values to be generated based on
    ** constraints on the "value" column.
    */
    if( pCur->ss.iStep>0 ){
      sqlite3_int64 szStep = pCur->ss.iStep;
      if( pCur->ss.iBase<iMin ){
        sqlite3_uint64 d = iMin - pCur->ss.iBase;
        pCur->ss.iBase += ((d+szStep-1)/szStep)*szStep;
      }
      if( pCur->ss.iTerm>iMax ){
        sqlite3_uint64 d = pCur->ss.iTerm - iMax;
        pCur->ss.iTerm -= ((d+szStep-1)/szStep)*szStep;
      }
    }else{
      sqlite3_int64 szStep = -pCur->ss.iStep;
      assert( szStep>0 );
      if( pCur->ss.iBase>iMax ){
        sqlite3_uint64 d = pCur->ss.iBase - iMax;
        pCur->ss.iBase -= ((d+szStep-1)/szStep)*szStep;
      }
      if( pCur->ss.iTerm<iMin ){
        sqlite3_uint64 d = iMin - pCur->ss.iTerm;
        pCur->ss.iTerm += ((d+szStep-1)/szStep)*szStep;
      }
    }
  }

  /* Apply LIMIT and OFFSET constraints, if any */
  if( idxNum & 0x20 ){
    if( iOffset>0 ){
      pCur->ss.iBase += pCur->ss.iStep*iOffset;
    }
    if( iLimit>=0 ){
      sqlite3_int64 iTerm;
      iTerm = pCur->ss.iBase + (iLimit - 1)*pCur->ss.iStep;
      if( pCur->ss.iStep<0 ){
        if( iTerm>pCur->ss.iTerm ) pCur->ss.iTerm = iTerm;
      }else{
        if( iTerm<pCur->ss.iTerm ) pCur->ss.iTerm = iTerm;
      }
    }
  }


  for(i=0; i<argc; i++){
    if( sqlite3_value_type(argv[i])==SQLITE_NULL ){
      /* If any of the constraints have a NULL value, then return no rows.
      ** See ticket https://www.sqlite.org/src/info/fac496b61722daf2 */
      returnNoRows = 1;
      break;
    }
  }
  if( returnNoRows ){
    pCur->ss.iBase = 1;
    pCur->ss.iTerm = 0;
    pCur->ss.iStep = 1;
  }
  if( idxNum & 0x08 ){
    pCur->ss.isReversing = pCur->ss.iStep > 0;
  }else{
    pCur->ss.isReversing = pCur->ss.iStep < 0;
  }
  setupSequence( &pCur->ss );
  return SQLITE_OK;
}

/*
** SQLite will invoke this method one or more times while planning a query
** that uses the generate_series virtual table.  This routine needs to create
** a query plan for each invocation and compute an estimated cost for that
** plan.
**
** In this implementation idxNum is used to represent the
** query plan.  idxStr is unused.
**
** The query plan is represented by bits in idxNum:
**
**   0x0001  start = $num
**   0x0002  stop = $num
**   0x0004  step = $num
**   0x0008  output is in descending order
**   0x0010  output is in ascending order
**   0x0020  LIMIT $num
**   0x0040  OFFSET $num
**   0x0080  value = $num
**   0x0100  value >= $num
**   0x0200  value > $num
**   0x1000  value <= $num
**   0x2000  value < $num
**
** Only one of 0x0100 or 0x0200 will be returned.  Similarly, only
** one of 0x1000 or 0x2000 will be returned.  If the 0x0080 is set, then
** none of the 0xff00 bits will be set.
**
** The order of parameters passed to xFilter is as follows:
**
**    * The argument to start= if bit 0x0001 is in the idxNum mask
**    * The argument to stop= if bit 0x0002 is in the idxNum mask
**    * The argument to step= if bit 0x0004 is in the idxNum mask
**    * The argument to LIMIT if bit 0x0020 is in the idxNum mask
**    * The argument to OFFSET if bit 0x0040 is in the idxNum mask
**    * The argument to value=, or value>= or value> if any of
**      bits 0x0380 are in the idxNum mask
**    * The argument to value<= or value< if either of bits 0x3000
**      are in the mask
**
*/
static int seriesBestIndex(
  sqlite3_vtab *pVTab,
  sqlite3_index_info *pIdxInfo
){
  int i, j;              /* Loop over constraints */
  int idxNum = 0;        /* The query plan bitmask */
#ifndef ZERO_ARGUMENT_GENERATE_SERIES
  int bStartSeen = 0;    /* EQ constraint seen on the START column */
#endif
  int unusableMask = 0;  /* Mask of unusable constraints */
  int nArg = 0;          /* Number of arguments that seriesFilter() expects */
  int aIdx[7];           /* Constraints on start, stop, step, LIMIT, OFFSET,
                         ** and value.  aIdx[5] covers value=, value>=, and
                         ** value>,  aIdx[6] covers value<= and value< */
  const struct sqlite3_index_constraint *pConstraint;

  /* This implementation assumes that the start, stop, and step columns
  ** are the last three columns in the virtual table. */
  assert( SERIES_COLUMN_STOP == SERIES_COLUMN_START+1 );
  assert( SERIES_COLUMN_STEP == SERIES_COLUMN_START+2 );

  aIdx[0] = aIdx[1] = aIdx[2] = aIdx[3] = aIdx[4] = aIdx[5] = aIdx[6] = -1;
  pConstraint = pIdxInfo->aConstraint;
  for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
    int iCol;    /* 0 for start, 1 for stop, 2 for step */
    int iMask;   /* bitmask for those column */
    int op = pConstraint->op;
    if( op>=SQLITE_INDEX_CONSTRAINT_LIMIT
     && op<=SQLITE_INDEX_CONSTRAINT_OFFSET
    ){
      if( pConstraint->usable==0 ){
        /* do nothing */
      }else if( op==SQLITE_INDEX_CONSTRAINT_LIMIT ){
        aIdx[3] = i;
        idxNum |= 0x20;
      }else{
        assert( op==SQLITE_INDEX_CONSTRAINT_OFFSET );
        aIdx[4] = i;
        idxNum |= 0x40;
      }
      continue;
    }
    if( pConstraint->iColumn==SERIES_COLUMN_VALUE ){
      switch( op ){
        case SQLITE_INDEX_CONSTRAINT_EQ:
        case SQLITE_INDEX_CONSTRAINT_IS: {
          idxNum |=  0x0080;
          idxNum &= ~0x3300;
          aIdx[5] = i;
          aIdx[6] = -1;
          bStartSeen = 1;
          break;
        }
        case SQLITE_INDEX_CONSTRAINT_GE: {
          if( idxNum & 0x0080 ) break;
          idxNum |=  0x0100;
          idxNum &= ~0x0200;
          aIdx[5] = i;
          bStartSeen = 1;
          break;
        }
        case SQLITE_INDEX_CONSTRAINT_GT: {
          if( idxNum & 0x0080 ) break;
          idxNum |=  0x0200;
          idxNum &= ~0x0100;
          aIdx[5] = i;
          bStartSeen = 1;
          break;
        }
        case SQLITE_INDEX_CONSTRAINT_LE: {
          if( idxNum & 0x0080 ) break;
          idxNum |=  0x1000;
          idxNum &= ~0x2000;
          aIdx[6] = i;
          break;
        }
        case SQLITE_INDEX_CONSTRAINT_LT: {
          if( idxNum & 0x0080 ) break;
          idxNum |=  0x2000;
          idxNum &= ~0x1000;
          aIdx[6] = i;
          break;
        }
      }
      continue;
    }
    iCol = pConstraint->iColumn - SERIES_COLUMN_START;
    assert( iCol>=0 && iCol<=2 );
    iMask = 1 << iCol;
#ifndef ZERO_ARGUMENT_GENERATE_SERIES
    if( iCol==0 && op==SQLITE_INDEX_CONSTRAINT_EQ ){
      bStartSeen = 1;
    }
#endif
    if( pConstraint->usable==0 ){
      unusableMask |=  iMask;
      continue;
    }else if( op==SQLITE_INDEX_CONSTRAINT_EQ ){
      idxNum |= iMask;
      aIdx[iCol] = i;
    }
  }
  if( aIdx[3]==0 ){
    /* Ignore OFFSET if LIMIT is omitted */
    idxNum &= ~0x60;
    aIdx[4] = 0;
  }
  for(i=0; i<7; i++){
    if( (j = aIdx[i])>=0 ){
      pIdxInfo->aConstraintUsage[j].argvIndex = ++nArg;
      pIdxInfo->aConstraintUsage[j].omit =
         !SQLITE_SERIES_CONSTRAINT_VERIFY || i>=3;
    }
  }
  /* The current generate_column() implementation requires at least one
  ** argument (the START value).  Legacy versions assumed START=0 if the
  ** first argument was omitted.  Compile with -DZERO_ARGUMENT_GENERATE_SERIES
  ** to obtain the legacy behavior */
#ifndef ZERO_ARGUMENT_GENERATE_SERIES
  if( !bStartSeen ){
    sqlite3_free(pVTab->zErrMsg);
    pVTab->zErrMsg = sqlite3_mprintf(
        "first argument to \"generate_series()\" missing or unusable");
    return SQLITE_ERROR;
  }
#endif
  if( (unusableMask & ~idxNum)!=0 ){
    /* The start, stop, and step columns are inputs.  Therefore if there
    ** are unusable constraints on any of start, stop, or step then
    ** this plan is unusable */
    return SQLITE_CONSTRAINT;
  }
  if( (idxNum & 0x03)==0x03 ){
    /* Both start= and stop= boundaries are available.  This is the 
    ** the preferred case */
    pIdxInfo->estimatedCost = (double)(2 - ((idxNum&4)!=0));
    pIdxInfo->estimatedRows = 1000;
    if( pIdxInfo->nOrderBy>=1 && pIdxInfo->aOrderBy[0].iColumn==0 ){
      if( pIdxInfo->aOrderBy[0].desc ){
        idxNum |= 0x08;
      }else{
        idxNum |= 0x10;
      }
      pIdxInfo->orderByConsumed = 1;
    }
  }else if( (idxNum & 0x21)==0x21 ){
    /* We have start= and LIMIT */
    pIdxInfo->estimatedRows = 2500;
  }else{
    /* If either boundary is missing, we have to generate a huge span
    ** of numbers.  Make this case very expensive so that the query
    ** planner will work hard to avoid it. */
    pIdxInfo->estimatedRows = 2147483647;
  }
  pIdxInfo->idxNum = idxNum;
#ifdef SQLITE_INDEX_SCAN_HEX
  pIdxInfo->idxFlags = SQLITE_INDEX_SCAN_HEX;
#endif
  return SQLITE_OK;
}

/*
** This following structure defines all the methods for the 
** generate_series virtual table.
*/
static sqlite3_module seriesModule = {
  0,                         /* iVersion */
  0,                         /* xCreate */
  seriesConnect,             /* xConnect */
  seriesBestIndex,           /* xBestIndex */
  seriesDisconnect,          /* xDisconnect */
  0,                         /* xDestroy */
  seriesOpen,                /* xOpen - open a cursor */
  seriesClose,               /* xClose - close a cursor */
  seriesFilter,              /* xFilter - configure scan constraints */
  seriesNext,                /* xNext - advance a cursor */
  seriesEof,                 /* xEof - check for end of scan */
  seriesColumn,              /* xColumn - read data */
  seriesRowid,               /* xRowid - read data */
  0,                         /* xUpdate */
  0,                         /* xBegin */
  0,                         /* xSync */
  0,                         /* xCommit */
  0,                         /* xRollback */
  0,                         /* xFindMethod */
  0,                         /* xRename */
  0,                         /* xSavepoint */
  0,                         /* xRelease */
  0,                         /* xRollbackTo */
  0,                         /* xShadowName */
  0                          /* xIntegrity */
};

#endif /* SQLITE_OMIT_VIRTUALTABLE */

#ifdef _WIN32
__declspec(dllexport)
#endif
int sqlite3_series_init(
  sqlite3 *db, 
  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  int rc = SQLITE_OK;
  SQLITE_EXTENSION_INIT2(pApi);
#ifndef SQLITE_OMIT_VIRTUALTABLE
  if( sqlite3_libversion_number()<3008012 && pzErrMsg!=0 ){
    *pzErrMsg = sqlite3_mprintf(
        "generate_series() requires SQLite 3.8.12 or later");
    return SQLITE_ERROR;
  }
  rc = sqlite3_create_module(db, "generate_series", &seriesModule, 0);
#endif
  return rc;
}