Last Comment Bug 812923 - Dragging a huge number of messages onto a folder freezes TB even BEFORE dropping
: Dragging a huge number of messages onto a folder freezes TB even BEFORE dropping
Status: RESOLVED FIXED
[bulkoperations]
: hang, perf
Product: Thunderbird
Classification: Client Software
Component: Folder and Message Lists (show other bugs)
: 16 Branch
: All All
: -- major (vote)
: Thunderbird 24.0
Assigned To: :aceman
:
Mentors:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2012-11-18 14:13 PST by matteo sisti sette
Modified: 2013-06-26 09:42 PDT (History)
7 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---


Attachments
patch (6.57 KB, patch)
2013-03-04 12:12 PST, :aceman
mconley: review-
Details | Diff | Splinter Review
patch v2 (4.52 KB, patch)
2013-04-29 10:37 PDT, :aceman
mconley: review+
Details | Diff | Splinter Review
patch v3 (4.52 KB, patch)
2013-05-19 05:56 PDT, :aceman
acelists: review+
Details | Diff | Splinter Review

Description matteo sisti sette 2012-11-18 14:13:04 PST
User Agent: Mozilla/5.0 (X11; Linux i686) AppleWebKit/537.11 (KHTML, like Gecko) Chrome/23.0.1271.64 Safari/537.11

Steps to reproduce:

Selected all the messages in a folder (about 20,000 small messages).
Clicked and dragged onto another folder (in Local Folders), but I still DIDN'T DROP them, I was still holding the button down


Actual results:

