[PATCH 00/27] [RFC] Sparse Index

This is based on ds/more-index-cleanups also available as GitGitGadget PR
#839.

The sparse checkout feature allows users to specify a "populated set" that
is smaller than the full list of files at HEAD. Files outside the sparse
checkout definition are not present in the working directory, but are still
present in the index (and marked with the CE_SKIP_WORKTREE bit).

This means that the working directory has size O(populated), and commands
like "git status" or "git checkout" operate using an O(populated) number of
filesystem operations. However, parsing the index still operates on the
scale of O(HEAD).

This can be particularly jarring if you are merging a small repository with
a large monorepo for the purpose of simplifying dependency management. Even
if users have nothing more in their working directory than they had before,
they suddenly see a significant increase in their "git status" or "git add"
times. In these cases, simply parsing the index can be a huge portion of the
command time.

This RFC proposes an update to the index formats to allow "sparse directory
entries". These entries correspond to directories that are completely
excluded from the sparse checkout definition. We can detect that a directory
is excluded when using "cone mode" patterns.

Since having directory entries is a radical departure from the existing
index format, a new extension "extensions.sparseIndex" is added. Using a
sparse index should cause incompatible tools to fail because they do not
understand this extension.

The index is a critical data structure, so making such a drastic change must
be handled carefully. This RFC does only enough adjustments to demonstrate
performance improvements for "git status" and "git add." Other commands
should operate identically to before, since the other commands will expand a
sparse index into a full index by parsing trees.

WARNING: I'm getting a failure on the FreeBSD build with my sparse-checkout
tests. I'm not sure what is causing these failures, but I will explore while
we discuss the possibility of the feature as a whole.

Here is an outline for this RFC:

 * Patches 1-14: create and test the sparse index format. This is just
   enough to start writing the format, but all Git commands become slower
   for using it. This is because everything is guarded to expand to a full
   index before actually operating on the cache entries.

 * Patch 15: This massive patch is actually a bunch of patches squashed
   together. I have a branch that adds "ensure_full_index()" guards in each
   necessary file along with some commentary about how the index is being
   used. This patch is presented here as one big dump because that
   commentary isn't particularly interesting if the RFC leads to a very
   different approach.

 * Patches 16-27: These changes make enough code "sparse aware" such that
   "git status" and "git add" start operating in time O(populated) instead
   of O(HEAD).

Performance numbers are given in patch 27, but repeated somewhat here. The
test environment I use has ~2.1 million paths at HEAD, but only 68,000
populated paths given the sparse-checkout I'm using. The sparse index has
about 2,000 sparse directory entries.

 1. Use the full index. The index size is ~186 MB.
 2. Use the sparse index. The index size is ~5.5 MB.
 3. Use a commit where HEAD matches the populated set. The full index size
    is ~5.3MB.

The third benchmark is included as a theoretical optimum for a repository of
the same object database.

First, a clean 'git status' improves from 3.1s to 240ms.

Benchmark #1: full index (git status) Time (mean ± σ): 3.167 s ± 0.036 s
[User: 2.006 s, System: 1.078 s] Range (min … max): 3.100 s … 3.208 s 10
runs

Benchmark #2: sparse index (git status) Time (mean ± σ): 239.5 ms ± 8.1 ms
[User: 189.4 ms, System: 226.8 ms] Range (min … max): 226.0 ms … 251.9 ms 13
runs

Benchmark #3: small tree (git status) Time (mean ± σ): 195.3 ms ± 4.5 ms
[User: 116.5 ms, System: 84.4 ms] Range (min … max): 188.8 ms … 202.8 ms 15
runs

The performance numbers for 'git add .' are much closer to optimal:

Benchmark #1: full index (git add .) Time (mean ± σ): 3.076 s ± 0.022 s
[User: 2.065 s, System: 0.943 s] Range (min … max): 3.044 s … 3.116 s 10
runs

Benchmark #2: sparse index (git add .) Time (mean ± σ): 218.0 ms ± 6.6 ms
[User: 195.7 ms, System: 206.6 ms] Range (min … max): 209.8 ms … 228.2 ms 13
runs

Benchmark #3: small tree (git add .) Time (mean ± σ): 217.6 ms ± 5.4 ms
[User: 131.9 ms, System: 86.7 ms] Range (min … max): 212.1 ms … 228.4 ms 14
runs

I expect that making a sparse index work optimally through the most common
Git commands will take a year of effort. During this process, I expect to
add a lot of testing infrastructure around the sparse-checkout feature,
especially in corner cases. (This RFC focuses on the happy paths of
operating only within the sparse cone, but that will change in the future.)

If this general approach is acceptable, then I would follow it with a
sequence of patch submissions that follow this approach:

 1. Basics of the format. (Patches 1-14)
 2. Add additional guards around index interactions (Patch 15, but split
    appropriately.)
 3. Speed up "git status" and "git add" (Patches 16-27)

After those three items that are represented in this RFC, the work starts to
parallelize a bit. My basic ideas for moving forward from this point are to
do these basic steps:

 * Add new index API abstractions where appropriate, make them sparse-aware.
 * Add new tests around sparse-checkout corner cases. Ensure the sparse
   index works correctly.
 * For a given builtin, add extra testing for sparse-checkouts then it them
   sparse-aware.

