bug: wrong order of messages in notmuch-show

bug: wrong order of messages in notmuch-show

[Gregor Zattler]

Dear notmuch developers,

notmuch sometimes shows emails of one thread in wrong order.  Now
I found an example in a public mailing list so it is possible to
share this example.  It is a small thread from the notmuch
mailing list, you might find it by searching for id:87zhzccrwg.fsf@tethera.net

While this email is the last written and sent in this thread it
is shown as first email in the notmuch show output, as shown in
this "screenshot" of the corresponding notmuch-emacs buffer:

      File Edit Options Buffers Tools Help
      'notmuch search thread:<>' lists multiple threads
-->   David Bremner <david@tethera.net> (Yest. 15:42) (inbox new unread)
      Subject: Re: 'notmuch search thread:<>' lists multiple threads
      Naveen N. Rao <naveen.n.rao@linux.vnet.ibm.com> (April 06) (inbox new unread)
       Naveen N. Rao <naveen.n.rao@linux.vnet.ibm.com> (April 06) (inbox new unread)
       David Bremner <david@tethera.net> (April 08) (inbox new unread)
        David Bremner <david@tethera.net> (April 09) (inbox new unread)
         David Bremner <david@tethera.net> (April 10) (inbox new unread)
         Subject: [PATCH] devel: add new tool to draw thread structure
         Naveen N. Rao <naveen.n.rao@linux.vnet.ibm.com> (April 18) (inbox new unread)
         Subject: Re: 'notmuch search thread:<>' lists multiple threads
          David Bremner <david@tethera.net> (April 22) (inbox new unread)


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 did a test with notmuch 0.27+7~gfd3c936 and .notmuch-config
pointing to a test maildir with this 8 messages as they arrived
at my email account.  I saved a tar archive of this in case this
is important to debug the problem.

Thanks, for your attention, Gregor

Re: bug: wrong order of messages in notmuch-show

[Amin Bandali]

For what it's worth, I've also noticed a similar behaviour for
some threads on some of the lists.gnu.org lists lately.

-amin

Re: bug: wrong order of messages in notmuch-show

[David Bremner]

Gregor Zattler <telegraph@gmx.net> writes:

> Dear notmuch developers,
>
> notmuch sometimes shows emails of one thread in wrong order.  Now
> I found an example in a public mailing list so it is possible to
> share this example.  It is a small thread from the notmuch
> mailing list, you might find it by searching for id:87zhzccrwg.fsf@tethera.net
>
> While this email is the last written and sent in this thread it
> is shown as first email in the notmuch show output, as shown in
> this "screenshot" of the corresponding notmuch-emacs buffer:
>
>       File Edit Options Buffers Tools Help
>       'notmuch search thread:<>' lists multiple threads
> -->   David Bremner <david@tethera.net> (Yest. 15:42) (inbox new unread)
>       Subject: Re: 'notmuch search thread:<>' lists multiple threads
>       Naveen N. Rao <naveen.n.rao@linux.vnet.ibm.com> (April 06) (inbox new unread)
>        Naveen N. Rao <naveen.n.rao@linux.vnet.ibm.com> (April 06) (inbox new unread)
>        David Bremner <david@tethera.net> (April 08) (inbox new unread)
>         David Bremner <david@tethera.net> (April 09) (inbox new unread)
>          David Bremner <david@tethera.net> (April 10) (inbox new unread)
>          Subject: [PATCH] devel: add new tool to draw thread structure
>          Naveen N. Rao <naveen.n.rao@linux.vnet.ibm.com> (April 18) (inbox new unread)
>          Subject: Re: 'notmuch search thread:<>' lists multiple threads
>           David Bremner <david@tethera.net> (April 22) (inbox new unread)
>

Hi Gregor;

The thread is not ordered that way here. Can you run the "draw-thread"
tool in id:20180410014539.24717-1-david@tethera.net and send the output
(either dot or PDF) as an attachement to the list?

>
> 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.

Unfortunately ticket systems seem to be among the worse offenders for
generating nonsense headers.

> I did a test with notmuch 0.27+7~gfd3c936 and .notmuch-config
> pointing to a test maildir with this 8 messages as they arrived
> at my email account.  I saved a tar archive of this in case this
> is important to debug the problem.
>

Yes, I'll probably need the tar file to reproduce it. If it's small
(<50k), send it to the list, otherwise let me know how I can pick it up.

