acme mail, sort by conversation

[mpl, 2010-03-12 09:15:28]

On 2010/03/08 10:02:30, mpl wrote:
> 

I've just realized there possibly are bugs since I haven't looked at how things
are going when the messages are reprinted after the deleted ones are erased.
Most likely some which are not deleted could get written over.
I'll have a look at it soon, sorry.

Mathieu

[mpl, 2010-03-12 11:39:44]

On 2010/03/12 09:15:28, mpl wrote:
> On 2010/03/08 10:02:30, mpl wrote:
> > 
> 
> I've just realized there possibly are bugs since I haven't looked at how
things
> are going when the messages are reprinted after the deleted ones are erased.
> Most likely some which are not deleted could get written over.
> I'll have a look at it soon, sorry.
> 
> Mathieu

Actually nevermind. Since mesgmenudel() only erases lines, and uses m->name to
find which ones, it should be ok.

[rsc_swtch, 2010-04-13 20:24:15]

Thanks for working on this.  I like the idea of sort by conversation.
My comments below are mainly on where the code ends up.

http://codereview.appspot.com/264043/diff/10001/11001
File src/cmd/acme/mail/mesg.c (right):

http://codereview.appspot.com/264043/diff/10001/11001#newcode464
src/cmd/acme/mail/mesg.c:464: Mlist *lister, *rimmer, *kryten, *holly, *thecat,
*kristine;
Better names?

http://codereview.appspot.com/264043/diff/10001/11001#newcode478
src/cmd/acme/mail/mesg.c:478: /* first make an Mlist with no reordering and tag
everyone in
This seems like a lot of list manipulation just to sort.
Also it looks like it might be quadratic though I admit
I can't quite follow what's going on.

Could you make an array instead and use qsort?

http://codereview.appspot.com/264043/diff/10001/11001#newcode493
src/cmd/acme/mail/mesg.c:493: /* then do a first sort by tagging them with
different groups.
use standard multiline comment format

/*
 * line1
 * line2
 */

http://codereview.appspot.com/264043/diff/10001/11001#newcode530
src/cmd/acme/mail/mesg.c:530: /* free the element from the first Mlist now that
it's
same

http://codereview.appspot.com/264043/diff/10001/11001#newcode603
src/cmd/acme/mail/mesg.c:603: if (sortbythread){
why is this in the ind <= 0 case?
shouldn't it be a separate test a few lines earlier?

can you move the body into its own function?

[mpl, 2010-04-15 16:40:56]

Hello,

Before I do it in mailfs, I worked with a small example, which is below.
I'm not sure it's faster than what I previously did (I've never really learned
how to calculate computational complexity) but it sure is more readable. I think
it's nice to order the conversations against each other by "recentness of their
most recent message" but that adds some complexity (here buildIndex). To do
simpler we could just drop that and order them lexicographically.
What do you think?

#include <u.h>
#include <libc.h>

char *A = "this is subject A";
char *B = "this is subject B";
char *C = "this is subject C";
char *D = "this is subject D";
char *E = "this is subject E";

char *index[30];
int indexSize = 0;

char
pickrand(char min, char max)
{
	double rn;

	srand((long)nsec());
	rn = min + frand() * (max - min);
	return (char)floor(rn);
}

int
compar(void *first, void *second)
{
	char **buf1 = (char **) first;
	char **buf2 = (char **) second;
	int n;

	// same subject, order by (inverse) id (=date)
	n = strncmp(&(*buf1)[1], &(*buf2)[1], 18);
	if (n == 0){
		if ((*buf1)[0] < (*buf2)[0])
			return -1;
		if ((*buf1)[0] > (*buf2)[0])
			return 1;
		if ((*buf1)[0] == (*buf2)[0])
			exits("ouch");
	}
	//different subject, order by index
	for(int i=0; i<indexSize; i++){
		if (strcmp(&(*buf1)[1], index[i]) == 0)
			return 1;
		if (strcmp(&(*buf2)[1], index[i]) == 0)
			return -1;
	}

}

/*
 * finds the first occurence for each future conversation
 * so we can use that as a criterion for the ordering of
 * the conversations.
 */
int
buildIndex(char *entries[], char *index[])
{
	int N, found;

	N = 0;
	for (int i=29; i>=0; i--){
		found = 0;
		for (int j=0; j<N; j++){
			if (strcmp(&entries[i][1], index[j]) == 0){
				found = 1;
				break;
			}
		}
		if (!found) {
			index[N] = smprint("%s", &entries[i][1]);
			N++;
		}
	}
	
	return N;
}

