[SCM] Debian package checker branch, infra-513663, updated. 2.5.0-rc1-131-g546475c
The following commit has been merged in the infra-513663 branch:
commit 546475cfa7fa04ea3a8379989a616e28b36ce4eb
Author: Niels Thykier <niels@thykier.net>
Date: Sun Apr 10 23:05:22 2011 +0200
Detect circular dependencies between binaries from the same src
Using Tarjan's algorithm to find the strongly connected packages.
DepMap was not used because while it can find circular
dependencies, it cannot tell how many or which package belong to
which "circle".
diff --git a/checks/circular-deps b/checks/circular-deps
new file mode 100644
index 0000000..18b11b0
--- /dev/null
+++ b/checks/circular-deps
@@ -0,0 +1,150 @@
+# circular-deps -- lintian check script -*- perl -*-
+
+# Copyright (C) 2011 Niels Thykier <niels@thykier.net>
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program. If not, you can find it on the World Wide
+# Web at http://www.gnu.org/copyleft/gpl.html, or write to the Free
+# Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
+# MA 02110-1301, USA.
+
+package Lintian::circular_deps;
+use strict;
+use warnings;
+
+use Lintian::Tags qw(tag);
+
+sub run {
+
+my $pkg = shift;
+my $type = shift;
+my $info = shift;
+my $proc = shift;
+my $group = shift;
+
+## To find circular dependencies, we will first generate
+## Strongly Connected Components using Tarjan's algorithm
+##
+## We are not using DepMap, because it cannot tell how the
+## circles are made - only that there exists at least 1
+## circle.
+
+# The packages a.k.a. nodes
+my @nodes = ();
+my %edges = ();
+my $sccs;
+
+foreach my $proc ($group->get_processables('binary')) {
+ my $pname = $proc->pkg_name;
+ my $relation = $proc->info->relation('strong');
+ my $deps = [];
+ foreach my $oproc ($group->get_processables('binary')) {
+ my $opname = $oproc->pkg_name;
+ next if $opname eq $pname;
+ push @$deps, $opname if $relation->implies($opname);
+ }
+ if (scalar @$deps > 0) {
+ # it depends on another package - it can cause
+ # a circular dependency
+ push @nodes, $pname;
+ $edges{$pname} = $deps;
+ }
+}
+
+# Bail now if we do not have at least two packages depending
+# on some other package from this source.
+return if scalar @nodes < 2;
+
+$sccs = Lintian::circular_deps::Graph->new(\@nodes, \%edges)->tarjans();
+
+foreach my $comp (@$sccs) {
+ # It takes two to tango... erh. make a circular dependency.
+ next if scalar @$comp < 2;
+ tag 'intra-source-package-circular-dependency', sort @$comp;
+}
+
+
+}
+
+## Encapsulate Tarjan's algorithm in an class/object to keep
+## the run sub somewhat sane.
+package Lintian::circular_deps::Graph;
+
+sub new{
+ my ($type, $nodes, $edges) = @_;
+ my $self = { nodes => $nodes, edges => $edges};
+ bless $self, $type;
+ return $self;
+}
+
+sub tarjans {
+ my ($self) = @_;
+ my $nodes = $self->{nodes};
+ $self->{index} = 0;
+ $self->{scc} = [];
+ $self->{stack} = [];
+ $self->{on_stack} = {};
+ # The information for each node:
+ # $self->{node_info}->{$node}->[X], where X is:
+ # 0 => index
+ # 1 => low_index
+ $self->{node_info} = {};
+ foreach my $node (@$nodes) {
+ $self->_tarjans_sc($node)
+ unless defined $self->{node_info}->{$node};
+ }
+ return $self->{scc};
+}
+
+sub _tarjans_sc{
+ my ($self, $node) = @_;
+ my $index = $self->{index};
+ my $stack = $self->{stack};
+ my $ninfo = [$index, $index];
+ my $on_stack = $self->{on_stack};
+ $self->{node_info}->{$node} = $ninfo;
+ $index++;
+ $self->{index} = $index;
+ push @$stack, $node;
+ $on_stack->{$node} = 1;
+ foreach my $neighbour (@{ $self->{edges}->{$node} }){
+ my $nb_info;
+ $nb_info = $self->{node_info}->{$neighbour};
+ if (!defined $nb_info){
+ # First time visit
+ $self->_tarjans_sc($neighbour);
+ # refresh $nb_info
+ $nb_info = $self->{node_info}->{$neighbour};
+ # min($node.low_index, $neigh.low_index)
+ $ninfo->[1] = $nb_info->[1] if $nb_info->[1] < $ninfo->[1];
+ } elsif (exists $on_stack->{$neighbour}) {
+ # Node is in this component
+ # min($node.low_index, $neigh.index)
+ $ninfo->[1] = $nb_info->[0] if $nb_info->[0] < $ninfo->[1];
+ }
+ }
+ if ($ninfo->[0] == $ninfo->[1]){
+ # the "root" node - create the SSC.
+ my $component = [];
+ my $scc = $self->{scc};
+ my $elem = '';
+ do {
+ $elem = pop @$stack;
+ delete $on_stack->{$elem};
+ push @$component, $elem;
+ } until $node eq $elem;
+ push @$scc, $component;
+ }
+}
+
+1;
diff --git a/checks/circular-deps.desc b/checks/circular-deps.desc
new file mode 100644
index 0000000..4280097
--- /dev/null
+++ b/checks/circular-deps.desc
@@ -0,0 +1,24 @@
+Check-Script: circular-deps
+Author: Niels Thykier <niels@thykier.net>
+Abbrev: cdeps
+# This is a source check, so we only calculate the dependency
+# graphs once.
+Type: source
+Needs-info: fields
+Info: This script checks for circular dependencies between packages
+ built from the same source.
+
+Tag: intra-source-package-circular-dependency
+Severity: normal
+Certainty: certain
+Info: The listed packages from the same source circularly depend
+ (or pre-depend) on each other. This makes it difficult for tools
+ to properly handle install/upgrade sequences. Furthermore this
+ complicates automated removal of unused packages.
+ .
+ If possible, consider removing or reducing one of the depends.
+ .
+ Note: This check is limited to packages created from the same
+ source package. Full circular dependencies between bianries from
+ different source packages is beyond the scope of Lintian.
+Ref: policy 7.2
diff --git a/t/tests/circular-deps/debian/debian/control.in b/t/tests/circular-deps/debian/debian/control.in
new file mode 100644
index 0000000..5c43b3e
--- /dev/null
+++ b/t/tests/circular-deps/debian/debian/control.in
@@ -0,0 +1,98 @@
+Source: {$srcpkg}
+Priority: extra
+Section: {$section}
+Maintainer: {$author}
+Standards-Version: {$standards_version}
+Build-Depends: debhelper (>= 7.0.50~)
+
+Package: root
+Architecture: all
+Depends: $\{misc:Depends\}, c1-a, c1-c, c2-b
+Description: {$description} - root
+ This is a test package designed to exercise some feature or tag of
+ Lintian. It is part of the Lintian test suite and may do very odd
+ things. It should not be installed like a regular package.
+ .
+ root.
+
+Package: leaf
+Architecture: all
+Depends: $\{misc:Depends\}
+Description: {$description} - leaf
+ This is a test package designed to exercise some feature or tag of
+ Lintian. It is part of the Lintian test suite and may do very odd
+ things. It should not be installed like a regular package.
+ .
+ leaf.
+
+Package: disconnected
+Architecture: all
+Depends: $\{misc:Depends\}
+Description: {$description} - dis
+ This is a test package designed to exercise some feature or tag of
+ Lintian. It is part of the Lintian test suite and may do very odd
+ things. It should not be installed like a regular package.
+ .
+ disconnected.
+
+
+Package: c1-a
+Architecture: all
+Depends: $\{misc:Depends\}, c1-b, leaf
+Description: {$description} - c1-a
+ This is a test package designed to exercise some feature or tag of
+ Lintian. It is part of the Lintian test suite and may do very odd
+ things. It should not be installed like a regular package.
+ .
+ c1-a.
+
+Package: c1-b
+Architecture: all
+Depends: $\{misc:Depends\}, c1-c
+Description: {$description} - c1-b
+ This is a test package designed to exercise some feature or tag of
+ Lintian. It is part of the Lintian test suite and may do very odd
+ things. It should not be installed like a regular package.
+ .
+ c1-b.
+
+Package: c1-c
+Architecture: all
+Depends: $\{misc:Depends\}, c1-a, leaf
+Description: {$description} - c1-c
+ This is a test package designed to exercise some feature or tag of
+ Lintian. It is part of the Lintian test suite and may do very odd
+ things. It should not be installed like a regular package.
+ .
+ c1-c.
+
+Package: c2-a
+Architecture: all
+Depends: $\{misc:Depends\}, c2-b, c2-c, leaf
+Description: {$description} - c2-a
+ This is a test package designed to exercise some feature or tag of
+ Lintian. It is part of the Lintian test suite and may do very odd
+ things. It should not be installed like a regular package.
+ .
+ c2-a.
+
+Package: c2-b
+Architecture: all
+Depends: $\{misc:Depends\}, c2-a, c2-c
+Description: {$description} - c2-b
+ This is a test package designed to exercise some feature or tag of
+ Lintian. It is part of the Lintian test suite and may do very odd
+ things. It should not be installed like a regular package.
+ .
+ c2-b.
+
+Package: c2-c
+Architecture: all
+Depends: $\{misc:Depends\}, c2-a, c2-b, leaf
+Description: {$description} - c2-c
+ This is a test package designed to exercise some feature or tag of
+ Lintian. It is part of the Lintian test suite and may do very odd
+ things. It should not be installed like a regular package.
+ .
+ c2-c.
+
diff --git a/t/tests/circular-deps/debian/debian/rules b/t/tests/circular-deps/debian/debian/rules
new file mode 100644
index 0000000..644131e
--- /dev/null
+++ b/t/tests/circular-deps/debian/debian/rules
@@ -0,0 +1,9 @@
+#!/usr/bin/make -f
+
+%:
+ dh $@
+
+override_dh_installdocs:
+ for P in $$(dh_listpackages) ; do \
+ dh_installdocs -p$$P some-doc.txt || exit 1 ;\
+ done
diff --git a/t/tests/basic-3.0-native/debian/README b/t/tests/circular-deps/debian/some-doc.txt
similarity index 100%
copy from t/tests/basic-3.0-native/debian/README
copy to t/tests/circular-deps/debian/some-doc.txt
diff --git a/t/tests/circular-deps/desc b/t/tests/circular-deps/desc
new file mode 100644
index 0000000..ab18235
--- /dev/null
+++ b/t/tests/circular-deps/desc
@@ -0,0 +1,5 @@
+Testname: circular-deps
+Sequence: 6000
+Version: 1.0
+Description: Test for circular dependencies
+#Test-For: intra-source-package-circular-dependency
diff --git a/t/tests/circular-deps/tags b/t/tests/circular-deps/tags
new file mode 100644
index 0000000..fae1932
--- /dev/null
+++ b/t/tests/circular-deps/tags
@@ -0,0 +1,2 @@
+W: circular-deps source: intra-source-package-circular-dependency c1-a c1-b c1-c
+W: circular-deps source: intra-source-package-circular-dependency c2-a c2-b c2-c
--
Debian package checker
Reply to: