Fossil

Check-in [95af789e]
Login

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

Overview
Comment:Oops. pass 5 is not complete. Missed the breaking of internal dependencies, this is done in this pass already. Extended pass _2_ and file revisions with code to save the branchchildren (possible dependencies), and pass 5 and changesets with the proper algorithm. From cvs2svn, works, do not truly like it, as it throws away and recomputes a lot of state after each split of a cset. Could update and reuse the state to perform all splits in one go. Will try that next, for now we have a working form in the code base.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:95af789e1fa51e6eac3e4ee857422844a935149e
User & Date: aku 2007-11-10 20:40:06
Context
2007-11-10
23:44
Rewrote the algorithm for breaking internal dependencies to my liking. The complex part handling multiple splits has moved from the pass code to the changeset class itself, reusing the state computed for the first split. The state is a bit more complex to allow for its incremental update after a break has been done. Factored major pieces into separate procedures to keep the highlevel code readable. Added lots of official log output to help debugging in case of trouble. check-in: 08ebab80 user: aku tags: trunk
20:40
Oops. pass 5 is not complete. Missed the breaking of internal dependencies, this is done in this pass already. Extended pass _2_ and file revisions with code to save the branchchildren (possible dependencies), and pass 5 and changesets with the proper algorithm. From cvs2svn, works, do not truly like it, as it throws away and recomputes a lot of state after each split of a cset. Could update and reuse the state to perform all splits in one go. Will try that next, for now we have a working form in the code base. check-in: 95af789e user: aku tags: trunk
07:46
Completed pass 5, computing the initial set of changesets. Defined persistent structure and filled out the long-existing placeholder class (project::rev). check-in: 5f7acef8 user: aku tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

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

363
364
365
366
367
368
369









370
371
372
373
374
375
376
	set cmd {
	    INSERT INTO revision ( rid,   fid,  rev,      lod, parent, child,  isdefault, dbparent, dbchild, bparent,  op,  date,    state,    mid,       coff,  clen)
	    VALUES               ($myid, $fid, $myrevnr, $lod, @P@,    @C@,   $idb,       @DP,      @DC,     @BP    , $op, $mydate, $mystate, $mymetaid, $coff, $clen);
	}

	state transaction {
	    state run [string map $map $cmd]









	}
	return
    }

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








>
>
>
>
>
>
>
>
>







