Overview
| SHA1 Hash: | 7f15be907861e9eb8f8fb9fa0a0baf9caf5d619b |
|---|---|
| Date: | 2007-11-20 06:59:03 |
| User: | aku |
| Comment: | Added the ability to export the changeset graphs processed by the passes 6 to 8 using GraphViz's dot-format. This is activated by using the switch '--dots'. Bugfixes in the cycle breaker. First corrected variable names, I forgot to use the standard 'myXXX' format for the typevariables. Second, fixed a bug uncovered by looking at the exported graphs, which caused the system to loose arcs, possibly breaking cycles without actually breaking them, leaving them in the dependencies. |
| Timelines: | ancestors | descendants | both | trunk |
| Other Links: | files | ZIP archive | manifest |
Tags And Properties
- branch=trunk inherited from [a28c83647d]
- sym-trunk inherited from [a28c83647d]
Changes
[hide diffs]Modified tools/cvs2fossil/lib/c2f_cyclebreaker.tcl from [41093323e5] to [7d4b849665].
@@ -18,10 +18,11 @@
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::dot ; # User feedback. DOT export.
package require vc::tools::log ; # User feedback.
package require vc::tools::misc ; # Text formatting.
package require vc::fossil::import::cvs::project::rev ; # Project level changesets
package require vc::fossil::import::cvs::project::revlink ; # Cycle links.
@@ -30,46 +31,40 @@
snit::type ::vc::fossil::import::cvs::cyclebreaker {
# # ## ### ##### ######## #############
## Public API
- typemethod run {changesets {savecmd {}}} {
- ::variable save $savecmd
- ::variable at 0
+ typemethod dotsto {path} {
+ ::variable mydotdestination $path
+ return
+ }
+
+ typemethod dot {label changesets} {
+ ::variable mydotprefix $label
+ ::variable mydotid 0
+
+ set dg [Setup $changesets 0]
+ Mark $dg
+ $dg destroy
+ return
+ }
+
+ typemethod run {label changesets {savecmd {}}} {
+ ::variable mysave $savecmd
+ ::variable myat 0
+ ::variable mydotprefix $label
+ ::variable mydotid 0
# We create a graph of the revision changesets, using the file
# level dependencies to construct a first approximation of the
# dependencies at the project level. Then we 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 cyclebreaker "Creating changeset graph, filling with nodes"
- log write 3 cyclebreaker "Adding [nsp [llength $changesets] node]"
-
- set dg [struct::graph dg]
-
- foreach cset $changesets {
- 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 cyclebreaker {Setting up node dependencies}
-
- foreach cset $changesets {
- 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
- }
- }
+ set dg [Setup $changesets]
# 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,
@@ -94,34 +89,67 @@
}
# # ## ### ##### ######## #############
## Internal methods
+ proc Setup {changesets {log 1}} {
+ if {$log} {
+ log write 3 cyclebreaker "Creating changeset graph, filling with nodes"
+ log write 3 cyclebreaker "Adding [nsp [llength $changesets] node]"
+ }
+
+ set dg [struct::graph dg]
+
+ foreach cset $changesets {
+ $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.
+
+ if {$log} {
+ log write 3 cyclebreaker {Setting up node dependencies}
+ }
+
+ foreach cset $changesets {
+ 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 $dg
+ }
+
# 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
+ ::variable mybottom
foreach n [$dg nodes] {
if {[$dg node degree -in $n]} continue
- lappend bottom [linsert [$dg node get $n timerange] 0 $n]
+ lappend mybottom [linsert [$dg node get $n timerange] 0 $n]
}
- set bottom [lsort -index 1 -integer [lsort -index 2 -integer $bottom]]
+ set mybottom [lsort -index 1 -integer [lsort -index 2 -integer $mybottom]]
return
}
proc WithoutPredecessor {dg nv} {
- ::variable bottom
+ ::variable mybottom
upvar 1 $nv n
- if {![llength $bottom]} { return 0 }
-
- set n [lindex [lindex $bottom 0] 0]
- set bottom [lrange $bottom 1 end]
+ if {![llength $mybottom]} { return 0 }
+
+ set n [lindex [lindex $mybottom 0] 0]
+ set mybottom [lrange $mybottom 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
@@ -128,35 +156,35 @@
# 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]
+ lappend mybottom [linsert [$dg node get $out timerange] 0 $out]
set changed 1
}
if {$changed} {
- set bottom [lsort -index 1 -integer [lsort -index 2 -integer $bottom]]
+ set mybottom [lsort -index 1 -integer [lsort -index 2 -integer $mybottom]]
}
# 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
- ::variable save
+ ::variable myat
+ ::variable mysave
# Give the user of the cycle breaker the opportunity to work
# with the changeset before it is removed from the graph.
- if {[llength $save]} {
- uplevel #0 [linsert $save end $at $n]
+ if {[llength $mysave]} {
+ uplevel #0 [linsert $mysave end $myat $n]
}
- incr at
+ incr myat
$dg node delete $n
return
}
proc FindCycle {dg} {
@@ -229,17 +257,27 @@
$link destroy
}
}
log write 5 breakrcycle "Breaking cycle ($cprint) by splitting changeset <[$bestnode id]>"
+ set ID [$bestnode id]
+ Mark $dg -${ID}-before
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.
+
+ # 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
@@ -252,16 +290,54 @@
# 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
+ }
+ }
+
+ Mark $dg -${ID}-after
+ return
+ }
+
+ # TODO: This should be a graph method.
+ proc HasArc {dg a b} {
+ #8.5: return [expr {$b in [$dg nodes -out $a]}]
+ if {[lsearch -exact [$dg nodes -out $a] $b] < 0} { return 0 }
+ return 1
+ }
+
+ proc Mark {dg {suffix {}}} {
+ ::variable mydotdestination
+ if {$mydotdestination eq ""} return
+ ::variable mydotprefix
+ ::variable mydotid
+ set fname $mydotdestination/${mydotprefix}${mydotid}${suffix}.dot
+ file mkdir [file dirname $fname]
+ dot write $dg $mydotprefix$suffix $fname
+ incr mydotid
+
+ log write 5 cyclebreaker ".dot export $fname"
return
}
- typevariable at 0 ; # Counter for commit ids for the changesets.
- typevariable bottom {} ; # List of candidate nodes for committing.
- typevariable save {} ; # The command to call for each processed node
+ typevariable myat 0 ; # Counter for commit ids for the changesets.
+ typevariable mybottom {} ; # List of candidate nodes for committing.
+ typevariable mysave {} ; # The command to call for each processed node
+
+ typevariable mydotdestination {} ; # Destination directory for .dot files.
+ typevariable mydotprefix {} ; # Prefix for dot files when exporting the graphs.
+ typevariable mydotid 0 ; # Counter for dot file name generation.
# # ## ### ##### ######## #############
## Configuration
pragma -hasinstances no ; # singleton
@@ -278,14 +354,15 @@
namespace import ::vc::fossil::import::cvs::project::rev
namespace import ::vc::fossil::import::cvs::project::revlink
}
namespace import ::vc::tools::misc::*
namespace import ::vc::tools::log
+ namespace import ::vc::tools::dot
log register cyclebreaker
}
}
# # ## ### ##### ######## ############# #####################
## Ready
package provide vc::fossil::import::cvs::cyclebreaker 1.0
return
Modified tools/cvs2fossil/lib/c2f_option.tcl from [593517a591] to [5b894a43fc].
@@ -26,10 +26,11 @@
package require vc::fossil::import::cvs::pass ; # Pass management
package require vc::fossil::import::cvs::pass::collar ; # Pass I.
package require vc::fossil::import::cvs::repository ; # Repository management
package require vc::fossil::import::cvs::state ; # State storage
package require vc::fossil::import::cvs::project::sym ; # Project level symbols
+package require vc::fossil::import::cvs::cyclebreaker ; # Breaking dependency cycles.
# # ## ### ##### ######## ############# #####################
##
snit::type ::vc::fossil::import::cvs::option {
@@ -77,10 +78,11 @@
--trunk-only { repository trunkonly! }
--exclude { project::sym exclude [Value arguments] }
--force-tag { project::sym forcetag [Value arguments] }
--force-branch { project::sym forcebranch [Value arguments] }
--batch { log noprogress }
+ --dots { cyclebreaker dotsto [Value arguments] }
default {
Usage $badoption$option\n$gethelp
}
}
}
@@ -138,10 +140,14 @@
trouble info " --force-branch ?PROJECT:?SYMBOL"
trouble info " Force the named symbol from all or just"
trouble info " the specified project to be converted as"
trouble info " branch. Both project and symbol names"
trouble info " are glob patterns."
+ trouble info ""
+ trouble info " --dots PATH Write the changeset graphs before, after,"
+ trouble info " and during breaking the of cycles to the"
+ trouble info " direcotry PATH, using GraphViz's dot format"
trouble info ""
# --project, --cache
# ...
return
@@ -213,10 +219,11 @@
namespace export option
namespace eval option {
namespace import ::vc::tools::misc::striptrailingslash
namespace import ::vc::fossil::import::cvs::pass
namespace import ::vc::fossil::import::cvs::pass::collar
+ namespace import ::vc::fossil::import::cvs::cyclebreaker
namespace import ::vc::fossil::import::cvs::repository
namespace import ::vc::fossil::import::cvs::state
namespace eval project {
namespace import ::vc::fossil::import::cvs::project::sym
}
Modified tools/cvs2fossil/lib/c2f_pbreakacycle.tcl from [9a96d44941] to [c92253ed90].
@@ -56,10 +56,14 @@
}
typemethod run {} {
# Pass manager interface. Executed to perform the
# functionality of the pass.
+
+ set changesets [project::rev all]
+ cyclebreaker dot break-all-start $changesets
+
return
}
typemethod discard {} {
# Pass manager interface. Executed for all passes after the
Modified tools/cvs2fossil/lib/c2f_pbreakrcycle.tcl from [030100362a] to [4f907e0102].
@@ -72,15 +72,19 @@
typemethod run {} {
# Pass manager interface. Executed to perform the
# functionality of the pass.
+ set changesets [struct::list filter [project::rev all] [myproc IsByRevision]]
+ cyclebreaker dot break-rev-start $changesets
+
state transaction {
- cyclebreaker run [struct::list filter [project::rev all] \
- [myproc IsByRevision]] \
- [myproc SaveOrder]
+ cyclebreaker run break-rev $changesets [myproc SaveOrder]
}
+
+ set changesets [struct::list filter [project::rev all] [myproc IsByRevision]]
+ cyclebreaker dot break-rev-done $changesets
repository printcsetstatistics
return
}
Modified tools/cvs2fossil/lib/c2f_pbreakscycle.tcl from [a1d5600281] to [e94461c91b].
@@ -60,14 +60,19 @@
typemethod run {} {
# Pass manager interface. Executed to perform the
# functionality of the pass.
+ set changesets [struct::list filter [project::rev all] [myproc IsBySymbol]]
+ cyclebreaker dot break-sym-start $changesets
+
state transaction {
- cyclebreaker run [struct::list filter [project::rev all] \
- [myproc IsBySymbol]]
+ cyclebreaker run break-sym $changesets
}
+
+ set changesets [struct::list filter [project::rev all] [myproc IsBySymbol]]
+ cyclebreaker dot break-sym-done $changesets
repository printcsetstatistics
return
}
Added tools/cvs2fossil/lib/dot.tcl version [191e7fb347]
@@ -1,1 +1,88 @@
+## -*- tcl -*-
+# # ## ### ##### ######## ############# #####################
+## Copyright (c) 2007 Andreas Kupries.
+#
+# This software is licensed as described in the file LICENSE, which
+# you should have received as part of this distribution.
+#
+# This software consists of voluntary contributions made by many
+# individuals. For exact contribution history, see the revision
+# history and logs, available at http://fossil-scm.hwaci.com/fossil
+# # ## ### ##### ######## ############# #####################
+
+## Utility package, export graph data to dot format for formatting
+## with neato et. all
+
+# # ## ### ##### ######## ############# #####################
+## Requirements
+
+package require Tcl 8.4 ; # Required runtime
+package require snit ; # OO system.
+package require fileutil ; # Helper commands.
+
+# # ## ### ##### ######## ############# #####################
+##
+
+snit::type ::vc::tools::dot {
+ # # ## ### ##### ######## #############
+ ## Public API, Methods
+
+ typemethod format {g name} {
+ lappend lines "digraph \"$name\" \{"
+
+ foreach n [$g nodes] {
+ set cmd "[$n id] \["
+ append cmd " label=\"<[$n id]>\""
+
+ if {[$g node keyexists $n shape]} {
+ append cmd " shape=[$g node get $n shape]"
+ }
+ append cmd " \];"
+ lappend lines $cmd
+ }
+ foreach a [$g arcs] {
+ lappend lines "[[$g arc source $a] id] -> [[$g arc target $a] id];"
+ }
+
+ lappend lines "\}"
+ return [join $lines \n]
+ }
+
+ typemethod write {g name file} {
+ fileutil::writeFile $file [$type format $g $name]
+ return
+ }
+
+ typemethod layout {format g name file} {
+ set f [fileutil::tempfile c2fdot_]
+ $type write $g $name $f
+ exec dot -T $format -o $file $f
+ file delete $f
+ return
+ }
+
+ # # ## ### ##### ######## #############
+ ## Internal, state
+
+ # # ## ### ##### ######## #############
+ ## Internal, helper methods (formatting, dispatch)
+
+ # # ## ### ##### ######## #############
+ ## Configuration
+
+ pragma -hasinstances no ; # singleton
+ pragma -hastypeinfo no ; # no introspection
+ pragma -hastypedestroy no ; # immortal
+
+ # # ## ### ##### ######## #############
+}
+
+namespace eval ::vc::tools {
+ namespace export dot
+}
+
+# -----------------------------------------------------------------------------
+# Ready
+package provide vc::tools::dot 1.0
+return
Modified tools/cvs2fossil/lib/pkgIndex.tcl from [326b42f768] to [48c254587c].
@@ -28,9 +28,10 @@ package ifneeded vc::fossil::import::cvs::project::sym 1.0 [list source [file join $dir c2f_psym.tcl]] package ifneeded vc::fossil::import::cvs::project::trunk 1.0 [list source [file join $dir c2f_ptrunk.tcl]] package ifneeded vc::fossil::import::cvs::repository 1.0 [list source [file join $dir c2f_repository.tcl]] package ifneeded vc::fossil::import::cvs::state 1.0 [list source [file join $dir c2f_state.tcl]] package ifneeded vc::rcs::parser 1.0 [list source [file join $dir rcsparser.tcl]] +package ifneeded vc::tools::dot 1.0 [list source [file join $dir dot.tcl]] +package ifneeded vc::tools::id 1.0 [list source [file join $dir id.tcl]] package ifneeded vc::tools::log 1.0 [list source [file join $dir log.tcl]] package ifneeded vc::tools::misc 1.0 [list source [file join $dir misc.tcl]] package ifneeded vc::tools::trouble 1.0 [list source [file join $dir trouble.tcl]] -package ifneeded vc::tools::id 1.0 [list source [file join $dir id.tcl]]