Right when I got the cursor over the target folder, and far before I even thought about releasing the button and dropping the message, TB began to "think" and became unresponsive, to the point that the popup appeared saying that a script was making the application unresponsive (I still hadn't released the button).


Expected results:

Merely dragging a group of messages, no matter how many, shouldn't be an expensive operation. You are just collecting an ORDER ("I'm gonna ask you to move these message to......"). The hard work starts when you drop the message and the order has to be executed - i.e., copying 20k message _can_ be expensive, but dragging and dropping to just _request_ (even _preparing_ to request!!) to copy N messages must be O(1).
Comment 1 matteo sisti sette 2012-11-18 16:42:23 PST
It's 100% systematic.

- Enter a folder (subfolder of Inbox) that has thousands of messages 
- Select a few thousand messages, e.g. 3000
- Click and drag them onto an empty folder in Local Folders, DON'T DROP, just drag

=> As soon as your cursor gets over the target folder, TB freezes and starts consuming 100% CPU.

Shortly the popup "a script is making the page unresponsive" will popup. 

Don't release the mouse button. Using the keyboard, check the "don't ask again" option and Click on Continue
(or, release the mouse button and normally click on Continue)

=> TB will freeze forever with the Continue button pressed and will keep consuming 100% CPU.

After ONE HOUR consuming 100% CPU, I kill it and it hasn't copied even one single message.

Something must be exploding exponentially at the very moment it starts considering the idea of copying the messages to a given folder.
Comment 2 matteo sisti sette 2012-11-18 16:45:28 PST
As little as 800 messages is enough to make the window fade to grayand become unresponsive, but then it recovers and copies them succesfully.
Maybe the problem comes when the "busy script" dialog pops up. Maybe that very popup interferes...
Comment 3 matteo sisti sette 2012-11-18 16:52:37 PST
(In reply to matteo sisti sette from comment #2)
> Maybe the problem comes when the "busy script" dialog pops up. Maybe that
> very popup interferes...

No, that's not the case. I just tried with a little more than 800, the "busy script" popup came out (_before_ I dropped), so I hit "continue" without ever releasing the mouse, and after a few seconds I could go on and drop the messages, and they were moved.

So it's just some unnecessary processing that goes on when you hover a potential target folder, and is (and obviously shouldn't be) increasing with the number of selected messages.
Comment 4 Wayne Mery (:wsmwk, NI for questions) 2013-01-22 15:12:09 PST
duplicate of bug 583365?
(I"m not sure I found the bug I wanted)
Comment 5 Wayne Mery (:wsmwk, NI for questions) 2013-02-18 11:47:41 PST
(In reply to Wayne Mery (:wsmwk) from comment #4)
> duplicate of bug 583365?

matteo, what do you think?
Comment 6 matteo sisti sette 2013-03-03 08:39:09 PST
I don't think it's an exact duplicate. I think what I describe is a huge processing time (CPU), not a memory leak or memory outage (btw that issue is titled "memory leak" but it seems to describe an excessive usage of memory, not an actual leak) an anyway not crash in my case.

However they may be two aspects of the same underlying issue: a ridiculously wrong design in the way operations on a bunch of messages are managed.

Actually EVERYTHING in TB is designed without taking into account what happens when you may have many messages. Even operations on a single message can become slow if you just _have_ many messages in your inbox (another bug). And moreover, when TB is busy doing these things, the UI is blocked (another bug).
Comment 7 matteo sisti sette 2013-03-03 08:40:07 PST
Not being able to edit comments is SO annoying
Comment 8 :aceman 2013-03-03 12:28:51 PST
Can you paste which file+line does the Unresponsive script dialog mention?
Is it chrome://messenger/content/msgMail3PaneWindow.js:1346 ?

While there is a canDrop function in folderPane.js that really is executed for each folder you drag the mouse over (even without releasing) and that one iterates over all messages being dragged to see if they are allowed to be pasted into that folder, I couldn't not see it take significant time.
Comment 9 :aceman 2013-03-03 14:54:39 PST
I can see a similar problem as the reporter sees. I have a tentative patch ready, I just need more info from the reporter if I see the same as him.

matteo, do many of the dragged messages have the same subject?
Comment 10 Wayne Mery (:wsmwk, NI for questions) 2013-03-03 15:45:06 PST
I can reproduce this with 35,000 messages of varied subjects. I do not get unresponsive script. I just chugs CPU.

I could not reproduce with 17,000 messages.
Comment 11 :aceman 2013-03-03 15:54:25 PST
You may have a good CPU, disabled unresponsive script warnings or your messages have unique subjects.
Comment 12 :aceman 2013-03-03 15:55:31 PST
Wayne, does it use CPU as soon as you start dragging (e.g. going down from the message list), or only after you move over some folder (in the left pane)?
Comment 13 matteo sisti sette 2013-03-03 16:22:10 PST
@:aceman, I'm pretty sure when I observed this all the messages had very similar subjects, not sure whether the exact same subject or not. Sounds crazy that that matters.
I'll try to see if I can test it again now; I don't seem to remember it mentioned a particular line of code at all, but I'll look at it.
(calling a function on _every_ selected message when you rollover a folder is wrong, no matter how little time the function consumes!!! you may have selected millions of messages)
Comment 14 matteo sisti sette 2013-03-03 16:34:53 PST
I've tried now with 7000 messages, yes all with the same subject. TB is consuming 100% CPU, has been for minutes already but the popup doesn't show up. I guess the unsersponsive script warning has been disabled for some reason (or the time limit increased to an unreasonable value) - i ceratainly didn't disable it.

Your question about the subject being the same scares me. I hope you are not implying the subject is somehow used to identify messages so that a O(N) operation (already too much) becomes even O(N^2) because for each message all messages are checked, or something like that ..... no I must be speaking nonsense, that would be crazy.
Comment 15 matteo sisti sette 2013-03-03 16:35:36 PST
How yo I check whether the nonresponsive-script warning is enabled?
Comment 16 Wayne Mery (:wsmwk, NI for questions) 2013-03-03 16:55:50 PST
I tested using local folders. high cpu starts when drag is started and ends after 5-6 minutes - UI is hung with "(Not Responding)" in windows title bar. no mouse over folder nor drop attempt needed.   

Indeed I had disabled script warnings for some testing. With dom.max_chrome_script_run_time non-zero I get Unresponsive Script.

The performance bugs about long threads are in http://tinyurl.com/ajnja9d

perhaps bug 846123 is dupe?
Comment 17 :aceman 2013-03-03 23:54:24 PST
(In reply to matteo sisti sette from comment #14)
> Your question about the subject being the same scares me. I hope you are not
> implying the subject is somehow used to identify messages so that a O(N)
> operation (already too much) becomes even O(N^2) because for each message
> all messages are checked, or something like that ..... no I must be speaking
> nonsense, that would be crazy.

No, the subject is not used to identify messages, but as soon as you start dragging the subject of each message is used to generate a unique filename IN CASE YOU EVENTUALLY drop it onto the OS desktop.
This is the current dnd architecture and I am not knowledgeable enough to rework that. And the current code actually did this in O(n^3) + a potentially expensive regex in the second inner level of the loop :(

With help from squib, we could optimize the loop a bit to O(n^2) and with the regex only at the top level when generating all the filenames. And as TB actually does not support dragging multiple messages onto desktop, the name generation is useless. So the loop got O(n) to just generate what is needed for drag inside TB.

So it looks like we see the same problem, fortunately. I upload the patch shortly. For me it reduces the time of 100% CPU to 15 seconds on 18000 messages (most with the same subject). With the new approach, it does not matter anymore if the subjects are the same.
Comment 18 :aceman 2013-03-03 23:54:56 PST
(In reply to matteo sisti sette from comment #15)
> How yo I check whether the nonresponsive-script warning is enabled?

See the pref dom.max_chrome_script_run_time in Options->Advanced->Config editor.
Comment 19 :aceman 2013-03-03 23:59:07 PST
(In reply to Wayne Mery (:wsmwk) from comment #16)
> perhaps bug 846123 is dupe?

This bug is only specific to drag and drop, is not IMAP specific and does not relate to copy/move via the context menu. Unless proven otherwise :)
Comment 20 WADA 2013-03-04 01:34:22 PST
(In reply to matteo sisti sette from comment #14)
> I hope you are not implying the subject is somehow used to identify messages
> so that a O(N) operation (already too much) becomes even O(N^2)
> because for each message all messages are checked, or something like that .....

Drag events in XUL.
> https://developer.mozilla.org/en-US/docs/DragDrop/Drag_and_Drop
> https://developer.mozilla.org/en-US/docs/XUL/Events

TreeChildren of threadTree
> http://mxr.mozilla.org/comm-central/source/mail/base/content/messenger.xul#482
> 482                     <treechildren ondraggesture="ThreadPaneOnDragStart(event);"
> 483                                   ondragover="ThreadPaneOnDragOver(event);"
> 484                                   ondrop="ThreadPaneOnDrop(event);"/>
> http://mxr.mozilla.org/comm-central/source/mail/base/content/msgMail3PaneWindow.js#1296
> 1296 function ThreadPaneOnDragStart(aEvent) {
> Set data array of msgDBHeader object of all selected messages in aEvent.dataTransfer propperty by aEvent.dataTransfer.mozSetDataAt(,messages[i],i)
> set myself in aEvent.dataTransfer property by aEvent.dataTransfer.addElement(aEvent.originalTarget)

folderTree
> http://mxr.mozilla.org/comm-central/source/mail/base/content/messenger.xul#350
> 350               <tree id="folderTree" class="plain" flex="1"
> 355                     ondraggesture="gFolderTreeView._onDragStart(event);"
> 356                     ondragover="gFolderTreeView._onDragOver(event);"
> 357                     ondblclick="gFolderTreeView.onDoubleClick(event);"
> 358                     onselect="FolderPaneSelectionChange();">
_onDragOver
> http://mxr.mozilla.org/comm-central/source/mail/base/content/folderPane.js#708
> 708   _onDragOver: function ftv_onDragOver(aEvent) {
> 709     this._currentTransfer = aEvent.dataTransfer;
> 710   },
> This is saving of passed aEvent.dataTransfer object in this treechildren object(==folder to which Drop may occur)
> When ondragdrop is kicked, it's perhaps notified to object where dragstart happened. 

Because "ondragstart" is for each treechildren of threadTree(==each selected message), "dragstart event is kicked at which selected message" may be unpredictable, or ondragstart may be invoked at multiple treechildrens.

aEvent.dataTransfer.mozSetDataAt(,messages[i],i) for 20,000 message is not so light job, but I guess it's not so different from for{Obj[Obj.length]=messages[i]} of 20,000 messages.
I suspect "ondragstart event at multiple treechildren of threadPane" like one.

Another concern.
When mouse stays at folder in folder pane after dragstart, ondragover, ondrag etc. may happen because human being can't keep absolutely same x & y. And, "holding down moouse button for long time by human being" may produce "mouseup event". This kind of unexpected mouse event may be relevant.
Comment 21 :aceman 2013-03-04 01:51:44 PST
(In reply to WADA from comment #20)
> > http://mxr.mozilla.org/comm-central/source/mail/base/content/msgMail3PaneWindow.js#1296
> > 1296 function ThreadPaneOnDragStart(aEvent) {
> > Set data array of msgDBHeader object of all selected messages in aEvent.dataTransfer propperty by aEvent.dataTransfer.mozSetDataAt(,messages[i],i)
> > set myself in aEvent.dataTransfer property by aEvent.dataTransfer.addElement(aEvent.originalTarget)

Yes, this is the spot I have optimized, as we identified the hang is at start of the drag. The bottleneck is actually the suggestUniqueFileName() function there, that is O(n^2) regexes.

If it would be at mouse over a folder, then there is canDrop function in folderPane.js. But I have seen that one is fast enough even though it checks properties of all dragged messages over each folder being moused-over.
Comment 22 matteo sisti sette 2013-03-04 03:11:01 PST
Oh my god.

Merely selecting a bunch of messages (AT LEAST if you select them with shift+click so it's from this to that message) and STARTING to grag MUST be O(1) Neither O(n2) nor O(n) is acceptable. Ony when you eventually drop them should it start actually processing the message and hence a O(n) is inevitable (but anything above it is unacceptable).

The only information being generated when you select and start to drag a bunch of messages should be "Start dragging messages from N to M", no matter what.

IF you select individual messages (e.g. with ctrl+click, and/or ctrl+shift+click) then the information about the selection can be built click by click, and it should be a O(1) for each click (you build a selection that says "From message X to message Y, plus message Z, plus message P, plus messages from M to N..." and each click adds one of these tokens). There's no need to do any actual copying or processing of messages until you drop them!!!

I have to start looking for an anternative MUA immediately.
Comment 23 :aceman 2013-03-04 03:22:18 PST
(In reply to matteo sisti sette from comment #22)
> IF you select individual messages (e.g. with ctrl+click, and/or
> ctrl+shift+click) then the information about the selection can be built
> click by click, and it should be a O(1) for each click (you build a
> selection that says "From message X to message Y, plus message Z, plus
> message P, plus messages from M to N..." and each click adds one of these
> tokens). There's no need to do any actual copying or processing of messages
> until you drop them!!!
Yes I agree, this needs rearchitecting. You could join us to do it.

Meanwhile you can use operations that are more strict and well defined, e.g. use Move to, Copy to in the context menu. In that case TB knows that you want to copy/move inside TB and does not need to do work "just in case".
Comment 24 matteo sisti sette 2013-03-04 03:34:27 PST
(In reply to :aceman from comment #23)
> Yes I agree, this needs rearchitecting. You could join us to do it.
Wish I could, but I have no skills in c++

> Meanwhile you can use operations that are more strict and well defined, e.g.
> use Move to, Copy to in the context menu. In that case TB knows that you
> want to copy/move inside TB and does not need to do work "just in case".
Cool! Good workaround, didn't know that
Comment 25 matteo sisti sette 2013-03-04 08:09:26 PST
No, sorry, actually the workaround doesn't work at all.

Even before you try to drag anything, MERELY SELECTING many messages hangs TB for several seconds with 100%CPU!! (though more messages are needed to trigger this than by dragging).
You need to select messages even in order to use context menu operations.

I guess this is because it has to generate that list of messages which appears below, in the window where usually the content of a single selected message appears. That is something completely useless as it contains the exact same information you already see in the window above (where you select the messages), plus the total number of message which you already have in the status bar, so this could be omitted completely.
Comment 26 matteo sisti sette 2013-03-04 08:10:13 PST
(well the workaround somewhat _reduces_ the problem, as i said, but it doesn't eliminate it)
Comment 27 Wayne Mery (:wsmwk, NI for questions) 2013-03-04 08:26:03 PST
I disagree.  The mere selection causes memory growth and modest CPU, but nothing like the CPU usage at start of drag.  These are *two* distinct issues. And the workaround should definitely avoid the worst of the two
Comment 28 matteo sisti sette 2013-03-04 09:03:46 PST
Yes they are two distinct issues. However the mere selection DOES cause huge cpu load.

And I'm not certain about which one is the worst of the two, since when I tried to merely select a few thousand messages (prior to my last comment) TB crashed and now i can't launch it any more because MY WHOLE PROFILE GOT CORRUPT.
Comment 29 Wayne Mery (:wsmwk, NI for questions) 2013-03-04 11:06:16 PST
(In reply to matteo sisti sette from comment #28)
> Yes they are two distinct issues. However the mere selection DOES cause huge cpu load.

agreed. but, based on your initial comment 0 (not your other bug from today) a few seconds compared to a few minutes is a non-trivial difference.


> And I'm not certain about which one is the worst of the two, since when I
> tried to merely select a few thousand messages (prior to my last comment) TB
> crashed and now i can't launch it any more because MY WHOLE PROFILE GOT
> CORRUPT.

is one of our memories faulty?  bug 847455 reads "many hundreds thousands messages", not a few thousand. :)

regardless, I think it will be helpful to keep discussion of bug 847455 in *that* bug, and discussion of what is reproducible of your original issue in *this* bug.
Comment 30 :aceman 2013-03-04 12:12:13 PST
Created attachment 720835 [details] [diff] [review]
patch

The promised patch.
Comment 31 :aceman 2013-03-04 12:17:33 PST
(In reply to matteo sisti sette from comment #28)
> Yes they are two distinct issues. However the mere selection DOES cause huge
> cpu load.
> 
> And I'm not certain about which one is the worst of the two, since when I
> tried to merely select a few thousand messages (prior to my last comment) TB
> crashed and now i can't launch it any more because MY WHOLE PROFILE GOT
> CORRUPT.

To disable the summary of the selection in the message pane, toggle the pref mail.operate_on_msgs_in_collapsed_threads .
Comment 32 WADA 2013-03-04 17:23:30 PST
(In reply to :aceman from comment #21)
> The bottleneck is actually the suggestUniqueFileName() function there, that is O(n^2) regexes.

I should have looked the function...

For your future "Drag&Drop to Desktop" support.
Responsibility of uniequness check can be trasferred to "indexing of Object property".
  // Same logic as current, except duplication check step
  Seed is Array. Filenames is array
  var NameTable={};
  for(var n=0;n<Seed.length;n++){
    var name; Generate name for Seed[n];
    while(NameTable[name]){ name=name+"-"n; } // duplication check by Object
    NameTable[name]=name or true or anything else;
    Filenames[Filenames.length]=name;
  }
Because n is unique in any for loop step, maximum execution count of while == Seed.length. So, O(2*n).
I believe following can be accepted.
  n=P : subjectX => subjectX
    |
  n=Q : subjectX => subjectX-Q  instead of current subjectX-1
    |
  n=R : subjectX => subjectX-R  instead of current subjectX-2

If subject-1 instead of subject-Q is needed, logic like following is usable.
  Seed is Array.
  var XX="\n\t\r...";  // name!=XX, name+suffix!=XX is garanteed
  var NameTable={};
  var UniequeName={}; UniequeName[XX]=0;
  for(var n=0;n<Seed.length;n++){
    var name; Generate name for Seed[n];
    var nameX=name; // save name from seed
    if( !NameTable[name] ) // name is unieque
    { NameTable[name]={}; NameTable[name][XX]=0; NameTable[name][name]=name; }
    else{ // same name, and suffix is increased, so "name + suffix" is unieque
      NameTable[nameX][XX]++; 
      name=name+"-"+NameTable[nameX][XX];
      NameTable[nameX][name]=name;
    }
    while( UniequeName[name] )
    // unfortunately, suffixed name is used for other Seed[m].
    // this usually means name generation logic from Seed is not so good...
    { UniequeName[XX]++; name=name+"-"+UniequeName[XX]; }
    UniequeName[name]=name;
  }
This is still O(2*n) instead of O(n^2)
Comment 33 Jim Porter (:squib) 2013-04-08 00:08:07 PDT
Comment on attachment 720835 [details] [diff] [review]
patch

Unfortunately, I don't think I'm going to have time to do a proper review of this soon, as Gaia email stuff has been extremely hectic. Sorry about that!
Comment 34 :aceman 2013-04-08 00:16:53 PDT
Can you recommend any other reviewer?
Comment 35 Jim Porter (:squib) 2013-04-08 00:20:07 PDT
mconley or bwinton probably know enough about this code to take a look...
Comment 36 :aceman 2013-04-08 00:37:47 PDT
Comment on attachment 720835 [details] [diff] [review]
patch

The changes in mail/base/content/folderPane.js are just debugging info that will go away.
Comment 37 WADA 2013-04-08 08:45:48 PDT
Comment on attachment 720835 [details] [diff] [review]
patch

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

Many OS has feature for "unique temporary/random file name in a directory" and many of programming languge has fuction to generate random value. What is reason not to utilize such features to generate "unique file name in a directory"? Is sequential N in suffix of "-N" so important in Tb?
Comment 38 :aceman 2013-04-08 08:55:48 PDT
1. Reaching down to the OS/C function may be slower than just doing it in our JS loop.
2. The files are not yet created so the OS/C function does not now about them and will not prevent collisions. Calling that function 1000x does produce 1000 random/temporary file names, but they are not guaranteed to be unique. The function has no set of names to check for uniqueness.

Do I miss anything?
Comment 39 WADA 2013-04-08 16:57:40 PDT
(In reply to :aceman from comment #38)
> 1. Reaching down to the OS/C function may be slower than just doing it in our JS loop.
> 2. The files are not yet created so the OS/C function does not now
> about them and will not prevent collisions.

(A) I think code like next is sufficient for unique file name.
> seed="abc-XXXXXX";for(nn=1;nn<count;nn++){ flag=true; while(true==flag){nm=mktemp(seed); set flag=false and Create file named nm if not-exists, and break;else continue to re-acquire new nm;} }
> http://linux.die.net/man/3/mktemp

(B) Test result of following Do_Test function by JavaScript for unique number generation.
  Count =  10000
  Elapsed = 13 msec
  Count = 100000
  Elapsed = 143 msec
I believe this is far better than Bug 389132, and I guess similar inefficiency to Bug 389132 is perhaps exposed by loop like your JS loop.
I think "Probability of collision with existent file name" is far smaller than "creation of '-9999' when '-1' to '-9998' already exists", as far as length of random string part is not so small.
Or, is your "JS loop" simply generates "-1" to "-NNNNNN" at once always?
No "search from '-1' to '-XX'" for every generation of "-(XX+nn) where nn=1 to PP"?

> function Do_Test()
> {
> var debug=document.getElementById("debug1") ; debug.innerHTML = "" ;
> var cnt= 10000; var range=0; var random_array=new Array(); var T1=new Date(); Gen_Unieque(cnt,range,random_array); var T2=new Date(); Put_Rep(debug,cnt,T1,T2);
> var cnt=100000; var range=0; var random_array=new Array(); var T1=new Date(); Gen_Unieque(cnt,range,random_array); var T2=new Date(); Put_Rep(debug,cnt,T1,T2);
> }
> function Gen_Unieque(cnt,range,random_array)
> {
>    var abs_range;if(0<=range){abs_range=range;}else if(range<0){abs_range=0-range;}else{abs_range=0;}
>    var max;if(abs_range<cnt*10){max=cnt*10;}else{max=abs_range;}
>    var avoid_loop=max*100;
>    var tbl={};
>    for(var xx=0; random_array.length<cnt && xx<avoid_loop; xx++)
>    { 
>        var dat = Math.floor(1+Math.random()*max) ;
>        if( tbl[dat] ){ continue; } // ignore duplicate number
>        tbl[dat] = true ;
>        random_array[random_array.length] = dat ;
>    }
> }
> function Put_Rep(debug,cnt,T1,T2)
> {
>    debug.innerHTML += "<"+"HR>Count = " + cnt ;
>    debug.innerHTML += "<"+"BR>Elapsed = " + ( T2.getMilliseconds() - T1.getMilliseconds() ) + " msec" ;
> }
Comment 40 WADA 2013-04-08 19:07:34 PDT
mkstemp(or mkstemps) may be better for our purpose, because it creates file and opens it.
> http://linux.die.net/man/3/mkstemp
> Porting of mkstemp to Win
>  http://www.suacommunity.com/dictionary/mkstemp-entry.php
Comment 41 WADA 2013-04-08 21:12:31 PDT
If cause of performance issue is similar to bug 389132, and if random number only is not so appropriate for file name, I think following is acceptable.
- Try "file name without suffix by current logic" first.
  If no collision, no problem.
- As file name length has limitation, use shorter one as TemplateBase.
  If longer than 64 unicode chars,
    TemplateBase=First 32 unicode chars + "..." + Last 31 unicode chars
  Request create of TemplateBase + ".eml"
  If TemplateBase + ".eml" doesn't produces collision, no problem.
- TemplateBase = TemplateBase + "-yyyy-mm-dd-hh-mm-ss."
  Template = TemplateBase + "XXXXXX.eml";
    Millisec like part is not numeric, but users perhaps don't mind :-) 
  If it excceds file path length lmit, shorten TemplateBase.
  FileHandle=mkstemps(Template,4);
  If it produces collision, try other TemplateBase several times.
    "..." part => "@", "_", "$", etc.
    First 32 char => First 32-n char, Last 31+n chars
  If collision count exceeds limit, add suffix, as currently done.
- Close file, and change permission if required.
Because probability of "collision even via mkstemps" is pretty low in acual environment usually, above is virtually O(n) always.
Comment 42 WADA 2013-04-08 21:47:13 PDT
Another way, if all file name is generated at once before file creation, and if serial number is needed for suffix value.
  Duplication check by JavaScript interpreter if JS code,
  instead of "check from '-1' to '-NNNNNN' for each NNNNNN by own code".
> var dupchk={}; var suffix={}; var UniqueName=new Array();
> for(index=0;index<ObjArray.length;index++){
> var filenm = ObjArray[index][FieldNameWhichContainsRequiredName];
> if(!dupchk[filenm]){dupchk[filenm]=true;suffix[filenm]=0;} //=>unique
> else{suffix[filenm]++; filenm=filenm+"-"+suffix[filenm];}  //=>unique
> Now filenm is unique, because suffix value is unique number starts from 1.
> UniqueName[index]=filenm;
> }
Because indexing is perhaps internally implemented for JavaScript Object, and because it's surely not sequential search, "if(!dupcheck[filenm])" and "holding highest suffix number for each  name in JavaScript Object" is far faster than "check from -1 to -NNNNNN for each NNNNNN" when NNNNNN is large, and is never O(n^2).

So, following may be a solution in mass unique file name generaion.
> function suggestUniqueFileName(aIdentifier, aType, aExistingNames, aDupCheckTable) {
> if(aDupCheckTable && "object"==(typeof aDupCheckTable)
> {
>  if(!aDupCheckTable["DupChk"])aDupCheckTable["DupChk"]={};
>  if(!aDupCheckTable["Suffix"])aDupCheckTable["Suffix"]={};
>  var DupChk=aDupCheckTable["DupChk"];
>  var Suffix=aDupCheckTable["Suffix"];
>  let base = validateFileName(aIdentifier);
>  let suggestion = base + aType;
>  if(!DupChk[suggestion]){DupChk[suggestion]=true;Suffix[suggestion]=0;}
>  else{Suffix[suggestion]++; suggestion = base + "-" + Suffix[suggestion] + aType;}
>  aExistingNames[aExistingNames.length]=suggestion;
>}

If "mass unique name generation without file creation", caller does do;
> var aDupCheckTable={};
> for(i=0; ...){
>   Set aIdentifier, aType, from ObjectArray[i]; 
>   suggestUniqueFileName(aIdentifier, aType, aExistingNames, aDupCheckTable);
> }
Comment 43 WADA 2013-04-08 22:11:07 PDT
If aExistingNames is pre-filled before suggestUniqueFileName call loop, caller should do following before start to call suggestUniqueFileName with aDupCheckTable.
> var aDupCheckTable={};aDupCheckTable["DupChk"]={};aDupCheckTable["Suffix"]={};
> var DupChk=aDupCheckTable["DupChk"];var Suffix=aDupCheckTable["Suffix"];
> for(var nn=0;nn<aExistingNames.length;nn++){
>  var nm = aExistingNames[nn];
>  if(!DupChk[nm]){DupChk[nm]=true;Suffix[nm]=0;} else Suffix[nm]++;
> }
If pre-filled aExistingNames is frequently used, fifth parameter of suggestUniqueFileName such as "InitDupCheckTableFromExistingNames" may be convenient in coding.
Comment 44 :aceman 2013-04-08 23:26:13 PDT
(In reply to WADA from comment #40)
> mkstemp(or mkstemps) may be better for our purpose, because it creates file
> and opens it.
> > http://linux.die.net/man/3/mkstemp
> > Porting of mkstemp to Win
> >  http://www.suacommunity.com/dictionary/mkstemp-entry.php

But we don't want any file to be created yet.
Comment 45 WADA 2013-04-09 03:11:01 PDT
My JS sample never considers bad case of "suffixed name is already used by other base". Registration of generated "base+suffix" to table is omitted. Uniquness is guranteed only within same base by my logic sample. 
If check for "already used name by other base" is added, comparison count is n*(n-1)/2 in worst case, and if check of "existent file(call num of files=F)" is also added, (n+F)*(n+F-1)/2 in worst case. So, it is still O(n^2). 

My point is:
 - To know "it's found in table via index" is usually faster than 
   To know "it's found in table by sequential search".
 - To know "it's not found in table via index" is far faster than 
   To know "it's not found in table by sequential search of all items".
And, even if worst case is still O(n^2), at least in "suffixed names from same base" case, or in "interfere of other_different_base(+suffix) by a base(+suffix)" case, required comparison count is O(2*n), because highest suffix is held for each base. So average comparison count can be reduced.
Comment 46 Mike Conley (:mconley) - (Needinfo me!) 2013-04-28 17:40:26 PDT
Comment on attachment 720835 [details] [diff] [review]
patch

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

This looks reasonable, but there's certainly stuff to clean up in here. See my comments.

::: mail/base/content/folderPane.js
@@ +487,5 @@
>    /**
>     * drag drop interfaces
>     */
>    canDrop: function ftv_canDrop(aRow, aOrientation) {
> +//Components.utils.reportError(aRow+"init");

I know you already mentioned removing these, but I want to be explicit - the three reportError's must go, and let's switch back from a var to a let on line 510.

::: mail/base/content/msgMail3PaneWindow.js
@@ +1322,5 @@
> +                             .messageURIToMsgHdr(messages[i]).mime2DecodedSubject;
> +      let uniqueFileName = suggestUniqueFileName(subject.substr(0,124), ".eml",
> +                                                 fileNames);
> +      fileNames.add(uniqueFileName);
> +      Components.utils.reportError(i+"="+uniqueFileName);

Please remove this debug line.

@@ +1333,2 @@
>    }
> +  Components.utils.reportError(fileNames.size);

Please remove this debug line as well.

@@ +1336,5 @@
>    aEvent.dataTransfer.addElement(aEvent.originalTarget);
>  }
>  
>  /**
> + * Returns a new filename that surely is not in the array of the existing names.

"surely" -> "is guaranteed to be"

@@ +1344,5 @@
> + *   returns "testname2.txt"
> + * Does not check file system for existing files.
> + *
> + * @param aIdentifier     proposed filename
> + * @param aType           extensions

extension, not extensions.

@@ +1345,5 @@
> + * Does not check file system for existing files.
> + *
> + * @param aIdentifier     proposed filename
> + * @param aType           extensions
> + * @param aExistingNames  a set of names in already in use

capitalize set in order to make it clear that we're talking about a Javascript Set here. Also, remove "in".
Comment 47 :aceman 2013-04-29 10:37:26 PDT
Created attachment 743159 [details] [diff] [review]
patch v2
Comment 48 Mike Conley (:mconley) - (Needinfo me!) 2013-05-18 09:49:08 PDT
Comment on attachment 743159 [details] [diff] [review]
patch v2

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

I'm happy with this, with my alignment nit fixed. Thanks aceman!

::: mail/base/content/msgMail3PaneWindow.js
@@ +1318,5 @@
> +      continue;
> +
> +    // Generate file name in case the object is dropped onto the desktop.
> +    let subject = messenger.messageServiceFromURI(messages[i])
> +                         .messageURIToMsgHdr(messages[i]).mime2DecodedSubject;

alignment nit
Comment 49 :aceman 2013-05-19 05:56:43 PDT
Created attachment 751457 [details] [diff] [review]
patch v3

Thanks.
Comment 50 Ryan VanderMeulen [:RyanVM] 2013-05-20 05:02:13 PDT
https://hg.mozilla.org/comm-central/rev/62360fc75a3c

Note You need to log in before you can comment on or make changes to this bug.