Fossil SCM

CVS import. First, fixed sig::next regarding two things. One, we have to take the root version of a file into account as a possible predecessor. Two, a missing changed file may be misclassified and actually be added instead. Second, modified the search for a root changeset of a branch. We now try the existing regular intersection first for exactness, and in case of failure we fall back to a voting scheme to locate the most acceptable aka non-conflicting changeset.

aku 2007-09-27 04:44 trunk
Commit 7a64b9e738eea1f6e84ef48acecf58f680495aa6
Parent f6f5c902e60fdbf…
3 files changed +1 -1 +11 -1 +97 -20
~ tools/lib/cvs.tcl ~ tools/lib/cvs_branch.tcl ~ tools/lib/cvs_sig.tcl
M tools/lib/cvs.tcl
+1 -1
--- tools/lib/cvs.tcl
+++ tools/lib/cvs.tcl
@@ -355,11 +355,11 @@
355355
 write 4 cvs "Branch base $base"
356356
357357
 ::foreach {tag rootsig} [branch::find [csets::get $base]] break
358358
359359
 write 4 cvs "Branch tag $tag"
360
- write 4 cvs "Root sig $rootsig"
360
+ write 5 cvs "Root sig $rootsig"
361361
362362
 set root [sig::find $base $rootsig]
363363
364364
 write 4 cvs "Branch root $root"
365365
366366
--- tools/lib/cvs.tcl
+++ tools/lib/cvs.tcl
@@ -355,11 +355,11 @@
355 write 4 cvs "Branch base $base"
356
357 ::foreach {tag rootsig} [branch::find [csets::get $base]] break
358
359 write 4 cvs "Branch tag $tag"
360 write 4 cvs "Root sig $rootsig"
361
362 set root [sig::find $base $rootsig]
363
364 write 4 cvs "Branch root $root"
365
366
--- tools/lib/cvs.tcl
+++ tools/lib/cvs.tcl
@@ -355,11 +355,11 @@
355 write 4 cvs "Branch base $base"
356
357 ::foreach {tag rootsig} [branch::find [csets::get $base]] break
358
359 write 4 cvs "Branch tag $tag"
360 write 5 cvs "Root sig $rootsig"
361
362 set root [sig::find $base $rootsig]
363
364 write 4 cvs "Branch root $root"
365
366
M tools/lib/cvs_branch.tcl
+11 -1
--- tools/lib/cvs_branch.tcl
+++ tools/lib/cvs_branch.tcl
@@ -207,10 +207,20 @@
207207
 return 0
208208
 } else {
209209
 return 1
210210
 }
211211
 }
