110205 - Add sortKey attribute to folder which is based on collation key.

Status: VERIFIED FIXED

(MailNews Core :: Backend, defect)

Description

[Navin Gupta]

Seth's comments from bug 104610

here's what we should do:

1) add "readonly attribute wstring sortKey" to the nsIMsgFolder interface.
2) move the code from the if (sort) {) block in nsMsgFolderDataSource.cpp#1060, 
to the GetSortKey() implementation in nsMsgFolder.cpp
3) fix GetSortKey() to actually generate collation keys
4) fix nsMsgFolderDataSource.cpp#1060 to use GetSortKey()

all that will fix folder pane sorting, and menu sorting.  (which is broken, 
because we aren't generation collation keys)

5) then, you can fix the JS to use array.sort(), folder.sortKey

nsICollation isn't scriptable, so to compare the sort keys, you're going have 
to add an method to compare them to some existing, scriptable interface, and 
pass in your sort keys to it, and use nsICollation from there.

we should review how we are doing sorting of accounts.  account names can have 
non-ASCII characters, like folder names, which means sorting is broken their 
too.

this should all be in a new bug, that blocks the landing of neil's patch.

Comment 1

[Navin Gupta]

Attachment: proposed fix

Added sortKey attribute to nsIMsgfolder that is based on order + collation key.

Comment 2

[Navin Gupta]

seth, could you review this ?

Comment 3

[Navin Gupta]

Attachment: patch

new patch

Comment 4

[Navin Gupta]

Attachment: patch

Sorry for the spam, this one is correct, thanks

Comment 5

[(not reading, please use [e-mail] instead)]

1)

why do you have to set the length of mSortKey?  Isn't it initialized to length 
0?

2) 

+ if (mSortKey.Length() == 0)

should be 

+ if (mSortKey.Length())

3)  why aren't you caching the collationKeyGenerator, instead of creating an 
instance of it every time you need a sort key?  

see http://lxr.mozilla.org/mozilla/source/mailnews/addrbook/src/nsAbView.cpp#625
for an example.

4)   hmm, this comment scares me.  looking in lxr, there are other places in 
mailnews where we are treating collation keys as PRUnichar*, instead of

// Note using PRUnichar* to store collation key is not recommented since the 
key may contains 0x0000.

looking at how the msg database does it, we're doing it wrong.  

we should be treating the collation keys as PRUint8 * (raw bytes) and when 
comparing, use collationKeyGenerator->CompareRawSortKey()

I'm going to go fix my nsAbView.cpp code.  please fix this code before checking 
in.

Comment 6

[(not reading, please use [e-mail] instead)]

update nsAbView.cpp and nsAbView.h.

I just fixed them.

those files aren't part of the build yet, but they work in my local tree, with 
my other changes.

Comment 7

[Navin Gupta]

>3)  why aren't you caching the collationKeyGenerator, instead of creating an 
>instance of it every time you need a sort key?  
>see 
http://lxr.mozilla.org/mozilla/source/mailnews/addrbook/src/nsAbView.cpp#625
>for an example.

This is because when you first create the sortKey for a folder, then 
mCollationKeyGenerator will be null and will need to be created, after that
you will always have mSortKey so this code will not be used. so there is 
no point caching mCollationKeyGenerator.

Comment 8

[Navin Gupta]

Attachment: patch

Revised patch w/ your suggestions. It does create a unique key for each source
string.

Comment 9

[(not reading, please use [e-mail] instead)]

+ mSortKey.AppendInt(*key, 8);

*key is an address of a chunk of memory, of size aLength, right?

what does that code do?  what keys are you producing?

it looks like your keys are appended by the hex version of the address of *key 
to mSortKey.  Is that what's going on?  I can't tell by eyeballing.

you need to think all this through.

you need to see how the XULSortService and nsXULOutlinerBuilder compares the 
keys you are generating, and in the future, if you fix the view navigation js, 
how it will compare two keys.

we return an RDFLiteral for the key, and later the outliner builder and the 
sort service turns that back into a raw key, and calls CompareRawSortKey()
or compares the two strings, you should debug to see which one gets called.

as we know, treating keys as PRUnichar * is bad, as there can be null bytes in 
the raw key, so strlen() is != key length.

talk to who owns the collation key code (nhotta?  ftang?) and also talk to 
someone who knows more about RDF, the sort service and the outliner build than 
we do.

