Overview
| SHA1 Hash: | e50f9ed55ec4e44c90e50fad10245879c2f2b7da |
|---|---|
| Date: | 2007-11-22 04:21:37 |
| User: | aku |
| Comment: | Continued work on pass 8. Completed the handling of backward branches, file level analysis and splitting them. Extended changesets with the necessary methods to the predecessor data and proper per-revision maps. |
| 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 [2f61c9c570] to [2878f83999].
@@ -121,11 +121,11 @@
# looking at all changesets to create a sql which selects all
# the branch changesets from the state in one go instead of
# having to check each changeset separately. Consider this
# later, get the pass working first.
#
- # NOTE 2: Might we even be able to select the retrograde
+ # NOTE 2: Might we even be able to select the backward branch
# changesets too ?
foreach cset [$graph nodes] {
if {![$cset isbranch]} continue
CheckAndBreakBackwardBranch $graph $cset
@@ -135,11 +135,49 @@
proc CheckAndBreakBackwardBranch {graph cset} {
while {[IsABackwardBranch $graph $cset]} {
log write 5 breakacycle "Breaking backward branch changeset <[$cset id]>"
- break
+ # Knowing that the branch is backward we now look at the
+ # individual revisions in the changeset and determine
+ # which of them are responsible for the overlap. This
+ # allows us to split them into two sets, one of
+ # non-overlapping revisions, and of overlapping ones. Each
+ # induces a new changeset, and the second may still be
+ # backward and need further splitting. Hence the looping.
+ #
+ # The border used for the split is the minimal commit
+ # position among the minimal sucessor commit positions for
+ # the revisions in the changeset.
+
+ # Note that individual revisions may not have revision
+ # changesets are predecessors and/or successors, leaving
+ # the limits partially or completely undefined.
+
+ # limits : dict (revision -> list (max predecessor commit, min sucessor commit))
+
+ ComputeLimits $cset limits border
+
+ log write 6 breakacycle "At commit position border $border"
+
+ # Then we sort the file level items based on there they
+ # sit relative to the border into before and after the
+ # border.
+
+ SplitRevisions $limits normalrevisions backwardrevisions
+
+ set replacements [project::rev split $cset $normalrevisions $backwardrevisions]
+ cyclebreaker replace $graph $cset $replacements
+
+ # At last check that the normal frament is indeed not
+ # backward, and iterate over the possibly still backward
+ # second fragment.
+
+ struct::list assign $replacements normal backward
+ if {[IsABackwardBranch $dg $normal]} { trouble internal "The normal fragment is unexpectedly a backward branch" }
+
+ set cset $backward
}
return
}
proc IsABackwardBranch {dg cset} {
@@ -182,10 +220,89 @@
[myproc ValidPosition]]
}
proc ToPosition {cset} { $cset pos }
proc ValidPosition {pos} { expr {$pos ne ""} }
+
+ proc ComputeLimits {cset lv bv} {
+ upvar 1 $lv thelimits $bv border
+
+ # Initialize the boundaries for all revisions.
+
+ array set limits {}
+ foreach revision [$cset revisions] {
+ set limits($revision) {0 {}}
+ }
+
+ # Compute and store the maximal predecessors per revision
+
+ foreach {revision csets} [$cset predecessormap] {
+ set s [Positions $csets]
+ if {![llength $s]} continue
+ set limits($revision) [lreplace $limits($revision) 0 0 [max $s]]
+ }
+
+ # Compute and store the minimal successors per revision
+
+ foreach {revision csets} [$cset successormap] {
+ set s [Positions $csets]
+ if {![llength $s]} continue
+ set limits($revision) [lreplace $limits($revision) 1 1 [min $s]]
+ }
+
+ # Check that the ordering at the file level is correct. We
+ # cannot have backward ordering per revision, or something is
+ # wrong.
+
+ foreach revision [array names limits] {
+ struct::list assign $limits($revision) maxp mins
+ # Handle min successor position "" as representing infinity
+ if {$mins eq ""} continue
+ if {$maxp < $mins} continue
+
+ trouble internal "Branch revision $revision 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]]]
+ return
+ }
+
+ proc Values {dict} {
+ set res {}
+ foreach {k v} $dict { lappend res $v }
+ return $res
+ }
+
+ proc MinSuccessorPosition {item} { lindex $item 1 }
+
+ proc SplitRevisions {limits nv bv} {
+ upvar 1 $nv normalrevisions $bv backwardrevisions
+
+ set normalrevisions {}
+ set backwardrevisions {}
+
+ foreach {rev v} $limits {
+ struct::list assign $v maxp mins
+ if {$maxp >= $border} {
+ lappend backwardrevisions $rev
+ } else {
+ lappend normalrevisions $rev
+ }
+ }
+
+ if {![llength $normalrevisions]} { trouble internal "Set of normal revisions is empty" }
+ if {![llength $backwardrevisions]} { trouble internal "Set of backward revisions is empty" }
+ return
+ }
+
# # ## ### ##### ######## #############
proc SaveOrder {cset pos} {
}
Modified tools/cvs2fossil/lib/c2f_prev.tcl from [75f13681e5] to [e0ef55994e].
@@ -67,10 +67,22 @@
($mybranchcode == [state one {
SELECT type FROM symbol WHERE sid = $mysrcid
}])}]
}
+ method successormap {} {
+ # NOTE / FUTURE: Possible bottleneck.
+ array set tmp {}
+ foreach {rev children} [$self nextmap] {
+ foreach child $children {
+ lappend tmp($rev) $myrevmap($child)
+ }
+ set tmp($rev) [lsort -unique $tmp($rev)]
+ }
+ return [array get tmp]
+ }
+
method successors {} {
# NOTE / FUTURE: Possible bottleneck.
set csets {}
foreach {_ children} [$self nextmap] {
foreach child $children {
@@ -78,16 +90,36 @@
}
}
return [lsort -unique $csets]
}
+ method predecessormap {} {
+ # NOTE / FUTURE: Possible bottleneck.
+ array set tmp {}
+ foreach {rev children} [$self premap] {
+ foreach child $children {
+ lappend tmp($rev) $myrevmap($child)
+ }
+ set tmp($rev) [lsort -unique $tmp($rev)]
+ }
+ return [array get tmp]
+ }
+
# revision -> list (revision)
method nextmap {} {
if {[llength $mynextmap]} { return $mynextmap }
PullSuccessorRevisions tmp $myrevisions
set mynextmap [array get tmp]
return $mynextmap
+ }
+
+ # revision -> list (revision)
+ method premap {} {
+ if {[llength $mypremap]} { return $mypremap }
+ PullPredecessorRevisions tmp $myrevisions
+ set mypremap [array get tmp]
+ return $mypremap
}
method breakinternaldependencies {} {
# This method inspects the changesets for internal
# dependencies. Nothing is done if there are no
@@ -303,10 +335,14 @@
# from.
variable mysrcid {} ; # Id of the metadata or symbol the cset
# is based on.
variable myrevisions {} ; # List of the file level revisions in
# the cset.
+ variable mypremap {} ; # Dictionary mapping from the revisions
+ # to their predecessors. Cache to avoid
+ # loading this from the state more than
+ # once.
variable mynextmap {} ; # Dictionary mapping from the revisions
# to their successors. Cache to avoid
# loading this from the state more than
# once.
variable mypos {} ; # Commit position of the changeset, if
@@ -391,10 +427,35 @@
# Consider moving this to the integrity module.
if {$rid == $child} {
trouble internal "Revision $rid depends on itself."
}
lappend dependencies($rid) $child
+ }
+ }
+
+ proc PullPredecessorRevisions {dv revisions} {
+ upvar 1 $dv dependencies
+ set theset ('[join $revisions {','}]')
+
+ foreach {rid parent} [state run "
+ -- Primary parent, can be in different LOD for first in a branch
+ SELECT R.rid, R.parent
+ FROM revision R
+ WHERE R.rid IN $theset
+ AND R.parent IS NOT NULL
+ UNION
+ -- Transition trunk to NTDB
+ SELECT R.rid, R.dbparent
+ FROM revision R
+ WHERE R.rid IN $theset
+ AND R.dbparent IS NOT NULL
+ "] {
+ # Consider moving this to the integrity module.
+ if {$rid == $parent} {
+ trouble internal "Revision $rid depends on itself."
+ }
+ lappend dependencies($rid) $parent
}
}
proc InitializeBreakState {revisions} {
upvar 1 pos pos cross cross range range depc depc delta delta \
@@ -608,12 +669,13 @@
typevariable mychangesets {} ; # List of all known changesets.
typevariable myrevmap -array {} ; # Map from revisions to their changeset.
typevariable myidmap -array {} ; # Map from changeset id to changeset.
typevariable mybranchcode {} ; # Local copy of project::sym/mybranch.
- typemethod all {} { return $mychangesets }
- typemethod of {id} { return $myidmap($id) }
+ typemethod all {} { return $mychangesets }
+ typemethod of {id} { return $myidmap($id) }
+ typemethod ofrev {id} { return $myrevmap($id) }
typeconstructor {
set mybranchcode [project::sym branch]
return
}