Forwarded message from Roman Hodek, 11:33:06 Fri,7 November 1997
--Bc966T3WbB
Content-Type: message/rfc822
Content-Transfer-Encoding: 7bit
Received: from tiamat.datasync.com (srivasta@tiamat.datasync.com [205.216.83.252])
by tiamat.datasync.com (8.8.8/8.8.8/Debian/GNU) with ESMTP id FAA08641
for <srivasta@tiamat.datasync.com>; Fri, 7 Nov 1997 05:55:19 -0600
Received: from mail.datasync.com
by tiamat.datasync.com (fetchmail-4.3.2 POP3 run by srivasta)
for <srivasta@tiamat.datasync.com> (single-drop); Fri Nov 7 05:55:20 1997
Received: by osh5 for srivasta
(with Cubic Circle's cucipop (v1.21 1997/08/10) Fri Nov 7 05:55:21 1997)
X-From_: rnhodek@immd2.informatik.uni-erlangen.de Fri Nov 7 05:33:23 1997
Received: from faui21.informatik.uni-erlangen.de (root@faui21.informatik.uni-erlangen.de [131.188.32.21]) by osh5.datasync.com (8.8.7/Datasync) with SMTP id FAA28274 for <srivasta@datasync.com>; Fri, 7 Nov 1997 05:33:21 -0600
Received: from faui22c.informatik.uni-erlangen.de by immd2.informatik.uni-erlangen.de with SMTP (5.64+/7.3h-FAU)
id AA24464; Fri, 7 Nov 97 12:32:15 +0100
Message-Id: <9711071132.AA24464@faui21.informatik.uni-erlangen.de>
In-Reply-To: <[🔎] 87oh3xab3y.fsf@tiamat.datasync.com> (srivasta@datasync.com)
Reply-To: Roman.Hodek@informatik.uni-erlangen.de
X-Filter: mailagent [version 3.0 PL58] for srivasta@tiamat.datasync.com
From: Roman Hodek <rnhodek@faui22c.informatik.uni-erlangen.de>
To: srivasta@datasync.com
Subject: Re: Another little bug in pkg-order
Date: Fri, 7 Nov 1997 11:33:06 GMT
Hi Manoj!
> Right.
Ok.
> Hmm. The results are returned in the ' _Results' object associated
> with each packaeg. result_as_string just collates all results for
> all packages as a giant string, which can then be printed out. There
> are other routines that merely count the errors (caled, for some
> reason, check); I think you should look at pkg-order where I use the
> call. So, do the depends as above, and then call check to see if
> there was an error. What you do then is upto you ;-)
Hmm.. I think just the number of errors isn't of much use for me,
because if there is some error, I also need the info what caused it to
solve it somehow...
But maybe I could gain some speed if I don't request the result string
and parse it thereafter :-) Are the _Result objects somehow part of
the interface (i.e. publically visible), so that I can access them
directly? By looking at the code, I think I have to do something like:
foreach $name ( keys %$installed ) {
next if $name =~ /\s+_/; # skip special things
foreach $type (...some types...) { # (*)
foreach $category ('Unknown', $type eq 'Conflict'?'Failed':'Conflict') {
$array = $installed->{$name}->{' _Results'}->{'Result'}->{$category}->{$type};
foreach (@$array) {
push( @{$result{$type}->{$name}}, $_ );
}
}
}
}
(The two foreach's at (*) are for me to loop over interesting types
and categories. %result is where I collect the results for further
processing.)
> Only informally (observed behaviour when calling dpkg manually).
That should be ok...
> Yes, but all these hueristics are hard ;-)
It's not that much heuristics, IMHO, but a few strange processing
steps that result from the strange problem :-) But it's not unlikely
that there is a better/cleaner solution.
> Umm, your old libc5 packages are of type A, you new libc5 packages
> are type C, and your new libc6 packages are type B.
You're right... Guess I mixed up the mapping of packages to letters so
that I didn't see that your description applies :-)
BTW, I've noticed that you (still) use 'tsort' for doing the actual
ordering of packages, because I've seen an error message from tsort
about a circular dependency :-) It was libpam and pam-util (maybe I
misspelled the names...) that depend on each other...
I can remember that you've written somewhere in the docs that you want
to replace tsort by some Perl code... The algorithm itself for
topological sorting is rather easy:
Assume you have a DAG. Then first calculate the indegree (number of
incoming edges) of each vertex. Then make a queue of to-be-processed
nodes, initialized with all nodes that indegree 0. Then take out a
node of the queue one by one, assign it the next order number, and
reduce the indegree of each target node of the node. If an indegree
becomes 0, put that node onto the todo list.
In Perl, this could look like the following. I assume that all nodes
are represented as a hash, that has a named field 'targets', which is
a list of target nodes.
# first, calculate indegrees
foreach $node ( keys %graph ) {
foreach $target ( @{$graph{$node}->{'targets'}} ) {
$graph{$target}->{'indegree'}++;
}
}
# init todo list with nodes that have indegree 0
foreach $node ( keys %graph ) {
push( @todo, $node ) if !$graph{$node}->{'indegree'};
}
# now process targets of each node in todo list
$next_order = 0;
while( $node = shift(@todo) ) {
$graph{$node}->{'order'} = $next_order++;
push( @ordered_list, $node );
# for each target, reduce indegree and append to todo queue if it
# becomes 0
foreach $target ( @{$graph{$node}->{'targets'}} ) {
push( @todo, $target ) if --($graph{$target}->{'indegree'}) == 0;
}
}
This produces the result in two representations: First each node gets
a new field 'order' that contains the order number. Additionally,
@ordered_list is a list that already contains the nodes in appropriate
topological order. Choose the representation that better fits your
needs... I guess it's @ordered_list. Then you can also omit the
assignment of $node->{'order'} and the $next_order variable.
I haven't looked at pkg-order how the edges are actually stored, but
you should be able to adapt the code above to pkg-order's data
structures.
The problem about the simple algorithm is that it doesn't detect
cycles, and in pratical applications we could have cycles :-(
(libpam!) A cycles shows up as nodes that have indegree > 0 after the
todo list becomes empty. It can be resolved by deleting one of the
edges that make up the cycle. (This is the same what tsort does.) But
of course this can end up in wrong results, as one dependency edge has
been deleted.
The code below tries to fix cycles that show up after ordering. It
looks for an edge that ends in a node with indegree == 1, so that this
node can be moved on todo after deleting the edge and thus its
indegree became 0. If no such node can be found, I simply let the
program die. Don't know if that can happen...
foreach $node ( keys %graph ) {
# if some indegree is still > 0, we have some sort of cycle
if ($graph{$node}->{'indegree'} > 0) {
# cycle detected, throw away one edge starting at the current
# node that ends at another node with indegree == 1 (1 is
# necessary so that we can push the target onto todo)
foreach $target ( @{$graph{$node}->{'targets'}} ) {
if ($graph{$target}->{'indegree'} == 1) {
$graph{$node}->{'targets'} =
[ grep $_ ne $target, @{$graph{$node}->{'targets'}} ];
--($graph{$target}->{'indegree'});
print "resolving cycle by deleting edge $node -> $target\n";
push( @todo, $target );
goto repeat;
}
}
}
}
foreach $node ( keys %graph ) {
die "Couldn't resolve cycle\n" if $graph{$node}->{'indegree'} > 0;
}
Cycles aren't a problem for dpkg if all packages in the cycle are
installed in the same run (right?). (Except --of course-- if it's a
Pre-Depends: cycle, which never can be resolved :-) So maybe you
should note somehow that the packages at both ends of the deleted edge
shouldn't be separated by a break.
Roman
--Bc966T3WbB
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
--
"Why did you hire that idiot?" "You can't fool all of the people all
of the time, so I'm breeding them for stupidity." President Weishaupt
Manoj Srivastava <srivasta@acm.org> <http://www.datasync.com/%7Esrivasta/>
Key C7261095 fingerprint = CB D9 F4 12 68 07 E4 05 CC 2D 27 12 1D F5 E8 6E
--Bc966T3WbB--
Reply to: