[PATCH 1/1] Make sure the empty tree exists when needed in merge-recursive.

There are some baseless merge cases where git-merge-recursive will
try to compare one of the branches against the empty tree.  However
most projects won't have the empty tree object in their object database
as Git does not normally create empty tree objects.  If the empty tree
object is missing then the merge process will die, as it cannot load the
object from the database.  The error message may make the user think that
their database is corrupt when its actually not.

So instead we should just create the empty tree object whenever it is
needed.  If the object already exists as a loose object then no harm
done.  Otherwise that loose object will be pruned away later by either
git-prune or git-prune-packed.

Thanks goes to Junio for suggesting this fix.

Signed-off-by: Shawn O. Pearce <redacted>
---
 merge-recursive.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index cd2cc77..32e186c 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c

@@ -1238,7 +1238,7 @@ static int merge(struct commit *h1,
 
 		tree->object.parsed = 1;
 		tree->object.type = OBJ_TREE;
-		hash_sha1_file(NULL, 0, tree_type, tree->object.sha1);
+		write_sha1_file(NULL, 0, tree_type, tree->object.sha1);
 		merged_common_ancestors = make_virtual_commit(tree, "ancestor");
 	}
 

-- 

Hi,

On Sat, 9 Dec 2006, Junio C Hamano wrote:

I think this is overkill that only helps a very narrow "empty tree" 
special case that [PATCH 2/3] addresses, and can be easily and 
incorrectly abused.  We do not want people to expect that reading many 
trees from different revisions as "struct tree" objects and keeping all 
of them in memory would magically speed up diff-tree, for example.

I'd prefer write_sha1_file() approach in Shawn's patch for its 
simplicity at least for now.

Okay, after thinking about it, I agree. merge-recursive is really the only 
user for such a diff. So, I do not think EMPTY_TREE would be useful.

Ciao,
Dscho

Johannes Schindelin [off-list ref] writes:

If the tree has already been read, no need to read it into memory
again.

Hmm...

This also helps when this function is called on temporary trees;
these no longer have to be written to disk.

To generate tree-diff, probably yes, but I am not sure that
allows you to use hash_sha1_file() everywhere in merge_recursive
instead of write_sha1_file(), if that is what you are getting
at.

+static int get_tree_desc_from_sha1(const unsigned char *sha1,
+		struct tree_desc *t)
+{
+	struct object *o;
+
+	o = lookup_object(sha1);
+	if (o && o->type == OBJ_TREE && o->parsed) {
+		struct tree *tree = (struct tree *)o;
+		t->size = tree->size;
+		t->buf = xmalloc(t->size);
+		memcpy(t->buf, tree->buffer, t->size);
+	} else {
+		t->buf = read_object_with_reference(sha1,
+				tree_type, &t->size, NULL);
+		if (!t->buf)
+			die("unable to read source tree (%s)",
+					sha1_to_hex(sha1));
+	}
+}

Are you absolutely sure that all users of "struct tree" retains
the tree->buffer for a parsed tree?  If nobody does
"free(tree->buffer)" without "tree->buffer = NULL", then the
situation is still salvageable (you need a bit more code above),
though.

I think this is overkill that only helps a very narrow "empty
tree" special case that [PATCH 2/3] addresses, and can be easily
and incorrectly abused.  We do not want people to expect that
reading many trees from different revisions as "struct tree"
objects and keeping all of them in memory would magically speed
up diff-tree, for example.

I'd prefer write_sha1_file() approach in Shawn's patch for its
simplicity at least for now.

I suspect gitlink/subproject people might want to modify in-core
representation of a tree to graft in subproject directory
somewhere in the superproject, just like the history traversal
code modifies in-core representation of a commit to simplify
parents.  Your approach might turn out to be the right thing to
for that application --- populate tree objects in the in-core
obj_hash[], muck with its entries and then have everybody else
go through get_tree_desc_from_sha1() interface to pretend as if
the superproject has everything contained in the subproject
tree.  I dunno.

To use it in diff_tree_sha1(), a tree has to be hashed in the
global object collection. This actually moves the empty tree (if
it is needed) into the global object hash.

Signed-off-by: Johannes Schindelin <redacted>
---
 merge-recursive.c |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 6e13b8e..280f23c 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c

@@ -1220,9 +1220,10 @@ static int merge(struct commit *h1,
 		/* if there is no common ancestor, make an empty tree */
 		struct tree *tree = xcalloc(1, sizeof(struct tree));
 
+		hash_sha1_file(NULL, 0, tree_type, tree->object.sha1);
+		created_object(tree->object.sha1, &tree->object);
 		tree->object.parsed = 1;
 		tree->object.type = OBJ_TREE;
-		hash_sha1_file(NULL, 0, tree_type, tree->object.sha1);
 		merged_common_ancestors = make_virtual_commit(tree, "ancestor");
 	}
 

-- 
1.4.4.2.g0f32-dirty

Hi,

this test succeeds consistently on the machine where I tested it 
originally, but fails on another of my machines, but only when run without 
"-v". Very annoying. I will not have time to investigate until Monday, 
though.

Ciao,
Dscho

On Sun, 10 Dec 2006, Johannes Schindelin wrote:

