X-Git-Url: http://www.git.stargrave.org/?a=blobdiff_plain;f=lib%2FPublicInbox%2FSearchThread.pm;h=00ae9faccc08b7b16aff259fb9cd54165b485eb2;hb=70209c643bd5b21d369dff684218714f5186993b;hp=5774a9562b55f27956fd8e8e1baad11389e95e08;hpb=274c7932e1dda688eb4b31e04db34992f0a0eedc;p=public-inbox.git diff --git a/lib/PublicInbox/SearchThread.pm b/lib/PublicInbox/SearchThread.pm index 5774a956..00ae9fac 100644 --- a/lib/PublicInbox/SearchThread.pm +++ b/lib/PublicInbox/SearchThread.pm @@ -7,7 +7,7 @@ # Mail::Thread is unmaintained and unavailable on some distros. # We also do not want pruning or subject grouping, since we want # to encourage strict threading and hopefully encourage people -# to use proper In-Reply-To. +# to use proper In-Reply-To/References. # # This includes fixes from several open bugs for Mail::Thread # @@ -20,89 +20,99 @@ package PublicInbox::SearchThread; use strict; use warnings; - -sub new { - return bless { - messages => $_[1], - id_table => {}, - rootset => [] - }, $_[0]; -} +use PublicInbox::MID qw($MID_EXTRACT); sub thread { - my $self = shift; - _add_message($self, $_) foreach @{$self->{messages}}; - my $id_table = delete $self->{id_table}; - $self->{rootset} = [ grep { !delete $_->{parent} } values %$id_table ]; -} - -sub _get_cont_for_id ($$) { - my ($self, $mid) = @_; - $self->{id_table}{$mid} ||= PublicInbox::SearchThread::Msg->new($mid); -} - -sub _add_message ($$) { - my ($self, $smsg) = @_; - - # A. if id_table... - my $this = _get_cont_for_id($self, $smsg->{mid}); - $this->{smsg} = $smsg; - - # B. For each element in the message's References field: - defined(my $refs = $smsg->{references}) or return; - - my $prev; - foreach my $ref ($refs =~ m/<([^>]+)>/g) { - # Find a Container object for the given Message-ID - my $cont = _get_cont_for_id($self, $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); + my ($msgs, $ordersub, $ctx) = @_; + my (%id_table, @imposters); + keys(%id_table) = scalar @$msgs; # pre-size + + # 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}; + bless $_, 'PublicInbox::SearchThread::Msg'; + if (exists $id_table{$_->{mid}}) { + $_->{children} = []; + push @imposters, $_; # we'll deal with them later + undef; + } else { + $_->{children} = {}; # will become arrayref later + $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; } - $prev = $cont; - } - # C. Set the parent of this message to be the last element in - # References... - if ($prev && !$this->has_descendent($prev)) { # would loop - $prev->add_child($this) + # 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); + } } -} - -sub order { - my ($self, $ordersub) = @_; - my $rootset = $ordersub->($self->{rootset}); - $self->{rootset} = $rootset; - $_->order_children($ordersub) for @$rootset; + my $ibx = $ctx->{ibx}; + my @rootset = grep { # n.b.: delete prevents cyclic refs + !delete($_->{parent}) && $_->visible($ibx) + } values %id_table; + $ordersub->(\@rootset); + $_->order_children($ordersub, $ctx) for @rootset; + + # parent imposter messages with reused Message-IDs + unshift(@{$id_table{$_->{mid}}->{children}}, $_) for @imposters; + \@rootset; } package PublicInbox::SearchThread::Msg; +use base qw(PublicInbox::Smsg); use strict; use warnings; use Carp qw(croak); -sub new { +# declare a ghost smsg (determined by absence of {blob}) +sub ghost { bless { - id => $_[1], + mid => $_[0], children => {}, # becomes an array when sorted by ->order(...) - }, $_[0]; + }, __PACKAGE__; } sub topmost { my ($self) = @_; my @q = ($self); while (my $cont = shift @q) { - return $cont if $cont->{smsg}; + return $cont if $cont->{blob}; push @q, values %{$cont->{children}}; } undef; @@ -113,7 +123,7 @@ sub add_child { croak "Cowardly refusing to become my own parent: $self" if $self == $child; - my $cid = $child->{id}; + my $cid = $child->{mid}; # reparenting: if (defined(my $parent = $child->{parent})) { @@ -126,25 +136,41 @@ sub add_child { sub has_descendent { my ($self, $child) = @_; + my %seen; # loop prevention while ($child) { - return 1 if $self == $child; + return 1 if $self == $child || $seen{$child}++; $child = $child->{parent}; } 0; } +# Do not show/keep ghosts iff they have no children. Sometimes +# a ghost Message-ID is the result of a long header line +# being folded/mangled by a MUA, and not a missing message. +sub visible ($$) { + my ($self, $ibx) = @_; + return 1 if $self->{blob}; + if (my $by_mid = $ibx->smsg_by_mid($self->{mid})) { + %$self = (%$self, %$by_mid); + 1; + } else { + (scalar values %{$self->{children}}); + } +} + sub order_children { - my ($cur, $ordersub) = @_; + my ($cur, $ordersub, $ctx) = @_; - my %seen = ($cur => 1); + my %seen = ($cur => 1); # self-referential loop prevention my @q = ($cur); + my $ibx = $ctx->{ibx}; while (defined($cur = shift @q)) { - my $c = $cur->{children}; # The hashref here... - - $c = [ grep { !$seen{$_}++ } values %$c ]; # spot/break loops - $c = $ordersub->($c) if scalar @$c > 1; - $cur->{children} = $c; # ...becomes an arrayref - push @q, @$c; + # the {children} hashref here... + my @c = grep { !$seen{$_}++ && visible($_, $ibx) } + values %{delete $cur->{children}}; + $ordersub->(\@c) if scalar(@c) > 1; + $cur->{children} = \@c; # ...becomes an arrayref + push @q, @c; } }