Fossil SCM
Updated commentary regarding cycles at this point, items instead of comments, etc.
Commit
af5904e6b7fade5c921695af0088a8c11262e504
Parent
960645443b74f56…
1 file changed
+60
-73
| --- tools/cvs2fossil/lib/c2f_pbreakacycle.tcl | ||
| +++ tools/cvs2fossil/lib/c2f_pbreakacycle.tcl | ||
| @@ -122,57 +122,49 @@ | ||
| 122 | 122 | # at least one incoming revision changeset which is committed |
| 123 | 123 | # after at least one of the outgoing revision changesets, per |
| 124 | 124 | # the order computed in pass 6. In "cvs2svn" this is called |
| 125 | 125 | # "retrograde". |
| 126 | 126 | |
| 127 | - # NOTE: We might be able to use our knowledge that we are | |
| 128 | - # looking at all changesets to create a sql which selects all | |
| 129 | - # the branch changesets from the state in one go instead of | |
| 130 | - # having to check each changeset separately. Consider this | |
| 131 | - # later, get the pass working first. | |
| 132 | - # | |
| 133 | - # NOTE 2: Might we even be able to select the backward branch | |
| 134 | - # changesets too ? | |
| 135 | - | |
| 136 | 127 | foreach cset [$graph nodes] { |
| 137 | - if {![$cset bysymbol]} continue | |
| 128 | + if {![$cset isbranch]} continue | |
| 138 | 129 | CheckAndBreakBackward $graph $cset |
| 139 | 130 | } |
| 140 | 131 | return |
| 141 | 132 | } |
| 142 | 133 | |
| 143 | 134 | proc CheckAndBreakBackward {graph cset} { |
| 144 | 135 | while {[IsBackward $graph $cset]} { |
| 145 | - # Knowing that the branch is backward we now look at the | |
| 146 | - # individual revisions in the changeset and determine | |
| 147 | - # which of them are responsible for the overlap. This | |
| 148 | - # allows us to split them into two sets, one of | |
| 149 | - # non-overlapping revisions, and of overlapping ones. Each | |
| 150 | - # induces a new changeset, and the second may still be | |
| 151 | - # backward and need further splitting. Hence the looping. | |
| 136 | + # Knowing that the branch changeset is backward we now | |
| 137 | + # look at the individual branches in the changeset and | |
| 138 | + # determine which of them are responsible for the | |
| 139 | + # overlap. This allows us to split them into two sets, one | |
| 140 | + # of non-overlapping branches, and of overlapping | |
| 141 | + # ones. Each set induces a new changeset, and the second | |
| 142 | + # one may still be backward and in need of further | |
| 143 | + # splitting. Hence the looping. | |
| 152 | 144 | # |
| 153 | 145 | # The border used for the split is the minimal commit |
| 154 | 146 | # position among the minimal sucessor commit positions for |
| 155 | - # the revisions in the changeset. | |
| 147 | + # the branches in the changeset. | |
| 156 | 148 | |
| 157 | - # Note that individual revisions may not have revision | |
| 158 | - # changesets are predecessors and/or successors, leaving | |
| 149 | + # Note that individual branches may not have changesets | |
| 150 | + # which are their predecessors and/or successors, leaving | |
| 159 | 151 | # the limits partially or completely undefined. |
| 160 | 152 | |
| 161 | 153 | # limits : dict (revision -> list (max predecessor commit, min sucessor commit)) |
| 162 | 154 | |
| 163 | 155 | ComputeLimits $cset limits border |
| 164 | 156 | |
| 165 | 157 | log write 5 breakacycle "Breaking backward changeset [$cset str] with commit position $border as border" |
| 166 | 158 | |
| 167 | - # Then we sort the file level items based on there they | |
| 168 | - # sit relative to the border into before and after the | |
| 169 | - # border. | |
| 159 | + # Secondly we sort the file level items based on there | |
| 160 | + # they sit relative to the border into before and after | |
| 161 | + # the border. | |
| 162 | + | |
| 163 | + SplitItems $limits $border normalitems backwarditems | |
| 170 | 164 | |
| 171 | - SplitRevisions $limits $border normalrevisions backwardrevisions | |
| 172 | - | |
| 173 | - set replacements [project::rev split $cset $normalrevisions $backwardrevisions] | |
| 165 | + set replacements [project::rev split $cset $normalitems $backwarditems] | |
| 174 | 166 | cyclebreaker replace $graph $cset $replacements |
| 175 | 167 | |
| 176 | 168 | # At last check that the normal frament is indeed not |
| 177 | 169 | # backward, and iterate over the possibly still backward |
| 178 | 170 | # second fragment. |
| @@ -188,18 +180,18 @@ | ||
| 188 | 180 | } |
| 189 | 181 | |
| 190 | 182 | proc IsBackward {dg cset} { |
| 191 | 183 | # A branch is "backward" if it has at least one incoming |
| 192 | 184 | # revision changeset which is committed after at least one of |
| 193 | - # the outgoing revision changesets, per the order computed in | |
| 185 | + # the outgoing revision changesets, per the order computed by | |
| 194 | 186 | # pass 6. |
| 195 | 187 | |
| 196 | 188 | # Rephrased, the maximal commit position found among the |
| 197 | 189 | # incoming revision changesets is larger than the minimal |
| 198 | 190 | # commit position found among the outgoing revision |
| 199 | 191 | # changesets. Assuming that we have both incoming and outgoing |
| 200 | - # revision changesets. | |
| 192 | + # revision changesets for the branch. | |
| 201 | 193 | |
| 202 | 194 | # The helper "Positions" computes the set of commit positions |
| 203 | 195 | # for a set of changesets, which can be a mix of revision and |
| 204 | 196 | # symbol changesets. |
| 205 | 197 | |
| @@ -231,43 +223,43 @@ | ||
| 231 | 223 | proc ValidPosition {pos} { expr {$pos ne ""} } |
| 232 | 224 | |
| 233 | 225 | proc ComputeLimits {cset lv bv} { |
| 234 | 226 | upvar 1 $lv thelimits $bv border |
| 235 | 227 | |
| 236 | - # Initialize the boundaries for all revisions. | |
| 228 | + # Initialize the boundaries for all items. | |
| 237 | 229 | |
| 238 | 230 | array set limits {} |
| 239 | - foreach revision [$cset revisions] { | |
| 231 | + foreach revision [$cset items] { | |
| 240 | 232 | set limits($revision) {0 {}} |
| 241 | 233 | } |
| 242 | 234 | |
| 243 | - # Compute and store the maximal predecessors per revision | |
| 235 | + # Compute and store the maximal predecessors per item (branch) | |
| 244 | 236 | |
| 245 | - foreach {revision csets} [$cset predecessormap] { | |
| 237 | + foreach {item csets} [$cset predecessormap] { | |
| 246 | 238 | set s [Positions $csets] |
| 247 | 239 | if {![llength $s]} continue |
| 248 | - set limits($revision) [lreplace $limits($revision) 0 0 [max $s]] | |
| 240 | + set limits($item) [lreplace $limits($item) 0 0 [max $s]] | |
| 249 | 241 | } |
| 250 | 242 | |
| 251 | - # Compute and store the minimal successors per revision | |
| 243 | + # Compute and store the minimal successors per item (branch) | |
| 252 | 244 | |
| 253 | - foreach {revision csets} [$cset successormap] { | |
| 245 | + foreach {item csets} [$cset successormap] { | |
| 254 | 246 | set s [Positions $csets] |
| 255 | 247 | if {![llength $s]} continue |
| 256 | - set limits($revision) [lreplace $limits($revision) 1 1 [min $s]] | |
| 248 | + set limits($item) [lreplace $limits($item) 1 1 [min $s]] | |
| 257 | 249 | } |
| 258 | 250 | |
| 259 | 251 | # Check that the ordering at the file level is correct. We |
| 260 | - # cannot have backward ordering per revision, or something is | |
| 252 | + # cannot have backward ordering per branch, or something is | |
| 261 | 253 | # wrong. |
| 262 | 254 | |
| 263 | - foreach revision [array names limits] { | |
| 264 | - struct::list assign $limits($revision) maxp mins | |
| 255 | + foreach item [array names limits] { | |
| 256 | + struct::list assign $limits($item) maxp mins | |
| 265 | 257 | # Handle min successor position "" as representing infinity |
| 266 | 258 | integrity assert { |
| 267 | 259 | ($mins eq "") || ($maxp < $mins) |
| 268 | - } {Branch revision $revision is backward at file level ($maxp >= $mins)} | |
| 260 | + } {Item <$item> is backward at file level ($maxp >= $mins)} | |
| 269 | 261 | } |
| 270 | 262 | |
| 271 | 263 | # Save the limits for the splitter, and compute the border at |
| 272 | 264 | # which to split as the minimum of all minimal successor |
| 273 | 265 | # positions. |
| @@ -285,27 +277,27 @@ | ||
| 285 | 277 | return $res |
| 286 | 278 | } |
| 287 | 279 | |
| 288 | 280 | proc MinSuccessorPosition {item} { lindex $item 1 } |
| 289 | 281 | |
| 290 | - proc SplitRevisions {limits border nv bv} { | |
| 291 | - upvar 1 $nv normalrevisions $bv backwardrevisions | |
| 282 | + proc SplitItems {limits border nv bv} { | |
| 283 | + upvar 1 $nv normalitems $bv backwarditems | |
| 292 | 284 | |
| 293 | - set normalrevisions {} | |
| 294 | - set backwardrevisions {} | |
| 285 | + set normalitems {} | |
| 286 | + set backwarditems {} | |
| 295 | 287 | |
| 296 | 288 | foreach {rev v} $limits { |
| 297 | 289 | struct::list assign $v maxp mins |
| 298 | 290 | if {$maxp >= $border} { |
| 299 | - lappend backwardrevisions $rev | |
| 291 | + lappend backwarditems $rev | |
| 300 | 292 | } else { |
| 301 | - lappend normalrevisions $rev | |
| 293 | + lappend normalitems $rev | |
| 302 | 294 | } |
| 303 | 295 | } |
| 304 | 296 | |
| 305 | - integrity assert {[llength $normalrevisions]} {Set of normal revisions is empty} | |
| 306 | - integrity assert {[llength $backwardrevisions]} {Set of backward revisions is empty} | |
| 297 | + integrity assert {[llength $normalitems]} {Set of normal items is empty} | |
| 298 | + integrity assert {[llength $backwarditems]} {Set of backward items is empty} | |
| 307 | 299 | return |
| 308 | 300 | } |
| 309 | 301 | |
| 310 | 302 | |
| 311 | 303 | # # ## ### ##### ######## ############# |
| @@ -325,42 +317,37 @@ | ||
| 325 | 317 | |
| 326 | 318 | # For the revision changesets we are sure that they are |
| 327 | 319 | # consumed in the same order as generated by pass 7 |
| 328 | 320 | # (RevTopologicalSort). Per the code in cvs2svn. |
| 329 | 321 | |
| 330 | - # IMHO this will work if and only if none of the symbol | |
| 331 | - # changesets are "backwards", which explains the breaking of | |
| 332 | - # the backward changesets first, in the pre-hook. A difference | |
| 333 | - # to cvs2svn however is that we are breaking all backward | |
| 334 | - # symbol changesets, both branch and tag. cvs2svn can | |
| 335 | - # apparently assume here that tag symbol changesets are not | |
| 336 | - # backwards, ever. We can't, apparently. It is unclear to me | |
| 337 | - # where the difference is. | |
| 338 | - | |
| 339 | - # An interesting thing IMHO, is that after breaking backward | |
| 340 | - # symbol changesets we should not have any circles any | |
| 341 | - # longer. Each circle which was still present had to involve a | |
| 342 | - # backward symbol, and that we split. | |
| 343 | - | |
| 344 | - # Proof: Let us assume we that have a circle | |
| 322 | + # This works if and only if none of the symbol changesets are | |
| 323 | + # "backwards", hence our breaking of the backward changesets | |
| 324 | + # first, in the pre-hook. | |
| 325 | + | |
| 326 | + # Note that tah changesets cannot be backward as they don't | |
| 327 | + # have successors at all. | |
| 328 | + | |
| 329 | + # An interesting thing IMHO, is that after breaking the | |
| 330 | + # backward symbol changesets we should not have any circles | |
| 331 | + # any longer. Each circle which would still be present has to | |
| 332 | + # involve a backward symbol, and we split them all, so there | |
| 333 | + # can't be a circle.. | |
| 334 | + | |
| 335 | + # Proof: | |
| 336 | + # Let us assume we that have a circle | |
| 345 | 337 | # C: R1 -> ... -> Rx -> S -> Ry -> ... -> Rn -> R1 |
| 346 | - # Let us further assume that S is not backward. That means | |
| 347 | - # ORD(Rx) < ORD(Ry). The earlier topological sorting without | |
| 348 | - # symbols now forces this relationship through to be | |
| 349 | - # ORD(Rx) < ORD(R1) < ORD(Rx). | |
| 350 | - # We have reached an impossibility, a paradox. Our initial | |
| 338 | + # Let us further assume that the symbol changeset S in that | |
| 339 | + # circle is not backward. That means ORD(Rx) < ORD(Ry). The | |
| 340 | + # earlier topological sorting without symbols now forces this | |
| 341 | + # relationship through to be ORD(Rx) < ORD(R1) < ORD(Rx). We | |
| 342 | + # have reached an impossibility, a paradox. Our initial | |
| 351 | 343 | # assumption of S not being backward cannot hold. |
| 352 | 344 | # |
| 353 | 345 | # Alternate, direct, reasoning: Without S the chain of |
| 354 | 346 | # dependencies is Ry -> .. -> R1 -> .. -> Rx, therefore |
| 355 | 347 | # ORD(Ry) < ORD(Rx) holds, and this means S is backward. |
| 356 | 348 | |
| 357 | - # NOTE. Even with the backward symbols broken, it is not clear | |
| 358 | - # to me yet what this means in terms of tagging revisions | |
| 359 | - # later, as we now have more than one place where the symbol | |
| 360 | - # occurs on the relevant LOD. | |
| 361 | - | |
| 362 | 349 | struct::set exclude myrevisionchangesets $cset |
| 363 | 350 | |
| 364 | 351 | ::variable mylastpos |
| 365 | 352 | set new [$cset pos] |
| 366 | 353 | |
| 367 | 354 |
| --- tools/cvs2fossil/lib/c2f_pbreakacycle.tcl | |
| +++ tools/cvs2fossil/lib/c2f_pbreakacycle.tcl | |
| @@ -122,57 +122,49 @@ | |
| 122 | # at least one incoming revision changeset which is committed |
| 123 | # after at least one of the outgoing revision changesets, per |
| 124 | # the order computed in pass 6. In "cvs2svn" this is called |
| 125 | # "retrograde". |
| 126 | |
| 127 | # NOTE: We might be able to use our knowledge that we are |
| 128 | # looking at all changesets to create a sql which selects all |
| 129 | # the branch changesets from the state in one go instead of |
| 130 | # having to check each changeset separately. Consider this |
| 131 | # later, get the pass working first. |
| 132 | # |
| 133 | # NOTE 2: Might we even be able to select the backward branch |
| 134 | # changesets too ? |
| 135 | |
| 136 | foreach cset [$graph nodes] { |
| 137 | if {![$cset bysymbol]} continue |
| 138 | CheckAndBreakBackward $graph $cset |
| 139 | } |
| 140 | return |
| 141 | } |
| 142 | |
| 143 | proc CheckAndBreakBackward {graph cset} { |
| 144 | while {[IsBackward $graph $cset]} { |
| 145 | # Knowing that the branch is backward we now look at the |
| 146 | # individual revisions in the changeset and determine |
| 147 | # which of them are responsible for the overlap. This |
| 148 | # allows us to split them into two sets, one of |
| 149 | # non-overlapping revisions, and of overlapping ones. Each |
| 150 | # induces a new changeset, and the second may still be |
| 151 | # backward and need further splitting. Hence the looping. |
| 152 | # |
| 153 | # The border used for the split is the minimal commit |
| 154 | # position among the minimal sucessor commit positions for |
| 155 | # the revisions in the changeset. |
| 156 | |
| 157 | # Note that individual revisions may not have revision |
| 158 | # changesets are predecessors and/or successors, leaving |
| 159 | # the limits partially or completely undefined. |
| 160 | |
| 161 | # limits : dict (revision -> list (max predecessor commit, min sucessor commit)) |
| 162 | |
| 163 | ComputeLimits $cset limits border |
| 164 | |
| 165 | log write 5 breakacycle "Breaking backward changeset [$cset str] with commit position $border as border" |
| 166 | |
| 167 | # Then we sort the file level items based on there they |
| 168 | # sit relative to the border into before and after the |
| 169 | # border. |
| 170 | |
| 171 | SplitRevisions $limits $border normalrevisions backwardrevisions |
| 172 | |
| 173 | set replacements [project::rev split $cset $normalrevisions $backwardrevisions] |
| 174 | cyclebreaker replace $graph $cset $replacements |
| 175 | |
| 176 | # At last check that the normal frament is indeed not |
| 177 | # backward, and iterate over the possibly still backward |
| 178 | # second fragment. |
| @@ -188,18 +180,18 @@ | |
| 188 | } |
| 189 | |
| 190 | proc IsBackward {dg cset} { |
| 191 | # A branch is "backward" if it has at least one incoming |
| 192 | # revision changeset which is committed after at least one of |
| 193 | # the outgoing revision changesets, per the order computed in |
| 194 | # pass 6. |
| 195 | |
| 196 | # Rephrased, the maximal commit position found among the |
| 197 | # incoming revision changesets is larger than the minimal |
| 198 | # commit position found among the outgoing revision |
| 199 | # changesets. Assuming that we have both incoming and outgoing |
| 200 | # revision changesets. |
| 201 | |
| 202 | # The helper "Positions" computes the set of commit positions |
| 203 | # for a set of changesets, which can be a mix of revision and |
| 204 | # symbol changesets. |
| 205 | |
| @@ -231,43 +223,43 @@ | |
| 231 | proc ValidPosition {pos} { expr {$pos ne ""} } |
| 232 | |
| 233 | proc ComputeLimits {cset lv bv} { |
| 234 | upvar 1 $lv thelimits $bv border |
| 235 | |
| 236 | # Initialize the boundaries for all revisions. |
| 237 | |
| 238 | array set limits {} |
| 239 | foreach revision [$cset revisions] { |
| 240 | set limits($revision) {0 {}} |
| 241 | } |
| 242 | |
| 243 | # Compute and store the maximal predecessors per revision |
| 244 | |
| 245 | foreach {revision csets} [$cset predecessormap] { |
| 246 | set s [Positions $csets] |
| 247 | if {![llength $s]} continue |
| 248 | set limits($revision) [lreplace $limits($revision) 0 0 [max $s]] |
| 249 | } |
| 250 | |
| 251 | # Compute and store the minimal successors per revision |
| 252 | |
| 253 | foreach {revision csets} [$cset successormap] { |
| 254 | set s [Positions $csets] |
| 255 | if {![llength $s]} continue |
| 256 | set limits($revision) [lreplace $limits($revision) 1 1 [min $s]] |
| 257 | } |
| 258 | |
| 259 | # Check that the ordering at the file level is correct. We |
| 260 | # cannot have backward ordering per revision, or something is |
| 261 | # wrong. |
| 262 | |
| 263 | foreach revision [array names limits] { |
| 264 | struct::list assign $limits($revision) maxp mins |
| 265 | # Handle min successor position "" as representing infinity |
| 266 | integrity assert { |
| 267 | ($mins eq "") || ($maxp < $mins) |
| 268 | } {Branch revision $revision is backward at file level ($maxp >= $mins)} |
| 269 | } |
| 270 | |
| 271 | # Save the limits for the splitter, and compute the border at |
| 272 | # which to split as the minimum of all minimal successor |
| 273 | # positions. |
| @@ -285,27 +277,27 @@ | |
| 285 | return $res |
| 286 | } |
| 287 | |
| 288 | proc MinSuccessorPosition {item} { lindex $item 1 } |
| 289 | |
| 290 | proc SplitRevisions {limits border nv bv} { |
| 291 | upvar 1 $nv normalrevisions $bv backwardrevisions |
| 292 | |
| 293 | set normalrevisions {} |
| 294 | set backwardrevisions {} |
| 295 | |
| 296 | foreach {rev v} $limits { |
| 297 | struct::list assign $v maxp mins |
| 298 | if {$maxp >= $border} { |
| 299 | lappend backwardrevisions $rev |
| 300 | } else { |
| 301 | lappend normalrevisions $rev |
| 302 | } |
| 303 | } |
| 304 | |
| 305 | integrity assert {[llength $normalrevisions]} {Set of normal revisions is empty} |
| 306 | integrity assert {[llength $backwardrevisions]} {Set of backward revisions is empty} |
| 307 | return |
| 308 | } |
| 309 | |
| 310 | |
| 311 | # # ## ### ##### ######## ############# |
| @@ -325,42 +317,37 @@ | |
| 325 | |
| 326 | # For the revision changesets we are sure that they are |
| 327 | # consumed in the same order as generated by pass 7 |
| 328 | # (RevTopologicalSort). Per the code in cvs2svn. |
| 329 | |
| 330 | # IMHO this will work if and only if none of the symbol |
| 331 | # changesets are "backwards", which explains the breaking of |
| 332 | # the backward changesets first, in the pre-hook. A difference |
| 333 | # to cvs2svn however is that we are breaking all backward |
| 334 | # symbol changesets, both branch and tag. cvs2svn can |
| 335 | # apparently assume here that tag symbol changesets are not |
| 336 | # backwards, ever. We can't, apparently. It is unclear to me |
| 337 | # where the difference is. |
| 338 | |
| 339 | # An interesting thing IMHO, is that after breaking backward |
| 340 | # symbol changesets we should not have any circles any |
| 341 | # longer. Each circle which was still present had to involve a |
| 342 | # backward symbol, and that we split. |
| 343 | |
| 344 | # Proof: Let us assume we that have a circle |
| 345 | # C: R1 -> ... -> Rx -> S -> Ry -> ... -> Rn -> R1 |
| 346 | # Let us further assume that S is not backward. That means |
| 347 | # ORD(Rx) < ORD(Ry). The earlier topological sorting without |
| 348 | # symbols now forces this relationship through to be |
| 349 | # ORD(Rx) < ORD(R1) < ORD(Rx). |
| 350 | # We have reached an impossibility, a paradox. Our initial |
| 351 | # assumption of S not being backward cannot hold. |
| 352 | # |
| 353 | # Alternate, direct, reasoning: Without S the chain of |
| 354 | # dependencies is Ry -> .. -> R1 -> .. -> Rx, therefore |
| 355 | # ORD(Ry) < ORD(Rx) holds, and this means S is backward. |
| 356 | |
| 357 | # NOTE. Even with the backward symbols broken, it is not clear |
| 358 | # to me yet what this means in terms of tagging revisions |
| 359 | # later, as we now have more than one place where the symbol |
| 360 | # occurs on the relevant LOD. |
| 361 | |
| 362 | struct::set exclude myrevisionchangesets $cset |
| 363 | |
| 364 | ::variable mylastpos |
| 365 | set new [$cset pos] |
| 366 | |
| 367 |
| --- tools/cvs2fossil/lib/c2f_pbreakacycle.tcl | |
| +++ tools/cvs2fossil/lib/c2f_pbreakacycle.tcl | |
| @@ -122,57 +122,49 @@ | |
| 122 | # at least one incoming revision changeset which is committed |
| 123 | # after at least one of the outgoing revision changesets, per |
| 124 | # the order computed in pass 6. In "cvs2svn" this is called |
| 125 | # "retrograde". |
| 126 | |
| 127 | foreach cset [$graph nodes] { |
| 128 | if {![$cset isbranch]} continue |
| 129 | CheckAndBreakBackward $graph $cset |
| 130 | } |
| 131 | return |
| 132 | } |
| 133 | |
| 134 | proc CheckAndBreakBackward {graph cset} { |
| 135 | while {[IsBackward $graph $cset]} { |
| 136 | # Knowing that the branch changeset is backward we now |
| 137 | # look at the individual branches in the changeset and |
| 138 | # determine which of them are responsible for the |
| 139 | # overlap. This allows us to split them into two sets, one |
| 140 | # of non-overlapping branches, and of overlapping |
| 141 | # ones. Each set induces a new changeset, and the second |
| 142 | # one may still be backward and in need of further |
| 143 | # splitting. Hence the looping. |
| 144 | # |
| 145 | # The border used for the split is the minimal commit |
| 146 | # position among the minimal sucessor commit positions for |
| 147 | # the branches in the changeset. |
| 148 | |
| 149 | # Note that individual branches may not have changesets |
| 150 | # which are their predecessors and/or successors, leaving |
| 151 | # the limits partially or completely undefined. |
| 152 | |
| 153 | # limits : dict (revision -> list (max predecessor commit, min sucessor commit)) |
| 154 | |
| 155 | ComputeLimits $cset limits border |
| 156 | |
| 157 | log write 5 breakacycle "Breaking backward changeset [$cset str] with commit position $border as border" |
| 158 | |
| 159 | # Secondly we sort the file level items based on there |
| 160 | # they sit relative to the border into before and after |
| 161 | # the border. |
| 162 | |
| 163 | SplitItems $limits $border normalitems backwarditems |
| 164 | |
| 165 | set replacements [project::rev split $cset $normalitems $backwarditems] |
| 166 | cyclebreaker replace $graph $cset $replacements |
| 167 | |
| 168 | # At last check that the normal frament is indeed not |
| 169 | # backward, and iterate over the possibly still backward |
| 170 | # second fragment. |
| @@ -188,18 +180,18 @@ | |
| 180 | } |
| 181 | |
| 182 | proc IsBackward {dg cset} { |
| 183 | # A branch is "backward" if it has at least one incoming |
| 184 | # revision changeset which is committed after at least one of |
| 185 | # the outgoing revision changesets, per the order computed by |
| 186 | # pass 6. |
| 187 | |
| 188 | # Rephrased, the maximal commit position found among the |
| 189 | # incoming revision changesets is larger than the minimal |
| 190 | # commit position found among the outgoing revision |
| 191 | # changesets. Assuming that we have both incoming and outgoing |
| 192 | # revision changesets for the branch. |
| 193 | |
| 194 | # The helper "Positions" computes the set of commit positions |
| 195 | # for a set of changesets, which can be a mix of revision and |
| 196 | # symbol changesets. |
| 197 | |
| @@ -231,43 +223,43 @@ | |
| 223 | proc ValidPosition {pos} { expr {$pos ne ""} } |
| 224 | |
| 225 | proc ComputeLimits {cset lv bv} { |
| 226 | upvar 1 $lv thelimits $bv border |
| 227 | |
| 228 | # Initialize the boundaries for all items. |
| 229 | |
| 230 | array set limits {} |
| 231 | foreach revision [$cset items] { |
| 232 | set limits($revision) {0 {}} |
| 233 | } |
| 234 | |
| 235 | # Compute and store the maximal predecessors per item (branch) |
| 236 | |
| 237 | foreach {item csets} [$cset predecessormap] { |
| 238 | set s [Positions $csets] |
| 239 | if {![llength $s]} continue |
| 240 | set limits($item) [lreplace $limits($item) 0 0 [max $s]] |
| 241 | } |
| 242 | |
| 243 | # Compute and store the minimal successors per item (branch) |
| 244 | |
| 245 | foreach {item csets} [$cset successormap] { |
| 246 | set s [Positions $csets] |
| 247 | if {![llength $s]} continue |
| 248 | set limits($item) [lreplace $limits($item) 1 1 [min $s]] |
| 249 | } |
| 250 | |
| 251 | # Check that the ordering at the file level is correct. We |
| 252 | # cannot have backward ordering per branch, or something is |
| 253 | # wrong. |
| 254 | |
| 255 | foreach item [array names limits] { |
| 256 | struct::list assign $limits($item) maxp mins |
| 257 | # Handle min successor position "" as representing infinity |
| 258 | integrity assert { |
| 259 | ($mins eq "") || ($maxp < $mins) |
| 260 | } {Item <$item> is backward at file level ($maxp >= $mins)} |
| 261 | } |
| 262 | |
| 263 | # Save the limits for the splitter, and compute the border at |
| 264 | # which to split as the minimum of all minimal successor |
| 265 | # positions. |
| @@ -285,27 +277,27 @@ | |
| 277 | return $res |
| 278 | } |
| 279 | |
| 280 | proc MinSuccessorPosition {item} { lindex $item 1 } |
| 281 | |
| 282 | proc SplitItems {limits border nv bv} { |
| 283 | upvar 1 $nv normalitems $bv backwarditems |
| 284 | |
| 285 | set normalitems {} |
| 286 | set backwarditems {} |
| 287 | |
| 288 | foreach {rev v} $limits { |
| 289 | struct::list assign $v maxp mins |
| 290 | if {$maxp >= $border} { |
| 291 | lappend backwarditems $rev |
| 292 | } else { |
| 293 | lappend normalitems $rev |
| 294 | } |
| 295 | } |
| 296 | |
| 297 | integrity assert {[llength $normalitems]} {Set of normal items is empty} |
| 298 | integrity assert {[llength $backwarditems]} {Set of backward items is empty} |
| 299 | return |
| 300 | } |
| 301 | |
| 302 | |
| 303 | # # ## ### ##### ######## ############# |
| @@ -325,42 +317,37 @@ | |
| 317 | |
| 318 | # For the revision changesets we are sure that they are |
| 319 | # consumed in the same order as generated by pass 7 |
| 320 | # (RevTopologicalSort). Per the code in cvs2svn. |
| 321 | |
| 322 | # This works if and only if none of the symbol changesets are |
| 323 | # "backwards", hence our breaking of the backward changesets |
| 324 | # first, in the pre-hook. |
| 325 | |
| 326 | # Note that tah changesets cannot be backward as they don't |
| 327 | # have successors at all. |
| 328 | |
| 329 | # An interesting thing IMHO, is that after breaking the |
| 330 | # backward symbol changesets we should not have any circles |
| 331 | # any longer. Each circle which would still be present has to |
| 332 | # involve a backward symbol, and we split them all, so there |
| 333 | # can't be a circle.. |
| 334 | |
| 335 | # Proof: |
| 336 | # Let us assume we that have a circle |
| 337 | # C: R1 -> ... -> Rx -> S -> Ry -> ... -> Rn -> R1 |
| 338 | # Let us further assume that the symbol changeset S in that |
| 339 | # circle is not backward. That means ORD(Rx) < ORD(Ry). The |
| 340 | # earlier topological sorting without symbols now forces this |
| 341 | # relationship through to be ORD(Rx) < ORD(R1) < ORD(Rx). We |
| 342 | # have reached an impossibility, a paradox. Our initial |
| 343 | # assumption of S not being backward cannot hold. |
| 344 | # |
| 345 | # Alternate, direct, reasoning: Without S the chain of |
| 346 | # dependencies is Ry -> .. -> R1 -> .. -> Rx, therefore |
| 347 | # ORD(Ry) < ORD(Rx) holds, and this means S is backward. |
| 348 | |
| 349 | struct::set exclude myrevisionchangesets $cset |
| 350 | |
| 351 | ::variable mylastpos |
| 352 | set new [$cset pos] |
| 353 | |
| 354 |