Sparse Index: Design, Format, Tests

Since the "test-tool read-cache" was originally added back in 1ecb5ff141 (read-cache: add simple performance test, 2013-06-09) it's been growing all sorts of bells and whistles that aren't very conducive to performance testing the index, e.g. it learned how to read config.

Let's split what remains of the "test-tool read-cache" into the two narrow use-cases it's used for.

---
 Makefile                         |  3 ++-
 t/helper/test-read-cache-again.c | 31 +++++++++++++++++++++++++
 t/helper/test-read-cache-perf.c  | 21 +++++++++++++++++
 t/helper/test-read-cache.c       | 39 --------------------------------
 t/helper/test-tool.c             |  3 ++-
 t/helper/test-tool.h             |  3 ++-
 t/perf/p0002-read-cache.sh       |  2 +-
 t/t7519-status-fsmonitor.sh      |  2 +-
 8 files changed, 60 insertions(+), 44 deletions(-)
 create mode 100644 t/helper/test-read-cache-again.c
 create mode 100644 t/helper/test-read-cache-perf.c
 delete mode 100644 t/helper/test-read-cache.c

index 89b1d53741..a1bbb818d9 100644
@@ -724,7 +724,8 @@ TEST_BUILTINS_OBJS += test-prio-queue.o
 TEST_BUILTINS_OBJS += test-proc-receive.o
 TEST_BUILTINS_OBJS += test-progress.o
 TEST_BUILTINS_OBJS += test-reach.o
-TEST_BUILTINS_OBJS += test-read-cache.o
+TEST_BUILTINS_OBJS += test-read-cache-again.o
+TEST_BUILTINS_OBJS += test-read-cache-perf.o
 TEST_BUILTINS_OBJS += test-read-graph.o
 TEST_BUILTINS_OBJS += test-read-midx.o
 TEST_BUILTINS_OBJS += test-ref-store.o

new file mode 100644
index 0000000000..5e20ca1c8f
@@ -0,0 +1,31 @@
+#include "test-tool.h"
+#include "cache.h"
+
+int cmd__read_cache_again(int argc, const char **argv)
+{
+	struct repository *r = the_repository;
+	int cnt;
+	const char *name;
+
+	if (argc != 2)
+		die("usage: test-tool read-cache-again <count> <file>");
+
+	cnt = strtol(argv[0], NULL, 0);
+	name = argv[2];
+
+	setup_git_directory();
+	while (cnt--) {
+		int pos;
+		repo_read_index(r);
+		refresh_index(r->index, REFRESH_QUIET,
+			      NULL, NULL, NULL);
+		pos = index_name_pos(r->index, name, strlen(name));
+		if (pos < 0)
+			die("%s not in index", name);
+		printf("%s is%s up to date\n", name,
+		       ce_uptodate(r->index->cache[pos]) ? "" : " not");
+		write_file(name, "%d\n", cnt);
+		discard_index(r->index);
+	}
+	return 0;
+}

new file mode 100644
index 0000000000..ac9c297efa
@@ -0,0 +1,21 @@
+#include "test-tool.h"
+#include "cache.h"
+
+int cmd__read_cache_perf(int argc, const char **argv)
+{
+	struct repository *r = the_repository;
+	int cnt = 1000;
+
+	if (argc == 1)
+		cnt = strtol(argv[0], NULL, 0);
+	else if (argc)
+		die("usage: test-tool read-cache-perf [<count>]");
+
+	setup_git_directory();
+	while (cnt--) {
+		repo_read_index(r);
+		discard_index(r->index);
+	}
+
+	return 0;
+}

deleted file mode 100644
index 2499999af3..0000000000
@@ -1,39 +0,0 @@
-#include "test-tool.h"
-#include "cache.h"
-#include "config.h"
-
-int cmd__read_cache(int argc, const char **argv)
-{
-	struct repository *r = the_repository;
-	int i, cnt = 1;
-	const char *name = NULL;
-
-	for (++argv, --argc; *argv && starts_with(*argv, "--"); ++argv, --argc) {
-		if (skip_prefix(*argv, "--print-and-refresh=", &name))
-			continue;
-	}
-
-	if (argc == 1)
-		cnt = strtol(argv[0], NULL, 0);
-	setup_git_directory();
-	git_config(git_default_config, NULL);
-
-	for (i = 0; i < cnt; i++) {
-		repo_read_index(r);
-
-		if (name) {
-			int pos;
-
-			refresh_index(r->index, REFRESH_QUIET,
-				      NULL, NULL, NULL);
-			pos = index_name_pos(r->index, name, strlen(name));
-			if (pos < 0)
-				die("%s not in index", name);
-			printf("%s is%s up to date\n", name,
-			       ce_uptodate(r->index->cache[pos]) ? "" : " not");
-			write_file(name, "%d\n", i);
-		}
-		discard_index(r->index);
-	}
-	return 0;
-}

