diff mbox series

[02/27] sparse-index: implement ensure_full_index()

Message ID ebbe8569dcc16f2ae235c4167be0e72a53982982.1611596534.git.gitgitgadget@gmail.com (mailing list archive)
State New
Headers show
Series Sparse Index | expand

Commit Message

Derrick Stolee Jan. 25, 2021, 5:41 p.m. UTC
From: Derrick Stolee <dstolee@microsoft.com>

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 <dstolee@microsoft.com>
---
 cache.h        | 11 +++++-
 read-cache.c   |  9 +++++
 sparse-index.c | 94 +++++++++++++++++++++++++++++++++++++++++++++++++-
 sparse-index.h |  1 +
 4 files changed, 113 insertions(+), 2 deletions(-)

Comments

Elijah Newren Jan. 27, 2021, 3:05 a.m. UTC | #1
On Mon, Jan 25, 2021 at 9:42 AM Derrick Stolee via GitGitGadget
<gitgitgadget@gmail.com> wrote:
>
> From: Derrick Stolee <dstolee@microsoft.com>
>
> 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.

> 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 <dstolee@microsoft.com>
> ---
>  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

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)?

> +
>  /* 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;

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

> +       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);

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
>
Derrick Stolee Jan. 27, 2021, 1:43 p.m. UTC | #2
On 1/26/2021 10:05 PM, Elijah Newren wrote:
> On Mon, Jan 25, 2021 at 9:42 AM Derrick Stolee via GitGitGadget
> <gitgitgadget@gmail.com> wrote:
...
>> 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.

>>  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.

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.

>>  4. ce->oid references a tree object.
> 
> Makes sense...but doesn't that suggest we'd want to use ce->ce_mode = 040000?

...

>> +#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.
> 
>> +#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

...

>> +       /* 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
Elijah Newren Jan. 27, 2021, 4:38 p.m. UTC | #3
On Wed, Jan 27, 2021 at 5:43 AM Derrick Stolee <stolee@gmail.com> wrote:
>
> On 1/26/2021 10:05 PM, Elijah Newren wrote:
> > On Mon, Jan 25, 2021 at 9:42 AM Derrick Stolee via GitGitGadget
> > <gitgitgadget@gmail.com> wrote:
> ...
> >> 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.
>
> >>  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.
>
> 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.
>
> >>  4. ce->oid references a tree object.
> >
> > Makes sense...but doesn't that suggest we'd want to use ce->ce_mode = 040000?
>
> ...
>
> >> +#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.
> >
> >> +#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.

> ...
>
> >> +       /* 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
Junio C Hamano Jan. 28, 2021, 5:25 a.m. UTC | #4
Elijah Newren <newren@gmail.com> writes:

>>  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")

Yes, that combination of IFLNK/IFDIR was the reason why we use the
value.  I tend to think IFDIR is the best thing to use here.
diff mbox series

Patch

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