On Wed, May 28, 2014 at 07:25:32PM +0200, Agustin Martin wrote:
>
> In parallel I am thinking about a raw iterative procedure processing the
> hash of dependencies. I have done some tests and seems OK, but still needs
> some rewrite and debugging.
>
> Will write again when I have something ready for wider testing.
Hi all,
I was doing some tests with an iterative depends sorting. Rob, please find
attached yet another lib.pl and test-lib.pl versions.
Dependency hash is first refreshed in each loop after remaining to process
add-ons, then add-ons having no dependencies are pushed to the list of done
add-ons and then loop goes to next iteration until either there are no
pending add-ons or those pending are the same as before (circular
dependency).
I have also split my monolithic function into three functions and made
`get_installed_add_on_packages' return again an array ref as in the
original lib.pl.
The way dependency hash is created and refreshed could be more ellaborated,
but in my tests things seem to work well.
--
Agustin
#!/usr/bin/perl -w
use strict;
use Cwd;
my $debug++ if $ENV{'EMACSEN_COMMON_DEBUG'};
# depends on: dpkg-query, perl
my $lib_dir = "/usr/lib/emacsen-common";
my $var_dir = "/var/lib/emacsen-common";
$::installed_package_state_dir = "${var_dir}/state/package/installed";
$::installed_flavor_state_dir = "${var_dir}/state/flavor/installed";
sub glob_in_dir
{
my ($dir, $pattern) = @_;
my $oldir = getcwd;
chdir($dir) or die "chdir $dir: $!";
my @files = glob("*[!~]");
chdir($oldir);
return \@files;
}
sub validate_add_on_pkg
{
my ($pkg, $script, $old_invocation_style) = @_;
if($old_invocation_style)
{
if(-e "$lib_dir/packages/compat/$pkg")
{
print STDERR "ERROR: $pkg is broken - called $script as an old-style add-on, but has compat file.\n";
#exit(1);
}
}
else # New invocation style.
{
unless(-e "$lib_dir/packages/compat/$pkg")
{
print STDERR "ERROR: $pkg is broken - called $script as a new-style add-on, but has no compat file.\n";
#exit(1);
}
}
}
sub get_installed_add_on_packages
{
# Return all of the old format packages, plus all of the new-format
# packages that are ready (i.e. have a state/installed file). In
# this case ready means ready for compilation.
my $all_pkgs = glob_in_dir("$lib_dir/packages/install", '*[!~]');
my $new_format_pkgs = glob_in_dir("$lib_dir/packages/compat", '*[!~]');
my %ready_pkgs = map { $_ => 1 } @$all_pkgs;
for my $p (@$new_format_pkgs)
{
delete $ready_pkgs{$p} unless (-e "$::installed_package_state_dir/$p");
}
return [ keys %ready_pkgs ];
}
sub get_installed_flavors
{
my $flavors = glob_in_dir($::installed_flavor_state_dir, '*[!~]');
return @$flavors;
}
# ------------------------------------------------------------
sub get_add_on_dependencies {
# ------------------------------------------------------------
# Generate a hash with emacsen add-on dependencies
#
# \%depends_hash = get_add_on_dependencies(\@packages_to_sort)
# $depends_hash->{$addon}${$dependency}
# ------------------------------------------------------------
my $packages_to_sort = shift;
my %installed_add_ons = map {$_ => 1 } @{ get_installed_add_on_packages() };
my %depends_hash = ();
# Ask dpkg-query about $packages_to_sort dependencies
my $packages_to_sort_string = join(' ',@$packages_to_sort);
my $dpkg_query_output = `dpkg-query -W -f='package:\${Package}, \${Depends}\n' $packages_to_sort_string`;
die 'emacsen-common: dpkg-query invocation failed' unless ($? == 0);
foreach my $dpkg_query_line ( split("\n", $dpkg_query_output) ){
my @package_depends = split(/[,|]/, $dpkg_query_line);
my $package = shift @package_depends;
# Remove consistency string or ignore line if missing.
next unless $package =~ s/^package://;
# Filter out all the "noise" (version number dependencies, etc)
@package_depends = map { /\s*(\S+)/o; $1; } @package_depends;
foreach my $dependency ( @package_depends ){
# dpkg-query regexp above will result in empty dependency for
# packages with no dependencies at all. Discard if so.
next unless $dependency;
# Filter out dependencies on non-add-on packages.
next unless ( defined $installed_add_ons{"$dependency"} );
# Populate the dependencies hash for this package
$depends_hash{$package}{$dependency}++;
}
}
if ( $debug ){
print "-------------------------------------------------------------\n";
print "Packages to sort:\n$packages_to_sort_string\n";
print "----------\n";
print "dpkg-query output:\n---\n$dpkg_query_output---\n";
print "----------\n";
print "Installed add-ons:\n", join(', ',sort keys %installed_add_ons), "\n";
print "----------\n";
# Show packages without dependencies
foreach my $pkg ( sort @$packages_to_sort ){
next if defined $depends_hash{$pkg};
print "- \"$pkg\" has no dependencies.\n";
}
# Show packages with dependencies
foreach my $pkg ( sort keys %depends_hash ){
print "+ \"$pkg\" dependencies: [",
join(', ',sort keys $depends_hash{$pkg} ),
"].\n";
}
}
return \%depends_hash;
}
# ------------------------------------------------------------
sub dependency_sort_addons {
# ------------------------------------------------------------
# Sort add-on list by dependencies
# @sorted_add_ons = dependency_sort_addons(\%packages_to_sort)
# ------------------------------------------------------------
my $packages_to_sort = shift;
my $depends_hash = get_add_on_dependencies($packages_to_sort);;
my @sorted_add_ons = ();
my %pending_to_sort = map {$_ => 1} @{$packages_to_sort};
# Put emacsen-common first if it is to be processed
if ( defined $pending_to_sort{'emacsen-common'} ){
push @sorted_add_ons, "emacsen-common";
delete $pending_to_sort{'emacsen-common'};
}
my $iteration = 0;
my $pending_num = scalar keys %pending_to_sort;
while ( %pending_to_sort ){
$iteration++;
# Create a subset of dependencies hash for pending add-ons
my %tmp_depends = ();
my @pending_add_ons = sort keys %pending_to_sort;
foreach my $add_on ( @pending_add_ons ){
foreach my $depend ( @pending_add_ons ){
$tmp_depends{$add_on}{$depend}++ if defined $depends_hash->{$add_on}->{$depend};
}
}
# Push packages with none or already processed dependencies
foreach my $add_on ( sort keys %pending_to_sort ){
unless ( defined $tmp_depends{$add_on} ){
push @sorted_add_ons, $add_on;
delete $pending_to_sort{$add_on};
}
}
if ( $debug ){
print " -$iteration- Pending add-ons: ", join(', ',sort keys %pending_to_sort ), "\n";
}
# Analyze loop result and proceed accordingly
my $new_pending_num = scalar keys %pending_to_sort;
if ( $new_pending_num == 0 ){
print "+ Done full sort\n" if $debug;
} elsif ( $new_pending_num == $pending_num ){
my @pending = sort keys %pending_to_sort;
print "emacsen-common warning: Circular dependencies between ",
join(', ',@pending), "\n";
push @sorted_add_ons, @pending;
return @sorted_add_ons;
} else {
$pending_num = $new_pending_num;
}
}
return @sorted_add_ons;
}
# ------------------------------------------------------------
sub generate_add_on_install_list {
# ------------------------------------------------------------
# Generate an array of emacsen-add-ons sorted by dependencies
#
# @sorted_packages = generate_add_on_install_list \@packages_to_sort
# ------------------------------------------------------------
my $packages_to_sort = shift;
my @sorted_add_ons = ();
return unless $packages_to_sort;
@sorted_add_ons = dependency_sort_addons($packages_to_sort);
return @sorted_add_ons;
}
# To make require happy...
1;
#!/usr/bin/perl -w
use strict;
require "./lib.pl";
# Get all the packages $pkg depends on, dependency sorted.
my @installed_add_ons = @{ get_installed_add_on_packages() };
my @pkgs_to_handle = generate_add_on_install_list(\@installed_add_ons);
print "----------\nSorted add-on packages:\n----------\n",
join(', ',@pkgs_to_handle), "\n";
# Show installed flavors
my @installed_flavors = get_installed_flavors();
print "----------\nInstalled flavors:\n----------\n",
join(', ',@installed_flavors), "\n";
