File Coverage

blib/lib/Algorithm/Dependency.pm

Criterion	Covered	Total	%
statement	55	58	94.8
branch	20	24	83.3
condition			n/a
subroutine	12	13	92.3
pod	8	8	100.0
total	95	103	92.2

package Algorithm::Dependency; # git description: v1.111-8-g2fb772e
# ABSTRACT: Base class for implementing various dependency trees

#pod =pod
#pod
#pod =head1 SYNOPSIS
#pod
#pod Typical Usage: Ordering based on dependency requirements
#pod
#pod   use Algorithm::Dependency::Ordered;
#pod   use Algorithm::Dependency::Source::HoA;
#pod
#pod   my $deps = {
#pod     core  => [ ],
#pod     a     => [ 'core' ],
#pod     b     => [ 'a' ]
#pod     this  => [ ],
#pod     that  => [ ],
#pod   };
#pod   my $deps_source = Algorithm::Dependency::Source::HoA->new( $deps );
#pod
#pod   my $dep = Algorithm::Dependency::Ordered->new(
#pod     source   => $deps_source,
#pod     selected => [ 'this', 'that' ], # Items we have processed elsewhere or have already satisfied
#pod   )
#pod   or die 'Failed to set up dependency algorithm';
#pod
#pod   my $also = $dep->schedule_all();
#pod   # Returns: ['core', 'a', 'b'] -- ie: installation-order. Whereas using base
#pod   # Algorithm::Dependency would return sorted ['a', 'b', 'core']
#pod
#pod   my $also = $dep->schedule( 'b' );
#pod   # Returns: ['core', 'a', 'b'] -- installation order, including ourselves
#pod
#pod   my $also = $dep->depends( 'b' );
#pod   # Returns: ['a', 'core'] -- sorted order, not including ourselves
#pod
#pod Base Classes
#pod
#pod   use Algorithm::Dependency;
#pod   use Algorithm::Dependency::Source::File;
#pod
#pod   # Load the data from a simple text file
#pod   my $data_source = Algorithm::Dependency::Source::File->new( 'foo.txt' );
#pod
#pod   # Create the dependency object, and indicate the items that are already
#pod   # selected/installed/etc in the database
#pod   my $dep = Algorithm::Dependency->new(
#pod       source   => $data_source,
#pod       selected => [ 'This', 'That' ]
#pod   ) or die 'Failed to set up dependency algorithm';
#pod
#pod   # For the item 'Foo', find out the other things we also have to select.
#pod   # This WON'T include the item we selected, 'Foo'.
#pod   my $also = $dep->depends( 'Foo' );
#pod   print $also
#pod   	? "By selecting 'Foo', you are also selecting the following items: "
#pod   		. join( ', ', @$also )
#pod   	: "Nothing else to select for 'Foo'";
#pod
#pod   # Find out the order we need to act on the items in.
#pod   # This WILL include the item we selected, 'Foo'.
#pod   my $schedule = $dep->schedule( 'Foo' );
#pod
#pod =head1 DESCRIPTION
#pod
#pod Algorithm::Dependency is a framework for creating simple read-only
#pod dependency hierarchies, where you have a set of items that rely on other
#pod items in the set, and require actions on them as well.
#pod
#pod Despite the most visible of these being software installation systems like
#pod the CPAN installer, or Debian apt-get, they are useful in other situations.
#pod This module intentionally uses implementation-neutral words, to avoid
#pod confusion.
#pod
#pod =head2 Terminology
#pod
#pod The term C refers to a single entity, such as a single software
#pod package, in the overall set of possible entities. Internally, this is a
#pod fairly simple object. See L for details.
#pod
#pod The term C means that a particular item, for your purposes, has
#pod already been acted up in the required way. For example, if the software
#pod package had already been installed, and didn't need to be re-installed,
#pod it would be C.
#pod
#pod The term C refers to a location that contains the master set of
#pod items. This will be very application specific, and might be a flat file,
#pod some form of database, the list of files in a folder, or generated
#pod dynamically.
#pod
#pod =head2 General Description
#pod
#pod =for stopwords versioned
#pod
#pod Algorithm::Dependency implements algorithms relating to dependency
#pod hierarchies. To use this framework, all you need is a source for the master
#pod list of all the items, and a list of those already selected. If your
#pod dependency hierarchy doesn't require the concept of items that are already
#pod selected, simply don't pass anything to the constructor for it.
#pod
#pod Please note that the class Algorithm::Dependency does NOT implement an
#pod ordering, for speed and simplicity reasons. That is, the C it
#pod provides is not in any particular order. If item 'A' depends on item 'B',
#pod it will not place B before A in the schedule. This makes it unsuitable for
#pod things like software installers, as they typically would need B to be
#pod installed before A, or the installation of A would fail.
#pod
#pod For dependency hierarchies requiring the items to be acted on in a particular
#pod order, either top down or bottom up, see L.
#pod It should be more applicable for your needs. This is the the subclass you
#pod would probably use to implement a simple ( non-versioned ) package
#pod installation system. Please note that an ordered hierarchy has additional
#pod constraints. For example, circular dependencies ARE legal in a
#pod non-ordered hierarchy, but ARE NOT legal in an ordered hierarchy.
#pod
#pod =head2 Extending
#pod
#pod A module for creating a source from a simple flat file is included. For
#pod details see L. Information on creating
#pod a source for your particular use is in L.
#pod
#pod =head1 METHODS
#pod
#pod =cut