To use it in diff_tree_sha1(), a tree has to be hashed in the
global object collection. This actually moves the empty tree (if
it is needed) into the global object hash.

I think you should do this more generically.

If we create this kind of "default fake object" that we know about whether 
the object _really_ exists or not (and I agree it makes sense for the 
empty tree), we should probably use it for "diff_root_tree_sha1()" too, 
rather than the special case we have now.

In other words, right now we have that very special 
"diff_root_tree_sha1()" function, but if you create a generic fake "empty 
tree" SHA1 that git knows about implicitly, we could entirely replace it 
with just using

	diff_tree_sha1(EMPTY_TREE_SHA1, tree, base, opt);

instead, and get rid of that special case code (which is efficient, but we 
don't really _need_ the efficiency).

So you could make "read_sha1_file()" just have a special case for known 
objects at the end. If the pack entry fails, the loose file case fails, 
then rather than returning NULL at the end, you could have a list of known 
fixed objects..

Hmm?

This test case is based on the bug report by Shawn Pearce.

Signed-off-by: Johannes Schindelin <redacted>
---
 t/t6024-recursive-merge.sh |   68 ++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 68 insertions(+), 0 deletions(-)

diff --git a/t/t6024-recursive-merge.sh b/t/t6024-recursive-merge.sh
new file mode 100644
index 0000000..5f821fb
--- /dev/null
+++ b/t/t6024-recursive-merge.sh

@@ -0,0 +1,68 @@
+#!/bin/sh
+
+test_description='Test merge without common ancestors'
+. ./test-lib.sh
+
+# This scenario is based on a real-world repository of Shawn Pearce.
+
+# 1 - A - D - F
+#   \   X   /
+#     B   X
+#       X   \
+# 2 - C - E - G
+
+echo 1 > a1
+git add a1
+git commit -m 1 a1
+
+git checkout -b A master
+echo A > a1
+git commit -m A a1
+
+git checkout -b B master
+echo B > a1
+git commit -m B a1
+
+git checkout -b D A
+git-rev-parse B > .git/MERGE_HEAD
+echo D > a1
+git update-index a1
+git commit -m D
+
+git symbolic-ref HEAD refs/heads/other
+echo 2 > a1
+git commit -m 2 a1
+
+git checkout -b C
+echo C > a1
+git commit -m C a1
+
+git checkout -b E C
+git-rev-parse B > .git/MERGE_HEAD
+echo E > a1
+git update-index a1
+git commit -m E
+
+git checkout -b G E
+git-rev-parse A > .git/MERGE_HEAD
+echo G > a1
+git update-index a1
+git commit -m G
+
+git checkout -b F D
+git-rev-parse C > .git/MERGE_HEAD
+echo F > a1
+git update-index a1
+git commit -m F
+
+test_expect_failure "combined merge conflicts" "git merge -m final G"
+
+git ls-files --stage > out
+cat > expect << EOF
+100644 cf84443e49e1b366fac938711ddf4be2d4d1d9e9 2	a1
+100644 fd7923529855d0b274795ae3349c5e0438333979 3	a1
+EOF
+
+test_expect_success "virtual trees were processed" "diff -u expect out"
+
+test_done

-- 
1.4.4.2.g0f32-dirty

If the tree has already been read, no need to read it into memory
again.

This also helps when this function is called on temporary trees;
these no longer have to be written to disk.

Signed-off-by: Johannes Schindelin <redacted>
---
 tree-diff.c |   33 ++++++++++++++++++++++-----------
 1 files changed, 22 insertions(+), 11 deletions(-)

diff --git a/tree-diff.c b/tree-diff.c
index 9d80dfb..54a6b44 100644
--- a/tree-diff.c
+++ b/tree-diff.c

@@ -195,23 +195,34 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2, const char *base, stru
 	return 0;
 }
 
+static int get_tree_desc_from_sha1(const unsigned char *sha1,
+		struct tree_desc *t)
+{
+	struct object *o;
+
+	o = lookup_object(sha1);
+	if (o && o->type == OBJ_TREE && o->parsed) {
+		struct tree *tree = (struct tree *)o;
+		t->size = tree->size;
+		t->buf = xmalloc(t->size);
+		memcpy(t->buf, tree->buffer, t->size);
+	} else {
+		t->buf = read_object_with_reference(sha1,
+				tree_type, &t->size, NULL);
+		if (!t->buf)
+			die("unable to read source tree (%s)",
+					sha1_to_hex(sha1));
+	}
+}
+
 int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)
 {
-	void *tree1, *tree2;
 	struct tree_desc t1, t2;
 	int retval;
 
-	tree1 = read_object_with_reference(old, tree_type, &t1.size, NULL);
-	if (!tree1)
-		die("unable to read source tree (%s)", sha1_to_hex(old));
-	tree2 = read_object_with_reference(new, tree_type, &t2.size, NULL);
-	if (!tree2)
-		die("unable to read destination tree (%s)", sha1_to_hex(new));
-	t1.buf = tree1;
-	t2.buf = tree2;
+	get_tree_desc_from_sha1(old, &t1);
+	get_tree_desc_from_sha1(new, &t2);
 	retval = diff_tree(&t1, &t2, base, opt);
-	free(tree1);
-	free(tree2);
 	return retval;
 }
 

-- 
1.4.4.2.g0f32-dirty