threading: implement on-the-fly message threading

implement message threading on the message store level using the
jwz algorithm. Build threads on-the-fly when new message headers arrive.

Use the references header to create the threads and the in-reply-to
header as a fall-back option in case no references header is present.

Does not run when the worker provides its own threading (e.g. imap
server threads).

Include only those message headers that have been fetched and are
stored in the message store.

References: https://www.jwz.org/doc/threading.html
Signed-off-by: Koni Marti <koni.marti@gmail.com>
Tested-by: Inwit <inwit@sindominio.net>
Tested-by: akspecs <akspecs@gmail.com>
Acked-by: Robin Jarry <robin@jarry.cc>

1 files changed, 12 insertions, 2 deletions

diff --git a/worker/types/thread.go b/worker/types/thread.go
index 18b31e9..48e4a00 100644
--- a/worker/types/thread.go
+++ b/worker/types/thread.go
@@ -17,14 +17,24 @@ type Thread struct {
 }
 
 func (t *Thread) AddChild(child *Thread) {
+	t.insertCmp(child, func(child, iter *Thread) bool { return true })
+}
+
+func (t *Thread) OrderedInsert(child *Thread) {
+	t.insertCmp(child, func(child, iter *Thread) bool { return child.Uid > iter.Uid })
+}
+
+func (t *Thread) insertCmp(child *Thread, cmp func(*Thread, *Thread) bool) {
 	if t.FirstChild == nil {
 		t.FirstChild = child
 	} else {
+		start := &Thread{Uid: t.FirstChild.Uid, NextSibling: t.FirstChild}
 		var iter *Thread
-		for iter = t.FirstChild; iter.NextSibling != nil; iter = iter.NextSibling {
+		for iter = start; iter.NextSibling != nil && cmp(child, iter); iter = iter.NextSibling {
 		}
-		child.PrevSibling = iter
+		child.NextSibling = iter.NextSibling
 		iter.NextSibling = child
+		t.FirstChild = start.NextSibling
 	}
 	child.Parent = t
 }