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