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 *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 			if (got_object_idset_get(graph->node_ids, qid->id))
307 				continue; /* parent already traversed */
308 
309 			err = got_object_id_by_path(&id, repo, qid->id,
310 			    graph->path);
311 			if (err) {
312 				if (err->code == GOT_ERR_NO_TREE_ENTRY) {
313 					branches_differ = 1;
314 					continue;
315 				}
316 				return err;
317 			}
318 
319 			if (prev_id) {
320 				if (!branches_differ &&
321 				    got_object_id_cmp(merged_id, prev_id) != 0)
322 					branches_differ = 1;
323 			} else
324 				prev_id = id;
325 
326 			/*
327 			 * If a branch has created the merged content we can
328 			 * skip any other branches.
329 			 */
330 			if (got_object_id_cmp(merged_id, id) == 0) {
331 				err = got_object_idset_add(graph->open_branches,
332 				    qid->id, node);
333 				return err;
334 			}
335 		}
336 
337 		/*
338 		 * If the path's content is the same on all branches,
339 		 * follow the first parent only.
340 		 */
341 		if (!branches_differ) {
342 			qid = SIMPLEQ_FIRST(&commit->parent_ids);
343 			if (qid == NULL)
344 				return NULL;
345 			if (got_object_idset_get(graph->node_ids, qid->id))
346 				return NULL; /* parent already traversed */
347 			if (got_object_idset_get(graph->open_branches, qid->id))
348 				return NULL;
349 			return got_object_idset_add(graph->open_branches,
350 			    qid->id, node);
351 		}
352 	}
353 
354 	SIMPLEQ_FOREACH(qid, &commit->parent_ids, entry) {
355 		if (got_object_idset_get(graph->node_ids, qid->id))
356 			continue; /* parent already traversed */
357 		if (got_object_idset_get(graph->open_branches, qid->id))
358 			continue;
359 		err = got_object_idset_add(graph->open_branches, qid->id, node);
360 		if (err)
361 			return err;
362 	}
363 
364 	return NULL;
365 }
366 
367 static void
368 free_node(struct got_commit_graph_node *node)
369 {
370 	while (!SIMPLEQ_EMPTY(&node->parent_ids)) {
371 		struct got_object_qid *pid = SIMPLEQ_FIRST(&node->parent_ids);
372 		SIMPLEQ_REMOVE_HEAD(&node->parent_ids, entry);
373 		got_object_qid_free(pid);
374 	}
375 	free(node);
376 }
377 
378 static const struct got_error *
379 add_node(struct got_commit_graph_node **new_node, int *changed,
380     int *branch_done, struct got_commit_graph *graph,
381     struct got_object_id *commit_id, struct got_commit_object *commit,
382     struct got_commit_graph_node *child_node, struct got_repository *repo)
383 {
384 	const struct got_error *err = NULL;
385 	struct got_commit_graph_node *node;
386 	struct got_object_qid *pid;
387 
388 	*new_node = NULL;
389 	*changed = 0;
390 	*branch_done = 0;
391 
392 	node = calloc(1, sizeof(*node));
393 	if (node == NULL)
394 		return got_error_from_errno();
395 
396 	memcpy(&node->id, commit_id, sizeof(node->id));
397 	SIMPLEQ_INIT(&node->parent_ids);
398 	SIMPLEQ_FOREACH(pid, &commit->parent_ids, entry) {
399 		err = add_vertex(&node->parent_ids, pid->id);
400 		if (err) {
401 			free_node(node);
402 			return err;
403 		}
404 		node->nparents++;
405 	}
406 	node->commit_timestamp = commit->committer_time;
407 
408 	err = got_object_idset_add(graph->node_ids, &node->id, node);
409 	if (err) {
410 		free_node(node);
411 		return err;
412 	}
413 
414 	err = detect_changed_path(changed, commit, commit_id, graph->path,
415 	    repo);
416 	if (err) {
417 		if (err->code == GOT_ERR_NO_OBJ) {
418 			/*
419 			 * History of the path stops here on the current
420 			 * branch. Keep going on other branches.
421 			 */
422 			err = NULL;
423 			*branch_done = 1;
424 		} else {
425 			free_node(node);
426 			return err;
427 		}
428 	}
429 
430 	if (*changed)
431 		add_node_to_iter_list(graph, node, child_node);
432 
433 	if (err)
434 		free_node(node);
435 	else
436 		*new_node = node;
437 
438 	return err;
439 }
440 
441 const struct got_error *
442 got_commit_graph_open(struct got_commit_graph **graph,
443     struct got_object_id *commit_id, const char *path,
444     int first_parent_traversal, struct got_repository *repo)
445 {
446 	const struct got_error *err = NULL;
447 	struct got_commit_object *commit;
448 	int changed, branch_done;
449 
450 	*graph = NULL;
451 
452 	err = got_object_open_as_commit(&commit, repo, commit_id);
453 	if (err)
454 		return err;
455 
456 	/* The path must exist in our initial commit. */
457 	if (!got_path_is_root_dir(path)) {
458 		struct got_object_id *obj_id;
459 		err = got_object_id_by_path(&obj_id, repo, commit_id, path);
460 		if (err)
461 			return err;
462 		free(obj_id);
463 	}
464 
465 	*graph = alloc_graph(path);
466 	if (*graph == NULL) {
467 		got_object_commit_close(commit);
468 		return got_error_from_errno();
469 	}
470 
471 	if (first_parent_traversal)
472 		(*graph)->flags |= GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL;
473 
474 	err = add_node(&(*graph)->head_node, &changed, &branch_done, *graph,
475 	    commit_id, commit, NULL, repo);
476 	if (err == NULL) {
477 		err = advance_branch(*graph, (*graph)->head_node, commit_id,
478 		    commit, repo);
479 	}
480 	got_object_commit_close(commit);
481 	if (err) {
482 		got_commit_graph_close(*graph);
483 		*graph = NULL;
484 		return err;
485 	}
486 	
487 	return NULL;
488 }
489 
490 struct add_branch_tip_arg {
491 	struct got_commit_graph_branch_tip *tips;
492 	int ntips;
493 	struct got_repository *repo;
494 	struct got_commit_graph *graph;
495 };
496 
497 static const struct got_error *
498 add_branch_tip(struct got_object_id *commit_id, void *data, void *arg)
499 {
500 	const struct got_error *err;
501 	struct got_commit_graph_node *child_node = data;
502 	struct add_branch_tip_arg *a = arg;
503 	struct got_commit_graph_node *new_node;
504 	struct got_commit_object *commit;
505 	int changed, branch_done;
506 
507 	err = got_object_open_as_commit(&commit, a->repo, commit_id);
508 	if (err)
509 		return err;
510 
511 	err = add_node(&new_node, &changed, &branch_done, a->graph,
512 	    commit_id, commit, child_node, a->repo);
513 	if (err)
514 		return err;
515 
516 	a->tips[a->ntips].commit_id = new_node ? &new_node->id : NULL;
517 	a->tips[a->ntips].commit = commit;
518 	a->tips[a->ntips].new_node = new_node;
519 	a->tips[a->ntips].changed = changed;
520 	a->tips[a->ntips].branch_done = branch_done;
521 	a->ntips++;
522 
523 	return NULL;
524 }
525 
526 static const struct got_error *
527 fetch_commits_from_open_branches(int *nfetched,
528     struct got_object_id **changed_id, struct got_commit_graph *graph,
529     struct got_repository *repo)
530 {
531 	const struct got_error *err;
532 	struct add_branch_tip_arg arg;
533 	int i, ntips;
534 
535 	*nfetched = 0;
536 	*changed_id = NULL;
537 
538 	ntips = got_object_idset_num_elements(graph->open_branches);
539 	if (ntips == 0)
540 		return NULL;
541 
542 	/* (Re-)allocate branch tips array if necessary. */
543 	if (graph->ntips < ntips) {
544 		struct got_commit_graph_branch_tip *tips;
545 		tips = recallocarray(graph->tips, graph->ntips, ntips,
546 		    sizeof(*tips));
547 		if (tips == NULL)
548 			return got_error_from_errno();
549 		graph->tips = tips;
550 		graph->ntips = ntips;
551 	}
552 	arg.tips = graph->tips;
553 	arg.ntips = 0; /* add_branch_tip() will increment */
554 	arg.repo = repo;
555 	arg.graph = graph;
556 	err = got_object_idset_for_each(graph->open_branches, add_branch_tip,
557 	    &arg);
558 	if (err)
559 		goto done;
560 
561 	for (i = 0; i < arg.ntips; i++) {
562 		struct got_object_id *commit_id;
563 		struct got_commit_object *commit;
564 		struct got_commit_graph_node *new_node;
565 		int branch_done, changed;
566 
567 		commit_id = arg.tips[i].commit_id;
568 		commit = arg.tips[i].commit;
569 		new_node = arg.tips[i].new_node;
570 		branch_done = arg.tips[i].branch_done;
571 		changed = arg.tips[i].changed;
572 
573 		if (branch_done)
574 			err = close_branch(graph, commit_id);
575 		else
576 			err = advance_branch(graph, new_node, commit_id,
577 			    commit, repo);
578 		if (err)
579 			break;
580 		if (changed && *changed_id == NULL)
581 			*changed_id = commit_id;
582 	}
583 done:
584 	for (i = 0; i < arg.ntips; i++)
585 		got_object_commit_close(arg.tips[i].commit);
586 	(*nfetched) = arg.ntips;
587 	return err;
588 }
589 
590 const struct got_error *
591 got_commit_graph_fetch_commits(struct got_commit_graph *graph, int limit,
592     struct got_repository *repo)
593 {
594 	const struct got_error *err;
595 	int nfetched = 0, ncommits;
596 	struct got_object_id *changed_id = NULL;
597 
598 	while (nfetched < limit) {
599 		err = fetch_commits_from_open_branches(&ncommits,
600 		    &changed_id, graph, repo);
601 		if (err)
602 			return err;
603 		if (ncommits == 0)
604 			break;
605 		if (changed_id)
606 			nfetched += ncommits;
607 	}
608 
609 	return NULL;
610 }
611 
612 static const struct got_error *
613 free_node_iter(struct got_object_id *id, void *data, void *arg)
614 {
615 	struct got_commit_graph_node *node = data;
616 	free_node(node);
617 	return NULL;
618 }
619 
620 void
621 got_commit_graph_close(struct got_commit_graph *graph)
622 {
623 	got_object_idset_free(graph->open_branches);
624 	got_object_idset_for_each(graph->node_ids, free_node_iter, NULL);
625 	got_object_idset_free(graph->node_ids);
626 	free(graph->tips);
627 	free(graph->path);
628 	free(graph);
629 }
630 
631 const struct got_error *
632 got_commit_graph_iter_start(struct got_commit_graph *graph,
633     struct got_object_id *id, struct got_repository *repo)
634 {
635 	const struct got_error *err = NULL;
636 	struct got_commit_graph_node *start_node;
637 	struct got_commit_object *commit;
638 	int changed;
639 
640 	start_node = got_object_idset_get(graph->node_ids, id);
641 	if (start_node == NULL)
642 		return got_error_no_obj(id);
643 
644 	err = got_object_open_as_commit(&commit, repo, &start_node->id);
645 	if (err)
646 		return err;
647 
648 	err = detect_changed_path(&changed, commit, &start_node->id,
649 	    graph->path, repo);
650 	if (err) {
651 		got_object_commit_close(commit);
652 		return err;
653 	}
654 
655 	if (!changed) {
656 		/* Locate first commit which changed graph->path. */
657 		struct got_object_id *changed_id = NULL;
658 		while (changed_id == NULL) {
659 			int ncommits;
660 			err = fetch_commits_from_open_branches(&ncommits,
661 			    &changed_id, graph, repo);
662 			if (err) {
663 				got_object_commit_close(commit);
664 				return err;
665 			}
666 		}
667 		start_node = got_object_idset_get(graph->node_ids, changed_id);
668 	}
669 	got_object_commit_close(commit);
670 
671 	graph->iter_node = start_node;
672 	return NULL;
673 }
674 
675 const struct got_error *
676 got_commit_graph_iter_next(struct got_object_id **id,
677     struct got_commit_graph *graph)
678 {
679 	*id = NULL;
680 
681 	if (graph->iter_node == NULL) {
682 		/* We are done iterating, or iteration was not started. */
683 		return got_error(GOT_ERR_ITER_COMPLETED);
684 	}
685 
686 	if (graph->iter_node ==
687 	    TAILQ_LAST(&graph->iter_list, got_commit_graph_iter_list) &&
688 	    got_object_idset_num_elements(graph->open_branches) == 0) {
689 		/* We are done iterating. */
690 		*id = &graph->iter_node->id;
691 		graph->iter_node = NULL;
692 		return NULL;
693 	}
694 
695 	if (TAILQ_NEXT(graph->iter_node, entry) == NULL)
696 		return got_error(GOT_ERR_ITER_NEED_MORE);
697 
698 	*id = &graph->iter_node->id;
699 	graph->iter_node = TAILQ_NEXT(graph->iter_node, entry);
700 	return NULL;
701 }