msgthr user+dev discussion/patches/pulls/bugs/help
 help / color / Atom feed
From: Eric Wong <e@80x24.org>
To: msgthr-public@80x24.org
Subject: [PATCH] fix missing loop check
Date: Thu, 26 Apr 2018 00:01:56 +0000
Message-ID: <20180426000156.10184-1-e@80x24.org> (raw)

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


                 reply index

Thread overview: [no followups] expand[flat|nested]  mbox.gz  Atom feed

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: https://80x24.org/msgthr/README

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20180426000156.10184-1-e@80x24.org \
    --to=e@80x24.org \
    --cc=msgthr-public@80x24.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

msgthr user+dev discussion/patches/pulls/bugs/help

Archives are clonable: git clone --mirror https://80x24.org/msgthr-public

Newsgroups are available over NNTP:
	nntp://news.public-inbox.org/inbox.comp.lang.ruby.msgthr
	nntp://ou63pmih66umazou.onion/inbox.comp.lang.ruby.msgthr

 note: .onion URLs require Tor: https://www.torproject.org/

AGPL code for this site: git clone https://public-inbox.org/ public-inbox