363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
	set cmd {
	    INSERT INTO revision ( rid,   fid,  rev,      lod, parent, child,  isdefault, dbparent, dbchild, bparent,  op,  date,    state,    mid,       coff,  clen)
	    VALUES               ($myid, $fid, $myrevnr, $lod, @P@,    @C@,   $idb,       @DP,      @DC,     @BP    , $op, $mydate, $mystate, $mymetaid, $coff, $clen);
	}

	state transaction {
	    state run [string map $map $cmd]

	    # And the branch children as well, for pass 5.
	    foreach bc $mybranchchildren {
		set bcid [$bc id]
		state run {
		    INSERT INTO revisionbranchchildren (rid,   brid)
		    VALUES                             ($myid, $bcid);
		}
	    }
	}
	return
    }

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

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

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
	    state TEXT     NOT NULL,
	    mid   INTEGER  NOT NULL  REFERENCES meta,
	    coff  INTEGER  NOT NULL,
	    clen  INTEGER  NOT NULL,

	    UNIQUE (fid, rev) -- The DTN is unique within the revision's file.
	}

	state writing optype {
	    oid   INTEGER  NOT NULL  PRIMARY KEY,
	    name  TEXT     NOT NULL,
	    UNIQUE(name)
	}
	state run {
	    INSERT INTO optype VALUES (-1,'delete');  -- The opcode names are the
	    INSERT INTO optype VALUES ( 0,'nothing'); -- fixed pieces, see myopstate
	    INSERT INTO optype VALUES ( 1,'add');     -- in file::rev. myopcode is
	    INSERT INTO optype VALUES ( 2,'change');  -- loaded from this.
	}












	state writing tag {
	    tid  INTEGER  NOT NULL  PRIMARY KEY AUTOINCREMENT,
	    fid  INTEGER  NOT NULL  REFERENCES file,     -- File the item belongs to
	    lod  INTEGER            REFERENCES symbol,   -- Line of development (NULL => Trunk)
	    sid  INTEGER  NOT NULL  REFERENCES symbol,   -- Symbol capturing the tag

	    rev  INTEGER  NOT NULL  REFERENCES revision  -- The revision being tagged.







>











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







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
	    state TEXT     NOT NULL,
	    mid   INTEGER  NOT NULL  REFERENCES meta,
	    coff  INTEGER  NOT NULL,
	    clen  INTEGER  NOT NULL,

	    UNIQUE (fid, rev) -- The DTN is unique within the revision's file.
	}

	state writing optype {
	    oid   INTEGER  NOT NULL  PRIMARY KEY,
	    name  TEXT     NOT NULL,
	    UNIQUE(name)
	}
	state run {
	    INSERT INTO optype VALUES (-1,'delete');  -- The opcode names are the
	    INSERT INTO optype VALUES ( 0,'nothing'); -- fixed pieces, see myopstate
	    INSERT INTO optype VALUES ( 1,'add');     -- in file::rev. myopcode is
	    INSERT INTO optype VALUES ( 2,'change');  -- loaded from this.
	}

	state writing revisionbranchchildren {
	    -- The non-primary children of a revision, as reachable
	    -- through a branch symbol, are listed here. This is
	    -- needed by pass 5 to break internal dependencies in a
	    -- changeset.

	    rid   INTEGER  NOT NULL  REFERENCES revision,
	    brid  INTEGER  NOT NULL  REFERENCES revision,
	    UNIQUE(rid,brid)
	}

	state writing tag {
	    tid  INTEGER  NOT NULL  PRIMARY KEY AUTOINCREMENT,
	    fid  INTEGER  NOT NULL  REFERENCES file,     -- File the item belongs to
	    lod  INTEGER            REFERENCES symbol,   -- Line of development (NULL => Trunk)
	    sid  INTEGER  NOT NULL  REFERENCES symbol,   -- Symbol capturing the tag

	    rev  INTEGER  NOT NULL  REFERENCES revision  -- The revision being tagged.

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

43
44
45
46
47
48
49

50
51
52
53
54
55
56
...
107
108
109
110
111
112
113
114

115
116
117
118
119
120
121
122
123
...
266
267
268
269
270
271
272
273














































274
275

276
277
278
279
280
281
282
283
284
285
286
287
288

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

	state reading meta
	state reading revision

	state reading branch
	state reading tag
	state reading symbol

	# Data per changeset, namely the project it belongs to, how it
	# was induced (revision or symbol), plus reference to the
	# primary entry causing it (meta entry or symbol). An adjunct
................................................................................

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

	set csets {}
	state transaction {
	    CreateRevisionChangesets csets ; # Group file revisions into csets.

	    CreateSymbolChangesets   csets ; # Create csets for tags and branches.
	    PersistTheChangesets    $csets
	}
	return
    }

    typemethod discard {} {
	# Pass manager interface. Executed for all passes after the
	# run passes, to remove all data of this pass from the state,
................................................................................
	    set  p [repository projectof $lastproject]
	    lappend csets [project::rev %AUTO% $p sym $lastsymbol $revisions]
	}

	log write 4 initcsets "Created [nsp $n {symbol changeset}]"
	return
    }















































    proc PersistTheChangesets {csets} {
	log write 3 initcsets {Saving the created changesets to the persistent state}


	foreach cset $csets {
	    $cset persist
	}

	log write 4 initcsets {Ok.}
	return
    }

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

    pragma -hasinstances   no ; # singleton







>







 







|
>
|
|







 








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

<
>





|







43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
...
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
...
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
305
306
307
308
309
310
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

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

	state reading meta
	state reading revision
	state reading revisionbranchchildren
	state reading branch
	state reading tag
	state reading symbol

	# Data per changeset, namely the project it belongs to, how it
	# was induced (revision or symbol), plus reference to the
	# primary entry causing it (meta entry or symbol). An adjunct
