1 /**
2  * @file
3  * Assorted sorting methods
4  *
5  * @authors
6  * Copyright (C) 1996-2000 Michael R. Elkins <me@mutt.org>
7  * Copyright (C) 2019 Pietro Cerutti <gahr@gahr.ch>
8  * Copyright (C) 2020 R Primus <rprimus@gmail.com>
9  *
10  * @copyright
11  * This program is free software: you can redistribute it and/or modify it under
12  * the terms of the GNU General Public License as published by the Free Software
13  * Foundation, either version 2 of the License, or (at your option) any later
14  * version.
15  *
16  * This program is distributed in the hope that it will be useful, but WITHOUT
17  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
19  * details.
20  *
21  * You should have received a copy of the GNU General Public License along with
22  * this program.  If not, see <http://www.gnu.org/licenses/>.
23  */
24 
25 /**
26  * @page neo_sort Assorted sorting methods
27  *
28  * Assorted sorting methods
29  */
30 
31 #include "config.h"
32 #include <stdbool.h>
33 #include <stdlib.h>
34 #include <string.h>
35 #include "mutt/lib.h"
36 #include "address/lib.h"
37 #include "config/lib.h"
38 #include "email/lib.h"
39 #include "core/lib.h"
40 #include "alias/lib.h"
41 #include "sort.h"
42 #include "mutt_logging.h"
43 #include "mutt_thread.h"
44 #include "mx.h"
45 #include "options.h"
46 #include "score.h"
47 #ifdef USE_NNTP
48 #include "nntp/lib.h"
49 #endif
50 
51 /**
52  * struct EmailCompare - Context for compare_email_shim()
53  */
54 struct EmailCompare
55 {
56   enum MailboxType type; ///< Current mailbox type
57   short sort;            ///< Primary sort
58   short sort_aux;        ///< Secondary sort
59 };
60 
61 /**
62  * compare_email_shim - qsort_r() comparator to drive mutt_compare_emails
63  * @param a   Pointer to first email
64  * @param b   Pointer to second email
65  * @param arg EmailCompare with needed context
66  * @retval <0 a precedes b
67  * @retval  0 a identical to b (should not happen in practice)
68  * @retval >0 b precedes a
69  */
compare_email_shim(const void * a,const void * b,void * arg)70 static int compare_email_shim(const void *a, const void *b, void *arg)
71 {
72   const struct Email *ea = *(struct Email const *const *) a;
73   const struct Email *eb = *(struct Email const *const *) b;
74   const struct EmailCompare *cmp = arg;
75   return mutt_compare_emails(ea, eb, cmp->type, cmp->sort, cmp->sort_aux);
76 }
77 
78 /**
79  * compare_score - Compare two emails using their scores - Implements ::sort_mail_t - @ingroup sort_mail_api
80  */
compare_score(const struct Email * a,const struct Email * b,bool reverse)81 static int compare_score(const struct Email *a, const struct Email *b, bool reverse)
82 {
83   int result = b->score - a->score; /* note that this is reverse */
84   return reverse ? -result : result;
85 }
86 
87 /**
88  * compare_size - Compare the size of two emails - Implements ::sort_mail_t - @ingroup sort_mail_api
89  */
compare_size(const struct Email * a,const struct Email * b,bool reverse)90 static int compare_size(const struct Email *a, const struct Email *b, bool reverse)
91 {
92   int result = a->body->length - b->body->length;
93   return reverse ? -result : result;
94 }
95 
96 /**
97  * compare_date_sent - Compare the sent date of two emails - Implements ::sort_mail_t - @ingroup sort_mail_api
98  */
compare_date_sent(const struct Email * a,const struct Email * b,bool reverse)99 static int compare_date_sent(const struct Email *a, const struct Email *b, bool reverse)
100 {
101   int result = a->date_sent - b->date_sent;
102   return reverse ? -result : result;
103 }
104 
105 /**
106  * compare_subject - Compare the subject of two emails - Implements ::sort_mail_t - @ingroup sort_mail_api
107  */
compare_subject(const struct Email * a,const struct Email * b,bool reverse)108 static int compare_subject(const struct Email *a, const struct Email *b, bool reverse)
109 {
110   int rc;
111 
112   if (!a->env->real_subj)
113   {
114     if (!b->env->real_subj)
115       rc = compare_date_sent(a, b, false);
116     else
117       rc = -1;
118   }
119   else if (!b->env->real_subj)
120     rc = 1;
121   else
122     rc = mutt_istr_cmp(a->env->real_subj, b->env->real_subj);
123   return reverse ? -rc : rc;
124 }
125 
126 /**
127  * mutt_get_name - Pick the best name to display from an address
128  * @param a Address to use
129  * @retval ptr Display name
130  *
131  * This function uses:
132  * 1. Alias for email address
133  * 2. Personal name
134  * 3. Email address
135  */
mutt_get_name(const struct Address * a)136 const char *mutt_get_name(const struct Address *a)
137 {
138   struct Address *ali = NULL;
139 
140   if (a)
141   {
142     const bool c_reverse_alias = cs_subset_bool(NeoMutt->sub, "reverse_alias");
143     if (c_reverse_alias && (ali = alias_reverse_lookup(a)) && ali->personal)
144       return ali->personal;
145     if (a->personal)
146       return a->personal;
147     if (a->mailbox)
148       return mutt_addr_for_display(a);
149   }
150   /* don't return NULL to avoid segfault when printing/comparing */
151   return "";
152 }
153 
154 /**
155  * compare_to - Compare the 'to' fields of two emails - Implements ::sort_mail_t - @ingroup sort_mail_api
156  */
compare_to(const struct Email * a,const struct Email * b,bool reverse)157 static int compare_to(const struct Email *a, const struct Email *b, bool reverse)
158 {
159   char fa[128];
160 
161   mutt_str_copy(fa, mutt_get_name(TAILQ_FIRST(&a->env->to)), sizeof(fa));
162   const char *fb = mutt_get_name(TAILQ_FIRST(&b->env->to));
163   int result = mutt_istrn_cmp(fa, fb, sizeof(fa));
164   return reverse ? -result : result;
165 }
166 
167 /**
168  * compare_from - Compare the 'from' fields of two emails - Implements ::sort_mail_t - @ingroup sort_mail_api
169  */
compare_from(const struct Email * a,const struct Email * b,bool reverse)170 static int compare_from(const struct Email *a, const struct Email *b, bool reverse)
171 {
172   char fa[128];
173 
174   mutt_str_copy(fa, mutt_get_name(TAILQ_FIRST(&a->env->from)), sizeof(fa));
175   const char *fb = mutt_get_name(TAILQ_FIRST(&b->env->from));
176   int result = mutt_istrn_cmp(fa, fb, sizeof(fa));
177   return reverse ? -result : result;
178 }
179 
180 /**
181  * compare_date_received - Compare the date received of two emails - Implements ::sort_mail_t - @ingroup sort_mail_api
182  */
compare_date_received(const struct Email * a,const struct Email * b,bool reverse)183 static int compare_date_received(const struct Email *a, const struct Email *b, bool reverse)
184 {
185   int result = a->received - b->received;
186   return reverse ? -result : result;
187 }
188 
189 /**
190  * compare_order - Restore the 'unsorted' order of emails - Implements ::sort_mail_t - @ingroup sort_mail_api
191  */
compare_order(const struct Email * a,const struct Email * b,bool reverse)192 static int compare_order(const struct Email *a, const struct Email *b, bool reverse)
193 {
194   int result = a->index - b->index;
195   return reverse ? -result : result;
196 }
197 
198 /**
199  * compare_spam - Compare the spam values of two emails - Implements ::sort_mail_t - @ingroup sort_mail_api
200  */
compare_spam(const struct Email * a,const struct Email * b,bool reverse)201 static int compare_spam(const struct Email *a, const struct Email *b, bool reverse)
202 {
203   char *aptr = NULL, *bptr = NULL;
204   int ahas, bhas;
205   int result = 0;
206   double difference;
207 
208   /* Firstly, require spam attributes for both msgs */
209   /* to compare. Determine which msgs have one.     */
210   ahas = a->env && !mutt_buffer_is_empty(&a->env->spam);
211   bhas = b->env && !mutt_buffer_is_empty(&b->env->spam);
212 
213   /* If one msg has spam attr but other does not, sort the one with first. */
214   if (ahas && !bhas)
215     return reverse ? -1 : 1;
216   if (!ahas && bhas)
217     return reverse ? 1 : -1;
218 
219   /* Else, if neither has a spam attr, presume equality. Fall back on aux. */
220   if (!ahas && !bhas)
221     return 0;
222 
223   /* Both have spam attrs. */
224 
225   /* preliminary numeric examination */
226   difference = (strtod(a->env->spam.data, &aptr) - strtod(b->env->spam.data, &bptr));
227 
228   /* map double into comparison (-1, 0, or 1) */
229   result = ((difference < 0.0) ? -1 : (difference > 0.0) ? 1 : 0);
230 
231   /* If either aptr or bptr is equal to data, there is no numeric    */
232   /* value for that spam attribute. In this case, compare lexically. */
233   if ((aptr == a->env->spam.data) || (bptr == b->env->spam.data))
234   {
235     result = strcmp(aptr, bptr);
236     return reverse ? -result : result;
237   }
238 
239   /* Otherwise, we have numeric value for both attrs. If these values */
240   /* are equal, then we first fall back upon string comparison, then  */
241   /* upon auxiliary sort.                                             */
242   if (result == 0)
243     result = strcmp(aptr, bptr);
244   return reverse ? -result : result;
245 }
246 
247 /**
248  * compare_label - Compare the labels of two emails - Implements ::sort_mail_t - @ingroup sort_mail_api
249  */
compare_label(const struct Email * a,const struct Email * b,bool reverse)250 static int compare_label(const struct Email *a, const struct Email *b, bool reverse)
251 {
252   int ahas, bhas, result = 0;
253 
254   /* As with compare_spam, not all messages will have the x-label
255    * property.  Blank X-Labels are treated as null in the index
256    * display, so we'll consider them as null for sort, too.       */
257   ahas = a->env && a->env->x_label && *(a->env->x_label);
258   bhas = b->env && b->env->x_label && *(b->env->x_label);
259 
260   /* First we bias toward a message with a label, if the other does not. */
261   if (ahas && !bhas)
262     return reverse ? 1 : -1;
263   if (!ahas && bhas)
264     return reverse ? -1 : 1;
265 
266   /* If neither has a label, use aux sort. */
267   if (!ahas && !bhas)
268     return 0;
269 
270   /* If both have a label, we just do a lexical compare. */
271   result = mutt_istr_cmp(a->env->x_label, b->env->x_label);
272   return reverse ? -result : result;
273 }
274 
275 /**
276  * get_sort_func - Get the sort function for a given sort id
277  * @param method Sort type, see #SortType
278  * @param type   The Mailbox type
279  * @retval ptr sort function - Implements ::sort_mail_t
280  */
get_sort_func(enum SortType method,enum MailboxType type)281 static sort_mail_t get_sort_func(enum SortType method, enum MailboxType type)
282 {
283   switch (method)
284   {
285     case SORT_DATE:
286       return compare_date_sent;
287     case SORT_FROM:
288       return compare_from;
289     case SORT_LABEL:
290       return compare_label;
291     case SORT_ORDER:
292 #ifdef USE_NNTP
293       if (type == MUTT_NNTP)
294         return nntp_compare_order;
295       else
296 #endif
297         return compare_order;
298     case SORT_RECEIVED:
299       return compare_date_received;
300     case SORT_SCORE:
301       return compare_score;
302     case SORT_SIZE:
303       return compare_size;
304     case SORT_SPAM:
305       return compare_spam;
306     case SORT_SUBJECT:
307       return compare_subject;
308     case SORT_TO:
309       return compare_to;
310     default:
311       mutt_error(_("Could not find sorting function [report this bug]"));
312       return NULL;
313   }
314   /* not reached */
315 }
316 
317 /**
318  * mutt_compare_emails - Compare two emails using up to two sort methods
319  * @param a        First email
320  * @param b        Second email
321  * @param type     Mailbox type
322  * @param sort     Primary sort to use (generally $sort)
323  * @param sort_aux Secondary sort (generally $sort_aux or SORT_ORDER)
324  * @retval <0 a precedes b
325  * @retval  0 a and b are identical (should not happen in practice)
326  * @retval >0 b precedes a
327  */
mutt_compare_emails(const struct Email * a,const struct Email * b,enum MailboxType type,short sort,short sort_aux)328 int mutt_compare_emails(const struct Email *a, const struct Email *b,
329                         enum MailboxType type, short sort, short sort_aux)
330 {
331   sort_mail_t func = get_sort_func(sort & SORT_MASK, type);
332   int retval = func(a, b, (sort & SORT_REVERSE) != 0);
333   if (retval == 0)
334   {
335     func = get_sort_func(sort_aux & SORT_MASK, type);
336     retval = func(a, b, (sort_aux & SORT_REVERSE) != 0);
337   }
338   if (retval == 0)
339   {
340     /* Fallback of last resort to preserve stable order; will only
341      * return 0 if a and b have the same index, which is probably a
342      * bug in the code. */
343     func = compare_order;
344     retval = func(a, b, false);
345   }
346   return retval;
347 }
348 
349 /**
350  * mutt_sort_headers - Sort emails by their headers
351  * @param m       Mailbox
352  * @param threads Threads context
353  * @param init If true, rebuild the thread
354  * @param[out] vsize Size in bytes of the messages in view
355  */
mutt_sort_headers(struct Mailbox * m,struct ThreadsContext * threads,bool init,off_t * vsize)356 void mutt_sort_headers(struct Mailbox *m, struct ThreadsContext *threads,
357                        bool init, off_t *vsize)
358 {
359   if (!m || !m->emails[0])
360     return;
361 
362   OptNeedResort = false;
363 
364   if (m->msg_count == 0)
365   {
366     /* this function gets called by mutt_sync_mailbox(), which may have just
367      * deleted all the messages.  the virtual message numbers are not updated
368      * in that routine, so we must make sure to zero the vcount member.  */
369     m->vcount = 0;
370     mutt_clear_threads(threads);
371     *vsize = 0;
372     return; /* nothing to do! */
373   }
374 
375   if (m->verbose)
376     mutt_message(_("Sorting mailbox..."));
377 
378   const bool c_score = cs_subset_bool(NeoMutt->sub, "score");
379   if (OptNeedRescore && c_score)
380   {
381     for (int i = 0; i < m->msg_count; i++)
382     {
383       struct Email *e = m->emails[i];
384       if (!e)
385         break;
386       mutt_score_message(m, e, true);
387     }
388   }
389   OptNeedRescore = false;
390 
391   if (OptResortInit)
392   {
393     OptResortInit = false;
394     init = true;
395   }
396 
397   if (init)
398     mutt_clear_threads(threads);
399 
400   const bool threaded = mutt_using_threads();
401   if (threaded)
402   {
403     mutt_sort_threads(threads, init);
404   }
405   else
406   {
407     struct EmailCompare cmp;
408     cmp.type = mx_type(m);
409     cmp.sort = cs_subset_sort(NeoMutt->sub, "sort");
410     cmp.sort_aux = cs_subset_sort(NeoMutt->sub, "sort_aux");
411     mutt_qsort_r((void *) m->emails, m->msg_count, sizeof(struct Email *),
412                  compare_email_shim, &cmp);
413   }
414 
415   /* adjust the virtual message numbers */
416   m->vcount = 0;
417   for (int i = 0; i < m->msg_count; i++)
418   {
419     struct Email *e_cur = m->emails[i];
420     if (!e_cur)
421       break;
422 
423     if ((e_cur->vnum != -1) || (e_cur->collapsed && e_cur->visible))
424     {
425       e_cur->vnum = m->vcount;
426       m->v2r[m->vcount] = i;
427       m->vcount++;
428     }
429     e_cur->msgno = i;
430   }
431 
432   /* re-collapse threads marked as collapsed */
433   if (threaded)
434   {
435     mutt_thread_collapse_collapsed(threads);
436     *vsize = mutt_set_vnum(m);
437   }
438 
439   if (m->verbose)
440     mutt_clear_error();
441 
442   return;
443 }
444