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