212
+
213
+proc ::vc::cvs::ws::branch::rootSuccessor {ra rb} {
214
+ # a root-successor-of b ? (<=> b root version of a ?)
215
+
216
+ if {$rb eq [revroot $ra]} {
217
+ return 1
218
+ } else {
219
+ return 0
220
+ }
221
+}
212222
213223
 proc ::vc::cvs::ws::branch::Signatures {bv deflist} {
214224
 upvar 1 $bv bdata
215225
 # Sort branch data by symbolic name for the upcoming checks, and
216226
 # generate file revision signatures.
@@ -250,11 +260,11 @@
250260
251261
252262
 namespace eval ::vc::cvs::ws::branch {
253263
 variable bra {}
254264
255
- namespace export def find successor revroot has
265
+ namespace export def find successor rootSuccessor revroot has
256266
 }
257267
258268
 package provide vc::cvs::ws::branch 1.0
259269
 return
260270
261271
--- tools/lib/cvs_branch.tcl
+++ tools/lib/cvs_branch.tcl
@@ -207,10 +207,20 @@
207 return 0
208 } else {
209 return 1
210 }
211 }
 
 
 
 
 
 
 
 
 
 
212
213 proc ::vc::cvs::ws::branch::Signatures {bv deflist} {
214 upvar 1 $bv bdata
215 # Sort branch data by symbolic name for the upcoming checks, and
216 # generate file revision signatures.
@@ -250,11 +260,11 @@
250
251
252 namespace eval ::vc::cvs::ws::branch {
253 variable bra {}
254
255 namespace export def find successor revroot has
256 }
257
258 package provide vc::cvs::ws::branch 1.0
259 return
260
261
--- tools/lib/cvs_branch.tcl
+++ tools/lib/cvs_branch.tcl
@@ -207,10 +207,20 @@
207 return 0
208 } else {
209 return 1
210 }
211 }
212
213 proc ::vc::cvs::ws::branch::rootSuccessor {ra rb} {
214 # a root-successor-of b ? (<=> b root version of a ?)
215
216 if {$rb eq [revroot $ra]} {
217 return 1
218 } else {
219 return 0
220 }
221 }
222
223 proc ::vc::cvs::ws::branch::Signatures {bv deflist} {
224 upvar 1 $bv bdata
225 # Sort branch data by symbolic name for the upcoming checks, and
226 # generate file revision signatures.
@@ -250,11 +260,11 @@
260
261
262 namespace eval ::vc::cvs::ws::branch {
263 variable bra {}
264
265 namespace export def find successor rootSuccessor revroot has
266 }
267
268 package provide vc::cvs::ws::branch 1.0
269 return
270
271
M tools/lib/cvs_sig.tcl
+97 -20
--- tools/lib/cvs_sig.tcl
+++ tools/lib/cvs_sig.tcl
@@ -27,19 +27,36 @@
2727
2828
 proc ::vc::cvs::ws::sig::next {id added changed removed tag ts} {
2929
 variable sig
3030
 array set rev $sig($id)
3131
32
+ #puts sig::next/$ts
3233
 foreach {f r} [concat $changed $removed] {
33
- if {![info exists rev($f)] || ![branch::successor $r $rev($f)]} {
34
+ if {![info exists rev($f)]} {
35
+
36
+ # A file missing in the candidate parent changeset is
37
+ # _not_ a reason to reject it, at least not immediately.
38
+ # The code generating the timeline entries has only
39
+ # partial information and is prone to misclassify files
40
+ # added to branches as changed instead of added. Thus we
41
+ # move this file to the list of added things and check it
42
+ # again as part of that, see below.
43
+
44
+ lappend added $f $r
45
+ continue
46
+ }
47
+ if {[branch::rootSuccessor $r $rev($f)]} continue
48
+ if {![branch::successor $r $rev($f)]} {
49
+ #puts "not-successor($r of $rev($f))"
3450
 return 0
3551
 }
3652
 }
3753
3854
 if {[llength $added]} {
3955
 # Check that added files belong to the branch too!
4056
 if {$tag ne [branch::has $ts $added]} {
57
+ #puts "not-added-into-same-branch"
4158
 return 0
4259
 }
4360
 }
4461
 return 1
4562
 }
@@ -80,48 +97,108 @@
8097
 return $res
8198
 }
8299
83100
 proc ::vc::cvs::ws::sig::Find {sig} {
84101
 # Locate all changesets which contain the given signature.
102
+
103
+ # First we try to the exact changeset, by intersecting the
104
+ # live-intervals for all file revisions found in the
105
+ # signature. This however may fail, as CVS is able to contain
106
+ # a-causal branch definitions.
107
+
108
+ # Example: sqlite, branch "gdbm-branch".
109
+
110
+ # File 'db.c', branch 1.6.2, root 1.6, entered on Jan 31, 2001.
111
+ # Then 'dbbegdbm.c', 1.1.2, root 1.1, entered on Oct 19, 2000.
112
+
113
+ # More pertinent, revision 1.2 was entered Jan 13, 2001,
114
+ # i.e. existed before Jan 31, before the branchwas actually
115
+ # made. Thus it is unclear why 1.1 is in the branch instead.
116
+
117
+ # An alternative complementary question would be how db.c 1.6
118
+ # ended up in a branch tag created before Jan 13, when this
119
+ # revision did not exist yet.
120
+
121
+ # So, CVS repositories can be a-causal when it comes to branches,
122
+ # at least in the details. Therefore while try for an exact result
123
+ # first we do not fail if that fails, but use a voting scheme as
124
+ # fallback which answers the question about which changeset is
125
+ # acceptable to the most file revisions in the signature.
126
+
127
+ # Note that multiple changesets are ok at this level and are
128
+ # simply returned.
129
+
130
+ set res [Intersect $sig]
131
+ puts Exact=($res)
132
+
133
+ if {[llength $res]} { return $res }
134
+
135
+ set res [Vote $sig]
136
+ puts Vote=($res)
137
+
138
+ return $res
139
+}
140
+
141
+
142
+proc ::vc::cvs::ws::sig::Intersect {sig} {
85143
 variable csl
86144
87145
 set res {}
88146
 set first 1
89147
 foreach {f r} $sig {
90148
 #puts $f/$r?
91149
 # Unknown file not used anywhere
92150
 if {![info exists csl($f,$r)]} {return {}}
93
- puts $f/$r\t=\t($csl($f,$r))*($res)/$first
151
+ #puts $f/$r\t=\t($csl($f,$r))*($res)/$first
94152
95153
 if {$first} {
96154
 set res $csl($f,$r)
97155
 set first 0
98156
 #puts F($res)
99157
 } else {
100
- set new [struct::set intersect $res $csl($f,$r)]
101
- set rv $r
102
- while {![llength $new]} {
103
- # Assume that the problem file was added and as such
104
- # does not exist yet at the root revision. However its
105
- # root should exist, and some point.
106
-
107
- set rv [branch::revroot $rv]
108
- if {$rv eq ""} {
109
- puts BREAK/\t($f\ $r)
110
- exit
111
- }
112
- if {![info exists csl($f,$rv)]} {return {}}
113
- #puts $f/$r\t=\t($csl($f,$rv))
114
- set new [struct::set intersect $res $csl($f,$rv)]
115
- }
116
- set res $new
158
+ set res [struct::set intersect $res $csl($f,$r)]
117159
 #puts R($res)
118
- #if {![llength $res]} {return {}}
160
+ if {![llength $res]} {return {}}
119161
 }
120162
 }
121163
 return $res
122164
 }
165
+
166
+
167
+proc ::vc::cvs::ws::sig::Vote {sig} {
168
+ variable csl
169
+
170
+ # I. Accumulate votes.
171
+ array set v {}
172
+ foreach {f r} $sig {
173
+ # Unknown revisions do not vote.
174
+ if {![info exists csl($f,$r)]} continue
175
+ foreach c $csl($f,$r) {
176
+ if {[info exists v($c)]} {
177
+ incr v($c)
178
+ } else {
179
+ set v($c) 1
180
+ }
181
+ }
182
+ }
183
+
184
+ # Invert index for easier finding the max, compute the max at the
185
+ # same time.
186
+ array set tally {}
187
+ set max -1
188
+ foreach {c n} [array get v] {
189
+ lappend tally($n) $c
190
+ if {$n > $max} {set max $n}
191
+ }
192
+
193
+ #parray tally
194
+ puts Max=$max
195
+
196
+ # Return the changesets having the most votes.
197
+ return $tally($max)
198
+}
199
+
123200
124201
 proc ::vc::cvs::ws::sig::DictSort {dict} {
125202
 array set a $dict
126203
 set r {}
127204
 foreach k [lsort [array names a]] {
128205
--- tools/lib/cvs_sig.tcl
+++ tools/lib/cvs_sig.tcl
@@ -27,19 +27,36 @@
27
28 proc ::vc::cvs::ws::sig::next {id added changed removed tag ts} {
29 variable sig
30 array set rev $sig($id)
31
 
32 foreach {f r} [concat $changed $removed] {
33 if {![info exists rev($f)] || ![branch::successor $r $rev($f)]} {
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
34 return 0
35 }
36 }
37
38 if {[llength $added]} {
39 # Check that added files belong to the branch too!
40 if {$tag ne [branch::has $ts $added]} {
 
41 return 0
42 }
43 }
44 return 1
45 }
@@ -80,48 +97,108 @@
80 return $res
81 }
82
83 proc ::vc::cvs::ws::sig::Find {sig} {
84 # Locate all changesets which contain the given signature.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
85 variable csl
86
87 set res {}
88 set first 1
89 foreach {f r} $sig {
90 #puts $f/$r?
91 # Unknown file not used anywhere
92 if {![info exists csl($f,$r)]} {return {}}
93 puts $f/$r\t=\t($csl($f,$r))*($res)/$first
94
95 if {$first} {
96 set res $csl($f,$r)
97 set first 0
98 #puts F($res)
99 } else {
100 set new [struct::set intersect $res $csl($f,$r)]
101 set rv $r
102 while {![llength $new]} {
103 # Assume that the problem file was added and as such
104 # does not exist yet at the root revision. However its
105 # root should exist, and some point.
106
107 set rv [branch::revroot $rv]
108 if {$rv eq ""} {
109 puts BREAK/\t($f\ $r)
110 exit
111 }
112 if {![info exists csl($f,$rv)]} {return {}}
113 #puts $f/$r\t=\t($csl($f,$rv))
114 set new [struct::set intersect $res $csl($f,$rv)]
115 }
116 set res $new
117 #puts R($res)
118 #if {![llength $res]} {return {}}
119 }
120 }
121 return $res
122 }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
123
124 proc ::vc::cvs::ws::sig::DictSort {dict} {
125 array set a $dict
126 set r {}
127 foreach k [lsort [array names a]] {
128
--- tools/lib/cvs_sig.tcl
+++ tools/lib/cvs_sig.tcl
@@ -27,19 +27,36 @@
27
28 proc ::vc::cvs::ws::sig::next {id added changed removed tag ts} {
29 variable sig
30 array set rev $sig($id)
31
32 #puts sig::next/$ts
33 foreach {f r} [concat $changed $removed] {
34 if {![info exists rev($f)]} {
35
36 # A file missing in the candidate parent changeset is
37 # _not_ a reason to reject it, at least not immediately.
38 # The code generating the timeline entries has only
39 # partial information and is prone to misclassify files
40 # added to branches as changed instead of added. Thus we
41 # move this file to the list of added things and check it
42 # again as part of that, see below.
43
44 lappend added $f $r
45 continue
46 }
47 if {[branch::rootSuccessor $r $rev($f)]} continue
48 if {![branch::successor $r $rev($f)]} {
49 #puts "not-successor($r of $rev($f))"
50 return 0
51 }
52 }
53
54 if {[llength $added]} {
55 # Check that added files belong to the branch too!
56 if {$tag ne [branch::has $ts $added]} {
57 #puts "not-added-into-same-branch"
58 return 0
59 }
60 }
61 return 1
62 }
@@ -80,48 +97,108 @@
97 return $res
98 }
99
100 proc ::vc::cvs::ws::sig::Find {sig} {
101 # Locate all changesets which contain the given signature.
102
103 # First we try to the exact changeset, by intersecting the
104 # live-intervals for all file revisions found in the
105 # signature. This however may fail, as CVS is able to contain
106 # a-causal branch definitions.
107
108 # Example: sqlite, branch "gdbm-branch".
109
110 # File 'db.c', branch 1.6.2, root 1.6, entered on Jan 31, 2001.
111 # Then 'dbbegdbm.c', 1.1.2, root 1.1, entered on Oct 19, 2000.
112
113 # More pertinent, revision 1.2 was entered Jan 13, 2001,
114 # i.e. existed before Jan 31, before the branchwas actually
115 # made. Thus it is unclear why 1.1 is in the branch instead.
116
117 # An alternative complementary question would be how db.c 1.6
118 # ended up in a branch tag created before Jan 13, when this
119 # revision did not exist yet.
120
121 # So, CVS repositories can be a-causal when it comes to branches,
122 # at least in the details. Therefore while try for an exact result
123 # first we do not fail if that fails, but use a voting scheme as
124 # fallback which answers the question about which changeset is
125 # acceptable to the most file revisions in the signature.
126
127 # Note that multiple changesets are ok at this level and are
128 # simply returned.
129
130 set res [Intersect $sig]
131 puts Exact=($res)
132
133 if {[llength $res]} { return $res }
134
135 set res [Vote $sig]
136 puts Vote=($res)
137
138 return $res
139 }
140
141
142 proc ::vc::cvs::ws::sig::Intersect {sig} {
143 variable csl
144
145 set res {}
146 set first 1
147 foreach {f r} $sig {
148 #puts $f/$r?
149 # Unknown file not used anywhere
150 if {![info exists csl($f,$r)]} {return {}}
151 #puts $f/$r\t=\t($csl($f,$r))*($res)/$first
152
153 if {$first} {
154 set res $csl($f,$r)
155 set first 0
156 #puts F($res)
157 } else {
158 set res [struct::set intersect $res $csl($f,$r)]
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
159 #puts R($res)
160 if {![llength $res]} {return {}}
161 }
162 }
163 return $res
164 }
165
166
167 proc ::vc::cvs::ws::sig::Vote {sig} {
168 variable csl
169
170 # I. Accumulate votes.
171 array set v {}
172 foreach {f r} $sig {
173 # Unknown revisions do not vote.
174 if {![info exists csl($f,$r)]} continue
175 foreach c $csl($f,$r) {
176 if {[info exists v($c)]} {
177 incr v($c)
178 } else {
179 set v($c) 1
180 }
181 }
182 }
183
184 # Invert index for easier finding the max, compute the max at the
185 # same time.
186 array set tally {}
187 set max -1
188 foreach {c n} [array get v] {
189 lappend tally($n) $c
190 if {$n > $max} {set max $n}
191 }
192
193 #parray tally
194 puts Max=$max
195
196 # Return the changesets having the most votes.
197 return $tally($max)
198 }
199
200
201 proc ::vc::cvs::ws::sig::DictSort {dict} {
202 array set a $dict
203 set r {}
204 foreach k [lsort [array names a]] {
205

Keyboard Shortcuts

Open search /
Next entry (timeline) j
Previous entry (timeline) k
Open focused entry Enter
Show this help ?
Toggle theme Top nav button