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.

195 lines
3.7 KiB

  1. package difftree
  2. import (
  3. "bytes"
  4. "fmt"
  5. "io"
  6. "sort"
  7. "strings"
  8. "gopkg.in/src-d/go-git.v3"
  9. "gopkg.in/src-d/go-git.v3/core"
  10. )
  11. type Action int
  12. func (a Action) String() string {
  13. switch a {
  14. case Insert:
  15. return "Insert"
  16. case Delete:
  17. return "Delete"
  18. case Modify:
  19. return "Modify"
  20. default:
  21. panic(fmt.Sprintf("unsupported action: %d", a))
  22. }
  23. }
  24. const (
  25. Insert Action = iota
  26. Delete
  27. Modify
  28. )
  29. type Change struct {
  30. Action
  31. File *git.File
  32. }
  33. func (c *Change) String() string {
  34. return fmt.Sprintf("<Action: %s, Path: %s, Size: %d>", c.Action, c.File.Name, c.File.Size)
  35. }
  36. type Changes []*Change
  37. func newEmpty() Changes {
  38. return make([]*Change, 0, 0)
  39. }
  40. func New(a, b *git.Tree) (Changes, error) {
  41. if a == b {
  42. return newEmpty(), nil
  43. }
  44. if a == nil || b == nil {
  45. return newWithEmpty(a, b)
  46. }
  47. return newDiffTree(a, b)
  48. }
  49. func (c Changes) Len() int {
  50. return len(c)
  51. }
  52. func (c Changes) Swap(i, j int) {
  53. c[i], c[j] = c[j], c[i]
  54. }
  55. func (c Changes) Less(i, j int) bool {
  56. return strings.Compare(c[i].File.Name, c[j].File.Name) < 0
  57. }
  58. func (c Changes) String() string {
  59. var buffer bytes.Buffer
  60. buffer.WriteString("[")
  61. comma := ""
  62. for _, v := range c {
  63. buffer.WriteString(comma)
  64. buffer.WriteString(v.String())
  65. comma = ", "
  66. }
  67. buffer.WriteString("]")
  68. return buffer.String()
  69. }
  70. func newWithEmpty(a, b *git.Tree) (Changes, error) {
  71. changes := newEmpty()
  72. var action Action
  73. var tree *git.Tree
  74. if a == nil {
  75. action = Insert
  76. tree = b
  77. } else {
  78. action = Delete
  79. tree = a
  80. }
  81. iter := tree.Files()
  82. defer iter.Close()
  83. for {
  84. file, err := iter.Next()
  85. if err == io.EOF {
  86. break
  87. } else if err != nil {
  88. return nil, fmt.Errorf("cannot get next file: %s", err)
  89. }
  90. insert := &Change{
  91. Action: action,
  92. File: file,
  93. }
  94. changes = append(changes, insert)
  95. }
  96. return changes, nil
  97. }
  98. // FIXME: this is very inefficient, but correct.
  99. // The proper way to do this is to implement a diff-tree algorithm,
  100. // while taking advantage of the tree hashes to avoid traversing
  101. // subtrees when the hash is equal in both inputs.
  102. func newDiffTree(a, b *git.Tree) (Changes, error) {
  103. result := newEmpty()
  104. aChanges, err := newWithEmpty(a, nil)
  105. if err != nil {
  106. return nil, fmt.Errorf("cannot create nil-diff of source tree: %s", err)
  107. }
  108. sort.Sort(aChanges)
  109. bChanges, err := newWithEmpty(nil, b)
  110. if err != nil {
  111. return nil, fmt.Errorf("cannot create nil-diff of destination tree: %s", err)
  112. }
  113. sort.Sort(bChanges)
  114. for len(aChanges) > 0 && len(bChanges) > 0 {
  115. switch comp := strings.Compare(aChanges[0].File.Name, bChanges[0].File.Name); {
  116. case comp == 0: // append as "Modify" or ignore if not changed
  117. modified, err := hasChange(a, b, aChanges[0].File.Name)
  118. if err != nil {
  119. return nil, err
  120. }
  121. if modified {
  122. bChanges[0].Action = Modify
  123. result = append(result, bChanges[0])
  124. } else {
  125. }
  126. aChanges = aChanges[1:]
  127. bChanges = bChanges[1:]
  128. case comp < 0: // delete first a change
  129. result = append(result, aChanges[0])
  130. aChanges = aChanges[1:]
  131. case comp > 0: // insert first b change
  132. result = append(result, bChanges[0])
  133. bChanges = bChanges[1:]
  134. }
  135. }
  136. // append all remaining changes in aChanges, if any, as deletes
  137. // append all remaining changes in bChanges, if any, as inserts
  138. result = append(result, aChanges...)
  139. result = append(result, bChanges...)
  140. return result, nil
  141. }
  142. func hasChange(a, b *git.Tree, path string) (bool, error) {
  143. ha, err := hash(a, path)
  144. if err != nil {
  145. return false, err
  146. }
  147. hb, err := hash(b, path)
  148. if err != nil {
  149. return false, err
  150. }
  151. return ha != hb, nil
  152. }
  153. func hash(tree *git.Tree, path string) (core.Hash, error) {
  154. file, err := tree.File(path)
  155. if err != nil {
  156. var empty core.Hash
  157. return empty, fmt.Errorf("cannot find file %s in tree: %s", path, err)
  158. }
  159. return file.Hash, nil
  160. }