181446 - Thread will be broken when child message is followed by parent message if subjects are not the same

Status: RESOLVED FIXED

(MailNews Core :: Database, defect)

Description

[u69748]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; ja-JP; rv:1.0.1) Gecko/20020823 Netscape/7.0
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.3a) Gecko/20021115

Thread will be broken when child message is followed by parent message.


Reproducible: Always

Steps to Reproduce:
I will upload an attachment (mbox) which contains 2 groups of messages,
a:(test1 test2 test3) and b:(test1r test2r test3r)
View messages in thread mode.

Actual Results:  
group a has correct thread view, but group b dose not.
=test1
|-=test2
  |-=test3
=test3r
=test2r
=test1r


Expected Results:  
=test1
|-=test2
  |-=test3
=test1r
|-=test2r
  |-=test3r


The only difference between group a and b is:
in group a, parent message is followed by child message,
in group b, child message is followed by parent message.

This often occurs when we copy/move messages individually.

Comment 1

[u69748]

Attachment: testcase (mbox)

Comment 2

[HARUNAGA Hirotoshi]

dup of Bug 125501, I think.

BTW in this testcase, move test2r to another folder and back to the old
folder, and do the same on test3r, then the problem is solved.

Comment 3

[u69748]

> dup of Bug 125501, I think.

I don't think so.
Bug 125501 mentions about order of threads. 
I think it is a dup of bug 72493.

This bug mentions about building a thread.

> BTW in this testcase, move test2r to another folder and back to the old
> folder, and do the same on test3r, then the problem is solved.

Right. But I have thousands of messages ;-(

Comment 4

[Mike Cowperthwaite]

I don't think this is a dupe of either of those bugs; confirming.

A duplicate of this that I found was for Linux, so OS=>all.

Comment 5

[Mike Cowperthwaite]

*** Bug 184946 has been marked as a duplicate of this bug. ***

Comment 6

[Mike Cowperthwaite]

*** Bug 125501 has been marked as a duplicate of this bug. ***

Comment 7

[R.K.Aa.]

*** Bug 250288 has been marked as a duplicate of this bug. ***

Comment 8

[Mike Cowperthwaite]

*** Bug 234009 has been marked as a duplicate of this bug. ***

Comment 9

[Mike Cowperthwaite]

*** Bug 249283 has been marked as a duplicate of this bug. ***

Comment 10

[David :Bienvenu]

taking. I believe this works if the subjects don't change...

Comment 11

[sidki]

Does this bug cover Thunderbird as well? It appears there, too.
Mozilla Thunderbird 0.8 (Windows/20041001)

Comment 12

[David :Bienvenu]

yes, it's backend code shared by seamonkey and thunderbird.

Comment 13

[sidki]

Okay. Forgot to say, in my case the subjects where the same (disregarding group
tag and Re):

From - Fri Oct 01 22:34:06 2004
Message-ID: <[e-mail]>
In-Reply-To: <[e-mail]>
Date: Fri, 1 Oct 2004 20:21:53 +0200 (CEST)
Subject: Re: [prox] Re: Errors with JD's Poxo configs

From - Fri Oct 01 22:48:13 2004
Message-ID: <[e-mail]>
Date: Fri, 01 Oct 2004 17:59:12 -0000
Subject: [prox] Re: Errors with JD's Poxo configs


However, those two msgs where deeply nested within a thread, and when trying to
isolate them into a separate mbox, i failed to reproduce the problem (editing
the original mbox file and reversing the sort order solved it).

Comment 14

[Jerry Baker]

*** Bug 321240 has been marked as a duplicate of this bug. ***

Comment 15

[Teemu Mannermaa (:wicked)]

Attachment: Fix threading, V1

Here's a patch I have been using to fix this "parent after child" threading issue. This will add to nsMsgDatabase::ThreadNewHdr logic to check if the new message header is a parent of an existing header. This seems to work, although I'm a bit concerned on the performance ramifications. With a folder that has many threads and/or headers this logic will longer and longer to execute. This is because this has two loops, first goes through every thread and second every message of a thread. Any and all ideas are welcome.. For me, getting correct threads is more important than performance. Especially on bugmail. :)

Comment 16

[David :Bienvenu]

yeah, the reason I've never done this is that it will perform awfully...

Comment 17

[David :Bienvenu]

The way 4.x did this was to basically take advantage of the fact that it had a hash table with every message-id that appeared in a message-id or reference header. So, for a new message, we could look at its message id and quickly tell if there was any other message that might refer to the new message via a reference header. You could build up this hash table "on demand", either when we iterate over all the headers in a db, or the first time we find a header that might need threading like this. Then, you'd have to keep the hash table up to date when headers are added/removed from the db (probably by ref-counting).

re this code:

+  nsCOMPtr <nsIDBChangeListener> dbListener = do_QueryInterface(threadEnumerator);
+  if (dbListener)
+    dbListener->OnAnnouncerGoingAway(nsnull);

That seems wrong. If the thread enumerator goes away, it should remove itself as a listener to the db, which will remove its reference.

