Check-in [00bf8c198e]
Not logged in
HomeFilesLeavesTimelineBranchesTagsTicketsWikiLogin
Overview

SHA1 Hash:00bf8c198ee6db85e9ec3868df1b6649695ae0e3
Date: 2007-12-02 20:04:40
User: aku
Comment:The performance was still not satisfying, even with faster recomputing of successors. Doing it multiple times (Building the graph in each breaker and sort passes) eats time. Caching in memory blows the memory. Chosen solution: Cache this information in the database.

Created a new pass 'CsetDeps' which is run between 'InitCsets' and 'BreakRevCsetCycles' (i.e. changeset creation and first breaker pass). It computes the changeset dependencies from the file-level dependencies once and saves the result in the state, in the new table 'cssuccessor'. Now the breaker and sort passes can get the information quickly, with virtually no effort. The dependencies are recomputed incrementally when a changeset is split by one of the breaker passes, for its fragments and its predecessors.

The loop check is now trivial, and integrated into the successor computation, with the heavy lifting for the detailed analysis and reporting moved down into the type-dependent SQL queries. The relevant new method is 'loops'. Now that the loop check is incremental the pass based checks have been removed from the integrity module, and the option '--loopcheck' has been eliminated. For paranoia the graph setup and modification code got its loop check reinstated as an assert, redusing the changeset report code.

Renumbered the breaker and sort passes. A number of places, like graph setup and traversal, loading of changesets, etc. got feedback indicators to show their progress.

The selection of revision and symbol changesets for the associated breaker passes was a bit on the slow side. We now keep changeset lists sorted by type (during loading or general construction) and access them directly.

Timelines: ancestors | descendants | both | trunk
Other Links: files | ZIP archive | manifest

Tags And Properties
Changes
[hide diffs]

Modified tools/cvs2fossil/lib/c2f_cyclebreaker.tcl from [6e157515ed] to [775fd1f9e5]. 

@@ -102,12 +102,16 @@
 	#    and work on breaking it.
 
 	log write 3 cyclebreaker {Traverse changesets}
 
 	InitializeCandidates $dg
