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

Overview
Comment:Tweaks of the log output, and reworked internals to expose not only breaking of cycles, but of paths as well.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:54e9b0a1439023bd37ee40edc6f6ccb1b5b23213
User & Date: aku 2007-11-25 02:51:50
Context
2007-11-25
02:52
Bugfix in pass manager, handling of open-ended pass specifications. check-in: 9668b164 user: aku tags: trunk
02:51
Tweaks of the log output, and reworked internals to expose not only breaking of cycles, but of paths as well. check-in: 54e9b0a1 user: aku tags: trunk
2007-11-24
05:31
Created convenience methods to create the human readable repesentation of a changeset and lists of such, and made liberal use of them. check-in: 87cf6090 user: aku tags: trunk
Changes

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

91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
...
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
...
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
...
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346

	# 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 cyclebreaker {Now sorting the changesets, breaking cycles}

	InitializeCandidates $dg
	while {1} {
	    while {[WithoutPredecessor $dg n]} {
		ProcessedHook $dg $n $myat
		$dg node delete $n
		incr myat
................................................................................
	set   dg [Setup [uplevel #0 $changesetcmd] 0]
	Mark $dg -done
	$dg destroy
	return
    }

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






    typemethod break {graph} {
	BreakCycle $graph [FindCycle $graph]











	return
    }

    typemethod replace {graph n replacements} {
	Replace $graph $n $replacements
	return
    }

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

    proc Setup {changesets {log 1}} {
	if {$log} {
	    log write 3 cyclebreaker "Creating changeset graph, filling with nodes"
	    log write 3 cyclebreaker "Adding [nsp [llength $changesets] node]"
	}

	set dg [struct::graph dg]

	foreach cset $changesets {
	    $dg node insert $cset
	    $dg node set    $cset timerange [$cset timerange]
................................................................................
	    # Choose arbitrary predecessor
	    set start [lindex [$dg nodes -in $start] 0]
	}

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

    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.

	# NOTE/TODO. Move this map operation to project::rev, as typemethod.
	set cprint [project::rev strlist $cycle]

	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]
................................................................................
		    set bestlink $link
		    set bestnode $cset
		} else {
		    $link destroy
		}
	    }

	log write 5 cyclebreaker "Breaking cycle ($cprint) by splitting changeset [$bestnode str]"
	set ID [$bestnode id]
	Mark $dg -${ID}-before

	set newcsets [$bestlink break]
	$bestlink destroy

        # At this point the old changeset (BESTNODE) is gone







|







 








>
>
>
>
>

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













<
|







 







|
|
|
|
|

<
<
<
<




|
|
|







 







|







91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
...
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
...
311
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
...
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357

	# 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 cyclebreaker {Traverse changesets}

	InitializeCandidates $dg
	while {1} {
	    while {[WithoutPredecessor $dg n]} {
		ProcessedHook $dg $n $myat
		$dg node delete $n
		incr myat
................................................................................
	set   dg [Setup [uplevel #0 $changesetcmd] 0]
	Mark $dg -done
	$dg destroy
	return
    }

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

    typemethod break-segment {graph} {
	BreakSegment $graph $path "segment ([project::rev strlist $path])"
	return
    }

    typemethod break {graph} {
	set cycle [FindCycle $graph]
	set label "cycle ([project::rev strlist $cycle])"

	# NOTE: cvs2svn uses the sequence "end-1, cycle, 0" to create
	#       the path from the cycle. The only effect I can see is
	#       that this causes the link-triples to be generated in a
	#       sightly different order, i.e. one link rotated to the
	#       right. This should have no effect on the search for
	#       the best of all.

	lappend cycle [lindex $cycle 0] [lindex $cycle 1]
	BreakSegment $graph $cycle $label
	return
    }

    typemethod replace {graph n replacements} {
	Replace $graph $n $replacements
	return
    }

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

    proc Setup {changesets {log 1}} {
	if {$log} {

	    log write 3 cyclebreaker "Create changeset graph, [nsp [llength $changesets] node]"
	}

	set dg [struct::graph dg]

	foreach cset $changesets {
	    $dg node insert $cset
	    $dg node set    $cset timerange [$cset timerange]
................................................................................
	    # Choose arbitrary predecessor
	    set start [lindex [$dg nodes -in $start] 0]
	}

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

    proc BreakSegment {dg path label} {
	# The path, usually a 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 bestlink {}
	set bestnode {}

	foreach \
	    prev [lrange $path 0 end-2] \
	    cset [lrange $path 1 end-1] \
	    next [lrange $path 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]
................................................................................
		    set bestlink $link
		    set bestnode $cset
		} else {
		    $link destroy
		}
	    }

	log write 5 cyclebreaker "Breaking $label by splitting changeset [$bestnode str]"
	set ID [$bestnode id]
	Mark $dg -${ID}-before

	set newcsets [$bestlink break]
	$bestlink destroy

        # At this point the old changeset (BESTNODE) is gone