Bug: write-tree corrupts intent-to-add index state

Hi revisionaries,

I came across what appears to be a bug while working today. I had several changes, both staged and unstaged, and two files that I had marked with intent-to-add (git add -N).

$ git status -sb
## Library-3.x...origin/Library-3.x [ahead 4]
M  Library/LIRootSource.m
 M Library/Library.xcodeproj/project.pbxproj
[...]
 M Library/SceneKit/LISceneKitBookshelfScene.m
AM Library/SceneKit/LISceneKitDisplayedMediumProxy.h
AM Library/SceneKit/LISceneKitDisplayedMediumProxy.m

(The last two files were added with -N.) I then attempted to stash my work, but that failed:

$ git stash -k
error: Entry 'Library/SceneKit/LISceneKitDisplayedMediumProxy.h' not uptodate. Cannot merge.
Cannot save the current worktree state

Re-checking the status showed that the intent-to-add files were now simply modified, yet they did not appear in git ls-tree -r HEAD.

$ git status -sb
## Library-3.x...origin/Library-3.x [ahead 4]
M  Library/LIRootSource.m
 M Library/Library.xcodeproj/project.pbxproj
[...]
 M Library/SceneKit/LISceneKitBookshelfScene.m
 M Library/SceneKit/LISceneKitDisplayedMediumProxy.h
 M Library/SceneKit/LISceneKitDisplayedMediumProxy.m

It appears the index forgot that those files were new. So not only has the intent-to-add status been lost, but git status shows a file existing in neither HEAD nor the index as not-new-but-modified.

Tracing through it, I narrowed it down to git write-tree affecting the index state. As far as I can tell, it's incorrect for that command to change the index. I'm now out of my (shallow) depth in the git codebase, so I'm throwing it out there for someone to tackle (hopefully). I've attached a failing test case.

Additional notes for bug hunters:

- I've only seen files in already-existing subdirectories lose intent-to-add status, whereas marking a file in the top-level as i-t-a is preserved during write-tree.

- The 'git ls-files -s --debug' output doesn't change across the write-tree:

100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 0	dir/baz
  ctime: 0:0
  mtime: 0:0
  dev: 0	ino: 0
  uid: 0	gid: 0
  size: 0	flags: 20004000


---
 t/t2203-add-intent.sh | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)

diff --git a/t/t2203-add-intent.sh b/t/t2203-add-intent.sh
index ec35409..fcc67c0 100755
--- a/t/t2203-add-intent.sh
+++ b/t/t2203-add-intent.sh

@@ -62,5 +62,27 @@ test_expect_success 'can "commit -a" with an i-t-a entry' '
 	git commit -a -m all
 '
 
+test_expect_success 'i-t-a status unaffected by write-tree' '
+	git reset --hard &&
+	mkdir dir &&
+	echo frotz >dir/bar &&
+	git add dir &&
+	git commit -m "establish dir" &&
+	echo fizfaz >foo &&
+	echo fragz >dir/baz &&
+	git add rezrov &&
+	git add -N foo &&
+	git add -N dir/baz &&
+	cat >expect <<-\EOF &&
+	AM dir/baz
+	AM foo
+	EOF
+	git status --untracked-files=no --porcelain >actual &&
+	test_cmp actual expect &&
+	git write-tree &&
+	git status --untracked-files=no --porcelain >actual &&
+	test_cmp actual expect
+'
+
 test_done
 

-- 
1.8.0



Jonathon Mah
me@JonathonMah.com

On Tue, Nov 06, 2012 at 12:53:27AM -0800, Jonathon Mah wrote:

It appears the index forgot that those files were new. So not only
has the intent-to-add status been lost, but git status shows a file
 existing in neither HEAD nor the index as not-new-but-modified.

Tracing through it, I narrowed it down to git write-tree affecting
the index state. As far as I can tell, it's incorrect for that
command to change the index. I'm now out of my (shallow) depth in
the git codebase, so I'm throwing it out there for someone to tackle
(hopefully). I've attached a failing test case.

I played with your test a bit and found that if we skip the commit
step, the bug disappears. I checked and believe that i-t-a flag in
index is preserved, which leaves cache-tree as the culprit. If
cache-tree is (incorrectly) valid, diff operations won't bother
checking index.

We used to not allow writing tree with i-t-a entries present. Then we
allowed it, but forgot that we need to invalidate any paths that
contain i-t-a entries, otherwise cache-tree won't truly reflect
index.

