FreeBSD Mail Archives

Date:      Tue, 24 Apr 2001 07:16:25 -0700 (PDT)
From:      Jeff Kletsky <Jeff+freebsd@wagsky.com>
To:        freebsd-stable@freebsd.org
Subject:   Re: pkg/port dependency tool (enclosed)
Message-ID:  <Pine.BSF.4.21.0104240708590.5506-100000@wildside.wagsky.com>
In-Reply-To: <15076.20167.337195.349137@guru.mired.org>


Thanks to some good pointers, I have an *alpha* of the text-output version
of the tool available. I need to integrate with the code already in
pkg_version and resolve how to detect and include the dependencies
introduced by the USE_* variables. I'll probably be quiet for a while, the
"easy" part is done -- now to make it a robust tool...

Jeff

#!/usr/bin/perl -w

# $Header: /usr/local/cvsroot/pkg_graph/graph_depends.pl,v 1.4 2001/04/24 14:08:28 jeff Exp $

#
# Tool to read from /var/db/pkg to find all pkg/port dependencies
# create a graph and solve for process to rebuild ports in "proper
# order"
#
# Examples of use:
#
# pkg_version -L = | cut -f 1 -d " " | graph_depends.pl
#
# graph_depends.pl -a
#

# Status: ALPHA development

# Author: Jeff Kletsky mailto:jeff+freebsd@wagsky.com

#
# TODO:
#
# * use '/usr/sbin/pkg_version'; to access the ports index, tie nodes
#   to their cannonical names, and ouput code to rebuild ports
#
# * deal with the USE_BZIP2 variables that Kevin Way has pointed out
#
# * Include dependencies of ports about to be built
#
# * Discriminate between existing dependencies and future ones
#   - How are "orphaned" ports to be handled??
#
# * Consider solving the problem where the changes are driven by
#   wishing to rebuild a target, all its predecessors, and all their
#   successors (e.g., " I need a clean version of gnome")
#

#
# Thanks to:
#
# * Mike Meyer for mumbling the words "transitive closure of the 
#   dependency matrix" and getting this rolling in the right direction
# 
# * Garance Drosihn for providing me to Kevin Way's comments on the 
#   USE_ variable issue
#


use strict;
use POSIX qw(EXIT_FAILURE EXIT_SUCCESS);
use FileHandle;

require Graph;  # (not yet in the ports tree)

my $usage = qq(
Usage:
$0 [-a]

Reads a list of packages/ports to be updated from STDIN and prints a 
suggested order for updating those packages/ports based on the dependencies
seen in the installed list of packages/ports in /var/db/pkg

  -a  Ignores STDIN and looks at all registered packages/ports

);

my $doall = 0;

if ( $#ARGV > 0 ) {
    die $usage;
}

if ( $#ARGV == 0 ) {
    $doall = ( shift @ARGV eq "-a" );
    die $usage unless $doall;
}

my $pkg_db_dir = '/var/db/pkg';
$pkg_db_dir =~ s/\/$//;             # prevent "trailing-slash" issue

my $required_by_filename = '+REQUIRED_BY';

#
# Open the directory that contains pkg/port information
#

opendir (VARDBPKG, $pkg_db_dir) or die "Unable to open $pkg_db_dir: $!";

#
# Get the subdirectories, and iterate through them
#

my @installed_pkgs = readdir VARDBPKG;

die "No files read in $pkg_db_dir\n" unless $#installed_pkgs > 1;

#
# Read the list of files from STDIN
#

my $target;
my %targets;

if ( !$doall ) {

    while ( $target = <> ) {
	chomp $target;
	$targets{$target} = 'true';
    }

} else {

    foreach $target (@installed_pkgs) {
	$targets{$target} = 'true';
    }

}	

my $pkg;
my $rqd;
my $required_by_fqn;
my $required_by_fh;

my $pkg_node;
my $rqd_node;

my $graph = new Graph;
$graph->directed('true');

 PKG:

    foreach $pkg (sort @installed_pkgs) {
	
	
	next PKG if $pkg =~ m/^\./;

	$graph->add_vertex($pkg);

	
#
# See if there is a +REQUIRED_BY file, open it, and process lines
#
	
	$required_by_fqn = "${pkg_db_dir}/${pkg}/${required_by_filename}";

	next PKG unless -e $required_by_fqn;
	
	$required_by_fh = new FileHandle "< $required_by_fqn";
	die "Unable to open $required_by_fqn: $!" 
	    unless defined $required_by_fh;
	
	while ($rqd = <$required_by_fh>) {

	    chomp $rqd;
	    
	    $graph->add_edge($pkg,$rqd);

	}

    } # PKG

#
# Now that we have the full graph, check for loops
# Loops should "never" occur or certain ports would be un-buildable    
# It *is* vaguely possible that the dependencies change and create a loop
# after one of the components in the loop were already built.
# Since this is a remote possibility, just die...
#

die "Graph loops back on itself, unable to resolve" 
    if ( $graph->self_loop_vertices );

if (! $doall ) {

#
# If not looking at all pkgs/ports, trim the tree
#

    my $tcgraph = $graph->TransitiveClosure_Floyd_Warshall;

#
# Mark and sweep
#

#
# Note that the output of pkg_version is "unqualified" 
# create a new list that identifies all old and new targets
#

    my %tgt_pkgs;
    my $tgtmatch;

    foreach $pkg ($graph->vertices) {
	$graph->delete_attribute('candidate', $pkg);
	foreach $target (keys %targets) {
	    $tgtmatch = "^" . quotemeta($target);
	    $tgt_pkgs{$pkg} = 'true' if $pkg =~/$tgtmatch/;
	}
    }

    foreach $target (keys %tgt_pkgs) {
#	print "setting $target\n";
	$graph->set_attribute('candidate', $target, 'true') ;
	foreach $pkg ($graph->vertices) {
	    $graph->set_attribute('candidate', $pkg, 'true') 
#		&&  print "setting $pkg as dependent on $target\n"
		    if $tcgraph->has_edge($target, $pkg);
	}
    }
    
    foreach $pkg ($graph->vertices) {
	$graph->delete_vertex($pkg) 
	    unless $graph->get_attribute('candidate', $pkg);
    }
    
}

#
# Start dumping out the order of processing
#

my $level = 0;
my @pkgs;

while ( $graph->vertices ) {

    print "\n\nLevel ${level}:\n";
    print "========\n";
    @pkgs = ($graph->isolated_vertices, $graph->source_vertices);

    print join("\n", sort(@pkgs));

    $graph->delete_vertices(@pkgs);

    die "No packages found which can be built at this level, unable to resolve"
	unless @pkgs;

    $level++;
}

print "\n\nDone\n";

exit EXIT_SUCCESS;


To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-stable" in the body of the message

Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.BSF.4.21.0104240708590.5506-100000>

Header And Logo

Peripheral Links

Site Navigation

Header And Logo

Peripheral Links

Search

Site Navigation