]>
Commit | Line | Data |
---|---|---|
b5039db6 | 1 | #include <stdlib.h> |
6683463e | 2 | #include "cache.h" |
b5039db6 | 3 | #include "commit.h" |
6683463e | 4 | |
0b9442d6 LT |
5 | #define PARENT1 1 |
6 | #define PARENT2 2 | |
7 | #define UNINTERESTING 4 | |
8 | ||
b4ad66b7 | 9 | static struct commit *interesting(struct commit_list *list) |
0b9442d6 LT |
10 | { |
11 | while (list) { | |
12 | struct commit *commit = list->item; | |
13 | list = list->next; | |
14 | if (commit->object.flags & UNINTERESTING) | |
15 | continue; | |
b4ad66b7 | 16 | return commit; |
0b9442d6 | 17 | } |
b4ad66b7 | 18 | return NULL; |
0b9442d6 LT |
19 | } |
20 | ||
b4ad66b7 JH |
21 | /* |
22 | * A pathological example of how this thing works. | |
23 | * | |
24 | * Suppose we had this commit graph, where chronologically | |
25 | * the timestamp on the commit are A <= B <= C <= D <= E <= F | |
26 | * and we are trying to figure out the merge base for E and F | |
27 | * commits. | |
28 | * | |
29 | * F | |
30 | * / \ | |
31 | * E A D | |
32 | * \ / / | |
33 | * B / | |
34 | * \ / | |
35 | * C | |
36 | * | |
37 | * First we push E and F to list to be processed. E gets bit 1 | |
38 | * and F gets bit 2. The list becomes: | |
39 | * | |
40 | * list=F(2) E(1), result=empty | |
41 | * | |
42 | * Then we pop F, the newest commit, from the list. Its flag is 2. | |
43 | * We scan its parents, mark them reachable from the side that F is | |
44 | * reachable from, and push them to the list: | |
45 | * | |
46 | * list=E(1) D(2) A(2), result=empty | |
47 | * | |
48 | * Next pop E and do the same. | |
49 | * | |
50 | * list=D(2) B(1) A(2), result=empty | |
51 | * | |
52 | * Next pop D and do the same. | |
53 | * | |
54 | * list=C(2) B(1) A(2), result=empty | |
55 | * | |
56 | * Next pop C and do the same. | |
57 | * | |
58 | * list=B(1) A(2), result=empty | |
59 | * | |
60 | * Now it is B's turn. We mark its parent, C, reachable from B's side, | |
61 | * and push it to the list: | |
62 | * | |
63 | * list=C(3) A(2), result=empty | |
64 | * | |
65 | * Now pop C and notice it has flags==3. It is placed on the result list, | |
66 | * and the list now contains: | |
67 | * | |
68 | * list=A(2), result=C(3) | |
69 | * | |
70 | * We pop A and do the same. | |
71 | * | |
72 | * list=B(3), result=C(3) | |
73 | * | |
74 | * Next, we pop B and something very interesting happens. It has flags==3 | |
75 | * so it is also placed on the result list, and its parents are marked | |
76 | * uninteresting, retroactively, and placed back on the list: | |
77 | * | |
78 | * list=C(7), result=C(7) B(3) | |
79 | * | |
80 | * Now, list does not have any interesting commit. So we find the newest | |
81 | * commit from the result list that is not marked uninteresting. Which is | |
82 | * commit B. | |
ed9a540b JH |
83 | * |
84 | * | |
85 | * Another pathological example how this thing can fail to mark an ancestor | |
86 | * of a merge base as UNINTERESTING without the postprocessing phase. | |
87 | * | |
88 | * 2 | |
89 | * H | |
90 | * 1 / \ | |
91 | * G A \ | |
92 | * |\ / \ | |
93 | * | B \ | |
94 | * | \ \ | |
95 | * \ C F | |
96 | * \ \ / | |
97 | * \ D / | |
98 | * \ | / | |
99 | * \| / | |
100 | * E | |
101 | * | |
102 | * list A B C D E F G H | |
103 | * G1 H2 - - - - - - 1 2 | |
104 | * H2 E1 B1 - 1 - - 1 - 1 2 | |
105 | * F2 E1 B1 A2 2 1 - - 1 2 1 2 | |
106 | * E3 B1 A2 2 1 - - 3 2 1 2 | |
107 | * B1 A2 2 1 - - 3 2 1 2 | |
108 | * C1 A2 2 1 1 - 3 2 1 2 | |
109 | * D1 A2 2 1 1 1 3 2 1 2 | |
110 | * A2 2 1 1 1 3 2 1 2 | |
111 | * B3 2 3 1 1 3 2 1 2 | |
112 | * C7 2 3 7 1 3 2 1 2 | |
113 | * | |
114 | * At this point, unfortunately, everybody in the list is | |
115 | * uninteresting, so we fail to complete the following two | |
116 | * steps to fully marking uninteresting commits. | |
117 | * | |
118 | * D7 2 3 7 7 3 2 1 2 | |
119 | * E7 2 3 7 7 7 2 1 2 | |
120 | * | |
121 | * and we end up showing E as an interesting merge base. | |
b4ad66b7 JH |
122 | */ |
123 | ||
9585e406 JH |
124 | static int show_all = 0; |
125 | ||
9e5f4a55 JH |
126 | static void mark_reachable_commits(struct commit_list *result, |
127 | struct commit_list *list) | |
128 | { | |
129 | struct commit_list *tmp; | |
130 | ||
131 | /* | |
132 | * Postprocess to fully contaminate the well. | |
133 | */ | |
134 | for (tmp = result; tmp; tmp = tmp->next) { | |
135 | struct commit *c = tmp->item; | |
136 | /* Reinject uninteresting ones to list, | |
137 | * so we can scan their parents. | |
138 | */ | |
139 | if (c->object.flags & UNINTERESTING) | |
140 | commit_list_insert(c, &list); | |
141 | } | |
142 | while (list) { | |
143 | struct commit *c = list->item; | |
144 | struct commit_list *parents; | |
145 | ||
146 | tmp = list; | |
147 | list = list->next; | |
148 | free(tmp); | |
149 | ||
150 | /* Anything taken out of the list is uninteresting, so | |
151 | * mark all its parents uninteresting. We do not | |
152 | * parse new ones (we already parsed all the relevant | |
153 | * ones). | |
154 | */ | |
155 | parents = c->parents; | |
156 | while (parents) { | |
157 | struct commit *p = parents->item; | |
158 | parents = parents->next; | |
159 | if (!(p->object.flags & UNINTERESTING)) { | |
160 | p->object.flags |= UNINTERESTING; | |
161 | commit_list_insert(p, &list); | |
162 | } | |
163 | } | |
164 | } | |
165 | } | |
166 | ||
9585e406 | 167 | static int merge_base(struct commit *rev1, struct commit *rev2) |
6683463e | 168 | { |
4f7eb2e5 LT |
169 | struct commit_list *list = NULL; |
170 | struct commit_list *result = NULL; | |
ed9a540b | 171 | struct commit_list *tmp = NULL; |
b5039db6 | 172 | |
9585e406 JH |
173 | if (rev1 == rev2) { |
174 | printf("%s\n", sha1_to_hex(rev1->object.sha1)); | |
175 | return 0; | |
176 | } | |
6683463e | 177 | |
b6b15db3 DB |
178 | parse_commit(rev1); |
179 | parse_commit(rev2); | |
6683463e | 180 | |
4f7eb2e5 LT |
181 | rev1->object.flags |= 1; |
182 | rev2->object.flags |= 2; | |
183 | insert_by_date(rev1, &list); | |
184 | insert_by_date(rev2, &list); | |
185 | ||
0b9442d6 | 186 | while (interesting(list)) { |
4f7eb2e5 | 187 | struct commit *commit = list->item; |
ed9a540b | 188 | struct commit_list *parents; |
0b9442d6 | 189 | int flags = commit->object.flags & 7; |
4f7eb2e5 | 190 | |
ed9a540b | 191 | tmp = list; |
4f7eb2e5 LT |
192 | list = list->next; |
193 | free(tmp); | |
0b9442d6 | 194 | if (flags == 3) { |
4f7eb2e5 | 195 | insert_by_date(commit, &result); |
0b9442d6 | 196 | |
9585e406 | 197 | /* Mark parents of a found merge uninteresting */ |
0b9442d6 | 198 | flags |= UNINTERESTING; |
b5039db6 | 199 | } |
4f7eb2e5 LT |
200 | parents = commit->parents; |
201 | while (parents) { | |
202 | struct commit *p = parents->item; | |
203 | parents = parents->next; | |
204 | if ((p->object.flags & flags) == flags) | |
205 | continue; | |
206 | parse_commit(p); | |
207 | p->object.flags |= flags; | |
208 | insert_by_date(p, &list); | |
6683463e | 209 | } |
6683463e | 210 | } |
9585e406 JH |
211 | |
212 | if (!result) | |
213 | return 1; | |
214 | ||
9e5f4a55 JH |
215 | if (result->next && list) |
216 | mark_reachable_commits(result, list); | |
ed9a540b | 217 | |
9585e406 JH |
218 | while (result) { |
219 | struct commit *commit = result->item; | |
220 | result = result->next; | |
221 | if (commit->object.flags & UNINTERESTING) | |
222 | continue; | |
223 | printf("%s\n", sha1_to_hex(commit->object.sha1)); | |
224 | if (!show_all) | |
225 | return 0; | |
226 | commit->object.flags |= UNINTERESTING; | |
227 | } | |
228 | return 0; | |
6683463e LT |
229 | } |
230 | ||
9585e406 JH |
231 | static const char merge_base_usage[] = |
232 | "git-merge-base [--all] <commit-id> <commit-id>"; | |
233 | ||
6683463e LT |
234 | int main(int argc, char **argv) |
235 | { | |
9585e406 | 236 | struct commit *rev1, *rev2; |
b5039db6 | 237 | unsigned char rev1key[20], rev2key[20]; |
6683463e | 238 | |
53228a5f JH |
239 | setup_git_directory(); |
240 | ||
9585e406 JH |
241 | while (1 < argc && argv[1][0] == '-') { |
242 | char *arg = argv[1]; | |
243 | if (!strcmp(arg, "-a") || !strcmp(arg, "--all")) | |
244 | show_all = 1; | |
245 | else | |
246 | usage(merge_base_usage); | |
247 | argc--; argv++; | |
248 | } | |
b5039db6 | 249 | if (argc != 3 || |
3c249c95 | 250 | get_sha1(argv[1], rev1key) || |
9585e406 JH |
251 | get_sha1(argv[2], rev2key)) |
252 | usage(merge_base_usage); | |
9b632be3 LT |
253 | rev1 = lookup_commit_reference(rev1key); |
254 | rev2 = lookup_commit_reference(rev2key); | |
4f7eb2e5 LT |
255 | if (!rev1 || !rev2) |
256 | return 1; | |
9585e406 | 257 | return merge_base(rev1, rev2); |
6683463e | 258 | } |