{"thread":{"id":"4671","subject":"CFT: merge-recursive in C","startedAt":"2006-06-26T23:38:38Z","lastAt":"2006-06-29T00:49:22Z","messageCount":27,"participants":["Alex Riesen","Linus Torvalds","Junio C Hamano","Johannes Schindelin","Uwe Zeisberger","Christopher Faylor"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"22629","messageId":"20060626233838.GA3121@steel.home","threadId":"4671","inReplyTo":null,"subject":"CFT: merge-recursive in C","fromName":"Alex Riesen","fromEmail":"fork0@t-online.de","sentAt":"2006-06-26T23:38:38Z","receivedAt":"2006-06-26T23:38:38Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Hi all.\n\nI finally got pis^Witched enough by my platform at work and decided\nto start the effort of converting Fredriks git-merge-recursive to C.\nAt the moment it is the only one annoyingly slow thing there.\n\nThe result, represented by the patch below, is really just a\nconversion. I DO NOT propose it for inclusion yet (maybe someone else\nlooks at it and does it for me). It passes the test suite, but I don't\nthink it is mature enough to be used routinely. I am about to test it\nextensively on my repository (which is kind of labirinth for any SCM)\nat work, so it is not really tested as well.\n\nIt still uses some calls to git programs (git-update-index,\ngit-hash-object, git-diff-tree and git-write-tree), and merge(1) has\nthe labels (-L) missing - I was unsure how to tackle this on windows -\nit has only argv[1].\n\nAnd it needs to be cleaned up a bit (a lot) - Python is not exactly\nwhat you'd call \"C-conversion-friendly-language\", and I am not an\nexpert (as in \"git-merge-recursive.py is my first Python experience\").\n\nTo my deep disappointment, it didn't work out as good as I hoped: one\nprogram I see most often and for longest time in the process list\n(git-diff-tree) is a too complex thing to be put directly into\nmerge-recursive.c, so any help in this direction will be greatly\nappreciated.\n\nStill, I have a dependency less, some spared calls to git-cat-file,\ngit-rev-parse, git-read-tree and git-ls-tree, so it should be\nfaster (my workflow on windows is seldom constrained by CPU, that\nbeing maxed out as per OS manufacturer recommendations).\n\nTwo files, path_list.[hc] can be probably used somewhere else - its a\ncrude string list. The other two, graph.[hc] - an attempt to represent\na graph. The \"struct node\" (a graph node representation) looks\nsomewhat superflous to me (copied from Commit) and probably should be\nreplaced by \"struct commit\". \"merge-recursive.c\" is what left from\n\"git-merge-recursive.py\".\n\nHave fun.\n\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..aa93847 100755\n--- a/git-merge.sh\n+++ b/git-merge.sh\n@@ -10,15 +10,15 @@ USAGE='[-n] [--no-commit] [-s \n LF='\n '\n \n-all_strategies='recursive octopus resolve stupid ours'\n-default_twohead_strategies='recursive'\n+all_strategies='recur recursive octopus resolve stupid ours'\n+default_twohead_strategies='recur'\n default_octopus_strategies='octopus'\n no_trivial_merge_strategies='ours'\n 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..9a0181c\n--- /dev/null\n+++ b/merge-recursive.c\n@@ -0,0 +1,1608 @@\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+\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+\tchar cmd[80];\n+\tsprintf(cmd, \"git-read-tree %s\", sha1_to_hex(tree->object.sha1));\n+\tint rc = system(cmd);\n+\treturn rc == -1 ? -1: WEXITSTATUS(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+\tchar cmd[256];\n+\tsprintf(cmd, \"git-read-tree %s -m %s %s %s\",\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+\tint rc = system(cmd);\n+\treturn rc == -1 ? -1: WEXITSTATUS(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+\tchar cmd[PATH_MAX];\n+\tsprintf(cmd, \"git-diff-tree -M --diff-filter=R -r -z %s %s\",\n+\t\tsha1_to_hex(oTree->object.sha1),\n+\t\tsha1_to_hex(tree->object.sha1));\n+\tFILE *fp = popen(cmd, \"r\");\n+\twhile ( !feof(fp) ) {\n+\t\tchar buf[PATH_MAX+1];\n+\t\tint p, ch;\n+\t\tstruct rename_entry *re = NULL;\n+\t\tif ( (ch = fgetc(fp)) == EOF )\n+\t\t\tbreak;\n+\t\telse if ( ':' != ch )\n+\t\t\tgoto error;\n+\t\tre = xmalloc(sizeof(*re));\n+\t\tre->src = re->dst = NULL;\n+\t\tre->next = NULL;\n+\t\tre->processed = 0;\n+\t\t// mode1\n+\t\tif ( fget_mode(&re->src_mode, fp, &ch) )\n+\t\t\tgoto error;\n+\t\tif ( '\\x20' != ch )\n+\t\t\tgoto error;\n+\t\t// mode2\n+\t\tif ( fget_mode(&re->dst_mode, fp, &ch) )\n+\t\t\tgoto error;\n+\t\tif ( '\\x20' != ch )\n+\t\t\tgoto error;\n+\t\t// src sha1\n+\t\tif ( fget_sha1(re->src_sha, fp, &ch) )\n+\t\t\tgoto error;\n+\t\tif ( '\\x20' != ch )\n+\t\t\tgoto error;\n+\t\t// dst sha1\n+\t\tif ( fget_sha1(re->dst_sha, fp, &ch) )\n+\t\t\tgoto error;\n+\t\tif ( '\\x20' != ch )\n+\t\t\tgoto error;\n+\t\t// score\n+\t\tif ( (ch = fgetc(fp)) != EOF )\n+\t\t\tif ( ch != 'R' )\n+\t\t\t\tgoto wait_3eol;\n+\t\tfor ( p = 0; (ch = fgetc(fp)) != EOF; ++p ) {\n+\t\t\tbuf[p] = ch;\n+\t\t\tif ( p == 3 ) {\n+\t\t\t\tbuf[p] = '\\0';\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif ( !ch )\n+\t\t\t\tbreak;\n+\t\t\tif ( ch < '0' || ch > '9' )\n+\t\t\t\tgoto error;\n+\t\t}\n+\t\tif ( '\\0' != ch && ((ch = fgetc(fp)) == EOF || '\\0' != ch) )\n+\t\t\tgoto error;\n+\t\tre->score = strtol(buf, 0, 10);\n+\t\t// name 1\n+\t\tfor ( p = 0; (ch = fgetc(fp)) != EOF; ++p ) {\n+\t\t\tbuf[p] = ch;\n+\t\t\tif ( !ch )\n+\t\t\t\tbreak;\n+\t\t\tif ( p == PATH_MAX ) {\n+\t\t\t\tbuf[p] = '\\0';\n+\t\t\t\terror(\"name1 too long: %s\", buf);\n+\t\t\t\tgoto error;\n+\t\t\t}\n+\t\t}\n+\t\tre->src = strdup(buf);\n+\t\t// name 2\n+\t\tfor ( p = 0; (ch = fgetc(fp)) != EOF; ++p ) {\n+\t\t\tbuf[p] = ch;\n+\t\t\tif ( !ch )\n+\t\t\t\tbreak;\n+\t\t\tif ( p == PATH_MAX ) {\n+\t\t\t\tbuf[p] = '\\0';\n+\t\t\t\terror(\"name2 too long: %s\", buf);\n+\t\t\t\tgoto error;\n+\t\t\t}\n+\t\t}\n+\t\tre->dst = strdup(buf);\n+\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\t// printf(\"re %s:%s -> %s:%s R%d\\n\",\n+\t\t// sha1_to_hex(re->src_sha), re->src,\n+\t\t// sha1_to_hex(re->dst_sha), re->dst,\n+\t\t// re->score);\n+\t\t// print_index_entry(\"re->src_entry \", re->src_entry);\n+\t\t// print_index_entry(\"re->dst_entry \", re->dst_entry);\n+\t\tcontinue;\n+\twait_3eol:\n+\t\twhile ( (ch = fgetc(fp)) != EOF && ch );\n+\t\twhile ( (ch = fgetc(fp)) != EOF && ch );\n+\terror:\n+\t\trename_entry_free(re);\n+\t\twhile ( (ch = fgetc(fp)) != EOF && ch );\n+\t}\n+\tpclose(fp);\n+\treturn renames;\n+}\n+\n+int setIndexStages(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+\tFILE *fp = popen(\"git-update-index -z --index-info\", \"w\");\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 pclose(fp);\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(int clean, const char *path)\n+{\n+\tint updateCache = index_only || clean;\n+\tint updateWd = !index_only;\n+\n+\tif ( updateCache ) {\n+\t\tFILE *fp = popen(\"git-update-index --force-remove -z --stdin\", \"w\");\n+\t\tif ( !fp )\n+\t\t\treturn -1;\n+\t\tfputs(path, fp);\n+\t\tfputc('\\0', fp);\n+\t\tif ( pclose(fp) != 0 )\n+\t\t\treturn -1;\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(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\tFILE *fp;\n+\t\t// XXX just always use \"git update-index --index-info\"?\n+\t\tif ( updateWd ) {\n+\t\t\tfp = popen(\"git-update-index --add -z --stdin\", \"w\");\n+\t\t\tfputs(path, fp);\n+\t\t\tfputc('\\0', fp);\n+\t\t} else {\n+\t\t\tfp = popen(\"git-update-index --add -z --index-info\", \"w\");\n+\t\t\tfprintf(fp, \"%06o %s\\t%s\", mode, sha1_to_hex(sha), path);\n+\t\t\tfputc('\\0', fp);\n+\t\t}\n+\t\tpclose(fp);\n+\t}\n+}\n+\n+void updateFile(int clean,\n+\t\tconst unsigned char *sha,\n+\t\tunsigned mode,\n+\t\tconst char *path)\n+{\n+\tupdateFileExt(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+#if 0\n+\t\t\t[out, code] = runProgram([\"merge\",\n+\t\t\t\t \"-L\", branch1Name + \"/\" + aPath,\n+\t\t\t\t \"-L\", \"orig/\" + oPath,\n+\t\t\t\t \"-L\", branch2Name + \"/\" + bPath,\n+\t\t\t\t src1, orig, src2],\n+\t\t\t\t returnCode=True)\n+#endif\n+\t\t\tchar cmd[PATH_MAX];\n+\t\t\t// TODO labels\n+\t\t\tsnprintf(cmd, sizeof(cmd), \"merge %s %s %s\", src1, orig, src2);\n+\t\t\tprintf(\"%s\\n\", cmd);\n+\t\t\tcode = system(cmd);\n+\t\t\tif ( code == -1 )\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\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+\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(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(0, ren2->dst);\n+\t\t\t\t}\n+\t\t\t\tsetIndexStages(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(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(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(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(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(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(0, ren1->dst);\n+\t\t\t\tupdateFile(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(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(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(0, ren1->dst);\n+\t\t\t\tupdateFile(0, ren1->dst_sha, ren1->dst_mode, newPath1);\n+\t\t\t\tupdateFile(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(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(mfi.clean, mfi.sha, mfi.mode, ren1->dst);\n+\t\t\t}\n+\t\t}\n+\t}\n+\tpath_list_clear(&srcNames, 0);\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+\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(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(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(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(0, path);\n+\t\t\tupdateFile(0, sha, mode, newPath);\n+\t\t} else {\n+\t\t\toutput(\"Adding %s\", path);\n+\t\t\tupdateFile(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(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(0, path);\n+\t\t\tupdateFile(0, aSha, aMode, newPath1);\n+\t\t\tupdateFile(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(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(0, mfi.sha, mfi.mode, path);\n+\t\t\telse\n+\t\t\t\tupdateFileExt(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+\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":"22630","messageId":"20060626234242.GB3121@steel.home","threadId":"4671","inReplyTo":"20060626233838.GA3121@steel.home","subject":"CFT: merge-recursive in C (test updates)","fromName":"Alex Riesen","fromEmail":"fork0@t-online.de","sentAt":"2006-06-26T23:42:42Z","receivedAt":"2006-06-26T23:42:42Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"I had to change the tests a little, to avoid skipping test on systems\nwithout python and to force t3402-rebase-merge.sh test the converted\nprogram (this one shouldn't be merged at all of course. I think we'd\nstill want have git-merge-recursive.py around and test it too. It is\nreference implementation, to say the least).\n\n---\n\ndiff --git a/t/t3402-rebase-merge.sh b/t/t3402-rebase-merge.sh\nindex d34c6cf..c13d154 100755\n--- a/t/t3402-rebase-merge.sh\n+++ b/t/t3402-rebase-merge.sh\n@@ -7,12 +7,6 @@ test_description='git rebase --merge tes\n \n . ./test-lib.sh\n \n-if test \"$no_python\"; then\n-\techo \"Skipping: no python => no recursive merge\"\n-\ttest_done\n-\texit 0\n-fi\n-\n T=\"A quick brown fox\n jumps over the lazy dog.\"\n for i in 1 2 3 4 5 6 7 8 9 10\n@@ -51,7 +45,7 @@ test_expect_success setup '\n '\n \n test_expect_success 'reference merge' '\n-\tgit merge -s recursive \"reference merge\" HEAD master\n+\tgit merge -s recur \"reference merge\" HEAD master\n '\n \n test_expect_success rebase '\ndiff --git a/t/t6021-merge-criss-cross.sh b/t/t6021-merge-criss-cross.sh\nindex 2623813..e8606c7 100755\n--- a/t/t6021-merge-criss-cross.sh\n+++ b/t/t6021-merge-criss-cross.sh\n@@ -10,12 +10,6 @@ # nice decription of what this is about.\n test_description='Test criss-cross merge'\n . ./test-lib.sh\n \n-if test \"$no_python\"; then\n-\techo \"Skipping: no python => no recursive merge\"\n-\ttest_done\n-\texit 0\n-fi\n-\n test_expect_success 'prepare repository' \\\n 'echo \"1\n 2\n"},{"id":"22631","messageId":"Pine.LNX.4.64.0606261652350.3927@g5.osdl.org","threadId":"4671","inReplyTo":"20060626233838.GA3121@steel.home","subject":"Re: CFT: merge-recursive in C","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-26T23:54:18Z","receivedAt":"2006-06-26T23:54:18Z","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> To my deep disappointment, it didn't work out as good as I hoped: one\n> program I see most often and for longest time in the process list\n> (git-diff-tree) is a too complex thing to be put directly into\n> merge-recursive.c, so any help in this direction will be greatly\n> appreciated.\n\nAre you sure?\n\ngit-diff-tree is one of the simplest git operations. We've got absolutely \n_tons_ of infrastructure in place to do it efficiently, since it's done \nall over the map (a \"git-rev-list\" with path limiting will do a diff-tree \nagainst all the commits).\n\nSome of the interfaces might be a bit non-obvious, but the diff stuff was \nsome of the first ones to be libified exactly because they end up being so \nfundamental.\n\n\t\tLinus\n"},{"id":"22632","messageId":"Pine.LNX.4.64.0606261704390.3927@g5.osdl.org","threadId":"4671","inReplyTo":"Pine.LNX.4.64.0606261652350.3927@g5.osdl.org","subject":"Re: CFT: merge-recursive in C","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-27T00:07:02Z","receivedAt":"2006-06-27T00:07:02Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 26 Jun 2006, Linus Torvalds wrote:\n> \n> git-diff-tree is one of the simplest git operations. We've got absolutely \n> _tons_ of infrastructure in place to do it efficiently, since it's done \n> all over the map (a \"git-rev-list\" with path limiting will do a diff-tree \n> against all the commits).\n\nSide note - I think merge-recursive could/should be rewritten to use \n\"git-merge-tree\" instead of \"git-read-tree -u -m\". I suspect that the \ngit-merge-tree output is in fact a lot closer to what git-merge-recursive \nactually wants to have.\n\n\t\t\tLinus\n"},{"id":"22633","messageId":"20060627001732.GC3121@steel.home","threadId":"4671","inReplyTo":"Pine.LNX.4.64.0606261652350.3927@g5.osdl.org","subject":"Re: CFT: merge-recursive in C","fromName":"Alex Riesen","fromEmail":"fork0@t-online.de","sentAt":"2006-06-27T00:17:32Z","receivedAt":"2006-06-27T00:17: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 01:54:18 +0200:\n> > \n> > To my deep disappointment, it didn't work out as good as I hoped: one\n> > program I see most often and for longest time in the process list\n> > (git-diff-tree) is a too complex thing to be put directly into\n> > merge-recursive.c, so any help in this direction will be greatly\n> > appreciated.\n> \n> Are you sure?\n> \n> git-diff-tree is one of the simplest git operations. We've got absolutely \n> _tons_ of infrastructure in place to do it efficiently, since it's done \n> all over the map (a \"git-rev-list\" with path limiting will do a diff-tree \n> against all the commits).\n> \n> Some of the interfaces might be a bit non-obvious, but the diff stuff was \n> some of the first ones to be libified exactly because they end up being so \n> fundamental.\n> \n\nThat (non-obvious) was actually the problem here. I needed a diff-tree\nwithout any output on stdout, with \"-M\" (rename detection). The\nprecise command I gave up to implement was:\n\n git-diff-tree -M --diff-filter=R -r -z \n\nI stopped somewhere around diff_tree, being confused by show_entry.\nI took a look at it again, and it seem that show_entry does not\nactually \"show\" anything but calls diff_options->add_remove, right?\nSo I could define my callback, setup the options (which I certanly can\nfind after looking closer and longer at builtin-diff-tree.c) and wrap\ndiff_options with my own struct (I need to pass arguments to the\ncallback reentrantly: it is a recursive algorithm).\n\nWell, it wasn't that clear (unless I missed something by a mile) last\nweek... But thanks for you suspicions, they actually forced me to look\nat diff-tree again. Will do ... unless (I hope) someone beats me to it.\n\nBye!\n"},{"id":"22634","messageId":"20060627002439.GD3121@steel.home","threadId":"4671","inReplyTo":"Pine.LNX.4.64.0606261704390.3927@g5.osdl.org","subject":"Re: CFT: merge-recursive in C","fromName":"Alex Riesen","fromEmail":"fork0@t-online.de","sentAt":"2006-06-27T00:24:39Z","receivedAt":"2006-06-27T00:24:39Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Linus Torvalds, Tue, Jun 27, 2006 02:07:02 +0200:\n> > \n> > git-diff-tree is one of the simplest git operations. We've got absolutely \n> > _tons_ of infrastructure in place to do it efficiently, since it's done \n> > all over the map (a \"git-rev-list\" with path limiting will do a diff-tree \n> > against all the commits).\n> \n> Side note - I think merge-recursive could/should be rewritten to use \n> \"git-merge-tree\" instead of \"git-read-tree -u -m\". I suspect that the \n> git-merge-tree output is in fact a lot closer to what git-merge-recursive \n> actually wants to have.\n> \n\nYep. And does not touch the index, too. Cool...\n"},{"id":"22635","messageId":"7v4py7h2b9.fsf@assigned-by-dhcp.cox.net","threadId":"4671","inReplyTo":"20060626233838.GA3121@steel.home","subject":"Re: CFT: merge-recursive in C","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-27T00:25:46Z","receivedAt":"2006-06-27T00:25:46Z","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> To my deep disappointment, it didn't work out as good as I hoped: one\n> program I see most often and for longest time in the process list\n> (git-diff-tree) is a too complex thing to be put directly into\n> merge-recursive.c, so any help in this direction will be greatly\n> appreciated.\n\nActually, diff-tree is (and to similar degree the internal diff\nmachinery is) quite reusable as library piece, far more reusable\nthan other parts of the core git. If you present what you want\nto achieve nicely and ask politely I might even get conned into\nhelping you interface with the rest of your code ;-).\n\nI am guessing that you want to find out how to do the diff-tree -M\nused by the recursive merge without spitting out patch text nor\nraw output. That's quite doable and should be easy. Most\nlikely you would use NO_OUTPUT option when you call diff_tree().\n\nFirst look at builtin-diff.c::builtin_diff_tree() to see how you\ncan call the diff machinery given two tree object names. diff_tree()\nitself does not emit the diff, but leaves the result in \"diff\nqueue\".\n\nAfter calling diff_tree(), inspect diff_queued_diff() and use\nthe result to do whatever sensible. The queue is an array of\ndiff_filepair that records the (path, sha1, mode) among other\nthings from old tree and from new tree (the one from the old\ntree is called \"one\", and the new tree is called \"two\").\n\nSo if you have one->path = \"old-name.c\" and two->path = \"new-name.c\"\nthen you see the old-name.c file was renamed to new-name.c\n\nWhen you are done, do not forget to call diff_flush() to get rid\nof queued_diff(); otherwise you would leak.\n\nHave fun.\n"},{"id":"22636","messageId":"7vzmfzfnoe.fsf@assigned-by-dhcp.cox.net","threadId":"4671","inReplyTo":"20060627002439.GD3121@steel.home","subject":"Re: CFT: merge-recursive in C","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-27T00:27:13Z","receivedAt":"2006-06-27T00:27:13Z","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> Linus Torvalds, Tue, Jun 27, 2006 02:07:02 +0200:\n>> > \n>> > git-diff-tree is one of the simplest git operations. We've got absolutely \n>> > _tons_ of infrastructure in place to do it efficiently, since it's done \n>> > all over the map (a \"git-rev-list\" with path limiting will do a diff-tree \n>> > against all the commits).\n>> \n>> Side note - I think merge-recursive could/should be rewritten to use \n>> \"git-merge-tree\" instead of \"git-read-tree -u -m\". I suspect that the \n>> git-merge-tree output is in fact a lot closer to what git-merge-recursive \n>> actually wants to have.\n>> \n>\n> Yep. And does not touch the index, too. Cool...\n\nActually \"does not touch the index\" part is a defect in\nmerge-tree. It is fine at the recursive level, but at the top\nlevel we need to make sure the local changes do not interfere\nwith the merge.\n"},{"id":"22637","messageId":"20060627003833.GE3121@steel.home","threadId":"4671","inReplyTo":"7v4py7h2b9.fsf@assigned-by-dhcp.cox.net","subject":"Re: CFT: merge-recursive in C","fromName":"Alex Riesen","fromEmail":"fork0@t-online.de","sentAt":"2006-06-27T00:38:33Z","receivedAt":"2006-06-27T00:38:33Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Junio C Hamano, Tue, Jun 27, 2006 02:25:46 +0200:\n> \n> Have fun.\n> \n\nWow. Thats more of explanation that I hoped. Just let me sleep on it a bit :)\n"},{"id":"22641","messageId":"7virmn9hx8.fsf_-_@assigned-by-dhcp.cox.net","threadId":"4671","inReplyTo":"7v4py7h2b9.fsf@assigned-by-dhcp.cox.net","subject":"Notes on diffcore API","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-27T07:28:03Z","receivedAt":"2006-06-27T07:28:03Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I really should have done this six months ago, but I guess being\nlate is much better than never...\n\nSomebody might want to do proper asciidoc and throw it in\nDocumentation/technical/.\n\n-- >8 --\nNotes on diffcore API\n=====================\n\nThe diff generation mechanism in git is designed to be\nself-contained and you should be able to call it as set of\nlibrary functions, unlike other parts of the system where \"we\nrun once and let exit() to clean up afterwards\" mentality is\ndominant. This is mainly because from early on \"diff-tree\n--stdin\" needed to be able to process hundreds of parent-child\ntree pairs without leaking.\n\nNOTE: this note does not describe how combined diff works. It\nis quite a different animal.\n\nThe diffcore machinery works in 4 phases:\n\n 1. setting up the machinery, including command line parsing.\n 2. feeding input pairs to the machinery.\n 3. letting it munge input pairs.\n 4. flushing the output.\n\nThe first phase sets up the operational parameters (e.g. use of\nrename detector, output format). The second phase feeds pairs\nof 'old' and 'new' files to the machinery as the front-end finds\nthem (e.g. diff-files compares each path found in the index and\nin the working tree, and feeds the information from the index as\n'old' and the information from the working tree as 'new';\ndiff-tree compares entries in two trees or entries in the tree\nof the first parent commit and the tree of the commit). In the\nthird phase, the pairs collected in the previous phase are\nsplit, matched up, and filtered to form a different set of\npairs. The last phase formats the resulting set of pairs for\nthe output.\n\nSetting it up\n-------------\n\nThe diffcore machinery takes one structure, `struct diff_options`,\nto record the set of options that affects its behaviour. These\noptions affect different parts of its operation, but can roughly\nbe classified into three groups: the ones that affects how the\ninput set of pairs are transformed in phase 3, and the ones that\naffects how the resulting set of pairs are formatted in phase 4.\n\nFirst call diff_setup() to initialize the diff_options\nstructure. This gives the minimum default set of options:\n\n - output format defaults to --raw format;\n - output lines are LF terminated;\n - no diffcore transformation (phase 3) is used;\n\nIf you are writing a top-level diff command, you can then call\ndiff_opt_parse() to parse the common diff options and fill the\ninformation in diff_options structure, but if your usage does\nnot require end-user customizability, you can set up the fields in\ndiff_options yourself without calling this function.\n\nThen call diff_setup_done() -- this makes sure the set of\noptions are consistent and derives a reasonable default\n(e.g. --find-copies-harder without -C does not make sense, patch\noutput is always recursive).\n\n\nFeeding Input\n-------------\n\nYour main program feeds 'file pairs' to the diffcore machinery\nby using these three functions: diff_addremove(), diff_change()\nand diff_unmerge(). The first one records a path appears not in\n'old' tree but in 'new' tree (or vice versa), the second one\nrecords a path is different between 'old' and 'new', and the\nthird one says the comparison is meaningless for the path\nbecause it is unmerged (this is only used by diff-index and\ndiff-files).\n\nWhen you want to do something diff-tree does, which is quite\ncommon, you can give two tree object names to diff_tree_sha1()\nfunction and let it walk the trees and call these functions for\nyou.\n\nTo signal the end of input, call `diffcore_std()`. This\nstarts the diffcore transformation described next.\n\n\nDiffcore Transformation\n-----------------------\n\nThe input file pairs recorded in the previous phase are\ncollected in diff_queued_diff (a global variable -- which means\nthat you cannot have two diffs running in parallel with the\ncurrent setup). This is an expandable array of pointers to\n`struct diff_filepair` structure.\n\nThe `struct diff_filepair` structure has (as the name suggests)\ntwo pointers to `struct diff_filespec` to record the 'old' and\nthe 'new' file in this pair (the old one is called 'one', and\nthe new one 'two'), along with some information used by various\ndiffcore transformation. `struct diff_filespec` records the\nblob object name, pathname, size and mode among other things.\nTwo things to watch out for are:\n\n - a non-existent path is denoted by mode=0 (e.g. in a filepair\n for a deleted file, one->mode != 0 and two->mode == 0).\n\n - 0{40} SHA-1 is used when the filespec talks about the file in\n the working tree.\n\n\nDocumentation/diffcore.txt should be consulted for the details\nof what each transformation does. A short version:\n\n - diffcore-break breaks a filepair that modifies 'one' to 'two'\n into two filepairs that deletes 'one' and creates 'two' if\n 'one' and 'two' are sufficiently dissimilar.\n\n - diffcore-rename matches up a filepair that deletes 'one' and\n another filepair that creates 'two' and makes them into one\n filepair.\n\n - diffcore-merge-broken picks up two filepairs that were\n originally one but broken by diffcore-break but did not get\n matched up by diffcore-rename.\n\n - diffcore-pickaxe filters out filepairs whose 'one' and 'two'\n have the same number of occurrences of the specified string.\n\n - diffcore-order reorders the resulting filepairs according to\n the given input.\n\n - after all of the above, --diff-filter is applied to remove\n the uninteresting classes of output (e.g. --diff-filter=A\n shows only additions).\n\n\nFlushing output\n---------------\n\nAfter diffcore transformation runs, the result is still in the\nsame diff_queued_diff variable. Before calling the standard\noutput routines, you can inspect each file pair in the queue to\nsee its status (e.g. what renames to what).\n\nEspecially interesting is the 'status' field of the filepair\nstructure. At this point in the processing chain, each file\npair is marked with `M` (modified), `C` (copied), `R` (renamed),\netc.\n\nOnce you are done, calling diff_flush() to perform the output\nand free the data structure. If you ran the diff primarily\nbecause you wanted to read the diff_queued_diff and you do not\nwant any output from this phase, set the putput_format to\nDIFF_FORMAT_NO_OUTPUT before calling diff_flush() -- otherwise\nyou would leak memory the big way.\n\nThe raw, patch-text, diffstat and summary output all happens in\nthis final phase; recent work to make --patch, --stat, --raw\netc. independent flags by Timo are primarily about phase 2 and\nthis phase.\n"},{"id":"22642","messageId":"Pine.LNX.4.63.0606270936520.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4671","inReplyTo":"20060626233838.GA3121@steel.home","subject":"Re: CFT: merge-recursive in C","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-27T07:52:05Z","receivedAt":"2006-06-27T07:52:05Z","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> I finally got pis^Witched enough by my platform at work and decided\n> to start the effort of converting Fredriks git-merge-recursive to C.\n\nDarn. I was working on the same thing since a few days.\n\nA few remarks:\n\n- have you considered using run-command() instead of system()?\n- in setup_index(), you set GIT_INDEX_FILE, but I do not think that the \n rest of git picks up on it. environment.cc:get_index_file() checks if \n the variable was set already, but not if it changed.\n- You work with linked lists all the time. This is slow, especially for \n the checks, if a file/directory is already there. Sorted lists would be\n way faster there. Since you encapsulated that, it is no problem to \n change that later (before inclusion).\n- is not \"struct commit_list\" more appropriate than \"struct graph\"?\n- I always wondered why merge-recursive did not call merge-base, but did \n its own thing. Hmm?\n\n> It still uses some calls to git programs (git-update-index,\n> git-hash-object, git-diff-tree and git-write-tree), and merge(1) has\n> the labels (-L) missing - I was unsure how to tackle this on windows -\n> it has only argv[1].\n\nSee above.\n\n> And it needs to be cleaned up a bit (a lot) - Python is not exactly\n> what you'd call \"C-conversion-friendly-language\", and I am not an\n> expert (as in \"git-merge-recursive.py is my first Python experience\").\n\nNo problem. Since I already worked on it, that should be easy.\n\n> To my deep disappointment, it didn't work out as good as I hoped: one\n> program I see most often and for longest time in the process list\n> (git-diff-tree) is a too complex thing to be put directly into\n> merge-recursive.c, so any help in this direction will be greatly\n> appreciated.\n\nMaybe something like this (ripped from my fragment of merge-recursive.c):\n\nstatic struct container *get_renames(struct tree *tree,\n\t\tstruct tree *o, struct tree *a, struct tree *b,\n\t\tstruct container *cache_entries)\n{\n\t/*\n\t * Get information of all renames which occured between 'oTree' and\n\t * 'tree'. We need the three trees in the merge ('oTree', 'aTree' and\n\t * 'bTree') to be able to associate the correct cache entries with the\n\t * rename information. 'tree' is always equal to either aTree or bTree.\n\t */\n\tint i;\n\tstruct diff_options diff_opts;\n\tstruct container *result\n\t\t= xcalloc(1, sizeof(struct container));\n\n\tdiff_setup(&diff_opts);\n\tdiff_opts.recursive = 1;\n\tdiff_opts.detect_rename = DIFF_DETECT_RENAME;\n\n\tif (diff_setup_done(&diff_opts) < 0)\n\t\tdie(\"diff_setup_done failed\");\n\n\tdiff_tree_sha1(o->object.sha1, tree->object.sha1,\n\t\t\t\"\", &diff_opts);\n\tdiffcore_std(&diff_opts);\n\n\tfor (i = 0; i < diff_queued_diff.nr; i++) {\n\t\tstruct diff_filepair *p = diff_queued_diff.queue[i];\n\n\t\tif (p->status == 'R') {\n\t\t\tstruct entry *entry = get_rename(result, p->one->path);\n\t\t\tstruct rename *rename = entry->priv;\n\n\t\t\trename->src.mode = p->one->mode;\n\t\t\trename->src.sha1 = p->one->sha1;\n\t\t\trename->src.data\n\t\t\t\t= get_cache_entry(cache_entries, p->one->path)->priv;\n\t\t\tfake_stage_data(rename->src.data, o, a, b);\n\n\t\t\trename->dest.path = p->two->path;\n\t\t\trename->dest.mode = p->two->mode;\n\t\t\trename->dest.sha1 = p->two->sha1;\n\t\t\trename->dest.data\n\t\t\t\t= get_cache_entry(cache_entries, p->two->path)->priv;\n\t\t\tfake_stage_data(rename->dest.data, o, a, b);\n\n\t\t\trename->score = p->score;\n\t\t}\n\t}\n\n\treturn result;\n}\n\nIt is not tested, evidently, since I did not get the merge-base code \nintegrated yet. But it should give you an idea.\n\nCiao,\nDscho\n"},{"id":"22647","messageId":"81b0412b0606270141x7e38af5i8a97b27e37da17bf@mail.gmail.com","threadId":"4671","inReplyTo":"7virmn9hx8.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: Notes on diffcore API","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-06-27T08:41:34Z","receivedAt":"2006-06-27T08:41:34Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 6/27/06, Junio C Hamano wrote:\n> -- >8 --\n> Notes on diffcore API\n> =====================\n\nThanks!\n\n> Diffcore Transformation\n> -----------------------\n>\n> The input file pairs recorded in the previous phase are\n> collected in diff_queued_diff (a global variable -- which means\n> that you cannot have two diffs running in parallel with the\n> current setup). This is an expandable array of pointers to\n> `struct diff_filepair` structure.\n>\n\nmerge-recursive shouldn't have any problems with that, as the\nrenames are just read in the current implementation.\nStill, it is somehow uncomfortable to see the amount of APIs\nwith the above restriction. Never know when it'll bite.\n"},{"id":"22650","messageId":"81b0412b0606270158i16ebee20me81ca2b9fa71db5c@mail.gmail.com","threadId":"4671","inReplyTo":"Pine.LNX.4.63.0606270936520.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: CFT: merge-recursive in C","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-06-27T08:58:41Z","receivedAt":"2006-06-27T08:58:41Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 6/27/06, Johannes Schindelin wrote:\n>\n> > I finally got pis^Witched enough by my platform at work and decided\n> > to start the effort of converting Fredriks git-merge-recursive to C.\n>\n> Darn. I was working on the same thing since a few days.\n\nI didn't know :)\n\n> - have you considered using run-command() instead of system()?\n\nNo. What run-program?\n\n> - in setup_index(), you set GIT_INDEX_FILE, but I do not think that the\n> rest of git picks up on it. environment.cc:get_index_file() checks if\n> the variable was set already, but not if it changed.\n\nNot even sure it's needed. Leftover from conversion\n\n> - You work with linked lists all the time. This is slow, especially for\n> the checks, if a file/directory is already there. Sorted lists would be\n> way faster there. Since you encapsulated that, it is no problem to\n> change that later (before inclusion).\n\nRight, that's why it is mostly encapsulated.\n\n> - is not \"struct commit_list\" more appropriate than \"struct graph\"?\n\nNot even properly considered it yet. It probably is.\n\n> - I always wondered why merge-recursive did not call merge-base, but did\n> its own thing. Hmm?\n\nNo idea yet.\n\n> > To my deep disappointment, it didn't work out as good as I hoped: one\n> > program I see most often and for longest time in the process list\n> > (git-diff-tree) is a too complex thing to be put directly into\n> > merge-recursive.c, so any help in this direction will be greatly\n> > appreciated.\n>\n> Maybe something like this (ripped from my fragment of merge-recursive.c):\n>\n> static struct container *get_renames(struct tree *tree,\n> struct tree *o, struct tree *a, struct tree *b,\n> struct container *cache_entries)\n...\n> It is not tested, evidently, since I did not get the merge-base code\n> integrated yet. But it should give you an idea.\n>\n\nThanks! It was something I was getting at after Junio explained it.\nWill have to wait until after work.\n"},{"id":"22660","messageId":"Pine.LNX.4.63.0606271248270.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4671","inReplyTo":"81b0412b0606270158i16ebee20me81ca2b9fa71db5c@mail.gmail.com","subject":"Re: CFT: merge-recursive in C","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-27T10:51:35Z","receivedAt":"2006-06-27T10:51:35Z","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> On 6/27/06, Johannes Schindelin wrote:\n> > \n> > > I finally got pis^Witched enough by my platform at work and decided\n> > > to start the effort of converting Fredriks git-merge-recursive to C.\n> > \n> > Darn. I was working on the same thing since a few days.\n> \n> I didn't know :)\n\nVice versa, I guess.\n\n> > - have you considered using run-command() instead of system()?\n> \n> No. What run-program?\n\nrun-command.c:run_command(). Call it like this:\n\nint return_code = run_command(\"git-read-tree\", sha1_to_hex(sha1), NULL);\n\n> > - in setup_index(), you set GIT_INDEX_FILE, but I do not think that the\n> > rest of git picks up on it. environment.cc:get_index_file() checks if\n> > the variable was set already, but not if it changed.\n> \n> Not even sure it's needed. Leftover from conversion\n\nI think it _is_ needed, in order not to mess up the current index. Setting \nthe environment variable works for exec()ed processes, but I think we need \nto add a set_index_file(const char *) to environment.c.\n\n> > - I always wondered why merge-recursive did not call merge-base, but did\n> > its own thing. Hmm?\n> \n> No idea yet.\n\nFrederik?\n\nCiao,\nDscho\n"},{"id":"22665","messageId":"81b0412b0606270453m15d65e9ap5f47071331cd3280@mail.gmail.com","threadId":"4671","inReplyTo":"Pine.LNX.4.63.0606271248270.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: CFT: merge-recursive in C","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-06-27T11:53:57Z","receivedAt":"2006-06-27T11:53:57Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 6/27/06, Johannes Schindelin wrote:\n> > > - have you considered using run-command() instead of system()?\n> >\n> > No. What run-program?\n>\n> run-command.c:run_command(). Call it like this:\n>\n> int return_code = run_command(\"git-read-tree\", sha1_to_hex(sha1), NULL);\n>\n\nOh, I see. Will convert right away.\n"},{"id":"22667","messageId":"81b0412b0606270517y199fbc5cn9e19639b01813a7f@mail.gmail.com","threadId":"4671","inReplyTo":"20060626233838.GA3121@steel.home","subject":"Re: CFT: merge-recursive in C","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-06-27T12:17:05Z","receivedAt":"2006-06-27T12:17:05Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 6/27/06, Alex Riesen wrote:\n> Hi all.\n>\n> I finally got pis^Witched enough by my platform at work and decided\n> to start the effort of converting Fredriks git-merge-recursive to C.\n> At the moment it is the only one annoyingly slow thing there.\n>\n\nJust tested it on my project. It's still the slow thing (even a bit\nslower, looks CPU bound).\n"},{"id":"22670","messageId":"Pine.LNX.4.63.0606271441320.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4671","inReplyTo":"81b0412b0606270517y199fbc5cn9e19639b01813a7f@mail.gmail.com","subject":"Re: CFT: merge-recursive in C","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-27T12:43:03Z","receivedAt":"2006-06-27T12:43:03Z","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> On 6/27/06, Alex Riesen wrote:\n> > \n> > I finally got pis^Witched enough by my platform at work and decided\n> > to start the effort of converting Fredriks git-merge-recursive to C.\n> > At the moment it is the only one annoyingly slow thing there.\n> \n> Just tested it on my project. It's still the slow thing (even a bit\n> slower, looks CPU bound).\n\nShould improve when using git-merge-tree, and a faster path_list.\n\nCiao,\nDscho\n"},{"id":"22672","messageId":"81b0412b0606270709q7f5c9958w634041f7a5e0349f@mail.gmail.com","threadId":"4671","inReplyTo":"Pine.LNX.4.63.0606271441320.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: CFT: merge-recursive in C","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-06-27T14:09:52Z","receivedAt":"2006-06-27T14:09:52Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 6/27/06, Johannes Schindelin wrote:\n> > >\n> > > I finally got pis^Witched enough by my platform at work and decided\n> > > to start the effort of converting Fredriks git-merge-recursive to C.\n> > > At the moment it is the only one annoyingly slow thing there.\n> >\n> > Just tested it on my project. It's still the slow thing (even a bit\n> > slower, looks CPU bound).\n>\n> Should improve when using git-merge-tree, and a faster path_list.\n>\n\nFor the moment the most visible next offenders are calls to update-index.\nI think about batching them (add, add, add, flush, rm, rm, flush,\nstages, flush),\nbut maybe someone have a better idea?\n"},{"id":"22678","messageId":"7vac7ya5r2.fsf@assigned-by-dhcp.cox.net","threadId":"4671","inReplyTo":"Pine.LNX.4.63.0606271248270.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: CFT: merge-recursive in C","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-27T17:05:37Z","receivedAt":"2006-06-27T17:05:37Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n>> > - I always wondered why merge-recursive did not call merge-base, but did\n>> > its own thing. Hmm?\n>> \n>> No idea yet.\n\nA somewhat related issue is that when one head is given I'd\nstrongly prefer that merge-recursive did not call merge-base nor\ndid its own thing (that is, for the top-level). Otherwise we\ncannot use it for historyless three tree merge that we need for\nrebase/revert/cherry-pick.\n"},{"id":"22696","messageId":"7vbqse6unx.fsf@assigned-by-dhcp.cox.net","threadId":"4671","inReplyTo":"81b0412b0606270141x7e38af5i8a97b27e37da17bf@mail.gmail.com","subject":"Re: Notes on diffcore API","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-27T23:33:22Z","receivedAt":"2006-06-27T23:33:22Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Alex Riesen\" writes:\n\n> On 6/27/06, Junio C Hamano wrote:\n>> -- >8 --\n>> Notes on diffcore API\n>> =====================\n>\n> Thanks!\n>\n>> Diffcore Transformation\n>> -----------------------\n>>\n>> The input file pairs recorded in the previous phase are\n>> collected in diff_queued_diff (a global variable -- which means\n>> that you cannot have two diffs running in parallel with the\n>> current setup). This is an expandable array of pointers to\n>> `struct diff_filepair` structure.\n>>\n>\n> merge-recursive shouldn't have any problems with that, as the\n> renames are just read in the current implementation.\n> Still, it is somehow uncomfortable to see the amount of APIs\n> with the above restriction. Never know when it'll bite.\n\nI think it is simply the matter of moving diff_queued_diff a\nfield in diff_optionss structure and adding an extra parameter\nto point at the current diff_options to handful functions if we\never need to support it. I haven't bothered doing that because\nwe haven't had the need to run more than one diff at once.\n"},{"id":"22707","messageId":"20060628063747.GA983@informatik.uni-freiburg.de","threadId":"4671","inReplyTo":"20060626233838.GA3121@steel.home","subject":"Re: CFT: merge-recursive in C","fromName":"Uwe Zeisberger","fromEmail":"zeisberg@informatik.uni-freiburg.de","sentAt":"2006-06-28T06:37:48Z","receivedAt":"2006-06-28T06:37:48Z","isPatch":false,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"Hello Alex,\n\n> +// does not belong here\nSome C compiler (e.g. Sun Forte) don't like C++-style comments.\n\n(So the line could read:\n\n /* \"//\" does not belong here :-) */\n\n)\n\nBest regards\nUwe\n\n-- \nUwe Zeisberger\n\nhttp://www.google.com/search?q=1+degree+celsius+in+kelvin\n"},{"id":"22709","messageId":"81b0412b0606280032j2cd6135bpdd48babddd4da98f@mail.gmail.com","threadId":"4671","inReplyTo":"20060628063747.GA983@informatik.uni-freiburg.de","subject":"Re: CFT: merge-recursive in C","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-06-28T07:32:57Z","receivedAt":"2006-06-28T07:32:57Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 6/28/06, Uwe Zeisberger wrote:\n> > +// does not belong here\n> Some C compiler (e.g. Sun Forte) don't like C++-style comments.\n\nYep, I'll change them\n"},{"id":"22710","messageId":"Pine.LNX.4.63.0606280934550.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4671","inReplyTo":"7vbqse6unx.fsf@assigned-by-dhcp.cox.net","subject":"Re: Notes on diffcore API","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-28T07:36:00Z","receivedAt":"2006-06-28T07:36:00Z","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, Junio C Hamano wrote:\n\n> \"Alex Riesen\" writes:\n> \n> > On 6/27/06, Junio C Hamano wrote:\n> >> -- >8 --\n> >> Notes on diffcore API\n> >> =====================\n> >\n> > Thanks!\n> >\n> >> Diffcore Transformation\n> >> -----------------------\n> >>\n> >> The input file pairs recorded in the previous phase are\n> >> collected in diff_queued_diff (a global variable -- which means\n> >> that you cannot have two diffs running in parallel with the\n> >> current setup). This is an expandable array of pointers to\n> >> `struct diff_filepair` structure.\n> >>\n> >\n> > merge-recursive shouldn't have any problems with that, as the\n> > renames are just read in the current implementation.\n> > Still, it is somehow uncomfortable to see the amount of APIs\n> > with the above restriction. Never know when it'll bite.\n> \n> I think it is simply the matter of moving diff_queued_diff a\n> field in diff_optionss structure and adding an extra parameter\n> to point at the current diff_options to handful functions if we\n> ever need to support it. I haven't bothered doing that because\n> we haven't had the need to run more than one diff at once.\n\nAnd we shouldn't bother until we need it. It has a small performance \nimpact, and the code gets more ugly.\n\nCiao,\nDscho\n"},{"id":"22722","messageId":"7v64il4otl.fsf@assigned-by-dhcp.cox.net","threadId":"4671","inReplyTo":"20060628063747.GA983@informatik.uni-freiburg.de","subject":"Re: CFT: merge-recursive in C","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-28T09:22:30Z","receivedAt":"2006-06-28T09:22:30Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Uwe Zeisberger writes:\n\n> Hello Alex,\n>\n>> +// does not belong here\n> Some C compiler (e.g. Sun Forte) don't like C++-style comments.\n\nHeh, I said something like that last year and was scolded by\nLinus who responded \"what century are you living in?\" ;-).\n"},{"id":"22743","messageId":"20060628150647.GA16935@trixie.casa.cgf.cx","threadId":"4671","inReplyTo":"20060626233838.GA3121@steel.home","subject":"Re: CFT: merge-recursive in C","fromName":"Christopher Faylor","fromEmail":"me@cgf.cx","sentAt":"2006-06-28T15:06:47Z","receivedAt":"2006-06-28T15:06:47Z","isPatch":false,"sender":{"key":"me@cgf.cx","avatar":null},"body":"On Tue, Jun 27, 2006 at 01:38:38AM +0200, Alex Riesen wrote:\n>It still uses some calls to git programs (git-update-index,\n>git-hash-object, git-diff-tree and git-write-tree), and merge(1) has\n>the labels (-L) missing - I was unsure how to tackle this on windows -\n>it has only argv[1].\n\nActually, Windows should behave the same as Linux wrt argv handling.\nYou can use argv[1] ... argv[n] modulo any differences in command line\nquoting.\n\nOn Windows the arguments are broken into individual components by the\nruntime, e.g., MSVCRT.dll or Cygwin1.dll.\n\ncgf\n"},{"id":"22762","messageId":"20060629003837.GB27507@steel.home","threadId":"4671","inReplyTo":"20060628150647.GA16935@trixie.casa.cgf.cx","subject":"Re: CFT: merge-recursive in C","fromName":"Alex Riesen","fromEmail":"fork0@t-online.de","sentAt":"2006-06-29T00:38:37Z","receivedAt":"2006-06-29T00:38:37Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Christopher Faylor, Wed, Jun 28, 2006 17:06:47 +0200:\n> >It still uses some calls to git programs (git-update-index,\n> >git-hash-object, git-diff-tree and git-write-tree), and merge(1) has\n> >the labels (-L) missing - I was unsure how to tackle this on windows -\n> >it has only argv[1].\n> \n> Actually, Windows should behave the same as Linux wrt argv handling.\n> You can use argv[1] ... argv[n] modulo any differences in command line\n> quoting.\n\nwhich leaves us (without quoting) with exactly one argument. argv[1],\naka GetCommandLine.\n\n> On Windows the arguments are broken into individual components by the\n> runtime, e.g., MSVCRT.dll or Cygwin1.dll.\n\nAnd the rules for quoting are the same for ms and cygwin? It's just\npassing arguments between cygwin programs and windows natives never\nworks as one might them expect. Try passing \"^\" to a batch script (to\na perl script with cmd wrapper around it).\n"},{"id":"22764","messageId":"20060629004922.GG20940@trixie.casa.cgf.cx","threadId":"4671","inReplyTo":"20060629003837.GB27507@steel.home","subject":"Re: CFT: merge-recursive in C","fromName":"Christopher Faylor","fromEmail":"me@cgf.cx","sentAt":"2006-06-29T00:49:22Z","receivedAt":"2006-06-29T00:49:22Z","isPatch":false,"sender":{"key":"me@cgf.cx","avatar":null},"body":"On Thu, Jun 29, 2006 at 02:38:37AM +0200, Alex Riesen wrote:\n>Christopher Faylor, Wed, Jun 28, 2006 17:06:47 +0200:\n>>>It still uses some calls to git programs (git-update-index,\n>>>git-hash-object, git-diff-tree and git-write-tree), and merge(1) has\n>>>the labels (-L) missing - I was unsure how to tackle this on windows -\n>>>it has only argv[1].\n>>\n>>Actually, Windows should behave the same as Linux wrt argv handling.\n>>You can use argv[1] ... argv[n] modulo any differences in command line\n>>quoting.\n>\n>which leaves us (without quoting) with exactly one argument. argv[1],\n>aka GetCommandLine.\n>\n>>On Windows the arguments are broken into individual components by the\n>>runtime, e.g., MSVCRT.dll or Cygwin1.dll.\n>\n>And the rules for quoting are the same for ms and cygwin?\n\nProbably not but I was the one who raised the issue of quoting, not you.\nQuoting is irrelevant to the general assertion that there is only an\nargv[1] on Windows. If that is the behavior that you're seeing then\nsomething is wrong in the way the program is being invoked.\n\nMaybe I'm missing something here and you're talking about some specific\ncase in git. It's hard to see how anyone could make this assertion\notherwise.\n\ncgf\n"}]}