automake-patches
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Automake::Conditional::simplify (Quine-McCluskey)


From: Alexandre Duret-Lutz
Subject: Automake::Conditional::simplify (Quine-McCluskey)
Date: Sat, 16 Nov 2002 13:48:08 +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> And, dare I say, implement Quine-McCluskey minimization ;-)

You've just won another patch to review :)

Automake::Conditional::simplify obviously deserves more tests.
I've a few of them which aren't shown in this patch.  I'd like
to setup a test-suite for lib/Automake/ first.

2002-11-16  Alexandre Duret-Lutz  <address@hidden>

        * lib/Automake/ConditionalSet.pm (simplify): New method.
        (string): Call string for each Conditional.
        * automake.in (variable_not_always_defined_in_cond): Return
        a simplified ConditionalSet.
        (macro_define, require_variables): Adjust.
        * tests/Makefile.am (TEST): Add library3.test.
        * tests/library3.test: New file.
        * tests/pluseq9.test: Adjust.

Index: automake.in
===================================================================
RCS file: /cvs/automake/automake/automake.in,v
retrieving revision 1.1388
diff -u -r1.1388 automake.in
--- automake.in 14 Nov 2002 22:37:29 -0000      1.1388
+++ automake.in 16 Nov 2002 12:31:04 -0000
@@ -6184,7 +6184,7 @@
       push @res, $icond
        if ($cond->true_when ($icond)); # (3)
     }
-  return @res;
+  return (new Automake::ConditionalSet @res)->simplify;
 }
 
 # &macro_define($VAR, $OWNER, $TYPE, $COND, $VALUE, $WHERE)
@@ -6326,13 +6326,14 @@
          #   X += Z
          # should be rejected because X is not defined for all conditions
          # where `+=' applies.
-         my @undef_cond = variable_not_always_defined_in_cond $var, $cond;
-         if (@undef_cond != 0)
+         my $undef_cond = variable_not_always_defined_in_cond $var, $cond;
+         if (! $undef_cond->false)
            {
              err ($where,
                   "Cannot apply `+=' because `$var' is not defined "
                   . "in\nthe following conditions:\n  "
-                  . join ("\n  ", map { $_->string } @undef_cond)
+                  . join ("\n  ",
+                          map { $_->string } $undef_cond->conds)
                   . "\nEither define `$var' in these conditions,"
                   . " or use\n`+=' in the same conditions as"
                   . " the definitions.");
@@ -8961,15 +8962,15 @@
        if ((exists $var_value{$var} && exists $var_value{$var}{$cond})
            || exists $configure_vars{$var});
 
-      my @undef_cond = variable_not_always_defined_in_cond $var, $cond;
+      my $undef_cond = variable_not_always_defined_in_cond $var, $cond;
       next VARIABLE
-       unless @undef_cond;
+       if $undef_cond->false;
 
       my $text = "$reason`$var' is undefined\n";
-      if (@undef_cond && $undef_cond[0] != TRUE)
+      if (! $undef_cond->true)
        {
          $text .= ("in the following conditions:\n  "
-                   . join ("\n  ", map { $_->string } @undef_cond));
+                   . join ("\n  ", map { $_->string } $undef_cond->conds));
        }
 
       ++$res;
Index: lib/Automake/ConditionalSet.pm
===================================================================
RCS file: /cvs/automake/automake/lib/Automake/ConditionalSet.pm,v
retrieving revision 1.3
diff -u -r1.3 ConditionalSet.pm
--- lib/Automake/ConditionalSet.pm      15 Nov 2002 10:12:12 -0000      1.3
+++ lib/Automake/ConditionalSet.pm      16 Nov 2002 12:31:07 -0000
@@ -233,7 +233,7 @@
     }
   else
     {
-      $res = join (',', $self->conds);
+      $res = join (' | ', map { $_->string } $self->conds);
     }
 
   $self->{'string'} = $res;
@@ -358,6 +358,232 @@
   # It's tempting to also set $res->{'invert'} to $self, but that
   # is a bad idea as $self hasn't been normalized in any way.
   # (Different inputs can produce the same inverted set.)
