graph.c 4.24 KB
Newer Older
1
/*
Edward Thomson committed
2
 * Copyright (C) the libgit2 contributors. All rights reserved.
3 4 5 6 7 8 9 10 11
 *
 * 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"

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

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

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

28 29 30
	return 0;
}

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

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

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

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

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

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

64 65
		if (commit == NULL)
			break;
66 67 68

		flags = commit->flags & (PARENT1 | PARENT2 | STALE);
		if (flags == (PARENT1 | PARENT2)) {
69
			if (!(commit->flags & RESULT))
70 71 72 73 74 75 76 77 78 79
				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;

80 81
			if (git_commit_list_parse(walk, p) < 0)
				goto on_error;
82 83 84

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

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

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

on_error:
	git_commit_list_free(&roots);
	git_pqueue_free(&list);
	return -1;
103 104
}

105

106 107 108 109 110
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;
111
	int error = 0, i;
112 113 114
	*ahead = 0;
	*behind = 0;

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

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

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

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

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

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

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

153 154
	commit_u = git_revwalk__commit_lookup(walk, upstream);
	if (commit_u == NULL)
155 156
		goto on_error;

157 158
	commit_l = git_revwalk__commit_lookup(walk, local);
	if (commit_l == NULL)
159 160
		goto on_error;

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

	git_revwalk_free(walk);

	return 0;

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

int git_graph_descendant_of(git_repository *repo, const git_oid *commit, const git_oid *ancestor)
{
	git_oid merge_base;
	int error;

	if (git_oid_equal(commit, ancestor))
		return 0;

183 184 185 186 187 188
	error = git_merge_base(&merge_base, repo, commit, ancestor);
	/* No merge-base found, it's not a descendant */
	if (error == GIT_ENOTFOUND)
		return 0;

	if (error < 0)
189 190 191 192
		return error;

	return git_oid_equal(&merge_base, ancestor);
}