1183490 - New emails into a mailbox do not adhere to sort by order received

Status: RESOLVED FIXED

(MailNews Core :: Backend, defect)

Description

[Mark Tischler]

User Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:39.0) Gecko/20100101 Firefox/39.0
Build ID: 20150630154324

Steps to reproduce:

Sort By set to "Order Received/Ascending/Unthreaded".  Threads set to "All".  Layout = "Wide View".  Headers = "Normal".  When new messages arrive they do not appear, at bottom of the pane.  They appear in the middle somewhere.  This seemingly started around the time that v38 was introduced.  I can take a message from my Inbox, move it to my Templates folder, and then back again, and it still appears in the middle of the list of Inbox messages, instead of at the bottom, where it should be.


Actual results:

Move message from one folder to another and back again, with Sort By set to "Order Received/Ascending", and message should appear at bottom of the list of emails, but it doesn't.


Expected results:

It should have appeared at the bottom of the list of emails. Changing "Ascending" to "Descending" doesn't solve the problem.  Message still appears in middle of list, rather than at top.

Comment 1

[:aceman]

Can you observe the number the message has in the Order received ? How does it change when you move the message and what is the value compared to the other surrounding messages?

Comment 2

[Mark Tischler]

Unfortunately, this problem seems to come and go.  Right now, it is gone.

I'm not sure what you mean by "the number the message has".  Do you mean simply counting from the top of the frame down (or the bottom of the frame up)?  When the messages are moved to another mailbox and then back again, I recall that they reappear in the same order they were in before.  Is that what you're looking for?

Perhaps when it starts happening again, I can be more precise. For now, if you want to put this ticket on hold, that would be fine, and I can add a comment to the ticket when I see it start to happen again.

Comment 3

[:aceman]

I mean the number that is shown in the Order received column.

Comment 4

[Mark Tischler]

Ah, didn't know this column existed.  (I rarely pull down the list of possible columns.) Next time, it happens, I will be sure to show this column and report back my findings.  Thanks.

Comment 5

[Mark Tischler]

Well it happened again.  I have uploaded a screenshot of when the email first came in -- 1.png.  I then moved it to the 'Sent' folder, and 2.png is a screenshot of that.  I then moved it back to the 'Inbox', and 3.png is a screenshot of that.  In each case, I have shown the 'Order Received' column.  As you can see the 'Order Received' number does change each time the message is moved.  But it's wrong in every case.  Note, both folders are set to Sort By Order Received.  Also, note that I moved the message each time by dragging the message to the other folder (not by right-clicking on the message and selecting the "Move To" optionO. So, I decided to try moving it with the "Move To" menu option, so I moved it to the 'Sent' folder again with this method -- 4.png shows the result.  I then used the "Move To" menu option to move it back to the Inbox, and 5.png is the result of that.  It seems that each time I repeated the move (by either method), the Order Received number went up somewhat, but it was, of course, still not right.  Perhaps if I had moved it back and forth enough times, it would eventually work its way to the right place.

Comment 6

[Mark Tischler]

Attachment: When message first arrived in Inbox

Comment 7

[Mark Tischler]

Attachment: Moved to 'Sent' folder via drag/drop

Comment 8

[Mark Tischler]

Attachment: Moved back to Inbox via drag/drop

Comment 9

[Mark Tischler]

Attachment: Moved to 'Sent' folder again, but with "Move To" menu option

Comment 10

[Mark Tischler]

Attachment: Moved back to 'Inbox' folder again, but with "Move To" menu option

Comment 11

[seppley]

I confirm this bug exists.  For my Thunderbird the bug began last night (July 22 2015).  The "order received" numbers that Thunderbird has assigned to the most recent incoming messages are less than the numbers that were assigned to the slightly less recent messages, which causes the most recent messages to be erroneously sorted (descending) after the slightly less recent messages.  Those numbers should increase monotonically so the most recently received message has the highest number, but Thunderbird seems to have lost track of the highest number already assigned.  In other words, the sorting works properly, but it's sorting using buggy numbers.

Comment 12

[seppley]

