Revision: 89661 http://trac.macports.org/changeset/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: -------------- trunk/base/src/macports1.0/macports.tcl Modified: trunk/base/src/macports1.0/macports.tcl =================================================================== --- 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"