Fossil SCM

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.

aku 2007-11-20 06:59 trunk
Commit 7f15be907861e9eb8f8fb9fa0a0baf9caf5d619b
Parent 4e7dd05fc61d66c…
7 files changed +121 -44 +7 +4 +7 -3 +7 -2 +24 +2 -1
~ tools/cvs2fossil/lib/c2f_cyclebreaker.tcl ~ tools/cvs2fossil/lib/c2f_option.tcl ~ tools/cvs2fossil/lib/c2f_pbreakacycle.tcl ~ tools/cvs2fossil/lib/c2f_pbreakrcycle.tcl ~ tools/cvs2fossil/lib/c2f_pbreakscycle.tcl + tools/cvs2fossil/lib/dot.tcl ~ tools/cvs2fossil/lib/pkgIndex.tcl
M tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
+121 -44
--- tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
+++ tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
@@ -18,10 +18,11 @@
1818
1919
 package require Tcl 8.4 ; # Required runtime.
2020
 package require snit ; # OO system.
2121
 package require struct::graph ; # Graph handling.
2222
 package require struct::list ; # Higher order list operations.
23
+package require vc::tools::dot ; # User feedback. DOT export.
2324
 package require vc::tools::log ; # User feedback.
2425
 package require vc::tools::misc ; # Text formatting.
2526
 package require vc::fossil::import::cvs::project::rev ; # Project level changesets
2627
 package require vc::fossil::import::cvs::project::revlink ; # Cycle links.