void
main()
{
	char *entries[30];
	char n;
	char *buf;

	//generate random data
	for (char i = 0; i<30; i++){
		entries[i] = malloc(20);
		entries[i][0] = i;
		n = pickrand(0,5);
		switch(n){
		case 0:
			buf = A;
			break;
		case 1:
			buf = B;
			break;
		case 2:
			buf = C;
			break;
		case 3:
			buf = D;
			break;
		case 4:
			buf = E;
			break;
		}
		memmove(&entries[i][1], buf, 18);
	}

	print("initial order: \n");
	for(int i=29; i>=0; i--)
		print("%d:	%s \n", entries[i][0], &entries[i][1]);
	print("\n");

	indexSize = buildIndex(entries, index);
	print("order of conversations: \n");
	for(int i = 0; i<indexSize; i++)
		print("%s \n", index[i]);
	print("\n");

	qsort(entries, 30, sizeof(char *), compar);

	print("final order: \n");
	for(int i=29; i>=0; i--)
		print("%d:	%s \n", entries[i][0], &entries[i][1]);

}

[mpl, 2010-04-25 23:16:02]

Hello Russ,

So I went ahead and I've redone it. Seems to be working fine for me but I
haven't tested it for very long.

I think this new implementation addresses all your comments except for
"why is this in the ind <= 0 case?
shouldn't it be a separate test a few lines earlier?"
The answer to that is we want everything dealing with sorting by conversation
inside the (ind<=0) case, because when it's recursing 
to deal with the pieces, we don't want any of the sort by conversation stuff to
happen. Maybe I missed something and there's a smarter way to ensure that
though...

Also, I haven't been able to make sure that "this is a subject" and "Re: this is
a subject" are seen as in the same conversation, even though that stripre()
thing I wrote seems to be working. I'm missing something and I haven't figured
out what yet. So instead, I'm using stripre() again when comparing the subject
with the sortedindex and that seems to get the work done, but I don't like it.

Hope you like it better.

Cheers,
Mathieu

[mpl, 2010-06-22 14:01:34]

Hello,

Is there anything in particular you don't like in that version and you'd like me
to redo?

Cheers,
Mathieu

[rsc, 2010-12-07 18:31:43]

I don't think this is going to happen. 
Sorry, I just don't have time to put into
acme Mail anymore, and I don't understand
what the code is doing.

http://codereview.appspot.com/264043/diff/16001/src/cmd/acme/mail/mesg.c
File src/cmd/acme/mail/mesg.c (right):

http://codereview.appspot.com/264043/diff/16001/src/cmd/acme/mail/mesg.c#newc...
src/cmd/acme/mail/mesg.c:520: if (strcmp((*msg1)->messageid ,
(*msg2)->inreplyto) == 0
why the spaces after the commas?

[mpl, 2010-12-07 22:02:21]

I don't understand what seems to be the problem. I've redone it according to
your comments, and it's working fine imho (I've been using it on all my machines
since this issue has been opened).
No biggie though, it's not like anyone else seems to care, so I'll just host the
changes somewhere else in case anyone ever want them.

Cheers,
Mathieu

On 2010/12/07 18:31:43, rsc wrote:
> I don't think this is going to happen. 
> Sorry, I just don't have time to put into
> acme Mail anymore, and I don't understand
> what the code is doing.
> 
> http://codereview.appspot.com/264043/diff/16001/src/cmd/acme/mail/mesg.c
> File src/cmd/acme/mail/mesg.c (right):
> 
>
http://codereview.appspot.com/264043/diff/16001/src/cmd/acme/mail/mesg.c#newc...
> src/cmd/acme/mail/mesg.c:520: if (strcmp((*msg1)->messageid ,
> (*msg2)->inreplyto) == 0
> why the spaces after the commas?

[rsc, 2010-12-07 23:03:51]

On Tue, Dec 7, 2010 at 17:02,  <mathieu.lonjaret@gmail.com> wrote:
> I don't understand what seems to be the problem. I've redone it
> according to your comments, and it's working fine imho (I've been using
> it on all my machines since this issue has been opened).

there are still very strange things about it.
for example, your qsort comparison function
is broken.  you can't use reply-to and message-id
comparisons to decide equality but not include
them in the rest of the comparison.
as written if you had subject S and then
a reply-to that changed it to subject Y,
the sort might end up with

