fts3.c
上传用户:sunhongbo
上传日期:2022-01-25
资源大小:3010k
文件大小:200k
源码类别:

数据库系统

开发平台:

C/C++

  1. /*
  2. ** 2006 Oct 10
  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 is an SQLite module implementing full-text search.
  14. */
  15. /*
  16. ** The code in this file is only compiled if:
  17. **
  18. **     * The FTS3 module is being built as an extension
  19. **       (in which case SQLITE_CORE is not defined), or
  20. **
  21. **     * The FTS3 module is being built into the core of
  22. **       SQLite (in which case SQLITE_ENABLE_FTS3 is defined).
  23. */
  24. /* TODO(shess) Consider exporting this comment to an HTML file or the
  25. ** wiki.
  26. */
  27. /* The full-text index is stored in a series of b+tree (-like)
  28. ** structures called segments which map terms to doclists.  The
  29. ** structures are like b+trees in layout, but are constructed from the
  30. ** bottom up in optimal fashion and are not updatable.  Since trees
  31. ** are built from the bottom up, things will be described from the
  32. ** bottom up.
  33. **
  34. **
  35. **** Varints ****
  36. ** The basic unit of encoding is a variable-length integer called a
  37. ** varint.  We encode variable-length integers in little-endian order
  38. ** using seven bits * per byte as follows:
  39. **
  40. ** KEY:
  41. **         A = 0xxxxxxx    7 bits of data and one flag bit
  42. **         B = 1xxxxxxx    7 bits of data and one flag bit
  43. **
  44. **  7 bits - A
  45. ** 14 bits - BA
  46. ** 21 bits - BBA
  47. ** and so on.
  48. **
  49. ** This is identical to how sqlite encodes varints (see util.c).
  50. **
  51. **
  52. **** Document lists ****
  53. ** A doclist (document list) holds a docid-sorted list of hits for a
  54. ** given term.  Doclists hold docids, and can optionally associate
  55. ** token positions and offsets with docids.
  56. **
  57. ** A DL_POSITIONS_OFFSETS doclist is stored like this:
  58. **
  59. ** array {
  60. **   varint docid;
  61. **   array {                (position list for column 0)
  62. **     varint position;     (delta from previous position plus POS_BASE)
  63. **     varint startOffset;  (delta from previous startOffset)
  64. **     varint endOffset;    (delta from startOffset)
  65. **   }
  66. **   array {
  67. **     varint POS_COLUMN;   (marks start of position list for new column)
  68. **     varint column;       (index of new column)
  69. **     array {
  70. **       varint position;   (delta from previous position plus POS_BASE)
  71. **       varint startOffset;(delta from previous startOffset)
  72. **       varint endOffset;  (delta from startOffset)
  73. **     }
  74. **   }
  75. **   varint POS_END;        (marks end of positions for this document.
  76. ** }
  77. **
  78. ** Here, array { X } means zero or more occurrences of X, adjacent in
  79. ** memory.  A "position" is an index of a token in the token stream
  80. ** generated by the tokenizer, while an "offset" is a byte offset,
  81. ** both based at 0.  Note that POS_END and POS_COLUMN occur in the
  82. ** same logical place as the position element, and act as sentinals
  83. ** ending a position list array.
  84. **
  85. ** A DL_POSITIONS doclist omits the startOffset and endOffset
  86. ** information.  A DL_DOCIDS doclist omits both the position and
  87. ** offset information, becoming an array of varint-encoded docids.
  88. **
  89. ** On-disk data is stored as type DL_DEFAULT, so we don't serialize
  90. ** the type.  Due to how deletion is implemented in the segmentation
  91. ** system, on-disk doclists MUST store at least positions.
  92. **
  93. **
  94. **** Segment leaf nodes ****
  95. ** Segment leaf nodes store terms and doclists, ordered by term.  Leaf
  96. ** nodes are written using LeafWriter, and read using LeafReader (to
  97. ** iterate through a single leaf node's data) and LeavesReader (to
  98. ** iterate through a segment's entire leaf layer).  Leaf nodes have
  99. ** the format:
  100. **
  101. ** varint iHeight;             (height from leaf level, always 0)
  102. ** varint nTerm;               (length of first term)
  103. ** char pTerm[nTerm];          (content of first term)
  104. ** varint nDoclist;            (length of term's associated doclist)
  105. ** char pDoclist[nDoclist];    (content of doclist)
  106. ** array {
  107. **                             (further terms are delta-encoded)
  108. **   varint nPrefix;           (length of prefix shared with previous term)
  109. **   varint nSuffix;           (length of unshared suffix)
  110. **   char pTermSuffix[nSuffix];(unshared suffix of next term)
  111. **   varint nDoclist;          (length of term's associated doclist)
  112. **   char pDoclist[nDoclist];  (content of doclist)
  113. ** }
  114. **
  115. ** Here, array { X } means zero or more occurrences of X, adjacent in
  116. ** memory.
  117. **
  118. ** Leaf nodes are broken into blocks which are stored contiguously in
  119. ** the %_segments table in sorted order.  This means that when the end
  120. ** of a node is reached, the next term is in the node with the next
  121. ** greater node id.
  122. **
  123. ** New data is spilled to a new leaf node when the current node
  124. ** exceeds LEAF_MAX bytes (default 2048).  New data which itself is
  125. ** larger than STANDALONE_MIN (default 1024) is placed in a standalone
  126. ** node (a leaf node with a single term and doclist).  The goal of
  127. ** these settings is to pack together groups of small doclists while
  128. ** making it efficient to directly access large doclists.  The
  129. ** assumption is that large doclists represent terms which are more
  130. ** likely to be query targets.
  131. **
  132. ** TODO(shess) It may be useful for blocking decisions to be more
  133. ** dynamic.  For instance, it may make more sense to have a 2.5k leaf
  134. ** node rather than splitting into 2k and .5k nodes.  My intuition is
  135. ** that this might extend through 2x or 4x the pagesize.
  136. **
  137. **
  138. **** Segment interior nodes ****
  139. ** Segment interior nodes store blockids for subtree nodes and terms
  140. ** to describe what data is stored by the each subtree.  Interior
  141. ** nodes are written using InteriorWriter, and read using
  142. ** InteriorReader.  InteriorWriters are created as needed when
  143. ** SegmentWriter creates new leaf nodes, or when an interior node
  144. ** itself grows too big and must be split.  The format of interior
  145. ** nodes:
  146. **
  147. ** varint iHeight;           (height from leaf level, always >0)
  148. ** varint iBlockid;          (block id of node's leftmost subtree)
  149. ** optional {
  150. **   varint nTerm;           (length of first term)
  151. **   char pTerm[nTerm];      (content of first term)
  152. **   array {
  153. **                                (further terms are delta-encoded)
  154. **     varint nPrefix;            (length of shared prefix with previous term)
  155. **     varint nSuffix;            (length of unshared suffix)
  156. **     char pTermSuffix[nSuffix]; (unshared suffix of next term)
  157. **   }
  158. ** }
  159. **
  160. ** Here, optional { X } means an optional element, while array { X }
  161. ** means zero or more occurrences of X, adjacent in memory.
  162. **
  163. ** An interior node encodes n terms separating n+1 subtrees.  The
  164. ** subtree blocks are contiguous, so only the first subtree's blockid
  165. ** is encoded.  The subtree at iBlockid will contain all terms less
  166. ** than the first term encoded (or all terms if no term is encoded).
  167. ** Otherwise, for terms greater than or equal to pTerm[i] but less
  168. ** than pTerm[i+1], the subtree for that term will be rooted at
  169. ** iBlockid+i.  Interior nodes only store enough term data to
  170. ** distinguish adjacent children (if the rightmost term of the left
  171. ** child is "something", and the leftmost term of the right child is
  172. ** "wicked", only "w" is stored).
  173. **
  174. ** New data is spilled to a new interior node at the same height when
  175. ** the current node exceeds INTERIOR_MAX bytes (default 2048).
  176. ** INTERIOR_MIN_TERMS (default 7) keeps large terms from monopolizing
  177. ** interior nodes and making the tree too skinny.  The interior nodes
  178. ** at a given height are naturally tracked by interior nodes at
  179. ** height+1, and so on.
  180. **
  181. **
  182. **** Segment directory ****
  183. ** The segment directory in table %_segdir stores meta-information for
  184. ** merging and deleting segments, and also the root node of the
  185. ** segment's tree.
  186. **
  187. ** The root node is the top node of the segment's tree after encoding
  188. ** the entire segment, restricted to ROOT_MAX bytes (default 1024).
  189. ** This could be either a leaf node or an interior node.  If the top
  190. ** node requires more than ROOT_MAX bytes, it is flushed to %_segments
  191. ** and a new root interior node is generated (which should always fit
  192. ** within ROOT_MAX because it only needs space for 2 varints, the
  193. ** height and the blockid of the previous root).
  194. **
  195. ** The meta-information in the segment directory is:
  196. **   level               - segment level (see below)
  197. **   idx                 - index within level
  198. **                       - (level,idx uniquely identify a segment)
  199. **   start_block         - first leaf node
  200. **   leaves_end_block    - last leaf node
  201. **   end_block           - last block (including interior nodes)
  202. **   root                - contents of root node
  203. **
  204. ** If the root node is a leaf node, then start_block,
  205. ** leaves_end_block, and end_block are all 0.
  206. **
  207. **
  208. **** Segment merging ****
  209. ** To amortize update costs, segments are groups into levels and
  210. ** merged in matches.  Each increase in level represents exponentially
  211. ** more documents.
  212. **
  213. ** New documents (actually, document updates) are tokenized and
  214. ** written individually (using LeafWriter) to a level 0 segment, with
  215. ** incrementing idx.  When idx reaches MERGE_COUNT (default 16), all
  216. ** level 0 segments are merged into a single level 1 segment.  Level 1
  217. ** is populated like level 0, and eventually MERGE_COUNT level 1
  218. ** segments are merged to a single level 2 segment (representing
  219. ** MERGE_COUNT^2 updates), and so on.
  220. **
  221. ** A segment merge traverses all segments at a given level in
  222. ** parallel, performing a straightforward sorted merge.  Since segment
  223. ** leaf nodes are written in to the %_segments table in order, this
  224. ** merge traverses the underlying sqlite disk structures efficiently.
  225. ** After the merge, all segment blocks from the merged level are
  226. ** deleted.
  227. **
  228. ** MERGE_COUNT controls how often we merge segments.  16 seems to be
  229. ** somewhat of a sweet spot for insertion performance.  32 and 64 show
  230. ** very similar performance numbers to 16 on insertion, though they're
  231. ** a tiny bit slower (perhaps due to more overhead in merge-time
  232. ** sorting).  8 is about 20% slower than 16, 4 about 50% slower than
  233. ** 16, 2 about 66% slower than 16.
  234. **
  235. ** At query time, high MERGE_COUNT increases the number of segments
  236. ** which need to be scanned and merged.  For instance, with 100k docs
  237. ** inserted:
  238. **
  239. **    MERGE_COUNT   segments
  240. **       16           25
  241. **        8           12
  242. **        4           10
  243. **        2            6
  244. **
  245. ** This appears to have only a moderate impact on queries for very
  246. ** frequent terms (which are somewhat dominated by segment merge
  247. ** costs), and infrequent and non-existent terms still seem to be fast
  248. ** even with many segments.
  249. **
  250. ** TODO(shess) That said, it would be nice to have a better query-side
  251. ** argument for MERGE_COUNT of 16.  Also, it is possible/likely that
  252. ** optimizations to things like doclist merging will swing the sweet
  253. ** spot around.
  254. **
  255. **
  256. **
  257. **** Handling of deletions and updates ****
  258. ** Since we're using a segmented structure, with no docid-oriented
  259. ** index into the term index, we clearly cannot simply update the term
  260. ** index when a document is deleted or updated.  For deletions, we
  261. ** write an empty doclist (varint(docid) varint(POS_END)), for updates
  262. ** we simply write the new doclist.  Segment merges overwrite older
  263. ** data for a particular docid with newer data, so deletes or updates
  264. ** will eventually overtake the earlier data and knock it out.  The
  265. ** query logic likewise merges doclists so that newer data knocks out
  266. ** older data.
  267. **
  268. ** TODO(shess) Provide a VACUUM type operation to clear out all
  269. ** deletions and duplications.  This would basically be a forced merge
  270. ** into a single segment.
  271. */
  272. #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)
  273. #if defined(SQLITE_ENABLE_FTS3) && !defined(SQLITE_CORE)
  274. # define SQLITE_CORE 1
  275. #endif
  276. #include <assert.h>
  277. #include <stdlib.h>
  278. #include <stdio.h>
  279. #include <string.h>
  280. #include <ctype.h>
  281. #include "fts3.h"
  282. #include "fts3_hash.h"
  283. #include "fts3_tokenizer.h"
  284. #ifndef SQLITE_CORE 
  285. # include "sqlite3ext.h"
  286.   SQLITE_EXTENSION_INIT1
  287. #endif
  288. /* TODO(shess) MAN, this thing needs some refactoring.  At minimum, it
  289. ** would be nice to order the file better, perhaps something along the
  290. ** lines of:
  291. **
  292. **  - utility functions
  293. **  - table setup functions
  294. **  - table update functions
  295. **  - table query functions
  296. **
  297. ** Put the query functions last because they're likely to reference
  298. ** typedefs or functions from the table update section.
  299. */
  300. #if 0
  301. # define FTSTRACE(A)  printf A; fflush(stdout)
  302. #else
  303. # define FTSTRACE(A)
  304. #endif
  305. /*
  306. ** Default span for NEAR operators.
  307. */
  308. #define SQLITE_FTS3_DEFAULT_NEAR_PARAM 10
  309. /* It is not safe to call isspace(), tolower(), or isalnum() on
  310. ** hi-bit-set characters.  This is the same solution used in the
  311. ** tokenizer.
  312. */
  313. /* TODO(shess) The snippet-generation code should be using the
  314. ** tokenizer-generated tokens rather than doing its own local
  315. ** tokenization.
  316. */
  317. /* TODO(shess) Is __isascii() a portable version of (c&0x80)==0? */
  318. static int safe_isspace(char c){
  319.   return (c&0x80)==0 ? isspace(c) : 0;
  320. }
  321. static int safe_tolower(char c){
  322.   return (c&0x80)==0 ? tolower(c) : c;
  323. }
  324. static int safe_isalnum(char c){
  325.   return (c&0x80)==0 ? isalnum(c) : 0;
  326. }
  327. typedef enum DocListType {
  328.   DL_DOCIDS,              /* docids only */
  329.   DL_POSITIONS,           /* docids + positions */
  330.   DL_POSITIONS_OFFSETS    /* docids + positions + offsets */
  331. } DocListType;
  332. /*
  333. ** By default, only positions and not offsets are stored in the doclists.
  334. ** To change this so that offsets are stored too, compile with
  335. **
  336. **          -DDL_DEFAULT=DL_POSITIONS_OFFSETS
  337. **
  338. ** If DL_DEFAULT is set to DL_DOCIDS, your table can only be inserted
  339. ** into (no deletes or updates).
  340. */
  341. #ifndef DL_DEFAULT
  342. # define DL_DEFAULT DL_POSITIONS
  343. #endif
  344. enum {
  345.   POS_END = 0,        /* end of this position list */
  346.   POS_COLUMN,         /* followed by new column number */
  347.   POS_BASE
  348. };
  349. /* MERGE_COUNT controls how often we merge segments (see comment at
  350. ** top of file).
  351. */
  352. #define MERGE_COUNT 16
  353. /* utility functions */
  354. /* CLEAR() and SCRAMBLE() abstract memset() on a pointer to a single
  355. ** record to prevent errors of the form:
  356. **
  357. ** my_function(SomeType *b){
  358. **   memset(b, '', sizeof(b));  // sizeof(b)!=sizeof(*b)
  359. ** }
  360. */
  361. /* TODO(shess) Obvious candidates for a header file. */
  362. #define CLEAR(b) memset(b, '', sizeof(*(b)))
  363. #ifndef NDEBUG
  364. #  define SCRAMBLE(b) memset(b, 0x55, sizeof(*(b)))
  365. #else
  366. #  define SCRAMBLE(b)
  367. #endif
  368. /* We may need up to VARINT_MAX bytes to store an encoded 64-bit integer. */
  369. #define VARINT_MAX 10
  370. /* Write a 64-bit variable-length integer to memory starting at p[0].
  371.  * The length of data written will be between 1 and VARINT_MAX bytes.
  372.  * The number of bytes written is returned. */
  373. static int fts3PutVarint(char *p, sqlite_int64 v){
  374.   unsigned char *q = (unsigned char *) p;
  375.   sqlite_uint64 vu = v;
  376.   do{
  377.     *q++ = (unsigned char) ((vu & 0x7f) | 0x80);
  378.     vu >>= 7;
  379.   }while( vu!=0 );
  380.   q[-1] &= 0x7f;  /* turn off high bit in final byte */
  381.   assert( q - (unsigned char *)p <= VARINT_MAX );
  382.   return (int) (q - (unsigned char *)p);
  383. }
  384. /* Read a 64-bit variable-length integer from memory starting at p[0].
  385.  * Return the number of bytes read, or 0 on error.
  386.  * The value is stored in *v. */
  387. static int fts3GetVarint(const char *p, sqlite_int64 *v){
  388.   const unsigned char *q = (const unsigned char *) p;
  389.   sqlite_uint64 x = 0, y = 1;
  390.   while( (*q & 0x80) == 0x80 ){
  391.     x += y * (*q++ & 0x7f);
  392.     y <<= 7;
  393.     if( q - (unsigned char *)p >= VARINT_MAX ){  /* bad data */
  394.       assert( 0 );
  395.       return 0;
  396.     }
  397.   }
  398.   x += y * (*q++);
  399.   *v = (sqlite_int64) x;
  400.   return (int) (q - (unsigned char *)p);
  401. }
  402. static int fts3GetVarint32(const char *p, int *pi){
  403.  sqlite_int64 i;
  404.  int ret = fts3GetVarint(p, &i);
  405.  *pi = (int) i;
  406.  assert( *pi==i );
  407.  return ret;
  408. }
  409. /*******************************************************************/
  410. /* DataBuffer is used to collect data into a buffer in piecemeal
  411. ** fashion.  It implements the usual distinction between amount of
  412. ** data currently stored (nData) and buffer capacity (nCapacity).
  413. **
  414. ** dataBufferInit - create a buffer with given initial capacity.
  415. ** dataBufferReset - forget buffer's data, retaining capacity.
  416. ** dataBufferDestroy - free buffer's data.
  417. ** dataBufferSwap - swap contents of two buffers.
  418. ** dataBufferExpand - expand capacity without adding data.
  419. ** dataBufferAppend - append data.
  420. ** dataBufferAppend2 - append two pieces of data at once.
  421. ** dataBufferReplace - replace buffer's data.
  422. */
  423. typedef struct DataBuffer {
  424.   char *pData;          /* Pointer to malloc'ed buffer. */
  425.   int nCapacity;        /* Size of pData buffer. */
  426.   int nData;            /* End of data loaded into pData. */
  427. } DataBuffer;
  428. static void dataBufferInit(DataBuffer *pBuffer, int nCapacity){
  429.   assert( nCapacity>=0 );
  430.   pBuffer->nData = 0;
  431.   pBuffer->nCapacity = nCapacity;
  432.   pBuffer->pData = nCapacity==0 ? NULL : sqlite3_malloc(nCapacity);
  433. }
  434. static void dataBufferReset(DataBuffer *pBuffer){
  435.   pBuffer->nData = 0;
  436. }
  437. static void dataBufferDestroy(DataBuffer *pBuffer){
  438.   if( pBuffer->pData!=NULL ) sqlite3_free(pBuffer->pData);
  439.   SCRAMBLE(pBuffer);
  440. }
  441. static void dataBufferSwap(DataBuffer *pBuffer1, DataBuffer *pBuffer2){
  442.   DataBuffer tmp = *pBuffer1;
  443.   *pBuffer1 = *pBuffer2;
  444.   *pBuffer2 = tmp;
  445. }
  446. static void dataBufferExpand(DataBuffer *pBuffer, int nAddCapacity){
  447.   assert( nAddCapacity>0 );
  448.   /* TODO(shess) Consider expanding more aggressively.  Note that the
  449.   ** underlying malloc implementation may take care of such things for
  450.   ** us already.
  451.   */
  452.   if( pBuffer->nData+nAddCapacity>pBuffer->nCapacity ){
  453.     pBuffer->nCapacity = pBuffer->nData+nAddCapacity;
  454.     pBuffer->pData = sqlite3_realloc(pBuffer->pData, pBuffer->nCapacity);
  455.   }
  456. }
  457. static void dataBufferAppend(DataBuffer *pBuffer,
  458.                              const char *pSource, int nSource){
  459.   assert( nSource>0 && pSource!=NULL );
  460.   dataBufferExpand(pBuffer, nSource);
  461.   memcpy(pBuffer->pData+pBuffer->nData, pSource, nSource);
  462.   pBuffer->nData += nSource;
  463. }
  464. static void dataBufferAppend2(DataBuffer *pBuffer,
  465.                               const char *pSource1, int nSource1,
  466.                               const char *pSource2, int nSource2){
  467.   assert( nSource1>0 && pSource1!=NULL );
  468.   assert( nSource2>0 && pSource2!=NULL );
  469.   dataBufferExpand(pBuffer, nSource1+nSource2);
  470.   memcpy(pBuffer->pData+pBuffer->nData, pSource1, nSource1);
  471.   memcpy(pBuffer->pData+pBuffer->nData+nSource1, pSource2, nSource2);
  472.   pBuffer->nData += nSource1+nSource2;
  473. }
  474. static void dataBufferReplace(DataBuffer *pBuffer,
  475.                               const char *pSource, int nSource){
  476.   dataBufferReset(pBuffer);
  477.   dataBufferAppend(pBuffer, pSource, nSource);
  478. }
  479. /* StringBuffer is a null-terminated version of DataBuffer. */
  480. typedef struct StringBuffer {
  481.   DataBuffer b;            /* Includes null terminator. */
  482. } StringBuffer;
  483. static void initStringBuffer(StringBuffer *sb){
  484.   dataBufferInit(&sb->b, 100);
  485.   dataBufferReplace(&sb->b, "", 1);
  486. }
  487. static int stringBufferLength(StringBuffer *sb){
  488.   return sb->b.nData-1;
  489. }
  490. static char *stringBufferData(StringBuffer *sb){
  491.   return sb->b.pData;
  492. }
  493. static void stringBufferDestroy(StringBuffer *sb){
  494.   dataBufferDestroy(&sb->b);
  495. }
  496. static void nappend(StringBuffer *sb, const char *zFrom, int nFrom){
  497.   assert( sb->b.nData>0 );
  498.   if( nFrom>0 ){
  499.     sb->b.nData--;
  500.     dataBufferAppend2(&sb->b, zFrom, nFrom, "", 1);
  501.   }
  502. }
  503. static void append(StringBuffer *sb, const char *zFrom){
  504.   nappend(sb, zFrom, strlen(zFrom));
  505. }
  506. /* Append a list of strings separated by commas. */
  507. static void appendList(StringBuffer *sb, int nString, char **azString){
  508.   int i;
  509.   for(i=0; i<nString; ++i){
  510.     if( i>0 ) append(sb, ", ");
  511.     append(sb, azString[i]);
  512.   }
  513. }
  514. static int endsInWhiteSpace(StringBuffer *p){
  515.   return stringBufferLength(p)>0 &&
  516.     safe_isspace(stringBufferData(p)[stringBufferLength(p)-1]);
  517. }
  518. /* If the StringBuffer ends in something other than white space, add a
  519. ** single space character to the end.
  520. */
  521. static void appendWhiteSpace(StringBuffer *p){
  522.   if( stringBufferLength(p)==0 ) return;
  523.   if( !endsInWhiteSpace(p) ) append(p, " ");
  524. }
  525. /* Remove white space from the end of the StringBuffer */
  526. static void trimWhiteSpace(StringBuffer *p){
  527.   while( endsInWhiteSpace(p) ){
  528.     p->b.pData[--p->b.nData-1] = '';
  529.   }
  530. }
  531. /*******************************************************************/
  532. /* DLReader is used to read document elements from a doclist.  The
  533. ** current docid is cached, so dlrDocid() is fast.  DLReader does not
  534. ** own the doclist buffer.
  535. **
  536. ** dlrAtEnd - true if there's no more data to read.
  537. ** dlrDocid - docid of current document.
  538. ** dlrDocData - doclist data for current document (including docid).
  539. ** dlrDocDataBytes - length of same.
  540. ** dlrAllDataBytes - length of all remaining data.
  541. ** dlrPosData - position data for current document.
  542. ** dlrPosDataLen - length of pos data for current document (incl POS_END).
  543. ** dlrStep - step to current document.
  544. ** dlrInit - initial for doclist of given type against given data.
  545. ** dlrDestroy - clean up.
  546. **
  547. ** Expected usage is something like:
  548. **
  549. **   DLReader reader;
  550. **   dlrInit(&reader, pData, nData);
  551. **   while( !dlrAtEnd(&reader) ){
  552. **     // calls to dlrDocid() and kin.
  553. **     dlrStep(&reader);
  554. **   }
  555. **   dlrDestroy(&reader);
  556. */
  557. typedef struct DLReader {
  558.   DocListType iType;
  559.   const char *pData;
  560.   int nData;
  561.   sqlite_int64 iDocid;
  562.   int nElement;
  563. } DLReader;
  564. static int dlrAtEnd(DLReader *pReader){
  565.   assert( pReader->nData>=0 );
  566.   return pReader->nData==0;
  567. }
  568. static sqlite_int64 dlrDocid(DLReader *pReader){
  569.   assert( !dlrAtEnd(pReader) );
  570.   return pReader->iDocid;
  571. }
  572. static const char *dlrDocData(DLReader *pReader){
  573.   assert( !dlrAtEnd(pReader) );
  574.   return pReader->pData;
  575. }
  576. static int dlrDocDataBytes(DLReader *pReader){
  577.   assert( !dlrAtEnd(pReader) );
  578.   return pReader->nElement;
  579. }
  580. static int dlrAllDataBytes(DLReader *pReader){
  581.   assert( !dlrAtEnd(pReader) );
  582.   return pReader->nData;
  583. }
  584. /* TODO(shess) Consider adding a field to track iDocid varint length
  585. ** to make these two functions faster.  This might matter (a tiny bit)
  586. ** for queries.
  587. */
  588. static const char *dlrPosData(DLReader *pReader){
  589.   sqlite_int64 iDummy;
  590.   int n = fts3GetVarint(pReader->pData, &iDummy);
  591.   assert( !dlrAtEnd(pReader) );
  592.   return pReader->pData+n;
  593. }
  594. static int dlrPosDataLen(DLReader *pReader){
  595.   sqlite_int64 iDummy;
  596.   int n = fts3GetVarint(pReader->pData, &iDummy);
  597.   assert( !dlrAtEnd(pReader) );
  598.   return pReader->nElement-n;
  599. }
  600. static void dlrStep(DLReader *pReader){
  601.   assert( !dlrAtEnd(pReader) );
  602.   /* Skip past current doclist element. */
  603.   assert( pReader->nElement<=pReader->nData );
  604.   pReader->pData += pReader->nElement;
  605.   pReader->nData -= pReader->nElement;
  606.   /* If there is more data, read the next doclist element. */
  607.   if( pReader->nData!=0 ){
  608.     sqlite_int64 iDocidDelta;
  609.     int iDummy, n = fts3GetVarint(pReader->pData, &iDocidDelta);
  610.     pReader->iDocid += iDocidDelta;
  611.     if( pReader->iType>=DL_POSITIONS ){
  612.       assert( n<pReader->nData );
  613.       while( 1 ){
  614.         n += fts3GetVarint32(pReader->pData+n, &iDummy);
  615.         assert( n<=pReader->nData );
  616.         if( iDummy==POS_END ) break;
  617.         if( iDummy==POS_COLUMN ){
  618.           n += fts3GetVarint32(pReader->pData+n, &iDummy);
  619.           assert( n<pReader->nData );
  620.         }else if( pReader->iType==DL_POSITIONS_OFFSETS ){
  621.           n += fts3GetVarint32(pReader->pData+n, &iDummy);
  622.           n += fts3GetVarint32(pReader->pData+n, &iDummy);
  623.           assert( n<pReader->nData );
  624.         }
  625.       }
  626.     }
  627.     pReader->nElement = n;
  628.     assert( pReader->nElement<=pReader->nData );
  629.   }
  630. }
  631. static void dlrInit(DLReader *pReader, DocListType iType,
  632.                     const char *pData, int nData){
  633.   assert( pData!=NULL && nData!=0 );
  634.   pReader->iType = iType;
  635.   pReader->pData = pData;
  636.   pReader->nData = nData;
  637.   pReader->nElement = 0;
  638.   pReader->iDocid = 0;
  639.   /* Load the first element's data.  There must be a first element. */
  640.   dlrStep(pReader);
  641. }
  642. static void dlrDestroy(DLReader *pReader){
  643.   SCRAMBLE(pReader);
  644. }
  645. #ifndef NDEBUG
  646. /* Verify that the doclist can be validly decoded.  Also returns the
  647. ** last docid found because it is convenient in other assertions for
  648. ** DLWriter.
  649. */
  650. static void docListValidate(DocListType iType, const char *pData, int nData,
  651.                             sqlite_int64 *pLastDocid){
  652.   sqlite_int64 iPrevDocid = 0;
  653.   assert( nData>0 );
  654.   assert( pData!=0 );
  655.   assert( pData+nData>pData );
  656.   while( nData!=0 ){
  657.     sqlite_int64 iDocidDelta;
  658.     int n = fts3GetVarint(pData, &iDocidDelta);
  659.     iPrevDocid += iDocidDelta;
  660.     if( iType>DL_DOCIDS ){
  661.       int iDummy;
  662.       while( 1 ){
  663.         n += fts3GetVarint32(pData+n, &iDummy);
  664.         if( iDummy==POS_END ) break;
  665.         if( iDummy==POS_COLUMN ){
  666.           n += fts3GetVarint32(pData+n, &iDummy);
  667.         }else if( iType>DL_POSITIONS ){
  668.           n += fts3GetVarint32(pData+n, &iDummy);
  669.           n += fts3GetVarint32(pData+n, &iDummy);
  670.         }
  671.         assert( n<=nData );
  672.       }
  673.     }
  674.     assert( n<=nData );
  675.     pData += n;
  676.     nData -= n;
  677.   }
  678.   if( pLastDocid ) *pLastDocid = iPrevDocid;
  679. }
  680. #define ASSERT_VALID_DOCLIST(i, p, n, o) docListValidate(i, p, n, o)
  681. #else
  682. #define ASSERT_VALID_DOCLIST(i, p, n, o) assert( 1 )
  683. #endif
  684. /*******************************************************************/
  685. /* DLWriter is used to write doclist data to a DataBuffer.  DLWriter
  686. ** always appends to the buffer and does not own it.
  687. **
  688. ** dlwInit - initialize to write a given type doclistto a buffer.
  689. ** dlwDestroy - clear the writer's memory.  Does not free buffer.
  690. ** dlwAppend - append raw doclist data to buffer.
  691. ** dlwCopy - copy next doclist from reader to writer.
  692. ** dlwAdd - construct doclist element and append to buffer.
  693. **    Only apply dlwAdd() to DL_DOCIDS doclists (else use PLWriter).
  694. */
  695. typedef struct DLWriter {
  696.   DocListType iType;
  697.   DataBuffer *b;
  698.   sqlite_int64 iPrevDocid;
  699. #ifndef NDEBUG
  700.   int has_iPrevDocid;
  701. #endif
  702. } DLWriter;
  703. static void dlwInit(DLWriter *pWriter, DocListType iType, DataBuffer *b){
  704.   pWriter->b = b;
  705.   pWriter->iType = iType;
  706.   pWriter->iPrevDocid = 0;
  707. #ifndef NDEBUG
  708.   pWriter->has_iPrevDocid = 0;
  709. #endif
  710. }
  711. static void dlwDestroy(DLWriter *pWriter){
  712.   SCRAMBLE(pWriter);
  713. }
  714. /* iFirstDocid is the first docid in the doclist in pData.  It is
  715. ** needed because pData may point within a larger doclist, in which
  716. ** case the first item would be delta-encoded.
  717. **
  718. ** iLastDocid is the final docid in the doclist in pData.  It is
  719. ** needed to create the new iPrevDocid for future delta-encoding.  The
  720. ** code could decode the passed doclist to recreate iLastDocid, but
  721. ** the only current user (docListMerge) already has decoded this
  722. ** information.
  723. */
  724. /* TODO(shess) This has become just a helper for docListMerge.
  725. ** Consider a refactor to make this cleaner.
  726. */
  727. static void dlwAppend(DLWriter *pWriter,
  728.                       const char *pData, int nData,
  729.                       sqlite_int64 iFirstDocid, sqlite_int64 iLastDocid){
  730.   sqlite_int64 iDocid = 0;
  731.   char c[VARINT_MAX];
  732.   int nFirstOld, nFirstNew;     /* Old and new varint len of first docid. */
  733. #ifndef NDEBUG
  734.   sqlite_int64 iLastDocidDelta;
  735. #endif
  736.   /* Recode the initial docid as delta from iPrevDocid. */
  737.   nFirstOld = fts3GetVarint(pData, &iDocid);
  738.   assert( nFirstOld<nData || (nFirstOld==nData && pWriter->iType==DL_DOCIDS) );
  739.   nFirstNew = fts3PutVarint(c, iFirstDocid-pWriter->iPrevDocid);
  740.   /* Verify that the incoming doclist is valid AND that it ends with
  741.   ** the expected docid.  This is essential because we'll trust this
  742.   ** docid in future delta-encoding.
  743.   */
  744.   ASSERT_VALID_DOCLIST(pWriter->iType, pData, nData, &iLastDocidDelta);
  745.   assert( iLastDocid==iFirstDocid-iDocid+iLastDocidDelta );
  746.   /* Append recoded initial docid and everything else.  Rest of docids
  747.   ** should have been delta-encoded from previous initial docid.
  748.   */
  749.   if( nFirstOld<nData ){
  750.     dataBufferAppend2(pWriter->b, c, nFirstNew,
  751.                       pData+nFirstOld, nData-nFirstOld);
  752.   }else{
  753.     dataBufferAppend(pWriter->b, c, nFirstNew);
  754.   }
  755.   pWriter->iPrevDocid = iLastDocid;
  756. }
  757. static void dlwCopy(DLWriter *pWriter, DLReader *pReader){
  758.   dlwAppend(pWriter, dlrDocData(pReader), dlrDocDataBytes(pReader),
  759.             dlrDocid(pReader), dlrDocid(pReader));
  760. }
  761. static void dlwAdd(DLWriter *pWriter, sqlite_int64 iDocid){
  762.   char c[VARINT_MAX];
  763.   int n = fts3PutVarint(c, iDocid-pWriter->iPrevDocid);
  764.   /* Docids must ascend. */
  765.   assert( !pWriter->has_iPrevDocid || iDocid>pWriter->iPrevDocid );
  766.   assert( pWriter->iType==DL_DOCIDS );
  767.   dataBufferAppend(pWriter->b, c, n);
  768.   pWriter->iPrevDocid = iDocid;
  769. #ifndef NDEBUG
  770.   pWriter->has_iPrevDocid = 1;
  771. #endif
  772. }
  773. /*******************************************************************/
  774. /* PLReader is used to read data from a document's position list.  As
  775. ** the caller steps through the list, data is cached so that varints
  776. ** only need to be decoded once.
  777. **
  778. ** plrInit, plrDestroy - create/destroy a reader.
  779. ** plrColumn, plrPosition, plrStartOffset, plrEndOffset - accessors
  780. ** plrAtEnd - at end of stream, only call plrDestroy once true.
  781. ** plrStep - step to the next element.
  782. */
  783. typedef struct PLReader {
  784.   /* These refer to the next position's data.  nData will reach 0 when
  785.   ** reading the last position, so plrStep() signals EOF by setting
  786.   ** pData to NULL.
  787.   */
  788.   const char *pData;
  789.   int nData;
  790.   DocListType iType;
  791.   int iColumn;         /* the last column read */
  792.   int iPosition;       /* the last position read */
  793.   int iStartOffset;    /* the last start offset read */
  794.   int iEndOffset;      /* the last end offset read */
  795. } PLReader;
  796. static int plrAtEnd(PLReader *pReader){
  797.   return pReader->pData==NULL;
  798. }
  799. static int plrColumn(PLReader *pReader){
  800.   assert( !plrAtEnd(pReader) );
  801.   return pReader->iColumn;
  802. }
  803. static int plrPosition(PLReader *pReader){
  804.   assert( !plrAtEnd(pReader) );
  805.   return pReader->iPosition;
  806. }
  807. static int plrStartOffset(PLReader *pReader){
  808.   assert( !plrAtEnd(pReader) );
  809.   return pReader->iStartOffset;
  810. }
  811. static int plrEndOffset(PLReader *pReader){
  812.   assert( !plrAtEnd(pReader) );
  813.   return pReader->iEndOffset;
  814. }
  815. static void plrStep(PLReader *pReader){
  816.   int i, n;
  817.   assert( !plrAtEnd(pReader) );
  818.   if( pReader->nData==0 ){
  819.     pReader->pData = NULL;
  820.     return;
  821.   }
  822.   n = fts3GetVarint32(pReader->pData, &i);
  823.   if( i==POS_COLUMN ){
  824.     n += fts3GetVarint32(pReader->pData+n, &pReader->iColumn);
  825.     pReader->iPosition = 0;
  826.     pReader->iStartOffset = 0;
  827.     n += fts3GetVarint32(pReader->pData+n, &i);
  828.   }
  829.   /* Should never see adjacent column changes. */
  830.   assert( i!=POS_COLUMN );
  831.   if( i==POS_END ){
  832.     pReader->nData = 0;
  833.     pReader->pData = NULL;
  834.     return;
  835.   }
  836.   pReader->iPosition += i-POS_BASE;
  837.   if( pReader->iType==DL_POSITIONS_OFFSETS ){
  838.     n += fts3GetVarint32(pReader->pData+n, &i);
  839.     pReader->iStartOffset += i;
  840.     n += fts3GetVarint32(pReader->pData+n, &i);
  841.     pReader->iEndOffset = pReader->iStartOffset+i;
  842.   }
  843.   assert( n<=pReader->nData );
  844.   pReader->pData += n;
  845.   pReader->nData -= n;
  846. }
  847. static void plrInit(PLReader *pReader, DLReader *pDLReader){
  848.   pReader->pData = dlrPosData(pDLReader);
  849.   pReader->nData = dlrPosDataLen(pDLReader);
  850.   pReader->iType = pDLReader->iType;
  851.   pReader->iColumn = 0;
  852.   pReader->iPosition = 0;
  853.   pReader->iStartOffset = 0;
  854.   pReader->iEndOffset = 0;
  855.   plrStep(pReader);
  856. }
  857. static void plrDestroy(PLReader *pReader){
  858.   SCRAMBLE(pReader);
  859. }
  860. /*******************************************************************/
  861. /* PLWriter is used in constructing a document's position list.  As a
  862. ** convenience, if iType is DL_DOCIDS, PLWriter becomes a no-op.
  863. ** PLWriter writes to the associated DLWriter's buffer.
  864. **
  865. ** plwInit - init for writing a document's poslist.
  866. ** plwDestroy - clear a writer.
  867. ** plwAdd - append position and offset information.
  868. ** plwCopy - copy next position's data from reader to writer.
  869. ** plwTerminate - add any necessary doclist terminator.
  870. **
  871. ** Calling plwAdd() after plwTerminate() may result in a corrupt
  872. ** doclist.
  873. */
  874. /* TODO(shess) Until we've written the second item, we can cache the
  875. ** first item's information.  Then we'd have three states:
  876. **
  877. ** - initialized with docid, no positions.
  878. ** - docid and one position.
  879. ** - docid and multiple positions.
  880. **
  881. ** Only the last state needs to actually write to dlw->b, which would
  882. ** be an improvement in the DLCollector case.
  883. */
  884. typedef struct PLWriter {
  885.   DLWriter *dlw;
  886.   int iColumn;    /* the last column written */
  887.   int iPos;       /* the last position written */
  888.   int iOffset;    /* the last start offset written */
  889. } PLWriter;
  890. /* TODO(shess) In the case where the parent is reading these values
  891. ** from a PLReader, we could optimize to a copy if that PLReader has
  892. ** the same type as pWriter.
  893. */
  894. static void plwAdd(PLWriter *pWriter, int iColumn, int iPos,
  895.                    int iStartOffset, int iEndOffset){
  896.   /* Worst-case space for POS_COLUMN, iColumn, iPosDelta,
  897.   ** iStartOffsetDelta, and iEndOffsetDelta.
  898.   */
  899.   char c[5*VARINT_MAX];
  900.   int n = 0;
  901.   /* Ban plwAdd() after plwTerminate(). */
  902.   assert( pWriter->iPos!=-1 );
  903.   if( pWriter->dlw->iType==DL_DOCIDS ) return;
  904.   if( iColumn!=pWriter->iColumn ){
  905.     n += fts3PutVarint(c+n, POS_COLUMN);
  906.     n += fts3PutVarint(c+n, iColumn);
  907.     pWriter->iColumn = iColumn;
  908.     pWriter->iPos = 0;
  909.     pWriter->iOffset = 0;
  910.   }
  911.   assert( iPos>=pWriter->iPos );
  912.   n += fts3PutVarint(c+n, POS_BASE+(iPos-pWriter->iPos));
  913.   pWriter->iPos = iPos;
  914.   if( pWriter->dlw->iType==DL_POSITIONS_OFFSETS ){
  915.     assert( iStartOffset>=pWriter->iOffset );
  916.     n += fts3PutVarint(c+n, iStartOffset-pWriter->iOffset);
  917.     pWriter->iOffset = iStartOffset;
  918.     assert( iEndOffset>=iStartOffset );
  919.     n += fts3PutVarint(c+n, iEndOffset-iStartOffset);
  920.   }
  921.   dataBufferAppend(pWriter->dlw->b, c, n);
  922. }
  923. static void plwCopy(PLWriter *pWriter, PLReader *pReader){
  924.   plwAdd(pWriter, plrColumn(pReader), plrPosition(pReader),
  925.          plrStartOffset(pReader), plrEndOffset(pReader));
  926. }
  927. static void plwInit(PLWriter *pWriter, DLWriter *dlw, sqlite_int64 iDocid){
  928.   char c[VARINT_MAX];
  929.   int n;
  930.   pWriter->dlw = dlw;
  931.   /* Docids must ascend. */
  932.   assert( !pWriter->dlw->has_iPrevDocid || iDocid>pWriter->dlw->iPrevDocid );
  933.   n = fts3PutVarint(c, iDocid-pWriter->dlw->iPrevDocid);
  934.   dataBufferAppend(pWriter->dlw->b, c, n);
  935.   pWriter->dlw->iPrevDocid = iDocid;
  936. #ifndef NDEBUG
  937.   pWriter->dlw->has_iPrevDocid = 1;
  938. #endif
  939.   pWriter->iColumn = 0;
  940.   pWriter->iPos = 0;
  941.   pWriter->iOffset = 0;
  942. }
  943. /* TODO(shess) Should plwDestroy() also terminate the doclist?  But
  944. ** then plwDestroy() would no longer be just a destructor, it would
  945. ** also be doing work, which isn't consistent with the overall idiom.
  946. ** Another option would be for plwAdd() to always append any necessary
  947. ** terminator, so that the output is always correct.  But that would
  948. ** add incremental work to the common case with the only benefit being
  949. ** API elegance.  Punt for now.
  950. */
  951. static void plwTerminate(PLWriter *pWriter){
  952.   if( pWriter->dlw->iType>DL_DOCIDS ){
  953.     char c[VARINT_MAX];
  954.     int n = fts3PutVarint(c, POS_END);
  955.     dataBufferAppend(pWriter->dlw->b, c, n);
  956.   }
  957. #ifndef NDEBUG
  958.   /* Mark as terminated for assert in plwAdd(). */
  959.   pWriter->iPos = -1;
  960. #endif
  961. }
  962. static void plwDestroy(PLWriter *pWriter){
  963.   SCRAMBLE(pWriter);
  964. }
  965. /*******************************************************************/
  966. /* DLCollector wraps PLWriter and DLWriter to provide a
  967. ** dynamically-allocated doclist area to use during tokenization.
  968. **
  969. ** dlcNew - malloc up and initialize a collector.
  970. ** dlcDelete - destroy a collector and all contained items.
  971. ** dlcAddPos - append position and offset information.
  972. ** dlcAddDoclist - add the collected doclist to the given buffer.
  973. ** dlcNext - terminate the current document and open another.
  974. */
  975. typedef struct DLCollector {
  976.   DataBuffer b;
  977.   DLWriter dlw;
  978.   PLWriter plw;
  979. } DLCollector;
  980. /* TODO(shess) This could also be done by calling plwTerminate() and
  981. ** dataBufferAppend().  I tried that, expecting nominal performance
  982. ** differences, but it seemed to pretty reliably be worth 1% to code
  983. ** it this way.  I suspect it is the incremental malloc overhead (some
  984. ** percentage of the plwTerminate() calls will cause a realloc), so
  985. ** this might be worth revisiting if the DataBuffer implementation
  986. ** changes.
  987. */
  988. static void dlcAddDoclist(DLCollector *pCollector, DataBuffer *b){
  989.   if( pCollector->dlw.iType>DL_DOCIDS ){
  990.     char c[VARINT_MAX];
  991.     int n = fts3PutVarint(c, POS_END);
  992.     dataBufferAppend2(b, pCollector->b.pData, pCollector->b.nData, c, n);
  993.   }else{
  994.     dataBufferAppend(b, pCollector->b.pData, pCollector->b.nData);
  995.   }
  996. }
  997. static void dlcNext(DLCollector *pCollector, sqlite_int64 iDocid){
  998.   plwTerminate(&pCollector->plw);
  999.   plwDestroy(&pCollector->plw);
  1000.   plwInit(&pCollector->plw, &pCollector->dlw, iDocid);
  1001. }
  1002. static void dlcAddPos(DLCollector *pCollector, int iColumn, int iPos,
  1003.                       int iStartOffset, int iEndOffset){
  1004.   plwAdd(&pCollector->plw, iColumn, iPos, iStartOffset, iEndOffset);
  1005. }
  1006. static DLCollector *dlcNew(sqlite_int64 iDocid, DocListType iType){
  1007.   DLCollector *pCollector = sqlite3_malloc(sizeof(DLCollector));
  1008.   dataBufferInit(&pCollector->b, 0);
  1009.   dlwInit(&pCollector->dlw, iType, &pCollector->b);
  1010.   plwInit(&pCollector->plw, &pCollector->dlw, iDocid);
  1011.   return pCollector;
  1012. }
  1013. static void dlcDelete(DLCollector *pCollector){
  1014.   plwDestroy(&pCollector->plw);
  1015.   dlwDestroy(&pCollector->dlw);
  1016.   dataBufferDestroy(&pCollector->b);
  1017.   SCRAMBLE(pCollector);
  1018.   sqlite3_free(pCollector);
  1019. }
  1020. /* Copy the doclist data of iType in pData/nData into *out, trimming
  1021. ** unnecessary data as we go.  Only columns matching iColumn are
  1022. ** copied, all columns copied if iColumn is -1.  Elements with no
  1023. ** matching columns are dropped.  The output is an iOutType doclist.
  1024. */
  1025. /* NOTE(shess) This code is only valid after all doclists are merged.
  1026. ** If this is run before merges, then doclist items which represent
  1027. ** deletion will be trimmed, and will thus not effect a deletion
  1028. ** during the merge.
  1029. */
  1030. static void docListTrim(DocListType iType, const char *pData, int nData,
  1031.                         int iColumn, DocListType iOutType, DataBuffer *out){
  1032.   DLReader dlReader;
  1033.   DLWriter dlWriter;
  1034.   assert( iOutType<=iType );
  1035.   dlrInit(&dlReader, iType, pData, nData);
  1036.   dlwInit(&dlWriter, iOutType, out);
  1037.   while( !dlrAtEnd(&dlReader) ){
  1038.     PLReader plReader;
  1039.     PLWriter plWriter;
  1040.     int match = 0;
  1041.     plrInit(&plReader, &dlReader);
  1042.     while( !plrAtEnd(&plReader) ){
  1043.       if( iColumn==-1 || plrColumn(&plReader)==iColumn ){
  1044.         if( !match ){
  1045.           plwInit(&plWriter, &dlWriter, dlrDocid(&dlReader));
  1046.           match = 1;
  1047.         }
  1048.         plwAdd(&plWriter, plrColumn(&plReader), plrPosition(&plReader),
  1049.                plrStartOffset(&plReader), plrEndOffset(&plReader));
  1050.       }
  1051.       plrStep(&plReader);
  1052.     }
  1053.     if( match ){
  1054.       plwTerminate(&plWriter);
  1055.       plwDestroy(&plWriter);
  1056.     }
  1057.     plrDestroy(&plReader);
  1058.     dlrStep(&dlReader);
  1059.   }
  1060.   dlwDestroy(&dlWriter);
  1061.   dlrDestroy(&dlReader);
  1062. }
  1063. /* Used by docListMerge() to keep doclists in the ascending order by
  1064. ** docid, then ascending order by age (so the newest comes first).
  1065. */
  1066. typedef struct OrderedDLReader {
  1067.   DLReader *pReader;
  1068.   /* TODO(shess) If we assume that docListMerge pReaders is ordered by
  1069.   ** age (which we do), then we could use pReader comparisons to break
  1070.   ** ties.
  1071.   */
  1072.   int idx;
  1073. } OrderedDLReader;
  1074. /* Order eof to end, then by docid asc, idx desc. */
  1075. static int orderedDLReaderCmp(OrderedDLReader *r1, OrderedDLReader *r2){
  1076.   if( dlrAtEnd(r1->pReader) ){
  1077.     if( dlrAtEnd(r2->pReader) ) return 0;  /* Both atEnd(). */
  1078.     return 1;                              /* Only r1 atEnd(). */
  1079.   }
  1080.   if( dlrAtEnd(r2->pReader) ) return -1;   /* Only r2 atEnd(). */
  1081.   if( dlrDocid(r1->pReader)<dlrDocid(r2->pReader) ) return -1;
  1082.   if( dlrDocid(r1->pReader)>dlrDocid(r2->pReader) ) return 1;
  1083.   /* Descending on idx. */
  1084.   return r2->idx-r1->idx;
  1085. }
  1086. /* Bubble p[0] to appropriate place in p[1..n-1].  Assumes that
  1087. ** p[1..n-1] is already sorted.
  1088. */
  1089. /* TODO(shess) Is this frequent enough to warrant a binary search?
  1090. ** Before implementing that, instrument the code to check.  In most
  1091. ** current usage, I expect that p[0] will be less than p[1] a very
  1092. ** high proportion of the time.
  1093. */
  1094. static void orderedDLReaderReorder(OrderedDLReader *p, int n){
  1095.   while( n>1 && orderedDLReaderCmp(p, p+1)>0 ){
  1096.     OrderedDLReader tmp = p[0];
  1097.     p[0] = p[1];
  1098.     p[1] = tmp;
  1099.     n--;
  1100.     p++;
  1101.   }
  1102. }
  1103. /* Given an array of doclist readers, merge their doclist elements
  1104. ** into out in sorted order (by docid), dropping elements from older
  1105. ** readers when there is a duplicate docid.  pReaders is assumed to be
  1106. ** ordered by age, oldest first.
  1107. */
  1108. /* TODO(shess) nReaders must be <= MERGE_COUNT.  This should probably
  1109. ** be fixed.
  1110. */
  1111. static void docListMerge(DataBuffer *out,
  1112.                          DLReader *pReaders, int nReaders){
  1113.   OrderedDLReader readers[MERGE_COUNT];
  1114.   DLWriter writer;
  1115.   int i, n;
  1116.   const char *pStart = 0;
  1117.   int nStart = 0;
  1118.   sqlite_int64 iFirstDocid = 0, iLastDocid = 0;
  1119.   assert( nReaders>0 );
  1120.   if( nReaders==1 ){
  1121.     dataBufferAppend(out, dlrDocData(pReaders), dlrAllDataBytes(pReaders));
  1122.     return;
  1123.   }
  1124.   assert( nReaders<=MERGE_COUNT );
  1125.   n = 0;
  1126.   for(i=0; i<nReaders; i++){
  1127.     assert( pReaders[i].iType==pReaders[0].iType );
  1128.     readers[i].pReader = pReaders+i;
  1129.     readers[i].idx = i;
  1130.     n += dlrAllDataBytes(&pReaders[i]);
  1131.   }
  1132.   /* Conservatively size output to sum of inputs.  Output should end
  1133.   ** up strictly smaller than input.
  1134.   */
  1135.   dataBufferExpand(out, n);
  1136.   /* Get the readers into sorted order. */
  1137.   while( i-->0 ){
  1138.     orderedDLReaderReorder(readers+i, nReaders-i);
  1139.   }
  1140.   dlwInit(&writer, pReaders[0].iType, out);
  1141.   while( !dlrAtEnd(readers[0].pReader) ){
  1142.     sqlite_int64 iDocid = dlrDocid(readers[0].pReader);
  1143.     /* If this is a continuation of the current buffer to copy, extend
  1144.     ** that buffer.  memcpy() seems to be more efficient if it has a
  1145.     ** lots of data to copy.
  1146.     */
  1147.     if( dlrDocData(readers[0].pReader)==pStart+nStart ){
  1148.       nStart += dlrDocDataBytes(readers[0].pReader);
  1149.     }else{
  1150.       if( pStart!=0 ){
  1151.         dlwAppend(&writer, pStart, nStart, iFirstDocid, iLastDocid);
  1152.       }
  1153.       pStart = dlrDocData(readers[0].pReader);
  1154.       nStart = dlrDocDataBytes(readers[0].pReader);
  1155.       iFirstDocid = iDocid;
  1156.     }
  1157.     iLastDocid = iDocid;
  1158.     dlrStep(readers[0].pReader);
  1159.     /* Drop all of the older elements with the same docid. */
  1160.     for(i=1; i<nReaders &&
  1161.              !dlrAtEnd(readers[i].pReader) &&
  1162.              dlrDocid(readers[i].pReader)==iDocid; i++){
  1163.       dlrStep(readers[i].pReader);
  1164.     }
  1165.     /* Get the readers back into order. */
  1166.     while( i-->0 ){
  1167.       orderedDLReaderReorder(readers+i, nReaders-i);
  1168.     }
  1169.   }
  1170.   /* Copy over any remaining elements. */
  1171.   if( nStart>0 ) dlwAppend(&writer, pStart, nStart, iFirstDocid, iLastDocid);
  1172.   dlwDestroy(&writer);
  1173. }
  1174. /* Helper function for posListUnion().  Compares the current position
  1175. ** between left and right, returning as standard C idiom of <0 if
  1176. ** left<right, >0 if left>right, and 0 if left==right.  "End" always
  1177. ** compares greater.
  1178. */
  1179. static int posListCmp(PLReader *pLeft, PLReader *pRight){
  1180.   assert( pLeft->iType==pRight->iType );
  1181.   if( pLeft->iType==DL_DOCIDS ) return 0;
  1182.   if( plrAtEnd(pLeft) ) return plrAtEnd(pRight) ? 0 : 1;
  1183.   if( plrAtEnd(pRight) ) return -1;
  1184.   if( plrColumn(pLeft)<plrColumn(pRight) ) return -1;
  1185.   if( plrColumn(pLeft)>plrColumn(pRight) ) return 1;
  1186.   if( plrPosition(pLeft)<plrPosition(pRight) ) return -1;
  1187.   if( plrPosition(pLeft)>plrPosition(pRight) ) return 1;
  1188.   if( pLeft->iType==DL_POSITIONS ) return 0;
  1189.   if( plrStartOffset(pLeft)<plrStartOffset(pRight) ) return -1;
  1190.   if( plrStartOffset(pLeft)>plrStartOffset(pRight) ) return 1;
  1191.   if( plrEndOffset(pLeft)<plrEndOffset(pRight) ) return -1;
  1192.   if( plrEndOffset(pLeft)>plrEndOffset(pRight) ) return 1;
  1193.   return 0;
  1194. }
  1195. /* Write the union of position lists in pLeft and pRight to pOut.
  1196. ** "Union" in this case meaning "All unique position tuples".  Should
  1197. ** work with any doclist type, though both inputs and the output
  1198. ** should be the same type.
  1199. */
  1200. static void posListUnion(DLReader *pLeft, DLReader *pRight, DLWriter *pOut){
  1201.   PLReader left, right;
  1202.   PLWriter writer;
  1203.   assert( dlrDocid(pLeft)==dlrDocid(pRight) );
  1204.   assert( pLeft->iType==pRight->iType );
  1205.   assert( pLeft->iType==pOut->iType );
  1206.   plrInit(&left, pLeft);
  1207.   plrInit(&right, pRight);
  1208.   plwInit(&writer, pOut, dlrDocid(pLeft));
  1209.   while( !plrAtEnd(&left) || !plrAtEnd(&right) ){
  1210.     int c = posListCmp(&left, &right);
  1211.     if( c<0 ){
  1212.       plwCopy(&writer, &left);
  1213.       plrStep(&left);
  1214.     }else if( c>0 ){
  1215.       plwCopy(&writer, &right);
  1216.       plrStep(&right);
  1217.     }else{
  1218.       plwCopy(&writer, &left);
  1219.       plrStep(&left);
  1220.       plrStep(&right);
  1221.     }
  1222.   }
  1223.   plwTerminate(&writer);
  1224.   plwDestroy(&writer);
  1225.   plrDestroy(&left);
  1226.   plrDestroy(&right);
  1227. }
  1228. /* Write the union of doclists in pLeft and pRight to pOut.  For
  1229. ** docids in common between the inputs, the union of the position
  1230. ** lists is written.  Inputs and outputs are always type DL_DEFAULT.
  1231. */
  1232. static void docListUnion(
  1233.   const char *pLeft, int nLeft,
  1234.   const char *pRight, int nRight,
  1235.   DataBuffer *pOut      /* Write the combined doclist here */
  1236. ){
  1237.   DLReader left, right;
  1238.   DLWriter writer;
  1239.   if( nLeft==0 ){
  1240.     if( nRight!=0) dataBufferAppend(pOut, pRight, nRight);
  1241.     return;
  1242.   }
  1243.   if( nRight==0 ){
  1244.     dataBufferAppend(pOut, pLeft, nLeft);
  1245.     return;
  1246.   }
  1247.   dlrInit(&left, DL_DEFAULT, pLeft, nLeft);
  1248.   dlrInit(&right, DL_DEFAULT, pRight, nRight);
  1249.   dlwInit(&writer, DL_DEFAULT, pOut);
  1250.   while( !dlrAtEnd(&left) || !dlrAtEnd(&right) ){
  1251.     if( dlrAtEnd(&right) ){
  1252.       dlwCopy(&writer, &left);
  1253.       dlrStep(&left);
  1254.     }else if( dlrAtEnd(&left) ){
  1255.       dlwCopy(&writer, &right);
  1256.       dlrStep(&right);
  1257.     }else if( dlrDocid(&left)<dlrDocid(&right) ){
  1258.       dlwCopy(&writer, &left);
  1259.       dlrStep(&left);
  1260.     }else if( dlrDocid(&left)>dlrDocid(&right) ){
  1261.       dlwCopy(&writer, &right);
  1262.       dlrStep(&right);
  1263.     }else{
  1264.       posListUnion(&left, &right, &writer);
  1265.       dlrStep(&left);
  1266.       dlrStep(&right);
  1267.     }
  1268.   }
  1269.   dlrDestroy(&left);
  1270.   dlrDestroy(&right);
  1271.   dlwDestroy(&writer);
  1272. }
  1273. /* 
  1274. ** This function is used as part of the implementation of phrase and
  1275. ** NEAR matching.
  1276. **
  1277. ** pLeft and pRight are DLReaders positioned to the same docid in
  1278. ** lists of type DL_POSITION. This function writes an entry to the
  1279. ** DLWriter pOut for each position in pRight that is less than
  1280. ** (nNear+1) greater (but not equal to or smaller) than a position 
  1281. ** in pLeft. For example, if nNear is 0, and the positions contained
  1282. ** by pLeft and pRight are:
  1283. **
  1284. **    pLeft:  5 10 15 20
  1285. **    pRight: 6  9 17 21
  1286. **
  1287. ** then the docid is added to pOut. If pOut is of type DL_POSITIONS,
  1288. ** then a positionids "6" and "21" are also added to pOut.
  1289. **
  1290. ** If boolean argument isSaveLeft is true, then positionids are copied
  1291. ** from pLeft instead of pRight. In the example above, the positions "5"
  1292. ** and "20" would be added instead of "6" and "21".
  1293. */
  1294. static void posListPhraseMerge(
  1295.   DLReader *pLeft, 
  1296.   DLReader *pRight,
  1297.   int nNear,
  1298.   int isSaveLeft,
  1299.   DLWriter *pOut
  1300. ){
  1301.   PLReader left, right;
  1302.   PLWriter writer;
  1303.   int match = 0;
  1304.   assert( dlrDocid(pLeft)==dlrDocid(pRight) );
  1305.   assert( pOut->iType!=DL_POSITIONS_OFFSETS );
  1306.   plrInit(&left, pLeft);
  1307.   plrInit(&right, pRight);
  1308.   while( !plrAtEnd(&left) && !plrAtEnd(&right) ){
  1309.     if( plrColumn(&left)<plrColumn(&right) ){
  1310.       plrStep(&left);
  1311.     }else if( plrColumn(&left)>plrColumn(&right) ){
  1312.       plrStep(&right);
  1313.     }else if( plrPosition(&left)>=plrPosition(&right) ){
  1314.       plrStep(&right);
  1315.     }else{
  1316.       if( (plrPosition(&right)-plrPosition(&left))<=(nNear+1) ){
  1317.         if( !match ){
  1318.           plwInit(&writer, pOut, dlrDocid(pLeft));
  1319.           match = 1;
  1320.         }
  1321.         if( !isSaveLeft ){
  1322.           plwAdd(&writer, plrColumn(&right), plrPosition(&right), 0, 0);
  1323.         }else{
  1324.           plwAdd(&writer, plrColumn(&left), plrPosition(&left), 0, 0);
  1325.         }
  1326.         plrStep(&right);
  1327.       }else{
  1328.         plrStep(&left);
  1329.       }
  1330.     }
  1331.   }
  1332.   if( match ){
  1333.     plwTerminate(&writer);
  1334.     plwDestroy(&writer);
  1335.   }
  1336.   plrDestroy(&left);
  1337.   plrDestroy(&right);
  1338. }
  1339. /*
  1340. ** Compare the values pointed to by the PLReaders passed as arguments. 
  1341. ** Return -1 if the value pointed to by pLeft is considered less than
  1342. ** the value pointed to by pRight, +1 if it is considered greater
  1343. ** than it, or 0 if it is equal. i.e.
  1344. **
  1345. **     (*pLeft - *pRight)
  1346. **
  1347. ** A PLReader that is in the EOF condition is considered greater than
  1348. ** any other. If neither argument is in EOF state, the return value of
  1349. ** plrColumn() is used. If the plrColumn() values are equal, the
  1350. ** comparison is on the basis of plrPosition().
  1351. */
  1352. static int plrCompare(PLReader *pLeft, PLReader *pRight){
  1353.   assert(!plrAtEnd(pLeft) || !plrAtEnd(pRight));
  1354.   if( plrAtEnd(pRight) || plrAtEnd(pLeft) ){
  1355.     return (plrAtEnd(pRight) ? -1 : 1);
  1356.   }
  1357.   if( plrColumn(pLeft)!=plrColumn(pRight) ){
  1358.     return ((plrColumn(pLeft)<plrColumn(pRight)) ? -1 : 1);
  1359.   }
  1360.   if( plrPosition(pLeft)!=plrPosition(pRight) ){
  1361.     return ((plrPosition(pLeft)<plrPosition(pRight)) ? -1 : 1);
  1362.   }
  1363.   return 0;
  1364. }
  1365. /* We have two doclists with positions:  pLeft and pRight. Depending
  1366. ** on the value of the nNear parameter, perform either a phrase
  1367. ** intersection (if nNear==0) or a NEAR intersection (if nNear>0)
  1368. ** and write the results into pOut.
  1369. **
  1370. ** A phrase intersection means that two documents only match
  1371. ** if pLeft.iPos+1==pRight.iPos.
  1372. **
  1373. ** A NEAR intersection means that two documents only match if 
  1374. ** (abs(pLeft.iPos-pRight.iPos)<nNear).
  1375. **
  1376. ** If a NEAR intersection is requested, then the nPhrase argument should
  1377. ** be passed the number of tokens in the two operands to the NEAR operator
  1378. ** combined. For example:
  1379. **
  1380. **       Query syntax               nPhrase
  1381. **      ------------------------------------
  1382. **       "A B C" NEAR "D E"         5
  1383. **       A NEAR B                   2
  1384. **
  1385. ** iType controls the type of data written to pOut.  If iType is
  1386. ** DL_POSITIONS, the positions are those from pRight.
  1387. */
  1388. static void docListPhraseMerge(
  1389.   const char *pLeft, int nLeft,
  1390.   const char *pRight, int nRight,
  1391.   int nNear,            /* 0 for a phrase merge, non-zero for a NEAR merge */
  1392.   int nPhrase,          /* Number of tokens in left+right operands to NEAR */
  1393.   DocListType iType,    /* Type of doclist to write to pOut */
  1394.   DataBuffer *pOut      /* Write the combined doclist here */
  1395. ){
  1396.   DLReader left, right;
  1397.   DLWriter writer;
  1398.   if( nLeft==0 || nRight==0 ) return;
  1399.   assert( iType!=DL_POSITIONS_OFFSETS );
  1400.   dlrInit(&left, DL_POSITIONS, pLeft, nLeft);
  1401.   dlrInit(&right, DL_POSITIONS, pRight, nRight);
  1402.   dlwInit(&writer, iType, pOut);
  1403.   while( !dlrAtEnd(&left) && !dlrAtEnd(&right) ){
  1404.     if( dlrDocid(&left)<dlrDocid(&right) ){
  1405.       dlrStep(&left);
  1406.     }else if( dlrDocid(&right)<dlrDocid(&left) ){
  1407.       dlrStep(&right);
  1408.     }else{
  1409.       if( nNear==0 ){
  1410.         posListPhraseMerge(&left, &right, 0, 0, &writer);
  1411.       }else{
  1412.         /* This case occurs when two terms (simple terms or phrases) are
  1413.          * connected by a NEAR operator, span (nNear+1). i.e.
  1414.          *
  1415.          *     '"terrible company" NEAR widget'
  1416.          */
  1417.         DataBuffer one = {0, 0, 0};
  1418.         DataBuffer two = {0, 0, 0};
  1419.         DLWriter dlwriter2;
  1420.         DLReader dr1 = {0, 0, 0, 0, 0}; 
  1421.         DLReader dr2 = {0, 0, 0, 0, 0};
  1422.         dlwInit(&dlwriter2, iType, &one);
  1423.         posListPhraseMerge(&right, &left, nNear-3+nPhrase, 1, &dlwriter2);
  1424.         dlwInit(&dlwriter2, iType, &two);
  1425.         posListPhraseMerge(&left, &right, nNear-1, 0, &dlwriter2);
  1426.         if( one.nData) dlrInit(&dr1, iType, one.pData, one.nData);
  1427.         if( two.nData) dlrInit(&dr2, iType, two.pData, two.nData);
  1428.         if( !dlrAtEnd(&dr1) || !dlrAtEnd(&dr2) ){
  1429.           PLReader pr1 = {0};
  1430.           PLReader pr2 = {0};
  1431.           PLWriter plwriter;
  1432.           plwInit(&plwriter, &writer, dlrDocid(dlrAtEnd(&dr1)?&dr2:&dr1));
  1433.           if( one.nData ) plrInit(&pr1, &dr1);
  1434.           if( two.nData ) plrInit(&pr2, &dr2);
  1435.           while( !plrAtEnd(&pr1) || !plrAtEnd(&pr2) ){
  1436.             int iCompare = plrCompare(&pr1, &pr2);
  1437.             switch( iCompare ){
  1438.               case -1:
  1439.                 plwCopy(&plwriter, &pr1);
  1440.                 plrStep(&pr1);
  1441.                 break;
  1442.               case 1:
  1443.                 plwCopy(&plwriter, &pr2);
  1444.                 plrStep(&pr2);
  1445.                 break;
  1446.               case 0:
  1447.                 plwCopy(&plwriter, &pr1);
  1448.                 plrStep(&pr1);
  1449.                 plrStep(&pr2);
  1450.                 break;
  1451.             }
  1452.           }
  1453.           plwTerminate(&plwriter);
  1454.         }
  1455.         dataBufferDestroy(&one);
  1456.         dataBufferDestroy(&two);
  1457.       }
  1458.       dlrStep(&left);
  1459.       dlrStep(&right);
  1460.     }
  1461.   }
  1462.   dlrDestroy(&left);
  1463.   dlrDestroy(&right);
  1464.   dlwDestroy(&writer);
  1465. }
  1466. /* We have two DL_DOCIDS doclists:  pLeft and pRight.
  1467. ** Write the intersection of these two doclists into pOut as a
  1468. ** DL_DOCIDS doclist.
  1469. */
  1470. static void docListAndMerge(
  1471.   const char *pLeft, int nLeft,
  1472.   const char *pRight, int nRight,
  1473.   DataBuffer *pOut      /* Write the combined doclist here */
  1474. ){
  1475.   DLReader left, right;
  1476.   DLWriter writer;
  1477.   if( nLeft==0 || nRight==0 ) return;
  1478.   dlrInit(&left, DL_DOCIDS, pLeft, nLeft);
  1479.   dlrInit(&right, DL_DOCIDS, pRight, nRight);
  1480.   dlwInit(&writer, DL_DOCIDS, pOut);
  1481.   while( !dlrAtEnd(&left) && !dlrAtEnd(&right) ){
  1482.     if( dlrDocid(&left)<dlrDocid(&right) ){
  1483.       dlrStep(&left);
  1484.     }else if( dlrDocid(&right)<dlrDocid(&left) ){
  1485.       dlrStep(&right);
  1486.     }else{
  1487.       dlwAdd(&writer, dlrDocid(&left));
  1488.       dlrStep(&left);
  1489.       dlrStep(&right);
  1490.     }
  1491.   }
  1492.   dlrDestroy(&left);
  1493.   dlrDestroy(&right);
  1494.   dlwDestroy(&writer);
  1495. }
  1496. /* We have two DL_DOCIDS doclists:  pLeft and pRight.
  1497. ** Write the union of these two doclists into pOut as a
  1498. ** DL_DOCIDS doclist.
  1499. */
  1500. static void docListOrMerge(
  1501.   const char *pLeft, int nLeft,
  1502.   const char *pRight, int nRight,
  1503.   DataBuffer *pOut      /* Write the combined doclist here */
  1504. ){
  1505.   DLReader left, right;
  1506.   DLWriter writer;
  1507.   if( nLeft==0 ){
  1508.     if( nRight!=0 ) dataBufferAppend(pOut, pRight, nRight);
  1509.     return;
  1510.   }
  1511.   if( nRight==0 ){
  1512.     dataBufferAppend(pOut, pLeft, nLeft);
  1513.     return;
  1514.   }
  1515.   dlrInit(&left, DL_DOCIDS, pLeft, nLeft);
  1516.   dlrInit(&right, DL_DOCIDS, pRight, nRight);
  1517.   dlwInit(&writer, DL_DOCIDS, pOut);
  1518.   while( !dlrAtEnd(&left) || !dlrAtEnd(&right) ){
  1519.     if( dlrAtEnd(&right) ){
  1520.       dlwAdd(&writer, dlrDocid(&left));
  1521.       dlrStep(&left);
  1522.     }else if( dlrAtEnd(&left) ){
  1523.       dlwAdd(&writer, dlrDocid(&right));
  1524.       dlrStep(&right);
  1525.     }else if( dlrDocid(&left)<dlrDocid(&right) ){
  1526.       dlwAdd(&writer, dlrDocid(&left));
  1527.       dlrStep(&left);
  1528.     }else if( dlrDocid(&right)<dlrDocid(&left) ){
  1529.       dlwAdd(&writer, dlrDocid(&right));
  1530.       dlrStep(&right);
  1531.     }else{
  1532.       dlwAdd(&writer, dlrDocid(&left));
  1533.       dlrStep(&left);
  1534.       dlrStep(&right);
  1535.     }
  1536.   }
  1537.   dlrDestroy(&left);
  1538.   dlrDestroy(&right);
  1539.   dlwDestroy(&writer);
  1540. }
  1541. /* We have two DL_DOCIDS doclists:  pLeft and pRight.
  1542. ** Write into pOut as DL_DOCIDS doclist containing all documents that
  1543. ** occur in pLeft but not in pRight.
  1544. */
  1545. static void docListExceptMerge(
  1546.   const char *pLeft, int nLeft,
  1547.   const char *pRight, int nRight,
  1548.   DataBuffer *pOut      /* Write the combined doclist here */
  1549. ){
  1550.   DLReader left, right;
  1551.   DLWriter writer;
  1552.   if( nLeft==0 ) return;
  1553.   if( nRight==0 ){
  1554.     dataBufferAppend(pOut, pLeft, nLeft);
  1555.     return;
  1556.   }
  1557.   dlrInit(&left, DL_DOCIDS, pLeft, nLeft);
  1558.   dlrInit(&right, DL_DOCIDS, pRight, nRight);
  1559.   dlwInit(&writer, DL_DOCIDS, pOut);
  1560.   while( !dlrAtEnd(&left) ){
  1561.     while( !dlrAtEnd(&right) && dlrDocid(&right)<dlrDocid(&left) ){
  1562.       dlrStep(&right);
  1563.     }
  1564.     if( dlrAtEnd(&right) || dlrDocid(&left)<dlrDocid(&right) ){
  1565.       dlwAdd(&writer, dlrDocid(&left));
  1566.     }
  1567.     dlrStep(&left);
  1568.   }
  1569.   dlrDestroy(&left);
  1570.   dlrDestroy(&right);
  1571.   dlwDestroy(&writer);
  1572. }
  1573. static char *string_dup_n(const char *s, int n){
  1574.   char *str = sqlite3_malloc(n + 1);
  1575.   memcpy(str, s, n);
  1576.   str[n] = '';
  1577.   return str;
  1578. }
  1579. /* Duplicate a string; the caller must free() the returned string.
  1580.  * (We don't use strdup() since it is not part of the standard C library and
  1581.  * may not be available everywhere.) */
  1582. static char *string_dup(const char *s){
  1583.   return string_dup_n(s, strlen(s));
  1584. }
  1585. /* Format a string, replacing each occurrence of the % character with
  1586.  * zDb.zName.  This may be more convenient than sqlite_mprintf()
  1587.  * when one string is used repeatedly in a format string.
  1588.  * The caller must free() the returned string. */
  1589. static char *string_format(const char *zFormat,
  1590.                            const char *zDb, const char *zName){
  1591.   const char *p;
  1592.   size_t len = 0;
  1593.   size_t nDb = strlen(zDb);
  1594.   size_t nName = strlen(zName);
  1595.   size_t nFullTableName = nDb+1+nName;
  1596.   char *result;
  1597.   char *r;
  1598.   /* first compute length needed */
  1599.   for(p = zFormat ; *p ; ++p){
  1600.     len += (*p=='%' ? nFullTableName : 1);
  1601.   }
  1602.   len += 1;  /* for null terminator */
  1603.   r = result = sqlite3_malloc(len);
  1604.   for(p = zFormat; *p; ++p){
  1605.     if( *p=='%' ){
  1606.       memcpy(r, zDb, nDb);
  1607.       r += nDb;
  1608.       *r++ = '.';
  1609.       memcpy(r, zName, nName);
  1610.       r += nName;
  1611.     } else {
  1612.       *r++ = *p;
  1613.     }
  1614.   }
  1615.   *r++ = '';
  1616.   assert( r == result + len );
  1617.   return result;
  1618. }
  1619. static int sql_exec(sqlite3 *db, const char *zDb, const char *zName,
  1620.                     const char *zFormat){
  1621.   char *zCommand = string_format(zFormat, zDb, zName);
  1622.   int rc;
  1623.   FTSTRACE(("FTS3 sql: %sn", zCommand));
  1624.   rc = sqlite3_exec(db, zCommand, NULL, 0, NULL);
  1625.   sqlite3_free(zCommand);
  1626.   return rc;
  1627. }
  1628. static int sql_prepare(sqlite3 *db, const char *zDb, const char *zName,
  1629.                        sqlite3_stmt **ppStmt, const char *zFormat){
  1630.   char *zCommand = string_format(zFormat, zDb, zName);
  1631.   int rc;
  1632.   FTSTRACE(("FTS3 prepare: %sn", zCommand));
  1633.   rc = sqlite3_prepare_v2(db, zCommand, -1, ppStmt, NULL);
  1634.   sqlite3_free(zCommand);
  1635.   return rc;
  1636. }
  1637. /* end utility functions */
  1638. /* Forward reference */
  1639. typedef struct fulltext_vtab fulltext_vtab;
  1640. /* A single term in a query is represented by an instances of
  1641. ** the following structure. Each word which may match against
  1642. ** document content is a term. Operators, like NEAR or OR, are
  1643. ** not terms. Query terms are organized as a flat list stored
  1644. ** in the Query.pTerms array.
  1645. **
  1646. ** If the QueryTerm.nPhrase variable is non-zero, then the QueryTerm
  1647. ** is the first in a contiguous string of terms that are either part
  1648. ** of the same phrase, or connected by the NEAR operator.
  1649. **
  1650. ** If the QueryTerm.nNear variable is non-zero, then the token is followed 
  1651. ** by a NEAR operator with span set to (nNear-1). For example, the 
  1652. ** following query:
  1653. **
  1654. ** The QueryTerm.iPhrase variable stores the index of the token within
  1655. ** its phrase, indexed starting at 1, or 1 if the token is not part 
  1656. ** of any phrase.
  1657. **
  1658. ** For example, the data structure used to represent the following query:
  1659. **
  1660. **     ... MATCH 'sqlite NEAR/5 google NEAR/2 "search engine"'
  1661. **
  1662. ** is:
  1663. **
  1664. **     {nPhrase=4, iPhrase=1, nNear=6, pTerm="sqlite"},
  1665. **     {nPhrase=0, iPhrase=1, nNear=3, pTerm="google"},
  1666. **     {nPhrase=0, iPhrase=1, nNear=0, pTerm="search"},
  1667. **     {nPhrase=0, iPhrase=2, nNear=0, pTerm="engine"},
  1668. **
  1669. ** compiling the FTS3 syntax to Query structures is done by the parseQuery()
  1670. ** function.
  1671. */
  1672. typedef struct QueryTerm {
  1673.   short int nPhrase; /* How many following terms are part of the same phrase */
  1674.   short int iPhrase; /* This is the i-th term of a phrase. */
  1675.   short int iColumn; /* Column of the index that must match this term */
  1676.   signed char nNear; /* term followed by a NEAR operator with span=(nNear-1) */
  1677.   signed char isOr;  /* this term is preceded by "OR" */
  1678.   signed char isNot; /* this term is preceded by "-" */
  1679.   signed char isPrefix; /* this term is followed by "*" */
  1680.   char *pTerm;       /* text of the term.  '00' terminated.  malloced */
  1681.   int nTerm;         /* Number of bytes in pTerm[] */
  1682. } QueryTerm;
  1683. /* A query string is parsed into a Query structure.
  1684.  *
  1685.  * We could, in theory, allow query strings to be complicated
  1686.  * nested expressions with precedence determined by parentheses.
  1687.  * But none of the major search engines do this.  (Perhaps the
  1688.  * feeling is that an parenthesized expression is two complex of
  1689.  * an idea for the average user to grasp.)  Taking our lead from
  1690.  * the major search engines, we will allow queries to be a list
  1691.  * of terms (with an implied AND operator) or phrases in double-quotes,
  1692.  * with a single optional "-" before each non-phrase term to designate
  1693.  * negation and an optional OR connector.
  1694.  *
  1695.  * OR binds more tightly than the implied AND, which is what the
  1696.  * major search engines seem to do.  So, for example:
  1697.  * 
  1698.  *    [one two OR three]     ==>    one AND (two OR three)
  1699.  *    [one OR two three]     ==>    (one OR two) AND three
  1700.  *
  1701.  * A "-" before a term matches all entries that lack that term.
  1702.  * The "-" must occur immediately before the term with in intervening
  1703.  * space.  This is how the search engines do it.
  1704.  *
  1705.  * A NOT term cannot be the right-hand operand of an OR.  If this
  1706.  * occurs in the query string, the NOT is ignored:
  1707.  *
  1708.  *    [one OR -two]          ==>    one OR two
  1709.  *
  1710.  */
  1711. typedef struct Query {
  1712.   fulltext_vtab *pFts;  /* The full text index */
  1713.   int nTerms;           /* Number of terms in the query */
  1714.   QueryTerm *pTerms;    /* Array of terms.  Space obtained from malloc() */
  1715.   int nextIsOr;         /* Set the isOr flag on the next inserted term */
  1716.   int nextIsNear;       /* Set the isOr flag on the next inserted term */
  1717.   int nextColumn;       /* Next word parsed must be in this column */
  1718.   int dfltColumn;       /* The default column */
  1719. } Query;
  1720. /*
  1721. ** An instance of the following structure keeps track of generated
  1722. ** matching-word offset information and snippets.
  1723. */
  1724. typedef struct Snippet {
  1725.   int nMatch;     /* Total number of matches */
  1726.   int nAlloc;     /* Space allocated for aMatch[] */
  1727.   struct snippetMatch { /* One entry for each matching term */
  1728.     char snStatus;       /* Status flag for use while constructing snippets */
  1729.     short int iCol;      /* The column that contains the match */
  1730.     short int iTerm;     /* The index in Query.pTerms[] of the matching term */
  1731.     int iToken;          /* The index of the matching document token */
  1732.     short int nByte;     /* Number of bytes in the term */
  1733.     int iStart;          /* The offset to the first character of the term */
  1734.   } *aMatch;      /* Points to space obtained from malloc */
  1735.   char *zOffset;  /* Text rendering of aMatch[] */
  1736.   int nOffset;    /* strlen(zOffset) */
  1737.   char *zSnippet; /* Snippet text */
  1738.   int nSnippet;   /* strlen(zSnippet) */
  1739. } Snippet;
  1740. typedef enum QueryType {
  1741.   QUERY_GENERIC,   /* table scan */
  1742.   QUERY_DOCID,     /* lookup by docid */
  1743.   QUERY_FULLTEXT   /* QUERY_FULLTEXT + [i] is a full-text search for column i*/
  1744. } QueryType;
  1745. typedef enum fulltext_statement {
  1746.   CONTENT_INSERT_STMT,
  1747.   CONTENT_SELECT_STMT,
  1748.   CONTENT_UPDATE_STMT,
  1749.   CONTENT_DELETE_STMT,
  1750.   BLOCK_INSERT_STMT,
  1751.   BLOCK_SELECT_STMT,
  1752.   BLOCK_DELETE_STMT,
  1753.   SEGDIR_MAX_INDEX_STMT,
  1754.   SEGDIR_SET_STMT,
  1755.   SEGDIR_SELECT_STMT,
  1756.   SEGDIR_SPAN_STMT,
  1757.   SEGDIR_DELETE_STMT,
  1758.   SEGDIR_SELECT_ALL_STMT,
  1759.   MAX_STMT                     /* Always at end! */
  1760. } fulltext_statement;
  1761. /* These must exactly match the enum above. */
  1762. /* TODO(shess): Is there some risk that a statement will be used in two
  1763. ** cursors at once, e.g.  if a query joins a virtual table to itself?
  1764. ** If so perhaps we should move some of these to the cursor object.
  1765. */
  1766. static const char *const fulltext_zStatement[MAX_STMT] = {
  1767.   /* CONTENT_INSERT */ NULL,  /* generated in contentInsertStatement() */
  1768.   /* CONTENT_SELECT */ NULL,  /* generated in contentSelectStatement() */
  1769.   /* CONTENT_UPDATE */ NULL,  /* generated in contentUpdateStatement() */
  1770.   /* CONTENT_DELETE */ "delete from %_content where docid = ?",
  1771.   /* BLOCK_INSERT */
  1772.   "insert into %_segments (blockid, block) values (null, ?)",
  1773.   /* BLOCK_SELECT */ "select block from %_segments where blockid = ?",
  1774.   /* BLOCK_DELETE */ "delete from %_segments where blockid between ? and ?",
  1775.   /* SEGDIR_MAX_INDEX */ "select max(idx) from %_segdir where level = ?",
  1776.   /* SEGDIR_SET */ "insert into %_segdir values (?, ?, ?, ?, ?, ?)",
  1777.   /* SEGDIR_SELECT */
  1778.   "select start_block, leaves_end_block, root from %_segdir "
  1779.   " where level = ? order by idx",
  1780.   /* SEGDIR_SPAN */
  1781.   "select min(start_block), max(end_block) from %_segdir "
  1782.   " where level = ? and start_block <> 0",
  1783.   /* SEGDIR_DELETE */ "delete from %_segdir where level = ?",
  1784.   /* SEGDIR_SELECT_ALL */
  1785.   "select root, leaves_end_block from %_segdir order by level desc, idx",
  1786. };
  1787. /*
  1788. ** A connection to a fulltext index is an instance of the following
  1789. ** structure.  The xCreate and xConnect methods create an instance
  1790. ** of this structure and xDestroy and xDisconnect free that instance.
  1791. ** All other methods receive a pointer to the structure as one of their
  1792. ** arguments.
  1793. */
  1794. struct fulltext_vtab {
  1795.   sqlite3_vtab base;               /* Base class used by SQLite core */
  1796.   sqlite3 *db;                     /* The database connection */
  1797.   const char *zDb;                 /* logical database name */
  1798.   const char *zName;               /* virtual table name */
  1799.   int nColumn;                     /* number of columns in virtual table */
  1800.   char **azColumn;                 /* column names.  malloced */
  1801.   char **azContentColumn;          /* column names in content table; malloced */
  1802.   sqlite3_tokenizer *pTokenizer;   /* tokenizer for inserts and queries */
  1803.   /* Precompiled statements which we keep as long as the table is
  1804.   ** open.
  1805.   */
  1806.   sqlite3_stmt *pFulltextStatements[MAX_STMT];
  1807.   /* Precompiled statements used for segment merges.  We run a
  1808.   ** separate select across the leaf level of each tree being merged.
  1809.   */
  1810.   sqlite3_stmt *pLeafSelectStmts[MERGE_COUNT];
  1811.   /* The statement used to prepare pLeafSelectStmts. */
  1812. #define LEAF_SELECT 
  1813.   "select block from %_segments where blockid between ? and ? order by blockid"
  1814.   /* These buffer pending index updates during transactions.
  1815.   ** nPendingData estimates the memory size of the pending data.  It
  1816.   ** doesn't include the hash-bucket overhead, nor any malloc
  1817.   ** overhead.  When nPendingData exceeds kPendingThreshold, the
  1818.   ** buffer is flushed even before the transaction closes.
  1819.   ** pendingTerms stores the data, and is only valid when nPendingData
  1820.   ** is >=0 (nPendingData<0 means pendingTerms has not been
  1821.   ** initialized).  iPrevDocid is the last docid written, used to make
  1822.   ** certain we're inserting in sorted order.
  1823.   */
  1824.   int nPendingData;
  1825. #define kPendingThreshold (1*1024*1024)
  1826.   sqlite_int64 iPrevDocid;
  1827.   fts3Hash pendingTerms;
  1828. };
  1829. /*
  1830. ** When the core wants to do a query, it create a cursor using a
  1831. ** call to xOpen.  This structure is an instance of a cursor.  It
  1832. ** is destroyed by xClose.
  1833. */
  1834. typedef struct fulltext_cursor {
  1835.   sqlite3_vtab_cursor base;        /* Base class used by SQLite core */
  1836.   QueryType iCursorType;           /* Copy of sqlite3_index_info.idxNum */
  1837.   sqlite3_stmt *pStmt;             /* Prepared statement in use by the cursor */
  1838.   int eof;                         /* True if at End Of Results */
  1839.   Query q;                         /* Parsed query string */
  1840.   Snippet snippet;                 /* Cached snippet for the current row */
  1841.   int iColumn;                     /* Column being searched */
  1842.   DataBuffer result;               /* Doclist results from fulltextQuery */
  1843.   DLReader reader;                 /* Result reader if result not empty */
  1844. } fulltext_cursor;
  1845. static struct fulltext_vtab *cursor_vtab(fulltext_cursor *c){
  1846.   return (fulltext_vtab *) c->base.pVtab;
  1847. }
  1848. static const sqlite3_module fts3Module;   /* forward declaration */
  1849. /* Return a dynamically generated statement of the form
  1850.  *   insert into %_content (docid, ...) values (?, ...)
  1851.  */
  1852. static const char *contentInsertStatement(fulltext_vtab *v){
  1853.   StringBuffer sb;
  1854.   int i;
  1855.   initStringBuffer(&sb);
  1856.   append(&sb, "insert into %_content (docid, ");
  1857.   appendList(&sb, v->nColumn, v->azContentColumn);
  1858.   append(&sb, ") values (?");
  1859.   for(i=0; i<v->nColumn; ++i)
  1860.     append(&sb, ", ?");
  1861.   append(&sb, ")");
  1862.   return stringBufferData(&sb);
  1863. }
  1864. /* Return a dynamically generated statement of the form
  1865.  *   select <content columns> from %_content where docid = ?
  1866.  */
  1867. static const char *contentSelectStatement(fulltext_vtab *v){
  1868.   StringBuffer sb;
  1869.   initStringBuffer(&sb);
  1870.   append(&sb, "SELECT ");
  1871.   appendList(&sb, v->nColumn, v->azContentColumn);
  1872.   append(&sb, " FROM %_content WHERE docid = ?");
  1873.   return stringBufferData(&sb);
  1874. }
  1875. /* Return a dynamically generated statement of the form
  1876.  *   update %_content set [col_0] = ?, [col_1] = ?, ...
  1877.  *                    where docid = ?
  1878.  */
  1879. static const char *contentUpdateStatement(fulltext_vtab *v){
  1880.   StringBuffer sb;
  1881.   int i;
  1882.   initStringBuffer(&sb);
  1883.   append(&sb, "update %_content set ");
  1884.   for(i=0; i<v->nColumn; ++i) {
  1885.     if( i>0 ){
  1886.       append(&sb, ", ");
  1887.     }
  1888.     append(&sb, v->azContentColumn[i]);
  1889.     append(&sb, " = ?");
  1890.   }
  1891.   append(&sb, " where docid = ?");
  1892.   return stringBufferData(&sb);
  1893. }
  1894. /* Puts a freshly-prepared statement determined by iStmt in *ppStmt.
  1895. ** If the indicated statement has never been prepared, it is prepared
  1896. ** and cached, otherwise the cached version is reset.
  1897. */
  1898. static int sql_get_statement(fulltext_vtab *v, fulltext_statement iStmt,
  1899.                              sqlite3_stmt **ppStmt){
  1900.   assert( iStmt<MAX_STMT );
  1901.   if( v->pFulltextStatements[iStmt]==NULL ){
  1902.     const char *zStmt;
  1903.     int rc;
  1904.     switch( iStmt ){
  1905.       case CONTENT_INSERT_STMT:
  1906.         zStmt = contentInsertStatement(v); break;
  1907.       case CONTENT_SELECT_STMT:
  1908.         zStmt = contentSelectStatement(v); break;
  1909.       case CONTENT_UPDATE_STMT:
  1910.         zStmt = contentUpdateStatement(v); break;
  1911.       default:
  1912.         zStmt = fulltext_zStatement[iStmt];
  1913.     }
  1914.     rc = sql_prepare(v->db, v->zDb, v->zName, &v->pFulltextStatements[iStmt],
  1915.                          zStmt);
  1916.     if( zStmt != fulltext_zStatement[iStmt]) sqlite3_free((void *) zStmt);
  1917.     if( rc!=SQLITE_OK ) return rc;
  1918.   } else {
  1919.     int rc = sqlite3_reset(v->pFulltextStatements[iStmt]);
  1920.     if( rc!=SQLITE_OK ) return rc;
  1921.   }
  1922.   *ppStmt = v->pFulltextStatements[iStmt];
  1923.   return SQLITE_OK;
  1924. }
  1925. /* Like sqlite3_step(), but convert SQLITE_DONE to SQLITE_OK and
  1926. ** SQLITE_ROW to SQLITE_ERROR.  Useful for statements like UPDATE,
  1927. ** where we expect no results.
  1928. */
  1929. static int sql_single_step(sqlite3_stmt *s){
  1930.   int rc = sqlite3_step(s);
  1931.   return (rc==SQLITE_DONE) ? SQLITE_OK : rc;
  1932. }
  1933. /* Like sql_get_statement(), but for special replicated LEAF_SELECT
  1934. ** statements.
  1935. */
  1936. /* TODO(shess) Write version for generic statements and then share
  1937. ** that between the cached-statement functions.
  1938. */
  1939. static int sql_get_leaf_statement(fulltext_vtab *v, int idx,
  1940.                                   sqlite3_stmt **ppStmt){
  1941.   assert( idx>=0 && idx<MERGE_COUNT );
  1942.   if( v->pLeafSelectStmts[idx]==NULL ){
  1943.     int rc = sql_prepare(v->db, v->zDb, v->zName, &v->pLeafSelectStmts[idx],
  1944.                          LEAF_SELECT);
  1945.     if( rc!=SQLITE_OK ) return rc;
  1946.   }else{
  1947.     int rc = sqlite3_reset(v->pLeafSelectStmts[idx]);
  1948.     if( rc!=SQLITE_OK ) return rc;
  1949.   }
  1950.   *ppStmt = v->pLeafSelectStmts[idx];
  1951.   return SQLITE_OK;
  1952. }
  1953. /* insert into %_content (docid, ...) values ([docid], [pValues])
  1954. ** If the docid contains SQL NULL, then a unique docid will be
  1955. ** generated.
  1956. */
  1957. static int content_insert(fulltext_vtab *v, sqlite3_value *docid,
  1958.                           sqlite3_value **pValues){
  1959.   sqlite3_stmt *s;
  1960.   int i;
  1961.   int rc = sql_get_statement(v, CONTENT_INSERT_STMT, &s);
  1962.   if( rc!=SQLITE_OK ) return rc;
  1963.   rc = sqlite3_bind_value(s, 1, docid);
  1964.   if( rc!=SQLITE_OK ) return rc;
  1965.   for(i=0; i<v->nColumn; ++i){
  1966.     rc = sqlite3_bind_value(s, 2+i, pValues[i]);
  1967.     if( rc!=SQLITE_OK ) return rc;
  1968.   }
  1969.   return sql_single_step(s);
  1970. }
  1971. /* update %_content set col0 = pValues[0], col1 = pValues[1], ...
  1972.  *                  where docid = [iDocid] */
  1973. static int content_update(fulltext_vtab *v, sqlite3_value **pValues,
  1974.                           sqlite_int64 iDocid){
  1975.   sqlite3_stmt *s;
  1976.   int i;
  1977.   int rc = sql_get_statement(v, CONTENT_UPDATE_STMT, &s);
  1978.   if( rc!=SQLITE_OK ) return rc;
  1979.   for(i=0; i<v->nColumn; ++i){
  1980.     rc = sqlite3_bind_value(s, 1+i, pValues[i]);
  1981.     if( rc!=SQLITE_OK ) return rc;
  1982.   }
  1983.   rc = sqlite3_bind_int64(s, 1+v->nColumn, iDocid);
  1984.   if( rc!=SQLITE_OK ) return rc;
  1985.   return sql_single_step(s);
  1986. }
  1987. static void freeStringArray(int nString, const char **pString){
  1988.   int i;
  1989.   for (i=0 ; i < nString ; ++i) {
  1990.     if( pString[i]!=NULL ) sqlite3_free((void *) pString[i]);
  1991.   }
  1992.   sqlite3_free((void *) pString);
  1993. }
  1994. /* select * from %_content where docid = [iDocid]
  1995.  * The caller must delete the returned array and all strings in it.
  1996.  * null fields will be NULL in the returned array.
  1997.  *
  1998.  * TODO: Perhaps we should return pointer/length strings here for consistency
  1999.  * with other code which uses pointer/length. */
  2000. static int content_select(fulltext_vtab *v, sqlite_int64 iDocid,
  2001.                           const char ***pValues){
  2002.   sqlite3_stmt *s;
  2003.   const char **values;
  2004.   int i;
  2005.   int rc;
  2006.   *pValues = NULL;
  2007.   rc = sql_get_statement(v, CONTENT_SELECT_STMT, &s);
  2008.   if( rc!=SQLITE_OK ) return rc;
  2009.   rc = sqlite3_bind_int64(s, 1, iDocid);
  2010.   if( rc!=SQLITE_OK ) return rc;
  2011.   rc = sqlite3_step(s);
  2012.   if( rc!=SQLITE_ROW ) return rc;
  2013.   values = (const char **) sqlite3_malloc(v->nColumn * sizeof(const char *));
  2014.   for(i=0; i<v->nColumn; ++i){
  2015.     if( sqlite3_column_type(s, i)==SQLITE_NULL ){
  2016.       values[i] = NULL;
  2017.     }else{
  2018.       values[i] = string_dup((char*)sqlite3_column_text(s, i));
  2019.     }
  2020.   }
  2021.   /* We expect only one row.  We must execute another sqlite3_step()
  2022.    * to complete the iteration; otherwise the table will remain locked. */
  2023.   rc = sqlite3_step(s);
  2024.   if( rc==SQLITE_DONE ){
  2025.     *pValues = values;
  2026.     return SQLITE_OK;
  2027.   }
  2028.   freeStringArray(v->nColumn, values);
  2029.   return rc;
  2030. }
  2031. /* delete from %_content where docid = [iDocid ] */
  2032. static int content_delete(fulltext_vtab *v, sqlite_int64 iDocid){
  2033.   sqlite3_stmt *s;
  2034.   int rc = sql_get_statement(v, CONTENT_DELETE_STMT, &s);
  2035.   if( rc!=SQLITE_OK ) return rc;
  2036.   rc = sqlite3_bind_int64(s, 1, iDocid);
  2037.   if( rc!=SQLITE_OK ) return rc;
  2038.   return sql_single_step(s);
  2039. }
  2040. /* insert into %_segments values ([pData])
  2041. **   returns assigned blockid in *piBlockid
  2042. */
  2043. static int block_insert(fulltext_vtab *v, const char *pData, int nData,
  2044.                         sqlite_int64 *piBlockid){
  2045.   sqlite3_stmt *s;
  2046.   int rc = sql_get_statement(v, BLOCK_INSERT_STMT, &s);
  2047.   if( rc!=SQLITE_OK ) return rc;
  2048.   rc = sqlite3_bind_blob(s, 1, pData, nData, SQLITE_STATIC);
  2049.   if( rc!=SQLITE_OK ) return rc;
  2050.   rc = sqlite3_step(s);
  2051.   if( rc==SQLITE_ROW ) return SQLITE_ERROR;
  2052.   if( rc!=SQLITE_DONE ) return rc;
  2053.   /* blockid column is an alias for rowid. */
  2054.   *piBlockid = sqlite3_last_insert_rowid(v->db);
  2055.   return SQLITE_OK;
  2056. }
  2057. /* delete from %_segments
  2058. **   where blockid between [iStartBlockid] and [iEndBlockid]
  2059. **
  2060. ** Deletes the range of blocks, inclusive, used to delete the blocks
  2061. ** which form a segment.
  2062. */
  2063. static int block_delete(fulltext_vtab *v,
  2064.                         sqlite_int64 iStartBlockid, sqlite_int64 iEndBlockid){
  2065.   sqlite3_stmt *s;
  2066.   int rc = sql_get_statement(v, BLOCK_DELETE_STMT, &s);
  2067.   if( rc!=SQLITE_OK ) return rc;
  2068.   rc = sqlite3_bind_int64(s, 1, iStartBlockid);
  2069.   if( rc!=SQLITE_OK ) return rc;
  2070.   rc = sqlite3_bind_int64(s, 2, iEndBlockid);
  2071.   if( rc!=SQLITE_OK ) return rc;
  2072.   return sql_single_step(s);
  2073. }
  2074. /* Returns SQLITE_ROW with *pidx set to the maximum segment idx found
  2075. ** at iLevel.  Returns SQLITE_DONE if there are no segments at
  2076. ** iLevel.  Otherwise returns an error.
  2077. */
  2078. static int segdir_max_index(fulltext_vtab *v, int iLevel, int *pidx){
  2079.   sqlite3_stmt *s;
  2080.   int rc = sql_get_statement(v, SEGDIR_MAX_INDEX_STMT, &s);
  2081.   if( rc!=SQLITE_OK ) return rc;
  2082.   rc = sqlite3_bind_int(s, 1, iLevel);
  2083.   if( rc!=SQLITE_OK ) return rc;
  2084.   rc = sqlite3_step(s);
  2085.   /* Should always get at least one row due to how max() works. */
  2086.   if( rc==SQLITE_DONE ) return SQLITE_DONE;
  2087.   if( rc!=SQLITE_ROW ) return rc;
  2088.   /* NULL means that there were no inputs to max(). */
  2089.   if( SQLITE_NULL==sqlite3_column_type(s, 0) ){
  2090.     rc = sqlite3_step(s);
  2091.     if( rc==SQLITE_ROW ) return SQLITE_ERROR;
  2092.     return rc;
  2093.   }
  2094.   *pidx = sqlite3_column_int(s, 0);
  2095.   /* We expect only one row.  We must execute another sqlite3_step()
  2096.    * to complete the iteration; otherwise the table will remain locked. */
  2097.   rc = sqlite3_step(s);
  2098.   if( rc==SQLITE_ROW ) return SQLITE_ERROR;
  2099.   if( rc!=SQLITE_DONE ) return rc;
  2100.   return SQLITE_ROW;
  2101. }
  2102. /* insert into %_segdir values (
  2103. **   [iLevel], [idx],
  2104. **   [iStartBlockid], [iLeavesEndBlockid], [iEndBlockid],
  2105. **   [pRootData]
  2106. ** )
  2107. */
  2108. static int segdir_set(fulltext_vtab *v, int iLevel, int idx,
  2109.                       sqlite_int64 iStartBlockid,
  2110.                       sqlite_int64 iLeavesEndBlockid,
  2111.                       sqlite_int64 iEndBlockid,
  2112.                       const char *pRootData, int nRootData){
  2113.   sqlite3_stmt *s;
  2114.   int rc = sql_get_statement(v, SEGDIR_SET_STMT, &s);
  2115.   if( rc!=SQLITE_OK ) return rc;
  2116.   rc = sqlite3_bind_int(s, 1, iLevel);
  2117.   if( rc!=SQLITE_OK ) return rc;
  2118.   rc = sqlite3_bind_int(s, 2, idx);
  2119.   if( rc!=SQLITE_OK ) return rc;
  2120.   rc = sqlite3_bind_int64(s, 3, iStartBlockid);
  2121.   if( rc!=SQLITE_OK ) return rc;
  2122.   rc = sqlite3_bind_int64(s, 4, iLeavesEndBlockid);
  2123.   if( rc!=SQLITE_OK ) return rc;
  2124.   rc = sqlite3_bind_int64(s, 5, iEndBlockid);
  2125.   if( rc!=SQLITE_OK ) return rc;
  2126.   rc = sqlite3_bind_blob(s, 6, pRootData, nRootData, SQLITE_STATIC);
  2127.   if( rc!=SQLITE_OK ) return rc;
  2128.   return sql_single_step(s);
  2129. }
  2130. /* Queries %_segdir for the block span of the segments in level
  2131. ** iLevel.  Returns SQLITE_DONE if there are no blocks for iLevel,
  2132. ** SQLITE_ROW if there are blocks, else an error.
  2133. */
  2134. static int segdir_span(fulltext_vtab *v, int iLevel,
  2135.                        sqlite_int64 *piStartBlockid,
  2136.                        sqlite_int64 *piEndBlockid){
  2137.   sqlite3_stmt *s;
  2138.   int rc = sql_get_statement(v, SEGDIR_SPAN_STMT, &s);
  2139.   if( rc!=SQLITE_OK ) return rc;
  2140.   rc = sqlite3_bind_int(s, 1, iLevel);
  2141.   if( rc!=SQLITE_OK ) return rc;
  2142.   rc = sqlite3_step(s);
  2143.   if( rc==SQLITE_DONE ) return SQLITE_DONE;  /* Should never happen */
  2144.   if( rc!=SQLITE_ROW ) return rc;
  2145.   /* This happens if all segments at this level are entirely inline. */
  2146.   if( SQLITE_NULL==sqlite3_column_type(s, 0) ){
  2147.     /* We expect only one row.  We must execute another sqlite3_step()
  2148.      * to complete the iteration; otherwise the table will remain locked. */
  2149.     int rc2 = sqlite3_step(s);
  2150.     if( rc2==SQLITE_ROW ) return SQLITE_ERROR;
  2151.     return rc2;
  2152.   }
  2153.   *piStartBlockid = sqlite3_column_int64(s, 0);
  2154.   *piEndBlockid = sqlite3_column_int64(s, 1);
  2155.   /* We expect only one row.  We must execute another sqlite3_step()
  2156.    * to complete the iteration; otherwise the table will remain locked. */
  2157.   rc = sqlite3_step(s);
  2158.   if( rc==SQLITE_ROW ) return SQLITE_ERROR;
  2159.   if( rc!=SQLITE_DONE ) return rc;
  2160.   return SQLITE_ROW;
  2161. }
  2162. /* Delete the segment blocks and segment directory records for all
  2163. ** segments at iLevel.
  2164. */
  2165. static int segdir_delete(fulltext_vtab *v, int iLevel){
  2166.   sqlite3_stmt *s;
  2167.   sqlite_int64 iStartBlockid, iEndBlockid;
  2168.   int rc = segdir_span(v, iLevel, &iStartBlockid, &iEndBlockid);
  2169.   if( rc!=SQLITE_ROW && rc!=SQLITE_DONE ) return rc;
  2170.   if( rc==SQLITE_ROW ){
  2171.     rc = block_delete(v, iStartBlockid, iEndBlockid);
  2172.     if( rc!=SQLITE_OK ) return rc;
  2173.   }
  2174.   /* Delete the segment directory itself. */
  2175.   rc = sql_get_statement(v, SEGDIR_DELETE_STMT, &s);
  2176.   if( rc!=SQLITE_OK ) return rc;
  2177.   rc = sqlite3_bind_int64(s, 1, iLevel);
  2178.   if( rc!=SQLITE_OK ) return rc;
  2179.   return sql_single_step(s);
  2180. }
  2181. /* TODO(shess) clearPendingTerms() is far down the file because
  2182. ** writeZeroSegment() is far down the file because LeafWriter is far
  2183. ** down the file.  Consider refactoring the code to move the non-vtab
  2184. ** code above the vtab code so that we don't need this forward
  2185. ** reference.
  2186. */
  2187. static int clearPendingTerms(fulltext_vtab *v);
  2188. /*
  2189. ** Free the memory used to contain a fulltext_vtab structure.
  2190. */
  2191. static void fulltext_vtab_destroy(fulltext_vtab *v){
  2192.   int iStmt, i;
  2193.   FTSTRACE(("FTS3 Destroy %pn", v));
  2194.   for( iStmt=0; iStmt<MAX_STMT; iStmt++ ){
  2195.     if( v->pFulltextStatements[iStmt]!=NULL ){
  2196.       sqlite3_finalize(v->pFulltextStatements[iStmt]);
  2197.       v->pFulltextStatements[iStmt] = NULL;
  2198.     }
  2199.   }
  2200.   for( i=0; i<MERGE_COUNT; i++ ){
  2201.     if( v->pLeafSelectStmts[i]!=NULL ){
  2202.       sqlite3_finalize(v->pLeafSelectStmts[i]);
  2203.       v->pLeafSelectStmts[i] = NULL;
  2204.     }
  2205.   }
  2206.   if( v->pTokenizer!=NULL ){
  2207.     v->pTokenizer->pModule->xDestroy(v->pTokenizer);
  2208.     v->pTokenizer = NULL;
  2209.   }
  2210.   clearPendingTerms(v);
  2211.   sqlite3_free(v->azColumn);
  2212.   for(i = 0; i < v->nColumn; ++i) {
  2213.     sqlite3_free(v->azContentColumn[i]);
  2214.   }
  2215.   sqlite3_free(v->azContentColumn);
  2216.   sqlite3_free(v);
  2217. }
  2218. /*
  2219. ** Token types for parsing the arguments to xConnect or xCreate.
  2220. */
  2221. #define TOKEN_EOF         0    /* End of file */
  2222. #define TOKEN_SPACE       1    /* Any kind of whitespace */
  2223. #define TOKEN_ID          2    /* An identifier */
  2224. #define TOKEN_STRING      3    /* A string literal */
  2225. #define TOKEN_PUNCT       4    /* A single punctuation character */
  2226. /*
  2227. ** If X is a character that can be used in an identifier then
  2228. ** ftsIdChar(X) will be true.  Otherwise it is false.
  2229. **
  2230. ** For ASCII, any character with the high-order bit set is
  2231. ** allowed in an identifier.  For 7-bit characters, 
  2232. ** isFtsIdChar[X] must be 1.
  2233. **
  2234. ** Ticket #1066.  the SQL standard does not allow '$' in the
  2235. ** middle of identfiers.  But many SQL implementations do. 
  2236. ** SQLite will allow '$' in identifiers for compatibility.
  2237. ** But the feature is undocumented.
  2238. */
  2239. static const char isFtsIdChar[] = {
  2240. /* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF */
  2241.     0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /* 2x */
  2242.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,  /* 3x */
  2243.     0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 4x */
  2244.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1,  /* 5x */
  2245.     0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 6x */
  2246.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0,  /* 7x */
  2247. };
  2248. #define ftsIdChar(C)  (((c=C)&0x80)!=0 || (c>0x1f && isFtsIdChar[c-0x20]))
  2249. /*
  2250. ** Return the length of the token that begins at z[0]. 
  2251. ** Store the token type in *tokenType before returning.
  2252. */
  2253. static int ftsGetToken(const char *z, int *tokenType){
  2254.   int i, c;
  2255.   switch( *z ){
  2256.     case 0: {
  2257.       *tokenType = TOKEN_EOF;
  2258.       return 0;
  2259.     }
  2260.     case ' ': case 't': case 'n': case 'f': case 'r': {
  2261.       for(i=1; safe_isspace(z[i]); i++){}
  2262.       *tokenType = TOKEN_SPACE;
  2263.       return i;
  2264.     }
  2265.     case '`':
  2266.     case ''':
  2267.     case '"': {
  2268.       int delim = z[0];
  2269.       for(i=1; (c=z[i])!=0; i++){
  2270.         if( c==delim ){
  2271.           if( z[i+1]==delim ){
  2272.             i++;
  2273.           }else{
  2274.             break;
  2275.           }
  2276.         }
  2277.       }
  2278.       *tokenType = TOKEN_STRING;
  2279.       return i + (c!=0);
  2280.     }
  2281.     case '[': {
  2282.       for(i=1, c=z[0]; c!=']' && (c=z[i])!=0; i++){}
  2283.       *tokenType = TOKEN_ID;
  2284.       return i;
  2285.     }
  2286.     default: {
  2287.       if( !ftsIdChar(*z) ){
  2288.         break;
  2289.       }
  2290.       for(i=1; ftsIdChar(z[i]); i++){}
  2291.       *tokenType = TOKEN_ID;
  2292.       return i;
  2293.     }
  2294.   }
  2295.   *tokenType = TOKEN_PUNCT;
  2296.   return 1;
  2297. }
  2298. /*
  2299. ** A token extracted from a string is an instance of the following
  2300. ** structure.
  2301. */
  2302. typedef struct FtsToken {
  2303.   const char *z;       /* Pointer to token text.  Not '00' terminated */
  2304.   short int n;         /* Length of the token text in bytes. */
  2305. } FtsToken;
  2306. /*
  2307. ** Given a input string (which is really one of the argv[] parameters
  2308. ** passed into xConnect or xCreate) split the string up into tokens.
  2309. ** Return an array of pointers to '00' terminated strings, one string
  2310. ** for each non-whitespace token.
  2311. **
  2312. ** The returned array is terminated by a single NULL pointer.
  2313. **
  2314. ** Space to hold the returned array is obtained from a single
  2315. ** malloc and should be freed by passing the return value to free().
  2316. ** The individual strings within the token list are all a part of
  2317. ** the single memory allocation and will all be freed at once.
  2318. */
  2319. static char **tokenizeString(const char *z, int *pnToken){
  2320.   int nToken = 0;
  2321.   FtsToken *aToken = sqlite3_malloc( strlen(z) * sizeof(aToken[0]) );
  2322.   int n = 1;
  2323.   int e, i;
  2324.   int totalSize = 0;
  2325.   char **azToken;
  2326.   char *zCopy;
  2327.   while( n>0 ){
  2328.     n = ftsGetToken(z, &e);
  2329.     if( e!=TOKEN_SPACE ){
  2330.       aToken[nToken].z = z;
  2331.       aToken[nToken].n = n;
  2332.       nToken++;
  2333.       totalSize += n+1;
  2334.     }
  2335.     z += n;
  2336.   }
  2337.   azToken = (char**)sqlite3_malloc( nToken*sizeof(char*) + totalSize );
  2338.   zCopy = (char*)&azToken[nToken];
  2339.   nToken--;
  2340.   for(i=0; i<nToken; i++){
  2341.     azToken[i] = zCopy;
  2342.     n = aToken[i].n;
  2343.     memcpy(zCopy, aToken[i].z, n);
  2344.     zCopy[n] = 0;
  2345.     zCopy += n+1;
  2346.   }
  2347.   azToken[nToken] = 0;
  2348.   sqlite3_free(aToken);
  2349.   *pnToken = nToken;
  2350.   return azToken;
  2351. }
  2352. /*
  2353. ** Convert an SQL-style quoted string into a normal string by removing
  2354. ** the quote characters.  The conversion is done in-place.  If the
  2355. ** input does not begin with a quote character, then this routine
  2356. ** is a no-op.
  2357. **
  2358. ** Examples:
  2359. **
  2360. **     "abc"   becomes   abc
  2361. **     'xyz'   becomes   xyz
  2362. **     [pqr]   becomes   pqr
  2363. **     `mno`   becomes   mno
  2364. */
  2365. static void dequoteString(char *z){
  2366.   int quote;
  2367.   int i, j;
  2368.   if( z==0 ) return;
  2369.   quote = z[0];
  2370.   switch( quote ){
  2371.     case ''':  break;
  2372.     case '"':   break;
  2373.     case '`':   break;                /* For MySQL compatibility */
  2374.     case '[':   quote = ']';  break;  /* For MS SqlServer compatibility */
  2375.     default:    return;
  2376.   }
  2377.   for(i=1, j=0; z[i]; i++){
  2378.     if( z[i]==quote ){
  2379.       if( z[i+1]==quote ){
  2380.         z[j++] = quote;
  2381.         i++;
  2382.       }else{
  2383.         z[j++] = 0;
  2384.         break;
  2385.       }
  2386.     }else{
  2387.       z[j++] = z[i];
  2388.     }
  2389.   }
  2390. }
  2391. /*
  2392. ** The input azIn is a NULL-terminated list of tokens.  Remove the first
  2393. ** token and all punctuation tokens.  Remove the quotes from
  2394. ** around string literal tokens.
  2395. **
  2396. ** Example:
  2397. **
  2398. **     input:      tokenize chinese ( 'simplifed' , 'mixed' )
  2399. **     output:     chinese simplifed mixed
  2400. **
  2401. ** Another example:
  2402. **
  2403. **     input:      delimiters ( '[' , ']' , '...' )
  2404. **     output:     [ ] ...
  2405. */
  2406. static void tokenListToIdList(char **azIn){
  2407.   int i, j;
  2408.   if( azIn ){
  2409.     for(i=0, j=-1; azIn[i]; i++){
  2410.       if( safe_isalnum(azIn[i][0]) || azIn[i][1] ){
  2411.         dequoteString(azIn[i]);
  2412.         if( j>=0 ){
  2413.           azIn[j] = azIn[i];
  2414.         }
  2415.         j++;
  2416.       }
  2417.     }
  2418.     azIn[j] = 0;
  2419.   }
  2420. }
  2421. /*
  2422. ** Find the first alphanumeric token in the string zIn.  Null-terminate
  2423. ** this token.  Remove any quotation marks.  And return a pointer to
  2424. ** the result.
  2425. */
  2426. static char *firstToken(char *zIn, char **pzTail){
  2427.   int n, ttype;
  2428.   while(1){
  2429.     n = ftsGetToken(zIn, &ttype);
  2430.     if( ttype==TOKEN_SPACE ){
  2431.       zIn += n;
  2432.     }else if( ttype==TOKEN_EOF ){
  2433.       *pzTail = zIn;
  2434.       return 0;
  2435.     }else{
  2436.       zIn[n] = 0;
  2437.       *pzTail = &zIn[1];
  2438.       dequoteString(zIn);
  2439.       return zIn;
  2440.     }
  2441.   }
  2442.   /*NOTREACHED*/
  2443. }
  2444. /* Return true if...
  2445. **
  2446. **   *  s begins with the string t, ignoring case
  2447. **   *  s is longer than t
  2448. **   *  The first character of s beyond t is not a alphanumeric
  2449. ** 
  2450. ** Ignore leading space in *s.
  2451. **
  2452. ** To put it another way, return true if the first token of
  2453. ** s[] is t[].
  2454. */
  2455. static int startsWith(const char *s, const char *t){
  2456.   while( safe_isspace(*s) ){ s++; }
  2457.   while( *t ){
  2458.     if( safe_tolower(*s++)!=safe_tolower(*t++) ) return 0;
  2459.   }
  2460.   return *s!='_' && !safe_isalnum(*s);
  2461. }
  2462. /*
  2463. ** An instance of this structure defines the "spec" of a
  2464. ** full text index.  This structure is populated by parseSpec
  2465. ** and use by fulltextConnect and fulltextCreate.
  2466. */
  2467. typedef struct TableSpec {
  2468.   const char *zDb;         /* Logical database name */
  2469.   const char *zName;       /* Name of the full-text index */
  2470.   int nColumn;             /* Number of columns to be indexed */
  2471.   char **azColumn;         /* Original names of columns to be indexed */
  2472.   char **azContentColumn;  /* Column names for %_content */
  2473.   char **azTokenizer;      /* Name of tokenizer and its arguments */
  2474. } TableSpec;
  2475. /*
  2476. ** Reclaim all of the memory used by a TableSpec
  2477. */
  2478. static void clearTableSpec(TableSpec *p) {
  2479.   sqlite3_free(p->azColumn);
  2480.   sqlite3_free(p->azContentColumn);
  2481.   sqlite3_free(p->azTokenizer);
  2482. }
  2483. /* Parse a CREATE VIRTUAL TABLE statement, which looks like this:
  2484.  *
  2485.  * CREATE VIRTUAL TABLE email
  2486.  *        USING fts3(subject, body, tokenize mytokenizer(myarg))
  2487.  *
  2488.  * We return parsed information in a TableSpec structure.
  2489.  * 
  2490.  */
  2491. static int parseSpec(TableSpec *pSpec, int argc, const char *const*argv,
  2492.                      char**pzErr){
  2493.   int i, n;
  2494.   char *z, *zDummy;
  2495.   char **azArg;
  2496.   const char *zTokenizer = 0;    /* argv[] entry describing the tokenizer */
  2497.   assert( argc>=3 );
  2498.   /* Current interface:
  2499.   ** argv[0] - module name
  2500.   ** argv[1] - database name
  2501.   ** argv[2] - table name
  2502.   ** argv[3..] - columns, optionally followed by tokenizer specification
  2503.   **             and snippet delimiters specification.
  2504.   */
  2505.   /* Make a copy of the complete argv[][] array in a single allocation.
  2506.   ** The argv[][] array is read-only and transient.  We can write to the
  2507.   ** copy in order to modify things and the copy is persistent.
  2508.   */
  2509.   CLEAR(pSpec);
  2510.   for(i=n=0; i<argc; i++){
  2511.     n += strlen(argv[i]) + 1;
  2512.   }
  2513.   azArg = sqlite3_malloc( sizeof(char*)*argc + n );
  2514.   if( azArg==0 ){
  2515.     return SQLITE_NOMEM;
  2516.   }
  2517.   z = (char*)&azArg[argc];
  2518.   for(i=0; i<argc; i++){
  2519.     azArg[i] = z;
  2520.     strcpy(z, argv[i]);
  2521.     z += strlen(z)+1;
  2522.   }
  2523.   /* Identify the column names and the tokenizer and delimiter arguments
  2524.   ** in the argv[][] array.
  2525.   */
  2526.   pSpec->zDb = azArg[1];
  2527.   pSpec->zName = azArg[2];
  2528.   pSpec->nColumn = 0;
  2529.   pSpec->azColumn = azArg;
  2530.   zTokenizer = "tokenize simple";
  2531.   for(i=3; i<argc; ++i){
  2532.     if( startsWith(azArg[i],"tokenize") ){
  2533.       zTokenizer = azArg[i];
  2534.     }else{
  2535.       z = azArg[pSpec->nColumn] = firstToken(azArg[i], &zDummy);
  2536.       pSpec->nColumn++;
  2537.     }
  2538.   }
  2539.   if( pSpec->nColumn==0 ){
  2540.     azArg[0] = "content";
  2541.     pSpec->nColumn = 1;
  2542.   }
  2543.   /*
  2544.   ** Construct the list of content column names.
  2545.   **
  2546.   ** Each content column name will be of the form cNNAAAA
  2547.   ** where NN is the column number and AAAA is the sanitized
  2548.   ** column name.  "sanitized" means that special characters are
  2549.   ** converted to "_".  The cNN prefix guarantees that all column
  2550.   ** names are unique.
  2551.   **
  2552.   ** The AAAA suffix is not strictly necessary.  It is included
  2553.   ** for the convenience of people who might examine the generated
  2554.   ** %_content table and wonder what the columns are used for.
  2555.   */
  2556.   pSpec->azContentColumn = sqlite3_malloc( pSpec->nColumn * sizeof(char *) );
  2557.   if( pSpec->azContentColumn==0 ){
  2558.     clearTableSpec(pSpec);
  2559.     return SQLITE_NOMEM;
  2560.   }
  2561.   for(i=0; i<pSpec->nColumn; i++){
  2562.     char *p;
  2563.     pSpec->azContentColumn[i] = sqlite3_mprintf("c%d%s", i, azArg[i]);
  2564.     for (p = pSpec->azContentColumn[i]; *p ; ++p) {
  2565.       if( !safe_isalnum(*p) ) *p = '_';
  2566.     }
  2567.   }
  2568.   /*
  2569.   ** Parse the tokenizer specification string.
  2570.   */
  2571.   pSpec->azTokenizer = tokenizeString(zTokenizer, &n);
  2572.   tokenListToIdList(pSpec->azTokenizer);
  2573.   return SQLITE_OK;
  2574. }
  2575. /*
  2576. ** Generate a CREATE TABLE statement that describes the schema of
  2577. ** the virtual table.  Return a pointer to this schema string.
  2578. **
  2579. ** Space is obtained from sqlite3_mprintf() and should be freed
  2580. ** using sqlite3_free().
  2581. */
  2582. static char *fulltextSchema(
  2583.   int nColumn,                  /* Number of columns */
  2584.   const char *const* azColumn,  /* List of columns */
  2585.   const char *zTableName        /* Name of the table */
  2586. ){
  2587.   int i;
  2588.   char *zSchema, *zNext;
  2589.   const char *zSep = "(";
  2590.   zSchema = sqlite3_mprintf("CREATE TABLE x");
  2591.   for(i=0; i<nColumn; i++){
  2592.     zNext = sqlite3_mprintf("%s%s%Q", zSchema, zSep, azColumn[i]);
  2593.     sqlite3_free(zSchema);
  2594.     zSchema = zNext;
  2595.     zSep = ",";
  2596.   }
  2597.   zNext = sqlite3_mprintf("%s,%Q HIDDEN", zSchema, zTableName);
  2598.   sqlite3_free(zSchema);
  2599.   zSchema = zNext;
  2600.   zNext = sqlite3_mprintf("%s,docid HIDDEN)", zSchema);
  2601.   sqlite3_free(zSchema);
  2602.   return zNext;
  2603. }
  2604. /*
  2605. ** Build a new sqlite3_vtab structure that will describe the
  2606. ** fulltext index defined by spec.
  2607. */
  2608. static int constructVtab(
  2609.   sqlite3 *db,              /* The SQLite database connection */
  2610.   fts3Hash *pHash,          /* Hash table containing tokenizers */
  2611.   TableSpec *spec,          /* Parsed spec information from parseSpec() */
  2612.   sqlite3_vtab **ppVTab,    /* Write the resulting vtab structure here */
  2613.   char **pzErr              /* Write any error message here */
  2614. ){
  2615.   int rc;
  2616.   int n;
  2617.   fulltext_vtab *v = 0;
  2618.   const sqlite3_tokenizer_module *m = NULL;
  2619.   char *schema;
  2620.   char const *zTok;         /* Name of tokenizer to use for this fts table */
  2621.   int nTok;                 /* Length of zTok, including nul terminator */
  2622.   v = (fulltext_vtab *) sqlite3_malloc(sizeof(fulltext_vtab));
  2623.   if( v==0 ) return SQLITE_NOMEM;
  2624.   CLEAR(v);
  2625.   /* sqlite will initialize v->base */
  2626.   v->db = db;
  2627.   v->zDb = spec->zDb;       /* Freed when azColumn is freed */
  2628.   v->zName = spec->zName;   /* Freed when azColumn is freed */
  2629.   v->nColumn = spec->nColumn;
  2630.   v->azContentColumn = spec->azContentColumn;
  2631.   spec->azContentColumn = 0;
  2632.   v->azColumn = spec->azColumn;
  2633.   spec->azColumn = 0;
  2634.   if( spec->azTokenizer==0 ){
  2635.     return SQLITE_NOMEM;
  2636.   }
  2637.   zTok = spec->azTokenizer[0]; 
  2638.   if( !zTok ){
  2639.     zTok = "simple";
  2640.   }
  2641.   nTok = strlen(zTok)+1;
  2642.   m = (sqlite3_tokenizer_module *)sqlite3Fts3HashFind(pHash, zTok, nTok);
  2643.   if( !m ){
  2644.     *pzErr = sqlite3_mprintf("unknown tokenizer: %s", spec->azTokenizer[0]);
  2645.     rc = SQLITE_ERROR;
  2646.     goto err;
  2647.   }
  2648.   for(n=0; spec->azTokenizer[n]; n++){}
  2649.   if( n ){
  2650.     rc = m->xCreate(n-1, (const char*const*)&spec->azTokenizer[1],
  2651.                     &v->pTokenizer);
  2652.   }else{
  2653.     rc = m->xCreate(0, 0, &v->pTokenizer);
  2654.   }
  2655.   if( rc!=SQLITE_OK ) goto err;
  2656.   v->pTokenizer->pModule = m;
  2657.   /* TODO: verify the existence of backing tables foo_content, foo_term */
  2658.   schema = fulltextSchema(v->nColumn, (const char*const*)v->azColumn,
  2659.                           spec->zName);
  2660.   rc = sqlite3_declare_vtab(db, schema);
  2661.   sqlite3_free(schema);
  2662.   if( rc!=SQLITE_OK ) goto err;
  2663.   memset(v->pFulltextStatements, 0, sizeof(v->pFulltextStatements));
  2664.   /* Indicate that the buffer is not live. */
  2665.   v->nPendingData = -1;
  2666.   *ppVTab = &v->base;
  2667.   FTSTRACE(("FTS3 Connect %pn", v));
  2668.   return rc;
  2669. err:
  2670.   fulltext_vtab_destroy(v);
  2671.   return rc;
  2672. }
  2673. static int fulltextConnect(
  2674.   sqlite3 *db,
  2675.   void *pAux,
  2676.   int argc, const char *const*argv,
  2677.   sqlite3_vtab **ppVTab,
  2678.   char **pzErr
  2679. ){
  2680.   TableSpec spec;
  2681.   int rc = parseSpec(&spec, argc, argv, pzErr);
  2682.   if( rc!=SQLITE_OK ) return rc;
  2683.   rc = constructVtab(db, (fts3Hash *)pAux, &spec, ppVTab, pzErr);
  2684.   clearTableSpec(&spec);
  2685.   return rc;
  2686. }
  2687. /* The %_content table holds the text of each document, with
  2688. ** the docid column exposed as the SQLite rowid for the table.
  2689. */
  2690. /* TODO(shess) This comment needs elaboration to match the updated
  2691. ** code.  Work it into the top-of-file comment at that time.
  2692. */
  2693. static int fulltextCreate(sqlite3 *db, void *pAux,
  2694.                           int argc, const char * const *argv,
  2695.                           sqlite3_vtab **ppVTab, char **pzErr){
  2696.   int rc;
  2697.   TableSpec spec;
  2698.   StringBuffer schema;
  2699.   FTSTRACE(("FTS3 Createn"));
  2700.   rc = parseSpec(&spec, argc, argv, pzErr);
  2701.   if( rc!=SQLITE_OK ) return rc;
  2702.   initStringBuffer(&schema);
  2703.   append(&schema, "CREATE TABLE %_content(");
  2704.   append(&schema, "  docid INTEGER PRIMARY KEY,");
  2705.   appendList(&schema, spec.nColumn, spec.azContentColumn);
  2706.   append(&schema, ")");
  2707.   rc = sql_exec(db, spec.zDb, spec.zName, stringBufferData(&schema));
  2708.   stringBufferDestroy(&schema);
  2709.   if( rc!=SQLITE_OK ) goto out;
  2710.   rc = sql_exec(db, spec.zDb, spec.zName,
  2711.                 "create table %_segments("
  2712.                 "  blockid INTEGER PRIMARY KEY,"
  2713.                 "  block blob"
  2714.                 ");"
  2715.                 );
  2716.   if( rc!=SQLITE_OK ) goto out;
  2717.   rc = sql_exec(db, spec.zDb, spec.zName,
  2718.                 "create table %_segdir("
  2719.                 "  level integer,"
  2720.                 "  idx integer,"
  2721.                 "  start_block integer,"
  2722.                 "  leaves_end_block integer,"
  2723.                 "  end_block integer,"
  2724.                 "  root blob,"
  2725.                 "  primary key(level, idx)"
  2726.                 ");");
  2727.   if( rc!=SQLITE_OK ) goto out;
  2728.   rc = constructVtab(db, (fts3Hash *)pAux, &spec, ppVTab, pzErr);
  2729. out:
  2730.   clearTableSpec(&spec);
  2731.   return rc;
  2732. }
  2733. /* Decide how to handle an SQL query. */
  2734. static int fulltextBestIndex(sqlite3_vtab *pVTab, sqlite3_index_info *pInfo){
  2735.   fulltext_vtab *v = (fulltext_vtab *)pVTab;
  2736.   int i;
  2737.   FTSTRACE(("FTS3 BestIndexn"));
  2738.   for(i=0; i<pInfo->nConstraint; ++i){
  2739.     const struct sqlite3_index_constraint *pConstraint;
  2740.     pConstraint = &pInfo->aConstraint[i];
  2741.     if( pConstraint->usable ) {
  2742.       if( (pConstraint->iColumn==-1 || pConstraint->iColumn==v->nColumn+1) &&
  2743.           pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ ){
  2744.         pInfo->idxNum = QUERY_DOCID;      /* lookup by docid */
  2745.         FTSTRACE(("FTS3 QUERY_DOCIDn"));
  2746.       } else if( pConstraint->iColumn>=0 && pConstraint->iColumn<=v->nColumn &&
  2747.                  pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH ){
  2748.         /* full-text search */
  2749.         pInfo->idxNum = QUERY_FULLTEXT + pConstraint->iColumn;
  2750.         FTSTRACE(("FTS3 QUERY_FULLTEXT %dn", pConstraint->iColumn));
  2751.       } else continue;
  2752.       pInfo->aConstraintUsage[i].argvIndex = 1;
  2753.       pInfo->aConstraintUsage[i].omit = 1;
  2754.       /* An arbitrary value for now.
  2755.        * TODO: Perhaps docid matches should be considered cheaper than
  2756.        * full-text searches. */
  2757.       pInfo->estimatedCost = 1.0;   
  2758.       return SQLITE_OK;
  2759.     }
  2760.   }
  2761.   pInfo->idxNum = QUERY_GENERIC;
  2762.   return SQLITE_OK;
  2763. }
  2764. static int fulltextDisconnect(sqlite3_vtab *pVTab){
  2765.   FTSTRACE(("FTS3 Disconnect %pn", pVTab));
  2766.   fulltext_vtab_destroy((fulltext_vtab *)pVTab);
  2767.   return SQLITE_OK;
  2768. }
  2769. static int fulltextDestroy(sqlite3_vtab *pVTab){
  2770.   fulltext_vtab *v = (fulltext_vtab *)pVTab;
  2771.   int rc;
  2772.   FTSTRACE(("FTS3 Destroy %pn", pVTab));
  2773.   rc = sql_exec(v->db, v->zDb, v->zName,
  2774.                 "drop table if exists %_content;"
  2775.                 "drop table if exists %_segments;"
  2776.                 "drop table if exists %_segdir;"
  2777.                 );
  2778.   if( rc!=SQLITE_OK ) return rc;
  2779.   fulltext_vtab_destroy((fulltext_vtab *)pVTab);
  2780.   return SQLITE_OK;
  2781. }
  2782. static int fulltextOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
  2783.   fulltext_cursor *c;
  2784.   c = (fulltext_cursor *) sqlite3_malloc(sizeof(fulltext_cursor));
  2785.   if( c ){
  2786.     memset(c, 0, sizeof(fulltext_cursor));
  2787.     /* sqlite will initialize c->base */
  2788.     *ppCursor = &c->base;
  2789.     FTSTRACE(("FTS3 Open %p: %pn", pVTab, c));
  2790.     return SQLITE_OK;
  2791.   }else{
  2792.     return SQLITE_NOMEM;
  2793.   }
  2794. }
  2795. /* Free all of the dynamically allocated memory held by *q
  2796. */
  2797. static void queryClear(Query *q){
  2798.   int i;
  2799.   for(i = 0; i < q->nTerms; ++i){
  2800.     sqlite3_free(q->pTerms[i].pTerm);
  2801.   }
  2802.   sqlite3_free(q->pTerms);
  2803.   CLEAR(q);
  2804. }
  2805. /* Free all of the dynamically allocated memory held by the
  2806. ** Snippet
  2807. */
  2808. static void snippetClear(Snippet *p){
  2809.   sqlite3_free(p->aMatch);
  2810.   sqlite3_free(p->zOffset);
  2811.   sqlite3_free(p->zSnippet);
  2812.   CLEAR(p);
  2813. }
  2814. /*
  2815. ** Append a single entry to the p->aMatch[] log.
  2816. */
  2817. static void snippetAppendMatch(
  2818.   Snippet *p,               /* Append the entry to this snippet */
  2819.   int iCol, int iTerm,      /* The column and query term */
  2820.   int iToken,               /* Matching token in document */
  2821.   int iStart, int nByte     /* Offset and size of the match */
  2822. ){
  2823.   int i;
  2824.   struct snippetMatch *pMatch;
  2825.   if( p->nMatch+1>=p->nAlloc ){
  2826.     p->nAlloc = p->nAlloc*2 + 10;
  2827.     p->aMatch = sqlite3_realloc(p->aMatch, p->nAlloc*sizeof(p->aMatch[0]) );
  2828.     if( p->aMatch==0 ){
  2829.       p->nMatch = 0;
  2830.       p->nAlloc = 0;
  2831.       return;
  2832.     }
  2833.   }
  2834.   i = p->nMatch++;
  2835.   pMatch = &p->aMatch[i];
  2836.   pMatch->iCol = iCol;
  2837.   pMatch->iTerm = iTerm;
  2838.   pMatch->iToken = iToken;
  2839.   pMatch->iStart = iStart;
  2840.   pMatch->nByte = nByte;
  2841. }
  2842. /*
  2843. ** Sizing information for the circular buffer used in snippetOffsetsOfColumn()
  2844. */
  2845. #define FTS3_ROTOR_SZ   (32)
  2846. #define FTS3_ROTOR_MASK (FTS3_ROTOR_SZ-1)
  2847. /*
  2848. ** Add entries to pSnippet->aMatch[] for every match that occurs against
  2849. ** document zDoc[0..nDoc-1] which is stored in column iColumn.
  2850. */
  2851. static void snippetOffsetsOfColumn(
  2852.   Query *pQuery,
  2853.   Snippet *pSnippet,
  2854.   int iColumn,
  2855.   const char *zDoc,
  2856.   int nDoc
  2857. ){
  2858.   const sqlite3_tokenizer_module *pTModule;  /* The tokenizer module */
  2859.   sqlite3_tokenizer *pTokenizer;             /* The specific tokenizer */
  2860.   sqlite3_tokenizer_cursor *pTCursor;        /* Tokenizer cursor */
  2861.   fulltext_vtab *pVtab;                /* The full text index */
  2862.   int nColumn;                         /* Number of columns in the index */
  2863.   const QueryTerm *aTerm;              /* Query string terms */
  2864.   int nTerm;                           /* Number of query string terms */  
  2865.   int i, j;                            /* Loop counters */
  2866.   int rc;                              /* Return code */
  2867.   unsigned int match, prevMatch;       /* Phrase search bitmasks */
  2868.   const char *zToken;                  /* Next token from the tokenizer */
  2869.   int nToken;                          /* Size of zToken */
  2870.   int iBegin, iEnd, iPos;              /* Offsets of beginning and end */
  2871.   /* The following variables keep a circular buffer of the last
  2872.   ** few tokens */
  2873.   unsigned int iRotor = 0;             /* Index of current token */
  2874.   int iRotorBegin[FTS3_ROTOR_SZ];      /* Beginning offset of token */
  2875.   int iRotorLen[FTS3_ROTOR_SZ];        /* Length of token */
  2876.   pVtab = pQuery->pFts;
  2877.   nColumn = pVtab->nColumn;
  2878.   pTokenizer = pVtab->pTokenizer;
  2879.   pTModule = pTokenizer->pModule;
  2880.   rc = pTModule->xOpen(pTokenizer, zDoc, nDoc, &pTCursor);
  2881.   if( rc ) return;
  2882.   pTCursor->pTokenizer = pTokenizer;
  2883.   aTerm = pQuery->pTerms;
  2884.   nTerm = pQuery->nTerms;
  2885.   if( nTerm>=FTS3_ROTOR_SZ ){
  2886.     nTerm = FTS3_ROTOR_SZ - 1;
  2887.   }
  2888.   prevMatch = 0;
  2889.   while(1){
  2890.     rc = pTModule->xNext(pTCursor, &zToken, &nToken, &iBegin, &iEnd, &iPos);
  2891.     if( rc ) break;
  2892.     iRotorBegin[iRotor&FTS3_ROTOR_MASK] = iBegin;
  2893.     iRotorLen[iRotor&FTS3_ROTOR_MASK] = iEnd-iBegin;
  2894.     match = 0;
  2895.     for(i=0; i<nTerm; i++){
  2896.       int iCol;
  2897.       iCol = aTerm[i].iColumn;
  2898.       if( iCol>=0 && iCol<nColumn && iCol!=iColumn ) continue;