# # Copyright (c) 2001-2011 NetApp, Inc., All Rights Reserved # Any use, modification, or distribution is prohibited # without prior written consent from NetApp, Inc. # ## @summary Base class for sets of objects ## @author dl-nacl-dev@netapp.com ## @status shared ## @pod here package NACL::MTask::Set; use strict; use warnings; use Params::Validate qw(validate_with validation_options SCALAR ARRAYREF OBJECT); use NATE::Log qw(log_global); my $Log = log_global(); my $may_enter = $Log->may_enter(); my $may_exit = $Log->may_exit(); use NACL::ComponentUtils qw(Dumper); use Scalar::Util qw(blessed); use NATE::Exceptions::Argument qw(:try); =head1 NAME NACL::MTask::Set =head1 DESCRIPTION A set is a data structure which contains elements (termed C) of the same unit type (termed as C here) and contains no duplicates. This makes dealing with lists of objects easier since each member is guaranteed to be of the same type and there are no undefs or duplicates in the list so adding, removing and checking for existence of a member becomes easy. It is also possible to form the union, intersection or difference of numerous sets, thus making it easy to deal with multiple lists. This is an abstract base class (i.e. this class should not be instantiated). Instead, one of the specific derived classes should be used. Each of the derived classes define the types allowed and criteria for determining uniqueness of a member. (See the directory NACL/MTask/Set/ for all the subclasses implemented) =over =item Basic Code Example use NACL::MTask::Set::Component; ... my @node_interfaces_matching_some_criteria = SomeLib::node_interfaces(); my $node_set = NACL::MTask::Set::Component->new( type => 'NACL::C::NetworkInterface', members => \@node_interfaces_matching_some_criteria ); my @iscsi_interfaces_matching_some_criteria = SomeOtherLib::iscsi_interfaces(); my $iscsi_set = NACL::MTask::Set::Component->new( type => 'NACL::C::NetworkInterface', members => \@iscsi_interfaces_matching_some_criteria ); my $iscsi_node_intersection = $node_set->intersection($iscsi_set); my @intersection_objects = $iscsi_node_intersection->get_all_members(); =back =head1 ATTRIBUTES =head2 type The unit type of all the members in this set. =head2 members A hash containing all the members in the set. Instead of accessing this attribute directly, the get_* methods should be used to access members of this set and L should be used to check for existence of a member in this set. =cut # Sub-classes can enforce limits on the type as well. For example, # NACL::MTask::Set::Component enforces that the "type" provided isa # NACL::C::Component. use Class::MethodMaker [ hash => 'members', scalar => [ { -store_cb => sub { $_[0]->_type_store_cb( $_[1] ) } }, 'type', ] ]; # Sub-classes should really just need to implement the # _calculate_key_of_member, which is what determines the uniqueness criteria # (the "characteristic function" in slightly more mathemetical terms) BEGIN { # Turn Params::Validate failures into NATE::Exceptions::Argument validation_options( on_fail => sub { NATE::Exceptions::Argument->throw(shift); } ); } =head1 METHODS =head2 new # In the examples listed below, we're using NACL::MTask::Set::Component # The same examples apply for other subclasses of NACL::MTask::Set # Providing only the type my $set = NACL::MTask::Set::Component->new(type => 'NACL::C::Volume'); # Providing the type along with a single member provided as a scalar my $set = NACL::MTask::Set::Component->new( type => 'NACL::C::Volume', members => $volume_obj ); # Providing the type along with an array of members my $set = NACL::MTask::Set::Component->new( type => 'NACL::C::Volume', members => \@volume_objs ); # Calling new with no type (a subsequent call to add() will determine # the type) my $set = NACL::MTask::Set::Component->new(); # Allowing the set to determine the type (assigns it as 'NACL::C::Volume' # in this example) my $set = NACL::MTask::Set::Component->new(members => $vol_c_obj); # Same as above, but providing multiple members my $set = NACL::MTask::Set::Component->new(members => @vol_objs); This method constructs a new Set object. The C argument is used to constrain the type of the members of this set. All members in the set are only allowed to be of this type or subclasses of this type (i.e. "isa" type). In the above example, we're constraining the set to allow members to be Volume Component objects (or subclasses thereof). (In set parlance, the C argument defines the "universe" of the set) Note that if C is not provided then the set will assign the type to be that of the first member provided (either here in the constructor or in a subsequent call to add). At the time of invoking this constructor, members may or may not be provided. =over =item Options =over =item C<< type => $type >> (Mandatory) Constrains all members of this set to be of this type. Note that this type must satisfy the criteria outlined by that particular Set. (for example, the C argument for NACL::MTask::Set::Component must in turn be of type 'NACL::C::Component') =item C<< members => $members | \@members >> (Optional) The members to add to this set. This can be provided as a scalar (a single member), as an array (for multiple members), or need not be provided at all. If any of the members do not satisfy the C criteria, then a C exception is thrown. =back =back =over =item Exceptions =over =item NATE::Exceptions::Argument If any of the members does not satisfy the type criteria. =back =back =cut sub new { my $pkg_or_obj = shift; my %opts = validate_with( params => \@_, spec => { type => { type => SCALAR, optional => 1 }, members => { type => OBJECT | ARRAYREF, optional => 1 } } ); my $pkg = ref $pkg_or_obj || $pkg_or_obj; my $self = bless {}, $pkg; my @members; if ( ref $opts{members} eq 'ARRAY' ) { @members = @{ $opts{members} }; } else { push @members, $opts{members} if ( defined $opts{members} ); } $self->type( $opts{type} ) if ( defined $opts{type} ); $self->add(@members) if @members; return $self; } =head2 add $set->add($member); or $set->add(@members); Adds one or more members to the set. This throws a C exception if any of the members do not satisfy the C criteria. =over =item Exceptions =over =item NATE::Exceptions::Argument If any of the members does not satisfy the type criteria. =back =back =cut sub add { $Log->enter() if $may_enter; my ( $self, @members ) = @_; unless (@members) { $Log->exit() if $may_exit; NATE::Exceptions::Argument->throw( 'At least 1 member must be ' . "provided in the call to 'add' but none were" ); } # Figure out the type just-in-time if it had not been provided by the # caller my $need_to_reset; if ( !$self->type_isset() ) { $self->type( ref $members[0] ); $need_to_reset = 1; } my @members_keys; try { @members_keys = $self->_calculate_keys_of_members(@members); } catch NATE::Exceptions::Argument with { # If the type got auto-determined, but one of the subsequent # members was of a different type, then we need to reset the type my $exception = shift; $self->type_reset() if $need_to_reset; $exception->throw(); }; $self->members_set( [@members_keys], [@members] ); $Log->exit() if $may_exit; } =head2 remove $set->remove($member); or $set->remove(@members); Removes one or more members to the set. This throws a C exception if any of the members do not satisfy the C criteria. =over =item Exceptions =over =item NATE::Exceptions::Argument If any of the members does not satisfy the type criteria. =back =back =cut sub remove { $Log->enter() if $may_enter; my ( $self, @members ) = @_; my @members_keys = $self->_calculate_keys_of_members(@members); $self->members_delete(@members_keys); $Log->exit() if $may_exit; } =head2 intersection my $intersection_set = $set->intersection($other_set); or my $intersection_set = $set->intersection(@other_sets); This method returns a set which is the intersection of this set and all the other sets provided as arguments. (i.e. the intersection set will only contain members that are present in B the sets provided) All of the provided sets have to be of the same type as this set, else a C exception is thrown. =over =item Exceptions =over =item NATE::Exceptions::Argument If any of the other sets provided is not of the same type as this set. =back =back =cut sub intersection { my ( $self, @other_sets ) = @_; $self->_check_if_of_same_type(@other_sets); my $intersect_set = $self->clone(); foreach my $other_set (@other_sets) { foreach my $key ( $self->members_keys() ) { if ( !$other_set->members_exists($key) ) { $intersect_set->members_delete($key); } } } return $intersect_set; } =head2 union my $union_set = $set->union($other_set); or my $union_set = $set->union(@other_sets); This method returns a set which is the union of this set and all the other sets provided as arguments. (i.e. the union set will contain members that are present in B the sets provided) All of the provided sets have to be of the same type as this set, else a C exception is thrown. =over =item Exceptions =over =item NATE::Exceptions::Argument If any of the other sets provided is not of the same type as this set. =back =back =cut sub union { my ( $self, @other_sets ) = @_; $self->_check_if_of_same_type(@other_sets); my $union_set = $self->clone(); foreach my $other_set (@other_sets) { my @other_keys = $other_set->members_keys(); my @other_values = $other_set->members_values(); $union_set->members_set( [@other_keys], [@other_values] ); } return $union_set; } =head2 difference my $difference_set = $set->difference($other_set); or my $difference_set = $set->difference(@other_sets); This method returns a set which is the difference of this set and all the other sets provided as arguments. (i.e. the union set will contain members that are present in B the sets provided) All of the provided sets have to be of the same type as this set, else a C exception is thrown. =over =item Exceptions =over =item NATE::Exceptions::Argument If any of the other sets provided is not of the same type as this set. =back =back =cut sub difference { $Log->enter() if $may_enter; my ( $self, @other_sets ) = @_; $self->_check_if_of_same_type(@other_sets); my $difference_set = $self->clone(); foreach my $other_set (@other_sets) { my @other_keys = $other_set->members_keys(); $difference_set->members_delete(@other_keys); } $Log->exit() if $may_exit; return $difference_set; } =head2 contains my $boolean = $set->contains($member); or my $boolean = $set->contains(@members); When provided a single member, this method checks whether that member is present in the set. When provided multiple members, this method checks whether B the members are present in the set. =over =item Exceptions =over =item NATE::Exceptions::Argument If any of the members does not satisfy the type criteria. =back =back =cut sub contains { $Log->enter() if $may_enter; my ( $self, @members ) = @_; my @members_keys = $self->_calculate_keys_of_members(@members); $Log->exit() if $may_exit; return $self->members_exists(@members_keys); } =head2 get_all_members my @all_members = $set->get_all_members(); Returns all members in the set. =head2 size my $size = $set->size(); Returns the number of members in this set. =head2 clear $set->clear(); Removes all members from this set. =cut no strict 'refs'; *{get_all_members} = \&members_values; *{size} = \&members_count; *{clear} = \&members_reset; use strict 'refs'; =head2 get_members my $obtained_member = $self->get_members($member); or my @obtained_members = $self->get_members(@members); Returns the member (or members) if they exist in the set. =over =item Exceptions =over =item NATE::Exceptions::Argument If any of the other sets provided is not of the same type as this set. =back =back =cut sub get_members { $Log->enter() if $may_enter; my $self = shift; my @members = $self->_get_members( members => \@_, sorted => 0 ); $Log->exit() if $may_exit; return wantarray ? @members : $members[0]; } =head2 get_all_members_sorted my @sorted_members = $set->get_all_members_sorted(); Returns all members in a sorted order. =cut sub get_all_members_sorted { $Log->enter() if $may_enter; my $self = shift; my @keys = $self->members_keys(); my @sorted_keys = sort @keys; $Log->exit() if $may_exit; return $self->members_index(@sorted_keys); } =head2 get_members_sorted my @sorted_member = $set->get_members_sorted($member); or my @sorted_members = $set->get_members_sorted(@members); Similar to L, but returns the existing members in a sorted order. =cut sub get_members_sorted { $Log->enter() if $may_enter; my $self = shift; my @members = $self->_get_members( members => \@_, sorted => 1 ); $Log->exit() if $may_exit; return wantarray ? @members : $members[0]; } sub _get_members { $Log->enter() if $may_enter; my $self = shift; my %opts = validate_with( params => \@_, spec => { members => { type => ARRAYREF }, sorted => { type => SCALAR } } ); my @members = @{ $opts{members} }; my @members_keys = $self->_calculate_keys_of_members(@members); @members_keys = sort (@members_keys) if ( $opts{sort} ); my @members_obtained = $self->members_index(@members_keys); # The *_index() method of MethodMaker returns undef for those keys which # do not exist in a hash. Here we're removing undefs since we don't # want to return a list like [ undef ]. @members_obtained = grep { defined $_ } @members_obtained; $Log->exit() if $may_exit; return @members_obtained; } =head2 is_equal my $is_equal = $set->is_equal($other_set); This method checks whether two sets are equal. Two sets are said to be equal if they contain the same members. Note that comparisons are only allowed between sets of the same type, else a C exception is thrown. =cut sub is_equal { my ( $self, $other_set ) = @_; $self->_check_if_of_same_type($other_set); my @self_keys = $self->members_keys(); my @other_keys = $other_set->members_keys(); if ( @self_keys == @other_keys ) { $Log->exit() if $may_exit; return $other_set->members_exists(@self_keys); } else { $Log->exit() if $may_exit; return 0; } } =head2 is_empty my $is_empty = $set->is_empty(); This method returns 1 if the set has no members. =cut sub is_empty { $Log->enter() if $may_enter; my $self = shift; $Log->exit() if $may_exit; return $self->size() ? 0 : 1; } =head2 empty_clone my $empty_clone = $set->empty_clone(); Returns a new set of the same type as this one, but with no memebers. =cut sub empty_clone { $Log->enter() if $may_enter; my $self = shift; my %args; # The "type" might not be set, so blindly setting the type of the clone # to be of this type could end up setting the type of the clone to be undef if ( $self->type_isset() ) { $args{type} = $self->type(); } my $empty_clone = $self->new(%args); $Log->exit() if $may_exit; return $empty_clone; } =head2 clone my $clone = $set->clone(); Returns a clone of this set (i.e. of the same type and with the same members) =cut sub clone { $Log->enter() if $may_enter; my $self = shift; my $clone = $self->empty_clone(); $clone->members_set( [ $self->members_keys() ], [ $self->members_values() ] ); $Log->exit() if $may_exit; return $clone; } # For operations involving more than one set (union, intersection, difference) # check if the sets are compatible, i.e. the sub _check_if_of_same_type { my ( $self, @other_sets ) = @_; my $this_type = $self->type(); my $caller = ( caller(1) )[3]; if ( !defined $this_type ) { $Log->exit() if $may_exit; NATE::Exceptions::Argument->throw( "Cannot call '$caller' since " . 'the type of this set is not known' ); } my $this_ref = ref $self; unless (@other_sets) { $Log->exit() if $may_exit; NATE::Exceptions::Argument->throw( 'At least 1 other set must be ' . "provided in the call to '$caller' but none were" ); } foreach my $other_set (@other_sets) { my $other_type = $other_set->type(); if ( !defined $other_type ) { $Log->exit() if $may_exit; NATE::Exceptions::Argument->throw( "Cannot call '$caller' since " . 'the type of one of the sets provided is not known' ); } my $other_ref = ref $other_set; if ( blessed($other_set) && ( $this_ref eq $other_ref ) ) { if ( $other_type ne $this_type ) { $Log->exit() if $may_exit; NATE::Exceptions::Argument->throw( 'One of the sets provided to ' . "'$caller' does not have the same type as this set.\n" . "Type of this set: $this_type\n" . "Type of other set: $other_type\n" ); } } else { $Log->exit() if $may_exit; $other_ref ||= 'SCALAR'; NATE::Exceptions::Argument->throw( 'All of the sets provided to ' . "'$caller' must be '$this_ref' objects but one of them " . "of them was provided as a '$other_ref'. Dumper:\n" . NACL::ComponentUtils::Dumper($other_set) ); } } } # Invokes _calculate_key_of_member for each of the members provided sub _calculate_keys_of_members { $Log->enter() if $may_enter; my ( $self, @members ) = @_; $self->_validate_members(@members); my @keys = map { $self->_calculate_key_of_member($_) } @members; $Log->exit() if $may_exit; return @keys; } sub _validate_members { $Log->enter() if $may_enter; my ( $self, @members ) = @_; unless (@members) { $Log->exit() if $may_exit; NATE::Exceptions::Argument->throw( 'At least 1 member must be ' . 'provided but none were' ); } foreach my $member (@members) { if ( !blessed $member || !$member->isa( $self->type() ) ) { $Log->exit() if $may_exit; NATE::Exceptions::Argument->throw( 'All of the members of this ' . 'set should be of type ' . $self->type() . ' but one of ' . 'the members provided was of type ' . ref($member) . ". Dumper (up to 3 levels) of member:\n" . NACL::ComponentUtils::Dumper($member) ); } } $Log->exit() if $may_exit; } sub _type_store_cb { $Log->enter() if $may_enter; my ( $self, $value ) = @_; if ( ref $value ) { $Log->exit() if $may_exit; NATE::Exceptions::Argument->throw( "The value for 'type' should " . "be a scalar but it was provided as a '" . ref($value) . "'. Value provided:\n" . NACL::ComponentUtils::Dumper($value) ); } my $base_type = $self->_base_type(); if ($base_type) { # Calling isa on a package name only works well if the package has been # previously loaded. Ensure that's the case. But perhas the $value isnt # a loadable file but defined in some other package, so use eval. require Module::Load; eval { Module::Load::load($value) }; if ( !$value->isa($base_type) ) { $Log->exit() if $may_exit; NATE::Exceptions::Argument->throw( "For the set '" . ref($self) . "' the type is allowed to be '$base_type' or packages " . "that are subclasses, but the provided value for 'type' " . "was '$value'\n" ); } } $Log->exit() if $may_exit; return $value; } sub _base_type { } 1; __END__ =head1 NOTES TO DEVELOPERS This section explains briefly how this module is implemented and how to extend it to create custom Set modules. If you are simply a user of the Set modules, then this section need not be read. (Note: any examples below are purely for illustrative purposes. The actual utility of these hypothetical sets would be debatable, at best.) =head2 Implementation of Base Class As mentioned above, a set is a collection of objects, which we term as "members". This is internally implemented as a hash, which is why C is listed as a hash field in MethodMaker. Defining it as a hash MethodMaker field allows us to make use of numerous MethodMaker provided functionality. =head3 MethodMaker-provided hash functionality This section describes the functionality provided by hash MethodMaker fields. An exhaustive reference is the POD available in the source code (see Class/MethodMaker/hash.pm), this section here is simply a primer. This is provided because our implementation extensively makes use of these methods. For any hash field named "foo", MethodMaker provides the following methods (most are self-explanatory, so aren't explained here): =over =item foo_keys =item foo_values =item foo_each =item foo_delete Delete one or more hash key-value pairs. =item foo_exists For a single key, returns whether that key exists. When provided multiple keys, returns true only if B keys are present. =item foo_count =item foo_set Set one or more key-value pairs in the hash. =item foo_index Returns the values of the requested keys from the hash. =back Hence, when any member is presented for a set operation, we first determine its key in the hash. The logic of determining the key for a particular member is done by what's known as the I. In our code, this is defined by the method C<_calculate_key_of_member()> (see below for explanation of how to define this). Having determined the key, any operation then becomes a single-access operation (performed by using one of the MethodMaker-provided methods listed above). Let's use a ComponentSet to illustrate the example. For a ComponentSet, the characteristic function for a member is its primary key string (which is a concatentation of the primary keys and their values, separated by semi-colons. For example, volume "vol" on vserver "vs" would have a primary key string of "volume=vol;vserver=vs"). Let's assume the set has two volumes: volume "vol1" on vserver "vs1" and volume "vol2" on vserver "vs2". This is the structure of the "members" hash: $VAR1 = { 'volume=vol1;vserver=vs1' => , 'volume=vol2;vserver=vs2' => , }; =head3 The "type" of a set As mentioned in the documentation at the beginning of this file, a set contains elements of a particular unit type (i.e. is a particular well-defined type). This is denoted by the C attribute. For example, for a ComponentSet each of the members B to be of type NACL::C::Component. If a provided member is not of this type, then the method throws an exception. (This is handled by the C<_validate_members()> method defined in the base class. See below for an example of when it needs to be redefined in the derived class) =head2 Creating a Set derived class This package provides the necessary functionality, but is an abstract base class. Object instances can only be created of a particular set derived class. This section describes what needs to be defined by the derived class. The two main pieces that need to be defined by the derived class are the characteristic function and the type. =head3 Defining the characteristic function The characteristic function is the logic that determines the unique key of the internal hash storing all the members. This is defining, in a sense, the uniqueness criteria. For example, if two components have the same values for the primary keys, then they refer to the same element. It is for this reason that a ComponentSet has the primary key string as its characteristic function: so that objects that refer to the same element will end up generating the same key. This is defined by the method "_calculate_key_of_member". Let's assume we have a basic config duplication tool that is capable of recreating volumes present on one vserver on another vserver. Let's assume that simply comparing that both vservers eventually have the same volumes is sufficient to determine that the tool has accurately duplicated the vserver. So let's say we need a set which has the list of volumes in that vserver (let's dub this set "VolumesInVserver"). In this case, the characteristic function is the name of the volume. The method we'd need to implement would be like this (heavily documented to explain the flow): sub _calculate_key_of_member { $Log->enter() if $may_enter; # This method is invoked internally with an object, and is # always passed the member as (positional) argument my ( $self, $member ) = @_; my $volume = $member->volume(); $Log->exit() if $may_exit; # The return value of the method ends up becoming the unique key in the # hash for this member return $volume; } Now, if multiple volume objects are passed which are of the same volume name, they will end up resolving to the same key. =head3 The type The C attribute determines the allowed type each of the members can be. For example, if we use the above example of the set containing only volume component objects, then in the derived class we can limit the type to be NACL::C::Volume. We would need to define the C<_base_type> subroutine for this: sub _base_type { return 'NACL::C::Volume' } If any of the provided members are not of type NACL::C::Volume, then the method exceptions out. (this checking is done by C<_validate_members()>) =head4 But hey, what if I'd like my set to have members of more than one type? Sets are meant to consist of members of a homogeneous type. Attempting to have a set contain members of different types would generally be a B idea. This section explains how this can be achieved, though we strongly suggest against creating sets with members of heterogenous types unless absolutely necessary. Creating sets with members of different types can be done by overriding the C<_validate_members> method. For example, if our "VolumesInVserver" set should allow objects either of type NACL::C::Volume or NACL::CS::Volume, then the above type declaration would result in failure for NACL::CS::Volume objects. Instead, we can override _validate_members like this: sub _validate_members { $Log->enter() if $may_enter; # Invoked internally with an object, gets passed an array # of members (which is the list of members originally passed # by the caller of the set) my ( $self, @members ) = @_; # If no members were passed, then we should exception out unless (@members) { $Log->exit() if $may_exit; NATE::Exceptions::Argument->throw( 'At least 1 member must be provided but none were' ); } foreach my $member (@members) { # Check if the member is a blessed object (using # Scalar::Util::blessed for this). Then check if its either of # type NACL::C::Volume or NACL::CS::Volume. Exception out if not if ( !blessed $member || !$member->isa( 'NACL::C::Volume' ) || !$member->isa( 'NACL::CS::Volume' ) ) { $Log->exit() if $may_exit; NATE::Exceptions::Argument->throw( 'All of the members of this ' . 'set should be of type NACL::C::Volume or ' . 'NACL::CS::Volume but one of ' . 'the members provided was of type ' . ref($member) . ". Dumper (up to 3 levels) of member:\n" . NACL::ComponentUtils::Dumper($member) ); } } $Log->exit() if $may_exit; } =cut