Fossil SCM
Split internals of breakinternaldependencies into more manageable pieces in prep for upcoming work on the handling of pseudo-dependencies.
Commit
530168ec30a1e9f382db32b2a6813501bcb25132
Parent
0246783012e9283…
1 file changed
+218
-181
+218
-181
| --- tools/cvs2fossil/lib/c2f_prev.tcl | ||
| +++ tools/cvs2fossil/lib/c2f_prev.tcl | ||
| @@ -53,16 +53,13 @@ | ||
| 53 | 53 | # Keep track of the generated changesets and of the inverse |
| 54 | 54 | # mapping from items to them. |
| 55 | 55 | lappend mychangesets $self |
| 56 | 56 | lappend mytchangesets($cstype) $self |
| 57 | 57 | set myidmap($myid) $self |
| 58 | - foreach iid $items { | |
| 59 | - set key [list $cstype $iid] | |
| 60 | - set myitemmap($key) $self | |
| 61 | - lappend mytitems $key | |
| 62 | - log write 8 csets {MAP+ item <$key> $self = [$self str]} | |
| 63 | - } | |
| 58 | + foreach iid $items { lappend mytitems [list $cstype $iid] } | |
| 59 | + | |
| 60 | + MapItems $cstype $items | |
| 64 | 61 | return |
| 65 | 62 | } |
| 66 | 63 | |
| 67 | 64 | destructor { |
| 68 | 65 | # The main thing is to keep track of the itemmap and remove |
| @@ -69,15 +66,11 @@ | ||
| 69 | 66 | # the object from it. The lists of changesets (mychangesets, |
| 70 | 67 | # mytchangesets) are not maintained (= reduced), for the |
| 71 | 68 | # moment. We may be able to get rid of this entirely, at least |
| 72 | 69 | # for (de)construction and pass InitCSets. |
| 73 | 70 | |
| 74 | - foreach iid $myitems { | |
| 75 | - set key [list $mytype $iid] | |
| 76 | - unset myitemmap($key) | |
| 77 | - log write 8 csets {MAP- item <$key> $self = [$self str]} | |
| 78 | - } | |
| 71 | + UnmapItems $mytype $myitems | |
| 79 | 72 | return |
| 80 | 73 | } |
| 81 | 74 | |
| 82 | 75 | method str {} { |
| 83 | 76 | set str "<" |
| @@ -165,183 +158,28 @@ | ||
| 165 | 158 | # This method inspects the changesets for internal |
| 166 | 159 | # dependencies. Nothing is done if there are no |
| 167 | 160 | # such. Otherwise the changeset is split into a set of |
| 168 | 161 | # fragments without internal dependencies, transforming the |
| 169 | 162 | # internal dependencies into external ones. The new changesets |
| 170 | - # are added to the list of all changesets. | |
| 171 | - | |
| 172 | - # We perform all necessary splits in one go, instead of only | |
| 173 | - # one. The previous algorithm, adapted from cvs2svn, computed | |
| 174 | - # a lot of state which was thrown away and then computed again | |
| 175 | - # for each of the fragments. It should be easier to update and | |
| 176 | - # reuse that state. | |
| 163 | + # generated from the fragment information are added to the | |
| 164 | + # list of all changesets. | |
| 177 | 165 | |
| 178 | 166 | # The code checks only successor dependencies, as this |
| 179 | 167 | # automatically covers the predecessor dependencies as well (A |
| 180 | 168 | # successor dependency a -> b is also a predecessor dependency |
| 181 | 169 | # b -> a). |
| 182 | 170 | |
| 183 | 171 | # Array of dependencies (parent -> child). This is pulled from |
| 184 | 172 | # the state, and limited to successors within the changeset. |
| 185 | 173 | |
| 186 | - array set dependencies {} | |
| 187 | - $mytypeobj internalsuccessors dependencies $myitems | |
| 188 | - if {![array size dependencies]} { | |
| 189 | - return {} | |
| 190 | - } ; # Nothing to break. | |
| 191 | - | |
| 192 | - log write 5 csets ...[$self str]....................................................... | |
| 193 | - vc::tools::mem::mark | |
| 194 | - | |
| 195 | - # We have internal dependencies to break. We now iterate over | |
| 196 | - # all positions in the list (which is chronological, at least | |
| 197 | - # as far as the timestamps are correct and unique) and | |
| 198 | - # determine the best position for the break, by trying to | |
| 199 | - # break as many dependencies as possible in one go. When a | |
| 200 | - # break was found this is redone for the fragments coming and | |
| 201 | - # after, after upding the crossing information. | |
| 202 | - | |
| 203 | - # Data structures: | |
| 204 | - # Map: POS revision id -> position in list. | |
| 205 | - # CROSS position in list -> number of dependencies crossing it | |
| 206 | - # DEPC dependency -> positions it crosses | |
| 207 | - # List: RANGE Of the positions itself. | |
| 208 | - # Map: DELTA position in list -> time delta between its revision | |
| 209 | - # and the next, if any. | |
| 210 | - # A dependency is a single-element map parent -> child | |
| 211 | - | |
| 212 | - # InitializeBreakState initializes their contents after | |
| 213 | - # upvar'ing them from this scope. It uses the information in | |
| 214 | - # DEPENDENCIES to do so. | |
| 215 | - | |
| 216 | - InitializeBreakState $myitems | |
| 217 | - | |
| 218 | - set fragments {} | |
| 219 | - set new [list $range] | |
| 220 | 174 | array set breaks {} |
| 221 | 175 | |
| 222 | - # Instead of one list holding both processed and pending | |
| 223 | - # fragments we use two, one for the framents to process, one | |
| 224 | - # to hold the new fragments, and the latter is copied to the | |
| 225 | - # former when they run out. This keeps the list of pending | |
| 226 | - # fragments short without sacrificing speed by shifting stuff | |
| 227 | - # down. We especially drop the memory of fragments broken | |
| 228 | - # during processing after a short time, instead of letting it | |
| 229 | - # consume memory. | |
| 230 | - | |
| 231 | - while {[llength $new]} { | |
| 232 | - | |
| 233 | - set pending $new | |
| 234 | - set new {} | |
| 235 | - set at 0 | |
| 236 | - | |
| 237 | - while {$at < [llength $pending]} { | |
| 238 | - set current [lindex $pending $at] | |
| 239 | - | |
| 240 | - log write 6 csets {. . .. ... ..... ........ .............} | |
| 241 | - log write 6 csets {Scheduled [join [PRs [lrange $pending $at end]] { }]} | |
| 242 | - log write 6 csets {Considering [PR $current] \[$at/[llength $pending]\]} | |
| 243 | - | |
| 244 | - set best [FindBestBreak $current] | |
| 245 | - | |
| 246 | - if {$best < 0} { | |
| 247 | - # The inspected range has no internal | |
| 248 | - # dependencies. This is a complete fragment. | |
| 249 | - lappend fragments $current | |
| 250 | - | |
| 251 | - log write 6 csets "No breaks, final" | |
| 252 | - } else { | |
| 253 | - # Split the range and schedule the resulting | |
| 254 | - # fragments for further inspection. Remember the | |
| 255 | - # number of dependencies cut before we remove them | |
| 256 | - # from consideration, for documentation later. | |
| 257 | - | |
| 258 | - set breaks($best) $cross($best) | |
| 259 | - | |
| 260 | - log write 6 csets "Best break @ $best, cutting [nsp $cross($best) dependency dependencies]" | |
| 261 | - | |
| 262 | - # Note: The value of best is an abolute location | |
| 263 | - # in myitems. Use the start of current to make it | |
| 264 | - # an index absolute to current. | |
| 265 | - | |
| 266 | - set brel [expr {$best - [lindex $current 0]}] | |
| 267 | - set bnext $brel ; incr bnext | |
| 268 | - set fragbefore [lrange $current 0 $brel] | |
| 269 | - set fragafter [lrange $current $bnext end] | |
| 270 | - | |
| 271 | - log write 6 csets "New pieces [PR $fragbefore] [PR $fragafter]" | |
| 272 | - | |
| 273 | - integrity assert {[llength $fragbefore]} {Found zero-length fragment at the beginning} | |
| 274 | - integrity assert {[llength $fragafter]} {Found zero-length fragment at the end} | |
| 275 | - | |
| 276 | - lappend new $fragbefore $fragafter | |
| 277 | - CutAt $best | |
| 278 | - } | |
| 279 | - | |
| 280 | - incr at | |
| 281 | - } | |
| 282 | - } | |
| 283 | - | |
| 284 | - log write 6 csets ". . .. ... ..... ........ ............." | |
| 285 | - | |
| 286 | - # (*) We clear out the associated part of the myitemmap | |
| 287 | - # in-memory index in preparation for new data. A simple unset | |
| 288 | - # is enough, we have no symbol changesets at this time, and | |
| 289 | - # thus never more than one reference in the list. | |
| 290 | - | |
| 291 | - foreach iid $myitems { | |
| 292 | - set key [list $mytype $iid] | |
| 293 | - unset myitemmap($key) | |
| 294 | - log write 8 csets {MAP- item <$key> $self = [$self str]} | |
| 295 | - } | |
| 296 | - | |
| 297 | - # Create changesets for the fragments, reusing the current one | |
| 298 | - # for the first fragment. We sort them in order to allow | |
| 299 | - # checking for gaps and nice messages. | |
| 300 | - | |
| 301 | - set newcsets {} | |
| 302 | - set fragments [lsort -index 0 -integer $fragments] | |
| 303 | - | |
| 304 | - #puts \t.[join [PRs $fragments] .\n\t.]. | |
| 305 | - | |
| 306 | - Border [lindex $fragments 0] firsts firste | |
| 307 | - | |
| 308 | - integrity assert {$firsts == 0} {Bad fragment start @ $firsts, gap, or before beginning of the range} | |
| 309 | - | |
| 310 | - set laste $firste | |
| 311 | - foreach fragment [lrange $fragments 1 end] { | |
| 312 | - Border $fragment s e | |
| 313 | - integrity assert {$laste == ($s - 1)} {Bad fragment border <$laste | $s>, gap or overlap} | |
| 314 | - | |
| 315 | - set new [$type %AUTO% $myproject $mytype $mysrcid [lrange $myitems $s $e]] | |
| 316 | - lappend newcsets $new | |
| 317 | - incr counter | |
| 318 | - | |
| 319 | - log write 4 csets "Breaking [$self str ] @ $laste, new [$new str], cutting $breaks($laste)" | |
| 320 | - | |
| 321 | - set laste $e | |
| 322 | - } | |
| 323 | - | |
| 324 | - integrity assert { | |
| 325 | - $laste == ([llength $myitems]-1) | |
| 326 | - } {Bad fragment end @ $laste, gap, or beyond end of the range} | |
| 327 | - | |
| 328 | - # Put the first fragment into the current changeset, and | |
| 329 | - # update the in-memory index. We can simply (re)add the items | |
| 330 | - # because we cleared the previously existing information, see | |
| 331 | - # (*) above. Persistence does not matter here, none of the | |
| 332 | - # changesets has been saved to the persistent state yet. | |
| 333 | - | |
| 334 | - set myitems [lrange $myitems 0 $firste] | |
| 335 | - set mytitems [lrange $mytitems 0 $firste] | |
| 336 | - foreach iid $myitems { | |
| 337 | - set key [list $mytype $iid] | |
| 338 | - set myitemmap($key) $self | |
| 339 | - log write 8 csets {MAP+ item <$key> $self = [$self str]} | |
| 340 | - } | |
| 341 | - | |
| 342 | - return $newcsets | |
| 176 | + set fragments [BreakDirectDependencies $myitems breaks] | |
| 177 | + | |
| 178 | + if {![llength $fragments]} { return {} } | |
| 179 | + | |
| 180 | + return [$self CreateFromFragments $fragments counter breaks] | |
| 343 | 181 | } |
| 344 | 182 | |
| 345 | 183 | method persist {} { |
| 346 | 184 | set tid $mycstype($mytype) |
| 347 | 185 | set pid [$myproject id] |
| @@ -379,19 +217,17 @@ | ||
| 379 | 217 | DELETE FROM changeset WHERE cid = $myid; |
| 380 | 218 | DELETE FROM csitem WHERE cid = $myid; |
| 381 | 219 | DELETE FROM cssuccessor WHERE cid = $myid; |
| 382 | 220 | } |
| 383 | 221 | } |
| 384 | - foreach iid $myitems { | |
| 385 | - set key [list $mytype $iid] | |
| 386 | - unset myitemmap($key) | |
| 387 | - log write 8 csets {MAP- item <$key> $self = [$self str]} | |
| 388 | - } | |
| 389 | - set pos [lsearch -exact $mychangesets $self] | |
| 390 | - set mychangesets [lreplace $mychangesets $pos $pos] | |
| 222 | + | |
| 223 | + UnmapItems $mytype $myitems | |
| 224 | + | |
| 225 | + set pos [lsearch -exact $mychangesets $self] | |
| 226 | + set mychangesets [lreplace $mychangesets $pos $pos] | |
| 391 | 227 | set pos [lsearch -exact $mytchangesets($mytype) $self] |
| 392 | - set mytchangesets($mytype) [lreplace $mytchangesets($mytype) $pos $pos] | |
| 228 | + set mytchangesets($mytype) [lreplace $mytchangesets($mytype) $pos $pos] | |
| 393 | 229 | |
| 394 | 230 | # Return the list of predecessors so that they can be adjusted. |
| 395 | 231 | return [struct::list map [state run { |
| 396 | 232 | SELECT cid |
| 397 | 233 | FROM cssuccessor |
| @@ -799,10 +635,182 @@ | ||
| 799 | 635 | set mycounter [state one { SELECT MAX(cid) FROM changeset }] |
| 800 | 636 | return |
| 801 | 637 | } |
| 802 | 638 | |
| 803 | 639 | typemethod num {} { return $mycounter } |
| 640 | + | |
| 641 | + # # ## ### ##### ######## ############# | |
| 642 | + | |
| 643 | + method CreateFromFragments {fragments cv bv} { | |
| 644 | + upvar 1 $cv counter $bv breaks | |
| 645 | + UnmapItems $mytype $myitems | |
| 646 | + | |
| 647 | + # Create changesets for the fragments, reusing the current one | |
| 648 | + # for the first fragment. We sort them in order to allow | |
| 649 | + # checking for gaps and nice messages. | |
| 650 | + | |
| 651 | + set newcsets {} | |
| 652 | + set fragments [lsort -index 0 -integer $fragments] | |
| 653 | + | |
| 654 | + #puts \t.[join [PRs $fragments] .\n\t.]. | |
| 655 | + | |
| 656 | + Border [lindex $fragments 0] firsts firste | |
| 657 | + | |
| 658 | + integrity assert {$firsts == 0} {Bad fragment start @ $firsts, gap, or before beginning of the range} | |
| 659 | + | |
| 660 | + set laste $firste | |
| 661 | + foreach fragment [lrange $fragments 1 end] { | |
| 662 | + Border $fragment s e | |
| 663 | + integrity assert {$laste == ($s - 1)} {Bad fragment border <$laste | $s>, gap or overlap} | |
| 664 | + | |
| 665 | + set new [$type %AUTO% $myproject $mytype $mysrcid [lrange $myitems $s $e]] | |
| 666 | + lappend newcsets $new | |
| 667 | + incr counter | |
| 668 | + | |
| 669 | + log write 4 csets "Breaking [$self str ] @ $laste, new [$new str], cutting $breaks($laste)" | |
| 670 | + | |
| 671 | + set laste $e | |
| 672 | + } | |
| 673 | + | |
| 674 | + integrity assert { | |
| 675 | + $laste == ([llength $myitems]-1) | |
| 676 | + } {Bad fragment end @ $laste, gap, or beyond end of the range} | |
| 677 | + | |
| 678 | + # Put the first fragment into the current changeset, and | |
| 679 | + # update the in-memory index. We can simply (re)add the items | |
| 680 | + # because we cleared the previously existing information, see | |
| 681 | + # 'UnmapItems' above. Persistence does not matter here, none | |
| 682 | + # of the changesets has been saved to the persistent state | |
| 683 | + # yet. | |
| 684 | + | |
| 685 | + set myitems [lrange $myitems 0 $firste] | |
| 686 | + set mytitems [lrange $mytitems 0 $firste] | |
| 687 | + MapItems $mytype $myitems | |
| 688 | + return $newcsets | |
| 689 | + } | |
| 690 | + | |
| 691 | + # # ## ### ##### ######## ############# | |
| 692 | + | |
| 693 | + proc BreakDirectDependencies {theitems bv} { | |
| 694 | + upvar 1 mytypeobj mytypeobj self self $bv breaks | |
| 695 | + | |
| 696 | + array set dependencies {} | |
| 697 | + $mytypeobj internalsuccessors dependencies $theitems | |
| 698 | + if {![array size dependencies]} { | |
| 699 | + return {} | |
| 700 | + } ; # Nothing to break. | |
| 701 | + | |
| 702 | + log write 5 csets ...[$self str]....................................................... | |
| 703 | + vc::tools::mem::mark | |
| 704 | + | |
| 705 | + return [BreakerCore $theitems dependencies breaks] | |
| 706 | + } | |
| 707 | + | |
| 708 | + proc BreakerCore {theitems dv bv} { | |
| 709 | + # Break a set of revisions into fragments which have no | |
| 710 | + # internal dependencies. | |
| 711 | + | |
| 712 | + # We perform all necessary splits in one go, instead of only | |
| 713 | + # one. The previous algorithm, adapted from cvs2svn, computed | |
| 714 | + # a lot of state which was thrown away and then computed again | |
| 715 | + # for each of the fragments. It should be easier to update and | |
| 716 | + # reuse that state. | |
| 717 | + | |
| 718 | + upvar 1 $dv dependencies $bv breaks | |
| 719 | + | |
| 720 | + # We have internal dependencies to break. We now iterate over | |
| 721 | + # all positions in the list (which is chronological, at least | |
| 722 | + # as far as the timestamps are correct and unique) and | |
| 723 | + # determine the best position for the break, by trying to | |
| 724 | + # break as many dependencies as possible in one go. When a | |
| 725 | + # break was found this is redone for the fragments coming and | |
| 726 | + # after, after upding the crossing information. | |
| 727 | + | |
| 728 | + # Data structures: | |
| 729 | + # Map: POS revision id -> position in list. | |
| 730 | + # CROSS position in list -> number of dependencies crossing it | |
| 731 | + # DEPC dependency -> positions it crosses | |
| 732 | + # List: RANGE Of the positions itself. | |
| 733 | + # Map: DELTA position in list -> time delta between its revision | |
| 734 | + # and the next, if any. | |
| 735 | + # A dependency is a single-element map parent -> child | |
| 736 | + | |
| 737 | + # InitializeBreakState initializes their contents after | |
| 738 | + # upvar'ing them from this scope. It uses the information in | |
| 739 | + # DEPENDENCIES to do so. | |
| 740 | + | |
| 741 | + InitializeBreakState $theitems | |
| 742 | + | |
| 743 | + set fragments {} | |
| 744 | + set new [list $range] | |
| 745 | + | |
| 746 | + # Instead of one list holding both processed and pending | |
| 747 | + # fragments we use two, one for the framents to process, one | |
| 748 | + # to hold the new fragments, and the latter is copied to the | |
| 749 | + # former when they run out. This keeps the list of pending | |
| 750 | + # fragments short without sacrificing speed by shifting stuff | |
| 751 | + # down. We especially drop the memory of fragments broken | |
| 752 | + # during processing after a short time, instead of letting it | |
| 753 | + # consume memory. | |
| 754 | + | |
| 755 | + while {[llength $new]} { | |
| 756 | + | |
| 757 | + set pending $new | |
| 758 | + set new {} | |
| 759 | + set at 0 | |
| 760 | + | |
| 761 | + while {$at < [llength $pending]} { | |
| 762 | + set current [lindex $pending $at] | |
| 763 | + | |
| 764 | + log write 6 csets {. . .. ... ..... ........ .............} | |
| 765 | + log write 6 csets {Scheduled [join [PRs [lrange $pending $at end]] { }]} | |
| 766 | + log write 6 csets {Considering [PR $current] \[$at/[llength $pending]\]} | |
| 767 | + | |
| 768 | + set best [FindBestBreak $current] | |
| 769 | + | |
| 770 | + if {$best < 0} { | |
| 771 | + # The inspected range has no internal | |
| 772 | + # dependencies. This is a complete fragment. | |
| 773 | + lappend fragments $current | |
| 774 | + | |
| 775 | + log write 6 csets "No breaks, final" | |
| 776 | + } else { | |
| 777 | + # Split the range and schedule the resulting | |
| 778 | + # fragments for further inspection. Remember the | |
| 779 | + # number of dependencies cut before we remove them | |
| 780 | + # from consideration, for documentation later. | |
| 781 | + | |
| 782 | + set breaks($best) $cross($best) | |
| 783 | + | |
| 784 | + log write 6 csets "Best break @ $best, cutting [nsp $cross($best) dependency dependencies]" | |
| 785 | + | |
| 786 | + # Note: The value of best is an abolute location | |
| 787 | + # in myitems. Use the start of current to make it | |
| 788 | + # an index absolute to current. | |
| 789 | + | |
| 790 | + set brel [expr {$best - [lindex $current 0]}] | |
| 791 | + set bnext $brel ; incr bnext | |
| 792 | + set fragbefore [lrange $current 0 $brel] | |
| 793 | + set fragafter [lrange $current $bnext end] | |
| 794 | + | |
| 795 | + log write 6 csets "New pieces [PR $fragbefore] [PR $fragafter]" | |
| 796 | + | |
| 797 | + integrity assert {[llength $fragbefore]} {Found zero-length fragment at the beginning} | |
| 798 | + integrity assert {[llength $fragafter]} {Found zero-length fragment at the end} | |
| 799 | + | |
| 800 | + lappend new $fragbefore $fragafter | |
| 801 | + CutAt $best | |
| 802 | + } | |
| 803 | + | |
| 804 | + incr at | |
| 805 | + } | |
| 806 | + } | |
| 807 | + | |
| 808 | + log write 6 csets ". . .. ... ..... ........ ............." | |
| 809 | + | |
| 810 | + return $fragments | |
| 811 | + } | |
| 804 | 812 | |
| 805 | 813 | proc InitializeBreakState {revisions} { |
| 806 | 814 | upvar 1 pos pos cross cross range range depc depc delta delta \ |
| 807 | 815 | dependencies dependencies |
| 808 | 816 | |
| @@ -1021,10 +1029,39 @@ | ||
| 1021 | 1029 | |
| 1022 | 1030 | proc Border {range sv ev} { |
| 1023 | 1031 | upvar 1 $sv s $ev e |
| 1024 | 1032 | set s [lindex $range 0] |
| 1025 | 1033 | set e [lindex $range end] |
| 1034 | + return | |
| 1035 | + } | |
| 1036 | + | |
| 1037 | + # # ## ### ##### ######## ############# | |
| 1038 | + | |
| 1039 | + proc UnmapItems {thetype theitems} { | |
| 1040 | + # (*) We clear out the associated part of the myitemmap | |
| 1041 | + # in-memory index in preparation for new data, or as part of | |
| 1042 | + # object destruction. A simple unset is enough, we have no | |
| 1043 | + # symbol changesets at this time, and thus never more than one | |
| 1044 | + # reference in the list. | |
| 1045 | + | |
| 1046 | + upvar 1 myitemmap myitemmap self self | |
| 1047 | + foreach iid $theitems { | |
| 1048 | + set key [list $thetype $iid] | |
| 1049 | + unset myitemmap($key) | |
| 1050 | + log write 8 csets {MAP- item <$key> $self = [$self str]} | |
| 1051 | + } | |
| 1052 | + return | |
| 1053 | + } | |
| 1054 | + | |
| 1055 | + proc MapItems {thetype theitems} { | |
| 1056 | + upvar 1 myitemmap myitemmap self self | |
| 1057 | + | |
| 1058 | + foreach iid $theitems { | |
| 1059 | + set key [list $thetype $iid] | |
| 1060 | + set myitemmap($key) $self | |
| 1061 | + log write 8 csets {MAP+ item <$key> $self = [$self str]} | |
| 1062 | + } | |
| 1026 | 1063 | return |
| 1027 | 1064 | } |
| 1028 | 1065 | |
| 1029 | 1066 | # # ## ### ##### ######## ############# |
| 1030 | 1067 | |
| 1031 | 1068 |
| --- tools/cvs2fossil/lib/c2f_prev.tcl | |
| +++ tools/cvs2fossil/lib/c2f_prev.tcl | |
| @@ -53,16 +53,13 @@ | |
| 53 | # Keep track of the generated changesets and of the inverse |
| 54 | # mapping from items to them. |
| 55 | lappend mychangesets $self |
| 56 | lappend mytchangesets($cstype) $self |
| 57 | set myidmap($myid) $self |
| 58 | foreach iid $items { |
| 59 | set key [list $cstype $iid] |
| 60 | set myitemmap($key) $self |
| 61 | lappend mytitems $key |
| 62 | log write 8 csets {MAP+ item <$key> $self = [$self str]} |
| 63 | } |
| 64 | return |
| 65 | } |
| 66 | |
| 67 | destructor { |
| 68 | # The main thing is to keep track of the itemmap and remove |
| @@ -69,15 +66,11 @@ | |
| 69 | # the object from it. The lists of changesets (mychangesets, |
| 70 | # mytchangesets) are not maintained (= reduced), for the |
| 71 | # moment. We may be able to get rid of this entirely, at least |
| 72 | # for (de)construction and pass InitCSets. |
| 73 | |
| 74 | foreach iid $myitems { |
| 75 | set key [list $mytype $iid] |
| 76 | unset myitemmap($key) |
| 77 | log write 8 csets {MAP- item <$key> $self = [$self str]} |
| 78 | } |
| 79 | return |
| 80 | } |
| 81 | |
| 82 | method str {} { |
| 83 | set str "<" |
| @@ -165,183 +158,28 @@ | |
| 165 | # This method inspects the changesets for internal |
| 166 | # dependencies. Nothing is done if there are no |
| 167 | # such. Otherwise the changeset is split into a set of |
| 168 | # fragments without internal dependencies, transforming the |
| 169 | # internal dependencies into external ones. The new changesets |
| 170 | # are added to the list of all changesets. |
| 171 | |
| 172 | # We perform all necessary splits in one go, instead of only |
| 173 | # one. The previous algorithm, adapted from cvs2svn, computed |
| 174 | # a lot of state which was thrown away and then computed again |
| 175 | # for each of the fragments. It should be easier to update and |
| 176 | # reuse that state. |
| 177 | |
| 178 | # The code checks only successor dependencies, as this |
| 179 | # automatically covers the predecessor dependencies as well (A |
| 180 | # successor dependency a -> b is also a predecessor dependency |
| 181 | # b -> a). |
| 182 | |
| 183 | # Array of dependencies (parent -> child). This is pulled from |
| 184 | # the state, and limited to successors within the changeset. |
| 185 | |
| 186 | array set dependencies {} |
| 187 | $mytypeobj internalsuccessors dependencies $myitems |
| 188 | if {![array size dependencies]} { |
| 189 | return {} |
| 190 | } ; # Nothing to break. |
| 191 | |
| 192 | log write 5 csets ...[$self str]....................................................... |
| 193 | vc::tools::mem::mark |
| 194 | |
| 195 | # We have internal dependencies to break. We now iterate over |
| 196 | # all positions in the list (which is chronological, at least |
| 197 | # as far as the timestamps are correct and unique) and |
| 198 | # determine the best position for the break, by trying to |
| 199 | # break as many dependencies as possible in one go. When a |
| 200 | # break was found this is redone for the fragments coming and |
| 201 | # after, after upding the crossing information. |
| 202 | |
| 203 | # Data structures: |
| 204 | # Map: POS revision id -> position in list. |
| 205 | # CROSS position in list -> number of dependencies crossing it |
| 206 | # DEPC dependency -> positions it crosses |
| 207 | # List: RANGE Of the positions itself. |
| 208 | # Map: DELTA position in list -> time delta between its revision |
| 209 | # and the next, if any. |
| 210 | # A dependency is a single-element map parent -> child |
| 211 | |
| 212 | # InitializeBreakState initializes their contents after |
| 213 | # upvar'ing them from this scope. It uses the information in |
| 214 | # DEPENDENCIES to do so. |
| 215 | |
| 216 | InitializeBreakState $myitems |
| 217 | |
| 218 | set fragments {} |
| 219 | set new [list $range] |
| 220 | array set breaks {} |
| 221 | |
| 222 | # Instead of one list holding both processed and pending |
| 223 | # fragments we use two, one for the framents to process, one |
| 224 | # to hold the new fragments, and the latter is copied to the |
| 225 | # former when they run out. This keeps the list of pending |
| 226 | # fragments short without sacrificing speed by shifting stuff |
| 227 | # down. We especially drop the memory of fragments broken |
| 228 | # during processing after a short time, instead of letting it |
| 229 | # consume memory. |
| 230 | |
| 231 | while {[llength $new]} { |
| 232 | |
| 233 | set pending $new |
| 234 | set new {} |
| 235 | set at 0 |
| 236 | |
| 237 | while {$at < [llength $pending]} { |
| 238 | set current [lindex $pending $at] |
| 239 | |
| 240 | log write 6 csets {. . .. ... ..... ........ .............} |
| 241 | log write 6 csets {Scheduled [join [PRs [lrange $pending $at end]] { }]} |
| 242 | log write 6 csets {Considering [PR $current] \[$at/[llength $pending]\]} |
| 243 | |
| 244 | set best [FindBestBreak $current] |
| 245 | |
| 246 | if {$best < 0} { |
| 247 | # The inspected range has no internal |
| 248 | # dependencies. This is a complete fragment. |
| 249 | lappend fragments $current |
| 250 | |
| 251 | log write 6 csets "No breaks, final" |
| 252 | } else { |
| 253 | # Split the range and schedule the resulting |
| 254 | # fragments for further inspection. Remember the |
| 255 | # number of dependencies cut before we remove them |
| 256 | # from consideration, for documentation later. |
| 257 | |
| 258 | set breaks($best) $cross($best) |
| 259 | |
| 260 | log write 6 csets "Best break @ $best, cutting [nsp $cross($best) dependency dependencies]" |
| 261 | |
| 262 | # Note: The value of best is an abolute location |
| 263 | # in myitems. Use the start of current to make it |
| 264 | # an index absolute to current. |
| 265 | |
| 266 | set brel [expr {$best - [lindex $current 0]}] |
| 267 | set bnext $brel ; incr bnext |
| 268 | set fragbefore [lrange $current 0 $brel] |
| 269 | set fragafter [lrange $current $bnext end] |
| 270 | |
| 271 | log write 6 csets "New pieces [PR $fragbefore] [PR $fragafter]" |
| 272 | |
| 273 | integrity assert {[llength $fragbefore]} {Found zero-length fragment at the beginning} |
| 274 | integrity assert {[llength $fragafter]} {Found zero-length fragment at the end} |
| 275 | |
| 276 | lappend new $fragbefore $fragafter |
| 277 | CutAt $best |
| 278 | } |
| 279 | |
| 280 | incr at |
| 281 | } |
| 282 | } |
| 283 | |
| 284 | log write 6 csets ". . .. ... ..... ........ ............." |
| 285 | |
| 286 | # (*) We clear out the associated part of the myitemmap |
| 287 | # in-memory index in preparation for new data. A simple unset |
| 288 | # is enough, we have no symbol changesets at this time, and |
| 289 | # thus never more than one reference in the list. |
| 290 | |
| 291 | foreach iid $myitems { |
| 292 | set key [list $mytype $iid] |
| 293 | unset myitemmap($key) |
| 294 | log write 8 csets {MAP- item <$key> $self = [$self str]} |
| 295 | } |
| 296 | |
| 297 | # Create changesets for the fragments, reusing the current one |
| 298 | # for the first fragment. We sort them in order to allow |
| 299 | # checking for gaps and nice messages. |
| 300 | |
| 301 | set newcsets {} |
| 302 | set fragments [lsort -index 0 -integer $fragments] |
| 303 | |
| 304 | #puts \t.[join [PRs $fragments] .\n\t.]. |
| 305 | |
| 306 | Border [lindex $fragments 0] firsts firste |
| 307 | |
| 308 | integrity assert {$firsts == 0} {Bad fragment start @ $firsts, gap, or before beginning of the range} |
| 309 | |
| 310 | set laste $firste |
| 311 | foreach fragment [lrange $fragments 1 end] { |
| 312 | Border $fragment s e |
| 313 | integrity assert {$laste == ($s - 1)} {Bad fragment border <$laste | $s>, gap or overlap} |
| 314 | |
| 315 | set new [$type %AUTO% $myproject $mytype $mysrcid [lrange $myitems $s $e]] |
| 316 | lappend newcsets $new |
| 317 | incr counter |
| 318 | |
| 319 | log write 4 csets "Breaking [$self str ] @ $laste, new [$new str], cutting $breaks($laste)" |
| 320 | |
| 321 | set laste $e |
| 322 | } |
| 323 | |
| 324 | integrity assert { |
| 325 | $laste == ([llength $myitems]-1) |
| 326 | } {Bad fragment end @ $laste, gap, or beyond end of the range} |
| 327 | |
| 328 | # Put the first fragment into the current changeset, and |
| 329 | # update the in-memory index. We can simply (re)add the items |
| 330 | # because we cleared the previously existing information, see |
| 331 | # (*) above. Persistence does not matter here, none of the |
| 332 | # changesets has been saved to the persistent state yet. |
| 333 | |
| 334 | set myitems [lrange $myitems 0 $firste] |
| 335 | set mytitems [lrange $mytitems 0 $firste] |
| 336 | foreach iid $myitems { |
| 337 | set key [list $mytype $iid] |
| 338 | set myitemmap($key) $self |
| 339 | log write 8 csets {MAP+ item <$key> $self = [$self str]} |
| 340 | } |
| 341 | |
| 342 | return $newcsets |
| 343 | } |
| 344 | |
| 345 | method persist {} { |
| 346 | set tid $mycstype($mytype) |
| 347 | set pid [$myproject id] |
| @@ -379,19 +217,17 @@ | |
| 379 | DELETE FROM changeset WHERE cid = $myid; |
| 380 | DELETE FROM csitem WHERE cid = $myid; |
| 381 | DELETE FROM cssuccessor WHERE cid = $myid; |
| 382 | } |
| 383 | } |
| 384 | foreach iid $myitems { |
| 385 | set key [list $mytype $iid] |
| 386 | unset myitemmap($key) |
| 387 | log write 8 csets {MAP- item <$key> $self = [$self str]} |
| 388 | } |
| 389 | set pos [lsearch -exact $mychangesets $self] |
| 390 | set mychangesets [lreplace $mychangesets $pos $pos] |
| 391 | set pos [lsearch -exact $mytchangesets($mytype) $self] |
| 392 | set mytchangesets($mytype) [lreplace $mytchangesets($mytype) $pos $pos] |
| 393 | |
| 394 | # Return the list of predecessors so that they can be adjusted. |
| 395 | return [struct::list map [state run { |
| 396 | SELECT cid |
| 397 | FROM cssuccessor |
| @@ -799,10 +635,182 @@ | |
| 799 | set mycounter [state one { SELECT MAX(cid) FROM changeset }] |
| 800 | return |
| 801 | } |
| 802 | |
| 803 | typemethod num {} { return $mycounter } |
| 804 | |
| 805 | proc InitializeBreakState {revisions} { |
| 806 | upvar 1 pos pos cross cross range range depc depc delta delta \ |
| 807 | dependencies dependencies |
| 808 | |
| @@ -1021,10 +1029,39 @@ | |
| 1021 | |
| 1022 | proc Border {range sv ev} { |
| 1023 | upvar 1 $sv s $ev e |
| 1024 | set s [lindex $range 0] |
| 1025 | set e [lindex $range end] |
| 1026 | return |
| 1027 | } |
| 1028 | |
| 1029 | # # ## ### ##### ######## ############# |
| 1030 | |
| 1031 |
| --- tools/cvs2fossil/lib/c2f_prev.tcl | |
| +++ tools/cvs2fossil/lib/c2f_prev.tcl | |
| @@ -53,16 +53,13 @@ | |
| 53 | # Keep track of the generated changesets and of the inverse |
| 54 | # mapping from items to them. |
| 55 | lappend mychangesets $self |
| 56 | lappend mytchangesets($cstype) $self |
| 57 | set myidmap($myid) $self |
| 58 | foreach iid $items { lappend mytitems [list $cstype $iid] } |
| 59 | |
| 60 | MapItems $cstype $items |
| 61 | return |
| 62 | } |
| 63 | |
| 64 | destructor { |
| 65 | # The main thing is to keep track of the itemmap and remove |
| @@ -69,15 +66,11 @@ | |
| 66 | # the object from it. The lists of changesets (mychangesets, |
| 67 | # mytchangesets) are not maintained (= reduced), for the |
| 68 | # moment. We may be able to get rid of this entirely, at least |
| 69 | # for (de)construction and pass InitCSets. |
| 70 | |
| 71 | UnmapItems $mytype $myitems |
| 72 | return |
| 73 | } |
| 74 | |
| 75 | method str {} { |
| 76 | set str "<" |
| @@ -165,183 +158,28 @@ | |
| 158 | # This method inspects the changesets for internal |
| 159 | # dependencies. Nothing is done if there are no |
| 160 | # such. Otherwise the changeset is split into a set of |
| 161 | # fragments without internal dependencies, transforming the |
| 162 | # internal dependencies into external ones. The new changesets |
| 163 | # generated from the fragment information are added to the |
| 164 | # list of all changesets. |
| 165 | |
| 166 | # The code checks only successor dependencies, as this |
| 167 | # automatically covers the predecessor dependencies as well (A |
| 168 | # successor dependency a -> b is also a predecessor dependency |
| 169 | # b -> a). |
| 170 | |
| 171 | # Array of dependencies (parent -> child). This is pulled from |
| 172 | # the state, and limited to successors within the changeset. |
| 173 | |
| 174 | array set breaks {} |
| 175 | |
| 176 | set fragments [BreakDirectDependencies $myitems breaks] |
| 177 | |
| 178 | if {![llength $fragments]} { return {} } |
| 179 | |
| 180 | return [$self CreateFromFragments $fragments counter breaks] |
| 181 | } |
| 182 | |
| 183 | method persist {} { |
| 184 | set tid $mycstype($mytype) |
| 185 | set pid [$myproject id] |
| @@ -379,19 +217,17 @@ | |
| 217 | DELETE FROM changeset WHERE cid = $myid; |
| 218 | DELETE FROM csitem WHERE cid = $myid; |
| 219 | DELETE FROM cssuccessor WHERE cid = $myid; |
| 220 | } |
| 221 | } |
| 222 | |
| 223 | UnmapItems $mytype $myitems |
| 224 | |
| 225 | set pos [lsearch -exact $mychangesets $self] |
| 226 | set mychangesets [lreplace $mychangesets $pos $pos] |
| 227 | set pos [lsearch -exact $mytchangesets($mytype) $self] |
| 228 | set mytchangesets($mytype) [lreplace $mytchangesets($mytype) $pos $pos] |
| 229 | |
| 230 | # Return the list of predecessors so that they can be adjusted. |
| 231 | return [struct::list map [state run { |
| 232 | SELECT cid |
| 233 | FROM cssuccessor |
| @@ -799,10 +635,182 @@ | |
| 635 | set mycounter [state one { SELECT MAX(cid) FROM changeset }] |
| 636 | return |
| 637 | } |
| 638 | |
| 639 | typemethod num {} { return $mycounter } |
| 640 | |
| 641 | # # ## ### ##### ######## ############# |
| 642 | |
| 643 | method CreateFromFragments {fragments cv bv} { |
| 644 | upvar 1 $cv counter $bv breaks |
| 645 | UnmapItems $mytype $myitems |
| 646 | |
| 647 | # Create changesets for the fragments, reusing the current one |
| 648 | # for the first fragment. We sort them in order to allow |
| 649 | # checking for gaps and nice messages. |
| 650 | |
| 651 | set newcsets {} |
| 652 | set fragments [lsort -index 0 -integer $fragments] |
| 653 | |
| 654 | #puts \t.[join [PRs $fragments] .\n\t.]. |
| 655 | |
| 656 | Border [lindex $fragments 0] firsts firste |
| 657 | |
| 658 | integrity assert {$firsts == 0} {Bad fragment start @ $firsts, gap, or before beginning of the range} |
| 659 | |
| 660 | set laste $firste |
| 661 | foreach fragment [lrange $fragments 1 end] { |
| 662 | Border $fragment s e |
| 663 | integrity assert {$laste == ($s - 1)} {Bad fragment border <$laste | $s>, gap or overlap} |
| 664 | |
| 665 | set new [$type %AUTO% $myproject $mytype $mysrcid [lrange $myitems $s $e]] |
| 666 | lappend newcsets $new |
| 667 | incr counter |
| 668 | |
| 669 | log write 4 csets "Breaking [$self str ] @ $laste, new [$new str], cutting $breaks($laste)" |
| 670 | |
| 671 | set laste $e |
| 672 | } |
| 673 | |
| 674 | integrity assert { |
| 675 | $laste == ([llength $myitems]-1) |
| 676 | } {Bad fragment end @ $laste, gap, or beyond end of the range} |
| 677 | |
| 678 | # Put the first fragment into the current changeset, and |
| 679 | # update the in-memory index. We can simply (re)add the items |
| 680 | # because we cleared the previously existing information, see |
| 681 | # 'UnmapItems' above. Persistence does not matter here, none |
| 682 | # of the changesets has been saved to the persistent state |
| 683 | # yet. |
| 684 | |
| 685 | set myitems [lrange $myitems 0 $firste] |
| 686 | set mytitems [lrange $mytitems 0 $firste] |
| 687 | MapItems $mytype $myitems |
| 688 | return $newcsets |
| 689 | } |
| 690 | |
| 691 | # # ## ### ##### ######## ############# |
| 692 | |
| 693 | proc BreakDirectDependencies {theitems bv} { |
| 694 | upvar 1 mytypeobj mytypeobj self self $bv breaks |
| 695 | |
| 696 | array set dependencies {} |
| 697 | $mytypeobj internalsuccessors dependencies $theitems |
| 698 | if {![array size dependencies]} { |
| 699 | return {} |
| 700 | } ; # Nothing to break. |
| 701 | |
| 702 | log write 5 csets ...[$self str]....................................................... |
| 703 | vc::tools::mem::mark |
| 704 | |
| 705 | return [BreakerCore $theitems dependencies breaks] |
| 706 | } |
| 707 | |
| 708 | proc BreakerCore {theitems dv bv} { |
| 709 | # Break a set of revisions into fragments which have no |
| 710 | # internal dependencies. |
| 711 | |
| 712 | # We perform all necessary splits in one go, instead of only |
| 713 | # one. The previous algorithm, adapted from cvs2svn, computed |
| 714 | # a lot of state which was thrown away and then computed again |
| 715 | # for each of the fragments. It should be easier to update and |
| 716 | # reuse that state. |
| 717 | |
| 718 | upvar 1 $dv dependencies $bv breaks |
| 719 | |
| 720 | # We have internal dependencies to break. We now iterate over |
| 721 | # all positions in the list (which is chronological, at least |
| 722 | # as far as the timestamps are correct and unique) and |
| 723 | # determine the best position for the break, by trying to |
| 724 | # break as many dependencies as possible in one go. When a |
| 725 | # break was found this is redone for the fragments coming and |
| 726 | # after, after upding the crossing information. |
| 727 | |
| 728 | # Data structures: |
| 729 | # Map: POS revision id -> position in list. |
| 730 | # CROSS position in list -> number of dependencies crossing it |
| 731 | # DEPC dependency -> positions it crosses |
| 732 | # List: RANGE Of the positions itself. |
| 733 | # Map: DELTA position in list -> time delta between its revision |
| 734 | # and the next, if any. |
| 735 | # A dependency is a single-element map parent -> child |
| 736 | |
| 737 | # InitializeBreakState initializes their contents after |
| 738 | # upvar'ing them from this scope. It uses the information in |
| 739 | # DEPENDENCIES to do so. |
| 740 | |
| 741 | InitializeBreakState $theitems |
| 742 | |
| 743 | set fragments {} |
| 744 | set new [list $range] |
| 745 | |
| 746 | # Instead of one list holding both processed and pending |
| 747 | # fragments we use two, one for the framents to process, one |
| 748 | # to hold the new fragments, and the latter is copied to the |
| 749 | # former when they run out. This keeps the list of pending |
| 750 | # fragments short without sacrificing speed by shifting stuff |
| 751 | # down. We especially drop the memory of fragments broken |
| 752 | # during processing after a short time, instead of letting it |
| 753 | # consume memory. |
| 754 | |
| 755 | while {[llength $new]} { |
| 756 | |
| 757 | set pending $new |
| 758 | set new {} |
| 759 | set at 0 |
| 760 | |
| 761 | while {$at < [llength $pending]} { |
| 762 | set current [lindex $pending $at] |
| 763 | |
| 764 | log write 6 csets {. . .. ... ..... ........ .............} |
| 765 | log write 6 csets {Scheduled [join [PRs [lrange $pending $at end]] { }]} |
| 766 | log write 6 csets {Considering [PR $current] \[$at/[llength $pending]\]} |
| 767 | |
| 768 | set best [FindBestBreak $current] |
| 769 | |
| 770 | if {$best < 0} { |
| 771 | # The inspected range has no internal |
| 772 | # dependencies. This is a complete fragment. |
| 773 | lappend fragments $current |
| 774 | |
| 775 | log write 6 csets "No breaks, final" |
| 776 | } else { |
| 777 | # Split the range and schedule the resulting |
| 778 | # fragments for further inspection. Remember the |
| 779 | # number of dependencies cut before we remove them |
| 780 | # from consideration, for documentation later. |
| 781 | |
| 782 | set breaks($best) $cross($best) |
| 783 | |
| 784 | log write 6 csets "Best break @ $best, cutting [nsp $cross($best) dependency dependencies]" |
| 785 | |
| 786 | # Note: The value of best is an abolute location |
| 787 | # in myitems. Use the start of current to make it |
| 788 | # an index absolute to current. |
| 789 | |
| 790 | set brel [expr {$best - [lindex $current 0]}] |
| 791 | set bnext $brel ; incr bnext |
| 792 | set fragbefore [lrange $current 0 $brel] |
| 793 | set fragafter [lrange $current $bnext end] |
| 794 | |
| 795 | log write 6 csets "New pieces [PR $fragbefore] [PR $fragafter]" |
| 796 | |
| 797 | integrity assert {[llength $fragbefore]} {Found zero-length fragment at the beginning} |
| 798 | integrity assert {[llength $fragafter]} {Found zero-length fragment at the end} |
| 799 | |
| 800 | lappend new $fragbefore $fragafter |
| 801 | CutAt $best |
| 802 | } |
| 803 | |
| 804 | incr at |
| 805 | } |
| 806 | } |
| 807 | |
| 808 | log write 6 csets ". . .. ... ..... ........ ............." |
| 809 | |
| 810 | return $fragments |
| 811 | } |
| 812 | |
| 813 | proc InitializeBreakState {revisions} { |
| 814 | upvar 1 pos pos cross cross range range depc depc delta delta \ |
| 815 | dependencies dependencies |
| 816 | |
| @@ -1021,10 +1029,39 @@ | |
| 1029 | |
| 1030 | proc Border {range sv ev} { |
| 1031 | upvar 1 $sv s $ev e |
| 1032 | set s [lindex $range 0] |
| 1033 | set e [lindex $range end] |
| 1034 | return |
| 1035 | } |
| 1036 | |
| 1037 | # # ## ### ##### ######## ############# |
| 1038 | |
| 1039 | proc UnmapItems {thetype theitems} { |
| 1040 | # (*) We clear out the associated part of the myitemmap |
| 1041 | # in-memory index in preparation for new data, or as part of |
| 1042 | # object destruction. A simple unset is enough, we have no |
| 1043 | # symbol changesets at this time, and thus never more than one |
| 1044 | # reference in the list. |
| 1045 | |
| 1046 | upvar 1 myitemmap myitemmap self self |
| 1047 | foreach iid $theitems { |
| 1048 | set key [list $thetype $iid] |
| 1049 | unset myitemmap($key) |
| 1050 | log write 8 csets {MAP- item <$key> $self = [$self str]} |
| 1051 | } |
| 1052 | return |
| 1053 | } |
| 1054 | |
| 1055 | proc MapItems {thetype theitems} { |
| 1056 | upvar 1 myitemmap myitemmap self self |
| 1057 | |
| 1058 | foreach iid $theitems { |
| 1059 | set key [list $thetype $iid] |
| 1060 | set myitemmap($key) $self |
| 1061 | log write 8 csets {MAP+ item <$key> $self = [$self str]} |
| 1062 | } |
| 1063 | return |
| 1064 | } |
| 1065 | |
| 1066 | # # ## ### ##### ######## ############# |
| 1067 | |
| 1068 |