+
+	set k   0
+	set max [llength [$dg nodes]]
 	while {1} {
 	    while {[WithoutPredecessor $dg n]} {
+		log progress 2 cyclebreaker $k $max ; incr k
 		MarkWatch $dg
 		ProcessedHook $dg $n $myat
 		$dg node delete $n
 		incr myat
 		ShowPendingNodes
@@ -205,14 +209,13 @@
 	    foreach succ [$cset successors] {
 		# Changesets may have dependencies outside of the
 		# chosen set. These are ignored
 		if {![$dg node exists $succ]} continue
 		$dg arc insert $cset $succ
-		if {$succ eq $cset} {
-		    $cset loopcheck
-		    trouble internal "[$cset str] depends on itself"
-		}
+		integrity assert {
+		    $succ ne $cset
+		} {[$cset reportloop 0]Changeset loop was not detected during creation}
 	    }
 	    incr n
 	}
 
 	if {$log} {
@@ -429,14 +432,13 @@
 	    foreach succ [$cset successors] {
 		# The new changesets may have dependencies outside of
 		# the chosen set. These are ignored
 		if {![$dg node exists $succ]} continue
 		$dg arc insert $cset $succ
-		if {$succ eq $cset} {
-		    $cset loopcheck
-		    trouble internal "[$cset str] depends on itself"
-		}
+		integrity assert {
+		    $succ ne $cset
+		} {[$cset reportloop 0]Changeset loop was not detected during creation}
 	    }
 	}
 	foreach cset $pre {
 	    foreach succ [$cset successors] {
 		# Note that the arc may already exist in the graph. If
@@ -555,12 +557,12 @@
 }
 
 namespace eval ::vc::fossil::import::cvs {
     namespace export cyclebreaker
     namespace eval cyclebreaker {
-	namespace eval project {
-	    namespace import ::vc::fossil::import::cvs::integrity
+	namespace import ::vc::fossil::import::cvs::integrity
+	namespace eval project {
 	    namespace import ::vc::fossil::import::cvs::project::rev
 	    namespace import ::vc::fossil::import::cvs::project::revlink
 	}
 	namespace import ::vc::tools::misc::*
 	namespace import ::vc::tools::log

Modified tools/cvs2fossil/lib/c2f_integrity.tcl from [3a6b91462b] to [3028615e2a]. 

@@ -51,25 +51,17 @@
 	set n 0
 	AllButMeta
 	return
     }
 
-    typemethod changesets {csets} {
+    typemethod changesets {} {
 	log write 4 integrity {Check database consistency}
 
 	set n 0
 	RevisionChangesets
 	TagChangesets
 	BranchChangesets
-	trouble abort? ; # Avoid expensive check if anything found before
-
-	LoopCheck $csets
-	return
-    }
-
-    typemethod loopcheckon {} {
-	set myloopcheck 1
 	return
     }
 
     # # ## ### ##### ######## #############
     ## Internal methods
@@ -769,24 +761,10 @@
 		AND    T.tid = C.type
 	    }
 	return
     }
 
-    proc LoopCheck {csets} {
-	::variable myloopcheck
-	if {!$myloopcheck} return
-
-	log write 4 integrity {Checking changesets for self-references}
-
-	foreach cset $csets {
-	    if {[$cset loopcheck]} {
-		trouble fatal "[$cset str] depends on itself"
-	    }
-	}
-	return
-    }
-
     proc ___UnusedChangesetChecks___ {} {
 	# This code performs a number of paranoid checks of the
 	# database, searching for inconsistent changeset/revision
 	# information.
 
@@ -902,17 +880,10 @@
 	    trouble fatal "$fname <$revnr> [string map [list @ $b] $label]"
 	}
 	log write 5 integrity {\[[format %02d [incr n]]\] [expr {$ok ? "Ok    " : "Failed"}] ... $header}
 	return
     }
-
-    # # ## ### ##### ######## #############
-
-    typevariable myloopcheck 0 ; # Boolean flag. Controls whether
-				 # 'integrity changesets' looks for
-				 # changesets with loops or not.
-				 # Default is to not look for them.
 
     # # ## ### ##### ######## #############
     ## Configuration
 
     pragma -hasinstances   no ; # singleton

Modified tools/cvs2fossil/lib/c2f_option.tcl from [b6d7645a3c] to [5835c5aa1e]. 

@@ -47,11 +47,10 @@
     # -q, --quiet
     # --state (conversion status, ala config.cache)
     # --trunk-only
     # --exclude, --force-tag, --force-branch
     # --batch
-    # --loopcheck
 
     # -o, --output
     # --dry-run
     # --symbol-transform RE:XX
 
@@ -82,11 +81,10 @@
 		--force-tag                 { project::sym forcetag    [Value arguments] }
 		--force-branch              { project::sym forcebranch [Value arguments] }
 		--batch                     { log noprogress }
 		--dots                      { cyclebreaker dotsto [Value arguments] }
 		--watch                     { cyclebreaker watch  [Value arguments] }
-		--loopcheck                 { integrity loopcheckon }
 		default {
 		    Usage $badoption$option\n$gethelp
 		}
 	    }
 	}
@@ -149,12 +147,10 @@
 	trouble info ""
 	trouble info "    --dots PATH                Write the changeset graphs before, after,"
 	trouble info "                               and during breaking the of cycles to the"
 	trouble info "                               direcotry PATH, using GraphViz's dot format"
 	trouble info ""
-	trouble info "    --loopcheck                Activate the expensive search for change-"
-	trouble info "                               with loops, i.e. depending on themselves."
 
 	# --project, --cache
 	# ...
 	return
     }

Modified tools/cvs2fossil/lib/c2f_patopsort.tcl from [271b9b7ee3] to [bd713af4f1]. 

@@ -8,11 +8,11 @@
 # 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 pass goes over all changesets and sorts them
+## Pass XI. This pass goes over all changesets and sorts them
 ## topologically. It assumes that there are no cycles which could
 ## impede it, any remaining having been broken by the previous two
 ## passes, and aborts if that condition doesn't hold.
 
 # # ## ### ##### ######## ############# #####################

Modified tools/cvs2fossil/lib/c2f_pbreakacycle.tcl from [f65b1a9322] to [9244bb5c27]. 

