lib/Automake/DisjConditions.pm

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