{"thread":{"id":"12492","subject":"[RFH] bug in unpack_trees","startedAt":"2008-03-04T11:59:41Z","lastAt":"2008-03-14T14:09:01Z","messageCount":9,"participants":["Jeff King","Linus Torvalds","Daniel Barkalow","John Goerzen"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"70929","messageId":"20080304115940.GA5260@sigill.intra.peff.net","threadId":"12492","inReplyTo":null,"subject":"[RFH] bug in unpack_trees","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-03-04T11:59:41Z","receivedAt":"2008-03-04T11:59:41Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"I am tracking down a bug in unpack_trees, but I can't seem to find the\nexact problem; I'm hoping to get help from people who have touched this\ncode a bit more than I have.\n\nYou can see the problem with this script:\n\n  # make a repo\n  mkdir repo && cd repo && git init\n\n  # make a directory which will become a df conflict\n  mkdir df\n  echo content >df/file\n  git add df/file\n  git commit -m one\n\n  # and save a copy of the index\n  git ls-files >index1\n\n  # now make a new commit that has the df conflict and\n  # a newly added file\n  rm -rf df\n  echo content >df\n  git add df\n  echo content >new\n  git add new\n  git commit -m two\n\n  # now this should put our index exactly back to 'one'\n  git reset --hard HEAD^\n\n  # but it doesn't\n  git ls-files >index2\n  diff -u index1 index2\n\nThe 'new' file is still in the index, and it shouldn't be. It's actually\nnot git-reset to blame, but the \"git read-tree -u --reset HEAD^\" that it\ncalls. The problem reproduces with every version of git I tried, so I\nsuspect it is as old as unpack_trees.\n\nAs far as I can tell, the D/F conflict somehow gets the list merge out\nof sync. In unpack_trees_rec, every cache entry we look up gets compared\nto the first tree entry, but because we are out of sync, the tree entry\nwill always become the new \"first\" (it looks like this test is supposed\nto be for processing foo/ before foo/bar, and shouldn't otherwise\ntrigger). Because \"first\" and \"cache_name\" don't match, we don't realize\nwe haven't found an entry missing from the tree, and we don't trigger\nthe removal code.\n\nSo where I need help is figuring out how the traversal is _supposed_ to\nwork. I.e., why does it get out of sync on the D/F case? I'm sure it's\nprobably a one-liner fix, but I just don't see it.\n\n-Peff\n"},{"id":"70995","messageId":"alpine.LFD.1.00.0803041325370.12253@woody.linux-foundation.org","threadId":"12492","inReplyTo":"20080304115940.GA5260@sigill.intra.peff.net","subject":"Re: [RFH] bug in unpack_trees","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-03-04T21:31:44Z","receivedAt":"2008-03-04T21:31:44Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 4 Mar 2008, Jeff King wrote:\n>\n> I am tracking down a bug in unpack_trees, but I can't seem to find the\n> exact problem; I'm hoping to get help from people who have touched this\n> code a bit more than I have.\n\nOk, I haven't (the blame for that unpack_trees function lies mainly at \nDscho, I think ;), and now that I'm looking at it more closely I really \ndon't think unpack_trees() is salvageable.\n\nI tried. I can't make it work.\n\nThe only really sane way to traverse trees in parallel is with the \nwalk-tree.c functionality (ie using \"traverse_trees()\"), which is quite \nstraightforward and rather simple, and which I can pretty much guarantee \nworks.\n\nIn contrast, the things that unpack_trees() does to try to figure out how \nto mix in the index into the pot really doesn't work.\n\nI'll take a good hard look at trying to convert users of unpack_trees() \ninto traverse_trees(), or perhaps even convert \"unpack_trees()\" itself.\n\n\t\tLinus\n"},{"id":"71035","messageId":"alpine.LNX.1.00.0803050130190.19665@iabervon.org","threadId":"12492","inReplyTo":"alpine.LFD.1.00.0803041325370.12253@woody.linux-foundation.org","subject":"Re: [RFH] bug in unpack_trees","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2008-03-05T06:47:57Z","receivedAt":"2008-03-05T06:47:57Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Tue, 4 Mar 2008, Linus Torvalds wrote:\n\n> On Tue, 4 Mar 2008, Jeff King wrote:\n> >\n> > I am tracking down a bug in unpack_trees, but I can't seem to find the\n> > exact problem; I'm hoping to get help from people who have touched this\n> > code a bit more than I have.\n> \n> Ok, I haven't (the blame for that unpack_trees function lies mainly at \n> Dscho, I think ;), and now that I'm looking at it more closely I really \n> don't think unpack_trees() is salvageable.\n\nIt was mostly me, 2.5 years ago in a file with a different name.\n\n> I tried. I can't make it work.\n> \n> The only really sane way to traverse trees in parallel is with the \n> walk-tree.c functionality (ie using \"traverse_trees()\"), which is quite \n> straightforward and rather simple, and which I can pretty much guarantee \n> works.\n> \n> In contrast, the things that unpack_trees() does to try to figure out how \n> to mix in the index into the pot really doesn't work.\n\nThe thing that's hopeless isn't including the index; it's including the \nindex that's simultaneously being regenerated. In this case, the mode 0 \nentry for df is getting dropped in order to not have both a \"remove df\" \nentry and a create \"df/file\" entry, and this means that the position in \nthe index is one entry later than it should be, skipping over \"new\", which \nthen doesn't get touched.\n\nOf course, regenerating the same index is not only very difficult but \ninefficient, because it involves adding and removing elements from the \nmiddle of an array. The sensible thing is just to generate a new \nin-memory index and swap it in on success at the end. This makes the \nposition update trivial (increment the position if you use the entry) and \nthe result generation efficient. In the process, we could have a separate \nlist of things to unlink() that aren't stored as weird index entries.\n\n> I'll take a good hard look at trying to convert users of unpack_trees() \n> into traverse_trees(), or perhaps even convert \"unpack_trees()\" itself.\n\nI'll see if I can get something sensible worked out Wednesday afternoon.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"71091","messageId":"alpine.LFD.1.00.0803050750400.12253@woody.linux-foundation.org","threadId":"12492","inReplyTo":"alpine.LNX.1.00.0803050130190.19665@iabervon.org","subject":"Re: [RFH] bug in unpack_trees","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-03-05T15:56:11Z","receivedAt":"2008-03-05T15:56:11Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 5 Mar 2008, Daniel Barkalow wrote:\n> \n> The thing that's hopeless isn't including the index; it's including the \n> index that's simultaneously being regenerated.\n\nYeah. I was thinking about just putting the result in a new index. It's \n*usually* what the user wants anyway. The whole complexity with updating \nthe old index is really nasty.\n\nThere are other complexities there, but the index one is the worst.\n\nWhen doing a stupid try at using \"traverse_trees()\" (which in itself was \nnot that easy - traverse_trees() is a fundamentally simpler walker and \n_different_ enough to not match well), one of the bigger issues is that \ntraverse_trees() wants to do the directories in a separate phase from the \nfiles (becasue they sort differently), and that coupled with the fact that \nwe do a kind of \"read-modify-write\" on the index makes it all really ugly.\n\nI'm still working on it, but it's nastier than I was hoping for. Maybe you \ncan come up with a better solution.\n\n\t\tLinus\n"},{"id":"71157","messageId":"alpine.LFD.1.00.0803051613230.12253@woody.linux-foundation.org","threadId":"12492","inReplyTo":"alpine.LFD.1.00.0803050750400.12253@woody.linux-foundation.org","subject":"Re: [RFH] bug in unpack_trees","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-03-06T00:35:39Z","receivedAt":"2008-03-06T00:35:39Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 5 Mar 2008, Linus Torvalds wrote:\n> \n> I'm still working on it, but it's nastier than I was hoping for. Maybe you \n> can come up with a better solution.\n\nOk, this doesn't actually fix the bug that Jeff found, because I tried \nvery hard to make sure it has the exact same behaviour as we used to have, \nbut what it does is to re-implement unpack_trees() in terms of \ntraverse_trees().\n\nI'm planning on splitting this diff up a bit, but before I do that I \nwanted to send it out to people to look at, to see if somebody can find \nany issues with it.\n\nQuite frankly, I'm not happy about how it adds more lines than it deletes, \nbut if you look at the patch, you'll quickly see the reason for why I \nthink this is a huge improvement anyway: compare the functions I add to \nthe ones I remove.\n\nIn particular, I remove the function from hell: unpack_trees_rec() used to \nbe this really quite unreadable 206-line monster function with a loop and \nvarious rather hard to understand non-local behaviours (hands up anybody \nwho understands how skip_entry works, or the df_conflict_list thing?).\n\nYes, I could have tried to just split that one function up, but I wanted \nto also really try to get rid of the whole use of that tree_entry_list, \nand just rewrite it to use an existing tree walker. Of course, I had to \nmake the existing tree walker a bit smarter in the process.\n\nThe new code isn't exactly simple either, but it tries to be much more \n\"local\", and while the replacement for unpack_trees_rec() is still \ncomplicated, it's now split into several smaller functions, but perhaps \nmost importantly, the \"top-level\" function (called \"unpack_callback()\") \nnow just handles unpacking one name at a time.\n\nIn short, I think this is an improvement, but it is a fairly big patch, \nand it essentially totally rewrites what used to be one of the most \ncomplicated functions in git. So maybe there's some bug there, but \nhopefully it's now much more straightforward and less arbitrary.\n\n[ Btw, the complexity is now in another part - it's in the code that \n  compares git pathnames without even linearizing it - see the whole dance \n  in \"do_compare_entry()\" where we recursively walk the chain of directory \n  traversal entries in order to compare a cache_entry to the name of a \n  directory walk.\n\n  So the number of lines in \"unpack-trees.c\" actually *does* go down \n  despite the functions being split up - which usually causes more lines \n  rather then fewer - but that decrease in line numbers is more than made \n  up for by the new helper functions to compare and linearize the tree \n  traversal name (setup_traverse_info, make_traverse_path and the afore- \n  mentioned compare_entry).\n\n  Maybe I could have done the tree traversal without that whole change to \n  how we keep track of the base, but I wanted to keep track of some \n  recursive info anyway, so handling the name there in that info structure \n  seemed like a really good idea. ]\n\nComments?\n\n\t\tLinus\n\n----\n cache.h        |    1 +\n merge-tree.c   |   59 ++++---\n read-cache.c   |   35 ++++\n tree-walk.c    |   72 ++++++--\n tree-walk.h    |   23 ++-\n unpack-trees.c |  530 ++++++++++++++++++++++++++------------------------------\n 6 files changed, 394 insertions(+), 326 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex e230302..6eb16cb 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -536,6 +536,7 @@ extern int create_symref(const char *ref, const char *refs_heads_master, const c\n extern int validate_headref(const char *ref);\n \n extern int base_name_compare(const char *name1, int len1, int mode1, const char *name2, int len2, int mode2);\n+extern int df_name_compare(const char *name1, int len1, int mode1, const char *name2, int len2, int mode2);\n extern int cache_name_compare(const char *name1, int len1, const char *name2, int len2);\n \n extern void *read_object_with_reference(const unsigned char *sha1,\ndiff --git a/merge-tree.c b/merge-tree.c\nindex e083246..eed0408 100644\n--- a/merge-tree.c\n+++ b/merge-tree.c\n@@ -168,7 +168,13 @@ static struct merge_list *create_entry(unsigned stage, unsigned mode, const unsi\n \treturn res;\n }\n \n-static void resolve(const char *base, struct name_entry *branch1, struct name_entry *result)\n+static char *traverse_path(const struct traverse_info *info, const struct name_entry *n)\n+{\n+\tchar *path = xmalloc(traverse_path_len(info, n) + 1);\n+\treturn make_traverse_path(path, info, n);\n+}\n+\n+static void resolve(const struct traverse_info *info, struct name_entry *branch1, struct name_entry *result)\n {\n \tstruct merge_list *orig, *final;\n \tconst char *path;\n@@ -177,7 +183,7 @@ static void resolve(const char *base, struct name_entry *branch1, struct name_en\n \tif (!branch1)\n \t\treturn;\n \n-\tpath = xstrdup(mkpath(\"%s%s\", base, result->path));\n+\tpath = traverse_path(info, result);\n \torig = create_entry(2, branch1->mode, branch1->sha1, path);\n \tfinal = create_entry(0, result->mode, result->sha1, path);\n \n@@ -186,9 +192,8 @@ static void resolve(const char *base, struct name_entry *branch1, struct name_en\n \tadd_merge_entry(final);\n }\n \n-static int unresolved_directory(const char *base, struct name_entry n[3])\n+static int unresolved_directory(const struct traverse_info *info, struct name_entry n[3])\n {\n-\tint baselen, pathlen;\n \tchar *newbase;\n \tstruct name_entry *p;\n \tstruct tree_desc t[3];\n@@ -204,13 +209,7 @@ static int unresolved_directory(const char *base, struct name_entry n[3])\n \t}\n \tif (!S_ISDIR(p->mode))\n \t\treturn 0;\n-\tbaselen = strlen(base);\n-\tpathlen = tree_entry_len(p->path, p->sha1);\n-\tnewbase = xmalloc(baselen + pathlen + 2);\n-\tmemcpy(newbase, base, baselen);\n-\tmemcpy(newbase + baselen, p->path, pathlen);\n-\tmemcpy(newbase + baselen + pathlen, \"/\", 2);\n-\n+\tnewbase = traverse_path(info, p);\n \tbuf0 = fill_tree_descriptor(t+0, n[0].sha1);\n \tbuf1 = fill_tree_descriptor(t+1, n[1].sha1);\n \tbuf2 = fill_tree_descriptor(t+2, n[2].sha1);\n@@ -223,8 +222,7 @@ static int unresolved_directory(const char *base, struct name_entry n[3])\n \treturn 1;\n }\n \n-\n-static struct merge_list *link_entry(unsigned stage, const char *base, struct name_entry *n, struct merge_list *entry)\n+static struct merge_list *link_entry(unsigned stage, const struct traverse_info *info, struct name_entry *n, struct merge_list *entry)\n {\n \tconst char *path;\n \tstruct merge_list *link;\n@@ -234,17 +232,17 @@ static struct merge_list *link_entry(unsigned stage, const char *base, struct na\n \tif (entry)\n \t\tpath = entry->path;\n \telse\n-\t\tpath = xstrdup(mkpath(\"%s%s\", base, n->path));\n+\t\tpath = traverse_path(info, n);\n \tlink = create_entry(stage, n->mode, n->sha1, path);\n \tlink->link = entry;\n \treturn link;\n }\n \n-static void unresolved(const char *base, struct name_entry n[3])\n+static void unresolved(const struct traverse_info *info, struct name_entry n[3])\n {\n \tstruct merge_list *entry = NULL;\n \n-\tif (unresolved_directory(base, n))\n+\tif (unresolved_directory(info, n))\n \t\treturn;\n \n \t/*\n@@ -252,9 +250,9 @@ static void unresolved(const char *base, struct name_entry n[3])\n \t * list has the stages in order - link_entry adds new\n \t * links at the front.\n \t */\n-\tentry = link_entry(3, base, n + 2, entry);\n-\tentry = link_entry(2, base, n + 1, entry);\n-\tentry = link_entry(1, base, n + 0, entry);\n+\tentry = link_entry(3, info, n + 2, entry);\n+\tentry = link_entry(2, info, n + 1, entry);\n+\tentry = link_entry(1, info, n + 0, entry);\n \n \tadd_merge_entry(entry);\n }\n@@ -288,36 +286,41 @@ static void unresolved(const char *base, struct name_entry n[3])\n  * The successful merge rules are the same as for the three-way merge\n  * in git-read-tree.\n  */\n-static void threeway_callback(int n, unsigned long mask, struct name_entry *entry, const char *base)\n+static int threeway_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *entry, struct traverse_info *info)\n {\n \t/* Same in both? */\n \tif (same_entry(entry+1, entry+2)) {\n \t\tif (entry[0].sha1) {\n-\t\t\tresolve(base, NULL, entry+1);\n-\t\t\treturn;\n+\t\t\tresolve(info, NULL, entry+1);\n+\t\t\treturn mask;\n \t\t}\n \t}\n \n \tif (same_entry(entry+0, entry+1)) {\n \t\tif (entry[2].sha1 && !S_ISDIR(entry[2].mode)) {\n-\t\t\tresolve(base, entry+1, entry+2);\n-\t\t\treturn;\n+\t\t\tresolve(info, entry+1, entry+2);\n+\t\t\treturn mask;\n \t\t}\n \t}\n \n \tif (same_entry(entry+0, entry+2)) {\n \t\tif (entry[1].sha1 && !S_ISDIR(entry[1].mode)) {\n-\t\t\tresolve(base, NULL, entry+1);\n-\t\t\treturn;\n+\t\t\tresolve(info, NULL, entry+1);\n+\t\t\treturn mask;\n \t\t}\n \t}\n \n-\tunresolved(base, entry);\n+\tunresolved(info, entry);\n+\treturn mask;\n }\n \n static void merge_trees(struct tree_desc t[3], const char *base)\n {\n-\ttraverse_trees(3, t, base, threeway_callback);\n+\tstruct traverse_info info;\n+\n+\tsetup_traverse_info(&info, base);\n+\tinfo.fn = threeway_callback;\n+\ttraverse_trees(3, t, &info);\n }\n \n static void *get_tree_descriptor(struct tree_desc *desc, const char *rev)\ndiff --git a/read-cache.c b/read-cache.c\nindex 657f0c5..bf649a3 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -351,6 +351,41 @@ int base_name_compare(const char *name1, int len1, int mode1,\n \treturn (c1 < c2) ? -1 : (c1 > c2) ? 1 : 0;\n }\n \n+/*\n+ * df_name_compare() is identical to base_name_compare(), except it\n+ * compares conflicting directory/file entries as equal. Note that\n+ * while a directory name compares as equal to a regular file, they\n+ * then individually compare _differently_ to a filename that has\n+ * a dot after the basename (because '\\0' < '.' < '/').\n+ *\n+ * This is used by routines that want to traverse the git namespace\n+ * but then handle conflicting entries together when possible.\n+ */\n+int df_name_compare(const char *name1, int len1, int mode1,\n+\t\t    const char *name2, int len2, int mode2)\n+{\n+\tint len = len1 < len2 ? len1 : len2, cmp;\n+\tunsigned char c1, c2;\n+\n+\tcmp = memcmp(name1, name2, len);\n+\tif (cmp)\n+\t\treturn cmp;\n+\t/* Directories and files compare equal (same length, same name) */\n+\tif (len1 == len2)\n+\t\treturn 0;\n+\tc1 = name1[len];\n+\tif (!c1 && S_ISDIR(mode1))\n+\t\tc1 = '/';\n+\tc2 = name2[len];\n+\tif (!c2 && S_ISDIR(mode2))\n+\t\tc2 = '/';\n+\tif (c1 == '/' && !c2)\n+\t\treturn 0;\n+\tif (c2 == '/' && !c1)\n+\t\treturn 0;\n+\treturn c1 - c2;\n+}\n+\n int cache_name_compare(const char *name1, int flags1, const char *name2, int flags2)\n {\n \tint len1 = flags1 & CE_NAMEMASK;\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 142205d..5134baf 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -62,9 +62,9 @@ void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)\n \n static int entry_compare(struct name_entry *a, struct name_entry *b)\n {\n-\treturn base_name_compare(\n-\t\t\ta->path, tree_entry_len(a->path, a->sha1), a->mode,\n-\t\t\tb->path, tree_entry_len(b->path, b->sha1), b->mode);\n+\tint len1 = tree_entry_len(a->path, a->sha1);\n+\tint len2 = tree_entry_len(b->path, b->sha1);\n+\treturn df_name_compare(a->path, len1, a->mode, b->path, len2, b->mode);\n }\n \n static void entry_clear(struct name_entry *a)\n@@ -104,21 +104,55 @@ int tree_entry(struct tree_desc *desc, struct name_entry *entry)\n \treturn 1;\n }\n \n-void traverse_trees(int n, struct tree_desc *t, const char *base, traverse_callback_t callback)\n+void setup_traverse_info(struct traverse_info *info, const char *base)\n {\n+\tint pathlen = strlen(base);\n+\n+\tmemset(info, 0, sizeof(*info));\n+\tif (pathlen && base[pathlen-1] == '/')\n+\t\tpathlen--;\n+\tinfo->pathlen = pathlen ? pathlen + 1 : 0;\n+\tinfo->name.path = base;\n+\tinfo->name.sha1 = (void *)(base + pathlen + 1);\n+}\n+\n+char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n)\n+{\n+\tint len = tree_entry_len(n->path, n->sha1);\n+\tint pathlen = info->pathlen;\n+\n+\tpath[pathlen + len] = 0;\n+\tfor (;;) {\n+\t\tmemcpy(path + pathlen, n->path, len);\n+\t\tif (!pathlen)\n+\t\t\tbreak;\n+\t\tpath[--pathlen] = '/';\n+\t\tn = &info->name;\n+\t\tlen = tree_entry_len(n->path, n->sha1);\n+\t\tinfo = info->prev;\n+\t\tpathlen -= len;\n+\t}\n+\treturn path;\n+}\n+\n+int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)\n+{\n+\tint ret = 0;\n \tstruct name_entry *entry = xmalloc(n*sizeof(*entry));\n \n \tfor (;;) {\n \t\tunsigned long mask = 0;\n+\t\tunsigned long dirmask = 0;\n+\t\tstruct name_entry *p = entry;\n \t\tint i, last;\n \n \t\tlast = -1;\n-\t\tfor (i = 0; i < n; i++) {\n+\t\tfor (i = 0; i < n; i++, p++) {\n \t\t\tif (!t[i].size)\n \t\t\t\tcontinue;\n-\t\t\tentry_extract(t+i, entry+i);\n+\t\t\tentry_extract(t+i, p);\n \t\t\tif (last >= 0) {\n-\t\t\t\tint cmp = entry_compare(entry+i, entry+last);\n+\t\t\t\tint cmp = entry_compare(p, entry+last);\n \n \t\t\t\t/*\n \t\t\t\t * Is the new name bigger than the old one?\n@@ -130,9 +164,13 @@ void traverse_trees(int n, struct tree_desc *t, const char *base, traverse_callb\n \t\t\t\t * Is the new name smaller than the old one?\n \t\t\t\t * Ignore all old ones\n \t\t\t\t */\n-\t\t\t\tif (cmp < 0)\n+\t\t\t\tif (cmp < 0) {\n \t\t\t\t\tmask = 0;\n+\t\t\t\t\tdirmask = 0;\n+\t\t\t\t}\n \t\t\t}\n+\t\t\tif (S_ISDIR(p->mode))\n+\t\t\t\tdirmask |= 1ul << i;\n \t\t\tmask |= 1ul << i;\n \t\t\tlast = i;\n \t\t}\n@@ -140,19 +178,25 @@ void traverse_trees(int n, struct tree_desc *t, const char *base, traverse_callb\n \t\t\tbreak;\n \n \t\t/*\n-\t\t * Update the tree entries we've walked, and clear\n-\t\t * all the unused name-entries.\n+\t\t * Clear all the unused name-entries.\n \t\t */\n \t\tfor (i = 0; i < n; i++) {\n-\t\t\tif (mask & (1ul << i)) {\n-\t\t\t\tupdate_tree_entry(t+i);\n+\t\t\tif (mask & (1ul << i))\n \t\t\t\tcontinue;\n-\t\t\t}\n \t\t\tentry_clear(entry + i);\n \t\t}\n-\t\tcallback(n, mask, entry, base);\n+\t\tret = info->fn(n, mask, dirmask, entry, info);\n+\t\tif (ret < 0)\n+\t\t\tbreak;\n+\t\tmask = ret;\n+\t\tret = 0;\n+\t\tfor (i = 0; i < n; i++) {\n+\t\t\tif (mask & (1ul << i))\n+\t\t\t\tupdate_tree_entry(t + i);\n+\t\t}\n \t}\n \tfree(entry);\n+\treturn ret;\n }\n \n static int find_tree_entry(struct tree_desc *t, const char *name, unsigned char *result, unsigned *mode)\ndiff --git a/tree-walk.h b/tree-walk.h\nindex db0fbdc..42110a4 100644\n--- a/tree-walk.h\n+++ b/tree-walk.h\n@@ -33,10 +33,27 @@ int tree_entry(struct tree_desc *, struct name_entry *);\n \n void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1);\n \n-typedef void (*traverse_callback_t)(int n, unsigned long mask, struct name_entry *entry, const char *base);\n-\n-void traverse_trees(int n, struct tree_desc *t, const char *base, traverse_callback_t callback);\n+struct traverse_info;\n+typedef int (*traverse_callback_t)(int n, unsigned long mask, unsigned long dirmask, struct name_entry *entry, struct traverse_info *);\n+int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info);\n+\n+struct traverse_info {\n+\tstruct traverse_info *prev;\n+\tstruct name_entry name;\n+\tint pathlen;\n+\n+\tunsigned long conflicts;\n+\ttraverse_callback_t fn;\n+\tvoid *data;\n+};\n \n int get_tree_entry(const unsigned char *, const char *, unsigned char *, unsigned *);\n+extern char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n);\n+extern void setup_traverse_info(struct traverse_info *info, const char *base);\n+\n+static inline int traverse_path_len(const struct traverse_info *info, const struct name_entry *n)\n+{\n+\treturn info->pathlen + tree_entry_len(n->path, n->sha1);\n+}\n \n #endif\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 3e448d8..ee9be29 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -7,270 +7,12 @@\n #include \"progress.h\"\n #include \"refs.h\"\n \n-#define DBRT_DEBUG 1\n-\n-struct tree_entry_list {\n-\tstruct tree_entry_list *next;\n-\tunsigned int mode;\n-\tconst char *name;\n-\tconst unsigned char *sha1;\n-};\n-\n-static struct tree_entry_list *create_tree_entry_list(struct tree_desc *desc)\n-{\n-\tstruct name_entry one;\n-\tstruct tree_entry_list *ret = NULL;\n-\tstruct tree_entry_list **list_p = &ret;\n-\n-\twhile (tree_entry(desc, &one)) {\n-\t\tstruct tree_entry_list *entry;\n-\n-\t\tentry = xmalloc(sizeof(struct tree_entry_list));\n-\t\tentry->name = one.path;\n-\t\tentry->sha1 = one.sha1;\n-\t\tentry->mode = one.mode;\n-\t\tentry->next = NULL;\n-\n-\t\t*list_p = entry;\n-\t\tlist_p = &entry->next;\n-\t}\n-\treturn ret;\n-}\n-\n-static int entcmp(const char *name1, int dir1, const char *name2, int dir2)\n-{\n-\tint len1 = strlen(name1);\n-\tint len2 = strlen(name2);\n-\tint len = len1 < len2 ? len1 : len2;\n-\tint ret = memcmp(name1, name2, len);\n-\tunsigned char c1, c2;\n-\tif (ret)\n-\t\treturn ret;\n-\tc1 = name1[len];\n-\tc2 = name2[len];\n-\tif (!c1 && dir1)\n-\t\tc1 = '/';\n-\tif (!c2 && dir2)\n-\t\tc2 = '/';\n-\tret = (c1 < c2) ? -1 : (c1 > c2) ? 1 : 0;\n-\tif (c1 && c2 && !ret)\n-\t\tret = len1 - len2;\n-\treturn ret;\n-}\n-\n static inline void remove_entry(int remove)\n {\n \tif (remove >= 0)\n \t\tremove_cache_entry_at(remove);\n }\n \n-static int unpack_trees_rec(struct tree_entry_list **posns, int len,\n-\t\t\t    const char *base, struct unpack_trees_options *o,\n-\t\t\t    struct tree_entry_list *df_conflict_list)\n-{\n-\tint remove;\n-\tint baselen = strlen(base);\n-\tint src_size = len + 1;\n-\tint retval = 0;\n-\n-\tdo {\n-\t\tint i;\n-\t\tconst char *first;\n-\t\tint firstdir = 0;\n-\t\tint pathlen;\n-\t\tunsigned ce_size;\n-\t\tstruct tree_entry_list **subposns;\n-\t\tstruct cache_entry **src;\n-\t\tint any_files = 0;\n-\t\tint any_dirs = 0;\n-\t\tchar *cache_name;\n-\t\tint ce_stage;\n-\t\tint skip_entry = 0;\n-\n-\t\t/* Find the first name in the input. */\n-\n-\t\tfirst = NULL;\n-\t\tcache_name = NULL;\n-\n-\t\t/* Check the cache */\n-\t\tif (o->merge && o->pos < active_nr) {\n-\t\t\t/* This is a bit tricky: */\n-\t\t\t/* If the index has a subdirectory (with\n-\t\t\t * contents) as the first name, it'll get a\n-\t\t\t * filename like \"foo/bar\". But that's after\n-\t\t\t * \"foo\", so the entry in trees will get\n-\t\t\t * handled first, at which point we'll go into\n-\t\t\t * \"foo\", and deal with \"bar\" from the index,\n-\t\t\t * because the base will be \"foo/\". The only\n-\t\t\t * way we can actually have \"foo/bar\" first of\n-\t\t\t * all the things is if the trees don't\n-\t\t\t * contain \"foo\" at all, in which case we'll\n-\t\t\t * handle \"foo/bar\" without going into the\n-\t\t\t * directory, but that's fine (and will return\n-\t\t\t * an error anyway, with the added unknown\n-\t\t\t * file case.\n-\t\t\t */\n-\n-\t\t\tcache_name = active_cache[o->pos]->name;\n-\t\t\tif (strlen(cache_name) > baselen &&\n-\t\t\t    !memcmp(cache_name, base, baselen)) {\n-\t\t\t\tcache_name += baselen;\n-\t\t\t\tfirst = cache_name;\n-\t\t\t} else {\n-\t\t\t\tcache_name = NULL;\n-\t\t\t}\n-\t\t}\n-\n-#if DBRT_DEBUG > 1\n-\t\tif (first)\n-\t\t\tfprintf(stderr, \"index %s\\n\", first);\n-#endif\n-\t\tfor (i = 0; i < len; i++) {\n-\t\t\tif (!posns[i] || posns[i] == df_conflict_list)\n-\t\t\t\tcontinue;\n-#if DBRT_DEBUG > 1\n-\t\t\tfprintf(stderr, \"%d %s\\n\", i + 1, posns[i]->name);\n-#endif\n-\t\t\tif (!first || entcmp(first, firstdir,\n-\t\t\t\t\t     posns[i]->name,\n-\t\t\t\t\t     S_ISDIR(posns[i]->mode)) > 0) {\n-\t\t\t\tfirst = posns[i]->name;\n-\t\t\t\tfirstdir = S_ISDIR(posns[i]->mode);\n-\t\t\t}\n-\t\t}\n-\t\t/* No name means we're done */\n-\t\tif (!first)\n-\t\t\tgoto leave_directory;\n-\n-\t\tpathlen = strlen(first);\n-\t\tce_size = cache_entry_size(baselen + pathlen);\n-\n-\t\tsrc = xcalloc(src_size, sizeof(struct cache_entry *));\n-\n-\t\tsubposns = xcalloc(len, sizeof(struct tree_list_entry *));\n-\n-\t\tremove = -1;\n-\t\tif (cache_name && !strcmp(cache_name, first)) {\n-\t\t\tany_files = 1;\n-\t\t\tsrc[0] = active_cache[o->pos];\n-\t\t\tremove = o->pos;\n-\t\t\tif (o->skip_unmerged && ce_stage(src[0]))\n-\t\t\t\tskip_entry = 1;\n-\t\t}\n-\n-\t\tfor (i = 0; i < len; i++) {\n-\t\t\tstruct cache_entry *ce;\n-\n-\t\t\tif (!posns[i] ||\n-\t\t\t    (posns[i] != df_conflict_list &&\n-\t\t\t     strcmp(first, posns[i]->name))) {\n-\t\t\t\tcontinue;\n-\t\t\t}\n-\n-\t\t\tif (posns[i] == df_conflict_list) {\n-\t\t\t\tsrc[i + o->merge] = o->df_conflict_entry;\n-\t\t\t\tcontinue;\n-\t\t\t}\n-\n-\t\t\tif (S_ISDIR(posns[i]->mode)) {\n-\t\t\t\tstruct tree *tree = lookup_tree(posns[i]->sha1);\n-\t\t\t\tstruct tree_desc t;\n-\t\t\t\tany_dirs = 1;\n-\t\t\t\tparse_tree(tree);\n-\t\t\t\tinit_tree_desc(&t, tree->buffer, tree->size);\n-\t\t\t\tsubposns[i] = create_tree_entry_list(&t);\n-\t\t\t\tposns[i] = posns[i]->next;\n-\t\t\t\tsrc[i + o->merge] = o->df_conflict_entry;\n-\t\t\t\tcontinue;\n-\t\t\t}\n-\n-\t\t\tif (skip_entry) {\n-\t\t\t\tsubposns[i] = df_conflict_list;\n-\t\t\t\tposns[i] = posns[i]->next;\n-\t\t\t\tcontinue;\n-\t\t\t}\n-\n-\t\t\tif (!o->merge)\n-\t\t\t\tce_stage = 0;\n-\t\t\telse if (i + 1 < o->head_idx)\n-\t\t\t\tce_stage = 1;\n-\t\t\telse if (i + 1 > o->head_idx)\n-\t\t\t\tce_stage = 3;\n-\t\t\telse\n-\t\t\t\tce_stage = 2;\n-\n-\t\t\tce = xcalloc(1, ce_size);\n-\t\t\tce->ce_mode = create_ce_mode(posns[i]->mode);\n-\t\t\tce->ce_flags = create_ce_flags(baselen + pathlen,\n-\t\t\t\t\t\t       ce_stage);\n-\t\t\tmemcpy(ce->name, base, baselen);\n-\t\t\tmemcpy(ce->name + baselen, first, pathlen + 1);\n-\n-\t\t\tany_files = 1;\n-\n-\t\t\thashcpy(ce->sha1, posns[i]->sha1);\n-\t\t\tsrc[i + o->merge] = ce;\n-\t\t\tsubposns[i] = df_conflict_list;\n-\t\t\tposns[i] = posns[i]->next;\n-\t\t}\n-\t\tif (any_files) {\n-\t\t\tif (skip_entry) {\n-\t\t\t\to->pos++;\n-\t\t\t\twhile (o->pos < active_nr &&\n-\t\t\t\t       !strcmp(active_cache[o->pos]->name,\n-\t\t\t\t\t       src[0]->name))\n-\t\t\t\t\to->pos++;\n-\t\t\t} else if (o->merge) {\n-\t\t\t\tint ret;\n-\n-#if DBRT_DEBUG > 1\n-\t\t\t\tfprintf(stderr, \"%s:\\n\", first);\n-\t\t\t\tfor (i = 0; i < src_size; i++) {\n-\t\t\t\t\tfprintf(stderr, \" %d \", i);\n-\t\t\t\t\tif (src[i])\n-\t\t\t\t\t\tfprintf(stderr, \"%06x %s\\n\", src[i]->ce_mode, sha1_to_hex(src[i]->sha1));\n-\t\t\t\t\telse\n-\t\t\t\t\t\tfprintf(stderr, \"\\n\");\n-\t\t\t\t}\n-#endif\n-\t\t\t\tret = o->fn(src, o, remove);\n-\t\t\t\tif (ret < 0)\n-\t\t\t\t\treturn ret;\n-\n-#if DBRT_DEBUG > 1\n-\t\t\t\tfprintf(stderr, \"Added %d entries\\n\", ret);\n-#endif\n-\t\t\t\to->pos += ret;\n-\t\t\t} else {\n-\t\t\t\tremove_entry(remove);\n-\t\t\t\tfor (i = 0; i < src_size; i++) {\n-\t\t\t\t\tif (src[i]) {\n-\t\t\t\t\t\tadd_cache_entry(src[i], ADD_CACHE_OK_TO_ADD|ADD_CACHE_SKIP_DFCHECK);\n-\t\t\t\t\t}\n-\t\t\t\t}\n-\t\t\t}\n-\t\t}\n-\t\tif (any_dirs) {\n-\t\t\tchar *newbase = xmalloc(baselen + 2 + pathlen);\n-\t\t\tmemcpy(newbase, base, baselen);\n-\t\t\tmemcpy(newbase + baselen, first, pathlen);\n-\t\t\tnewbase[baselen + pathlen] = '/';\n-\t\t\tnewbase[baselen + pathlen + 1] = '\\0';\n-\t\t\tif (unpack_trees_rec(subposns, len, newbase, o,\n-\t\t\t\t\t     df_conflict_list)) {\n-\t\t\t\tretval = -1;\n-\t\t\t\tgoto leave_directory;\n-\t\t\t}\n-\t\t\tfree(newbase);\n-\t\t}\n-\t\tfree(subposns);\n-\t\tfree(src);\n-\t} while (1);\n-\n- leave_directory:\n-\treturn retval;\n-}\n-\n /* Unlink the last component and attempt to remove leading\n  * directories, in case this unlink is the removal of the\n  * last entry in the directory -- empty directories are removed.\n@@ -346,15 +88,241 @@ static void check_updates(struct unpack_trees_options *o)\n \tstop_progress(&progress);\n }\n \n-int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)\n+static inline int call_unpack_fn(struct cache_entry **src, struct unpack_trees_options *o, int remove)\n+{\n+\tint ret = o->fn(src, o, remove);\n+\tif (ret > 0) {\n+\t\to->pos += ret;\n+\t\tret = 0;\n+\t}\n+\treturn ret;\n+}\n+\n+static int unpack_index_entry(struct cache_entry *ce, struct unpack_trees_options *o)\n+{\n+\tstruct cache_entry *src[5] = { ce, };\n+\tif (ce_stage(ce)) {\n+\t\tif (o->skip_unmerged) {\n+\t\t\to->pos++;\n+\t\t} else {\n+\t\t\tremove_entry(o->pos);\n+\t\t}\n+\t\treturn 0;\n+\t}\n+\treturn call_unpack_fn(src, o, o->pos);\n+}\n+\n+int traverse_trees_recursive(int n, unsigned long dirmask, unsigned long df_conflicts, struct name_entry *names, struct traverse_info *info)\n+{\n+\tint i;\n+\tstruct tree_desc t[3];\n+\tstruct traverse_info newinfo;\n+\tstruct name_entry *p;\n+\n+\tp = names;\n+\twhile (!p->mode)\n+\t\tp++;\n+\n+\tnewinfo = *info;\n+\tnewinfo.prev = info;\n+\tnewinfo.name = *p;\n+\tnewinfo.pathlen += tree_entry_len(p->path, p->sha1) + 1;\n+\tnewinfo.conflicts |= df_conflicts;\n+\n+\tfor (i = 0; i < n; i++, dirmask >>= 1) {\n+\t\tconst unsigned char *sha1 = NULL;\n+\t\tif (dirmask & 1)\n+\t\t\tsha1 = names[i].sha1;\n+\t\tfill_tree_descriptor(t+i, sha1);\n+\t}\n+\ttraverse_trees(n, t, &newinfo);\n+\treturn 0;\n+}\n+\n+/*\n+ * Compare the traverse-path to the cache entry without actually\n+ * having to generate the textual representation of the traverse\n+ * path.\n+ *\n+ * NOTE! This *only* compares up to the size of the traverse path\n+ * itself - the caller needs to do the final check for the cache\n+ * entry having more data at the end!\n+ */\n+static int do_compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)\n+{\n+\tint len, pathlen, ce_len;\n+\tconst char *ce_name;\n+\n+\tif (info->prev) {\n+\t\tint cmp = do_compare_entry(ce, info->prev, &info->name);\n+\t\tif (cmp)\n+\t\t\treturn cmp;\n+\t}\n+\tpathlen = info->pathlen;\n+\tce_len = ce_namelen(ce);\n+\n+\t/* If ce_len < pathlen then we must have previously hit \"name == directory\" entry */\n+\tif (ce_len < pathlen)\n+\t\treturn -1;\n+\n+\tce_len -= pathlen;\n+\tce_name = ce->name + pathlen;\n+\n+\tlen = tree_entry_len(n->path, n->sha1);\n+\treturn df_name_compare(ce_name, ce_len, S_IFREG, n->path, len, n->mode);\n+}\n+\n+static int compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)\n+{\n+\tint cmp = do_compare_entry(ce, info, n);\n+\tif (cmp)\n+\t\treturn cmp;\n+\n+\t/*\n+\t * Even if the beginning compared identically, the ce should\n+\t * compare as bigger than a directory leading up to it!\n+\t */\n+\treturn ce_namelen(ce) > traverse_path_len(info, n);\n+}\n+\n+static struct cache_entry *create_ce_entry(const struct traverse_info *info, const struct name_entry *n, int stage)\n+{\n+\tint len = traverse_path_len(info, n);\n+\tstruct cache_entry *ce = xcalloc(1, cache_entry_size(len));\n+\n+\tce->ce_mode = create_ce_mode(n->mode);\n+\tce->ce_flags = create_ce_flags(len, stage);\n+\thashcpy(ce->sha1, n->sha1);\n+\tmake_traverse_path(ce->name, info, n);\n+\n+\treturn ce;\n+}\n+\n+static int unpack_nondirectories(int n, unsigned long mask, unsigned long dirmask, struct cache_entry *src[5],\n+\tconst struct name_entry *names, const struct traverse_info *info, int remove)\n {\n-\tstruct tree_entry_list **posns;\n \tint i;\n-\tstruct tree_entry_list df_conflict_list;\n+\tstruct unpack_trees_options *o = info->data;\n+\tunsigned long conflicts;\n+\n+\t/* Do we have *only* directories? Nothing to do */\n+\tif (mask == dirmask && !src[0])\n+\t\treturn 0;\n+\n+\tconflicts = info->conflicts;\n+\tif (o->merge)\n+\t\tconflicts >>= 1;\n+\tconflicts |= dirmask;\n+\n+\t/*\n+\t * Ok, we've filled in up to any potential index entry in src[0],\n+\t * now do the rest.\n+\t */\n+\tfor (i = 0; i < n; i++) {\n+\t\tint stage;\n+\t\tunsigned int bit = 1ul << i;\n+\t\tif (conflicts & bit) {\n+\t\t\tsrc[i + o->merge] = o->df_conflict_entry;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!(mask & bit))\n+\t\t\tcontinue;\n+\t\tif (!o->merge)\n+\t\t\tstage = 0;\n+\t\telse if (i + 1 < o->head_idx)\n+\t\t\tstage = 1;\n+\t\telse if (i + 1 > o->head_idx)\n+\t\t\tstage = 3;\n+\t\telse\n+\t\t\tstage = 2;\n+\t\tsrc[i + o->merge] = create_ce_entry(info, names + i, stage);\n+\t}\n+\n+\tif (o->merge)\n+\t\treturn call_unpack_fn(src, o, remove);\n+\n+\tn += o->merge;\n+\tremove_entry(remove);\n+\tfor (i = 0; i < n; i++)\n+\t\tadd_cache_entry(src[i], ADD_CACHE_OK_TO_ADD|ADD_CACHE_SKIP_DFCHECK);\n+\treturn 0;\n+}\n+\n+static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)\n+{\n+\tstruct cache_entry *src[5] = { NULL, };\n+\tstruct unpack_trees_options *o = info->data;\n+\tint remove = -1;\n+\tconst struct name_entry *p = names;\n+\n+\t/* Find first entry with a real name (we could use \"mask\" too) */\n+\twhile (!p->mode)\n+\t\tp++;\n+\n+\t/* Are we supposed to look at the index too? */\n+\tif (o->merge) {\n+\t\twhile (o->pos < active_nr) {\n+\t\t\tstruct cache_entry *ce = active_cache[o->pos];\n+\t\t\tint cmp = compare_entry(ce, info, p);\n+\t\t\tif (cmp < 0) {\n+\t\t\t\tif (unpack_index_entry(ce, o) < 0)\n+\t\t\t\t\treturn -1;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tif (!cmp) {\n+\t\t\t\tif (ce_stage(ce)) {\n+\t\t\t\t\t/*\n+\t\t\t\t\t * If we skip unmerged index entries, we'll skip this\n+\t\t\t\t\t * entry *and* the tree entries associated with it!\n+\t\t\t\t\t */\n+\t\t\t\t\tif (o->skip_unmerged)\n+\t\t\t\t\t\treturn mask;\n+\t\t\t\t\tremove_entry(o->pos);\n+\t\t\t\t\tcontinue;\n+\t\t\t\t}\n+\t\t\t\tsrc[0] = ce;\n+\t\t\t\tremove = o->pos;\n+\t\t\t}\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\n+\tif (unpack_nondirectories(n, mask, dirmask, src, names, info, remove) < 0)\n+\t\treturn -1;\n+\n+\t/* Now handle any directories.. */\n+\tif (dirmask) {\n+\t\tunsigned long conflicts = mask & ~dirmask;\n+\t\tif (o->merge) {\n+\t\t\tconflicts <<= 1;\n+\t\t\tif (src[0])\n+\t\t\t\tconflicts |= 1;\n+\t\t}\n+\t\ttraverse_trees_recursive(n, dirmask, conflicts, names, info);\n+\t\treturn mask;\n+\t}\n+\n+\treturn mask;\n+}\n+\n+static int unpack_failed(struct unpack_trees_options *o, const char *message)\n+{\n+\tif (!o->gently) {\n+\t\tif (message)\n+\t\t\treturn error(message);\n+\t\treturn -1;\n+\t}\n+\tdiscard_cache();\n+\tread_cache();\n+\treturn -1;\n+}\n+\n+int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)\n+{\n \tstatic struct cache_entry *dfc;\n \n-\tmemset(&df_conflict_list, 0, sizeof(df_conflict_list));\n-\tdf_conflict_list.next = &df_conflict_list;\n+\tif (len > 4)\n+\t\tdie(\"unpack_trees takes at most four trees\");\n \tmemset(&state, 0, sizeof(state));\n \tstate.base_dir = \"\";\n \tstate.force = 1;\n@@ -368,29 +336,29 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n \to->df_conflict_entry = dfc;\n \n \tif (len) {\n-\t\tposns = xmalloc(len * sizeof(struct tree_entry_list *));\n-\t\tfor (i = 0; i < len; i++)\n-\t\t\tposns[i] = create_tree_entry_list(t+i);\n-\n-\t\tif (unpack_trees_rec(posns, len, o->prefix ? o->prefix : \"\",\n-\t\t\t\t     o, &df_conflict_list)) {\n-\t\t\tif (o->gently) {\n-\t\t\t\tdiscard_cache();\n-\t\t\t\tread_cache();\n-\t\t\t}\n-\t\t\treturn -1;\n-\t\t}\n+\t\tconst char *prefix = o->prefix ? o->prefix : \"\";\n+\t\tstruct traverse_info info;\n+\n+\t\tsetup_traverse_info(&info, prefix);\n+\t\tinfo.fn = unpack_callback;\n+\t\tinfo.data = o;\n+\n+\t\tif (traverse_trees(len, t, &info) < 0)\n+\t\t\treturn unpack_failed(o, NULL);\n \t}\n \n-\tif (o->trivial_merges_only && o->nontrivial_merge) {\n-\t\tif (o->gently) {\n-\t\t\tdiscard_cache();\n-\t\t\tread_cache();\n+\t/* Any left-over entries in the index? */\n+\tif (o->merge) {\n+\t\twhile (o->pos < active_nr) {\n+\t\t\tstruct cache_entry *ce = active_cache[o->pos];\n+\t\t\tif (unpack_index_entry(ce, o) < 0)\n+\t\t\t\treturn unpack_failed(o, NULL);\n \t\t}\n-\t\treturn o->gently ? -1 :\n-\t\t\terror(\"Merge requires file-level merging\");\n \t}\n \n+\tif (o->trivial_merges_only && o->nontrivial_merge)\n+\t\treturn unpack_failed(o, \"Merge requires file-level merging\");\n+\n \tcheck_updates(o);\n \treturn 0;\n }\n"},{"id":"71452","messageId":"alpine.LFD.1.00.0803081417040.5896@woody.linux-foundation.org","threadId":"12492","inReplyTo":"20080304115940.GA5260@sigill.intra.peff.net","subject":"Re: [RFH] bug in unpack_trees","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-03-08T22:25:03Z","receivedAt":"2008-03-08T22:25:03Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 4 Mar 2008, Jeff King wrote:\n>\n> I am tracking down a bug in unpack_trees, but I can't seem to find the\n> exact problem; I'm hoping to get help from people who have touched this\n> code a bit more than I have.\n\nOk, so I decided that I should now finally go back and look at the \noriginal bug-report that triggered my unpack-trees rewrite, now that it's \nin a form where I feel like I can actually look at the code and fix the \nproblem..\n\nBut when I just tested the bug-report case that Jeff described, it seems \nthat I fixed the bug just with my cleanup. The current git \"master\" branch \ngives the following (incorrect) output for Jeff's script:\n\n\t[torvalds@woody repo]$   diff -u index1 index2\n\t--- index1      2008-03-08 14:16:51.000000000 -0800\n\t+++ index2      2008-03-08 14:16:51.000000000 -0800\n\t@@ -1 +1,2 @@\n\t df/file\n\t+new\n\nand with all my patches it just magically works correctly and the \"git \nreset\" correctly reset the index.\n\nSo while I actually tried to be as careful as possible and do a minimal \n\"convert to cleaner code\" rather than actually fix the bug, it seems that \njust the cleanup actually did end up fixing it and there is nothing more \nto chase down.\n\nI'd love to say that I know what the original bug was, but since I \ncouldn't fix it in the first place because I couldn't read the original \ncode, I can't really say what fixed it.\n\nJeff's test-script appended just for people who can't find the original \nmessage that started this all.\n\n\t\tLinus\n\n---\n  # make a repo\n  mkdir repo && cd repo && git init\n\n  # make a directory which will become a df conflict\n  mkdir df\n  echo content >df/file\n  git add df/file\n  git commit -m one\n\n  # and save a copy of the index\n  git ls-files >index1\n\n  # now make a new commit that has the df conflict and\n  # a newly added file\n  rm -rf df\n  echo content >df\n  git add df\n  echo content >new\n  git add new\n  git commit -m two\n\n  # now this should put our index exactly back to 'one'\n  git reset --hard HEAD^\n\n  # but it doesn't\n  git ls-files >index2\n  diff -u index1 index2\n\n"},{"id":"71453","messageId":"alpine.LNX.1.00.0803081726450.19665@iabervon.org","threadId":"12492","inReplyTo":"alpine.LFD.1.00.0803081417040.5896@woody.linux-foundation.org","subject":"Re: [RFH] bug in unpack_trees","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2008-03-08T22:36:25Z","receivedAt":"2008-03-08T22:36:25Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Sat, 8 Mar 2008, Linus Torvalds wrote:\n\n> On Tue, 4 Mar 2008, Jeff King wrote:\n> >\n> > I am tracking down a bug in unpack_trees, but I can't seem to find the\n> > exact problem; I'm hoping to get help from people who have touched this\n> > code a bit more than I have.\n> \n> Ok, so I decided that I should now finally go back and look at the \n> original bug-report that triggered my unpack-trees rewrite, now that it's \n> in a form where I feel like I can actually look at the code and fix the \n> problem..\n> \n> I'd love to say that I know what the original bug was, but since I \n> couldn't fix it in the first place because I couldn't read the original \n> code, I can't really say what fixed it.\n\nThe original bug was that the position in the index being modified in \nplace got messed up by core code that discarded unnecessary REMOVE entries \nfor files in a d/f conflicting directory without reporting how many were \nremoved so that the iteration could compensate. Cleaning up the code may \nor may not have fixed it, but using separate indices would make it really \nhard to retain the bug.\n\n> Jeff's test-script appended just for people who can't find the original \n> message that started this all.\n\nHere it is as an actual test case:\n\n----------\ncommit f9eef3140fedaa10842d433e6fbf67f6b914712c\nAuthor: Daniel Barkalow <barkalow@iabervon.org>\nDate:   Wed Mar 5 15:50:36 2008 -0500\n\n    Add a test for read-tree -u --reset working despite df conflicts\n    \n    From an email by Jeff King <peff@peff.net>\n    \n    Signed-off-by: Daniel Barkalow <barkalow@iabervon.org>\n\ndiff --git a/t/t1005-read-tree-reset.sh b/t/t1005-read-tree-reset.sh\nnew file mode 100755\nindex 0000000..f1b1216\n--- /dev/null\n+++ b/t/t1005-read-tree-reset.sh\n@@ -0,0 +1,30 @@\n+#!/bin/sh\n+\n+test_description='read-tree -u --reset'\n+\n+. ./test-lib.sh\n+\n+# two-tree test\n+\n+test_expect_success 'setup' '\n+  git init &&\n+  mkdir df &&\n+  echo content >df/file &&\n+  git add df/file &&\n+  git commit -m one &&\n+  git ls-files >expect &&\n+  rm -rf df &&\n+  echo content >df &&\n+  git add df &&\n+  echo content >new &&\n+  git add new &&\n+  git commit -m two\n+'\n+\n+test_expect_failure 'reset should work' '\n+  git read-tree -u --reset HEAD^ &&\n+  git ls-files >actual &&\n+  diff -u expect actual\n+'\n+\n+test_done\n"},{"id":"71944","messageId":"20080313140005.GA30348@coredump.intra.peff.net","threadId":"12492","inReplyTo":"alpine.LFD.1.00.0803081417040.5896@woody.linux-foundation.org","subject":"Re: [RFH] bug in unpack_trees","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-03-13T14:00:05Z","receivedAt":"2008-03-13T14:00:05Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Mar 08, 2008 at 02:25:03PM -0800, Linus Torvalds wrote:\n\n> But when I just tested the bug-report case that Jeff described, it seems \n> that I fixed the bug just with my cleanup. The current git \"master\" branch \n> gives the following (incorrect) output for Jeff's script:\n\nHeh. I never meant to just dump the bug on you and run away, but I\nhaven't had much of a chance to review your patches until now. Looks\nlike Junio shook all the bugs out, though. ;) Thanks for all the hard\nwork on this.\n\nThe _real_ bug which started this, though, was actually a git-rebase\nproblem reported by John Goerzen on a private repo. I'm 99% sure that\nthis read-tree issue was the problem, but it would be nice to confirm\nit is fixed.\n\nJohn, is it possible for you to re-try that rebase and confirm that it\nworks with the current master? I deleted the repo you sent me after\nnarrowing the bug.\n\n-Peff\n"},{"id":"72083","messageId":"200803140909.02107.jgoerzen@complete.org","threadId":"12492","inReplyTo":"20080313140005.GA30348@coredump.intra.peff.net","subject":"Re: [RFH] bug in unpack_trees","fromName":"John Goerzen","fromEmail":"jgoerzen@complete.org","sentAt":"2008-03-14T14:09:01Z","receivedAt":"2008-03-14T14:09:01Z","isPatch":false,"sender":{"key":"jgoerzen@complete.org","avatar":null},"body":"On Thu March 13 2008 9:00:05 am Jeff King wrote:\n\n> John, is it possible for you to re-try that rebase and confirm that it\n> works with the current master? I deleted the repo you sent me after\n> narrowing the bug.\n\nI have just tried it on the precise test case I gave you, and it looks like \nthe problem has indeed been fixed.\n\nMany thanks to all of you that have worked on this.\n\n-- John\n"}]}