granicus.if.org Git - neomutt/blob - sort.c

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