Re: bug: wrong order of messages in notmuch-show

[Gregor Zattler]

Hi David,
* David Bremner <david@tethera.net> [2018-07-01; 21:23]:
> Gregor Zattler <telegraph@gmx.net> writes:
> The thread is not ordered that way here. Can you run the "draw-thread"
> tool in id:20180410014539.24717-1-david@tethera.net and send the output
> (either dot or PDF) as an attachement to the list?

sure, I produced two sets of files:

the ones with "for-real" in their names are done with my working
notmuch installation, the ones with "test-order-notmuch" in their
names are done with ta maildir which only contains the relevant
messages.

> Yes, I'll probably need the tar file to reproduce it. If it's small
> (<50k), send it to the list, otherwise let me know how I can pick it up.


This tar file also contains a tar file with the xapian database for these 8
messages etc.:
https://giku.de/4iczfdzgnedth8ni--notmuch-show-order-problem.tar.7z

Thanks for looking into this.  Ciao; Gregor 

(no subject)

[David Bremner]

Thanks to Gregor for the test data. I can now duplicate the problem
with a regression test using (small) synthetic data.

[PATCH 1/2] test: start threading test corpus

[David Bremner]

These are not really broken, but one of the messages is in reply to a
non-existent message. This currently causes the wrong message to be
chosen as root
---
 test/corpora/threading/ghost-root/child     | 9 +++++++++
 test/corpora/threading/ghost-root/fake-root | 9 +++++++++
 test/corpora/threading/ghost-root/real-root | 7 +++++++
 3 files changed, 25 insertions(+)
 create mode 100644 test/corpora/threading/ghost-root/child
 create mode 100644 test/corpora/threading/ghost-root/fake-root
 create mode 100644 test/corpora/threading/ghost-root/real-root

diff --git a/test/corpora/threading/ghost-root/child b/test/corpora/threading/ghost-root/child
new file mode 100644
index 00000000..a8dc245d
--- /dev/null
+++ b/test/corpora/threading/ghost-root/child
@@ -0,0 +1,9 @@
+From: Alice <alice@example.org>
+To: Daniel <daniel@example.org>
+Subject: child message
+Message-ID: <mid-child@example.org>
+In-Reply-To: <mid-real-root@example.org>
+References:  <mid-real-root@example.org>
+Date: Fri, 17 Jun 2016 22:14:41 -0400
+
+
diff --git a/test/corpora/threading/ghost-root/fake-root b/test/corpora/threading/ghost-root/fake-root
new file mode 100644
index 00000000..11928537
--- /dev/null
+++ b/test/corpora/threading/ghost-root/fake-root
@@ -0,0 +1,9 @@
+From: Mallory <mallory@example.org>
+To: Daniel <daniel@example.org>
+Subject: fake root message
+Message-ID: <mid-fake-message-root@example.org>
+In-Reply-to: <nonexistent-message@example.org>
+References:  <mid-real-root@example.org> <nonexistent-message@example.org>
+Date: Thu, 16 Jun 2016 22:14:41 -0400
+
+This message has no reply-to
diff --git a/test/corpora/threading/ghost-root/real-root b/test/corpora/threading/ghost-root/real-root
new file mode 100644
index 00000000..8c4e59b3
--- /dev/null
+++ b/test/corpora/threading/ghost-root/real-root
@@ -0,0 +1,7 @@
+From: Alice <alice@example.org>
+To: Daniel <daniel@example.org>
+Subject: root message
+Message-ID: <mid-real-root@example.org>
+Date: Thu, 16 Jun 2016 22:14:41 -0400
+
+This message has no reply-to
-- 
2.18.0

[PATCH 2/2] test: add known broken test for "ghost roots"

[David Bremner]

This documents the bug discussed at

     id:87efgmmysi.fsf@len.workgroup

I believe the underlying issue is that the reply to a ghost-message is
falsely classified as a root message in _resolve_thread_relationships.
---
 test/T260-thread-order.sh | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/test/T260-thread-order.sh b/test/T260-thread-order.sh
