Revision
89661
Author
cal@macports.org
Date
2012-02-05 15:33:16 -0800 (Sun, 05 Feb 2012)

Log Message

rev-upgrade: Break circular dependencies in dependency resolution by selecting port with the least dependents

Although it shouldn't happen, I've had problems with circular dependencies when
determining the rebuild-order of ports in rev-upgrade. To prevent such a cycle
triggering an endless loop, this code is introduced.

Modified Paths

Diff

Modified: trunk/base/src/macports1.0/macports.tcl (89660 => 89661)


--- trunk/base/src/macports1.0/macports.tcl	2012-02-05 23:30:07 UTC (rev 89660)
+++ trunk/base/src/macports1.0/macports.tcl	2012-02-05 23:33:16 UTC (rev 89661)
@@ -4184,8 +4184,15 @@
         set unsorted_ports $broken_ports
         set topsort_ports {}
         while {[llength $unsorted_ports] > 0} {
+            set lowest_adj_number [llength $adjlist([lindex $unsorted_ports 0])]
+            set lowest_adj_port [lindex $unsorted_ports 0]
+
             foreach port $unsorted_ports {
-                if {[llength $adjlist($port)] == 0} {
+                set len [llength $adjlist($port)]
+                if {$len < $lowest_adj_number} {
+                    set lowest_adj_port $port
+                }
+                if {$len == 0} {
                     # this node has no further dependencies
                     # add it to topsorted list
                     lappend topsort_ports $port
@@ -4199,7 +4206,25 @@
                         set adjlist($target) [lreplace $adjlist($target) $index $index]
                     }
                 }
+
+                # start anew
+                break;
             }
+
+            # if we arrive here and lowest_adj_number is larger than 0, then we
+            # have a loop in the graph and need to break it somehow
+            if {$lowest_adj_number > 0} {
+                ui_debug "Breaking loop in dependency graph by starting with [$lowest_adj_port name], which has $lowest_adj_number dependencies"
+                lappend topsort_ports $lowest_adj_port
+
+                set index [lsearch -exact $unsorted_ports $lowest_adj_port]
+                set unsorted_ports [lreplace $unsorted_ports $index $index]
+
+                foreach target $revadjlist($port) {
+                    set index [lsearch -exact $adjlist($target) $lowest_adj_port]
+                    set adjlist($target) [lreplace $adjlist($target) $index $index]
+                }
+            }
         }
 
         ui_msg "$macports::ui_prefix Rebuilding in order"