/
file.go
393 lines (368 loc) · 11.9 KB
/
file.go
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
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
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
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
package burndown
import (
"fmt"
"log"
"math"
"gopkg.in/src-d/hercules.v9/internal"
"gopkg.in/src-d/hercules.v9/internal/rbtree"
)
// Updater is the function which is called back on File.Update().
type Updater = func(currentTime, previousTime, delta int)
// File encapsulates a balanced binary tree to store line intervals and
// a cumulative mapping of values to the corresponding length counters. Users
// are not supposed to create File-s directly; instead, they should call NewFile().
// NewFileFromTree() is the special constructor which is useful in the tests.
//
// Len() returns the number of lines in File.
//
// Update() mutates File by introducing tree structural changes and updating the
// length mapping.
//
// Dump() writes the tree to a string and Validate() checks the tree integrity.
type File struct {
tree *rbtree.RBTree
updaters []Updater
}
// TreeEnd denotes the value of the last leaf in the tree.
const TreeEnd = math.MaxUint32
// TreeMaxBinPower is the binary power value which corresponds to the maximum day which
// can be stored in the tree.
const TreeMaxBinPower = 14
// TreeMergeMark is the special day which disables the status updates and is used in File.Merge().
const TreeMergeMark = (1 << TreeMaxBinPower) - 1
func (file *File) updateTime(currentTime, previousTime, delta int) {
if previousTime&TreeMergeMark == TreeMergeMark {
if currentTime == previousTime {
return
}
panic("previousTime cannot be TreeMergeMark")
}
if currentTime&TreeMergeMark == TreeMergeMark {
// merge mode - `delta` is negative and we have already applied it in a branch
return
}
for _, update := range file.updaters {
update(currentTime, previousTime, delta)
}
}
// NewFile initializes a new instance of File struct.
//
// time is the starting value of the first node;
//
// length is the starting length of the tree (the key of the second and the
// last node);
//
// updaters are the attached interval length mappings.
func NewFile(time int, length int, allocator *rbtree.Allocator, updaters ...Updater) *File {
file := &File{tree: rbtree.NewRBTree(allocator), updaters: updaters}
file.updateTime(time, time, length)
if time < 0 || time > math.MaxUint32 {
log.Panicf("time is out of allowed range: %d", time)
}
if length > math.MaxUint32 {
log.Panicf("length is out of allowed range: %d", length)
}
if length > 0 {
file.tree.Insert(rbtree.Item{Key: 0, Value: uint32(time)})
}
file.tree.Insert(rbtree.Item{Key: uint32(length), Value: TreeEnd})
return file
}
// NewFileFromTree is an alternative constructor for File which is used in tests.
// The resulting tree is validated with Validate() to ensure the initial integrity.
//
// keys is a slice with the starting tree keys.
//
// vals is a slice with the starting tree values. Must match the size of keys.
//
// updaters are the attached interval length mappings.
func NewFileFromTree(keys []int, vals []int, allocator *rbtree.Allocator, updaters ...Updater) *File {
file := &File{tree: rbtree.NewRBTree(allocator), updaters: updaters}
if len(keys) != len(vals) {
panic("keys and vals must be of equal length")
}
for i, key := range keys {
val := vals[i]
if key < 0 || key >= math.MaxUint32 {
log.Panicf("key is out of allowed range: [%d]=%d", i, key)
}
if val < 0 || val > math.MaxUint32 {
log.Panicf("val is out of allowed range: [%d]=%d", i, val)
}
file.tree.Insert(rbtree.Item{Key: uint32(key), Value: uint32(val)})
}
file.Validate()
return file
}
// CloneShallow copies the file. It performs a shallow copy of the tree: the allocator
// must be Clone()-d beforehand.
func (file *File) CloneShallow(allocator *rbtree.Allocator) *File {
return &File{tree: file.tree.CloneShallow(allocator), updaters: file.updaters}
}
// CloneDeep copies the file. It performs a deep copy of the tree.
func (file *File) CloneDeep(allocator *rbtree.Allocator) *File {
return &File{tree: file.tree.CloneDeep(allocator), updaters: file.updaters}
}
// Delete deallocates the file.
func (file *File) Delete() {
file.tree.Erase()
}
// Len returns the File's size - that is, the maximum key in the tree of line
// intervals.
func (file File) Len() int {
return int(file.tree.Max().Item().Key)
}
// Nodes returns the number of RBTree nodes in the file.
func (file File) Nodes() int {
return file.tree.Len()
}
// Update modifies the underlying tree to adapt to the specified line changes.
//
// time is the time when the requested changes are made. Sets the values of the
// inserted nodes.
//
// pos is the index of the line at which the changes are introduced.
//
// ins_length is the number of inserted lines after pos.
//
// del_length is the number of removed lines after pos. Deletions come before
// the insertions.
//
// The code inside this function is probably the most important one throughout
// the project. It is extensively covered with tests. If you find a bug, please
// add the corresponding case in file_test.go.
func (file *File) Update(time int, pos int, insLength int, delLength int) {
if time < 0 {
panic("time may not be negative")
}
if time >= math.MaxUint32 {
panic("time may not be >= MaxUint32")
}
if pos < 0 {
panic("attempt to insert/delete at a negative position")
}
if pos > math.MaxUint32 {
panic("pos may not be > MaxUint32")
}
if insLength < 0 || delLength < 0 {
panic("insLength and delLength must be non-negative")
}
if insLength|delLength == 0 {
return
}
tree := file.tree
if tree.Len() < 2 && tree.Min().Item().Key != 0 {
panic("invalid tree state")
}
if uint32(pos) > tree.Max().Item().Key {
panic(fmt.Sprintf("attempt to insert after the end of the file: %d < %d",
tree.Max().Item().Key, pos))
}
iter := tree.FindLE(uint32(pos))
origin := *iter.Item()
prevOrigin := origin
{
prevIter := iter.Prev()
if prevIter.Item() != nil {
prevOrigin = *prevIter.Item()
}
}
if insLength > 0 {
file.updateTime(time, time, insLength)
}
if delLength == 0 {
// simple case with insertions only
if origin.Key < uint32(pos) || (origin.Value == uint32(time) && (pos == 0 || uint32(pos) == origin.Key)) {
iter = iter.Next()
}
for ; !iter.Limit(); iter = iter.Next() {
iter.Item().Key += uint32(insLength)
}
if origin.Value != uint32(time) {
tree.Insert(rbtree.Item{Key: uint32(pos), Value: uint32(time)})
if origin.Key < uint32(pos) {
tree.Insert(rbtree.Item{Key: uint32(pos + insLength), Value: origin.Value})
}
}
return
}
// delete nodes
for true {
node := iter.Item()
nextIter := iter.Next()
if nextIter.Limit() {
if uint32(pos+delLength) > node.Key {
panic("attempt to delete after the end of the file")
}
break
}
delta := internal.Min(int(nextIter.Item().Key), pos+delLength) - internal.Max(int(node.Key), pos)
if delta == 0 && insLength == 0 && origin.Key == uint32(pos) && prevOrigin.Value == node.Value {
origin = *node
tree.DeleteWithIterator(iter)
iter = nextIter
}
if delta <= 0 {
break
}
file.updateTime(time, int(node.Value), -delta)
if node.Key >= uint32(pos) {
origin = *node
tree.DeleteWithIterator(iter)
}
iter = nextIter
}
// prepare for the keys update
var previous *rbtree.Item
if insLength > 0 && (origin.Value != uint32(time) || origin.Key == uint32(pos)) {
// insert our new interval
if iter.Item().Value == uint32(time) && int(iter.Item().Key)-delLength == pos {
prev := iter.Prev()
if prev.NegativeLimit() || prev.Item().Value != uint32(time) {
iter.Item().Key = uint32(pos)
} else {
tree.DeleteWithIterator(iter)
iter = prev
}
origin.Value = uint32(time) // cancels the insertion after applying the delta
} else {
_, iter = tree.Insert(rbtree.Item{Key: uint32(pos), Value: uint32(time)})
}
} else {
// rollback 1 position back, see "for true" deletion cycle ^
iter = iter.Prev()
previous = iter.Item()
}
// update the keys of all subsequent nodes
delta := insLength - delLength
if delta != 0 {
for iter = iter.Next(); !iter.Limit(); iter = iter.Next() {
// we do not need to re-balance the tree
iter.Item().Key = uint32(int(iter.Item().Key) + delta)
}
// have to adjust origin in case insLength == 0
if origin.Key > uint32(pos) {
origin.Key = uint32(int(origin.Key) + delta)
}
}
if insLength > 0 {
if origin.Value != uint32(time) {
tree.Insert(rbtree.Item{Key: uint32(pos + insLength), Value: origin.Value})
} else if pos == 0 {
// recover the beginning
tree.Insert(rbtree.Item{Key: uint32(pos), Value: uint32(time)})
}
} else if (uint32(pos) > origin.Key && previous != nil && previous.Value != origin.Value) ||
(uint32(pos) == origin.Key && origin.Value != prevOrigin.Value) ||
pos == 0 {
// continue the original interval
tree.Insert(rbtree.Item{Key: uint32(pos), Value: origin.Value})
}
}
// Merge combines several prepared File-s together.
func (file *File) Merge(day int, others ...*File) {
myself := file.flatten()
for _, other := range others {
if other == nil {
log.Panic("merging with a nil file")
}
lines := other.flatten()
if len(myself) != len(lines) {
log.Panicf("file corruption, lines number mismatch during merge %d != %d",
len(myself), len(lines))
}
for i, l := range myself {
ol := lines[i]
if ol&TreeMergeMark == TreeMergeMark {
continue
}
if l&TreeMergeMark == TreeMergeMark || l&TreeMergeMark > ol&TreeMergeMark {
// the line is merged in myself and exists in other
// OR the same line introduced in different branches
// consider the oldest version as the ground truth in that case
myself[i] = ol
continue
}
}
}
for i, l := range myself {
if l&TreeMergeMark == TreeMergeMark {
// original merge conflict resolution
myself[i] = day
file.updateTime(day, day, 1)
}
}
// now we need to reconstruct the tree from the discrete values
file.tree.Erase()
tree := rbtree.NewRBTree(file.tree.Allocator())
for i, v := range myself {
if i == 0 || v != myself[i-1] {
tree.Insert(rbtree.Item{Key: uint32(i), Value: uint32(v)})
}
}
tree.Insert(rbtree.Item{Key: uint32(len(myself)), Value: TreeEnd})
file.tree = tree
}
// Dump formats the underlying line interval tree into a string.
// Useful for error messages, panic()-s and debugging.
func (file File) Dump() string {
buffer := ""
file.ForEach(func(line, value int) {
buffer += fmt.Sprintf("%d %d\n", line, value)
})
return buffer
}
// Validate checks the underlying line interval tree integrity.
// The checks are as follows:
//
// 1. The minimum key must be 0 because the first line index is always 0.
//
// 2. The last node must carry TreeEnd value. This is the maintained invariant
// which marks the ending of the last line interval.
//
// 3. Node keys must monotonically increase and never duplicate.
func (file File) Validate() {
if file.tree.Min().Item().Key != 0 {
log.Panic("the tree must start with key 0")
}
if file.tree.Max().Item().Value != TreeEnd {
log.Panicf("the last value in the tree must be %d", TreeEnd)
}
prevKey := uint32(math.MaxUint32)
for iter := file.tree.Min(); !iter.Limit(); iter = iter.Next() {
node := iter.Item()
if node.Key == prevKey {
log.Panicf("duplicate tree key: %d", node.Key)
}
if node.Value == TreeMergeMark {
log.Panicf("unmerged lines left: %d", node.Key)
}
prevKey = node.Key
}
}
// ForEach visits each node in the underlying tree, in ascending key order.
func (file File) ForEach(callback func(line, value int)) {
for iter := file.tree.Min(); !iter.Limit(); iter = iter.Next() {
item := iter.Item()
key := int(item.Key)
var value int
if item.Value == math.MaxUint32 {
value = -1
} else {
value = int(item.Value)
}
callback(key, value)
}
}
// flatten represents the file as a slice of lines, each line's value being the corresponding day.
func (file *File) flatten() []int {
lines := make([]int, 0, file.Len())
val := uint32(math.MaxUint32)
for iter := file.tree.Min(); !iter.Limit(); iter = iter.Next() {
for i := uint32(len(lines)); i < iter.Item().Key; i++ {
lines = append(lines, int(val))
}
val = iter.Item().Value
}
return lines
}