2728
@@ -30,46 +31,40 @@
3031
3132
 snit::type ::vc::fossil::import::cvs::cyclebreaker {
3233
 # # ## ### ##### ######## #############
3334
 ## Public API
3435
35
- typemethod run {changesets {savecmd {}}} {
36
- ::variable save $savecmd
37
- ::variable at 0
36
+ typemethod dotsto {path} {
37
+ ::variable mydotdestination $path
38
+ return
39
+ }
40
+
41
+ typemethod dot {label changesets} {
42
+ ::variable mydotprefix $label
43
+ ::variable mydotid 0
44
+
45
+ set dg [Setup $changesets 0]
46
+ Mark $dg
47
+ $dg destroy
48
+ return
49
+ }
50
+
51
+ typemethod run {label changesets {savecmd {}}} {
52
+ ::variable mysave $savecmd
53
+ ::variable myat 0
54
+ ::variable mydotprefix $label
55
+ ::variable mydotid 0
3856
3957
 # We create a graph of the revision changesets, using the file
4058
 # level dependencies to construct a first approximation of the
4159
 # dependencies at the project level. Then we look for cycles
4260
 # in that graph and break them.
4361
4462
 # 1. Create nodes for all relevant changesets and a mapping
4563
 # from the revisions to their changesets/nodes.
4664
47
- log write 3 cyclebreaker "Creating changeset graph, filling with nodes"
48
- log write 3 cyclebreaker "Adding [nsp [llength $changesets] node]"
49
-
50
- set dg [struct::graph dg]
51
-
52
- foreach cset $changesets {
53
- dg node insert $cset
54
- dg node set $cset timerange [$cset timerange]
55
- }
56
-
57
- # 2. Find for all relevant changeset their revisions and their
58
- # dependencies. Map the latter back to changesets and
59
- # construct the corresponding arcs.
60
-
61
- log write 3 cyclebreaker {Setting up node dependencies}
62
-
63
- foreach cset $changesets {
64
- foreach succ [$cset successors] {
65
- # Changesets may have dependencies outside of the
66
- # chosen set. These are ignored
67
- if {![dg node exists $succ]} continue
68
- dg arc insert $cset $succ
69
- }
70
- }
65
+ set dg [Setup $changesets]
7166
7267
 # 3. Lastly we iterate the graph topologically. We mark off
7368
 # the nodes which have no predecessors, in order from
7469
 # oldest to youngest, saving and removing dependencies. If
7570
 # we find no nodes without predecessors we have a cycle,
@@ -93,35 +88,68 @@
9388
 return
9489
 }
9590
9691
 # # ## ### ##### ######## #############
9792
 ## Internal methods
93
+
94
+ proc Setup {changesets {log 1}} {
95
+ if {$log} {
96
+ log write 3 cyclebreaker "Creating changeset graph, filling with nodes"
97
+ log write 3 cyclebreaker "Adding [nsp [llength $changesets] node]"
98
+ }
99
+
100
+ set dg [struct::graph dg]
101
+
102
+ foreach cset $changesets {
103
+ $dg node insert $cset
104
+ $dg node set $cset timerange [$cset timerange]
105
+ }
106
+
107
+ # 2. Find for all relevant changeset their revisions and their
108
+ # dependencies. Map the latter back to changesets and
109
+ # construct the corresponding arcs.
110
+
111
+ if {$log} {
112
+ log write 3 cyclebreaker {Setting up node dependencies}
113
+ }
114
+
115
+ foreach cset $changesets {
116
+ foreach succ [$cset successors] {
117
+ # Changesets may have dependencies outside of the
118
+ # chosen set. These are ignored
119
+ if {![$dg node exists $succ]} continue
120
+ $dg arc insert $cset $succ
121
+ }
122
+ }
123
+
124
+ return $dg
125
+ }
98126
99127
 # Instead of searching the whole graph for the degree-0 nodes in
100128
 # each iteration we compute the list once to start, and then only
101129
 # update it incrementally based on the outgoing neighbours of the
102130
 # node chosen for commit.
103131
104132
 proc InitializeCandidates {dg} {
105133
 # bottom = list (list (node, range min, range max))
106
- ::variable bottom
134
+ ::variable mybottom
107135
 foreach n [$dg nodes] {
108136
 if {[$dg node degree -in $n]} continue
109
- lappend bottom [linsert [$dg node get $n timerange] 0 $n]
137
+ lappend mybottom [linsert [$dg node get $n timerange] 0 $n]
110138
 }
111
- set bottom [lsort -index 1 -integer [lsort -index 2 -integer $bottom]]
139
+ set mybottom [lsort -index 1 -integer [lsort -index 2 -integer $mybottom]]
112140
 return
113141
 }
114142
115143
 proc WithoutPredecessor {dg nv} {
116
- ::variable bottom
144
+ ::variable mybottom
117145
118146
 upvar 1 $nv n
119
- if {![llength $bottom]} { return 0 }
147
+ if {![llength $mybottom]} { return 0 }
120148
121
- set n [lindex [lindex $bottom 0] 0]
122
- set bottom [lrange $bottom 1 end]
149
+ set n [lindex [lindex $mybottom 0] 0]
150
+ set mybottom [lrange $mybottom 1 end]
123151
 set changed 0
124152
125153
 # Update list of nodes without predecessor, based on the
126154
 # outgoing neighbours of the chosen node. This should be
127155
 # faster than iterating of the whole set of nodes, finding all
@@ -128,35 +156,35 @@
128156
 # without predecessors, sorting them by time, etc. pp.
129157
 foreach out [$dg nodes -out $n] {
130158
 if {[$dg node degree -in $out] > 1} continue
131159
 # Degree-1 neighbour, will have no predecessors after the
132160
 # removal of n. Put on the list.
133
- lappend bottom [linsert [$dg node get $out timerange] 0 $out]
161
+ lappend mybottom [linsert [$dg node get $out timerange] 0 $out]
134162
 set changed 1
135163
 }
136164
 if {$changed} {
137
- set bottom [lsort -index 1 -integer [lsort -index 2 -integer $bottom]]
165
+ set mybottom [lsort -index 1 -integer [lsort -index 2 -integer $mybottom]]
138166
 }
139167
140168
 # We do not delete the node immediately, to allow the Save
141169
 # procedure to save the dependencies as well (encoded in the
142170
 # arcs).
143171
 return 1
144172
 }
145173
146174
 proc SaveAndRemove {dg n} {
147
- ::variable at
148
- ::variable save
175
+ ::variable myat
176
+ ::variable mysave
149177
150178
 # Give the user of the cycle breaker the opportunity to work
151179
 # with the changeset before it is removed from the graph.
152180
153
- if {[llength $save]} {
154
- uplevel #0 [linsert $save end $at $n]
181
+ if {[llength $mysave]} {
182
+ uplevel #0 [linsert $mysave end $myat $n]
155183
 }
156184
157
- incr at
185
+ incr myat
158186
 $dg node delete $n
159187
 return
160188
 }
161189
162190
 proc FindCycle {dg} {
@@ -229,17 +257,27 @@
229257
 $link destroy
230258
 }
231259
 }
232260
233261
 log write 5 breakrcycle "Breaking cycle ($cprint) by splitting changeset <[$bestnode id]>"
262
+ set ID [$bestnode id]
263
+ Mark $dg -${ID}-before
234264
235265
 set newcsets [$bestlink break]
236266
 $bestlink destroy
237267
238268
 # At this point the old changeset (BESTNODE) is gone
239269
 # already. We remove it from the graph as well and then enter
240270
 # the fragments generated for it.
271
+
272
+ # NOTE. We have to get the list of incoming neighbours and
273
+ # recompute their successors after the new nodes have been
274
+ # inserted. Their outgoing arcs will now go to one or both of
275
+ # the new nodes, and not redoing them may cause us to forget
276
+ # circles, leaving them in, unbroken.
277
+
278
+ set pre [$dg nodes -in $bestnode]
241279
242280
 $dg node delete $bestnode
243281
244282
 foreach cset $newcsets {
245283
 $dg node insert $cset
@@ -252,16 +290,54 @@
252290
 # the chosen set. These are ignored
253291
 if {![$dg node exists $succ]} continue
254292
 $dg arc insert $cset $succ
255293
 }
256294
 }
295
+ foreach cset $pre {
296
+ foreach succ [$cset successors] {
297
+ # Note that the arc may already exist in the graph. If
298
+ # so ignore it. The new changesets may have
299
+ # dependencies outside of the chosen set. These are
300
+ # ignored
301
+ if {![$dg node exists $succ]} continue
302
+ if {[HasArc $dg $cset $succ]} continue;# TODO should be graph method.
303
+ $dg arc insert $cset $succ
304
+ }
305
+ }
306
+
307
+ Mark $dg -${ID}-after
308
+ return
309
+ }
310
+
311
+ # TODO: This should be a graph method.
312
+ proc HasArc {dg a b} {
313
+ #8.5: return [expr {$b in [$dg nodes -out $a]}]
314
+ if {[lsearch -exact [$dg nodes -out $a] $b] < 0} { return 0 }
315
+ return 1
316
+ }
317
+
318
+ proc Mark {dg {suffix {}}} {
319
+ ::variable mydotdestination
320
+ if {$mydotdestination eq ""} return
321
+ ::variable mydotprefix
322
+ ::variable mydotid
323
+ set fname $mydotdestination/${mydotprefix}${mydotid}${suffix}.dot
324
+ file mkdir [file dirname $fname]
325
+ dot write $dg $mydotprefix$suffix $fname
326
+ incr mydotid
327
+
328
+ log write 5 cyclebreaker ".dot export $fname"
257329
 return
258330
 }
259331
260
- typevariable at 0 ; # Counter for commit ids for the changesets.
261
- typevariable bottom {} ; # List of candidate nodes for committing.
262
- typevariable save {} ; # The command to call for each processed node
332
+ typevariable myat 0 ; # Counter for commit ids for the changesets.
333
+ typevariable mybottom {} ; # List of candidate nodes for committing.
334
+ typevariable mysave {} ; # The command to call for each processed node
335
+
336
+ typevariable mydotdestination {} ; # Destination directory for .dot files.
337
+ typevariable mydotprefix {} ; # Prefix for dot files when exporting the graphs.
338
+ typevariable mydotid 0 ; # Counter for dot file name generation.
263339
264340
 # # ## ### ##### ######## #############
