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