1 /*
2  * Copyright (c) 2018, 2019, 2020 Stefan Sperling <stsp@openbsd.org>
3  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
4  *
5  * Permission to use, copy, modify, and distribute this software for any
6  * purpose with or without fee is hereby granted, provided that the above
7  * copyright notice and this permission notice appear in all copies.
8  *
9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16  */
17 
18 #include <sys/queue.h>
19 #include <sys/mman.h>
20 #include <sys/stat.h>
21 
22 #include <sha1.h>
23 #include <string.h>
24 #include <stdbool.h>
25 #include <stdio.h>
26 #include <stdlib.h>
27 #include <time.h>
28 #include <limits.h>
29 #include <util.h>
30 #include <zlib.h>
31 
32 #include "got_error.h"
33 #include "got_object.h"
34 #include "got_cancel.h"
35 #include "got_blame.h"
36 #include "got_commit_graph.h"
37 #include "got_opentemp.h"
38 
39 #include "got_lib_inflate.h"
40 #include "got_lib_delta.h"
41 #include "got_lib_object.h"
42 #include "got_lib_diff.h"
43 
44 #ifndef MAX
45 #define	MAX(_a,_b) ((_a) > (_b) ? (_a) : (_b))
46 #endif
47 
48 struct got_blame_line {
49 	int annotated;
50 	struct got_object_id id;
51 };
52 
53 struct got_blame {
54 	FILE *f;
55 	off_t size;
56 	struct diff_config *cfg;
57 	off_t filesize;
58 	int nlines;
59 	int nannotated;
60 	struct got_blame_line *lines; /* one per line */
61 	off_t *line_offsets;		/* one per line */
62 	int ncommits;
63 
64 	/*
65 	 * Map line numbers of an older version of the file to valid line
66 	 * numbers in blame->f. This map is updated with each commit we
67 	 * traverse throughout the file's history.
68 	 * Lines mapped to -1 do not correspond to any line in blame->f.
69 	 */
70 	int *linemap2;
71 	int nlines2;
72 };
73 
74 static const struct got_error *
75 annotate_line(struct got_blame *blame, int lineno, struct got_object_id *id,
76     const struct got_error *(*cb)(void *, int, int, struct got_object_id *),
77     void *arg)
78 {
79 	const struct got_error *err = NULL;
80 	struct got_blame_line *line;
81 
82 	if (lineno < 0 || lineno >= blame->nlines)
83 		return NULL;
84 
85 	line = &blame->lines[lineno];
86 	if (line->annotated)
87 		return NULL;
88 
89 	memcpy(&line->id, id, sizeof(line->id));
90 	line->annotated = 1;
91 	blame->nannotated++;
92 	if (cb)
93 		err = cb(arg, blame->nlines, lineno + 1, id);
94 	return err;
95 }
96 
97 static const struct got_error *
98 blame_changes(struct got_blame *blame, int *linemap1,
99     struct diff_result *diff_result, struct got_object_id *commit_id,
100     const struct got_error *(*cb)(void *, int, int, struct got_object_id *),
101     void *arg)
102 {
103 	const struct got_error *err = NULL;
104 	int i;
105 	int idx1 = 0, idx2 = 0;
106 
107 	for (i = 0; i < diff_result->chunks.len &&
108 	    blame->nannotated < blame->nlines; i++) {
109 		struct diff_chunk *c = diff_chunk_get(diff_result, i);
110 		unsigned int left_start, left_count;
111 		unsigned int right_start, right_count;
112 		int j;
113 
114 		/*
115 		 * We do not need to worry about idx1/idx2 growing out
116 		 * of bounds because the diff implementation ensures
117 		 * that chunk ranges never exceed the number of lines
118 		 * in the left/right input files.
119 		 */
120 		left_start = diff_chunk_get_left_start(c, diff_result, 0);
121 		left_count = diff_chunk_get_left_count(c);
122 		right_start = diff_chunk_get_right_start(c, diff_result, 0);
123 		right_count = diff_chunk_get_right_count(c);
124 
125 		if (left_count == right_count) {
126 			for (j = 0; j < left_count; j++) {
127 				linemap1[idx1++] = blame->linemap2[idx2++];
128 			}
129 			continue;
130 		}
131 
132 		if (right_count == 0) {
133 			for (j = 0; j < left_count; j++) {
134 				linemap1[idx1++] = -1;
135 			}
136 			continue;
137 		}
138 
139 		for (j = 0; j < right_count; j++) {
140 			int ln = blame->linemap2[idx2++];
141 			err = annotate_line(blame, ln, commit_id, cb, arg);
142 			if (err)
143 				return err;
144 			if (blame->nlines == blame->nannotated)
145 				break;
146 		}
147 	}
148 
149 	return NULL;
150 }
151 
152 static const struct got_error *
153 blame_commit(struct got_blame *blame, struct got_object_id *id,
154     const char *path, struct got_repository *repo,
155     const struct got_error *(*cb)(void *, int, int, struct got_object_id *),
156     void *arg)
157 {
158 	const struct got_error *err = NULL;
159 	struct got_commit_object *commit = NULL;
160 	struct got_object_qid *pid = NULL;
161 	struct got_object_id *blob_id = NULL, *pblob_id = NULL;
162 	struct got_blob_object *blob = NULL, *pblob = NULL;
163 	struct got_diffreg_result *diffreg_result = NULL;
164 	FILE *f1 = NULL, *f2 = NULL;
165 	off_t size1, size2;
166 	int nlines1, nlines2;
167 	int *linemap1 = NULL;
168 
169 	err = got_object_open_as_commit(&commit, repo, id);
170 	if (err)
171 		return err;
172 
173 	pid = SIMPLEQ_FIRST(got_object_commit_get_parent_ids(commit));
174 	if (pid == NULL) {
175 		got_object_commit_close(commit);
176 		return NULL;
177 	}
178 
179 	err = got_object_id_by_path(&blob_id, repo, id, path);
180 	if (err) {
181 		if (err->code == GOT_ERR_NO_TREE_ENTRY)
182 			err = NULL;
183 		goto done;
184 	}
185 
186 	err = got_object_open_as_blob(&blob, repo, blob_id, 8192);
187 	if (err)
188 		goto done;
189 
190 	f2 = got_opentemp();
191 	if (f2 == NULL) {
192 		err = got_error_from_errno("got_opentemp");
193 		goto done;
194 	}
195 	err = got_object_blob_dump_to_file(&size2, &nlines2, NULL,
196 	    f2, blob);
197 	if (err)
198 		goto done;
199 
200 	err = got_object_id_by_path(&pblob_id, repo, pid->id, path);
201 	if (err) {
202 		if (err->code == GOT_ERR_NO_TREE_ENTRY)
203 			err = NULL;
204 		goto done;
205 	}
206 
207 	err = got_object_open_as_blob(&pblob, repo, pblob_id, 8192);
208 	if (err)
209 		goto done;
210 
211 	f1 = got_opentemp();
212 	if (f1 == NULL) {
213 		err = got_error_from_errno("got_opentemp");
214 		goto done;
215 	}
216 	err = got_object_blob_dump_to_file(&size1, &nlines1, NULL, f1, pblob);
217 	if (err)
218 		goto done;
219 
220 	err = got_diff_files(&diffreg_result, f1, "", f2, "",
221 	    0, 0, NULL);
222 	if (err)
223 		goto done;
224 	if (diffreg_result->result->chunks.len > 0) {
225 		if (nlines1 > 0) {
226 			linemap1 = calloc(nlines1, sizeof(*linemap1));
227 			if (linemap1 == NULL) {
228 				err = got_error_from_errno("malloc");
229 				goto done;
230 			}
231 		}
232 		err = blame_changes(blame, linemap1,
233 		    diffreg_result->result, id, cb, arg);
234 		if (err) {
235 			free(linemap1);
236 			goto done;
237 		}
238 		if (linemap1) {
239 			free(blame->linemap2);
240 			blame->linemap2 = linemap1;
241 			blame->nlines2 = nlines1;
242 		}
243 	} else if (cb)
244 		err = cb(arg, blame->nlines, -1, id);
245 done:
246 	if (diffreg_result) {
247 		const struct got_error *free_err;
248 		free_err = got_diffreg_result_free(diffreg_result);
249 		if (free_err && err == NULL)
250 			err = free_err;
251 	}
252 	if (commit)
253 		got_object_commit_close(commit);
254 	free(blob_id);
255 	free(pblob_id);
256 	if (blob)
257 		got_object_blob_close(blob);
258 	if (pblob)
259 		got_object_blob_close(pblob);
260 	if (f1 && fclose(f1) != 0 && err == NULL)
261 		err = got_error_from_errno("fclose");
262 	if (f2 && fclose(f2) != 0 && err == NULL)
263 		err = got_error_from_errno("fclose");
264 	return err;
265 }
266 
267 static const struct got_error *
268 blame_close(struct got_blame *blame)
269 {
270 	const struct got_error *err = NULL;
271 
272 	if (blame->f && fclose(blame->f) != 0 && err == NULL)
273 		err = got_error_from_errno("fclose");
274 	free(blame->lines);
275 	free(blame->linemap2);
276 	free(blame->cfg);
277 	free(blame);
278 	return err;
279 }
280 
281 static const struct got_error *
282 blame_open(struct got_blame **blamep, const char *path,
283     struct got_object_id *start_commit_id, struct got_repository *repo,
284     const struct got_error *(*cb)(void *, int, int, struct got_object_id *),
285     void *arg, got_cancel_cb cancel_cb, void *cancel_arg)
286 {
287 	const struct got_error *err = NULL;
288 	struct got_object *obj = NULL;
289 	struct got_object_id *obj_id = NULL;
290 	struct got_blob_object *blob = NULL;
291 	struct got_blame *blame = NULL;
292 	struct got_object_id *id = NULL;
293 	int lineno;
294 	struct got_commit_graph *graph = NULL;
295 
296 	*blamep = NULL;
297 
298 	err = got_object_id_by_path(&obj_id, repo, start_commit_id, path);
299 	if (err)
300 		goto done;
301 
302 	err = got_object_open(&obj, repo, obj_id);
303 	if (err)
304 		goto done;
305 
306 	if (obj->type != GOT_OBJ_TYPE_BLOB) {
307 		err = got_error_path(path, GOT_ERR_OBJ_TYPE);
308 		goto done;
309 	}
310 
311 	err = got_object_blob_open(&blob, repo, obj, 8192);
312 	if (err)
313 		goto done;
314 
315 	blame = calloc(1, sizeof(*blame));
316 	if (blame == NULL) {
317 		err = got_error_from_errno("calloc");
318 		goto done;
319 	}
320 
321 	blame->f = got_opentemp();
322 	if (blame->f == NULL) {
323 		err = got_error_from_errno("got_opentemp");
324 		goto done;
325 	}
326 	err = got_object_blob_dump_to_file(&blame->filesize, &blame->nlines,
327 	    &blame->line_offsets, blame->f, blob);
328 	if (err || blame->nlines == 0)
329 		goto done;
330 
331 	err = got_diff_get_config(&blame->cfg, GOT_DIFF_ALGORITHM_PATIENCE,
332 	    NULL, NULL);
333 	if (err)
334 		goto done;
335 
336 	/* Don't include \n at EOF in the blame line count. */
337 	if (blame->line_offsets[blame->nlines - 1] == blame->filesize)
338 		blame->nlines--;
339 
340 	blame->lines = calloc(blame->nlines, sizeof(*blame->lines));
341 	if (blame->lines == NULL) {
342 		err = got_error_from_errno("calloc");
343 		goto done;
344 	}
345 
346 	blame->nlines2 = blame->nlines;
347 	blame->linemap2 = calloc(blame->nlines2, sizeof(*blame->linemap2));
348 	if (blame->linemap2 == NULL) {
349 		err = got_error_from_errno("calloc");
350 		goto done;
351 	}
352 	for (lineno = 0; lineno < blame->nlines2; lineno++)
353 		blame->linemap2[lineno] = lineno;
354 
355 	err = got_commit_graph_open(&graph, path, 1);
356 	if (err)
357 		goto done;
358 
359 	err = got_commit_graph_iter_start(graph, start_commit_id, repo,
360 	    cancel_cb, cancel_arg);
361 	if (err)
362 		goto done;
363 	for (;;) {
364 		struct got_object_id *next_id;
365 		err = got_commit_graph_iter_next(&next_id, graph, repo,
366 		    cancel_cb, cancel_arg);
367 		if (err) {
368 			if (err->code == GOT_ERR_ITER_COMPLETED) {
369 				err = NULL;
370 				break;
371 			}
372 			goto done;
373 		}
374 		if (next_id) {
375 			id = next_id;
376 			err = blame_commit(blame, id, path, repo, cb, arg);
377 			if (err) {
378 				if (err->code == GOT_ERR_ITER_COMPLETED)
379 					err = NULL;
380 				goto done;
381 			}
382 			if (blame->nannotated == blame->nlines)
383 				break;
384 		}
385 	}
386 
387 	if (id && blame->nannotated < blame->nlines) {
388 		/* Annotate remaining non-annotated lines with last commit. */
389 		for (lineno = 0; lineno < blame->nlines; lineno++) {
390 			err = annotate_line(blame, lineno, id, cb, arg);
391 			if (err)
392 				goto done;
393 		}
394 	}
395 
396 done:
397 	if (graph)
398 		got_commit_graph_close(graph);
399 	free(obj_id);
400 	if (obj)
401 		got_object_close(obj);
402 	if (blob)
403 		got_object_blob_close(blob);
404 	if (err) {
405 		if (blame)
406 			blame_close(blame);
407 	} else
408 		*blamep = blame;
409 
410 	return err;
411 }
412 
413 const struct got_error *
414 got_blame(const char *path, struct got_object_id *commit_id,
415     struct got_repository *repo,
416     const struct got_error *(*cb)(void *, int, int, struct got_object_id *),
417     void *arg, got_cancel_cb cancel_cb, void* cancel_arg)
418 {
419 	const struct got_error *err = NULL, *close_err = NULL;
420 	struct got_blame *blame;
421 	char *abspath;
422 
423 	if (asprintf(&abspath, "%s%s", path[0] == '/' ? "" : "/", path) == -1)
424 		return got_error_from_errno2("asprintf", path);
425 
426 	err = blame_open(&blame, abspath, commit_id, repo, cb, arg,
427 	    cancel_cb, cancel_arg);
428 	free(abspath);
429 	if (blame)
430 		close_err = blame_close(blame);
431 	return err ? err : close_err;
432 }