@@ -8,12 +8,12 @@
 # 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 IX. This is the final pass for breaking changeset dependency
-## cycles. The previous breaker passes (6 and 8) broke cycles covering
+## 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.
 
 # # ## ### ##### ######## ############# #####################
@@ -80,11 +80,11 @@
 	    LoadCommitOrder
 	    cyclebreaker run break-all [myproc Changesets]
 	}
 
 	repository printcsetstatistics
-	integrity changesets [project::rev all]
+	integrity changesets
 	return
     }
 
     typemethod discard {} {
 	# Pass manager interface. Executed for all passes after the
@@ -94,11 +94,14 @@
     }
 
     # # ## ### ##### ######## #############
     ## Internal methods
 
-    proc Changesets {} { project::rev all }
+    proc Changesets {} {
+	log write 2 breakrcycle {Selecting all changesets}
+	return [project::rev all]
+    }
 
     proc LoadCommitOrder {} {
 	::variable mycset
 	::variable myrevisionchangesets

Modified tools/cvs2fossil/lib/c2f_pbreakrcycle.tcl from [0b1951c1de] to [3c073e957a]. 

@@ -8,13 +8,13 @@
 # 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 VI. This pass goes over the set of revision based changesets
+## Pass VII. This pass goes over the set of revision based changesets
 ## and breaks all dependency cycles they may be in. We need a
-## dependency tree. Identical to pass VII, except for the selection of
+## dependency tree. Identical to pass IX, except for the selection of
 ## the changesets.
 
 # # ## ### ##### ######## ############# #####################
 ## Requirements
 
@@ -69,11 +69,11 @@
 	state transaction {
 	    cyclebreaker run break-rev [myproc Changesets]
 	}
 
 	repository printcsetstatistics
-	integrity changesets [project::rev all]
+	integrity changesets
 	return
     }
 
     typemethod discard {} {
 	# Pass manager interface. Executed for all passes after the
@@ -84,14 +84,13 @@
 
     # # ## ### ##### ######## #############
     ## Internal methods
 
     proc Changesets {} {
-	return [struct::list filter [project::rev all] [myproc IsByRevision]]
-    }
-
-    proc IsByRevision {cset} { $cset byrevision }
+	log write 2 breakrcycle {Selecting the revision changesets}
+	return [project::rev rev]
+    }
 
     # # ## ### ##### ######## #############
     ## Configuration
 
     pragma -hasinstances   no ; # singleton

Modified tools/cvs2fossil/lib/c2f_pbreakscycle.tcl from [427766d2fb] to [24924cb693]. 

@@ -8,21 +8,22 @@
 # 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 VIII. This pass goes over the set of symbol based changesets
-## and breaks all dependency cycles they may be in. We need a
-## dependency tree. Identical to pass VI, except for the selection of
-## the changesets.
+## Pass IX. This pass goes over the set of symbol based changesets and
+## breaks all dependency cycles they may be in. We need a dependency
+## tree. Identical to pass VII, except for the selection of the
+## changesets.
 
 # # ## ### ##### ######## ############# #####################
 ## Requirements
 
 package require Tcl 8.4                                   ; # Required runtime.
 package require snit                                      ; # OO system.
 package require struct::list                              ; # Higher order list operations.
+package require vc::tools::log                            ; # User feedback.
 package require vc::fossil::import::cvs::cyclebreaker     ; # Breaking dependency cycles.
 package require vc::fossil::import::cvs::repository       ; # Repository management.
 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
@@ -68,11 +69,11 @@
 	state transaction {
 	    cyclebreaker run break-sym [myproc Changesets]
 	}
 
 	repository printcsetstatistics
-	integrity changesets [project::rev all]
+	integrity changesets
 	return
     }
 
     typemethod discard {} {
 	# Pass manager interface. Executed for all passes after the
@@ -83,14 +84,13 @@
 
     # # ## ### ##### ######## #############
     ## Internal methods
 
     proc Changesets {} {
-	return [struct::list filter [project::rev all] [myproc IsBySymbol]]
-    }
-
-    proc IsBySymbol {cset} { $cset bysymbol }
+	log write 2 breakscycle {Selecting the symbol changesets}
+	return [project::rev sym]
+    }
 
     # # ## ### ##### ######## #############
     ## Configuration
 
     pragma -hasinstances   no ; # singleton
