Finds the commit two lines of history last agreed at.
A three-way merge is only meaningful against a common ancestor: without one there is no way to
tell a value somebody changed from a value that was always there, and every difference would read
as a conflict. So this runs first, and a merge with no base refuses rather than falling back to
comparing two tips against each other.
Parents are walked through CommitIndex rather than through CommitLog, so the walk is queries
against a local table instead of one ranged GET per commit. That is what makes it affordable to
walk thousands of commits to answer a question an operator asked interactively.
The walk is bounded twice and says which bound it hit. A ceiling stops it after a fixed number
of commits, because a branch cut a year ago against a busy trunk is a walk nobody wants to wait
for and "this is further back than I will look" is a usable answer. A seen set stops it on a chain
that revisits a commit, which cannot happen in a content-addressed history and therefore means the
index is corrupt - that one is refused outright rather than reported as a distance, because
carrying on would produce a base that is not one.
Counted per side, so the worst case is twice this many rows. Chosen to be far longer than any
branch an operator would merge by hand and far shorter than a walk that would time out a
request.
Properties
$parentsOf
$parentsOf : \Closure
Type
Closure
$ceiling
$ceiling : int
Type
int
Methods
__construct()
__construct(callable $parentsOf, int $ceiling = \self::DEFAULT_CEILING) : mixed
Constructs a merge base finder.
The lookup is a callable rather than the index itself, and on a real site it is
CommitIndex::parentsOf(...). What this needs is one question answered - what does this commit
build on - and taking the answer rather than the table is what lets the walk be driven over a
synthetic chain with no database behind it, which is the only way a diamond and a corrupt chain
can be tested at all.
Parameters
callable
$parentsOf
Answers what one commit builds on, first parent first, or NULL when the commit is not indexed.
int
$ceiling
How many commits either walk may read before refusing.
Returns
mixed
—
find()
find(string $left, string $right) : string|null
The nearest commit both sides descend from.
Ancestors of the left side are collected first, then the right side is walked breadth first and
the first commit already seen is the answer. Breadth first is what makes it the NEAREST common
ancestor rather than merely a common one: on a diamond, the fork point is reached before the
commits above it.
Parameters
string
$left
One commit, conventionally the target tip.
string
$right
The other, conventionally the branch tip.
Throws
\RuntimeException
When either walk passes the ceiling, or meets the same commit twice.
Returns
string|null
—
The base commit, or NULL when the two share no ancestor at all, which is what two histories
with different roots look like.
Answers the question a merge asks before it does any work: a branch whose tip the target already
contains has nothing to bring in, and one that contains the target tip is a fast-forward rather
than a merge.
Parameters
string
$ancestor
The commit that might be behind.
string
$descendant
The commit to walk back from.
Throws
\RuntimeException
When the walk passes the ceiling, or meets the same commit twice.
Returns
bool
—
TRUE when walking back from the descendant reaches the ancestor.
ancestors()
ancestors(string $from) : array<string,true>
Every commit reachable from one, as a lookup set.
Parameters
string
$from
Commit to walk back from.
Throws
\RuntimeException
When the walk passes the ceiling, or meets the same commit twice.
Returns
array
—
Commit id keyed to TRUE, the starting commit included.
walk()
walk(string $from) : list<string>
Walks back from a commit, nearest first, refusing a chain that will not terminate.
A commit the index does not hold ends that line of the walk rather than raising. History is
pruned from the far end, so a branch cut before a prune legitimately walks off the end of what
survives, and refusing there would make an ordinary store unmergeable.
Parameters
string
$from
Commit to start at.
Throws
\RuntimeException
When the walk passes the ceiling, or the commits it read describe a cycle.
Returns
list
—
Commit ids in breadth-first order, the starting commit first.
Refuses a set of commits whose parent links form a loop.
Meeting a commit twice is not the test, and using it as one would refuse ordinary histories.
A merge whose branch was cut off the target's current tip reaches that tip down both sides, and
every diamond reaches its fork point twice; both are correct histories. What cannot happen is a
commit being its own ancestor, since an address is derived from the bytes that name the parent.
So the peel is the test: repeatedly remove the commits whose parents are all outside the set or
already removed. An acyclic set empties; whatever is left when nothing can be removed is exactly
the commits inside a loop.