Fossil SCM
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.
Commit
ad7d5c2d10666dd81a2e111590dcce632d938d2c
Parent
59207428e2f5aa5…
1 file changed
+57
-34
| --- tools/cvs2fossil/lib/c2f_cyclebreaker.tcl | ||
| +++ tools/cvs2fossil/lib/c2f_cyclebreaker.tcl | ||
| @@ -96,10 +96,11 @@ | ||
| 96 | 96 | while {1} { |
| 97 | 97 | while {[WithoutPredecessor $dg n]} { |
| 98 | 98 | ProcessedHook $n $myat |
| 99 | 99 | $dg node delete $n |
| 100 | 100 | incr myat |
| 101 | + ShowPendingNodes | |
| 101 | 102 | } |
| 102 | 103 | |
| 103 | 104 | if {![llength [dg nodes]]} break |
| 104 | 105 | |
| 105 | 106 | BreakCycleHook $dg |
| @@ -127,10 +128,15 @@ | ||
| 127 | 128 | |
| 128 | 129 | typemethod break {graph} { |
| 129 | 130 | BreakCycle $graph [FindCycle $graph] |
| 130 | 131 | return |
| 131 | 132 | } |
| 133 | + | |
| 134 | + typemethod replace {graph n replacements} { | |
| 135 | + Replace $graph $n $replacements | |
| 136 | + return | |
| 137 | + } | |
| 132 | 138 | |
| 133 | 139 | # # ## ### ##### ######## ############# |
| 134 | 140 | ## Internal methods |
| 135 | 141 | |
| 136 | 142 | proc Setup {changesets {log 1}} { |
| @@ -182,10 +188,11 @@ | ||
| 182 | 188 | foreach n [$dg nodes] { |
| 183 | 189 | if {[$dg node degree -in $n]} continue |
| 184 | 190 | lappend mybottom [linsert [$dg node get $n timerange] 0 $n] |
| 185 | 191 | } |
| 186 | 192 | set mybottom [lsort -index 1 -integer [lsort -index 2 -integer $mybottom]] |
| 193 | + ShowPendingNodes | |
| 187 | 194 | return |
| 188 | 195 | } |
| 189 | 196 | |
| 190 | 197 | proc WithoutPredecessor {dg nv} { |
| 191 | 198 | ::variable mybottom |
| @@ -216,10 +223,20 @@ | ||
| 216 | 223 | # procedure to save the dependencies as well (encoded in the |
| 217 | 224 | # arcs). |
| 218 | 225 | return 1 |
| 219 | 226 | } |
| 220 | 227 | |
| 228 | + proc ShowPendingNodes {} { | |
| 229 | + if {[log verbosity?] < 10} return | |
| 230 | + ::variable mybottom | |
| 231 | + log write 10 cyclebreaker \ | |
| 232 | + "Pending: [struct::list map $mybottom [myproc FormatPendingItem]]" | |
| 233 | + return | |
| 234 | + } | |
| 235 | + | |
| 236 | + proc FormatPendingItem {item} { lreplace $item 0 0 <[[lindex $item 0] id]> } | |
| 237 | + | |
| 221 | 238 | proc FindCycle {dg} { |
| 222 | 239 | # This procedure is run if and only the graph is not empty and |
| 223 | 240 | # all nodes have predecessors. This means that each node is |
| 224 | 241 | # either part of a cycle or (indirectly) depending on a node |
| 225 | 242 | # in a cycle. We can start at an arbitrary node, follow its |
| @@ -298,44 +315,11 @@ | ||
| 298 | 315 | |
| 299 | 316 | # At this point the old changeset (BESTNODE) is gone |
| 300 | 317 | # already. We remove it from the graph as well and then enter |
| 301 | 318 | # the fragments generated for it. |
| 302 | 319 | |
| 303 | - # NOTE. We have to get the list of incoming neighbours and | |
| 304 | - # recompute their successors after the new nodes have been | |
| 305 | - # inserted. Their outgoing arcs will now go to one or both of | |
| 306 | - # the new nodes, and not redoing them may cause us to forget | |
| 307 | - # circles, leaving them in, unbroken. | |
| 308 | - | |
| 309 | - set pre [$dg nodes -in $bestnode] | |
| 310 | - | |
| 311 | - $dg node delete $bestnode | |
| 312 | - | |
| 313 | - foreach cset $newcsets { | |
| 314 | - $dg node insert $cset | |
| 315 | - $dg node set $cset timerange [$cset timerange] | |
| 316 | - } | |
| 317 | - | |
| 318 | - foreach cset $newcsets { | |
| 319 | - foreach succ [$cset successors] { | |
| 320 | - # The new changesets may have dependencies outside of | |
| 321 | - # the chosen set. These are ignored | |
| 322 | - if {![$dg node exists $succ]} continue | |
| 323 | - $dg arc insert $cset $succ | |
| 324 | - } | |
| 325 | - } | |
| 326 | - foreach cset $pre { | |
| 327 | - foreach succ [$cset successors] { | |
| 328 | - # Note that the arc may already exist in the graph. If | |
| 329 | - # so ignore it. The new changesets may have | |
| 330 | - # dependencies outside of the chosen set. These are | |
| 331 | - # ignored | |
| 332 | - if {![$dg node exists $succ]} continue | |
| 333 | - if {[HasArc $dg $cset $succ]} continue;# TODO should be graph method. | |
| 334 | - $dg arc insert $cset $succ | |
| 335 | - } | |
| 336 | - } | |
| 320 | + Replace $dg $bestnode $newcsets | |
| 337 | 321 | |
| 338 | 322 | Mark $dg -${ID}-after |
| 339 | 323 | return |
| 340 | 324 | } |
| 341 | 325 | |
| @@ -355,10 +339,49 @@ | ||
| 355 | 339 | file mkdir [file dirname $fname] |
| 356 | 340 | dot write $dg $mydotprefix$suffix $fname |
| 357 | 341 | incr mydotid |
| 358 | 342 | |
| 359 | 343 | log write 5 cyclebreaker ".dot export $fname" |
| 344 | + return | |
| 345 | + } | |
| 346 | + | |
| 347 | + proc Replace {dg n replacements} { | |
| 348 | + # NOTE. We have to get the list of incoming neighbours and | |
| 349 | + # recompute their successors after the new nodes have been | |
| 350 | + # inserted. Their outgoing arcs will now go to one or both of | |
| 351 | + # the new nodes, and not redoing them may cause us to forget | |
| 352 | + # circles, leaving them in, unbroken. | |
| 353 | + | |
| 354 | + set pre [$dg nodes -in $n] | |
| 355 | + | |
| 356 | + $dg node delete $n | |
| 357 | + | |
| 358 | + foreach cset $replacements { | |
| 359 | + $dg node insert $cset | |
| 360 | + $dg node set $cset timerange [$cset timerange] | |
| 361 | + } | |
| 362 | + | |
| 363 | + foreach cset $replacements { | |
| 364 | + foreach succ [$cset successors] { | |
| 365 | + # The new changesets may have dependencies outside of | |
| 366 | + # the chosen set. These are ignored | |
| 367 | + if {![$dg node exists $succ]} continue | |
| 368 | + $dg arc insert $cset $succ | |
| 369 | + } | |
| 370 | + } | |
| 371 | + foreach cset $pre { | |
| 372 | + foreach succ [$cset successors] { | |
| 373 | + # Note that the arc may already exist in the graph. If | |
| 374 | + # so ignore it. The new changesets may have | |
| 375 | + # dependencies outside of the chosen set. These are | |
| 376 | + # ignored | |
| 377 | + if {![$dg node exists $succ]} continue | |
| 378 | + if {[HasArc $dg $cset $succ]} continue;# TODO should be graph method. | |
| 379 | + $dg arc insert $cset $succ | |
| 380 | + } | |
| 381 | + } | |
| 382 | + | |
| 360 | 383 | return |
| 361 | 384 | } |
| 362 | 385 | |
| 363 | 386 | # # ## ### ##### ######## ############# |
| 364 | 387 | ## Callback invokation ... |
| 365 | 388 |
| --- tools/cvs2fossil/lib/c2f_cyclebreaker.tcl | |
| +++ tools/cvs2fossil/lib/c2f_cyclebreaker.tcl | |
| @@ -96,10 +96,11 @@ | |
| 96 | while {1} { |
| 97 | while {[WithoutPredecessor $dg n]} { |
| 98 | ProcessedHook $n $myat |
| 99 | $dg node delete $n |
| 100 | incr myat |
| 101 | } |
| 102 | |
| 103 | if {![llength [dg nodes]]} break |
| 104 | |
| 105 | BreakCycleHook $dg |
| @@ -127,10 +128,15 @@ | |
| 127 | |
| 128 | typemethod break {graph} { |
| 129 | BreakCycle $graph [FindCycle $graph] |
| 130 | return |
| 131 | } |
| 132 | |
| 133 | # # ## ### ##### ######## ############# |
| 134 | ## Internal methods |
| 135 | |
| 136 | proc Setup {changesets {log 1}} { |
| @@ -182,10 +188,11 @@ | |
| 182 | foreach n [$dg nodes] { |
| 183 | if {[$dg node degree -in $n]} continue |
| 184 | lappend mybottom [linsert [$dg node get $n timerange] 0 $n] |
| 185 | } |
| 186 | set mybottom [lsort -index 1 -integer [lsort -index 2 -integer $mybottom]] |
| 187 | return |
| 188 | } |
| 189 | |
| 190 | proc WithoutPredecessor {dg nv} { |
| 191 | ::variable mybottom |
| @@ -216,10 +223,20 @@ | |
| 216 | # procedure to save the dependencies as well (encoded in the |
| 217 | # arcs). |
| 218 | return 1 |
| 219 | } |
| 220 | |
| 221 | proc FindCycle {dg} { |
| 222 | # This procedure is run if and only the graph is not empty and |
| 223 | # all nodes have predecessors. This means that each node is |
| 224 | # either part of a cycle or (indirectly) depending on a node |
| 225 | # in a cycle. We can start at an arbitrary node, follow its |
| @@ -298,44 +315,11 @@ | |
| 298 | |
| 299 | # At this point the old changeset (BESTNODE) is gone |
| 300 | # already. We remove it from the graph as well and then enter |
| 301 | # the fragments generated for it. |
| 302 | |
| 303 | # NOTE. We have to get the list of incoming neighbours and |
| 304 | # recompute their successors after the new nodes have been |
| 305 | # inserted. Their outgoing arcs will now go to one or both of |
| 306 | # the new nodes, and not redoing them may cause us to forget |
| 307 | # circles, leaving them in, unbroken. |
| 308 | |
| 309 | set pre [$dg nodes -in $bestnode] |
| 310 | |
| 311 | $dg node delete $bestnode |
| 312 | |
| 313 | foreach cset $newcsets { |
| 314 | $dg node insert $cset |
| 315 | $dg node set $cset timerange [$cset timerange] |
| 316 | } |
| 317 | |
| 318 | foreach cset $newcsets { |
| 319 | foreach succ [$cset successors] { |
| 320 | # The new changesets may have dependencies outside of |
| 321 | # the chosen set. These are ignored |
| 322 | if {![$dg node exists $succ]} continue |
| 323 | $dg arc insert $cset $succ |
| 324 | } |
| 325 | } |
| 326 | foreach cset $pre { |
| 327 | foreach succ [$cset successors] { |
| 328 | # Note that the arc may already exist in the graph. If |
| 329 | # so ignore it. The new changesets may have |
| 330 | # dependencies outside of the chosen set. These are |
| 331 | # ignored |
| 332 | if {![$dg node exists $succ]} continue |
| 333 | if {[HasArc $dg $cset $succ]} continue;# TODO should be graph method. |
| 334 | $dg arc insert $cset $succ |
| 335 | } |
| 336 | } |
| 337 | |
| 338 | Mark $dg -${ID}-after |
| 339 | return |
| 340 | } |
| 341 | |
| @@ -355,10 +339,49 @@ | |
| 355 | file mkdir [file dirname $fname] |
| 356 | dot write $dg $mydotprefix$suffix $fname |
| 357 | incr mydotid |
| 358 | |
| 359 | log write 5 cyclebreaker ".dot export $fname" |
| 360 | return |
| 361 | } |
| 362 | |
| 363 | # # ## ### ##### ######## ############# |
| 364 | ## Callback invokation ... |
| 365 |
| --- tools/cvs2fossil/lib/c2f_cyclebreaker.tcl | |
| +++ tools/cvs2fossil/lib/c2f_cyclebreaker.tcl | |
| @@ -96,10 +96,11 @@ | |
| 96 | while {1} { |
| 97 | while {[WithoutPredecessor $dg n]} { |
| 98 | ProcessedHook $n $myat |
| 99 | $dg node delete $n |
| 100 | incr myat |
| 101 | ShowPendingNodes |
| 102 | } |
| 103 | |
| 104 | if {![llength [dg nodes]]} break |
| 105 | |
| 106 | BreakCycleHook $dg |
| @@ -127,10 +128,15 @@ | |
| 128 | |
| 129 | typemethod break {graph} { |
| 130 | BreakCycle $graph [FindCycle $graph] |
| 131 | return |
| 132 | } |
| 133 | |
| 134 | typemethod replace {graph n replacements} { |
| 135 | Replace $graph $n $replacements |
| 136 | return |
| 137 | } |
| 138 | |
| 139 | # # ## ### ##### ######## ############# |
| 140 | ## Internal methods |
| 141 | |
| 142 | proc Setup {changesets {log 1}} { |
| @@ -182,10 +188,11 @@ | |
| 188 | foreach n [$dg nodes] { |
| 189 | if {[$dg node degree -in $n]} continue |
| 190 | lappend mybottom [linsert [$dg node get $n timerange] 0 $n] |
| 191 | } |
| 192 | set mybottom [lsort -index 1 -integer [lsort -index 2 -integer $mybottom]] |
| 193 | ShowPendingNodes |
| 194 | return |
| 195 | } |
| 196 | |
| 197 | proc WithoutPredecessor {dg nv} { |
| 198 | ::variable mybottom |
| @@ -216,10 +223,20 @@ | |
| 223 | # procedure to save the dependencies as well (encoded in the |
| 224 | # arcs). |
| 225 | return 1 |
| 226 | } |
| 227 | |
| 228 | proc ShowPendingNodes {} { |
| 229 | if {[log verbosity?] < 10} return |
| 230 | ::variable mybottom |
| 231 | log write 10 cyclebreaker \ |
| 232 | "Pending: [struct::list map $mybottom [myproc FormatPendingItem]]" |
| 233 | return |
| 234 | } |
| 235 | |
| 236 | proc FormatPendingItem {item} { lreplace $item 0 0 <[[lindex $item 0] id]> } |
| 237 | |
| 238 | proc FindCycle {dg} { |
| 239 | # This procedure is run if and only the graph is not empty and |
| 240 | # all nodes have predecessors. This means that each node is |
| 241 | # either part of a cycle or (indirectly) depending on a node |
| 242 | # in a cycle. We can start at an arbitrary node, follow its |
| @@ -298,44 +315,11 @@ | |
| 315 | |
| 316 | # At this point the old changeset (BESTNODE) is gone |
| 317 | # already. We remove it from the graph as well and then enter |
| 318 | # the fragments generated for it. |
| 319 | |
| 320 | Replace $dg $bestnode $newcsets |
| 321 | |
| 322 | Mark $dg -${ID}-after |
| 323 | return |
| 324 | } |
| 325 | |
| @@ -355,10 +339,49 @@ | |
| 339 | file mkdir [file dirname $fname] |
| 340 | dot write $dg $mydotprefix$suffix $fname |
| 341 | incr mydotid |
| 342 | |
| 343 | log write 5 cyclebreaker ".dot export $fname" |
| 344 | return |
| 345 | } |
| 346 | |
| 347 | proc Replace {dg n replacements} { |
| 348 | # NOTE. We have to get the list of incoming neighbours and |
| 349 | # recompute their successors after the new nodes have been |
| 350 | # inserted. Their outgoing arcs will now go to one or both of |
| 351 | # the new nodes, and not redoing them may cause us to forget |
| 352 | # circles, leaving them in, unbroken. |
| 353 | |
| 354 | set pre [$dg nodes -in $n] |
| 355 | |
| 356 | $dg node delete $n |
| 357 | |
| 358 | foreach cset $replacements { |
| 359 | $dg node insert $cset |
| 360 | $dg node set $cset timerange [$cset timerange] |
| 361 | } |
| 362 | |
| 363 | foreach cset $replacements { |
| 364 | foreach succ [$cset successors] { |
| 365 | # The new changesets may have dependencies outside of |
| 366 | # the chosen set. These are ignored |
| 367 | if {![$dg node exists $succ]} continue |
| 368 | $dg arc insert $cset $succ |
| 369 | } |
| 370 | } |
| 371 | foreach cset $pre { |
| 372 | foreach succ [$cset successors] { |
| 373 | # Note that the arc may already exist in the graph. If |
| 374 | # so ignore it. The new changesets may have |
| 375 | # dependencies outside of the chosen set. These are |
| 376 | # ignored |
| 377 | if {![$dg node exists $succ]} continue |
| 378 | if {[HasArc $dg $cset $succ]} continue;# TODO should be graph method. |
| 379 | $dg arc insert $cset $succ |
| 380 | } |
| 381 | } |
| 382 | |
| 383 | return |
| 384 | } |
| 385 | |
| 386 | # # ## ### ##### ######## ############# |
| 387 | ## Callback invokation ... |
| 388 |