aboutsummaryrefslogtreecommitdiffstats
path: root/references.go
blob: 593b9752b1ce1d3fb51a94981e4fb5fcda9b6f2a (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
package git

import (
	"io"

	"gopkg.in/src-d/go-git.v3/core"
	"gopkg.in/src-d/go-git.v3/diff"

	"github.com/sergi/go-diff/diffmatchpatch"
)

// References returns a References for the file at "path", the commits are
// sorted in commit order. It stops searching a branch for a file upon reaching
// the commit were the file was created.
//
// Caveats:
// - Moves and copies are not currently supported.
// - Cherry-picks are not detected unless there are no commits between them and
//   therefore can appear repeated in the list.
//   (see git path-id for hints on how to fix this).
func (c *Commit) References(path string) ([]*Commit, error) {
	result := make([]*Commit, 0)
	seen := make(map[core.Hash]struct{}, 0)
	if err := walkGraph(&result, &seen, c.r, c, path); err != nil {
		return nil, err
	}

	SortCommits(result)

	// for merges of identical cherry-picks
	return removeComp(path, result, equivalent)
}

// Recursive traversal of the commit graph, generating a linear history
// of the path.
func walkGraph(result *[]*Commit, seen *map[core.Hash]struct{}, repo *Repository, current *Commit, path string) error {
	// check and update seen
	if _, ok := (*seen)[current.Hash]; ok {
		return nil
	}
	(*seen)[current.Hash] = struct{}{}

	// if the path is not in the current commit, stop searching.
	if _, err := current.File(path); err != nil {
		return nil
	}

	// optimization: don't traverse branches that does not
	// contain the path.
	parents := parentsContainingPath(path, current)

	switch len(parents) {
	// if the path is not found in any of its parents, the path was
	// created by this commit; we must add it to the revisions list and
	// stop searching. This includes the case when current is the
	// initial commit.
	case 0:
		*result = append(*result, current)
		return nil
	case 1: // only one parent contains the path
		// if the file contents has change, add the current commit
		different, err := differentContents(path, current, parents)
		if err != nil {
			return err
		}
		if len(different) == 1 {
			*result = append(*result, current)
		}
		// in any case, walk the parent
		return walkGraph(result, seen, repo, parents[0], path)
	default: // more than one parent contains the path
		// TODO: detect merges that had a conflict, because they must be
		// included in the result here.
		for _, p := range parents {
			err := walkGraph(result, seen, repo, p, path)
			if err != nil {
				return err
			}
		}
	}
	return nil
}

// TODO: benchmark this making git.Commit.parent public instead of using
// an iterator
func parentsContainingPath(path string, c *Commit) []*Commit {
	var result []*Commit
	iter := c.Parents()
	for {
		parent, err := iter.Next()
		if err != nil {
			if err == io.EOF {
				return result
			}
			panic("unreachable")
		}
		if _, err := parent.File(path); err == nil {
			result = append(result, parent)
		}
	}
}

// Returns an slice of the commits in "cs" that has the file "path", but with different
// contents than what can be found in "c".
func differentContents(path string, c *Commit, cs []*Commit) ([]*Commit, error) {
	result := make([]*Commit, 0, len(cs))
	h, found := blobHash(path, c)
	if !found {
		return nil, ErrFileNotFound
	}
	for _, cx := range cs {
		if hx, found := blobHash(path, cx); found && h != hx {
			result = append(result, cx)
		}
	}
	return result, nil
}

// blobHash returns the hash of a path in a commit
func blobHash(path string, commit *Commit) (hash core.Hash, found bool) {
	file, err := commit.File(path)
	if err != nil {
		var empty core.Hash
		return empty, found
	}
	return file.Hash, true
}

type contentsComparatorFn func(path string, a, b *Commit) (bool, error)

// Returns a new slice of commits, with duplicates removed.  Expects a
// sorted commit list.  Duplication is defined according to "comp".  It
// will always keep the first commit of a series of duplicated commits.
func removeComp(path string, cs []*Commit, comp contentsComparatorFn) ([]*Commit, error) {
	result := make([]*Commit, 0, len(cs))
	if len(cs) == 0 {
		return result, nil
	}
	result = append(result, cs[0])
	for i := 1; i < len(cs); i++ {
		equals, err := comp(path, cs[i], cs[i-1])
		if err != nil {
			return nil, err
		}
		if !equals {
			result = append(result, cs[i])
		}
	}
	return result, nil
}

// Equivalent commits are commits whose patch is the same.
func equivalent(path string, a, b *Commit) (bool, error) {
	numParentsA := a.NumParents()
	numParentsB := b.NumParents()

	// the first commit is not equivalent to anyone
	// and "I think" merges can not be equivalent to anything
	if numParentsA != 1 || numParentsB != 1 {
		return false, nil
	}

	diffsA, err := patch(a, path)
	if err != nil {
		return false, err
	}
	diffsB, err := patch(b, path)
	if err != nil {
		return false, err
	}

	return sameDiffs(diffsA, diffsB), nil
}

func patch(c *Commit, path string) ([]diffmatchpatch.Diff, error) {
	// get contents of the file in the commit
	file, err := c.File(path)
	if err != nil {
		return nil, err
	}
	content := file.Contents()

	// get contents of the file in the first parent of the commit
	var contentParent string
	iter := c.Parents()
	parent, err := iter.Next()
	if err != nil {
		return nil, err
	}
	file, err = parent.File(path)
	if err != nil {
		contentParent = ""
	} else {
		contentParent = file.Contents()
	}

	// compare the contents of parent and child
	return diff.Do(content, contentParent), nil
}

func sameDiffs(a, b []diffmatchpatch.Diff) bool {
	if len(a) != len(b) {
		return false
	}
	for i := range a {
		if !sameDiff(a[i], b[i]) {
			return false
		}
	}
	return true
}

func sameDiff(a, b diffmatchpatch.Diff) bool {
	if a.Type != b.Type {
		return false
	}
	switch a.Type {
	case 0:
		return countLines(a.Text) == countLines(b.Text)
	case 1, -1:
		return a.Text == b.Text
	default:
		panic("unreachable")
	}
}