2 * Recursive Merge algorithm stolen from git-merge-recursive.py by
4 * The thieves were Alex Riesen and Johannes Schindelin, in June/July 2006
10 #include <sys/types.h>
14 #include "cache-tree.h"
17 #include "tree-walk.h"
20 #include "run-command.h"
23 #include "path-list.h"
28 #define debug(args, ...) fprintf(stderr, args, ## __VA_ARGS__)
30 #define debug(args, ...)
35 static void show_ce_entry(const char *tag, struct cache_entry *ce)
38 (ce->ce_flags & htons(CE_VALID))) {
39 static char alttag[4];
40 memcpy(alttag, tag, 3);
42 alttag[0] = tolower(tag[0]);
43 else if (tag[0] == '?')
54 fprintf(stderr,"%s%06o %s %d\t",
57 sha1_to_hex(ce->sha1),
59 write_name_quoted("", 0, ce->name,
64 static void ls_files() {
66 for (i = 0; i < active_nr; i++) {
67 struct cache_entry *ce = active_cache[i];
68 show_ce_entry("", ce);
70 fprintf(stderr, "---\n");
75 * A virtual commit has
76 * - (const char *)commit->util set to the name, and
77 * - *(int *)commit->object.sha1 set to the virtual id.
79 static const char *commit_title(struct commit *commit, int *len)
81 const char *s = "(null commit)";
88 if ( parse_commit(commit) != 0 ) {
95 if ( '\n' == prev && '\n' == *s ) {
102 while ( s[*len] && '\n' != s[*len] )
109 static const char *commit_hex_sha1(const struct commit *commit)
111 return commit->util ? "virtual" : commit ?
112 sha1_to_hex(commit->object.sha1) : "undefined";
115 static unsigned commit_list_count(const struct commit_list *l)
118 for (; l; l = l->next )
123 static struct commit *make_virtual_commit(struct tree *tree, const char *comment)
125 struct commit *commit = xcalloc(1, sizeof(struct commit));
126 static unsigned virtual_id = 1;
128 commit->util = (void*)comment;
129 *(int*)commit->object.sha1 = virtual_id++;
134 * TODO: we should not have to copy the SHA1s around, but rather reference
135 * them. That way, sha_eq() is just sha1 == sha2.
137 static int sha_eq(const unsigned char *a, const unsigned char *b)
141 return a && b && memcmp(a, b, 20) == 0;
144 static void memswp(void *p1, void *p2, unsigned n)
146 unsigned char *a = p1, *b = p2;
157 * TODO: we should convert the merge_result users to
158 * int blabla(..., struct commit **result)
159 * like everywhere else in git.
160 * Same goes for merge_tree_result and merge_file_info.
164 struct commit *commit;
168 struct merge_tree_result
175 * TODO: check if we can just reuse the active_cache structure: it is already
176 * sorted (by name, stage).
177 * Only problem: do not write it when flushing the cache.
184 unsigned char sha[20];
186 unsigned processed:1;
189 static struct path_list currentFileSet = {NULL, 0, 0, 1};
190 static struct path_list currentDirectorySet = {NULL, 0, 0, 1};
192 static int output_indent = 0;
194 static void output(const char *fmt, ...)
198 for ( i = output_indent; i--; )
201 vfprintf(stdout, fmt, args);
206 static const char *original_index_file;
207 static const char *temporary_index_file;
208 static int cache_dirty = 0;
210 static int flush_cache()
212 /* flush temporary index */
213 struct lock_file *lock = xcalloc(1, sizeof(struct lock_file));
214 int fd = hold_lock_file_for_update(lock, getenv("GIT_INDEX_FILE"));
216 die("could not lock %s", temporary_index_file);
217 if (write_cache(fd, active_cache, active_nr) ||
218 close(fd) || commit_lock_file(lock))
219 die ("unable to write %s", getenv("GIT_INDEX_FILE"));
225 static void setup_index(int temp)
227 const char *idx = temp ? temporary_index_file: original_index_file;
229 die("fatal: cache changed flush_cache();");
230 unlink(temporary_index_file);
231 setenv("GIT_INDEX_FILE", idx, 1);
235 static struct cache_entry *make_cache_entry(unsigned int mode,
236 const unsigned char *sha1, const char *path, int stage, int refresh)
239 struct cache_entry *ce;
241 if (!verify_path(path))
245 size = cache_entry_size(len);
246 ce = xcalloc(1, size);
248 memcpy(ce->sha1, sha1, 20);
249 memcpy(ce->name, path, len);
250 ce->ce_flags = create_ce_flags(len, stage);
251 ce->ce_mode = create_ce_mode(mode);
254 return refresh_cache_entry(ce, 0);
259 static int add_cacheinfo(unsigned int mode, const unsigned char *sha1,
260 const char *path, int stage, int refresh, int options)
262 struct cache_entry *ce;
264 read_cache_from(getenv("GIT_INDEX_FILE"));
266 ce = make_cache_entry(mode, sha1 ? sha1 : null_sha1, path, stage, refresh);
268 return error("cache_addinfo failed: %s", strerror(cache_errno));
269 return add_cache_entry(ce, options);
273 * This is a global variable which is used in a number of places but
274 * only written to in the 'merge' function.
276 * index_only == 1 => Don't leave any non-stage 0 entries in the cache and
277 * don't update the working directory.
278 * 0 => Leave unmerged entries in the cache and update
279 * the working directory.
281 static int index_only = 0;
284 * TODO: this can be streamlined by refactoring builtin-read-tree.c
286 static int git_read_tree(const struct tree *tree)
289 fprintf(stderr, "GIT_INDEX_FILE='%s' git-read-tree %s\n",
290 getenv("GIT_INDEX_FILE"),
291 sha1_to_hex(tree->object.sha1));
293 const char *argv[] = { "git-read-tree", NULL, NULL, };
295 die("read-tree with dirty cache");
296 argv[1] = sha1_to_hex(tree->object.sha1);
297 int rc = run_command_v(2, argv);
298 return rc < 0 ? -1: rc;
302 * TODO: this can be streamlined by refactoring builtin-read-tree.c
304 static int git_merge_trees(const char *update_arg,
310 fprintf(stderr, "GIT_INDEX_FILE='%s' git-read-tree %s -m %s %s %s\n",
311 getenv("GIT_INDEX_FILE"),
313 sha1_to_hex(common->object.sha1),
314 sha1_to_hex(head->object.sha1),
315 sha1_to_hex(merge->object.sha1));
317 const char *argv[] = {
318 "git-read-tree", NULL, "-m", NULL, NULL, NULL,
323 argv[1] = update_arg;
324 argv[3] = sha1_to_hex(common->object.sha1);
325 argv[4] = sha1_to_hex(head->object.sha1);
326 argv[5] = sha1_to_hex(merge->object.sha1);
327 int rc = run_command_v(6, argv);
328 return rc < 0 ? -1: rc;
332 * TODO: this can be streamlined by refactoring builtin-write-tree.c
334 static struct tree *git_write_tree()
337 fprintf(stderr, "GIT_INDEX_FILE='%s' git-write-tree\n",
338 getenv("GIT_INDEX_FILE"));
342 FILE *fp = popen("git-write-tree 2>/dev/null", "r");
344 unsigned char sha1[20];
347 while ( (ch = fgetc(fp)) != EOF )
348 if ( i < sizeof(buf)-1 && ch >= '0' && ch <= 'f' )
353 if ( rc == -1 || WEXITSTATUS(rc) )
356 if ( get_sha1(buf, sha1) != 0 )
358 return lookup_tree(sha1);
362 * TODO: get rid of files_and_dirs; we do not use it except for
363 * current_file_set and current_dir_set, which are global already.
367 struct path_list *files;
368 struct path_list *dirs;
371 static int save_files_dirs(const unsigned char *sha1,
372 const char *base, int baselen, const char *path,
373 unsigned int mode, int stage)
375 int len = strlen(path);
376 char *newpath = malloc(baselen + len + 1);
377 memcpy(newpath, base, baselen);
378 memcpy(newpath + baselen, path, len);
379 newpath[baselen + len] = '\0';
382 path_list_insert(newpath, files_and_dirs.dirs);
384 path_list_insert(newpath, files_and_dirs.files);
387 return READ_TREE_RECURSIVE;
390 static int get_files_dirs(struct tree *tree,
391 struct path_list *files,
392 struct path_list *dirs)
395 files_and_dirs.files = files;
396 files_and_dirs.dirs = dirs;
397 debug("get_files_dirs ...\n");
398 if (read_tree_recursive(tree, "", 0, 0, NULL, save_files_dirs) != 0) {
399 debug(" get_files_dirs done (0)\n");
402 n = files->nr + dirs->nr;
403 debug(" get_files_dirs done (%d)\n", n);
408 * TODO: this wrapper is so small, we can use path_list_lookup directly.
409 * Same goes for index_entry_get(), free_index_entries(), find_rename_bysrc(),
410 * free_rename_entries().
412 static struct stage_data *index_entry_find(struct path_list *ents,
415 struct path_list_item *item = path_list_lookup(path, ents);
421 static struct stage_data *index_entry_get(struct path_list *ents,
424 struct path_list_item *item = path_list_lookup(path, ents);
427 item = path_list_insert(path, ents);
428 item->util = xcalloc(1, sizeof(struct stage_data));
434 * TODO: since the result of index_entry_from_db() is tucked into a
435 * path_list anyway, this helper can do that already.
438 * Returns a index_entry instance which doesn't have to correspond to
439 * a real cache entry in Git's index.
441 static struct stage_data *index_entry_from_db(const char *path,
446 struct stage_data *e = xcalloc(1, sizeof(struct stage_data));
447 get_tree_entry(o->object.sha1, path,
448 e->stages[1].sha, &e->stages[1].mode);
449 get_tree_entry(a->object.sha1, path,
450 e->stages[2].sha, &e->stages[2].mode);
451 get_tree_entry(b->object.sha1, path,
452 e->stages[3].sha, &e->stages[3].mode);
456 static void free_index_entries(struct path_list **ents)
461 path_list_clear(*ents, 1);
467 * Create a dictionary mapping file names to CacheEntry objects. The
468 * dictionary contains one entry for every path with a non-zero stage entry.
470 static struct path_list *get_unmerged()
472 struct path_list *unmerged = xcalloc(1, sizeof(struct path_list));
475 unmerged->strdup_paths = 1;
477 read_cache_from(getenv("GIT_INDEX_FILE"));
480 for (i = 0; i < active_nr; i++) {
481 struct cache_entry *ce = active_cache[i];
485 struct stage_data *e = index_entry_get(unmerged, ce->name);
486 e->stages[ce_stage(ce)].mode = ntohl(ce->ce_mode);
487 memcpy(e->stages[ce_stage(ce)].sha, ce->sha1, 20);
490 debug(" get_unmerged done\n");
496 struct diff_filepair *pair;
497 struct stage_data *src_entry;
498 struct stage_data *dst_entry;
499 unsigned processed:1;
502 static struct rename *find_rename_bysrc(struct path_list *e,
505 struct path_list_item *item = path_list_lookup(name, e);
511 static void free_rename_entries(struct path_list **list)
516 path_list_clear(*list, 0);
522 * Get information of all renames which occured between 'oTree' and
523 * 'tree'. We need the three trees in the merge ('oTree', 'aTree' and
524 * 'bTree') to be able to associate the correct cache entries with
525 * the rename information. 'tree' is always equal to either aTree or bTree.
527 static struct path_list *get_renames(struct tree *tree,
531 struct path_list *entries)
535 debug("getRenames ...\n");
538 struct path_list *renames = xcalloc(1, sizeof(struct path_list));
539 struct diff_options opts;
542 opts.detect_rename = DIFF_DETECT_RENAME;
543 opts.output_format = DIFF_FORMAT_NO_OUTPUT;
544 if (diff_setup_done(&opts) < 0)
545 die("diff setup failed");
546 diff_tree_sha1(oTree->object.sha1, tree->object.sha1, "", &opts);
548 for (i = 0; i < diff_queued_diff.nr; ++i) {
550 struct diff_filepair *pair = diff_queued_diff.queue[i];
551 if (pair->status != 'R') {
552 diff_free_filepair(pair);
555 re = xmalloc(sizeof(*re));
558 re->src_entry = index_entry_find(entries, re->pair->one->path);
559 /* TODO: should it not be an error, if src_entry was found? */
560 if ( !re->src_entry ) {
561 re->src_entry = index_entry_from_db(re->pair->one->path,
562 oTree, aTree, bTree);
563 struct path_list_item *item =
564 path_list_insert(re->pair->one->path, entries);
565 item->util = re->src_entry;
567 re->dst_entry = index_entry_find(entries, re->pair->two->path);
568 if ( !re->dst_entry ) {
569 re->dst_entry = index_entry_from_db(re->pair->two->path,
570 oTree, aTree, bTree);
571 struct path_list_item *item =
572 path_list_insert(re->pair->two->path, entries);
573 item->util = re->dst_entry;
575 struct path_list_item *item = path_list_insert(pair->one->path, renames);
578 opts.output_format = DIFF_FORMAT_NO_OUTPUT;
579 diff_queued_diff.nr = 0;
581 debug(" getRenames done in %ld\n", time(0)-t);
586 * TODO: the code would be way nicer, if we had a struct containing just sha1 and mode.
587 * In this particular case, we might get away reusing stage_data, no?
589 int update_stages(const char *path,
590 unsigned char *osha, unsigned omode,
591 unsigned char *asha, unsigned amode,
592 unsigned char *bsha, unsigned bmode,
593 int clear /* =True */)
595 int options = ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE;
597 if (add_cacheinfo(0, null_sha1, path, 0, 0, options))
600 if (add_cacheinfo(omode, osha, path, 1, 0, options))
603 if (add_cacheinfo(omode, osha, path, 2, 0, options))
606 if (add_cacheinfo(omode, osha, path, 3, 0, options))
612 * TODO: there has to be a function in libgit doing this exact thing.
614 static int remove_path(const char *name)
622 int len = strlen(name);
623 char *dirs = malloc(len+1);
624 memcpy(dirs, name, len);
626 while ( (slash = strrchr(name, '/')) ) {
629 if ( rmdir(name) != 0 )
636 /* General TODO: unC99ify the code: no declaration after code */
637 /* General TODO: no javaIfiCation: rename updateCache to update_cache */
639 * TODO: once we no longer call external programs, we'd probably be better of
640 * not setting / getting the environment variable GIT_INDEX_FILE all the time.
642 int remove_file(int clean, const char *path)
644 int updateCache = index_only || clean;
645 int updateWd = !index_only;
649 read_cache_from(getenv("GIT_INDEX_FILE"));
651 if (remove_file_from_cache(path))
657 if ( errno != ENOENT || errno != EISDIR )
664 static char *unique_path(const char *path, const char *branch)
666 char *newpath = xmalloc(strlen(path) + 1 + strlen(branch) + 8 + 1);
667 strcpy(newpath, path);
668 strcat(newpath, "~");
669 char *p = newpath + strlen(newpath);
676 while ( path_list_has_path(¤tFileSet, newpath) ||
677 path_list_has_path(¤tDirectorySet, newpath) ||
678 lstat(newpath, &st) == 0 ) {
679 sprintf(p, "_%d", suffix++);
681 path_list_insert(newpath, ¤tFileSet);
686 * TODO: except for create_last, this so looks like
687 * safe_create_leading_directories().
689 static int mkdir_p(const char *path, unsigned long mode, int create_last)
691 char *buf = strdup(path);
694 for ( p = buf; *p; ++p ) {
698 if (mkdir(buf, mode)) {
702 if ( !stat(buf, &st) && S_ISDIR(st.st_mode) )
713 if ( create_last && mkdir(path, mode) )
718 static void flush_buffer(int fd, const char *buf, unsigned long size)
721 long ret = xwrite(fd, buf, size);
726 die("merge-recursive: %s", strerror(errno));
728 die("merge-recursive: disk full?");
735 /* General TODO: reindent according to guide lines (no if ( blabla )) */
736 void update_file_flags(const unsigned char *sha,
750 buf = read_sha1_file(sha, type, &size);
752 die("cannot read object %s '%s'", sha1_to_hex(sha), path);
753 if ( strcmp(type, blob_type) != 0 )
754 die("blob expected for %s '%s'", sha1_to_hex(sha), path);
756 if ( S_ISREG(mode) ) {
757 if ( mkdir_p(path, 0777, 0 /* don't create last element */) )
758 die("failed to create path %s: %s", path, strerror(errno));
764 int fd = open(path, O_WRONLY | O_TRUNC | O_CREAT, mode);
766 die("failed to open %s: %s", path, strerror(errno));
767 flush_buffer(fd, buf, size);
769 } else if ( S_ISLNK(mode) ) {
770 char *linkTarget = malloc(size + 1);
771 memcpy(linkTarget, buf, size);
772 linkTarget[size] = '\0';
773 mkdir_p(path, 0777, 0);
774 symlink(linkTarget, path);
776 die("do not know what to do with %06o %s '%s'",
777 mode, sha1_to_hex(sha), path);
780 add_cacheinfo(mode, sha, path, 0, updateWd, ADD_CACHE_OK_TO_ADD);
783 /* TODO: is this often used? if not, do direct call */
784 void update_file(int clean,
785 const unsigned char *sha,
789 update_file_flags(sha, mode, path, index_only || clean, !index_only);
792 /* Low level file merging, update and removal */
794 struct merge_file_info
796 unsigned char sha[20];
802 static char *git_unpack_file(const unsigned char *sha1, char *path)
809 buf = read_sha1_file(sha1, type, &size);
810 if (!buf || strcmp(type, blob_type))
811 die("unable to read blob object %s", sha1_to_hex(sha1));
813 strcpy(path, ".merge_file_XXXXXX");
816 die("unable to create temp-file");
817 flush_buffer(fd, buf, size);
823 * TODO: the signature would be much more efficient using stage_data
825 static struct merge_file_info merge_file(const char *oPath,
826 const unsigned char *oSha,
829 const unsigned char *aSha,
832 const unsigned char *bSha,
834 const char *branch1Name,
835 const char *branch2Name)
837 struct merge_file_info result;
841 if ( (S_IFMT & aMode) != (S_IFMT & bMode) ) {
843 if ( S_ISREG(aMode) ) {
845 memcpy(result.sha, aSha, 20);
848 memcpy(result.sha, bSha, 20);
851 if ( memcmp(aSha, oSha, 20) != 0 && memcmp(bSha, oSha, 20) != 0 )
854 result.mode = aMode == oMode ? bMode: aMode;
856 if ( memcmp(aSha, oSha, 20) == 0 )
857 memcpy(result.sha, bSha, 20);
858 else if ( memcmp(bSha, oSha, 20) == 0 )
859 memcpy(result.sha, aSha, 20);
860 else if ( S_ISREG(aMode) ) {
867 git_unpack_file(oSha, orig);
868 git_unpack_file(aSha, src1);
869 git_unpack_file(bSha, src2);
871 const char *argv[] = {
872 "merge", "-L", NULL, "-L", NULL, "-L", NULL,
877 argv[2] = la = strdup(mkpath("%s/%s", branch1Name, aPath));
878 argv[6] = lb = strdup(mkpath("%s/%s", branch2Name, bPath));
879 argv[4] = lo = strdup(mkpath("orig/%s", oPath));
882 printf("%s %s %s %s %s %s %s %s %s %s\n",
883 argv[0], argv[1], argv[2], argv[3], argv[4],
884 argv[5], argv[6], argv[7], argv[8], argv[9]);
886 code = run_command_v(10, argv);
891 if ( code && code < -256 ) {
892 die("Failed to execute 'merge'. merge(1) is used as the "
893 "file-level merge tool. Is 'merge' in your path?");
896 int fd = open(src1, O_RDONLY);
897 if (fd < 0 || fstat(fd, &st) < 0 ||
898 index_fd(result.sha, fd, &st, 1,
900 die("Unable to add %s to database", src1);
907 result.clean = WEXITSTATUS(code) == 0;
909 if ( !(S_ISLNK(aMode) || S_ISLNK(bMode)) )
910 die("cannot merge modes?");
912 memcpy(result.sha, aSha, 20);
914 if ( memcmp(aSha, bSha, 20) != 0 )
922 static void conflict_rename_rename(struct rename *ren1,
929 const char *ren1_dst = ren1->pair->two->path;
930 const char *ren2_dst = ren2->pair->two->path;
931 const char *dstName1 = ren1_dst;
932 const char *dstName2 = ren2_dst;
933 if (path_list_has_path(¤tDirectorySet, ren1_dst)) {
934 dstName1 = del[delp++] = unique_path(ren1_dst, branch1);
935 output("%s is a directory in %s adding as %s instead",
936 ren1_dst, branch2, dstName1);
937 remove_file(0, ren1_dst);
939 if (path_list_has_path(¤tDirectorySet, ren2_dst)) {
940 dstName2 = del[delp++] = unique_path(ren2_dst, branch2);
941 output("%s is a directory in %s adding as %s instead",
942 ren2_dst, branch1, dstName2);
943 remove_file(0, ren2_dst);
945 update_stages(dstName1,
947 ren1->pair->two->sha1, ren1->pair->two->mode,
950 update_stages(dstName2,
953 ren2->pair->two->sha1, ren2->pair->two->mode,
959 static void conflict_rename_dir(struct rename *ren1,
962 char *newPath = unique_path(ren1->pair->two->path, branch1);
963 output("Renaming %s to %s instead", ren1->pair->one->path, newPath);
964 remove_file(0, ren1->pair->two->path);
965 update_file(0, ren1->pair->two->sha1, ren1->pair->two->mode, newPath);
969 static void conflict_rename_rename_2(struct rename *ren1,
974 char *newPath1 = unique_path(ren1->pair->two->path, branch1);
975 char *newPath2 = unique_path(ren2->pair->two->path, branch2);
976 output("Renaming %s to %s and %s to %s instead",
977 ren1->pair->one->path, newPath1,
978 ren2->pair->one->path, newPath2);
979 remove_file(0, ren1->pair->two->path);
980 update_file(0, ren1->pair->two->sha1, ren1->pair->two->mode, newPath1);
981 update_file(0, ren2->pair->two->sha1, ren2->pair->two->mode, newPath2);
986 /* General TODO: get rid of all the debug messages */
987 static int process_renames(struct path_list *renamesA,
988 struct path_list *renamesB,
989 const char *branchNameA,
990 const char *branchNameB)
992 int cleanMerge = 1, i;
993 struct path_list srcNames = {NULL, 0, 0, 0}, byDstA = {NULL, 0, 0, 0}, byDstB = {NULL, 0, 0, 0};
994 const struct rename *sre;
997 * TODO: think about a saner way to do this.
998 * Since both renamesA and renamesB are sorted, it should
999 * be much more efficient to traverse both simultaneously,
1000 * only byDstA and byDstB should be needed.
1002 debug("processRenames...\n");
1003 for (i = 0; i < renamesA->nr; i++) {
1004 sre = renamesA->items[i].util;
1005 path_list_insert(sre->pair->one->path, &srcNames);
1006 path_list_insert(sre->pair->two->path, &byDstA)->util
1009 for (i = 0; i < renamesB->nr; i++) {
1010 sre = renamesB->items[i].util;
1011 path_list_insert(sre->pair->one->path, &srcNames);
1012 path_list_insert(sre->pair->two->path, &byDstB)->util
1016 for (i = 0; i < srcNames.nr; i++) {
1017 char *src = srcNames.items[i].path;
1018 struct path_list *renames1, *renames2, *renames2Dst;
1019 struct rename *ren1, *ren2;
1020 const char *branchName1, *branchName2;
1021 ren1 = find_rename_bysrc(renamesA, src);
1022 ren2 = find_rename_bysrc(renamesB, src);
1023 /* TODO: refactor, so that 1/2 are not needed */
1025 renames1 = renamesA;
1026 renames2 = renamesB;
1027 renames2Dst = &byDstB;
1028 branchName1 = branchNameA;
1029 branchName2 = branchNameB;
1031 renames1 = renamesB;
1032 renames2 = renamesA;
1033 renames2Dst = &byDstA;
1034 branchName1 = branchNameB;
1035 branchName2 = branchNameA;
1036 struct rename *tmp = ren2;
1041 ren1->dst_entry->processed = 1;
1042 ren1->src_entry->processed = 1;
1044 if ( ren1->processed )
1046 ren1->processed = 1;
1048 const char *ren1_src = ren1->pair->one->path;
1049 const char *ren1_dst = ren1->pair->two->path;
1052 const char *ren2_src = ren2->pair->one->path;
1053 const char *ren2_dst = ren2->pair->two->path;
1054 /* Renamed in 1 and renamed in 2 */
1055 if (strcmp(ren1_src, ren2_src) != 0)
1056 die("ren1.src != ren2.src");
1057 ren2->dst_entry->processed = 1;
1058 ren2->processed = 1;
1059 if (strcmp(ren1_dst, ren2_dst) != 0) {
1061 output("CONFLICT (rename/rename): "
1062 "Rename %s->%s in branch %s "
1063 "rename %s->%s in %s",
1064 src, ren1_dst, branchName1,
1065 src, ren2_dst, branchName2);
1066 conflict_rename_rename(ren1, branchName1, ren2, branchName2);
1068 remove_file(1, ren1_src);
1069 struct merge_file_info mfi;
1070 mfi = merge_file(ren1_src,
1071 ren1->pair->one->sha1,
1072 ren1->pair->one->mode,
1074 ren1->pair->two->sha1,
1075 ren1->pair->two->mode,
1077 ren2->pair->two->sha1,
1078 ren2->pair->two->mode,
1081 if ( mfi.merge || !mfi.clean )
1082 output("Renaming %s->%s", src, ren1_dst);
1085 output("Auto-merging %s", ren1_dst);
1088 output("CONFLICT (content): merge conflict in %s",
1093 update_stages(ren1_dst,
1094 ren1->pair->one->sha1,
1095 ren1->pair->one->mode,
1096 ren1->pair->two->sha1,
1097 ren1->pair->two->mode,
1098 ren2->pair->two->sha1,
1099 ren2->pair->two->mode,
1102 update_file(mfi.clean, mfi.sha, mfi.mode, ren1_dst);
1105 /* Renamed in 1, maybe changed in 2 */
1106 remove_file(1, ren1_src);
1108 unsigned char srcShaOtherBranch[20], dstShaOtherBranch[20];
1109 unsigned srcModeOtherBranch, dstModeOtherBranch;
1111 int stage = renamesA == renames1 ? 3: 2;
1113 memcpy(srcShaOtherBranch, ren1->src_entry->stages[stage].sha, 20);
1114 srcModeOtherBranch = ren1->src_entry->stages[stage].mode;
1116 memcpy(dstShaOtherBranch, ren1->dst_entry->stages[stage].sha, 20);
1117 dstModeOtherBranch = ren1->dst_entry->stages[stage].mode;
1122 if (path_list_has_path(¤tDirectorySet, ren1_dst)) {
1124 output("CONFLICT (rename/directory): Rename %s->%s in %s "
1125 " directory %s added in %s",
1126 ren1_src, ren1_dst, branchName1,
1127 ren1_dst, branchName2);
1128 conflict_rename_dir(ren1, branchName1);
1129 } else if ( memcmp(srcShaOtherBranch, null_sha1, 20) == 0 ) {
1131 output("CONFLICT (rename/delete): Rename %s->%s in %s "
1132 "and deleted in %s",
1133 ren1_src, ren1_dst, branchName1,
1135 update_file(0, ren1->pair->two->sha1, ren1->pair->two->mode, ren1_dst);
1136 } else if ( memcmp(dstShaOtherBranch, null_sha1, 20) != 0 ) {
1139 output("CONFLICT (rename/add): Rename %s->%s in %s. "
1141 ren1_src, ren1_dst, branchName1,
1142 ren1_dst, branchName2);
1143 newPath = unique_path(ren1_dst, branchName2);
1144 output("Adding as %s instead", newPath);
1145 update_file(0, dstShaOtherBranch, dstModeOtherBranch, newPath);
1146 } else if ( (ren2 = find_rename_bysrc(renames2Dst, ren1_dst)) ) {
1148 ren2->processed = 1;
1149 output("CONFLICT (rename/rename): Rename %s->%s in %s. "
1150 "Rename %s->%s in %s",
1151 ren1_src, ren1_dst, branchName1,
1152 ren2->pair->one->path, ren2->pair->two->path, branchName2);
1153 conflict_rename_rename_2(ren1, branchName1, ren2, branchName2);
1158 const char *oname = ren1_src;
1159 const char *aname = ren1_dst;
1160 const char *bname = ren1_src;
1161 unsigned char osha[20], asha[20], bsha[20];
1162 unsigned omode = ren1->pair->one->mode;
1163 unsigned amode = ren1->pair->two->mode;
1164 unsigned bmode = srcModeOtherBranch;
1165 memcpy(osha, ren1->pair->one->sha1, 20);
1166 memcpy(asha, ren1->pair->two->sha1, 20);
1167 memcpy(bsha, srcShaOtherBranch, 20);
1168 const char *aBranch = branchName1;
1169 const char *bBranch = branchName2;
1171 if ( renamesA != renames1 ) {
1172 memswp(&aname, &bname, sizeof(aname));
1173 memswp(asha, bsha, 20);
1174 memswp(&aBranch, &bBranch, sizeof(aBranch));
1176 struct merge_file_info mfi;
1177 mfi = merge_file(oname, osha, omode,
1182 if ( mfi.merge || !mfi.clean )
1183 output("Renaming %s => %s", ren1_src, ren1_dst);
1185 output("Auto-merging %s", ren1_dst);
1187 output("CONFLICT (rename/modify): Merge conflict in %s",
1192 update_stages(ren1_dst,
1198 update_file(mfi.clean, mfi.sha, mfi.mode, ren1_dst);
1202 path_list_clear(&srcNames, 0);
1203 debug(" processRenames done\n");
1210 static unsigned char *has_sha(const unsigned char *sha)
1212 return memcmp(sha, null_sha1, 20) == 0 ? NULL: (unsigned char *)sha;
1215 /* Per entry merge function */
1216 static int process_entry(const char *path, struct stage_data *entry,
1217 const char *branch1Name,
1218 const char *branch2Name)
1221 printf("processing entry, clean cache: %s\n", index_only ? "yes": "no");
1222 print_index_entry("\tpath: ", entry);
1225 unsigned char *oSha = has_sha(entry->stages[1].sha);
1226 unsigned char *aSha = has_sha(entry->stages[2].sha);
1227 unsigned char *bSha = has_sha(entry->stages[3].sha);
1228 unsigned oMode = entry->stages[1].mode;
1229 unsigned aMode = entry->stages[2].mode;
1230 unsigned bMode = entry->stages[3].mode;
1232 if ( oSha && (!aSha || !bSha) ) {
1233 /* Case A: Deleted in one */
1234 if ( (!aSha && !bSha) ||
1235 (sha_eq(aSha, oSha) && !bSha) ||
1236 (!aSha && sha_eq(bSha, oSha)) ) {
1237 /* Deleted in both or deleted in one and
1238 * unchanged in the other */
1240 output("Removing %s", path);
1241 remove_file(1, path);
1243 /* Deleted in one and changed in the other */
1246 output("CONFLICT (delete/modify): %s deleted in %s "
1247 "and modified in %s. Version %s of %s left in tree.",
1249 branch2Name, branch2Name, path);
1250 update_file(0, bSha, bMode, path);
1252 output("CONFLICT (delete/modify): %s deleted in %s "
1253 "and modified in %s. Version %s of %s left in tree.",
1255 branch1Name, branch1Name, path);
1256 update_file(0, aSha, aMode, path);
1260 } else if ( (!oSha && aSha && !bSha) ||
1261 (!oSha && !aSha && bSha) ) {
1262 /* Case B: Added in one. */
1263 const char *addBranch;
1264 const char *otherBranch;
1266 const unsigned char *sha;
1270 addBranch = branch1Name;
1271 otherBranch = branch2Name;
1274 conf = "file/directory";
1276 addBranch = branch2Name;
1277 otherBranch = branch1Name;
1280 conf = "directory/file";
1282 if ( path_list_has_path(¤tDirectorySet, path) ) {
1284 const char *newPath = unique_path(path, addBranch);
1285 output("CONFLICT (%s): There is a directory with name %s in %s. "
1287 conf, path, otherBranch, path, newPath);
1288 remove_file(0, path);
1289 update_file(0, sha, mode, newPath);
1291 output("Adding %s", path);
1292 update_file(1, sha, mode, path);
1294 } else if ( !oSha && aSha && bSha ) {
1295 /* Case C: Added in both (check for same permissions). */
1296 if ( sha_eq(aSha, bSha) ) {
1297 if ( aMode != bMode ) {
1299 output("CONFLICT: File %s added identically in both branches, "
1300 "but permissions conflict %06o->%06o",
1301 path, aMode, bMode);
1302 output("CONFLICT: adding with permission: %06o", aMode);
1303 update_file(0, aSha, aMode, path);
1305 /* This case is handled by git-read-tree */
1306 assert(0 && "This case must be handled by git-read-tree");
1310 const char *newPath1 = unique_path(path, branch1Name);
1311 const char *newPath2 = unique_path(path, branch2Name);
1312 output("CONFLICT (add/add): File %s added non-identically "
1313 "in both branches. Adding as %s and %s instead.",
1314 path, newPath1, newPath2);
1315 remove_file(0, path);
1316 update_file(0, aSha, aMode, newPath1);
1317 update_file(0, bSha, bMode, newPath2);
1320 } else if ( oSha && aSha && bSha ) {
1321 /* case D: Modified in both, but differently. */
1322 output("Auto-merging %s", path);
1323 struct merge_file_info mfi;
1324 mfi = merge_file(path, oSha, oMode,
1327 branch1Name, branch2Name);
1330 update_file(1, mfi.sha, mfi.mode, path);
1333 output("CONFLICT (content): Merge conflict in %s", path);
1336 update_file(0, mfi.sha, mfi.mode, path);
1338 update_file_flags(mfi.sha, mfi.mode, path,
1339 0 /* updateCache */, 1 /* updateWd */);
1342 die("Fatal merge failure, shouldn't happen.");
1350 static struct merge_tree_result merge_trees(struct tree *head,
1352 struct tree *common,
1353 const char *branch1Name,
1354 const char *branch2Name)
1357 struct merge_tree_result result = { NULL, 0 };
1358 if ( !memcmp(common->object.sha1, merge->object.sha1, 20) ) {
1359 output("Already uptodate!");
1365 debug("merge_trees ...\n");
1366 code = git_merge_trees(index_only ? "-i": "-u", common, head, merge);
1369 die("merging of trees %s and %s failed",
1370 sha1_to_hex(head->object.sha1),
1371 sha1_to_hex(merge->object.sha1));
1373 result.tree = git_write_tree();
1375 if ( !result.tree ) {
1376 path_list_clear(¤tFileSet, 1);
1377 path_list_clear(¤tDirectorySet, 1);
1378 get_files_dirs(head, ¤tFileSet, ¤tDirectorySet);
1379 get_files_dirs(merge, ¤tFileSet, ¤tDirectorySet);
1381 struct path_list *entries = get_unmerged();
1382 struct path_list *re_head, *re_merge;
1383 re_head = get_renames(head, common, head, merge, entries);
1384 re_merge = get_renames(merge, common, head, merge, entries);
1385 result.clean = process_renames(re_head, re_merge,
1386 branch1Name, branch2Name);
1387 debug("\tprocessing entries...\n");
1389 for (i = 0; i < entries->nr; i++) {
1390 const char *path = entries->items[i].path;
1391 struct stage_data *e = entries->items[i].util;
1394 if (!process_entry(path, e, branch1Name, branch2Name))
1398 free_rename_entries(&re_merge);
1399 free_rename_entries(&re_head);
1400 free_index_entries(&entries);
1402 if (result.clean || index_only)
1403 result.tree = git_write_tree();
1406 debug("\t processing entries done\n");
1409 printf("merging of trees %s and %s resulted in %s\n",
1410 sha1_to_hex(head->object.sha1),
1411 sha1_to_hex(merge->object.sha1),
1412 sha1_to_hex(result.tree->object.sha1));
1415 debug(" merge_trees done\n");
1420 * Merge the commits h1 and h2, return the resulting virtual
1421 * commit object and a flag indicating the cleaness of the merge.
1424 struct merge_result merge(struct commit *h1,
1426 const char *branch1Name,
1427 const char *branch2Name,
1428 int callDepth /* =0 */,
1429 struct commit *ancestor /* =None */)
1431 struct merge_result result = { NULL, 0 };
1434 struct commit_list *ca = NULL, *iter;
1435 struct commit *mergedCA;
1436 struct merge_tree_result mtr;
1439 msg = commit_title(h1, &msglen);
1440 /* TODO: refactor. we always show the sha1 with the title */
1441 output("%s %.*s", commit_hex_sha1(h1), msglen, msg);
1442 msg = commit_title(h2, &msglen);
1443 output("%s %.*s", commit_hex_sha1(h2), msglen, msg);
1446 commit_list_insert(ancestor, &ca);
1448 ca = get_merge_bases(h1, h2, 1);
1450 output("found %u common ancestor(s):", commit_list_count(ca));
1451 for (iter = ca; iter; iter = iter->next) {
1452 msg = commit_title(iter->item, &msglen);
1453 output("%s %.*s", commit_hex_sha1(iter->item), msglen, msg);
1456 mergedCA = pop_commit(&ca);
1458 /* TODO: what happens when merge with virtual commits fails? */
1459 for (iter = ca; iter; iter = iter->next) {
1460 output_indent = callDepth + 1;
1461 result = merge(mergedCA, iter->item,
1462 "Temporary merge branch 1",
1463 "Temporary merge branch 2",
1466 mergedCA = result.commit;
1467 output_indent = callDepth;
1470 die("merge returned no commit");
1473 if ( callDepth == 0 ) {
1478 git_read_tree(h1->tree);
1482 mtr = merge_trees(h1->tree, h2->tree,
1483 mergedCA->tree, branch1Name, branch2Name);
1485 if ( !ancestor && (mtr.clean || index_only) ) {
1486 result.commit = make_virtual_commit(mtr.tree, "merged tree");
1487 commit_list_insert(h1, &result.commit->parents);
1488 commit_list_insert(h2, &result.commit->parents->next);
1490 result.commit = NULL;
1492 result.clean = mtr.clean;
1496 static struct commit *get_ref(const char *ref)
1498 unsigned char sha1[20];
1499 struct object *object;
1501 if (get_sha1(ref, sha1))
1502 die("Could not resolve ref '%s'", ref);
1503 object = deref_tag(parse_object(sha1), ref, strlen(ref));
1504 if (object->type != OBJ_COMMIT)
1506 if (parse_commit((struct commit *)object))
1507 die("Could not parse commit '%s'", sha1_to_hex(object->sha1));
1508 return (struct commit *)object;
1511 int main(int argc, char *argv[])
1513 static const char *bases[2];
1514 static unsigned bases_count = 0;
1516 original_index_file = getenv("GIT_INDEX_FILE");
1518 if (!original_index_file)
1519 original_index_file = strdup(git_path("index"));
1521 temporary_index_file = strdup(git_path("mrg-rcrsv-tmp-idx"));
1524 die("Usage: %s <base>... -- <head> <remote> ...\n", argv[0]);
1527 for (i = 1; i < argc; ++i) {
1528 if (!strcmp(argv[i], "--"))
1530 if (bases_count < sizeof(bases)/sizeof(*bases))
1531 bases[bases_count++] = argv[i];
1533 if (argc - i != 3) /* "--" "<head>" "<remote>" */
1534 die("Not handling anything other than two heads merge.");
1536 const char *branch1, *branch2;
1538 branch1 = argv[++i];
1539 branch2 = argv[++i];
1540 printf("Merging %s with %s\n", branch1, branch2);
1542 struct merge_result result;
1543 struct commit *h1 = get_ref(branch1);
1544 struct commit *h2 = get_ref(branch2);
1546 if (bases_count == 1) {
1547 struct commit *ancestor = get_ref(bases[0]);
1548 result = merge(h1, h2, branch1, branch2, 0, ancestor);
1550 result = merge(h1, h2, branch1, branch2, 0, NULL);
1555 return result.clean ? 0: 1;