lib/Automake/DisjConditions.pm

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