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

Overview
Comment:Put the graph traversal core of the cycle breaker core into a separate class, for use in other parts of the system. TODO: Rewrite the cycle breaker core in terms of this class.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:e70131373302d41968d95982033ddf3ef3de54f9
User & Date: aku 2007-12-05 07:50:17
Context
2007-12-05
07:52
Added helper class managing access to fossil repositories. Already has a basic method to import and delta-compress a series of files. Used 'test' commands of fossil to get the necessary low-level access. check-in: b6bf21e2 user: aku tags: trunk
07:50
Put the graph traversal core of the cycle breaker core into a separate class, for use in other parts of the system. TODO: Rewrite the cycle breaker core in terms of this class. check-in: e7013137 user: aku tags: trunk
07:47
Extended project class with method return full path of the project, i.e. inclusive its repository base path. check-in: 82e35d33 user: aku tags: trunk
Changes

Added tools/cvs2fossil/lib/c2f_gtcore.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
## -*- 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
# # ## ### ##### ######## ############# #####################

## This file provides a helper package implementing the core of
## traversing the nodes of a graph in topological order. This is used
## by the cycle breaker code (not yet), and the import backend.

# # ## ### ##### ######## ############# #####################
## 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::tools::trouble                        ; # Error reporting.

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

snit::type ::vc::fossil::import::cvs::gtcore {
    # # ## ### ##### ######## #############
    ## Public API

    typemethod savecmd   {cmd} { ::variable mysavecmd   $cmd ; return }
    typemethod cyclecmd  {cmd} { ::variable mycyclecmd  $cmd ; return }
    typemethod sortcmd   {cmd} { ::variable mysortcmd   $cmd ; return }
    typemethod datacmd   {cmd} { ::variable mydatacmd   $cmd ; return }
    typemethod formatcmd {cmd} { ::variable myformatcmd $cmd ; return }

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

    typemethod traverse {graph} {
	InitializeCandidates $graph

	log write 3 gtcore {Traverse}

	set k   0
	set max [llength [$graph nodes]]

	while {1} {
	    while {[WithoutPredecessor $graph node]} {
		log progress 2 gtcore $k $max
		incr k

		ProcessedHook    $graph $node
		ShowPendingNodes $graph
		$graph node delete      $node
	    }

	    if {![llength [$graph nodes]]} break

	    CycleHook            $graph
	    InitializeCandidates $graph
	}

	$graph destroy

	log write 3 gtcore Done.
	ClearHooks
	return
    }

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

    # Instead of searching the whole graph for the degree-0 nodes in
    # each iteration we compute the list once to start, and then only
    # update it incrementally based on the outgoing neighbours of the
    # node chosen for commit.

    proc InitializeCandidates {graph} {
	# bottom = list (list (node, range min, range max))
	::variable mybottom
	foreach node [$graph nodes] {
	    if {[$graph node degree -in $node]} continue
	    lappend mybottom [list $node [DataHook $graph $node]]
	}
	ScheduleCandidates $graph
	ShowPendingNodes   $graph
	return
    }

    proc WithoutPredecessor {graph nodevar} {
	::variable mybottom

	upvar 1 $nodevar node
	if {![llength $mybottom]} { return 0 }

	set node [lindex [lindex $mybottom 0] 0]
	set mybottom     [lrange $mybottom 1 end]
	set changed 0

	# Update list of nodes without predecessor, based on the
	# outgoing neighbours of the chosen node. This should be
	# faster than iterating of the whole set of nodes, finding all
	# without predecessors, sorting them by time, etc. pp.

	foreach out [$graph nodes -out $node] {
	    if {[$graph node degree -in $out] > 1} continue
	    # Degree-1 neighbour, will have no predecessors after the
	    # removal of n. Put on the list of candidates we can
	    # process.
	    lappend mybottom [list $out [DataHook $graph $out]]
	    set changed 1
	}
	if {$changed} {
	    ScheduleCandidates $graph
	}

	# We do not delete the node immediately, to allow the Save
	# procedure to save the dependencies as well (encoded in the
	# arcs).
	return 1
    }

    proc ScheduleCandidates {graph} {
	::variable mybottom
	::variable mysortcmd
	if {[llength $mysortcmd]} {
	    set mybottom [uplevel \#0 [linsert $mysortcmd end $graph $mybottom]]
	} else {
	    set mybottom [lsort -index 0 -dict $mybottom]
	}
	return
    }

    proc ShowPendingNodes {graph} {
	if {[log verbosity?] < 10} return
	::variable mybottom
	::variable myformatcmd

	log write 10 gtcore "Pending..............................."
	foreach item [struct::list map $mybottom \
			  [linsert $myformatcmd end $graph]] {
	    log write 10 gtcore "Pending:     $item"
	}
	return
    }

    # # ## ### ##### ######## #############
    ## Callback invokation ...

    proc DataHook {graph node} {
	# Allow the user of the traverser to a client data to a node
	# in the list of nodes available for immediate processing.
	# This data can be used by the sort callback.

	::variable mydatacmd
	if {![llength $mydatacmd]} { return {} }

	return [uplevel \#0 [linsert $mydatacmd end $graph $node]]
    }

    proc FormatHook {graph item} {
	# Allow the user to format a pending item (node + client data)
	# according to its wishes.

	::variable myformatcmd
	if {![llength $myformatcmd]} { return $item }

	return [uplevel \#0 [linsert $myformatcmd end $graph $item]]
    }

    proc ProcessedHook {graph node} {
	# Give the user of the traverser the opportunity to work with
	# the node before it is removed from the graph.

	::variable mysavecmd
	if {![llength $mysavecmd]} return

	uplevel \#0 [linsert $mysavecmd end $graph $node]
	return
    }

    proc CycleHook {graph} {
	# Call out to the chosen algorithm for handling cycles. It is
	# an error to find a cycle if no hook was defined.

	::variable mycyclecmd
	if {![llength $mycyclecmd]} {
	    trouble fatal "Found a cycle, expecting none."
	    exit 1
	}

	uplevel \#0 [linsert $mycyclecmd end $graph]
	return
    }

    proc ClearHooks {} {
	::variable mysortcmd   {}
	::variable myformatcmd {}
	::variable mydatacmd   {}
	::variable mysavecmd   {}
	::variable mycyclecmd  {}
	return
    }

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

    typevariable mybottom    {} ; # List of the nodes pending traversal.

    typevariable mysortcmd   {} ; # Callback, sort list of pending nodes
    typevariable mydatacmd   {} ; # Callback, get client data for a pending node
    typevariable myformatcmd {} ; # Callback, format a pending node for display
    typevariable mysavecmd   {} ; # Callback, for each processed node.
    typevariable mycyclecmd  {} ; # Callback, when a cycle was encountered.

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

    pragma -hasinstances   no ; # singleton
    pragma -hastypeinfo    no ; # no introspection
    pragma -hastypedestroy no ; # immortal

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

namespace eval ::vc::fossil::import::cvs {
    namespace export gtcore
    namespace eval   gtcore {
	namespace import ::vc::tools::log
	namespace import ::vc::tools::trouble
	log register gtcore
    }
}

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

package provide vc::fossil::import::cvs::gtcore 1.0
return

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

19
20
21
22
23
24
25

26
27
28
29
30
31
32
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]]

package ifneeded vc::fossil::import::cvs::cyclebreaker      1.0 [list source [file join $dir c2f_cyclebreaker.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]]







>







19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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]]
package ifneeded vc::fossil::import::cvs::gtcore            1.0 [list source [file join $dir c2f_gtcore.tcl]]
package ifneeded vc::fossil::import::cvs::cyclebreaker      1.0 [list source [file join $dir c2f_cyclebreaker.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]]