Comment 18

[David :Bienvenu]

Comment on attachment 214235 [details] [diff] [review]
Fix threading, V1

minusing for now - one option would be to control this by a hidden pref that defaults to off, either a new one, or an existing one like strict threading.

Comment 19

[Mitar]

*** Bug 354877 has been marked as a duplicate of this bug. ***

Comment 20

[Mike Cowperthwaite]

I noticed that a single-source saved-search folder I had was mis-threading messages.  The order looked like this:
   RespA (to Orig)
    - Original
    - RespB (to A)
      - RespC (to B)
      - RespD (to B)
        - RespE (to D)
That is, the original message appeared inside the thread rather than at root, but the other messages were all in order.  The same thread in the source folder was ordered correctly.  The messages were placed in that folder in this order:
  RespA, RespC, RespD, RespB, RespE, Original
The first three were dragged from my Inbox in one action, and the others dragged from my Sent folder in two actions.

So I wanted to create a simple test case.  I created two subfolders, and copied the messages to them; in the first subfolder, I copied them in (one at a time) in date order, and in the other, in the original folder's order received.  The date-order subfolder threads as expected.  The duplicate-order-received subfolder threads incorrectly even without creating a search folder: the 'Re:' messages are all sorted correctly, but the original isn't even included in the thread -- which is this bug, but comment 10 implies that since the subjects are the same (modulo the 'Re') they should be threaded correctly.
And they *are* threaded correctly in the original folder.

Same results regardless of  mail.strict_threading.  TB 2b2-0207.

Comment 21

[Teemu Mannermaa (:wicked)]

Attachment: Fix threading, V2

This now uses a reference hash that's created when it's first time needed and then kept in sync whenever messages are added or removed from the DB. In addition to fixing threads where "parent comes after child" this also fixes threads where the referenced message is missing. In this case messages that reference same (missing) message are put into same thread. For example, this can happen when "new bug" bugmail is deleted because all later "changed bug" bugmail point to it.

Comment 22

[David :Bienvenu]

Comment on attachment 258461 [details] [diff] [review]
Fix threading, V2

do we only do this on strict threading? In general, I don't think most users care about this...

Comment 23

[Teemu Mannermaa (:wicked)]

