2 * Copyright (C) the libgit2 contributors. All rights reserved.
4 * This file is part of libgit2, distributed under the GNU GPL v2 with
5 * a Linking Exception. For full terms see the included COPYING file.
12 #include "git2/graph.h"
14 static int interesting(git_pqueue
*list
, git_commit_list
*roots
)
18 for (i
= 0; i
< git_pqueue_size(list
); i
++) {
19 git_commit_list_node
*commit
= git_pqueue_get(list
, i
);
20 if ((commit
->flags
& STALE
) == 0)
25 if ((roots
->item
->flags
& STALE
) == 0)
33 static int mark_parents(git_revwalk
*walk
, git_commit_list_node
*one
,
34 git_commit_list_node
*two
)
37 git_commit_list
*roots
= NULL
;
40 /* if the commit is repeated, we have a our merge base already */
42 one
->flags
|= PARENT1
| PARENT2
| RESULT
;
46 if (git_pqueue_init(&list
, 0, 2, git_commit_list_generation_cmp
) < 0)
49 if (git_commit_list_parse(walk
, one
) < 0)
51 one
->flags
|= PARENT1
;
52 if (git_pqueue_insert(&list
, one
) < 0)
55 if (git_commit_list_parse(walk
, two
) < 0)
57 two
->flags
|= PARENT2
;
58 if (git_pqueue_insert(&list
, two
) < 0)
61 /* as long as there are non-STALE commits */
62 while (interesting(&list
, roots
)) {
63 git_commit_list_node
*commit
= git_pqueue_pop(&list
);
69 flags
= commit
->flags
& (PARENT1
| PARENT2
| STALE
);
70 if (flags
== (PARENT1
| PARENT2
)) {
71 if (!(commit
->flags
& RESULT
))
72 commit
->flags
|= RESULT
;
73 /* we mark the parents of a merge stale */
77 for (i
= 0; i
< commit
->out_degree
; i
++) {
78 git_commit_list_node
*p
= commit
->parents
[i
];
79 if ((p
->flags
& flags
) == flags
)
82 if (git_commit_list_parse(walk
, p
) < 0)
86 if (git_pqueue_insert(&list
, p
) < 0)
90 /* Keep track of root commits, to make sure the path gets marked */
91 if (commit
->out_degree
== 0) {
92 if (git_commit_list_insert(commit
, &roots
) == NULL
)
97 git_commit_list_free(&roots
);
98 git_pqueue_free(&list
);
102 git_commit_list_free(&roots
);
103 git_pqueue_free(&list
);
108 static int ahead_behind(git_commit_list_node
*one
, git_commit_list_node
*two
,
109 size_t *ahead
, size_t *behind
)
111 git_commit_list_node
*commit
;
117 if (git_pqueue_init(&pq
, 0, 2, git_commit_list_time_cmp
) < 0)
120 if ((error
= git_pqueue_insert(&pq
, one
)) < 0 ||
121 (error
= git_pqueue_insert(&pq
, two
)) < 0)
124 while ((commit
= git_pqueue_pop(&pq
)) != NULL
) {
125 if (commit
->flags
& RESULT
||
126 (commit
->flags
& (PARENT1
| PARENT2
)) == (PARENT1
| PARENT2
))
128 else if (commit
->flags
& PARENT1
)
130 else if (commit
->flags
& PARENT2
)
133 for (i
= 0; i
< commit
->out_degree
; i
++) {
134 git_commit_list_node
*p
= commit
->parents
[i
];
135 if ((error
= git_pqueue_insert(&pq
, p
)) < 0)
138 commit
->flags
|= RESULT
;
142 git_pqueue_free(&pq
);
146 int git_graph_ahead_behind(size_t *ahead
, size_t *behind
, git_repository
*repo
,
147 const git_oid
*local
, const git_oid
*upstream
)
150 git_commit_list_node
*commit_u
, *commit_l
;
152 if (git_revwalk_new(&walk
, repo
) < 0)
155 commit_u
= git_revwalk__commit_lookup(walk
, upstream
);
156 if (commit_u
== NULL
)
159 commit_l
= git_revwalk__commit_lookup(walk
, local
);
160 if (commit_l
== NULL
)
163 if (mark_parents(walk
, commit_l
, commit_u
) < 0)
165 if (ahead_behind(commit_l
, commit_u
, ahead
, behind
) < 0)
168 git_revwalk_free(walk
);
173 git_revwalk_free(walk
);
177 int git_graph_descendant_of(git_repository
*repo
, const git_oid
*commit
, const git_oid
*ancestor
)
179 if (git_oid_equal(commit
, ancestor
))
182 return git_graph_reachable_from_any(repo
, ancestor
, commit
, 1);
185 int git_graph_reachable_from_any(
186 git_repository
*repo
,
187 const git_oid
*commit_id
,
188 const git_oid descendant_array
[],
191 git_revwalk
*walk
= NULL
;
193 git_commit_list
*result
= NULL
;
194 git_commit_list_node
*commit
;
196 uint32_t minimum_generation
= 0xffffffff;
202 for (i
= 0; i
< length
; ++i
) {
203 if (git_oid_equal(commit_id
, &descendant_array
[i
]))
207 if ((error
= git_vector_init(&list
, length
+ 1, NULL
)) < 0)
210 if ((error
= git_revwalk_new(&walk
, repo
)) < 0)
213 for (i
= 0; i
< length
; i
++) {
214 commit
= git_revwalk__commit_lookup(walk
, &descendant_array
[i
]);
215 if (commit
== NULL
) {
220 git_vector_insert(&list
, commit
);
221 if (minimum_generation
> commit
->generation
)
222 minimum_generation
= commit
->generation
;
225 commit
= git_revwalk__commit_lookup(walk
, commit_id
);
226 if (commit
== NULL
) {
231 if (minimum_generation
> commit
->generation
)
232 minimum_generation
= commit
->generation
;
234 if ((error
= git_merge__bases_many(&result
, walk
, commit
, &list
, minimum_generation
)) < 0)
238 error
= git_oid_equal(commit_id
, &result
->item
->oid
);
240 /* No merge-base found, it's not a descendant */
245 git_commit_list_free(&result
);
246 git_vector_free(&list
);
247 git_revwalk_free(walk
);