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