1 /*@ S-nail - a mail user agent derived from Berkeley Mail.
2 *@ Message threading. TODO thread handling needs rewrite, m_collapsed must go
4 * Copyright (c) 2000-2004 Gunnar Ritter, Freiburg i. Br., Germany.
5 * Copyright (c) 2012 - 2018 Steffen (Daode) Nurpmeso <steffen@sdaoden.eu>.
6 * SPDX-License-Identifier: BSD-4-Clause
10 * Gunnar Ritter. All rights reserved.
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
15 * 1. Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
20 * 3. All advertising materials mentioning features or use of this software
21 * must display the following acknowledgement:
22 * This product includes software developed by Gunnar Ritter
23 * and his contributors.
24 * 4. Neither the name of Gunnar Ritter nor the names of his contributors
25 * may be used to endorse or promote products derived from this software
26 * without specific prior written permission.
28 * THIS SOFTWARE IS PROVIDED BY GUNNAR RITTER AND CONTRIBUTORS ``AS IS'' AND
29 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
30 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
31 * ARE DISCLAIMED. IN NO EVENT SHALL GUNNAR RITTER OR CONTRIBUTORS BE LIABLE
32 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
33 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
34 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
35 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
36 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
37 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
43 #ifndef HAVE_AMALGAMATION
47 /* Open addressing is used for Message-IDs because the maximum number of
48 * messages in the table is known in advance (== msgCount) */
50 struct message
*mi_data
;
53 #define NOT_AN_ID ((struct mitem*)-1)
66 /* Return the hash value for a message id modulo mprime, or mprime if the
67 * passed string does not look like a message-id */
68 static ui32_t
_mhash(char const *cp
, ui32_t mprime
);
70 /* Look up a message id. Returns NOT_AN_ID if the passed string does not look
71 * like a message-id */
72 static struct mitem
* _mlook(char *id
, struct mitem
*mt
,
73 struct message
*mdata
, ui32_t mprime
);
75 /* Child is to be adopted by parent. A thread tree is structured as follows:
77 * ------ m_child ------ m_child
78 * | |-------------------->| |------------------------> . . .
79 * | |<--------------------| |<----------------------- . . .
80 * ------ m_parent ------ m_parent
82 * | \____ m_younger | |
91 * | |------------------------> . . .
92 * | |<----------------------- . . .
97 * The base message of a thread does not have a m_parent link. Elements
98 * connected by m_younger/m_elder links are replies to the same message, which
99 * is connected to them by m_parent links. The first reply to a message gets
100 * the m_child link */
101 static void _adopt(struct message
*parent
, struct message
*child
,
104 /* Connect all msgs on the lowest thread level with m_younger/m_elder links */
105 static struct message
* _interlink(struct message
*m
, ui32_t cnt
, int nmail
);
107 static void _finalize(struct message
*mp
);
109 /* Several sort comparison PTFs */
111 static int _mui32lt(void const *a
, void const *b
);
113 static int _mlonglt(void const *a
, void const *b
);
114 static int _mcharlt(void const *a
, void const *b
);
116 static void _lookup(struct message
*m
, struct mitem
*mi
,
118 static void _makethreads(struct message
*m
, ui32_t cnt
, int nmail
);
119 static int _colpt(int *msgvec
, int cl
);
120 static void _colps(struct message
*b
, int cl
);
121 static void _colpm(struct message
*m
, int cl
, int *cc
, int *uc
);
124 _mhash(char const *cp
, ui32_t mprime
)
126 ui32_t h
= 0, g
, at
= 0;
129 for (--cp
; *++cp
!= '\0';) {
130 /* Pay attention not to hash characters which are irrelevant for
131 * Message-ID semantics */
133 cp
= skip_comment(cp
+ 1) - 1;
136 if (*cp
== '"' || *cp
== '\\')
140 /* TODO torek hash */
141 h
= ((h
<< 4) & 0xffffffff) + lowerconv(*cp
);
142 if ((g
= h
& 0xf0000000) != 0) {
148 return (at
? h
% mprime
: mprime
);
151 static struct mitem
*
152 _mlook(char *id
, struct mitem
*mt
, struct message
*mdata
, ui32_t mprime
)
154 struct mitem
*mp
= NULL
;
159 if ((id
= hfield1("message-id", mdata
)) == NULL
)
161 /* Normalize, what hfield1() doesn't do (TODO should now GREF, too!!) */
163 id
[strlen(id
) -1] = '\0';
169 if (mdata
!= NULL
&& mdata
->m_idhash
)
170 h
= ~mdata
->m_idhash
;
172 h
= _mhash(id
, mprime
);
180 while (mp
->mi_id
!= NULL
) {
181 if (!msgidcmp(mp
->mi_id
, id
))
183 c
+= (n
& 1) ? -((n
+1)/2) * ((n
+1)/2) : ((n
+1)/2) * ((n
+1)/2);
187 else while (c
>= mprime
)
192 if (mdata
!= NULL
&& mp
->mi_id
== NULL
) {
193 mp
->mi_id
= sstrdup(id
);
195 mdata
->m_idhash
= ~h
;
197 if (mp
->mi_id
== NULL
)
205 _adopt(struct message
*parent
, struct message
*child
, int dist
)
207 struct message
*mp
, *mq
;
210 for (mp
= parent
; mp
!= NULL
; mp
= mp
->m_parent
)
214 child
->m_level
= dist
; /* temporarily store distance */
215 child
->m_parent
= parent
;
217 if (parent
->m_child
!= NULL
) {
219 for (mp
= parent
->m_child
; mp
!= NULL
; mp
= mp
->m_younger
) {
220 if (mp
->m_date
>= child
->m_date
) {
221 if (mp
->m_elder
!= NULL
)
222 mp
->m_elder
->m_younger
= child
;
223 child
->m_elder
= mp
->m_elder
;
225 child
->m_younger
= mp
;
226 if (mp
== parent
->m_child
)
227 parent
->m_child
= child
;
232 mq
->m_younger
= child
;
235 parent
->m_child
= child
;
240 static struct message
*
241 _interlink(struct message
*m
, ui32_t cnt
, int nmail
)
243 struct message
*root
;
249 autocollapse
= (!nmail
&& !(n_pstate
& n_PS_HOOK_NEWMAIL
) &&
250 ok_blook(autocollapse
));
251 ms
= n_alloc(sizeof *ms
* cnt
);
253 for (n
= 0, i
= 0; UICMP(32, i
, <, cnt
); ++i
) {
254 if (m
[i
].m_parent
== NULL
) {
257 ms
[n
].ms_u
.ms_long
= m
[i
].m_date
;
264 qsort(ms
, n
, sizeof *ms
, &_mlonglt
);
265 root
= m
+ ms
[0].ms_n
;
266 for (i
= 1; UICMP(32, i
, <, n
); ++i
) {
267 m
[ms
[i
-1].ms_n
].m_younger
= m
+ ms
[i
].ms_n
;
268 m
[ms
[i
].ms_n
].m_elder
= m
+ ms
[i
- 1].ms_n
;
279 _finalize(struct message
*mp
)
284 for (n
= 0; mp
; mp
= next_in_thread(mp
)) {
285 mp
->m_threadpos
= ++n
;
286 mp
->m_level
= mp
->m_parent
? mp
->m_level
+ mp
->m_parent
->m_level
: 0;
293 _mui32lt(void const *a
, void const *b
)
295 struct msort
const *xa
= a
, *xb
= b
;
299 i
= (int)(xa
->ms_u
.ms_ui
- xb
->ms_u
.ms_ui
);
301 i
= xa
->ms_n
- xb
->ms_n
;
308 _mlonglt(void const *a
, void const *b
)
310 struct msort
const *xa
= a
, *xb
= b
;
314 i
= (int)(xa
->ms_u
.ms_long
- xb
->ms_u
.ms_long
);
316 i
= xa
->ms_n
- xb
->ms_n
;
322 _mcharlt(void const *a
, void const *b
)
324 struct msort
const *xa
= a
, *xb
= b
;
328 i
= strcoll(xa
->ms_u
.ms_char
, xb
->ms_u
.ms_char
);
330 i
= xa
->ms_n
- xb
->ms_n
;
336 _lookup(struct message
*m
, struct mitem
*mi
, ui32_t mprime
)
344 if (m
->m_flag
& MHIDDEN
)
348 if ((cp
= hfield1("in-reply-to", m
)) != NULL
) {
349 if ((np
= extract(cp
, GREF
)) != NULL
)
351 if ((ip
= _mlook(np
->n_name
, mi
, NULL
, mprime
)) != NULL
&&
353 _adopt(ip
->mi_data
, m
, 1);
356 } while ((np
= np
->n_flink
) != NULL
);
359 if ((cp
= hfield1("references", m
)) != NULL
) {
360 if ((np
= extract(cp
, GREF
)) != NULL
) {
361 while (np
->n_flink
!= NULL
)
364 if ((ip
= _mlook(np
->n_name
, mi
, NULL
, mprime
)) != NULL
) {
366 continue; /* skip dist++ */
367 _adopt(ip
->mi_data
, m
, dist
);
371 } while ((np
= np
->n_blink
) != NULL
);
379 _makethreads(struct message
*m
, ui32_t cnt
, int nmail
)
389 /* It is performance crucial to space this large enough in order to minimize
391 mprime
= n_prime_next((cnt
< UI32_MAX
>> 3) ? cnt
<< 2 : cnt
);
392 mt
= n_calloc(mprime
, sizeof *mt
);
396 for (i
= 0; i
< cnt
; ++i
) {
397 if (!(m
[i
].m_flag
& MHIDDEN
)) {
398 _mlook(NULL
, mt
, m
+ i
, mprime
);
399 if (m
[i
].m_date
== 0) {
400 if ((cp
= hfield1("date", m
+ i
)) != NULL
)
401 m
[i
].m_date
= rfctime(cp
);
404 m
[i
].m_child
= m
[i
].m_younger
= m
[i
].m_elder
= m
[i
].m_parent
= NULL
;
406 if (!nmail
&& !(n_pstate
& n_PS_HOOK_NEWMAIL
))
407 m
[i
].m_collapsed
= 0;
411 /* Most folders contain the eldest messages first. Traversing them in
412 * descending order makes it more likely that younger brothers are found
413 * first, so elder ones can be prepended to the brother list, which is
414 * faster. The worst case is still in O(n^2) and occurs when all but one
415 * messages in a folder are replies to the one message, and are sorted such
416 * that youngest messages occur first */
417 for (i
= cnt
; i
> 0; --i
) {
418 _lookup(m
+ i
- 1, mt
, mprime
);
424 threadroot
= _interlink(m
, cnt
, nmail
);
425 _finalize(threadroot
);
427 for (i
= 0; i
< mprime
; ++i
)
428 if (mt
[i
].mi_id
!= NULL
)
438 _colpt(int *msgvec
, int cl
)
443 if (mb
.mb_threaded
!= 1) {
444 fputs("Not in threaded mode.\n", n_stdout
);
447 for (ip
= msgvec
; *ip
!= 0; ++ip
)
448 _colps(message
+ *ip
- 1, cl
);
456 _colps(struct message
*b
, int cl
)
462 if (cl
&& (b
->m_collapsed
> 0 || (b
->m_flag
& (MNEW
| MREAD
)) == MNEW
))
465 if (b
->m_child
!= NULL
) {
467 _colpm(m
, cl
, &cc
, &uc
);
468 for (m
= m
->m_younger
; m
!= NULL
; m
= m
->m_younger
)
469 _colpm(m
, cl
, &cc
, &uc
);
473 b
->m_collapsed
= -cc
;
474 for (m
= b
->m_parent
; m
!= NULL
; m
= m
->m_parent
)
475 if (m
->m_collapsed
<= -uc
) {
476 m
->m_collapsed
+= uc
;
480 if (b
->m_collapsed
> 0) {
484 for (m
= b
; m
!= NULL
; m
= m
->m_parent
)
485 if (m
->m_collapsed
<= -uc
) {
486 m
->m_collapsed
+= uc
;
495 _colpm(struct message
*m
, int cl
, int *cc
, int *uc
)
499 if (m
->m_collapsed
> 0)
501 if ((m
->m_flag
& (MNEW
| MREAD
)) != MNEW
|| m
->m_collapsed
< 0)
503 if (m
->m_collapsed
> 0)
506 if (m
->m_collapsed
> 0) {
512 if (m
->m_child
!= NULL
) {
514 _colpm(m
, cl
, cc
, uc
);
515 for (m
= m
->m_younger
; m
!= NULL
; m
= m
->m_younger
)
516 _colpm(m
, cl
, cc
, uc
);
527 if (mb
.mb_threaded
!= 1 || vp
== NULL
|| vp
== (void*)-1) {
529 if (mb
.mb_type
== MB_IMAP
)
530 imap_getheaders(1, msgCount
);
532 _makethreads(message
, msgCount
, (vp
== (void*)-1));
533 if (mb
.mb_sorted
!= NULL
)
534 n_free(mb
.mb_sorted
);
535 mb
.mb_sorted
= sstrdup("thread");
538 if (vp
!= NULL
&& vp
!= (void*)-1 && !(n_pstate
& n_PS_HOOK_MASK
) &&
540 rv
= print_header_group(vp
);
555 if (mb
.mb_sorted
!= NULL
)
556 n_free(mb
.mb_sorted
);
559 for (m
= message
; PTRCMP(m
, <, message
+ msgCount
); ++m
)
562 if (vp
&& !(n_pstate
& n_PS_HOOK_MASK
) && ok_blook(header
))
563 rv
= print_header_group(vp
);
571 next_in_thread(struct message
*mp
)
576 if ((rv
= mp
->m_child
) != NULL
)
578 if ((rv
= mp
->m_younger
) != NULL
)
581 while ((rv
= mp
->m_parent
) != NULL
) {
583 if ((rv
= rv
->m_younger
) != NULL
)
592 prev_in_thread(struct message
*mp
)
597 if ((rv
= mp
->m_elder
) != NULL
) {
598 for (mp
= rv
; (rv
= mp
->m_child
) != NULL
;) {
600 while ((rv
= mp
->m_younger
) != NULL
)
613 this_in_thread(struct message
*mp
, long n
)
618 if (n
== -1) { /* find end of thread */
620 if ((rv
= mp
->m_younger
) != NULL
) {
624 rv
= next_in_thread(mp
);
625 if (rv
== NULL
|| rv
->m_threadpos
< mp
->m_threadpos
) {
635 while (mp
!= NULL
&& mp
->m_threadpos
< n
) {
636 if ((rv
= mp
->m_younger
) != NULL
&& rv
->m_threadpos
<= n
) {
640 mp
= next_in_thread(mp
);
642 rv
= (mp
!= NULL
&& mp
->m_threadpos
== n
) ? mp
: NULL
;
651 enum method
{SORT_SUBJECT
, SORT_DATE
, SORT_STATUS
, SORT_SIZE
, SORT_FROM
,
652 SORT_TO
, SORT_SPAM
, SORT_THREAD
} method
;
655 enum method me_method
;
656 int (*me_func
)(void const *, void const *);
657 } const methnames
[] = {
658 {"date", SORT_DATE
, &_mlonglt
},
659 {"from", SORT_FROM
, &_mcharlt
},
660 {"to", SORT_TO
, &_mcharlt
},
661 {"subject", SORT_SUBJECT
, &_mcharlt
},
662 {"size", SORT_SIZE
, &_mlonglt
},
664 {"spam", SORT_SPAM
, &_mui32lt
},
666 {"status", SORT_STATUS
, &_mlonglt
},
667 {"thread", SORT_THREAD
, NULL
}
671 char *_args
[2], *cp
, **args
= vp
;
673 int (*func
)(void const *, void const *);
679 if (vp
== NULL
|| vp
== (void*)-1) {
680 _args
[0] = savestr((mb
.mb_sorted
!= NULL
) ? mb
.mb_sorted
: "unsorted");
683 } else if (args
[0] == NULL
) {
684 fprintf(n_stdout
, "Current sorting criterion is: %s\n",
685 (mb
.mb_sorted
!= NULL
) ? mb
.mb_sorted
: "unsorted");
692 if (*args
[0] != '\0' && is_prefix(args
[0], methnames
[i
].me_name
))
694 if (UICMP(z
, ++i
, >=, n_NELEM(methnames
))) {
695 n_err(_("Unknown sorting method: %s\n"), args
[0]);
701 if (mb
.mb_sorted
!= NULL
)
702 n_free(mb
.mb_sorted
);
703 mb
.mb_sorted
= sstrdup(args
[0]);
705 method
= methnames
[i
].me_method
;
706 func
= methnames
[i
].me_func
;
707 msgvec
[0] = (int)PTR2SIZE(dot
- message
+ 1);
710 if (method
== SORT_THREAD
) {
711 i
= c_thread((vp
!= NULL
&& vp
!= (void*)-1) ? msgvec
: vp
);
715 showname
= ok_blook(showname
);
716 ms
= n_lofi_alloc(sizeof *ms
* msgCount
);
723 if (mb
.mb_type
== MB_IMAP
)
724 imap_getheaders(1, msgCount
);
732 for (n
= 0, i
= 0; i
< msgCount
; ++i
) {
734 if (!(mp
->m_flag
& MHIDDEN
)) {
737 if (mp
->m_date
== 0 && (cp
= hfield1("date", mp
)) != NULL
)
738 mp
->m_date
= rfctime(cp
);
739 ms
[n
].ms_u
.ms_long
= mp
->m_date
;
742 if (mp
->m_flag
& MDELETED
)
743 ms
[n
].ms_u
.ms_long
= 1;
744 else if ((mp
->m_flag
& (MNEW
| MREAD
)) == MNEW
)
745 ms
[n
].ms_u
.ms_long
= 90;
746 else if (mp
->m_flag
& MFLAGGED
)
747 ms
[n
].ms_u
.ms_long
= 85;
748 else if ((mp
->m_flag
& (MNEW
| MBOX
)) == MBOX
)
749 ms
[n
].ms_u
.ms_long
= 70;
750 else if (mp
->m_flag
& MNEW
)
751 ms
[n
].ms_u
.ms_long
= 80;
752 else if (mp
->m_flag
& MREAD
)
753 ms
[n
].ms_u
.ms_long
= 40;
755 ms
[n
].ms_u
.ms_long
= 60;
758 ms
[n
].ms_u
.ms_long
= mp
->m_xsize
;
762 ms
[n
].ms_u
.ms_ui
= mp
->m_spamscore
;
767 if ((cp
= hfield1((method
== SORT_FROM
? "from" : "to"), mp
)) !=
769 ms
[n
].ms_u
.ms_char
= sstrdup(showname
? realname(cp
) : skin(cp
));
770 makelow(ms
[n
].ms_u
.ms_char
);
772 ms
[n
].ms_u
.ms_char
= sstrdup(n_empty
);
776 if ((cp
= hfield1("subject", mp
)) != NULL
) {
779 mime_fromhdr(&in
, &out
, TD_ICONV
);
780 ms
[n
].ms_u
.ms_char
= sstrdup(subject_re_trim(out
.s
));
782 makelow(ms
[n
].ms_u
.ms_char
);
784 ms
[n
].ms_u
.ms_char
= sstrdup(n_empty
);
789 mp
->m_child
= mp
->m_younger
= mp
->m_elder
= mp
->m_parent
= NULL
;
797 qsort(ms
, n
, sizeof *ms
, func
);
798 threadroot
= message
+ ms
[0].ms_n
;
799 for (i
= 1; i
< n
; ++i
) {
800 message
[ms
[i
- 1].ms_n
].m_younger
= message
+ ms
[i
].ms_n
;
801 message
[ms
[i
].ms_n
].m_elder
= message
+ ms
[i
- 1].ms_n
;
806 _finalize(threadroot
);
813 for (i
= 0; i
< n
; ++i
)
814 n_free(ms
[i
].ms_u
.ms_char
);
821 i
= ((vp
!= NULL
&& vp
!= (void*)-1 && !(n_pstate
& n_PS_HOOK_MASK
) &&
822 ok_blook(header
)) ? print_header_group(msgvec
) : 0);
840 c_uncollapse(void *v
)
851 uncollapse1(struct message
*mp
, int always
)
854 if (mb
.mb_threaded
== 1 && (always
|| mp
->m_collapsed
> 0))