NEWS: update for v14.5.2
[s-mailx.git] / thread.c
blob3ac596652a03731fa337457ec9e2fe095462102b
1 /*@ S-nail - a mail user agent derived from Berkeley Mail.
2 *@ Message threading.
4 * Copyright (c) 2000-2004 Gunnar Ritter, Freiburg i. Br., Germany.
5 * Copyright (c) 2012 - 2014 Steffen "Daode" Nurpmeso <sdaoden@users.sf.net>.
6 */
7 /*
8 * Copyright (c) 2004
9 * Gunnar Ritter. All rights reserved.
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. All advertising materials mentioning features or use of this software
20 * must display the following acknowledgement:
21 * This product includes software developed by Gunnar Ritter
22 * and his contributors.
23 * 4. Neither the name of Gunnar Ritter nor the names of his contributors
24 * may be used to endorse or promote products derived from this software
25 * without specific prior written permission.
27 * THIS SOFTWARE IS PROVIDED BY GUNNAR RITTER AND CONTRIBUTORS ``AS IS'' AND
28 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
30 * ARE DISCLAIMED. IN NO EVENT SHALL GUNNAR RITTER OR CONTRIBUTORS BE LIABLE
31 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
32 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
33 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
34 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
35 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
36 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 * SUCH DAMAGE.
40 #ifndef HAVE_AMALGAMATION
41 # include "nail.h"
42 #endif
45 * Open addressing is used for Message-IDs because the maximum number of
46 * messages in the table is known in advance (== msgCount).
48 struct mitem {
49 struct message *mi_data;
50 char *mi_id;
53 struct msort {
54 union {
55 #ifdef HAVE_SPAM
56 ui_it ms_ui;
57 #endif
58 long ms_long;
59 char * ms_char;
60 } ms_u;
61 int ms_n;
64 static unsigned mhash(const char *cp, int mprime);
65 static struct mitem *mlook(char *id, struct mitem *mt, struct message *mdata,
66 int mprime);
67 static void adopt(struct message *parent, struct message *child, int dist);
68 static struct message *interlink(struct message *m, long cnt, int nmail);
69 static void finalize(struct message *mp);
70 #ifdef HAVE_SPAM
71 static int muilt(void const *a, void const *b);
72 #endif
73 static int mlonglt(const void *a, const void *b);
74 static int mcharlt(const void *a, const void *b);
75 static void lookup(struct message *m, struct mitem *mi, int mprime);
76 static void makethreads(struct message *m, long cnt, int nmail);
77 static char const *skipre(char const *cp);
78 static int colpt(int *msgvec, int cl);
79 static void colps(struct message *b, int cl);
80 static void colpm(struct message *m, int cl, int *cc, int *uc);
83 * Return the hash value for a message id modulo mprime, or mprime
84 * if the passed string does not look like a message-id.
86 static unsigned
87 mhash(const char *cp, int mprime)
90 unsigned h = 0, g, at = 0;
92 cp--;
93 while (*++cp) {
95 * Pay attention not to hash characters which are
96 * irrelevant for Message-ID semantics.
98 if (*cp == '(') {
99 cp = skip_comment(&cp[1]) - 1;
100 continue;
102 if (*cp == '"' || *cp == '\\')
103 continue;
104 if (*cp == '@')
105 at++;
106 h = ((h << 4) & 0xffffffff) + lowerconv(*cp & 0377);
107 if ((g = h & 0xf0000000) != 0) {
108 h = h ^ (g >> 24);
109 h = h ^ g;
112 return at ? h % (unsigned int)mprime : (unsigned int)mprime;
115 #define NOT_AN_ID ((struct mitem *)-1)
118 * Look up a message id. Returns NOT_AN_ID if the passed string does
119 * not look like a message-id.
121 static struct mitem *
122 mlook(char *id, struct mitem *mt, struct message *mdata, int mprime)
124 struct mitem *mp;
125 unsigned h, c, n = 0;
127 if (id == NULL && (id = hfield1("message-id", mdata)) == NULL)
128 return NULL;
129 if (mdata && mdata->m_idhash)
130 h = ~mdata->m_idhash;
131 else {
132 h = mhash(id, mprime);
133 if (h == (unsigned int)mprime)
134 return NOT_AN_ID;
136 mp = &mt[c = h];
137 while (mp->mi_id != NULL) {
138 if (msgidcmp(mp->mi_id, id) == 0)
139 break;
140 c += n&1 ? -((n+1)/2) * ((n+1)/2) : ((n+1)/2) * ((n+1)/2);
141 n++;
142 while (c >= (unsigned int)mprime)
143 c -= mprime;
144 mp = &mt[c];
146 if (mdata != NULL && mp->mi_id == NULL) {
147 mp->mi_id = id;
148 mp->mi_data = mdata;
149 mdata->m_idhash = ~h;
151 return mp->mi_id ? mp : NULL;
155 * Child is to be adopted by parent. A thread tree is structured
156 * as follows:
158 * ------ m_child ------ m_child
159 * | |-------------------->| |------------------------> . . .
160 * | |<--------------------| |<----------------------- . . .
161 * ------ m_parent ------ m_parent
162 * ^^ | ^
163 * | \____ m_younger | |
164 * | \ | |
165 * | ---- | |
166 * | \ | | m_elder
167 * | m_parent ---- | |
168 * | \ | |
169 * | ---- | |
170 * | \ + |
171 * | ------ m_child
172 * | | |------------------------> . . .
173 * | | |<----------------------- . . .
174 * | ------ m_parent
175 * | | ^
176 * \----- m_younger | |
177 * \ | |
178 * ---- | |
179 * \ | | m_elder
180 * m_parent ---- | |
181 * \ | |
182 * ---- | |
183 * \ + |
184 * ------ m_child
185 * | |------------------------> . . .
186 * | |<----------------------- . . .
187 * ------ m_parent
188 * | ^
189 * . . .
191 * The base message of a thread does not have a m_parent link. Elements
192 * connected by m_younger/m_elder links are replies to the same message,
193 * which is connected to them by m_parent links. The first reply to a
194 * message gets the m_child link.
196 static void
197 adopt(struct message *parent, struct message *child, int dist)
199 struct message *mp, *mq;
201 for (mp = parent; mp; mp = mp->m_parent)
202 if (mp == child)
203 return;
204 child->m_level = dist; /* temporarily store distance */
205 child->m_parent = parent;
206 if (parent->m_child != NULL) {
207 mq = NULL;
208 for (mp = parent->m_child; mp; mp = mp->m_younger) {
209 if (mp->m_date >= child->m_date) {
210 if (mp->m_elder)
211 mp->m_elder->m_younger = child;
212 child->m_elder = mp->m_elder;
213 mp->m_elder = child;
214 child->m_younger = mp;
215 if (mp == parent->m_child)
216 parent->m_child = child;
217 return;
219 mq = mp;
221 mq->m_younger = child;
222 child->m_elder = mq;
223 } else
224 parent->m_child = child;
228 * Connect all messages on the lowest thread level with m_younger/m_elder
229 * links.
231 static struct message *
232 interlink(struct message *m, long cnt, int nmail)
234 int i;
235 long n;
236 struct msort *ms;
237 struct message *root;
238 int autocollapse = !nmail && !(inhook&2) &&
239 ok_blook(autocollapse);
241 ms = smalloc(sizeof *ms * cnt);
242 for (n = 0, i = 0; i < cnt; i++) {
243 if (m[i].m_parent == NULL) {
244 if (autocollapse)
245 colps(&m[i], 1);
246 ms[n].ms_u.ms_long = m[i].m_date;
247 ms[n].ms_n = i;
248 n++;
251 if (n > 0) {
252 qsort(ms, n, sizeof *ms, mlonglt);
253 root = &m[ms[0].ms_n];
254 for (i = 1; i < n; i++) {
255 m[ms[i-1].ms_n].m_younger = &m[ms[i].ms_n];
256 m[ms[i].ms_n].m_elder = &m[ms[i-1].ms_n];
258 } else
259 root = &m[0];
260 free(ms);
261 return root;
264 static void
265 finalize(struct message *mp)
267 long n;
269 for (n = 0; mp; mp = next_in_thread(mp)) {
270 mp->m_threadpos = ++n;
271 mp->m_level = mp->m_parent ?
272 mp->m_level + mp->m_parent->m_level : 0;
276 #ifdef HAVE_SPAM
277 static int
278 muilt(void const *a, void const *b)
280 struct msort const *xa = a, *xb = b;
281 int i;
283 i = (int)(xa->ms_u.ms_ui - xb->ms_u.ms_ui);
284 if (i == 0)
285 i = xa->ms_n - xb->ms_n;
286 return i;
288 #endif
290 static int
291 mlonglt(const void *a, const void *b)
293 struct msort const *xa = a, *xb = b;
294 int i;
296 i = (int)(xa->ms_u.ms_long - xb->ms_u.ms_long);
297 if (i == 0)
298 i = xa->ms_n - xb->ms_n;
299 return i;
302 static int
303 mcharlt(const void *a, const void *b)
305 struct msort const *xa = a, *xb = b;
306 int i;
308 i = strcoll(xa->ms_u.ms_char, xb->ms_u.ms_char);
309 if (i == 0)
310 i = xa->ms_n - xb->ms_n;
311 return i;
314 static void
315 lookup(struct message *m, struct mitem *mi, int mprime)
317 struct name *np;
318 struct mitem *ip;
319 char *cp;
320 long dist;
322 if (m->m_flag & MHIDDEN)
323 return;
324 dist = 1;
325 if ((cp = hfield1("in-reply-to", m)) != NULL) {
326 if ((np = extract(cp, GREF)) != NULL)
327 do {
328 if ((ip = mlook(np->n_name, mi, NULL, mprime))
329 != NULL && ip != NOT_AN_ID) {
330 adopt(ip->mi_data, m, 1);
331 return;
333 } while ((np = np->n_flink) != NULL);
335 if ((cp = hfield1("references", m)) != NULL) {
336 if ((np = extract(cp, GREF)) != NULL) {
337 while (np->n_flink != NULL)
338 np = np->n_flink;
339 do {
340 if ((ip = mlook(np->n_name, mi, NULL, mprime))
341 != NULL) {
342 if (ip == NOT_AN_ID)
343 continue; /* skip dist++ */
344 adopt(ip->mi_data, m, dist);
345 return;
347 dist++;
348 } while ((np = np->n_blink) != NULL);
353 static void
354 makethreads(struct message *m, long cnt, int nmail)
356 struct mitem *mt;
357 char *cp;
358 long i, mprime;
360 if (cnt == 0)
361 return;
362 mprime = nextprime(cnt);
363 mt = scalloc(mprime, sizeof *mt);
365 srelax_hold();
366 for (i = 0; i < cnt; i++) {
367 if ((m[i].m_flag&MHIDDEN) == 0) {
368 mlook(NULL, mt, &m[i], mprime);
369 if (m[i].m_date == 0) {
370 if ((cp = hfield1("date", &m[i])) != NULL)
371 m[i].m_date = rfctime(cp);
374 m[i].m_child = m[i].m_younger = m[i].m_elder =
375 m[i].m_parent = NULL;
376 m[i].m_level = 0;
377 if (!nmail && !(inhook&2))
378 m[i].m_collapsed = 0;
379 srelax();
382 * Most folders contain the eldest messages first. Traversing
383 * them in descending order makes it more likely that younger
384 * brothers are found first, so elder ones can be prepended to
385 * the brother list, which is faster. The worst case is still
386 * in O(n^2) and occurs when all but one messages in a folder
387 * are replies to the one message, and are sorted such that
388 * youngest messages occur first.
390 for (i = cnt-1; i >= 0; i--) {
391 lookup(&m[i], mt, mprime);
392 srelax();
394 srelax_rele();
396 threadroot = interlink(m, cnt, nmail);
397 finalize(threadroot);
398 free(mt);
399 mb.mb_threaded = 1;
402 FL int
403 thread(void *vp)
405 if (mb.mb_threaded != 1 || vp == NULL || vp == (void *)-1) {
406 #ifdef HAVE_IMAP
407 if (mb.mb_type == MB_IMAP)
408 imap_getheaders(1, msgCount);
409 #endif
410 makethreads(message, msgCount, vp == (void *)-1);
411 if (mb.mb_sorted != NULL)
412 free(mb.mb_sorted);
413 mb.mb_sorted = sstrdup("thread");
415 if (vp && vp != (void *)-1 && !inhook && ok_blook(header))
416 return headers(vp);
417 return 0;
420 FL int
421 unthread(void *vp)
423 struct message *m;
425 mb.mb_threaded = 0;
426 free(mb.mb_sorted);
427 mb.mb_sorted = NULL;
428 for (m = &message[0]; m < &message[msgCount]; m++)
429 m->m_collapsed = 0;
430 if (vp && !inhook && ok_blook(header))
431 return headers(vp);
432 return 0;
435 FL struct message *
436 next_in_thread(struct message *mp)
438 if (mp->m_child)
439 return mp->m_child;
440 if (mp->m_younger)
441 return mp->m_younger;
442 while (mp->m_parent) {
443 if (mp->m_parent->m_younger)
444 return mp->m_parent->m_younger;
445 mp = mp->m_parent;
447 return NULL;
450 FL struct message *
451 prev_in_thread(struct message *mp)
453 if (mp->m_elder) {
454 mp = mp->m_elder;
455 while (mp->m_child) {
456 mp = mp->m_child;
457 while (mp->m_younger)
458 mp = mp->m_younger;
460 return mp;
462 return mp->m_parent;
465 FL struct message *
466 this_in_thread(struct message *mp, long n)
468 struct message *mq;
470 if (n == -1) { /* find end of thread */
471 while (mp) {
472 if (mp->m_younger) {
473 mp = mp->m_younger;
474 continue;
476 mq = next_in_thread(mp);
477 if (mq == NULL || mq->m_threadpos < mp->m_threadpos)
478 return mp;
479 mp = mq;
481 return NULL;
483 while (mp && mp->m_threadpos < n) {
484 if (mp->m_younger && mp->m_younger->m_threadpos <= n) {
485 mp = mp->m_younger;
486 continue;
488 mp = next_in_thread(mp);
490 return mp && mp->m_threadpos == n ? mp : NULL;
494 * Sorted mode is internally just a variant of threaded mode with all
495 * m_parent and m_child links being NULL.
497 FL int
498 sort(void *vp)
500 enum method {
501 SORT_SUBJECT,
502 SORT_DATE,
503 SORT_STATUS,
504 SORT_SIZE,
505 SORT_FROM,
506 SORT_TO,
507 #ifdef HAVE_SPAM
508 SORT_SPAM,
509 #endif
510 SORT_THREAD
511 } method;
512 struct {
513 const char *me_name;
514 enum method me_method;
515 int (*me_func)(const void *, const void *);
516 } methnames[] = {
517 { "date", SORT_DATE, mlonglt },
518 { "from", SORT_FROM, mcharlt },
519 { "to", SORT_TO, mcharlt },
520 { "subject", SORT_SUBJECT, mcharlt },
521 { "size", SORT_SIZE, mlonglt },
522 #ifdef HAVE_SPAM
523 { "spam", SORT_SPAM, muilt },
524 #endif
525 { "status", SORT_STATUS, mlonglt },
526 { "thread", SORT_THREAD, NULL },
527 { NULL, -1, NULL }
529 char **args = (char **)vp, *cp, *_args[2];
530 int (*func)(const void *, const void *);
531 struct msort *ms;
532 struct str in, out;
533 int i, n, msgvec[2];
534 bool_t showname = ok_blook(showname);
535 struct message *mp;
537 msgvec[0] = dot - &message[0] + 1;
538 msgvec[1] = 0;
539 if (vp == NULL || vp == (void *)-1) {
540 _args[0] = savestr(mb.mb_sorted);
541 _args[1] = NULL;
542 args = _args;
543 } else if (args[0] == NULL) {
544 printf("Current sorting criterion is: %s\n",
545 mb.mb_sorted ? mb.mb_sorted : "unsorted");
546 return 0;
548 for (i = 0; methnames[i].me_name; i++)
549 if (*args[0] && is_prefix(args[0], methnames[i].me_name))
550 break;
551 if (methnames[i].me_name == NULL) {
552 fprintf(stderr, "Unknown sorting method \"%s\"\n", args[0]);
553 return 1;
555 method = methnames[i].me_method;
556 func = methnames[i].me_func;
557 free(mb.mb_sorted);
558 mb.mb_sorted = sstrdup(args[0]);
559 if (method == SORT_THREAD)
560 return thread(vp && vp != (void *)-1 ? msgvec : vp);
561 ms = ac_alloc(sizeof *ms * msgCount);
562 switch (method) {
563 case SORT_SUBJECT:
564 case SORT_DATE:
565 case SORT_FROM:
566 case SORT_TO:
567 #ifdef HAVE_IMAP
568 if (mb.mb_type == MB_IMAP)
569 imap_getheaders(1, msgCount);
570 #endif
571 break;
572 default:
573 break;
576 srelax_hold();
577 for (n = 0, i = 0; i < msgCount; i++) {
578 mp = &message[i];
579 if ((mp->m_flag&MHIDDEN) == 0) {
580 switch (method) {
581 case SORT_DATE:
582 if (mp->m_date == 0 &&
583 (cp = hfield1("date", mp)) != 0)
584 mp->m_date = rfctime(cp);
585 ms[n].ms_u.ms_long = mp->m_date;
586 break;
587 case SORT_STATUS:
588 if (mp->m_flag & MDELETED)
589 ms[n].ms_u.ms_long = 1;
590 else if ((mp->m_flag&(MNEW|MREAD)) == MNEW)
591 ms[n].ms_u.ms_long = 90;
592 else if (mp->m_flag & MFLAGGED)
593 ms[n].ms_u.ms_long = 85;
594 else if ((mp->m_flag&(MNEW|MBOX)) == MBOX)
595 ms[n].ms_u.ms_long = 70;
596 else if (mp->m_flag & MNEW)
597 ms[n].ms_u.ms_long = 80;
598 else if (mp->m_flag & MREAD)
599 ms[n].ms_u.ms_long = 40;
600 else
601 ms[n].ms_u.ms_long = 60;
602 break;
603 case SORT_SIZE:
604 ms[n].ms_u.ms_long = mp->m_xsize;
605 break;
606 #ifdef HAVE_SPAM
607 case SORT_SPAM:
608 ms[n].ms_u.ms_ui = mp->m_spamscore;
609 break;
610 #endif
611 case SORT_FROM:
612 case SORT_TO:
613 if ((cp = hfield1(method == SORT_FROM ?
614 "from" : "to", mp)) != NULL) {
615 ms[n].ms_u.ms_char = showname ?
616 realname(cp) : skin(cp);
617 makelow(ms[n].ms_u.ms_char);
618 } else
619 ms[n].ms_u.ms_char = UNCONST("");
620 break;
621 default:
622 case SORT_SUBJECT:
623 if ((cp = hfield1("subject", mp)) != NULL) {
624 in.s = cp;
625 in.l = strlen(in.s);
626 mime_fromhdr(&in, &out, TD_ICONV);
627 ms[n].ms_u.ms_char =
628 savestr(skipre(out.s));
629 free(out.s);
630 makelow(ms[n].ms_u.ms_char);
631 } else
632 ms[n].ms_u.ms_char = UNCONST("");
633 break;
635 ms[n++].ms_n = i;
637 mp->m_child = mp->m_younger = mp->m_elder = mp->m_parent = NULL;
638 mp->m_level = 0;
639 mp->m_collapsed = 0;
640 srelax();
642 srelax_rele();
644 if (n > 0) {
645 qsort(ms, n, sizeof *ms, func);
646 threadroot = &message[ms[0].ms_n];
647 for (i = 1; i < n; i++) {
648 message[ms[i-1].ms_n].m_younger = &message[ms[i].ms_n];
649 message[ms[i].ms_n].m_elder = &message[ms[i-1].ms_n];
651 } else
652 threadroot = &message[0];
653 finalize(threadroot);
654 mb.mb_threaded = 2;
655 ac_free(ms);
656 return ((vp && vp != (void *)-1 && !inhook && ok_blook(header))
657 ? headers(msgvec) : 0);
660 static char const *
661 skipre(char const *cp)
663 if (lowerconv(cp[0]) == 'r' && lowerconv(cp[1]) == 'e' &&
664 cp[2] == ':' && spacechar(cp[3])) {
665 cp = &cp[4];
666 while (spacechar(*cp))
667 cp++;
669 return cp;
672 FL int
673 ccollapse(void *v)
675 return colpt(v, 1);
678 FL int
679 cuncollapse(void *v)
681 return colpt(v, 0);
684 static int
685 colpt(int *msgvec, int cl)
687 int *ip;
689 if (mb.mb_threaded != 1) {
690 puts("Not in threaded mode.");
691 return 1;
693 for (ip = msgvec; *ip != 0; ip++)
694 colps(&message[*ip-1], cl);
695 return 0;
698 static void
699 colps(struct message *b, int cl)
701 struct message *m;
702 int cc = 0, uc = 0;
704 if (cl && (b->m_collapsed > 0 || (b->m_flag & (MNEW|MREAD)) == MNEW))
705 return;
706 if (b->m_child) {
707 m = b->m_child;
708 colpm(m, cl, &cc, &uc);
709 for (m = m->m_younger; m; m = m->m_younger)
710 colpm(m, cl, &cc, &uc);
712 if (cl) {
713 b->m_collapsed = -cc;
714 for (m = b->m_parent; m; m = m->m_parent)
715 if (m->m_collapsed <= -uc ) {
716 m->m_collapsed += uc;
717 break;
719 } else {
720 if (b->m_collapsed > 0) {
721 b->m_collapsed = 0;
722 uc++;
724 for (m = b; m; m = m->m_parent)
725 if (m->m_collapsed <= -uc) {
726 m->m_collapsed += uc;
727 break;
732 static void
733 colpm(struct message *m, int cl, int *cc, int *uc)
735 if (cl) {
736 if (m->m_collapsed > 0)
737 (*uc)++;
738 if ((m->m_flag & (MNEW|MREAD)) != MNEW || m->m_collapsed < 0)
739 m->m_collapsed = 1;
740 if (m->m_collapsed > 0)
741 (*cc)++;
742 } else {
743 if (m->m_collapsed > 0) {
744 m->m_collapsed = 0;
745 (*uc)++;
748 if (m->m_child) {
749 m = m->m_child;
750 colpm(m, cl, cc, uc);
751 for (m = m->m_younger; m; m = m->m_younger)
752 colpm(m, cl, cc, uc);
756 FL void
757 uncollapse1(struct message *m, int always)
759 if (mb.mb_threaded == 1 && (always || m->m_collapsed > 0))
760 colps(m, 0);