Merge tag 'debian/0.28-2' into debian/stretch-backports

notmuch release 0.28-2 for unstable (sid) [dgit]
[dgit distro=debian]

6 files changed, 296 insertions, 31 deletions

diff --git a/lib/add-message.cc b/lib/add-message.cc
index f5fac8be..da37032c 100644
--- a/lib/add-message.cc
+++ b/lib/add-message.cc
@@ -227,7 +227,7 @@ _notmuch_database_link_message_to_parents (notmuch_database_t *notmuch,
 					   const char **thread_id)
 {
     GHashTable *parents = NULL;
-    const char *refs, *in_reply_to, *in_reply_to_message_id;
+    const char *refs, *in_reply_to, *in_reply_to_message_id, *strict_message_id = NULL;
     const char *last_ref_message_id, *this_message_id;
     GList *l, *keys = NULL;
     notmuch_status_t ret = NOTMUCH_STATUS_SUCCESS;
@@ -242,14 +242,24 @@ _notmuch_database_link_message_to_parents (notmuch_database_t *notmuch,
 					    parents, refs);
 
     in_reply_to = _notmuch_message_file_get_header (message_file, "in-reply-to");
+    if (in_reply_to)
+	strict_message_id = _notmuch_message_id_parse_strict (message,
+							      in_reply_to);
+
     in_reply_to_message_id = parse_references (message,
 					       this_message_id,
 					       parents, in_reply_to);
 
-    /* For the parent of this message, use the last message ID of the
-     * References header, if available.  If not, fall back to the
-     * first message ID in the In-Reply-To header. */
-    if (last_ref_message_id) {
+    /* For the parent of this message, use
+     * 1) the In-Reply-To header, if it looks sane, otherwise
+     * 2) the last message ID of the References header, if available.
+     * 3) Otherwise, fall back to the first message ID in
+     * the In-Reply-To header.
+     */
+
+    if (strict_message_id) {
+	_notmuch_message_add_term (message, "replyto", strict_message_id);
+    } else if (last_ref_message_id) {
 	_notmuch_message_add_term (message, "replyto",
 				   last_ref_message_id);
     } else if (in_reply_to_message_id) {
diff --git a/lib/message-id.c b/lib/message-id.c
index d7541d50..e71ce9f4 100644
--- a/lib/message-id.c
+++ b/lib/message-id.c
@@ -1,4 +1,5 @@
 #include "notmuch-private.h"
+#include "string-util.h"
 
 /* Advance 'str' past any whitespace or RFC 822 comments. A comment is
  * a (potentially nested) parenthesized sequence with '\' used to
@@ -94,3 +95,32 @@ _notmuch_message_id_parse (void *ctx, const char *message_id, const char **next)
 
     return result;
 }
+
+char *
+_notmuch_message_id_parse_strict (void *ctx, const char *message_id)
+{
+    const char *s, *end;
+
+    if (message_id == NULL || *message_id == '\0')
+	return NULL;
+
+    s = skip_space (message_id);
+    if (*s == '<')
+	s++;
+    else
+	return NULL;
+
+    for (end = s; *end && *end != '>'; end++)
+	if (isspace (*end))
+	    return NULL;
+
+    if (*end != '>')
+	return NULL;
+    else {
+	const char *last = skip_space (end + 1);
+	if (*last != '\0')
+	    return NULL;
+    }
+
+    return talloc_strndup (ctx, s, end - s);
+}
diff --git a/lib/message.cc b/lib/message.cc
index 153e4bed..6f2f6345 100644
--- a/lib/message.cc
+++ b/lib/message.cc
@@ -32,6 +32,7 @@ struct _notmuch_message {
     int frozen;
     char *message_id;
     char *thread_id;
+    size_t thread_depth;
     char *in_reply_to;
     notmuch_string_list_t *tag_list;
     notmuch_string_list_t *filename_term_list;
@@ -41,6 +42,7 @@ struct _notmuch_message {
     notmuch_message_file_t *message_file;
     notmuch_string_list_t *property_term_list;
     notmuch_string_map_t *property_map;
+    notmuch_string_list_t *reference_list;
     notmuch_message_list_t *replies;
     unsigned long flags;
     /* For flags that are initialized on-demand, lazy_flags indicates
@@ -117,6 +119,9 @@ _notmuch_message_create_for_document (const void *talloc_owner,
     /* the message is initially not synchronized with Xapian */
     message->last_view = 0;
 
+    /* Calculated after the thread structure is computed */
+    message->thread_depth = 0;
+
     /* Each of these will be lazily created as needed. */
     message->message_id = NULL;
     message->thread_id = NULL;
@@ -129,6 +134,7 @@ _notmuch_message_create_for_document (const void *talloc_owner,
     message->author = NULL;
     message->property_term_list = NULL;
     message->property_map = NULL;
+    message->reference_list = NULL;
 
     message->replies = _notmuch_message_list_create (message);
     if (unlikely (message->replies == NULL)) {
@@ -349,6 +355,7 @@ _notmuch_message_ensure_metadata (notmuch_message_t *message, void *field)
 	*type_prefix = _find_prefix ("type"),
 	*filename_prefix = _find_prefix ("file-direntry"),
 	*property_prefix = _find_prefix ("property"),
+	*reference_prefix = _find_prefix ("reference"),
 	*replyto_prefix = _find_prefix ("replyto");
 
     /* We do this all in a single pass because Xapian decompresses the
@@ -413,6 +420,14 @@ _notmuch_message_ensure_metadata (notmuch_message_t *message, void *field)
 		    _notmuch_database_get_terms_with_prefix (message, i, end,
 							 property_prefix);
 
+	    /* get references */
+	    assert (strcmp (property_prefix, reference_prefix) < 0);
+	    if (!message->reference_list) {
+		message->reference_list =
+		    _notmuch_database_get_terms_with_prefix (message, i, end,
+							     reference_prefix);
+	    }
+
 	    /* Get reply to */
 	    assert (strcmp (property_prefix, replyto_prefix) < 0);
 	    if (!message->in_reply_to)
@@ -588,6 +603,84 @@ _notmuch_message_add_reply (notmuch_message_t *message,
     _notmuch_message_list_add_message (message->replies, reply);
 }
 
+size_t
+_notmuch_message_get_thread_depth (notmuch_message_t *message) {
+    return message->thread_depth;
+}
+
+void
+_notmuch_message_label_depths (notmuch_message_t *message,
+			       size_t depth)
+{
+    message->thread_depth = depth;
+
+    for (notmuch_messages_t *messages = _notmuch_messages_create (message->replies);
+	 notmuch_messages_valid (messages);
+	 notmuch_messages_move_to_next (messages)) {
+	notmuch_message_t *child = notmuch_messages_get (messages);
+	_notmuch_message_label_depths (child, depth+1);
+    }
+}
+
+const notmuch_string_list_t *
+_notmuch_message_get_references (notmuch_message_t *message)
+{
+    _notmuch_message_ensure_metadata (message, message->reference_list);
+    return message->reference_list;
+}
+
+static int
+_cmpmsg (const void *pa, const void *pb)
+{
+    notmuch_message_t **a = (notmuch_message_t **) pa;
+    notmuch_message_t **b = (notmuch_message_t **) pb;
+    time_t time_a = notmuch_message_get_date (*a);
+    time_t time_b = notmuch_message_get_date (*b);
+
+    if (time_a == time_b)
+	return 0;
+    else if (time_a < time_b)
+	return -1;
+    else
+	return 1;
+}
+
+notmuch_message_list_t *
+_notmuch_message_sort_subtrees (void *ctx, notmuch_message_list_t *list)
+{
+
+    size_t count = 0;
+    size_t capacity = 16;
+
+    if (! list)
+	return list;
+
+    void *local = talloc_new (NULL);
+    notmuch_message_list_t *new_list = _notmuch_message_list_create (ctx);
+    notmuch_message_t **message_array = talloc_zero_array (local, notmuch_message_t *, capacity);
+
+    for (notmuch_messages_t *messages = _notmuch_messages_create (list);
+	 notmuch_messages_valid (messages);
+	 notmuch_messages_move_to_next (messages)) {
+	notmuch_message_t *root = notmuch_messages_get (messages);
+	if (count >= capacity) {
+	    capacity *= 2;
+	    message_array = talloc_realloc (local, message_array, notmuch_message_t *, capacity);
+	}
+	message_array[count++] = root;
+	root->replies = _notmuch_message_sort_subtrees (root, root->replies);
+    }
+
+    qsort (message_array, count, sizeof (notmuch_message_t *), _cmpmsg);
+    for (size_t i = 0; i < count; i++) {
+	_notmuch_message_list_add_message (new_list, message_array[i]);
+    }
+
+    talloc_free (local);
+    talloc_free (list);
+    return new_list;
+}
+
 notmuch_messages_t *
 notmuch_message_get_replies (notmuch_message_t *message)
 {
diff --git a/lib/messages.c b/lib/messages.c
index a88f974f..04fa19f8 100644
--- a/lib/messages.c
+++ b/lib/messages.c
@@ -56,6 +56,15 @@ _notmuch_message_list_add_message (notmuch_message_list_t *list,
     list->tail = &node->next;
 }
 
+bool
+_notmuch_message_list_empty (notmuch_message_list_t *list)
+{
+    if (list == NULL)
+	return TRUE;
+
+    return (list->head == NULL);
+}
+
 notmuch_messages_t *
 _notmuch_messages_create (notmuch_message_list_t *list)
 {
@@ -101,6 +110,18 @@ notmuch_messages_valid (notmuch_messages_t *messages)
     return (messages->iterator != NULL);
 }
 
+bool
+_notmuch_messages_has_next (notmuch_messages_t *messages)
+{
+    if (! notmuch_messages_valid (messages))
+	return false;
+
+    if (! messages->is_of_list_type)
+	INTERNAL_ERROR("_notmuch_messages_has_next not implimented for msets");
+
+    return (messages->iterator->next != NULL);
+}
+
 notmuch_message_t *
 notmuch_messages_get (notmuch_messages_t *messages)
 {
diff --git a/lib/notmuch-private.h b/lib/notmuch-private.h
index 3764a6a9..df32d39c 100644
--- a/lib/notmuch-private.h
+++ b/lib/notmuch-private.h
@@ -56,6 +56,7 @@ NOTMUCH_BEGIN_DECLS
 
 #ifdef DEBUG
 # define DEBUG_DATABASE_SANITY 1
+# define DEBUG_THREADING 1
 # define DEBUG_QUERY 1
 #endif
 
@@ -476,6 +477,9 @@ struct _notmuch_messages {
 notmuch_message_list_t *
 _notmuch_message_list_create (const void *ctx);
 
+bool
+_notmuch_message_list_empty (notmuch_message_list_t *list);
+
 void
 _notmuch_message_list_add_message (notmuch_message_list_t *list,
 				   notmuch_message_t *message);
@@ -483,6 +487,9 @@ _notmuch_message_list_add_message (notmuch_message_list_t *list,
 notmuch_messages_t *
 _notmuch_messages_create (notmuch_message_list_t *list);
 
+bool
+_notmuch_messages_has_next (notmuch_messages_t *messages);
+
 /* query.cc */
 
 bool
@@ -526,6 +533,20 @@ _notmuch_query_count_documents (notmuch_query_t *query,
 char *
 _notmuch_message_id_parse (void *ctx, const char *message_id, const char **next);
 
+/* Parse a message-id, discarding leading and trailing whitespace, and
+ * '<' and '>' delimiters.
+ *
+ * Apply a probably-stricter-than RFC definition of what is allowed in
+ * a message-id. In particular, forbid whitespace.
+ *
+ * Returns a newly talloc'ed string belonging to 'ctx'.
+ *
+ * Returns NULL if there is any error parsing the message-id.
+ */
+
+char *
+_notmuch_message_id_parse_strict (void *ctx, const char *message_id);
+
 
 /* message.cc */
 
@@ -539,6 +560,15 @@ _notmuch_message_remove_unprefixed_terms (notmuch_message_t *message);
 const char *
 _notmuch_message_get_thread_id_only(notmuch_message_t *message);
 
+size_t _notmuch_message_get_thread_depth (notmuch_message_t *message);
+
+void
+_notmuch_message_label_depths (notmuch_message_t *message,
+			       size_t depth);
+
+notmuch_message_list_t *
+_notmuch_message_sort_subtrees (void *ctx, notmuch_message_list_t *list);
+
 /* sha1.c */
 
 char *
@@ -580,6 +610,9 @@ _notmuch_string_list_append (notmuch_string_list_t *list,
 void
 _notmuch_string_list_sort (notmuch_string_list_t *list);
 
+const notmuch_string_list_t *
+_notmuch_message_get_references(notmuch_message_t *message);
+
 /* string-map.c */
 typedef struct _notmuch_string_map  notmuch_string_map_t;
 typedef struct _notmuch_string_map_iterator notmuch_string_map_iterator_t;
diff --git a/lib/thread.cc b/lib/thread.cc
index e961c76b..47c90664 100644
--- a/lib/thread.cc
+++ b/lib/thread.cc
@@ -24,6 +24,12 @@
 #include <gmime/gmime.h>
 #include <glib.h> /* GHashTable */
 
+#ifdef DEBUG_THREADING
+#define THREAD_DEBUG(format, ...) fprintf(stderr, format " (%s).\n", ##__VA_ARGS__, __location__)
+#else
+#define THREAD_DEBUG(format, ...) do {} while (0) /* ignored */
+#endif
+
 #define EMPTY_STRING(s) ((s)[0] == '\0')
 
 struct _notmuch_thread {
@@ -387,27 +393,84 @@ _thread_add_matched_message (notmuch_thread_t *thread,
     _thread_add_matched_author (thread, _notmuch_message_get_author (hashed_message));
 }
 
+static bool
+_parent_via_in_reply_to (notmuch_thread_t *thread, notmuch_message_t *message) {
+    notmuch_message_t *parent;
+    const char *in_reply_to;
+
+    in_reply_to = _notmuch_message_get_in_reply_to (message);
+    THREAD_DEBUG("checking message = %s in_reply_to=%s\n",
+		 notmuch_message_get_message_id (message), in_reply_to);
+
+    if (in_reply_to && (! EMPTY_STRING(in_reply_to)) &&
+	g_hash_table_lookup_extended (thread->message_hash,
+				      in_reply_to, NULL,
+				      (void **) &parent)) {
+	_notmuch_message_add_reply (parent, message);
+	return true;
+    } else {
+	return false;
+    }
+}
+
+static void
+_parent_or_toplevel (notmuch_thread_t *thread, notmuch_message_t *message)
+{
+    size_t max_depth = 0;
+    notmuch_message_t *new_parent;
+    notmuch_message_t *parent = NULL;
+    const notmuch_string_list_t *references =
+	_notmuch_message_get_references (message);
+
+    THREAD_DEBUG("trying to reparent via references: %s\n",
+		     notmuch_message_get_message_id (message));
+
+    for (notmuch_string_node_t *ref_node = references->head;
+	 ref_node; ref_node = ref_node->next) {
+	THREAD_DEBUG("checking reference=%s\n", ref_node->string);
+	if ((g_hash_table_lookup_extended (thread->message_hash,
+					   ref_node->string, NULL,
+					   (void **) &new_parent))) {
+	    size_t new_depth = _notmuch_message_get_thread_depth (new_parent);
+	    THREAD_DEBUG("got depth %lu\n", new_depth);
+	    if (new_depth > max_depth || !parent) {
+		THREAD_DEBUG("adding at depth %lu parent=%s\n", new_depth, ref_node->string);
+		max_depth = new_depth;
+		parent = new_parent;
+	    }
+	}
+    }
+    if (parent) {
+	THREAD_DEBUG("adding reply %s to parent=%s\n",
+		 notmuch_message_get_message_id (message),
+		 notmuch_message_get_message_id (parent));
+	_notmuch_message_add_reply (parent, message);
+    } else {
+	THREAD_DEBUG("adding as toplevel %s\n",
+		 notmuch_message_get_message_id (message));
+	_notmuch_message_list_add_message (thread->toplevel_list, message);
+    }
+}
+
 static void
 _resolve_thread_relationships (notmuch_thread_t *thread)
 {
     notmuch_message_node_t *node, *first_node;
-    notmuch_message_t *message, *parent;
-    const char *in_reply_to;
+    notmuch_message_t *message;
+    void *local;
+    notmuch_message_list_t *maybe_toplevel_list;
 
     first_node = thread->message_list->head;
     if (! first_node)
 	return;
 
+    local = talloc_new (thread);
+    maybe_toplevel_list = _notmuch_message_list_create (local);
+
     for (node = first_node->next; node; node = node->next) {
 	message = node->message;
-	in_reply_to = _notmuch_message_get_in_reply_to (message);
-	if (in_reply_to && strlen (in_reply_to) &&
-	    g_hash_table_lookup_extended (thread->message_hash,
-					  in_reply_to, NULL,
-					  (void **) &parent))
-	    _notmuch_message_add_reply (parent, message);
-	else
-	    _notmuch_message_list_add_message (thread->toplevel_list, message);
+	if (! _parent_via_in_reply_to (thread, message))
+	    _notmuch_message_list_add_message (maybe_toplevel_list, message);
     }
 
     /*
@@ -418,27 +481,42 @@ _resolve_thread_relationships (notmuch_thread_t *thread)
      */
     if (first_node) {
 	message = first_node->message;
-	in_reply_to = _notmuch_message_get_in_reply_to (message);
-	if (thread->toplevel_list->head &&
-	    in_reply_to && strlen (in_reply_to) &&
-	    g_hash_table_lookup_extended (thread->message_hash,
-					  in_reply_to, NULL,
-					  (void **) &parent))
-	    _notmuch_message_add_reply (parent, message);
+	THREAD_DEBUG("checking first message  %s\n",
+		     notmuch_message_get_message_id (message));
+
+        if (_notmuch_message_list_empty (maybe_toplevel_list) ||
+	    ! _parent_via_in_reply_to (thread, message)) {
+
+	    THREAD_DEBUG("adding first message as toplevel = %s\n",
+			 notmuch_message_get_message_id (message));
+	    _notmuch_message_list_add_message (maybe_toplevel_list, message);
+	}
+    }
+
+    for (notmuch_messages_t *messages = _notmuch_messages_create (maybe_toplevel_list);
+	 notmuch_messages_valid (messages);
+	 notmuch_messages_move_to_next (messages))
+    {
+	notmuch_message_t *message = notmuch_messages_get (messages);
+	_notmuch_message_label_depths (message, 0);
+    }
+
+    for (notmuch_messages_t *roots = _notmuch_messages_create (maybe_toplevel_list);
+	 notmuch_messages_valid (roots);
+	 notmuch_messages_move_to_next (roots)) {
+	notmuch_message_t *message = notmuch_messages_get (roots);
+	if (_notmuch_messages_has_next (roots) || ! _notmuch_message_list_empty (thread->toplevel_list))
+	    _parent_or_toplevel (thread, message);
 	else
 	    _notmuch_message_list_add_message (thread->toplevel_list, message);
     }
 
-    /* XXX: After scanning through the entire list looking for parents
-     * via "In-Reply-To", we should do a second pass that looks at the
-     * list of messages IDs in the "References" header instead. (And
-     * for this the parent would be the "deepest" message of all the
-     * messages found in the "References" list.)
-     *
-     * Doing this will allow messages and sub-threads to be positioned
-     * correctly in the thread even when an intermediate message is
-     * missing from the thread.
+    /* XXX this could be made conditional on messages being inserted
+     * (out of order) in later passes
      */
+    thread->toplevel_list = _notmuch_message_sort_subtrees (thread, thread->toplevel_list);
+
+    talloc_free (local);
 }
 
 /* Create a new notmuch_thread_t object by finding the thread