use 5.005;
use strict;
use Params::Util qw{_INSTANCE _ARRAY};
use Algorithm::Dependency::Item   ();
use Algorithm::Dependency::Source ();

our $VERSION = '1.112';


#####################################################################
# Constructor

#pod =pod
#pod
#pod =head2 new %args
#pod
#pod The constructor creates a new context object for the dependency algorithms to
#pod act in. It takes as argument a series of options for creating the object.
#pod
#pod =over 4
#pod
#pod =item source => $Source
#pod
#pod The only compulsory option is the source of the dependency items. This is
#pod an object of a subclass of L. In practical terms,
#pod this means you will create the source object before creating the
#pod Algorithm::Dependency object.
#pod
#pod =item selected => [ 'A', 'B', 'C', etc... ]
#pod
#pod The C option provides a list of those items that have already been
#pod 'selected', acted upon, installed, or whatever. If another item depends on one
#pod in this list, we don't have to include it in the output of the C or
#pod C methods.
#pod
#pod =item ignore_orphans => 1
#pod
#pod Normally, the item source is expected to be largely perfect and error free.
#pod An 'orphan' is an item name that appears as a dependency of another item, but
#pod doesn't exist, or has been deleted.
#pod
#pod By providing the C flag, orphans are simply ignored. Without
#pod the C flag, an error will be returned if an orphan is found.
#pod
#pod =back
#pod
#pod The C constructor returns a new Algorithm::Dependency object on success,
#pod or C on error.
#pod
#pod =cut

sub new {
	my $class  = shift;
	my %args   = @_;
	my $source = _INSTANCE($args{source}, 'Algorithm::Dependency::Source')
		or return undef;

	# Create the object
	my $self = bless {
		source   => $source, # Source object
		selected => {},
		}, $class;

	# Were we given the 'ignore_orphans' flag?
	if ( $args{ignore_orphans} ) {
		$self->{ignore_orphans} = 1;
	}

	# Done, unless we have been given some selected items
	_ARRAY($args{selected}) or return $self;

	# Make sure each of the selected ids exists
	my %selected = ();
	foreach my $id ( @{ $args{selected} } ) {
		# Does the item exist?
		return undef unless $source->item($id);

		# Is it a duplicate
		return undef if $selected{$id};

		# Add to the selected index
		$selected{$id} = 1;
	}

	$self->{selected} = \%selected;
	$self;
}





#####################################################################
# Basic methods

#pod =pod
#pod
#pod =head2 source
#pod
#pod The C method retrieves the L object
#pod for the algorithm context.
#pod
#pod =cut

sub source { $_[0]->{source} }

