{"thread":{"id":"21004","subject":"[WIP PATCH 0/6] Merging with D/F conflicts","startedAt":"2009-09-20T05:06:09Z","lastAt":"2009-09-20T05:06:15Z","messageCount":7,"participants":["Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":6},"messages":[{"id":"123529","messageId":"1253423175-6339-1-git-send-email-gitster@pobox.com","threadId":"21004","inReplyTo":null,"subject":"[WIP PATCH 0/6] Merging with D/F conflicts","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-09-20T05:06:09Z","receivedAt":"2009-09-20T05:06:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I have been working on this on-and-off and it still is not finished, but I\nthought it would be a good place to stop, especially since this will not\nbe part of the upcoming 1.6.5 anyway.\n\nThe first three patches are preparatory clean-ups.\n\nThe fourth patch roughly corresponds to Linus's 880386c (Prepare\n'traverse_trees()' for D/F conflict lookahead, 2009-09-06), but it does\nimplement multi-entry lookahead.  It reveals why lookahead on the tree\nside alone is not sufficient by breaking a few tests.\n\nThe fifth one starts to compensate for the change in the tree side by\npreparing the side that walks the index for a similar lookahead mechanism,\nbut it does not actually implement the lookahead yet.\n\nThe last one is a debugging patch.\n\nThis change has to break the output order (but not content) of the\ndiff-index somewhat.  If you had this:\n\n    Index    Tree\n    b        b-2/c\n    b-2      b/d\n\nthe expected output order from diff-index is b, b-2, b-2/c, then b/d.  But\nif you walk the tree and the index in parallel, we would end up showing b,\nb/d, b-2 and then b-2/c.  A sad part of the story is that diff-index\nalways emits D/F conflicted entries as two independent records, so it is\nrather a bad match to the unpack_trees() framework to begin with.\n\nThe patches are designed to apply on 79b4fde (Merge branch 'maint',\n2009-09-03).\n\nJunio C Hamano (6):\n  diff-lib.c: fix misleading comments on oneway_diff()\n  unpack-trees: typofix\n  unpack_callback(): use unpack_failed() consistently\n  traverse_trees(): handle D/F conflict case sanely\n  unpack-trees.c: prepare for looking ahead in the index\n  read-tree --debug-unpack\n\n builtin-read-tree.c |   36 +++++++\n cache.h             |    2 +\n diff-lib.c          |   20 +----\n tree-walk.c         |  277 +++++++++++++++++++++++++++++++++++++++++++--------\n unpack-trees.c      |  275 ++++++++++++++++++++++++++++++++++++++------------\n unpack-trees.h      |    3 +-\n 6 files changed, 484 insertions(+), 129 deletions(-)\n"},{"id":"123533","messageId":"1253423175-6339-2-git-send-email-gitster@pobox.com","threadId":"21004","inReplyTo":"1253423175-6339-1-git-send-email-gitster@pobox.com","subject":"[WIP PATCH 1/6] diff-lib.c: fix misleading comments on oneway_diff()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-09-20T05:06:10Z","receivedAt":"2009-09-20T05:06:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"20a16eb (unpack_trees(): fix diff-index regression., 2008-03-10) adjusted\ndiff-index to the new world order since 34110cd (Make 'unpack_trees()'\nhave a separate source and destination index, 2008-03-06).  Callbacks are\nexpected to return anything non-negative as \"success\", and instead of\nreporting how many index entries they have processed, they are expected to\nadvance o->pos themselves.  The code did so, but a stale comment was left\nbehind.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n diff-lib.c |    2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/diff-lib.c b/diff-lib.c\nindex 0c74ef5..adf1c5f 100644\n--- a/diff-lib.c\n+++ b/diff-lib.c\n@@ -383,7 +383,7 @@ static inline void skip_same_name(struct cache_entry *ce, struct unpack_trees_op\n  * For diffing, the index is more important, and we only have a\n  * single tree.\n  *\n- * We're supposed to return how many index entries we want to skip.\n+ * We're supposed to advance o->pos to skip what we have already processed.\n  *\n  * This wrapper makes it all more readable, and takes care of all\n  * the fairly complex unpack_trees() semantic requirements, including\n-- \n1.6.5.rc1.90.ga3b1b\n"},{"id":"123531","messageId":"1253423175-6339-3-git-send-email-gitster@pobox.com","threadId":"21004","inReplyTo":"1253423175-6339-1-git-send-email-gitster@pobox.com","subject":"[WIP PATCH 2/6] unpack-trees: typofix","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-09-20T05:06:11Z","receivedAt":"2009-09-20T05:06:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I am not good at subject-verb concordance.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n unpack-trees.c |    2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 720f7a1..d174fe0 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -617,7 +617,7 @@ static int verify_absent(struct cache_entry *ce, const char *action,\n \t\t\t * found \"foo/.\" in the working tree.\n \t\t\t * This is tricky -- if we have modified\n \t\t\t * files that are in \"foo/\" we would lose\n-\t\t\t * it.\n+\t\t\t * them.\n \t\t\t */\n \t\t\tret = verify_clean_subdirectory(ce, action, o);\n \t\t\tif (ret < 0)\n-- \n1.6.5.rc1.90.ga3b1b\n"},{"id":"123530","messageId":"1253423175-6339-4-git-send-email-gitster@pobox.com","threadId":"21004","inReplyTo":"1253423175-6339-1-git-send-email-gitster@pobox.com","subject":"[WIP PATCH 3/6] unpack_callback(): use unpack_failed() consistently","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-09-20T05:06:12Z","receivedAt":"2009-09-20T05:06:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"When unpack_index_entry() failed, consistently call unpack_failed(),\ninstead of silently returning -1.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n unpack-trees.c |   24 ++++++++++++------------\n 1 files changed, 12 insertions(+), 12 deletions(-)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex d174fe0..c424bab 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -277,6 +277,17 @@ static int unpack_nondirectories(int n, unsigned long mask,\n \treturn 0;\n }\n \n+static int unpack_failed(struct unpack_trees_options *o, const char *message)\n+{\n+\tdiscard_index(&o->result);\n+\tif (!o->gently) {\n+\t\tif (message)\n+\t\t\treturn error(\"%s\", message);\n+\t\treturn -1;\n+\t}\n+\treturn -1;\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[MAX_UNPACK_TREES + 1] = { NULL, };\n@@ -294,7 +305,7 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str\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\t\treturn unpack_failed(o, NULL);\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tif (!cmp) {\n@@ -352,17 +363,6 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str\n \treturn mask;\n }\n \n-static int unpack_failed(struct unpack_trees_options *o, const char *message)\n-{\n-\tdiscard_index(&o->result);\n-\tif (!o->gently) {\n-\t\tif (message)\n-\t\t\treturn error(\"%s\", message);\n-\t\treturn -1;\n-\t}\n-\treturn -1;\n-}\n-\n /*\n  * N-way merge \"len\" trees.  Returns 0 on success, -1 on failure to manipulate the\n  * resulting index, -2 on failure to reflect the changes to the work tree.\n-- \n1.6.5.rc1.90.ga3b1b\n"},{"id":"123534","messageId":"1253423175-6339-5-git-send-email-gitster@pobox.com","threadId":"21004","inReplyTo":"1253423175-6339-1-git-send-email-gitster@pobox.com","subject":"[WIP PATCH 4/6] traverse_trees(): handle D/F conflict case sanely","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-09-20T05:06:13Z","receivedAt":"2009-09-20T05:06:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"traverse_trees() is supposed to call its callback with all the matching\nentries from the given trees.  The current algorithm keeps a pointer to\neach of the tree being traversed, and feeds the entry with the earliest\nname to the callback.\n\nThis breaks down if the trees being traversed looks like this:\n\n    A    B\n    t-1  t\n    t-2  u\n    t/a  v\n\nWhen we are currently looking at an entry \"t-1\" in tree A, and tree B has\nreturned \"t\", feeding \"t\" from the B and not feeding anything from A, only\nbecause \"t-1\" sorts later than \"t\", will miss an entry for a subtree \"t\"\nbehind the current entry in tree A.\n\nThis introduces extended_entry_extract() helper function that gives what\nname is expected from the tree, and implements a mechanism to look-ahead\nin the tree object using it, to make sure such a case is handled sanely.\nTraversal in tree A in the above example will first return \"t\" to match\nthat of B, and then the next request for an entry to A then returns \"t-1\".\n\nThis roughly corresponds to what Linus's \"prepare for one-entry lookahead\"\nwanted to do, but because this does implement look ahead, t6035 and t7003\nreveal that the approach would not work without adjusting the side that\nwalks the index in unpack_trees() as well.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n tree-walk.c |  277 +++++++++++++++++++++++++++++++++++++++++++++++++---------\n 1 files changed, 234 insertions(+), 43 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 02e2aed..08796c2 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -60,13 +60,6 @@ void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)\n \treturn buf;\n }\n \n-static int entry_compare(struct name_entry *a, struct name_entry *b)\n-{\n-\treturn df_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-}\n-\n static void entry_clear(struct name_entry *a)\n {\n \tmemset(a, 0, sizeof(*a));\n@@ -138,66 +131,264 @@ char *make_traverse_path(char *path, const struct traverse_info *info, const str\n \treturn path;\n }\n \n+struct tree_desc_skip {\n+\tstruct tree_desc_skip *prev;\n+\tconst void *ptr;\n+};\n+\n+struct tree_desc_x {\n+\tstruct tree_desc d;\n+\tstruct tree_desc_skip *skip;\n+};\n+\n+static int name_compare(const char *a, int a_len,\n+\t\t\tconst char *b, int b_len)\n+{\n+\tint len = (a_len < b_len) ? a_len : b_len;\n+\tint cmp = memcmp(a, b, len);\n+\tif (cmp)\n+\t\treturn cmp;\n+\treturn (a_len - b_len);\n+}\n+\n+static int check_entry_match(const char *a, int a_len, const char *b, int b_len)\n+{\n+\t/*\n+\t * The caller wants to pick *a* from a tree or nothing.\n+\t * We are looking at *b* in a tree.\n+\t *\n+\t * (0) If a and b are the same name, we are trivially happy.\n+\t *\n+\t * There are three possibilities where *a* could be hiding\n+\t * behind *b*.\n+\t *\n+\t * (1) *a* == \"t\",   *b* == \"ab\"  i.e. *b* sorts earlier than *a* no\n+\t *                                matter what.\n+\t * (2) *a* == \"t\",   *b* == \"t-2\" and \"t\" is a subtree in the tree;\n+\t * (3) *a* == \"t-2\", *b* == \"t\"   and \"t-2\" is a blob in the tree.\n+\t *\n+\t * Otherwise we know *a* won't appear in the tree without\n+\t * scanning further.\n+\t */\n+\n+\tint cmp = name_compare(a, a_len, b, b_len);\n+\n+\t/* Most common case first -- reading sync'd trees */\n+\tif (!cmp)\n+\t\treturn cmp;\n+\n+\tif (0 < cmp) {\n+\t\t/* a comes after b; it does not matter if it is case (3)\n+\t\tif (b_len < a_len && !memcmp(a, b, b_len) && a[b_len] < '/')\n+\t\t\treturn 1;\n+\t\t*/\n+\t\treturn 1; /* keep looking */\n+\t}\n+\n+\t/* b comes after a; are we looking at case (2)? */\n+\tif (a_len < b_len && !memcmp(a, b, a_len) && b[a_len] < '/')\n+\t\treturn 1; /* keep looking */\n+\n+\treturn -1; /* a cannot appear in the tree */\n+}\n+\n+/*\n+ * From the extended tree_desc, extract the first name entry, while\n+ * paying attention to the candidate \"first\" name.  Most importantly,\n+ * when looking for an entry, if there are entries that sorts earlier\n+ * in the tree object representation than that name, skip them and\n+ * process the named entry first.  We will remember that we haven't\n+ * processed the first entry yet, and in the later call skip the\n+ * entry we processed early when update_extended_entry() is called.\n+ *\n+ * E.g. if the underlying tree object has these entries:\n+ *\n+ *    blob    \"t-1\"\n+ *    blob    \"t-2\"\n+ *    tree    \"t\"\n+ *    blob    \"t=1\"\n+ *\n+ * and the \"first\" asks for \"t\", remember that we still need to\n+ * process \"t-1\" and \"t-2\" but extract \"t\".  After processing the\n+ * entry \"t\" from this call, the caller will let us know by calling\n+ * update_extended_entry() that we can remember \"t\" has been processed\n+ * already.\n+ */\n+\n+static void extended_entry_extract(struct tree_desc_x *t,\n+\t\t\t\t   struct name_entry *a,\n+\t\t\t\t   const char *first,\n+\t\t\t\t   int first_len)\n+{\n+\tconst char *path;\n+\tint len;\n+\tstruct tree_desc probe;\n+\tstruct tree_desc_skip *skip;\n+\n+\t/*\n+\t * Extract the first entry from the tree_desc, but skip the\n+\t * ones that we already returned in earlier rounds.\n+\t */\n+\twhile (1) {\n+\t\tif (!t->d.size) {\n+\t\t\tentry_clear(a);\n+\t\t\tbreak; /* not found */\n+\t\t}\n+\t\tentry_extract(&t->d, a);\n+\t\tfor (skip = t->skip; skip; skip = skip->prev)\n+\t\t\tif (a->path == skip->ptr)\n+\t\t\t\tbreak; /* found */\n+\t\tif (!skip)\n+\t\t\tbreak;\n+\t\t/* We have processed this entry already. */\n+\t\tupdate_tree_entry(&t->d);\n+\t}\n+\n+\tif (!first || !a->path)\n+\t\treturn;\n+\n+\t/*\n+\t * The caller wants \"first\" from this tree, or nothing.\n+\t */\n+\tpath = a->path;\n+\tlen = tree_entry_len(a->path, a->sha1);\n+\tswitch (check_entry_match(first, first_len, path, len)) {\n+\tcase -1:\n+\t\tentry_clear(a);\n+\tcase 0:\n+\t\treturn;\n+\tdefault:\n+\t\tbreak;\n+\t}\n+\n+\t/*\n+\t * We need to look-ahead -- we suspect that a subtree whose\n+\t * name is \"first\" may be hiding behind the current entry \"path\".\n+\t */\n+\tprobe = t->d;\n+\twhile (probe.size) {\n+\t\tentry_extract(&probe, a);\n+\t\tpath = a->path;\n+\t\tlen = tree_entry_len(a->path, a->sha1);\n+\t\tswitch (check_entry_match(first, first_len, path, len)) {\n+\t\tcase -1:\n+\t\t\tentry_clear(a);\n+\t\tcase 0:\n+\t\t\treturn;\n+\t\tdefault:\n+\t\t\tupdate_tree_entry(&probe);\n+\t\t\tbreak;\n+\t\t}\n+\t\t/* keep looking */\n+\t}\n+\tentry_clear(a);\n+}\n+\n+static void update_extended_entry(struct tree_desc_x *t, struct name_entry *a)\n+{\n+\tif (t->d.entry.path == a->path) {\n+\t\tupdate_tree_entry(&t->d);\n+\t} else {\n+\t\t/* we have returned this entry early */\n+\t\tstruct tree_desc_skip *skip = xmalloc(sizeof(*skip));\n+\t\tskip->ptr = a->path;\n+\t\tskip->prev = t->skip;\n+\t\tt->skip = skip;\n+\t}\n+}\n+\n+static void free_extended_entry(struct tree_desc_x *t)\n+{\n+\tstruct tree_desc_skip *p, *s;\n+\n+\tfor (s = t->skip; s; s = p) {\n+\t\tp = s->prev;\n+\t\tfree(s);\n+\t}\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+\tint i;\n+\tstruct tree_desc_x *tx = xcalloc(n, sizeof(*tx));\n+\n+\tfor (i = 0; i < n; i++)\n+\t\ttx[i].d = t[i];\n \n \tfor (;;) {\n-\t\tunsigned long mask = 0;\n-\t\tunsigned long dirmask = 0;\n-\t\tint i, last;\n+\t\tunsigned long mask, dirmask;\n+\t\tconst char *first = NULL;\n+\t\tint first_len = 0;\n+\t\tstruct name_entry *e;\n+\t\tint len;\n \n-\t\tlast = -1;\n \t\tfor (i = 0; i < n; i++) {\n-\t\t\tif (!t[i].size)\n+\t\t\te = entry + i;\n+\t\t\textended_entry_extract(tx + i, e, NULL, 0);\n+\t\t}\n+\n+\t\t/*\n+\t\t * A tree may have \"t-2\" at the current location even\n+\t\t * though it may have \"t\" that is a subtree behind it,\n+\t\t * and another tree may return \"t\".  We want to grab\n+\t\t * all \"t\" from all trees to match in such a case.\n+\t\t */\n+\t\tfor (i = 0; i < n; i++) {\n+\t\t\te = entry + i;\n+\t\t\tif (!e->path)\n \t\t\t\tcontinue;\n-\t\t\tentry_extract(t+i, entry+i);\n-\t\t\tif (last >= 0) {\n-\t\t\t\tint cmp = entry_compare(entry+i, entry+last);\n-\n-\t\t\t\t/*\n-\t\t\t\t * Is the new name bigger than the old one?\n-\t\t\t\t * Ignore it\n-\t\t\t\t */\n-\t\t\t\tif (cmp > 0)\n+\t\t\tlen = tree_entry_len(e->path, e->sha1);\n+\t\t\tif (!first) {\n+\t\t\t\tfirst = e->path;\n+\t\t\t\tfirst_len = len;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tif (name_compare(e->path, len, first, first_len) < 0) {\n+\t\t\t\tfirst = e->path;\n+\t\t\t\tfirst_len = len;\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (first) {\n+\t\t\tfor (i = 0; i < n; i++) {\n+\t\t\t\te = entry + i;\n+\t\t\t\textended_entry_extract(tx + i, e, first, first_len);\n+\t\t\t\t/* Cull the ones that are not the earliest */\n+\t\t\t\tif (!e->path)\n \t\t\t\t\tcontinue;\n-\t\t\t\t/*\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\t\tmask = 0;\n+\t\t\t\tlen = tree_entry_len(e->path, e->sha1);\n+\t\t\t\tif (name_compare(e->path, len, first, first_len))\n+\t\t\t\t\tentry_clear(e);\n \t\t\t}\n+\t\t}\n+\n+\t\t/* Now we have in entry[i] the earliest name from the trees */\n+\t\tmask = 0;\n+\t\tdirmask = 0;\n+\t\tfor (i = 0; i < n; i++) {\n+\t\t\tif (!entry[i].path)\n+\t\t\t\tcontinue;\n \t\t\tmask |= 1ul << i;\n \t\t\tif (S_ISDIR(entry[i].mode))\n \t\t\t\tdirmask |= 1ul << i;\n-\t\t\tlast = i;\n \t\t}\n \t\tif (!mask)\n \t\t\tbreak;\n-\t\tdirmask &= mask;\n-\n-\t\t/*\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\tcontinue;\n-\t\t\tentry_clear(entry + i);\n-\t\t}\n \t\tret = info->fn(n, mask, dirmask, entry, info);\n \t\tif (ret < 0)\n \t\t\tbreak;\n-\t\tif (ret)\n-\t\t\tmask &= ret;\n+\t\tmask &= ret;\n \t\tret = 0;\n-\t\tfor (i = 0; i < n; i++) {\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\t\t\tupdate_extended_entry(tx + i, entry + i);\n \t}\n \tfree(entry);\n+\tfor (i = 0; i < n; i++)\n+\t\tfree_extended_entry(tx + i);\n+\tfree(tx);\n \treturn ret;\n }\n \n-- \n1.6.5.rc1.90.ga3b1b\n"},{"id":"123535","messageId":"1253423175-6339-6-git-send-email-gitster@pobox.com","threadId":"21004","inReplyTo":"1253423175-6339-1-git-send-email-gitster@pobox.com","subject":"[WIP PATCH 5/6] unpack-trees.c: prepare for looking ahead in the index","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-09-20T05:06:14Z","receivedAt":"2009-09-20T05:06:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This prepares but does not yet implement a look-ahead in the index entries\nwhen traverse-trees.c decides to give us tree entries in an order that\ndoes not match what is in the index.\n\nA case where a look-ahead in the index is necessary happens when merging\nbranch B into branch A while the index matches the current branch A, using\na tree O as their common ancestor, and these three trees looks like this:\n\n   O        A       B\n   t                t\n   t-i      t-i     t-i\n   t-j      t-j\n            t/1\n            t/2\n\nThe traverse_trees() function gets \"t\", \"t-i\" and \"t\" from trees O, A and\nB first, and notices that A may have a matching \"t\" behind \"t-i\" and \"t-j\"\n(indeed it does), and tells A to give that entry instead.  After unpacking\nblob \"t\" from tree B (as it hasn't changed since O in B and A removed it,\nit will result in its removal), it descends into directory \"t/\".\n\nThe side that walked index in parallel to the tree traversal used to be\nimplemented with one pointer, o->pos, that points at the next index entry\nto be processed.  When this happens, the pointer o->pos still points at\n\"t-i\" that is the first entry.  We should be able to skip \"t-i\" and \"t-j\"\nand locate \"t/1\" from the index while the recursive invocation of\ntraverse_trees() walks and match entries found there, and later come back\nto process \"t-i\".\n\nWhile that look-ahead is not implemented yet, this adds a flag bit,\nCE_UNPACKED, to mark the entries in the index that has already been\nprocessed.  o->pos pointer has been renamed to o->cache_bottom and it\npoints at the first entry that may still need to be processed.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n\n * t6035 is still broken with this patch, although t7003 is fixed.\n\n cache.h        |    2 +\n diff-lib.c     |   18 -----\n unpack-trees.c |  214 ++++++++++++++++++++++++++++++++++++++++++--------------\n unpack-trees.h |    2 +-\n 4 files changed, 164 insertions(+), 72 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 5fad24c..18a3e13 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -177,6 +177,8 @@ struct cache_entry {\n #define CE_HASHED    (0x100000)\n #define CE_UNHASHED  (0x200000)\n \n+#define CE_UNPACKED  (0x400000)\n+\n /*\n  * Extended on-disk flags\n  */\ndiff --git a/diff-lib.c b/diff-lib.c\nindex adf1c5f..f759917 100644\n--- a/diff-lib.c\n+++ b/diff-lib.c\n@@ -359,21 +359,6 @@ static void do_oneway_diff(struct unpack_trees_options *o,\n \tshow_modified(revs, tree, idx, 1, cached, match_missing);\n }\n \n-static inline void skip_same_name(struct cache_entry *ce, struct unpack_trees_options *o)\n-{\n-\tint len = ce_namelen(ce);\n-\tconst struct index_state *index = o->src_index;\n-\n-\twhile (o->pos < index->cache_nr) {\n-\t\tstruct cache_entry *next = index->cache[o->pos];\n-\t\tif (len != ce_namelen(next))\n-\t\t\tbreak;\n-\t\tif (memcmp(ce->name, next->name, len))\n-\t\t\tbreak;\n-\t\to->pos++;\n-\t}\n-}\n-\n /*\n  * The unpack_trees() interface is designed for merging, so\n  * the different source entries are designed primarily for\n@@ -395,9 +380,6 @@ static int oneway_diff(struct cache_entry **src, struct unpack_trees_options *o)\n \tstruct cache_entry *tree = src[1];\n \tstruct rev_info *revs = o->unpack_data;\n \n-\tif (idx && ce_stage(idx))\n-\t\tskip_same_name(idx, o);\n-\n \t/*\n \t * Unpack-trees generates a DF/conflict entry if\n \t * there was a directory in the index and a tree\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex c424bab..a6f2187 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -126,18 +126,109 @@ static inline int call_unpack_fn(struct cache_entry **src, struct unpack_trees_o\n \treturn ret;\n }\n \n-static int unpack_index_entry(struct cache_entry *ce, struct unpack_trees_options *o)\n+static void mark_ce_used(struct cache_entry *ce, struct unpack_trees_options *o)\n+{\n+\tce->ce_flags |= CE_UNPACKED;\n+\n+\tif (o->cache_bottom < o->src_index->cache_nr &&\n+\t    o->src_index->cache[o->cache_bottom] == ce) {\n+\t\tint bottom = o->cache_bottom;\n+\t\twhile (bottom < o->src_index->cache_nr &&\n+\t\t       o->src_index->cache[bottom]->ce_flags & CE_UNPACKED)\n+\t\t\tbottom++;\n+\t\to->cache_bottom = bottom;\n+\t}\n+}\n+\n+static void mark_all_ce_unused(struct index_state *index)\n+{\n+\tint i;\n+\tfor (i = 0; i < index->cache_nr; i++)\n+\t\tindex->cache[i]->ce_flags &= ~CE_UNPACKED;\n+}\n+\n+static int locate_in_src_index(struct cache_entry *ce,\n+\t\t\t       struct unpack_trees_options *o)\n+{\n+\tstruct index_state *index = o->src_index;\n+\tint len = ce_namelen(ce);\n+\tint pos = index_name_pos(index, ce->name, len);\n+\tif (pos < 0)\n+\t\tpos = -1 - pos;\n+\treturn pos;\n+}\n+\n+/*\n+ * We call unpack_index_entry() with an unmerged cache entry\n+ * only in diff-index, and it wants a single callback.  Skip\n+ * the other unmerged entry with the same name.\n+ */\n+static void mark_ce_used_same_name(struct cache_entry *ce,\n+\t\t\t\t   struct unpack_trees_options *o)\n+{\n+\tstruct index_state *index = o->src_index;\n+\tint len = ce_namelen(ce);\n+\tint pos;\n+\n+\tfor (pos = locate_in_src_index(ce, o); pos < index->cache_nr; pos++) {\n+\t\tstruct cache_entry *next = index->cache[pos];\n+\t\tif (len != ce_namelen(next) ||\n+\t\t    memcmp(ce->name, next->name, len))\n+\t\t\tbreak;\n+\t\tmark_ce_used(next, o);\n+\t}\n+}\n+\n+static struct cache_entry *next_cache_entry(struct unpack_trees_options *o)\n+{\n+\tconst struct index_state *index = o->src_index;\n+\tint pos = o->cache_bottom;\n+\n+\twhile (pos < index->cache_nr) {\n+\t\tstruct cache_entry *ce = index->cache[pos];\n+\t\tif (!(ce->ce_flags & CE_UNPACKED))\n+\t\t\treturn ce;\n+\t\tpos++;\n+\t}\n+\treturn NULL;\n+}\n+\n+static void add_same_unmerged(struct cache_entry *ce,\n+\t\t\t      struct unpack_trees_options *o)\n+{\n+\tstruct index_state *index = o->src_index;\n+\tint len = ce_namelen(ce);\n+\tint pos = index_name_pos(index, ce->name, len);\n+\n+\tif (0 <= pos)\n+\t\tdie(\"programming error in a caller of mark_ce_used_same_name\");\n+\tfor (pos = -pos - 1; pos < index->cache_nr; pos++) {\n+\t\tstruct cache_entry *next = index->cache[pos];\n+\t\tif (len != ce_namelen(next) ||\n+\t\t    memcmp(ce->name, next->name, len))\n+\t\t\tbreak;\n+\t\tadd_entry(o, next, 0, 0);\n+\t\tmark_ce_used(next, o);\n+\t}\n+}\n+\n+static int unpack_index_entry(struct cache_entry *ce,\n+\t\t\t      struct unpack_trees_options *o)\n {\n \tstruct cache_entry *src[5] = { ce, NULL, };\n+\tint ret;\n \n-\to->pos++;\n+\tmark_ce_used(ce, o);\n \tif (ce_stage(ce)) {\n \t\tif (o->skip_unmerged) {\n \t\t\tadd_entry(o, ce, 0, 0);\n \t\t\treturn 0;\n \t\t}\n \t}\n-\treturn call_unpack_fn(src, o);\n+\tret = call_unpack_fn(src, o);\n+\tif (ce_stage(ce))\n+\t\tmark_ce_used_same_name(ce, o);\n+\treturn ret;\n }\n \n static int traverse_trees_recursive(int n, unsigned long dirmask, unsigned long df_conflicts, struct name_entry *names, struct traverse_info *info)\n@@ -212,6 +303,20 @@ static int compare_entry(const struct cache_entry *ce, const struct traverse_inf\n \treturn ce_namelen(ce) > traverse_path_len(info, n);\n }\n \n+static int ce_in_traverse_path(const struct cache_entry *ce,\n+\t\t\t       const struct traverse_info *info)\n+{\n+\tif (!info->prev)\n+\t\treturn 1;\n+\tif (do_compare_entry(ce, info->prev, &info->name))\n+\t\treturn 0;\n+\t/*\n+\t * If ce (blob) is the same name as the path (which is a tree\n+\t * we will be descending into), it won't be inside it.\n+\t */\n+\treturn (info->pathlen < ce_namelen(ce));\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@@ -300,23 +405,27 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str\n \n \t/* Are we supposed to look at the index too? */\n \tif (o->merge) {\n-\t\twhile (o->pos < o->src_index->cache_nr) {\n-\t\t\tstruct cache_entry *ce = o->src_index->cache[o->pos];\n-\t\t\tint cmp = compare_entry(ce, info, p);\n+\t\twhile (1) {\n+\t\t\tstruct cache_entry *ce = next_cache_entry(o);\n+\t\t\tint cmp;\n+\t\t\tif (!ce)\n+\t\t\t\tbreak;\n+\t\t\tcmp = 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 unpack_failed(o, NULL);\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tif (!cmp) {\n-\t\t\t\to->pos++;\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 * If we skip unmerged index\n+\t\t\t\t\t * entries, we'll skip this\n+\t\t\t\t\t * entry *and* the tree\n+\t\t\t\t\t * 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\tadd_entry(o, ce, 0, 0);\n+\t\t\t\t\t\tadd_same_unmerged(ce, o);\n \t\t\t\t\t\treturn mask;\n \t\t\t\t\t}\n \t\t\t\t}\n@@ -329,6 +438,13 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str\n \tif (unpack_nondirectories(n, mask, dirmask, src, names, info) < 0)\n \t\treturn -1;\n \n+\tif (src[0]) {\n+\t\tif (ce_stage(src[0]))\n+\t\t\tmark_ce_used_same_name(src[0], o);\n+\t\telse\n+\t\t\tmark_ce_used(src[0], o);\n+\t}\n+\n \t/* Now handle any directories.. */\n \tif (dirmask) {\n \t\tunsigned long conflicts = mask & ~dirmask;\n@@ -338,22 +454,6 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str\n \t\t\t\tconflicts |= 1;\n \t\t}\n \n-\t\t/* special case: \"diff-index --cached\" looking at a tree */\n-\t\tif (o->diff_index_cached &&\n-\t\t    n == 1 && dirmask == 1 && S_ISDIR(names->mode)) {\n-\t\t\tint matches;\n-\t\t\tmatches = cache_tree_matches_traversal(o->src_index->cache_tree,\n-\t\t\t\t\t\t\t       names, info);\n-\t\t\t/*\n-\t\t\t * Everything under the name matches.  Adjust o->pos to\n-\t\t\t * skip the entire hierarchy.\n-\t\t\t */\n-\t\t\tif (matches) {\n-\t\t\t\to->pos += matches;\n-\t\t\t\treturn mask;\n-\t\t\t}\n-\t\t}\n-\n \t\tif (traverse_trees_recursive(n, dirmask, conflicts,\n \t\t\t\t\t     names, info) < 0)\n \t\t\treturn -1;\n@@ -400,14 +500,33 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n \t\tinfo.fn = unpack_callback;\n \t\tinfo.data = o;\n \n+\t\tif (o->prefix) {\n+\t\t\t/*\n+\t\t\t * Unpack existing index entries that sort before the\n+\t\t\t * prefix the tree is spliced into.  Note that o->merge\n+\t\t\t * is always true in this case.\n+\t\t\t */\n+\t\t\twhile (1) {\n+\t\t\t\tstruct cache_entry *ce = next_cache_entry(o);\n+\t\t\t\tif (!ce)\n+\t\t\t\t\tbreak;\n+\t\t\t\tif (ce_in_traverse_path(ce, &info))\n+\t\t\t\t\tbreak;\n+\t\t\t\tif (unpack_index_entry(ce, o) < 0)\n+\t\t\t\t\treturn unpack_failed(o, NULL);\n+\t\t\t}\n+\t\t}\n+\n \t\tif (traverse_trees(len, t, &info) < 0)\n \t\t\treturn unpack_failed(o, NULL);\n \t}\n \n \t/* Any left-over entries in the index? */\n \tif (o->merge) {\n-\t\twhile (o->pos < o->src_index->cache_nr) {\n-\t\t\tstruct cache_entry *ce = o->src_index->cache[o->pos];\n+\t\twhile (1) {\n+\t\t\tstruct cache_entry *ce = next_cache_entry(o);\n+\t\t\tif (!ce)\n+\t\t\t\tbreak;\n \t\t\tif (unpack_index_entry(ce, o) < 0)\n \t\t\t\treturn unpack_failed(o, NULL);\n \t\t}\n@@ -416,6 +535,12 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n \tif (o->trivial_merges_only && o->nontrivial_merge)\n \t\treturn unpack_failed(o, \"Merge requires file-level merging\");\n \n+\t/*\n+\t * some callers, most notably \"git status -v\" runs unpack_trees()\n+\t * multiple times; clean everything up after us.\n+\t */\n+\tmark_all_ce_unused(o->src_index);\n+\n \to->src_index = NULL;\n \tret = check_updates(o) ? (-2) : 0;\n \tif (o->dst_index)\n@@ -522,7 +647,9 @@ static int verify_clean_subdirectory(struct cache_entry *ce, const char *action,\n \t * in that directory.\n \t */\n \tnamelen = strlen(ce->name);\n-\tfor (i = o->pos; i < o->src_index->cache_nr; i++) {\n+\tfor (i = locate_in_src_index(ce, o);\n+\t     i < o->src_index->cache_nr;\n+\t     i++) {\n \t\tstruct cache_entry *ce2 = o->src_index->cache[i];\n \t\tint len = ce_namelen(ce2);\n \t\tif (len < namelen ||\n@@ -530,12 +657,14 @@ static int verify_clean_subdirectory(struct cache_entry *ce, const char *action,\n \t\t    ce2->name[namelen] != '/')\n \t\t\tbreak;\n \t\t/*\n-\t\t * ce2->name is an entry in the subdirectory.\n+\t\t * ce2->name is an entry in the subdirectory to be\n+\t\t * removed.\n \t\t */\n \t\tif (!ce_stage(ce2)) {\n \t\t\tif (verify_uptodate(ce2, o))\n \t\t\t\treturn -1;\n \t\t\tadd_entry(o, ce2, CE_REMOVE, 0);\n+\t\t\tmark_ce_used(ce2, o);\n \t\t}\n \t\tcnt++;\n \t}\n@@ -591,7 +720,6 @@ static int verify_absent(struct cache_entry *ce, const char *action,\n \t\treturn 0;\n \n \tif (!lstat(ce->name, &st)) {\n-\t\tint ret;\n \t\tint dtype = ce_to_dtype(ce);\n \t\tstruct cache_entry *result;\n \n@@ -619,28 +747,8 @@ static int verify_absent(struct cache_entry *ce, const char *action,\n \t\t\t * files that are in \"foo/\" we would lose\n \t\t\t * them.\n \t\t\t */\n-\t\t\tret = verify_clean_subdirectory(ce, action, o);\n-\t\t\tif (ret < 0)\n-\t\t\t\treturn ret;\n-\n-\t\t\t/*\n-\t\t\t * If this removed entries from the index,\n-\t\t\t * what that means is:\n-\t\t\t *\n-\t\t\t * (1) the caller unpack_callback() saw path/foo\n-\t\t\t * in the index, and it has not removed it because\n-\t\t\t * it thinks it is handling 'path' as blob with\n-\t\t\t * D/F conflict;\n-\t\t\t * (2) we will return \"ok, we placed a merged entry\n-\t\t\t * in the index\" which would cause o->pos to be\n-\t\t\t * incremented by one;\n-\t\t\t * (3) however, original o->pos now has 'path/foo'\n-\t\t\t * marked with \"to be removed\".\n-\t\t\t *\n-\t\t\t * We need to increment it by the number of\n-\t\t\t * deleted entries here.\n-\t\t\t */\n-\t\t\to->pos += ret;\n+\t\t\tif (verify_clean_subdirectory(ce, action, o) < 0)\n+\t\t\t\treturn -1;\n \t\t\treturn 0;\n \t\t}\n \ndiff --git a/unpack-trees.h b/unpack-trees.h\nindex d19df44..9a0733e 100644\n--- a/unpack-trees.h\n+++ b/unpack-trees.h\n@@ -30,7 +30,7 @@ struct unpack_trees_options {\n \t\t     diff_index_cached,\n \t\t     gently;\n \tconst char *prefix;\n-\tint pos;\n+\tint cache_bottom;\n \tstruct dir_struct *dir;\n \tmerge_fn_t fn;\n \tstruct unpack_trees_error_msgs msgs;\n-- \n1.6.5.rc1.90.ga3b1b\n"},{"id":"123532","messageId":"1253423175-6339-7-git-send-email-gitster@pobox.com","threadId":"21004","inReplyTo":"1253423175-6339-1-git-send-email-gitster@pobox.com","subject":"[WIP PATCH 6/6] read-tree --debug-unpack","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-09-20T05:06:15Z","receivedAt":"2009-09-20T05:06:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Debugging patch.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n builtin-read-tree.c |   36 ++++++++++++++++++++++++++++++++++++\n unpack-trees.c      |   35 +++++++++++++++++++++++++++++++++++\n unpack-trees.h      |    1 +\n 3 files changed, 72 insertions(+), 0 deletions(-)\n\ndiff --git a/builtin-read-tree.c b/builtin-read-tree.c\nindex 14c836b..a9788e5 100644\n--- a/builtin-read-tree.c\n+++ b/builtin-read-tree.c\n@@ -64,6 +64,34 @@ static int exclude_per_directory_cb(const struct option *opt, const char *arg,\n \treturn 0;\n }\n \n+static void debug_stage(const char *label, struct cache_entry *ce,\n+\t\t\tstruct unpack_trees_options *o)\n+{\n+\tprintf(\"%s \", label);\n+\tif (!ce)\n+\t\tprintf(\"(missing)\\n\");\n+\telse if (ce == o->df_conflict_entry)\n+\t\tprintf(\"(conflict)\\n\");\n+\telse\n+\t\tprintf(\"%06o #%d %s %.8s\\n\",\n+\t\t       ce->ce_mode, ce_stage(ce), ce->name,\n+\t\t       sha1_to_hex(ce->sha1));\n+}\n+\n+static int debug_merge(struct cache_entry **stages, struct unpack_trees_options *o)\n+{\n+\tint i;\n+\n+\tprintf(\"* %d-way merge\\n\", o->merge_size);\n+\tdebug_stage(\"index\", stages[0], o);\n+\tfor (i = 1; i <= o->merge_size; i++) {\n+\t\tchar buf[24];\n+\t\tsprintf(buf, \"ent#%d\", i);\n+\t\tdebug_stage(buf, stages[i], o);\n+\t}\n+\treturn 0;\n+}\n+\n static struct lock_file lock_file;\n \n int cmd_read_tree(int argc, const char **argv, const char *unused_prefix)\n@@ -98,6 +126,8 @@ int cmd_read_tree(int argc, const char **argv, const char *unused_prefix)\n \t\t  PARSE_OPT_NONEG, exclude_per_directory_cb },\n \t\tOPT_SET_INT('i', NULL, &opts.index_only,\n \t\t\t    \"don't check the working tree after merging\", 1),\n+\t\tOPT_SET_INT(0, \"debug-unpack\", &opts.debug_unpack,\n+\t\t\t    \"debug unpack-trees\", 1),\n \t\tOPT_END()\n \t};\n \n@@ -165,6 +195,9 @@ int cmd_read_tree(int argc, const char **argv, const char *unused_prefix)\n \t\t\topts.head_idx = 1;\n \t}\n \n+\tif (opts.debug_unpack)\n+\t\topts.fn = debug_merge;\n+\n \tcache_tree_free(&active_cache_tree);\n \tfor (i = 0; i < nr_trees; i++) {\n \t\tstruct tree *tree = trees[i];\n@@ -174,6 +207,9 @@ int cmd_read_tree(int argc, const char **argv, const char *unused_prefix)\n \tif (unpack_trees(nr_trees, t, &opts))\n \t\treturn 128;\n \n+\tif (opts.debug_unpack)\n+\t\treturn 0; /* do not write the index out */\n+\n \t/*\n \t * When reading only one tree (either the most basic form,\n \t * \"-m ent\" or \"--reset ent\" form), we can obtain a fully\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex a6f2187..b1ad2d9 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -393,6 +393,38 @@ static int unpack_failed(struct unpack_trees_options *o, const char *message)\n \treturn -1;\n }\n \n+static void debug_path(struct traverse_info *info)\n+{\n+\tif (info->prev) {\n+\t\tdebug_path(info->prev);\n+\t\tif (*info->prev->name.path)\n+\t\t\tputchar('/');\n+\t}\n+\tprintf(\"%s\", info->name.path);\n+}\n+\n+static void debug_name_entry(int i, struct name_entry *n)\n+{\n+\tprintf(\"ent#%d %06o %s\\n\", i,\n+\t       n->path ? n->mode : 0,\n+\t       n->path ? n->path : \"(missing)\");\n+}\n+\n+static void debug_unpack_callback(int n,\n+\t\t\t\t  unsigned long mask,\n+\t\t\t\t  unsigned long dirmask,\n+\t\t\t\t  struct name_entry *names,\n+\t\t\t\t  struct traverse_info *info)\n+{\n+\tint i;\n+\tprintf(\"* unpack mask %lu, dirmask %lu, cnt %d \",\n+\t       mask, dirmask, n);\n+\tdebug_path(info);\n+\tputchar('\\n');\n+\tfor (i = 0; i < n; i++)\n+\t\tdebug_name_entry(i, names + i);\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[MAX_UNPACK_TREES + 1] = { NULL, };\n@@ -403,6 +435,9 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str\n \twhile (!p->mode)\n \t\tp++;\n \n+\tif (o->debug_unpack)\n+\t\tdebug_unpack_callback(n, mask, dirmask, names, info);\n+\n \t/* Are we supposed to look at the index too? */\n \tif (o->merge) {\n \t\twhile (1) {\ndiff --git a/unpack-trees.h b/unpack-trees.h\nindex 9a0733e..701dca5 100644\n--- a/unpack-trees.h\n+++ b/unpack-trees.h\n@@ -28,6 +28,7 @@ struct unpack_trees_options {\n \t\t     skip_unmerged,\n \t\t     initial_checkout,\n \t\t     diff_index_cached,\n+\t\t     debug_unpack,\n \t\t     gently;\n \tconst char *prefix;\n \tint cache_bottom;\n-- \n1.6.5.rc1.90.ga3b1b\n"}]}