Fossil SCM
Modified to break all backward symbols, not only branches, removed the other custom circle breaking code, should not be needed any longer (See comments for proof).
Commit
6b520e7d97c3d610a2282685fa37f83f1c0dd774
Parent
3e18606b5c5bb5a…
1 file changed
+47
-152
+47
-152
| --- tools/cvs2fossil/lib/c2f_pbreakacycle.tcl | ||
| +++ tools/cvs2fossil/lib/c2f_pbreakacycle.tcl | ||
| @@ -66,16 +66,15 @@ | ||
| 66 | 66 | # Pass manager interface. Executed to perform the |
| 67 | 67 | # functionality of the pass. |
| 68 | 68 | |
| 69 | 69 | set len [string length [project::rev num]] |
| 70 | 70 | set myatfmt %${len}s |
| 71 | - incr len 6 | |
| 71 | + incr len 12 | |
| 72 | 72 | set mycsfmt %${len}s |
| 73 | 73 | |
| 74 | - cyclebreaker precmd [myproc BreakBackwardBranches] | |
| 74 | + cyclebreaker precmd [myproc BreakBackward] | |
| 75 | 75 | cyclebreaker savecmd [myproc KeepOrder] |
| 76 | - cyclebreaker breakcmd [myproc BreakCycle] | |
| 77 | 76 | |
| 78 | 77 | state transaction { |
| 79 | 78 | LoadCommitOrder |
| 80 | 79 | cyclebreaker run break-all [myproc Changesets] |
| 81 | 80 | } |
| @@ -106,21 +105,17 @@ | ||
| 106 | 105 | set cset [project::rev of $cid] |
| 107 | 106 | $cset setpos $pos |
| 108 | 107 | set mycset($pos) $cset |
| 109 | 108 | lappend myrevisionchangesets $cset |
| 110 | 109 | } |
| 111 | - # Remove the order information now that we have it in | |
| 112 | - # memory, so that we can save it once more, for all | |
| 113 | - # changesets, while breaking the remaining cycles. | |
| 114 | - state run { DELETE FROM csorder } | |
| 115 | 110 | } |
| 116 | 111 | return |
| 117 | 112 | } |
| 118 | 113 | |
| 119 | 114 | # # ## ### ##### ######## ############# |
| 120 | 115 | |
| 121 | - proc BreakBackwardBranches {graph} { | |
| 116 | + proc BreakBackward {graph} { | |
| 122 | 117 | # We go over all branch changesets, i.e. the changesets |
| 123 | 118 | # created by the symbols which are translated as branches, and |
| 124 | 119 | # break any which are 'backward', which means that they have |
| 125 | 120 | # at least one incoming revision changeset which is committed |
| 126 | 121 | # after at least one of the outgoing revision changesets, per |
| @@ -135,20 +130,18 @@ | ||
| 135 | 130 | # |
| 136 | 131 | # NOTE 2: Might we even be able to select the backward branch |
| 137 | 132 | # changesets too ? |
| 138 | 133 | |
| 139 | 134 | foreach cset [$graph nodes] { |
| 140 | - if {![$cset isbranch]} continue | |
| 141 | - CheckAndBreakBackwardBranch $graph $cset | |
| 135 | + if {![$cset bysymbol]} continue | |
| 136 | + CheckAndBreakBackward $graph $cset | |
| 142 | 137 | } |
| 143 | 138 | return |
| 144 | 139 | } |
| 145 | 140 | |
| 146 | - proc CheckAndBreakBackwardBranch {graph cset} { | |
| 147 | - while {[IsABackwardBranch $graph $cset]} { | |
| 148 | - log write 5 breakacycle "Breaking backward branch changeset [$cset str]" | |
| 149 | - | |
| 141 | + proc CheckAndBreakBackward {graph cset} { | |
| 142 | + while {[IsBackward $graph $cset]} { | |
| 150 | 143 | # Knowing that the branch is backward we now look at the |
| 151 | 144 | # individual revisions in the changeset and determine |
| 152 | 145 | # which of them are responsible for the overlap. This |
| 153 | 146 | # allows us to split them into two sets, one of |
| 154 | 147 | # non-overlapping revisions, and of overlapping ones. Each |
| @@ -165,11 +158,11 @@ | ||
| 165 | 158 | |
| 166 | 159 | # limits : dict (revision -> list (max predecessor commit, min sucessor commit)) |
| 167 | 160 | |
| 168 | 161 | ComputeLimits $cset limits border |
| 169 | 162 | |
| 170 | - log write 6 breakacycle "Using commit position $border as border" | |
| 163 | + log write 5 breakacycle "Breaking backward changeset [$cset str] with commit position $border as border" | |
| 171 | 164 | |
| 172 | 165 | # Then we sort the file level items based on there they |
| 173 | 166 | # sit relative to the border into before and after the |
| 174 | 167 | # border. |
| 175 | 168 | |
| @@ -181,18 +174,20 @@ | ||
| 181 | 174 | # At last check that the normal frament is indeed not |
| 182 | 175 | # backward, and iterate over the possibly still backward |
| 183 | 176 | # second fragment. |
| 184 | 177 | |
| 185 | 178 | struct::list assign $replacements normal backward |
| 186 | - if {[IsABackwardBranch $graph $normal]} { trouble internal "The normal fragment is unexpectedly a backward branch" } | |
| 179 | + if {[IsBackward $graph $normal]} { | |
| 180 | + trouble internal "The normal fragment is unexpectedly backward" | |
| 181 | + } | |
| 187 | 182 | |
| 188 | 183 | set cset $backward |
| 189 | 184 | } |
| 190 | 185 | return |
| 191 | 186 | } |
| 192 | 187 | |
| 193 | - proc IsABackwardBranch {dg cset} { | |
| 188 | + proc IsBackward {dg cset} { | |
| 194 | 189 | # A branch is "backward" if it has at least one incoming |
| 195 | 190 | # revision changeset which is committed after at least one of |
| 196 | 191 | # the outgoing revision changesets, per the order computed in |
| 197 | 192 | # pass 6. |
| 198 | 193 | |
| @@ -313,13 +308,16 @@ | ||
| 313 | 308 | |
| 314 | 309 | |
| 315 | 310 | # # ## ### ##### ######## ############# |
| 316 | 311 | |
| 317 | 312 | proc KeepOrder {graph at cset} { |
| 313 | + ::variable myatfmt | |
| 314 | + ::variable mycsfmt | |
| 315 | + | |
| 318 | 316 | set cid [$cset id] |
| 319 | 317 | |
| 320 | - log write 4 breakacycle "Changeset @ [format $myatfmt $at]: [format $mycsfmt [$cset str]] <<[FormatTR $graph $cset]>>" | |
| 318 | + log write 8 breakacycle "Changeset @ [format $myatfmt $at]: [format $mycsfmt [$cset str]] <<[FormatTR $graph $cset]>>" | |
| 321 | 319 | |
| 322 | 320 | # We see here a mixture of symbol and revision changesets. |
| 323 | 321 | # The symbol changesets are ignored as irrelevant. |
| 324 | 322 | |
| 325 | 323 | if {[$cset pos] eq ""} return |
| @@ -326,23 +324,41 @@ | ||
| 326 | 324 | |
| 327 | 325 | # For the revision changesets we are sure that they are |
| 328 | 326 | # consumed in the same order as generated by pass 7 |
| 329 | 327 | # (RevTopologicalSort). Per the code in cvs2svn. |
| 330 | 328 | |
| 331 | - # NOTE: I cannot see that. Assume cs A and cs B, not dependent | |
| 332 | - # on each other in the set of revisions, now B after A | |
| 333 | - # simply means that B has a later time or depends on | |
| 334 | - # something wit a later time than A. In the full graph A | |
| 335 | - # may now have dependencies which shift it after B, | |
| 336 | - # violating the above assumption. | |
| 337 | - # | |
| 338 | - # Well, it seems to work if I do not make the NTDB root a | |
| 339 | - # successor of the regular root. Doing so seems to tangle the | |
| 340 | - # changesets into a knots regarding time vs dependencies and | |
| 341 | - # trigger such shifts. Keeping these two roots separate OTOH | |
| 342 | - # disappears the tangle. So, for now I accept that, and for | |
| 343 | - # paranoia I add code which checks this assumption. | |
| 329 | + # IMHO this will work if and only if none of the symbol | |
| 330 | + # changesets are "backwards", which explains the breaking of | |
| 331 | + # the backward changesets first, in the pre-hook. A difference | |
| 332 | + # to cvs2svn however is that we are breaking all backward | |
| 333 | + # symbol changesets, both branch and tag. cvs2svn can | |
| 334 | + # apparently assume here that tag symbol changesets are not | |
| 335 | + # backwards, ever. We can't, apparently. It is unclear to me | |
| 336 | + # where the difference is. | |
| 337 | + | |
| 338 | + # An interesting thing IMHO, is that after breaking backward | |
| 339 | + # symbol changesets we should not have any circles any | |
| 340 | + # longer. Each circle which was still present had to involve a | |
| 341 | + # backward symbol, and that we split. | |
| 342 | + | |
| 343 | + # Proof: Let us assume we that have a circle | |
| 344 | + # C: R1 -> ... -> Rx -> S -> Ry -> ... -> Rn -> R1 | |
| 345 | + # Let us further assume that S is not backward. That means | |
| 346 | + # ORD(Rx) < ORD(Ry). The earlier topological sorting without | |
| 347 | + # symbols now forces this relationship through to be | |
| 348 | + # ORD(Rx) < ORD(R1) < ORD(Rx). | |
| 349 | + # We have reached an impossibility, a paradox. Our initial | |
| 350 | + # assumption of S not being backward cannot hold. | |
| 351 | + # | |
| 352 | + # Alternate, direct, reasoning: Without S the chain of | |
| 353 | + # dependencies is Ry -> .. -> R1 -> .. -> Rx, therefore | |
| 354 | + # ORD(Ry) < ORD(Rx) holds, and this means S is backward. | |
| 355 | + | |
| 356 | + # NOTE. Even with the backward symbols broken, it is not clear | |
| 357 | + # to me yet what this means in terms of tagging revisions | |
| 358 | + # later, as we now have more than one place where the symbol | |
| 359 | + # occurs on the relevant LOD. | |
| 344 | 360 | |
| 345 | 361 | struct::set exclude myrevisionchangesets $cset |
| 346 | 362 | |
| 347 | 363 | ::variable mylastpos |
| 348 | 364 | set new [$cset pos] |
| @@ -370,131 +386,10 @@ | ||
| 370 | 386 | typevariable myrevisionchangesets {} ; # Set of revision changesets |
| 371 | 387 | |
| 372 | 388 | typevariable myatfmt ; # Format for log output to gain better alignment of the various columns. |
| 373 | 389 | typevariable mycsfmt ; # Ditto for the changesets. |
| 374 | 390 | |
| 375 | - # # ## ### ##### ######## ############# | |
| 376 | - | |
| 377 | - proc BreakCycle {graph} { | |
| 378 | - # In this pass the cycle breaking can be made a bit more | |
| 379 | - # targeted, hence this custom callback. | |
| 380 | - # | |
| 381 | - # First we use the data remembered by 'SaveOrder', about the | |
| 382 | - # last commit position it handled, to deduce the next revision | |
| 383 | - # changeset it would encounter. Then we look for the shortest | |
| 384 | - # predecessor path from it to all other revision changesets | |
| 385 | - # and break this path. Without such a path we fall back to the | |
| 386 | - # generic cycle breaker. | |
| 387 | - | |
| 388 | - ::variable mylastpos | |
| 389 | - ::variable mycset | |
| 390 | - ::variable myrevisionchangesets | |
| 391 | - | |
| 392 | - set nextpos [expr {$mylastpos + 1}] | |
| 393 | - set next $mycset($nextpos) | |
| 394 | - | |
| 395 | - puts "** Last: $mylastpos = [$mycset($mylastpos) str] @ [$mycset($mylastpos) pos]" | |
| 396 | - puts "** Next: $nextpos = [$next str] @ [$next pos]" | |
| 397 | - | |
| 398 | - set path [SearchForPath $graph $next $myrevisionchangesets] | |
| 399 | - if {[llength $path]} { | |
| 400 | - cyclebreaker break-segment $graph $path | |
| 401 | - return | |
| 402 | - } | |
| 403 | - | |
| 404 | - # We were unable to find an ordered changeset in the reachable | |
| 405 | - # predecessors, fall back to the generic code for breaking the | |
| 406 | - # found cycle. | |
| 407 | - | |
| 408 | - cyclebreaker break $graph | |
| 409 | - } | |
| 410 | - | |
| 411 | - proc SearchForPath {graph n stopnodes} { | |
| 412 | - # Search for paths to prerequisites of N. | |
| 413 | - # | |
| 414 | - # Try to find the shortest dependency path that causes the | |
| 415 | - # changeset N to depend (directly or indirectly) on one of the | |
| 416 | - # changesets contained in STOPNODES. | |
| 417 | - # | |
| 418 | - # We consider direct and indirect dependencies in the sense | |
| 419 | - # that the changeset can be reached by following a chain of | |
| 420 | - # predecessor nodes. | |
| 421 | - # | |
| 422 | - # When one of the csets in STOPNODES is found, we terminate | |
| 423 | - # the search and return the path from that cset to N. If no | |
| 424 | - # path is found to a node in STOP_SET, we return the empty | |
| 425 | - # list/path. | |
| 426 | - | |
| 427 | - # This is in essence a multi-destination Dijkstra starting at | |
| 428 | - # N which stops when one of the destinations in STOPNODES has | |
| 429 | - # been reached, traversing the predecessor arcs. | |
| 430 | - | |
| 431 | - # REACHABLE :: array (NODE -> list (STEPS, PREVIOUS)) | |
| 432 | - # | |
| 433 | - # Semantics: NODE can be reached from N in STEPS steps, and | |
| 434 | - # PREVIOUS is the previous node in the path which reached it, | |
| 435 | - # allowing us at the end to construct the full path by | |
| 436 | - # following these backlinks from the found destination. N is | |
| 437 | - # only included as a key if there is a loop leading back to | |
| 438 | - # it. | |
| 439 | - | |
| 440 | - # PENDING :: list (list (NODE, STEPS)) | |
| 441 | - # | |
| 442 | - # Semantics: A list of possibilities that still have to be | |
| 443 | - # investigated, where STEPS is the number of steps to get to | |
| 444 | - # NODE. | |
| 445 | - | |
| 446 | - array set reachable {} | |
| 447 | - set pending [list [list $n 0]] | |
| 448 | - set at 0 | |
| 449 | - | |
| 450 | - puts "** Searching shortest path ..." | |
| 451 | - | |
| 452 | - while {$at < [llength $pending]} { | |
| 453 | - struct::list assign [lindex $pending $at] current steps | |
| 454 | - | |
| 455 | - #puts "** [lindex $pending $at] ** [$current str] **" | |
| 456 | - incr at | |
| 457 | - | |
| 458 | - # Process the possibility. This is a breadth-first traversal. | |
| 459 | - incr steps | |
| 460 | - foreach pre [$graph nodes -in $current] { | |
| 461 | - # Since the search is breadth-first, we only have to # | |
| 462 | - # set nodes that don't already exist. If they do they | |
| 463 | - # have been reached already on a shorter path. | |
| 464 | - | |
| 465 | - if {[info exists reachable($pre)]} continue | |
| 466 | - | |
| 467 | - set reachable($pre) [list $steps $current] | |
| 468 | - lappend pending [list $pre $steps] | |
| 469 | - | |
| 470 | - # Continue the search while have not reached any of | |
| 471 | - # our destinations? | |
| 472 | - if {![struct::set contain $pre $stopnodes]} continue | |
| 473 | - | |
| 474 | - # We have arrived, PRE is one of the destination; now | |
| 475 | - # construct and return the path to it from N by | |
| 476 | - # following the backlinks in the search state. | |
| 477 | - set path [list $pre] | |
| 478 | - while {1} { | |
| 479 | - set pre [lindex $reachable($pre) 1] | |
| 480 | - if {$pre eq $n} break | |
| 481 | - lappend path $pre | |
| 482 | - } | |
| 483 | - lappend path $n | |
| 484 | - | |
| 485 | - puts "** Searching shortest path ... Found ([project rev strlist $path])" | |
| 486 | - return $path | |
| 487 | - } | |
| 488 | - } | |
| 489 | - | |
| 490 | - puts "** Searching shortest path ... Not found" | |
| 491 | - | |
| 492 | - # No path found. | |
| 493 | - return {} | |
| 494 | - } | |
| 495 | - | |
| 496 | 391 | # # ## ### ##### ######## ############# |
| 497 | 392 | |
| 498 | 393 | typevariable mycset -array {} ; # Map from commit positions to the |
| 499 | 394 | # changeset (object ref) at that |
| 500 | 395 | # position. |
| 501 | 396 |
| --- tools/cvs2fossil/lib/c2f_pbreakacycle.tcl | |
| +++ tools/cvs2fossil/lib/c2f_pbreakacycle.tcl | |
| @@ -66,16 +66,15 @@ | |
| 66 | # Pass manager interface. Executed to perform the |
| 67 | # functionality of the pass. |
| 68 | |
| 69 | set len [string length [project::rev num]] |
| 70 | set myatfmt %${len}s |
| 71 | incr len 6 |
| 72 | set mycsfmt %${len}s |
| 73 | |
| 74 | cyclebreaker precmd [myproc BreakBackwardBranches] |
| 75 | cyclebreaker savecmd [myproc KeepOrder] |
| 76 | cyclebreaker breakcmd [myproc BreakCycle] |
| 77 | |
| 78 | state transaction { |
| 79 | LoadCommitOrder |
| 80 | cyclebreaker run break-all [myproc Changesets] |
| 81 | } |
| @@ -106,21 +105,17 @@ | |
| 106 | set cset [project::rev of $cid] |
| 107 | $cset setpos $pos |
| 108 | set mycset($pos) $cset |
| 109 | lappend myrevisionchangesets $cset |
| 110 | } |
| 111 | # Remove the order information now that we have it in |
| 112 | # memory, so that we can save it once more, for all |
| 113 | # changesets, while breaking the remaining cycles. |
| 114 | state run { DELETE FROM csorder } |
| 115 | } |
| 116 | return |
| 117 | } |
| 118 | |
| 119 | # # ## ### ##### ######## ############# |
| 120 | |
| 121 | proc BreakBackwardBranches {graph} { |
| 122 | # We go over all branch changesets, i.e. the changesets |
| 123 | # created by the symbols which are translated as branches, and |
| 124 | # break any which are 'backward', which means that they have |
| 125 | # at least one incoming revision changeset which is committed |
| 126 | # after at least one of the outgoing revision changesets, per |
| @@ -135,20 +130,18 @@ | |
| 135 | # |
| 136 | # NOTE 2: Might we even be able to select the backward branch |
| 137 | # changesets too ? |
| 138 | |
| 139 | foreach cset [$graph nodes] { |
| 140 | if {![$cset isbranch]} continue |
| 141 | CheckAndBreakBackwardBranch $graph $cset |
| 142 | } |
| 143 | return |
| 144 | } |
| 145 | |
| 146 | proc CheckAndBreakBackwardBranch {graph cset} { |
| 147 | while {[IsABackwardBranch $graph $cset]} { |
| 148 | log write 5 breakacycle "Breaking backward branch changeset [$cset str]" |
| 149 | |
| 150 | # Knowing that the branch is backward we now look at the |
| 151 | # individual revisions in the changeset and determine |
| 152 | # which of them are responsible for the overlap. This |
| 153 | # allows us to split them into two sets, one of |
| 154 | # non-overlapping revisions, and of overlapping ones. Each |
| @@ -165,11 +158,11 @@ | |
| 165 | |
| 166 | # limits : dict (revision -> list (max predecessor commit, min sucessor commit)) |
| 167 | |
| 168 | ComputeLimits $cset limits border |
| 169 | |
| 170 | log write 6 breakacycle "Using commit position $border as border" |
| 171 | |
| 172 | # Then we sort the file level items based on there they |
| 173 | # sit relative to the border into before and after the |
| 174 | # border. |
| 175 | |
| @@ -181,18 +174,20 @@ | |
| 181 | # At last check that the normal frament is indeed not |
| 182 | # backward, and iterate over the possibly still backward |
| 183 | # second fragment. |
| 184 | |
| 185 | struct::list assign $replacements normal backward |
| 186 | if {[IsABackwardBranch $graph $normal]} { trouble internal "The normal fragment is unexpectedly a backward branch" } |
| 187 | |
| 188 | set cset $backward |
| 189 | } |
| 190 | return |
| 191 | } |
| 192 | |
| 193 | proc IsABackwardBranch {dg cset} { |
| 194 | # A branch is "backward" if it has at least one incoming |
| 195 | # revision changeset which is committed after at least one of |
| 196 | # the outgoing revision changesets, per the order computed in |
| 197 | # pass 6. |
| 198 | |
| @@ -313,13 +308,16 @@ | |
| 313 | |
| 314 | |
| 315 | # # ## ### ##### ######## ############# |
| 316 | |
| 317 | proc KeepOrder {graph at cset} { |
| 318 | set cid [$cset id] |
| 319 | |
| 320 | log write 4 breakacycle "Changeset @ [format $myatfmt $at]: [format $mycsfmt [$cset str]] <<[FormatTR $graph $cset]>>" |
| 321 | |
| 322 | # We see here a mixture of symbol and revision changesets. |
| 323 | # The symbol changesets are ignored as irrelevant. |
| 324 | |
| 325 | if {[$cset pos] eq ""} return |
| @@ -326,23 +324,41 @@ | |
| 326 | |
| 327 | # For the revision changesets we are sure that they are |
| 328 | # consumed in the same order as generated by pass 7 |
| 329 | # (RevTopologicalSort). Per the code in cvs2svn. |
| 330 | |
| 331 | # NOTE: I cannot see that. Assume cs A and cs B, not dependent |
| 332 | # on each other in the set of revisions, now B after A |
| 333 | # simply means that B has a later time or depends on |
| 334 | # something wit a later time than A. In the full graph A |
| 335 | # may now have dependencies which shift it after B, |
| 336 | # violating the above assumption. |
| 337 | # |
| 338 | # Well, it seems to work if I do not make the NTDB root a |
| 339 | # successor of the regular root. Doing so seems to tangle the |
| 340 | # changesets into a knots regarding time vs dependencies and |
| 341 | # trigger such shifts. Keeping these two roots separate OTOH |
| 342 | # disappears the tangle. So, for now I accept that, and for |
| 343 | # paranoia I add code which checks this assumption. |
| 344 | |
| 345 | struct::set exclude myrevisionchangesets $cset |
| 346 | |
| 347 | ::variable mylastpos |
| 348 | set new [$cset pos] |
| @@ -370,131 +386,10 @@ | |
| 370 | typevariable myrevisionchangesets {} ; # Set of revision changesets |
| 371 | |
| 372 | typevariable myatfmt ; # Format for log output to gain better alignment of the various columns. |
| 373 | typevariable mycsfmt ; # Ditto for the changesets. |
| 374 | |
| 375 | # # ## ### ##### ######## ############# |
| 376 | |
| 377 | proc BreakCycle {graph} { |
| 378 | # In this pass the cycle breaking can be made a bit more |
| 379 | # targeted, hence this custom callback. |
| 380 | # |
| 381 | # First we use the data remembered by 'SaveOrder', about the |
| 382 | # last commit position it handled, to deduce the next revision |
| 383 | # changeset it would encounter. Then we look for the shortest |
| 384 | # predecessor path from it to all other revision changesets |
| 385 | # and break this path. Without such a path we fall back to the |
| 386 | # generic cycle breaker. |
| 387 | |
| 388 | ::variable mylastpos |
| 389 | ::variable mycset |
| 390 | ::variable myrevisionchangesets |
| 391 | |
| 392 | set nextpos [expr {$mylastpos + 1}] |
| 393 | set next $mycset($nextpos) |
| 394 | |
| 395 | puts "** Last: $mylastpos = [$mycset($mylastpos) str] @ [$mycset($mylastpos) pos]" |
| 396 | puts "** Next: $nextpos = [$next str] @ [$next pos]" |
| 397 | |
| 398 | set path [SearchForPath $graph $next $myrevisionchangesets] |
| 399 | if {[llength $path]} { |
| 400 | cyclebreaker break-segment $graph $path |
| 401 | return |
| 402 | } |
| 403 | |
| 404 | # We were unable to find an ordered changeset in the reachable |
| 405 | # predecessors, fall back to the generic code for breaking the |
| 406 | # found cycle. |
| 407 | |
| 408 | cyclebreaker break $graph |
| 409 | } |
| 410 | |
| 411 | proc SearchForPath {graph n stopnodes} { |
| 412 | # Search for paths to prerequisites of N. |
| 413 | # |
| 414 | # Try to find the shortest dependency path that causes the |
| 415 | # changeset N to depend (directly or indirectly) on one of the |
| 416 | # changesets contained in STOPNODES. |
| 417 | # |
| 418 | # We consider direct and indirect dependencies in the sense |
| 419 | # that the changeset can be reached by following a chain of |
| 420 | # predecessor nodes. |
| 421 | # |
| 422 | # When one of the csets in STOPNODES is found, we terminate |
| 423 | # the search and return the path from that cset to N. If no |
| 424 | # path is found to a node in STOP_SET, we return the empty |
| 425 | # list/path. |
| 426 | |
| 427 | # This is in essence a multi-destination Dijkstra starting at |
| 428 | # N which stops when one of the destinations in STOPNODES has |
| 429 | # been reached, traversing the predecessor arcs. |
| 430 | |
| 431 | # REACHABLE :: array (NODE -> list (STEPS, PREVIOUS)) |
| 432 | # |
| 433 | # Semantics: NODE can be reached from N in STEPS steps, and |
| 434 | # PREVIOUS is the previous node in the path which reached it, |
| 435 | # allowing us at the end to construct the full path by |
| 436 | # following these backlinks from the found destination. N is |
| 437 | # only included as a key if there is a loop leading back to |
| 438 | # it. |
| 439 | |
| 440 | # PENDING :: list (list (NODE, STEPS)) |
| 441 | # |
| 442 | # Semantics: A list of possibilities that still have to be |
| 443 | # investigated, where STEPS is the number of steps to get to |
| 444 | # NODE. |
| 445 | |
| 446 | array set reachable {} |
| 447 | set pending [list [list $n 0]] |
| 448 | set at 0 |
| 449 | |
| 450 | puts "** Searching shortest path ..." |
| 451 | |
| 452 | while {$at < [llength $pending]} { |
| 453 | struct::list assign [lindex $pending $at] current steps |
| 454 | |
| 455 | #puts "** [lindex $pending $at] ** [$current str] **" |
| 456 | incr at |
| 457 | |
| 458 | # Process the possibility. This is a breadth-first traversal. |
| 459 | incr steps |
| 460 | foreach pre [$graph nodes -in $current] { |
| 461 | # Since the search is breadth-first, we only have to # |
| 462 | # set nodes that don't already exist. If they do they |
| 463 | # have been reached already on a shorter path. |
| 464 | |
| 465 | if {[info exists reachable($pre)]} continue |
| 466 | |
| 467 | set reachable($pre) [list $steps $current] |
| 468 | lappend pending [list $pre $steps] |
| 469 | |
| 470 | # Continue the search while have not reached any of |
| 471 | # our destinations? |
| 472 | if {![struct::set contain $pre $stopnodes]} continue |
| 473 | |
| 474 | # We have arrived, PRE is one of the destination; now |
| 475 | # construct and return the path to it from N by |
| 476 | # following the backlinks in the search state. |
| 477 | set path [list $pre] |
| 478 | while {1} { |
| 479 | set pre [lindex $reachable($pre) 1] |
| 480 | if {$pre eq $n} break |
| 481 | lappend path $pre |
| 482 | } |
| 483 | lappend path $n |
| 484 | |
| 485 | puts "** Searching shortest path ... Found ([project rev strlist $path])" |
| 486 | return $path |
| 487 | } |
| 488 | } |
| 489 | |
| 490 | puts "** Searching shortest path ... Not found" |
| 491 | |
| 492 | # No path found. |
| 493 | return {} |
| 494 | } |
| 495 | |
| 496 | # # ## ### ##### ######## ############# |
| 497 | |
| 498 | typevariable mycset -array {} ; # Map from commit positions to the |
| 499 | # changeset (object ref) at that |
| 500 | # position. |
| 501 |
| --- tools/cvs2fossil/lib/c2f_pbreakacycle.tcl | |
| +++ tools/cvs2fossil/lib/c2f_pbreakacycle.tcl | |
| @@ -66,16 +66,15 @@ | |
| 66 | # Pass manager interface. Executed to perform the |
| 67 | # functionality of the pass. |
| 68 | |
| 69 | set len [string length [project::rev num]] |
| 70 | set myatfmt %${len}s |
| 71 | incr len 12 |
| 72 | set mycsfmt %${len}s |
| 73 | |
| 74 | cyclebreaker precmd [myproc BreakBackward] |
| 75 | cyclebreaker savecmd [myproc KeepOrder] |
| 76 | |
| 77 | state transaction { |
| 78 | LoadCommitOrder |
| 79 | cyclebreaker run break-all [myproc Changesets] |
| 80 | } |
| @@ -106,21 +105,17 @@ | |
| 105 | set cset [project::rev of $cid] |
| 106 | $cset setpos $pos |
| 107 | set mycset($pos) $cset |
| 108 | lappend myrevisionchangesets $cset |
| 109 | } |
| 110 | } |
| 111 | return |
| 112 | } |
| 113 | |
| 114 | # # ## ### ##### ######## ############# |
| 115 | |
| 116 | proc BreakBackward {graph} { |
| 117 | # We go over all branch changesets, i.e. the changesets |
| 118 | # created by the symbols which are translated as branches, and |
| 119 | # break any which are 'backward', which means that they have |
| 120 | # at least one incoming revision changeset which is committed |
| 121 | # after at least one of the outgoing revision changesets, per |
| @@ -135,20 +130,18 @@ | |
| 130 | # |
| 131 | # NOTE 2: Might we even be able to select the backward branch |
| 132 | # changesets too ? |
| 133 | |
| 134 | foreach cset [$graph nodes] { |
| 135 | if {![$cset bysymbol]} continue |
| 136 | CheckAndBreakBackward $graph $cset |
| 137 | } |
| 138 | return |
| 139 | } |
| 140 | |
| 141 | proc CheckAndBreakBackward {graph cset} { |
| 142 | while {[IsBackward $graph $cset]} { |
| 143 | # Knowing that the branch is backward we now look at the |
| 144 | # individual revisions in the changeset and determine |
| 145 | # which of them are responsible for the overlap. This |
| 146 | # allows us to split them into two sets, one of |
| 147 | # non-overlapping revisions, and of overlapping ones. Each |
| @@ -165,11 +158,11 @@ | |
| 158 | |
| 159 | # limits : dict (revision -> list (max predecessor commit, min sucessor commit)) |
| 160 | |
| 161 | ComputeLimits $cset limits border |
| 162 | |
| 163 | log write 5 breakacycle "Breaking backward changeset [$cset str] with commit position $border as border" |
| 164 | |
| 165 | # Then we sort the file level items based on there they |
| 166 | # sit relative to the border into before and after the |
| 167 | # border. |
| 168 | |
| @@ -181,18 +174,20 @@ | |
| 174 | # At last check that the normal frament is indeed not |
| 175 | # backward, and iterate over the possibly still backward |
| 176 | # second fragment. |
| 177 | |
| 178 | struct::list assign $replacements normal backward |
| 179 | if {[IsBackward $graph $normal]} { |
| 180 | trouble internal "The normal fragment is unexpectedly backward" |
| 181 | } |
| 182 | |
| 183 | set cset $backward |
| 184 | } |
| 185 | return |
| 186 | } |
| 187 | |
| 188 | proc IsBackward {dg cset} { |
| 189 | # A branch is "backward" if it has at least one incoming |
| 190 | # revision changeset which is committed after at least one of |
| 191 | # the outgoing revision changesets, per the order computed in |
| 192 | # pass 6. |
| 193 | |
| @@ -313,13 +308,16 @@ | |
| 308 | |
| 309 | |
| 310 | # # ## ### ##### ######## ############# |
| 311 | |
| 312 | proc KeepOrder {graph at cset} { |
| 313 | ::variable myatfmt |
| 314 | ::variable mycsfmt |
| 315 | |
| 316 | set cid [$cset id] |
| 317 | |
| 318 | log write 8 breakacycle "Changeset @ [format $myatfmt $at]: [format $mycsfmt [$cset str]] <<[FormatTR $graph $cset]>>" |
| 319 | |
| 320 | # We see here a mixture of symbol and revision changesets. |
| 321 | # The symbol changesets are ignored as irrelevant. |
| 322 | |
| 323 | if {[$cset pos] eq ""} return |
| @@ -326,23 +324,41 @@ | |
| 324 | |
| 325 | # For the revision changesets we are sure that they are |
| 326 | # consumed in the same order as generated by pass 7 |
| 327 | # (RevTopologicalSort). Per the code in cvs2svn. |
| 328 | |
| 329 | # IMHO this will work if and only if none of the symbol |
| 330 | # changesets are "backwards", which explains the breaking of |
| 331 | # the backward changesets first, in the pre-hook. A difference |
| 332 | # to cvs2svn however is that we are breaking all backward |
| 333 | # symbol changesets, both branch and tag. cvs2svn can |
| 334 | # apparently assume here that tag symbol changesets are not |
| 335 | # backwards, ever. We can't, apparently. It is unclear to me |
| 336 | # where the difference is. |
| 337 | |
| 338 | # An interesting thing IMHO, is that after breaking backward |
| 339 | # symbol changesets we should not have any circles any |
| 340 | # longer. Each circle which was still present had to involve a |
| 341 | # backward symbol, and that we split. |
| 342 | |
| 343 | # Proof: Let us assume we that have a circle |
| 344 | # C: R1 -> ... -> Rx -> S -> Ry -> ... -> Rn -> R1 |
| 345 | # Let us further assume that S is not backward. That means |
| 346 | # ORD(Rx) < ORD(Ry). The earlier topological sorting without |
| 347 | # symbols now forces this relationship through to be |
| 348 | # ORD(Rx) < ORD(R1) < ORD(Rx). |
| 349 | # We have reached an impossibility, a paradox. Our initial |
| 350 | # assumption of S not being backward cannot hold. |
| 351 | # |
| 352 | # Alternate, direct, reasoning: Without S the chain of |
| 353 | # dependencies is Ry -> .. -> R1 -> .. -> Rx, therefore |
| 354 | # ORD(Ry) < ORD(Rx) holds, and this means S is backward. |
| 355 | |
| 356 | # NOTE. Even with the backward symbols broken, it is not clear |
| 357 | # to me yet what this means in terms of tagging revisions |
| 358 | # later, as we now have more than one place where the symbol |
| 359 | # occurs on the relevant LOD. |
| 360 | |
| 361 | struct::set exclude myrevisionchangesets $cset |
| 362 | |
| 363 | ::variable mylastpos |
| 364 | set new [$cset pos] |
| @@ -370,131 +386,10 @@ | |
| 386 | typevariable myrevisionchangesets {} ; # Set of revision changesets |
| 387 | |
| 388 | typevariable myatfmt ; # Format for log output to gain better alignment of the various columns. |
| 389 | typevariable mycsfmt ; # Ditto for the changesets. |
| 390 | |
| 391 | # # ## ### ##### ######## ############# |
| 392 | |
| 393 | typevariable mycset -array {} ; # Map from commit positions to the |
| 394 | # changeset (object ref) at that |
| 395 | # position. |
| 396 |