]>
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. | |
83 | */ | |
84 | ||
9585e406 JH |
85 | static int show_all = 0; |
86 | ||
87 | static int merge_base(struct commit *rev1, struct commit *rev2) | |
6683463e | 88 | { |
4f7eb2e5 LT |
89 | struct commit_list *list = NULL; |
90 | struct commit_list *result = NULL; | |
b5039db6 | 91 | |
9585e406 JH |
92 | if (rev1 == rev2) { |
93 | printf("%s\n", sha1_to_hex(rev1->object.sha1)); | |
94 | return 0; | |
95 | } | |
6683463e | 96 | |
b6b15db3 DB |
97 | parse_commit(rev1); |
98 | parse_commit(rev2); | |
6683463e | 99 | |
4f7eb2e5 LT |
100 | rev1->object.flags |= 1; |
101 | rev2->object.flags |= 2; | |
102 | insert_by_date(rev1, &list); | |
103 | insert_by_date(rev2, &list); | |
104 | ||
0b9442d6 | 105 | while (interesting(list)) { |
4f7eb2e5 LT |
106 | struct commit *commit = list->item; |
107 | struct commit_list *tmp = list, *parents; | |
0b9442d6 | 108 | int flags = commit->object.flags & 7; |
4f7eb2e5 LT |
109 | |
110 | list = list->next; | |
111 | free(tmp); | |
0b9442d6 | 112 | if (flags == 3) { |
4f7eb2e5 | 113 | insert_by_date(commit, &result); |
0b9442d6 | 114 | |
9585e406 | 115 | /* Mark parents of a found merge uninteresting */ |
0b9442d6 | 116 | flags |= UNINTERESTING; |
b5039db6 | 117 | } |
4f7eb2e5 LT |
118 | parents = commit->parents; |
119 | while (parents) { | |
120 | struct commit *p = parents->item; | |
121 | parents = parents->next; | |
122 | if ((p->object.flags & flags) == flags) | |
123 | continue; | |
124 | parse_commit(p); | |
125 | p->object.flags |= flags; | |
126 | insert_by_date(p, &list); | |
6683463e | 127 | } |
6683463e | 128 | } |
9585e406 JH |
129 | |
130 | if (!result) | |
131 | return 1; | |
132 | ||
133 | while (result) { | |
134 | struct commit *commit = result->item; | |
135 | result = result->next; | |
136 | if (commit->object.flags & UNINTERESTING) | |
137 | continue; | |
138 | printf("%s\n", sha1_to_hex(commit->object.sha1)); | |
139 | if (!show_all) | |
140 | return 0; | |
141 | commit->object.flags |= UNINTERESTING; | |
142 | } | |
143 | return 0; | |
6683463e LT |
144 | } |
145 | ||
9585e406 JH |
146 | static const char merge_base_usage[] = |
147 | "git-merge-base [--all] <commit-id> <commit-id>"; | |
148 | ||
6683463e LT |
149 | int main(int argc, char **argv) |
150 | { | |
9585e406 | 151 | struct commit *rev1, *rev2; |
b5039db6 | 152 | unsigned char rev1key[20], rev2key[20]; |
6683463e | 153 | |
9585e406 JH |
154 | while (1 < argc && argv[1][0] == '-') { |
155 | char *arg = argv[1]; | |
156 | if (!strcmp(arg, "-a") || !strcmp(arg, "--all")) | |
157 | show_all = 1; | |
158 | else | |
159 | usage(merge_base_usage); | |
160 | argc--; argv++; | |
161 | } | |
b5039db6 | 162 | if (argc != 3 || |
3c249c95 | 163 | get_sha1(argv[1], rev1key) || |
9585e406 JH |
164 | get_sha1(argv[2], rev2key)) |
165 | usage(merge_base_usage); | |
9b632be3 LT |
166 | rev1 = lookup_commit_reference(rev1key); |
167 | rev2 = lookup_commit_reference(rev2key); | |
4f7eb2e5 LT |
168 | if (!rev1 || !rev2) |
169 | return 1; | |
9585e406 | 170 | return merge_base(rev1, rev2); |
6683463e | 171 | } |