Re: [PATCH] [RFD] Add repoid identifier to commit

From: Jon Seymour <jon.seymour@gmail.com>
Date: May 12, 2005, 17:09 UTC
Message-ID: <2cfc403205051210093e1a396d@mail.gmail.com>
In-Reply-To: <20050512162023.GA14010@delft.aura.cs.cmu.edu>

On 5/13/05, Jan Harkes <jaharkes@cs.cmu.edu> wrote:

Show 19 quoted lines

> >
> > Ln
> > |     \
> > Ln-1  Fn
> > |         |
> > Ln-2  Fn-1
> > |       /
> > Ln-3
> 
> It breaks when Fn was a pull from Ln-1, and Ln was a fast-forward to Fn.
> Now the first parent is going to be Fn-1 and the history of the local
> repository after the fast forward warps to
> 
>     Fn (== Ln)
>     Ln-1
>     Ln-2
>     Fn-1
>     Ln-3
>

Yep, you are right.

Show 7 quoted lines

> Which I believe is exactly what Thomas wants to see in this case. I
> don't see how repoid's can be useful for this. It is a porcelain thing
> where you need to track what you have seen before. Anything else doesn't
> matter because most permutations of the history are perfectly valid
> since the Fn and Ln changes in reality occured in parallel and as a
> result can be arbitrarily interleaved.
>

I may be wrong, but I don't think Thomas is interested in his own repository. I think he is interested in the history of commits found in any public repository. Therefore, he needs an algorithm that doesn't rely on locally cached information.

In otherwords, at each point in the commit graph, what did the committer consider as "foreign" changes that needed to be merged into the "local" repository to progress the repository forward. He wants to derive that order only from the information in the repository itself - everyone given the same commit graph should reach the same conclusion as to what the committer saw as local and foreign at the time of the commit.

My previous algorithm was incorrect, but I suspect it could probably be fixed with a 2-pass algorithm that marked any nodes in the path between the merge base and the merge head as local and then ensured that nodes marked that way are sorted after any nodes reached via "foreign" paths.

-- 
homepage: http://www.zeta.org.au/~jon/
blog: http://orwelliantremors.blogspot.com/