The below patch seems to do the trick, but I'd rather do the
invalidation inside update_one() so we don't need to traverse over the
index again. I haven't succesfully put cache-tree.c back in my head
again to make it happen. Anybody is welcome to step up, or I'll finish
it this weekend.

-- 8< --

diff --git a/cache-tree.c b/cache-tree.c
index 28ed657..30a8018 100644
--- a/cache-tree.c
+++ b/cache-tree.c

@@ -381,6 +381,9 @@ int cache_tree_update(struct cache_tree *it,
 	i = update_one(it, cache, entries, "", 0, flags);
 	if (i < 0)
 		return i;
+	for (i = 0; i < entries; i++)
+		if (cache[i]->ce_flags & CE_INTENT_TO_ADD)
+			cache_tree_invalidate_path(it, cache[i]->name);
 	return 0;
 }
 

diff --git a/t/t2203-add-intent.sh b/t/t2203-add-intent.sh
index ec35409..3ddbd89 100755
--- a/t/t2203-add-intent.sh
+++ b/t/t2203-add-intent.sh

@@ -62,5 +62,25 @@ test_expect_success 'can "commit -a" with an i-t-a entry' '
 	git commit -a -m all
 '
 
+test_expect_success 'cache-tree invalidates i-t-a paths' '
+	git reset --hard &&
+	mkdir dir &&
+	: >dir/foo &&
+	git add dir/foo &&
+	git commit -m foo &&
+
+	: >dir/bar &&
+	git add -N dir/bar &&
+	git diff --cached --name-only >actual &&
+	echo dir/bar >expect &&
+	test_cmp expect actual &&
+
+	git write-tree >/dev/null &&
+
+	git diff --cached --name-only >actual &&
+	echo dir/bar >expect &&
+	test_cmp expect actual
+'
+
 test_done
-- 8< -- 

Intent-to-add entries used to forbid writing trees so it was not a
problem. After commit 3f6d56d (commit: ignore intent-to-add entries
instead of refusing - 2012-02-07), an index with i-t-a entries can
write trees. However, the commit forgets to invalidate all paths
leading to i-t-a entries. With fully valid cache-tree (e.g. after
commit or write-tree), diff operations may prefer cache-tree to index
and not see i-t-a entries in the index, because cache-tree does not
have them.

The invalidation is done after calling update_one() in
cache_tree_update() for simplicity because it's probably not worth the
complexity of changing a recursive function and the performance
bottleneck won't likely fall to this new loop, rather in
write_sha1_file or hash_sha1_file. But this means that if update_one()
has new call sites, they must re-do the same what this commit does to
avoid the same fault.

Reported-by: Jonathon Mah <redacted>
Signed-off-by: Nguyễn Thái Ngọc Duy <redacted>
---
 cache-tree.c          |  3 +++
 t/t2203-add-intent.sh | 20 ++++++++++++++++++++
 2 files changed, 23 insertions(+)

diff --git a/cache-tree.c b/cache-tree.c
index 28ed657..30a8018 100644
--- a/cache-tree.c
+++ b/cache-tree.c

@@ -381,6 +381,9 @@ int cache_tree_update(struct cache_tree *it,
 	i = update_one(it, cache, entries, "", 0, flags);
 	if (i < 0)
 		return i;
+	for (i = 0; i < entries; i++)
+		if (cache[i]->ce_flags & CE_INTENT_TO_ADD)
+			cache_tree_invalidate_path(it, cache[i]->name);
 	return 0;
 }
 

diff --git a/t/t2203-add-intent.sh b/t/t2203-add-intent.sh
index ec35409..2a4a749 100755
--- a/t/t2203-add-intent.sh
+++ b/t/t2203-add-intent.sh

@@ -62,5 +62,25 @@ test_expect_success 'can "commit -a" with an i-t-a entry' '
 	git commit -a -m all
 '
 
+test_expect_success 'cache-tree invalidates i-t-a paths' '
+	git reset --hard &&
+	mkdir dir &&
+	: >dir/foo &&
+	git add dir/foo &&
+	git commit -m foo &&
+
+	: >dir/bar &&
+	git add -N dir/bar &&
+	git diff --cached --name-only >actual &&
+	echo dir/bar >expect &&
+	test_cmp expect actual &&
+
+	git write-tree >/dev/null &&
+
+	git diff --cached --name-only >actual &&
+	echo dir/bar >expect &&
+	test_cmp expect actual
+'
+
 test_done
 

-- 
1.8.0.rc2.23.g1fb49df

