Fossil

Check-in [66c85b4d]
Login

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

Overview
Comment:Investigation of changeset order differences between running passes 1 to 6 and pass 6 alone show why the topological sort passes are separate in cvs2svn. The breaking of cycles can change the order of things due to different timeranges and dependencies of the broken changesets. Created two new passes for the sorting. The break passes 7 and 8 are now passes 8 and 9, and the new sort passes are 7 and 10.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:66c85b4db47d612813594021856271974b584157
User & Date: aku 2007-11-25 02:59:21
Context
2007-11-25
03:00
Moved the parts taken over by the top. sort passes out the breaker passes, and renumbered them (comments). check-in: b6b7ff79 user: aku tags: trunk
02:59
Investigation of changeset order differences between running passes 1 to 6 and pass 6 alone show why the topological sort passes are separate in cvs2svn. The breaking of cycles can change the order of things due to different timeranges and dependencies of the broken changesets. Created two new passes for the sorting. The break passes 7 and 8 are now passes 8 and 9, and the new sort passes are 7 and 10. check-in: 66c85b4d user: aku tags: trunk
02:54
Tweaked log output of filtering pass a bit. check-in: b41127b9 user: aku tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

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

## Pass X. This pass goes over all changesets and sorts them
## topologically. It assumes that there are no cycles which could
## impede it, any remaining having been broken by the previous two
## passes, and aborts if that condition doesn't hold.

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

package require Tcl 8.4                                   ; # Required runtime.
package require snit                                      ; # OO system.
package require struct::list                              ; # Higher order list operations.
package require vc::tools::log                            ; # User feedback.
package require vc::fossil::import::cvs::cyclebreaker     ; # Breaking dependency cycles.
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 \
    AllTopologicalSort \
    {Topologically Sort All ChangeSets} \
    ::vc::fossil::import::cvs::pass::atopsort

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

snit::type ::vc::fossil::import::cvs::pass::atopsort {
    # # ## ### ##### ######## #############
    ## Public API

    typemethod setup {} {
	# Define the names and structure of the persistent state of
	# this pass.

	state reading csorder

	state writing cstimestamp {
	    -- Commit order of all changesets based on their
	    -- dependencies, plus a monotonically increasing
	    -- timestamp.

	    cid  INTEGER  NOT NULL  REFERENCES changeset,
	    pos  INTEGER  NOT NULL,
	    date INTEGER  NOT NULL,
	    UNIQUE (cid),
	    UNIQUE (pos),
	    UNIQUE (date)
	}
	return
    }

    typemethod load {} {
	# Pass manager interface. Executed to load data computed by
	# this pass into memory when this pass is skipped instead of
	# executed.
	return
    }

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

	cyclebreaker savecmd  [myproc SaveTimestamps]

	state transaction {
	    LoadSymbolChangesets
	    cyclebreaker run break-all [myproc Changesets]
	}
	return
    }

    typemethod discard {} {
	# Pass manager interface. Executed for all passes after the
	# run passes, to remove all data of this pass from the state,
	# as being out of date.

	state discard cstimestamp
	return
    }

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

    proc Changesets {} { project::rev all }

    proc LoadSymbolChangesets {} {
	set mysymchangesets [struct::list filter [project::rev all] [myproc IsBySymbol]]
	return
    }

    proc SaveTimestamps {graph at cset} {
	set cid [$cset id]

	set date [GetTime [lindex [$graph node get $cset timerange] 1] \
		      [struct::set contain $mysymchangesets $cset]]

	log write 4 atopsort "Changeset @ $at: [$cset str]"
	state run {
	    INSERT INTO cstimestamp (cid,  pos, date)
	    VALUES                  ($cid, $at, $date)
	}
	return
    }

    proc GetTime {stamp expectchange} {
	::variable mylasttimestamp
	if {$stamp > $mymaxtimestamp} {
	    # A timestamp in the future is believed to be bogus and
	    # shifted backwars in time to prevent it from forcing
	    # other timestamps to be pushed even further in the
	    # future.

	    # From cvs2svn: Note that this is not nearly a complete
	    # solution to the bogus timestamp problem.  A timestamp in
	    # the future still affects the ordering of changesets, and
	    # a changeset having such a timestamp will not be
	    # committed until all changesets with earlier timestamps
	    # have been committed, even if other changesets with even
	    # earlier timestamps depend on this one.

	    incr mylasttimestamp
	    if {!$expectchange} {
		log write 4 atopsort "Timestamp [clock format $stamp] is in the future; shifted back to [clock format $mylasttimestamp]"
	    }
	} elseif {$stamp < ($mylasttimestamp)+1} {
	    incr mylasttimestamp
	    if {!$expectchange} {
		log write 4 atopsort "Timestamp [clock format $stamp] adjusted to [clock format $mylasttimestamp]"
	    }
	} else {
	    set mylasttimestamp $stamp
	}
	return $mylasttimestamp
    }

    typevariable mysymchangesets {} ; # Set of the symbol changesets.
    typevariable mylasttimestamp 0  ; # Last delivered timestamp.
    typevariable mymaxtimestamp 

    typeconstructor {
	# The maximum timestamp considered as reasonable is
	# "now + 1 day".
	set  mymaxtimestamp [clock seconds]
	incr mymaxtimestamp 86400 ; # 24h * 60min * 60sec
	return
    }

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

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

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

namespace eval ::vc::fossil::import::cvs::pass {
    namespace export atopsort
    namespace eval atopsort {
	namespace import ::vc::fossil::import::cvs::cyclebreaker
	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 atopsort
    }
}

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

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

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

## Pass VII. This pass goes over the set of revision based changesets
## and sorts them topologically. It assumes that there are no cycles
## which could impede it, any having been broken by the previous pass,
## and aborts if that condition doesn't hold.

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

