Debian Codegraph @

ext/misc/series.c

raw
1 /*
2 ** 2015-08-18, 2023-04-28
3 **
4 ** The author disclaims copyright to this source code. In place of
5 ** a legal notice, here is a blessing:
6 **
7 ** May you do good and not evil.
8 ** May you find forgiveness for yourself and forgive others.
9 ** May you share freely, never taking more than you give.
10 **
11 *************************************************************************
12 **
13 ** This file demonstrates how to create a table-valued-function using
14 ** a virtual table. This demo implements the generate_series() function
15 ** which gives the same results as the eponymous function in PostgreSQL,
16 ** within the limitation that its arguments are signed 64-bit integers.
17 **
18 ** Considering its equivalents to generate_series(start,stop,step): A
19 ** value V[n] sequence is produced for integer n ascending from 0 where
20 ** ( V[n] == start + n * step && sgn(V[n] - stop) * sgn(step) >= 0 )
21 ** for each produced value (independent of production time ordering.)
22 **
23 ** All parameters must be either integer or convertable to integer.
24 ** The start parameter is required.
25 ** The stop parameter defaults to (1<<32)-1 (aka 4294967295 or 0xffffffff)
26 ** The step parameter defaults to 1 and 0 is treated as 1.
27 **
28 ** Examples:
29 **
30 ** SELECT * FROM generate_series(0,100,5);
31 **
32 ** The query above returns integers from 0 through 100 counting by steps
33 ** of 5. In other words, 0, 5, 10, 15, ..., 90, 95, 100. There are a total
34 ** of 21 rows.
35 **
36 ** SELECT * FROM generate_series(0,100);
37 **
38 ** Integers from 0 through 100 with a step size of 1. 101 rows.
39 **
40 ** SELECT * FROM generate_series(20) LIMIT 10;
41 **
42 ** Integers 20 through 29. 10 rows.
43 **
44 ** SELECT * FROM generate_series(0,-100,-5);
45 **
46 ** Integers 0 -5 -10 ... -100. 21 rows.
47 **
48 ** SELECT * FROM generate_series(0,-1);
49 **
50 ** Empty sequence.
51 **
52 ** HOW IT WORKS
53 **
54 ** The generate_series "function" is really a virtual table with the
55 ** following schema:
56 **
57 ** CREATE TABLE generate_series(
58 ** value,
59 ** start HIDDEN,
60 ** stop HIDDEN,
61 ** step HIDDEN
62 ** );
63 **
64 ** The virtual table also has a rowid which is an alias for the value.
65 **
66 ** Function arguments in queries against this virtual table are translated
67 ** into equality constraints against successive hidden columns. In other
68 ** words, the following pairs of queries are equivalent to each other:
69 **
70 ** SELECT * FROM generate_series(0,100,5);
71 ** SELECT * FROM generate_series WHERE start=0 AND stop=100 AND step=5;
72 **
73 ** SELECT * FROM generate_series(0,100);
74 ** SELECT * FROM generate_series WHERE start=0 AND stop=100;
75 **
76 ** SELECT * FROM generate_series(20) LIMIT 10;
77 ** SELECT * FROM generate_series WHERE start=20 LIMIT 10;
78 **
79 ** The generate_series virtual table implementation leaves the xCreate method
80 ** set to NULL. This means that it is not possible to do a CREATE VIRTUAL
81 ** TABLE command with "generate_series" as the USING argument. Instead, there
82 ** is a single generate_series virtual table that is always available without
83 ** having to be created first.
84 **
85 ** The xBestIndex method looks for equality constraints against the hidden
86 ** start, stop, and step columns, and if present, it uses those constraints
87 ** to bound the sequence of generated values. If the equality constraints
88 ** are missing, it uses 0 for start, 4294967295 for stop, and 1 for step.
89 ** xBestIndex returns a small cost when both start and stop are available,
90 ** and a very large cost if either start or stop are unavailable. This
91 ** encourages the query planner to order joins such that the bounds of the
92 ** series are well-defined.
93 **
94 ** Update on 2024-08-22:
95 ** xBestIndex now also looks for equality and inequality constraints against
96 ** the value column and uses those constraints as additional bounds against
97 ** the sequence range. Thus, a query like this:
98 **
99 ** SELECT value FROM generate_series($SA,$EA)
100 ** WHERE value BETWEEN $SB AND $EB;
101 **
102 ** Is logically the same as:
103 **
104 ** SELECT value FROM generate_series(max($SA,$SB),min($EA,$EB));
105 **
106 ** Constraints on the value column can server as substitutes for constraints
107 ** on the hidden start and stop columns. So, the following two queries
108 ** are equivalent:
109 **
110 ** SELECT value FROM generate_series($S,$E);
111 ** SELECT value FROM generate_series WHERE value BETWEEN $S and $E;
112 **
113 */
114 #include "sqlite3ext.h"
115 SQLITE_EXTENSION_INIT1
116 #include <assert.h>
117 #include <string.h>
118 #include <limits.h>
119 #include <math.h>
120
121 #ifndef SQLITE_OMIT_VIRTUALTABLE
122
123 /* series_cursor is a subclass of sqlite3_vtab_cursor which will
124 ** serve as the underlying representation of a cursor that scans
125 ** over rows of the result.
126 **
127 ** iOBase, iOTerm, and iOStep are the original values of the
128 ** start=, stop=, and step= constraints on the query. These are
129 ** the values reported by the start, stop, and step columns of the
130 ** virtual table.
131 **
132 ** iBase, iTerm, iStep, and bDescp are the actual values used to generate
133 ** the sequence. These might be different from the iOxxxx values.
134 ** For example in
135 **
136 ** SELECT value FROM generate_series(1,11,2)
137 ** WHERE value BETWEEN 4 AND 8;
138 **
139 ** The iOBase is 1, but the iBase is 5. iOTerm is 11 but iTerm is 7.
140 ** Another example:
141 **
142 ** SELECT value FROM generate_series(1,15,3) ORDER BY value DESC;
143 **
144 ** The cursor initialization for the above query is:
145 **
146 ** iOBase = 1 iBase = 13
147 ** iOTerm = 15 iTerm = 1
148 ** iOStep = 3 iStep = 3 bDesc = 1
149 **
150 ** The actual step size is unsigned so that can have a value of
151 ** +9223372036854775808 which is needed for querys like this:
152 **
153 ** SELECT value
154 ** FROM generate_series(9223372036854775807,
155 ** -9223372036854775808,
156 ** -9223372036854775808)
157 ** ORDER BY value ASC;
158 **
159 ** The setup for the previous query will be:
160 **
161 ** iOBase = 9223372036854775807 iBase = -1
162 ** iOTerm = -9223372036854775808 iTerm = 9223372036854775807
163 ** iOStep = -9223372036854775808 iStep = 9223372036854775808 bDesc = 0
164 */
165 typedef unsigned char u8;
166 typedef struct series_cursor series_cursor;
167 struct series_cursor {
168 sqlite3_vtab_cursor base; /* Base class - must be first */
169 sqlite3_int64 iOBase; /* Original starting value ("start") */
170 sqlite3_int64 iOTerm; /* Original terminal value ("stop") */
171 sqlite3_int64 iOStep; /* Original step value */
172 sqlite3_int64 iBase; /* Starting value to actually use */
173 sqlite3_int64 iTerm; /* Terminal value to actually use */
174 sqlite3_uint64 iStep; /* The step size */
175 sqlite3_int64 iValue; /* Current value */
176 u8 bDesc; /* iStep is really negative */
177 u8 bDone; /* True if stepped past last element */
178 };
179
180 /*
181 ** Computed the difference between two 64-bit signed integers using a
182 ** convoluted computation designed to work around the silly restriction
183 ** against signed integer overflow in C.
184 */
185 static sqlite3_uint64 span64(sqlite3_int64 a, sqlite3_int64 b){
186 assert( a>=b );
187 return (*(sqlite3_uint64*)&a) - (*(sqlite3_uint64*)&b);
188 }
189
190 /*
191 ** Add or substract an unsigned 64-bit integer from a signed 64-bit integer
192 ** and return the new signed 64-bit integer.
193 */
194 static sqlite3_int64 add64(sqlite3_int64 a, sqlite3_uint64 b){
195 sqlite3_uint64 x = *(sqlite3_uint64*)&a;
196 x += b;
197 return *(sqlite3_int64*)&x;
198 }
199 static sqlite3_int64 sub64(sqlite3_int64 a, sqlite3_uint64 b){
200 sqlite3_uint64 x = *(sqlite3_uint64*)&a;
201 x -= b;
202 return *(sqlite3_int64*)&x;
203 }
204
205 /*
206 ** The seriesConnect() method is invoked to create a new
207 ** series_vtab that describes the generate_series virtual table.
208 **
209 ** Think of this routine as the constructor for series_vtab objects.
210 **
211 ** All this routine needs to do is:
212 **
213 ** (1) Allocate the series_vtab object and initialize all fields.
214 **
215 ** (2) Tell SQLite (via the sqlite3_declare_vtab() interface) what the
216 ** result set of queries against generate_series will look like.
217 */
218 static int seriesConnect(
219 sqlite3 *db,
220 void *pUnused,
221 int argcUnused, const char *const*argvUnused,
222 sqlite3_vtab **ppVtab,
223 char **pzErrUnused
224 ){
225 sqlite3_vtab *pNew;
226 int rc;
227
228 /* Column numbers */
229 #define SERIES_COLUMN_ROWID (-1)
230 #define SERIES_COLUMN_VALUE 0
231 #define SERIES_COLUMN_START 1
232 #define SERIES_COLUMN_STOP 2
233 #define SERIES_COLUMN_STEP 3
234
235 (void)pUnused;
236 (void)argcUnused;
237 (void)argvUnused;
238 (void)pzErrUnused;
239 rc = sqlite3_declare_vtab(db,
240 "CREATE TABLE x(value,start hidden,stop hidden,step hidden)");
241 if( rc==SQLITE_OK ){
242 pNew = *ppVtab = sqlite3_malloc64( sizeof(*pNew) );
243 if( pNew==0 ) return SQLITE_NOMEM;
244 memset(pNew, 0, sizeof(*pNew));
245 sqlite3_vtab_config(db, SQLITE_VTAB_INNOCUOUS);
246 }
247 return rc;
248 }
249
250 /*
251 ** This method is the destructor for series_cursor objects.
252 */
253 static int seriesDisconnect(sqlite3_vtab *pVtab){
254 sqlite3_free(pVtab);
255 return SQLITE_OK;
256 }
257
258 /*
259 ** Constructor for a new series_cursor object.
260 */
261 static int seriesOpen(sqlite3_vtab *pUnused, sqlite3_vtab_cursor **ppCursor){
262 series_cursor *pCur;
263 (void)pUnused;
264 pCur = sqlite3_malloc64( sizeof(*pCur) );
265 if( pCur==0 ) return SQLITE_NOMEM;
266 memset(pCur, 0, sizeof(*pCur));
267 *ppCursor = &pCur->base;
268 return SQLITE_OK;
269 }
270
271 /*
272 ** Destructor for a series_cursor.
273 */
274 static int seriesClose(sqlite3_vtab_cursor *cur){
275 sqlite3_free(cur);
276 return SQLITE_OK;
277 }
278
279
280 /*
281 ** Advance a series_cursor to its next row of output.
282 */
283 static int seriesNext(sqlite3_vtab_cursor *cur){
284 series_cursor *pCur = (series_cursor*)cur;
285 if( pCur->iValue==pCur->iTerm ){
286 pCur->bDone = 1;
287 }else if( pCur->bDesc ){
288 pCur->iValue = sub64(pCur->iValue, pCur->iStep);
289 assert( pCur->iValue>=pCur->iTerm );
290 }else{
291 pCur->iValue = add64(pCur->iValue, pCur->iStep);
292 assert( pCur->iValue<=pCur->iTerm );
293 }
294 return SQLITE_OK;
295 }
296
297 /*
298 ** Return values of columns for the row at which the series_cursor
299 ** is currently pointing.
300 */
301 static int seriesColumn(
302 sqlite3_vtab_cursor *cur, /* The cursor */
303 sqlite3_context *ctx, /* First argument to sqlite3_result_...() */
304 int i /* Which column to return */
305 ){
306 series_cursor *pCur = (series_cursor*)cur;
307 sqlite3_int64 x = 0;
308 switch( i ){
309 case SERIES_COLUMN_START: x = pCur->iOBase; break;
310 case SERIES_COLUMN_STOP: x = pCur->iOTerm; break;
311 case SERIES_COLUMN_STEP: x = pCur->iOStep; break;
312 default: x = pCur->iValue; break;
313 }
314 sqlite3_result_int64(ctx, x);
315 return SQLITE_OK;
316 }
317
318 #ifndef LARGEST_UINT64
319 #define LARGEST_INT64 ((sqlite3_int64)0x7fffffffffffffffLL)
320 #define LARGEST_UINT64 ((sqlite3_uint64)0xffffffffffffffffULL)
321 #define SMALLEST_INT64 ((sqlite3_int64)0x8000000000000000LL)
322 #endif
323
324 /*
325 ** The rowid is the same as the value.
326 */
327 static int seriesRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
328 series_cursor *pCur = (series_cursor*)cur;
329 *pRowid = pCur->iValue;
330 return SQLITE_OK;
331 }
332
333 /*
334 ** Return TRUE if the cursor has been moved off of the last
335 ** row of output.
336 */
337 static int seriesEof(sqlite3_vtab_cursor *cur){
338 series_cursor *pCur = (series_cursor*)cur;
339 return pCur->bDone;
340 }
341
342 /* True to cause run-time checking of the start=, stop=, and/or step=
343 ** parameters. The only reason to do this is for testing the
344 ** constraint checking logic for virtual tables in the SQLite core.
345 */
346 #ifndef SQLITE_SERIES_CONSTRAINT_VERIFY
347 # define SQLITE_SERIES_CONSTRAINT_VERIFY 0
348 #endif
349
350 /*
351 ** Return the number of steps between pCur->iBase and pCur->iTerm if
352 ** the step width is pCur->iStep.
353 */
354 static sqlite3_uint64 seriesSteps(series_cursor *pCur){
355 if( pCur->bDesc ){
356 assert( pCur->iBase >= pCur->iTerm );
357 return span64(pCur->iBase, pCur->iTerm)/pCur->iStep;
358 }else{
359 assert( pCur->iBase <= pCur->iTerm );
360 return span64(pCur->iTerm, pCur->iBase)/pCur->iStep;
361 }
362 }
363
364 #if defined(SQLITE_ENABLE_MATH_FUNCTIONS) || defined(_WIN32)
365 /*
366 ** Case 1 (the most common case):
367 ** The standard math library is available so use ceil() and floor() from there.
368 */
369 static double seriesCeil(double r){ return ceil(r); }
370 static double seriesFloor(double r){ return floor(r); }
371 #elif defined(__GNUC__) && !defined(SQLITE_DISABLE_INTRINSIC)
372 /*
373 ** Case 2 (2nd most common): Use GCC/Clang builtins
374 */
375 static double seriesCeil(double r){ return __builtin_ceil(r); }
376 static double seriesFloor(double r){ return __builtin_floor(r); }
377 #else
378 /*
379 ** Case 3 (rarely happens): Use home-grown ceil() and floor() routines.
380 */
381 static double seriesCeil(double r){
382 sqlite3_int64 x;
383 if( r!=r ) return r;
384 if( r<=(-4503599627370496.0) ) return r;
385 if( r>=(+4503599627370496.0) ) return r;
386 x = (sqlite3_int64)r;
387 if( r==(double)x ) return r;
388 if( r>(double)x ) x++;
389 return (double)x;
390 }
391 static double seriesFloor(double r){
392 sqlite3_int64 x;
393 if( r!=r ) return r;
394 if( r<=(-4503599627370496.0) ) return r;
395 if( r>=(+4503599627370496.0) ) return r;
396 x = (sqlite3_int64)r;
397 if( r==(double)x ) return r;
398 if( r<(double)x ) x--;
399 return (double)x;
400 }
401 #endif
402
403 /*
404 ** This method is called to "rewind" the series_cursor object back
405 ** to the first row of output. This method is always called at least
406 ** once prior to any call to seriesColumn() or seriesRowid() or
407 ** seriesEof().
408 **
409 ** The query plan selected by seriesBestIndex is passed in the idxNum
410 ** parameter. (idxStr is not used in this implementation.) idxNum
411 ** is a bitmask showing which constraints are available:
412 **
413 ** 0x0001: start=VALUE
414 ** 0x0002: stop=VALUE
415 ** 0x0004: step=VALUE
416 ** 0x0008: descending order
417 ** 0x0010: ascending order
418 ** 0x0020: LIMIT VALUE
419 ** 0x0040: OFFSET VALUE
420 ** 0x0080: value=VALUE
421 ** 0x0100: value>=VALUE
422 ** 0x0200: value>VALUE
423 ** 0x1000: value<=VALUE
424 ** 0x2000: value<VALUE
425 **
426 ** This routine should initialize the cursor and position it so that it
427 ** is pointing at the first row, or pointing off the end of the table
428 ** (so that seriesEof() will return true) if the table is empty.
429 */
430 static int seriesFilter(
431 sqlite3_vtab_cursor *pVtabCursor,
432 int idxNum, const char *idxStrUnused,
433 int argc, sqlite3_value **argv
434 ){
435 series_cursor *pCur = (series_cursor *)pVtabCursor;
436 int iArg = 0; /* Arguments used so far */
437 int i; /* Loop counter */
438 sqlite3_int64 iMin = SMALLEST_INT64; /* Smallest allowed output value */
439 sqlite3_int64 iMax = LARGEST_INT64; /* Largest allowed output value */
440 sqlite3_int64 iLimit = 0; /* if >0, the value of the LIMIT */
441 sqlite3_int64 iOffset = 0; /* if >0, the value of the OFFSET */
442
443 (void)idxStrUnused;
444
445 /* If any constraints have a NULL value, then return no rows.
446 ** See ticket https://sqlite.org/src/info/fac496b61722daf2
447 */
448 for(i=0; i<argc; i++){
449 if( sqlite3_value_type(argv[i])==SQLITE_NULL ){
450 goto series_no_rows;
451 }
452 }
453
454 /* Capture the three HIDDEN parameters to the virtual table and insert
455 ** default values for any parameters that are omitted.
456 */
457 if( idxNum & 0x01 ){
458 pCur->iOBase = sqlite3_value_int64(argv[iArg++]);
459 }else{
460 pCur->iOBase = 0;
461 }
462 if( idxNum & 0x02 ){
463 pCur->iOTerm = sqlite3_value_int64(argv[iArg++]);
464 }else{
465 pCur->iOTerm = 0xffffffff;
466 }
467 if( idxNum & 0x04 ){
468 pCur->iOStep = sqlite3_value_int64(argv[iArg++]);
469 if( pCur->iOStep==0 ) pCur->iOStep = 1;
470 }else{
471 pCur->iOStep = 1;
472 }
473
474 /* If there are constraints on the value column but there are
475 ** no constraints on the start, stop, and step columns, then
476 ** initialize the default range to be the entire range of 64-bit signed
477 ** integers. This range will contracted by the value column constraints
478 ** further below.
479 */
480 if( (idxNum & 0x05)==0 && (idxNum & 0x0380)!=0 ){
481 pCur->iOBase = SMALLEST_INT64;
482 }
483 if( (idxNum & 0x06)==0 && (idxNum & 0x3080)!=0 ){
484 pCur->iOTerm = LARGEST_INT64;
485 }
486 pCur->iBase = pCur->iOBase;
487 pCur->iTerm = pCur->iOTerm;
488 if( pCur->iOStep>0 ){
489 pCur->iStep = pCur->iOStep;
490 }else if( pCur->iOStep>SMALLEST_INT64 ){
491 pCur->iStep = -pCur->iOStep;
492 }else{
493 pCur->iStep = LARGEST_INT64;
494 pCur->iStep++;
495 }
496 pCur->bDesc = pCur->iOStep<0;
497 if( pCur->bDesc==0 && pCur->iBase>pCur->iTerm ){
498 goto series_no_rows;
499 }
500 if( pCur->bDesc!=0 && pCur->iBase<pCur->iTerm ){
501 goto series_no_rows;
502 }
503
504 /* Extract the LIMIT and OFFSET values, but do not apply them yet.
505 ** The range must first be constrained by the limits on value.
506 */
507 if( idxNum & 0x20 ){
508 iLimit = sqlite3_value_int64(argv[iArg++]);
509 if( idxNum & 0x40 ){
510 iOffset = sqlite3_value_int64(argv[iArg++]);
511 }
512 }
513
514 /* Narrow the range of iMin and iMax (the minimum and maximum outputs)
515 ** based on equality and inequality constraints on the "value" column.
516 */
517 if( idxNum & 0x3380 ){
518 if( idxNum & 0x0080 ){ /* value=X */
519 if( sqlite3_value_numeric_type(argv[iArg])==SQLITE_FLOAT ){
520 double r = sqlite3_value_double(argv[iArg++]);
521 if( r==seriesCeil(r)
522 && r>=(double)SMALLEST_INT64
523 && r<=(double)LARGEST_INT64
524 ){
525 iMin = iMax = (sqlite3_int64)r;
526 }else{
527 goto series_no_rows;
528 }
529 }else{
530 iMin = iMax = sqlite3_value_int64(argv[iArg++]);
531 }
532 }else{
533 if( idxNum & 0x0300 ){ /* value>X or value>=X */
534 if( sqlite3_value_numeric_type(argv[iArg])==SQLITE_FLOAT ){
535 double r = sqlite3_value_double(argv[iArg++]);
536 if( r<(double)SMALLEST_INT64 ){
537 iMin = SMALLEST_INT64;
538 }else if( (idxNum & 0x0200)!=0 && r==seriesCeil(r) ){
539 iMin = (sqlite3_int64)seriesCeil(r)+1;
540 }else{
541 iMin = (sqlite3_int64)seriesCeil(r);
542 }
543 }else{
544 iMin = sqlite3_value_int64(argv[iArg++]);
545 if( (idxNum & 0x0200)!=0 ){
546 if( iMin==LARGEST_INT64 ){
547 goto series_no_rows;
548 }else{
549 iMin++;
550 }
551 }
552 }
553 }
554 if( idxNum & 0x3000 ){ /* value<X or value<=X */
555 if( sqlite3_value_numeric_type(argv[iArg])==SQLITE_FLOAT ){
556 double r = sqlite3_value_double(argv[iArg++]);
557 if( r>(double)LARGEST_INT64 ){
558 iMax = LARGEST_INT64;
559 }else if( (idxNum & 0x2000)!=0 && r==seriesFloor(r) ){
560 iMax = ((sqlite3_int64)r)-1;
561 }else{
562 iMax = (sqlite3_int64)seriesFloor(r);
563 }
564 }else{
565 iMax = sqlite3_value_int64(argv[iArg++]);
566 if( idxNum & 0x2000 ){
567 if( iMax==SMALLEST_INT64 ){
568 goto series_no_rows;
569 }else{
570 iMax--;
571 }
572 }
573 }
574 }
575 if( iMin>iMax ){
576 goto series_no_rows;
577 }
578 }
579
580 /* Try to reduce the range of values to be generated based on
581 ** constraints on the "value" column.
582 */
583 if( pCur->bDesc==0 ){
584 if( pCur->iBase<iMin ){
585 sqlite3_uint64 span = span64(iMin,pCur->iBase);
586 pCur->iBase = add64(pCur->iBase, (span/pCur->iStep)*pCur->iStep);
587 if( pCur->iBase<iMin ){
588 if( pCur->iBase > sub64(LARGEST_INT64, pCur->iStep) ){
589 goto series_no_rows;
590 }
591 pCur->iBase = add64(pCur->iBase, pCur->iStep);
592 }
593 }
594 if( pCur->iTerm>iMax ){
595 pCur->iTerm = iMax;
596 }
597 }else{
598 if( pCur->iBase>iMax ){
599 sqlite3_uint64 span = span64(pCur->iBase,iMax);
600 pCur->iBase = sub64(pCur->iBase, (span/pCur->iStep)*pCur->iStep);
601 if( pCur->iBase>iMax ){
602 if( pCur->iBase < add64(SMALLEST_INT64, pCur->iStep) ){
603 goto series_no_rows;
604 }
605 pCur->iBase = sub64(pCur->iBase, pCur->iStep);
606 }
607 }
608 if( pCur->iTerm<iMin ){
609 pCur->iTerm = iMin;
610 }
611 }
612 }
613
614 /* Adjust iTerm so that it is exactly the last value of the series.
615 */
616 if( pCur->bDesc==0 ){
617 if( pCur->iBase>pCur->iTerm ){
618 goto series_no_rows;
619 }
620 pCur->iTerm = sub64(pCur->iTerm,
621 span64(pCur->iTerm,pCur->iBase) % pCur->iStep);
622 }else{
623 if( pCur->iBase<pCur->iTerm ){
624 goto series_no_rows;
625 }
626 pCur->iTerm = add64(pCur->iTerm,
627 span64(pCur->iBase,pCur->iTerm) % pCur->iStep);
628 }
629
630 /* Transform the series generator to output values in the requested
631 ** order.
632 */
633 if( ((idxNum & 0x0008)!=0 && pCur->bDesc==0)
634 || ((idxNum & 0x0010)!=0 && pCur->bDesc!=0)
635 ){
636 sqlite3_int64 tmp = pCur->iBase;
637 pCur->iBase = pCur->iTerm;
638 pCur->iTerm = tmp;
639 pCur->bDesc = !pCur->bDesc;
640 }
641
642 /* Apply LIMIT and OFFSET constraints, if any */
643 assert( pCur->iStep!=0 );
644 if( idxNum & 0x20 ){
645 if( iOffset>0 ){
646 if( seriesSteps(pCur) < (sqlite3_uint64)iOffset ){
647 goto series_no_rows;
648 }else if( pCur->bDesc ){
649 pCur->iBase = sub64(pCur->iBase, pCur->iStep*iOffset);
650 }else{
651 pCur->iBase = add64(pCur->iBase, pCur->iStep*iOffset);
652 }
653 }
654 if( iLimit>=0 && seriesSteps(pCur) > (sqlite3_uint64)iLimit ){
655 pCur->iTerm = add64(pCur->iBase, (iLimit - 1)*pCur->iStep);
656 }
657 }
658 pCur->iValue = pCur->iBase;
659 pCur->bDone = 0;
660 return SQLITE_OK;
661
662 series_no_rows:
663 pCur->iBase = 0;
664 pCur->iTerm = 0;
665 pCur->iStep = 1;
666 pCur->bDesc = 0;
667 pCur->bDone = 1;
668 return SQLITE_OK;
669 }
670
671 /*
672 ** SQLite will invoke this method one or more times while planning a query
673 ** that uses the generate_series virtual table. This routine needs to create
674 ** a query plan for each invocation and compute an estimated cost for that
675 ** plan.
676 **
677 ** In this implementation idxNum is used to represent the
678 ** query plan. idxStr is unused.
679 **
680 ** The query plan is represented by bits in idxNum:
681 **
682 ** 0x0001 start = $num
683 ** 0x0002 stop = $num
684 ** 0x0004 step = $num
685 ** 0x0008 output is in descending order
686 ** 0x0010 output is in ascending order
687 ** 0x0020 LIMIT $num
688 ** 0x0040 OFFSET $num
689 ** 0x0080 value = $num
690 ** 0x0100 value >= $num
691 ** 0x0200 value > $num
692 ** 0x1000 value <= $num
693 ** 0x2000 value < $num
694 **
695 ** Only one of 0x0100 or 0x0200 will be returned. Similarly, only
696 ** one of 0x1000 or 0x2000 will be returned. If the 0x0080 is set, then
697 ** none of the 0xff00 bits will be set.
698 **
699 ** The order of parameters passed to xFilter is as follows:
700 **
701 ** * The argument to start= if bit 0x0001 is in the idxNum mask
702 ** * The argument to stop= if bit 0x0002 is in the idxNum mask
703 ** * The argument to step= if bit 0x0004 is in the idxNum mask
704 ** * The argument to LIMIT if bit 0x0020 is in the idxNum mask
705 ** * The argument to OFFSET if bit 0x0040 is in the idxNum mask
706 ** * The argument to value=, or value>= or value> if any of
707 ** bits 0x0380 are in the idxNum mask
708 ** * The argument to value<= or value< if either of bits 0x3000
709 ** are in the mask
710 **
711 */
712 static int seriesBestIndex(
713 sqlite3_vtab *pVTab,
714 sqlite3_index_info *pIdxInfo
715 ){
716 int i, j; /* Loop over constraints */
717 int idxNum = 0; /* The query plan bitmask */
718 #ifndef ZERO_ARGUMENT_GENERATE_SERIES
719 int bStartSeen = 0; /* EQ constraint seen on the START column */
720 #endif
721 int unusableMask = 0; /* Mask of unusable constraints */
722 int nArg = 0; /* Number of arguments that seriesFilter() expects */
723 int aIdx[7]; /* Constraints on start, stop, step, LIMIT, OFFSET,
724 ** and value. aIdx[5] covers value=, value>=, and
725 ** value>, aIdx[6] covers value<= and value< */
726 const struct sqlite3_index_constraint *pConstraint;
727
728 /* This implementation assumes that the start, stop, and step columns
729 ** are the last three columns in the virtual table. */
730 assert( SERIES_COLUMN_STOP == SERIES_COLUMN_START+1 );
731 assert( SERIES_COLUMN_STEP == SERIES_COLUMN_START+2 );
732
733 aIdx[0] = aIdx[1] = aIdx[2] = aIdx[3] = aIdx[4] = aIdx[5] = aIdx[6] = -1;
734 pConstraint = pIdxInfo->aConstraint;
735 for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
736 int iCol; /* 0 for start, 1 for stop, 2 for step */
737 int iMask; /* bitmask for those column */
738 int op = pConstraint->op;
739 if( op>=SQLITE_INDEX_CONSTRAINT_LIMIT
740 && op<=SQLITE_INDEX_CONSTRAINT_OFFSET
741 ){
742 if( pConstraint->usable==0 ){
743 /* do nothing */
744 }else if( op==SQLITE_INDEX_CONSTRAINT_LIMIT ){
745 aIdx[3] = i;
746 idxNum |= 0x20;
747 }else{
748 assert( op==SQLITE_INDEX_CONSTRAINT_OFFSET );
749 aIdx[4] = i;
750 idxNum |= 0x40;
751 }
752 continue;
753 }
754 if( pConstraint->iColumn<SERIES_COLUMN_START ){
755 if( (pConstraint->iColumn==SERIES_COLUMN_VALUE ||
756 pConstraint->iColumn==SERIES_COLUMN_ROWID)
757 && pConstraint->usable
758 ){
759 switch( op ){
760 case SQLITE_INDEX_CONSTRAINT_EQ:
761 case SQLITE_INDEX_CONSTRAINT_IS: {
762 idxNum |= 0x0080;
763 idxNum &= ~0x3300;
764 aIdx[5] = i;
765 aIdx[6] = -1;
766 #ifndef ZERO_ARGUMENT_GENERATE_SERIES
767 bStartSeen = 1;
768 #endif
769 break;
770 }
771 case SQLITE_INDEX_CONSTRAINT_GE: {
772 if( idxNum & 0x0080 ) break;
773 idxNum |= 0x0100;
774 idxNum &= ~0x0200;
775 aIdx[5] = i;
776 #ifndef ZERO_ARGUMENT_GENERATE_SERIES
777 bStartSeen = 1;
778 #endif
779 break;
780 }
781 case SQLITE_INDEX_CONSTRAINT_GT: {
782 if( idxNum & 0x0080 ) break;
783 idxNum |= 0x0200;
784 idxNum &= ~0x0100;
785 aIdx[5] = i;
786 #ifndef ZERO_ARGUMENT_GENERATE_SERIES
787 bStartSeen = 1;
788 #endif
789 break;
790 }
791 case SQLITE_INDEX_CONSTRAINT_LE: {
792 if( idxNum & 0x0080 ) break;
793 idxNum |= 0x1000;
794 idxNum &= ~0x2000;
795 aIdx[6] = i;
796 break;
797 }
798 case SQLITE_INDEX_CONSTRAINT_LT: {
799 if( idxNum & 0x0080 ) break;
800 idxNum |= 0x2000;
801 idxNum &= ~0x1000;
802 aIdx[6] = i;
803 break;
804 }
805 }
806 }
807 continue;
808 }
809 iCol = pConstraint->iColumn - SERIES_COLUMN_START;
810 assert( iCol>=0 && iCol<=2 );
811 iMask = 1 << iCol;
812 #ifndef ZERO_ARGUMENT_GENERATE_SERIES
813 if( iCol==0 && op==SQLITE_INDEX_CONSTRAINT_EQ ){
814 bStartSeen = 1;
815 }
816 #endif
817 if( pConstraint->usable==0 ){
818 unusableMask |= iMask;
819 continue;
820 }else if( op==SQLITE_INDEX_CONSTRAINT_EQ ){
821 idxNum |= iMask;
822 aIdx[iCol] = i;
823 }
824 }
825 if( aIdx[3]==0 ){
826 /* Ignore OFFSET if LIMIT is omitted */
827 idxNum &= ~0x60;
828 aIdx[4] = 0;
829 }
830 for(i=0; i<7; i++){
831 if( (j = aIdx[i])>=0 ){
832 pIdxInfo->aConstraintUsage[j].argvIndex = ++nArg;
833 pIdxInfo->aConstraintUsage[j].omit =
834 !SQLITE_SERIES_CONSTRAINT_VERIFY || i>=3;
835 }
836 }
837 /* The current generate_column() implementation requires at least one
838 ** argument (the START value). Legacy versions assumed START=0 if the
839 ** first argument was omitted. Compile with -DZERO_ARGUMENT_GENERATE_SERIES
840 ** to obtain the legacy behavior */
841 #ifndef ZERO_ARGUMENT_GENERATE_SERIES
842 if( !bStartSeen ){
843 sqlite3_free(pVTab->zErrMsg);
844 pVTab->zErrMsg = sqlite3_mprintf(
845 "first argument to \"generate_series()\" missing or unusable");
846 return SQLITE_ERROR;
847 }
848 #endif
849 if( (unusableMask & ~idxNum)!=0 ){
850 /* The start, stop, and step columns are inputs. Therefore if there
851 ** are unusable constraints on any of start, stop, or step then
852 ** this plan is unusable */
853 return SQLITE_CONSTRAINT;
854 }
855 if( (idxNum & 0x03)==0x03 ){
856 /* Both start= and stop= boundaries are available. This is the
857 ** the preferred case */
858 pIdxInfo->estimatedCost = (double)(2 - ((idxNum&4)!=0));
859 pIdxInfo->estimatedRows = 1000;
860 if( pIdxInfo->nOrderBy>=1 && pIdxInfo->aOrderBy[0].iColumn==0 ){
861 if( pIdxInfo->aOrderBy[0].desc ){
862 idxNum |= 0x08;
863 }else{
864 idxNum |= 0x10;
865 }
866 pIdxInfo->orderByConsumed = 1;
867 }
868 }else if( (idxNum & 0x21)==0x21 ){
869 /* We have start= and LIMIT */
870 pIdxInfo->estimatedRows = 2500;
871 }else{
872 /* If either boundary is missing, we have to generate a huge span
873 ** of numbers. Make this case very expensive so that the query
874 ** planner will work hard to avoid it. */
875 pIdxInfo->estimatedRows = 2147483647;
876 }
877 pIdxInfo->idxNum = idxNum;
878 #ifdef SQLITE_INDEX_SCAN_HEX
879 pIdxInfo->idxFlags = SQLITE_INDEX_SCAN_HEX;
880 #endif
881 return SQLITE_OK;
882 }
883
884 /*
885 ** This following structure defines all the methods for the
886 ** generate_series virtual table.
887 */
888 static sqlite3_module seriesModule = {
889 0, /* iVersion */
890 0, /* xCreate */
891 seriesConnect, /* xConnect */
892 seriesBestIndex, /* xBestIndex */
893 seriesDisconnect, /* xDisconnect */
894 0, /* xDestroy */
895 seriesOpen, /* xOpen - open a cursor */
896 seriesClose, /* xClose - close a cursor */
897 seriesFilter, /* xFilter - configure scan constraints */
898 seriesNext, /* xNext - advance a cursor */
899 seriesEof, /* xEof - check for end of scan */
900 seriesColumn, /* xColumn - read data */
901 seriesRowid, /* xRowid - read data */
902 0, /* xUpdate */
903 0, /* xBegin */
904 0, /* xSync */
905 0, /* xCommit */
906 0, /* xRollback */
907 0, /* xFindMethod */
908 0, /* xRename */
909 0, /* xSavepoint */
910 0, /* xRelease */
911 0, /* xRollbackTo */
912 0, /* xShadowName */
913 0 /* xIntegrity */
914 };
915
916 #endif /* SQLITE_OMIT_VIRTUALTABLE */
917
918 #ifdef _WIN32
919 __declspec(dllexport)
920 #endif
921 int sqlite3_series_init(
922 sqlite3 *db,
923 char **pzErrMsg,
924 const sqlite3_api_routines *pApi
925 ){
926 int rc = SQLITE_OK;
927 SQLITE_EXTENSION_INIT2(pApi);
928 #ifndef SQLITE_OMIT_VIRTUALTABLE
929 if( sqlite3_libversion_number()<3008012 && pzErrMsg!=0 ){
930 *pzErrMsg = sqlite3_mprintf(
931 "generate_series() requires SQLite 3.8.12 or later");
932 return SQLITE_ERROR;
933 }
934 rc = sqlite3_create_module(db, "generate_series", &seriesModule, 0);
935 #endif
936 return rc;
937 }