represent allowed status transitions graph in Perl

Question

There is something like status changes check logic in our app.

Currently checking is being handled by ugly if statement

I want to replace it by transition matrix:

my %allowed_status_changes = (
    1 => (2,5),     
    2 => (1,2,3,4,5),
    3 => (4,2),     
    4 => (3,2),     
    5 => (),        
);
my $is_allowed_transition = 
    $submitted_status ~~ $allowed_status_changes {$original_status};

if ($prerequestsites && !$is_allowed_transition) {
    return;
}

certain transitions can be allowed only on additional condition, therefore I will need something like

2 => ( 
    (target => 1)
    (target => 2, condition => $some_condition)
    (target => (3,4), condition => $other_condition), 
    (target => 5)
),

(in my opinion it is too long)

What structure would you use in this situation if you should focus on readability and maintainability?

How you will parse it to check if transition is allowed?

Answer 1

If the conditions are very prevalent (e.g. almost every allowed transition has them) then your latter structure is perfectly fine, other than your syntax error of representing a hashref with "()" instead of "{}".

If the conditions are rare, I'd suggest going with #1, augmented by optional constructs similar to your #2.

Please note that readability of checking code is IMHO very clear though voluminous and not very idiomatic.

OTOH, maintainability of the matrix is high - you have terse yet readable syntax from #1 where no conditions are needed and a clear though longer syntax for conditions which is flexible enough for many conditions per many settings like your #2.

my %allowed_status_changes = (
    1 => [2,5],
    2 => [1,5,{targets=>[2], conditions=>[$some_condition]}
             ,{targets=>[3,4], conditions=>[$other_condition, $more_cond]}]
    3 => [4,2],     
    4 => [3,2],
    5 => [],        
);

sub is_allowed_transition {
    my ($submitted_status, $original_status ) = @_;
    foreach my $alowed_status (@$allowed_status_changes{$original_status}) {
        return 1 if !ref $alowed_status && $alowed_status == $submitted_status;
        if (ref $alowed_status) {
            foreach my $target (@$alowed_status{targets}) {
                foreach my $condition (@$alowed_status{conditions}) {
                    return 1 if check_condition($submitted_status
                                              , $original_status, $condition);    
                }
            }
        }
    }
    return 0;
}

if ($prerequestsites
  && !$is_allowed_transition($submitted_status, $original_status )) {
    return;
}

Answer 2

Although I agree with DVK for the most part, I have to say, once you start delving into arrays of arrays of hashes, you're reaching a code complexity level that is hard to maintain without much spinning of heads and bugs.

At this point, I'd probably reach for an object and a class, for a bit of syntactic sugar.

my $transitions = TransitionGraph->new(); 
$transition->add( 1, { targets => [ 2, 5 ] }); 
$transition->add( 2, { targets => [ 1, 5 ] });
$transition->add( 2, { targets => [ 2 ],    conditions => [ $some_condition ] });
$transition->add( 2, { targets => [ 3, 4 ], conditions => [ $other_condition, $more_cond ]}); 
$transition->add( 3, { targets => [4,2] } );
$transition->add( 4, { targets => [3,2] } );
$transition->add( 5, { targets => [] } );

if( $transition->allowed( 1 , 3 )){ 

}

Class implementation is up to the user, but I'd use Moose.

The primary benefits of this is you're encapsulating how the state graph works so you can Just Use it and worry about how the graph works seperate from where its used.

nb. in the above proposed API, add() creates a new record if one does not exist, and updates that record if it does exist. This turned out to be simpler than having "upgrade" methods or "get this item and then modify it" techniques.

Internally, it could do this, or something like it:

sub add { 
   my ( $self , $input_state, $rules ) = @_;
   my $state;
   if ( $self->has_state( $input_state ) ) { 
       $state = $self->get_state( $input_state );
   } else { 
       $state = TransitionGraphState->new( source_id => $input_state );
       $self->add_state( $input_state, $state );
   }
   my $targets = delete $rules{targets};
   for my $target ( @$targets ) {
      $state->add_target( $target, $rules );
   }
   return $self;
}

sub allowed { 
    my ( $self, $from, $to )  = @_; 

    if ( not $self->has_state( $from ) ){ 
         croak "NO source state $from in transition graph";
    }
    my $state = $self->get_state( $from );
    return $state->allowed_to( $to );
}

This also has the cool perk of not requiring one particular code set to work on the sub-nodes, you can create seperate instances with their own behaviour just in case you want one source state to be treated differently.

 $transition->add_state( 2, $some_other_class_wich_works_like_transitiongraphstate );

Hope this is helpful =).

Answer 3

There is nothing wrong with the second form. You are not going to be able to get around the fact that you must encode the state machine somewhere. In fact, I think having the entire machine encoded in one place like that is far easier to understand that something with too many layers of abstraction where you need to look in n different places to understand the flow of the machine.