thread.c

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