index fea61275..365ca657 100755
--- a/test/T260-thread-order.sh
+++ b/test/T260-thread-order.sh
@@ -75,4 +75,14 @@ $(for ((i = 0; i < $nthreads; i++)); do
 done
 test_expect_equal "$output" "$expected"
 
+add_email_corpus threading
+
+test_begin_subtest "reply to ghost"
+test_subtest_known_broken
+notmuch show --entire-thread=true id:mid-real-root@example.org | grep ^Subject: | head -1  > OUTPUT
+cat <<EOF > EXPECTED
+Subject: root message
+EOF
+test_expect_equal_file EXPECTED OUTPUT
+
 test_done
-- 
2.18.0

Re: bug: wrong order of messages in notmuch-show

[Gregor Zattler]

[-- Attachment #1: Type: text/plain, Size: 2878 bytes --]

Hi David, dear notmuch developers,
* Gregor Zattler <telegraph@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 "+++":

      [support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33712] xxxxxxx-xxxxxxxxx-server xxxxxxxxxxxx
      Gregor Zattler <g.zattler@xxxxxxx-xxxxxxxxx.de> (Mon, 09 Jul 2018 10:03:54 +0200) (inbox)
      Subject: xxxxxxx-xxxxxxxxx-server xxxxxxxxxxxx
        via RT <rt-xxx@xxxxxxx-xxxxxxxxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de> (Mon, 09 Jul 2018 10:04:03 +0200) (inbox replied)
        Subject: [support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33712] AutoReply: xxxxxxx-xxxxxxxxx-server xxxxxxxxxxxx
          Gregor Zattler <g.zattler@xxxxxxx-xxxxxxxxx.de> (Mon, 09 Jul 2018 10:24:26 +0200) (inbox replied)
            Gregor Zattler <g.zattler@xxxxxxx-xxxxxxxxx.de> (Tue, 10 Jul 2018 12:18:39 +0200) (inbox)
            Subject: Re: [support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33712] xxxxxxx-xxxxxxxxx-server xxxxxxxxxxxx
+++         Gregor Zattler <g.zattler@xxxxxxx-xxxxxxxxx.de> (Tue, 24 Jul 2018 14:03:22 +0200) (inbox)
            Subject: Re: [support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33712] AutoReply: xxxxxxx-xxxxxxxxx-server xxxxxxxxxxxx
-->         via RT <rt-xxx@xxxxxxx-xxxxxxxxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de> (Mon, 09 Jul 2018 10:37:43 +0200) (inbox)
            Subject: [support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33712] xxxxxxx-xxxxxxxxx-server xxxxxxxxxxxx
      
      

With the second thread the email marked "-->" should be at the
end, IMHO.  I don'nt know how this Resolved-Message is produced,
perhaps it is not a reply to the last message in thread:

      
      [support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33575] AutoReply: FYI: xxxx  xxxxxxx  xxxxxxxxxxxx xxx
       via RT <rt-xxx@xxxxxxx-xxxxxxxxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de> (Tue, 26 Jun 2018 14:44:24 +0200) (inbox)
-->   Subject: [support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33575] Resolved: FYI: xxxx  xxxxxxx  xxxxxxxxxxxx xxx
      Gregor Zattler <g.zattler@xxxxxxx-xxxxxxxxx.de> (Tue, 19 Jun 2018 18:26:26 +0200) (inbox)
      Subject: FYI: xxxx  xxxxxxx  xxxxxxxxxxxx xxx
         via RT <rt-xxx@xxxxxxx-xxxxxxxxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de> (Tue, 19 Jun 2018 18:26:36 +0200) (inbox)
        Subject: [support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33575] AutoReply: FYI: xxxx  xxxxxxx  xxxxxxxxxxxx xxx





Thanks again for your attention.


Ciao; Gregor
-- 
 -... --- .-. . -.. ..--.. ...-.-

[-- Attachment #2: test-email-order-in-threads.tar.xz --]
[-- Type: application/x-xz, Size: 18400 bytes --]

Re: bug: wrong order of messages in notmuch-show

[David Bremner]

Gregor Zattler <telegraph@gmx.net> writes:

> Hi David, dear notmuch developers,
> * Gregor Zattler <telegraph@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.

Re: bug: wrong order of messages in notmuch-show

[Gregor Zattler]

Hi David,
* David Bremner <david@tethera.net> [2018-07-29; 17:47]:
> Gregor Zattler <telegraph@gmx.net> writes:
>> * Gregor Zattler <telegraph@gmx.net> [2018-07-01; 23:27]:
> 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.

Yes it would or was.  Your poatches are surely an improvement.

> [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.

Thanks for considering this.


FWIW: This is what mutt does (the '=>' marks duplicates):

   1|   | 0|Di-19.06.18-18:26|Gregor Zattler      |  0K|FYI: xxxx  xxxxxxx  xxxxxxxxxxxx xxx
   2|   | 0|Di-19.06.18-18:26| via RT             |0,1K|`->[support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33575] AutoReply: FYI: xxxx  xxxxxxx  xxxxxxxxxxxx xxx
   3|   | 0|Di-26.06.18-14:44| via RT             |0,1K|[support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33575] Resolved: FYI: xxxx  xxxxxxx  xxxxxxxxxxxx xxx
   4|   | 0|Mo-09.07.18-10:03|Gregor Zattler      |0,1K|xxxxxxx-xxxxxxxxx-server xxxxxxxxxxxx
   5|r  | 0|Mo-09.07.18-10:04|via RT              |0,1K|`->[support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33712] AutoReply: xxxxxxx-xxxxxxxxx-server xxxxxxxxxxxx
   6|r  | 0|Mo-09.07.18-10:24|Gregor Zattler      |0,1K|  `->
   7|r  | 0|Mo-09.07.18-10:24|Gregor Zattler      |0,1K|    |=>
   8|   | 0|Mo-09.07.18-10:37|via RT              |0,1K|    |->[support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33712] xxxxxxx-xxxxxxxxx-server xxxxxxxxxxxx
   9|   | 0|Di-10.07.18-12:18|Gregor Zattler      |0,1K|    |->Re: [support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33712] xxxxxxx-xxxxxxxxx-server xxxxxxxxxxxx
  10|   | 0|Di-10.07.18-12:18|Gregor Zattler      |0,1K|    | `=>
  11|   | 0|Di-24.07.18-14:03|Gregor Zattler      |0,1K|    `->Re: [support.xxxxxxxxxxx-xxxxxxxxx-xxxxxxxxx.de #33712] AutoReply: xxxxxxx-xxxxxxxxx-server xxxxxxxxxxxx
  12|   | 0|Di-24.07.18-14:03|Gregor Zattler      |0,1K|      `=>

- The treads are ordered according to date of arrival.

- The "resolved" email (No 3) is not part of the 33575-Thread
  (which is a pity).


Thanks, Gregor
-- 
 -... --- .-. . -.. ..--.. ...-.-

Re: bug: wrong order of messages in notmuch-show

[David Bremner]

Gregor Zattler <telegraph@gmx.net> writes:

> Dear notmuch developers,
>
> notmuch sometimes shows emails of one thread in wrong order.  Now
> I found an example in a public mailing list so it is possible to
> share this example.  It is a small thread from the notmuch
> mailing list, you might find it by searching for id:87zhzccrwg.fsf@tethera.net
>
> While this email is the last written and sent in this thread it
> is shown as first email in the notmuch show output, as shown in
> this "screenshot" of the corresponding notmuch-emacs buffer:

As far as I know the problems discussed in this message should be fixed
in commit 87934c432c4bee9df09f268a3f05933c59c2caf1, so I'm marking it
fixed.

d

Re: bug: wrong order of messages in notmuch-show

[Gregor Zattler]

Hi David, notmuch developers,
* David Bremner <david@tethera.net> [2018-09-08; 07:35]:
> Gregor Zattler <telegraph@gmx.net> writes:
>> notmuch sometimes shows emails of one thread in wrong order.  Now
>> I found an example in a public mailing list so it is possible to
>> share this example.  It is a small thread from the notmuch
>> mailing list, you might find it by searching for id:87zhzccrwg.fsf@tethera.net
>>
>> While this email is the last written and sent in this thread it
>> is shown as first email in the notmuch show output, as shown in
>> this "screenshot" of the corresponding notmuch-emacs buffer:
>
> As far as I know the problems discussed in this message should be fixed
> in commit 87934c432c4bee9df09f268a3f05933c59c2caf1, so I'm marking it
> fixed.

Yes, for me these problems are fixed now, as the ones described in
id:87fu05p2iu.fsf@len.workgroup

Thanks, it's much easier now for me to follow long email threads.


Ciao; Gregor
-- 
 -... --- .-. . -.. ..--.. ...-.-