[Top][All Lists]
[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;
}
# ¯o_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
- Automake::Conditional::simplify (Quine-McCluskey),
Alexandre Duret-Lutz <=
- 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, 2002/11/20
- Re: Automake::Conditional::invert, Raja R Harinath, 2002/11/20