Here are some specific questions I'm hoping to answer in this RFC period:

 1. Are these sparse directory entries an appropriate way to extend the
    index format?
 2. Is extensions.sparseIndex a good way to signal that these entries can
    exist?
 3. Is git sparse-checkout init --cone --sparse-index an appropriate way to
    toggle the format?
 4. Are there specific areas that I should target to harden the index API
    before I submit this work?
 5. Does anyone have a good idea how to test a large portion of the test
    suite with sparse-index enabled? The problem I see is that most tests
    don't use sparse-checkout, so the sparse index is identical to the full
    index. Would it be interesting to enable the test setup to add such
    "extra" directories during the test setup?

Thanks, -Stolee

Derrick Stolee (27):
  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: read-cache --table --no-stat
  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
  [RFC-VERSION] *: ensure full index
  unpack-trees: make sparse aware
  dir.c: accept a directory as part of cone-mode patterns
  status: use sparse-index throughout
  status: skip sparse-checkout percentage with sparse-index
  sparse-index: expand_to_path() trivial implementation
  sparse-index: expand_to_path no-op if path exists
  add: allow operating on a sparse-only index
  submodule: die_path_inside_submodule is sparse aware
  dir: use expand_to_path in add_patterns()
  fsmonitor: disable if index is sparse
  pathspec: stop calling ensure_full_index
  cache-tree: integrate with sparse directory entries

 Documentation/config/extensions.txt      |   7 +
 Documentation/git-sparse-checkout.txt    |  14 +
 Makefile                                 |   1 +
 apply.c                                  |  10 +-
 blame.c                                  |   7 +-
 builtin/add.c                            |   3 +
 builtin/checkout-index.c                 |   5 +-
 builtin/commit.c                         |   3 +
 builtin/grep.c                           |   2 +
 builtin/ls-files.c                       |   9 +-
 builtin/merge-index.c                    |   2 +
 builtin/mv.c                             |   2 +
 builtin/rm.c                             |   2 +
 builtin/sparse-checkout.c                |  35 ++-
 builtin/update-index.c                   |   2 +
 cache-tree.c                             |  21 ++
 cache.h                                  |  15 +-
 diff.c                                   |   2 +
 dir.c                                    |  19 +-
 dir.h                                    |   2 +-
 entry.c                                  |   2 +
 fsmonitor.c                              |  18 +-
 merge-recursive.c                        |  22 +-
 name-hash.c                              |  10 +
 pathspec.c                               |   4 +-
 pathspec.h                               |   4 +-
 preload-index.c                          |   2 +
 read-cache.c                             |  51 +++-
 repo-settings.c                          |  15 +
 repository.c                             |  11 +-
 repository.h                             |   3 +
 rerere.c                                 |   2 +
 resolve-undo.c                           |   6 +
 setup.c                                  |   3 +
 sha1-name.c                              |   3 +
 sparse-index.c                           | 360 +++++++++++++++++++++++
 sparse-index.h                           |  23 ++
 split-index.c                            |   2 +
 submodule.c                              |  22 +-
 submodule.h                              |   6 +-
 t/helper/test-read-cache.c               |  77 ++++-
 t/t1092-sparse-checkout-compatibility.sh | 130 +++++++-
 tree.c                                   |   2 +
 unpack-trees.c                           |  40 ++-
 wt-status.c                              |  21 +-
 wt-status.h                              |   1 +
 46 files changed, 942 insertions(+), 61 deletions(-)
 create mode 100644 sparse-index.c
 create mode 100644 sparse-index.h


base-commit: 2271fe7848aa11b30e5313d95d9caebc2937fce5
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-847%2Fderrickstolee%2Fsparse-index%2Frfc-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-847/derrickstolee/sparse-index/rfc-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/847
-- 
gitgitgadget

From: Derrick Stolee <redacted>

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) 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 == 01000755
 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.

Signed-off-by: Derrick Stolee <redacted>
---
 cache.h        | 11 +++++-
 read-cache.c   |  9 +++++
 sparse-index.c | 94 +++++++++++++++++++++++++++++++++++++++++++++++++-
 sparse-index.h |  1 +
 4 files changed, 113 insertions(+), 2 deletions(-)

diff --git a/cache.h b/cache.h
index f9c7a603841..884046ca5b8 100644
--- a/cache.h
+++ b/cache.h

@@ -204,6 +204,10 @@ struct cache_entry {
 #error "CE_EXTENDED_FLAGS out of range"
 #endif
 
+#define CE_MODE_SPARSE_DIRECTORY 01000755
+#define SPARSE_DIR_MODE 0100
+#define S_ISSPARSEDIR(m) ((m)->ce_mode == CE_MODE_SPARSE_DIRECTORY)
+
 /* Forward structure decls */
 struct pathspec;
 struct child_process;

@@ -249,6 +253,8 @@ static inline unsigned int create_ce_mode(unsigned int mode)
 {
 	if (S_ISLNK(mode))
 		return S_IFLNK;
+	if (mode == SPARSE_DIR_MODE)
+		return CE_MODE_SPARSE_DIRECTORY;
 	if (S_ISDIR(mode) || S_ISGITLINK(mode))
 		return S_IFGITLINK;
 	return S_IFREG | ce_permissions(mode);

@@ -319,7 +325,8 @@ 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;
 	struct hashmap name_hash;
 	struct hashmap dir_hash;
 	struct object_id oid;

@@ -721,6 +728,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)

diff --git a/read-cache.c b/read-cache.c
index ecf6f689940..1097ecbf132 100644
--- a/read-cache.c
+++ b/read-cache.c

@@ -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))
+		istate->sparse_index = 1;
+
 	istate->cache[nr] = ce;
 	add_name_hash(istate, ce);
 }

