threads / discuss / 14275

Question about git-merge-stupid

Subject: Question about git-merge-stupid

## tl;dr

7 messages between Jul 3, 2008 and Jul 5, 2008.

replies: 6people: 3as markdown or json

Miklos Vajna· Jul 3, 2008, 12:33 UTC · lore
Hi,

I'm trying to understand what is the difference between different merge strategies. git-merge-stupid is something I failed to understand from the git history/code/documentation, so I'm asking here.

1) From git history:

It seems git-merge-stupid was created by 2276aa6 when Junio renamed -resolve to -stupid and let -resolve use read-tree. Actually

        git show 2276aa6:git-merge-stupid.sh
says -stupid uses read-tree as well.
2) From code:

It seems -stupid is better than -resolve when there are multiple bases. -resolve just passes all bases to read-tree, while -stupid tries to find the best one. It does it by counting unmerged entries and the less one is a better.

Here is what I tried:
A - B - C
      X   \
  \ D - E - F
(Where 'A' adds 'a.c' while the contents 'a', etc.)

$ git reset --hard e $ git merge -s resolve c Trying simple merge. Merge made by resolve.

So it seems resolve does not completely fail if there are multiple bases, either.

I would like to write a testcase that ensures git-merge-stupid really picks the best base, but I don't know exactly in what situation can the number of unmerged entires differ.

3) From documentation:

Actually -stupid is missing from Documentation/merge-strategies.txt. I plan to send a patch to add it, once I understnad what it does. :-)

Thanks.

[ Writing to Linus as suggested by Dscho, adding Junio to CC as - according to git log - both strategy created by him. ]

Linus Torvalds· Jul 3, 2008, 17:08 UTC · re: Miklos Vajna · lore

Re: Question about git-merge-stupid

On Thu, 3 Jul 2008, Miklos Vajna wrote:
Show 13 quoted lines
> 
> I'm trying to understand what is the difference between different merge
> strategies. git-merge-stupid is something I failed to understand from
> the git history/code/documentation, so I'm asking here.
> 
> 1) From git history:
> 
> It seems git-merge-stupid was created by 2276aa6 when Junio renamed
> -resolve to -stupid and let -resolve use read-tree. Actually
> 
>         git show 2276aa6:git-merge-stupid.sh
> 
> says -stupid uses read-tree as well.
I think -stupid should probably be removed.

The history of -stupid is from doing the simple single-tree resolve that git-read-tree can do, but then doing the obvious hack of just trying to pick the base that gives the least number of conflicts.

HOWEVER. 
 - in practice, there's seldom any actual point to it. In 99% of all 
   cases, you only have a single merge base anyway.
 - if you have a workflow that encourages criss-cross merges (which makes 
   the above "in practice" not be true), the common case will be that the 
   merge base doesn't much matter.
 - Counting conflicts by looking at the numbe of files that conflict is a 
   pretty stupid metric anyway. Yes, it's obvious, and yes, I bet there 
   are cases where it does the right thing, but I also bet there are cases 
   where it does the _wrong_ thing - it might pick a merge base with fewer 
   files conflicting, but with harder conflicts.
 - the "recursive" merge strategy simply handles things better. There's 
   not really any reason to use a "pick random merge base that happens to 
   give least conflicts", when the recursive strategy does something much 
   more natural.

So you shouldn't really compare -stupid to -resolve. You should compare -stupid to -recursive, and the latter is simply much better.

> 2) From code:
> 
> It seems -stupid is better than -resolve when there are multiple bases.
Maybe. And maybe not.
Show 6 quoted lines
> $ git merge -s resolve c
> Trying simple merge.
> Merge made by resolve.
> 
> So it seems resolve does not completely fail if there are multiple
> bases, either.

I think -resolve can handle up to 6 bases, or something like that. After that it should fail with a "I cannot read more than 8 trees" or something (eight being the two trees to be merged, plus the six bases).