@@ -108,13 +108,15 @@
 	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::log
+	log register breakscycle
     }
 }
 
 # # ## ### ##### ######## ############# #####################
 ## Ready
 
 package provide vc::fossil::import::cvs::pass::breakscycle 1.0
 return

Modified tools/cvs2fossil/lib/c2f_pinitcsets.tcl from [f56c12b551] to [ced4d957b1]. 

@@ -22,11 +22,10 @@
 package require vc::tools::misc                       ; # Text formatting.
 package require vc::tools::log                        ; # User feedback.
 package require vc::fossil::import::cvs::repository   ; # Repository management.
 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::sym ; # Project level symbols
 package require vc::fossil::import::cvs::project::rev ; # Project level changesets
 
 # # ## ### ##### ######## ############# #####################
 ## Register the pass with the management
 
@@ -113,22 +112,27 @@
 
 	# Need the types first, the constructor in the loop below uses
 	# them to assert the correctness of type names.
 	project::rev getcstypes
 
+	# TODO: Move to project::rev
+	set n 0
+	log write 2 initcsets {Loading the changesets}
 	foreach {id pid cstype srcid} [state run {
 	    SELECT C.cid, C.pid, CS.name, C.src
 	    FROM   changeset C, cstype CS
 	    WHERE  C.type = CS.tid
 	    ORDER BY C.cid
 	}] {
+	    log progress 2 initcsets $n {}
 	    set r [project::rev %AUTO% [repository projectof $pid] $cstype $srcid [state run {
 		SELECT C.iid
 		FROM   csitem C
 		WHERE  C.cid = $id
 		ORDER BY C.pos
 	    }] $id]
+	    incr n
 	}
 
 	project::rev loadcounter
 	return
     }
@@ -143,11 +147,11 @@
 	    CreateSymbolChangesets    ; # Create csets for tags and branches.
 	    PersistTheChangesets
 	}
 
 	repository printcsetstatistics
