Overview
| SHA1 Hash: | 711e000206259f355854b886f14b25e6d9601389 |
|---|---|
| Date: | 2007-12-04 04:54:10 |
| User: | aku |
| Comment: | Reworked ComputeLimits in the last breaker pass. Moved the heavy computation of the max predecessor / min successor data down to the sql in the changeset class. |
| Timelines: | ancestors | descendants | both | trunk |
| Other Links: | files | ZIP archive | manifest |
Tags And Properties
- branch=trunk inherited from [a28c83647d]
- sym-trunk inherited from [a28c83647d]
Changes
[hide diffs]Modified tools/cvs2fossil/lib/c2f_pbreakacycle.tcl from [7e073778fc] to [4af9517982].
@@ -107,16 +107,21 @@
proc LoadCommitOrder {} {
::variable mycset
::variable myrevisionchangesets
+ log write 2 breakacycle {Loading revision commit order}
+
+ set n 0
state transaction {
foreach {cid pos} [state run { SELECT cid, pos FROM csorder }] {
+ log progress 2 breakacycle $n
set cset [project::rev of $cid]
$cset setpos $pos
set mycset($pos) $cset
lappend myrevisionchangesets $cset
+ incr n
}
}
return
}
@@ -149,35 +154,33 @@
# overlap. This allows us to split them into two sets, one
# of non-overlapping branches, and of overlapping
# ones. Each set induces a new changeset, and the second
# one may still be backward and in need of further
# splitting. Hence the looping.
- #
+
# The border used for the split is the minimal commit
# position among the minimal sucessor commit positions for
- # the branches in the changeset.
-
- # Note that individual branches may not have changesets
- # which are their predecessors and/or successors, leaving
- # the limits partially or completely undefined.
+ # the branches in the changeset. We sort the file level
+ # items based on there they sit relative to the border
+ # into before and after the border. As the branches cannot
+ # be backward at file level thos before the border cannot
+ # generate a backward symbol changeset, however the
+ # branches after may constitute another backward branch
+ # with a new border.
# limits : dict (revision -> list (max predecessor commit, min sucessor commit))
ComputeLimits $cset limits border
- log write 5 breakacycle "Breaking backward changeset [$cset str] with commit position $border as border"
-
- # Secondly we sort the file level items based on there
- # they sit relative to the border into before and after
- # the border.
+ log write 5 breakacycle "Breaking backward changeset [$cset str] using commit position $border as border"
SplitItems $limits $border normalitems backwarditems
set replacements [project::rev split $cset $normalitems $backwarditems]
cyclebreaker replace $graph $cset $replacements
- # At last check that the normal frament is indeed not
+ # At last we check that the normal frament is indeed not
# backward, and iterate over the possibly still backward
# second fragment.
struct::list assign $replacements normal backward
integrity assert {
@@ -233,84 +236,85 @@
proc ValidPosition {pos} { expr {$pos ne ""} }
proc ComputeLimits {cset lv bv} {
upvar 1 $lv thelimits $bv border
- # Initialize the boundaries for all items.
-
- array set limits {}
- foreach revision [$cset items] {
- set limits($revision) {0 {}}
- }
-
- # Compute and store the maximal predecessors per item (branch)
-
- foreach {item csets} [$cset predecessormap] {
- set s [Positions $csets]
- if {![llength $s]} continue
- set limits($item) [lreplace $limits($item) 0 0 [max $s]]
+ # Individual branches may not have revision changesets which
+ # are their predecessors and/or successors, leaving the limits
+ # partially or completely undefined. To overcome this
+ # initialize boundaries for all items with proper defaults (-1
+ # for max, {} for min, representing +infinity).
+
+ array set maxpa {}
+ array set minsa {}
+ foreach item [$cset items] {
+ set maxpa($item) -1
+ set minsa($item) {}
}
- # Compute and store the minimal successors per item (branch)
-
- foreach {item csets} [$cset successormap] {
- set s [Positions $csets]
- if {![llength $s]} continue
- set limits($item) [lreplace $limits($item) 1 1 [min $s]]
- }
+ # Get the limits from the database, for the items which
+ # actually have such, and merge the information with the
+ # defaults.
+
+ struct::list assign [$cset limits] maxpdict minsdict
+
+ array set maxpa $maxpdict
+ array set minsa $minsdict
# Check that the ordering at the file level is correct. We
# cannot have backward ordering per branch, or something is
# wrong.
foreach item [array names limits] {
- struct::list assign $limits($item) maxp mins
- # Handle min successor position "" as representing infinity
+ set mins $minsa($item)
+ set maxp $maxp($item)
+ # Note that for the min successor position "" represents
+ # +infinity
integrity assert {
($mins eq "") || ($maxp < $mins)
} {Item <$item> is backward at file level ($maxp >= $mins)}
}
# Save the limits for the splitter, and compute the border at
# which to split as the minimum of all minimal successor
# positions.
- set thelimits [array get limits]
- set border [min [struct::list filter [struct::list map [Values $thelimits] \
- [myproc MinSuccessorPosition]] \
- [myproc ValidPosition]]]
+ # Compute the border at which to split as the minimum of all
+ # minimal successor positions. By using the database info we
+ # automatically/implicitly filter out anything without a min
+ # successor. Further the data going into the comparison with
+ # the border is put together.
+
+ set border [min [Values $minsdict]]
+ set thelimits [array get maxpa]
return
}
proc Values {dict} {
set res {}
foreach {k v} $dict { lappend res $v }
return $res
}
- proc MinSuccessorPosition {item} { lindex $item 1 }
-
proc SplitItems {limits border nv bv} {
upvar 1 $nv normalitems $bv backwarditems
set normalitems {}
set backwarditems {}
- foreach {rev v} $limits {
- struct::list assign $v maxp mins
+ foreach {item maxp} $limits {
if {$maxp >= $border} {
- lappend backwarditems $rev
+ lappend backwarditems $item
} else {
- lappend normalitems $rev
+ lappend normalitems $item
}
}
integrity assert {[llength $normalitems]} {Set of normal items is empty}
integrity assert {[llength $backwarditems]} {Set of backward items is empty}
return
}
-
# # ## ### ##### ######## #############
proc KeepOrder {graph at cset} {
::variable myatfmt
Modified tools/cvs2fossil/lib/c2f_prev.tcl from [bf483d028a] to [f2b05566df].
@@ -379,10 +379,15 @@
return
}
method timerange {} { return [$mytypeobj timerange $myitems] }
+ method limits {} {
+ struct::list assign [$mytypeobj limits $myitems] maxp mins
+ return [list [TagItemDict $maxp $mytype] [TagItemDict $mins $mytype]]
+ }
+
method drop {} {
log write 8 csets {Dropping $self = [$self str]}
state transaction {
state run {
@@ -493,10 +498,16 @@
proc Untag1 {cstype theitem} {
struct::list assign $theitem t i
integrity assert {$cstype eq $t} {Item $i's type is '$t', expected '$cstype'}
return $i
+ }
+
+ proc TagItemDict {itemdict cstype} {
+ set res {}
+ foreach {i v} $itemdict { lappend res [list $cstype $i] $v }
+ return $res
}
proc ValidateFragments {cset fragments} {
# Check the various integrity constraints for the fragments
# specifying how to split the changeset:
@@ -1460,10 +1471,49 @@
AND CI.iid = T.tid
AND C.cid = CI.cid
AND C.type = 1
"]
return
+ }
+
+ typemethod limits {branches} {
+ # Notes. This method exists only for branches. It is needed to
+ # get detailed information about a backward branch. It does
+ # not apply to tags, nor revisions. The queries can also
+ # restrict themselves to the revision sucessors/predecessors
+ # of branches, as only they have ordering data and thus can
+ # cause the backwardness.
+
+ set theset ('[join $branches {','}]')
+
+ set maxp [state run [subst -nocommands -nobackslashes {
+ -- maximal predecessor position per branch
+ SELECT B.bid, MAX (CO.pos)
+ FROM branch B, revision R, csitem CI, changeset C, csorder CO
+ WHERE B.bid IN $theset
+ AND B.root = R.rid
+ AND CI.iid = R.rid
+ AND C.cid = CI.cid
+ AND C.type = 0
+ AND CO.cid = C.cid
+ GROUP BY B.bid
+ }]]
+
+ set mins [state run [subst -nocommands -nobackslashes {
+ -- minimal successor position per branch
+ SELECT B.bid, MIN (CO.pos)
+ FROM branch B, revision R, csitem CI, changeset C, csorder CO
+ WHERE B.bid IN $theset
+ AND B.first = R.rid
+ AND CI.iid = R.rid
+ AND C.cid = CI.cid
+ AND C.type = 0
+ AND CO.cid = C.cid
+ GROUP BY B.bid
+ }]]
+
+ return [list $maxp $mins]
}
# # ## ### ##### ######## #############
## Configuration