Tracey has discovered that 'got rebase' can corrupt the file index.
This happens if a file gets deleted, added, and deleted again in
the commit history being rebased.

This adds a test for the bug and a fix.

-----------------------------------------------
commit f8c22fb8662a04d5bddd793b39ab74d560f3ba7e (fileindex)
from: Stefan Sperling <stsp@stsp.name>
date: Fri Apr 24 08:22:46 2020 UTC
 
 add a test for rebase file index corruption problem fix in previous commit
 
diff dd0dd14a87d9a70da54a219cfab181dfff5f3e4e 0eb1956e309d9b69ef92dc44770cbbe11d637647
blob - 34f088073605cb3bb15c99c42ee9655c75a994da
blob + ff453b223f4e883bf285ec5a0e4e0c465ba3dd3c
--- regress/cmdline/common.sh
+++ regress/cmdline/common.sh
@@ -84,7 +84,8 @@ function git_show_tagger_time
 function git_show_parent_commit
 {
 	local repo="$1"
-	(cd $repo && git show --no-patch --pretty='format:%P')
+	local commit="$2"
+	(cd $repo && git show --no-patch --pretty='format:%P' $commit)
 }
 
 function git_show_tree
blob - e6f7a88e48abfbf74fffea06c088a955d610baf1
blob + e54de3f2dd29851f2675c480f96c1061d6e4df17
--- regress/cmdline/rebase.sh
+++ regress/cmdline/rebase.sh
@@ -1163,6 +1163,113 @@ function test_rebase_delete_missing_file {
 	test_done "$testroot" "$ret"
 }
 
+function test_rebase_rm_add_rm_file {
+	local testroot=`test_init rebase_rm_add_rm_file`
+
+	(cd $testroot/repo && git checkout -q -b newbranch)
+	(cd $testroot/repo && git rm -q beta)
+	git_commit $testroot/repo -m "removing beta from newbranch"
+	local orig_commit1=`git_show_head $testroot/repo`
+
+	echo 'restored beta' > $testroot/repo/beta
+	(cd $testroot/repo && git add beta)
+	git_commit $testroot/repo -m "restoring beta on newbranch"
+	local orig_commit2=`git_show_head $testroot/repo`
+
+	(cd $testroot/repo && git rm -q beta)
+	git_commit $testroot/repo -m "removing beta from newbranch again"
+	local orig_commit3=`git_show_head $testroot/repo`
+
+	(cd $testroot/repo && git checkout -q master)
+	echo "modified zeta on master" > $testroot/repo/epsilon/zeta
+	git_commit $testroot/repo -m "committing to zeta on master"
+	local master_commit=`git_show_head $testroot/repo`
+
+	got checkout $testroot/repo $testroot/wt > /dev/null
+	ret="$?"
+	if [ "$ret" != "0" ]; then
+		test_done "$testroot" "$ret"
+		return 1
+	fi
+
+	(cd $testroot/wt && got rebase newbranch > $testroot/stdout)
+
+	# this would error out with 'got: file index is corrupt'
+	(cd $testroot/wt && got status > /dev/null)
+	ret="$?"
+	if [ "$ret" != "0" ]; then
+		echo "got status command failed unexpectedly" >&2
+		test_done "$testroot" "$ret"
+		return 1
+	fi
+
+	(cd $testroot/repo && git checkout -q newbranch)
+	local new_commit3=`git_show_head $testroot/repo`
+	local new_commit2=`git_show_parent_commit $testroot/repo`
+	local new_commit1=`git_show_parent_commit $testroot/repo $new_commit2`
+
+	(cd $testroot/repo && git checkout -q newbranch)
+
+	local short_orig_commit1=`trim_obj_id 28 $orig_commit1`
+	local short_orig_commit2=`trim_obj_id 28 $orig_commit2`
+	local short_orig_commit3=`trim_obj_id 28 $orig_commit3`
+	local short_new_commit1=`trim_obj_id 28 $new_commit1`
+	local short_new_commit2=`trim_obj_id 28 $new_commit2`
+	local short_new_commit3=`trim_obj_id 28 $new_commit3`
+
+	echo "D  beta" > $testroot/stdout.expected
+	echo -n "$short_orig_commit1 -> $short_new_commit1" \
+		>> $testroot/stdout.expected
+	echo ": removing beta from newbranch" >> $testroot/stdout.expected
+	echo "A  beta" >> $testroot/stdout.expected
+	echo -n "$short_orig_commit2 -> $short_new_commit2" \
+		>> $testroot/stdout.expected
+	echo ": restoring beta on newbranch" >> $testroot/stdout.expected
+	echo "D  beta" >> $testroot/stdout.expected
+	echo -n "$short_orig_commit3 -> $short_new_commit3" \
+		>> $testroot/stdout.expected
+	echo ": removing beta from newbranch again" >> $testroot/stdout.expected
+	echo "Switching work tree to refs/heads/newbranch" \
+		>> $testroot/stdout.expected
+
+	cmp -s $testroot/stdout.expected $testroot/stdout
+	ret="$?"
+	if [ "$ret" != "0" ]; then
+		diff -u $testroot/stdout.expected $testroot/stdout
+		test_done "$testroot" "$ret"
+		return 1
+	fi
+
+	(cd $testroot/wt && got status > $testroot/stdout)
+	ret="$?"
+	if [ "$ret" != "0" ]; then
+		echo "got status command failed unexpectedly" >&2
+		test_done "$testroot" "$ret"
+		return 1
+	fi
+
+	echo -n > $testroot/stdout.expected
+	cmp -s $testroot/stdout.expected $testroot/stdout
+	ret="$?"
+	if [ "$ret" != "0" ]; then
+		diff -u $testroot/stdout.expected $testroot/stdout
+		test_done "$testroot" "$ret"
+		return 1
+	fi
+
+	(cd $testroot/wt && got log -l4 | grep ^commit > $testroot/stdout)
+	echo "commit $new_commit3 (newbranch)" > $testroot/stdout.expected
+	echo "commit $new_commit2" >> $testroot/stdout.expected
+	echo "commit $new_commit1" >> $testroot/stdout.expected
+	echo "commit $master_commit (master)" >> $testroot/stdout.expected
+	cmp -s $testroot/stdout.expected $testroot/stdout
+	ret="$?"
+	if [ "$ret" != "0" ]; then
+		diff -u $testroot/stdout.expected $testroot/stdout
+	fi
+	test_done "$testroot" "$ret"
+}
+
 run_test test_rebase_basic
 run_test test_rebase_ancestry_check
 run_test test_rebase_continue