I'm thinking the way out of this is some sort of conversion code in 
nsMsgFolder::GetSortKey() that will turn the raw key into a save PRUnichar *, 
one with out null bytes, but one that is still "correct" when it gets turned 
back into a raw key, it works.

I'm after the f2 that meets this requirement:

f1 = compare raw sort keys
f2 = convert raw sort keys into "safe" PRUnichar *

f1(raw1,raw2) == f1(f2(raw1), f2(raw2))

I'm not sure if that exists, ftang and nhotta would probably know.

note, nsMsgDBView and nsAbView don't have this problem, as we don't go through 
RDF for sorting.

Comment 10

[Navin Gupta]

To create mSortKey i use the sort order + collation key 

nsOutlinerBuilder gets called and that uses PRUnichar as literal value and 
then does the comparsion, so we should be fine. We are storing as PRUnichar
and getting back PRUnichar. 

nhotta what do you think, is it safe to do this ? Could you review the
last patch.

Comment 11

[(not reading, please use [e-mail] instead)]

I don't see how 

mSortKey.AppendInt(*key, 8);

is doing what you want, in any case.  can you explain that code?

Comment 12

[Navin Gupta]

>mSortKey.AppendInt(*key, 8);

It appends the key which has base 8 (PRUint8 *). 

CompareRawSortKey always does a memcmp if length of two strings are same.

One thing we could do is whenever sort order is 6 then use this method otherwise
we know how the sort would like, right ?

Comment 13

[nhottanscp]

mSortKey.AppendInt(*key, 8);
I think this is not needed. The client code is not suppose to manipulate the
generated key. PRUint8 just means it is a raw 8 bit data not ASCII.

Comment 14

[Navin Gupta]

But then how do we convert PRUint8* to PRUnichar and the sortKey is also 
dependent on the order which is PRUint32

Comment 15

[nhottanscp]

The key should not be stored in PRUnichar*.

+  readonly attribute wstring sortKey;
The key is a binary data not a unicode string. Is there a type for unsigned
char* for IDL? And the key may cotain zeros so it also need length along with a key.

+  nsString mSortKey;
The same reason, it has to be stored separtely a key and its length.

Comment 16

[Navin Gupta]

So what about order. 

have the order and name appended in the source for which the sortKey should be
generated? is that what you are suggesting.  

Comment 17

[nhottanscp]

Actually, I don't know about the context here.
Could you explain about order and name?

Comment 18

[Navin Gupta]

we just do not want to sort alphanumerically, for special folders like inbox
sent, drafts, we have a predetermined sort order - folder->GetSortOrder, these
special folder should appear before user-defined folder. For user-defined 
folders we want to use folder name.
  
therefore both name and sort order play a role.

Also rdf expects node name to be PRUnichar, so how will this work 
PRUint8* -> PRUnichar is not advised. look at these code snippets 

content/xul/templates/src/nsXULOutlinerBuilder.cpp:1819
content/xul/templates/src/nsXULSortService.cpp:902

They are just casting from PRUnichar* to PRUint8*. I guess for now we can 
just go with this. There should be no dataloss from 1 byte word to 2 byte 
word and then back to 1 byte word, although it is not correct. 

Comment 19

[nhottanscp]

But how order are related to sort keys, do the special folders also need sort keys?

>Also rdf expects node name to be PRUnichar
It is used incorrectly in RDF, they have to fix it. Anyway, PRUint8* to
PRUnichar* conversion (or appending 0x0000 and cast to PRUnichar*) can take
place just before passing the key to RDF. I think the fields in the classes
should be kept as the raw data with a length.

Comment 20

[Navin Gupta]

>But how order are related to sort keys, do the special folders also need sort keys?

we want to have a sortKey for special folders also and the way folders are going
to be sorted depends upon
1)name
2)order

so the sortKey should be generated based on both name and order.

Comment 21

[nhottanscp]

Sorry, still not clear. So orders are numbers like 1,2,3? Then sort by order
first then by name would make special folders sorted separately, instead of name
then order. Anyway, I think the order does not need to be converted to a sort
key, no locale sensitive sorting needed for the internal numbers.

Comment 22

[nhottanscp]

How about adding a method to nsICollation which return key in ASCII? This 
can ensure no null bytes in a key. If the caller pre-allocate extra byte(s) for 
null terminator then no need to keep a length with the key.
A side effect of encoding to ASCII is that it doubles the size of a key.

