Re: [PATCH v9 1/3] push: add reflog check for "--force-if-includes"

[Junio C Hamano <gitster@pobox.com>]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> Having said that, the change I suggested (to use `get_reachable_subset()`
> instead of repeated `in_merge_bases_many()`) is _still_ the right thing to
> do: we are not actually interested in the merge bases at all, but in
> reachability, and in the future there might be more efficient ways to
> determine that than painting down all the way to merge bases.

I agree with you that the age-old implementation has an obvious room
for optimization.  I think I already pointed out a #leftoverbit that
we can invent a version of paint_down_to_common() that can
short-circuit and return immediately after one side (the "commit"
side) gets painted, so that in_merge_bases_many() can stop
immediately after finding out that the answer is "true".

The function is *not* about computing the merge base across the
commits on the "reference" side but finding out if "commit" is
reachable from any in the "reference" side, so (1) it has a wrong
name and more importantly (2) it wants to do something quite similar
to get_reachable_subset(), but it is much less ambitious.

get_reachable_subset() is capable of doing a lot more.  Unlike the
older in_merge_bases_many() that allowed only one commit on the
candidate for an ancestor side, it can throw a set and ask "which
ones among these are reachable from the other set".

So from the "semantics" point of view, get_reachable_subset() is
overkill and less suitable than in_merge_bases_many() for this
particular application.  We know we have only one candidate, and we
want to ask "is this reachable, or not?" a single bit question.  In
any case, they should yield the right answer from correctness point
of view ;-)

Having said that.

I do not think in the longer term we should keep both.  Clearly the
get_reachable_subset() function can handle more general cases, so it
would make a lot of sense to make in_merge_bases_many() into a thin
wrapper that feeds just a single commit array on one side to be
filtered while feeding the "reference" commits to the other side, as
long as we can demonstrate that the result is just as correct as,
and it is not slower than, the current implementation.  That may be
a bit larger than a typical #leftoverbit but would be a good clean-up
project.