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

From: Jon Seymour <jon.seymour@gmail.com>
Date: May 12, 2005, 15:48 UTC
Message-ID: <2cfc403205051208483132921@mail.gmail.com>
In-Reply-To: <2cfc4032050512084426ea3d4d@mail.gmail.com>

| small clarification to algorithm, removed editing work area

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

Show 12 quoted lines

> On Thu, May 12, 2005 at 01:43:50PM +0200, Thomas Gleixner wrote:
> ....
> Your examples break if you consider additional merges where M syncs up a
> couple of times (f.i. at Rn-2) before M is merged back into R.
>
> What you seem to want won't be fixed by adding a repoid, you need to
> keep a list of all the commits you have already seen and append any new
> ones whenever you look at the history. If you look whenever you pull or
> merge the list will be in the total ordering that you seem to expect for
> your repository. But that is a porcelain thing.
>
> Jan

If committers always follow the convention that their previous local commit is nominated as the first (local) parent in the commit and commits from foreign repositories are listed after the first parent, can the chain of "local" parents be an effective proxy for repoid?

Consider first a graph where there are no more than 2 parents in a merge

Ln
|     \
Ln-1  Fn
|         |
Ln-2  Fn-1
|       /
Ln-3

Thomas would like to sort this as:

Ln Fn Fn-1 Ln-1 Ln-2 Ln-3

So, use this algorithm:

1. Merge result comes first.
2. For each foreign parent:
    - sort the graph between the foreign parent and the merge base
(not including merge base) according to his algorithm using the
foreign parent as the starting
point of the algorithm. Append the result into the list.
3. Append the merge base to the list.

Admittedly the order for foreign parent for N-way merges is somewhat arbitrary but a committer could probably make a choice that "works" in most cases by specifying the foreign parents in a "sensible" order.

Of course, this relies on a committer always nominating the local parent first, but that wouldn't be hard to enforce in the porcelain layer.

jon.

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