-	integrity changesets [project::rev all]
+	integrity changesets
 	return
     }
 
     typemethod discard {} {
 	# Pass manager interface. Executed for all passes after the

Modified tools/cvs2fossil/lib/c2f_prev.tcl from [c123dc0a3e] to [bf483d028a]. 

@@ -51,10 +51,11 @@
 	set mypos       {} ; # Commit location is not known yet.
 
 	# Keep track of the generated changesets and of the inverse
 	# mapping from items to them.
 	lappend mychangesets   $self
+	lappend mytchangesets($cstype) $self
 	set     myidmap($myid) $self
 	foreach iid $items {
 	    set key [list $cstype $iid]
 	    set myitemmap($key) $self
 	    lappend mytitems $key
@@ -87,15 +88,42 @@
     delegate method istag      to mytypeobj
 
     method setpos {p} { set mypos $p ; return }
     method pos    {}  { return $mypos }
 
+    method determinesuccessors {} {
+	# Pass 6 operation. Compute project-level dependencies from
+	# the file-level data and save it back to the state. This may
+	# be called during the cycle breaker passes as well, to adjust
+	# the successor information of changesets which are the
+	# predecessors of dropped changesets. For them we have to
+	# remove their existing information first before inserting the
+	# new data.
+	state run {
+	    DELETE FROM cssuccessor WHERE cid = $myid;
+	}
+	set loop 0
+	foreach nid [$mytypeobj cs_successors $myitems] {
+	    state run {
+		INSERT INTO cssuccessor (cid,  nid)
+		VALUES                  ($myid,$nid)
+	    }
+	    if {$nid == $myid} { set loop 1 }
+	}
+	# Report after the complete structure has been saved.
+	if {$loop} { $self reportloop }
+	return
+    }
+
     # result = list (changeset)
     method successors {} {
-	return [struct::list map \
-		    [$mytypeobj cs_successors $myitems] \
-		    [mytypemethod of]]
+	# Use the data saved by pass 6.
+	return [struct::list map [state run {
+	    SELECT S.nid
+	    FROM   cssuccessor S
+	    WHERE  S.cid = $myid
+	}] [mytypemethod of]]
     }
 
     # result = dict (item -> list (changeset))
     method successormap {} {
 	# NOTE / FUTURE: Definitive bottleneck (can be millions of pairs).
@@ -172,11 +200,11 @@
 	# one. The previous algorithm, adapted from cvs2svn, computed
 	# a lot of state which was thrown away and then computed again
 	# for each of the fragments. It should be easier to update and
 	# reuse that state.
 
-	# The code checks only sucessor dependencies, as this
+	# The code checks only successor dependencies, as this
 	# automatically covers the predecessor dependencies as well (A
 	# successor dependency a -> b is also a predecessor dependency
 	# b -> a).
 
 	# Array of dependencies (parent -> child). This is pulled from
@@ -356,52 +384,56 @@
     method drop {} {
 	log write 8 csets {Dropping $self = [$self str]}
 
 	state transaction {
 	    state run {
-		DELETE FROM changeset WHERE cid = $myid;
-		DELETE FROM csitem    WHERE cid = $myid;
+		DELETE FROM changeset   WHERE cid = $myid;
+		DELETE FROM csitem      WHERE cid = $myid;
+		DELETE FROM cssuccessor WHERE cid = $myid;
 	    }
 	}
 	foreach iid $myitems {
 	    set key [list $mytype $iid]
 	    unset myitemmap($key)
 	    log write 8 csets {MAP- item <$key> $self = [$self str]}
 	}
 	set pos          [lsearch -exact $mychangesets $self]
 	set mychangesets [lreplace $mychangesets $pos $pos]
-	return
-    }
-
-    method loopcheck {} {
-	log write 7 csets {Checking [$self str] for loops /[llength $myitems]}
-
-	if {![struct::set contains [$self successors] $self]} {
-	    return 0
-	}
-	if {[log verbosity?] < 8} { return 1 }
-
-	# Print the detailed successor structure of the self-
-	# referential changeset, if the verbosity of the log is dialed
-	# high enough.
-
-	log write 8 csets [set hdr {Self-referential changeset [$self str] __________________}]
-	array set nmap [$self nextmap]
-	foreach item [lsort -dict [array names nmap]] {
-	    foreach succitem $nmap($item) {
-		set succcs $myitemmap($succitem)
-		set hint [expr {($succcs eq $self)
-				? "LOOP"
-				: "    "}]
-		set i   "<$item [$type itemstr $item]>"
-		set s   "<$succitem [$type itemstr $succitem]>"
-		set scs [$succcs str]
-		log write 8 csets {$hint * $i --> $s --> cs $scs}
-	    }
-	}
-	log write 8 csets [regsub -all {[^ 	]} $hdr {_}]
-	return 1
+	set pos                    [lsearch -exact $mytchangesets($mytype) $self]
+	set mytchangesets($mytype) [lreplace $mytchangesets($mytype) $pos $pos]
+
+	# Return the list of predecessors so that they can be adjusted.
+	return [struct::list map [state run {
+	    SELECT cid
+	    FROM   cssuccessor
+	    WHERE  nid = $myid
+	}] [mytypemethod of]]
+    }
+
+    method reportloop {{kill 1}} {
+	# We print the items which are producing the loop, and how.
+
+	set hdr "Self-referential changeset [$self str] __________________"
+	set ftr [regsub -all {[^ 	]} $hdr {_}]
+
+	log write 0 csets $hdr
+	foreach {item nextitem} [$mytypeobj loops $myitems] {
+	    # Create tagged items from the id and our type.
+	    set item     [list $mytype  $item]
+	    set nextitem [list $mytype $nextitem]
+	    # Printable labels.
+	    set i  "<[$type itemstr $item]>"
+	    set n  "<[$type itemstr $nextitem]>"
+	    set ncs $myitemmap($nextitem)
+	    # Print
+	    log write 0 csets {* $i --> $n --> cs [$ncs str]}
+	}
+	log write 0 csets $ftr
+
+	if {!$kill} return
+	trouble internal "[$self str] depends on itself"
+	return
     }
 
     typemethod split {cset args} {
 	# As part of the creation of the new changesets specified in
 	# ARGS as sets of items, all subsets of CSET's item set, CSET
@@ -417,28 +449,32 @@
 
 	# All checks pass, actually perform the split.
 
 	struct::list assign [$cset data] project cstype cssrc
 
-	$cset drop
+	set predecessors [$cset drop]
 	$cset destroy
 
 	set newcsets {}
 	foreach fragmentitems $args {
 	    log write 8 csets {MAKE: [lsort $fragmentitems]}
 
 	    set fragment [$type %AUTO% $project $cstype $cssrc \
 			      [Untag $fragmentitems $cstype]]
 	    lappend newcsets $fragment
+
 	    $fragment persist
-
-	    if {[$fragment loopcheck]} {
-		trouble fatal "[$fragment str] depends on itself"
-	    }
-	}
-
-	trouble abort?
+	    $fragment determinesuccessors
+	}
+
+	# The predecessors have to recompute their successors, i.e.
+	# remove the dropped changeset and put one of the fragments
+	# into its place.
+	foreach p $predecessors {
+	    $p determinesuccessors
+	}
+
 	return $newcsets
     }
 
     typemethod itemstr {item} {
 	struct::list assign $item itype iid
@@ -560,10 +596,11 @@
 	return
     }
 
     typemethod loadcounter {} {
 	# Initialize the counter from the state
+	log write 2 initcsets {Loading changeset counter}
 	set mycounter [state one { SELECT MAX(cid) FROM changeset }]
 	return
     }
 
     typemethod num {} { return $mycounter }
@@ -778,22 +815,30 @@
 	return
     }
 
     # # ## ### ##### ######## #############
 
-    typevariable mychangesets     {} ; # List of all known changesets.
-    typevariable myitemmap -array {} ; # Map from items (tagged) to
-				       # the list of changesets
-				       # containing it. Each item can
-				       # be used by only one
-				       # changeset.
+    typevariable mychangesets         {} ; # List of all known
+					   # changesets.
+    typevariable mytchangesets -array {} ; # List of all known
+					   # changesets of a type.
+    typevariable myitemmap     -array {} ; # Map from items (tagged)
+					   # to the list of changesets
+					   # containing it. Each item
+					   # can be used by only one
+					   # changeset.
     typevariable myidmap   -array {} ; # Map from changeset id to
 				       # changeset.
 
     typemethod all    {}    { return $mychangesets }
     typemethod of     {cid} { return $myidmap($cid) }
     typemethod ofitem {iid} { return $myitemmap($iid) }
+
+    typemethod rev    {}    { return $mytchangesets(rev) }
+    typemethod sym    {}    { return [concat \
+					  ${mytchangesets(sym::branch)} \
+					  ${mytchangesets(sym::tag)}] }
 
     # # ## ### ##### ######## #############
     ## Configuration
 
     pragma -hastypeinfo    no  ; # no type introspection
@@ -925,10 +970,46 @@
 	    }
 	}
 	return
     }
 
