Diff
Not logged in

Differences From:

File tools/cvs2fossil/lib/c2f_prev.tcl part of check-in [c784751485] - Bugfix. Typo. by aku on 2007-12-02 06:49:19. [view]

To:

File tools/cvs2fossil/lib/c2f_prev.tcl part of check-in [00bf8c198e] - 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.

by aku on 2007-12-02 20:04:40. [view]

@@ -52,8 +52,9 @@
 
 	# 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
@@ -88,13 +89,40 @@
 
     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 {} {
@@ -173,9 +201,9 @@
 	# 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).
 
@@ -357,10 +385,11 @@
 	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]
@@ -368,39 +397,42 @@
 	    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
@@ -418,9 +450,9 @@
 	# 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 {
@@ -428,16 +460,20 @@
 
 	    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} {
@@ -561,8 +597,9 @@
     }
 
     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
     }
 
@@ -779,20 +816,28 @@
     }
 
     # # ## ### ##### ######## #############
 
-    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
 
@@ -926,8 +971,44 @@
 	}
 	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 {','}]')
@@ -987,17 +1068,17 @@
 	}
 	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]
 	}
@@ -1161,8 +1242,14 @@
 	# 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
@@ -1246,8 +1333,25 @@
             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
@@ -1260,9 +1364,9 @@
 	    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
@@ -1269,9 +1373,9 @@
 	    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
@@ -1278,9 +1382,9 @@
 	    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
     }