1 /* jwz-style threading
2 * clean-room implementation of https://www.jwz.org/doc/threading.html
3 * without looking at any code
4 *
5 * subject threading and sibling sorting is not done yet
6 */
7
8 #include <sys/stat.h>
9 #include <sys/types.h>
10
11 #include <errno.h>
12 #include <fcntl.h>
13 #include <search.h>
14 #include <stdint.h>
15 #include <stdio.h>
16 #include <stdlib.h>
17 #include <string.h>
18 #include <time.h>
19 #include <unistd.h>
20
21 #include "blaze822.h"
22 #include "xpledge.h"
23
24 static int vflag;
25 static int pflag;
26 static int rflag;
27 static int optional;
28
29 struct container {
30 char *mid;
31 char *file;
32 struct message *msg;
33 time_t date;
34 struct container *parent;
35 struct container *child;
36 struct container *next;
37 int optional;
38 };
39
40 static void *mids;
41
42 int
midorder(const void * a,const void * b)43 midorder(const void *a, const void *b)
44 {
45 struct container *ia = (struct container *)a;
46 struct container *ib = (struct container *)b;
47
48 return strcmp(ia->mid, ib->mid);
49 }
50
51 char *
mid(struct message * msg)52 mid(struct message *msg)
53 {
54 char *v;
55 v = blaze822_hdr(msg, "message-id");
56 // XXX intern mid?
57 if (v) {
58 char *m;
59
60 m = strchr(v, '<');
61 if (!m)
62 return strdup(v);
63 v = strchr(m, '>');
64 if (!v)
65 return strdup(m);
66 return strndup(m+1, v-m-1);
67 } else {
68 // invent new message-id for internal tracking
69 static long i;
70 char buf[40];
71 snprintf(buf, sizeof buf, "thread%08ld@localhost", ++i);
72 return strdup(buf);
73 }
74 }
75
76 struct container *
midcont(char * mid)77 midcont(char *mid)
78 {
79 struct container key, **result;
80 if (!mid)
81 exit(111);
82 key.mid = mid;
83
84 if (!(result = tfind(&key, &mids, midorder))) {
85 struct container *c = malloc(sizeof (struct container));
86 if (!c)
87 exit(111);
88 c->mid = mid;
89 c->file = 0;
90 c->msg = 0;
91 c->date = -1;
92 c->optional = 0;
93 c->parent = c->child = c->next = 0;
94 return *(struct container **)tsearch(c, &mids, midorder);
95 } else {
96 return *result;
97 }
98 }
99
100 struct container *
store_id(char * file,struct message * msg)101 store_id(char *file, struct message *msg)
102 {
103 struct container *c;
104
105 c = midcont(mid(msg));
106 c->file = strdup(file);
107 c->msg = msg;
108 c->optional = optional;
109
110 return c;
111 }
112
113 int
reachable(struct container * child,struct container * parent)114 reachable(struct container *child, struct container *parent)
115 {
116 int r = 0;
117
118 if (strcmp(child->mid, parent->mid) == 0)
119 return 1;
120 if (child->child)
121 r |= reachable(child->child, parent);
122 if (child->next)
123 r |= reachable(child->next, parent);
124 return r;
125 }
126
127 void
thread(char * file)128 thread(char *file)
129 {
130 struct message *msg;
131
132 while (*file == ' ' || *file == '\t')
133 file++;
134
135 msg = blaze822(file);
136 if (!msg)
137 return;
138
139 struct container *c = store_id(file, msg);
140
141 char *mid = "";
142
143 char *v, *m;
144 struct container *parent = 0, *me = 0;
145
146 if ((v = blaze822_hdr(msg, "date"))) {
147 c->date = blaze822_date(v);
148 } else {
149 c->date = -1;
150 }
151
152 v = blaze822_hdr(msg, "references");
153 if (v) {
154 parent = 0;
155 while (1) {
156 m = strchr(v, '<');
157 if (!m)
158 break;
159 v = strchr(m, '>');
160 if (!v)
161 break;
162 mid = strndup(m+1, v-m-1);
163 // XXX free?
164
165 me = midcont(mid);
166
167 if (me == c)
168 continue;
169
170 if (parent && !me->parent &&
171 !reachable(me, parent) && !reachable(parent, me)) {
172 me->parent = parent;
173 me->next = parent->child;
174 parent->child = me;
175 }
176
177 parent = me;
178 }
179 }
180
181 v = blaze822_hdr(msg, "in-reply-to");
182 char *irt;
183 if (v) {
184 m = strchr(v, '<');
185 if (!m)
186 goto out;
187 v = strchr(m, '>');
188 if (!v)
189 goto out;
190 irt = strndup(m+1, v-m-1);
191
192 if (strcmp(irt, mid) != 0) {
193 parent = midcont(irt);
194 } else {
195 free(irt);
196 }
197 }
198 out:
199
200 if (parent && parent != c) {
201 struct container *r;
202
203 // check we don't introduce a new loop
204 if (reachable(parent, c) || reachable(c, parent))
205 goto out2;
206
207 if (c->parent == parent) { // already correct
208 goto out2;
209 } else if (c->parent) {
210 // if we already have a wrong parent, orphan us first
211
212 if (c->parent->child == c) // first in list
213 c->parent->child = c->parent->child->next;
214 for (r = c->parent->child; r; r = r->next) {
215 if (r->next == c)
216 r->next = c->next;
217 }
218
219 c->next = 0;
220 }
221
222 c->parent = parent;
223
224 // add at the end
225 if (!parent->child) {
226 parent->child = c;
227 } else {
228 for (r = parent->child; r && r->next; r = r->next)
229 if (r == c)
230 goto out2;
231 r->next = c;
232 c->next = 0;
233 }
234
235 out2:
236 // someone said our parent was our child, a lie
237 if (c->child == c->parent) {
238 c->child->parent = 0;
239 c->child = 0;
240 }
241 }
242 }
243
244 time_t
newest(struct container * c,int depth)245 newest(struct container *c, int depth)
246 {
247 time_t n = -1;
248
249 if (!c)
250 return n;
251
252 do {
253 if (c->child) {
254 time_t r = newest(c->child, depth+1);
255 if (n < r)
256 n = r;
257 }
258 if (n < c->date)
259 n = c->date;
260 } while ((c = c->next));
261
262 return n;
263 }
264
265 struct container *top;
266 struct container *lastc;
267
268 void
find_root(const void * nodep,const VISIT which,const int depth)269 find_root(const void *nodep, const VISIT which, const int depth)
270 {
271 (void)depth;
272
273 if (which == preorder || which == leaf) {
274 struct container *c = *(struct container **)nodep;
275
276 if (!c->parent) {
277 lastc->next = c;
278 c->next = 0;
279 time_t r = newest(c->child, 0);
280 if (c->date < r)
281 c->date = r;
282 lastc = c;
283 }
284 }
285 }
286
287 void
find_roots()288 find_roots()
289 {
290 top = malloc(sizeof (struct container));
291 if (!top)
292 exit(111);
293 top->msg = 0;
294 top->date = -1;
295 top->file = 0;
296 top->next = top->child = top->parent = 0;
297 top->optional = 0;
298 top->mid = "(top)";
299
300 lastc = top;
301
302 twalk(mids, find_root);
303
304 top->child = top->next;
305 top->next = 0;
306 }
307
308 void
prune_tree(struct container * c,int depth)309 prune_tree(struct container *c, int depth)
310 {
311 do {
312 if (c->child)
313 prune_tree(c->child, depth+1);
314 if (depth >= 0 && !c->file && c->child && !c->child->next) {
315 // turn into child if we don't exist and only have a child
316 c->mid = c->child->mid;
317 c->file = c->child->file;
318 c->msg = c->child->msg;
319 if (c->child->date > c->date)
320 c->date = c->child->date;
321 c->optional = c->child->optional;
322 c->child = c->child->child;
323 }
324 } while ((c = c->next));
325 }
326
327 int
alloptional(struct container * c)328 alloptional(struct container *c)
329 {
330 do {
331 if (!c->optional && c->file)
332 return 0;
333 if (c->child && !alloptional(c->child))
334 return 0;
335 } while ((c = c->next));
336
337 return 1;
338 }
339
340 static int
dateorder(const void * a,const void * b)341 dateorder(const void *a, const void *b)
342 {
343 struct container *ia = *(struct container **)a;
344 struct container *ib = *(struct container **)b;
345
346 if (ia->date < ib->date)
347 return -1;
348 else if (ia->date > ib->date)
349 return 1;
350 return 0;
351 }
352
353 static int
reverse_dateorder(const void * a,const void * b)354 reverse_dateorder(const void *a, const void *b)
355 {
356 return dateorder(b, a);
357 }
358
359 void
sort_tree(struct container * c,int depth)360 sort_tree(struct container *c, int depth)
361 {
362 if (c && c->child) {
363 struct container *r;
364 int i, j;
365 for (r = c->child, i = 0; r; r = r->next, i++)
366 sort_tree(r, depth+1);
367
368 if (i == 1) // no sort needed
369 return;
370
371 struct container **a = calloc(sizeof (struct container *), i);
372 if (!a)
373 return;
374
375 for (r = c->child, i = 0; r; r = r->next, i++)
376 a[i] = r;
377
378 qsort(a, i, sizeof (struct container *),
379 rflag && depth < 0 ? reverse_dateorder : dateorder);
380
381 c->child = a[0];
382 for (j = 0; j+1 < i; j++)
383 a[j]->next = a[j+1];
384 a[i-1]->next = 0;
385
386 free(a);
387 }
388 }
389
390 void
print_tree(struct container * c,int depth)391 print_tree(struct container *c, int depth)
392 {
393 do {
394 // skip toplevel threads when they are unresolved or all optional
395 // (or when -p is given, skip those subthreads)
396 if ((depth <= 1 || pflag) &&
397 (c->optional || !c->file) &&
398 (!c->child || alloptional(c->child)))
399 continue;
400
401 if (depth >= 0) {
402 int i;
403 for (i = 0; i < depth; i++)
404 printf(" ");
405 if (c->file)
406 printf("%s\n", c->file);
407 else
408 printf("<%s>\n", c->mid);
409 }
410
411 if (c->child)
412 print_tree(c->child, depth+1);
413 } while ((c = c->next));
414 }
415
416 int
main(int argc,char * argv[])417 main(int argc, char *argv[])
418 {
419 int c;
420
421 optional = 1;
422
423 xpledge("stdio rpath", "");
424
425 while ((c = getopt(argc, argv, "S:prv")) != -1)
426 switch (c) {
427 case 'S': blaze822_loop1(optarg, thread); break;
428 case 'v': vflag = 1; break;
429 case 'p': pflag = 1; break;
430 case 'r': rflag = 1; break;
431 default:
432 fprintf(stderr, "Usage: mthread [-vpr] [-S dir] [msgs...]\n");
433 exit(1);
434 }
435
436 optional = 0;
437
438 if (argc == optind && isatty(0))
439 blaze822_loop1(":", thread);
440 else
441 blaze822_loop(argc-optind, argv+optind, thread);
442
443 // the tree of all toplevel threads has depth -1,
444 // so toplevel threads have depth 0.
445
446 find_roots();
447 if (!vflag)
448 prune_tree(top, -1);
449 sort_tree(top, -1);
450 print_tree(top, -1);
451
452 return 0;
453 }
454