+  return $res;
+}
+
+=item C<$simp = $set->simplify>
+
+Find prime implicants and return a simplified C<ConditionalSet>.
+
+=cut
+
+sub simplify ($)               # Based on Quime-McCluskey's algorithm.
+{
+  my ($self) = @_;
+
+  return $self->{'simplify'} if defined $self->{'simplify'};
+
+  my $nvars = 0;
+  my %var_rank;
+  my @rank_var;
+
+  # Initialization.
+  # Translate and-terms into bit string pairs: [$true, $false].
+  #
+  # Each variable is given a bit position in the strings.
+  #
+  # The first string in the pair tells wether a variable is
+  # uncomplemented in the term.
+  # The second string tells whether a variable is complemented.
+  # If a variable does not appear in the term, then its
+  # corresponding bit is unset in both strings.
+
+  # Order the resulting bit string pairs by the number of
+  # variables involved:
+  #   @{$subcubes[2]} is the list of string pairs involving two variables.
+  # (Level 0 is used for "TRUE".)
+  my @subcubes;
+
+  for my $and_conds ($self->conds)
+    {
+      my $true = 0;            # Bit string for uncomplemented variables.
+      my $false = 0;           # Bit string for complemented variables.
+
+      my @conds = $and_conds->conds;
+      for my $cond (@conds)
+       {
+         # Which variable is this condition about?
+         $cond =~ /^(.*_)(FALSE|TRUE)$/;
+
+         # Get the variabe's rank, or assign it a new one.
+         my $rank = $var_rank{$1};
+         if (! defined $rank)
+           {
+             $rank = $nvars++;
+             $var_rank{$1} = $rank;
+             $rank_var[$rank] = $1;
+           }
+
+         # Fire the relevant bit in the strings.
+         if ($2 eq 'FALSE')
+           {
+             $false |= 1 << $rank;
+           }
+         else
+           {
+             $true |= 1 << $rank;
+           }
+       }
+
+      # Register this term.
+      push @{$subcubes[1 + $#conds]}, [$true, $false];
+    }
+
+  # Real work.  Let's combine terms.
+
+  # Process terms in diminishing size order.  Those
+  # involving the maximum number of variables first.
+  for (my $m = $#subcubes; $m > 0; --$m)
+    {
+      my $m_subcubes = $#{$subcubes[$m]};
+      # Consider all terms with $m variables.
+      for (my $j = 0; $j <= $m_subcubes; ++$j)
+       {
+         my $tj = $subcubes[$m][$j];
+         next unless $tj;      # Skip deleted terms.
+         my $jtrue = $tj->[0];
+         my $jfalse = $tj->[1];
+
+         # Compare them with all other terms with $m variables.
+       COMBINATION:
+         for (my $k = $j + 1; $k <= $m_subcubes; ++$k)
+           {
+             my $tk = $subcubes[$m][$k];
+             next COMBINATION unless $tk; # Skip deleted terms.
+             my $ktrue = $tk->[0];
+             my $kfalse = $tk->[1];
+
+             # Two terms can combine if they differ only by one variable
+             # (i.e., a bit here), which is complemented in one term
+             # and uncomplemented in the other.
+             my $true  = $jtrue  ^ $ktrue;
+             my $false = $jfalse ^ $kfalse;
+             next COMBINATION if $true != $false;
+             # There should be exactly one bit set.
+             # (`$true & ($true - 1)' unsets the rightmost 1 bit in $true.)
+             next COMBINATION if $true == 0 || $true & ($true - 1);
+
+             # At this point we know we can combine the two terms.
+
+             # Mark these two terms as "combined", so we don't output
+             # them in the result.
+             $tj->[2] = 1;
+             $tk->[2] = 1;
+
+             # Actually combine the two terms.
+             my $ctrue  = $jtrue  & $ktrue;
+             my $cfalse = $jfalse & $kfalse;
+
+             # Don't add the combined term if it already exists.
+           DUP_SEARCH:
+             for my $c (@{$subcubes[$m - 1]})
+               {
+                 next DUP_SEARCH  if $ctrue  != $c->[0];
+                 next COMBINATION if $cfalse == $c->[1];
+               }
+             push @{$subcubes[$m - 1]}, [$ctrue, $cfalse];
+           }
+
+         # Filter-out implied terms.
+         #
+         # An and-term at level N might cover and-terms at level M>N.
+         # We need to mark all these covered terms so that they are
+         # not output in the result formula.
+         #
+         # If $tj was generated by combining two terms at level N+1,
+         # there two terms are already marked.  However there might be
+         # implied terms deeper.
+         #
+         #    For instance consider this input: "A_TRUE | A_TRUE C_FALSE".
+         #
+         #    This can also occur with and-term generated by the
+         #    combining algorith.  E.g., consider
+         #    "A_TRUE B_TRUE" | "A_TRUE B_FALSE" | "A_TRUE C_FALSE D_FALSE"
+         #     - at level 3 we can't combine "A_TRUE C_FALSE D_FALSE"
+         #     - at level 2 we can combine "A_TRUE B_TRUE" | "A_TRUE B_FALSE"
+         #       into "A_TRUE
+         #     - at level 1 we an't combine "A_TRUE"
+         #    so without more simplification we would output
+         #    "A_TRUE | A_TRUE C_FALSE D_FALSE"
+         #
+         #
+         # So let's filter-out and-terms which are implied by other
+         # and-terms. An and-term $tk is implied by an and-term $tj if $k
+         # involves more variables than $tj (i.e., N>M) and if
+         # all variables occurring in $tk also occur in A in the
+         # same state (complemented or uncomplemented.)
+
+         next if $tj->[2];     # Skip covered terms.  (If $tj covers some
+                               # terms, they will be filtered out when
+                               # we later process the term that covers $tj.)
+         for (my $n = $m + 1; $n <= $#subcubes; ++$n)
+           {
+             my $n_subcubes = $#{$subcubes[$n]};
+
+             for (my $k = 0; $k <= $n_subcubes; ++$k)
+               {
+                 my $tk = $subcubes[$n][$k];
+                 next if $tk->[2]; # Skip covered terms.
+                 my $ktrue = $tk->[0];
+                 my $kfalse = $tk->[1];
+
+                 next unless $ktrue == ($ktrue | $jtrue);
+                 next unless $kfalse == ($kfalse | $jfalse);
+
+                 delete $subcubes[$n][$k];
+               }
+           }
+       }
+    }
+
+  # Finally merge bit strings back into a Automake::ConditionalSet.
+
+  # If level 0 has been filled, we've found `TRUE'.  No need to translate
+  # anything.
+  return new Automake::ConditionalSet TRUE if $#{$subcubes[0]} >= 0;
+
+  # Otherwise, translate uncombined terms in other levels.
+  my @or_conds = ();
+  for my $mcubes (@subcubes)
+    {
+      for my $mcube (@$mcubes)
+       {
+         next unless $mcube;   # Skip deleted terms.
+         next if $mcube->[2];  # Skip combined terms.
+
+         my $true  = $mcube->[0];
+         my $false = $mcube->[1];
+
+         my @and_conds = ();
+
+         my $rank = 0;
+
+         while ($true > 0)
+           {
+             if ($true & 1)
+               {
+                 push @and_conds, $rank_var[$rank] . 'TRUE';
+               }
+             $true >>= 1;
+             ++$rank;
+           }
+         $rank = 0;
+         while ($false > 0)
+           {
+             if ($false & 1)
+               {
+                 push @and_conds, $rank_var[$rank] . 'FALSE';
+               }
+             $false >>= 1;
+             ++$rank;
+           }
+
+         push @or_conds, new Automake::Conditional @and_conds if @and_conds;
+       }
+    }
+
+  my $res = new Automake::ConditionalSet @or_conds;
+  $self->{'simplify'} = $res;
   return $res;
 }
 
Index: tests/Makefile.am
===================================================================
RCS file: /cvs/automake/automake/tests/Makefile.am,v
retrieving revision 1.452
diff -u -r1.452 Makefile.am
--- tests/Makefile.am   10 Nov 2002 14:25:16 -0000      1.452
+++ tests/Makefile.am   16 Nov 2002 12:31:07 -0000
@@ -230,6 +230,7 @@
 libobj12b.test \
 library.test \
 library2.test \
+library3.test \
 libtool.test \
 libtool2.test \
 libtool3.test \
Index: tests/Makefile.in
===================================================================
RCS file: /cvs/automake/automake/tests/Makefile.in,v
retrieving revision 1.587
diff -u -r1.587 Makefile.in
--- tests/Makefile.in   10 Nov 2002 14:25:23 -0000      1.587
+++ tests/Makefile.in   16 Nov 2002 12:31:09 -0000
@@ -322,6 +322,7 @@
 libobj12b.test \
 library.test \
 library2.test \
+library3.test \
 libtool.test \
 libtool2.test \
 libtool3.test \
Index: tests/library3.test
===================================================================
RCS file: tests/library3.test
diff -N tests/library3.test
--- /dev/null   1 Jan 1970 00:00:00 -0000
+++ tests/library3.test 16 Nov 2002 12:31:09 -0000
@@ -0,0 +1,59 @@
+#! /bin/sh
+# Copyright (C) 2002  Free Software Foundation, Inc.
+#
+# This file is part of GNU Automake.
+#
+# GNU Automake is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2, or (at your option)
+# any later version.
+#
+# GNU Automake is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with autoconf; see the file COPYING.  If not, write to
+# the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+# Boston, MA 02111-1307, USA.
+
+# Make sure Automake simplify conditions in diagnostics.
+
+. ./defs || exit 1
+
+set -e
+
+cat >>configure.in <<EOF
+AC_PROG_CC
+AM_CONDITIONAL([A], [:])
+AM_CONDITIONAL([B], [:])
+AM_CONDITIONAL([C], [:])
+AM_CONDITIONAL([D], [:])
+EOF
+
+cat > Makefile.am << 'END'
+if A
+if !B
+  RANLIB = anb
+else
+  RANLIB = ab
+endif
+endif
+if C
+  RANLIB = c
+endif
+if !C
+if D
+  RANLIB = ncd
+endif
+endif
+EXTRA_LIBRARIES = libfoo.a
+END
+
+$ACLOCAL
+$AUTOMAKE 2>stderr && exit 1
+cat stderr
+grep '^Makefile.am:.*:   A_FALSE C_FALSE D_FALSE$' stderr
+# Is there only one missing condition?
+test `grep ':  ' stderr | wc -l` = 1 || exit 1
Index: tests/pluseq9.test
===================================================================
RCS file: /cvs/automake/automake/tests/pluseq9.test,v
retrieving revision 1.3
diff -u -r1.3 pluseq9.test
--- tests/pluseq9.test  8 Sep 2002 13:07:55 -0000       1.3
+++ tests/pluseq9.test  16 Nov 2002 12:31:09 -0000
@@ -61,9 +61,7 @@
 #
 # Makefile.am:19: Cannot apply `+=' because `B' is not defined in
 # Makefile.am:19: the following conditions:
-# Makefile.am:19:   COND3_FALSE
-# Makefile.am:19:   COND1_FALSE COND2_FALSE
-# Makefile.am:19:   COND1_FALSE COND2_TRUE
+# Makefile.am:19:   COND1_FALSE COND3_FALSE
 # Makefile.am:19: Either define `B' in these conditions, or use
 # Makefile.am:19: `+=' in the same conditions as the definitions.
 #
@@ -71,10 +69,8 @@
 # COND1_FALSE (merging the last two conditions), so we'll support
 # this case in the check too.
 
-# Are COND3_FALSE and COND1_FALSE mentioned?
-grep ':.*COND3_FALSE$' stderr || exit 1
-grep ':.*COND1_FALSE' stderr || exit 1
-# Make sure there are no more than three missing conditions.
-test `grep ':  ' stderr | wc -l` -le 3 || exit 1
+grep ':  COND1_FALSE COND3_FALSE$' stderr || exit 1
+# Make sure there is exactly one missing condition.
+test `grep ':  ' stderr | wc -l` = 1 || exit 1
 
 :

-- 
Alexandre Duret-Lutz





reply via email to

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