1 /* $Id: Threading.cpp 1649 2009-10-19 14:35:01Z terpstra $
2 *
3 * Threading.h - Helper which can load a thread tree
4 *
5 * Copyright (C) 2002 - Wesley W. Terpstra
6 *
7 * License: GPL
8 *
9 * Authors: 'Wesley W. Terpstra' <wesley@terpstra.ca>
10 *
11 * This program is free software; you can redistribute it and/or modify
12 * it under the terms of the GNU General Public License as published by
13 * the Free Software Foundation; version 2.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, write to the Free Software
22 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23 */
24
25 #define _FILE_OFFSET_BITS 64
26
27 #include "Threading.h"
28 #include <Keys.h>
29 #include <memory>
30 #include <cerrno>
31 #include <iostream>
32 #include <list>
33
34 #define DAY_GAP_FOR_NEW_THREAD 40
35
36 #define EMPTY_CELL "<a/>"
37 #define BAR_NS "<b/>"
38 #define BAR_EW "<c/>"
39 #define CORNER_SW "<d/>"
40 #define TEE_WSE "<e/>"
41
42 #define MESSAGE_END 'f'
43 #define MESSAGE_DOWN 'g'
44 #define MESSAGE_BOTH 'h'
45 #define TOPMESSAGE_END 'i'
46 #define TOPMESSAGE_DOWN 'j'
47 #define TOPMESSAGE_BOTH 'k'
48
49 using namespace std;
50 using namespace ESort;
51
load(Reader * r,const Summary & sum,Key & out)52 string Threading::load(Reader* r, const Summary& sum, Key& out)
53 {
54 // dump any prior state
55 hashes.clear();
56 nodes.clear();
57
58 string prefix =
59 LU_THREADING +
60 subject_hash(sum.subject().c_str());
61
62 auto_ptr<Walker> backwards(r->seek(prefix, sum.id().raw(), Backward));
63
64 /** Walk backwards until we find step off the subject, or there is
65 * a break of more than 40 days between messages.
66 */
67 MessageId root = sum.id();
68 while (backwards->advance() != -1)
69 {
70 if (backwards->key.length() < prefix.length() + 8)
71 return "corrupt threading record -- too short";
72
73 MessageId x(backwards->key.c_str() + prefix.length(), 1);
74 if (x.timestamp() + 60*60*24*DAY_GAP_FOR_NEW_THREAD
75 < root.timestamp())
76 break;
77
78 root = x;
79 }
80
81 /** Ok, we have found what will be the root of the tree.
82 * Now, we shall seek and read the messages off.
83 */
84 auto_ptr<Walker> forwards(r->seek(prefix, root.raw(), Forward));
85
86 /* We read the nodes off in timestamp sorted order
87 */
88 std::list<Node> timestamp_sorted;
89
90 /** Walk forwards until we find step off the subject, or there is
91 * a break of more than 40 days between messages.
92 */
93 MessageId prev = root;
94 while (forwards->advance() != -1)
95 {
96 if (forwards->key.length() < prefix.length() + 8)
97 return "corrupt forwardthreading record -- too short";
98
99 MessageId x(forwards->key.c_str() + prefix.length(), 1);
100
101 if (prev.timestamp() + 60*60*24*DAY_GAP_FOR_NEW_THREAD
102 < x.timestamp())
103 break;
104
105 timestamp_sorted.push_back(Node(x));
106 Node& b = timestamp_sorted.back();
107
108 b.in_reply_tos.assign(
109 forwards->key.c_str() + prefix.length() + 8,
110 forwards->key.length() - prefix.length() - 8);
111
112 // record that this hash does in fact exist
113 hashes[b.summary.id().hash()] = -1;
114
115 prev = x;
116 }
117
118 /** We now have all the messages in timestamp sorted order.
119 * Let's scan the list for the first message with no predecessor.
120 */
121 while (!timestamp_sorted.empty())
122 {
123 std::list<Node>::iterator i;
124
125 for (i = timestamp_sorted.begin(); i != timestamp_sorted.end(); ++i)
126 {
127 // scan all the in_reply_tos. if none of them are left
128 // in timestamp_sorted, then this should come next.
129 // (ie: no predecessors and lowest timestamp)
130
131 i->replyee = -1; // find best predecessor also
132
133 string::size_type replyto;
134 for (replyto = 0; replyto+4 <= i->in_reply_tos.size(); replyto += 4)
135 {
136 map<string, int>::iterator r = hashes.find(
137 i->in_reply_tos.substr(replyto, 4));
138
139 if (r != hashes.end())
140 {
141 if (r->second == -1)
142 { // still in the timestamp queue
143 break;
144 }
145 else if (r->second > i->replyee)
146 { // an older predecessor
147 i->replyee = r->second;
148 }
149 }
150 }
151
152 // Did we find no queued predecessors?
153 if (replyto+4 > i->in_reply_tos.size())
154 break;
155 }
156
157 // deal with cycles (theorectically impossible, but ...)
158 if (i == timestamp_sorted.end()) i = timestamp_sorted.begin();
159
160 hashes[i->summary.id().hash()] = nodes.size();
161 nodes.push_back(*i);
162 timestamp_sorted.erase(i);
163
164 // prep the node
165 Node& b = nodes.back();
166 b.replies = 0;
167 b.replyor_first = -1;
168 b.replyor_next = -1;
169 b.draw_next = -1;
170 b.depth = nodes.size() - 1;
171 b.consumed = 0;
172
173 if (b.replyee != -1)
174 nodes[b.replyee].replies++;
175
176 // check for high-lighted node
177 if (b.summary.id() == sum.id())
178 out = b.depth;
179 }
180
181 Node* tree = &nodes[0];
182
183 /** Resolve back links
184 */
185 for (int i = nodes.size()-1; i > 0; i--)
186 {
187 int p = tree[i].replyee;
188 if (p == -1) continue;
189
190 if (tree[p].depth < tree[i].depth)
191 tree[p].depth = tree[i].depth;
192
193 /* Insertion sort is not that fast...
194 * But compared to the drawing algo, this n^2 is negligable.
195 */
196 int* w = &tree[p].replyor_first;
197 while (*w != -1 && tree[*w].depth > tree[i].depth)
198 w = &tree[*w].replyor_next;
199
200 tree[i].replyor_next = *w;
201 *w = i;
202 }
203
204 return "";
205 }
206
replies(Key k)207 set<Summary> Threading::replies(Key k)
208 {
209 set<Summary> out;
210 for (int l = nodes[k].replyor_first; l != -1; l = nodes[l].replyor_next)
211 out.insert(nodes[l].summary);
212 return out;
213 }
214
getSummary(Key m)215 Summary& Threading::getSummary(Key m)
216 {
217 return nodes[m].summary;
218 }
219
my_service_tree_message_link(ostream & o,Threading::Node * tree,int i,int hl)220 void my_service_tree_message_link(
221 ostream& o,
222 Threading::Node* tree,
223 int i,
224 int hl)
225 {
226 int selected = (hl == i);
227 // int drift = 0; // !!! too bad I can't do this...
228 char x;
229
230 if (tree[i].replyee == -1)
231 {
232 switch (tree[i].replies)
233 {
234 case 0: x = TOPMESSAGE_END; break;
235 case 1: x = TOPMESSAGE_DOWN; break;
236 default: x = TOPMESSAGE_BOTH; break;
237 }
238 }
239 else
240 {
241 switch (tree[i].replies)
242 {
243 case 0: x = MESSAGE_END; break;
244 case 1: x = MESSAGE_DOWN; break;
245 default: x = MESSAGE_BOTH; break;
246 }
247 }
248
249 o << "<" << x;
250 if (selected) o << " selected=\"yes\"";
251 o << " id=\"" << tree[i].summary.id().serialize() << "\"/>";
252 }
253
my_service_draw_tree(Threading::Node * tree,int n,int u)254 int my_service_draw_tree(
255 Threading::Node* tree,
256 int n, int u)
257 {
258 int i;
259 int c;
260 int col = 0;
261
262 /* Find the column we can use. */
263 for (i = u; i <= tree[n].depth; i++)
264 if (col < tree[i].consumed)
265 col = tree[i].consumed;
266
267 tree[n].consumed = col;
268
269 tree[n].column = col;
270 for (c = tree[n].replyor_first; c != -1; c = tree[c].replyor_next)
271 {
272 col = my_service_draw_tree(tree, c, n);
273 for (i = n; i < c; i++)
274 tree[i].consumed = col+1;
275 }
276
277 return tree[n].column;
278 }
279
draw_tree(Reader * db)280 string Threading::draw_tree(Reader* db)
281 {
282 Threading::Node* tree = &nodes[0];
283 int tree_size = nodes.size();
284
285 for (int i = 0; i < tree_size; ++i)
286 if (tree[i].replyee == -1)
287 my_service_draw_tree(tree, i, i);
288
289 return "";
290 }
291
my_service_draw_tree_row(ostream & o,Threading::Node * tree,int * head,int i)292 void my_service_draw_tree_row(
293 ostream& o,
294 Threading::Node* tree,
295 int* head,
296 int i)
297 {
298 int col, p;
299 int* w;
300
301 #ifdef DEBUG
302 printf("\nOffset: %d", tree[i].column);
303 #endif
304
305 col = 0;
306 w = head;
307 while (*w != -1)
308 {
309 for (; col < tree[*w].column; col++)
310 o << EMPTY_CELL;
311
312 if (*w == i) break;
313
314 o << BAR_NS;
315 col++;
316 w = &tree[*w].draw_next;
317 }
318
319 for (; col < tree[i].column; col++)
320 o << EMPTY_CELL;
321
322 my_service_tree_message_link(o, tree, i, -1);
323 col++;
324
325 /* Cut ourselves out of the list and graft on our
326 * children. While we're at it, draw the links.
327 */
328 for (p = tree[i].replyor_first; p != -1; p = tree[p].replyor_next)
329 {
330 *w = p;
331 w = &tree[p].draw_next;
332
333 if (col > tree[p].column) continue;
334
335 for (; col < tree[p].column; col++)
336 o << BAR_EW;
337 col++;
338 if (tree[p].replyor_next == -1)
339 o << CORNER_SW;
340 else o << TEE_WSE;
341 }
342 *w = tree[i].draw_next;
343
344 /* Continue drawing the other children */
345 for (p = *w; p != -1; p = tree[p].draw_next)
346 {
347 for (; col < tree[p].column; col++)
348 o << EMPTY_CELL;
349 col++;
350 o << BAR_NS;
351 }
352 }
353
draw_tree_row(ostream & o,int * h,Key row)354 void Threading::draw_tree_row(ostream& o, int* h, Key row)
355 {
356 my_service_draw_tree_row(o, &nodes[0], h, row);
357 }
358
my_service_draw_snippet(ESort::Reader * db,Threading::Node * tree,int p,int row,string & out,int num,const Config & cfg)359 int my_service_draw_snippet(
360 ESort::Reader* db,
361 Threading::Node* tree,
362 int p,
363 int row,
364 string& out,
365 int num,
366 const Config& cfg)
367 {
368 int col;
369 int c;
370 bool dangle_reply = false;
371
372 col = tree[p].column = tree[p].consumed;
373
374 if (row < 3)
375 {
376 out = tree[p].summary.load(db, cfg);
377 if (out != "") return -1;
378
379 for (c = tree[p].replyor_first; c != -1; c = tree[c].replyor_next)
380 {
381 tree[c].consumed = col;
382 col = my_service_draw_snippet(db, tree, c, row+1, out, num, cfg);
383 if (col == -1) return -1;
384 }
385
386 if (p+1 < num && tree[p+1].replyee == -1)
387 { // draw it as though it were a child
388 dangle_reply = true;
389 c = p+1;
390
391 tree[c].consumed = col;
392 col = my_service_draw_snippet(db, tree, c, row+1, out, num, cfg);
393 if (col == -1) return -1;
394 }
395 }
396
397 if ((tree[p].replyor_first == -1 && !dangle_reply) || row >= 3) col++;
398
399 return col;
400 }
401
my_service_pick_p(Threading::Node * tree,int root,int num)402 int my_service_pick_p(Threading::Node* tree, int root, int num)
403 {
404 int p = root;
405
406 // If we have nothing which is drawn below us move up an extra step
407 if (tree[p].replyor_first == -1 &&
408 (p+1 >= num || tree[p+1].replyee != -1))
409 { // we have no children and we have no dangling replyee
410 if (tree[p].replyee != -1)
411 p = tree[p].replyee;
412 else if (p != 0)
413 p = p - 1; // use the dangling replyee trick
414 }
415
416 // always move up at least one row if we can
417 if (tree[p].replyee != -1)
418 p = tree[p].replyee;
419 else if (p != 0)
420 p = p - 1; // use dangling replyee trick
421
422 return p;
423 }
424
draw_snippet(ESort::Reader * db,Key root,const Config & cfg)425 string Threading::draw_snippet(ESort::Reader* db, Key root, const Config& cfg)
426 {
427 Threading::Node* tree = &nodes[0];
428 string out;
429 my_service_draw_snippet(db, tree,
430 my_service_pick_p(tree, root, nodes.size()),
431 0, out, nodes.size(), cfg);
432 return out;
433 }
434
my_service_draw_snippet_row(ostream & o,Threading::Node * tree,int * draw_head,int row,int hl,int num)435 void my_service_draw_snippet_row(
436 ostream& o,
437 Threading::Node* tree,
438 int* draw_head,
439 int row,
440 int hl,
441 int num)
442 {
443 int p;
444 int c;
445 int col = 0;
446
447 /* First, draw the current row */
448 for (p = *draw_head; p != -1; p = tree[p].draw_next)
449 {
450 for (; col < tree[p].column; col++)
451 o << EMPTY_CELL;
452
453
454 my_service_tree_message_link(o, tree, p, hl);
455 col++;
456
457 /* Now, inject our children in place.
458 * Also, draw the stuff down to them.
459 */
460 for (c = tree[p].replyor_first; c != -1; c = tree[c].replyor_next)
461 {
462 *draw_head = c;
463 draw_head = &tree[c].draw_next;
464
465 if (c == tree[p].replyor_first)
466 continue;
467
468 for (; col < tree[c].column; col++)
469 o << BAR_EW;
470
471 if (tree[c].replyor_next == -1)
472 o << CORNER_SW;
473 else o << TEE_WSE;
474 col++;
475 }
476
477 // Check if the next message after p has no in-reply-to
478 if (p+1 < num && tree[p+1].replyee == -1)
479 { // draw it as though it were a child
480 *draw_head = p+1;
481 draw_head = &tree[p+1].draw_next;
482 }
483 }
484
485 /* Terminate the list */
486 *draw_head = -1;
487 }
488
draw_snippet_row(ostream & o,int * h,Key row,Key root)489 void Threading::draw_snippet_row(ostream& o, int* h, Key row, Key root)
490 {
491 Threading::Node* tree = &nodes[0];
492 if (*h == -2) *h = my_service_pick_p(tree, root, nodes.size());
493 my_service_draw_snippet_row(o, tree, h, row, root, nodes.size());
494 }
495
findprev(Key m,ESort::Reader * r,const Config & cfg,Summary & s)496 string Threading::findprev(Key m, ESort::Reader* r, const Config& cfg, Summary& s)
497 {
498 string ok;
499
500 Key i = m;
501 while (1)
502 {
503 if (i == 0)
504 {
505 s = nodes[m].summary;
506 return "";
507 }
508 --i;
509
510 if (!nodes[i].summary.loaded() &&
511 (ok = nodes[i].summary.load(r, cfg)) != "")
512 return ok;
513
514 if (!nodes[i].summary.deleted())
515 {
516 s = nodes[i].summary;
517 return "";
518 }
519 }
520 }
521
findnext(Key m,ESort::Reader * r,const Config & cfg,Summary & s)522 string Threading::findnext(Key m, ESort::Reader* r, const Config& cfg, Summary& s)
523 {
524 string ok;
525
526
527 Key i = m;
528 while (1)
529 {
530 ++i;
531 if (i == nodes.size())
532 {
533 s = nodes[m].summary;
534 return "";
535 }
536
537 if (!nodes[i].summary.loaded() &&
538 (ok = nodes[i].summary.load(r, cfg)) != "")
539 return ok;
540
541 if (!nodes[i].summary.deleted())
542 {
543 s = nodes[i].summary;
544 return "";
545 }
546 }
547 }
548