Diff
Not logged in
HomeFilesLeavesTimelineBranchesTagsTicketsWikiLogin

Differences From:

File tools/cvs2fossil/lib/c2f_pbreakrcycle.tcl part of check-in [85bd219d0b] - Continued work on pass 6. Completed creation of changeset graph (nodes, dependencies), started on topological iteration and breaking cycles. Basic iteration is complete, fiding a cycle ditto. Not yet done is to actually break a found cycle. Extended the changeset class with the necessary accessor methods (getting cset type, successors, time range). Note: Looking at my code it may be that my decision to save the cset order caused this pass to subsume the RevisionTopologicalSortPass of cvs2svn. Check again when I am done. Note 2: The test case (tcl repository, tcl project) had no cycles. by aku on 2007-11-13 07:22:35. [view]

To:

File tools/cvs2fossil/lib/c2f_pbreakrcycle.tcl part of check-in [94c39d6375] - Completed pass 6, wrote the code performing the breaking of cycles. Done by analysing each triple of changesets in the cycle at the file dependency level to see which revisions can be sorted apart. Added some additional utility routines. Extended the changeset class with the accessors required by the cycle breaker. by aku on 2007-11-14 05:11:56. [view] 
@@ -16,15 +16,16 @@
 
 # # ## ### ##### ######## ############# #####################
 ## Requirements
 
-package require Tcl 8.4                               ; # Required runtime.
-package require snit                                  ; # OO system.
-package require struct::graph                         ; # Graph handling.
-package require struct::list                          ; # Higher order list operations.
-package require vc::tools::log                        ; # User feedback.
-package require vc::fossil::import::cvs::state        ; # State storage.
-package require vc::fossil::import::cvs::project::rev ; # Project level changesets
+package require Tcl 8.4                                   ; # Required runtime.
+package require snit                                      ; # OO system.
+package require struct::graph                             ; # Graph handling.
+package require struct::list                              ; # Higher order list operations.
+package require vc::tools::log                            ; # User feedback.
+package require vc::fossil::import::cvs::state            ; # State storage.
+package require vc::fossil::import::cvs::project::rev     ; # Project level changesets
+package require vc::fossil::import::cvs::project::revlink ; # Cycle links.
 
 # # ## ### ##### ######## ############# #####################
 ## Register the pass with the management
 
@@ -66,8 +67,10 @@
 	# Pass manager interface. Executed to perform the
 	# functionality of the pass.
 
 	state reading revision
+	state reading changeset
+	state reading csrevision
 
 	# We create a graph of the revision changesets, using the file
 	# level dependencies to construct a first approximation of
 	# them at the project level. Then look for cycles in that
@@ -75,9 +78,9 @@
 
 	# 1. Create nodes for all relevant changesets and a mapping
 	#    from the revisions to their changesets/nodes.
 
-	log write 3 brkrcycle {Creating changeset graph, filling with nodes}
+	log write 3 breakrcycle {Creating changeset graph, filling with nodes}
 
 	set dg [struct::graph dg]
 
 	state transaction {
@@ -91,9 +94,9 @@
 	# 2. Find for all relevant changeset their revisions and their
 	#    dependencies. Map the latter back to changesets and
 	#    construct the corresponding arcs.
 
-	log write 3 brkrcycle {Setting up node dependencies}
+	log write 3 breakrcycle {Setting up node dependencies}
 
 	state transaction {
 	    foreach cset [project::rev all] {
 		if {[$cset bysymbol]} continue
@@ -108,9 +111,9 @@
 	#    oldest to youngest, saving and removing dependencies. If
 	#    we find no nodes without predecessors we have a cycle,
 	#    and work on breaking it.
 
-	log write 3 brkrcycle {Computing changeset order, breaking cycles}
+	log write 3 breakrcycle {Computing changeset order, breaking cycles}
 
 	InitializeCandidates $dg
 	state transaction {
 	    while {1} {
@@ -117,10 +120,10 @@
 		while {[WithoutPredecessor $dg n]} {
 		    SaveAndRemove $dg $n
 		}
 		if {![llength [dg nodes]]} break
-		set cycle [FindCycle $dg]
-		BreakCycle $dg $cycle
+		BreakCycle $dg [FindCycle $dg]
+		InitializeCandidates $dg
 	    }
 	}
 
 	return
@@ -225,18 +228,74 @@
 	    # Stop searching when we have seen the current node
 	    # already, the circle has been closed.
 	    if {[info exists seen($start)]} break
 	    lappend path $start
-	    set seen($start) [llength $path]
+	    set seen($start) [expr {[llength $path]-1}]
 	    # Choose arbitrary predecessor
 	    set start [lindex [$dg nodes -in $start] 0]
 	}
 
 	return [struct::list reverse [lrange $path $seen($start) end]]
     }
 
+    proc ID {cset} { return "<[$cset id]>" }
+
     proc BreakCycle {dg cycle} {
-	trouble internal "Break cycle <$cycle>"
+	# The cycle we have gotten is broken by breaking apart one or
+	# more of the changesets in the cycle. This causes us to
+	# create one or more changesets which are to be committed,
+	# added to the graph, etc. pp.
+
+	set cprint [join [struct::list map $cycle [myproc ID]] { }]
+
+	lappend cycle [lindex $cycle 0] [lindex $cycle 1]
+	set bestlink {}
+	set bestnode {}
+
+	foreach \
+	    prev [lrange $cycle 0 end-2] \
+	    cset [lrange $cycle 1 end-1] \
+	    next [lrange $cycle 2 end] {
+
+		# Each triple PREV -> CSET -> NEXT of changesets, a
+		# 'link' in the cycle, is analysed and the best
+		# location where to at least weaken the cycle is
+		# chosen for further processing.
+
+		set link [project::revlink %AUTO% $prev $cset $next]
+		if {$bestlink eq ""} {
+		    set bestlink $link
+		    set bestnode $cset
+		} elseif {[$link betterthan $bestlink]} {
+		    $bestlink destroy
+		    set bestlink $link
+		    set bestnode $cset
+		} else {
+		    $link destroy
+		}
+	    }
+
+	log write 5 breakrcycle "Breaking cycle ($cprint) by splitting changeset <[$bestnode id]>"
+
+	set newcsets [$bestlink break]
+	$bestlink destroy
+
+        # 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.
+
+        $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] {
+		dg arc insert $cset $succ
+	    }
+	}
 	return
     }
 
     typevariable at      0 ; # Counter for commit ids for the changesets.
@@ -257,11 +316,12 @@
     namespace eval breakrcycle {
 	namespace import ::vc::fossil::import::cvs::state
 	namespace eval project {
 	    namespace import ::vc::fossil::import::cvs::project::rev
+	    namespace import ::vc::fossil::import::cvs::project::revlink
 	}
 	namespace import ::vc::tools::log
-	log register brkrcycle
+	log register breakrcycle
     }
 }
 
 # # ## ### ##### ######## ############# #####################

Fossil version [c0211010a1] 2009-12-13 01:31:36