MBOX-Line: From dave at cridland.net  Sat Apr  1 00:09:55 2006
To: imap-protocol@u.washington.edu
From: Dave Cridland <dave@cridland.net>
Date: Fri Jun  8 12:34:37 2018
Subject: [Imap-protocol] Thread extension
In-Reply-To: <Pine.WNT.4.65.0603311522280.4704@Tomobiki-Cho.CAC.Washington.EDU>
References: <1143819932.8744.163.camel@localhost.localdomain>
	<Pine.OSX.4.64.0603310950110.26204@pangtzu.panda.com>
	<1143843283.3985.18.camel@hurina>
	<Pine.WNT.4.65.0603311421060.4704@Tomobiki-Cho.CAC.Washington.EDU>
	<1143847047.3985.42.camel@hurina>
	<Pine.WNT.4.65.0603311522280.4704@Tomobiki-Cho.CAC.Washington.EDU>
Message-ID: <14820.1143878996.313026@peirce.dave.cridland.net>

On Sat Apr  1 00:30:03 2006, Mark Crispin wrote:
> On Sat, 1 Apr 2006, Timo Sirainen wrote:
>> I think two types of insertions would be enough: "insert as 
>> sibling to
>> message n" and "insert as the first child to message n".
> 
> You need to define the semantics when UID THREAD is used.  Also, 
> you need to define what happens if the new message has children 
> (insertion as opposed to append).
> 
> 
I vaguely suspect that rather than single identifiers (sequence 
numbers or UIDs), you want tree fragments. That handles both "gap 
plugging", where a message arrives out of order (and I see a few of 
those on some mailing lists, especially where there's a mixture of 
replying direct to me and only replying to the list going on), and 
actual "grafting", where two previously unrelated trees are joined.

It also means you can unify most insertions down to a tree fragment 
by the algorithm of finding the insertion point, and sending the tree 
fragment starting at the parent, and ending at the first identified 
descendent node. I'd imagine most server implementations would give 
up and resend the whole tree in any complex cases.


>> I think that should be easy enough for the clients to handle?
> 
> You'd be surprised at what people find to be "not easy".
> 
> 
True, but there's precious few clients which implement much more than 
LITERAL+, CHILDREN, and perhaps one or two more. Better, these 
messages are at least clear in their intent by a reasonable 
application of common sense. ACL is fairly common, but I could only 
find one client-side implementation of LISTRIGHTS.


>> Well, I'm still mostly just interested in optimizing this 
>> internally in
>> my server so that the reply gets sent near instantly, but these are
>> somewhat related goals in that if I can figure out rules how to 
>> quickly
>> update the thread list internally, I can easily send out 
>> incremental
>> updates to clients as well.
> 
> I don't understand.  A thread should be nearly instantaneous, even 
> for a very large mailbox, if you use a hash table.  It's probably 
> also a good idea to cache the data needed to thread so it's 
> available the next time you thread.

JWZ's description of speeds on now fairly ancient hardware would 
suggest that. In any case, optimizing to the level Mark suggests 
would be a clearly useful first step.

Dave.
-- 
           You see things; and you say "Why?"
   But I dream things that never were; and I say "Why not?"
    - George Bernard Shaw

