File Coverage

File:Dpkg/Deps.pm
Coverage:79.1%

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
22=encoding utf8
23
24 - 36
=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.

=cut
37
38package Dpkg::Deps 1.07;
39
40
12
12
12
12
55
15
309
use strict;
41
12
12
12
12
24
9
459
use warnings;
42
12
12
12
12
40
10
995
use feature qw(current_sub);
43
44our @EXPORT = qw(
45    deps_concat
46    deps_parse
47    deps_eval_implication
48    deps_iterate
49    deps_compare
50);
51
52
12
12
12
12
42
10
534
use Carp;
53
12
12
12
12
33
9
205
use Exporter qw(import);
54
55
12
12
12
12
27
10
568
use Dpkg::Version;
56
12
12
12
12
730
14
544
use Dpkg::Arch qw(get_host_arch get_build_arch debarch_to_debtuple);
57
12
12
12
12
7079
20
559
use Dpkg::BuildProfiles qw(get_build_profiles);
58
12
12
12
12
40
11
503
use Dpkg::ErrorHandling;
59
12
12
12
12
72
15
503
use Dpkg::Gettext;
60
12
12
12
12
7487
19
376
use Dpkg::Deps::Simple;
61
12
12
12
12
6844
21
365
use Dpkg::Deps::Union;
62
12
12
12
12
7932
15
332
use Dpkg::Deps::AND;
63
12
12
12
12
7554
17
423
use Dpkg::Deps::OR;
64
12
12
12
12
7291
21
13226
use Dpkg::Deps::KnownFacts;
65
66 - 84
=head1 FUNCTIONS

All the deps_* functions are exported by default.

=over 4

=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 L<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 L<Dpkg::Version> objects.

