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 22package Dpkg::Deps; 23 24=encoding utf8 25 26=head1 NAME 27 28Dpkg::Deps - parse and manipulate dependencies of Debian packages 29 30=head1 DESCRIPTION 31 32The Dpkg::Deps module provides objects implementing various types of 33dependencies. 34 35The most important function is deps_parse(), it turns a dependency line in 36a set of Dpkg::Deps::{Simple,AND,OR,Union} objects depending on the case. 37 38=head1 FUNCTIONS 39 40All the deps_* functions are exported by default. 41 42=over 4 43 44=cut 45 46use strict; 47use warnings; 48 49our $VERSION = '1.06'; 50our @EXPORT = qw( 51 deps_concat 52 deps_parse 53 deps_eval_implication 54 deps_iterate 55 deps_compare 56); 57 58use Carp; 59use Exporter qw(import); 60 61use Dpkg::Version; 62use Dpkg::Arch qw(get_host_arch get_build_arch debarch_to_debtuple); 63use Dpkg::BuildProfiles qw(get_build_profiles); 64use Dpkg::ErrorHandling; 65use Dpkg::Gettext; 66use Dpkg::Deps::Simple; 67use Dpkg::Deps::Union; 68use Dpkg::Deps::AND; 69use Dpkg::Deps::OR; 70use Dpkg::Deps::KnownFacts; 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, 75version). The relation variable can have the following values that are 76exported by Dpkg::Version: REL_EQ, REL_LT, REL_LE, REL_GT, REL_GT. 77 78This functions returns 1 if the "p" dependency implies the "q" 79dependency. It returns 0 if the "p" dependency implies that "q" is 80not satisfied. It returns undef when there's no implication. 81 82The $v_p and $v_q parameter should be Dpkg::Version objects. 83 84=cut 85 86sub 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 167This function concatenates multiple dependency lines into a single line, 168joining them with ", " if appropriate, and always returning a valid string. 169 170=cut 171 172sub deps_concat { 173 my (@dep_list) = @_; 174 175 return join ', ', grep { defined } @dep_list; 176} 177 178=item $dep = deps_parse($line, %options) 179 180This function parses the dependency line and returns an object, either a 181Dpkg::Deps::AND or a Dpkg::Deps::Union. Various options can alter the 182behaviour of that function. 183 184=over 4 185 186=item use_arch (defaults to 1) 187 188Take into account the architecture restriction part of the dependencies. 189Set to 0 to completely ignore that information. 190 191=item host_arch (defaults to the current architecture) 192 193Define the host architecture. By default it uses 194Dpkg::Arch::get_host_arch() to identify the proper architecture. 195 196=item build_arch (defaults to the current architecture) 197 198Define the build architecture. By default it uses 199Dpkg::Arch::get_build_arch() to identify the proper architecture. 200 201=item reduce_arch (defaults to 0) 202 203If set to 1, ignore dependencies that do not concern the current host 204architecture. This implicitly strips off the architecture restriction 205list so that the resulting dependencies are directly applicable to the 206current architecture. 207 208=item use_profiles (defaults to 1) 209 210Take into account the profile restriction part of the dependencies. Set 211to 0 to completely ignore that information. 212 213=item build_profiles (defaults to no profile) 214 215Define the active build profiles. By default no profile is defined. 216 217=item reduce_profiles (defaults to 0) 218 219If set to 1, ignore dependencies that do not concern the current build 220profile. This implicitly strips off the profile restriction formula so 221that the resulting dependencies are directly applicable to the current 222profiles. 223 224=item reduce_restrictions (defaults to 0) 225 226If set to 1, ignore dependencies that do not concern the current set of 227restrictions. This implicitly strips off any architecture restriction list 228or restriction formula so that the resulting dependencies are directly 229applicable to the current restriction. 230This currently implies C<reduce_arch> and C<reduce_profiles>, and overrides 231them if set. 232 233=item union (defaults to 0) 234 235If set to 1, returns a Dpkg::Deps::Union instead of a Dpkg::Deps::AND. Use 236this when parsing non-dependency fields like Conflicts. 237 238=item build_dep (defaults to 0) 239 240If set to 1, allow build-dep only arch qualifiers, that is “:native”. 241This should be set whenever working with build-deps. 242 243=item tests_dep (defaults to 0) 244 245If set to 1, allow tests-specific package names in dependencies, that is 246"@" and "@builddeps@" (since dpkg 1.18.7). This should be set whenever 247working with dependency fields from F<debian/tests/control>. 248 249=back 250 251=cut 252 253sub deps_parse { 254 my ($dep_line, %options) = @_; 255 256 # Validate arguments. 257 croak "invalid host_arch $options{host_arch}" 258 if defined $options{host_arch} and not defined debarch_to_debtuple($options{host_arch}); 259 croak "invalid build_arch $options{build_arch}" 260 if defined $options{build_arch} and not defined debarch_to_debtuple($options{build_arch}); 261 262 $options{use_arch} //= 1; 263 $options{reduce_arch} //= 0; 264 $options{use_profiles} //= 1; 265 $options{reduce_profiles} //= 0; 266 $options{reduce_restrictions} //= 0; 267 $options{union} //= 0; 268 $options{build_dep} //= 0; 269 $options{tests_dep} //= 0; 270 271 if ($options{reduce_restrictions}) { 272 $options{reduce_arch} = 1; 273 $options{reduce_profiles} = 1; 274 } 275 if ($options{reduce_arch}) { 276 $options{host_arch} //= get_host_arch(); 277 $options{build_arch} //= get_build_arch(); 278 } 279 if ($options{reduce_profiles}) { 280 $options{build_profiles} //= [ get_build_profiles() ]; 281 } 282 283 # Options for Dpkg::Deps::Simple. 284 my %deps_options = ( 285 host_arch => $options{host_arch}, 286 build_arch => $options{build_arch}, 287 build_dep => $options{build_dep}, 288 tests_dep => $options{tests_dep}, 289 ); 290 291 # Strip trailing/leading spaces 292 $dep_line =~ s/^\s+//; 293 $dep_line =~ s/\s+$//; 294 295 my @dep_list; 296 foreach my $dep_and (split(/\s*,\s*/m, $dep_line)) { 297 my @or_list = (); 298 foreach my $dep_or (split(/\s*\|\s*/m, $dep_and)) { 299 my $dep_simple = Dpkg::Deps::Simple->new($dep_or, %deps_options); 300 if (not defined $dep_simple->{package}) { 301 warning(g_("can't parse dependency %s"), $dep_or); 302 return; 303 } 304 $dep_simple->{arches} = undef if not $options{use_arch}; 305 if ($options{reduce_arch}) { 306 $dep_simple->reduce_arch($options{host_arch}); 307 next if not $dep_simple->arch_is_concerned($options{host_arch}); 308 } 309 $dep_simple->{restrictions} = undef if not $options{use_profiles}; 310 if ($options{reduce_profiles}) { 311 $dep_simple->reduce_profiles($options{build_profiles}); 312 next if not $dep_simple->profile_is_concerned($options{build_profiles}); 313 } 314 push @or_list, $dep_simple; 315 } 316 next if not @or_list; 317 if (scalar @or_list == 1) { 318 push @dep_list, $or_list[0]; 319 } else { 320 my $dep_or = Dpkg::Deps::OR->new(); 321 $dep_or->add($_) foreach (@or_list); 322 push @dep_list, $dep_or; 323 } 324 } 325 my $dep_and; 326 if ($options{union}) { 327 $dep_and = Dpkg::Deps::Union->new(); 328 } else { 329 $dep_and = Dpkg::Deps::AND->new(); 330 } 331 foreach my $dep (@dep_list) { 332 if ($options{union} and not $dep->isa('Dpkg::Deps::Simple')) { 333 warning(g_('an union dependency can only contain simple dependencies')); 334 return; 335 } 336 $dep_and->add($dep); 337 } 338 return $dep_and; 339} 340 341=item $bool = deps_iterate($deps, $callback_func) 342 343This function visits all elements of the dependency object, calling the 344callback function for each element. 345 346The callback function is expected to return true when everything is fine, 347or false if something went wrong, in which case the iteration will stop. 348 349Return the same value as the callback function. 350 351=cut 352 353sub deps_iterate { 354 my ($deps, $callback_func) = @_; 355 356 my $visitor_func; 357 $visitor_func = sub { 358 foreach my $dep (@_) { 359 return unless defined $dep; 360 361 if ($dep->isa('Dpkg::Deps::Simple')) { 362 return unless $callback_func->($dep); 363 } else { 364 return unless $visitor_func->($dep->get_deps()); 365 } 366 } 367 return 1; 368 }; 369 370 return $visitor_func->($deps); 371} 372 373=item deps_compare($a, $b) 374 375Implements a comparison operator between two dependency objects. 376This function is mainly used to implement the sort() method. 377 378=back 379 380=cut 381 382my %relation_ordering = ( 383 undef => 0, 384 REL_GE() => 1, 385 REL_GT() => 2, 386 REL_EQ() => 3, 387 REL_LT() => 4, 388 REL_LE() => 5, 389); 390 391sub deps_compare { 392 my ($aref, $bref) = @_; 393 394 my (@as, @bs); 395 deps_iterate($aref, sub { push @as, @_ }); 396 deps_iterate($bref, sub { push @bs, @_ }); 397 398 while (1) { 399 my ($a, $b) = (shift @as, shift @bs); 400 my $aundef = not defined $a or $a->is_empty(); 401 my $bundef = not defined $b or $b->is_empty(); 402 403 return 0 if $aundef and $bundef; 404 return -1 if $aundef; 405 return 1 if $bundef; 406 407 my $ar = $a->{relation} // 'undef'; 408 my $br = $b->{relation} // 'undef'; 409 my $av = $a->{version} // ''; 410 my $bv = $b->{version} // ''; 411 412 my $res = (($a->{package} cmp $b->{package}) || 413 ($relation_ordering{$ar} <=> $relation_ordering{$br}) || 414 ($av cmp $bv)); 415 return $res if $res != 0; 416 } 417} 418 419=head1 OBJECTS - Dpkg::Deps::* 420 421There are several kind of dependencies. A Dpkg::Deps::Simple dependency 422represents a single dependency statement (it relates to one package only). 423Dpkg::Deps::Multiple dependencies are built on top of this object 424and combine several dependencies in different manners. Dpkg::Deps::AND 425represents the logical "AND" between dependencies while Dpkg::Deps::OR 426represents the logical "OR". Dpkg::Deps::Multiple objects can contain 427Dpkg::Deps::Simple object as well as other Dpkg::Deps::Multiple objects. 428 429In practice, the code is only meant to handle the realistic cases which, 430given Debian's dependencies structure, imply those restrictions: AND can 431contain Simple or OR objects, OR can only contain Simple objects. 432 433Dpkg::Deps::KnownFacts is a special object that is used while evaluating 434dependencies and while trying to simplify them. It represents a set of 435installed packages along with the virtual packages that they might 436provide. 437 438=head1 CHANGES 439 440=head2 Version 1.06 (dpkg 1.18.7; module version bumped on dpkg 1.18.24) 441 442New option: Add tests_dep option to Dpkg::Deps::deps_parse(). 443 444=head2 Version 1.05 (dpkg 1.17.14) 445 446New function: Dpkg::Deps::deps_iterate(). 447 448=head2 Version 1.04 (dpkg 1.17.10) 449 450New options: Add use_profiles, build_profiles, reduce_profiles and 451reduce_restrictions to Dpkg::Deps::deps_parse(). 452 453=head2 Version 1.03 (dpkg 1.17.0) 454 455New option: Add build_arch option to Dpkg::Deps::deps_parse(). 456 457=head2 Version 1.02 (dpkg 1.17.0) 458 459New function: Dpkg::Deps::deps_concat() 460 461=head2 Version 1.01 (dpkg 1.16.1) 462 463<Used to document changes to Dpkg::Deps::* modules before they were split.> 464 465=head2 Version 1.00 (dpkg 1.15.6) 466 467Mark the module as public. 468 469=cut 470 4711; 472