aboutsummaryrefslogtreecommitdiff
path: root/merge-base.c
blob: e73fca7453e8141b3f371a1aeba483c9ed946ccc (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
#include <stdlib.h>
#include "cache.h"
#include "commit.h"

#define PARENT1 1
#define PARENT2 2
#define UNINTERESTING 4

static struct commit *interesting(struct commit_list *list)
{
	while (list) {
		struct commit *commit = list->item;
		list = list->next;
		if (commit->object.flags & UNINTERESTING)
			continue;
		return commit;
	}
	return NULL;
}

/*
 * A pathological example of how this thing works.
 *
 * Suppose we had this commit graph, where chronologically
 * the timestamp on the commit are A <= B <= C <= D <= E <= F
 * and we are trying to figure out the merge base for E and F
 * commits.
 *
 *                  F
 *                 / \
 *            E   A   D
 *             \ /   /  
 *              B   /
 *               \ /
 *                C
 *
 * First we push E and F to list to be processed.  E gets bit 1
 * and F gets bit 2.  The list becomes:
 *
 *     list=F(2) E(1), result=empty
 *
 * Then we pop F, the newest commit, from the list.  Its flag is 2.
 * We scan its parents, mark them reachable from the side that F is
 * reachable from, and push them to the list:
 *
 *     list=E(1) D(2) A(2), result=empty
 *
 * Next pop E and do the same.
 *
 *     list=D(2) B(1) A(2), result=empty
 *
 * Next pop D and do the same.
 *
 *     list=C(2) B(1) A(2), result=empty
 *
 * Next pop C and do the same.
 *
 *     list=B(1) A(2), result=empty
 *
 * Now it is B's turn.  We mark its parent, C, reachable from B's side,
 * and push it to the list:
 *
 *     list=C(3) A(2), result=empty
 *
 * Now pop C and notice it has flags==3.  It is placed on the result list,
 * and the list now contains:
 *
 *     list=A(2), result=C(3)
 *
 * We pop A and do the same.
 * 
 *     list=B(3), result=C(3)
 *
 * Next, we pop B and something very interesting happens.  It has flags==3
 * so it is also placed on the result list, and its parents are marked
 * uninteresting, retroactively, and placed back on the list:
 *
 *    list=C(7), result=C(7) B(3)
 * 
 * Now, list does not have any interesting commit.  So we find the newest
 * commit from the result list that is not marked uninteresting.  Which is
 * commit B.
 *
 *
 * Another pathological example how this thing can fail to mark an ancestor
 * of a merge base as UNINTERESTING without the postprocessing phase.
 *
 *		  2
 *		  H
 *	    1    / \
 *	    G   A   \
 *	    |\ /     \ 
 *	    | B       \
 *	    |  \       \
 *	     \  C       F
 *	      \  \     / 
 *	       \  D   /   
 *		\ |  /
 *		 \| /
 *		  E
 *
 *	 list			A B C D E F G H
 *	 G1 H2			- - - - - - 1 2
 *	 H2 E1 B1		- 1 - - 1 - 1 2
 *	 F2 E1 B1 A2		2 1 - - 1 2 1 2
 *	 E3 B1 A2		2 1 - - 3 2 1 2
 *	 B1 A2			2 1 - - 3 2 1 2
 *	 C1 A2			2 1 1 - 3 2 1 2
 *	 D1 A2			2 1 1 1 3 2 1 2
 *	 A2			2 1 1 1 3 2 1 2
 *	 B3			2 3 1 1 3 2 1 2
 *	 C7			2 3 7 1 3 2 1 2
 *
 * At this point, unfortunately, everybody in the list is
 * uninteresting, so we fail to complete the following two
 * steps to fully marking uninteresting commits.
 *
 *	 D7			2 3 7 7 3 2 1 2
 *	 E7			2 3 7 7 7 2 1 2
 *
 * and we end up showing E as an interesting merge base.
 */

static int show_all = 0;

static void mark_reachable_commits(struct commit_list *result,
				   struct commit_list *list)
{
	struct commit_list *tmp;

	/*
	 * Postprocess to fully contaminate the well.
	 */
	for (tmp = result; tmp; tmp = tmp->next) {
		struct commit *c = tmp->item;
		/* Reinject uninteresting ones to list,
		 * so we can scan their parents.
		 */
		if (c->object.flags & UNINTERESTING)
			commit_list_insert(c, &list);
	}
	while (list) {
		struct commit *c = list->item;
		struct commit_list *parents;

		tmp = list;
		list = list->next;
		free(tmp);

		/* Anything taken out of the list is uninteresting, so
		 * mark all its parents uninteresting.  We do not
		 * parse new ones (we already parsed all the relevant
		 * ones).
		 */
		parents = c->parents;
		while (parents) {
			struct commit *p = parents->item;
			parents = parents->next;
			if (!(p->object.flags & UNINTERESTING)) {
				p->object.flags |= UNINTERESTING;
				commit_list_insert(p, &list);
			}
		}
	}
}

static int merge_base(struct commit *rev1, struct commit *rev2)
{
	struct commit_list *list = NULL;
	struct commit_list *result = NULL;
	struct commit_list *tmp = NULL;

	if (rev1 == rev2) {
		printf("%s\n", sha1_to_hex(rev1->object.sha1));
		return 0;
	}

	parse_commit(rev1);
	parse_commit(rev2);

	rev1->object.flags |= 1;
	rev2->object.flags |= 2;
	insert_by_date(rev1, &list);
	insert_by_date(rev2, &list);

	while (interesting(list)) {
		struct commit *commit = list->item;
		struct commit_list *parents;
		int flags = commit->object.flags & 7;

		tmp = list;
		list = list->next;
		free(tmp);
		if (flags == 3) {
			insert_by_date(commit, &result);

			/* Mark parents of a found merge uninteresting */
			flags |= UNINTERESTING;
		}
		parents = commit->parents;
		while (parents) {
			struct commit *p = parents->item;
			parents = parents->next;
			if ((p->object.flags & flags) == flags)
				continue;
			parse_commit(p);
			p->object.flags |= flags;
			insert_by_date(p, &list);
		}
	}

	if (!result)
		return 1;

	if (result->next && list)
		mark_reachable_commits(result, list);

	while (result) {
		struct commit *commit = result->item;
		result = result->next;
		if (commit->object.flags & UNINTERESTING)
			continue;
		printf("%s\n", sha1_to_hex(commit->object.sha1));
		if (!show_all)
			return 0;
		commit->object.flags |= UNINTERESTING;
	}
	return 0;
}

static const char merge_base_usage[] =
"git-merge-base [--all] <commit-id> <commit-id>";

int main(int argc, char **argv)
{
	struct commit *rev1, *rev2;
	unsigned char rev1key[20], rev2key[20];

	setup_git_directory();

	while (1 < argc && argv[1][0] == '-') {
		char *arg = argv[1];
		if (!strcmp(arg, "-a") || !strcmp(arg, "--all"))
			show_all = 1;
		else
			usage(merge_base_usage);
		argc--; argv++;
	}
	if (argc != 3 ||
	    get_sha1(argv[1], rev1key) ||
	    get_sha1(argv[2], rev2key))
		usage(merge_base_usage);
	rev1 = lookup_commit_reference(rev1key);
	rev2 = lookup_commit_reference(rev2key);
	if (!rev1 || !rev2)
		return 1;
	return merge_base(rev1, rev2);
}