package require Tcl 8.4                                   ; # Required runtime.
package require snit                                      ; # OO system.
package require struct::list                              ; # Higher order list operations.
package require vc::tools::log                            ; # User feedback.
package require vc::fossil::import::cvs::cyclebreaker     ; # Breaking dependency cycles.
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 \
    RevTopologicalSort \
    {Topologically Sort Revision ChangeSets} \
    ::vc::fossil::import::cvs::pass::rtopsort

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

snit::type ::vc::fossil::import::cvs::pass::rtopsort {
    # # ## ### ##### ######## #############
    ## Public API

    typemethod setup {} {
	# Define the names and structure of the persistent state of
	# this pass.

	state reading revision
	state reading changeset
	state reading csrevision

	state writing csorder {
	    -- Commit order of the revision changesets based on their
	    -- dependencies

	    cid INTEGER  NOT NULL  REFERENCES changeset,
	    pos INTEGER  NOT NULL,
	    UNIQUE (cid),
	    UNIQUE (pos)
	}
	return
    }

    typemethod load {} {
	# Pass manager interface. Executed to load data computed by
	# this pass into memory when this pass is skipped instead of
	# executed.

	state reading changeset
	project::rev loadcounter
	return
    }

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

	cyclebreaker savecmd  [myproc SaveOrder]
	state transaction {
	    cyclebreaker run break-rev [myproc Changesets]
	}
	return
    }

    typemethod discard {} {
	# Pass manager interface. Executed for all passes after the
	# run passes, to remove all data of this pass from the state,
	# as being out of date.

	state discard csorder
	return
    }

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

    proc Changesets {} {
	return [struct::list filter [project::rev all] [myproc IsByRevision]]
    }

    proc IsByRevision {cset} { $cset byrevision }

    proc SaveOrder {graph at cset} {
	set cid [$cset id]

	log write 4 rtopsort "Changeset @ $at: [$cset str] <<[$graph node set $cset timerange]>>"
	state run {
	    INSERT INTO csorder (cid,  pos)
	    VALUES              ($cid, $at)
	}
	return
    }

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

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

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

namespace eval ::vc::fossil::import::cvs::pass {
    namespace export rtopsort
    namespace eval rtopsort {
	namespace import ::vc::fossil::import::cvs::cyclebreaker
	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 rtopsort
    }
}

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

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

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

32
33
34
35
36
37
38
39
40
41
42
43

44
45

46
47
48
49
50
51
52
# Note: cvs2svn's SortRevisionSummaryPass and SortSymbolSummaryPass
#       are not implemented by us. They are irrelevant due to our use
#       of a relational database proper for the persistent state,
#       allowing us to sort the data on the fly as we need it.

package require vc::fossil::import::cvs::pass::initcsets   ; # Init'ialize C'hange'Sets
package require vc::fossil::import::cvs::pass::breakrcycle ; # Break' R'evision Cycle's

# Note: cvs2svn's RevisionTopologicalSortPass is not a separate pass,
#       but was subsumed by the previous pass, by immediately saving
#       the order of consumed graph nodes to 'csorder'.


package require vc::fossil::import::cvs::pass::breakscycle ; # Break' S'ymbol Cycle's
package require vc::fossil::import::cvs::pass::breakacycle ; # Break' A'll Cycle's


# # ## ### ##### ######## ############# #####################
## Support for passes etc.

package require vc::fossil::import::cvs::option ; # Cmd line parsing & database
package require vc::fossil::import::cvs::pass   ; # Pass management
package require vc::tools::log                  ; # User feedback







<
<
<
<
<
>


>







32
33
34
35
36
37
38





39
40
41
42
43
44
45
46
47
48
49
# Note: cvs2svn's SortRevisionSummaryPass and SortSymbolSummaryPass
#       are not implemented by us. They are irrelevant due to our use
#       of a relational database proper for the persistent state,
#       allowing us to sort the data on the fly as we need it.

package require vc::fossil::import::cvs::pass::initcsets   ; # Init'ialize C'hange'Sets
package require vc::fossil::import::cvs::pass::breakrcycle ; # Break' R'evision Cycle's





package require vc::fossil::import::cvs::pass::rtopsort    ; # R'evision Top'ological Sort'
package require vc::fossil::import::cvs::pass::breakscycle ; # Break' S'ymbol Cycle's
package require vc::fossil::import::cvs::pass::breakacycle ; # Break' A'll Cycle's
package require vc::fossil::import::cvs::pass::atopsort    ; # A'll Top'ological Sort'

# # ## ### ##### ######## ############# #####################
## Support for passes etc.

package require vc::fossil::import::cvs::option ; # Cmd line parsing & database
package require vc::fossil::import::cvs::pass   ; # Pass management
package require vc::tools::log                  ; # User feedback

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

14
15
16
17
18
19
20

21
22

23
24
25
26
27
28
29
package ifneeded vc::fossil::import::cvs::pass              1.0 [list source [file join $dir c2f_pass.tcl]]
package ifneeded vc::fossil::import::cvs::pass::collar      1.0 [list source [file join $dir c2f_pcollar.tcl]]
package ifneeded vc::fossil::import::cvs::pass::collrev     1.0 [list source [file join $dir c2f_pcollrev.tcl]]
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::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::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]]







>


>







14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package ifneeded vc::fossil::import::cvs::pass              1.0 [list source [file join $dir c2f_pass.tcl]]
package ifneeded vc::fossil::import::cvs::pass::collar      1.0 [list source [file join $dir c2f_pcollar.tcl]]
package ifneeded vc::fossil::import::cvs::pass::collrev     1.0 [list source [file join $dir c2f_pcollrev.tcl]]
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::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]]