thread.c

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