* [ANN] msgthr 1.2.2 - container-agnostic, non-recursive message
@ 2018-05-01 20:45 7% ` Eric Wong
0 siblings, 0 replies; 2+ results
From: Eric Wong @ 2018-05-01 20:45 UTC (permalink / raw)
To: ruby-talk, msgthr-public; +Cc: misc
Pure Ruby message threading based on the algorithm described by
JWZ in <https://www.jwz.org/doc/threading.html> and used in
countless mail and news readers; but with some features removed
and improved flexibility for non-mail/news usage.
* https://80x24.org/msgthr/README
* API: https://80x24.org/msgthr/rdoc/Msgthr.html
* public list: msgthr-public@80x24.org
* mail archives: https://80x24.org/msgthr-public/
* git clone https://80x24.org/msgthr.git
* follow releases: https://80x24.org/msgthr/NEWS.atom.xml
* follow all: https://80x24.org/msgthr-public/new.atom
* nntp://news.public-inbox.org/inbox.comp.lang.ruby.msgthr
Changes: fix missing loop check
This release fixes a missing loop check due to References
being out-of-order. This caused cyclic dependencies leading
to lost message roots.
A NEWS file is also bundled in the RubyGem for non-git users.
--
https://80x24.org/msgthr/README
^ permalink raw reply [relevance 7%]
* [PATCH] fix missing loop check
@ 2018-04-26 0:01 5% Eric Wong
0 siblings, 0 replies; 2+ results
From: Eric Wong @ 2018-04-26 0:01 UTC (permalink / raw)
To: msgthr-public
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.
---
lib/msgthr.rb | 2 +-
lib/msgthr/container.rb | 5 +++--
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
--
EW
^ permalink raw reply related [relevance 5%]
Results 1-2 of 2 | reverse | options above
-- pct% links below jump to the message on this page, permalinks otherwise --
2018-01-25 23:08 [ANN] msgthr 1.2.0 - container-agnostic, non-recursive message threading Eric Wong
2018-05-01 20:45 7% ` [ANN] msgthr 1.2.2 - container-agnostic, non-recursive message Eric Wong
2018-04-26 0:01 5% [PATCH] fix missing loop check Eric Wong
Code repositories for project(s) associated with this public inbox
https://80x24.org/msgthr.git/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).