]>
Commit | Line | Data |
---|---|---|
0984c876 | 1 | /* |
359fc2d2 | 2 | * Copyright (C) the libgit2 contributors. All rights reserved. |
0984c876 SG |
3 | * |
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. | |
6 | */ | |
7 | ||
eae0bfdc PP |
8 | #include "common.h" |
9 | ||
0984c876 | 10 | #include "revwalk.h" |
0984c876 | 11 | #include "merge.h" |
0984c876 SG |
12 | #include "git2/graph.h" |
13 | ||
e51c8b99 | 14 | static int interesting(git_pqueue *list, git_commit_list *roots) |
a3a81ae5 SG |
15 | { |
16 | unsigned int i; | |
4075e060 RB |
17 | |
18 | for (i = 0; i < git_pqueue_size(list); i++) { | |
19 | git_commit_list_node *commit = git_pqueue_get(list, i); | |
a3a81ae5 SG |
20 | if ((commit->flags & STALE) == 0) |
21 | return 1; | |
22 | } | |
23 | ||
e51c8b99 SG |
24 | while(roots) { |
25 | if ((roots->item->flags & STALE) == 0) | |
26 | return 1; | |
27 | roots = roots->next; | |
28 | } | |
29 | ||
a3a81ae5 SG |
30 | return 0; |
31 | } | |
32 | ||
9c2a4e8c SG |
33 | static int mark_parents(git_revwalk *walk, git_commit_list_node *one, |
34 | git_commit_list_node *two) | |
a3a81ae5 | 35 | { |
a3a81ae5 | 36 | unsigned int i; |
e51c8b99 | 37 | git_commit_list *roots = NULL; |
a3a81ae5 SG |
38 | git_pqueue list; |
39 | ||
40 | /* if the commit is repeated, we have a our merge base already */ | |
9c2a4e8c SG |
41 | if (one == two) { |
42 | one->flags |= PARENT1 | PARENT2 | RESULT; | |
43 | return 0; | |
a3a81ae5 SG |
44 | } |
45 | ||
4075e060 | 46 | if (git_pqueue_init(&list, 0, 2, git_commit_list_time_cmp) < 0) |
a3a81ae5 SG |
47 | return -1; |
48 | ||
49 | if (git_commit_list_parse(walk, one) < 0) | |
7d26c410 | 50 | goto on_error; |
a3a81ae5 SG |
51 | one->flags |= PARENT1; |
52 | if (git_pqueue_insert(&list, one) < 0) | |
7d26c410 | 53 | goto on_error; |
a3a81ae5 | 54 | |
9c2a4e8c | 55 | if (git_commit_list_parse(walk, two) < 0) |
7d26c410 | 56 | goto on_error; |
9c2a4e8c SG |
57 | two->flags |= PARENT2; |
58 | if (git_pqueue_insert(&list, two) < 0) | |
7d26c410 | 59 | goto on_error; |
a3a81ae5 SG |
60 | |
61 | /* as long as there are non-STALE commits */ | |
e51c8b99 | 62 | while (interesting(&list, roots)) { |
4075e060 | 63 | git_commit_list_node *commit = git_pqueue_pop(&list); |
e781a0c5 | 64 | unsigned int flags; |
a3a81ae5 | 65 | |
e51c8b99 SG |
66 | if (commit == NULL) |
67 | break; | |
a3a81ae5 SG |
68 | |
69 | flags = commit->flags & (PARENT1 | PARENT2 | STALE); | |
70 | if (flags == (PARENT1 | PARENT2)) { | |
9c2a4e8c | 71 | if (!(commit->flags & RESULT)) |
a3a81ae5 | 72 | commit->flags |= RESULT; |
a3a81ae5 SG |
73 | /* we mark the parents of a merge stale */ |
74 | flags |= STALE; | |
75 | } | |
76 | ||
77 | for (i = 0; i < commit->out_degree; i++) { | |
78 | git_commit_list_node *p = commit->parents[i]; | |
79 | if ((p->flags & flags) == flags) | |
80 | continue; | |
81 | ||
7d26c410 SG |
82 | if (git_commit_list_parse(walk, p) < 0) |
83 | goto on_error; | |
a3a81ae5 SG |
84 | |
85 | p->flags |= flags; | |
86 | if (git_pqueue_insert(&list, p) < 0) | |
7d26c410 | 87 | goto on_error; |
a3a81ae5 | 88 | } |
e51c8b99 | 89 | |
7d26c410 | 90 | /* Keep track of root commits, to make sure the path gets marked */ |
e51c8b99 SG |
91 | if (commit->out_degree == 0) { |
92 | if (git_commit_list_insert(commit, &roots) == NULL) | |
7d26c410 | 93 | goto on_error; |
e51c8b99 | 94 | } |
a3a81ae5 SG |
95 | } |
96 | ||
7d26c410 | 97 | git_commit_list_free(&roots); |
a3a81ae5 | 98 | git_pqueue_free(&list); |
a3a81ae5 | 99 | return 0; |
7d26c410 SG |
100 | |
101 | on_error: | |
102 | git_commit_list_free(&roots); | |
103 | git_pqueue_free(&list); | |
104 | return -1; | |
a3a81ae5 SG |
105 | } |
106 | ||
9c2a4e8c | 107 | |
0984c876 SG |
108 | static int ahead_behind(git_commit_list_node *one, git_commit_list_node *two, |
109 | size_t *ahead, size_t *behind) | |
110 | { | |
111 | git_commit_list_node *commit; | |
112 | git_pqueue pq; | |
4075e060 | 113 | int error = 0, i; |
0984c876 SG |
114 | *ahead = 0; |
115 | *behind = 0; | |
116 | ||
4075e060 | 117 | if (git_pqueue_init(&pq, 0, 2, git_commit_list_time_cmp) < 0) |
0984c876 | 118 | return -1; |
4075e060 RB |
119 | |
120 | if ((error = git_pqueue_insert(&pq, one)) < 0 || | |
121 | (error = git_pqueue_insert(&pq, two)) < 0) | |
122 | goto done; | |
0984c876 SG |
123 | |
124 | while ((commit = git_pqueue_pop(&pq)) != NULL) { | |
125 | if (commit->flags & RESULT || | |
126 | (commit->flags & (PARENT1 | PARENT2)) == (PARENT1 | PARENT2)) | |
127 | continue; | |
128 | else if (commit->flags & PARENT1) | |
0984c876 | 129 | (*ahead)++; |
05f0d0c1 CMN |
130 | else if (commit->flags & PARENT2) |
131 | (*behind)++; | |
0984c876 SG |
132 | |
133 | for (i = 0; i < commit->out_degree; i++) { | |
134 | git_commit_list_node *p = commit->parents[i]; | |
4075e060 RB |
135 | if ((error = git_pqueue_insert(&pq, p)) < 0) |
136 | goto done; | |
0984c876 SG |
137 | } |
138 | commit->flags |= RESULT; | |
139 | } | |
140 | ||
4075e060 | 141 | done: |
da820437 | 142 | git_pqueue_free(&pq); |
4075e060 | 143 | return error; |
0984c876 SG |
144 | } |
145 | ||
146 | int git_graph_ahead_behind(size_t *ahead, size_t *behind, git_repository *repo, | |
33a59401 | 147 | const git_oid *local, const git_oid *upstream) |
0984c876 SG |
148 | { |
149 | git_revwalk *walk; | |
33a59401 | 150 | git_commit_list_node *commit_u, *commit_l; |
0984c876 SG |
151 | |
152 | if (git_revwalk_new(&walk, repo) < 0) | |
153 | return -1; | |
154 | ||
33a59401 CMN |
155 | commit_u = git_revwalk__commit_lookup(walk, upstream); |
156 | if (commit_u == NULL) | |
0984c876 SG |
157 | goto on_error; |
158 | ||
33a59401 CMN |
159 | commit_l = git_revwalk__commit_lookup(walk, local); |
160 | if (commit_l == NULL) | |
0984c876 SG |
161 | goto on_error; |
162 | ||
33a59401 | 163 | if (mark_parents(walk, commit_l, commit_u) < 0) |
0984c876 | 164 | goto on_error; |
33a59401 | 165 | if (ahead_behind(commit_l, commit_u, ahead, behind) < 0) |
0984c876 SG |
166 | goto on_error; |
167 | ||
0984c876 SG |
168 | git_revwalk_free(walk); |
169 | ||
170 | return 0; | |
171 | ||
172 | on_error: | |
173 | git_revwalk_free(walk); | |
174 | return -1; | |
175 | } | |
e7c16943 AS |
176 | |
177 | int git_graph_descendant_of(git_repository *repo, const git_oid *commit, const git_oid *ancestor) | |
178 | { | |
179 | git_oid merge_base; | |
180 | int error; | |
181 | ||
182 | if (git_oid_equal(commit, ancestor)) | |
183 | return 0; | |
184 | ||
ce2e8269 CMN |
185 | error = git_merge_base(&merge_base, repo, commit, ancestor); |
186 | /* No merge-base found, it's not a descendant */ | |
187 | if (error == GIT_ENOTFOUND) | |
188 | return 0; | |
189 | ||
190 | if (error < 0) | |
e7c16943 AS |
191 | return error; |
192 | ||
193 | return git_oid_equal(&merge_base, ancestor); | |
194 | } |