Debian Codegraph @

tools/sort_deps

raw
1 #!/usr/bin/perl -w
2 #
3 # Copyright 1999 RaphaĆ«l Hertzog <[email protected]>
4 # Copyright 2006-2016 Steve McIntyre <[email protected]>
5 # See the README file for the license
6 #
7 # This script takes 1 argument on input :
8 # - a filename listing all the packages to include
9 #
10 # and it sorts those packages such that dependencies are met in order
11 #
12 # Used to be called list2cds, renamed as it now just sorts
13 # dependencies. Later code in make_disc_trees.pl actually splits on a
14 # per-disc basis now.
15
16 use strict;
17 use Data::Dumper;
18 use Dpkg::Version;
19
20 my $listfile = shift;
21
22 my $nonfree = read_env('NONFREE', 0);
23 my $extranonfree = read_env('EXTRANONFREE', 0);
24 my $force_firmware = read_env('FORCE_FIRMWARE', 0);
25 my @nonfree_components = split /\ /, read_env('NONFREE_COMPONENTS', 'non-free');
26 my $local = read_env('LOCAL', 0);
27 my $complete = read_env('COMPLETE', 0);
28 my $add_rec = ! read_env('NORECOMMENDS', 1);
29 my $add_sug = ! read_env('NOSUGGESTS', 1);
30 my $verbose = read_env('VERBOSE', 0);
31 my $max_pkg_size = read_env('MAX_PKG_SIZE', 9999999999999);
32 my $codename = $ENV{'CODENAME'};
33 my $backports_list = read_env('BACKPORTS', "");
34 my $backports = 1;
35 if ($backports_list =~ /^$/) {
36 $backports = 0;
37 }
38
39 my $apt = "$ENV{'BASEDIR'}/tools/apt-selection";
40 my $adir = "$ENV{'APTTMP'}/$ENV{'CODENAME'}-$ENV{'ARCH'}";
41 my $arch = "$ENV{'ARCH'}";
42 my $dir = "$ENV{'TDIR'}/$ENV{'CODENAME'}";
43
44 my $force_unstable_tasks = read_env('FORCE_SID_TASKSEL', 0);
45 my $tasks_packages = read_env('TASKS_PACKAGES',
46 "$ENV{'MIRROR'}/dists/sid/main/binary-$ENV{'ARCH'}/Packages.gz");
47 my @output = ();
48
49 $| = 1; # Autoflush for debugging
50
51 open(LOG, ">$dir/sort_deps.$arch.log")
52 || die "Can't write in $dir/sort_deps.$arch.log !\n";
53
54 sub read_env {
55 my $env_var = shift;
56 my $default = shift;
57
58 if (exists($ENV{$env_var})) {
59 return $ENV{$env_var};
60 }
61 # else
62 return $default;
63 }
64
65 sub msg {
66 my $level = shift;
67 if ($verbose >= $level) {
68 print @_;
69 }
70 print LOG @_;
71 }
72
73 my %included;
74 my %excluded;
75 my %excluded_firmware;
76 my %packages;
77 my %backport_packages;
78
79 msg(0, "Running sort_deps to sort packages for $arch:\n");
80 msg(1, "======================================================================
81 Here are the settings you've chosen for making the list:
82 Architecture: $arch
83 List of prefered packages: $listfile
84 Output file: $dir/packages.$arch
85 ");
86 msg(1, "Complete selected packages with all the rest: ");
87 msg(1, yesno($complete)."\n");
88 msg(1, "Include non-free packages: ");
89 msg(1, yesno($nonfree)."\n");
90 msg(1, "Non-free components:\n");
91 foreach my $cmp (@nonfree_components) {
92 msg(1, " - $cmp\n");
93 }
94 msg(1, "Force inclusion of firmware packages: ");
95 msg(1, yesno($force_firmware)."\n");
96 msg(1, "Include Recommends: ");
97 msg(1, yesno($add_rec)."\n");
98 msg(1, "Include Suggests: ");
99 msg(1, yesno($add_sug)."\n");
100 msg(1, "Maximum allowed package size: $max_pkg_size bytes\n");
101 msg(1, "======================================================================
102 ");
103
104 # Look for firmware packages that we've been told to exclude
105 if ($force_firmware) {
106 msg(1, "Reading tasks/exclude-firmware...\n");
107 my $cpp_command = "cpp -undef -P -Wall -nostdinc -I$dir/tasks -DARCH$arch";
108 my $excludelist = "$dir/tasks/exclude-firmware";
109 open (EXLIST, "$cpp_command $excludelist |") or
110 die "Can't parse exclude list: $!\n";
111 while (defined (my $exc = <EXLIST>)) {
112 chomp $exc;
113 $excluded_firmware{$exc} = 1;
114 msg(1, " - Ignore $exc\n");
115 }
116 close EXLIST;
117 }
118
119 # Get the information on all packages
120 my $oldrs = $/;
121 $/ = '';
122 msg(1, "Parsing packages...\n");
123 open(AVAIL, "$apt cache dumpavail |") || die "Can't fork : $!\n";
124 my ($p, $re);
125 my $num_pkgs = 0;
126 while (defined($_=<AVAIL>)) {
127 next if not m/^Package: (\S+)\s*$/m;
128 if (!$force_unstable_tasks || $1 !~ /^task-/) {
129 parse_package(0, $_);
130 $num_pkgs++;
131 }
132 }
133 msg(1, "Got $num_pkgs packages\n");
134 close AVAIL or die "apt-cache failed : $@ ($!)\n";
135 if ($backports) {
136 $num_pkgs = 0;
137 msg(1, "Parsing packages from backports...\n");
138 open(AVAIL, "USE_BP=1 $apt cache dumpavail |") || die "Can't fork : $!\n";
139 my ($p, $re);
140 while (defined($_=<AVAIL>)) {
141 next if not m/^Package: (\S+)\s*$/m;
142 if (!$force_unstable_tasks || $1 !~ /^task-/) {
143 parse_package(1, $_);
144 $num_pkgs++;
145 }
146 }
147 msg(1, "Got $num_pkgs packages\n");
148 close AVAIL or die "apt-cache (backports) failed : $@ ($!)\n";
149 }
150
151 # Read in the extra (new/unstable) tasks packages
152 if ($force_unstable_tasks) {
153 my $num = 0;
154 if ($tasks_packages =~ /\.gz$/) {
155 open(AVAIL, "zcat $tasks_packages |") || die "Can't zcat $tasks_packages : $!\n";
156 } else {
157 open(AVAIL, "< $tasks_packages") || die "Can't open $tasks_packages for reading: $!\n";
158 }
159 while (defined($_=<AVAIL>)) {
160 next if not m/^Package: (\S+)\s*$/m;
161 if ($1 =~ /^task-/) {
162 parse_package(0, $_);
163 $num++;
164 }
165 }
166 close AVAIL or die "reading unstable tasks failed : $@ ($!)\n";
167 msg(0, " Read $num tasks packages from $tasks_packages\n");
168 }
169
170 $/ = $oldrs;
171
172 # Get the list of excluded packages
173 %excluded = %included;
174 my $count_excl = 0;
175
176 # Now exclude packages because of the non-free rules
177 if (not $nonfree) {
178 foreach my $cmp (@nonfree_components) {
179 msg(1, "Checking for $cmp packages to exclude\n");
180 foreach (grep { $packages{$_}{"Section"} =~ /$cmp\//}
181 (keys %packages)) {
182 if ($force_firmware and $packages{$_}{"IsFirmware"}) {
183 if ($excluded_firmware{$_}) {
184 msg(1, " - force_firmware: dropping $cmp package $_ due to listing in tasks/exclude_firmware\n");
185 $excluded{$_} = 'nonfree-exclude-firmware';
186 $count_excl++;
187 } else {
188 msg(1, " - force_firmware: keeping $cmp package $_\n");
189 }
190 } else {
191 msg(1, " - excluding $cmp package $_\n");
192 $excluded{$_} = 'nonfree';
193 $count_excl++;
194 }
195 }
196 }
197 }
198
199 msg(1, "Statistics:
200 Number of packages: @{ [scalar(keys %packages)] }
201 Number of excluded: $count_excl of @{ [scalar(keys %excluded)] }
202 ======================================================================
203
204 ");
205
206 open(STATS, "> $dir/stats.excluded.$arch")
207 || die "Can't write in stats.excluded.$arch: $!\n";
208 foreach (keys %excluded) {
209 print STATS "$_ => $excluded{$_}\n";
210 }
211 close (STATS);
212
213 # Browse the list of packages to include
214 my ($output_size, $size) = (0, 0);
215 my %cds;
216
217 # Generate a dependency tree for each package
218 msg(0, " Generating dependency tree with apt-cache depends...\n");
219 my (@list) = grep (!/\/$codename-backports$/, keys %packages);
220 while (@list) {
221 my (@pkg) = splice(@list,0,200);
222 $ENV{'LC_ALL'} = 'C'; # Required since apt is now translated
223 open (APT, "$apt cache depends @pkg |") || die "Can't fork : $!\n";
224 my (@res) = (<APT>);
225 close APT or die "'apt-cache depends failed: $! \n";
226 # Getting rid of conflicts/replaces/provides
227 my $i = 0;
228 my $nb_lines = scalar @res;
229 push @res, ""; # Avoid warnings ...
230 while ($i < $nb_lines) {
231 if ($res[$i] !~ m/^(\S+)\s*$/) {
232 msg(0, "UNEXPECTED: Line `$res[$i]' while parsing " .
233 "end of deptree from '$p'\n");
234 die "sort_deps failed! :-(\n";
235 }
236 $p = lc $1;
237 $i++;
238 msg(2, " Dependency tree of `$p' ...\n");
239 read_depends (\$i, \@res, $p);
240 }
241
242 }
243 # Now redo with backports packages
244 if ($backports) {
245 @list = grep (/\/$codename-backports$/, keys %packages);
246 while (@list) {
247 my (@pkg) = splice(@list,0,200);
248 $ENV{'LC_ALL'} = 'C'; # Required since apt is now translated
249 open (APT, "USE_BP=1 $apt cache depends @pkg |") || die "Can't fork : $!\n";
250 my (@res) = (<APT>);
251 close APT or die "'apt-cache depends failed: $! \n";
252 # Getting rid of conflicts/replaces/provides
253 my $i = 0;
254 my $nb_lines = scalar @res;
255 push @res, ""; # Avoid warnings ...
256 while ($i < $nb_lines) {
257 if ($res[$i] !~ m/^(\S+)\s*$/) {
258 msg(0, "UNEXPECTED: Line `$res[$i]' while parsing " .
259 "end of deptree from '$p'\n");
260 die "sort_deps failed! :-(\n";
261 }
262 $p = lc $1;
263 $i++;
264 msg(2, " Dependency tree of `$p/$codename-backports' ...\n");
265 read_depends (\$i, \@res, "$p/$codename-backports");
266 }
267 }
268 # Now check and maybe up our dependencies in the backports
269 # packages. If any of them depend on package versions not already
270 # in the base set, change them to be package/$codename-backports
271 # instead. Only need to check direct dependencies here; any
272 # indirects going through base packages shouldn't have any
273 # backports dependencies, of course. Can only do this once we've
274 # read *all* the packages in.
275 @list = grep (/\/$codename-backports$/, keys %packages);
276 foreach my $pkg (@list) {
277 msg(1, "Fixing up deps for $pkg\n");
278 $packages{$pkg}{"Depends"} = fix_backport_depends($packages{$pkg}{"Depends"});
279 $packages{$pkg}{"Recommends"} = fix_backport_depends($packages{$pkg}{"Recommends"});
280 $packages{$pkg}{"Suggests"} = fix_backport_depends($packages{$pkg}{"Suggests"});
281 }
282 }
283
284 msg(0, " Adding standard, required, important and base packages first\n");
285 # Automatically include packages listed in the status file
286 open(STATUS, "< $adir/status") || die "Can't open status file $adir/status: $!\n";
287 while (defined($_ = <STATUS>)) {
288 next if not m/^Package: (\S+)/;
289 $p = $1;
290 if (not exists $packages{$p}) {
291 msg(1, "WARNING: Package `$p' is listed in the status file "
292 . "but doesn't exist ! (ignored) \n",
293 " TIP: Try to generate the status file with " .
294 "make (correct)status (after a make distclean)...\n");
295 next;
296 }
297 next if $excluded{$p};
298 if ($p =~ /\/$codename-backports$/) {
299 add_package($p, 1);
300 } else {
301 add_package($p, 0);
302 }
303 }
304 close STATUS;
305 msg(0, " S/R/I/B packages take $output_size bytes\n");
306
307 # Now start to look for packages wanted by the user ...
308 msg(0, " Adding the rest of the requested packages\n");
309 open (LIST, "< $listfile") || die "Can't open $listfile : $!\n";
310 while (defined($_=<LIST>)) {
311 chomp;
312 msg(1, "Looking at list, line \"$_\"\n");
313 next if m/^\s*$/;
314 if (not exists $packages{$_}) {
315 msg(1, "WARNING: '$_' does not appear to be available ... " .
316 "(ignored)\n");
317 next;
318 }
319 next if $excluded{$_};
320 if ($included{$_}) {
321 msg(3, "$_ has already been included.\n");
322 next;
323 }
324 # This is because udebs tend to have bad dependencies but work
325 # nevertheless ... this may be removed once the udebs have a
326 # better depencency system
327 if ($packages{$_}{"IsUdeb"}) {
328 add_to_output($_);
329 } else {
330 if ($_ =~ /\/$codename-backports$/) {
331 add_package($_, 1);
332 } else {
333 add_package($_, 0);
334 }
335 }
336 }
337 close LIST;
338
339 msg(0, " Now up to $output_size bytes\n");
340 # All requested packages have been included
341 # But we'll continue to add if $complete was requested
342 if ($complete) {
343 msg(0, " COMPLETE=1; add all remaining packages\n");
344 # Try to sort them by section even if packages from
345 # other sections will get in through dependencies
346 # With some luck, most of them will already be here
347 foreach my $p (sort { ($packages{lc $a}{"Section"} cmp $packages{lc $b}{"Section"})
348 || (lc $a cmp lc $b) }
349 grep { not ($included{$_} or $excluded{$_}) } keys %packages) {
350 # At this point, we should *not* be adding any more udebs,
351 # as they're no use to anybody.
352 if ($packages{lc $p}{"IsUdeb"}) {
353 msg(2, " Ignoring udeb $p ...\n");
354 } else {
355 if ($p =~ /\/$codename-backports$/i) {
356 add_package (lc $p, 1);
357 } else {
358 add_package (lc $p, 0);
359 }
360 }
361 }
362 }
363
364 # Now select the non-free packages for an extra CD
365 if ($extranonfree and (! $nonfree))
366 {
367 my ($p, @toinclude);
368
369 msg(0, " Adding non-free* packages now\n");
370
371 # Finally accept non-free packages that were excluded earlier ...
372 foreach my $reason ("nonfree", "nonfree-exclude-firmware") {
373 foreach $p (grep { $excluded{$_} eq $reason } (keys %excluded))
374 {
375 $excluded{$p} = 0;
376 push @toinclude, $p;
377 }
378 }
379
380 # Include non-free packages
381 foreach $p (@toinclude)
382 {
383 if ($p =~ /\/$codename-backports$/i) {
384 add_package (lc $p, 1);
385 } else {
386 add_package (lc $p, 0);
387 }
388 }
389
390 # If a contrib package was listed in the list of packages to
391 # include and if COMPLETE=0 there's a chance that the package
392 # will not get included in any CD ... so I'm checking the complete
393 # list again
394 open (LIST, "< $listfile") || die "Can't open $listfile : $!\n";
395 while (defined($_=<LIST>)) {
396 chomp;
397 next if m/^\s*$/;
398 next if $included{$_};
399 next if $included{lc $_};
400 next if $excluded{$_};
401 next if $excluded{lc $_};
402 if (not exists $packages{$_} && not exists $packages{lc $_}) {
403 msg(1, "WARNING: '$_' does not appear to be available ... " .
404 "(ignored)\n");
405 next;
406 }
407 if ($packages{lc $p}{"IsUdeb"}) {
408 msg(2, " Ignoring udeb $p ...\n");
409 } else {
410 if ($_ =~ /\/$codename-backports$/i) {
411 add_package (lc $_, 1);
412 } else {
413 add_package (lc $_, 0);
414 }
415 }
416 }
417 close LIST;
418
419 # Try to include other packages that could not be included
420 # before (because they depends on excluded non-free packages)
421 if ($complete)
422 {
423 foreach $p (sort { ($packages{$a}{"Section"}
424 cmp $packages{$b}{"Section"}) || ($a cmp $b) }
425 grep { not ($included{$_} or $excluded{$_}) }
426 keys %packages)
427 {
428 if ($packages{lc $p}{"IsUdeb"}) {
429 msg(2, " Ignoring udeb $p ...\n");
430 } else {
431 if ($p =~ /\/$codename-backports$/i) {
432 add_package (lc $p, 1);
433 } else {
434 add_package (lc $p, 0);
435 }
436 }
437 }
438 }
439
440 }
441
442 # Remove old files
443 foreach (glob("$dir/*.packages*")) {
444 unlink $_;
445 }
446
447 # Now write the list down
448 my $count = 0;
449 open(CDLIST, "> $dir/packages.$arch")
450 || die "Can't write in $dir/$_.packages.$arch: $!\n";
451 open(FWLIST, ">> $dir/firmware-packages")
452 || die "Can't write in $dir/firmware-packages: $!\n";
453 foreach (@output) {
454 my $component = $packages{$_}{"Component"};
455 my $size = $packages{$_}{"Size"};
456 my $bu = $packages{$_}{"Built-Using"};
457 print CDLIST "$arch:$component:$_:$size:$bu\n";
458 if ($packages{$_}{"IsFirmware"}) {
459 print FWLIST "$_\n";
460 }
461 $count++;
462 }
463 close CDLIST;
464 close FWLIST;
465 msg(0, "Done: processed/sorted $count packages, total size $output_size bytes.\n");
466
467 close LOG;
468
469 ## END OF MAIN
470 ## BEGINNING OF SUBS
471
472 sub parse_package {
473 my $p;
474 my $use_bp = shift;
475 m/^Package: (\S+)\s*$/m and $p = $1;
476 if ($use_bp) {
477 $p = "$p/$codename-backports";
478 }
479 $included{$p} = 0;
480 $packages{$p}{"Package"} = $p;
481 foreach $re (qw(Version Priority Section Filename Size MD5sum)) {
482 (m/^$re: (\S+)\s*$/m and $packages{$p}{$re} = $1)
483 || msg(1, "Header field '$re' missing for package '$p'.\n");
484 }
485 $packages{$p}{"Depends"} = [];
486 $packages{$p}{"Suggests"} = [];
487 $packages{$p}{"Recommends"} = [];
488 $packages{$p}{"Built-Using"} = "";
489 if (m/^Built-Using: (.*)$/m) {
490 my $built = $1;
491 $built =~ s/ \(= \S*\)//g;
492 $built =~ s/,//g;
493 $built =~ s/ /,/g;
494 $packages{$p}{"Built-Using"} = $built;
495 }
496 $packages{$p}{"IsUdeb"} = ($packages{$p}{"Filename"} =~ /.udeb$/) ? 1 : 0;
497 $packages{$p}{"IsFirmware"} = ($packages{$p}{"Filename"} =~ /(firmware|microcode)/) ? 1 : 0;
498 if ($packages{$p}{"Section"} =~ /contrib\//) {
499 $packages{$p}{"Component"} = "contrib";
500 } elsif ($packages{$p}{"Section"} =~ /non-free\//) {
501 $packages{$p}{"Component"} = "non-free";
502 } elsif ($packages{$p}{"Section"} =~ /non-free-firmware\//) {
503 $packages{$p}{"Component"} = "non-free-firmware";
504 } elsif ($packages{$p}{"IsUdeb"}) {
505 $packages{$p}{"Component"} = "main-installer";
506 } else {
507 $packages{$p}{"Component"} = "main";
508 }
509 }
510
511 sub dump_depend {
512 my $tmpin = shift;
513 my %d;
514 my $ret = "";
515
516 if ("ARRAY" eq ref($tmpin)) {
517 my @array = @{$tmpin};
518 foreach (@array) {
519 %d = %$_;
520 $ret .= $d{"Package"};
521 if ($d{"CmpOp"} ne "") {
522 $ret .= " (" . $d{"CmpOp"} . " " . $d{"Version"} . ")";
523 }
524 $ret .= " ";
525 }
526 } elsif ("HASH" eq ref($tmpin)) {
527 %d = %$tmpin;
528 $ret .= $d{"Package"};
529 if ($d{"CmpOp"} ne "") {
530 $ret .= " (" . $d{"CmpOp"} . " " . $d{"Version"} . ")";
531 }
532 } else {
533 die "dump_depend: $tmpin is neither an array nor a hash!\n";
534 }
535
536 return $ret;
537 }
538
539 sub dump_or_list {
540 my $out_type = shift;
541 my $elt = shift;
542 my @or = @$elt;
543
544 if (scalar @or == 1) {
545 msg(1, " $out_type: " . dump_depend($or[0]) . "\n");
546 } else {
547 msg(1, " $out_type: OR (");
548 foreach my $t (@or) {
549 msg(1, dump_depend($t) . " ");
550 }
551 msg(1, ")\n");
552 }
553 }
554
555 sub read_depends {
556 my $i = shift; # Ref
557 my $lines = shift; # Ref
558 my $pkg = shift; # string
559 my $types = "(?:Pre)?Depends|Suggests|Recommends|Replaces|Conflicts|Breaks|Enhances";
560 my (@dep, @rec, @sug);
561 my ($type, $or);
562
563 while ($lines->[$$i] =~ m/^\s([\s\|])($types):/) {
564 $type = $2; $or = $1;
565 # Get rid of replaces, conflicts and any other fields we don't
566 # care about...
567 if (($type eq "Replaces") or
568 ($type eq "Conflicts") or
569 ($type eq "Breaks") or
570 ($type eq "Enhances")) {
571 $$i++;
572 while ($lines->[$$i] =~ m/^\s{4}/) {
573 $$i++;
574 }
575 next;
576 }
577
578 my $out_type = $type;
579 $out_type =~ s/^Pre//; # PreDepends are like Depends for me
580
581 # Check the kind of depends : or, virtual, normal
582 if ($or eq '|') {
583 my $elt = read_ordepends ($i, $lines);
584 dump_or_list($out_type, \@$elt);
585 push @{$packages{$pkg}{$out_type}}, $elt;
586 } elsif ($lines->[$$i] =~ m/^\s\s$type: <([^>]+)>/) {
587 my $elt = read_virtualdepends ($i, $lines);
588 foreach my $t (@$elt) {
589 msg(1, " $out_type: " . dump_depend($t) . " <virt>\n");
590 }
591 push @{$packages{$pkg}{$out_type}}, $elt;
592 } elsif ($lines->[$$i] =~ m/^\s\s$type: (\S+)( \((\S+) (\S+)\))*/) {
593 my @or;
594 my %elt;
595 $elt{"Package"} = $1;
596 if (defined $2) {
597 $elt{"CmpOp"} = $3;
598 $elt{"Version"} = $4;
599 } else {
600 $elt{"CmpOp"} = "";
601 $elt{"Version"} = "";
602 }
603 push @or, \%elt;
604 $$i++;
605
606 # Special case for packages providing not
607 # truly virtual packages
608 if ($lines->[$$i] =~ m/^\s{4}/) {
609 while ($lines->[$$i] =~ m/\s{4}(\S+)( \((\S+) (\S+)\))*/) {
610 my %elt1;
611 $elt1{"Package"} = $1;
612 if (defined $2) {
613 $elt1{"CmpOp"} = $3;
614 $elt1{"Version"} = $4;
615 } else {
616 $elt1{"CmpOp"} = "";
617 $elt1{"Version"} = "";
618 }
619 push @or, \%elt1;
620 $$i++;
621 }
622 }
623 dump_or_list($out_type, \@or);
624 push @{$packages{$pkg}{$out_type}}, \@or;
625 } else {
626 msg(0, "ERROR: Unknown depends line : $lines->[$$i]\n");
627 foreach ($$i - 3 .. $$i + 3) {
628 msg(0, " ", $lines->[$_]);
629 }
630 }
631 }
632 }
633
634 # Big matrix of tests. Check to see if the available version of a
635 # package matches what we're requesting in a dependency relationship
636 sub check_versions {
637 my $wanted = shift;
638 my $op = shift;
639 my $available = shift;
640
641 # Trivial check - if we don't care about versioning, anything will
642 # do!
643 if ($op eq "") {
644 return 1;
645 }
646
647 # Ask the dpkg perl code to compare the version strings
648 my $comp = version_compare($available, $wanted);
649
650 if ($op eq "<=") {
651 if ($comp == -1 || $comp == 0) {
652 return 1;
653 }
654 } elsif ($op eq ">=") {
655 if ($comp == 0 || $comp == 1) {
656 return 1;
657 }
658 } elsif ($op eq "<<") {
659 if ($comp == -1) {
660 return 1;
661 }
662 } elsif ($op eq ">>") {
663 if ($comp == 1) {
664 return 1;
665 }
666 } elsif ($op eq "=") {
667 if ($comp == 0) {
668 return 1;
669 }
670 # Not sure this ("!") actually exists!
671 # Mentioned in apt sources, but not in debian policy
672 # No harm done by checking for it, though...
673 } elsif ($op eq "!") {
674 if ($comp == -1 || $comp == 1) {
675 return 1;
676 }
677 }
678 # else
679 return 0;
680 }
681
682 # Check if a specific dependency package is installed already
683 sub dep_pkg_included {
684 my $p = shift;
685 my $check_backports = shift;
686 my $need_udeb = shift;
687 my %d = %$p;
688 my $pn = $d{"Package"};
689
690 if ($included{$pn}) {
691 if (check_versions($d{"Version"}, $d{"CmpOp"}, $packages{$pn}{"Version"})) {
692 if ($packages{$pn}{"IsUdeb"} == $need_udeb) {
693 msg(1, " $pn is included already, acceptable version " . $packages{$pn}{"Version"} . "\n");
694 return 1;
695 } else {
696 my $explanation = "it's a udeb instead of regular deb";
697 $explanation = "it's a deb instead of an udeb" if $need_udeb;
698 msg(1, " $pn is included already, but $explanation\n");
699 }
700 } else {
701 msg(1, " $pn is included already, but invalid version " . $packages{$pn}{"Version"} . "\n");
702 }
703 }
704 msg(1, " $pn not included in a useful version, check_backports $check_backports\n");
705 if ($check_backports) {
706 $pn = "$pn/$codename-backports";
707 msg(1, " Checking $pn too:\n");
708 if ($included{$pn}) {
709 if (check_versions($d{"Version"}, $d{"CmpOp"}, $packages{$pn}{"Version"})) {
710 if ($packages{$pn}{"IsUdeb"} == $need_udeb) {
711 msg(1, " $pn is included already, acceptable version " . $packages{$pn}{"Version"} . "\n");
712 return 1;
713 } else {
714 my $explanation = "it's a udeb instead of regular deb";
715 $explanation = "it's a deb instead of an udeb" if $need_udeb;
716 msg(1, " $pn is included already, but $explanation\n");
717 }
718 } else {
719 msg(1, " $pn is included already, but invalid version " . $packages{$pn}{"Version"} . "\n");
720 }
721 msg(1, " $pn not included in a useful version\n");
722 }
723 }
724 # else
725 return 0;
726 }
727
728 # Check backports package dependencies; update them if they are also only in backports
729 sub fix_backport_depends {
730 my $deplist = shift;
731 my @new_dep_list;
732 foreach my $thisdep (@{$deplist}) {
733 if ("ARRAY" eq ref($thisdep)) {
734 # If it's an OR list
735 my @new_or_list;
736 foreach my $pkg (@{$thisdep}) {
737 my %t = %$pkg;
738 my $pkgname = lc $t{"Package"};
739 # Does the package exist?
740 if (exists $excluded{$pkgname} &&
741 check_versions($t{"Version"}, $t{"CmpOp"}, $packages{$pkgname}{"Version"})) {
742 # Looks fine already
743 push (@new_or_list, $pkg);
744 next;
745 }
746 # Doesn't exist, or version doesn't work. Try backports
747 $pkgname = "$pkgname/$codename-backports";
748 if (exists $excluded{$pkgname} &&
749 check_versions($t{"Version"}, $t{"CmpOp"}, $packages{$pkgname}{"Version"})) {
750 my %elt;
751 $elt{"Package"} = $pkgname;
752 $elt{"CmpOp"} = $t{"CmpOp"};
753 $elt{"Version"} = $t{"Version"};
754 push @new_or_list, \%elt;
755 msg(1, " Upgrading dep to $pkgname\n");
756 next;
757 }
758 }
759 push (@new_dep_list, \@new_or_list);
760 } else {
761 # It's virtual or a normal package
762 my %t = %{$thisdep};
763 my $pkgname = lc $t{"Package"};
764 # Does the package exist?
765 if (exists $excluded{$pkgname} &&
766 check_versions($t{"Version"}, $t{"CmpOp"}, $packages{$pkgname}{"Version"})) {
767 # Looks fine already
768 push (@new_dep_list, $thisdep);
769 next;
770 }
771 # Doesn't exist, or version doesn't work. Try backports
772 $pkgname = "$pkgname/$codename-backports";
773 if (exists $excluded{$pkgname} &&
774 check_versions($t{"Version"}, $t{"CmpOp"}, $packages{$pkgname}{"Version"})) {
775 my %elt;
776 $elt{"Package"} = $pkgname;
777 $elt{"CmpOp"} = $t{"CmpOp"};
778 $elt{"Version"} = $t{"Version"};
779 push @new_dep_list, \%elt;
780 msg(1, " Upgrading dep to $pkgname\n");
781 next;
782 }
783 }
784 }
785 return \@new_dep_list;
786 }
787
788 # Check to see if a dependency is satisfied, either a direct
789 # dependency or any one of an OR array
790 sub dep_satisfied {
791 my $p = shift;
792 my $check_backports = shift;
793 my $need_udeb = shift;
794
795 if ("ARRAY" eq ref $p) {
796 foreach (@{$p}) {
797 if (dep_pkg_included($_, $check_backports, $need_udeb)) {
798 return 1;
799 }
800 }
801 } elsif ("HASH" eq ref $p) {
802 return dep_pkg_included($p, $check_backports, $need_udeb);
803 } else {
804 }
805 return 0;
806 }
807
808 sub read_ordepends {
809 my $i = shift;
810 my $lines = shift;
811 my @or = ();
812 my ($val, $dep, $last) = ('','',0);
813 my ($op, $version);
814
815 chomp $lines->[$$i];
816
817 while ($lines->[$$i]
818 =~ m/^\s([\s\|])((?:Pre)?Depends|Suggests|Recommends): (\S+)( \((\S+) (\S+)\))*/) {
819 $val = $3;
820 if (defined $4) {
821 $op = $5;
822 $version = $6;
823 } else {
824 $op = "";
825 $version = "";
826 }
827 $last = 1 if $1 ne '|'; #Stop when no more '|'
828 if ($val =~ m/^<.*>$/) {
829 $dep = read_virtualdepends ($i, $lines);
830 if (ref $dep) {
831 push @or, @{$dep};
832 } else {
833 push @or, $dep;
834 }
835 } else {
836 my %elt;
837 $elt{"Package"} = $val;
838 $elt{"CmpOp"} = $op;
839 $elt{"Version"} = $version;
840 push @or, \%elt;
841 $$i++;
842 # Hack for packages providing not a truly
843 # virtual package
844 while ($lines->[$$i] =~ m/^\s{4}(\S+)( \((\S+) (\S+)\))*/) {
845 my %elt1;
846 $elt1{"Package"} = $1;
847 if (defined $2) {
848 $elt1{"CmpOp"} = $3;
849 $elt1{"Version"} = $4;
850 } else {
851 $elt1{"CmpOp"} = "";
852 $elt1{"Version"} = "";
853 }
854 msg(1, " " . dump_depend(\%elt1) . "\n");
855 push @or, \%elt1;
856 $$i++;
857 }
858 }
859 last if $last;
860 }
861 return \@or;
862 }
863
864 sub read_virtualdepends {
865 my $i = shift;
866 my $lines = shift;
867 my $virtual;
868 my @or = ();
869
870 #Check for the lines with <>
871 if ($lines->[$$i]
872 =~ m/^\s[\s\|]((?:Pre)?Depends|Recommends|Suggests): <([^>]+)>/) {
873 $virtual = $2;
874 $$i++
875 }
876 # Now look at the alternatives on the following lines
877 while ($lines->[$$i] =~ m/^\s{4}(\S+)( \((\S+) (\S+)\))*/) {
878 my %elt;
879 $elt{"Package"} = $1;
880 if (defined $2) {
881 $elt{"CmpOp"} = $3;
882 $elt{"Version"} = $4;
883 } else {
884 $elt{"CmpOp"} = "";
885 $elt{"Version"} = "";
886 }
887 push @or, \%elt;
888 $$i++;
889 }
890 if (@or) {
891 return \@or;
892 } else {
893 my %elt;
894 $elt{"Package"} = $virtual;
895 $elt{"CmpOp"} = "";
896 $elt{"Version"} = "";
897 push @or, \%elt;
898 return \@or;
899 }
900 }
901
902 sub add_package {
903 my $p = shift;
904 my $check_backports = shift;
905 my ($ok, $reasons);
906
907 msg(2, "+ Trying to add $p...\n");
908 if ($included{$p}) {
909 msg(2, " Already included ...\n");
910 return;
911 }
912
913 # Get all dependencies (not yet included) of each package
914 my (@dep) = (get_missing ($p, $check_backports));
915
916 # Stop here if apt failed
917 if (not scalar(@dep)) {
918 msg(2, "Can't add $p ... dependency problem.\n");
919 return;
920 }
921
922 if ($packages{$p}{"Size"} > $max_pkg_size) {
923 $size = $packages{$p}{"Size"};
924 msg(2, "Can't add $p ... too big! ($size > $max_pkg_size)\n");
925 $excluded{$p} = 'toobig';
926 return;
927 }
928
929 msg(3, " \@dep before checklist = " . dump_depend(\@dep) . "\n");
930
931 # Check if all packages are allowed (fail if one cannot)
932 ($ok, $reasons) = check_list (\@dep, 1, $check_backports);
933 if (not $ok) {
934 msg(2, "Can't add $p ... one of the packages needed has " .
935 "been refused. Reasons: $reasons\n");
936 return;
937 }
938
939 msg(3, " \@dep after checklist = " . dump_depend(\@dep) . "\n");
940
941 # All packages are ok, now list them out and add sizes
942 foreach my $t (@dep) {
943 my %t = %$t;
944 my $pkgname = $t{"Package"};
945 add_to_output($pkgname);
946 }
947 }
948
949 sub accepted {
950 my $p = shift;
951 if (exists $excluded{$p}) {
952 return not $excluded{$p}
953 }
954 # Return false for a non-existent package ...
955 return 0;
956 }
957
958 sub get_missing {
959 my $p = shift;
960 my $check_backports = shift;
961 my @deps_list = ();
962 my %t;
963 my $dep_text;
964 my $found_missing = 0;
965
966 $t{"Package"} = $p;
967 $t{"CmpOp"} = "";
968 $t{"Version"} = "";
969
970 if (add_missing (\@deps_list, $packages{$p}{"Depends"}, \%t, 0, $check_backports)) {
971 $found_missing = 1;
972 }
973
974 if ($add_rec and add_missing (\@deps_list, $packages{$p}{"Recommends"}, \%t, 1, $check_backports)) {
975 $found_missing = 1;
976 }
977
978 if ($add_sug and add_missing (\@deps_list, $packages{$p}{"Suggests"}, \%t, 1, $check_backports)) {
979 $found_missing = 1;
980 }
981
982 if (not $found_missing) {
983 return ();
984 }
985
986 # Explicitly move the package itself to the end of the list,
987 # i.e. *after* all its dependencies
988 remove_entry(\%t, \@deps_list);
989 push @deps_list, \%t;
990
991 return (@deps_list);
992 }
993
994 # Recursive function adding packages to our list
995 sub add_missing {
996 my $list = shift;
997 my $new = shift;
998 my $pkgin = shift;
999 my @backup = @{$list};
1000 my $ok = 1;
1001 my $soft_depend = shift;
1002 my $check_backports = shift;
1003 my (%pkgin);
1004
1005 if (ref $pkgin eq "HASH") {
1006 %pkgin = %$pkgin;
1007 } else {
1008 die "add_missing passed a non-hash";
1009 }
1010
1011 my $need_udeb = $packages{$pkgin{"Package"}}{"IsUdeb"};
1012 my $pkgname = $pkgin{"Package"};
1013
1014 # Check all dependencies
1015 foreach my $thisdep (@{$new}) {
1016 my $textout = "";
1017 my $type_rel = "simple";
1018
1019 if ("ARRAY" ne ref($thisdep)) {
1020 die "add_missing: $thisdep should be an array!\n";
1021 }
1022
1023 # Print out status
1024 if (scalar(@{$thisdep} > 1)) {
1025 $textout = "(OR ";
1026 $type_rel = "OR";
1027 }
1028 foreach my $orpkg (@{$thisdep}) {
1029 $textout .= dump_depend($orpkg) . " ";
1030 }
1031 if (scalar(@{$thisdep} > 1)) {
1032 $textout .= ")";
1033 }
1034 msg(3, " $pkgname Dep: $textout soft_depend $soft_depend\n");
1035
1036 # Bail out early if we can!
1037 if (dep_satisfied ($thisdep, $check_backports, $need_udeb)) {
1038 next;
1039 }
1040
1041 # Still work to do...
1042 my $or_ok = 0;
1043
1044 # First check all the OR packages up-front with no
1045 # recursion. If *any* one of them is already installed, it
1046 # will do.
1047 foreach my $pkg (@{$thisdep}) {
1048 my %t = %$pkg;
1049 my $pkgname = lc $t{"Package"};
1050
1051 if (exists $packages{$pkgname} &&
1052 ($packages{$pkgname}{"Size"} > $max_pkg_size)) {
1053 msg(2, " $pkgname is too big, mark it as excluded\n");
1054 $excluded{$pkgname} = 'toobig';
1055 }
1056
1057 # Already installed?
1058 if (dep_satisfied($pkg, $check_backports, $need_udeb)) {
1059 msg(3, " $type_rel relationship already installed: " . dump_depend($pkg) . "\n");
1060 $or_ok = 1;
1061 last;
1062 }
1063
1064 # Pulled in already somewhere above us in the
1065 # depth-first search? (yes, we have to cope with
1066 # circular dependencies here...)
1067 if (is_in_dep_list($pkg, $list, $soft_depend)) {
1068 msg(3, " $type_rel relationship already satisfied by current list " . dump_depend($pkg) . "\n");
1069 $or_ok = 1;
1070 last;
1071 }
1072 # else
1073 msg(3, " " . dump_depend($pkg) . " not already installed\n");
1074 }
1075
1076 # If we don't have any of the OR packages, then start
1077 # again and try them in order. We always add the first
1078 # package in the OR to allow APT to figure out which is
1079 # the better one to install for any combination of
1080 # packages that have similar alternative dependencies, but
1081 # in different order. Having the first alternative
1082 # available should be good enough for all cases we care
1083 # about.
1084 if (not $or_ok) {
1085 msg(3, " $type_rel relationship not already satisfied, looking at alternatives in order, check_backports $check_backports\n");
1086
1087 foreach my $pkg (@{$thisdep}) {
1088 my %t = %$pkg;
1089 my $pkgname = $t{"Package"};
1090 if (not accepted($pkgname)) {
1091 if ($check_backports && accepted("$pkgname/$codename-backports")) {
1092 $pkgname = "$pkgname/$codename-backports";
1093 $t{"Package"} = $pkgname;
1094 } else {
1095 next;
1096 }
1097 }
1098
1099 # Stop after the first
1100 # package that is
1101 # added successfully
1102 # FIXME! NEED TO CHECK IF VERSION DEPS ARE SATISFIED, FALL BACK TO BPO VERSION
1103 push (@{$list}, $pkg);
1104 if (add_missing ($list, $packages{$pkgname}{"Depends"}, $pkg, $soft_depend, $check_backports)) {
1105 $or_ok = 1;
1106 if ($add_rec) {
1107 add_missing ($list, $packages{$pkgname}{"Recommends"}, $pkg, 1, $check_backports);
1108 }
1109 if ($add_sug) {
1110 add_missing ($list, $packages{$pkgname}{"Suggests"}, $pkg, 1, $check_backports);
1111 }
1112 remove_entry($pkg, $list);
1113 push @{$list}, $pkg;
1114 last;
1115 } else {
1116 pop @{$list};
1117 }
1118 }
1119 }
1120 $ok &&= $or_ok;
1121 if (not $ok) {
1122 $pkgname = $pkgin{"Package"};
1123 if ($soft_depend) {
1124 msg(1, " $pkgname failed, couldn't satisfy $type_rel dep (but it's a soft dep, so ignoring...)\n");
1125 $ok = 1;
1126 } else {
1127 msg(1, " $pkgname failed, couldn't satisfy $type_rel dep\n");
1128 }
1129 }
1130 }
1131 # If a problem has come up, then restore the original list
1132 if (not $ok) {
1133 @{$list} = @backup;
1134 }
1135 if (not is_in_dep_list(\%pkgin, $list, $soft_depend)) {
1136 push @{$list}, \%pkgin;
1137 }
1138 return $ok;
1139 }
1140
1141 # Check if $value is in @{$array}
1142 sub is_in {
1143 my $value = shift;
1144 my $array = shift;
1145 foreach my $key (@{$array}) {
1146 return 1 if ($key eq $value);
1147 }
1148 return 0;
1149 }
1150
1151 # Check if a package dependency is already in a dependency list
1152 sub is_in_dep_list {
1153 my $hash = shift;
1154 my $array = shift;
1155 my $soft_dep = shift // 0; # When analyzing recommends
1156 my %t = %$hash;
1157
1158 foreach my $key (@{$array}) {
1159 my %a = %$key;
1160 if ($a{"Package"} eq $t{"Package"}) {
1161 my $pn = $a{"Package"};
1162 if ($soft_dep) {
1163 # We don't have to ensure exact version when we analyze
1164 # Recommends/Suggests
1165 return 1;
1166 } elsif (check_versions($t{"Version"}, $t{"CmpOp"}, $packages{$pn}{"Version"})) {
1167 return 1;
1168 }
1169 }
1170 }
1171 return 0;
1172 }
1173
1174 # Remove an antry from @{$array}
1175 sub remove_entry {
1176 my $tmp1 = shift;
1177 my $array = shift;
1178 my $entries = scalar(@{$array});
1179 my $i;
1180 my %t1 = %$tmp1;
1181
1182 for ($i=0; $i < $entries; $i++) {
1183 my $tmp2 = @{$array}[$i];
1184 my %t2 = %$tmp2;
1185 if ($t1{"Package"} eq $t2{"Package"}) {
1186 splice(@{$array}, $i, 1);
1187 $i--;
1188 $entries--;
1189 }
1190 }
1191 }
1192
1193 # Check a list of packages
1194 sub check_list {
1195 my $ref = shift;
1196 my $fail = shift;
1197 my $check_backports = shift;
1198 my $ok = 1;
1199 my @to_remove = ();
1200 my $reasons = "";
1201 foreach my $thispkg (@{$ref}) {
1202 my %t = %$thispkg;
1203 my $pkgname = $t{"Package"};
1204 if (not exists $excluded{$pkgname}) {
1205 msg(1," $pkgname has been refused because it doesn't exist ...\n");
1206 $ok = 0;
1207 push @to_remove, $thispkg;
1208 $reasons = $reasons . " noexist";
1209 next;
1210 }
1211 if (not accepted($pkgname)) {
1212 my $text = $excluded{"$pkgname"};
1213 msg(1," $pkgname has been refused because of $text ...\n");
1214 $ok = 0;
1215 push @to_remove, $thispkg;
1216 $reasons = $reasons . " " . $excluded{$pkgname};
1217 next;
1218 }
1219 if ($check_backports &&
1220 ($pkgname !~ /\/$codename-backports/) &&
1221 (not accepted("$pkgname/$codename-backports"))) {
1222 my $text = $excluded{"$pkgname/$codename-backports"};
1223 msg(1," $pkgname/$codename-backports has been refused because of $text} ...\n");
1224 $ok = 0;
1225 push @to_remove, $thispkg;
1226 $reasons = $reasons . " " . $excluded{$pkgname};
1227 next;
1228 }
1229 if ($included{$pkgname}) {
1230 msg(1, " $pkgname has already been included.\n");
1231 push @to_remove, $thispkg;
1232 $reasons = $reasons . " alreadyinc";
1233 next;
1234 }
1235 if ($check_backports && $included{"$pkgname/$codename-backports"}) {
1236 msg(1, " $pkgname/$codename-backports has already been included.\n");
1237 push @to_remove, $thispkg;
1238 $reasons = $reasons . " alreadyinc";
1239 next;
1240 }
1241 }
1242 foreach my $removed (@to_remove) {
1243 my %t = %$removed;
1244 my $pkgname = $t{"Package"};
1245 msg(2, " Removing $pkgname ... ($reasons )\n");
1246 @{$ref} = grep { $_ ne $removed } @{$ref};
1247 }
1248 return ($fail ? $ok : 1, $reasons);
1249 }
1250
1251 # Add packages to the output list
1252 sub add_to_output {
1253 my $pkgname = shift;
1254 my $size = $packages{$pkgname}{"Size"};
1255
1256 $output_size += $size;
1257 $included{$pkgname} = 1;
1258 push(@output, $pkgname);
1259 }
1260
1261 sub yesno {
1262 my $in = shift;
1263 return $in ? "yes" : "no";
1264 }