graph.c 5.48 KB
Newer Older
1
/*
Edward Thomson committed
2
 * Copyright (C) the libgit2 contributors. All rights reserved.
3 4 5 6 7
 *
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
 */

8 9
#include "common.h"

10 11 12 13
#include "revwalk.h"
#include "merge.h"
#include "git2/graph.h"

14
static int interesting(git_pqueue *list, git_commit_list *roots)
15 16
{
	unsigned int i;
17 18 19

	for (i = 0; i < git_pqueue_size(list); i++) {
		git_commit_list_node *commit = git_pqueue_get(list, i);
20 21 22 23
		if ((commit->flags & STALE) == 0)
			return 1;
	}

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

30 31 32
	return 0;
}

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

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

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

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

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

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

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
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;
113
	int error = 0, i;
114 115 116
	*ahead = 0;
	*behind = 0;

117
	if (git_pqueue_init(&pq, 0, 2, git_commit_list_time_cmp) < 0)
118
		return -1;
119 120 121 122

	if ((error = git_pqueue_insert(&pq, one)) < 0 ||
		(error = git_pqueue_insert(&pq, two)) < 0)
		goto done;
123 124 125 126 127 128 129

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

		for (i = 0; i < commit->out_degree; i++) {
			git_commit_list_node *p = commit->parents[i];
135 136
			if ((error = git_pqueue_insert(&pq, p)) < 0)
				goto done;
137 138 139 140
		}
		commit->flags |= RESULT;
	}

141
done:
Carlos Martín Nieto committed
142
	git_pqueue_free(&pq);
143
	return error;
144 145 146
}

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

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

155 156
	commit_u = git_revwalk__commit_lookup(walk, upstream);
	if (commit_u == NULL)
157 158
		goto on_error;

159 160
	commit_l = git_revwalk__commit_lookup(walk, local);
	if (commit_l == NULL)
161 162
		goto on_error;

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

	git_revwalk_free(walk);

	return 0;

on_error:
	git_revwalk_free(walk);
	return -1;
}
176 177 178 179 180 181

int git_graph_descendant_of(git_repository *repo, const git_oid *commit, const git_oid *ancestor)
{
	if (git_oid_equal(commit, ancestor))
		return 0;

182
	return git_graph_reachable_from_any(repo, ancestor, commit, 1);
183 184 185 186 187
}

int git_graph_reachable_from_any(
		git_repository *repo,
		const git_oid *commit_id,
188 189
		const git_oid descendant_array[],
		size_t length)
190 191 192 193 194 195 196 197 198 199
{
	git_revwalk *walk = NULL;
	git_vector list;
	git_commit_list *result = NULL;
	git_commit_list_node *commit;
	size_t i;
	uint32_t minimum_generation = 0xffffffff;
	int error = 0;

	if (!length)
200 201
		return 0;

202 203 204 205 206 207
	for (i = 0; i < length; ++i) {
		if (git_oid_equal(commit_id, &descendant_array[i]))
			return 1;
	}

	if ((error = git_vector_init(&list, length + 1, NULL)) < 0)
208 209
		return error;

210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248
	if ((error = git_revwalk_new(&walk, repo)) < 0)
		goto done;

	for (i = 0; i < length; i++) {
		commit = git_revwalk__commit_lookup(walk, &descendant_array[i]);
		if (commit == NULL) {
			error = -1;
			goto done;
		}

		git_vector_insert(&list, commit);
		if (minimum_generation > commit->generation)
			minimum_generation = commit->generation;
	}

	commit = git_revwalk__commit_lookup(walk, commit_id);
	if (commit == NULL) {
		error = -1;
		goto done;
	}

	if (minimum_generation > commit->generation)
		minimum_generation = commit->generation;

	if ((error = git_merge__bases_many(&result, walk, commit, &list, minimum_generation)) < 0)
		goto done;

	if (result) {
		error = git_oid_equal(commit_id, &result->item->oid);
	} else {
		/* No merge-base found, it's not a descendant */
		error = 0;
	}

done:
	git_commit_list_free(&result);
	git_vector_free(&list);
	git_revwalk_free(walk);
	return error;
249
}