graph.c 3.87 KB
Newer Older
1 2

/*
Edward Thomson committed
3
 * Copyright (C) the libgit2 contributors. All rights reserved.
4 5 6 7 8 9 10 11 12
 *
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
 */

#include "revwalk.h"
#include "merge.h"
#include "git2/graph.h"

13
static int interesting(git_pqueue *list, git_commit_list *roots)
14 15 16 17 18 19 20 21 22
{
	unsigned int i;
	/* element 0 isn't used - we need to start at 1 */
	for (i = 1; i < list->size; i++) {
		git_commit_list_node *commit = list->d[i];
		if ((commit->flags & STALE) == 0)
			return 1;
	}

23 24 25 26 27 28
	while(roots) {
		if ((roots->item->flags & STALE) == 0)
			return 1;
		roots = roots->next;
	}

29 30 31
	return 0;
}

32 33
static int mark_parents(git_revwalk *walk, git_commit_list_node *one,
	git_commit_list_node *two)
34 35
{
	unsigned int i;
36
	git_commit_list *roots = NULL;
37 38 39
	git_pqueue list;

	/* if the commit is repeated, we have a our merge base already */
40 41 42
	if (one == two) {
		one->flags |= PARENT1 | PARENT2 | RESULT;
		return 0;
43 44
	}

45
	if (git_pqueue_init(&list, 2, git_commit_list_time_cmp) < 0)
46 47 48
		return -1;

	if (git_commit_list_parse(walk, one) < 0)
49
		goto on_error;
50 51
	one->flags |= PARENT1;
	if (git_pqueue_insert(&list, one) < 0)
52
		goto on_error;
53

54
	if (git_commit_list_parse(walk, two) < 0)
55
		goto on_error;
56 57
	two->flags |= PARENT2;
	if (git_pqueue_insert(&list, two) < 0)
58
		goto on_error;
59 60

	/* as long as there are non-STALE commits */
61
	while (interesting(&list, roots)) {
62 63 64 65
		git_commit_list_node *commit;
		int flags;

		commit = git_pqueue_pop(&list);
66 67
		if (commit == NULL)
			break;
68 69 70

		flags = commit->flags & (PARENT1 | PARENT2 | STALE);
		if (flags == (PARENT1 | PARENT2)) {
71
			if (!(commit->flags & RESULT))
72 73 74 75 76 77 78 79 80 81
				commit->flags |= RESULT;
			/* we mark the parents of a merge stale */
			flags |= STALE;
		}

		for (i = 0; i < commit->out_degree; i++) {
			git_commit_list_node *p = commit->parents[i];
			if ((p->flags & flags) == flags)
				continue;

82 83
			if (git_commit_list_parse(walk, p) < 0)
				goto on_error;
84 85 86

			p->flags |= flags;
			if (git_pqueue_insert(&list, p) < 0)
87
				goto on_error;
88
		}
89

90
		/* Keep track of root commits, to make sure the path gets marked */
91 92
		if (commit->out_degree == 0) {
			if (git_commit_list_insert(commit, &roots) == NULL)
93
				goto on_error;
94
		}
95 96
	}

97
	git_commit_list_free(&roots);
98 99
	git_pqueue_free(&list);
	return 0;
100 101 102 103 104

on_error:
	git_commit_list_free(&roots);
	git_pqueue_free(&list);
	return -1;
105 106
}

107

108 109 110 111 112 113 114 115 116 117 118 119
static int ahead_behind(git_commit_list_node *one, git_commit_list_node *two,
	size_t *ahead, size_t *behind)
{
	git_commit_list_node *commit;
	git_pqueue pq;
	int i;
	*ahead = 0;
	*behind = 0;

	if (git_pqueue_init(&pq, 2, git_commit_list_time_cmp) < 0)
		return -1;
	if (git_pqueue_insert(&pq, one) < 0)
Carlos Martín Nieto committed
120
		goto on_error;
121
	if (git_pqueue_insert(&pq, two) < 0)
Carlos Martín Nieto committed
122
		goto on_error;
123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140

	while ((commit = git_pqueue_pop(&pq)) != NULL) {
		if (commit->flags & RESULT ||
			(commit->flags & (PARENT1 | PARENT2)) == (PARENT1 | PARENT2))
			continue;
		else if (commit->flags & PARENT1)
			(*behind)++;
		else if (commit->flags & PARENT2)
			(*ahead)++;

		for (i = 0; i < commit->out_degree; i++) {
			git_commit_list_node *p = commit->parents[i];
			if (git_pqueue_insert(&pq, p) < 0)
				return -1;
		}
		commit->flags |= RESULT;
	}

Carlos Martín Nieto committed
141
	git_pqueue_free(&pq);
142
	return 0;
Carlos Martín Nieto committed
143 144 145 146

on_error:
	git_pqueue_free(&pq);
	return -1;
147 148 149
}

int git_graph_ahead_behind(size_t *ahead, size_t *behind, git_repository *repo,
150
	const git_oid *local, const git_oid *upstream)
151 152
{
	git_revwalk *walk;
153
	git_commit_list_node *commit_u, *commit_l;
154 155 156 157

	if (git_revwalk_new(&walk, repo) < 0)
		return -1;

158 159
	commit_u = git_revwalk__commit_lookup(walk, upstream);
	if (commit_u == NULL)
160 161
		goto on_error;

162 163
	commit_l = git_revwalk__commit_lookup(walk, local);
	if (commit_l == NULL)
164 165
		goto on_error;

166
	if (mark_parents(walk, commit_l, commit_u) < 0)
167
		goto on_error;
168
	if (ahead_behind(commit_l, commit_u, ahead, behind) < 0)
169 170 171 172 173 174 175 176 177 178
		goto on_error;

	git_revwalk_free(walk);

	return 0;

on_error:
	git_revwalk_free(walk);
	return -1;
}