@@ -1176,3 +1283,4 @@ run_test test_rebase_forward
 run_test test_rebase_out_of_date
 run_test test_rebase_trims_empty_dir
 run_test test_rebase_delete_missing_file
+run_test test_rebase_rm_add_rm_file

-----------------------------------------------
commit c965e9bd3a1c5efec760787528b3756f7ab7afc7
from: Stefan Sperling <stsp@stsp.name>
date: Fri Apr 24 08:22:46 2020 UTC
 
 remove file index entries from RB tree upon flush to disk
 
 Fixes a file index corruption problem with 'got rebase' found by tracey.
 
diff 07912ed061a0a4946a026a5ca01322fd20dd2dd5 dd0dd14a87d9a70da54a219cfab181dfff5f3e4e
blob - 61af7dd7264c91833efaded48290d683fc4500cc
blob + 460afc6a44656e2606c3799dcc340b57e57cf037
--- lib/fileindex.c
+++ lib/fileindex.c
@@ -222,8 +222,8 @@ got_fileindex_entry_remove(struct got_fileindex *filei
 	/*
 	 * Removing an entry from the RB tree immediately breaks
 	 * in-progress iterations over file index entries.
-	 * So flag this entry for removal and skip it once the index
-	 * is written out to disk, and pretend this entry no longer
+	 * So flag this entry for removal and remove it once the index
+	 * is written out to disk. Meanwhile, pretend this entry no longer
 	 * exists if we get queried for it again before then.
 	 */
 	ie->flags |= GOT_FILEIDX_F_REMOVE_ON_FLUSH;
@@ -423,7 +423,7 @@ got_fileindex_write(struct got_fileindex *fileindex, F
 	SHA1_CTX ctx;
 	uint8_t sha1[SHA1_DIGEST_LENGTH];
 	size_t n;
-	struct got_fileindex_entry *ie;
+	struct got_fileindex_entry *ie, *tmp;
 
 	SHA1Init(&ctx);
 
@@ -444,10 +444,13 @@ got_fileindex_write(struct got_fileindex *fileindex, F
 	if (n != sizeof(hdr.nentries))
 		return got_ferror(outfile, GOT_ERR_IO);
 
-	RB_FOREACH(ie, got_fileindex_tree, &fileindex->entries) {
+	RB_FOREACH_SAFE(ie, got_fileindex_tree, &fileindex->entries, tmp) {
 		ie->flags &= ~GOT_FILEIDX_F_NOT_FLUSHED;
-		if (ie->flags & GOT_FILEIDX_F_REMOVE_ON_FLUSH)
+		if (ie->flags & GOT_FILEIDX_F_REMOVE_ON_FLUSH) {
+			RB_REMOVE(got_fileindex_tree, &fileindex->entries, ie);
+			got_fileindex_entry_free(ie);
 			continue;
+		}
 		err = write_fileindex_entry(&ctx, ie, outfile);
 		if (err)
 			return err;