SHA1 Hash:	4f1b60dd168e5629be8c174d521086a3ff95c3d8
Date:	2007-11-22 03:47:38
User:	aku
Comment:	Continued work on pass 8. Renamed 'retrograde' to 'Backward Branch', should be easier to understand, and completed the predicate testing if a branch changeset is backward or not.
Timelines:	ancestors | descendants | both | trunk
Other Links:	files | ZIP archive | manifest

• branch=trunk inherited from [a28c83647d]
• sym-trunk inherited from [a28c83647d]

Modified tools/cvs2fossil/lib/c2f_pbreakacycle.tcl from [a4b4de4900] to [2f61c9c570].

@@ -62,11 +62,11 @@
 
     typemethod run {} {
 	# Pass manager interface. Executed to perform the
 	# functionality of the pass.
 
-	cyclebreaker precmd   [myproc BreakRetrogradeBranches]
+	cyclebreaker precmd   [myproc BreakBackwardBranches]
 	cyclebreaker savecmd  [myproc SaveOrder]
 	cyclebreaker breakcmd [myproc BreakCycle]
 
 	state transaction {
 	    LoadCommitOrder
@@ -106,16 +106,18 @@
 	return
     }
 
     # # ## ### ##### ######## #############
 
-    proc BreakRetrogradeBranches {graph} {
+    proc BreakBackwardBranches {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 'retrograde'. Meaning that they have
-	# incoming revision changesets which are committed after some
-	# outgoing revision changeset.
+	# 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".
 
 	# NOTE: We might be able to use our knowledge that we are
 	# 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
@@ -124,27 +126,66 @@
 	# NOTE 2: Might we even be able to select the retrograde
 	# changesets too ?
 
 	foreach cset [$graph nodes] {
 	    if {![$cset isbranch]} continue
-	    CheckAndBreakRetrograde $graph $cset
+	    CheckAndBreakBackwardBranch $graph $cset
 	}
 	return
     }
 
-    proc CheckAndBreakRetrograde {graph cset} {
-	while {[IsRetrograde $graph $cset]} {
-	    log write 5 breakacycle "Breaking retrograde changeset <[$cset id]>"
+    proc CheckAndBreakBackwardBranch {graph cset} {
+	while {[IsABackwardBranch $graph $cset]} {
+	    log write 5 breakacycle "Breaking backward branch changeset <[$cset id]>"
 
 	    break
 	}
 	return
     }
 
-    proc IsRetrograde {dg cset} {
-	return 0
+    proc IsABackwardBranch {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 in
+	# 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.
+
+	# 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 SaveOrder {cset pos} {
     }