Comment 23

[Navin Gupta]

The order and name both have to be used at the same time because there 
will be comparison between special folder and user created folders for 
sorting. 

I don't know how I can explain better. Can I stop by your cube tomorrow ?

Comment 24

[nhottanscp]

Filed bug 110837 for adding ASCII sort key to nsICollation.

Comment 25

[[e-mail]]

So if I have understood correctly, the sortKey will be a unicode string of the
hex representation of a collation key which can be sorted using the < or >
operators.

Comment 26

[nhottanscp]

The new method return char* not PRUnichar*, so it's not a unicode string. Hex
encode to unicode would increase the key four time large as the original binary key.

Comment 27

[[e-mail]]

Sorry to harp on about this but I thought that JavaScript only used Unicode.

Comment 28

[nhottanscp]

Reply to comment #27: 
The input is a Unicode string but generated key is a binary. That is why using
PRUnichar* for a key is not good.

Comment 29

[nhottanscp]

As I wrote in bug 110837, I cannot simply provide the ASCII key support. Could
you do this bug with a binary key instead (like address book does)? 
All you need to do is  to encode the order to ASCII (e.g. by sprintf) and
prepend it to the input string before creating a binary sort key. So the input
to the collation method is ASCII encoded order + input string. For example, the
order is 2 and the input string is "abc" then input to nsCreateRawSortKey() is
"2abc".

Comment 30

[Navin Gupta]

Attachment: proposed fix

So this patch uses the order and name to generate the collation key that we
are caching as mSortKey (PRUnichar ) because of the problem naoki outlined. 
This works for both msgViewNavigation and folder sorting in folder pane. 
naoki, can you review, thanks for the help.

Comment 31

[nhottanscp]

+  attribute wstring sortKey;
This is depending the XUL sort service, I filed bug 114070 for that.
But does it have to be public in idl?

+  nsCOMPtr<nsILocaleService> localeSvc =
do_GetService(NS_LOCALESERVICE_CONTRACTID,&rv); 
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  nsCOMPtr<nsILocale> locale; 
+  rv = localeSvc->GetApplicationLocale(getter_AddRefs(locale));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  nsCOMPtr <nsICollationFactory> factory =
do_CreateInstance(kCollationFactoryCID, &rv); 
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  rv = factory->CreateCollation(locale, getter_AddRefs(collationKeyGenerator));
+  NS_ENSURE_SUCCESS(rv, rv);

These parts are not needed per key generation. Please do it only once then
remember  'collationKeyGenerator' somewhere in the class.

Comment 32

[Navin Gupta]

We cannot use static nsCOMPtr so I don't know to share it among different
folder objects, trying to think of something?

Comment 33

[nhottanscp]

Comment on attachment 60876 [details] [diff] [review]
proposed fix

Okay, if that is not possible but those are not inexpensive calls.

r=nhotta

Comment 34

[nhottanscp]

I thought about it again, it could be a large overhead depends on the number of
items to be sorted which may impact the performance. I am not familiar with the
code but please consider to save it if possible.

Comment 35

[Navin Gupta]

ok, I am able to make collationKeyGenerator global, patch coming up..

Comment 36

[Navin Gupta]

Attachment: proposed fix

made collationKeyGenerator global.

Comment 37

[(not reading, please use [e-mail] instead)]

there's a problem with caching the sort key, what if the sort order changes?
what if the folder becomes a special folder, or "unbecomes" a special folder?

note, we've got a bunch of bugs for what happens when a folder becomes or 
unbecomes a special folder, but let's not add any more.

can this be fixed by calling child->SetSortKey(nsnull) when the folder flags 
change?

Comment 38

[nhottanscp]

+nsMsgFolder::CreateCollationKey(const PRUnichar *aSource,  nsString &aSortKey)
The function copies the key to nsString and frees the original key. Then another
duplication at nsMsgFolder::GetSortKey() by ToNewUnicode. Is there a way to
avoid them? Sorry, I did not see it last time.

Comment 39

[Navin Gupta]

Attachment: fix

reduced one copy and free. also setSortKey to null on flag change. this diff
includes only mailnews/base where I made changes. local and imap part remain
unchanged.

Comment 40

[(not reading, please use [e-mail] instead)]

1)

what about this code and comment that got removed?

-    // to create the sort string, we get the sort order
-    // append the name, and make the whole thing lower case
-    // because we want AAA to be next to aaa.

