1 ## Herein lies all the code responsible for threading messages. It's
2 ## basically an online version of the JWZ threading algorithm:
3 ## http://www.jwz.org/doc/threading.html
5 ## I didn't implement it for efficiency, but thanks to our search
6 ## engine backend, it's typically not applied to very many messages at
9 ## At the top level, we have a ThreadSet, which represents a set of
10 ## threads, e.g. a message folder or an inbox. Each ThreadSet contains
11 ## zero or more Threads. A Thread represents all the message related
12 ## to a particular subject. Each Thread has one or more Containers. A
13 ## Container is a recursive structure that holds the message tree as
14 ## determined by the references: and in-reply-to: headers. Each
15 ## Container holds zero or one messages. In the case of zero messages,
16 ## it means we've seen a reference to the message but haven't (yet)
17 ## seen the message itself.
19 ## A Thread can have multiple top-level Containers if we decide to
20 ## group them together independent of tree structure, typically if
21 ## (e.g. due to someone using a primitive MUA) the messages have the
22 ## same subject but we don't have evidence from in-reply-to: or
23 ## references: headers. In this case Thread#each can optionally yield
24 ## a faked root object tying them all together into one tree
34 attr_reader :containers
36 ## ah, the joys of a multithreaded application with a class called
37 ## "Thread". i keep instantiating the wrong one...
38 raise "wrong Thread class, buddy!" if block_given?
46 def empty?; @containers.empty?; end
47 def empty!; @containers.clear; end
48 def drop c; @containers.delete(c) or raise "bad drop"; end
52 f.puts "=== start thread with #{@containers.length} trees ==="
53 @containers.each { |c| c.dump_recursive f; f.puts }
54 f.puts "=== end thread ==="
57 ## yields each message, its depth, and its parent. the message yield
58 ## parameter can be a Message object, or :fake_root, or nil (no
59 ## message found but the presence of one deduced from other
61 def each fake_root=false
63 root = @containers.find_all { |c| c.message && !Message.subj_is_reply?(c.message.subj) }.argmin { |c| c.date }
67 root.first_useful_descendant.each_with_stuff do |c, d, par|
68 yield c.message, d, (par ? par.message : nil)
70 elsif @containers.length > 1 && fake_root
72 yield :fake_root, 0, nil
75 @containers.each do |cont|
77 fud = cont.first_useful_descendant
78 fud.each_with_stuff do |c, d, par|
79 ## special case here: if we're an empty root that's already
80 ## been joined by a fake root, don't emit
81 yield c.message, d + adj, (par ? par.message : nil) unless
82 fake_root && c.message.nil? && root.nil? && c == fud
87 def first; each { |m, *o| return m if m }; nil; end
88 def dirty?; any? { |m, *o| m && m.dirty? }; end
89 def date; map { |m, *o| m.date if m }.compact.max; end
91 with_snippets = select { |m, *o| m && m.snippet && !m.snippet.empty? }
92 first_unread, * = with_snippets.select { |m, *o| m.has_label?(:unread) }.sort_by { |m, *o| m.date }.first
93 return first_unread.snippet if first_unread
94 last_read, * = with_snippets.sort_by { |m, *o| m.date }.last
95 return last_read.snippet if last_read
98 def authors; map { |m, *o| m.from if m }.compact.uniq; end
100 def apply_label t; each { |m, *o| m && m.add_label(t) }; end
101 def remove_label t; each { |m, *o| m && m.remove_label(t) }; end
103 def toggle_label label
113 def set_labels l; each { |m, *o| m && m.labels = l }; end
114 def has_label? t; any? { |m, *o| m && m.has_label?(t) }; end
115 def save_state index; each { |m, *o| m && m.save_state(index) }; end
117 def direct_participants
118 map { |m, *o| [m.from] + m.to if m }.flatten.compact.uniq
122 map { |m, *o| [m.from] + m.to + m.cc + m.bcc if m }.flatten.compact.uniq
125 def size; map { |m, *o| m ? 1 : 0 }.sum; end
126 def subj; argfind { |m, *o| m && m.subj }; end
127 def labels; inject(Set.new) { |s, (m, *o)| m ? s | m.labels : s } end
129 raise ArgumentError, "not a set" unless l.is_a?(Set)
130 each { |m, *o| m && m.labels = l.dup }
134 inject(nil) do |a, b|
141 b.date > a.date ? b : a
147 "<thread containing: #{@containers.join ', '}>"
151 ## recursive structure used internally to represent message trees as
152 ## described by reply-to: and references: headers.
154 ## the 'id' field is the same as the message id. but the message might
155 ## be empty, in the case that we represent a message that was referenced
156 ## by another message (as an ancestor) but never received.
158 attr_accessor :message, :parent, :children, :id, :thread
161 raise "non-String #{id.inspect}" unless id.is_a? String
163 @message, @parent, @thread = nil, nil, nil
167 def each_with_stuff parent=nil
168 yield self, 0, parent
169 @children.each do |c|
170 c.each_with_stuff(self) { |cc, d, par| yield cc, d + 1, par }
178 @parent && @parent.descendant_of?(o)
182 def == o; Container === o && id == o.id; end
184 def empty?; @message.nil?; end
185 def root?; @parent.nil?; end
186 def root; root? ? self : @parent.root; end
188 ## skip over any containers which are empty and have only one child. we use
189 ## this make the threaded display a little nicer, and only stick in the
190 ## "missing message" line when it's graphically necessary, i.e. when the
191 ## missing message has more than one descendent.
192 def first_useful_descendant
193 if empty? && @children.size == 1
194 @children.first.first_useful_descendant
202 @children.argfind { |c| c.find_attr attr }
207 def subj; find_attr :subj; end
208 def date; find_attr :date; end
210 def is_reply?; subj && Message.subj_is_reply?(subj); end
214 (@parent.nil? ? nil : "parent=#{@parent.id}"),
215 (@children.empty? ? nil : "children=#{@children.map { |c| c.id }.inspect}"),
216 ].compact.join(" ") + ">"
219 def dump_recursive f=$stdout, indent=0, root=true, parent=nil
220 raise "inconsistency" unless parent.nil? || parent.children.include?(self)
225 line = "[#{thread.nil? ? ' ' : '*'}] " + #"[#{useful? ? 'U' : ' '}] " +
227 message.subj ##{@message.refs.inspect} / #{@message.replytos.inspect}"
232 f.puts "#{id} #{line}"#[0 .. (105 - indent)]
234 @children.each { |c| c.dump_recursive f, indent, false, self }
238 ## A set of threads, so a forest. Is integrated with the index and
239 ## builds thread structures by reading messages from it.
241 ## If 'thread_by_subj' is true, puts messages with the same subject in
242 ## one thread, even if they don't reference each other. This is
243 ## helpful for crappy MUAs that don't set In-reply-to: or References:
244 ## headers, but means that messages may be threaded unnecessarily.
246 ## The following invariants are maintained: every Thread has at least one
247 ## Container tree, and every Container tree has at least one Message.
249 attr_reader :num_messages
250 bool_reader :thread_by_subj
252 def initialize index, thread_by_subj=true
255 ## map from message ids to container objects
256 @messages = SavingHash.new { |id| Container.new id }
257 ## map from subject strings or (or root message ids) to thread objects
258 @threads = SavingHash.new { Thread.new }
259 @thread_by_subj = thread_by_subj
262 def thread_for_id mid; @messages.member?(mid) && @messages[mid].root.thread end
263 def contains_id? id; @messages.member?(id) && !@messages[id].empty? end
264 def thread_for m; thread_for_id m.id end
265 def contains? m; contains_id? m.id end
267 def threads; @threads.values end
268 def size; @threads.size end
271 @threads.each do |s, t|
272 f.puts "**********************"
273 f.puts "** for subject #{s} **"
274 f.puts "**********************"
279 ## link two containers
280 def link p, c, overwrite=false
281 if p == c || p.descendant_of?(c) || c.descendant_of?(p) # would create a loop
282 #puts "*** linking parent #{p.id} and child #{c.id} would create a loop"
286 #puts "in link for #{p.id} to #{c.id}, perform? #{c.parent.nil?} || #{overwrite}"
288 return unless c.parent.nil? || overwrite
293 ## if the child was previously a top-level container, it now ain't,
294 ## so ditch our thread and kill it if necessary
299 def remove_container c
300 c.parent.children.delete c if c.parent # remove from tree
302 private :remove_container
304 def prune_thread_of c
305 return unless c.thread
307 @threads.delete_if { |k, v| v == c.thread } if c.thread.empty?
310 private :prune_thread_of
313 return unless @messages.member?(mid)
319 def remove_thread_containing_id mid
320 return unless @messages.member?(mid)
323 @threads.delete_if { |key, thread| t == thread }
326 ## load in (at most) num number of threads from the index
327 def load_n_threads num, opts={}
328 @index.each_id_by_date opts do |mid, builder|
329 break if size >= num unless num == -1
330 next if contains_id? mid
333 load_thread_for_message m, :skip_killed => opts[:skip_killed], :load_deleted => opts[:load_deleted], :load_spam => opts[:load_spam]
334 yield size if block_given?
338 ## loads in all messages needed to thread m
339 ## may do nothing if m's thread is killed
340 def load_thread_for_message m, opts={}
341 good = @index.each_message_in_thread_for m, opts do |mid, builder|
342 next if contains_id? mid
343 add_message builder.call
345 add_message m if good
348 ## merges in a pre-loaded thread
350 raise "duplicate" if @threads.values.member? t
351 t.each { |m, *o| add_message m }
354 ## merges two threads together. both must be members of this threadset.
355 ## does its best, heuristically, to determine which is the parent.
356 def join_threads threads
357 return if threads.size < 2
359 containers = threads.map do |t|
360 c = @messages.member?(t.first.id) ? @messages[t.first.id] : nil
361 raise "not in threadset: #{t.first.id}" unless c && c.message
365 ## use subject headers heuristically
366 parent = containers.find { |c| !c.is_reply? }
368 ## no thread was rooted by a non-reply, so make a fake parent
369 parent ||= @messages["joining-ref-" + containers.map { |c| c.id }.join("-")]
371 containers.each do |c|
373 c.message.add_ref parent.id
381 m.refs.any? { |ref_id| @messages.member? ref_id }
384 ## the heart of the threading code
385 def add_message message
386 el = @messages[message.id]
387 return if el.message # we've seen it before
389 #puts "adding: #{message.id}, refs #{message.refs.inspect}"
394 ## link via references:
395 (message.refs + [el.id]).inject(nil) do |prev, ref_id|
396 ref = @messages[ref_id]
397 link prev, ref if prev
401 ## link via in-reply-to:
402 message.replytos.each do |ref_id|
403 ref = @messages[ref_id]
405 break # only do the first one
411 Message.normalize_subj root.subj
416 ## check to see if the subject is still the same (in the case
417 ## that we first added a child message with a different
420 if @threads.member?(key) && @threads[key] != root.thread
424 thread = @threads[key]