{"thread":{"id":"4714","subject":"[PATCH 1/4] merge-recursive in C","startedAt":"2006-06-30T00:27:21Z","lastAt":"2006-07-03T15:54:44Z","messageCount":3,"participants":["Alex Riesen","Timo Hirvonen","Johannes Schindelin"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"22863","messageId":"20060630002721.GA22618@steel.home","threadId":"4714","inReplyTo":null,"subject":"[PATCH 1/4] merge-recursive in C","fromName":"Alex Riesen","fromEmail":"fork0@t-online.de","sentAt":"2006-06-30T00:27:21Z","receivedAt":"2006-06-30T00:27:21Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"This is summary of all merge-recursive patches floating around rebased\noff current git (75dedd5a21246be03ae443e9fc6a9f75c6d2995b).\n\n---\nI think I have to start doing this properly sometime, so that\nincremental patches can be posted. So I just chose a compiling state\n(it still has that ctime/mtime bug), added some of recent work on top\nof it and branched it all off Junio's master.\n\nThe merge_bases patches from Dscho (\"refactor merge_bases()\" and \"move\nget_merge_bases() to core lib\") can be applied on top of last.\n\n Makefile          |    7 \n git-merge.sh      |    4 \n graph.c           |  256 ++++++++\n graph.h           |   80 +++\n merge-recursive.c | 1622 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n path-list.c       |  110 ++++\n path-list.h       |   32 +\n 7 files changed, 2108 insertions(+), 3 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex cde619c..660f09b 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -163,7 +163,8 @@ PROGRAMS = \\\n \tgit-upload-pack$X git-verify-pack$X \\\n \tgit-symbolic-ref$X \\\n \tgit-name-rev$X git-pack-redundant$X git-repo-config$X git-var$X \\\n-\tgit-describe$X git-merge-tree$X git-blame$X git-imap-send$X\n+\tgit-describe$X git-merge-tree$X git-blame$X git-imap-send$X \\\n+\tgit-merge-recur$X\n \n BUILT_INS = git-log$X git-whatchanged$X git-show$X git-update-ref$X \\\n \tgit-count-objects$X git-diff$X git-push$X git-mailsplit$X \\\n@@ -595,6 +596,10 @@ git-http-push$X: revision.o http.o http-\n \t$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $(filter %.o,$^) \\\n \t\t$(LIBS) $(CURL_LIBCURL) $(EXPAT_LIBEXPAT)\n \n+git-merge-recur$X: merge-recursive.o graph.o path-list.o $(LIB_FILE)\n+\t$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $(filter %.o,$^) \\\n+\t\t$(LIBS)\n+\n $(LIB_OBJS) $(BUILTIN_OBJS): $(LIB_H)\n $(patsubst git-%$X,%.o,$(PROGRAMS)): $(LIB_H) $(wildcard */*.h)\n $(DIFF_OBJS): diffcore.h\ndiff --git a/git-merge.sh b/git-merge.sh\nindex 24e3b50..3c3fed6 100755\n--- a/git-merge.sh\n+++ b/git-merge.sh\n@@ -9,7 +9,7 @@ USAGE='[-n] [--no-commit] [--squash] [-s\n LF='\n '\n \n-all_strategies='recursive octopus resolve stupid ours'\n+all_strategies='recur recursive octopus resolve stupid ours'\n default_twohead_strategies='recursive'\n default_octopus_strategies='octopus'\n no_trivial_merge_strategies='ours'\n@@ -17,7 +17,7 @@ use_strategies=\n \n index_merge=t\n if test \"@@NO_PYTHON@@\"; then\n-\tall_strategies='resolve octopus stupid ours'\n+\tall_strategies='recur resolve octopus stupid ours'\n \tdefault_twohead_strategies='resolve'\n fi\n \ndiff --git a/graph.c b/graph.c\nnew file mode 100644\nindex 0000000..1a28302\n--- /dev/null\n+++ b/graph.c\n@@ -0,0 +1,256 @@\n+#include <stdlib.h>\n+#include <string.h>\n+#include <sys/wait.h>\n+#include \"cache.h\"\n+#include \"commit.h\"\n+#include \"graph.h\"\n+\n+/* does not belong here */\n+struct tree *git_write_tree()\n+{\n+#if 0\n+\tfprintf(stderr, \"GIT_INDEX_FILE='%s' git-write-tree\\n\",\n+\t\tgetenv(\"GIT_INDEX_FILE\"));\n+#endif\n+\tFILE *fp = popen(\"git-write-tree 2>/dev/null\", \"r\");\n+\tchar buf[41];\n+\tunsigned char sha1[20];\n+\tint ch;\n+\tunsigned i = 0;\n+\twhile ( (ch = fgetc(fp)) != EOF )\n+\t\tif ( i < sizeof(buf)-1 && ch >= '0' && ch <= 'f' )\n+\t\t\tbuf[i++] = ch;\n+\t\telse\n+\t\t\tbreak;\n+\tint rc = pclose(fp);\n+\tif ( rc == -1 || WEXITSTATUS(rc) )\n+\t\treturn NULL;\n+\tbuf[i] = '\\0';\n+\tif ( get_sha1(buf, sha1) != 0 )\n+\t\treturn NULL;\n+\treturn lookup_tree(sha1);\n+}\n+\n+const char *node_title(struct node *node, int *len)\n+{\n+\tconst char *s = \"(null commit)\";\n+\t*len = strlen(s);\n+\n+\tif ( node->virtual ) {\n+\t\ts = node->comment;\n+\t\t*len = strlen(s);\n+\t} else if ( node->commit ) {\n+\t\tif ( parse_commit(node->commit) != 0 ) {\n+\t\t\ts = \"(bad commit)\";\n+\t\t\t*len = strlen(s);\n+\t\t} else {\n+\t\t\ts = node->commit->buffer;\n+\t\t\tchar prev = '\\0';\n+\t\t\twhile ( *s ) {\n+\t\t\t\tif ( '\\n' == prev && '\\n' == *s ) {\n+\t\t\t\t\t++s;\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n+\t\t\t\tprev = *s++;\n+\t\t\t}\n+\t\t\t*len = 0;\n+\t\t\twhile ( s[*len] && '\\n' != s[*len] )\n+\t\t\t\t++(*len);\n+\t\t}\n+\t}\n+\treturn s;\n+}\n+\n+const unsigned char *node_sha(const struct node *node)\n+{\n+\treturn node->commit->object.sha1;\n+}\n+\n+const char *node_hex_sha1(const struct node *node)\n+{\n+\treturn node->commit ?  sha1_to_hex(node->commit->object.sha1):\n+\t\tnode->virtual ? \"virtual\": \"undefined\";\n+}\n+\n+static int sha_eq(const unsigned char *a, const unsigned char *b)\n+{\n+\tif ( !a && !b )\n+\t\treturn 2;\n+\treturn a && b && memcmp(a, b, 20) == 0;\n+}\n+\n+static struct node_list *node_list_pool = NULL;\n+static unsigned node_list_pool_size = 0;\n+\n+unsigned node_list_count(const struct node_list *l)\n+{\n+\tunsigned c = 0;\n+\twhile ( l ) {\n+\t\t++c;\n+\t\tl = l->next;\n+\t}\n+\treturn c;\n+}\n+\n+struct node_list *node_list_insert(struct node *node, struct node_list **list)\n+{\n+\tstruct node_list *e;\n+\tif ( node_list_pool )\n+\t\te = node_list_shift(&node_list_pool);\n+\telse\n+\t\te = malloc(sizeof(struct node_list));\n+\te->next = *list;\n+\te->node = node;\n+\t*list = e;\n+\treturn e;\n+}\n+\n+struct node_list *node_list_free1(struct node_list *list, int free_nodes)\n+{\n+\tstruct node_list *next = list->next;\n+\tif ( free_nodes )\n+\t\tfree(list->node);\n+\n+\tif ( node_list_pool_size < 1000 ) {\n+\t\tlist->node = NULL;\n+\t\tlist->next = node_list_pool;\n+\t\tnode_list_pool = list;\n+\t} else\n+\t\tfree(list);\n+\treturn next;\n+}\n+\n+void node_list_free(struct node_list **list, int free_nodes)\n+{\n+\twhile ( *list )\n+\t\tnode_list_free1(node_list_shift(list), free_nodes);\n+}\n+\n+struct node *node_alloc(struct commit *commit)\n+{\n+\tstruct node *node = malloc(sizeof(struct node));\n+\tnode->parents = NULL;\n+\tnode->parents_count = 0;\n+\tnode->children = NULL;\n+\tnode->virtual = 0;\n+\tnode->commit = commit;\n+\tif ( parse_commit(commit) == 0 )\n+\t\tnode->tree = commit->tree;\n+\telse\n+\t\tdie(\"failed to parse commit %s\", sha1_to_hex(commit->object.sha1));\n+\n+\treturn node;\n+}\n+\n+struct node *node_alloc_virtual(struct tree *tree, const char *comment)\n+{\n+\tstruct node *node = malloc(sizeof(struct node));\n+\tnode->parents = NULL;\n+\tnode->children = NULL;\n+\tnode->commit = NULL;\n+\tnode->tree = tree;\n+\tnode->virtual = 1;\n+\tstatic unsigned virtual_id = 0;\n+\tnode->virtual_id = virtual_id++;\n+\tnode->comment = comment;\n+\treturn node;\n+}\n+\n+void node_set_parents(struct node *node, struct node_list *parents)\n+{\n+\tstruct node_list *p;\n+\tnode->parents_count = 0;\n+\tfor_each_node_list(p, node->parents = parents) {\n+\t\tnode_list_insert(node, &p->node->children);\n+\t\tnode->parents_count++;\n+\t}\n+}\n+\n+static inline int node_eq(const struct node *a, const struct node *b)\n+{\n+\tif ( a == b )\n+\t\treturn 1;\n+\tif ( a->virtual != b->virtual )\n+\t\treturn 0;\n+\tif ( a->virtual )\n+\t\treturn a->virtual_id == b->virtual_id;\n+\tif ( a->commit == b->commit )\n+\t\treturn 1;\n+\treturn sha_eq(a->commit->object.sha1, b->commit->object.sha1);\n+}\n+\n+struct node_list *node_list_find_node(const struct node *node,\n+\t\t\t\t      const struct node_list *list)\n+{\n+\tconst struct node_list *p;\n+\tfor_each_node_list(p, list)\n+\t\tif ( node_eq(p->node, node) )\n+\t\t\tbreak;\n+\treturn (struct node_list*)p;\n+}\n+\n+/*\n+ * a & b. a and are invalid after the call,\n+ * the result will contain all the common nodes\n+ */\n+struct node_list *node_list_intersect(struct node_list *a,\n+\t\t\t\t      struct node_list *b)\n+{\n+\tstruct node_list *result = NULL;\n+\tstruct node_list *p = a;\n+\twhile ( p ) {\n+\t\tstruct node_list *next = p->next;\n+\t\tstruct node_list *bn = node_list_find_node(p->node, b);\n+\t\tif ( bn ) {\n+\t\t\tp->next = result;\n+\t\t\tresult = p;\n+\t\t} else\n+\t\t\tnode_list_free1(p, 0);\n+\t\tp = next;\n+\t}\n+\tnode_list_free(&b, 0);\n+\treturn result;\n+}\n+\n+struct node *graph_add_node(struct graph *graph, struct node *node)\n+{\n+\tstruct node_list **bucket;\n+\tif ( node->virtual )\n+\t\t/* virtual nodes hashed by lowest byte of virtual_id */\n+\t\tbucket = graph->commits + (node->virtual_id & 0xff);\n+\telse\n+\t\tbucket = graph->commits + node->commit->object.sha1[0];\n+\tnode_list_insert(node, bucket);\n+\treturn node;\n+}\n+\n+struct node *graph_node_bysha(const struct graph *graph,\n+\t\t\t      const unsigned char *sha)\n+{\n+\tconst struct node_list *head = *(graph->commits + sha[0]);\n+\twhile ( head ) {\n+\t\tif ( !head->node->virtual &&\n+\t\t     sha_eq(head->node->commit->object.sha1, sha) ) {\n+\t\t\treturn head->node;\n+\t\t}\n+\t\thead = head->next;\n+\t}\n+\treturn NULL;\n+}\n+\n+#if 0\n+void node_list_print(const char *msg, const struct node_list *list)\n+{\n+    const struct node_list *p;\n+    printf(\"%s\\n\", msg);\n+    for_each_node_list(p, list) {\n+\tint len;\n+\tconst char *msg = node_title(p->node, &len);\n+\tprintf(\"\\t%s %.*s\\n\", node_hex_sha1(p->node), len, msg);\n+    }\n+}\n+#endif\n+\n+/*\n+vim: sw=8 noet\n+*/\ndiff --git a/graph.h b/graph.h\nnew file mode 100644\nindex 0000000..3b8ca5c\n--- /dev/null\n+++ b/graph.h\n@@ -0,0 +1,80 @@\n+#ifndef _GRAPH_H_\n+#define _GRAPH_H_\n+\n+struct node;\n+struct graph;\n+struct commit;\n+struct tree;\n+struct commit_list;\n+\n+struct node_list\n+{\n+\tstruct node_list *next;\n+\tstruct node *node;\n+};\n+\n+struct node\n+{\n+\tstruct commit *commit;\n+\tstruct tree *tree;\n+\n+\tunsigned parents_count;\n+\tstruct node_list *parents;\n+\tstruct node_list *children;\n+\n+\tunsigned virtual:1;\n+\tunsigned virtual_id;\n+\tconst char *comment;\n+};\n+\n+struct node_list *node_list_insert(struct node *node, struct node_list **list);\n+void node_list_free(struct node_list **list, int free_nodes);\n+struct node_list *node_list_free1(struct node_list *list, int free_node);\n+\n+static inline struct node_list *node_list_shift(struct node_list **list)\n+{\n+\tstruct node_list *head = *list;\n+\t*list = head->next;\n+\treturn head;\n+}\n+\n+static inline struct node *node_list_shift_node(struct node_list **list)\n+{\n+\tstruct node *node = (*list)->node;\n+\t*list = node_list_free1(*list, 0);\n+\treturn node;\n+}\n+\n+struct node *node_alloc(struct commit *);\n+struct node *node_alloc_virtual(struct tree *, const char *comment);\n+\n+void node_set_parents(struct node *node, struct node_list *parents);\n+unsigned node_list_count(const struct node_list *);\n+\n+struct node_list *node_list_find_node(const struct node *node,\n+\t\t\t\t      const struct node_list *list);\n+\n+\n+struct graph\n+{\n+\t// hashed by first byte of SHA-1 or low byte of virtual_id\n+\tstruct node_list *commits[256];\n+};\n+\n+struct node *graph_add_node(struct graph *graph, struct node *node);\n+struct node *graph_node_bysha(const struct graph *graph,\n+\t\t\t      const unsigned char *sha);\n+\n+#define for_each_node_list(p,list) \\\n+\tfor ( p = (list); p; p = p->next )\n+\n+const char *node_title(struct node *, int *len);\n+const unsigned char *node_sha(const struct node *);\n+const char *node_hex_sha1(const struct node *);\n+void node_list_print(const char *msg, const struct node_list *list);\n+\n+struct tree *git_write_tree();\n+\n+#endif /* _GRAPH_H_ */\n+\n+// vim: sw=8 noet\ndiff --git a/merge-recursive.c b/merge-recursive.c\nnew file mode 100644\nindex 0000000..abceb30\n--- /dev/null\n+++ b/merge-recursive.c\n@@ -0,0 +1,1622 @@\n+/*\n+ * Recursive Merge algorithm stolen from git-merge-recursive.py by\n+ * Fredrik Kuivinen.\n+ */\n+#include <stdarg.h>\n+#include <string.h>\n+#include <assert.h>\n+#include <sys/wait.h>\n+#include <sys/types.h>\n+#include <sys/stat.h>\n+#include <time.h>\n+#include \"cache.h\"\n+#include \"commit.h\"\n+#include \"blob.h\"\n+#include \"tree-walk.h\"\n+#include \"diff.h\"\n+#include \"diffcore.h\"\n+#include \"run-command.h\"\n+\n+#include \"graph.h\"\n+#include \"path-list.h\"\n+\n+#define HAVE_ALLOCA\n+#define DEBUG\n+\n+#ifdef DEBUG\n+#define debug(args, ...) fprintf(stderr, args, ## __VA_ARGS__)\n+#else\n+#define debug(args, ...)\n+#endif\n+\n+#define for_each_commit(p,list) for ( p = (list); p; p = p->next )\n+\n+static int sha_eq(const unsigned char *a, const unsigned char *b)\n+{\n+\tif ( !a && !b )\n+\t\treturn 2;\n+\treturn a && b && memcmp(a, b, 20) == 0;\n+}\n+\n+static void memswp(void *p1, void *p2, unsigned n)\n+{\n+\tunsigned char *a = p1, *b = p2;\n+\twhile ( n-- ) {\n+\t\t*a ^= *b;\n+\t\t*b ^= *a;\n+\t\t*a ^= *b;\n+\t\t++a;\n+\t\t++b;\n+\t}\n+}\n+\n+\n+struct merge_result\n+{\n+\tstruct node *commit;\n+\tunsigned clean:1;\n+};\n+\n+struct merge_tree_result\n+{\n+\tstruct tree *tree;\n+\tunsigned clean:1;\n+};\n+\n+static struct merge_tree_result merge_trees(struct tree *head,\n+\t\t\t\t     struct tree *merge,\n+\t\t\t\t     struct tree *common,\n+\t\t\t\t     const char *branch1Name,\n+\t\t\t\t     const char *branch2Name);\n+\n+struct index_entry\n+{\n+\tstruct index_entry *next;\n+\tstruct\n+\t{\n+\t\tunsigned mode;\n+\t\tunsigned char sha[20];\n+\t} stages[4];\n+\tunsigned processed:1;\n+\tchar path[1];\n+};\n+\n+struct index_entry *index_entry_alloc(const char *path)\n+{\n+\tsize_t n = strlen(path); /* index_entry::path has room for \\0 */\n+\tstruct index_entry *p = xmalloc(sizeof(struct index_entry) + n);\n+\tif ( !p )\n+\t\treturn NULL;\n+\tmemcpy(p->path, path, n + 1);\n+\tp->next = NULL;\n+\tp->processed = 0;\n+\treturn p;\n+}\n+\n+#if 0\n+static\n+void print_index_entry(const char *text, const struct index_entry *e)\n+{\n+    printf(\"%s%s next: %p %s\\n\", text,\n+\t   e ? e->path: NULL,\n+\t   e ? e->next: NULL,\n+\t   e && e->processed ? \"processed\": \"\");\n+    if ( e ) {\n+\tint i;\n+\tfor ( i = 1; i < 4; ++i )\n+\t    printf(\"\\tstage[%d]: %06o %s\\n\", i,\n+\t\t   e->stages[i].mode,\n+\t\t   sha1_to_hex(e->stages[i].sha));\n+    }\n+}\n+#endif\n+\n+static struct path_list currentFileSet = {NULL, 0, 0};\n+static struct path_list currentDirectorySet = {NULL, 0, 0};\n+\n+static int output_indent = 0;\n+\n+static void output(const char *fmt, ...)\n+{\n+\tva_list args;\n+\tint i;\n+\tfor ( i = output_indent; i--; )\n+\t\tfputs(\"  \", stdout);\n+\tva_start(args, fmt);\n+\tvfprintf(stdout, fmt, args);\n+\tva_end(args);\n+\tfputc('\\n', stdout);\n+}\n+\n+static const char *original_index_file;\n+static const char *temporary_index_file;\n+\n+static void setup_index(int temp)\n+{\n+\tconst char *idx = temp ? temporary_index_file: original_index_file;\n+\tunlink(temporary_index_file);\n+\tsetenv(\"GIT_INDEX_FILE\", idx, 1);\n+}\n+\n+/*\n+ * This is a global variable which is used in a number of places but\n+ * only written to in the 'merge' function.\n+ *\n+ * index_only == 1    => Don't leave any non-stage 0 entries in the cache and\n+ *                       don't update the working directory.\n+ *               0    => Leave unmerged entries in the cache and update\n+ *                       the working directory.\n+ */\n+static int index_only = 0;\n+\n+static int git_read_tree(const struct tree *tree)\n+{\n+#if 0\n+\tfprintf(stderr, \"GIT_INDEX_FILE='%s' git-read-tree %s\\n\",\n+\t\tgetenv(\"GIT_INDEX_FILE\"),\n+\t\tsha1_to_hex(tree->object.sha1));\n+#endif\n+\tconst char *argv[] = { \"git-read-tree\", NULL, NULL, };\n+\targv[1] = sha1_to_hex(tree->object.sha1);\n+\tint rc = run_command_v(2, argv);\n+\treturn rc < 0 ? -1: rc;\n+}\n+\n+static int git_merge_trees(const char *update_arg,\n+\t\t\t   struct tree *common,\n+\t\t\t   struct tree *head,\n+\t\t\t   struct tree *merge)\n+{\n+#if 0\n+\tfprintf(stderr, \"GIT_INDEX_FILE='%s' git-read-tree %s -m %s %s %s\\n\",\n+\t\tgetenv(\"GIT_INDEX_FILE\"),\n+\t\tupdate_arg,\n+\t\tsha1_to_hex(common->object.sha1),\n+\t\tsha1_to_hex(head->object.sha1),\n+\t\tsha1_to_hex(merge->object.sha1));\n+#endif\n+\tconst char *argv[] = {\n+\t\t\"git-read-tree\", NULL, \"-m\", NULL, NULL, NULL,\n+\t\tNULL,\n+\t};\n+\targv[1] = update_arg;\n+\targv[3] = sha1_to_hex(common->object.sha1);\n+\targv[4] = sha1_to_hex(head->object.sha1);\n+\targv[5] = sha1_to_hex(merge->object.sha1);\n+\tint rc = run_command_v(6, argv);\n+\treturn rc < 0 ? -1: rc;\n+}\n+\n+static int fget_sha1(unsigned char *sha, FILE *, int *ch);\n+\n+/*\n+ * Merge the commits h1 and h2, return the resulting virtual\n+ * commit object and a flag indicating the cleaness of the merge.\n+ */\n+static\n+struct merge_result merge(struct node *h1,\n+\t\t\t  struct node *h2,\n+\t\t\t  const char *branch1Name,\n+\t\t\t  const char *branch2Name,\n+\t\t\t  struct graph *graph,\n+\t\t\t  int callDepth /* =0 */,\n+\t\t\t  struct node *ancestor /* =None */)\n+{\n+\tstruct merge_result result = { NULL, 0 };\n+\n+\tconst char *msg;\n+\tint msglen;\n+\toutput(\"Merging:\");\n+\tmsg = node_title(h1, &msglen);\n+\toutput(\"%s %.*s\", node_hex_sha1(h1), msglen, msg);\n+\tmsg = node_title(h2, &msglen);\n+\toutput(\"%s %.*s\", node_hex_sha1(h2), msglen, msg);\n+\tif ( !ancestor && !graph )\n+\t\tdie(\"graph is not initialized\");\n+\tstruct node_list *ca = NULL;\n+\tif ( ancestor )\n+\t\tnode_list_insert(ancestor, &ca);\n+\telse {\n+\t\tstruct node_list **pca = &ca;\n+\t\tchar cmd[100];\n+\t\tsprintf(cmd, \"git-merge-base --all %s %s\",\n+\t\t\tnode_hex_sha1(h1),\n+\t\t\tnode_hex_sha1(h2));\n+\t\tFILE *fp = popen(cmd, \"r\");\n+\t\twhile (!feof(fp)) {\n+\t\t\tunsigned char sha1[20];\n+\t\t\tint ch;\n+\t\t\tif (fget_sha1(sha1, fp, &ch) == 0) {\n+\t\t\t\tstruct node *n;\n+\t\t\t\tn = node_alloc(lookup_commit(sha1));\n+\t\t\t\tnode_list_insert(n, pca);\n+\t\t\t\tpca = &(*pca)->next;\n+\t\t\t}\n+\t\t}\n+\t\tpclose(fp);\n+\t}\n+\n+\toutput(\"found %u common ancestor(s):\", node_list_count(ca));\n+\tstruct node_list *x;\n+\tfor_each_node_list(x,ca) {\n+\t\tmsg = node_title(x->node, &msglen);\n+\t\toutput(\"%s %.*s\", node_hex_sha1(x->node), msglen, msg);\n+\t}\n+\n+\tstruct node *mergedCA = node_list_shift_node(&ca);\n+\n+\tstruct node_list *h;\n+\tfor_each_commit(h,ca) {\n+\t\toutput_indent = callDepth + 1;\n+\t\tresult = merge(mergedCA, h->node,\n+\t\t\t       \"Temporary merge branch 1\",\n+\t\t\t       \"Temporary merge branch 2\",\n+\t\t\t       graph,\n+\t\t\t       callDepth + 1,\n+\t\t\t       NULL);\n+\t\tmergedCA = result.commit;\n+\t\toutput_indent = callDepth;\n+\n+\t\tif ( !mergedCA )\n+\t\t\tdie(\"merge returned no commit\");\n+\t}\n+\n+\tif ( callDepth == 0 ) {\n+\t\tsetup_index(0);\n+\t\tindex_only = 0;\n+\t} else {\n+\t\tsetup_index(1);\n+\t\tgit_read_tree(h1->tree);\n+\t\tindex_only = 1;\n+\t}\n+\n+\tstruct merge_tree_result mtr;\n+\tmtr = merge_trees(h1->tree, h2->tree,\n+\t\t\t  mergedCA->tree, branch1Name, branch2Name);\n+\n+\tif ( !ancestor && (mtr.clean || index_only) ) {\n+\t\tresult.commit = node_alloc_virtual(mtr.tree, \"merged tree\");\n+\t\tstruct node_list *parents = NULL;\n+\t\tnode_list_insert(h1, &parents);\n+\t\tnode_list_insert(h2, &parents->next);\n+\t\tnode_set_parents(result.commit, parents);\n+\t\tgraph_add_node(graph, result.commit);\n+\t} else\n+\t\tresult.commit = NULL;\n+\n+\tresult.clean = mtr.clean;\n+\treturn result;\n+}\n+\n+#define READ_TREE_FOUND 2\n+typedef int (*read_tree_rt_fn_t)(const char *sha1,\n+\t\t\t\t const char *base,\n+\t\t\t\t int baselen,\n+\t\t\t\t const struct name_entry *entry,\n+\t\t\t\t void *data);\n+\n+/* git-ls-tree -r -t <tree> */\n+static int read_tree_rt(struct tree *tree,\n+\t\t\tconst char *base,\n+\t\t\tint baselen,\n+\t\t\tread_tree_rt_fn_t fn,\n+\t\t\tvoid *data)\n+{\n+\tstruct tree_desc desc;\n+\tstruct name_entry entry;\n+\n+\tif (parse_tree(tree))\n+\t\treturn -1;\n+\n+\tdesc.buf = tree->buffer;\n+\tdesc.size = tree->size;\n+\n+\twhile (tree_entry(&desc, &entry)) {\n+\t\tint retval = fn(entry.sha1, base, baselen, &entry, data);\n+\n+\t\tswitch (retval) {\n+\t\tcase READ_TREE_RECURSIVE:\n+\t\t\tbreak;\n+\t\tcase 0:\n+\t\t\tcontinue;\n+\t\tdefault:\n+\t\t\treturn retval;\n+\t\t}\n+\t\tif (S_ISDIR(entry.mode)) {\n+#if defined(HAVE_ALLOCA)\n+\t\t\tchar *path = alloca(baselen + entry.pathlen + 1);\n+#else\n+\t\t\tchar *path = xmalloc(baselen + entry.pathlen + 1);\n+#endif\n+\t\t\tmemcpy(path, base, baselen);\n+\t\t\tmemcpy(path + baselen, entry.path, entry.pathlen);\n+\t\t\tpath[baselen + entry.pathlen] = '/';\n+\t\t\tretval = read_tree_rt(lookup_tree(entry.sha1),\n+\t\t\t\t\t      path,\n+\t\t\t\t\t      baselen + entry.pathlen + 1,\n+\t\t\t\t\t      fn, data);\n+#if !defined(HAVE_ALLOCA)\n+\t\t\tfree(path);\n+#endif\n+\t\t\tif (retval)\n+\t\t\t\treturn retval;\n+\t\t}\n+\t}\n+\treturn 0;\n+}\n+\n+struct files_and_dirs\n+{\n+\tstruct path_list *files;\n+\tstruct path_list *dirs;\n+};\n+\n+static int save_files_dirs(const char *sha1,\n+\t\t\t   const char *base,\n+\t\t\t   int baselen,\n+\t\t\t   const struct name_entry *entry,\n+\t\t\t   void *data_)\n+{\n+\tstruct files_and_dirs *data = data_;\n+\tchar *path = malloc(baselen + entry->pathlen + 1);\n+\tmemcpy(path, base, baselen);\n+\tmemcpy(path + baselen, entry->path, entry->pathlen);\n+\tpath[baselen + entry->pathlen] = '\\0';\n+\n+\tif (S_ISDIR(entry->mode))\n+\t\tpath_list_insert(path, data->dirs);\n+\telse\n+\t\tpath_list_insert(path, data->files);\n+\treturn READ_TREE_RECURSIVE;\n+}\n+\n+static int get_files_dirs(struct tree *tree,\n+\t\t\t  struct path_list *files,\n+\t\t\t  struct path_list *dirs)\n+{\n+\tstruct files_and_dirs data;\n+\tpath_list_clear(files, 1);\n+\tpath_list_clear(dirs, 1);\n+\tdata.files = files;\n+\tdata.dirs = dirs;\n+\tdebug(\"get_files_dirs ...\\n\");\n+\tif ( read_tree_rt(tree, \"\", 0, save_files_dirs, &data) != 0 ) {\n+\t\tdebug(\"  get_files_dirs done (0)\\n\");\n+\t\treturn 0;\n+\t}\n+\tint n = path_list_count(files) + path_list_count(dirs);\n+\tdebug(\"  get_files_dirs done (%d)\\n\", n);\n+\treturn n;\n+}\n+\n+static struct index_entry *index_entry_find(struct index_entry *ents,\n+\t\t\t\t\t    const char *path)\n+{\n+\tstruct index_entry *e;\n+\tfor ( e = ents; e; e = e->next )\n+\t\tif ( strcmp(e->path, path) == 0 )\n+\t\t\tbreak;\n+\treturn e;\n+}\n+\n+static struct index_entry *index_entry_get(struct index_entry **ents,\n+\t\t\t\t\t   const char *path)\n+{\n+\tstruct index_entry *e, **tail = ents;\n+\tfor ( e = *ents; e; e = e->next ) {\n+\t\tif ( strcmp(e->path, path) == 0 )\n+\t\t\treturn e;\n+\t\ttail = &e->next;\n+\t}\n+\te = index_entry_alloc(path);\n+\tmemset(e->stages, 0, sizeof(e->stages));\n+\treturn *tail = e;\n+}\n+\n+struct find_entry\n+{\n+\tconst char *path;\n+\tint pathlen;\n+\tunsigned char *sha;\n+\tunsigned *mode;\n+};\n+\n+static int find_entry(const char *sha,\n+\t\t      const char *base,\n+\t\t      int baselen,\n+\t\t      const struct name_entry *entry,\n+\t\t      void *data_)\n+{\n+\tstruct find_entry *data = data_;\n+\tif (baselen + entry->pathlen == data->pathlen &&\n+\t    memcmp(data->path, base, baselen) == 0 &&\n+\t    memcmp(data->path + baselen, entry->path, entry->pathlen) == 0) {\n+\t\tmemcpy(data->sha, entry->sha1, 20);\n+\t\t*data->mode = entry->mode;\n+\t\treturn READ_TREE_FOUND;\n+\t}\n+\treturn READ_TREE_RECURSIVE;\n+}\n+\n+/*\n+ * Returns a index_entry instance which doesn't have to correspond to\n+ * a real cache entry in Git's index.\n+ */\n+static struct index_entry *index_entry_from_db(const char *path,\n+\t\t\t\t\t       struct tree *o,\n+\t\t\t\t\t       struct tree *a,\n+\t\t\t\t\t       struct tree *b)\n+{\n+\tstruct index_entry *e = index_entry_alloc(path);\n+\tstruct find_entry data;\n+\tdata.path = path;\n+\tdata.pathlen = strlen(path);\n+\tdata.sha = e->stages[1].sha;\n+\tdata.mode = &e->stages[1].mode;\n+\tif ( read_tree_rt(o, \"\", 0, find_entry, &data) != READ_TREE_FOUND ) {\n+\t\tmemcpy(e->stages[1].sha, null_sha1, 20);\n+\t\te->stages[1].mode = 0;\n+\t}\n+\tdata.sha = e->stages[2].sha;\n+\tdata.mode = &e->stages[2].mode;\n+\tif ( read_tree_rt(a, \"\", 0, find_entry, &data) != READ_TREE_FOUND ) {\n+\t\tmemcpy(e->stages[2].sha, null_sha1, 20);\n+\t\te->stages[2].mode = 0;\n+\t}\n+\tdata.sha = e->stages[3].sha;\n+\tdata.mode = &e->stages[3].mode;\n+\tif ( read_tree_rt(b, \"\", 0, find_entry, &data) != READ_TREE_FOUND ) {\n+\t\tmemcpy(e->stages[3].sha, null_sha1, 20);\n+\t\te->stages[3].mode = 0;\n+\t}\n+\treturn e;\n+}\n+\n+static void free_index_entries(struct index_entry **ents)\n+{\n+\twhile (*ents) {\n+\t\tstruct index_entry *next = (*ents)->next;\n+\t\tfree(*ents);\n+\t\t*ents = next;\n+\t}\n+}\n+\n+static int fget_mode(unsigned *mode, FILE *fp, int *ch)\n+{\n+\tint p;\n+\tchar buf[8];\n+\tfor (p = 0; (*ch = fgetc(fp)) != EOF && p < 6;) {\n+\t\tif (*ch == '\\x20' || *ch == '\\t' || *ch == '\\n' || *ch == '\\r')\n+\t\t\tbreak;\n+\t\tif (*ch < '0' || *ch > '7')\n+\t\t\treturn -1;\n+\t\tbuf[p++] = *ch;\n+\t}\n+\tbuf[p] = '\\0';\n+\t*mode = strtoul(buf, 0, 8);\n+\treturn 0;\n+}\n+\n+static int fget_sha1(unsigned char *sha, FILE *fp, int *ch)\n+{\n+\tchar buf[40];\n+\tint p;\n+\tfor (p = 0; (*ch = fgetc(fp)) != EOF && p < 40;) {\n+\t\tif (('0' <= *ch && *ch <= '9') ||\n+\t\t    ('a' <= *ch && *ch <= 'f') ||\n+\t\t    ('A' <= *ch && *ch <= 'F'))\n+\t\t\tbuf[p++] = *ch;\n+\t\telse\n+\t\t\treturn -1;\n+\t}\n+\tif ( p != 40 || get_sha1_hex(buf, sha) == -1 )\n+\t\treturn -1;\n+\treturn 0;\n+}\n+\n+/*\n+ * Create a dictionary mapping file names to CacheEntry objects. The\n+ * dictionary contains one entry for every path with a non-zero stage entry.\n+ */\n+static struct index_entry *get_unmerged()\n+{\n+\tstruct index_entry *unmerged = NULL;\n+\tFILE *fp = popen(\"git-ls-files -z --unmerged\", \"r\");\n+\tif ( !fp )\n+\t\treturn NULL;\n+\tdebug(\"get_unmerged...\\n\");\n+\tint ch;\n+\twhile ( !feof(fp) ) {\n+\t\tunsigned mode;\n+\t\tunsigned char sha[20];\n+\t\tchar stage = '0';\n+\t\tchar path[PATH_MAX];\n+\t\tint p;\n+\t\t/* mode */\n+\t\tif ( fget_mode(&mode, fp, &ch) )\n+\t\t\tgoto wait_eol;\n+\t\tif ( '\\x20' != ch )\n+\t\t\tgoto wait_eol;\n+\t\t/* SHA1 */\n+\t\tif ( fget_sha1(sha, fp, &ch) )\n+\t\t\tgoto wait_eol;\n+\t\tif ( '\\x20' != ch )\n+\t\t\tgoto wait_eol;\n+\t\t/* stage */\n+\t\tif ( (ch = fgetc(fp)) != EOF ) {\n+\t\t\tstage = ch;\n+\t\t\tif ( ch < '1' || ch > '3' )\n+\t\t\t\tgoto wait_eol;\n+\t\t}\n+\t\tif ( (ch = fgetc(fp)) == EOF || '\\t' != ch )\n+\t\t\tgoto wait_eol;\n+\t\t/* path */\n+\t\tfor ( p = 0; (ch = fgetc(fp)) != EOF; ++p ) {\n+\t\t\tpath[p] = ch;\n+\t\t\tif ( !ch )\n+\t\t\t\tbreak;\n+\t\t\tif ( p == sizeof(path) - 1 ) {\n+\t\t\t\tpath[p] = '\\0';\n+\t\t\t\terror(\"path too long: %s\", path);\n+\t\t\t\tgoto wait_eol;\n+\t\t\t}\n+\t\t}\n+\t\tif ( ch )\n+\t\t\tgoto wait_eol;\n+\t\tstruct index_entry *e = index_entry_get(&unmerged, path);\n+\t\te->stages[stage - '1' + 1].mode = mode;\n+\t\tmemcpy(e->stages[stage - '1' + 1].sha, sha, 20);\n+\t\tcontinue;\n+\twait_eol:\n+\t\twhile ( (ch = fgetc(fp)) != EOF && ch );\n+\t}\n+\tpclose(fp);\n+\tdebug(\"  get_unmerged done\\n\");\n+\treturn unmerged;\n+}\n+\n+struct rename_entry\n+{\n+\tstruct rename_entry *next;\n+\n+\tunsigned char src_sha[20];\n+\tunsigned src_mode;\n+\tstruct index_entry *src_entry;\n+\n+\tunsigned char dst_sha[20];\n+\tunsigned dst_mode;\n+\tstruct index_entry *dst_entry;\n+\n+\tunsigned score:16,\n+\t\t processed:1;\n+\n+\tchar *src; /* dst + strlen(dst) + 1 */\n+\tchar dst[1];\n+};\n+\n+static struct rename_entry *find_rename_bysrc(struct rename_entry *e,\n+\t\t\t\t\t      const char *name)\n+{\n+\twhile ( e ) {\n+\t\tif ( strcmp(e->src, name) == 0 )\n+\t\t\tbreak;\n+\t\te = e->next;\n+\t}\n+\treturn e;\n+}\n+\n+static struct rename_entry *find_rename_bydst(struct rename_entry *e,\n+\t\t\t\t\t      const char *name)\n+{\n+\twhile ( e ) {\n+\t\tif ( strcmp(e->dst, name) == 0 )\n+\t\t\tbreak;\n+\t\te = e->next;\n+\t}\n+\treturn e;\n+}\n+\n+static void free_rename_entries(struct rename_entry **list)\n+{\n+\twhile (*list) {\n+\t\tstruct rename_entry *next = (*list)->next;\n+\t\tfree(*list);\n+\t\t*list = next;\n+\t}\n+}\n+\n+/*\n+ * Get information of all renames which occured between 'oTree' and\n+ * 'tree'. We need the three trees in the merge ('oTree', 'aTree' and\n+ * 'bTree') to be able to associate the correct cache entries with\n+ * the rename information. 'tree' is always equal to either aTree or bTree.\n+ */\n+static struct rename_entry *get_renames(struct tree *tree,\n+\t\t\t\t\tstruct tree *oTree,\n+\t\t\t\t\tstruct tree *aTree,\n+\t\t\t\t\tstruct tree *bTree,\n+\t\t\t\t\tstruct index_entry **entries)\n+{\n+\ttime_t t = time(0);\n+\tdebug(\"getRenames ...\\n\");\n+\tstruct rename_entry *renames = NULL;\n+\tstruct rename_entry **rptr = &renames;\n+\tstruct diff_options opts;\n+\tdiff_setup(&opts);\n+\topts.recursive = 1;\n+\topts.detect_rename = DIFF_DETECT_RENAME;\n+\topts.output_format = DIFF_FORMAT_NO_OUTPUT;\n+\tif (diff_setup_done(&opts) < 0)\n+\t\tdie(\"diff setup failed\");\n+\tdiff_tree_sha1(oTree->object.sha1, tree->object.sha1, \"\", &opts);\n+\tdiffcore_std(&opts);\n+\tint i;\n+\tfor (i = 0; i < diff_queued_diff.nr; ++i) {\n+\t\tstruct rename_entry *re;\n+\t\tstruct diff_filepair *pair = diff_queued_diff.queue[i];\n+\t\tif (pair->status != 'R')\n+\t\t\tcontinue;\n+\t\tsize_t l1 = strlen(pair->one->path);\n+\t\tsize_t l2 = strlen(pair->two->path);\n+\t\tre = xmalloc(sizeof(*re) + l1 + l2 + 2);\n+\t\tre->src = re->dst + l2;\n+\t\tre->next = NULL;\n+\t\tre->processed = 0;\n+\t\tre->score = pair->score;\n+\t\tmemcpy(re->src_sha, pair->one->sha1, 20);\n+\t\tmemcpy(re->src, pair->one->path, ++l1);\n+\t\tre->src_mode = pair->one->mode;\n+\t\tmemcpy(re->dst_sha, pair->two->sha1, 20);\n+\t\tmemcpy(re->dst, pair->two->path, ++l2);\n+\t\tre->dst_mode = pair->two->mode;\n+\t\t// TODO: optimize index_entry_find\n+\t\tre->src_entry = index_entry_find(*entries, re->src);\n+\t\tif ( !re->src_entry ) {\n+\t\t\tre->src_entry = index_entry_from_db(re->src, oTree, aTree, bTree);\n+\t\t\tre->src_entry->next = *entries;\n+\t\t\t*entries = re->src_entry;\n+\t\t}\n+\t\tre->dst_entry = index_entry_find(*entries, re->dst);\n+\t\tif ( !re->dst_entry ) {\n+\t\t\tre->dst_entry = index_entry_from_db(re->dst, oTree, aTree, bTree);\n+\t\t\tre->dst_entry->next = *entries;\n+\t\t\t*entries = re->dst_entry;\n+\t\t}\n+\t\t*rptr = re;\n+\t\trptr = &re->next;\n+\t}\n+\topts.output_format = DIFF_FORMAT_NO_OUTPUT;\n+\tdiff_flush(&opts);\n+\tdebug(\"  getRenames done in %ld\\n\", time(0)-t);\n+\tdie(\"PROFILING\");\n+\treturn renames;\n+}\n+\n+static FILE *git_update_index_pipe()\n+{\n+\treturn popen(\"git-update-index -z --index-info\", \"w\");\n+}\n+\n+static int update_stages(FILE *up_index,\n+\t\t\t const char *path,\n+\t\t\t const unsigned char *osha, unsigned omode,\n+\t\t\t const unsigned char *asha, unsigned amode,\n+\t\t\t const unsigned char *bsha, unsigned bmode,\n+\t\t\t int clear /* =True */)\n+{\n+\tif ( !up_index )\n+\t\treturn -1;\n+\tif ( clear ) {\n+\t\tfprintf(up_index, \"0 %s\\t%s\", sha1_to_hex(null_sha1), path);\n+\t\tfputc('\\0', up_index);\n+\t}\n+\tif ( omode ) {\n+\t\tfprintf(up_index, \"0%o %s 1\\t%s\", omode, sha1_to_hex(osha), path);\n+\t\tfputc('\\0', up_index);\n+\t}\n+\tif ( amode ) {\n+\t\tfprintf(up_index, \"0%o %s 2\\t%s\", amode, sha1_to_hex(asha), path);\n+\t\tfputc('\\0', up_index);\n+\t}\n+\tif ( bmode ) {\n+\t\tfprintf(up_index, \"0%o %s 3\\t%s\", bmode, sha1_to_hex(bsha), path);\n+\t\tfputc('\\0', up_index);\n+\t}\n+\treturn 0;\n+}\n+\n+static int remove_path(const char *name)\n+{\n+\tint ret;\n+\tchar *slash;\n+\n+\tret = unlink(name);\n+\tif ( ret )\n+\t\treturn ret;\n+\tint len = strlen(name);\n+\tchar *dirs = malloc(len+1);\n+\tmemcpy(dirs, name, len);\n+\tdirs[len] = '\\0';\n+\twhile ( (slash = strrchr(name, '/')) ) {\n+\t\t*slash = '\\0';\n+\t\tlen = slash - name;\n+\t\tif ( rmdir(name) != 0 )\n+\t\t\tbreak;\n+\t}\n+\tfree(dirs);\n+\treturn ret;\n+}\n+\n+static int remove_file(FILE *update_index, int clean, const char *path)\n+{\n+\tint updateCache = index_only || clean;\n+\tint updateWd = !index_only;\n+\n+\tif ( updateCache ) {\n+\t\tif ( !update_index )\n+\t\t\treturn -1;\n+\t\tfprintf(update_index, \"0 %s\\t%s\", sha1_to_hex(null_sha1), path);\n+\t\tfputc('\\0', update_index);\n+\t\treturn 0;\n+\t}\n+\tif ( updateWd )\n+\t{\n+\t\tunlink(path);\n+\t\tif ( errno != ENOENT || errno != EISDIR )\n+\t\t\treturn -1;\n+\t\tremove_path(path);\n+\t}\n+\treturn 0;\n+}\n+\n+static char *unique_path(const char *path, const char *branch)\n+{\n+\tchar *newpath = xmalloc(strlen(path) + 1 + strlen(branch) + 8 + 1);\n+\tstrcpy(newpath, path);\n+\tstrcat(newpath, \"~\");\n+\tchar *p = newpath + strlen(newpath);\n+\tstrcpy(p, branch);\n+\tfor ( ; *p; ++p )\n+\t\tif ( '/' == *p )\n+\t\t\t*p = '_';\n+\tint suffix = 0;\n+\tstruct stat st;\n+\twhile ( path_list_has_path(&currentFileSet, newpath) ||\n+\t\tpath_list_has_path(&currentDirectorySet, newpath) ||\n+\t\tlstat(newpath, &st) == 0 ) {\n+\t\tsprintf(p, \"_%d\", suffix++);\n+\t}\n+\tpath_list_insert(newpath, &currentFileSet);\n+\treturn newpath;\n+}\n+\n+static int mkdir_p(const char *path, unsigned long mode, int create_last)\n+{\n+\tchar *buf = strdup(path);\n+\tchar *p;\n+\n+\tfor ( p = buf; *p; ++p ) {\n+\t\tif ( *p != '/' )\n+\t\t\tcontinue;\n+\t\t*p = '\\0';\n+\t\tif (mkdir(buf, mode)) {\n+\t\t\tint e = errno;\n+\t\t\tif ( e == EEXIST ) {\n+\t\t\t\tstruct stat st;\n+\t\t\t\tif ( !stat(buf, &st) && S_ISDIR(st.st_mode) )\n+\t\t\t\t\tgoto next; /* ok */\n+\t\t\t\terrno = e;\n+\t\t\t}\n+\t\t\tfree(buf);\n+\t\t\treturn -1;\n+\t\t}\n+\tnext:\n+\t\t*p = '/';\n+\t}\n+\tfree(buf);\n+\tif ( create_last && mkdir(path, mode) )\n+\t\treturn -1;\n+\treturn 0;\n+}\n+\n+/* stolen from builtin-cat-file.c */\n+static void flush_buffer(int fd, const char *buf, unsigned long size)\n+{\n+\twhile (size > 0) {\n+\t\tlong ret = xwrite(fd, buf, size);\n+\t\tif (ret < 0) {\n+\t\t\t/* Ignore epipe */\n+\t\t\tif (errno == EPIPE)\n+\t\t\t\tbreak;\n+\t\t\tdie(\"git-cat-file: %s\", strerror(errno));\n+\t\t} else if (!ret) {\n+\t\t\tdie(\"git-cat-file: disk full?\");\n+\t\t}\n+\t\tsize -= ret;\n+\t\tbuf += ret;\n+\t}\n+}\n+\n+static void update_file_flags(FILE *up_index,\n+\t\t\t      const unsigned char *sha, unsigned mode,\n+\t\t\t      const char *path,\n+\t\t\t      int updateCache, int updateWd)\n+{\n+\tif ( index_only )\n+\t\tupdateWd = 0;\n+\n+\tif ( updateWd ) {\n+\t\tchar type[20];\n+\t\tvoid *buf;\n+\t\tunsigned long size;\n+\n+\t\tbuf = read_sha1_file(sha, type, &size);\n+\t\tif (!buf)\n+\t\t\tdie(\"cannot read object %s '%s'\", sha1_to_hex(sha), path);\n+\t\tif ( strcmp(type, blob_type) != 0 )\n+\t\t\tdie(\"blob expected for %s '%s'\", sha1_to_hex(sha), path);\n+\n+\t\tif ( S_ISREG(mode) ) {\n+\t\t\tif ( mkdir_p(path, 0777, 0 /* don't create last element */) )\n+\t\t\t\tdie(\"failed to create path %s: %s\", path, strerror(errno));\n+\t\t\tunlink(path);\n+\t\t\tif ( mode & 0100 )\n+\t\t\t\tmode = 0777;\n+\t\t\telse\n+\t\t\t\tmode = 0666;\n+\t\t\tint fd = open(path, O_WRONLY | O_TRUNC | O_CREAT, mode);\n+\t\t\tif ( fd < 0 )\n+\t\t\t\tdie(\"failed to open %s: %s\", path, strerror(errno));\n+\t\t\tflush_buffer(fd, buf, size);\n+\t\t\tclose(fd);\n+\t\t} else if ( S_ISLNK(mode) ) {\n+\t\t\tchar *linkTarget = malloc(size + 1);\n+\t\t\tmemcpy(linkTarget, buf, size);\n+\t\t\tlinkTarget[size] = '\\0';\n+\t\t\tmkdir_p(path, 0777, 0);\n+\t\t\tsymlink(linkTarget, path);\n+\t\t} else\n+\t\t\tdie(\"do not know what to do with %06o %s '%s'\",\n+\t\t\t    mode, sha1_to_hex(sha), path);\n+\t}\n+\tif ( updateCache )\n+\t{\n+\t\tfprintf(up_index, \"%06o %s\\t%s\", mode, sha1_to_hex(sha), path);\n+\t\tfputc('\\0', up_index);\n+\t}\n+}\n+\n+static void update_file(FILE *up_index,\n+\t\t\tint clean,\n+\t\t\tconst unsigned char *sha,\n+\t\t\tunsigned mode,\n+\t\t\tconst char *path)\n+{\n+\tupdate_file_flags(up_index, sha, mode, path,\n+\t\t\t  index_only || clean, !index_only);\n+}\n+\n+/* Low level file merging, update and removal */\n+\n+struct merge_file_info\n+{\n+\tunsigned char sha[20];\n+\tunsigned mode;\n+\tunsigned clean:1,\n+\t\t merge:1;\n+};\n+\n+static char *git_unpack_file(const unsigned char *sha1, char *path)\n+{\n+\tvoid *buf;\n+\tchar type[20];\n+\tunsigned long size;\n+\tint fd;\n+\n+\tbuf = read_sha1_file(sha1, type, &size);\n+\tif (!buf || strcmp(type, blob_type))\n+\t\tdie(\"unable to read blob object %s\", sha1_to_hex(sha1));\n+\n+\tstrcpy(path, \".merge_file_XXXXXX\");\n+\tfd = mkstemp(path);\n+\tif (fd < 0)\n+\t\tdie(\"unable to create temp-file\");\n+\tif (write(fd, buf, size) != size)\n+\t\tdie(\"unable to write temp-file\");\n+\tclose(fd);\n+\treturn path;\n+}\n+\n+static struct merge_file_info merge_file(const char *oPath,\n+\t\t\t\t\t const unsigned char *oSha,\n+\t\t\t\t\t unsigned oMode,\n+\t\t\t\t\t const char *aPath,\n+\t\t\t\t\t const unsigned char *aSha,\n+\t\t\t\t\t unsigned aMode,\n+\t\t\t\t\t const char *bPath,\n+\t\t\t\t\t const unsigned char *bSha,\n+\t\t\t\t\t unsigned bMode,\n+\t\t\t\t\t const char *branch1Name,\n+\t\t\t\t\t const char *branch2Name)\n+{\n+\tstruct merge_file_info result;\n+\tresult.merge = 0;\n+\tresult.clean = 1;\n+\n+\tif ( (S_IFMT & aMode) != (S_IFMT & bMode) ) {\n+\t\tresult.clean = 0;\n+\t\tif ( S_ISREG(aMode) ) {\n+\t\t\tresult.mode = aMode;\n+\t\t\tmemcpy(result.sha, aSha, 20);\n+\t\t} else {\n+\t\t\tresult.mode = bMode;\n+\t\t\tmemcpy(result.sha, bSha, 20);\n+\t\t}\n+\t} else {\n+\t\tif ( memcmp(aSha, oSha, 20) != 0 && memcmp(bSha, oSha, 20) != 0 )\n+\t\t\tresult.merge = 1;\n+\n+\t\tresult.mode = aMode == oMode ? bMode: aMode;\n+\n+\t\tif ( memcmp(aSha, oSha, 20) == 0 )\n+\t\t\tmemcpy(result.sha, bSha, 20);\n+\t\telse if ( memcmp(bSha, oSha, 20) == 0 )\n+\t\t\tmemcpy(result.sha, aSha, 20);\n+\t\telse if ( S_ISREG(aMode) ) {\n+\n+\t\t\tint code = 1;\n+\t\t\tchar orig[PATH_MAX];\n+\t\t\tchar src1[PATH_MAX];\n+\t\t\tchar src2[PATH_MAX];\n+\n+\t\t\tgit_unpack_file(oSha, orig);\n+\t\t\tgit_unpack_file(aSha, src1);\n+\t\t\tgit_unpack_file(bSha, src2);\n+\n+\t\t\tconst char *argv[] = {\n+\t\t\t\t\"merge\", \"-L\", NULL, \"-L\", NULL, \"-L\", NULL,\n+\t\t\t\tsrc1, orig, src2,\n+\t\t\t\tNULL\n+\t\t\t};\n+\t\t\tchar *la, *lb, *lo;\n+\t\t\targv[2] = la = malloc(strlen(branch1Name) + 2 + strlen(aPath));\n+\t\t\tstrcat(strcat(strcpy(la, branch1Name), \"/\"), aPath);\n+\t\t\targv[6] = lb = malloc(strlen(branch2Name) + 2 + strlen(bPath));\n+\t\t\tstrcat(strcat(strcpy(lb, branch2Name), \"/\"), bPath);\n+\t\t\targv[4] = lo = malloc(7 + strlen(oPath));\n+\t\t\tstrcat(strcpy(lo, \"orig/\"), oPath);\n+\n+#if 0\n+\t\t\tprintf(\"%s %s %s %s %s %s %s %s %s %s\\n\",\n+\t\t\t       argv[0], argv[1], argv[2], argv[3], argv[4],\n+\t\t\t       argv[5], argv[6], argv[7], argv[8], argv[9]);\n+#endif\n+\t\t\tcode = run_command_v(10, argv);\n+\n+\t\t\tfree(la);\n+\t\t\tfree(lb);\n+\t\t\tfree(lo);\n+\t\t\tif ( code && code < -256 ) {\n+\t\t\t\tdie(\"Failed to execute 'merge'. merge(1) is used as the \"\n+\t\t\t\t    \"file-level merge tool. Is 'merge' in your path?\");\n+\t\t\t}\n+\t\t\tchar cmd[PATH_MAX];\n+\t\t\tsnprintf(cmd, sizeof(cmd), \"git-hash-object -t blob -w %s\", src1);\n+\t\t\tFILE *hash_object = popen(cmd, \"r\");\n+\t\t\tif ( !hash_object )\n+\t\t\t\tdie(\"cannot run git-hash-object: %s\", strerror(errno));\n+\t\t\tint ch;\n+\t\t\tif ( fget_sha1(result.sha, hash_object, &ch) )\n+\t\t\t\tdie(\"invalid output from git-hash-object\");\n+\t\t\tpclose(hash_object);\n+\n+\t\t\tunlink(orig);\n+\t\t\tunlink(src1);\n+\t\t\tunlink(src2);\n+\n+\t\t\tresult.clean = WEXITSTATUS(code) == 0;\n+\t\t} else {\n+\t\t\tif ( !(S_ISLNK(aMode) || S_ISLNK(bMode)) )\n+\t\t\t\tdie(\"cannot merge modes?\");\n+\n+\t\t\tmemcpy(result.sha, aSha, 20);\n+\n+\t\t\tif ( memcmp(aSha, bSha, 20) != 0 )\n+\t\t\t\tresult.clean = 0;\n+\t\t}\n+\t}\n+\n+\treturn result;\n+}\n+\n+static int process_renames(struct rename_entry *renamesA,\n+\t\t\t   struct rename_entry *renamesB,\n+\t\t\t   const char *branchNameA,\n+\t\t\t   const char *branchNameB)\n+{\n+\tdebug(\"processRenames...\\n\");\n+\tint cleanMerge = 1;\n+\n+\tstruct path_list srcNames = {NULL, 0, 0};\n+\tconst struct rename_entry *sre;\n+\tchar **src;\n+\n+\tfor (sre = renamesA; sre; sre = sre->next)\n+\t\tpath_list_insert(sre->src, &srcNames);\n+\tfor (sre = renamesB; sre; sre = sre->next)\n+\t\tpath_list_insert(sre->src, &srcNames);\n+\n+\tFILE *fp = git_update_index_pipe();\n+\tfor_each_path(src,&srcNames) {\n+\t\tstruct rename_entry *renames1, *renames2, *ren1, *ren2;\n+\t\tconst char *branchName1, *branchName2;\n+\t\tren1 = find_rename_bysrc(renamesA, *src);\n+\t\tren2 = find_rename_bysrc(renamesB, *src);\n+\t\tif ( ren1 ) {\n+\t\t\trenames1 = renamesA;\n+\t\t\trenames2 = renamesB;\n+\t\t\tbranchName1 = branchNameA;\n+\t\t\tbranchName2 = branchNameB;\n+\t\t} else {\n+\t\t\trenames1 = renamesB;\n+\t\t\trenames2 = renamesA;\n+\t\t\tbranchName1 = branchNameB;\n+\t\t\tbranchName2 = branchNameA;\n+\t\t\tstruct rename_entry *tmp = ren2;\n+\t\t\tren2 = ren1;\n+\t\t\tren1 = tmp;\n+\t\t}\n+\n+\t\tren1->dst_entry->processed = 1;\n+\t\tren1->src_entry->processed = 1;\n+\n+\t\tif ( ren1->processed )\n+\t\t\tcontinue;\n+\t\tren1->processed = 1;\n+\n+\t\tif ( ren2 ) {\n+\t\t\t/* Renamed in 1 and renamed in 2 */\n+\t\t\tif ( strcmp(ren1->src, ren2->src) != 0 )\n+\t\t\t\tdie(\"ren1.srcName != ren2.srcName\");\n+\t\t\tren2->dst_entry->processed = 1;\n+\t\t\tren2->processed = 1;\n+\t\t\tif ( strcmp(ren1->dst, ren2->dst) != 0 ) {\n+\t\t\t\toutput(\"CONFLICT (rename/rename): \"\n+\t\t\t\t       \"Rename %s->%s in branch %s \"\n+\t\t\t\t       \"rename %s->%s in %s\",\n+\t\t\t\t       *src, ren1->dst, branchName1,\n+\t\t\t\t       *src, ren2->dst, branchName2);\n+\t\t\t\tcleanMerge = 0;\n+\t\t\t\tchar *dstName1 = ren1->dst, *dstName2 = ren2->dst;\n+\t\t\t\tif ( path_list_has_path(&currentDirectorySet, ren1->dst) ) {\n+\t\t\t\t\tdstName1 = unique_path(ren1->dst, branchName1);\n+\t\t\t\t\toutput(\"%s is a directory in %s adding as %s instead\",\n+\t\t\t\t\t       ren1->dst, branchName2, dstName1);\n+\t\t\t\t\tremove_file(fp, 0, ren1->dst);\n+\t\t\t\t}\n+\t\t\t\tif ( path_list_has_path(&currentDirectorySet, ren2->dst) ) {\n+\t\t\t\t\tdstName2 = unique_path(ren2->dst, branchName2);\n+\t\t\t\t\toutput(\"%s is a directory in %s adding as %s instead\",\n+\t\t\t\t\t       ren2->dst, branchName1, dstName2);\n+\t\t\t\t\tremove_file(fp, 0, ren2->dst);\n+\t\t\t\t}\n+\t\t\t\tupdate_stages(fp, dstName1,\n+\t\t\t\t\t       NULL, 0,\n+\t\t\t\t\t       ren1->dst_sha, ren1->dst_mode,\n+\t\t\t\t\t       NULL, 0,\n+\t\t\t\t\t       1 /* clear */);\n+\t\t\t\tupdate_stages(fp, dstName2,\n+\t\t\t\t\t       NULL, 0,\n+\t\t\t\t\t       NULL, 0,\n+\t\t\t\t\t       ren2->dst_sha, ren2->dst_mode,\n+\t\t\t\t\t       1 /* clear */);\n+\t\t\t} else {\n+\t\t\t\tremove_file(fp, 1, ren1->src);\n+\t\t\t\tstruct merge_file_info mfi;\n+\t\t\t\tmfi = merge_file(ren1->src,\n+\t\t\t\t\t\t ren1->src_sha,\n+\t\t\t\t\t\t ren1->src_mode,\n+\t\t\t\t\t\t ren1->dst,\n+\t\t\t\t\t\t ren1->dst_sha,\n+\t\t\t\t\t\t ren1->dst_mode,\n+\t\t\t\t\t\t ren2->dst,\n+\t\t\t\t\t\t ren2->dst_sha,\n+\t\t\t\t\t\t ren2->dst_mode,\n+\t\t\t\t\t\t branchName1,\n+\t\t\t\t\t\t branchName2);\n+\t\t\t\tif ( mfi.merge || !mfi.clean )\n+\t\t\t\t\toutput(\"Renaming %s->%s\", *src, ren1->dst);\n+\n+\t\t\t\tif ( mfi.merge )\n+\t\t\t\t\toutput(\"Auto-merging %s\", ren1->dst);\n+\n+\t\t\t\tif ( !mfi.clean ) {\n+\t\t\t\t\toutput(\"CONFLICT (content): merge conflict in %s\",\n+\t\t\t\t\t       ren1->dst);\n+\t\t\t\t\tcleanMerge = 0;\n+\n+\t\t\t\t\tif ( !index_only )\n+\t\t\t\t\t\tupdate_stages(fp,\n+\t\t\t\t\t\t\t       ren1->dst,\n+\t\t\t\t\t\t\t       ren1->src_sha, ren1->src_mode,\n+\t\t\t\t\t\t\t       ren1->dst_sha, ren1->dst_mode,\n+\t\t\t\t\t\t\t       ren2->dst_sha, ren2->dst_mode,\n+\t\t\t\t\t\t\t       1 /* clear */);\n+\t\t\t\t}\n+\t\t\t\tupdate_file(fp, mfi.clean, mfi.sha, mfi.mode, ren1->dst);\n+\t\t\t}\n+\t\t} else {\n+\t\t\t/* Renamed in 1, maybe changed in 2 */\n+\t\t\tremove_file(fp, 1, ren1->src);\n+\n+\t\t\tunsigned char srcShaOtherBranch[20], dstShaOtherBranch[20];\n+\t\t\tunsigned srcModeOtherBranch, dstModeOtherBranch;\n+\n+\t\t\tint stage = renamesA == renames1 ? 3: 2;\n+\n+\t\t\tmemcpy(srcShaOtherBranch, ren1->src_entry->stages[stage].sha, 20);\n+\t\t\tsrcModeOtherBranch = ren1->src_entry->stages[stage].mode;\n+\n+\t\t\tmemcpy(dstShaOtherBranch, ren1->dst_entry->stages[stage].sha, 20);\n+\t\t\tdstModeOtherBranch = ren1->dst_entry->stages[stage].mode;\n+\n+\t\t\tint tryMerge = 0;\n+\t\t\tchar *newPath;\n+\t\t\tstruct rename_entry *dst2;\n+\n+\t\t\tif ( path_list_has_path(&currentDirectorySet, ren1->dst) ) {\n+\t\t\t\tnewPath = unique_path(ren1->dst, branchName1);\n+\t\t\t\toutput(\"CONFLICT (rename/directory): Rename %s->%s in %s \"\n+\t\t\t\t       \" directory %s added in %s\",\n+\t\t\t\t       ren1->src, ren1->dst, branchName1,\n+\t\t\t\t       ren1->dst, branchName2);\n+\t\t\t\toutput(\"Renaming %s to %s instead\", ren1->src, newPath);\n+\t\t\t\tcleanMerge = 0;\n+\t\t\t\tremove_file(fp, 0, ren1->dst);\n+\t\t\t\tupdate_file(fp, 0, ren1->dst_sha, ren1->dst_mode, newPath);\n+\t\t\t} else if ( memcmp(srcShaOtherBranch, null_sha1, 20) == 0 ) {\n+\t\t\t\toutput(\"CONFLICT (rename/delete): Rename %s->%s in %s \"\n+\t\t\t\t       \"and deleted in %s\",\n+\t\t\t\t       ren1->src, ren1->dst, branchName1,\n+\t\t\t\t       branchName2);\n+\t\t\t\tcleanMerge = 0;\n+\t\t\t\tupdate_file(fp, 0, ren1->dst_sha, ren1->dst_mode, ren1->dst);\n+\t\t\t} else if ( memcmp(dstShaOtherBranch, null_sha1, 20) != 0 ) {\n+\t\t\t\tnewPath = unique_path(ren1->dst, branchName2);\n+\t\t\t\toutput(\"CONFLICT (rename/add): Rename %s->%s in %s. \"\n+\t\t\t\t       \"%s added in %s\",\n+\t\t\t\t       ren1->src, ren1->dst, branchName1,\n+\t\t\t\t       ren1->dst, branchName2);\n+\t\t\t\toutput(\"Adding as %s instead\", newPath);\n+\t\t\t\tupdate_file(fp, 0, dstShaOtherBranch, dstModeOtherBranch, newPath);\n+\t\t\t\tcleanMerge = 0;\n+\t\t\t\ttryMerge = 1;\n+\t\t\t} else if ( (dst2 = find_rename_bydst(renames2, ren1->dst)) ) {\n+\t\t\t\tchar *newPath1 = unique_path(ren1->dst, branchName1);\n+\t\t\t\tchar *newPath2 = unique_path(dst2->dst, branchName2);\n+\t\t\t\toutput(\"CONFLICT (rename/rename): Rename %s->%s in %s. \"\n+\t\t\t\t       \"Rename %s->%s in %s\",\n+\t\t\t\t       ren1->src, ren1->dst, branchName1,\n+\t\t\t\t       dst2->src, dst2->dst, branchName2);\n+\t\t\t\toutput(\"Renaming %s to %s and %s to %s instead\",\n+\t\t\t\t       ren1->src, newPath1, dst2->src, newPath2);\n+\t\t\t\tremove_file(fp, 0, ren1->dst);\n+\t\t\t\tupdate_file(fp, 0, ren1->dst_sha, ren1->dst_mode, newPath1);\n+\t\t\t\tupdate_file(fp, 0, dst2->dst_sha, dst2->dst_mode, newPath2);\n+\t\t\t\tdst2->processed = 1;\n+\t\t\t\tcleanMerge = 0;\n+\t\t\t} else\n+\t\t\t\ttryMerge = 1;\n+\n+\t\t\tif ( tryMerge ) {\n+\t\t\t\tchar *oname = ren1->src;\n+\t\t\t\tchar *aname = ren1->dst;\n+\t\t\t\tchar *bname = ren1->src;\n+\t\t\t\tunsigned char osha[20], asha[20], bsha[20];\n+\t\t\t\tunsigned omode = ren1->src_mode;\n+\t\t\t\tunsigned amode = ren1->dst_mode;\n+\t\t\t\tunsigned bmode = srcModeOtherBranch;\n+\t\t\t\tmemcpy(osha, ren1->src_sha, 20);\n+\t\t\t\tmemcpy(asha, ren1->dst_sha, 20);\n+\t\t\t\tmemcpy(bsha, srcShaOtherBranch, 20);\n+\t\t\t\tconst char *aBranch = branchName1;\n+\t\t\t\tconst char *bBranch = branchName2;\n+\n+\t\t\t\tif ( renamesA != renames1 ) {\n+\t\t\t\t\tmemswp(&aname, &bname, sizeof(aname));\n+\t\t\t\t\tmemswp(asha, bsha, 20);\n+\t\t\t\t\tmemswp(&aBranch, &bBranch, sizeof(aBranch));\n+\t\t\t\t}\n+\t\t\t\tstruct merge_file_info mfi;\n+\t\t\t\tmfi = merge_file(oname, osha, omode,\n+\t\t\t\t\t\t aname, asha, amode,\n+\t\t\t\t\t\t bname, bsha, bmode,\n+\t\t\t\t\t\t aBranch, bBranch);\n+\n+\t\t\t\tif ( mfi.merge || !mfi.clean )\n+\t\t\t\t\toutput(\"Renaming %s => %s\", ren1->src, ren1->dst);\n+\t\t\t\tif ( mfi.merge )\n+\t\t\t\t\toutput(\"Auto-merging %s\", ren1->dst);\n+\t\t\t\tif ( !mfi.clean ) {\n+\t\t\t\t\toutput(\"CONFLICT (rename/modify): Merge conflict in %s\",\n+\t\t\t\t\t       ren1->dst);\n+\t\t\t\t\tcleanMerge = 0;\n+\n+\t\t\t\t\tif ( !index_only )\n+\t\t\t\t\t\tupdate_stages(fp,\n+\t\t\t\t\t\t\t       ren1->dst,\n+\t\t\t\t\t\t\t       osha, omode,\n+\t\t\t\t\t\t\t       asha, amode,\n+\t\t\t\t\t\t\t       bsha, bmode,\n+\t\t\t\t\t\t\t       1 /* clear */);\n+\t\t\t\t}\n+\t\t\t\tupdate_file(fp, mfi.clean, mfi.sha, mfi.mode, ren1->dst);\n+\t\t\t}\n+\t\t}\n+\t}\n+\tpath_list_clear(&srcNames, 0);\n+\tif (pclose(fp)) {\n+\t\tdie(\"git update-index --index-info failed\");\n+\t}\n+\tdebug(\"  processRenames done\\n\");\n+\treturn cleanMerge;\n+}\n+\n+static unsigned char *has_sha(const unsigned char *sha)\n+{\n+\treturn memcmp(sha, null_sha1, 20) == 0 ? NULL: (unsigned char *)sha;\n+}\n+\n+/* Per entry merge function */\n+static int process_entry(FILE *up_index,\n+\t\t\t struct index_entry *entry,\n+\t\t\t const char *branch1Name,\n+\t\t\t const char *branch2Name)\n+{\n+\t/*\n+\tprintf(\"processing entry, clean cache: %s\\n\", index_only ? \"yes\": \"no\");\n+\tprint_index_entry(\"\\tpath: \", entry);\n+\t*/\n+\tint cleanMerge = 1;\n+\tconst char *path = entry->path;\n+\tunsigned char *oSha = has_sha(entry->stages[1].sha);\n+\tunsigned char *aSha = has_sha(entry->stages[2].sha);\n+\tunsigned char *bSha = has_sha(entry->stages[3].sha);\n+\tunsigned oMode = entry->stages[1].mode;\n+\tunsigned aMode = entry->stages[2].mode;\n+\tunsigned bMode = entry->stages[3].mode;\n+\n+\tif ( oSha && (!aSha || !bSha) ) {\n+\t\t/* Case A: Deleted in one */\n+\t\tif ( (!aSha && !bSha) ||\n+\t\t     (sha_eq(aSha, oSha) && !bSha) ||\n+\t\t     (!aSha && sha_eq(bSha, oSha)) ) {\n+\t\t\t/* Deleted in both or deleted in one and\n+\t\t\t * unchanged in the other */\n+\t\t\tif ( aSha )\n+\t\t\t\toutput(\"Removing %s\", path);\n+\t\t\tremove_file(up_index, 1, path);\n+\t\t} else {\n+\t\t\t/* Deleted in one and changed in the other */\n+\t\t\tcleanMerge = 0;\n+\t\t\tif ( !aSha ) {\n+\t\t\t\toutput(\"CONFLICT (delete/modify): %s deleted in %s \"\n+\t\t\t\t       \"and modified in %s. Version %s of %s left in tree.\",\n+\t\t\t\t       path, branch1Name,\n+\t\t\t\t       branch2Name, branch2Name, path);\n+\t\t\t\tupdate_file(up_index, 0, bSha, bMode, path);\n+\t\t\t} else {\n+\t\t\t\toutput(\"CONFLICT (delete/modify): %s deleted in %s \"\n+\t\t\t\t       \"and modified in %s. Version %s of %s left in tree.\",\n+\t\t\t\t       path, branch2Name,\n+\t\t\t\t       branch1Name, branch1Name, path);\n+\t\t\t\tupdate_file(up_index, 0, aSha, aMode, path);\n+\t\t\t}\n+\t\t}\n+\n+\t} else if ( (!oSha && aSha && !bSha) ||\n+\t\t    (!oSha && !aSha && bSha) ) {\n+\t\t/* Case B: Added in one. */\n+\t\tconst char *addBranch;\n+\t\tconst char *otherBranch;\n+\t\tunsigned mode;\n+\t\tconst unsigned char *sha;\n+\t\tconst char *conf;\n+\n+\t\tif ( aSha ) {\n+\t\t\taddBranch = branch1Name;\n+\t\t\totherBranch = branch2Name;\n+\t\t\tmode = aMode;\n+\t\t\tsha = aSha;\n+\t\t\tconf = \"file/directory\";\n+\t\t} else {\n+\t\t\taddBranch = branch2Name;\n+\t\t\totherBranch = branch1Name;\n+\t\t\tmode = bMode;\n+\t\t\tsha = bSha;\n+\t\t\tconf = \"directory/file\";\n+\t\t}\n+\t\tif ( path_list_has_path(&currentDirectorySet, path) ) {\n+\t\t\tcleanMerge = 0;\n+\t\t\tconst char *newPath = unique_path(path, addBranch);\n+\t\t\toutput(\"CONFLICT (%s): There is a directory with name %s in %s. \"\n+\t\t\t       \"Adding %s as %s\",\n+\t\t\t       conf, path, otherBranch, path, newPath);\n+\t\t\tremove_file(up_index, 0, path);\n+\t\t\tupdate_file(up_index, 0, sha, mode, newPath);\n+\t\t} else {\n+\t\t\toutput(\"Adding %s\", path);\n+\t\t\tupdate_file(up_index, 1, sha, mode, path);\n+\t\t}\n+\t} else if ( !oSha && aSha && bSha ) {\n+\t\t/* Case C: Added in both (check for same permissions). */\n+\t\tif ( sha_eq(aSha, bSha) ) {\n+\t\t\tif ( aMode != bMode ) {\n+\t\t\t\tcleanMerge = 0;\n+\t\t\t\toutput(\"CONFLICT: File %s added identically in both branches, \"\n+\t\t\t\t       \"but permissions conflict %06o->%06o\",\n+\t\t\t\t       path, aMode, bMode);\n+\t\t\t\toutput(\"CONFLICT: adding with permission: %06o\", aMode);\n+\t\t\t\tupdate_file(up_index, 0, aSha, aMode, path);\n+\t\t\t} else {\n+\t\t\t\t/* This case is handled by git-read-tree */\n+\t\t\t\tassert(0 && \"This case must be handled by git-read-tree\");\n+\t\t\t}\n+\t\t} else {\n+\t\t\tcleanMerge = 0;\n+\t\t\tconst char *newPath1 = unique_path(path, branch1Name);\n+\t\t\tconst char *newPath2 = unique_path(path, branch2Name);\n+\t\t\toutput(\"CONFLICT (add/add): File %s added non-identically \"\n+\t\t\t       \"in both branches. Adding as %s and %s instead.\",\n+\t\t\t       path, newPath1, newPath2);\n+\t\t\tremove_file(up_index, 0, path);\n+\t\t\tupdate_file(up_index, 0, aSha, aMode, newPath1);\n+\t\t\tupdate_file(up_index, 0, bSha, bMode, newPath2);\n+\t\t}\n+\n+\t} else if ( oSha && aSha && bSha ) {\n+\t\t/* case D: Modified in both, but differently. */\n+\t\toutput(\"Auto-merging %s\", path);\n+\t\tstruct merge_file_info mfi;\n+\t\tmfi = merge_file(path, oSha, oMode,\n+\t\t\t\t path, aSha, aMode,\n+\t\t\t\t path, bSha, bMode,\n+\t\t\t\t branch1Name, branch2Name);\n+\n+\t\tif ( mfi.clean )\n+\t\t\tupdate_file(up_index, 1, mfi.sha, mfi.mode, path);\n+\t\telse {\n+\t\t\tcleanMerge = 0;\n+\t\t\toutput(\"CONFLICT (content): Merge conflict in %s\", path);\n+\n+\t\t\tif ( index_only )\n+\t\t\t\tupdate_file(up_index, 0, mfi.sha, mfi.mode, path);\n+\t\t\telse\n+\t\t\t\tupdate_file_flags(up_index, mfi.sha, mfi.mode, path,\n+\t\t\t\t\t\t  0 /* updateCache */,\n+\t\t\t\t\t\t  1 /* updateWd */);\n+\t\t}\n+\t} else\n+\t\tdie(\"Fatal merge failure, shouldn't happen.\");\n+\n+\treturn cleanMerge;\n+}\n+\n+static struct merge_tree_result merge_trees(struct tree *head,\n+\t\t\t\t\t    struct tree *merge,\n+\t\t\t\t\t    struct tree *common,\n+\t\t\t\t\t    const char *branch1Name,\n+\t\t\t\t\t    const char *branch2Name)\n+{\n+\tint code;\n+\tstruct merge_tree_result result = { NULL, 0 };\n+\tif ( !memcmp(common->object.sha1, merge->object.sha1, 20) ) {\n+\t\toutput(\"Already uptodate!\");\n+\t\tresult.tree = head;\n+\t\tresult.clean = 1;\n+\t\treturn result;\n+\t}\n+\n+\tdebug(\"merge_trees ...\\n\");\n+\tcode = git_merge_trees(index_only ? \"-i\": \"-u\", common, head, merge);\n+\n+\tif ( code != 0 )\n+\t\tdie(\"merging of trees %s and %s failed\",\n+\t\t    sha1_to_hex(head->object.sha1),\n+\t\t    sha1_to_hex(merge->object.sha1));\n+\n+\tresult.tree = git_write_tree();\n+\n+\tif ( !result.tree ) {\n+\t\tstruct path_list mfiles = {NULL, 0, 0}, mdirs = {NULL, 0, 0};\n+\n+\t\tget_files_dirs(head, &currentFileSet, &currentDirectorySet);\n+\t\tget_files_dirs(merge, &mfiles, &mdirs);\n+\n+\t\tpath_list_union_update(&currentFileSet, &mfiles);\n+\t\tpath_list_union_update(&currentDirectorySet, &mdirs);\n+\n+\t\tstruct index_entry *entries = get_unmerged();\n+\t\tstruct rename_entry *re_head, *re_merge;\n+\t\tre_head  = get_renames(head, common, head, merge, &entries);\n+\t\tre_merge = get_renames(merge, common, head, merge, &entries);\n+\t\tresult.clean = process_renames(re_head, re_merge,\n+\t\t\t\t\t       branch1Name, branch2Name);\n+\t\tdebug(\"\\tprocessing entries...\\n\");\n+\t\tFILE *fp = git_update_index_pipe();\n+\t\tstruct index_entry *e;\n+\t\tfor (e = entries; e; e = e->next) {\n+\t\t\tif (e->processed)\n+\t\t\t\tcontinue;\n+\t\t\tif (!process_entry(fp, e, branch1Name, branch2Name))\n+\t\t\t\tresult.clean = 0;\n+\t\t}\n+\t\tif (pclose(fp))\n+\t\t\tdie(\"updating entry failed in git update-index\");\n+\t\tif (result.clean || index_only)\n+\t\t\tresult.tree = git_write_tree();\n+\t\telse\n+\t\t\tresult.tree = NULL;\n+\t\tdebug(\"\\t  processing entries done\\n\");\n+\t\tfree_rename_entries(&re_merge);\n+\t\tfree_rename_entries(&re_head);\n+\t\tfree_index_entries(&entries);\n+\t} else {\n+\t\tresult.clean = 1;\n+\t\tprintf(\"merging of trees %s and %s resulted in %s\\n\",\n+\t\t       sha1_to_hex(head->object.sha1),\n+\t\t       sha1_to_hex(merge->object.sha1),\n+\t\t       sha1_to_hex(result.tree->object.sha1));\n+\t}\n+\n+\tdebug(\"  merge_trees done\\n\");\n+\treturn result;\n+}\n+\n+static void collect_nodes(struct node *node, struct node_list **res)\n+{\n+    node_list_insert(node, res);\n+    struct node_list *p;\n+    for ( p = node->parents; p; p = p->next )\n+\tcollect_nodes(node, res);\n+}\n+\n+struct node_list *reachable_nodes(struct node *n1, struct node *n2)\n+{\n+    struct node_list *res = NULL;\n+    collect_nodes(n1, &res);\n+    collect_nodes(n2, &res);\n+    return res;\n+}\n+\n+struct graph *graph_build(struct node_list *commits)\n+{\n+\tstruct graph *graph = malloc(sizeof(struct graph));\n+\tmemset(graph->commits, 0, sizeof(graph->commits));\n+\n+\tchar cmd[256];\n+\tstrcpy(cmd, \"git-rev-list --parents\");\n+\tstruct node_list *cp;\n+\tfor_each_node_list(cp,commits) {\n+\t\tgraph_add_node(graph, cp->node);\n+\t\tstrcat(cmd, \" \");\n+\t\tstrcat(cmd, node_hex_sha1(cp->node));\n+\t}\n+\tassert(strlen(cmd) < sizeof(cmd));\n+\n+\tFILE *fp = popen(cmd, \"r\");\n+\tif (!fp)\n+\t\tdie(\"%s failed: %s\", cmd, strerror(errno));\n+\twhile (!feof(fp)) {\n+\t\tunsigned char sha[20];\n+\t\tint ch;\n+\t\tif (fget_sha1(sha, fp, &ch))\n+\t\t\tbreak;\n+\t\tif (EOF == ch)\n+\t\t\tbreak;\n+\t\t/* a commit */\n+\t\tstruct node *node = graph_node_bysha(graph, sha);\n+\t\tif (!node)\n+\t\t{\n+\t\t\tnode = node_alloc(lookup_commit(sha));\n+\t\t\tgraph_add_node(graph, node);\n+\t\t}\n+\t\t/* ...and its parents. I assume a parent cannot be mentioned\n+\t\t   before the children. */\n+\t\tstruct node_list *parents = NULL;\n+\t\twhile ('\\n' != ch) {\n+\t\t\tif (fget_sha1(sha, fp, &ch)) {\n+\t\t\t\tdie(\"invalid output from %s, \"\n+\t\t\t\t    \"sha1 (parents) expected\",\n+\t\t\t\t    cmd);\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (EOF == ch)\n+\t\t\t\tbreak;\n+\t\t\tstruct node *pn = graph_node_bysha(graph, sha);\n+\t\t\tif (!pn) {\n+\t\t\t\tpn = node_alloc(lookup_commit(sha));\n+\t\t\t\tgraph_add_node(graph, pn);\n+\t\t\t}\n+\t\t\tnode_list_insert(pn, &parents);\n+\t\t}\n+\t\tnode_set_parents(node, parents);\n+\t}\n+\tpclose(fp);\n+\treturn graph;\n+}\n+\n+static int get_sha1_0(const char *ref, unsigned char *sha)\n+{\n+\tsize_t n = strlen(ref);\n+\tchar *t = xmalloc(n + 4);\n+\tmemcpy(t, ref, n);\n+\tstrcpy(t + n, \"^0\");\n+\tint rc = get_sha1(t, sha);\n+\tfree(t);\n+\treturn rc;\n+}\n+\n+int main(int argc, char *argv[])\n+{\n+\tstatic const char *bases[2];\n+\tstatic unsigned bases_count = 0;\n+\n+\toriginal_index_file = getenv(\"GIT_INDEX_FILE\");\n+\n+\tif (!original_index_file)\n+\t\toriginal_index_file = strdup(git_path(\"index\"));\n+\n+\ttemporary_index_file = strdup(git_path(\"mrg-rcrsv-tmp-idx\"));\n+\n+\tif (argc < 4)\n+\t\tdie(\"Usage: %s <base>... -- <head> <remote> ...\\n\", argv[0]);\n+\n+\tint i;\n+\tfor (i = 1; i < argc; ++i) {\n+\t\tif (!strcmp(argv[i], \"--\"))\n+\t\t\tbreak;\n+\t\tif (bases_count < sizeof(bases)/sizeof(*bases))\n+\t\t\tbases[bases_count++] = argv[i];\n+\t}\n+\tif (argc - i != 3) /* \"--\" \"<head>\" \"<remote>\" */\n+\t\tdie(\"Not handling anything other than two heads merge.\");\n+\n+\tunsigned char sha1[20], sha2[20];\n+\tconst char *branch1, *branch2;\n+\n+\tbranch1 = argv[++i];\n+\tif (get_sha1_0(branch1, sha1) != 0)\n+\t\tdie(\"invalid first branch %s\", branch1);\n+\n+\tbranch2 = argv[++i];\n+\tif (get_sha1_0(branch2, sha2) != 0)\n+\t\tdie(\"invalid second branch %s\", branch2);\n+\n+\tprintf(\"Merging %s with %s\\n\", branch1, branch2);\n+\n+\tstruct merge_result result;\n+\tstruct node *h1 = node_alloc(lookup_commit(sha1));\n+\tstruct node *h2 = node_alloc(lookup_commit(sha2));\n+\n+\tif (bases_count == 1) {\n+\t\tunsigned char shabase[20];\n+\t\tif (get_sha1_0(bases[0], shabase) != 0)\n+\t\t\tdie(\"invalid base commit %s\", bases[0]);\n+\t\tstruct node *ancestor = node_alloc(lookup_commit(shabase));\n+\t\tresult = merge(h1, h2, branch1, branch2, NULL, 0, ancestor);\n+\t} else {\n+\t\tstruct node_list *commits = NULL;\n+\t\tnode_list_insert(h1, &commits);\n+\t\tnode_list_insert(h2, &commits->next);\n+\t\tdebug(\"building graph...\\n\");\n+\t\tstruct graph *graph = graph_build(commits);\n+\t\tdebug(\"  building graph...\\n\");\n+\t\tresult = merge(h1, h2, branch1, branch2, graph, 0, NULL);\n+\t}\n+\treturn result.clean ? 0: 1;\n+}\n+\n+/*\n+vim: sw=8 noet\n+*/\ndiff --git a/path-list.c b/path-list.c\nnew file mode 100644\nindex 0000000..95395ab\n--- /dev/null\n+++ b/path-list.c\n@@ -0,0 +1,110 @@\n+#include <stdio.h>\n+#include \"cache.h\"\n+#include \"path-list.h\"\n+\n+/* if there is no exact match, point to the index where the entry could be\n+ * inserted */\n+static int get_entry_index(const struct path_list *container, const char *path,\n+\t\tint *exact_match)\n+{\n+\tint left = -1, right = container->nr;\n+\n+\twhile (left + 1 < right) {\n+\t\tint middle = (left + right) / 2;\n+\t\tint compare = strcmp(path, container->paths[middle]);\n+\t\tif (compare < 0)\n+\t\t\tright = middle;\n+\t\telse if (compare > 0)\n+\t\t\tleft = middle;\n+\t\telse {\n+\t\t\t*exact_match = 1;\n+\t\t\treturn middle;\n+\t\t}\n+\t}\n+\n+\t*exact_match = 0;\n+\treturn right;\n+}\n+\n+/* returns -1-index if already exists */\n+static int add_entry(struct path_list *container, const char *path)\n+{\n+\tint exact_match;\n+\tint index = get_entry_index(container, path, &exact_match);\n+\n+\tif (exact_match)\n+\t\treturn -1 - index;\n+\n+\tif (container->nr + 1 >= container->alloc) {\n+\t\tcontainer->alloc += 32;\n+\t\tcontainer->paths = realloc(container->paths,\n+\t\t\t\tcontainer->alloc * sizeof(char *));\n+\t}\n+\tif (index < container->nr)\n+\t\tmemmove(container->paths + index + 1,\n+\t\t\t\tcontainer->paths + index,\n+\t\t\t\t(container->nr - index) * sizeof(char *));\n+\tcontainer->paths[index] = strdup(path);\n+\tcontainer->nr++;\n+\n+\treturn index;\n+}\n+\n+char *path_list_insert(char *path, struct path_list *list)\n+{\n+\tint index = add_entry(list, path);\n+\n+\tif (index < 0)\n+\t\tindex = 1 - index;\n+\n+\treturn list->paths[index];\n+}\n+\n+int path_list_has_path(const struct path_list *list, const char *path)\n+{\n+\tint exact_match;\n+\tget_entry_index(list, path, &exact_match);\n+\treturn exact_match;\n+}\n+\n+/* in place */\n+void path_list_union_update(struct path_list *dst, const struct path_list *src)\n+{\n+\tchar **new_paths;\n+\tint i = 0, j = 0, nr = 0, alloc = dst->nr + dst->nr;\n+\n+\tnew_paths = xcalloc(sizeof(char *), alloc);\n+\n+\twhile (i < dst->nr || j < src->nr) {\n+\t\tchar **entry = new_paths + nr++;\n+\t\tif (i == dst->nr)\n+\t\t\t*entry = src->paths[j++];\n+\t\telse if (j == src->nr)\n+\t\t\t*entry = dst->paths[i++];\n+\t\telse {\n+\t\t\tint compare = strcmp(dst->paths[i], src->paths[j]);\n+\t\t\tif (compare > 0)\n+\t\t\t\t*entry = src->paths[j++];\n+\t\t\telse {\n+\t\t\t\t*entry = dst->paths[i++];\n+\t\t\t\tif (!compare)\n+\t\t\t\t\tfree(src->paths[j++]);\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tfree(dst->paths);\n+\tdst->paths = new_paths;\n+\tdst->nr = nr;\n+\tdst->alloc = alloc;\n+}\n+\n+void print_path_list(const char *text, const struct path_list *p)\n+{\n+\tint i;\n+\tif ( text )\n+\t\tprintf(\"%s\\n\", text);\n+\tfor (i = 0; i < p->nr; i++)\n+\t\tprintf(\"%s\\n\", p->paths[i]);\n+}\n+\ndiff --git a/path-list.h b/path-list.h\nnew file mode 100644\nindex 0000000..a12c7a4\n--- /dev/null\n+++ b/path-list.h\n@@ -0,0 +1,32 @@\n+#ifndef _PATH_LIST_H_\n+#define _PATH_LIST_H_\n+\n+struct path_list\n+{\n+    char **paths;\n+    unsigned int nr, alloc;\n+};\n+\n+#define for_each_path(p,list) for ( p = (list)->paths; p != (list)->paths + (list)->nr; p++ )\n+\n+void print_path_list(const char *text, const struct path_list *p);\n+\n+#define path_list_count(list) (list)->nr\n+\n+int path_list_has_path(const struct path_list *list, const char *path);\n+void path_list_union_update(struct path_list *dst, const struct path_list *src);\n+static inline void path_list_clear(struct path_list *list, int free_paths)\n+{\n+\tif (list->paths) {\n+\t\tint i;\n+\t\tif (free_paths)\n+\t\t\tfor (i = 0; i < list->nr; i++)\n+\t\t\t\tfree(list->paths[i]);\n+\t\tfree(list->paths);\n+\t}\n+\tlist->paths = NULL;\n+\tlist->nr = list->alloc = 0;\n+}\n+char *path_list_insert(char *path, struct path_list *list);\n+\n+#endif /* _PATH_LIST_H_ */\n-- \n1.4.1.rc1.g17dc\n"},{"id":"23115","messageId":"20060703184604.59801e4e.tihirvon@gmail.com","threadId":"4714","inReplyTo":"20060630002721.GA22618@steel.home","subject":"Re: [PATCH 1/4] merge-recursive in C","fromName":"Timo Hirvonen","fromEmail":"tihirvon@gmail.com","sentAt":"2006-07-03T15:46:04Z","receivedAt":"2006-07-03T15:46:04Z","isPatch":true,"sender":{"key":"tihirvon@gmail.com","avatar":null},"body":"fork0@t-online.de (Alex Riesen) wrote:\n\n> +/* in place */\n> +void path_list_union_update(struct path_list *dst, const struct path_list *src)\n> +{\n> +\tchar **new_paths;\n> +\tint i = 0, j = 0, nr = 0, alloc = dst->nr + dst->nr;\n\nIt should be alloc = dst->nr + src->nr.\n\n-- \nhttp://onion.dynserv.net/~timo/\n"},{"id":"23116","messageId":"Pine.LNX.4.63.0607031750310.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4714","inReplyTo":"20060703184604.59801e4e.tihirvon@gmail.com","subject":"Re: [PATCH 1/4] merge-recursive in C","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-07-03T15:54:44Z","receivedAt":"2006-07-03T15:54:44Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 3 Jul 2006, Timo Hirvonen wrote:\n\n> fork0@t-online.de (Alex Riesen) wrote:\n> \n> > +/* in place */\n> > +void path_list_union_update(struct path_list *dst, const struct path_list *src)\n> > +{\n> > +\tchar **new_paths;\n> > +\tint i = 0, j = 0, nr = 0, alloc = dst->nr + dst->nr;\n> \n> It should be alloc = dst->nr + src->nr.\n\nGood catch. Merci.\n\nCiao,\nDscho\n"}]}