[RFC v2] blame: new option --prefer-first to better handle merged cherry-picks

Allows to disable the git blame optimization of assuming that if there is a parent of a merge commit that has the exactly same file content, then only this parent is to be looked at.

This optimization, while being faster in the usual case, means that in the case of cherry-picks the blamed commit depends on which other commits touched a file.

If for example one commit A modified both files b and c. And there are commits B and C, B only modifies file b and C only modifies file c (so that no conflicts happen), and assume A is cherry-picked as A' and the two branches then merged:

--o-----B---A
   \         \
    ---C---A'--M---

Then without this new option git blame blames the A|A' changes of file b to A while blaming the changes of c to A'. With the new option --prefer-first it blames both changes to the same commit and to the one more on the "left" side of the graph.

Signed-off-by: Bernhard R. Link <brlink@debian.org>
---
 Documentation/blame-options.txt | 6 ++++++
 builtin/blame.c                 | 7 +++++--
 2 files changed, 11 insertions(+), 2 deletions(-)

 Differences to first round: rename option and describe the effect
 instead of the implementation in documentation.

"Bernhard R. Link" <brlink@debian.org> writes:

I read the updated documentation three times but it still does not answer any of my questions I had in $gmane/239888, the most important part of which was:

    Yeah, the cherry-picked one will introduce the same change as
    the one that was cherry-picked, so if you look at the end result
    and ask "where did _this_ line come from?", there are two
    equally plausible candidates, as "blame" output can give only
    one answer to each line.  I still do not see why the one that is
    picked with the new option is better.  At best, it looks to me
    that it is saying "running with this option may (or may not)
    give a different answer, so run the command with and without it
    and see which one you like", which does not sound too useful to
    the end users.

To put it another way, why/when would an end user choose to use this option? If the result of using this option is always better than without, why/when would an end user choose not to use this option?

* Junio C Hamano <gitster@pobox.com> [140113 23:31]:

Because:
  - it will blame the modifications of merged cherry-picked commit
    to only one commit. Without the option parts of the modification
    will be reported as coming from the one, parts will be reported
    to be from the other. With the option only one of those two commits
    is reported as the origin at the same time and not both.
  - it is more predictable which commit is blamed, so if one is
    interested in where some commit was introduced first into a
    "mainline", one gets this information, and not somtimes a different
    one due to unrelated reasons.

While the result is more consistent and more predictable in the case of merged cherry picks, it is also slower in every case. Usually speed will be more important than this exactness, especially as the result will not differ for the common case (if there are no cherry-picked commits merged or when those commits do not touch any files that are otherwise only modified in the merged branch).

	Bernhard R. Link

"Bernhard R. Link" <brl+git@mail.brlink.eu> writes:

Consistent and predictable, perhaps, but I am not sure "exact" would be a good word.

Wouldn't the result depend on which way the cherry pick went, and then the later merge went? In the particular topology you depicted in the log message, the end result may happen to point at the same commit for these two paths, but I am not sure how the change guarantees that "we always point at the same original commit not the cherry-picked one", which was implied by the log message, if your cherry-pick and merge went in different direction in similar topologies.

And that is why I said:

    At best, it looks to me that it is saying "running with this
    option may (or may not) give a different answer, so run the
    command with and without it and see which one you like"

With the stress on "different" answer; it the change were "with the option the result is always better, albeit you will have to wait longer", I would not have this much trouble accepting the change, though.

Junio C Hamano <gitster@pobox.com> writes:

Another thing I am not enthusiasitc about this change is that I am afraid that this may make "git blame -- path" and "git log -- path" work inconsistenly. The both cull side branches whenever one of the parents gave the resulting blob, even that parent is not the first one. But "git blame --prefer-first -- path", afaict, behaves quite differently from "git log --first-parent -- path", even though they share similar option names, adding more to the confusion.

Junio C Hamano <gitster@pobox.com> writes:

I think I am starting to understand why this patch felt wrong to me. This wasn't about "--first-parent" at all, and you are correct that you didn't call the option as such), but I somehow thought that they were related; perhaps the fact that both disable the "if the result exactly matches one parent, all the other parents can be culled to simplify the history" logic blinded me.

In reality, the new flag is a lot closer in spirit to the total opposite of "--first-parent", i.e. "--full-history". That option also disables that "if same to one parent, other parents do not matter" logic, but its effect is quite different. It makes the other histories that did not have to have contributed the end result shown in the output.

Now, when we step back and think about how the normal "git blame" logic apportions the blame to multiple parents when there is no exact match, it does so in a pretty arbitrary way. It lets earlier parents to claim the responsibility and later parents only get leftover contents that weren't claimed by the earlier ones. We can call that "favouring earler ones", i.e. "--prefer-first".

It was implemented this way, not because this order makes any sense, but primarily because no order is particularly better than any other, and the designer (me) happened to have picked the easiest one at random.

