diff options
| author | Eric Wong <e@80x24.org> | 2018-04-26 00:01:56 +0000 |
|---|---|---|
| committer | Eric Wong <e@80x24.org> | 2018-04-26 00:02:24 +0000 |
| commit | 370d1e01ac9a81c10aa1cc3dea256337f94321c9 (patch) | |
| tree | ca724eb755de8d54aa9eac56cc52b7db3013aa05 | |
| parent | 341e3ac6a07358c76b4e0690567949063cc70497 (diff) | |
| download | msgthr-370d1e01ac9a81c10aa1cc3dea256337f94321c9.tar.gz | |
We failed to detect cyclic dependencies, leading to lost thread roots. In this Ruby version, I also screwed up the `seen' hash check in a misguided effort to avoid an extra hash lookup. The same algorithm was recently fixed in public-inbox: https://public-inbox.org/meta/20180425085249.14974-1-e@80x24.org/ Summarizing what happened with public-inbox: this algorithm can still be thrown off when the References: order presented to us is wrong, so sorting messages by age before feeding to Msgthr#add can improve the results. Regardless of ordering, messages should not become "lost" by the algorithm.
| -rw-r--r-- | lib/msgthr.rb | 2 | ||||
| -rw-r--r-- | lib/msgthr/container.rb | 5 | ||||
| -rw-r--r-- | test/test_msgthr.rb | 30 |
3 files changed, 34 insertions, 3 deletions
diff --git a/lib/msgthr.rb b/lib/msgthr.rb index bf4b14e..8619c62 100644 --- a/lib/msgthr.rb +++ b/lib/msgthr.rb @@ -183,7 +183,7 @@ class Msgthr end # set parent of this message to be the last element in refs - if prev + if prev && !cur.has_descendent(prev) prev.add_child(cur) yield(prev, cur) if block_given? end diff --git a/lib/msgthr/container.rb b/lib/msgthr/container.rb index fbff719..256033b 100644 --- a/lib/msgthr/container.rb +++ b/lib/msgthr/container.rb @@ -64,9 +64,10 @@ class Msgthr::Container end def has_descendent(child) # :nodoc: - seen = Hash.new(0) + seen = {} while child - return true if self == child || (seen[child] += 1) != 0 + return true if self == child || seen[child] + seen[child] = true child = child.parent end false diff --git a/test/test_msgthr.rb b/test/test_msgthr.rb index ee04d54..3d70d35 100644 --- a/test/test_msgthr.rb +++ b/test/test_msgthr.rb @@ -144,4 +144,34 @@ EOF assert_equal threads[2][0], '2' end + def test_no_lost_root + ids = [ + [ 8, [] ], + [ 7, [8] ], + [ 6, [8, 7] ], + [ 3, [6, 7, 8] ], + [ 2, [6, 7, 8, 3] ], + [ 10, [8, 7, 6] ], + [ 9, [6, 3] ], + [ 5, [6, 7, 8, 3, 2] ], + [ 4, [2, 3] ], + [ 1, [2, 3, 4] ], + [ 'a', ], + [ 'b', ['a'] ], + ] + [ [ :forward, ids, 2 ], + [ :backwards, ids.reverse, 3 ], + [ :shuffle, ids.shuffle, nil ], + ].each do |desc,msgs,exp| + thr = Msgthr.new + msgs.each { |id| thr.add(id[0], id[1], id[0]) } + seen0 = nr = 0 + thr.walk_thread do |level, _, _| + seen0 += 1 if level == 0 + nr += 1 + end + assert_equal nr, msgs.size, 'no lost messages' + assert_equal exp, seen0, "single root #{desc}" if exp + end + end end |