file.go 8.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304
  1. package hercules
  2. import (
  3. "fmt"
  4. "gopkg.in/src-d/hercules.v3/rbtree"
  5. )
  6. // A status is the something we would like to update during File.Update().
  7. type Status struct {
  8. data interface{}
  9. update func(interface{}, int, int, int)
  10. }
  11. // A file encapsulates a balanced binary tree to store line intervals and
  12. // a cumulative mapping of values to the corresponding length counters. Users
  13. // are not supposed to create File-s directly; instead, they should call NewFile().
  14. // NewFileFromTree() is the special constructor which is useful in the tests.
  15. //
  16. // Len() returns the number of lines in File.
  17. //
  18. // Update() mutates File by introducing tree structural changes and updating the
  19. // length mapping.
  20. //
  21. // Dump() writes the tree to a string and Validate() checks the tree integrity.
  22. type File struct {
  23. tree *rbtree.RBTree
  24. statuses []Status
  25. }
  26. func NewStatus(data interface{}, update func(interface{}, int, int, int)) Status {
  27. return Status{data: data, update: update}
  28. }
  29. // TreeEnd denotes the value of the last leaf in the tree.
  30. const TreeEnd int = -1
  31. // The ugly side of Go.
  32. // template <typename T> please!
  33. // min calculates the minimum of two 32-bit integers.
  34. func min(a int, b int) int {
  35. if a < b {
  36. return a
  37. }
  38. return b
  39. }
  40. // min64 calculates the minimum of two 64-bit integers.
  41. func min64(a int64, b int64) int64 {
  42. if a < b {
  43. return a
  44. }
  45. return b
  46. }
  47. // max calculates the maximum of two 32-bit integers.
  48. func max(a int, b int) int {
  49. if a < b {
  50. return b
  51. }
  52. return a
  53. }
  54. // max64 calculates the maximum of two 64-bit integers.
  55. func max64(a int64, b int64) int64 {
  56. if a < b {
  57. return b
  58. }
  59. return a
  60. }
  61. // abs64 calculates the absolute value of a 64-bit integer.
  62. func abs64(v int64) int64 {
  63. if v <= 0 {
  64. return -v
  65. }
  66. return v
  67. }
  68. func (file *File) updateTime(current_time int, previous_time int, delta int) {
  69. for _, status := range file.statuses {
  70. status.update(status.data, current_time, previous_time, delta)
  71. }
  72. }
  73. // NewFile initializes a new instance of File struct.
  74. //
  75. // time is the starting value of the first node;
  76. //
  77. // length is the starting length of the tree (the key of the second and the
  78. // last node);
  79. //
  80. // statuses are the attached interval length mappings.
  81. func NewFile(time int, length int, statuses ...Status) *File {
  82. file := new(File)
  83. file.statuses = statuses
  84. file.tree = new(rbtree.RBTree)
  85. if length > 0 {
  86. file.updateTime(time, time, length)
  87. file.tree.Insert(rbtree.Item{Key: 0, Value: time})
  88. }
  89. file.tree.Insert(rbtree.Item{Key: length, Value: TreeEnd})
  90. return file
  91. }
  92. // NewFileFromTree is an alternative constructor for File which is used in tests.
  93. // The resulting tree is validated with Validate() to ensure the initial integrity.
  94. //
  95. // keys is a slice with the starting tree keys.
  96. //
  97. // vals is a slice with the starting tree values. Must match the size of keys.
  98. //
  99. // statuses are the attached interval length mappings.
  100. func NewFileFromTree(keys []int, vals []int, statuses ...Status) *File {
  101. file := new(File)
  102. file.statuses = statuses
  103. file.tree = new(rbtree.RBTree)
  104. if len(keys) != len(vals) {
  105. panic("keys and vals must be of equal length")
  106. }
  107. for i := 0; i < len(keys); i++ {
  108. file.tree.Insert(rbtree.Item{Key: keys[i], Value: vals[i]})
  109. }
  110. file.Validate()
  111. return file
  112. }
  113. // Len returns the File's size - that is, the maximum key in the tree of line
  114. // intervals.
  115. func (file *File) Len() int {
  116. return file.tree.Max().Item().Key
  117. }
  118. // Update modifies the underlying tree to adapt to the specified line changes.
  119. //
  120. // time is the time when the requested changes are made. Sets the values of the
  121. // inserted nodes.
  122. //
  123. // pos is the index of the line at which the changes are introduced.
  124. //
  125. // ins_length is the number of inserted lines after pos.
  126. //
  127. // del_length is the number of removed lines after pos. Deletions come before
  128. // the insertions.
  129. //
  130. // The code inside this function is probably the most important one throughout
  131. // the project. It is extensively covered with tests. If you find a bug, please
  132. // add the corresponding case in file_test.go.
  133. func (file *File) Update(time int, pos int, ins_length int, del_length int) {
  134. if time < 0 {
  135. panic("time may not be negative")
  136. }
  137. if pos < 0 {
  138. panic("attempt to insert/delete at a negative position")
  139. }
  140. if ins_length < 0 || del_length < 0 {
  141. panic("ins_length and del_length must be nonnegative")
  142. }
  143. if ins_length|del_length == 0 {
  144. return
  145. }
  146. tree := file.tree
  147. if tree.Len() < 2 && tree.Min().Item().Key != 0 {
  148. panic("invalid tree state")
  149. }
  150. if pos > tree.Max().Item().Key {
  151. panic(fmt.Sprintf("attempt to insert after the end of the file: %d < %d",
  152. tree.Max().Item().Key, pos))
  153. }
  154. iter := tree.FindLE(pos)
  155. origin := *iter.Item()
  156. file.updateTime(time, time, ins_length)
  157. if del_length == 0 {
  158. // simple case with insertions only
  159. if origin.Key < pos || (origin.Value == time && pos == 0) {
  160. iter = iter.Next()
  161. }
  162. for ; !iter.Limit(); iter = iter.Next() {
  163. iter.Item().Key += ins_length
  164. }
  165. if origin.Value != time {
  166. tree.Insert(rbtree.Item{Key: pos, Value: time})
  167. if origin.Key < pos {
  168. tree.Insert(rbtree.Item{Key: pos + ins_length, Value: origin.Value})
  169. }
  170. }
  171. return
  172. }
  173. // delete nodes
  174. for true {
  175. node := iter.Item()
  176. next_iter := iter.Next()
  177. if next_iter.Limit() {
  178. if pos+del_length > node.Key {
  179. panic("attempt to delete after the end of the file")
  180. }
  181. break
  182. }
  183. delta := min(next_iter.Item().Key, pos+del_length) - max(node.Key, pos)
  184. if delta <= 0 {
  185. break
  186. }
  187. file.updateTime(time, node.Value, -delta)
  188. if node.Key >= pos {
  189. origin = *node
  190. tree.DeleteWithIterator(iter)
  191. }
  192. iter = next_iter
  193. }
  194. // prepare for the keys update
  195. var previous *rbtree.Item
  196. if ins_length > 0 && (origin.Value != time || origin.Key == pos) {
  197. // insert our new interval
  198. if iter.Item().Value == time {
  199. prev := iter.Prev()
  200. if prev.Item().Value != time {
  201. iter.Item().Key = pos
  202. } else {
  203. tree.DeleteWithIterator(iter)
  204. iter = prev
  205. }
  206. origin.Value = time // cancels the insertion after applying the delta
  207. } else {
  208. _, iter = tree.Insert(rbtree.Item{Key: pos, Value: time})
  209. }
  210. } else {
  211. // rollback 1 position back, see "for true" deletion cycle ^
  212. iter = iter.Prev()
  213. previous = iter.Item()
  214. }
  215. // update the keys of all subsequent nodes
  216. delta := ins_length - del_length
  217. if delta != 0 {
  218. for iter = iter.Next(); !iter.Limit(); iter = iter.Next() {
  219. // we do not need to re-balance the tree
  220. iter.Item().Key += delta
  221. }
  222. // have to adjust origin in case ins_length == 0
  223. if origin.Key > pos {
  224. origin.Key += delta
  225. }
  226. }
  227. if ins_length > 0 {
  228. if origin.Value != time {
  229. tree.Insert(rbtree.Item{pos + ins_length, origin.Value})
  230. } else if pos == 0 {
  231. // recover the beginning
  232. tree.Insert(rbtree.Item{pos, time})
  233. }
  234. } else if (pos > origin.Key && previous.Value != origin.Value) || pos == origin.Key || pos == 0 {
  235. // continue the original interval
  236. tree.Insert(rbtree.Item{pos, origin.Value})
  237. }
  238. }
  239. func (file *File) Status(index int) interface{} {
  240. if index < 0 || index >= len(file.statuses) {
  241. panic(fmt.Sprintf("status index %d is out of bounds [0, %d)",
  242. index, len(file.statuses)))
  243. }
  244. return file.statuses[index].data
  245. }
  246. // Dump formats the underlying line interval tree into a string.
  247. // Useful for error messages, panic()-s and debugging.
  248. func (file *File) Dump() string {
  249. buffer := ""
  250. for iter := file.tree.Min(); !iter.Limit(); iter = iter.Next() {
  251. node := iter.Item()
  252. buffer += fmt.Sprintf("%d %d\n", node.Key, node.Value)
  253. }
  254. return buffer
  255. }
  256. // Validate checks the underlying line interval tree integrity.
  257. // The checks are as follows:
  258. //
  259. // 1. The minimum key must be 0 because the first line index is always 0.
  260. //
  261. // 2. The last node must carry TreeEnd value. This is the maintained invariant
  262. // which marks the ending of the last line interval.
  263. //
  264. // 3. Node keys must monotonically increase and never duplicate.
  265. func (file *File) Validate() {
  266. if file.tree.Min().Item().Key != 0 {
  267. panic("the tree must start with key 0")
  268. }
  269. if file.tree.Max().Item().Value != TreeEnd {
  270. panic(fmt.Sprintf("the last value in the tree must be %d", TreeEnd))
  271. }
  272. prev_key := -1
  273. for iter := file.tree.Min(); !iter.Limit(); iter = iter.Next() {
  274. node := iter.Item()
  275. if node.Key == prev_key {
  276. panic(fmt.Sprintf("duplicate tree key: %d", node.Key))
  277. }
  278. prev_key = node.Key
  279. }
  280. }