265341
 ## Configuration
266342
267343
 pragma -hasinstances no ; # singleton
@@ -278,14 +354,15 @@
278354
 namespace import ::vc::fossil::import::cvs::project::rev
279355
 namespace import ::vc::fossil::import::cvs::project::revlink
280356
 }
281357
 namespace import ::vc::tools::misc::*
282358
 namespace import ::vc::tools::log
359
+ namespace import ::vc::tools::dot
283360
 log register cyclebreaker
284361
 }
285362
 }
286363
287364
 # # ## ### ##### ######## ############# #####################
288365
 ## Ready
289366
290367
 package provide vc::fossil::import::cvs::cyclebreaker 1.0
291368
 return
292369
--- tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
+++ tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
@@ -18,10 +18,11 @@
18
19 package require Tcl 8.4 ; # Required runtime.
20 package require snit ; # OO system.
21 package require struct::graph ; # Graph handling.
22 package require struct::list ; # Higher order list operations.
 
23 package require vc::tools::log ; # User feedback.
24 package require vc::tools::misc ; # Text formatting.
25 package require vc::fossil::import::cvs::project::rev ; # Project level changesets
26 package require vc::fossil::import::cvs::project::revlink ; # Cycle links.
27
@@ -30,46 +31,40 @@
30
31 snit::type ::vc::fossil::import::cvs::cyclebreaker {
32 # # ## ### ##### ######## #############
33 ## Public API
34
35 typemethod run {changesets {savecmd {}}} {
36 ::variable save $savecmd
37 ::variable at 0
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
38
39 # We create a graph of the revision changesets, using the file
40 # level dependencies to construct a first approximation of the
41 # dependencies at the project level. Then we look for cycles
42 # in that graph and break them.
43
44 # 1. Create nodes for all relevant changesets and a mapping
45 # from the revisions to their changesets/nodes.
46
47 log write 3 cyclebreaker "Creating changeset graph, filling with nodes"
48 log write 3 cyclebreaker "Adding [nsp [llength $changesets] node]"
49
50 set dg [struct::graph dg]
51
52 foreach cset $changesets {
53 dg node insert $cset
54 dg node set $cset timerange [$cset timerange]
55 }
56
57 # 2. Find for all relevant changeset their revisions and their
58 # dependencies. Map the latter back to changesets and
59 # construct the corresponding arcs.
60
61 log write 3 cyclebreaker {Setting up node dependencies}
62
63 foreach cset $changesets {
64 foreach succ [$cset successors] {
65 # Changesets may have dependencies outside of the
66 # chosen set. These are ignored
67 if {![dg node exists $succ]} continue
68 dg arc insert $cset $succ
69 }
70 }
71
72 # 3. Lastly we iterate the graph topologically. We mark off
73 # the nodes which have no predecessors, in order from
74 # oldest to youngest, saving and removing dependencies. If
75 # we find no nodes without predecessors we have a cycle,
@@ -93,35 +88,68 @@
93 return
94 }
95
96 # # ## ### ##### ######## #############
97 ## Internal methods
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
98
99 # Instead of searching the whole graph for the degree-0 nodes in
100 # each iteration we compute the list once to start, and then only
101 # update it incrementally based on the outgoing neighbours of the
102 # node chosen for commit.
103
104 proc InitializeCandidates {dg} {
105 # bottom = list (list (node, range min, range max))
106 ::variable bottom
107 foreach n [$dg nodes] {
108 if {[$dg node degree -in $n]} continue
109 lappend bottom [linsert [$dg node get $n timerange] 0 $n]
110 }
111 set bottom [lsort -index 1 -integer [lsort -index 2 -integer $bottom]]
112 return
113 }
114
115 proc WithoutPredecessor {dg nv} {
116 ::variable bottom
117
118 upvar 1 $nv n
119 if {![llength $bottom]} { return 0 }
120
121 set n [lindex [lindex $bottom 0] 0]
122 set bottom [lrange $bottom 1 end]
123 set changed 0
124
125 # Update list of nodes without predecessor, based on the
126 # outgoing neighbours of the chosen node. This should be
127 # faster than iterating of the whole set of nodes, finding all
@@ -128,35 +156,35 @@
128 # without predecessors, sorting them by time, etc. pp.
129 foreach out [$dg nodes -out $n] {
130 if {[$dg node degree -in $out] > 1} continue
131 # Degree-1 neighbour, will have no predecessors after the
132 # removal of n. Put on the list.
133 lappend bottom [linsert [$dg node get $out timerange] 0 $out]
134 set changed 1
135 }
136 if {$changed} {
137 set bottom [lsort -index 1 -integer [lsort -index 2 -integer $bottom]]
138 }
139
140 # We do not delete the node immediately, to allow the Save
141 # procedure to save the dependencies as well (encoded in the
142 # arcs).
143 return 1
144 }
145
146 proc SaveAndRemove {dg n} {
147 ::variable at
148 ::variable save
149
150 # Give the user of the cycle breaker the opportunity to work
151 # with the changeset before it is removed from the graph.
152
153 if {[llength $save]} {
154 uplevel #0 [linsert $save end $at $n]
155 }
156
157 incr at
158 $dg node delete $n
159 return
160 }
161
162 proc FindCycle {dg} {
@@ -229,17 +257,27 @@
229 $link destroy
230 }
231 }
232
233 log write 5 breakrcycle "Breaking cycle ($cprint) by splitting changeset <[$bestnode id]>"
 
 
234
235 set newcsets [$bestlink break]
236 $bestlink destroy
237
238 # At this point the old changeset (BESTNODE) is gone
239 # already. We remove it from the graph as well and then enter
240 # the fragments generated for it.
 
 
 
 
 
 
 
 
241
242 $dg node delete $bestnode
243
244 foreach cset $newcsets {
245 $dg node insert $cset
@@ -252,16 +290,54 @@
252 # the chosen set. These are ignored
253 if {![$dg node exists $succ]} continue
254 $dg arc insert $cset $succ
255 }
256 }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
257 return
258 }
259
260 typevariable at 0 ; # Counter for commit ids for the changesets.
261 typevariable bottom {} ; # List of candidate nodes for committing.
262 typevariable save {} ; # The command to call for each processed node
 
 
 
 
263
264 # # ## ### ##### ######## #############
265 ## Configuration
266
267 pragma -hasinstances no ; # singleton
@@ -278,14 +354,15 @@
278 namespace import ::vc::fossil::import::cvs::project::rev
279 namespace import ::vc::fossil::import::cvs::project::revlink
280 }
281 namespace import ::vc::tools::misc::*
282 namespace import ::vc::tools::log
 
