Add sorting functionality

There is a command and config option. The criteria are a list of the
sort criterion and each can be individually reversed.

This only includes support for sorting in the maildir backend currently.
The other backends are not supported in this patch.

4 files changed, 319 insertions, 7 deletions

diff --git a/worker/lib/sort.go b/worker/lib/sort.go
new file mode 100644
index 00000000..36c09242
--- /dev/null
+++ b/worker/lib/sort.go
@@ -0,0 +1,253 @@
+package lib
+
+import (
+	"fmt"
+	"sort"
+	"strings"
+	"time"
+
+	"git.sr.ht/~sircmpwn/aerc/models"
+	"git.sr.ht/~sircmpwn/aerc/worker/types"
+)
+
+func Sort(messageInfos []*models.MessageInfo,
+	criteria []*types.SortCriterion) ([]uint32, error) {
+	// loop through in reverse to ensure we sort by non-primary fields first
+	for i := len(criteria) - 1; i >= 0; i-- {
+		criterion := criteria[i]
+		var err error
+		switch criterion.Field {
+		case types.SortArrival:
+			err = sortDate(messageInfos, criterion,
+				func(msgInfo *models.MessageInfo) time.Time {
+					return msgInfo.InternalDate
+				})
+		case types.SortCc:
+			err = sortAddresses(messageInfos, criterion,
+				func(msgInfo *models.MessageInfo) []*models.Address {
+					return msgInfo.Envelope.Cc
+				})
+		case types.SortDate:
+			err = sortDate(messageInfos, criterion,
+				func(msgInfo *models.MessageInfo) time.Time {
+					return msgInfo.Envelope.Date
+				})
+		case types.SortFrom:
+			err = sortAddresses(messageInfos, criterion,
+				func(msgInfo *models.MessageInfo) []*models.Address {
+					return msgInfo.Envelope.From
+				})
+		case types.SortRead:
+			err = sortFlags(messageInfos, criterion, models.SeenFlag)
+		case types.SortSize:
+			err = sortInts(messageInfos, criterion,
+				func(msgInfo *models.MessageInfo) uint32 {
+					return msgInfo.Size
+				})
+		case types.SortSubject:
+			err = sortStrings(messageInfos, criterion,
+				func(msgInfo *models.MessageInfo) string {
+					subject := strings.ToLower(msgInfo.Envelope.Subject)
+					subject = strings.TrimPrefix(subject, "re: ")
+					return strings.TrimPrefix(subject, "fwd: ")
+				})
+		case types.SortTo:
+			err = sortAddresses(messageInfos, criterion,
+				func(msgInfo *models.MessageInfo) []*models.Address {
+					return msgInfo.Envelope.To
+				})
+		}
+		if err != nil {
+			return nil, err
+		}
+	}
+	var uids []uint32
+	// copy in reverse as msgList displays backwards
+	for i := len(messageInfos) - 1; i >= 0; i-- {
+		uids = append(uids, messageInfos[i].Uid)
+	}
+	return uids, nil
+}
+
+func sortDate(messageInfos []*models.MessageInfo, criterion *types.SortCriterion,
+	getValue func(*models.MessageInfo) time.Time) error {
+	var slice []*dateStore
+	for _, msgInfo := range messageInfos {
+		slice = append(slice, &dateStore{
+			Value:   getValue(msgInfo),
+			MsgInfo: msgInfo,
+		})
+	}
+	sortSlice(criterion, dateSlice{slice})
+	for i := 0; i < len(messageInfos); i++ {
+		messageInfos[i] = slice[i].MsgInfo
+	}
+	return nil
+}
+
+func sortAddresses(messageInfos []*models.MessageInfo, criterion *types.SortCriterion,
+	getValue func(*models.MessageInfo) []*models.Address) error {
+	var slice []*addressStore
+	for _, msgInfo := range messageInfos {
+		slice = append(slice, &addressStore{
+			Value:   getValue(msgInfo),
+			MsgInfo: msgInfo,
+		})
+	}
+	sortSlice(criterion, addressSlice{slice})
+	for i := 0; i < len(messageInfos); i++ {
+		messageInfos[i] = slice[i].MsgInfo
+	}
+	return nil
+}
+
+func sortFlags(messageInfos []*models.MessageInfo, criterion *types.SortCriterion,
+	testFlag models.Flag) error {
+	var slice []*boolStore
+	for _, msgInfo := range messageInfos {
+		flagPresent := false
+		for _, flag := range msgInfo.Flags {
+			if flag == testFlag {
+				flagPresent = true
+			}
+		}
+		slice = append(slice, &boolStore{
+			Value:   flagPresent,
+			MsgInfo: msgInfo,
+		})
+	}
+	sortSlice(criterion, boolSlice{slice})
+	for i := 0; i < len(messageInfos); i++ {
+		messageInfos[i] = slice[i].MsgInfo
+	}
+	return nil
+}
+
+func sortInts(messageInfos []*models.MessageInfo, criterion *types.SortCriterion,
+	getValue func(*models.MessageInfo) uint32) error {
+	var slice []*intStore
+	for _, msgInfo := range messageInfos {
+		slice = append(slice, &intStore{
+			Value:   getValue(msgInfo),
+			MsgInfo: msgInfo,
+		})
+	}
+	sortSlice(criterion, intSlice{slice})
+	for i := 0; i < len(messageInfos); i++ {
+		messageInfos[i] = slice[i].MsgInfo
+	}
+	return nil
+}
+
+func sortStrings(messageInfos []*models.MessageInfo, criterion *types.SortCriterion,
+	getValue func(*models.MessageInfo) string) error {
+	var slice []*lexiStore
+	for _, msgInfo := range messageInfos {
+		slice = append(slice, &lexiStore{
+			Value:   getValue(msgInfo),
+			MsgInfo: msgInfo,
+		})
+	}
+	sortSlice(criterion, lexiSlice{slice})
+	for i := 0; i < len(messageInfos); i++ {
+		messageInfos[i] = slice[i].MsgInfo
+	}
+	return nil
+}
+
+type lexiStore struct {
+	Value   string
+	MsgInfo *models.MessageInfo
+}
+
+type lexiSlice struct{ Slice []*lexiStore }
+
+func (s lexiSlice) Len() int      { return len(s.Slice) }
+func (s lexiSlice) Swap(i, j int) { s.Slice[i], s.Slice[j] = s.Slice[j], s.Slice[i] }
+func (s lexiSlice) Less(i, j int) bool {
+	return s.Slice[i].Value < s.Slice[j].Value
+}
+
+type dateStore struct {
+	Value   time.Time
+	MsgInfo *models.MessageInfo
+}
+
+type dateSlice struct{ Slice []*dateStore }
+
+func (s dateSlice) Len() int      { return len(s.Slice) }
+func (s dateSlice) Swap(i, j int) { s.Slice[i], s.Slice[j] = s.Slice[j], s.Slice[i] }
+func (s dateSlice) Less(i, j int) bool {
+	return s.Slice[i].Value.Before(s.Slice[j].Value)
+}
+
+type intStore struct {
+	Value   uint32
+	MsgInfo *models.MessageInfo
+}
+
+type intSlice struct{ Slice []*intStore }
+
+func (s intSlice) Len() int      { return len(s.Slice) }
+func (s intSlice) Swap(i, j int) { s.Slice[i], s.Slice[j] = s.Slice[j], s.Slice[i] }
+func (s intSlice) Less(i, j int) bool {
+	return s.Slice[i].Value < s.Slice[j].Value
+}
+
+type addressStore struct {
+	Value   []*models.Address
+	MsgInfo *models.MessageInfo
+}
+
+type addressSlice struct{ Slice []*addressStore }
+
+func (s addressSlice) Len() int      { return len(s.Slice) }
+func (s addressSlice) Swap(i, j int) { s.Slice[i], s.Slice[j] = s.Slice[j], s.Slice[i] }
+func (s addressSlice) Less(i, j int) bool {
+	addressI, addressJ := s.Slice[i].Value, s.Slice[j].Value
+	var firstI, firstJ *models.Address
+	if len(addressI) > 0 {
+		firstI = addressI[0]
+	}
+	if len(addressJ) > 0 {
+		firstJ = addressJ[0]
+	}
+	if firstI == nil && firstJ == nil {
+		return false
+	} else if firstI == nil && firstJ != nil {
+		return false
+	} else if firstI != nil && firstJ == nil {
+		return true
+	} else /* firstI != nil && firstJ != nil */ {
+		getName := func(addr *models.Address) string {
+			if addr.Name != "" {
+				return addr.Name
+			} else {
+				return fmt.Sprintf("%s@%s", addr.Mailbox, addr.Host)
+			}
+		}
+		return getName(firstI) < getName(firstJ)
+	}
+}
+
+type boolStore struct {
+	Value   bool
+	MsgInfo *models.MessageInfo
+}
+
+type boolSlice struct{ Slice []*boolStore }
+
+func (s boolSlice) Len() int      { return len(s.Slice) }
+func (s boolSlice) Swap(i, j int) { s.Slice[i], s.Slice[j] = s.Slice[j], s.Slice[i] }
+func (s boolSlice) Less(i, j int) bool {
+	valI, valJ := s.Slice[i].Value, s.Slice[j].Value
+	return valI && !valJ
+}
+
+func sortSlice(criterion *types.SortCriterion, interfce sort.Interface) {
+	if criterion.Reverse {
+		sort.Stable(sort.Reverse(interfce))
+	} else {
+		sort.Stable(interfce)
+	}
+}
diff --git a/worker/maildir/worker.go b/worker/maildir/worker.go
index 597e0d24..1df4e09c 100644
--- a/worker/maildir/worker.go
+++ b/worker/maildir/worker.go
@@ -12,6 +12,7 @@ import (
 
 	"git.sr.ht/~sircmpwn/aerc/models"
 	"git.sr.ht/~sircmpwn/aerc/worker/handlers"
+	"git.sr.ht/~sircmpwn/aerc/worker/lib"
 	"git.sr.ht/~sircmpwn/aerc/worker/types"
 )
 
