lib/Fedora/Rebuild/Solver.pm

   1 package Fedora::Rebuild::Solver;
   2 use strict;
   3 use warnings;
   4 use version 0.77; our $VERSION = version->declare("v0.5.1");
   5
   6 use Moose;
   7 use Fedora::Rebuild::Set::Package;
   8 use Fedora::Rebuild::Package;
   9 use namespace::clean;
  10
  11 # Set of packages with populated provides and requires
  12 has 'packages' => (is => 'ro', isa => 'Fedora::Rebuild::Set::Package',
  13     lazy_build => 1, required => 1);
  14 # Reference to function with three arguments (dependency name, relation
  15 # flag, version) returning false if the dependency should be considered, true
  16 # otherwise. If attribute is undef or missing, no filtering will be performed
  17 # (i.e. the same effect as sub {1}).
  18 has 'dependencyfilter' => (is => 'ro', isa => 'CodeRef', required => 0);
  19
  20
  21 # This is cache of binary packages already resolved as installable or not
  22 # installable.
  23 # To keep coherency, do not update $self->packages or referenced packages.
  24 # This is reference to hash of binary package names. Values holds verdict
  25 # (true for installable, false otherwise) and message (string of dependencies
  26 # or reason why not installable).
  27 has 'cache' => (is => 'rw', isa => 'HashRef', lazy_build => 1,
  28     init_arg => 0);
  29
  30 sub _build_cache {
  31     # TODO: Thread safety?
  32     return {};
  33 }
  34
  35 sub invalidate_cache {
  36     my $self = shift;
  37     # TODO: Thread safety?
  38     $self->cache({});
  39     #print STDERR "Cache invalidated\n";
  40 }
  41
  42 # Add is_installable result to cache
  43 sub add_to_cache {
  44     my ($self, $binarypackage, $is_installable, $message) = @_;
  45
  46     # TODO: Thread safety?
  47     ${$self->cache}{$binarypackage} = {
  48         is_installable => $is_installable,
  49         message => $message
  50     };
  51
  52     #print STDERR "Cache write: $binarypackage, " .
  53     #    "is_installable=$is_installable, message=$message\n";
  54 }
  55
  56 # Decide a package is installable now and set string of dependenices.
  57 # This is private method, use is_installable() instead.
  58 # $package is source package object
  59 # $binarypackage is binary package ENVR as index to $package->runrequies
  60 # $backpath is reference to list of binary packages on the path in the
  61 # dependecy tree from parent to root (i.e. root is last element). It's used to
  62 # detect cycle.
  63 # Return 0 for false, 1 for true, 2 for cycle. Fill list of dependencies into
  64 # $$message (without trailing new line) which is reference itself.
  65 sub is_installable_recursive {
  66
  67     my ($self, $package, $binarypackage, $message, $backpath) = @_;
  68
  69     # Detect cycle
  70     if (defined $backpath) {
  71         for my $predecessor (@$backpath) {
  72             if ($predecessor eq $binarypackage) {
  73                 return 2;
  74             }
  75         }
  76     } else {
  77         # Although the cache provides correct verdicts (installable vs. not
  78         # installable), it provides bad messages that were cached for
  79         # dependency in cycle.
  80         # Thus invalidate the cache for each top-level package
  81         $self->invalidate_cache();
  82     }
  83     unshift @$backpath, $binarypackage;
  84
  85     # Check cached result
  86     if (defined (my $result = ${$self->cache()}{$binarypackage})) {
  87         $$message = $$result{message};
  88         #print STDERR "Cache hit: $binarypackage, message=$$message\n";
  89         shift @$backpath;
  90         return $$result{is_installable};
  91     };
  92
  93
  94     # Each requirement of $binarypackage must be satisfied by at least one
  95     # binary package from packages list.
  96     my $binarypackage_runrequires = ${$package->runrequires}{$binarypackage};
  97     for my $rname (keys %$binarypackage_runrequires) {
  98         for my $require (@{$$binarypackage_runrequires{$rname}}) {
  99             my $rflag = $$require[0];
 100             my $rversion = $$require[1];
 101             my $is_satisfied = 0;
 102             my $deep_message;
 103
 104             if (defined $self->dependencyfilter and
 105                     &{$self->dependencyfilter}($rname, $rflag, $rversion)) {
 106                 # Avoid user-defined Requires from dependency evaluation
 107                 next;
 108             }
 109
 110             ALL_PACKAGES: for my $providing_package ($self->packages->packages)
 111             {
 112                 for my $binary_providing_package
 113                         (keys %{$providing_package->provides}) {
 114                     if (Fedora::Rebuild::RPM::is_satisfied($rname, $rflag,
 115                            $rversion,
 116                            ${$providing_package->provides}{$binary_providing_package})) {
 117                         $deep_message = '';
 118                         my $is_installable =
 119                                 $self->is_installable_recursive(
 120                                     $providing_package,
 121                                     $binary_providing_package, \$deep_message,
 122                                     $backpath);
 123                         if ($is_installable) {
 124                             $is_satisfied = 1;
 125
 126                             #print STDERR "$binary_providing_package: " .
 127                             #    "$is_installable, deep: $deep_message\n";
 128                             if ($is_installable == 1) {
 129                                 # Do not log end of cycle
 130                                 if ($$message ne '') {
 131                                     $$message .= ' ';
 132                                 }
 133                                 $$message .= $providing_package->name . '/' .
 134                                     $binary_providing_package;
 135                                 if ($deep_message ne '')  {
 136                                     $$message .= " ($deep_message)";
 137                                 }
 138                             }
 139
 140                             last ALL_PACKAGES;
 141                         }
 142                     }
 143                 }
 144             }
 145
 146             if (!$is_satisfied) {
 147                 $$message =  q{`} . $package->name . q{/} . $binarypackage .
 148                     q{' requires `}. $rname .
 149                     q{ } .
 150                     Fedora::Rebuild::RPM::flag_as_string($rflag) .
 151                     q{ } . $rversion . q{' that cannot be satisfied};
 152                 if ($deep_message//'' ne '')  {
 153                     $$message .= " ($deep_message)";
 154                 }
 155
 156                 # FIXME: Can we cache negative answers for cut-off subtree?
 157                 $self->add_to_cache($binarypackage, 0, $$message);
 158                 shift @$backpath;
 159                 return 0;
 160             }
 161         }
 162     }
 163
 164     # FIXME: We cannot cache package whose descendants were cut
 165     # off because of breaking cycle.
 166     # TODO: Cache top-level package only or reevaluate subtree
 167     # from point of view of the package. (Cyclic problem again?)
 168     $self->add_to_cache($binarypackage, 1, $$message);
 169     shift @$backpath;
 170     return 1;
 171 }
 172
 173
 174 # Decides a $binarypackage compiled from source $package is installable now.
 175 # This is hard problem as it requires recursive evaluation of each package
 176 # satisifying run-time dependency of previous package.
 177 # Return 0 for false, 1 or true, undef for error while deciding. Fill error
 178 # message (without trailing new line) into reference of second argument
 179 # if defined.
 180 sub is_installable {
 181     my ($self, $package, $binarypackage, $message) = @_;
 182
 183     my $reason = '';
 184     if ($self->is_installable_recursive($package, $binarypackage, \$reason,
 185             undef)) {
 186         if (defined $message) {
 187             $$message = q{RunRequires for `} . $package->name . '/' .
 188                 $binarypackage . q{' fulfilled} .
 189                 (($reason ne '') ? " ($reason)" : '') . '.';
 190         }
 191         return 1;
 192     } else {
 193         if (defined $message) {
 194             $$message = q{Package `} . $package->name . '/' . $binarypackage .
 195                 q{' cannot be installed because: } . $reason . '.';
 196         }
 197         return 0;
 198     }
 199 }
 200
 201
 202 # Decide a package is buildable now and set string of dependenices.
 203 # Return 0 for false, 1 or true. Fill list of dependencies into
 204 # message (without trailing new line) which is reference itself.
 205 sub is_buildable {
 206
 207     my ($self, $package, $message) = @_;
 208
 209     if (defined $message) {
 210         $$message = '';
 211     }
 212
 213     # Each requirement of $package must be satisfied by at least one binary
 214     # package from source packages list.
 215     for my $rname (keys %{$package->requires}) {
 216         for my $require (@{${$package->requires}{$rname}}) {
 217             my $rflag = $$require[0];
 218             my $rversion = $$require[1];
 219             my $is_satisfied = 0;
 220             my $deep_message;
 221
 222             if (defined $self->dependencyfilter and
 223                     &{$self->dependencyfilter}($rname, $rflag, $rversion)) {
 224                 # Avoid user-defined BuilRequires from dependency evaluation
 225                 next;
 226             }
 227
 228             ALL_PACKAGES: for my $providing_package ($self->packages->packages)
 229             {
 230                 for my $binary_providing_package
 231                         (keys %{$providing_package->provides}) {
 232                     if (Fedora::Rebuild::RPM::is_satisfied($rname, $rflag,
 233                             $rversion,
 234                             ${$providing_package->provides}{$binary_providing_package})) {
 235                         $deep_message = '';
 236                         if ($self->is_installable_recursive($providing_package,
 237                                 $binary_providing_package, \$deep_message,
 238                                 undef)) {
 239                             $is_satisfied = 1;
 240                             if ($message) {
 241                                 if ($$message ne '') {
 242                                     $$message .= ' ';
 243                                 }
 244                                 $$message .= $providing_package->name . '/' .
 245                                     $binary_providing_package;
 246                                 if ($deep_message ne '')  {
 247                                     $$message .= " ($deep_message)";
 248                                 }
 249                             }
 250                             last ALL_PACKAGES;
 251                         }
 252                     }
 253                 }
 254             }
 255
 256             if (!$is_satisfied) {
 257                 if (defined $message) {
 258                     $$message =  q{Source package `} . $package->name .
 259                         q{' cannot be installed because it build-requires `} .
 260                         $rname .  q{ } .
 261                         Fedora::Rebuild::RPM::flag_as_string($rflag) .
 262                         q{ } . $rversion . q{' that cannot be satisfied};
 263                     if ($deep_message//'' ne '')  {
 264                         $$message .= " ($deep_message)";
 265                     }
 266                     $$message .= '.';
 267                 }
 268                 return 0;
 269             }
 270         }
 271     }
 272
 273     if (defined $message) {
 274         $$message = "BuildRequires for `" . $package->name . "' fulfilled" .
 275             (($$message ne '') ? " ($$message)" : '') . '.';
 276     }
 277     return 1;
 278 }
 279
 280
 281 1;