{"thread":{"id":"4682","subject":"CFT: merge-recursive in C (updated)","startedAt":"2006-06-27T15:48:32Z","lastAt":"2006-06-30T00:27:13Z","messageCount":32,"participants":["Alex Riesen","Johannes Schindelin","Linus Torvalds","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"22673","messageId":"81b0412b0606270848v2253209aw52466de632ab25c1@mail.gmail.com","threadId":"4682","inReplyTo":null,"subject":"CFT: merge-recursive in C (updated)","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-06-27T15:48:32Z","receivedAt":"2006-06-27T15:48:32Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Following many useful suggestions I updated the patch a little:\n\n - use run_command\n (and hope that whatever libc on windows does the quoting correctly)\n - use diffcore api instead of running git-diff-tree\n - use a pipe to \"git-update-index --index-info\" instead of using command line\n\nThanks Junio for the careful explanations, Johannes for his example and Linus\nfor inspiration :)\n\nGood news is that it is faster: 6min vs 10min. Bad news is that it is still\nnot enough for me and it is only on Linux (Windows will be slower,\nstill testing),\nuses an awful lot of memory and CPU.\n\n---\n\nPath list optimization should be next (and I'll be glad if someone does this\nbefore me). Also graph algos have a greate optimization potential\n(intersection, all parents of a node, node_by_sha).\n\nSorry for attachment, still at work.\n\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 da5657e..04fac15 100755\n--- a/git-merge.sh\n+++ b/git-merge.sh\n@@ -10,7 +10,7 @@ USAGE='[-n] [--no-commit] [-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@@ -18,7 +18,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..7458930\n--- /dev/null\n+++ b/graph.c\n@@ -0,0 +1,346 @@\n+#include \n+#include \n+#include \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+static struct node_list *node_all_parents(struct node *node)\n+{\n+\tstruct node_list *parents = NULL, **set = &parents;\n+\tstruct node_list *stack = NULL;\n+\tnode_list_insert(node, &stack);\n+\twhile ( stack ) {\n+\t\tstruct node_list *el = node_list_shift(&stack);\n+\n+\t\tnode_list_insert(el->node, set);\n+\t\tset = &(*set)->next;\n+\n+\t\tstruct node_list *p = el->node->parents;\n+\t\twhile ( p ) {\n+\t\t\tif ( !node_list_find_node(p->node, parents) )\n+\t\t\t\tnode_list_insert(p->node, &stack);\n+\t\t\tp = p->next;\n+\t\t}\n+\t\tnode_list_free1(el, 0);\n+\t}\n+\treturn parents;\n+}\n+\n+// a & b. a and are invalid after the call,\n+// the result will contain all the common nodes\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+// setup an empty tree in repository and returns it\n+static struct tree *get_empty_tree()\n+{\n+\tstatic struct tree *tree = NULL;\n+\tif ( !tree ) {\n+\t\tchar *tmpindex = git_path(\"/merge-tmp-index\");\n+\t\tsetenv(INDEX_ENVIRONMENT, tmpindex, 1);\n+\t\tunlink(tmpindex);\n+\t\ttree = git_write_tree();\n+\t\tunlink(tmpindex);\n+\t\tif ( !tree )\n+\t\t\tdie(\"failed to setup an empty tree\");\n+\t}\n+\treturn tree;\n+}\n+\n+static struct node *addCommonRoot(struct graph *graph)\n+{\n+\tstruct node_list *roots = NULL;\n+\tstruct node_list *p;\n+\tunsigned b;\n+\tfor (b = 0; b < sizeof(graph->commits)/sizeof(graph->commits[0]); ++b) {\n+\t\tfor_each_node_list(p, graph->commits[b])\n+\t\t\tif ( p->node->parents_count )\n+\t\t\t\tnode_list_insert(p->node, &roots);\n+\t}\n+\tstruct node *super = node_alloc_virtual(get_empty_tree(), \"Root\");\n+\tfor_each_node_list(p, roots) {\n+\t\tstruct node_list *list = NULL;\n+\t\tnode_list_insert(super, &list);\n+\t\tnode_set_parents(p->node, list);\n+\t}\n+\tgraph_add_node(graph, super);\n+\treturn super;\n+}\n+\n+// getCommonAncestors: Find the common ancestors for commit1 and commit2\n+struct node_list *graph_common_ancestors(struct graph *graph,\n+\t\t\t\t\t struct node *commit1,\n+\t\t\t\t\t struct node *commit2)\n+{\n+\tstruct node_list *shared;\n+\tshared = node_list_intersect(node_all_parents(commit1),\n+\t\t\t\t node_all_parents(commit2));\n+\tif ( !shared )\n+\t\tnode_list_insert(addCommonRoot(graph), &shared);\n+\n+\t/*\n+\t for s in shared:\n+\t if len([c for c in s.children if c in shared]) == 0:\n+\t res.add(s)\n+\t return list(res)\n+\t */\n+\tstruct node_list *ca = NULL, **pca = &ca;\n+\tstruct node_list *s;\n+\tfor_each_node_list(s, shared) {\n+\t\tunsigned n = 0;\n+\t\tstruct node_list *c;\n+\t\tfor_each_node_list(c, s->node->children)\n+\t\t\tif ( node_list_find_node(c->node, shared) ) {\n+\t\t\t\t++n;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\tif ( n == 0 ) {\n+\t\t\tnode_list_insert(s->node, pca);\n+\t\t\tpca = &(*pca)->next;\n+\t\t}\n+\t}\n+\tnode_list_free(&shared, 0);\n+\treturn ca;\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+// vim: sw=8 noet\ndiff --git a/graph.h b/graph.h\nnew file mode 100644\nindex 0000000..2cdbd96\n--- /dev/null\n+++ b/graph.h\n@@ -0,0 +1,85 @@\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+// find the common ancestors for commit1 and commit2\n+struct node_list *graph_common_ancestors(struct graph *graph,\n+\t\t\t\t\t struct node *commit1,\n+\t\t\t\t\t struct node *commit2);\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..547150e\n--- /dev/null\n+++ b/merge-recursive.c\n@@ -0,0 +1,1563 @@\n+//\n+// Recursive Merge algorithm stolen from git-merge-recursive.py by\n+// Fredrik Kuivinen.\n+//\n+#include \n+#include \n+#include \n+#include \n+#include \n+#include \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 for_each_commit(p,list) for ( p = (list); p; p = p->next )\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+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;\n+static struct path_list *currentDirectorySet;\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+// 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+static int index_only = 0; // cacheOnly\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+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+\n+// The entry point to the merge code\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+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\tca = graph_common_ancestors(graph, h1, h2);\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 ( graph && (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 *path,\n+\t\t\t\t unsigned mode,\n+\t\t\t\t void *data);\n+\n+// git-ls-tree -r -t \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;\n+\t\tchar *path = xmalloc(baselen + entry.pathlen + 2);\n+\t\tmemcpy(path, base, baselen);\n+\t\tmemcpy(path + baselen, entry.path, entry.pathlen);\n+\t\tpath[baselen + entry.pathlen] = '\\0';\n+\n+\t\tswitch ( retval = fn(entry.sha1, path, entry.mode, data) ) {\n+\t\tcase READ_TREE_RECURSIVE:\n+\t\t\tbreak;\n+\t\tcase 0:\n+\t\t\tfree(path);\n+\t\t\tcontinue;\n+\t\tdefault:\n+\t\t\tfree(path);\n+\t\t\treturn retval;\n+\t\t}\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tpath[baselen + entry.pathlen] = '/';\n+\t\t\tpath[baselen + entry.pathlen + 1] = '\\0';\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+\t\t\tpath[baselen + entry.pathlen] = '\\0';\n+\t\t\tif (retval) {\n+\t\t\t\tfree(path);\n+\t\t\t\treturn retval;\n+\t\t\t}\n+\t\t}\n+\t\tfree(path);\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 *path_,\n+\t\t\t unsigned mode,\n+\t\t\t void *data_)\n+{\n+\tstruct files_and_dirs *data = data_;\n+\tchar *path = strdup(path_);\n+\n+\tif (S_ISDIR(mode)) {\n+\t\tpath_list_insert(path, data->dirs);\n+\t\tdata->dirs = &(*data->dirs)->next;\n+\t} else {\n+\t\tpath_list_insert(path, data->files);\n+\t\tdata->files = &(*data->files)->next;\n+\t}\n+\treturn READ_TREE_RECURSIVE;\n+}\n+\n+int getFilesAndDirs(struct tree *tree,\n+\t\t struct path_list **files,\n+\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+\tif ( read_tree_rt(tree, \"\", 0, save_files_dirs, &data) != 0 )\n+\t\treturn 0;\n+\treturn path_list_count(*files) + path_list_count(*dirs);\n+}\n+\n+struct index_entry *index_entry_find(struct index_entry *ents, 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+struct index_entry *index_entry_get(struct index_entry **ents, 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+\tunsigned char *sha;\n+\tunsigned *mode;\n+};\n+\n+static int find_entry(const char *sha,\n+\t\t const char *path,\n+\t\t unsigned mode,\n+\t\t void *data_)\n+{\n+\tstruct find_entry *data = data_;\n+\tif ( strcmp(path, data->path) == 0 ) {\n+\t\tmemcpy(data->sha, sha, 20);\n+\t\t*data->mode = mode;\n+\t\treturn READ_TREE_FOUND;\n+\t}\n+\treturn READ_TREE_RECURSIVE;\n+}\n+\n+// Returns a CacheEntry object which doesn't have to correspond to\n+// a real cache entry in Git's index.\n+struct index_entry *index_entry_from_db(const char *path,\n+\t\t\t\t\tstruct tree *o,\n+\t\t\t\t\tstruct tree *a,\n+\t\t\t\t\tstruct tree *b)\n+{\n+\tstruct index_entry *e = index_entry_alloc(path);\n+\tstruct find_entry data;\n+\tdata.path = 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\t// fprintf(stderr, \"1: %s:%s not found\\n\",\n+\t\t// \tsha1_to_hex(o->object.sha1), path);\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\t// fprintf(stderr, \"2: %s:%s not found\\n\",\n+\t\t// \tsha1_to_hex(a->object.sha1), path);\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\t// fprintf(stderr, \"3: %s:%s not found\\n\",\n+\t\t// \tsha1_to_hex(b->object.sha1), path);\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+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+// 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+struct index_entry *unmergedCacheEntries()\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+\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\t// printf(\"unmerged %08o %s %c %s\\n\",mode,sha1_to_hex(sha),stage,path);\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+\treturn unmerged;\n+}\n+\n+struct rename_entry\n+{\n+\tstruct rename_entry *next;\n+\n+\tchar *src;\n+\tunsigned char src_sha[20];\n+\tunsigned src_mode;\n+\tstruct index_entry *src_entry;\n+\n+\tchar *dst;\n+\tunsigned char dst_sha[20];\n+\tunsigned dst_mode;\n+\tstruct index_entry *dst_entry;\n+\n+\tunsigned score;\n+\tunsigned processed:1;\n+};\n+\n+struct rename_entry *find_rename_bysrc(struct rename_entry *e,\n+\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+struct rename_entry *find_rename_bydst(struct rename_entry *e,\n+\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+void rename_entry_free(struct rename_entry *p)\n+{\n+\tfree(p->src);\n+\tfree(p->dst);\n+\tfree(p);\n+}\n+\n+void free_rename_entries(struct rename_entry **list)\n+{\n+\twhile ( *list ) {\n+\t\tstruct rename_entry *next = (*list)->next;\n+\t\trename_entry_free(*list);\n+\t\t*list = next;\n+\t}\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+struct rename_entry *getRenames(struct tree *tree,\n+\t\t\t\tstruct tree *oTree,\n+\t\t\t\tstruct tree *aTree,\n+\t\t\t\tstruct tree *bTree,\n+\t\t\t\tstruct index_entry **entries)\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\tre = xmalloc(sizeof(*re));\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\tre->src = strdup(pair->one->path);\n+\t\tre->src_mode = pair->one->mode;\n+\t\tmemcpy(re->dst_sha, pair->two->sha1, 20);\n+\t\tre->dst = strdup(pair->two->path);\n+\t\tre->dst_mode = pair->two->mode;\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+\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+int setIndexStages(FILE *fp,\n+\t\t const char *path,\n+\t\t unsigned char *osha, unsigned omode,\n+\t\t unsigned char *asha, unsigned amode,\n+\t\t unsigned char *bsha, unsigned bmode,\n+\t\t int clear /* =True */)\n+{\n+\tif ( !fp )\n+\t\treturn -1;\n+\tif ( clear ) {\n+\t\tfprintf(fp, \"0 %s\\t%s\", sha1_to_hex(null_sha1), path);\n+\t\tfputc('\\0', fp);\n+\t}\n+\tif ( omode ) {\n+\t\tfprintf(fp, \"0%o %s 1\\t%s\", omode, sha1_to_hex(osha), path);\n+\t\tfputc('\\0', fp);\n+\t}\n+\tif ( amode ) {\n+\t\tfprintf(fp, \"0%o %s 2\\t%s\", amode, sha1_to_hex(asha), path);\n+\t\tfputc('\\0', fp);\n+\t}\n+\tif ( bmode ) {\n+\t\tfprintf(fp, \"0%o %s 3\\t%s\", bmode, sha1_to_hex(bsha), path);\n+\t\tfputc('\\0', fp);\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+int removeFile(FILE *fp, int clean, const char *path)\n+{\n+\tint updateCache = index_only || clean;\n+\tint updateWd = !index_only;\n+\n+\tif ( updateCache ) {\n+\t\tif ( !fp )\n+\t\t\treturn -1;\n+\t\tfprintf(fp, \"0 %s\\t%s\", sha1_to_hex(null_sha1), path);\n+\t\tfputc('\\0', fp);\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+char *uniquePath(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, ¤tFileSet);\n+\treturn newpath;\n+}\n+\n+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+void updateFileExt(FILE *fp,\n+\t\t const unsigned char *sha,\n+\t\t unsigned mode,\n+\t\t const char *path,\n+\t\t int updateCache,\n+\t\t 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\t// XXX just always use \"git update-index --index-info\"?\n+\t\tfprintf(fp, \"%06o %s\\t%s\", mode, sha1_to_hex(sha), path);\n+\t\tfputc('\\0', fp);\n+\t}\n+}\n+\n+void updateFile(FILE *fp,\n+\t\tint clean,\n+\t\tconst unsigned char *sha,\n+\t\tunsigned mode,\n+\t\tconst char *path)\n+{\n+\tupdateFileExt(fp, sha, mode, path, 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+\tunsigned merge:1;\n+};\n+\n+static char *git_unpack_file(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+struct merge_file_info\n+mergeFile(const char *oPath, unsigned char *oSha, unsigned oMode,\n+\t const char *aPath, unsigned char *aSha, unsigned aMode,\n+\t const char *bPath, unsigned char *bSha, unsigned bMode,\n+\t const char *branch1Name, 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 *fp = popen(cmd, \"r\");\n+\t\t\tif ( !fp )\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, fp, &ch) )\n+\t\t\t\tdie(\"invalid output from git-hash-object\");\n+\t\t\tpclose(fp);\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 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+int processRenames(struct rename_entry *renamesA,\n+\t\t struct rename_entry *renamesB,\n+\t\t const char *branchNameA,\n+\t\t const char *branchNameB)\n+{\n+\tint cleanMerge = 1;\n+\t// printf(\"process renames %s:%s -> %s:%s\\n\",\n+\t//\t branchNameA, renamesA ? renamesA->src: \"(none)\",\n+\t//\t branchNameB, renamesB ? renamesB->dst: \"(none)\");\n+\n+\tstruct path_list *srcNames = NULL;\n+\tconst struct rename_entry *sre;\n+\n+\tfor (sre = renamesA; sre; sre = sre->next)\n+\t\tif (!path_list_has_path(srcNames, sre->src))\n+\t\t\tpath_list_insert(sre->src, &srcNames);\n+\tfor (sre = renamesB; sre; sre = sre->next)\n+\t\tif (!path_list_has_path(srcNames, sre->src))\n+\t\t\tpath_list_insert(sre->src, &srcNames);\n+\n+\tFILE *fp = git_update_index_pipe();\n+\tstruct path_list *src;\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->path);\n+\t\tren2 = find_rename_bysrc(renamesB, src->path);\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->path, ren1->dst, branchName1,\n+\t\t\t\t src->path, 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 = uniquePath(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\tremoveFile(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 = uniquePath(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\tremoveFile(fp, 0, ren2->dst);\n+\t\t\t\t}\n+\t\t\t\tsetIndexStages(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\tsetIndexStages(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\tremoveFile(fp, 1, ren1->src);\n+\t\t\t\tstruct merge_file_info mfi;\n+\t\t\t\tmfi = mergeFile(ren1->src, ren1->src_sha, ren1->src_mode,\n+\t\t\t\t\t\tren1->dst, ren1->dst_sha, ren1->dst_mode,\n+\t\t\t\t\t\tren2->dst, ren2->dst_sha, ren2->dst_mode,\n+\t\t\t\t\t\tbranchName1, branchName2);\n+\t\t\t\tif ( mfi.merge || !mfi.clean )\n+\t\t\t\t\toutput(\"Renaming %s->%s\", src->path, 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\tsetIndexStages(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\tupdateFile(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\tremoveFile(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 = uniquePath(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\tremoveFile(fp, 0, ren1->dst);\n+\t\t\t\tupdateFile(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\tupdateFile(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 = uniquePath(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\tupdateFile(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 = uniquePath(ren1->dst, branchName1);\n+\t\t\t\tchar *newPath2 = uniquePath(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\tremoveFile(fp, 0, ren1->dst);\n+\t\t\t\tupdateFile(fp, 0, ren1->dst_sha, ren1->dst_mode, newPath1);\n+\t\t\t\tupdateFile(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 = mergeFile(oname, osha, omode,\n+\t\t\t\t\t\taname, asha, amode,\n+\t\t\t\t\t\tbname, bsha, bmode,\n+\t\t\t\t\t\taBranch, 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\tsetIndexStages(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\tupdateFile(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+\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+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+// Per entry merge function\n+// ------------------------\n+// Merge one cache entry.\n+int processEntry(struct index_entry *entry,\n+\t\t const char *branch1Name,\n+\t\t const char *branch2Name)\n+{\n+\t// printf(\"processing entry, clean cache: %s\\n\", index_only ? \"yes\": \"no\");\n+\t// print_index_entry(\"\\tpath: \", entry);\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+\tFILE *fp = git_update_index_pipe();\n+\n+\tif ( oSha && (!aSha || !bSha) ) {\n+\t\t//\n+\t\t// Case A: Deleted in one\n+\t\t//\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 unchanged in the other\n+\t\t\tif ( aSha )\n+\t\t\t\toutput(\"Removing %s\", path);\n+\t\t\tremoveFile(fp, 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\tupdateFile(fp, 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\tupdateFile(fp, 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//\n+\t\t// Case B: Added in one.\n+\t\t//\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 = uniquePath(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\tremoveFile(fp, 0, path);\n+\t\t\tupdateFile(fp, 0, sha, mode, newPath);\n+\t\t} else {\n+\t\t\toutput(\"Adding %s\", path);\n+\t\t\tupdateFile(fp, 1, sha, mode, path);\n+\t\t}\n+\t} else if ( !oSha && aSha && bSha ) {\n+\t\t//\n+\t\t// Case C: Added in both (check for same permissions).\n+\t\t//\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\tupdateFile(fp, 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 = uniquePath(path, branch1Name);\n+\t\t\tconst char *newPath2 = uniquePath(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\tremoveFile(fp, 0, path);\n+\t\t\tupdateFile(fp, 0, aSha, aMode, newPath1);\n+\t\t\tupdateFile(fp, 0, bSha, bMode, newPath2);\n+\t\t}\n+\n+\t} else if ( oSha && aSha && bSha ) {\n+\t\t//\n+\t\t// case D: Modified in both, but differently.\n+\t\t//\n+\t\toutput(\"Auto-merging %s\\n\", path);\n+\t\tstruct merge_file_info mfi;\n+\t\tmfi = mergeFile(path, oSha, oMode,\n+\t\t\t\tpath, aSha, aMode,\n+\t\t\t\tpath, bSha, bMode,\n+\t\t\t\tbranch1Name, branch2Name);\n+\n+\t\tif ( mfi.clean )\n+\t\t\tupdateFile(fp, 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\tupdateFile(fp, 0, mfi.sha, mfi.mode, path);\n+\t\t\telse\n+\t\t\t\tupdateFileExt(fp, mfi.sha, mfi.mode, path,\n+\t\t\t\t\t 0 /* updateCache */, 1 /* updateWd */);\n+\t\t}\n+\t} else\n+\t\tdie(\"Fatal merge failure, shouldn't happen.\");\n+\n+\tif (pclose(fp))\n+\t\tdie(\"updating entry failed in git update-index\");\n+\treturn cleanMerge;\n+}\n+\n+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+\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+\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 *filesM = NULL, *dirsM = NULL;\n+\n+\t\tgetFilesAndDirs(head, ¤tFileSet, ¤tDirectorySet);\n+\t\tgetFilesAndDirs(merge, &filesM, &dirsM);\n+\n+\t\tpath_list_union_update(¤tFileSet, filesM);\n+\t\tpath_list_union_update(¤tDirectorySet, dirsM);\n+\n+\t\tstruct index_entry *entries = unmergedCacheEntries();\n+\t\tstruct rename_entry *renamesHead, *renamesMerge;\n+\t\trenamesHead = getRenames(head, common, head, merge, &entries);\n+\t\trenamesMerge = getRenames(merge, common, head, merge, &entries);\n+\t\tresult.clean = processRenames(renamesHead, renamesMerge,\n+\t\t\t\t\t branch1Name, branch2Name);\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 ( !processEntry(e, branch1Name, branch2Name) )\n+\t\t\t\tresult.clean = 0;\n+\t\t\tif ( result.clean || index_only )\n+\t\t\t\tresult.tree = git_write_tree();\n+\t\t\telse\n+\t\t\t\tresult.tree = NULL;\n+\t\t}\n+\t\tfree_rename_entries(&renamesMerge);\n+\t\tfree_rename_entries(&renamesHead);\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+\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 ... -- ...\\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) /* \"--\" \"\" \"\" */\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\tstruct graph *graph = graph_build(commits);\n+\t\tresult = merge(h1, h2, branch1, branch2, graph, 0, NULL);\n+\t}\n+\treturn result.clean ? 0: 1;\n+}\n+\n+// vim: sw=8 noet\ndiff --git a/path-list.c b/path-list.c\nnew file mode 100644\nindex 0000000..f969116\n--- /dev/null\n+++ b/path-list.c\n@@ -0,0 +1,68 @@\n+#include \n+#include \"cache.h\"\n+#include \"path-list.h\"\n+\n+static struct path_list *path_list_pool = NULL;\n+\n+struct path_list *path_list_insert(char *path, struct path_list **list)\n+{\n+ struct path_list *e;\n+ if ( path_list_pool ) {\n+ e = path_list_pool;\n+ path_list_pool = path_list_pool->next;\n+ } else\n+ e = xmalloc(sizeof(struct path_list));\n+ e->next = *list;\n+ e->path = path;\n+ *list = e;\n+ return e;\n+}\n+\n+void path_list_clear(struct path_list **list, int free_path)\n+{\n+ while ( *list ) {\n+ struct path_list *next = (*list)->next;\n+\tif (free_path)\n+\t free((*list)->path);\n+ (*list)->path = NULL;\n+ (*list)->next = path_list_pool;\n+ path_list_pool = *list;\n+ *list = next;\n+ }\n+}\n+\n+int path_list_count(const struct path_list *list)\n+{\n+ int n = 0;\n+ for ( ; list; list = list->next )\n+ ++n;\n+ return n;\n+}\n+\n+int path_list_has_path(const struct path_list *list, const char *path)\n+{\n+ for ( ; list; list = list->next )\n+ if ( strcmp(path, list->path) == 0 )\n+ return 1;\n+ return 0;\n+}\n+\n+// in place\n+void path_list_union_update(struct path_list **dst, const struct path_list *src)\n+{\n+ const struct path_list *i = src;\n+ while ( i ) {\n+ if ( !path_list_has_path(*dst, i->path) )\n+\t path_list_insert(i->path, dst);\n+\ti = i->next;\n+ }\n+}\n+\n+void print_path_list(const char *text, const struct path_list *p)\n+{\n+ if ( text )\n+ printf(\"%s\\n\", text);\n+ for ( ; p; p = p->next )\n+ printf(\"%s\\n\", p->path);\n+}\n+\ndiff --git a/path-list.h b/path-list.h\nnew file mode 100644\nindex 0000000..7e79f17\n--- /dev/null\n+++ b/path-list.h\n@@ -0,0 +1,31 @@\n+#ifndef _PATH_LIST_H_\n+#define _PATH_LIST_H_\n+\n+struct path_list\n+{\n+ struct path_list *next;\n+ char *path;\n+};\n+\n+#define for_each_path(p,list) for ( p = (list); p; p = p->next )\n+\n+void print_path_list(const char *text, const struct path_list *p);\n+\n+static inline struct path_list *path_list_shift(struct path_list **list)\n+{\n+ struct path_list *cur = *list;\n+ *list = cur->next;\n+ return cur;\n+}\n+\n+int path_list_count(const struct path_list *list);\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+void path_list_clear(struct path_list **list, int free_path);\n+static inline void path_list_free(struct path_list *list)\n+{\n+ path_list_clear(&list, 1);\n+}\n+struct path_list *path_list_insert(char *path, struct path_list **list);\n+\n+#endif /* _PATH_LIST_H_ */\n"},{"id":"22675","messageId":"Pine.LNX.4.63.0606271830210.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4682","inReplyTo":"81b0412b0606270848v2253209aw52466de632ab25c1@mail.gmail.com","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-27T16:42:51Z","receivedAt":"2006-06-27T16:42:51Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 27 Jun 2006, Alex Riesen wrote:\n\n> - use a pipe to \"git-update-index --index-info\" instead of using command \n> line\n\nIt might be an even better idea to call the cache functions directly. But \nin that case, you definitely want a function set_index_file() in \nenvironment.c, as well as a way to invalidate the active cache. Something \nlike\n\n\tif (active_cache) {\n\t\tfree(active_cache);\n\t\tactive_cache = NULL;\n\t\tactive_nr = active_alloc = 0;\n\t\tfree(active_cache_tree);\n\t\tactive_cache_tree = NULL;\n\t\tread_cache();\n\t}\n\n> Good news is that it is faster: 6min vs 10min. Bad news is that it is \n> still not enough for me and it is only on Linux (Windows will be slower, \n> still testing), uses an awful lot of memory and CPU.\n\nNo fear. I am sure we'll get there.\n\n> Path list optimization should be next (and I'll be glad if someone does \n> this before me).\n\nSee below.\n\n> Also graph algos have a greate optimization potential (intersection, all \n> parents of a node, node_by_sha).\n\nThe longer I look at it, the more I am convinced that this graph thing is \nnot necessary. I was hesitant at first that addCommonRoot() would not be \npossible, but nobody says we cannot override commit->parents.\n\nI have some commits in a private branch to split out get_merge_bases() \nfrom merge-base.c, so I'll try that next.\n\nBTW, before actually finishing this, we might want to do away with \ncapitalizedFunctionNames and 4-space indent.\n\nAnd here comes my patch (on top of what you sent) to avoid linked lists:\n\n merge-recursive.c | 61 ++++++++++++-------------\n path-list.c | 128 +++++++++++++++++++++++++++++++++++------------------\n path-list.h | 31 +++++++------\n 3 files changed, 129 insertions(+), 91 deletions(-)\n\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 547150e..b608a49 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -75,8 +75,8 @@ void print_index_entry(const char *text,\n }\n #endif\n \n-static struct path_list *currentFileSet;\n-static struct path_list *currentDirectorySet;\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@@ -297,8 +297,8 @@ static int read_tree_rt(struct tree *tre\n \n struct files_and_dirs\n {\n-\tstruct path_list **files;\n-\tstruct path_list **dirs;\n+\tstruct path_list *files;\n+\tstruct path_list *dirs;\n };\n \n static int save_files_dirs(const char *sha1,\n@@ -309,19 +309,16 @@ static int save_files_dirs(const char *s\n \tstruct files_and_dirs *data = data_;\n \tchar *path = strdup(path_);\n \n-\tif (S_ISDIR(mode)) {\n+\tif (S_ISDIR(mode))\n \t\tpath_list_insert(path, data->dirs);\n-\t\tdata->dirs = &(*data->dirs)->next;\n-\t} else {\n+\telse\n \t\tpath_list_insert(path, data->files);\n-\t\tdata->files = &(*data->files)->next;\n-\t}\n \treturn READ_TREE_RECURSIVE;\n }\n \n int getFilesAndDirs(struct tree *tree,\n-\t\t struct path_list **files,\n-\t\t struct path_list **dirs)\n+\t\t struct path_list *files,\n+\t\t struct path_list *dirs)\n {\n \tstruct files_and_dirs data;\n \tpath_list_clear(files, 1);\n@@ -330,7 +327,7 @@ int getFilesAndDirs(struct tree *tree,\n \tdata.dirs = dirs;\n \tif ( read_tree_rt(tree, \"\", 0, save_files_dirs, &data) != 0 )\n \t\treturn 0;\n-\treturn path_list_count(*files) + path_list_count(*dirs);\n+\treturn path_list_count(files) + path_list_count(dirs);\n }\n \n struct index_entry *index_entry_find(struct index_entry *ents, const char *path)\n@@ -714,8 +711,8 @@ char *uniquePath(const char *path, const\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+\twhile ( path_list_has_path(¤tFileSet, newpath) ||\n+\t\tpath_list_has_path(¤tDirectorySet, newpath) ||\n \t\tlstat(newpath, &st) == 0 ) {\n \t\tsprintf(p, \"_%d\", suffix++);\n \t}\n@@ -980,23 +977,21 @@ int processRenames(struct rename_entry *\n \t//\t branchNameA, renamesA ? renamesA->src: \"(none)\",\n \t//\t branchNameB, renamesB ? renamesB->dst: \"(none)\");\n \n-\tstruct path_list *srcNames = NULL;\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\tif (!path_list_has_path(srcNames, sre->src))\n-\t\t\tpath_list_insert(sre->src, &srcNames);\n+\t\tpath_list_insert(sre->src, &srcNames);\n \tfor (sre = renamesB; sre; sre = sre->next)\n-\t\tif (!path_list_has_path(srcNames, sre->src))\n-\t\t\tpath_list_insert(sre->src, &srcNames);\n+\t\tpath_list_insert(sre->src, &srcNames);\n \n \tFILE *fp = git_update_index_pipe();\n-\tstruct path_list *src;\n-\tfor_each_path(src,srcNames) {\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->path);\n-\t\tren2 = find_rename_bysrc(renamesB, src->path);\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@@ -1029,17 +1024,17 @@ int processRenames(struct rename_entry *\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->path, ren1->dst, branchName1,\n-\t\t\t\t src->path, ren2->dst, branchName2);\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\tif ( path_list_has_path(¤tDirectorySet, ren1->dst) ) {\n \t\t\t\t\tdstName1 = uniquePath(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\tremoveFile(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\tif ( path_list_has_path(¤tDirectorySet, ren2->dst) ) {\n \t\t\t\t\tdstName2 = uniquePath(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@@ -1063,7 +1058,7 @@ int processRenames(struct rename_entry *\n \t\t\t\t\t\tren2->dst, ren2->dst_sha, ren2->dst_mode,\n \t\t\t\t\t\tbranchName1, branchName2);\n \t\t\t\tif ( mfi.merge || !mfi.clean )\n-\t\t\t\t\toutput(\"Renaming %s->%s\", src->path, ren1->dst);\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@@ -1102,7 +1097,7 @@ int processRenames(struct rename_entry *\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\tif ( path_list_has_path(¤tDirectorySet, ren1->dst) ) {\n \t\t\t\tnewPath = uniquePath(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@@ -1283,7 +1278,7 @@ int processEntry(struct index_entry *ent\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\tif ( path_list_has_path(¤tDirectorySet, path) ) {\n \t\t\tcleanMerge = 0;\n \t\t\tconst char *newPath = uniquePath(path, addBranch);\n \t\t\toutput(\"CONFLICT (%s): There is a directory with name %s in %s. \"\n@@ -1379,13 +1374,13 @@ struct merge_tree_result merge_trees(str\n \tresult.tree = git_write_tree();\n \n \tif ( !result.tree ) {\n-\t\tstruct path_list *filesM = NULL, *dirsM = NULL;\n+\t\tstruct path_list filesM = {NULL, 0, 0}, dirsM = {NULL, 0, 0};\n \n \t\tgetFilesAndDirs(head, ¤tFileSet, ¤tDirectorySet);\n \t\tgetFilesAndDirs(merge, &filesM, &dirsM);\n \n-\t\tpath_list_union_update(¤tFileSet, filesM);\n-\t\tpath_list_union_update(¤tDirectorySet, dirsM);\n+\t\tpath_list_union_update(¤tFileSet, &filesM);\n+\t\tpath_list_union_update(¤tDirectorySet, &dirsM);\n \n \t\tstruct index_entry *entries = unmergedCacheEntries();\n \t\tstruct rename_entry *renamesHead, *renamesMerge;\ndiff --git a/path-list.c b/path-list.c\nindex f969116..fbfc103 100644\n--- a/path-list.c\n+++ b/path-list.c\n@@ -2,67 +2,109 @@ #include \n #include \"cache.h\"\n #include \"path-list.h\"\n \n-static struct path_list *path_list_pool = NULL;\n-\n-struct path_list *path_list_insert(char *path, struct path_list **list)\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- struct path_list *e;\n- if ( path_list_pool ) {\n- e = path_list_pool;\n- path_list_pool = path_list_pool->next;\n- } else\n- e = xmalloc(sizeof(struct path_list));\n- e->next = *list;\n- e->path = path;\n- *list = e;\n- return e;\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-void path_list_clear(struct path_list **list, int free_path)\n+/* returns -1-index if already exists */\n+static int add_entry(struct path_list *container, const char *path)\n {\n- while ( *list ) {\n- struct path_list *next = (*list)->next;\n-\tif (free_path)\n-\t free((*list)->path);\n- (*list)->path = NULL;\n- (*list)->next = path_list_pool;\n- path_list_pool = *list;\n- *list = next;\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-int path_list_count(const struct path_list *list)\n+char *path_list_insert(char *path, struct path_list *list)\n {\n- int n = 0;\n- for ( ; list; list = list->next )\n- ++n;\n- return 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- for ( ; list; list = list->next )\n- if ( strcmp(path, list->path) == 0 )\n- return 1;\n- return 0;\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+void path_list_union_update(struct path_list *dst, const struct path_list *src)\n {\n- const struct path_list *i = src;\n- while ( i ) {\n- if ( !path_list_has_path(*dst, i->path) )\n-\t path_list_insert(i->path, dst);\n-\ti = i->next;\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- if ( text )\n- printf(\"%s\\n\", text);\n- for ( ; p; p = p->next )\n- printf(\"%s\\n\", p->path);\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\nindex 7e79f17..a12c7a4 100644\n--- a/path-list.h\n+++ b/path-list.h\n@@ -3,29 +3,30 @@ #define _PATH_LIST_H_\n \n struct path_list\n {\n- struct path_list *next;\n- char *path;\n+ char **paths;\n+ unsigned int nr, alloc;\n };\n \n-#define for_each_path(p,list) for ( p = (list); p; p = p->next )\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-static inline struct path_list *path_list_shift(struct path_list **list)\n-{\n- struct path_list *cur = *list;\n- *list = cur->next;\n- return cur;\n-}\n+#define path_list_count(list) (list)->nr\n \n-int path_list_count(const struct path_list *list);\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-void path_list_clear(struct path_list **list, int free_path);\n-static inline void path_list_free(struct path_list *list)\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- path_list_clear(&list, 1);\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-struct path_list *path_list_insert(char *path, struct path_list **list);\n+char *path_list_insert(char *path, struct path_list *list);\n \n #endif /* _PATH_LIST_H_ */\n-- \n1.4.1.rc1.g3583-dirty\n"},{"id":"22682","messageId":"Pine.LNX.4.64.0606271116360.3927@g5.osdl.org","threadId":"4682","inReplyTo":"81b0412b0606270848v2253209aw52466de632ab25c1@mail.gmail.com","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-27T18:22:53Z","receivedAt":"2006-06-27T18:22:53Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 27 Jun 2006, Alex Riesen wrote:\n> \n> Good news is that it is faster: 6min vs 10min. Bad news is that it is still\n> not enough for me and it is only on Linux (Windows will be slower,\n> still testing),\n> uses an awful lot of memory and CPU.\n\nWhy do you do that horrible node_list, and the broken \"find common \nancestors?\"\n\nI can't follow your code, but it _looks_ like you are using some totally \nbroken graph walking function.\n\nFor git, the #1 optimization ALWAYS is to avoid walking the full commit \ngraph. That fundamentally _cannot_ scale. \n\nAlmost all of the \"hard work\" in git has been to try to read the minimum \namount of commits possible. That means that you absolutely must not just \nwalk the commits the \"obvious\" way, because that will always require you \nto build up the whole graph of the whole history, even if the common \nshared point is much closer.\n\nSo it look slike your \"graph.c\" is _fundamentally_ flawed.\n\nYou need to really read \"git-merge-base.c\" and understand it thoroughly. \nAnd then you need to throw away your graph.c, and use git-merge-base \ninstead.\n\n\t\t\tLinus\n"},{"id":"22683","messageId":"Pine.LNX.4.63.0606272043400.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4682","inReplyTo":"Pine.LNX.4.64.0606271116360.3927@g5.osdl.org","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-27T18:45:33Z","receivedAt":"2006-06-27T18:45:33Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 27 Jun 2006, Linus Torvalds wrote:\n\n> \n> \n> On Tue, 27 Jun 2006, Alex Riesen wrote:\n> > \n> > Good news is that it is faster: 6min vs 10min. Bad news is that it is still\n> > not enough for me and it is only on Linux (Windows will be slower,\n> > still testing),\n> > uses an awful lot of memory and CPU.\n> \n> Why do you do that horrible node_list, and the broken \"find common \n> ancestors?\"\n> \n> I can't follow your code, but it _looks_ like you are using some totally \n> broken graph walking function.\n\nNote that all Alex does was to translate the Python code to C. And in \nPython, this horrible graph thing was necessary, because git is not \nlibified yet.\n\nHOWEVER, I think it is a very good start. It _works_, albeit slow, and we \nhave test cases in place to make sure that our wonderful optimizations do \nnot break the tool.\n\nCiao,\nDscho\n"},{"id":"22684","messageId":"Pine.LNX.4.64.0606271205130.3927@g5.osdl.org","threadId":"4682","inReplyTo":"Pine.LNX.4.63.0606272043400.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-27T19:10:07Z","receivedAt":"2006-06-27T19:10:07Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 27 Jun 2006, Johannes Schindelin wrote:\n> \n> Note that all Alex does was to translate the Python code to C. And in \n> Python, this horrible graph thing was necessary, because git is not \n> libified yet.\n\nAhh. I thought the Python thing used an external program to do all graph \ncalculations.\n\nOne thing to look out for is (as Junio mentioned) that you do often want \nto merge things with externally controlled \"history\": either by having \nsomething like cherry-pick/rebase give fake history information, or by \nmanually forcing a certain merge-base (possibly even an empty tree) in \norder to generate a merge of two unrelated histories.\n\n> HOWEVER, I think it is a very good start. It _works_, albeit slow, and we \n> have test cases in place to make sure that our wonderful optimizations do \n> not break the tool.\n\nYeah, once it's all in C, it's going to be easier to move functionality \naround incrementally.\n\n\t\tLinus\n"},{"id":"22690","messageId":"20060627223249.GA8177@steel.home","threadId":"4682","inReplyTo":"Pine.LNX.4.63.0606271830210.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Alex Riesen","fromEmail":"fork0@t-online.de","sentAt":"2006-06-27T22:32:49Z","receivedAt":"2006-06-27T22:32:49Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Johannes Schindelin, Tue, Jun 27, 2006 18:42:51 +0200:\n> > - use a pipe to \"git-update-index --index-info\" instead of using command \n> > line\n> \n> It might be an even better idea to call the cache functions directly. But \n> in that case, you definitely want a function set_index_file() in \n> environment.c, as well as a way to invalidate the active cache. Something \n> like\n> \n> \tif (active_cache) {\n> \t\tfree(active_cache);\n> \t\tactive_cache = NULL;\n> \t\tactive_nr = active_alloc = 0;\n> \t\tfree(active_cache_tree);\n> \t\tactive_cache_tree = NULL;\n> \t\tread_cache();\n> \t}\n\nWe should check how will that work across recursive calls to merge\n(that long function in the middle of merge-recursive.c), but yes,\nit's certanly worth a try.\n\n> > Path list optimization should be next (and I'll be glad if someone does \n> > this before me).\n> \n> See below.\n> \n\nAah, thanks. Merged, tried, tested, left in patch.\nThe reallocs can cause some undesirable heap fragmentation, don't you\nthink?\n\n> > Also graph algos have a greate optimization potential (intersection, all \n> > parents of a node, node_by_sha).\n> \n> The longer I look at it, the more I am convinced that this graph thing is \n> not necessary. I was hesitant at first that addCommonRoot() would not be \n> possible, but nobody says we cannot override commit->parents.\n\nI tried to replace that code completely with a call to git-merge-base\n(it does not happen too often). So far it passed all tests.\n\n> I have some commits in a private branch to split out get_merge_bases() \n> from merge-base.c, so I'll try that next.\n\nThanks, that'd be nice.\n\n> BTW, before actually finishing this, we might want to do away with \n> capitalizedFunctionNames and 4-space indent.\n\n4-space indent should be gone by now, the names pending (they were\nimportant in initial debugging after conversion).\n\nAnd I almost forgot about using git-merge-tree instead of\n\"git-read-tree -m\". I hope this message will remind me tomorrow\nto think more about that.\n\nUpdated patch (your path_list and git-merge-base instead of graph's\ncommon ancestors):\n\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 fc25f8d..7d81122 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..fa2bfee\n--- /dev/null\n+++ b/graph.c\n@@ -0,0 +1,252 @@\n+#include \n+#include \n+#include \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+// a & b. a and are invalid after the call,\n+// the result will contain all the common nodes\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+// vim: sw=8 noet\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..9bbb426\n--- /dev/null\n+++ b/merge-recursive.c\n@@ -0,0 +1,1576 @@\n+//\n+// Recursive Merge algorithm stolen from git-merge-recursive.py by\n+// Fredrik Kuivinen.\n+//\n+#include \n+#include \n+#include \n+#include \n+#include \n+#include \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 for_each_commit(p,list) for ( p = (list); p; p = p->next )\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+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+// 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+static int index_only = 0; // cacheOnly\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+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+static int fget_sha1(unsigned char *sha, FILE *fp, int *ch);\n+\n+// The entry point to the merge code\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+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 *path,\n+\t\t\t\t unsigned mode,\n+\t\t\t\t void *data);\n+\n+// git-ls-tree -r -t \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;\n+\t\tchar *path = xmalloc(baselen + entry.pathlen + 2);\n+\t\tmemcpy(path, base, baselen);\n+\t\tmemcpy(path + baselen, entry.path, entry.pathlen);\n+\t\tpath[baselen + entry.pathlen] = '\\0';\n+\n+\t\tswitch ( retval = fn(entry.sha1, path, entry.mode, data) ) {\n+\t\tcase READ_TREE_RECURSIVE:\n+\t\t\tbreak;\n+\t\tcase 0:\n+\t\t\tfree(path);\n+\t\t\tcontinue;\n+\t\tdefault:\n+\t\t\tfree(path);\n+\t\t\treturn retval;\n+\t\t}\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tpath[baselen + entry.pathlen] = '/';\n+\t\t\tpath[baselen + entry.pathlen + 1] = '\\0';\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+\t\t\tpath[baselen + entry.pathlen] = '\\0';\n+\t\t\tif (retval) {\n+\t\t\t\tfree(path);\n+\t\t\t\treturn retval;\n+\t\t\t}\n+\t\t}\n+\t\tfree(path);\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 *path_,\n+\t\t\t unsigned mode,\n+\t\t\t void *data_)\n+{\n+\tstruct files_and_dirs *data = data_;\n+\tchar *path = strdup(path_);\n+\n+\tif (S_ISDIR(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+int getFilesAndDirs(struct tree *tree,\n+\t\t struct path_list *files,\n+\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+\tif ( read_tree_rt(tree, \"\", 0, save_files_dirs, &data) != 0 )\n+\t\treturn 0;\n+\treturn path_list_count(files) + path_list_count(dirs);\n+}\n+\n+struct index_entry *index_entry_find(struct index_entry *ents, 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+struct index_entry *index_entry_get(struct index_entry **ents, 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+\tunsigned char *sha;\n+\tunsigned *mode;\n+};\n+\n+static int find_entry(const char *sha,\n+\t\t const char *path,\n+\t\t unsigned mode,\n+\t\t void *data_)\n+{\n+\tstruct find_entry *data = data_;\n+\tif ( strcmp(path, data->path) == 0 ) {\n+\t\tmemcpy(data->sha, sha, 20);\n+\t\t*data->mode = mode;\n+\t\treturn READ_TREE_FOUND;\n+\t}\n+\treturn READ_TREE_RECURSIVE;\n+}\n+\n+// Returns a CacheEntry object which doesn't have to correspond to\n+// a real cache entry in Git's index.\n+struct index_entry *index_entry_from_db(const char *path,\n+\t\t\t\t\tstruct tree *o,\n+\t\t\t\t\tstruct tree *a,\n+\t\t\t\t\tstruct tree *b)\n+{\n+\tstruct index_entry *e = index_entry_alloc(path);\n+\tstruct find_entry data;\n+\tdata.path = 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\t// fprintf(stderr, \"1: %s:%s not found\\n\",\n+\t\t// \tsha1_to_hex(o->object.sha1), path);\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\t// fprintf(stderr, \"2: %s:%s not found\\n\",\n+\t\t// \tsha1_to_hex(a->object.sha1), path);\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\t// fprintf(stderr, \"3: %s:%s not found\\n\",\n+\t\t// \tsha1_to_hex(b->object.sha1), path);\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+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+// 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+struct index_entry *unmergedCacheEntries()\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+\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\t// printf(\"unmerged %08o %s %c %s\\n\",mode,sha1_to_hex(sha),stage,path);\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+\treturn unmerged;\n+}\n+\n+struct rename_entry\n+{\n+\tstruct rename_entry *next;\n+\n+\tchar *src;\n+\tunsigned char src_sha[20];\n+\tunsigned src_mode;\n+\tstruct index_entry *src_entry;\n+\n+\tchar *dst;\n+\tunsigned char dst_sha[20];\n+\tunsigned dst_mode;\n+\tstruct index_entry *dst_entry;\n+\n+\tunsigned score;\n+\tunsigned processed:1;\n+};\n+\n+struct rename_entry *find_rename_bysrc(struct rename_entry *e,\n+\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+struct rename_entry *find_rename_bydst(struct rename_entry *e,\n+\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+void rename_entry_free(struct rename_entry *p)\n+{\n+\tfree(p->src);\n+\tfree(p->dst);\n+\tfree(p);\n+}\n+\n+void free_rename_entries(struct rename_entry **list)\n+{\n+\twhile ( *list ) {\n+\t\tstruct rename_entry *next = (*list)->next;\n+\t\trename_entry_free(*list);\n+\t\t*list = next;\n+\t}\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+struct rename_entry *getRenames(struct tree *tree,\n+\t\t\t\tstruct tree *oTree,\n+\t\t\t\tstruct tree *aTree,\n+\t\t\t\tstruct tree *bTree,\n+\t\t\t\tstruct index_entry **entries)\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\tre = xmalloc(sizeof(*re));\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\tre->src = strdup(pair->one->path);\n+\t\tre->src_mode = pair->one->mode;\n+\t\tmemcpy(re->dst_sha, pair->two->sha1, 20);\n+\t\tre->dst = strdup(pair->two->path);\n+\t\tre->dst_mode = pair->two->mode;\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+\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+int setIndexStages(FILE *fp,\n+\t\t const char *path,\n+\t\t unsigned char *osha, unsigned omode,\n+\t\t unsigned char *asha, unsigned amode,\n+\t\t unsigned char *bsha, unsigned bmode,\n+\t\t int clear /* =True */)\n+{\n+\tif ( !fp )\n+\t\treturn -1;\n+\tif ( clear ) {\n+\t\tfprintf(fp, \"0 %s\\t%s\", sha1_to_hex(null_sha1), path);\n+\t\tfputc('\\0', fp);\n+\t}\n+\tif ( omode ) {\n+\t\tfprintf(fp, \"0%o %s 1\\t%s\", omode, sha1_to_hex(osha), path);\n+\t\tfputc('\\0', fp);\n+\t}\n+\tif ( amode ) {\n+\t\tfprintf(fp, \"0%o %s 2\\t%s\", amode, sha1_to_hex(asha), path);\n+\t\tfputc('\\0', fp);\n+\t}\n+\tif ( bmode ) {\n+\t\tfprintf(fp, \"0%o %s 3\\t%s\", bmode, sha1_to_hex(bsha), path);\n+\t\tfputc('\\0', fp);\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+int removeFile(FILE *fp, int clean, const char *path)\n+{\n+\tint updateCache = index_only || clean;\n+\tint updateWd = !index_only;\n+\n+\tif ( updateCache ) {\n+\t\tif ( !fp )\n+\t\t\treturn -1;\n+\t\tfprintf(fp, \"0 %s\\t%s\", sha1_to_hex(null_sha1), path);\n+\t\tfputc('\\0', fp);\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+char *uniquePath(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(¤tFileSet, newpath) ||\n+\t\tpath_list_has_path(¤tDirectorySet, newpath) ||\n+\t\tlstat(newpath, &st) == 0 ) {\n+\t\tsprintf(p, \"_%d\", suffix++);\n+\t}\n+\tpath_list_insert(newpath, ¤tFileSet);\n+\treturn newpath;\n+}\n+\n+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+void updateFileExt(FILE *fp,\n+\t\t const unsigned char *sha,\n+\t\t unsigned mode,\n+\t\t const char *path,\n+\t\t int updateCache,\n+\t\t 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\t// XXX just always use \"git update-index --index-info\"?\n+\t\tfprintf(fp, \"%06o %s\\t%s\", mode, sha1_to_hex(sha), path);\n+\t\tfputc('\\0', fp);\n+\t}\n+}\n+\n+void updateFile(FILE *fp,\n+\t\tint clean,\n+\t\tconst unsigned char *sha,\n+\t\tunsigned mode,\n+\t\tconst char *path)\n+{\n+\tupdateFileExt(fp, sha, mode, path, 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+\tunsigned merge:1;\n+};\n+\n+static char *git_unpack_file(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+struct merge_file_info\n+mergeFile(const char *oPath, unsigned char *oSha, unsigned oMode,\n+\t const char *aPath, unsigned char *aSha, unsigned aMode,\n+\t const char *bPath, unsigned char *bSha, unsigned bMode,\n+\t const char *branch1Name, 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 *fp = popen(cmd, \"r\");\n+\t\t\tif ( !fp )\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, fp, &ch) )\n+\t\t\t\tdie(\"invalid output from git-hash-object\");\n+\t\t\tpclose(fp);\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 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+int processRenames(struct rename_entry *renamesA,\n+\t\t struct rename_entry *renamesB,\n+\t\t const char *branchNameA,\n+\t\t const char *branchNameB)\n+{\n+\tint cleanMerge = 1;\n+\t// printf(\"process renames %s:%s -> %s:%s\\n\",\n+\t//\t branchNameA, renamesA ? renamesA->src: \"(none)\",\n+\t//\t branchNameB, renamesB ? renamesB->dst: \"(none)\");\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(¤tDirectorySet, ren1->dst) ) {\n+\t\t\t\t\tdstName1 = uniquePath(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\tremoveFile(fp, 0, ren1->dst);\n+\t\t\t\t}\n+\t\t\t\tif ( path_list_has_path(¤tDirectorySet, ren2->dst) ) {\n+\t\t\t\t\tdstName2 = uniquePath(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\tremoveFile(fp, 0, ren2->dst);\n+\t\t\t\t}\n+\t\t\t\tsetIndexStages(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\tsetIndexStages(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\tremoveFile(fp, 1, ren1->src);\n+\t\t\t\tstruct merge_file_info mfi;\n+\t\t\t\tmfi = mergeFile(ren1->src, ren1->src_sha, ren1->src_mode,\n+\t\t\t\t\t\tren1->dst, ren1->dst_sha, ren1->dst_mode,\n+\t\t\t\t\t\tren2->dst, ren2->dst_sha, ren2->dst_mode,\n+\t\t\t\t\t\tbranchName1, 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\tsetIndexStages(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\tupdateFile(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\tremoveFile(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(¤tDirectorySet, ren1->dst) ) {\n+\t\t\t\tnewPath = uniquePath(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\tremoveFile(fp, 0, ren1->dst);\n+\t\t\t\tupdateFile(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\tupdateFile(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 = uniquePath(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\tupdateFile(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 = uniquePath(ren1->dst, branchName1);\n+\t\t\t\tchar *newPath2 = uniquePath(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\tremoveFile(fp, 0, ren1->dst);\n+\t\t\t\tupdateFile(fp, 0, ren1->dst_sha, ren1->dst_mode, newPath1);\n+\t\t\t\tupdateFile(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 = mergeFile(oname, osha, omode,\n+\t\t\t\t\t\taname, asha, amode,\n+\t\t\t\t\t\tbname, bsha, bmode,\n+\t\t\t\t\t\taBranch, 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\tsetIndexStages(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\tupdateFile(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+\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+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+// Per entry merge function\n+// ------------------------\n+// Merge one cache entry.\n+int processEntry(struct index_entry *entry,\n+\t\t const char *branch1Name,\n+\t\t const char *branch2Name)\n+{\n+\t// printf(\"processing entry, clean cache: %s\\n\", index_only ? \"yes\": \"no\");\n+\t// print_index_entry(\"\\tpath: \", entry);\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+\tFILE *fp = git_update_index_pipe();\n+\n+\tif ( oSha && (!aSha || !bSha) ) {\n+\t\t//\n+\t\t// Case A: Deleted in one\n+\t\t//\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 unchanged in the other\n+\t\t\tif ( aSha )\n+\t\t\t\toutput(\"Removing %s\", path);\n+\t\t\tremoveFile(fp, 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\tupdateFile(fp, 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\tupdateFile(fp, 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//\n+\t\t// Case B: Added in one.\n+\t\t//\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(¤tDirectorySet, path) ) {\n+\t\t\tcleanMerge = 0;\n+\t\t\tconst char *newPath = uniquePath(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\tremoveFile(fp, 0, path);\n+\t\t\tupdateFile(fp, 0, sha, mode, newPath);\n+\t\t} else {\n+\t\t\toutput(\"Adding %s\", path);\n+\t\t\tupdateFile(fp, 1, sha, mode, path);\n+\t\t}\n+\t} else if ( !oSha && aSha && bSha ) {\n+\t\t//\n+\t\t// Case C: Added in both (check for same permissions).\n+\t\t//\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\tupdateFile(fp, 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 = uniquePath(path, branch1Name);\n+\t\t\tconst char *newPath2 = uniquePath(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\tremoveFile(fp, 0, path);\n+\t\t\tupdateFile(fp, 0, aSha, aMode, newPath1);\n+\t\t\tupdateFile(fp, 0, bSha, bMode, newPath2);\n+\t\t}\n+\n+\t} else if ( oSha && aSha && bSha ) {\n+\t\t//\n+\t\t// case D: Modified in both, but differently.\n+\t\t//\n+\t\toutput(\"Auto-merging %s\\n\", path);\n+\t\tstruct merge_file_info mfi;\n+\t\tmfi = mergeFile(path, oSha, oMode,\n+\t\t\t\tpath, aSha, aMode,\n+\t\t\t\tpath, bSha, bMode,\n+\t\t\t\tbranch1Name, branch2Name);\n+\n+\t\tif ( mfi.clean )\n+\t\t\tupdateFile(fp, 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\tupdateFile(fp, 0, mfi.sha, mfi.mode, path);\n+\t\t\telse\n+\t\t\t\tupdateFileExt(fp, mfi.sha, mfi.mode, path,\n+\t\t\t\t\t 0 /* updateCache */, 1 /* updateWd */);\n+\t\t}\n+\t} else\n+\t\tdie(\"Fatal merge failure, shouldn't happen.\");\n+\n+\tif (pclose(fp))\n+\t\tdie(\"updating entry failed in git update-index\");\n+\treturn cleanMerge;\n+}\n+\n+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+\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+\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 filesM = {NULL, 0, 0}, dirsM = {NULL, 0, 0};\n+\n+\t\tgetFilesAndDirs(head, ¤tFileSet, ¤tDirectorySet);\n+\t\tgetFilesAndDirs(merge, &filesM, &dirsM);\n+\n+\t\tpath_list_union_update(¤tFileSet, &filesM);\n+\t\tpath_list_union_update(¤tDirectorySet, &dirsM);\n+\n+\t\tstruct index_entry *entries = unmergedCacheEntries();\n+\t\tstruct rename_entry *renamesHead, *renamesMerge;\n+\t\trenamesHead = getRenames(head, common, head, merge, &entries);\n+\t\trenamesMerge = getRenames(merge, common, head, merge, &entries);\n+\t\tresult.clean = processRenames(renamesHead, renamesMerge,\n+\t\t\t\t\t branch1Name, branch2Name);\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 ( !processEntry(e, branch1Name, branch2Name) )\n+\t\t\t\tresult.clean = 0;\n+\t\t\tif ( result.clean || index_only )\n+\t\t\t\tresult.tree = git_write_tree();\n+\t\t\telse\n+\t\t\t\tresult.tree = NULL;\n+\t\t}\n+\t\tfree_rename_entries(&renamesMerge);\n+\t\tfree_rename_entries(&renamesHead);\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+\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 ... -- ...\\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) /* \"--\" \"\" \"\" */\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\tstruct graph *graph = graph_build(commits);\n+\t\tresult = merge(h1, h2, branch1, branch2, graph, 0, NULL);\n+\t}\n+\treturn result.clean ? 0: 1;\n+}\n+\n+// vim: sw=8 noet\ndiff --git a/path-list.c b/path-list.c\nnew file mode 100644\nindex 0000000..fbfc103\n--- /dev/null\n+++ b/path-list.c\n@@ -0,0 +1,110 @@\n+#include \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"},{"id":"22691","messageId":"20060627223632.GB8177@steel.home","threadId":"4682","inReplyTo":"Pine.LNX.4.64.0606271205130.3927@g5.osdl.org","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Alex Riesen","fromEmail":"fork0@t-online.de","sentAt":"2006-06-27T22:36:32Z","receivedAt":"2006-06-27T22:36:32Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Linus Torvalds, Tue, Jun 27, 2006 21:10:07 +0200:\n> > HOWEVER, I think it is a very good start. It _works_, albeit slow, and we \n> > have test cases in place to make sure that our wonderful optimizations do \n> > not break the tool.\n> \n> Yeah, once it's all in C, it's going to be easier to move functionality \n> around incrementally.\n> \n\nThat's why I started it: it'll eventually become so easy to move\nfunctionality around, that it will move all by itself and optimizes\nin a perfect code.\n"},{"id":"22786","messageId":"81b0412b0606280234x7d07fbbck7887b5214d98bf91@mail.gmail.com","threadId":"4682","inReplyTo":"20060627223249.GA8177@steel.home","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-06-28T09:34:23Z","receivedAt":"2006-06-28T09:34:23Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 6/28/06, Alex Riesen wrote:\n> Johannes Schindelin, Tue, Jun 27, 2006 18:42:51 +0200:\n> > > - use a pipe to \"git-update-index --index-info\" instead of using command\n> > > line\n\n...and to take it a step further, a patch (0002) to avoid too many calls to\ngit-write-tree and to git-update-index. Brought merge times on my test\nmonster (~25k files) down to 2min 30sec (from something around 11 min).\nThe 0001 patch is just C++ comments.\n\n\nFrom 36147880afad3a2d53f6474bec069e29d82a74a8 Mon Sep 17 00:00:00 2001\nFrom: Riesen \nDate: Wed, 28 Jun 2006 09:46:47 +0200\nSubject: update comments and remove C++ //...\n---\n graph.c | 14 ++++--\n merge-recursive.c | 131 +++++++++++++++++++++++++----------------------------\n path-list.c | 2 -\n 3 files changed, 72 insertions(+), 75 deletions(-)\n\ndiff --git a/graph.c b/graph.c\nindex fa2bfee..1a28302 100644\n--- a/graph.c\n+++ b/graph.c\n@@ -5,7 +5,7 @@ #include \"cache.h\"\n #include \"commit.h\"\n #include \"graph.h\"\n \n-// does not belong here\n+/* does not belong here */\n struct tree *git_write_tree()\n {\n #if 0\n@@ -189,8 +189,10 @@ struct node_list *node_list_find_node(co\n \treturn (struct node_list*)p;\n }\n \n-// a & b. a and are invalid after the call,\n-// the result will contain all the common nodes\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@@ -214,7 +216,7 @@ struct node *graph_add_node(struct graph\n {\n \tstruct node_list **bucket;\n \tif ( node->virtual )\n-\t\t// virtual nodes hashed by lowest byte of virtual_id\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@@ -249,4 +251,6 @@ void node_list_print(const char *msg, co\n }\n #endif\n \n-// vim: sw=8 noet\n+/*\n+vim: sw=8 noet\n+*/\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 9bbb426..ba5b024 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -1,7 +1,7 @@\n-//\n-// Recursive Merge algorithm stolen from git-merge-recursive.py by\n-// Fredrik Kuivinen.\n-//\n+/*\n+ * Recursive Merge algorithm stolen from git-merge-recursive.py by\n+ * Fredrik Kuivinen.\n+ */\n #include \n #include \n #include \n@@ -47,7 +47,7 @@ struct index_entry\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+\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@@ -102,14 +102,16 @@ static void setup_index(int temp)\n \tsetenv(\"GIT_INDEX_FILE\", idx, 1);\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-static int index_only = 0; // cacheOnly\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@@ -157,10 +159,10 @@ struct merge_tree_result merge_trees(str\n \n static int fget_sha1(unsigned char *sha, FILE *fp, int *ch);\n \n-// The entry point to the merge code\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+ * 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@@ -262,7 +264,7 @@ typedef int (*read_tree_rt_fn_t)(const c\n \t\t\t\t unsigned mode,\n \t\t\t\t void *data);\n \n-// git-ls-tree -r -t \n+/* git-ls-tree -r -t */\n static int read_tree_rt(struct tree *tree,\n \t\t\tconst char *base,\n \t\t\tint baselen,\n@@ -391,8 +393,10 @@ static int find_entry(const char *sha,\n \treturn READ_TREE_RECURSIVE;\n }\n \n-// Returns a CacheEntry object which doesn't have to correspond to\n-// a real cache entry in Git's index.\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 struct index_entry *index_entry_from_db(const char *path,\n \t\t\t\t\tstruct tree *o,\n \t\t\t\t\tstruct tree *a,\n@@ -404,24 +408,18 @@ struct index_entry *index_entry_from_db(\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\t// fprintf(stderr, \"1: %s:%s not found\\n\",\n-\t\t// \tsha1_to_hex(o->object.sha1), path);\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\t// fprintf(stderr, \"2: %s:%s not found\\n\",\n-\t\t// \tsha1_to_hex(a->object.sha1), path);\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\t// fprintf(stderr, \"3: %s:%s not found\\n\",\n-\t\t// \tsha1_to_hex(b->object.sha1), path);\n \t\tmemcpy(e->stages[3].sha, null_sha1, 20);\n \t\te->stages[3].mode = 0;\n \t}\n@@ -469,8 +467,11 @@ static int fget_sha1(unsigned char *sha,\n \t\treturn -1;\n \treturn 0;\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+/*\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 struct index_entry *unmergedCacheEntries()\n {\n \tstruct index_entry *unmerged = NULL;\n@@ -484,17 +485,17 @@ struct index_entry *unmergedCacheEntries\n \t\tchar stage = '0';\n \t\tchar path[PATH_MAX];\n \t\tint p;\n-\t\t// mode\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\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\t/* stage */\n \t\tif ( (ch = fgetc(fp)) != EOF ) {\n \t\t\tstage = ch;\n \t\t\tif ( ch < '1' || ch > '3' )\n@@ -502,7 +503,7 @@ struct index_entry *unmergedCacheEntries\n \t\t}\n \t\tif ( (ch = fgetc(fp)) == EOF || '\\t' != ch )\n \t\t\tgoto wait_eol;\n-\t\t// path\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@@ -515,7 +516,6 @@ struct index_entry *unmergedCacheEntries\n \t\t}\n \t\tif ( ch )\n \t\t\tgoto wait_eol;\n-\t\t// printf(\"unmerged %08o %s %c %s\\n\",mode,sha1_to_hex(sha),stage,path);\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@@ -583,10 +583,12 @@ void free_rename_entries(struct rename_e\n \t}\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+ * 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 struct rename_entry *getRenames(struct tree *tree,\n \t\t\t\tstruct tree *oTree,\n \t\t\t\tstruct tree *aTree,\n@@ -831,7 +833,6 @@ void updateFileExt(FILE *fp,\n \t}\n \tif ( updateCache )\n \t{\n-\t\t// XXX just always use \"git update-index --index-info\"?\n \t\tfprintf(fp, \"%06o %s\\t%s\", mode, sha1_to_hex(sha), path);\n \t\tfputc('\\0', fp);\n \t}\n@@ -846,8 +847,8 @@ void updateFile(FILE *fp,\n \tupdateFileExt(fp, sha, mode, path, index_only || clean, !index_only);\n }\n \n-// Low level file merging, update and removal\n-// ------------------------------------------\n+/* Low level file merging, update and removal */\n+\n struct merge_file_info\n {\n \tunsigned char sha[20];\n@@ -991,9 +992,6 @@ int processRenames(struct rename_entry *\n \t\t const char *branchNameB)\n {\n \tint cleanMerge = 1;\n-\t// printf(\"process renames %s:%s -> %s:%s\\n\",\n-\t//\t branchNameA, renamesA ? renamesA->src: \"(none)\",\n-\t//\t branchNameB, renamesB ? renamesB->dst: \"(none)\");\n \n \tstruct path_list srcNames = {NULL, 0, 0};\n \tconst struct rename_entry *sre;\n@@ -1033,7 +1031,7 @@ int processRenames(struct rename_entry *\n \t\tren1->processed = 1;\n \n \t\tif ( ren2 ) {\n-\t\t\t// Renamed in 1 and renamed in 2\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@@ -1097,7 +1095,7 @@ int processRenames(struct rename_entry *\n \t\t\t\tupdateFile(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\t/* Renamed in 1, maybe changed in 2 */\n \t\t\tremoveFile(fp, 1, ren1->src);\n \n \t\t\tunsigned char srcShaOtherBranch[20], dstShaOtherBranch[20];\n@@ -1224,15 +1222,15 @@ static int sha_eq(const unsigned char *a\n \treturn a && b && memcmp(a, b, 20) == 0;\n }\n \n-// Per entry merge function\n-// ------------------------\n-// Merge one cache entry.\n+/* Per entry merge function */\n int processEntry(struct index_entry *entry,\n \t\t const char *branch1Name,\n \t\t const char *branch2Name)\n {\n-\t// printf(\"processing entry, clean cache: %s\\n\", index_only ? \"yes\": \"no\");\n-\t// print_index_entry(\"\\tpath: \", entry);\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@@ -1244,18 +1242,17 @@ int processEntry(struct index_entry *ent\n \tFILE *fp = git_update_index_pipe();\n \n \tif ( oSha && (!aSha || !bSha) ) {\n-\t\t//\n-\t\t// Case A: Deleted in one\n-\t\t//\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 unchanged in the other\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\tremoveFile(fp, 1, path);\n \t\t} else {\n-\t\t\t// Deleted in one and changed in the other\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@@ -1274,9 +1271,7 @@ int processEntry(struct index_entry *ent\n \n \t} else if ( (!oSha && aSha && !bSha) ||\n \t\t (!oSha && !aSha && bSha) ) {\n-\t\t//\n-\t\t// Case B: Added in one.\n-\t\t//\n+\t\t/* Case B: Added in one. */\n \t\tconst char *addBranch;\n \t\tconst char *otherBranch;\n \t\tunsigned mode;\n@@ -1309,9 +1304,7 @@ int processEntry(struct index_entry *ent\n \t\t\tupdateFile(fp, 1, sha, mode, path);\n \t\t}\n \t} else if ( !oSha && aSha && bSha ) {\n-\t\t//\n-\t\t// Case C: Added in both (check for same permissions).\n-\t\t//\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@@ -1321,7 +1314,7 @@ int processEntry(struct index_entry *ent\n \t\t\t\toutput(\"CONFLICT: adding with permission: %06o\", aMode);\n \t\t\t\tupdateFile(fp, 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\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@@ -1337,9 +1330,7 @@ int processEntry(struct index_entry *ent\n \t\t}\n \n \t} else if ( oSha && aSha && bSha ) {\n-\t\t//\n-\t\t// case D: Modified in both, but differently.\n-\t\t//\n+\t\t/* case D: Modified in both, but differently. */\n \t\toutput(\"Auto-merging %s\\n\", path);\n \t\tstruct merge_file_info mfi;\n \t\tmfi = mergeFile(path, oSha, oMode,\n@@ -1472,15 +1463,15 @@ struct graph *graph_build(struct node_li\n \t\t\tbreak;\n \t\tif (EOF == ch)\n \t\t\tbreak;\n-\t\t// a commit\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\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@@ -1573,4 +1564,6 @@ int main(int argc, char *argv[])\n \treturn result.clean ? 0: 1;\n }\n \n-// vim: sw=8 noet\n+/*\n+vim: sw=8 noet\n+*/\ndiff --git a/path-list.c b/path-list.c\nindex fbfc103..95395ab 100644\n--- a/path-list.c\n+++ b/path-list.c\n@@ -67,7 +67,7 @@ int path_list_has_path(const struct path\n \treturn exact_match;\n }\n \n-// in place\n+/* in place */\n void path_list_union_update(struct path_list *dst, const struct path_list *src)\n {\n \tchar **new_paths;\n-- \n1.4.1.rc1.g8b09-dirty\n\n\n\nFrom b2fbfc22526fb2a1f56ef56836b7412c53524e60 Mon Sep 17 00:00:00 2001\nFrom: Riesen \nDate: Wed, 28 Jun 2006 10:45:05 +0200\nSubject: fix processEntries to avoid multiple calls to write-tree and update-index\n---\n merge-recursive.c | 47 ++++++++++++++++++++++++++++++++++++-----------\n 1 files changed, 36 insertions(+), 11 deletions(-)\n\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex ba5b024..5b7ed51 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -19,6 +19,13 @@ #include \"run-command.h\"\n #include \"graph.h\"\n #include \"path-list.h\"\n \n+#define DEBUG\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 struct merge_result\n@@ -345,9 +352,14 @@ int getFilesAndDirs(struct tree *tree,\n \tpath_list_clear(dirs, 1);\n \tdata.files = files;\n \tdata.dirs = dirs;\n-\tif ( read_tree_rt(tree, \"\", 0, save_files_dirs, &data) != 0 )\n+\tdebug(\"getFilesAndDirs ...\\n\");\n+\tif ( read_tree_rt(tree, \"\", 0, save_files_dirs, &data) != 0 ) {\n+\t\tdebug(\"\\tgetFilesAndDirs done (0)\\n\");\n \t\treturn 0;\n-\treturn path_list_count(files) + path_list_count(dirs);\n+\t}\n+\tint n = path_list_count(files) + path_list_count(dirs);\n+\tdebug(\"\\tgetFilesAndDirs done (%d)\\n\", n);\n+\treturn n;\n }\n \n struct index_entry *index_entry_find(struct index_entry *ents, const char *path)\n@@ -478,6 +490,7 @@ struct index_entry *unmergedCacheEntries\n \tFILE *fp = popen(\"git-ls-files -z --unmerged\", \"r\");\n \tif ( !fp )\n \t\treturn NULL;\n+\tdebug(\"unmergedCacheEntries...\\n\");\n \tint ch;\n \twhile ( !feof(fp) ) {\n \t\tunsigned mode;\n@@ -524,6 +537,7 @@ struct index_entry *unmergedCacheEntries\n \t\twhile ( (ch = fgetc(fp)) != EOF && ch );\n \t}\n \tpclose(fp);\n+\tdebug(\"\\tunmergedCacheEntries done\\n\");\n \treturn unmerged;\n }\n \n@@ -595,6 +609,7 @@ struct rename_entry *getRenames(struct t\n \t\t\t\tstruct tree *bTree,\n \t\t\t\tstruct index_entry **entries)\n {\n+\tdebug(\"getRenames ...\\n\");\n \tstruct rename_entry *renames = NULL;\n \tstruct rename_entry **rptr = &renames;\n \tstruct diff_options opts;\n@@ -639,6 +654,7 @@ struct rename_entry *getRenames(struct t\n \t}\n \topts.output_format = DIFF_FORMAT_NO_OUTPUT;\n \tdiff_flush(&opts);\n+\tdebug(\"\\tgetRenames done\\n\");\n \treturn renames;\n }\n \n@@ -991,6 +1007,7 @@ int processRenames(struct rename_entry *\n \t\t const char *branchNameA,\n \t\t const char *branchNameB)\n {\n+\tdebug(\"processRenames...\\n\");\n \tint cleanMerge = 1;\n \n \tstruct path_list srcNames = {NULL, 0, 0};\n@@ -1207,6 +1224,7 @@ int processRenames(struct rename_entry *\n \tif (pclose(fp)) {\n \t\tdie(\"git update-index --index-info failed\");\n \t}\n+\tdebug(\"\\tprocessRenames done\\n\");\n \treturn cleanMerge;\n }\n \n@@ -1223,7 +1241,8 @@ static int sha_eq(const unsigned char *a\n }\n \n /* Per entry merge function */\n-int processEntry(struct index_entry *entry,\n+int processEntry(FILE *fp,\n+\t\t struct index_entry *entry,\n \t\t const char *branch1Name,\n \t\t const char *branch2Name)\n {\n@@ -1239,7 +1258,6 @@ int processEntry(struct index_entry *ent\n \tunsigned oMode = entry->stages[1].mode;\n \tunsigned aMode = entry->stages[2].mode;\n \tunsigned bMode = entry->stages[3].mode;\n-\tFILE *fp = git_update_index_pipe();\n \n \tif ( oSha && (!aSha || !bSha) ) {\n \t\t/* Case A: Deleted in one */\n@@ -1353,8 +1371,6 @@ int processEntry(struct index_entry *ent\n \t} else\n \t\tdie(\"Fatal merge failure, shouldn't happen.\");\n \n-\tif (pclose(fp))\n-\t\tdie(\"updating entry failed in git update-index\");\n \treturn cleanMerge;\n }\n \n@@ -1373,6 +1389,7 @@ struct merge_tree_result merge_trees(str\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@@ -1397,17 +1414,22 @@ struct merge_tree_result merge_trees(str\n \t\trenamesMerge = getRenames(merge, common, head, merge, &entries);\n \t\tresult.clean = processRenames(renamesHead, renamesMerge,\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 ( !processEntry(e, branch1Name, branch2Name) )\n+\t\t\tif ( !processEntry(fp, e, branch1Name, branch2Name) )\n \t\t\t\tresult.clean = 0;\n-\t\t\tif ( result.clean || index_only )\n-\t\t\t\tresult.tree = git_write_tree();\n-\t\t\telse\n-\t\t\t\tresult.tree = NULL;\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\\tprocessing entries done\\n\");\n \t\tfree_rename_entries(&renamesMerge);\n \t\tfree_rename_entries(&renamesHead);\n \t\tfree_index_entries(&entries);\n@@ -1419,6 +1441,7 @@ struct merge_tree_result merge_trees(str\n \t\t sha1_to_hex(result.tree->object.sha1));\n \t}\n \n+\tdebug(\"\\tmerge_trees done\\n\");\n \treturn result;\n }\n \n@@ -1558,7 +1581,9 @@ int main(int argc, char *argv[])\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(\"\\tbuilding graph...\\n\");\n \t\tresult = merge(h1, h2, branch1, branch2, graph, 0, NULL);\n \t}\n \treturn result.clean ? 0: 1;\n-- \n1.4.1.rc1.g8b09-dirty\n\n"},{"id":"22729","messageId":"Pine.LNX.4.63.0606281202360.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4682","inReplyTo":"81b0412b0606280234x7d07fbbck7887b5214d98bf91@mail.gmail.com","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-28T10:04:13Z","receivedAt":"2006-06-28T10:04:13Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 28 Jun 2006, Alex Riesen wrote:\n\n> On 6/28/06, Alex Riesen wrote:\n> > Johannes Schindelin, Tue, Jun 27, 2006 18:42:51 +0200:\n> > > > - use a pipe to \"git-update-index --index-info\" instead of using command\n> > > > line\n> \n> ...and to take it a step further, a patch (0002) to avoid too many calls to\n> git-write-tree and to git-update-index.\n\n... and introduces a lot more lines doing debug output.\n\nHowever, the change is good, but I would not call it \"FILE *fp\". IMHO \n\"FILE *update_index_pipe\" would explain better what you do there.\n\nCiao,\nDscho\n"},{"id":"22737","messageId":"81b0412b0606280435t70ac9957jae2c4d1c10b7681d@mail.gmail.com","threadId":"4682","inReplyTo":"Pine.LNX.4.63.0606281202360.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-06-28T11:35:10Z","receivedAt":"2006-06-28T11:35:10Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 6/28/06, Johannes Schindelin wrote:\n> > > > > - use a pipe to \"git-update-index --index-info\" instead of using command\n> > > > > line\n> >\n> > ...and to take it a step further, a patch (0002) to avoid too many calls to\n> > git-write-tree and to git-update-index.\n>\n> ... and introduces a lot more lines doing debug output.\n\nwell, that's how I found out about what to fix. Was really impressed\nwhen saw the difference :)\nWhat stands out next is getRenames (to be renamed into get_renames),\na little profiling shows that the renames lists are the culprit this time too.\n\nI actually expected these problems, but decided to postpone the\noptimization for later: linked lists are comfortable to work with.\nI didn't had much time for this project, and the first commit is\ndated 7th June - it was a very slow progress.\n\n> However, the change is good, but I would not call it \"FILE *fp\". IMHO\n> \"FILE *update_index_pipe\" would explain better what you do there.\n\njust update_index would be enough. It can't possibly mean anything else,\nbeing FILE* in that context.\n\nBy the way, is it safe to use \"git-update-index --index-info\"?\nAFAICS it was designed for this kind of use, but the most\nvisible user of it (git-update-recursive.py) didn't use --index-info\nthis way! Was there any specific reasons?\n"},{"id":"22740","messageId":"Pine.LNX.4.63.0606281342290.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4682","inReplyTo":"81b0412b0606280435t70ac9957jae2c4d1c10b7681d@mail.gmail.com","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-28T12:55:49Z","receivedAt":"2006-06-28T12:55:49Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 28 Jun 2006, Alex Riesen wrote:\n\n> What stands out next is getRenames (to be renamed into get_renames), a \n> little profiling shows that the renames lists are the culprit this time \n> too.\n\nIn my attempts, the path_list did not contain paths, but structs \ncontaining a path and a void pointer. I think I will resurrect this idea \nfor the renames.\n\nCiao,\nDscho\n"},{"id":"22741","messageId":"81b0412b0606280727k2f4d5c26m5d37f2835821c93b@mail.gmail.com","threadId":"4682","inReplyTo":"Pine.LNX.4.63.0606281342290.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-06-28T14:27:01Z","receivedAt":"2006-06-28T14:27:01Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 6/28/06, Johannes Schindelin wrote:\n>\n> > What stands out next is getRenames (to be renamed into get_renames), a\n> > little profiling shows that the renames lists are the culprit this time\n> > too.\n>\n> In my attempts, the path_list did not contain paths, but structs\n> containing a path and a void pointer. I think I will resurrect this idea\n> for the renames.\n>\n\nWhat was the pointer for?\n"},{"id":"22744","messageId":"Pine.LNX.4.63.0606281707570.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4682","inReplyTo":"81b0412b0606280727k2f4d5c26m5d37f2835821c93b@mail.gmail.com","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-28T15:09:51Z","receivedAt":"2006-06-28T15:09:51Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 28 Jun 2006, Alex Riesen wrote:\n\n> On 6/28/06, Johannes Schindelin wrote:\n> > \n> > > What stands out next is getRenames (to be renamed into get_renames), a\n> > > little profiling shows that the renames lists are the culprit this time\n> > > too.\n> > \n> > In my attempts, the path_list did not contain paths, but structs\n> > containing a path and a void pointer. I think I will resurrect this idea\n> > for the renames.\n> > \n> \n> What was the pointer for?\n\nWe want to emulate the set with a sorted list. The pointer is for the \npayload.\n\nCiao,\nDscho\n"},{"id":"22760","messageId":"20060629002547.GA27507@steel.home","threadId":"4682","inReplyTo":"81b0412b0606280234x7d07fbbck7887b5214d98bf91@mail.gmail.com","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Alex Riesen","fromEmail":"fork0@t-online.de","sentAt":"2006-06-29T00:25:47Z","receivedAt":"2006-06-29T00:25:47Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Alex Riesen, Wed, Jun 28, 2006 11:34:23 +0200:\n> >> > - use a pipe to \"git-update-index --index-info\" instead of\n> >> > using command line\n> \n> ...and to take it a step further, a patch (0002) to avoid too many calls to\n> git-write-tree and to git-update-index. Brought merge times on my test\n> monster (~25k files) down to 2min 30sec (from something around 11 min).\n\nthis broke t6022-merge-rename.sh (the second test). It produces an\nindex with this:\n\n.../t/trash$ git-diff-index white\n:100644 100644 2d603156dc5bdf6295c789cac08e3c9942a0b82a 0000000000000000000000000000000000000000 M B\n:100644 100644 ba41fb96393979b22691106b06bf5231eab57b85 0000000000000000000000000000000000000000 M N\n\nwhereas git-merge-recursive (and the previous version, without pipe):\n\n.../t/trash$ git-diff-index white\n:100644 100644 2d603156dc5bdf6295c789cac08e3c9942a0b82a 0000000000000000000000000000000000000000 M B\n\nI can see that \"git update-index --add\" is somehow different from a\npipe to \"git update-index --index-info\", but not very clear. Does this\n\"zero-sha1\" mean that the file \"N\" is not in the index?\n"},{"id":"22766","messageId":"7vzmfwy97w.fsf@assigned-by-dhcp.cox.net","threadId":"4682","inReplyTo":"20060629002547.GA27507@steel.home","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-29T02:41:23Z","receivedAt":"2006-06-29T02:41:23Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"fork0@t-online.de (Alex Riesen) writes:\n\n> this broke t6022-merge-rename.sh (the second test). It produces an\n> index with this:\n>\n> .../t/trash$ git-diff-index white\n> :100644 100644 2d603156dc5bdf6295c789cac08e3c9942a0b82a 0000000000000000000000000000000000000000 M B\n> :100644 100644 ba41fb96393979b22691106b06bf5231eab57b85 0000000000000000000000000000000000000000 M N\n>\n> whereas git-merge-recursive (and the previous version, without pipe):\n>\n> .../t/trash$ git-diff-index white\n> :100644 100644 2d603156dc5bdf6295c789cac08e3c9942a0b82a 0000000000000000000000000000000000000000 M B\n>\n> I can see that \"git update-index --add\" is somehow different from a\n> pipe to \"git update-index --index-info\", but not very clear. Does this\n> \"zero-sha1\" mean that the file \"N\" is not in the index?\n\nWhen diff-index and diff-files compare a tree entry or an index\nentry with a file in the working tree, they do not compute the\nblob hash value for the file in the working tree. 0{40} is used\non the RHS in such a case. When the working tree file matches\nthe corresponding index entry, then we know RHS matches what is\nin the index, so both sides have the blob hash value.\n"},{"id":"22780","messageId":"81b0412b0606290143g5a3a0f5atbda3f4250411e92e@mail.gmail.com","threadId":"4682","inReplyTo":"7vzmfwy97w.fsf@assigned-by-dhcp.cox.net","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-06-29T08:43:38Z","receivedAt":"2006-06-29T08:43:38Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"[cc list restored, I'm lost in the maze of git update-index, all cache\nchanging functions looking almost the same]\n\nOn 6/29/06, Junio C Hamano wrote:\n> > this broke t6022-merge-rename.sh (the second test). It produces an\n> > index with this:\n> >\n> > .../t/trash$ git-diff-index white\n> > :100644 100644 2d603156dc5bdf6295c789cac08e3c9942a0b82a 0000000000000000000000000000000000000000 M B\n> > :100644 100644 ba41fb96393979b22691106b06bf5231eab57b85 0000000000000000000000000000000000000000 M N\n> >\n> > whereas git-merge-recursive (and the previous version, without pipe):\n> >\n> > .../t/trash$ git-diff-index white\n> > :100644 100644 2d603156dc5bdf6295c789cac08e3c9942a0b82a 0000000000000000000000000000000000000000 M B\n> >\n> > I can see that \"git update-index --add\" is somehow different from a\n> > pipe to \"git update-index --index-info\", but not very clear. Does this\n> > \"zero-sha1\" mean that the file \"N\" is not in the index?\n>\n> When diff-index and diff-files compare a tree entry or an index\n> entry with a file in the working tree, they do not compute the\n> blob hash value for the file in the working tree. 0{40} is used\n> on the RHS in such a case. When the working tree file matches\n> the corresponding index entry, then we know RHS matches what is\n> in the index, so both sides have the blob hash value.\n\nOk. Am I correct in the assumption, that if the file in working tree has\nthe same SHA1 as LHS, than the next \"git-update-index --refresh\" will\nremove the entry from git-diff-index output?\nThis is what actually happens, if I do \"git-update-index --refresh\", so I\nsuspect that I have an SHA1 update gone missing somewhere.\n"},{"id":"22790","messageId":"Pine.LNX.4.63.0606291440510.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4682","inReplyTo":"20060627223249.GA8177@steel.home","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-29T13:16:01Z","receivedAt":"2006-06-29T13:16:01Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 28 Jun 2006, Alex Riesen wrote:\n\n> > > Path list optimization should be next (and I'll be glad if someone does \n> > > this before me).\n> > \n> > See below.\n> > \n> \n> Aah, thanks. Merged, tried, tested, left in patch.\n> The reallocs can cause some undesirable heap fragmentation, don't you\n> think?\n\nI do not care too deeply about the heap fragmentation there: it is just 4 \nbytes per file name. Besides, I chose an increment of 32 (probably I \nshould use alloc_nr() instead).\n\n> I tried to replace that code completely with a call to git-merge-base\n> (it does not happen too often). So far it passed all tests.\n> \n> > I have some commits in a private branch to split out get_merge_bases() \n> > from merge-base.c, so I'll try that next.\n> \n> Thanks, that'd be nice.\n\nWill reply with two patches.\n\n> > BTW, before actually finishing this, we might want to do away with \n> > capitalizedFunctionNames and 4-space indent.\n> \n> 4-space indent should be gone by now, the names pending (they were\n> important in initial debugging after conversion).\n\nOkay.\n\nCiao,\nDscho\n"},{"id":"22791","messageId":"Pine.LNX.4.63.0606291516150.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4682","inReplyTo":"20060627223249.GA8177@steel.home","subject":"[PATCH 1/2] refactor merge_bases() as preparation to libify merge-base","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-29T13:16:46Z","receivedAt":"2006-06-29T13:16:46Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\n---\n merge-base.c | 64 ++++++++++++++++++++++++++++++++++++++++++----------------\n 1 files changed, 46 insertions(+), 18 deletions(-)\n\ndiff --git a/merge-base.c b/merge-base.c\nindex 4856ca0..7d87c20 100644\n--- a/merge-base.c\n+++ b/merge-base.c\n@@ -124,8 +124,6 @@ static struct commit *interesting(struct\n * to contaminate D and E.\n */\n \n-static int show_all = 0;\n-\n static void mark_reachable_commits(struct commit_list *result,\n \t\t\t\t struct commit_list *list)\n {\n@@ -167,34 +165,33 @@ static void mark_reachable_commits(struc\n \t}\n }\n \n-static int merge_base(struct commit *rev1, struct commit *rev2)\n+struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2)\n {\n \tstruct commit_list *list = NULL;\n \tstruct commit_list *result = NULL;\n \tstruct commit_list *tmp = NULL;\n \n-\tif (rev1 == rev2) {\n-\t\tprintf(\"%s\\n\", sha1_to_hex(rev1->object.sha1));\n-\t\treturn 0;\n-\t}\n+\tif (rev1 == rev2)\n+\t\treturn commit_list_insert(rev1, &result);\n \n \tparse_commit(rev1);\n \tparse_commit(rev2);\n \n-\trev1->object.flags |= 1;\n-\trev2->object.flags |= 2;\n+\trev1->object.flags |= PARENT1;\n+\trev2->object.flags |= PARENT2;\n \tinsert_by_date(rev1, &list);\n \tinsert_by_date(rev2, &list);\n \n \twhile (interesting(list)) {\n \t\tstruct commit *commit = list->item;\n \t\tstruct commit_list *parents;\n-\t\tint flags = commit->object.flags & 7;\n+\t\tint flags = commit->object.flags\n+\t\t\t& (PARENT1 | PARENT2 | UNINTERESTING);\n \n \t\ttmp = list;\n \t\tlist = list->next;\n \t\tfree(tmp);\n-\t\tif (flags == 3) {\n+\t\tif (flags == (PARENT1 | PARENT2)) {\n \t\t\tinsert_by_date(commit, &result);\n \n \t\t\t/* Mark parents of a found merge uninteresting */\n@@ -213,21 +210,52 @@ static int merge_base(struct commit *rev\n \t}\n \n \tif (!result)\n-\t\treturn 1;\n+\t\treturn NULL;\n \n \tif (result->next && list)\n \t\tmark_reachable_commits(result, list);\n \n+\t/* cull duplicates */\n+\tfor (tmp = result, list = NULL; tmp; ) {\n+\t\tstruct commit *commit = tmp->item;\n+\t\tstruct commit_list *next = tmp->next;\n+\t\tif (commit->object.flags & UNINTERESTING) {\n+\t\t\tif (list != NULL)\n+\t\t\t\tlist->next = next;\n+\t\t\tfree(tmp);\n+\t\t} else {\n+\t\t\tif (list == NULL)\n+\t\t\t\tresult = tmp;\n+\t\t\tlist = tmp;\n+\t\t\tcommit->object.flags |= UNINTERESTING;\n+\t\t}\n+\n+\t\ttmp = next;\n+\t}\n+\n+\t/* reset flags */\n+\tclear_commit_marks(rev1, PARENT1 | PARENT2 | UNINTERESTING);\n+\tclear_commit_marks(rev2, PARENT1 | PARENT2 | UNINTERESTING);\n+\n+\treturn result;\n+}\n+\n+static int show_all = 0;\n+\n+static int merge_base(struct commit *rev1, struct commit *rev2)\n+{\n+\tstruct commit_list *result = get_merge_bases(rev1, rev2);\n+\n+\tif (!result)\n+\t\treturn 1;\n+\n \twhile (result) {\n-\t\tstruct commit *commit = result->item;\n-\t\tresult = result->next;\n-\t\tif (commit->object.flags & UNINTERESTING)\n-\t\t\tcontinue;\n-\t\tprintf(\"%s\\n\", sha1_to_hex(commit->object.sha1));\n+\t\tprintf(\"%s\\n\", sha1_to_hex(result->item->object.sha1));\n \t\tif (!show_all)\n \t\t\treturn 0;\n-\t\tcommit->object.flags |= UNINTERESTING;\n+\t\tresult = result->next;\n \t}\n+\n \treturn 0;\n }\n \n-- \n1.4.1.rc1.g87c00-dirty\n"},{"id":"22792","messageId":"Pine.LNX.4.63.0606291517010.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4682","inReplyTo":"20060627223249.GA8177@steel.home","subject":"[PATCH] move get_merge_bases() to core lib; use it in merge-recursive","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-29T13:17:32Z","receivedAt":"2006-06-29T13:17:32Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nmost of this patch is just a \"sub-file rename\", i.e. moving code\nliterally (sue me, SCO!) from merge-base.c to commit.c.\n\n---\n commit.c | 240 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n commit.h | 2 \n merge-base.c | 238 -----------------------------------------------------\n merge-recursive.c | 23 ++---\n 4 files changed, 250 insertions(+), 253 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 946615d..891c6d0 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -842,3 +842,243 @@ void sort_in_topological_order_fn(struct\n \t}\n \tfree(nodes);\n }\n+\n+/* merge-rebase stuff */\n+\n+#define PARENT1 1\n+#define PARENT2 2\n+#define UNINTERESTING 4\n+\n+static struct commit *interesting(struct commit_list *list)\n+{\n+\twhile (list) {\n+\t\tstruct commit *commit = list->item;\n+\t\tlist = list->next;\n+\t\tif (commit->object.flags & UNINTERESTING)\n+\t\t\tcontinue;\n+\t\treturn commit;\n+\t}\n+\treturn NULL;\n+}\n+\n+/*\n+ * A pathological example of how this thing works.\n+ *\n+ * Suppose we had this commit graph, where chronologically\n+ * the timestamp on the commit are A <= B <= C <= D <= E <= F\n+ * and we are trying to figure out the merge base for E and F\n+ * commits.\n+ *\n+ * F\n+ * / \\\n+ * E A D\n+ * \\ / / \n+ * B /\n+ * \\ /\n+ * C\n+ *\n+ * First we push E and F to list to be processed. E gets bit 1\n+ * and F gets bit 2. The list becomes:\n+ *\n+ * list=F(2) E(1), result=empty\n+ *\n+ * Then we pop F, the newest commit, from the list. Its flag is 2.\n+ * We scan its parents, mark them reachable from the side that F is\n+ * reachable from, and push them to the list:\n+ *\n+ * list=E(1) D(2) A(2), result=empty\n+ *\n+ * Next pop E and do the same.\n+ *\n+ * list=D(2) B(1) A(2), result=empty\n+ *\n+ * Next pop D and do the same.\n+ *\n+ * list=C(2) B(1) A(2), result=empty\n+ *\n+ * Next pop C and do the same.\n+ *\n+ * list=B(1) A(2), result=empty\n+ *\n+ * Now it is B's turn. We mark its parent, C, reachable from B's side,\n+ * and push it to the list:\n+ *\n+ * list=C(3) A(2), result=empty\n+ *\n+ * Now pop C and notice it has flags==3. It is placed on the result list,\n+ * and the list now contains:\n+ *\n+ * list=A(2), result=C(3)\n+ *\n+ * We pop A and do the same.\n+ * \n+ * list=B(3), result=C(3)\n+ *\n+ * Next, we pop B and something very interesting happens. It has flags==3\n+ * so it is also placed on the result list, and its parents are marked\n+ * uninteresting, retroactively, and placed back on the list:\n+ *\n+ * list=C(7), result=C(7) B(3)\n+ * \n+ * Now, list does not have any interesting commit. So we find the newest\n+ * commit from the result list that is not marked uninteresting. Which is\n+ * commit B.\n+ *\n+ *\n+ * Another pathological example how this thing used to fail to mark an\n+ * ancestor of a merge base as UNINTERESTING before we introduced the\n+ * postprocessing phase (mark_reachable_commits).\n+ *\n+ *\t\t 2\n+ *\t\t H\n+ *\t 1 / \\\n+ *\t G A \\\n+ *\t |\\ / \\ \n+ *\t | B \\\n+ *\t | \\ \\\n+ *\t \\ C F\n+ *\t \\ \\ / \n+ *\t \\ D / \n+ *\t\t\\ | /\n+ *\t\t \\| /\n+ *\t\t E\n+ *\n+ *\t list\t\t\tA B C D E F G H\n+ *\t G1 H2\t\t\t- - - - - - 1 2\n+ *\t H2 E1 B1\t\t- 1 - - 1 - 1 2\n+ *\t F2 E1 B1 A2\t\t2 1 - - 1 2 1 2\n+ *\t E3 B1 A2\t\t2 1 - - 3 2 1 2\n+ *\t B1 A2\t\t\t2 1 - - 3 2 1 2\n+ *\t C1 A2\t\t\t2 1 1 - 3 2 1 2\n+ *\t D1 A2\t\t\t2 1 1 1 3 2 1 2\n+ *\t A2\t\t\t2 1 1 1 3 2 1 2\n+ *\t B3\t\t\t2 3 1 1 3 2 1 2\n+ *\t C7\t\t\t2 3 7 1 3 2 1 2\n+ *\n+ * At this point, unfortunately, everybody in the list is\n+ * uninteresting, so we fail to complete the following two\n+ * steps to fully marking uninteresting commits.\n+ *\n+ *\t D7\t\t\t2 3 7 7 3 2 1 2\n+ *\t E7\t\t\t2 3 7 7 7 2 1 2\n+ *\n+ * and we ended up showing E as an interesting merge base.\n+ * The postprocessing phase re-injects C and continues traversal\n+ * to contaminate D and E.\n+ */\n+\n+static void mark_reachable_commits(struct commit_list *result,\n+\t\t\t\t struct commit_list *list)\n+{\n+\tstruct commit_list *tmp;\n+\n+\t/*\n+\t * Postprocess to fully contaminate the well.\n+\t */\n+\tfor (tmp = result; tmp; tmp = tmp->next) {\n+\t\tstruct commit *c = tmp->item;\n+\t\t/* Reinject uninteresting ones to list,\n+\t\t * so we can scan their parents.\n+\t\t */\n+\t\tif (c->object.flags & UNINTERESTING)\n+\t\t\tcommit_list_insert(c, &list);\n+\t}\n+\twhile (list) {\n+\t\tstruct commit *c = list->item;\n+\t\tstruct commit_list *parents;\n+\n+\t\ttmp = list;\n+\t\tlist = list->next;\n+\t\tfree(tmp);\n+\n+\t\t/* Anything taken out of the list is uninteresting, so\n+\t\t * mark all its parents uninteresting. We do not\n+\t\t * parse new ones (we already parsed all the relevant\n+\t\t * ones).\n+\t\t */\n+\t\tparents = c->parents;\n+\t\twhile (parents) {\n+\t\t\tstruct commit *p = parents->item;\n+\t\t\tparents = parents->next;\n+\t\t\tif (!(p->object.flags & UNINTERESTING)) {\n+\t\t\t\tp->object.flags |= UNINTERESTING;\n+\t\t\t\tcommit_list_insert(p, &list);\n+\t\t\t}\n+\t\t}\n+\t}\n+}\n+\n+struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2)\n+{\n+\tstruct commit_list *list = NULL;\n+\tstruct commit_list *result = NULL;\n+\tstruct commit_list *tmp = NULL;\n+\n+\tif (rev1 == rev2)\n+\t\treturn commit_list_insert(rev1, &result);\n+\n+\tparse_commit(rev1);\n+\tparse_commit(rev2);\n+\n+\trev1->object.flags |= PARENT1;\n+\trev2->object.flags |= PARENT2;\n+\tinsert_by_date(rev1, &list);\n+\tinsert_by_date(rev2, &list);\n+\n+\twhile (interesting(list)) {\n+\t\tstruct commit *commit = list->item;\n+\t\tstruct commit_list *parents;\n+\t\tint flags = commit->object.flags\n+\t\t\t& (PARENT1 | PARENT2 | UNINTERESTING);\n+\n+\t\ttmp = list;\n+\t\tlist = list->next;\n+\t\tfree(tmp);\n+\t\tif (flags == (PARENT1 | PARENT2)) {\n+\t\t\tinsert_by_date(commit, &result);\n+\n+\t\t\t/* Mark parents of a found merge uninteresting */\n+\t\t\tflags |= UNINTERESTING;\n+\t\t}\n+\t\tparents = commit->parents;\n+\t\twhile (parents) {\n+\t\t\tstruct commit *p = parents->item;\n+\t\t\tparents = parents->next;\n+\t\t\tif ((p->object.flags & flags) == flags)\n+\t\t\t\tcontinue;\n+\t\t\tparse_commit(p);\n+\t\t\tp->object.flags |= flags;\n+\t\t\tinsert_by_date(p, &list);\n+\t\t}\n+\t}\n+\n+\tif (!result)\n+\t\treturn NULL;\n+\n+\tif (result->next && list)\n+\t\tmark_reachable_commits(result, list);\n+\n+\t/* cull duplicates */\n+\tfor (tmp = result, list = NULL; tmp; ) {\n+\t\tstruct commit *commit = tmp->item;\n+\t\tstruct commit_list *next = tmp->next;\n+\t\tif (commit->object.flags & UNINTERESTING) {\n+\t\t\tif (list != NULL)\n+\t\t\t\tlist->next = next;\n+\t\t\tfree(tmp);\n+\t\t} else {\n+\t\t\tif (list == NULL)\n+\t\t\t\tresult = tmp;\n+\t\t\tlist = tmp;\n+\t\t\tcommit->object.flags |= UNINTERESTING;\n+\t\t}\n+\n+\t\ttmp = next;\n+\t}\n+\n+\t/* reset flags */\n+\tclear_commit_marks(rev1, PARENT1 | PARENT2 | UNINTERESTING);\n+\tclear_commit_marks(rev2, PARENT1 | PARENT2 | UNINTERESTING);\n+\n+\treturn result;\n+}\ndiff --git a/commit.h b/commit.h\nindex 7c9ca3f..89b9dad 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -105,4 +105,6 @@ struct commit_graft *read_graft_line(cha\n int register_commit_graft(struct commit_graft *, int);\n int read_graft_file(const char *graft_file);\n \n+extern struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2);\n+\n #endif /* COMMIT_H */\ndiff --git a/merge-base.c b/merge-base.c\nindex 7d87c20..b41f76c 100644\n--- a/merge-base.c\n+++ b/merge-base.c\n@@ -2,244 +2,6 @@ #include \n #include \"cache.h\"\n #include \"commit.h\"\n \n-#define PARENT1 1\n-#define PARENT2 2\n-#define UNINTERESTING 4\n-\n-static struct commit *interesting(struct commit_list *list)\n-{\n-\twhile (list) {\n-\t\tstruct commit *commit = list->item;\n-\t\tlist = list->next;\n-\t\tif (commit->object.flags & UNINTERESTING)\n-\t\t\tcontinue;\n-\t\treturn commit;\n-\t}\n-\treturn NULL;\n-}\n-\n-/*\n- * A pathological example of how this thing works.\n- *\n- * Suppose we had this commit graph, where chronologically\n- * the timestamp on the commit are A <= B <= C <= D <= E <= F\n- * and we are trying to figure out the merge base for E and F\n- * commits.\n- *\n- * F\n- * / \\\n- * E A D\n- * \\ / / \n- * B /\n- * \\ /\n- * C\n- *\n- * First we push E and F to list to be processed. E gets bit 1\n- * and F gets bit 2. The list becomes:\n- *\n- * list=F(2) E(1), result=empty\n- *\n- * Then we pop F, the newest commit, from the list. Its flag is 2.\n- * We scan its parents, mark them reachable from the side that F is\n- * reachable from, and push them to the list:\n- *\n- * list=E(1) D(2) A(2), result=empty\n- *\n- * Next pop E and do the same.\n- *\n- * list=D(2) B(1) A(2), result=empty\n- *\n- * Next pop D and do the same.\n- *\n- * list=C(2) B(1) A(2), result=empty\n- *\n- * Next pop C and do the same.\n- *\n- * list=B(1) A(2), result=empty\n- *\n- * Now it is B's turn. We mark its parent, C, reachable from B's side,\n- * and push it to the list:\n- *\n- * list=C(3) A(2), result=empty\n- *\n- * Now pop C and notice it has flags==3. It is placed on the result list,\n- * and the list now contains:\n- *\n- * list=A(2), result=C(3)\n- *\n- * We pop A and do the same.\n- * \n- * list=B(3), result=C(3)\n- *\n- * Next, we pop B and something very interesting happens. It has flags==3\n- * so it is also placed on the result list, and its parents are marked\n- * uninteresting, retroactively, and placed back on the list:\n- *\n- * list=C(7), result=C(7) B(3)\n- * \n- * Now, list does not have any interesting commit. So we find the newest\n- * commit from the result list that is not marked uninteresting. Which is\n- * commit B.\n- *\n- *\n- * Another pathological example how this thing used to fail to mark an\n- * ancestor of a merge base as UNINTERESTING before we introduced the\n- * postprocessing phase (mark_reachable_commits).\n- *\n- *\t\t 2\n- *\t\t H\n- *\t 1 / \\\n- *\t G A \\\n- *\t |\\ / \\ \n- *\t | B \\\n- *\t | \\ \\\n- *\t \\ C F\n- *\t \\ \\ / \n- *\t \\ D / \n- *\t\t\\ | /\n- *\t\t \\| /\n- *\t\t E\n- *\n- *\t list\t\t\tA B C D E F G H\n- *\t G1 H2\t\t\t- - - - - - 1 2\n- *\t H2 E1 B1\t\t- 1 - - 1 - 1 2\n- *\t F2 E1 B1 A2\t\t2 1 - - 1 2 1 2\n- *\t E3 B1 A2\t\t2 1 - - 3 2 1 2\n- *\t B1 A2\t\t\t2 1 - - 3 2 1 2\n- *\t C1 A2\t\t\t2 1 1 - 3 2 1 2\n- *\t D1 A2\t\t\t2 1 1 1 3 2 1 2\n- *\t A2\t\t\t2 1 1 1 3 2 1 2\n- *\t B3\t\t\t2 3 1 1 3 2 1 2\n- *\t C7\t\t\t2 3 7 1 3 2 1 2\n- *\n- * At this point, unfortunately, everybody in the list is\n- * uninteresting, so we fail to complete the following two\n- * steps to fully marking uninteresting commits.\n- *\n- *\t D7\t\t\t2 3 7 7 3 2 1 2\n- *\t E7\t\t\t2 3 7 7 7 2 1 2\n- *\n- * and we ended up showing E as an interesting merge base.\n- * The postprocessing phase re-injects C and continues traversal\n- * to contaminate D and E.\n- */\n-\n-static void mark_reachable_commits(struct commit_list *result,\n-\t\t\t\t struct commit_list *list)\n-{\n-\tstruct commit_list *tmp;\n-\n-\t/*\n-\t * Postprocess to fully contaminate the well.\n-\t */\n-\tfor (tmp = result; tmp; tmp = tmp->next) {\n-\t\tstruct commit *c = tmp->item;\n-\t\t/* Reinject uninteresting ones to list,\n-\t\t * so we can scan their parents.\n-\t\t */\n-\t\tif (c->object.flags & UNINTERESTING)\n-\t\t\tcommit_list_insert(c, &list);\n-\t}\n-\twhile (list) {\n-\t\tstruct commit *c = list->item;\n-\t\tstruct commit_list *parents;\n-\n-\t\ttmp = list;\n-\t\tlist = list->next;\n-\t\tfree(tmp);\n-\n-\t\t/* Anything taken out of the list is uninteresting, so\n-\t\t * mark all its parents uninteresting. We do not\n-\t\t * parse new ones (we already parsed all the relevant\n-\t\t * ones).\n-\t\t */\n-\t\tparents = c->parents;\n-\t\twhile (parents) {\n-\t\t\tstruct commit *p = parents->item;\n-\t\t\tparents = parents->next;\n-\t\t\tif (!(p->object.flags & UNINTERESTING)) {\n-\t\t\t\tp->object.flags |= UNINTERESTING;\n-\t\t\t\tcommit_list_insert(p, &list);\n-\t\t\t}\n-\t\t}\n-\t}\n-}\n-\n-struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2)\n-{\n-\tstruct commit_list *list = NULL;\n-\tstruct commit_list *result = NULL;\n-\tstruct commit_list *tmp = NULL;\n-\n-\tif (rev1 == rev2)\n-\t\treturn commit_list_insert(rev1, &result);\n-\n-\tparse_commit(rev1);\n-\tparse_commit(rev2);\n-\n-\trev1->object.flags |= PARENT1;\n-\trev2->object.flags |= PARENT2;\n-\tinsert_by_date(rev1, &list);\n-\tinsert_by_date(rev2, &list);\n-\n-\twhile (interesting(list)) {\n-\t\tstruct commit *commit = list->item;\n-\t\tstruct commit_list *parents;\n-\t\tint flags = commit->object.flags\n-\t\t\t& (PARENT1 | PARENT2 | UNINTERESTING);\n-\n-\t\ttmp = list;\n-\t\tlist = list->next;\n-\t\tfree(tmp);\n-\t\tif (flags == (PARENT1 | PARENT2)) {\n-\t\t\tinsert_by_date(commit, &result);\n-\n-\t\t\t/* Mark parents of a found merge uninteresting */\n-\t\t\tflags |= UNINTERESTING;\n-\t\t}\n-\t\tparents = commit->parents;\n-\t\twhile (parents) {\n-\t\t\tstruct commit *p = parents->item;\n-\t\t\tparents = parents->next;\n-\t\t\tif ((p->object.flags & flags) == flags)\n-\t\t\t\tcontinue;\n-\t\t\tparse_commit(p);\n-\t\t\tp->object.flags |= flags;\n-\t\t\tinsert_by_date(p, &list);\n-\t\t}\n-\t}\n-\n-\tif (!result)\n-\t\treturn NULL;\n-\n-\tif (result->next && list)\n-\t\tmark_reachable_commits(result, list);\n-\n-\t/* cull duplicates */\n-\tfor (tmp = result, list = NULL; tmp; ) {\n-\t\tstruct commit *commit = tmp->item;\n-\t\tstruct commit_list *next = tmp->next;\n-\t\tif (commit->object.flags & UNINTERESTING) {\n-\t\t\tif (list != NULL)\n-\t\t\t\tlist->next = next;\n-\t\t\tfree(tmp);\n-\t\t} else {\n-\t\t\tif (list == NULL)\n-\t\t\t\tresult = tmp;\n-\t\t\tlist = tmp;\n-\t\t\tcommit->object.flags |= UNINTERESTING;\n-\t\t}\n-\n-\t\ttmp = next;\n-\t}\n-\n-\t/* reset flags */\n-\tclear_commit_marks(rev1, PARENT1 | PARENT2 | UNINTERESTING);\n-\tclear_commit_marks(rev2, PARENT1 | PARENT2 | UNINTERESTING);\n-\n-\treturn result;\n-}\n-\n static int show_all = 0;\n \n static int merge_base(struct commit *rev1, struct commit *rev2)\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 9bbb426..c0de38a 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -186,22 +186,15 @@ struct merge_result merge(struct node *h\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\tstruct commit_list *iter, *merge_bases\n+\t\t\t= get_merge_bases(h1->commit, h2->commit);\n+\n+\t\tfor (iter = merge_bases; iter; iter = iter->next) {\n+\t\t\tstruct node *n = node_alloc(iter->item);\n+\t\t\tnode_list_insert(n, pca);\n+\t\t\tpca = &(*pca)->next;\n \t\t}\n-\t\tpclose(fp);\n+\t\tfree_commit_list(merge_bases);\n \t}\n \n \toutput(\"found %u common ancestor(s):\", node_list_count(ca));\n-- \n1.4.1.rc1.g87c00-dirty\n"},{"id":"22793","messageId":"Pine.LNX.4.63.0606291519440.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4682","inReplyTo":"Pine.LNX.4.63.0606291517010.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] move get_merge_bases() to core lib; use it in merge-recursive","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-29T13:21:31Z","receivedAt":"2006-06-29T13:21:31Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nAargh! Of course this is [PATCH 2/2]. BTW, no signoff, since the whole \nmerge-recursive is not mergeable yet (passes the tests, but we have a \nsmall way to go).\n\nCiao,\nDscho\n"},{"id":"22796","messageId":"81b0412b0606290712h4960ee8et7ea219d4dd6428b4@mail.gmail.com","threadId":"4682","inReplyTo":"Pine.LNX.4.63.0606291519440.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] move get_merge_bases() to core lib; use it in merge-recursive","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-06-29T14:12:38Z","receivedAt":"2006-06-29T14:12:38Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 6/29/06, Johannes Schindelin wrote:\n> Aargh! Of course this is [PATCH 2/2]. BTW, no signoff, since the whole\n> merge-recursive is not mergeable yet (passes the tests, but we have a\n> small way to go).\n\nHow did you get it to pass the tests? Maybe you still have git-merge-recursive\nas default merge strategy?\n"},{"id":"22797","messageId":"81b0412b0606290713y41b2e1dblbec3cd962f109f05@mail.gmail.com","threadId":"4682","inReplyTo":"Pine.LNX.4.63.0606291517010.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] move get_merge_bases() to core lib; use it in merge-recursive","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-06-29T14:13:21Z","receivedAt":"2006-06-29T14:13:21Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 6/29/06, Johannes Schindelin wrote:\n>\n> most of this patch is just a \"sub-file rename\", i.e. moving code\n> literally (sue me, SCO!) from merge-base.c to commit.c.\n>\n\nAah, thanks! Will try it later today.\n"},{"id":"22798","messageId":"81b0412b0606290714v66a32976j531e2077ce6c1d77@mail.gmail.com","threadId":"4682","inReplyTo":"Pine.LNX.4.63.0606291517010.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] move get_merge_bases() to core lib; use it in merge-recursive","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-06-29T14:14:38Z","receivedAt":"2006-06-29T14:14:38Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 6/29/06, Johannes Schindelin wrote:\n>\n> most of this patch is just a \"sub-file rename\", i.e. moving code\n> literally (sue me, SCO!) from merge-base.c to commit.c.\n>\n\nBTW, you probably want to post merge-recursive.c changes separately.\n"},{"id":"22801","messageId":"Pine.LNX.4.63.0606291813540.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4682","inReplyTo":"81b0412b0606290712h4960ee8et7ea219d4dd6428b4@mail.gmail.com","subject":"Re: [PATCH] move get_merge_bases() to core lib; use it in merge-recursive","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-29T16:14:12Z","receivedAt":"2006-06-29T16:14:12Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 29 Jun 2006, Alex Riesen wrote:\n\n> On 6/29/06, Johannes Schindelin wrote:\n> > Aargh! Of course this is [PATCH 2/2]. BTW, no signoff, since the whole\n> > merge-recursive is not mergeable yet (passes the tests, but we have a\n> > small way to go).\n> \n> How did you get it to pass the tests? Maybe you still have git-merge-recursive\n> as default merge strategy?\n\nDarn. Yes.\n\nSorry for the noise.\n\nCiao,\nDscho\n"},{"id":"22802","messageId":"Pine.LNX.4.63.0606291814200.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4682","inReplyTo":"81b0412b0606290714v66a32976j531e2077ce6c1d77@mail.gmail.com","subject":"Re: [PATCH] move get_merge_bases() to core lib; use it in merge-recursive","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-29T16:14:48Z","receivedAt":"2006-06-29T16:14:48Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 29 Jun 2006, Alex Riesen wrote:\n\n> On 6/29/06, Johannes Schindelin wrote:\n> > \n> > most of this patch is just a \"sub-file rename\", i.e. moving code\n> > literally (sue me, SCO!) from merge-base.c to commit.c.\n> > \n> \n> BTW, you probably want to post merge-recursive.c changes separately.\n\nMy point being: it makes no sense to split off get_merge_bases() if nobody \nuses it except for git-merge-base.\n\nCiao,\nDscho\n"},{"id":"22816","messageId":"Pine.LNX.4.64.0606291123360.12404@g5.osdl.org","threadId":"4682","inReplyTo":"Pine.LNX.4.63.0606291814200.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] move get_merge_bases() to core lib; use it in merge-recursive","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-29T18:26:23Z","receivedAt":"2006-06-29T18:26:23Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 29 Jun 2006, Johannes Schindelin wrote:\n> \n> My point being: it makes no sense to split off get_merge_bases() if nobody \n> uses it except for git-merge-base.\n\nI disagree. Your get_merge_bases() function is another small step in \ncleanup and libification, so I think it's perfectly valid regardless of \nwhether somebody uses it yet.\n\nA lot of the libification effort ends up being preparatory, because often \nyou need to get past a hump of libifying a _lot_ in order to actually use \nsomething in a library.\n\nSo at first, the only user is usually the old separate program. So you \nlibify get_merge_bases, and initially the only user is git-merge-base, \nwhich could now be made a built-in, since the bulk of its code is going to \nbe linked in regardless..\n\n\t\tLinus\n"},{"id":"22817","messageId":"7vmzbvrela.fsf@assigned-by-dhcp.cox.net","threadId":"4682","inReplyTo":"Pine.LNX.4.63.0606291814200.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] move get_merge_bases() to core lib; use it in merge-recursive","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-29T18:39:29Z","receivedAt":"2006-06-29T18:39:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> My point being: it makes no sense to split off get_merge_bases() if nobody \n> uses it except for git-merge-base.\n\nI do not think that is a good reasoning. If something is\nreusable (or you made it reusable) and you are planning to reuse\nit later, splitting it out without changing anything else to\nmake sure the split is correct is a seemingly small but a very\nimportant step.\n"},{"id":"22818","messageId":"Pine.LNX.4.63.0606291945200.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4682","inReplyTo":"81b0412b0606290143g5a3a0f5atbda3f4250411e92e@mail.gmail.com","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-29T18:40:46Z","receivedAt":"2006-06-29T18:40:46Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 29 Jun 2006, Alex Riesen wrote:\n\n> [cc list restored, I'm lost in the maze of git update-index, all cache\n> changing functions looking almost the same]\n> \n> On 6/29/06, Junio C Hamano wrote:\n> > > this broke t6022-merge-rename.sh (the second test). It produces an\n> > > index with this:\n> > >\n> > > .../t/trash$ git-diff-index white\n> > > :100644 100644 2d603156dc5bdf6295c789cac08e3c9942a0b82a\n> > 0000000000000000000000000000000000000000 M B\n> > > :100644 100644 ba41fb96393979b22691106b06bf5231eab57b85\n> > 0000000000000000000000000000000000000000 M N\n> > >\n> > > whereas git-merge-recursive (and the previous version, without pipe):\n> > >\n> > > .../t/trash$ git-diff-index white\n> > > :100644 100644 2d603156dc5bdf6295c789cac08e3c9942a0b82a\n> > 0000000000000000000000000000000000000000 M B\n> > >\n> > > I can see that \"git update-index --add\" is somehow different from a\n> > > pipe to \"git update-index --index-info\", but not very clear. Does this\n> > > \"zero-sha1\" mean that the file \"N\" is not in the index?\n> > \n> > When diff-index and diff-files compare a tree entry or an index\n> > entry with a file in the working tree, they do not compute the\n> > blob hash value for the file in the working tree. 0{40} is used\n> > on the RHS in such a case. When the working tree file matches\n> > the corresponding index entry, then we know RHS matches what is\n> > in the index, so both sides have the blob hash value.\n> \n> Ok. Am I correct in the assumption, that if the file in working tree has\n> the same SHA1 as LHS, than the next \"git-update-index --refresh\" will\n> remove the entry from git-diff-index output?\n> This is what actually happens, if I do \"git-update-index --refresh\", so I\n> suspect that I have an SHA1 update gone missing somewhere.\n\nI think the problem is more like this (in ce_match_stat_basic()):\n\n if (ce->ce_mtime.sec != htonl(st->st_mtime))\n changed |= MTIME_CHANGED;\n if (ce->ce_ctime.sec != htonl(st->st_ctime))\n changed |= CTIME_CHANGED;\n\nIf you update with --index-info, the mtime and ctime is not updated \nfrom the file in the working directory.\n\nAll the more a reason to go forward with direct calls to read_cache() and \nwrite_cache(). At the moment, my plan is\n\n- trivially split the read_cache() code into read_cache()/read_cache_from(),\n- introduce flush_cache(),\n- trivially rewrite add_file_to_cache(), and add_cache_info() from\n builtin-update-index.c, move that to read-tree.c, too, and\n- throw out the pipe to git-update-index from merge-recursive.c \n altogether.\n\nThis should be less intrusive than it sounds: with the introduction of \nread_cache_from() it should be trivial to handle the problem of different \nindex files.\n\nWe have to put a lock_file on the index file at the start, and write the \nindex file at the end.\n\nCiao,\nDscho\n"},{"id":"22824","messageId":"Pine.LNX.4.63.0606292050380.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4682","inReplyTo":"7vmzbvrela.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] move get_merge_bases() to core lib; use it in merge-recursive","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-29T19:06:56Z","receivedAt":"2006-06-29T19:06:56Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Linus, Hi Junio\n\n[this is a response to both of your responses; mail threads cannot yet be \nmerged a la git ;-)]\n\nOn Thu, 29 Jun 2006, Junio C Hamano wrote:\n\n> Johannes Schindelin writes:\n> \n> > My point being: it makes no sense to split off get_merge_bases() if nobody \n> > uses it except for git-merge-base.\n> \n> I do not think that is a good reasoning. If something is\n> reusable (or you made it reusable) and you are planning to reuse\n> it later, splitting it out without changing anything else to\n> make sure the split is correct is a seemingly small but a very\n> important step.\n\nOkay. Convinced.\n\nI tested my patch again, and like Alex said, a test fails. But I tested on \ntop of Alex's latest merge-recursive patch, which has that nasty \nupdate-index bug, and that is the reason for the test to fail.\n\nSo, a few tests later, I am pretty sure that my patches do not break \ngit-merge-base. I'll prepare another patch series which builds-in \nmerge-base.\n\nCiao,\nDscho\n"},{"id":"22835","messageId":"7vr717ptlx.fsf@assigned-by-dhcp.cox.net","threadId":"4682","inReplyTo":"Pine.LNX.4.63.0606292050380.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] move get_merge_bases() to core lib; use it in merge-recursive","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-29T20:58:02Z","receivedAt":"2006-06-29T20:58:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> So, a few tests later, I am pretty sure that my patches do not break \n> git-merge-base. I'll prepare another patch series which builds-in \n> merge-base.\n\nI'll take your two patches to refactor merge-base and to move\nthe bulk of the code to commit.c for now. Updated \"next\" coming\nshortly.\n"},{"id":"22858","messageId":"20060629232836.GB7216@steel.home","threadId":"4682","inReplyTo":"Pine.LNX.4.63.0606291945200.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: CFT: merge-recursive in C (updated)","fromName":"Alex Riesen","fromEmail":"fork0@t-online.de","sentAt":"2006-06-29T23:28:36Z","receivedAt":"2006-06-29T23:28:36Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Johannes Schindelin, Thu, Jun 29, 2006 20:40:46 +0200:\n> > > \n> > > When diff-index and diff-files compare a tree entry or an index\n> > > entry with a file in the working tree, they do not compute the\n> > > blob hash value for the file in the working tree. 0{40} is used\n> > > on the RHS in such a case. When the working tree file matches\n> > > the corresponding index entry, then we know RHS matches what is\n> > > in the index, so both sides have the blob hash value.\n> > \n> > Ok. Am I correct in the assumption, that if the file in working tree has\n> > the same SHA1 as LHS, than the next \"git-update-index --refresh\" will\n> > remove the entry from git-diff-index output?\n> > This is what actually happens, if I do \"git-update-index --refresh\", so I\n> > suspect that I have an SHA1 update gone missing somewhere.\n> \n> I think the problem is more like this (in ce_match_stat_basic()):\n> \n> if (ce->ce_mtime.sec != htonl(st->st_mtime))\n> changed |= MTIME_CHANGED;\n> if (ce->ce_ctime.sec != htonl(st->st_ctime))\n> changed |= CTIME_CHANGED;\n> \n> If you update with --index-info, the mtime and ctime is not updated \n> from the file in the working directory.\n\nOh, I see. I was under impression git-diff-index does not use mtime/ctime.\nThought it was just mode+sha between treeish and index.\n $ man git-diff-index\n git-diff-index \n compares the and the files on the filesystem.\n git-diff-index --cached \n compares the and the index.\nSo it does compare treeish ad index, but only if explicitly told so.\nPity, there seem to be no way to update the times in --index-info\nprotocol yet. Maybe it'll be even never needed, after cache functions\ngone libraries.\n\n> All the more a reason to go forward with direct calls to read_cache() and \n> write_cache(). At the moment, my plan is\n> \n> - trivially split the read_cache() code into read_cache()/read_cache_from(),\n> - introduce flush_cache(),\n> - trivially rewrite add_file_to_cache(), and add_cache_info() from\n> builtin-update-index.c, move that to read-tree.c, too, and\n> - throw out the pipe to git-update-index from merge-recursive.c \n> altogether.\n> \n> This should be less intrusive than it sounds: with the introduction of \n> read_cache_from() it should be trivial to handle the problem of different \n> index files.\n> \n> We have to put a lock_file on the index file at the start, and write the \n> index file at the end.\n> \n\nYes, very nice plan, all by itself :)\n"},{"id":"22861","messageId":"20060630002713.GD7216@steel.home","threadId":"4682","inReplyTo":"Pine.LNX.4.63.0606292050380.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] move get_merge_bases() to core lib; use it in merge-recursive","fromName":"Alex Riesen","fromEmail":"fork0@t-online.de","sentAt":"2006-06-30T00:27:13Z","receivedAt":"2006-06-30T00:27:13Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Johannes Schindelin, Thu, Jun 29, 2006 21:06:56 +0200:\n> \n> Okay. Convinced.\n> \n> I tested my patch again, and like Alex said, a test fails. But I tested on \n> top of Alex's latest merge-recursive patch, which has that nasty \n> update-index bug, and that is the reason for the test to fail.\n> \n> So, a few tests later, I am pretty sure that my patches do not break \n> git-merge-base. I'll prepare another patch series which builds-in \n> merge-base.\n> \n\nJust for reference, I'll repost all my patches again, somewhat\nconsolidated. Your merge_base patches can be applied on top of that\nseries.\n"}]}