www: fix ref cycle from threading w/ extindex

Unlike v1 inboxes (which don't accept duplicate Message-IDs at
all), and v2 inboxes (which generate a new Message-ID for
duplicates), extindex must accept duplicate Message-IDs as-is.

This was fine for storage, but prevented the reference-cycle
mechanism of our message threading display algorithm from working
reliably.  It could no longer delete the ->{parent} field from
clobbered entries in the %id_table.

So we now take into account reused Message-IDs and never clobber
entries in %id_table.  Instead, we mark reused Message-IDs as
"imposters" and special-case them by injecting them as children
after all other threading is complete.

This cycle was noticed using a pre-release of Devel::Mwrap::PSGI:
  https://80x24.org/mwrap-perl.git

diff --git a/lib/PublicInbox/SearchThread.pm b/lib/PublicInbox/SearchThread.pm
index 8fb3a030aa723417036108bb1728d8abeec8be4f..507f25baab0e04760b3e55c57f116d6a958246a6 100644 (file)
--- a/lib/PublicInbox/SearchThread.pm
+++ b/lib/PublicInbox/SearchThread.pm
@@ -24,70 +24,74 @@ use PublicInbox::MID qw($MID_EXTRACT);
 
 sub thread {
        my ($msgs, $ordersub, $ctx) = @_;
+       my (%id_table, @imposters);
+       keys(%id_table) = scalar @$msgs; # pre-size
 
-       # A. put all current $msgs (non-ghosts) into %id_table
-       my %id_table = map {;
+       # A. put all current non-imposter $msgs (non-ghosts) into %id_table
+       # (imposters are messages with reused Message-IDs)
+       # Sadly, we sort here anyways since the fill-in-the-blanks References:
+       # can be shakier if somebody used In-Reply-To with multiple, disparate
+       # messages.  So, take the client Date: into account since we can't
+       # always determine ordering when somebody uses multiple In-Reply-To.
+       my @kids = sort { $a->{ds} <=> $b->{ds} } grep {
                # this delete saves around 4K across 1K messages
                # TODO: move this to a more appropriate place, breaks tests
                # if we do it during psgi_cull
                delete $_->{num};
 
-               $_->{mid} => PublicInbox::SearchThread::Msg::cast($_);
+               PublicInbox::SearchThread::Msg::cast($_);
+               if (exists $id_table{$_->{mid}}) {
+                       $_->{children} = [];
+                       push @imposters, $_; # we'll deal with them later
+                       undef;
+               } else {
+                       $id_table{$_->{mid}} = $_;
+                       defined($_->{references});
+               }
        } @$msgs;
+       for my $smsg (@kids) {
+               # This loop exists to help fill in gaps left from missing
+               # messages.  It is not needed in a perfect world where
+               # everything is perfectly referenced, only the last ref
+               # matters.
+               my $prev;
+               for my $ref ($smsg->{references} =~ m/$MID_EXTRACT/go) {
+                       # Find a Container object for the given Message-ID
+                       my $cont = $id_table{$ref} //=
+                               PublicInbox::SearchThread::Msg::ghost($ref);
+
+                       # Link the References field's Containers together in
+                       # the order implied by the References header
+                       #
+                       # * If they are already linked don't change the
+                       #   existing links
+                       # * Do not add a link if adding that link would
+                       #   introduce a loop...
+                       if ($prev &&
+                               !$cont->{parent} &&  # already linked
+                               !$cont->has_descendent($prev) # would loop
+                          ) {
+                               $prev->add_child($cont);
+                       }
+                       $prev = $cont;
+               }
 
-       # Sadly, we sort here anyways since the fill-in-the-blanks References:
-       # can be shakier if somebody used In-Reply-To with multiple, disparate
-       # messages.  So, take the client Date: into account since we can't
-       # always determine ordering when somebody uses multiple In-Reply-To.
-       # We'll trust the client Date: header here instead of the Received:
-       # time since this is for display (and not retrieval)
-       _set_parent(\%id_table, $_) for sort { $a->{ds} <=> $b->{ds} } @$msgs;
+               # C. Set the parent of this message to be the last element in
+               # References.
+               if (defined $prev && !$smsg->has_descendent($prev)) {
+                       $prev->add_child($smsg);
+               }
+       }
        my $ibx = $ctx->{ibx};
-       my $rootset = [ grep {
+       my $rootset = [ grep { # n.b.: delete prevents cyclic refs
                        !delete($_->{parent}) && $_->visible($ibx)
                } values %id_table ];
        $rootset = $ordersub->($rootset);
        $_->order_children($ordersub, $ctx) for @$rootset;
-       $rootset;
-}
 
-sub _set_parent ($$) {
-       my ($id_table, $this) = @_;
-
-       # B. For each element in the message's References field:
-       defined(my $refs = $this->{references}) or return;
-
-       # This loop exists to help fill in gaps left from missing
-       # messages.  It is not needed in a perfect world where
-       # everything is perfectly referenced, only the last ref
-       # matters.
-       my $prev;
-       foreach my $ref ($refs =~ m/$MID_EXTRACT/go) {
-               # Find a Container object for the given Message-ID
-               my $cont = $id_table->{$ref} //=
-                       PublicInbox::SearchThread::Msg::ghost($ref);
-
-               # Link the References field's Containers together in
-               # the order implied by the References header
-               #
-               # * If they are already linked don't change the
-               #   existing links
-               # * Do not add a link if adding that link would
-               #   introduce a loop...
-               if ($prev &&
-                       !$cont->{parent} &&  # already linked
-                       !$cont->has_descendent($prev) # would loop
-                  ) {
-                       $prev->add_child($cont);
-               }
-               $prev = $cont;
-       }
-
-       # C. Set the parent of this message to be the last element in
-       # References.
-       if (defined $prev && !$this->has_descendent($prev)) { # would loop
-               $prev->add_child($this);
-       }
+       # parent imposter messages with reused Message-IDs
+       unshift(@{$id_table{$_->{mid}}->{children}}, $_) for @imposters;
+       $rootset;
 }
 
 package PublicInbox::SearchThread::Msg;

diff --git a/t/thread-cycle.t b/t/thread-cycle.t
index 4b47c01c37c1c9b81b4a684c85d2326323f62d3b..e89b18464a5f55335c63320b33e9c172e65f3f79 100644 (file)
--- a/t/thread-cycle.t
+++ b/t/thread-cycle.t
@@ -96,7 +96,26 @@ if ('sorting by Date') {
        is("\n".$backward, "\n".$forward, 'forward and backward matches');
 }
 
-done_testing();
+SKIP: {
+       require_mods 'Devel::Cycle', 1;
+       Devel::Cycle->import('find_cycle');
+       my @dup = (
+               { mid => 5, references => '<6>' },
+               { mid => 5, references => '<6> <1>' },
+       );
+       open my $fh, '+>', \(my $out = '') or xbail "open: $!";
+       (undef, $smsgs) = $make_objs->(@dup);
+       eval 'package EmptyInbox; sub smsg_by_mid { undef }';
+       my $ctx = { ibx => bless {}, 'EmptyInbox' };
+       my $rootset = PublicInbox::SearchThread::thread($smsgs, sub {
+               [ sort { $a->{mid} cmp $b->{mid} } @{$_[0]} ] }, $ctx);
+       my $oldout = select $fh;
+       find_cycle($rootset);
+       select $oldout;
+       is($out, '', 'nothing from find_cycle');
+} # Devel::Cycle check
+
+done_testing;
 
 sub thread_to_s {
        my ($msgs) = @_;