S S Y S S X X X Y Y Z

depending on how qsort happens to process
the messages.

which can't possibly be desired behavior.
also the various operations make it all
quadratic or worse.

instead of what you have now a much
simpler way would be to add two new field
to the message struct called orig_index,
thread_index, and then do

make array of messages

n = 0
for each mesg
   m->orig_index = n++

qsort by subject and when subjects are equal, orig_index

for each mesg
    if subject matches previous message
        thread_index = orig_index of previous message
    else
        thread_index = orig_index

qsort by thread_index and when thread_index is equal, orig_index

russ

[mpl, 2011-01-03 09:20:42]

Thanks for the analysis, I'll get back to it as soon as I can.

On 2010/12/07 23:03:51, rsc wrote:
> On Tue, Dec 7, 2010 at 17:02,  <mailto:mathieu.lonjaret@gmail.com> wrote:
> > I don't understand what seems to be the problem. I've redone it
> > according to your comments, and it's working fine imho (I've been using
> > it on all my machines since this issue has been opened).
> 
> there are still very strange things about it.
> for example, your qsort comparison function
> is broken.  you can't use reply-to and message-id
> comparisons to decide equality but not include
> them in the rest of the comparison.
> as written if you had subject S and then
> a reply-to that changed it to subject Y,
> the sort might end up with
> 
> S S Y S S X X X Y Y Z
> 
> depending on how qsort happens to process
> the messages.
> 
> which can't possibly be desired behavior.
> also the various operations make it all
> quadratic or worse.
> 
> instead of what you have now a much
> simpler way would be to add two new field
> to the message struct called orig_index,
> thread_index, and then do
> 
> make array of messages
> 
> n = 0
> for each mesg
>    m->orig_index = n++
> 
> qsort by subject and when subjects are equal, orig_index
> 
> for each mesg
>     if subject matches previous message
>         thread_index = orig_index of previous message
>     else
>         thread_index = orig_index
> 
> qsort by thread_index and when thread_index is equal, orig_index
> 
> russ

[mpl, 2011-03-22 16:27:02]

hello,

just a little ping to signal I haven't given up on that. I'm starting
redoing it as you advised just now.

mathieu

[mpl, 2011-03-27 14:14:42]

Hi,

I implemented your suggestion in patch set 6. A few comments in the following:

> instead of what you have now a much
> simpler way would be to add two new field
> to the message struct called orig_index,
> thread_index, and then do
> 
> make array of messages

Done. I'm also deleting the messages from the initial mbox as I copy them in
this new array of messages, so that we don't end up with twice the memory usage.

> n = 0
> for each mesg
>    m->orig_index = n++
> 
> qsort by subject and when subjects are equal, orig_index
> 
> for each mesg
>     if subject matches previous message
>         thread_index = orig_index of previous message
>     else
>         thread_index = orig_index

I assumed you meant
      if subject matches previous message
          thread_index = thread_index of previous message

> qsort by thread_index and when thread_index is equal, orig_index

all of the above is done in 
void sortbyconversation(Message *mbox), which happens just at the beginning of
mesgmenu0 (under the right conditions).

after which I have the mbox point at this new sorted array instead of the
initial one (which has been emptied as we go).

then I kept the original contents of mesgmenu0.

and as a last step, I've added 
void 
moveconversationup(Window *w, Message *mbox, char *realdir, char *dir, int ind,
CFid *fd, int dotail)
which happens just after a new incoming message has been printed. it moves up
all the messages of the same conversation as the new incoming message to print
them just below it.
I don't do any mbox reorganization here, it's only some printing, because I
don't think it is needed.

Cheers,
mathieu

[mpl, 2011-03-31 15:19:18]

there's a bug in the last step, I'm working on it.

[mpl, 2011-04-05 11:48:40]

So I think the bug was that when some incoming messages arrived in close
succession, there was nothing preventing the corresponding reordering of the
conversations for those messages (namely the moveconversationup() function) to
happen concurrently. So the resulting output was a mix of the prints of those
two (or more).

The easy solution was to set a lock around that. Do you see a problem with that?

[mpl, 2011-04-20 22:26:58]

after some more testing I can see there's still something wrong, sorry about
that. I'm working on it.

[mpl, 2011-05-15 19:52:16]

Hello,

Please take another look.

mathieu