lib: fix g_hash_table related read-after-free bug
[notmuch] / lib / database.cc
1 /* database.cc - The database interfaces of the notmuch mail library
2  *
3  * Copyright © 2009 Carl Worth
4  *
5  * This program is free software: you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation, either version 3 of the License, or
8  * (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program.  If not, see https://www.gnu.org/licenses/ .
17  *
18  * Author: Carl Worth <cworth@cworth.org>
19  */
20
21 #include "database-private.h"
22 #include "parse-time-vrp.h"
23 #include "query-fp.h"
24 #include "string-util.h"
25
26 #include <iostream>
27
28 #include <sys/time.h>
29 #include <sys/stat.h>
30 #include <signal.h>
31 #include <ftw.h>
32
33 #include <glib.h> /* g_free, GPtrArray, GHashTable */
34 #include <glib-object.h> /* g_type_init */
35
36 #include <gmime/gmime.h> /* g_mime_init */
37
38 using namespace std;
39
40 #define ARRAY_SIZE(arr) (sizeof (arr) / sizeof (arr[0]))
41
42 typedef struct {
43     const char *name;
44     const char *prefix;
45 } prefix_t;
46
47 #define NOTMUCH_DATABASE_VERSION 3
48
49 #define STRINGIFY(s) _SUB_STRINGIFY(s)
50 #define _SUB_STRINGIFY(s) #s
51
52 #if HAVE_XAPIAN_DB_RETRY_LOCK
53 #define DB_ACTION (Xapian::DB_CREATE_OR_OPEN | Xapian::DB_RETRY_LOCK)
54 #else
55 #define DB_ACTION Xapian::DB_CREATE_OR_OPEN
56 #endif
57
58 /* Here's the current schema for our database (for NOTMUCH_DATABASE_VERSION):
59  *
60  * We currently have three different types of documents (mail, ghost,
61  * and directory) and also some metadata.
62  *
63  * Mail document
64  * -------------
65  * A mail document is associated with a particular email message. It
66  * is stored in one or more files on disk (though only one has its
67  * content indexed) and is uniquely identified  by its "id" field
68  * (which is generally the message ID). It is indexed with the
69  * following prefixed terms which the database uses to construct
70  * threads, etc.:
71  *
72  *    Single terms of given prefix:
73  *
74  *      type:   mail
75  *
76  *      id:     Unique ID of mail. This is from the Message-ID header
77  *              if present and not too long (see NOTMUCH_MESSAGE_ID_MAX).
78  *              If it's present and too long, then we use
79  *              "notmuch-sha1-<sha1_sum_of_message_id>".
80  *              If this header is not present, we use
81  *              "notmuch-sha1-<sha1_sum_of_entire_file>".
82  *
83  *      thread: The ID of the thread to which the mail belongs
84  *
85  *      replyto: The ID from the In-Reply-To header of the mail (if any).
86  *
87  *    Multiple terms of given prefix:
88  *
89  *      reference: All message IDs from In-Reply-To and References
90  *                 headers in the message.
91  *
92  *      tag:       Any tags associated with this message by the user.
93  *
94  *      file-direntry:  A colon-separated pair of values
95  *                      (INTEGER:STRING), where INTEGER is the
96  *                      document ID of a directory document, and
97  *                      STRING is the name of a file within that
98  *                      directory for this mail message.
99  *
100  *      property:       Has a property with key=value
101  *                 FIXME: if no = is present, should match on any value
102  *
103  *    A mail document also has four values:
104  *
105  *      TIMESTAMP:      The time_t value corresponding to the message's
106  *                      Date header.
107  *
108  *      MESSAGE_ID:     The unique ID of the mail mess (see "id" above)
109  *
110  *      FROM:           The value of the "From" header
111  *
112  *      SUBJECT:        The value of the "Subject" header
113  *
114  *      LAST_MOD:       The revision number as of the last tag or
115  *                      filename change.
116  *
117  * In addition, terms from the content of the message are added with
118  * "from", "to", "attachment", and "subject" prefixes for use by the
119  * user in searching. Similarly, terms from the path of the mail
120  * message are added with "folder" and "path" prefixes. But the
121  * database doesn't really care itself about any of these.
122  *
123  * The data portion of a mail document is empty.
124  *
125  * Ghost mail document [if NOTMUCH_FEATURE_GHOSTS]
126  * -----------------------------------------------
127  * A ghost mail document is like a mail document, but where we don't
128  * have the message content.  These are used to track thread reference
129  * information for messages we haven't received.
130  *
131  * A ghost mail document has type: ghost; id and thread fields that
132  * are identical to the mail document fields; and a MESSAGE_ID value.
133  *
134  * Directory document
135  * ------------------
136  * A directory document is used by a client of the notmuch library to
137  * maintain data necessary to allow for efficient polling of mail
138  * directories.
139  *
140  * All directory documents contain one term:
141  *
142  *      directory:      The directory path (relative to the database path)
143  *                      Or the SHA1 sum of the directory path (if the
144  *                      path itself is too long to fit in a Xapian
145  *                      term).
146  *
147  * And all directory documents for directories other than top-level
148  * directories also contain the following term:
149  *
150  *      directory-direntry: A colon-separated pair of values
151  *                          (INTEGER:STRING), where INTEGER is the
152  *                          document ID of the parent directory
153  *                          document, and STRING is the name of this
154  *                          directory within that parent.
155  *
156  * All directory documents have a single value:
157  *
158  *      TIMESTAMP:      The mtime of the directory (at last scan)
159  *
160  * The data portion of a directory document contains the path of the
161  * directory (relative to the database path).
162  *
163  * Database metadata
164  * -----------------
165  * Xapian allows us to store arbitrary name-value pairs as
166  * "metadata". We currently use the following metadata names with the
167  * given meanings:
168  *
169  *      version         The database schema version, (which is distinct
170  *                      from both the notmuch package version (see
171  *                      notmuch --version) and the libnotmuch library
172  *                      version. The version is stored as an base-10
173  *                      ASCII integer. The initial database version
174  *                      was 1, (though a schema existed before that
175  *                      were no "version" database value existed at
176  *                      all). Successive versions are allocated as
177  *                      changes are made to the database (such as by
178  *                      indexing new fields).
179  *
180  *      features        The set of features supported by this
181  *                      database. This consists of a set of
182  *                      '\n'-separated lines, where each is a feature
183  *                      name, a '\t', and compatibility flags.  If the
184  *                      compatibility flags contain 'w', then the
185  *                      opener must support this feature to safely
186  *                      write this database.  If the compatibility
187  *                      flags contain 'r', then the opener must
188  *                      support this feature to read this database.
189  *                      Introduced in database version 3.
190  *
191  *      last_thread_id  The last thread ID generated. This is stored
192  *                      as a 16-byte hexadecimal ASCII representation
193  *                      of a 64-bit unsigned integer. The first ID
194  *                      generated is 1 and the value will be
195  *                      incremented for each thread ID.
196  *
197  *      C*              metadata keys starting with C indicate
198  *                      configuration data. It can be managed with the
199  *                      n_database_*config* API.  There is a convention
200  *                      of hierarchical keys separated by '.' (e.g.
201  *                      query.notmuch stores the value for the named
202  *                      query 'notmuch'), but it is not enforced by the
203  *                      API.
204  *
205  * Obsolete metadata
206  * -----------------
207  *
208  * If ! NOTMUCH_FEATURE_GHOSTS, there are no ghost mail documents.
209  * Instead, the database has the following additional database
210  * metadata:
211  *
212  *      thread_id_*     A pre-allocated thread ID for a particular
213  *                      message. This is actually an arbitrarily large
214  *                      family of metadata name. Any particular name is
215  *                      formed by concatenating "thread_id_" with a message
216  *                      ID (or the SHA1 sum of a message ID if it is very
217  *                      long---see description of 'id' in the mail
218  *                      document). The value stored is a thread ID.
219  *
220  *                      These thread ID metadata values are stored
221  *                      whenever a message references a parent message
222  *                      that does not yet exist in the database. A
223  *                      thread ID will be allocated and stored, and if
224  *                      the message is later added, the stored thread
225  *                      ID will be used (and the metadata value will
226  *                      be cleared).
227  *
228  *                      Even before a message is added, it's
229  *                      pre-allocated thread ID is useful so that all
230  *                      descendant messages that reference this common
231  *                      parent can be recognized as belonging to the
232  *                      same thread.
233  */
234
235 /* With these prefix values we follow the conventions published here:
236  *
237  * https://xapian.org/docs/omega/termprefixes.html
238  *
239  * as much as makes sense. Note that I took some liberty in matching
240  * the reserved prefix values to notmuch concepts, (for example, 'G'
241  * is documented as "newsGroup (or similar entity - e.g. a web forum
242  * name)", for which I think the thread is the closest analogue in
243  * notmuch. This in spite of the fact that we will eventually be
244  * storing mailing-list messages where 'G' for "mailing list name"
245  * might be even a closer analogue. I'm treating the single-character
246  * prefixes preferentially for core notmuch concepts (which will be
247  * nearly universal to all mail messages).
248  */
249
250 static prefix_t BOOLEAN_PREFIX_INTERNAL[] = {
251     { "type",                   "T" },
252     { "reference",              "XREFERENCE" },
253     { "replyto",                "XREPLYTO" },
254     { "directory",              "XDIRECTORY" },
255     { "file-direntry",          "XFDIRENTRY" },
256     { "directory-direntry",     "XDDIRENTRY" },
257 };
258
259 static prefix_t BOOLEAN_PREFIX_EXTERNAL[] = {
260     { "thread",                 "G" },
261     { "tag",                    "K" },
262     { "is",                     "K" },
263     { "id",                     "Q" },
264     { "path",                   "P" },
265     { "property",               "XPROPERTY" },
266     /*
267      * Unconditionally add ':' to reduce potential ambiguity with
268      * overlapping prefixes and/or terms that start with capital
269      * letters. See Xapian document termprefixes.html for related
270      * discussion.
271      */
272     { "folder",                 "XFOLDER:" },
273 };
274
275 static prefix_t PROBABILISTIC_PREFIX[]= {
276     { "from",                   "XFROM" },
277     { "to",                     "XTO" },
278     { "attachment",             "XATTACHMENT" },
279     { "mimetype",               "XMIMETYPE"},
280     { "subject",                "XSUBJECT"},
281 };
282
283 const char *
284 _find_prefix (const char *name)
285 {
286     unsigned int i;
287
288     for (i = 0; i < ARRAY_SIZE (BOOLEAN_PREFIX_INTERNAL); i++) {
289         if (strcmp (name, BOOLEAN_PREFIX_INTERNAL[i].name) == 0)
290             return BOOLEAN_PREFIX_INTERNAL[i].prefix;
291     }
292
293     for (i = 0; i < ARRAY_SIZE (BOOLEAN_PREFIX_EXTERNAL); i++) {
294         if (strcmp (name, BOOLEAN_PREFIX_EXTERNAL[i].name) == 0)
295             return BOOLEAN_PREFIX_EXTERNAL[i].prefix;
296     }
297
298     for (i = 0; i < ARRAY_SIZE (PROBABILISTIC_PREFIX); i++) {
299         if (strcmp (name, PROBABILISTIC_PREFIX[i].name) == 0)
300             return PROBABILISTIC_PREFIX[i].prefix;
301     }
302
303     INTERNAL_ERROR ("No prefix exists for '%s'\n", name);
304
305     return "";
306 }
307
308 static const struct {
309     /* NOTMUCH_FEATURE_* value. */
310     _notmuch_features value;
311     /* Feature name as it appears in the database.  This name should
312      * be appropriate for displaying to the user if an older version
313      * of notmuch doesn't support this feature. */
314     const char *name;
315     /* Compatibility flags when this feature is declared. */
316     const char *flags;
317 } feature_names[] = {
318     { NOTMUCH_FEATURE_FILE_TERMS,
319       "multiple paths per message", "rw" },
320     { NOTMUCH_FEATURE_DIRECTORY_DOCS,
321       "relative directory paths", "rw" },
322     /* Header values are not required for reading a database because a
323      * reader can just refer to the message file. */
324     { NOTMUCH_FEATURE_FROM_SUBJECT_ID_VALUES,
325       "from/subject/message-ID in database", "w" },
326     { NOTMUCH_FEATURE_BOOL_FOLDER,
327       "exact folder:/path: search", "rw" },
328     { NOTMUCH_FEATURE_GHOSTS,
329       "mail documents for missing messages", "w"},
330     /* Knowledge of the index mime-types are not required for reading
331      * a database because a reader will just be unable to query
332      * them. */
333     { NOTMUCH_FEATURE_INDEXED_MIMETYPES,
334       "indexed MIME types", "w"},
335     { NOTMUCH_FEATURE_LAST_MOD,
336       "modification tracking", "w"},
337 };
338
339 const char *
340 notmuch_status_to_string (notmuch_status_t status)
341 {
342     switch (status) {
343     case NOTMUCH_STATUS_SUCCESS:
344         return "No error occurred";
345     case NOTMUCH_STATUS_OUT_OF_MEMORY:
346         return "Out of memory";
347     case NOTMUCH_STATUS_READ_ONLY_DATABASE:
348         return "Attempt to write to a read-only database";
349     case NOTMUCH_STATUS_XAPIAN_EXCEPTION:
350         return "A Xapian exception occurred";
351     case NOTMUCH_STATUS_FILE_ERROR:
352         return "Something went wrong trying to read or write a file";
353     case NOTMUCH_STATUS_FILE_NOT_EMAIL:
354         return "File is not an email";
355     case NOTMUCH_STATUS_DUPLICATE_MESSAGE_ID:
356         return "Message ID is identical to a message in database";
357     case NOTMUCH_STATUS_NULL_POINTER:
358         return "Erroneous NULL pointer";
359     case NOTMUCH_STATUS_TAG_TOO_LONG:
360         return "Tag value is too long (exceeds NOTMUCH_TAG_MAX)";
361     case NOTMUCH_STATUS_UNBALANCED_FREEZE_THAW:
362         return "Unbalanced number of calls to notmuch_message_freeze/thaw";
363     case NOTMUCH_STATUS_UNBALANCED_ATOMIC:
364         return "Unbalanced number of calls to notmuch_database_begin_atomic/end_atomic";
365     case NOTMUCH_STATUS_UNSUPPORTED_OPERATION:
366         return "Unsupported operation";
367     case NOTMUCH_STATUS_UPGRADE_REQUIRED:
368         return "Operation requires a database upgrade";
369     case NOTMUCH_STATUS_PATH_ERROR:
370         return "Path supplied is illegal for this function";
371     default:
372     case NOTMUCH_STATUS_LAST_STATUS:
373         return "Unknown error status value";
374     }
375 }
376
377 void
378 _notmuch_database_log (notmuch_database_t *notmuch,
379                       const char *format,
380                       ...)
381 {
382     va_list va_args;
383
384     va_start (va_args, format);
385
386     if (notmuch->status_string)
387         talloc_free (notmuch->status_string);
388
389     notmuch->status_string = talloc_vasprintf (notmuch, format, va_args);
390     va_end (va_args);
391 }
392
393 void
394 _notmuch_database_log_append (notmuch_database_t *notmuch,
395                       const char *format,
396                       ...)
397 {
398     va_list va_args;
399
400     va_start (va_args, format);
401
402     if (notmuch->status_string)
403         notmuch->status_string = talloc_vasprintf_append (notmuch->status_string, format, va_args);
404     else
405         notmuch->status_string = talloc_vasprintf (notmuch, format, va_args);
406
407     va_end (va_args);
408 }
409
410 static void
411 find_doc_ids_for_term (notmuch_database_t *notmuch,
412                        const char *term,
413                        Xapian::PostingIterator *begin,
414                        Xapian::PostingIterator *end)
415 {
416     *begin = notmuch->xapian_db->postlist_begin (term);
417
418     *end = notmuch->xapian_db->postlist_end (term);
419 }
420
421 static void
422 find_doc_ids (notmuch_database_t *notmuch,
423               const char *prefix_name,
424               const char *value,
425               Xapian::PostingIterator *begin,
426               Xapian::PostingIterator *end)
427 {
428     char *term;
429
430     term = talloc_asprintf (notmuch, "%s%s",
431                             _find_prefix (prefix_name), value);
432
433     find_doc_ids_for_term (notmuch, term, begin, end);
434
435     talloc_free (term);
436 }
437
438 notmuch_private_status_t
439 _notmuch_database_find_unique_doc_id (notmuch_database_t *notmuch,
440                                       const char *prefix_name,
441                                       const char *value,
442                                       unsigned int *doc_id)
443 {
444     Xapian::PostingIterator i, end;
445
446     find_doc_ids (notmuch, prefix_name, value, &i, &end);
447
448     if (i == end) {
449         *doc_id = 0;
450         return NOTMUCH_PRIVATE_STATUS_NO_DOCUMENT_FOUND;
451     }
452
453     *doc_id = *i;
454
455 #if DEBUG_DATABASE_SANITY
456     i++;
457
458     if (i != end)
459         INTERNAL_ERROR ("Term %s:%s is not unique as expected.\n",
460                         prefix_name, value);
461 #endif
462
463     return NOTMUCH_PRIVATE_STATUS_SUCCESS;
464 }
465
466 static Xapian::Document
467 find_document_for_doc_id (notmuch_database_t *notmuch, unsigned doc_id)
468 {
469     return notmuch->xapian_db->get_document (doc_id);
470 }
471
472 /* Generate a compressed version of 'message_id' of the form:
473  *
474  *      notmuch-sha1-<sha1_sum_of_message_id>
475  */
476 char *
477 _notmuch_message_id_compressed (void *ctx, const char *message_id)
478 {
479     char *sha1, *compressed;
480
481     sha1 = _notmuch_sha1_of_string (message_id);
482
483     compressed = talloc_asprintf (ctx, "notmuch-sha1-%s", sha1);
484     free (sha1);
485
486     return compressed;
487 }
488
489 notmuch_status_t
490 notmuch_database_find_message (notmuch_database_t *notmuch,
491                                const char *message_id,
492                                notmuch_message_t **message_ret)
493 {
494     notmuch_private_status_t status;
495     unsigned int doc_id;
496
497     if (message_ret == NULL)
498         return NOTMUCH_STATUS_NULL_POINTER;
499
500     if (strlen (message_id) > NOTMUCH_MESSAGE_ID_MAX)
501         message_id = _notmuch_message_id_compressed (notmuch, message_id);
502
503     try {
504         status = _notmuch_database_find_unique_doc_id (notmuch, "id",
505                                                        message_id, &doc_id);
506
507         if (status == NOTMUCH_PRIVATE_STATUS_NO_DOCUMENT_FOUND)
508             *message_ret = NULL;
509         else {
510             *message_ret = _notmuch_message_create (notmuch, notmuch, doc_id,
511                                                     NULL);
512             if (*message_ret == NULL)
513                 return NOTMUCH_STATUS_OUT_OF_MEMORY;
514         }
515
516         return NOTMUCH_STATUS_SUCCESS;
517     } catch (const Xapian::Error &error) {
518         _notmuch_database_log (notmuch, "A Xapian exception occurred finding message: %s.\n",
519                  error.get_msg().c_str());
520         notmuch->exception_reported = TRUE;
521         *message_ret = NULL;
522         return NOTMUCH_STATUS_XAPIAN_EXCEPTION;
523     }
524 }
525
526 /* Advance 'str' past any whitespace or RFC 822 comments. A comment is
527  * a (potentially nested) parenthesized sequence with '\' used to
528  * escape any character (including parentheses).
529  *
530  * If the sequence to be skipped continues to the end of the string,
531  * then 'str' will be left pointing at the final terminating '\0'
532  * character.
533  */
534 static void
535 skip_space_and_comments (const char **str)
536 {
537     const char *s;
538
539     s = *str;
540     while (*s && (isspace (*s) || *s == '(')) {
541         while (*s && isspace (*s))
542             s++;
543         if (*s == '(') {
544             int nesting = 1;
545             s++;
546             while (*s && nesting) {
547                 if (*s == '(') {
548                     nesting++;
549                 } else if (*s == ')') {
550                     nesting--;
551                 } else if (*s == '\\') {
552                     if (*(s+1))
553                         s++;
554                 }
555                 s++;
556             }
557         }
558     }
559
560     *str = s;
561 }
562
563 /* Parse an RFC 822 message-id, discarding whitespace, any RFC 822
564  * comments, and the '<' and '>' delimiters.
565  *
566  * If not NULL, then *next will be made to point to the first character
567  * not parsed, (possibly pointing to the final '\0' terminator.
568  *
569  * Returns a newly talloc'ed string belonging to 'ctx'.
570  *
571  * Returns NULL if there is any error parsing the message-id. */
572 static char *
573 _parse_message_id (void *ctx, const char *message_id, const char **next)
574 {
575     const char *s, *end;
576     char *result;
577
578     if (message_id == NULL || *message_id == '\0')
579         return NULL;
580
581     s = message_id;
582
583     skip_space_and_comments (&s);
584
585     /* Skip any unstructured text as well. */
586     while (*s && *s != '<')
587         s++;
588
589     if (*s == '<') {
590         s++;
591     } else {
592         if (next)
593             *next = s;
594         return NULL;
595     }
596
597     skip_space_and_comments (&s);
598
599     end = s;
600     while (*end && *end != '>')
601         end++;
602     if (next) {
603         if (*end)
604             *next = end + 1;
605         else
606             *next = end;
607     }
608
609     if (end > s && *end == '>')
610         end--;
611     if (end <= s)
612         return NULL;
613
614     result = talloc_strndup (ctx, s, end - s + 1);
615
616     /* Finally, collapse any whitespace that is within the message-id
617      * itself. */
618     {
619         char *r;
620         int len;
621
622         for (r = result, len = strlen (r); *r; r++, len--)
623             if (*r == ' ' || *r == '\t')
624                 memmove (r, r+1, len);
625     }
626
627     return result;
628 }
629
630 /* Parse a References header value, putting a (talloc'ed under 'ctx')
631  * copy of each referenced message-id into 'hash'.
632  *
633  * We explicitly avoid including any reference identical to
634  * 'message_id' in the result (to avoid mass confusion when a single
635  * message references itself cyclically---and yes, mail messages are
636  * not infrequent in the wild that do this---don't ask me why).
637  *
638  * Return the last reference parsed, if it is not equal to message_id.
639  */
640 static char *
641 parse_references (void *ctx,
642                   const char *message_id,
643                   GHashTable *hash,
644                   const char *refs)
645 {
646     char *ref, *last_ref = NULL;
647
648     if (refs == NULL || *refs == '\0')
649         return NULL;
650
651     while (*refs) {
652         ref = _parse_message_id (ctx, refs, &refs);
653
654         if (ref && strcmp (ref, message_id)) {
655             g_hash_table_add (hash, ref);
656             last_ref = ref;
657         }
658     }
659
660     /* The return value of this function is used to add a parent
661      * reference to the database.  We should avoid making a message
662      * its own parent, thus the above check.
663      */
664     return talloc_strdup(ctx, last_ref);
665 }
666
667 notmuch_status_t
668 notmuch_database_create (const char *path, notmuch_database_t **database)
669 {
670     char *status_string = NULL;
671     notmuch_status_t status;
672
673     status = notmuch_database_create_verbose (path, database,
674                                               &status_string);
675
676     if (status_string) {
677         fputs (status_string, stderr);
678         free (status_string);
679     }
680
681     return status;
682 }
683
684 notmuch_status_t
685 notmuch_database_create_verbose (const char *path,
686                                  notmuch_database_t **database,
687                                  char **status_string)
688 {
689     notmuch_status_t status = NOTMUCH_STATUS_SUCCESS;
690     notmuch_database_t *notmuch = NULL;
691     char *notmuch_path = NULL;
692     char *message = NULL;
693     struct stat st;
694     int err;
695
696     if (path == NULL) {
697         message = strdup ("Error: Cannot create a database for a NULL path.\n");
698         status = NOTMUCH_STATUS_NULL_POINTER;
699         goto DONE;
700     }
701
702     if (path[0] != '/') {
703         message = strdup ("Error: Database path must be absolute.\n");
704         status = NOTMUCH_STATUS_PATH_ERROR;
705         goto DONE;
706     }
707
708     err = stat (path, &st);
709     if (err) {
710         IGNORE_RESULT (asprintf (&message, "Error: Cannot create database at %s: %s.\n",
711                                 path, strerror (errno)));
712         status = NOTMUCH_STATUS_FILE_ERROR;
713         goto DONE;
714     }
715
716     if (! S_ISDIR (st.st_mode)) {
717         IGNORE_RESULT (asprintf (&message, "Error: Cannot create database at %s: "
718                                  "Not a directory.\n",
719                                  path));
720         status = NOTMUCH_STATUS_FILE_ERROR;
721         goto DONE;
722     }
723
724     notmuch_path = talloc_asprintf (NULL, "%s/%s", path, ".notmuch");
725
726     err = mkdir (notmuch_path, 0755);
727
728     if (err) {
729         IGNORE_RESULT (asprintf (&message, "Error: Cannot create directory %s: %s.\n",
730                                  notmuch_path, strerror (errno)));
731         status = NOTMUCH_STATUS_FILE_ERROR;
732         goto DONE;
733     }
734
735     status = notmuch_database_open_verbose (path,
736                                             NOTMUCH_DATABASE_MODE_READ_WRITE,
737                                             &notmuch, &message);
738     if (status)
739         goto DONE;
740
741     /* Upgrade doesn't add these feature to existing databases, but
742      * new databases have them. */
743     notmuch->features |= NOTMUCH_FEATURE_FROM_SUBJECT_ID_VALUES;
744     notmuch->features |= NOTMUCH_FEATURE_INDEXED_MIMETYPES;
745
746     status = notmuch_database_upgrade (notmuch, NULL, NULL);
747     if (status) {
748         notmuch_database_close(notmuch);
749         notmuch = NULL;
750     }
751
752   DONE:
753     if (notmuch_path)
754         talloc_free (notmuch_path);
755
756     if (message) {
757         if (status_string)
758             *status_string = message;
759         else
760             free (message);
761     }
762     if (database)
763         *database = notmuch;
764     else
765         talloc_free (notmuch);
766     return status;
767 }
768
769 notmuch_status_t
770 _notmuch_database_ensure_writable (notmuch_database_t *notmuch)
771 {
772     if (notmuch->mode == NOTMUCH_DATABASE_MODE_READ_ONLY) {
773         _notmuch_database_log (notmuch, "Cannot write to a read-only database.\n");
774         return NOTMUCH_STATUS_READ_ONLY_DATABASE;
775     }
776
777     return NOTMUCH_STATUS_SUCCESS;
778 }
779
780 /* Allocate a revision number for the next change. */
781 unsigned long
782 _notmuch_database_new_revision (notmuch_database_t *notmuch)
783 {
784     unsigned long new_revision = notmuch->revision + 1;
785
786     /* If we're in an atomic section, hold off on updating the
787      * committed revision number until we commit the atomic section.
788      */
789     if (notmuch->atomic_nesting)
790         notmuch->atomic_dirty = TRUE;
791     else
792         notmuch->revision = new_revision;
793
794     return new_revision;
795 }
796
797 /* Parse a database features string from the given database version.
798  * Returns the feature bit set.
799  *
800  * For version < 3, this ignores the features string and returns a
801  * hard-coded set of features.
802  *
803  * If there are unrecognized features that are required to open the
804  * database in mode (which should be 'r' or 'w'), return a
805  * comma-separated list of unrecognized but required features in
806  * *incompat_out suitable for presenting to the user.  *incompat_out
807  * will be allocated from ctx.
808  */
809 static _notmuch_features
810 _parse_features (const void *ctx, const char *features, unsigned int version,
811                  char mode, char **incompat_out)
812 {
813     _notmuch_features res = static_cast<_notmuch_features>(0);
814     unsigned int namelen, i;
815     size_t llen = 0;
816     const char *flags;
817
818     /* Prior to database version 3, features were implied by the
819      * version number. */
820     if (version == 0)
821         return NOTMUCH_FEATURES_V0;
822     else if (version == 1)
823         return NOTMUCH_FEATURES_V1;
824     else if (version == 2)
825         return NOTMUCH_FEATURES_V2;
826
827     /* Parse the features string */
828     while ((features = strtok_len_c (features + llen, "\n", &llen)) != NULL) {
829         flags = strchr (features, '\t');
830         if (! flags || flags > features + llen)
831             continue;
832         namelen = flags - features;
833
834         for (i = 0; i < ARRAY_SIZE (feature_names); ++i) {
835             if (strlen (feature_names[i].name) == namelen &&
836                 strncmp (feature_names[i].name, features, namelen) == 0) {
837                 res |= feature_names[i].value;
838                 break;
839             }
840         }
841
842         if (i == ARRAY_SIZE (feature_names) && incompat_out) {
843             /* Unrecognized feature */
844             const char *have = strchr (flags, mode);
845             if (have && have < features + llen) {
846                 /* This feature is required to access this database in
847                  * 'mode', but we don't understand it. */
848                 if (! *incompat_out)
849                     *incompat_out = talloc_strdup (ctx, "");
850                 *incompat_out = talloc_asprintf_append_buffer (
851                     *incompat_out, "%s%.*s", **incompat_out ? ", " : "",
852                     namelen, features);
853             }
854         }
855     }
856
857     return res;
858 }
859
860 static char *
861 _print_features (const void *ctx, unsigned int features)
862 {
863     unsigned int i;
864     char *res = talloc_strdup (ctx, "");
865
866     for (i = 0; i < ARRAY_SIZE (feature_names); ++i)
867         if (features & feature_names[i].value)
868             res = talloc_asprintf_append_buffer (
869                 res, "%s\t%s\n", feature_names[i].name, feature_names[i].flags);
870
871     return res;
872 }
873
874 notmuch_status_t
875 notmuch_database_open (const char *path,
876                        notmuch_database_mode_t mode,
877                        notmuch_database_t **database)
878 {
879     char *status_string = NULL;
880     notmuch_status_t status;
881
882     status = notmuch_database_open_verbose (path, mode, database,
883                                            &status_string);
884
885     if (status_string) {
886         fputs (status_string, stderr);
887         free (status_string);
888     }
889
890     return status;
891 }
892
893 notmuch_status_t
894 notmuch_database_open_verbose (const char *path,
895                                notmuch_database_mode_t mode,
896                                notmuch_database_t **database,
897                                char **status_string)
898 {
899     notmuch_status_t status = NOTMUCH_STATUS_SUCCESS;
900     void *local = talloc_new (NULL);
901     notmuch_database_t *notmuch = NULL;
902     char *notmuch_path, *xapian_path, *incompat_features;
903     char *message = NULL;
904     struct stat st;
905     int err;
906     unsigned int i, version;
907     static int initialized = 0;
908
909     if (path == NULL) {
910         message = strdup ("Error: Cannot open a database for a NULL path.\n");
911         status = NOTMUCH_STATUS_NULL_POINTER;
912         goto DONE;
913     }
914
915     if (path[0] != '/') {
916         message = strdup ("Error: Database path must be absolute.\n");
917         status = NOTMUCH_STATUS_PATH_ERROR;
918         goto DONE;
919     }
920
921     if (! (notmuch_path = talloc_asprintf (local, "%s/%s", path, ".notmuch"))) {
922         message = strdup ("Out of memory\n");
923         status = NOTMUCH_STATUS_OUT_OF_MEMORY;
924         goto DONE;
925     }
926
927     err = stat (notmuch_path, &st);
928     if (err) {
929         IGNORE_RESULT (asprintf (&message, "Error opening database at %s: %s\n",
930                                  notmuch_path, strerror (errno)));
931         status = NOTMUCH_STATUS_FILE_ERROR;
932         goto DONE;
933     }
934
935     if (! (xapian_path = talloc_asprintf (local, "%s/%s", notmuch_path, "xapian"))) {
936         message = strdup ("Out of memory\n");
937         status = NOTMUCH_STATUS_OUT_OF_MEMORY;
938         goto DONE;
939     }
940
941     /* Initialize the GLib type system and threads */
942 #if !GLIB_CHECK_VERSION(2, 35, 1)
943     g_type_init ();
944 #endif
945
946     /* Initialize gmime */
947     if (! initialized) {
948         g_mime_init (GMIME_ENABLE_RFC2047_WORKAROUNDS);
949         initialized = 1;
950     }
951
952     notmuch = talloc_zero (NULL, notmuch_database_t);
953     notmuch->exception_reported = FALSE;
954     notmuch->status_string = NULL;
955     notmuch->path = talloc_strdup (notmuch, path);
956
957     if (notmuch->path[strlen (notmuch->path) - 1] == '/')
958         notmuch->path[strlen (notmuch->path) - 1] = '\0';
959
960     notmuch->mode = mode;
961     notmuch->atomic_nesting = 0;
962     try {
963         string last_thread_id;
964         string last_mod;
965
966         if (mode == NOTMUCH_DATABASE_MODE_READ_WRITE) {
967             notmuch->xapian_db = new Xapian::WritableDatabase (xapian_path,
968                                                                DB_ACTION);
969         } else {
970             notmuch->xapian_db = new Xapian::Database (xapian_path);
971         }
972
973         /* Check version.  As of database version 3, we represent
974          * changes in terms of features, so assume a version bump
975          * means a dramatically incompatible change. */
976         version = notmuch_database_get_version (notmuch);
977         if (version > NOTMUCH_DATABASE_VERSION) {
978             IGNORE_RESULT (asprintf (&message,
979                       "Error: Notmuch database at %s\n"
980                       "       has a newer database format version (%u) than supported by this\n"
981                       "       version of notmuch (%u).\n",
982                                      notmuch_path, version, NOTMUCH_DATABASE_VERSION));
983             notmuch->mode = NOTMUCH_DATABASE_MODE_READ_ONLY;
984             notmuch_database_destroy (notmuch);
985             notmuch = NULL;
986             status = NOTMUCH_STATUS_FILE_ERROR;
987             goto DONE;
988         }
989
990         /* Check features. */
991         incompat_features = NULL;
992         notmuch->features = _parse_features (
993             local, notmuch->xapian_db->get_metadata ("features").c_str (),
994             version, mode == NOTMUCH_DATABASE_MODE_READ_WRITE ? 'w' : 'r',
995             &incompat_features);
996         if (incompat_features) {
997             IGNORE_RESULT (asprintf (&message,
998                 "Error: Notmuch database at %s\n"
999                 "       requires features (%s)\n"
1000                 "       not supported by this version of notmuch.\n",
1001                                      notmuch_path, incompat_features));
1002             notmuch->mode = NOTMUCH_DATABASE_MODE_READ_ONLY;
1003             notmuch_database_destroy (notmuch);
1004             notmuch = NULL;
1005             status = NOTMUCH_STATUS_FILE_ERROR;
1006             goto DONE;
1007         }
1008
1009         notmuch->last_doc_id = notmuch->xapian_db->get_lastdocid ();
1010         last_thread_id = notmuch->xapian_db->get_metadata ("last_thread_id");
1011         if (last_thread_id.empty ()) {
1012             notmuch->last_thread_id = 0;
1013         } else {
1014             const char *str;
1015             char *end;
1016
1017             str = last_thread_id.c_str ();
1018             notmuch->last_thread_id = strtoull (str, &end, 16);
1019             if (*end != '\0')
1020                 INTERNAL_ERROR ("Malformed database last_thread_id: %s", str);
1021         }
1022
1023         /* Get current highest revision number. */
1024         last_mod = notmuch->xapian_db->get_value_upper_bound (
1025             NOTMUCH_VALUE_LAST_MOD);
1026         if (last_mod.empty ())
1027             notmuch->revision = 0;
1028         else
1029             notmuch->revision = Xapian::sortable_unserialise (last_mod);
1030         notmuch->uuid = talloc_strdup (
1031             notmuch, notmuch->xapian_db->get_uuid ().c_str ());
1032
1033         notmuch->query_parser = new Xapian::QueryParser;
1034         notmuch->term_gen = new Xapian::TermGenerator;
1035         notmuch->term_gen->set_stemmer (Xapian::Stem ("english"));
1036         notmuch->value_range_processor = new Xapian::NumberValueRangeProcessor (NOTMUCH_VALUE_TIMESTAMP);
1037         notmuch->date_range_processor = new ParseTimeValueRangeProcessor (NOTMUCH_VALUE_TIMESTAMP);
1038 #if HAVE_XAPIAN_FIELD_PROCESSOR
1039         /* This currently relies on the query parser to pass anything
1040          * with a .. to the range processor */
1041         notmuch->date_field_processor = new DateFieldProcessor();
1042         notmuch->query_parser->add_boolean_prefix("date", notmuch->date_field_processor);
1043         notmuch->query_field_processor = new QueryFieldProcessor (*notmuch->query_parser, notmuch);
1044         notmuch->query_parser->add_boolean_prefix("query", notmuch->query_field_processor);
1045 #endif
1046         notmuch->last_mod_range_processor = new Xapian::NumberValueRangeProcessor (NOTMUCH_VALUE_LAST_MOD, "lastmod:");
1047
1048         notmuch->query_parser->set_default_op (Xapian::Query::OP_AND);
1049         notmuch->query_parser->set_database (*notmuch->xapian_db);
1050         notmuch->query_parser->set_stemmer (Xapian::Stem ("english"));
1051         notmuch->query_parser->set_stemming_strategy (Xapian::QueryParser::STEM_SOME);
1052         notmuch->query_parser->add_valuerangeprocessor (notmuch->value_range_processor);
1053         notmuch->query_parser->add_valuerangeprocessor (notmuch->date_range_processor);
1054         notmuch->query_parser->add_valuerangeprocessor (notmuch->last_mod_range_processor);
1055
1056         for (i = 0; i < ARRAY_SIZE (BOOLEAN_PREFIX_EXTERNAL); i++) {
1057             prefix_t *prefix = &BOOLEAN_PREFIX_EXTERNAL[i];
1058             notmuch->query_parser->add_boolean_prefix (prefix->name,
1059                                                        prefix->prefix);
1060         }
1061
1062         for (i = 0; i < ARRAY_SIZE (PROBABILISTIC_PREFIX); i++) {
1063             prefix_t *prefix = &PROBABILISTIC_PREFIX[i];
1064             notmuch->query_parser->add_prefix (prefix->name, prefix->prefix);
1065         }
1066     } catch (const Xapian::Error &error) {
1067         IGNORE_RESULT (asprintf (&message, "A Xapian exception occurred opening database: %s\n",
1068                                  error.get_msg().c_str()));
1069         notmuch_database_destroy (notmuch);
1070         notmuch = NULL;
1071         status = NOTMUCH_STATUS_XAPIAN_EXCEPTION;
1072     }
1073
1074   DONE:
1075     talloc_free (local);
1076
1077     if (message) {
1078         if (status_string)
1079             *status_string = message;
1080         else
1081             free (message);
1082     }
1083
1084     if (database)
1085         *database = notmuch;
1086     else
1087         talloc_free (notmuch);
1088     return status;
1089 }
1090
1091 notmuch_status_t
1092 notmuch_database_close (notmuch_database_t *notmuch)
1093 {
1094     notmuch_status_t status = NOTMUCH_STATUS_SUCCESS;
1095
1096     /* Many Xapian objects (and thus notmuch objects) hold references to
1097      * the database, so merely deleting the database may not suffice to
1098      * close it.  Thus, we explicitly close it here. */
1099     if (notmuch->xapian_db != NULL) {
1100         try {
1101             /* If there's an outstanding transaction, it's unclear if
1102              * closing the Xapian database commits everything up to
1103              * that transaction, or may discard committed (but
1104              * unflushed) transactions.  To be certain, explicitly
1105              * cancel any outstanding transaction before closing. */
1106             if (notmuch->mode == NOTMUCH_DATABASE_MODE_READ_WRITE &&
1107                 notmuch->atomic_nesting)
1108                 (static_cast <Xapian::WritableDatabase *> (notmuch->xapian_db))
1109                     ->cancel_transaction ();
1110
1111             /* Close the database.  This implicitly flushes
1112              * outstanding changes. */
1113             notmuch->xapian_db->close();
1114         } catch (const Xapian::Error &error) {
1115             status = NOTMUCH_STATUS_XAPIAN_EXCEPTION;
1116             if (! notmuch->exception_reported) {
1117                 _notmuch_database_log (notmuch, "Error: A Xapian exception occurred closing database: %s\n",
1118                          error.get_msg().c_str());
1119             }
1120         }
1121     }
1122
1123     delete notmuch->term_gen;
1124     notmuch->term_gen = NULL;
1125     delete notmuch->query_parser;
1126     notmuch->query_parser = NULL;
1127     delete notmuch->xapian_db;
1128     notmuch->xapian_db = NULL;
1129     delete notmuch->value_range_processor;
1130     notmuch->value_range_processor = NULL;
1131     delete notmuch->date_range_processor;
1132     notmuch->date_range_processor = NULL;
1133     delete notmuch->last_mod_range_processor;
1134     notmuch->last_mod_range_processor = NULL;
1135
1136 #if HAVE_XAPIAN_FIELD_PROCESSOR
1137     delete notmuch->date_field_processor;
1138     notmuch->date_field_processor = NULL;
1139     delete notmuch->query_field_processor;
1140     notmuch->query_field_processor = NULL;
1141 #endif
1142
1143     return status;
1144 }
1145
1146 static int
1147 unlink_cb (const char *path,
1148            unused (const struct stat *sb),
1149            unused (int type),
1150            unused (struct FTW *ftw))
1151 {
1152     return remove (path);
1153 }
1154
1155 static int
1156 rmtree (const char *path)
1157 {
1158     return nftw (path, unlink_cb, 64, FTW_DEPTH | FTW_PHYS);
1159 }
1160
1161 class NotmuchCompactor : public Xapian::Compactor
1162 {
1163     notmuch_compact_status_cb_t status_cb;
1164     void *status_closure;
1165
1166 public:
1167     NotmuchCompactor(notmuch_compact_status_cb_t cb, void *closure) :
1168         status_cb (cb), status_closure (closure) { }
1169
1170     virtual void
1171     set_status (const std::string &table, const std::string &status)
1172     {
1173         char *msg;
1174
1175         if (status_cb == NULL)
1176             return;
1177
1178         if (status.length () == 0)
1179             msg = talloc_asprintf (NULL, "compacting table %s", table.c_str());
1180         else
1181             msg = talloc_asprintf (NULL, "     %s", status.c_str());
1182
1183         if (msg == NULL) {
1184             return;
1185         }
1186
1187         status_cb (msg, status_closure);
1188         talloc_free (msg);
1189     }
1190 };
1191
1192 /* Compacts the given database, optionally saving the original database
1193  * in backup_path. Additionally, a callback function can be provided to
1194  * give the user feedback on the progress of the (likely long-lived)
1195  * compaction process.
1196  *
1197  * The backup path must point to a directory on the same volume as the
1198  * original database. Passing a NULL backup_path will result in the
1199  * uncompacted database being deleted after compaction has finished.
1200  * Note that the database write lock will be held during the
1201  * compaction process to protect data integrity.
1202  */
1203 notmuch_status_t
1204 notmuch_database_compact (const char *path,
1205                           const char *backup_path,
1206                           notmuch_compact_status_cb_t status_cb,
1207                           void *closure)
1208 {
1209     void *local;
1210     char *notmuch_path, *xapian_path, *compact_xapian_path;
1211     notmuch_status_t ret = NOTMUCH_STATUS_SUCCESS;
1212     notmuch_database_t *notmuch = NULL;
1213     struct stat statbuf;
1214     notmuch_bool_t keep_backup;
1215     char *message = NULL;
1216
1217     local = talloc_new (NULL);
1218     if (! local)
1219         return NOTMUCH_STATUS_OUT_OF_MEMORY;
1220
1221     ret = notmuch_database_open_verbose (path,
1222                                          NOTMUCH_DATABASE_MODE_READ_WRITE,
1223                                          &notmuch,
1224                                          &message);
1225     if (ret) {
1226         if (status_cb) status_cb (message, closure);
1227         goto DONE;
1228     }
1229
1230     if (! (notmuch_path = talloc_asprintf (local, "%s/%s", path, ".notmuch"))) {
1231         ret = NOTMUCH_STATUS_OUT_OF_MEMORY;
1232         goto DONE;
1233     }
1234
1235     if (! (xapian_path = talloc_asprintf (local, "%s/%s", notmuch_path, "xapian"))) {
1236         ret = NOTMUCH_STATUS_OUT_OF_MEMORY;
1237         goto DONE;
1238     }
1239
1240     if (! (compact_xapian_path = talloc_asprintf (local, "%s.compact", xapian_path))) {
1241         ret = NOTMUCH_STATUS_OUT_OF_MEMORY;
1242         goto DONE;
1243     }
1244
1245     if (backup_path == NULL) {
1246         if (! (backup_path = talloc_asprintf (local, "%s.old", xapian_path))) {
1247             ret = NOTMUCH_STATUS_OUT_OF_MEMORY;
1248             goto DONE;
1249         }
1250         keep_backup = FALSE;
1251     }
1252     else {
1253         keep_backup = TRUE;
1254     }
1255
1256     if (stat (backup_path, &statbuf) != -1) {
1257         _notmuch_database_log (notmuch, "Path already exists: %s\n", backup_path);
1258         ret = NOTMUCH_STATUS_FILE_ERROR;
1259         goto DONE;
1260     }
1261     if (errno != ENOENT) {
1262         _notmuch_database_log (notmuch, "Unknown error while stat()ing path: %s\n",
1263                  strerror (errno));
1264         ret = NOTMUCH_STATUS_FILE_ERROR;
1265         goto DONE;
1266     }
1267
1268     /* Unconditionally attempt to remove old work-in-progress database (if
1269      * any). This is "protected" by database lock. If this fails due to write
1270      * errors (etc), the following code will fail and provide error message.
1271      */
1272     (void) rmtree (compact_xapian_path);
1273
1274     try {
1275         NotmuchCompactor compactor (status_cb, closure);
1276
1277         compactor.set_renumber (false);
1278         compactor.add_source (xapian_path);
1279         compactor.set_destdir (compact_xapian_path);
1280         compactor.compact ();
1281     } catch (const Xapian::Error &error) {
1282         _notmuch_database_log (notmuch, "Error while compacting: %s\n", error.get_msg().c_str());
1283         ret = NOTMUCH_STATUS_XAPIAN_EXCEPTION;
1284         goto DONE;
1285     }
1286
1287     if (rename (xapian_path, backup_path)) {
1288         _notmuch_database_log (notmuch, "Error moving %s to %s: %s\n",
1289                  xapian_path, backup_path, strerror (errno));
1290         ret = NOTMUCH_STATUS_FILE_ERROR;
1291         goto DONE;
1292     }
1293
1294     if (rename (compact_xapian_path, xapian_path)) {
1295         _notmuch_database_log (notmuch, "Error moving %s to %s: %s\n",
1296                  compact_xapian_path, xapian_path, strerror (errno));
1297         ret = NOTMUCH_STATUS_FILE_ERROR;
1298         goto DONE;
1299     }
1300
1301     if (! keep_backup) {
1302         if (rmtree (backup_path)) {
1303             _notmuch_database_log (notmuch, "Error removing old database %s: %s\n",
1304                      backup_path, strerror (errno));
1305             ret = NOTMUCH_STATUS_FILE_ERROR;
1306             goto DONE;
1307         }
1308     }
1309
1310   DONE:
1311     if (notmuch) {
1312         notmuch_status_t ret2;
1313
1314         const char *str = notmuch_database_status_string (notmuch);
1315         if (status_cb && str)
1316             status_cb (str, closure);
1317
1318         ret2 = notmuch_database_destroy (notmuch);
1319
1320         /* don't clobber previous error status */
1321         if (ret == NOTMUCH_STATUS_SUCCESS && ret2 != NOTMUCH_STATUS_SUCCESS)
1322             ret = ret2;
1323     }
1324
1325     talloc_free (local);
1326
1327     return ret;
1328 }
1329
1330 notmuch_status_t
1331 notmuch_database_destroy (notmuch_database_t *notmuch)
1332 {
1333     notmuch_status_t status;
1334
1335     status = notmuch_database_close (notmuch);
1336     talloc_free (notmuch);
1337
1338     return status;
1339 }
1340
1341 const char *
1342 notmuch_database_get_path (notmuch_database_t *notmuch)
1343 {
1344     return notmuch->path;
1345 }
1346
1347 unsigned int
1348 notmuch_database_get_version (notmuch_database_t *notmuch)
1349 {
1350     unsigned int version;
1351     string version_string;
1352     const char *str;
1353     char *end;
1354
1355     version_string = notmuch->xapian_db->get_metadata ("version");
1356     if (version_string.empty ())
1357         return 0;
1358
1359     str = version_string.c_str ();
1360     if (str == NULL || *str == '\0')
1361         return 0;
1362
1363     version = strtoul (str, &end, 10);
1364     if (*end != '\0')
1365         INTERNAL_ERROR ("Malformed database version: %s", str);
1366
1367     return version;
1368 }
1369
1370 notmuch_bool_t
1371 notmuch_database_needs_upgrade (notmuch_database_t *notmuch)
1372 {
1373     return notmuch->mode == NOTMUCH_DATABASE_MODE_READ_WRITE &&
1374         ((NOTMUCH_FEATURES_CURRENT & ~notmuch->features) ||
1375          (notmuch_database_get_version (notmuch) < NOTMUCH_DATABASE_VERSION));
1376 }
1377
1378 static volatile sig_atomic_t do_progress_notify = 0;
1379
1380 static void
1381 handle_sigalrm (unused (int signal))
1382 {
1383     do_progress_notify = 1;
1384 }
1385
1386 /* Upgrade the current database.
1387  *
1388  * After opening a database in read-write mode, the client should
1389  * check if an upgrade is needed (notmuch_database_needs_upgrade) and
1390  * if so, upgrade with this function before making any modifications.
1391  *
1392  * The optional progress_notify callback can be used by the caller to
1393  * provide progress indication to the user. If non-NULL it will be
1394  * called periodically with 'count' as the number of messages upgraded
1395  * so far and 'total' the overall number of messages that will be
1396  * converted.
1397  */
1398 notmuch_status_t
1399 notmuch_database_upgrade (notmuch_database_t *notmuch,
1400                           void (*progress_notify) (void *closure,
1401                                                    double progress),
1402                           void *closure)
1403 {
1404     void *local = talloc_new (NULL);
1405     Xapian::TermIterator t, t_end;
1406     Xapian::WritableDatabase *db;
1407     struct sigaction action;
1408     struct itimerval timerval;
1409     notmuch_bool_t timer_is_active = FALSE;
1410     enum _notmuch_features target_features, new_features;
1411     notmuch_status_t status;
1412     notmuch_private_status_t private_status;
1413     notmuch_query_t *query = NULL;
1414     unsigned int count = 0, total = 0;
1415
1416     status = _notmuch_database_ensure_writable (notmuch);
1417     if (status)
1418         return status;
1419
1420     db = static_cast <Xapian::WritableDatabase *> (notmuch->xapian_db);
1421
1422     target_features = notmuch->features | NOTMUCH_FEATURES_CURRENT;
1423     new_features = NOTMUCH_FEATURES_CURRENT & ~notmuch->features;
1424
1425     if (! notmuch_database_needs_upgrade (notmuch))
1426         return NOTMUCH_STATUS_SUCCESS;
1427
1428     if (progress_notify) {
1429         /* Set up our handler for SIGALRM */
1430         memset (&action, 0, sizeof (struct sigaction));
1431         action.sa_handler = handle_sigalrm;
1432         sigemptyset (&action.sa_mask);
1433         action.sa_flags = SA_RESTART;
1434         sigaction (SIGALRM, &action, NULL);
1435
1436         /* Then start a timer to send SIGALRM once per second. */
1437         timerval.it_interval.tv_sec = 1;
1438         timerval.it_interval.tv_usec = 0;
1439         timerval.it_value.tv_sec = 1;
1440         timerval.it_value.tv_usec = 0;
1441         setitimer (ITIMER_REAL, &timerval, NULL);
1442
1443         timer_is_active = TRUE;
1444     }
1445
1446     /* Figure out how much total work we need to do. */
1447     if (new_features &
1448         (NOTMUCH_FEATURE_FILE_TERMS | NOTMUCH_FEATURE_BOOL_FOLDER |
1449          NOTMUCH_FEATURE_LAST_MOD)) {
1450         query = notmuch_query_create (notmuch, "");
1451         unsigned msg_count;
1452
1453         status = notmuch_query_count_messages_st (query, &msg_count);
1454         if (status)
1455             goto DONE;
1456
1457         total += msg_count;
1458         notmuch_query_destroy (query);
1459         query = NULL;
1460     }
1461     if (new_features & NOTMUCH_FEATURE_DIRECTORY_DOCS) {
1462         t_end = db->allterms_end ("XTIMESTAMP");
1463         for (t = db->allterms_begin ("XTIMESTAMP"); t != t_end; t++)
1464             ++total;
1465     }
1466     if (new_features & NOTMUCH_FEATURE_GHOSTS) {
1467         /* The ghost message upgrade converts all thread_id_*
1468          * metadata values into ghost message documents. */
1469         t_end = db->metadata_keys_end ("thread_id_");
1470         for (t = db->metadata_keys_begin ("thread_id_"); t != t_end; ++t)
1471             ++total;
1472     }
1473
1474     /* Perform the upgrade in a transaction. */
1475     db->begin_transaction (true);
1476
1477     /* Set the target features so we write out changes in the desired
1478      * format. */
1479     notmuch->features = target_features;
1480
1481     /* Perform per-message upgrades. */
1482     if (new_features &
1483         (NOTMUCH_FEATURE_FILE_TERMS | NOTMUCH_FEATURE_BOOL_FOLDER |
1484          NOTMUCH_FEATURE_LAST_MOD)) {
1485         notmuch_messages_t *messages;
1486         notmuch_message_t *message;
1487         char *filename;
1488
1489         query = notmuch_query_create (notmuch, "");
1490
1491         status = notmuch_query_search_messages_st (query, &messages);
1492         if (status)
1493             goto DONE;
1494         for (;
1495              notmuch_messages_valid (messages);
1496              notmuch_messages_move_to_next (messages))
1497         {
1498             if (do_progress_notify) {
1499                 progress_notify (closure, (double) count / total);
1500                 do_progress_notify = 0;
1501             }
1502
1503             message = notmuch_messages_get (messages);
1504
1505             /* Before version 1, each message document had its
1506              * filename in the data field. Copy that into the new
1507              * format by calling notmuch_message_add_filename.
1508              */
1509             if (new_features & NOTMUCH_FEATURE_FILE_TERMS) {
1510                 filename = _notmuch_message_talloc_copy_data (message);
1511                 if (filename && *filename != '\0') {
1512                     _notmuch_message_add_filename (message, filename);
1513                     _notmuch_message_clear_data (message);
1514                 }
1515                 talloc_free (filename);
1516             }
1517
1518             /* Prior to version 2, the "folder:" prefix was
1519              * probabilistic and stemmed. Change it to the current
1520              * boolean prefix. Add "path:" prefixes while at it.
1521              */
1522             if (new_features & NOTMUCH_FEATURE_BOOL_FOLDER)
1523                 _notmuch_message_upgrade_folder (message);
1524
1525             /* Prior to NOTMUCH_FEATURE_LAST_MOD, messages did not
1526              * track modification revisions.  Give all messages the
1527              * next available revision; since we just started tracking
1528              * revisions for this database, that will be 1.
1529              */
1530             if (new_features & NOTMUCH_FEATURE_LAST_MOD)
1531                 _notmuch_message_upgrade_last_mod (message);
1532
1533             _notmuch_message_sync (message);
1534
1535             notmuch_message_destroy (message);
1536
1537             count++;
1538         }
1539
1540         notmuch_query_destroy (query);
1541         query = NULL;
1542     }
1543
1544     /* Perform per-directory upgrades. */
1545
1546     /* Before version 1 we stored directory timestamps in
1547      * XTIMESTAMP documents instead of the current XDIRECTORY
1548      * documents. So copy those as well. */
1549     if (new_features & NOTMUCH_FEATURE_DIRECTORY_DOCS) {
1550         t_end = notmuch->xapian_db->allterms_end ("XTIMESTAMP");
1551
1552         for (t = notmuch->xapian_db->allterms_begin ("XTIMESTAMP");
1553              t != t_end;
1554              t++)
1555         {
1556             Xapian::PostingIterator p, p_end;
1557             std::string term = *t;
1558
1559             p_end = notmuch->xapian_db->postlist_end (term);
1560
1561             for (p = notmuch->xapian_db->postlist_begin (term);
1562                  p != p_end;
1563                  p++)
1564             {
1565                 Xapian::Document document;
1566                 time_t mtime;
1567                 notmuch_directory_t *directory;
1568
1569                 if (do_progress_notify) {
1570                     progress_notify (closure, (double) count / total);
1571                     do_progress_notify = 0;
1572                 }
1573
1574                 document = find_document_for_doc_id (notmuch, *p);
1575                 mtime = Xapian::sortable_unserialise (
1576                     document.get_value (NOTMUCH_VALUE_TIMESTAMP));
1577
1578                 directory = _notmuch_directory_create (notmuch, term.c_str() + 10,
1579                                                        NOTMUCH_FIND_CREATE, &status);
1580                 notmuch_directory_set_mtime (directory, mtime);
1581                 notmuch_directory_destroy (directory);
1582
1583                 db->delete_document (*p);
1584             }
1585
1586             ++count;
1587         }
1588     }
1589
1590     /* Perform metadata upgrades. */
1591
1592     /* Prior to NOTMUCH_FEATURE_GHOSTS, thread IDs for missing
1593      * messages were stored as database metadata. Change these to
1594      * ghost messages.
1595      */
1596     if (new_features & NOTMUCH_FEATURE_GHOSTS) {
1597         notmuch_message_t *message;
1598         std::string message_id, thread_id;
1599
1600         t_end = db->metadata_keys_end (NOTMUCH_METADATA_THREAD_ID_PREFIX);
1601         for (t = db->metadata_keys_begin (NOTMUCH_METADATA_THREAD_ID_PREFIX);
1602              t != t_end; ++t) {
1603             if (do_progress_notify) {
1604                 progress_notify (closure, (double) count / total);
1605                 do_progress_notify = 0;
1606             }
1607
1608             message_id = (*t).substr (
1609                 strlen (NOTMUCH_METADATA_THREAD_ID_PREFIX));
1610             thread_id = db->get_metadata (*t);
1611
1612             /* Create ghost message */
1613             message = _notmuch_message_create_for_message_id (
1614                 notmuch, message_id.c_str (), &private_status);
1615             if (private_status == NOTMUCH_PRIVATE_STATUS_SUCCESS) {
1616                 /* Document already exists; ignore the stored thread ID */
1617             } else if (private_status ==
1618                        NOTMUCH_PRIVATE_STATUS_NO_DOCUMENT_FOUND) {
1619                 private_status = _notmuch_message_initialize_ghost (
1620                     message, thread_id.c_str ());
1621                 if (! private_status)
1622                     _notmuch_message_sync (message);
1623             }
1624
1625             if (private_status) {
1626                 _notmuch_database_log (notmuch,
1627                          "Upgrade failed while creating ghost messages.\n");
1628                 status = COERCE_STATUS (private_status, "Unexpected status from _notmuch_message_initialize_ghost");
1629                 goto DONE;
1630             }
1631
1632             /* Clear saved metadata thread ID */
1633             db->set_metadata (*t, "");
1634
1635             ++count;
1636         }
1637     }
1638
1639     status = NOTMUCH_STATUS_SUCCESS;
1640     db->set_metadata ("features", _print_features (local, notmuch->features));
1641     db->set_metadata ("version", STRINGIFY (NOTMUCH_DATABASE_VERSION));
1642
1643  DONE:
1644     if (status == NOTMUCH_STATUS_SUCCESS)
1645         db->commit_transaction ();
1646     else
1647         db->cancel_transaction ();
1648
1649     if (timer_is_active) {
1650         /* Now stop the timer. */
1651         timerval.it_interval.tv_sec = 0;
1652         timerval.it_interval.tv_usec = 0;
1653         timerval.it_value.tv_sec = 0;
1654         timerval.it_value.tv_usec = 0;
1655         setitimer (ITIMER_REAL, &timerval, NULL);
1656
1657         /* And disable the signal handler. */
1658         action.sa_handler = SIG_IGN;
1659         sigaction (SIGALRM, &action, NULL);
1660     }
1661
1662     if (query)
1663         notmuch_query_destroy (query);
1664
1665     talloc_free (local);
1666     return status;
1667 }
1668
1669 notmuch_status_t
1670 notmuch_database_begin_atomic (notmuch_database_t *notmuch)
1671 {
1672     if (notmuch->mode == NOTMUCH_DATABASE_MODE_READ_ONLY ||
1673         notmuch->atomic_nesting > 0)
1674         goto DONE;
1675
1676     if (notmuch_database_needs_upgrade (notmuch))
1677         return NOTMUCH_STATUS_UPGRADE_REQUIRED;
1678
1679     try {
1680         (static_cast <Xapian::WritableDatabase *> (notmuch->xapian_db))->begin_transaction (false);
1681     } catch (const Xapian::Error &error) {
1682         _notmuch_database_log (notmuch, "A Xapian exception occurred beginning transaction: %s.\n",
1683                  error.get_msg().c_str());
1684         notmuch->exception_reported = TRUE;
1685         return NOTMUCH_STATUS_XAPIAN_EXCEPTION;
1686     }
1687
1688 DONE:
1689     notmuch->atomic_nesting++;
1690     return NOTMUCH_STATUS_SUCCESS;
1691 }
1692
1693 notmuch_status_t
1694 notmuch_database_end_atomic (notmuch_database_t *notmuch)
1695 {
1696     Xapian::WritableDatabase *db;
1697
1698     if (notmuch->atomic_nesting == 0)
1699         return NOTMUCH_STATUS_UNBALANCED_ATOMIC;
1700
1701     if (notmuch->mode == NOTMUCH_DATABASE_MODE_READ_ONLY ||
1702         notmuch->atomic_nesting > 1)
1703         goto DONE;
1704
1705     db = static_cast <Xapian::WritableDatabase *> (notmuch->xapian_db);
1706     try {
1707         db->commit_transaction ();
1708
1709         /* This is a hack for testing.  Xapian never flushes on a
1710          * non-flushed commit, even if the flush threshold is 1.
1711          * However, we rely on flushing to test atomicity. */
1712         const char *thresh = getenv ("XAPIAN_FLUSH_THRESHOLD");
1713         if (thresh && atoi (thresh) == 1)
1714             db->flush ();
1715     } catch (const Xapian::Error &error) {
1716         _notmuch_database_log (notmuch, "A Xapian exception occurred committing transaction: %s.\n",
1717                  error.get_msg().c_str());
1718         notmuch->exception_reported = TRUE;
1719         return NOTMUCH_STATUS_XAPIAN_EXCEPTION;
1720     }
1721
1722     if (notmuch->atomic_dirty) {
1723         ++notmuch->revision;
1724         notmuch->atomic_dirty = FALSE;
1725     }
1726
1727 DONE:
1728     notmuch->atomic_nesting--;
1729     return NOTMUCH_STATUS_SUCCESS;
1730 }
1731
1732 unsigned long
1733 notmuch_database_get_revision (notmuch_database_t *notmuch,
1734                                 const char **uuid)
1735 {
1736     if (uuid)
1737         *uuid = notmuch->uuid;
1738     return notmuch->revision;
1739 }
1740
1741 /* We allow the user to use arbitrarily long paths for directories. But
1742  * we have a term-length limit. So if we exceed that, we'll use the
1743  * SHA-1 of the path for the database term.
1744  *
1745  * Note: This function may return the original value of 'path'. If it
1746  * does not, then the caller is responsible to free() the returned
1747  * value.
1748  */
1749 const char *
1750 _notmuch_database_get_directory_db_path (const char *path)
1751 {
1752     int term_len = strlen (_find_prefix ("directory")) + strlen (path);
1753
1754     if (term_len > NOTMUCH_TERM_MAX)
1755         return _notmuch_sha1_of_string (path);
1756     else
1757         return path;
1758 }
1759
1760 /* Given a path, split it into two parts: the directory part is all
1761  * components except for the last, and the basename is that last
1762  * component. Getting the return-value for either part is optional
1763  * (the caller can pass NULL).
1764  *
1765  * The original 'path' can represent either a regular file or a
1766  * directory---the splitting will be carried out in the same way in
1767  * either case. Trailing slashes on 'path' will be ignored, and any
1768  * cases of multiple '/' characters appearing in series will be
1769  * treated as a single '/'.
1770  *
1771  * Allocation (if any) will have 'ctx' as the talloc owner. But
1772  * pointers will be returned within the original path string whenever
1773  * possible.
1774  *
1775  * Note: If 'path' is non-empty and contains no non-trailing slash,
1776  * (that is, consists of a filename with no parent directory), then
1777  * the directory returned will be an empty string. However, if 'path'
1778  * is an empty string, then both directory and basename will be
1779  * returned as NULL.
1780  */
1781 notmuch_status_t
1782 _notmuch_database_split_path (void *ctx,
1783                               const char *path,
1784                               const char **directory,
1785                               const char **basename)
1786 {
1787     const char *slash;
1788
1789     if (path == NULL || *path == '\0') {
1790         if (directory)
1791             *directory = NULL;
1792         if (basename)
1793             *basename = NULL;
1794         return NOTMUCH_STATUS_SUCCESS;
1795     }
1796
1797     /* Find the last slash (not counting a trailing slash), if any. */
1798
1799     slash = path + strlen (path) - 1;
1800
1801     /* First, skip trailing slashes. */
1802     while (slash != path && *slash == '/')
1803         --slash;
1804
1805     /* Then, find a slash. */
1806     while (slash != path && *slash != '/') {
1807         if (basename)
1808             *basename = slash;
1809
1810         --slash;
1811     }
1812
1813     /* Finally, skip multiple slashes. */
1814     while (slash != path && *(slash - 1) == '/')
1815         --slash;
1816
1817     if (slash == path) {
1818         if (directory)
1819             *directory = talloc_strdup (ctx, "");
1820         if (basename)
1821             *basename = path;
1822     } else {
1823         if (directory)
1824             *directory = talloc_strndup (ctx, path, slash - path);
1825     }
1826
1827     return NOTMUCH_STATUS_SUCCESS;
1828 }
1829
1830 /* Find the document ID of the specified directory.
1831  *
1832  * If (flags & NOTMUCH_FIND_CREATE), a new directory document will be
1833  * created if one does not exist for 'path'.  Otherwise, if the
1834  * directory document does not exist, this sets *directory_id to
1835  * ((unsigned int)-1) and returns NOTMUCH_STATUS_SUCCESS.
1836  */
1837 notmuch_status_t
1838 _notmuch_database_find_directory_id (notmuch_database_t *notmuch,
1839                                      const char *path,
1840                                      notmuch_find_flags_t flags,
1841                                      unsigned int *directory_id)
1842 {
1843     notmuch_directory_t *directory;
1844     notmuch_status_t status;
1845
1846     if (path == NULL) {
1847         *directory_id = 0;
1848         return NOTMUCH_STATUS_SUCCESS;
1849     }
1850
1851     directory = _notmuch_directory_create (notmuch, path, flags, &status);
1852     if (status || !directory) {
1853         *directory_id = -1;
1854         return status;
1855     }
1856
1857     *directory_id = _notmuch_directory_get_document_id (directory);
1858
1859     notmuch_directory_destroy (directory);
1860
1861     return NOTMUCH_STATUS_SUCCESS;
1862 }
1863
1864 const char *
1865 _notmuch_database_get_directory_path (void *ctx,
1866                                       notmuch_database_t *notmuch,
1867                                       unsigned int doc_id)
1868 {
1869     Xapian::Document document;
1870
1871     document = find_document_for_doc_id (notmuch, doc_id);
1872
1873     return talloc_strdup (ctx, document.get_data ().c_str ());
1874 }
1875
1876 /* Given a legal 'filename' for the database, (either relative to
1877  * database path or absolute with initial components identical to
1878  * database path), return a new string (with 'ctx' as the talloc
1879  * owner) suitable for use as a direntry term value.
1880  *
1881  * If (flags & NOTMUCH_FIND_CREATE), the necessary directory documents
1882  * will be created in the database as needed.  Otherwise, if the
1883  * necessary directory documents do not exist, this sets
1884  * *direntry to NULL and returns NOTMUCH_STATUS_SUCCESS.
1885  */
1886 notmuch_status_t
1887 _notmuch_database_filename_to_direntry (void *ctx,
1888                                         notmuch_database_t *notmuch,
1889                                         const char *filename,
1890                                         notmuch_find_flags_t flags,
1891                                         char **direntry)
1892 {
1893     const char *relative, *directory, *basename;
1894     Xapian::docid directory_id;
1895     notmuch_status_t status;
1896
1897     relative = _notmuch_database_relative_path (notmuch, filename);
1898
1899     status = _notmuch_database_split_path (ctx, relative,
1900                                            &directory, &basename);
1901     if (status)
1902         return status;
1903
1904     status = _notmuch_database_find_directory_id (notmuch, directory, flags,
1905                                                   &directory_id);
1906     if (status || directory_id == (unsigned int)-1) {
1907         *direntry = NULL;
1908         return status;
1909     }
1910
1911     *direntry = talloc_asprintf (ctx, "%u:%s", directory_id, basename);
1912
1913     return NOTMUCH_STATUS_SUCCESS;
1914 }
1915
1916 /* Given a legal 'path' for the database, return the relative path.
1917  *
1918  * The return value will be a pointer to the original path contents,
1919  * and will be either the original string (if 'path' was relative) or
1920  * a portion of the string (if path was absolute and begins with the
1921  * database path).
1922  */
1923 const char *
1924 _notmuch_database_relative_path (notmuch_database_t *notmuch,
1925                                  const char *path)
1926 {
1927     const char *db_path, *relative;
1928     unsigned int db_path_len;
1929
1930     db_path = notmuch_database_get_path (notmuch);
1931     db_path_len = strlen (db_path);
1932
1933     relative = path;
1934
1935     if (*relative == '/') {
1936         while (*relative == '/' && *(relative+1) == '/')
1937             relative++;
1938
1939         if (strncmp (relative, db_path, db_path_len) == 0)
1940         {
1941             relative += db_path_len;
1942             while (*relative == '/')
1943                 relative++;
1944         }
1945     }
1946
1947     return relative;
1948 }
1949
1950 notmuch_status_t
1951 notmuch_database_get_directory (notmuch_database_t *notmuch,
1952                                 const char *path,
1953                                 notmuch_directory_t **directory)
1954 {
1955     notmuch_status_t status;
1956
1957     if (directory == NULL)
1958         return NOTMUCH_STATUS_NULL_POINTER;
1959     *directory = NULL;
1960
1961     try {
1962         *directory = _notmuch_directory_create (notmuch, path,
1963                                                 NOTMUCH_FIND_LOOKUP, &status);
1964     } catch (const Xapian::Error &error) {
1965         _notmuch_database_log (notmuch, "A Xapian exception occurred getting directory: %s.\n",
1966                  error.get_msg().c_str());
1967         notmuch->exception_reported = TRUE;
1968         status = NOTMUCH_STATUS_XAPIAN_EXCEPTION;
1969     }
1970     return status;
1971 }
1972
1973 /* Allocate a document ID that satisfies the following criteria:
1974  *
1975  * 1. The ID does not exist for any document in the Xapian database
1976  *
1977  * 2. The ID was not previously returned from this function
1978  *
1979  * 3. The ID is the smallest integer satisfying (1) and (2)
1980  *
1981  * This function will trigger an internal error if these constraints
1982  * cannot all be satisfied, (that is, the pool of available document
1983  * IDs has been exhausted).
1984  */
1985 unsigned int
1986 _notmuch_database_generate_doc_id (notmuch_database_t *notmuch)
1987 {
1988     assert (notmuch->last_doc_id >= notmuch->xapian_db->get_lastdocid ());
1989
1990     notmuch->last_doc_id++;
1991
1992     if (notmuch->last_doc_id == 0)
1993         INTERNAL_ERROR ("Xapian document IDs are exhausted.\n");
1994
1995     return notmuch->last_doc_id;
1996 }
1997
1998 static const char *
1999 _notmuch_database_generate_thread_id (notmuch_database_t *notmuch)
2000 {
2001     /* 16 bytes (+ terminator) for hexadecimal representation of
2002      * a 64-bit integer. */
2003     static char thread_id[17];
2004     Xapian::WritableDatabase *db;
2005
2006     db = static_cast <Xapian::WritableDatabase *> (notmuch->xapian_db);
2007
2008     notmuch->last_thread_id++;
2009
2010     sprintf (thread_id, "%016" PRIx64, notmuch->last_thread_id);
2011
2012     db->set_metadata ("last_thread_id", thread_id);
2013
2014     return thread_id;
2015 }
2016
2017 static char *
2018 _get_metadata_thread_id_key (void *ctx, const char *message_id)
2019 {
2020     if (strlen (message_id) > NOTMUCH_MESSAGE_ID_MAX)
2021         message_id = _notmuch_message_id_compressed (ctx, message_id);
2022
2023     return talloc_asprintf (ctx, NOTMUCH_METADATA_THREAD_ID_PREFIX "%s",
2024                             message_id);
2025 }
2026
2027 static notmuch_status_t
2028 _resolve_message_id_to_thread_id_old (notmuch_database_t *notmuch,
2029                                       void *ctx,
2030                                       const char *message_id,
2031                                       const char **thread_id_ret);
2032
2033 /* Find the thread ID to which the message with 'message_id' belongs.
2034  *
2035  * Note: 'thread_id_ret' must not be NULL!
2036  * On success '*thread_id_ret' is set to a newly talloced string belonging to
2037  * 'ctx'.
2038  *
2039  * Note: If there is no message in the database with the given
2040  * 'message_id' then a new thread_id will be allocated for this
2041  * message ID and stored in the database metadata so that the
2042  * thread ID can be looked up if the message is added to the database
2043  * later.
2044  */
2045 static notmuch_status_t
2046 _resolve_message_id_to_thread_id (notmuch_database_t *notmuch,
2047                                   void *ctx,
2048                                   const char *message_id,
2049                                   const char **thread_id_ret)
2050 {
2051     notmuch_private_status_t status;
2052     notmuch_message_t *message;
2053
2054     if (! (notmuch->features & NOTMUCH_FEATURE_GHOSTS))
2055         return _resolve_message_id_to_thread_id_old (notmuch, ctx, message_id,
2056                                                      thread_id_ret);
2057
2058     /* Look for this message (regular or ghost) */
2059     message = _notmuch_message_create_for_message_id (
2060         notmuch, message_id, &status);
2061     if (status == NOTMUCH_PRIVATE_STATUS_SUCCESS) {
2062         /* Message exists */
2063         *thread_id_ret = talloc_steal (
2064             ctx, notmuch_message_get_thread_id (message));
2065     } else if (status == NOTMUCH_PRIVATE_STATUS_NO_DOCUMENT_FOUND) {
2066         /* Message did not exist.  Give it a fresh thread ID and
2067          * populate this message as a ghost message. */
2068         *thread_id_ret = talloc_strdup (
2069             ctx, _notmuch_database_generate_thread_id (notmuch));
2070         if (! *thread_id_ret) {
2071             status = NOTMUCH_PRIVATE_STATUS_OUT_OF_MEMORY;
2072         } else {
2073             status = _notmuch_message_initialize_ghost (message, *thread_id_ret);
2074             if (status == 0)
2075                 /* Commit the new ghost message */
2076                 _notmuch_message_sync (message);
2077         }
2078     } else {
2079         /* Create failed. Fall through. */
2080     }
2081
2082     notmuch_message_destroy (message);
2083
2084     return COERCE_STATUS (status, "Error creating ghost message");
2085 }
2086
2087 /* Pre-ghost messages _resolve_message_id_to_thread_id */
2088 static notmuch_status_t
2089 _resolve_message_id_to_thread_id_old (notmuch_database_t *notmuch,
2090                                       void *ctx,
2091                                       const char *message_id,
2092                                       const char **thread_id_ret)
2093 {
2094     notmuch_status_t status;
2095     notmuch_message_t *message;
2096     string thread_id_string;
2097     char *metadata_key;
2098     Xapian::WritableDatabase *db;
2099
2100     status = notmuch_database_find_message (notmuch, message_id, &message);
2101
2102     if (status)
2103         return status;
2104
2105     if (message) {
2106         *thread_id_ret = talloc_steal (ctx,
2107                                        notmuch_message_get_thread_id (message));
2108
2109         notmuch_message_destroy (message);
2110
2111         return NOTMUCH_STATUS_SUCCESS;
2112     }
2113
2114     /* Message has not been seen yet.
2115      *
2116      * We may have seen a reference to it already, in which case, we
2117      * can return the thread ID stored in the metadata. Otherwise, we
2118      * generate a new thread ID and store it there.
2119      */
2120     db = static_cast <Xapian::WritableDatabase *> (notmuch->xapian_db);
2121     metadata_key = _get_metadata_thread_id_key (ctx, message_id);
2122     thread_id_string = notmuch->xapian_db->get_metadata (metadata_key);
2123
2124     if (thread_id_string.empty()) {
2125         *thread_id_ret = talloc_strdup (ctx,
2126                                         _notmuch_database_generate_thread_id (notmuch));
2127         db->set_metadata (metadata_key, *thread_id_ret);
2128     } else {
2129         *thread_id_ret = talloc_strdup (ctx, thread_id_string.c_str());
2130     }
2131
2132     talloc_free (metadata_key);
2133
2134     return NOTMUCH_STATUS_SUCCESS;
2135 }
2136
2137 static notmuch_status_t
2138 _merge_threads (notmuch_database_t *notmuch,
2139                 const char *winner_thread_id,
2140                 const char *loser_thread_id)
2141 {
2142     Xapian::PostingIterator loser, loser_end;
2143     notmuch_message_t *message = NULL;
2144     notmuch_private_status_t private_status;
2145     notmuch_status_t ret = NOTMUCH_STATUS_SUCCESS;
2146
2147     find_doc_ids (notmuch, "thread", loser_thread_id, &loser, &loser_end);
2148
2149     for ( ; loser != loser_end; loser++) {
2150         message = _notmuch_message_create (notmuch, notmuch,
2151                                            *loser, &private_status);
2152         if (message == NULL) {
2153             ret = COERCE_STATUS (private_status,
2154                                  "Cannot find document for doc_id from query");
2155             goto DONE;
2156         }
2157
2158         _notmuch_message_remove_term (message, "thread", loser_thread_id);
2159         _notmuch_message_add_term (message, "thread", winner_thread_id);
2160         _notmuch_message_sync (message);
2161
2162         notmuch_message_destroy (message);
2163         message = NULL;
2164     }
2165
2166   DONE:
2167     if (message)
2168         notmuch_message_destroy (message);
2169
2170     return ret;
2171 }
2172
2173 static void
2174 _my_talloc_free_for_g_hash (void *ptr)
2175 {
2176     talloc_free (ptr);
2177 }
2178
2179 static notmuch_status_t
2180 _notmuch_database_link_message_to_parents (notmuch_database_t *notmuch,
2181                                            notmuch_message_t *message,
2182                                            notmuch_message_file_t *message_file,
2183                                            const char **thread_id)
2184 {
2185     GHashTable *parents = NULL;
2186     const char *refs, *in_reply_to, *in_reply_to_message_id;
2187     const char *last_ref_message_id, *this_message_id;
2188     GList *l, *keys = NULL;
2189     notmuch_status_t ret = NOTMUCH_STATUS_SUCCESS;
2190
2191     parents = g_hash_table_new_full (g_str_hash, g_str_equal,
2192                                      _my_talloc_free_for_g_hash, NULL);
2193     this_message_id = notmuch_message_get_message_id (message);
2194
2195     refs = _notmuch_message_file_get_header (message_file, "references");
2196     last_ref_message_id = parse_references (message,
2197                                             this_message_id,
2198                                             parents, refs);
2199
2200     in_reply_to = _notmuch_message_file_get_header (message_file, "in-reply-to");
2201     in_reply_to_message_id = parse_references (message,
2202                                                this_message_id,
2203                                                parents, in_reply_to);
2204
2205     /* For the parent of this message, use the last message ID of the
2206      * References header, if available.  If not, fall back to the
2207      * first message ID in the In-Reply-To header. */
2208     if (last_ref_message_id) {
2209         _notmuch_message_add_term (message, "replyto",
2210                                    last_ref_message_id);
2211     } else if (in_reply_to_message_id) {
2212         _notmuch_message_add_term (message, "replyto",
2213                              in_reply_to_message_id);
2214     }
2215
2216     keys = g_hash_table_get_keys (parents);
2217     for (l = keys; l; l = l->next) {
2218         char *parent_message_id;
2219         const char *parent_thread_id = NULL;
2220
2221         parent_message_id = (char *) l->data;
2222
2223         _notmuch_message_add_term (message, "reference",
2224                                    parent_message_id);
2225
2226         ret = _resolve_message_id_to_thread_id (notmuch,
2227                                                 message,
2228                                                 parent_message_id,
2229                                                 &parent_thread_id);
2230         if (ret)
2231             goto DONE;
2232
2233         if (*thread_id == NULL) {
2234             *thread_id = talloc_strdup (message, parent_thread_id);
2235             _notmuch_message_add_term (message, "thread", *thread_id);
2236         } else if (strcmp (*thread_id, parent_thread_id)) {
2237             ret = _merge_threads (notmuch, *thread_id, parent_thread_id);
2238             if (ret)
2239                 goto DONE;
2240         }
2241     }
2242
2243   DONE:
2244     if (keys)
2245         g_list_free (keys);
2246     if (parents)
2247         g_hash_table_unref (parents);
2248
2249     return ret;
2250 }
2251
2252 static notmuch_status_t
2253 _notmuch_database_link_message_to_children (notmuch_database_t *notmuch,
2254                                             notmuch_message_t *message,
2255                                             const char **thread_id)
2256 {
2257     const char *message_id = notmuch_message_get_message_id (message);
2258     Xapian::PostingIterator child, children_end;
2259     notmuch_message_t *child_message = NULL;
2260     const char *child_thread_id;
2261     notmuch_status_t ret = NOTMUCH_STATUS_SUCCESS;
2262     notmuch_private_status_t private_status;
2263
2264     find_doc_ids (notmuch, "reference", message_id, &child, &children_end);
2265
2266     for ( ; child != children_end; child++) {
2267
2268         child_message = _notmuch_message_create (message, notmuch,
2269                                                  *child, &private_status);
2270         if (child_message == NULL) {
2271             ret = COERCE_STATUS (private_status,
2272                                  "Cannot find document for doc_id from query");
2273             goto DONE;
2274         }
2275
2276         child_thread_id = notmuch_message_get_thread_id (child_message);
2277         if (*thread_id == NULL) {
2278             *thread_id = talloc_strdup (message, child_thread_id);
2279             _notmuch_message_add_term (message, "thread", *thread_id);
2280         } else if (strcmp (*thread_id, child_thread_id)) {
2281             _notmuch_message_remove_term (child_message, "reference",
2282                                           message_id);
2283             _notmuch_message_sync (child_message);
2284             ret = _merge_threads (notmuch, *thread_id, child_thread_id);
2285             if (ret)
2286                 goto DONE;
2287         }
2288
2289         notmuch_message_destroy (child_message);
2290         child_message = NULL;
2291     }
2292
2293   DONE:
2294     if (child_message)
2295         notmuch_message_destroy (child_message);
2296
2297     return ret;
2298 }
2299
2300 /* Fetch and clear the stored thread_id for message, or NULL if none. */
2301 static char *
2302 _consume_metadata_thread_id (void *ctx, notmuch_database_t *notmuch,
2303                              notmuch_message_t *message)
2304 {
2305     const char *message_id;
2306     string stored_id;
2307     char *metadata_key;
2308
2309     message_id = notmuch_message_get_message_id (message);
2310     metadata_key = _get_metadata_thread_id_key (ctx, message_id);
2311
2312     /* Check if we have already seen related messages to this one.
2313      * If we have then use the thread_id that we stored at that time.
2314      */
2315     stored_id = notmuch->xapian_db->get_metadata (metadata_key);
2316     if (stored_id.empty ()) {
2317         return NULL;
2318     } else {
2319         Xapian::WritableDatabase *db;
2320
2321         db = static_cast <Xapian::WritableDatabase *> (notmuch->xapian_db);
2322
2323         /* Clear the metadata for this message ID. We don't need it
2324          * anymore. */
2325         db->set_metadata (metadata_key, "");
2326
2327         return talloc_strdup (ctx, stored_id.c_str ());
2328     }
2329 }
2330
2331 /* Given a blank or ghost 'message' and its corresponding
2332  * 'message_file' link it to existing threads in the database.
2333  *
2334  * First, if is_ghost, this retrieves the thread ID already stored in
2335  * the message (which will be the case if a message was previously
2336  * added that referenced this one).  If the message is blank
2337  * (!is_ghost), it doesn't have a thread ID yet (we'll generate one
2338  * later in this function).  If the database does not support ghost
2339  * messages, this checks for a thread ID stored in database metadata
2340  * for this message ID.
2341  *
2342  * Second, we look at 'message_file' and its link-relevant headers
2343  * (References and In-Reply-To) for message IDs.
2344  *
2345  * Finally, we look in the database for existing message that
2346  * reference 'message'.
2347  *
2348  * In all cases, we assign to the current message the first thread ID
2349  * found. We will also merge any existing, distinct threads where this
2350  * message belongs to both, (which is not uncommon when messages are
2351  * processed out of order).
2352  *
2353  * Finally, if no thread ID has been found through referenced messages, we
2354  * call _notmuch_message_generate_thread_id to generate a new thread
2355  * ID. This should only happen for new, top-level messages, (no
2356  * References or In-Reply-To header in this message, and no previously
2357  * added message refers to this message).
2358  */
2359 static notmuch_status_t
2360 _notmuch_database_link_message (notmuch_database_t *notmuch,
2361                                 notmuch_message_t *message,
2362                                 notmuch_message_file_t *message_file,
2363                                 notmuch_bool_t is_ghost)
2364 {
2365     void *local = talloc_new (NULL);
2366     notmuch_status_t status;
2367     const char *thread_id = NULL;
2368
2369     /* Check if the message already had a thread ID */
2370     if (notmuch->features & NOTMUCH_FEATURE_GHOSTS) {
2371         if (is_ghost)
2372             thread_id = notmuch_message_get_thread_id (message);
2373     } else {
2374         thread_id = _consume_metadata_thread_id (local, notmuch, message);
2375         if (thread_id)
2376             _notmuch_message_add_term (message, "thread", thread_id);
2377     }
2378
2379     status = _notmuch_database_link_message_to_parents (notmuch, message,
2380                                                         message_file,
2381                                                         &thread_id);
2382     if (status)
2383         goto DONE;
2384
2385     if (! (notmuch->features & NOTMUCH_FEATURE_GHOSTS)) {
2386         /* In general, it shouldn't be necessary to link children,
2387          * since the earlier indexing of those children will have
2388          * stored a thread ID for the missing parent.  However, prior
2389          * to ghost messages, these stored thread IDs were NOT
2390          * rewritten during thread merging (and there was no
2391          * performant way to do so), so if indexed children were
2392          * pulled into a different thread ID by a merge, it was
2393          * necessary to pull them *back* into the stored thread ID of
2394          * the parent.  With ghost messages, we just rewrite the
2395          * stored thread IDs during merging, so this workaround isn't
2396          * necessary. */
2397         status = _notmuch_database_link_message_to_children (notmuch, message,
2398                                                              &thread_id);
2399         if (status)
2400             goto DONE;
2401     }
2402
2403     /* If not part of any existing thread, generate a new thread ID. */
2404     if (thread_id == NULL) {
2405         thread_id = _notmuch_database_generate_thread_id (notmuch);
2406
2407         _notmuch_message_add_term (message, "thread", thread_id);
2408     }
2409
2410  DONE:
2411     talloc_free (local);
2412
2413     return status;
2414 }
2415
2416 notmuch_status_t
2417 notmuch_database_add_message (notmuch_database_t *notmuch,
2418                               const char *filename,
2419                               notmuch_message_t **message_ret)
2420 {
2421     notmuch_message_file_t *message_file;
2422     notmuch_message_t *message = NULL;
2423     notmuch_status_t ret = NOTMUCH_STATUS_SUCCESS, ret2;
2424     notmuch_private_status_t private_status;
2425     notmuch_bool_t is_ghost = false;
2426
2427     const char *date, *header;
2428     const char *from, *to, *subject;
2429     char *message_id = NULL;
2430
2431     if (message_ret)
2432         *message_ret = NULL;
2433
2434     ret = _notmuch_database_ensure_writable (notmuch);
2435     if (ret)
2436         return ret;
2437
2438     message_file = _notmuch_message_file_open (notmuch, filename);
2439     if (message_file == NULL)
2440         return NOTMUCH_STATUS_FILE_ERROR;
2441
2442     /* Adding a message may change many documents.  Do this all
2443      * atomically. */
2444     ret = notmuch_database_begin_atomic (notmuch);
2445     if (ret)
2446         goto DONE;
2447
2448     /* Parse message up front to get better error status. */
2449     ret = _notmuch_message_file_parse (message_file);
2450     if (ret)
2451         goto DONE;
2452
2453     try {
2454         /* Before we do any real work, (especially before doing a
2455          * potential SHA-1 computation on the entire file's contents),
2456          * let's make sure that what we're looking at looks like an
2457          * actual email message.
2458          */
2459         from = _notmuch_message_file_get_header (message_file, "from");
2460         subject = _notmuch_message_file_get_header (message_file, "subject");
2461         to = _notmuch_message_file_get_header (message_file, "to");
2462
2463         if ((from == NULL || *from == '\0') &&
2464             (subject == NULL || *subject == '\0') &&
2465             (to == NULL || *to == '\0'))
2466         {
2467             ret = NOTMUCH_STATUS_FILE_NOT_EMAIL;
2468             goto DONE;
2469         }
2470
2471         /* Now that we're sure it's mail, the first order of business
2472          * is to find a message ID (or else create one ourselves). */
2473
2474         header = _notmuch_message_file_get_header (message_file, "message-id");
2475         if (header && *header != '\0') {
2476             message_id = _parse_message_id (message_file, header, NULL);
2477
2478             /* So the header value isn't RFC-compliant, but it's
2479              * better than no message-id at all. */
2480             if (message_id == NULL)
2481                 message_id = talloc_strdup (message_file, header);
2482         }
2483
2484         if (message_id == NULL ) {
2485             /* No message-id at all, let's generate one by taking a
2486              * hash over the file's contents. */
2487             char *sha1 = _notmuch_sha1_of_file (filename);
2488
2489             /* If that failed too, something is really wrong. Give up. */
2490             if (sha1 == NULL) {
2491                 ret = NOTMUCH_STATUS_FILE_ERROR;
2492                 goto DONE;
2493             }
2494
2495             message_id = talloc_asprintf (message_file,
2496                                           "notmuch-sha1-%s", sha1);
2497             free (sha1);
2498         }
2499
2500         /* Now that we have a message ID, we get a message object,
2501          * (which may or may not reference an existing document in the
2502          * database). */
2503
2504         message = _notmuch_message_create_for_message_id (notmuch,
2505                                                           message_id,
2506                                                           &private_status);
2507
2508         talloc_free (message_id);
2509
2510         if (message == NULL) {
2511             ret = COERCE_STATUS (private_status,
2512                                  "Unexpected status value from _notmuch_message_create_for_message_id");
2513             goto DONE;
2514         }
2515
2516         _notmuch_message_add_filename (message, filename);
2517
2518         /* Is this a newly created message object or a ghost
2519          * message?  We have to be slightly careful: if this is a
2520          * blank message, it's not safe to call
2521          * notmuch_message_get_flag yet. */
2522         if (private_status == NOTMUCH_PRIVATE_STATUS_NO_DOCUMENT_FOUND ||
2523             (is_ghost = notmuch_message_get_flag (
2524                 message, NOTMUCH_MESSAGE_FLAG_GHOST))) {
2525             _notmuch_message_add_term (message, "type", "mail");
2526             if (is_ghost)
2527                 /* Convert ghost message to a regular message */
2528                 _notmuch_message_remove_term (message, "type", "ghost");
2529
2530             ret = _notmuch_database_link_message (notmuch, message,
2531                                                   message_file, is_ghost);
2532             if (ret)
2533                 goto DONE;
2534
2535             date = _notmuch_message_file_get_header (message_file, "date");
2536             _notmuch_message_set_header_values (message, date, from, subject);
2537
2538             ret = _notmuch_message_index_file (message, message_file);
2539             if (ret)
2540                 goto DONE;
2541         } else {
2542             ret = NOTMUCH_STATUS_DUPLICATE_MESSAGE_ID;
2543         }
2544
2545         _notmuch_message_sync (message);
2546     } catch (const Xapian::Error &error) {
2547         _notmuch_database_log (notmuch, "A Xapian exception occurred adding message: %s.\n",
2548                  error.get_msg().c_str());
2549         notmuch->exception_reported = TRUE;
2550         ret = NOTMUCH_STATUS_XAPIAN_EXCEPTION;
2551         goto DONE;
2552     }
2553
2554   DONE:
2555     if (message) {
2556         if ((ret == NOTMUCH_STATUS_SUCCESS ||
2557              ret == NOTMUCH_STATUS_DUPLICATE_MESSAGE_ID) && message_ret)
2558             *message_ret = message;
2559         else
2560             notmuch_message_destroy (message);
2561     }
2562
2563     if (message_file)
2564         _notmuch_message_file_close (message_file);
2565
2566     ret2 = notmuch_database_end_atomic (notmuch);
2567     if ((ret == NOTMUCH_STATUS_SUCCESS ||
2568          ret == NOTMUCH_STATUS_DUPLICATE_MESSAGE_ID) &&
2569         ret2 != NOTMUCH_STATUS_SUCCESS)
2570         ret = ret2;
2571
2572     return ret;
2573 }
2574
2575 notmuch_status_t
2576 notmuch_database_remove_message (notmuch_database_t *notmuch,
2577                                  const char *filename)
2578 {
2579     notmuch_status_t status;
2580     notmuch_message_t *message;
2581
2582     status = notmuch_database_find_message_by_filename (notmuch, filename,
2583                                                         &message);
2584
2585     if (status == NOTMUCH_STATUS_SUCCESS && message) {
2586             status = _notmuch_message_remove_filename (message, filename);
2587             if (status == NOTMUCH_STATUS_SUCCESS)
2588                 _notmuch_message_delete (message);
2589             else if (status == NOTMUCH_STATUS_DUPLICATE_MESSAGE_ID)
2590                 _notmuch_message_sync (message);
2591
2592             notmuch_message_destroy (message);
2593     }
2594
2595     return status;
2596 }
2597
2598 notmuch_status_t
2599 notmuch_database_find_message_by_filename (notmuch_database_t *notmuch,
2600                                            const char *filename,
2601                                            notmuch_message_t **message_ret)
2602 {
2603     void *local;
2604     const char *prefix = _find_prefix ("file-direntry");
2605     char *direntry, *term;
2606     Xapian::PostingIterator i, end;
2607     notmuch_status_t status;
2608
2609     if (message_ret == NULL)
2610         return NOTMUCH_STATUS_NULL_POINTER;
2611
2612     if (! (notmuch->features & NOTMUCH_FEATURE_FILE_TERMS))
2613         return NOTMUCH_STATUS_UPGRADE_REQUIRED;
2614
2615     /* return NULL on any failure */
2616     *message_ret = NULL;
2617
2618     local = talloc_new (notmuch);
2619
2620     try {
2621         status = _notmuch_database_filename_to_direntry (
2622             local, notmuch, filename, NOTMUCH_FIND_LOOKUP, &direntry);
2623         if (status || !direntry)
2624             goto DONE;
2625
2626         term = talloc_asprintf (local, "%s%s", prefix, direntry);
2627
2628         find_doc_ids_for_term (notmuch, term, &i, &end);
2629
2630         if (i != end) {
2631             notmuch_private_status_t private_status;
2632
2633             *message_ret = _notmuch_message_create (notmuch, notmuch, *i,
2634                                                     &private_status);
2635             if (*message_ret == NULL)
2636                 status = NOTMUCH_STATUS_OUT_OF_MEMORY;
2637         }
2638     } catch (const Xapian::Error &error) {
2639         _notmuch_database_log (notmuch, "Error: A Xapian exception occurred finding message by filename: %s\n",
2640                  error.get_msg().c_str());
2641         notmuch->exception_reported = TRUE;
2642         status = NOTMUCH_STATUS_XAPIAN_EXCEPTION;
2643     }
2644
2645   DONE:
2646     talloc_free (local);
2647
2648     if (status && *message_ret) {
2649         notmuch_message_destroy (*message_ret);
2650         *message_ret = NULL;
2651     }
2652     return status;
2653 }
2654
2655 notmuch_string_list_t *
2656 _notmuch_database_get_terms_with_prefix (void *ctx, Xapian::TermIterator &i,
2657                                          Xapian::TermIterator &end,
2658                                          const char *prefix)
2659 {
2660     int prefix_len = strlen (prefix);
2661     notmuch_string_list_t *list;
2662
2663     list = _notmuch_string_list_create (ctx);
2664     if (unlikely (list == NULL))
2665         return NULL;
2666
2667     for (i.skip_to (prefix); i != end; i++) {
2668         /* Terminate loop at first term without desired prefix. */
2669         if (strncmp ((*i).c_str (), prefix, prefix_len))
2670             break;
2671
2672         _notmuch_string_list_append (list, (*i).c_str () + prefix_len);
2673     }
2674
2675     return list;
2676 }
2677
2678 notmuch_tags_t *
2679 notmuch_database_get_all_tags (notmuch_database_t *db)
2680 {
2681     Xapian::TermIterator i, end;
2682     notmuch_string_list_t *tags;
2683
2684     try {
2685         i = db->xapian_db->allterms_begin();
2686         end = db->xapian_db->allterms_end();
2687         tags = _notmuch_database_get_terms_with_prefix (db, i, end,
2688                                                         _find_prefix ("tag"));
2689         _notmuch_string_list_sort (tags);
2690         return _notmuch_tags_create (db, tags);
2691     } catch (const Xapian::Error &error) {
2692         _notmuch_database_log (db, "A Xapian exception occurred getting tags: %s.\n",
2693                  error.get_msg().c_str());
2694         db->exception_reported = TRUE;
2695         return NULL;
2696     }
2697 }
2698
2699 const char *
2700 notmuch_database_status_string (const notmuch_database_t *notmuch)
2701 {
2702     return notmuch->status_string;
2703 }