The "pick the one that exactly matches if exists" can be thought of an easy hack to hide the problems that come from this arbitrary choice. Without it, if the result matches the second parent (i.e. a typical merge of a work done on the topic branch while the mainline has been quiescent in the same area), the "give earlier parents a chance to claim responsiblity before later ones" rule would have split the blame for parts that weren't changed in the side branch topic to the mainline and blame would have been passed to the side branch only for the portion that were changed by the side branch. Instead, "pass the whole blame to the one that exactly matches" hack keeps larger blocks of text unsplit, clumping related contents together as long as possible while we traverse the history.

It is an "easy hack", because we only need to compare the object name, but a logical extension to it would have been to compute the similarity scores between the result and each of the parents, sort the parents by that similarity score order, and give more similar ones a chance to claim responsibility before less similar ones. We could call it "favouring similar ones", i.e. "--prefer-similar" or something.

That would have made the result more stable. Imagine that in one history, a merge's result matchs exactly the second parent, and in another history, a merge's result almost matches exactly the second parent but the difference is the result adds one blank line at the end of the file relative to what the second parent has.

With the current code, blaming the file will get quite a different result.

In the former history, the sub-history leading to the second parent of the merge will get all the blame, but in the latter history, the sub-history leading to the first parent of the merge will have a chance to claim the responsibility for the shared part before the second parent has a say in the output.

If we sorted the parents in the similarity order and gave the first refusal right to more similar parents before less similar ones, then the resulting output from "git blame" would be very similar in these two histories, which would be a very desirable property. If the only difference between the results of the merge in the former and the latter histories is one blank line at the end of the file in question, blames for the remaining part of the file should be assigned the same between the two histories, but the "pass the entire blame to the second parent only when the second parent exactly matches" hack gets in the way for that ideal, and "sort the parents in similarity order" will fix that.

Of course, it would make the computation a lot more costly, but it would make the behaviour more predictable and understandable.

But that is a different tangent.

I think the new feature introduced by your change can be explained as "'git blame' uses the same history simplification as the commands in the 'git log' family that culls other side branches when the merge result exactly matches one parent, and in all other cases, it lets earlier parents claim responsibility before the later ones. This option disables the culling of the irrelevant side branches, in a way similar to how '--full-history' option to the commands in the 'git log' family works, and lets earlier parents claim responsibility to the merge result (even when the later parents contributed a lot more to the result) before the later parents.".

And if it were sold that way, I think I could at least understand it (I do not necessarily buy it as a useful feature, though---at least not yet).

In any case, "--prefer-first" is not particularly a good name, as that is the default mode of operation for "git blame". If we were ever going to implement the "sort parents by similarity", that would be triggered with "--prefer-similar" and "--prefer-first" would becomeq a way to choose the current algorithm (i.e. not sort the parents by similarity but go from earlier to later parents). We would regret if we gave that option name to the feature proposed by the patch under discussion. How about calling it "--full-history", which is a way to tell Git not to cull side branches when the result matches one of the parents? It is even plausible that we may later come up with "--prefer-<something>" (sort the parents not in the original parent order nor in the similarity order but with some other heuristics), and I suspect "--full-history" would be an orthogonal axis to the order in which the parents are given a chance to claim responsiblity.

Thanks; I'll queue the patch on 'pu' and wait for others to comment.

Junio C Hamano <gitster@pobox.com> writes:

Extending along the tangent further.

Another thing that I found the argument in the proposed log message of the patch weak was that the claim that changed code will assign the blame to the "same" commit for both path b and c. There are two reasons why. One is that we do not look at b while chasing the ancestry of c, so if a different traverse order assigns the blame to the same commit for them, it is a mere happenstance. But a more important reason is that the changed code will still assign the blame for "different" commits if the final merge were made in the opposite direction. In your original topology, we skip over the first parent and give the whole blame to the second parent without the change, and with the change, we stop doing so and instead give some blame to the first parent and then allow the second parent a chance to claim the blame for the remainder. But in a history where the final merge went in the opposite direction, even with the change, we compare with the "first" parent (which was the "second" one in your original topology) with the result, find out that the contents exactly match, and that parent grabs the whole blame. So in that sense, the updated code that "consistently" gives earlier parents chance to claim the blame before later ones does not behave consitently on the same history with different merge parent order.

That makes me think that the reason why the result you got with the change is better (assuming it is better) is _not_ because the updated code lets earlier parents give chance to claim the blame; it could be an indication that the "keep larger blocks of text unsplit, clumping related contents together as long as possible" heuristics is what prevents us from having a better result.

If that is really the case, that would mean that letting the blame split early would give us a better result. I alluded to "give more similar parents first chance to claim responsibility before less similar ones" in the previous message, but perhaps this is indicating that we might get a better result if we did the opposite---instead of assigning blames to earlier parents and then to later ones, compare the result with each parent, order the parents by how few lines of blame they could claim if each of them were allowed to go first, and then actually compute and assign the blame in that order, "favouring dissimilar ones". That may produce the result you are after in a more consistent way, regardless of the merge order.

I think I've done thinking about this issue, at least for now.