2a01d50430 2007-11-11 aku: ## -*- tcl -*- 2a01d50430 2007-11-11 aku: # # ## ### ##### ######## ############# ##################### 2a01d50430 2007-11-11 aku: ## Copyright (c) 2007 Andreas Kupries. 2a01d50430 2007-11-11 aku: # 2a01d50430 2007-11-11 aku: # This software is licensed as described in the file LICENSE, which 2a01d50430 2007-11-11 aku: # you should have received as part of this distribution. 2a01d50430 2007-11-11 aku: # 2a01d50430 2007-11-11 aku: # This software consists of voluntary contributions made by many 2a01d50430 2007-11-11 aku: # individuals. For exact contribution history, see the revision 2a01d50430 2007-11-11 aku: # history and logs, available at http://fossil-scm.hwaci.com/fossil 2a01d50430 2007-11-11 aku: # # ## ### ##### ######## ############# ##################### 2a01d50430 2007-11-11 aku: 2a01d50430 2007-11-11 aku: ## Pass VI. This pass goes over the set of revision based changesets 2a01d50430 2007-11-11 aku: ## and breaks all dependency cycles they may be in. We need a 2a01d50430 2007-11-11 aku: ## dependency tree. 2a01d50430 2007-11-11 aku: 2a01d50430 2007-11-11 aku: # # ## ### ##### ######## ############# ##################### 2a01d50430 2007-11-11 aku: ## Requirements 2a01d50430 2007-11-11 aku: 94c39d6375 2007-11-14 aku: package require Tcl 8.4 ; # Required runtime. 94c39d6375 2007-11-14 aku: package require snit ; # OO system. 94c39d6375 2007-11-14 aku: package require struct::graph ; # Graph handling. 94c39d6375 2007-11-14 aku: package require struct::list ; # Higher order list operations. 94c39d6375 2007-11-14 aku: package require vc::tools::log ; # User feedback. 94c39d6375 2007-11-14 aku: package require vc::fossil::import::cvs::state ; # State storage. 94c39d6375 2007-11-14 aku: package require vc::fossil::import::cvs::project::rev ; # Project level changesets 94c39d6375 2007-11-14 aku: package require vc::fossil::import::cvs::project::revlink ; # Cycle links. 2a01d50430 2007-11-11 aku: 2a01d50430 2007-11-11 aku: # # ## ### ##### ######## ############# ##################### 2a01d50430 2007-11-11 aku: ## Register the pass with the management 2a01d50430 2007-11-11 aku: 2a01d50430 2007-11-11 aku: vc::fossil::import::cvs::pass define \ 2a01d50430 2007-11-11 aku: BreakRevCsetCycles \ 2a01d50430 2007-11-11 aku: {Break Revision ChangeSet Dependency Cycles} \ 2a01d50430 2007-11-11 aku: ::vc::fossil::import::cvs::pass::breakrcycle 2a01d50430 2007-11-11 aku: 2a01d50430 2007-11-11 aku: # # ## ### ##### ######## ############# ##################### 2a01d50430 2007-11-11 aku: ## 2a01d50430 2007-11-11 aku: 2a01d50430 2007-11-11 aku: snit::type ::vc::fossil::import::cvs::pass::breakrcycle { 2a01d50430 2007-11-11 aku: # # ## ### ##### ######## ############# 2a01d50430 2007-11-11 aku: ## Public API 2a01d50430 2007-11-11 aku: 2a01d50430 2007-11-11 aku: typemethod setup {} { 2a01d50430 2007-11-11 aku: # Define the names and structure of the persistent state of 2a01d50430 2007-11-11 aku: # this pass. 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: state writing csorder { 85bd219d0b 2007-11-13 aku: -- Commit order of changesets based on their dependencies 85bd219d0b 2007-11-13 aku: cid INTEGER NOT NULL REFERENCES changeset, 85bd219d0b 2007-11-13 aku: pos INTEGER NOT NULL, 85bd219d0b 2007-11-13 aku: UNIQUE (cid), 85bd219d0b 2007-11-13 aku: UNIQUE (pos) 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: 2a01d50430 2007-11-11 aku: return 2a01d50430 2007-11-11 aku: } 2a01d50430 2007-11-11 aku: 2a01d50430 2007-11-11 aku: typemethod load {} { 2a01d50430 2007-11-11 aku: # Pass manager interface. Executed to load data computed by 2a01d50430 2007-11-11 aku: # this pass into memory when this pass is skipped instead of 2a01d50430 2007-11-11 aku: # executed. 2a01d50430 2007-11-11 aku: return 2a01d50430 2007-11-11 aku: } 2a01d50430 2007-11-11 aku: 2a01d50430 2007-11-11 aku: typemethod run {} { 2a01d50430 2007-11-11 aku: # Pass manager interface. Executed to perform the 2a01d50430 2007-11-11 aku: # functionality of the pass. 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: state reading revision 94c39d6375 2007-11-14 aku: state reading changeset 94c39d6375 2007-11-14 aku: state reading csrevision 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: # We create a graph of the revision changesets, using the file 85bd219d0b 2007-11-13 aku: # level dependencies to construct a first approximation of 85bd219d0b 2007-11-13 aku: # them at the project level. Then look for cycles in that 85bd219d0b 2007-11-13 aku: # graph and break them. 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: # 1. Create nodes for all relevant changesets and a mapping 85bd219d0b 2007-11-13 aku: # from the revisions to their changesets/nodes. 85bd219d0b 2007-11-13 aku: 94c39d6375 2007-11-14 aku: log write 3 breakrcycle {Creating changeset graph, filling with nodes} 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: set dg [struct::graph dg] 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: state transaction { 85bd219d0b 2007-11-13 aku: foreach cset [project::rev all] { 85bd219d0b 2007-11-13 aku: if {[$cset bysymbol]} continue 85bd219d0b 2007-11-13 aku: dg node insert $cset 85bd219d0b 2007-11-13 aku: dg node set $cset timerange [$cset timerange] 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: # 2. Find for all relevant changeset their revisions and their 85bd219d0b 2007-11-13 aku: # dependencies. Map the latter back to changesets and 85bd219d0b 2007-11-13 aku: # construct the corresponding arcs. 85bd219d0b 2007-11-13 aku: 94c39d6375 2007-11-14 aku: log write 3 breakrcycle {Setting up node dependencies} 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: state transaction { 85bd219d0b 2007-11-13 aku: foreach cset [project::rev all] { 85bd219d0b 2007-11-13 aku: if {[$cset bysymbol]} continue 85bd219d0b 2007-11-13 aku: foreach succ [$cset successors] { 85bd219d0b 2007-11-13 aku: dg arc insert $cset $succ 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: # 3. Lastly we iterate the graph topologically. We mark off 85bd219d0b 2007-11-13 aku: # the nodes which have no predecessors, in order from 85bd219d0b 2007-11-13 aku: # oldest to youngest, saving and removing dependencies. If 85bd219d0b 2007-11-13 aku: # we find no nodes without predecessors we have a cycle, 85bd219d0b 2007-11-13 aku: # and work on breaking it. 85bd219d0b 2007-11-13 aku: 94c39d6375 2007-11-14 aku: log write 3 breakrcycle {Computing changeset order, breaking cycles} 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: InitializeCandidates $dg 85bd219d0b 2007-11-13 aku: state transaction { 85bd219d0b 2007-11-13 aku: while {1} { 85bd219d0b 2007-11-13 aku: while {[WithoutPredecessor $dg n]} { 85bd219d0b 2007-11-13 aku: SaveAndRemove $dg $n 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: if {![llength [dg nodes]]} break 94c39d6375 2007-11-14 aku: BreakCycle $dg [FindCycle $dg] 94c39d6375 2007-11-14 aku: InitializeCandidates $dg 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: 2a01d50430 2007-11-11 aku: return 2a01d50430 2007-11-11 aku: } 2a01d50430 2007-11-11 aku: 2a01d50430 2007-11-11 aku: typemethod discard {} { 2a01d50430 2007-11-11 aku: # Pass manager interface. Executed for all passes after the 2a01d50430 2007-11-11 aku: # run passes, to remove all data of this pass from the state, 2a01d50430 2007-11-11 aku: # as being out of date. 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: state discard csorder 2a01d50430 2007-11-11 aku: return 2a01d50430 2007-11-11 aku: } 2a01d50430 2007-11-11 aku: 2a01d50430 2007-11-11 aku: # # ## ### ##### ######## ############# 2a01d50430 2007-11-11 aku: ## Internal methods 2a01d50430 2007-11-11 aku: 85bd219d0b 2007-11-13 aku: # Instead of searching the whole graph for the degree-0 nodes in 85bd219d0b 2007-11-13 aku: # each iteration we compute the list once to start, and then only 85bd219d0b 2007-11-13 aku: # update it incrementally based on the outgoing neighbours of the 85bd219d0b 2007-11-13 aku: # node chosen for commit. 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: proc InitializeCandidates {dg} { 85bd219d0b 2007-11-13 aku: # bottom = list (list (node, range min, range max)) 85bd219d0b 2007-11-13 aku: ::variable bottom 85bd219d0b 2007-11-13 aku: foreach n [$dg nodes] { 85bd219d0b 2007-11-13 aku: if {[$dg node degree -in $n]} continue 85bd219d0b 2007-11-13 aku: lappend bottom [linsert [$dg node get $n timerange] 0 $n] 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: set bottom [lsort -index 1 -integer [lsort -index 2 -integer $bottom]] 85bd219d0b 2007-11-13 aku: return 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: proc WithoutPredecessor {dg nv} { 85bd219d0b 2007-11-13 aku: ::variable bottom 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: upvar 1 $nv n 85bd219d0b 2007-11-13 aku: if {![llength $bottom]} { return 0 } 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: set n [lindex [lindex $bottom 0] 0] 85bd219d0b 2007-11-13 aku: set bottom [lrange $bottom 1 end] 85bd219d0b 2007-11-13 aku: set changed 0 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: # Update list of nodes without predecessor, based on the 85bd219d0b 2007-11-13 aku: # outgoing neighbours of the chosen node. This should be 85bd219d0b 2007-11-13 aku: # faster than iterating of the whole set of nodes, finding all 85bd219d0b 2007-11-13 aku: # without predecessors, sorting them by time, etc. pp. 85bd219d0b 2007-11-13 aku: foreach out [$dg nodes -out $n] { 85bd219d0b 2007-11-13 aku: if {[$dg node degree -in $out] > 1} continue 85bd219d0b 2007-11-13 aku: # Degree-1 neighbour, will have no predecessors after the 85bd219d0b 2007-11-13 aku: # removal of n. Put on the list. 85bd219d0b 2007-11-13 aku: lappend bottom [linsert [$dg node get $out timerange] 0 $out] 85bd219d0b 2007-11-13 aku: set changed 1 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: if {$changed} { 85bd219d0b 2007-11-13 aku: set bottom [lsort -index 1 -integer [lsort -index 2 -integer $bottom]] 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: # We do not delete the node immediately, to allow the Save 85bd219d0b 2007-11-13 aku: # procedure to save the dependencies as well (encoded in the 85bd219d0b 2007-11-13 aku: # arcs). 85bd219d0b 2007-11-13 aku: return 1 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: proc SaveAndRemove {dg n} { 85bd219d0b 2007-11-13 aku: ::variable at 85bd219d0b 2007-11-13 aku: set cid [$n id] 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: log write 4 breakrcycle "Comitting @ $at: <$cid>" 85bd219d0b 2007-11-13 aku: state run { 85bd219d0b 2007-11-13 aku: INSERT INTO csorder (cid, pos) 85bd219d0b 2007-11-13 aku: VALUES ($cid, $at) 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: # TODO: Write the project level changeset dependencies as well. 85bd219d0b 2007-11-13 aku: incr at 85bd219d0b 2007-11-13 aku: $dg node delete $n 85bd219d0b 2007-11-13 aku: return 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: proc FindCycle {dg} { 85bd219d0b 2007-11-13 aku: # This procedure is run if and only the graph is not empty and 85bd219d0b 2007-11-13 aku: # all nodes have predecessors. This means that each node is 85bd219d0b 2007-11-13 aku: # either part of a cycle or (indirectly) depending on a node 85bd219d0b 2007-11-13 aku: # in a cycle. We can start at an arbitrary node, follow its 85bd219d0b 2007-11-13 aku: # incoming edges to its predecessors until we see a node a 85bd219d0b 2007-11-13 aku: # second time. That node closes the cycle and the beginning is 85bd219d0b 2007-11-13 aku: # its first occurence. Note that we can choose an arbitrary 85bd219d0b 2007-11-13 aku: # predecessor of each node as well, we do not have to search. 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: # We record for each node the index of the first appearance in 85bd219d0b 2007-11-13 aku: # the path, making it easy at the end to cut the cycle from 85bd219d0b 2007-11-13 aku: # it. 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: # Choose arbitrary node to start our search at. 85bd219d0b 2007-11-13 aku: set start [lindex [$dg nodes] 0] 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: # Initialize state, path of seen nodes, and when seen. 85bd219d0b 2007-11-13 aku: set path {} 85bd219d0b 2007-11-13 aku: array set seen {} 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: while {1} { 85bd219d0b 2007-11-13 aku: # Stop searching when we have seen the current node 85bd219d0b 2007-11-13 aku: # already, the circle has been closed. 85bd219d0b 2007-11-13 aku: if {[info exists seen($start)]} break 85bd219d0b 2007-11-13 aku: lappend path $start 94c39d6375 2007-11-14 aku: set seen($start) [expr {[llength $path]-1}] 85bd219d0b 2007-11-13 aku: # Choose arbitrary predecessor 85bd219d0b 2007-11-13 aku: set start [lindex [$dg nodes -in $start] 0] 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: return [struct::list reverse [lrange $path $seen($start) end]] 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: 94c39d6375 2007-11-14 aku: proc ID {cset} { return "<[$cset id]>" } 94c39d6375 2007-11-14 aku: 85bd219d0b 2007-11-13 aku: proc BreakCycle {dg cycle} { 94c39d6375 2007-11-14 aku: # The cycle we have gotten is broken by breaking apart one or 94c39d6375 2007-11-14 aku: # more of the changesets in the cycle. This causes us to 94c39d6375 2007-11-14 aku: # create one or more changesets which are to be committed, 94c39d6375 2007-11-14 aku: # added to the graph, etc. pp. 94c39d6375 2007-11-14 aku: 94c39d6375 2007-11-14 aku: set cprint [join [struct::list map $cycle [myproc ID]] { }] 94c39d6375 2007-11-14 aku: 94c39d6375 2007-11-14 aku: lappend cycle [lindex $cycle 0] [lindex $cycle 1] 94c39d6375 2007-11-14 aku: set bestlink {} 94c39d6375 2007-11-14 aku: set bestnode {} 94c39d6375 2007-11-14 aku: 94c39d6375 2007-11-14 aku: foreach \ 94c39d6375 2007-11-14 aku: prev [lrange $cycle 0 end-2] \ 94c39d6375 2007-11-14 aku: cset [lrange $cycle 1 end-1] \ 94c39d6375 2007-11-14 aku: next [lrange $cycle 2 end] { 94c39d6375 2007-11-14 aku: 94c39d6375 2007-11-14 aku: # Each triple PREV -> CSET -> NEXT of changesets, a 94c39d6375 2007-11-14 aku: # 'link' in the cycle, is analysed and the best 94c39d6375 2007-11-14 aku: # location where to at least weaken the cycle is 94c39d6375 2007-11-14 aku: # chosen for further processing. 94c39d6375 2007-11-14 aku: 94c39d6375 2007-11-14 aku: set link [project::revlink %AUTO% $prev $cset $next] 94c39d6375 2007-11-14 aku: if {$bestlink eq ""} { 94c39d6375 2007-11-14 aku: set bestlink $link 94c39d6375 2007-11-14 aku: set bestnode $cset 94c39d6375 2007-11-14 aku: } elseif {[$link betterthan $bestlink]} { 94c39d6375 2007-11-14 aku: $bestlink destroy 94c39d6375 2007-11-14 aku: set bestlink $link 94c39d6375 2007-11-14 aku: set bestnode $cset 94c39d6375 2007-11-14 aku: } else { 94c39d6375 2007-11-14 aku: $link destroy 94c39d6375 2007-11-14 aku: } 94c39d6375 2007-11-14 aku: } 94c39d6375 2007-11-14 aku: 94c39d6375 2007-11-14 aku: log write 5 breakrcycle "Breaking cycle ($cprint) by splitting changeset <[$bestnode id]>" 94c39d6375 2007-11-14 aku: 94c39d6375 2007-11-14 aku: set newcsets [$bestlink break] 94c39d6375 2007-11-14 aku: $bestlink destroy 94c39d6375 2007-11-14 aku: 94c39d6375 2007-11-14 aku: # At this point the old changeset (BESTNODE) is gone 94c39d6375 2007-11-14 aku: # already. We remove it from the graph as well and then enter 94c39d6375 2007-11-14 aku: # the fragments generated for it. 94c39d6375 2007-11-14 aku: 94c39d6375 2007-11-14 aku: $dg node delete $bestnode 94c39d6375 2007-11-14 aku: 94c39d6375 2007-11-14 aku: foreach cset $newcsets { 94c39d6375 2007-11-14 aku: dg node insert $cset 94c39d6375 2007-11-14 aku: dg node set $cset timerange [$cset timerange] 94c39d6375 2007-11-14 aku: } 94c39d6375 2007-11-14 aku: 94c39d6375 2007-11-14 aku: foreach cset $newcsets { 94c39d6375 2007-11-14 aku: foreach succ [$cset successors] { 94c39d6375 2007-11-14 aku: dg arc insert $cset $succ 94c39d6375 2007-11-14 aku: } 94c39d6375 2007-11-14 aku: } 85bd219d0b 2007-11-13 aku: return 85bd219d0b 2007-11-13 aku: } 85bd219d0b 2007-11-13 aku: 85bd219d0b 2007-11-13 aku: typevariable at 0 ; # Counter for commit ids for the changesets. 85bd219d0b 2007-11-13 aku: typevariable bottom {} ; # List of candidate nodes for committing. 85bd219d0b 2007-11-13 aku: 2a01d50430 2007-11-11 aku: # # ## ### ##### ######## ############# 2a01d50430 2007-11-11 aku: ## Configuration 2a01d50430 2007-11-11 aku: 2a01d50430 2007-11-11 aku: pragma -hasinstances no ; # singleton 2a01d50430 2007-11-11 aku: pragma -hastypeinfo no ; # no introspection 2a01d50430 2007-11-11 aku: pragma -hastypedestroy no ; # immortal 2a01d50430 2007-11-11 aku: 2a01d50430 2007-11-11 aku: # # ## ### ##### ######## ############# 2a01d50430 2007-11-11 aku: } 2a01d50430 2007-11-11 aku: 2a01d50430 2007-11-11 aku: namespace eval ::vc::fossil::import::cvs::pass { 85bd219d0b 2007-11-13 aku: namespace export breakrcycle 85bd219d0b 2007-11-13 aku: namespace eval breakrcycle { 85bd219d0b 2007-11-13 aku: namespace import ::vc::fossil::import::cvs::state 85bd219d0b 2007-11-13 aku: namespace eval project { 85bd219d0b 2007-11-13 aku: namespace import ::vc::fossil::import::cvs::project::rev 94c39d6375 2007-11-14 aku: namespace import ::vc::fossil::import::cvs::project::revlink 85bd219d0b 2007-11-13 aku: } 2a01d50430 2007-11-11 aku: namespace import ::vc::tools::log 94c39d6375 2007-11-14 aku: log register breakrcycle 2a01d50430 2007-11-11 aku: } 2a01d50430 2007-11-11 aku: } 2a01d50430 2007-11-11 aku: 2a01d50430 2007-11-11 aku: # # ## ### ##### ######## ############# ##################### 2a01d50430 2007-11-11 aku: ## Ready 2a01d50430 2007-11-11 aku: 2a01d50430 2007-11-11 aku: package provide vc::fossil::import::cvs::pass::breakrcycle 1.0 2a01d50430 2007-11-11 aku: return
File Annotation