@@ -23,11 +24,12 @@ var errUnsupported = fmt.Errorf("unsupported command")
 
 // A Worker handles interfacing between aerc's UI and a group of maildirs.
 type Worker struct {
-	c            *Container
-	selected     *maildir.Dir
-	selectedName string
-	worker       *types.Worker
-	watcher      *fsnotify.Watcher
+	c                   *Container
+	selected            *maildir.Dir
+	selectedName        string
+	worker              *types.Worker
+	watcher             *fsnotify.Watcher
+	currentSortCriteria []*types.SortCriterion
 }
 
 // NewWorker creates a new maildir worker with the provided worker.
@@ -86,8 +88,13 @@ func (w *Worker) handleFSEvent(ev fsnotify.Event) {
 		w.worker.Logger.Printf("could not scan UIDs: %v", err)
 		return
 	}
+	sortedUids, err := w.sort(uids, w.currentSortCriteria)
+	if err != nil {
+		w.worker.Logger.Printf("error sorting directory: %v", err)
+		return
+	}
 	w.worker.PostMessage(&types.DirectoryContents{
-		Uids: uids,
+		Uids: sortedUids,
 	}, nil)
 	dirInfo := w.getDirectoryInfo()
 	dirInfo.Recent = len(newUnseen)
@@ -271,13 +278,45 @@ func (w *Worker) handleFetchDirectoryContents(
 		w.worker.Logger.Printf("error scanning uids: %v", err)
 		return err
 	}
