merge-recursive.c: Add more generic merge_recursive_generic()
[git/git.git] / merge-recursive.c
CommitLineData
9047ebbc
MV
1/*
2 * Recursive Merge algorithm stolen from git-merge-recursive.py by
3 * Fredrik Kuivinen.
4 * The thieves were Alex Riesen and Johannes Schindelin, in June/July 2006
5 */
6#include "cache.h"
7#include "cache-tree.h"
8#include "commit.h"
9#include "blob.h"
10#include "builtin.h"
11#include "tree-walk.h"
12#include "diff.h"
13#include "diffcore.h"
14#include "tag.h"
15#include "unpack-trees.h"
16#include "string-list.h"
17#include "xdiff-interface.h"
18#include "ll-merge.h"
19#include "interpolate.h"
20#include "attr.h"
21#include "merge-recursive.h"
22
23static int subtree_merge;
24
25static struct tree *shift_tree_object(struct tree *one, struct tree *two)
26{
27 unsigned char shifted[20];
28
29 /*
30 * NEEDSWORK: this limits the recursion depth to hardcoded
31 * value '2' to avoid excessive overhead.
32 */
33 shift_tree(one->object.sha1, two->object.sha1, shifted, 2);
34 if (!hashcmp(two->object.sha1, shifted))
35 return two;
36 return lookup_tree(shifted);
37}
38
39/*
40 * A virtual commit has
41 * - (const char *)commit->util set to the name, and
42 * - *(int *)commit->object.sha1 set to the virtual id.
43 */
44
45struct commit *make_virtual_commit(struct tree *tree, const char *comment)
46{
47 struct commit *commit = xcalloc(1, sizeof(struct commit));
48 static unsigned virtual_id = 1;
49 commit->tree = tree;
50 commit->util = (void*)comment;
51 *(int*)commit->object.sha1 = virtual_id++;
52 /* avoid warnings */
53 commit->object.parsed = 1;
54 return commit;
55}
56
57/*
58 * Since we use get_tree_entry(), which does not put the read object into
59 * the object pool, we cannot rely on a == b.
60 */
61static int sha_eq(const unsigned char *a, const unsigned char *b)
62{
63 if (!a && !b)
64 return 2;
65 return a && b && hashcmp(a, b) == 0;
66}
67
68/*
69 * Since we want to write the index eventually, we cannot reuse the index
70 * for these (temporary) data.
71 */
72struct stage_data
73{
74 struct
75 {
76 unsigned mode;
77 unsigned char sha[20];
78 } stages[4];
79 unsigned processed:1;
80};
81
82static struct string_list current_file_set = {NULL, 0, 0, 1};
83static struct string_list current_directory_set = {NULL, 0, 0, 1};
84
85static int call_depth = 0;
86int merge_recursive_verbosity = 2;
87static int diff_rename_limit = -1;
88static int merge_rename_limit = -1;
89static int buffer_output = 1;
90static struct strbuf obuf = STRBUF_INIT;
91
92static int show(int v)
93{
94 return (!call_depth && merge_recursive_verbosity >= v) ||
95 merge_recursive_verbosity >= 5;
96}
97
98static void flush_output(void)
99{
100 if (obuf.len) {
101 fputs(obuf.buf, stdout);
102 strbuf_reset(&obuf);
103 }
104}
105
106static void output(int v, const char *fmt, ...)
107{
108 int len;
109 va_list ap;
110
111 if (!show(v))
112 return;
113
114 strbuf_grow(&obuf, call_depth * 2 + 2);
115 memset(obuf.buf + obuf.len, ' ', call_depth * 2);
116 strbuf_setlen(&obuf, obuf.len + call_depth * 2);
117
118 va_start(ap, fmt);
119 len = vsnprintf(obuf.buf + obuf.len, strbuf_avail(&obuf), fmt, ap);
120 va_end(ap);
121
122 if (len < 0)
123 len = 0;
124 if (len >= strbuf_avail(&obuf)) {
125 strbuf_grow(&obuf, len + 2);
126 va_start(ap, fmt);
127 len = vsnprintf(obuf.buf + obuf.len, strbuf_avail(&obuf), fmt, ap);
128 va_end(ap);
129 if (len >= strbuf_avail(&obuf)) {
130 die("this should not happen, your snprintf is broken");
131 }
132 }
133 strbuf_setlen(&obuf, obuf.len + len);
134 strbuf_add(&obuf, "\n", 1);
135 if (!buffer_output)
136 flush_output();
137}
138
139static void output_commit_title(struct commit *commit)
140{
141 int i;
142 flush_output();
143 for (i = call_depth; i--;)
144 fputs(" ", stdout);
145 if (commit->util)
146 printf("virtual %s\n", (char *)commit->util);
147 else {
148 printf("%s ", find_unique_abbrev(commit->object.sha1, DEFAULT_ABBREV));
149 if (parse_commit(commit) != 0)
150 printf("(bad commit)\n");
151 else {
152 const char *s;
153 int len;
154 for (s = commit->buffer; *s; s++)
155 if (*s == '\n' && s[1] == '\n') {
156 s += 2;
157 break;
158 }
159 for (len = 0; s[len] && '\n' != s[len]; len++)
160 ; /* do nothing */
161 printf("%.*s\n", len, s);
162 }
163 }
164}
165
166static int add_cacheinfo(unsigned int mode, const unsigned char *sha1,
167 const char *path, int stage, int refresh, int options)
168{
169 struct cache_entry *ce;
170 ce = make_cache_entry(mode, sha1 ? sha1 : null_sha1, path, stage, refresh);
171 if (!ce)
172 return error("addinfo_cache failed for path '%s'", path);
173 return add_cache_entry(ce, options);
174}
175
176/*
177 * This is a global variable which is used in a number of places but
178 * only written to in the 'merge' function.
179 *
180 * index_only == 1 => Don't leave any non-stage 0 entries in the cache and
181 * don't update the working directory.
182 * 0 => Leave unmerged entries in the cache and update
183 * the working directory.
184 */
185static int index_only = 0;
186
187static void init_tree_desc_from_tree(struct tree_desc *desc, struct tree *tree)
188{
189 parse_tree(tree);
190 init_tree_desc(desc, tree->buffer, tree->size);
191}
192
193static int git_merge_trees(int index_only,
194 struct tree *common,
195 struct tree *head,
196 struct tree *merge)
197{
198 int rc;
199 struct tree_desc t[3];
200 struct unpack_trees_options opts;
201
202 memset(&opts, 0, sizeof(opts));
203 if (index_only)
204 opts.index_only = 1;
205 else
206 opts.update = 1;
207 opts.merge = 1;
208 opts.head_idx = 2;
209 opts.fn = threeway_merge;
210 opts.src_index = &the_index;
211 opts.dst_index = &the_index;
212
213 init_tree_desc_from_tree(t+0, common);
214 init_tree_desc_from_tree(t+1, head);
215 init_tree_desc_from_tree(t+2, merge);
216
217 rc = unpack_trees(3, t, &opts);
218 cache_tree_free(&active_cache_tree);
219 return rc;
220}
221
222struct tree *write_tree_from_memory(void)
223{
224 struct tree *result = NULL;
225
226 if (unmerged_cache()) {
227 int i;
228 output(0, "There are unmerged index entries:");
229 for (i = 0; i < active_nr; i++) {
230 struct cache_entry *ce = active_cache[i];
231 if (ce_stage(ce))
232 output(0, "%d %.*s", ce_stage(ce), ce_namelen(ce), ce->name);
233 }
234 return NULL;
235 }
236
237 if (!active_cache_tree)
238 active_cache_tree = cache_tree();
239
240 if (!cache_tree_fully_valid(active_cache_tree) &&
241 cache_tree_update(active_cache_tree,
242 active_cache, active_nr, 0, 0) < 0)
243 die("error building trees");
244
245 result = lookup_tree(active_cache_tree->sha1);
246
247 return result;
248}
249
250static int save_files_dirs(const unsigned char *sha1,
251 const char *base, int baselen, const char *path,
252 unsigned int mode, int stage, void *context)
253{
254 int len = strlen(path);
255 char *newpath = xmalloc(baselen + len + 1);
256 memcpy(newpath, base, baselen);
257 memcpy(newpath + baselen, path, len);
258 newpath[baselen + len] = '\0';
259
260 if (S_ISDIR(mode))
261 string_list_insert(newpath, &current_directory_set);
262 else
263 string_list_insert(newpath, &current_file_set);
264 free(newpath);
265
266 return READ_TREE_RECURSIVE;
267}
268
269static int get_files_dirs(struct tree *tree)
270{
271 int n;
272 if (read_tree_recursive(tree, "", 0, 0, NULL, save_files_dirs, NULL))
273 return 0;
274 n = current_file_set.nr + current_directory_set.nr;
275 return n;
276}
277
278/*
279 * Returns an index_entry instance which doesn't have to correspond to
280 * a real cache entry in Git's index.
281 */
282static struct stage_data *insert_stage_data(const char *path,
283 struct tree *o, struct tree *a, struct tree *b,
284 struct string_list *entries)
285{
286 struct string_list_item *item;
287 struct stage_data *e = xcalloc(1, sizeof(struct stage_data));
288 get_tree_entry(o->object.sha1, path,
289 e->stages[1].sha, &e->stages[1].mode);
290 get_tree_entry(a->object.sha1, path,
291 e->stages[2].sha, &e->stages[2].mode);
292 get_tree_entry(b->object.sha1, path,
293 e->stages[3].sha, &e->stages[3].mode);
294 item = string_list_insert(path, entries);
295 item->util = e;
296 return e;
297}
298
299/*
300 * Create a dictionary mapping file names to stage_data objects. The
301 * dictionary contains one entry for every path with a non-zero stage entry.
302 */
303static struct string_list *get_unmerged(void)
304{
305 struct string_list *unmerged = xcalloc(1, sizeof(struct string_list));
306 int i;
307
308 unmerged->strdup_strings = 1;
309
310 for (i = 0; i < active_nr; i++) {
311 struct string_list_item *item;
312 struct stage_data *e;
313 struct cache_entry *ce = active_cache[i];
314 if (!ce_stage(ce))
315 continue;
316
317 item = string_list_lookup(ce->name, unmerged);
318 if (!item) {
319 item = string_list_insert(ce->name, unmerged);
320 item->util = xcalloc(1, sizeof(struct stage_data));
321 }
322 e = item->util;
323 e->stages[ce_stage(ce)].mode = ce->ce_mode;
324 hashcpy(e->stages[ce_stage(ce)].sha, ce->sha1);
325 }
326
327 return unmerged;
328}
329
330struct rename
331{
332 struct diff_filepair *pair;
333 struct stage_data *src_entry;
334 struct stage_data *dst_entry;
335 unsigned processed:1;
336};
337
338/*
339 * Get information of all renames which occurred between 'o_tree' and
340 * 'tree'. We need the three trees in the merge ('o_tree', 'a_tree' and
341 * 'b_tree') to be able to associate the correct cache entries with
342 * the rename information. 'tree' is always equal to either a_tree or b_tree.
343 */
344static struct string_list *get_renames(struct tree *tree,
345 struct tree *o_tree,
346 struct tree *a_tree,
347 struct tree *b_tree,
348 struct string_list *entries)
349{
350 int i;
351 struct string_list *renames;
352 struct diff_options opts;
353
354 renames = xcalloc(1, sizeof(struct string_list));
355 diff_setup(&opts);
356 DIFF_OPT_SET(&opts, RECURSIVE);
357 opts.detect_rename = DIFF_DETECT_RENAME;
358 opts.rename_limit = merge_rename_limit >= 0 ? merge_rename_limit :
359 diff_rename_limit >= 0 ? diff_rename_limit :
360 500;
361 opts.warn_on_too_large_rename = 1;
362 opts.output_format = DIFF_FORMAT_NO_OUTPUT;
363 if (diff_setup_done(&opts) < 0)
364 die("diff setup failed");
365 diff_tree_sha1(o_tree->object.sha1, tree->object.sha1, "", &opts);
366 diffcore_std(&opts);
367 for (i = 0; i < diff_queued_diff.nr; ++i) {
368 struct string_list_item *item;
369 struct rename *re;
370 struct diff_filepair *pair = diff_queued_diff.queue[i];
371 if (pair->status != 'R') {
372 diff_free_filepair(pair);
373 continue;
374 }
375 re = xmalloc(sizeof(*re));
376 re->processed = 0;
377 re->pair = pair;
378 item = string_list_lookup(re->pair->one->path, entries);
379 if (!item)
380 re->src_entry = insert_stage_data(re->pair->one->path,
381 o_tree, a_tree, b_tree, entries);
382 else
383 re->src_entry = item->util;
384
385 item = string_list_lookup(re->pair->two->path, entries);
386 if (!item)
387 re->dst_entry = insert_stage_data(re->pair->two->path,
388 o_tree, a_tree, b_tree, entries);
389 else
390 re->dst_entry = item->util;
391 item = string_list_insert(pair->one->path, renames);
392 item->util = re;
393 }
394 opts.output_format = DIFF_FORMAT_NO_OUTPUT;
395 diff_queued_diff.nr = 0;
396 diff_flush(&opts);
397 return renames;
398}
399
400static int update_stages(const char *path, struct diff_filespec *o,
401 struct diff_filespec *a, struct diff_filespec *b,
402 int clear)
403{
404 int options = ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE;
405 if (clear)
406 if (remove_file_from_cache(path))
407 return -1;
408 if (o)
409 if (add_cacheinfo(o->mode, o->sha1, path, 1, 0, options))
410 return -1;
411 if (a)
412 if (add_cacheinfo(a->mode, a->sha1, path, 2, 0, options))
413 return -1;
414 if (b)
415 if (add_cacheinfo(b->mode, b->sha1, path, 3, 0, options))
416 return -1;
417 return 0;
418}
419
420static int remove_path(const char *name)
421{
422 int ret;
423 char *slash, *dirs;
424
425 ret = unlink(name);
426 if (ret)
427 return ret;
428 dirs = xstrdup(name);
429 while ((slash = strrchr(name, '/'))) {
430 *slash = '\0';
431 if (rmdir(name) != 0)
432 break;
433 }
434 free(dirs);
435 return ret;
436}
437
438static int remove_file(int clean, const char *path, int no_wd)
439{
440 int update_cache = index_only || clean;
441 int update_working_directory = !index_only && !no_wd;
442
443 if (update_cache) {
444 if (remove_file_from_cache(path))
445 return -1;
446 }
447 if (update_working_directory) {
448 unlink(path);
449 if (errno != ENOENT || errno != EISDIR)
450 return -1;
451 remove_path(path);
452 }
453 return 0;
454}
455
456static char *unique_path(const char *path, const char *branch)
457{
458 char *newpath = xmalloc(strlen(path) + 1 + strlen(branch) + 8 + 1);
459 int suffix = 0;
460 struct stat st;
461 char *p = newpath + strlen(path);
462 strcpy(newpath, path);
463 *(p++) = '~';
464 strcpy(p, branch);
465 for (; *p; ++p)
466 if ('/' == *p)
467 *p = '_';
468 while (string_list_has_string(&current_file_set, newpath) ||
469 string_list_has_string(&current_directory_set, newpath) ||
470 lstat(newpath, &st) == 0)
471 sprintf(p, "_%d", suffix++);
472
473 string_list_insert(newpath, &current_file_set);
474 return newpath;
475}
476
477static void flush_buffer(int fd, const char *buf, unsigned long size)
478{
479 while (size > 0) {
480 long ret = write_in_full(fd, buf, size);
481 if (ret < 0) {
482 /* Ignore epipe */
483 if (errno == EPIPE)
484 break;
485 die("merge-recursive: %s", strerror(errno));
486 } else if (!ret) {
487 die("merge-recursive: disk full?");
488 }
489 size -= ret;
490 buf += ret;
491 }
492}
493
494static int make_room_for_path(const char *path)
495{
496 int status;
497 const char *msg = "failed to create path '%s'%s";
498
499 status = safe_create_leading_directories_const(path);
500 if (status) {
501 if (status == -3) {
502 /* something else exists */
503 error(msg, path, ": perhaps a D/F conflict?");
504 return -1;
505 }
506 die(msg, path, "");
507 }
508
509 /* Successful unlink is good.. */
510 if (!unlink(path))
511 return 0;
512 /* .. and so is no existing file */
513 if (errno == ENOENT)
514 return 0;
515 /* .. but not some other error (who really cares what?) */
516 return error(msg, path, ": perhaps a D/F conflict?");
517}
518
519static void update_file_flags(const unsigned char *sha,
520 unsigned mode,
521 const char *path,
522 int update_cache,
523 int update_wd)
524{
525 if (index_only)
526 update_wd = 0;
527
528 if (update_wd) {
529 enum object_type type;
530 void *buf;
531 unsigned long size;
532
533 if (S_ISGITLINK(mode))
534 die("cannot read object %s '%s': It is a submodule!",
535 sha1_to_hex(sha), path);
536
537 buf = read_sha1_file(sha, &type, &size);
538 if (!buf)
539 die("cannot read object %s '%s'", sha1_to_hex(sha), path);
540 if (type != OBJ_BLOB)
541 die("blob expected for %s '%s'", sha1_to_hex(sha), path);
542 if (S_ISREG(mode)) {
543 struct strbuf strbuf;
544 strbuf_init(&strbuf, 0);
545 if (convert_to_working_tree(path, buf, size, &strbuf)) {
546 free(buf);
547 size = strbuf.len;
548 buf = strbuf_detach(&strbuf, NULL);
549 }
550 }
551
552 if (make_room_for_path(path) < 0) {
553 update_wd = 0;
554 free(buf);
555 goto update_index;
556 }
557 if (S_ISREG(mode) || (!has_symlinks && S_ISLNK(mode))) {
558 int fd;
559 if (mode & 0100)
560 mode = 0777;
561 else
562 mode = 0666;
563 fd = open(path, O_WRONLY | O_TRUNC | O_CREAT, mode);
564 if (fd < 0)
565 die("failed to open %s: %s", path, strerror(errno));
566 flush_buffer(fd, buf, size);
567 close(fd);
568 } else if (S_ISLNK(mode)) {
569 char *lnk = xmemdupz(buf, size);
570 safe_create_leading_directories_const(path);
571 unlink(path);
572 symlink(lnk, path);
573 free(lnk);
574 } else
575 die("do not know what to do with %06o %s '%s'",
576 mode, sha1_to_hex(sha), path);
577 free(buf);
578 }
579 update_index:
580 if (update_cache)
581 add_cacheinfo(mode, sha, path, 0, update_wd, ADD_CACHE_OK_TO_ADD);
582}
583
584static void update_file(int clean,
585 const unsigned char *sha,
586 unsigned mode,
587 const char *path)
588{
589 update_file_flags(sha, mode, path, index_only || clean, !index_only);
590}
591
592/* Low level file merging, update and removal */
593
594struct merge_file_info
595{
596 unsigned char sha[20];
597 unsigned mode;
598 unsigned clean:1,
599 merge:1;
600};
601
602static void fill_mm(const unsigned char *sha1, mmfile_t *mm)
603{
604 unsigned long size;
605 enum object_type type;
606
607 if (!hashcmp(sha1, null_sha1)) {
608 mm->ptr = xstrdup("");
609 mm->size = 0;
610 return;
611 }
612
613 mm->ptr = read_sha1_file(sha1, &type, &size);
614 if (!mm->ptr || type != OBJ_BLOB)
615 die("unable to read blob object %s", sha1_to_hex(sha1));
616 mm->size = size;
617}
618
619static int merge_3way(mmbuffer_t *result_buf,
620 struct diff_filespec *o,
621 struct diff_filespec *a,
622 struct diff_filespec *b,
623 const char *branch1,
624 const char *branch2)
625{
626 mmfile_t orig, src1, src2;
627 char *name1, *name2;
628 int merge_status;
629
630 name1 = xstrdup(mkpath("%s:%s", branch1, a->path));
631 name2 = xstrdup(mkpath("%s:%s", branch2, b->path));
632
633 fill_mm(o->sha1, &orig);
634 fill_mm(a->sha1, &src1);
635 fill_mm(b->sha1, &src2);
636
637 merge_status = ll_merge(result_buf, a->path, &orig,
638 &src1, name1, &src2, name2,
639 index_only);
640
641 free(name1);
642 free(name2);
643 free(orig.ptr);
644 free(src1.ptr);
645 free(src2.ptr);
646 return merge_status;
647}
648
649static struct merge_file_info merge_file(struct diff_filespec *o,
650 struct diff_filespec *a, struct diff_filespec *b,
651 const char *branch1, const char *branch2)
652{
653 struct merge_file_info result;
654 result.merge = 0;
655 result.clean = 1;
656
657 if ((S_IFMT & a->mode) != (S_IFMT & b->mode)) {
658 result.clean = 0;
659 if (S_ISREG(a->mode)) {
660 result.mode = a->mode;
661 hashcpy(result.sha, a->sha1);
662 } else {
663 result.mode = b->mode;
664 hashcpy(result.sha, b->sha1);
665 }
666 } else {
667 if (!sha_eq(a->sha1, o->sha1) && !sha_eq(b->sha1, o->sha1))
668 result.merge = 1;
669
670 /*
671 * Merge modes
672 */
673 if (a->mode == b->mode || a->mode == o->mode)
674 result.mode = b->mode;
675 else {
676 result.mode = a->mode;
677 if (b->mode != o->mode) {
678 result.clean = 0;
679 result.merge = 1;
680 }
681 }
682
683 if (sha_eq(a->sha1, b->sha1) || sha_eq(a->sha1, o->sha1))
684 hashcpy(result.sha, b->sha1);
685 else if (sha_eq(b->sha1, o->sha1))
686 hashcpy(result.sha, a->sha1);
687 else if (S_ISREG(a->mode)) {
688 mmbuffer_t result_buf;
689 int merge_status;
690
691 merge_status = merge_3way(&result_buf, o, a, b,
692 branch1, branch2);
693
694 if ((merge_status < 0) || !result_buf.ptr)
695 die("Failed to execute internal merge");
696
697 if (write_sha1_file(result_buf.ptr, result_buf.size,
698 blob_type, result.sha))
699 die("Unable to add %s to database",
700 a->path);
701
702 free(result_buf.ptr);
703 result.clean = (merge_status == 0);
704 } else if (S_ISGITLINK(a->mode)) {
705 result.clean = 0;
706 hashcpy(result.sha, a->sha1);
707 } else if (S_ISLNK(a->mode)) {
708 hashcpy(result.sha, a->sha1);
709
710 if (!sha_eq(a->sha1, b->sha1))
711 result.clean = 0;
712 } else {
713 die("unsupported object type in the tree");
714 }
715 }
716
717 return result;
718}
719
720static void conflict_rename_rename(struct rename *ren1,
721 const char *branch1,
722 struct rename *ren2,
723 const char *branch2)
724{
725 char *del[2];
726 int delp = 0;
727 const char *ren1_dst = ren1->pair->two->path;
728 const char *ren2_dst = ren2->pair->two->path;
729 const char *dst_name1 = ren1_dst;
730 const char *dst_name2 = ren2_dst;
731 if (string_list_has_string(&current_directory_set, ren1_dst)) {
732 dst_name1 = del[delp++] = unique_path(ren1_dst, branch1);
733 output(1, "%s is a directory in %s adding as %s instead",
734 ren1_dst, branch2, dst_name1);
735 remove_file(0, ren1_dst, 0);
736 }
737 if (string_list_has_string(&current_directory_set, ren2_dst)) {
738 dst_name2 = del[delp++] = unique_path(ren2_dst, branch2);
739 output(1, "%s is a directory in %s adding as %s instead",
740 ren2_dst, branch1, dst_name2);
741 remove_file(0, ren2_dst, 0);
742 }
743 if (index_only) {
744 remove_file_from_cache(dst_name1);
745 remove_file_from_cache(dst_name2);
746 /*
747 * Uncomment to leave the conflicting names in the resulting tree
748 *
749 * update_file(0, ren1->pair->two->sha1, ren1->pair->two->mode, dst_name1);
750 * update_file(0, ren2->pair->two->sha1, ren2->pair->two->mode, dst_name2);
751 */
752 } else {
753 update_stages(dst_name1, NULL, ren1->pair->two, NULL, 1);
754 update_stages(dst_name2, NULL, NULL, ren2->pair->two, 1);
755 }
756 while (delp--)
757 free(del[delp]);
758}
759
760static void conflict_rename_dir(struct rename *ren1,
761 const char *branch1)
762{
763 char *new_path = unique_path(ren1->pair->two->path, branch1);
764 output(1, "Renaming %s to %s instead", ren1->pair->one->path, new_path);
765 remove_file(0, ren1->pair->two->path, 0);
766 update_file(0, ren1->pair->two->sha1, ren1->pair->two->mode, new_path);
767 free(new_path);
768}
769
770static void conflict_rename_rename_2(struct rename *ren1,
771 const char *branch1,
772 struct rename *ren2,
773 const char *branch2)
774{
775 char *new_path1 = unique_path(ren1->pair->two->path, branch1);
776 char *new_path2 = unique_path(ren2->pair->two->path, branch2);
777 output(1, "Renaming %s to %s and %s to %s instead",
778 ren1->pair->one->path, new_path1,
779 ren2->pair->one->path, new_path2);
780 remove_file(0, ren1->pair->two->path, 0);
781 update_file(0, ren1->pair->two->sha1, ren1->pair->two->mode, new_path1);
782 update_file(0, ren2->pair->two->sha1, ren2->pair->two->mode, new_path2);
783 free(new_path2);
784 free(new_path1);
785}
786
787static int process_renames(struct string_list *a_renames,
788 struct string_list *b_renames,
789 const char *a_branch,
790 const char *b_branch)
791{
792 int clean_merge = 1, i, j;
793 struct string_list a_by_dst = {NULL, 0, 0, 0}, b_by_dst = {NULL, 0, 0, 0};
794 const struct rename *sre;
795
796 for (i = 0; i < a_renames->nr; i++) {
797 sre = a_renames->items[i].util;
798 string_list_insert(sre->pair->two->path, &a_by_dst)->util
799 = sre->dst_entry;
800 }
801 for (i = 0; i < b_renames->nr; i++) {
802 sre = b_renames->items[i].util;
803 string_list_insert(sre->pair->two->path, &b_by_dst)->util
804 = sre->dst_entry;
805 }
806
807 for (i = 0, j = 0; i < a_renames->nr || j < b_renames->nr;) {
808 int compare;
809 char *src;
810 struct string_list *renames1, *renames2, *renames2Dst;
811 struct rename *ren1 = NULL, *ren2 = NULL;
812 const char *branch1, *branch2;
813 const char *ren1_src, *ren1_dst;
814
815 if (i >= a_renames->nr) {
816 compare = 1;
817 ren2 = b_renames->items[j++].util;
818 } else if (j >= b_renames->nr) {
819 compare = -1;
820 ren1 = a_renames->items[i++].util;
821 } else {
822 compare = strcmp(a_renames->items[i].string,
823 b_renames->items[j].string);
824 if (compare <= 0)
825 ren1 = a_renames->items[i++].util;
826 if (compare >= 0)
827 ren2 = b_renames->items[j++].util;
828 }
829
830 /* TODO: refactor, so that 1/2 are not needed */
831 if (ren1) {
832 renames1 = a_renames;
833 renames2 = b_renames;
834 renames2Dst = &b_by_dst;
835 branch1 = a_branch;
836 branch2 = b_branch;
837 } else {
838 struct rename *tmp;
839 renames1 = b_renames;
840 renames2 = a_renames;
841 renames2Dst = &a_by_dst;
842 branch1 = b_branch;
843 branch2 = a_branch;
844 tmp = ren2;
845 ren2 = ren1;
846 ren1 = tmp;
847 }
848 src = ren1->pair->one->path;
849
850 ren1->dst_entry->processed = 1;
851 ren1->src_entry->processed = 1;
852
853 if (ren1->processed)
854 continue;
855 ren1->processed = 1;
856
857 ren1_src = ren1->pair->one->path;
858 ren1_dst = ren1->pair->two->path;
859
860 if (ren2) {
861 const char *ren2_src = ren2->pair->one->path;
862 const char *ren2_dst = ren2->pair->two->path;
863 /* Renamed in 1 and renamed in 2 */
864 if (strcmp(ren1_src, ren2_src) != 0)
865 die("ren1.src != ren2.src");
866 ren2->dst_entry->processed = 1;
867 ren2->processed = 1;
868 if (strcmp(ren1_dst, ren2_dst) != 0) {
869 clean_merge = 0;
870 output(1, "CONFLICT (rename/rename): "
871 "Rename \"%s\"->\"%s\" in branch \"%s\" "
872 "rename \"%s\"->\"%s\" in \"%s\"%s",
873 src, ren1_dst, branch1,
874 src, ren2_dst, branch2,
875 index_only ? " (left unresolved)": "");
876 if (index_only) {
877 remove_file_from_cache(src);
878 update_file(0, ren1->pair->one->sha1,
879 ren1->pair->one->mode, src);
880 }
881 conflict_rename_rename(ren1, branch1, ren2, branch2);
882 } else {
883 struct merge_file_info mfi;
884 remove_file(1, ren1_src, 1);
885 mfi = merge_file(ren1->pair->one,
886 ren1->pair->two,
887 ren2->pair->two,
888 branch1,
889 branch2);
890 if (mfi.merge || !mfi.clean)
891 output(1, "Renaming %s->%s", src, ren1_dst);
892
893 if (mfi.merge)
894 output(2, "Auto-merging %s", ren1_dst);
895
896 if (!mfi.clean) {
897 output(1, "CONFLICT (content): merge conflict in %s",
898 ren1_dst);
899 clean_merge = 0;
900
901 if (!index_only)
902 update_stages(ren1_dst,
903 ren1->pair->one,
904 ren1->pair->two,
905 ren2->pair->two,
906 1 /* clear */);
907 }
908 update_file(mfi.clean, mfi.sha, mfi.mode, ren1_dst);
909 }
910 } else {
911 /* Renamed in 1, maybe changed in 2 */
912 struct string_list_item *item;
913 /* we only use sha1 and mode of these */
914 struct diff_filespec src_other, dst_other;
915 int try_merge, stage = a_renames == renames1 ? 3: 2;
916
917 remove_file(1, ren1_src, index_only || stage == 3);
918
919 hashcpy(src_other.sha1, ren1->src_entry->stages[stage].sha);
920 src_other.mode = ren1->src_entry->stages[stage].mode;
921 hashcpy(dst_other.sha1, ren1->dst_entry->stages[stage].sha);
922 dst_other.mode = ren1->dst_entry->stages[stage].mode;
923
924 try_merge = 0;
925
926 if (string_list_has_string(&current_directory_set, ren1_dst)) {
927 clean_merge = 0;
928 output(1, "CONFLICT (rename/directory): Rename %s->%s in %s "
929 " directory %s added in %s",
930 ren1_src, ren1_dst, branch1,
931 ren1_dst, branch2);
932 conflict_rename_dir(ren1, branch1);
933 } else if (sha_eq(src_other.sha1, null_sha1)) {
934 clean_merge = 0;
935 output(1, "CONFLICT (rename/delete): Rename %s->%s in %s "
936 "and deleted in %s",
937 ren1_src, ren1_dst, branch1,
938 branch2);
939 update_file(0, ren1->pair->two->sha1, ren1->pair->two->mode, ren1_dst);
940 } else if (!sha_eq(dst_other.sha1, null_sha1)) {
941 const char *new_path;
942 clean_merge = 0;
943 try_merge = 1;
944 output(1, "CONFLICT (rename/add): Rename %s->%s in %s. "
945 "%s added in %s",
946 ren1_src, ren1_dst, branch1,
947 ren1_dst, branch2);
948 new_path = unique_path(ren1_dst, branch2);
949 output(1, "Adding as %s instead", new_path);
950 update_file(0, dst_other.sha1, dst_other.mode, new_path);
951 } else if ((item = string_list_lookup(ren1_dst, renames2Dst))) {
952 ren2 = item->util;
953 clean_merge = 0;
954 ren2->processed = 1;
955 output(1, "CONFLICT (rename/rename): Rename %s->%s in %s. "
956 "Rename %s->%s in %s",
957 ren1_src, ren1_dst, branch1,
958 ren2->pair->one->path, ren2->pair->two->path, branch2);
959 conflict_rename_rename_2(ren1, branch1, ren2, branch2);
960 } else
961 try_merge = 1;
962
963 if (try_merge) {
964 struct diff_filespec *o, *a, *b;
965 struct merge_file_info mfi;
966 src_other.path = (char *)ren1_src;
967
968 o = ren1->pair->one;
969 if (a_renames == renames1) {
970 a = ren1->pair->two;
971 b = &src_other;
972 } else {
973 b = ren1->pair->two;
974 a = &src_other;
975 }
976 mfi = merge_file(o, a, b,
977 a_branch, b_branch);
978
979 if (mfi.clean &&
980 sha_eq(mfi.sha, ren1->pair->two->sha1) &&
981 mfi.mode == ren1->pair->two->mode)
982 /*
983 * This messaged is part of
984 * t6022 test. If you change
985 * it update the test too.
986 */
987 output(3, "Skipped %s (merged same as existing)", ren1_dst);
988 else {
989 if (mfi.merge || !mfi.clean)
990 output(1, "Renaming %s => %s", ren1_src, ren1_dst);
991 if (mfi.merge)
992 output(2, "Auto-merging %s", ren1_dst);
993 if (!mfi.clean) {
994 output(1, "CONFLICT (rename/modify): Merge conflict in %s",
995 ren1_dst);
996 clean_merge = 0;
997
998 if (!index_only)
999 update_stages(ren1_dst,
1000 o, a, b, 1);
1001 }
1002 update_file(mfi.clean, mfi.sha, mfi.mode, ren1_dst);
1003 }
1004 }
1005 }
1006 }
1007 string_list_clear(&a_by_dst, 0);
1008 string_list_clear(&b_by_dst, 0);
1009
1010 return clean_merge;
1011}
1012
1013static unsigned char *stage_sha(const unsigned char *sha, unsigned mode)
1014{
1015 return (is_null_sha1(sha) || mode == 0) ? NULL: (unsigned char *)sha;
1016}
1017
1018/* Per entry merge function */
1019static int process_entry(const char *path, struct stage_data *entry,
1020 const char *branch1,
1021 const char *branch2)
1022{
1023 /*
1024 printf("processing entry, clean cache: %s\n", index_only ? "yes": "no");
1025 print_index_entry("\tpath: ", entry);
1026 */
1027 int clean_merge = 1;
1028 unsigned o_mode = entry->stages[1].mode;
1029 unsigned a_mode = entry->stages[2].mode;
1030 unsigned b_mode = entry->stages[3].mode;
1031 unsigned char *o_sha = stage_sha(entry->stages[1].sha, o_mode);
1032 unsigned char *a_sha = stage_sha(entry->stages[2].sha, a_mode);
1033 unsigned char *b_sha = stage_sha(entry->stages[3].sha, b_mode);
1034
1035 if (o_sha && (!a_sha || !b_sha)) {
1036 /* Case A: Deleted in one */
1037 if ((!a_sha && !b_sha) ||
1038 (sha_eq(a_sha, o_sha) && !b_sha) ||
1039 (!a_sha && sha_eq(b_sha, o_sha))) {
1040 /* Deleted in both or deleted in one and
1041 * unchanged in the other */
1042 if (a_sha)
1043 output(2, "Removing %s", path);
1044 /* do not touch working file if it did not exist */
1045 remove_file(1, path, !a_sha);
1046 } else {
1047 /* Deleted in one and changed in the other */
1048 clean_merge = 0;
1049 if (!a_sha) {
1050 output(1, "CONFLICT (delete/modify): %s deleted in %s "
1051 "and modified in %s. Version %s of %s left in tree.",
1052 path, branch1,
1053 branch2, branch2, path);
1054 update_file(0, b_sha, b_mode, path);
1055 } else {
1056 output(1, "CONFLICT (delete/modify): %s deleted in %s "
1057 "and modified in %s. Version %s of %s left in tree.",
1058 path, branch2,
1059 branch1, branch1, path);
1060 update_file(0, a_sha, a_mode, path);
1061 }
1062 }
1063
1064 } else if ((!o_sha && a_sha && !b_sha) ||
1065 (!o_sha && !a_sha && b_sha)) {
1066 /* Case B: Added in one. */
1067 const char *add_branch;
1068 const char *other_branch;
1069 unsigned mode;
1070 const unsigned char *sha;
1071 const char *conf;
1072
1073 if (a_sha) {
1074 add_branch = branch1;
1075 other_branch = branch2;
1076 mode = a_mode;
1077 sha = a_sha;
1078 conf = "file/directory";
1079 } else {
1080 add_branch = branch2;
1081 other_branch = branch1;
1082 mode = b_mode;
1083 sha = b_sha;
1084 conf = "directory/file";
1085 }
1086 if (string_list_has_string(&current_directory_set, path)) {
1087 const char *new_path = unique_path(path, add_branch);
1088 clean_merge = 0;
1089 output(1, "CONFLICT (%s): There is a directory with name %s in %s. "
1090 "Adding %s as %s",
1091 conf, path, other_branch, path, new_path);
1092 remove_file(0, path, 0);
1093 update_file(0, sha, mode, new_path);
1094 } else {
1095 output(2, "Adding %s", path);
1096 update_file(1, sha, mode, path);
1097 }
1098 } else if (a_sha && b_sha) {
1099 /* Case C: Added in both (check for same permissions) and */
1100 /* case D: Modified in both, but differently. */
1101 const char *reason = "content";
1102 struct merge_file_info mfi;
1103 struct diff_filespec o, a, b;
1104
1105 if (!o_sha) {
1106 reason = "add/add";
1107 o_sha = (unsigned char *)null_sha1;
1108 }
1109 output(2, "Auto-merging %s", path);
1110 o.path = a.path = b.path = (char *)path;
1111 hashcpy(o.sha1, o_sha);
1112 o.mode = o_mode;
1113 hashcpy(a.sha1, a_sha);
1114 a.mode = a_mode;
1115 hashcpy(b.sha1, b_sha);
1116 b.mode = b_mode;
1117
1118 mfi = merge_file(&o, &a, &b,
1119 branch1, branch2);
1120
1121 clean_merge = mfi.clean;
1122 if (mfi.clean)
1123 update_file(1, mfi.sha, mfi.mode, path);
1124 else if (S_ISGITLINK(mfi.mode))
1125 output(1, "CONFLICT (submodule): Merge conflict in %s "
1126 "- needs %s", path, sha1_to_hex(b.sha1));
1127 else {
1128 output(1, "CONFLICT (%s): Merge conflict in %s",
1129 reason, path);
1130
1131 if (index_only)
1132 update_file(0, mfi.sha, mfi.mode, path);
1133 else
1134 update_file_flags(mfi.sha, mfi.mode, path,
1135 0 /* update_cache */, 1 /* update_working_directory */);
1136 }
1137 } else if (!o_sha && !a_sha && !b_sha) {
1138 /*
1139 * this entry was deleted altogether. a_mode == 0 means
1140 * we had that path and want to actively remove it.
1141 */
1142 remove_file(1, path, !a_mode);
1143 } else
1144 die("Fatal merge failure, shouldn't happen.");
1145
1146 return clean_merge;
1147}
1148
1149int merge_trees(struct tree *head,
1150 struct tree *merge,
1151 struct tree *common,
1152 const char *branch1,
1153 const char *branch2,
1154 struct tree **result)
1155{
1156 int code, clean;
1157
1158 if (subtree_merge) {
1159 merge = shift_tree_object(head, merge);
1160 common = shift_tree_object(head, common);
1161 }
1162
1163 if (sha_eq(common->object.sha1, merge->object.sha1)) {
1164 output(0, "Already uptodate!");
1165 *result = head;
1166 return 1;
1167 }
1168
1169 code = git_merge_trees(index_only, common, head, merge);
1170
1171 if (code != 0)
1172 die("merging of trees %s and %s failed",
1173 sha1_to_hex(head->object.sha1),
1174 sha1_to_hex(merge->object.sha1));
1175
1176 if (unmerged_cache()) {
1177 struct string_list *entries, *re_head, *re_merge;
1178 int i;
1179 string_list_clear(&current_file_set, 1);
1180 string_list_clear(&current_directory_set, 1);
1181 get_files_dirs(head);
1182 get_files_dirs(merge);
1183
1184 entries = get_unmerged();
1185 re_head = get_renames(head, common, head, merge, entries);
1186 re_merge = get_renames(merge, common, head, merge, entries);
1187 clean = process_renames(re_head, re_merge,
1188 branch1, branch2);
1189 for (i = 0; i < entries->nr; i++) {
1190 const char *path = entries->items[i].string;
1191 struct stage_data *e = entries->items[i].util;
1192 if (!e->processed
1193 && !process_entry(path, e, branch1, branch2))
1194 clean = 0;
1195 }
1196
1197 string_list_clear(re_merge, 0);
1198 string_list_clear(re_head, 0);
1199 string_list_clear(entries, 1);
1200
1201 }
1202 else
1203 clean = 1;
1204
1205 if (index_only)
1206 *result = write_tree_from_memory();
1207
1208 return clean;
1209}
1210
1211static struct commit_list *reverse_commit_list(struct commit_list *list)
1212{
1213 struct commit_list *next = NULL, *current, *backup;
1214 for (current = list; current; current = backup) {
1215 backup = current->next;
1216 current->next = next;
1217 next = current;
1218 }
1219 return next;
1220}
1221
1222/*
1223 * Merge the commits h1 and h2, return the resulting virtual
1224 * commit object and a flag indicating the cleanness of the merge.
1225 */
1226int merge_recursive(struct commit *h1,
1227 struct commit *h2,
1228 const char *branch1,
1229 const char *branch2,
1230 struct commit_list *ca,
1231 struct commit **result)
1232{
1233 struct commit_list *iter;
1234 struct commit *merged_common_ancestors;
1235 struct tree *mrtree = mrtree;
1236 int clean;
1237
1238 if (show(4)) {
1239 output(4, "Merging:");
1240 output_commit_title(h1);
1241 output_commit_title(h2);
1242 }
1243
1244 if (!ca) {
1245 ca = get_merge_bases(h1, h2, 1);
1246 ca = reverse_commit_list(ca);
1247 }
1248
1249 if (show(5)) {
1250 output(5, "found %u common ancestor(s):", commit_list_count(ca));
1251 for (iter = ca; iter; iter = iter->next)
1252 output_commit_title(iter->item);
1253 }
1254
1255 merged_common_ancestors = pop_commit(&ca);
1256 if (merged_common_ancestors == NULL) {
1257 /* if there is no common ancestor, make an empty tree */
1258 struct tree *tree = xcalloc(1, sizeof(struct tree));
1259
1260 tree->object.parsed = 1;
1261 tree->object.type = OBJ_TREE;
1262 pretend_sha1_file(NULL, 0, OBJ_TREE, tree->object.sha1);
1263 merged_common_ancestors = make_virtual_commit(tree, "ancestor");
1264 }
1265
1266 for (iter = ca; iter; iter = iter->next) {
1267 call_depth++;
1268 /*
1269 * When the merge fails, the result contains files
1270 * with conflict markers. The cleanness flag is
1271 * ignored, it was never actually used, as result of
1272 * merge_trees has always overwritten it: the committed
1273 * "conflicts" were already resolved.
1274 */
1275 discard_cache();
1276 merge_recursive(merged_common_ancestors, iter->item,
1277 "Temporary merge branch 1",
1278 "Temporary merge branch 2",
1279 NULL,
1280 &merged_common_ancestors);
1281 call_depth--;
1282
1283 if (!merged_common_ancestors)
1284 die("merge returned no commit");
1285 }
1286
1287 discard_cache();
1288 if (!call_depth) {
1289 read_cache();
1290 index_only = 0;
1291 } else
1292 index_only = 1;
1293
1294 clean = merge_trees(h1->tree, h2->tree, merged_common_ancestors->tree,
1295 branch1, branch2, &mrtree);
1296
1297 if (index_only) {
1298 *result = make_virtual_commit(mrtree, "merged tree");
1299 commit_list_insert(h1, &(*result)->parents);
1300 commit_list_insert(h2, &(*result)->parents->next);
1301 }
1302 flush_output();
1303 return clean;
1304}
1305
73118f89
SB
1306static struct commit *get_ref(const unsigned char *sha1, const char *name)
1307{
1308 struct object *object;
1309
1310 object = deref_tag(parse_object(sha1), name, strlen(name));
1311 if (!object)
1312 return NULL;
1313 if (object->type == OBJ_TREE)
1314 return make_virtual_commit((struct tree*)object, name);
1315 if (object->type != OBJ_COMMIT)
1316 return NULL;
1317 if (parse_commit((struct commit *)object))
1318 return NULL;
1319 return (struct commit *)object;
1320}
1321
1322int merge_recursive_generic(const char **base_list,
1323 const unsigned char *head_sha1, const char *head_name,
1324 const unsigned char *next_sha1, const char *next_name)
1325{
1326 int clean, index_fd;
1327 struct lock_file *lock = xcalloc(1, sizeof(struct lock_file));
1328 struct commit *result;
1329 struct commit *head_commit = get_ref(head_sha1, head_name);
1330 struct commit *next_commit = get_ref(next_sha1, next_name);
1331 struct commit_list *ca = NULL;
1332
1333 if (base_list) {
1334 int i;
1335 for (i = 0; base_list[i]; ++i) {
1336 unsigned char sha[20];
1337 struct commit *base;
1338 if (get_sha1(base_list[i], sha))
1339 return error("Could not resolve ref '%s'",
1340 base_list[i]);
1341 if (!(base = get_ref(sha, base_list[i])))
1342 return error("Could not parse object '%s'",
1343 base_list[i]);
1344 commit_list_insert(base, &ca);
1345 }
1346 }
1347
1348 index_fd = hold_locked_index(lock, 1);
1349 clean = merge_recursive(head_commit, next_commit,
1350 head_name, next_name, ca, &result);
1351 if (active_cache_changed &&
1352 (write_cache(index_fd, active_cache, active_nr) ||
1353 commit_locked_index(lock)))
1354 return error("Unable to write index.");
1355
1356 return clean ? 0 : 1;
1357}
1358
9047ebbc
MV
1359int merge_recursive_config(const char *var, const char *value, void *cb)
1360{
1361 if (!strcasecmp(var, "merge.verbosity")) {
1362 merge_recursive_verbosity = git_config_int(var, value);
1363 return 0;
1364 }
1365 if (!strcasecmp(var, "diff.renamelimit")) {
1366 diff_rename_limit = git_config_int(var, value);
1367 return 0;
1368 }
1369 if (!strcasecmp(var, "merge.renamelimit")) {
1370 merge_rename_limit = git_config_int(var, value);
1371 return 0;
1372 }
1373 return git_default_config(var, value, cb);
1374}
1375
1376void merge_recursive_setup(int is_subtree_merge)
1377{
1378 if (getenv("GIT_MERGE_VERBOSITY"))
1379 merge_recursive_verbosity =
1380 strtol(getenv("GIT_MERGE_VERBOSITY"), NULL, 10);
1381 if (merge_recursive_verbosity >= 5)
1382 buffer_output = 0;
1383 subtree_merge = is_subtree_merge;
1384}