From 6b94a8b170d2dbe753c0b4867bebf67cd200de5d Mon Sep 17 00:00:00 2001
From: Zhang Qiang <qiang.z.zhang@intel.com>
Date: Wed, 6 Feb 2013 11:10:06 -0500
Subject: [PATCH] Check dependency circle before generating topological seq

Change-Id: If94527cc7b76bfe56ea30b02088982294457f8da
---
 depanneur | 167 ++++++++++++++++++++++++++++++++------------------------------
 1 file changed, 86 insertions(+), 81 deletions(-)

diff --git a/depanneur b/depanneur
index f029c75..aa0a1f6 100755
--- a/depanneur
+++ b/depanneur
@@ -899,33 +899,60 @@ sub source_of {
     return;
 }
 
-sub update_pkgdeps
-{
-    %tmp_expansion_errors = ();
-    foreach my $name (keys %to_build) {
-        next if (defined $pkgdeps{$name});
-        if(! (grep $_ eq $name, @skipped)) {
-            my $fn = $to_build{$name}->{filename};
-            debug("Checking dependencies for $name");
-            my @bdeps = expand_deps($fn);
-            if (!shift @bdeps ) {
-                debug("expansion error");
-                debug("  $_") for @bdeps;
-                $tmp_expansion_errors{$name} = [@bdeps];
-                next;
-            }
-            my @deps;
-            foreach my $depp (@bdeps) {
-                my $so = source_of($depp, %to_build);
-                if (defined($so) && $name ne $so
-                    && (! grep($_ eq $so, @skipped))
-                    && (! grep($_ eq $so, @deps))) {
-                    push (@deps, $so);
-                }
+sub find_circle {
+    my (@stack) = @_;
+    my $curpkg = $stack[$#stack];
+
+    return 0 if (exists $tmp_expansion_errors{$curpkg});
+
+    my @deps = @{$pkgddeps{$curpkg}};
+    my $dep;
+
+    foreach my $dep (@deps) {
+        if ($visit{$dep} == 1 && ! (grep $_ eq $dep, @stack)){
+            next;
+        }
+        $visit{$dep} = 1;
+        if (grep $_ eq $dep, @stack){
+            my @circle = ();
+            push @circle, $dep;
+            while (@stack) {
+                my $cur = pop @stack;
+                unshift @circle, $cur;
+                last if ($cur eq $dep);
             }
-            $pkgdeps{$name} = [@deps];
+            warning ("circle found: " . join("->", @circle));
+            return 1;
+        } else {
+            push (@stack, $dep);
+            return 1 if (find_circle(@stack) == 1);
+            pop @stack;
         }
     }
+
+    return 0;
+}
+
+sub check_circle {
+    my $pkg;
+    my $reset_visit = sub {
+        for my $pkg (keys %pkgddeps) {
+            # Skip expansion error packages
+            next if (exists $tmp_expansion_errors{$pkg});
+            $visit{$pkg} = 0;
+        }
+    };
+    for $pkg (keys %pkgddeps) {
+        my @visit_stack;
+        &$reset_visit();
+        push (@visit_stack, $pkg);
+        $visit{$pkg} = 1;
+        if (find_circle(@visit_stack) == 1) {
+            return 1;
+        }
+    }
+
+    return 0;
 }
 
 # generate topological sort sequence from global %pkgddeps
@@ -959,13 +986,41 @@ sub get_top_order {
                 $ref{$_} -= 1;
             }
         }
-
-        error ("circle found, break!!!") if (!@candlist);
     }
 
     return @top_order;
 }
 
+
+sub update_pkgdeps
+{
+    %tmp_expansion_errors = ();
+    foreach my $name (keys %to_build) {
+        next if (defined $pkgdeps{$name});
+        if(! (grep $_ eq $name, @skipped)) {
+            my $fn = $to_build{$name}->{filename};
+            debug("Checking dependencies for $name");
+            my @bdeps = expand_deps($fn);
+            if (!shift @bdeps ) {
+                debug("expansion error");
+                debug("  $_") for @bdeps;
+                $tmp_expansion_errors{$name} = [@bdeps];
+                next;
+            }
+            my @deps;
+            foreach my $depp (@bdeps) {
+                my $so = source_of($depp, %to_build);
+                if (defined($so) && $name ne $so
+                    && (! grep($_ eq $so, @skipped))
+                    && (! grep($_ eq $so, @deps))) {
+                    push (@deps, $so);
+                }
+            }
+            $pkgdeps{$name} = [@deps];
+        }
+    }
+}
+
 sub update_pkgddeps {
     foreach my $name (keys %to_build) {
         # Skip expansion error packages
@@ -998,6 +1053,11 @@ sub update_pkgddeps {
         }
     }
 
+    if (check_circle() == 1) {
+        info("circle found, exit...");
+        exit 1;
+    }
+
     # Expand dependency using direct dependency dict
     # pkgddeps  => pkgdeps
     # pkgrddeps => pkgrdeps
@@ -1069,61 +1129,6 @@ sub resolve_deps {
     return @final;
 }
 
-sub find_circle {
-    my (@stack) = @_;
-    my $curpkg = $stack[$#stack];
-
-    return 0 if (exists $tmp_expansion_errors{$curpkg});
-
-    my @deps = @{$pkgddeps{$curpkg}};
-    my $dep;
-
-    foreach my $dep (@deps) {
-        if ($visit{$dep} == 1 && ! (grep $_ eq $dep, @stack)){
-            next;
-        }
-        $visit{$dep} = 1;
-        if (grep $_ eq $dep, @stack){
-            my @circle = ();
-            push @circle, $dep;
-            while (@stack) {
-                my $cur = pop @stack;
-                unshift @circle, $cur;
-                last if ($cur eq $dep);
-            }
-            warning ("circle found: " . join("->", @circle));
-            return 1;
-        } else {
-            push (@stack, $dep);
-            return 1 if (find_circle(@stack) == 1);
-            pop @stack;
-        }
-    }
-
-    return 0;
-}
-
-sub check_circle {
-    my $pkg;
-    my $reset_visit = sub {
-        for my $pkg (keys %pkgddeps) {
-            # Skip expansion error packages
-            next if (exists $tmp_expansion_errors{$pkg});
-            $visit{$pkg} = 0;
-        }
-    };
-    for $pkg (keys %pkgddeps) {
-        my @visit_stack;
-        &$reset_visit();
-        push (@visit_stack, $pkg);
-        $visit{$pkg} = 1;
-        if (find_circle(@visit_stack) == 1) {
-            return 1;
-        }
-    }
-
-    return 0;
-}
 
 sub worker_thread {
     my ($name, $thread, $index) = @_;
-- 
2.7.4