283 log register cyclebreaker
284 }
285 }
286
287 # # ## ### ##### ######## ############# #####################
288 ## Ready
289
290 package provide vc::fossil::import::cvs::cyclebreaker 1.0
291 return
292
--- tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
+++ tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
@@ -18,10 +18,11 @@
18
19 package require Tcl 8.4 ; # Required runtime.
20 package require snit ; # OO system.
21 package require struct::graph ; # Graph handling.
22 package require struct::list ; # Higher order list operations.
23 package require vc::tools::dot ; # User feedback. DOT export.
24 package require vc::tools::log ; # User feedback.
25 package require vc::tools::misc ; # Text formatting.
26 package require vc::fossil::import::cvs::project::rev ; # Project level changesets
27 package require vc::fossil::import::cvs::project::revlink ; # Cycle links.
28
@@ -30,46 +31,40 @@
31
32 snit::type ::vc::fossil::import::cvs::cyclebreaker {
33 # # ## ### ##### ######## #############
34 ## Public API
35
36 typemethod dotsto {path} {
37 ::variable mydotdestination $path
38 return
39 }
40
41 typemethod dot {label changesets} {
42 ::variable mydotprefix $label
43 ::variable mydotid 0
44
45 set dg [Setup $changesets 0]
46 Mark $dg
47 $dg destroy
48 return
49 }
50
51 typemethod run {label changesets {savecmd {}}} {
52 ::variable mysave $savecmd
53 ::variable myat 0
54 ::variable mydotprefix $label
55 ::variable mydotid 0
56
57 # We create a graph of the revision changesets, using the file
58 # level dependencies to construct a first approximation of the
59 # dependencies at the project level. Then we look for cycles
60 # in that graph and break them.
61
62 # 1. Create nodes for all relevant changesets and a mapping
63 # from the revisions to their changesets/nodes.
64
65 set dg [Setup $changesets]
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
66
67 # 3. Lastly we iterate the graph topologically. We mark off
68 # the nodes which have no predecessors, in order from
69 # oldest to youngest, saving and removing dependencies. If
70 # we find no nodes without predecessors we have a cycle,
@@ -93,35 +88,68 @@
88 return
89 }
90
91 # # ## ### ##### ######## #############
92 ## Internal methods
93
94 proc Setup {changesets {log 1}} {
95 if {$log} {
96 log write 3 cyclebreaker "Creating changeset graph, filling with nodes"
97 log write 3 cyclebreaker "Adding [nsp [llength $changesets] node]"
98 }
99
100 set dg [struct::graph dg]
101
102 foreach cset $changesets {
103 $dg node insert $cset
104 $dg node set $cset timerange [$cset timerange]
105 }
106
107 # 2. Find for all relevant changeset their revisions and their
108 # dependencies. Map the latter back to changesets and
109 # construct the corresponding arcs.
110
111 if {$log} {
112 log write 3 cyclebreaker {Setting up node dependencies}
113 }
114
115 foreach cset $changesets {
116 foreach succ [$cset successors] {
117 # Changesets may have dependencies outside of the
118 # chosen set. These are ignored
119 if {![$dg node exists $succ]} continue
120 $dg arc insert $cset $succ
121 }
122 }
123
124 return $dg
125 }
126
127 # Instead of searching the whole graph for the degree-0 nodes in
128 # each iteration we compute the list once to start, and then only
129 # update it incrementally based on the outgoing neighbours of the
130 # node chosen for commit.
131
132 proc InitializeCandidates {dg} {
133 # bottom = list (list (node, range min, range max))
134 ::variable mybottom
135 foreach n [$dg nodes] {
136 if {[$dg node degree -in $n]} continue
137 lappend mybottom [linsert [$dg node get $n timerange] 0 $n]
138 }
139 set mybottom [lsort -index 1 -integer [lsort -index 2 -integer $mybottom]]
140 return
141 }
142
143 proc WithoutPredecessor {dg nv} {
144 ::variable mybottom
145
146 upvar 1 $nv n
147 if {![llength $mybottom]} { return 0 }
148
149 set n [lindex [lindex $mybottom 0] 0]
150 set mybottom [lrange $mybottom 1 end]
151 set changed 0
152
153 # Update list of nodes without predecessor, based on the
154 # outgoing neighbours of the chosen node. This should be
155 # faster than iterating of the whole set of nodes, finding all
@@ -128,35 +156,35 @@
156 # without predecessors, sorting them by time, etc. pp.
157 foreach out [$dg nodes -out $n] {
158 if {[$dg node degree -in $out] > 1} continue
159 # Degree-1 neighbour, will have no predecessors after the
160 # removal of n. Put on the list.
161 lappend mybottom [linsert [$dg node get $out timerange] 0 $out]
162 set changed 1
163 }
164 if {$changed} {
165 set mybottom [lsort -index 1 -integer [lsort -index 2 -integer $mybottom]]
166 }
167
168 # We do not delete the node immediately, to allow the Save
169 # procedure to save the dependencies as well (encoded in the
170 # arcs).
171 return 1
172 }
173
174 proc SaveAndRemove {dg n} {
175 ::variable myat
176 ::variable mysave
177
178 # Give the user of the cycle breaker the opportunity to work
179 # with the changeset before it is removed from the graph.
180
181 if {[llength $mysave]} {
182 uplevel #0 [linsert $mysave end $myat $n]
183 }
184
185 incr myat
186 $dg node delete $n
187 return
188 }
189
190 proc FindCycle {dg} {
@@ -229,17 +257,27 @@
257 $link destroy
258 }
259 }
260
261 log write 5 breakrcycle "Breaking cycle ($cprint) by splitting changeset <[$bestnode id]>"
262 set ID [$bestnode id]
263 Mark $dg -${ID}-before
264
265 set newcsets [$bestlink break]
266 $bestlink destroy
267
268 # At this point the old changeset (BESTNODE) is gone
269 # already. We remove it from the graph as well and then enter
270 # the fragments generated for it.
271
272 # NOTE. We have to get the list of incoming neighbours and
273 # recompute their successors after the new nodes have been
274 # inserted. Their outgoing arcs will now go to one or both of
275 # the new nodes, and not redoing them may cause us to forget
276 # circles, leaving them in, unbroken.
277
278 set pre [$dg nodes -in $bestnode]
279
280 $dg node delete $bestnode
281
282 foreach cset $newcsets {
283 $dg node insert $cset
@@ -252,16 +290,54 @@
290 # the chosen set. These are ignored
291 if {![$dg node exists $succ]} continue
292 $dg arc insert $cset $succ
293 }
294 }
295 foreach cset $pre {
296 foreach succ [$cset successors] {
297 # Note that the arc may already exist in the graph. If
298 # so ignore it. The new changesets may have
299 # dependencies outside of the chosen set. These are
300 # ignored
301 if {![$dg node exists $succ]} continue
302 if {[HasArc $dg $cset $succ]} continue;# TODO should be graph method.
303 $dg arc insert $cset $succ
304 }
305 }
306
307 Mark $dg -${ID}-after
308 return
309 }
310
311 # TODO: This should be a graph method.
312 proc HasArc {dg a b} {
313 #8.5: return [expr {$b in [$dg nodes -out $a]}]
314 if {[lsearch -exact [$dg nodes -out $a] $b] < 0} { return 0 }
315 return 1
316 }
317
318 proc Mark {dg {suffix {}}} {
319 ::variable mydotdestination
320 if {$mydotdestination eq ""} return
321 ::variable mydotprefix
322 ::variable mydotid
323 set fname $mydotdestination/${mydotprefix}${mydotid}${suffix}.dot
324 file mkdir [file dirname $fname]
325 dot write $dg $mydotprefix$suffix $fname
326 incr mydotid
327
328 log write 5 cyclebreaker ".dot export $fname"
329 return
330 }
331
332 typevariable myat 0 ; # Counter for commit ids for the changesets.
333 typevariable mybottom {} ; # List of candidate nodes for committing.
334 typevariable mysave {} ; # The command to call for each processed node
335
336 typevariable mydotdestination {} ; # Destination directory for .dot files.
337 typevariable mydotprefix {} ; # Prefix for dot files when exporting the graphs.
338 typevariable mydotid 0 ; # Counter for dot file name generation.
339
340 # # ## ### ##### ######## #############
341 ## Configuration
342
343 pragma -hasinstances no ; # singleton
@@ -278,14 +354,15 @@
354 namespace import ::vc::fossil::import::cvs::project::rev
355 namespace import ::vc::fossil::import::cvs::project::revlink
356 }
357 namespace import ::vc::tools::misc::*
358 namespace import ::vc::tools::log
359 namespace import ::vc::tools::dot
360 log register cyclebreaker
361 }
362 }
363
364 # # ## ### ##### ######## ############# #####################
365 ## Ready
366
367 package provide vc::fossil::import::cvs::cyclebreaker 1.0
368 return
369
M tools/cvs2fossil/lib/c2f_option.tcl
+7
--- tools/cvs2fossil/lib/c2f_option.tcl
+++ tools/cvs2fossil/lib/c2f_option.tcl
@@ -26,10 +26,11 @@
2626
 package require vc::fossil::import::cvs::pass ; # Pass management
