{"thread":{"id":"37382","subject":"[PATCH] intersect_paths: respect mode in git's tree-sort","startedAt":"2014-08-20T02:14:30Z","lastAt":"2014-08-20T20:40:07Z","messageCount":3,"participants":["Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"247995","messageId":"20140820021428.GA22266@peff.net","threadId":"37382","inReplyTo":null,"subject":"[PATCH] intersect_paths: respect mode in git's tree-sort","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-20T02:14:30Z","receivedAt":"2014-08-20T02:14:30Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we do a combined diff, we individually diff against\neach parent, and then use intersect_paths to do a parallel\nwalk through the sorted results and come up with a final\nlist of interesting paths.\n\nThe sort order here is that returned by the diffs, which\nmeans it is in git's tree-order which sorts sub-trees as if\ntheir paths have \"/\" at the end. When we do our parallel\nwalk, we need to use a comparison function which provides\nthe same order.\n\nSince 8518ff8 (combine-diff: optimize combine_diff_path sets\nintersection, 2014-01-20), we use a simple strcmp to\ncompare the pathnames, and get this wrong. It's somewhat\nhard to trigger because normally a diff does not produce\ntree entries at all, and therefore the sort order is the\nsame as a strcmp. However, if the \"-t\" option is used with\nthe diff, then we will produce diff_filepairs for both trees\nand files.\n\nWe can use base_name_compare to do the comparison, just as\nthe tree-diff code does. Even though what we have are not\ntechnically base names (they are full paths within the\ntree), the end result is the same (we do not care about\ninterior slashes at all, only about the final character).\n\nHowever, since we do not have the length of each path\nstored, we take a slight shortcut: if neither of the entries\nis a sub-tree then the comparison is equivalent to a strcmp.\nThis lets us skip the extra strlen calls in the common case\nwithout having to reimplement base_name_compare from\nscratch.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nThis regression is in v2.0.0 and up. I suspect most people didn't notice\nbecause \"-t\" isn't that common an option (and it only kicks in if you\nhave files like \"foo-ext\" or \"foo.ext\" next to a directory \"foo\"). At\nGitHub we do a lot of diffs like this to generate the default tree\nviews.\n\nYou can see more real-world cases by running \"git log --merges -c -t\n--raw\" on git.git. The results from v2.0.0 (and the current \"master\")\ndisagree with those from v1.9.4. With my patch, we match v1.9.4 again.\n\n combine-diff.c           | 12 +++++++++++-\n t/t4038-diff-combined.sh | 34 ++++++++++++++++++++++++++++++++++\n 2 files changed, 45 insertions(+), 1 deletion(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex fd6d63c..6d62973 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -12,6 +12,16 @@\n #include \"sha1-array.h\"\n #include \"revision.h\"\n \n+static int compare_paths(const struct combine_diff_path *one,\n+\t\t\t  const struct diff_filespec *two)\n+{\n+\tif (!S_ISDIR(one->mode) && !S_ISDIR(two->mode))\n+\t\treturn strcmp(one->path, two->path);\n+\n+\treturn base_name_compare(one->path, strlen(one->path), one->mode,\n+\t\t\t\t two->path, strlen(two->path), two->mode);\n+}\n+\n static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr, int n, int num_parent)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n@@ -52,7 +62,7 @@ static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr,\n \ti = 0;\n \twhile ((p = *tail) != NULL) {\n \t\tcmp = ((i >= q->nr)\n-\t\t       ? -1 : strcmp(p->path, q->queue[i]->two->path));\n+\t\t       ? -1 : compare_paths(p, q->queue[i]->two));\n \n \t\tif (cmp < 0) {\n \t\t\t/* p->path not in q->queue[]; drop it */\ndiff --git a/t/t4038-diff-combined.sh b/t/t4038-diff-combined.sh\nindex 1019d7b..71a664d 100755\n--- a/t/t4038-diff-combined.sh\n+++ b/t/t4038-diff-combined.sh\n@@ -401,4 +401,38 @@ test_expect_success 'combine diff missing delete bug' '\n \tcompare_diff_patch expected actual\n '\n \n+test_expect_success 'combine diff gets tree sorting right' '\n+\t# create a directory and a file that sort differently in trees\n+\t# versus byte-wise (implied \"/\" sorts \".\")\n+\tgit checkout -f master &&\n+\tmkdir foo &&\n+\techo base >foo/one &&\n+\techo base >foo/two &&\n+\techo base >foo.ext &&\n+\tgit add foo foo.ext &&\n+\tgit commit -m base &&\n+\n+\t# one side modifies a file in the directory, along with the root\n+\t# file...\n+\techo master >foo/one &&\n+\techo master >foo.ext &&\n+\tgit commit -a -m master &&\n+\n+\t# the other side modifies the other file in the directory\n+\tgit checkout -b other HEAD^ &&\n+\techo other >foo/two &&\n+\tgit commit -a -m other &&\n+\n+\t# And now we merge. The files in the subdirectory will resolve cleanly,\n+\t# meaning that a combined diff will not find them interesting. But it\n+\t# will find the tree itself interesting, because it had to be merged.\n+\tgit checkout master &&\n+\tgit merge other &&\n+\n+\tprintf \"MM\\tfoo\\n\" >expect &&\n+\tgit diff-tree -c --name-status -t HEAD >actual.tmp &&\n+\tsed 1d <actual.tmp >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n2.1.0.346.ga0367b9\n"},{"id":"247999","messageId":"20140820033539.GA2773@peff.net","threadId":"37382","inReplyTo":"20140820021428.GA22266@peff.net","subject":"Re: [PATCH] intersect_paths: respect mode in git's tree-sort","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-20T03:35:39Z","receivedAt":"2014-08-20T03:35:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Aug 19, 2014 at 10:14:30PM -0400, Jeff King wrote:\n\n> diff --git a/t/t4038-diff-combined.sh b/t/t4038-diff-combined.sh\n> index 1019d7b..71a664d 100755\n> --- a/t/t4038-diff-combined.sh\n> +++ b/t/t4038-diff-combined.sh\n> @@ -401,4 +401,38 @@ test_expect_success 'combine diff missing delete bug' '\n>  \tcompare_diff_patch expected actual\n>  '\n>  \n> +test_expect_success 'combine diff gets tree sorting right' '\n> +\t# create a directory and a file that sort differently in trees\n> +\t# versus byte-wise (implied \"/\" sorts \".\")\n\nThis should be s/sorts/& after/, of course.\n\n-Peff\n"},{"id":"248031","messageId":"xmqqfvgquc7s.fsf@gitster.dls.corp.google.com","threadId":"37382","inReplyTo":"20140820033539.GA2773@peff.net","subject":"Re: [PATCH] intersect_paths: respect mode in git's tree-sort","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-08-20T20:40:07Z","receivedAt":"2014-08-20T20:40:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thanks.\n\nWill queue on top of v2.0.0-rc0~146^2 (tests: add checking that\ncombine-diff emits only correct paths, 2014-02-03) so that we can\nmerge the fix down to 2.0 maintenance track later.\n"}]}