@@ -2255,6 +2258,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:

diff --git a/sparse-index.c b/sparse-index.c
index 82183ead563..1e70244dc13 100644
--- a/sparse-index.c
+++ b/sparse-index.c

@@ -1,8 +1,100 @@
 #include "cache.h"
 #include "repository.h"
 #include "sparse-index.h"
+#include "tree.h"
+#include "pathspec.h"
+#include "trace2.h"
+
+static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)
+{
+	ALLOC_GROW(istate->cache, nr + 1, istate->cache_alloc);
+
+	istate->cache[nr] = ce;
+	add_name_hash(istate, ce);
+}
+
+static int add_path_to_index(const struct object_id *oid,
+				struct strbuf *base, const char *path,
+				unsigned int mode, int stage, void *context)
+{
+	struct index_state *istate = (struct index_state *)context;
+	struct cache_entry *ce;
+	size_t len = base->len;
+
+	if (S_ISDIR(mode))
+		return READ_TREE_RECURSIVE;
+
+	strbuf_addstr(base, path);
+
+	ce = make_cache_entry(istate, mode, oid, base->buf, 0, 0);
+	ce->ce_flags |= CE_SKIP_WORKTREE;
+	set_index_entry(istate, istate->cache_nr++, ce);
+
+	strbuf_setlen(base, len);
+	return 0;
+}
 
 void ensure_full_index(struct index_state *istate)
 {
-	/* intentionally left blank */
+	int i;
+	struct index_state *full;
+
+	if (!istate || !istate->sparse_index)
+		return;
+
+	if (!istate->repo)
+		istate->repo = the_repository;
+
+	trace2_region_enter("index", "ensure_full_index", istate->repo);
+
+	/* initialize basics of new index */
+	full = xcalloc(1, sizeof(struct index_state));
+	memcpy(full, istate, sizeof(struct index_state));
+
+	/* then change the necessary things */
+	full->sparse_index = 0;
+	full->cache_alloc = (3 * istate->cache_alloc) / 2;
+	full->cache_nr = 0;
+	ALLOC_ARRAY(full->cache, full->cache_alloc);
+
+	for (i = 0; i < istate->cache_nr; i++) {
+		struct cache_entry *ce = istate->cache[i];
+		struct tree *tree;
+		struct pathspec ps;
+
+		if (!S_ISSPARSEDIR(ce)) {
+			set_index_entry(full, full->cache_nr++, ce);
+			continue;
+		}
+		if (!(ce->ce_flags & CE_SKIP_WORKTREE))
+			warning(_("index entry is a directory, but not sparse (%08x)"),
+				ce->ce_flags);
+
+		/* recursively walk into cd->name */
+		tree = lookup_tree(istate->repo, &ce->oid);
+
+		memset(&ps, 0, sizeof(ps));
+		ps.recursive = 1;
+		ps.has_wildcard = 1;
+		ps.max_depth = -1;
+
+		read_tree_recursive(istate->repo, tree,
+				    ce->name, strlen(ce->name),
+				    0, &ps,
+				    add_path_to_index, full);
+
+		/* free directory entries. full entries are re-used */
+		discard_cache_entry(ce);
+	}
+
+	/* Copy back into original index. */
+	memcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));
+	istate->sparse_index = 0;
+	istate->cache = full->cache;
+	istate->cache_nr = full->cache_nr;
+	istate->cache_alloc = full->cache_alloc;
+
+	free(full);
+
+	trace2_region_leave("index", "ensure_full_index", istate->repo);
 }

diff --git a/sparse-index.h b/sparse-index.h
index 8dda92032e2..a2777dcac59 100644
--- a/sparse-index.h
+++ b/sparse-index.h

@@ -3,5 +3,6 @@
 
 struct index_state;
 void ensure_full_index(struct index_state *istate);
+int convert_to_sparse(struct index_state *istate);
 
 #endif

\ No newline at end of file
-- 
gitgitgadget

On Mon, Jan 25, 2021 at 9:42 AM Derrick Stolee via GitGitGadget
[off-list ref] wrote:

From: Derrick Stolee <redacted>

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) 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 == 01000755

This is a weird number.  What's the reason for choosing it?  It looks
deceptively close to 0100755, normal executable files, but has the
extra 0, meaning that ce->ce_mode & S_IFMT is 0, suggesting it has no
file type.

Since it's a directory, why not use S_IFDIR (040000)?

