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