Re: resolving ambiguity in action stamps (was: Everyone, please stop making my life more difficult)

["Eric S. Raymond" <esr@thyrsus.com>]

Stephen J. Turnbull <stephen@xemacs.org>:
> Eric S. Raymond writes:
> 
>  > I couldn't invent one.  I believe this is mathematically equivalent
>  > to total-ordering the DAG. Which you can't do.
> 
> You must have other conditions in mind for your allowable total
> orders, since any finite partial order can be extended to a total
> order (topological sort), usually in several ways.  Not even the Emacs
> repo has an uncountable number of revisions (although working with bzr
> sometimes makes me feel like it does).

Sorry, you're right. I should have said equivalent to the existence of a 
*unique* total ordering.  The multiplicity of possible extended orders is the
problem, not the solution.

Look at it this way.  For a suffix-numbering scheme to be useful, a
browsing tool or anything else chasing references needs to converge on
*the same ordering that you generated* using only the DAG topology -
because it's not going to know, in particular, what order you
encountered the commits in.

/me puts on his "I used to be a mathematician..." hat...

The problem admits of a unique solution if every clique of commits
has the property that the minimal subgraph required to connect it
is totally ordered.  Think of the dates as node colors.  Then, in
this graph:

A <-- B <-- C <-- B <-- D

we can number uniquely as 

A <-- B1 <-- C <-- B2 <-- D

based on the parent-of ordering.  Then there's this case:

A <-- B1 <-- C <-- B2 <-- D
              \
               +--- E <-- F

We can still uniquely order B1 and B2 because the minimal subgraph that
joins them is totally ordered.  The problem case is this:

A <-- B <-- C <-- B <-- D
              \
               +--- B <-- E <- F

In this the minimal subgraph joining the clique is not totally ordered,
so we don't know how to uniquely order the Bs on the branches.

To solve this problem we need a unique order relation on the branch heads.
If branches had immutable names that would imply one, but we can't assume that.

Possibly there's a solution here using a constraint particular to VCSes that
I haven't taken into account, and someone cleverer than me will notice.
That would be nice.
-- 
		<a href="http://www.catb.org/~esr/">Eric S. Raymond</a>