(GITLINK does use the weird 0160000 value, but it happens to be
S_IFLNK | S_IFDIR == 0120000 | 040000, which conveys "it's both a
directory and a symlink")

 2. ce->flags & CE_SKIP_WORKTREE is true

Makes sense.

 3. ce->name[ce->namelen - 1] == '/' (ends in dir separator)

Is there a particular reason for this?  I'm used to seeing names
without the trailing slash, both in the index and in tree objects.  I
don't know enough to be for or against this idea; just curious at this
point.

 4. ce->oid references a tree object.

Makes sense...but doesn't that suggest we'd want to use ce->ce_mode = 040000?


Also, as a bit of a side comment: There have been other requests in
the past to support directory objects in the index.  The only use I
remember for them requested from others was to allow tracking empty
directories.  However, I've long wanted to introduce a new "blobtree"
object to git, so that a user can "git add" some big binary file, but
internally git splits the binary file up and stores it as multiple
blobs within git plus a new "blobtree" object that references all the
individual blobs with enough information about how to stitch all the
blobs together to get the original file.  I had a few different forms
of "blobtree" things that I was interested in.  I think brian once
suggested some similar idea.

Another magic value.  Feels like the commit message should reference
this one and why it was picked.  Seems odd to me, and possibly
problematic to re-use file permission bits that might collide with
files recorded by really old versions of git.  Maybe that's not a
concern, though.

+#define S_ISSPARSEDIR(m) ((m)->ce_mode == CE_MODE_SPARSE_DIRECTORY)

Should the special sauce apply to ce_flags rather than ce_mode?  Thus,
instead of an S_ISSPARSEDIR, perhaps have a ce_sparse_dir macro
(similar to ce_skip_worktree) based on a CE_SPARSE_DIR value (similar
to CE_SKIP_WORKTREE)?

Or, alternatively, do we need a single special state here?  Could we
check for a combination of ce_mode == 040000 && ce_skip_worktree(ce)?

Haven't you leaked the original istate->cache here?

Seems logically that you'd add one, but was this meant to be included
in a later patch?

 #endif
\ No newline at end of file
--
gitgitgadget

On 1/26/2021 10:05 PM, Elijah Newren wrote:

On Mon, Jan 25, 2021 at 9:42 AM Derrick Stolee via GitGitGadget
[off-list ref] wrote:

...

quoted

Sparse directory entries have a specific 'ce_mode' value. The macro
S_ISSPARSEDIR(ce) 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 == 01000755

This is a weird number.  What's the reason for choosing it?  It looks
deceptively close to 0100755, normal executable files, but has the
extra 0, meaning that ce->ce_mode & S_IFMT is 0, suggesting it has no
file type.

Since it's a directory, why not use S_IFDIR (040000)?

(GITLINK does use the weird 0160000 value, but it happens to be
S_IFLNK | S_IFDIR == 0120000 | 040000, which conveys "it's both a
directory and a symlink")

I forget how exactly I came up with these magic constants, but then
completely forgot to think of them critically because I haven't had
to look at them in a while. They _are_ important, especially because
these values affect the file format itself.

I'll think harder on this before submitting a series intended for
merging.

quoted

 2. ce->flags & CE_SKIP_WORKTREE is true

Makes sense.

quoted

 3. ce->name[ce->namelen - 1] == '/' (ends in dir separator)

Is there a particular reason for this?  I'm used to seeing names
without the trailing slash, both in the index and in tree objects.  I
don't know enough to be for or against this idea; just curious at this
point.

It's yet another way to distinguish directories from files, but
there are cases where we do string searches up to a prefix, and
having these directory separators did help, IIRC.

quoted

 4. ce->oid references a tree object.

Makes sense...but doesn't that suggest we'd want to use ce->ce_mode = 040000?

...

quoted

+#define CE_MODE_SPARSE_DIRECTORY 01000755
+#define SPARSE_DIR_MODE 0100

Another magic value.  Feels like the commit message should reference
this one and why it was picked.  Seems odd to me, and possibly
problematic to re-use file permission bits that might collide with
files recorded by really old versions of git.  Maybe that's not a
concern, though.

quoted

+#define S_ISSPARSEDIR(m) ((m)->ce_mode == CE_MODE_SPARSE_DIRECTORY)

Should the special sauce apply to ce_flags rather than ce_mode?  Thus,
instead of an S_ISSPARSEDIR, perhaps have a ce_sparse_dir macro
(similar to ce_skip_worktree) based on a CE_SPARSE_DIR value (similar
to CE_SKIP_WORKTREE)?

Or, alternatively, do we need a single special state here?  Could we
check for a combination of ce_mode == 040000 && ce_skip_worktree(ce)?

The intention was that ce_mode be a unique value that could only
be assigned to a directory entry, which would then by necessity be
sparse. Checking both ce_mode and ce_flags seemed wasteful with the
given assumptions

...

quoted

+       /* Copy back into original index. */
+       memcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));
+       istate->sparse_index = 0;
+       istate->cache = full->cache;

Haven't you leaked the original istate->cache here?

Yes, seems so. Will fix.

Thanks,
-Stolee

On Wed, Jan 27, 2021 at 5:43 AM Derrick Stolee [off-list ref] wrote:

On 1/26/2021 10:05 PM, Elijah Newren wrote:

quoted

On Mon, Jan 25, 2021 at 9:42 AM Derrick Stolee via GitGitGadget
[off-list ref] wrote:

...

quoted

quoted

Sparse directory entries have a specific 'ce_mode' value. The macro
S_ISSPARSEDIR(ce) 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 == 01000755

