7 #define UNINTERESTING 4
9 static struct commit
*interesting(struct commit_list
*list
)
12 struct commit
*commit
= list
->item
;
14 if (commit
->object
.flags
& UNINTERESTING
)
22 * A pathological example of how this thing works.
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
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:
40 * list=F(2) E(1), result=empty
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:
46 * list=E(1) D(2) A(2), result=empty
48 * Next pop E and do the same.
50 * list=D(2) B(1) A(2), result=empty
52 * Next pop D and do the same.
54 * list=C(2) B(1) A(2), result=empty
56 * Next pop C and do the same.
58 * list=B(1) A(2), result=empty
60 * Now it is B's turn. We mark its parent, C, reachable from B's side,
61 * and push it to the list:
63 * list=C(3) A(2), result=empty
65 * Now pop C and notice it has flags==3. It is placed on the result list,
66 * and the list now contains:
68 * list=A(2), result=C(3)
70 * We pop A and do the same.
72 * list=B(3), result=C(3)
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:
78 * list=C(7), result=C(7) B(3)
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
85 * Another pathological example how this thing can fail to mark an ancestor
86 * of a merge base as UNINTERESTING without the postprocessing phase.
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
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.
121 * and we end up showing E as an interesting merge base.
124 static int show_all
= 0;
126 static int merge_base(struct commit
*rev1
, struct commit
*rev2
)
128 struct commit_list
*list
= NULL
;
129 struct commit_list
*result
= NULL
;
130 struct commit_list
*tmp
= NULL
;
133 printf("%s\n", sha1_to_hex(rev1
->object
.sha1
));
140 rev1
->object
.flags
|= 1;
141 rev2
->object
.flags
|= 2;
142 insert_by_date(rev1
, &list
);
143 insert_by_date(rev2
, &list
);
145 while (interesting(list
)) {
146 struct commit
*commit
= list
->item
;
147 struct commit_list
*parents
;
148 int flags
= commit
->object
.flags
& 7;
154 insert_by_date(commit
, &result
);
156 /* Mark parents of a found merge uninteresting */
157 flags
|= UNINTERESTING
;
159 parents
= commit
->parents
;
161 struct commit
*p
= parents
->item
;
162 parents
= parents
->next
;
163 if ((p
->object
.flags
& flags
) == flags
)
166 p
->object
.flags
|= flags
;
167 insert_by_date(p
, &list
);
175 * Postprocess to fully contaminate the well.
177 for (tmp
= result
; tmp
; tmp
= tmp
->next
) {
178 struct commit
*c
= tmp
->item
;
179 /* Reinject uninteresting ones to list,
180 * so we can scan their parents.
182 if (c
->object
.flags
& UNINTERESTING
)
183 commit_list_insert(c
, &list
);
186 struct commit
*c
= list
->item
;
187 struct commit_list
*parents
;
193 /* Anything taken out of the list is uninteresting, so
194 * mark all its parents uninteresting. We do not
195 * parse new ones (we already parsed all the relevant
198 parents
= c
->parents
;
200 struct commit
*p
= parents
->item
;
201 parents
= parents
->next
;
202 if (!(p
->object
.flags
& UNINTERESTING
)) {
203 p
->object
.flags
|= UNINTERESTING
;
204 commit_list_insert(p
, &list
);
210 struct commit
*commit
= result
->item
;
211 result
= result
->next
;
212 if (commit
->object
.flags
& UNINTERESTING
)
214 printf("%s\n", sha1_to_hex(commit
->object
.sha1
));
217 commit
->object
.flags
|= UNINTERESTING
;
222 static const char merge_base_usage
[] =
223 "git-merge-base [--all] <commit-id> <commit-id>";
225 int main(int argc
, char **argv
)
227 struct commit
*rev1
, *rev2
;
228 unsigned char rev1key
[20], rev2key
[20];
230 while (1 < argc
&& argv
[1][0] == '-') {
232 if (!strcmp(arg
, "-a") || !strcmp(arg
, "--all"))
235 usage(merge_base_usage
);
239 get_sha1(argv
[1], rev1key
) ||
240 get_sha1(argv
[2], rev2key
))
241 usage(merge_base_usage
);
242 rev1
= lookup_commit_reference(rev1key
);
243 rev2
= lookup_commit_reference(rev2key
);
246 return merge_base(rev1
, rev2
);