=cut
85
86sub deps_eval_implication {
87
75
75
1
88
    my ($rel_p, $v_p, $rel_q, $v_q) = @_;
88
89    # If versions are not valid, we can't decide of any implication
90
75
50
33
185
    return unless defined($v_p) and $v_p->is_valid();
91
75
50
33
162
    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
75
100
95
    if ($rel_q eq REL_EQ) {
96
9
100
50
50
0
0
17
        if ($rel_p eq REL_LT) {
97
6
100
11
            return ($v_p <= $v_q) ? 0 : undef;
98        } elsif ($rel_p eq REL_LE) {
99
0
0
0
            return ($v_p < $v_q) ? 0 : undef;
100        } elsif ($rel_p eq REL_GT) {
101
3
50
5
            return ($v_p >= $v_q) ? 0 : undef;
102        } elsif ($rel_p eq REL_GE) {
103
0
0
0
            return ($v_p > $v_q) ? 0 : undef;
104        } elsif ($rel_p eq REL_EQ) {
105
0
0
            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
66
100
200
    if ($rel_q eq REL_LE) {
113
9
50
100
50
17
        if ($rel_p eq REL_GT) {
114
0
0
0
            return ($v_p >= $v_q) ? 0 : undef;
115        } elsif ($rel_p eq REL_GE) {
116
3
50
4
            return ($v_p > $v_q) ? 0 : undef;
117        } elsif ($rel_p eq REL_EQ) {
118
0
0
0
            return ($v_p <= $v_q) ? 1 : 0;
119        } else { # <<, <=
120
6
100
7
            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
57
100
71
    if ($rel_q eq REL_LT) {
127
12
100
50
50
100
43
        if ($rel_p eq REL_GT or $rel_p eq REL_GE) {
128
6
50
12
            return ($v_p >= $v_p) ? 0 : undef;
129        } elsif ($rel_p eq REL_LT) {
130
0
0
0
            return ($v_p <= $v_q) ? 1 : undef;
131        } elsif ($rel_p eq REL_EQ) {
132
6
100
8
            return ($v_p < $v_q) ? 1 : 0;
133        } else { # <<, <=
134
0
0
0
            return ($v_p < $v_q) ? 1 : undef;
135        }
136    }
137
138    # Same logic as above, only inverted.
139
45
100
86
    if ($rel_q eq REL_GE) {
140
30
50
100
50
58
        if ($rel_p eq REL_LT) {
141
0
0
0
            return ($v_p <= $v_q) ? 0 : undef;
142        } elsif ($rel_p eq REL_LE) {
143
6
50
18
            return ($v_p < $v_q) ? 0 : undef;
144        } elsif ($rel_p eq REL_EQ) {
145
0
0
0
            return ($v_p >= $v_q) ? 1 : 0;
146        } else { # >>, >=
147
24
100
32
            return ($v_p >= $v_q) ? 1 : undef;
148        }
149    }
150
15
50
21
    if ($rel_q eq REL_GT) {
151
15
100
50
100
67
59
        if ($rel_p eq REL_LT or $rel_p eq REL_LE) {
152
3
50
25
            return ($v_p <= $v_q) ? 0 : undef;
153        } elsif ($rel_p eq REL_GT) {
154
0
0
0
            return ($v_p >= $v_q) ? 1 : undef;
155        } elsif ($rel_p eq REL_EQ) {
156
3
50
5
            return ($v_p > $v_q) ? 1 : 0;
157        } else {
158
9
50
28
            return ($v_p > $v_q) ? 1 : undef;
159        }
160    }
161
162
0
0
    return;
163}
164
165 - 170
=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
171
172sub deps_concat {
173
36
36
1
56
    my (@dep_list) = @_;
174
175
36
84
50
127
    return join ', ', grep { defined } @dep_list;
176}
177
178 - 260
=item $dep = deps_parse($line, %options)

This function parses the dependency line and returns an object, either a
L<Dpkg::Deps::AND> or a L<Dpkg::Deps::Union>. Various options can alter the
behavior 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 L<Dpkg::Deps::Union> instead of a L<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>.

This option implicitly (and forcibly) enables C<build_dep> because test
dependencies are based on build dependencies (since dpkg 1.22.1).

=back

=cut
261
262sub deps_parse {
263
228
228
1
428
    my ($dep_line, %options) = @_;
264
265    # Validate arguments.
266    croak "invalid host_arch $options{host_arch}"
267
228
100
100
516
        if defined $options{host_arch} and not defined debarch_to_debtuple($options{host_arch});
268    croak "invalid build_arch $options{build_arch}"
269
216
100
67
410
        if defined $options{build_arch} and not defined debarch_to_debtuple($options{build_arch});
270
271
204
50
804
    $options{use_arch} //= 1;
272
204
100
507
    $options{reduce_arch} //= 0;
273
204
50
531
    $options{use_profiles} //= 1;
274
204
100
521
    $options{reduce_profiles} //= 0;
275
204
100
457
    $options{reduce_restrictions} //= 0;
276
204
100
502
    $options{union} //= 0;
277
204
50
470
    $options{virtual} //= 0;
278
204
100
453
    $options{build_dep} //= 0;
279
204
100
458
    $options{tests_dep} //= 0;
280
281
204
100
239
    if ($options{reduce_restrictions}) {
282
24
22
        $options{reduce_arch} = 1;
283
24
22
        $options{reduce_profiles} = 1;
284    }
285
204
100
261
    if ($options{reduce_arch}) {
286
33
67
108
        $options{host_arch} //= get_host_arch();
287
33
33
112
        $options{build_arch} //= get_build_arch();
288    }
289
204
100
246
    if ($options{reduce_profiles}) {
290
36
100
120
        $options{build_profiles} //= [ get_build_profiles() ];
291    }
292
204
100
256
    if ($options{tests_dep}) {
293
6
5
        $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
204
491
    );
303
304    # Merge in a single-line
305
204
822
    $dep_line =~ s/\s*[\r\n]\s*/ /g;
306    # Strip trailing/leading spaces
307
204
249
    $dep_line =~ s/^\s+//;
308
204
511
    $dep_line =~ s/\s+$//;
309
310
204
170
    my @dep_list;
311
204
820
    foreach my $dep_and (split(/\s*,\s*/m, $dep_line)) {
312
705
495
        my @or_list = ();
313
705
814
        foreach my $dep_or (split(/\s*\|\s*/m, $dep_and)) {
314
804
1337
            my $dep_simple = Dpkg::Deps::Simple->new($dep_or, %deps_options);
315
804
100
932
            if (not defined $dep_simple->{package}) {
316
15
37
                warning(g_("can't parse dependency %s"), $dep_or);
317
15
75
                return;
318            }
319
789
0
25
791
            if ($options{virtual} && defined $dep_simple->{relation} &&
320                $dep_simple->{relation} ne '=') {
321
0
0
                warning(g_('virtual dependency contains invalid relation: %s'),
322                        $dep_simple->output);
323
0
0
                return;
324            }
325
789
50
725
            $dep_simple->{arches} = undef if not $options{use_arch};
326
789
100
694
            if ($options{reduce_arch}) {
327
69
122
                $dep_simple->reduce_arch($options{host_arch});
328
69
100
75
                next if not $dep_simple->arch_is_concerned($options{host_arch});
329            }
330
771
50
612
            $dep_simple->{restrictions} = undef if not $options{use_profiles};
331
771
100
691
            if ($options{reduce_profiles}) {
332
210
246
                $dep_simple->reduce_profiles($options{build_profiles});
333
210
100
197
                next if not $dep_simple->profile_is_concerned($options{build_profiles});
334            }
335
684
669
            push @or_list, $dep_simple;
336        }
337
690
100
671
        next if not @or_list;
338
582
100
508
        if (scalar @or_list == 1) {
339
516
478
            push @dep_list, $or_list[0];
340        } else {
341
66
169
            my $dep_or = Dpkg::Deps::OR->new();
342
66
136
            $dep_or->add($_) foreach (@or_list);
343
66
83
            push @dep_list, $dep_or;
344        }
345    }
346
189
179
    my $dep_and;
347
189
100
251
    if ($options{union}) {
348
9
42
        $dep_and = Dpkg::Deps::Union->new();
349    } else {
350
180
358
        $dep_and = Dpkg::Deps::AND->new();
351    }
352
189
194
    foreach my $dep (@dep_list) {
353
573
50
67
566
        if ($options{union} and not $dep->isa('Dpkg::Deps::Simple')) {
354
0
0
            warning(g_('an union dependency can only contain simple dependencies'));
355
0
0
            return;
356        }
357
573
530
        $dep_and->add($dep);
358    }
359
189
680
    return $dep_and;
360}
361
362 - 372
=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
373
374sub deps_iterate {
375
216
216
1
163
    my ($deps, $callback_func) = @_;
376
377    my $visitor_func = sub {
378
264
264
202
        foreach my $dep (@_) {
379
297
50
240
            return unless defined $dep;
380
381
297
100
472
            if ($dep->isa('Dpkg::Deps::Simple')) {
382
249
50
207
                return unless $callback_func->($dep);
383            } else {
384
48
50
93
                return unless __SUB__->($dep->get_deps());
385            }
386        }
387
246
412
        return 1;
388
216
303
    };
389
390
216
189
    return $visitor_func->($deps);
391}
392
393 - 400
=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
401
402my %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
411sub deps_compare {
412
96
96
1
73
    my ($aref, $bref) = @_;
413
414
96
63
    my (@as, @bs);
415
96
102
102
232
119
    deps_iterate($aref, sub { push @as, @_ });
416
96
111
111
185
118
    deps_iterate($bref, sub { push @bs, @_ });
417
418
96
87
    while (1) {
419
105
92
        my ($a, $b) = (shift @as, shift @bs);
420
105
100
177
        my $aundef = not defined $a or $a->is_empty();
421
105
50
138
        my $bundef = not defined $b or $b->is_empty();
422
423
105
50
67
111
        return  0 if $aundef and $bundef;
424
105
100
94
        return -1 if $aundef;
425
99
50
82
        return  1 if $bundef;
426
427
99
100
130
        my $ar = $a->{relation} // 'undef';
428
99
100
133
        my $br = $b->{relation} // 'undef';
429
99
100
167
        my $av = $a->{version} // '';
430
99
100
149
        my $bv = $b->{version} // '';
431
432        my $res = (($a->{package} cmp $b->{package}) ||
433
99
67
257
                   ($relation_ordering{$ar} <=> $relation_ordering{$br}) ||
434                   ($av cmp $bv));
435
99
100
188
        return $res if $res != 0;
436    }
437}
438
439 - 493
=head1 CLASSES - Dpkg::Deps::*

There are several kind of dependencies. A L<Dpkg::Deps::Simple> dependency
represents a single dependency statement (it relates to one package only).
L<Dpkg::Deps::Multiple> dependencies are built on top of this class
and combine several dependencies in different manners. L<Dpkg::Deps::AND>
represents the logical "AND" between dependencies while L<Dpkg::Deps::OR>
represents the logical "OR". L<Dpkg::Deps::Multiple> objects can contain
L<Dpkg::Deps::Simple> object as well as other L<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.

L<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 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 deps_parse().

=head2 Version 1.05 (dpkg 1.17.14)

New function: deps_iterate().

=head2 Version 1.04 (dpkg 1.17.10)

New options: Add use_profiles, build_profiles, reduce_profiles and
reduce_restrictions to deps_parse().

=head2 Version 1.03 (dpkg 1.17.0)

New option: Add build_arch option to deps_parse().

=head2 Version 1.02 (dpkg 1.17.0)

New function: 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
494
4951;