Index: ext/fts3/fts3.c ================================================================== --- ext/fts3/fts3.c +++ ext/fts3/fts3.c @@ -2064,11 +2064,41 @@ char *aOut; int bFirstOut = 0; *paOut = 0; *pnOut = 0; - aOut = sqlite3_malloc(n1+n2); + + /* Allocate space for the output. Both the input and output doclists + ** are delta encoded. If they are in ascending order (bDescDoclist==0), + ** then the first docid in each list is simply encoded as a varint. For + ** each subsequent docid, the varint stored is the difference between the + ** current and previous docid (a positive number - since the list is in + ** ascending order). + ** + ** The first docid written to the output is therefore encoded using the + ** same number of bytes as it is in whichever of the input lists it is + ** read from. And each subsequent docid read from the same input list + ** consumes either the same or less bytes as it did in the input (since + ** the difference between it and the previous value in the output must + ** be a positive value less than or equal to the delta value read from + ** the input list). The same argument applies to all but the first docid + ** read from the 'other' list. And to the contents of all position lists + ** that will be copied and merged from the input to the output. + ** + ** However, if the first docid copied to the output is a negative number, + ** then the encoding of the first docid from the 'other' input list may + ** be larger in the output than it was in the input (since the delta value + ** may be a larger positive integer than the actual docid). + ** + ** The space required to store the output is therefore the sum of the + ** sizes of the two inputs, plus enough space for exactly one of the input + ** docids to grow. + ** + ** A symetric argument may be made if the doclists are in descending + ** order. + */ + aOut = sqlite3_malloc(n1+n2+FTS3_VARINT_MAX-1); if( !aOut ) return SQLITE_NOMEM; p = aOut; fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1); fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2); @@ -2091,10 +2121,11 @@ } } *paOut = aOut; *pnOut = (p-aOut); + assert( *pnOut<=n1+n2+FTS3_VARINT_MAX-1 ); return SQLITE_OK; } /* ** This function does a "phrase" merge of two doclists. In a phrase merge, Index: test/fts3sort.test ================================================================== --- test/fts3sort.test +++ test/fts3sort.test @@ -155,8 +155,26 @@ END; } {3 1} do_execsql_test 2.3 { SELECT docid FROM t2 WHERE t2 MATCH 'aa'; } {3 1} + +#------------------------------------------------------------------------- +# Test that ticket [56be976859] has been fixed. +# +do_execsql_test 3.1 { + CREATE VIRTUAL TABLE t3 USING fts4(x, order=DESC); + INSERT INTO t3(docid, x) VALUES(113382409004785664, 'aa'); + INSERT INTO t3(docid, x) VALUES(1, 'ab'); + SELECT rowid FROM t3 WHERE x MATCH 'a*' ORDER BY docid DESC; +} {113382409004785664 1} +do_execsql_test 3.2 { + CREATE VIRTUAL TABLE t4 USING fts4(x); + INSERT INTO t4(docid, x) VALUES(-113382409004785664, 'aa'); + INSERT INTO t4(docid, x) VALUES(1, 'ab'); + SELECT rowid FROM t4 WHERE x MATCH 'a*'; +} {-113382409004785664 1} + + finish_test