+    # result = 4-list (itemtype itemid nextitemtype nextitemid ...)
+    typemethod loops {revisions} {
+	# Note: Tags and branches cannot cause the loop. Their id's,
+	# bein of a fundamentally different type than the revisions
+	# coming in cannot be in the set.
+
+	set theset ('[join $revisions {','}]')
+	return [state run [subst -nocommands -nobackslashes {
+	    -- (1) Primary child
+	    SELECT R.rid, R.child
+	    FROM   revision R
+	    WHERE  R.rid   IN $theset     -- Restrict to revisions of interest
+	    AND    R.child IS NOT NULL    -- Has primary child
+	    AND    R.child IN $theset     -- Loop
+	    --
+	    UNION
+	    -- (2) Secondary (branch) children
+	    SELECT R.rid, B.brid
+	    FROM   revision R, revisionbranchchildren B
+	    WHERE  R.rid   IN $theset     -- Restrict to revisions of interest
+	    AND    R.rid = B.rid          -- Select subset of branch children
+	    AND    B.rid   IN $theset     -- Loop
+	    --
+	    UNION
+	    -- (4) Child of trunk root successor of last NTDB on trunk.
+	    SELECT R.rid, RA.child
+	    FROM   revision R, revision RA
+	    WHERE  R.rid    IN $theset     -- Restrict to revisions of interest
+	    AND    R.isdefault             -- Restrict to NTDB
+	    AND    R.dbchild IS NOT NULL   -- and last NTDB belonging to trunk
+	    AND    RA.rid = R.dbchild      -- Go directly to trunk root
+	    AND    RA.child IS NOT NULL    -- Has primary child.
+	    AND    RA.child IN $theset     -- Loop
+	}]]
+    }
+
     # var(dv) = dict (item -> list (item)), item  = list (type id)
     typemethod successors {dv revisions} {
 	upvar 1 $dv dependencies
 	set theset ('[join $revisions {','}]')
 
@@ -986,19 +1067,19 @@
 	    lappend dependencies([list rev $rid]) [list rev $child]
 	}
 	foreach {rid child} [state run "
 	    SELECT R.rid, T.tid
 	    FROM   revision R, tag T
-	    WHERE  R.rid in $theset
+	    WHERE  R.rid IN $theset
 	    AND    T.rev = R.rid
 	"] {
 	    lappend dependencies([list rev $rid]) [list sym::tag $child]
 	}
 	foreach {rid child} [state run "
 	    SELECT R.rid, B.bid
 	    FROM   revision R, branch B
-	    WHERE  R.rid in $theset
+	    WHERE  R.rid IN $theset
 	    AND    B.root = R.rid
 	"] {
 	    lappend dependencies([list rev $rid]) [list sym::branch $child]
 	}
 	return
