Okay, so how can I use CPAN to find a module that will wash the dishes for me? ;)

Melding different dependencies is really a policy decision. If there is an inconsistency, do we throw out a package, or do we install both versions? Given a range of possible versions do we always pick the most recent? The most stable? And so on. If you are creating a perl clone of the Portage apps, the policy is already set for you: look at those apps to see what is done in case of dependency conflict.

As you say, the second part is fairly simple: just do a preorder traversal of the tree.

I'm still not quite sure how to build or structure the tree, though. I was thinking of using a hash with each package name as a key as a way to avoid extra calls to the function to extract dependencies and to avoid getting a package's dependency tree twice (2 packages have a dependency on the same package):



my $deps = { 'mainpackage-1.0' => [ 'dependency1-1.3',
                                    'dependency2-2.3',
                                    'dependency3'],
             'dependency1-1.3' => [ 'dep1_of_dep1' ],
             'dependency2-2.3' => [ 'dep1_of_dep2',
                                    'dep2_of_dep2',
                                    'dep3_of_dep2' ],
             'dependency3' => undef };
[download]


This way, I have easy access to each previously referenced packages's primary dependencies without another function call. I still can't figure out how to put it all together into a full dependency tree, though. I'm still not sure I'm going about this the right way.

You can use a structure just like the one you show. You don't really need a data structure that is internally hierarchical. The one you have is an adjacency (dependency) list, which can store a tree (well, any graph) just fine. In fact, it's a little nicer since there may be duplicated dependencies, as you mention (your dependencies form a directed acyclic graph, and not necessarily a tree). Assuming that finding the dependencies is trivial, generate the adjacency list like this:

my @pkgs = qw[ mainpackage-1.0 ];
my %deps;

while (@pkgs) {
    my $pkg = shift @pkgs;
    next if exists $deps{$pkg};

    my @deps = find_dependencies($pkg);
    $deps{$pkg} = \@deps;
    push @pkgs, @deps;
}
[download]

You can traverse it like a tree like this:

sub traverse {
    my ($deps, $root, $depth) = @_;
    print "  " x $depth, "$root\n";
    traverse($deps, $_, $depth + 1)
        for @{ $deps->{$root} };
}

traverse( \%deps, "mainpackage-1.0" );
[download]

.. which would generate output like this:

mainpackage-1.0
  dependency1-1.3
    dep1_of_dep1
  dependency2-2.3
    dep1_of_dep2
    dep2_of_dep2
    dep3_of_dep3
  dependency3
[download]

The output would contain duplicates if the directed graph is not a tree. But you can use an additional hash within your traversal to mark already-seen packages, say, if you were doing a postorder traversal to determine what order to install all the needed packages.

Anyway, with the adjacency list data structure, all the dependency information about a package is in one place. You can do the same with restrictions, i.e. "somepackage < 4.0" and "somepackage > 3.0". Store all these restrictions in another similar hash indexed by package name. When you're done calculating dependencies, look at each package's list of restrictions and see if they're reconcilable.

blokhead