Re: [PATCH] Additional merge-base tests

From: A Large Angry SCM <gitzilla@gmail.com>
Date: Jul 4, 2006, 20:08 UTC
Message-ID: <44AACAAA.1030708@gmail.com>
In-Reply-To: <7vpsgllsnp.fsf@assigned-by-dhcp.cox.net>

Junio C Hamano wrote:

Show 15 quoted lines

> A Large Angry SCM <gitzilla@gmail.com> 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.

Show 5 quoted lines

> 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.