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