messages: allow displaying email threads

Display threads in the message list. For now, only supported by the
notmuch backend and on IMAP when the server supports the THREAD
extension.

Setting threading-enable=true is global and will cause the message list
to be empty with maildir:// accounts.

Co-authored-by: Kevin Kuehler <keur@xcf.berkeley.edu>
Co-authored-by: Reto Brunner <reto@labrat.space>
Signed-off-by: Robin Jarry <robin@jarry.cc>

3 files changed, 217 insertions, 0 deletions

diff --git a/worker/types/messages.go b/worker/types/messages.go
index 599e870..fb701bd 100644
--- a/worker/types/messages.go
+++ b/worker/types/messages.go
@@ -81,11 +81,21 @@ type FetchDirectoryContents struct {
 	SortCriteria []*SortCriterion
 }
 
+type FetchDirectoryThreaded struct {
+	Message
+	SortCriteria []*SortCriterion
+}
+
 type SearchDirectory struct {
 	Message
 	Argv []string
 }
 
+type DirectoryThreaded struct {
+	Message
+	Threads []*Thread
+}
+
 type CreateDirectory struct {
 	Message
 	Directory string
diff --git a/worker/types/thread.go b/worker/types/thread.go
new file mode 100644
index 0000000..09f9dbb
--- /dev/null
+++ b/worker/types/thread.go
@@ -0,0 +1,99 @@
+package types
+
+import (
+	"errors"
+	"fmt"
+)
+
+type Thread struct {
+	Uid         uint32
+	Parent      *Thread
+	PrevSibling *Thread
+	NextSibling *Thread
+	FirstChild  *Thread
+
+	Hidden  bool // if this flag is set the message isn't rendered in the UI
+	Deleted bool // if this flag is set the message was deleted
+}
+
+func (t *Thread) Walk(walkFn NewThreadWalkFn) error {
+	err := newWalk(t, walkFn, 0, nil)
+	if err == ErrSkipThread {
+		return nil
+	}
+	return err
+}
+
+func (t *Thread) String() string {
+	if t == nil {
+		return "<nil>"
+	}
+	parent := -1
+	if t.Parent != nil {
+		parent = int(t.Parent.Uid)
+	}
+	next := -1
+	if t.NextSibling != nil {
+		next = int(t.NextSibling.Uid)
+	}
+	child := -1
+	if t.FirstChild != nil {
+		child = int(t.FirstChild.Uid)
+	}
+	return fmt.Sprintf(
+		"[%d] (parent:%v, next:%v, child:%v)",
+		t.Uid, parent, next, child,
+	)
+}
+
+func newWalk(node *Thread, walkFn NewThreadWalkFn, lvl int, ce error) error {
+	if node == nil {
+		return nil
+	}
+	err := walkFn(node, lvl, ce)
+	if err != nil {
+		return err
+	}
+	for child := node.FirstChild; child != nil; child = child.NextSibling {
+		err = newWalk(child, walkFn, lvl+1, err)
+		if err == ErrSkipThread {
+			err = nil
+			continue
+		} else if err != nil {
+			return err
+		}
+	}
+	return nil
+}
+
+var ErrSkipThread = errors.New("skip this Thread")
+
+type NewThreadWalkFn func(t *Thread, level int, currentErr error) error
+
+//Implement interface to be able to sort threads by newest (max UID)
+type ByUID []*Thread
+
+func getMaxUID(thread *Thread) uint32 {
+	// TODO: should we make this part of the Thread type to avoid recomputation?
+	var Uid uint32
+
+	thread.Walk(func(t *Thread, _ int, currentErr error) error {
+		if t.Uid > Uid {
+			Uid = t.Uid
+		}
+		return nil
+	})
+	return Uid
+}
+
+func (s ByUID) Len() int {
+	return len(s)
+}
+func (s ByUID) Swap(i, j int) {
+	s[i], s[j] = s[j], s[i]
+}
+func (s ByUID) Less(i, j int) bool {
+	maxUID_i := getMaxUID(s[i])
+	maxUID_j := getMaxUID(s[j])
+	return maxUID_i < maxUID_j
+}
diff --git a/worker/types/thread_test.go b/worker/types/thread_test.go
new file mode 100644
index 0000000..e79dddd
--- /dev/null
+++ b/worker/types/thread_test.go
@@ -0,0 +1,108 @@
+package types
+
+import (
+	"fmt"
+	"strings"
+	"testing"
+)
+
+func genFakeTree() *Thread {
+	tree := &Thread{
+		Uid: 0,
+	}
+	var prevChild *Thread
+	for i := 1; i < 3; i++ {
+		child := &Thread{
+			Uid:         uint32(i * 10),
+			Parent:      tree,
+			PrevSibling: prevChild,
+		}
+		if prevChild != nil {
+			prevChild.NextSibling = child
+		} else if tree.FirstChild == nil {
+			tree.FirstChild = child
+		} else {
+			panic("unreachable")
+		}
+		prevChild = child
+		var prevSecond *Thread
+		for j := 1; j < 3; j++ {
+			second := &Thread{
+				Uid:         child.Uid + uint32(j),
+				Parent:      child,
+				PrevSibling: prevSecond,
+			}
+			if prevSecond != nil {
+				prevSecond.NextSibling = second
+			} else if child.FirstChild == nil {
+				child.FirstChild = second
+			} else {
+				panic("unreachable")
+			}
+			prevSecond = second
+			var prevThird *Thread
+			limit := 3
+			if j == 2 {
+				limit = 8
+			}
+			for k := 1; k < limit; k++ {
+				third := &Thread{
+					Uid:         second.Uid*10 + uint32(k),
+					Parent:      second,
+					PrevSibling: prevThird,
+				}
+				if prevThird != nil {
+					prevThird.NextSibling = third
+				} else if second.FirstChild == nil {
+					second.FirstChild = third
+				} else {
+					panic("unreachable")
+				}
+				prevThird = third
+			}
+		}
+	}
+	return tree
+}
+
+func TestNewWalk(t *testing.T) {
+	tree := genFakeTree()
+	var prefix []string
+	lastLevel := 0
+	tree.Walk(func(t *Thread, lvl int, e error) error {
+		// if t.Uid%2 != 0 {
+		// 	return ErrSkipThread
+		// }
+		if e != nil {
+			fmt.Printf("ERROR: %v\n", e)
+		}
+		if lvl > lastLevel && lvl > 1 {
+			// we actually just descended... so figure out what connector we need
+			// level 1 is flush to the root, so we avoid the indentation there
+			if t.Parent.NextSibling != nil {
+				prefix = append(prefix, "│  ")
+			} else {
+				prefix = append(prefix, "   ")
+			}
+		} else if lvl < lastLevel {
+			//ascended, need to trim the prefix layers
+			diff := lastLevel - lvl
+			prefix = prefix[:len(prefix)-diff]
+		}
+
+		var arrow string
+		if t.Parent != nil {
+			if t.NextSibling != nil {
+				arrow = "├─>"
+			} else {
+				arrow = "└─>"
+			}
+		}
+
+		// format
+		fmt.Printf("%s%s%s\n", strings.Join(prefix, ""), arrow, t)
+
+		lastLevel = lvl
+		return nil
+	})
+}