1 /**
2 * @file
3 * Create/manipulate threading in emails
4 *
5 * @authors
6 * Copyright (C) 1996-2002 Michael R. Elkins <me@mutt.org>
7 *
8 * @copyright
9 * This program is free software: you can redistribute it and/or modify it under
10 * the terms of the GNU General Public License as published by the Free Software
11 * Foundation, either version 2 of the License, or (at your option) any later
12 * version.
13 *
14 * This program is distributed in the hope that it will be useful, but WITHOUT
15 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
16 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
17 * details.
18 *
19 * You should have received a copy of the GNU General Public License along with
20 * this program. If not, see <http://www.gnu.org/licenses/>.
21 */
22
23 /**
24 * @page neo_mutt_thread Create/manipulate threading in emails
25 *
26 * Create/manipulate threading in emails
27 */
28
29 #include "config.h"
30 #include <assert.h>
31 #include <limits.h>
32 #include <stdbool.h>
33 #include <stdlib.h>
34 #include <string.h>
35 #include "mutt/lib.h"
36 #include "config/lib.h"
37 #include "email/lib.h"
38 #include "core/lib.h"
39 #include "mutt.h"
40 #include "mutt_thread.h"
41 #include "mx.h"
42 #include "options.h"
43 #include "protos.h"
44 #include "sort.h"
45
46 /**
47 * struct ThreadsContext - The "current" threading state
48 */
49 struct ThreadsContext
50 {
51 struct Mailbox *mailbox; ///< Current mailbox
52 struct MuttThread *tree; ///< Top of thread tree
53 struct HashTable *hash; ///< Hash table for threads
54 short c_sort; ///< Last sort method
55 short c_sort_aux; ///< Last sort_aux method
56 };
57
58 /**
59 * UseThreadsMethods - Choices for '$use_threads' for the index
60 */
61 static const struct Mapping UseThreadsMethods[] = {
62 // clang-format off
63 { "unset", UT_UNSET },
64 { "flat", UT_FLAT },
65 { "threads", UT_THREADS },
66 { "reverse", UT_REVERSE },
67 // aliases
68 { "no", UT_FLAT },
69 { "yes", UT_THREADS },
70 { NULL, 0 },
71 // clang-format on
72 };
73
74 struct EnumDef UseThreadsTypeDef = {
75 "use_threads_type",
76 4,
77 (struct Mapping *) &UseThreadsMethods,
78 };
79
80 /**
81 * mutt_thread_style - Which threading style is active?
82 * @retval UT_FLAT No threading in use
83 * @retval UT_THREADS Normal threads (root above subthread)
84 * @retval UT_REVERSE Reverse threads (subthread above root)
85 *
86 * @note UT_UNSET is never returned; rather, this function considers the
87 * interaction between $use_threads and $sort.
88 */
mutt_thread_style(void)89 enum UseThreads mutt_thread_style(void)
90 {
91 const unsigned char c_use_threads =
92 cs_subset_enum(NeoMutt->sub, "use_threads");
93 const short c_sort = cs_subset_sort(NeoMutt->sub, "sort");
94 if (c_use_threads > UT_FLAT)
95 return c_use_threads;
96 if ((c_sort & SORT_MASK) != SORT_THREADS)
97 return UT_FLAT;
98 if (c_sort & SORT_REVERSE)
99 return UT_REVERSE;
100 return UT_THREADS;
101 }
102
103 /**
104 * get_use_threads_str - Convert UseThreads enum to string
105 * @param value Value to convert
106 * @retval string form of value
107 */
get_use_threads_str(enum UseThreads value)108 const char *get_use_threads_str(enum UseThreads value)
109 {
110 return mutt_map_get_name(value, UseThreadsMethods);
111 }
112
113 /**
114 * sort_validator - Validate values of "sort" - Implements ConfigDef::validator() - @ingroup cfg_def_validator
115 */
sort_validator(const struct ConfigSet * cs,const struct ConfigDef * cdef,intptr_t value,struct Buffer * err)116 int sort_validator(const struct ConfigSet *cs, const struct ConfigDef *cdef,
117 intptr_t value, struct Buffer *err)
118 {
119 if (((value & SORT_MASK) == SORT_THREADS) && (value & SORT_LAST))
120 {
121 mutt_buffer_printf(err, _("Cannot use 'last-' prefix with 'threads' for %s"), cdef->name);
122 return CSR_ERR_INVALID;
123 }
124 return CSR_SUCCESS;
125 }
126
127 /**
128 * is_visible - Is the message visible?
129 * @param e Email
130 * @retval true The message is not hidden in some way
131 */
is_visible(struct Email * e)132 static bool is_visible(struct Email *e)
133 {
134 return e->vnum >= 0 || (e->collapsed && e->visible);
135 }
136
137 /**
138 * need_display_subject - Determines whether to display a message's subject
139 * @param e Email
140 * @retval true The subject should be displayed
141 */
need_display_subject(struct Email * e)142 static bool need_display_subject(struct Email *e)
143 {
144 struct MuttThread *tmp = NULL;
145 struct MuttThread *tree = e->thread;
146
147 /* if the user disabled subject hiding, display it */
148 const bool c_hide_thread_subject =
149 cs_subset_bool(NeoMutt->sub, "hide_thread_subject");
150 if (!c_hide_thread_subject)
151 return true;
152
153 /* if our subject is different from our parent's, display it */
154 if (e->subject_changed)
155 return true;
156
157 /* if our subject is different from that of our closest previously displayed
158 * sibling, display the subject */
159 for (tmp = tree->prev; tmp; tmp = tmp->prev)
160 {
161 e = tmp->message;
162 if (e && is_visible(e))
163 {
164 if (e->subject_changed)
165 return true;
166 break;
167 }
168 }
169
170 /* if there is a parent-to-child subject change anywhere between us and our
171 * closest displayed ancestor, display the subject */
172 for (tmp = tree->parent; tmp; tmp = tmp->parent)
173 {
174 e = tmp->message;
175 if (e)
176 {
177 if (is_visible(e))
178 return false;
179 if (e->subject_changed)
180 return true;
181 }
182 }
183
184 /* if we have no visible parent or previous sibling, display the subject */
185 return true;
186 }
187
188 /**
189 * linearize_tree - Flatten an email thread
190 * @param tctx Threading context
191 */
linearize_tree(struct ThreadsContext * tctx)192 static void linearize_tree(struct ThreadsContext *tctx)
193 {
194 if (!tctx || !tctx->mailbox)
195 return;
196
197 struct Mailbox *m = tctx->mailbox;
198
199 const bool reverse = (mutt_thread_style() == UT_REVERSE);
200 struct MuttThread *tree = tctx->tree;
201 struct Email **array = m->emails + (reverse ? m->msg_count - 1 : 0);
202
203 while (tree)
204 {
205 while (!tree->message)
206 tree = tree->child;
207
208 *array = tree->message;
209 array += reverse ? -1 : 1;
210
211 if (tree->child)
212 tree = tree->child;
213 else
214 {
215 while (tree)
216 {
217 if (tree->next)
218 {
219 tree = tree->next;
220 break;
221 }
222 else
223 tree = tree->parent;
224 }
225 }
226 }
227 }
228
229 /**
230 * calculate_visibility - Are tree nodes visible
231 * @param tree Threads tree
232 * @param max_depth Maximum depth to check
233 *
234 * this calculates whether a node is the root of a subtree that has visible
235 * nodes, whether a node itself is visible, whether, if invisible, it has
236 * depth anyway, and whether any of its later siblings are roots of visible
237 * subtrees. while it's at it, it frees the old thread display, so we can
238 * skip parts of the tree in mutt_draw_tree() if we've decided here that we
239 * don't care about them any more.
240 */
calculate_visibility(struct MuttThread * tree,int * max_depth)241 static void calculate_visibility(struct MuttThread *tree, int *max_depth)
242 {
243 if (!tree)
244 return;
245
246 struct MuttThread *tmp = NULL;
247 struct MuttThread *orig_tree = tree;
248 const bool c_hide_top_missing =
249 cs_subset_bool(NeoMutt->sub, "hide_top_missing");
250 const bool c_hide_missing = cs_subset_bool(NeoMutt->sub, "hide_missing");
251 int hide_top_missing = c_hide_top_missing && !c_hide_missing;
252 const bool c_hide_top_limited =
253 cs_subset_bool(NeoMutt->sub, "hide_top_limited");
254 const bool c_hide_limited = cs_subset_bool(NeoMutt->sub, "hide_limited");
255 int hide_top_limited = c_hide_top_limited && !c_hide_limited;
256 int depth = 0;
257
258 /* we walk each level backwards to make it easier to compute next_subtree_visible */
259 while (tree->next)
260 tree = tree->next;
261 *max_depth = 0;
262
263 while (true)
264 {
265 if (depth > *max_depth)
266 *max_depth = depth;
267
268 tree->subtree_visible = 0;
269 if (tree->message)
270 {
271 FREE(&tree->message->tree);
272 if (is_visible(tree->message))
273 {
274 tree->deep = true;
275 tree->visible = true;
276 tree->message->display_subject = need_display_subject(tree->message);
277 for (tmp = tree; tmp; tmp = tmp->parent)
278 {
279 if (tmp->subtree_visible)
280 {
281 tmp->deep = true;
282 tmp->subtree_visible = 2;
283 break;
284 }
285 else
286 tmp->subtree_visible = 1;
287 }
288 }
289 else
290 {
291 tree->visible = false;
292 tree->deep = !c_hide_limited;
293 }
294 }
295 else
296 {
297 tree->visible = false;
298 tree->deep = !c_hide_missing;
299 }
300 tree->next_subtree_visible =
301 tree->next && (tree->next->next_subtree_visible || tree->next->subtree_visible);
302 if (tree->child)
303 {
304 depth++;
305 tree = tree->child;
306 while (tree->next)
307 tree = tree->next;
308 }
309 else if (tree->prev)
310 tree = tree->prev;
311 else
312 {
313 while (tree && !tree->prev)
314 {
315 depth--;
316 tree = tree->parent;
317 }
318 if (!tree)
319 break;
320 tree = tree->prev;
321 }
322 }
323
324 /* now fix up for the OPTHIDETOP* options if necessary */
325 if (hide_top_limited || hide_top_missing)
326 {
327 tree = orig_tree;
328 while (true)
329 {
330 if (!tree->visible && tree->deep && (tree->subtree_visible < 2) &&
331 ((tree->message && hide_top_limited) || (!tree->message && hide_top_missing)))
332 {
333 tree->deep = false;
334 }
335 if (!tree->deep && tree->child && tree->subtree_visible)
336 tree = tree->child;
337 else if (tree->next)
338 tree = tree->next;
339 else
340 {
341 while (tree && !tree->next)
342 tree = tree->parent;
343 if (!tree)
344 break;
345 tree = tree->next;
346 }
347 }
348 }
349 }
350
351 /**
352 * mutt_thread_ctx_init - Initialize a threading context
353 * @param m Current mailbox
354 * @retval tctx Threading context
355 */
mutt_thread_ctx_init(struct Mailbox * m)356 struct ThreadsContext *mutt_thread_ctx_init(struct Mailbox *m)
357 {
358 struct ThreadsContext *tctx = mutt_mem_calloc(1, sizeof(struct ThreadsContext));
359 tctx->mailbox = m;
360 tctx->tree = NULL;
361 tctx->hash = NULL;
362 return tctx;
363 }
364
365 /**
366 * mutt_thread_ctx_free - Finalize a threading context
367 * @param tctx Threading context to finalize
368 */
mutt_thread_ctx_free(struct ThreadsContext ** tctx)369 void mutt_thread_ctx_free(struct ThreadsContext **tctx)
370 {
371 (*tctx)->mailbox = NULL;
372 mutt_hash_free(&(*tctx)->hash);
373 FREE(tctx);
374 }
375
376 /**
377 * mutt_draw_tree - Draw a tree of threaded emails
378 * @param tctx Threading context
379 *
380 * Since the graphics characters have a value >255, I have to resort to using
381 * escape sequences to pass the information to print_enriched_string(). These
382 * are the macros MUTT_TREE_* defined in mutt.h.
383 *
384 * ncurses should automatically use the default ASCII characters instead of
385 * graphics chars on terminals which don't support them (see the man page for
386 * curs_addch).
387 */
mutt_draw_tree(struct ThreadsContext * tctx)388 void mutt_draw_tree(struct ThreadsContext *tctx)
389 {
390 char *pfx = NULL, *mypfx = NULL, *arrow = NULL, *myarrow = NULL, *new_tree = NULL;
391 const bool reverse = (mutt_thread_style() == UT_REVERSE);
392 enum TreeChar corner = reverse ? MUTT_TREE_ULCORNER : MUTT_TREE_LLCORNER;
393 enum TreeChar vtee = reverse ? MUTT_TREE_BTEE : MUTT_TREE_TTEE;
394 const bool c_narrow_tree = cs_subset_bool(NeoMutt->sub, "narrow_tree");
395 int depth = 0, start_depth = 0, max_depth = 0, width = c_narrow_tree ? 1 : 2;
396 struct MuttThread *nextdisp = NULL, *pseudo = NULL, *parent = NULL;
397
398 struct MuttThread *tree = tctx->tree;
399
400 /* Do the visibility calculations and free the old thread chars.
401 * From now on we can simply ignore invisible subtrees */
402 calculate_visibility(tree, &max_depth);
403 pfx = mutt_mem_malloc((width * max_depth) + 2);
404 arrow = mutt_mem_malloc((width * max_depth) + 2);
405 while (tree)
406 {
407 if (depth != 0)
408 {
409 myarrow = arrow + (depth - start_depth - ((start_depth != 0) ? 0 : 1)) * width;
410 const bool c_hide_limited = cs_subset_bool(NeoMutt->sub, "hide_limited");
411 const bool c_hide_missing = cs_subset_bool(NeoMutt->sub, "hide_missing");
412 if (start_depth == depth)
413 myarrow[0] = nextdisp ? MUTT_TREE_LTEE : corner;
414 else if (parent->message && !c_hide_limited)
415 myarrow[0] = MUTT_TREE_HIDDEN;
416 else if (!parent->message && !c_hide_missing)
417 myarrow[0] = MUTT_TREE_MISSING;
418 else
419 myarrow[0] = vtee;
420 if (width == 2)
421 {
422 myarrow[1] = pseudo ? MUTT_TREE_STAR :
423 (tree->duplicate_thread ? MUTT_TREE_EQUALS : MUTT_TREE_HLINE);
424 }
425 if (tree->visible)
426 {
427 myarrow[width] = MUTT_TREE_RARROW;
428 myarrow[width + 1] = 0;
429 new_tree = mutt_mem_malloc(((size_t) depth * width) + 2);
430 if (start_depth > 1)
431 {
432 strncpy(new_tree, pfx, (size_t) width * (start_depth - 1));
433 mutt_str_copy(new_tree + (start_depth - 1) * width, arrow,
434 (1 + depth - start_depth) * width + 2);
435 }
436 else
437 mutt_str_copy(new_tree, arrow, ((size_t) depth * width) + 2);
438 tree->message->tree = new_tree;
439 }
440 }
441 if (tree->child && (depth != 0))
442 {
443 mypfx = pfx + (depth - 1) * width;
444 mypfx[0] = nextdisp ? MUTT_TREE_VLINE : MUTT_TREE_SPACE;
445 if (width == 2)
446 mypfx[1] = MUTT_TREE_SPACE;
447 }
448 parent = tree;
449 nextdisp = NULL;
450 pseudo = NULL;
451 do
452 {
453 if (tree->child && tree->subtree_visible)
454 {
455 if (tree->deep)
456 depth++;
457 if (tree->visible)
458 start_depth = depth;
459 tree = tree->child;
460
461 /* we do this here because we need to make sure that the first child thread
462 * of the old tree that we deal with is actually displayed if any are,
463 * or we might set the parent variable wrong while going through it. */
464 while (!tree->subtree_visible && tree->next)
465 tree = tree->next;
466 }
467 else
468 {
469 while (!tree->next && tree->parent)
470 {
471 if (tree == pseudo)
472 pseudo = NULL;
473 if (tree == nextdisp)
474 nextdisp = NULL;
475 if (tree->visible)
476 start_depth = depth;
477 tree = tree->parent;
478 if (tree->deep)
479 {
480 if (start_depth == depth)
481 start_depth--;
482 depth--;
483 }
484 }
485 if (tree == pseudo)
486 pseudo = NULL;
487 if (tree == nextdisp)
488 nextdisp = NULL;
489 if (tree->visible)
490 start_depth = depth;
491 tree = tree->next;
492 if (!tree)
493 break;
494 }
495 if (!pseudo && tree->fake_thread)
496 pseudo = tree;
497 if (!nextdisp && tree->next_subtree_visible)
498 nextdisp = tree;
499 } while (!tree->deep);
500 }
501
502 FREE(&pfx);
503 FREE(&arrow);
504 }
505
506 /**
507 * make_subject_list - Create a sorted list of all subjects in a thread
508 * @param[out] subjects String List of subjects
509 * @param[in] cur Email Thread
510 * @param[out] dateptr Earliest date found in thread
511 *
512 * Since we may be trying to attach as a pseudo-thread a MuttThread that has no
513 * message, we have to make a list of all the subjects of its most immediate
514 * existing descendants.
515 */
make_subject_list(struct ListHead * subjects,struct MuttThread * cur,time_t * dateptr)516 static void make_subject_list(struct ListHead *subjects, struct MuttThread *cur, time_t *dateptr)
517 {
518 struct MuttThread *start = cur;
519 struct Envelope *env = NULL;
520 time_t thisdate;
521 int rc = 0;
522
523 while (true)
524 {
525 while (!cur->message)
526 cur = cur->child;
527
528 if (dateptr)
529 {
530 const bool c_thread_received =
531 cs_subset_bool(NeoMutt->sub, "thread_received");
532 thisdate = c_thread_received ? cur->message->received : cur->message->date_sent;
533 if ((*dateptr == 0) || (thisdate < *dateptr))
534 *dateptr = thisdate;
535 }
536
537 env = cur->message->env;
538 const bool c_sort_re = cs_subset_bool(NeoMutt->sub, "sort_re");
539 if (env->real_subj && ((env->real_subj != env->subject) || !c_sort_re))
540 {
541 struct ListNode *np = NULL;
542 STAILQ_FOREACH(np, subjects, entries)
543 {
544 rc = mutt_str_cmp(env->real_subj, np->data);
545 if (rc >= 0)
546 break;
547 }
548 if (!np)
549 mutt_list_insert_head(subjects, env->real_subj);
550 else if (rc > 0)
551 mutt_list_insert_after(subjects, np, env->real_subj);
552 }
553
554 while (!cur->next && (cur != start))
555 {
556 cur = cur->parent;
557 }
558 if (cur == start)
559 break;
560 cur = cur->next;
561 }
562 }
563
564 /**
565 * find_subject - Find the best possible match for a parent based on subject
566 * @param m Mailbox
567 * @param cur Email to match
568 * @retval ptr Best match for a parent
569 *
570 * If there are multiple matches, the one which was sent the latest, but before
571 * the current message, is used.
572 */
find_subject(struct Mailbox * m,struct MuttThread * cur)573 static struct MuttThread *find_subject(struct Mailbox *m, struct MuttThread *cur)
574 {
575 if (!m)
576 return NULL;
577
578 struct HashElem *ptr = NULL;
579 struct MuttThread *tmp = NULL, *last = NULL;
580 struct ListHead subjects = STAILQ_HEAD_INITIALIZER(subjects);
581 time_t date = 0;
582
583 make_subject_list(&subjects, cur, &date);
584
585 struct ListNode *np = NULL;
586 STAILQ_FOREACH(np, &subjects, entries)
587 {
588 for (ptr = mutt_hash_find_bucket(m->subj_hash, np->data); ptr; ptr = ptr->next)
589 {
590 const bool c_thread_received =
591 cs_subset_bool(NeoMutt->sub, "thread_received");
592 tmp = ((struct Email *) ptr->data)->thread;
593 if ((tmp != cur) && /* don't match the same message */
594 !tmp->fake_thread && /* don't match pseudo threads */
595 tmp->message->subject_changed && /* only match interesting replies */
596 !is_descendant(tmp, cur) && /* don't match in the same thread */
597 (date >= (c_thread_received ? tmp->message->received : tmp->message->date_sent)) &&
598 (!last || (c_thread_received ?
599 (last->message->received < tmp->message->received) :
600 (last->message->date_sent < tmp->message->date_sent))) &&
601 tmp->message->env->real_subj &&
602 mutt_str_equal(np->data, tmp->message->env->real_subj))
603 {
604 last = tmp; /* best match so far */
605 }
606 }
607 }
608
609 mutt_list_clear(&subjects);
610 return last;
611 }
612
613 /**
614 * make_subj_hash - Create a Hash Table for the email subjects
615 * @param m Mailbox
616 * @retval ptr Newly allocated Hash Table
617 */
make_subj_hash(struct Mailbox * m)618 static struct HashTable *make_subj_hash(struct Mailbox *m)
619 {
620 if (!m)
621 return NULL;
622
623 struct HashTable *hash = mutt_hash_new(m->msg_count * 2, MUTT_HASH_ALLOW_DUPS);
624
625 for (int i = 0; i < m->msg_count; i++)
626 {
627 struct Email *e = m->emails[i];
628 if (!e || !e->env)
629 continue;
630 if (e->env->real_subj)
631 mutt_hash_insert(hash, e->env->real_subj, e);
632 }
633
634 return hash;
635 }
636
637 /**
638 * pseudo_threads - Thread messages by subject
639 * @param tctx Threading context
640 *
641 * Thread by subject things that didn't get threaded by message-id
642 */
pseudo_threads(struct ThreadsContext * tctx)643 static void pseudo_threads(struct ThreadsContext *tctx)
644 {
645 if (!tctx || !tctx->mailbox)
646 return;
647
648 struct Mailbox *m = tctx->mailbox;
649
650 struct MuttThread *tree = tctx->tree;
651 struct MuttThread *top = tree;
652 struct MuttThread *tmp = NULL, *cur = NULL, *parent = NULL, *curchild = NULL,
653 *nextchild = NULL;
654
655 if (!m->subj_hash)
656 m->subj_hash = make_subj_hash(m);
657
658 while (tree)
659 {
660 cur = tree;
661 tree = tree->next;
662 parent = find_subject(m, cur);
663 if (parent)
664 {
665 cur->fake_thread = true;
666 unlink_message(&top, cur);
667 insert_message(&parent->child, parent, cur);
668 parent->sort_children = true;
669 tmp = cur;
670 while (true)
671 {
672 while (!tmp->message)
673 tmp = tmp->child;
674
675 /* if the message we're attaching has pseudo-children, they
676 * need to be attached to its parent, so move them up a level.
677 * but only do this if they have the same real subject as the
678 * parent, since otherwise they rightly belong to the message
679 * we're attaching. */
680 if ((tmp == cur) || mutt_str_equal(tmp->message->env->real_subj,
681 parent->message->env->real_subj))
682 {
683 tmp->message->subject_changed = false;
684
685 for (curchild = tmp->child; curchild;)
686 {
687 nextchild = curchild->next;
688 if (curchild->fake_thread)
689 {
690 unlink_message(&tmp->child, curchild);
691 insert_message(&parent->child, parent, curchild);
692 }
693 curchild = nextchild;
694 }
695 }
696
697 while (!tmp->next && (tmp != cur))
698 {
699 tmp = tmp->parent;
700 }
701 if (tmp == cur)
702 break;
703 tmp = tmp->next;
704 }
705 }
706 }
707 tctx->tree = top;
708 }
709
710 /**
711 * mutt_clear_threads - Clear the threading of message in a mailbox
712 * @param tctx Threading context
713 */
mutt_clear_threads(struct ThreadsContext * tctx)714 void mutt_clear_threads(struct ThreadsContext *tctx)
715 {
716 if (!tctx || !tctx->mailbox || !tctx->mailbox->emails || !tctx->tree)
717 return;
718
719 for (int i = 0; i < tctx->mailbox->msg_count; i++)
720 {
721 struct Email *e = tctx->mailbox->emails[i];
722 if (!e)
723 break;
724
725 /* mailbox may have been only partially read */
726 e->thread = NULL;
727 e->threaded = false;
728 }
729 tctx->tree = NULL;
730 mutt_hash_free(&tctx->hash);
731 }
732
733 /**
734 * compare_threads - qsort_r() function for comparing email threads
735 * @param a First thread to compare
736 * @param b Second thread to compare
737 * @param arg ThreadsContext for how to compare
738 * @retval <0 a precedes b
739 * @retval 0 a and b are identical
740 * @retval >0 b precedes a
741 */
compare_threads(const void * a,const void * b,void * arg)742 static int compare_threads(const void *a, const void *b, void *arg)
743 {
744 const struct MuttThread *ta = *(struct MuttThread const *const *) a;
745 const struct MuttThread *tb = *(struct MuttThread const *const *) b;
746 const struct ThreadsContext *tctx = arg;
747 assert(ta->parent == tb->parent);
748 /* If c_sort ties, remember we are building the thread array in
749 * reverse from the index the mails had in the mailbox. */
750 if (ta->parent)
751 {
752 return mutt_compare_emails(ta->sort_aux_key, tb->sort_aux_key, mx_type(tctx->mailbox),
753 tctx->c_sort_aux, SORT_REVERSE | SORT_ORDER);
754 }
755 else
756 {
757 return mutt_compare_emails(ta->sort_thread_key, tb->sort_thread_key,
758 mx_type(tctx->mailbox), tctx->c_sort,
759 SORT_REVERSE | SORT_ORDER);
760 }
761 }
762
763 /**
764 * mutt_sort_subthreads - Sort the children of a thread
765 * @param tctx Threading context
766 * @param init If true, rebuild the thread
767 */
mutt_sort_subthreads(struct ThreadsContext * tctx,bool init)768 static void mutt_sort_subthreads(struct ThreadsContext *tctx, bool init)
769 {
770 struct MuttThread *thread = tctx->tree;
771 if (!thread)
772 return;
773
774 struct MuttThread **array = NULL, *top = NULL, *tmp = NULL;
775 struct Email *sort_aux_key = NULL, *oldsort_aux_key = NULL;
776 struct Email *oldsort_thread_key = NULL;
777 int i, array_size;
778 bool sort_top = false;
779
780 /* we put things into the array backwards to save some cycles,
781 * but we want to have to move less stuff around if we're
782 * resorting, so we sort backwards and then put them back
783 * in reverse order so they're forwards */
784 const bool reverse = (mutt_thread_style() == UT_REVERSE);
785 short c_sort = cs_subset_sort(NeoMutt->sub, "sort");
786 short c_sort_aux = cs_subset_sort(NeoMutt->sub, "sort_aux");
787 if ((c_sort & SORT_MASK) == SORT_THREADS)
788 {
789 assert(!(c_sort & SORT_REVERSE) != reverse);
790 assert(cs_subset_enum(NeoMutt->sub, "use_threads") == UT_UNSET);
791 c_sort = c_sort_aux;
792 }
793 c_sort ^= SORT_REVERSE;
794 c_sort_aux ^= SORT_REVERSE;
795 if (init || tctx->c_sort != c_sort || tctx->c_sort_aux != c_sort_aux)
796 {
797 tctx->c_sort = c_sort;
798 tctx->c_sort_aux = c_sort_aux;
799 init = true;
800 }
801
802 top = thread;
803
804 array_size = 256;
805 array = mutt_mem_calloc(array_size, sizeof(struct MuttThread *));
806 while (true)
807 {
808 if (init || !thread->sort_thread_key || !thread->sort_aux_key)
809 {
810 thread->sort_thread_key = NULL;
811 thread->sort_aux_key = NULL;
812
813 if (thread->parent)
814 thread->parent->sort_children = true;
815 else
816 sort_top = true;
817 }
818
819 if (thread->child)
820 {
821 thread = thread->child;
822 continue;
823 }
824 else
825 {
826 /* if it has no children, it must be real. sort it on its own merits */
827 thread->sort_thread_key = thread->message;
828 thread->sort_aux_key = thread->message;
829
830 if (thread->next)
831 {
832 thread = thread->next;
833 continue;
834 }
835 }
836
837 while (!thread->next)
838 {
839 /* if it has siblings and needs to be sorted, sort it... */
840 if (thread->prev && (thread->parent ? thread->parent->sort_children : sort_top))
841 {
842 /* put them into the array */
843 for (i = 0; thread; i++, thread = thread->prev)
844 {
845 if (i >= array_size)
846 mutt_mem_realloc(&array, (array_size *= 2) * sizeof(struct MuttThread *));
847
848 array[i] = thread;
849 }
850
851 mutt_qsort_r((void *) array, i, sizeof(struct MuttThread *), compare_threads, tctx);
852
853 /* attach them back together. make thread the last sibling. */
854 thread = array[0];
855 thread->next = NULL;
856 array[i - 1]->prev = NULL;
857
858 if (thread->parent)
859 thread->parent->child = array[i - 1];
860 else
861 top = array[i - 1];
862
863 while (--i)
864 {
865 array[i - 1]->prev = array[i];
866 array[i]->next = array[i - 1];
867 }
868 }
869
870 if (thread->parent)
871 {
872 tmp = thread;
873 thread = thread->parent;
874
875 if (!thread->sort_thread_key || !thread->sort_aux_key || thread->sort_children)
876 {
877 /* we just sorted its children */
878 thread->sort_children = false;
879
880 oldsort_aux_key = thread->sort_aux_key;
881 oldsort_thread_key = thread->sort_thread_key;
882
883 /* update sort keys. sort_aux_key will be the first or last
884 * sibling, as appropriate... */
885 thread->sort_aux_key = thread->message;
886 sort_aux_key = ((!(c_sort_aux & SORT_LAST)) ^ (!(c_sort_aux & SORT_REVERSE))) ?
887 thread->child->sort_aux_key :
888 tmp->sort_aux_key;
889
890 if (c_sort_aux & SORT_LAST)
891 {
892 if (!thread->sort_aux_key ||
893 (mutt_compare_emails(thread->sort_aux_key, sort_aux_key, mx_type(tctx->mailbox),
894 c_sort_aux | SORT_REVERSE, SORT_ORDER) > 0))
895 {
896 thread->sort_aux_key = sort_aux_key;
897 }
898 }
899 else if (!thread->sort_aux_key)
900 thread->sort_aux_key = sort_aux_key;
901
902 /* ...but sort_thread_key may require searching the entire
903 * list of siblings */
904 if ((c_sort_aux & ~SORT_REVERSE) == (c_sort & ~SORT_REVERSE))
905 {
906 thread->sort_thread_key = thread->sort_aux_key;
907 }
908 else
909 {
910 if (thread->message)
911 {
912 thread->sort_thread_key = thread->message;
913 }
914 else if (reverse != (!(c_sort_aux & SORT_REVERSE)))
915 {
916 thread->sort_thread_key = tmp->sort_thread_key;
917 }
918 else
919 {
920 thread->sort_thread_key = thread->child->sort_thread_key;
921 }
922 if (c_sort & SORT_LAST)
923 {
924 for (tmp = thread->child; tmp; tmp = tmp->next)
925 {
926 if (tmp->sort_thread_key == thread->sort_thread_key)
927 continue;
928 if ((mutt_compare_emails(thread->sort_thread_key, tmp->sort_thread_key,
929 mx_type(tctx->mailbox),
930 c_sort | SORT_REVERSE, SORT_ORDER) > 0))
931 {
932 thread->sort_thread_key = tmp->sort_thread_key;
933 }
934 }
935 }
936 }
937
938 /* if a sort_key has changed, we need to resort it and siblings */
939 if ((oldsort_aux_key != thread->sort_aux_key) ||
940 (oldsort_thread_key != thread->sort_thread_key))
941 {
942 if (thread->parent)
943 thread->parent->sort_children = true;
944 else
945 sort_top = true;
946 }
947 }
948 }
949 else
950 {
951 FREE(&array);
952 tctx->tree = top;
953 return;
954 }
955 }
956
957 thread = thread->next;
958 }
959 }
960
961 /**
962 * check_subjects - Find out which emails' subjects differ from their parent's
963 * @param m Mailbox
964 * @param init If true, rebuild the thread
965 */
check_subjects(struct Mailbox * m,bool init)966 static void check_subjects(struct Mailbox *m, bool init)
967 {
968 if (!m)
969 return;
970
971 for (int i = 0; i < m->msg_count; i++)
972 {
973 struct Email *e = m->emails[i];
974 if (!e || !e->thread)
975 continue;
976
977 if (e->thread->check_subject)
978 e->thread->check_subject = false;
979 else if (!init)
980 continue;
981
982 /* figure out which messages have subjects different than their parents' */
983 struct MuttThread *tmp = e->thread->parent;
984 while (tmp && !tmp->message)
985 {
986 tmp = tmp->parent;
987 }
988
989 if (!tmp)
990 e->subject_changed = true;
991 else if (e->env->real_subj && tmp->message->env->real_subj)
992 {
993 e->subject_changed = !mutt_str_equal(e->env->real_subj, tmp->message->env->real_subj);
994 }
995 else
996 {
997 e->subject_changed = (e->env->real_subj || tmp->message->env->real_subj);
998 }
999 }
1000 }
1001
1002 /**
1003 * mutt_sort_threads - Sort email threads
1004 * @param tctx Threading context
1005 * @param init If true, rebuild the thread
1006 */
mutt_sort_threads(struct ThreadsContext * tctx,bool init)1007 void mutt_sort_threads(struct ThreadsContext *tctx, bool init)
1008 {
1009 if (!tctx || !tctx->mailbox)
1010 return;
1011
1012 struct Mailbox *m = tctx->mailbox;
1013
1014 struct Email *e = NULL;
1015 int i, using_refs = 0;
1016 struct MuttThread *thread = NULL, *tnew = NULL, *tmp = NULL;
1017 struct MuttThread top = { 0 };
1018 struct ListNode *ref = NULL;
1019
1020 assert(m->msg_count > 0);
1021 if (!tctx->hash)
1022 init = true;
1023
1024 if (init)
1025 {
1026 tctx->hash = mutt_hash_new(m->msg_count * 2, MUTT_HASH_ALLOW_DUPS);
1027 mutt_hash_set_destructor(tctx->hash, thread_hash_destructor, 0);
1028 }
1029
1030 /* we want a quick way to see if things are actually attached to the top of the
1031 * thread tree or if they're just dangling, so we attach everything to a top
1032 * node temporarily */
1033 top.parent = NULL;
1034 top.next = NULL;
1035 top.prev = NULL;
1036
1037 top.child = tctx->tree;
1038 for (thread = tctx->tree; thread; thread = thread->next)
1039 thread->parent = ⊤
1040
1041 /* put each new message together with the matching messageless MuttThread if it
1042 * exists. otherwise, if there is a MuttThread that already has a message, thread
1043 * new message as an identical child. if we didn't attach the message to a
1044 * MuttThread, make a new one for it. */
1045 const bool c_duplicate_threads =
1046 cs_subset_bool(NeoMutt->sub, "duplicate_threads");
1047 for (i = 0; i < m->msg_count; i++)
1048 {
1049 e = m->emails[i];
1050 if (!e)
1051 continue;
1052
1053 if (!e->thread)
1054 {
1055 if ((!init || c_duplicate_threads) && e->env->message_id)
1056 thread = mutt_hash_find(tctx->hash, e->env->message_id);
1057 else
1058 thread = NULL;
1059
1060 if (thread && !thread->message)
1061 {
1062 /* this is a message which was missing before */
1063 thread->message = e;
1064 e->thread = thread;
1065 thread->check_subject = true;
1066
1067 /* mark descendants as needing subject_changed checked */
1068 for (tmp = (thread->child ? thread->child : thread); tmp != thread;)
1069 {
1070 while (!tmp->message)
1071 tmp = tmp->child;
1072 tmp->check_subject = true;
1073 while (!tmp->next && (tmp != thread))
1074 tmp = tmp->parent;
1075 if (tmp != thread)
1076 tmp = tmp->next;
1077 }
1078
1079 if (thread->parent)
1080 {
1081 /* remove threading info above it based on its children, which we'll
1082 * recalculate based on its headers. make sure not to leave
1083 * dangling missing messages. note that we haven't kept track
1084 * of what info came from its children and what from its siblings'
1085 * children, so we just remove the stuff that's definitely from it */
1086 do
1087 {
1088 tmp = thread->parent;
1089 unlink_message(&tmp->child, thread);
1090 thread->parent = NULL;
1091 thread->sort_thread_key = NULL;
1092 thread->sort_aux_key = NULL;
1093 thread->fake_thread = false;
1094 thread = tmp;
1095 } while (thread != &top && !thread->child && !thread->message);
1096 }
1097 }
1098 else
1099 {
1100 tnew = (c_duplicate_threads ? thread : NULL);
1101
1102 thread = mutt_mem_calloc(1, sizeof(struct MuttThread));
1103 thread->message = e;
1104 thread->check_subject = true;
1105 e->thread = thread;
1106 mutt_hash_insert(tctx->hash, e->env->message_id ? e->env->message_id : "", thread);
1107
1108 if (tnew)
1109 {
1110 if (tnew->duplicate_thread)
1111 tnew = tnew->parent;
1112
1113 thread = e->thread;
1114
1115 insert_message(&tnew->child, tnew, thread);
1116 thread->duplicate_thread = true;
1117 thread->message->threaded = true;
1118 }
1119 }
1120 }
1121 else
1122 {
1123 /* unlink pseudo-threads because they might be children of newly
1124 * arrived messages */
1125 thread = e->thread;
1126 for (tnew = thread->child; tnew;)
1127 {
1128 tmp = tnew->next;
1129 if (tnew->fake_thread)
1130 {
1131 unlink_message(&thread->child, tnew);
1132 insert_message(&top.child, &top, tnew);
1133 tnew->fake_thread = false;
1134 }
1135 tnew = tmp;
1136 }
1137 }
1138 }
1139
1140 /* thread by references */
1141 for (i = 0; i < m->msg_count; i++)
1142 {
1143 e = m->emails[i];
1144 if (!e)
1145 break;
1146
1147 if (e->threaded)
1148 continue;
1149 e->threaded = true;
1150
1151 thread = e->thread;
1152 if (!thread)
1153 continue;
1154 using_refs = 0;
1155
1156 while (true)
1157 {
1158 if (using_refs == 0)
1159 {
1160 /* look at the beginning of in-reply-to: */
1161 ref = STAILQ_FIRST(&e->env->in_reply_to);
1162 if (ref)
1163 using_refs = 1;
1164 else
1165 {
1166 ref = STAILQ_FIRST(&e->env->references);
1167 using_refs = 2;
1168 }
1169 }
1170 else if (using_refs == 1)
1171 {
1172 /* if there's no references header, use all the in-reply-to:
1173 * data that we have. otherwise, use the first reference
1174 * if it's different than the first in-reply-to, otherwise use
1175 * the second reference (since at least eudora puts the most
1176 * recent reference in in-reply-to and the rest in references) */
1177 if (STAILQ_EMPTY(&e->env->references))
1178 ref = STAILQ_NEXT(ref, entries);
1179 else
1180 {
1181 if (!mutt_str_equal(ref->data, STAILQ_FIRST(&e->env->references)->data))
1182 ref = STAILQ_FIRST(&e->env->references);
1183 else
1184 ref = STAILQ_NEXT(STAILQ_FIRST(&e->env->references), entries);
1185
1186 using_refs = 2;
1187 }
1188 }
1189 else
1190 ref = STAILQ_NEXT(ref, entries); /* go on with references */
1191
1192 if (!ref)
1193 break;
1194
1195 tnew = mutt_hash_find(tctx->hash, ref->data);
1196 if (tnew)
1197 {
1198 if (tnew->duplicate_thread)
1199 tnew = tnew->parent;
1200 if (is_descendant(tnew, thread)) /* no loops! */
1201 continue;
1202 }
1203 else
1204 {
1205 tnew = mutt_mem_calloc(1, sizeof(struct MuttThread));
1206 mutt_hash_insert(tctx->hash, ref->data, tnew);
1207 }
1208
1209 if (thread->parent)
1210 unlink_message(&top.child, thread);
1211 insert_message(&tnew->child, tnew, thread);
1212 thread = tnew;
1213 if (thread->message || (thread->parent && (thread->parent != &top)))
1214 break;
1215 }
1216
1217 if (!thread->parent)
1218 insert_message(&top.child, &top, thread);
1219 }
1220
1221 /* detach everything from the temporary top node */
1222 for (thread = top.child; thread; thread = thread->next)
1223 {
1224 thread->parent = NULL;
1225 }
1226 tctx->tree = top.child;
1227
1228 check_subjects(tctx->mailbox, init);
1229
1230 const bool c_strict_threads = cs_subset_bool(NeoMutt->sub, "strict_threads");
1231 if (!c_strict_threads)
1232 pseudo_threads(tctx);
1233
1234 /* if $sort_aux or similar changed after the mailbox is sorted, then
1235 * all the subthreads need to be resorted */
1236 if (tctx->tree)
1237 {
1238 mutt_sort_subthreads(tctx, init || OptSortSubthreads);
1239 OptSortSubthreads = false;
1240
1241 /* Put the list into an array. */
1242 linearize_tree(tctx);
1243
1244 /* Draw the thread tree. */
1245 mutt_draw_tree(tctx);
1246 }
1247 }
1248
1249 /**
1250 * mutt_aside_thread - Find the next/previous (sub)thread
1251 * @param e Search from this Email
1252 * @param forwards Direction to search: 'true' forwards, 'false' backwards
1253 * @param subthreads Search subthreads: 'true' subthread, 'false' not
1254 * @retval num Index into the virtual email table
1255 */
mutt_aside_thread(struct Email * e,bool forwards,bool subthreads)1256 int mutt_aside_thread(struct Email *e, bool forwards, bool subthreads)
1257 {
1258 struct MuttThread *cur = NULL;
1259 struct Email *e_tmp = NULL;
1260
1261 const enum UseThreads threaded = mutt_thread_style();
1262 if (threaded == UT_FLAT)
1263 {
1264 mutt_error(_("Threading is not enabled"));
1265 return e->vnum;
1266 }
1267
1268 cur = e->thread;
1269
1270 if (subthreads)
1271 {
1272 if (forwards ^ (threaded == UT_REVERSE))
1273 {
1274 while (!cur->next && cur->parent)
1275 cur = cur->parent;
1276 }
1277 else
1278 {
1279 while (!cur->prev && cur->parent)
1280 cur = cur->parent;
1281 }
1282 }
1283 else
1284 {
1285 while (cur->parent)
1286 cur = cur->parent;
1287 }
1288
1289 if (forwards ^ (threaded == UT_REVERSE))
1290 {
1291 do
1292 {
1293 cur = cur->next;
1294 if (!cur)
1295 return -1;
1296 e_tmp = find_virtual(cur, false);
1297 } while (!e_tmp);
1298 }
1299 else
1300 {
1301 do
1302 {
1303 cur = cur->prev;
1304 if (!cur)
1305 return -1;
1306 e_tmp = find_virtual(cur, true);
1307 } while (!e_tmp);
1308 }
1309
1310 return e_tmp->vnum;
1311 }
1312
1313 /**
1314 * mutt_parent_message - Find the parent of a message
1315 * @param e Current Email
1316 * @param find_root If true, find the root message
1317 * @retval >=0 Virtual index number of parent/root message
1318 * @retval -1 Error
1319 */
mutt_parent_message(struct Email * e,bool find_root)1320 int mutt_parent_message(struct Email *e, bool find_root)
1321 {
1322 if (!e)
1323 return -1;
1324
1325 struct MuttThread *thread = NULL;
1326 struct Email *e_parent = NULL;
1327
1328 if (!mutt_using_threads())
1329 {
1330 mutt_error(_("Threading is not enabled"));
1331 return e->vnum;
1332 }
1333
1334 /* Root may be the current message */
1335 if (find_root)
1336 e_parent = e;
1337
1338 for (thread = e->thread->parent; thread; thread = thread->parent)
1339 {
1340 e = thread->message;
1341 if (e)
1342 {
1343 e_parent = e;
1344 if (!find_root)
1345 break;
1346 }
1347 }
1348
1349 if (!e_parent)
1350 {
1351 mutt_error(_("Parent message is not available"));
1352 return -1;
1353 }
1354 if (!is_visible(e_parent))
1355 {
1356 if (find_root)
1357 mutt_error(_("Root message is not visible in this limited view"));
1358 else
1359 mutt_error(_("Parent message is not visible in this limited view"));
1360 return -1;
1361 }
1362 return e_parent->vnum;
1363 }
1364
1365 /**
1366 * mutt_set_vnum - Set the virtual index number of all the messages in a mailbox
1367 * @param m Mailbox
1368 * @retval mum Size in bytes of all messages shown
1369 */
mutt_set_vnum(struct Mailbox * m)1370 off_t mutt_set_vnum(struct Mailbox *m)
1371 {
1372 if (!m)
1373 return 0;
1374
1375 off_t vsize = 0;
1376 const int padding = mx_msg_padding_size(m);
1377
1378 m->vcount = 0;
1379
1380 for (int i = 0; i < m->msg_count; i++)
1381 {
1382 struct Email *e = m->emails[i];
1383 if (!e)
1384 break;
1385
1386 if (e->vnum >= 0)
1387 {
1388 e->vnum = m->vcount;
1389 m->v2r[m->vcount] = i;
1390 m->vcount++;
1391 vsize += e->body->length + e->body->offset - e->body->hdr_offset + padding;
1392 }
1393 }
1394
1395 return vsize;
1396 }
1397
1398 /**
1399 * mutt_traverse_thread - Recurse through an email thread, matching messages
1400 * @param e_cur Current Email
1401 * @param flag Flag to set, see #MuttThreadFlags
1402 * @retval num Number of matches
1403 */
mutt_traverse_thread(struct Email * e_cur,MuttThreadFlags flag)1404 int mutt_traverse_thread(struct Email *e_cur, MuttThreadFlags flag)
1405 {
1406 struct MuttThread *thread = NULL, *top = NULL;
1407 struct Email *e_root = NULL;
1408 const enum UseThreads threaded = mutt_thread_style();
1409 int final, reverse = (threaded == UT_REVERSE), minmsgno;
1410 int num_hidden = 0, new_mail = 0, old_mail = 0;
1411 bool flagged = false;
1412 int min_unread_msgno = INT_MAX, min_unread = e_cur->vnum;
1413
1414 if (threaded == UT_FLAT)
1415 {
1416 mutt_error(_("Threading is not enabled"));
1417 return e_cur->vnum;
1418 }
1419
1420 if (!e_cur->thread)
1421 {
1422 return e_cur->vnum;
1423 }
1424
1425 final = e_cur->vnum;
1426 thread = e_cur->thread;
1427 while (thread->parent)
1428 thread = thread->parent;
1429 top = thread;
1430 while (!thread->message)
1431 thread = thread->child;
1432 e_cur = thread->message;
1433 minmsgno = e_cur->msgno;
1434
1435 if (!e_cur->read && e_cur->visible)
1436 {
1437 if (e_cur->old)
1438 old_mail = 2;
1439 else
1440 new_mail = 1;
1441 if (e_cur->msgno < min_unread_msgno)
1442 {
1443 min_unread = e_cur->vnum;
1444 min_unread_msgno = e_cur->msgno;
1445 }
1446 }
1447
1448 if (e_cur->flagged && e_cur->visible)
1449 flagged = true;
1450
1451 if ((e_cur->vnum == -1) && e_cur->visible)
1452 num_hidden++;
1453
1454 if (flag & (MUTT_THREAD_COLLAPSE | MUTT_THREAD_UNCOLLAPSE))
1455 {
1456 e_cur->pair = 0; /* force index entry's color to be re-evaluated */
1457 e_cur->collapsed = flag & MUTT_THREAD_COLLAPSE;
1458 if (e_cur->vnum != -1)
1459 {
1460 e_root = e_cur;
1461 if (flag & MUTT_THREAD_COLLAPSE)
1462 final = e_root->vnum;
1463 }
1464 }
1465
1466 if ((thread == top) && !(thread = thread->child))
1467 {
1468 /* return value depends on action requested */
1469 if (flag & (MUTT_THREAD_COLLAPSE | MUTT_THREAD_UNCOLLAPSE))
1470 {
1471 e_cur->num_hidden = num_hidden;
1472 return final;
1473 }
1474 if (flag & MUTT_THREAD_UNREAD)
1475 return (old_mail && new_mail) ? new_mail : (old_mail ? old_mail : new_mail);
1476 if (flag & MUTT_THREAD_NEXT_UNREAD)
1477 return min_unread;
1478 if (flag & MUTT_THREAD_FLAGGED)
1479 return flagged;
1480 }
1481
1482 while (true)
1483 {
1484 e_cur = thread->message;
1485
1486 if (e_cur)
1487 {
1488 if (flag & (MUTT_THREAD_COLLAPSE | MUTT_THREAD_UNCOLLAPSE))
1489 {
1490 e_cur->pair = 0; /* force index entry's color to be re-evaluated */
1491 e_cur->collapsed = flag & MUTT_THREAD_COLLAPSE;
1492 if (!e_root && e_cur->visible)
1493 {
1494 e_root = e_cur;
1495 if (flag & MUTT_THREAD_COLLAPSE)
1496 final = e_root->vnum;
1497 }
1498
1499 if (reverse && (flag & MUTT_THREAD_COLLAPSE) &&
1500 (e_cur->msgno < minmsgno) && e_cur->visible)
1501 {
1502 minmsgno = e_cur->msgno;
1503 final = e_cur->vnum;
1504 }
1505
1506 if (flag & MUTT_THREAD_COLLAPSE)
1507 {
1508 if (e_cur != e_root)
1509 e_cur->vnum = -1;
1510 }
1511 else
1512 {
1513 if (e_cur->visible)
1514 e_cur->vnum = e_cur->msgno;
1515 }
1516 }
1517
1518 if (!e_cur->read && e_cur->visible)
1519 {
1520 if (e_cur->old)
1521 old_mail = 2;
1522 else
1523 new_mail = 1;
1524 if (e_cur->msgno < min_unread_msgno)
1525 {
1526 min_unread = e_cur->vnum;
1527 min_unread_msgno = e_cur->msgno;
1528 }
1529 }
1530
1531 if (e_cur->flagged && e_cur->visible)
1532 flagged = true;
1533
1534 if ((e_cur->vnum == -1) && e_cur->visible)
1535 num_hidden++;
1536 }
1537
1538 if (thread->child)
1539 thread = thread->child;
1540 else if (thread->next)
1541 thread = thread->next;
1542 else
1543 {
1544 bool done = false;
1545 while (!thread->next)
1546 {
1547 thread = thread->parent;
1548 if (thread == top)
1549 {
1550 done = true;
1551 break;
1552 }
1553 }
1554 if (done)
1555 break;
1556 thread = thread->next;
1557 }
1558 }
1559
1560 /* re-traverse the thread and store num_hidden in all headers, with or
1561 * without a virtual index. this will allow ~v to match all collapsed
1562 * messages when switching sort order to non-threaded. */
1563 if (flag & MUTT_THREAD_COLLAPSE)
1564 {
1565 thread = top;
1566 while (true)
1567 {
1568 e_cur = thread->message;
1569 if (e_cur)
1570 e_cur->num_hidden = num_hidden + 1;
1571
1572 if (thread->child)
1573 thread = thread->child;
1574 else if (thread->next)
1575 thread = thread->next;
1576 else
1577 {
1578 bool done = false;
1579 while (!thread->next)
1580 {
1581 thread = thread->parent;
1582 if (thread == top)
1583 {
1584 done = true;
1585 break;
1586 }
1587 }
1588 if (done)
1589 break;
1590 thread = thread->next;
1591 }
1592 }
1593 }
1594
1595 /* return value depends on action requested */
1596 if (flag & (MUTT_THREAD_COLLAPSE | MUTT_THREAD_UNCOLLAPSE))
1597 return final;
1598 if (flag & MUTT_THREAD_UNREAD)
1599 return (old_mail && new_mail) ? new_mail : (old_mail ? old_mail : new_mail);
1600 if (flag & MUTT_THREAD_NEXT_UNREAD)
1601 return min_unread;
1602 if (flag & MUTT_THREAD_FLAGGED)
1603 return flagged;
1604
1605 return 0;
1606 }
1607
1608 /**
1609 * mutt_messages_in_thread - Count the messages in a thread
1610 * @param m Mailbox
1611 * @param e Email
1612 * @param mit Flag, e.g. #MIT_NUM_MESSAGES
1613 * @retval num Number of message / Our position
1614 */
mutt_messages_in_thread(struct Mailbox * m,struct Email * e,enum MessageInThread mit)1615 int mutt_messages_in_thread(struct Mailbox *m, struct Email *e, enum MessageInThread mit)
1616 {
1617 if (!m || !e)
1618 return 1;
1619
1620 struct MuttThread *threads[2];
1621 int rc;
1622
1623 const enum UseThreads threaded = mutt_thread_style();
1624 if ((threaded == UT_FLAT) || !e->thread)
1625 return 1;
1626
1627 threads[0] = e->thread;
1628 while (threads[0]->parent)
1629 threads[0] = threads[0]->parent;
1630
1631 threads[1] = (mit == MIT_POSITION) ? e->thread : threads[0]->next;
1632
1633 for (int i = 0; i < (((mit == MIT_POSITION) || !threads[1]) ? 1 : 2); i++)
1634 {
1635 while (!threads[i]->message)
1636 threads[i] = threads[i]->child;
1637 }
1638
1639 if (threaded == UT_REVERSE)
1640 rc = threads[0]->message->msgno - (threads[1] ? threads[1]->message->msgno : -1);
1641 else
1642 {
1643 rc = (threads[1] ? threads[1]->message->msgno : m->msg_count) -
1644 threads[0]->message->msgno;
1645 }
1646
1647 if (mit == MIT_POSITION)
1648 rc += 1;
1649
1650 return rc;
1651 }
1652
1653 /**
1654 * mutt_make_id_hash - Create a Hash Table for message-ids
1655 * @param m Mailbox
1656 * @retval ptr Newly allocated Hash Table
1657 */
mutt_make_id_hash(struct Mailbox * m)1658 struct HashTable *mutt_make_id_hash(struct Mailbox *m)
1659 {
1660 struct HashTable *hash = mutt_hash_new(m->msg_count * 2, MUTT_HASH_NO_FLAGS);
1661
1662 for (int i = 0; i < m->msg_count; i++)
1663 {
1664 struct Email *e = m->emails[i];
1665 if (!e || !e->env)
1666 continue;
1667
1668 if (e->env->message_id)
1669 mutt_hash_insert(hash, e->env->message_id, e);
1670 }
1671
1672 return hash;
1673 }
1674
1675 /**
1676 * link_threads - Forcibly link messages together
1677 * @param parent Parent Email
1678 * @param child Child Email
1679 * @param m Mailbox
1680 * @retval true On success
1681 */
link_threads(struct Email * parent,struct Email * child,struct Mailbox * m)1682 static bool link_threads(struct Email *parent, struct Email *child, struct Mailbox *m)
1683 {
1684 if (child == parent)
1685 return false;
1686
1687 mutt_break_thread(child);
1688 mutt_list_insert_head(&child->env->in_reply_to, mutt_str_dup(parent->env->message_id));
1689 mutt_set_flag(m, child, MUTT_TAG, false);
1690
1691 child->changed = true;
1692 child->env->changed |= MUTT_ENV_CHANGED_IRT;
1693 return true;
1694 }
1695
1696 /**
1697 * mutt_link_threads - Forcibly link threads together
1698 * @param parent Parent Email
1699 * @param children List of children Emails
1700 * @param m Mailbox
1701 * @retval true On success
1702 */
mutt_link_threads(struct Email * parent,struct EmailList * children,struct Mailbox * m)1703 bool mutt_link_threads(struct Email *parent, struct EmailList *children, struct Mailbox *m)
1704 {
1705 if (!parent || !children || !m)
1706 return false;
1707
1708 bool changed = false;
1709
1710 struct EmailNode *en = NULL;
1711 STAILQ_FOREACH(en, children, entries)
1712 {
1713 changed |= link_threads(parent, en->email, m);
1714 }
1715
1716 return changed;
1717 }
1718
1719 /**
1720 * mutt_thread_collapse_collapsed - Re-collapse threads marked as collapsed
1721 * @param tctx Threading context
1722 */
mutt_thread_collapse_collapsed(struct ThreadsContext * tctx)1723 void mutt_thread_collapse_collapsed(struct ThreadsContext *tctx)
1724 {
1725 struct MuttThread *thread = NULL;
1726 struct MuttThread *top = tctx->tree;
1727 while ((thread = top))
1728 {
1729 while (!thread->message)
1730 thread = thread->child;
1731
1732 struct Email *e = thread->message;
1733 if (e->collapsed)
1734 mutt_collapse_thread(e);
1735 top = top->next;
1736 }
1737 }
1738
1739 /**
1740 * mutt_thread_collapse - Toggle collapse
1741 * @param tctx Threading context
1742 * @param collapse Collapse / uncollapse
1743 */
mutt_thread_collapse(struct ThreadsContext * tctx,bool collapse)1744 void mutt_thread_collapse(struct ThreadsContext *tctx, bool collapse)
1745 {
1746 struct MuttThread *thread = NULL;
1747 struct MuttThread *top = tctx->tree;
1748 while ((thread = top))
1749 {
1750 while (!thread->message)
1751 thread = thread->child;
1752
1753 struct Email *e = thread->message;
1754
1755 if (e->collapsed != collapse)
1756 {
1757 if (e->collapsed)
1758 mutt_uncollapse_thread(e);
1759 else if (mutt_thread_can_collapse(e))
1760 mutt_collapse_thread(e);
1761 }
1762 top = top->next;
1763 }
1764 }
1765
1766 /**
1767 * mutt_thread_can_collapse - Check whether a thread can be collapsed
1768 * @param e Head of the thread
1769 * @retval true Can be collapsed
1770 * @retval false Cannot be collapsed
1771 */
mutt_thread_can_collapse(struct Email * e)1772 bool mutt_thread_can_collapse(struct Email *e)
1773 {
1774 const bool c_collapse_flagged =
1775 cs_subset_bool(NeoMutt->sub, "collapse_flagged");
1776 const bool c_collapse_unread =
1777 cs_subset_bool(NeoMutt->sub, "collapse_unread");
1778 return (c_collapse_unread || !mutt_thread_contains_unread(e)) &&
1779 (c_collapse_flagged || !mutt_thread_contains_flagged(e));
1780 }
1781