unpack-trees: fix D/F conflict bugs in verify_absent

I came across a few bugs while investigating the changes I proposed in the
modify/delete conflict thread. The first two are quite obvious. The third I'm
not so sure about. I could not find a testcase where it matters. Junio, do you
recall the original intention of that code?

[PATCH 1/3] unpack-trees: handle failure in verify_absent
[PATCH 2/3] unpack-trees: fix path search bug in verify_absent
[PATCH 3/3] unpack-trees: remove redundant path search in verify_absent

 t/t1001-read-tree-m-2way.sh |   51 +++++++++++++++++++++++++++++++++++++++++++
 unpack-trees.c              |   37 +++++++++++++++----------------
 2 files changed, 69 insertions(+), 19 deletions(-)

Commit 0cf73755 (unpack-trees.c: assume submodules are clean during
check-out) changed an argument to verify_absent from 'path' to 'ce',
which is however shadowed by a local variable of the same name.

The bug triggers if verify_absent is used on a tree entry, for which
the index contains one or more subsequent directories of the same
length. The affected subdirectories are removed from the index. The
testcase included in this commit bisects to 55218834 (checkout: do not
lose staged removal), which reveals the bug in this case, but is
otherwise unrelated.
---
 t/t1001-read-tree-m-2way.sh |   27 +++++++++++++++++++++++++++
 unpack-trees.c              |   23 ++++++++++++-----------
 2 files changed, 39 insertions(+), 11 deletions(-)

diff --git a/t/t1001-read-tree-m-2way.sh b/t/t1001-read-tree-m-2way.sh
index 7f6ab31..271bc4e 100755
--- a/t/t1001-read-tree-m-2way.sh
+++ b/t/t1001-read-tree-m-2way.sh

@@ -365,4 +365,31 @@ test_expect_success \
      git ls-files --stage &&
      test -f a/b'
 
+test_expect_success \
+    'a/b vs a, plus c/d case setup.' \
+    'rm -f .git/index &&
+     rm -fr a &&
+     : >a &&
+     mkdir c &&
+     : >c/d &&
+     git update-index --add a c/d &&
+     treeM=`git write-tree` &&
+     echo treeM $treeM &&
+     git ls-tree $treeM &&
+     git ls-files --stage >treeM.out &&
+
+     rm -f a &&
+     mkdir a
+     : >a/b &&
+     git update-index --add --remove a a/b &&
+     treeH=`git write-tree` &&
+     echo treeH $treeH &&
+     git ls-tree $treeH'
+
+test_expect_success \
+    'a/b vs a, plus c/d case test.' \
+    'git read-tree -u -m "$treeH" "$treeM" &&
+     git ls-files --stage | tee >treeMcheck.out &&
+     test_cmp treeM.out treeMcheck.out'
+
 test_done

diff --git a/unpack-trees.c b/unpack-trees.c
index a736947..f8e2484 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c

@@ -289,7 +289,8 @@ static int unpack_nondirectories(int n, unsigned long mask, unsigned long dirmas
 	return 0;
 }
 