This is a weird number.  What's the reason for choosing it?  It looks
deceptively close to 0100755, normal executable files, but has the
extra 0, meaning that ce->ce_mode & S_IFMT is 0, suggesting it has no
file type.

Since it's a directory, why not use S_IFDIR (040000)?

(GITLINK does use the weird 0160000 value, but it happens to be
S_IFLNK | S_IFDIR == 0120000 | 040000, which conveys "it's both a
directory and a symlink")

I forget how exactly I came up with these magic constants, but then
completely forgot to think of them critically because I haven't had
to look at them in a while. They _are_ important, especially because
these values affect the file format itself.

I'll think harder on this before submitting a series intended for
merging.

quoted

quoted

 2. ce->flags & CE_SKIP_WORKTREE is true

Makes sense.

quoted

 3. ce->name[ce->namelen - 1] == '/' (ends in dir separator)

Is there a particular reason for this?  I'm used to seeing names
without the trailing slash, both in the index and in tree objects.  I
don't know enough to be for or against this idea; just curious at this
point.

It's yet another way to distinguish directories from files, but
there are cases where we do string searches up to a prefix, and
having these directory separators did help, IIRC.

quoted

quoted

 4. ce->oid references a tree object.

Makes sense...but doesn't that suggest we'd want to use ce->ce_mode = 040000?

...

quoted

quoted

+#define CE_MODE_SPARSE_DIRECTORY 01000755
+#define SPARSE_DIR_MODE 0100

Another magic value.  Feels like the commit message should reference
this one and why it was picked.  Seems odd to me, and possibly
problematic to re-use file permission bits that might collide with
files recorded by really old versions of git.  Maybe that's not a
concern, though.

quoted

+#define S_ISSPARSEDIR(m) ((m)->ce_mode == CE_MODE_SPARSE_DIRECTORY)

Should the special sauce apply to ce_flags rather than ce_mode?  Thus,
instead of an S_ISSPARSEDIR, perhaps have a ce_sparse_dir macro
(similar to ce_skip_worktree) based on a CE_SPARSE_DIR value (similar
to CE_SKIP_WORKTREE)?

Or, alternatively, do we need a single special state here?  Could we
check for a combination of ce_mode == 040000 && ce_skip_worktree(ce)?

The intention was that ce_mode be a unique value that could only
be assigned to a directory entry, which would then by necessity be
sparse. Checking both ce_mode and ce_flags seemed wasteful with the
given assumptions

040000 is a unique value that could only be assigned to a directory
entry.  Since we have no other uses of directories within the index,
you are right, we wouldn't need to check ce_skip_worktree(ce) as well;
just a check for the 040000 mode would be enough.

...

quoted

quoted

+       /* Copy back into original index. */
+       memcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));
+       istate->sparse_index = 0;
+       istate->cache = full->cache;

Haven't you leaked the original istate->cache here?

Yes, seems so. Will fix.

Thanks,
-Stolee

From: Derrick Stolee <redacted>

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.

Signed-off-by: Derrick Stolee <redacted>
---
 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

diff --git a/Makefile b/Makefile
index 7b64106930a..77564ae3b78 100644
--- a/Makefile
+++ b/Makefile

@@ -999,6 +999,7 @@ LIB_OBJS += sha1-name.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

diff --git a/repo-settings.c b/repo-settings.c
index f7fff0f5ab8..d63569e4041 100644
--- a/repo-settings.c
+++ b/repo-settings.c

@@ -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;
 }

diff --git a/repository.c b/repository.c
index c98298acd01..a8acae002f7 100644
--- a/repository.c
+++ b/repository.c

@@ -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,

diff --git a/repository.h b/repository.h
index b385ca3c94b..e06a2301569 100644
--- a/repository.h
+++ b/repository.h

@@ -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 {

diff --git a/sparse-index.c b/sparse-index.c
new file mode 100644
index 00000000000..82183ead563
--- /dev/null
+++ b/sparse-index.c

@@ -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 */
+}

diff --git a/sparse-index.h b/sparse-index.h
new file mode 100644
index 00000000000..8dda92032e2
--- /dev/null
+++ b/sparse-index.h

@@ -0,0 +1,7 @@
+#ifndef SPARSE_INDEX_H__
+#define SPARSE_INDEX_H__
+
+struct index_state;
+void ensure_full_index(struct index_state *istate);
+
+#endif

\ No newline at end of file
-- 
gitgitgadget

From: Derrick Stolee <redacted>

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.

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.

Signed-off-by: Derrick Stolee <redacted>
---
 cache-tree.c                             |   3 +
 read-cache.c                             |  18 ++-
 sparse-index.c                           | 139 +++++++++++++++++++++++
 t/t1092-sparse-checkout-compatibility.sh |  63 +++++++++-
 4 files changed, 218 insertions(+), 5 deletions(-)

diff --git a/cache-tree.c b/cache-tree.c
index 2fb483d3c08..5f07a39e501 100644
--- a/cache-tree.c
+++ b/cache-tree.c

@@ -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();
 

diff --git a/read-cache.c b/read-cache.c
index 1097ecbf132..0522260416e 100644
--- a/read-cache.c
+++ b/read-cache.c

