{"thread":{"id":"54327","subject":"[PATCH] combine-diff: handle --find-object in multitree code path","startedAt":"2020-09-30T11:52:44Z","lastAt":"2020-09-30T22:55:02Z","messageCount":5,"participants":["Jeff King","Chris Torek","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"406664","messageId":"20200930115240.GA1899467@coredump.intra.peff.net","threadId":"54327","inReplyTo":null,"subject":"[PATCH] combine-diff: handle --find-object in multitree code path","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-09-30T11:52:40Z","receivedAt":"2020-09-30T11:52:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When doing combined diffs, we have two possible code paths:\n\n  - a slower one which independently diffs against each parent, applies\n    any filters, and then intersects the resulting paths\n\n  - a faster one which walks all trees simultaneously\n\nWhen the diff options specify that we must do certain filters, like\npickaxe, then we always use the slow path, since the pickaxe code only\nknows how to handle filepairs, not the n-parent entries generated for\ncombined diffs.\n\nBut there are two problems with the slow path:\n\n 1. It's slow. Running:\n\n      git rev-list HEAD | git diff-tree --stdin -r -c\n\n    in git.git takes ~3s on my machine. But adding \"--find-object\" to\n    that increases it to ~6s, even though find-object itself should\n    incur only a few extra oid comparisons. On linux.git, it's even\n    worse: 35s versus 215s.\n\n 2. It doesn't catch all cases where a particular path is interesting.\n    Consider a merge with parent blobs X and Y for a particular path,\n    and end result Z. That should be interesting according to \"-c\",\n    because the result doesn't match either parent. And it should be\n    interesting even with \"--find-object=X\", because \"X\" went away in\n    the merge.\n\n    But because we perform each pairwise diff independently, this\n    confuses the intersection code. The change from X to Z is still\n    interesting according to --find-object. But in the other parent we\n    went from Y to Z, so the diff appears empty! That causes the\n    intersection code to think that parent didn't change the path, and\n    thus it's not interesting for \"-c\".\n\nThis patch fixes both by implementing --find-object for the multitree\ncode. It's a bit unfortunate that we have to duplicate some logic from\ndiffcore-pickaxe, but this is the best we can do for now. In an ideal\nworld, all of the diffcore code would stop thinking about filepairs and\nstart thinking about n-parent sets, and we could use the multitree walk\nwith all of it.\n\nUntil then, there are some leftover warts:\n\n  - other pickaxe operations, like -S or -G, still suffer from both\n    problems. These would be hard to adapt because they rely on having\n    a diff_filespec() for each path to look at content. And we'd need to\n    define what an n-way \"change\" means in each case (probably easy for\n    \"-S\", which can compare counts, but not so clear for -G, which is\n    about grepping diffs).\n\n  - other options besides --find-object may cause us to use the slow\n    pairwise path, in which case we'll go back to producing a different\n    (wrong) answer for the X/Y/Z case above.\n\nWe may be able to hack around these, but I think the ultimate solution\nwill be a larger rewrite of the diffcore code. For now, this patch\nimproves one specific case but leaves the rest.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nI'm a little nervous that the second \"wart\" may actually be making\nthings worse, because now we sometimes produce a wrong answer and\nsometime a right one, and it can be difficult to know which options\ncause which (e.g., rename detection puts us onto the slow path). Is it\nworse to sometimes be right and sometimes wrong, or to always be\nconsistently and predictably wrong? I suppose one could even argue that\nthe current semantics aren't \"wrong\", but just what we happen to\nproduce. But IMHO they are so un-useful as to be considered wrong.\n\n combine-diff.c          | 43 ++++++++++++++++++++++++++++++--\n t/t4064-diff-oidfind.sh | 55 +++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 96 insertions(+), 2 deletions(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 002e0e5438..23bca28746 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -1451,6 +1451,42 @@ static struct combine_diff_path *find_paths_multitree(\n \treturn paths_head.next;\n }\n \n+static int match_objfind(struct combine_diff_path *path,\n+\t\t\t int num_parent,\n+\t\t\t const struct oidset *set)\n+{\n+\tint i;\n+\tif (oidset_contains(set, &path->oid))\n+\t\treturn 1;\n+\tfor (i = 0; i < num_parent; i++) {\n+\t\tif (oidset_contains(set, &path->parent[i].oid))\n+\t\t\treturn 1;\n+\t}\n+\treturn 0;\n+}\n+\n+static struct combine_diff_path *combined_objfind(struct diff_options *opt,\n+\t\t\t\t\t\t  struct combine_diff_path *paths,\n+\t\t\t\t\t\t  int num_parent)\n+{\n+\tstruct combine_diff_path *ret = NULL, **tail = &ret;\n+\tstruct combine_diff_path *p = paths;\n+\n+\twhile (p) {\n+\t\tstruct combine_diff_path *next = p->next;\n+\n+\t\tif (match_objfind(p, num_parent, opt->objfind)) {\n+\t\t\tp->next = NULL;\n+\t\t\t*tail = p;\n+\t\t\ttail = &p->next;\n+\t\t} else {\n+\t\t\tfree(p);\n+\t\t}\n+\t\tp = next;\n+\t}\n+\n+\treturn ret;\n+}\n \n void diff_tree_combined(const struct object_id *oid,\n \t\t\tconst struct oid_array *parents,\n@@ -1506,10 +1542,10 @@ void diff_tree_combined(const struct object_id *oid,\n \t\t\topt->flags.follow_renames\t||\n \t\t\topt->break_opt != -1\t||\n \t\t\topt->detect_rename\t||\n-\t\t\t(opt->pickaxe_opts & DIFF_PICKAXE_KINDS_MASK)\t||\n+\t\t\t(opt->pickaxe_opts &\n+\t\t\t (DIFF_PICKAXE_KINDS_MASK & ~DIFF_PICKAXE_KIND_OBJFIND)) ||\n \t\t\topt->filter;\n \n-\n \tif (need_generic_pathscan) {\n \t\t/*\n \t\t * NOTE generic case also handles --stat, as it computes\n@@ -1523,6 +1559,9 @@ void diff_tree_combined(const struct object_id *oid,\n \t\tint stat_opt;\n \t\tpaths = find_paths_multitree(oid, parents, &diffopts);\n \n+\t\tif (opt->pickaxe_opts & DIFF_PICKAXE_KIND_OBJFIND)\n+\t\t\tpaths = combined_objfind(opt, paths, num_parent);\n+\n \t\t/*\n \t\t * show stat against the first parent even\n \t\t * when doing combined diff.\ndiff --git a/t/t4064-diff-oidfind.sh b/t/t4064-diff-oidfind.sh\nindex 3bdf317af8..6d8c8986fc 100755\n--- a/t/t4064-diff-oidfind.sh\n+++ b/t/t4064-diff-oidfind.sh\n@@ -65,4 +65,59 @@ test_expect_success 'find a submodule' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'set up merge tests' '\n+\ttest_commit base &&\n+\n+\tgit checkout -b boring base^ &&\n+\techo boring >file &&\n+\tgit add file &&\n+\tgit commit -m boring &&\n+\n+\tgit checkout -b interesting base^ &&\n+\techo interesting >file &&\n+\tgit add file &&\n+\tgit commit -m interesting &&\n+\n+\tblob=$(git rev-parse interesting:file)\n+'\n+\n+test_expect_success 'detect merge which introduces blob' '\n+\tgit checkout -B merge base &&\n+\tgit merge --no-commit boring &&\n+\techo interesting >file &&\n+\tgit commit -am \"introduce blob\" &&\n+\tgit diff-tree --format=%s --find-object=$blob -c --name-status HEAD >actual &&\n+\tcat >expect <<-\\EOF &&\n+\tintroduce blob\n+\n+\tAM\tfile\n+\tEOF\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'detect merge which removes blob' '\n+\tgit checkout -B merge interesting &&\n+\tgit merge --no-commit base &&\n+\techo boring >file &&\n+\tgit commit -am \"remove blob\" &&\n+\tgit diff-tree --format=%s --find-object=$blob -c --name-status HEAD >actual &&\n+\tcat >expect <<-\\EOF &&\n+\tremove blob\n+\n+\tMA\tfile\n+\tEOF\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'do not detect merge that does not touch blob' '\n+\tgit checkout -B merge interesting &&\n+\tgit merge -m \"untouched blob\" base &&\n+\tgit diff-tree --format=%s --find-object=$blob -c --name-status HEAD >actual &&\n+\tcat >expect <<-\\EOF &&\n+\tuntouched blob\n+\n+\tEOF\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n2.28.0.1173.gad90222cf0\n"},{"id":"406702","messageId":"CAPx1Gvd7WpAgUGgZkZARY7JcFj8nbDJ6zEDTSaBt2=xR535E-g@mail.gmail.com","threadId":"54327","inReplyTo":"20200930115240.GA1899467@coredump.intra.peff.net","subject":"Re: [PATCH] combine-diff: handle --find-object in multitree code path","fromName":"Chris Torek","fromEmail":"chris.torek@gmail.com","sentAt":"2020-09-30T20:06:02Z","receivedAt":"2020-09-30T20:06:16Z","isPatch":true,"sender":{"key":"chris.torek@gmail.com","avatar":"https://avatars.githubusercontent.com/u/16826774?v=4"},"body":"On Wed, Sep 30, 2020 at 4:54 AM Jeff King <peff@peff.net> wrote:\n> I'm a little nervous that the second \"wart\" may actually be making\n> things worse, because now we sometimes produce a wrong answer and\n> sometime a right one, and it can be difficult to know which options\n> cause which (e.g., rename detection puts us onto the slow path). Is it\n> worse to sometimes be right and sometimes wrong, or to always be\n> consistently and predictably wrong? I suppose one could even argue that\n> the current semantics aren't \"wrong\", but just what we happen to\n> produce. But IMHO they are so un-useful as to be considered wrong.\n\n\"Predictably wrong\" *is* actually useful while \"unpredictably wrong\"\nis, um, \"less useful\".  Perhaps just documenting exactly which options\nuse which path?  Basically turn some of this into documentation.\n\nChris\n"},{"id":"406721","messageId":"xmqqmu16gbqk.fsf@gitster.c.googlers.com","threadId":"54327","inReplyTo":"20200930115240.GA1899467@coredump.intra.peff.net","subject":"Re: [PATCH] combine-diff: handle --find-object in multitree code path","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-09-30T22:07:15Z","receivedAt":"2020-09-30T22:07:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n>  2. It doesn't catch all cases where a particular path is interesting.\n>     Consider a merge with parent blobs X and Y for a particular path,\n>     and end result Z. That should be interesting according to \"-c\",\n>     because the result doesn't match either parent. And it should be\n>     interesting even with \"--find-object=X\", because \"X\" went away in\n>     the merge.\n>\n>     But because we perform each pairwise diff independently, this\n>     confuses the intersection code. The change from X to Z is still\n>     interesting according to --find-object. But in the other parent we\n>     went from Y to Z, so the diff appears empty! That causes the\n>     intersection code to think that parent didn't change the path, and\n>     thus it's not interesting for \"-c\".\n\nHmmmm....\n\n> +test_expect_success 'do not detect merge that does not touch blob' '\n> +\tgit checkout -B merge interesting &&\n> +\tgit merge -m \"untouched blob\" base &&\n> +\tgit diff-tree --format=%s --find-object=$blob -c --name-status HEAD >actual &&\n\nYou learn new things every day ;-)\n\nI've always thought that for --find-object to do a good job, you'd\nneed \"--full-history\" and perhaps \"-m\".  Especially, I didn't expect\n\"-c\" or \"--cc\" to make a difference.\n\n\n"},{"id":"406727","messageId":"20200930224611.GC1908000@coredump.intra.peff.net","threadId":"54327","inReplyTo":"CAPx1Gvd7WpAgUGgZkZARY7JcFj8nbDJ6zEDTSaBt2=xR535E-g@mail.gmail.com","subject":"Re: [PATCH] combine-diff: handle --find-object in multitree code path","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-09-30T22:46:11Z","receivedAt":"2020-09-30T22:46:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Sep 30, 2020 at 01:06:02PM -0700, Chris Torek wrote:\n\n> On Wed, Sep 30, 2020 at 4:54 AM Jeff King <peff@peff.net> wrote:\n> > I'm a little nervous that the second \"wart\" may actually be making\n> > things worse, because now we sometimes produce a wrong answer and\n> > sometime a right one, and it can be difficult to know which options\n> > cause which (e.g., rename detection puts us onto the slow path). Is it\n> > worse to sometimes be right and sometimes wrong, or to always be\n> > consistently and predictably wrong? I suppose one could even argue that\n> > the current semantics aren't \"wrong\", but just what we happen to\n> > produce. But IMHO they are so un-useful as to be considered wrong.\n> \n> \"Predictably wrong\" *is* actually useful while \"unpredictably wrong\"\n> is, um, \"less useful\".  Perhaps just documenting exactly which options\n> use which path?  Basically turn some of this into documentation.\n\nPerhaps. The thing is that I do have a use case for which I need that\nanswer, and I need it to be reliable and fast. So right now\n--find-object is not useful at all, and this makes it useful for at\nleast my narrow case.\n\nMy big concern is just making the overall system more confusing. I agree\nthat documenting _might_ help, but we're getting pretty far into\ninternals here. I'm not sure I'd want to expose the user to a list of\n\"these options trigger this code path, which behaves like this\". It's\nlikely to generate more confusion than it solves, and would likely\nbitrot anyway.\n\nMaybe something like this would help:\n\ndiff --git a/Documentation/diff-generate-patch.txt b/Documentation/diff-generate-patch.txt\nindex b10ff4caa6..f61af6af18 100644\n--- a/Documentation/diff-generate-patch.txt\n+++ b/Documentation/diff-generate-patch.txt\n@@ -200,3 +200,7 @@ parents).  When shown by `git diff-files -c`, it compares the\n two unresolved merge parents with the working tree file\n (i.e. file1 is stage 2 aka \"our version\", file2 is stage 3 aka\n \"their version\").\n+\n+Note that the results of using `-c` or `--cc` with diff-filtering\n+options such as `-S` or `--find-object` are currently poorly defined,\n+and are subject to change.\n\nI'd perhaps even put that in a BUGS section, but that can't be done from\nan include file like this.\n\n-Peff\n"},{"id":"406728","messageId":"20200930225441.GD1908000@coredump.intra.peff.net","threadId":"54327","inReplyTo":"xmqqmu16gbqk.fsf@gitster.c.googlers.com","subject":"Re: [PATCH] combine-diff: handle --find-object in multitree code path","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-09-30T22:54:41Z","receivedAt":"2020-09-30T22:55:02Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Sep 30, 2020 at 03:07:15PM -0700, Junio C Hamano wrote:\n\n> > +test_expect_success 'do not detect merge that does not touch blob' '\n> > +\tgit checkout -B merge interesting &&\n> > +\tgit merge -m \"untouched blob\" base &&\n> > +\tgit diff-tree --format=%s --find-object=$blob -c --name-status HEAD >actual &&\n> \n> You learn new things every day ;-)\n> \n> I've always thought that for --find-object to do a good job, you'd\n> need \"--full-history\" and perhaps \"-m\".  Especially, I didn't expect\n> \"-c\" or \"--cc\" to make a difference.\n\nYou don't need --full-history, since there's no history simplification\ngoing on here. And \"-m\" isn't very helpful with --find-object. It's\ngoing to find every merge that crosses a boundary where the object was\nintroduced, since it will be introduced in the diff against the _other_\nparent. E.g., in:\n\n  A -- B\n   \\    \\\n    C -- M\n\nIf B introduces object X, then:\n\n  git log --find-object=X -m M\n\nis going to see the diff of C to M as introducing X. But M didn't do\nanything interesting there; it just picked it up from the branch with B.\n\nMy concrete use case here, btw, is reporting to users which commit\nintroduced a blob (and at which path). It mostly works if you ignore\nmerges, but misses out on any evil merges which introduce the object.\nAdding \"-c\" fixes that (but before this patch is slow and misses the\ncase where the merge removes the object).\n\n-Peff\n"}]}