And with multiple bases, it will already pick the best one on a per-file basis (I think - I should know the threeway merge, but it is pretty confusing code) rather than trying to pick one globally. Not pretty, but it's yet another reason why -stupid is actually stupid, and not worth it.

So -stupid in _theory_ can handle cases that -resolve cannot (more than six bases), but (a) that doesn't happen and (b) you'd be better off with -recursive anyway.

> 3) From documentation:
> 
> Actually -stupid is missing from Documentation/merge-strategies.txt. I
> plan to send a patch to add it, once I understnad what it does. :-)

Well, see above. I think there's a reason why -stupid isn't even worth documenting. It might be better off just removed.

		Linus
Miklos Vajna· Jul 3, 2008, 23:18 UTC · re: Linus Torvalds · lore

[RFC/PATCH] Remove 'stupid' merge strategy.

As pointed out by Linus, this strategy tries to take the best merge base, but 'recursive' just does it better. If one needs something more than 'resolve' then he/she should really use 'recursive' and not 'stupid'. ---

On Thu, Jul 03, 2008 at 10:08:54AM -0700, Linus Torvalds <torvalds@linux-foundation.org> wrote:
> I think -stupid should probably be removed.
Here is an attempt to do so.
Show 9 quoted lines
> The history of -stupid is from doing the simple single-tree resolve
> that
> git-read-tree can do, but then doing the obvious hack of just trying
> to
> pick the base that gives the least number of conflicts.
>
> HOWEVER.
>
>  (...)
Thanks for the detailed answer.
 .gitignore          |    1 -
 Makefile            |    3 +-
 git-merge-stupid.sh |   80 ---------------------------------------------------
 3 files changed, 1 insertions(+), 83 deletions(-)
 delete mode 100755 git-merge-stupid.sh
diff --git a/.gitignore b/.gitignore
index 4ff2fec..8054d9d 100644
--- a/.gitignore
+++ b/.gitignore
@@ -75,7 +75,6 @@ git-merge-one-file
 git-merge-ours
 git-merge-recursive
 git-merge-resolve
-git-merge-stupid
 git-merge-subtree
 git-mergetool
 git-mktag
diff --git a/Makefile b/Makefile
index 78e08d3..bddd1a7 100644
--- a/Makefile
+++ b/Makefile
@@ -241,7 +241,6 @@ SCRIPT_SH += git-merge-octopus.sh
 SCRIPT_SH += git-merge-one-file.sh
 SCRIPT_SH += git-merge-resolve.sh
 SCRIPT_SH += git-merge.sh
-SCRIPT_SH += git-merge-stupid.sh
 SCRIPT_SH += git-mergetool.sh
 SCRIPT_SH += git-parse-remote.sh
 SCRIPT_SH += git-pull.sh
@@ -1429,7 +1428,7 @@ check-docs::
 	do \
 		case "$$v" in \
 		git-merge-octopus | git-merge-ours | git-merge-recursive | \
-		git-merge-resolve | git-merge-stupid | git-merge-subtree | \
+		git-merge-resolve | git-merge-subtree | \
 		git-fsck-objects | git-init-db | \
 		git-?*--?* ) continue ;; \
 		esac ; \