@@ -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,15 @@ 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 enries.
+			 */
+			if (c == '\0')
+				return mode == CE_MODE_SPARSE_DIRECTORY ||
+				       mode == SPARSE_DIR_MODE;
 		} else if (c == '\\' && protect_ntfs) {
 			if (is_ntfs_dotgit(path))
 				return 0;

@@ -3062,6 +3070,13 @@ static int do_write_locked_index(struct index_state *istate, struct lock_file *l
 {
 	int ret;
 
+	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
 	 * that is associated with the given "istate".

@@ -3165,6 +3180,7 @@ static int write_shared_index(struct index_state *istate,
 	int ret;
 
 	move_cache_to_base_index(istate);
+	convert_to_sparse(istate);
 
 	trace2_region_enter_printf("index", "shared/do_write_index",
 				   the_repository, "%s", (*temp)->filename.buf);

diff --git a/sparse-index.c b/sparse-index.c
index 1e70244dc13..d8f1a5a13d7 100644
--- a/sparse-index.c
+++ b/sparse-index.c

@@ -4,6 +4,145 @@
 #include "tree.h"
 #include "pathspec.h"
 #include "trace2.h"
+#include "cache-tree.h"
+#include "config.h"
+#include "dir.h"
+#include "fsmonitor.h"
+
+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, SPARSE_DIR_MODE, &tree->oid, sparse_dir, 0, 0);
+
+	de->ce_flags |= CE_SKIP_WORKTREE;
+	return de;
+}
+
+/*
+ * Returns the number of entries "inserted" into the index.
+ */
+static int convert_to_sparse_rec(struct index_state *istate,
+				 int num_converted,
+				 int start, int end,
+				 const char *ct_path, size_t ct_pathlen,
+				 struct cache_tree *ct)
+{
+	int i, can_convert = 1;
+	int start_converted = num_converted;
+	enum pattern_match_result match;
+	int dtype;
+	struct strbuf child_path = STRBUF_INIT;
+	struct pattern_list *pl = istate->sparse_checkout_patterns;
+
+	/*
+	 * Is the current path outside of the sparse cone?
+	 * Then check if the region can be replaced by a sparse
+	 * directory entry (everything is sparse and merged).
+	 */
+	match = path_matches_pattern_list(ct_path, ct_pathlen,
+					  NULL, &dtype, pl, istate);
+	if (match != NOT_MATCHED)
+		can_convert = 0;
+
+	for (i = start; can_convert && i < end; i++) {
+		struct cache_entry *ce = istate->cache[i];
+
+		if (ce_stage(ce) ||
+		    !(ce->ce_flags & CE_SKIP_WORKTREE))
+			can_convert = 0;
+	}
+
+	if (can_convert) {
+		struct cache_entry *se;
+		se = construct_sparse_dir_entry(istate, ct_path, ct);
+
+		istate->cache[num_converted++] = se;
+		return 1;
+	}
+
+	for (i = start; i < end; ) {
+		int count, span, pos = -1;
+		const char *base, *slash;
+		struct cache_entry *ce = istate->cache[i];
+
+		/*
+		 * Detect if this is a normal entry oustide of any subtree
+		 * entry.
+		 */
+		base = ce->name + ct_pathlen;
+		slash = strchr(base, '/');
+
+		if (slash)
+			pos = cache_tree_subtree_pos(ct, base, slash - base);
+
+		if (pos < 0) {
+			istate->cache[num_converted++] = ce;
+			i++;
+			continue;
+		}
+
+		strbuf_setlen(&child_path, 0);
+		strbuf_add(&child_path, ce->name, slash - ce->name + 1);
+
+		span = ct->down[pos]->cache_tree->entry_count;
+		count = convert_to_sparse_rec(istate,
+					      num_converted, i, i + span,
+					      child_path.buf, child_path.len,
+					      ct->down[pos]->cache_tree);
+		num_converted += count;
+		i += span;
+	}
+
+	strbuf_release(&child_path);
+	return num_converted - start_converted;
+}
+
+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;
+
+	/*
+	 * 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).
+	 */
+	if (!git_env_bool("GIT_TEST_SPARSE_INDEX", 0))
+		return 0;
+
+	if (!istate->sparse_checkout_patterns) {
+		istate->sparse_checkout_patterns = xcalloc(1, sizeof(struct pattern_list));
+		if (get_sparse_checkout_patterns(istate->sparse_checkout_patterns) < 0)
+			return 0;
+	}
+
+	if (!istate->sparse_checkout_patterns->use_cone_patterns) {
+		warning(_("attempting to use sparse-index without cone mode"));
+		return -1;
+	}
+
+	if (cache_tree_update(istate, 0)) {
+		warning(_("unable to update cache-tree, staying full"));
+		return -1;
+	}
+
+	remove_fsmonitor(istate);
+
+	trace2_region_enter("index", "convert_to_sparse", istate->repo);
+	istate->cache_nr = convert_to_sparse_rec(istate,
+						 0, 0, istate->cache_nr,
+						 "", 0, istate->cache_tree);
+	istate->drop_cache_tree = 1;
+	istate->sparse_index = 1;
+	trace2_region_leave("index", "convert_to_sparse", istate->repo);
+	return 0;
+}
 
 static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)
 {

diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh
index 3aa9b0d21b4..22becbaca2e 100755
--- a/t/t1092-sparse-checkout-compatibility.sh
+++ b/t/t1092-sparse-checkout-compatibility.sh

@@ -2,6 +2,9 @@
 
 test_description='compare full workdir to sparse workdir'
 
+GIT_TEST_CHECK_CACHE_TREE=0
+GIT_TEST_SPLIT_INDEX=0
+
 . ./test-lib.sh
 
 test_expect_success 'setup' '

@@ -106,7 +109,7 @@ run_on_sparse () {
 	) &&
 	(
 		cd sparse-index &&
-		$* >../sparse-index-out 2>../sparse-index-err
+		GIT_TEST_SPARSE_INDEX=1 $* >../sparse-index-out 2>../sparse-index-err
 	)
 }
 

