GIT 1.0.0a
[git] / merge-base.c
1 #include <stdlib.h>
2 #include "cache.h"
3 #include "commit.h"
4
5 #define PARENT1 1
6 #define PARENT2 2
7 #define UNINTERESTING 4
8
9 static struct commit *interesting(struct commit_list *list)
10 {
11         while (list) {
12                 struct commit *commit = list->item;
13                 list = list->next;
14                 if (commit->object.flags & UNINTERESTING)
15                         continue;
16                 return commit;
17         }
18         return NULL;
19 }
20
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  *
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.
122  */
123
124 static int show_all = 0;
125
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
167 static int merge_base(struct commit *rev1, struct commit *rev2)
168 {
169         struct commit_list *list = NULL;
170         struct commit_list *result = NULL;
171         struct commit_list *tmp = NULL;
172
173         if (rev1 == rev2) {
174                 printf("%s\n", sha1_to_hex(rev1->object.sha1));
175                 return 0;
176         }
177
178         parse_commit(rev1);
179         parse_commit(rev2);
180
181         rev1->object.flags |= 1;
182         rev2->object.flags |= 2;
183         insert_by_date(rev1, &list);
184         insert_by_date(rev2, &list);
185
186         while (interesting(list)) {
187                 struct commit *commit = list->item;
188                 struct commit_list *parents;
189                 int flags = commit->object.flags & 7;
190
191                 tmp = list;
192                 list = list->next;
193                 free(tmp);
194                 if (flags == 3) {
195                         insert_by_date(commit, &result);
196
197                         /* Mark parents of a found merge uninteresting */
198                         flags |= UNINTERESTING;
199                 }
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);
209                 }
210         }
211
212         if (!result)
213                 return 1;
214
215         if (result->next && list)
216                 mark_reachable_commits(result, list);
217
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;
229 }
230
231 static const char merge_base_usage[] =
232 "git-merge-base [--all] <commit-id> <commit-id>";
233
234 int main(int argc, char **argv)
235 {
236         struct commit *rev1, *rev2;
237         unsigned char rev1key[20], rev2key[20];
238
239         setup_git_directory();
240
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         }
249         if (argc != 3 ||
250             get_sha1(argv[1], rev1key) ||
251             get_sha1(argv[2], rev2key))
252                 usage(merge_base_usage);
253         rev1 = lookup_commit_reference(rev1key);
254         rev2 = lookup_commit_reference(rev2key);
255         if (!rev1 || !rev2)
256                 return 1;
257         return merge_base(rev1, rev2);
258 }