1 /*
2  * Copyright (c) 2018 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/types.h>
18 #include <sys/stat.h>
19 #include <sys/queue.h>
20 #include <sys/stdint.h>
21 
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include <sha1.h>
26 #include <zlib.h>
27 #include <ctype.h>
28 
29 #include "got_error.h"
30 #include "got_object.h"
31 #include "got_commit_graph.h"
32 
33 #include "got_lib_delta.h"
34 #include "got_lib_inflate.h"
35 #include "got_lib_object.h"
36 #include "got_lib_object_idset.h"
37 #include "got_lib_path.h"
38 
39 struct got_commit_graph_node {
40 	struct got_object_id id;
41 	time_t timestamp;
42 
43 	/* Used during graph iteration. */
44 	TAILQ_ENTRY(got_commit_graph_node) entry;
45 };
46 
47 TAILQ_HEAD(got_commit_graph_iter_list, got_commit_graph_node);
48 
49 struct got_commit_graph_branch_tip {
50 	struct got_object_id *commit_id;
51 	struct got_commit_object *commit;
52 	struct got_commit_graph_node *new_node;
53 	int changed;
54 	int branch_done;
55 };
56 
57 struct got_commit_graph {
58 	/* The set of all commits we have traversed. */
59 	struct got_object_idset *node_ids;
60 
61 	/* The commit at which traversal began (youngest commit in node_ids). */
62 	struct got_commit_graph_node *head_node;
63 
64 	int flags;
65 #define GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL		0x01
66 
67 	/*
68 	 * A set of object IDs of known parent commits which we have not yet
69 	 * traversed. Each commit ID in this set represents a branch in commit
70 	 * history: Either the first-parent branch of the head node, or another
71 	 * branch corresponding to a traversed merge commit for which we have
72 	 * not traversed a branch point commit yet.
73 	 *
74 	 * Whenever we add a commit with a matching ID to the graph, we remove
75 	 * its corresponding element from this set, and add new elements for
76 	 * each of that commit's parent commits which were not traversed yet.
77 	 *
78 	 * When API users ask us to fetch more commits, we fetch commits from
79 	 * all currently open branches. This allows API users to process
80 	 * commits in linear order even though the history contains branches.
81 	 */
82 	struct got_object_idset *open_branches;
83 
84 	/* Array of branch tips for fetch_commits_from_open_branches(). */
85 	struct got_commit_graph_branch_tip *tips;
86 	int ntips;
87 
88 	/* Path of tree entry of interest to the API user. */
89 	char *path;
90 
91 	/* The next commit to return when the API user asks for one. */
92 	struct got_commit_graph_node *iter_node;
93 
94 	/* The graph iteration list contains all nodes in sorted order. */
95 	struct got_commit_graph_iter_list iter_list;
96 };
97 
98 static struct got_commit_graph *
99 alloc_graph(const char *path)
100 {
101 	struct got_commit_graph *graph;
102 
103 	graph = calloc(1, sizeof(*graph));
104 	if (graph == NULL)
105 		return NULL;
106 
107 	graph->path = strdup(path);
108 	if (graph->path == NULL) {
109 		free(graph);
110 		return NULL;
111 	}
112 
113 	graph->node_ids = got_object_idset_alloc();
114 	if (graph->node_ids == NULL) {
115 		free(graph->path);
116 		free(graph);
117 		return NULL;
118 	}
119 
120 	graph->open_branches = got_object_idset_alloc();
121 	if (graph->open_branches == NULL) {
122 		got_object_idset_free(graph->node_ids);
123 		free(graph->path);
124 		free(graph);
125 		return NULL;
126 	}
127 
128 	TAILQ_INIT(&graph->iter_list);
129 	return graph;
130 }
131 
132 static const struct got_error *
133 detect_changed_path(int *changed, struct got_commit_object *commit,
134     struct got_object_id *commit_id, const char *path,
135     struct got_repository *repo)
136 {
137 	const struct got_error *err = NULL;
138 	struct got_commit_object *pcommit = NULL;
139 	struct got_tree_object *tree = NULL, *ptree = NULL;
140 	struct got_object_qid *pid;
141 
142 	if (got_path_is_root_dir(path)) {
143 		*changed = 1;
144 		return NULL;
145 	}
146 
147 	*changed = 0;
148 
149 	pid = SIMPLEQ_FIRST(&commit->parent_ids);
150 	if (pid == NULL) {
151 		struct got_object_id *obj_id;
152 		err = got_object_id_by_path(&obj_id, repo, commit_id, path);
153 		if (err) {
154 			if (err->code == GOT_ERR_NO_TREE_ENTRY)
155 				err = NULL;
156 		} else
157 			*changed = 1; /* The path was created in this commit. */
158 		free(obj_id);
159 		return err;
160 	}
161 
162 	err = got_object_open_as_tree(&tree, repo, commit->tree_id);
163 	if (err)
164 		return err;
165 
166 	err = got_object_open_as_commit(&pcommit, repo, pid->id);
167 	if (err)
168 		goto done;
169 
170 	err = got_object_open_as_tree(&ptree, repo, pcommit->tree_id);
171 	if (err)
172 		goto done;
173 
174 	err = got_object_tree_path_changed(changed, tree, ptree, path, repo);
175 done:
176 	if (tree)
177 		got_object_tree_close(tree);
178 	if (ptree)
179 		got_object_tree_close(ptree);
180 	if (pcommit)
181 		got_object_commit_close(pcommit);
182 	return err;
183 }
184 
185 static void
186 add_node_to_iter_list(struct got_commit_graph *graph,
187     struct got_commit_graph_node *node,
188     struct got_commit_graph_node *child_node)
189 {
190 	struct got_commit_graph_node *n, *next;
191 
192 	if (TAILQ_EMPTY(&graph->iter_list)) {
193 		TAILQ_INSERT_HEAD(&graph->iter_list, node, entry);
194 		graph->iter_node = node;
195 		return;
196 	}
197 
198 	n = graph->iter_node;
199 	/* Ensure that an iteration in progress will see this new commit. */
200 	while (n) {
201 		next = TAILQ_NEXT(n, entry);
202 		if (next && node->timestamp >= next->timestamp) {
203 			TAILQ_INSERT_BEFORE(next, node, entry);
204 			return;
205 		}
206 		n = next;
207 	}
208 	TAILQ_INSERT_TAIL(&graph->iter_list, node, entry);
209 }
210 
211 static const struct got_error *
212 close_branch(struct got_commit_graph *graph, struct got_object_id *commit_id)
213 {
214 	const struct got_error *err;
215 
216 	err = got_object_idset_remove(NULL, graph->open_branches, commit_id);
217 	if (err && err->code != GOT_ERR_NO_OBJ)
218 		return err;
219 	return NULL;
220 }
221 
222 static const struct got_error *
223 advance_branch(struct got_commit_graph *graph,
224     struct got_commit_graph_node *node,
225     struct got_object_id *commit_id, struct got_commit_object *commit,
226     struct got_repository *repo)
227 {
228 	const struct got_error *err;
229 	struct got_object_qid *qid;
230 
231 	err = close_branch(graph, commit_id);
232 	if (err)
233 		return err;
234 
235 	if (graph->flags & GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL) {
236 		qid = SIMPLEQ_FIRST(&commit->parent_ids);
237 		if (qid == NULL ||
238 		    got_object_idset_get(graph->open_branches, qid->id))
239 			return NULL;
240 		return got_object_idset_add(graph->open_branches,
241 		    qid->id, node);
242 	}
243 
244 	/*
245 	 * If we are graphing commits for a specific path, skip branches
246 	 * which do not contribute any content to this path.
247 	 */
248 	if (commit->nparents > 1 && !got_path_is_root_dir(graph->path)) {
249 		struct got_object_id *merged_id, *prev_id = NULL;
250 		int branches_differ = 0;
251 
252 		err = got_object_id_by_path(&merged_id, repo, commit_id,
253 		    graph->path);
254 		if (err)
255 			return err;
256 
257 		SIMPLEQ_FOREACH(qid, &commit->parent_ids, entry) {
258 			struct got_object_id *id;
259 
260 			if (got_object_idset_get(graph->open_branches, qid->id))
261 				continue;
262 
263 			err = got_object_id_by_path(&id, repo, qid->id,
264 			    graph->path);
265 			if (err) {
266 				if (err->code == GOT_ERR_NO_TREE_ENTRY) {
267 					branches_differ = 1;
268 					continue;
269 				}
270 				free(merged_id);
271 				free(prev_id);
272 				return err;
273 			}
274 
275 			if (prev_id) {
276 				if (!branches_differ &&
277 				    got_object_id_cmp(id, prev_id) != 0)
278 					branches_differ = 1;
279 				free(prev_id);
280 			}
281 			prev_id = id;
282 
283 			/*
284 			 * If a branch has created the merged content we can
285 			 * skip any other branches.
286 			 */
287 			if (got_object_id_cmp(merged_id, id) == 0) {
288 				err = got_object_idset_add(graph->open_branches,
289 				    qid->id, node);
290 				free(merged_id);
291 				free(id);
292 				return err;
293 			}
294 		}
295 
296 		free(prev_id);
297 		prev_id = NULL;
298 		free(merged_id);
299 		merged_id = NULL;
300 
301 		/*
302 		 * If the path's content is the same on all branches,
303 		 * follow the first parent only.
304 		 */
305 		if (!branches_differ) {
306 			qid = SIMPLEQ_FIRST(&commit->parent_ids);
307 			if (qid == NULL)
308 				return NULL;
309 			if (got_object_idset_get(graph->open_branches, qid->id))
310 				return NULL;
311 			if (got_object_idset_get(graph->node_ids, qid->id))
312 				return NULL; /* parent already traversed */
313 			return got_object_idset_add(graph->open_branches,
314 			    qid->id, node);
315 		}
316 	}
317 
318 	SIMPLEQ_FOREACH(qid, &commit->parent_ids, entry) {
319 		if (got_object_idset_get(graph->open_branches, qid->id))
320 			continue;
321 		if (got_object_idset_get(graph->node_ids, qid->id))
322 			continue; /* parent already traversed */
323 		err = got_object_idset_add(graph->open_branches, qid->id, node);
324 		if (err)
325 			return err;
326 	}
327 
328 	return NULL;
329 }
330 
331 static const struct got_error *
332 add_node(struct got_commit_graph_node **new_node, int *changed,
333     int *branch_done, struct got_commit_graph *graph,
334     struct got_object_id *commit_id, struct got_commit_object *commit,
335     struct got_commit_graph_node *child_node, struct got_repository *repo)
336 {
337 	const struct got_error *err = NULL;
338 	struct got_commit_graph_node *node;
339 
340 	*new_node = NULL;
341 	*changed = 0;
342 	*branch_done = 0;
343 
344 	node = calloc(1, sizeof(*node));
345 	if (node == NULL)
346 		return got_error_from_errno();
347 
348 	memcpy(&node->id, commit_id, sizeof(node->id));
349 	node->timestamp = commit->committer_time;
350 
351 	err = got_object_idset_add(graph->node_ids, &node->id, node);
352 	if (err) {
353 		free(node);
354 		return err;
355 	}
356 
357 	err = detect_changed_path(changed, commit, commit_id, graph->path,
358 	    repo);
359 	if (err) {
360 		if (err->code == GOT_ERR_NO_OBJ) {
361 			/*
362 			 * History of the path stops here on the current
363 			 * branch. Keep going on other branches.
364 			 */
365 			err = NULL;
366 			*branch_done = 1;
367 		} else {
368 			got_object_idset_remove(NULL, graph->node_ids,
369 			    &node->id);
370 			free(node);
371 			return err;
372 		}
373 	}
374 
375 	if (*changed)
376 		add_node_to_iter_list(graph, node, child_node);
377 	*new_node = node;
378 	return NULL;
379 }
380 
381 const struct got_error *
382 got_commit_graph_open(struct got_commit_graph **graph,
383     struct got_object_id *commit_id, const char *path,
384     int first_parent_traversal, struct got_repository *repo)
385 {
386 	const struct got_error *err = NULL;
387 	struct got_commit_object *commit;
388 	int changed, branch_done;
389 
390 	*graph = NULL;
391 
392 	err = got_object_open_as_commit(&commit, repo, commit_id);
393 	if (err)
394 		return err;
395 
396 	/* The path must exist in our initial commit. */
397 	if (!got_path_is_root_dir(path)) {
398 		struct got_object_id *obj_id;
399 		err = got_object_id_by_path(&obj_id, repo, commit_id, path);
400 		if (err)
401 			return err;
402 		free(obj_id);
403 	}
404 
405 	*graph = alloc_graph(path);
406 	if (*graph == NULL) {
407 		got_object_commit_close(commit);
408 		return got_error_from_errno();
409 	}
410 
411 	if (first_parent_traversal)
412 		(*graph)->flags |= GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL;
413 
414 	err = add_node(&(*graph)->head_node, &changed, &branch_done, *graph,
415 	    commit_id, commit, NULL, repo);
416 	if (err == NULL) {
417 		err = advance_branch(*graph, (*graph)->head_node, commit_id,
418 		    commit, repo);
419 	}
420 	got_object_commit_close(commit);
421 	if (err) {
422 		got_commit_graph_close(*graph);
423 		*graph = NULL;
424 		return err;
425 	}
426 	
427 	return NULL;
428 }
429 
430 struct add_branch_tip_arg {
431 	struct got_commit_graph_branch_tip *tips;
432 	int ntips;
433 	struct got_repository *repo;
434 	struct got_commit_graph *graph;
435 };
436 
437 static const struct got_error *
438 add_branch_tip(struct got_object_id *commit_id, void *data, void *arg)
439 {
440 	const struct got_error *err;
441 	struct got_commit_graph_node *child_node = data;
442 	struct add_branch_tip_arg *a = arg;
443 	struct got_commit_graph_node *new_node;
444 	struct got_commit_object *commit;
445 	int changed, branch_done;
446 
447 	err = got_object_open_as_commit(&commit, a->repo, commit_id);
448 	if (err)
449 		return err;
450 
451 	err = add_node(&new_node, &changed, &branch_done, a->graph,
452 	    commit_id, commit, child_node, a->repo);
453 	if (err)
454 		return err;
455 
456 	a->tips[a->ntips].commit_id = new_node ? &new_node->id : NULL;
457 	a->tips[a->ntips].commit = commit;
458 	a->tips[a->ntips].new_node = new_node;
459 	a->tips[a->ntips].changed = changed;
460 	a->tips[a->ntips].branch_done = branch_done;
461 	a->ntips++;
462 
463 	return NULL;
464 }
465 
466 static const struct got_error *
467 fetch_commits_from_open_branches(int *nfetched,
468     struct got_object_id **changed_id, struct got_commit_graph *graph,
469     struct got_repository *repo)
470 {
471 	const struct got_error *err;
472 	struct add_branch_tip_arg arg;
473 	int i, ntips;
474 
475 	*nfetched = 0;
476 	*changed_id = NULL;
477 
478 	ntips = got_object_idset_num_elements(graph->open_branches);
479 	if (ntips == 0)
480 		return NULL;
481 
482 	/* (Re-)allocate branch tips array if necessary. */
483 	if (graph->ntips < ntips) {
484 		struct got_commit_graph_branch_tip *tips;
485 		tips = recallocarray(graph->tips, graph->ntips, ntips,
486 		    sizeof(*tips));
487 		if (tips == NULL)
488 			return got_error_from_errno();
489 		graph->tips = tips;
490 		graph->ntips = ntips;
491 	}
492 	arg.tips = graph->tips;
493 	arg.ntips = 0; /* add_branch_tip() will increment */
494 	arg.repo = repo;
495 	arg.graph = graph;
496 	err = got_object_idset_for_each(graph->open_branches, add_branch_tip,
497 	    &arg);
498 	if (err)
499 		goto done;
500 
501 	for (i = 0; i < arg.ntips; i++) {
502 		struct got_object_id *commit_id;
503 		struct got_commit_object *commit;
504 		struct got_commit_graph_node *new_node;
505 		int branch_done, changed;
506 
507 		commit_id = arg.tips[i].commit_id;
508 		commit = arg.tips[i].commit;
509 		new_node = arg.tips[i].new_node;
510 		branch_done = arg.tips[i].branch_done;
511 		changed = arg.tips[i].changed;
512 
513 		if (branch_done)
514 			err = close_branch(graph, commit_id);
515 		else
516 			err = advance_branch(graph, new_node, commit_id,
517 			    commit, repo);
518 		if (err)
519 			break;
520 		if (changed && *changed_id == NULL)
521 			*changed_id = commit_id;
522 	}
523 done:
524 	for (i = 0; i < arg.ntips; i++)
525 		got_object_commit_close(arg.tips[i].commit);
526 	(*nfetched) = arg.ntips;
527 	return err;
528 }
529 
530 const struct got_error *
531 got_commit_graph_fetch_commits(struct got_commit_graph *graph, int limit,
532     struct got_repository *repo)
533 {
534 	const struct got_error *err;
535 	int nfetched = 0, ncommits;
536 	struct got_object_id *changed_id = NULL;
537 
538 	while (nfetched < limit) {
539 		err = fetch_commits_from_open_branches(&ncommits,
540 		    &changed_id, graph, repo);
541 		if (err)
542 			return err;
543 		if (ncommits == 0)
544 			break;
545 		if (changed_id)
546 			nfetched += ncommits;
547 	}
548 
549 	return NULL;
550 }
551 
552 static const struct got_error *
553 free_node_iter(struct got_object_id *id, void *data, void *arg)
554 {
555 	struct got_commit_graph_node *node = data;
556 	free(node);
557 	return NULL;
558 }
559 
560 void
561 got_commit_graph_close(struct got_commit_graph *graph)
562 {
563 	got_object_idset_free(graph->open_branches);
564 	got_object_idset_for_each(graph->node_ids, free_node_iter, NULL);
565 	got_object_idset_free(graph->node_ids);
566 	free(graph->tips);
567 	free(graph->path);
568 	free(graph);
569 }
570 
571 const struct got_error *
572 got_commit_graph_iter_start(struct got_commit_graph *graph,
573     struct got_object_id *id, struct got_repository *repo)
574 {
575 	const struct got_error *err = NULL;
576 	struct got_commit_graph_node *start_node;
577 	struct got_commit_object *commit;
578 	int changed;
579 
580 	start_node = got_object_idset_get(graph->node_ids, id);
581 	if (start_node == NULL)
582 		return got_error_no_obj(id);
583 
584 	err = got_object_open_as_commit(&commit, repo, &start_node->id);
585 	if (err)
586 		return err;
587 
588 	err = detect_changed_path(&changed, commit, &start_node->id,
589 	    graph->path, repo);
590 	if (err) {
591 		got_object_commit_close(commit);
592 		return err;
593 	}
594 
595 	if (!changed) {
596 		/* Locate first commit which changed graph->path. */
597 		struct got_object_id *changed_id = NULL;
598 		while (changed_id == NULL) {
599 			int ncommits;
600 			err = fetch_commits_from_open_branches(&ncommits,
601 			    &changed_id, graph, repo);
602 			if (err) {
603 				got_object_commit_close(commit);
604 				return err;
605 			}
606 		}
607 		start_node = got_object_idset_get(graph->node_ids, changed_id);
608 	}
609 	got_object_commit_close(commit);
610 
611 	graph->iter_node = start_node;
612 	return NULL;
613 }
614 
615 const struct got_error *
616 got_commit_graph_iter_next(struct got_object_id **id,
617     struct got_commit_graph *graph)
618 {
619 	*id = NULL;
620 
621 	if (graph->iter_node == NULL) {
622 		/* We are done iterating, or iteration was not started. */
623 		return got_error(GOT_ERR_ITER_COMPLETED);
624 	}
625 
626 	if (graph->iter_node ==
627 	    TAILQ_LAST(&graph->iter_list, got_commit_graph_iter_list) &&
628 	    got_object_idset_num_elements(graph->open_branches) == 0) {
629 		/* We are done iterating. */
630 		*id = &graph->iter_node->id;
631 		graph->iter_node = NULL;
632 		return NULL;
633 	}
634 
635 	if (TAILQ_NEXT(graph->iter_node, entry) == NULL)
636 		return got_error(GOT_ERR_ITER_NEED_MORE);
637 
638 	*id = &graph->iter_node->id;
639 	graph->iter_node = TAILQ_NEXT(graph->iter_node, entry);
640 	return NULL;
641 }