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