package PublicInbox::SearchThread;
use strict;
use warnings;
-use Email::Abstract;
sub new {
return bless {
}, $_[0];
}
-sub _get_hdr {
- my ($class, $msg, $hdr) = @_;
- Email::Abstract->get_header($msg, $hdr) || '';
-}
-
-sub _uniq {
- my %seen;
- return grep { !$seen{$_}++ } @_;
-}
-
-sub _references {
- my $class = shift;
- my $msg = shift;
- my @references = ($class->_get_hdr($msg, "References") =~ /<([^>]+)>/g);
- my $foo = $class->_get_hdr($msg, "In-Reply-To");
- chomp $foo;
- $foo =~ s/.*?<([^>]+)>.*/$1/;
- push @references, $foo
- if $foo =~ /^\S+\@\S+$/ && (!@references || $references[-1] ne $foo);
- return _uniq(@references);
-}
-
-sub _msgid {
- my ($class, $msg) = @_;
- my $id = $class->_get_hdr($msg, "Message-ID");
- die "attempt to thread message with no id" unless $id;
- chomp $id;
- $id =~ s/^<([^>]+)>.*/$1/; # We expect this not to have <>s
- return $id;
-}
-
-sub rootset { @{$_[0]{rootset}} }
-
sub thread {
my $self = shift;
- $self->_setup();
- $self->{rootset} = [ grep { !$_->parent } values %{$self->{id_table}} ];
- $self->_finish();
-}
-
-sub _finish {
- my $self = shift;
+ _add_message($self, $_) foreach @{$self->{messages}};
+ $self->{rootset} = [
+ grep { !$_->{parent} } values %{$self->{id_table}} ];
delete $self->{id_table};
- delete $self->{seen};
}
-sub _get_cont_for_id {
- my $self = shift;
- my $id = shift;
- $self->{id_table}{$id} ||= $self->_container_class->new($id);
-}
-
-sub _container_class { 'PublicInbox::SearchThread::Container' }
-
-sub _setup {
- my ($self) = @_;
-
- _add_message($self, $_) foreach @{$self->{messages}};
+sub _get_cont_for_id ($$) {
+ my ($self, $mid) = @_;
+ $self->{id_table}{$mid} ||= PublicInbox::SearchThread::Msg->new($mid);
}
sub _add_message ($$) {
- my ($self, $message) = @_;
+ my ($self, $smsg) = @_;
# A. if id_table...
- my $this_container = $self->_get_cont_for_id($self->_msgid($message));
- $this_container->message($message);
+ my $this = _get_cont_for_id($self, $smsg->{mid});
+ $this->{smsg} = $smsg;
# B. For each element in the message's References field:
- my @refs = $self->_references($message);
-
my $prev;
- for my $ref (@refs) {
- # Find a Container object for the given Message-ID
- my $container = $self->_get_cont_for_id($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 &&
- !$container->parent && # already linked
- !$container->has_descendent($prev) # would loop
- ) {
- $prev->add_child($container);
+ if (defined(my $refs = $smsg->{references})) {
+ 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);
+ }
+ $prev = $cont;
}
- $prev = $container;
}
# C. Set the parent of this message to be the last element in
# References...
- if ($prev &&
- !$this_container->has_descendent($prev) # would loop
- ) {
- $prev->add_child($this_container)
+ if ($prev && !$this->has_descendent($prev)) { # would loop
+ $prev->add_child($this)
}
}
sub order {
- my $self = shift;
- my $ordersub = shift;
+ my ($self, $ordersub) = @_;
# make a fake root
- my $root = $self->_container_class->new( 'fakeroot' );
+ my $root = _get_cont_for_id($self, 'fakeroot');
$root->add_child( $_ ) for @{ $self->{rootset} };
# sort it
$root->order_children( $ordersub );
# and untangle it
- my @kids = $root->children;
- $self->{rootset} = \@kids;
- $root->remove_child($_) for @kids;
+ my $kids = $root->children;
+ $self->{rootset} = $kids;
+ $root->remove_child($_) for @$kids;
}
-package PublicInbox::SearchThread::Container;
+package PublicInbox::SearchThread::Msg;
use Carp qw(croak);
use Scalar::Util qw(weaken);
sub new { my $self = shift; bless { id => shift }, $self; }
-sub message { $_[0]->{message} = $_[1] if @_ == 2; $_[0]->{message} }
-sub parent { @_ == 2 ? weaken($_[0]->{parent} = $_[1]) : $_[0]->{parent} }
-sub child { $_[0]->{child} = $_[1] if @_ == 2; $_[0]->{child} }
-sub next { $_[0]->{next} = $_[1] if @_ == 2; $_[0]->{next} }
-sub messageid { $_[0]->{id} }
-
sub add_child {
my ($self, $child) = @_;
croak "Cowardly refusing to become my own parent: $self"
if $self == $child;
- if (grep { $_ == $child } $self->children) {
+ if (grep { $_ == $child } @{$self->children}) {
# All is potentially correct with the world
- $child->parent($self);
+ weaken($child->{parent} = $self);
return;
}
- $child->parent->remove_child($child) if $child->parent;
+ my $parent = $child->{parent};
+ remove_child($parent, $child) if $parent;
- $child->next($self->child);
- $self->child($child);
- $child->parent($self);
+ $child->{next} = $self->{child};
+ $self->{child} = $child;
+ weaken($child->{parent} = $self);
}
sub remove_child {
my ($self, $child) = @_;
- return unless $self->child;
- if ($self->child == $child) { # First one's easy.
- $self->child($child->next);
- $child->next(undef);
- $child->parent(undef);
+
+ my $x = $self->{child} or return;
+ if ($x == $child) { # First one's easy.
+ $self->{child} = $child->{next};
+ $child->{parent} = $child->{next} = undef;
return;
}
- my $x = $self->child;
my $prev = $x;
- while ($x = $x->next) {
+ while ($x = $x->{next}) {
if ($x == $child) {
- $prev->next($x->next); # Unlink x
- $x->next(undef);
- $x->parent(undef); # Deparent it
+ $prev->{next} = $x->{next}; # Unlink x
+ $x->{next} = $x->{parent} = undef; # Deparent it
return;
}
$prev = $x;
}
# oddly, we can get here
- $child->next(undef);
- $child->parent(undef);
+ $child->{next} = $child->{parent} = undef;
}
sub has_descendent {
sub children {
my $self = shift;
my @children;
- my $visitor = $self->child;
+ my $visitor = $self->{child};
while ($visitor) {
push @children, $visitor;
- $visitor = $visitor->next
+ $visitor = $visitor->{next};
}
- return @children;
+ \@children;
}
sub set_children {
- my $self = shift;
- my $walk = $self->child( shift );
- while (@_) { $walk = $walk->next( shift ) }
- $walk->next(undef) if $walk;
-}
-
-sub order_children {
- my $self = shift;
- my $ordersub = shift;
-
- return unless $ordersub;
-
- my $sub = sub {
- my $cont = shift;
- my @children = $cont->children;
- return if @children < 2;
- $cont->set_children( $ordersub->( @children ) );
- };
- $self->iterate_down( undef, $sub );
- undef $sub;
+ my ($self, $children) = @_;
+ my $walk = $self->{child} = shift @$children;
+ do {
+ $walk = $walk->{next} = shift @$children;
+ } while ($walk);
}
# non-recursive version of recurse_down to avoid stack depth warnings
my %seen;
my @q = ($self);
while (my $cont = shift @q) {
- $seen{$cont}++;
+ $seen{$cont} = 1;
$callback->($cont);
- if (my $next = $cont->next) {
+ if (my $next = $cont->{next}) {
if ($seen{$next}) {
- $cont->next(undef);
+ $cont->{next} = undef;
} else {
push @q, $next;
}
}
- if (my $child = $cont->child) {
+ if (my $child = $cont->{child}) {
if ($seen{$child}) {
- $cont->child(undef);
+ $cont->{child} = undef;
} else {
push @q, $child;
}
}
}
-sub iterate_down {
- my $self = shift;
- my ($before, $after) = @_;
+sub order_children {
+ my ($walk, $ordersub) = @_;
my %seen;
- my $walk = $self;
my $depth = 0;
my @visited;
while ($walk) {
- push @visited, [ $walk, $depth ];
- $before->($walk, $depth) if $before;
+ push @visited, $walk;
# spot/break loops
- $seen{$walk}++;
+ $seen{$walk} = 1;
- my $child = $walk->child;
+ my $child = $walk->{child};
if ($child && $seen{$child}) {
- $walk->child(undef);
- $child = undef;
+ $walk->{child} = $child = undef;
}
- my $next = $walk->next;
+ my $next = $walk->{next};
if ($next && $seen{$next}) {
- $walk->next(undef);
- $next = undef;
+ $walk->{next} = $next = undef;
}
# go down, or across
if (!$next) {
my $up = $walk;
while ($up && !$next) {
- $up = $up->parent;
+ $up = $up->{parent};
--$depth;
- $next = $up->next if $up;
+ $next = $up->{next} if $up;
}
}
$walk = $next;
}
- return unless $after;
- while (@visited) { $after->(@{ pop @visited }) }
+ foreach my $cont (@visited) {
+ my $children = $cont->children;
+ next if @$children < 2;
+ $children = $ordersub->($children);
+ $cont = $cont->{child} = shift @$children;
+ do {
+ $cont = $cont->{next} = shift @$children;
+ } while ($cont);
+ }
}
1;