Question about git-merge-stupid

Question about git-merge-stupid

[Miklos Vajna]

[-- Attachment #1: Type: text/plain, Size: 1444 bytes --]

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. ]

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: Question about git-merge-stupid

[Linus Torvalds]

On Thu, 3 Jul 2008, Miklos Vajna wrote:
> 
> 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.

> $ 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

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

[Miklos Vajna]

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.

> 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

Re: Question about git-merge-stupid

[Junio C Hamano]

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.

Re: Question about git-merge-stupid

[Miklos Vajna]

[-- Attachment #1: Type: text/plain, Size: 310 bytes --]

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?

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

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

[Miklos Vajna]

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:
> 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

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

[Miklos Vajna]

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