Fossil

Check-in [94c39d63]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Completed pass 6, wrote the code performing the breaking of cycles. Done by analysing each triple of changesets in the cycle at the file dependency level to see which revisions can be sorted apart. Added some additional utility routines. Extended the changeset class with the accessors required by the cycle breaker.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:94c39d63758d78dc26b3ad5c2fdd285ea37047d1
User & Date: aku 2007-11-14 05:11:56
Context
2007-11-14
05:26
Added note regarding 'RevisionTopologicalSortPass', which is not a separate pass for us, but part of pass 6, breaking cycles over revision changesets. check-in: f631d438 user: aku tags: trunk
05:11
Completed pass 6, wrote the code performing the breaking of cycles. Done by analysing each triple of changesets in the cycle at the file dependency level to see which revisions can be sorted apart. Added some additional utility routines. Extended the changeset class with the accessors required by the cycle breaker. check-in: 94c39d63 user: aku tags: trunk
05:08
Fixed handling of project objects when persisting them. Fill the project map. This is needed if the pass is not skipped. For the skip case we already initialize the project map when 'load'ing from the state. check-in: 67600f77 user: aku tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to tools/cvs2fossil/lib/c2f_pbreakrcycle.tcl.

13
14
15
16
17
18
19
20
21
22
23
24
25

26
27
28
29
30
31
32
33
..
63
64
65
66
67
68
69


70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
..
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
...
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236


237
238























































239
240
241
242
243
244
245
...
254
255
256
257
258
259
260

261
262
263
264
265
266
267
268
269
270
271
## Pass VI. This pass goes over the set of revision based changesets
## and breaks all dependency cycles they may be in. We need a
## dependency tree.

# # ## ### ##### ######## ############# #####################
## Requirements

package require Tcl 8.4                               ; # Required runtime.
package require snit                                  ; # OO system.
package require struct::graph                         ; # Graph handling.
package require struct::list                          ; # Higher order list operations.
package require vc::tools::log                        ; # User feedback.
package require vc::fossil::import::cvs::state        ; # State storage.

package require vc::fossil::import::cvs::project::rev ; # Project level changesets

# # ## ### ##### ######## ############# #####################
## Register the pass with the management

vc::fossil::import::cvs::pass define \
    BreakRevCsetCycles \
    {Break Revision ChangeSet Dependency Cycles} \
