1 /*
2  * Copyright (c) 2018, 2019, 2020 Stefan Sperling <stsp@openbsd.org>
3  *
4  * Permission to use, copy, modify, and distribute this software for any
5  * purpose with or without fee is hereby granted, provided that the above
6  * copyright notice and this permission notice appear in all copies.
7  *
8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15  */
16 
17 #include <sys/queue.h>
18 #include <sys/mman.h>
19 #include <sys/stat.h>
20 
21 #include <sha1.h>
22 #include <string.h>
23 #include <stdbool.h>
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <time.h>
27 #include <limits.h>
28 #include <util.h>
29 #include <zlib.h>
30 
31 #include "got_error.h"
32 #include "got_object.h"
33 #include "got_cancel.h"
34 #include "got_blame.h"
35 #include "got_commit_graph.h"
36 #include "got_opentemp.h"
37 
38 #include "got_lib_inflate.h"
39 #include "got_lib_delta.h"
40 #include "got_lib_object.h"
41 #include "got_lib_diff.h"
42 
43 #ifndef MAX
44 #define	MAX(_a,_b) ((_a) > (_b) ? (_a) : (_b))
45 #endif
46 
47 struct got_blame_line {
48 	int annotated;
49 	struct got_object_id id;
50 };
51 
52 struct got_blame {
53 	FILE *f;
54 	char *map;
55 	struct diff_data left_data;
56 	struct diff_data right_data;
57 	const struct diff_config *cfg;
58 	size_t filesize;
59 	int nlines;
60 	int nannotated;
61 	struct got_blame_line *lines; /* one per line */
62 	off_t *line_offsets;		/* one per line */
63 	int ncommits;
64 };
65 
66 static const struct got_error *
67 annotate_line(struct got_blame *blame, int lineno, struct got_object_id *id,
68     const struct got_error *(*cb)(void *, int, int, struct got_object_id *),
69     void *arg)
70 {
71 	const struct got_error *err = NULL;
72 	struct got_blame_line *line;
73 
74 	if (lineno < 1 || lineno > blame->nlines)
75 		return NULL;
76 
77 	line = &blame->lines[lineno - 1];
78 	if (line->annotated)
79 		return NULL;
80 
81 	memcpy(&line->id, id, sizeof(line->id));
82 	line->annotated = 1;
83 	blame->nannotated++;
84 	if (cb)
85 		err = cb(arg, blame->nlines, lineno, id);
86 	return err;
87 }
88 
89 static const struct got_error *
90 blame_changes(struct got_blame *blame, struct diff_result *diff_result,
91     struct got_object_id *commit_id,
92     const struct got_error *(*cb)(void *, int, int, struct got_object_id *),
93     void *arg)
94 {
95 	const struct got_error *err = NULL;
96 	int i;
97 
98 	for (i = 0; i < diff_result->chunks.len; i++) {
99 		struct diff_chunk *c = diff_chunk_get(diff_result, i);
100 		unsigned int right_start, right_count;
101 		int lineno, len;
102 		int ln;
103 
104 		if (diff_chunk_get_left_count(c) != 0)
105 			continue;
106 
107 		len = diff_chunk_get_right_count(c);
108 		if (len == 0)
109 			continue;
110 
111 		right_start = diff_chunk_get_right_start(c, diff_result, 0);
112 		right_count = diff_chunk_get_right_count(c);
113 
114 		lineno = right_start + 1;
115 		len = right_count;
116 		for (ln = lineno; ln < lineno + len; ln++) {
117 			err = annotate_line(blame, ln, commit_id, cb, arg);
118 			if (err)
119 				return err;
120 			if (blame->nlines == blame->nannotated)
121 				break;
122 		}
123 	}
124 
125 	return NULL;
126 }
127 
128 static const struct got_error *
129 blame_commit(struct got_blame *blame, struct got_object_id *parent_id,
130     struct got_object_id *id, const char *path, struct got_repository *repo,
131     const struct got_error *(*cb)(void *, int, int, struct got_object_id *),
132     void *arg)
133 {
134 	const struct got_error *err = NULL;
135 	struct got_object *obj = NULL;
136 	struct got_object_id *obj_id = NULL;
137 	struct got_commit_object *commit = NULL;
138 	struct got_blob_object *blob = NULL;
139 	struct got_diffreg_result *diffreg_result = NULL;
140 
141 	err = got_object_open_as_commit(&commit, repo, parent_id);
142 	if (err)
143 		return err;
144 
145 	err = got_object_id_by_path(&obj_id, repo, parent_id, path);
146 	if (err) {
147 		if (err->code == GOT_ERR_NO_TREE_ENTRY)
148 			err = NULL;
149 		goto done;
150 	}
151 
152 	err = got_object_open(&obj, repo, obj_id);
153 	if (err)
154 		goto done;
155 
156 	if (obj->type != GOT_OBJ_TYPE_BLOB) {
157 		err = got_error_path(path, GOT_ERR_OBJ_TYPE);
158 		goto done;
159 	}
160 
161 	err = got_object_blob_open(&blob, repo, obj, 8192);
162 	if (err)
163 		goto done;
164 
165 	if (fseek(blame->f, 0L, SEEK_SET) == -1) {
166 		err = got_ferror(blame->f, GOT_ERR_IO);
167 		goto done;
168 	}
169 
170 	diff_data_free(&blame->left_data);
171 	memset(&blame->left_data, 0, sizeof(blame->left_data));
172 	err = got_diff_blob_prepared_file(&diffreg_result, &blame->left_data,
173 	    blob, &blame->right_data, blame->f, blame->map, blame->filesize,
174 	    blame->cfg, 0);
175 	if (err)
176 		goto done;
177 
178 	if (diffreg_result->result->chunks.len > 0) {
179 		err = blame_changes(blame, diffreg_result->result, id, cb, arg);
180 	} else if (cb)
181 		err = cb(arg, blame->nlines, -1, id);
182 done:
183 	if (diffreg_result) {
184 		const struct got_error *free_err;
185 		free_err = got_diffreg_result_free_left(diffreg_result);
186 		if (free_err && err == NULL)
187 			err = free_err;
188 	}
189 	if (commit)
190 		got_object_commit_close(commit);
191 	free(obj_id);
192 	if (obj)
193 		got_object_close(obj);
194 	if (blob)
195 		got_object_blob_close(blob);
196 	return err;
197 }
198 
199 static const struct got_error *
200 blame_close(struct got_blame *blame)
201 {
202 	const struct got_error *err = NULL;
203 
204 	diff_data_free(&blame->left_data);
205 	diff_data_free(&blame->right_data);
206 	if (blame->map && munmap(blame->map, blame->filesize) == -1)
207 		err = got_error_from_errno("munmap");
208 	if (blame->f && fclose(blame->f) != 0 && err == NULL)
209 		err = got_error_from_errno("fclose");
210 	free(blame->lines);
211 	free(blame);
212 	return err;
213 }
214 
215 static const struct got_error *
216 blame_open(struct got_blame **blamep, const char *path,
217     struct got_object_id *start_commit_id, struct got_repository *repo,
218     const struct got_error *(*cb)(void *, int, int, struct got_object_id *),
219     void *arg, got_cancel_cb cancel_cb, void *cancel_arg)
220 {
221 	const struct got_error *err = NULL;
222 	struct got_object *obj = NULL;
223 	struct got_object_id *obj_id = NULL;
224 	struct got_blob_object *blob = NULL;
225 	struct got_blame *blame = NULL;
226 	struct got_object_id *id = NULL, *pid = NULL;
227 	int lineno, created;
228 	size_t size;
229 	struct got_commit_graph *graph = NULL;
230 
231 	*blamep = NULL;
232 
233 	err = got_object_id_by_path(&obj_id, repo, start_commit_id, path);
234 	if (err)
235 		return err;
236 
237 	err = got_object_open(&obj, repo, obj_id);
238 	if (err)
239 		goto done;
240 
241 	if (obj->type != GOT_OBJ_TYPE_BLOB) {
242 		err = got_error_path(path, GOT_ERR_OBJ_TYPE);
243 		goto done;
244 	}
245 
246 	err = got_object_blob_open(&blob, repo, obj, 8192);
247 	if (err)
248 		goto done;
249 
250 	blame = calloc(1, sizeof(*blame));
251 	if (blame == NULL)
252 		return got_error_from_errno("calloc");
253 
254 	blame->f = got_opentemp();
255 	if (blame->f == NULL) {
256 		err = got_error_from_errno("got_opentemp");
257 		goto done;
258 	}
259 	err = got_object_blob_dump_to_file(&blame->filesize, &blame->nlines,
260 	    &blame->line_offsets, blame->f, blob);
261 	if (err || blame->nlines == 0)
262 		goto done;
263 
264 	blame->cfg = got_diff_get_config(GOT_DIFF_ALGORITHM_PATIENCE),
265 	err = got_diff_prepare_file(&blame->f, &blame->map, &created, &size,
266 	    &blame->right_data, blame->cfg, 0);
267 	if (err)
268 		goto done;
269 
270 	/* Don't include \n at EOF in the blame line count. */
271 	if (blame->line_offsets[blame->nlines - 1] == blame->filesize)
272 		blame->nlines--;
273 
274 	blame->lines = calloc(blame->nlines, sizeof(*blame->lines));
275 	if (blame->lines == NULL) {
276 		err = got_error_from_errno("calloc");
277 		goto done;
278 	}
279 
280 	err = got_commit_graph_open(&graph, path, 1);
281 	if (err)
282 		return err;
283 	err = got_commit_graph_iter_start(graph, start_commit_id, repo,
284 	    cancel_cb, cancel_arg);
285 	if (err)
286 		goto done;
287 	id = start_commit_id;
288 	for (;;) {
289 		err = got_commit_graph_iter_next(&pid, graph, repo,
290 		    cancel_cb, cancel_arg);
291 		if (err) {
292 			if (err->code == GOT_ERR_ITER_COMPLETED)
293 				err = NULL;
294 			break;
295 		}
296 		if (pid) {
297 			err = blame_commit(blame, pid, id, path, repo, cb, arg);
298 			if (err) {
299 				if (err->code == GOT_ERR_ITER_COMPLETED)
300 					err = NULL;
301 				break;
302 			}
303 			if (blame->nannotated == blame->nlines)
304 				break;
305 		}
306 		id = pid;
307 	}
308 
309 	if (id && blame->nannotated < blame->nlines) {
310 		/* Annotate remaining non-annotated lines with last commit. */
311 		for (lineno = 1; lineno <= blame->nlines; lineno++) {
312 			err = annotate_line(blame, lineno, id, cb, arg);
313 			if (err)
314 				goto done;
315 		}
316 	}
317 
318 done:
319 	if (graph)
320 		got_commit_graph_close(graph);
321 	free(obj_id);
322 	if (obj)
323 		got_object_close(obj);
324 	if (blob)
325 		got_object_blob_close(blob);
326 	if (err) {
327 		if (blame)
328 			blame_close(blame);
329 	} else
330 		*blamep = blame;
331 
332 	return err;
333 }
334 
335 const struct got_error *
336 got_blame(const char *path, struct got_object_id *commit_id,
337     struct got_repository *repo,
338     const struct got_error *(*cb)(void *, int, int, struct got_object_id *),
339     void *arg, got_cancel_cb cancel_cb, void* cancel_arg)
340 {
341 	const struct got_error *err = NULL, *close_err = NULL;
342 	struct got_blame *blame;
343 	char *abspath;
344 
345 	if (asprintf(&abspath, "%s%s", path[0] == '/' ? "" : "/", path) == -1)
346 		return got_error_from_errno2("asprintf", path);
347 
348 	err = blame_open(&blame, abspath, commit_id, repo, cb, arg,
349 	    cancel_cb, cancel_arg);
350 	free(abspath);
351 	if (blame)
352 		close_err = blame_close(blame);
353 	return err ? err : close_err;
354 }