File Coverage

File:Dpkg/Deps.pm
Coverage:78.7%

linestmtbrancondsubpodtimecode
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 - 44
=head1 NAME

Dpkg::Deps - parse and manipulate dependencies of Debian packages

=head1 DESCRIPTION

The Dpkg::Deps module provides classes 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
45
46
1
1
1
1
2
1
11
use strict;
47
1
1
1
1
2
1
23
use warnings;
48
1
1
1
1
1
1
49
use feature qw(current_sub);
49
50our $VERSION = '1.07';
51our @EXPORT = qw(
52    deps_concat
53    deps_parse
54    deps_eval_implication
55    deps_iterate
56    deps_compare
57);
58
59
1
1
1
1
2
1
28
use Carp;
60
1
1
1
1
2
0
11
use Exporter qw(import);
61
62
1
1
1
1
2
0
31
use Dpkg::Version;
63
1
1
1
1
2
1
19
use Dpkg::Arch qw(get_host_arch get_build_arch debarch_to_debtuple);
64
1
1
1
1
309
1
23
use Dpkg::BuildProfiles qw(get_build_profiles);
65
1
1
1
1
2
1
25
use Dpkg::ErrorHandling;
66
1
1
1
1
1
1
17
use Dpkg::Gettext;
67
1
1
1
1
335
0
17
use Dpkg::Deps::Simple;
68
1
1
1
1
306
0
17
use Dpkg::Deps::Union;
69
1
1
1
1
302
0
17
use Dpkg::Deps::AND;
70
1
1
1
1
304
1
24
use Dpkg::Deps::OR;
71
1
1
1
1
312
1
736
use Dpkg::Deps::KnownFacts;
72
73 - 85
=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
86
87sub deps_eval_implication {
88
25
25
1
15
    my ($rel_p, $v_p, $rel_q, $v_q) = @_;
89
90    # If versions are not valid, we can't decide of any implication
91
25
50
33
37
    return unless defined($v_p) and $v_p->is_valid();
92
25
50
33
33
    return unless defined($v_q) and $v_q->is_valid();
93
94    # q wants an exact version, so p must provide that exact version.  p
95    # disproves q if q's version is outside the range enforced by p.
96
25
100
15
    if ($rel_q eq REL_EQ) {
97
3
100
50
50
0
0
3
        if ($rel_p eq REL_LT) {
98
2
100
2
            return ($v_p <= $v_q) ? 0 : undef;
99        } elsif ($rel_p eq REL_LE) {
100
0
0
0
            return ($v_p < $v_q) ? 0 : undef;
101        } elsif ($rel_p eq REL_GT) {
102
1
50
1
            return ($v_p >= $v_q) ? 0 : undef;
103        } elsif ($rel_p eq REL_GE) {
104
0
0
0
            return ($v_p > $v_q) ? 0 : undef;
105        } elsif ($rel_p eq REL_EQ) {
106
0
0
            return ($v_p == $v_q);
107        }
108    }
109
110    # A greater than clause may disprove a less than clause. An equal
111    # cause might as well.  Otherwise, if
112    # p's clause is <<, <=, or =, the version must be <= q's to imply q.
113
22
100
17
    if ($rel_q eq REL_LE) {
114
3
50
100
50
9
        if ($rel_p eq REL_GT) {
115
0
0
0
            return ($v_p >= $v_q) ? 0 : undef;
116        } elsif ($rel_p eq REL_GE) {
117
1
50
1
            return ($v_p > $v_q) ? 0 : undef;
118        } elsif ($rel_p eq REL_EQ) {
119
0
0
0
            return ($v_p <= $v_q) ? 1 : 0;
120        } else { # <<, <=
121
2
100
2
            return ($v_p <= $v_q) ? 1 : undef;
122        }
123    }
124
125    # Similar, but << is stronger than <= so p's version must be << q's
126    # version if the p relation is <= or =.
127
19
100
13
    if ($rel_q eq REL_LT) {
128
4
100
50
50
100
11
        if ($rel_p eq REL_GT or $rel_p eq REL_GE) {
129
2
50
2
            return ($v_p >= $v_p) ? 0 : undef;
130        } elsif ($rel_p eq REL_LT) {
131
0
0
0
            return ($v_p <= $v_q) ? 1 : undef;
132        } elsif ($rel_p eq REL_EQ) {
133
2
100
2
            return ($v_p < $v_q) ? 1 : 0;
134        } else { # <<, <=
135
0
0
0
            return ($v_p < $v_q) ? 1 : undef;
136        }
137    }
138
139    # Same logic as above, only inverted.
140
15
100
9
    if ($rel_q eq REL_GE) {
141
10
50
100
50
11
        if ($rel_p eq REL_LT) {
142
0
0
0
            return ($v_p <= $v_q) ? 0 : undef;
143        } elsif ($rel_p eq REL_LE) {
144
2
50
2
            return ($v_p < $v_q) ? 0 : undef;
145        } elsif ($rel_p eq REL_EQ) {
146
0
0
0
            return ($v_p >= $v_q) ? 1 : 0;
147        } else { # >>, >=
148
8
100
8
            return ($v_p >= $v_q) ? 1 : undef;
149        }
150    }
151
5
50
4
    if ($rel_q eq REL_GT) {
152
5
100
50
100
67
13
        if ($rel_p eq REL_LT or $rel_p eq REL_LE) {
153
1
50
1
            return ($v_p <= $v_q) ? 0 : undef;
154        } elsif ($rel_p eq REL_GT) {
155
0
0
0
            return ($v_p >= $v_q) ? 1 : undef;
156        } elsif ($rel_p eq REL_EQ) {
157
1
50
1
            return ($v_p > $v_q) ? 1 : 0;
158        } else {
159
3
50
4
            return ($v_p > $v_q) ? 1 : undef;
160        }
161    }
162
163
0
0
    return;
164}
165
166 - 171
=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
172
173sub deps_concat {
174
5
5
1
5
    my (@dep_list) = @_;
175
176
5
7
5
10
    return join ', ', grep { defined } @dep_list;
177}
178
179 - 258
=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 virtual (defaults to 0)

