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