summaryrefslogtreecommitdiffstats
path: root/scripts/Dpkg/Deps
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--scripts/Dpkg/Deps.pm471
-rw-r--r--scripts/Dpkg/Deps/AND.pm182
-rw-r--r--scripts/Dpkg/Deps/KnownFacts.pm245
-rw-r--r--scripts/Dpkg/Deps/Multiple.pm250
-rw-r--r--scripts/Dpkg/Deps/OR.pm174
-rw-r--r--scripts/Dpkg/Deps/Simple.pm669
-rw-r--r--scripts/Dpkg/Deps/Union.pm119
7 files changed, 2110 insertions, 0 deletions
diff --git a/scripts/Dpkg/Deps.pm b/scripts/Dpkg/Deps.pm
new file mode 100644
index 0000000..f3a19e7
--- /dev/null
+++ b/scripts/Dpkg/Deps.pm
@@ -0,0 +1,471 @@
+# Copyright © 1998 Richard Braakman
+# Copyright © 1999 Darren Benham
+# Copyright © 2000 Sean 'Shaleh' Perry
+# Copyright © 2004 Frank Lichtenheld
+# Copyright © 2006 Russ Allbery
+# Copyright © 2007-2009 Raphaël Hertzog <hertzog@debian.org>
+# Copyright © 2008-2009,2012-2014 Guillem Jover <guillem@debian.org>
+#
+# This program is free software; you may redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program. If not, see <https://www.gnu.org/licenses/>.
+
+package Dpkg::Deps;
+
+=encoding utf8
+
+=head1 NAME
+
+Dpkg::Deps - parse and manipulate dependencies of Debian packages
+
+=head1 DESCRIPTION
+
+The Dpkg::Deps module provides objects implementing various types of
+dependencies.
+
+The most important function is deps_parse(), it turns a dependency line in
+a set of Dpkg::Deps::{Simple,AND,OR,Union} objects depending on the case.
+
+=head1 FUNCTIONS
+
+All the deps_* functions are exported by default.
+
+=over 4
+
+=cut
+
+use strict;
+use warnings;
+
+our $VERSION = '1.06';
+our @EXPORT = qw(
+ deps_concat
+ deps_parse
+ deps_eval_implication
+ deps_iterate
+ deps_compare
+);
+
+use Carp;
+use Exporter qw(import);
+
+use Dpkg::Version;
+use Dpkg::Arch qw(get_host_arch get_build_arch debarch_to_debtuple);
+use Dpkg::BuildProfiles qw(get_build_profiles);
+use Dpkg::ErrorHandling;
+use Dpkg::Gettext;
+use Dpkg::Deps::Simple;
+use Dpkg::Deps::Union;
+use Dpkg::Deps::AND;
+use Dpkg::Deps::OR;
+use Dpkg::Deps::KnownFacts;
+
+=item deps_eval_implication($rel_p, $v_p, $rel_q, $v_q)
+
+($rel_p, $v_p) and ($rel_q, $v_q) express two dependencies as (relation,
+version). The relation variable can have the following values that are
+exported by Dpkg::Version: REL_EQ, REL_LT, REL_LE, REL_GT, REL_GT.
+
+This functions returns 1 if the "p" dependency implies the "q"
+dependency. It returns 0 if the "p" dependency implies that "q" is
+not satisfied. It returns undef when there's no implication.
+
+The $v_p and $v_q parameter should be Dpkg::Version objects.
+
+=cut
+
+sub deps_eval_implication {
+ my ($rel_p, $v_p, $rel_q, $v_q) = @_;
+
+ # If versions are not valid, we can't decide of any implication
+ return unless defined($v_p) and $v_p->is_valid();
+ return unless defined($v_q) and $v_q->is_valid();
+
+ # q wants an exact version, so p must provide that exact version. p
+ # disproves q if q's version is outside the range enforced by p.
+ if ($rel_q eq REL_EQ) {
+ if ($rel_p eq REL_LT) {
+ return ($v_p <= $v_q) ? 0 : undef;
+ } elsif ($rel_p eq REL_LE) {
+ return ($v_p < $v_q) ? 0 : undef;
+ } elsif ($rel_p eq REL_GT) {
+ return ($v_p >= $v_q) ? 0 : undef;
+ } elsif ($rel_p eq REL_GE) {
+ return ($v_p > $v_q) ? 0 : undef;
+ } elsif ($rel_p eq REL_EQ) {
+ return ($v_p == $v_q);
+ }
+ }
+
+ # A greater than clause may disprove a less than clause. An equal
+ # cause might as well. Otherwise, if
+ # p's clause is <<, <=, or =, the version must be <= q's to imply q.
+ if ($rel_q eq REL_LE) {
+ if ($rel_p eq REL_GT) {
+ return ($v_p >= $v_q) ? 0 : undef;
+ } elsif ($rel_p eq REL_GE) {
+ return ($v_p > $v_q) ? 0 : undef;
+ } elsif ($rel_p eq REL_EQ) {
+ return ($v_p <= $v_q) ? 1 : 0;
+ } else { # <<, <=
+ return ($v_p <= $v_q) ? 1 : undef;
+ }
+ }
+
+ # Similar, but << is stronger than <= so p's version must be << q's
+ # version if the p relation is <= or =.
+ if ($rel_q eq REL_LT) {
+ if ($rel_p eq REL_GT or $rel_p eq REL_GE) {
+ return ($v_p >= $v_p) ? 0 : undef;
+ } elsif ($rel_p eq REL_LT) {
+ return ($v_p <= $v_q) ? 1 : undef;
+ } elsif ($rel_p eq REL_EQ) {
+ return ($v_p < $v_q) ? 1 : 0;
+ } else { # <<, <=
+ return ($v_p < $v_q) ? 1 : undef;
+ }
+ }
+
+ # Same logic as above, only inverted.
+ if ($rel_q eq REL_GE) {
+ if ($rel_p eq REL_LT) {
+ return ($v_p <= $v_q) ? 0 : undef;
+ } elsif ($rel_p eq REL_LE) {
+ return ($v_p < $v_q) ? 0 : undef;
+ } elsif ($rel_p eq REL_EQ) {
+ return ($v_p >= $v_q) ? 1 : 0;
+ } else { # >>, >=
+ return ($v_p >= $v_q) ? 1 : undef;
+ }
+ }
+ if ($rel_q eq REL_GT) {
+ if ($rel_p eq REL_LT or $rel_p eq REL_LE) {
+ return ($v_p <= $v_q) ? 0 : undef;
+ } elsif ($rel_p eq REL_GT) {
+ return ($v_p >= $v_q) ? 1 : undef;
+ } elsif ($rel_p eq REL_EQ) {
+ return ($v_p > $v_q) ? 1 : 0;
+ } else {
+ return ($v_p > $v_q) ? 1 : undef;
+ }
+ }
+
+ return;
+}
+
+=item $dep = deps_concat(@dep_list)
+
+This function concatenates multiple dependency lines into a single line,
+joining them with ", " if appropriate, and always returning a valid string.
+
+=cut
+
+sub deps_concat {
+ my (@dep_list) = @_;
+
+ return join ', ', grep { defined } @dep_list;
+}
+
+=item $dep = deps_parse($line, %options)
+
+This function parses the dependency line and returns an object, either a
+Dpkg::Deps::AND or a Dpkg::Deps::Union. Various options can alter the
+behaviour of that function.
+
+=over 4
+
+=item use_arch (defaults to 1)
+
+Take into account the architecture restriction part of the dependencies.
+Set to 0 to completely ignore that information.
+
+=item host_arch (defaults to the current architecture)
+
+Define the host architecture. By default it uses
+Dpkg::Arch::get_host_arch() to identify the proper architecture.
+
+=item build_arch (defaults to the current architecture)
+
+Define the build architecture. By default it uses
+Dpkg::Arch::get_build_arch() to identify the proper architecture.
+
+=item reduce_arch (defaults to 0)
+
+If set to 1, ignore dependencies that do not concern the current host
+architecture. This implicitly strips off the architecture restriction
+list so that the resulting dependencies are directly applicable to the
+current architecture.
+
+=item use_profiles (defaults to 1)
+
+Take into account the profile restriction part of the dependencies. Set
+to 0 to completely ignore that information.
+
+=item build_profiles (defaults to no profile)
+
+Define the active build profiles. By default no profile is defined.
+
+=item reduce_profiles (defaults to 0)
+
+If set to 1, ignore dependencies that do not concern the current build
+profile. This implicitly strips off the profile restriction formula so
+that the resulting dependencies are directly applicable to the current
+profiles.
+
+=item reduce_restrictions (defaults to 0)
+
+If set to 1, ignore dependencies that do not concern the current set of
+restrictions. This implicitly strips off any architecture restriction list
+or restriction formula so that the resulting dependencies are directly
+applicable to the current restriction.
+This currently implies C<reduce_arch> and C<reduce_profiles>, and overrides
+them if set.
+
+=item union (defaults to 0)
+
+If set to 1, returns a Dpkg::Deps::Union instead of a Dpkg::Deps::AND. Use
+this when parsing non-dependency fields like Conflicts.
+
+=item build_dep (defaults to 0)
+
+If set to 1, allow build-dep only arch qualifiers, that is “:native”.
+This should be set whenever working with build-deps.
+
+=item tests_dep (defaults to 0)
+
+If set to 1, allow tests-specific package names in dependencies, that is
+"@" and "@builddeps@" (since dpkg 1.18.7). This should be set whenever
+working with dependency fields from F<debian/tests/control>.
+
+=back
+
+=cut
+
+sub deps_parse {
+ my ($dep_line, %options) = @_;
+
+ # Validate arguments.
+ croak "invalid host_arch $options{host_arch}"
+ if defined $options{host_arch} and not defined debarch_to_debtuple($options{host_arch});
+ croak "invalid build_arch $options{build_arch}"
+ if defined $options{build_arch} and not defined debarch_to_debtuple($options{build_arch});
+
+ $options{use_arch} //= 1;
+ $options{reduce_arch} //= 0;
+ $options{use_profiles} //= 1;
+ $options{reduce_profiles} //= 0;
+ $options{reduce_restrictions} //= 0;
+ $options{union} //= 0;
+ $options{build_dep} //= 0;
+ $options{tests_dep} //= 0;
+
+ if ($options{reduce_restrictions}) {
+ $options{reduce_arch} = 1;
+ $options{reduce_profiles} = 1;
+ }
+ if ($options{reduce_arch}) {
+ $options{host_arch} //= get_host_arch();
+ $options{build_arch} //= get_build_arch();
+ }
+ if ($options{reduce_profiles}) {
+ $options{build_profiles} //= [ get_build_profiles() ];
+ }
+
+ # Options for Dpkg::Deps::Simple.
+ my %deps_options = (
+ host_arch => $options{host_arch},
+ build_arch => $options{build_arch},
+ build_dep => $options{build_dep},
+ tests_dep => $options{tests_dep},
+ );
+
+ # Strip trailing/leading spaces
+ $dep_line =~ s/^\s+//;
+ $dep_line =~ s/\s+$//;
+
+ my @dep_list;
+ foreach my $dep_and (split(/\s*,\s*/m, $dep_line)) {
+ my @or_list = ();
+ foreach my $dep_or (split(/\s*\|\s*/m, $dep_and)) {
+ my $dep_simple = Dpkg::Deps::Simple->new($dep_or, %deps_options);
+ if (not defined $dep_simple->{package}) {
+ warning(g_("can't parse dependency %s"), $dep_or);
+ return;
+ }
+ $dep_simple->{arches} = undef if not $options{use_arch};
+ if ($options{reduce_arch}) {
+ $dep_simple->reduce_arch($options{host_arch});
+ next if not $dep_simple->arch_is_concerned($options{host_arch});
+ }
+ $dep_simple->{restrictions} = undef if not $options{use_profiles};
+ if ($options{reduce_profiles}) {
+ $dep_simple->reduce_profiles($options{build_profiles});
+ next if not $dep_simple->profile_is_concerned($options{build_profiles});
+ }
+ push @or_list, $dep_simple;
+ }
+ next if not @or_list;
+ if (scalar @or_list == 1) {
+ push @dep_list, $or_list[0];
+ } else {
+ my $dep_or = Dpkg::Deps::OR->new();
+ $dep_or->add($_) foreach (@or_list);
+ push @dep_list, $dep_or;
+ }
+ }
+ my $dep_and;
+ if ($options{union}) {
+ $dep_and = Dpkg::Deps::Union->new();
+ } else {
+ $dep_and = Dpkg::Deps::AND->new();
+ }
+ foreach my $dep (@dep_list) {
+ if ($options{union} and not $dep->isa('Dpkg::Deps::Simple')) {
+ warning(g_('an union dependency can only contain simple dependencies'));
+ return;
+ }
+ $dep_and->add($dep);
+ }
+ return $dep_and;
+}
+
+=item $bool = deps_iterate($deps, $callback_func)
+
+This function visits all elements of the dependency object, calling the
+callback function for each element.
+
+The callback function is expected to return true when everything is fine,
+or false if something went wrong, in which case the iteration will stop.
+
+Return the same value as the callback function.
+
+=cut
+
+sub deps_iterate {
+ my ($deps, $callback_func) = @_;
+
+ my $visitor_func;
+ $visitor_func = sub {
+ foreach my $dep (@_) {
+ return unless defined $dep;
+
+ if ($dep->isa('Dpkg::Deps::Simple')) {
+ return unless $callback_func->($dep);
+ } else {
+ return unless $visitor_func->($dep->get_deps());
+ }
+ }
+ return 1;
+ };
+
+ return $visitor_func->($deps);
+}
+
+=item deps_compare($a, $b)
+
+Implements a comparison operator between two dependency objects.
+This function is mainly used to implement the sort() method.
+
+=back
+
+=cut
+
+my %relation_ordering = (
+ undef => 0,
+ REL_GE() => 1,
+ REL_GT() => 2,
+ REL_EQ() => 3,
+ REL_LT() => 4,
+ REL_LE() => 5,
+);
+
+sub deps_compare {
+ my ($aref, $bref) = @_;
+
+ my (@as, @bs);
+ deps_iterate($aref, sub { push @as, @_ });
+ deps_iterate($bref, sub { push @bs, @_ });
+
+ while (1) {
+ my ($a, $b) = (shift @as, shift @bs);
+ my $aundef = not defined $a or $a->is_empty();
+ my $bundef = not defined $b or $b->is_empty();
+
+ return 0 if $aundef and $bundef;
+ return -1 if $aundef;
+ return 1 if $bundef;
+
+ my $ar = $a->{relation} // 'undef';
+ my $br = $b->{relation} // 'undef';
+ my $av = $a->{version} // '';
+ my $bv = $b->{version} // '';
+
+ my $res = (($a->{package} cmp $b->{package}) ||
+ ($relation_ordering{$ar} <=> $relation_ordering{$br}) ||
+ ($av cmp $bv));
+ return $res if $res != 0;
+ }
+}
+
+=head1 OBJECTS - Dpkg::Deps::*
+
+There are several kind of dependencies. A Dpkg::Deps::Simple dependency
+represents a single dependency statement (it relates to one package only).
+Dpkg::Deps::Multiple dependencies are built on top of this object
+and combine several dependencies in different manners. Dpkg::Deps::AND
+represents the logical "AND" between dependencies while Dpkg::Deps::OR
+represents the logical "OR". Dpkg::Deps::Multiple objects can contain
+Dpkg::Deps::Simple object as well as other Dpkg::Deps::Multiple objects.
+
+In practice, the code is only meant to handle the realistic cases which,
+given Debian's dependencies structure, imply those restrictions: AND can
+contain Simple or OR objects, OR can only contain Simple objects.
+
+Dpkg::Deps::KnownFacts is a special object that is used while evaluating
+dependencies and while trying to simplify them. It represents a set of
+installed packages along with the virtual packages that they might
+provide.
+
+=head1 CHANGES
+
+=head2 Version 1.06 (dpkg 1.18.7; module version bumped on dpkg 1.18.24)
+
+New option: Add tests_dep option to Dpkg::Deps::deps_parse().
+
+=head2 Version 1.05 (dpkg 1.17.14)
+
+New function: Dpkg::Deps::deps_iterate().
+
+=head2 Version 1.04 (dpkg 1.17.10)
+
+New options: Add use_profiles, build_profiles, reduce_profiles and
+reduce_restrictions to Dpkg::Deps::deps_parse().
+
+=head2 Version 1.03 (dpkg 1.17.0)
+
+New option: Add build_arch option to Dpkg::Deps::deps_parse().
+
+=head2 Version 1.02 (dpkg 1.17.0)
+
+New function: Dpkg::Deps::deps_concat()
+
+=head2 Version 1.01 (dpkg 1.16.1)
+
+<Used to document changes to Dpkg::Deps::* modules before they were split.>
+
+=head2 Version 1.00 (dpkg 1.15.6)
+
+Mark the module as public.
+
+=cut
+
+1;
diff --git a/scripts/Dpkg/Deps/AND.pm b/scripts/Dpkg/Deps/AND.pm
new file mode 100644
index 0000000..e16a2cf
--- /dev/null
+++ b/scripts/Dpkg/Deps/AND.pm
@@ -0,0 +1,182 @@
+# Copyright © 1998 Richard Braakman
+# Copyright © 1999 Darren Benham
+# Copyright © 2000 Sean 'Shaleh' Perry
+# Copyright © 2004 Frank Lichtenheld
+# Copyright © 2006 Russ Allbery
+# Copyright © 2007-2009 Raphaël Hertzog <hertzog@debian.org>
+# Copyright © 2008-2009, 2012-2014 Guillem Jover <guillem@debian.org>
+#
+# This program is free software; you may redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program. If not, see <https://www.gnu.org/licenses/>.
+
+package Dpkg::Deps::AND;
+
+=encoding utf8
+
+=head1 NAME
+
+Dpkg::Deps::AND - list of AND dependencies
+
+=head1 DESCRIPTION
+
+This object represents a list of dependencies that must be met at the same
+time. It inherits from Dpkg::Deps::Multiple.
+
+=cut
+
+use strict;
+use warnings;
+
+our $VERSION = '1.00';
+
+use parent qw(Dpkg::Deps::Multiple);
+
+=head1 METHODS
+
+=over 4
+
+=item $dep->output([$fh])
+
+The output method uses ", " to join the list of sub-dependencies.
+
+=cut
+
+sub output {
+ my ($self, $fh) = @_;
+
+ my $res = join(', ', map {
+ $_->output()
+ } grep {
+ not $_->is_empty()
+ } $self->get_deps());
+
+ if (defined $fh) {
+ print { $fh } $res;
+ }
+ return $res;
+}
+
+=item $dep->implies($other_dep)
+
+Returns 1 when $dep implies $other_dep. Returns 0 when $dep implies
+NOT($other_dep). Returns undef when there's no implication. $dep and
+$other_dep do not need to be of the same type.
+
+=cut
+
+sub implies {
+ my ($self, $o) = @_;
+
+ # If any individual member can imply $o or NOT $o, we're fine
+ foreach my $dep ($self->get_deps()) {
+ my $implication = $dep->implies($o);
+ return 1 if defined $implication and $implication == 1;
+ return 0 if defined $implication and $implication == 0;
+ }
+
+ # If o is an AND, we might have an implication, if we find an
+ # implication within us for each predicate in o
+ if ($o->isa('Dpkg::Deps::AND')) {
+ my $subset = 1;
+ foreach my $odep ($o->get_deps()) {
+ my $found = 0;
+ foreach my $dep ($self->get_deps()) {
+ $found = 1 if $dep->implies($odep);
+ }
+ $subset = 0 if not $found;
+ }
+ return 1 if $subset;
+ }
+ return;
+}
+
+=item $dep->get_evaluation($facts)
+
+Evaluates the dependency given a list of installed packages and a list of
+virtual packages provided. These lists are part of the Dpkg::Deps::KnownFacts
+object given as parameters.
+
+Returns 1 when it's true, 0 when it's false, undef when some information
+is lacking to conclude.
+
+=cut
+
+sub get_evaluation {
+ my ($self, $facts) = @_;
+
+ # Return 1 only if all members evaluates to true
+ # Return 0 if at least one member evaluates to false
+ # Return undef otherwise
+ my $result = 1;
+ foreach my $dep ($self->get_deps()) {
+ my $eval = $dep->get_evaluation($facts);
+ if (not defined $eval) {
+ $result = undef;
+ } elsif ($eval == 0) {
+ $result = 0;
+ last;
+ } elsif ($eval == 1) {
+ # Still possible
+ }
+ }
+ return $result;
+}
+
+=item $dep->simplify_deps($facts, @assumed_deps)
+
+Simplifies the dependency as much as possible given the list of facts (see
+object Dpkg::Deps::KnownFacts) and a list of other dependencies that are
+known to be true.
+
+=cut
+
+sub simplify_deps {
+ my ($self, $facts, @knowndeps) = @_;
+ my @new;
+
+WHILELOOP:
+ while (@{$self->{list}}) {
+ my $dep = shift @{$self->{list}};
+ my $eval = $dep->get_evaluation($facts);
+ next if defined $eval and $eval == 1;
+ foreach my $odep (@knowndeps, @new) {
+ next WHILELOOP if $odep->implies($dep);
+ }
+ # When a dependency is implied by another dependency that
+ # follows, then invert them
+ # "a | b, c, a" becomes "a, c" and not "c, a"
+ my $i = 0;
+ foreach my $odep (@{$self->{list}}) {
+ if (defined $odep and $odep->implies($dep)) {
+ splice @{$self->{list}}, $i, 1;
+ unshift @{$self->{list}}, $odep;
+ next WHILELOOP;
+ }
+ $i++;
+ }
+ push @new, $dep;
+ }
+ $self->{list} = [ @new ];
+}
+
+=back
+
+=head1 CHANGES
+
+=head2 Version 1.00 (dpkg 1.15.6)
+
+Mark the module as public.
+
+=cut
+
+1;
diff --git a/scripts/Dpkg/Deps/KnownFacts.pm b/scripts/Dpkg/Deps/KnownFacts.pm
new file mode 100644
index 0000000..192f6aa
--- /dev/null
+++ b/scripts/Dpkg/Deps/KnownFacts.pm
@@ -0,0 +1,245 @@
+# Copyright © 1998 Richard Braakman
+# Copyright © 1999 Darren Benham
+# Copyright © 2000 Sean 'Shaleh' Perry
+# Copyright © 2004 Frank Lichtenheld
+# Copyright © 2006 Russ Allbery
+# Copyright © 2007-2009 Raphaël Hertzog <hertzog@debian.org>
+# Copyright © 2008-2009, 2012-2014 Guillem Jover <guillem@debian.org>
+#
+# This program is free software; you may redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program. If not, see <https://www.gnu.org/licenses/>.
+
+package Dpkg::Deps::KnownFacts;
+
+=encoding utf8
+
+=head1 NAME
+
+Dpkg::Deps::KnownFacts - list of installed real and virtual packages
+
+=head1 DESCRIPTION
+
+This object represents a list of installed packages and a list of virtual
+packages provided (by the set of installed packages).
+
+=cut
+
+use strict;
+use warnings;
+
+our $VERSION = '1.01';
+
+use Dpkg::Version;
+
+=head1 METHODS
+
+=over 4
+
+=item $facts = Dpkg::Deps::KnownFacts->new();
+
+Creates a new object.
+
+=cut
+
+sub new {
+ my $this = shift;
+ my $class = ref($this) || $this;
+ my $self = {
+ pkg => {},
+ virtualpkg => {},
+ };
+
+ bless $self, $class;
+ return $self;
+}
+
+=item $facts->add_installed_package($package, $version, $arch, $multiarch)
+
+Records that the given version of the package is installed. If
+$version/$arch is undefined we know that the package is installed but we
+don't know which version/architecture it is. $multiarch is the Multi-Arch
+field of the package. If $multiarch is undef, it will be equivalent to
+"Multi-Arch: no".
+
+Note that $multiarch is only used if $arch is provided.
+
+=cut
+
+sub add_installed_package {
+ my ($self, $pkg, $ver, $arch, $multiarch) = @_;
+ my $p = {
+ package => $pkg,
+ version => $ver,
+ architecture => $arch,
+ multiarch => $multiarch // 'no',
+ };
+
+ $self->{pkg}{"$pkg:$arch"} = $p if defined $arch;
+ push @{$self->{pkg}{$pkg}}, $p;
+}
+
+=item $facts->add_provided_package($virtual, $relation, $version, $by)
+
+Records that the "$by" package provides the $virtual package. $relation
+and $version correspond to the associated relation given in the Provides
+field (if present).
+
+=cut
+
+sub add_provided_package {
+ my ($self, $pkg, $rel, $ver, $by) = @_;
+ my $v = {
+ package => $pkg,
+ relation => $rel,
+ version => $ver,
+ provider => $by,
+ };
+
+ $self->{virtualpkg}{$pkg} //= [];
+ push @{$self->{virtualpkg}{$pkg}}, $v;
+}
+
+=item ($check, $param) = $facts->check_package($package)
+
+$check is one when the package is found. For a real package, $param
+contains the version. For a virtual package, $param contains an array
+reference containing the list of packages that provide it (each package is
+listed as [ $provider, $relation, $version ]).
+
+This function is obsolete and should not be used. Dpkg::Deps::KnownFacts
+is only meant to be filled with data and then passed to Dpkg::Deps
+methods where appropriate, but it should not be directly queried.
+
+=cut
+
+sub check_package {
+ my ($self, $pkg) = @_;
+
+ warnings::warnif('deprecated', 'obsolete function, pass ' .
+ 'Dpkg::Deps::KnownFacts to Dpkg::Deps methods instead');
+
+ if (exists $self->{pkg}{$pkg}) {
+ return (1, $self->{pkg}{$pkg}[0]{version});
+ }
+ if (exists $self->{virtualpkg}{$pkg}) {
+ my $arrayref = [ map { [
+ $_->{provider}, $_->{relation}, $_->{version}
+ ] } @{$self->{virtualpkg}{$pkg}} ];
+ return (1, $arrayref);
+ }
+ return (0, undef);
+}
+
+##
+## The functions below are private to Dpkg::Deps::KnownFacts.
+##
+
+sub _find_package {
+ my ($self, $dep, $lackinfos) = @_;
+ my ($pkg, $archqual) = ($dep->{package}, $dep->{archqual});
+
+ return if not exists $self->{pkg}{$pkg};
+
+ my $host_arch = $dep->{host_arch} // Dpkg::Arch::get_host_arch();
+ my $build_arch = $dep->{build_arch} // Dpkg::Arch::get_build_arch();
+
+ foreach my $p (@{$self->{pkg}{$pkg}}) {
+ my $a = $p->{architecture};
+ my $ma = $p->{multiarch};
+
+ if (not defined $a) {
+ $$lackinfos = 1;
+ next;
+ }
+ if (not defined $archqual) {
+ return $p if $ma eq 'foreign';
+ return $p if $a eq $host_arch or $a eq 'all';
+ } elsif ($archqual eq 'any') {
+ return $p if $ma eq 'allowed';
+ } elsif ($archqual eq 'native') {
+ return if $ma eq 'foreign';
+ return $p if $a eq $build_arch or $a eq 'all';
+ } else {
+ return $p if $a eq $archqual;
+ }
+ }
+ return;
+}
+
+sub _find_virtual_packages {
+ my ($self, $pkg) = @_;
+
+ return () if not exists $self->{virtualpkg}{$pkg};
+ return @{$self->{virtualpkg}{$pkg}};
+}
+
+=item $facts->evaluate_simple_dep()
+
+This method is private and should not be used except from within Dpkg::Deps.
+
+=cut
+
+sub evaluate_simple_dep {
+ my ($self, $dep) = @_;
+ my ($lackinfos, $pkg) = (0, $dep->{package});
+
+ my $p = $self->_find_package($dep, \$lackinfos);
+ if ($p) {
+ if (defined $dep->{relation}) {
+ if (defined $p->{version}) {
+ return 1 if version_compare_relation($p->{version},
+ $dep->{relation},
+ $dep->{version});
+ } else {
+ $lackinfos = 1;
+ }
+ } else {
+ return 1;
+ }
+ }
+ foreach my $virtpkg ($self->_find_virtual_packages($pkg)) {
+ next if defined $virtpkg->{relation} and
+ $virtpkg->{relation} ne REL_EQ;
+
+ if (defined $dep->{relation}) {
+ next if not defined $virtpkg->{version};
+ return 1 if version_compare_relation($virtpkg->{version},
+ $dep->{relation},
+ $dep->{version});
+ } else {
+ return 1;
+ }
+ }
+ return if $lackinfos;
+ return 0;
+}
+
+=back
+
+=head1 CHANGES
+
+=head2 Version 1.01 (dpkg 1.16.1)
+
+New option: Dpkg::Deps::KnownFacts->add_installed_package() now accepts 2
+supplementary parameters ($arch and $multiarch).
+
+Deprecated method: Dpkg::Deps::KnownFacts->check_package() is obsolete,
+it should not have been part of the public API.
+
+=head2 Version 1.00 (dpkg 1.15.6)
+
+Mark the module as public.
+
+=cut
+
+1;
diff --git a/scripts/Dpkg/Deps/Multiple.pm b/scripts/Dpkg/Deps/Multiple.pm
new file mode 100644
index 0000000..da12f51
--- /dev/null
+++ b/scripts/Dpkg/Deps/Multiple.pm
@@ -0,0 +1,250 @@
+# Copyright © 1998 Richard Braakman
+# Copyright © 1999 Darren Benham
+# Copyright © 2000 Sean 'Shaleh' Perry
+# Copyright © 2004 Frank Lichtenheld
+# Copyright © 2006 Russ Allbery
+# Copyright © 2007-2009 Raphaël Hertzog <hertzog@debian.org>
+# Copyright © 2008-2009, 2012-2014 Guillem Jover <guillem@debian.org>
+#
+# This program is free software; you may redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program. If not, see <https://www.gnu.org/licenses/>.
+
+package Dpkg::Deps::Multiple;
+
+=encoding utf8
+
+=head1 NAME
+
+Dpkg::Deps::Multiple - base module to represent multiple dependencies
+
+=head1 DESCRIPTION
+
+The Dpkg::Deps::Multiple module provides objects implementing various types
+of dependencies. It is the base class for Dpkg::Deps::{AND,OR,Union}.
+
+=cut
+
+use strict;
+use warnings;
+
+our $VERSION = '1.02';
+
+use Carp;
+
+use Dpkg::ErrorHandling;
+
+use parent qw(Dpkg::Interface::Storable);
+
+=head1 METHODS
+
+=over 4
+
+=item $dep = Dpkg::Deps::Multiple->new(%opts);
+
+Creates a new object.
+
+=cut
+
+sub new {
+ my $this = shift;
+ my $class = ref($this) || $this;
+ my $self = { list => [ @_ ] };
+
+ bless $self, $class;
+ return $self;
+}
+
+=item $dep->reset()
+
+Clears any dependency information stored in $dep so that $dep->is_empty()
+returns true.
+
+=cut
+
+sub reset {
+ my $self = shift;
+
+ $self->{list} = [];
+}
+
+=item $dep->add(@deps)
+
+Adds new dependency objects at the end of the list.
+
+=cut
+
+sub add {
+ my $self = shift;
+
+ push @{$self->{list}}, @_;
+}
+
+=item $dep->get_deps()
+
+Returns a list of sub-dependencies.
+
+=cut
+
+sub get_deps {
+ my $self = shift;
+
+ return grep { not $_->is_empty() } @{$self->{list}};
+}
+
+=item $dep->sort()
+
+Sorts alphabetically the internal list of dependencies.
+
+=cut
+
+sub sort {
+ my $self = shift;
+
+ my @res = ();
+ @res = sort { Dpkg::Deps::deps_compare($a, $b) } @{$self->{list}};
+ $self->{list} = [ @res ];
+}
+
+=item $dep->arch_is_concerned($arch)
+
+Returns true if at least one of the sub-dependencies apply to this
+architecture.
+
+=cut
+
+sub arch_is_concerned {
+ my ($self, $host_arch) = @_;
+
+ my $res = 0;
+ foreach my $dep (@{$self->{list}}) {
+ $res = 1 if $dep->arch_is_concerned($host_arch);
+ }
+ return $res;
+}
+
+=item $dep->reduce_arch($arch)
+
+Simplifies the dependencies to contain only information relevant to the
+given architecture. The non-relevant sub-dependencies are simply removed.
+
+This trims off the architecture restriction list of Dpkg::Deps::Simple
+objects.
+
+=cut
+
+sub reduce_arch {
+ my ($self, $host_arch) = @_;
+
+ my @new;
+ foreach my $dep (@{$self->{list}}) {
+ $dep->reduce_arch($host_arch);
+ push @new, $dep if $dep->arch_is_concerned($host_arch);
+ }
+ $self->{list} = [ @new ];
+}
+
+=item $dep->has_arch_restriction()
+
+Returns the list of package names that have such a restriction.
+
+=cut
+
+sub has_arch_restriction {
+ my $self = shift;
+
+ my @res;
+ foreach my $dep (@{$self->{list}}) {
+ push @res, $dep->has_arch_restriction();
+ }
+ return @res;
+}
+
+=item $dep->profile_is_concerned()
+
+Returns true if at least one of the sub-dependencies apply to this profile.
+
+=cut
+
+sub profile_is_concerned {
+ my ($self, $build_profiles) = @_;
+
+ my $res = 0;
+ foreach my $dep (@{$self->{list}}) {
+ $res = 1 if $dep->profile_is_concerned($build_profiles);
+ }
+ return $res;
+}
+
+=item $dep->reduce_profiles()
+
+Simplifies the dependencies to contain only information relevant to the
+given profile. The non-relevant sub-dependencies are simply removed.
+
+This trims off the profile restriction list of Dpkg::Deps::Simple objects.
+
+=cut
+
+sub reduce_profiles {
+ my ($self, $build_profiles) = @_;
+
+ my @new;
+ foreach my $dep (@{$self->{list}}) {
+ $dep->reduce_profiles($build_profiles);
+ push @new, $dep if $dep->profile_is_concerned($build_profiles);
+ }
+ $self->{list} = [ @new ];
+}
+
+=item $dep->is_empty()
+
+Returns true if the dependency is empty and doesn't contain any useful
+information. This is true when a (descendant of) Dpkg::Deps::Multiple
+contains an empty list of dependencies.
+
+=cut
+
+sub is_empty {
+ my $self = shift;
+
+ return scalar @{$self->{list}} == 0;
+}
+
+=item $dep->merge_union($other_dep)
+
+This method is not meaningful for this object, and will always croak.
+
+=cut
+
+sub merge_union {
+ croak 'method merge_union() is only valid for Dpkg::Deps::Simple';
+}
+
+=back
+
+=head1 CHANGES
+
+=head2 Version 1.02 (dpkg 1.17.10)
+
+New methods: Add $dep->profile_is_concerned() and $dep->reduce_profiles().
+
+=head2 Version 1.01 (dpkg 1.16.1)
+
+New method: Add $dep->reset().
+
+=head2 Version 1.00 (dpkg 1.15.6)
+
+Mark the module as public.
+
+=cut
+
+1;
diff --git a/scripts/Dpkg/Deps/OR.pm b/scripts/Dpkg/Deps/OR.pm
new file mode 100644
index 0000000..b2f8d03
--- /dev/null
+++ b/scripts/Dpkg/Deps/OR.pm
@@ -0,0 +1,174 @@
+# Copyright © 1998 Richard Braakman
+# Copyright © 1999 Darren Benham
+# Copyright © 2000 Sean 'Shaleh' Perry
+# Copyright © 2004 Frank Lichtenheld
+# Copyright © 2006 Russ Allbery
+# Copyright © 2007-2009 Raphaël Hertzog <hertzog@debian.org>
+# Copyright © 2008-2009, 2012-2014 Guillem Jover <guillem@debian.org>
+#
+# This program is free software; you may redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program. If not, see <https://www.gnu.org/licenses/>.
+
+package Dpkg::Deps::OR;
+
+=encoding utf8
+
+=head1 NAME
+
+Dpkg::Deps::OR - list of OR dependencies
+
+=head1 DESCRIPTION
+
+This object represents a list of dependencies of which only one must be met
+for the dependency to be true. It inherits from Dpkg::Deps::Multiple.
+
+=cut
+
+use strict;
+use warnings;
+
+our $VERSION = '1.00';
+
+use parent qw(Dpkg::Deps::Multiple);
+
+=head1 METHODS
+
+=over 4
+
+=item $dep->output([$fh])
+
+The output method uses " | " to join the list of sub-dependencies.
+
+=cut
+
+sub output {
+ my ($self, $fh) = @_;
+
+ my $res = join(' | ', map {
+ $_->output()
+ } grep {
+ not $_->is_empty()
+ } $self->get_deps());
+
+ if (defined $fh) {
+ print { $fh } $res;
+ }
+ return $res;
+}
+
+=item $dep->implies($other_dep)
+
+Returns 1 when $dep implies $other_dep. Returns 0 when $dep implies
+NOT($other_dep). Returns undef when there's no implication. $dep and
+$other_dep do not need to be of the same type.
+
+=cut
+
+sub implies {
+ my ($self, $o) = @_;
+
+ # Special case for AND with a single member, replace it by its member
+ if ($o->isa('Dpkg::Deps::AND')) {
+ my @subdeps = $o->get_deps();
+ if (scalar(@subdeps) == 1) {
+ $o = $subdeps[0];
+ }
+ }
+
+ # In general, an OR dependency can't imply anything except if each
+ # of its member implies a member in the other OR dependency
+ if ($o->isa('Dpkg::Deps::OR')) {
+ my $subset = 1;
+ foreach my $dep ($self->get_deps()) {
+ my $found = 0;
+ foreach my $odep ($o->get_deps()) {
+ $found = 1 if $dep->implies($odep);
+ }
+ $subset = 0 if not $found;
+ }
+ return 1 if $subset;
+ }
+ return;
+}
+
+=item $dep->get_evaluation($facts)
+
+Evaluates the dependency given a list of installed packages and a list of
+virtual packages provided. These lists are part of the Dpkg::Deps::KnownFacts
+object given as parameters.
+
+Returns 1 when it's true, 0 when it's false, undef when some information
+is lacking to conclude.
+
+=cut
+
+sub get_evaluation {
+ my ($self, $facts) = @_;
+
+ # Returns false if all members evaluates to 0
+ # Returns true if at least one member evaluates to true
+ # Returns undef otherwise
+ my $result = 0;
+ foreach my $dep ($self->get_deps()) {
+ my $eval = $dep->get_evaluation($facts);
+ if (not defined $eval) {
+ $result = undef;
+ } elsif ($eval == 1) {
+ $result = 1;
+ last;
+ } elsif ($eval == 0) {
+ # Still possible to have a false evaluation
+ }
+ }
+ return $result;
+}
+
+=item $dep->simplify_deps($facts, @assumed_deps)
+
+Simplifies the dependency as much as possible given the list of facts (see
+object Dpkg::Deps::KnownFacts) and a list of other dependencies that are
+known to be true.
+
+=cut
+
+sub simplify_deps {
+ my ($self, $facts) = @_;
+ my @new;
+
+WHILELOOP:
+ while (@{$self->{list}}) {
+ my $dep = shift @{$self->{list}};
+ my $eval = $dep->get_evaluation($facts);
+ if (defined $eval and $eval == 1) {
+ $self->{list} = [];
+ return;
+ }
+ foreach my $odep (@new, @{$self->{list}}) {
+ next WHILELOOP if $odep->implies($dep);
+ }
+ push @new, $dep;
+ }
+ $self->{list} = [ @new ];
+}
+
+=back
+
+=head1 CHANGES
+
+=head2 Version 1.00 (dpkg 1.15.6)
+
+Mark the module as public.
+
+=cut
+
+1;
diff --git a/scripts/Dpkg/Deps/Simple.pm b/scripts/Dpkg/Deps/Simple.pm
new file mode 100644
index 0000000..efe635c
--- /dev/null
+++ b/scripts/Dpkg/Deps/Simple.pm
@@ -0,0 +1,669 @@
+# Copyright © 1998 Richard Braakman
+# Copyright © 1999 Darren Benham
+# Copyright © 2000 Sean 'Shaleh' Perry
+# Copyright © 2004 Frank Lichtenheld
+# Copyright © 2006 Russ Allbery
+# Copyright © 2007-2009 Raphaël Hertzog <hertzog@debian.org>
+# Copyright © 2008-2009, 2012-2014 Guillem Jover <guillem@debian.org>
+#
+# This program is free software; you may redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program. If not, see <https://www.gnu.org/licenses/>.
+
+package Dpkg::Deps::Simple;
+
+=encoding utf8
+
+=head1 NAME
+
+Dpkg::Deps::Simple - represents a single dependency statement
+
+=head1 DESCRIPTION
+
+This object has several interesting properties:
+
+=over 4
+
+=item package
+
+The package name (can be undef if the dependency has not been initialized
+or if the simplification of the dependency lead to its removal).
+
+=item relation
+
+The relational operator: "=", "<<", "<=", ">=" or ">>". It can be
+undefined if the dependency had no version restriction. In that case the
+following field is also undefined.
+
+=item version
+
+The version.
+
+=item arches
+
+The list of architectures where this dependency is applicable. It is
+undefined when there's no restriction, otherwise it is an
+array ref. It can contain an exclusion list, in that case each
+architecture is prefixed with an exclamation mark.
+
+=item archqual
+
+The arch qualifier of the dependency (can be undef if there is none).
+In the dependency "python:any (>= 2.6)", the arch qualifier is "any".
+
+=item restrictions
+
+The restrictions formula for this dependency. It is undefined when there
+is no restriction formula. Otherwise it is an array ref.
+
+=back
+
+=head1 METHODS
+
+=over 4
+
+=cut
+
+use strict;
+use warnings;
+
+our $VERSION = '1.02';
+
+use Carp;
+
+use Dpkg::Arch qw(debarch_is_concerned debarch_list_parse);
+use Dpkg::BuildProfiles qw(parse_build_profiles evaluate_restriction_formula);
+use Dpkg::Version;
+use Dpkg::ErrorHandling;
+use Dpkg::Gettext;
+
+use parent qw(Dpkg::Interface::Storable);
+
+=item $dep = Dpkg::Deps::Simple->new([$dep[, %opts]]);
+
+Creates a new object. Some options can be set through %opts:
+
+=over
+
+=item host_arch
+
+Sets the host architecture.
+
+=item build_arch
+
+Sets the build architecture.
+
+=item build_dep
+
+Specifies whether the parser should consider it a build dependency.
+Defaults to 0.
+
+=item tests_dep
+
+Specifies whether the parser should consider it a tests dependency.
+Defaults to 0.
+
+=back
+
+=cut
+
+sub new {
+ my ($this, $arg, %opts) = @_;
+ my $class = ref($this) || $this;
+ my $self = {};
+
+ bless $self, $class;
+ $self->reset();
+ $self->{host_arch} = $opts{host_arch};
+ $self->{build_arch} = $opts{build_arch};
+ $self->{build_dep} = $opts{build_dep} // 0;
+ $self->{tests_dep} = $opts{tests_dep} // 0;
+ $self->parse_string($arg) if defined $arg;
+ return $self;
+}
+
+=item $dep->reset()
+
+Clears any dependency information stored in $dep so that $dep->is_empty()
+returns true.
+
+=cut
+
+sub reset {
+ my $self = shift;
+
+ $self->{package} = undef;
+ $self->{relation} = undef;
+ $self->{version} = undef;
+ $self->{arches} = undef;
+ $self->{archqual} = undef;
+ $self->{restrictions} = undef;
+}
+
+=item $dep->parse_string($dep_string)
+
+Parses the dependency string and modifies internal properties to match the
+parsed dependency.
+
+=cut
+
+sub parse_string {
+ my ($self, $dep) = @_;
+
+ my $pkgname_re;
+ if ($self->{tests_dep}) {
+ $pkgname_re = qr/[\@a-zA-Z0-9][\@a-zA-Z0-9+.-]*/;
+ } else {
+ $pkgname_re = qr/[a-zA-Z0-9][a-zA-Z0-9+.-]*/;
+ }
+
+ return if not $dep =~
+ m{^\s* # skip leading whitespace
+ ($pkgname_re) # package name
+ (?: # start of optional part
+ : # colon for architecture
+ ([a-zA-Z0-9][a-zA-Z0-9-]*) # architecture name
+ )? # end of optional part
+ (?: # start of optional part
+ \s* \( # open parenthesis for version part
+ \s* (<<|<=|=|>=|>>|[<>]) # relation part
+ \s* ([^\)\s]+) # do not attempt to parse version
+ \s* \) # closing parenthesis
+ )? # end of optional part
+ (?: # start of optional architecture
+ \s* \[ # open bracket for architecture
+ \s* ([^\]]+) # don't parse architectures now
+ \s* \] # closing bracket
+ )? # end of optional architecture
+ (
+ (?: # start of optional restriction
+ \s* < # open bracket for restriction
+ \s* [^>]+ # do not parse restrictions now
+ \s* > # closing bracket
+ )+
+ )? # end of optional restriction
+ \s*$ # trailing spaces at end
+ }x;
+ if (defined $2) {
+ return if $2 eq 'native' and not $self->{build_dep};
+ $self->{archqual} = $2;
+ }
+ $self->{package} = $1;
+ $self->{relation} = version_normalize_relation($3) if defined $3;
+ if (defined $4) {
+ $self->{version} = Dpkg::Version->new($4);
+ }
+ if (defined $5) {
+ $self->{arches} = [ debarch_list_parse($5) ];
+ }
+ if (defined $6) {
+ $self->{restrictions} = [ parse_build_profiles($6) ];
+ }
+}
+
+=item $dep->parse($fh, $desc)
+
+Parse a dependency line from a filehandle.
+
+=cut
+
+sub parse {
+ my ($self, $fh, $desc) = @_;
+
+ my $line = <$fh>;
+ chomp $line;
+ return $self->parse_string($line);
+}
+
+=item $dep->load($filename)
+
+Parse a dependency line from $filename.
+
+=item $dep->output([$fh])
+
+=item "$dep"
+
+Returns a string representing the dependency. If $fh is set, it prints
+the string to the filehandle.
+
+=cut
+
+sub output {
+ my ($self, $fh) = @_;
+
+ my $res = $self->{package};
+ if (defined $self->{archqual}) {
+ $res .= ':' . $self->{archqual};
+ }
+ if (defined $self->{relation}) {
+ $res .= ' (' . $self->{relation} . ' ' . $self->{version} . ')';
+ }
+ if (defined $self->{arches}) {
+ $res .= ' [' . join(' ', @{$self->{arches}}) . ']';
+ }
+ if (defined $self->{restrictions}) {
+ for my $restrlist (@{$self->{restrictions}}) {
+ $res .= ' <' . join(' ', @{$restrlist}) . '>';
+ }
+ }
+ if (defined $fh) {
+ print { $fh } $res;
+ }
+ return $res;
+}
+
+=item $dep->save($filename)
+
+Save the dependency into the given $filename.
+
+=cut
+
+# _arch_is_superset(\@p, \@q)
+#
+# Returns true if the arch list @p is a superset of arch list @q.
+# The arguments can also be undef in case there's no explicit architecture
+# restriction.
+sub _arch_is_superset {
+ my ($p, $q) = @_;
+ my $p_arch_neg = defined $p and $p->[0] =~ /^!/;
+ my $q_arch_neg = defined $q and $q->[0] =~ /^!/;
+
+ # If "p" has no arches, it is a superset of q and we should fall through
+ # to the version check.
+ if (not defined $p) {
+ return 1;
+ }
+ # If q has no arches, it is a superset of p and there are no useful
+ # implications.
+ elsif (not defined $q) {
+ return 0;
+ }
+ # Both have arches. If neither are negated, we know nothing useful
+ # unless q is a subset of p.
+ elsif (not $p_arch_neg and not $q_arch_neg) {
+ my %p_arches = map { $_ => 1 } @{$p};
+ my $subset = 1;
+ for my $arch (@{$q}) {
+ $subset = 0 unless $p_arches{$arch};
+ }
+ return 0 unless $subset;
+ }
+ # If both are negated, we know nothing useful unless p is a subset of
+ # q (and therefore has fewer things excluded, and therefore is more
+ # general).
+ elsif ($p_arch_neg and $q_arch_neg) {
+ my %q_arches = map { $_ => 1 } @{$q};
+ my $subset = 1;
+ for my $arch (@{$p}) {
+ $subset = 0 unless $q_arches{$arch};
+ }
+ return 0 unless $subset;
+ }
+ # If q is negated and p isn't, we'd need to know the full list of
+ # arches to know if there's any relationship, so bail.
+ elsif (not $p_arch_neg and $q_arch_neg) {
+ return 0;
+ }
+ # If p is negated and q isn't, q is a subset of p if none of the
+ # negated arches in p are present in q.
+ elsif ($p_arch_neg and not $q_arch_neg) {
+ my %q_arches = map { $_ => 1 } @{$q};
+ my $subset = 1;
+ for my $arch (@{$p}) {
+ $subset = 0 if $q_arches{substr($arch, 1)};
+ }
+ return 0 unless $subset;
+ }
+ return 1;
+}
+
+# _arch_qualifier_implies($p, $q)
+#
+# Returns true if the arch qualifier $p and $q are compatible with the
+# implication $p -> $q, false otherwise. $p/$q can be undef/"any"/"native"
+# or an architecture string.
+#
+# Because we are handling dependencies in isolation, and the full context
+# of the implications are only known when doing dependency resolution at
+# run-time, we can only assert that they are implied if they are equal.
+#
+# For example dependencies with different arch-qualifiers cannot be simplified
+# as these depend on the state of Multi-Arch field in the package depended on.
+sub _arch_qualifier_implies {
+ my ($p, $q) = @_;
+
+ return $p eq $q if defined $p and defined $q;
+ return 1 if not defined $p and not defined $q;
+ return 0;
+}
+
+# _restrictions_imply($p, $q)
+#
+# Returns true if the restrictions $p and $q are compatible with the
+# implication $p -> $q, false otherwise.
+# NOTE: We don't try to be very clever here, so we may conservatively
+# return false when there is an implication.
+sub _restrictions_imply {
+ my ($p, $q) = @_;
+
+ if (not defined $p) {
+ return 1;
+ } elsif (not defined $q) {
+ return 0;
+ } else {
+ # Check whether set difference is empty.
+ my %restr;
+
+ for my $restrlist (@{$q}) {
+ my $reststr = join ' ', sort @{$restrlist};
+ $restr{$reststr} = 1;
+ }
+ for my $restrlist (@{$p}) {
+ my $reststr = join ' ', sort @{$restrlist};
+ delete $restr{$reststr};
+ }
+
+ return keys %restr == 0;
+ }
+}
+
+=item $dep->implies($other_dep)
+
+Returns 1 when $dep implies $other_dep. Returns 0 when $dep implies
+NOT($other_dep). Returns undef when there is no implication. $dep and
+$other_dep do not need to be of the same type.
+
+=cut
+
+sub implies {
+ my ($self, $o) = @_;
+
+ if ($o->isa('Dpkg::Deps::Simple')) {
+ # An implication is only possible on the same package
+ return if $self->{package} ne $o->{package};
+
+ # Our architecture set must be a superset of the architectures for
+ # o, otherwise we can't conclude anything.
+ return unless _arch_is_superset($self->{arches}, $o->{arches});
+
+ # The arch qualifier must not forbid an implication
+ return unless _arch_qualifier_implies($self->{archqual},
+ $o->{archqual});
+
+ # Our restrictions must imply the restrictions for o
+ return unless _restrictions_imply($self->{restrictions},
+ $o->{restrictions});
+
+ # If o has no version clause, then our dependency is stronger
+ return 1 if not defined $o->{relation};
+ # If o has a version clause, we must also have one, otherwise there
+ # can't be an implication
+ return if not defined $self->{relation};
+
+ return Dpkg::Deps::deps_eval_implication($self->{relation},
+ $self->{version}, $o->{relation}, $o->{version});
+ } elsif ($o->isa('Dpkg::Deps::AND')) {
+ # TRUE: Need to imply all individual elements
+ # FALSE: Need to NOT imply at least one individual element
+ my $res = 1;
+ foreach my $dep ($o->get_deps()) {
+ my $implication = $self->implies($dep);
+ unless (defined $implication and $implication == 1) {
+ $res = $implication;
+ last if defined $res;
+ }
+ }
+ return $res;
+ } elsif ($o->isa('Dpkg::Deps::OR')) {
+ # TRUE: Need to imply at least one individual element
+ # FALSE: Need to not apply all individual elements
+ # UNDEF: The rest
+ my $res = undef;
+ foreach my $dep ($o->get_deps()) {
+ my $implication = $self->implies($dep);
+ if (defined $implication) {
+ if (not defined $res) {
+ $res = $implication;
+ } else {
+ if ($implication) {
+ $res = 1;
+ } else {
+ $res = 0;
+ }
+ }
+ last if defined $res and $res == 1;
+ }
+ }
+ return $res;
+ } else {
+ croak 'Dpkg::Deps::Simple cannot evaluate implication with a ' .
+ ref($o);
+ }
+}
+
+=item $dep->get_deps()
+
+Returns a list of sub-dependencies, which for this object it means it
+returns itself.
+
+=cut
+
+sub get_deps {
+ my $self = shift;
+
+ return $self;
+}
+
+=item $dep->sort()
+
+This method is a no-op for this object.
+
+=cut
+
+sub sort {
+ # Nothing to sort
+}
+
+=item $dep->arch_is_concerned($arch)
+
+Returns true if the dependency applies to the indicated architecture.
+
+=cut
+
+sub arch_is_concerned {
+ my ($self, $host_arch) = @_;
+
+ return 0 if not defined $self->{package}; # Empty dep
+ return 1 if not defined $self->{arches}; # Dep without arch spec
+
+ return debarch_is_concerned($host_arch, @{$self->{arches}});
+}
+
+=item $dep->reduce_arch($arch)
+
+Simplifies the dependency to contain only information relevant to the given
+architecture. This object can be left empty after this operation. This trims
+off the architecture restriction list of these objects.
+
+=cut
+
+sub reduce_arch {
+ my ($self, $host_arch) = @_;
+
+ if (not $self->arch_is_concerned($host_arch)) {
+ $self->reset();
+ } else {
+ $self->{arches} = undef;
+ }
+}
+
+=item $dep->has_arch_restriction()
+
+Returns the package name if the dependency applies only to a subset of
+architectures.
+
+=cut
+
+sub has_arch_restriction {
+ my $self = shift;
+
+ if (defined $self->{arches}) {
+ return $self->{package};
+ } else {
+ return ();
+ }
+}
+
+=item $dep->profile_is_concerned()
+
+Returns true if the dependency applies to the indicated profile.
+
+=cut
+
+sub profile_is_concerned {
+ my ($self, $build_profiles) = @_;
+
+ return 0 if not defined $self->{package}; # Empty dep
+ return 1 if not defined $self->{restrictions}; # Dep without restrictions
+ return evaluate_restriction_formula($self->{restrictions}, $build_profiles);
+}
+
+=item $dep->reduce_profiles()
+
+Simplifies the dependency to contain only information relevant to the given
+profile. This object can be left empty after this operation. This trims off
+the profile restriction list of this object.
+
+=cut
+
+sub reduce_profiles {
+ my ($self, $build_profiles) = @_;
+
+ if (not $self->profile_is_concerned($build_profiles)) {
+ $self->reset();
+ } else {
+ $self->{restrictions} = undef;
+ }
+}
+
+=item $dep->get_evaluation($facts)
+
+Evaluates the dependency given a list of installed packages and a list of
+virtual packages provided. These lists are part of the Dpkg::Deps::KnownFacts
+object given as parameters.
+
+Returns 1 when it's true, 0 when it's false, undef when some information
+is lacking to conclude.
+
+=cut
+
+sub get_evaluation {
+ my ($self, $facts) = @_;
+
+ return if not defined $self->{package};
+ return $facts->evaluate_simple_dep($self);
+}
+
+=item $dep->simplify_deps($facts, @assumed_deps)
+
+Simplifies the dependency as much as possible given the list of facts (see
+object Dpkg::Deps::KnownFacts) and a list of other dependencies that are
+known to be true.
+
+=cut
+
+sub simplify_deps {
+ my ($self, $facts) = @_;
+
+ my $eval = $self->get_evaluation($facts);
+ $self->reset() if defined $eval and $eval == 1;
+}
+
+=item $dep->is_empty()
+
+Returns true if the dependency is empty and doesn't contain any useful
+information. This is true when the object has not yet been initialized.
+
+=cut
+
+sub is_empty {
+ my $self = shift;
+
+ return not defined $self->{package};
+}
+
+=item $dep->merge_union($other_dep)
+
+Returns true if $dep could be modified to represent the union of both
+dependencies. Otherwise returns false.
+
+=cut
+
+sub merge_union {
+ my ($self, $o) = @_;
+
+ return 0 if not $o->isa('Dpkg::Deps::Simple');
+ return 0 if $self->is_empty() or $o->is_empty();
+ return 0 if $self->{package} ne $o->{package};
+ return 0 if defined $self->{arches} or defined $o->{arches};
+
+ if (not defined $o->{relation} and defined $self->{relation}) {
+ # Union is the non-versioned dependency
+ $self->{relation} = undef;
+ $self->{version} = undef;
+ return 1;
+ }
+
+ my $implication = $self->implies($o);
+ my $rev_implication = $o->implies($self);
+ if (defined $implication) {
+ if ($implication) {
+ $self->{relation} = $o->{relation};
+ $self->{version} = $o->{version};
+ return 1;
+ } else {
+ return 0;
+ }
+ }
+ if (defined $rev_implication) {
+ if ($rev_implication) {
+ # Already merged...
+ return 1;
+ } else {
+ return 0;
+ }
+ }
+ return 0;
+}
+
+=back
+
+=head1 CHANGES
+
+=head2 Version 1.02 (dpkg 1.17.10)
+
+New methods: Add $dep->profile_is_concerned() and $dep->reduce_profiles().
+
+=head2 Version 1.01 (dpkg 1.16.1)
+
+New method: Add $dep->reset().
+
+New property: recognizes the arch qualifier "any" and stores it in the
+"archqual" property when present.
+
+=head2 Version 1.00 (dpkg 1.15.6)
+
+Mark the module as public.
+
+=cut
+
+1;
diff --git a/scripts/Dpkg/Deps/Union.pm b/scripts/Dpkg/Deps/Union.pm
new file mode 100644
index 0000000..62cf5c3
--- /dev/null
+++ b/scripts/Dpkg/Deps/Union.pm
@@ -0,0 +1,119 @@
+# Copyright © 1998 Richard Braakman
+# Copyright © 1999 Darren Benham
+# Copyright © 2000 Sean 'Shaleh' Perry
+# Copyright © 2004 Frank Lichtenheld
+# Copyright © 2006 Russ Allbery
+# Copyright © 2007-2009 Raphaël Hertzog <hertzog@debian.org>
+# Copyright © 2008-2009, 2012-2014 Guillem Jover <guillem@debian.org>
+#
+# This program is free software; you may redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program. If not, see <https://www.gnu.org/licenses/>.
+
+package Dpkg::Deps::Union;
+
+=encoding utf8
+
+=head1 NAME
+
+Dpkg::Deps::Union - list of unrelated dependencies
+
+=head1 DESCRIPTION
+
+This object represents a list of relationships. It inherits from
+Dpkg::Deps::Multiple.
+
+=cut
+
+use strict;
+use warnings;
+
+our $VERSION = '1.00';
+
+use parent qw(Dpkg::Deps::Multiple);
+
+=head1 METHODS
+
+=over 4
+
+=item $dep->output([$fh])
+
+The output method uses ", " to join the list of relationships.
+
+=cut
+
+sub output {
+ my ($self, $fh) = @_;
+
+ my $res = join(', ', map {
+ $_->output()
+ } grep {
+ not $_->is_empty()
+ } $self->get_deps());
+
+ if (defined $fh) {
+ print { $fh } $res;
+ }
+ return $res;
+}
+
+=item $dep->implies($other_dep)
+
+=item $dep->get_evaluation($other_dep)
+
+These methods are not meaningful for this object and always return undef.
+
+=cut
+
+sub implies {
+ # Implication test is not useful on Union.
+ return;
+}
+
+sub get_evaluation {
+ # Evaluation is not useful on Union.
+ return;
+}
+
+=item $dep->simplify_deps($facts)
+
+The simplification is done to generate an union of all the relationships.
+It uses $simple_dep->merge_union($other_dep) to get its job done.
+
+=cut
+
+sub simplify_deps {
+ my ($self, $facts) = @_;
+ my @new;
+
+WHILELOOP:
+ while (@{$self->{list}}) {
+ my $odep = shift @{$self->{list}};
+ foreach my $dep (@new) {
+ next WHILELOOP if $dep->merge_union($odep);
+ }
+ push @new, $odep;
+ }
+ $self->{list} = [ @new ];
+}
+
+=back
+
+=head1 CHANGES
+
+=head2 Version 1.00 (dpkg 1.15.6)
+
+Mark the module as public.
+
+=cut
+
+1;