Junio C Hamano wrote:
A Large Angry SCM <gitzilla@xxxxxxxxx> writes:
This is a good demonstration that merge-base may not give you
minimal set for pathological cases. If you want to be through
you could traverse everything to make sure we do not say 'S' is
relevant, but that is quite expensive, so I think there will
always be artifacts of horizon effect like this no matter how
you try to catch it (didn't I keep saying that already?).
The problem is in mark_reachable_commits(); it is either superfluous
or it needs to parse_commit() those commits that haven't been parsed
yet that it needs to traverse.
Yes, you could traverse everything. But that is not practical.
We have known that the clean-up pass has this horizon effect,
and it is a compromise.
The clean-up pass was devised to eliminate bases that are reachable from
other bases. It just doesn't look hard enough.
If you apply this testing patch on top of yours, you will see
that parsing more commits at that point makes the clean-up
pass go all the way down to the root commit.
Yes, I was aware of graphs that would have that behavior.
The root of the problem is that the heuristic, that attempts to use
timestamps to detect that a commit is _not_ reachable from a given
commit, relies on the timestamps of commits with a reachability
relationship to have a relationship that matches the graph.
We may alternatively not use the clean-up pass at all, but I
suspect that might give us many false positives. I don't
remember the details but I think we added it while fixing
merge-base in the real life situation.
The history of the clean-up pass is that before it was added,
git-merge-base was returning a base reachable from another base, and the
base returned was, in some significant way, worse for merging. My
construct demonstrates that the clean-up pass only deals with special case.
It may be interesting to run tests on real merges (I believe the
kernel repository has a handful merges that have more than one
merge bases) to see how effective the current clean-up pass is.
It may turn out to be ineffective in practice, in which case we
could kill it off.
Although a very important set of repositories to Git, the linux kernel
repositories may no longer be representative of the diversity of Git
use. Still, it would be interesting to know the outcome.
-
: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html