Debian Codegraph @

debtree

raw
1 #! /usr/bin/perl -w
2
3 # debtree version 1.0.2
4 # Copyright 2007-2009 Frans Pop <[email protected]>
5 # This program is free software; you can redistribute it and/or modify it
6 # under the terms of the GNU General Public License as published by the Free
7 # Software Foundation; either version 2 of the License, or (at your option)
8 # any later version.
9
10 # Usage: debtree [options] <package name>
11
12 # The script produces a dot file for processing with 'dot'.
13 # Examples: debtree <package> > <package>.dot
14 # debtree <package> | dot -Tpng -o <package>.png
15 # debtree <package> | dot -Tps | kghostview -
16
17 sub usage {
18 warn join(" ", @_)."\n" if @_;
19 warn <<EOF;
20 Usage: $0 [options] package
21
22 For details, see man page.
23 EOF
24 exit(1);
25 }
26
27 use strict;
28 use Cwd;
29 use Getopt::Long;
30
31 ### INITIALIZATION ###
32
33 my $HOME;
34 ($HOME = $ENV{'HOME'}) or die "HOME not defined in environment!\n";
35
36 my @ARCHES = qw/alpha amd64 arm armel hppa i386 ia64 mips mipsel powerpc s390 sparc/;
37 push(@ARCHES, qw/hurd-i386 kfreebsd-i386 kfreebsd-amd64 m68k ppc64 sh all/);
38
39 my $ptype;
40 my $verbose = 0;
41 my $quiet = 0;
42 my $show_installed = 0;
43 my $show_rdeps = 0;
44 my $build_dep = 0;
45 my $with_alternatives = 1;
46 my $with_suggests = 0;
47 my $with_recommends = 1;
48 my $with_conflicts = 1;
49 my $with_vconflicts = 0;
50 my $with_provides = 1;
51 my $max_providers = 3;
52 my $with_versions = 1;
53 my $max_depth = 999999;
54 my $rdeps_depth = 0;
55 my $max_rdeps=5;
56 my $no_skip = 0;
57 my $show_all = 0;
58 my $do_rotate = 0;
59 my $do_condense = 0;
60 my $ARCH="";
61 my $endlist="";
62 my $skiplist="";
63 my $download_size=0;
64 my $total_size=0;
65
66 # Hash containing skip and end packages read from config files
67 my %clist;
68 # Hash containing global package status info; used types are:
69 # skipped, ended, done, leaf, unknown, OR_seen, rdep, prov_rdeps
70 my %pstatus;
71
72 my (%OR_dep_list, %OR_virt_list, %pdep_set_list);
73 my $OR_dep_cnt = 0;
74 my $OR_virt_cnt = 0;
75 my $pdep_set_cnt = 0;
76
77 $Getopt::Long::ignorecase = 0;
78 GetOptions(
79 'show-installed|I' => \$show_installed,
80 'show-rdeps|R' => \$show_rdeps,
81 'build-dep|b' => \$build_dep,
82 'alternatives!' => \$with_alternatives,
83 'recommends!' => \$with_recommends,
84 'conflicts!' => \$with_conflicts,
85 'provides!' => \$with_provides,
86 'max-providers=i' => \$max_providers,
87 'with-suggests|S' => \$with_suggests,
88 'versioned-conflicts|VC' => \$with_vconflicts,
89 'versions!' => \$with_versions,
90 'max-depth=i' => \$max_depth,
91 'rdeps-depth=i' => \$rdeps_depth,
92 'max-rdeps=i' => \$max_rdeps,
93 'skip!' => \$no_skip,
94 'show-all' => \$show_all,
95 'rotate|r' => \$do_rotate,
96 'condense' => \$do_condense,
97 'arch=s' => \$ARCH,
98 'endlist=s' => \$endlist,
99 'skiplist=s' => \$skiplist,
100 'quiet|q' => \$quiet,
101 'verbose|v+' => \$verbose,
102 ) or usage;
103 #usage if $help;
104
105 # Package for which to generate the graph
106 my $requested_package = shift or error("invalid number of arguments");
107
108 if (@ARGV) {
109 #error("invalid number of arguments");
110 print(STDERR "Listing of dependency paths is no longer supported.\n");
111 print(STDERR "Use 'aptitude why' instead.\n");
112 exit 1;
113 }
114
115 # Raise verbosity level by one unless the quiet option was passed
116 $verbose++ unless $quiet;
117
118 # Don't allow Suggests without Recommends
119 $with_suggests = 0 unless $with_recommends;
120 # Don't allow versioned Conflicts without Conflicts
121 $with_vconflicts = 0 unless $with_conflicts;
122
123 # Build-dep implies no-suggests and no-alternatives (unless installed packages
124 # are being displayed); recommends are optional; rdeps are not allowed
125 if ($build_dep) {
126 $ptype = "S";
127 $with_suggests = 0;
128 $show_rdeps = 0;
129 $with_alternatives = 0 unless $show_installed;
130 $with_provides = 0;
131 } else {
132 $ptype = "B";
133 }
134 error("invalid value for option 'arch'") if ($ARCH && ! grep (/^$ARCH$/, @ARCHES));
135
136 # These options are overlapping
137 $rdeps_depth = 1 if ($show_rdeps && $rdeps_depth == 0);
138 $show_rdeps = 1 if ($rdeps_depth);
139
140 error("invalid value for option 'max-providers'") if ($max_providers < 1);
141 error("invalid value for option 'max-depth'") if ($max_depth < 0);
142 error("invalid value for option 'rdeps-depth'") if ($show_rdeps && $rdeps_depth < 1);
143 error("invalid value for option 'max-rdeps'") if ($max_rdeps < 1);
144
145 # The dependency types to display in the graph
146 my @dtypes = qw/PreDepends Depends/;
147 push(@dtypes, "Recommends") if $with_recommends;
148 push(@dtypes, "Suggests") if $with_suggests;
149 push(@dtypes, "Conflicts") if $with_conflicts;
150 # Same for reverse dependencies
151 my @rdtypes = qw/PreDepends Depends/;
152 push(@rdtypes, "Recommends") if $with_recommends;
153
154 # ToDo: use configurable colors for everything?
155 my $rdep_color;
156 if ($show_installed) {
157 $rdep_color = "azure";
158 } else {
159 $rdep_color = "ivory";
160 }
161
162 ## Initialize AptPkg's interface
163
164 use AptPkg::Config '$_config';
165 use AptPkg::System '$_system';
166 use AptPkg::Source;
167 use AptPkg::Cache;
168 $_config->init();
169 $_system = $_config->system();
170
171 if ($verbose) {
172 # Redirect AptPkg's little ditty so it doesn't go into our files
173 open(OLDOUT, ">&STDOUT");
174 open(STDOUT, ">&STDERR");
175 select(STDERR); $| = 1;
176 } else {
177 $_config->{quiet} = 2;
178 }
179
180 # Create instances to search for Depends and, if needed, Build-Depends
181 my $cache = AptPkg::Cache->new();
182 my $source;
183 # AptPkg does not expose architecture conditions, but it does take them
184 # into account when determining which dependencies to return. So we can
185 # use AptPkg to show build dependencies for a specific architecture, but
186 # not when ARCH=all. For that case we call out to apt-cache instead.
187 # AptPkg defaults to the host system's architecture.
188 if ($build_dep && $ARCH ne "all") {
189 $_config->{"APT::Architecture"} = $ARCH if $ARCH;
190 $source = AptPkg::Source->new();
191 }
192
193 if ($verbose) {
194 # Restore the redirects
195 close(STDOUT);
196 open(STDOUT, ">&OLDOUT");
197 close(OLDOUT);
198 select(STDOUT); $| = 0;
199 }
200
201 ### LOG FUNCTIONS ###
202
203 sub mylog {
204 my ($loglevel, $msg) = @_;
205 if ($loglevel <= $verbose) {
206 print(STDERR "$msg\n");
207 }
208 }
209 sub info {
210 my ($loglevel, $msg) = @_;
211 mylog($loglevel, "I: $msg");
212 }
213 sub mywarn {
214 my ($loglevel, $msg) = @_;
215 mylog($loglevel, "W: $msg");
216 }
217 sub debug {
218 my ($loglevel, $msg) = @_;
219 mylog($loglevel, "D: $msg");
220 }
221 sub error {
222 my $msg = shift;
223 mylog(0, "Error: $msg");
224 exit 1
225 }
226
227 ### FUNCTIONS ###
228
229 # Translates AptPkg's (localized) dependency types to what's used by debtree.
230 # This is only needed for regular dependencies, not build dependencies.
231 sub get_type {
232 my $apt_dtype = shift;
233 return "PreDepends" if ($apt_dtype == AptPkg::Dep::PreDepends);
234 return "Depends" if ($apt_dtype == AptPkg::Dep::Depends);
235 return "Recommends" if ($apt_dtype == AptPkg::Dep::Recommends);
236 return "Suggests" if ($apt_dtype == AptPkg::Dep::Suggests);
237 return "Conflicts" if ($apt_dtype == AptPkg::Dep::Conflicts);
238 return "Unsupported";
239 }
240
241 sub import_list {
242 my ($file, $ltype) = @_;
243
244 if (open LIST, "<$file") {
245 while (<LIST>) {
246 chomp;
247 my ($line) = /^\s*([^#]+)/;
248 $line =~ s/\s+$// if $line;
249 next unless $line;
250 for my $package (split(/ +/, $line)) {
251 $clist{$package}{$ltype} = 1;
252 }
253 }
254 }
255 close LIST;
256 }
257
258 sub get_bdeps_all {
259 my $package = shift;
260
261 my $pinfo = `apt-cache showsrc $package | grep -E "^Build-Depends(-Indep)?:"`;
262 chomp $pinfo;
263 $pinfo =~ s/, /,/g;
264 $pinfo =~ s/ \| /|/g;
265 return $pinfo;
266 }
267
268 sub get_apt_pinfo {
269 my ($package, $ptype) = @_;
270
271 if ($ptype eq "S") {
272 my $pdata = $source->get($package);
273 return unless $pdata;
274 # First in array is highest version
275 return shift(@$pdata);
276 } else {
277 my $pdata = $cache->get($package);
278 return unless $pdata;
279 if ($show_installed && exists $$pdata{CurrentVer}) {
280 return $$pdata{CurrentVer};
281 } elsif (exists $$pdata{VersionList}) {
282 # First in array is highest version
283 return shift(@{ $$pdata{VersionList} });
284 }
285 }
286 }
287
288 sub get_apt_deps {
289 my ($pinfo, $dtype) = @_;
290 my $delim="";
291 my $deps = "";
292
293 return "" unless $pinfo;
294 for my $dep (@{ $$pinfo{DependsList} }) {
295 next if (get_type(0 + $$dep{DepType}) ne $dtype);
296 if ($deps) {
297 $deps .= $delim;
298 }
299 $deps .= $$dep{TargetPkg}{Name};
300 if (exists $$dep{CompTypeDeb}) {
301 $deps .= " ($$dep{CompTypeDeb} $$dep{TargetVer})"
302 }
303 $delim = ($$dep{CompType} & AptPkg::Dep::Or) ? '|' : ',';
304 }
305 #debug(0, "$dtype --- $deps");
306 return $deps;
307 }
308
309 sub is_installed {
310 my $package = shift;
311
312 my $pinfo = $cache->get($package);
313 return ($pinfo && $$pinfo{CurrentState} eq "Installed");
314 }
315
316 sub get_provides {
317 my $pinfo = shift;
318
319 return unless exists $$pinfo{ProvidesList};
320 my @pset = map($_->{Name}, @{ $$pinfo{ProvidesList} });
321 return @pset if @pset;
322 }
323
324 # Check to see that the version we get matches the one that would
325 # be selected for the rest of the graph.
326 sub check_version {
327 my ($package, $version) = @_;
328 my $pinfo = get_apt_pinfo($package, "");
329 return ($$pinfo{VerStr} eq $version);
330 }
331
332 sub get_rdeps {
333 my ($package, $parent) = @_;
334 my %rdeps;
335
336 my $pinfo = $cache->get($package);
337 return unless ($pinfo && exists $$pinfo{RevDependsList});
338
339 for my $rdep (@{ $$pinfo{RevDependsList} }) {
340 my $pname = $$rdep{ParentPkg}{Name};
341 my $dtype = get_type(0 + $$rdep{DepType});
342
343 next unless grep(/^$dtype$/, @rdtypes);
344 next if ($parent && $pname eq $parent);
345 next unless check_version($pname, $$rdep{ParentVer}{VerStr});
346 next unless (! $show_installed || is_installed($pname));
347 # As long as we don't show versions for rdeps, avoid duplicates
348 # due to double dependencies; for example, gimp has:
349 # Depends: libgimp2.0 (>= 2.4.7), libgimp2.0 (< 2.4.7-z)
350 next if grep(/^$pname$/, @{ $rdeps{$dtype} });
351
352 push(@{ $rdeps{$dtype} }, $pname);
353 }
354
355 return %rdeps;
356 }
357
358 sub get_providers {
359 my $package = shift;
360 my @providers;
361
362 my $pinfo = $cache->get($package);
363 return unless $pinfo && exists $$pinfo{ProvidesList};
364
365 for my $provider (@{ $$pinfo{ProvidesList} }) {
366 my $pname = $$provider{OwnerPkg}{Name};
367 next unless check_version($pname, $$provider{OwnerVer}{VerStr});
368 push(@providers, $pname);
369 }
370 return @providers;
371 }
372
373 sub set_name {
374 my ($plist, $set) = @_;
375 foreach my $s (sort keys %$set) {
376 return $s if ($$set{$s}{plist} eq $plist);
377 }
378 }
379
380 sub first_set_with_package {
381 my ($package, $set) = @_;
382 foreach my $s (sort keys %$set) {
383 if ($$set{$s}{plist} =~ /(^|,)\Q$package\E(,|$)/) {
384 return $s;
385 }
386 }
387 }
388
389 sub get_prior_OR_dep {
390 my $package = shift;
391 if (! exists $pstatus{$package}{OR_seen}) {
392 return first_set_with_package($package, \%OR_dep_list);
393 }
394 }
395
396 sub mark_installed {
397 my ($level, $package) = @_;
398 my $style = "filled";
399
400 $style = "\"setlinewidth(2),$style\"" if ($level == 1);
401 printf("\t\"$package\" [style=${style},fillcolor=honeydew];\n");
402 }
403
404 sub mark_rdep {
405 my $package = shift;
406 printf("\t\"$package\" [style=filled,fillcolor=$rdep_color];\n");
407 }
408
409 sub mark_endpackage {
410 my $package = shift;
411 if (! get_prior_OR_dep($package) && ! exists $pstatus{$package}{rdep}) {
412 printf("\t\"$package\" [shape=diamond];\n");
413 if ($show_installed && is_installed($package)) {
414 mark_installed(0, $package);
415 }
416 }
417 }
418
419 sub print_dot_header {
420 print("digraph \"$requested_package\" {\n");
421 print("\trankdir=LR;\n") unless $do_rotate;
422 print("\tconcentrate=true;\n") if $do_condense;
423 print("\tnode [shape=box];\n");
424 }
425
426 sub print_dot_footer {
427 print("}\n");
428
429 # Show which packages were skipped
430 my @plist;
431 for my $package (sort keys %pstatus) {
432 next unless exists $pstatus{$package}{skipped};
433 push(@plist, $package);
434 }
435 if (@plist) {
436 # Also list excluded packages as comments in the output
437 print("// Excluded dependencies:\n");
438 print("// @plist\n");
439 }
440 }
441
442 sub print_dot_OR_header {
443 my ($atype, $OR_name, $has_inst) = @_;
444
445 printf("\t$OR_name [\n");
446 print("\t\tshape = \"record\"\n");
447 if ($has_inst) {
448 if ($atype eq "P") {
449 print("\t\tstyle = \"rounded,filled\"\n");
450 } else {
451 print("\t\tstyle = \"filled\"\n");
452 }
453 print("\t\tfillcolor = \"honeydew\"\n");
454 } elsif ($atype eq "P") {
455 print("\t\tstyle = \"rounded\"\n");
456 }
457 print("\t\tlabel = \""); # no newline
458 }
459 sub print_dot_OR_footer {
460 print("\"\n\t]\n");
461 }
462
463 sub print_dot_OR_main {
464 my ($package, $seen, $first) = @_;
465
466 print(" | ") unless $first;
467 # Mark packages previously encountered
468 if ($package eq "...") {
469 print("<other> ...");
470 } elsif (exists $pstatus{$package}{unknown}) {
471 print("<$package> ?$package?");
472 } elsif ($seen == 2) {
473 print("<$package> \\{$package\\}");
474 } elsif ($seen == 1) {
475 print("<$package> [$package]");
476 } else {
477 print("<$package> $package");
478 }
479 }
480
481 sub print_alternatives {
482 my ($atype, $OR_name, $OR_has_inst, $OR_pkgs) = @_;
483
484 my $first = 1;
485 print_dot_OR_header($atype, $OR_name, $OR_has_inst);
486 for my $package (split(/,/, $OR_pkgs)) {
487 # Is this package also part of an earlier set of alternatives?
488 my $seen = 0;
489 if (exists $pstatus{$package}{OR_seen}) {
490 $seen = 1;
491 } else {
492 my $t_or = first_set_with_package($package, \%OR_dep_list);
493 if ($atype eq "D") {
494 if (exists $clist{$package}{end} ||
495 exists $pstatus{$package}{ended}) {
496 $seen = 2;
497 } elsif ($OR_dep_list{$t_or}{plist} ne $OR_pkgs) {
498 $seen = 1;
499 }
500 } else {
501 if ($t_or) {
502 $seen = 1;
503 } elsif (exists $pstatus{$package}{done} &&
504 ! exists $pstatus{$package}{ended}) {
505 $seen = 1;
506 } else {
507 # Not seen; mark as end package
508 $seen = 2;
509 }
510 }
511 }
512
513 print_dot_OR_main($package, $seen, $first);
514 $first = 0;
515 }
516 print_dot_OR_footer();
517 }
518
519 sub cjoin {
520 my ($str1, $sep, $str2) = @_;
521 return ($str1 ? ($str1 . $sep) : "") . $str2;
522 }
523 sub cjoin_quoted {
524 my ($str1, $sep, $str2) = @_;
525 return ($str1 ? ("\"$str1\"" . $sep) : "") . "\"$str2\"";
526 }
527
528 sub print_dot_dependency {
529 my $package = shift;
530 my $OR_name = shift;
531 my $prevdep_OR_name = shift;
532 my $dep_package = shift;
533 my $dtype = shift;
534 my $pkgdep = shift;
535 my $rdep = shift;
536 my ($opts, $verdep, $arch_cond, $p_package, $p_dep_package, $prior_OR_dep);
537
538 # Second or later dependency in alternatives: skip unless versioned (see also below)
539 # TODO: make this work better if only some of the alternatives have versioned deps
540 if ($OR_name && (! $with_versions || ! $pkgdep) &&
541 $OR_dep_list{$OR_name}{plist} =~ /,\Q$dep_package\E(,|$)/) {
542 return
543 }
544
545 # No extra options if $dtype = Recommends
546 $opts = cjoin($opts, ",", "color=purple,style=bold") if ($dtype eq "PreDepends");
547 $opts = cjoin($opts, ",", "color=blue") if ($dtype eq "Depends");
548 $opts = cjoin($opts, ",", "style=dotted") if ($dtype eq "Suggests");
549 $opts = cjoin($opts, ",", "color=red") if ($dtype eq "Conflicts");
550 $opts = cjoin($opts, ",", "color=darkgoldenrod,style=bold") if ($dtype eq "Build-Depends");
551 $opts = cjoin($opts, ",", "color=goldenrod") if ($dtype eq "Build-Depends-Indep");
552
553 if ($pkgdep) {
554 ($verdep) = $pkgdep =~ /(\(.*\))/;
555 ($arch_cond) = $pkgdep =~ /(\[.*\])/;
556 # Always include versions for versioned conflicts
557 if ($verdep && ($with_versions || $dtype eq "Conflicts")) {
558 $opts = cjoin($opts, ",", "label=\"$verdep" . ($arch_cond ? "\\n$arch_cond" : "") . "\"");
559 } elsif ($arch_cond && $dtype =~ /Build-Depends/) {
560 $opts = cjoin($opts, ",", "label=\"$verdep\"");
561 }
562 }
563 $opts = $opts ? " [$opts]" : "";
564
565 $p_package = cjoin_quoted($prevdep_OR_name, ":", $package);
566
567 if ($OR_name) {
568 # Make the link to the alternatives to the group, unless we have
569 # to show version or arch condition (see also above)
570 if (($with_versions && $verdep) || $arch_cond) {
571 $p_dep_package = cjoin_quoted($OR_name, ":", $dep_package);
572 } else {
573 $p_dep_package = "\"$OR_name\"";
574 }
575 } else {
576 # Keep all dependencies on a package with the first alternative
577 # For now unless package was previously encountered separately,
578 # in which case we use square brackets in the labels (print_dot_OR_main)
579 $prior_OR_dep = get_prior_OR_dep($dep_package);
580 $p_dep_package = cjoin_quoted($prior_OR_dep, ":", $dep_package);
581 }
582
583 printf("\t$p_package -> $p_dep_package$opts;\n");
584
585 # How can "end" packages that are part of an OR be identified?
586 # For now, marked by using braces in the labels (see print_dot_OR_main)
587 if (exists $clist{$dep_package}{end} && ! $rdep &&
588 ! $OR_name && ! $prior_OR_dep &&
589 ! exists $pstatus{$dep_package}{done}) {
590 if ($dtype ne "Conflicts") {
591 debug(4, "Adding '$dep_package' ($dtype) to ended (list)");
592 $pstatus{$dep_package}{ended} = 1;
593 }
594 $pstatus{$dep_package}{done} = 1;
595 }
596 }
597
598 sub print_rdeps_provides {
599 my $rdep = shift;
600 my $dtype = shift;
601 my $package = shift;
602 my @pset = @_;
603
604 if (! exists $pstatus{$rdep}{prov_rdeps}) {
605 debug(4, "Provider rdeps: $rdep - $dtype - $package - @pset");
606 } else {
607 debug(4, "Provider rdeps: $rdep is already done");
608 return 1
609 }
610 $pstatus{$rdep}{prov_rdeps} = 1;
611
612 my $pinfo = get_apt_pinfo($rdep, "");
613 my $deps = get_apt_deps($pinfo, $dtype);
614 no warnings qw(misc);
615 my $regex = "(\Q" . join("\E|\Q", @pset) . "\E)";
616 use warnings;
617 for my $dep_or (split(/,/, $deps)) {
618 next unless $dep_or =~ /(^|\|)$regex([| ]|$)/;
619
620 my @dset;
621 my $cnt = 0;
622 for my $d (split(/\|/, $dep_or)) {
623 $d =~ s/ .*//; # strip version
624 push(@dset, $d);
625 $cnt++;
626
627 # Packages not in the pset are leaf packages
628 if (! grep(/^$d$/, @pset) && ! exists $pstatus{$d}{ended}) {
629 debug(4, "Provider rdeps: adding '$d' to ended (list)");
630 $pstatus{$d}{ended} = 1;
631 }
632 }
633 return 0 if ($cnt == 1);
634
635 my $pdep_set_name = set_name(join(",", @dset), \%pdep_set_list);
636 if (! $pdep_set_name) {
637 $pdep_set_cnt++;
638 $pdep_set_name = "pds" . $pdep_set_cnt;
639 debug(3, "Provider rdeps: new set '$pdep_set_name' - @dset");
640 my $cnt = 0;
641 for my $p (@dset) {
642 printf("\t\"$pdep_set_name\" -> \"$p\" [style=dotted,label=\"(".++$cnt.")\"];\n");
643 }
644 printf("\t\"$pdep_set_name\" [shape=circle,label=or];\n");
645 $pdep_set_list{$pdep_set_name}{plist} = join(",", @dset);
646 }
647 print_dot_dependency($rdep, "", "", $pdep_set_name, $dtype, "", "");
648 }
649 return 1
650 }
651
652 sub process_deps {
653 my $level = shift;
654 my $package = shift;
655 my $deps = shift;
656 my $dtype = shift;
657 my $prevdep_OR_name = shift;
658
659 return if ($max_depth == 0);
660 debug(3, "$level - dependencies for '$package' ($dtype): $deps");
661
662 for my $dep (split(/,/, $deps)) {
663 my $OR_name;
664 my (@OR_pkgs, @OR_uninst);
665 my ($OR_skip, $OR_has_skip, $OR_has_inst, $OR_has_uninst, $OR_has_other);
666
667 if ($dep =~ /\|/ && ($with_alternatives || $show_installed)) {
668 # Gather information about alternatives
669 for my $dep_or (split(/\|/, $dep)) {
670 my ($dep_package) = $dep_or =~ /^([^ ]+) ?/;
671 if (exists $clist{$dep_package}{skip}) {
672 $pstatus{$dep_package}{skipped} = 1;
673 $OR_has_skip = 1;
674 # Account for installation status
675 if ($show_installed) {
676 if (is_installed($dep_package)) {
677 $OR_has_inst = 1;
678 } else {
679 $OR_has_uninst = 1;
680 }
681 }
682 next;
683 }
684
685 if (! $show_installed) {
686 push(@OR_pkgs, $dep_package);
687 } elsif (is_installed $dep_package) {
688 push(@OR_pkgs, $dep_package);
689 $OR_has_inst = 1;
690 } else {
691 push(@OR_uninst, $dep_package);
692 $OR_has_uninst = 1;
693 }
694 }
695 # If none of the alternatives is installed, show them all
696 if ($show_installed && ! $OR_has_inst) {
697 push(@OR_pkgs, @OR_uninst);
698 $OR_has_uninst = 0;
699 }
700 $OR_skip = 1 unless @OR_pkgs;
701 $OR_has_other = ($OR_has_skip || $OR_has_uninst);
702 push(@OR_pkgs, "...") if $OR_has_other;
703
704 # Create alternative dependency "records" for dot graph
705 if (! $OR_skip && $with_alternatives) {
706
707 # Check if we already have these (exact) alternatives
708 $OR_name = set_name(join(",", @OR_pkgs), \%OR_dep_list);
709 if (! $OR_name) {
710 $OR_dep_cnt++;
711 $OR_name = "alt" . $OR_dep_cnt;
712
713 debug(3, "Alternatives: new set '$OR_name' - @OR_pkgs");
714 for my $dep_package (@OR_pkgs) {
715 # Has this dependency already been
716 # processed as a separate package?
717 if (exists $pstatus{$dep_package}{done} &&
718 ! first_set_with_package($dep_package, \%OR_dep_list) &&
719 ! exists $pstatus{$dep_package}{OR_seen}) {
720 $pstatus{$dep_package}{OR_seen} = 1;
721 }
722 }
723
724 $OR_dep_list{$OR_name}{plist} = join(",", @OR_pkgs);
725 $OR_dep_list{$OR_name}{has_inst} = $OR_has_inst;
726 } else {
727 debug(3, "Alternatives: matches existing set '$OR_name'");
728 }
729 }
730 }
731
732 if ($OR_skip) {
733 debug(3, "Alternatives: skipping ('$dep')");
734 next;
735 }
736
737 for my $dep_or (split(/\|/, $dep)) {
738 my ($dep_package) = $dep_or =~ /^([^ ]+) ?/;
739 debug(3, "Processing dependency '$package'->'$dep_package'");
740
741 if ($show_installed && $OR_name &&
742 ! grep(/^$dep_package$/, @OR_pkgs)) {
743 next;
744 }
745
746 # Note: for build dependencies pkgdep can include architecture conditions
747 my ($pkgdep) = $dep_or =~ m/ (.*)/;
748
749 if (exists $clist{$dep_package}{skip}) {
750 $pstatus{$dep_package}{skipped} = 1;
751 next;
752 } elsif ($dtype eq "Conflicts" && ! $with_vconflicts && $pkgdep) {
753 # Include only unversioned conflicts
754 next;
755 }
756 print_dot_dependency($package, $OR_name, $prevdep_OR_name, $dep_package, $dtype, $pkgdep);
757
758 if (exists $pstatus{$dep_package}{done} ||
759 exists $clist{$dep_package}{end}) {
760 # do nothing
761 } else {
762 # Recurse through dependencies, except for Suggests
763 # and Conflicts
764 if ($dtype eq "Suggests") {
765 if (! exists $pstatus{$dep_package}{done}) {
766 debug(4, "Adding '$dep_package' ($dtype) to ended");
767 $pstatus{$dep_package}{ended} = 1;
768 $pstatus{$dep_package}{leaf} = 1;
769 }
770 } elsif ($dtype eq "Conflicts") {
771 if (! exists $pstatus{$dep_package}{done}) {
772 $pstatus{$dep_package}{leaf} = 1;
773 }
774 } else {
775 if ($level < $max_depth) {
776 process_package($level + 1, $dep_package, $OR_name, "");
777 } else {
778 debug(4, "Adding '$dep_package' ($dtype) to ended (max)");
779 $pstatus{$dep_package}{ended} = 1;
780 }
781 }
782 }
783
784 last unless $with_alternatives;
785 }
786 }
787 }
788
789 sub pre_process_deps {
790 my $level = shift;
791 my $package = shift;
792 my $prevdep_OR_name = shift;
793 my $pinfo = shift;
794
795 my $dtype = "";
796 my $delim = "";
797 my $deps = "";
798
799 return unless exists $$pinfo{DependsList};
800 for my $dep (@{ $$pinfo{DependsList} }) {
801 my $new_type = get_type(0 + $$dep{DepType});
802 if ($new_type ne $dtype) {
803 if ($deps) {
804 process_deps($level, $package, $deps, $dtype, $prevdep_OR_name);
805 $delim = "";
806 $deps = "";
807 }
808 $dtype = $new_type;
809 }
810 next unless grep(/^$dtype$/, @dtypes);
811 if ($deps) {
812 $deps .= $delim;
813 }
814 $deps .= $$dep{TargetPkg}{Name};
815 if (exists $$dep{CompTypeDeb}) {
816 $deps .= " ($$dep{CompTypeDeb} $$dep{TargetVer})"
817 }
818 $delim = ($$dep{CompType} & AptPkg::Dep::Or) ? '|' : ',';
819 }
820 # Ensure the dependency type encountered last also gets processed
821 if ($deps) {
822 process_deps($level, $package, $deps, $dtype, $prevdep_OR_name);
823 }
824 }
825
826 sub pre_process_bdeps {
827 my ($level, $package, $pinfo) = @_;
828
829 if ($ARCH eq "all") {
830 # $pinfo contains output from apt-cache (see get_bdeps_all)
831 for my $dtype (qw/Build-Depends Build-Depends-Indep/) {
832 my ($deps) = $pinfo =~ /^$dtype: (.*)/;
833 next unless $deps;
834 process_deps($level, $package, $deps, $dtype, "");
835 }
836 } else {
837 # $pinfo is a pointer to AptPkg data
838 return unless exists $$pinfo{BuildDepends};
839 for my $dtype (keys %{ $$pinfo{BuildDepends} }) {
840 my $deps = "";
841 for my $dep (@{ $$pinfo{BuildDepends}{$dtype} }) {
842 if ($deps) {
843 $deps .= ",";
844 }
845 $deps .= @$dep[0];
846 if (@$dep[1]) {
847 $deps .= " (@$dep[1] @$dep[2])"
848 }
849 }
850 process_deps($level, $package, $deps, $dtype, "");
851 }
852 }
853 }
854
855 sub process_virtual {
856 my $level = shift;
857 my $package = shift;
858 my $prevdep_OR_name = shift;
859 my $ptype = shift;
860 my @providers = @_; # must be last
861 my $prior_OR_dep;
862 my (@OR_pkgs, @OR_uninst);
863 my ($OR_name, $OR_has_inst, $OR_has_uninst);
864
865 if (exists $pstatus{$package}{done}) {
866 debug(3, "$level - virtual package '$package' already done");
867 return;
868 } elsif ($level == 1) {
869 debug(3, "$level - '@providers' provides '$package'");
870 } else {
871 debug(3, "$level - '$package' provided by: @providers");
872 }
873
874 my $p_package = cjoin_quoted($prevdep_OR_name, ":", $package);
875
876 my $prov_cnt = @providers;
877 if ($prov_cnt == 1) {
878 my $provider = pop(@providers);
879 if ($ptype eq "V" && exists $pstatus{$provider}{done}) {
880 debug(3, "$level - '$package' has no other providers");
881 return;
882 } elsif ($level != 1 && exists $clist{$provider}{skip}) {
883 $pstatus{$provider}{skipped} = 1;
884 } else {
885 $prior_OR_dep = get_prior_OR_dep($provider);
886 my $p_provider = cjoin_quoted($prior_OR_dep, ":", $provider);
887 if ($level == 1 && ! $show_rdeps) {
888 printf("\t$p_provider -> $p_package [arrowhead=inv,color=green];\n");
889 } else {
890 printf("\t$p_package -> $p_provider [dir=back,arrowtail=inv,color=green];\n");
891 }
892
893 if (exists $clist{$provider}{end} && ! $prior_OR_dep &&
894 ! exists $pstatus{$provider}{done}) {
895 debug(4, "Adding '$provider' (provides) to ended (list)");
896 $pstatus{$provider}{ended} = 1;
897 $pstatus{$provider}{done} = 1;
898 }
899
900 # Process as leaf to show other providers
901 if ($level == 1 && ! exists $pstatus{$package}{done}) {
902 process_package(0, $package, "", "V");
903 }
904
905 # Recurse to get dependencies for providing package
906 $pstatus{$package}{done} = 1;
907 if (! exists $pstatus{$provider}{done} && $ptype ne "L") {
908 process_package($level + 1, $provider, "", "");
909 }
910 }
911 } else {
912 # Note: if there are multiple providing packages, we do
913 # not recurse into them!
914 for my $provider (@providers) {
915 if ($show_installed) {
916 if (is_installed($provider)) {
917 push(@OR_pkgs, $provider);
918 $OR_has_inst = 1;
919 } else {
920 push(@OR_uninst, $provider);
921 $OR_has_uninst = 1;
922 }
923 } else {
924 push(@OR_pkgs, $provider);
925 }
926 }
927 if ($show_installed && ! @OR_pkgs) {
928 # If none of the alternatives is installed, show them all
929 push(@OR_pkgs, @OR_uninst);
930 $OR_has_uninst = 0;
931 }
932 push(@OR_pkgs, "...") if $OR_has_uninst;
933
934 # Only show multiple providing packages if there are $max_providers
935 # or less, or when restricted to installed packages
936 if ($prov_cnt < $max_providers || ($show_installed && $OR_has_inst)) {
937 # Check if we already have these (exact) alternative providers
938 $OR_name = set_name(join(",", @OR_pkgs), \%OR_virt_list);
939 if (! $OR_name) {
940 $OR_virt_cnt++;
941 $OR_name = "virt" . $OR_virt_cnt;
942
943 debug(3, "Providers: new set '$OR_name' - @OR_pkgs");
944 $OR_virt_list{$OR_name}{plist} = join(",", @OR_pkgs);
945 $OR_virt_list{$OR_name}{has_inst} = $OR_has_inst;
946 } else {
947 debug(3, "Providers: matches existing set '$OR_name'");
948 }
949
950 # Print the arrow now; the record itself is printed later
951 printf("\t$p_package -> $OR_name [dir=back,arrowtail=inv,color=green];\n");
952 } else {
953 printf("\t$p_package -> \"Pr_$package\" [label=\"-$prov_cnt-\",dir=back,arrowtail=inv,color=green];\n");
954 printf("\t\"Pr_$package\" [label=\"...\",style=rounded];\n");
955 }
956 }
957
958 # Green arrow sufficiently identifies virtual package that is part of alternatives
959 if (! $prevdep_OR_name || exists $pstatus{$package}{OR_seen}) {
960 printf("\t\"$package\" [shape=octagon];\n") unless ($ptype eq "V");
961 }
962 $pstatus{$package}{done} = 1;
963 }
964
965 sub process_missing {
966 my $package = shift;
967
968 my $prior_OR_dep = get_prior_OR_dep($package);
969 if (! $prior_OR_dep) {
970 printf("\t\"$package\" [style=filled,fillcolor=oldlace];\n");
971 } else {
972 $pstatus{$package}{unknown} = 1;
973 }
974 }
975
976 sub find_rdeps {
977 my $level = shift;
978 my $package = shift;
979 my $parent = shift;
980 my @provides = @_;
981 my $has_max = 0;
982
983 info(2, "Level $level: processing reverse dependencies for $package");
984 $pstatus{$package}{rdep} = 1;
985
986 my @recurse_rdeps;
987 my %rdeps = get_rdeps($package, $parent);
988 for my $dtype (sort keys %rdeps) {
989 my @rdeps = @{ $rdeps{$dtype} };
990 my $cnt = @rdeps;
991 if ($cnt > 0) {
992 debug(4, "$level - " . ($show_installed ? "installed " : "") . "$dtype rdeps for '$package' ($cnt): @rdeps");
993 }
994
995 my $opts;
996 if ($level < -1 && $cnt > $max_rdeps) {
997 $opts = "color=purple,style=bold" if ($dtype eq "PreDepends");
998 $opts = "color=blue" if ($dtype eq "Depends");
999 $opts = "" if ($dtype eq "Recommends");
1000 $opts = " [label=\"-$cnt-\",$opts]"; # FIXME if dtype=Recommends ?
1001 printf("\t\"RD_$package\" -> \"$package\" $opts;\n");
1002 $has_max = 1;
1003 next;
1004 }
1005
1006 push(@recurse_rdeps, @rdeps);
1007 for my $rdep (@rdeps) {
1008 if (@provides &&
1009 print_rdeps_provides($rdep, $dtype, $package, ($parent, @provides))) {
1010 next;
1011 }
1012
1013 if (! exists $pstatus{$rdep}{done}) {
1014 debug(4, "$level - adding reverse dependency '$rdep'->'$package'");
1015 print_dot_dependency($rdep, "", "", $package, $dtype, "", 1);
1016 } else {
1017 debug(4, "$level - package '$rdep' is already done");
1018 }
1019 }
1020 }
1021
1022 for my $rdep (@recurse_rdeps) {
1023 if (! exists $pstatus{$rdep}{rdep}) {
1024 if (! exists $pstatus{$rdep}{done}) {
1025 mark_rdep($rdep);
1026 }
1027 next unless ($level > -$rdeps_depth);
1028 if ($level == -1) {
1029 find_rdeps($level - 1, $rdep, $package);
1030 } else {
1031 find_rdeps($level - 1, $rdep, "");
1032 }
1033 }
1034 }
1035
1036 if ($has_max) {
1037 printf("\t\"RD_$package\" [label=\"...\",style=\"rounded,filled\",fillcolor=$rdep_color];\n");
1038 }
1039 }
1040
1041 sub process_package {
1042 my $level = shift;
1043 my $package = shift;
1044 my $prevdep_OR_name = shift;
1045 my $ptype = shift;
1046 my $pinfo;
1047 my $pdata = $cache->get($package);
1048 my $size=0;
1049
1050 info(2, "Level $level: processing $package" . ($ptype ? " ($ptype)" : ""));
1051
1052 # something installed?
1053 if (exists $$pdata{CurrentVer}) {
1054 $size=$pdata->{CurrentVer}->{InstalledSize};
1055 $total_size += $size;
1056 $size=$pdata->{CurrentVer}->{Size};
1057 $download_size += $size;
1058 info (2,"size of $package: $size / total size: $total_size / download size: $download_size");
1059 }else {
1060 # is there a list of versions available in cache?
1061 if (exists $$pdata{VersionList}) {
1062 # just use first version
1063 my $first_version=shift(@{ $$pdata{VersionList} });
1064 $size=$first_version->{InstalledSize};
1065 $total_size += $size;
1066 $size=$first_version->{Size};
1067 $download_size += $size;
1068 info (2,"size of first $package: $size / total size: $total_size / download site: $download_size");
1069 } else {
1070 info (2,"no size available: $package");
1071 }
1072 }
1073
1074 if ($ptype ne "L" && exists $pstatus{$package}{ended}) {
1075 debug(4, "Removing '$package' from ended");
1076 delete $pstatus{$package}{ended};
1077 }
1078
1079 if ($ptype eq "S" && $ARCH eq "all") {
1080 # AptPkg does not expose architecture conditions, so use apt-cache
1081 $pinfo = get_bdeps_all($package);
1082 } else {
1083 $pinfo = get_apt_pinfo($package, $ptype);
1084 info(3, "Using package version: " .
1085 (($ptype eq "S") ? $$pinfo{Version} : $$pinfo{VerStr}))
1086 if $pinfo;
1087 }
1088 if ($ptype eq "S" || $ptype eq "B") {
1089 if ($pinfo) {
1090 print_dot_header();
1091 } else {
1092 error("no dependency info found for '$package'");
1093 }
1094 }
1095 if (! $pinfo) {
1096 my @providers = get_providers($package);
1097 if (@providers) {
1098 # For leaf packages we need to check if it was an alternative
1099 $prevdep_OR_name = get_prior_OR_dep($package) if ($ptype eq "L");
1100
1101 process_virtual($level, $package, $prevdep_OR_name, $ptype, @providers);
1102 } else {
1103 process_missing($package);
1104 }
1105 }
1106
1107 # Mark as done now to prevent recursion loops
1108 $pstatus{$package}{done} = 1;
1109
1110 return if ($ptype eq "L" || $ptype eq "V");
1111
1112 # Recurse through dependencies
1113 if ($pinfo) {
1114 if ($ptype eq "S") {
1115 pre_process_bdeps($level, $package, $pinfo);
1116 } else {
1117 pre_process_deps($level, $package, $prevdep_OR_name, $pinfo);
1118 }
1119 }
1120
1121 # Provides and reverse dependencies for the requested package
1122 if ($level == 1 && ($with_provides || $show_rdeps)) {
1123 my @provides = get_provides($pinfo);
1124 if (! $with_provides || ! @provides) {
1125 if ($show_rdeps) {
1126 debug(4, "Find rdeps for the package");
1127 find_rdeps(-1, $package);
1128 }
1129 } elsif (@provides) {
1130 # Virtual packages
1131 for my $provided (@provides) {
1132 process_virtual($level, $provided, "", "L", ($package));
1133 }
1134 # Installed reverse dependencies for the package and its provides
1135 if ($show_rdeps) {
1136 debug(4, "Find rdeps for the package & its provides");
1137 for my $p ($package, @provides) {
1138 find_rdeps(-1, $p, $package, @provides);
1139 }
1140 }
1141 }
1142 }
1143
1144 if ($show_installed && is_installed($package) &&
1145 ! get_prior_OR_dep $package) {
1146 mark_installed($level, $package);
1147 } elsif ($level == 1) {
1148 printf("\t\"$package\" [style=\"setlinewidth(2)\"]\n");
1149 }
1150
1151 debug(3, "Level $level: processing $package" . ($ptype ? " ($ptype)" : "") . " - done");
1152 }
1153
1154 ### MAINLINE ###
1155
1156 # Import lists to limit processing:
1157 # - "skip" packages are completely ignored: nothing is displayed
1158 # - "end" packages are displayed and marked as such, but we don't recurse
1159 # to determine their dependencies
1160 if (! $show_all) {
1161 if (-r $skiplist) {
1162 info(3, "Using list of 'skip' packages from $skiplist");
1163 if (! $no_skip){
1164 import_list($skiplist, "skip");
1165 } else {
1166 # Change skip packages to end packages
1167 import_list($skiplist, "end");
1168 }
1169 } else {
1170 my $file;
1171 for $file ("$HOME/.debtree/skiplist", "/etc/debtree/skiplist") {
1172 if (-r $file) {
1173 info(3, "Using list of 'skip' packages from $file");
1174 if (! $no_skip) {
1175 import_list($file, "skip");
1176 } else {
1177 # Change skip packages to end packages
1178 import_list($file, "end");
1179 }
1180 last;
1181 }
1182 }
1183 }
1184 if (-r $endlist) {
1185 info(3, "Using list of 'end' packages from $endlist");
1186 import_list($endlist, "end");
1187 } else {
1188 my $file;
1189 for $file ("$HOME/.debtree/endlist", "/etc/debtree/endlist") {
1190 if (-r $file) {
1191 info(3, "Using list of 'end' packages from $file");
1192 import_list($file, "end");
1193 last;
1194 }
1195 }
1196 }
1197 }
1198
1199 # ptype B/S indicates "start" binary/source package
1200 process_package(1, $requested_package, "", $ptype);
1201
1202 # For packages we did not yet recurse through, check if they are virtual
1203 # packages as we want to show the providing package(s)
1204 info(2, "Processing leaf packages");
1205 for my $package (sort keys %pstatus) {
1206 next unless exists $pstatus{$package}{leaf};
1207 if (! exists $pstatus{$package}{done}) {
1208 process_package(0, $package, "", "L");
1209 }
1210 }
1211
1212 info(2, "Final processing for graph");
1213 # Print record definitions for alternatives
1214 for my $OR_name (sort keys %OR_dep_list) {
1215 print_alternatives("D", $OR_name, $OR_dep_list{$OR_name}{has_inst}, $OR_dep_list{$OR_name}{plist});
1216 }
1217
1218 # Print record definitions for alternative provides
1219 for my $OR_name (sort keys %OR_virt_list) {
1220 print_alternatives("P", $OR_name, $OR_virt_list{$OR_name}{has_inst}, $OR_virt_list{$OR_name}{plist});
1221 }
1222
1223 # Set shape to diamond for packages whose dependencies we did not
1224 # recurse into
1225 for my $package (sort keys %pstatus) {
1226 next unless exists $pstatus{$package}{ended};
1227 mark_endpackage($package);
1228 }
1229
1230 print_dot_footer();
1231
1232 # does it make sense to show these numbers for rdeps?
1233 if (! $show_rdeps) {
1234 printf("// total size of all shown packages: $total_size\n");
1235 printf("// download size of all shown packages: $download_size\n");
1236 }