Intent-to-add entries used to forbid writing trees so it was not a
problem. After commit 3f6d56d (commit: ignore intent-to-add entries
instead of refusing - 2012-02-07), we can generate trees from an index
with i-t-a entries.

However, the commit forgets to invalidate all paths leading to i-t-a
entries. With fully valid cache-tree (e.g. after commit or
write-tree), diff operations may prefer cache-tree to index and not
see i-t-a entries in the index, because cache-tree does not have them.

Reported-by: Jonathon Mah <redacted>
Signed-off-by: Nguyễn Thái Ngọc Duy <redacted>
---
 Sorry for the late update, I have little time for git these days.
 It turns out that we don't need phony bit and another round for
 invalidation. We can do it in update_one.

 cache-tree.c          | 30 ++++++++++++++++++++++++++----
 t/t2203-add-intent.sh | 20 ++++++++++++++++++++
 2 files changed, 46 insertions(+), 4 deletions(-)

diff --git a/cache-tree.c b/cache-tree.c
index 28ed657..989a7ff 100644
--- a/cache-tree.c
+++ b/cache-tree.c

@@ -248,6 +248,7 @@ static int update_one(struct cache_tree *it,
 	int missing_ok = flags & WRITE_TREE_MISSING_OK;
 	int dryrun = flags & WRITE_TREE_DRY_RUN;
 	int i;
+	int to_invalidate = 0;
 
 	if (0 <= it->entry_count && has_sha1_file(it->sha1))
 		return it->entry_count;

@@ -324,7 +325,13 @@ static int update_one(struct cache_tree *it,
 			if (!sub)
 				die("cache-tree.c: '%.*s' in '%s' not found",
 				    entlen, path + baselen, path);
-			i += sub->cache_tree->entry_count - 1;
+			i--; /* this entry is already counted in "sub" */
+			if (sub->cache_tree->entry_count < 0) {
+				i -= sub->cache_tree->entry_count;
+				to_invalidate = 1;
+			}
+			else
+				i += sub->cache_tree->entry_count;
 			sha1 = sub->cache_tree->sha1;
 			mode = S_IFDIR;
 		}

@@ -339,8 +346,23 @@ static int update_one(struct cache_tree *it,
 				mode, sha1_to_hex(sha1), entlen+baselen, path);
 		}
 
-		if (ce->ce_flags & (CE_REMOVE | CE_INTENT_TO_ADD))
-			continue; /* entry being removed or placeholder */
+		/*
+		 * CE_REMOVE entries are removed before the index is
+		 * written to disk. Skip them to remain consistent
+		 * with the future on-disk index.
+		 */
+		if (ce->ce_flags & CE_REMOVE)
+			continue;
+
+		/*
+		 * CE_INTENT_TO_ADD entries exist on on-disk index but
+		 * they are not part of generated trees. Invalidate up
+		 * to root to force cache-tree users to read elsewhere.
+		 */
+		if (ce->ce_flags & CE_INTENT_TO_ADD) {
+			to_invalidate = 1;
+			continue;
+		}
 
 		strbuf_grow(&buffer, entlen + 100);
 		strbuf_addf(&buffer, "%o %.*s%c", mode, entlen, path + baselen, '\0');

@@ -360,7 +382,7 @@ static int update_one(struct cache_tree *it,
 	}
 
 	strbuf_release(&buffer);
-	it->entry_count = i;
+	it->entry_count = to_invalidate ? -i : i;
 #if DEBUG
 	fprintf(stderr, "cache-tree update-one (%d ent, %d subtree) %s\n",
 		it->entry_count, it->subtree_nr,

diff --git a/t/t2203-add-intent.sh b/t/t2203-add-intent.sh
index ec35409..2a4a749 100755
--- a/t/t2203-add-intent.sh
+++ b/t/t2203-add-intent.sh

@@ -62,5 +62,25 @@ test_expect_success 'can "commit -a" with an i-t-a entry' '
 	git commit -a -m all
 '
 
+test_expect_success 'cache-tree invalidates i-t-a paths' '
+	git reset --hard &&
+	mkdir dir &&
+	: >dir/foo &&
+	git add dir/foo &&
+	git commit -m foo &&
+
+	: >dir/bar &&
+	git add -N dir/bar &&
+	git diff --cached --name-only >actual &&
+	echo dir/bar >expect &&
+	test_cmp expect actual &&
+
+	git write-tree >/dev/null &&
+
+	git diff --cached --name-only >actual &&
+	echo dir/bar >expect &&
+	test_cmp expect actual
+'
+
 test_done
 

-- 
1.8.0.rc2.23.g1fb49df