automake-patches
[Top][All Lists]
Advanced

[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





reply via email to

[Prev in Thread] Current Thread [Next in Thread]