+	sortedUids, err := w.sort(uids, msg.SortCriteria)
+	if err != nil {
+		w.worker.Logger.Printf("error sorting directory: %v", err)
+		return err
+	}
+	w.currentSortCriteria = msg.SortCriteria
 	w.worker.PostMessage(&types.DirectoryContents{
 		Message: types.RespondTo(msg),
-		Uids:    uids,
+		Uids:    sortedUids,
 	}, nil)
 	return nil
 }
 
+func (w *Worker) sort(uids []uint32, criteria []*types.SortCriterion) ([]uint32, error) {
+	if len(criteria) == 0 {
+		return uids, nil
+	}
+	var msgInfos []*models.MessageInfo
+	for _, uid := range uids {
+		m, err := w.c.Message(*w.selected, uid)
+		if err != nil {
+			w.worker.Logger.Printf("could not get message: %v", err)
+			continue
+		}
+		info, err := m.MessageInfo()
+		if err != nil {
+			w.worker.Logger.Printf("could not get message info: %v", err)
+			continue
+		}
+		msgInfos = append(msgInfos, info)
+	}
+	sortedUids, err := lib.Sort(msgInfos, criteria)
+	if err != nil {
+		w.worker.Logger.Printf("could not sort the messages: %v", err)
+		return nil, err
+	}
+	return sortedUids, nil
+}
+
 func (w *Worker) handleCreateDirectory(msg *types.CreateDirectory) error {
 	dir := w.c.Dir(msg.Directory)
 	if err := dir.Create(); err != nil {
diff --git a/worker/types/messages.go b/worker/types/messages.go
index 9f40b8f3..3539139a 100644
--- a/worker/types/messages.go
+++ b/worker/types/messages.go
@@ -78,6 +78,7 @@ type OpenDirectory struct {
 
 type FetchDirectoryContents struct {
 	Message
+	SortCriteria []*SortCriterion
 }
 
 type SearchDirectory struct {
diff --git a/worker/types/sort.go b/worker/types/sort.go
new file mode 100644
index 00000000..ffbcf463
--- /dev/null
+++ b/worker/types/sort.go
@@ -0,0 +1,19 @@
+package types
+
+type SortField int
+
+const (
+	SortArrival SortField = iota
+	SortCc
+	SortDate
+	SortFrom
+	SortRead
+	SortSize
+	SortSubject
+	SortTo
+)
+
+type SortCriterion struct {
+	Field   SortField
+	Reverse bool
+}