Re: Automatic merge failed, fix up by hand
Linus Torvalds <[EMAIL PROTECTED]> writes: > Ok, I think your approach is the correct one. Just list all the commits, > and let the merge logic figure out which one is the best one. > > Just returning several entries is the correct thing to do, because then > you can make the distance function be based on the tree diffs, like you > do. That's _much_ better than trying to make the distance be based on some > topology. > > So I append this patch just as a historical curiosity. Junio's patch is > clearly superior. > > Linus Of course it is clearly superior, because it is not _my_ patch but *yours*. I just did what you earlier told the world how things should work, based on this message: Date: Mon, 11 Apr 2005 16:48:25 -0700 (PDT) From: Linus Torvalds <[EMAIL PROTECTED]> Subject: Re: git: patch for parent-id and idea for merge Message-ID: <[EMAIL PROTECTED]> Btw, I've changed the semantics of "rev-tree" once again. ... In other words, it will give you a way to figure out which changeset to use as the common one. It's always going to be a parent of one of these edge-commits that has all of its reachability bits set. Which one.. Now that's the question. Maybe just the most recent one, or maybe actually use "diff-tree" to see which one generates the fewest conflicts. - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Automatic merge failed, fix up by hand
On Tue, 23 Aug 2005, Junio C Hamano wrote: > Only lightly tested, in the sense that I did only this one case > and nothing else. For a large repository and with complex > merges, "merge-base -a" _might_ end up reporting many > candidates, in which case the pre-merge step to figure out the > best merge base may turn out to be disastrously slow. I dunno. I think it's the right thing to do for now (and what I was going to suggest), and if people find it too slow, we can consider teaching read-tree to take multiple common ancestors and use any of them that gives clear result on a per-file basis. On the other hand, Tony might have hit a bad case with an ill-chosen common ancestor for a patch/revert sequence, and we probably want to look into that if we've got some history that demonstrates the problem. I think that, if there are two common ancestors, one of which has applied a patch and one of which hasn't, and on one side of the merge it gets reverted, we should get the revert, but we'll only get it if we choose the ancestor where it was applied. (Letters are versions of the file, which 'b' being the bad patch; the second column is the two choices for common ancestor) a-b-a-? / X / a-b-b-b Of course, you could have the two lines exactly flipped for a different file in the same commits, or for a different hunk in the same file, and there would be no single choice that doesn't lose the revert. The really right thing to do is identify that there is a b->a transition that is not a trivial merge and that is not beyond a common ancestor, but that's hard to determine easily and with sufficient granularity to catch everything. I still someday want to do a version of diff/merge for git that could select common ancestors on a per-hunk basis and identify block moves and avoid giving confusing (but marginally shorter) diffs, but that's a major undertaking that I don't have time for right now. -Daniel *This .sig left intentionally blank* - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Automatic merge failed, fix up by hand
On Tue, 2005-08-23 at 21:07 -0400, Junio C Hamano wrote: > Junio C Hamano <[EMAIL PROTECTED]> writes: > > > Probably the ideal way would be to give merge-base an option to > > spit out all the candidates, and have the script try to see > > which ones yield the least number of non-trivial merges. > > I first checked out your 702c7e.. commit, and slurped Linus tip > (back then, 81065e2f415af6c028eac13f481fb9e60a0b487b). Then I > ran git resolve with the attached patch (against the tip of > git.git "master" branch). Here is what happened, which seems to > work a little bit better, at least to me. > > prompt$ git checkout -f > prompt$ git status > nothing to commit > prompt$ ls -l .git/HEAD > lrwxrwxrwx 1 junio src 26 Aug 23 15:43 .git/HEAD -> > refs/heads/lenb > prompt$ git resolve HEAD origin 'Merge Linus into Lenb' > Trying to find the optimum merge base > Trying to merge 81065e2f415af6c028eac13f481fb9e60a0b487b into > 702c7e7626deeabb057b6f529167b65ec2eefbdb using > 3edea4833a1efcd43e1dff082bc8001fdfe74b34 Looking at gitk, it certainly chose the right ancestor in this case. > Simple merge failed, trying Automatic merge > Auto-merging Documentation/acpi-hotkey.txt. > merge: warning: conflicts during merge > ERROR: Merge conflict in Documentation/acpi-hotkey.txt. > Auto-merging drivers/acpi/osl.c. > fatal: merge program failed > Automatic merge failed, fix up by hand > > Only lightly tested, in the sense that I did only this one case > and nothing else. For a large repository and with complex > merges, "merge-base -a" _might_ end up reporting many > candidates, in which case the pre-merge step to figure out the > best merge base may turn out to be disastrously slow. I dunno. It ran a heck of a lot faster than the alternative -- which would have been to export 85 patches and re-commit them to a new tree. Perhaps Tony's recent merge mystery had the same cause and he can also benefit from this patch? thanks! -Len - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Automatic merge failed, fix up by hand
On Tue, 23 Aug 2005, Junio C Hamano wrote: > > Only lightly tested, in the sense that I did only this one case > and nothing else. For a large repository and with complex > merges, "merge-base -a" _might_ end up reporting many > candidates, in which case the pre-merge step to figure out the > best merge base may turn out to be disastrously slow. I dunno. Ok, I think your approach is the correct one. Just list all the commits, and let the merge logic figure out which one is the best one. Here, in case anybody cares, is an alternate approach, which sucks. It _happens_ to pick the right parent in this case, but when I look at why it picks it, it's pretty much just pure luck again. The distance function is not good. Just returning several entries is the correct thing to do, because then you can make the distance function be based on the tree diffs, like you do. That's _much_ better than trying to make the distance be based on some topology. So I append this patch just as a historical curiosity. Junio's patch is clearly superior. Linus --- diff --git a/merge-base.c b/merge-base.c --- a/merge-base.c +++ b/merge-base.c @@ -82,10 +82,84 @@ static struct commit *interesting(struct * commit B. */ +/* + * Count the distance from one commit to the base, using a very + * stupid recursive algorithm. We only avoid recursion when seeing + * a single parent. + */ +static unsigned long count_distance(struct commit *head, struct commit *base) +{ + struct commit_list *parents; + unsigned long distance = ULONG_MAX; + unsigned long chain = 1; + + /* Walk the chain of direct parents */ + for (;;) { + parents = head->parents; + if (!parents) + goto no_parent; + /* Multiple parents? */ + if (parents->next) + break; + head = parents->item; + if (head == base) + return chain; + chain++; + } + + while (parents) { + struct commit *c = parents->item; + unsigned long d; + + parents = parents->next; + if (c == base) + return chain; + if (c->object.flags & UNINTERESTING) + continue; + d = count_distance(c, base); + if (d < distance) + distance = d; + } + if (distance != ULONG_MAX) + return distance + chain; +no_parent: + return ULONG_MAX; +} + +/* + * There are some really nasty cases where we get multiple apparently + * equally valid parents, and we need to disambiguate them. + * + * We aim for the one whose total distance to the two revisions is the + * smallest, where distance is "x**2 + y**2" (we _much_ prefer a nice + * balanced equidistant one over one that is near to one but far from + * the other) + */ +static struct commit *pick_best_commit(struct commit_list *list, struct commit *rev1, struct commit *rev2) +{ + unsigned long distance = ULONG_MAX; + struct commit *best = NULL; + + do { + struct commit *base = list->item; + unsigned long d1 = count_distance(rev1, base); + unsigned long d2 = count_distance(rev2, base); + unsigned long d = d1*d1 + d2*d2; + +fprintf(stderr, "distance analysis: %s: %lu %lu %lu\n", sha1_to_hex(base->object.sha1), d1, d2, d); + if (d < distance) { + distance = d; + best = base; + } + } while ((list = list->next) != NULL); + return best; +} + static struct commit *common_ancestor(struct commit *rev1, struct commit *rev2) { struct commit_list *list = NULL; struct commit_list *result = NULL; + struct commit_list *final = NULL; if (rev1 == rev2) return rev1; @@ -122,7 +196,32 @@ static struct commit *common_ancestor(st insert_by_date(p, &list); } } - return interesting(result); + + /* +* Go through the result list, and pick out unique +* members to put on the final list. +*/ + while (result) { + struct commit_list *entry = result; + struct commit *c = result->item; + result = result->next; + if (c->object.flags & UNINTERESTING) + continue; + if (c == rev1 || c == rev2) + return c; + entry->next = final; + final = entry; + c->object.flags |= UNINTERESTING; + } + + if (!final) + return NULL; + + /* Just one entry? */ + if (!final->next) + return final->item; + + return pick_best_commit(final, rev1, rev2); } int main(int argc, char **argv) - To unsubscribe from this list
Re: Automatic merge failed, fix up by hand
Junio C Hamano <[EMAIL PROTECTED]> writes: > Probably the ideal way would be to give merge-base an option to > spit out all the candidates, and have the script try to see > which ones yield the least number of non-trivial merges. I first checked out your 702c7e.. commit, and slurped Linus tip (back then, 81065e2f415af6c028eac13f481fb9e60a0b487b). Then I ran git resolve with the attached patch (against the tip of git.git "master" branch). Here is what happened, which seems to work a little bit better, at least to me. prompt$ git checkout -f prompt$ git status nothing to commit prompt$ ls -l .git/HEAD lrwxrwxrwx 1 junio src 26 Aug 23 15:43 .git/HEAD -> refs/heads/lenb prompt$ git resolve HEAD origin 'Merge Linus into Lenb' Trying to find the optimum merge base Trying to merge 81065e2f415af6c028eac13f481fb9e60a0b487b into 702c7e7626deeabb057b6f529167b65ec2eefbdb using 3edea4833a1efcd43e1dff082bc8001fdfe74b34 Simple merge failed, trying Automatic merge Auto-merging Documentation/acpi-hotkey.txt. merge: warning: conflicts during merge ERROR: Merge conflict in Documentation/acpi-hotkey.txt. Auto-merging drivers/acpi/osl.c. fatal: merge program failed Automatic merge failed, fix up by hand Only lightly tested, in the sense that I did only this one case and nothing else. For a large repository and with complex merges, "merge-base -a" _might_ end up reporting many candidates, in which case the pre-merge step to figure out the best merge base may turn out to be disastrously slow. I dunno. --- git diff HEAD diff --git a/git-resolve-script b/git-resolve-script --- a/git-resolve-script +++ b/git-resolve-script @@ -49,7 +49,42 @@ if [ "$common" == "$head" ]; then dropheads exit 0 fi -echo "Trying to merge $merge into $head" + +# Find optimum merge base if there are more than one candidate. +LF=' +' +common=$(git-merge-base -a $head $merge) +case "$common" in +?*"$LF"?*) + echo "Trying to find the optimum merge base" + G=.tmp-index$$ + best= + best_cnt=-1 + for c in $common + do + rm -f $G + GIT_INDEX_FILE=$G git-read-tree -m $c $head $merge \ + 2>/dev/null || continue + if GIT_INDEX_FILE=$G git-write-tree 2>/dev/null + then + # This one results in just a Simple merge; + # It cannot become better than this. + best=$c + break + fi + # Otherwise, count the paths that are unmerged. + cnt=`GIT_INDEX_FILE=$G git-ls-files --unmerged | wc -l` + if test $best_cnt -le 0 -o $cnt -le $best_cnt + then + best=$c + best_cnt=$cnt + fi + done + rm -f $G + common="$best" +esac + +echo "Trying to merge $merge into $head using $common" git-read-tree -u -m $common $head $merge || exit 1 result_tree=$(git-write-tree 2> /dev/null) if [ $? -ne 0 ]; then diff --git a/merge-base.c b/merge-base.c --- a/merge-base.c +++ b/merge-base.c @@ -82,13 +82,17 @@ static struct commit *interesting(struct * commit B. */ -static struct commit *common_ancestor(struct commit *rev1, struct commit *rev2) +static int show_all = 0; + +static int merge_base(struct commit *rev1, struct commit *rev2) { struct commit_list *list = NULL; struct commit_list *result = NULL; - if (rev1 == rev2) - return rev1; + if (rev1 == rev2) { + printf("%s\n", sha1_to_hex(rev1->object.sha1)); + return 0; + } parse_commit(rev1); parse_commit(rev2); @@ -108,7 +112,7 @@ static struct commit *common_ancestor(st if (flags == 3) { insert_by_date(commit, &result); - /* Mark children of a found merge uninteresting */ + /* Mark parents of a found merge uninteresting */ flags |= UNINTERESTING; } parents = commit->parents; @@ -122,26 +126,46 @@ static struct commit *common_ancestor(st insert_by_date(p, &list); } } - return interesting(result); + + if (!result) + return 1; + + while (result) { + struct commit *commit = result->item; + result = result->next; + if (commit->object.flags & UNINTERESTING) + continue; + printf("%s\n", sha1_to_hex(commit->object.sha1)); + if (!show_all) + return 0; + commit->object.flags |= UNINTERESTING; + } + return 0; } +static const char merge_base_usage[] = +"git-merge-base [--all] "; + int main(int argc, char **argv) { - struct commit *rev1, *rev2, *ret; + st
Re: Automatic merge failed, fix up by hand
On Tue, 23 Aug 2005, Len Brown wrote: > > I'm having trouble using git for merging kernel trees. > > git seems to manufacture conflicts in files that > I never touched, and on some files it completely > throws up its arms, see "Not handling case" below. Cool. You've found a case where git-merge-base finds what appears to be two equally good merge candidates, but they really aren't. The merge candidates are 30e332f3307e9f7718490a706e5ce99f0d3a7b26 and 3edea4833a1efcd43e1dff082bc8001fdfe74b34. To see this graphically, do: echo 30e332f3307e9f7718490a706e5ce99f0d3a7b26 > .git/refs/tags/selected-merge-base echo 3edea4833a1efcd43e1dff082bc8001fdfe74b34 > .git/refs/tags/other-merge-base echo 81065e2f415af6c028eac13f481fb9e60a0b487b > .git/refs/tags/linus-head echo 702c7e7626deeabb057b6f529167b65ec2eefbdb > .git/refs/tags/lenb-head gitk --all and notice how the not-selected one is: Author: Antonino A. Daplas <[EMAIL PROTECTED]> 2005-08-15 06:29:11 Committer: Linus Torvalds <[EMAIL PROTECTED]> 2005-08-15 09:59:39 Tags: not-selected while the selected on is: Author: Luming Yu <[EMAIL PROTECTED]> 2005-08-11 21:31:00 Committer: Len Brown <[EMAIL PROTECTED]> 2005-08-15 12:46:58 Tags: selected and the reason we chose that one is that it's three hours later than the other one, and we don't know any better. > Not clear how I got into this state -- probably > something to do with adding commits on branches > and them git-pull-branch'ing them into the master; > combined with updating the master from-linus. No, it's git. Well, it's git, together with your propensity to merge old work, which causes this kind of confusion where there are two "equally good" points to choose from as the merge base, and git chose the wrong one because it _looked_ newer and there was a recent merge to an old version of my tree. Cross-merges cause this, but I'm sure there's a good algorithm for selecting _which_ of the two interesting commits to pick. Give me a moment to think about this. Linus - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Automatic merge failed, fix up by hand
Junio C Hamano <[EMAIL PROTECTED]> writes: > I think merge-base, even though we attempted to fix it recently, > is still confused and that is one of the reasons why you are > getting this. > > prompt$ git-rev-parse origin test-lenb-merge > 81065e2f415af6c028eac13f481fb9e60a0b487b > 702c7e7626deeabb057b6f529167b65ec2eefbdb -->8-- snip -->8-- > + Merge ../to-linus-stable/ > ++ [ACPI] re-enable platform-specific hotkey drivers by default > + ARM: 2851/1: Fix NWFPE extended precision exception handling > ++ [origin~34] intelfb/fbdev: Save info->flags in a local variable > prompt$ git-rev-parse origin~34 > 3edea4833a1efcd43e1dff082bc8001fdfe74b34 I spoke too fast. merge-base is not giving you an incorrect answer. It just happens that the answer was way suboptimal. The "[ACPI] re-enable platform-specific hotkey" is what it chose, and my monkey guessing origin~34 happened to be better merge base, but the logic used by merge-base is to pick the latest (from wallclock wise) commit among several candidates, and by that criteria it did the "right" thing. In this case, the "right" thing was a wrong decision. So we probably should revisit how we choose the "best" merge base among candidates. I think "origin~34" which happened to be the last one output by "git show-branch" was just an accident, not a good rule to follow, so changing merge-base to use the one that the other command shows the last would not be a good way to fix this. Probably the ideal way would be to give merge-base an option to spit out all the candidates, and have the script try to see which ones yield the least number of non-trivial merges. Linus? - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Automatic merge failed, fix up by hand
On Tue, 2005-08-23 at 19:58 -0400, Junio C Hamano wrote: > Len Brown <[EMAIL PROTECTED]> writes: > > >> I could get to 81065e2f415af6... commit (Linus tip at this > >> moment), so if you can tell me where to snarf the other commit > >> (702c7e76) that would help me diagnose the problem a lot. > > > > rsync://rsync.kernel.org/pub/scm/linux/kernel/git/lenb/to-akpm.git > > Thanks. > > I think merge-base, even though we attempted to fix it recently, > is still confused and that is one of the reasons why you are > getting this. > > prompt$ git-rev-parse origin test-lenb-merge > 81065e2f415af6c028eac13f481fb9e60a0b487b > 702c7e7626deeabb057b6f529167b65ec2eefbdb > prompt$ git-merge-base origin test-lenb-merge > 30e332f3307e9f7718490a706e5ce99f0d3a7b26 > prompt$ git show-branch origin test-lenb-merge > ! [origin] zd1201 kmalloc size fix > * [test-lenb-merge] [ACPI] fix ia64 build issues resulting from > L... > -- > + [origin] zd1201 kmalloc size fix > + [origin~1] md: make sure resync gets started when array starts. > + [origin~2] preempt race in getppid > + [origin~3] Merge master.kernel.org:/pub/scm/linux/kernel/git/da > -- >8 -- snip -- >8 -- > + Merge ../to-linus-stable/ > ++ [ACPI] re-enable platform-specific hotkey drivers by default > + ARM: 2851/1: Fix NWFPE extended precision exception handling > ++ [origin~34] intelfb/fbdev: Save info->flags in a local variable > prompt$ git-rev-parse origin~34 > 3edea4833a1efcd43e1dff082bc8001fdfe74b34 > > Notice that show-branch, which walks the commit ancestry chain > pretty much the same way merge-base does, notices and stops at > origin~34 (that's 34th generation first parent commit from Linus > tip) that is the common commit between the two heads being > merged? And that commit, 3edea48... is different from what > merge-base is reporting. > > If I maually run merge-cache using origin~34 as the merge base, > only the following two files needs to result in non-simple merge: > > Documentation/acpi-hotkey.txt > drivers/acpi/osl.c > > Do these two files match your expectation? No, I don't think so. Unless I missed something, to-akpm should be a proper super-set of from-linus, so I wouldn't expect a merge on these two. > I'll take a look at merge-base.c next, but just in case I CC:ed > this to Linus, who is more familiar with that code. thanks, -Len - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Automatic merge failed, fix up by hand
Len Brown <[EMAIL PROTECTED]> writes: >> I could get to 81065e2f415af6... commit (Linus tip at this >> moment), so if you can tell me where to snarf the other commit >> (702c7e76) that would help me diagnose the problem a lot. > > rsync://rsync.kernel.org/pub/scm/linux/kernel/git/lenb/to-akpm.git Thanks. I think merge-base, even though we attempted to fix it recently, is still confused and that is one of the reasons why you are getting this. prompt$ git-rev-parse origin test-lenb-merge 81065e2f415af6c028eac13f481fb9e60a0b487b 702c7e7626deeabb057b6f529167b65ec2eefbdb prompt$ git-merge-base origin test-lenb-merge 30e332f3307e9f7718490a706e5ce99f0d3a7b26 prompt$ git show-branch origin test-lenb-merge ! [origin] zd1201 kmalloc size fix * [test-lenb-merge] [ACPI] fix ia64 build issues resulting from L... -- + [origin] zd1201 kmalloc size fix + [origin~1] md: make sure resync gets started when array starts. + [origin~2] preempt race in getppid + [origin~3] Merge master.kernel.org:/pub/scm/linux/kernel/git/da -- >8 -- snip -- >8 -- + Merge ../to-linus-stable/ ++ [ACPI] re-enable platform-specific hotkey drivers by default + ARM: 2851/1: Fix NWFPE extended precision exception handling ++ [origin~34] intelfb/fbdev: Save info->flags in a local variable prompt$ git-rev-parse origin~34 3edea4833a1efcd43e1dff082bc8001fdfe74b34 Notice that show-branch, which walks the commit ancestry chain pretty much the same way merge-base does, notices and stops at origin~34 (that's 34th generation first parent commit from Linus tip) that is the common commit between the two heads being merged? And that commit, 3edea48... is different from what merge-base is reporting. If I maually run merge-cache using origin~34 as the merge base, only the following two files needs to result in non-simple merge: Documentation/acpi-hotkey.txt drivers/acpi/osl.c Do these two files match your expectation? I'll take a look at merge-base.c next, but just in case I CC:ed this to Linus, who is more familiar with that code. - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Automatic merge failed, fix up by hand
On Tue, 2005-08-23 at 18:06 -0400, Junio C Hamano wrote: > Len Brown <[EMAIL PROTECTED]> writes: > > > The merge issue below is reproduced in a "git clone -l" copy > > with no plain files present. > > Meaning you did not have any file in the working tree? It seems > to me that what is happenning is the resolve is trying to merge > the head of your tree and from-linus, but at the same time it > notices that you removed those files from your working tree and > thinks that is what you would want to do. Doesn't matter if the merge is after a git checkout -f or not. I was just pointing out that it also fails if there are no plain files checked out. > I could get to 81065e2f415af6... commit (Linus tip at this > moment), so if you can tell me where to snarf the other commit > (702c7e76) that would help me diagnose the problem a lot. rsync://rsync.kernel.org/pub/scm/linux/kernel/git/lenb/to-akpm.git fails when merged into latest linus, or when latest linus is merged into it. I suspect some artifact of my patches being based on one of several branches rooted at 2.6.12 is the issue, and that in switching between latest 2.6.13 and stable 2.6.12 branches, some state has bled through that now confuses the heck out of resolve. thanks, -Len - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Automatic merge failed, fix up by hand
Len Brown <[EMAIL PROTECTED]> writes: > The merge issue below is reproduced in a "git clone -l" copy > with no plain files present. Meaning you did not have any file in the working tree? It seems to me that what is happenning is the resolve is trying to merge the head of your tree and from-linus, but at the same time it notices that you removed those files from your working tree and thinks that is what you would want to do. I could get to 81065e2f415af6... commit (Linus tip at this moment), so if you can tell me where to snarf the other commit (702c7e76) that would help me diagnose the problem a lot. Thanks. - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html