1#include "builtin.h"
2#include "tree-walk.h"
3#include "xdiff-interface.h"
4#include "object-store.h"
5#include "blob.h"
6#include "exec_cmd.h"
7#include "merge-blobs.h"
8
9static const char merge_tree_usage[] = "git merge-tree <base-tree> <branch1> <branch2>";
10
11struct merge_list {
12 struct merge_list *next;
13 struct merge_list *link; /* other stages for this object */
14
15 unsigned int stage : 2;
16 unsigned int mode;
17 const char *path;
18 struct blob *blob;
19};
20
21static struct merge_list *merge_result, **merge_result_end = &merge_result;
22
23static void add_merge_entry(struct merge_list *entry)
24{
25 *merge_result_end = entry;
26 merge_result_end = &entry->next;
27}
28
29static void merge_trees(struct tree_desc t[3], const char *base);
30
31static const char *explanation(struct merge_list *entry)
32{
33 switch (entry->stage) {
34 case 0:
35 return "merged";
36 case 3:
37 return "added in remote";
38 case 2:
39 if (entry->link)
40 return "added in both";
41 return "added in local";
42 }
43
44 /* Existed in base */
45 entry = entry->link;
46 if (!entry)
47 return "removed in both";
48
49 if (entry->link)
50 return "changed in both";
51
52 if (entry->stage == 3)
53 return "removed in local";
54 return "removed in remote";
55}
56
57static void *result(struct merge_list *entry, unsigned long *size)
58{
59 enum object_type type;
60 struct blob *base, *our, *their;
61 const char *path = entry->path;
62
63 if (!entry->stage)
64 return read_object_file(&entry->blob->object.oid, &type, size);
65 base = NULL;
66 if (entry->stage == 1) {
67 base = entry->blob;
68 entry = entry->link;
69 }
70 our = NULL;
71 if (entry && entry->stage == 2) {
72 our = entry->blob;
73 entry = entry->link;
74 }
75 their = NULL;
76 if (entry)
77 their = entry->blob;
78 return merge_blobs(path, base, our, their, size);
79}
80
81static void *origin(struct merge_list *entry, unsigned long *size)
82{
83 enum object_type type;
84 while (entry) {
85 if (entry->stage == 2)
86 return read_object_file(&entry->blob->object.oid,
87 &type, size);
88 entry = entry->link;
89 }
90 return NULL;
91}
92
93static int show_outf(void *priv_, mmbuffer_t *mb, int nbuf)
94{
95 int i;
96 for (i = 0; i < nbuf; i++)
97 printf("%.*s", (int) mb[i].size, mb[i].ptr);
98 return 0;
99}
100
101static void show_diff(struct merge_list *entry)
102{
103 unsigned long size;
104 mmfile_t src, dst;
105 xpparam_t xpp;
106 xdemitconf_t xecfg;
107 xdemitcb_t ecb;
108
109 xpp.flags = 0;
110 memset(&xecfg, 0, sizeof(xecfg));
111 xecfg.ctxlen = 3;
112 ecb.outf = show_outf;
113 ecb.priv = NULL;
114
115 src.ptr = origin(entry, &size);
116 if (!src.ptr)
117 size = 0;
118 src.size = size;
119 dst.ptr = result(entry, &size);
120 if (!dst.ptr)
121 size = 0;
122 dst.size = size;
123 if (xdi_diff(&src, &dst, &xpp, &xecfg, &ecb))
124 die("unable to generate diff");
125 free(src.ptr);
126 free(dst.ptr);
127}
128
129static void show_result_list(struct merge_list *entry)
130{
131 printf("%s\n", explanation(entry));
132 do {
133 struct merge_list *link = entry->link;
134 static const char *desc[4] = { "result", "base", "our", "their" };
135 printf(" %-6s %o %s %s\n", desc[entry->stage], entry->mode, oid_to_hex(&entry->blob->object.oid), entry->path);
136 entry = link;
137 } while (entry);
138}
139
140static void show_result(void)
141{
142 struct merge_list *walk;
143
144 walk = merge_result;
145 while (walk) {
146 show_result_list(walk);
147 show_diff(walk);
148 walk = walk->next;
149 }
150}
151
152/* An empty entry never compares same, not even to another empty entry */
153static int same_entry(struct name_entry *a, struct name_entry *b)
154{
155 return a->oid &&
156 b->oid &&
157 !oidcmp(a->oid, b->oid) &&
158 a->mode == b->mode;
159}
160
161static int both_empty(struct name_entry *a, struct name_entry *b)
162{
163 return !(a->oid || b->oid);
164}
165
166static struct merge_list *create_entry(unsigned stage, unsigned mode, const struct object_id *oid, const char *path)
167{
168 struct merge_list *res = xcalloc(1, sizeof(*res));
169
170 res->stage = stage;
171 res->path = path;
172 res->mode = mode;
173 res->blob = lookup_blob(oid);
174 return res;
175}
176
177static char *traverse_path(const struct traverse_info *info, const struct name_entry *n)
178{
179 char *path = xmallocz(traverse_path_len(info, n));
180 return make_traverse_path(path, info, n);
181}
182
183static void resolve(const struct traverse_info *info, struct name_entry *ours, struct name_entry *result)
184{
185 struct merge_list *orig, *final;
186 const char *path;
187
188 /* If it's already ours, don't bother showing it */
189 if (!ours)
190 return;
191
192 path = traverse_path(info, result);
193 orig = create_entry(2, ours->mode, ours->oid, path);
194 final = create_entry(0, result->mode, result->oid, path);
195
196 final->link = orig;
197
198 add_merge_entry(final);
199}
200
201static void unresolved_directory(const struct traverse_info *info,
202 struct name_entry n[3])
203{
204 char *newbase;
205 struct name_entry *p;
206 struct tree_desc t[3];
207 void *buf0, *buf1, *buf2;
208
209 for (p = n; p < n + 3; p++) {
210 if (p->mode && S_ISDIR(p->mode))
211 break;
212 }
213 if (n + 3 <= p)
214 return; /* there is no tree here */
215
216 newbase = traverse_path(info, p);
217
218#define ENTRY_OID(e) (((e)->mode && S_ISDIR((e)->mode)) ? (e)->oid : NULL)
219 buf0 = fill_tree_descriptor(t + 0, ENTRY_OID(n + 0));
220 buf1 = fill_tree_descriptor(t + 1, ENTRY_OID(n + 1));
221 buf2 = fill_tree_descriptor(t + 2, ENTRY_OID(n + 2));
222#undef ENTRY_OID
223
224 merge_trees(t, newbase);
225
226 free(buf0);
227 free(buf1);
228 free(buf2);
229 free(newbase);
230}
231
232
233static struct merge_list *link_entry(unsigned stage, const struct traverse_info *info, struct name_entry *n, struct merge_list *entry)
234{
235 const char *path;
236 struct merge_list *link;
237
238 if (!n->mode)
239 return entry;
240 if (entry)
241 path = entry->path;
242 else
243 path = traverse_path(info, n);
244 link = create_entry(stage, n->mode, n->oid, path);
245 link->link = entry;
246 return link;
247}
248
249static void unresolved(const struct traverse_info *info, struct name_entry n[3])
250{
251 struct merge_list *entry = NULL;
252 int i;
253 unsigned dirmask = 0, mask = 0;
254
255 for (i = 0; i < 3; i++) {
256 mask |= (1 << i);
257 /*
258 * Treat missing entries as directories so that we return
259 * after unresolved_directory has handled this.
260 */
261 if (!n[i].mode || S_ISDIR(n[i].mode))
262 dirmask |= (1 << i);
263 }
264
265 unresolved_directory(info, n);
266
267 if (dirmask == mask)
268 return;
269
270 if (n[2].mode && !S_ISDIR(n[2].mode))
271 entry = link_entry(3, info, n + 2, entry);
272 if (n[1].mode && !S_ISDIR(n[1].mode))
273 entry = link_entry(2, info, n + 1, entry);
274 if (n[0].mode && !S_ISDIR(n[0].mode))
275 entry = link_entry(1, info, n + 0, entry);
276
277 add_merge_entry(entry);
278}
279
280/*
281 * Merge two trees together (t[1] and t[2]), using a common base (t[0])
282 * as the origin.
283 *
284 * This walks the (sorted) trees in lock-step, checking every possible
285 * name. Note that directories automatically sort differently from other
286 * files (see "base_name_compare"), so you'll never see file/directory
287 * conflicts, because they won't ever compare the same.
288 *
289 * IOW, if a directory changes to a filename, it will automatically be
290 * seen as the directory going away, and the filename being created.
291 *
292 * Think of this as a three-way diff.
293 *
294 * The output will be either:
295 * - successful merge
296 * "0 mode sha1 filename"
297 * NOTE NOTE NOTE! FIXME! We really really need to walk the index
298 * in parallel with this too!
299 *
300 * - conflict:
301 * "1 mode sha1 filename"
302 * "2 mode sha1 filename"
303 * "3 mode sha1 filename"
304 * where not all of the 1/2/3 lines may exist, of course.
305 *
306 * The successful merge rules are the same as for the three-way merge
307 * in git-read-tree.
308 */
309static int threeway_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *entry, struct traverse_info *info)
310{
311 /* Same in both? */
312 if (same_entry(entry+1, entry+2) || both_empty(entry+1, entry+2)) {
313 /* Modified, added or removed identically */
314 resolve(info, NULL, entry+1);
315 return mask;
316 }
317
318 if (same_entry(entry+0, entry+1)) {
319 if (entry[2].oid && !S_ISDIR(entry[2].mode)) {
320 /* We did not touch, they modified -- take theirs */
321 resolve(info, entry+1, entry+2);
322 return mask;
323 }
324 /*
325 * If we did not touch a directory but they made it
326 * into a file, we fall through and unresolved()
327 * recurses down. Likewise for the opposite case.
328 */
329 }
330
331 if (same_entry(entry+0, entry+2) || both_empty(entry+0, entry+2)) {
332 /* We added, modified or removed, they did not touch -- take ours */
333 resolve(info, NULL, entry+1);
334 return mask;
335 }
336
337 unresolved(info, entry);
338 return mask;
339}
340
341static void merge_trees(struct tree_desc t[3], const char *base)
342{
343 struct traverse_info info;
344
345 setup_traverse_info(&info, base);
346 info.fn = threeway_callback;
347 traverse_trees(3, t, &info);
348}
349
350static void *get_tree_descriptor(struct tree_desc *desc, const char *rev)
351{
352 struct object_id oid;
353 void *buf;
354
355 if (get_oid(rev, &oid))
356 die("unknown rev %s", rev);
357 buf = fill_tree_descriptor(desc, &oid);
358 if (!buf)
359 die("%s is not a tree", rev);
360 return buf;
361}
362
363int cmd_merge_tree(int argc, const char **argv, const char *prefix)
364{
365 struct tree_desc t[3];
366 void *buf1, *buf2, *buf3;
367
368 if (argc != 4)
369 usage(merge_tree_usage);
370
371 buf1 = get_tree_descriptor(t+0, argv[1]);
372 buf2 = get_tree_descriptor(t+1, argv[2]);
373 buf3 = get_tree_descriptor(t+2, argv[3]);
374 merge_trees(t, "");
375 free(buf1);
376 free(buf2);
377 free(buf3);
378
379 show_result();
380 return 0;
381}