lib/Automake/DisjConditions.pm

   1 # Copyright (C) 1997, 2001, 2002, 2003, 2004, 2006  Free Software Foundation, Inc.
   2
   3 # This program is free software; you can redistribute it and/or modify
   4 # it under the terms of the GNU General Public License as published by
   5 # the Free Software Foundation; either version 3, or (at your option)
   6 # any later version.
   7
   8 # This program is distributed in the hope that it will be useful,
   9 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 # GNU General Public License for more details.
  12
  13 # You should have received a copy of the GNU General Public License
  14 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
  15
  16 package Automake::DisjConditions;
  17
  18 use Carp;
  19 use strict;
  20 use Automake::Condition qw/TRUE FALSE/;
  21
  22 =head1 NAME
  23
  24 Automake::DisjConditions - record a disjunction of Conditions
  25
  26 =head1 SYNOPSIS
  27
  28   use Automake::Condition;
  29   use Automake::DisjConditions;
  30
  31   # Create a Condition to represent "COND1 and not COND2".
  32   my $cond = new Automake::Condition "COND1_TRUE", "COND2_FALSE";
  33   # Create a Condition to represent "not COND3".
  34   my $other = new Automake::Condition "COND3_FALSE";
  35
  36   # Create a DisjConditions to represent
  37   #   "(COND1 and not COND2) or (not COND3)"
  38   my $set = new Automake::DisjConditions $cond, $other;
  39
  40   # Return the list of Conditions involved in $set.
  41   my @conds = $set->conds;
  42
  43   # Return one of the Condition involved in $set.
  44   my $cond = $set->one_cond;
  45
  46   # Return true iff $set is always true (i.e. its subconditions
  47   # cover all cases).
  48   if ($set->true) { ... }
  49
  50   # Return false iff $set is always false (i.e. is empty, or contains
  51   # only false conditions).
  52   if ($set->false) { ... }
  53
  54   # Return a string representing the DisjConditions.
  55   #   "COND1_TRUE COND2_FALSE | COND3_FALSE"
  56   my $str = $set->string;
  57
  58   # Return a human readable string representing the DisjConditions.
  59   #   "(COND1 and !COND2) or (!COND3)"
  60   my $str = $set->human;
  61
  62   # Merge (OR) several DisjConditions.
  63   my $all = $set->merge($set2, $set3, ...)
  64
  65   # Invert a DisjConditions, i.e., create a new DisjConditions
  66   # that complements $set.
  67   my $inv = $set->invert;
  68
  69   # Multiply two DisjConditions.
  70   my $prod = $set1->multiply ($set2);
  71
  72   # Return the subconditions of a DisjConditions with respect to
  73   # a Condition.  See the description for a real example.
  74   my $subconds = $set->sub_conditions ($cond);
  75
  76   # Check whether a new definition in condition $cond would be
  77   # ambiguous w.r.t. existing definitions in $set.
  78   ($msg, $ambig_cond) = $set->ambiguous_p ($what, $cond);
  79
  80 =head1 DESCRIPTION
  81
  82 A C<DisjConditions> is a disjunction of C<Condition>s.  In Automake
  83 they are used to represent the conditions into which Makefile
  84 variables and Makefile rules are defined.
  85
  86 If the variable C<VAR> is defined as
  87
  88   if COND1
  89     if COND2
  90       VAR = value1
  91     endif
  92   endif
  93   if !COND3
  94     if COND4
  95       VAR = value2
  96     endif
  97   endif
  98
  99 then it will be associated a C<DisjConditions> created with
 100 the following statement.
 101
 102   new Automake::DisjConditions
 103     (new Automake::Condition ("COND1_TRUE", "COND2_TRUE"),
 104      new Automake::Condition ("COND3_FALSE", "COND4_TRUE"));
 105
 106 As you can see, a C<DisjConditions> is made from a list of
 107 C<Condition>s.  Since C<DisjConditions> is a disjunction, and
 108 C<Condition> is a conjunction, the above can be read as
 109 follows.
 110
 111   (COND1 and COND2) or ((not COND3) and COND4)
 112
 113 That's indeed the condition into which C<VAR> has a value.
 114
 115 Like C<Condition> objects, a C<DisjConditions> object is unique
 116 with respect to its conditions.  Two C<DisjConditions> objects created
 117 for the same set of conditions will have the same address.  This makes
 118 it easy to compare C<DisjConditions>s: just compare the references.
 119
 120 =head2 Methods
 121
 122 =over 4
 123
 124 =item C<$set = new Automake::DisjConditions [@conds]>
 125
 126 Create a C<DisjConditions> object from the list of C<Condition>
 127 objects passed in arguments.
 128
 129 If the C<@conds> list is empty, the C<DisjConditions> is assumed to be
 130 false.
 131
 132 As explained previously, the reference (object) returned is unique
 133 with respect to C<@conds>.  For this purpose, duplicate elements are
 134 ignored.
 135
 136 =cut
 137
 138 # Keys in this hash are DisjConditions strings. Values are the
 139 # associated object DisjConditions.  This is used by `new' to reuse
 140 # DisjConditions objects with identical conditions.
 141 use vars '%_disjcondition_singletons';
 142
 143 sub new ($;@)
 144 {
 145   my ($class, @conds) = @_;
 146   my @filtered_conds = ();
 147   for my $cond (@conds)
 148     {
 149       confess "`$cond' isn't a reference" unless ref $cond;
 150       confess "`$cond' isn't an Automake::Condition"
 151         unless $cond->isa ("Automake::Condition");
 152
 153       # This is a disjunction of conditions, so we drop
 154       # false conditions.  We'll always treat an "empty"
 155       # DisjConditions as false for this reason.
 156       next if $cond->false;
 157
 158       push @filtered_conds, $cond;
 159     }
 160
 161   my $string;
 162   if (@filtered_conds)
 163     {
 164       @filtered_conds = sort { $a->string cmp $b->string } @filtered_conds;
 165       $string = join (' | ', map { $_->string } @filtered_conds);
 166     }
 167   else
 168     {
 169       $string = 'FALSE';
 170     }
 171
 172   # Return any existing identical DisjConditions.
 173   my $me = $_disjcondition_singletons{$string};
 174   return $me if $me;
 175
 176   # Else, create a new DisjConditions.
 177
 178   # Store conditions as keys AND as values, because blessed
 179   # objects are converted to string when used as keys (so
 180   # at least we still have the value when we need to call
 181   # a method).
 182   my %h = map {$_ => $_} @filtered_conds;
 183
 184   my $self = {
 185     hash => \%h,
 186     string => $string,
 187     conds => \@filtered_conds,
 188   };
 189   bless $self, $class;
 190
 191   $_disjcondition_singletons{$string} = $self;
 192   return $self;
 193 }
 194
 195 =item C<@conds = $set-E<gt>conds>
 196
 197 Return the list of C<Condition> objects involved in C<$set>.
 198
 199 =cut
 200
 201 sub conds ($ )
 202 {
 203   my ($self) = @_;
 204   return @{$self->{'conds'}};
 205 }
 206
 207 =item C<$cond = $set-E<gt>one_cond>
 208
 209 Return one C<Condition> object involved in C<$set>.
 210
 211 =cut
 212
 213 sub one_cond ($)
 214 {
 215   my ($self) = @_;
 216   return (%{$self->{'hash'}},)[1];
 217 }
 218
 219 =item C<$et = $set-E<gt>false>
 220
 221 Return 1 iff the C<DisjConditions> object is always false (i.e., if it
 222 is empty, or if it contains only false C<Condition>s). Return 0
 223 otherwise.
 224
 225 =cut
 226
 227 sub false ($ )
 228 {
 229   my ($self) = @_;
 230   return 0 == keys %{$self->{'hash'}};
 231 }
 232
 233 =item C<$et = $set-E<gt>true>
 234
 235 Return 1 iff the C<DisjConditions> object is always true (i.e. covers all
 236 conditions). Return 0 otherwise.
 237
 238 =cut
 239
 240 sub true ($ )
 241 {
 242   my ($self) = @_;
 243   return $self->invert->false;
 244 }
 245
 246 =item C<$str = $set-E<gt>string>
 247
 248 Build a string which denotes the C<DisjConditions>.
 249
 250 =cut
 251
 252 sub string ($ )
 253 {
 254   my ($self) = @_;
 255   return $self->{'string'};
 256 }
 257
 258 =item C<$cond-E<gt>human>
 259
 260 Build a human readable string which denotes the C<DisjConditions>.
 261
 262 =cut
 263
 264 sub human ($ )
 265 {
 266   my ($self) = @_;
 267
 268   return $self->{'human'} if defined $self->{'human'};
 269
 270   my $res = '';
 271   if ($self->false)
 272     {
 273       $res = 'FALSE';
 274     }
 275   else
 276     {
 277       my @c = $self->conds;
 278       if (1 == @c)
 279         {
 280           $res = $c[0]->human;
 281         }
 282       else
 283         {
 284           $res = '(' . join (') or (', map { $_->human } $self->conds) . ')';
 285         }
 286     }
 287   $self->{'human'} = $res;
 288   return $res;
 289 }
 290
 291
 292 =item C<$newcond = $cond-E<gt>merge (@otherconds)>
 293
 294 Return a new C<DisjConditions> which is the disjunction of
 295 C<$cond> and C<@otherconds>.  Items in C<@otherconds> can be
 296 @C<Condition>s or C<DisjConditions>.
 297
 298 =cut
 299
 300 sub merge ($@)
 301 {
 302   my ($self, @otherconds) = @_;
 303   new Automake::DisjConditions (
 304     map { $_->isa ("Automake::DisjConditions") ? $_->conds : $_ }
 305         ($self, @otherconds));
 306 }
 307
 308
 309 =item C<$prod = $set1-E<gt>multiply ($set2)>
 310
 311 Multiply two conditional sets.
 312
 313   my $set1 = new Automake::DisjConditions
 314     (new Automake::Condition ("A_TRUE"),
 315      new Automake::Condition ("B_TRUE"));
 316   my $set2 = new Automake::DisjConditions
 317     (new Automake::Condition ("C_FALSE"),
 318      new Automake::Condition ("D_FALSE"));
 319
 320 C<$set1-E<gt>multiply ($set2)> will return
 321
 322   new Automake::DisjConditions
 323     (new Automake::Condition ("A_TRUE", "C_FALSE"),
 324      new Automake::Condition ("B_TRUE", "C_FALSE"),;
 325      new Automake::Condition ("A_TRUE", "D_FALSE"),
 326      new Automake::Condition ("B_TRUE", "D_FALSE"));
 327
 328 The argument can also be a C<Condition>.
 329
 330 =cut
 331
 332 # Same as multiply() but take a list of Conditionals as second argument.
 333 # We use this in invert().
 334 sub _multiply ($@)
 335 {
 336   my ($self, @set) = @_;
 337   my @res = map { $_->multiply (@set) } $self->conds;
 338   return new Automake::DisjConditions (Automake::Condition::reduce_or @res);
 339 }
 340
 341 sub multiply ($$)
 342 {
 343   my ($self, $set) = @_;
 344   return $self->_multiply ($set) if $set->isa('Automake::Condition');
 345   return $self->_multiply ($set->conds);
 346 }
 347
 348 =item C<$inv = $set-E<gt>invert>
 349
 350 Invert a C<DisjConditions>.  Return a C<DisjConditions> which is true
 351 when C<$set> is false, and vice-versa.
 352
 353   my $set = new Automake::DisjConditions
 354     (new Automake::Condition ("A_TRUE", "B_TRUE"),
 355      new Automake::Condition ("A_FALSE", "B_FALSE"));
 356
 357 Calling C<$set-E<gt>invert> will return the following C<DisjConditions>.
 358
 359   new Automake::DisjConditions
 360     (new Automake::Condition ("A_TRUE", "B_FALSE"),
 361      new Automake::Condition ("A_FALSE", "B_TRUE"));
 362
 363 We implement the inversion by a product-of-sums to sum-of-products
 364 conversion using repeated multiplications.  Because of the way we
 365 implement multiplication, the result of inversion is in canonical
 366 prime implicant form.
 367
 368 =cut
 369
 370 sub invert($ )
 371 {
 372   my ($self) = @_;
 373
 374   return $self->{'invert'} if defined $self->{'invert'};
 375
 376   # The invert of an empty DisjConditions is TRUE.
 377   my $res = new Automake::DisjConditions TRUE;
 378
 379   #   !((a.b)+(c.d)+(e.f))
 380   # = (!a+!b).(!c+!d).(!e+!f)
 381   # We develop this into a sum of product iteratively, starting from TRUE:
 382   # 1) TRUE
 383   # 2) TRUE.!a + TRUE.!b
 384   # 3) TRUE.!a.!c + TRUE.!b.!c + TRUE.!a.!d + TRUE.!b.!d
 385   # 4) TRUE.!a.!c.!e + TRUE.!b.!c.!e + TRUE.!a.!d.!e + TRUE.!b.!d.!e
 386   #    + TRUE.!a.!c.!f + TRUE.!b.!c.!f + TRUE.!a.!d.!f + TRUE.!b.!d.!f
 387   foreach my $cond ($self->conds)
 388     {
 389       $res = $res->_multiply ($cond->not);
 390     }
 391
 392   # Cache result.
 393   $self->{'invert'} = $res;
 394   # It's tempting to also set $res->{'invert'} to $self, but that
 395   # is a bad idea as $self hasn't been normalized in any way.
 396   # (Different inputs can produce the same inverted set.)
 397   return $res;
 398 }
 399
 400 =item C<$self-E<gt>simplify>
 401
 402 Return a C<Disjunction> which is a simplified canonical form of C<$self>.
 403 This canonical form contains only prime implicants, but it can contain
 404 non-essential prime implicants.
 405
 406 =cut
 407
 408 sub simplify ($)
 409 {
 410   my ($self) = @_;
 411   return $self->invert->invert;
 412 }
 413
 414 =item C<$self-E<gt>sub_conditions ($cond)>
 415
 416 Return the subconditions of C<$self> that contains C<$cond>, with
 417 C<$cond> stripped.  More formally, return C<$res> such that
 418 C<$res-E<gt>multiply ($cond) == $self-E<gt>multiply ($cond)> and
 419 C<$res> does not mention any of the variables in C<$cond>.
 420
 421 For instance, consider:
 422
 423   my $a = new Automake::DisjConditions
 424     (new Automake::Condition ("A_TRUE", "B_TRUE"),
 425      new Automake::Condition ("A_TRUE", "C_FALSE"),
 426      new Automake::Condition ("A_TRUE", "B_FALSE", "C_TRUE"),
 427      new Automake::Condition ("A_FALSE"));
 428   my $b = new Automake::DisjConditions
 429     (new Automake::Condition ("A_TRUE", "B_FALSE"));
 430
 431 Calling C<$a-E<gt>sub_conditions ($b)> will return the following
 432 C<DisjConditions>.
 433
 434   new Automake::DisjConditions
 435     (new Automake::Condition ("C_FALSE"), # From A_TRUE C_FALSE
 436      new Automake::Condition ("C_TRUE")); # From A_TRUE B_FALSE C_TRUE"
 437
 438 =cut
 439
 440 sub sub_conditions ($$)
 441 {
 442   my ($self, $subcond) = @_;
 443
 444   # Make $subcond blindingly apparent in the DisjConditions.
 445   # For instance `$b->multiply($a->conds)' (from the POD example) is:
 446   #     (new Automake::Condition ("FALSE"),
 447   #      new Automake::Condition ("A_TRUE", "B_FALSE", "C_FALSE"),
 448   #      new Automake::Condition ("A_TRUE", "B_FALSE", "C_TRUE"),
 449   #      new Automake::Condition ("FALSE"))
 450   my @prodconds = $subcond->multiply ($self->conds);
 451
 452   # Now, strip $subcond from the remaining (i.e., non-false) Conditions.
 453   my @res = map { $_->false ? () : $_->strip ($subcond) } @prodconds;
 454
 455   return new Automake::DisjConditions @res;
 456 }
 457
 458 =item C<($string, $ambig_cond) = $condset-E<gt>ambiguous_p ($what, $cond)>
 459
 460 Check for an ambiguous condition.  Return an error message and the
 461 other condition involved if we have an ambiguity.  Return an empty
 462 string and FALSE otherwise.
 463
 464 C<$what> is the name of the thing being defined, to use in the error
 465 message.  C<$cond> is the C<Condition> under which it is being
 466 defined.  C<$condset> is the C<DisjConditions> under which it had
 467 already been defined.
 468
 469 =cut
 470
 471 sub ambiguous_p ($$$)
 472 {
 473   my ($self, $var, $cond) = @_;
 474
 475   # Note that these rules don't consider the following
 476   # example as ambiguous.
 477   #
 478   #   if COND1
 479   #     FOO = foo
 480   #   endif
 481   #   if COND2
 482   #     FOO = bar
 483   #   endif
 484   #
 485   # It's up to the user to not define COND1 and COND2
 486   # simultaneously.
 487
 488   return ("$var multiply defined in condition " . $cond->human, $cond)
 489     if exists $self->{'hash'}{$cond};
 490
 491   foreach my $vcond ($self->conds)
 492     {
 493       return ("$var was already defined in condition " . $vcond->human
 494               . ", which includes condition ". $cond->human, $vcond)
 495         if $vcond->true_when ($cond);
 496
 497       return ("$var was already defined in condition " . $vcond->human
 498               . ", which is included in condition " . $cond->human, $vcond)
 499         if $cond->true_when ($vcond);
 500     }
 501   return ('', FALSE);
 502 }
 503
 504 =head1 SEE ALSO
 505
 506 L<Automake::Condition>.
 507
 508 =head1 HISTORY
 509
 510 C<AM_CONDITIONAL>s and supporting code were added to Automake 1.1o by
 511 Ian Lance Taylor <ian@cygnus.org> in 1997.  Since then it has been
 512 improved by Tom Tromey <tromey@redhat.com>, Richard Boulton
 513 <richard@tartarus.org>, Raja R Harinath <harinath@cs.umn.edu>, Akim
 514 Demaille <akim@epita.fr>, Pavel Roskin <proski@gnu.org>, and
 515 Alexandre Duret-Lutz <adl@gnu.org>.
 516
 517 =cut
 518
 519 1;
 520
 521 ### Setup "GNU" style for perl-mode and cperl-mode.
 522 ## Local Variables:
 523 ## perl-indent-level: 2
 524 ## perl-continued-statement-offset: 2
 525 ## perl-continued-brace-offset: 0
 526 ## perl-brace-offset: 0
 527 ## perl-brace-imaginary-offset: 0
 528 ## perl-label-offset: -2
 529 ## cperl-indent-level: 2
 530 ## cperl-brace-offset: 0
 531 ## cperl-continued-brace-offset: 0
 532 ## cperl-label-offset: -2
 533 ## cperl-extra-newline-before-brace: t
 534 ## cperl-merge-trailing-else: nil
 535 ## cperl-continued-statement-offset: 2
 536 ## End: