initial commitHEADmaster

1 files changed, 433 insertions, 0 deletions

diff --git a/tools/cvs2fossil/lib/c2f_pbreakacycle.tcl b/tools/cvs2fossil/lib/c2f_pbreakacycle.tcl
new file mode 100644
index 0000000..59841c1
--- /dev/null
+++ b/tools/cvs2fossil/lib/c2f_pbreakacycle.tcl
@@ -0,0 +1,433 @@
+## -*- tcl -*-
+# # ## ### ##### ######## ############# #####################
+## Copyright (c) 2007 Andreas Kupries.
+#
+# This software is licensed as described in the file LICENSE, which
+# you should have received as part of this distribution.
+#
+# This software consists of voluntary contributions made by many
+# individuals.  For exact contribution history, see the revision
+# history and logs, available at http://fossil-scm.hwaci.com/fossil
+# # ## ### ##### ######## ############# #####################
+
+## Pass X. This is the final pass for breaking changeset dependency
+## cycles. The previous breaker passes (7 and 9) broke cycles covering
+## revision and symbol changesets, respectively. This pass now breaks
+## any remaining cycles, each of which has to contain at least one
+## revision and at least one symbol changeset.
+
+# # ## ### ##### ######## ############# #####################
+## Requirements
+
+package require Tcl 8.4                                   ; # Required runtime.
+package require snit                                      ; # OO system.
+package require struct::list                              ; # Higher order list operations.
+package require struct::set                               ; # Set operations.
+package require vc::tools::misc                           ; # Min, max.
+package require vc::tools::log                            ; # User feedback.
+package require vc::tools::trouble                        ; # Error reporting.
+package require vc::fossil::import::cvs::repository       ; # Repository management.
+package require vc::fossil::import::cvs::cyclebreaker     ; # Breaking dependency cycles.
+package require vc::fossil::import::cvs::state            ; # State storage.
+package require vc::fossil::import::cvs::integrity        ; # State integrity checks.
+package require vc::fossil::import::cvs::project::rev     ; # Project level changesets
+
+# # ## ### ##### ######## ############# #####################
+## Register the pass with the management
+
+vc::fossil::import::cvs::pass define \
+    BreakAllCsetCycles \
+    {Break Remaining ChangeSet Dependency Cycles} \
+    ::vc::fossil::import::cvs::pass::breakacycle
+
+# # ## ### ##### ######## ############# #####################
+##
+
+snit::type ::vc::fossil::import::cvs::pass::breakacycle {
+    # # ## ### ##### ######## #############
+    ## Public API
+
+    typemethod setup {} {
+	# Define the names and structure of the persistent state of
+	# this pass.
+
+	state use revision
+	state use tag
+	state use branch
+	state use symbol
+	state use changeset
+	state use csitem
+	state use cssuccessor
+	return
+    }
+
+    typemethod load {} {
+	# Pass manager interface. Executed to load data computed by
+	# this pass into memory when this pass is skipped instead of
+	# executed.
+	return
+    }
+
+    typemethod run {} {
+	# Pass manager interface. Executed to perform the
+	# functionality of the pass.
+
+	set len [string length [project::rev num]]
+	set myatfmt %${len}s
+	incr len 12
+	set mycsfmt %${len}s
+
+	cyclebreaker precmd   [myproc BreakBackward]
+	cyclebreaker savecmd  [myproc KeepOrder]
+
+	state transaction {
+	    LoadCommitOrder
+	    cyclebreaker run break-all [myproc Changesets]
+	}
+
+	repository printcsetstatistics
+	integrity changesets
+	return
+    }
+
+    typemethod discard {} {
+	# Pass manager interface. Executed for all passes after the
+	# run passes, to remove all data of this pass from the state,
+	# as being out of date.
+	return
+    }
+
+    # # ## ### ##### ######## #############
+    ## Internal methods
+
+    proc Changesets {} {
+	log write 2 breakrcycle {Selecting all changesets}
+	return [project::rev all]
+    }
+
+    proc LoadCommitOrder {} {
+	::variable mycset
+	::variable myrevisionchangesets
+
+	log write 2 breakacycle {Loading revision commit order}
+
+	set n 0
+	state transaction {
+	    state foreachrow {
+		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
+    }
+
+    # # ## ### ##### ######## #############
+
+    proc BreakBackward {graph} {
+	# We go over all branch changesets, i.e. the changesets
+	# created by the symbols which are translated as branches, and
+	# break any which are 'backward', which means that they have
+	# at least one incoming revision changeset which is committed
+	# after at least one of the outgoing revision changesets, per
+	# the order computed in pass 6. In "cvs2svn" this is called
+	# "retrograde".
+
+	set n 0
+	set max [llength [$graph nodes]]
+	foreach cset [$graph nodes] {
+	    log progress 2 breakacycle $n $max ; incr n
+	    if {![$cset isbranch]} continue
+	    CheckAndBreakBackward $graph $cset
+	}
+	return
+    }
+
+    proc CheckAndBreakBackward {graph cset} {
+	while {[IsBackward $graph $cset]} {
+	    # Knowing that the branch changeset is backward we now
+	    # look at the individual branches 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 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.  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] 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 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 {
+		![IsBackward $graph $normal]
+	    } {The normal fragment is unexpectedly backward}
+
+	    set cset $backward
+	}
+	return
+    }
+
+    proc IsBackward {dg cset} {
+	# A branch is "backward" if it has at least one incoming
+	# revision changeset which is committed after at least one of
+	# the outgoing revision changesets, per the order computed by
+	# pass 6.
+
+	# Rephrased, the maximal commit position found among the
+	# incoming revision changesets is larger than the minimal
+	# commit position found among the outgoing revision
+	# changesets. Assuming that we have both incoming and outgoing
+	# revision changesets for the branch.
+
+	# The helper "Positions" computes the set of commit positions
+	# for a set of changesets, which can be a mix of revision and
+	# symbol changesets.
+
+	set predecessors [Positions [$dg nodes -in  $cset]]
+	set successors   [Positions [$dg nodes -out $cset]]
+
+	return [expr {
+		      [llength $predecessors] &&
+		      [llength $successors]   &&
+		      ([max $predecessors] >= [min $successors])
+		  }]
+    }
+
+    proc Positions {changesets} {
+	# To compute the set of commit positions from the set of
+	# changesets we first map each changeset to its position (*)
+	# and then filter out the invalid responses (the empty string)
+	# returned by the symbol changesets.
+	#
+	# (*) This data was loaded into memory earlir in the pass, by
+	#     LoadCommitOrder.
+
+	return [struct::list filter [struct::list map $changesets \
+					 [myproc ToPosition]] \
+		    [myproc ValidPosition]]
+    }
+
+    proc ToPosition    {cset} { $cset pos }
+    proc ValidPosition {pos}  { expr {$pos ne ""} }
+
+    proc ComputeLimits {cset lv bv} {
+	upvar 1 $lv thelimits $bv border
+
+	# 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) {}
+	}
+
+	# 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] {
+	    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.
+
+	# 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 SplitItems {limits border nv bv} {
+	upvar 1 $nv normalitems $bv backwarditems
+
+	set normalitems   {}
+	set backwarditems {}
+
+	foreach {item maxp} $limits {
+	    if {$maxp >= $border} {
+		lappend backwarditems $item
+	    } else {
+		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
+	::variable mycsfmt
+
+	set cid [$cset id]
+
+	log write 8 breakacycle "Changeset @ [format $myatfmt $at]: [format $mycsfmt [$cset str]] <<[FormatTR $graph $cset]>>"
+
+	# We see here a mixture of symbol and revision changesets.
+	# The symbol changesets are ignored as irrelevant.
+
+	if {[$cset pos] eq ""} return
+
+	# For the revision changesets we are sure that they are
+	# consumed in the same order as generated by pass 7
+	# (RevTopologicalSort). Per the code in cvs2svn.
+
+	# This works if and only if none of the symbol changesets are
+	# "backwards", hence our breaking of the backward changesets
+	# first, in the pre-hook.
+
+	# Note that tag changesets cannot be backward as they don't
+	# have successors at all.
+
+	# An interesting thing IMHO, is that after breaking the
+	# backward symbol changesets we should not have any circles
+	# any longer. Each circle which would still be present has to
+	# involve a backward symbol, and we split them all, so there
+	# can't be a circle..
+
+	# Proof:
+	# Let us assume we that have a circle
+	# 	C: R1 -> ... -> Rx -> S -> Ry -> ... -> Rn -> R1
+	# Let us further assume that the symbol changeset S in that
+	# circle is not backward. That means ORD(Rx) < ORD(Ry).  The
+	# earlier topological sorting without symbols now forces this
+	# relationship through to be ORD(Rx) < ORD(R1) < ORD(Rx).  We
+	# have reached an impossibility, a paradox. Our initial
+	# assumption of S not being backward cannot hold.
+	#
+	# Alternate, direct, reasoning: Without S the chain of
+	# dependencies is Ry -> .. -> R1 -> .. -> Rx, therefore
+	# ORD(Ry) < ORD(Rx) holds, and this means S is backward.
+
+	struct::set exclude myrevisionchangesets $cset
+
+	::variable mylastpos
+	set new [$cset pos]
+
+	if {$new != ($mylastpos + 1)} {
+	    if {$mylastpos < 0} {
+		set old "<NONE>"
+	    } else {
+		::variable mycset
+		set old [$mycset($mylastpos) str]@$mylastpos
+	    }
+
+	    #integrity assert 0 {Ordering of revision changesets violated, [$cset str]@$new is not immediately after $old}
+	    log write 2 breakacycle {Ordering of revision changesets violated, [$cset str]@$new is not immediately after $old}
+	}
+
+	set mylastpos $new
+	return
+    }
+
+    proc FormatTR {graph cset} {
+	return [join [struct::list map [$graph node set $cset timerange] {clock format}] { -- }]
+    }
+
+    typevariable mylastpos            -1 ; # Position of last revision changeset saved.
+    typevariable myrevisionchangesets {} ; # Set of revision changesets
+
+    typevariable myatfmt ; # Format for log output to gain better alignment of the various columns.
+    typevariable mycsfmt ; # Ditto for the changesets.
+
+    # # ## ### ##### ######## #############
+
+    typevariable mycset -array {} ; # Map from commit positions to the
+				    # changeset (object ref) at that
+				    # position.
+
+    # # ## ### ##### ######## #############
+    ## Configuration
+
+    pragma -hasinstances   no ; # singleton
+    pragma -hastypeinfo    no ; # no introspection
+    pragma -hastypedestroy no ; # immortal
+
+    # # ## ### ##### ######## #############
+}
+
+namespace eval ::vc::fossil::import::cvs::pass {
+    namespace export breakacycle
+    namespace eval breakacycle {
+	namespace import ::vc::fossil::import::cvs::cyclebreaker
+	namespace import ::vc::fossil::import::cvs::repository
+	namespace import ::vc::fossil::import::cvs::state
+	namespace import ::vc::fossil::import::cvs::integrity
+	namespace eval project {
+	    namespace import ::vc::fossil::import::cvs::project::rev
+	}
+	namespace import ::vc::tools::misc::*
+	namespace import ::vc::tools::trouble
+	namespace import ::vc::tools::log
+	log register breakacycle
+    }
+}
+
+# # ## ### ##### ######## ############# #####################
+## Ready
+
+package provide vc::fossil::import::cvs::pass::breakacycle 1.0
+return