2727
 package require vc::fossil::import::cvs::pass::collar ; # Pass I.
2828
 package require vc::fossil::import::cvs::repository ; # Repository management
2929
 package require vc::fossil::import::cvs::state ; # State storage
3030
 package require vc::fossil::import::cvs::project::sym ; # Project level symbols
31
+package require vc::fossil::import::cvs::cyclebreaker ; # Breaking dependency cycles.
3132
3233
 # # ## ### ##### ######## ############# #####################
3334
 ##
3435
3536
 snit::type ::vc::fossil::import::cvs::option {
@@ -77,10 +78,11 @@
7778
 --trunk-only { repository trunkonly! }
7879
 --exclude { project::sym exclude [Value arguments] }
7980
 --force-tag { project::sym forcetag [Value arguments] }
8081
 --force-branch { project::sym forcebranch [Value arguments] }
8182
 --batch { log noprogress }
83
+ --dots { cyclebreaker dotsto [Value arguments] }
8284
 default {
8385
 Usage $badoption$option\n$gethelp
8486
 }
8587
 }
8688
 }
@@ -139,10 +141,14 @@
139141
 trouble info " Force the named symbol from all or just"
140142
 trouble info " the specified project to be converted as"
141143
 trouble info " branch. Both project and symbol names"
142144
 trouble info " are glob patterns."
143145
 trouble info ""
146
+ trouble info " --dots PATH Write the changeset graphs before, after,"
147
+ trouble info " and during breaking the of cycles to the"
148
+ trouble info " direcotry PATH, using GraphViz's dot format"
149
+ trouble info ""
144150
145151
 # --project, --cache
146152
 # ...
147153
 return
148154
 }
@@ -213,10 +219,11 @@
213219
 namespace export option
