Instead of inflicting a Perl script on us, maybe writing a
textual specification of what you want it to do would help to
clarify your thinking and help us understand the problem you are
trying to describe a lot better. I think Linus publicly stated
he does not do Perl much. I am OK with Perl but I'd rather
answer questions posed in a more reader-friendly manner, rather
than having to guess what the caller is expected to give this
"merge" sub, which you do not document well.
I think I've already asked you something quite similar when you
posted another part of your script for parsing the new diff-raw
format, which I responded with something like: "Without knowing
how this sub is supposed to be called, I think you are stripping
leading colon from a filename if there is one". Anyhow.
Are you trying to implement an Octopus capable N-way merger?
If so, the way I would do would be something like this:
- Accept N parameters, which are heads being merged.
- Sanity check that given heads are commits, and N <= 16.
- Initialize a set, HTM (heads to be merged), to contain all of
the supplied heads.
- Remove one commit from HTM, call it H0.
- Initialize a variable, BASE, with H0. This variable
determines the base of the merge in the commit topology.
- Initialize a variable, T, with tree associated with H0. This
variable holds the "current intermediate merge result" tree.
- While HTM is not empty, loop over the following:
- Remove one commit out of HTM; call it H1.
- MB = git-merge-base BASE H1;
- If MB is either BASE or H1, then you have a fast forward.
Take either BASE or H1 that is not MB and update variable
BASE with it, and update variable T with the tree
associated with it. Continue with the loop (i.e. Perl
"next").
- Run your usual read-tree -m MB T H1 and git-merge-cache; as
Linus explained, if this step ends up involving any
non-trivial merges, you should not do an Octopus. So in
such a case, if HTM is not empty yet, barf (i.e. Perl
"die", or at least "last").
- Do not touch your ${GIT-.git}/HEAD in any way at this
moment.
- Update variable T with git-write-tree of the resolved cache
contents.
- Update varaible BASE with MB.
- Continue with the loop.
- We exited the loop by now. HTM being empty means that T has
the result of N-way merge. Create a single commit object
that has all the commits you have merged as its parents, and
register T as its associated tree. I would imagine recording
that commit in ${GIT-.git}/HEAD is what the user usually
wants but there may be use cases that it may not be
appropriate (I do not do Porcelain so I do not know).
Hello,
okay let me try again.
I have a function merge which gets a sorted array of heads. Heads can be
unlimited at the time because some of the heads can be included into
other heads (they're a subset) and so they don't show up in the commit
object. I call this array MERGE_HEADS.
Note: If I pull into an empty tree (no HEAD) there is only one head in
this array which corresponds to the remote_head. Otherwise the first
element is *always* the local HEAD.
After that I am starting looping over MERGE_HEADS. The first thing I
have to do is getting the first element out of this array and safe it
for later reference I call this 'head'. Also I have to push this head in
a another array called COMMIT_HEADS which will be used to create the final
commit object later on. The latter will be done for every loop pass. next;
Note: If I left the the loop because there are no more MERGE_HEADS to
work on and my COMMIT_HEADS array consists only of *one* member I don't
create a COMMIT object, but save it as new HEAD because we're in a fast
forward condition (this could be pulling into an empty tree; having many
fast forward object (remote is ahead or included into the current
'head'). On the contrary if I have *more* than one object I call
commit-tree with the COMMIT_HEADS as arguments and save the new head
return from this call.
Now I start processing the second HEAD from MERGE_HEADS. I use
merge_base to find out the MERGE_BASE. If this MERGE_BASE ==
head than we have a (remote is fast forward condition) so our
CURRENT_HEAD becomes head and I delete the week of the last element of
COMMIT_HEADS (but leaving the CURRENT_HEAD in COMMIT_HEADS). next;
If MERGE_BASE == CURRENT_HEAD than CURRENT_HEAD is already included in
our history so no need to anything, but get it out of COMMIT_HEADS.
next; If it isn't a fast forward or already included case, we do
automatic/threeway/manual merge and save the resulting tree for the
maybe to come next automatic/threeway/manual merge. And of course also
leaving the CURRENT_HEAD in COMMIT_HEADS. FIXME: Do we need to update
our 'head' to the REMOTE_HEAD? next;
Oh and of course the sanity check: I can't commit-tree more than 16
parents at a time. (16 is of course the define mentioned by Linus
before).
That's it.
Thomas
quoted
quoted
quoted
quoted
"TG" == Thomas Glanzmann [off-list ref] writes:
TG> Note: If I pull into an empty tree (no HEAD) there is only one head in
TG> this array which corresponds to the remote_head. Otherwise the first
TG> element is *always* the local HEAD.
"An empty tree (no HEAD)"? Is your definition of "an empty
tree" the same as "empty" directory after you do "mkdir empty &&
cd empty && git-init-db", followed by bunch of git-*-pull to get
the objects and commits from other reposititories being involved
in the merge but without touching .git/HEAD? If so, why cannot
I do the git-*-pull from multiple repositories and merge them
together? Why "there is only one head in this array that is
remote_head"? Oh, I guess I am missing your definition of
"remote_head". Puzzled...
Anyhow I presume that if your ${GIT-.git}/HEAD exists, you
include it as the first element of MERGE_HEADS.
TG> I have a function merge which gets a sorted array of heads. Heads can be
TG> unlimited at the time because some of the heads can be included into
TG> other heads (they're a subset) and so they don't show up in the commit
TG> object. I call this array MERGE_HEADS.
Sorry I am not very good at this "thinking" thing, and I need to
draw pictures. Please bear with me.
(line of dev C)-------------C We are here, trying to merge
(line of dev B)---(merge)---B these three lines of devs:
(line of dev A)---A/ A, B and C
MERGE_HEADS = (A B C)
A is actually a "subset" of B
Is this what you mean by "subset"? Are these "subset" HEAD the
only thing that causes fast forwards?
My gut feeling without thinking much is that it might be easier
to first cull such fast forward heads by using N-way rev-tree
before you do anything else. If only one head survives after
that, then that head would be your new head and you do not have
to go through any merges. Otherwise you merge those independent
heads without worrying about fast forwards. How does that
sound?
Hello,
[ => Skip till next ']' if you want because my approach doesn't work out
for all cases in the optimal way.
"An empty tree (no HEAD)"? Is your definition of "an empty
tree" the same as "empty" directory after you do "mkdir empty &&
cd empty && git-init-db", followed by bunch of git-*-pull to get
the objects and commits from other reposititories being involved
in the merge but without touching .git/HEAD?
Yep. In practice it isn't anything else than just using the first
'remote' HEAD as 'local' HEAD if there is no 'local' HEAD. But for merge
this doesn't really matter.
If so, why cannot I do the git-*-pull from multiple repositories and
merge them together? Why "there is only one head in this array that
is remote_head"? Oh, I guess I am missing your definition of
"remote_head". Puzzled...
My intention by writing this note was to clear things up. That it also
works for cases where you do the 'initial clone' for one and multiple
remotes.
Anyhow I presume that if your ${GIT-.git}/HEAD exists, you
include it as the first element of MERGE_HEADS.
Affirmative.
TG> I have a function merge which gets a sorted array of heads. Heads can be
TG> unlimited at the time because some of the heads can be included into
TG> other heads (they're a subset) and so they don't show up in the commit
TG> object. I call this array MERGE_HEADS.
Here is a typo: MERGE_HEADS is *not* sorted. But it is 'ordered'.
Sorry I am not very good at this "thinking" thing, and I need to
draw pictures. Please bear with me.
Of course, I do.
(line of dev C)-------------C We are here, trying to merge
(line of dev B)---(merge)---B these three lines of devs:
(line of dev A)---A/ A, B and C
MERGE_HEADS = (A B C)
A is actually a "subset" of B
Is this what you mean by "subset"? Are these "subset" HEAD the
only thing that causes fast forwards?
Exactly, but it has not to be a merge it also can be a linear
development. What matters that A is referenced in any way in the history
of B.
In this case where A is referenced in the history of B, we just discard
HEAD A, because it is already merged. So A will never show up in
git-commit-tree in one of its "-p" options. But I mention it in the
commit-text as 'there was nothing todo'.
If we take now your example and switch the order A and B we have
MERGE_HEADS = (B A C) and A is still in the history of B:
We do exactly the same here only that in the above scenario we have to
kick out the previous COMMIT_HEAD when processing B while we drop the
current COMMIT_HEAD when processing A in this scenario. So to clear
things up:
The HEAD we are working on is surrouned by '*'s.
MERGE_HEADS = (*B* A C) => COMMIT_HEADS = (B)
MERGE_HEADS = (B *A* C) => COMMIT_HEADS = (B) /* note: A never did it in COMMIT_HEADS because it was referenced in history of B */
MERGE_HEADS = (B A *C*) => COMMIT_HEADS = (B C)
while in the above example with your initial order it is:
MERGE_HEADS = (*A* B C) => COMMIT_HEADS = (A)
MERGE_HEADS = (A *B* C) => COMMIT_HEADS = (B) /* note: A is kicked out of COMMIT_HEADS ... see above */
MERGE_HEADS = (A B *C*) => COMMIT_HEADS = (B C)
]
My gut feeling without thinking much is that it might be easier
to first cull such fast forward heads by using N-way rev-tree
before you do anything else. If only one head survives after
that, then that head would be your new head and you do not have
to go through any merges. Otherwise you merge those independent
heads without worrying about fast forwards. How does that
sound?
You're right. Because this would work out bad (unneccessary
automatic/threeway/manual merge) if we twist MERGE_HEADS again:
MERGE_HEADS = (*C* A B) => COMMIT_HEADS (C)
MERGE_HEADS = (C *A* B) => COMMIT_HEADS (C A) /* A stays in because it is not in the history of C; -> unneccessary merge */
MERGE_HEADS = (C A *B*) => COMMIT_HEADS (C A B)
Okay, so I have to elminate all fast forward conditions in the first
place? How do I do this:
foreach CURRENT_HEAD (@MERGE_HEADS) {
foreach COMPARE_HEAD (@MERGE_HEADS) {
if (COMPARE_HEAD != CURRENT_HEAD
&& COMPARE_HEAD is_included_into_history_of CURRENT_HEAD) {
@WIPE_HEADS += COMPARE_HEAD;
}
}
}
foreach (@WIPE_HEADS) {
grep -v @WIPE_HEADS @MERGE_HEADS;
}
Thomas
Hello,
I also have to strip duplicate HEADs out. So we do the following:
run 0: kill dups
run 1: kill HEADs which are referenced in the history of other HEADs
run 2: do the merging (still don't know to what I should set the local
HEAD to the 'left' or 'right' part. Maybe we should create temporary
commit object so that 'merge-base' can better work on them?
Thomas