thread.c

   1 /*
   2  * Copyright (C) 1996-2002 Michael R. Elkins <me@mutt.org>
   3  *
   4  *     This program is free software; you can redistribute it and/or modify
   5  *     it under the terms of the GNU General Public License as published by
   6  *     the Free Software Foundation; either version 2 of the License, or
   7  *     (at your option) any later version.
   8  *
   9  *     This program is distributed in the hope that it will be useful,
  10  *     but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  *     GNU General Public License for more details.
  13  *
  14  *     You should have received a copy of the GNU General Public License
  15  *     along with this program; if not, write to the Free Software
  16  *     Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111, USA.
  17  */
  18
  19 #if HAVE_CONFIG_H
  20 # include "config.h"
  21 #endif
  22
  23 #include "mutt.h"
  24 #include "sort.h"
  25
  26 #include <string.h>
  27 #include <ctype.h>
  28
  29 #define VISIBLE(hdr, ctx) (hdr->virtual >= 0 || (hdr->collapsed && (!ctx->pattern || hdr->limited)))
  30
  31 /* determine whether a is a descendant of b */
  32 static int is_descendant (THREAD * a, THREAD * b)
  33 {
  34   while (a) {
  35     if (a == b)
  36       return (1);
  37     a = a->parent;
  38   }
  39   return (0);
  40 }
  41
  42 /* Determines whether to display a message's subject. */
  43 static int need_display_subject (CONTEXT * ctx, HEADER * hdr)
  44 {
  45   THREAD *tmp, *tree = hdr->thread;
  46
  47   /* if the user disabled subject hiding, display it */
  48   if (!option (OPTHIDETHREADSUBJECT))
  49     return (1);
  50
  51   /* if our subject is different from our parent's, display it */
  52   if (hdr->subject_changed)
  53     return (1);
  54
  55   /* if our subject is different from that of our closest previously displayed
  56    * sibling, display the subject */
  57   for (tmp = tree->prev; tmp; tmp = tmp->prev) {
  58     hdr = tmp->message;
  59     if (hdr && VISIBLE (hdr, ctx)) {
  60       if (hdr->subject_changed)
  61         return (1);
  62       else
  63         break;
  64     }
  65   }
  66
  67   /* if there is a parent-to-child subject change anywhere between us and our
  68    * closest displayed ancestor, display the subject */
  69   for (tmp = tree->parent; tmp; tmp = tmp->parent) {
  70     hdr = tmp->message;
  71     if (hdr) {
  72       if (VISIBLE (hdr, ctx))
  73         return (0);
  74       else if (hdr->subject_changed)
  75         return (1);
  76     }
  77   }
  78
  79   /* if we have no visible parent or previous sibling, display the subject */
  80   return (1);
  81 }
  82
  83 static void linearize_tree (CONTEXT * ctx)
  84 {
  85   THREAD *tree = ctx->tree;
  86   HEADER **array = ctx->hdrs + (Sort & SORT_REVERSE ? ctx->msgcount - 1 : 0);
  87
  88   while (tree) {
  89     while (!tree->message)
  90       tree = tree->child;
  91
  92     *array = tree->message;
  93     array += Sort & SORT_REVERSE ? -1 : 1;
  94
  95     if (tree->child)
  96       tree = tree->child;
  97     else {
  98       while (tree) {
  99         if (tree->next) {
 100           tree = tree->next;
 101           break;
 102         }
 103         else
 104           tree = tree->parent;
 105       }
 106     }
 107   }
 108 }
 109
 110 /* this calculates whether a node is the root of a subtree that has visible
 111  * nodes, whether a node itself is visible, whether, if invisible, it has
 112  * depth anyway, and whether any of its later siblings are roots of visible
 113  * subtrees.  while it's at it, it frees the old thread display, so we can
 114  * skip parts of the tree in mutt_draw_tree() if we've decided here that we
 115  * don't care about them any more.
 116  */
 117 static void calculate_visibility (CONTEXT * ctx, int *max_depth)
 118 {
 119   THREAD *tmp, *tree = ctx->tree;
 120   int hide_top_missing = option (OPTHIDETOPMISSING)
 121     && !option (OPTHIDEMISSING);
 122   int hide_top_limited = option (OPTHIDETOPLIMITED)
 123     && !option (OPTHIDELIMITED);
 124   int depth = 0;
 125
 126   /* we walk each level backwards to make it easier to compute next_subtree_visible */
 127   while (tree->next)
 128     tree = tree->next;
 129   *max_depth = 0;
 130
 131   FOREVER {
 132     if (depth > *max_depth)
 133       *max_depth = depth;
 134
 135     tree->subtree_visible = 0;
 136     if (tree->message) {
 137       FREE (&tree->message->tree);
 138       if (VISIBLE (tree->message, ctx)) {
 139         tree->deep = 1;
 140         tree->visible = 1;
 141         tree->message->display_subject =
 142           need_display_subject (ctx, tree->message);
 143         for (tmp = tree; tmp; tmp = tmp->parent) {
 144           if (tmp->subtree_visible) {
 145             tmp->deep = 1;
 146             tmp->subtree_visible = 2;
 147             break;
 148           }
 149           else
 150             tmp->subtree_visible = 1;
 151         }
 152       }
 153       else {
 154         tree->visible = 0;
 155         tree->deep = !option (OPTHIDELIMITED);
 156       }
 157     }
 158     else {
 159       tree->visible = 0;
 160       tree->deep = !option (OPTHIDEMISSING);
 161     }
 162     tree->next_subtree_visible = tree->next
 163       && (tree->next->next_subtree_visible || tree->next->subtree_visible);
 164     if (tree->child) {
 165       depth++;
 166       tree = tree->child;
 167       while (tree->next)
 168         tree = tree->next;
 169     }
 170     else if (tree->prev)
 171       tree = tree->prev;
 172     else {
 173       while (tree && !tree->prev) {
 174         depth--;
 175         tree = tree->parent;
 176       }
 177       if (!tree)
 178         break;
 179       else
 180         tree = tree->prev;
 181     }
 182   }
 183
 184   /* now fix up for the OPTHIDETOP* options if necessary */
 185   if (hide_top_limited || hide_top_missing) {
 186     tree = ctx->tree;
 187     FOREVER {
 188       if (!tree->visible && tree->deep && tree->subtree_visible < 2
 189           && ((tree->message && hide_top_limited)
 190               || (!tree->message && hide_top_missing)))
 191         tree->deep = 0;
 192       if (!tree->deep && tree->child && tree->subtree_visible)
 193         tree = tree->child;
 194       else if (tree->next)
 195         tree = tree->next;
 196       else {
 197         while (tree && !tree->next)
 198           tree = tree->parent;
 199         if (!tree)
 200           break;
 201         else
 202           tree = tree->next;
 203       }
 204     }
 205   }
 206 }
 207
 208 /* Since the graphics characters have a value >255, I have to resort to
 209  * using escape sequences to pass the information to print_enriched_string().
 210  * These are the macros M_TREE_* defined in mutt.h.
 211  *
 212  * ncurses should automatically use the default ASCII characters instead of
 213  * graphics chars on terminals which don't support them (see the man page
 214  * for curs_addch).
 215  */
 216 void mutt_draw_tree (CONTEXT * ctx)
 217 {
 218   char *pfx = NULL, *mypfx = NULL, *arrow = NULL, *myarrow = NULL, *new_tree;
 219   char corner = (Sort & SORT_REVERSE) ? M_TREE_ULCORNER : M_TREE_LLCORNER;
 220   char vtee = (Sort & SORT_REVERSE) ? M_TREE_BTEE : M_TREE_TTEE;
 221   int depth = 0, start_depth = 0, max_depth = 0, width =
 222     option (OPTNARROWTREE) ? 1 : 2;
 223   THREAD *nextdisp = NULL, *pseudo = NULL, *parent = NULL, *tree = ctx->tree;
 224
 225   /* Do the visibility calculations and free the old thread chars.
 226    * From now on we can simply ignore invisible subtrees
 227    */
 228   calculate_visibility (ctx, &max_depth);
 229   pfx = safe_malloc (width * max_depth + 2);
 230   arrow = safe_malloc (width * max_depth + 2);
 231   while (tree) {
 232     if (depth) {
 233       myarrow = arrow + (depth - start_depth - (start_depth ? 0 : 1)) * width;
 234       if (depth && start_depth == depth)
 235         myarrow[0] = nextdisp ? M_TREE_LTEE : corner;
 236       else if (parent->message && !option (OPTHIDELIMITED))
 237         myarrow[0] = M_TREE_HIDDEN;
 238       else if (!parent->message && !option (OPTHIDEMISSING))
 239         myarrow[0] = M_TREE_MISSING;
 240       else
 241         myarrow[0] = vtee;
 242       if (width == 2)
 243         myarrow[1] = pseudo ? M_TREE_STAR
 244           : (tree->duplicate_thread ? M_TREE_EQUALS : M_TREE_HLINE);
 245       if (tree->visible) {
 246         myarrow[width] = M_TREE_RARROW;
 247         myarrow[width + 1] = 0;
 248         new_tree = safe_malloc ((2 + depth * width));
 249         if (start_depth > 1) {
 250           strncpy (new_tree, pfx, (start_depth - 1) * width);
 251           strfcpy (new_tree + (start_depth - 1) * width,
 252                    arrow, (1 + depth - start_depth) * width + 2);
 253         }
 254         else
 255           strfcpy (new_tree, arrow, 2 + depth * width);
 256         tree->message->tree = new_tree;
 257       }
 258     }
 259     if (tree->child && depth) {
 260       mypfx = pfx + (depth - 1) * width;
 261       mypfx[0] = nextdisp ? M_TREE_VLINE : M_TREE_SPACE;
 262       if (width == 2)
 263         mypfx[1] = M_TREE_SPACE;
 264     }
 265     parent = tree;
 266     nextdisp = NULL;
 267     pseudo = NULL;
 268     do {
 269       if (tree->child && tree->subtree_visible) {
 270         if (tree->deep)
 271           depth++;
 272         if (tree->visible)
 273           start_depth = depth;
 274         tree = tree->child;
 275
 276         /* we do this here because we need to make sure that the first child thread
 277          * of the old tree that we deal with is actually displayed if any are,
 278          * or we might set the parent variable wrong while going through it. */
 279         while (!tree->subtree_visible && tree->next)
 280           tree = tree->next;
 281       }
 282       else {
 283         while (!tree->next && tree->parent) {
 284           if (tree == pseudo)
 285             pseudo = NULL;
 286           if (tree == nextdisp)
 287             nextdisp = NULL;
 288           if (tree->visible)
 289             start_depth = depth;
 290           tree = tree->parent;
 291           if (tree->deep) {
 292             if (start_depth == depth)
 293               start_depth--;
 294             depth--;
 295           }
 296         }
 297         if (tree == pseudo)
 298           pseudo = NULL;
 299         if (tree == nextdisp)
 300           nextdisp = NULL;
 301         if (tree->visible)
 302           start_depth = depth;
 303         tree = tree->next;
 304         if (!tree)
 305           break;
 306       }
 307       if (!pseudo && tree->fake_thread)
 308         pseudo = tree;
 309       if (!nextdisp && tree->next_subtree_visible)
 310         nextdisp = tree;
 311     }
 312     while (!tree->deep);
 313   }
 314
 315   FREE (&pfx);
 316   FREE (&arrow);
 317 }
 318
 319 /* since we may be trying to attach as a pseudo-thread a THREAD that
 320  * has no message, we have to make a list of all the subjects of its
 321  * most immediate existing descendants.  we also note the earliest
 322  * date on any of the parents and put it in *dateptr. */
 323 static LIST *make_subject_list (THREAD * cur, time_t * dateptr)
 324 {
 325   THREAD *start = cur;
 326   ENVELOPE *env;
 327   time_t thisdate;
 328   LIST *curlist, *oldlist, *newlist, *subjects = NULL;
 329   int rc = 0;
 330
 331   FOREVER {
 332     while (!cur->message)
 333       cur = cur->child;
 334
 335     if (dateptr) {
 336       thisdate = option (OPTTHREADRECEIVED)
 337         ? cur->message->received : cur->message->date_sent;
 338       if (!*dateptr || thisdate < *dateptr)
 339         *dateptr = thisdate;
 340     }
 341
 342     env = cur->message->env;
 343     if (env->real_subj &&
 344         ((env->real_subj != env->subject) || (!option (OPTSORTRE)))) {
 345       for (curlist = subjects, oldlist = NULL;
 346            curlist; oldlist = curlist, curlist = curlist->next) {
 347         rc = mutt_strcmp (env->real_subj, curlist->data);
 348         if (rc >= 0)
 349           break;
 350       }
 351       if (!curlist || rc > 0) {
 352         newlist = safe_calloc (1, sizeof (LIST));
 353         newlist->data = env->real_subj;
 354         if (oldlist) {
 355           newlist->next = oldlist->next;
 356           oldlist->next = newlist;
 357         }
 358         else {
 359           newlist->next = subjects;
 360           subjects = newlist;
 361         }
 362       }
 363     }
 364
 365     while (!cur->next && cur != start) {
 366       cur = cur->parent;
 367     }
 368     if (cur == start)
 369       break;
 370     cur = cur->next;
 371   }
 372
 373   return (subjects);
 374 }
 375
 376 /* find the best possible match for a parent mesage based upon subject.
 377  * if there are multiple matches, the one which was sent the latest, but
 378  * before the current message, is used.
 379  */
 380 static THREAD *find_subject (CONTEXT * ctx, THREAD * cur)
 381 {
 382   struct hash_elem *ptr;
 383   THREAD *tmp, *last = NULL;
 384   int hash;
 385   LIST *subjects = NULL, *oldlist;
 386   time_t date = 0;
 387
 388   subjects = make_subject_list (cur, &date);
 389
 390   while (subjects) {
 391     hash = hash_string ((unsigned char *) subjects->data,
 392                         ctx->subj_hash->nelem);
 393     for (ptr = ctx->subj_hash->table[hash]; ptr; ptr = ptr->next) {
 394       tmp = ((HEADER *) ptr->data)->thread;
 395       if (tmp != cur &&         /* don't match the same message */
 396           !tmp->fake_thread &&  /* don't match pseudo threads */
 397           tmp->message->subject_changed &&      /* only match interesting replies */
 398           !is_descendant (tmp, cur) &&  /* don't match in the same thread */
 399           (date >= (option (OPTTHREADRECEIVED) ?
 400                     tmp->message->received :
 401                     tmp->message->date_sent)) &&
 402           (!last ||
 403            (option (OPTTHREADRECEIVED) ?
 404             (last->message->received < tmp->message->received) :
 405             (last->message->date_sent < tmp->message->date_sent))) &&
 406           tmp->message->env->real_subj &&
 407           mutt_strcmp (subjects->data, tmp->message->env->real_subj) == 0)
 408         last = tmp;             /* best match so far */
 409     }
 410
 411     oldlist = subjects;
 412     subjects = subjects->next;
 413     FREE (&oldlist);
 414   }
 415   return (last);
 416 }
 417
 418 /* remove cur and its descendants from their current location.
 419  * also make sure ancestors of cur no longer are sorted by the
 420  * fact that cur is their descendant. */
 421 static void unlink_message (THREAD ** old, THREAD * cur)
 422 {
 423   THREAD *tmp;
 424
 425   if (cur->prev)
 426     cur->prev->next = cur->next;
 427   else
 428     *old = cur->next;
 429
 430   if (cur->next)
 431     cur->next->prev = cur->prev;
 432
 433   if (cur->sort_key) {
 434     for (tmp = cur->parent; tmp && tmp->sort_key == cur->sort_key;
 435          tmp = tmp->parent)
 436       tmp->sort_key = NULL;
 437   }
 438 }
 439
 440 /* add cur as a prior sibling of *new, with parent newparent */
 441 static void insert_message (THREAD ** new, THREAD * newparent, THREAD * cur)
 442 {
 443   if (*new)
 444     (*new)->prev = cur;
 445
 446   cur->parent = newparent;
 447   cur->next = *new;
 448   cur->prev = NULL;
 449   *new = cur;
 450 }
 451
 452 /* thread by subject things that didn't get threaded by message-id */
 453 static void pseudo_threads (CONTEXT * ctx)
 454 {
 455   THREAD *tree = ctx->tree, *top = tree;
 456   THREAD *tmp, *cur, *parent, *curchild, *nextchild;
 457
 458   if (!ctx->subj_hash)
 459     ctx->subj_hash = mutt_make_subj_hash (ctx);
 460
 461   while (tree) {
 462     cur = tree;
 463     tree = tree->next;
 464     if ((parent = find_subject (ctx, cur)) != NULL) {
 465       cur->fake_thread = 1;
 466       unlink_message (&top, cur);
 467       insert_message (&parent->child, parent, cur);
 468       parent->sort_children = 1;
 469       tmp = cur;
 470       FOREVER {
 471         while (!tmp->message)
 472           tmp = tmp->child;
 473
 474         /* if the message we're attaching has pseudo-children, they
 475          * need to be attached to its parent, so move them up a level.
 476          * but only do this if they have the same real subject as the
 477          * parent, since otherwise they rightly belong to the message
 478          * we're attaching. */
 479         if (tmp == cur
 480             || !mutt_strcmp (tmp->message->env->real_subj,
 481                              parent->message->env->real_subj)) {
 482           tmp->message->subject_changed = 0;
 483
 484           for (curchild = tmp->child; curchild;) {
 485             nextchild = curchild->next;
 486             if (curchild->fake_thread) {
 487               unlink_message (&tmp->child, curchild);
 488               insert_message (&parent->child, parent, curchild);
 489             }
 490             curchild = nextchild;
 491           }
 492         }
 493
 494         while (!tmp->next && tmp != cur) {
 495           tmp = tmp->parent;
 496         }
 497         if (tmp == cur)
 498           break;
 499         tmp = tmp->next;
 500       }
 501     }
 502   }
 503   ctx->tree = top;
 504 }
 505
 506
 507 void mutt_clear_threads (CONTEXT * ctx)
 508 {
 509   int i;
 510
 511   for (i = 0; i < ctx->msgcount; i++) {
 512     ctx->hdrs[i]->thread = NULL;
 513     ctx->hdrs[i]->threaded = 0;
 514   }
 515   ctx->tree = NULL;
 516
 517   if (ctx->thread_hash)
 518     hash_destroy (&ctx->thread_hash, free);
 519 }
 520
 521 int compare_threads (const void *a, const void *b)
 522 {
 523   static sort_t *sort_func = NULL;
 524
 525   if (a || b)
 526     return ((*sort_func) (&(*((THREAD **) a))->sort_key,
 527                           &(*((THREAD **) b))->sort_key));
 528   /* a hack to let us reset sort_func even though we can't
 529    * have extra arguments because of qsort
 530    */
 531   else {
 532     sort_func = NULL;
 533     sort_func = mutt_get_sort_func (Sort);
 534     return (sort_func ? 1 : 0);
 535   }
 536 }
 537
 538 THREAD *mutt_sort_subthreads (THREAD * thread, int init)
 539 {
 540   THREAD **array, *sort_key, *top, *tmp;
 541   HEADER *oldsort_key;
 542   int i, array_size, sort_top = 0;
 543
 544   /* we put things into the array backwards to save some cycles,
 545    * but we want to have to move less stuff around if we're
 546    * resorting, so we sort backwards and then put them back
 547    * in reverse order so they're forwards
 548    */
 549   Sort ^= SORT_REVERSE;
 550   if (!compare_threads (NULL, NULL))
 551     return (thread);
 552
 553   top = thread;
 554
 555   array = safe_calloc ((array_size = 256), sizeof (THREAD *));
 556   while (1) {
 557     if (init || !thread->sort_key) {
 558       thread->sort_key = NULL;
 559
 560       if (thread->parent)
 561         thread->parent->sort_children = 1;
 562       else
 563         sort_top = 1;
 564     }
 565
 566     if (thread->child) {
 567       thread = thread->child;
 568       continue;
 569     }
 570     else {
 571       /* if it has no children, it must be real. sort it on its own merits */
 572       thread->sort_key = thread->message;
 573
 574       if (thread->next) {
 575         thread = thread->next;
 576         continue;
 577       }
 578     }
 579
 580     while (!thread->next) {
 581       /* if it has siblings and needs to be sorted, sort it... */
 582       if (thread->prev
 583           && (thread->parent ? thread->parent->sort_children : sort_top)) {
 584         /* put them into the array */
 585         for (i = 0; thread; i++, thread = thread->prev) {
 586           if (i >= array_size)
 587             safe_realloc (&array, (array_size *= 2) * sizeof (THREAD *));
 588
 589           array[i] = thread;
 590         }
 591
 592         qsort ((void *) array, i, sizeof (THREAD *), compare_threads);
 593
 594         /* attach them back together.  make thread the last sibling. */
 595         thread = array[0];
 596         thread->next = NULL;
 597         array[i - 1]->prev = NULL;
 598
 599         if (thread->parent)
 600           thread->parent->child = array[i - 1];
 601         else
 602           top = array[i - 1];
 603
 604         while (--i) {
 605           array[i - 1]->prev = array[i];
 606           array[i]->next = array[i - 1];
 607         }
 608       }
 609
 610       if (thread->parent) {
 611         tmp = thread;
 612         thread = thread->parent;
 613
 614         if (!thread->sort_key || thread->sort_children) {
 615           /* make sort_key the first or last sibling, as appropriate */
 616           sort_key =
 617             (!(Sort & SORT_LAST) ^ !(Sort & SORT_REVERSE)) ? thread->
 618             child : tmp;
 619
 620           /* we just sorted its children */
 621           thread->sort_children = 0;
 622
 623           oldsort_key = thread->sort_key;
 624           thread->sort_key = thread->message;
 625
 626           if (Sort & SORT_LAST) {
 627             if (!thread->sort_key || ((((Sort & SORT_REVERSE) ? 1 : -1)
 628                                        * compare_threads ((void *) &thread,
 629                                                           (void *) &sort_key))
 630                                       > 0))
 631               thread->sort_key = sort_key->sort_key;
 632           }
 633           else if (!thread->sort_key)
 634             thread->sort_key = sort_key->sort_key;
 635
 636           /* if its sort_key has changed, we need to resort it and siblings */
 637           if (oldsort_key != thread->sort_key) {
 638             if (thread->parent)
 639               thread->parent->sort_children = 1;
 640             else
 641               sort_top = 1;
 642           }
 643         }
 644       }
 645       else {
 646         Sort ^= SORT_REVERSE;
 647         FREE (&array);
 648         return (top);
 649       }
 650     }
 651
 652     thread = thread->next;
 653   }
 654 }
 655
 656 static void check_subjects (CONTEXT * ctx, int init)
 657 {
 658   HEADER *cur;
 659   THREAD *tmp;
 660   int i;
 661
 662   for (i = 0; i < ctx->msgcount; i++) {
 663     cur = ctx->hdrs[i];
 664     if (cur->thread->check_subject)
 665       cur->thread->check_subject = 0;
 666     else if (!init)
 667       continue;
 668
 669     /* figure out which messages have subjects different than their parents' */
 670     tmp = cur->thread->parent;
 671     while (tmp && !tmp->message) {
 672       tmp = tmp->parent;
 673     }
 674
 675     if (!tmp)
 676       cur->subject_changed = 1;
 677     else if (cur->env->real_subj && tmp->message->env->real_subj)
 678       cur->subject_changed = mutt_strcmp (cur->env->real_subj,
 679                                           tmp->message->env->
 680                                           real_subj) ? 1 : 0;
 681     else
 682       cur->subject_changed = (cur->env->real_subj
 683                               || tmp->message->env->real_subj) ? 1 : 0;
 684   }
 685 }
 686
 687 void mutt_sort_threads (CONTEXT * ctx, int init)
 688 {
 689   HEADER *cur;
 690   int i, oldsort, using_refs = 0;
 691   THREAD *thread, *new, *tmp, top;
 692   LIST *ref = NULL;
 693
 694   /* set Sort to the secondary method to support the set sort_aux=reverse-*
 695    * settings.  The sorting functions just look at the value of
 696    * SORT_REVERSE
 697    */
 698   oldsort = Sort;
 699   Sort = SortAux;
 700
 701   if (!ctx->thread_hash)
 702     init = 1;
 703
 704   if (init)
 705     ctx->thread_hash = hash_create (ctx->msgcount * 2);
 706
 707   /* we want a quick way to see if things are actually attached to the top of the
 708    * thread tree or if they're just dangling, so we attach everything to a top
 709    * node temporarily */
 710   top.parent = top.next = top.prev = NULL;
 711   top.child = ctx->tree;
 712   for (thread = ctx->tree; thread; thread = thread->next)
 713     thread->parent = &top;
 714
 715   /* put each new message together with the matching messageless THREAD if it
 716    * exists.  otherwise, if there is a THREAD that already has a message, thread
 717    * new message as an identical child.  if we didn't attach the message to a
 718    * THREAD, make a new one for it. */
 719   for (i = 0; i < ctx->msgcount; i++) {
 720     cur = ctx->hdrs[i];
 721
 722     if (!cur->thread) {
 723       if ((!init || option (OPTDUPTHREADS)) && cur->env->message_id)
 724         thread = hash_find (ctx->thread_hash, cur->env->message_id);
 725       else
 726         thread = NULL;
 727
 728       if (thread && !thread->message) {
 729         /* this is a message which was missing before */
 730         thread->message = cur;
 731         cur->thread = thread;
 732         thread->check_subject = 1;
 733
 734         /* mark descendants as needing subject_changed checked */
 735         for (tmp = (thread->child ? thread->child : thread); tmp != thread;) {
 736           while (!tmp->message)
 737             tmp = tmp->child;
 738           tmp->check_subject = 1;
 739           while (!tmp->next && tmp != thread)
 740             tmp = tmp->parent;
 741           if (tmp != thread)
 742             tmp = tmp->next;
 743         }
 744
 745         if (thread->parent) {
 746           /* remove threading info above it based on its children, which we'll
 747            * recalculate based on its headers.  make sure not to leave
 748            * dangling missing messages.  note that we haven't kept track
 749            * of what info came from its children and what from its siblings'
 750            * children, so we just remove the stuff that's definitely from it */
 751           do {
 752             tmp = thread->parent;
 753             unlink_message (&tmp->child, thread);
 754             thread->parent = NULL;
 755             thread->sort_key = NULL;
 756             thread->fake_thread = 0;
 757             thread = tmp;
 758           } while (thread != &top && !thread->child && !thread->message);
 759         }
 760       }
 761       else {
 762         new = (option (OPTDUPTHREADS) ? thread : NULL);
 763
 764         thread = safe_calloc (1, sizeof (THREAD));
 765         thread->message = cur;
 766         thread->check_subject = 1;
 767         cur->thread = thread;
 768         hash_insert (ctx->thread_hash,
 769                      cur->env->message_id ? cur->env->message_id : "",
 770                      thread, 1);
 771
 772         if (new) {
 773           if (new->duplicate_thread)
 774             new = new->parent;
 775
 776           thread = cur->thread;
 777
 778           insert_message (&new->child, new, thread);
 779           thread->duplicate_thread = 1;
 780           thread->message->threaded = 1;
 781         }
 782       }
 783     }
 784     else {
 785       /* unlink pseudo-threads because they might be children of newly
 786        * arrived messages */
 787       thread = cur->thread;
 788       for (new = thread->child; new;) {
 789         tmp = new->next;
 790         if (new->fake_thread) {
 791           unlink_message (&thread->child, new);
 792           insert_message (&top.child, &top, new);
 793           new->fake_thread = 0;
 794         }
 795         new = tmp;
 796       }
 797     }
 798   }
 799
 800   /* thread by references */
 801   for (i = 0; i < ctx->msgcount; i++) {
 802     cur = ctx->hdrs[i];
 803     if (cur->threaded)
 804       continue;
 805     cur->threaded = 1;
 806
 807     thread = cur->thread;
 808     using_refs = 0;
 809
 810     while (1) {
 811       if (using_refs == 0) {
 812         /* look at the beginning of in-reply-to: */
 813         if ((ref = cur->env->in_reply_to) != NULL)
 814           using_refs = 1;
 815         else {
 816           ref = cur->env->references;
 817           using_refs = 2;
 818         }
 819       }
 820       else if (using_refs == 1) {
 821         /* if there's no references header, use all the in-reply-to:
 822          * data that we have.  otherwise, use the first reference
 823          * if it's different than the first in-reply-to, otherwise use
 824          * the second reference (since at least eudora puts the most
 825          * recent reference in in-reply-to and the rest in references)
 826          */
 827         if (!cur->env->references)
 828           ref = ref->next;
 829         else {
 830           if (mutt_strcmp (ref->data, cur->env->references->data))
 831             ref = cur->env->references;
 832           else
 833             ref = cur->env->references->next;
 834
 835           using_refs = 2;
 836         }
 837       }
 838       else
 839         ref = ref->next;        /* go on with references */
 840
 841       if (!ref)
 842         break;
 843
 844       if ((new = hash_find (ctx->thread_hash, ref->data)) == NULL) {
 845         new = safe_calloc (1, sizeof (THREAD));
 846         hash_insert (ctx->thread_hash, ref->data, new, 1);
 847       }
 848       else {
 849         if (new->duplicate_thread)
 850           new = new->parent;
 851         if (is_descendant (new, thread))        /* no loops! */
 852           break;
 853       }
 854
 855       if (thread->parent)
 856         unlink_message (&top.child, thread);
 857       insert_message (&new->child, new, thread);
 858       thread = new;
 859       if (thread->message || (thread->parent && thread->parent != &top))
 860         break;
 861     }
 862
 863     if (!thread->parent)
 864       insert_message (&top.child, &top, thread);
 865   }
 866
 867   /* detach everything from the temporary top node */
 868   for (thread = top.child; thread; thread = thread->next) {
 869     thread->parent = NULL;
 870   }
 871   ctx->tree = top.child;
 872
 873   check_subjects (ctx, init);
 874
 875   if (!option (OPTSTRICTTHREADS))
 876     pseudo_threads (ctx);
 877
 878   if (ctx->tree) {
 879     ctx->tree = mutt_sort_subthreads (ctx->tree, init);
 880
 881     /* restore the oldsort order. */
 882     Sort = oldsort;
 883
 884     /* Put the list into an array. */
 885     linearize_tree (ctx);
 886
 887     /* Draw the thread tree. */
 888     mutt_draw_tree (ctx);
 889   }
 890 }
 891
 892 static HEADER *find_virtual (THREAD * cur, int reverse)
 893 {
 894   THREAD *top;
 895
 896   if (cur->message && cur->message->virtual >= 0)
 897     return (cur->message);
 898
 899   top = cur;
 900   if ((cur = cur->child) == NULL)
 901     return (NULL);
 902
 903   while (reverse && cur->next)
 904     cur = cur->next;
 905
 906   FOREVER {
 907     if (cur->message && cur->message->virtual >= 0)
 908       return (cur->message);
 909
 910     if (cur->child) {
 911       cur = cur->child;
 912
 913       while (reverse && cur->next)
 914         cur = cur->next;
 915     }
 916     else if (reverse ? cur->prev : cur->next)
 917       cur = reverse ? cur->prev : cur->next;
 918     else {
 919       while (!(reverse ? cur->prev : cur->next)) {
 920         cur = cur->parent;
 921         if (cur == top)
 922           return (NULL);
 923       }
 924       cur = reverse ? cur->prev : cur->next;
 925     }
 926     /* not reached */
 927   }
 928 }
 929
 930 int _mutt_aside_thread (HEADER * hdr, short dir, short subthreads)
 931 {
 932   THREAD *cur;
 933   HEADER *tmp;
 934
 935   if ((Sort & SORT_MASK) != SORT_THREADS) {
 936     mutt_error _("Threading is not enabled.");
 937
 938     return (hdr->virtual);
 939   }
 940
 941   cur = hdr->thread;
 942
 943   if (!subthreads) {
 944     while (cur->parent)
 945       cur = cur->parent;
 946   }
 947   else {
 948     if ((dir != 0) ^ ((Sort & SORT_REVERSE) != 0)) {
 949       while (!cur->next && cur->parent)
 950         cur = cur->parent;
 951     }
 952     else {
 953       while (!cur->prev && cur->parent)
 954         cur = cur->parent;
 955     }
 956   }
 957
 958   if ((dir != 0) ^ ((Sort & SORT_REVERSE) != 0)) {
 959     do {
 960       cur = cur->next;
 961       if (!cur)
 962         return (-1);
 963       tmp = find_virtual (cur, 0);
 964     } while (!tmp);
 965   }
 966   else {
 967     do {
 968       cur = cur->prev;
 969       if (!cur)
 970         return (-1);
 971       tmp = find_virtual (cur, 1);
 972     } while (!tmp);
 973   }
 974
 975   return (tmp->virtual);
 976 }
 977
 978 int mutt_parent_message (CONTEXT * ctx, HEADER * hdr)
 979 {
 980   THREAD *thread;
 981
 982   if ((Sort & SORT_MASK) != SORT_THREADS) {
 983     mutt_error _("Threading is not enabled.");
 984
 985     return (hdr->virtual);
 986   }
 987
 988   for (thread = hdr->thread->parent; thread; thread = thread->parent) {
 989     if ((hdr = thread->message) != NULL) {
 990       if (VISIBLE (hdr, ctx))
 991         return (hdr->virtual);
 992       else {
 993         mutt_error _("Parent message is not visible in this limited view.");
 994
 995         return (-1);
 996       }
 997     }
 998   }
 999
1000   mutt_error _("Parent message is not available.");
1001
1002   return (-1);
1003 }
1004
1005 void mutt_set_virtual (CONTEXT * ctx)
1006 {
1007   int i;
1008   HEADER *cur;
1009
1010   ctx->vcount = 0;
1011   ctx->vsize = 0;
1012
1013   for (i = 0; i < ctx->msgcount; i++) {
1014     cur = ctx->hdrs[i];
1015     if (cur->virtual >= 0) {
1016       cur->virtual = ctx->vcount;
1017       ctx->v2r[ctx->vcount] = i;
1018       ctx->vcount++;
1019       ctx->vsize +=
1020         cur->content->length + cur->content->offset -
1021         cur->content->hdr_offset;
1022       cur->num_hidden = mutt_get_hidden (ctx, cur);
1023     }
1024   }
1025 }
1026
1027 int _mutt_traverse_thread (CONTEXT * ctx, HEADER * cur, int flag)
1028 {
1029   THREAD *thread, *top;
1030   HEADER *roothdr = NULL;
1031   int final, reverse = (Sort & SORT_REVERSE), minmsgno;
1032   int num_hidden = 0, new = 0, old = 0;
1033   int min_unread_msgno = INT_MAX, min_unread = cur->virtual;
1034
1035 #define CHECK_LIMIT (!ctx->pattern || cur->limited)
1036
1037   if ((Sort & SORT_MASK) != SORT_THREADS && !(flag & M_THREAD_GET_HIDDEN)) {
1038     mutt_error (_("Threading is not enabled."));
1039     return (cur->virtual);
1040   }
1041
1042   final = cur->virtual;
1043   thread = cur->thread;
1044   while (thread->parent)
1045     thread = thread->parent;
1046   top = thread;
1047   while (!thread->message)
1048     thread = thread->child;
1049   cur = thread->message;
1050   minmsgno = cur->msgno;
1051
1052   if (!cur->read && CHECK_LIMIT) {
1053     if (cur->old)
1054       old = 2;
1055     else
1056       new = 1;
1057     if (cur->msgno < min_unread_msgno) {
1058       min_unread = cur->virtual;
1059       min_unread_msgno = cur->msgno;
1060     }
1061   }
1062
1063   if (cur->virtual == -1 && CHECK_LIMIT)
1064     num_hidden++;
1065
1066   if (flag & (M_THREAD_COLLAPSE | M_THREAD_UNCOLLAPSE)) {
1067     cur->pair = 0;              /* force index entry's color to be re-evaluated */
1068     cur->collapsed = flag & M_THREAD_COLLAPSE;
1069     if (cur->virtual != -1) {
1070       roothdr = cur;
1071       if (flag & M_THREAD_COLLAPSE)
1072         final = roothdr->virtual;
1073     }
1074   }
1075
1076   if (thread == top && (thread = thread->child) == NULL) {
1077     /* return value depends on action requested */
1078     if (flag & (M_THREAD_COLLAPSE | M_THREAD_UNCOLLAPSE))
1079       return (final);
1080     else if (flag & M_THREAD_UNREAD)
1081       return ((old && new) ? new : (old ? old : new));
1082     else if (flag & M_THREAD_GET_HIDDEN)
1083       return (num_hidden);
1084     else if (flag & M_THREAD_NEXT_UNREAD)
1085       return (min_unread);
1086   }
1087
1088   FOREVER {
1089     cur = thread->message;
1090
1091     if (cur) {
1092       if (flag & (M_THREAD_COLLAPSE | M_THREAD_UNCOLLAPSE)) {
1093         cur->pair = 0;          /* force index entry's color to be re-evaluated */
1094         cur->collapsed = flag & M_THREAD_COLLAPSE;
1095         if (!roothdr && CHECK_LIMIT) {
1096           roothdr = cur;
1097           if (flag & M_THREAD_COLLAPSE)
1098             final = roothdr->virtual;
1099         }
1100
1101         if (reverse && (flag & M_THREAD_COLLAPSE) && (cur->msgno < minmsgno)
1102             && CHECK_LIMIT) {
1103           minmsgno = cur->msgno;
1104           final = cur->virtual;
1105         }
1106
1107         if (flag & M_THREAD_COLLAPSE) {
1108           if (cur != roothdr)
1109             cur->virtual = -1;
1110         }
1111         else {
1112           if (CHECK_LIMIT)
1113             cur->virtual = cur->msgno;
1114         }
1115       }
1116
1117
1118       if (!cur->read && CHECK_LIMIT) {
1119         if (cur->old)
1120           old = 2;
1121         else
1122           new = 1;
1123         if (cur->msgno < min_unread_msgno) {
1124           min_unread = cur->virtual;
1125           min_unread_msgno = cur->msgno;
1126         }
1127       }
1128
1129       if (cur->virtual == -1 && CHECK_LIMIT)
1130         num_hidden++;
1131     }
1132
1133     if (thread->child)
1134       thread = thread->child;
1135     else if (thread->next)
1136       thread = thread->next;
1137     else {
1138       int done = 0;
1139
1140       while (!thread->next) {
1141         thread = thread->parent;
1142         if (thread == top) {
1143           done = 1;
1144           break;
1145         }
1146       }
1147       if (done)
1148         break;
1149       thread = thread->next;
1150     }
1151   }
1152
1153   /* return value depends on action requested */
1154   if (flag & (M_THREAD_COLLAPSE | M_THREAD_UNCOLLAPSE))
1155     return (final);
1156   else if (flag & M_THREAD_UNREAD)
1157     return ((old && new) ? new : (old ? old : new));
1158   else if (flag & M_THREAD_GET_HIDDEN)
1159     return (num_hidden + 1);
1160   else if (flag & M_THREAD_NEXT_UNREAD)
1161     return (min_unread);
1162
1163   return (0);
1164 #undef CHECK_LIMIT
1165 }
1166
1167
1168 /* if flag is 0, we want to know how many messages
1169  * are in the thread.  if flag is 1, we want to know
1170  * our position in the thread. */
1171 int mutt_messages_in_thread (CONTEXT * ctx, HEADER * hdr, int flag)
1172 {
1173   THREAD *threads[2];
1174   int i, rc;
1175
1176   if ((Sort & SORT_MASK) != SORT_THREADS || !hdr->thread)
1177     return (1);
1178
1179   threads[0] = hdr->thread;
1180   while (threads[0]->parent)
1181     threads[0] = threads[0]->parent;
1182
1183   threads[1] = flag ? hdr->thread : threads[0]->next;
1184
1185   for (i = 0; i < ((flag || !threads[1]) ? 1 : 2); i++) {
1186     while (!threads[i]->message)
1187       threads[i] = threads[i]->child;
1188   }
1189
1190   if (Sort & SORT_REVERSE)
1191     rc =
1192       threads[0]->message->msgno -
1193       (threads[1] ? threads[1]->message->msgno : -1);
1194   else
1195     rc =
1196       (threads[1] ? threads[1]->message->msgno : ctx->msgcount) -
1197       threads[0]->message->msgno;
1198
1199   if (flag)
1200     rc += 1;
1201
1202   return (rc);
1203 }
1204
1205
1206 HASH *mutt_make_id_hash (CONTEXT * ctx)
1207 {
1208   int i;
1209   HEADER *hdr;
1210   HASH *hash;
1211
1212   hash = hash_create (ctx->msgcount * 2);
1213
1214   for (i = 0; i < ctx->msgcount; i++) {
1215     hdr = ctx->hdrs[i];
1216     if (hdr->env->message_id)
1217       hash_insert (hash, hdr->env->message_id, hdr, 0);
1218   }
1219
1220   return hash;
1221 }
1222
1223 HASH *mutt_make_subj_hash (CONTEXT * ctx)
1224 {
1225   int i;
1226   HEADER *hdr;
1227   HASH *hash;
1228
1229   hash = hash_create (ctx->msgcount * 2);
1230
1231   for (i = 0; i < ctx->msgcount; i++) {
1232     hdr = ctx->hdrs[i];
1233     if (hdr->env->real_subj)
1234       hash_insert (hash, hdr->env->real_subj, hdr, 1);
1235   }
1236
1237   return hash;
1238 }
1239
1240 static void clean_references (THREAD * brk, THREAD * cur)
1241 {
1242   THREAD *p;
1243   LIST *ref = NULL;
1244   int done = 0;
1245
1246   for (; cur; cur = cur->next, done = 0) {
1247     /* parse subthread recursively */
1248     clean_references (brk, cur->child);
1249
1250     if (!cur->message)
1251       break;                    /* skip pseudo-message */
1252
1253     /* Looking for the first bad reference according to the new threading.
1254      * Optimal since Mutt stores the references in reverse order, and the
1255      * first loop should match immediatly for mails respecting RFC2822. */
1256     for (p = brk; !done && p; p = p->parent)
1257       for (ref = cur->message->env->references; p->message && ref;
1258            ref = ref->next)
1259         if (!mutt_strcasecmp (ref->data, p->message->env->message_id)) {
1260           done = 1;
1261           break;
1262         }
1263
1264     if (done) {
1265       HEADER *h = cur->message;
1266
1267       /* clearing the References: header from obsolete Message-Id(s) */
1268       mutt_free_list (&ref->next);
1269
1270       if (h->new_env)
1271         mutt_free_list (&h->new_env->references);
1272       else
1273         h->new_env = mutt_new_envelope ();
1274
1275       h->new_env->references = mutt_copy_list (h->env->references);
1276
1277       h->refs_changed = h->changed = 1;
1278     }
1279   }
1280 }
1281
1282 void mutt_break_thread (HEADER * hdr)
1283 {
1284   mutt_free_list (&hdr->env->in_reply_to);
1285   mutt_free_list (&hdr->env->references);
1286   hdr->irt_changed = hdr->refs_changed = hdr->changed = 1;
1287
1288   if (hdr->new_env) {
1289     mutt_free_list (&hdr->new_env->in_reply_to);
1290     mutt_free_list (&hdr->new_env->references);
1291   }
1292   else
1293     hdr->new_env = mutt_new_envelope ();
1294
1295   clean_references (hdr->thread, hdr->thread->child);
1296 }
1297
1298 static int link_threads (HEADER * parent, HEADER * child, CONTEXT * ctx)
1299 {
1300   if (child == parent)
1301     return 0;
1302
1303   mutt_break_thread (child);
1304
1305   child->env->in_reply_to = mutt_new_list ();
1306   child->env->in_reply_to->data = safe_strdup (parent->env->message_id);
1307
1308   child->new_env->in_reply_to = mutt_new_list ();
1309   child->new_env->in_reply_to->data = safe_strdup (parent->env->message_id);
1310
1311   mutt_set_flag (ctx, child, M_TAG, 0);
1312
1313   child->irt_changed = child->changed = 1;
1314   return 1;
1315 }
1316
1317 int mutt_link_threads (HEADER * cur, HEADER * last, CONTEXT * ctx)
1318 {
1319   int i, changed = 0;
1320
1321   if (!last) {
1322     for (i = 0; i < ctx->vcount; i++)
1323       if (ctx->hdrs[Context->v2r[i]]->tagged)
1324         changed |= link_threads (cur, ctx->hdrs[Context->v2r[i]], ctx);
1325   }
1326   else
1327     changed = link_threads (cur, last, ctx);
1328
1329   return changed;
1330 }