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