/ Check-in [07788c0f]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Allocate the correct size for the output buffer in fts3DoclistOrMerge(). Fix for [56be976859].
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 07788c0f7f3740c1c280f6ce4dc68401c30bae6e
User & Date: dan 2011-09-13 19:08:43
References
2011-09-14
11:16 Closed ticket [56be9768]: Buffer overrun in FTS prefix queries plus 2 other changes artifact: e4256312 user: dan
Context
2011-09-14
13:23
Remove code from vdbesort.c that was made unreachable by the recent sqlite3VdbeRecordUnpack() optimizations. check-in: 607aba6c user: drh tags: trunk
2011-09-13
19:08
Allocate the correct size for the output buffer in fts3DoclistOrMerge(). Fix for [56be976859]. check-in: 07788c0f user: dan tags: trunk
2011-09-11
10:14
Cleanup pdb/ilk files generated by the MSVC makefile. check-in: a9db247b user: mistachkin tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/fts3/fts3.c.

2062
2063
2064
2065
2066
2067
2068






























2069
2070
2071
2072
2073
2074
2075
2076
....
2089
2090
2091
2092
2093
2094
2095

2096
2097
2098
2099
2100
2101
2102
  char *p2 = a2;
  char *p;
  char *aOut;
  int bFirstOut = 0;

  *paOut = 0;
  *pnOut = 0;






























  aOut = sqlite3_malloc(n1+n2);
  if( !aOut ) return SQLITE_NOMEM;

  p = aOut;
  fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1);
  fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2);
  while( p1 || p2 ){
    sqlite3_int64 iDiff = DOCID_CMP(i1, i2);
................................................................................
      fts3PoslistCopy(&p, &p2);
      fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);
    }
  }

  *paOut = aOut;
  *pnOut = (p-aOut);

  return SQLITE_OK;
}

/*
** This function does a "phrase" merge of two doclists. In a phrase merge,
** the output contains a copy of each position from the right-hand input
** doclist for which there is a position in the left-hand input doclist







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







 







>







2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
....
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
  char *p2 = a2;
  char *p;
  char *aOut;
  int bFirstOut = 0;

  *paOut = 0;
  *pnOut = 0;

  /* 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);
  while( p1 || p2 ){
    sqlite3_int64 iDiff = DOCID_CMP(i1, i2);
................................................................................
      fts3PoslistCopy(&p, &p2);
      fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);
    }
  }

  *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,
** the output contains a copy of each position from the right-hand input
** doclist for which there is a position in the left-hand input doclist

Changes to test/fts3sort.test.

153
154
155
156
157
158
159


















160
161
162
    INSERT INTO t2 VALUES('cc aa');
    SELECT docid FROM t2 WHERE t2 MATCH 'aa';
  END;
} {3 1}
do_execsql_test 2.3 {
  SELECT docid FROM t2 WHERE t2 MATCH 'aa';
} {3 1}



















finish_test








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



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
    INSERT INTO t2 VALUES('cc aa');
    SELECT docid FROM t2 WHERE t2 MATCH 'aa';
  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