gitweb: safely output binary files for 'blob_plain' action
[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 used to fail to mark an
86  * ancestor of a merge base as UNINTERESTING before we introduced the
87  * postprocessing phase (mark_reachable_commits).
88  *
89  *                2
90  *                H
91  *          1    / \
92  *          G   A   \
93  *          |\ /     \ 
94  *          | B       \
95  *          |  \       \
96  *           \  C       F
97  *            \  \     / 
98  *             \  D   /   
99  *              \ |  /
100  *               \| /
101  *                E
102  *
103  *       list                   A B C D E F G H
104  *       G1 H2                  - - - - - - 1 2
105  *       H2 E1 B1               - 1 - - 1 - 1 2
106  *       F2 E1 B1 A2            2 1 - - 1 2 1 2
107  *       E3 B1 A2               2 1 - - 3 2 1 2
108  *       B1 A2                  2 1 - - 3 2 1 2
109  *       C1 A2                  2 1 1 - 3 2 1 2
110  *       D1 A2                  2 1 1 1 3 2 1 2
111  *       A2                     2 1 1 1 3 2 1 2
112  *       B3                     2 3 1 1 3 2 1 2
113  *       C7                     2 3 7 1 3 2 1 2
114  *
115  * At this point, unfortunately, everybody in the list is
116  * uninteresting, so we fail to complete the following two
117  * steps to fully marking uninteresting commits.
118  *
119  *       D7                     2 3 7 7 3 2 1 2
120  *       E7                     2 3 7 7 7 2 1 2
121  *
122  * and we ended up showing E as an interesting merge base.
123  * The postprocessing phase re-injects C and continues traversal
124  * to contaminate D and E.
125  */
126
127 static int show_all = 0;
128
129 static void mark_reachable_commits(struct commit_list *result,
130                                    struct commit_list *list)
131 {
132         struct commit_list *tmp;
133
134         /*
135          * Postprocess to fully contaminate the well.
136          */
137         for (tmp = result; tmp; tmp = tmp->next) {
138                 struct commit *c = tmp->item;
139                 /* Reinject uninteresting ones to list,
140                  * so we can scan their parents.
141                  */
142                 if (c->object.flags & UNINTERESTING)
143                         commit_list_insert(c, &list);
144         }
145         while (list) {
146                 struct commit *c = list->item;
147                 struct commit_list *parents;
148
149                 tmp = list;
150                 list = list->next;
151                 free(tmp);
152
153                 /* Anything taken out of the list is uninteresting, so
154                  * mark all its parents uninteresting.  We do not
155                  * parse new ones (we already parsed all the relevant
156                  * ones).
157                  */
158                 parents = c->parents;
159                 while (parents) {
160                         struct commit *p = parents->item;
161                         parents = parents->next;
162                         if (!(p->object.flags & UNINTERESTING)) {
163                                 p->object.flags |= UNINTERESTING;
164                                 commit_list_insert(p, &list);
165                         }
166                 }
167         }
168 }
169
170 static int merge_base(struct commit *rev1, struct commit *rev2)
171 {
172         struct commit_list *list = NULL;
173         struct commit_list *result = NULL;
174         struct commit_list *tmp = NULL;
175
176         if (rev1 == rev2) {
177                 printf("%s\n", sha1_to_hex(rev1->object.sha1));
178                 return 0;
179         }
180
181         parse_commit(rev1);
182         parse_commit(rev2);
183
184         rev1->object.flags |= 1;
185         rev2->object.flags |= 2;
186         insert_by_date(rev1, &list);
187         insert_by_date(rev2, &list);
188
189         while (interesting(list)) {
190                 struct commit *commit = list->item;
191                 struct commit_list *parents;
192                 int flags = commit->object.flags & 7;
193
194                 tmp = list;
195                 list = list->next;
196                 free(tmp);
197                 if (flags == 3) {
198                         insert_by_date(commit, &result);
199
200                         /* Mark parents of a found merge uninteresting */
201                         flags |= UNINTERESTING;
202                 }
203                 parents = commit->parents;
204                 while (parents) {
205                         struct commit *p = parents->item;
206                         parents = parents->next;
207                         if ((p->object.flags & flags) == flags)
208                                 continue;
209                         parse_commit(p);
210                         p->object.flags |= flags;
211                         insert_by_date(p, &list);
212                 }
213         }
214
215         if (!result)
216                 return 1;
217
218         if (result->next && list)
219                 mark_reachable_commits(result, list);
220
221         while (result) {
222                 struct commit *commit = result->item;
223                 result = result->next;
224                 if (commit->object.flags & UNINTERESTING)
225                         continue;
226                 printf("%s\n", sha1_to_hex(commit->object.sha1));
227                 if (!show_all)
228                         return 0;
229                 commit->object.flags |= UNINTERESTING;
230         }
231         return 0;
232 }
233
234 static const char merge_base_usage[] =
235 "git-merge-base [--all] <commit-id> <commit-id>";
236
237 int main(int argc, char **argv)
238 {
239         struct commit *rev1, *rev2;
240         unsigned char rev1key[20], rev2key[20];
241
242         setup_git_directory();
243         git_config(git_default_config);
244
245         while (1 < argc && argv[1][0] == '-') {
246                 char *arg = argv[1];
247                 if (!strcmp(arg, "-a") || !strcmp(arg, "--all"))
248                         show_all = 1;
249                 else
250                         usage(merge_base_usage);
251                 argc--; argv++;
252         }
253         if (argc != 3)
254                 usage(merge_base_usage);
255         if (get_sha1(argv[1], rev1key))
256                 die("Not a valid object name %s", argv[1]);
257         if (get_sha1(argv[2], rev2key))
258                 die("Not a valid object name %s", argv[2]);
259         rev1 = lookup_commit_reference(rev1key);
260         rev2 = lookup_commit_reference(rev2key);
261         if (!rev1 || !rev2)
262                 return 1;
263         return merge_base(rev1, rev2);
264 }