file.go 9.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330
  1. package burndown
  2. import (
  3. "fmt"
  4. "log"
  5. "gopkg.in/src-d/hercules.v4/internal"
  6. "gopkg.in/src-d/hercules.v4/internal/rbtree"
  7. )
  8. // Updater is the function which is called back on File.Update().
  9. type Updater = func(currentTime, previousTime, delta int)
  10. // File encapsulates a balanced binary tree to store line intervals and
  11. // a cumulative mapping of values to the corresponding length counters. Users
  12. // are not supposed to create File-s directly; instead, they should call NewFile().
  13. // NewFileFromTree() is the special constructor which is useful in the tests.
  14. //
  15. // Len() returns the number of lines in File.
  16. //
  17. // Update() mutates File by introducing tree structural changes and updating the
  18. // length mapping.
  19. //
  20. // Dump() writes the tree to a string and Validate() checks the tree integrity.
  21. type File struct {
  22. tree *rbtree.RBTree
  23. updaters []Updater
  24. }
  25. // TreeEnd denotes the value of the last leaf in the tree.
  26. const TreeEnd = -1
  27. // TreeMaxBinPower is the binary power value which corresponds to the maximum day which
  28. // can be stored in the tree.
  29. const TreeMaxBinPower = 14
  30. // TreeMergeMark is the special day which disables the status updates and is used in File.Merge().
  31. const TreeMergeMark = (1 << TreeMaxBinPower) - 1
  32. func (file *File) updateTime(currentTime, previousTime, delta int) {
  33. if currentTime & TreeMergeMark == TreeMergeMark {
  34. // merge mode
  35. return
  36. }
  37. if previousTime & TreeMergeMark == TreeMergeMark {
  38. previousTime = currentTime
  39. }
  40. for _, update := range file.updaters {
  41. update(currentTime, previousTime, delta)
  42. }
  43. }
  44. // NewFile initializes a new instance of File struct.
  45. //
  46. // time is the starting value of the first node;
  47. //
  48. // length is the starting length of the tree (the key of the second and the
  49. // last node);
  50. //
  51. // updaters are the attached interval length mappings.
  52. func NewFile(time int, length int, updaters ...Updater) *File {
  53. file := &File{tree: new(rbtree.RBTree), updaters: updaters}
  54. file.updateTime(time, time, length)
  55. if length > 0 {
  56. file.tree.Insert(rbtree.Item{Key: 0, Value: time})
  57. }
  58. file.tree.Insert(rbtree.Item{Key: length, Value: TreeEnd})
  59. return file
  60. }
  61. // NewFileFromTree is an alternative constructor for File which is used in tests.
  62. // The resulting tree is validated with Validate() to ensure the initial integrity.
  63. //
  64. // keys is a slice with the starting tree keys.
  65. //
  66. // vals is a slice with the starting tree values. Must match the size of keys.
  67. //
  68. // updaters are the attached interval length mappings.
  69. func NewFileFromTree(keys []int, vals []int, updaters ...Updater) *File {
  70. file := &File{tree: new(rbtree.RBTree), updaters: updaters}
  71. if len(keys) != len(vals) {
  72. panic("keys and vals must be of equal length")
  73. }
  74. for i := 0; i < len(keys); i++ {
  75. file.tree.Insert(rbtree.Item{Key: keys[i], Value: vals[i]})
  76. }
  77. file.Validate()
  78. return file
  79. }
  80. // Clone copies the file. It performs a deep copy of the tree;
  81. // depending on `clearStatuses` the original updaters are removed or not.
  82. // Any new `updaters` are appended.
  83. func (file *File) Clone(clearStatuses bool, updaters ...Updater) *File {
  84. clone := &File{tree: file.tree.Clone(), updaters: file.updaters}
  85. if clearStatuses {
  86. clone.updaters = []Updater{}
  87. }
  88. for _, updater := range updaters {
  89. clone.updaters = append(clone.updaters, updater)
  90. }
  91. return clone
  92. }
  93. // Len returns the File's size - that is, the maximum key in the tree of line
  94. // intervals.
  95. func (file *File) Len() int {
  96. return file.tree.Max().Item().Key
  97. }
  98. // Update modifies the underlying tree to adapt to the specified line changes.
  99. //
  100. // time is the time when the requested changes are made. Sets the values of the
  101. // inserted nodes.
  102. //
  103. // pos is the index of the line at which the changes are introduced.
  104. //
  105. // ins_length is the number of inserted lines after pos.
  106. //
  107. // del_length is the number of removed lines after pos. Deletions come before
  108. // the insertions.
  109. //
  110. // The code inside this function is probably the most important one throughout
  111. // the project. It is extensively covered with tests. If you find a bug, please
  112. // add the corresponding case in file_test.go.
  113. func (file *File) Update(time int, pos int, insLength int, delLength int) {
  114. if time < 0 {
  115. panic("time may not be negative")
  116. }
  117. if pos < 0 {
  118. panic("attempt to insert/delete at a negative position")
  119. }
  120. if insLength < 0 || delLength < 0 {
  121. panic("insLength and delLength must be non-negative")
  122. }
  123. if insLength|delLength == 0 {
  124. return
  125. }
  126. tree := file.tree
  127. if tree.Len() < 2 && tree.Min().Item().Key != 0 {
  128. panic("invalid tree state")
  129. }
  130. if pos > tree.Max().Item().Key {
  131. panic(fmt.Sprintf("attempt to insert after the end of the file: %d < %d",
  132. tree.Max().Item().Key, pos))
  133. }
  134. iter := tree.FindLE(pos)
  135. origin := *iter.Item()
  136. file.updateTime(time, time, insLength)
  137. if delLength == 0 {
  138. // simple case with insertions only
  139. if origin.Key < pos || (origin.Value == time && pos == 0) {
  140. iter = iter.Next()
  141. }
  142. for ; !iter.Limit(); iter = iter.Next() {
  143. iter.Item().Key += insLength
  144. }
  145. if origin.Value != time {
  146. tree.Insert(rbtree.Item{Key: pos, Value: time})
  147. if origin.Key < pos {
  148. tree.Insert(rbtree.Item{Key: pos + insLength, Value: origin.Value})
  149. }
  150. }
  151. return
  152. }
  153. // delete nodes
  154. for true {
  155. node := iter.Item()
  156. nextIter := iter.Next()
  157. if nextIter.Limit() {
  158. if pos+delLength > node.Key {
  159. panic("attempt to delete after the end of the file")
  160. }
  161. break
  162. }
  163. delta := internal.Min(nextIter.Item().Key, pos+delLength) - internal.Max(node.Key, pos)
  164. if delta <= 0 {
  165. break
  166. }
  167. file.updateTime(time, node.Value, -delta)
  168. if node.Key >= pos {
  169. origin = *node
  170. tree.DeleteWithIterator(iter)
  171. }
  172. iter = nextIter
  173. }
  174. // prepare for the keys update
  175. var previous *rbtree.Item
  176. if insLength > 0 && (origin.Value != time || origin.Key == pos) {
  177. // insert our new interval
  178. if iter.Item().Value == time {
  179. prev := iter.Prev()
  180. if prev.Item().Value != time {
  181. iter.Item().Key = pos
  182. } else {
  183. tree.DeleteWithIterator(iter)
  184. iter = prev
  185. }
  186. origin.Value = time // cancels the insertion after applying the delta
  187. } else {
  188. _, iter = tree.Insert(rbtree.Item{Key: pos, Value: time})
  189. }
  190. } else {
  191. // rollback 1 position back, see "for true" deletion cycle ^
  192. iter = iter.Prev()
  193. previous = iter.Item()
  194. }
  195. // update the keys of all subsequent nodes
  196. delta := insLength - delLength
  197. if delta != 0 {
  198. for iter = iter.Next(); !iter.Limit(); iter = iter.Next() {
  199. // we do not need to re-balance the tree
  200. iter.Item().Key += delta
  201. }
  202. // have to adjust origin in case insLength == 0
  203. if origin.Key > pos {
  204. origin.Key += delta
  205. }
  206. }
  207. if insLength > 0 {
  208. if origin.Value != time {
  209. tree.Insert(rbtree.Item{Key: pos + insLength, Value: origin.Value})
  210. } else if pos == 0 {
  211. // recover the beginning
  212. tree.Insert(rbtree.Item{Key: pos, Value: time})
  213. }
  214. } else if (pos > origin.Key && previous.Value != origin.Value) || pos == origin.Key || pos == 0 {
  215. // continue the original interval
  216. tree.Insert(rbtree.Item{Key: pos, Value: origin.Value})
  217. }
  218. }
  219. // Merge combines several prepared File-s together.
  220. func (file *File) Merge(day int, others... *File) {
  221. myself := file.flatten()
  222. for _, other := range others {
  223. if other == nil {
  224. log.Panic("merging with a nil file")
  225. }
  226. lines := other.flatten()
  227. if len(myself) != len(lines) {
  228. log.Panicf("file corruption, lines number mismatch during merge %d != %d",
  229. len(myself), len(lines))
  230. }
  231. for i, l := range myself {
  232. ol := lines[i]
  233. if ol & TreeMergeMark == TreeMergeMark {
  234. continue
  235. }
  236. if l & TreeMergeMark == TreeMergeMark || l > ol {
  237. // 1 - the line is merged in myself and exists in other
  238. // 2 - the same line introduced in different branches,
  239. // consider the oldest version as the ground truth
  240. //
  241. // in case with (2) we should decrease the "future" counter,
  242. // but that really poisons the analysis
  243. myself[i] = ol
  244. }
  245. }
  246. }
  247. for i, l := range myself {
  248. if l & TreeMergeMark == TreeMergeMark {
  249. // original merge conflict resolution
  250. myself[i] = day
  251. file.updateTime(day, day, 1)
  252. }
  253. }
  254. // now we need to reconstruct the tree from the discrete values
  255. tree := &rbtree.RBTree{}
  256. for i, v := range myself {
  257. if i == 0 || v != myself[i - 1] {
  258. tree.Insert(rbtree.Item{Key: i, Value: v})
  259. }
  260. }
  261. tree.Insert(rbtree.Item{Key: len(myself), Value: TreeEnd})
  262. file.tree = tree
  263. }
  264. // Dump formats the underlying line interval tree into a string.
  265. // Useful for error messages, panic()-s and debugging.
  266. func (file *File) Dump() string {
  267. buffer := ""
  268. for iter := file.tree.Min(); !iter.Limit(); iter = iter.Next() {
  269. node := iter.Item()
  270. buffer += fmt.Sprintf("%d %d\n", node.Key, node.Value)
  271. }
  272. return buffer
  273. }
  274. // Validate checks the underlying line interval tree integrity.
  275. // The checks are as follows:
  276. //
  277. // 1. The minimum key must be 0 because the first line index is always 0.
  278. //
  279. // 2. The last node must carry TreeEnd value. This is the maintained invariant
  280. // which marks the ending of the last line interval.
  281. //
  282. // 3. Node keys must monotonically increase and never duplicate.
  283. func (file *File) Validate() {
  284. if file.tree.Min().Item().Key != 0 {
  285. panic("the tree must start with key 0")
  286. }
  287. if file.tree.Max().Item().Value != TreeEnd {
  288. panic(fmt.Sprintf("the last value in the tree must be %d", TreeEnd))
  289. }
  290. prevKey := -1
  291. for iter := file.tree.Min(); !iter.Limit(); iter = iter.Next() {
  292. node := iter.Item()
  293. if node.Key == prevKey {
  294. panic(fmt.Sprintf("duplicate tree key: %d", node.Key))
  295. }
  296. prevKey = node.Key
  297. }
  298. }
  299. // flatten represents the file as a slice of lines, each line's value being the corresponding day.
  300. func (file *File) flatten() []int {
  301. lines := make([]int, 0, file.Len())
  302. val := -1
  303. for iter := file.tree.Min(); !iter.Limit(); iter = iter.Next() {
  304. for i := len(lines); i < iter.Item().Key; i++ {
  305. lines = append(lines, val)
  306. }
  307. val = iter.Item().Value
  308. }
  309. return lines
  310. }