-static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)
+static int unpack_callback(int n, unsigned long mask, unsigned long dirmask,
+		struct name_entry *names, struct traverse_info *info)
 {
 	struct cache_entry *src[5] = { NULL, };
 	struct unpack_trees_options *o = info->data;

@@ -517,22 +518,22 @@ static int verify_clean_subdirectory(struct cache_entry *ce, const char *action,
 	namelen = strlen(ce->name);
 	pos = index_name_pos(o->src_index, ce->name, namelen);
 	if (0 <= pos)
-		return cnt; /* we have it as nondirectory */
+		return 0; /* we have it as nondirectory */
 	pos = -pos - 1;
 	for (i = pos; i < o->src_index->cache_nr; i++) {
-		struct cache_entry *ce = o->src_index->cache[i];
-		int len = ce_namelen(ce);
+		struct cache_entry *ce2 = o->src_index->cache[i];
+		int len = ce_namelen(ce2);
 		if (len < namelen ||
-		    strncmp(ce->name, ce->name, namelen) ||
-		    ce->name[namelen] != '/')
+		    strncmp(ce->name, ce2->name, namelen) ||
+		    ce2->name[namelen] != '/')
 			break;
 		/*
-		 * ce->name is an entry in the subdirectory.
+		 * ce2->name is an entry in the subdirectory.
 		 */
-		if (!ce_stage(ce)) {
-			if (verify_uptodate(ce, o))
+		if (!ce_stage(ce2)) {
+			if (verify_uptodate(ce2, o))
 				return -1;
-			add_entry(o, ce, CE_REMOVE, 0);
+			add_entry(o, ce2, CE_REMOVE, 0);
 		}
 		cnt++;
 	}

@@ -624,7 +625,7 @@ static int verify_absent(struct cache_entry *ce, const char *action,
 			 * If this removed entries from the index,
 			 * what that means is:
 			 *
-			 * (1) the caller unpack_trees_rec() saw path/foo
+			 * (1) the caller unpack_callback() saw path/foo
 			 * in the index, and it has not removed it because
 			 * it thinks it is handling 'path' as blob with
 			 * D/F conflict;

-- 
1.6.1

Commit 203a2fe1 (Allow callers of unpack_trees() to handle failure)
changed the "die on error" behavior to "return failure code".
verify_absent did not handle errors returned by
verify_clean_subdirectory, however.
---
 t/t1001-read-tree-m-2way.sh |   24 ++++++++++++++++++++++++
 unpack-trees.c              |    8 +++++---
 2 files changed, 29 insertions(+), 3 deletions(-)

diff --git a/t/t1001-read-tree-m-2way.sh b/t/t1001-read-tree-m-2way.sh
index 4b44e13..7f6ab31 100755
--- a/t/t1001-read-tree-m-2way.sh
+++ b/t/t1001-read-tree-m-2way.sh

@@ -341,4 +341,28 @@ test_expect_success \
      check_cache_at DF/DF dirty &&
      :'
 
+test_expect_success \
+    'a/b (untracked) vs a case setup.' \
+    'rm -f .git/index &&
+     : >a &&
+     git update-index --add a &&
+     treeM=`git write-tree` &&
+     echo treeM $treeM &&
+     git ls-tree $treeM &&
+     git ls-files --stage >treeM.out &&
+
+     rm -f a &&
+     git update-index --remove a &&
+     mkdir a &&
+     : >a/b &&
+     treeH=`git write-tree` &&
+     echo treeH $treeH &&
+     git ls-tree $treeH'
+
+test_expect_success \
+    'a/b (untracked) vs a, plus c/d case test.' \
+    '! git read-tree -u -m "$treeH" "$treeM" &&
+     git ls-files --stage &&
+     test -f a/b'
+
 test_done

diff --git a/unpack-trees.c b/unpack-trees.c
index 54f301d..a736947 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c

@@ -588,7 +588,7 @@ static int verify_absent(struct cache_entry *ce, const char *action,
 		return 0;
 
 	if (!lstat(ce->name, &st)) {
-		int cnt;
+		int ret;
 		int dtype = ce_to_dtype(ce);
 		struct cache_entry *result;
 

@@ -616,7 +616,9 @@ static int verify_absent(struct cache_entry *ce, const char *action,
 			 * files that are in "foo/" we would lose
 			 * it.
 			 */
-			cnt = verify_clean_subdirectory(ce, action, o);
+			ret = verify_clean_subdirectory(ce, action, o);
+			if (ret < 0)
+				return ret;
 
 			/*
 			 * If this removed entries from the index,

@@ -635,7 +637,7 @@ static int verify_absent(struct cache_entry *ce, const char *action,
 			 * We need to increment it by the number of
 			 * deleted entries here.
 			 */
-			o->pos += cnt;
+			o->pos += ret;
 			return 0;
 		}
 

-- 
1.6.1

Since the only caller, verify_absent, relies on the fact that o->pos
points to the next index entry anyways, there is no need to recompute
its position.

Furthermore, if a nondirectory entry were found, this would return too
early, because there could still be an untracked directory in the way.
This is currently not a problem, because verify_absent is only called
if the index does not have this entry.
---
 unpack-trees.c |    8 ++------
 1 files changed, 2 insertions(+), 6 deletions(-)

diff --git a/unpack-trees.c b/unpack-trees.c
index f8e2484..c4dc6dc 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c

@@ -495,7 +495,7 @@ static int verify_clean_subdirectory(struct cache_entry *ce, const char *action,
 	 * anything in the existing directory there.
 	 */
 	int namelen;
-	int pos, i;
+	int i;
 	struct dir_struct d;
 	char *pathbuf;
 	int cnt = 0;

@@ -516,11 +516,7 @@ static int verify_clean_subdirectory(struct cache_entry *ce, const char *action,
 	 * in that directory.
 	 */
 	namelen = strlen(ce->name);
-	pos = index_name_pos(o->src_index, ce->name, namelen);
-	if (0 <= pos)
-		return 0; /* we have it as nondirectory */
-	pos = -pos - 1;
-	for (i = pos; i < o->src_index->cache_nr; i++) {
+	for (i = o->pos; i < o->src_index->cache_nr; i++) {
 		struct cache_entry *ce2 = o->src_index->cache[i];
 		int len = ce_namelen(ce2);
 		if (len < namelen ||

-- 
1.6.1

On Thu, 1 Jan 2009, Clemens Buchacher wrote:

Commit 0cf73755 (unpack-trees.c: assume submodules are clean during
check-out) changed an argument to verify_absent from 'path' to 'ce',
which is however shadowed by a local variable of the same name.

The bug triggers if verify_absent is used on a tree entry, for which
the index contains one or more subsequent directories of the same
length. The affected subdirectories are removed from the index. The
testcase included in this commit bisects to 55218834 (checkout: do not
lose staged removal), which reveals the bug in this case, but is
otherwise unrelated.
---

Sign-off?

Just for the record, this patch fixes the testcase Miklos reported 
earlier.

Ciao,
Dscho

Hi,

On Thu, 1 Jan 2009, Clemens Buchacher wrote:

Commit 0cf73755 (unpack-trees.c: assume submodules are clean during
check-out) changed an argument to verify_absent from 'path' to 'ce',
which is however shadowed by a local variable of the same name.

This explanation makes sense.  However, this:

... is distracting during review, and this:

... is not accounted for in the commit message.  Intended or not, that is 
the question.

Ciao,
Dscho "whether 'tis noble"

On Fri, Jan 02, 2009 at 10:59:47PM +0100, Johannes Schindelin wrote:

This explanation makes sense.  However, this:

quoted

@@ -289,7 +289,8 @@ static int unpack_nondirectories(int n, unsigned long mask, unsigned long dirmas
 	return 0;
 }
 
-static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)
+static int unpack_callback(int n, unsigned long mask, unsigned long dirmask,
+		struct name_entry *names, struct traverse_info *info)
 {
 	struct cache_entry *src[5] = { NULL, };
 	struct unpack_trees_options *o = info->data;

... is distracting during review, and this:

quoted

@@ -517,22 +518,22 @@ static int verify_clean_subdirectory(struct cache_entry *ce, const char *action,
 	namelen = strlen(ce->name);
 	pos = index_name_pos(o->src_index, ce->name, namelen);
 	if (0 <= pos)
-		return cnt; /* we have it as nondirectory */
+		return 0; /* we have it as nondirectory */
 	pos = -pos - 1;
 	for (i = pos; i < o->src_index->cache_nr; i++) {

... is not accounted for in the commit message.  Intended or not, that is 
the question.

Those are trivial readability improvements in the context of the patch.

On Fri, Jan 02, 2009 at 10:59:43PM +0100, Johannes Schindelin wrote:

Sign-off?

Signed-off-by: Clemens Buchacher <redacted>

on all three patches.

Hi,

On Sat, 3 Jan 2009, Clemens Buchacher wrote:

On Fri, Jan 02, 2009 at 10:59:47PM +0100, Johannes Schindelin wrote:

quoted

This explanation makes sense.  However, this:

quoted

@@ -289,7 +289,8 @@ static int unpack_nondirectories(int n, unsigned long mask, unsigned long dirmas
 	return 0;
 }
 
-static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)
+static int unpack_callback(int n, unsigned long mask, unsigned long dirmask,
+		struct name_entry *names, struct traverse_info *info)
 {
 	struct cache_entry *src[5] = { NULL, };
 	struct unpack_trees_options *o = info->data;

... is distracting during review, and this:

quoted

@@ -517,22 +518,22 @@ static int verify_clean_subdirectory(struct cache_entry *ce, const char *action,
 	namelen = strlen(ce->name);
 	pos = index_name_pos(o->src_index, ce->name, namelen);
 	if (0 <= pos)
-		return cnt; /* we have it as nondirectory */
+		return 0; /* we have it as nondirectory */
 	pos = -pos - 1;
 	for (i = pos; i < o->src_index->cache_nr; i++) {

... is not accounted for in the commit message.  Intended or not, that is 
the question.

Those are trivial readability improvements in the context of the patch.

They are not trivial enough for me not to be puzzled.  Reason enough to 
explain in the commit message?

Ciao,
Dscho

On Fri, Jan 02, 2009 at 10:59:43PM +0100, Johannes Schindelin [off-list ref] wrote:

Just for the record, this patch fixes the testcase Miklos reported 
earlier.

Indeed, thanks for the notice.

Johannes Schindelin [off-list ref] writes:

On Sat, 3 Jan 2009, Clemens Buchacher wrote:

quoted

On Fri, Jan 02, 2009 at 10:59:47PM +0100, Johannes Schindelin wrote:

quoted

This explanation makes sense.  However, this:

quoted

@@ -289,7 +289,8 @@ static int unpack_nondirectories(int n, unsigned long mask, unsigned long dirmas
 	return 0;
 }
 
-static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)
+static int unpack_callback(int n, unsigned long mask, unsigned long dirmask,
+		struct name_entry *names, struct traverse_info *info)
 {
 	struct cache_entry *src[5] = { NULL, };
 	struct unpack_trees_options *o = info->data;

... is distracting during review, and this:

quoted

@@ -517,22 +518,22 @@ static int verify_clean_subdirectory(struct cache_entry *ce, const char *action,
 	namelen = strlen(ce->name);
 	pos = index_name_pos(o->src_index, ce->name, namelen);
 	if (0 <= pos)
-		return cnt; /* we have it as nondirectory */
+		return 0; /* we have it as nondirectory */
 	pos = -pos - 1;
 	for (i = pos; i < o->src_index->cache_nr; i++) {

... is not accounted for in the commit message.  Intended or not, that is 
the question.

Those are trivial readability improvements in the context of the patch.

They are not trivial enough for me not to be puzzled.  Reason enough to 
explain in the commit message?

I'd say the first hunk quoted is probably on the borderline.  It is an
unnecessary churn that won't even be commented on if it were sent alone,
but as a "while we are at it" hunk in a patch that is not too big, this is
a kind of thing that often is tolerated, because it is obvious enough not
to hurt anything from the correctness standpoint [*1*].

The second one is moderately worse for two reasons.

 * I actually had to scratch my head because you need to view the change
   in a lot wider context that covers the initializing definition of "int
   cnt" near the beginning of the function down to the area affected by
   the hunk, in order to see that the new "return 0" is the same as the
   old "return cnt" and does not break things.  A comment to say that "at
   this point in the codeflow, cnt which is returned by the old code is
   always zero", perhaps below the three-dash marker, would have saved me
   a minute.

 * The function's purpose and logic is to see if the subdirectory is
   clean, and return how many cache entries need to be skipped if it is
   (otherwise a negative number as an error indicator).  For that purpose,
   the return value cnt is initialized to 0 (i.e. "we haven't counted any
   entry that needs to be skipped yet"), the loop below the patched part
   counts it up while performing the verification, and then the resulting
   count is returned from the function.  The logic flow, at least to me,
   is easier to follow if it returned the value in cnt, not a hardcoded 0,
   from the place the patch tries to touch.

The latter point is with "at least to me", because I think an alternate
position is entirely valid if the author wants to justify the change by
saying something like:

    The function's purpose is ....  Before entering the loop to count the
    number of entries to skip, this check to detect if we do not even have
    to count appears.  When this check triggers, we know we do not want to
    skip anything, and returning constant 0 is much clearer than returning
    a variable cnt that was initialized to 0 near the beginning of the
    function; we haven't even started using it to count yet.

But the point is, if that is the reason the author thinks it is an
improvement, that probably needs to be stated.

[Footnote]

*1* I am not sure if it is obviously clear that the change improves any
readability.  Some people argue that splitting the function definition
header hurts greppability for one thing.  I personally do not find it easy
to read when the subsequent header lines are indented without aligning
(compare the way it is indented in the postimage of the patch with the way
the headers verify_absent() and show_stage_entry() are indented), either.

Hi,

On Sun, Jan 04, 2009 at 02:01:14AM -0800, Junio C Hamano wrote:

    The function's purpose is ....  Before entering the loop to count the
    number of entries to skip, this check to detect if we do not even have
    to count appears.  When this check triggers, we know we do not want to
    skip anything, and returning constant 0 is much clearer than returning
    a variable cnt that was initialized to 0 near the beginning of the
    function; we haven't even started using it to count yet.

But the point is, if that is the reason the author thinks it is an
improvement, that probably needs to be stated.

If you want to check the validity of the patch you have to view it in
context anyways. Compared to understanding the change to the code, it takes
much longer to parse and understand the above paragraph _plus_ verify its
agreement with the code. I think you will agree that there is a limit to the
amount of documentation that's still useful.

My estimate of this limit is apparently much lower than what is expected by
the main contributors to this project. I respect that and I will try not to
waste your time any further.

What's sad, however, is that we are now discussing style and commenting
issues of a line of code, which, as by my analysis of [PATCH 3/3] never
actually gets executed in the first place. I would have been much more
curious about your comments on that.

Best regards,
Clemens

Clemens Buchacher [off-list ref] writes:

Since the only caller, verify_absent, relies on the fact that o->pos
points to the next index entry anyways, there is no need to recompute
its position.

I suspect that the original reasoning of this behaviour might have been in
anticipation of other callers, but I agree with your reasoning especially
because I do not think of a good reason to want to receive the number of
entries to skip as the return value and not have o->pos pointing at the
right place.

Thanks, queued.

Hi,

On Sun, 4 Jan 2009, Clemens Buchacher wrote:

On Sun, Jan 04, 2009 at 02:01:14AM -0800, Junio C Hamano wrote:

quoted

    The function's purpose is ....  Before entering the loop to count 
    the number of entries to skip, this check to detect if we do not 
    even have to count appears.  When this check triggers, we know we 
    do not want to skip anything, and returning constant 0 is much 
    clearer than returning a variable cnt that was initialized to 0 
    near the beginning of the function; we haven't even started using 
    it to count yet.

But the point is, if that is the reason the author thinks it is an 
improvement, that probably needs to be stated.

If you want to check the validity of the patch you have to view it in
context anyways.

Umm.

You can make reviewing your patch attractive and easy, and you can make it 
unattractive and difficult.

If you explain in the commit message that you replaced "cnt" by "0" 
because it is initialized to 0 at that point anyway, it is a _much bigger_ 
pleasure to review your patch.

Let alone a much bigger pleasure for you, 6 months from now, when somebody 
says "why does this silly function return 0, when it should return cnt?"

BTW exactly for that reason, I'd like to leave it as "cnt".  Because code 
_will_ change, and it's quite possible that cnt will not be 0 at that 
point in the future.

Compared to understanding the change to the code, it takes much longer 
to parse and understand the above paragraph _plus_ verify its agreement 
with the code. I think you will agree that there is a limit to the 
amount of documentation that's still useful.

Just look at a concrete case: me.  I saw that part of the patch, even 
before coming to the real meat of it.  And that head-scratching already 
removed all the enthusiasm I had to look at unpack-trees.c again, so you 
lost a reviewer.

What's sad, however, is that we are now discussing style and commenting 
issues of a line of code, which, as by my analysis of [PATCH 3/3] never 
actually gets executed in the first place. I would have been much more 
curious about your comments on that.

Exactly,
Dscho

Here are two cases where we ignore the result from lstat in
unpack_trees.  I think we rather shouldn't ignore it.  Sane?

Jonathan Nieder (2):
  unpack-trees: handle lstat failure for existing directory
  unpack-trees: handle lstat failure for existing file

 unpack-trees.c |    8 ++++++--
 1 files changed, 6 insertions(+), 2 deletions(-)

When check_leading_path notices no file in the way of the new entry to
be checked out, verify_absent checks whether there is a directory
there or nothing at all.  If that lstat call fails (for example due to
ENOMEM), it assumes ENOENT, meaning a directory with untracked files
would be clobbered in that case.

Check errno after calling lstat, and for conditions other than ENOENT,
just error out.

This is a theoretical race condition.  lstat has to succeed moments
before it fails for there to be trouble.

Signed-off-by: Jonathan Nieder <redacted>
---
Does this need an o->gently check?

 unpack-trees.c |    4 +++-
 1 files changed, 3 insertions(+), 1 deletions(-)

diff --git a/unpack-trees.c b/unpack-trees.c
index 1ca41b1..a795db5 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c

@@ -1382,7 +1382,9 @@ static int verify_absent_1(struct cache_entry *ce,
 		return check_ok_to_remove(ce->name, ce_namelen(ce),
 				ce_to_dtype(ce), ce, &st,
 				error_type, o);
-
+	if (errno != ENOENT)
+		return error("cannot stat '%s': %s", ce->name,
+				strerror(errno));
 	return 0;
 }
 

-- 
1.7.4.rc1

When check_leading_path notices a file in the way of a new entry to be
checked out, verify_absent uses (1) the mode to determine whether it
is a directory (2) the rest of the stat information to check if this
is actually an old entry, disguised by a change in filename (e.g.,
README -> Readme) that is significant to git but insignificant to the
underlying filesystem.  If lstat fails, these checks are performed
with an uninitialied stat structure, producing essentially random
results.

Better to just error out when lstat fails.

The easiest way to reproduce this is to remove a file after the
check_leading_path call and before the lstat in verify_absent.  An
lstat failure other than ENOENT in check_leading_path would also
trigger the same code path.

Signed-off-by: Jonathan Nieder <redacted>
---
 unpack-trees.c |    4 +++-
 1 files changed, 3 insertions(+), 1 deletions(-)

diff --git a/unpack-trees.c b/unpack-trees.c
index a795db5..9c3fe64 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c

@@ -1374,7 +1374,9 @@ static int verify_absent_1(struct cache_entry *ce,
 		char path[PATH_MAX + 1];
 		memcpy(path, ce->name, len);
 		path[len] = 0;
-		lstat(path, &st);
+		if (lstat(path, &st))
+			return error("cannot stat '%s': %s", path,
+					strerror(errno));
 
 		return check_ok_to_remove(path, len, DT_UNKNOWN, NULL, &st,
 				error_type, o);

-- 
1.7.4.rc1

On Wed, Jan 12, 2011 at 08:24:15PM -0600, Jonathan Nieder wrote:

Here are two cases where we ignore the result from lstat in
unpack_trees.  I think we rather shouldn't ignore it.  Sane?

Looks good. Thanks.

But in addition to the ones you fixed, lstat errors returned by
lstat_cache_matchlen() in check_leading_path() are also ignored.
I was actually hoping to restructure this into two functions.

 1) check_path() to see if we need to overwrite anything (leading
    directory _or_ file of the same name)
 2) check_ok_to_remove() to check if we can safely overwrite that
    directory or file

All the lstat handling would go into check_path(), and
check_ok_to_remove() can reuse the stat returned by check_path().

But right now I can't say when I will find the time.

Clemens