Automake::Conditional::invert

[Alexandre Duret-Lutz]

>>> "Raja" == Raja R Harinath <address@hidden> writes:

[...]

 Raja> If you really want to worry about scalability, A::CS::invert would be
 Raja> better written as a product-of-sums to sum-of-products converter,
 Raja> rather than explicitly enumerating every truth-value candidate.

[...]

Here is my proposal.  make check is running.

2002-11-19  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.
        Suggested by Raja R Harinath.
        * lib/Automake/tests/ConditionalSet.pl (test_invert): Update.
        * automake.in (condition_negate): Move ...
        * lib/Automake/Conditional.pm (negate_condition): ... here.

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 19 Nov 2002 21:09:02 -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 19 Nov 2002 21:09:03 -0000
@@ -443,6 +443,23 @@
   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
 
 L<Automake::ConditionalSet>.
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      19 Nov 2002 21:09:06 -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;
@@ -332,15 +332,37 @@
 
   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 = (&TRUE => 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
+  #
+  # We store each product (i.e., each Conditional) in a Hash, so
+  # that duplicates get removed automatically.
+  foreach my $set ($self->conds)
+    {
+      my @old = values %res;
+      %res = ();
+      for my $cond ($set->conds)
+       {
+         my $negstr = Automake::Conditional::condition_negate $cond;
+         my $neg = new Automake::Conditional $negstr;
+         foreach my $r (@old)
+           {
+             my $m = $r->merge ($neg);
+             $res{$m} = $m;
+           }
+       }
+    }
 
+  my $res = new Automake::ConditionalSet values %res;
   # Cache result.
   $self->{'invert'} = $res;
   # It's tempting to also set $res->{'invert'} to $self, but that
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        19 Nov 2002 21:09:08 -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