@@ -121,7 +124,9 @@ run_on_all () {
 test_all_match () {
 	run_on_all $* &&
 	test_cmp full-checkout-out sparse-checkout-out &&
-	test_cmp full-checkout-err sparse-checkout-err
+	test_cmp full-checkout-out sparse-index-out &&
+	test_cmp full-checkout-err sparse-checkout-err &&
+	test_cmp full-checkout-err sparse-index-err
 }
 
 test_sparse_match () {

@@ -130,6 +135,38 @@ test_sparse_match () {
 	test_cmp sparse-checkout-err sparse-index-err
 }
 
+test_expect_success 'sparse-index contents' '
+	init_repos &&
+
+	test-tool -C sparse-index read-cache --table --no-stat >cache &&
+	for dir in folder1 folder2 x
+	do
+		TREE=$(git -C sparse-index rev-parse HEAD:$dir) &&
+		grep "0b0000 0755 $TREE $dir/" cache \
+			|| return 1
+	done &&
+
+	GIT_TEST_SPARSE_INDEX=1 git -C sparse-index sparse-checkout set folder1 &&
+
+	test-tool -C sparse-index read-cache --table --no-stat >cache &&
+	for dir in deep folder2 x
+	do
+		TREE=$(git -C sparse-index rev-parse HEAD:$dir) &&
+		grep "0b0000 0755 $TREE $dir/" cache \
+			|| return 1
+	done &&
+
+	GIT_TEST_SPARSE_INDEX=1 git -C sparse-index sparse-checkout set deep/deeper1 &&
+
+	test-tool -C sparse-index read-cache --table --no-stat >cache &&
+	for dir in deep/deeper2 folder1 folder2 x
+	do
+		TREE=$(git -C sparse-index rev-parse HEAD:$dir) &&
+		grep "0b0000 0755 $TREE $dir/" cache \
+			|| return 1
+	done
+'
+
 test_expect_success 'expanded in-memory index matches full index' '
 	init_repos &&
 	test_sparse_match test-tool read-cache --expand --table --no-stat

@@ -137,6 +174,7 @@ test_expect_success 'expanded in-memory index matches full index' '
 
 test_expect_success 'status with options' '
 	init_repos &&
+	test_sparse_match ls &&
 	test_all_match git status --porcelain=v2 &&
 	test_all_match git status --porcelain=v2 -z -u &&
 	test_all_match git status --porcelain=v2 -uno &&

@@ -169,7 +207,7 @@ test_expect_success 'add, commit, checkout' '
 
 	test_all_match git add -A &&
 	test_all_match git status --porcelain=v2 &&
-	test_all_match git commit -m "Extend README.md" &&
+	test_all_match git commit -m "Extend-README.md" &&
 
 	test_all_match git checkout HEAD~1 &&
 	test_all_match git checkout - &&

@@ -273,6 +311,17 @@ test_expect_failure 'checkout and reset (mixed)' '
 	test_all_match git reset update-folder2
 '
 
+# Ensure that sparse-index behaves identically to
+# sparse-checkout with a full index.
+test_expect_success 'checkout and reset (mixed) [sparse]' '
+	init_repos &&
+
+	test_sparse_match git checkout -b reset-test update-deep &&
+	test_sparse_match git reset deepest &&
+	test_sparse_match git reset update-folder1 &&
+	test_sparse_match git reset update-folder2
+'
+
 test_expect_success 'merge' '
 	init_repos &&
 

@@ -309,14 +358,20 @@ test_expect_success 'clean' '
 	test_all_match git status --porcelain=v2 &&
 	test_all_match git clean -f &&
 	test_all_match git status --porcelain=v2 &&
+	test_sparse_match ls &&
+	test_sparse_match ls folder1 &&
 
 	test_all_match git clean -xf &&
 	test_all_match git status --porcelain=v2 &&
+	test_sparse_match ls &&
+	test_sparse_match ls folder1 &&
 
 	test_all_match git clean -xdf &&
 	test_all_match git status --porcelain=v2 &&
+	test_sparse_match ls &&
+	test_sparse_match ls folder1 &&
 
-	test_path_is_dir sparse-checkout/folder1
+	test_sparse_match test_path_is_dir folder1
 '
 
 test_done

-- 
gitgitgadget

On Mon, Jan 25, 2021 at 9:42 AM Derrick Stolee via GitGitGadget
[off-list ref] wrote:

From: Derrick Stolee <redacted>

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.

Oh good, you check for *both* unmerged entries and !CE_SKIP_WORKTREE
ones.  Very nice.

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.

When going from full to sparse, won't the parts of the cache-tree for
paths outside of sparsified directories still be valid?  Can't we use
those?

Also, when going from sparse to full, can't we just populate the
cache-tree as well since we have to read trees to get the individual
file entries and we will get all the directory (tree) values at the
same time?

s/enries/entries/

+                        */
+                       if (c == '\0')
+                               return mode == CE_MODE_SPARSE_DIRECTORY ||
+                                      mode == SPARSE_DIR_MODE;

Why two values here?  I get confused why you have both (which isn't
new to this patch; I'm just still confused from when I saw
SPARSE_DIR_MODE).

I know some people hate gotos, but this seems like one of the cases
where a goto jumping after the following for & if would be clearer
then setting can_convert to 0.

+
+       for (i = start; can_convert && i < end; i++) {

Instead of checking can_convert here...

+               struct cache_entry *ce = istate->cache[i];
+
+               if (ce_stage(ce) ||
+                   !(ce->ce_flags & CE_SKIP_WORKTREE))
+                       can_convert = 0;

...could you just insert a break here?

+       }
+
+       if (can_convert) {
+               struct cache_entry *se;
+               se = construct_sparse_dir_entry(istate, ct_path, ct);
+
+               istate->cache[num_converted++] = se;
+               return 1;
+       }
+
+       for (i = start; i < end; ) {
+               int count, span, pos = -1;
+               const char *base, *slash;
+               struct cache_entry *ce = istate->cache[i];
+
+               /*
+                * Detect if this is a normal entry oustide of any subtree

s/oustide/outside/

+                * entry.
+                */
+               base = ce->name + ct_pathlen;
+               slash = strchr(base, '/');
+
+               if (slash)
+                       pos = cache_tree_subtree_pos(ct, base, slash - base);
+
+               if (pos < 0) {
+                       istate->cache[num_converted++] = ce;
+                       i++;
+                       continue;
+               }
+
+               strbuf_setlen(&child_path, 0);
+               strbuf_add(&child_path, ce->name, slash - ce->name + 1);
+
+               span = ct->down[pos]->cache_tree->entry_count;
+               count = convert_to_sparse_rec(istate,
+                                             num_converted, i, i + span,
+                                             child_path.buf, child_path.len,
+                                             ct->down[pos]->cache_tree);
+               num_converted += count;
+               i += span;

And there's no i++ in the loop itself, so this is good.

Why do you need to set this?  I vaguely remember needing to mess with
this when working with sparse checkouts because it did weird stuff but
I don't remember details.  But since you patch touches cache_trees, it
seems weird to show up without explanation.

It would seem clearer to me if this output were to better match `git
ls-tree -rt ...` output (or at least the ' tree ' lines from such
output).

Why this change?

From: Derrick Stolee <redacted>

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 outsie the sparse cone.

Signed-off-by: Derrick Stolee <redacted>
---
 builtin/sparse-checkout.c | 17 ++++++++++-------
 cache.h                   |  2 ++
 2 files changed, 12 insertions(+), 7 deletions(-)

diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c
index 2306a9ad98e..e00b82af727 100644
--- a/builtin/sparse-checkout.c
+++ b/builtin/sparse-checkout.c

@@ -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;
 }
 

diff --git a/cache.h b/cache.h
index 884046ca5b8..b05341cc687 100644
--- a/cache.h
+++ b/cache.h

@@ -311,6 +311,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;

@@ -336,6 +337,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

On Mon, Jan 25, 2021 at 9:42 AM Derrick Stolee via GitGitGadget
[off-list ref] wrote:

From: Derrick Stolee <redacted>

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 outsie the sparse cone.

s/outsie/outside/

Isn't this the same patch you put in your index cleanup series, or am
I getting confused?  It looks very familiar.

On 1/27/2021 12:00 PM, Elijah Newren wrote:

On Mon, Jan 25, 2021 at 9:42 AM Derrick Stolee via GitGitGadget
[off-list ref] wrote:

quoted

From: Derrick Stolee <redacted>

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 outsie the sparse cone.

s/outsie/outside/

Thanks! 

Isn't this the same patch you put in your index cleanup series, or am
I getting confused?  It looks very familiar.

 
I removed it from v2 of that series because it didn't do anything of
value until we start using the sparse_checkout_patterns member in the
next patch of _this_ series.

Thanks,
-Stolee

From: Derrick Stolee <redacted>

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.

Signed-off-by: Derrick Stolee <redacted>
---
 t/helper/test-read-cache.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/t/helper/test-read-cache.c b/t/helper/test-read-cache.c
index f858d0d0a0c..3c45dfeb3cb 100644
--- a/t/helper/test-read-cache.c
+++ b/t/helper/test-read-cache.c

@@ -1,6 +1,7 @@
 #include "test-tool.h"
 #include "cache.h"
 #include "config.h"
+#include "sparse-index.h"
 
 static void print_cache_entry(struct cache_entry *ce, unsigned stat)
 {

@@ -44,6 +45,11 @@ int cmd__read_cache(int argc, const char **argv)
 	const char *name = NULL;
 	int table = 0;
 	int stat = 1;
+	int 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))