#pod =pod
#pod
#pod =head2 selected_list
#pod
#pod The C method returns, as a list and in alphabetical order,
#pod the list of the names of the selected items.
#pod
#pod =cut

sub selected_list { sort keys %{$_[0]->{selected}} }

#pod =pod
#pod
#pod =head2 selected $name
#pod
#pod Given an item name, the C method will return true if the item is
#pod selected, false is not, or C if the item does not exist, or an error
#pod occurs.
#pod
#pod =cut

sub selected { $_[0]->{selected}->{$_[1]} }

#pod =pod
#pod
#pod =head2 item $name
#pod
#pod The C method fetches and returns the item object, as specified by the
#pod name argument.
#pod
#pod Returns an L object on success, or C if
#pod an item does not exist for the argument provided.
#pod
#pod =cut

sub item { $_[0]->{source}->item($_[1]) }





#####################################################################
# Main algorithm methods

#pod =pod
#pod
#pod =head2 depends $name1, ..., $nameN
#pod
#pod Given a list of one or more item names, the C method will return
#pod a reference to an array containing a list of the names of all the OTHER
#pod items that also have to be selected to meet dependencies.
#pod
#pod That is, if item A depends on B and C then the C method would
#pod return a reference to an array with B and C. ( C<[ 'B', 'C' ]> )
#pod
#pod If multiple item names are provided, the same applies. The list returned
#pod will not contain duplicates.
#pod
#pod The method returns a reference to an array of item names on success, a
#pod reference to an empty array if no other items are needed, or C
#pod on error.
#pod
#pod NOTE: The result of C is ordered by an internal C
#pod irrespective of the ordering provided by the dependency handler.  Use
#pod L and C to use the most
#pod common ordering (process sequence)
#pod
#pod =cut

sub depends {
	my $self    = shift;
	my @stack   = @_ or return undef;
	my @depends = ();
	my %checked = ();

	# Process the stack
	while ( my $id = shift @stack ) {
		# Does the id exist?
		my $Item = $self->{source}->item($id)
		or $self->{ignore_orphans} ? next : return undef;

		# Skip if selected or checked
		next if $checked{$id};

		# Add its depends to the stack
		push @stack, $Item->depends;
		$checked{$id} = 1;

		# Add anything to the final output that wasn't one of
		# the original input.
		unless ( scalar grep { $id eq $_ } @_ ) {
			push @depends, $id;
		}
	}

	# Remove any items already selected
	my $s = $self->{selected};
	return [ sort grep { ! $s->{$_} } @depends ];
}

#pod =pod
#pod
#pod =head2 schedule $name1, ..., $nameN
#pod
#pod Given a list of one or more item names, the C method will
#pod return, as a reference to an array, the ordered list of items you
#pod should act upon in whichever order this particular dependency handler
#pod uses - see L for one that implements
#pod the most common ordering (process sequence).
#pod
#pod This would be the original names provided, plus those added to satisfy
#pod dependencies, in the preferred order of action. For the normal algorithm,
#pod where order it not important, this is alphabetical order. This makes it
#pod easier for someone watching a program operate on the items to determine
#pod how far you are through the task and makes any logs easier to read.
#pod
#pod If any of the names you provided in the arguments is already selected, it
#pod will not be included in the list.
#pod
#pod The method returns a reference to an array of item names on success, a
#pod reference to an empty array if no items need to be acted upon, or C
#pod on error.
#pod
#pod =cut

sub schedule {
	my $self  = shift;
	my @items = @_ or return undef;

	# Get their dependencies
	my $depends = $self->depends( @items ) or return undef;

	# Now return a combined list, removing any items already selected.
	# We are allowed to return an empty list.
	my $s = $self->{selected};
	return [ sort grep { ! $s->{$_} } @items, @$depends ];
}

#pod =pod
#pod
#pod =head2 schedule_all;
#pod
#pod The C method acts the same as the C method, but
#pod returns a schedule that selected all the so-far unselected items.
#pod
#pod =cut

sub schedule_all {
	my $self = shift;
	$self->schedule( map { $_->id } $self->source->items );
}

1;

__END__