-    // make sort insensitive to case
-    orderString.ToLowerCase();

don't we still need that?

2)  I don't think you put the call to SetSortKey(nsnull) in the right place.
for the special folder flags, do we clear them when a folder "unbecomes" the 
sent or drafts folder?  You'll have to investigate.  I think OnFlagChange() is 
the right place.

would it be a benefit to only call SetSortKey(nsnull) when only certain flags 
change, or when any flag changes?  Probably on all flag changes, since we only 
regenerate the sort key when someone does GetSortKey(), so several calls to 
SetSortKey(nsnull) aren't that expensive.  but you should confirm.

3)  please add comments to all the places in the code where you did:

SetSortKey(nsnull);

for the one you just added, a comment about why we have to clear the sort key 
(so it will get regenerated) when the folder flags (like inbox or sent) change.

also, where else do we need to do that?  on rename only, right?

please attach a complete patch, so I can review the whole thing.

Comment 41

[nhottanscp]

At CreateCollationKey, I think the key is still copied to a buffer of aSortKey,
so the original key is not freed. I think mSortKey could be PRUnichar* so it can
hold the original key and freed at destructor, or it could be nsXPIDLString and
adopt the original key.

Comment 42

[Navin Gupta]

Attachment: fix

taken care of free and copy issues and unspecializing "trash" problems in this
patch. I curse operator overloading...

Comment 43

[Navin Gupta]

what about this code and comment that got removed?

-    // to create the sort string, we get the sort order
-    // append the name, and make the whole thing lower case
-    // because we want AAA to be next to aaa.

-    // make sort insensitive to case
-    orderString.ToLowerCase();

don't we still need that?

No, we are now directly getting sortKey. 

For rest of your comments we only
unspecialize trash when we change imap delete model, all other folders 
remain as it is and this unspecialization issue can be taken care in another
bug. I don't understand why you have to club issues and cause more confusion.

I have attached the complete patch and we need to generate the sort key on
rename 
+ setSortKey(nsnull);
+ getSortKey(nsnull);




 

Comment 44

[(not reading, please use [e-mail] instead)]

1)

>> -    orderString.ToLowerCase();
>> don't we still need that?
>No, we are now directly getting sortKey. 

ah, so passing in kCollationCaseInSensitive will do the right thing, and 
generate case insensitive keys.

2)

> For rest of your comments we only
> unspecialize trash when we change imap delete model, all other folders 
> remain as it is and this unspecialization issue can be taken care in another
> bug. 

I don't understand.  can you elaborate?

3)

I don't understand why you do this:

SetSortKey(nsnull);
GetSortKey(nsnull); 

Why do you need to force the key to get regenerated?  won't GetSortKey() get 
called when needed?  I don't understand what's going on.

something seems weird, when you've got a wstring attribute sortKey, where 
calling the setter followed by the getter doesn't return the same thing.

wstring getSortKey();
void recomputeSortKey();

would make more sense, where recomputeSortKey() would cause mSortKey to get 
regenerated.

4)

-#ifdef DEBUG_bienvenu
       nsXPIDLString name;
       rv = GetName(getter_Copies(name));
-      NS_ASSERTION(Compare(name, NS_LITERAL_STRING("Trash")) || (mFlags & 
MSG_FOLDER_FLAG_TRASH), "lost trash flag");
-#endif
+      if (nsCRT::strcmp(name.get(), NS_LITERAL_STRING("Trash").get()) == 0 && !
(mFlags & MSG_FOLDER_FLAG_TRASH))
+      {
+        NS_ASSERTION(0, "lost trash flag");
+        SetSortKey(nsnull); //force sortKey generation because trash is no 
longer special folder.
+        GetSortKey(nsnull); 
+      }
+

why are you only regenerating when we lose the trash folder flag?  I think you 
want to regenerate when ever the folder flags change.   do they regenerate when 
I change my sent folder?

5)
       
> I don't understand why you have to club issues and cause more confusion.

what does "club issues" mean?  I'm just trying to make sure the best, most 
maintainable code gets checked in.

Comment 45

[Navin Gupta]

+SetSortKey(nsnull);
+GetSortKey(nsnull); 

This is ok because sortKey is cached and once the folder is renamed,
the renamed folder will be sorted, so there is no extra cost.

>why are you only regenerating when we lose the trash folder flag?  I think you 
>want to regenerate when ever the folder flags change.   do they regenerate when 
>I change my sent folder?