214220
 namespace eval option {
215221
 namespace import ::vc::tools::misc::striptrailingslash
216222
 namespace import ::vc::fossil::import::cvs::pass
217223
 namespace import ::vc::fossil::import::cvs::pass::collar
224
+ namespace import ::vc::fossil::import::cvs::cyclebreaker
218225
 namespace import ::vc::fossil::import::cvs::repository
219226
 namespace import ::vc::fossil::import::cvs::state
220227
 namespace eval project {
221228
 namespace import ::vc::fossil::import::cvs::project::sym
222229
 }
223230
--- tools/cvs2fossil/lib/c2f_option.tcl
+++ tools/cvs2fossil/lib/c2f_option.tcl
@@ -26,10 +26,11 @@
26 package require vc::fossil::import::cvs::pass ; # Pass management
27 package require vc::fossil::import::cvs::pass::collar ; # Pass I.
28 package require vc::fossil::import::cvs::repository ; # Repository management
29 package require vc::fossil::import::cvs::state ; # State storage
30 package require vc::fossil::import::cvs::project::sym ; # Project level symbols
 
31
32 # # ## ### ##### ######## ############# #####################
33 ##
34
35 snit::type ::vc::fossil::import::cvs::option {
@@ -77,10 +78,11 @@
77 --trunk-only { repository trunkonly! }
78 --exclude { project::sym exclude [Value arguments] }
79 --force-tag { project::sym forcetag [Value arguments] }
80 --force-branch { project::sym forcebranch [Value arguments] }
81 --batch { log noprogress }
 
82 default {
83 Usage $badoption$option\n$gethelp
84 }
85 }
86 }
@@ -139,10 +141,14 @@
139 trouble info " Force the named symbol from all or just"
140 trouble info " the specified project to be converted as"
141 trouble info " branch. Both project and symbol names"
142 trouble info " are glob patterns."
143 trouble info ""
 
 
 
 
144
145 # --project, --cache
146 # ...
147 return
148 }
@@ -213,10 +219,11 @@
213 namespace export option
214 namespace eval option {
215 namespace import ::vc::tools::misc::striptrailingslash
216 namespace import ::vc::fossil::import::cvs::pass
217 namespace import ::vc::fossil::import::cvs::pass::collar
 
218 namespace import ::vc::fossil::import::cvs::repository
219 namespace import ::vc::fossil::import::cvs::state
220 namespace eval project {
221 namespace import ::vc::fossil::import::cvs::project::sym
222 }
223
--- tools/cvs2fossil/lib/c2f_option.tcl
+++ tools/cvs2fossil/lib/c2f_option.tcl
@@ -26,10 +26,11 @@
26 package require vc::fossil::import::cvs::pass ; # Pass management
27 package require vc::fossil::import::cvs::pass::collar ; # Pass I.
28 package require vc::fossil::import::cvs::repository ; # Repository management
29 package require vc::fossil::import::cvs::state ; # State storage
30 package require vc::fossil::import::cvs::project::sym ; # Project level symbols
31 package require vc::fossil::import::cvs::cyclebreaker ; # Breaking dependency cycles.
32
33 # # ## ### ##### ######## ############# #####################
34 ##
35
36 snit::type ::vc::fossil::import::cvs::option {
@@ -77,10 +78,11 @@
78 --trunk-only { repository trunkonly! }
79 --exclude { project::sym exclude [Value arguments] }
80 --force-tag { project::sym forcetag [Value arguments] }
81 --force-branch { project::sym forcebranch [Value arguments] }
82 --batch { log noprogress }
83 --dots { cyclebreaker dotsto [Value arguments] }
84 default {
85 Usage $badoption$option\n$gethelp
86 }
87 }
88 }
@@ -139,10 +141,14 @@
141 trouble info " Force the named symbol from all or just"
142 trouble info " the specified project to be converted as"
143 trouble info " branch. Both project and symbol names"
144 trouble info " are glob patterns."
145 trouble info ""
146 trouble info " --dots PATH Write the changeset graphs before, after,"
147 trouble info " and during breaking the of cycles to the"
148 trouble info " direcotry PATH, using GraphViz's dot format"
149 trouble info ""
150
151 # --project, --cache
152 # ...
153 return
154 }
@@ -213,10 +219,11 @@
219 namespace export option
220 namespace eval option {
221 namespace import ::vc::tools::misc::striptrailingslash
222 namespace import ::vc::fossil::import::cvs::pass
223 namespace import ::vc::fossil::import::cvs::pass::collar
224 namespace import ::vc::fossil::import::cvs::cyclebreaker
225 namespace import ::vc::fossil::import::cvs::repository
226 namespace import ::vc::fossil::import::cvs::state
227 namespace eval project {
228 namespace import ::vc::fossil::import::cvs::project::sym
229 }
230
M tools/cvs2fossil/lib/c2f_pbreakacycle.tcl
+4
--- tools/cvs2fossil/lib/c2f_pbreakacycle.tcl
+++ tools/cvs2fossil/lib/c2f_pbreakacycle.tcl
@@ -56,10 +56,14 @@
5656
 }
5757
5858
 typemethod run {} {
5959
 # Pass manager interface. Executed to perform the
6060
 # functionality of the pass.
61
+
62
+ set changesets [project::rev all]
63
+ cyclebreaker dot break-all-start $changesets
64
+
6165
 return
6266
 }
