1 ## Herein is all the code responsible for threading messages. I use an
2 ## online version of the JWZ threading algorithm:
3 ## http://www.jwz.org/doc/threading.html
5 ## I certainly didn't implement it for efficiency, but thanks to our
6 ## search engine backend, it's typically not applied to very many
9 ## At the top level, we have a ThreadSet. A ThreadSet represents a set
10 ## of threads, e.g. a message folder or an inbox. Each ThreadSet
11 ## contains zero or more Threads. A Thread represents all the message
12 ## related to a particular subject. Each Thread has one or more
13 ## Containers. A Container is a recursive structure that holds the
14 ## tree structure as determined by the references: and in-reply-to:
15 ## headers. A Thread with multiple Containers occurs if they have the
16 ## same subject, but (most likely due to someone using a primitive
17 ## MUA) we don't have evidence from in-reply-to: or references:
18 ## headers, only subject: (and thus our tree is probably broken). A
19 ## Container holds zero or one message. In the case of no message, it
20 ## means we've seen a reference to the message but haven't seen the
21 ## message itself (yet).
28 attr_reader :containers
30 ## ah, the joys of a multithreaded application with a class called
31 ## "Thread". i keep instantiating the wrong one...
32 raise "wrong Thread class, buddy!" if block_given?
40 def empty?; @containers.empty?; end
43 raise "bad drop" unless @containers.member? c
48 puts "=== start thread #{self} with #{@containers.length} trees ==="
49 @containers.each { |c| c.dump_recursive }
50 puts "=== end thread ==="
53 ## yields each message, its depth, and its parent. note that the
54 ## message can be a Message object, or :fake_root, or nil.
55 def each fake_root=false
57 root = @containers.find_all { |c| !Message.subj_is_reply?(c) }.argmin { |c| c.date }
61 root.first_useful_descendant.each_with_stuff do |c, d, par|
62 yield c.message, d, (par ? par.message : nil)
64 elsif @containers.length > 1 && fake_root
66 yield :fake_root, 0, nil
69 @containers.each do |cont|
71 fud = cont.first_useful_descendant
72 fud.each_with_stuff do |c, d, par|
73 ## special case here: if we're an empty root that's already
74 ## been joined by a fake root, don't emit
75 yield c.message, d + adj, (par ? par.message : nil) unless
76 fake_root && c.message.nil? && root.nil? && c == fud
81 def first; each { |m, *o| return m if m }; nil; end
82 def dirty?; any? { |m, *o| m && m.dirty? }; end
83 def date; map { |m, *o| m.date if m }.compact.max; end
84 def snippet; argfind { |m, *o| m && m.snippet }; end
85 def authors; map { |m, *o| m.from if m }.compact.uniq; end
87 def apply_label t; each { |m, *o| m && m.add_label(t) }; end
89 each { |m, *o| m && m.remove_label(t) }
92 def toggle_label label
102 def set_labels l; each { |m, *o| m && m.labels = l }; end
104 def has_label? t; any? { |m, *o| m && m.has_label?(t) }; end
105 def dirty?; any? { |m, *o| m && m.dirty? }; end
106 def save index; each { |m, *o| m && m.save(index) }; end
108 def direct_participants
109 map { |m, *o| [m.from] + m.to if m }.flatten.compact.uniq
113 map { |m, *o| [m.from] + m.to + m.cc + m.bcc if m }.flatten.compact.uniq
116 def size; map { |m, *o| m ? 1 : 0 }.sum; end
117 def subj; argfind { |m, *o| m && m.subj }; end
119 map { |m, *o| m && m.labels }.flatten.compact.uniq.sort_by { |t| t.to_s }
122 each { |m, *o| m && m.labels = l.clone }
126 inject(nil) do |a, b|
133 b.date > a.date ? b : a
139 "<thread containing: #{@containers.join ', '}>"
143 ## recursive structure used internally to represent message trees as
144 ## described by reply-to: and references: headers.
146 ## the 'id' field is the same as the message id. but the message might
147 ## be empty, in the case that we represent a message that was referenced
148 ## by another message (as an ancestor) but never received.
150 attr_accessor :message, :parent, :children, :id, :thread
153 raise "non-String #{id.inspect}" unless id.is_a? String
155 @message, @parent, @thread = nil, nil, nil
159 def each_with_stuff parent=nil
160 yield self, 0, parent
161 @children.each do |c|
162 c.each_with_stuff(self) { |cc, d, par| yield cc, d + 1, par }
170 @parent && @parent.descendant_of?(o)
174 def == o; Container === o && id == o.id; end
176 def empty?; @message.nil?; end
177 def root?; @parent.nil?; end
178 def root; root? ? self : @parent.root; end
180 def first_useful_descendant
181 if empty? && @children.size == 1
182 @children.first.first_useful_descendant
190 @children.argfind { |c| c.find_attr attr }
195 def subj; find_attr :subj; end
196 def date; find_attr :date; end
198 def is_reply?; subj && Message.subject_is_reply?(subj); end
202 (@parent.nil? ? nil : "parent=#{@parent.id}"),
203 (@children.empty? ? nil : "children=#{@children.map { |c| c.id }.inspect}"),
204 ].compact.join(" ") + ">"
207 def dump_recursive indent=0, root=true, parent=nil
208 raise "inconsistency" unless parent.nil? || parent.children.include?(self)
213 line = #"[#{useful? ? 'U' : ' '}] " +
215 "[#{thread}] #{@message.subj} " ##{@message.refs.inspect} / #{@message.replytos.inspect}"
220 puts "#{id} #{line}"#[0 .. (105 - indent)]
222 @children.each { |c| c.dump_recursive indent, false, self }
226 ## a set of threads (so a forest). builds the thread structures by
227 ## reading messages from an index.
229 attr_reader :num_messages
234 @messages = {} ## map from message ids to container objects
235 @subj_thread = {} ## map from subject strings to thread objects
238 def contains_id? id; @messages.member?(id) && !@messages[id].empty?; end
240 (c = @messages[m.id]) && c.root.thread
244 @subj_thread.each { |k, v| @subj_thread.delete(k) if v.empty? || v.subj != k }
246 private :delete_cruft
248 def threads; delete_cruft; @subj_thread.values; end
249 def size; delete_cruft; @subj_thread.size; end
252 @subj_thread.each do |s, t|
253 puts "**********************"
254 puts "** for subject #{s} **"
255 puts "**********************"
260 def link p, c, overwrite=false
261 if p == c || p.descendant_of?(c) || c.descendant_of?(p) # would create a loop
262 # puts "*** linking parent #{p} and child #{c} would create a loop"
266 if c.parent.nil? || overwrite
267 c.parent.children.delete c if overwrite && c.parent
279 return unless(c = @messages[mid])
281 c.parent.children.delete c if c.parent
288 ## load in (at most) num number of threads from the index
289 def load_n_threads num, opts={}
290 @index.each_id_by_date opts do |mid, builder|
292 next if contains_id? mid
296 load_thread_for_message m
297 yield @subj_thread.size if block_given?
301 ## loads in all messages needed to thread m
302 def load_thread_for_message m
303 @index.each_message_in_thread_for m, :limit => 100 do |mid, builder|
304 next if contains_id? mid
305 add_message builder.call
310 m.refs.any? { |ref_id| @messages[ref_id] }
313 ## an "online" version of the jwz threading algorithm.
314 def add_message message
316 el = (@messages[id] ||= Container.new id)
317 return if @messages[id].message # we've seen it before
322 ## link via references:
324 message.refs.each do |ref_id|
325 raise "non-String ref id #{ref_id.inspect} (full: #{message.refs.inspect})" unless ref_id.is_a?(String)
326 ref = (@messages[ref_id] ||= Container.new ref_id)
327 link prev, ref if prev
330 link prev, el, true if prev
332 ## link via in-reply-to:
333 message.replytos.each do |ref_id|
334 ref = (@messages[ref_id] ||= Container.new ref_id)
336 break # only do the first one
339 ## update subject grouping
341 # puts "> have #{el}, root #{root}, oldroot #{oldroot}"
346 ## check to see if the subject is still the same (in the case
347 ## that we first added a child message with a different
350 ## this code is duplicated below. sorry! TODO: refactor
351 s = Message.normalize_subj(root.subj)
352 unless @subj_thread[s] == root.thread
353 ## Redwood::log "[1] moving thread to new subject #{root.subj}"
355 @subj_thread[s] << root
356 root.thread = @subj_thread[s]
358 @subj_thread[s] = root.thread
363 ## to disable subject grouping, use the next line instead
364 ## (and the same for below)
365 #Redwood::log "[1] for #{root}, subject #{Message.normalize_subj(root.subj)} has #{@subj_thread[Message.normalize_subj(root.subj)] ? 'a' : 'no'} thread"
366 thread = (@subj_thread[Message.normalize_subj(root.subj)] ||= Thread.new)
367 #thread = (@subj_thread[root.id] ||= Thread.new)
371 # Redwood::log "[1] added #{root} to #{thread}"
375 ## new root. need to drop old one and put this one in its place
376 oldroot.thread.drop oldroot
381 ## check to see if the subject is still the same (in the case
382 ## that we first added a child message with a different
384 s = Message.normalize_subj(root.subj)
385 unless @subj_thread[s] == root.thread
386 # Redwood::log "[2] moving thread to new subject #{root.subj}"
388 @subj_thread[s] << root
389 root.thread = @subj_thread[s]
391 @subj_thread[s] = root.thread
396 ## to disable subject grouping, use the next line instead
397 ## (and the same above)
399 ## this code is duplicated above. sorry! TODO: refactor
400 # Redwood::log "[2] for #{root}, subject '#{Message.normalize_subj(root.subj)}' has #{@subj_thread[Message.normalize_subj(root.subj)] ? 'a' : 'no'} thread"
402 thread = (@subj_thread[Message.normalize_subj(root.subj)] ||= Thread.new)
403 #thread = (@subj_thread[root.id] ||= Thread.new)
407 # Redwood::log "[2] added #{root} to #{thread}"