diff --git a/git-merge-stupid.sh b/git-merge-stupid.sh
deleted file mode 100755
index f612d47..0000000
--- a/git-merge-stupid.sh
+++ /dev/null
@@ -1,80 +0,0 @@
-#!/bin/sh
-#
-# Copyright (c) 2005 Linus Torvalds
-#
-# Resolve two trees, 'stupid merge'.
-
-# The first parameters up to -- are merge bases; the rest are heads.
-bases= head= remotes= sep_seen=
-for arg
-do
-	case ",$sep_seen,$head,$arg," in
-	*,--,)
-		sep_seen=yes
-		;;
-	,yes,,*)
-		head=$arg
-		;;
-	,yes,*)
-		remotes="$remotes$arg "
-		;;
-	*)
-		bases="$bases$arg "
-		;;
-	esac
-done
-
-# Give up if we are given two or more remotes -- not handling octopus.
-case "$remotes" in
-?*' '?*)
-	exit 2 ;;
-esac
-
-# Find an optimum merge base if there are more than one candidates.
-case "$bases" in
-?*' '?*)
-	echo "Trying to find the optimum merge base."
-	G=.tmp-index$$
-	best=
-	best_cnt=-1
-	for c in $bases
-	do
-		rm -f $G
-		GIT_INDEX_FILE=$G git read-tree -m $c $head $remotes \
-			 2>/dev/null ||	continue
-		# 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
-			if test "$best_cnt" -eq 0
-			then
-				# Cannot do any better than all trivial merge.
-				break
-			fi
-		fi
-	done
-	rm -f $G
-	common="$best"
-	;;
-*)
-	common="$bases"
-	;;
-esac
-
-git update-index --refresh 2>/dev/null
-git read-tree -u -m $common $head $remotes || exit 2
-echo "Trying simple merge."
-if result_tree=$(git write-tree  2>/dev/null)
-then
-	exit 0
-else
-	echo "Simple merge failed, trying Automatic merge."
-	if git-merge-index -o git-merge-one-file -a
-	then
-		exit 0
-	else
-		exit 1
-	fi
-fi
-- 
1.5.6.1
Junio C Hamano· Jul 3, 2008, 23:54 UTC · re: Linus Torvalds · lore

Re: Question about git-merge-stupid

Linus Torvalds <torvalds@linux-foundation.org> writes:
> Well, see above. I think there's a reason why -stupid isn't even worth 
> documenting. It might be better off just removed.
It is called stupid for a reason ;-).

It has been sitting there as an example for a long time, and I do not think anybody minds removing it.

Miklos Vajna· Jul 4, 2008, 00:07 UTC · re: Junio C Hamano · lore

Re: Question about git-merge-stupid

On Thu, Jul 03, 2008 at 04:54:31PM -0700, Junio C Hamano <gitster@pobox.com> wrote:
> It is called stupid for a reason ;-).
> 
> It has been sitting there as an example for a long time, and I do
> not think anybody minds removing it.
OK, then should I resend a patch that moves it to contrib/examples?
Miklos Vajna· Jul 5, 2008, 14:43 UTC · re: Miklos Vajna · lore

[PATCH] Move 'stupid' merge strategy to contrib.

As pointed out by Linus, this strategy tries to take the best merge base, but 'recursive' just does it better. If one needs something more than 'resolve' then he/she should really use 'recursive' and not 'stupid'.

Given that it may still serve as a good example, don't remove it, just move it to contrib/examples. ---

On Fri, Jul 04, 2008 at 02:07:01AM +0200, Miklos Vajna <vmiklos@frugalware.org> wrote:
Show 8 quoted lines
> On Thu, Jul 03, 2008 at 04:54:31PM -0700, Junio C Hamano
> <gitster@pobox.com> wrote:
> > It is called stupid for a reason ;-).
> >
> > It has been sitting there as an example for a long time, and I do
> > not think anybody minds removing it.
>
> OK, then should I resend a patch that moves it to contrib/examples?
Here is one.
 .gitignore                           |    1 -
 Makefile                             |    3 +-
 contrib/examples/git-merge-stupid.sh |   80 ++++++++++++++++++++++++++++++++++
 git-merge-stupid.sh                  |   80 ----------------------------------
 4 files changed, 81 insertions(+), 83 deletions(-)
 create mode 100755 contrib/examples/git-merge-stupid.sh
 delete mode 100755 git-merge-stupid.sh
diff --git a/.gitignore b/.gitignore
index 4ff2fec..8054d9d 100644
--- a/.gitignore
+++ b/.gitignore
@@ -75,7 +75,6 @@ git-merge-one-file
 git-merge-ours
 git-merge-recursive
 git-merge-resolve
-git-merge-stupid
 git-merge-subtree
 git-mergetool
 git-mktag
