SHA1 Hash:	ad7d5c2d10666dd81a2e111590dcce632d938d2c
Date:	2007-11-22 03:03:44
User:	aku
Comment:	Reworked the cycle breaker internals, moving the code handling the replacement of a changset (= node) with its fragments into a separate command. Extended the API, exposing the replacement operation, for use by passes. Added debugging code showing the set of consumable nodes for each iteration.
Timelines:	ancestors | descendants | both | trunk
Other Links:	files | ZIP archive | manifest

• branch=trunk inherited from [a28c83647d]
• sym-trunk inherited from [a28c83647d]

Modified tools/cvs2fossil/lib/c2f_cyclebreaker.tcl from [f2e71127d5] to [0fd2ab8302].

@@ -96,10 +96,11 @@
 	while {1} {
 	    while {[WithoutPredecessor $dg n]} {
 		ProcessedHook $n $myat
 		$dg node delete $n
 		incr myat
+		ShowPendingNodes
 	    }
 
 	    if {![llength [dg nodes]]} break
 
 	    BreakCycleHook       $dg
@@ -125,10 +126,15 @@
 
     # # ## ### ##### ######## #############
 
     typemethod break {graph} {
 	BreakCycle $graph [FindCycle $graph]
+	return
+    }
+
+    typemethod replace {graph n replacements} {
+	Replace $graph $n $replacements
 	return
     }
 
     # # ## ### ##### ######## #############
     ## Internal methods
@@ -182,10 +188,11 @@
 	foreach n [$dg nodes] {
 	    if {[$dg node degree -in $n]} continue
 	    lappend mybottom [linsert [$dg node get $n timerange] 0 $n]
 	}
 	set mybottom [lsort -index 1 -integer [lsort -index 2 -integer $mybottom]]
+	ShowPendingNodes
 	return
     }
 
     proc WithoutPredecessor {dg nv} {
 	::variable mybottom
@@ -215,10 +222,20 @@
 	# We do not delete the node immediately, to allow the Save
 	# procedure to save the dependencies as well (encoded in the
 	# arcs).
 	return 1
     }
+
+    proc ShowPendingNodes {} {
+	if {[log verbosity?] < 10} return
+	::variable mybottom
+	log write 10 cyclebreaker \
+	    "Pending: [struct::list map $mybottom [myproc FormatPendingItem]]"
+	return
+    }
+
+    proc FormatPendingItem {item} { lreplace $item 0 0 <[[lindex $item 0] id]> }
 
     proc FindCycle {dg} {
 	# This procedure is run if and only the graph is not empty and
 	# all nodes have predecessors. This means that each node is
 	# either part of a cycle or (indirectly) depending on a node
@@ -298,44 +315,11 @@
 
         # At this point the old changeset (BESTNODE) is gone
         # already. We remove it from the graph as well and then enter
         # the fragments generated for it.
 
-	# NOTE. We have to get the list of incoming neighbours and
-	# recompute their successors after the new nodes have been
-	# inserted. Their outgoing arcs will now go to one or both of
-	# the new nodes, and not redoing them may cause us to forget
-	# circles, leaving them in, unbroken.
-
-	set pre [$dg nodes -in $bestnode]
-
-        $dg node delete $bestnode
-
-	foreach cset $newcsets {
-	    $dg node insert $cset
-	    $dg node set    $cset timerange [$cset timerange]
-	}
-
-	foreach cset $newcsets {
-	    foreach succ [$cset successors] {
-		# The new changesets may have dependencies outside of
-		# the chosen set. These are ignored
-		if {![$dg node exists $succ]} continue
-		$dg arc insert $cset $succ
-	    }
-	}
-	foreach cset $pre {
-	    foreach succ [$cset successors] {
-		# Note that the arc may already exist in the graph. If
-		# so ignore it. The new changesets may have
-		# dependencies outside of the chosen set. These are
-		# ignored
-		if {![$dg node exists $succ]} continue
-		if {[HasArc $dg $cset $succ]} continue;# TODO should be graph method.
-		$dg arc insert $cset $succ
-	    }
-	}
+	Replace $dg $bestnode $newcsets
 
 	Mark $dg -${ID}-after
 	return
     }
 
@@ -355,10 +339,49 @@
 	file mkdir [file dirname $fname]
 	dot write $dg $mydotprefix$suffix $fname
 	incr mydotid
 
 	log write 5 cyclebreaker ".dot export $fname"
+	return
+    }
+
+    proc Replace {dg n replacements} {
+	# NOTE. We have to get the list of incoming neighbours and
+	# recompute their successors after the new nodes have been
+	# inserted. Their outgoing arcs will now go to one or both of
+	# the new nodes, and not redoing them may cause us to forget
+	# circles, leaving them in, unbroken.
+
+	set pre [$dg nodes -in $n]
+
+        $dg node delete $n
+
+	foreach cset $replacements {
+	    $dg node insert $cset
+	    $dg node set    $cset timerange [$cset timerange]
+	}
+
+	foreach cset $replacements {
+	    foreach succ [$cset successors] {
+		# The new changesets may have dependencies outside of
+		# the chosen set. These are ignored
+		if {![$dg node exists $succ]} continue
+		$dg arc insert $cset $succ
+	    }
+	}
+	foreach cset $pre {
+	    foreach succ [$cset successors] {
+		# Note that the arc may already exist in the graph. If
+		# so ignore it. The new changesets may have
+		# dependencies outside of the chosen set. These are
+		# ignored
+		if {![$dg node exists $succ]} continue
+		if {[HasArc $dg $cset $succ]} continue;# TODO should be graph method.
+		$dg arc insert $cset $succ
+	    }
+	}
+
 	return
     }
 
     # # ## ### ##### ######## #############
     ## Callback invokation ...