thread.c

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