author | zautrix <zautrix> | 2004-07-03 16:33:12 (UTC) |
---|---|---|
committer | zautrix <zautrix> | 2004-07-03 16:33:12 (UTC) |
commit | e3b89230f065c48c84b48c88edb6eb088374c487 (patch) (unidiff) | |
tree | 162ea2ef909a6f82ccfcedf45d80d6c821174912 /kmicromail/libetpan/generic/mailthread.c | |
parent | 2dd6ac0b2d24c91d35ce674a6c26351352df2b15 (diff) | |
download | kdepimpi-e3b89230f065c48c84b48c88edb6eb088374c487.zip kdepimpi-e3b89230f065c48c84b48c88edb6eb088374c487.tar.gz kdepimpi-e3b89230f065c48c84b48c88edb6eb088374c487.tar.bz2 |
Initial revision
Diffstat (limited to 'kmicromail/libetpan/generic/mailthread.c') (more/less context) (ignore whitespace changes)
-rw-r--r-- | kmicromail/libetpan/generic/mailthread.c | 1631 |
1 files changed, 1631 insertions, 0 deletions
diff --git a/kmicromail/libetpan/generic/mailthread.c b/kmicromail/libetpan/generic/mailthread.c new file mode 100644 index 0000000..1dca70d --- a/dev/null +++ b/kmicromail/libetpan/generic/mailthread.c | |||
@@ -0,0 +1,1631 @@ | |||
1 | /* | ||
2 | * libEtPan! -- a mail stuff library | ||
3 | * | ||
4 | * Copyright (C) 2001, 2002 - DINH Viet Hoa | ||
5 | * All rights reserved. | ||
6 | * | ||
7 | * Redistribution and use in source and binary forms, with or without | ||
8 | * modification, are permitted provided that the following conditions | ||
9 | * are met: | ||
10 | * 1. Redistributions of source code must retain the above copyright | ||
11 | * notice, this list of conditions and the following disclaimer. | ||
12 | * 2. Redistributions in binary form must reproduce the above copyright | ||
13 | * notice, this list of conditions and the following disclaimer in the | ||
14 | * documentation and/or other materials provided with the distribution. | ||
15 | * 3. Neither the name of the libEtPan! project nor the names of its | ||
16 | * contributors may be used to endorse or promote products derived | ||
17 | * from this software without specific prior written permission. | ||
18 | * | ||
19 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | ||
20 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||
21 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
22 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | ||
23 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | ||
24 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | ||
25 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | ||
26 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | ||
27 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | ||
28 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | ||
29 | * SUCH DAMAGE. | ||
30 | */ | ||
31 | |||
32 | /* | ||
33 | * $Id$ | ||
34 | */ | ||
35 | |||
36 | #include "mailthread.h" | ||
37 | #include "mailthread_types.h" | ||
38 | |||
39 | #include <string.h> | ||
40 | #include <time.h> | ||
41 | #include <stdlib.h> | ||
42 | #include <ctype.h> | ||
43 | |||
44 | #include "mail.h" | ||
45 | #include "chash.h" | ||
46 | #include "carray.h" | ||
47 | #include "clist.h" | ||
48 | #include "mailmessage.h" | ||
49 | |||
50 | static inline char * get_msg_id(mailmessage * msg) | ||
51 | { | ||
52 | if (msg->msg_single_fields.fld_message_id != NULL) | ||
53 | return msg->msg_single_fields.fld_message_id->mid_value; | ||
54 | else | ||
55 | return NULL; | ||
56 | } | ||
57 | |||
58 | static inline clist * get_ref(mailmessage * msg) | ||
59 | { | ||
60 | if (msg->msg_single_fields.fld_references != NULL) | ||
61 | return msg->msg_single_fields.fld_references->mid_list; | ||
62 | else | ||
63 | return NULL; | ||
64 | } | ||
65 | |||
66 | static inline clist * get_in_reply_to(mailmessage * msg) | ||
67 | { | ||
68 | if (msg->msg_single_fields.fld_in_reply_to != NULL) | ||
69 | return msg->msg_single_fields.fld_in_reply_to->mid_list; | ||
70 | else | ||
71 | return NULL; | ||
72 | } | ||
73 | |||
74 | static inline int skip_subj_blob(char * subj, size_t * begin, | ||
75 | size_t length) | ||
76 | { | ||
77 | /* subj-blob = "[" *BLOBCHAR "]" *WSP */ | ||
78 | size_t cur_token; | ||
79 | |||
80 | cur_token = * begin; | ||
81 | |||
82 | if (subj[cur_token] != '[') | ||
83 | return FALSE; | ||
84 | |||
85 | cur_token ++; | ||
86 | |||
87 | while (1) { | ||
88 | if (cur_token >= length) | ||
89 | return FALSE; | ||
90 | |||
91 | if (subj[cur_token] == '[') | ||
92 | return FALSE; | ||
93 | |||
94 | if (subj[cur_token] == ']') | ||
95 | break; | ||
96 | |||
97 | cur_token ++; | ||
98 | } | ||
99 | |||
100 | cur_token ++; | ||
101 | |||
102 | while (1) { | ||
103 | if (cur_token >= length) | ||
104 | break; | ||
105 | |||
106 | if (subj[cur_token] != ' ') | ||
107 | break; | ||
108 | |||
109 | cur_token ++; | ||
110 | } | ||
111 | |||
112 | * begin = cur_token; | ||
113 | |||
114 | return TRUE; | ||
115 | } | ||
116 | |||
117 | static inline int skip_subj_refwd(char * subj, size_t * begin, | ||
118 | size_t length) | ||
119 | { | ||
120 | /* subj-refwd = ("re" / ("fw" ["d"])) *WSP [subj-blob] ":" */ | ||
121 | size_t cur_token; | ||
122 | int prefix; | ||
123 | |||
124 | cur_token = * begin; | ||
125 | |||
126 | prefix = FALSE; | ||
127 | if (length >= 3) { | ||
128 | if (strncasecmp(subj + cur_token, "fwd", 3) == 0) { | ||
129 | cur_token += 3; | ||
130 | prefix = TRUE; | ||
131 | } | ||
132 | } | ||
133 | if (!prefix) { | ||
134 | if (length >= 2) { | ||
135 | if (strncasecmp(subj + cur_token, "fw", 2) == 0) { | ||
136 | cur_token += 2; | ||
137 | prefix = TRUE; | ||
138 | } | ||
139 | else if (strncasecmp(subj + cur_token, "re", 2) == 0) { | ||
140 | cur_token += 2; | ||
141 | prefix = TRUE; | ||
142 | } | ||
143 | } | ||
144 | } | ||
145 | |||
146 | if (!prefix) | ||
147 | return FALSE; | ||
148 | |||
149 | while (1) { | ||
150 | if (cur_token >= length) | ||
151 | break; | ||
152 | |||
153 | if (subj[cur_token] != ' ') | ||
154 | break; | ||
155 | |||
156 | cur_token ++; | ||
157 | } | ||
158 | |||
159 | skip_subj_blob(subj, &cur_token, length); | ||
160 | |||
161 | if (subj[cur_token] != ':') | ||
162 | return FALSE; | ||
163 | |||
164 | cur_token ++; | ||
165 | |||
166 | * begin = cur_token; | ||
167 | |||
168 | return TRUE; | ||
169 | } | ||
170 | |||
171 | static inline int skip_subj_leader(struct mailmessage_tree * tree, | ||
172 | char * subj, size_t * begin, | ||
173 | size_t length) | ||
174 | { | ||
175 | size_t cur_token; | ||
176 | |||
177 | cur_token = * begin; | ||
178 | |||
179 | /* subj-leader = (*subj-blob subj-refwd) / WSP */ | ||
180 | |||
181 | if (subj[cur_token] == ' ') { | ||
182 | cur_token ++; | ||
183 | } | ||
184 | else { | ||
185 | while (cur_token < length) { | ||
186 | if (!skip_subj_blob(subj, &cur_token, length)) | ||
187 | break; | ||
188 | } | ||
189 | if (!skip_subj_refwd(subj, &cur_token, length)) | ||
190 | return FALSE; | ||
191 | tree->node_is_reply = TRUE; | ||
192 | } | ||
193 | |||
194 | * begin = cur_token; | ||
195 | |||
196 | return TRUE; | ||
197 | } | ||
198 | |||
199 | |||
200 | static char * extract_subject(char * default_from, | ||
201 | struct mailmessage_tree * tree, | ||
202 | char * str) | ||
203 | { | ||
204 | char * subj; | ||
205 | char * cur; | ||
206 | char * write_pos; | ||
207 | size_t len; | ||
208 | size_t begin; | ||
209 | |||
210 | char * decoded; | ||
211 | size_t cur_token; | ||
212 | |||
213 | int do_repeat_5; | ||
214 | int do_repeat_6; | ||
215 | int r; | ||
216 | |||
217 | /* | ||
218 | (1) Convert any RFC 2047 encoded-words in the subject to | ||
219 | UTF-8. | ||
220 | */ | ||
221 | |||
222 | decoded = NULL; | ||
223 | |||
224 | cur_token = 0; | ||
225 | r = mailmime_encoded_phrase_parse(default_from, str, strlen(str), | ||
226 | &cur_token, "utf-8", | ||
227 | &decoded); | ||
228 | |||
229 | if (r == MAILIMF_NO_ERROR) { | ||
230 | subj = decoded; | ||
231 | } | ||
232 | else | ||
233 | subj = strdup(str); | ||
234 | |||
235 | len = strlen(subj); | ||
236 | |||
237 | /* | ||
238 | Convert all tabs and continuations to space. | ||
239 | Convert all multiple spaces to a single space. | ||
240 | */ | ||
241 | |||
242 | cur = subj; | ||
243 | write_pos = subj; | ||
244 | while (* cur != '\0') { | ||
245 | int cont; | ||
246 | |||
247 | switch (* cur) { | ||
248 | case '\t': | ||
249 | case '\r': | ||
250 | case '\n': | ||
251 | cont = TRUE; | ||
252 | |||
253 | cur ++; | ||
254 | while (* cur && cont) { | ||
255 | switch (* cur) { | ||
256 | case '\t': | ||
257 | case '\r': | ||
258 | case '\n': | ||
259 | cont = TRUE; | ||
260 | break; | ||
261 | default: | ||
262 | cont = FALSE; | ||
263 | break; | ||
264 | } | ||
265 | cur ++; | ||
266 | } | ||
267 | |||
268 | * write_pos = ' '; | ||
269 | write_pos ++; | ||
270 | |||
271 | break; | ||
272 | |||
273 | default: | ||
274 | * write_pos = * cur; | ||
275 | write_pos ++; | ||
276 | |||
277 | cur ++; | ||
278 | |||
279 | break; | ||
280 | } | ||
281 | } | ||
282 | * write_pos = '\0'; | ||
283 | |||
284 | begin = 0; | ||
285 | |||
286 | do { | ||
287 | do_repeat_6 = FALSE; | ||
288 | |||
289 | /* | ||
290 | (2) Remove all trailing text of the subject that matches | ||
291 | the subj-trailer ABNF, repeat until no more matches are | ||
292 | possible. | ||
293 | */ | ||
294 | |||
295 | while (len > 0) { | ||
296 | int chg; | ||
297 | |||
298 | chg = FALSE; | ||
299 | |||
300 | /* subj-trailer = "(fwd)" / WSP */ | ||
301 | if (subj[len - 1] == ' ') { | ||
302 | subj[len - 1] = '\0'; | ||
303 | len --; | ||
304 | } | ||
305 | else { | ||
306 | if (len < 5) | ||
307 | break; | ||
308 | |||
309 | if (strncasecmp(subj + len - 5, "(fwd)", 5) != 0) | ||
310 | break; | ||
311 | |||
312 | subj[len - 5] = '\0'; | ||
313 | len -= 5; | ||
314 | tree->node_is_reply = TRUE; | ||
315 | } | ||
316 | } | ||
317 | |||
318 | do { | ||
319 | size_t saved_begin; | ||
320 | |||
321 | do_repeat_5 = FALSE; | ||
322 | |||
323 | /* | ||
324 | (3) Remove all prefix text of the subject that matches the | ||
325 | subj-leader ABNF. | ||
326 | */ | ||
327 | |||
328 | if (skip_subj_leader(tree, subj, &begin, len)) | ||
329 | do_repeat_5 = TRUE; | ||
330 | |||
331 | /* | ||
332 | (4) If there is prefix text of the subject that matches the | ||
333 | subj-blob ABNF, and removing that prefix leaves a non-empty | ||
334 | subj-base, then remove the prefix text. | ||
335 | */ | ||
336 | |||
337 | saved_begin = begin; | ||
338 | if (skip_subj_blob(subj, &begin, len)) { | ||
339 | if (begin == len) { | ||
340 | /* this will leave a empty subject base */ | ||
341 | begin = saved_begin; | ||
342 | } | ||
343 | else | ||
344 | do_repeat_5 = TRUE; | ||
345 | } | ||
346 | |||
347 | /* | ||
348 | (5) Repeat (3) and (4) until no matches remain. | ||
349 | Note: it is possible to defer step (2) until step (6), | ||
350 | but this requires checking for subj-trailer in step (4). | ||
351 | */ | ||
352 | |||
353 | } | ||
354 | while (do_repeat_5); | ||
355 | |||
356 | /* | ||
357 | (6) If the resulting text begins with the subj-fwd-hdr ABNF | ||
358 | and ends with the subj-fwd-trl ABNF, remove the | ||
359 | subj-fwd-hdr and subj-fwd-trl and repeat from step (2). | ||
360 | */ | ||
361 | |||
362 | if (len >= 5) { | ||
363 | size_t saved_begin; | ||
364 | |||
365 | saved_begin = begin; | ||
366 | if (strncasecmp(subj + begin, "[fwd:", 5) == 0) { | ||
367 | begin += 5; | ||
368 | |||
369 | if (subj[len - 1] != ']') | ||
370 | saved_begin = begin; | ||
371 | else { | ||
372 | tree->node_is_reply = TRUE; | ||
373 | |||
374 | subj[len - 1] = '\0'; | ||
375 | len --; | ||
376 | do_repeat_6 = TRUE; | ||
377 | } | ||
378 | } | ||
379 | } | ||
380 | |||
381 | } | ||
382 | while (do_repeat_6); | ||
383 | |||
384 | /* | ||
385 | (7) The resulting text is the "base subject" used in | ||
386 | threading. | ||
387 | */ | ||
388 | |||
389 | /* convert to upper case */ | ||
390 | |||
391 | cur = subj + begin; | ||
392 | write_pos = subj; | ||
393 | |||
394 | while (* cur != '\0') { | ||
395 | * write_pos = (char) toupper((unsigned char) * cur); | ||
396 | cur ++; | ||
397 | write_pos ++; | ||
398 | } | ||
399 | * write_pos = '\0'; | ||
400 | |||
401 | return subj; | ||
402 | } | ||
403 | |||
404 | static int get_extracted_subject(char * default_from, | ||
405 | struct mailmessage_tree * tree, | ||
406 | char ** result) | ||
407 | { | ||
408 | if (tree->node_msg->msg_single_fields.fld_subject != NULL) { | ||
409 | char * subj; | ||
410 | |||
411 | subj = extract_subject(default_from, | ||
412 | tree, tree->node_msg->msg_single_fields.fld_subject->sbj_value); | ||
413 | if (subj == NULL) | ||
414 | return MAIL_ERROR_MEMORY; | ||
415 | |||
416 | * result = subj; | ||
417 | |||
418 | return MAIL_NO_ERROR; | ||
419 | } | ||
420 | |||
421 | return MAIL_ERROR_SUBJECT_NOT_FOUND; | ||
422 | } | ||
423 | |||
424 | static int get_thread_subject(char * default_from, | ||
425 | struct mailmessage_tree * tree, | ||
426 | char ** result) | ||
427 | { | ||
428 | char * thread_subject; | ||
429 | int r; | ||
430 | unsigned int i; | ||
431 | |||
432 | if (tree->node_msg != NULL) { | ||
433 | if (tree->node_msg->msg_fields != NULL) { | ||
434 | r = get_extracted_subject(default_from, tree, &thread_subject); | ||
435 | |||
436 | if (r != MAIL_NO_ERROR) | ||
437 | return r; | ||
438 | |||
439 | * result = thread_subject; | ||
440 | return MAIL_NO_ERROR; | ||
441 | } | ||
442 | } | ||
443 | |||
444 | for(i = 0 ; i < carray_count(tree->node_children) ; i ++) { | ||
445 | struct mailmessage_tree * child; | ||
446 | |||
447 | child = carray_get(tree->node_children, i); | ||
448 | |||
449 | r = get_thread_subject(default_from, child, &thread_subject); | ||
450 | |||
451 | switch (r) { | ||
452 | case MAIL_NO_ERROR: | ||
453 | * result = thread_subject; | ||
454 | return MAIL_NO_ERROR; | ||
455 | |||
456 | case MAIL_ERROR_SUBJECT_NOT_FOUND: | ||
457 | /* do nothing */ | ||
458 | break; | ||
459 | |||
460 | default: | ||
461 | return r; | ||
462 | } | ||
463 | } | ||
464 | |||
465 | return MAIL_ERROR_SUBJECT_NOT_FOUND; | ||
466 | } | ||
467 | |||
468 | |||
469 | |||
470 | #ifndef WRONG | ||
471 | #define WRONG(-1) | ||
472 | #endif /* !defined WRONG */ | ||
473 | |||
474 | static int tmcomp(struct tm * atmp, struct tm * btmp) | ||
475 | { | ||
476 | register intresult; | ||
477 | |||
478 | if ((result = (atmp->tm_year - btmp->tm_year)) == 0 && | ||
479 | (result = (atmp->tm_mon - btmp->tm_mon)) == 0 && | ||
480 | (result = (atmp->tm_mday - btmp->tm_mday)) == 0 && | ||
481 | (result = (atmp->tm_hour - btmp->tm_hour)) == 0 && | ||
482 | (result = (atmp->tm_min - btmp->tm_min)) == 0) | ||
483 | result = atmp->tm_sec - btmp->tm_sec; | ||
484 | return result; | ||
485 | } | ||
486 | |||
487 | static time_t mkgmtime(struct tm * tmp) | ||
488 | { | ||
489 | register int dir; | ||
490 | register int bits; | ||
491 | register int saved_seconds; | ||
492 | time_t t; | ||
493 | struct tm yourtm, *mytm; | ||
494 | |||
495 | yourtm = *tmp; | ||
496 | saved_seconds = yourtm.tm_sec; | ||
497 | yourtm.tm_sec = 0; | ||
498 | /* | ||
499 | ** Calculate the number of magnitude bits in a time_t | ||
500 | ** (this works regardless of whether time_t is | ||
501 | ** signed or unsigned, though lint complains if unsigned). | ||
502 | */ | ||
503 | for (bits = 0, t = 1; t > 0; ++bits, t <<= 1) | ||
504 | ; | ||
505 | /* | ||
506 | ** If time_t is signed, then 0 is the median value, | ||
507 | ** if time_t is unsigned, then 1 << bits is median. | ||
508 | */ | ||
509 | t = (t < 0) ? 0 : ((time_t) 1 << bits); | ||
510 | for ( ; ; ) { | ||
511 | mytm = gmtime(&t); | ||
512 | dir = tmcomp(mytm, &yourtm); | ||
513 | if (dir != 0) { | ||
514 | if (bits-- < 0) | ||
515 | return WRONG; | ||
516 | if (bits < 0) | ||
517 | --t; | ||
518 | else if (dir > 0) | ||
519 | t -= (time_t) 1 << bits; | ||
520 | elset += (time_t) 1 << bits; | ||
521 | continue; | ||
522 | } | ||
523 | break; | ||
524 | } | ||
525 | t += saved_seconds; | ||
526 | return t; | ||
527 | } | ||
528 | |||
529 | static inline time_t get_date(mailmessage * msg) | ||
530 | { | ||
531 | struct tm tmval; | ||
532 | time_t timeval; | ||
533 | struct mailimf_date_time * date_time; | ||
534 | |||
535 | if (msg->msg_single_fields.fld_orig_date == NULL) | ||
536 | return (time_t) -1; | ||
537 | |||
538 | date_time = msg->msg_single_fields.fld_orig_date->dt_date_time; | ||
539 | |||
540 | tmval.tm_sec = date_time->dt_sec; | ||
541 | tmval.tm_min = date_time->dt_min; | ||
542 | tmval.tm_hour = date_time->dt_hour; | ||
543 | tmval.tm_sec = date_time->dt_sec; | ||
544 | tmval.tm_mday = date_time->dt_day; | ||
545 | tmval.tm_mon = date_time->dt_month - 1; | ||
546 | tmval.tm_year = date_time->dt_year - 1900; | ||
547 | |||
548 | timeval = mkgmtime(&tmval); | ||
549 | |||
550 | timeval -= date_time->dt_zone * 36; | ||
551 | |||
552 | return timeval; | ||
553 | } | ||
554 | |||
555 | static inline int is_descendant(struct mailmessage_tree * node, | ||
556 | struct mailmessage_tree * maybe_child) | ||
557 | { | ||
558 | unsigned int i; | ||
559 | |||
560 | for(i = 0 ; i < carray_count(node->node_children) ; i++) { | ||
561 | struct mailmessage_tree * tree; | ||
562 | |||
563 | tree = carray_get(node->node_children, i); | ||
564 | if (tree == maybe_child) | ||
565 | return TRUE; | ||
566 | if (carray_count(tree->node_children) != 0) | ||
567 | if (is_descendant(tree, maybe_child)) | ||
568 | return TRUE; | ||
569 | } | ||
570 | |||
571 | return FALSE; | ||
572 | } | ||
573 | |||
574 | static int delete_dummy(carray * rootlist, carray * sibling_list, | ||
575 | unsigned int cur, unsigned int * pnext) | ||
576 | { | ||
577 | struct mailmessage_tree * env_tree; | ||
578 | int res; | ||
579 | int r; | ||
580 | unsigned int cur_child; | ||
581 | unsigned int next; | ||
582 | |||
583 | env_tree = carray_get(sibling_list, cur); | ||
584 | |||
585 | cur_child = 0; | ||
586 | while (cur_child < carray_count(env_tree->node_children)) { | ||
587 | delete_dummy(rootlist, env_tree->node_children, cur_child, &cur_child); | ||
588 | } | ||
589 | |||
590 | if (env_tree->node_msg == NULL) { | ||
591 | if (carray_count(env_tree->node_children) == 0) { | ||
592 | |||
593 | /* If it is a dummy message with NO children, delete it. */ | ||
594 | mailmessage_tree_free(env_tree); | ||
595 | carray_delete(sibling_list, cur); | ||
596 | next = cur; | ||
597 | } | ||
598 | else { | ||
599 | /* If it is a dummy message with children, delete it, but | ||
600 | promote its children to the current level. */ | ||
601 | |||
602 | /* | ||
603 | Do not promote the children if doing so would make them | ||
604 | children of the root, unless there is only one child. | ||
605 | */ | ||
606 | |||
607 | cur_child = 0; | ||
608 | if ((sibling_list != rootlist) || | ||
609 | (carray_count(env_tree->node_children) == 1)) { | ||
610 | while (cur_child < carray_count(env_tree->node_children)) { | ||
611 | struct mailmessage_tree * child; | ||
612 | |||
613 | child = carray_get(env_tree->node_children, cur_child); | ||
614 | r = carray_add(sibling_list, child, NULL); | ||
615 | if (r < 0) { | ||
616 | res = MAIL_ERROR_MEMORY; | ||
617 | goto err; | ||
618 | } | ||
619 | /* set new parent of the children */ | ||
620 | child->node_parent = env_tree->node_parent; | ||
621 | |||
622 | carray_delete(env_tree->node_children, cur_child); | ||
623 | } | ||
624 | mailmessage_tree_free(env_tree); | ||
625 | carray_delete(sibling_list, cur); | ||
626 | next = cur; | ||
627 | } | ||
628 | else | ||
629 | next = cur + 1; | ||
630 | } | ||
631 | } | ||
632 | else | ||
633 | next = cur + 1; | ||
634 | |||
635 | * pnext = next; | ||
636 | |||
637 | return MAIL_NO_ERROR; | ||
638 | |||
639 | err: | ||
640 | return res; | ||
641 | } | ||
642 | |||
643 | static inline time_t tree_get_date(struct mailmessage_tree * tree) | ||
644 | { | ||
645 | if (tree->node_msg != NULL) { | ||
646 | return tree->node_date; | ||
647 | } | ||
648 | else { | ||
649 | struct mailmessage_tree * subtree; | ||
650 | |||
651 | if (carray_count(tree->node_children) == 0) | ||
652 | return (time_t) -1; | ||
653 | |||
654 | subtree = carray_get(tree->node_children, 0); | ||
655 | |||
656 | return subtree->node_date; | ||
657 | } | ||
658 | } | ||
659 | |||
660 | static inline uint32_t tree_get_index(struct mailmessage_tree * tree) | ||
661 | { | ||
662 | if (tree->node_msg == NULL) | ||
663 | return 0; | ||
664 | |||
665 | return tree->node_msg->msg_index; | ||
666 | } | ||
667 | |||
668 | int mailthread_tree_timecomp(struct mailmessage_tree ** ptree1, | ||
669 | struct mailmessage_tree ** ptree2) | ||
670 | { | ||
671 | time_t date1; | ||
672 | time_t date2; | ||
673 | |||
674 | date1 = tree_get_date(* ptree1); | ||
675 | date2 = tree_get_date(* ptree2); | ||
676 | |||
677 | if ((date1 == (time_t) -1) || (date2 == (time_t) -1)) { | ||
678 | uint32_t index1; | ||
679 | uint32_t index2; | ||
680 | |||
681 | index1 = tree_get_index(* ptree1); | ||
682 | index2 = tree_get_index(* ptree2); | ||
683 | return (int) ((long) index1 - (long) index2); | ||
684 | } | ||
685 | |||
686 | return (int) ((long) date1 - (long) date2); | ||
687 | } | ||
688 | |||
689 | static int tree_subj_time_comp(struct mailmessage_tree ** ptree1, | ||
690 | struct mailmessage_tree ** ptree2) | ||
691 | { | ||
692 | char * subj1; | ||
693 | char * subj2; | ||
694 | time_t date1; | ||
695 | time_t date2; | ||
696 | int r; | ||
697 | |||
698 | subj1 = (* ptree1)->node_base_subject; | ||
699 | subj2 = (* ptree2)->node_base_subject; | ||
700 | |||
701 | if ((subj1 != NULL) && (subj2 != NULL)) | ||
702 | r = strcmp(subj1, subj2); | ||
703 | else { | ||
704 | if ((subj1 == NULL) && (subj2 == NULL)) | ||
705 | r = 0; | ||
706 | else if (subj1 == NULL) | ||
707 | r = -1; | ||
708 | else /* subj2 == NULL */ | ||
709 | r = 1; | ||
710 | } | ||
711 | |||
712 | if (r != 0) | ||
713 | return r; | ||
714 | |||
715 | date1 = (* ptree1)->node_date; | ||
716 | date2 = (* ptree2)->node_date; | ||
717 | |||
718 | if ((date1 == (time_t) -1) || (date2 == (time_t) -1)) | ||
719 | return ((int32_t) (* ptree1)->node_msg->msg_index) - | ||
720 | ((int32_t) (* ptree2)->node_msg->msg_index); | ||
721 | |||
722 | return (int) ((long) date1 - (long) date2); | ||
723 | } | ||
724 | |||
725 | |||
726 | |||
727 | int mail_thread_sort(struct mailmessage_tree * tree, | ||
728 | int (* comp_func)(struct mailmessage_tree **, | ||
729 | struct mailmessage_tree **), | ||
730 | int sort_sub) | ||
731 | { | ||
732 | unsigned int cur; | ||
733 | int r; | ||
734 | int res; | ||
735 | |||
736 | for(cur = 0 ; cur < carray_count(tree->node_children) ; cur ++) { | ||
737 | struct mailmessage_tree * subtree; | ||
738 | |||
739 | subtree = carray_get(tree->node_children, cur); | ||
740 | |||
741 | if (sort_sub) { | ||
742 | r = mail_thread_sort(subtree, comp_func, sort_sub); | ||
743 | if (r != MAIL_NO_ERROR) { | ||
744 | res = r; | ||
745 | goto err; | ||
746 | } | ||
747 | } | ||
748 | } | ||
749 | |||
750 | qsort(carray_data(tree->node_children), carray_count(tree->node_children), | ||
751 | sizeof(struct mailmessage_tree *), | ||
752 | (int (*)(const void *, const void *)) comp_func); | ||
753 | |||
754 | return MAIL_NO_ERROR; | ||
755 | |||
756 | err: | ||
757 | return res; | ||
758 | } | ||
759 | |||
760 | |||
761 | static int | ||
762 | mail_build_thread_references(char * default_from, | ||
763 | struct mailmessage_list * env_list, | ||
764 | struct mailmessage_tree ** result, | ||
765 | int use_subject, | ||
766 | int (* comp_func)(struct mailmessage_tree **, | ||
767 | struct mailmessage_tree **)) | ||
768 | { | ||
769 | int r; | ||
770 | int res; | ||
771 | chash * msg_id_hash; | ||
772 | unsigned int cur; | ||
773 | struct mailmessage_tree * root; | ||
774 | carray * rootlist; | ||
775 | carray * msg_list; | ||
776 | unsigned int i; | ||
777 | chash * subject_hash; | ||
778 | |||
779 | msg_id_hash = chash_new(128, CHASH_COPYNONE); | ||
780 | if (msg_id_hash == NULL) { | ||
781 | res = MAIL_ERROR_MEMORY; | ||
782 | goto err; | ||
783 | } | ||
784 | |||
785 | root = mailmessage_tree_new(NULL, (time_t) -1, NULL); | ||
786 | if (root == NULL) { | ||
787 | res = MAIL_ERROR_MEMORY; | ||
788 | goto free_hash; | ||
789 | } | ||
790 | rootlist = root->node_children; | ||
791 | |||
792 | msg_list = carray_new(128); | ||
793 | if (msg_list == NULL) { | ||
794 | res = MAIL_ERROR_MEMORY; | ||
795 | goto free_root; | ||
796 | } | ||
797 | |||
798 | /* collect message-ID */ | ||
799 | for(i = 0 ; i < carray_count(env_list->msg_tab) ; i ++) { | ||
800 | mailmessage * msg; | ||
801 | char * msgid; | ||
802 | struct mailmessage_tree * env_tree; | ||
803 | chashdatum hashkey; | ||
804 | chashdatum hashdata; | ||
805 | chashdatum hashold; | ||
806 | time_t date; | ||
807 | |||
808 | msg = carray_get(env_list->msg_tab, i); | ||
809 | |||
810 | if (msg == NULL) | ||
811 | continue; | ||
812 | |||
813 | if (msg->msg_fields != NULL) { | ||
814 | msgid = get_msg_id(msg); | ||
815 | |||
816 | if (msgid == NULL) { | ||
817 | msgid = mailimf_get_message_id(); | ||
818 | } | ||
819 | else { | ||
820 | hashkey.data = msgid; | ||
821 | hashkey.len = strlen(msgid); | ||
822 | |||
823 | if (chash_get(msg_id_hash, &hashkey, &hashdata) == 0) | ||
824 | msgid = mailimf_get_message_id(); | ||
825 | else | ||
826 | msgid = strdup(msgid); | ||
827 | } | ||
828 | |||
829 | if (msgid == NULL) { | ||
830 | res = MAIL_ERROR_MEMORY; | ||
831 | goto free_list; | ||
832 | } | ||
833 | |||
834 | date = get_date(msg); | ||
835 | |||
836 | env_tree = mailmessage_tree_new(msgid, date, msg); | ||
837 | if (env_tree == NULL) { | ||
838 | res = MAIL_ERROR_MEMORY; | ||
839 | goto free_list; | ||
840 | } | ||
841 | |||
842 | r = carray_add(msg_list, env_tree, NULL); | ||
843 | if (r < 0) { | ||
844 | mailmessage_tree_free(env_tree); | ||
845 | res = MAIL_ERROR_MEMORY; | ||
846 | goto free_list; | ||
847 | } | ||
848 | |||
849 | hashkey.data = msgid; | ||
850 | hashkey.len = strlen(msgid); | ||
851 | |||
852 | hashdata.data = env_tree; | ||
853 | hashdata.len = 0; | ||
854 | |||
855 | r = chash_set(msg_id_hash, &hashkey, &hashdata, &hashold); | ||
856 | if (r < 0) { | ||
857 | res = MAIL_ERROR_MEMORY; | ||
858 | goto free_list; | ||
859 | } | ||
860 | } | ||
861 | } | ||
862 | |||
863 | /* (1) for all messages */ | ||
864 | |||
865 | for(cur = 0 ; cur < carray_count(msg_list) ; cur ++) { | ||
866 | struct mailmessage_tree * env_tree; | ||
867 | mailmessage * msg; | ||
868 | clist * ref; | ||
869 | |||
870 | env_tree = carray_get(msg_list, cur); | ||
871 | |||
872 | msg = env_tree->node_msg; | ||
873 | |||
874 | ref = NULL; | ||
875 | if (msg != NULL) { | ||
876 | ref = get_ref(msg); | ||
877 | if (ref == NULL) | ||
878 | ref = get_in_reply_to(msg); | ||
879 | } | ||
880 | |||
881 | /* (A) Using the Message IDs in the message's references, link | ||
882 | the corresponding messages (those whose Message-ID header | ||
883 | line contains the given reference Message ID) together as | ||
884 | parent/child. | ||
885 | */ | ||
886 | |||
887 | if (ref != NULL) { | ||
888 | /* try to start a tree */ | ||
889 | |||
890 | clistiter * cur_ref; | ||
891 | chashdatum hashkey; | ||
892 | chashdatum hashdata; | ||
893 | chashdatum hashold; | ||
894 | struct mailmessage_tree * env_cur_tree; | ||
895 | struct mailmessage_tree * last_env_cur_tree; | ||
896 | |||
897 | env_cur_tree = NULL; | ||
898 | for(cur_ref = clist_begin(ref) ; cur_ref != NULL ; | ||
899 | cur_ref = clist_next(cur_ref)) { | ||
900 | char * msgid; | ||
901 | |||
902 | last_env_cur_tree = env_cur_tree; | ||
903 | |||
904 | msgid = clist_content(cur_ref); | ||
905 | |||
906 | hashkey.data = msgid; | ||
907 | hashkey.len = strlen(msgid); | ||
908 | |||
909 | r = chash_get(msg_id_hash, &hashkey, &hashdata); | ||
910 | if (r < 0) { | ||
911 | /* not found, create a dummy message */ | ||
912 | msgid = strdup(msgid); | ||
913 | if (msgid == NULL) { | ||
914 | res = MAIL_ERROR_MEMORY; | ||
915 | goto free_list; | ||
916 | } | ||
917 | |||
918 | env_cur_tree = mailmessage_tree_new(msgid, (time_t) -1, NULL); | ||
919 | if (env_cur_tree == NULL) { | ||
920 | free(msgid); | ||
921 | res = MAIL_ERROR_MEMORY; | ||
922 | goto free_list; | ||
923 | } | ||
924 | |||
925 | r = carray_add(msg_list, env_cur_tree, NULL); | ||
926 | if (r < 0) { | ||
927 | mailmessage_tree_free(env_cur_tree); | ||
928 | res = MAIL_ERROR_MEMORY; | ||
929 | goto free_list; | ||
930 | } | ||
931 | |||
932 | hashkey.data = msgid; | ||
933 | hashkey.len = strlen(msgid); | ||
934 | |||
935 | hashdata.data = env_cur_tree; | ||
936 | hashdata.len = 0; | ||
937 | |||
938 | r = chash_set(msg_id_hash, &hashkey, &hashdata, &hashold); | ||
939 | if (r < 0) { | ||
940 | res = MAIL_ERROR_MEMORY; | ||
941 | goto free_list; | ||
942 | } | ||
943 | } | ||
944 | else { | ||
945 | env_cur_tree = hashdata.data; | ||
946 | } | ||
947 | |||
948 | if (last_env_cur_tree != NULL) { | ||
949 | if (env_cur_tree->node_parent == NULL) { | ||
950 | /* make it one child */ | ||
951 | if (env_cur_tree != last_env_cur_tree) { | ||
952 | if (!is_descendant(env_cur_tree, last_env_cur_tree)) { | ||
953 | /* set parent */ | ||
954 | env_cur_tree->node_parent = last_env_cur_tree; | ||
955 | r = carray_add(last_env_cur_tree->node_children, | ||
956 | env_cur_tree, NULL); | ||
957 | if (r < 0) { | ||
958 | res = MAIL_ERROR_MEMORY; | ||
959 | goto free_list; | ||
960 | } | ||
961 | } | ||
962 | } | ||
963 | } | ||
964 | } | ||
965 | } | ||
966 | |||
967 | /* (B) Create a parent/child link between the last reference | ||
968 | (or NIL if there are no references) and the current message. | ||
969 | If the current message already has a parent, it is probably | ||
970 | the result of a truncated References header line, so break | ||
971 | the current parent/child link before creating the new | ||
972 | correct one. | ||
973 | */ | ||
974 | |||
975 | last_env_cur_tree = env_cur_tree; | ||
976 | |||
977 | if (last_env_cur_tree != NULL) { | ||
978 | if (env_tree->node_parent == NULL) { | ||
979 | if (last_env_cur_tree != env_tree) { | ||
980 | if (!is_descendant(env_tree, last_env_cur_tree)) { | ||
981 | /* set parent */ | ||
982 | env_tree->node_parent = last_env_cur_tree; | ||
983 | r = carray_add(last_env_cur_tree->node_children, env_tree, NULL); | ||
984 | if (r < 0) { | ||
985 | res = MAIL_ERROR_MEMORY; | ||
986 | goto free_list; | ||
987 | } | ||
988 | } | ||
989 | } | ||
990 | } | ||
991 | } | ||
992 | } | ||
993 | } | ||
994 | |||
995 | chash_free(msg_id_hash); | ||
996 | msg_id_hash = NULL; | ||
997 | |||
998 | /* (2) Gather together all of the messages that have no parents | ||
999 | and make them all children (siblings of one another) of a dummy | ||
1000 | parent (the "root"). | ||
1001 | */ | ||
1002 | |||
1003 | for(cur = 0 ; cur < carray_count(msg_list) ; cur ++) { | ||
1004 | struct mailmessage_tree * env_tree; | ||
1005 | |||
1006 | env_tree = carray_get(msg_list, cur); | ||
1007 | if (env_tree->node_parent == NULL) { | ||
1008 | r = carray_add(rootlist, env_tree, NULL); | ||
1009 | if (r < 0) { | ||
1010 | res = MAIL_ERROR_MEMORY; | ||
1011 | goto free_list; | ||
1012 | } | ||
1013 | /* set parent */ | ||
1014 | env_tree->node_parent = root; | ||
1015 | } | ||
1016 | } | ||
1017 | |||
1018 | carray_free(msg_list); | ||
1019 | msg_list = NULL; | ||
1020 | |||
1021 | /* (3) Prune dummy messages from the thread tree. | ||
1022 | */ | ||
1023 | |||
1024 | cur = 0; | ||
1025 | while (cur < carray_count(rootlist)) { | ||
1026 | r = delete_dummy(rootlist, rootlist, cur, &cur); | ||
1027 | if (r != MAIL_NO_ERROR) { | ||
1028 | res = r; | ||
1029 | goto free_list; | ||
1030 | } | ||
1031 | } | ||
1032 | |||
1033 | /* (4) Sort the messages under the root (top-level siblings only) | ||
1034 | by sent date. | ||
1035 | */ | ||
1036 | |||
1037 | r = mail_thread_sort(root, mailthread_tree_timecomp, FALSE); | ||
1038 | if (r != MAIL_NO_ERROR) { | ||
1039 | res = r; | ||
1040 | goto free_list; | ||
1041 | } | ||
1042 | |||
1043 | if (use_subject) { | ||
1044 | |||
1045 | /* (5) Gather together messages under the root that have the same | ||
1046 | extracted subject text. | ||
1047 | |||
1048 | (A) Create a table for associating extracted subjects with | ||
1049 | messages. | ||
1050 | */ | ||
1051 | |||
1052 | subject_hash = chash_new(128, CHASH_COPYVALUE); | ||
1053 | if (subject_hash == NULL) { | ||
1054 | res = MAIL_ERROR_MEMORY; | ||
1055 | goto free_list; | ||
1056 | } | ||
1057 | |||
1058 | /* | ||
1059 | (B) Populate the subject table with one message per | ||
1060 | extracted subject. For each child of the root: | ||
1061 | */ | ||
1062 | |||
1063 | for(cur = 0 ; cur < carray_count(rootlist) ; cur ++) { | ||
1064 | struct mailmessage_tree * env_tree; | ||
1065 | chashdatum key; | ||
1066 | chashdatum data; | ||
1067 | char * base_subject; | ||
1068 | int r; | ||
1069 | |||
1070 | env_tree = carray_get(rootlist, cur); | ||
1071 | |||
1072 | /* | ||
1073 | (i) Find the subject of this thread by extracting the | ||
1074 | base subject from the current message, or its first child | ||
1075 | if the current message is a dummy. | ||
1076 | */ | ||
1077 | |||
1078 | r = get_thread_subject(default_from, env_tree, &base_subject); | ||
1079 | |||
1080 | /* | ||
1081 | (ii) If the extracted subject is empty, skip this | ||
1082 | message. | ||
1083 | */ | ||
1084 | |||
1085 | if (r == MAIL_ERROR_SUBJECT_NOT_FOUND) { | ||
1086 | /* no subject found */ | ||
1087 | continue; | ||
1088 | } | ||
1089 | else if (r == MAIL_NO_ERROR) { | ||
1090 | if (* base_subject == '\0') { | ||
1091 | /* subject empty */ | ||
1092 | free(base_subject); | ||
1093 | continue; | ||
1094 | } | ||
1095 | else { | ||
1096 | /* do nothing */ | ||
1097 | } | ||
1098 | } | ||
1099 | else { | ||
1100 | res = r; | ||
1101 | goto free_subject_hash; | ||
1102 | } | ||
1103 | |||
1104 | env_tree->node_base_subject = base_subject; | ||
1105 | |||
1106 | /* | ||
1107 | (iii) Lookup the message associated with this extracted | ||
1108 | subject in the table. | ||
1109 | */ | ||
1110 | |||
1111 | key.data = base_subject; | ||
1112 | key.len = strlen(base_subject); | ||
1113 | |||
1114 | r = chash_get(subject_hash, &key, &data); | ||
1115 | |||
1116 | if (r < 0) { | ||
1117 | /* | ||
1118 | (iv) If there is no message in the table with this | ||
1119 | subject, add the current message and the extracted | ||
1120 | subject to the subject table. | ||
1121 | */ | ||
1122 | |||
1123 | data.data = &cur; | ||
1124 | data.len = sizeof(cur); | ||
1125 | |||
1126 | r = chash_set(subject_hash, &key, &data, NULL); | ||
1127 | if (r < 0) { | ||
1128 | res = MAIL_ERROR_MEMORY; | ||
1129 | goto free_subject_hash; | ||
1130 | } | ||
1131 | } | ||
1132 | else { | ||
1133 | /* | ||
1134 | Otherwise, replace the message in the table with the | ||
1135 | current message if the message in the table is not a | ||
1136 | dummy AND either of the following criteria are true: | ||
1137 | The current message is a dummy, OR | ||
1138 | The message in the table is a reply or forward (its | ||
1139 | original subject contains a subj-refwd part and/or a | ||
1140 | "(fwd)" subj-trailer) and the current message is not. | ||
1141 | */ | ||
1142 | struct mailmessage_tree * msg_in_table; | ||
1143 | unsigned int * iter_in_table; | ||
1144 | int replace; | ||
1145 | |||
1146 | iter_in_table = data.data; | ||
1147 | msg_in_table = carray_get(rootlist, cur); | ||
1148 | |||
1149 | replace = FALSE; | ||
1150 | /* message is dummy if info is NULL */ | ||
1151 | if (msg_in_table->node_msg != NULL) { | ||
1152 | |||
1153 | if (env_tree->node_msg == NULL) | ||
1154 | replace = TRUE; | ||
1155 | else { | ||
1156 | if (env_tree->node_is_reply && !env_tree->node_is_reply) | ||
1157 | replace = TRUE; | ||
1158 | } | ||
1159 | } | ||
1160 | |||
1161 | if (replace) { | ||
1162 | data.data = &cur; | ||
1163 | data.len = sizeof(cur); | ||
1164 | |||
1165 | r = chash_set(subject_hash, &key, &data, NULL); | ||
1166 | if (r < 0) { | ||
1167 | res = MAIL_ERROR_MEMORY; | ||
1168 | goto free_subject_hash; | ||
1169 | } | ||
1170 | } | ||
1171 | } | ||
1172 | } | ||
1173 | |||
1174 | /* | ||
1175 | (C) Merge threads with the same subject. For each child of | ||
1176 | the root: | ||
1177 | */ | ||
1178 | |||
1179 | cur = 0; | ||
1180 | while (cur < carray_count(rootlist)) { | ||
1181 | struct mailmessage_tree * env_tree; | ||
1182 | chashdatum key; | ||
1183 | chashdatum data; | ||
1184 | int r; | ||
1185 | struct mailmessage_tree * main_tree; | ||
1186 | unsigned int * main_cur; | ||
1187 | |||
1188 | env_tree = carray_get(rootlist, cur); | ||
1189 | |||
1190 | if (env_tree == NULL) | ||
1191 | goto next_msg; | ||
1192 | |||
1193 | /* | ||
1194 | (i) Find the subject of this thread as in step 4.B.i | ||
1195 | above. | ||
1196 | */ | ||
1197 | |||
1198 | /* already done in tree->node_base_subject */ | ||
1199 | |||
1200 | /* | ||
1201 | (ii) If the extracted subject is empty, skip this | ||
1202 | message. | ||
1203 | */ | ||
1204 | |||
1205 | if (env_tree->node_base_subject == NULL) | ||
1206 | goto next_msg; | ||
1207 | |||
1208 | if (* env_tree->node_base_subject == '\0') | ||
1209 | goto next_msg; | ||
1210 | |||
1211 | /* | ||
1212 | (iii) Lookup the message associated with this extracted | ||
1213 | subject in the table. | ||
1214 | */ | ||
1215 | |||
1216 | key.data = env_tree->node_base_subject; | ||
1217 | key.len = strlen(env_tree->node_base_subject); | ||
1218 | |||
1219 | r = chash_get(subject_hash, &key, &data); | ||
1220 | if (r < 0) | ||
1221 | goto next_msg; | ||
1222 | |||
1223 | /* | ||
1224 | (iv) If the message in the table is the current message, | ||
1225 | skip this message. | ||
1226 | */ | ||
1227 | |||
1228 | main_cur = data.data; | ||
1229 | if (* main_cur == cur) | ||
1230 | goto next_msg; | ||
1231 | |||
1232 | /* | ||
1233 | Otherwise, merge the current message with the one in the | ||
1234 | table using the following rules: | ||
1235 | */ | ||
1236 | |||
1237 | main_tree = carray_get(rootlist, * main_cur); | ||
1238 | |||
1239 | /* | ||
1240 | If both messages are dummies, append the current | ||
1241 | message's children to the children of the message in | ||
1242 | the table (the children of both messages become | ||
1243 | siblings), and then delete the current message. | ||
1244 | */ | ||
1245 | |||
1246 | if ((env_tree->node_msg == NULL) && (main_tree->node_msg == NULL)) { | ||
1247 | unsigned int old_size; | ||
1248 | |||
1249 | old_size = carray_count(main_tree->node_children); | ||
1250 | |||
1251 | r = carray_set_size(main_tree->node_children, old_size + | ||
1252 | carray_count(env_tree->node_children)); | ||
1253 | if (r < 0) { | ||
1254 | res = MAIL_ERROR_MEMORY; | ||
1255 | goto free_subject_hash; | ||
1256 | } | ||
1257 | |||
1258 | for(i = 0 ; i < carray_count(env_tree->node_children) ; i ++) { | ||
1259 | struct mailmessage_tree * child; | ||
1260 | |||
1261 | child = carray_get(env_tree->node_children, i); | ||
1262 | carray_set(main_tree->node_children, old_size + i, child); | ||
1263 | /* set parent */ | ||
1264 | child->node_parent = main_tree; | ||
1265 | } | ||
1266 | carray_set_size(env_tree->node_children, 0); | ||
1267 | /* this is the only case where children can be NULL, | ||
1268 | this is before freeing it */ | ||
1269 | mailmessage_tree_free(env_tree); | ||
1270 | carray_delete_fast(rootlist, cur); | ||
1271 | } | ||
1272 | |||
1273 | /* | ||
1274 | If the message in the table is a dummy and the current | ||
1275 | message is not, make the current message a child of | ||
1276 | the message in the table (a sibling of it's children). | ||
1277 | */ | ||
1278 | |||
1279 | else if (main_tree->node_msg == NULL) { | ||
1280 | r = carray_add(main_tree->node_children, env_tree, NULL); | ||
1281 | if (r < 0) { | ||
1282 | res = MAIL_ERROR_MEMORY; | ||
1283 | goto free_subject_hash; | ||
1284 | } | ||
1285 | /* set parent */ | ||
1286 | env_tree->node_parent = main_tree; | ||
1287 | |||
1288 | carray_delete_fast(rootlist, cur); | ||
1289 | } | ||
1290 | |||
1291 | /* | ||
1292 | If the current message is a reply or forward and the | ||
1293 | message in the table is not, make the current message | ||
1294 | a child of the message in the table (a sibling of it's | ||
1295 | children). | ||
1296 | */ | ||
1297 | |||
1298 | else if (env_tree->node_is_reply && !main_tree->node_is_reply) { | ||
1299 | r = carray_add(main_tree->node_children, env_tree, NULL); | ||
1300 | if (r < 0) { | ||
1301 | res = MAIL_ERROR_MEMORY; | ||
1302 | goto free_subject_hash; | ||
1303 | } | ||
1304 | /* set parent */ | ||
1305 | env_tree->node_parent = main_tree; | ||
1306 | |||
1307 | carray_delete_fast(rootlist, cur); | ||
1308 | } | ||
1309 | |||
1310 | /* | ||
1311 | Otherwise, create a new dummy message and make both | ||
1312 | the current message and the message in the table | ||
1313 | children of the dummy. Then replace the message in | ||
1314 | the table with the dummy message. | ||
1315 | Note: Subject comparisons are case-insensitive, as | ||
1316 | described under "Internationalization | ||
1317 | Considerations." | ||
1318 | */ | ||
1319 | |||
1320 | else { | ||
1321 | struct mailmessage_tree * new_main_tree; | ||
1322 | char * base_subject; | ||
1323 | unsigned int last; | ||
1324 | |||
1325 | new_main_tree = mailmessage_tree_new(NULL, (time_t) -1, NULL); | ||
1326 | if (new_main_tree == NULL) { | ||
1327 | res = MAIL_ERROR_MEMORY; | ||
1328 | goto free_subject_hash; | ||
1329 | } | ||
1330 | |||
1331 | /* main_tree->node_base_subject is never NULL */ | ||
1332 | |||
1333 | base_subject = strdup(main_tree->node_base_subject); | ||
1334 | if (base_subject == NULL) { | ||
1335 | mailmessage_tree_free(new_main_tree); | ||
1336 | res = MAIL_ERROR_MEMORY; | ||
1337 | goto free_subject_hash; | ||
1338 | } | ||
1339 | |||
1340 | new_main_tree->node_base_subject = base_subject; | ||
1341 | |||
1342 | r = carray_add(rootlist, new_main_tree, &last); | ||
1343 | if (r < 0) { | ||
1344 | mailmessage_tree_free(new_main_tree); | ||
1345 | res = MAIL_ERROR_MEMORY; | ||
1346 | goto free_subject_hash; | ||
1347 | } | ||
1348 | |||
1349 | r = carray_add(new_main_tree->node_children, main_tree, NULL); | ||
1350 | if (r < 0) { | ||
1351 | res = MAIL_ERROR_MEMORY; | ||
1352 | goto free_subject_hash; | ||
1353 | } | ||
1354 | /* set parent */ | ||
1355 | main_tree->node_parent = new_main_tree; | ||
1356 | |||
1357 | carray_delete_fast(rootlist, * main_cur); | ||
1358 | |||
1359 | r = carray_add(new_main_tree->node_children, env_tree, NULL); | ||
1360 | if (r < 0) { | ||
1361 | res = MAIL_ERROR_MEMORY; | ||
1362 | goto free_subject_hash; | ||
1363 | } | ||
1364 | /* set parent */ | ||
1365 | env_tree->node_parent = new_main_tree; | ||
1366 | |||
1367 | carray_delete_fast(rootlist, cur); | ||
1368 | |||
1369 | data.data = &last; | ||
1370 | data.len = sizeof(last); | ||
1371 | |||
1372 | r = chash_set(subject_hash, &key, &data, NULL); | ||
1373 | |||
1374 | if (r < 0) { | ||
1375 | res = MAIL_ERROR_MEMORY; | ||
1376 | goto free_subject_hash; | ||
1377 | } | ||
1378 | } | ||
1379 | |||
1380 | continue; | ||
1381 | |||
1382 | next_msg: | ||
1383 | cur ++; | ||
1384 | continue; | ||
1385 | } | ||
1386 | |||
1387 | i = 0; | ||
1388 | for(cur = 0 ; cur < carray_count(rootlist) ; cur ++) { | ||
1389 | struct mailmessage_tree * env_tree; | ||
1390 | |||
1391 | env_tree = carray_get(rootlist, cur); | ||
1392 | if (env_tree == NULL) | ||
1393 | continue; | ||
1394 | |||
1395 | carray_set(rootlist, i, env_tree); | ||
1396 | i ++; | ||
1397 | } | ||
1398 | carray_set_size(rootlist, i); | ||
1399 | |||
1400 | chash_free(subject_hash); | ||
1401 | } | ||
1402 | |||
1403 | /* | ||
1404 | (6) Traverse the messages under the root and sort each set of | ||
1405 | siblings by sent date. Traverse the messages in such a way | ||
1406 | that the "youngest" set of siblings are sorted first, and the | ||
1407 | "oldest" set of siblings are sorted last (grandchildren are | ||
1408 | sorted before children, etc). | ||
1409 | |||
1410 | In the case of an exact match on | ||
1411 | sent date or if either of the Date: headers used in a | ||
1412 | comparison can not be parsed, use the order in which the | ||
1413 | messages appear in the mailbox (that is, by sequence number) to | ||
1414 | determine the order. In the case of a dummy message (which can | ||
1415 | only occur with top-level siblings), use its first child for | ||
1416 | sorting. | ||
1417 | */ | ||
1418 | |||
1419 | if (comp_func != NULL) { | ||
1420 | r = mail_thread_sort(root, comp_func, TRUE); | ||
1421 | if (r != MAIL_NO_ERROR) { | ||
1422 | res = r; | ||
1423 | goto free_list; | ||
1424 | } | ||
1425 | } | ||
1426 | |||
1427 | * result = root; | ||
1428 | |||
1429 | return MAIL_NO_ERROR; | ||
1430 | |||
1431 | free_subject_hash: | ||
1432 | chash_free(subject_hash); | ||
1433 | free_list: | ||
1434 | if (msg_list != NULL) { | ||
1435 | for(i = 0 ; i < carray_count(msg_list) ; i ++) | ||
1436 | mailmessage_tree_free(carray_get(msg_list, i)); | ||
1437 | carray_free(msg_list); | ||
1438 | } | ||
1439 | free_root: | ||
1440 | mailmessage_tree_free_recursive(root); | ||
1441 | free_hash: | ||
1442 | if (msg_id_hash != NULL) | ||
1443 | chash_free(msg_id_hash); | ||
1444 | err: | ||
1445 | return res; | ||
1446 | } | ||
1447 | |||
1448 | |||
1449 | |||
1450 | static int | ||
1451 | mail_build_thread_orderedsubject(char * default_from, | ||
1452 | struct mailmessage_list * env_list, | ||
1453 | struct mailmessage_tree ** result, | ||
1454 | int (* comp_func)(struct mailmessage_tree **, | ||
1455 | struct mailmessage_tree **)) | ||
1456 | { | ||
1457 | unsigned int i; | ||
1458 | carray * rootlist; | ||
1459 | unsigned int cur; | ||
1460 | struct mailmessage_tree * root; | ||
1461 | int res; | ||
1462 | int r; | ||
1463 | struct mailmessage_tree * current_thread; | ||
1464 | |||
1465 | root = mailmessage_tree_new(NULL, (time_t) -1, NULL); | ||
1466 | if (root == NULL) { | ||
1467 | res = MAIL_ERROR_MEMORY; | ||
1468 | goto err; | ||
1469 | } | ||
1470 | rootlist = root->node_children; | ||
1471 | |||
1472 | /* | ||
1473 | The ORDEREDSUBJECT threading algorithm is also referred to as | ||
1474 | "poor man's threading." | ||
1475 | */ | ||
1476 | |||
1477 | for(i = 0 ; i < carray_count(env_list->msg_tab) ; i ++) { | ||
1478 | mailmessage * msg; | ||
1479 | struct mailmessage_tree * env_tree; | ||
1480 | char * base_subject; | ||
1481 | time_t date; | ||
1482 | |||
1483 | msg = carray_get(env_list->msg_tab, i); | ||
1484 | |||
1485 | if (msg == NULL) | ||
1486 | continue; | ||
1487 | |||
1488 | if (msg->msg_fields != NULL) { | ||
1489 | |||
1490 | date = get_date(msg); | ||
1491 | |||
1492 | env_tree = mailmessage_tree_new(NULL, date, msg); | ||
1493 | if (env_tree == NULL) { | ||
1494 | res = MAIL_ERROR_MEMORY; | ||
1495 | goto free; | ||
1496 | } | ||
1497 | |||
1498 | /* set parent */ | ||
1499 | env_tree->node_parent = root; | ||
1500 | r = carray_add(rootlist, env_tree, NULL); | ||
1501 | if (r < 0) { | ||
1502 | mailmessage_tree_free(env_tree); | ||
1503 | res = MAIL_ERROR_MEMORY; | ||
1504 | goto free; | ||
1505 | } | ||
1506 | |||
1507 | r = get_extracted_subject(default_from, env_tree, &base_subject); | ||
1508 | switch (r) { | ||
1509 | case MAIL_NO_ERROR: | ||
1510 | env_tree->node_base_subject = base_subject; | ||
1511 | break; | ||
1512 | |||
1513 | case MAIL_ERROR_SUBJECT_NOT_FOUND: | ||
1514 | break; | ||
1515 | |||
1516 | default: | ||
1517 | res = r; | ||
1518 | goto free; | ||
1519 | } | ||
1520 | } | ||
1521 | } | ||
1522 | |||
1523 | /* | ||
1524 | The searched messages are sorted by | ||
1525 | subject and then by the sent date. | ||
1526 | */ | ||
1527 | |||
1528 | r = mail_thread_sort(root, tree_subj_time_comp, FALSE); | ||
1529 | if (r != MAIL_NO_ERROR) { | ||
1530 | res = r; | ||
1531 | goto free; | ||
1532 | } | ||
1533 | |||
1534 | /* | ||
1535 | The messages are then split | ||
1536 | into separate threads, with each thread containing messages | ||
1537 | with the same extracted subject text. | ||
1538 | */ | ||
1539 | |||
1540 | current_thread = NULL; | ||
1541 | |||
1542 | cur = 0; | ||
1543 | while (cur < carray_count(rootlist)) { | ||
1544 | struct mailmessage_tree * cur_env_tree; | ||
1545 | |||
1546 | cur_env_tree = carray_get(rootlist, cur); | ||
1547 | if (current_thread == NULL) { | ||
1548 | current_thread = cur_env_tree; | ||
1549 | cur ++; | ||
1550 | continue; | ||
1551 | } | ||
1552 | |||
1553 | if ((cur_env_tree->node_base_subject == NULL) || | ||
1554 | (current_thread->node_base_subject == NULL)) { | ||
1555 | current_thread = cur_env_tree; | ||
1556 | cur ++; | ||
1557 | continue; | ||
1558 | } | ||
1559 | |||
1560 | if (strcmp(cur_env_tree->node_base_subject, | ||
1561 | current_thread->node_base_subject) == 0) { | ||
1562 | |||
1563 | /* set parent */ | ||
1564 | cur_env_tree->node_parent = current_thread; | ||
1565 | r = carray_add(current_thread->node_children, cur_env_tree, NULL); | ||
1566 | if (r < 0) { | ||
1567 | res = MAIL_ERROR_MEMORY; | ||
1568 | goto free; | ||
1569 | } | ||
1570 | |||
1571 | carray_delete(rootlist, cur); | ||
1572 | } | ||
1573 | else | ||
1574 | cur ++; | ||
1575 | current_thread = cur_env_tree; | ||
1576 | } | ||
1577 | |||
1578 | /* | ||
1579 | Finally, the threads are | ||
1580 | sorted by the sent date of the first message in the thread. | ||
1581 | Note that each message in a thread is a child (as opposed to a | ||
1582 | sibling) of the previous message. | ||
1583 | */ | ||
1584 | |||
1585 | if (comp_func != NULL) { | ||
1586 | r = mail_thread_sort(root, comp_func, FALSE); | ||
1587 | if (r != MAIL_NO_ERROR) { | ||
1588 | res = r; | ||
1589 | goto free; | ||
1590 | } | ||
1591 | } | ||
1592 | |||
1593 | * result = root; | ||
1594 | |||
1595 | return MAIL_NO_ERROR; | ||
1596 | |||
1597 | free: | ||
1598 | mailmessage_tree_free_recursive(root); | ||
1599 | err: | ||
1600 | return res; | ||
1601 | } | ||
1602 | |||
1603 | |||
1604 | int mail_build_thread(int type, char * default_from, | ||
1605 | struct mailmessage_list * env_list, | ||
1606 | struct mailmessage_tree ** result, | ||
1607 | int (* comp_func)(struct mailmessage_tree **, | ||
1608 | struct mailmessage_tree **)) | ||
1609 | { | ||
1610 | unsigned int i; | ||
1611 | |||
1612 | for(i = 0 ; i < carray_count(env_list->msg_tab) ; i ++) | ||
1613 | mailmessage_resolve_single_fields(carray_get(env_list->msg_tab, i)); | ||
1614 | |||
1615 | switch (type) { | ||
1616 | case MAIL_THREAD_REFERENCES: | ||
1617 | return mail_build_thread_references(default_from, | ||
1618 | env_list, result, TRUE, comp_func); | ||
1619 | |||
1620 | case MAIL_THREAD_REFERENCES_NO_SUBJECT: | ||
1621 | return mail_build_thread_references(default_from, | ||
1622 | env_list, result, FALSE, comp_func); | ||
1623 | |||
1624 | case MAIL_THREAD_ORDEREDSUBJECT: | ||
1625 | return mail_build_thread_orderedsubject(default_from, | ||
1626 | env_list, result, comp_func); | ||
1627 | |||
1628 | default: | ||
1629 | return MAIL_ERROR_NOT_IMPLEMENTED; | ||
1630 | } | ||
1631 | } | ||