Re: resolving ambiguity in action stamps

[Yuri Khan <yuri.v.khan@gmail.com>]

On Sat, Sep 13, 2014 at 5:50 PM, Eric S. Raymond <esr@thyrsus.com> wrote:

> Both of Harald's objections are, alas, sound.  In particular, the
> branch total ordering is not useful if any commit can arbitrarily
> permute it.
>
> The hash of the branch's *root* node would be better.  But that still
> leaves the two of the three problems unsolved.

One of them being “How do you define the root node of a branch?”.

* You cannot mean the commit that is most distant one reachable from
the branch tip, because that root (the “Big Bang” of the repository)
is often common to all branches.
* Do you mean the most distant commit that is reachable from this
branch and unreachable from other branch tips? Then this is
invalidated by creating a new branch tip. If two branch tips point to
the same commit, then, under this definition, they have no root at
all.

No, if we want a mathematically sound and (mostly)
implementation-agnostic way to refer to commits, then it has to:

* be invariant under the operations that do not modify the graph —
branch tip and tag creation, deletion, renaming, resetting,
pushing/fetching;
* be invariant under the operations that are commonly performed on the
graph during normal repository use (creating new commits, pushing and
fetching);
* (optional but highly desired) be well-behaved under less common
operations (cherry-picking, rebasing, force-push).

An author + authoring timestamp combination is in my opinion the
closest thing in Git. It leaves ambiguity when a commit is
cherry-picked or rebased, but:

* This ambiguity may be resolved by tracing reachability from the
referring commit. It should be a rare situation when more than one
instance of the same rebased commit are reachable from a single
descendant/referrer.
** Under that heuristic, rebasing the referrer over to the branch
containing a different instance of the referree will “fix up” the
reference to point to that instance. I actually see this as a good
thing, e.g. when both commits are rebased in a single rebase
operation.
** However, on certain occasions, one may want to refer to a commit on
a different branch, e.g. when cherry-picking, add a reference to the
original commit. I do not have a solution here, apart from “don’t do
that”.

One could suggest ordering the commits having the same
author+timestamp by their commit timestamp (or in fact any other
property), and appending the numeric position according to that order
as a disambiguator. This will break if a reference is made without
knowledge of the combined global set of instances of the commit
referred to — uniting different subsets during fetch or push will
change the positions and invalidate references.

I suggest that, if it is desirable to be able to unambiguously refer
to commits in a rebaseful graph, the 4-tuple <author, authoring
timestamp, committer, commit timestamp> will provide a good
approximation.

In practice, I believe <author, authoring timestamp, optional part of
commit summary> will be precise enough for human software
archaeologists.