@@ -1160,10 +1241,16 @@
     typemethod successors {dv tags} {
 	# Tags have no successors.
 	return
     }
 
+    # result = 4-list (itemtype itemid nextitemtype nextitemid ...)
+    typemethod loops {tags} {
+	# Tags have no successors, therefore cannot cause loops
+	return {}
+    }
+
     # var(dv) = dict (item -> list (item)), item  = list (type id)
     typemethod predecessors {dv tags} {
 	upvar 1 $dv dependencies
 	# The predecessors of a tag are all the revisions the tags are
 	# attached to, as well as all the branches or tags which are
@@ -1245,10 +1332,27 @@
 	    WHERE B.bid IN $theset
             AND   R.rid = B.root
 	"]
     }
 
+    # result = 4-list (itemtype itemid nextitemtype nextitemid ...)
+    typemethod loops {branches} {
+	# Note: Revisions and tags cannot cause the loop. Being of a
+	# fundamentally different type they cannot be in the incoming
+	# set of ids.
+
+	set theset ('[join $branches {','}]')
+	return [state run [subst -nocommands -nobackslashes {
+	    SELECT B.bid, BX.bid
+	    FROM   branch B, preferedparent P, branch BX
+	    WHERE  B.bid IN $theset
+	    AND    B.sid = P.pid
+	    AND    BX.sid = P.sid
+	    AND    BX.bid IN $theset
+	}]]
+    }
+
     # var(dv) = dict (item -> list (item)), item  = list (type id)
     typemethod successors {dv branches} {
 	upvar 1 $dv dependencies
 	# The first revision committed on a branch, and all branches
 	# and tags which have it as their prefered parent are the
@@ -1259,29 +1363,29 @@
 	    SELECT B.bid, R.rid
 	    FROM   branch B, revision R
 	    WHERE  B.bid IN $theset
 	    AND    B.first = R.rid
 	"] {
-	    lappend dependencies([list sym::tag $bid]) [list rev $child]
+	    lappend dependencies([list sym::branch $bid]) [list rev $child]
 	}
 	foreach {bid child} [state run "
 	    SELECT B.bid, BX.bid
 	    FROM   branch B, preferedparent P, branch BX
 	    WHERE  B.bid IN $theset
 	    AND    B.sid = P.pid
 	    AND    BX.sid = P.sid
 	"] {
-	    lappend dependencies([list sym::tag $bid]) [list sym::branch $child]
+	    lappend dependencies([list sym::branch $bid]) [list sym::branch $child]
 	}
 	foreach {bid child} [state run "
 	    SELECT B.bid, T.tid
 	    FROM   branch B, preferedparent P, tag T
 	    WHERE  B.bid IN $theset
 	    AND    B.sid = P.pid
 	    AND    T.sid = P.sid
 	"] {
-	    lappend dependencies([list sym::tag $bid]) [list sym::tag $child]
+	    lappend dependencies([list sym::branch $bid]) [list sym::tag $child]
 	}
 	return
     }
 
     # var(dv) = dict (item -> list (item)), item  = list (type id)

