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
32 attr_reader :containers
34 ## ah, the joys of a multithreaded application with a class called
35 ## "Thread". i keep instantiating the wrong one...
36 raise "wrong Thread class, buddy!" if block_given?
44 def empty?; @containers.empty?; end
45 def empty!; @containers.clear; end
46 def drop c; @containers.delete(c) or raise "bad drop"; end
50 f.puts "=== start thread #{self} with #{@containers.length} trees ==="
51 @containers.each { |c| c.dump_recursive f }
52 f.puts "=== end thread ==="
55 ## yields each message, its depth, and its parent. the message yield
56 ## parameter can be a Message object, or :fake_root, or nil (no
57 ## message found but the presence of one deduced from other
59 def each fake_root=false
61 root = @containers.find_all { |c| !Message.subj_is_reply?(c) }.argmin { |c| c.date || 0 }
65 root.first_useful_descendant.each_with_stuff do |c, d, par|
66 yield c.message, d, (par ? par.message : nil)
68 elsif @containers.length > 1 && fake_root
70 yield :fake_root, 0, nil
73 @containers.each do |cont|
75 fud = cont.first_useful_descendant
76 fud.each_with_stuff do |c, d, par|
77 ## special case here: if we're an empty root that's already
78 ## been joined by a fake root, don't emit
79 yield c.message, d + adj, (par ? par.message : nil) unless
80 fake_root && c.message.nil? && root.nil? && c == fud
85 def first; each { |m, *o| return m if m }; nil; end
86 def dirty?; any? { |m, *o| m && m.dirty? }; end
87 def date; map { |m, *o| m.date if m }.compact.max; end
89 last_m, last_stuff = select { |m, *o| m && m.snippet && !m.snippet.empty? }.sort_by { |m, *o| m.date }.last
90 last_m ? last_m.snippet : ""
92 def authors; map { |m, *o| m.from if m }.compact.uniq; end
94 def apply_label t; each { |m, *o| m && m.add_label(t) }; end
95 def remove_label t; each { |m, *o| m && m.remove_label(t) }; end
97 def toggle_label label
107 def set_labels l; each { |m, *o| m && m.labels = l }; end
109 def has_label? t; any? { |m, *o| m && m.has_label?(t) }; end
110 def save index; each { |m, *o| m && m.save(index) }; end
112 def direct_participants
113 map { |m, *o| [m.from] + m.to if m }.flatten.compact.uniq
117 map { |m, *o| [m.from] + m.to + m.cc + m.bcc if m }.flatten.compact.uniq
120 def size; map { |m, *o| m ? 1 : 0 }.sum; end
121 def subj; argfind { |m, *o| m && m.subj }; end
123 map { |m, *o| m && m.labels }.flatten.compact.uniq.sort_by { |t| t.to_s }
126 each { |m, *o| m && m.labels = l.clone }
130 inject(nil) do |a, b|
137 b.date > a.date ? b : a
143 "<thread containing: #{@containers.join ', '}>"
147 ## recursive structure used internally to represent message trees as
148 ## described by reply-to: and references: headers.
150 ## the 'id' field is the same as the message id. but the message might
151 ## be empty, in the case that we represent a message that was referenced
152 ## by another message (as an ancestor) but never received.
154 attr_accessor :message, :parent, :children, :id, :thread
157 raise "non-String #{id.inspect}" unless id.is_a? String
159 @message, @parent, @thread = nil, nil, nil
163 def each_with_stuff parent=nil
164 yield self, 0, parent
165 @children.each do |c|
166 c.each_with_stuff(self) { |cc, d, par| yield cc, d + 1, par }
174 @parent && @parent.descendant_of?(o)
178 def == o; Container === o && id == o.id; end
180 def empty?; @message.nil?; end
181 def root?; @parent.nil?; end
182 def root; root? ? self : @parent.root; end
184 def first_useful_descendant
185 if empty? && @children.size == 1
186 @children.first.first_useful_descendant
194 @children.argfind { |c| c.find_attr attr }
199 def subj; find_attr :subj; end
200 def date; find_attr :date; end
202 def is_reply?; subj && Message.subject_is_reply?(subj); end
206 (@parent.nil? ? nil : "parent=#{@parent.id}"),
207 (@children.empty? ? nil : "children=#{@children.map { |c| c.id }.inspect}"),
208 ].compact.join(" ") + ">"
211 def dump_recursive f=$stdout, indent=0, root=true, parent=nil
212 raise "inconsistency" unless parent.nil? || parent.children.include?(self)
217 line = #"[#{useful? ? 'U' : ' '}] " +
219 "[#{thread}] #{@message.subj} " ##{@message.refs.inspect} / #{@message.replytos.inspect}"
224 f.puts "#{id} #{line}"#[0 .. (105 - indent)]
226 @children.each { |c| c.dump_recursive f, indent, false, self }
230 ## A set of threads (so a forest). Builds thread structures by reading
231 ## messages from an index.
233 ## If 'thread_by_subj' is true, puts messages with the same subject in
234 ## one thread, even if they don't reference each other. This is
235 ## helpful for crappy MUAs that don't set In-reply-to: or References:
236 ## headers, but means that messages may be threaded unnecessarily.
238 attr_reader :num_messages
239 bool_reader :thread_by_subj
241 def initialize index, thread_by_subj=true
244 ## map from message ids to container objects
245 @messages = SavingHash.new { |id| Container.new id }
246 ## map from subject strings or (or root message ids) to thread objects
247 @threads = SavingHash.new { Thread.new }
248 @thread_by_subj = thread_by_subj
251 def contains_id? id; @messages.member?(id) && !@messages[id].empty?; end
253 (c = @messages[m.id]) && c.root.thread
257 @threads.each { |k, v| @threads.delete(k) if v.empty? }
259 private :delete_cruft
261 def threads; delete_cruft; @threads.values; end
262 def size; delete_cruft; @threads.size; end
266 @threads.each do |s, t|
267 f.puts "**********************"
268 f.puts "** for subject #{s} **"
269 f.puts "**********************"
274 def link p, c, overwrite=false
275 if p == c || p.descendant_of?(c) || c.descendant_of?(p) # would create a loop
276 # puts "*** linking parent #{p} and child #{c} would create a loop"
280 if c.parent.nil? || overwrite
281 c.parent.children.delete c if overwrite && c.parent
293 return unless(c = @messages[mid])
295 c.parent.children.delete c if c.parent
302 ## load in (at most) num number of threads from the index
303 def load_n_threads num, opts={}
304 @index.each_id_by_date opts do |mid, builder|
306 next if contains_id? mid
309 load_thread_for_message m, :skip_killed => opts[:skip_killed], :load_deleted => opts[:load_deleted], :load_spam => opts[:load_spam]
310 yield size if block_given?
314 ## loads in all messages needed to thread m
315 ## may do nothing if m's thread is killed
316 def load_thread_for_message m, opts={}
317 good = @index.each_message_in_thread_for m, opts do |mid, builder|
318 next if contains_id? mid
319 add_message builder.call
321 add_message m if good
324 ## merges in a pre-loaded thread
326 raise "duplicate" if @threads.values.member? t
327 t.each { |m, *o| add_message m }
331 m.refs.any? { |ref_id| @messages.member? ref_id }
334 ## the heart of the threading code
335 def add_message message
336 el = @messages[message.id]
337 return if el.message # we've seen it before
342 ## link via references:
344 message.refs.each do |ref_id|
345 ref = @messages[ref_id]
346 link prev, ref if prev
349 link prev, el, true if prev
351 ## link via in-reply-to:
352 message.replytos.each do |ref_id|
353 ref = @messages[ref_id]
355 break # only do the first one
360 ## new root. need to drop old one and put this one in its place
361 if root != oldroot && oldroot.thread
362 oldroot.thread.drop oldroot
368 Message.normalize_subj root.subj
373 ## check to see if the subject is still the same (in the case
374 ## that we first added a child message with a different
377 unless @threads[key] == root.thread
380 @threads[key] << root
381 root.thread = @threads[key]
383 @threads[key] = root.thread
387 thread = @threads[key]