diff --git a/Makefile b/Makefile
index 78e08d3..bddd1a7 100644
--- a/Makefile
+++ b/Makefile
@@ -241,7 +241,6 @@ SCRIPT_SH += git-merge-octopus.sh
 SCRIPT_SH += git-merge-one-file.sh
 SCRIPT_SH += git-merge-resolve.sh
 SCRIPT_SH += git-merge.sh
-SCRIPT_SH += git-merge-stupid.sh
 SCRIPT_SH += git-mergetool.sh
 SCRIPT_SH += git-parse-remote.sh
 SCRIPT_SH += git-pull.sh
@@ -1429,7 +1428,7 @@ check-docs::
 	do \
 		case "$$v" in \
 		git-merge-octopus | git-merge-ours | git-merge-recursive | \
-		git-merge-resolve | git-merge-stupid | git-merge-subtree | \
+		git-merge-resolve | git-merge-subtree | \
 		git-fsck-objects | git-init-db | \
 		git-?*--?* ) continue ;; \
 		esac ; \
diff --git a/contrib/examples/git-merge-stupid.sh b/contrib/examples/git-merge-stupid.sh
new file mode 100755
index 0000000..f612d47
--- /dev/null
+++ b/contrib/examples/git-merge-stupid.sh
@@ -0,0 +1,80 @@
+#!/bin/sh
+#
+# Copyright (c) 2005 Linus Torvalds
+#
+# Resolve two trees, 'stupid merge'.
+
+# The first parameters up to -- are merge bases; the rest are heads.
+bases= head= remotes= sep_seen=
+for arg
+do
+	case ",$sep_seen,$head,$arg," in
+	*,--,)
+		sep_seen=yes
+		;;
+	,yes,,*)
+		head=$arg
+		;;
+	,yes,*)
+		remotes="$remotes$arg "
+		;;
+	*)
+		bases="$bases$arg "
+		;;
+	esac
+done
+
+# Give up if we are given two or more remotes -- not handling octopus.
+case "$remotes" in
+?*' '?*)
+	exit 2 ;;
+esac
+
+# Find an optimum merge base if there are more than one candidates.
+case "$bases" in
+?*' '?*)
+	echo "Trying to find the optimum merge base."
+	G=.tmp-index$$
+	best=
+	best_cnt=-1
+	for c in $bases
+	do
+		rm -f $G
+		GIT_INDEX_FILE=$G git read-tree -m $c $head $remotes \
+			 2>/dev/null ||	continue
+		# 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
+			if test "$best_cnt" -eq 0
+			then
+				# Cannot do any better than all trivial merge.
+				break
+			fi
+		fi
+	done
+	rm -f $G
+	common="$best"
+	;;
+*)
+	common="$bases"
+	;;
+esac
+
+git update-index --refresh 2>/dev/null
+git read-tree -u -m $common $head $remotes || exit 2
+echo "Trying simple merge."
+if result_tree=$(git write-tree  2>/dev/null)
+then
+	exit 0
+else
+	echo "Simple merge failed, trying Automatic merge."
+	if git-merge-index -o git-merge-one-file -a
+	then
+		exit 0
+	else
+		exit 1
+	fi
+fi
diff --git a/git-merge-stupid.sh b/git-merge-stupid.sh
deleted file mode 100755
index f612d47..0000000
--- a/git-merge-stupid.sh
+++ /dev/null
@@ -1,80 +0,0 @@
-#!/bin/sh
-#
-# Copyright (c) 2005 Linus Torvalds
-#
-# Resolve two trees, 'stupid merge'.
-
-# The first parameters up to -- are merge bases; the rest are heads.
-bases= head= remotes= sep_seen=
-for arg
-do
-	case ",$sep_seen,$head,$arg," in
-	*,--,)
-		sep_seen=yes
-		;;
-	,yes,,*)
-		head=$arg
-		;;
-	,yes,*)
-		remotes="$remotes$arg "
-		;;
-	*)
-		bases="$bases$arg "
-		;;
-	esac
-done
-
-# Give up if we are given two or more remotes -- not handling octopus.
-case "$remotes" in
-?*' '?*)
-	exit 2 ;;
-esac
-
-# Find an optimum merge base if there are more than one candidates.
-case "$bases" in
-?*' '?*)
-	echo "Trying to find the optimum merge base."
-	G=.tmp-index$$
-	best=
-	best_cnt=-1
-	for c in $bases
-	do
-		rm -f $G
-		GIT_INDEX_FILE=$G git read-tree -m $c $head $remotes \
-			 2>/dev/null ||	continue
-		# 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
-			if test "$best_cnt" -eq 0
-			then
-				# Cannot do any better than all trivial merge.
-				break
-			fi
-		fi
-	done
-	rm -f $G
-	common="$best"
-	;;
-*)
-	common="$bases"
-	;;
-esac
-
-git update-index --refresh 2>/dev/null
-git read-tree -u -m $common $head $remotes || exit 2
-echo "Trying simple merge."
-if result_tree=$(git write-tree  2>/dev/null)
-then
-	exit 0
-else
-	echo "Simple merge failed, trying Automatic merge."
-	if git-merge-index -o git-merge-one-file -a
-	then
-		exit 0
-	else
-		exit 1
-	fi
-fi
-- 
1.5.6.1.322.ge904b.dirty
Miklos Vajna· Jul 5, 2008, 21:00 UTC · re: Miklos Vajna · lore

