From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: X-Spam-Status: No, score=-4.0 required=3.0 tests=ALL_TRUSTED,BAYES_00 shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from localhost (dcvr.yhbt.net [127.0.0.1]) by dcvr.yhbt.net (Postfix) with ESMTP id 302D51F9F3 for ; Mon, 4 Oct 2021 00:07:18 +0000 (UTC) From: Eric Wong To: meta@public-inbox.org Subject: [PATCH 2/2] www: fix ref cycle from threading w/ extindex Date: Sun, 3 Oct 2021 19:07:17 -0500 Message-Id: <20211004000717.18965-3-e@80x24.org> In-Reply-To: <20211004000717.18965-1-e@80x24.org> References: <20211004000717.18965-1-e@80x24.org> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit List-Id: 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 --- lib/PublicInbox/SearchThread.pm | 104 +++++++++++++++++--------------- t/thread-cycle.t | 21 ++++++- 2 files changed, 74 insertions(+), 51 deletions(-) diff --git a/lib/PublicInbox/SearchThread.pm b/lib/PublicInbox/SearchThread.pm index 8fb3a030aa72..507f25baab0e 100644 --- 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 4b47c01c37c1..e89b18464a5f 100644 --- 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) = @_;