6367
6468
 typemethod discard {} {
6569
 # Pass manager interface. Executed for all passes after the
6670
--- tools/cvs2fossil/lib/c2f_pbreakacycle.tcl
+++ tools/cvs2fossil/lib/c2f_pbreakacycle.tcl
@@ -56,10 +56,14 @@
56 }
57
58 typemethod run {} {
59 # Pass manager interface. Executed to perform the
60 # functionality of the pass.
 
 
 
 
61 return
62 }
63
64 typemethod discard {} {
65 # Pass manager interface. Executed for all passes after the
66
--- tools/cvs2fossil/lib/c2f_pbreakacycle.tcl
+++ tools/cvs2fossil/lib/c2f_pbreakacycle.tcl
@@ -56,10 +56,14 @@
56 }
57
58 typemethod run {} {
59 # Pass manager interface. Executed to perform the
60 # functionality of the pass.
61
62 set changesets [project::rev all]
63 cyclebreaker dot break-all-start $changesets
64
65 return
66 }
67
68 typemethod discard {} {
69 # Pass manager interface. Executed for all passes after the
70
M tools/cvs2fossil/lib/c2f_pbreakrcycle.tcl
+7 -3
--- tools/cvs2fossil/lib/c2f_pbreakrcycle.tcl
+++ tools/cvs2fossil/lib/c2f_pbreakrcycle.tcl
@@ -72,15 +72,19 @@
7272
7373
 typemethod run {} {
7474
 # Pass manager interface. Executed to perform the
7575
 # functionality of the pass.
7676
77
+ set changesets [struct::list filter [project::rev all] [myproc IsByRevision]]
78
+ cyclebreaker dot break-rev-start $changesets
79
+
7780
 state transaction {
78
- cyclebreaker run [struct::list filter [project::rev all] \
79
- [myproc IsByRevision]] \
80
- [myproc SaveOrder]
81
+ cyclebreaker run break-rev $changesets [myproc SaveOrder]
8182
 }
83
+
84
+ set changesets [struct::list filter [project::rev all] [myproc IsByRevision]]
85
+ cyclebreaker dot break-rev-done $changesets
8286
8387
 repository printcsetstatistics
8488
 return
8589
 }
8690
8791
--- tools/cvs2fossil/lib/c2f_pbreakrcycle.tcl
+++ tools/cvs2fossil/lib/c2f_pbreakrcycle.tcl
@@ -72,15 +72,19 @@
72
73 typemethod run {} {
74 # Pass manager interface. Executed to perform the
75 # functionality of the pass.
76
 
 
 
77 state transaction {
78 cyclebreaker run [struct::list filter [project::rev all] \
79 [myproc IsByRevision]] \
80 [myproc SaveOrder]
81 }
 
 
 
82
83 repository printcsetstatistics
84 return
85 }
86
87
--- tools/cvs2fossil/lib/c2f_pbreakrcycle.tcl
+++ tools/cvs2fossil/lib/c2f_pbreakrcycle.tcl
@@ -72,15 +72,19 @@
72
73 typemethod run {} {
74 # Pass manager interface. Executed to perform the
75 # functionality of the pass.
76
77 set changesets [struct::list filter [project::rev all] [myproc IsByRevision]]
78 cyclebreaker dot break-rev-start $changesets
79
80 state transaction {
81 cyclebreaker run break-rev $changesets [myproc SaveOrder]
 
 
82 }
83
84 set changesets [struct::list filter [project::rev all] [myproc IsByRevision]]
85 cyclebreaker dot break-rev-done $changesets
86
87 repository printcsetstatistics
88 return
89 }
90
91
M tools/cvs2fossil/lib/c2f_pbreakscycle.tcl
+7 -2
--- tools/cvs2fossil/lib/c2f_pbreakscycle.tcl
+++ tools/cvs2fossil/lib/c2f_pbreakscycle.tcl
@@ -60,14 +60,19 @@
6060
6161
 typemethod run {} {
6262
 # Pass manager interface. Executed to perform the
6363
 # functionality of the pass.
6464
65
+ set changesets [struct::list filter [project::rev all] [myproc IsBySymbol]]
66
+ cyclebreaker dot break-sym-start $changesets
67
+
6568
 state transaction {
66
- cyclebreaker run [struct::list filter [project::rev all] \
67
- [myproc IsBySymbol]]
69
+ cyclebreaker run break-sym $changesets
6870
 }
71
+
72
+ set changesets [struct::list filter [project::rev all] [myproc IsBySymbol]]
73
+ cyclebreaker dot break-sym-done $changesets
6974
7075
 repository printcsetstatistics
7176
 return
7277
 }
7378
7479
7580
ADDED tools/cvs2fossil/lib/dot.tcl
--- tools/cvs2fossil/lib/c2f_pbreakscycle.tcl
+++ tools/cvs2fossil/lib/c2f_pbreakscycle.tcl
@@ -60,14 +60,19 @@
60
61 typemethod run {} {
62 # Pass manager interface. Executed to perform the
63 # functionality of the pass.
64
 
 
 
65 state transaction {
66 cyclebreaker run [struct::list filter [project::rev all] \
67 [myproc IsBySymbol]]
68 }
 
 
 
69
70 repository printcsetstatistics
71 return
72 }
73
74
75 DDED tools/cvs2fossil/lib/dot.tcl
--- tools/cvs2fossil/lib/c2f_pbreakscycle.tcl
+++ tools/cvs2fossil/lib/c2f_pbreakscycle.tcl
@@ -60,14 +60,19 @@
60
61 typemethod run {} {
62 # Pass manager interface. Executed to perform the
63 # functionality of the pass.
64
65 set changesets [struct::list filter [project::rev all] [myproc IsBySymbol]]
66 cyclebreaker dot break-sym-start $changesets
67
68 state transaction {
69 cyclebreaker run break-sym $changesets
 
70 }
71
72 set changesets [struct::list filter [project::rev all] [myproc IsBySymbol]]
73 cyclebreaker dot break-sym-done $changesets
74
75 repository printcsetstatistics
76 return
77 }
78
79
80 DDED tools/cvs2fossil/lib/dot.tcl
A tools/cvs2fossil/lib/dot.tcl
+24
--- a/tools/cvs2fossil/lib/dot.tcl
+++ b/tools/cvs2fossil/lib/dot.tcl
@@ -0,0 +1,24 @@
1
+## -*- tcl -*-
2
+# # ## ### ##### ######## ############# #####################
3
+## Copyright (c) 2007 Andreas Kupries.
4
+#
5
+# This software is licensed as described in the file LICENSE, which
6
+# you should have received as part of this distribution.
7
+#
8
+# This software consists of voluntary contributions made by many
9
+# individuals. For exact contribution history, see the revision
10
+# history and logs, available at http://fossil-scm.hwaci.com/fossil
11
+# # ## ### ##### ######## ############# #####################
12
+
13
+## Utility package, export graph data to dot format for formatting
14
+## with neato et. all
15
+
16
+# # ## ### ##### ######## ############# #####################
17
+## Requirements
18
+
19
+package require Tcl 8.4 ; # Required ru cmd "[$n id] \["
20
+ append cmd " label=\"<[$n id]>\""
21
+
22
+ if {[$g node keyexists $n shape]} {
23
+ append cmd " shape=[$g node get $n shape]"
24
+[[$g arc source $a] id]
--- a/tools/cvs2fossil/lib/dot.tcl
+++ b/tools/cvs2fossil/lib/dot.tcl
@@ -0,0 +1,24 @@
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
--- a/tools/cvs2fossil/lib/dot.tcl
+++ b/tools/cvs2fossil/lib/dot.tcl
@@ -0,0 +1,24 @@
1 ## -*- tcl -*-
2 # # ## ### ##### ######## ############# #####################
3 ## Copyright (c) 2007 Andreas Kupries.
4 #
5 # This software is licensed as described in the file LICENSE, which
6 # you should have received as part of this distribution.
7 #
8 # This software consists of voluntary contributions made by many
9 # individuals. For exact contribution history, see the revision
10 # history and logs, available at http://fossil-scm.hwaci.com/fossil
11 # # ## ### ##### ######## ############# #####################
12
13 ## Utility package, export graph data to dot format for formatting
14 ## with neato et. all
15
16 # # ## ### ##### ######## ############# #####################
17 ## Requirements
18
19 package require Tcl 8.4 ; # Required ru cmd "[$n id] \["
20 append cmd " label=\"<[$n id]>\""
21
22 if {[$g node keyexists $n shape]} {
23 append cmd " shape=[$g node get $n shape]"
24 [[$g arc source $a] id]
M tools/cvs2fossil/lib/pkgIndex.tcl
+2 -1
--- tools/cvs2fossil/lib/pkgIndex.tcl
+++ tools/cvs2fossil/lib/pkgIndex.tcl
@@ -28,9 +28,10 @@
2828
 package ifneeded vc::fossil::import::cvs::project::sym 1.0 [list source [file join $dir c2f_psym.tcl]]
2929
 package ifneeded vc::fossil::import::cvs::project::trunk 1.0 [list source [file join $dir c2f_ptrunk.tcl]]
3030
 package ifneeded vc::fossil::import::cvs::repository 1.0 [list source [file join $dir c2f_repository.tcl]]
3131
 package ifneeded vc::fossil::import::cvs::state 1.0 [list source [file join $dir c2f_state.tcl]]
3232
 package ifneeded vc::rcs::parser 1.0 [list source [file join $dir rcsparser.tcl]]
33
+package ifneeded vc::tools::dot 1.0 [list source [file join $dir dot.tcl]]
34
+package ifneeded vc::tools::id 1.0 [list source [file join $dir id.tcl]]
3335
 package ifneeded vc::tools::log 1.0 [list source [file join $dir log.tcl]]
3436
 package ifneeded vc::tools::misc 1.0 [list source [file join $dir misc.tcl]]
3537
 package ifneeded vc::tools::trouble 1.0 [list source [file join $dir trouble.tcl]]
36
-package ifneeded vc::tools::id 1.0 [list source [file join $dir id.tcl]]
3738
--- tools/cvs2fossil/lib/pkgIndex.tcl
+++ tools/cvs2fossil/lib/pkgIndex.tcl
@@ -28,9 +28,10 @@
28 package ifneeded vc::fossil::import::cvs::project::sym 1.0 [list source [file join $dir c2f_psym.tcl]]
29 package ifneeded vc::fossil::import::cvs::project::trunk 1.0 [list source [file join $dir c2f_ptrunk.tcl]]
30 package ifneeded vc::fossil::import::cvs::repository 1.0 [list source [file join $dir c2f_repository.tcl]]
31 package ifneeded vc::fossil::import::cvs::state 1.0 [list source [file join $dir c2f_state.tcl]]
32 package ifneeded vc::rcs::parser 1.0 [list source [file join $dir rcsparser.tcl]]
 
 
33 package ifneeded vc::tools::log 1.0 [list source [file join $dir log.tcl]]
34 package ifneeded vc::tools::misc 1.0 [list source [file join $dir misc.tcl]]
35 package ifneeded vc::tools::trouble 1.0 [list source [file join $dir trouble.tcl]]
36 package ifneeded vc::tools::id 1.0 [list source [file join $dir id.tcl]]
37
--- tools/cvs2fossil/lib/pkgIndex.tcl
+++ tools/cvs2fossil/lib/pkgIndex.tcl
@@ -28,9 +28,10 @@
28 package ifneeded vc::fossil::import::cvs::project::sym 1.0 [list source [file join $dir c2f_psym.tcl]]
29 package ifneeded vc::fossil::import::cvs::project::trunk 1.0 [list source [file join $dir c2f_ptrunk.tcl]]
30 package ifneeded vc::fossil::import::cvs::repository 1.0 [list source [file join $dir c2f_repository.tcl]]
31 package ifneeded vc::fossil::import::cvs::state 1.0 [list source [file join $dir c2f_state.tcl]]
32 package ifneeded vc::rcs::parser 1.0 [list source [file join $dir rcsparser.tcl]]
33 package ifneeded vc::tools::dot 1.0 [list source [file join $dir dot.tcl]]
34 package ifneeded vc::tools::id 1.0 [list source [file join $dir id.tcl]]
35 package ifneeded vc::tools::log 1.0 [list source [file join $dir log.tcl]]
36 package ifneeded vc::tools::misc 1.0 [list source [file join $dir misc.tcl]]
37 package ifneeded vc::tools::trouble 1.0 [list source [file join $dir trouble.tcl]]
 
38

Keyboard Shortcuts

Open search /
Next entry (timeline) j
Previous entry (timeline) k
Open focused entry Enter
Show this help ?
Toggle theme Top nav button