Modified tools/cvs2fossil/lib/c2f_prtopsort.tcl from [b280cf33d2] to [108eb140ec]. 

@@ -8,11 +8,11 @@
 # 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 VII. This pass goes over the set of revision based changesets
+## Pass VIII. This pass goes over the set of revision based changesets
 ## and sorts them topologically. It assumes that there are no cycles
 ## which could impede it, any having been broken by the previous pass,
 ## and aborts if that condition doesn't hold.
 
 # # ## ### ##### ######## ############# #####################
@@ -99,14 +99,13 @@
 
     # # ## ### ##### ######## #############
     ## Internal methods
 
     proc Changesets {} {
-	return [struct::list filter [project::rev all] [myproc IsByRevision]]
-    }
-
-    proc IsByRevision {cset} { $cset byrevision }
+	log write 2 breakscycle {Selecting the revision changesets}
+	return [project::rev rev]
+    }
 
     proc SaveOrder {graph at cset} {
 	::variable myatfmt
 	::variable mycsfmt

Modified tools/cvs2fossil/lib/cvs2fossil.tcl from [fe8a4a6dae] to [fb15e077e1]. 

@@ -33,10 +33,11 @@
 #       are not implemented by us. They are irrelevant due to our use
 #       of a relational database proper for the persistent state,
 #       allowing us to sort the data on the fly as we need it.
 
 package require vc::fossil::import::cvs::pass::initcsets   ; # Init'ialize C'hange'Sets
+package require vc::fossil::import::cvs::pass::csetdeps    ; # C'hange'Set Dep'endencies
 package require vc::fossil::import::cvs::pass::breakrcycle ; # Break' R'evision Cycle's
 package require vc::fossil::import::cvs::pass::rtopsort    ; # R'evision Top'ological Sort'
 package require vc::fossil::import::cvs::pass::breakscycle ; # Break' S'ymbol Cycle's
 package require vc::fossil::import::cvs::pass::breakacycle ; # Break' A'll Cycle's
 package require vc::fossil::import::cvs::pass::atopsort    ; # A'll Top'ological Sort'

Modified tools/cvs2fossil/lib/pkgIndex.tcl from [d37efe5d62] to [bba80efcbb]. 

@@ -15,10 +15,11 @@
 package ifneeded vc::fossil::import::cvs::pass::collar      1.0 [list source [file join $dir c2f_pcollar.tcl]]
 package ifneeded vc::fossil::import::cvs::pass::collrev     1.0 [list source [file join $dir c2f_pcollrev.tcl]]
 package ifneeded vc::fossil::import::cvs::pass::collsym     1.0 [list source [file join $dir c2f_pcollsym.tcl]]
 package ifneeded vc::fossil::import::cvs::pass::filtersym   1.0 [list source [file join $dir c2f_pfiltersym.tcl]]
 package ifneeded vc::fossil::import::cvs::pass::initcsets   1.0 [list source [file join $dir c2f_pinitcsets.tcl]]
+package ifneeded vc::fossil::import::cvs::pass::csetdeps    1.0 [list source [file join $dir c2f_pcsetdeps.tcl]]
 package ifneeded vc::fossil::import::cvs::pass::breakrcycle 1.0 [list source [file join $dir c2f_pbreakrcycle.tcl]]
 package ifneeded vc::fossil::import::cvs::pass::rtopsort    1.0 [list source [file join $dir c2f_prtopsort.tcl]]
 package ifneeded vc::fossil::import::cvs::pass::breakscycle 1.0 [list source [file join $dir c2f_pbreakscycle.tcl]]
 package ifneeded vc::fossil::import::cvs::pass::breakacycle 1.0 [list source [file join $dir c2f_pbreakacycle.tcl]]
 package ifneeded vc::fossil::import::cvs::pass::atopsort    1.0 [list source [file join $dir c2f_patopsort.tcl]]

Fossil version [c0211010a1] 2009-12-13 01:31:36