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.

9 files changed, 491 insertions, 8 deletions

diff --git a/commands/account/sort.go b/commands/account/sort.go
new file mode 100644
index 00000000..62025785
--- /dev/null
+++ b/commands/account/sort.go
@@ -0,0 +1,85 @@
+package account
+
+import (
+	"errors"
+	"strings"
+
+	"git.sr.ht/~sircmpwn/aerc/lib/sort"
+	"git.sr.ht/~sircmpwn/aerc/widgets"
+)
+
+type Sort struct{}
+
+func init() {
+	register(Sort{})
+}
+
+func (Sort) Aliases() []string {
+	return []string{"sort"}
+}
+
+func (Sort) Complete(aerc *widgets.Aerc, args []string) []string {
+	supportedCriteria := []string{
+		"arrival",
+		"cc",
+		"date",
+		"from",
+		"read",
+		"size",
+		"subject",
+		"to",
+	}
+	if len(args) == 0 {
+		return supportedCriteria
+	}
+	last := args[len(args)-1]
+	var completions []string
+	currentPrefix := strings.Join(args, " ") + " "
+	// if there is a completed criteria then suggest all again or an option
+	for _, criteria := range append(supportedCriteria, "-r") {
+		if criteria == last {
+			for _, criteria := range supportedCriteria {
+				completions = append(completions, currentPrefix+criteria)
+			}
+			return completions
+		}
+	}
+
+	currentPrefix = strings.Join(args[:len(args)-1], " ")
+	if len(args) > 1 {
+		currentPrefix += " "
+	}
+	// last was beginning an option
+	if last == "-" {
+		return []string{currentPrefix + "-r"}
+	}
+	// the last item is not complete
+	for _, criteria := range supportedCriteria {
+		if strings.HasPrefix(criteria, last) {
+			completions = append(completions, currentPrefix+criteria)
+		}
+	}
+	return completions
+}
+
+func (Sort) Execute(aerc *widgets.Aerc, args []string) error {
+	acct := aerc.SelectedAccount()
+	if acct == nil {
+		return errors.New("No account selected.")
+	}
+	store := acct.Store()
+	if store == nil {
+		return errors.New("Messages still loading.")
+	}
+
+	sortCriteria, err := sort.GetSortCriteria(args[1:])
+	if err != nil {
+		return err
+	}
+
+	aerc.SetStatus("Sorting")
+	store.Sort(sortCriteria, func() {
+		aerc.SetStatus("Sorting complete")
+	})
+	return nil
+}
diff --git a/config/config.go b/config/config.go
index eeaf9370..5a41903f 100644
--- a/config/config.go
+++ b/config/config.go
@@ -36,6 +36,7 @@ type UIConfig struct {
 	Spinner           string   `ini:"spinner"`
 	SpinnerDelimiter  string   `ini:"spinner-delimiter"`
 	DirListFormat     string   `ini:"dirlist-format"`
+	Sort              []string `delim:" "`
 }
 
 const (
diff --git a/lib/msgstore.go b/lib/msgstore.go
index 1f18fbf1..b0392bab 100644
--- a/lib/msgstore.go
+++ b/lib/msgstore.go
@@ -25,6 +25,8 @@ type MessageStore struct {
 	resultIndex int
 	filter      bool
 
+	defaultSortCriteria []*types.SortCriterion
+
 	// Map of uids we've asked the worker to fetch
 	onUpdate       func(store *MessageStore) // TODO: multiple onUpdate handlers
 	onUpdateDirs   func()
@@ -38,6 +40,7 @@ type MessageStore struct {
 
 func NewMessageStore(worker *types.Worker,
 	dirInfo *models.DirectoryInfo,
+	defaultSortCriteria []*types.SortCriterion,
 	triggerNewEmail func(*models.MessageInfo),
 	triggerDirectoryChange func()) *MessageStore {
 
@@ -49,6 +52,8 @@ func NewMessageStore(worker *types.Worker,
 		bodyCallbacks:   make(map[uint32][]func(io.Reader)),
 		headerCallbacks: make(map[uint32][]func(*types.MessageInfo)),
 
+		defaultSortCriteria: defaultSortCriteria,
+
 		pendingBodies:  make(map[uint32]interface{}),
 		pendingHeaders: make(map[uint32]interface{}),
 		worker:         worker,
@@ -151,7 +156,9 @@ func (store *MessageStore) Update(msg types.WorkerMessage) {
 	switch msg := msg.(type) {
 	case *types.DirectoryInfo:
 		store.DirInfo = *msg.Info
-		store.worker.PostAction(&types.FetchDirectoryContents{}, nil)
+		store.worker.PostAction(&types.FetchDirectoryContents{
+			SortCriteria: store.defaultSortCriteria,
+		}, nil)
 		update = true
 	case *types.DirectoryContents:
 		newMap := make(map[uint32]*models.MessageInfo)
@@ -434,3 +441,11 @@ func (store *MessageStore) ModifyLabels(uids []uint32, add, remove []string,
 		Remove: remove,
 	}, cb)
 }
+
+func (store *MessageStore) Sort(criteria []*types.SortCriterion, cb func()) {
+	store.worker.PostAction(&types.FetchDirectoryContents{
+		SortCriteria: criteria,
+	}, func(msg types.WorkerMessage) {
+		cb()
+	})
+}
diff --git a/lib/sort/sort.go b/lib/sort/sort.go
new file mode 100644
index 00000000..89c36a90
--- /dev/null
+++ b/lib/sort/sort.go
@@ -0,0 +1,56 @@
+package sort
+
+import (
+	"errors"
+	"fmt"
+	"strings"
+
+	"git.sr.ht/~sircmpwn/aerc/worker/types"
+)
+
+func GetSortCriteria(args []string) ([]*types.SortCriterion, error) {
+	var sortCriteria []*types.SortCriterion
+	reverse := false
+	for _, arg := range args {
+		if arg == "-r" {
+			reverse = true
+			continue
+		}
+		field, err := parseSortField(arg)
+		if err != nil {
+			return nil, err
+		}
+		sortCriteria = append(sortCriteria, &types.SortCriterion{
+			Field:   field,
+			Reverse: reverse,
+		})
+		reverse = false
+	}
+	if reverse {
+		return nil, errors.New("Expected argument to reverse")
+	}
+	return sortCriteria, nil
+}
+
+func parseSortField(arg string) (types.SortField, error) {
+	switch strings.ToLower(arg) {
+	case "arrival":
+		return types.SortArrival, nil
+	case "cc":
+		return types.SortCc, nil
+	case "date":
+		return types.SortDate, nil
+	case "from":
+		return types.SortFrom, nil
+	case "read":
+		return types.SortRead, nil
+	case "size":
+		return types.SortSize, nil
+	case "subject":
+		return types.SortSubject, nil
+	case "to":
+		return types.SortTo, nil
+	default:
+		return types.SortArrival, fmt.Errorf("%v is not a valid sort criterion", arg)
+	}
+}
diff --git a/widgets/account.go b/widgets/account.go
index eb6a495b..4e8dd171 100644
--- a/widgets/account.go
+++ b/widgets/account.go
@@ -9,6 +9,7 @@ import (
 
 	"git.sr.ht/~sircmpwn/aerc/config"
 	"git.sr.ht/~sircmpwn/aerc/lib"
+	"git.sr.ht/~sircmpwn/aerc/lib/sort"
 	"git.sr.ht/~sircmpwn/aerc/lib/ui"
 	"git.sr.ht/~sircmpwn/aerc/models"
 	"git.sr.ht/~sircmpwn/aerc/worker"
@@ -218,6 +219,7 @@ func (acct *AccountView) onMessage(msg types.WorkerMessage) {
 			store.Update(msg)
 		} else {
 			store = lib.NewMessageStore(acct.worker, msg.Info,
+				acct.getSortCriteria(),
 				func(msg *models.MessageInfo) {
 					acct.conf.Triggers.ExecNewEmail(acct.acct,
 						acct.conf, msg)
@@ -254,3 +256,15 @@ func (acct *AccountView) onMessage(msg types.WorkerMessage) {
 			Color(tcell.ColorDefault, tcell.ColorRed)
 	}
 }
+
+func (acct *AccountView) getSortCriteria() []*types.SortCriterion {
+	if len(acct.conf.Ui.Sort) == 0 {
+		return nil
+	}
+	criteria, err := sort.GetSortCriteria(acct.conf.Ui.Sort)
+	if err != nil {
+		acct.aerc.PushError(" ui.sort: " + err.Error())
+		return nil
+	}
+	return criteria
+}
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
+}