(In reply to comment #22)
> do we only do this on strict threading? In general, I don't think most users

No, parent finding is tried always as a last effort like reference threading is always tried first. Same referenced message thread is an extension of current reference threading.

AFAICS, strict threading setting is only used to disable subject threading that's now a second attempt at finding a thread.

Comment 24

[David :Bienvenu]

I'm not sure I want to pay the memory usage and cpu usage of this solution for everybody - most users simply don't care...

Comment 25

[David :Bienvenu]

one comment - you might want to use an arena for the memory allocated for the new hash table - either an existing arena or a new one...that'll reduce memory fragmentation and immensely speed up freeing up the memory when the db is closed.

Comment 27

[Teemu Mannermaa (:wicked)]

Attachment: Fix threading, V2.1

This adds new pref with name mail.correct_threading to enable or disable reference threading fixes in this patch. I first thought about using Strict Threading pref but it's likely somebody would want to have correct reference threading independently from using subjects for threading.

It was agreed on irc with bienvenu that memory arenas will be left for later or even to a different bug where they are implemented to all things that benefit from them. Also, I currently think memory arena support is best to leave for hash table code itself. And I still don't know exactly what they are. :)

Comment 28

[David :Bienvenu]

Comment on attachment 272474 [details] [diff] [review]
Fix threading, V2.1

Overall, this looks pretty good. Except for:

+      element->mRef = PL_strdup(reference.get());

this can be element->mRef = ToNewCString(reference);

And why is it  a void *? And do you even need this field? The ref string is already stored in the hash key, if I understand correctly...

Also, unless I'm missing something, you're leaking this string anyway...

Comment 29

[Teemu Mannermaa (:wicked)]

Attachment: Fix threading, V2.2

(In reply to comment #28)
> +      element->mRef = PL_strdup(reference.get());
> this can be element->mRef = ToNewCString(reference);

Okay, here's a new patch with this change. I hope it's fine to use free() to free result of this instead of nsMemory::Free as said in a comment.

> And why is it  a void *? And do you even need this field? The ref string is
> already stored in the hash key, if I understand correctly...

Yes, it's needed, if I understand XPCom hash table code correctly. That's actually the stored string key that's get used by the hash table code to make final matches of entries during searches and additions. Specifically by the PL_DHashMatchStringKey() function that's defined as the entry matcher op for the reference hash table.

I originally made it void * because that's how minimal entry stub is defined in pldhash.h line 356. I guess it could also be char * to not confuse things. Changed in this patch.

> Also, unless I'm missing something, you're leaking this string anyway...

They should get freed by the hash table code. Specifically by the PL_DHashFreeStringKey() function that's defined as the entry destructor op for  the reference hash table.

Comment 30

[David :Bienvenu]

Ah, I see, you're right. You might do what this code does instead:

http://mxr.mozilla.org/seamonkey/source/xpcom/io/nsFastLoadFile.cpp#309

but I don't care that much - but I do think a comment might help, though, about how this matches PLDHashEntryStub in pldhash.h, and the hash functions handle freeing that memory.

I'm going to try running with your patch for a bit. Thx for the patch!

Comment 31

[David :Bienvenu]

a few more comments:

+  if (numReferences > 0)
+    return NS_OK;
+  else
+    return NS_ERROR_FAILURE;


can just be 

return (numReferences) ? NS_OK : NS_ERROR_FAILURE;

and
+  if (m_msgReferences)
+    delete m_msgReferences;

can just be
+  delete m_msgReferences;

since delete already checks for null.

For the trunk, we're not using nsXPIDLStrings anymore

+    nsXPIDLCString msgId;
+    newHdr->GetMessageId(getter_Copies(msgId));
+    nsCAutoString cMsgId(msgId);

so msgId can just be an nsCString and you can skip the nsCAutoString (nsCString supports getter_Copies now.

+    if (element->mRef == nsnull)
+    {
+      element->mRef = ToNewCString(reference);
+      element->mThreadId = threadId;
+      element->mCount = 1;
+    } else
+      element->mCount += 1;
+  }

we'd prefer

if (!element->mRef)

and:

}
else
  element->mCount++;

Comment 32

[David :Bienvenu]

Comment on attachment 272733 [details] [diff] [review]
Fix threading, V2.2

and:

+      element->mCount -= 1;
+      if (element->mCount == 0)
+        
can just be 

if (--element->mCount == 0)

So if you could submit a patch with all those little nits fixed, then I think we'll be good to go, assuming it runs OK in my tests...

Comment 33

[David :Bienvenu]

I've run with the patch, and the pref turned on, and haven't seen any problems, and verified that it does fix the attached test case. Excellent job! If you can just submit a patch that fixes the little code issues, then we can get this checked in.

Comment 34

[Teemu Mannermaa (:wicked)]

Attachment: Fix threading, V2.3

This should address all your comments except possibly some part from comment #30 which you don't care about.

Comment 35

[David :Bienvenu]

Comment on attachment 273092 [details] [diff] [review]
Fix threading, V2.3

looks good, thx.

Comment 36

[Scott MacGregor]

Comment on attachment 273092 [details] [diff] [review]
Fix threading, V2.3

does it make sense to use one of our hash table abstraction classes instead of PLDHashTable? Like nsInterfaceHashTable using a nsCString as the key?

i.e. 

also, what happens if both of these prefs are set to true?

+pref("mail.strict_threading",               false); // if true, don't thread by subject at all
+pref("mail.correct_threading",              false); // if true, makes sure threading works correctly always (see bug 181446)

Comment 38

[Teemu Mannermaa (:wicked)]

(In reply to comment #36)
> does it make sense to use one of our hash table abstraction classes instead of
> PLDHashTable? Like nsInterfaceHashTable using a nsCString as the key?

I used PLDHashTable because that's what was already used in that class. Do you want me to try rewrite with nsInterfaceHashTable instead? I guess it could simplify code but I'm not sure at the moment what I would use as the interface pointer or how to make sure count duplicate references correctly.

> +pref("mail.strict_threading",               false); // if true, don't thread
> by subject at all
> +pref("mail.correct_threading",              false); // if true, makes sure
> threading works correctly always (see bug 181446)

Just what the comments say. First disables subject threading (second step) so only reference threading (first step) is attempted. Second enables reference threading fixes (third step) from my patch. Steps mean attempts to find a thread for the new message in nsMsgDatabase::ThreadNewHdr() method.

Comment 39

[Scott MacGregor]

Comment on attachment 273092 [details] [diff] [review]
Fix threading, V2.3

ok...thanks for answering my questions.

Comment 40

[Frank Wein [:mcsmurf]]

I checked the patch in:
Checking in mailnews/db/msgdb/public/nsMsgDatabase.h;
/cvsroot/mozilla/mailnews/db/msgdb/public/nsMsgDatabase.h,v  <--  nsMsgDatabase.h
new revision: 1.129; previous revision: 1.128
done
Checking in mailnews/db/msgdb/src/nsMsgDatabase.cpp;
/cvsroot/mozilla/mailnews/db/msgdb/src/nsMsgDatabase.cpp,v  <--  nsMsgDatabase.cpp
new revision: 1.386; previous revision: 1.385
done
Checking in mailnews/mailnews.js;
/cvsroot/mozilla/mailnews/mailnews.js,v  <--  mailnews.js
new revision: 3.303; previous revision: 3.302
done

Comment 41

[Frédéric Buclin]

Why is this bug left open?

Comment 42

[Frank Wein [:mcsmurf]]

Teemu needs to know if this bug is now fixed, I don't know that :-).

Comment 43

[Teemu Mannermaa (:wicked)]

Thanks for checkin this in, Frank. Fix does seem to be in the latest nightly build of trunk (currently build 2007080505).

Comment 44

[Frédéric Buclin]

No chance to see it checked in on the 2.0.0.x branch?