Differences From:
File
tools/cvs2fossil/lib/c2f_pbreakrcycle.tcl
part of check-in
[de64c94f54]
- Bugfix. When setting up or extended the changeset graph a changeset's successor may lay outside of the set of changesets under consideration, i.e. without a node in the graph. Ignore these. This did not (or only rarely) happen before the bugfix to the successor computation of changesets in project::rev (list instead of single).
by
aku on
2007-11-16 03:59:21.
[view]
To:
File
tools/cvs2fossil/lib/c2f_pbreakrcycle.tcl
part of check-in
[770a9b576a]
- Completed pass 7, breaking dependency cycles over symbol changesets. Moved the bulk of the cycle breaker code into its own class as it was common to the passes 6 and 7, and updated the two passes accordingly. Added code to load the changeset counter from the state to start properly.
by
aku on
2007-11-16 04:17:30.
[view]
@@ -11,21 +11,21 @@
# # ## ### ##### ######## ############# #####################
## Pass VI. This pass goes over the set of revision based changesets
## and breaks all dependency cycles they may be in. We need a
-## dependency tree.
+## dependency tree. Identical to pass VII, except for the selection of
+## the changesets.
# # ## ### ##### ######## ############# #####################
## 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 vc::fossil::import::cvs::project::revlink ; # Cycle links.
+package require vc::fossil::import::cvs::cyclebreaker ; # Breaking dependency cycles.
+package require vc::fossil::import::cvs::state ; # State storage.
+package require vc::fossil::import::cvs::project::rev ; # Project level changesets
# # ## ### ##### ######## ############# #####################
## Register the pass with the management
@@ -51,16 +51,18 @@
pos INTEGER NOT NULL,
UNIQUE (cid),
UNIQUE (pos)
}
-
return
}
typemethod load {} {
# Pass manager interface. Executed to load data computed by
# this pass into memory when this pass is skipped instead of
# executed.
+
+ state reading changeset
+ project::rev loadcounter
return
}
typemethod run {} {
@@ -70,66 +72,13 @@
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
- # graph and break them.
-
- # 1. Create nodes for all relevant changesets and a mapping
- # from the revisions to their changesets/nodes.
-
- log write 3 breakrcycle {Creating changeset graph, filling with nodes}
-
- set dg [struct::graph dg]
-
- state transaction {
- foreach cset [project::rev all] {
- if {[$cset bysymbol]} continue
- dg node insert $cset
- dg node set $cset timerange [$cset timerange]
- }
- }
-
- # 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 breakrcycle {Setting up node dependencies}
-
state transaction {
- foreach cset [project::rev all] {
- if {[$cset bysymbol]} continue
- foreach succ [$cset successors] {
- # Changesets may have dependencies outside of the
- # chosen set. These are ignored
- if {![dg node exists $succ]} continue
- dg arc insert $cset $succ
- }
- }
- }
-
- # 3. Lastly we iterate the graph topologically. We mark off
- # the nodes which have no predecessors, in order from
- # 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 breakrcycle {Computing changeset order, breaking cycles}
-
- InitializeCandidates $dg
- state transaction {
- while {1} {
- while {[WithoutPredecessor $dg n]} {
- SaveAndRemove $dg $n
- }
- if {![llength [dg nodes]]} break
- BreakCycle $dg [FindCycle $dg]
- InitializeCandidates $dg
- }
- }
-
+ cyclebreaker run [struct::list filter [project::rev all] \
+ [myproc IsByRevision]] \
+ [myproc SaveOrder]
+ }
return
}
typemethod discard {} {
@@ -143,170 +92,21 @@
# # ## ### ##### ######## #############
## Internal methods
- # Instead of searching the whole graph for the degree-0 nodes in
- # each iteration we compute the list once to start, and then only
- # update it incrementally based on the outgoing neighbours of the
- # node chosen for commit.
-
- proc InitializeCandidates {dg} {
- # bottom = list (list (node, range min, range max))
- ::variable bottom
- foreach n [$dg nodes] {
- if {[$dg node degree -in $n]} continue
- lappend bottom [linsert [$dg node get $n timerange] 0 $n]
- }
- set bottom [lsort -index 1 -integer [lsort -index 2 -integer $bottom]]
- return
- }
-
- proc WithoutPredecessor {dg nv} {
- ::variable bottom
-
- upvar 1 $nv n
- if {![llength $bottom]} { return 0 }
+ proc IsByRevision {cset} { $cset byrevision }
- set n [lindex [lindex $bottom 0] 0]
- set bottom [lrange $bottom 1 end]
- set changed 0
-
- # Update list of nodes without predecessor, based on the
- # outgoing neighbours of the chosen node. This should be
- # faster than iterating of the whole set of nodes, finding all
- # without predecessors, sorting them by time, etc. pp.
- foreach out [$dg nodes -out $n] {
- if {[$dg node degree -in $out] > 1} continue
- # Degree-1 neighbour, will have no predecessors after the
- # removal of n. Put on the list.
- lappend bottom [linsert [$dg node get $out timerange] 0 $out]
- set changed 1
- }
- if {$changed} {
- set bottom [lsort -index 1 -integer [lsort -index 2 -integer $bottom]]
- }
-
- # 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 SaveAndRemove {dg n} {
- ::variable at
- set cid [$n id]
+ proc SaveOrder {at cset} {
+ set cid [$cset id]
log write 4 breakrcycle "Comitting @ $at: <$cid>"
state run {
INSERT INTO csorder (cid, pos)
VALUES ($cid, $at)
}
# TODO: Write the project level changeset dependencies as well.
- incr at
- $dg node delete $n
return
}
-
- 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
- # in a cycle. We can start at an arbitrary node, follow its
- # incoming edges to its predecessors until we see a node a
- # second time. That node closes the cycle and the beginning is
- # its first occurence. Note that we can choose an arbitrary
- # predecessor of each node as well, we do not have to search.
-
- # We record for each node the index of the first appearance in
- # the path, making it easy at the end to cut the cycle from
- # it.
-
- # Choose arbitrary node to start our search at.
- set start [lindex [$dg nodes] 0]
-
- # Initialize state, path of seen nodes, and when seen.
- set path {}
- array set seen {}
-
- while {1} {
- # 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) [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} {
- # 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] {
- # Changesets may have dependencies outside of the
- # chosen set. These are ignored
- if {![dg node exists $succ]} continue
- $dg arc insert $cset $succ
- }
- }
- return
- }
-
- typevariable at 0 ; # Counter for commit ids for the changesets.
- typevariable bottom {} ; # List of candidate nodes for committing.
# # ## ### ##### ######## #############
## Configuration
@@ -319,12 +119,12 @@
namespace eval ::vc::fossil::import::cvs::pass {
namespace export breakrcycle
namespace eval breakrcycle {
+ namespace import ::vc::fossil::import::cvs::cyclebreaker
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 breakrcycle
}