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