scripts/Dpkg/Deps.pm

   1 # Copyright © 1998 Richard Braakman
   2 # Copyright © 1999 Darren Benham
   3 # Copyright © 2000 Sean 'Shaleh' Perry
   4 # Copyright © 2004 Frank Lichtenheld
   5 # Copyright © 2006 Russ Allbery
   6 # Copyright © 2007-2009 Raphaël Hertzog <hertzog@debian.org>
   7 # Copyright © 2008-2009,2012-2014 Guillem Jover <guillem@debian.org>
   8 #
   9 # This program is free software; you may redistribute it and/or modify
  10 # it under the terms of the GNU General Public License as published by
  11 # the Free Software Foundation; either version 2 of the License, or
  12 # (at your option) any later version.
  13 #
  14 # This is distributed in the hope that it will be useful,
  15 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 # GNU General Public License for more details.
  18 #
  19 # You should have received a copy of the GNU General Public License
  20 # along with this program.  If not, see <https://www.gnu.org/licenses/>.
  21
  22 =encoding utf8
  23
  24 =head1 NAME
  25
  26 Dpkg::Deps - parse and manipulate dependencies of Debian packages
  27
  28 =head1 DESCRIPTION
  29
  30 The Dpkg::Deps module provides classes implementing various types of
  31 dependencies.
  32
  33 The most important function is deps_parse(), it turns a dependency line in
  34 a set of Dpkg::Deps::{Simple,AND,OR,Union} objects depending on the case.
  35
  36 =cut
  37
  38 package Dpkg::Deps 1.07;
  39
  40 use strict;
  41 use warnings;
  42 use feature qw(current_sub);
  43
  44 our @EXPORT = qw(
  45     deps_concat
  46     deps_parse
  47     deps_eval_implication
  48     deps_iterate
  49     deps_compare
  50 );
  51
  52 use Carp;
  53 use Exporter qw(import);
  54
  55 use Dpkg::Version;
  56 use Dpkg::Arch qw(get_host_arch get_build_arch debarch_to_debtuple);
  57 use Dpkg::BuildProfiles qw(get_build_profiles);
  58 use Dpkg::ErrorHandling;
  59 use Dpkg::Gettext;
  60 use Dpkg::Deps::Simple;
  61 use Dpkg::Deps::Union;
  62 use Dpkg::Deps::AND;
  63 use Dpkg::Deps::OR;
  64 use Dpkg::Deps::KnownFacts;
  65
  66 =head1 FUNCTIONS
  67
  68 All the deps_* functions are exported by default.
  69
  70 =over 4
  71
  72 =item deps_eval_implication($rel_p, $v_p, $rel_q, $v_q)
  73
  74 ($rel_p, $v_p) and ($rel_q, $v_q) express two dependencies as (relation,
  75 version). The relation variable can have the following values that are
  76 exported by L<Dpkg::Version>: REL_EQ, REL_LT, REL_LE, REL_GT, REL_GT.
  77
  78 This functions returns 1 if the "p" dependency implies the "q"
  79 dependency. It returns 0 if the "p" dependency implies that "q" is
  80 not satisfied. It returns undef when there's no implication.
  81
  82 The $v_p and $v_q parameter should be L<Dpkg::Version> objects.
  83
  84 =cut
  85
  86 sub deps_eval_implication {
  87     my ($rel_p, $v_p, $rel_q, $v_q) = @_;
  88
  89     # If versions are not valid, we can't decide of any implication
  90     return unless defined($v_p) and $v_p->is_valid();
  91     return unless defined($v_q) and $v_q->is_valid();
  92
  93     # q wants an exact version, so p must provide that exact version.  p
  94     # disproves q if q's version is outside the range enforced by p.
  95     if ($rel_q eq REL_EQ) {
  96         if ($rel_p eq REL_LT) {
  97             return ($v_p <= $v_q) ? 0 : undef;
  98         } elsif ($rel_p eq REL_LE) {
  99             return ($v_p < $v_q) ? 0 : undef;
 100         } elsif ($rel_p eq REL_GT) {
 101             return ($v_p >= $v_q) ? 0 : undef;
 102         } elsif ($rel_p eq REL_GE) {
 103             return ($v_p > $v_q) ? 0 : undef;
 104         } elsif ($rel_p eq REL_EQ) {
 105             return ($v_p == $v_q);
 106         }
 107     }
 108
 109     # A greater than clause may disprove a less than clause. An equal
 110     # cause might as well.  Otherwise, if
 111     # p's clause is <<, <=, or =, the version must be <= q's to imply q.
 112     if ($rel_q eq REL_LE) {
 113         if ($rel_p eq REL_GT) {
 114             return ($v_p >= $v_q) ? 0 : undef;
 115         } elsif ($rel_p eq REL_GE) {
 116             return ($v_p > $v_q) ? 0 : undef;
 117         } elsif ($rel_p eq REL_EQ) {
 118             return ($v_p <= $v_q) ? 1 : 0;
 119         } else { # <<, <=
 120             return ($v_p <= $v_q) ? 1 : undef;
 121         }
 122     }
 123
 124     # Similar, but << is stronger than <= so p's version must be << q's
 125     # version if the p relation is <= or =.
 126     if ($rel_q eq REL_LT) {
 127         if ($rel_p eq REL_GT or $rel_p eq REL_GE) {
 128             return ($v_p >= $v_p) ? 0 : undef;
 129         } elsif ($rel_p eq REL_LT) {
 130             return ($v_p <= $v_q) ? 1 : undef;
 131         } elsif ($rel_p eq REL_EQ) {
 132             return ($v_p < $v_q) ? 1 : 0;
 133         } else { # <<, <=
 134             return ($v_p < $v_q) ? 1 : undef;
 135         }
 136     }
 137
 138     # Same logic as above, only inverted.
 139     if ($rel_q eq REL_GE) {
 140         if ($rel_p eq REL_LT) {
 141             return ($v_p <= $v_q) ? 0 : undef;
 142         } elsif ($rel_p eq REL_LE) {
 143             return ($v_p < $v_q) ? 0 : undef;
 144         } elsif ($rel_p eq REL_EQ) {
 145             return ($v_p >= $v_q) ? 1 : 0;
 146         } else { # >>, >=
 147             return ($v_p >= $v_q) ? 1 : undef;
 148         }
 149     }
 150     if ($rel_q eq REL_GT) {
 151         if ($rel_p eq REL_LT or $rel_p eq REL_LE) {
 152             return ($v_p <= $v_q) ? 0 : undef;
 153         } elsif ($rel_p eq REL_GT) {
 154             return ($v_p >= $v_q) ? 1 : undef;
 155         } elsif ($rel_p eq REL_EQ) {
 156             return ($v_p > $v_q) ? 1 : 0;
 157         } else {
 158             return ($v_p > $v_q) ? 1 : undef;
 159         }
 160     }
 161
 162     return;
 163 }
 164
 165 =item $dep = deps_concat(@dep_list)
 166
 167 This function concatenates multiple dependency lines into a single line,
 168 joining them with ", " if appropriate, and always returning a valid string.
 169
 170 =cut
 171
 172 sub deps_concat {
 173     my (@dep_list) = @_;
 174
 175     return join ', ', grep { defined } @dep_list;
 176 }
 177
 178 =item $dep = deps_parse($line, %options)
 179
 180 This function parses the dependency line and returns an object, either a
 181 L<Dpkg::Deps::AND> or a L<Dpkg::Deps::Union>. Various options can alter the
 182 behavior of that function.
 183
 184 =over 4
 185
 186 =item use_arch (defaults to 1)
 187
 188 Take into account the architecture restriction part of the dependencies.
 189 Set to 0 to completely ignore that information.
 190
 191 =item host_arch (defaults to the current architecture)
 192
 193 Define the host architecture. By default it uses
 194 Dpkg::Arch::get_host_arch() to identify the proper architecture.
 195
 196 =item build_arch (defaults to the current architecture)
 197
 198 Define the build architecture. By default it uses
 199 Dpkg::Arch::get_build_arch() to identify the proper architecture.
 200
 201 =item reduce_arch (defaults to 0)
 202
 203 If set to 1, ignore dependencies that do not concern the current host
 204 architecture. This implicitly strips off the architecture restriction
 205 list so that the resulting dependencies are directly applicable to the
 206 current architecture.
 207
 208 =item use_profiles (defaults to 1)
 209
 210 Take into account the profile restriction part of the dependencies. Set
 211 to 0 to completely ignore that information.
 212
 213 =item build_profiles (defaults to no profile)
 214
 215 Define the active build profiles. By default no profile is defined.
 216
 217 =item reduce_profiles (defaults to 0)
 218
 219 If set to 1, ignore dependencies that do not concern the current build
 220 profile. This implicitly strips off the profile restriction formula so
 221 that the resulting dependencies are directly applicable to the current
 222 profiles.
 223
 224 =item reduce_restrictions (defaults to 0)
 225
 226 If set to 1, ignore dependencies that do not concern the current set of
 227 restrictions. This implicitly strips off any architecture restriction list
 228 or restriction formula so that the resulting dependencies are directly
 229 applicable to the current restriction.
 230 This currently implies C<reduce_arch> and C<reduce_profiles>, and overrides
 231 them if set.
 232
 233 =item union (defaults to 0)
 234
 235 If set to 1, returns a L<Dpkg::Deps::Union> instead of a L<Dpkg::Deps::AND>.
 236 Use this when parsing non-dependency fields like Conflicts.
 237
 238 =item virtual (defaults to 0)
 239
 240 If set to 1, allow only virtual package version relations, that is none,
 241 or "=".
 242 This should be set whenever working with Provides fields.
 243
 244 =item build_dep (defaults to 0)
 245
 246 If set to 1, allow build-dep only arch qualifiers, that is ":native".
 247 This should be set whenever working with build-deps.
 248
 249 =item tests_dep (defaults to 0)
 250
 251 If set to 1, allow tests-specific package names in dependencies, that is
 252 "@" and "@builddeps@" (since dpkg 1.18.7). This should be set whenever
 253 working with dependency fields from F<debian/tests/control>.
 254
 255 This option implicitly (and forcibly) enables C<build_dep> because test
 256 dependencies are based on build dependencies (since dpkg 1.22.1).
 257
 258 =back
 259
 260 =cut
 261
 262 sub deps_parse {
 263     my ($dep_line, %options) = @_;
 264
 265     # Validate arguments.
 266     croak "invalid host_arch $options{host_arch}"
 267         if defined $options{host_arch} and not defined debarch_to_debtuple($options{host_arch});
 268     croak "invalid build_arch $options{build_arch}"
 269         if defined $options{build_arch} and not defined debarch_to_debtuple($options{build_arch});
 270
 271     $options{use_arch} //= 1;
 272     $options{reduce_arch} //= 0;
 273     $options{use_profiles} //= 1;
 274     $options{reduce_profiles} //= 0;
 275     $options{reduce_restrictions} //= 0;
 276     $options{union} //= 0;
 277     $options{virtual} //= 0;
 278     $options{build_dep} //= 0;
 279     $options{tests_dep} //= 0;
 280
 281     if ($options{reduce_restrictions}) {
 282         $options{reduce_arch} = 1;
 283         $options{reduce_profiles} = 1;
 284     }
 285     if ($options{reduce_arch}) {
 286         $options{host_arch} //= get_host_arch();
 287         $options{build_arch} //= get_build_arch();
 288     }
 289     if ($options{reduce_profiles}) {
 290         $options{build_profiles} //= [ get_build_profiles() ];
 291     }
 292     if ($options{tests_dep}) {
 293         $options{build_dep} = 1;
 294     }
 295
 296     # Options for Dpkg::Deps::Simple.
 297     my %deps_options = (
 298         host_arch => $options{host_arch},
 299         build_arch => $options{build_arch},
 300         build_dep => $options{build_dep},
 301         tests_dep => $options{tests_dep},
 302     );
 303
 304     # Merge in a single-line
 305     $dep_line =~ s/\s*[\r\n]\s*/ /g;
 306     # Strip trailing/leading spaces
 307     $dep_line =~ s/^\s+//;
 308     $dep_line =~ s/\s+$//;
 309
 310     my @dep_list;
 311     foreach my $dep_and (split(/\s*,\s*/m, $dep_line)) {
 312         my @or_list = ();
 313         foreach my $dep_or (split(/\s*\|\s*/m, $dep_and)) {
 314             my $dep_simple = Dpkg::Deps::Simple->new($dep_or, %deps_options);
 315             if (not defined $dep_simple->{package}) {
 316                 warning(g_("can't parse dependency %s"), $dep_or);
 317                 return;
 318             }
 319             if ($options{virtual} && defined $dep_simple->{relation} &&
 320                 $dep_simple->{relation} ne '=') {
 321                 warning(g_('virtual dependency contains invalid relation: %s'),
 322                         $dep_simple->output);
 323                 return;
 324             }
 325             $dep_simple->{arches} = undef if not $options{use_arch};
 326             if ($options{reduce_arch}) {
 327                 $dep_simple->reduce_arch($options{host_arch});
 328                 next if not $dep_simple->arch_is_concerned($options{host_arch});
 329             }
 330             $dep_simple->{restrictions} = undef if not $options{use_profiles};
 331             if ($options{reduce_profiles}) {
 332                 $dep_simple->reduce_profiles($options{build_profiles});
 333                 next if not $dep_simple->profile_is_concerned($options{build_profiles});
 334             }
 335             push @or_list, $dep_simple;
 336         }
 337         next if not @or_list;
 338         if (scalar @or_list == 1) {
 339             push @dep_list, $or_list[0];
 340         } else {
 341             my $dep_or = Dpkg::Deps::OR->new();
 342             $dep_or->add($_) foreach (@or_list);
 343             push @dep_list, $dep_or;
 344         }
 345     }
 346     my $dep_and;
 347     if ($options{union}) {
 348         $dep_and = Dpkg::Deps::Union->new();
 349     } else {
 350         $dep_and = Dpkg::Deps::AND->new();
 351     }
 352     foreach my $dep (@dep_list) {
 353         if ($options{union} and not $dep->isa('Dpkg::Deps::Simple')) {
 354             warning(g_('an union dependency can only contain simple dependencies'));
 355             return;
 356         }
 357         $dep_and->add($dep);
 358     }
 359     return $dep_and;
 360 }
 361
 362 =item $bool = deps_iterate($deps, $callback_func)
 363
 364 This function visits all elements of the dependency object, calling the
 365 callback function for each element.
 366
 367 The callback function is expected to return true when everything is fine,
 368 or false if something went wrong, in which case the iteration will stop.
 369
 370 Return the same value as the callback function.
 371
 372 =cut
 373
 374 sub deps_iterate {
 375     my ($deps, $callback_func) = @_;
 376
 377     my $visitor_func = sub {
 378         foreach my $dep (@_) {
 379             return unless defined $dep;
 380
 381             if ($dep->isa('Dpkg::Deps::Simple')) {
 382                 return unless $callback_func->($dep);
 383             } else {
 384                 return unless __SUB__->($dep->get_deps());
 385             }
 386         }
 387         return 1;
 388     };
 389
 390     return $visitor_func->($deps);
 391 }
 392
 393 =item deps_compare($a, $b)
 394
 395 Implements a comparison operator between two dependency objects.
 396 This function is mainly used to implement the sort() method.
 397
 398 =back
 399
 400 =cut
 401
 402 my %relation_ordering = (
 403         undef => 0,
 404         REL_GE() => 1,
 405         REL_GT() => 2,
 406         REL_EQ() => 3,
 407         REL_LT() => 4,
 408         REL_LE() => 5,
 409 );
 410
 411 sub deps_compare {
 412     my ($aref, $bref) = @_;
 413
 414     my (@as, @bs);
 415     deps_iterate($aref, sub { push @as, @_ });
 416     deps_iterate($bref, sub { push @bs, @_ });
 417
 418     while (1) {
 419         my ($a, $b) = (shift @as, shift @bs);
 420         my $aundef = not defined $a or $a->is_empty();
 421         my $bundef = not defined $b or $b->is_empty();
 422
 423         return  0 if $aundef and $bundef;
 424         return -1 if $aundef;
 425         return  1 if $bundef;
 426
 427         my $ar = $a->{relation} // 'undef';
 428         my $br = $b->{relation} // 'undef';
 429         my $av = $a->{version} // '';
 430         my $bv = $b->{version} // '';
 431
 432         my $res = (($a->{package} cmp $b->{package}) ||
 433                    ($relation_ordering{$ar} <=> $relation_ordering{$br}) ||
 434                    ($av cmp $bv));
 435         return $res if $res != 0;
 436     }
 437 }
 438
 439 =head1 CLASSES - Dpkg::Deps::*
 440
 441 There are several kind of dependencies. A L<Dpkg::Deps::Simple> dependency
 442 represents a single dependency statement (it relates to one package only).
 443 L<Dpkg::Deps::Multiple> dependencies are built on top of this class
 444 and combine several dependencies in different manners. L<Dpkg::Deps::AND>
 445 represents the logical "AND" between dependencies while L<Dpkg::Deps::OR>
 446 represents the logical "OR". L<Dpkg::Deps::Multiple> objects can contain
 447 L<Dpkg::Deps::Simple> object as well as other L<Dpkg::Deps::Multiple> objects.
 448
 449 In practice, the code is only meant to handle the realistic cases which,
 450 given Debian's dependencies structure, imply those restrictions: AND can
 451 contain Simple or OR objects, OR can only contain Simple objects.
 452
 453 L<Dpkg::Deps::KnownFacts> is a special class that is used while evaluating
 454 dependencies and while trying to simplify them. It represents a set of
 455 installed packages along with the virtual packages that they might
 456 provide.
 457
 458 =head1 CHANGES
 459
 460 =head2 Version 1.07 (dpkg 1.20.0)
 461
 462 New option: Add virtual option to deps_parse().
 463
 464 =head2 Version 1.06 (dpkg 1.18.7; module version bumped on dpkg 1.18.24)
 465
 466 New option: Add tests_dep option to deps_parse().
 467
 468 =head2 Version 1.05 (dpkg 1.17.14)
 469
 470 New function: deps_iterate().
 471
 472 =head2 Version 1.04 (dpkg 1.17.10)
 473
 474 New options: Add use_profiles, build_profiles, reduce_profiles and
 475 reduce_restrictions to deps_parse().
 476
 477 =head2 Version 1.03 (dpkg 1.17.0)
 478
 479 New option: Add build_arch option to deps_parse().
 480
 481 =head2 Version 1.02 (dpkg 1.17.0)
 482
 483 New function: deps_concat()
 484
 485 =head2 Version 1.01 (dpkg 1.16.1)
 486
 487 <Used to document changes to Dpkg::Deps::* modules before they were split.>
 488
 489 =head2 Version 1.00 (dpkg 1.15.6)
 490
 491 Mark the module as public.
 492
 493 =cut
 494
 495 1;