A fork of Gitea (see branch `mj`) adding Majority Judgment Polls 𐄷 over Issues and Merge Requests. https://git.mieuxvoter.fr
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

291 lines
8.1 KiB

Use native git variants by default with go-git variants as build tag (#13673) * Move last commit cache back into modules/git Signed-off-by: Andrew Thornton <art27@cantab.net> * Remove go-git from the interface for last commit cache Signed-off-by: Andrew Thornton <art27@cantab.net> * move cacheref to last_commit_cache Signed-off-by: Andrew Thornton <art27@cantab.net> * Remove go-git from routers/private/hook Signed-off-by: Andrew Thornton <art27@cantab.net> * Move FindLFSFiles to pipeline Signed-off-by: Andrew Thornton <art27@cantab.net> * Make no-go-git variants Signed-off-by: Andrew Thornton <art27@cantab.net> * Submodule RefID Signed-off-by: Andrew Thornton <art27@cantab.net> * fix issue with GetCommitsInfo Signed-off-by: Andrew Thornton <art27@cantab.net> * fix GetLastCommitForPaths Signed-off-by: Andrew Thornton <art27@cantab.net> * Improve efficiency Signed-off-by: Andrew Thornton <art27@cantab.net> * More efficiency Signed-off-by: Andrew Thornton <art27@cantab.net> * even faster Signed-off-by: Andrew Thornton <art27@cantab.net> * Reduce duplication * As per @lunny Signed-off-by: Andrew Thornton <art27@cantab.net> * attempt to fix drone Signed-off-by: Andrew Thornton <art27@cantab.net> * fix test-tags Signed-off-by: Andrew Thornton <art27@cantab.net> * default to use no-go-git variants and add gogit build tag Signed-off-by: Andrew Thornton <art27@cantab.net> * placate lint Signed-off-by: Andrew Thornton <art27@cantab.net> * as per @6543 Signed-off-by: Andrew Thornton <art27@cantab.net> Co-authored-by: 6543 <6543@obermui.de> Co-authored-by: techknowlogick <techknowlogick@gitea.io>
2 years ago
  1. // Copyright 2017 The Gitea Authors. All rights reserved.
  2. // Use of this source code is governed by a MIT-style
  3. // license that can be found in the LICENSE file.
  4. // +build gogit
  5. package git
  6. import (
  7. "path"
  8. "github.com/emirpasic/gods/trees/binaryheap"
  9. "github.com/go-git/go-git/v5/plumbing"
  10. "github.com/go-git/go-git/v5/plumbing/object"
  11. cgobject "github.com/go-git/go-git/v5/plumbing/object/commitgraph"
  12. )
  13. // GetCommitsInfo gets information of all commits that are corresponding to these entries
  14. func (tes Entries) GetCommitsInfo(commit *Commit, treePath string, cache *LastCommitCache) ([]CommitInfo, *Commit, error) {
  15. entryPaths := make([]string, len(tes)+1)
  16. // Get the commit for the treePath itself
  17. entryPaths[0] = ""
  18. for i, entry := range tes {
  19. entryPaths[i+1] = entry.Name()
  20. }
  21. commitNodeIndex, commitGraphFile := commit.repo.CommitNodeIndex()
  22. if commitGraphFile != nil {
  23. defer commitGraphFile.Close()
  24. }
  25. c, err := commitNodeIndex.Get(commit.ID)
  26. if err != nil {
  27. return nil, nil, err
  28. }
  29. var revs map[string]*object.Commit
  30. if cache != nil {
  31. var unHitPaths []string
  32. revs, unHitPaths, err = getLastCommitForPathsByCache(commit.ID.String(), treePath, entryPaths, cache)
  33. if err != nil {
  34. return nil, nil, err
  35. }
  36. if len(unHitPaths) > 0 {
  37. revs2, err := GetLastCommitForPaths(c, treePath, unHitPaths)
  38. if err != nil {
  39. return nil, nil, err
  40. }
  41. for k, v := range revs2 {
  42. if err := cache.Put(commit.ID.String(), path.Join(treePath, k), v.ID().String()); err != nil {
  43. return nil, nil, err
  44. }
  45. revs[k] = v
  46. }
  47. }
  48. } else {
  49. revs, err = GetLastCommitForPaths(c, treePath, entryPaths)
  50. }
  51. if err != nil {
  52. return nil, nil, err
  53. }
  54. commit.repo.gogitStorage.Close()
  55. commitsInfo := make([]CommitInfo, len(tes))
  56. for i, entry := range tes {
  57. commitsInfo[i] = CommitInfo{
  58. Entry: entry,
  59. }
  60. if rev, ok := revs[entry.Name()]; ok {
  61. entryCommit := convertCommit(rev)
  62. commitsInfo[i].Commit = entryCommit
  63. if entry.IsSubModule() {
  64. subModuleURL := ""
  65. var fullPath string
  66. if len(treePath) > 0 {
  67. fullPath = treePath + "/" + entry.Name()
  68. } else {
  69. fullPath = entry.Name()
  70. }
  71. if subModule, err := commit.GetSubModule(fullPath); err != nil {
  72. return nil, nil, err
  73. } else if subModule != nil {
  74. subModuleURL = subModule.URL
  75. }
  76. subModuleFile := NewSubModuleFile(entryCommit, subModuleURL, entry.ID.String())
  77. commitsInfo[i].SubModuleFile = subModuleFile
  78. }
  79. }
  80. }
  81. // Retrieve the commit for the treePath itself (see above). We basically
  82. // get it for free during the tree traversal and it's used for listing
  83. // pages to display information about newest commit for a given path.
  84. var treeCommit *Commit
  85. if treePath == "" {
  86. treeCommit = commit
  87. } else if rev, ok := revs[""]; ok {
  88. treeCommit = convertCommit(rev)
  89. treeCommit.repo = commit.repo
  90. }
  91. return commitsInfo, treeCommit, nil
  92. }
  93. type commitAndPaths struct {
  94. commit cgobject.CommitNode
  95. // Paths that are still on the branch represented by commit
  96. paths []string
  97. // Set of hashes for the paths
  98. hashes map[string]plumbing.Hash
  99. }
  100. func getCommitTree(c cgobject.CommitNode, treePath string) (*object.Tree, error) {
  101. tree, err := c.Tree()
  102. if err != nil {
  103. return nil, err
  104. }
  105. // Optimize deep traversals by focusing only on the specific tree
  106. if treePath != "" {
  107. tree, err = tree.Tree(treePath)
  108. if err != nil {
  109. return nil, err
  110. }
  111. }
  112. return tree, nil
  113. }
  114. func getFileHashes(c cgobject.CommitNode, treePath string, paths []string) (map[string]plumbing.Hash, error) {
  115. tree, err := getCommitTree(c, treePath)
  116. if err == object.ErrDirectoryNotFound {
  117. // The whole tree didn't exist, so return empty map
  118. return make(map[string]plumbing.Hash), nil
  119. }
  120. if err != nil {
  121. return nil, err
  122. }
  123. hashes := make(map[string]plumbing.Hash)
  124. for _, path := range paths {
  125. if path != "" {
  126. entry, err := tree.FindEntry(path)
  127. if err == nil {
  128. hashes[path] = entry.Hash
  129. }
  130. } else {
  131. hashes[path] = tree.Hash
  132. }
  133. }
  134. return hashes, nil
  135. }
  136. func getLastCommitForPathsByCache(commitID, treePath string, paths []string, cache *LastCommitCache) (map[string]*object.Commit, []string, error) {
  137. var unHitEntryPaths []string
  138. var results = make(map[string]*object.Commit)
  139. for _, p := range paths {
  140. lastCommit, err := cache.Get(commitID, path.Join(treePath, p))
  141. if err != nil {
  142. return nil, nil, err
  143. }
  144. if lastCommit != nil {
  145. results[p] = lastCommit.(*object.Commit)
  146. continue
  147. }
  148. unHitEntryPaths = append(unHitEntryPaths, p)
  149. }
  150. return results, unHitEntryPaths, nil
  151. }
  152. // GetLastCommitForPaths returns last commit information
  153. func GetLastCommitForPaths(c cgobject.CommitNode, treePath string, paths []string) (map[string]*object.Commit, error) {
  154. // We do a tree traversal with nodes sorted by commit time
  155. heap := binaryheap.NewWith(func(a, b interface{}) int {
  156. if a.(*commitAndPaths).commit.CommitTime().Before(b.(*commitAndPaths).commit.CommitTime()) {
  157. return 1
  158. }
  159. return -1
  160. })
  161. resultNodes := make(map[string]cgobject.CommitNode)
  162. initialHashes, err := getFileHashes(c, treePath, paths)
  163. if err != nil {
  164. return nil, err
  165. }
  166. // Start search from the root commit and with full set of paths
  167. heap.Push(&commitAndPaths{c, paths, initialHashes})
  168. for {
  169. cIn, ok := heap.Pop()
  170. if !ok {
  171. break
  172. }
  173. current := cIn.(*commitAndPaths)
  174. // Load the parent commits for the one we are currently examining
  175. numParents := current.commit.NumParents()
  176. var parents []cgobject.CommitNode
  177. for i := 0; i < numParents; i++ {
  178. parent, err := current.commit.ParentNode(i)
  179. if err != nil {
  180. break
  181. }
  182. parents = append(parents, parent)
  183. }
  184. // Examine the current commit and set of interesting paths
  185. pathUnchanged := make([]bool, len(current.paths))
  186. parentHashes := make([]map[string]plumbing.Hash, len(parents))
  187. for j, parent := range parents {
  188. parentHashes[j], err = getFileHashes(parent, treePath, current.paths)
  189. if err != nil {
  190. break
  191. }
  192. for i, path := range current.paths {
  193. if parentHashes[j][path] == current.hashes[path] {
  194. pathUnchanged[i] = true
  195. }
  196. }
  197. }
  198. var remainingPaths []string
  199. for i, path := range current.paths {
  200. // The results could already contain some newer change for the same path,
  201. // so don't override that and bail out on the file early.
  202. if resultNodes[path] == nil {
  203. if pathUnchanged[i] {
  204. // The path existed with the same hash in at least one parent so it could
  205. // not have been changed in this commit directly.
  206. remainingPaths = append(remainingPaths, path)
  207. } else {
  208. // There are few possible cases how can we get here:
  209. // - The path didn't exist in any parent, so it must have been created by
  210. // this commit.
  211. // - The path did exist in the parent commit, but the hash of the file has
  212. // changed.
  213. // - We are looking at a merge commit and the hash of the file doesn't
  214. // match any of the hashes being merged. This is more common for directories,
  215. // but it can also happen if a file is changed through conflict resolution.
  216. resultNodes[path] = current.commit
  217. }
  218. }
  219. }
  220. if len(remainingPaths) > 0 {
  221. // Add the parent nodes along with remaining paths to the heap for further
  222. // processing.
  223. for j, parent := range parents {
  224. // Combine remainingPath with paths available on the parent branch
  225. // and make union of them
  226. remainingPathsForParent := make([]string, 0, len(remainingPaths))
  227. newRemainingPaths := make([]string, 0, len(remainingPaths))
  228. for _, path := range remainingPaths {
  229. if parentHashes[j][path] == current.hashes[path] {
  230. remainingPathsForParent = append(remainingPathsForParent, path)
  231. } else {
  232. newRemainingPaths = append(newRemainingPaths, path)
  233. }
  234. }
  235. if remainingPathsForParent != nil {
  236. heap.Push(&commitAndPaths{parent, remainingPathsForParent, parentHashes[j]})
  237. }
  238. if len(newRemainingPaths) == 0 {
  239. break
  240. } else {
  241. remainingPaths = newRemainingPaths
  242. }
  243. }
  244. }
  245. }
  246. // Post-processing
  247. result := make(map[string]*object.Commit)
  248. for path, commitNode := range resultNodes {
  249. var err error
  250. result[path], err = commitNode.Commit()
  251. if err != nil {
  252. return nil, err
  253. }
  254. }
  255. return result, nil
  256. }