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