[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Automake::Conditional::invert
From: |
Alexandre Duret-Lutz |
Subject: |
Re: Automake::Conditional::invert |
Date: |
Wed, 20 Nov 2002 12:09:09 +0100 |
User-agent: |
Gnus/5.090008 (Oort Gnus v0.08) Emacs/20.7 (i386-debian-linux-gnu) |
>>> "Raja" == Raja R Harinath <address@hidden> writes:
[...]
Raja> Noting the handling of the %res in 'invert', you might as well use the
Raja> ConditionalSet constructor. There are two slightly more primitive
Raja> operations that this can be written in terms of.
Raja> * method A::C::not which returns an ConditionalSet
Raja> * method A::CS::multiply that takes another ConditionalSet,
Raja> multiplies it with $self and returns a new ConditionalSet
Raja> $res = new A::CS A::C::TRUE;
Raja> $res = $res->multiply $cond->not
Raja> foreach $cond ($self->conds);
Raja> return $res;
Ok. I'm checking this in.
2002-11-20 Alexandre Duret-Lutz <address@hidden>
* lib/Automake/ConditionalSet.pm (conds): Use value() to simplify.
(invert): Rewrite as a product-of-sums to sum-of-products converter.
(_multiply, multiply): New functions.
* lib/Automake/Conditional.pm (not): New function.
* lib/Automake/tests/ConditionalSet.pl (test_invert): Update.
* automake.in (condition_negate): Move ...
* lib/Automake/Conditional.pm (negate_condition): ... here.
Suggested by Raja R Harinath.
Index: automake.in
===================================================================
RCS file: /cvs/automake/automake/automake.in,v
retrieving revision 1.1389
diff -u -r1.1389 automake.in
--- automake.in 19 Nov 2002 20:02:38 -0000 1.1389
+++ automake.in 20 Nov 2002 11:01:36 -0000
@@ -5925,21 +5925,6 @@
################################################################
-# $NEGATION
-# condition_negate ($COND)
-# ------------------------
-sub condition_negate ($)
-{
- my ($cond) = @_;
-
- $cond =~ s/TRUE$/TRUEO/;
- $cond =~ s/FALSE$/TRUE/;
- $cond =~ s/TRUEO$/FALSE/;
-
- return $cond;
-}
-
-
## ------------------------------ ##
## Handling the condition stack. ##
## ------------------------------ ##
@@ -5957,7 +5942,7 @@
$cond = "${cond}_TRUE"
unless $cond =~ /^TRUE|FALSE$/;
- $cond = condition_negate ($cond)
+ $cond = Automake::Conditional::condition_negate ($cond)
if $negate;
push (@cond_stack, $cond);
@@ -5979,14 +5964,15 @@
return;
}
- $cond_stack[$#cond_stack] = condition_negate ($cond_stack[$#cond_stack]);
+ $cond_stack[$#cond_stack] =
+ Automake::Conditional::condition_negate ($cond_stack[$#cond_stack]);
# If $COND is given, check against it.
if (defined $cond)
{
$cond = "${cond}_TRUE"
unless $cond =~ /^TRUE|FALSE$/;
- $cond = condition_negate ($cond)
+ $cond = Automake::Conditional::condition_negate ($cond)
if $negate;
err ($where, "else reminder ($negate$cond) incompatible with "
@@ -6018,7 +6004,7 @@
{
$cond = "${cond}_TRUE"
unless $cond =~ /^TRUE|FALSE$/;
- $cond = condition_negate ($cond)
+ $cond = Automake::Conditional::condition_negate ($cond)
if $negate;
err ($where, "endif reminder ($negate$cond) incompatible with "
Index: lib/Automake/Conditional.pm
===================================================================
RCS file: /cvs/automake/automake/lib/Automake/Conditional.pm,v
retrieving revision 1.4
diff -u -r1.4 Conditional.pm
--- lib/Automake/Conditional.pm 14 Nov 2002 16:12:00 -0000 1.4
+++ lib/Automake/Conditional.pm 20 Nov 2002 11:01:38 -0000
@@ -77,6 +77,9 @@
# $other and $cond are implied by $both.)
@conds = Automake::Conditional::reduce ($other, $both, $cond);
+ # Invert a Conditional. This returns a ConditionalSet.
+ $set = $both->not;
+
=head1 DESCRIPTION
A C<Conditional> is a conjunction of atomic conditions. In Automake they
@@ -394,6 +397,28 @@
return 0;
}
+=item C<$cond-E<gt>not>
+
+Return a negation of @<$cond> as a list of C<Conditional>s.
+This list should be used to construct a C<ConditionalSet>
+(we cannot return a C<ConditionalSet> from C<Automake::Conditional>,
+because that would make these two packages interdependent).
+
+=cut
+
+sub not ($ )
+{
+ my ($self) = @_;
+ return @{$self->{'not'}} if defined $self->{'not'};
+ my @res;
+ for my $cond ($self->conds)
+ {
+ push @res, new Automake::Conditional &condition_negate ($cond);
+ }
+ $self->{'not'} = address@hidden;
+ return @res;
+}
+
=head2 Other helper functions
=over 4
@@ -441,6 +466,23 @@
return TRUE if @ret == 0;
return @ret;
+}
+
+=item C<condition_negate ($condstr)>
+
+Negate a condition string.
+
+=cut
+
+sub condition_negate ($)
+{
+ my ($cond) = @_;
+
+ $cond =~ s/TRUE$/TRUEO/;
+ $cond =~ s/FALSE$/TRUE/;
+ $cond =~ s/TRUEO$/FALSE/;
+
+ return $cond;
}
=head1 SEE ALSO
Index: lib/Automake/ConditionalSet.pm
===================================================================
RCS file: /cvs/automake/automake/lib/Automake/ConditionalSet.pm,v
retrieving revision 1.5
diff -u -r1.5 ConditionalSet.pm
--- lib/Automake/ConditionalSet.pm 19 Nov 2002 20:02:39 -0000 1.5
+++ lib/Automake/ConditionalSet.pm 20 Nov 2002 11:01:41 -0000
@@ -153,7 +153,7 @@
{
my ($self) = @_;
return @{$self->{'conds'}} if exists $self->{'conds'};
- my @conds = map { $self->{'hash'}{$_} } (keys %{$self->{'hash'}});
+ my @conds = values %{$self->{'hash'}};
@conds = sort { $a->string cmp $b->string } @conds;
$self->{'conds'} = address@hidden;
return @conds;
@@ -309,10 +309,53 @@
return $res;
}
-=item C<$inv = $res-E<gt>invert>
+=item C<$prod = $set1->multiply ($set2)>
+
+Multiply to conditional sets.
+
+ my $set1 = new Automake::ConditionalSet
+ (new Automake::Conditional ("A_TRUE"),
+ new Automake::Conditional ("B_TRUE"));
+ my $set2 = new Automake::ConditionalSet
+ (new Automake::Conditional ("C_FALSE"),
+ new Automake::Conditional ("D_FALSE"));
+
+C<$set1-E<gt>multiply ($set2)> will return
+
+ new Automake::ConditionalSet
+ (new Automake::Conditional ("A_TRUE", "C_FALSE"),
+ new Automake::Conditional ("B_TRUE", "C_FALSE"),;
+ new Automake::Conditional ("A_TRUE", "D_FALSE"),
+ new Automake::Conditional ("B_TRUE", "D_FALSE"));
+
+=cut
+
+# Same as multiply() but take a list of Conditonal as second argument.
+# We use this in invert().
+sub _multiply ($@)
+{
+ my ($self, @set) = @_;
+ my @res = ();
+ foreach my $selfcond ($self->conds)
+ {
+ foreach my $setcond (@set)
+ {
+ push @res, $selfcond->merge ($setcond);
+ }
+ }
+ return new Automake::ConditionalSet @res;
+}
+
+sub multiply ($$)
+{
+ my ($self, $set) = @_;
+ return $self->_multiply ($set->conds);
+}
+
+=item C<$inv = $set-E<gt>invert>
Invert a C<ConditionalSet>. Return a C<ConditionalSet> which is true
-when C<$res> is false, and vice-versa.
+when C<$set> is false, and vice-versa.
my $set = new Automake::ConditionalSet
(new Automake::Conditional ("A_TRUE", "B_TRUE"),
@@ -332,14 +375,21 @@
return $self->{'invert'} if defined $self->{'invert'};
- # Generate permutations for all subconditions.
- my @perm = $self->permutations->conds;
+ # The invert of an empty ConditionalSet is TRUE.
+ my $res = new Automake::ConditionalSet TRUE;
- # Now remove all conditions which imply one of the input conditions.
- my @conds = $self->conds;
- my @notconds =
- grep { ! $_->implies_any (@conds) } $self->permutations->conds;
- my $res = new Automake::ConditionalSet @notconds;
+ # !((a.b)+(c.d)+(e.f))
+ # = (!a+!b).(!c+!d).(!e+!f)
+ # We develop this into a sum of product iteratively, starting from TRUE:
+ # 1) TRUE
+ # 2) TRUE.!a + TRUE.!b
+ # 3) TRUE.!a.!c + TRUE.!b.!c + TRUE.!a.!d + TRUE.!b.!d
+ # 4) TRUE.!a.!c.!e + TRUE.!b.!c.!e + TRUE.!a.!d.!e + TRUE.!b.!d.!e
+ # + TRUE.!a.!c.!f + TRUE.!b.!c.!f + TRUE.!a.!d.!f + TRUE.!b.!d.!f
+ foreach my $cond ($self->conds)
+ {
+ $res = $res->_multiply ($cond->not);
+ }
# Cache result.
$self->{'invert'} = $res;
Index: lib/Automake/tests/ConditionalSet.pl
===================================================================
RCS file: /cvs/automake/automake/lib/Automake/tests/ConditionalSet.pl,v
retrieving revision 1.2
diff -u -r1.2 ConditionalSet.pl
--- lib/Automake/tests/ConditionalSet.pl 19 Nov 2002 20:02:39 -0000
1.2
+++ lib/Automake/tests/ConditionalSet.pl 20 Nov 2002 11:01:41 -0000
@@ -109,11 +109,10 @@
[[["COND1_TRUE", "COND2_TRUE"],
["COND3_FALSE", "COND2_TRUE"]],
- [["COND1_FALSE","COND2_FALSE","COND3_FALSE"],
- ["COND1_TRUE", "COND2_FALSE","COND3_FALSE"],
- ["COND1_FALSE","COND2_FALSE","COND3_TRUE"],
- ["COND1_TRUE", "COND2_FALSE","COND3_TRUE"],
- ["COND1_FALSE","COND2_TRUE", "COND3_TRUE"]]],
+ [["COND2_FALSE"],
+ ["COND2_FALSE", "COND3_TRUE"],
+ ["COND1_FALSE", "COND2_FALSE"],
+ ["COND1_FALSE", "COND3_TRUE"]]],
[[["COND1_TRUE", "COND2_TRUE"],
["TRUE"]],
@@ -121,9 +120,8 @@
[[["COND1_TRUE", "COND2_TRUE"],
["FALSE"]],
- [["COND1_FALSE", "COND2_TRUE"],
- ["COND1_FALSE", "COND2_FALSE"],
- ["COND1_TRUE", "COND2_FALSE"]]],
+ [["COND1_FALSE"],
+ ["COND2_FALSE"]]],
[[["COND1_TRUE"],
["COND2_FALSE"]],
@@ -137,7 +135,8 @@
my $inv = $set->invert;
if ($inv != $res)
{
- print " (I) " . $inv->string . ' != ' . $res->string . "\n";
+ print " (I) " . $set->string . "\n\t"
+ . $inv->string . ' != ' . $res->string . "\n";
return 1;
}
}
--
Alexandre Duret-Lutz
- Automake::Conditional::simplify (Quine-McCluskey), Alexandre Duret-Lutz, 2002/11/16
- Re: Automake::Conditional::simplify (Quine-McCluskey), Raja R Harinath, 2002/11/16
- Automake::Conditional::invert, Alexandre Duret-Lutz, 2002/11/19
- Re: Automake::Conditional::invert, Raja R Harinath, 2002/11/19
- Re: Automake::Conditional::invert,
Alexandre Duret-Lutz <=
- Re: Automake::Conditional::invert, Raja R Harinath, 2002/11/20
- Re: Automake::Conditional::invert, Alexandre Duret-Lutz, 2002/11/20
- Re: Automake::Conditional::invert, Raja R Harinath, 2002/11/20
- FYI: make_conditional_string, Alexandre Duret-Lutz, 2002/11/21
FYI: simplify variable_not_always_defined_in_cond, Alexandre Duret-Lutz, 2002/11/20