SQLite

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

** encourages the query planner to order joins such that the bounds of the
** series are well-defined.
*/
#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){
  if( ix>=(sqlite3_uint64)LLONG_MAX ){
    /* Get ix into signed i64 range. */
    ix -= (sqlite3_uint64)LLONG_MAX;
    smBase += LLONG_MAX * smStep;
  }
  return smBase + ((sqlite3_int64)ix)*smStep;
}

typedef unsigned char u8;

typedef struct SequenceSpec {
  sqlite3_int64 iBase;         /* Starting value ("start") */
  sqlite3_int64 iTerm;         /* Given terminal value ("stop") */
  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.
*/
void setupSequence( SequenceSpec *pss ){
  pss->uSeqIndexMax = 0;
  pss->isNotEOF = 0;
  if( pss->iTerm < pss->iBase ){
    sqlite3_uint64 nuspan = (sqlite3_uint64)(pss->iBase-pss->iTerm);
    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 = (sqlite3_uint64)(pss->iTerm-pss->iBase);
    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.
*/
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.

/*
** 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.iBase; break;
    case SERIES_COLUMN_STOP:   x = pCur->ss.iTerm; break;
    case SERIES_COLUMN_STEP:   x = pCur->ss.iStep;   break;
    default:                   x = pCur->ss.iValueNow;  break;
  }
  sqlite3_result_int64(ctx, x);
  return SQLITE_OK;
}

/*
** Return the rowid for the current row. In this implementation, the
** first row returned is assigned rowid value 1, and each subsequent
** row a value 1 more than that of the previous.
*/
static int seriesRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
  series_cursor *pCur = (series_cursor*)cur;
  *pRowid = ((sqlite3_int64)pCur->ss.uSeqIndexNow + 1);
  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:
**
**    1:    start=VALUE
**    2:    stop=VALUE
**    4:    step=VALUE
**
** Also, if bit 8 is set, that means that the series should be output
** in descending order rather than in ascending order.  If bit 16 is
** set, then output must appear in ascending order.
**
** 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;
  (void)idxStrUnused;
  if( idxNum & 1 ){
    pCur->ss.iBase = sqlite3_value_int64(argv[i++]);
  }else{
    pCur->ss.iBase = 0;
  }
  if( idxNum & 2 ){
    pCur->ss.iTerm = sqlite3_value_int64(argv[i++]);
  }else{
    pCur->ss.iTerm = 0xffffffff;
  }
  if( idxNum & 4 ){
    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 & 16)==0 ) idxNum |= 8;
    }
  }else{
    pCur->ss.iStep = 1;
  }
  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 */
      pCur->ss.iBase = 1;
      pCur->ss.iTerm = 0;
      pCur->ss.iStep = 1;
      break;
    }
  }
  if( idxNum & 8 ){

    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

.clone clone.db
.open clone.db
 SELECT max(seq) FROM sqlite_sequence;}]]
} {0 {t... done
done
2}}

# Verify that generate_series stays sane near 64-bit range boundaries.
# See overflow report at https://sqlite.org/forum/forumpost/5d34ce5280
do_test shell2-1.4.10 {
 set res [catchcmd :memory: [string trim {
 SELECT * FROM generate_series(9223372036854775807,9223372036854775807,1);
 SELECT * FROM generate_series(9223372036854775807,9223372036854775807,-1);
 SELECT avg(rowid),min(value),max(value) FROM generate_series(
  -9223372036854775808,9223372036854775807,1085102592571150095);
 SELECT * FROM generate_series(-9223372036854775808,9223372036854775807,
  9223372036854775807);
 SELECT value,rowid FROM generate_series(-4611686018427387904,
  4611686018427387904, 4611686018427387904) ORDER BY value DESC;
 SELECT * FROM generate_series(0,-2,-1);
 SELECT * FROM generate_series(0,-2);
 SELECT * FROM generate_series(0,2) LIMIT 3;}]]
} {0 {9223372036854775807
9223372036854775807
9.5|-9223372036854775808|9223372036854775807
-9223372036854775808
-1
9223372036854775806
4611686018427387904|3
0|2
-4611686018427387904|1
0
-1
-2
0
1
2}}

finish_test

} {1 {too many arguments on generate_series() - max 3}}

do_execsql_test tabfunc01-1.8 {
  SELECT * FROM generate_series(0,32,5) ORDER BY rowid DESC;
} {30 25 20 15 10 5 0}
do_execsql_test tabfunc01-1.9 {
  SELECT rowid, * FROM generate_series(0,32,5) ORDER BY value DESC;
} {7 30 6 25 5 20 4 15 3 10 2 5 1 0}
do_execsql_test tabfunc01-1.10 {
  SELECT rowid, * FROM generate_series(0,32,5) ORDER BY +value DESC;
} {7 30 6 25 5 20 4 15 3 10 2 5 1 0}

do_execsql_test tabfunc01-1.20 {
  CREATE VIEW v1(a,b) AS VALUES(1,2),(3,4);
  SELECT * FROM v1;