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 save index; each { |m, *o| m && m.save(index) }; end
107 def direct_participants
108 map { |m, *o| [m.from] + m.to if m }.flatten.compact.uniq
112 map { |m, *o| [m.from] + m.to + m.cc + m.bcc if m }.flatten.compact.uniq
115 def size; map { |m, *o| m ? 1 : 0 }.sum; end
116 def subj; argfind { |m, *o| m && m.subj }; end
118 map { |m, *o| m && m.labels }.flatten.compact.uniq.sort_by { |t| t.to_s }
121 each { |m, *o| m && m.labels = l.clone }
125 inject(nil) do |a, b|
132 b.date > a.date ? b : a
138 "<thread containing: #{@containers.join ', '}>"
142 ## recursive structure used internally to represent message trees as
143 ## described by reply-to: and references: headers.
145 ## the 'id' field is the same as the message id. but the message might
146 ## be empty, in the case that we represent a message that was referenced
147 ## by another message (as an ancestor) but never received.
149 attr_accessor :message, :parent, :children, :id, :thread
152 raise "non-String #{id.inspect}" unless id.is_a? String
154 @message, @parent, @thread = nil, nil, nil
158 def each_with_stuff parent=nil
159 yield self, 0, parent
160 @children.each do |c|
161 c.each_with_stuff(self) { |cc, d, par| yield cc, d + 1, par }
169 @parent && @parent.descendant_of?(o)
173 def == o; Container === o && id == o.id; end
175 def empty?; @message.nil?; end
176 def root?; @parent.nil?; end
177 def root; root? ? self : @parent.root; end
179 def first_useful_descendant
180 if empty? && @children.size == 1
181 @children.first.first_useful_descendant
189 @children.argfind { |c| c.find_attr attr }
194 def subj; find_attr :subj; end
195 def date; find_attr :date; end
197 def is_reply?; subj && Message.subject_is_reply?(subj); end
201 (@parent.nil? ? nil : "parent=#{@parent.id}"),
202 (@children.empty? ? nil : "children=#{@children.map { |c| c.id }.inspect}"),
203 ].compact.join(" ") + ">"
206 def dump_recursive indent=0, root=true, parent=nil
207 raise "inconsistency" unless parent.nil? || parent.children.include?(self)
212 line = #"[#{useful? ? 'U' : ' '}] " +
214 "[#{thread}] #{@message.subj} " ##{@message.refs.inspect} / #{@message.replytos.inspect}"
219 puts "#{id} #{line}"#[0 .. (105 - indent)]
221 @children.each { |c| c.dump_recursive indent, false, self }
225 ## a set of threads (so a forest). builds the thread structures by
226 ## reading messages from an index.
228 attr_reader :num_messages
233 @messages = {} ## map from message ids to container objects
234 @subj_thread = {} ## map from subject strings to thread objects
237 def contains_id? id; @messages.member?(id) && !@messages[id].empty?; end
239 (c = @messages[m.id]) && c.root.thread
243 @subj_thread.each { |k, v| @subj_thread.delete(k) if v.empty? || v.subj != k }
245 private :delete_cruft
247 def threads; delete_cruft; @subj_thread.values; end
248 def size; delete_cruft; @subj_thread.size; end
251 @subj_thread.each do |s, t|
252 puts "**********************"
253 puts "** for subject #{s} **"
254 puts "**********************"
259 def link p, c, overwrite=false
260 if p == c || p.descendant_of?(c) || c.descendant_of?(p) # would create a loop
261 # puts "*** linking parent #{p} and child #{c} would create a loop"
265 if c.parent.nil? || overwrite
266 c.parent.children.delete c if overwrite && c.parent
278 return unless(c = @messages[mid])
280 c.parent.children.delete c if c.parent
287 ## load in (at most) num number of threads from the index
288 def load_n_threads num, opts={}
289 @index.each_id_by_date opts do |mid, builder|
291 next if contains_id? mid
295 load_thread_for_message m
296 yield @subj_thread.size if block_given?
300 ## loads in all messages needed to thread m
301 def load_thread_for_message m
302 @index.each_message_in_thread_for m, :limit => 100 do |mid, builder|
303 next if contains_id? mid
304 add_message builder.call
309 m.refs.any? { |ref_id| @messages[ref_id] }
312 ## an "online" version of the jwz threading algorithm.
313 def add_message message
315 el = (@messages[id] ||= Container.new id)
316 return if @messages[id].message # we've seen it before
321 ## link via references:
323 message.refs.each do |ref_id|
324 raise "non-String ref id #{ref_id.inspect} (full: #{message.refs.inspect})" unless ref_id.is_a?(String)
325 ref = (@messages[ref_id] ||= Container.new ref_id)
326 link prev, ref if prev
329 link prev, el, true if prev
331 ## link via in-reply-to:
332 message.replytos.each do |ref_id|
333 ref = (@messages[ref_id] ||= Container.new ref_id)
335 break # only do the first one
338 ## update subject grouping
340 # puts "> have #{el}, root #{root}, oldroot #{oldroot}"
345 ## check to see if the subject is still the same (in the case
346 ## that we first added a child message with a different
349 ## this code is duplicated below. sorry! TODO: refactor
350 s = Message.normalize_subj(root.subj)
351 unless @subj_thread[s] == root.thread
352 ## Redwood::log "[1] moving thread to new subject #{root.subj}"
354 @subj_thread[s] << root
355 root.thread = @subj_thread[s]
357 @subj_thread[s] = root.thread
362 ## to disable subject grouping, use the next line instead
363 ## (and the same for below)
364 #Redwood::log "[1] for #{root}, subject #{Message.normalize_subj(root.subj)} has #{@subj_thread[Message.normalize_subj(root.subj)] ? 'a' : 'no'} thread"
365 thread = (@subj_thread[Message.normalize_subj(root.subj)] ||= Thread.new)
366 #thread = (@subj_thread[root.id] ||= Thread.new)
370 # Redwood::log "[1] added #{root} to #{thread}"
374 ## new root. need to drop old one and put this one in its place
375 oldroot.thread.drop oldroot
380 ## check to see if the subject is still the same (in the case
381 ## that we first added a child message with a different
383 s = Message.normalize_subj(root.subj)
384 unless @subj_thread[s] == root.thread
385 # Redwood::log "[2] moving thread to new subject #{root.subj}"
387 @subj_thread[s] << root
388 root.thread = @subj_thread[s]
390 @subj_thread[s] = root.thread
395 ## to disable subject grouping, use the next line instead
396 ## (and the same above)
398 ## this code is duplicated above. sorry! TODO: refactor
399 # Redwood::log "[2] for #{root}, subject '#{Message.normalize_subj(root.subj)}' has #{@subj_thread[Message.normalize_subj(root.subj)] ? 'a' : 'no'} thread"
401 thread = (@subj_thread[Message.normalize_subj(root.subj)] ||= Thread.new)
402 #thread = (@subj_thread[root.id] ||= Thread.new)
406 # Redwood::log "[2] added #{root} to #{thread}"