| 1 | package Logic::Relational::Goal::ConstraintFD; | ||||||||||||||||||||
| 2 | |||||||||||||||||||||
| 3 | 30 | ▶ | use v5.38; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 4 | 30 | ▶ | use experimental 'signatures'; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 5 | 30 | ▶ | use parent 'Logic::Relational::Goal'; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 6 | 30 | ▶ | use Carp qw(croak); | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 7 | 30 | ▶ | use Logic::Relational::Domain; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 8 | |||||||||||||||||||||
| 9 | =head1 NAME | ||||||||||||||||||||
| 10 | |||||||||||||||||||||
| 11 | Logic::Relational::Goal::ConstraintFD - Declarative CLP(FD) arithmetic constraint goal. | ||||||||||||||||||||
| 12 | |||||||||||||||||||||
| 13 | =cut | ||||||||||||||||||||
| 14 | |||||||||||||||||||||
| 15 | my %OP_CHECK = ( | ||||||||||||||||||||
| 16 | 58 | ▶ | '#=' => sub ( $l, $r ) { $l == $r }, | ||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 17 | 0 | ▶ | '==' => sub ( $l, $r ) { $l == $r }, | ||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||
| 18 | 8 | ▶ | '#/=' => sub ( $l, $r ) { $l != $r }, | ||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 19 | 0 | ▶ | '#!=' => sub ( $l, $r ) { $l != $r }, | ||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||
| 20 | 0 | ▶ | '#\=' => sub ( $l, $r ) { $l != $r }, | ||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||
| 21 | 0 | ▶ | '!=' => sub ( $l, $r ) { $l != $r }, | ||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||
| 22 | 15 | ▶ | '#<' => sub ( $l, $r ) { $l < $r }, | ||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 23 | 0 | ▶ | '<' => sub ( $l, $r ) { $l < $r }, | ||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||
| 24 | 0 | ▶ | '#<=' => sub ( $l, $r ) { $l <= $r }, | ||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||
| 25 | 0 | ▶ | '#=<' => sub ( $l, $r ) { $l <= $r }, | ||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||
| 26 | 11 | ▶ | '<=' => sub ( $l, $r ) { $l <= $r }, | ||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 27 | 0 | ▶ | '#>' => sub ( $l, $r ) { $l > $r }, | ||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||
| 28 | 0 | ▶ | '>' => sub ( $l, $r ) { $l > $r }, | ||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||
| 29 | 0 | ▶ | '#>=' => sub ( $l, $r ) { $l >= $r }, | ||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||
| 30 | 16 | ▶ | '>=' => sub ( $l, $r ) { $l >= $r }, | ||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 31 | 30 | ); | |||||||||||||||||||
| 32 | |||||||||||||||||||||
| 33 | 108 | ▶ | sub _compare ( $op, $left, $right ) { | ||||||||||||||||||
|
Subroutine
_compare: called CC=3 SCAR=11.1
| |||||||||||||||||||||
| 34 | 108 | ▶ | my $code = $OP_CHECK{$op} // croak "Unknown CLP(FD) operator: $op"; | ||||||||||||||||||
|
Condition50%1/2
$OP_CHECK{$op} // croak("Unknown CLP(FD) operator: $op")
MC/DC0%0/1
$OP_CHECK{$op} // croak("Unknown CLP(FD) operator: $op")
$OP_CHECK{$op}
Truth table50%1/2
A
A= $OP_CHECK{$op}
| |||||||||||||||||||||
| 35 | 108 | ▶ | return $code->( $left, $right ) ? 1 : 0; | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 36 | } | ||||||||||||||||||||
| 37 | |||||||||||||||||||||
| 38 | 24 | ▶ | sub new ( $class, $op, $vars, $eval_sub ) { | ||||||||||||||||||
|
Subroutine
new: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||
| 39 | 24 | return bless { | |||||||||||||||||||
| 40 | op => $op, | ||||||||||||||||||||
| 41 | vars => $vars, # Arrayref of Logic::Relational::Variable objects | ||||||||||||||||||||
| 42 | eval_sub => | ||||||||||||||||||||
| 43 | $eval_sub, # Closure: sub ($vals_hash) { returns ($left, $right) } | ||||||||||||||||||||
| 44 | }, $class; | ||||||||||||||||||||
| 45 | } | ||||||||||||||||||||
| 46 | |||||||||||||||||||||
| 47 | 15 | ▶ | sub expand ( $self, %args ) { | ||||||||||||||||||
|
Subroutine
expand: called CC=3 SCAR=11.1
Pod
documented
| |||||||||||||||||||||
| 48 | 15 | my $subst = $args{substitution}; | |||||||||||||||||||
| 49 | 15 | my $remaining = $args{remaining}; | |||||||||||||||||||
| 50 | 15 | my $state = $args{state}; | |||||||||||||||||||
| 51 | |||||||||||||||||||||
| 52 | 15 | my $propagator = $self->_make_propagator(); | |||||||||||||||||||
| 53 | 15 | my $new_subst = $propagator->($subst); | |||||||||||||||||||
| 54 | 15 | ▶ | if ($new_subst) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 55 | 13 | my $new_state = $state->add_propagator($propagator); | |||||||||||||||||||
| 56 | 13 | my $succ = $new_state->derive( | |||||||||||||||||||
| 57 | substitution => $new_subst, | ||||||||||||||||||||
| 58 | goals => $remaining, | ||||||||||||||||||||
| 59 | ); | ||||||||||||||||||||
| 60 | 13 | ▶ | return $succ // (); | ||||||||||||||||||
|
Condition33%1/3
$succ // ()
MC/DC0%0/2
$succ // ()
$succ
()
Truth table33%1/3
A // B
A= $succB= ()
| |||||||||||||||||||||
| 61 | } | ||||||||||||||||||||
| 62 | |||||||||||||||||||||
| 63 | 2 | return (); | |||||||||||||||||||
| 64 | } | ||||||||||||||||||||
| 65 | |||||||||||||||||||||
| 66 | 15 | ▶ | sub _make_propagator ($self) { | ||||||||||||||||||
|
Subroutine
_make_propagator: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 67 | 15 | my @vars = @{ $self->{vars} }; | |||||||||||||||||||
| 68 | 15 | my $op = $self->{op}; | |||||||||||||||||||
| 69 | 15 | my $eval_sub = $self->{eval_sub}; | |||||||||||||||||||
| 70 | |||||||||||||||||||||
| 71 | 142 | ▶ | return sub ($curr_subst) { | ||||||||||||||||||
|
Subroutine
__ANON__: called CC=11 SCAR=24.6
| |||||||||||||||||||||
| 72 | 142 | my %var_states; | |||||||||||||||||||
| 73 | my @unbound_ids; | ||||||||||||||||||||
| 74 | |||||||||||||||||||||
| 75 | 142 | for my $var (@vars) { | |||||||||||||||||||
| 76 | 292 | my $val = $curr_subst->walk($var); | |||||||||||||||||||
| 77 | 292 | ▶ | my $id = | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 78 | ref($var) eq 'Logic::Relational::Variable' ? $var->id : undef; | ||||||||||||||||||||
| 79 | |||||||||||||||||||||
| 80 | 292 | ▶ | if ( ref($val) eq 'Logic::Relational::Variable' ) { | ||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||
| 81 | 62 | my $d = $curr_subst->{bindings}{ $val->id }; | |||||||||||||||||||
| 82 | 62 | ▶ | if ( ref($d) eq 'Logic::Relational::Domain' ) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 83 | 62 | $var_states{ $val->id } = { var => $val, domain => $d }; | |||||||||||||||||||
| 84 | push @unbound_ids, $val->id | ||||||||||||||||||||
| 85 | 62 | ▶ | unless grep { $_ eq $val->id } @unbound_ids; | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 86 | } | ||||||||||||||||||||
| 87 | else { | ||||||||||||||||||||
| 88 | 0 | return $curr_subst; | |||||||||||||||||||
| 89 | } | ||||||||||||||||||||
| 90 | } | ||||||||||||||||||||
| 91 | elsif ( ref($val) eq 'Logic::Relational::Domain' ) { | ||||||||||||||||||||
| 92 | 0 | croak "Walk returned domain object directly"; | |||||||||||||||||||
| 93 | } | ||||||||||||||||||||
| 94 | } | ||||||||||||||||||||
| 95 | |||||||||||||||||||||
| 96 | 142 | ▶ | if ( !@unbound_ids ) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 97 | 108 | my %vals_map; | |||||||||||||||||||
| 98 | 108 | for my $var (@vars) { | |||||||||||||||||||
| 99 | 218 | ▶ | my $vname = | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 100 | ref($var) eq 'Logic::Relational::Variable' | ||||||||||||||||||||
| 101 | ? $var->name | ||||||||||||||||||||
| 102 | : $var; | ||||||||||||||||||||
| 103 | 218 | $vname =~ s/^\$//; | |||||||||||||||||||
| 104 | 218 | $vals_map{$vname} = $curr_subst->walk($var); | |||||||||||||||||||
| 105 | } | ||||||||||||||||||||
| 106 | 108 | my ( $left, $right ) = $eval_sub->( \%vals_map ); | |||||||||||||||||||
| 107 | 108 | ▶ | return unless _compare( $op, $left, $right ); | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 108 | 80 | return $curr_subst; | |||||||||||||||||||
| 109 | } | ||||||||||||||||||||
| 110 | |||||||||||||||||||||
| 111 | 34 | return $curr_subst; | |||||||||||||||||||
| 112 | 15 | }; | |||||||||||||||||||
| 113 | } | ||||||||||||||||||||
| 114 | |||||||||||||||||||||
| 115 | 0 | ▶ | sub _prune_unbound_domains ( $unbound_ids_ref, $var_states_ref, $curr_subst, | ||||||||||||||||||
|
Subroutine
_prune_unbound_domains: not called CC=7 SCAR=40.3
| |||||||||||||||||||||
| 116 | $eval_sub, $op, $vars_ref ) | ||||||||||||||||||||
| 117 | { | ||||||||||||||||||||
| 118 | 0 | for my $target_id (@$unbound_ids_ref) { | |||||||||||||||||||
| 119 | 0 | my $target_domain = $var_states_ref->{$target_id}{domain}; | |||||||||||||||||||
| 120 | 0 | my @valid_vals; | |||||||||||||||||||
| 121 | |||||||||||||||||||||
| 122 | 0 | for my $candidate ( $target_domain->values ) { | |||||||||||||||||||
| 123 | 0 | ▶ | if ( | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 124 | _is_candidate_feasible( | ||||||||||||||||||||
| 125 | $target_id, $candidate, $unbound_ids_ref, | ||||||||||||||||||||
| 126 | $var_states_ref, $curr_subst, $eval_sub, | ||||||||||||||||||||
| 127 | $op, $vars_ref | ||||||||||||||||||||
| 128 | ) | ||||||||||||||||||||
| 129 | ) | ||||||||||||||||||||
| 130 | { | ||||||||||||||||||||
| 131 | 0 | push @valid_vals, $candidate; | |||||||||||||||||||
| 132 | } | ||||||||||||||||||||
| 133 | } | ||||||||||||||||||||
| 134 | |||||||||||||||||||||
| 135 | 0 | ▶ | return unless @valid_vals; | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 136 | |||||||||||||||||||||
| 137 | 0 | ▶ | if ( @valid_vals < $target_domain->size ) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 138 | 0 | my %new_set = map { $_ => 1 } @valid_vals; | |||||||||||||||||||
| 139 | 0 | my $new_d = Logic::Relational::Domain->new( \%new_set ); | |||||||||||||||||||
| 140 | 0 | ▶ | if ( $new_d->is_bound ) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 141 | 0 | $curr_subst = | |||||||||||||||||||
| 142 | $curr_subst->bind( $target_id, $new_d->bound_value ); | ||||||||||||||||||||
| 143 | } | ||||||||||||||||||||
| 144 | else { | ||||||||||||||||||||
| 145 | 0 | $curr_subst = $curr_subst->bind( $target_id, $new_d ); | |||||||||||||||||||
| 146 | } | ||||||||||||||||||||
| 147 | } | ||||||||||||||||||||
| 148 | } | ||||||||||||||||||||
| 149 | |||||||||||||||||||||
| 150 | 0 | return $curr_subst; | |||||||||||||||||||
| 151 | } | ||||||||||||||||||||
| 152 | |||||||||||||||||||||
| 153 | 0 | ▶ | sub _is_candidate_feasible ( $target_id, $candidate, $unbound_ids_ref, | ||||||||||||||||||
|
Subroutine
_is_candidate_feasible: not called CC=1 SCAR=6.9
| |||||||||||||||||||||
| 154 | $var_states_ref, $curr_subst, $eval_sub, $op, $vars_ref ) | ||||||||||||||||||||
| 155 | { | ||||||||||||||||||||
| 156 | 0 | my @other_ids = grep { $_ ne $target_id } @$unbound_ids_ref; | |||||||||||||||||||
| 157 | |||||||||||||||||||||
| 158 | 0 | my $search; | |||||||||||||||||||
| 159 | 0 | ▶ | $search = sub ( $idx, $assignments ) { | ||||||||||||||||||
|
Subroutine
__ANON__: not called CC=7 SCAR=40.3
| |||||||||||||||||||||
| 160 | 0 | ▶ | if ( $idx > $#other_ids ) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 161 | 0 | my %vals_map; | |||||||||||||||||||
| 162 | 0 | for my $var (@$vars_ref) { | |||||||||||||||||||
| 163 | 0 | ▶ | my $vname = ref($var) eq 'Logic::Relational::Variable' ? $var->name : $var; | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 164 | 0 | $vname =~ s/^\$//; | |||||||||||||||||||
| 165 | 0 | my $v = $curr_subst->walk($var); | |||||||||||||||||||
| 166 | 0 | ▶ | if ( ref($v) eq 'Logic::Relational::Variable' ) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 167 | 0 | $vals_map{$vname} = $assignments->{ $v->id }; | |||||||||||||||||||
| 168 | } | ||||||||||||||||||||
| 169 | else { | ||||||||||||||||||||
| 170 | 0 | $vals_map{$vname} = $v; | |||||||||||||||||||
| 171 | } | ||||||||||||||||||||
| 172 | } | ||||||||||||||||||||
| 173 | 0 | my ( $left, $right ) = $eval_sub->( \%vals_map ); | |||||||||||||||||||
| 174 | 0 | return _compare( $op, $left, $right ); | |||||||||||||||||||
| 175 | } | ||||||||||||||||||||
| 176 | |||||||||||||||||||||
| 177 | 0 | my $id = $other_ids[$idx]; | |||||||||||||||||||
| 178 | 0 | my $d = $var_states_ref->{$id}{domain}; | |||||||||||||||||||
| 179 | 0 | for my $v ( $d->values ) { | |||||||||||||||||||
| 180 | 0 | $assignments->{$id} = $v; | |||||||||||||||||||
| 181 | 0 | ▶ | return 1 if $search->( $idx + 1, $assignments ); | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 182 | } | ||||||||||||||||||||
| 183 | 0 | return 0; | |||||||||||||||||||
| 184 | 0 | }; | |||||||||||||||||||
| 185 | |||||||||||||||||||||
| 186 | 0 | my %initial_assignments = ( $target_id => $candidate ); | |||||||||||||||||||
| 187 | 0 | return $search->( 0, \%initial_assignments ); | |||||||||||||||||||
| 188 | } | ||||||||||||||||||||
| 189 | |||||||||||||||||||||
| 190 | 15 | ▶ | sub freshen ( $self, $var_map ) { | ||||||||||||||||||
|
Subroutine
freshen: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||
| 191 | 15 | require Logic::Relational::DSL; | |||||||||||||||||||
| 192 | 15 | my @fresh_vars = map { $_->freshen($var_map) } @{ $self->{vars} }; | |||||||||||||||||||
| 193 | 15 | return ref($self)->new( $self->{op}, \@fresh_vars, $self->{eval_sub} ); | |||||||||||||||||||
| 194 | } | ||||||||||||||||||||
| 195 | |||||||||||||||||||||
| 196 | 0 | ▶ | sub is_ground ( $self, $subst ) { | ||||||||||||||||||
|
Subroutine
is_ground: not called CC=3 SCAR=24.8
Pod
documented
| |||||||||||||||||||||
| 197 | 0 | for my $var ( @{ $self->{vars} } ) { | |||||||||||||||||||
| 198 | 0 | ▶ | return 0 unless $self->term_is_ground( $var, $subst ); | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 199 | } | ||||||||||||||||||||
| 200 | 0 | return 1; | |||||||||||||||||||
| 201 | } | ||||||||||||||||||||
| 202 | |||||||||||||||||||||
| 203 | 30 | 1; | |||||||||||||||||||