From 5bdf91aa1f8d4b11de820f527bb5c091735954c0 Mon Sep 17 00:00:00 2001
From: Pascal Rigaux <pixel@mandriva.com>
Date: Mon, 3 Sep 2007 08:08:48 +0000
Subject: - fix bug in sort_graph (used by build_transaction_set)

---
 NEWS            |  2 ++
 URPM/Resolve.pm | 25 +++++++++++++++----------
 2 files changed, 17 insertions(+), 10 deletions(-)

diff --git a/NEWS b/NEWS
index e01ac02..c92869a 100644
--- a/NEWS
+++ b/NEWS
@@ -1,3 +1,5 @@
+- fix bug in sort_graph (used by build_transaction_set)
+
 Version 1.78 - 31 August 2007, by Pascal "Pixel" Rigaux
 
 - fix dead-loop in build_transaction_set (#33020)
diff --git a/URPM/Resolve.pm b/URPM/Resolve.pm
index 2195ccd..629e5b5 100644
--- a/URPM/Resolve.pm
+++ b/URPM/Resolve.pm
@@ -1272,10 +1272,9 @@ sub sort_graph {
     my (%examined, %added, @sorted);
 
     my $recurse; $recurse = sub {
-	my (@ids) = @_;
-	my $id = $ids[0];
+	my ($id, @ids) = @_;
 
-	my @loop;
+	my ($loop_ahead, %loop);
 	foreach my $p_id (@{$edges->{$id}}) {
 	    if ($p_id == $id) {
 		# don't care
@@ -1284,24 +1283,30 @@ sub sort_graph {
 	    } elsif (grep { $_ == $p_id } @ids) {
 		my $begin = 1;
 		my @l = grep { $begin &&= $_ != $p_id } @ids;
-		push @loop, $p_id, @l;
+		$loop_ahead = 1;
+		@loop{$p_id, $id, @l} = undef;
 	    } elsif (!exists $examined{$p_id}) {
 		$examined{$p_id} = undef;
-		my @l = $recurse->($p_id, @ids);
+		my @l = $recurse->($p_id, $id, @ids);
 		if (@l) {
-		    push @loop, @l;
+		    @loop{@l} = undef;
+		    #- we would need to compute loop_ahead. we will do it below only once, and if not already set
 		}
 	    }
 	}
-	if (!@loop || $loop[0] == $id) {
+	if (!$loop_ahead && grep { exists $loop{$_} } @ids) {
+	    $loop_ahead = 1;
+	}
+
+	if (!$loop_ahead) {
 	    #- it's now a leaf or a loop we're done with
-	    my @toadd = @loop ? @loop : $id;
+	    my @toadd = %loop ? keys %loop : $id;
 	    $added{$_} = undef foreach @toadd;
 	    push @sorted, [ uniq(grep { $nodes_h{$_} } @toadd) ];
 	    ();
 	} else {
 	    #- still looping, going up
-	    @loop;
+	    keys %loop;
 	}
     };
     !exists $added{$_} and $recurse->($_) foreach @$nodes;
@@ -1327,7 +1332,7 @@ sub check_graph_is_sorted {
 	my $id_i = $nb{$id} or next;
 	foreach my $req (@{$edges->{$id}}) {
 	    my $req_i = $nb{$req} or next;
-	    $req_i <= $id_i or $error->("$id should be before $req ($req_i $id_i)");
+	    $req_i <= $id_i or $error->("$req should be before $id ($req_i $id_i)");
 	}
     }
     $nb_errors == 0;
-- 
cgit v1.2.1