burndown.go 41 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277
  1. package leaves
  2. import (
  3. "errors"
  4. "fmt"
  5. "io"
  6. "log"
  7. "sort"
  8. "sync"
  9. "unicode/utf8"
  10. "github.com/gogo/protobuf/proto"
  11. "github.com/sergi/go-diff/diffmatchpatch"
  12. "gopkg.in/src-d/go-git.v4"
  13. "gopkg.in/src-d/go-git.v4/plumbing"
  14. "gopkg.in/src-d/go-git.v4/plumbing/object"
  15. "gopkg.in/src-d/go-git.v4/utils/merkletrie"
  16. "gopkg.in/src-d/hercules.v6/internal/burndown"
  17. "gopkg.in/src-d/hercules.v6/internal/core"
  18. "gopkg.in/src-d/hercules.v6/internal/pb"
  19. items "gopkg.in/src-d/hercules.v6/internal/plumbing"
  20. "gopkg.in/src-d/hercules.v6/internal/plumbing/identity"
  21. "gopkg.in/src-d/hercules.v6/internal/yaml"
  22. )
  23. // BurndownAnalysis allows to gather the line burndown statistics for a Git repository.
  24. // It is a LeafPipelineItem.
  25. // Reference: https://erikbern.com/2016/12/05/the-half-life-of-code.html
  26. type BurndownAnalysis struct {
  27. // Granularity sets the size of each band - the number of days it spans.
  28. // Smaller values provide better resolution but require more work and eat more
  29. // memory. 30 days is usually enough.
  30. Granularity int
  31. // Sampling sets how detailed is the statistic - the size of the interval in
  32. // days between consecutive measurements. It may not be greater than Granularity. Try 15 or 30.
  33. Sampling int
  34. // TrackFiles enables or disables the fine-grained per-file burndown analysis.
  35. // It does not change the project level burndown results.
  36. TrackFiles bool
  37. // The number of developers for which to collect the burndown stats. 0 disables it.
  38. PeopleNumber int
  39. // Debug activates the debugging mode. Analyse() runs slower in this mode
  40. // but it accurately checks all the intermediate states for invariant
  41. // violations.
  42. Debug bool
  43. // Repository points to the analysed Git repository struct from go-git.
  44. repository *git.Repository
  45. // globalHistory is the daily deltas of daily line counts.
  46. // E.g. day 0: day 0 +50 lines
  47. // day 10: day 0 -10 lines; day 10 +20 lines
  48. // day 12: day 0 -5 lines; day 10 -3 lines; day 12 +10 lines
  49. // map [0] [0] = 50
  50. // map[10] [0] = -10
  51. // map[10][10] = 20
  52. // map[12] [0] = -5
  53. // map[12][10] = -3
  54. // map[12][12] = 10
  55. globalHistory sparseHistory
  56. // fileHistories is the daily deltas of each file's daily line counts.
  57. fileHistories map[string]sparseHistory
  58. // peopleHistories is the daily deltas of each person's daily line counts.
  59. peopleHistories []sparseHistory
  60. // files is the mapping <file path> -> *File.
  61. files map[string]*burndown.File
  62. // mergedFiles is used during merges to record the real file hashes
  63. mergedFiles map[string]bool
  64. // mergedAuthor of the processed merge commit
  65. mergedAuthor int
  66. // renames is a quick and dirty solution for the "future branch renames" problem.
  67. renames map[string]string
  68. // matrix is the mutual deletions and self insertions.
  69. matrix []map[int]int64
  70. // day is the most recent day index processed.
  71. day int
  72. // previousDay is the day from the previous sample period -
  73. // different from DaysSinceStart.previousDay.
  74. previousDay int
  75. // references IdentityDetector.ReversedPeopleDict
  76. reversedPeopleDict []string
  77. }
  78. // BurndownResult carries the result of running BurndownAnalysis - it is returned by
  79. // BurndownAnalysis.Finalize().
  80. type BurndownResult struct {
  81. // [number of samples][number of bands]
  82. // The number of samples depends on Sampling: the less Sampling, the bigger the number.
  83. // The number of bands depends on Granularity: the less Granularity, the bigger the number.
  84. GlobalHistory DenseHistory
  85. // The key is the path inside the Git repository. The value's dimensions are the same as
  86. // in GlobalHistory.
  87. FileHistories map[string]DenseHistory
  88. // [number of people][number of samples][number of bands]
  89. PeopleHistories []DenseHistory
  90. // [number of people][number of people + 2]
  91. // The first element is the total number of lines added by the author.
  92. // The second element is the number of removals by unidentified authors (outside reversedPeopleDict).
  93. // The rest of the elements are equal the number of line removals by the corresponding
  94. // authors in reversedPeopleDict: 2 -> 0, 3 -> 1, etc.
  95. PeopleMatrix DenseHistory
  96. // The following members are private.
  97. // reversedPeopleDict is borrowed from IdentityDetector and becomes available after
  98. // Pipeline.Initialize(facts map[string]interface{}). Thus it can be obtained via
  99. // facts[FactIdentityDetectorReversedPeopleDict].
  100. reversedPeopleDict []string
  101. // sampling and granularity are copied from BurndownAnalysis and stored for service purposes
  102. // such as merging several results together.
  103. sampling int
  104. granularity int
  105. }
  106. const (
  107. // ConfigBurndownGranularity is the name of the option to set BurndownAnalysis.Granularity.
  108. ConfigBurndownGranularity = "Burndown.Granularity"
  109. // ConfigBurndownSampling is the name of the option to set BurndownAnalysis.Sampling.
  110. ConfigBurndownSampling = "Burndown.Sampling"
  111. // ConfigBurndownTrackFiles enables burndown collection for files.
  112. ConfigBurndownTrackFiles = "Burndown.TrackFiles"
  113. // ConfigBurndownTrackPeople enables burndown collection for authors.
  114. ConfigBurndownTrackPeople = "Burndown.TrackPeople"
  115. // ConfigBurndownDebug enables some extra debug assertions.
  116. ConfigBurndownDebug = "Burndown.Debug"
  117. // DefaultBurndownGranularity is the default number of days for BurndownAnalysis.Granularity
  118. // and BurndownAnalysis.Sampling.
  119. DefaultBurndownGranularity = 30
  120. // authorSelf is the internal author index which is used in BurndownAnalysis.Finalize() to
  121. // format the author overwrites matrix.
  122. authorSelf = (1 << (32 - burndown.TreeMaxBinPower)) - 2
  123. )
  124. type sparseHistory = map[int]map[int]int64
  125. // DenseHistory is the matrix [number of samples][number of bands] -> number of lines.
  126. type DenseHistory = [][]int64
  127. // Name of this PipelineItem. Uniquely identifies the type, used for mapping keys, etc.
  128. func (analyser *BurndownAnalysis) Name() string {
  129. return "Burndown"
  130. }
  131. // Provides returns the list of names of entities which are produced by this PipelineItem.
  132. // Each produced entity will be inserted into `deps` of dependent Consume()-s according
  133. // to this list. Also used by core.Registry to build the global map of providers.
  134. func (analyser *BurndownAnalysis) Provides() []string {
  135. return []string{}
  136. }
  137. // Requires returns the list of names of entities which are needed by this PipelineItem.
  138. // Each requested entity will be inserted into `deps` of Consume(). In turn, those
  139. // entities are Provides() upstream.
  140. func (analyser *BurndownAnalysis) Requires() []string {
  141. arr := [...]string{
  142. items.DependencyFileDiff, items.DependencyTreeChanges, items.DependencyBlobCache,
  143. items.DependencyDay, identity.DependencyAuthor}
  144. return arr[:]
  145. }
  146. // ListConfigurationOptions returns the list of changeable public properties of this PipelineItem.
  147. func (analyser *BurndownAnalysis) ListConfigurationOptions() []core.ConfigurationOption {
  148. options := [...]core.ConfigurationOption{{
  149. Name: ConfigBurndownGranularity,
  150. Description: "How many days there are in a single band.",
  151. Flag: "granularity",
  152. Type: core.IntConfigurationOption,
  153. Default: DefaultBurndownGranularity}, {
  154. Name: ConfigBurndownSampling,
  155. Description: "How frequently to record the state in days.",
  156. Flag: "sampling",
  157. Type: core.IntConfigurationOption,
  158. Default: DefaultBurndownGranularity}, {
  159. Name: ConfigBurndownTrackFiles,
  160. Description: "Record detailed statistics per each file.",
  161. Flag: "burndown-files",
  162. Type: core.BoolConfigurationOption,
  163. Default: false}, {
  164. Name: ConfigBurndownTrackPeople,
  165. Description: "Record detailed statistics per each developer.",
  166. Flag: "burndown-people",
  167. Type: core.BoolConfigurationOption,
  168. Default: false}, {
  169. Name: ConfigBurndownDebug,
  170. Description: "Validate the trees on each step.",
  171. Flag: "burndown-debug",
  172. Type: core.BoolConfigurationOption,
  173. Default: false},
  174. }
  175. return options[:]
  176. }
  177. // Configure sets the properties previously published by ListConfigurationOptions().
  178. func (analyser *BurndownAnalysis) Configure(facts map[string]interface{}) error {
  179. if val, exists := facts[ConfigBurndownGranularity].(int); exists {
  180. analyser.Granularity = val
  181. }
  182. if val, exists := facts[ConfigBurndownSampling].(int); exists {
  183. analyser.Sampling = val
  184. }
  185. if val, exists := facts[ConfigBurndownTrackFiles].(bool); exists {
  186. analyser.TrackFiles = val
  187. }
  188. if people, exists := facts[ConfigBurndownTrackPeople].(bool); people {
  189. if val, exists := facts[identity.FactIdentityDetectorPeopleCount].(int); exists {
  190. if val < 0 {
  191. return fmt.Errorf("PeopleNumber is negative: %d", val)
  192. }
  193. analyser.PeopleNumber = val
  194. analyser.reversedPeopleDict = facts[identity.FactIdentityDetectorReversedPeopleDict].([]string)
  195. }
  196. } else if exists {
  197. analyser.PeopleNumber = 0
  198. }
  199. if val, exists := facts[ConfigBurndownDebug].(bool); exists {
  200. analyser.Debug = val
  201. }
  202. return nil
  203. }
  204. // Flag for the command line switch which enables this analysis.
  205. func (analyser *BurndownAnalysis) Flag() string {
  206. return "burndown"
  207. }
  208. // Description returns the text which explains what the analysis is doing.
  209. func (analyser *BurndownAnalysis) Description() string {
  210. return "Line burndown stats indicate the numbers of lines which were last edited within " +
  211. "specific time intervals through time. Search for \"git-of-theseus\" in the internet."
  212. }
  213. // Initialize resets the temporary caches and prepares this PipelineItem for a series of Consume()
  214. // calls. The repository which is going to be analysed is supplied as an argument.
  215. func (analyser *BurndownAnalysis) Initialize(repository *git.Repository) error {
  216. if analyser.Granularity <= 0 {
  217. log.Printf("Warning: adjusted the granularity to %d days\n",
  218. DefaultBurndownGranularity)
  219. analyser.Granularity = DefaultBurndownGranularity
  220. }
  221. if analyser.Sampling <= 0 {
  222. log.Printf("Warning: adjusted the sampling to %d days\n",
  223. DefaultBurndownGranularity)
  224. analyser.Sampling = DefaultBurndownGranularity
  225. }
  226. if analyser.Sampling > analyser.Granularity {
  227. log.Printf("Warning: granularity may not be less than sampling, adjusted to %d\n",
  228. analyser.Granularity)
  229. analyser.Sampling = analyser.Granularity
  230. }
  231. analyser.repository = repository
  232. analyser.globalHistory = sparseHistory{}
  233. analyser.fileHistories = map[string]sparseHistory{}
  234. if analyser.PeopleNumber < 0 {
  235. return fmt.Errorf("PeopleNumber is negative: %d", analyser.PeopleNumber)
  236. }
  237. analyser.peopleHistories = make([]sparseHistory, analyser.PeopleNumber)
  238. analyser.files = map[string]*burndown.File{}
  239. analyser.mergedFiles = map[string]bool{}
  240. analyser.mergedAuthor = identity.AuthorMissing
  241. analyser.renames = map[string]string{}
  242. analyser.matrix = make([]map[int]int64, analyser.PeopleNumber)
  243. analyser.day = 0
  244. analyser.previousDay = 0
  245. return nil
  246. }
  247. // Consume runs this PipelineItem on the next commit's data.
  248. // `deps` contain all the results from upstream PipelineItem-s as requested by Requires().
  249. // Additionally, DependencyCommit is always present there and represents the analysed *object.Commit.
  250. // This function returns the mapping with analysis results. The keys must be the same as
  251. // in Provides(). If there was an error, nil is returned.
  252. func (analyser *BurndownAnalysis) Consume(deps map[string]interface{}) (map[string]interface{}, error) {
  253. author := deps[identity.DependencyAuthor].(int)
  254. day := deps[items.DependencyDay].(int)
  255. if !deps[core.DependencyIsMerge].(bool) {
  256. analyser.day = day
  257. analyser.onNewDay()
  258. } else {
  259. // effectively disables the status updates if the commit is a merge
  260. // we will analyse the conflicts resolution in Merge()
  261. analyser.day = burndown.TreeMergeMark
  262. analyser.mergedFiles = map[string]bool{}
  263. analyser.mergedAuthor = author
  264. }
  265. cache := deps[items.DependencyBlobCache].(map[plumbing.Hash]*items.CachedBlob)
  266. treeDiffs := deps[items.DependencyTreeChanges].(object.Changes)
  267. fileDiffs := deps[items.DependencyFileDiff].(map[string]items.FileDiffData)
  268. for _, change := range treeDiffs {
  269. action, _ := change.Action()
  270. var err error
  271. switch action {
  272. case merkletrie.Insert:
  273. err = analyser.handleInsertion(change, author, cache)
  274. case merkletrie.Delete:
  275. err = analyser.handleDeletion(change, author, cache)
  276. case merkletrie.Modify:
  277. err = analyser.handleModification(change, author, cache, fileDiffs)
  278. }
  279. if err != nil {
  280. return nil, err
  281. }
  282. }
  283. // in case there is a merge analyser.day equals to TreeMergeMark
  284. analyser.day = day
  285. return nil, nil
  286. }
  287. // Fork clones this item. Everything is copied by reference except the files
  288. // which are copied by value.
  289. func (analyser *BurndownAnalysis) Fork(n int) []core.PipelineItem {
  290. result := make([]core.PipelineItem, n)
  291. for i := range result {
  292. clone := *analyser
  293. clone.files = map[string]*burndown.File{}
  294. for key, file := range analyser.files {
  295. clone.files[key] = file.Clone(false)
  296. }
  297. result[i] = &clone
  298. }
  299. return result
  300. }
  301. // Merge combines several items together. We apply the special file merging logic here.
  302. func (analyser *BurndownAnalysis) Merge(branches []core.PipelineItem) {
  303. all := make([]*BurndownAnalysis, len(branches)+1)
  304. all[0] = analyser
  305. for i, branch := range branches {
  306. all[i+1] = branch.(*BurndownAnalysis)
  307. }
  308. keys := map[string]bool{}
  309. for _, burn := range all {
  310. for key, val := range burn.mergedFiles {
  311. // (*)
  312. // there can be contradicting flags,
  313. // e.g. item was renamed and a new item written on its place
  314. // this may be not exactly accurate
  315. keys[key] = keys[key] || val
  316. }
  317. }
  318. for key, val := range keys {
  319. if !val {
  320. for _, burn := range all {
  321. delete(burn.files, key)
  322. }
  323. continue
  324. }
  325. files := make([]*burndown.File, 0, len(all))
  326. for _, burn := range all {
  327. file := burn.files[key]
  328. if file != nil {
  329. // file can be nil if it is considered binary in this branch
  330. files = append(files, file)
  331. }
  332. }
  333. if len(files) == 0 {
  334. // so we could be wrong in (*) and there is no such file eventually
  335. // it could be also removed in the merge commit itself
  336. continue
  337. }
  338. if len(files) > 1 {
  339. files[0].Merge(analyser.packPersonWithDay(analyser.mergedAuthor, analyser.day), files[1:]...)
  340. }
  341. for _, burn := range all {
  342. if burn.files[key] != files[0] {
  343. burn.files[key] = files[0].Clone(false)
  344. }
  345. }
  346. }
  347. analyser.onNewDay()
  348. }
  349. // Finalize returns the result of the analysis. Further Consume() calls are not expected.
  350. func (analyser *BurndownAnalysis) Finalize() interface{} {
  351. globalHistory, lastDay := analyser.groupSparseHistory(analyser.globalHistory, -1)
  352. fileHistories := map[string]DenseHistory{}
  353. for key, history := range analyser.fileHistories {
  354. if len(history) > 0 {
  355. fileHistories[key], _ = analyser.groupSparseHistory(history, lastDay)
  356. }
  357. }
  358. peopleHistories := make([]DenseHistory, analyser.PeopleNumber)
  359. for i, history := range analyser.peopleHistories {
  360. if len(history) > 0 {
  361. // there can be people with only trivial merge commits and without own lines
  362. peopleHistories[i], _ = analyser.groupSparseHistory(history, lastDay)
  363. } else {
  364. peopleHistories[i] = make(DenseHistory, len(globalHistory))
  365. for j, gh := range globalHistory {
  366. peopleHistories[i][j] = make([]int64, len(gh))
  367. }
  368. }
  369. }
  370. peopleMatrix := make(DenseHistory, analyser.PeopleNumber)
  371. for i, row := range analyser.matrix {
  372. mrow := make([]int64, analyser.PeopleNumber+2)
  373. peopleMatrix[i] = mrow
  374. for key, val := range row {
  375. if key == identity.AuthorMissing {
  376. key = -1
  377. } else if key == authorSelf {
  378. key = -2
  379. }
  380. mrow[key+2] = val
  381. }
  382. }
  383. return BurndownResult{
  384. GlobalHistory: globalHistory,
  385. FileHistories: fileHistories,
  386. PeopleHistories: peopleHistories,
  387. PeopleMatrix: peopleMatrix,
  388. reversedPeopleDict: analyser.reversedPeopleDict,
  389. sampling: analyser.Sampling,
  390. granularity: analyser.Granularity,
  391. }
  392. }
  393. // Serialize converts the analysis result as returned by Finalize() to text or bytes.
  394. // The text format is YAML and the bytes format is Protocol Buffers.
  395. func (analyser *BurndownAnalysis) Serialize(result interface{}, binary bool, writer io.Writer) error {
  396. burndownResult := result.(BurndownResult)
  397. if binary {
  398. return analyser.serializeBinary(&burndownResult, writer)
  399. }
  400. analyser.serializeText(&burndownResult, writer)
  401. return nil
  402. }
  403. // Deserialize converts the specified protobuf bytes to BurndownResult.
  404. func (analyser *BurndownAnalysis) Deserialize(pbmessage []byte) (interface{}, error) {
  405. msg := pb.BurndownAnalysisResults{}
  406. err := proto.Unmarshal(pbmessage, &msg)
  407. if err != nil {
  408. return nil, err
  409. }
  410. result := BurndownResult{}
  411. convertCSR := func(mat *pb.BurndownSparseMatrix) DenseHistory {
  412. res := make(DenseHistory, mat.NumberOfRows)
  413. for i := 0; i < int(mat.NumberOfRows); i++ {
  414. res[i] = make([]int64, mat.NumberOfColumns)
  415. for j := 0; j < len(mat.Rows[i].Columns); j++ {
  416. res[i][j] = int64(mat.Rows[i].Columns[j])
  417. }
  418. }
  419. return res
  420. }
  421. result.GlobalHistory = convertCSR(msg.Project)
  422. result.FileHistories = map[string]DenseHistory{}
  423. for _, mat := range msg.Files {
  424. result.FileHistories[mat.Name] = convertCSR(mat)
  425. }
  426. result.reversedPeopleDict = make([]string, len(msg.People))
  427. result.PeopleHistories = make([]DenseHistory, len(msg.People))
  428. for i, mat := range msg.People {
  429. result.PeopleHistories[i] = convertCSR(mat)
  430. result.reversedPeopleDict[i] = mat.Name
  431. }
  432. if msg.PeopleInteraction != nil {
  433. result.PeopleMatrix = make(DenseHistory, msg.PeopleInteraction.NumberOfRows)
  434. }
  435. for i := 0; i < len(result.PeopleMatrix); i++ {
  436. result.PeopleMatrix[i] = make([]int64, msg.PeopleInteraction.NumberOfColumns)
  437. for j := int(msg.PeopleInteraction.Indptr[i]); j < int(msg.PeopleInteraction.Indptr[i+1]); j++ {
  438. result.PeopleMatrix[i][msg.PeopleInteraction.Indices[j]] = msg.PeopleInteraction.Data[j]
  439. }
  440. }
  441. result.sampling = int(msg.Sampling)
  442. result.granularity = int(msg.Granularity)
  443. return result, nil
  444. }
  445. // MergeResults combines two BurndownResult-s together.
  446. func (analyser *BurndownAnalysis) MergeResults(
  447. r1, r2 interface{}, c1, c2 *core.CommonAnalysisResult) interface{} {
  448. bar1 := r1.(BurndownResult)
  449. bar2 := r2.(BurndownResult)
  450. merged := BurndownResult{}
  451. if bar1.sampling < bar2.sampling {
  452. merged.sampling = bar1.sampling
  453. } else {
  454. merged.sampling = bar2.sampling
  455. }
  456. if bar1.granularity < bar2.granularity {
  457. merged.granularity = bar1.granularity
  458. } else {
  459. merged.granularity = bar2.granularity
  460. }
  461. var people map[string][3]int
  462. people, merged.reversedPeopleDict = identity.Detector{}.MergeReversedDicts(
  463. bar1.reversedPeopleDict, bar2.reversedPeopleDict)
  464. var wg sync.WaitGroup
  465. if len(bar1.GlobalHistory) > 0 || len(bar2.GlobalHistory) > 0 {
  466. wg.Add(1)
  467. go func() {
  468. defer wg.Done()
  469. merged.GlobalHistory = mergeMatrices(
  470. bar1.GlobalHistory, bar2.GlobalHistory,
  471. bar1.granularity, bar1.sampling,
  472. bar2.granularity, bar2.sampling,
  473. c1, c2)
  474. }()
  475. }
  476. if len(bar1.FileHistories) > 0 || len(bar2.FileHistories) > 0 {
  477. merged.FileHistories = map[string]DenseHistory{}
  478. historyMutex := sync.Mutex{}
  479. for key, fh1 := range bar1.FileHistories {
  480. if fh2, exists := bar2.FileHistories[key]; exists {
  481. wg.Add(1)
  482. go func(fh1, fh2 DenseHistory, key string) {
  483. defer wg.Done()
  484. historyMutex.Lock()
  485. defer historyMutex.Unlock()
  486. merged.FileHistories[key] = mergeMatrices(
  487. fh1, fh2, bar1.granularity, bar1.sampling, bar2.granularity, bar2.sampling, c1, c2)
  488. }(fh1, fh2, key)
  489. } else {
  490. historyMutex.Lock()
  491. merged.FileHistories[key] = fh1
  492. historyMutex.Unlock()
  493. }
  494. }
  495. for key, fh2 := range bar2.FileHistories {
  496. if _, exists := bar1.FileHistories[key]; !exists {
  497. historyMutex.Lock()
  498. merged.FileHistories[key] = fh2
  499. historyMutex.Unlock()
  500. }
  501. }
  502. }
  503. if len(merged.reversedPeopleDict) > 0 {
  504. merged.PeopleHistories = make([]DenseHistory, len(merged.reversedPeopleDict))
  505. for i, key := range merged.reversedPeopleDict {
  506. ptrs := people[key]
  507. if ptrs[1] < 0 {
  508. if len(bar2.PeopleHistories) > 0 {
  509. merged.PeopleHistories[i] = bar2.PeopleHistories[ptrs[2]]
  510. }
  511. } else if ptrs[2] < 0 {
  512. if len(bar1.PeopleHistories) > 0 {
  513. merged.PeopleHistories[i] = bar1.PeopleHistories[ptrs[1]]
  514. }
  515. } else {
  516. wg.Add(1)
  517. go func(i int) {
  518. defer wg.Done()
  519. var m1, m2 DenseHistory
  520. if len(bar1.PeopleHistories) > 0 {
  521. m1 = bar1.PeopleHistories[ptrs[1]]
  522. }
  523. if len(bar2.PeopleHistories) > 0 {
  524. m2 = bar2.PeopleHistories[ptrs[2]]
  525. }
  526. merged.PeopleHistories[i] = mergeMatrices(
  527. m1, m2,
  528. bar1.granularity, bar1.sampling,
  529. bar2.granularity, bar2.sampling,
  530. c1, c2,
  531. )
  532. }(i)
  533. }
  534. }
  535. wg.Add(1)
  536. go func() {
  537. defer wg.Done()
  538. if len(bar2.PeopleMatrix) == 0 {
  539. merged.PeopleMatrix = bar1.PeopleMatrix
  540. // extend the matrix in both directions
  541. for i := 0; i < len(merged.PeopleMatrix); i++ {
  542. for j := len(bar1.reversedPeopleDict); j < len(merged.reversedPeopleDict); j++ {
  543. merged.PeopleMatrix[i] = append(merged.PeopleMatrix[i], 0)
  544. }
  545. }
  546. for i := len(bar1.reversedPeopleDict); i < len(merged.reversedPeopleDict); i++ {
  547. merged.PeopleMatrix = append(
  548. merged.PeopleMatrix, make([]int64, len(merged.reversedPeopleDict)+2))
  549. }
  550. } else {
  551. merged.PeopleMatrix = make(DenseHistory, len(merged.reversedPeopleDict))
  552. for i := range merged.PeopleMatrix {
  553. merged.PeopleMatrix[i] = make([]int64, len(merged.reversedPeopleDict)+2)
  554. }
  555. for i, key := range bar1.reversedPeopleDict {
  556. mi := people[key][0] // index in merged.reversedPeopleDict
  557. copy(merged.PeopleMatrix[mi][:2], bar1.PeopleMatrix[i][:2])
  558. for j, val := range bar1.PeopleMatrix[i][2:] {
  559. merged.PeopleMatrix[mi][2+people[bar1.reversedPeopleDict[j]][0]] = val
  560. }
  561. }
  562. for i, key := range bar2.reversedPeopleDict {
  563. mi := people[key][0] // index in merged.reversedPeopleDict
  564. merged.PeopleMatrix[mi][0] += bar2.PeopleMatrix[i][0]
  565. merged.PeopleMatrix[mi][1] += bar2.PeopleMatrix[i][1]
  566. for j, val := range bar2.PeopleMatrix[i][2:] {
  567. merged.PeopleMatrix[mi][2+people[bar2.reversedPeopleDict[j]][0]] += val
  568. }
  569. }
  570. }
  571. }()
  572. }
  573. wg.Wait()
  574. return merged
  575. }
  576. // mergeMatrices takes two [number of samples][number of bands] matrices,
  577. // resamples them to days so that they become square, sums and resamples back to the
  578. // least of (sampling1, sampling2) and (granularity1, granularity2).
  579. func mergeMatrices(m1, m2 DenseHistory, granularity1, sampling1, granularity2, sampling2 int,
  580. c1, c2 *core.CommonAnalysisResult) DenseHistory {
  581. commonMerged := *c1
  582. commonMerged.Merge(c2)
  583. var granularity, sampling int
  584. if sampling1 < sampling2 {
  585. sampling = sampling1
  586. } else {
  587. sampling = sampling2
  588. }
  589. if granularity1 < granularity2 {
  590. granularity = granularity1
  591. } else {
  592. granularity = granularity2
  593. }
  594. size := int((commonMerged.EndTime - commonMerged.BeginTime) / (3600 * 24))
  595. daily := make([][]float32, size+granularity)
  596. for i := range daily {
  597. daily[i] = make([]float32, size+sampling)
  598. }
  599. if len(m1) > 0 {
  600. addBurndownMatrix(m1, granularity1, sampling1, daily,
  601. int(c1.BeginTime-commonMerged.BeginTime)/(3600*24))
  602. }
  603. if len(m2) > 0 {
  604. addBurndownMatrix(m2, granularity2, sampling2, daily,
  605. int(c2.BeginTime-commonMerged.BeginTime)/(3600*24))
  606. }
  607. // convert daily to [][]int64
  608. result := make(DenseHistory, (size+sampling-1)/sampling)
  609. for i := range result {
  610. result[i] = make([]int64, (size+granularity-1)/granularity)
  611. sampledIndex := i * sampling
  612. if i == len(result)-1 {
  613. sampledIndex = size - 1
  614. }
  615. for j := 0; j < len(result[i]); j++ {
  616. accum := float32(0)
  617. for k := j * granularity; k < (j+1)*granularity && k < size; k++ {
  618. accum += daily[sampledIndex][k]
  619. }
  620. result[i][j] = int64(accum)
  621. }
  622. }
  623. return result
  624. }
  625. // Explode `matrix` so that it is daily sampled and has daily bands, shift by `offset` days
  626. // and add to the accumulator. `daily` size is square and is guaranteed to fit `matrix` by
  627. // the caller.
  628. // Rows: *at least* len(matrix) * sampling + offset
  629. // Columns: *at least* len(matrix[...]) * granularity + offset
  630. // `matrix` can be sparse, so that the last columns which are equal to 0 are truncated.
  631. func addBurndownMatrix(matrix DenseHistory, granularity, sampling int, daily [][]float32, offset int) {
  632. // Determine the maximum number of bands; the actual one may be larger but we do not care
  633. maxCols := 0
  634. for _, row := range matrix {
  635. if maxCols < len(row) {
  636. maxCols = len(row)
  637. }
  638. }
  639. neededRows := len(matrix)*sampling + offset
  640. if len(daily) < neededRows {
  641. log.Panicf("merge bug: too few daily rows: required %d, have %d",
  642. neededRows, len(daily))
  643. }
  644. if len(daily[0]) < maxCols {
  645. log.Panicf("merge bug: too few daily cols: required %d, have %d",
  646. maxCols, len(daily[0]))
  647. }
  648. for x := 0; x < maxCols; x++ {
  649. for y := 0; y < len(matrix); y++ {
  650. if x*granularity > (y+1)*sampling {
  651. // the future is zeros
  652. continue
  653. }
  654. decay := func(startIndex int, startVal float32) {
  655. if startVal == 0 {
  656. return
  657. }
  658. k := float32(matrix[y][x]) / startVal // <= 1
  659. scale := float32((y+1)*sampling - startIndex)
  660. for i := x * granularity; i < (x+1)*granularity; i++ {
  661. initial := daily[startIndex-1+offset][i+offset]
  662. for j := startIndex; j < (y+1)*sampling; j++ {
  663. daily[j+offset][i+offset] = initial * (1 + (k-1)*float32(j-startIndex+1)/scale)
  664. }
  665. }
  666. }
  667. raise := func(finishIndex int, finishVal float32) {
  668. var initial float32
  669. if y > 0 {
  670. initial = float32(matrix[y-1][x])
  671. }
  672. startIndex := y * sampling
  673. if startIndex < x*granularity {
  674. startIndex = x * granularity
  675. }
  676. if startIndex == finishIndex {
  677. return
  678. }
  679. avg := (finishVal - initial) / float32(finishIndex-startIndex)
  680. for j := y * sampling; j < finishIndex; j++ {
  681. for i := startIndex; i <= j; i++ {
  682. daily[j+offset][i+offset] = avg
  683. }
  684. }
  685. // copy [x*g..y*s)
  686. for j := y * sampling; j < finishIndex; j++ {
  687. for i := x * granularity; i < y*sampling; i++ {
  688. daily[j+offset][i+offset] = daily[j-1+offset][i+offset]
  689. }
  690. }
  691. }
  692. if (x+1)*granularity >= (y+1)*sampling {
  693. // x*granularity <= (y+1)*sampling
  694. // 1. x*granularity <= y*sampling
  695. // y*sampling..(y+1)sampling
  696. //
  697. // x+1
  698. // /
  699. // /
  700. // / y+1 -|
  701. // / |
  702. // / y -|
  703. // /
  704. // / x
  705. //
  706. // 2. x*granularity > y*sampling
  707. // x*granularity..(y+1)sampling
  708. //
  709. // x+1
  710. // /
  711. // /
  712. // / y+1 -|
  713. // / |
  714. // / x -|
  715. // /
  716. // / y
  717. if x*granularity <= y*sampling {
  718. raise((y+1)*sampling, float32(matrix[y][x]))
  719. } else if (y+1)*sampling > x*granularity {
  720. raise((y+1)*sampling, float32(matrix[y][x]))
  721. avg := float32(matrix[y][x]) / float32((y+1)*sampling-x*granularity)
  722. for j := x * granularity; j < (y+1)*sampling; j++ {
  723. for i := x * granularity; i <= j; i++ {
  724. daily[j+offset][i+offset] = avg
  725. }
  726. }
  727. }
  728. } else if (x+1)*granularity >= y*sampling {
  729. // y*sampling <= (x+1)*granularity < (y+1)sampling
  730. // y*sampling..(x+1)*granularity
  731. // (x+1)*granularity..(y+1)sampling
  732. // x+1
  733. // /\
  734. // / \
  735. // / \
  736. // / y+1
  737. // /
  738. // y
  739. v1 := float32(matrix[y-1][x])
  740. v2 := float32(matrix[y][x])
  741. var peak float32
  742. delta := float32((x+1)*granularity - y*sampling)
  743. var scale float32
  744. var previous float32
  745. if y > 0 && (y-1)*sampling >= x*granularity {
  746. // x*g <= (y-1)*s <= y*s <= (x+1)*g <= (y+1)*s
  747. // |________|.......^
  748. if y > 1 {
  749. previous = float32(matrix[y-2][x])
  750. }
  751. scale = float32(sampling)
  752. } else {
  753. // (y-1)*s < x*g <= y*s <= (x+1)*g <= (y+1)*s
  754. // |______|.......^
  755. if y == 0 {
  756. scale = float32(sampling)
  757. } else {
  758. scale = float32(y*sampling - x*granularity)
  759. }
  760. }
  761. peak = v1 + (v1-previous)/scale*delta
  762. if v2 > peak {
  763. // we need to adjust the peak, it may not be less than the decayed value
  764. if y < len(matrix)-1 {
  765. // y*s <= (x+1)*g <= (y+1)*s < (y+2)*s
  766. // ^.........|_________|
  767. k := (v2 - float32(matrix[y+1][x])) / float32(sampling) // > 0
  768. peak = float32(matrix[y][x]) + k*float32((y+1)*sampling-(x+1)*granularity)
  769. // peak > v2 > v1
  770. } else {
  771. peak = v2
  772. // not enough data to interpolate; this is at least not restricted
  773. }
  774. }
  775. raise((x+1)*granularity, peak)
  776. decay((x+1)*granularity, peak)
  777. } else {
  778. // (x+1)*granularity < y*sampling
  779. // y*sampling..(y+1)sampling
  780. decay(y*sampling, float32(matrix[y-1][x]))
  781. }
  782. }
  783. }
  784. }
  785. func (analyser *BurndownAnalysis) serializeText(result *BurndownResult, writer io.Writer) {
  786. fmt.Fprintln(writer, " granularity:", result.granularity)
  787. fmt.Fprintln(writer, " sampling:", result.sampling)
  788. yaml.PrintMatrix(writer, result.GlobalHistory, 2, "project", true)
  789. if len(result.FileHistories) > 0 {
  790. fmt.Fprintln(writer, " files:")
  791. keys := sortedKeys(result.FileHistories)
  792. for _, key := range keys {
  793. yaml.PrintMatrix(writer, result.FileHistories[key], 4, key, true)
  794. }
  795. }
  796. if len(result.PeopleHistories) > 0 {
  797. fmt.Fprintln(writer, " people_sequence:")
  798. for key := range result.PeopleHistories {
  799. fmt.Fprintln(writer, " - "+yaml.SafeString(result.reversedPeopleDict[key]))
  800. }
  801. fmt.Fprintln(writer, " people:")
  802. for key, val := range result.PeopleHistories {
  803. yaml.PrintMatrix(writer, val, 4, result.reversedPeopleDict[key], true)
  804. }
  805. fmt.Fprintln(writer, " people_interaction: |-")
  806. yaml.PrintMatrix(writer, result.PeopleMatrix, 4, "", false)
  807. }
  808. }
  809. func (analyser *BurndownAnalysis) serializeBinary(result *BurndownResult, writer io.Writer) error {
  810. message := pb.BurndownAnalysisResults{
  811. Granularity: int32(result.granularity),
  812. Sampling: int32(result.sampling),
  813. }
  814. if len(result.GlobalHistory) > 0 {
  815. message.Project = pb.ToBurndownSparseMatrix(result.GlobalHistory, "project")
  816. }
  817. if len(result.FileHistories) > 0 {
  818. message.Files = make([]*pb.BurndownSparseMatrix, len(result.FileHistories))
  819. keys := sortedKeys(result.FileHistories)
  820. i := 0
  821. for _, key := range keys {
  822. message.Files[i] = pb.ToBurndownSparseMatrix(
  823. result.FileHistories[key], key)
  824. i++
  825. }
  826. }
  827. if len(result.PeopleHistories) > 0 {
  828. message.People = make(
  829. []*pb.BurndownSparseMatrix, len(result.PeopleHistories))
  830. for key, val := range result.PeopleHistories {
  831. if len(val) > 0 {
  832. message.People[key] = pb.ToBurndownSparseMatrix(val, result.reversedPeopleDict[key])
  833. }
  834. }
  835. message.PeopleInteraction = pb.DenseToCompressedSparseRowMatrix(result.PeopleMatrix)
  836. }
  837. serialized, err := proto.Marshal(&message)
  838. if err != nil {
  839. return err
  840. }
  841. _, err = writer.Write(serialized)
  842. return err
  843. }
  844. func sortedKeys(m map[string]DenseHistory) []string {
  845. keys := make([]string, 0, len(m))
  846. for k := range m {
  847. keys = append(keys, k)
  848. }
  849. sort.Strings(keys)
  850. return keys
  851. }
  852. func checkClose(c io.Closer) {
  853. if err := c.Close(); err != nil {
  854. panic(err)
  855. }
  856. }
  857. // We do a hack and store the day in the first 14 bits and the author index in the last 18.
  858. // Strictly speaking, int can be 64-bit and then the author index occupies 32+18 bits.
  859. // This hack is needed to simplify the values storage inside File-s. We can compare
  860. // different values together and they are compared as days for the same author.
  861. func (analyser *BurndownAnalysis) packPersonWithDay(person int, day int) int {
  862. if analyser.PeopleNumber == 0 {
  863. return day
  864. }
  865. result := day & burndown.TreeMergeMark
  866. result |= person << burndown.TreeMaxBinPower
  867. // This effectively means max (16383 - 1) days (>44 years) and (131072 - 2) devs.
  868. // One day less because burndown.TreeMergeMark = ((1 << 14) - 1) is a special day.
  869. return result
  870. }
  871. func (analyser *BurndownAnalysis) unpackPersonWithDay(value int) (int, int) {
  872. if analyser.PeopleNumber == 0 {
  873. return identity.AuthorMissing, value
  874. }
  875. return value >> burndown.TreeMaxBinPower, value & burndown.TreeMergeMark
  876. }
  877. func (analyser *BurndownAnalysis) onNewDay() {
  878. if analyser.day > analyser.previousDay {
  879. analyser.previousDay = analyser.day
  880. }
  881. analyser.mergedAuthor = identity.AuthorMissing
  882. }
  883. func (analyser *BurndownAnalysis) updateGlobal(currentTime, previousTime, delta int) {
  884. _, currentDay := analyser.unpackPersonWithDay(currentTime)
  885. _, previousDay := analyser.unpackPersonWithDay(previousTime)
  886. currentHistory := analyser.globalHistory[currentDay]
  887. if currentHistory == nil {
  888. currentHistory = map[int]int64{}
  889. analyser.globalHistory[currentDay] = currentHistory
  890. }
  891. currentHistory[previousDay] += int64(delta)
  892. }
  893. // updateFile is bound to the specific `history` in the closure.
  894. func (analyser *BurndownAnalysis) updateFile(
  895. history sparseHistory, currentTime, previousTime, delta int) {
  896. _, currentDay := analyser.unpackPersonWithDay(currentTime)
  897. _, previousDay := analyser.unpackPersonWithDay(previousTime)
  898. currentHistory := history[currentDay]
  899. if currentHistory == nil {
  900. currentHistory = map[int]int64{}
  901. history[currentDay] = currentHistory
  902. }
  903. currentHistory[previousDay] += int64(delta)
  904. }
  905. func (analyser *BurndownAnalysis) updateAuthor(currentTime, previousTime, delta int) {
  906. previousAuthor, previousDay := analyser.unpackPersonWithDay(previousTime)
  907. if previousAuthor == identity.AuthorMissing {
  908. return
  909. }
  910. _, currentDay := analyser.unpackPersonWithDay(currentTime)
  911. history := analyser.peopleHistories[previousAuthor]
  912. if history == nil {
  913. history = sparseHistory{}
  914. analyser.peopleHistories[previousAuthor] = history
  915. }
  916. currentHistory := history[currentDay]
  917. if currentHistory == nil {
  918. currentHistory = map[int]int64{}
  919. history[currentDay] = currentHistory
  920. }
  921. currentHistory[previousDay] += int64(delta)
  922. }
  923. func (analyser *BurndownAnalysis) updateMatrix(currentTime, previousTime, delta int) {
  924. newAuthor, _ := analyser.unpackPersonWithDay(currentTime)
  925. oldAuthor, _ := analyser.unpackPersonWithDay(previousTime)
  926. if oldAuthor == identity.AuthorMissing {
  927. return
  928. }
  929. if newAuthor == oldAuthor && delta > 0 {
  930. newAuthor = authorSelf
  931. }
  932. row := analyser.matrix[oldAuthor]
  933. if row == nil {
  934. row = map[int]int64{}
  935. analyser.matrix[oldAuthor] = row
  936. }
  937. cell, exists := row[newAuthor]
  938. if !exists {
  939. row[newAuthor] = 0
  940. cell = 0
  941. }
  942. row[newAuthor] = cell + int64(delta)
  943. }
  944. func (analyser *BurndownAnalysis) newFile(
  945. hash plumbing.Hash, name string, author int, day int, size int) (*burndown.File, error) {
  946. updaters := make([]burndown.Updater, 1)
  947. updaters[0] = analyser.updateGlobal
  948. if analyser.TrackFiles {
  949. history := analyser.fileHistories[name]
  950. if history == nil {
  951. // can be not nil if the file was created in a future branch
  952. history = sparseHistory{}
  953. }
  954. analyser.fileHistories[name] = history
  955. updaters = append(updaters, func(currentTime, previousTime, delta int) {
  956. analyser.updateFile(history, currentTime, previousTime, delta)
  957. })
  958. }
  959. if analyser.PeopleNumber > 0 {
  960. updaters = append(updaters, analyser.updateAuthor)
  961. updaters = append(updaters, analyser.updateMatrix)
  962. day = analyser.packPersonWithDay(author, day)
  963. }
  964. return burndown.NewFile(day, size, updaters...), nil
  965. }
  966. func (analyser *BurndownAnalysis) handleInsertion(
  967. change *object.Change, author int, cache map[plumbing.Hash]*items.CachedBlob) error {
  968. blob := cache[change.To.TreeEntry.Hash]
  969. lines, err := blob.CountLines()
  970. if err != nil {
  971. // binary
  972. return nil
  973. }
  974. name := change.To.Name
  975. file, exists := analyser.files[name]
  976. if exists {
  977. println("\n", analyser, "error")
  978. return fmt.Errorf("file %s already exists", name)
  979. }
  980. var hash plumbing.Hash
  981. if analyser.day != burndown.TreeMergeMark {
  982. hash = blob.Hash
  983. }
  984. file, err = analyser.newFile(hash, name, author, analyser.day, lines)
  985. analyser.files[name] = file
  986. if analyser.day == burndown.TreeMergeMark {
  987. analyser.mergedFiles[name] = true
  988. }
  989. return err
  990. }
  991. func (analyser *BurndownAnalysis) handleDeletion(
  992. change *object.Change, author int, cache map[plumbing.Hash]*items.CachedBlob) error {
  993. name := change.From.Name
  994. file, exists := analyser.files[name]
  995. blob := cache[change.From.TreeEntry.Hash]
  996. lines, err := blob.CountLines()
  997. if exists && err != nil {
  998. return fmt.Errorf("file %s unexpectedly became binary", name)
  999. }
  1000. if !exists {
  1001. return nil
  1002. }
  1003. file.Update(analyser.packPersonWithDay(author, analyser.day), 0, 0, lines)
  1004. delete(analyser.files, name)
  1005. delete(analyser.fileHistories, name)
  1006. analyser.renames[name] = ""
  1007. if analyser.day == burndown.TreeMergeMark {
  1008. analyser.mergedFiles[name] = false
  1009. }
  1010. return nil
  1011. }
  1012. func (analyser *BurndownAnalysis) handleModification(
  1013. change *object.Change, author int, cache map[plumbing.Hash]*items.CachedBlob,
  1014. diffs map[string]items.FileDiffData) error {
  1015. if analyser.day == burndown.TreeMergeMark {
  1016. analyser.mergedFiles[change.To.Name] = true
  1017. }
  1018. file, exists := analyser.files[change.From.Name]
  1019. if !exists {
  1020. // this indeed may happen
  1021. return analyser.handleInsertion(change, author, cache)
  1022. }
  1023. // possible rename
  1024. if change.To.Name != change.From.Name {
  1025. err := analyser.handleRename(change.From.Name, change.To.Name)
  1026. if err != nil {
  1027. return err
  1028. }
  1029. }
  1030. // Check for binary changes
  1031. blobFrom := cache[change.From.TreeEntry.Hash]
  1032. _, errFrom := blobFrom.CountLines()
  1033. blobTo := cache[change.To.TreeEntry.Hash]
  1034. _, errTo := blobTo.CountLines()
  1035. if errFrom != errTo {
  1036. if errFrom != nil {
  1037. // the file is no longer binary
  1038. return analyser.handleInsertion(change, author, cache)
  1039. }
  1040. // the file became binary
  1041. return analyser.handleDeletion(change, author, cache)
  1042. } else if errFrom != nil {
  1043. // what are we doing here?!
  1044. return nil
  1045. }
  1046. thisDiffs := diffs[change.To.Name]
  1047. if file.Len() != thisDiffs.OldLinesOfCode {
  1048. log.Printf("====TREE====\n%s", file.Dump())
  1049. return fmt.Errorf("%s: internal integrity error src %d != %d %s -> %s",
  1050. change.To.Name, thisDiffs.OldLinesOfCode, file.Len(),
  1051. change.From.TreeEntry.Hash.String(), change.To.TreeEntry.Hash.String())
  1052. }
  1053. // we do not call RunesToDiffLines so the number of lines equals
  1054. // to the rune count
  1055. position := 0
  1056. pending := diffmatchpatch.Diff{Text: ""}
  1057. apply := func(edit diffmatchpatch.Diff) {
  1058. length := utf8.RuneCountInString(edit.Text)
  1059. if edit.Type == diffmatchpatch.DiffInsert {
  1060. file.Update(analyser.packPersonWithDay(author, analyser.day), position, length, 0)
  1061. position += length
  1062. } else {
  1063. file.Update(analyser.packPersonWithDay(author, analyser.day), position, 0, length)
  1064. }
  1065. if analyser.Debug {
  1066. file.Validate()
  1067. }
  1068. }
  1069. for _, edit := range thisDiffs.Diffs {
  1070. dumpBefore := ""
  1071. if analyser.Debug {
  1072. dumpBefore = file.Dump()
  1073. }
  1074. length := utf8.RuneCountInString(edit.Text)
  1075. debugError := func() {
  1076. log.Printf("%s: internal diff error\n", change.To.Name)
  1077. log.Printf("Update(%d, %d, %d (0), %d (0))\n", analyser.day, position,
  1078. length, utf8.RuneCountInString(pending.Text))
  1079. if dumpBefore != "" {
  1080. log.Printf("====TREE BEFORE====\n%s====END====\n", dumpBefore)
  1081. }
  1082. log.Printf("====TREE AFTER====\n%s====END====\n", file.Dump())
  1083. }
  1084. switch edit.Type {
  1085. case diffmatchpatch.DiffEqual:
  1086. if pending.Text != "" {
  1087. apply(pending)
  1088. pending.Text = ""
  1089. }
  1090. position += length
  1091. case diffmatchpatch.DiffInsert:
  1092. if pending.Text != "" {
  1093. if pending.Type == diffmatchpatch.DiffInsert {
  1094. debugError()
  1095. return errors.New("DiffInsert may not appear after DiffInsert")
  1096. }
  1097. file.Update(analyser.packPersonWithDay(author, analyser.day), position, length,
  1098. utf8.RuneCountInString(pending.Text))
  1099. if analyser.Debug {
  1100. file.Validate()
  1101. }
  1102. position += length
  1103. pending.Text = ""
  1104. } else {
  1105. pending = edit
  1106. }
  1107. case diffmatchpatch.DiffDelete:
  1108. if pending.Text != "" {
  1109. debugError()
  1110. return errors.New("DiffDelete may not appear after DiffInsert/DiffDelete")
  1111. }
  1112. pending = edit
  1113. default:
  1114. debugError()
  1115. return fmt.Errorf("diff operation is not supported: %d", edit.Type)
  1116. }
  1117. }
  1118. if pending.Text != "" {
  1119. apply(pending)
  1120. pending.Text = ""
  1121. }
  1122. if file.Len() != thisDiffs.NewLinesOfCode {
  1123. return fmt.Errorf("%s: internal integrity error dst %d != %d %s -> %s",
  1124. change.To.Name, thisDiffs.NewLinesOfCode, file.Len(),
  1125. change.From.TreeEntry.Hash.String(), change.To.TreeEntry.Hash.String())
  1126. }
  1127. return nil
  1128. }
  1129. func (analyser *BurndownAnalysis) handleRename(from, to string) error {
  1130. if from == to {
  1131. return nil
  1132. }
  1133. file, exists := analyser.files[from]
  1134. if !exists {
  1135. return fmt.Errorf("file %s > %s does not exist (files)", from, to)
  1136. }
  1137. analyser.files[to] = file
  1138. delete(analyser.files, from)
  1139. if analyser.day == burndown.TreeMergeMark {
  1140. analyser.mergedFiles[from] = false
  1141. }
  1142. if analyser.TrackFiles {
  1143. history := analyser.fileHistories[from]
  1144. if history == nil {
  1145. // a future branch could have already renamed it and we are retarded
  1146. futureRename, exists := analyser.renames[from]
  1147. if futureRename == "" && exists {
  1148. // the file will be deleted in the future, whatever
  1149. history = sparseHistory{}
  1150. } else {
  1151. history = analyser.fileHistories[futureRename]
  1152. if history == nil {
  1153. return fmt.Errorf("file %s > %s does not exist (histories)", from, to)
  1154. }
  1155. }
  1156. }
  1157. analyser.fileHistories[to] = history
  1158. delete(analyser.fileHistories, from)
  1159. }
  1160. analyser.renames[from] = to
  1161. return nil
  1162. }
  1163. func (analyser *BurndownAnalysis) groupSparseHistory(
  1164. history sparseHistory, lastDay int) (DenseHistory, int) {
  1165. if len(history) == 0 {
  1166. panic("empty history")
  1167. }
  1168. var days []int
  1169. for day := range history {
  1170. days = append(days, day)
  1171. }
  1172. sort.Ints(days)
  1173. if lastDay >= 0 {
  1174. if days[len(days)-1] < lastDay {
  1175. days = append(days, lastDay)
  1176. } else if days[len(days)-1] > lastDay {
  1177. panic("days corruption")
  1178. }
  1179. } else {
  1180. lastDay = days[len(days)-1]
  1181. }
  1182. // [y][x]
  1183. // y - sampling
  1184. // x - granularity
  1185. samples := lastDay/analyser.Sampling + 1
  1186. bands := lastDay/analyser.Granularity + 1
  1187. result := make(DenseHistory, samples)
  1188. for i := 0; i < bands; i++ {
  1189. result[i] = make([]int64, bands)
  1190. }
  1191. prevsi := 0
  1192. for _, day := range days {
  1193. si := day / analyser.Sampling
  1194. if si > prevsi {
  1195. state := result[prevsi]
  1196. for i := prevsi + 1; i <= si; i++ {
  1197. copy(result[i], state)
  1198. }
  1199. prevsi = si
  1200. }
  1201. sample := result[si]
  1202. for bday, value := range history[day] {
  1203. sample[bday/analyser.Granularity] += value
  1204. }
  1205. }
  1206. return result, lastDay
  1207. }
  1208. func init() {
  1209. core.Registry.Register(&BurndownAnalysis{})
  1210. }