thread.c

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