This is an addendum to the comment I posted a few minutes ago.  I tried exiting and relaunching Thunderbird to see whether it would recalculate the highest "order received" number it's already assigned, so that subsequently received emails would display at the top of the inbox (which is sorted descending by order number).  To test whether it worked, after relaunching Thunderbird I sent myself a new email, but it still didn't work right... the order received number Thunderbird assigned it upon reception (271250977) is still less than the highest order received number (273987648, which was assigned to one of yesterday's messages).

After the bug is fixed, we users will also need a tool that allows us to revise the order received numbers of the batch of messages that have erroneous numbers.  Otherwise, those messages will continue to display in the wrong order even after the bug is fixed.

Comment 13

[seppley]

I discovered a 5-step procedure that corrects the "order received" sort order of the Inbox:
1. Create a temporary email folder, which I will refer to as Temp in the remaining steps.
2. Move the most recent messages that are failing to display at the top (if the Inbox is sorted descending by "order received") or bottom (if the Inbox is sorted ascending by "order received") of the Inbox, plus the slightly older messages that are displaying above (or below, if ascending order) them, to the Temp folder.
3. Move those slightly older messages back from the Temp folder to the Inbox folder.
4. Move the most recent messages back from the Temp folder to the Inbox folder.
5. The Temp folder should be empty; delete it since we're done.

(Note that the 3 Move operations can be done by highlighting the messages you want to move, then dragging & dropping them using the mouse.)

Helpful to my discovery of the above procedure was the following: 
"Keep in mind, however, that Thunderbird changes the "order-received number" each time you manually move a message to another folder; as a result, if you change your mind and move a month-old message back into the Inbox, it will be listed as the newest message."

I found that sentence at:
http://www.omnitechsupport.com/Resources/EmailClients/mozilla/generic/four.html

Although I've corrected the sort order, obviously the potential exists for the problem to recur, because Thunderbird can somehow lose track of the highest assigned order-received number.  So I think someone should find and eliminate this bug.

By the way, the undesirable behavior mentioned in that webpage excerpt, about a manually moved old message being listed as the newest message, can be solved using essentially the same procedure: move the newer messages out of the folder, and then move them back, so they will all be properly sorted.

Comment 14

[[e-mail]]

Attachment: bugzilla order receiver problem.doc

I have had this problem off and on for a month or so.  Reading your discussion of the problem rang a bell.   

Just Repair the folder having the problem, it resequences the earlier messages that have higher order received numbers to fit below (above if descending) the new incoming messages.

Comment 15

[Mark Tischler]

That's nice to repair the folder once, but then, when the next mail arrives, it comes in out of order.  I don't really think repairing the folder multiple times a day is what I want to spend my time on.  In addition, I have multiple folders (Inbox, Sent, Trash) that are all experiencing this problem, which now multiplies that remedy. However, repairing the folder will likely work to fix each folder one time once Thunderbird is no longer providing emails out of order.

By the way, this ticket ought not to be "unconfirmed" at this point.  It has been confirmed by multiple other people, and it would be nice if someone took it and started work on it.  This is a very annoying problem.

Comment 16

[:aceman]

(In reply to [e-mail] from comment #14)
> Just Repair the folder having the problem, it resequences the earlier
> messages that have higher order received numbers to fit below (above if
> descending) the new incoming messages.

After repairing the folder, does the problem come back with new messages?

Comment 17

[:aceman]

Mark, thanks for the images, I now see what you mean. It is absolutely strange that the moved message is "inserted" into the middle of the existing messages (going by the order received number).
This does not represent the internal design in TB. When putting a new message into a folder (e.g. downloading via POP3, or copying/moving from other folder), TB just appends the message data to the end of the file representing the folder. Then TB allocates new "order received" number like this:
1. equal to the 'position of the message data in the file'. So it will be "order received" of the last message+size of that last message (also deleted messages may still be in the file so contributing to the number). This is called the offset or file position in the file.
2. equal to the 'highest "order received" number in that folder' PLUS 1. This is done in some situations e.g. when filters move the message. Even in this scenario the position in the file is stored somewhere else, just not in the "order received" number.

So the number is monotonically growing. Unless you compact the folder, then the deleted messages are really removed and the valid messages get new positions in the file (offsets) in the "order received" number. At least that was the case in TB31. I think already in TB38 compacting does not change the "order received" number for any valid (visible) message.

Comment 18

[:aceman]

Great and I think therein lies the bug:(
After compaction, if the file shrinks and "order received" is allocated for new messages using method 1., the number can be lower than some of the older messages in that folder, whose original offset in the file (from the time it was larger) was preserved.

I was now able to reproduce my problem in current trunk, STR:
1. delete some msgs, but not the ones with highest "order received"
2. compact
3. copy new msgs into the folder

This is potentially datalossy, as I think there is a small but non-zero chance that a new message gets the same offset that an older message already has. Maybe the database will reject duplicate msgkey (=offset), but then we may reject to store the message at all and lose it (depends on what the code really does).

I think this is fallout of bug 854798. I need to see if this can be fixed quickly, or we back out bug 854798.

Comment 19

[seppley]

The problem came back after the procedure (moving messages temporarily to another folder) that I described here a few weeks ago, and kept coming back every few days after each time I repeated the procedure.  So I don't know if the problem will recur after "repairing" the folder.

I did manage to get it to stop recurring, but only after trying several variations of my procedure.  Unfortunately I don't recall the exact details of what made the problem stop.  One thing I did, which I don't think was sufficient to stop it from recurring, and perhaps wasn't necessary, was to permanently move most of the emails in the folder (which had grown very large) to a subfolder. (Not an ideal fix, in my opinion, since the extra folder complicates searching for messages.)  If memory serves, the other things I tried were various combinations of the following: compacting the folder, temporarily moving all messages to other folders, and exiting/restarting Thunderbird.

I agree with Mark that the issue should not still be classified as "unconfirmed."  Glad to see it was upgraded while I was composing this!

(Another bug I hope will be fixed is that Thunderbird frequently creates redundant copies of incoming messages when it moves email from the IMAP server to my local Inbox folder.  Perhaps it's a timing issue with the IMAP server that hosts my email account, causing the server not to delete the moved emails fast enough so that Thunderbird sees them again and downloads them again?  Whatever the cause, perhaps Thunderbird could be made more robust by checking for duplicates when downloading email.  When I have more time, I'll check whether this bug already has a ticket.)

By the way, when I googled 'thunderbird repair folder' I noticed one of the results was about problems that may be caused by repairing folders; in particular losing messages.  If repair is still buggy, it seems a risky solution to our problem.

Comment 20

[Mark Tischler]

I compact folders typically once every week or two.  I have done this for a long time.

In answer to a previous question, as I stated in comment #15, after I repaired my inbox, the next new message that came in, came in out of order again.  That's why I stated that repairing a folder might be nice for what's currently in there, but the order breaks down again once a new message comes in. So, repairing folders is a recurring job until this issue is fixed.

Thanks for getting this ticket assigned.

Comment 21

[seppley]

Thanks for the suggestion of disabling the automatic folder compacting and not manually compacting.  I hope we'll be notified when the bug is fixed, so we can resume compacting.

Comment 22

[alta88]

The problem is that Order Received is a quite incorrect description for its value.  For pop/local folders, it means offset in the mbox file, for imap it's sequential, for the new maildir it's based on file order in the /cur directory. It can but does *not* have to mean date or temporal ordering at all.  Clearly, an old (by date) message copied into any existing folder with messages will by definition have the highest value.

The value is called byId internally and used when no explicit sort is known or requested.  It has no useful end user value and should be removed from the UI as a sort option. Or at least renamed Index or such. Is there any use case where one really doesn't mean Date?  Is it useful to know 'Order of insertion into the file'?  Unlikely.

Comment 23

[seppley]

[I'm answering the question posed by Alta88.]  The reason I sort my Inbox by "Order Received (descending)" instead of by "Date (descending)" is because some incoming emails contain a very old date.  If I sort by Date, I would discover those "new old" messages only if I scroll down far enough and scrutinize every unread message I see.  Usually such scrolling down would be a waste of time, and how can one know how far down to scroll?  What I'd really like to sort by is the date when Thunderbird first accessed the message (or its header), or the date Thunderbird received the message, or the date that my email host received the message, but none of those appear to be available options.  Order Received appears to be the closest to what I want (but it has the drawback of changing when the message is moved to another folder).  Is there a solution that hasn't occurred to me?  Could the option to sort by Date Received be added to Thunderbird?

Comment 24

[alta88]

The columnpicker's Received means Date Received...

Comment 25

[seppley]

Then "Received" is probably the field I want to sort by... thanks.  It's awfully terse, though, and googling 'thunderbird folder sort received' didn't help me understand it; can you elaborate a little?  Does it mean the date the email was received by Thunderbird?  Assuming so, does it mean the date when Thunderbird fetched the mail from the IMAP server to my local Inbox folder?  If not, does it mean the date the email arrived at the IMAP server?  Where does Thunderbird find this date, or when does it construct it?

Comment 26

[:aceman]

I have looked at this and also have a test that shows the bug. So I see 2 options here:
1. back out bug 854798 on ESR. Should be safe. I recommend this.
2. finally drop msgkey=offset in mbox and just increment key by 1. May be risky but there is already a precedent that msgs moved by filters already get key+1 so code expecting key==offset should have already been uncovered. However, there are still some unsure places, fixing which means basically bug 793865 (the 64bit envelope and initializing key to offset cleanup). I would not recommend this for ESR.

Comment 27

[Magnus Melin [:mkmelin]]

(In reply to seppley from comment #25
Received is taken from the Received header that servers add once they receive a message. Beware of bug 402594 though :/

Comment 28

[seppley]

Replying to Magnus' comment #27:
> Received is taken from the Received header that servers add
> once they receive a message. Beware of bug 402594 though :/

I read most of the comments in the bug 402594 thread, plus the description of an add-on that partially mitigates 402594.  If I correctly understood what I read, there are actually two bugs: (1) Thunderbird doesn't fetch messages' Received header field from IMAP servers, and (2) when a user sorts by Received, Thunderbird actually sorts the folder by Date (date sent).

The add-on mitigates the former (by somehow getting Thunderbird to pay attention to the Received fields) but doesn't solve Thunderbird's inability to sort by Received.

So, if I understood correctly, it means Alta88's hint that we could sort by Received instead of Order Received won't help.

It's troubling that the two bugs in 402594 persist; it was reported in 2007.  According to comments in the 402594 thread, other email clients don't have the issue, so it shouldn't be that hard to fix.  It's a major bug; it's very important for users to be able to reliably sort by date, and at present Thunderbird has no way to do so.  Sorting by Date Sent is unreliable because it can be spoofed by the sender.  Sorting by Received is totally unreliable due to the 402584 bugs.  Sorting by Order Received is unreliable because it's currently buggy. (Also, even after the bug is fixed, moving messages between folders alters the order.  But I can live with that, so please fix our Order Received bug!)

In addition to pleading for the bugs to be fixed, I propose providing a "global" version of Order Received, that would use a single counter for all folders.  It would indicate the order in which the message was first received into any folder, and wouldn't change when a message is moved from one folder to another.  Would this be hard to implement in Thunderbird?  Assuming it's hard to do for messages stored on an IMAP server, would it be hard to do only for messages stored in local folders?

I also suggest changing the vague labels of some fields in Thunderbird's column picker (and in the column headers when displayed).  Instead of "Date" it should say "Date Sent" (and Thunderbird should warn the user that senders can spoof the date).  Instead of "Received" it should say "Date Received" (and Thunderbird should warn the user it doesn't work due to bugs 402594).  Instead of "Order Received" it should say "Order Added to This Folder" (and Thunderbird should warn the user that moving messages from one folder to another makes them the most recent.)

Comment 29

[WADA:World Anti-bad-Duping Agency]

Aha! I now understand this bug by Blocks:854798, Version:38. Thanks to :aceman for problem analysis.
Mechanism is pretty simple.
  0. Order Received column == messageKey value of the mail
  1. When message is copied/downloaaded to local mail folder, messageOffset==fileSize is set.
     messageOffset value is stil used for messageKey value of the mail.
  2. Many mails are added, and many mails are deleted.
  3. Compaact is executed.
     After change by Bug 854798(released by Tb 38), Compact does not change messageKey of existent mail.
     Compact changes mssageOffset of each mail and fileSize of the folder(smaller than before Compact)
  4. When mail is copied/downloaaded to local mail folder,
     messageOffset==current fileSize is still used as messageKey.
     If many mails are deleted and Compacted, because fileSize is far smaller than messageKey of existent mails,
     "messageKey assigned to the newly added mail" is smaller than messageKey of existent mail.
  5. When Repair Folder is executed, all mails are re-parsed, and messageKey==messageOffset is used.

I thought following change is already made in many place.
  "messageKey of newly added mail in local BerkleyStore folder" == "Highest key in msgDB + 1"
  (This is same as UID/Article number assignment at IMAP/NNTP server)
  Note: If filter move of multiple POP3 mails, following occurs since Tb 12.
        1st moved mail : messageKey==messageOffset==fileSize
        2nd to last moved mail : Highest key in msgDB + 1 (i.e. incremented by one)
"Repair Folder" should assign messageKey of each mail with "starting from 1, incrementing by 1".
Change like this is needed for "Instead of Order Received, it should say Order Added to This Folder".

Is keyword=dataloss appropriate for bug at bugzillaa.mozilla.org?

Comment 30

[:aceman]

(In reply to WADA from comment #29)
> Aha! I now understand this bug by Blocks:854798, Version:38. Thanks to
> :aceman for problem analysis.
> Mechanism is pretty simple.

Yes, your summary is correct.

> Is keyword=dataloss appropriate for bug at bugzillaa.mozilla.org?
I explained this in comment 18. I think in the algorithm you described TB may try to allocate a duplicate key (coming from "below" to already existing keys). And in that case I have not tested what exactly happens.

Comment 31

[WADA:World Anti-bad-Duping Agency]

Because change by bug 854798 is pretty important for many victims of Bug 799450, Bug 766495, Bug 817245, I don't want "immediate backout of bug 854798".
Can "Comact code after bug 854798" be optional?
  BerleyStoreLocalFolder-compact-mode-bypass-Bug799450-Bug766495-Bug817245 = true  => Compact after  bug 854798
  BerleyStoreLocalFolder-compact-mode-bypass-Bug799450-Bug766495-Bug817245 = false => Compact before bug 854798
  Default :
    Before "Stop using messageKey==msgOffset at any place in BerleyStoreLocalFolder" is achieved: false      
    After  "Stop using messageKey==msgOffset at any place in BerleyStoreLocalFolder" is achieved: true
  We can recomend true to many victims of Bug 799450, Bug 766495, Bug 817245,
  with careful explanation about risk of this bug(bug 1183490).
  Because messageKey and messgeOffset is clearly separated by Pluggable Store of Tb 12,
  "what sould be done for messageKey=Highest key in msgDB + 1" itself is not so complicated,
  although it's pretty tough work because of complicated code.

Comment 32

[:aceman]

(In reply to WADA from comment #31)
> Because change by bug 854798 is pretty important for many victims of Bug
> 799450, Bug 766495, Bug 817245, I don't want "immediate backout of bug
> 854798".

I know backing out would return the problem. I just do not see a better solution yet.

> Can "Comact code after bug 854798" be optional?
>   BerleyStoreLocalFolder-compact-mode-bypass-Bug799450-Bug766495-Bug817245 =
> true  => Compact after  bug 854798
>   BerleyStoreLocalFolder-compact-mode-bypass-Bug799450-Bug766495-Bug817245 =
> false => Compact before bug 854798

What do you mean by optional? Who (user/TB) will decide it and how?

> Because messageKey and messgeOffset is clearly separated by Pluggable
> Store of Tb 12,

I fear this is not 100% true yet, see https://bug793865.bmoattachments.org/attachment.cgi?id=8561006, code like "CopyHdrFromExistingHdr(m_envelope_pos, ..." (uses file position instead of/as key).

>   "what sould be done for messageKey=Highest key in msgDB + 1" itself is not
> so complicated,
>   although it's pretty tough work because of complicated code.

Yes, it is some of the code in https://bug793865.bmoattachments.org/attachment.cgi?id=8561006 . And it is your bug 1144020. I think I should split some parts of that attachment from bug 793865 into bug 1144020 so that some non-problematic parts can already be landed.

Comment 33

[WADA:World Anti-bad-Duping Agency]

(In reply to :aceman from comment #32)
> What do you mean by optional? Who (user/TB) will decide it and how?

User can choose "Compact logic before bug 854798 fix"(messageKey==new offset after Compact) and "Compact logic after bug 854798 fix"(messageKey is unchanged by Compact) by ptrfs.js option setting.

About "dataloss".
If "messageKey of an existent mail after Compact" is re-used by message copy which uses messageKey=messageOffset, or by logic of "a known messageKey + 1", key in msgDB for existent mail is replaced by the newly copied message. So, the existent mail disappers at Thread pane.

If "Repair Folder" is executed before Compact is invoked, lost mail is recovered.
If Compact is invoked before "Repair Folder" is executed, the lost mail is permanently/completely lost.
This is same as "broken .msf" case.

These are pretty easily observed by test mails attached to Bug 799450 Comment #10, because size of all crafted 4 mails is 4000 bytes and same.

Comment 34

[WADA:World Anti-bad-Duping Agency]

(In reply to :aceman from comment #32)
> Who (user/TB) will decide it and how?

To victims of Bug 766495, Bug 799450, Bug　817245, we recommend to set true in these bugs.
Detailed description in Release Note is mandatory.

Comment 35

[WADA:World Anti-bad-Duping Agency]

FYI.
I've opened bug 1201782 for mail composition issue even after fix of bug 832519.
"dataloss part of this bug by re-use of existent messageKey by CopyMove" case is involved in that bug.

Comment 36

[WADA:World Anti-bad-Duping Agency]

FYI.
"Compact + Repair Folder" is best and only one recovery procedure from this bug.
But "Compact + Repair Folder while draft editing, forwarding" is a persistent method to generate problem of bug 766495, bug 799450, bug 817245.
This is because:
  "Compact + Repair Folder after fix of bug 817245" is absolutely same as "Compact before fix of bug 817245"

Comment 37

[WADA:World Anti-bad-Duping Agency]

FYI. I've opened bug 1202105 for phenomeno of bug 1201782 comment #4 (re-use/replace of messageKey by CopyMove).

Comment 39

[:aceman]

Rkent, can we get your decision here (comment 26)?
Is it possible to backout on ESR only? Or do we need to do it on trunk too?

Comment 40

[Kent James (:rkent)]

I'll be looking at this soon, hopefully this week. We'll want some resolution for 38.4.0

Comment 41

[Kent James (:rkent)]

Attachment: Detect and fix key collisions

Give me our opinion about this approach. This is intended to fix the most urgent issue for esr38, which is the potential loss of message. If we take this approach, we should probably put this in a new bug, as this does not solve the order received issue which was the original intent of this bug.

You can simulate the data loss problem by hand with these STR:

1) Create a local folder TheBug
2) Copy the same message 5 times into folder TheBug
3) Delete the 2nd and 3rd message in TheBug
4) Compact TheBug
5) Copy a new message into TheBug

Expect: 4 messages in TheBug
Actual: 3 messages in TheBug (the new message does not copy). If you Repair folder TheBug, then the moved message will appear.

Comment 42

[WADA:World Anti-bad-Duping Agency]

(In reply to Kent James (:rkent) from comment #41)
> Detect and fix key collisions

Kent James, thanks for your patch.
I split issue of "Overlay of existent msgKey by Copy/Move" part of this bug to Bug 1202105.
Please propose your patch in that bug.
This bug is mainly for "Sort order by Order Received column after fix of Bug 854798".
Bug 1202105 is relevaant to problem of Bug 1201782.
But this bug is irrelevant to Bug 1201782 if problem of Bug 1202105 is separated from this bug.

Comment 43

[WADA:World Anti-bad-Duping Agency]

(In reply to Kent James (:rkent) from comment #41)
> You can simulate the data loss problem by hand with these STR:

STR of Bug 1202105 is commet #4 of this bug. Size of "all test mails of commet #4 of this bug" = 4000 bytes.
i,e. STR in comment #4 === STR by you.

Comment 44

[:aceman]

Comment on attachment 8666431 [details] [diff] [review]
Detect and fix key collisions

Review of attachment 8666431 [details] [diff] [review]:
-----------------------------------------------------------------

Well, I didn't propose this solution as it isn't perfect:) I can't guarantee that this will work 100% (as some code may expect key=offset, that is why bug 793865 is so complicated), but for the single theoretical message that may get duplicate key, this may be enough as a quick fix.

If you implement the loop I talk about below, then let's move the patch to bug 1202105.

If you use the highest-key solution, it could stay here.

Thanks.

::: mailnews/local/src/nsMsgBrkMBoxStore.cpp
@@ +665,5 @@
> +      // is a collision.
> +      bool hasKey = false;
> +      while (db->ContainsKey(key, &hasKey), hasKey)
> +        key++;
> +    }

In some cases we already generate newkey=old key+1 and then there is a group of successive messages that have keys like (1024,1025,1026). You may hit a spot in this array, so your key++ may be another valid message again. I'd said we need to do a loop here until we find a key that does not exists yet. The ideal solution here would be to get key=max_existing_key+1 and that would also completely solve this bug, but I think the database does not tell us what the highest key is (unless we request all keys and look up the highest key).

::: mailnews/local/src/nsParseMailbox.cpp
@@ +1396,5 @@
> +    // m_envelope_pos is set in nsImapMailFolder::ParseAdoptedHeaderLine to be
> +    // the UID of the message, so that the key can get created as UID. That of
> +    // course is extremely confusing, and we really need to clean that up. We
> +    // really should not conflate the meaning of envelope position, key, and
> +    // UID.

This may be the key why my changes in 793865 are causing problems in IMAP. I tried to remove m_envelope_pos from this place, which may be needed for pop, but not for imap... I can split this part out of my patches and then we can move in bug 793865. Thanks.

Comment 45

[Kent James (:rkent)]

Since this bug is being defined to be the sort order issue rather than the data loss issue, this is no longer a critical esr38 issue (that has been moved to bug 1202105) As for the current bug, what we need to do is to decouple the meaning of "order received" from key. That probably means adding a new field to the database which is order received, which perhaps should be the time when the message was received. Or perhaps we could just use the data column for this instead? We need to investigate how that data column is set.

Comment 47

[Peter]

I have cured this bug for a moment (probably persisting only until the next compacting) by terminating TB, deleting .msf-file, and restarting TB. TB then recreates .msf-file.

What are the drawbacks I didn’t consider?

Comment 48

[WADA:World Anti-bad-Duping Agency]

(In reply to Peter from comment #47)
> What are the drawbacks I didn’t consider?

"Column choice at Thread pane" is saved in xxx.msf file. So if you delete .msf file, it's lost.
To force Re-indexing/re-creation of .msf from scratch with iheriting some data, Folder Propertes/"Repair Folder" is provided. This is not only due to ".msf is frequently broken in Tb" but also due to "in edge case, mail data is appended to msgStore file without keeping consistency of .msf file"(this is current design/implementation). So, "Repair Folder" is needed for edge case, and it's pretty useful for us in "frequent broken .msf" case :-)

"Delete .msf" is never officially supported although it's well known as a last resort. And, when .msf is deleted by user, .msf is recreated from absolute scratch as desined/implemented.

Comment 49

[Kent James (:rkent)]

Attachment: Part 1, Remove QueryInterface from PromiseTestUtils wrapped

Comment 50

[Kent James (:rkent)]

Attachment: Part 2, use PromiseTestUtils in test_folderCompact

Comment 51

[Kent James (:rkent)]

Attachment: part 3, Remove dependency on offset in creating message keys

(This patch assumes that the patch in bug 1202105 lands first)

Much of the patch concerns test cleanup.

Adding the IMAP ability to set key is a temporary measure. Those will be replaced eventually by some method of setting a database property serverToken that will be a string representation of the server's access ID for the message. In IMAP's case, that will be UID. In EWS it is the message ID. Most server stores have the concept of some sort of unique ID to access an item, and we need to store those locally with the message (and not conflate that with messageKey).

Comment 52

[seppley]

(In reply to Kent James (:rkent) from comment #51)
-snip-
> Most server stores have the concept of some sort of unique ID to access
> an item, and we need to store those locally with the message
-snip-

I hope you're not planning to rely on a value that's unique at some server to also be unique elsewhere.  A user might set Thunderbird to move messages from two or more servers into the same local folder (because the user can have more than one email account and prefers to combine their incoming mail into one inbox folder, for example).

It's nice to see progress is being made on the bug.  Thanks!

Comment 53

[WADA:World Anti-bad-Duping Agency]

(In reply to Kent James (:rkent) from comment #51)
> In IMAP's case, that will be UID. In EWS it is the message ID.

Are you worryng about "IMAP server who doesn't support UID"?
Does "IMAP server who doesn't support UID" actually exist?

Comment 54

[:aceman]

Comment on attachment 8670653 [details] [diff] [review]
Part 2, use PromiseTestUtils in test_folderCompact

Review of attachment 8670653 [details] [diff] [review]:
-----------------------------------------------------------------

Sorry, I do not yet understand this JS stuff.

Comment 55

[:aceman]

Comment on attachment 8670652 [details] [diff] [review]
Part 1, Remove QueryInterface from PromiseTestUtils wrapped

Review of attachment 8670652 [details] [diff] [review]:
-----------------------------------------------------------------

The same here.

Comment 56

[WADA:World Anti-bad-Duping Agency]

Comment on attachment 8670655 [details] [diff] [review]
part 3, Remove dependency on offset in creating message keys

Review of attachment 8670655 [details] [diff] [review]:
-----------------------------------------------------------------

If phantom mail of size=0(no corresponding data in BerkleyStore msgStore file) is generated by problem(bug) in some codes, if current logic(use messaageKey=messaageOffset), it's currently masked by "resuse of messageKey=messageOffset".
This surely occurred in my tests in the past.
If your patch will be landed, such phantom mail will be exposed to many Tb users.
No need to care such special/exceptional  case?

Comment 57

[Kent James (:rkent)]

(In reply to seppley from comment #52)
> (In reply to Kent James (:rkent) from comment #51)
> -snip-
> > Most server stores have the concept of some sort of unique ID to access
> > an item, and we need to store those locally with the message
> -snip-
> 
> I hope you're not planning to rely on a value that's unique at some server
> to also be unique elsewhere.  A user might set Thunderbird to move messages
> from two or more servers into the same local folder (because the user can
> have more than one email account and prefers to combine their incoming mail
> into one inbox folder, for example).
> 
> It's nice to see progress is being made on the bug.  Thanks!

Although this is not really the place to be discussing a future serverToken, once a message is moved or copied into a local folder, then the "server" for that message becomes the local folder, and the serverToken value is meaningless (or to look at it another way, the serverToken becomes the same as the storeToken). The serverToken is whatever string is necessary to uniquely access a message in its server (or mailbox) location. If that location changes, then the serverToken would change.

The point is that this is more general than just IMAP UID, and that we should not conflate its meaning with other things like messageKey.

Comment 58

[Kent James (:rkent)]

(In reply to WADA from comment #53)
> (In reply to Kent James (:rkent) from comment #51)
> > In IMAP's case, that will be UID. In EWS it is the message ID.
> 
> Are you worryng about "IMAP server who doesn't support UID"?
> Does "IMAP server who doesn't support UID" actually exist?

Sorry, I don't understand the question. All I am assuming is that server will always have some way to uniquely access an item, and gave two examples of that.

Comment 59

[Kent James (:rkent)]

(In reply to WADA from comment #56)
> Comment on attachment 8670655 [details] [diff] [review]
> part 3, Remove dependency on offset in creating message keys
> 
> Review of attachment 8670655 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> If phantom mail of size=0(no corresponding data in BerkleyStore msgStore
> file) is generated by problem(bug) in some codes, if current logic(use
> messaageKey=messaageOffset), it's currently masked by "resuse of
> messageKey=messageOffset".
> This surely occurred in my tests in the past.
> If your patch will be landed, such phantom mail will be exposed to many Tb
> users.
> No need to care such special/exceptional  case?

If we could be absolutely sure that there was some way to detect this phantom message, then it might be possible to block it. The problem is that you need to not accidentally block a real message (including bugs affecting real messages, such as setting the size=0 inadvertently). I doubt if the possible advantages of blocking some phantom messages is worth the risk of losing a real message.

Comment 60

[WADA:World Anti-bad-Duping Agency]

Comment on attachment 8670655 [details] [diff] [review]
part 3, Remove dependency on offset in creating message keys

Review of attachment 8670655 [details] [diff] [review]:
-----------------------------------------------------------------

When key=nsMsgKey_None is used, how/when HighestKey+1 is generated?
In multi-cpu/multi-task environment, is "generation of HighestKey+1" serialized?

"bulk move to FolderX" * N and "filter move upon download" may occur at same time.
If multiple "generation of HighestKey+1" are executed at multi-cpu concurrently, duplicate key may occur.
If key=Offset, no duplicate key is guranteed by file lock like one in "append data to msgStore file".

Comment 61

[Kent James (:rkent)]

"how/when HighestKey+1 is generated?"

This all happens in Mork, which is all main thread only. There should not be any contention issues.

Comment 62

[Magnus Melin [:mkmelin]]

Comment on attachment 8670653 [details] [diff] [review]
Part 2, use PromiseTestUtils in test_folderCompact

Review of attachment 8670653 [details] [diff] [review]:
-----------------------------------------------------------------

LGTM, sorry for the delay

Comment 63

[Wayne Mery (:wsmwk)]

(In reply to Magnus Melin from comment #62)
> Comment on attachment 8670653 [details] [diff] [review]
> Part 2, use PromiseTestUtils in test_folderCompact
> ...
> LGTM, sorry for the delay

so now ready for checkin?

Comment 64

[:aceman]

(In reply to Wayne Mery (:wsmwk, use Needinfo for questions) from comment #63)
> > LGTM, sorry for the delay
> 
> so now ready for checkin?

Depends on whether those test changes are independent (will work) also without landing the main backend logic change in part 3. Magnus has not reviewed that part, which is OK as I plan to do it (probably next week).

Comment 65

[:aceman]

Comment on attachment 8670655 [details] [diff] [review]
part 3, Remove dependency on offset in creating message keys

Review of attachment 8670655 [details] [diff] [review]:
-----------------------------------------------------------------

Nice, you seem to have solved the IMAP problem I had remaining in bug 793865.

There are 2 places of bitrot in 2 of the 3 patches.

I noticed when you rebuild a folder, the first key gets assigned as 1. Previously we had 0 as the lowest key (as that was the first offset). I am not yet sure if that is a problem.

Otherwise this looks good and does mostly the same as I had in bug bug 793865 (even the 2GB test change) in the area of splitting the offset and key. Once you land this, I'll be able to continue in that bug with a much reduced patch.

Thanks.

::: mailnews/base/test/unit/test_folderCompact.js
@@ +271,5 @@
> +    do_check_eq(preInboxMsg3Key, postInboxMsg3Key);
> +
> +    // For folder3, which was rebuilt, keys change but all messages should exist.
> +    do_check_true(gLocalFolder2.msgDatabase.getMsgHdrForMessageID(gMsg2ID));
> +    do_check_true(gLocalFolder2.msgDatabase.getMsgHdrForMessageID(gMsg3ID));

Can you add a test for a folder rebuild where keys get renumbered? I had that in bug 793865 and I do not see it here.

::: mailnews/local/src/nsParseMailbox.cpp
@@ +1405,3 @@
>      // the UID of the message, so that the key can get created as UID. That of
>      // course is extremely confusing, and we really need to clean that up. We
>      // really should not conflate the meaning of envelope position, key, and

Is this comment still valid, or have you cleaned up the confusion right now?

@@ +1411,5 @@
>                  oldHeader, false, getter_AddRefs(m_newMsgHdr));
>      else if (!m_newMsgHdr)
>      {
>        // Should assert that this is not a local message
> +      ret = m_mailDB->CreateNewHdr(m_new_key, getter_AddRefs(m_newMsgHdr));

Should we set m_newMsgHdr->SetMessageOffset(m_envelope_pos) here or is that done elsewhere?

Comment 66

[WADA:World Anti-bad-Duping Agency]

FYI.

(In reply to :aceman from comment #65)
> I noticed when you rebuild a folder, the first key gets assigned as 1.
> Previously we had 0 as the lowest key (as that was the first offset). I am
> not yet sure if that is a problem.

Following problem currently occurs due to messaageKey=messageOffset=0 in IMAP folder.
- When newly created IMAP folder and no message in the IMAP folder and OffflineStore file is compacted,
  while WorkOffline mode, copy mails to this IMAP folder
  => first message has messaageKey=messageOffset=0. (-0 === +0 === 0)
- Go Work Online
  => because messaageKey=0 === MSGID=0 in IMAP which never happens in IMAP,
     the mail of messaageKey=messageOffset=0 is not removed by re-sync with server.
- Repair Folder is needed to remove the mail of messaageKey=0 === MSGID=0.

This funny problem in edge case will be resolved if messageKey starts from 1,
(-1 is perhaps used as faked key while Offline mode)

Comment 67

[Kent James (:rkent)]

NI myself to get this landed.

Comment 68

[:aceman]

This also radically moves forward the 4GB+ mbox folders.

Comment 69

[Kent James (:rkent)]

I fixed the requests from Aceman to test changed key, and pushed.

"Is this comment still valid, or have you cleaned up the confusion right now?"

Yes it is.

"Should we set m_newMsgHdr->SetMessageOffset(m_envelope_pos) here or is that done elsewhere?"

It is done elsewhere.

I did try runs with and without these patches, and saw no difference in the test failures.

http://hg.mozilla.org/comm-central/rev/82e9b4739973
http://hg.mozilla.org/comm-central/rev/944449395c02
http://hg.mozilla.org/comm-central/rev/4d8d5d6eecfb