| 1 | # -*- Perl -*- | ||||||||||||||||||||||||||
| 2 | # | ||||||||||||||||||||||||||
| 3 | # logic expression related routines. see Logic::Expr::Parser for how the | ||||||||||||||||||||||||||
| 4 | # expressions are built | ||||||||||||||||||||||||||
| 5 | |||||||||||||||||||||||||||
| 6 | package Logic::Expr; | ||||||||||||||||||||||||||
| 7 | 3 | our $VERSION = '0.02'; | |||||||||||||||||||||||||
| 8 | 3 | ▶ | use Scalar::Util 'refaddr'; | ||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||
| 9 | 3 | ▶ | use parent qw(Exporter); | ||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||
| 10 | |||||||||||||||||||||||||||
| 11 | # 'atoms' contains a name to a scalar reference in 'bools'; 'bools' is | ||||||||||||||||||||||||||
| 12 | # an array of unique atoms in an expression (for easy iteration by the | ||||||||||||||||||||||||||
| 13 | # "solutions" method); 'expr' is the parse tree of the expression as | ||||||||||||||||||||||||||
| 14 | # probably generated by Logic::Expr::Parser. 'bools' must be modified | ||||||||||||||||||||||||||
| 15 | # in-place to not break the scalar references from the other two | ||||||||||||||||||||||||||
| 16 | # structures. for example, given X&Y, | ||||||||||||||||||||||||||
| 17 | # * atoms - { X => \$bools[0], Y => \$bools[1] } | ||||||||||||||||||||||||||
| 18 | # * bools - [ 1, 1 ] | ||||||||||||||||||||||||||
| 19 | # * expr - [ LE_AND, ... ] | ||||||||||||||||||||||||||
| 20 | 3 | our ( @EXPORT_OK, %EXPORT_TAGS, %atoms, @bools ); | |||||||||||||||||||||||||
| 21 | |||||||||||||||||||||||||||
| 22 | 3 | ▶ | BEGIN { | ||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||
| 23 | 3 | my @all = qw(TRUE FALSE LE_NOT LE_AND LE_OR LE_COND LE_BICOND); | |||||||||||||||||||||||||
| 24 | 3 | @EXPORT_OK = @all; | |||||||||||||||||||||||||
| 25 | 3 | %EXPORT_TAGS = ( all => \@all ); | |||||||||||||||||||||||||
| 26 | } | ||||||||||||||||||||||||||
| 27 | |||||||||||||||||||||||||||
| 28 | sub TRUE () { 1 } | ||||||||||||||||||||||||||
| 29 | sub FALSE () { 0 } | ||||||||||||||||||||||||||
| 30 | # -1 is reserved for testing (FAKE_OP); 0 or 1 for ops would conflate | ||||||||||||||||||||||||||
| 31 | # with the prior should a truth value be assigned to an op slot | ||||||||||||||||||||||||||
| 32 | sub LE_NOT () { 2 } # ! ~ | ||||||||||||||||||||||||||
| 33 | sub LE_AND () { 3 } # & | ||||||||||||||||||||||||||
| 34 | sub LE_OR () { 4 } # | v | ||||||||||||||||||||||||||
| 35 | sub LE_COND () { 5 } # -> | ||||||||||||||||||||||||||
| 36 | sub LE_BICOND () { 6 } # == | ||||||||||||||||||||||||||
| 37 | |||||||||||||||||||||||||||
| 38 | 4 | ▶ | sub expr { $_[0]->{expr} } | ||||||||||||||||||||||||
|
Subroutine
expr: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||
| 39 | |||||||||||||||||||||||||||
| 40 | # generate a function that with suitable arguments evaluates the expr | ||||||||||||||||||||||||||
| 41 | sub codex | ||||||||||||||||||||||||||
| 42 | 8 | ▶ | { | ||||||||||||||||||||||||
|
Subroutine
codex: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||
| 43 | 8 | my ($self) = @_; | |||||||||||||||||||||||||
| 44 | 8 | my %atom2symbol = map { refaddr($atoms{$_}) => $_ } keys %atoms; | |||||||||||||||||||||||||
| 45 | my $code = $self->walk( | ||||||||||||||||||||||||||
| 46 | 8 | ▶ | sub { | ||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=6 SCAR=17.9
| |||||||||||||||||||||||||||
| 47 | 8 | my ( $op, $arg ) = @_; | |||||||||||||||||||||||||
| 48 | 8 | ▶ | if ( $op == LE_NOT ) { | ||||||||||||||||||||||||
|
Branch: 5 branches
| |||||||||||||||||||||||||||
| 49 | 1 | return "!$arg->[0]"; | |||||||||||||||||||||||||
| 50 | } elsif ( $op == LE_AND ) { | ||||||||||||||||||||||||||
| 51 | 1 | return "($arg->[0] and $arg->[1])"; | |||||||||||||||||||||||||
| 52 | } elsif ( $op == LE_OR ) { | ||||||||||||||||||||||||||
| 53 | 1 | return "($arg->[0] or $arg->[1])"; | |||||||||||||||||||||||||
| 54 | } elsif ( $op == LE_COND ) { | ||||||||||||||||||||||||||
| 55 | 3 | return "(!$arg->[0] or $arg->[1])"; | |||||||||||||||||||||||||
| 56 | } elsif ( $op == LE_BICOND ) { | ||||||||||||||||||||||||||
| 57 | 1 | return "!($arg->[0] xor $arg->[1])"; | |||||||||||||||||||||||||
| 58 | } else { | ||||||||||||||||||||||||||
| 59 | 1 | die "unknown op $op"; | |||||||||||||||||||||||||
| 60 | } | ||||||||||||||||||||||||||
| 61 | }, | ||||||||||||||||||||||||||
| 62 | 13 | ▶ | sub { q($p{) . $atom2symbol{ refaddr($_[0]) } . q(}) }, | ||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||
| 63 | 8 | ); | |||||||||||||||||||||||||
| 64 | 6 | eval "sub { my \%p = \@_; $code ? TRUE : FALSE }"; | |||||||||||||||||||||||||
| 65 | } | ||||||||||||||||||||||||||
| 66 | |||||||||||||||||||||||||||
| 67 | sub new | ||||||||||||||||||||||||||
| 68 | 10 | ▶ | { | ||||||||||||||||||||||||
|
Subroutine
new: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||
| 69 | 10 | my ( $class, %param ) = @_; | |||||||||||||||||||||||||
| 70 | 10 | my $self = { expr => $param{expr} }; | |||||||||||||||||||||||||
| 71 | 10 | bless $self, $class; | |||||||||||||||||||||||||
| 72 | 10 | return $self; | |||||||||||||||||||||||||
| 73 | } | ||||||||||||||||||||||||||
| 74 | |||||||||||||||||||||||||||
| 75 | 3 | ▶ | sub reset { %atoms = @bools = (); } | ||||||||||||||||||||||||
|
Subroutine
reset: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||
| 76 | |||||||||||||||||||||||||||
| 77 | # brute force all possible boolean states for an expression | ||||||||||||||||||||||||||
| 78 | sub solutions | ||||||||||||||||||||||||||
| 79 | 6 | ▶ | { | ||||||||||||||||||||||||
|
Subroutine
solutions: called CC=9 SCAR=22.0
Pod
documented
| |||||||||||||||||||||||||||
| 80 | 6 | my ($self, $noprefix) = @_; | |||||||||||||||||||||||||
| 81 | 6 | my (@orig, $ret, @solutions); | |||||||||||||||||||||||||
| 82 | 6 | for my $x (@bools) { | |||||||||||||||||||||||||
| 83 | 12 | push @orig, $x; | |||||||||||||||||||||||||
| 84 | 12 | $x = TRUE; | |||||||||||||||||||||||||
| 85 | } | ||||||||||||||||||||||||||
| 86 | 6 | ▶ | $ret = _solve( $self->{expr} ) ? TRUE : FALSE; | ||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||
| 87 | 6 | ▶ | push @solutions, $noprefix ? $ret : [ [@bools], $ret ]; | ||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||
| 88 | # the reverse index ordering is to match that of the logic book, | ||||||||||||||||||||||||||
| 89 | # backwards binary counting | ||||||||||||||||||||||||||
| 90 | 6 | my $i = $#bools; | |||||||||||||||||||||||||
| 91 | 6 | ▶ | while ( $i >= 0 ) { | ||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||
| 92 | 36 | ▶ | if ( $bools[$i] ) { | ||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||
| 93 | 18 | $bools[$i] = FALSE; | |||||||||||||||||||||||||
| 94 | 18 | ▶ | $ret = _solve( $self->{expr} ) ? TRUE : FALSE; | ||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||
| 95 | 18 | ▶ | push @solutions, $noprefix ? $ret : [ [@bools], $ret ]; | ||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||
| 96 | 18 | $i = $#bools; | |||||||||||||||||||||||||
| 97 | } else { | ||||||||||||||||||||||||||
| 98 | 18 | $bools[ $i-- ] = TRUE; | |||||||||||||||||||||||||
| 99 | } | ||||||||||||||||||||||||||
| 100 | } | ||||||||||||||||||||||||||
| 101 | 6 | for my $x (@bools) { $x = shift @orig } | |||||||||||||||||||||||||
| 102 | 6 | return \@solutions; | |||||||||||||||||||||||||
| 103 | } | ||||||||||||||||||||||||||
| 104 | |||||||||||||||||||||||||||
| 105 | # solve the expression using the current state in bools | ||||||||||||||||||||||||||
| 106 | 4 | ▶ | sub solve { _solve( $_[0]->{expr} ) ? TRUE : FALSE } | ||||||||||||||||||||||||
|
Subroutine
solve: called CC=2 SCAR=6.9
Pod
documented
Branch: 1 branch
| |||||||||||||||||||||||||||
| 107 | |||||||||||||||||||||||||||
| 108 | sub _solve | ||||||||||||||||||||||||||
| 109 | 75 | ▶ | { | ||||||||||||||||||||||||
|
Subroutine
_solve: called CC=11 SCAR=24.0
| |||||||||||||||||||||||||||
| 110 | 75 | my ($ptr) = @_; | |||||||||||||||||||||||||
| 111 | 75 | my $rt = ref $ptr; | |||||||||||||||||||||||||
| 112 | 75 | ▶ | return $$ptr if $rt eq 'SCALAR'; # lookup from bools | ||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||
| 113 | 34 | ▶ | if ( $rt eq 'ARRAY' ) { | ||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||
| 114 | 33 | ▶ | if ( $ptr->[0] == LE_NOT ) { | ||||||||||||||||||||||||
|
Branch: 5 branches
| |||||||||||||||||||||||||||
| 115 | 6 | return !_solve( $ptr->[1] ); | |||||||||||||||||||||||||
| 116 | } elsif ( $ptr->[0] == LE_AND ) { | ||||||||||||||||||||||||||
| 117 | 4 | ▶ | return _solve( $ptr->[1] ) && _solve( $ptr->[2] ); | ||||||||||||||||||||||||
|
Condition100%3/3
_solve($ptr->[1]) && _solve($ptr->[2])
MC/DC100%2/2
_solve($ptr->[1]) && _solve($ptr->[2])
_solve($ptr->[1])
_solve($ptr->[2])
Truth table100%3/3
A && B
A= _solve($ptr->[1])B= _solve($ptr->[2])
| |||||||||||||||||||||||||||
| 118 | } elsif ( $ptr->[0] == LE_OR ) { | ||||||||||||||||||||||||||
| 119 | 8 | ▶ | return _solve( $ptr->[1] ) || _solve( $ptr->[2] ); | ||||||||||||||||||||||||
|
Condition100%3/3
_solve($ptr->[1]) || _solve($ptr->[2])
MC/DC100%2/2
_solve($ptr->[1]) || _solve($ptr->[2])
_solve($ptr->[1])
_solve($ptr->[2])
Truth table100%3/3
A || B
A= _solve($ptr->[1])B= _solve($ptr->[2])
| |||||||||||||||||||||||||||
| 120 | } elsif ( $ptr->[0] == LE_COND ) { | ||||||||||||||||||||||||||
| 121 | 10 | ▶ | return !_solve( $ptr->[1] ) || _solve( $ptr->[2] ); | ||||||||||||||||||||||||
|
Condition100%3/3
!_solve($ptr->[1]) || _solve($ptr->[2])
MC/DC100%2/2
!_solve($ptr->[1]) || _solve($ptr->[2])
!_solve($ptr->[1])
_solve($ptr->[2])
Truth table100%3/3
not(A) || B
A= !_solve($ptr->[1])B= _solve($ptr->[2])
| |||||||||||||||||||||||||||
| 122 | } elsif ( $ptr->[0] == LE_BICOND ) { | ||||||||||||||||||||||||||
| 123 | 4 | return !( _solve( $ptr->[1] ) ^ _solve( $ptr->[2] ) ); | |||||||||||||||||||||||||
| 124 | } | ||||||||||||||||||||||||||
| 125 | 1 | die "unknown op $ptr->[0]"; | |||||||||||||||||||||||||
| 126 | } | ||||||||||||||||||||||||||
| 127 | 1 | die "unexpected reference type '$rt'"; | |||||||||||||||||||||||||
| 128 | } | ||||||||||||||||||||||||||
| 129 | |||||||||||||||||||||||||||
| 130 | sub walk | ||||||||||||||||||||||||||
| 131 | 8 | ▶ | { | ||||||||||||||||||||||||
|
Subroutine
walk: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||
| 132 | 8 | my ( $self, $opfn, $atomfn ) = @_; | |||||||||||||||||||||||||
| 133 | 8 | _walk( $self->{expr}, $opfn, $atomfn ); | |||||||||||||||||||||||||
| 134 | } | ||||||||||||||||||||||||||
| 135 | |||||||||||||||||||||||||||
| 136 | sub _walk | ||||||||||||||||||||||||||
| 137 | 10 | ▶ | { | ||||||||||||||||||||||||
|
Subroutine
_walk: called CC=5 SCAR=16.1
| |||||||||||||||||||||||||||
| 138 | 10 | my ( $ptr, $opfn, $atomfn ) = @_; | |||||||||||||||||||||||||
| 139 | 10 | my $rt = ref $ptr; | |||||||||||||||||||||||||
| 140 | 10 | ▶ | if ( $rt eq 'SCALAR' ) { | ||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||
| 141 | 1 | return $atomfn->($ptr); | |||||||||||||||||||||||||
| 142 | } elsif ( $rt eq 'ARRAY' ) { | ||||||||||||||||||||||||||
| 143 | return $opfn->( | ||||||||||||||||||||||||||
| 144 | $ptr->[0], | ||||||||||||||||||||||||||
| 145 | [ map { | ||||||||||||||||||||||||||
| 146 | 8 | my $type = ref $ptr->[$_]; | |||||||||||||||||||||||||
| 147 | 16 | ▶ | if ( $type eq 'SCALAR' ) { | ||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||
| 148 | 12 | $atomfn->( $ptr->[$_] ); | |||||||||||||||||||||||||
| 149 | } elsif ( $type eq 'ARRAY' ) { | ||||||||||||||||||||||||||
| 150 | 2 | _walk( $ptr->[$_], $opfn, $atomfn ); | |||||||||||||||||||||||||
| 151 | } else { | ||||||||||||||||||||||||||
| 152 | () # unary negation, probably | ||||||||||||||||||||||||||
| 153 | 2 | } | |||||||||||||||||||||||||
| 154 | } 1 .. 2 | ||||||||||||||||||||||||||
| 155 | ] | ||||||||||||||||||||||||||
| 156 | ); | ||||||||||||||||||||||||||
| 157 | } else { | ||||||||||||||||||||||||||
| 158 | 1 | die "unexpected reference type '$rt'"; | |||||||||||||||||||||||||
| 159 | } | ||||||||||||||||||||||||||
| 160 | } | ||||||||||||||||||||||||||
| 161 | |||||||||||||||||||||||||||
| 162 | 3 | 1; | |||||||||||||||||||||||||
| 163 | __END__ | ||||||||||||||||||||||||||