graph.c 4.26 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_time_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 182 183 184

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;

185 186 187 188 189 190
	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)
191 192 193 194
		return error;

	return git_oid_equal(&merge_base, ancestor);
}