File Coverage

deps/libgit2/src/graph.c
Criterion Covered Total %
statement 78 102 76.4
branch 53 76 69.7
condition n/a
subroutine n/a
pod n/a
total 131 178 73.6


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