................................................................................
    }

    typemethod run {} {
	# Pass manager interface. Executed to perform the
	# functionality of the pass.

	state reading revision



	# We create a graph of the revision changesets, using the file
	# level dependencies to construct a first approximation of
	# them at the project level. Then look for cycles in that
	# graph and break them.

	# 1. Create nodes for all relevant changesets and a mapping
	#    from the revisions to their changesets/nodes.

	log write 3 brkrcycle {Creating changeset graph, filling with nodes}

	set dg [struct::graph dg]

	state transaction {
	    foreach cset [project::rev all] {
		if {[$cset bysymbol]} continue
		dg node insert $cset
................................................................................
	    }
	}

	# 2. Find for all relevant changeset their revisions and their
	#    dependencies. Map the latter back to changesets and
	#    construct the corresponding arcs.

	log write 3 brkrcycle {Setting up node dependencies}

	state transaction {
	    foreach cset [project::rev all] {
		if {[$cset bysymbol]} continue
		foreach succ [$cset successors] {
		    dg arc insert $cset $succ
		}
................................................................................

	# 3. Lastly we iterate the graph topologically. We mark off
	#    the nodes which have no predecessors, in order from
	#    oldest to youngest, saving and removing dependencies. If
	#    we find no nodes without predecessors we have a cycle,
	#    and work on breaking it.

	log write 3 brkrcycle {Computing changeset order, breaking cycles}

	InitializeCandidates $dg
	state transaction {
	    while {1} {
		while {[WithoutPredecessor $dg n]} {
		    SaveAndRemove $dg $n
		}
		if {![llength [dg nodes]]} break
		set cycle [FindCycle $dg]
		BreakCycle $dg $cycle
	    }
	}

	return
    }

    typemethod discard {} {
................................................................................
	array set seen {}

	while {1} {
	    # Stop searching when we have seen the current node
	    # already, the circle has been closed.
	    if {[info exists seen($start)]} break
	    lappend path $start
	    set seen($start) [llength $path]
	    # Choose arbitrary predecessor
	    set start [lindex [$dg nodes -in $start] 0]
	}

	return [struct::list reverse [lrange $path $seen($start) end]]
    }



    proc BreakCycle {dg cycle} {
	trouble internal "Break cycle <$cycle>"























































	return
    }

    typevariable at      0 ; # Counter for commit ids for the changesets.
    typevariable bottom {} ; # List of candidate nodes for committing.

    # # ## ### ##### ######## #############
................................................................................

namespace eval ::vc::fossil::import::cvs::pass {
    namespace export breakrcycle
    namespace eval breakrcycle {
	namespace import ::vc::fossil::import::cvs::state
	namespace eval project {
	    namespace import ::vc::fossil::import::cvs::project::rev

	}
	namespace import ::vc::tools::log
	log register brkrcycle
    }
}

# # ## ### ##### ######## ############# #####################
## Ready

package provide vc::fossil::import::cvs::pass::breakrcycle 1.0
return







|
|
|
|
|
|
>
|







 







>
>









|







 







|







 







|








|
|







 







|







>
>

<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







>


|








13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
..
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
..
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
...
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
...
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242

243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
...
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
## Pass VI. This pass goes over the set of revision based changesets
## and breaks all dependency cycles they may be in. We need a
## dependency tree.

# # ## ### ##### ######## ############# #####################
## Requirements

package require Tcl 8.4                                   ; # Required runtime.
package require snit                                      ; # OO system.
package require struct::graph                             ; # Graph handling.
package require struct::list                              ; # Higher order list operations.
package require vc::tools::log                            ; # User feedback.
package require vc::fossil::import::cvs::state            ; # State storage.
package require vc::fossil::import::cvs::project::rev     ; # Project level changesets
package require vc::fossil::import::cvs::project::revlink ; # Cycle links.

# # ## ### ##### ######## ############# #####################
## Register the pass with the management

vc::fossil::import::cvs::pass define \
    BreakRevCsetCycles \
    {Break Revision ChangeSet Dependency Cycles} \
................................................................................
    }

    typemethod run {} {
	# Pass manager interface. Executed to perform the
	# functionality of the pass.

	state reading revision
	state reading changeset
	state reading csrevision

	# We create a graph of the revision changesets, using the file
	# level dependencies to construct a first approximation of
	# them at the project level. Then look for cycles in that
	# graph and break them.

	# 1. Create nodes for all relevant changesets and a mapping
	#    from the revisions to their changesets/nodes.

	log write 3 breakrcycle {Creating changeset graph, filling with nodes}

	set dg [struct::graph dg]

	state transaction {
	    foreach cset [project::rev all] {
		if {[$cset bysymbol]} continue
		dg node insert $cset
................................................................................
	    }
	}

	# 2. Find for all relevant changeset their revisions and their
	#    dependencies. Map the latter back to changesets and
	#    construct the corresponding arcs.

	log write 3 breakrcycle {Setting up node dependencies}

	state transaction {
	    foreach cset [project::rev all] {
		if {[$cset bysymbol]} continue
		foreach succ [$cset successors] {
		    dg arc insert $cset $succ
		}
................................................................................

	# 3. Lastly we iterate the graph topologically. We mark off
	#    the nodes which have no predecessors, in order from
	#    oldest to youngest, saving and removing dependencies. If
	#    we find no nodes without predecessors we have a cycle,
	#    and work on breaking it.

	log write 3 breakrcycle {Computing changeset order, breaking cycles}

	InitializeCandidates $dg
	state transaction {
	    while {1} {
		while {[WithoutPredecessor $dg n]} {
		    SaveAndRemove $dg $n
		}
		if {![llength [dg nodes]]} break
		BreakCycle $dg [FindCycle $dg]
		InitializeCandidates $dg
	    }
	}

	return
    }

    typemethod discard {} {
................................................................................
	array set seen {}

	while {1} {
	    # Stop searching when we have seen the current node
	    # already, the circle has been closed.
	    if {[info exists seen($start)]} break
	    lappend path $start
	    set seen($start) [expr {[llength $path]-1}]
	    # Choose arbitrary predecessor
	    set start [lindex [$dg nodes -in $start] 0]
	}

	return [struct::list reverse [lrange $path $seen($start) end]]
    }

    proc ID {cset} { return "<[$cset id]>" }

    proc BreakCycle {dg cycle} {

	# The cycle we have gotten is broken by breaking apart one or
	# more of the changesets in the cycle. This causes us to
	# create one or more changesets which are to be committed,
	# added to the graph, etc. pp.

	set cprint [join [struct::list map $cycle [myproc ID]] { }]

	lappend cycle [lindex $cycle 0] [lindex $cycle 1]
	set bestlink {}
	set bestnode {}

	foreach \
	    prev [lrange $cycle 0 end-2] \
	    cset [lrange $cycle 1 end-1] \
	    next [lrange $cycle 2 end] {

		# Each triple PREV -> CSET -> NEXT of changesets, a
		# 'link' in the cycle, is analysed and the best
		# location where to at least weaken the cycle is
		# chosen for further processing.

		set link [project::revlink %AUTO% $prev $cset $next]
		if {$bestlink eq ""} {
		    set bestlink $link
		    set bestnode $cset
		} elseif {[$link betterthan $bestlink]} {
		    $bestlink destroy
		    set bestlink $link
		    set bestnode $cset
		} else {
		    $link destroy
		}
	    }

	log write 5 breakrcycle "Breaking cycle ($cprint) by splitting changeset <[$bestnode id]>"

	set newcsets [$bestlink break]
	$bestlink destroy

        # At this point the old changeset (BESTNODE) is gone
        # already. We remove it from the graph as well and then enter
        # the fragments generated for it.

        $dg node delete $bestnode

	foreach cset $newcsets {
	    dg node insert $cset
	    dg node set    $cset timerange [$cset timerange]
	}

	foreach cset $newcsets {
	    foreach succ [$cset successors] {
		dg arc insert $cset $succ
	    }
	}
	return
    }

    typevariable at      0 ; # Counter for commit ids for the changesets.
    typevariable bottom {} ; # List of candidate nodes for committing.

    # # ## ### ##### ######## #############
................................................................................

namespace eval ::vc::fossil::import::cvs::pass {
    namespace export breakrcycle
    namespace eval breakrcycle {
	namespace import ::vc::fossil::import::cvs::state
	namespace eval project {
	    namespace import ::vc::fossil::import::cvs::project::rev
	    namespace import ::vc::fossil::import::cvs::project::revlink
	}
	namespace import ::vc::tools::log
	log register breakrcycle
    }
}

# # ## ### ##### ######## ############# #####################
## Ready

package provide vc::fossil::import::cvs::pass::breakrcycle 1.0
return

Changes to tools/cvs2fossil/lib/c2f_prev.tcl.

42
43
44
45
46
47
48

49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64







65
66
67
68
69
70
71
..
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
...
229
230
231
232
233
234
235
236













237
238
239
240

241

242

243

244





245
246
247
248
249
250
251
...
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
...
282
283
284
285
286
287
288
289































290
291
292
293
294
295
296
...
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
	lappend mychangesets $self
	foreach r $revisions { set myrevmap($r) $self }
	return
    }

    method id        {} { return $myid }
    method revisions {} { return $myrevisions }


    method setid {id} { set myid $id ; return }

    method bysymbol   {} { return [expr {$mytype eq "sym"}] }
    method byrevision {} { return [expr {$mytype eq "rev"}] }

    method successors {} {
	# NOTE / FUTURE: Possible bottleneck.
	array set dependencies {}
	PullSuccessorRevisions dependencies $myrevisions
	set csets {}
	foreach {_ child} [array get dependencies] {
	    lappend csets $myrevmap($child)
	}
	return [lsort -unique $csets]
    }








    method breakinternaldependencies {} {
	# This method inspects the changesets for internal
	# dependencies. Nothing is done if there are no
	# such. Otherwise the changeset is split into a set of
	# fragments without internal dependencies, transforming the
	# internal dependencies into external ones. The new changesets
................................................................................
	# successor dependency a -> b is also a predecessor dependency
	# b -> a).

	# Array of dependencies (parent -> child). This is pulled from
	# the state, and limited to successors within the changeset.

	array set dependencies {}
	PullSuccessorRevisions dependencies $myrevisions
	if {![array size dependencies]} {return 0} ; # Nothing to break.

	log write 6 csets ...<$myid>.......................................................

	# We have internal dependencies to break. We now iterate over
	# all positions in the list (which is chronological, at least
	# as far as the timestamps are correct and unique) and
................................................................................
	set theset ('[join $myrevisions {','}]')
	return [state run "
	    SELECT MIN(R.date), MAX(R.date)
	    FROM revision R
	    WHERE R.rid IN $theset
	"]
    }














    # # ## ### ##### ######## #############
    ## State

    variable myid        ; # Id of the cset for the persistent state.

    variable myproject   ; # Reference of the project object the changeset belongs to.

    variable mytype      ; # rev or sym, where the cset originated from.

    variable mysrcid     ; # id of the metadata or symbol the cset is based on.

    variable myrevisions ; # List of the file level revisions in the cset.






    # # ## ### ##### ######## #############
    ## Internal methods

    typevariable mycounter        0 ; # Id counter for csets.
    typevariable mycstype -array {} ; # Map cstypes to persistent ids.

................................................................................
    typemethod getcstypes {} {
	foreach {tid name} [state run {
	    SELECT tid, name FROM cstype;
	}] { set mycstype($name) $tid }
	return
    }

    proc PullSuccessorRevisions {dv revisions} {
	upvar 1 $dv dependencies
	set theset ('[join $revisions {','}]')

	foreach {rid child} [state run "
   -- Primary children
	    SELECT R.rid, R.child
	    FROM   revision R
................................................................................
	    AND    R.rid = B.rid
	    AND    B.brid IN $theset
	"] {
	    # Consider moving this to the integrity module.
	    if {$rid == $child} {
		trouble internal "Revision $rid depends on itself."
	    }
	    set dependencies($rid) $child































	}
    }

    proc InitializeBreakState {revisions} {
	upvar 1 pos pos cross cross range range depc depc delta delta \
	    dependencies dependencies

................................................................................
	#       possible to have a backward successor dependency,
	#       i.e. with start > end. We may have to swap the indices
	#       to ensure that the following loop runs correctly.
	#
	# Note 2: start == end is not possible. It indicates a
	#         self-dependency due to the uniqueness of positions,
	#         and that is something we have ruled out already, see
	#         PullSuccessorRevisions.

	foreach {rid child} [array get dependencies] {
	    set dkey    [list $rid $child]
	    set start   $pos($rid)
	    set end     $pos($child)
	    set crosses {}








>








|
|
|
|
|



>
>
>
>
>
>
>







 







|







 








>
>
>
>
>
>
>
>
>
>
>
>
>



|
>
|
>
|
>
|
>
|
>
>
>
>
>







 







|







 







|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|







42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
..
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
...
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
...
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
...
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
...
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
	lappend mychangesets $self
	foreach r $revisions { set myrevmap($r) $self }
	return
    }

    method id        {} { return $myid }
    method revisions {} { return $myrevisions }
    method data      {} { return [list $myproject $mytype $mysrcid] }

    method setid {id} { set myid $id ; return }

    method bysymbol   {} { return [expr {$mytype eq "sym"}] }
    method byrevision {} { return [expr {$mytype eq "rev"}] }

    method successors {} {
	# NOTE / FUTURE: Possible bottleneck.
	set csets {}
	foreach {_ children} [$self nextmap] {
	    foreach child $children {
		lappend csets $myrevmap($child)
	    }
	}
	return [lsort -unique $csets]
    }

    method nextmap {} {
	if {[llength $mynextmap]} { return $mynextmap }
	PullSuccessorRevisions tmp $myrevisions
	set mynextmap [array get tmp]
	return $mynextmap
    }

    method breakinternaldependencies {} {
	# This method inspects the changesets for internal
	# dependencies. Nothing is done if there are no
	# such. Otherwise the changeset is split into a set of
	# fragments without internal dependencies, transforming the
	# internal dependencies into external ones. The new changesets
................................................................................
	# successor dependency a -> b is also a predecessor dependency
	# b -> a).

	# Array of dependencies (parent -> child). This is pulled from
	# the state, and limited to successors within the changeset.

	array set dependencies {}
	PullInternalSuccessorRevisions dependencies $myrevisions
	if {![array size dependencies]} {return 0} ; # Nothing to break.

	log write 6 csets ...<$myid>.......................................................

	# We have internal dependencies to break. We now iterate over
	# all positions in the list (which is chronological, at least
	# as far as the timestamps are correct and unique) and
................................................................................
	set theset ('[join $myrevisions {','}]')
	return [state run "
	    SELECT MIN(R.date), MAX(R.date)
	    FROM revision R
	    WHERE R.rid IN $theset
	"]
    }

    method drop {} {
	state transaction {
	    state run {
		DELETE FROM changeset  WHERE cid = $myid;
		DELETE FROM csrevision WHERE cid = $myid;
	    }
	}
	foreach r $myrevisions { unset myrevmap($r) }
	set pos          [lsearch -exact $mychangesets $self]
	set mychangesets [lreplace $mychangesets $pos $pos]
	return
    }

    # # ## ### ##### ######## #############
    ## State

    variable myid        {} ; # Id of the cset for the persistent
			      # state.
    variable myproject   {} ; # Reference of the project object the
			      # changeset belongs to.
    variable mytype      {} ; # rev or sym, where the cset originated
			      # from.
    variable mysrcid     {} ; # Id of the metadata or symbol the cset
			      # is based on.
    variable myrevisions {} ; # List of the file level revisions in
			      # the cset.
    variable mynextmap   {} ; # Dictionary mapping from the revisions
			      # to their successors. Cache to avoid
			      # loading this from the state more than
			      # once.

    # # ## ### ##### ######## #############
    ## Internal methods

    typevariable mycounter        0 ; # Id counter for csets.
    typevariable mycstype -array {} ; # Map cstypes to persistent ids.

................................................................................
    typemethod getcstypes {} {
	foreach {tid name} [state run {
	    SELECT tid, name FROM cstype;
	}] { set mycstype($name) $tid }
	return
    }

    proc PullInternalSuccessorRevisions {dv revisions} {
	upvar 1 $dv dependencies
	set theset ('[join $revisions {','}]')

	foreach {rid child} [state run "
   -- Primary children
	    SELECT R.rid, R.child
	    FROM   revision R
................................................................................
	    AND    R.rid = B.rid
	    AND    B.brid IN $theset
	"] {
	    # Consider moving this to the integrity module.
	    if {$rid == $child} {
		trouble internal "Revision $rid depends on itself."
	    }
	    lappend dependencies($rid) $child
	}
    }

    proc PullSuccessorRevisions {dv revisions} {
	upvar 1 $dv dependencies
	set theset ('[join $revisions {','}]')

	foreach {rid child} [state run "
   -- Primary children
	    SELECT R.rid, R.child
	    FROM   revision R
	    WHERE  R.rid   IN $theset
	    AND    R.child IS NOT NULL
    UNION
    -- Transition NTDB to trunk
	    SELECT R.rid, R.dbchild
	    FROM   revision R
	    WHERE  R.rid   IN $theset
	    AND    R.dbchild IS NOT NULL
    UNION
    -- Secondary (branch) children
	    SELECT R.rid, B.brid
	    FROM   revision R, revisionbranchchildren B
	    WHERE  R.rid   IN $theset
	    AND    R.rid = B.rid
	"] {
	    # Consider moving this to the integrity module.
	    if {$rid == $child} {
		trouble internal "Revision $rid depends on itself."
	    }
	    lappend dependencies($rid) $child
	}
    }

    proc InitializeBreakState {revisions} {
	upvar 1 pos pos cross cross range range depc depc delta delta \
	    dependencies dependencies

................................................................................
	#       possible to have a backward successor dependency,
	#       i.e. with start > end. We may have to swap the indices
	#       to ensure that the following loop runs correctly.
	#
	# Note 2: start == end is not possible. It indicates a
	#         self-dependency due to the uniqueness of positions,
	#         and that is something we have ruled out already, see
	#         PullInternalSuccessorRevisions.

	foreach {rid child} [array get dependencies] {
	    set dkey    [list $rid $child]
	    set start   $pos($rid)
	    set end     $pos($child)
	    set crosses {}

Added tools/cvs2fossil/lib/c2f_prevlink.tcl.

















































































































































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
## -*- 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
# # ## ### ##### ######## ############# #####################

## Helper class for the pass 6 cycle breaker. Each instance refers to
## three changesets A, B, and C, with A a predecessor of B, and B
## predecessor of C, and the whole part of a dependency cycle.

## Instances analyse the file level dependencies which gave rise to
## the changeset dependencies of A, B, and C, with the results used by
## the cycle breaker algorithm to find a good location where to at
## least weaken and at best fully break the cycle.

# # ## ### ##### ######## ############# #####################
## Requirements

package require Tcl 8.4                               ; # Required runtime.
package require snit                                  ; # OO system.
package require vc::tools::misc                       ; # Text formatting
package require vc::tools::trouble                    ; # Error reporting.
package require vc::tools::log                        ; # User feedback.
package require vc::fossil::import::cvs::state        ; # State storage.
package require vc::fossil::import::cvs::project::rev ; # Project level changesets

# # ## ### ##### ######## ############# #####################
## 

snit::type ::vc::fossil::import::cvs::project::revlink {
    # # ## ### ##### ######## #############
    ## Public API

    constructor {prev cset next} {
	set myprev $prev
	set mycset $cset
	set mynext $next

	# We perform the bulk of the analysis during construction. The
	# file revisions held by the changeset CSET can be sorted into
	# four categories.

	# 1. Revisions whose predecessors are not in PREV, nor are
	#    their successors found in NEXT. These revisions do not
	#    count, as they did not induce any of the two dependencies
	#    under consideration. They can be ignored.

	# 2. Revisions which have predecessors in PREV and sucessors
	#    in NEXT. They are called 'passthrough' in cvs2svn. They
	#    induce both dependencies under consideration and are thus
	#    critical in the creation of the cycle. As such they are
	#    also unbreakable :(

	# 3. Revisions which have predecessor in PREVE, but no
	#    successors in NEXT. As such they induced the incoming
	#    dependency, but not the outgoing one.

	# 4. Revisions which have no predecessors in PREVE, but their
	#    successors are in NEXT. As such they induced the outgoing
	#    dependency, but not the incoming one.

	# If we have no passthrough revisions then splitting the
	# changeset between categories 3 and 4, with category 1 going
	# wherever, will break the cycle. If category 2 revisions are
	# present we can still perform the split, this will however
	# not break the cycle, only weaken it.

	array set csetprevmap [Invert [$myprev nextmap]]
	array set csetnextmap [$mycset nextmap]

	set prevrev [$myprev revisions]
	set nextrev [$mynext revisions]

	foreach r [$mycset revisions] {
	    set rt [RT $r]
	    incr    mycount($rt)
	    lappend mycategory($rt) $r
	}
	return
    }

    # Result is TRUE if and only breaking myset will do some good.
    method breakable {} { expr  {$mycount(prev) || $mycount(next)} }
    method passcount {} { return $mycount(pass) }

    method linkstomove {} {
	# Return the number of revisions that would be moved should we
	# split the changeset.

	set n [min2 $mycount(prev) $mycount(next)]
	if {$n > 0 } { return $n }
	return [max2 $mycount(prev) $mycount(next)]
    }

    method betterthan {other} {
	set sbreak [$self  breakable]
	set obreak [$other breakable]

	if {$sbreak && !$obreak} { return 1 } ; # self is better.
	if {!$sbreak && $obreak} { return 0 } ; # self is worse.

	# Equality. Look at the counters.
	# - Whichever has the lesser number of passthrough revisions
	#   is better, as more can be split off, weakening the cycle
	#   more.
	# - Whichever has less links to move is better.

	set opass [$other passcount]
	if {$mycount(pass) < $opass} { return 1 } ; # self is better.
	if {$mycount(pass) > $opass} { return 0 } ; # self is worse.

	set smove [$self  linkstomove]
	set omove [$other linkstomove]

	if {$smove < $omove} { return 1 } ; # self is better.

	return 0 ; # Self is worse or equal, i.e. not better.
    }

    method break {} {
	if {![$self breakable]} {
	    trouble internal "Changeset <[$mycset id]> is not breakable."
	}

	# One thing to choose when splitting CSET is where the
	# revision in categories 1 and 2 (none and passthrough
	# respectively) are moved to. This is done using the counters.

	if {!$mycount(prev)} {
	    # Nothing in category 3 => 1,2 go there, 4 the other.
	    set mycategory(prev) [concat $mycategory(none) $mycategory(pass)]
	} elseif {!$mycount(next)} {
	    # Nothing in category 4 => 1,2 go there, 3 the other.
	    set mycategory(next) [concat $mycategory(none) $mycategory(pass)]
	} elseif {$mycount(prev) < $mycount(next)} {
	    # Less predecessors than successors => 1,2 go to the
	    # sucessors.
	    set mycategory(next) [concat $mycategory(next) $mycategory(none) \
				      $mycategory(pass)]
	} else {
	    # Less successors than predecessors => 1,2 go to the
	    # predecessors.
	    set mycategory(next) [concat $mycategory(next) $mycategory(none) \
				      $mycategory(pass)]
	}

	# We now have the split in the mycategory(prev|next)
	# elements. As part of the creation of the new changesets the
	# old one is dropped from all databases, in and out of memory,
	# and then destroyed.

	struct::list assign [$mycset data] project cstype cssrc
	$mycset drop
	$mycset destroy

	set newcsets {}
	lappend newcsets [project::rev %AUTO% $project $cstype $cssrc $mycategory(prev)]
	lappend newcsets [project::rev %AUTO% $project $cstype $cssrc $mycategory(next)]

	foreach c $newcsets { $c persist }

	return $newcsets
    }

    # # ## ### ##### ######## #############
    ## State

    variable myprev {} ; # Reference to predecessor changeset in the link.
    variable mycset {} ; # Reference to the main changeset of the link.
    variable mynext {} ; # Reference to the successor changeset in the link.

    # Counters for the revision categories.
    variable mycount -array {
	none 0
	prev 0
	next 0
	pass 0
    }
    # Lists of revisions for the various categories
    variable mycategory -array {
	none {}
	prev {}
	next {}
	pass {}
    }

    # # ## ### ##### ######## #############
    ## Internal methods

    proc RT {r} {
	upvar 1 csetprevmap csetprevmap csetnextmap csetnextmap prevrev prevrev nextrev nextrev

	set inc	[expr {[info exists csetprevmap($r)]
		       ? [struct::set size [struct::set intersect $csetprevmap($r) $prevrev]]
		       : 0}]
	set out [expr {[info exists csetnextmap($r)]
		       ? [struct::set size [struct::set intersect $csetnextmap($r) $nextrev]]
		       : 0}]

	if {$inc && $out} { return pass }
	if {$inc}         { return prev }
	if {$out}         { return next }
	return none
    }

    proc Invert {dict} {
	array set tmp {}
	foreach {k values} $dict {
	    foreach v $values { lappend tmp($v) $k }
	}
	return [array get tmp]
    }

    # # ## ### ##### ######## #############
    ## Configuration

    pragma -hastypeinfo    no  ; # no type introspection
    pragma -hasinfo        no  ; # no object introspection
    pragma -simpledispatch yes ; # simple fast dispatch

    # # ## ### ##### ######## #############
}

namespace eval ::vc::fossil::import::cvs::project {
    namespace export revlink
    namespace eval revlink {
	namespace import ::vc::fossil::import::cvs::state
	namespace import ::vc::tools::misc::*
	namespace import ::vc::tools::trouble
	namespace eval project {
	    namespace import ::vc::fossil::import::cvs::project::rev
	}
	namespace import ::vc::tools::log
	log register csets
    }
}

# # ## ### ##### ######## ############# #####################
## Ready

package provide vc::fossil::import::cvs::project::revlink 1.0
return

Changes to tools/cvs2fossil/lib/misc.tcl.

35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51





















52
53
54
55
56
57
58
..
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
    # As above, with the number automatically put in front of the
    # string.

    proc nsp {n singular {plural {}}} {
	return "$n [sp $n $singular $plural]"
    }

    # Find maximum in a list.

    proc max {list} {
	set max -1
	foreach e $list {
	    if {$e < $max} continue
	    set max $e
	}
	return $max
    }






















    proc ldelete {lv item} {
	upvar 1 $lv list
	set pos [lsearch -exact $list $item]
	if {$pos < 0} return
	set list [lreplace $list $pos $pos]
	return
................................................................................
	return [eval [linsert [file split $path] 0 file join]]
    }

    # # ## ### ##### ######## #############
}

namespace eval ::vc::tools::misc {
    namespace export sp nsp max ldelete striptrailingslash
}

# -----------------------------------------------------------------------------
# Ready

package provide vc::tools::misc 1.0
return







|









>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|







35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
..
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
    # As above, with the number automatically put in front of the
    # string.

    proc nsp {n singular {plural {}}} {
	return "$n [sp $n $singular $plural]"
    }

    # Find maximum/minimum in a list.

    proc max {list} {
	set max -1
	foreach e $list {
	    if {$e < $max} continue
	    set max $e
	}
	return $max
    }

    proc min {list} {
	set min {}
	foreach e $list {
	    if {$min == {}} {
		set min $e
	    } elseif {$e > $min} continue
	    set min $e
	}
	return $min
    }

    proc max2 {a b} {
	if {$a > $b}  { return $a }
	return $b
    }

    proc min2 {a b} {
	if {$a < $b}  { return $a }
	return $b
    }

    proc ldelete {lv item} {
	upvar 1 $lv list
	set pos [lsearch -exact $list $item]
	if {$pos < 0} return
	set list [lreplace $list $pos $pos]
	return
................................................................................
	return [eval [linsert [file split $path] 0 file join]]
    }

    # # ## ### ##### ######## #############
}

namespace eval ::vc::tools::misc {
    namespace export sp nsp max min max2 min2 ldelete striptrailingslash
}

# -----------------------------------------------------------------------------
# Ready

package provide vc::tools::misc 1.0
return

Changes to tools/cvs2fossil/lib/pkgIndex.tcl.

17
18
19
20
21
22
23

24
25
26
27
28
29
30
31
32
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::breakrcycle 1.0 [list source [file join $dir c2f_pbreakrcycle.tcl]]
package ifneeded vc::fossil::import::cvs::project           1.0 [list source [file join $dir c2f_project.tcl]]
package ifneeded vc::fossil::import::cvs::project::lodmgr   1.0 [list source [file join $dir c2f_plodmgr.tcl]]
package ifneeded vc::fossil::import::cvs::project::rev      1.0 [list source [file join $dir c2f_prev.tcl]]

package ifneeded vc::fossil::import::cvs::project::sym      1.0 [list source [file join $dir c2f_psym.tcl]]
package ifneeded vc::fossil::import::cvs::project::trunk    1.0 [list source [file join $dir c2f_ptrunk.tcl]]
package ifneeded vc::fossil::import::cvs::repository        1.0 [list source [file join $dir c2f_repository.tcl]]
package ifneeded vc::fossil::import::cvs::state             1.0 [list source [file join $dir c2f_state.tcl]]
package ifneeded vc::rcs::parser                            1.0 [list source [file join $dir rcsparser.tcl]]
package ifneeded vc::tools::log                             1.0 [list source [file join $dir log.tcl]]
package ifneeded vc::tools::misc                            1.0 [list source [file join $dir misc.tcl]]
package ifneeded vc::tools::trouble                         1.0 [list source [file join $dir trouble.tcl]]
package ifneeded vc::tools::id                              1.0 [list source [file join $dir id.tcl]]







>









17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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::breakrcycle 1.0 [list source [file join $dir c2f_pbreakrcycle.tcl]]
package ifneeded vc::fossil::import::cvs::project           1.0 [list source [file join $dir c2f_project.tcl]]
package ifneeded vc::fossil::import::cvs::project::lodmgr   1.0 [list source [file join $dir c2f_plodmgr.tcl]]
package ifneeded vc::fossil::import::cvs::project::rev      1.0 [list source [file join $dir c2f_prev.tcl]]
package ifneeded vc::fossil::import::cvs::project::revlink  1.0 [list source [file join $dir c2f_prevlink.tcl]]
package ifneeded vc::fossil::import::cvs::project::sym      1.0 [list source [file join $dir c2f_psym.tcl]]
package ifneeded vc::fossil::import::cvs::project::trunk    1.0 [list source [file join $dir c2f_ptrunk.tcl]]
package ifneeded vc::fossil::import::cvs::repository        1.0 [list source [file join $dir c2f_repository.tcl]]
package ifneeded vc::fossil::import::cvs::state             1.0 [list source [file join $dir c2f_state.tcl]]
package ifneeded vc::rcs::parser                            1.0 [list source [file join $dir rcsparser.tcl]]
package ifneeded vc::tools::log                             1.0 [list source [file join $dir log.tcl]]
package ifneeded vc::tools::misc                            1.0 [list source [file join $dir misc.tcl]]
package ifneeded vc::tools::trouble                         1.0 [list source [file join $dir trouble.tcl]]
package ifneeded vc::tools::id                              1.0 [list source [file join $dir id.tcl]]