................................................................................

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

	set csets {}
	state transaction {
	    CreateRevisionChangesets  csets ; # Group file revisions into csets.
	    BreakInternalDependencies csets ; # Split the csets based on internal conflicts.
	    CreateSymbolChangesets    csets ; # Create csets for tags and branches.
	    PersistTheChangesets     $csets
	}
	return
    }

    typemethod discard {} {
	# Pass manager interface. Executed for all passes after the
	# run passes, to remove all data of this pass from the state,
................................................................................
	    set  p [repository projectof $lastproject]
	    lappend csets [project::rev %AUTO% $p sym $lastsymbol $revisions]
	}

	log write 4 initcsets "Created [nsp $n {symbol changeset}]"
	return
    }

    proc BreakInternalDependencies {cv} {
	upvar 1 $cv csets

	# This code operates on the revision changesets created by
	# 'CreateRevisionChangesets'. As such it has to follow after
	# it, before the symbol changesets are made. The changesets
	# are inspected for internal conflicts and any such are broken
	# by splitting the problematic changeset into multiple
	# fragments. The results are changesets which have no internal
	# dependencies, only external ones.

	log write 3 initcsets {Break internal dependencies}
	set n 0

	foreach cset $csets {
	    # The main method for splitting does only one split, which
	    # may not be enough. The code here iterates until no more
	    # splits can be performed. An iterative algorithm was
	    # chosen over a recursive one to prevent running into
	    # stack limits.

	    set tosplit [list $cset]
	    set at 0
	    while {$at < [llength $tosplit]} {
		# Note here how we are __not__ advancing in the list
		#      when we were able to break the current
		#      changeset into two pieces, causing the loop to
		#      immediately check the first of the two pieces
		#      again for further break possibilities. The
		#      other piece is added at the end, thus processed
		#      later.
		while {[[lindex $tosplit $at] breakinternaldependencies tosplit]} {}
		incr at
	    }

	    # At last the generated fragments are added to the main
	    # list of changesets. The first element is skipped as it
	    # is already in the list.
	    foreach cset [lrange $tosplit 1 end] { lappend csets $cset ; incr n }
	}

	log write 4 initcsets "Created [nsp $n {additional revision changeset}]"
	log write 4 initcsets Ok.
	return
    }

    proc PersistTheChangesets {csets} {

	log write 3 initcsets "Saving [nsp [llength $csets] {initial changeset}] to the persistent state"

	foreach cset $csets {
	    $cset persist
	}

	log write 4 initcsets Ok.
	return
    }

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

    pragma -hasinstances   no ; # singleton

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

14
15
16
17
18
19
20

21
22
23
24
25
26
27
..
31
32
33
34
35
36
37




































































































































































38
39
40
41
42
43
44
..
90
91
92
93
94
95
96


97
98
99
100
101
102
103
104
## in pass 5, which creates the initial set covering the repository.

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

package require Tcl 8.4                               ; # Required runtime.
package require snit                                  ; # OO system.

package require vc::fossil::import::cvs::state        ; # State storage.

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

snit::type ::vc::fossil::import::cvs::project::rev {
    # # ## ### ##### ######## #############
................................................................................
	set myid        [incr mycounter]
	set myproject   $project
	set mytype      $cstype	  
	set mysrcid	$srcid	  
	set myrevisions $revisions
	return
    }





































































































































































    method persist {} {
	set tid $mycstype($mytype)
	set pid [$myproject id]
	set pos 0

	state transaction {
................................................................................
    # # ## ### ##### ######## #############
}

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


    }
}

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

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







>







 







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







 







>
>








14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
..
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
...
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
## in pass 5, which creates the initial set covering the repository.

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

package require Tcl 8.4                               ; # Required runtime.
package require snit                                  ; # OO system.
package require vc::tools::log                        ; # User feedback.
package require vc::fossil::import::cvs::state        ; # State storage.

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

