thread: prevent hidden threads in /$INBOX/ landing page

In retrospect, the loop prevention done by our indexer is not
always sufficient since it can have an improperly sorted
or incomplete References headers.

This bug was triggered multiple bracketed Message-IDs in an
In-Reply-To: header (not References) where the Message-IDs were
in non-chronological order when somebody tried to reply to
different leafs of a thread with a single message.

So we must check for descendents before blindly trying to
use the last one.

Fixes: c6a8fdf71e2c336f ("thread: last Reference always wins")

2 files changed, 68 insertions, 24 deletions

diff --git a/lib/PublicInbox/SearchThread.pm b/lib/PublicInbox/SearchThread.pm
index 1d250b46..450a06f4 100644
--- a/lib/PublicInbox/SearchThread.pm
+++ b/lib/PublicInbox/SearchThread.pm
@@ -76,7 +76,9 @@ sub _add_message ($$) {
 
         # C. Set the parent of this message to be the last element in
         # References.
-        $prev->add_child($this) if defined $prev;
+        if (defined $prev && !$this->has_descendent($prev)) { # would loop
+                $prev->add_child($this);
+        }
 }
 
 package PublicInbox::SearchThread::Msg;
diff --git a/t/thread-cycle.t b/t/thread-cycle.t
index 7d85909f..9e915a12 100644
--- a/t/thread-cycle.t
+++ b/t/thread-cycle.t
@@ -11,18 +11,25 @@ my $mt = eval {
         $Mail::Thread::nosubject = 1;
         $Mail::Thread::noprune = 1;
 };
-my @check;
-my @msgs = map {
-        my $msg = $_;
-        $msg->{references} =~ s/\s+/ /sg if $msg->{references};
-        my $simple = Email::Simple->create(header => [
-                'Message-Id' => "<$msg->{mid}>",
-                'References' => $msg->{references},
-        ]);
-        push @check, $simple;
-        bless $msg, 'PublicInbox::SearchMsg'
-} (
 
+sub make_objs {
+        my @simples;
+        my $n = 0;
+        my @msgs = map {
+                my $msg = $_;
+                $msg->{ds} ||= ++$n;
+                $msg->{references} =~ s/\s+/ /sg if $msg->{references};
+                my $simple = Email::Simple->create(header => [
+                        'Message-ID' => "<$msg->{mid}>",
+                        'References' => $msg->{references},
+                ]);
+                push @simples, $simple;
+                bless $msg, 'PublicInbox::SearchMsg'
+        } @_;
+        (\@simples, \@msgs);
+}
+
+my ($simples, $smsgs) = make_objs(
 # data from t/testbox-6 in Mail::Thread 2.55:
         { mid => '20021124145312.GA1759@nlin.net' },
         { mid => 'slrnau448m.7l4.markj+0111@cloaked.freeserve.co.uk',
@@ -50,23 +57,42 @@ my @msgs = map {
         }
 );
 
-my $st = thread_to_s(\@msgs);
+my $st = thread_to_s($smsgs);
 
 SKIP: {
         skip 'Mail::Thread missing', 1 unless $mt;
-        $mt = Mail::Thread->new(@check);
-        $mt->thread;
-        $mt->order(sub { sort { $a->messageid cmp $b->messageid } @_ });
-        my $check = '';
+        check_mt($st, $simples, 'Mail::Thread output matches');
+}
 
-        my @q = map { (0, $_) } $mt->rootset;
-        while (@q) {
-                my $level = shift @q;
-                my $node = shift @q or next;
-                $check .= (" "x$level) . $node->messageid . "\n";
-                unshift @q, $level + 1, $node->child, $level, $node->next;
+my @backwards = (
+        { mid => 1, references => '<2> <3> <4>' },
+        { mid => 4, references => '<2> <3>' },
+        { mid => 5, references => '<6> <7> <8> <3> <2>' },
+        { mid => 9, references => '<6> <3>' },
+        { mid => 10, references => '<8> <7> <6>' },
+        { mid => 2, references => '<6> <7> <8> <3>' },
+        { mid => 3, references => '<6> <7> <8>' },
+        { mid => 6, references => '<8> <7>' },
+        { mid => 7, references => '<8>' },
+        { mid => 8, references => '' }
+);
+
+($simples, $smsgs) = make_objs(@backwards);
+my $backward = thread_to_s($smsgs);
+SKIP: {
+        skip 'Mail::Thread missing', 1 unless $mt;
+        check_mt($backward, $simples, 'matches Mail::Thread backwards');
+}
+($simples, $smsgs) = make_objs(reverse @backwards);
+my $forward = thread_to_s($smsgs);
+if ('Mail::Thread sorts by Date') {
+        SKIP: {
+                skip 'Mail::Thread missing', 1 unless $mt;
+                check_mt($forward, $simples, 'matches Mail::Thread forwards');
         }
-        is($check, $st, 'Mail::Thread output matches');
+}
+unless ('sorting by Date') {
+        is("\n".$backward, "\n".$forward, 'forward and backward matches');
 }
 
 done_testing();
@@ -86,3 +112,19 @@ sub thread_to_s {
         }
         $st;
 }
+
+sub check_mt {
+        my ($st, $simples, $msg) = @_;
+        my $mt = Mail::Thread->new(@$simples);
+        $mt->thread;
+        $mt->order(sub { sort { $a->messageid cmp $b->messageid } @_ });
+        my $check = '';
+        my @q = map { (0, $_) } $mt->rootset;
+        while (@q) {
+                my $level = shift @q;
+                my $node = shift @q or next;
+                $check .= (" "x$level) . $node->messageid . "\n";
+                unshift @q, $level + 1, $node->child, $level, $node->next;
+        }
+        is("\n".$check, "\n".$st, $msg);
+}