Re: [PATCH v5 00/21] Sparse Index: Design, Format, Tests

>
> Here is the first full patch series submission coming out of the
> sparse-index RFC [1].
>
> [1]
> https://lore.kernel.org/git/pull.847.git.1611596533.gitgitgadget@gmail.com/
>
> 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 V5
> =============
>
> This version is updated to use an index extension instead of a repository
> format extension. Thanks, Szeder! This one change affects the range-diff
> quite a bit, so please review those changes carefully.
>
> In particular: git sparse-checkout init --cone --sparse-index now sets a new
> index.sparse config option as an indicator that we should attempt writing
> the index in sparse form.
>
>
> 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 (21):
>   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: add 'sdir' index extension
>   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: add index.sparse config option
>   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/index.txt           |   5 +
>  Documentation/git-sparse-checkout.txt    |  14 ++
>  Documentation/technical/index-format.txt |  19 ++
>  Documentation/technical/sparse-index.txt | 175 ++++++++++++++
>  Makefile                                 |   1 +
>  builtin/sparse-checkout.c                |  44 +++-
>  cache-tree.c                             |  40 ++++
>  cache.h                                  |  18 +-
>  read-cache.c                             |  44 +++-
>  repo-settings.c                          |  15 ++
>  repository.c                             |  11 +-
>  repository.h                             |   3 +
>  sparse-index.c                           | 285 +++++++++++++++++++++++
>  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 +-
>  20 files changed, 988 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-v5
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-883/derrickstolee/sparse-index/format-v5
> Pull-Request: https://github.com/gitgitgadget/git/pull/883
>
> Range-diff vs v4:
>
>   1:  6426a5c60e53 !  1:  7b600d536c6e sparse-index: design doc and format update
>      @@ Documentation/technical/sparse-index.txt (new)
>       +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
>      ++To start, we use a new required index extension, `sdir`, to allow
>      ++inserting sparse-directory entries into indexes with file format
>       +versions 2, 3, and 4. This prevents Git versions that do not understand
>      -+the sparse-index from operating on one, but it also prevents other
>      -+operations that do not use the index at all. A new format, index v5, will
>      -+be introduced that includes sparse-directory entries by default. It might
>      -+also introduce other features that have been considered for improving the
>      ++the sparse-index from operating on one, while allowing tools that do not
>      ++understand the sparse-index to operate on repositories as long as they do
>      ++not interact with the index. A new format, index v5, will be introduced
>      ++that includes sparse-directory entries by default. It might also
>      ++introduce other features that have been considered for improving the
>       +index, as well.
>       +
>       +Next, consumers of the index will be guarded against operating on a
>   2:  7eabc1d0586c =  2:  202253ec82f3 t/perf: add performance test for sparse operations
>   3:  c9e21d78ecba =  3:  437a0f144e57 t1092: clean up script quoting
>   4:  03cdde756563 =  4:  b7e1bf5c55a7 sparse-index: add guard to ensure full index
>   5:  6b3b6d86385d =  5:  e41d55d2cca9 sparse-index: implement ensure_full_index()
>   6:  7f67adba0498 =  6:  7bfbfbd17321 t1092: compare sparse-checkout to sparse-index
>   7:  7ebd9570b1ad =  7:  a1b8135c0fc8 test-read-cache: print cache entries with --table
>   8:  db7bbd06dbcc =  8:  dd84a2a9121b test-tool: don't force full index
>   9:  3ddd5e794b5e =  9:  b276d2ed5323 unpack-trees: ensure full index
>  10:  7308c87697f1 = 10:  c3651e26dc3a sparse-checkout: hold pattern list in index
>   -:  ------------ > 11:  f926cf8b2e01 sparse-index: add 'sdir' index extension
>  11:  7c10d653ca6b = 12:  c870ae5e8749 sparse-index: convert from full to sparse
>  12:  6db36f33e960 = 13:  bcf0da959ef3 submodule: sparse-index should not collapse links
>  13:  d24bd3348d98 = 14:  7191b48237de unpack-trees: allow sparse directories
>  14:  08d9f5f3c0d1 = 15:  57be9b4a728b sparse-index: check index conversion happens
>  15:  6f38cef196b0 ! 16:  c22b4111e49e sparse-index: create extension for compatibility
>      @@ Metadata
>       Author: Derrick Stolee <dstolee@microsoft.com>
>
>        ## Commit message ##
>      -    sparse-index: create extension for compatibility
>      +    sparse-index: add index.sparse config option
>
>      -    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.
>      +    When enabled, this config option signals that index writes should
>      +    attempt to use sparse-directory entries.
>
>           Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
>
>      - ## Documentation/config/extensions.txt ##
>      -@@ Documentation/config/extensions.txt: 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.
>      + ## Documentation/config/index.txt ##
>      +@@ Documentation/config/index.txt: index.recordOffsetTable::
>      +  Defaults to 'true' if index.threads has been explicitly enabled,
>      +  'false' otherwise.
>      +
>      ++index.sparse::
>      ++ When enabled, write the index using sparse-directory entries. This
>      ++ has no effect unless `core.sparseCheckout` and
>      ++ `core.sparseCheckoutCone` are both enabled. Defaults to 'false'.
>       +
>      -+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.threads::
>      +  Specifies the number of threads to spawn when loading the index.
>      +  This is meant to reduce index load time on multiprocessor machines.
>
>        ## cache.h ##
>       @@ cache.h: struct repository_format {
>      @@ repo-settings.c: void prepare_repo_settings(struct repository *r)
>       +  * Initialize this as off.
>       +  */
>       + r->settings.sparse_index = 0;
>      -+ if (!repo_config_get_bool(r, "extensions.sparseindex", &value) && value)
>      ++ if (!repo_config_get_bool(r, "index.sparse", &value) && value)
>       +         r->settings.sparse_index = 1;
>        }
>
>      @@ repository.h: struct repo_settings {
>
>        struct repository {
>
>      - ## setup.c ##
>      -@@ setup.c: 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;
>      - }
>      -
>        ## sparse-index.c ##
>       @@ sparse-index.c: static int convert_to_sparse_rec(struct index_state *istate,
>         return num_converted - start_converted;
>      @@ sparse-index.c: static int convert_to_sparse_rec(struct index_state *istate,
>       +{
>       + 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",
>      ++                               "index.sparse",
>       +                               "true");
>       +
>       + prepare_repo_settings(repo);
>      @@ sparse-index.c: static int convert_to_sparse_rec(struct index_state *istate,
>       +
>       + /*
>       +  * The GIT_TEST_SPARSE_INDEX environment variable triggers the
>      -+  * extensions.sparseIndex config variable to be on.
>      ++  * index.sparse config variable to be on.
>       +  */
>       + if (git_env_bool("GIT_TEST_SPARSE_INDEX", 0)) {
>       +         int err = enable_sparse_index(istate->repo);
>      @@ sparse-index.c: static int convert_to_sparse_rec(struct index_state *istate,
>       -  * 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.
>      ++  * Only convert to sparse if index.sparse is set.
>          */
>       - if (!git_env_bool("GIT_TEST_SPARSE_INDEX", 0))
>       + prepare_repo_settings(istate->repo);
>  16:  923081e7e079 ! 17:  75fe9b0f57da sparse-checkout: toggle sparse index from builtin
>      @@ Documentation/git-sparse-checkout.txt: To avoid interfering with other worktrees
>       +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.
>      ++understand the sparse directory entries index 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
>      @@ builtin/sparse-checkout.c: static int sparse_checkout_init(int argc, const char
>
>        ## sparse-index.c ##
>       @@ sparse-index.c: static int convert_to_sparse_rec(struct index_state *istate,
>      +  return num_converted - start_converted;
>      + }
>
>      - static int enable_sparse_index(struct repository *repo)
>      +-static int enable_sparse_index(struct repository *repo)
>      ++static int set_index_sparse_config(struct repository *repo, int enable)
>        {
>       - 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",
>      +-                               "index.sparse",
>       -                               "true");
>      -+ res = git_config_set_gently("extensions.sparseindex", "true");
>      ++ int res;
>      ++ char *config_path = repo_git_path(repo, "config.worktree");
>      ++ res = git_config_set_in_file_gently(config_path,
>      ++                                     "index.sparse",
>      ++                                     enable ? "true" : NULL);
>      ++ free(config_path);
>
>         prepare_repo_settings(repo);
>         repo->settings.sparse_index = 1;
>      @@ sparse-index.c: static int convert_to_sparse_rec(struct index_state *istate,
>       +
>       +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);
>      ++ int res = set_index_sparse_config(repo, enable);
>       +
>       + prepare_repo_settings(repo);
>      -+ repo->settings.sparse_index = 0;
>      ++ repo->settings.sparse_index = enable;
>       + return res;
>        }
>
>      @@ sparse-index.c: static int convert_to_sparse_rec(struct index_state *istate,
>             !core_apply_sparse_checkout || !core_sparse_checkout_cone)
>                 return 0;
>       @@ sparse-index.c: 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.
>      +   * The GIT_TEST_SPARSE_INDEX environment variable triggers the
>      +   * index.sparse config variable to be on.
>          */
>       - if (git_env_bool("GIT_TEST_SPARSE_INDEX", 0)) {
>       -         int err = enable_sparse_index(istate->repo);
>      @@ sparse-index.c: int convert_to_sparse(struct index_state *istate)
>       +         set_sparse_index_config(istate->repo, test_env);
>
>         /*
>      -   * Only convert to sparse if extensions.sparseIndex is set.
>      +   * Only convert to sparse if index.sparse is set.
>
>        ## sparse-index.h ##
>       @@ sparse-index.h: struct index_state;
>      @@ t/t1092-sparse-checkout-compatibility.sh: init_repos () {
>       - 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
>       + git -C sparse-index sparse-checkout init --cone --sparse-index &&
>      -+ test_cmp_config -C sparse-index true extensions.sparseindex &&
>      ++ test_cmp_config -C sparse-index true index.sparse &&
>       + git -C sparse-index sparse-checkout set deep
>        }
>
>  17:  6f1ad72c390d ! 18:  7f55a232e647 sparse-checkout: disable sparse-index
>      @@ t/t1091-sparse-checkout-builtin.sh: test_expect_success 'sparse-checkout disable
>
>       +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_cmp_config -C repo true index.sparse &&
>       + test-tool -C repo read-cache --table >cache &&
>       + grep " tree " cache &&
>       +
>      @@ t/t1091-sparse-checkout-builtin.sh: test_expect_success 'sparse-checkout disable
>       + test-tool -C repo read-cache --table >cache &&
>       + ! grep " tree " cache &&
>       + git -C repo config --list >config &&
>      -+ ! grep extensions.sparseindex config
>      ++ ! grep index.sparse config
>       +'
>       +
>        test_expect_success 'cone mode: init and set' '
>  18:  bd94e6b7d089 = 19:  365901809d9d cache-tree: integrate with sparse directory entries
>  19:  e7190376b806 = 20:  9b068c458898 sparse-index: loose integration with cache_tree_verify()
>  20:  bcf0a58eb38c = 21:  66602733cc95 p2000: add sparse-index repos