snit::type ::vc::fossil::import::cvs::project::rev {
    # # ## ### ##### ######## #############
................................................................................
	set myid        [incr mycounter]
	set myproject   $project
	set mytype      $cstype	  
	set mysrcid	$srcid	  
	set myrevisions $revisions
	return
    }

    method id {} { return $myid }

    method breakinternaldependencies {cv} {
	upvar 2 $cv csets ; # simple-dispatch!

	# 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
	# are added to the list of all changesets.

	# Actually at most one split is performed, resulting in at
	# most one additional fragment. It is the caller's
	# responsibility to spli the resulting fragments further.

	# The code checks only sucessor dependencies, automatically
	# covering the predecessor dependencies as well (A sucessor
	# dependency a -> b is 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 {}

	set theset ('[join $myrevisions {','}]')

	foreach {rid child} [state run "
	    SELECT R.rid, R.child
	    FROM   revision R
	    WHERE  R.rid   IN $theset
	    AND    R.child IS NOT NULL
	    AND    R.child IN $theset
    UNION
	    SELECT R.rid, R.dbchild
	    FROM   revision R
	    WHERE  R.rid   IN $theset
	    AND    R.dbchild IS NOT NULL
	    AND    R.dbchild IN $theset
    UNION
	    SELECT R.rid, B.brid
	    FROM   revision R, revisionbranchchildren B
	    WHERE  R.rid   IN $theset
	    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
	}

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

	# 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
	# determine the best position for the break, by trying to
	# break as many dependencies as possible in one go.

	# First we create a map of positions to make it easier to
	# determine whether a dependency cross a particular index.

	array set pos {}
	array set crossing {}
	set n 0
	foreach rev $myrevisions { 
	    set pos($rev) $n
	    set crossing($n) 0
	    incr n
	}

	# Secondly we count the crossings per position, by iterating
	# over the recorded internal dependencies.

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

	    # Note: If the timestamps are badly out of order it is
	    #       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.

	    if {$start > $end} {
		while {$end < $start} { incr crossing($end)   ; incr end }
	    } else {
		while {$start < $end} { incr crossing($start) ; incr start }
	    }
	}

	# Now we can determine the best break location. First we look
	# for the locations with the maximal number of crossings. If
	# there are several we look for the shortest time interval
	# among them. If we still have multiple possibilities after
	# that we select the smallest index among these.

	set max -1
	set best {}

	foreach key [array names crossing] {
	    set now $crossing($key)
	    if {$now > $max} {
		set max $now
		set best $key
		continue
	    } elseif {$now == $max} {
		lappend best $key
	    }
	}

	if {[llength $best] > 1} {
	    set min -1
	    set newbest {}
	    foreach at $best {
		set rat   [lindex $myrevisions $at] ; incr at
		set rnext [lindex $myrevisions $at] ; incr at -1
		set tat   [lindex [state run {SELECT R.date FROM revision R WHERE R.rid = $rat  }] 0]
		set tnext [lindex [state run {SELECT R.date FROM revision R WHERE R.rid = $rnext}] 0]
		set delta [expr {$tnext - $tat}]
		if {($min < 0) || ($delta < $min)} {
		    set min $delta
		    set newbest $at
		} elseif {$delta == $min} {
		    lappend newbest $at
		}
	    }
	    set best $newbest
	}

	if {[llength $best] > 1} {
	    set best [lindex [lsort -integer -increasing $best] 0]
	}

	# Now we can split off a fragment.

	set bnext $best ; incr bnext
	set revbefore [lrange $myrevisions 0 $best]
	set revafter  [lrange $myrevisions $bnext end]

	if {![llength $revbefore]} {
	    trouble internal "Tried to split off a zero-length fragment at the beginning"
	}
	if {![llength $revafter]} {
	    trouble internal "Tried to split off a zero-length fragment at the end"
	}

	lappend csets [set new [$type %AUTO% $myproject $mytype $mysrcid $revafter]]
	set myrevisions $revbefore

	log write 4 csets "Breaking <$myid> @$best, making <[$new id]>, cutting $crossing($best)"

	#puts "\tKeeping   <$revbefore>"
	#puts "\tSplit off <$revafter>"

	return 1
    }

    method persist {} {
	set tid $mycstype($mytype)
	set pid [$myproject id]
	set pos 0

	state transaction {
................................................................................
    # # ## ### ##### ######## #############
}

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

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

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