lib/Automake/DisjConditions.pm

   1 # Copyright (C) 1997-2012 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 2, 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 in 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 strings 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
 196 =item C<CLONE>
 197
 198 Internal special subroutine to fix up the self hashes in
 199 C<%_disjcondition_singletons> upon thread creation.  C<CLONE> is invoked
 200 automatically with ithreads from Perl 5.7.2 or later, so if you use this
 201 module with earlier versions of Perl, it is not thread-safe.
 202
 203 =cut
 204
 205 sub CLONE
 206 {
 207   foreach my $self (values %_disjcondition_singletons)
 208     {
 209       my %h = map { $_ => $_ } @{$self->{'conds'}};
 210       $self->{'hash'} = \%h;
 211     }
 212 }
 213
 214
 215 =item C<@conds = $set-E<gt>conds>
 216
 217 Return the list of C<Condition> objects involved in C<$set>.
 218
 219 =cut
 220
 221 sub conds ($ )
 222 {
 223   my ($self) = @_;
 224   return @{$self->{'conds'}};
 225 }
 226
 227 =item C<$cond = $set-E<gt>one_cond>
 228
 229 Return one C<Condition> object involved in C<$set>.
 230
 231 =cut
 232
 233 sub one_cond ($)
 234 {
 235   my ($self) = @_;
 236   return (%{$self->{'hash'}},)[1];
 237 }
 238
 239 =item C<$et = $set-E<gt>false>
 240
 241 Return 1 iff the C<DisjConditions> object is always false (i.e., if it
 242 is empty, or if it contains only false C<Condition>s). Return 0
 243 otherwise.
 244
 245 =cut
 246
 247 sub false ($ )
 248 {
 249   my ($self) = @_;
 250   return 0 == keys %{$self->{'hash'}};
 251 }
 252
 253 =item C<$et = $set-E<gt>true>
 254
 255 Return 1 iff the C<DisjConditions> object is always true (i.e. covers all
 256 conditions). Return 0 otherwise.
 257
 258 =cut
 259
 260 sub true ($ )
 261 {
 262   my ($self) = @_;
 263   return $self->invert->false;
 264 }
 265
 266 =item C<$str = $set-E<gt>string>
 267
 268 Build a string which denotes the C<DisjConditions>.
 269
 270 =cut
 271
 272 sub string ($ )
 273 {
 274   my ($self) = @_;
 275   return $self->{'string'};
 276 }
 277
 278 =item C<$cond-E<gt>human>
 279
 280 Build a human readable string which denotes the C<DisjConditions>.
 281
 282 =cut
 283
 284 sub human ($ )
 285 {
 286   my ($self) = @_;
 287
 288   return $self->{'human'} if defined $self->{'human'};
 289
 290   my $res = '';
 291   if ($self->false)
 292     {
 293       $res = 'FALSE';
 294     }
 295   else
 296     {
 297       my @c = $self->conds;
 298       if (1 == @c)
 299         {
 300           $res = $c[0]->human;
 301         }
 302       else
 303         {
 304           $res = '(' . join (') or (', map { $_->human } $self->conds) . ')';
 305         }
 306     }
 307   $self->{'human'} = $res;
 308   return $res;
 309 }
 310
 311
 312 =item C<$newcond = $cond-E<gt>merge (@otherconds)>
 313
 314 Return a new C<DisjConditions> which is the disjunction of
 315 C<$cond> and C<@otherconds>.  Items in C<@otherconds> can be
 316 @C<Condition>s or C<DisjConditions>.
 317
 318 =cut
 319
 320 sub merge ($@)
 321 {
 322   my ($self, @otherconds) = @_;
 323   new Automake::DisjConditions (
 324     map { $_->isa ("Automake::DisjConditions") ? $_->conds : $_ }
 325         ($self, @otherconds));
 326 }
 327
 328
 329 =item C<$prod = $set1-E<gt>multiply ($set2)>
 330
 331 Multiply two conditional sets.
 332
 333   my $set1 = new Automake::DisjConditions
 334     (new Automake::Condition ("A_TRUE"),
 335      new Automake::Condition ("B_TRUE"));
 336   my $set2 = new Automake::DisjConditions
 337     (new Automake::Condition ("C_FALSE"),
 338      new Automake::Condition ("D_FALSE"));
 339
 340 C<$set1-E<gt>multiply ($set2)> will return
 341
 342   new Automake::DisjConditions
 343     (new Automake::Condition ("A_TRUE", "C_FALSE"),
 344      new Automake::Condition ("B_TRUE", "C_FALSE"),;
 345      new Automake::Condition ("A_TRUE", "D_FALSE"),
 346      new Automake::Condition ("B_TRUE", "D_FALSE"));
 347
 348 The argument can also be a C<Condition>.
 349
 350 =cut
 351
 352 # Same as multiply() but take a list of Conditionals as second argument.
 353 # We use this in invert().
 354 sub _multiply ($@)
 355 {
 356   my ($self, @set) = @_;
 357   my @res = map { $_->multiply (@set) } $self->conds;
 358   return new Automake::DisjConditions (Automake::Condition::reduce_or @res);
 359 }
 360
 361 sub multiply ($$)
 362 {
 363   my ($self, $set) = @_;
 364   return $self->_multiply ($set) if $set->isa('Automake::Condition');
 365   return $self->_multiply ($set->conds);
 366 }
 367
 368 =item C<$inv = $set-E<gt>invert>
 369
 370 Invert a C<DisjConditions>.  Return a C<DisjConditions> which is true
 371 when C<$set> is false, and vice-versa.
 372
 373   my $set = new Automake::DisjConditions
 374     (new Automake::Condition ("A_TRUE", "B_TRUE"),
 375      new Automake::Condition ("A_FALSE", "B_FALSE"));
 376
 377 Calling C<$set-E<gt>invert> will return the following C<DisjConditions>.
 378
 379   new Automake::DisjConditions
 380     (new Automake::Condition ("A_TRUE", "B_FALSE"),
 381      new Automake::Condition ("A_FALSE", "B_TRUE"));
 382
 383 We implement the inversion by a product-of-sums to sum-of-products
 384 conversion using repeated multiplications.  Because of the way we
 385 implement multiplication, the result of inversion is in canonical
 386 prime implicant form.
 387
 388 =cut
 389
 390 sub invert($ )
 391 {
 392   my ($self) = @_;
 393
 394   return $self->{'invert'} if defined $self->{'invert'};
 395
 396   # The invert of an empty DisjConditions is TRUE.
 397   my $res = new Automake::DisjConditions TRUE;
 398
 399   #   !((a.b)+(c.d)+(e.f))
 400   # = (!a+!b).(!c+!d).(!e+!f)
 401   # We develop this into a sum of product iteratively, starting from TRUE:
 402   # 1) TRUE
 403   # 2) TRUE.!a + TRUE.!b
 404   # 3) TRUE.!a.!c + TRUE.!b.!c + TRUE.!a.!d + TRUE.!b.!d
 405   # 4) TRUE.!a.!c.!e + TRUE.!b.!c.!e + TRUE.!a.!d.!e + TRUE.!b.!d.!e
 406   #    + TRUE.!a.!c.!f + TRUE.!b.!c.!f + TRUE.!a.!d.!f + TRUE.!b.!d.!f
 407   foreach my $cond ($self->conds)
 408     {
 409       $res = $res->_multiply ($cond->not);
 410     }
 411
 412   # Cache result.
 413   $self->{'invert'} = $res;
 414   # It's tempting to also set $res->{'invert'} to $self, but that
 415   # is a bad idea as $self hasn't been normalized in any way.
 416   # (Different inputs can produce the same inverted set.)
 417   return $res;
 418 }
 419
 420 =item C<$self-E<gt>simplify>
 421
 422 Return a C<Disjunction> which is a simplified canonical form of C<$self>.
 423 This canonical form contains only prime implicants, but it can contain
 424 non-essential prime implicants.
 425
 426 =cut
 427
 428 sub simplify ($)
 429 {
 430   my ($self) = @_;
 431   return $self->invert->invert;
 432 }
 433
 434 =item C<$self-E<gt>sub_conditions ($cond)>
 435
 436 Return the subconditions of C<$self> that contains C<$cond>, with
 437 C<$cond> stripped.  More formally, return C<$res> such that
 438 C<$res-E<gt>multiply ($cond) == $self-E<gt>multiply ($cond)> and
 439 C<$res> does not mention any of the variables in C<$cond>.
 440
 441 For instance, consider:
 442
 443   my $a = new Automake::DisjConditions
 444     (new Automake::Condition ("A_TRUE", "B_TRUE"),
 445      new Automake::Condition ("A_TRUE", "C_FALSE"),
 446      new Automake::Condition ("A_TRUE", "B_FALSE", "C_TRUE"),
 447      new Automake::Condition ("A_FALSE"));
 448   my $b = new Automake::DisjConditions
 449     (new Automake::Condition ("A_TRUE", "B_FALSE"));
 450
 451 Calling C<$a-E<gt>sub_conditions ($b)> will return the following
 452 C<DisjConditions>.
 453
 454   new Automake::DisjConditions
 455     (new Automake::Condition ("C_FALSE"), # From A_TRUE C_FALSE
 456      new Automake::Condition ("C_TRUE")); # From A_TRUE B_FALSE C_TRUE"
 457
 458 =cut
 459
 460 sub sub_conditions ($$)
 461 {
 462   my ($self, $subcond) = @_;
 463
 464   # Make $subcond blindingly apparent in the DisjConditions.
 465   # For instance `$b->multiply($a->conds)' (from the POD example) is:
 466   #     (new Automake::Condition ("FALSE"),
 467   #      new Automake::Condition ("A_TRUE", "B_FALSE", "C_FALSE"),
 468   #      new Automake::Condition ("A_TRUE", "B_FALSE", "C_TRUE"),
 469   #      new Automake::Condition ("FALSE"))
 470   my @prodconds = $subcond->multiply ($self->conds);
 471
 472   # Now, strip $subcond from the remaining (i.e., non-false) Conditions.
 473   my @res = map { $_->false ? () : $_->strip ($subcond) } @prodconds;
 474
 475   return new Automake::DisjConditions @res;
 476 }
 477
 478 =item C<($string, $ambig_cond) = $condset-E<gt>ambiguous_p ($what, $cond)>
 479
 480 Check for an ambiguous condition.  Return an error message and the
 481 other condition involved if we have an ambiguity.  Return an empty
 482 string and FALSE otherwise.
 483
 484 C<$what> is the name of the thing being defined, to use in the error
 485 message.  C<$cond> is the C<Condition> under which it is being
 486 defined.  C<$condset> is the C<DisjConditions> under which it had
 487 already been defined.
 488
 489 =cut
 490
 491 sub ambiguous_p ($$$)
 492 {
 493   my ($self, $var, $cond) = @_;
 494
 495   # Note that these rules don't consider the following
 496   # example as ambiguous.
 497   #
 498   #   if COND1
 499   #     FOO = foo
 500   #   endif
 501   #   if COND2
 502   #     FOO = bar
 503   #   endif
 504   #
 505   # It's up to the user to not define COND1 and COND2
 506   # simultaneously.
 507
 508   return ("$var multiply defined in condition " . $cond->human, $cond)
 509     if exists $self->{'hash'}{$cond};
 510
 511   foreach my $vcond ($self->conds)
 512     {
 513       return ("$var was already defined in condition " . $vcond->human
 514               . ", which includes condition ". $cond->human, $vcond)
 515         if $vcond->true_when ($cond);
 516
 517       return ("$var was already defined in condition " . $vcond->human
 518               . ", which is included in condition " . $cond->human, $vcond)
 519         if $cond->true_when ($vcond);
 520     }
 521   return ('', FALSE);
 522 }
 523
 524 =head1 SEE ALSO
 525
 526 L<Automake::Condition>.
 527
 528 =head1 HISTORY
 529
 530 C<AM_CONDITIONAL>s and supporting code were added to Automake 1.1o by
 531 Ian Lance Taylor <ian@cygnus.org> in 1997.  Since then it has been
 532 improved by Tom Tromey <tromey@redhat.com>, Richard Boulton
 533 <richard@tartarus.org>, Raja R Harinath <harinath@cs.umn.edu>, Akim
 534 Demaille <akim@epita.fr>, Pavel Roskin <proski@gnu.org>, and
 535 Alexandre Duret-Lutz <adl@gnu.org>.
 536
 537 =cut
 538
 539 1;
 540
 541 ### Setup "GNU" style for perl-mode and cperl-mode.
 542 ## Local Variables:
 543 ## perl-indent-level: 2
 544 ## perl-continued-statement-offset: 2
 545 ## perl-continued-brace-offset: 0
 546 ## perl-brace-offset: 0
 547 ## perl-brace-imaginary-offset: 0
 548 ## perl-label-offset: -2
 549 ## cperl-indent-level: 2
 550 ## cperl-brace-offset: 0
 551 ## cperl-continued-brace-offset: 0
 552 ## cperl-label-offset: -2
 553 ## cperl-extra-newline-before-brace: t
 554 ## cperl-merge-trailing-else: nil
 555 ## cperl-continued-statement-offset: 2
 556 ## End: