bug: wrong order of messages in notmuch-show

[David Bremner]

Gregor Zattler <telegraph at gmx.net> writes:

> Hi David, dear notmuch developers,
> * Gregor Zattler <telegraph at gmx.net> [2018-07-01; 23:27]:
>> This happens often to me with emails from a ticket system which I
>> cannot disclose.  In this kind of technical threads order is
>> necessary to understand current status of affairs.
>
> I finally isolated two such threads, anonymized them and indexed
> them.  tar'ed and compressed the maildir is small enough to attach,
> therefore I attached it.
>
>
> With the first thread (Ticket 33712) notmuch shows the "-->"
> marked email last in thread, instead (as according to date sent)
> before position marked "+++":

I find it helpful to look at these things in tree-view. 

     July 09  Gregor Zattler        ┬►xxxxxxx-xxxxxxxxx-server xxxxxxxxxxxx               (inbox)
     July 09  via RT                ╰┬►[support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33712] AutoReply: xxxxxxx-xxxxxxxxx-server xxxxxxxxxxxx (inbox replied)
     July 09  Gregor Zattler         ╰┬► ...                                              (inbox replied)
     July 10  Gregor Zattler          ├─►[support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33712] xxxxxxx-xxxxxxxxx-server xxxxxxxxxxxx (inbox)
  Tue. 20:03  Gregor Zattler          ├─►[support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33712] AutoReply: xxxxxxx-xxxxxxxxx-server xxxxxxxxxxxx (inbox)
     July 09  via RT                  ╰─►[support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33712] xxxxxxx-xxxxxxxxx-server xxxxxxxxxxxx (inbox)

The place notmuch is not doing as nice a job as you would like is in
ordering the children of your July 9 message. I think this is because it
is added into the tree in the second pass. It ends up in this situation
because its In-Reply-To field points to a non-existent (in the local
database).  In the previous version of threading, I'm pretty sure it
would have been a root message, which might have looked a bit better
with respect to dates, but would have been just as confusing.

[enter thinking out loud mode]

I agree there is still room for improvement here.  Looking at the code,
it seems like it might make sense to order the children by date in
_notmuch_message_add_reply. Currently this uses a generic linked list
insert at tail, which is O(1). It would be more expensive to insert by
date, but it would depend how many replies to a given message there are.