[PATCH] Move 'stupid' merge strategy to contrib.

As pointed out by Linus, this strategy tries to take the best merge base, but 'recursive' just does it better. If one needs something more than 'resolve' then he/she should really use 'recursive' and not 'stupid'.

Given that it may still serve as a good example, don't remove it, just move it to contrib/examples. ---

n Sat, Jul 05, 2008 at 04:43:51PM +0200, Miklos Vajna <vmiklos@frugalware.org> wrote:
> Here is one.
Oops, I forgot -M with format-patch.
 .gitignore                                         |    1 -
 Makefile                                           |    3 +--
 .../examples/git-merge-stupid.sh                   |    0
 3 files changed, 1 insertions(+), 3 deletions(-)
 rename git-merge-stupid.sh => contrib/examples/git-merge-stupid.sh (100%)
diff --git a/.gitignore b/.gitignore
index 4ff2fec..8054d9d 100644
--- a/.gitignore
+++ b/.gitignore
@@ -75,7 +75,6 @@ git-merge-one-file
 git-merge-ours
 git-merge-recursive
 git-merge-resolve
-git-merge-stupid
 git-merge-subtree
 git-mergetool
 git-mktag
diff --git a/Makefile b/Makefile
index 78e08d3..bddd1a7 100644
--- a/Makefile
+++ b/Makefile
@@ -241,7 +241,6 @@ SCRIPT_SH += git-merge-octopus.sh
 SCRIPT_SH += git-merge-one-file.sh
 SCRIPT_SH += git-merge-resolve.sh
 SCRIPT_SH += git-merge.sh
-SCRIPT_SH += git-merge-stupid.sh
 SCRIPT_SH += git-mergetool.sh
 SCRIPT_SH += git-parse-remote.sh
 SCRIPT_SH += git-pull.sh
@@ -1429,7 +1428,7 @@ check-docs::
 	do \
 		case "$$v" in \
 		git-merge-octopus | git-merge-ours | git-merge-recursive | \
-		git-merge-resolve | git-merge-stupid | git-merge-subtree | \
+		git-merge-resolve | git-merge-subtree | \
 		git-fsck-objects | git-init-db | \
 		git-?*--?* ) continue ;; \
 		esac ; \
diff --git a/git-merge-stupid.sh b/contrib/examples/git-merge-stupid.sh
similarity index 100%
rename from git-merge-stupid.sh
rename to contrib/examples/git-merge-stupid.sh
-- 
1.5.6.1.322.ge904b.dirty

← back to recent threads