Norman,
Apparently this is the sort algorithm Autobuild uses to calculate the
build order.
Steve.
=pod
=item my \@sorted_modules =
Test::AutoBuild::Lib::sort_modules(\@modules);
Performs a topological sort of modules based on their declared
build dependancies. The elements in the C<modules> parameter
should be instances of Test::AutoBuild::Module class. The returned
array ref will be in sorted order.
=cut
sub sort_modules {
my $modules = shift;
my $order = [];
my %pairs; # all pairs ($l, $r)
my %npred; # number of predecessors
my %succ; # list of successors
# tsort code by Jeffrey S. Haemer, <[log in to unmask]>
# SEE ALSO tsort(1), tcsh(1), tchrist(1)
# Algorithm stolen from Jon Bentley (I<More Programming Pearls>, pp.
20-23),
# Who, in turn, stole it from Don Knuth
# (I<Art of Computer Programming, volume 1: Fundamental Algorithms>,
# Section 2.2.3)
foreach my $name (keys %{$modules}) {
my $depends = $modules->{$name}->dependencies();
if ($#{$depends} > -1) {
foreach (@{$depends}) {
die "module $name depends on non-existent module $_"
unless exists $modules->{$_};
next if defined $pairs{$_}{$name};
$pairs{$_}{$name}++;
$npred{$_} += 0;
$npred{$name}++;
push @{$succ{$_}}, $name;
}
} else {
$pairs{$name}{$name}++;
$npred{$name} += 0;
push @{$succ{$name}}, $name;
}
}
# create a list of nodes without predecessors
my @list = &_rand_order(grep {!$npred{$_}} keys %npred);
while (@list) {
$_ = pop @list;
push @{$order}, $_;
foreach my $child (@{$succ{$_}}) {
# depth-first (default)
push @list, $child unless --$npred{$child};
}
}
return $order;
}
-----Original Message-----
From: Starlink development [mailto:[log in to unmask]] On Behalf Of
Norman Gray
Sent: 28 February 2005 13:17
To: [log in to unmask]
Subject: Re: Pending
Steve,
On 2005 Feb 28 , at 12.27, Rankin, SE (Stephen) wrote:
> It is not the scripts that generate the autobuild conf file from
> componentset.xml, it is Autobuild itself that generates the unique
list
> of components to build and the order in which they should be built.
Righto. But if Peter's right, and it's deducing a cyclic dependency
(and not spotting it), then it might be that there's some bug in the
way that the dependencies are being expressed to it. But this is of
course just speculation -- if your debugging stuff does produce a clear
explanation of the problem that's more reassuring.
All the best,
Norman
--
----------------------------------------------------------------------
Norman Gray : Physics & Astronomy, Glasgow University, UK
http://www.astro.gla.ac.uk/users/norman/ : www.starlink.ac.uk
|