If set to 1, allow only virtual package version relations, that is none,
or "=".
This should be set whenever working with Provides fields.

=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
259
260sub deps_parse {
261
67
67
1
59
    my ($dep_line, %options) = @_;
262
263    # Validate arguments.
264    croak "invalid host_arch $options{host_arch}"
265
67
100
100
84
        if defined $options{host_arch} and not defined debarch_to_debtuple($options{host_arch});
266    croak "invalid build_arch $options{build_arch}"
267
63
100
67
55
        if defined $options{build_arch} and not defined debarch_to_debtuple($options{build_arch});
268
269
59
50
133
    $options{use_arch} //= 1;
270
59
100
83
    $options{reduce_arch} //= 0;
271
59
50
86
    $options{use_profiles} //= 1;
272
59
100
95
    $options{reduce_profiles} //= 0;
273
59
100
79
    $options{reduce_restrictions} //= 0;
274
59
100
81
    $options{union} //= 0;
275
59
50
81
    $options{virtual} //= 0;
276
59
100
86
    $options{build_dep} //= 0;
277
59
100
92
    $options{tests_dep} //= 0;
278
279
59
100
43
    if ($options{reduce_restrictions}) {
280
1
0
        $options{reduce_arch} = 1;
281
1
1
        $options{reduce_profiles} = 1;
282    }
283
59
100
45
    if ($options{reduce_arch}) {
284
4
67
6
        $options{host_arch} //= get_host_arch();
285
4
33
5
        $options{build_arch} //= get_build_arch();
286    }
287
59
100
35
    if ($options{reduce_profiles}) {
288
5
50
5
        $options{build_profiles} //= [ get_build_profiles() ];
289    }
290
291    # Options for Dpkg::Deps::Simple.
292    my %deps_options = (
293        host_arch => $options{host_arch},
294        build_arch => $options{build_arch},
295        build_dep => $options{build_dep},
296        tests_dep => $options{tests_dep},
297
59
84
    );
298
299    # Merge in a single-line
300
59
122
    $dep_line =~ s/\s*[\r\n]\s*/ /g;
301    # Strip trailing/leading spaces
302
59
44
    $dep_line =~ s/^\s+//;
303
59
91
    $dep_line =~ s/\s+$//;
304
305
59
30
    my @dep_list;
306
59
138
    foreach my $dep_and (split(/\s*,\s*/m, $dep_line)) {
307
219
116
        my @or_list = ();
308
219
174
        foreach my $dep_or (split(/\s*\|\s*/m, $dep_and)) {
309
254
255
            my $dep_simple = Dpkg::Deps::Simple->new($dep_or, %deps_options);
310
254
100
205
            if (not defined $dep_simple->{package}) {
311
4
6
                warning(g_("can't parse dependency %s"), $dep_or);
312
4
12
                return;
313            }
314
250
0
25
190
            if ($options{virtual} && defined $dep_simple->{relation} &&
315                $dep_simple->{relation} ne '=') {
316
0
0
                warning(g_('virtual dependency contains invalid relation: %s'),
317                        $dep_simple->output);
318
0
0
                return;
319            }
320
250
50
174
            $dep_simple->{arches} = undef if not $options{use_arch};
321
250
100
161
            if ($options{reduce_arch}) {
322
15
17
                $dep_simple->reduce_arch($options{host_arch});
323
15
100
12
                next if not $dep_simple->arch_is_concerned($options{host_arch});
324            }
325
244
50
148
            $dep_simple->{restrictions} = undef if not $options{use_profiles};
326
244
100
157
            if ($options{reduce_profiles}) {
327
62
60
                $dep_simple->reduce_profiles($options{build_profiles});
328
62
100
46
                next if not $dep_simple->profile_is_concerned($options{build_profiles});
329            }
330
215
139
            push @or_list, $dep_simple;
331        }
332
215
100
150
        next if not @or_list;
333
181
100
116
        if (scalar @or_list == 1) {
334
159
111
            push @dep_list, $or_list[0];
335        } else {
336
22
23
            my $dep_or = Dpkg::Deps::OR->new();
337
22
22
            $dep_or->add($_) foreach (@or_list);
338
22
14
            push @dep_list, $dep_or;
339        }
340    }
341
55
36
    my $dep_and;
342
55
100
35
    if ($options{union}) {
343
3
7
        $dep_and = Dpkg::Deps::Union->new();
344    } else {
345
52
43
        $dep_and = Dpkg::Deps::AND->new();
346    }
347
55
33
    foreach my $dep (@dep_list) {
348
179
50
67
130
        if ($options{union} and not $dep->isa('Dpkg::Deps::Simple')) {
349
0
0
            warning(g_('an union dependency can only contain simple dependencies'));
350
0
0
            return;
351        }
352
179
116
        $dep_and->add($dep);
353    }
354
55
115
    return $dep_and;
355}
356
357 - 367
=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
368
369sub deps_iterate {
370
65
65
1
30
    my ($deps, $callback_func) = @_;
371
372    my $visitor_func = sub {
373
74
74
36
        foreach my $dep (@_) {
374
85
50
56
            return unless defined $dep;
375
376
85
100
74
            if ($dep->isa('Dpkg::Deps::Simple')) {
377
76
50
42
                return unless $callback_func->($dep);
378            } else {
379
9
50
8
                return unless __SUB__->($dep->get_deps());
380            }
381        }
382
74
80
        return 1;
383
65
64
    };
384
385
65
43
    return $visitor_func->($deps);
386}
387
388 - 395
=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
396
397my %relation_ordering = (
398        undef => 0,
399        REL_GE() => 1,
400        REL_GT() => 2,
401        REL_EQ() => 3,
402        REL_LT() => 4,
403        REL_LE() => 5,
404);
405
406sub deps_compare {
407
32
32
1
21
    my ($aref, $bref) = @_;
408
409
32
13
    my (@as, @bs);
410
32
34
34
52
30
    deps_iterate($aref, sub { push @as, @_ });
411
32
37
37
48
31
    deps_iterate($bref, sub { push @bs, @_ });
412
413
32
22
    while (1) {
414
35
21
        my ($a, $b) = (shift @as, shift @bs);
415
35
100
39
        my $aundef = not defined $a or $a->is_empty();
416
35
50
33
        my $bundef = not defined $b or $b->is_empty();
417
418
35
50
67
26
        return  0 if $aundef and $bundef;
419
35
100
24
        return -1 if $aundef;
420
33
50
19
        return  1 if $bundef;
421
422
33
100
26
        my $ar = $a->{relation} // 'undef';
423
33
100
28
        my $br = $b->{relation} // 'undef';
424
33
100
41
        my $av = $a->{version} // '';
425
33
100
31
        my $bv = $b->{version} // '';
426
427        my $res = (($a->{package} cmp $b->{package}) ||
428
33
67
39
                   ($relation_ordering{$ar} <=> $relation_ordering{$br}) ||
429                   ($av cmp $bv));
430
33
100
40
        return $res if $res != 0;
431    }
432}
433
434 - 488
=head1 CLASSES - 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 class
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 class 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.07 (dpkg 1.20.0)

New option: Add virtual option to Dpkg::Deps::deps_parse().

=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
489
4901;