If you look at copies and folders you cannot change your sent folder meaning
it will always point to "Sent". Please look at the panel.

>what does "club issues" mean?  I'm just trying to make sure the best, most 
>maintainable code gets checked in.

I filed this bug to make sure that we sort the non-ascii in the folder pane
correctly. you can take specialization and non-specialization to another bug 
(It is something on the periphery and can be taken care of in another bug.)
 

Comment 46

[Navin Gupta]

I take it back you can change the "sent" folder", the ui seems complicated..
Again this is something uncommon and let us first get the main part going 
so that we can fix 104610, a perf bug. 

Comment 47

[David :Bienvenu]

It looks like you're taking away that getrequirescleanup method - am I missing
something? I thought we'd agreed to leave that in because we will need it in the
future. I don't see how nsMsgFolder.cpp can compile with that change to
nsMsgFolder.h either.

Comment 48

[Navin Gupta]

ok, checked the specialization issue for sent, draft, templates, we never
unspecialize special folder if the user chnages the setting in "Copies and 
Folders", we just set the pref and use that to find the "sent" folder. Also
for "trash" there is already a bug about unspecializing it when user changes
the delete model to imap-delete. 

Comment 49

[nhottanscp]

Comment on attachment 60903 [details] [diff] [review]
fix

r=nhotta

Comment 50

[David :Bienvenu]

Is there a compelling reason to cache this sort key, instead of regenerating it
on request? If we didn't cache it, we would reduce memory bloat, and simplify
this patch significantly. Client code shouldn't be asking for this key over and
over again, I wouldn't think. 

Comment 51

[Navin Gupta]

atleast for msgNaviagtion this will be asked for repeatedly. I don't know
about other case. 

Comment 52

[David :Bienvenu]

OK, that should only happen when navigation is going to span folders, which is
pretty rare.  I don't think that should be a significant performance issue. The
other time this code is called is when menus are created - we hope that the sort
key is just retrieved once per menu item, in which case, again, caching isn't
really a good idea (in general, caching state that can change or become invalid
can really produce hard-to-maintain code and needs to be justified by
performance gains).

Comment 53

[(not reading, please use [e-mail] instead)]

> Is there a compelling reason to cache this sort key, instead of regenerating it
> on request? If we didn't cache it, we would reduce memory bloat, and simplify
> this patch significantly.

I agree, that would simplify the patch and make it easier to maintain going forward.

we should check how much caching vs non-caching matters to performance in the
navigation code.  I bet it's small, but if not, we could fix that code to get
all the keys once, instead of getting them and comparing them in the comparator
function we pass to sort().

Comment 54

[Navin Gupta]

you guys want to change so many times, i don't know what to do? when this
bug was filed seth said in bug 104610. 

"1) add "readonly attribute wstring sortKey" to the nsIMsgFolder interface.
2) move the code from the if (sort) {) block in nsMsgFolderDataSource.cpp#1060, 
to the GetSortKey() implementation in nsMsgFolder.cpp..."

Now I want to be sure before I go back one more time. I don't think there will
be much difference because we are using global collationKeyGenerator. 

Comment 55

[David :Bienvenu]

those things are both still true, I believe, unless I'm missing something. The
implementation of the getter for the attribute would just regenerate the string
instead of caching it and using a cached copy. I don't know about the folder
data source code, but I can't imagine that's related to the folder caching the
string, because there's only one folder ds, and lots of folders.

Comment 56

[Navin Gupta]

Attachment: proposed fix

removed mSortKey. please review.

Comment 57

[Navin Gupta]

I will change the name from orderString to sortKey in nsMsgFolderDataSource.cpp

Comment 58

[David :Bienvenu]

Comment on attachment 61168 [details] [diff] [review]
proposed fix

looks good to me, r=bienvenu

Comment 59

[Navin Gupta]

fixed

Comment 60

[[e-mail] (gone - use [e-mail] instead)]

Is this bug a candidate for verification through LXR?

Comment 61

[nhottanscp]

This enabled locale sensitive sorting, IQA might want to verify, cc to ji.

Comment 62

[[e-mail] (gone - use [e-mail] instead)]

QA contact --> Shirley, so that this bug gets verified more precisely than I
might do.

Comment 63

[ji]

Verified as fixed with the latest build. The sorting is working now except in a
new Japanese folder case which is mentioned in bug 104484.