index f97cd9f48a..1334fa25ba 100644
@@ -52,7 +52,8 @@ static struct test_cmd cmds[] = {
 	{ "proc-receive", cmd__proc_receive},
 	{ "progress", cmd__progress },
 	{ "reach", cmd__reach },
-	{ "read-cache", cmd__read_cache },
+	{ "read-cache-again", cmd__read_cache_again },
+	{ "read-cache-perf", cmd__read_cache_perf },
 	{ "read-graph", cmd__read_graph },
 	{ "read-midx", cmd__read_midx },
 	{ "ref-store", cmd__ref_store },

index 28072c0ad5..d70cde8574 100644
@@ -41,7 +41,8 @@ int cmd__prio_queue(int argc, const char **argv);
 int cmd__proc_receive(int argc, const char **argv);
 int cmd__progress(int argc, const char **argv);
 int cmd__reach(int argc, const char **argv);
-int cmd__read_cache(int argc, const char **argv);
+int cmd__read_cache_again(int argc, const char **argv);
+int cmd__read_cache_perf(int argc, const char **argv);
 int cmd__read_graph(int argc, const char **argv);
 int cmd__read_midx(int argc, const char **argv);
 int cmd__ref_store(int argc, const char **argv);

index cdd105a594..d0ba5173fb 100755
@@ -8,7 +8,7 @@ test_perf_default_repo
 
 count=1000
 test_perf "read_cache/discard_cache $count times" "
-	test-tool read-cache $count
+	test-tool read-cache-perf $count
 "
 
 test_done

index 45d025f960..3761a8781d 100755
@@ -359,7 +359,7 @@ test_expect_success UNTRACKED_CACHE 'ignore .git changes when invalidating UNTR'
 test_expect_success 'discard_index() also discards fsmonitor info' '
 	test_config core.fsmonitor "$TEST_DIRECTORY/t7519/fsmonitor-all" &&
 	test_might_fail git update-index --refresh &&
-	test-tool read-cache --print-and-refresh=tracked 2 >actual &&
+	test-tool read-cache-again 2 tracked >actual &&
 	printf "tracked is%s up to date\n" "" " not" >expect &&
 	test_cmp expect actual
 '

2.31.0.260.g719c683c1d

From: Derrick Stolee <[email protected]>

We will use 'test-tool read-cache --table' to check that a sparse index is written as part of init_repos. Since we will no longer always expand a sparse index into a full index, add an '--expand' parameter that adds a call to ensure_full_index() so we can compare a sparse index directly against a full index, or at least what the in-memory index looks like when expanded in this way.

---
 t/helper/test-read-cache.c               | 13 ++++++++++++-
 t/t1092-sparse-checkout-compatibility.sh |  5 +++++
 2 files changed, 17 insertions(+), 1 deletion(-)

index 6cfd8f2de71c..b52c174acc7a 100644
@@ -4,6 +4,7 @@
 #include "blob.h"
 #include "commit.h"
 #include "tree.h"
+#include "sparse-index.h"
 
 static void print_cache_entry(struct cache_entry *ce)
 {

@@ -35,13 +36,19 @@ int cmd__read_cache(int argc, const char **argv)
 	struct repository *r = the_repository;
 	int i, cnt = 1;
 	const char *name = NULL;
-	int table = 0;
+	int table = 0, expand = 0;
+
+	initialize_the_repository();
+	prepare_repo_settings(r);
+	r->settings.command_requires_full_index = 0;
 
 	for (++argv, --argc; *argv && starts_with(*argv, "--"); ++argv, --argc) {
 		if (skip_prefix(*argv, "--print-and-refresh=", &name))
 			continue;
 		if (!strcmp(*argv, "--table"))
 			table = 1;
+		else if (!strcmp(*argv, "--expand"))
+			expand = 1;
 	}
 
 	if (argc == 1)

@@ -51,6 +58,10 @@ int cmd__read_cache(int argc, const char **argv)
 
 	for (i = 0; i < cnt; i++) {
 		repo_read_index(r);
+
+		if (expand)
+			ensure_full_index(r->index);
+
 		if (name) {
 			int pos;
 

index de5d8461c993..a1aea141c62c 100755
@@ -130,6 +130,11 @@ test_sparse_match () {
 	test_cmp sparse-checkout-err sparse-index-err
 }
 
+test_expect_success 'expanded in-memory index matches full index' '
+	init_repos &&
+	test_sparse_match test-tool read-cache --expand --table
+'
+
 test_expect_success 'status with options' '
 	init_repos &&
 	test_all_match git status --porcelain=v2 &&

gitgitgadget

From: Derrick Stolee <[email protected]>

The next change will translate full indexes into sparse indexes at write time. The existing logic provides a way for every sparse index to be expanded to a full index at read time. However, there are cases where an index is written and then continues to be used in-memory to perform further updates.

unpack_trees() is frequently called after such a write. In particular, commands like 'git reset' do this double-update of the index.

Ensure that we have a full index when entering unpack_trees(), but only when command_requires_full_index is true. This is always true at the moment, but we will later relax that after unpack_trees() is updated to handle sparse directory entries.

---
 unpack-trees.c | 7 +++++++
 1 file changed, 7 insertions(+)

index eb8fcda31ba7..2da3e5ec77a1 100644
@@ -1570,6 +1570,7 @@ static int verify_absent(const struct cache_entry *,
  */
 int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)
 {
+	struct repository *repo = the_repository;
 	int i, ret;
 	static struct cache_entry *dfc;
 	struct pattern_list pl;

@@ -1581,6 +1582,12 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 	trace_performance_enter();
 	trace2_region_enter("unpack_trees", "unpack_trees", the_repository);
 
+	prepare_repo_settings(repo);
+	if (repo->settings.command_requires_full_index) {
+		ensure_full_index(o->src_index);
+		ensure_full_index(o->dst_index);
+	}
+
 	if (!core_apply_sparse_checkout || !o->update)
 		o->skip_sparse_checkout = 1;
 	if (!o->skip_sparse_checkout && !o->pl) {

gitgitgadget

From: Derrick Stolee <[email protected]>

As we modify the sparse-checkout definition, we perform index operations on a pattern_list that only exists in-memory. This allows easy backing out in case the index update fails.

However, if the index write itself cares about the sparse-checkout pattern set, we need access to that in-memory copy. Place a pointer to a 'struct pattern_list' in the index so we can access this on-demand. This will be used in the next change which uses the sparse-checkout definition to filter out directories that are outside the sparse cone.

---
 builtin/sparse-checkout.c | 17 ++++++++++-------
 cache.h                   |  2 ++
 2 files changed, 12 insertions(+), 7 deletions(-)

index 2306a9ad98e0..e00b82af727b 100644
@@ -110,6 +110,8 @@ static int update_working_directory(struct pattern_list *pl)
 	if (is_index_unborn(r->index))
 		return UPDATE_SPARSITY_SUCCESS;
 
+	r->index->sparse_checkout_patterns = pl;
+
 	memset(&o, 0, sizeof(o));
 	o.verbose_update = isatty(2);
 	o.update = 1;

@@ -138,6 +140,7 @@ static int update_working_directory(struct pattern_list *pl)
 	else
 		rollback_lock_file(&lock_file);
 
+	r->index->sparse_checkout_patterns = NULL;
 	return result;
 }
 

@@ -517,19 +520,18 @@ static int modify_pattern_list(int argc, const char **argv, enum modify_type m)
 {
 	int result;
 	int changed_config = 0;
-	struct pattern_list pl;
-	memset(&pl, 0, sizeof(pl));
+	struct pattern_list *pl = xcalloc(1, sizeof(*pl));
 
 	switch (m) {
 	case ADD:
 		if (core_sparse_checkout_cone)
-			add_patterns_cone_mode(argc, argv, &pl);
+			add_patterns_cone_mode(argc, argv, pl);
 		else
-			add_patterns_literal(argc, argv, &pl);
+			add_patterns_literal(argc, argv, pl);
 		break;
 
 	case REPLACE:
-		add_patterns_from_input(&pl, argc, argv);
+		add_patterns_from_input(pl, argc, argv);
 		break;
 	}
 

@@ -539,12 +541,13 @@ static int modify_pattern_list(int argc, const char **argv, enum modify_type m)
 		changed_config = 1;
 	}
 
-	result = write_patterns_and_update(&pl);
+	result = write_patterns_and_update(pl);
 
 	if (result && changed_config)
 		set_config(MODE_NO_PATTERNS);
 
-	clear_pattern_list(&pl);
+	clear_pattern_list(pl);
+	free(pl);
 	return result;
 }
 

index abb00a068e5d..759ca92e2ecc 100644
@@ -307,6 +307,7 @@ static inline unsigned int canon_mode(unsigned int mode)
 struct split_index;
 struct untracked_cache;
 struct progress;
+struct pattern_list;
 
 struct index_state {
 	struct cache_entry **cache;

@@ -338,6 +339,7 @@ struct index_state {
 	struct mem_pool *ce_mem_pool;
 	struct progress *progress;
 	struct repository *repo;
+	struct pattern_list *sparse_checkout_patterns;
 };
 
 /* Name hashing */

gitgitgadget

From: Derrick Stolee <[email protected]>

If we have a full index, then we can convert it to a sparse index by replacing directories outside of the sparse cone with sparse directory entries. The convert_to_sparse() method does this, when the situation is appropriate.

For now, we avoid converting the index to a sparse index if:

1. the index is split.
2. the index is already sparse.
3. sparse-checkout is disabled.
4. sparse-checkout does not use cone mode.

Finally, we currently limit the conversion to when the GIT_TEST_SPARSE_INDEX environment variable is enabled. A mode using Git config will be added in a later change.

The trickiest thing about this conversion is that we might not be able to mark a directory as a sparse directory just because it is outside the sparse cone. There might be unmerged files within that directory, so we need to look for those. Also, if there is some strange reason why a file is not marked with CE_SKIP_WORKTREE, then we should give up on converting that directory. There is still hope that some of its subdirectories might be able to convert to sparse, so we keep looking deeper.

The conversion process is assisted by the cache-tree extension. This is calculated from the full index if it does not already exist. We then abandon the cache-tree as it no longer applies to the newly-sparse index. Thus, this cache-tree will be recalculated in every sparse-full-sparse round-trip until we integrate the cache-tree extension with the sparse index.

Some Git commands use the index after writing it. For example, 'git add' will update the index, then write it to disk, then read its entries to report information. To keep the in-memory index in a full state after writing, we re-expand it to a full one after the write. This is wasteful for commands that only write the index and do not read from it again, but that is only the case until we make those commands "sparse aware."

We can compare the behavior of the sparse-index in t1092-sparse-checkout-compability.sh by using GIT_TEST_SPARSE_INDEX=1 when operating on the 'sparse-index' repo. We can also compare the two sparse repos directly, such as comparing their indexes (when expanded to full in the case of the 'sparse-index' repo). We also verify that the index is actually populated with sparse directory entries.

The 'checkout and reset (mixed)' test is marked for failure when comparing a sparse repo to a full repo, but we can compare the two sparse-checkout cases directly to ensure that we are not changing the behavior when using a sparse index.

---
 cache-tree.c                             |   3 +
 cache.h                                  |   2 +
 read-cache.c                             |  26 ++++-
 sparse-index.c                           | 139 +++++++++++++++++++++++
 sparse-index.h                           |   1 +
 t/t1092-sparse-checkout-compatibility.sh |  61 +++++++++-
 6 files changed, 228 insertions(+), 4 deletions(-)

index 2fb483d3c083..5f07a39e501e 100644
@@ -6,6 +6,7 @@
 #include "object-store.h"
 #include "replace-object.h"
 #include "promisor-remote.h"
+#include "sparse-index.h"
 
 #ifndef DEBUG_CACHE_TREE
 #define DEBUG_CACHE_TREE 0

@@ -442,6 +443,8 @@ int cache_tree_update(struct index_state *istate, int flags)
 	if (i)
 		return i;
 
+	ensure_full_index(istate);
+
 	if (!istate->cache_tree)
 		istate->cache_tree = cache_tree();
 

index 759ca92e2ecc..69a32146cd77 100644
@@ -251,6 +251,8 @@ static inline unsigned int create_ce_mode(unsigned int mode)
 {
 	if (S_ISLNK(mode))
 		return S_IFLNK;
+	if (mode == S_IFDIR)
+		return S_IFDIR;
 	if (S_ISDIR(mode) || S_ISGITLINK(mode))
 		return S_IFGITLINK;
 	return S_IFREG | ce_permissions(mode);

index dd3980c12b53..b9c08773466c 100644
@@ -25,6 +25,7 @@
 #include "fsmonitor.h"
 #include "thread-utils.h"
 #include "progress.h"
+#include "sparse-index.h"
 
 /* Mask for the name length in ce_flags in the on-disk index */
 

@@ -1002,8 +1003,14 @@ int verify_path(const char *path, unsigned mode)
 
 			c = *path++;
 			if ((c == '.' && !verify_dotfile(path, mode)) ||
-			    is_dir_sep(c) || c == '\0')
+			    is_dir_sep(c))
 				return 0;
+			/*
+			 * allow terminating directory separators for
+			 * sparse directory entries.
+			 */
+			if (c == '\0')
+				return S_ISDIR(mode);
 		} else if (c == '\\' && protect_ntfs) {
 			if (is_ntfs_dotgit(path))
 				return 0;

@@ -3079,6 +3086,14 @@ static int do_write_locked_index(struct index_state *istate, struct lock_file *l
 				 unsigned flags)
 {
 	int ret;
+	int was_full = !istate->sparse_index;
+
+	ret = convert_to_sparse(istate);
+
+	if (ret) {
+		warning(_("failed to convert to a sparse-index"));
+		return ret;
+	}
 
 	/*
 	 * TODO trace2: replace "the_repository" with the actual repo instance

@@ -3090,6 +3105,9 @@ static int do_write_locked_index(struct index_state *istate, struct lock_file *l
 	trace2_region_leave_printf("index", "do_write_index", the_repository,
 				   "%s", get_lock_file_path(lock));
 
+	if (was_full)
+		ensure_full_index(istate);
+
 	if (ret)
 		return ret;
 	if (flags & COMMIT_LOCK)

@@ -3180,9 +3198,10 @@ static int write_shared_index(struct index_state *istate,
 			      struct tempfile **temp)
 {
 	struct split_index *si = istate->split_index;
-	int ret;
+	int ret, was_full = !istate->sparse_index;
 
 	move_cache_to_base_index(istate);
+	convert_to_sparse(istate);
 
 	trace2_region_enter_printf("index", "shared/do_write_index",
 				   the_repository, "%s", get_tempfile_path(*temp));

@@ -3190,6 +3209,9 @@ static int write_shared_index(struct index_state *istate,
 	trace2_region_leave_printf("index", "shared/do_write_index",
 				   the_repository, "%s", get_tempfile_path(*temp));
 
+	if (was_full)
+		ensure_full_index(istate);
+
 	if (ret)
 		return ret;
 	ret = adjust_shared_perm(get_tempfile_path(*temp));

index 09a20d036c46..64380e121d80 100644
@@ -3,5 +3,6 @@
 
 struct index_state;
 void ensure_full_index(struct index_state *istate);
+int convert_to_sparse(struct index_state *istate);
 
 #endif

gitgitgadget

I have a vague recollection that I did that at one point, and it didn't work. However, using the simpler

	if (S_ISDIR(mode))
		return S_IFDIR;
	if (S_ISGITLINK(mode))
		return S_IFGITLINK;

passes all of my tests.

Looking at the history of create_ce_mode(), this "||" condition was created in this commit:

commit 9eec4795d44439cd170fb52c73827c728252648d

Author: Linus Torvalds <[email protected]>
Date:   Mon Apr 9 21:14:58 2007 -0700

Add "S_IFDIRLNK" file mode infrastructure for git links

This just adds the basic helper functions to recognize and work with git tree entries that are links to other git repositories ("subprojects"). They still aren't actually connected up to any of the code-paths, but now all the infrastructure is in place.

The next commit will start actually adding actual subproject support.

There isn't any justification of why S_ISDIR() is there. Perhaps it was defensive programming? If that is the case, then this simpler logic will work.

Thanks,
-Stolee

I'm not sure why it was passing yesterday (maybe I was in the wrong worktree) but I _do_ get failures, such as this one in t2105:

expecting success of 2105.4 'add gitlink to relative .git file':

        git update-index --add -- sub2

+ git update-index --add -- sub2
warning: index entry is a directory, but not sparse (00000000)
error: Could not read 50e526bb426771f6036ad3a8b0c81d511d91fc2a

BUG: read-cache.c:324: unsupported ce_mode: 40000

Aborted (core dumped)
error: last command exited with $?=134
not ok 4 - add gitlink to relative .git file
#
# git update-index --add -- sub2
#

In this case, the mode that is specified is equal to 040775, so we need to use the permission bits outside of __S_IFMT (0170000) to determine if this is a sparse directory or a submodule entry. Submodules will never be sparse, so permissions matter. Sparse directories never actually exist, so permissions don't matter.

Playing around with it, I still only see the exact equality as working for me.

I can, however, use this format for these if statements:

	if (S_ISSPARSEDIR(mode))
		return S_IFDIR;
	if (S_ISDIR(mode) || S_ISGITLINK(mode))
		return S_IFGITLINK;

The S_ISSPARSEDIR macro expands to the exact equality.

Now, if we intended to make this work differently, then a change would be required to construct_sparse_dir_entry() in sparse-index.c:

static struct cache_entry *construct_sparse_dir_entry(
struct index_state *istate, const char *sparse_dir, struct cache_tree *tree)

{
	struct cache_entry *de;

	de = make_cache_entry(istate, S_IFDIR, &tree->oid, sparse_dir, 0, 0);

	de->ce_flags |= CE_SKIP_WORKTREE;
	return de;
}

For instance, we could at this point assign de->ce_mode to be S_IFDIR directly. It seems like the wrong place to do that to me, but I'm open to suggestions.

Thanks,
-Stolee

From: Derrick Stolee <[email protected]>

A submodule is stored as a "Git link" that actually points to a commit within a submodule. Submodules are populated or not depending on submodule configuration, not sparse-checkout. To ensure that the sparse-index feature integrates correctly with submodules, we should not collapse a directory if there is a Git link within its range.

---
 sparse-index.c                           |  1 +
 t/t1092-sparse-checkout-compatibility.sh | 17 +++++++++++++++++
 2 files changed, 18 insertions(+)

index 619ff7c2e217..7631f7bd00b7 100644
@@ -52,6 +52,7 @@ static int convert_to_sparse_rec(struct index_state *istate,
 		struct cache_entry *ce = istate->cache[i];
 
 		if (ce_stage(ce) ||
+		    S_ISGITLINK(ce->ce_mode) ||
 		    !(ce->ce_flags & CE_SKIP_WORKTREE))
 			can_convert = 0;
 	}

index 1e888d195122..cba5f89b1e96 100755
@@ -376,4 +376,21 @@ test_expect_success 'clean' '
 	test_sparse_match test_path_is_dir folder1
 '
 
+test_expect_success 'submodule handling' '
+	init_repos &&
+
+	test_all_match mkdir modules &&
+	test_all_match touch modules/a &&
+	test_all_match git add modules &&
+	test_all_match git commit -m "add modules directory" &&
+
+	run_on_all git submodule add "$(pwd)/initial-repo" modules/sub &&
+	test_all_match git commit -m "add submodule" &&
+
+	# having a submodule prevents "modules" from collapse
+	test-tool -C sparse-index read-cache --table >cache &&
+	grep "100644 blob .*	modules/a" cache &&
+	grep "160000 commit $(git -C initial-repo rev-parse HEAD)	modules/sub" cache
+'
+
 test_done

gitgitgadget

From: Derrick Stolee <[email protected]>

The index_pos_by_traverse_info() currently throws a BUG() when a directory entry exists exactly in the index. We need to consider that it is possible to have a directory in a sparse index as long as that entry is itself marked with the skip-worktree bit.

The 'pos' variable is assigned a negative value if an exact match is not found. Since a directory name can be an exact match, it is no longer an error to have a nonnegative 'pos' value.

---
 unpack-trees.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)

index 2da3e5ec77a1..e81d82d72d89 100644
@@ -749,9 +749,12 @@ static int index_pos_by_traverse_info(struct name_entry *names,
 	strbuf_make_traverse_path(&name, info, names->path, names->pathlen);
 	strbuf_addch(&name, '/');
 	pos = index_name_pos(o->src_index, name.buf, name.len);
-	if (pos >= 0)
-		BUG("This is a directory and should not exist in index");
-	pos = -pos - 1;
+	if (pos >= 0) {
+		if (!o->src_index->sparse_index ||
+		    !(o->src_index->cache[pos]->ce_flags & CE_SKIP_WORKTREE))
+			BUG("This is a directory and should not exist in index");
+	} else
+		pos = -pos - 1;
 	if (pos >= o->src_index->cache_nr ||
 	    !starts_with(o->src_index->cache[pos]->name, name.buf) ||
 	    (pos > 0 && starts_with(o->src_index->cache[pos-1]->name, name.buf)))

gitgitgadget

From: Derrick Stolee <[email protected]>

Add a test case that uses test_region to ensure that we are truly expanding a sparse index to a full one, then converting back to sparse when writing the index. As we integrate more Git commands with the sparse index, we will convert these commands to check that we do _not_ convert the sparse index to a full index and instead stay sparse the entire time.

---
 t/t1092-sparse-checkout-compatibility.sh | 18 ++++++++++++++++++
 1 file changed, 18 insertions(+)

index cba5f89b1e96..47f983217852 100755
@@ -393,4 +393,22 @@ test_expect_success 'submodule handling' '
 	grep "160000 commit $(git -C initial-repo rev-parse HEAD)	modules/sub" cache
 '
 
+test_expect_success 'sparse-index is expanded and converted back' '
+	init_repos &&
+
+	(
+		GIT_TEST_SPARSE_INDEX=1 &&
+		export GIT_TEST_SPARSE_INDEX &&
+		GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
+			git -C sparse-index -c core.fsmonitor="" reset --hard &&
+		test_region index convert_to_sparse trace2.txt &&
+		test_region index ensure_full_index trace2.txt &&
+
+		rm trace2.txt &&
+		GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
+			git -C sparse-index -c core.fsmonitor="" status -uno &&
+		test_region index ensure_full_index trace2.txt
+	)
+'
+
 test_done

gitgitgadget

From: Derrick Stolee <[email protected]>

Previously, we enabled the sparse index format only using GIT_TEST_SPARSE_INDEX=1. This is not a feasible direction for users to actually select this mode. Further, sparse directory entries are not understood by the index formats as advertised.

We _could_ add a new index version that explicitly adds these capabilities, but there are nuances to index formats 2, 3, and 4 that are still valuable to select as options. Until we add index format version 5, create a repo extension, "extensions.sparseIndex", that specifies that the tool reading this repository must understand sparse directory entries.

This change only encodes the extension and enables it when GIT_TEST_SPARSE_INDEX=1. Later, we will add a more user-friendly CLI mechanism.

---
 Documentation/config/extensions.txt |  8 ++++++
 cache.h                             |  1 +
 repo-settings.c                     |  7 ++++++
 repository.h                        |  3 ++-
 setup.c                             |  3 +++
 sparse-index.c                      | 38 +++++++++++++++++++++++++----
 6 files changed, 54 insertions(+), 6 deletions(-)

index 4e23d73cdcad..c02e09af0046 100644
@@ -6,3 +6,11 @@ extensions.objectFormat::
 Note that this setting should only be set by linkgit:git-init[1] or
 linkgit:git-clone[1].  Trying to change it after initialization will not
 work and will produce hard-to-diagnose issues.
+
+extensions.sparseIndex::
+	When combined with `core.sparseCheckout=true` and
+	`core.sparseCheckoutCone=true`, the index may contain entries
+	corresponding to directories outside of the sparse-checkout
+	definition in lieu of containing each path under such directories.
+	Versions of Git that do not understand this extension do not
+	expect directory entries in the index.

index 69a32146cd77..4ca6cd7f782c 100644
@@ -1059,6 +1059,7 @@ struct repository_format {
 	int worktree_config;
 	int is_bare;
 	int hash_algo;
+	int sparse_index;
 	char *work_tree;
 	struct string_list unknown_extensions;
 	struct string_list v1_only_extensions;

index d63569e4041e..9677d50f9238 100644
@@ -85,4 +85,11 @@ void prepare_repo_settings(struct repository *r)
 	 * removed.
 	 */
 	r->settings.command_requires_full_index = 1;
+
+	/*
+	 * Initialize this as off.
+	 */
+	r->settings.sparse_index = 0;
+	if (!repo_config_get_bool(r, "extensions.sparseindex", &value) && value)
+		r->settings.sparse_index = 1;
 }

index e06a23015697..a45f7520fd9e 100644
@@ -42,7 +42,8 @@ struct repo_settings {
 
 	int core_multi_pack_index;
 
-	unsigned command_requires_full_index:1;
+	unsigned command_requires_full_index:1,
+		 sparse_index:1;
 };
 
 struct repository {

index c04cd25a30df..cd8394564613 100644
@@ -500,6 +500,9 @@ static enum extension_result handle_extension(const char *var,
 			return error("invalid value for 'extensions.objectformat'");
 		data->hash_algo = format;
 		return EXTENSION_OK;
+	} else if (!strcmp(ext, "sparseindex")) {
+		data->sparse_index = 1;
+		return EXTENSION_OK;
 	}
 	return EXTENSION_UNKNOWN;
 }

index 7631f7bd00b7..3a6df66faeab 100644
@@ -102,19 +102,47 @@ static int convert_to_sparse_rec(struct index_state *istate,
 	return num_converted - start_converted;
 }
 
+static int enable_sparse_index(struct repository *repo)
+{
+	const char *config_path = repo_git_path(repo, "config.worktree");
+
+	if (upgrade_repository_format(1) < 0) {
+		warning(_("unable to upgrade repository format to enable sparse-index"));
+		return -1;
+	}
+	git_config_set_in_file_gently(config_path,
+				      "extensions.sparseIndex",
+				      "true");
+
+	prepare_repo_settings(repo);
+	repo->settings.sparse_index = 1;
+	return 0;
+}
+
 int convert_to_sparse(struct index_state *istate)
 {
 	if (istate->split_index || istate->sparse_index ||
 	    !core_apply_sparse_checkout || !core_sparse_checkout_cone)
 		return 0;
 
+	if (!istate->repo)
+		istate->repo = the_repository;
+
+	/*
+	 * The GIT_TEST_SPARSE_INDEX environment variable triggers the
+	 * extensions.sparseIndex config variable to be on.
+	 */
+	if (git_env_bool("GIT_TEST_SPARSE_INDEX", 0)) {
+		int err = enable_sparse_index(istate->repo);
+		if (err < 0)
+			return err;
+	}
+
 	/*
-	 * For now, only create a sparse index with the
-	 * GIT_TEST_SPARSE_INDEX environment variable. We will relax
-	 * this once we have a proper way to opt-in (and later still,
-	 * opt-out).
+	 * Only convert to sparse if extensions.sparseIndex is set.
 	 */
-	if (!git_env_bool("GIT_TEST_SPARSE_INDEX", 0))
+	prepare_repo_settings(istate->repo);
+	if (!istate->repo->settings.sparse_index)
 		return 0;
 
 	if (!istate->sparse_checkout_patterns) {

gitgitgadget

From: Derrick Stolee <[email protected]>

The sparse index extension is used to signal that index writes should be in sparse mode. This was only updated using GIT_TEST_SPARSE_INDEX=1.

Add a '--[no-]sparse-index' option to 'git sparse-checkout init' that specifies if the sparse index should be used. It also updates the index to use the correct format, either way. Add a warning in the documentation that the use of a repository extension might reduce compatibility with third-party tools. 'git sparse-checkout init' already sets extension.worktreeConfig, which places most sparse-checkout users outside of the scope of most third-party tools.

Update t1092-sparse-checkout-compatibility.sh to use this CLI instead of GIT_TEST_SPARSE_INDEX=1.

---
 Documentation/git-sparse-checkout.txt    | 14 +++++++
 builtin/sparse-checkout.c                | 17 ++++++++-
 sparse-index.c                           | 37 +++++++++++++------
 sparse-index.h                           |  3 ++
 t/t1092-sparse-checkout-compatibility.sh | 47 +++++++++++++-----------
 5 files changed, 84 insertions(+), 34 deletions(-)

index a0eeaeb02ee3..2ff66c5a4e41 100644
@@ -45,6 +45,20 @@ To avoid interfering with other worktrees, it first enables the
 When `--cone` is provided, the `core.sparseCheckoutCone` setting is
 also set, allowing for better performance with a limited set of
 patterns (see 'CONE PATTERN SET' below).
++
+Use the `--[no-]sparse-index` option to toggle the use of the sparse
+index format. This reduces the size of the index to be more closely
+aligned with your sparse-checkout definition. This can have significant
+performance advantages for commands such as `git status` or `git add`.
+This feature is still experimental. Some commands might be slower with
+a sparse index until they are properly integrated with the feature.
++
+**WARNING:** Using a sparse index requires modifying the index in a way
+that is not completely understood by external tools. If you have trouble
+with this compatibility, then run `git sparse-checkout init --no-sparse-index`
+to rewrite your index to not be sparse. Older versions of Git will not
+understand the `sparseIndex` repository extension and may fail to interact
+with your repository until it is disabled.
 
 'set'::
 	Write a set of patterns to the sparse-checkout file, as given as

index e00b82af727b..ca63e2c64e95 100644
@@ -14,6 +14,7 @@
 #include "unpack-trees.h"
 #include "wt-status.h"
 #include "quote.h"
+#include "sparse-index.h"
 
 static const char *empty_base = "";
 

@@ -283,12 +284,13 @@ static int set_config(enum sparse_checkout_mode mode)
 }
 
 static char const * const builtin_sparse_checkout_init_usage[] = {
-	N_("git sparse-checkout init [--cone]"),
+	N_("git sparse-checkout init [--cone] [--[no-]sparse-index]"),
 	NULL
 };
 
 static struct sparse_checkout_init_opts {
 	int cone_mode;
+	int sparse_index;
 } init_opts;
 
 static int sparse_checkout_init(int argc, const char **argv)

@@ -303,11 +305,15 @@ static int sparse_checkout_init(int argc, const char **argv)
 	static struct option builtin_sparse_checkout_init_options[] = {
 		OPT_BOOL(0, "cone", &init_opts.cone_mode,
 			 N_("initialize the sparse-checkout in cone mode")),
+		OPT_BOOL(0, "sparse-index", &init_opts.sparse_index,
+			 N_("toggle the use of a sparse index")),
 		OPT_END(),
 	};
 
 	repo_read_index(the_repository);
 
+	init_opts.sparse_index = -1;
+
 	argc = parse_options(argc, argv, NULL,
 			     builtin_sparse_checkout_init_options,
 			     builtin_sparse_checkout_init_usage, 0);

@@ -326,6 +332,15 @@ static int sparse_checkout_init(int argc, const char **argv)
 	sparse_filename = get_sparse_checkout_filename();
 	res = add_patterns_from_file_to_list(sparse_filename, "", 0, &pl, NULL);
 
+	if (init_opts.sparse_index >= 0) {
+		if (set_sparse_index_config(the_repository, init_opts.sparse_index) < 0)
+			die(_("failed to modify sparse-index config"));
+
+		/* force an index rewrite */
+		repo_read_index(the_repository);
+		the_repository->index->updated_workdir = 1;
+	}
+
 	/* If we already have a sparse-checkout file, use it. */
 	if (res >= 0) {
 		free(sparse_filename);

index 3a6df66faeab..30c1a11fd62d 100644
@@ -104,23 +104,37 @@ static int convert_to_sparse_rec(struct index_state *istate,
 
 static int enable_sparse_index(struct repository *repo)
 {
-	const char *config_path = repo_git_path(repo, "config.worktree");
+	int res;
 
 	if (upgrade_repository_format(1) < 0) {
 		warning(_("unable to upgrade repository format to enable sparse-index"));
 		return -1;
 	}
-	git_config_set_in_file_gently(config_path,
-				      "extensions.sparseIndex",
-				      "true");
+	res = git_config_set_gently("extensions.sparseindex", "true");
 
 	prepare_repo_settings(repo);
 	repo->settings.sparse_index = 1;
-	return 0;
+	return res;
+}
+
+int set_sparse_index_config(struct repository *repo, int enable)
+{
+	int res;
+
+	if (enable)
+		return enable_sparse_index(repo);
+
+	/* Don't downgrade repository format, just remove the extension. */
+	res = git_config_set_gently("extensions.sparseindex", NULL);
+
+	prepare_repo_settings(repo);
+	repo->settings.sparse_index = 0;
+	return res;
 }
 
 int convert_to_sparse(struct index_state *istate)
 {
+	int test_env;
 	if (istate->split_index || istate->sparse_index ||
 	    !core_apply_sparse_checkout || !core_sparse_checkout_cone)
 		return 0;

@@ -129,14 +143,13 @@ int convert_to_sparse(struct index_state *istate)
 		istate->repo = the_repository;
 
 	/*
-	 * The GIT_TEST_SPARSE_INDEX environment variable triggers the
-	 * extensions.sparseIndex config variable to be on.
+	 * If GIT_TEST_SPARSE_INDEX=1, then trigger extensions.sparseIndex
+	 * to be fully enabled. If GIT_TEST_SPARSE_INDEX=0 (set explicitly),
+	 * then purposefully disable the setting.
 	 */
-	if (git_env_bool("GIT_TEST_SPARSE_INDEX", 0)) {
-		int err = enable_sparse_index(istate->repo);
-		if (err < 0)
-			return err;
-	}
+	test_env = git_env_bool("GIT_TEST_SPARSE_INDEX", -1);
+	if (test_env >= 0)
+		set_sparse_index_config(istate->repo, test_env);
 
 	/*
 	 * Only convert to sparse if extensions.sparseIndex is set.

index 64380e121d80..39dcc859735e 100644
@@ -5,4 +5,7 @@ struct index_state;
 void ensure_full_index(struct index_state *istate);
 int convert_to_sparse(struct index_state *istate);
 
+struct repository;
+int set_sparse_index_config(struct repository *repo, int enable);
+
 #endif

gitgitgadget

From: Derrick Stolee <[email protected]>

We use 'git sparse-checkout init --cone --sparse-index' to toggle the sparse-index feature. It makes sense to also disable it when running 'git sparse-checkout disable'. This is particularly important because it removes the extensions.sparseIndex config option, allowing other tools to use this Git repository again.

This does mean that 'git sparse-checkout init' will not re-enable the sparse-index feature, even if it was previously enabled.

While testing this feature, I noticed that the sparse-index was not being written on the first run, but by a second. This was caught by the call to 'test-tool read-cache --table'. This requires adjusting some assignments to core_apply_sparse_checkout and pl.use_cone_patterns in the sparse_checkout_init() logic.

---
 builtin/sparse-checkout.c          | 10 +++++++++-
 t/t1091-sparse-checkout-builtin.sh | 13 +++++++++++++
 2 files changed, 22 insertions(+), 1 deletion(-)

index ca63e2c64e95..585343fa1972 100644
@@ -280,6 +280,9 @@ static int set_config(enum sparse_checkout_mode mode)
 				      "core.sparseCheckoutCone",
 				      mode == MODE_CONE_PATTERNS ? "true" : NULL);
 
+	if (mode == MODE_NO_PATTERNS)
+		set_sparse_index_config(the_repository, 0);
+
 	return 0;
 }
 

@@ -341,10 +344,11 @@ static int sparse_checkout_init(int argc, const char **argv)
 		the_repository->index->updated_workdir = 1;
 	}
 
+	core_apply_sparse_checkout = 1;
+
 	/* If we already have a sparse-checkout file, use it. */
 	if (res >= 0) {
 		free(sparse_filename);
-		core_apply_sparse_checkout = 1;
 		return update_working_directory(NULL);
 	}
 

@@ -366,6 +370,7 @@ static int sparse_checkout_init(int argc, const char **argv)
 	add_pattern(strbuf_detach(&pattern, NULL), empty_base, 0, &pl, 0);
 	strbuf_addstr(&pattern, "!/*/");
 	add_pattern(strbuf_detach(&pattern, NULL), empty_base, 0, &pl, 0);
+	pl.use_cone_patterns = init_opts.cone_mode;
 
 	return write_patterns_and_update(&pl);
 }

@@ -632,6 +637,9 @@ static int sparse_checkout_disable(int argc, const char **argv)
 	strbuf_addstr(&match_all, "/*");
 	add_pattern(strbuf_detach(&match_all, NULL), empty_base, 0, &pl, 0);
 
+	prepare_repo_settings(the_repository);
+	the_repository->settings.sparse_index = 0;
+
 	if (update_working_directory(&pl))
 		die(_("error while refreshing working directory"));
 

index fc64e9ed99f4..ff1ad570a255 100755
@@ -205,6 +205,19 @@ test_expect_success 'sparse-checkout disable' '
 	check_files repo a deep folder1 folder2
 '
 
+test_expect_success 'sparse-index enabled and disabled' '
+	git -C repo sparse-checkout init --cone --sparse-index &&
+	test_cmp_config -C repo true extensions.sparseIndex &&
+	test-tool -C repo read-cache --table >cache &&
+	grep " tree " cache &&
+
+	git -C repo sparse-checkout disable &&
+	test-tool -C repo read-cache --table >cache &&
+	! grep " tree " cache &&
+	git -C repo config --list >config &&
+	! grep extensions.sparseindex config
+'
+
 test_expect_success 'cone mode: init and set' '
 	git -C repo sparse-checkout init --cone &&
 	git -C repo config --list >config &&

gitgitgadget

From: Derrick Stolee <[email protected]>

The cache-tree extension was previously disabled with sparse indexes. However, the cache-tree is an important performance feature for commands like 'git status' and 'git add'. Integrate it with sparse directory entries.

When writing a sparse index, completely clear and recalculate the cache tree. By starting from scratch, the only integration necessary is to check if we hit a sparse directory entry and create a leaf of the cache-tree that has an entry_count of one and no subtrees.

---
 cache-tree.c   | 18 ++++++++++++++++++
 sparse-index.c | 10 +++++++++-
 2 files changed, 27 insertions(+), 1 deletion(-)

index 5f07a39e501e..950a9615db8f 100644
@@ -256,6 +256,24 @@ static int update_one(struct cache_tree *it,
 
 	*skip_count = 0;
 
+	/*
+	 * If the first entry of this region is a sparse directory
+	 * entry corresponding exactly to 'base', then this cache_tree
+	 * struct is a "leaf" in the data structure, pointing to the
+	 * tree OID specified in the entry.
+	 */
+	if (entries > 0) {
+		const struct cache_entry *ce = cache[0];
+
+		if (S_ISSPARSEDIR(ce->ce_mode) &&
+		    ce->ce_namelen == baselen &&
+		    !strncmp(ce->name, base, baselen)) {
+			it->entry_count = 1;
+			oidcpy(&it->oid, &ce->oid);
+			return 1;
+		}
+	}
+
 	if (0 <= it->entry_count && has_object_file(&it->oid))
 		return it->entry_count;
 

index 30c1a11fd62d..56313e805d9d 100644
@@ -180,7 +180,11 @@ int convert_to_sparse(struct index_state *istate)
 	istate->cache_nr = convert_to_sparse_rec(istate,
 						 0, 0, istate->cache_nr,
 						 "", 0, istate->cache_tree);
-	istate->drop_cache_tree = 1;
+
+	/* Clear and recompute the cache-tree */
+	cache_tree_free(&istate->cache_tree);
+	cache_tree_update(istate, 0);
+
 	istate->sparse_index = 1;
 	trace2_region_leave("index", "convert_to_sparse", istate->repo);
 	return 0;

@@ -281,5 +285,9 @@ void ensure_full_index(struct index_state *istate)
 	strbuf_release(&base);
 	free(full);
 
+	/* Clear and recompute the cache-tree */
+	cache_tree_free(&istate->cache_tree);
+	cache_tree_update(istate, 0);
+
 	trace2_region_leave("index", "ensure_full_index", istate->repo);
 }

gitgitgadget

From: Derrick Stolee <[email protected]>

The cache_tree_verify() method is run when GIT_TEST_CHECK_CACHE_TREE is enabled, which it is by default in the test suite. The logic must be adjusted for the presence of these directory entries.

For now, leave the test as a simple check for whether the directory entry is sparse. Do not go any further until needed.

This allows us to re-enable GIT_TEST_CHECK_CACHE_TREE in t1092-sparse-checkout-compatibility.sh. Further, p2000-sparse-operations.sh uses the test suite and hence this is enabled for all tests. We need to integrate with it before we run our performance tests with a sparse-index.

---
 cache-tree.c                             | 19 +++++++++++++++++++
 t/t1092-sparse-checkout-compatibility.sh |  3 ---
 2 files changed, 19 insertions(+), 3 deletions(-)

index 950a9615db8f..11bf1fcae6e1 100644
@@ -808,6 +808,19 @@ int cache_tree_matches_traversal(struct cache_tree *root,
 	return 0;
 }
 
+static void verify_one_sparse(struct repository *r,
+			      struct index_state *istate,
+			      struct cache_tree *it,
+			      struct strbuf *path,
+			      int pos)
+{
+	struct cache_entry *ce = istate->cache[pos];
+
+	if (!S_ISSPARSEDIR(ce->ce_mode))
+		BUG("directory '%s' is present in index, but not sparse",
+		    path->buf);
+}
+
 static void verify_one(struct repository *r,
 		       struct index_state *istate,
 		       struct cache_tree *it,

@@ -830,6 +843,12 @@ static void verify_one(struct repository *r,
 
 	if (path->len) {
 		pos = index_name_pos(istate, path->buf, path->len);
+
+		if (pos >= 0) {
+			verify_one_sparse(r, istate, it, path, pos);
+			return;
+		}
+
 		pos = -pos - 1;
 	} else {
 		pos = 0;

index f14dc48924d2..d97bf9b64527 100755
@@ -2,9 +2,6 @@
 
 test_description='compare full workdir to sparse workdir'
 
-# The verify_cache_tree() check is not sparse-aware (yet).
-# So, disable the check until that integration is complete.
-GIT_TEST_CHECK_CACHE_TREE=0
 GIT_TEST_SPLIT_INDEX=0
 GIT_TEST_SPARSE_INDEX=
 

gitgitgadget

From: Derrick Stolee <[email protected]>

p2000-sparse-operations.sh compares different Git commands in repositories with many files at HEAD but using sparse-checkout to focus on a small portion of those files.

Add extra copies of the repository that use the sparse-index format so we can track how that affects the performance of different commands.

At this point in time, the sparse-index is 100% overhead from the CPU front, and this is measurable in these tests:

Test
---------------------------------------------------------------

2000.2: git status (full-index-v3)              0.59(0.51+0.12)
2000.3: git status (full-index-v4)              0.59(0.52+0.11)
2000.4: git status (sparse-index-v3)            1.40(1.32+0.12)
2000.5: git status (sparse-index-v4)            1.41(1.36+0.08)
2000.6: git add -A (full-index-v3)              2.32(1.97+0.19)
2000.7: git add -A (full-index-v4)              2.17(1.92+0.14)
2000.8: git add -A (sparse-index-v3)            2.31(2.21+0.15)
2000.9: git add -A (sparse-index-v4)            2.30(2.20+0.13)
2000.10: git add . (full-index-v3)              2.39(2.02+0.20)
2000.11: git add . (full-index-v4)              2.20(1.94+0.16)
2000.12: git add . (sparse-index-v3)            2.36(2.27+0.12)
2000.13: git add . (sparse-index-v4)            2.33(2.21+0.16)
2000.14: git commit -a -m A (full-index-v3)     2.47(2.12+0.20)
2000.15: git commit -a -m A (full-index-v4)     2.26(2.00+0.17)
2000.16: git commit -a -m A (sparse-index-v3)   3.01(2.92+0.16)
2000.17: git commit -a -m A (sparse-index-v4)   3.01(2.94+0.15)

Note that there is very little difference between the v3 and v4 index formats when the sparse-index is enabled. This is primarily due to the fact that the relative file sizes are the same, and the command time is mostly taken up by parsing tree objects to expand the sparse index into a full one.

With the current file layout, the index file sizes are given by this table:

       |  full index | sparse index |
       +-------------+--------------+
    v3 |     108 MiB |      1.6 MiB |
    v4 |      80 MiB |      1.2 MiB |

Future updates will improve the performance of Git commands when the index is sparse.

---
 t/perf/p2000-sparse-operations.sh | 19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)

index 2fbc81b22119..e527316e66d6 100755
@@ -60,12 +60,29 @@ test_expect_success 'setup repo and indexes' '
 		git sparse-checkout set $SPARSE_CONE &&
 		git config index.version 4 &&
 		git update-index --index-version=4
+	) &&
+	git -c core.sparseCheckoutCone=true clone --branch=wide --sparse . sparse-index-v3 &&
+	(
+		cd sparse-index-v3 &&
+		git sparse-checkout init --cone --sparse-index &&
+		git sparse-checkout set $SPARSE_CONE &&
+		git config index.version 3 &&
+		git update-index --index-version=3
+	) &&
+	git -c core.sparseCheckoutCone=true clone --branch=wide --sparse . sparse-index-v4 &&
+	(
+		cd sparse-index-v4 &&
+		git sparse-checkout init --cone --sparse-index &&
+		git sparse-checkout set $SPARSE_CONE &&
+		git config index.version 4 &&
+		git update-index --index-version=4
 	)
 '
 
 test_perf_on_all () {
 	command="$@"
-	for repo in full-index-v3 full-index-v4
+	for repo in full-index-v3 full-index-v4 \
+		    sparse-index-v3 sparse-index-v4
 	do
 		test_perf "$command ($repo)" "
 			(

gitgitgadget

On 3/16/2021 12:42 PM, Derrick Stolee via GitGitGadget wrote:> Updates in V3

Junio, I wanted to call your attention to this change in base.

Here is the relevant part of the range-diff:

Thanks,
-Stolee

I've read through the range-diff. Sorry for not spotting the conflict with Ævar's series (that I also reviewed). Anyway, my Reviewed-by from the last series still holds.

Thanks. I expect ab/read-tree would be rerolled at least one more time, if only to straighten out the "oops #5 was screwy, let's patch it up on top with three more steps", but I do not expect the end state would be all that different, so tentatively I'll queue these patches on top of the latest iteration of the topic for now and hope that the other topic will be updated soonish.

Thanks. I'm grateful that it can spend some time in 'seen' if only to avoid these conflicts in the meantime.

I'm waiting for that reroll of ab/read-tree before updating this version with the feedback from v3.

Thanks,
-Stolee

Here is the first full patch series submission coming out of the sparse-index RFC [1].

[1]
https://lore.kernel.org/git/[email protected]/

I won't waste too much space here, because PATCH 1 includes a sizeable design document that describes the feature, the reasoning behind it, and my plan for getting this implemented widely throughout the codebase.

There are some new things here that were not in the RFC:

* Design doc and format updates. (Patch 1)
* Performance test script. (Patches 2 and 20)

Notably missing in this series from the RFC:

* The mega-patch inserting ensure_full_index() throughout the codebase. That will be a follow-up series to this one.
* The integrations with git status and git add to demonstrate the improved performance. Those will also appear in their own series later.

I plan to keep my latest work in this area in my 'sparse-index/wip' branch [2]. It includes all of the work from the RFC right now, updated with the work from this series.

[2] https://github.com/derrickstolee/git/tree/sparse-index/wip

Updates in V4
=============

* Rebased onto the latest copy of ab/read-tree.
* Updated the design document as per Junio's comments.
* Updated the submodule handling in the performance test.
* Followed up on some other review from Ævar, mostly style or commit message things.

Updates in V3
=============

For this version, I took Ævar's latest patches and applied them to v2.31.0 and rebased this series on top. It uses his new "read_tree_at()" helper and the associated changes to the function pointer type.

* Fixed more typos. Thanks Martin and Elijah!
* Updated the test_sparse_match() macro to use "$@" instead of $*
* Added a test that git sparse-checkout init --no-sparse-index rewrites the index to be full.

Updates in V2
=============

* Various typos and awkward grammar is fixed.
* Cleaned up unnecessary commands in p2000-sparse-operations.sh
* Added a comment to the sparse_index member of struct index_state.
* Used tree_type, commit_type, and blob_type in test-read-cache.c.

Thanks, -Stolee

Derrick Stolee (20):
sparse-index: design doc and format update t/perf: add performance test for sparse operations
t1092: clean up script quoting
sparse-index: add guard to ensure full index
sparse-index: implement ensure_full_index()
t1092: compare sparse-checkout to sparse-index
test-read-cache: print cache entries with --table
test-tool: don't force full index
unpack-trees: ensure full index
sparse-checkout: hold pattern list in index
sparse-index: convert from full to sparse
submodule: sparse-index should not collapse links
unpack-trees: allow sparse directories
sparse-index: check index conversion happens
sparse-index: create extension for compatibility
sparse-checkout: toggle sparse index from builtin
sparse-checkout: disable sparse-index
cache-tree: integrate with sparse directory entries
sparse-index: loose integration with cache_tree_verify()
p2000: add sparse-index repos

 Documentation/config/extensions.txt      |   8 +
 Documentation/git-sparse-checkout.txt    |  14 ++
 Documentation/technical/index-format.txt |   7 +
 Documentation/technical/sparse-index.txt | 174 ++++++++++++++
 Makefile                                 |   1 +
 builtin/sparse-checkout.c                |  44 +++-
 cache-tree.c                             |  40 ++++
 cache.h                                  |  18 +-
 read-cache.c                             |  35 ++-
 repo-settings.c                          |  15 ++
 repository.c                             |  11 +-
 repository.h                             |   3 +
 setup.c                                  |   3 +
 sparse-index.c                           | 293 +++++++++++++++++++++++
 sparse-index.h                           |  11 +
 t/README                                 |   3 +
 t/helper/test-read-cache.c               |  66 ++++-
 t/perf/p2000-sparse-operations.sh        | 101 ++++++++
 t/t1091-sparse-checkout-builtin.sh       |  13 +
 t/t1092-sparse-checkout-compatibility.sh | 143 +++++++++--
 unpack-trees.c                           |  17 +-
 21 files changed, 980 insertions(+), 40 deletions(-)
 create mode 100644 Documentation/technical/sparse-index.txt
 create mode 100644 sparse-index.c
 create mode 100644 sparse-index.h
 create mode 100755 t/perf/p2000-sparse-operations.sh

base-commit: 47957485b3b731a7860e0554d2bd12c0dce1c75a
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-883%2Fderrickstolee%2Fsparse-index%2Fformat-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-883/derrickstolee/sparse-index/format-v4
Pull-Request: https://github.com/gitgitgadget/git/pull/883

Range-diff vs v3:

1: 62ac13945bec ! 1: 6426a5c60e53 sparse-index: design doc and format update
@@ Documentation/technical/index-format.txt: Git index format
+ is enabled in cone mode (core.sparseCheckoutCone is enabled) and the
+ extensions.sparseIndex extension is enabled, then the index may
+ contain entries for directories outside of the sparse-checkout definition.
-+ These entries have mode 0040000, include the SKIP_WORKTREE bit, and ++ These entries have mode 040000, include the SKIP_WORKTREE bit, and
+ the path ends in a directory separator.
+
32-bit ctime seconds, the last time a file's metadata changed
@@ Documentation/technical/sparse-index.txt (new)
+core.sparseCheckoutCone, allow for very fast pattern matching to +discover which files at HEAD belong in the sparse-checkout cone.
+
-+Three important scale dimensions for a Git worktree are:
++Three important scale dimensions for a Git working directory are:
+
+* HEAD: How many files are present at HEAD?
+
@@ Documentation/technical/sparse-index.txt (new)
+
+These dimensions are ordered by their magnitude: users (typically) modify +fewer files than are populated, and we can only populate files at HEAD.
-+These dimensions are also ordered by how expensive they are per item: it -+is expensive to detect a modified file than it is to write one that we -+know must be populated; changing HEAD only really requires updating the -+index.
+
+Problems occur if there is an extreme imbalance in these dimensions. For +example, if HEAD contains millions of paths but the populated set has
@@ Documentation/technical/sparse-index.txt (new)
+At time of writing, sparse-directory entries violate expectations about the +index format and its in-memory data structure. There are many consumers in +the codebase that expect to iterate through all of the index entries and
-+see only files. In addition, they expect to see all files at HEAD. One -+way to handle this is to parse trees to replace a sparse-directory entry -+with all of the files within that tree as the index is loaded. However, -+parsing trees is slower than parsing the index format, so that is a slower -+operation than if we left the index alone.
++see only files. In fact, these loops expect to see a reference to every ++staged file. One way to handle this is to parse trees to replace a ++sparse-directory entry with all of the files within that tree as the index ++is loaded. However, parsing trees is slower than parsing the index format, ++so that is a slower operation than if we left the index alone. The plan is ++to make all of these integrations "sparse aware" so this expansion through ++tree parsing is unnecessary and they use fewer resources than when using a ++full index.
+
+The implementation plan below follows four phases to slowly integrate with +the sparse-index. The intention is to incrementally update Git commands to
@@ Documentation/technical/sparse-index.txt (new)
+data structure can operate with its current assumption of every file at +HEAD.
+
-+At first, every index parse will expand the sparse-directory entries into -+the full list of paths at HEAD. This will be slower in all cases. The -+only noticable change in behavior will be that the serialized index file -+contains sparse-directory entries.
++At first, every index parse will call a helper method, ++ensure_full_index(), which scans the index for sparse-directory entries ++(pointing to trees) and replaces them with the full list of paths (with ++blob contents) by parsing tree objects. This will be slower in all cases. ++The only noticeable change in behavior will be that the serialized index ++file contains sparse-directory entries.
+
+To start, we use a new repository extension, extensions.sparseIndex, to +allow inserting sparse-directory entries into indexes with file format
2: d2197e895e4d ! 2: 7eabc1d0586c t/perf: add performance test for sparse operations

     @@ t/perf/p2000-sparse-operations.sh (new)
      +
      +test_expect_success 'setup repo and indexes' '
      +	git reset --hard HEAD &&
     ++
      +	# Remove submodules from the example repo, because our
     -+	# duplication of the entire repo creates an unlikly data shape.
     -+	git config --file .gitmodules --get-regexp "submodule.*.path" >modules &&
     -+	git rm -f .gitmodules &&
     -+	for module in $(awk "{print \$2}" modules)
     -+	do
     -+		git rm $module || return 1
     -+	done &&
     -+	git commit -m "remove submodules" &&
     ++	# duplication of the entire repo creates an unlikely data shape.
     ++	if git config --file .gitmodules --get-regexp "submodule.*.path" >modules
     ++	then
     ++		git rm $(awk "{print \$2}" modules) &&
     ++		git commit -m "remove submodules" || return 1
     ++	fi &&
      +
      +	echo bogus >a &&
      +	cp a b &&

3: d3cfd34b8418 ! 3: c9e21d78ecba t1092: clean up script quoting
@@ Commit message
t1092: clean up script quoting

This test was introduced in 19a0acc83e4 (t1092: test interesting
- sparse-checkout scenarios, 2021-01-23), but these issues with quoting
- were not noticed until starting this follow-up series. The old mechanism
- would drop quoting such as in
+ sparse-checkout scenarios, 2021-01-23), but it contains issues with quoting
+ that were not noticed until starting this follow-up series. The old
+ mechanism would drop quoting such as in

test_all_match git commit -m "touch README.md"

  4:  4472118cf903 =  4:  03cdde756563 sparse-index: add guard to ensure full index
  5:  99292cdbaae4 =  5:  6b3b6d86385d sparse-index: implement ensure_full_index()
  6:  fae5663a17bb =  6:  7f67adba0498 t1092: compare sparse-checkout to sparse-index
  7:  dffe8821fde2 !  7:  7ebd9570b1ad test-read-cache: print cache entries with --table

@@ Commit message
a sparse-index. Further, 'git ls-tree' does not use a trailing directory separator for its tree rows.

- This does not print the stat() information for the blobs. That could be
+ This does not print the stat() information for the blobs. That will be
added in a future change with another option. The tests that are added in the next few changes care only about the object types and IDs.
+ However, this future need for full index information justifies the need
+ for this test helper over extending a user-facing feature, such as 'git
+ ls-files'.

To make the option parsing slightly more robust, wrap the string comparisons in a loop adapted from test-dir-iterator.c.

  8:  f4ad081f25bb =  8:  db7bbd06dbcc test-tool: don't force full index
  9:  4780076a50df =  9:  3ddd5e794b5e unpack-trees: ensure full index
 10:  33fdba2b8cfd = 10:  7308c87697f1 sparse-checkout: hold pattern list in index
 11:  e41b14e03ebb ! 11:  7c10d653ca6b sparse-index: convert from full to sparse
     @@ cache.h: static inline unsigned int create_ce_mode(unsigned int mode)
       {
       	if (S_ISLNK(mode))
       		return S_IFLNK;
     -+	if (mode == S_IFDIR)
     ++	if (S_ISSPARSEDIR(mode))
      +		return S_IFDIR;
       	if (S_ISDIR(mode) || S_ISGITLINK(mode))
       		return S_IFGITLINK;
 12:  b77cd6b02265 = 12:  6db36f33e960 submodule: sparse-index should not collapse links
 13:  4000c5cdd4cf ! 13:  d24bd3348d98 unpack-trees: allow sparse directories
     @@ unpack-trees.c: static int index_pos_by_traverse_info(struct name_entry *names,
      +		if (!o->src_index->sparse_index ||
      +		    !(o->src_index->cache[pos]->ce_flags & CE_SKIP_WORKTREE))
      +			BUG("This is a directory and should not exist in index");
     -+	} else
     ++	} else {
      +		pos = -pos - 1;
     ++	}
       	if (pos >= o->src_index->cache_nr ||
       	    !starts_with(o->src_index->cache[pos]->name, name.buf) ||
       	    (pos > 0 && starts_with(o->src_index->cache[pos-1]->name, name.buf)))
 14:  1a2be38b2ca7 = 14:  08d9f5f3c0d1 sparse-index: check index conversion happens
 15:  f89891b0ae4e = 15:  6f38cef196b0 sparse-index: create extension for compatibility
 16:  bd703c76c859 = 16:  923081e7e079 sparse-checkout: toggle sparse index from builtin
 17:  598557f90a2a = 17:  6f1ad72c390d sparse-checkout: disable sparse-index
 18:  c2d0c17db31a = 18:  bd94e6b7d089 cache-tree: integrate with sparse directory entries
 19:  6fdd9323c14e = 19:  e7190376b806 sparse-index: loose integration with cache_tree_verify()
 20:  3db06ac46dd5 = 20:  bcf0a58eb38c p2000: add sparse-index repos

gitgitgadget

From: Derrick Stolee <[email protected]>

This begins a long effort to update the index format to allow sparse directory entries. This should result in a significant improvement to Git commands when HEAD contains millions of files, but the user has selected many fewer files to keep in their sparse-checkout definition.

Currently, the index format is only updated in the presence of extensions.sparseIndex instead of increasing a file format version number. This is temporary, and index v5 is part of the plan for future work in this area.

The design document details many of the reasons for embarking on this work, and also the plan for completing it safely.

---
 Documentation/technical/index-format.txt |   7 +
 Documentation/technical/sparse-index.txt | 174 +++++++++++++++++++++++
 2 files changed, 181 insertions(+)
 create mode 100644 Documentation/technical/sparse-index.txt

index d363a71c37ec..3b74c05647db 100644
@@ -44,6 +44,13 @@ Git index format
   localization, no special casing of directory separator '/'). Entries
   with the same name are sorted by their stage field.
 
+  An index entry typically represents a file. However, if sparse-checkout
+  is enabled in cone mode (`core.sparseCheckoutCone` is enabled) and the
+  `extensions.sparseIndex` extension is enabled, then the index may
+  contain entries for directories outside of the sparse-checkout definition.
+  These entries have mode `040000`, include the `SKIP_WORKTREE` bit, and
+  the path ends in a directory separator.
+
   32-bit ctime seconds, the last time a file's metadata changed
     this is stat(2) data
 

gitgitgadget

Yeah, the index extension mechanism was designed with optional and required kinds because we wanted to support exactly a use case like this one.

Thanks for pointing it out.

Ok, so let me be sure I understand the request, as I believe it is a very good one:

Using a REQUIRED index extension that says "this index has sparse-directory entries" will allow tools that don't touch the index to be compatible with repos using the sparse-index, while also avoiding a new index version.

I'll work on this right away. Thanks!
-Stolee

From: Derrick Stolee <[email protected]>

Create a test script that takes the default performance test (the Git codebase) and multiplies it by 256 using four layers of duplicated trees of width four. This results in nearly one million blob entries in the index. Then, we can clone this repository with sparse-checkout patterns that demonstrate four copies of the initial repository. Each clone will use a different index format or mode so peformance can be tested across the different options.

Note that the initial repo is stripped of submodules before doing the copies. This preserves the expected data shape of the sparse index, because directories containing submodules are not collapsed to a sparse directory entry.

Run a few Git commands on these clones, especially those that use the index (status, add, commit).

Here are the results on my Linux machine:

Test
--------------------------------------------------------------

2000.2: git status (full-index-v3)             0.37(0.30+0.09)
2000.3: git status (full-index-v4)             0.39(0.32+0.10)
2000.4: git add -A (full-index-v3)             1.42(1.06+0.20)
2000.5: git add -A (full-index-v4)             1.26(0.98+0.16)
2000.6: git add . (full-index-v3)              1.40(1.04+0.18)
2000.7: git add . (full-index-v4)              1.26(0.98+0.17)
2000.8: git commit -a -m A (full-index-v3)     1.42(1.11+0.16)
2000.9: git commit -a -m A (full-index-v4)     1.33(1.08+0.16)

It is perhaps noteworthy that there is an improvement when using index version 4. This is because the v3 index uses 108 MiB while the v4 index uses 80 MiB. Since the repeated portions of the directories are very short (f3/f1/f2, for example) this ratio is less pronounced than in similarly-sized real repositories.

---
 t/perf/p2000-sparse-operations.sh | 84 +++++++++++++++++++++++++++++++
 1 file changed, 84 insertions(+)
 create mode 100755 t/perf/p2000-sparse-operations.sh

new file mode 100755
index 000000000000..dddd527b6330
@@ -0,0 +1,84 @@
+#!/bin/sh
+
+test_description="test performance of Git operations using the index"
+
+. ./perf-lib.sh
+
+test_perf_default_repo
+
+SPARSE_CONE=f2/f4/f1
+
+test_expect_success 'setup repo and indexes' '
+	git reset --hard HEAD &&
+
+	# Remove submodules from the example repo, because our
+	# duplication of the entire repo creates an unlikely data shape.
+	if git config --file .gitmodules --get-regexp "submodule.*.path" >modules
+	then
+		git rm $(awk "{print \$2}" modules) &&
+		git commit -m "remove submodules" || return 1
+	fi &&
+
+	echo bogus >a &&
+	cp a b &&
+	git add a b &&
+	git commit -m "level 0" &&
+	BLOB=$(git rev-parse HEAD:a) &&
+	OLD_COMMIT=$(git rev-parse HEAD) &&
+	OLD_TREE=$(git rev-parse HEAD^{tree}) &&
+
+	for i in $(test_seq 1 4)
+	do
+		cat >in <<-EOF &&
+			100755 blob $BLOB	a
+			040000 tree $OLD_TREE	f1
+			040000 tree $OLD_TREE	f2
+			040000 tree $OLD_TREE	f3
+			040000 tree $OLD_TREE	f4
+		EOF
+		NEW_TREE=$(git mktree <in) &&
+		NEW_COMMIT=$(git commit-tree $NEW_TREE -p $OLD_COMMIT -m "level $i") &&
+		OLD_TREE=$NEW_TREE &&
+		OLD_COMMIT=$NEW_COMMIT || return 1
+	done &&
+
+	git sparse-checkout init --cone &&
+	git branch -f wide $OLD_COMMIT &&
+	git -c core.sparseCheckoutCone=true clone --branch=wide --sparse . full-index-v3 &&
+	(
+		cd full-index-v3 &&
+		git sparse-checkout init --cone &&
+		git sparse-checkout set $SPARSE_CONE &&
+		git config index.version 3 &&
+		git update-index --index-version=3
+	) &&
+	git -c core.sparseCheckoutCone=true clone --branch=wide --sparse . full-index-v4 &&
+	(
+		cd full-index-v4 &&
+		git sparse-checkout init --cone &&
+		git sparse-checkout set $SPARSE_CONE &&
+		git config index.version 4 &&
+		git update-index --index-version=4
+	)
+'
+
+test_perf_on_all () {
+	command="$@"
+	for repo in full-index-v3 full-index-v4
+	do
+		test_perf "$command ($repo)" "
+			(
+				cd $repo &&
+				echo >>$SPARSE_CONE/a &&
+				$command
+			)
+		"
+	done
+}
+
+test_perf_on_all git status
+test_perf_on_all git add -A
+test_perf_on_all git add .
+test_perf_on_all git commit -a -m A
+
+test_done

gitgitgadget

From: Derrick Stolee <[email protected]>

This test was introduced in 19a0acc83e4 (t1092: test interesting sparse-checkout scenarios, 2021-01-23), but it contains issues with quoting that were not noticed until starting this follow-up series. The old mechanism would drop quoting such as in

test_all_match git commit -m "touch README.md"

The above happened to work because README.md is a file in the repository, so 'git commit -m touch REAMDE.md' would succeed by accident.

Other cases included quoting for no good reason, so clean that up now.

---
 t/t1092-sparse-checkout-compatibility.sh | 20 ++++++++++----------
 1 file changed, 10 insertions(+), 10 deletions(-)

index 8cd3e5a8d227..3725d3997e70 100755
@@ -96,20 +96,20 @@ init_repos () {
 run_on_sparse () {
 	(
 		cd sparse-checkout &&
-		$* >../sparse-checkout-out 2>../sparse-checkout-err
+		"$@" >../sparse-checkout-out 2>../sparse-checkout-err
 	)
 }
 
 run_on_all () {
 	(
 		cd full-checkout &&
-		$* >../full-checkout-out 2>../full-checkout-err
+		"$@" >../full-checkout-out 2>../full-checkout-err
 	) &&
-	run_on_sparse $*
+	run_on_sparse "$@"
 }
 
 test_all_match () {
-	run_on_all $* &&
+	run_on_all "$@" &&
 	test_cmp full-checkout-out sparse-checkout-out &&
 	test_cmp full-checkout-err sparse-checkout-err
 }

@@ -119,7 +119,7 @@ test_expect_success 'status with options' '
 	test_all_match git status --porcelain=v2 &&
 	test_all_match git status --porcelain=v2 -z -u &&
 	test_all_match git status --porcelain=v2 -uno &&
-	run_on_all "touch README.md" &&
+	run_on_all touch README.md &&
 	test_all_match git status --porcelain=v2 &&
 	test_all_match git status --porcelain=v2 -z -u &&
 	test_all_match git status --porcelain=v2 -uno &&

@@ -135,7 +135,7 @@ test_expect_success 'add, commit, checkout' '
 	write_script edit-contents <<-\EOF &&
 	echo text >>$1
 	EOF
-	run_on_all "../edit-contents README.md" &&
+	run_on_all ../edit-contents README.md &&
 
 	test_all_match git add README.md &&
 	test_all_match git status --porcelain=v2 &&

@@ -144,7 +144,7 @@ test_expect_success 'add, commit, checkout' '
 	test_all_match git checkout HEAD~1 &&
 	test_all_match git checkout - &&
 
-	run_on_all "../edit-contents README.md" &&
+	run_on_all ../edit-contents README.md &&
 
 	test_all_match git add -A &&
 	test_all_match git status --porcelain=v2 &&

@@ -153,7 +153,7 @@ test_expect_success 'add, commit, checkout' '
 	test_all_match git checkout HEAD~1 &&
 	test_all_match git checkout - &&
 
-	run_on_all "../edit-contents deep/newfile" &&
+	run_on_all ../edit-contents deep/newfile &&
 
 	test_all_match git status --porcelain=v2 -uno &&
 	test_all_match git status --porcelain=v2 &&

@@ -186,7 +186,7 @@ test_expect_success 'diff --staged' '
 	write_script edit-contents <<-\EOF &&
 	echo text >>README.md
 	EOF
-	run_on_all "../edit-contents" &&
+	run_on_all ../edit-contents &&
 
 	test_all_match git diff &&
 	test_all_match git diff --staged &&

@@ -280,7 +280,7 @@ test_expect_success 'clean' '
 	echo bogus >>.gitignore &&
 	run_on_all cp ../.gitignore . &&
 	test_all_match git add .gitignore &&
-	test_all_match git commit -m ignore-bogus-files &&
+	test_all_match git commit -m "ignore bogus files" &&
 
 	run_on_sparse mkdir folder1 &&
 	run_on_all touch folder1/bogus &&

gitgitgadget

From: Derrick Stolee <[email protected]>

Upcoming changes will introduce modifications to the index format that allow sparse directories. It will be useful to have a mechanism for converting those sparse index files into full indexes by walking the tree at those sparse directories. Name this method ensure_full_index() as it will guarantee that the index is fully expanded.

This method is not implemented yet, and instead we focus on the scaffolding to declare it and call it at the appropriate time.

Add a 'command_requires_full_index' member to struct repo_settings. This will be an indicator that we need the index in full mode to do certain index operations. This starts as being true for every command, then we will set it to false as some commands integrate with sparse indexes.

If 'command_requires_full_index' is true, then we will immediately expand a sparse index to a full one upon reading from disk. This suffices for now, but we will want to add more callers to ensure_full_index() later.

---
 Makefile        |  1 +
 repo-settings.c |  8 ++++++++
 repository.c    | 11 ++++++++++-
 repository.h    |  2 ++
 sparse-index.c  |  8 ++++++++
 sparse-index.h  |  7 +++++++
 6 files changed, 36 insertions(+), 1 deletion(-)
 create mode 100644 sparse-index.c
 create mode 100644 sparse-index.h

index dfb0f1000fa3..89b1d5374107 100644
@@ -985,6 +985,7 @@ LIB_OBJS += setup.o
 LIB_OBJS += shallow.o
 LIB_OBJS += sideband.o
 LIB_OBJS += sigchain.o
+LIB_OBJS += sparse-index.o
 LIB_OBJS += split-index.o
 LIB_OBJS += stable-qsort.o
 LIB_OBJS += strbuf.o

index f7fff0f5ab83..d63569e4041e 100644
@@ -77,4 +77,12 @@ void prepare_repo_settings(struct repository *r)
 		UPDATE_DEFAULT_BOOL(r->settings.core_untracked_cache, UNTRACKED_CACHE_KEEP);
 
 	UPDATE_DEFAULT_BOOL(r->settings.fetch_negotiation_algorithm, FETCH_NEGOTIATION_DEFAULT);
+
+	/*
+	 * This setting guards all index reads to require a full index
+	 * over a sparse index. After suitable guards are placed in the
+	 * codebase around uses of the index, this setting will be
+	 * removed.
+	 */
+	r->settings.command_requires_full_index = 1;
 }

index c98298acd017..a8acae002f71 100644
@@ -10,6 +10,7 @@
 #include "object.h"
 #include "lockfile.h"
 #include "submodule-config.h"
+#include "sparse-index.h"
 
 /* The main repository */
 static struct repository the_repo;

@@ -261,6 +262,8 @@ void repo_clear(struct repository *repo)
 
 int repo_read_index(struct repository *repo)
 {
+	int res;
+
 	if (!repo->index)
 		repo->index = xcalloc(1, sizeof(*repo->index));
 

@@ -270,7 +273,13 @@ int repo_read_index(struct repository *repo)
 	else if (repo->index->repo != repo)
 		BUG("repo's index should point back at itself");
 
-	return read_index_from(repo->index, repo->index_file, repo->gitdir);
+	res = read_index_from(repo->index, repo->index_file, repo->gitdir);
+
+	prepare_repo_settings(repo);
+	if (repo->settings.command_requires_full_index)
+		ensure_full_index(repo->index);
+
+	return res;
 }
 
 int repo_hold_locked_index(struct repository *repo,

index b385ca3c94b6..e06a23015697 100644
@@ -41,6 +41,8 @@ struct repo_settings {
 	enum fetch_negotiation_setting fetch_negotiation_algorithm;
 
 	int core_multi_pack_index;
+
+	unsigned command_requires_full_index:1;
 };
 
 struct repository {

new file mode 100644
index 000000000000..82183ead563b
@@ -0,0 +1,8 @@
+#include "cache.h"
+#include "repository.h"
+#include "sparse-index.h"
+
+void ensure_full_index(struct index_state *istate)
+{
+	/* intentionally left blank */
+}

new file mode 100644
index 000000000000..09a20d036c46
@@ -0,0 +1,7 @@
+#ifndef SPARSE_INDEX_H__
+#define SPARSE_INDEX_H__
+
+struct index_state;
+void ensure_full_index(struct index_state *istate);
+
+#endif

gitgitgadget

From: Derrick Stolee <[email protected]>

We will mark an in-memory index_state as having sparse directory entries with the sparse_index bit. These currently cannot exist, but we will add a mechanism for collapsing a full index to a sparse one in a later change. That will happen at write time, so we must first allow parsing the format before writing it.

Commands or methods that require a full index in order to operate can call ensure_full_index() to expand that index in-memory. This requires parsing trees using that index's repository.

Sparse directory entries have a specific 'ce_mode' value. The macro S_ISSPARSEDIR(ce->ce_mode) can check if a cache_entry 'ce' has this type. This ce_mode is not possible with the existing index formats, so we don't also verify all properties of a sparse-directory entry, which are:

1. ce->ce_mode == 0040000
2. ce->flags & CE_SKIP_WORKTREE is true
3. ce->name[ce->namelen - 1] == '/' (ends in dir separator)
4. ce->oid references a tree object.

These are all semi-enforced in ensure_full_index() to some extent. Any deviation will cause a warning at minimum or a failure in the worst case.

---
 cache.h        | 13 ++++++-
 read-cache.c   |  9 +++++
 sparse-index.c | 98 +++++++++++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 118 insertions(+), 2 deletions(-)

index bb317abc91fb..136dd496c95d 100644
@@ -204,6 +204,8 @@ struct cache_entry {
 #error "CE_EXTENDED_FLAGS out of range"
 #endif
 
+#define S_ISSPARSEDIR(m) ((m) == S_IFDIR)
+
 /* Forward structure decls */
 struct pathspec;
 struct child_process;

@@ -319,7 +321,14 @@ struct index_state {
 		 drop_cache_tree : 1,
 		 updated_workdir : 1,
 		 updated_skipworktree : 1,
-		 fsmonitor_has_run_once : 1;
+		 fsmonitor_has_run_once : 1,
+
+		 /*
+		  * sparse_index == 1 when sparse-directory
+		  * entries exist. Requires sparse-checkout
+		  * in cone mode.
+		  */
+		 sparse_index : 1;
 	struct hashmap name_hash;
 	struct hashmap dir_hash;
 	struct object_id oid;

@@ -722,6 +731,8 @@ int read_index_from(struct index_state *, const char *path,
 		    const char *gitdir);
 int is_index_unborn(struct index_state *);
 
+void ensure_full_index(struct index_state *istate);
+
 /* For use with `write_locked_index()`. */
 #define COMMIT_LOCK		(1 << 0)
 #define SKIP_IF_UNCHANGED	(1 << 1)

index 1e9a50c6c734..dd3980c12b53 100644
@@ -101,6 +101,9 @@ static const char *alternate_index_output;
 
 static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)
 {
+	if (S_ISSPARSEDIR(ce->ce_mode))
+		istate->sparse_index = 1;
+
 	istate->cache[nr] = ce;
 	add_name_hash(istate, ce);
 }

@@ -2273,6 +2276,12 @@ int do_read_index(struct index_state *istate, const char *path, int must_exist)
 	trace2_data_intmax("index", the_repository, "read/cache_nr",
 			   istate->cache_nr);
 
+	if (!istate->repo)
+		istate->repo = the_repository;
+	prepare_repo_settings(istate->repo);
+	if (istate->repo->settings.command_requires_full_index)
+		ensure_full_index(istate);
+
 	return istate->cache_nr;
 
 unmap:

gitgitgadget

From: Derrick Stolee <[email protected]>

Add a new 'sparse-index' repo alongside the 'full-checkout' and 'sparse-checkout' repos in t1092-sparse-checkout-compatibility.sh. Also add run_on_sparse and test_sparse_match helpers. These helpers will be used when the sparse index is implemented.

Add the GIT_TEST_SPARSE_INDEX environment variable to enable the sparse-index by default. This can be enabled across all tests, but that will only affect cases where the sparse-checkout feature is enabled.

---
 t/README                                 |  3 +++
 t/t1092-sparse-checkout-compatibility.sh | 24 ++++++++++++++++++++----
 2 files changed, 23 insertions(+), 4 deletions(-)

index 593d4a4e270c..b98bc563aab5 100644
@@ -439,6 +439,9 @@ and "sha256".
 GIT_TEST_WRITE_REV_INDEX=<boolean>, when true enables the
 'pack.writeReverseIndex' setting.
 
+GIT_TEST_SPARSE_INDEX=<boolean>, when true enables index writes to use the
+sparse-index format by default.
+
 Naming Tests
 ------------
 

index 3725d3997e70..de5d8461c993 100755
@@ -7,6 +7,7 @@ test_description='compare full workdir to sparse workdir'
 test_expect_success 'setup' '
 	git init initial-repo &&
 	(
+		GIT_TEST_SPARSE_INDEX=0 &&
 		cd initial-repo &&
 		echo a >a &&
 		echo "after deep" >e &&

@@ -87,23 +88,32 @@ init_repos () {
 
 	cp -r initial-repo sparse-checkout &&
 	git -C sparse-checkout reset --hard &&
-	git -C sparse-checkout sparse-checkout init --cone &&
+
+	cp -r initial-repo sparse-index &&
+	git -C sparse-index reset --hard &&
 
 	# initialize sparse-checkout definitions
-	git -C sparse-checkout sparse-checkout set deep
+	git -C sparse-checkout sparse-checkout init --cone &&
+	git -C sparse-checkout sparse-checkout set deep &&
+	GIT_TEST_SPARSE_INDEX=1 git -C sparse-index sparse-checkout init --cone &&
+	GIT_TEST_SPARSE_INDEX=1 git -C sparse-index sparse-checkout set deep
 }
 
 run_on_sparse () {
 	(
 		cd sparse-checkout &&
-		"$@" >../sparse-checkout-out 2>../sparse-checkout-err
+		GIT_TEST_SPARSE_INDEX=0 "$@" >../sparse-checkout-out 2>../sparse-checkout-err
+	) &&
+	(
+		cd sparse-index &&
+		GIT_TEST_SPARSE_INDEX=1 "$@" >../sparse-index-out 2>../sparse-index-err
 	)
 }
 
 run_on_all () {
 	(
 		cd full-checkout &&
-		"$@" >../full-checkout-out 2>../full-checkout-err
+		GIT_TEST_SPARSE_INDEX=0 "$@" >../full-checkout-out 2>../full-checkout-err
 	) &&
 	run_on_sparse "$@"
 }

@@ -114,6 +124,12 @@ test_all_match () {
 	test_cmp full-checkout-err sparse-checkout-err
 }
 
+test_sparse_match () {
+	run_on_sparse "$@" &&
+	test_cmp sparse-checkout-out sparse-index-out &&
+	test_cmp sparse-checkout-err sparse-index-err
+}
+
 test_expect_success 'status with options' '
 	init_repos &&
 	test_all_match git status --porcelain=v2 &&

gitgitgadget

From: Derrick Stolee <[email protected]>

This table is helpful for discovering data in the index to ensure it is being written correctly, especially as we build and test the sparse-index. This table includes an output format similar to 'git ls-tree', but should not be compared to that directly. The biggest reasons are that 'git ls-tree' includes a tree entry for every subdirectory, even those that would not appear as a sparse directory in a sparse-index. Further, 'git ls-tree' does not use a trailing directory separator for its tree rows.

This does not print the stat() information for the blobs. That will be added in a future change with another option. The tests that are added in the next few changes care only about the object types and IDs. However, this future need for full index information justifies the need for this test helper over extending a user-facing feature, such as 'git ls-files'.

To make the option parsing slightly more robust, wrap the string comparisons in a loop adapted from test-dir-iterator.c.

Care must be taken with the final check for the 'cnt' variable. We continue the expectation that the numerical value is the final argument.

---
 t/helper/test-read-cache.c | 55 +++++++++++++++++++++++++++++++-------
 1 file changed, 45 insertions(+), 10 deletions(-)

index 244977a29bdf..6cfd8f2de71c 100644
@@ -1,36 +1,71 @@
 #include "test-tool.h"
 #include "cache.h"
 #include "config.h"
+#include "blob.h"
+#include "commit.h"
+#include "tree.h"
+
+static void print_cache_entry(struct cache_entry *ce)
+{
+	const char *type;
+	printf("%06o ", ce->ce_mode & 0177777);
+
+	if (S_ISSPARSEDIR(ce->ce_mode))
+		type = tree_type;
+	else if (S_ISGITLINK(ce->ce_mode))
+		type = commit_type;
+	else
+		type = blob_type;
+
+	printf("%s %s\t%s\n",
+	       type,
+	       oid_to_hex(&ce->oid),
+	       ce->name);
+}
+
+static void print_cache(struct index_state *istate)
+{
+	int i;
+	for (i = 0; i < istate->cache_nr; i++)
+		print_cache_entry(istate->cache[i]);
+}
 
 int cmd__read_cache(int argc, const char **argv)
 {
+	struct repository *r = the_repository;
 	int i, cnt = 1;
 	const char *name = NULL;
+	int table = 0;
 
-	if (argc > 1 && skip_prefix(argv[1], "--print-and-refresh=", &name)) {
-		argc--;
-		argv++;
+	for (++argv, --argc; *argv && starts_with(*argv, "--"); ++argv, --argc) {
+		if (skip_prefix(*argv, "--print-and-refresh=", &name))
+			continue;
+		if (!strcmp(*argv, "--table"))
+			table = 1;
 	}
 
-	if (argc == 2)
-		cnt = strtol(argv[1], NULL, 0);
+	if (argc == 1)
+		cnt = strtol(argv[0], NULL, 0);
 	setup_git_directory();
 	git_config(git_default_config, NULL);
+
 	for (i = 0; i < cnt; i++) {
-		read_cache();
+		repo_read_index(r);
 		if (name) {
 			int pos;
 
-			refresh_index(&the_index, REFRESH_QUIET,
+			refresh_index(r->index, REFRESH_QUIET,
 				      NULL, NULL, NULL);
-			pos = index_name_pos(&the_index, name, strlen(name));
+			pos = index_name_pos(r->index, name, strlen(name));
 			if (pos < 0)
 				die("%s not in index", name);
 			printf("%s is%s up to date\n", name,
-			       ce_uptodate(the_index.cache[pos]) ? "" : " not");
+			       ce_uptodate(r->index->cache[pos]) ? "" : " not");
 			write_file(name, "%d\n", i);
 		}
-		discard_cache();
+		if (table)
+			print_cache(r->index);
+		discard_index(r->index);
 	}
 	return 0;
 }

gitgitgadget

Is that stat() information that's going to be essential to grab in the same process that runs the "for (i = 0; i < istate->cache_nr; i++)" for-loop, or stat() information that could be grabbed as:

    git ls-files -z --stage | some-program-that-stats-all-listed-blobs

It's not so much that I still disagree as I feel like I'm missing something. I haven't gone through this topic with a fine toothed comb, so ...

If and when these patches land and I'm using this nascent sparse checkout support why wouldn't I want ls-files or another not-a-test-tool to support extracting this new information that's in the index?

That's why I sent the RFC patches at
https://lore.kernel.org/git/[email protected]/ to roll this functionality into ls-files.

Still, I think if there's a good reason for why we want this in the index but never want our plumbing to be able to dump it in some user-facing way I think just as a matter of reviewing this code it would be much simpler if it was in ls-files behind some git_env_bool("GIT_TEST_...") flag or something.

Or maybe I'm the only one who spends a lot of time with both ls-files.c and test-read-cache.c open while trying to review this trying to keep track of if and how this helper is and isn't subtly different from ls-files (as my RFC series shows, not really that different at all...). Especially with the really-just-ls-files-plus-one-thing tool mimicking ls-tree output, for reasons I still don't get...

I think even if you're set on not having this exposed in some builtin/*.c command this code would be much clearer based on some version of my
https://lore.kernel.org/git/[email protected]/
i.e. the part that isn't entirely deleting t/helper/test-read-cache.c, which would survive as t/helper/test-read-cache-sparse.c or something.

As that patch shows this code is needlessly convoluted because it's serving 3x wildly different in-tree use-cases. I don't see how the very small amount of de-duplication we're getting is worth the complexity.

At that point we don't need any care with the cnt variable, because we're not combining the fsmonitor and perf use-cases of reading the index in some loop with the ls-files-alike.

The point is not to find the stat() data from disk, but to ensure that the stat() data is correctly stored in the index (say, after converting an existing index from another format). This pipe strategy does not allow for that scenario.

And I recommend that you continue to pursue them as an independent series, but I'm not going to incorporate them into this one. I'm not going to distract from this internal data structure with changes to user-facing commands until I think it's ready to use. As the design document describes the plan, I don't expect this to be something I will recommend to users until most of "Phase 3" is complete, making the most common Git commands aware of a sparse index. (I expect to fast-track a prototype to willing users that covers that functionality while review continues on the mailing list.)

Making a change to a builtin is _forever_, and since the only purpose right now is to expose the data in a test environment, I don't want to adjust the builtin until either there is a real user need or the feature has otherwise stabilized. If you want to take on that responsibility, then please do.

Otherwise, I will need to eventually handle "git ls-files" being sparse-aware when eventually removing 'command_requires_full_index', (Phase 4) so that would be a good opportunity to adjust the expectations.

Thanks,
-Stolee

So a dump of ce->ce_stat_data, i.e. the same thing ls-files --debug prints out now, or...?

This series is 20 patches. Your current derrickstolee/sparse-index/wip is another 36, and from skimming those patches & your design doc those 56 seem to be partway into Phase I of IV.

So at the rate things tend to get reviewed / re-rolled & land in git.git it seems exceedingly likely that we'll have some part-way implementation of this for at least a major release or two. No?

Which is why I'm suggesting/asking if we shouldn't have something like this debugging helper as part of installed tooling, because people are going to try it, it's probably going to have bugs and do other weird things, and I'd rather not have to manually build some test-tool to debug some local sparse checkout somewhere.

That's just not the case, we have plenty of unstable debug-esque options in various built-in commands, in fact ls-files already has a --debug option whose docs say:

This is intended to show as much information as possible for manual inspection; the exact format may change at any time.

It was added in 84974217151 (ls-files: learn a debugging dump format, 2010-07-31) and "just tacks all available data from the cache onto each file's line" so in a way not adjusting it and using it would be a regression, after all this is new data in the cache, so it should print it :)

There's also PARSE_OPT_HIDDEN for other such in-tree use. Whatever the sanity/merits of me suggesting that this specific thing be in ls-files instead of a test-helper, it seems far fetched that something like that hidden behind a GIT_TEST_* env var (or hidden option, --debug etc.) is something we'd need to worry about backwards compatibility for.

So, whatever you think about the merits of including this functionality in ls-files I think your stance of this being a no-go for adding to the builtin is based on a false premise. It's fine to have unstable/transitory/debug output in the builtins. We just name & document them as such.

I also had some feedback in that series and on the earlier iteration that I think is appropriate to be incorporated into a re-roll of this one, which doesn't have anything to do with the question of whether we use ls-files or the helper in the tests. Such as us showing more stuff into the read-cache.c test-tool v.s. splitting it up making that code needlessly convoluted.

I don't see how recommending that I pursue that as an independent series is productive for anyone. So as you re-roll this I should submit another series on top to refactor your in-flight code & tests?

Either my suggestions are just bad, and we shouldn't do them at all, or it makes sense to incorporate relevant feedback in re-rolls. I'll let other reviewers draw their own conclusions on that.

That's not a snarky "I'm right" b.t.w., I may honestly be full of it on this particular topic.

But if those suggested changes are worth doing at all, then doing them in that way seems like a massive waste of time for everyone involved, or maybe I'm not getting what you're suggesting by pursuing them as an independent series.

At which point you'd be adjusting your tests that expect ls-tree format output to using ls-files output, instead of using ls-files-like output from the beginning?

At the end of this E-Mail is a patch on top that adds an undocumented --debug-sparse in addition to the existing --debug. Running that in the middle of one of your tests:

    $ ~/g/git/git ls-files --debug -- a folder1
    a
      ctime: 1616641434:474004002
      mtime: 1616641434:474004002
      dev: 2306     ino: 28576528
      uid: 1001     gid: 1001
      size: 8       flags: 0
    folder1/a
      ctime: 0:0
      mtime: 0:0
      dev: 0        ino: 0
      uid: 0        gid: 0
      size: 0       flags: 40000000
    $ ~/g/git/git ls-files --debug --debug-sparse -- a folder1
    a 
      ctime: 1616641434:474004002
      mtime: 1616641434:474004002
      dev: 2306     ino: 28576528
      uid: 1001     gid: 1001
      size: 8       flags: 0
    folder1/
      ctime: 0:0
      mtime: 0:0
      dev: 0        ino: 0
      uid: 0        gid: 0
      size: 0       flags: 40004000
    $ ~/g/git/git ls-files --stage -- a folder1
    100644 e79c5e8f964493290a409888d5413a737e8e5dd5 0       a
    100644 e79c5e8f964493290a409888d5413a737e8e5dd5 0       folder1/a
    $ ~/g/git/git ls-files --stage --debug-sparse -- a folder1
    100644 e79c5e8f964493290a409888d5413a737e8e5dd5 0       a
    040000 f203181537ff55dcf7896bf8c5b5c35af1514421 0       folder1/

I.e. it gives you everything your helper does and more with a trivial addition of a --debug-sparse (which we can later just remove, it's a debug option...).

See e.g. my recent 15c9649730d (grep/log: remove hidden --debug and --grep-debug options, 2021-01-26) which is already in a release, and AFAICT nobody has noticed or cared.

I don't know if that's the stat() information you wanted (your WIP branch doesn't have such a change), but presumably it either is the info you want, or ls-files's --debug would want to emit any such such info that's now missing too.

index 13bcc2d8473..e691512d4f8 100644
@@ -34,6 +34,7 @@ static int show_valid_bit;
 static int show_fsmonitor_bit;
 static int line_terminator = '\n';
 static int debug_mode;
+static int debug_sparse_mode;
 static int show_eol;
 static int recurse_submodules;
 static int skipping_duplicates;

@@ -242,9 +243,17 @@ static void show_ce(struct repository *repo, struct dir_struct *dir,
 		if (!show_stage) {
 			fputs(tag, stdout);
 		} else {
+			unsigned int mode = ce->ce_mode;
+			if (debug_sparse_mode && S_ISSPARSEDIR(mode))
+				/*
+				 * We could just do & 0177777 all the
+				 * time, just make it clear this is
+				 * for --debug-sparse.
+				 */
+				mode &= 0177777;
 			printf("%s%06o %s %d\t",
 			       tag,
-			       ce->ce_mode,
+			       mode,
 			       find_unique_abbrev(&ce->oid, abbrev),
 			       ce_stage(ce));
 		}

@@ -667,6 +676,7 @@ int cmd_ls_files(int argc, const char **argv, const char *cmd_prefix)
 			N_("pretend that paths removed since <tree-ish> are still present")),
 		OPT__ABBREV(&abbrev),
 		OPT_BOOL(0, "debug", &debug_mode, N_("show debugging data")),
+		OPT_BOOL(0, "debug-sparse", &debug_sparse_mode, N_("show sparse debugging data")),
 		OPT_BOOL(0, "deduplicate", &skipping_duplicates,
 			 N_("suppress duplicate entries")),
 		OPT_END()

@@ -681,9 +691,6 @@ int cmd_ls_files(int argc, const char **argv, const char *cmd_prefix)
 		prefix_len = strlen(prefix);
 	git_config(git_default_config, NULL);
 
-	if (repo_read_index(the_repository) < 0)
-		die("index file corrupt");
-
 	argc = parse_options(argc, argv, prefix, builtin_ls_files_options,
 			ls_files_usage, 0);
 	pl = add_pattern_list(&dir, EXC_CMDL, "--exclude option");

@@ -700,6 +707,10 @@ int cmd_ls_files(int argc, const char **argv, const char *cmd_prefix)
 		tag_skip_worktree = "S ";
 		tag_resolve_undo = "U ";
 	}
+	if (debug_sparse_mode) {
+		prepare_repo_settings(the_repository);
+		the_repository->settings.command_requires_full_index = 0;
+	}
 	if (show_modified || show_others || show_deleted || (dir.flags & DIR_SHOW_IGNORED) || show_killed)
 		require_work_tree = 1;
 	if (show_unmerged)

@@ -743,6 +754,12 @@ int cmd_ls_files(int argc, const char **argv, const char *cmd_prefix)
 		max_prefix = common_prefix(&pathspec);
 	max_prefix_len = get_common_prefix_len(max_prefix);
 
+	/*
+	 * Read the index after parse options etc. have had a chance
+	 * to die early.
+	 */
+	if (repo_read_index(the_repository) < 0)
+		die("index file corrupt");
 	prune_index(the_repository->index, max_prefix, max_prefix_len);
 
 	/* Treat unmatching pathspec elements as errors */

Hi,

...

I'm curious why you feel it's critical that this particular piece of debugging machinery needs to be prioritized early and exposed; in particular, I'm not sure I follow the "people are going to try it" assertion. Are you the one who is going to try it or are you going to give it to your users? If so, what do you need out of the debugging tool?

You are correct that this will span multiple releases; Stolee already said he was planning to be working on this for most of 2021. But just because pieces of the code exist and are shipped doesn't mean it'll be announced or supported. For example, the git-2.30 and git-2.31 release notes were completely silent about merge-ort. It existed in both releases; in fact, the version that ships in git-2.31, could theoretically be used successfully by the vast majority of users for their daily workflow. (But it does have known shortcomings and test failures so I definitely did *not* want it to be announced at that time.)

Well:
* you seem to be strongly opposed to test-read-cache.c containing
this code (though I don't quite follow why)
* Stolee seems to be strongly opposed to modifying
builtin/ls-files.c until he has time to think through how builtins should work.

So putting it in another test file that looks slightly duplicative of test-read-cache.c might indeed be a good way out of this conundrum. :-)

(I'm not opposed to any of the three solutions, I'm mostly chiming in here because I'm worried about possible bubbling frustration; see below.)

Your tone suggests some frustration; I have a suspicion there's some lack of understanding or misreading that has occurred (perhaps on my part too), and before that misunderstanding morphs into motive questioning, let me see if I might be able to help...

So far, you have advocated for:
A) Moving the checks to ls-files with a permanent new flag (--sparse)
B) Duplicating test-read-cache.c (which is admittedly pretty small)
and then modifying the duplicate to have the new behavior, or alternatively:
C) Just stating files to get the information
D) Creating new debug option(s) to ls-files so that end users can
use this in the next few releases before the feature is ready for prime time
You also mentioned you had read just part of the series.

Option D comes with the problem that it's not at all clear who these end-users are, why they want the option, or how we should design it. Personally, I'm totally onboard that ls-files should generally have the ability to show information in the index (e.g. if there are tree entries in addition to blob entries, it should be able to show both), but I'm not following the reasoning for why it needs to be there as part of the early stages of development of the sparse-index feature and who it's supposed to be helping in these next few releases.

The progression also suggests that Option B might have just been a step along the way and that you were advocating for Option D now. I think it'd be easy to miss that you still had option B open and considered it equivalently good to option D (or am I misreading?), much like you missed how option C wasn't even relevant to the problem at hand or option A would have introduced perpetual confusion as a mere duplicate of --stage (in the best case scenario, anyway). They're all easy misunderstandings.

I think that's a bit unfair; Stolee has been incorporating feedback. He even called out fixing up things at your suggestion in v4 of his re-roll.

I think you should instead read it as he has no idea why this needs to be exposed in ls-files, who these users are you are asserting will be using it, or how to cater for their needs. Shouldn't the person who implements this understand those pieces to avoid a massive waste of time?

I don't understand what you're getting at here. I was the one who requested Stolee make the output look like ls-trees in his original RFC series, so if there's a problem with this style of output, I'm to blame. But, what is exactly the problem? Old-style ls-files output just isn't relevant anymore. ls-tree prints four things: mode, type, hash, and filename. ls-files prints all of those except "type". The reason ls-files never included type before was because it was always "blob". This series changes that, and adds "tree" to the mix. Once you have different types included in the index, then ls-files has to print all the same fields that ls-tree does...so why not make it look similar?

The debugging machinery's already there, the question is why we have a need for duplicating code in-tree.

I just did some cursory review of this topic, and wondered why its tests couldn't use a builtin instead of (mostly) reinventing the wheel.

It seems to me that the reason for that state is based on a misunderstanding about what we would and wouldn't add to builtin/*.c, i.e. that we wouldn't have something like a --debug option, but as ls-files shows that's not a problem.

So my interest is twofold:

* Just a comment on "can we avoid this code duplication"

* The related one of not wanting to re-learn some custom test helper as (presumably) we get N number of large patch serieses on this topic, if it turns out that we can use an existing well-known tool with minimal changes.

I haven't understood the sparse index enough feature enough to know if anyone would ever want to run this --debug-sparse outside of the test suite.

Isn't extract info about its internal state going to be useful sooner than later in the scenarios where you'd care enough to run "ls-files --stage" now?

Maybe I've misunderstood this feature and it's going to be so transparent that nobody will ever have any reason to dump how it's working out of the index...

Yes, and that's fine. But if you'd been bending over backwards to add merge-ort to t/helper/ "because it's not ready yet" or something I'd have probably commented to the effect of "can't we just add it as part of builtins but not advertise it?" which is what you did :)

See above.

As noted above my reading of upthread is that those reasons basically boil down to not knowing "git ls-files --debug" exists, and that we can extend it.

FWIW I think that read-cache.c split is worth doing even if this series doesn't modify t/helper/read-cache.c.

The "this is for fsmonitor" and "this is for the perf test" use-cases are (as I think my RFC patch shows) clearer once they're split up.

Honestly more flabbergasted than anything, so I'm trying to clarify what the author thinks of this direction.

I mean it's fine if it's just a "I don't think this is important and don't want to spend time on it, but it seems like a good idea", in which case others have the option of re-rolling some of these patches if they care (at this point I wouldn't).

Or "this is just a bad idea for XYZ reason", which is also fine, and even more valuable to document for future work in the area.

But to have another series built on this with refactorings back and forth before code's landed on master just seems like needless churn.

I think s/advocated/read the series and sent an flow-of-thought not-ready-for-anything RFC patches on top/ would be more accurate :)

I.e. the A) --sparse thing was just reading the patch and seeing if ls-files couldn't be made to do this, but yes, having the documented --sparse interface might not make sense.

we discussed B) above.

C) Was a question to clarify what was meant with stat data, since it's an offhand comment in the commit message. Does it mean "stat after the fact" or "this will have a mode like ls-files --debug has now"?

Right now I'm just suggesting with D) that this might be rolled into the dev-only-not-for-end-users --debug mode.

We already are extracting the info at this early stage, just with a custom helper. All I'm suggesting right now is that the motivation for the custom helper is "this isn't for end users" then surely having a patch around 1/2 the size to add it to already reviewed/tested ls-files code under a --debug option makes more sense.

Especially since the upthread commit mentions wanting to incorporate stat() data. I'm not sure how exactly (there's no outstanding patches, even on a WIP branch for it, AFAICT), but most likely it's further duplication of data "ls-files --debug" already spews out.

So the patch would be 1/2 the size, and instead of saying "let's do stat stuff in the future" it would get it for free.

Or not, part of that's speculation on information that's just in Stolee's head. Hence this side-discussion.

[Cut parts hopefully all clarified with the above comments]

I didn't read the RFC series, so I missed that there was past discussion on this point.

Perhaps something to roll into an updated commit message? My reading of the current version is that it suggests that the ls-tree-like output is important to get at the data we need, which my patch-for-discussion shows isn't the case.

I don't have a problem with how the output looks, I happen to like the ls-tree output better, I've just been suggesting that differing output == code duplication.

In any case. I'm sorry about any comments I've made that came across as snarky or whatever. Since we're talking in a text-based medium I'm going to take the reading of a third-party native speaker (you) over mine.

I didn't mean any comments I've made that way, I'm very interested in seeing this feature land, and just want to try to help it along. Given the size of this thread over a relatively trivial matter I think that "help" is probably counterproductive at this point.

I don't think this is criticial or needs to be done or whatever. I've only kept up this thread for the reasons stated above, i.e. it seeming to me to be based on the premise that we can't add certain code to builtin/*.c, and if we can get around that we can make this simpler.

On 3/28/2021 11:31 AM, Ævar Arnfjörð Bjarmason wrote:> It seems to me that the reason for that state is based on a

I feel _strongly_ that a change to the user-facing CLI should come with a good reason and care about how it locks-in behavior for the future.

Any adjustment to 'git ls-files' deserves its own series and attention, not in an already-too-large series like this one.

I'm not happy that this series and the next are so long, but that's the best I can do to make them reviewable and still capture a complete scenario. Hopefully the remaining series after these first two are smaller. Things like "what should 'git ls-files' do with a sparse index?" can fit cleanly on top once the core functionality of the internals are stable.

I have an _opinion_ that the ls-files output is not well-suited to testing because the --debug output splits details across multiple lines. This is a minor point that could probably be corrected by a complicated script method, but that's why I list this as an opinion.

I think changing 'ls-files' before the sparse index has stabilized is premature. I said that a series like the RFC you sent would be appropriate after this concept is more stable. I do _not_ recommend trying to juggle it on top of the work while the patches are in flight.

Thanks,
-Stolee

I do not have a problem with either of approaches to help debugging (i.e. extending "ls-files --debug" or a new test helper), but I am curious to be reminded what the plan for "git ls-files [-s]" output is, when run in a repository in which sparse cone checkout is used.

Do we see trees and paths outside the cone omitted, or does the act of running "ls-files" dehydrate the trees into their constituent blobs?

Thanks.

At the moment, end-to-end behavior is identical as before: sparse directory entries are expanded to all of the contained blobs instead of writing the tree entries.

The sparse-index work will not be complete until every command is audited for potential behavior change when disabling the command_requires_full_index setting. That includes deciding what is the best decision for ls-files, and will likely include an option for both possible outputs (tree entries, or expanding to blobs). The interesting discussion that is worth its own topic is whether or not the tree entries should be displayed by default.

So the plan is: this _will_ be addressed, but in the future after the core functionality and value of the sparse-index is set.

Thanks,
-Stolee

At the risk of going in circles here...

And I agree with you. Where we disagree is whether lives in builtin/*.c == user-facing. I think --debug options are != that. It seems Junio downthread agrees with that.

A user-facing change to it yes, but I don't see how use of an (existing even) --debug option would warrant any more attention than a new test helper, less actually, it's less new code.

The alternative way of doing it at the end of
https://lore.kernel.org/git/[email protected] would make this series smaller.

Anyway. As I noted in the E-Mail you're replying to
(https://lore.kernel.org/git/[email protected]/) I really don't care that much.

I'm just still perplexed at how you keep bringing up use of an internal-only --debug option as "user-facing", and here "already too large" when we're talking about a proposed alternate direction that would reduce the size.

Sure. I'm fully on board with just moving forward with this in some manner.

I'm not on board with the part of this that seems like it could just be rephrased/understood as "...and we're not touching ls-files even with a --debug option now because that would be user-facing[...]".

If the --debug it's spewing now isn't handy we can just change the output format. The docs say:

This is intended to show as much information as possible for manual inspection; the exact format may change at any time.

And we don't have existing in-tree users, something like this would make it rather trivial:

    diff --git a/builtin/ls-files.c b/builtin/ls-files.c
    index f6f9e483b27..7596edc9f9d 100644
    --- a/builtin/ls-files.c
    +++ b/builtin/ls-files.c
    @@ -113,11 +113,11 @@ static void print_debug(const struct cache_entry *ce)
     	if (debug_mode) {
     		const struct stat_data *sd = &ce->ce_stat_data;
     
    -		printf("  ctime: %u:%u\n", sd->sd_ctime.sec, sd->sd_ctime.nsec);
    -		printf("  mtime: %u:%u\n", sd->sd_mtime.sec, sd->sd_mtime.nsec);
    -		printf("  dev: %u\tino: %u\n", sd->sd_dev, sd->sd_ino);
    -		printf("  uid: %u\tgid: %u\n", sd->sd_uid, sd->sd_gid);
    -		printf("  size: %u\tflags: %x\n", sd->sd_size, ce->ce_flags);
    +		printf("  ctime: %u:%u%c", sd->sd_ctime.sec, sd->sd_ctime.nsec, line_terminator);
    +		printf("  mtime: %u:%u%c", sd->sd_mtime.sec, sd->sd_mtime.nsec, line_terminator);
    +		printf("  dev: %u\tino: %u%c", sd->sd_dev, sd->sd_ino, line_terminator);
    +		printf("  uid: %u\tgid: %u%c", sd->sd_uid, sd->sd_gid, line_terminator);
    +		printf("  size: %u\tflags: %x%c", sd->sd_size, ce->ce_flags, line_terminator);
     	}
     }

But even without that it wouldn't be some complicated post-processing, just a pipe to a small perl or awk process.

Just to clarify, upthread in [1] you said:

And I recommend that you continue to pursue [these RFC patches] as an independent series, but I'm not going to incorporate them into this one[...]

So do I understand it right that you're referring to phase IV in your opinion being the first point where we'd consider piggy-backing on anything in builtin (that "user-facing" dilemma again...).

But at that point wouldn't you have your own ideas about some user-facing ls-files or other porcelain for this, so I'm not sure where to place the encouragement that I continue to pursue that RFC series, other than setting a reminder in my calendar for 6-12 months in the future :)

1. https://lore.kernel.org/git/[email protected]/

I disagree that we can change the expected output of --debug so quickly, despite warnings in the documentation. Changing that format or creating a new output format requires cognitive load, and we have enough of that going on in this area as it is.

...

I'm not saying "patch size" or "code size" but instead thinking of it in terms of how many decisions need to be made. Changing a builtin when it's not necessary adds to the complexity of the series and interrupts its core goals.

Finally, I have mentioned that I will need extra data for testing a new index format. I don't want to modify the builtin now in a way that is insufficient for the needs in that future series.

I'm saying that if you feel strongly about it, then please pursue the changes to ls-files any time after this series (but probably after the next) solidifies. Having the changes be in a separate series allows time to inspect the behavior change to the builtin in a focused way.

Otherwise, I will modify ls-files myself in this 6-12 month timeframe, based on the established plan to remove the command_requires_full_index setting.

Thanks,
-Stolee

Hi,

[...]

Actually, I did add a t/helper/test-fast-rebase.c (which is a few hundred lines long) as part of the work on merge-ort, because merge-ort wasn't ready and because rewiring sequencer.c was a huge amount of work that I didn't want to get distracted by at the time. I originally suggested making fast-rebase a non-advertised builtin, but multiple reviewers suggested the test helper route instead.

¯\_(ツ)_/¯

From: Derrick Stolee <[email protected]>

We will use 'test-tool read-cache --table' to check that a sparse index is written as part of init_repos. Since we will no longer always expand a sparse index into a full index, add an '--expand' parameter that adds a call to ensure_full_index() so we can compare a sparse index directly against a full index, or at least what the in-memory index looks like when expanded in this way.

---
 t/helper/test-read-cache.c               | 13 ++++++++++++-
 t/t1092-sparse-checkout-compatibility.sh |  5 +++++
 2 files changed, 17 insertions(+), 1 deletion(-)

index 6cfd8f2de71c..b52c174acc7a 100644
@@ -4,6 +4,7 @@
 #include "blob.h"
 #include "commit.h"
 #include "tree.h"
+#include "sparse-index.h"
 
 static void print_cache_entry(struct cache_entry *ce)
 {

@@ -35,13 +36,19 @@ int cmd__read_cache(int argc, const char **argv)
 	struct repository *r = the_repository;
 	int i, cnt = 1;
 	const char *name = NULL;
-	int table = 0;
+	int table = 0, expand = 0;
+
+	initialize_the_repository();
+	prepare_repo_settings(r);
+	r->settings.command_requires_full_index = 0;
 
 	for (++argv, --argc; *argv && starts_with(*argv, "--"); ++argv, --argc) {
 		if (skip_prefix(*argv, "--print-and-refresh=", &name))
 			continue;
 		if (!strcmp(*argv, "--table"))
 			table = 1;
+		else if (!strcmp(*argv, "--expand"))
+			expand = 1;
 	}
 
 	if (argc == 1)

@@ -51,6 +58,10 @@ int cmd__read_cache(int argc, const char **argv)
 
 	for (i = 0; i < cnt; i++) {
 		repo_read_index(r);
+
+		if (expand)
+			ensure_full_index(r->index);
+
 		if (name) {
 			int pos;
 

index de5d8461c993..a1aea141c62c 100755
@@ -130,6 +130,11 @@ test_sparse_match () {
 	test_cmp sparse-checkout-err sparse-index-err
 }
 
+test_expect_success 'expanded in-memory index matches full index' '
+	init_repos &&
+	test_sparse_match test-tool read-cache --expand --table
+'
+
 test_expect_success 'status with options' '
 	init_repos &&
 	test_all_match git status --porcelain=v2 &&

gitgitgadget

From: Derrick Stolee <[email protected]>

The next change will translate full indexes into sparse indexes at write time. The existing logic provides a way for every sparse index to be expanded to a full index at read time. However, there are cases where an index is written and then continues to be used in-memory to perform further updates.

unpack_trees() is frequently called after such a write. In particular, commands like 'git reset' do this double-update of the index.

Ensure that we have a full index when entering unpack_trees(), but only when command_requires_full_index is true. This is always true at the moment, but we will later relax that after unpack_trees() is updated to handle sparse directory entries.

---
 unpack-trees.c | 7 +++++++
 1 file changed, 7 insertions(+)

index f5f668f532d8..4dd99219073a 100644
@@ -1567,6 +1567,7 @@ static int verify_absent(const struct cache_entry *,
  */
 int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)
 {
+	struct repository *repo = the_repository;
 	int i, ret;
 	static struct cache_entry *dfc;
 	struct pattern_list pl;

@@ -1578,6 +1579,12 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 	trace_performance_enter();
 	trace2_region_enter("unpack_trees", "unpack_trees", the_repository);
 
+	prepare_repo_settings(repo);
+	if (repo->settings.command_requires_full_index) {
+		ensure_full_index(o->src_index);
+		ensure_full_index(o->dst_index);
+	}
+
 	if (!core_apply_sparse_checkout || !o->update)
 		o->skip_sparse_checkout = 1;
 	if (!o->skip_sparse_checkout && !o->pl) {

gitgitgadget

From: Derrick Stolee <[email protected]>

As we modify the sparse-checkout definition, we perform index operations on a pattern_list that only exists in-memory. This allows easy backing out in case the index update fails.

However, if the index write itself cares about the sparse-checkout pattern set, we need access to that in-memory copy. Place a pointer to a 'struct pattern_list' in the index so we can access this on-demand. This will be used in the next change which uses the sparse-checkout definition to filter out directories that are outside the sparse cone.

---
 builtin/sparse-checkout.c | 17 ++++++++++-------
 cache.h                   |  2 ++
 2 files changed, 12 insertions(+), 7 deletions(-)

index 2306a9ad98e0..e00b82af727b 100644
@@ -110,6 +110,8 @@ static int update_working_directory(struct pattern_list *pl)
 	if (is_index_unborn(r->index))
 		return UPDATE_SPARSITY_SUCCESS;
 
+	r->index->sparse_checkout_patterns = pl;
+
 	memset(&o, 0, sizeof(o));
 	o.verbose_update = isatty(2);
 	o.update = 1;

@@ -138,6 +140,7 @@ static int update_working_directory(struct pattern_list *pl)
 	else
 		rollback_lock_file(&lock_file);
 
+	r->index->sparse_checkout_patterns = NULL;
 	return result;
 }
 

@@ -517,19 +520,18 @@ static int modify_pattern_list(int argc, const char **argv, enum modify_type m)
 {
 	int result;
 	int changed_config = 0;
-	struct pattern_list pl;
-	memset(&pl, 0, sizeof(pl));
+	struct pattern_list *pl = xcalloc(1, sizeof(*pl));
 
 	switch (m) {
 	case ADD:
 		if (core_sparse_checkout_cone)
-			add_patterns_cone_mode(argc, argv, &pl);
+			add_patterns_cone_mode(argc, argv, pl);
 		else
-			add_patterns_literal(argc, argv, &pl);
+			add_patterns_literal(argc, argv, pl);
 		break;
 
 	case REPLACE:
-		add_patterns_from_input(&pl, argc, argv);
+		add_patterns_from_input(pl, argc, argv);
 		break;
 	}
 

@@ -539,12 +541,13 @@ static int modify_pattern_list(int argc, const char **argv, enum modify_type m)
 		changed_config = 1;
 	}
 
-	result = write_patterns_and_update(&pl);
+	result = write_patterns_and_update(pl);
 
 	if (result && changed_config)
 		set_config(MODE_NO_PATTERNS);
 
-	clear_pattern_list(&pl);
+	clear_pattern_list(pl);
+	free(pl);
 	return result;
 }
 

index 136dd496c95d..8c4464420d0a 100644
@@ -307,6 +307,7 @@ static inline unsigned int canon_mode(unsigned int mode)
 struct split_index;
 struct untracked_cache;
 struct progress;
+struct pattern_list;
 
 struct index_state {
 	struct cache_entry **cache;

@@ -338,6 +339,7 @@ struct index_state {
 	struct mem_pool *ce_mem_pool;
 	struct progress *progress;
 	struct repository *repo;
+	struct pattern_list *sparse_checkout_patterns;
 };
 
 /* Name hashing */

gitgitgadget

From: Derrick Stolee <[email protected]>

If we have a full index, then we can convert it to a sparse index by replacing directories outside of the sparse cone with sparse directory entries. The convert_to_sparse() method does this, when the situation is appropriate.

For now, we avoid converting the index to a sparse index if:

1. the index is split.
2. the index is already sparse.
3. sparse-checkout is disabled.
4. sparse-checkout does not use cone mode.

Finally, we currently limit the conversion to when the GIT_TEST_SPARSE_INDEX environment variable is enabled. A mode using Git config will be added in a later change.

The trickiest thing about this conversion is that we might not be able to mark a directory as a sparse directory just because it is outside the sparse cone. There might be unmerged files within that directory, so we need to look for those. Also, if there is some strange reason why a file is not marked with CE_SKIP_WORKTREE, then we should give up on converting that directory. There is still hope that some of its subdirectories might be able to convert to sparse, so we keep looking deeper.

The conversion process is assisted by the cache-tree extension. This is calculated from the full index if it does not already exist. We then abandon the cache-tree as it no longer applies to the newly-sparse index. Thus, this cache-tree will be recalculated in every sparse-full-sparse round-trip until we integrate the cache-tree extension with the sparse index.

Some Git commands use the index after writing it. For example, 'git add' will update the index, then write it to disk, then read its entries to report information. To keep the in-memory index in a full state after writing, we re-expand it to a full one after the write. This is wasteful for commands that only write the index and do not read from it again, but that is only the case until we make those commands "sparse aware."

We can compare the behavior of the sparse-index in t1092-sparse-checkout-compability.sh by using GIT_TEST_SPARSE_INDEX=1 when operating on the 'sparse-index' repo. We can also compare the two sparse repos directly, such as comparing their indexes (when expanded to full in the case of the 'sparse-index' repo). We also verify that the index is actually populated with sparse directory entries.

The 'checkout and reset (mixed)' test is marked for failure when comparing a sparse repo to a full repo, but we can compare the two sparse-checkout cases directly to ensure that we are not changing the behavior when using a sparse index.

---
 cache-tree.c                             |   3 +
 cache.h                                  |   2 +
 read-cache.c                             |  26 ++++-
 sparse-index.c                           | 139 +++++++++++++++++++++++
 sparse-index.h                           |   1 +
 t/t1092-sparse-checkout-compatibility.sh |  61 +++++++++-
 6 files changed, 228 insertions(+), 4 deletions(-)

index 2fb483d3c083..5f07a39e501e 100644
@@ -6,6 +6,7 @@
 #include "object-store.h"
 #include "replace-object.h"
 #include "promisor-remote.h"
+#include "sparse-index.h"
 
 #ifndef DEBUG_CACHE_TREE
 #define DEBUG_CACHE_TREE 0

@@ -442,6 +443,8 @@ int cache_tree_update(struct index_state *istate, int flags)
 	if (i)
 		return i;
 
+	ensure_full_index(istate);
+
 	if (!istate->cache_tree)
 		istate->cache_tree = cache_tree();
 

index 8c4464420d0a..74b43aaa2bd1 100644
@@ -251,6 +251,8 @@ static inline unsigned int create_ce_mode(unsigned int mode)
 {
 	if (S_ISLNK(mode))
 		return S_IFLNK;
+	if (S_ISSPARSEDIR(mode))
+		return S_IFDIR;
 	if (S_ISDIR(mode) || S_ISGITLINK(mode))
 		return S_IFGITLINK;
 	return S_IFREG | ce_permissions(mode);

index dd3980c12b53..b9c08773466c 100644
@@ -25,6 +25,7 @@
 #include "fsmonitor.h"
 #include "thread-utils.h"
 #include "progress.h"
+#include "sparse-index.h"
 
 /* Mask for the name length in ce_flags in the on-disk index */
 

@@ -1002,8 +1003,14 @@ int verify_path(const char *path, unsigned mode)
 
 			c = *path++;
 			if ((c == '.' && !verify_dotfile(path, mode)) ||
-			    is_dir_sep(c) || c == '\0')
+			    is_dir_sep(c))
 				return 0;
+			/*
+			 * allow terminating directory separators for
+			 * sparse directory entries.
+			 */
+			if (c == '\0')
+				return S_ISDIR(mode);
 		} else if (c == '\\' && protect_ntfs) {
 			if (is_ntfs_dotgit(path))
 				return 0;

@@ -3079,6 +3086,14 @@ static int do_write_locked_index(struct index_state *istate, struct lock_file *l
 				 unsigned flags)
 {
 	int ret;
+	int was_full = !istate->sparse_index;
+
+	ret = convert_to_sparse(istate);
+
+	if (ret) {
+		warning(_("failed to convert to a sparse-index"));
+		return ret;
+	}
 
 	/*
 	 * TODO trace2: replace "the_repository" with the actual repo instance

@@ -3090,6 +3105,9 @@ static int do_write_locked_index(struct index_state *istate, struct lock_file *l
 	trace2_region_leave_printf("index", "do_write_index", the_repository,
 				   "%s", get_lock_file_path(lock));
 
+	if (was_full)
+		ensure_full_index(istate);
+
 	if (ret)
 		return ret;
 	if (flags & COMMIT_LOCK)

@@ -3180,9 +3198,10 @@ static int write_shared_index(struct index_state *istate,
 			      struct tempfile **temp)
 {
 	struct split_index *si = istate->split_index;
-	int ret;
+	int ret, was_full = !istate->sparse_index;
 
 	move_cache_to_base_index(istate);
+	convert_to_sparse(istate);
 
 	trace2_region_enter_printf("index", "shared/do_write_index",
 				   the_repository, "%s", get_tempfile_path(*temp));

@@ -3190,6 +3209,9 @@ static int write_shared_index(struct index_state *istate,
 	trace2_region_leave_printf("index", "shared/do_write_index",
 				   the_repository, "%s", get_tempfile_path(*temp));
 
+	if (was_full)
+		ensure_full_index(istate);
+
 	if (ret)
 		return ret;
 	ret = adjust_shared_perm(get_tempfile_path(*temp));

index 09a20d036c46..64380e121d80 100644
@@ -3,5 +3,6 @@
 
 struct index_state;
 void ensure_full_index(struct index_state *istate);
+int convert_to_sparse(struct index_state *istate);
 
 #endif

gitgitgadget

From: Derrick Stolee <[email protected]>

A submodule is stored as a "Git link" that actually points to a commit within a submodule. Submodules are populated or not depending on submodule configuration, not sparse-checkout. To ensure that the sparse-index feature integrates correctly with submodules, we should not collapse a directory if there is a Git link within its range.

---
 sparse-index.c                           |  1 +
 t/t1092-sparse-checkout-compatibility.sh | 17 +++++++++++++++++
 2 files changed, 18 insertions(+)

index 619ff7c2e217..7631f7bd00b7 100644
@@ -52,6 +52,7 @@ static int convert_to_sparse_rec(struct index_state *istate,
 		struct cache_entry *ce = istate->cache[i];
 
 		if (ce_stage(ce) ||
+		    S_ISGITLINK(ce->ce_mode) ||
 		    !(ce->ce_flags & CE_SKIP_WORKTREE))
 			can_convert = 0;
 	}

index 1e888d195122..cba5f89b1e96 100755
@@ -376,4 +376,21 @@ test_expect_success 'clean' '
 	test_sparse_match test_path_is_dir folder1
 '
 
+test_expect_success 'submodule handling' '
+	init_repos &&
+
+	test_all_match mkdir modules &&
+	test_all_match touch modules/a &&
+	test_all_match git add modules &&
+	test_all_match git commit -m "add modules directory" &&
+
+	run_on_all git submodule add "$(pwd)/initial-repo" modules/sub &&
+	test_all_match git commit -m "add submodule" &&
+
+	# having a submodule prevents "modules" from collapse
+	test-tool -C sparse-index read-cache --table >cache &&
+	grep "100644 blob .*	modules/a" cache &&
+	grep "160000 commit $(git -C initial-repo rev-parse HEAD)	modules/sub" cache
+'
+
 test_done

gitgitgadget

From: Derrick Stolee <[email protected]>

The index_pos_by_traverse_info() currently throws a BUG() when a directory entry exists exactly in the index. We need to consider that it is possible to have a directory in a sparse index as long as that entry is itself marked with the skip-worktree bit.

The 'pos' variable is assigned a negative value if an exact match is not found. Since a directory name can be an exact match, it is no longer an error to have a nonnegative 'pos' value.

---
 unpack-trees.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

index 4dd99219073a..0b888dab2246 100644
@@ -746,9 +746,13 @@ static int index_pos_by_traverse_info(struct name_entry *names,
 	strbuf_make_traverse_path(&name, info, names->path, names->pathlen);
 	strbuf_addch(&name, '/');
 	pos = index_name_pos(o->src_index, name.buf, name.len);
-	if (pos >= 0)
-		BUG("This is a directory and should not exist in index");
-	pos = -pos - 1;
+	if (pos >= 0) {
+		if (!o->src_index->sparse_index ||
+		    !(o->src_index->cache[pos]->ce_flags & CE_SKIP_WORKTREE))
+			BUG("This is a directory and should not exist in index");
+	} else {
+		pos = -pos - 1;
+	}
 	if (pos >= o->src_index->cache_nr ||
 	    !starts_with(o->src_index->cache[pos]->name, name.buf) ||
 	    (pos > 0 && starts_with(o->src_index->cache[pos-1]->name, name.buf)))

gitgitgadget

From: Derrick Stolee <[email protected]>

Add a test case that uses test_region to ensure that we are truly expanding a sparse index to a full one, then converting back to sparse when writing the index. As we integrate more Git commands with the sparse index, we will convert these commands to check that we do _not_ convert the sparse index to a full index and instead stay sparse the entire time.

---
 t/t1092-sparse-checkout-compatibility.sh | 18 ++++++++++++++++++
 1 file changed, 18 insertions(+)

index cba5f89b1e96..47f983217852 100755
@@ -393,4 +393,22 @@ test_expect_success 'submodule handling' '
 	grep "160000 commit $(git -C initial-repo rev-parse HEAD)	modules/sub" cache
 '
 
+test_expect_success 'sparse-index is expanded and converted back' '
+	init_repos &&
+
+	(
+		GIT_TEST_SPARSE_INDEX=1 &&
+		export GIT_TEST_SPARSE_INDEX &&
+		GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
+			git -C sparse-index -c core.fsmonitor="" reset --hard &&
+		test_region index convert_to_sparse trace2.txt &&
+		test_region index ensure_full_index trace2.txt &&
+
+		rm trace2.txt &&
+		GIT_TRACE2_EVENT="$(pwd)/trace2.txt" GIT_TRACE2_EVENT_NESTING=10 \
+			git -C sparse-index -c core.fsmonitor="" status -uno &&
+		test_region index ensure_full_index trace2.txt
+	)
+'
+
 test_done

gitgitgadget

From: Derrick Stolee <[email protected]>

Previously, we enabled the sparse index format only using GIT_TEST_SPARSE_INDEX=1. This is not a feasible direction for users to actually select this mode. Further, sparse directory entries are not understood by the index formats as advertised.

We _could_ add a new index version that explicitly adds these capabilities, but there are nuances to index formats 2, 3, and 4 that are still valuable to select as options. Until we add index format version 5, create a repo extension, "extensions.sparseIndex", that specifies that the tool reading this repository must understand sparse directory entries.

This change only encodes the extension and enables it when GIT_TEST_SPARSE_INDEX=1. Later, we will add a more user-friendly CLI mechanism.

---
 Documentation/config/extensions.txt |  8 ++++++
 cache.h                             |  1 +
 repo-settings.c                     |  7 ++++++
 repository.h                        |  3 ++-
 setup.c                             |  3 +++
 sparse-index.c                      | 38 +++++++++++++++++++++++++----
 6 files changed, 54 insertions(+), 6 deletions(-)

index 4e23d73cdcad..c02e09af0046 100644
@@ -6,3 +6,11 @@ extensions.objectFormat::
 Note that this setting should only be set by linkgit:git-init[1] or
 linkgit:git-clone[1].  Trying to change it after initialization will not
 work and will produce hard-to-diagnose issues.
+
+extensions.sparseIndex::
+	When combined with `core.sparseCheckout=true` and
+	`core.sparseCheckoutCone=true`, the index may contain entries
+	corresponding to directories outside of the sparse-checkout
+	definition in lieu of containing each path under such directories.
+	Versions of Git that do not understand this extension do not
+	expect directory entries in the index.

index 74b43aaa2bd1..8aede373aeb3 100644
@@ -1059,6 +1059,7 @@ struct repository_format {
 	int worktree_config;
 	int is_bare;
 	int hash_algo;
+	int sparse_index;
 	char *work_tree;
 	struct string_list unknown_extensions;
 	struct string_list v1_only_extensions;

index d63569e4041e..9677d50f9238 100644
@@ -85,4 +85,11 @@ void prepare_repo_settings(struct repository *r)
 	 * removed.
 	 */
 	r->settings.command_requires_full_index = 1;
+
+	/*
+	 * Initialize this as off.
+	 */
+	r->settings.sparse_index = 0;
+	if (!repo_config_get_bool(r, "extensions.sparseindex", &value) && value)
+		r->settings.sparse_index = 1;
 }

index e06a23015697..a45f7520fd9e 100644
@@ -42,7 +42,8 @@ struct repo_settings {
 
 	int core_multi_pack_index;
 
-	unsigned command_requires_full_index:1;
+	unsigned command_requires_full_index:1,
+		 sparse_index:1;
 };
 
 struct repository {

index c04cd25a30df..cd8394564613 100644
@@ -500,6 +500,9 @@ static enum extension_result handle_extension(const char *var,
 			return error("invalid value for 'extensions.objectformat'");
 		data->hash_algo = format;
 		return EXTENSION_OK;
+	} else if (!strcmp(ext, "sparseindex")) {
+		data->sparse_index = 1;
+		return EXTENSION_OK;
 	}
 	return EXTENSION_UNKNOWN;
 }

index 7631f7bd00b7..3a6df66faeab 100644
@@ -102,19 +102,47 @@ static int convert_to_sparse_rec(struct index_state *istate,
 	return num_converted - start_converted;
 }
 
+static int enable_sparse_index(struct repository *repo)
+{
+	const char *config_path = repo_git_path(repo, "config.worktree");
+
+	if (upgrade_repository_format(1) < 0) {
+		warning(_("unable to upgrade repository format to enable sparse-index"));
+		return -1;
+	}
+	git_config_set_in_file_gently(config_path,
+				      "extensions.sparseIndex",
+				      "true");
+
+	prepare_repo_settings(repo);
+	repo->settings.sparse_index = 1;
+	return 0;
+}
+
 int convert_to_sparse(struct index_state *istate)
 {
 	if (istate->split_index || istate->sparse_index ||
 	    !core_apply_sparse_checkout || !core_sparse_checkout_cone)
 		return 0;
 
+	if (!istate->repo)
+		istate->repo = the_repository;
+
+	/*
+	 * The GIT_TEST_SPARSE_INDEX environment variable triggers the
+	 * extensions.sparseIndex config variable to be on.
+	 */
+	if (git_env_bool("GIT_TEST_SPARSE_INDEX", 0)) {
+		int err = enable_sparse_index(istate->repo);
+		if (err < 0)
+			return err;
+	}
+
 	/*
-	 * For now, only create a sparse index with the
-	 * GIT_TEST_SPARSE_INDEX environment variable. We will relax
-	 * this once we have a proper way to opt-in (and later still,
-	 * opt-out).
+	 * Only convert to sparse if extensions.sparseIndex is set.
 	 */
-	if (!git_env_bool("GIT_TEST_SPARSE_INDEX", 0))
+	prepare_repo_settings(istate->repo);
+	if (!istate->repo->settings.sparse_index)
 		return 0;
 
 	if (!istate->sparse_checkout_patterns) {

gitgitgadget

From: Derrick Stolee <[email protected]>

The sparse index extension is used to signal that index writes should be in sparse mode. This was only updated using GIT_TEST_SPARSE_INDEX=1.

Add a '--[no-]sparse-index' option to 'git sparse-checkout init' that specifies if the sparse index should be used. It also updates the index to use the correct format, either way. Add a warning in the documentation that the use of a repository extension might reduce compatibility with third-party tools. 'git sparse-checkout init' already sets extension.worktreeConfig, which places most sparse-checkout users outside of the scope of most third-party tools.

Update t1092-sparse-checkout-compatibility.sh to use this CLI instead of GIT_TEST_SPARSE_INDEX=1.

---
 Documentation/git-sparse-checkout.txt    | 14 +++++++
 builtin/sparse-checkout.c                | 17 ++++++++-
 sparse-index.c                           | 37 +++++++++++++------
 sparse-index.h                           |  3 ++
 t/t1092-sparse-checkout-compatibility.sh | 47 +++++++++++++-----------
 5 files changed, 84 insertions(+), 34 deletions(-)

index a0eeaeb02ee3..2ff66c5a4e41 100644
@@ -45,6 +45,20 @@ To avoid interfering with other worktrees, it first enables the
 When `--cone` is provided, the `core.sparseCheckoutCone` setting is
 also set, allowing for better performance with a limited set of
 patterns (see 'CONE PATTERN SET' below).
++
+Use the `--[no-]sparse-index` option to toggle the use of the sparse
+index format. This reduces the size of the index to be more closely
+aligned with your sparse-checkout definition. This can have significant
+performance advantages for commands such as `git status` or `git add`.
+This feature is still experimental. Some commands might be slower with
+a sparse index until they are properly integrated with the feature.
++
+**WARNING:** Using a sparse index requires modifying the index in a way
+that is not completely understood by external tools. If you have trouble
+with this compatibility, then run `git sparse-checkout init --no-sparse-index`
+to rewrite your index to not be sparse. Older versions of Git will not
+understand the `sparseIndex` repository extension and may fail to interact
+with your repository until it is disabled.
 
 'set'::
 	Write a set of patterns to the sparse-checkout file, as given as

index e00b82af727b..ca63e2c64e95 100644
@@ -14,6 +14,7 @@
 #include "unpack-trees.h"
 #include "wt-status.h"
 #include "quote.h"
+#include "sparse-index.h"
 
 static const char *empty_base = "";
 

@@ -283,12 +284,13 @@ static int set_config(enum sparse_checkout_mode mode)
 }
 
 static char const * const builtin_sparse_checkout_init_usage[] = {
-	N_("git sparse-checkout init [--cone]"),
+	N_("git sparse-checkout init [--cone] [--[no-]sparse-index]"),
 	NULL
 };
 
 static struct sparse_checkout_init_opts {
 	int cone_mode;
+	int sparse_index;
 } init_opts;
 
 static int sparse_checkout_init(int argc, const char **argv)

@@ -303,11 +305,15 @@ static int sparse_checkout_init(int argc, const char **argv)
 	static struct option builtin_sparse_checkout_init_options[] = {
 		OPT_BOOL(0, "cone", &init_opts.cone_mode,
 			 N_("initialize the sparse-checkout in cone mode")),
+		OPT_BOOL(0, "sparse-index", &init_opts.sparse_index,
+			 N_("toggle the use of a sparse index")),
 		OPT_END(),
 	};
 
 	repo_read_index(the_repository);
 
+	init_opts.sparse_index = -1;
+
 	argc = parse_options(argc, argv, NULL,
 			     builtin_sparse_checkout_init_options,
 			     builtin_sparse_checkout_init_usage, 0);

@@ -326,6 +332,15 @@ static int sparse_checkout_init(int argc, const char **argv)
 	sparse_filename = get_sparse_checkout_filename();
 	res = add_patterns_from_file_to_list(sparse_filename, "", 0, &pl, NULL);
 
+	if (init_opts.sparse_index >= 0) {
+		if (set_sparse_index_config(the_repository, init_opts.sparse_index) < 0)
+			die(_("failed to modify sparse-index config"));
+
+		/* force an index rewrite */
+		repo_read_index(the_repository);
+		the_repository->index->updated_workdir = 1;
+	}
+
 	/* If we already have a sparse-checkout file, use it. */
 	if (res >= 0) {
 		free(sparse_filename);

index 3a6df66faeab..30c1a11fd62d 100644
@@ -104,23 +104,37 @@ static int convert_to_sparse_rec(struct index_state *istate,
 
 static int enable_sparse_index(struct repository *repo)
 {
-	const char *config_path = repo_git_path(repo, "config.worktree");
+	int res;
 
 	if (upgrade_repository_format(1) < 0) {
 		warning(_("unable to upgrade repository format to enable sparse-index"));
 		return -1;
 	}
-	git_config_set_in_file_gently(config_path,
-				      "extensions.sparseIndex",
-				      "true");
+	res = git_config_set_gently("extensions.sparseindex", "true");
 
 	prepare_repo_settings(repo);
 	repo->settings.sparse_index = 1;
-	return 0;
+	return res;
+}
+
+int set_sparse_index_config(struct repository *repo, int enable)
+{
+	int res;
+
+	if (enable)
+		return enable_sparse_index(repo);
+
+	/* Don't downgrade repository format, just remove the extension. */
+	res = git_config_set_gently("extensions.sparseindex", NULL);
+
+	prepare_repo_settings(repo);
+	repo->settings.sparse_index = 0;
+	return res;
 }
 
 int convert_to_sparse(struct index_state *istate)
 {
+	int test_env;
 	if (istate->split_index || istate->sparse_index ||
 	    !core_apply_sparse_checkout || !core_sparse_checkout_cone)
 		return 0;

@@ -129,14 +143,13 @@ int convert_to_sparse(struct index_state *istate)
 		istate->repo = the_repository;
 
 	/*
-	 * The GIT_TEST_SPARSE_INDEX environment variable triggers the
-	 * extensions.sparseIndex config variable to be on.
+	 * If GIT_TEST_SPARSE_INDEX=1, then trigger extensions.sparseIndex
+	 * to be fully enabled. If GIT_TEST_SPARSE_INDEX=0 (set explicitly),
+	 * then purposefully disable the setting.
 	 */
-	if (git_env_bool("GIT_TEST_SPARSE_INDEX", 0)) {
-		int err = enable_sparse_index(istate->repo);
-		if (err < 0)
-			return err;
-	}
+	test_env = git_env_bool("GIT_TEST_SPARSE_INDEX", -1);
+	if (test_env >= 0)
+		set_sparse_index_config(istate->repo, test_env);
 
 	/*
 	 * Only convert to sparse if extensions.sparseIndex is set.

index 64380e121d80..39dcc859735e 100644
@@ -5,4 +5,7 @@ struct index_state;
 void ensure_full_index(struct index_state *istate);
 int convert_to_sparse(struct index_state *istate);
 
+struct repository;
+int set_sparse_index_config(struct repository *repo, int enable);
+
 #endif

gitgitgadget

From: Derrick Stolee <[email protected]>

We use 'git sparse-checkout init --cone --sparse-index' to toggle the sparse-index feature. It makes sense to also disable it when running 'git sparse-checkout disable'. This is particularly important because it removes the extensions.sparseIndex config option, allowing other tools to use this Git repository again.

This does mean that 'git sparse-checkout init' will not re-enable the sparse-index feature, even if it was previously enabled.

While testing this feature, I noticed that the sparse-index was not being written on the first run, but by a second. This was caught by the call to 'test-tool read-cache --table'. This requires adjusting some assignments to core_apply_sparse_checkout and pl.use_cone_patterns in the sparse_checkout_init() logic.

---
 builtin/sparse-checkout.c          | 10 +++++++++-
 t/t1091-sparse-checkout-builtin.sh | 13 +++++++++++++
 2 files changed, 22 insertions(+), 1 deletion(-)

index ca63e2c64e95..585343fa1972 100644
@@ -280,6 +280,9 @@ static int set_config(enum sparse_checkout_mode mode)
 				      "core.sparseCheckoutCone",
 				      mode == MODE_CONE_PATTERNS ? "true" : NULL);
 
+	if (mode == MODE_NO_PATTERNS)
+		set_sparse_index_config(the_repository, 0);
+
 	return 0;
 }
 

@@ -341,10 +344,11 @@ static int sparse_checkout_init(int argc, const char **argv)
 		the_repository->index->updated_workdir = 1;
 	}
 
+	core_apply_sparse_checkout = 1;
+
 	/* If we already have a sparse-checkout file, use it. */
 	if (res >= 0) {
 		free(sparse_filename);
-		core_apply_sparse_checkout = 1;
 		return update_working_directory(NULL);
 	}
 

@@ -366,6 +370,7 @@ static int sparse_checkout_init(int argc, const char **argv)
 	add_pattern(strbuf_detach(&pattern, NULL), empty_base, 0, &pl, 0);
 	strbuf_addstr(&pattern, "!/*/");
 	add_pattern(strbuf_detach(&pattern, NULL), empty_base, 0, &pl, 0);
+	pl.use_cone_patterns = init_opts.cone_mode;
 
 	return write_patterns_and_update(&pl);
 }