{"thread":{"id":"57888","subject":"[PATCH 0/8] Sparse index: integrate with sparse-checkout","startedAt":"2022-05-16T18:11:48Z","lastAt":"2022-05-25T16:32:30Z","messageCount":55,"participants":["Derrick Stolee via GitGitGadget","Victoria Dye","Derrick Stolee","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":8},"messages":[{"id":"455332","messageId":"pull.1208.git.1652724693.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":null,"subject":"[PATCH 0/8] Sparse index: integrate with sparse-checkout","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-16T18:11:25Z","receivedAt":"2022-05-16T18:11:48Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"This series is based on ds/sparse-colon-path.\n\nThis series integrates the 'git sparse-checkout' builtin with the sparse\nindex. This is the last integration that we fast-tracked into the\nmicrosoft/git fork. After this, we have no work in flight that would\nconflict with a Google Summer of Code project in this area.\n\nThe tricky part about the sparse-checkout builtin is that we actually do\nneed to expand the index when growing the sparse-checkout boundary. The\ntrick is to expand it only as far as we need it, and then ensure that we\ncollapse any removed directories before the command completes.\n\nTo do this, we introduce a concept of a \"partially expanded\" index. In fact,\nwe break the boolean sparse_index member into an enum with three states:\n\n * COMPLETELY_FULL (0): No sparse directories exist.\n\n * COMPLETELY_SPARSE (1): Sparse directories may exist. Files outside the\n sparse-checkout cone are reduced to sparse directory entries whenever\n possible.\n\n * PARTIALLY_SPARSE (2): Sparse directories may exist. Some file entries\n outside the sparse-checkout cone may exist. Running convert_to_sparse()\n may further reduce those files to sparse directory entries.\n\nMost of the patches in this series focus on introducing this enum and\ncarefully converting previous uses of the boolean to use the enum. Some\nadditional work is required to refactor ensure_full_index() into a new\nexpand_to_pattern_list() method, as they are doing essentially the same\nthing, but with different scopes.\n\nThe result is improved performance on the sparse-checkout builtin as\ndemonstrated in a new p2000-sparse-operations.sh performance test:\n\n\nTest HEAD~1 HEAD\n================\n\n2000.24: git sparse-checkout ... (sparse-v3) 2.14(1.55+0.58) 1.57(1.03+0.53)\n-26.6% 2000.25: git sparse-checkout ... (sparse-v4) 2.20(1.62+0.57)\n1.58(0.98+0.59) -28.2%\n\nThe improvement here is less dramatic because the operation is dominated by\nwriting and deleting a lot of files in the worktree. A repeated no-op\noperation such as git sparse-checkout set $SPARSE_CONE would show a greater\nimprovement, but is less interesting since it could gain that improvement\nwithout satisfying the \"hard\" parts of this builtin.\n\nI specifically chose how to update the tests in t1092 and p2000 to avoid\nconflicts with Victoria's 'git stash' work.\n\nThanks, -Stolee\n\nDerrick Stolee (8):\n sparse-index: create expand_to_pattern_list()\n sparse-index: introduce partially-sparse indexes\n cache-tree: implement cache_tree_find_path()\n sparse-checkout: --no-sparse-index needs a full index\n sparse-index: partially expand directories\n sparse-index: complete partial expansion\n p2000: add test for 'git sparse-checkout [add|set]'\n sparse-checkout: integrate with sparse index\n\n builtin/sparse-checkout.c | 8 +-\n cache-tree.c | 24 +++++\n cache-tree.h | 2 +\n cache.h | 32 ++++--\n read-cache.c | 6 +-\n sparse-index.c | 126 ++++++++++++++++++++---\n sparse-index.h | 14 +++\n t/perf/p2000-sparse-operations.sh | 1 +\n t/t1092-sparse-checkout-compatibility.sh | 25 +++++\n unpack-trees.c | 4 +\n 10 files changed, 214 insertions(+), 28 deletions(-)\n\n\nbase-commit: 124b05b23005437fa5fb91863bde2a8f5840e164\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1208%2Fderrickstolee%2Fsparse-index%2Fsparse-checkout-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1208/derrickstolee/sparse-index/sparse-checkout-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/1208\n-- \ngitgitgadget\n"},{"id":"455333","messageId":"f1194d56d331611446c285a1d070509d73bd5f43.1652724693.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.git.1652724693.gitgitgadget@gmail.com","subject":"[PATCH 1/8] sparse-index: create expand_to_pattern_list()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-16T18:11:26Z","receivedAt":"2022-05-16T18:11:51Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThis is the first change in a series to allow modifying the\nsparse-checkout pattern set without expanding a sparse index to a full\none in the process. Here, we focus on the problem of expanding the\npattern set through a command like 'git sparse-checkout add '\nwhich needs to create new index entries for the paths now being written\nto the worktree.\n\nTo achieve this, we need to be able to replace sparse directory entries\nwith their contained files and subdirectories. Once this is complete,\nother code paths can discover those cache entries and write the\ncorresponding files to disk before committing the index.\n\nWe already have logic in ensure_full_index() that expands the index\nentries, so we will use that as our base. Create a new method,\nexpand_to_pattern_list(), which takes a pattern list, but for now mostly\nignores it. The current implementation is only correct when the pattern\nlist is NULL as that does the same as ensure_full_index(). In fact,\nensure_full_index() is converted to a shim over\nexpand_to_pattern_list().\n\nA future update will actually implement expand_to_pattern_list() to its\nfull capabilities. For now, it is created and documented.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 35 ++++++++++++++++++++++++++++++++---\n sparse-index.h | 14 ++++++++++++++\n 2 files changed, 46 insertions(+), 3 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex 8636af72de5..37c7df877a6 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -248,19 +248,41 @@ static int add_path_to_index(const struct object_id *oid,\n \treturn 0;\n }\n \n-void ensure_full_index(struct index_state *istate)\n+void expand_to_pattern_list(struct index_state *istate,\n+\t\t\t struct pattern_list *pl)\n {\n \tint i;\n \tstruct index_state *full;\n \tstruct strbuf base = STRBUF_INIT;\n \n+\t/*\n+\t * If the index is already full, then keep it full. We will convert\n+\t * it to a sparse index on write, if possible.\n+\t */\n \tif (!istate || !istate->sparse_index)\n \t\treturn;\n \n+\t/*\n+\t * If our index is sparse, but our new pattern set does not use\n+\t * cone mode patterns, then we need to expand the index before we\n+\t * continue. A NULL pattern set indicates a full expansion to a\n+\t * full index.\n+\t */\n+\tif (pl && !pl->use_cone_patterns)\n+\t\tpl = NULL;\n+\n \tif (!istate->repo)\n \t\tistate->repo = the_repository;\n \n-\ttrace2_region_enter(\"index\", \"ensure_full_index\", istate->repo);\n+\t/*\n+\t * A NULL pattern set indicates we are expanding a full index, so\n+\t * we use a special region name that indicates the full expansion.\n+\t * This is used by test cases, but also helps to differentiate the\n+\t * two cases.\n+\t */\n+\ttrace2_region_enter(\"index\",\n+\t\t\t pl ? \"expand_to_pattern_list\" : \"ensure_full_index\",\n+\t\t\t istate->repo);\n \n \t/* initialize basics of new index */\n \tfull = xcalloc(1, sizeof(struct index_state));\n@@ -322,7 +344,14 @@ void ensure_full_index(struct index_state *istate)\n \tcache_tree_free(&istate->cache_tree);\n \tcache_tree_update(istate, 0);\n \n-\ttrace2_region_leave(\"index\", \"ensure_full_index\", istate->repo);\n+\ttrace2_region_leave(\"index\",\n+\t\t\t pl ? \"expand_to_pattern_list\" : \"ensure_full_index\",\n+\t\t\t istate->repo);\n+}\n+\n+void ensure_full_index(struct index_state *istate)\n+{\n+\texpand_to_pattern_list(istate, NULL);\n }\n \n void ensure_correct_sparsity(struct index_state *istate)\ndiff --git a/sparse-index.h b/sparse-index.h\nindex 633d4fb7e31..037b541f49d 100644\n--- a/sparse-index.h\n+++ b/sparse-index.h\n@@ -23,4 +23,18 @@ void expand_to_path(struct index_state *istate,\n struct repository;\n int set_sparse_index_config(struct repository *repo, int enable);\n \n+struct pattern_list;\n+\n+/**\n+ * Scan the given index and compare its entries to the given pattern list.\n+ * If the index is sparse and the pattern list uses cone mode patterns,\n+ * then modify the index to contain the all of the file entries within that\n+ * new pattern list. This expands sparse directories only as far as needed.\n+ *\n+ * If the pattern list is NULL or does not use cone mode patterns, then the\n+ * index is expanded to a full index.\n+ */\n+void expand_to_pattern_list(struct index_state *istate,\n+\t\t\t struct pattern_list *pl);\n+\n #endif\n-- \ngitgitgadget\n\n"},{"id":"455334","messageId":"d1fb2e0e0d3df29e38c92b0e5d24ff797bfa53b0.1652724693.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.git.1652724693.gitgitgadget@gmail.com","subject":"[PATCH 4/8] sparse-checkout: --no-sparse-index needs a full index","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-16T18:11:29Z","receivedAt":"2022-05-16T18:11:55Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nWhen the --no-sparse-index option is supplied, the sparse-checkout\nbuiltin should explicitly ask to expand a sparse index to a full one.\nThis is currently done implicitly due to the command_requires_full_index\nprotection, but that will be removed in an upcoming change.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/sparse-checkout.c | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\nindex 88eea069ad4..cbff6ad00b0 100644\n--- a/builtin/sparse-checkout.c\n+++ b/builtin/sparse-checkout.c\n@@ -413,6 +413,9 @@ static int update_modes(int *cone_mode, int *sparse_index)\n \t\t/* force an index rewrite */\n \t\trepo_read_index(the_repository);\n \t\tthe_repository->index->updated_workdir = 1;\n+\n+\t\tif (!*sparse_index)\n+\t\t\tensure_full_index(the_repository->index);\n \t}\n \n \treturn 0;\n-- \ngitgitgadget\n\n"},{"id":"455335","messageId":"d394d0e20e87c0bf7537b27a05f5afce3a84421d.1652724693.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.git.1652724693.gitgitgadget@gmail.com","subject":"[PATCH 2/8] sparse-index: introduce partially-sparse indexes","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-16T18:11:27Z","receivedAt":"2022-05-16T18:11:58Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nA future change will present a temporary, in-memory mode where the index\ncan both contain sparse directory entries but also not be completely\ncollapsed to the smallest possible sparse directories. This will be\nnecessary for modifying the sparse-checkout definition while using a\nsparse index.\n\nFor now, convert the single-bit member 'sparse_index' in 'struct\nindex_state' to be a an 'enum sparse_index_mode' with three modes:\n\n* COMPLETELY_FULL (0): No sparse directories exist.\n\n* COMPLETELY_SPARSE (1): Sparse directories may exist. Files outside the\n sparse-checkout cone are reduced to sparse directory entries whenever\n possible.\n\n* PARTIALLY_SPARSE (2): Sparse directories may exist. Some file entries\n outside the sparse-checkout cone may exist. Running\n convert_to_sparse() may further reduce those files to sparse directory\n entries.\n\nThe main reason to store this extra information is to allow\nconvert_to_sparse() to short-circuit when the index is already in\nCOMPLETELY_SPARSE mode but to actually do the necessary work when in\nPARTIALLY_SPARSE mode.\n\nThe PARTIALLY_SPARSE mode will be used in an upcoming change.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/sparse-checkout.c | 2 +-\n cache.h | 32 ++++++++++++++++++++++++--------\n read-cache.c | 6 +++---\n sparse-index.c | 6 +++---\n 4 files changed, 31 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\nindex 0217d44c5b1..88eea069ad4 100644\n--- a/builtin/sparse-checkout.c\n+++ b/builtin/sparse-checkout.c\n@@ -128,7 +128,7 @@ static void clean_tracked_sparse_directories(struct repository *r)\n \t * sparse index will not delete directories that contain\n \t * conflicted entries or submodules.\n \t */\n-\tif (!r->index->sparse_index) {\n+\tif (r->index->sparse_index == COMPLETELY_FULL) {\n \t\t/*\n \t\t * If something, such as a merge conflict or other concern,\n \t\t * prevents us from converting to a sparse index, then do\ndiff --git a/cache.h b/cache.h\nindex 6226f6a8a53..2d067aca2fd 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -310,6 +310,28 @@ struct untracked_cache;\n struct progress;\n struct pattern_list;\n \n+enum sparse_index_mode {\n+\t/*\n+\t * COMPLETELY_FULL: there are no sparse directories\n+\t * in the index at all.\n+\t */\n+\tCOMPLETELY_FULL = 0,\n+\n+\t/*\n+\t * COLLAPSED: the index has already been collapsed to sparse\n+\t * directories whereever possible.\n+\t */\n+\tCOLLAPSED = 1,\n+\n+\t/*\n+\t * PARTIALLY_SPARSE: the sparse directories that exist are\n+\t * outside the sparse-checkout boundary, but it is possible\n+\t * that some file entries could collapse to sparse directory\n+\t * entries.\n+\t */\n+\tPARTIALLY_SPARSE = 2,\n+};\n+\n struct index_state {\n \tstruct cache_entry **cache;\n \tunsigned int version;\n@@ -323,14 +345,8 @@ struct index_state {\n \t\t drop_cache_tree : 1,\n \t\t updated_workdir : 1,\n \t\t updated_skipworktree : 1,\n-\t\t fsmonitor_has_run_once : 1,\n-\n-\t\t /*\n-\t\t * sparse_index == 1 when sparse-directory\n-\t\t * entries exist. Requires sparse-checkout\n-\t\t * in cone mode.\n-\t\t */\n-\t\t sparse_index : 1;\n+\t\t fsmonitor_has_run_once : 1;\n+\tenum sparse_index_mode sparse_index;\n \tstruct hashmap name_hash;\n \tstruct hashmap dir_hash;\n \tstruct object_id oid;\ndiff --git a/read-cache.c b/read-cache.c\nindex 4df97e185e9..cb9b33169fd 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -112,7 +112,7 @@ static const char *alternate_index_output;\n static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)\n {\n \tif (S_ISSPARSEDIR(ce->ce_mode))\n-\t\tistate->sparse_index = 1;\n+\t\tistate->sparse_index = COLLAPSED;\n \n \tistate->cache[nr] = ce;\n \tadd_name_hash(istate, ce);\n@@ -1856,7 +1856,7 @@ static int read_index_extension(struct index_state *istate,\n \t\tbreak;\n \tcase CACHE_EXT_SPARSE_DIRECTORIES:\n \t\t/* no content, only an indicator */\n-\t\tistate->sparse_index = 1;\n+\t\tistate->sparse_index = COLLAPSED;\n \t\tbreak;\n \tdefault:\n \t\tif (*ext < 'A' || 'Z' < *ext)\n@@ -3149,7 +3149,7 @@ static int do_write_locked_index(struct index_state *istate, struct lock_file *l\n \t\t\t\t unsigned flags)\n {\n \tint ret;\n-\tint was_full = !istate->sparse_index;\n+\tint was_full = istate->sparse_index == COMPLETELY_FULL;\n \n \tret = convert_to_sparse(istate, 0);\n \ndiff --git a/sparse-index.c b/sparse-index.c\nindex 37c7df877a6..79e8ff087bc 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -173,7 +173,7 @@ int convert_to_sparse(struct index_state *istate, int flags)\n \t * If the index is already sparse, empty, or otherwise\n \t * cannot be converted to sparse, do not convert.\n \t */\n-\tif (istate->sparse_index || !istate->cache_nr ||\n+\tif (istate->sparse_index == COLLAPSED || !istate->cache_nr ||\n \t !is_sparse_index_allowed(istate, flags))\n \t\treturn 0;\n \n@@ -214,7 +214,7 @@ int convert_to_sparse(struct index_state *istate, int flags)\n \tFREE_AND_NULL(istate->fsmonitor_dirty);\n \tFREE_AND_NULL(istate->fsmonitor_last_update);\n \n-\tistate->sparse_index = 1;\n+\tistate->sparse_index = COLLAPSED;\n \ttrace2_region_leave(\"index\", \"convert_to_sparse\", istate->repo);\n \treturn 0;\n }\n@@ -259,7 +259,7 @@ void expand_to_pattern_list(struct index_state *istate,\n \t * If the index is already full, then keep it full. We will convert\n \t * it to a sparse index on write, if possible.\n \t */\n-\tif (!istate || !istate->sparse_index)\n+\tif (!istate || istate->sparse_index == COMPLETELY_FULL)\n \t\treturn;\n \n \t/*\n-- \ngitgitgadget\n\n"},{"id":"455337","messageId":"eba63cc12af4f60320b34a54eef691b9f59d86bc.1652724693.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.git.1652724693.gitgitgadget@gmail.com","subject":"[PATCH 6/8] sparse-index: complete partial expansion","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-16T18:11:31Z","receivedAt":"2022-05-16T18:11:59Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nTo complete the implementation of expand_to_pattern_list(), we need to\ndetect when a sparse directory entry should remain sparse. This avoids a\nfull expansion, so we now need to use the PARTIALLY_SPARSE mode to\nindicate this state.\n\nThere still are no callers to this method, but we will add one in the\nnext change.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 41 +++++++++++++++++++++++++++++++++++++----\n 1 file changed, 37 insertions(+), 4 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex 3d8eed585b5..0bad5503304 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -297,8 +297,24 @@ void expand_to_pattern_list(struct index_state *istate,\n \t * continue. A NULL pattern set indicates a full expansion to a\n \t * full index.\n \t */\n-\tif (pl && !pl->use_cone_patterns)\n+\tif (pl && !pl->use_cone_patterns) {\n \t\tpl = NULL;\n+\t} else {\n+\t\t/*\n+\t\t * We might contract file entries into sparse-directory\n+\t\t * entries, and for that we will need the cache tree to\n+\t\t * be recomputed.\n+\t\t */\n+\t\tcache_tree_free(&istate->cache_tree);\n+\n+\t\t/*\n+\t\t * If there is a problem creating the cache tree, then we\n+\t\t * need to expand to a full index since we cannot satisfy\n+\t\t * the current request as a sparse index.\n+\t\t */\n+\t\tif (cache_tree_update(istate, WRITE_TREE_MISSING_OK))\n+\t\t\tpl = NULL;\n+\t}\n \n \tif (!istate->repo)\n \t\tistate->repo = the_repository;\n@@ -317,8 +333,14 @@ void expand_to_pattern_list(struct index_state *istate,\n \tfull = xcalloc(1, sizeof(struct index_state));\n \tmemcpy(full, istate, sizeof(struct index_state));\n \n+\t/*\n+\t * This slightly-misnamed 'full' index might still be sparse if we\n+\t * are only modifying the list of sparse directories. This hinges\n+\t * on whether we have a non-NULL pattern list.\n+\t */\n+\tfull->sparse_index = pl ? PARTIALLY_SPARSE : COMPLETELY_FULL;\n+\n \t/* then change the necessary things */\n-\tfull->sparse_index = 0;\n \tfull->cache_alloc = (3 * istate->cache_alloc) / 2;\n \tfull->cache_nr = 0;\n \tALLOC_ARRAY(full->cache, full->cache_alloc);\n@@ -330,11 +352,22 @@ void expand_to_pattern_list(struct index_state *istate,\n \t\tstruct cache_entry *ce = istate->cache[i];\n \t\tstruct tree *tree;\n \t\tstruct pathspec ps;\n+\t\tint dtype;\n \n \t\tif (!S_ISSPARSEDIR(ce->ce_mode)) {\n \t\t\tset_index_entry(full, full->cache_nr++, ce);\n \t\t\tcontinue;\n \t\t}\n+\n+\t\t/* We now have a sparse directory entry. Should we expand? */\n+\t\tif (pl &&\n+\t\t path_matches_pattern_list(ce->name, ce->ce_namelen,\n+\t\t\t\t\t NULL, &dtype,\n+\t\t\t\t\t pl, istate) <= 0) {\n+\t\t\tset_index_entry(full, full->cache_nr++, ce);\n+\t\t\tcontinue;\n+\t\t}\n+\n \t\tif (!(ce->ce_flags & CE_SKIP_WORKTREE))\n \t\t\twarning(_(\"index entry is a directory, but not sparse (%08x)\"),\n \t\t\t\tce->ce_flags);\n@@ -360,7 +393,7 @@ void expand_to_pattern_list(struct index_state *istate,\n \t/* Copy back into original index. */\n \tmemcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));\n \tmemcpy(&istate->dir_hash, &full->dir_hash, sizeof(full->dir_hash));\n-\tistate->sparse_index = 0;\n+\tistate->sparse_index = pl ? PARTIALLY_SPARSE : COMPLETELY_FULL;\n \tfree(istate->cache);\n \tistate->cache = full->cache;\n \tistate->cache_nr = full->cache_nr;\n@@ -374,7 +407,7 @@ void expand_to_pattern_list(struct index_state *istate,\n \n \t/* Clear and recompute the cache-tree */\n \tcache_tree_free(&istate->cache_tree);\n-\tcache_tree_update(istate, 0);\n+\tcache_tree_update(istate, WRITE_TREE_MISSING_OK);\n \n \ttrace2_region_leave(\"index\",\n \t\t\t pl ? \"expand_to_pattern_list\" : \"ensure_full_index\",\n-- \ngitgitgadget\n\n"},{"id":"455336","messageId":"2804326c8bb0f70ca43e68c03789f32ad628cfaa.1652724693.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.git.1652724693.gitgitgadget@gmail.com","subject":"[PATCH 7/8] p2000: add test for 'git sparse-checkout [add|set]'","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-16T18:11:32Z","receivedAt":"2022-05-16T18:12:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe sparse-checkout builtin is almost completely integrated with the\nsparse index, allowing the sparse-checkout boundary to be modified\nwithout expanding a sparse index to a full one. Add a test to\np2000-sparse-operations.sh that adds a directory to the sparse-checkout\ndefinition, then removes it. Using both operations is important to\nensure that the operation is doing the same work in each repetition as\nwell as leaving the test repo in a good state for later tests.\n\nSigned-off-by: Derrick Stolee \n---\n t/perf/p2000-sparse-operations.sh | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/t/perf/p2000-sparse-operations.sh b/t/perf/p2000-sparse-operations.sh\nindex 382716cfca9..ce5cfac5714 100755\n--- a/t/perf/p2000-sparse-operations.sh\n+++ b/t/perf/p2000-sparse-operations.sh\n@@ -110,6 +110,7 @@ test_perf_on_all git add -A\n test_perf_on_all git add .\n test_perf_on_all git commit -a -m A\n test_perf_on_all git checkout -f -\n+test_perf_on_all \"git sparse-checkout add f2/f3/f1 && git sparse-checkout set $SPARSE_CONE\"\n test_perf_on_all git reset\n test_perf_on_all git reset --hard\n test_perf_on_all git reset -- does-not-exist\n-- \ngitgitgadget\n\n"},{"id":"455338","messageId":"5c7546ab07080b43972b265eb2eee3de0c5396a2.1652724693.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.git.1652724693.gitgitgadget@gmail.com","subject":"[PATCH 5/8] sparse-index: partially expand directories","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-16T18:11:30Z","receivedAt":"2022-05-16T18:12:04Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe expand_to_pattern_list() method expands sparse directory entries\nto their list of contained files when either the pattern list is NULL or\nthe directory is contained in the new pattern list's cone mode patterns.\n\nIt is possible that the pattern list has a recursive match with a\ndirectory 'A/B/C/' and so an existing sparse directory 'A/B/' would need\nto be expanded. If there exists a directory 'A/B/D/', then that\ndirectory should not be expanded and instead we can create a sparse\ndirectory.\n\nTo implement this, we plug into the add_path_to_index() callback for the\ncall to read_tree_at(). Since we now need access to both the index we\nare writing and the pattern list we are comparing, create a 'struct\nmodify_index_context' to use as a data transfer object. It is important\nthat we use the given pattern list since we will use this pattern list\nto change the sparse-checkout patterns and cannot use\nistate->sparse_checkout_patterns.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 46 +++++++++++++++++++++++++++++++++++++++-------\n 1 file changed, 39 insertions(+), 7 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex 79e8ff087bc..3d8eed585b5 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -9,6 +9,11 @@\n #include \"dir.h\"\n #include \"fsmonitor.h\"\n \n+struct modify_index_context {\n+\tstruct index_state *write;\n+\tstruct pattern_list *pl;\n+};\n+\n static struct cache_entry *construct_sparse_dir_entry(\n \t\t\t\tstruct index_state *istate,\n \t\t\t\tconst char *sparse_dir,\n@@ -231,18 +236,41 @@ static int add_path_to_index(const struct object_id *oid,\n \t\t\t struct strbuf *base, const char *path,\n \t\t\t unsigned int mode, void *context)\n {\n-\tstruct index_state *istate = (struct index_state *)context;\n+\tstruct modify_index_context *ctx = (struct modify_index_context *)context;\n \tstruct cache_entry *ce;\n \tsize_t len = base->len;\n \n-\tif (S_ISDIR(mode))\n-\t\treturn READ_TREE_RECURSIVE;\n+\tif (S_ISDIR(mode)) {\n+\t\tint dtype;\n+\t\tsize_t baselen = base->len;\n+\t\tif (!ctx->pl)\n+\t\t\treturn READ_TREE_RECURSIVE;\n \n-\tstrbuf_addstr(base, path);\n+\t\t/*\n+\t\t * Have we expanded to a point outside of the sparse-checkout?\n+\t\t */\n+\t\tstrbuf_addstr(base, path);\n+\t\tstrbuf_add(base, \"/-\", 2);\n+\n+\t\tif (path_matches_pattern_list(base->buf, base->len,\n+\t\t\t\t\t NULL, &dtype,\n+\t\t\t\t\t ctx->pl, ctx->write)) {\n+\t\t\tstrbuf_setlen(base, baselen);\n+\t\t\treturn READ_TREE_RECURSIVE;\n+\t\t}\n \n-\tce = make_cache_entry(istate, mode, oid, base->buf, 0, 0);\n+\t\t/*\n+\t\t * The path \"{base}{path}/\" is a sparse directory. Create the correct\n+\t\t * name for inserting the entry into the idnex.\n+\t\t */\n+\t\tstrbuf_setlen(base, base->len - 1);\n+\t} else {\n+\t\tstrbuf_addstr(base, path);\n+\t}\n+\n+\tce = make_cache_entry(ctx->write, mode, oid, base->buf, 0, 0);\n \tce->ce_flags |= CE_SKIP_WORKTREE | CE_EXTENDED;\n-\tset_index_entry(istate, istate->cache_nr++, ce);\n+\tset_index_entry(ctx->write, ctx->write->cache_nr++, ce);\n \n \tstrbuf_setlen(base, len);\n \treturn 0;\n@@ -254,6 +282,7 @@ void expand_to_pattern_list(struct index_state *istate,\n \tint i;\n \tstruct index_state *full;\n \tstruct strbuf base = STRBUF_INIT;\n+\tstruct modify_index_context ctx;\n \n \t/*\n \t * If the index is already full, then keep it full. We will convert\n@@ -294,6 +323,9 @@ void expand_to_pattern_list(struct index_state *istate,\n \tfull->cache_nr = 0;\n \tALLOC_ARRAY(full->cache, full->cache_alloc);\n \n+\tctx.write = full;\n+\tctx.pl = pl;\n+\n \tfor (i = 0; i < istate->cache_nr; i++) {\n \t\tstruct cache_entry *ce = istate->cache[i];\n \t\tstruct tree *tree;\n@@ -319,7 +351,7 @@ void expand_to_pattern_list(struct index_state *istate,\n \t\tstrbuf_add(&base, ce->name, strlen(ce->name));\n \n \t\tread_tree_at(istate->repo, tree, &base, &ps,\n-\t\t\t add_path_to_index, full);\n+\t\t\t add_path_to_index, &ctx);\n \n \t\t/* free directory entries. full entries are re-used */\n \t\tdiscard_cache_entry(ce);\n-- \ngitgitgadget\n\n"},{"id":"455339","messageId":"c0e81be97aa50c808ebf44d1833e915e19901d60.1652724693.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.git.1652724693.gitgitgadget@gmail.com","subject":"[PATCH 3/8] cache-tree: implement cache_tree_find_path()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-16T18:11:28Z","receivedAt":"2022-05-16T18:12:08Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nGiven a 'struct cache_tree', it may be beneficial to navigate directly\nto a node within that corresponds to a given path name. Create\ncache_tree_find_path() for this function. It returns NULL when no such\npath exists.\n\nThe implementation is adapted from do_invalidate_path() which does a\nsimilar search but also modifies the nodes it finds along the way.\n\nThis new method is not currently used, but will be in an upcoming\nchange.\n\nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 24 ++++++++++++++++++++++++\n cache-tree.h | 2 ++\n 2 files changed, 26 insertions(+)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 6752f69d515..23893a7b113 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -100,6 +100,30 @@ struct cache_tree_sub *cache_tree_sub(struct cache_tree *it, const char *path)\n \treturn find_subtree(it, path, pathlen, 1);\n }\n \n+struct cache_tree *cache_tree_find_path(struct cache_tree *it, const char *path)\n+{\n+\tconst char *slash;\n+\tint namelen;\n+\tstruct cache_tree_sub *down;\n+\n+\tif (!it)\n+\t\treturn NULL;\n+\tslash = strchrnul(path, '/');\n+\tnamelen = slash - path;\n+\tit->entry_count = -1;\n+\tif (!*slash) {\n+\t\tint pos;\n+\t\tpos = cache_tree_subtree_pos(it, path, namelen);\n+\t\tif (0 <= pos)\n+\t\t\treturn it->down[pos]->cache_tree;\n+\t\treturn NULL;\n+\t}\n+\tdown = find_subtree(it, path, namelen, 0);\n+\tif (down)\n+\t\treturn cache_tree_find_path(down->cache_tree, slash + 1);\n+\treturn NULL;\n+}\n+\n static int do_invalidate_path(struct cache_tree *it, const char *path)\n {\n \t/* a/b/c\ndiff --git a/cache-tree.h b/cache-tree.h\nindex 8efeccebfc9..f75f8e74dcd 100644\n--- a/cache-tree.h\n+++ b/cache-tree.h\n@@ -29,6 +29,8 @@ struct cache_tree_sub *cache_tree_sub(struct cache_tree *, const char *);\n \n int cache_tree_subtree_pos(struct cache_tree *it, const char *path, int pathlen);\n \n+struct cache_tree *cache_tree_find_path(struct cache_tree *it, const char *path);\n+\n void cache_tree_write(struct strbuf *, struct cache_tree *root);\n struct cache_tree *cache_tree_read(const char *buffer, unsigned long size);\n \n-- \ngitgitgadget\n\n"},{"id":"455340","messageId":"b8a349c6deeb4b970075629d0c292b2ae9f7d0d3.1652724693.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.git.1652724693.gitgitgadget@gmail.com","subject":"[PATCH 8/8] sparse-checkout: integrate with sparse index","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-16T18:11:33Z","receivedAt":"2022-05-16T18:12:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nWhen modifying the sparse-checkout definition, the sparse-checkout\nbuiltin calls update_sparsity() to modify the SKIP_WORKTREE bits of all\ncache entries in the index. Before, we needed the index to be fully\nexpanded in order to ensure we had the full list of files necessary that\nmatch the new patterns.\n\nInsert a call to reset_sparse_directories() that expands sparse\ndirectories that are within the new pattern list, but only far enough\nthat every necessary file path now exists as a cache entry. The\nremaining logic within update_sparsity() will modify the SKIP_WORKTREE\nbits appropriately.\n\nThis allows us to disable command_requires_full_index within the\nsparse-checkout builtin. Add tests that demonstrate that we are not\nexpanding to a full index unnecessarily.\n\nWe can see the improved performance in the p2000 test script:\n\nTest HEAD~1 HEAD\n------------------------------------------------------------------------\n2000.24: git ... (sparse-v3) 2.14(1.55+0.58) 1.57(1.03+0.53) -26.6%\n2000.25: git ... (sparse-v4) 2.20(1.62+0.57) 1.58(0.98+0.59) -28.2%\n\nThese reductions of 26-28% are small compared to most examples, but the\ntime is dominated by writing a new copy of the base repository to the\nworktree and then deleting it again. The fact that the previous index\nexpansion was such a large portion of the time is telling how important\nit is to complete this sparse index integration.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/sparse-checkout.c | 3 +++\n t/t1092-sparse-checkout-compatibility.sh | 25 ++++++++++++++++++++++++\n unpack-trees.c | 4 ++++\n 3 files changed, 32 insertions(+)\n\ndiff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\nindex cbff6ad00b0..0157b292b36 100644\n--- a/builtin/sparse-checkout.c\n+++ b/builtin/sparse-checkout.c\n@@ -937,6 +937,9 @@ int cmd_sparse_checkout(int argc, const char **argv, const char *prefix)\n \n \tgit_config(git_default_config, NULL);\n \n+\tprepare_repo_settings(the_repository);\n+\tthe_repository->settings.command_requires_full_index = 0;\n+\n \tif (argc > 0) {\n \t\tif (!strcmp(argv[0], \"list\"))\n \t\t\treturn sparse_checkout_list(argc, argv);\ndiff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\nindex 93bcfd20bbc..614357fc48c 100755\n--- a/t/t1092-sparse-checkout-compatibility.sh\n+++ b/t/t1092-sparse-checkout-compatibility.sh\n@@ -1552,6 +1552,31 @@ test_expect_success 'ls-files' '\n \tensure_not_expanded ls-files --sparse\n '\n \n+test_expect_success 'sparse index is not expanded: sparse-checkout' '\n+\tinit_repos &&\n+\n+\tensure_not_expanded sparse-checkout set deep/deeper2 &&\n+\tensure_not_expanded sparse-checkout set deep/deeper1 &&\n+\tensure_not_expanded sparse-checkout set deep &&\n+\tensure_not_expanded sparse-checkout add folder1 &&\n+\tensure_not_expanded sparse-checkout set deep/deeper1 &&\n+\tensure_not_expanded sparse-checkout set folder2 &&\n+\n+\t# Demonstrate that the checks that \"folder1/a\" is a file\n+\t# do not cause a sparse-index expansion (since it is in the\n+\t# sparse-checkout cone).\n+\techo >>sparse-index/folder2/a &&\n+\tgit -C sparse-index add folder2/a &&\n+\n+\tensure_not_expanded sparse-checkout add folder1 &&\n+\n+\t# Skip checks here, since deep/deeper1 is inside a sparse directory\n+\t# that must be expanded to check whether `deep/deeper1` is a file\n+\t# or not.\n+\tensure_not_expanded sparse-checkout set --skip-checks deep/deeper1 &&\n+\tensure_not_expanded sparse-checkout set\n+'\n+\n # NEEDSWORK: a sparse-checkout behaves differently from a full checkout\n # in this scenario, but it shouldn't.\n test_expect_success 'reset mixed and checkout orphan' '\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 7f528d35cc2..9745e0dfc34 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -18,6 +18,7 @@\n #include \"promisor-remote.h\"\n #include \"entry.h\"\n #include \"parallel-checkout.h\"\n+#include \"sparse-index.h\"\n \n /*\n * Error messages expected by scripts out of plumbing commands such as\n@@ -2018,6 +2019,9 @@ enum update_sparsity_result update_sparsity(struct unpack_trees_options *o)\n \t\t\tgoto skip_sparse_checkout;\n \t}\n \n+\t/* Expand sparse directories as needed */\n+\texpand_to_pattern_list(o->src_index, o->pl);\n+\n \t/* Set NEW_SKIP_WORKTREE on existing entries. */\n \tmark_all_ce_unused(o->src_index);\n \tmark_new_skip_worktree(o->pl, o->src_index, 0,\n-- \ngitgitgadget\n"},{"id":"455359","messageId":"a90af86d-e3dd-e0fe-106a-52123d6ac023@github.com","threadId":"57888","inReplyTo":"5c7546ab07080b43972b265eb2eee3de0c5396a2.1652724693.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 5/8] sparse-index: partially expand directories","fromName":"Victoria Dye","fromEmail":"vdye@github.com","sentAt":"2022-05-16T20:36:56Z","receivedAt":"2022-05-16T21:01:47Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n> \n> The expand_to_pattern_list() method expands sparse directory entries\n> to their list of contained files when either the pattern list is NULL or\n> the directory is contained in the new pattern list's cone mode patterns.\n> \n> It is possible that the pattern list has a recursive match with a\n> directory 'A/B/C/' and so an existing sparse directory 'A/B/' would need\n> to be expanded. If there exists a directory 'A/B/D/', then that\n> directory should not be expanded and instead we can create a sparse\n> directory.\n> \n> To implement this, we plug into the add_path_to_index() callback for the\n> call to read_tree_at(). Since we now need access to both the index we\n> are writing and the pattern list we are comparing, create a 'struct\n> modify_index_context' to use as a data transfer object. It is important\n> that we use the given pattern list since we will use this pattern list\n> to change the sparse-checkout patterns and cannot use\n> istate->sparse_checkout_patterns.\n> \n> Signed-off-by: Derrick Stolee \n> ---\n> sparse-index.c | 46 +++++++++++++++++++++++++++++++++++++++-------\n> 1 file changed, 39 insertions(+), 7 deletions(-)\n> \n> diff --git a/sparse-index.c b/sparse-index.c\n> index 79e8ff087bc..3d8eed585b5 100644\n> --- a/sparse-index.c\n> +++ b/sparse-index.c\n> @@ -9,6 +9,11 @@\n> #include \"dir.h\"\n> #include \"fsmonitor.h\"\n> \n> +struct modify_index_context {\n> +\tstruct index_state *write;\n> +\tstruct pattern_list *pl;\n> +};\n> +\n> static struct cache_entry *construct_sparse_dir_entry(\n> \t\t\t\tstruct index_state *istate,\n> \t\t\t\tconst char *sparse_dir,\n> @@ -231,18 +236,41 @@ static int add_path_to_index(const struct object_id *oid,\n> \t\t\t struct strbuf *base, const char *path,\n> \t\t\t unsigned int mode, void *context)\n> {\n> -\tstruct index_state *istate = (struct index_state *)context;\n> +\tstruct modify_index_context *ctx = (struct modify_index_context *)context;\n> \tstruct cache_entry *ce;\n> \tsize_t len = base->len;\n> \n> -\tif (S_ISDIR(mode))\n> -\t\treturn READ_TREE_RECURSIVE;\n> +\tif (S_ISDIR(mode)) {\n> +\t\tint dtype;\n> +\t\tsize_t baselen = base->len;\n> +\t\tif (!ctx->pl)\n> +\t\t\treturn READ_TREE_RECURSIVE;\n> \n> -\tstrbuf_addstr(base, path);\n> +\t\t/*\n> +\t\t * Have we expanded to a point outside of the sparse-checkout?\n> +\t\t */\n> +\t\tstrbuf_addstr(base, path);\n> +\t\tstrbuf_add(base, \"/-\", 2);\n> +\n> +\t\tif (path_matches_pattern_list(base->buf, base->len,\n> +\t\t\t\t\t NULL, &dtype,\n> +\t\t\t\t\t ctx->pl, ctx->write)) {\n> +\t\t\tstrbuf_setlen(base, baselen);\n> +\t\t\treturn READ_TREE_RECURSIVE;\n> +\t\t}\n> \n> -\tce = make_cache_entry(istate, mode, oid, base->buf, 0, 0);\n> +\t\t/*\n> +\t\t * The path \"{base}{path}/\" is a sparse directory. Create the correct\n> +\t\t * name for inserting the entry into the idnex.\n\ns/idnex/index\n\n> +\t\t */\n> +\t\tstrbuf_setlen(base, base->len - 1);\n> +\t} else {\n> +\t\tstrbuf_addstr(base, path);\n> +\t}\n> +\n> +\tce = make_cache_entry(ctx->write, mode, oid, base->buf, 0, 0);\n> \tce->ce_flags |= CE_SKIP_WORKTREE | CE_EXTENDED;\n> -\tset_index_entry(istate, istate->cache_nr++, ce);\n> +\tset_index_entry(ctx->write, ctx->write->cache_nr++, ce);\n> \n> \tstrbuf_setlen(base, len);\n> \treturn 0;\n> @@ -254,6 +282,7 @@ void expand_to_pattern_list(struct index_state *istate,\n> \tint i;\n> \tstruct index_state *full;\n> \tstruct strbuf base = STRBUF_INIT;\n> +\tstruct modify_index_context ctx;\n> \n> \t/*\n> \t * If the index is already full, then keep it full. We will convert\n> @@ -294,6 +323,9 @@ void expand_to_pattern_list(struct index_state *istate,\n> \tfull->cache_nr = 0;\n> \tALLOC_ARRAY(full->cache, full->cache_alloc);\n> \n> +\tctx.write = full;\n> +\tctx.pl = pl;\n> +\n> \tfor (i = 0; i < istate->cache_nr; i++) {\n> \t\tstruct cache_entry *ce = istate->cache[i];\n> \t\tstruct tree *tree;\n> @@ -319,7 +351,7 @@ void expand_to_pattern_list(struct index_state *istate,\n> \t\tstrbuf_add(&base, ce->name, strlen(ce->name));\n> \n> \t\tread_tree_at(istate->repo, tree, &base, &ps,\n> -\t\t\t add_path_to_index, full);\n> +\t\t\t add_path_to_index, &ctx);\n> \n> \t\t/* free directory entries. full entries are re-used */\n> \t\tdiscard_cache_entry(ce);\n\n"},{"id":"455360","messageId":"9191a98c-087a-39b9-cff3-eb7eccd198ea@github.com","threadId":"57888","inReplyTo":"b8a349c6deeb4b970075629d0c292b2ae9f7d0d3.1652724693.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 8/8] sparse-checkout: integrate with sparse index","fromName":"Victoria Dye","fromEmail":"vdye@github.com","sentAt":"2022-05-16T20:38:28Z","receivedAt":"2022-05-16T21:01:49Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n> \n> When modifying the sparse-checkout definition, the sparse-checkout\n> builtin calls update_sparsity() to modify the SKIP_WORKTREE bits of all\n> cache entries in the index. Before, we needed the index to be fully\n> expanded in order to ensure we had the full list of files necessary that\n> match the new patterns.\n> \n> Insert a call to reset_sparse_directories() that expands sparse\n> directories that are within the new pattern list, but only far enough\n> that every necessary file path now exists as a cache entry. The\n> remaining logic within update_sparsity() will modify the SKIP_WORKTREE\n> bits appropriately.\n> \n> This allows us to disable command_requires_full_index within the\n> sparse-checkout builtin. Add tests that demonstrate that we are not\n> expanding to a full index unnecessarily.\n> \n> We can see the improved performance in the p2000 test script:\n> \n> Test HEAD~1 HEAD\n> ------------------------------------------------------------------------\n> 2000.24: git ... (sparse-v3) 2.14(1.55+0.58) 1.57(1.03+0.53) -26.6%\n> 2000.25: git ... (sparse-v4) 2.20(1.62+0.57) 1.58(0.98+0.59) -28.2%\n> \n> These reductions of 26-28% are small compared to most examples, but the\n> time is dominated by writing a new copy of the base repository to the\n> worktree and then deleting it again. The fact that the previous index\n> expansion was such a large portion of the time is telling how important\n> it is to complete this sparse index integration.\n> \n> Signed-off-by: Derrick Stolee \n> ---\n> builtin/sparse-checkout.c | 3 +++\n> t/t1092-sparse-checkout-compatibility.sh | 25 ++++++++++++++++++++++++\n> unpack-trees.c | 4 ++++\n> 3 files changed, 32 insertions(+)\n> \n> diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\n> index cbff6ad00b0..0157b292b36 100644\n> --- a/builtin/sparse-checkout.c\n> +++ b/builtin/sparse-checkout.c\n> @@ -937,6 +937,9 @@ int cmd_sparse_checkout(int argc, const char **argv, const char *prefix)\n> \n> \tgit_config(git_default_config, NULL);\n> \n> +\tprepare_repo_settings(the_repository);\n> +\tthe_repository->settings.command_requires_full_index = 0;\n> +\n> \tif (argc > 0) {\n> \t\tif (!strcmp(argv[0], \"list\"))\n> \t\t\treturn sparse_checkout_list(argc, argv);\n> diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\n> index 93bcfd20bbc..614357fc48c 100755\n> --- a/t/t1092-sparse-checkout-compatibility.sh\n> +++ b/t/t1092-sparse-checkout-compatibility.sh\n> @@ -1552,6 +1552,31 @@ test_expect_success 'ls-files' '\n> \tensure_not_expanded ls-files --sparse\n> '\n> \n> +test_expect_success 'sparse index is not expanded: sparse-checkout' '\n> +\tinit_repos &&\n> +\n> +\tensure_not_expanded sparse-checkout set deep/deeper2 &&\n> +\tensure_not_expanded sparse-checkout set deep/deeper1 &&\n> +\tensure_not_expanded sparse-checkout set deep &&\n> +\tensure_not_expanded sparse-checkout add folder1 &&\n> +\tensure_not_expanded sparse-checkout set deep/deeper1 &&\n> +\tensure_not_expanded sparse-checkout set folder2 &&\n> +\n> +\t# Demonstrate that the checks that \"folder1/a\" is a file\n> +\t# do not cause a sparse-index expansion (since it is in the\n> +\t# sparse-checkout cone).\n> +\techo >>sparse-index/folder2/a &&\n> +\tgit -C sparse-index add folder2/a &&\n> +\n> +\tensure_not_expanded sparse-checkout add folder1 &&\n> +\n> +\t# Skip checks here, since deep/deeper1 is inside a sparse directory\n> +\t# that must be expanded to check whether `deep/deeper1` is a file\n> +\t# or not.\n> +\tensure_not_expanded sparse-checkout set --skip-checks deep/deeper1 &&\n> +\tensure_not_expanded sparse-checkout set\n> +'\n> +\n\nThese tests look good for ensuring sparsity is preserved, but it'd be nice\nto also have some \"stress tests\" of 'sparse-checkout (add|set)'. The purpose\nwould be to make sure the index has the right contents for various types of\npattern changes, e.g. running 'sparse-checkout (add|set) ', then\nverifying index contents with 'ls-files --sparse'. Paths might be:\n\n- in vs. out of (current) cone\n- match an existing vs. nonexistent directory\n\netc.\n\n> # NEEDSWORK: a sparse-checkout behaves differently from a full checkout\n> # in this scenario, but it shouldn't.\n> test_expect_success 'reset mixed and checkout orphan' '\n> diff --git a/unpack-trees.c b/unpack-trees.c\n> index 7f528d35cc2..9745e0dfc34 100644\n> --- a/unpack-trees.c\n> +++ b/unpack-trees.c\n> @@ -18,6 +18,7 @@\n> #include \"promisor-remote.h\"\n> #include \"entry.h\"\n> #include \"parallel-checkout.h\"\n> +#include \"sparse-index.h\"\n> \n> /*\n> * Error messages expected by scripts out of plumbing commands such as\n> @@ -2018,6 +2019,9 @@ enum update_sparsity_result update_sparsity(struct unpack_trees_options *o)\n> \t\t\tgoto skip_sparse_checkout;\n> \t}\n> \n> +\t/* Expand sparse directories as needed */\n> +\texpand_to_pattern_list(o->src_index, o->pl);\n> +\n> \t/* Set NEW_SKIP_WORKTREE on existing entries. */\n> \tmark_all_ce_unused(o->src_index);\n> \tmark_new_skip_worktree(o->pl, o->src_index, 0,\n\n"},{"id":"455361","messageId":"12df1777-9f02-ca6f-7d17-57aebe25d06c@github.com","threadId":"57888","inReplyTo":"f1194d56d331611446c285a1d070509d73bd5f43.1652724693.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/8] sparse-index: create expand_to_pattern_list()","fromName":"Victoria Dye","fromEmail":"vdye@github.com","sentAt":"2022-05-16T20:36:49Z","receivedAt":"2022-05-16T21:01:51Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n> \n> This is the first change in a series to allow modifying the\n> sparse-checkout pattern set without expanding a sparse index to a full\n> one in the process. Here, we focus on the problem of expanding the\n> pattern set through a command like 'git sparse-checkout add '\n> which needs to create new index entries for the paths now being written\n> to the worktree.\n> \n> To achieve this, we need to be able to replace sparse directory entries\n> with their contained files and subdirectories. Once this is complete,\n> other code paths can discover those cache entries and write the\n> corresponding files to disk before committing the index.\n> \n> We already have logic in ensure_full_index() that expands the index\n> entries, so we will use that as our base. Create a new method,\n> expand_to_pattern_list(), which takes a pattern list, but for now mostly\n> ignores it. The current implementation is only correct when the pattern\n> list is NULL as that does the same as ensure_full_index(). In fact,\n> ensure_full_index() is converted to a shim over\n> expand_to_pattern_list().\n> \n> A future update will actually implement expand_to_pattern_list() to its\n> full capabilities. For now, it is created and documented.\n> \n> Signed-off-by: Derrick Stolee \n> ---\n> sparse-index.c | 35 ++++++++++++++++++++++++++++++++---\n> sparse-index.h | 14 ++++++++++++++\n> 2 files changed, 46 insertions(+), 3 deletions(-)\n> \n> diff --git a/sparse-index.c b/sparse-index.c\n> index 8636af72de5..37c7df877a6 100644\n> --- a/sparse-index.c\n> +++ b/sparse-index.c\n> @@ -248,19 +248,41 @@ static int add_path_to_index(const struct object_id *oid,\n> \treturn 0;\n> }\n> \n> -void ensure_full_index(struct index_state *istate)\n> +void expand_to_pattern_list(struct index_state *istate,\n> +\t\t\t struct pattern_list *pl)\n\nHyper-nit: I don't think this is aligned (it's probably not worth fixing\nunless you end up rerolling for something else).\n\n> {\n> \tint i;\n> \tstruct index_state *full;\n> \tstruct strbuf base = STRBUF_INIT;\n> \n> +\t/*\n> +\t * If the index is already full, then keep it full. We will convert\n> +\t * it to a sparse index on write, if possible.\n> +\t */\n> \tif (!istate || !istate->sparse_index)\n> \t\treturn;\n> \n> +\t/*\n> +\t * If our index is sparse, but our new pattern set does not use\n> +\t * cone mode patterns, then we need to expand the index before we\n> +\t * continue. A NULL pattern set indicates a full expansion to a\n> +\t * full index.\n> +\t */\n> +\tif (pl && !pl->use_cone_patterns)\n> +\t\tpl = NULL;\n> +\n> \tif (!istate->repo)\n> \t\tistate->repo = the_repository;\n> \n> -\ttrace2_region_enter(\"index\", \"ensure_full_index\", istate->repo);\n> +\t/*\n> +\t * A NULL pattern set indicates we are expanding a full index, so\n> +\t * we use a special region name that indicates the full expansion.\n> +\t * This is used by test cases, but also helps to differentiate the\n> +\t * two cases.\n> +\t */\n> +\ttrace2_region_enter(\"index\",\n> +\t\t\t pl ? \"expand_to_pattern_list\" : \"ensure_full_index\",\n> +\t\t\t istate->repo);\n> \n> \t/* initialize basics of new index */\n> \tfull = xcalloc(1, sizeof(struct index_state));\n> @@ -322,7 +344,14 @@ void ensure_full_index(struct index_state *istate)\n> \tcache_tree_free(&istate->cache_tree);\n> \tcache_tree_update(istate, 0);\n> \n> -\ttrace2_region_leave(\"index\", \"ensure_full_index\", istate->repo);\n> +\ttrace2_region_leave(\"index\",\n> +\t\t\t pl ? \"expand_to_pattern_list\" : \"ensure_full_index\",\n> +\t\t\t istate->repo);\n> +}\n> +\n> +void ensure_full_index(struct index_state *istate)\n> +{\n> +\texpand_to_pattern_list(istate, NULL);\n> }\n> \n> void ensure_correct_sparsity(struct index_state *istate)\n> diff --git a/sparse-index.h b/sparse-index.h\n> index 633d4fb7e31..037b541f49d 100644\n> --- a/sparse-index.h\n> +++ b/sparse-index.h\n> @@ -23,4 +23,18 @@ void expand_to_path(struct index_state *istate,\n> struct repository;\n> int set_sparse_index_config(struct repository *repo, int enable);\n> \n> +struct pattern_list;\n> +\n> +/**\n> + * Scan the given index and compare its entries to the given pattern list.\n> + * If the index is sparse and the pattern list uses cone mode patterns,\n> + * then modify the index to contain the all of the file entries within that\n> + * new pattern list. This expands sparse directories only as far as needed.\n> + *\n> + * If the pattern list is NULL or does not use cone mode patterns, then the\n> + * index is expanded to a full index.\n> + */\n> +void expand_to_pattern_list(struct index_state *istate,\n> +\t\t\t struct pattern_list *pl);\n> +\n> #endif\n\n"},{"id":"455362","messageId":"ac3869a5-3592-5408-587a-178afde3f7e9@github.com","threadId":"57888","inReplyTo":"eba63cc12af4f60320b34a54eef691b9f59d86bc.1652724693.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 6/8] sparse-index: complete partial expansion","fromName":"Victoria Dye","fromEmail":"vdye@github.com","sentAt":"2022-05-16T20:38:10Z","receivedAt":"2022-05-16T21:01:56Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n> \n> To complete the implementation of expand_to_pattern_list(), we need to\n> detect when a sparse directory entry should remain sparse. This avoids a\n> full expansion, so we now need to use the PARTIALLY_SPARSE mode to\n> indicate this state.\n> \n> There still are no callers to this method, but we will add one in the\n> next change.\n> \n> Signed-off-by: Derrick Stolee \n> ---\n> sparse-index.c | 41 +++++++++++++++++++++++++++++++++++++----\n> 1 file changed, 37 insertions(+), 4 deletions(-)\n> \n> diff --git a/sparse-index.c b/sparse-index.c\n> index 3d8eed585b5..0bad5503304 100644\n> --- a/sparse-index.c\n> +++ b/sparse-index.c\n> @@ -297,8 +297,24 @@ void expand_to_pattern_list(struct index_state *istate,\n> \t * continue. A NULL pattern set indicates a full expansion to a\n> \t * full index.\n> \t */\n> -\tif (pl && !pl->use_cone_patterns)\n> +\tif (pl && !pl->use_cone_patterns) {\n> \t\tpl = NULL;\n> +\t} else {\n> +\t\t/*\n> +\t\t * We might contract file entries into sparse-directory\n> +\t\t * entries, and for that we will need the cache tree to\n> +\t\t * be recomputed.\n> +\t\t */\n> +\t\tcache_tree_free(&istate->cache_tree);\n> +\n> +\t\t/*\n> +\t\t * If there is a problem creating the cache tree, then we\n> +\t\t * need to expand to a full index since we cannot satisfy\n> +\t\t * the current request as a sparse index.\n> +\t\t */\n> +\t\tif (cache_tree_update(istate, WRITE_TREE_MISSING_OK))\n> +\t\t\tpl = NULL;\n> +\t}\n> \n> \tif (!istate->repo)\n> \t\tistate->repo = the_repository;\n> @@ -317,8 +333,14 @@ void expand_to_pattern_list(struct index_state *istate,\n> \tfull = xcalloc(1, sizeof(struct index_state));\n> \tmemcpy(full, istate, sizeof(struct index_state));\n> \n> +\t/*\n> +\t * This slightly-misnamed 'full' index might still be sparse if we\n> +\t * are only modifying the list of sparse directories. This hinges\n> +\t * on whether we have a non-NULL pattern list.\n> +\t */\n> +\tfull->sparse_index = pl ? PARTIALLY_SPARSE : COMPLETELY_FULL;\n> +\n> \t/* then change the necessary things */\n> -\tfull->sparse_index = 0;\n> \tfull->cache_alloc = (3 * istate->cache_alloc) / 2;\n> \tfull->cache_nr = 0;\n> \tALLOC_ARRAY(full->cache, full->cache_alloc);\n> @@ -330,11 +352,22 @@ void expand_to_pattern_list(struct index_state *istate,\n> \t\tstruct cache_entry *ce = istate->cache[i];\n> \t\tstruct tree *tree;\n> \t\tstruct pathspec ps;\n> +\t\tint dtype;\n> \n> \t\tif (!S_ISSPARSEDIR(ce->ce_mode)) {\n> \t\t\tset_index_entry(full, full->cache_nr++, ce);\n> \t\t\tcontinue;\n> \t\t}\n> +\n> +\t\t/* We now have a sparse directory entry. Should we expand? */\n> +\t\tif (pl &&\n> +\t\t path_matches_pattern_list(ce->name, ce->ce_namelen,\n> +\t\t\t\t\t NULL, &dtype,\n> +\t\t\t\t\t pl, istate) <= 0) {\n\nIf I'm reading this correctly, what this is doing is:\n\n- if we have a sparse directory entry\n- ...and we're expanding only what matches the pattern list (i.e., not\n 'ensure_full_index')\n- ...and that sparse directory path is either *not matching* or *undecided\n whether it matches* the pattern list\n- ...then we add the sparse directory to the result index and continue. \n\nThe part that's confusing me is the \"<= 0\", which means a return value of\n'UNDECIDED' from 'path_matches_pattern_list' adds the sparse directory\nas-is. At the moment, it looks like 'UNDECIDED' is only returned if not\nusing cone patterns (so it shouldn't make a functional difference at this\npoint), but wouldn't that return value indicate that the pattern *may or may\nnot* match the path, so we should continue on to 'read_tree_at()'?\n\nAll that to say, should the condition be:\n\n\t\t/* We now have a sparse directory entry. Should we expand? */\n\t\tif (pl &&\n\t\t path_matches_pattern_list(ce->name, ce->ce_namelen,\n\t\t\t\t\t NULL, &dtype,\n\t\t\t\t\t pl, istate) == NOT_MATCHED) {\n\nto reflect that a sparse directory should only be added to the index if we\n*know* it isn't matched?\n\nTo be clear, this is ultimately a non-functional nit - my question is mostly\nto make sure I understand the intent of the code.\n\n> +\t\t\tset_index_entry(full, full->cache_nr++, ce);\n> +\t\t\tcontinue;\n> +\t\t}\n> +\n> \t\tif (!(ce->ce_flags & CE_SKIP_WORKTREE))\n> \t\t\twarning(_(\"index entry is a directory, but not sparse (%08x)\"),\n> \t\t\t\tce->ce_flags);\n> @@ -360,7 +393,7 @@ void expand_to_pattern_list(struct index_state *istate,\n> \t/* Copy back into original index. */\n> \tmemcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));\n> \tmemcpy(&istate->dir_hash, &full->dir_hash, sizeof(full->dir_hash));\n> -\tistate->sparse_index = 0;\n> +\tistate->sparse_index = pl ? PARTIALLY_SPARSE : COMPLETELY_FULL;\n> \tfree(istate->cache);\n> \tistate->cache = full->cache;\n> \tistate->cache_nr = full->cache_nr;\n> @@ -374,7 +407,7 @@ void expand_to_pattern_list(struct index_state *istate,\n> \n> \t/* Clear and recompute the cache-tree */\n> \tcache_tree_free(&istate->cache_tree);\n> -\tcache_tree_update(istate, 0);\n> +\tcache_tree_update(istate, WRITE_TREE_MISSING_OK);\n> \n> \ttrace2_region_leave(\"index\",\n> \t\t\t pl ? \"expand_to_pattern_list\" : \"ensure_full_index\",\n\n"},{"id":"455363","messageId":"0d4cf56a-83b6-c7d2-b0b8-a5a5e5d0ccfd@github.com","threadId":"57888","inReplyTo":"12df1777-9f02-ca6f-7d17-57aebe25d06c@github.com","subject":"Re: [PATCH 1/8] sparse-index: create expand_to_pattern_list()","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-05-16T20:49:23Z","receivedAt":"2022-05-16T21:08:27Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/16/2022 4:36 PM, Victoria Dye wrote:\n> Derrick Stolee via GitGitGadget wrote:\n\n>> -void ensure_full_index(struct index_state *istate)\n>> +void expand_to_pattern_list(struct index_state *istate,\n>> +\t\t\t struct pattern_list *pl)\n> \n> Hyper-nit: I don't think this is aligned (it's probably not worth fixing\n> unless you end up rerolling for something else).\n\nYou're right. When I saw this I thought it was just the\n\"off by one\" issue when patches have a \"+\" in the beginning,\nbut it's actually the backwards order. Thanks for catching it.\n\n-Stolee\n"},{"id":"455381","messageId":"f756a125-2d88-3a32-1ae1-652932c663b2@github.com","threadId":"57888","inReplyTo":"ac3869a5-3592-5408-587a-178afde3f7e9@github.com","subject":"Re: [PATCH 6/8] sparse-index: complete partial expansion","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-05-17T13:23:28Z","receivedAt":"2022-05-17T13:23:48Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/16/2022 4:38 PM, Victoria Dye wrote:\n> Derrick Stolee via GitGitGadget wrote:\n>> From: Derrick Stolee \n\n>> +\n>> +\t\t/* We now have a sparse directory entry. Should we expand? */\n>> +\t\tif (pl &&\n>> +\t\t path_matches_pattern_list(ce->name, ce->ce_namelen,\n>> +\t\t\t\t\t NULL, &dtype,\n>> +\t\t\t\t\t pl, istate) <= 0) {\n> \n> If I'm reading this correctly, what this is doing is:\n> \n> - if we have a sparse directory entry\n> - ...and we're expanding only what matches the pattern list (i.e., not\n> 'ensure_full_index')\n> - ...and that sparse directory path is either *not matching* or *undecided\n> whether it matches* the pattern list\n> - ...then we add the sparse directory to the result index and continue. \n> \n> The part that's confusing me is the \"<= 0\", which means a return value of\n> 'UNDECIDED' from 'path_matches_pattern_list' adds the sparse directory\n> as-is. At the moment, it looks like 'UNDECIDED' is only returned if not\n> using cone patterns (so it shouldn't make a functional difference at this\n> point), but wouldn't that return value indicate that the pattern *may or may\n> not* match the path, so we should continue on to 'read_tree_at()'?\n> \n> All that to say, should the condition be:\n> \n> \t\t/* We now have a sparse directory entry. Should we expand? */\n> \t\tif (pl &&\n> \t\t path_matches_pattern_list(ce->name, ce->ce_namelen,\n> \t\t\t\t\t NULL, &dtype,\n> \t\t\t\t\t pl, istate) == NOT_MATCHED) {\n> \n> to reflect that a sparse directory should only be added to the index if we\n> *know* it isn't matched?\n> \n> To be clear, this is ultimately a non-functional nit - my question is mostly\n> to make sure I understand the intent of the code.\n\nYou are 100% correct, and using \"== NOT_MATCHED\" makes the intention clear,\nas well as being more robust to a breakage in path_matches_pattern_list().\n\nThanks,\n-Stolee\n\n"},{"id":"455382","messageId":"f9f49c09-c566-6938-273d-56015ed14d4e@github.com","threadId":"57888","inReplyTo":"9191a98c-087a-39b9-cff3-eb7eccd198ea@github.com","subject":"Re: [PATCH 8/8] sparse-checkout: integrate with sparse index","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-05-17T13:28:06Z","receivedAt":"2022-05-17T13:28:14Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/16/2022 4:38 PM, Victoria Dye wrote:\n> Derrick Stolee via GitGitGadget wrote:\n>> From: Derrick Stolee \n\n>> +test_expect_success 'sparse index is not expanded: sparse-checkout' '\n>> +\tinit_repos &&\n>> +\n>> +\tensure_not_expanded sparse-checkout set deep/deeper2 &&\n>> +\tensure_not_expanded sparse-checkout set deep/deeper1 &&\n>> +\tensure_not_expanded sparse-checkout set deep &&\n>> +\tensure_not_expanded sparse-checkout add folder1 &&\n>> +\tensure_not_expanded sparse-checkout set deep/deeper1 &&\n>> +\tensure_not_expanded sparse-checkout set folder2 &&\n>> +\n>> +\t# Demonstrate that the checks that \"folder1/a\" is a file\n>> +\t# do not cause a sparse-index expansion (since it is in the\n>> +\t# sparse-checkout cone).\n>> +\techo >>sparse-index/folder2/a &&\n>> +\tgit -C sparse-index add folder2/a &&\n>> +\n>> +\tensure_not_expanded sparse-checkout add folder1 &&\n>> +\n>> +\t# Skip checks here, since deep/deeper1 is inside a sparse directory\n>> +\t# that must be expanded to check whether `deep/deeper1` is a file\n>> +\t# or not.\n>> +\tensure_not_expanded sparse-checkout set --skip-checks deep/deeper1 &&\n>> +\tensure_not_expanded sparse-checkout set\n>> +'\n>> +\n> \n> These tests look good for ensuring sparsity is preserved, but it'd be nice\n> to also have some \"stress tests\" of 'sparse-checkout (add|set)'. The purpose\n> would be to make sure the index has the right contents for various types of\n> pattern changes, e.g. running 'sparse-checkout (add|set) ', then\n> verifying index contents with 'ls-files --sparse'. Paths might be:\n> \n> - in vs. out of (current) cone\n> - match an existing vs. nonexistent directory\n> \n> etc.\n\nI guess I was relying on tests added previously for the sparse index,\nsuch as this one:\n\ntest_expect_success 'sparse-index contents' '\n\tinit_repos &&\n\n\tgit -C sparse-index ls-files --sparse --stage >cache &&\n\tfor dir in folder1 folder2 x\n\tdo\n\t\tTREE=$(git -C sparse-index rev-parse HEAD:$dir) &&\n\t\tgrep \"040000 $TREE 0\t$dir/\" cache \\\n\t\t\t|| return 1\n\tdone &&\n\n\tgit -C sparse-index sparse-checkout set folder1 &&\n\n\tgit -C sparse-index ls-files --sparse --stage >cache &&\n\tfor dir in deep folder2 x\n\tdo\n\t\tTREE=$(git -C sparse-index rev-parse HEAD:$dir) &&\n\t\tgrep \"040000 $TREE 0\t$dir/\" cache \\\n\t\t\t|| return 1\n\tdone &&\n\n\tgit -C sparse-index sparse-checkout set deep/deeper1 &&\n\n\tgit -C sparse-index ls-files --sparse --stage >cache &&\n\tfor dir in deep/deeper2 folder1 folder2 x\n\tdo\n\t\tTREE=$(git -C sparse-index rev-parse HEAD:$dir) &&\n\t\tgrep \"040000 $TREE 0\t$dir/\" cache \\\n\t\t\t|| return 1\n\tdone &&\n\n\t# Disabling the sparse-index replaces tree entries with full ones\n\tgit -C sparse-index sparse-checkout init --no-sparse-index &&\n\ttest_sparse_match git ls-files --stage --sparse\n'\n\nBut this test isn't covering enough interesting cases that might\ncause issues with the changes in this series. I'll add a patch that\nincreases coverage in this area.\n\nThanks,\n-Stolee\n"},{"id":"455502","messageId":"5030eeecf4f8e2dd65bc055d6a720c7d67015b1e.1652982758.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v2.git.1652982758.gitgitgadget@gmail.com","subject":"[PATCH v2 02/10] t1092: stress test 'git sparse-checkout set'","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-19T17:52:30Z","receivedAt":"2022-05-19T17:53:43Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe 'sparse-index contents' test checks that the sparse index has the\ncorrect set of sparse directories in the index after modifying the cone\nmode patterns using 'git sparse-checkout set'. Add to the coverage here\nby adding more complicated scenarios that were not previously tested.\n\nIn order to check paths that do not exist at HEAD, we need to modify the\ntest_sparse_checkout_set helper slightly:\n\n1. Add the --skip-checks argument to the 'set' command to avoid failures\n when passing paths that do not exist at HEAD.\n\n2. When looking for the non-existence of sparse directories for the\n paths in $CONE_DIRS, allow the rev-list command to fail because the\n path does not exist at HEAD.\n\nThis allows us to add some interesting test cases.\n\nHelped-by: Victoria Dye \nSigned-off-by: Derrick Stolee \n---\n t/t1092-sparse-checkout-compatibility.sh | 19 +++++++++++++++++--\n 1 file changed, 17 insertions(+), 2 deletions(-)\n\ndiff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\nindex e7c0ae9b953..785820f9fd5 100755\n--- a/t/t1092-sparse-checkout-compatibility.sh\n+++ b/t/t1092-sparse-checkout-compatibility.sh\n@@ -212,7 +212,7 @@ test_sparse_unstaged () {\n test_sparse_checkout_set () {\n \tCONE_DIRS=$1 &&\n \tSPARSE_DIRS=$2 &&\n-\tgit -C sparse-index sparse-checkout set $CONE_DIRS &&\n+\tgit -C sparse-index sparse-checkout set --skip-checks $CONE_DIRS &&\n \tgit -C sparse-index ls-files --sparse --stage >cache &&\n \n \t# Check that the directories outside of the sparse-checkout cone\n@@ -228,7 +228,9 @@ test_sparse_checkout_set () {\n \t# are not sparse directory entries.\n \tfor dir in $CONE_DIRS\n \tdo\n-\t\tTREE=$(git -C sparse-index rev-parse HEAD:$dir) &&\n+\t\t# Allow TREE to not exist because\n+\t\t# $dir does not exist at HEAD.\n+\t\tTREE=$(git -C sparse-index rev-parse HEAD:$dir) ||\n \t\t! grep \"040000 $TREE 0\t$dir/\" cache \\\n \t\t\t|| return 1\n \tdone\n@@ -253,6 +255,19 @@ test_expect_success 'sparse-index contents' '\n \t\t\"deep/deeper2 folder1 folder2 x\" \\\n \t\t\"before deep/deeper1\" &&\n \n+\t# Replace deep/deeper2 with deep/deeper1\n+\t# Replace folder1 with folder1/0/0\n+\t# Replace folder2 with non-existent folder2/2/3\n+\t# Add non-existent \"bogus\"\n+\ttest_sparse_checkout_set \\\n+\t\t\"bogus deep/deeper1 folder1/0/0 folder2/2/3 x\" \\\n+\t\t\"before deep/deeper2 folder2/0\" &&\n+\n+\t# Drop down to only files at root\n+\ttest_sparse_checkout_set \\\n+\t\t\"\" \\\n+\t\t\"before deep folder1 folder2 x\" &&\n+\n \t# Disabling the sparse-index replaces tree entries with full ones\n \tgit -C sparse-index sparse-checkout init --no-sparse-index &&\n \ttest_sparse_match git ls-files --stage --sparse\n-- \ngitgitgadget\n\n"},{"id":"455503","messageId":"d15338573e570aebe239dacdd8c2aba275ff61b9.1652982758.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v2.git.1652982758.gitgitgadget@gmail.com","subject":"[PATCH v2 03/10] sparse-index: create expand_to_pattern_list()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-19T17:52:31Z","receivedAt":"2022-05-19T17:53:44Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThis is the first change in a series to allow modifying the\nsparse-checkout pattern set without expanding a sparse index to a full\none in the process. Here, we focus on the problem of expanding the\npattern set through a command like 'git sparse-checkout add '\nwhich needs to create new index entries for the paths now being written\nto the worktree.\n\nTo achieve this, we need to be able to replace sparse directory entries\nwith their contained files and subdirectories. Once this is complete,\nother code paths can discover those cache entries and write the\ncorresponding files to disk before committing the index.\n\nWe already have logic in ensure_full_index() that expands the index\nentries, so we will use that as our base. Create a new method,\nexpand_to_pattern_list(), which takes a pattern list, but for now mostly\nignores it. The current implementation is only correct when the pattern\nlist is NULL as that does the same as ensure_full_index(). In fact,\nensure_full_index() is converted to a shim over\nexpand_to_pattern_list().\n\nA future update will actually implement expand_to_pattern_list() to its\nfull capabilities. For now, it is created and documented.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 35 ++++++++++++++++++++++++++++++++---\n sparse-index.h | 14 ++++++++++++++\n 2 files changed, 46 insertions(+), 3 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex 8636af72de5..2a06ef58051 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -248,19 +248,41 @@ static int add_path_to_index(const struct object_id *oid,\n \treturn 0;\n }\n \n-void ensure_full_index(struct index_state *istate)\n+void expand_to_pattern_list(struct index_state *istate,\n+\t\t\t struct pattern_list *pl)\n {\n \tint i;\n \tstruct index_state *full;\n \tstruct strbuf base = STRBUF_INIT;\n \n+\t/*\n+\t * If the index is already full, then keep it full. We will convert\n+\t * it to a sparse index on write, if possible.\n+\t */\n \tif (!istate || !istate->sparse_index)\n \t\treturn;\n \n+\t/*\n+\t * If our index is sparse, but our new pattern set does not use\n+\t * cone mode patterns, then we need to expand the index before we\n+\t * continue. A NULL pattern set indicates a full expansion to a\n+\t * full index.\n+\t */\n+\tif (pl && !pl->use_cone_patterns)\n+\t\tpl = NULL;\n+\n \tif (!istate->repo)\n \t\tistate->repo = the_repository;\n \n-\ttrace2_region_enter(\"index\", \"ensure_full_index\", istate->repo);\n+\t/*\n+\t * A NULL pattern set indicates we are expanding a full index, so\n+\t * we use a special region name that indicates the full expansion.\n+\t * This is used by test cases, but also helps to differentiate the\n+\t * two cases.\n+\t */\n+\ttrace2_region_enter(\"index\",\n+\t\t\t pl ? \"expand_to_pattern_list\" : \"ensure_full_index\",\n+\t\t\t istate->repo);\n \n \t/* initialize basics of new index */\n \tfull = xcalloc(1, sizeof(struct index_state));\n@@ -322,7 +344,14 @@ void ensure_full_index(struct index_state *istate)\n \tcache_tree_free(&istate->cache_tree);\n \tcache_tree_update(istate, 0);\n \n-\ttrace2_region_leave(\"index\", \"ensure_full_index\", istate->repo);\n+\ttrace2_region_leave(\"index\",\n+\t\t\t pl ? \"expand_to_pattern_list\" : \"ensure_full_index\",\n+\t\t\t istate->repo);\n+}\n+\n+void ensure_full_index(struct index_state *istate)\n+{\n+\texpand_to_pattern_list(istate, NULL);\n }\n \n void ensure_correct_sparsity(struct index_state *istate)\ndiff --git a/sparse-index.h b/sparse-index.h\nindex 633d4fb7e31..037b541f49d 100644\n--- a/sparse-index.h\n+++ b/sparse-index.h\n@@ -23,4 +23,18 @@ void expand_to_path(struct index_state *istate,\n struct repository;\n int set_sparse_index_config(struct repository *repo, int enable);\n \n+struct pattern_list;\n+\n+/**\n+ * Scan the given index and compare its entries to the given pattern list.\n+ * If the index is sparse and the pattern list uses cone mode patterns,\n+ * then modify the index to contain the all of the file entries within that\n+ * new pattern list. This expands sparse directories only as far as needed.\n+ *\n+ * If the pattern list is NULL or does not use cone mode patterns, then the\n+ * index is expanded to a full index.\n+ */\n+void expand_to_pattern_list(struct index_state *istate,\n+\t\t\t struct pattern_list *pl);\n+\n #endif\n-- \ngitgitgadget\n\n"},{"id":"455504","messageId":"pull.1208.v2.git.1652982758.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.git.1652724693.gitgitgadget@gmail.com","subject":"[PATCH v2 00/10] Sparse index: integrate with sparse-checkout","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-19T17:52:28Z","receivedAt":"2022-05-19T17:53:46Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"This series is based on ds/sparse-colon-path.\n\nThis series integrates the 'git sparse-checkout' builtin with the sparse\nindex. This is the last integration that we fast-tracked into the\nmicrosoft/git fork. After this, we have no work in flight that would\nconflict with a Google Summer of Code project in this area.\n\nThe tricky part about the sparse-checkout builtin is that we actually do\nneed to expand the index when growing the sparse-checkout boundary. The\ntrick is to expand it only as far as we need it, and then ensure that we\ncollapse any removed directories before the command completes.\n\nTo do this, we introduce a concept of a \"partially expanded\" index. In fact,\nwe break the boolean sparse_index member into an enum with three states:\n\n * COMPLETELY_FULL (0): No sparse directories exist.\n\n * COMPLETELY_SPARSE (1): Sparse directories may exist. Files outside the\n sparse-checkout cone are reduced to sparse directory entries whenever\n possible.\n\n * PARTIALLY_SPARSE (2): Sparse directories may exist. Some file entries\n outside the sparse-checkout cone may exist. Running convert_to_sparse()\n may further reduce those files to sparse directory entries.\n\nMost of the patches in this series focus on introducing this enum and\ncarefully converting previous uses of the boolean to use the enum. Some\nadditional work is required to refactor ensure_full_index() into a new\nexpand_to_pattern_list() method, as they are doing essentially the same\nthing, but with different scopes.\n\nThe result is improved performance on the sparse-checkout builtin as\ndemonstrated in a new p2000-sparse-operations.sh performance test:\n\n\nTest HEAD~1 HEAD\n================\n\n2000.24: git sparse-checkout ... (sparse-v3) 2.14(1.55+0.58) 1.57(1.03+0.53)\n-26.6% 2000.25: git sparse-checkout ... (sparse-v4) 2.20(1.62+0.57)\n1.58(0.98+0.59) -28.2%\n\nThe improvement here is less dramatic because the operation is dominated by\nwriting and deleting a lot of files in the worktree. A repeated no-op\noperation such as git sparse-checkout set $SPARSE_CONE would show a greater\nimprovement, but is less interesting since it could gain that improvement\nwithout satisfying the \"hard\" parts of this builtin.\n\nI specifically chose how to update the tests in t1092 and p2000 to avoid\nconflicts with Victoria's 'git stash' work.\n\n\nUpdates in v2\n=============\n\n * Typo fixes.\n * Two patches are added to the start to (a) refactor existing sparse index\n content tests, and (b) add new sparse index content tests with additional\n scenarios.\n * Use NOT_MATCHED directly instead of implicitly allowing UNDECIDED when\n matching in cone mode.\n\nThanks, -Stolee\n\nDerrick Stolee (10):\n t1092: refactor 'sparse-index contents' test\n t1092: stress test 'git sparse-checkout set'\n sparse-index: create expand_to_pattern_list()\n sparse-index: introduce partially-sparse indexes\n cache-tree: implement cache_tree_find_path()\n sparse-checkout: --no-sparse-index needs a full index\n sparse-index: partially expand directories\n sparse-index: complete partial expansion\n p2000: add test for 'git sparse-checkout [add|set]'\n sparse-checkout: integrate with sparse index\n\n builtin/sparse-checkout.c | 8 +-\n cache-tree.c | 24 +++++\n cache-tree.h | 2 +\n cache.h | 32 ++++--\n read-cache.c | 6 +-\n sparse-index.c | 126 ++++++++++++++++++++---\n sparse-index.h | 14 +++\n t/perf/p2000-sparse-operations.sh | 1 +\n t/t1092-sparse-checkout-compatibility.sh | 95 +++++++++++++----\n unpack-trees.c | 4 +\n 10 files changed, 265 insertions(+), 47 deletions(-)\n\n\nbase-commit: 124b05b23005437fa5fb91863bde2a8f5840e164\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1208%2Fderrickstolee%2Fsparse-index%2Fsparse-checkout-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1208/derrickstolee/sparse-index/sparse-checkout-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/1208\n\nRange-diff vs v1:\n\n -: ----------- > 1: f2960747ed8 t1092: refactor 'sparse-index contents' test\n -: ----------- > 2: 5030eeecf4f t1092: stress test 'git sparse-checkout set'\n 1: f1194d56d33 ! 3: d15338573e5 sparse-index: create expand_to_pattern_list()\n @@ sparse-index.c: static int add_path_to_index(const struct object_id *oid,\n \n -void ensure_full_index(struct index_state *istate)\n +void expand_to_pattern_list(struct index_state *istate,\n -+\t\t\t struct pattern_list *pl)\n ++\t\t\t struct pattern_list *pl)\n {\n \tint i;\n \tstruct index_state *full;\n 2: d394d0e20e8 = 4: 269c206c331 sparse-index: introduce partially-sparse indexes\n 3: c0e81be97aa = 5: c977001c033 cache-tree: implement cache_tree_find_path()\n 4: d1fb2e0e0d3 = 6: e42463de0d2 sparse-checkout: --no-sparse-index needs a full index\n 5: 5c7546ab070 ! 7: 346c56bf256 sparse-index: partially expand directories\n @@ sparse-index.c: static int add_path_to_index(const struct object_id *oid,\n -\tce = make_cache_entry(istate, mode, oid, base->buf, 0, 0);\n +\t\t/*\n +\t\t * The path \"{base}{path}/\" is a sparse directory. Create the correct\n -+\t\t * name for inserting the entry into the idnex.\n ++\t\t * name for inserting the entry into the index.\n +\t\t */\n +\t\tstrbuf_setlen(base, base->len - 1);\n +\t} else {\n 6: eba63cc12af ! 8: ed640e3645b sparse-index: complete partial expansion\n @@ sparse-index.c: void expand_to_pattern_list(struct index_state *istate,\n +\t\tif (pl &&\n +\t\t path_matches_pattern_list(ce->name, ce->ce_namelen,\n +\t\t\t\t\t NULL, &dtype,\n -+\t\t\t\t\t pl, istate) <= 0) {\n ++\t\t\t\t\t pl, istate) == NOT_MATCHED) {\n +\t\t\tset_index_entry(full, full->cache_nr++, ce);\n +\t\t\tcontinue;\n +\t\t}\n 7: 2804326c8bb = 9: 089ab086f58 p2000: add test for 'git sparse-checkout [add|set]'\n 8: b8a349c6dee = 10: ad9ed6973d5 sparse-checkout: integrate with sparse index\n\n-- \ngitgitgadget\n"},{"id":"455505","messageId":"269c206c331bb43006678beaa20832a75754c3df.1652982758.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v2.git.1652982758.gitgitgadget@gmail.com","subject":"[PATCH v2 04/10] sparse-index: introduce partially-sparse indexes","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-19T17:52:32Z","receivedAt":"2022-05-19T17:53:51Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nA future change will present a temporary, in-memory mode where the index\ncan both contain sparse directory entries but also not be completely\ncollapsed to the smallest possible sparse directories. This will be\nnecessary for modifying the sparse-checkout definition while using a\nsparse index.\n\nFor now, convert the single-bit member 'sparse_index' in 'struct\nindex_state' to be a an 'enum sparse_index_mode' with three modes:\n\n* COMPLETELY_FULL (0): No sparse directories exist.\n\n* COMPLETELY_SPARSE (1): Sparse directories may exist. Files outside the\n sparse-checkout cone are reduced to sparse directory entries whenever\n possible.\n\n* PARTIALLY_SPARSE (2): Sparse directories may exist. Some file entries\n outside the sparse-checkout cone may exist. Running\n convert_to_sparse() may further reduce those files to sparse directory\n entries.\n\nThe main reason to store this extra information is to allow\nconvert_to_sparse() to short-circuit when the index is already in\nCOMPLETELY_SPARSE mode but to actually do the necessary work when in\nPARTIALLY_SPARSE mode.\n\nThe PARTIALLY_SPARSE mode will be used in an upcoming change.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/sparse-checkout.c | 2 +-\n cache.h | 32 ++++++++++++++++++++++++--------\n read-cache.c | 6 +++---\n sparse-index.c | 6 +++---\n 4 files changed, 31 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\nindex 0217d44c5b1..88eea069ad4 100644\n--- a/builtin/sparse-checkout.c\n+++ b/builtin/sparse-checkout.c\n@@ -128,7 +128,7 @@ static void clean_tracked_sparse_directories(struct repository *r)\n \t * sparse index will not delete directories that contain\n \t * conflicted entries or submodules.\n \t */\n-\tif (!r->index->sparse_index) {\n+\tif (r->index->sparse_index == COMPLETELY_FULL) {\n \t\t/*\n \t\t * If something, such as a merge conflict or other concern,\n \t\t * prevents us from converting to a sparse index, then do\ndiff --git a/cache.h b/cache.h\nindex 6226f6a8a53..2d067aca2fd 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -310,6 +310,28 @@ struct untracked_cache;\n struct progress;\n struct pattern_list;\n \n+enum sparse_index_mode {\n+\t/*\n+\t * COMPLETELY_FULL: there are no sparse directories\n+\t * in the index at all.\n+\t */\n+\tCOMPLETELY_FULL = 0,\n+\n+\t/*\n+\t * COLLAPSED: the index has already been collapsed to sparse\n+\t * directories whereever possible.\n+\t */\n+\tCOLLAPSED = 1,\n+\n+\t/*\n+\t * PARTIALLY_SPARSE: the sparse directories that exist are\n+\t * outside the sparse-checkout boundary, but it is possible\n+\t * that some file entries could collapse to sparse directory\n+\t * entries.\n+\t */\n+\tPARTIALLY_SPARSE = 2,\n+};\n+\n struct index_state {\n \tstruct cache_entry **cache;\n \tunsigned int version;\n@@ -323,14 +345,8 @@ struct index_state {\n \t\t drop_cache_tree : 1,\n \t\t updated_workdir : 1,\n \t\t updated_skipworktree : 1,\n-\t\t fsmonitor_has_run_once : 1,\n-\n-\t\t /*\n-\t\t * sparse_index == 1 when sparse-directory\n-\t\t * entries exist. Requires sparse-checkout\n-\t\t * in cone mode.\n-\t\t */\n-\t\t sparse_index : 1;\n+\t\t fsmonitor_has_run_once : 1;\n+\tenum sparse_index_mode sparse_index;\n \tstruct hashmap name_hash;\n \tstruct hashmap dir_hash;\n \tstruct object_id oid;\ndiff --git a/read-cache.c b/read-cache.c\nindex 4df97e185e9..cb9b33169fd 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -112,7 +112,7 @@ static const char *alternate_index_output;\n static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)\n {\n \tif (S_ISSPARSEDIR(ce->ce_mode))\n-\t\tistate->sparse_index = 1;\n+\t\tistate->sparse_index = COLLAPSED;\n \n \tistate->cache[nr] = ce;\n \tadd_name_hash(istate, ce);\n@@ -1856,7 +1856,7 @@ static int read_index_extension(struct index_state *istate,\n \t\tbreak;\n \tcase CACHE_EXT_SPARSE_DIRECTORIES:\n \t\t/* no content, only an indicator */\n-\t\tistate->sparse_index = 1;\n+\t\tistate->sparse_index = COLLAPSED;\n \t\tbreak;\n \tdefault:\n \t\tif (*ext < 'A' || 'Z' < *ext)\n@@ -3149,7 +3149,7 @@ static int do_write_locked_index(struct index_state *istate, struct lock_file *l\n \t\t\t\t unsigned flags)\n {\n \tint ret;\n-\tint was_full = !istate->sparse_index;\n+\tint was_full = istate->sparse_index == COMPLETELY_FULL;\n \n \tret = convert_to_sparse(istate, 0);\n \ndiff --git a/sparse-index.c b/sparse-index.c\nindex 2a06ef58051..c2cd3bdb614 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -173,7 +173,7 @@ int convert_to_sparse(struct index_state *istate, int flags)\n \t * If the index is already sparse, empty, or otherwise\n \t * cannot be converted to sparse, do not convert.\n \t */\n-\tif (istate->sparse_index || !istate->cache_nr ||\n+\tif (istate->sparse_index == COLLAPSED || !istate->cache_nr ||\n \t !is_sparse_index_allowed(istate, flags))\n \t\treturn 0;\n \n@@ -214,7 +214,7 @@ int convert_to_sparse(struct index_state *istate, int flags)\n \tFREE_AND_NULL(istate->fsmonitor_dirty);\n \tFREE_AND_NULL(istate->fsmonitor_last_update);\n \n-\tistate->sparse_index = 1;\n+\tistate->sparse_index = COLLAPSED;\n \ttrace2_region_leave(\"index\", \"convert_to_sparse\", istate->repo);\n \treturn 0;\n }\n@@ -259,7 +259,7 @@ void expand_to_pattern_list(struct index_state *istate,\n \t * If the index is already full, then keep it full. We will convert\n \t * it to a sparse index on write, if possible.\n \t */\n-\tif (!istate || !istate->sparse_index)\n+\tif (!istate || istate->sparse_index == COMPLETELY_FULL)\n \t\treturn;\n \n \t/*\n-- \ngitgitgadget\n\n"},{"id":"455506","messageId":"f2960747ed868d57bc2eccfbe49d284f5268aba4.1652982758.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v2.git.1652982758.gitgitgadget@gmail.com","subject":"[PATCH v2 01/10] t1092: refactor 'sparse-index contents' test","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-19T17:52:29Z","receivedAt":"2022-05-19T17:53:54Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nBefore expanding this test with more involved cases, first extract the\nrepeated logic into a new test_sparse_checkout_set helper. This helper\nchecks that 'git sparse-checkout set ...' succeeds and then verifies\nthat certain directories have sparse directory entries in the sparse\nindex. It also verifies that the in-cone directories are _not_ sparse\ndirectory entries in the sparse index.\n\nSigned-off-by: Derrick Stolee \n---\n t/t1092-sparse-checkout-compatibility.sh | 53 ++++++++++++++++--------\n 1 file changed, 35 insertions(+), 18 deletions(-)\n\ndiff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\nindex 93bcfd20bbc..e7c0ae9b953 100755\n--- a/t/t1092-sparse-checkout-compatibility.sh\n+++ b/t/t1092-sparse-checkout-compatibility.sh\n@@ -205,36 +205,53 @@ test_sparse_unstaged () {\n \tdone\n }\n \n-test_expect_success 'sparse-index contents' '\n-\tinit_repos &&\n-\n+# Usage: test_sprase_checkout_set \" ... \" \" ... \"\n+# Verifies that \"git sparse-checkout set ... \" succeeds and\n+# leaves the sparse index in a state where ... are sparse\n+# directories (and ... are not).\n+test_sparse_checkout_set () {\n+\tCONE_DIRS=$1 &&\n+\tSPARSE_DIRS=$2 &&\n+\tgit -C sparse-index sparse-checkout set $CONE_DIRS &&\n \tgit -C sparse-index ls-files --sparse --stage >cache &&\n-\tfor dir in folder1 folder2 x\n+\n+\t# Check that the directories outside of the sparse-checkout cone\n+\t# have sparse directory entries.\n+\tfor dir in $SPARSE_DIRS\n \tdo\n \t\tTREE=$(git -C sparse-index rev-parse HEAD:$dir) &&\n \t\tgrep \"040000 $TREE 0\t$dir/\" cache \\\n \t\t\t|| return 1\n \tdone &&\n \n-\tgit -C sparse-index sparse-checkout set folder1 &&\n-\n-\tgit -C sparse-index ls-files --sparse --stage >cache &&\n-\tfor dir in deep folder2 x\n+\t# Check that the directories in the sparse-checkout cone\n+\t# are not sparse directory entries.\n+\tfor dir in $CONE_DIRS\n \tdo\n \t\tTREE=$(git -C sparse-index rev-parse HEAD:$dir) &&\n-\t\tgrep \"040000 $TREE 0\t$dir/\" cache \\\n+\t\t! grep \"040000 $TREE 0\t$dir/\" cache \\\n \t\t\t|| return 1\n-\tdone &&\n+\tdone\n+}\n \n-\tgit -C sparse-index sparse-checkout set deep/deeper1 &&\n+test_expect_success 'sparse-index contents' '\n+\tinit_repos &&\n \n-\tgit -C sparse-index ls-files --sparse --stage >cache &&\n-\tfor dir in deep/deeper2 folder1 folder2 x\n-\tdo\n-\t\tTREE=$(git -C sparse-index rev-parse HEAD:$dir) &&\n-\t\tgrep \"040000 $TREE 0\t$dir/\" cache \\\n-\t\t\t|| return 1\n-\tdone &&\n+\t# Remove deep, add three other directories.\n+\ttest_sparse_checkout_set \\\n+\t\t\"folder1 folder2 x\" \\\n+\t\t\"before deep\" &&\n+\n+\t# Remove folder1, add deep\n+\ttest_sparse_checkout_set \\\n+\t\t\"deep folder2 x\" \\\n+\t\t\"before folder1\" &&\n+\n+\t# Replace deep with deep/deeper2 (dropping deep/deeper1)\n+\t# Add folder1\n+\ttest_sparse_checkout_set \\\n+\t\t\"deep/deeper2 folder1 folder2 x\" \\\n+\t\t\"before deep/deeper1\" &&\n \n \t# Disabling the sparse-index replaces tree entries with full ones\n \tgit -C sparse-index sparse-checkout init --no-sparse-index &&\n-- \ngitgitgadget\n\n"},{"id":"455507","messageId":"c977001c033e8689f6d0ca52a6021bde61b1b476.1652982759.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v2.git.1652982758.gitgitgadget@gmail.com","subject":"[PATCH v2 05/10] cache-tree: implement cache_tree_find_path()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-19T17:52:33Z","receivedAt":"2022-05-19T17:53:57Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nGiven a 'struct cache_tree', it may be beneficial to navigate directly\nto a node within that corresponds to a given path name. Create\ncache_tree_find_path() for this function. It returns NULL when no such\npath exists.\n\nThe implementation is adapted from do_invalidate_path() which does a\nsimilar search but also modifies the nodes it finds along the way.\n\nThis new method is not currently used, but will be in an upcoming\nchange.\n\nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 24 ++++++++++++++++++++++++\n cache-tree.h | 2 ++\n 2 files changed, 26 insertions(+)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 6752f69d515..23893a7b113 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -100,6 +100,30 @@ struct cache_tree_sub *cache_tree_sub(struct cache_tree *it, const char *path)\n \treturn find_subtree(it, path, pathlen, 1);\n }\n \n+struct cache_tree *cache_tree_find_path(struct cache_tree *it, const char *path)\n+{\n+\tconst char *slash;\n+\tint namelen;\n+\tstruct cache_tree_sub *down;\n+\n+\tif (!it)\n+\t\treturn NULL;\n+\tslash = strchrnul(path, '/');\n+\tnamelen = slash - path;\n+\tit->entry_count = -1;\n+\tif (!*slash) {\n+\t\tint pos;\n+\t\tpos = cache_tree_subtree_pos(it, path, namelen);\n+\t\tif (0 <= pos)\n+\t\t\treturn it->down[pos]->cache_tree;\n+\t\treturn NULL;\n+\t}\n+\tdown = find_subtree(it, path, namelen, 0);\n+\tif (down)\n+\t\treturn cache_tree_find_path(down->cache_tree, slash + 1);\n+\treturn NULL;\n+}\n+\n static int do_invalidate_path(struct cache_tree *it, const char *path)\n {\n \t/* a/b/c\ndiff --git a/cache-tree.h b/cache-tree.h\nindex 8efeccebfc9..f75f8e74dcd 100644\n--- a/cache-tree.h\n+++ b/cache-tree.h\n@@ -29,6 +29,8 @@ struct cache_tree_sub *cache_tree_sub(struct cache_tree *, const char *);\n \n int cache_tree_subtree_pos(struct cache_tree *it, const char *path, int pathlen);\n \n+struct cache_tree *cache_tree_find_path(struct cache_tree *it, const char *path);\n+\n void cache_tree_write(struct strbuf *, struct cache_tree *root);\n struct cache_tree *cache_tree_read(const char *buffer, unsigned long size);\n \n-- \ngitgitgadget\n\n"},{"id":"455508","messageId":"346c56bf2560c5a89850ef4f8a58fbe17cde10fc.1652982759.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v2.git.1652982758.gitgitgadget@gmail.com","subject":"[PATCH v2 07/10] sparse-index: partially expand directories","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-19T17:52:35Z","receivedAt":"2022-05-19T17:53:59Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe expand_to_pattern_list() method expands sparse directory entries\nto their list of contained files when either the pattern list is NULL or\nthe directory is contained in the new pattern list's cone mode patterns.\n\nIt is possible that the pattern list has a recursive match with a\ndirectory 'A/B/C/' and so an existing sparse directory 'A/B/' would need\nto be expanded. If there exists a directory 'A/B/D/', then that\ndirectory should not be expanded and instead we can create a sparse\ndirectory.\n\nTo implement this, we plug into the add_path_to_index() callback for the\ncall to read_tree_at(). Since we now need access to both the index we\nare writing and the pattern list we are comparing, create a 'struct\nmodify_index_context' to use as a data transfer object. It is important\nthat we use the given pattern list since we will use this pattern list\nto change the sparse-checkout patterns and cannot use\nistate->sparse_checkout_patterns.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 46 +++++++++++++++++++++++++++++++++++++++-------\n 1 file changed, 39 insertions(+), 7 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex c2cd3bdb614..73b82e5017b 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -9,6 +9,11 @@\n #include \"dir.h\"\n #include \"fsmonitor.h\"\n \n+struct modify_index_context {\n+\tstruct index_state *write;\n+\tstruct pattern_list *pl;\n+};\n+\n static struct cache_entry *construct_sparse_dir_entry(\n \t\t\t\tstruct index_state *istate,\n \t\t\t\tconst char *sparse_dir,\n@@ -231,18 +236,41 @@ static int add_path_to_index(const struct object_id *oid,\n \t\t\t struct strbuf *base, const char *path,\n \t\t\t unsigned int mode, void *context)\n {\n-\tstruct index_state *istate = (struct index_state *)context;\n+\tstruct modify_index_context *ctx = (struct modify_index_context *)context;\n \tstruct cache_entry *ce;\n \tsize_t len = base->len;\n \n-\tif (S_ISDIR(mode))\n-\t\treturn READ_TREE_RECURSIVE;\n+\tif (S_ISDIR(mode)) {\n+\t\tint dtype;\n+\t\tsize_t baselen = base->len;\n+\t\tif (!ctx->pl)\n+\t\t\treturn READ_TREE_RECURSIVE;\n \n-\tstrbuf_addstr(base, path);\n+\t\t/*\n+\t\t * Have we expanded to a point outside of the sparse-checkout?\n+\t\t */\n+\t\tstrbuf_addstr(base, path);\n+\t\tstrbuf_add(base, \"/-\", 2);\n+\n+\t\tif (path_matches_pattern_list(base->buf, base->len,\n+\t\t\t\t\t NULL, &dtype,\n+\t\t\t\t\t ctx->pl, ctx->write)) {\n+\t\t\tstrbuf_setlen(base, baselen);\n+\t\t\treturn READ_TREE_RECURSIVE;\n+\t\t}\n \n-\tce = make_cache_entry(istate, mode, oid, base->buf, 0, 0);\n+\t\t/*\n+\t\t * The path \"{base}{path}/\" is a sparse directory. Create the correct\n+\t\t * name for inserting the entry into the index.\n+\t\t */\n+\t\tstrbuf_setlen(base, base->len - 1);\n+\t} else {\n+\t\tstrbuf_addstr(base, path);\n+\t}\n+\n+\tce = make_cache_entry(ctx->write, mode, oid, base->buf, 0, 0);\n \tce->ce_flags |= CE_SKIP_WORKTREE | CE_EXTENDED;\n-\tset_index_entry(istate, istate->cache_nr++, ce);\n+\tset_index_entry(ctx->write, ctx->write->cache_nr++, ce);\n \n \tstrbuf_setlen(base, len);\n \treturn 0;\n@@ -254,6 +282,7 @@ void expand_to_pattern_list(struct index_state *istate,\n \tint i;\n \tstruct index_state *full;\n \tstruct strbuf base = STRBUF_INIT;\n+\tstruct modify_index_context ctx;\n \n \t/*\n \t * If the index is already full, then keep it full. We will convert\n@@ -294,6 +323,9 @@ void expand_to_pattern_list(struct index_state *istate,\n \tfull->cache_nr = 0;\n \tALLOC_ARRAY(full->cache, full->cache_alloc);\n \n+\tctx.write = full;\n+\tctx.pl = pl;\n+\n \tfor (i = 0; i < istate->cache_nr; i++) {\n \t\tstruct cache_entry *ce = istate->cache[i];\n \t\tstruct tree *tree;\n@@ -319,7 +351,7 @@ void expand_to_pattern_list(struct index_state *istate,\n \t\tstrbuf_add(&base, ce->name, strlen(ce->name));\n \n \t\tread_tree_at(istate->repo, tree, &base, &ps,\n-\t\t\t add_path_to_index, full);\n+\t\t\t add_path_to_index, &ctx);\n \n \t\t/* free directory entries. full entries are re-used */\n \t\tdiscard_cache_entry(ce);\n-- \ngitgitgadget\n\n"},{"id":"455509","messageId":"e42463de0d218b63bf0c786590708b1be32257f0.1652982759.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v2.git.1652982758.gitgitgadget@gmail.com","subject":"[PATCH v2 06/10] sparse-checkout: --no-sparse-index needs a full index","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-19T17:52:34Z","receivedAt":"2022-05-19T17:54:03Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nWhen the --no-sparse-index option is supplied, the sparse-checkout\nbuiltin should explicitly ask to expand a sparse index to a full one.\nThis is currently done implicitly due to the command_requires_full_index\nprotection, but that will be removed in an upcoming change.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/sparse-checkout.c | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\nindex 88eea069ad4..cbff6ad00b0 100644\n--- a/builtin/sparse-checkout.c\n+++ b/builtin/sparse-checkout.c\n@@ -413,6 +413,9 @@ static int update_modes(int *cone_mode, int *sparse_index)\n \t\t/* force an index rewrite */\n \t\trepo_read_index(the_repository);\n \t\tthe_repository->index->updated_workdir = 1;\n+\n+\t\tif (!*sparse_index)\n+\t\t\tensure_full_index(the_repository->index);\n \t}\n \n \treturn 0;\n-- \ngitgitgadget\n\n"},{"id":"455510","messageId":"089ab086f584054a7b2bb8a2868a01c545e38d27.1652982759.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v2.git.1652982758.gitgitgadget@gmail.com","subject":"[PATCH v2 09/10] p2000: add test for 'git sparse-checkout [add|set]'","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-19T17:52:37Z","receivedAt":"2022-05-19T17:54:05Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe sparse-checkout builtin is almost completely integrated with the\nsparse index, allowing the sparse-checkout boundary to be modified\nwithout expanding a sparse index to a full one. Add a test to\np2000-sparse-operations.sh that adds a directory to the sparse-checkout\ndefinition, then removes it. Using both operations is important to\nensure that the operation is doing the same work in each repetition as\nwell as leaving the test repo in a good state for later tests.\n\nSigned-off-by: Derrick Stolee \n---\n t/perf/p2000-sparse-operations.sh | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/t/perf/p2000-sparse-operations.sh b/t/perf/p2000-sparse-operations.sh\nindex 382716cfca9..ce5cfac5714 100755\n--- a/t/perf/p2000-sparse-operations.sh\n+++ b/t/perf/p2000-sparse-operations.sh\n@@ -110,6 +110,7 @@ test_perf_on_all git add -A\n test_perf_on_all git add .\n test_perf_on_all git commit -a -m A\n test_perf_on_all git checkout -f -\n+test_perf_on_all \"git sparse-checkout add f2/f3/f1 && git sparse-checkout set $SPARSE_CONE\"\n test_perf_on_all git reset\n test_perf_on_all git reset --hard\n test_perf_on_all git reset -- does-not-exist\n-- \ngitgitgadget\n\n"},{"id":"455511","messageId":"ad9ed6973d5ed1a73a1b7e2c4f88208cbb0b31c8.1652982759.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v2.git.1652982758.gitgitgadget@gmail.com","subject":"[PATCH v2 10/10] sparse-checkout: integrate with sparse index","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-19T17:52:38Z","receivedAt":"2022-05-19T17:54:11Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nWhen modifying the sparse-checkout definition, the sparse-checkout\nbuiltin calls update_sparsity() to modify the SKIP_WORKTREE bits of all\ncache entries in the index. Before, we needed the index to be fully\nexpanded in order to ensure we had the full list of files necessary that\nmatch the new patterns.\n\nInsert a call to reset_sparse_directories() that expands sparse\ndirectories that are within the new pattern list, but only far enough\nthat every necessary file path now exists as a cache entry. The\nremaining logic within update_sparsity() will modify the SKIP_WORKTREE\nbits appropriately.\n\nThis allows us to disable command_requires_full_index within the\nsparse-checkout builtin. Add tests that demonstrate that we are not\nexpanding to a full index unnecessarily.\n\nWe can see the improved performance in the p2000 test script:\n\nTest HEAD~1 HEAD\n------------------------------------------------------------------------\n2000.24: git ... (sparse-v3) 2.14(1.55+0.58) 1.57(1.03+0.53) -26.6%\n2000.25: git ... (sparse-v4) 2.20(1.62+0.57) 1.58(0.98+0.59) -28.2%\n\nThese reductions of 26-28% are small compared to most examples, but the\ntime is dominated by writing a new copy of the base repository to the\nworktree and then deleting it again. The fact that the previous index\nexpansion was such a large portion of the time is telling how important\nit is to complete this sparse index integration.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/sparse-checkout.c | 3 +++\n t/t1092-sparse-checkout-compatibility.sh | 25 ++++++++++++++++++++++++\n unpack-trees.c | 4 ++++\n 3 files changed, 32 insertions(+)\n\ndiff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\nindex cbff6ad00b0..0157b292b36 100644\n--- a/builtin/sparse-checkout.c\n+++ b/builtin/sparse-checkout.c\n@@ -937,6 +937,9 @@ int cmd_sparse_checkout(int argc, const char **argv, const char *prefix)\n \n \tgit_config(git_default_config, NULL);\n \n+\tprepare_repo_settings(the_repository);\n+\tthe_repository->settings.command_requires_full_index = 0;\n+\n \tif (argc > 0) {\n \t\tif (!strcmp(argv[0], \"list\"))\n \t\t\treturn sparse_checkout_list(argc, argv);\ndiff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\nindex 785820f9fd5..73f4cf47314 100755\n--- a/t/t1092-sparse-checkout-compatibility.sh\n+++ b/t/t1092-sparse-checkout-compatibility.sh\n@@ -1584,6 +1584,31 @@ test_expect_success 'ls-files' '\n \tensure_not_expanded ls-files --sparse\n '\n \n+test_expect_success 'sparse index is not expanded: sparse-checkout' '\n+\tinit_repos &&\n+\n+\tensure_not_expanded sparse-checkout set deep/deeper2 &&\n+\tensure_not_expanded sparse-checkout set deep/deeper1 &&\n+\tensure_not_expanded sparse-checkout set deep &&\n+\tensure_not_expanded sparse-checkout add folder1 &&\n+\tensure_not_expanded sparse-checkout set deep/deeper1 &&\n+\tensure_not_expanded sparse-checkout set folder2 &&\n+\n+\t# Demonstrate that the checks that \"folder1/a\" is a file\n+\t# do not cause a sparse-index expansion (since it is in the\n+\t# sparse-checkout cone).\n+\techo >>sparse-index/folder2/a &&\n+\tgit -C sparse-index add folder2/a &&\n+\n+\tensure_not_expanded sparse-checkout add folder1 &&\n+\n+\t# Skip checks here, since deep/deeper1 is inside a sparse directory\n+\t# that must be expanded to check whether `deep/deeper1` is a file\n+\t# or not.\n+\tensure_not_expanded sparse-checkout set --skip-checks deep/deeper1 &&\n+\tensure_not_expanded sparse-checkout set\n+'\n+\n # NEEDSWORK: a sparse-checkout behaves differently from a full checkout\n # in this scenario, but it shouldn't.\n test_expect_success 'reset mixed and checkout orphan' '\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 7f528d35cc2..9745e0dfc34 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -18,6 +18,7 @@\n #include \"promisor-remote.h\"\n #include \"entry.h\"\n #include \"parallel-checkout.h\"\n+#include \"sparse-index.h\"\n \n /*\n * Error messages expected by scripts out of plumbing commands such as\n@@ -2018,6 +2019,9 @@ enum update_sparsity_result update_sparsity(struct unpack_trees_options *o)\n \t\t\tgoto skip_sparse_checkout;\n \t}\n \n+\t/* Expand sparse directories as needed */\n+\texpand_to_pattern_list(o->src_index, o->pl);\n+\n \t/* Set NEW_SKIP_WORKTREE on existing entries. */\n \tmark_all_ce_unused(o->src_index);\n \tmark_new_skip_worktree(o->pl, o->src_index, 0,\n-- \ngitgitgadget\n"},{"id":"455512","messageId":"ed640e3645ba4f60f06bd335b9ac7bf350dd81f9.1652982759.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v2.git.1652982758.gitgitgadget@gmail.com","subject":"[PATCH v2 08/10] sparse-index: complete partial expansion","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-19T17:52:36Z","receivedAt":"2022-05-19T17:54:14Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nTo complete the implementation of expand_to_pattern_list(), we need to\ndetect when a sparse directory entry should remain sparse. This avoids a\nfull expansion, so we now need to use the PARTIALLY_SPARSE mode to\nindicate this state.\n\nThere still are no callers to this method, but we will add one in the\nnext change.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 41 +++++++++++++++++++++++++++++++++++++----\n 1 file changed, 37 insertions(+), 4 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex 73b82e5017b..a65169030a2 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -297,8 +297,24 @@ void expand_to_pattern_list(struct index_state *istate,\n \t * continue. A NULL pattern set indicates a full expansion to a\n \t * full index.\n \t */\n-\tif (pl && !pl->use_cone_patterns)\n+\tif (pl && !pl->use_cone_patterns) {\n \t\tpl = NULL;\n+\t} else {\n+\t\t/*\n+\t\t * We might contract file entries into sparse-directory\n+\t\t * entries, and for that we will need the cache tree to\n+\t\t * be recomputed.\n+\t\t */\n+\t\tcache_tree_free(&istate->cache_tree);\n+\n+\t\t/*\n+\t\t * If there is a problem creating the cache tree, then we\n+\t\t * need to expand to a full index since we cannot satisfy\n+\t\t * the current request as a sparse index.\n+\t\t */\n+\t\tif (cache_tree_update(istate, WRITE_TREE_MISSING_OK))\n+\t\t\tpl = NULL;\n+\t}\n \n \tif (!istate->repo)\n \t\tistate->repo = the_repository;\n@@ -317,8 +333,14 @@ void expand_to_pattern_list(struct index_state *istate,\n \tfull = xcalloc(1, sizeof(struct index_state));\n \tmemcpy(full, istate, sizeof(struct index_state));\n \n+\t/*\n+\t * This slightly-misnamed 'full' index might still be sparse if we\n+\t * are only modifying the list of sparse directories. This hinges\n+\t * on whether we have a non-NULL pattern list.\n+\t */\n+\tfull->sparse_index = pl ? PARTIALLY_SPARSE : COMPLETELY_FULL;\n+\n \t/* then change the necessary things */\n-\tfull->sparse_index = 0;\n \tfull->cache_alloc = (3 * istate->cache_alloc) / 2;\n \tfull->cache_nr = 0;\n \tALLOC_ARRAY(full->cache, full->cache_alloc);\n@@ -330,11 +352,22 @@ void expand_to_pattern_list(struct index_state *istate,\n \t\tstruct cache_entry *ce = istate->cache[i];\n \t\tstruct tree *tree;\n \t\tstruct pathspec ps;\n+\t\tint dtype;\n \n \t\tif (!S_ISSPARSEDIR(ce->ce_mode)) {\n \t\t\tset_index_entry(full, full->cache_nr++, ce);\n \t\t\tcontinue;\n \t\t}\n+\n+\t\t/* We now have a sparse directory entry. Should we expand? */\n+\t\tif (pl &&\n+\t\t path_matches_pattern_list(ce->name, ce->ce_namelen,\n+\t\t\t\t\t NULL, &dtype,\n+\t\t\t\t\t pl, istate) == NOT_MATCHED) {\n+\t\t\tset_index_entry(full, full->cache_nr++, ce);\n+\t\t\tcontinue;\n+\t\t}\n+\n \t\tif (!(ce->ce_flags & CE_SKIP_WORKTREE))\n \t\t\twarning(_(\"index entry is a directory, but not sparse (%08x)\"),\n \t\t\t\tce->ce_flags);\n@@ -360,7 +393,7 @@ void expand_to_pattern_list(struct index_state *istate,\n \t/* Copy back into original index. */\n \tmemcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));\n \tmemcpy(&istate->dir_hash, &full->dir_hash, sizeof(full->dir_hash));\n-\tistate->sparse_index = 0;\n+\tistate->sparse_index = pl ? PARTIALLY_SPARSE : COMPLETELY_FULL;\n \tfree(istate->cache);\n \tistate->cache = full->cache;\n \tistate->cache_nr = full->cache_nr;\n@@ -374,7 +407,7 @@ void expand_to_pattern_list(struct index_state *istate,\n \n \t/* Clear and recompute the cache-tree */\n \tcache_tree_free(&istate->cache_tree);\n-\tcache_tree_update(istate, 0);\n+\tcache_tree_update(istate, WRITE_TREE_MISSING_OK);\n \n \ttrace2_region_leave(\"index\",\n \t\t\t pl ? \"expand_to_pattern_list\" : \"ensure_full_index\",\n-- \ngitgitgadget\n\n"},{"id":"455531","messageId":"xmqqsfp5mhcw.fsf@gitster.g","threadId":"57888","inReplyTo":"d15338573e570aebe239dacdd8c2aba275ff61b9.1652982758.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 03/10] sparse-index: create expand_to_pattern_list()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-05-19T19:50:55Z","receivedAt":"2022-05-19T19:51:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> list is NULL as that does the same as ensure_full_index(). In fact,\n> ensure_full_index() is converted to a shim over\n> expand_to_pattern_list().\n\nSounds like a natural evolution of the API that used to be\nall-or-none to expand-only-those-that-match.\n\nThe old one had a sensible name to tell us that it is about the\nin-core index (and \"full index\" implied it was about sparse-index\nfeature because what state other than \"full\" the index can be---some\nare shrunk into tree entries, which by definition is the\nsparse-index feature). Contrasted to that, the name of the new one\nis horrible. It does not even have index anywhere in the name.\n\nI wonder expand_index() would work?\n\n> +void expand_to_pattern_list(struct index_state *istate,\n> +\t\t\t struct pattern_list *pl)\n> {\n> \tint i;\n> \tstruct index_state *full;\n> \tstruct strbuf base = STRBUF_INIT;\n> \n> +\t/*\n> +\t * If the index is already full, then keep it full. We will convert\n> +\t * it to a sparse index on write, if possible.\n> +\t */\n> \tif (!istate || !istate->sparse_index)\n> \t\treturn;\n> \n> +\t/*\n> +\t * If our index is sparse, but our new pattern set does not use\n> +\t * cone mode patterns, then we need to expand the index before we\n> +\t * continue. A NULL pattern set indicates a full expansion to a\n> +\t * full index.\n> +\t */\n> +\tif (pl && !pl->use_cone_patterns)\n> +\t\tpl = NULL;\n> +\n> \tif (!istate->repo)\n> \t\tistate->repo = the_repository;\n> \n> -\ttrace2_region_enter(\"index\", \"ensure_full_index\", istate->repo);\n> +\t/*\n> +\t * A NULL pattern set indicates we are expanding a full index, so\n> +\t * we use a special region name that indicates the full expansion.\n> +\t * This is used by test cases, but also helps to differentiate the\n> +\t * two cases.\n> +\t */\n\nExcept that we lost the distinction for non-cone mode, which I am\nnot sure matters, but I suspect we do not have to, if we do not want\nto. Nobody used \"pl\" up to this point, so resetting it to NULL can\nbe done much later. In later phases of this series, we add another\ncase where we can lose pl even if we are not using cone mode, so\nthis distinction may start to matter later. I dunno.\n\nI'd invent a separate \"const char *tr2_region_label\" variable and\nset it at the beginning, regardless of where we clobber pl and why,\nand use that label variable for trace2 calls, if I were doing this\npatch. That feels much simpler and cleaner.\n\n> +\ttrace2_region_enter(\"index\",\n> +\t\t\t pl ? \"expand_to_pattern_list\" : \"ensure_full_index\",\n> +\t\t\t istate->repo);\n\n> diff --git a/sparse-index.h b/sparse-index.h\n> index 633d4fb7e31..037b541f49d 100644\n> --- a/sparse-index.h\n> +++ b/sparse-index.h\n> @@ -23,4 +23,18 @@ void expand_to_path(struct index_state *istate,\n> struct repository;\n> int set_sparse_index_config(struct repository *repo, int enable);\n> \n> +struct pattern_list;\n> +\n> +/**\n> + * Scan the given index and compare its entries to the given pattern list.\n> + * If the index is sparse and the pattern list uses cone mode patterns,\n> + * then modify the index to contain the all of the file entries within that\n> + * new pattern list. This expands sparse directories only as far as needed.\n> + *\n> + * If the pattern list is NULL or does not use cone mode patterns, then the\n> + * index is expanded to a full index.\n> + */\n> +void expand_to_pattern_list(struct index_state *istate,\n> +\t\t\t struct pattern_list *pl);\n> +\n> #endif\n"},{"id":"455532","messageId":"xmqqleuxmgof.fsf@gitster.g","threadId":"57888","inReplyTo":"269c206c331bb43006678beaa20832a75754c3df.1652982758.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 04/10] sparse-index: introduce partially-sparse indexes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-05-19T20:05:36Z","receivedAt":"2022-05-19T20:05:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> +enum sparse_index_mode {\n> +\t/*\n> +\t * COMPLETELY_FULL: there are no sparse directories\n> +\t * in the index at all.\n> +\t */\n> +\tCOMPLETELY_FULL = 0,\n\nTwo things that make me wonder are:\n\n * Do concrete values assigned to these symbols matter? If we do\n\n\tif (some_function_that_returns_this_type())\n\t\t/* ok, we know it is full */\n\t\tdo_full_thing();\n\n then the answer is yes. If we write these values to on-disk\n file, and other versions and reimplementations of Git need to\n know the concrete values, then the answer is yes. Otherwise, we\n may not want to say \"= 0\" and the like here.\n\n * Is it worth repeating the label in the comment? IOW, I am\n wondering if\n\n\t/* there are no sparse directories in the index */\n\tCOMPLETELY_FULL,\n\n is equally readable and slightly more maintainable.\n\nAlso these names being in cache.h and visible everywhere is somewhat\nworrying. Other CPP macros and enum constants in the file have\nnames that are prepared to be truly global, but COMPLETELY_FULL and\nCOLLAPSED do not hint that they are about sparse-index state as\nstrongly as PARTIALLY_SPARSE does.\n\n> -\t\t /*\n> -\t\t * sparse_index == 1 when sparse-directory\n> -\t\t * entries exist. Requires sparse-checkout\n> -\t\t * in cone mode.\n> -\t\t */\n> -\t\t sparse_index : 1;\n> +\t\t fsmonitor_has_run_once : 1;\n> +\tenum sparse_index_mode sparse_index;\n\nGood that we can lose the comment on a single bit. Are some of the\nenum sparse_index_mode values only possible in cone mode, just like\nhaving true in this bit was only possible in cone mode? Perhaps a\ncomment before \"enum sparse_index_mode {\" can say \"in non-cone mode,\nCOMPLETELY_FULL is the only possible value\" or somesuch?\n\nThanks.\n"},{"id":"455536","messageId":"xmqqczg9mg8s.fsf@gitster.g","threadId":"57888","inReplyTo":"c977001c033e8689f6d0ca52a6021bde61b1b476.1652982759.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 05/10] cache-tree: implement cache_tree_find_path()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-05-19T20:14:59Z","receivedAt":"2022-05-19T20:15:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> +struct cache_tree *cache_tree_find_path(struct cache_tree *it, const char *path)\n> +{\n> +\tconst char *slash;\n> +\tint namelen;\n> +\tstruct cache_tree_sub *down;\n> +\n> +\tif (!it)\n> +\t\treturn NULL;\n> +\tslash = strchrnul(path, '/');\n> +\tnamelen = slash - path;\n> +\tit->entry_count = -1;\n> +\tif (!*slash) {\n> +\t\tint pos;\n> +\t\tpos = cache_tree_subtree_pos(it, path, namelen);\n> +\t\tif (0 <= pos)\n> +\t\t\treturn it->down[pos]->cache_tree;\n> +\t\treturn NULL;\n> +\t}\n> +\tdown = find_subtree(it, path, namelen, 0);\n> +\tif (down)\n> +\t\treturn cache_tree_find_path(down->cache_tree, slash + 1);\n> +\treturn NULL;\n> +}\n\nThe tail recursion (and the one in the orginal) may want to be\ntrivially converted to iteration with \"goto\".\n\nIt is somewhat surprising that we didn't have any external interface\nto expose a sub-part of the cache_tree at all so far. It may be\nbecause the API was so well designed that the abstraction did not\nhave to be exposed. I dunno.\n\n> diff --git a/cache-tree.h b/cache-tree.h\n> index 8efeccebfc9..f75f8e74dcd 100644\n> --- a/cache-tree.h\n> +++ b/cache-tree.h\n> @@ -29,6 +29,8 @@ struct cache_tree_sub *cache_tree_sub(struct cache_tree *, const char *);\n> \n> int cache_tree_subtree_pos(struct cache_tree *it, const char *path, int pathlen);\n> \n> +struct cache_tree *cache_tree_find_path(struct cache_tree *it, const char *path);\n> +\n> void cache_tree_write(struct strbuf *, struct cache_tree *root);\n> struct cache_tree *cache_tree_read(const char *buffer, unsigned long size);\n"},{"id":"455537","messageId":"xmqq8rqxmg1t.fsf@gitster.g","threadId":"57888","inReplyTo":"e42463de0d218b63bf0c786590708b1be32257f0.1652982759.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 06/10] sparse-checkout: --no-sparse-index needs a full index","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-05-19T20:19:10Z","receivedAt":"2022-05-19T20:19:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> From: Derrick Stolee \n>\n> When the --no-sparse-index option is supplied, the sparse-checkout\n> builtin should explicitly ask to expand a sparse index to a full one.\n> This is currently done implicitly due to the command_requires_full_index\n> protection, but that will be removed in an upcoming change.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> builtin/sparse-checkout.c | 3 +++\n> 1 file changed, 3 insertions(+)\n>\n> diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\n> index 88eea069ad4..cbff6ad00b0 100644\n> --- a/builtin/sparse-checkout.c\n> +++ b/builtin/sparse-checkout.c\n> @@ -413,6 +413,9 @@ static int update_modes(int *cone_mode, int *sparse_index)\n> \t\t/* force an index rewrite */\n> \t\trepo_read_index(the_repository);\n> \t\tthe_repository->index->updated_workdir = 1;\n> +\n> +\t\tif (!*sparse_index)\n> +\t\t\tensure_full_index(the_repository->index);\n\ninit_opts.sparse_index is initialized to -1 (unknown) and parse_options()\nmay set it to 0 (false) or 1 (true). We call ensure_full only when\nthe caller explicitly asks with --no-sparse-index.\n\nMakes sense.\n\n> \t}\n> \n> \treturn 0;\n"},{"id":"455583","messageId":"3d4cb244-2e55-0337-90f8-a380ed836465@github.com","threadId":"57888","inReplyTo":"xmqqsfp5mhcw.fsf@gitster.g","subject":"Re: [PATCH v2 03/10] sparse-index: create expand_to_pattern_list()","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-05-20T18:01:27Z","receivedAt":"2022-05-20T18:01:37Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/19/2022 3:50 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n> \n>> list is NULL as that does the same as ensure_full_index(). In fact,\n>> ensure_full_index() is converted to a shim over\n>> expand_to_pattern_list().\n> \n> Sounds like a natural evolution of the API that used to be\n> all-or-none to expand-only-those-that-match.\n> \n> The old one had a sensible name to tell us that it is about the\n> in-core index (and \"full index\" implied it was about sparse-index\n> feature because what state other than \"full\" the index can be---some\n> are shrunk into tree entries, which by definition is the\n> sparse-index feature). Contrasted to that, the name of the new one\n> is horrible. It does not even have index anywhere in the name.\n> \n> I wonder expand_index() would work?\n\nMakes sense. Good suggestion.\n \n>> -\ttrace2_region_enter(\"index\", \"ensure_full_index\", istate->repo);\n>> +\t/*\n>> +\t * A NULL pattern set indicates we are expanding a full index, so\n>> +\t * we use a special region name that indicates the full expansion.\n>> +\t * This is used by test cases, but also helps to differentiate the\n>> +\t * two cases.\n>> +\t */\n> \n> Except that we lost the distinction for non-cone mode, which I am\n> not sure matters, but I suspect we do not have to, if we do not want\n> to. Nobody used \"pl\" up to this point, so resetting it to NULL can\n> be done much later. In later phases of this series, we add another\n> case where we can lose pl even if we are not using cone mode, so\n> this distinction may start to matter later. I dunno.\n> \n> I'd invent a separate \"const char *tr2_region_label\" variable and\n> set it at the beginning, regardless of where we clobber pl and why,\n> and use that label variable for trace2 calls, if I were doing this\n> patch. That feels much simpler and cleaner.\n\nGood idea.\n\nThanks,\n-Stolee\n"},{"id":"455584","messageId":"0b2215e1-7f12-ed0d-b7bf-03648b19e30a@github.com","threadId":"57888","inReplyTo":"xmqqleuxmgof.fsf@gitster.g","subject":"Re: [PATCH v2 04/10] sparse-index: introduce partially-sparse indexes","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-05-20T18:05:09Z","receivedAt":"2022-05-20T18:05:14Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/19/2022 4:05 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n> \n>> +enum sparse_index_mode {\n>> +\t/*\n>> +\t * COMPLETELY_FULL: there are no sparse directories\n>> +\t * in the index at all.\n>> +\t */\n>> +\tCOMPLETELY_FULL = 0,\n> \n> Two things that make me wonder are:\n> \n> * Do concrete values assigned to these symbols matter? If we do\n> \n> \tif (some_function_that_returns_this_type())\n> \t\t/* ok, we know it is full */\n> \t\tdo_full_thing();\n> \n> then the answer is yes. If we write these values to on-disk\n> file, and other versions and reimplementations of Git need to\n> know the concrete values, then the answer is yes. Otherwise, we\n> may not want to say \"= 0\" and the like here.\n\nThe = 0 case matters because that is the default when the index\nstruct is initialized to zero. The other values are not important.\n \n> * Is it worth repeating the label in the comment? IOW, I am\n> wondering if\n> \n> \t/* there are no sparse directories in the index */\n> \tCOMPLETELY_FULL,\n> \n> is equally readable and slightly more maintainable.\n\nCan do.\n\n> Also these names being in cache.h and visible everywhere is somewhat\n> worrying. Other CPP macros and enum constants in the file have\n> names that are prepared to be truly global, but COMPLETELY_FULL and\n> COLLAPSED do not hint that they are about sparse-index state as\n> strongly as PARTIALLY_SPARSE does.\n\nWould prepending with \"INDEX_\" be sufficient?\n\n>> -\t\t /*\n>> -\t\t * sparse_index == 1 when sparse-directory\n>> -\t\t * entries exist. Requires sparse-checkout\n>> -\t\t * in cone mode.\n>> -\t\t */\n>> -\t\t sparse_index : 1;\n>> +\t\t fsmonitor_has_run_once : 1;\n>> +\tenum sparse_index_mode sparse_index;\n> \n> Good that we can lose the comment on a single bit. Are some of the\n> enum sparse_index_mode values only possible in cone mode, just like\n> having true in this bit was only possible in cone mode? Perhaps a\n> comment before \"enum sparse_index_mode {\" can say \"in non-cone mode,\n> COMPLETELY_FULL is the only possible value\" or somesuch?\n\nI can add that comment for the COMPLETELY_FULL enum value.\n\nThanks,\n-Stolee\n"},{"id":"455585","messageId":"9a89398a-c5ec-d386-d554-a077fefcd46b@github.com","threadId":"57888","inReplyTo":"xmqqczg9mg8s.fsf@gitster.g","subject":"Re: [PATCH v2 05/10] cache-tree: implement cache_tree_find_path()","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-05-20T18:13:03Z","receivedAt":"2022-05-20T18:13:13Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/19/2022 4:14 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n> \n>> +struct cache_tree *cache_tree_find_path(struct cache_tree *it, const char *path)\n>> +{\n>> +\tconst char *slash;\n>> +\tint namelen;\n>> +\tstruct cache_tree_sub *down;\n>> +\n>> +\tif (!it)\n>> +\t\treturn NULL;\n>> +\tslash = strchrnul(path, '/');\n>> +\tnamelen = slash - path;\n>> +\tit->entry_count = -1;\n>> +\tif (!*slash) {\n>> +\t\tint pos;\n>> +\t\tpos = cache_tree_subtree_pos(it, path, namelen);\n>> +\t\tif (0 <= pos)\n>> +\t\t\treturn it->down[pos]->cache_tree;\n>> +\t\treturn NULL;\n>> +\t}\n>> +\tdown = find_subtree(it, path, namelen, 0);\n>> +\tif (down)\n>> +\t\treturn cache_tree_find_path(down->cache_tree, slash + 1);\n>> +\treturn NULL;\n>> +}\n> \n> The tail recursion (and the one in the orginal) may want to be\n> trivially converted to iteration with \"goto\".\n\nGood idea!\n \n> It is somewhat surprising that we didn't have any external interface\n> to expose a sub-part of the cache_tree at all so far. It may be\n> because the API was so well designed that the abstraction did not\n> have to be exposed. I dunno.\n\nI think the abstraction definitely fit the shape of its consumers\npretty perfectly. I wonder if having a method like this will make\nus think of new ways to use the cache tree for other things.\n\nThanks,\n-Stolee\n"},{"id":"455586","messageId":"xmqqbkvshxvn.fsf@gitster.g","threadId":"57888","inReplyTo":"346c56bf2560c5a89850ef4f8a58fbe17cde10fc.1652982759.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 07/10] sparse-index: partially expand directories","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-05-20T18:17:32Z","receivedAt":"2022-05-20T18:18:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> @@ -231,18 +236,41 @@ static int add_path_to_index(const struct object_id *oid,\n> \t\t\t struct strbuf *base, const char *path,\n> \t\t\t unsigned int mode, void *context)\n> {\n\nOK, this function is a callback of read_tree_at(), whose caller is\nwalking the source (=current) index, and while it is copying\nexisting non-directory entries to the destination (=ctx->write)\nindex, it found a tree in the source in-core index that does not\nmatch the cone pattern (or we are expanding fully). Our job is to\nexpand the given tree as a \"subdirectory\" in the project into the\ndestination index.\n\nWe used to just let the calling read_tree_at() fully and recursively\nwalk the tree while adding any non-tree entries to the destination.\nNow, we have the pattern list in the context, we go more selective.\n\nThe design makes sense.\n\n> +\tstruct modify_index_context *ctx = (struct modify_index_context *)context;\n> \tstruct cache_entry *ce;\n> \tsize_t len = base->len;\n> \n> +\tif (S_ISDIR(mode)) {\n> +\t\tint dtype;\n> +\t\tsize_t baselen = base->len;\n> +\t\tif (!ctx->pl)\n> +\t\t\treturn READ_TREE_RECURSIVE;\n\nFully recursive case. We can do without any match, just like the\ncaller (i.e. expand_to_pattern_list) did, when the pattern list is\nNULL.\n\n> +\t\t/*\n> +\t\t * Have we expanded to a point outside of the sparse-checkout?\n> +\t\t */\n> +\t\tstrbuf_addstr(base, path);\n> +\t\tstrbuf_add(base, \"/-\", 2);\n> +\n> +\t\tif (path_matches_pattern_list(base->buf, base->len,\n> +\t\t\t\t\t NULL, &dtype,\n> +\t\t\t\t\t ctx->pl, ctx->write)) {\n\nIf that sample path in the directory matches (MATCHED or\nMATCHED_RECURSIVE) the patterns, we recurse into the tree to expand.\n\nCan the function return UNDECIDED here? If so what should happen?\nAs written, the code will behave as if it matched, and it is not\nquite clear if that is the behaviour intended by this patch or an\naccident.\n\n> +\t\t\tstrbuf_setlen(base, baselen);\n> +\t\t\treturn READ_TREE_RECURSIVE;\n> +\t\t}\n\nThe caller found a tree at path in the index. We check if\nour patterns match a fictitious path + \"/-\", which may exist\nif the is a directory and if there is a funny named file or\ndirectory \"-\" in it.\n\nWhy \"-\"? Are we trying ot see if \"ctx->pl\" matches \"anything\" in\nthe directory that is at ? Is the assumption here that pl\nonly names directories literally without blobs (I presume that is\nthe same thing as assuming the cone mode)?\n\nI am trying to see if there is a way that expresses the intention of\nthis code more clearly than using an arbitrary path \"-\" (and trying\nto figure out if I got the intention right in the first place ;-)..\n\n> +\t\t/*\n> +\t\t * The path \"{base}{path}/\" is a sparse directory. Create the correct\n> +\t\t * name for inserting the entry into the index.\n> +\t\t */\n> +\t\tstrbuf_setlen(base, base->len - 1);\n\nThis removes that phoney \"-\" while keeping the trailing \"/\". Just\nlike \"-\" was unclear, understanding this \"- 1\" requires that the\nreader understands why \"/-\" was used earlier.\n\nThe resulting \"base\" is used in the newly created cache entry to\nrepresent the (unexpanded) directory below, and such a cache entry\nis supposed to have a path with a trailing slash, so it makes sense.\n\n> +\t} else {\n> +\t\tstrbuf_addstr(base, path);\n\nFor any non-tree thing, we use the given path for the cache entry to\nrepresent it.\n\n> +\t}\n> +\n> +\tce = make_cache_entry(ctx->write, mode, oid, base->buf, 0, 0);\n> \tce->ce_flags |= CE_SKIP_WORKTREE | CE_EXTENDED;\n> -\tset_index_entry(istate, istate->cache_nr++, ce);\n> +\tset_index_entry(ctx->write, ctx->write->cache_nr++, ce);\n\nAnd the cache entry (newly created) is added to the destination.\nUnlike what happens in the caller (i.e. expand_to_pattern_list) that\nmoves the cache entry taken from the source index to the destination\nindex, the caller will discard the cache entry taken from the source\nindex after read_tree_at() returns, and we create a new instance for\nourselves here, even if we _could_ have reused it (by passing it in\nthe context structure, for example).\n\n> \tstrbuf_setlen(base, len);\n\nAnd we restore the length of the path in the base to the original\nbefore we return.\n\n> \treturn 0;\n\nReturning 0 as opposed to READ_TREE_RECURSIVE here means \"we've\ndealt with the entry; don't recurse into subtree even if you called\nus with a tree\", which is the right thing to do here, as we did have\ndone all we need to here.\n\nOK, except for that \"/-\" thing, all of the above makes sense to me.\n\nThanks.\n\n> @@ -254,6 +282,7 @@ void expand_to_pattern_list(struct index_state *istate,\n> \tint i;\n> \tstruct index_state *full;\n> \tstruct strbuf base = STRBUF_INIT;\n> +\tstruct modify_index_context ctx;\n> \n> \t/*\n> \t * If the index is already full, then keep it full. We will convert\n> @@ -294,6 +323,9 @@ void expand_to_pattern_list(struct index_state *istate,\n> \tfull->cache_nr = 0;\n> \tALLOC_ARRAY(full->cache, full->cache_alloc);\n> \n> +\tctx.write = full;\n> +\tctx.pl = pl;\n> +\n> \tfor (i = 0; i < istate->cache_nr; i++) {\n> \t\tstruct cache_entry *ce = istate->cache[i];\n> \t\tstruct tree *tree;\n> @@ -319,7 +351,7 @@ void expand_to_pattern_list(struct index_state *istate,\n> \t\tstrbuf_add(&base, ce->name, strlen(ce->name));\n> \n> \t\tread_tree_at(istate->repo, tree, &base, &ps,\n> -\t\t\t add_path_to_index, full);\n> +\t\t\t add_path_to_index, &ctx);\n> \n> \t\t/* free directory entries. full entries are re-used */\n> \t\tdiscard_cache_entry(ce);\n"},{"id":"455587","messageId":"xmqq4k1khxl1.fsf@gitster.g","threadId":"57888","inReplyTo":"0b2215e1-7f12-ed0d-b7bf-03648b19e30a@github.com","subject":"Re: [PATCH v2 04/10] sparse-index: introduce partially-sparse indexes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-05-20T18:23:54Z","receivedAt":"2022-05-20T18:24:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n>> Also these names being in cache.h and visible everywhere is somewhat\n>> worrying. Other CPP macros and enum constants in the file have\n>> names that are prepared to be truly global, but COMPLETELY_FULL and\n>> COLLAPSED do not hint that they are about sparse-index state as\n>> strongly as PARTIALLY_SPARSE does.\n>\n> Would prepending with \"INDEX_\" be sufficient?\n\nYeah, index-collapsed, index-expanded, etc., sounds distinctive\nenough. Sorry, but I cannot think of a good phrase for partially\nexpanded case that is short, succinct and would go well with the\nfully expanded and fully collapsed cases.\n\nThanks.\n"},{"id":"455588","messageId":"8c093377-74f7-0a1e-fbcc-8a1aedfe3fca@github.com","threadId":"57888","inReplyTo":"xmqqbkvshxvn.fsf@gitster.g","subject":"Re: [PATCH v2 07/10] sparse-index: partially expand directories","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-05-20T18:33:17Z","receivedAt":"2022-05-20T18:33:25Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/20/2022 2:17 PM, Junio C Hamano wrote:> \"Derrick Stolee via GitGitGadget\" writes:\n> \n>> @@ -231,18 +236,41 @@ static int add_path_to_index(const struct object_id *oid,\n>> \t\t\t struct strbuf *base, const char *path,\n>> \t\t\t unsigned int mode, void *context)\n>> {\n> \n> OK, this function is a callback of read_tree_at(), whose caller is\n> walking the source (=current) index, and while it is copying\n> existing non-directory entries to the destination (=ctx->write)\n> index, it found a tree in the source in-core index that does not\n> match the cone pattern (or we are expanding fully). Our job is to\n> expand the given tree as a \"subdirectory\" in the project into the\n> destination index.\n> \n> We used to just let the calling read_tree_at() fully and recursively\n> walk the tree while adding any non-tree entries to the destination.\n> Now, we have the pattern list in the context, we go more selective.\n> \n> The design makes sense.\n> \n>> +\tstruct modify_index_context *ctx = (struct modify_index_context *)context;\n>> \tstruct cache_entry *ce;\n>> \tsize_t len = base->len;\n>> \n>> +\tif (S_ISDIR(mode)) {\n>> +\t\tint dtype;\n>> +\t\tsize_t baselen = base->len;\n>> +\t\tif (!ctx->pl)\n>> +\t\t\treturn READ_TREE_RECURSIVE;\n> \n> Fully recursive case. We can do without any match, just like the\n> caller (i.e. expand_to_pattern_list) did, when the pattern list is\n> NULL.\n> \n>> +\t\t/*\n>> +\t\t * Have we expanded to a point outside of the sparse-checkout?\n>> +\t\t */\n>> +\t\tstrbuf_addstr(base, path);\n>> +\t\tstrbuf_add(base, \"/-\", 2);\n>> +\n>> +\t\tif (path_matches_pattern_list(base->buf, base->len,\n>> +\t\t\t\t\t NULL, &dtype,\n>> +\t\t\t\t\t ctx->pl, ctx->write)) {\n> \n> If that sample path in the directory matches (MATCHED or\n> MATCHED_RECURSIVE) the patterns, we recurse into the tree to expand.\n> \n> Can the function return UNDECIDED here? If so what should happen?\n> As written, the code will behave as if it matched, and it is not\n> quite clear if that is the behaviour intended by this patch or an\n> accident.\n\nUNDECIDED can only be returned when not in cone mode. We are in cone mode\nwhen this helper is used.\n\n>> +\t\t\tstrbuf_setlen(base, baselen);\n>> +\t\t\treturn READ_TREE_RECURSIVE;\n>> +\t\t}\n> \n> The caller found a tree at path in the index. We check if\n> our patterns match a fictitious path + \"/-\", which may exist\n> if the is a directory and if there is a funny named file or\n> directory \"-\" in it.\n> \n> Why \"-\"? Are we trying ot see if \"ctx->pl\" matches \"anything\" in\n> the directory that is at ? Is the assumption here that pl\n> only names directories literally without blobs (I presume that is\n> the same thing as assuming the cone mode)?\n> \n> I am trying to see if there is a way that expresses the intention of\n> this code more clearly than using an arbitrary path \"-\" (and trying\n> to figure out if I got the intention right in the first place ;-)..\n\nThe '+ \"/-\"' is there to give us an example file path for \"\" as a\ndirectory. This is specifically because path_matches_pattern_list() checks\nthe parent directories for matches, expecting the input to be a file name.\n\nThis could use a comment. I'm thinking...\n\n/*\n * Have we expanded to a point outside of the sparse-checkout?\n *\n * Artificially pad the path name with a slash \"/\" to\n * indicate it as a directory, and add an arbitrary file\n * name (\"-\") so we can consider base->buf as a file name\n * to match against the cone-mode patterns.\n *\n * If we compared just \"path\", then we would expand more\n * than we should. Since every file at root is always\n * included, we would expand every directory at root at\n * least one level deep instead of using sparse directory\n * entries.\n */\n\n>> +\t\t/*\n>> +\t\t * The path \"{base}{path}/\" is a sparse directory. Create the correct\n>> +\t\t * name for inserting the entry into the index.\n>> +\t\t */\n>> +\t\tstrbuf_setlen(base, base->len - 1);\n> \n> This removes that phoney \"-\" while keeping the trailing \"/\". Just\n> like \"-\" was unclear, understanding this \"- 1\" requires that the\n> reader understands why \"/-\" was used earlier.\n> \n> The resulting \"base\" is used in the newly created cache entry to\n> represent the (unexpanded) directory below, and such a cache entry\n> is supposed to have a path with a trailing slash, so it makes sense.\n> \n>> +\t} else {\n>> +\t\tstrbuf_addstr(base, path);\n> \n> For any non-tree thing, we use the given path for the cache entry to\n> represent it.\n> \n>> +\t}\n>> +\n>> +\tce = make_cache_entry(ctx->write, mode, oid, base->buf, 0, 0);\n>> \tce->ce_flags |= CE_SKIP_WORKTREE | CE_EXTENDED;\n>> -\tset_index_entry(istate, istate->cache_nr++, ce);\n>> +\tset_index_entry(ctx->write, ctx->write->cache_nr++, ce);\n> \n> And the cache entry (newly created) is added to the destination.\n> Unlike what happens in the caller (i.e. expand_to_pattern_list) that\n> moves the cache entry taken from the source index to the destination\n> index, the caller will discard the cache entry taken from the source\n> index after read_tree_at() returns, and we create a new instance for\n> ourselves here, even if we _could_ have reused it (by passing it in\n> the context structure, for example).\n> \n>> \tstrbuf_setlen(base, len);\n> \n> And we restore the length of the path in the base to the original\n> before we return.\n> \n>> \treturn 0;\n> \n> Returning 0 as opposed to READ_TREE_RECURSIVE here means \"we've\n> dealt with the entry; don't recurse into subtree even if you called\n> us with a tree\", which is the right thing to do here, as we did have\n> done all we need to here.\n> \n> OK, except for that \"/-\" thing, all of the above makes sense to me.\n\nThanks for your careful read. Hopefully my explanation of the \"/-\" thing\nhelps.\n\nThanks,\n-Stolee\n"},{"id":"455665","messageId":"xmqqsfp3coqy.fsf@gitster.g","threadId":"57888","inReplyTo":"ed640e3645ba4f60f06bd335b9ac7bf350dd81f9.1652982759.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 08/10] sparse-index: complete partial expansion","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-05-21T07:45:57Z","receivedAt":"2022-05-21T07:46:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> +\tif (pl && !pl->use_cone_patterns) {\n> \t\tpl = NULL;\n> +\t} else {\n> +\t\t/*\n> +\t\t * We might contract file entries into sparse-directory\n> +\t\t * entries, and for that we will need the cache tree to\n> +\t\t * be recomputed.\n> +\t\t */\n> +\t\tcache_tree_free(&istate->cache_tree);\n> +\n> +\t\t/*\n> +\t\t * If there is a problem creating the cache tree, then we\n> +\t\t * need to expand to a full index since we cannot satisfy\n> +\t\t * the current request as a sparse index.\n> +\t\t */\n> +\t\tif (cache_tree_update(istate, WRITE_TREE_MISSING_OK))\n> +\t\t\tpl = NULL;\n> +\t}\n\nSo, if the current index has some irrelevant (i.e. do not match the\npattern list) subtrees in collapsed form, presense of an unmerged\nentry, presumably inside the cone(s) we are interested in, makes us\nlose the pattern list here, and we end up expanding everything?\n\nI suspect that is a situation that is not so uncommon. Working\ninside a narrow cone of a wide tree, performing a merge would\nhopefully allow many subtrees that are outside of the cones of our\ninterest merged without getting expanded at all (e.g. only the other\nside touched these subtrees we are not working on, so their version\nwill become the merge result), while changes to some paths in the\ncone of our interest may result in true conflicts represented as\ncache entries at higher stages, needing conflict resolution\nconcluded with \"git add\". Having to expand these subtrees that we\nmanaged to merge while still collapsed, only because we have\nconflicts in some other parts of the tree, feels somewhat sad.\n\nBy the way, why are we passing the \"--missing-ok\" option to \"git\nwrite-tree\" here?\n\n> @@ -330,11 +352,22 @@ void expand_to_pattern_list(struct index_state *istate,\n> \t\tstruct cache_entry *ce = istate->cache[i];\n> \t\tstruct tree *tree;\n> \t\tstruct pathspec ps;\n> +\t\tint dtype;\n> \n> \t\tif (!S_ISSPARSEDIR(ce->ce_mode)) {\n> \t\t\tset_index_entry(full, full->cache_nr++, ce);\n> \t\t\tcontinue;\n> \t\t}\n> +\n> +\t\t/* We now have a sparse directory entry. Should we expand? */\n> +\t\tif (pl &&\n> +\t\t path_matches_pattern_list(ce->name, ce->ce_namelen,\n> +\t\t\t\t\t NULL, &dtype,\n> +\t\t\t\t\t pl, istate) == NOT_MATCHED) {\n> +\t\t\tset_index_entry(full, full->cache_nr++, ce);\n> +\t\t\tcontinue;\n> +\t\t}\n> +\n> \t\tif (!(ce->ce_flags & CE_SKIP_WORKTREE))\n> \t\t\twarning(_(\"index entry is a directory, but not sparse (%08x)\"),\n> \t\t\t\tce->ce_flags);\n> @@ -360,7 +393,7 @@ void expand_to_pattern_list(struct index_state *istate,\n> \t/* Copy back into original index. */\n> \tmemcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));\n> \tmemcpy(&istate->dir_hash, &full->dir_hash, sizeof(full->dir_hash));\n> -\tistate->sparse_index = 0;\n> +\tistate->sparse_index = pl ? PARTIALLY_SPARSE : COMPLETELY_FULL;\n> \tfree(istate->cache);\n> \tistate->cache = full->cache;\n> \tistate->cache_nr = full->cache_nr;\n> @@ -374,7 +407,7 @@ void expand_to_pattern_list(struct index_state *istate,\n> \n> \t/* Clear and recompute the cache-tree */\n> \tcache_tree_free(&istate->cache_tree);\n> -\tcache_tree_update(istate, 0);\n> +\tcache_tree_update(istate, WRITE_TREE_MISSING_OK);\n\nThe same question here. We didn't say \"missing trees are OK\". What\nmade it OK in this change?\n\n"},{"id":"455766","messageId":"5909f466-c323-0874-b175-51fe5e93dc12@github.com","threadId":"57888","inReplyTo":"xmqqsfp3coqy.fsf@gitster.g","subject":"Re: [PATCH v2 08/10] sparse-index: complete partial expansion","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-05-23T13:13:33Z","receivedAt":"2022-05-23T13:14:31Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/21/2022 3:45 AM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n> \n>> +\tif (pl && !pl->use_cone_patterns) {\n>> \t\tpl = NULL;\n>> +\t} else {\n>> +\t\t/*\n>> +\t\t * We might contract file entries into sparse-directory\n>> +\t\t * entries, and for that we will need the cache tree to\n>> +\t\t * be recomputed.\n>> +\t\t */\n>> +\t\tcache_tree_free(&istate->cache_tree);\n>> +\n>> +\t\t/*\n>> +\t\t * If there is a problem creating the cache tree, then we\n>> +\t\t * need to expand to a full index since we cannot satisfy\n>> +\t\t * the current request as a sparse index.\n>> +\t\t */\n>> +\t\tif (cache_tree_update(istate, WRITE_TREE_MISSING_OK))\n>> +\t\t\tpl = NULL;\n>> +\t}\n> \n> So, if the current index has some irrelevant (i.e. do not match the\n> pattern list) subtrees in collapsed form, presense of an unmerged\n> entry, presumably inside the cone(s) we are interested in, makes us\n> lose the pattern list here, and we end up expanding everything?\n> \n> I suspect that is a situation that is not so uncommon. Working\n> inside a narrow cone of a wide tree, performing a merge would\n> hopefully allow many subtrees that are outside of the cones of our\n> interest merged without getting expanded at all (e.g. only the other\n> side touched these subtrees we are not working on, so their version\n> will become the merge result), while changes to some paths in the\n> cone of our interest may result in true conflicts represented as\n> cache entries at higher stages, needing conflict resolution\n> concluded with \"git add\". Having to expand these subtrees that we\n> managed to merge while still collapsed, only because we have\n> conflicts in some other parts of the tree, feels somewhat sad.\n\nYou are correct that conflicts outside of the sparse-checkout cone will\ncause index expansion. That happens during the 'git merge' command, but\nthe index will continue to fail to collapse as long as those conflicts\nstill exist in the index.\n\nWhen there are conflicts like this during the merge, then the index\nexpansion is not as large of a portion of the command as normal, because\nthe conflict resolution also takes some time to compute. The commands\nafterwards do take longer purely because of the expanded index.\n\nHowever, this state is also not as common as you might think. If a user\nhas a sparse-checkout cone specified, then they are unlikely to change\nfiles outside of the sparse-checkout cone. They would not be the reason\nthat those files have a conflict. The conflicts would exist only if they\nare merging branches that had conflicts outside of the cone. Typically,\nany merge of external changes like this are of the form of \"git pull\" or\n\"git rebase\", in which case the conflicts are still \"local\" to the\ndeveloper's changes.\n\nYou are right that there is additional work that could be done here,\nspecifically allowing the cache tree to partially succeed and use the\nsuccessfully generated trees to create sparse directory entries where\npossible. This was not viable before because we lacked the \"partially\nexpanded\" index state. This series establishes the necessary vocabulary to\ndo such an improvement later.\n> By the way, why are we passing the \"--missing-ok\" option to \"git\n> write-tree\" here?\n> \n>> +\tcache_tree_update(istate, WRITE_TREE_MISSING_OK);\n> \n> The same question here. We didn't say \"missing trees are OK\". What\n> made it OK in this change?\n \nBoth of these additions of WRITE_TREE_MISSING_OK are not needed. I\nthink I added them in an earlier version, thinking they were needed\ndue to something in the Scalar functional tests. I confirmed just now\nthat they are not needed for that. I will remove them.\n\nThanks,\n-Stolee\n"},{"id":"455767","messageId":"f9abea8d-5386-5275-4de2-27d443945c7a@github.com","threadId":"57888","inReplyTo":"5909f466-c323-0874-b175-51fe5e93dc12@github.com","subject":"Re: [PATCH v2 08/10] sparse-index: complete partial expansion","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-05-23T13:18:43Z","receivedAt":"2022-05-23T13:18:55Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/23/2022 9:13 AM, Derrick Stolee wrote:\n> On 5/21/2022 3:45 AM, Junio C Hamano wrote:\n>> \"Derrick Stolee via GitGitGadget\" writes:\n\n>> By the way, why are we passing the \"--missing-ok\" option to \"git\n>> write-tree\" here?\n>>\n>>> +\tcache_tree_update(istate, WRITE_TREE_MISSING_OK);\n>>\n>> The same question here. We didn't say \"missing trees are OK\". What\n>> made it OK in this change?\n> \n> Both of these additions of WRITE_TREE_MISSING_OK are not needed. I\n> think I added them in an earlier version, thinking they were needed\n> due to something in the Scalar functional tests. I confirmed just now\n> that they are not needed for that. I will remove them.\n\nAs I went to remove these from sparse-index.c, I found another that\nexists, but for good reason. See 8a96b9d0a (sparse-index: use\nWRITE_TREE_MISSING_OK, 2021-09-08), which explains that that instance\nneeds the flag because it could be used during 'git add'.\n\nIt still isn't necessary in the instances being added here, so I will\nremove them.\n\nThanks,\n-Stolee\n"},{"id":"455771","messageId":"pull.1208.v3.git.1653313726.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v2.git.1652982758.gitgitgadget@gmail.com","subject":"[PATCH v3 00/10] Sparse index: integrate with sparse-checkout","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-23T13:48:36Z","receivedAt":"2022-05-23T13:48:56Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"This series is based on ds/sparse-colon-path.\n\nThis series integrates the 'git sparse-checkout' builtin with the sparse\nindex. This is the last integration that we fast-tracked into the\nmicrosoft/git fork. After this, we have no work in flight that would\nconflict with a Google Summer of Code project in this area.\n\nThe tricky part about the sparse-checkout builtin is that we actually do\nneed to expand the index when growing the sparse-checkout boundary. The\ntrick is to expand it only as far as we need it, and then ensure that we\ncollapse any removed directories before the command completes.\n\nTo do this, we introduce a concept of a \"partially expanded\" index. In fact,\nwe break the boolean sparse_index member into an enum with three states:\n\n * INDEX_EXPANDED (0): No sparse directories exist.\n\n * INDEX_COLLAPSED: Sparse directories may exist. Files outside the\n sparse-checkout cone are reduced to sparse directory entries whenever\n possible.\n\n * INDEX_PARTIALLY_SPARSE: Sparse directories may exist. Some file entries\n outside the sparse-checkout cone may exist. Running convert_to_sparse()\n may further reduce those files to sparse directory entries.\n\nMost of the patches in this series focus on introducing this enum and\ncarefully converting previous uses of the boolean to use the enum. Some\nadditional work is required to refactor ensure_full_index() into a new\nexpand_index() method, as they are doing essentially the same thing, but\nwith different scopes.\n\nThe result is improved performance on the sparse-checkout builtin as\ndemonstrated in a new p2000-sparse-operations.sh performance test:\n\n\nTest HEAD~1 HEAD\n================\n\n2000.24: git sparse-checkout ... (sparse-v3) 2.14(1.55+0.58) 1.57(1.03+0.53)\n-26.6% 2000.25: git sparse-checkout ... (sparse-v4) 2.20(1.62+0.57)\n1.58(0.98+0.59) -28.2%\n\nThe improvement here is less dramatic because the operation is dominated by\nwriting and deleting a lot of files in the worktree. A repeated no-op\noperation such as git sparse-checkout set $SPARSE_CONE would show a greater\nimprovement, but is less interesting since it could gain that improvement\nwithout satisfying the \"hard\" parts of this builtin.\n\nI specifically chose how to update the tests in t1092 and p2000 to avoid\nconflicts with Victoria's 'git stash' work.\n\n\nUpdates in v3\n=============\n\n * expand_to_pattern_list() is renamed to expand_index().\n\n * The enum values are renamed to be less ambiguous.\n\n * Use a local variable to store the trace2 region label.\n\n * A tail-recursive method is converted to an iterative one.\n\n * Comments are added.\n\n * WRITE_MISSING_TREE_OK flags are removed as unnecessary.\n\n\nUpdates in v2\n=============\n\n * Typo fixes.\n * Two patches are added to the start to (a) refactor existing sparse index\n content tests, and (b) add new sparse index content tests with additional\n scenarios.\n * Use NOT_MATCHED directly instead of implicitly allowing UNDECIDED when\n matching in cone mode.\n\nThanks, -Stolee\n\nDerrick Stolee (10):\n t1092: refactor 'sparse-index contents' test\n t1092: stress test 'git sparse-checkout set'\n sparse-index: create expand_index()\n sparse-index: introduce partially-sparse indexes\n cache-tree: implement cache_tree_find_path()\n sparse-checkout: --no-sparse-index needs a full index\n sparse-index: partially expand directories\n sparse-index: complete partial expansion\n p2000: add test for 'git sparse-checkout [add|set]'\n sparse-checkout: integrate with sparse index\n\n builtin/sparse-checkout.c | 8 +-\n cache-tree.c | 27 +++++\n cache-tree.h | 2 +\n cache.h | 33 ++++--\n read-cache.c | 6 +-\n sparse-index.c | 132 ++++++++++++++++++++---\n sparse-index.h | 13 +++\n t/perf/p2000-sparse-operations.sh | 1 +\n t/t1092-sparse-checkout-compatibility.sh | 95 ++++++++++++----\n unpack-trees.c | 4 +\n 10 files changed, 275 insertions(+), 46 deletions(-)\n\n\nbase-commit: 124b05b23005437fa5fb91863bde2a8f5840e164\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1208%2Fderrickstolee%2Fsparse-index%2Fsparse-checkout-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1208/derrickstolee/sparse-index/sparse-checkout-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/1208\n\nRange-diff vs v2:\n\n 1: f2960747ed8 = 1: f2960747ed8 t1092: refactor 'sparse-index contents' test\n 2: 5030eeecf4f = 2: 5030eeecf4f t1092: stress test 'git sparse-checkout set'\n 3: d15338573e5 ! 3: 44b0549a288 sparse-index: create expand_to_pattern_list()\n @@ Metadata\n Author: Derrick Stolee \n \n ## Commit message ##\n - sparse-index: create expand_to_pattern_list()\n + sparse-index: create expand_index()\n \n This is the first change in a series to allow modifying the\n sparse-checkout pattern set without expanding a sparse index to a full\n @@ Commit message\n \n We already have logic in ensure_full_index() that expands the index\n entries, so we will use that as our base. Create a new method,\n - expand_to_pattern_list(), which takes a pattern list, but for now mostly\n - ignores it. The current implementation is only correct when the pattern\n - list is NULL as that does the same as ensure_full_index(). In fact,\n - ensure_full_index() is converted to a shim over\n - expand_to_pattern_list().\n + expand_index(), which takes a pattern list, but for now mostly ignores\n + it. The current implementation is only correct when the pattern list is\n + NULL as that does the same as ensure_full_index(). In fact,\n + ensure_full_index() is converted to a shim over expand_index().\n \n - A future update will actually implement expand_to_pattern_list() to its\n - full capabilities. For now, it is created and documented.\n + A future update will actually implement expand_index() to its full\n + capabilities. For now, it is created and documented.\n \n Signed-off-by: Derrick Stolee \n \n @@ sparse-index.c: static int add_path_to_index(const struct object_id *oid,\n }\n \n -void ensure_full_index(struct index_state *istate)\n -+void expand_to_pattern_list(struct index_state *istate,\n -+\t\t\t struct pattern_list *pl)\n ++void expand_index(struct index_state *istate, struct pattern_list *pl)\n {\n \tint i;\n \tstruct index_state *full;\n \tstruct strbuf base = STRBUF_INIT;\n ++\tconst char *tr_region;\n \n +\t/*\n +\t * If the index is already full, then keep it full. We will convert\n @@ sparse-index.c: static int add_path_to_index(const struct object_id *oid,\n +\t * This is used by test cases, but also helps to differentiate the\n +\t * two cases.\n +\t */\n -+\ttrace2_region_enter(\"index\",\n -+\t\t\t pl ? \"expand_to_pattern_list\" : \"ensure_full_index\",\n -+\t\t\t istate->repo);\n ++\ttr_region = pl ? \"expand_index\" : \"ensure_full_index\";\n ++\ttrace2_region_enter(\"index\", tr_region, istate->repo);\n \n \t/* initialize basics of new index */\n \tfull = xcalloc(1, sizeof(struct index_state));\n @@ sparse-index.c: void ensure_full_index(struct index_state *istate)\n \tcache_tree_update(istate, 0);\n \n -\ttrace2_region_leave(\"index\", \"ensure_full_index\", istate->repo);\n -+\ttrace2_region_leave(\"index\",\n -+\t\t\t pl ? \"expand_to_pattern_list\" : \"ensure_full_index\",\n -+\t\t\t istate->repo);\n ++\ttrace2_region_leave(\"index\", tr_region, istate->repo);\n +}\n +\n +void ensure_full_index(struct index_state *istate)\n +{\n -+\texpand_to_pattern_list(istate, NULL);\n ++\texpand_index(istate, NULL);\n }\n \n void ensure_correct_sparsity(struct index_state *istate)\n @@ sparse-index.h: void expand_to_path(struct index_state *istate,\n + * If the pattern list is NULL or does not use cone mode patterns, then the\n + * index is expanded to a full index.\n + */\n -+void expand_to_pattern_list(struct index_state *istate,\n -+\t\t\t struct pattern_list *pl);\n ++void expand_index(struct index_state *istate, struct pattern_list *pl);\n +\n #endif\n 4: 269c206c331 ! 4: 8a459d6c67d sparse-index: introduce partially-sparse indexes\n @@ Commit message\n For now, convert the single-bit member 'sparse_index' in 'struct\n index_state' to be a an 'enum sparse_index_mode' with three modes:\n \n - * COMPLETELY_FULL (0): No sparse directories exist.\n + * INDEX_EXPANDED (0): No sparse directories exist. This is always the\n + case for repositories that do not use cone-mode sparse-checkout.\n \n - * COMPLETELY_SPARSE (1): Sparse directories may exist. Files outside the\n + * INDEX_COLLAPSED: Sparse directories may exist. Files outside the\n sparse-checkout cone are reduced to sparse directory entries whenever\n possible.\n \n - * PARTIALLY_SPARSE (2): Sparse directories may exist. Some file entries\n - outside the sparse-checkout cone may exist. Running\n + * INDEX_PARTIALLY_SPARSE: Sparse directories may exist. Some file\n + entries outside the sparse-checkout cone may exist. Running\n convert_to_sparse() may further reduce those files to sparse directory\n entries.\n \n The main reason to store this extra information is to allow\n convert_to_sparse() to short-circuit when the index is already in\n - COMPLETELY_SPARSE mode but to actually do the necessary work when in\n - PARTIALLY_SPARSE mode.\n + INDEX_EXPANDED mode but to actually do the necessary work when in\n + INDEX_PARTIALLY_SPARSE mode.\n \n - The PARTIALLY_SPARSE mode will be used in an upcoming change.\n + The INDEX_PARTIALLY_SPARSE mode will be used in an upcoming change.\n \n Signed-off-by: Derrick Stolee \n \n @@ builtin/sparse-checkout.c: static void clean_tracked_sparse_directories(struct r\n \t * conflicted entries or submodules.\n \t */\n -\tif (!r->index->sparse_index) {\n -+\tif (r->index->sparse_index == COMPLETELY_FULL) {\n ++\tif (r->index->sparse_index == INDEX_EXPANDED) {\n \t\t/*\n \t\t * If something, such as a merge conflict or other concern,\n \t\t * prevents us from converting to a sparse index, then do\n @@ cache.h: struct untracked_cache;\n \n +enum sparse_index_mode {\n +\t/*\n -+\t * COMPLETELY_FULL: there are no sparse directories\n -+\t * in the index at all.\n ++\t * There are no sparse directories in the index at all.\n ++\t *\n ++\t * Repositories that don't use cone-mode sparse-checkout will\n ++\t * always have their indexes in this mode.\n +\t */\n -+\tCOMPLETELY_FULL = 0,\n ++\tINDEX_EXPANDED = 0,\n +\n +\t/*\n -+\t * COLLAPSED: the index has already been collapsed to sparse\n -+\t * directories whereever possible.\n ++\t * The index has already been collapsed to sparse directories\n ++\t * whereever possible.\n +\t */\n -+\tCOLLAPSED = 1,\n ++\tINDEX_COLLAPSED,\n +\n +\t/*\n -+\t * PARTIALLY_SPARSE: the sparse directories that exist are\n -+\t * outside the sparse-checkout boundary, but it is possible\n -+\t * that some file entries could collapse to sparse directory\n -+\t * entries.\n ++\t * The sparse directories that exist are outside the\n ++\t * sparse-checkout boundary, but it is possible that some file\n ++\t * entries could collapse to sparse directory entries.\n +\t */\n -+\tPARTIALLY_SPARSE = 2,\n ++\tINDEX_PARTIALLY_SPARSE,\n +};\n +\n struct index_state {\n @@ read-cache.c: static const char *alternate_index_output;\n {\n \tif (S_ISSPARSEDIR(ce->ce_mode))\n -\t\tistate->sparse_index = 1;\n -+\t\tistate->sparse_index = COLLAPSED;\n ++\t\tistate->sparse_index = INDEX_COLLAPSED;\n \n \tistate->cache[nr] = ce;\n \tadd_name_hash(istate, ce);\n @@ read-cache.c: static int read_index_extension(struct index_state *istate,\n \tcase CACHE_EXT_SPARSE_DIRECTORIES:\n \t\t/* no content, only an indicator */\n -\t\tistate->sparse_index = 1;\n -+\t\tistate->sparse_index = COLLAPSED;\n ++\t\tistate->sparse_index = INDEX_COLLAPSED;\n \t\tbreak;\n \tdefault:\n \t\tif (*ext < 'A' || 'Z' < *ext)\n @@ read-cache.c: static int do_write_locked_index(struct index_state *istate, struc\n {\n \tint ret;\n -\tint was_full = !istate->sparse_index;\n -+\tint was_full = istate->sparse_index == COMPLETELY_FULL;\n ++\tint was_full = istate->sparse_index == INDEX_EXPANDED;\n \n \tret = convert_to_sparse(istate, 0);\n \n @@ sparse-index.c: int convert_to_sparse(struct index_state *istate, int flags)\n \t * cannot be converted to sparse, do not convert.\n \t */\n -\tif (istate->sparse_index || !istate->cache_nr ||\n -+\tif (istate->sparse_index == COLLAPSED || !istate->cache_nr ||\n ++\tif (istate->sparse_index == INDEX_COLLAPSED || !istate->cache_nr ||\n \t !is_sparse_index_allowed(istate, flags))\n \t\treturn 0;\n \n @@ sparse-index.c: int convert_to_sparse(struct index_state *istate, int flags)\n \tFREE_AND_NULL(istate->fsmonitor_last_update);\n \n -\tistate->sparse_index = 1;\n -+\tistate->sparse_index = COLLAPSED;\n ++\tistate->sparse_index = INDEX_COLLAPSED;\n \ttrace2_region_leave(\"index\", \"convert_to_sparse\", istate->repo);\n \treturn 0;\n }\n -@@ sparse-index.c: void expand_to_pattern_list(struct index_state *istate,\n +@@ sparse-index.c: void expand_index(struct index_state *istate, struct pattern_list *pl)\n \t * If the index is already full, then keep it full. We will convert\n \t * it to a sparse index on write, if possible.\n \t */\n -\tif (!istate || !istate->sparse_index)\n -+\tif (!istate || istate->sparse_index == COMPLETELY_FULL)\n ++\tif (!istate || istate->sparse_index == INDEX_EXPANDED)\n \t\treturn;\n \n \t/*\n 5: c977001c033 ! 5: 9103584ed75 cache-tree: implement cache_tree_find_path()\n @@ Commit message\n path exists.\n \n The implementation is adapted from do_invalidate_path() which does a\n - similar search but also modifies the nodes it finds along the way.\n + similar search but also modifies the nodes it finds along the way. The\n + method could be implemented simply using tail-recursion, but this while\n + loop does the same thing.\n \n This new method is not currently used, but will be in an upcoming\n change.\n \n + Helped-by: Junio C Hamano \n Signed-off-by: Derrick Stolee \n \n ## cache-tree.c ##\n @@ cache-tree.c: struct cache_tree_sub *cache_tree_sub(struct cache_tree *it, const\n +{\n +\tconst char *slash;\n +\tint namelen;\n -+\tstruct cache_tree_sub *down;\n ++\tstruct cache_tree_sub it_sub = {\n ++\t\t.cache_tree = it,\n ++\t};\n ++\tstruct cache_tree_sub *down = &it_sub;\n +\n -+\tif (!it)\n -+\t\treturn NULL;\n -+\tslash = strchrnul(path, '/');\n -+\tnamelen = slash - path;\n -+\tit->entry_count = -1;\n -+\tif (!*slash) {\n -+\t\tint pos;\n -+\t\tpos = cache_tree_subtree_pos(it, path, namelen);\n -+\t\tif (0 <= pos)\n -+\t\t\treturn it->down[pos]->cache_tree;\n -+\t\treturn NULL;\n ++\twhile (down) {\n ++\t\tslash = strchrnul(path, '/');\n ++\t\tnamelen = slash - path;\n ++\t\tdown->cache_tree->entry_count = -1;\n ++\t\tif (!*slash) {\n ++\t\t\tint pos;\n ++\t\t\tpos = cache_tree_subtree_pos(down->cache_tree, path, namelen);\n ++\t\t\tif (0 <= pos)\n ++\t\t\t\treturn down->cache_tree->down[pos]->cache_tree;\n ++\t\t\treturn NULL;\n ++\t\t}\n ++\t\tdown = find_subtree(it, path, namelen, 0);\n ++\t\tpath = slash + 1;\n +\t}\n -+\tdown = find_subtree(it, path, namelen, 0);\n -+\tif (down)\n -+\t\treturn cache_tree_find_path(down->cache_tree, slash + 1);\n ++\n +\treturn NULL;\n +}\n +\n 6: e42463de0d2 = 6: 75ecb579a9f sparse-checkout: --no-sparse-index needs a full index\n 7: 346c56bf256 ! 7: 310e59d9f0e sparse-index: partially expand directories\n @@ sparse-index.c: static int add_path_to_index(const struct object_id *oid,\n -\tstrbuf_addstr(base, path);\n +\t\t/*\n +\t\t * Have we expanded to a point outside of the sparse-checkout?\n ++\t\t *\n ++\t\t * Artificially pad the path name with a slash \"/\" to\n ++\t\t * indicate it as a directory, and add an arbitrary file\n ++\t\t * name (\"-\") so we can consider base->buf as a file name\n ++\t\t * to match against the cone-mode patterns.\n ++\t\t *\n ++\t\t * If we compared just \"path\", then we would expand more\n ++\t\t * than we should. Since every file at root is always\n ++\t\t * included, we would expand every directory at root at\n ++\t\t * least one level deep instead of using sparse directory\n ++\t\t * entries.\n +\t\t */\n +\t\tstrbuf_addstr(base, path);\n +\t\tstrbuf_add(base, \"/-\", 2);\n @@ sparse-index.c: static int add_path_to_index(const struct object_id *oid,\n \n \tstrbuf_setlen(base, len);\n \treturn 0;\n -@@ sparse-index.c: void expand_to_pattern_list(struct index_state *istate,\n - \tint i;\n +@@ sparse-index.c: void expand_index(struct index_state *istate, struct pattern_list *pl)\n \tstruct index_state *full;\n \tstruct strbuf base = STRBUF_INIT;\n + \tconst char *tr_region;\n +\tstruct modify_index_context ctx;\n \n \t/*\n \t * If the index is already full, then keep it full. We will convert\n -@@ sparse-index.c: void expand_to_pattern_list(struct index_state *istate,\n +@@ sparse-index.c: void expand_index(struct index_state *istate, struct pattern_list *pl)\n \tfull->cache_nr = 0;\n \tALLOC_ARRAY(full->cache, full->cache_alloc);\n \n @@ sparse-index.c: void expand_to_pattern_list(struct index_state *istate,\n \tfor (i = 0; i < istate->cache_nr; i++) {\n \t\tstruct cache_entry *ce = istate->cache[i];\n \t\tstruct tree *tree;\n -@@ sparse-index.c: void expand_to_pattern_list(struct index_state *istate,\n +@@ sparse-index.c: void expand_index(struct index_state *istate, struct pattern_list *pl)\n \t\tstrbuf_add(&base, ce->name, strlen(ce->name));\n \n \t\tread_tree_at(istate->repo, tree, &base, &ps,\n 8: ed640e3645b ! 8: b3cbfd3f136 sparse-index: complete partial expansion\n @@ Commit message\n Signed-off-by: Derrick Stolee \n \n ## sparse-index.c ##\n -@@ sparse-index.c: void expand_to_pattern_list(struct index_state *istate,\n +@@ sparse-index.c: void expand_index(struct index_state *istate, struct pattern_list *pl)\n \t * continue. A NULL pattern set indicates a full expansion to a\n \t * full index.\n \t */\n @@ sparse-index.c: void expand_to_pattern_list(struct index_state *istate,\n +\t\t * need to expand to a full index since we cannot satisfy\n +\t\t * the current request as a sparse index.\n +\t\t */\n -+\t\tif (cache_tree_update(istate, WRITE_TREE_MISSING_OK))\n ++\t\tif (cache_tree_update(istate, 0))\n +\t\t\tpl = NULL;\n +\t}\n \n \tif (!istate->repo)\n \t\tistate->repo = the_repository;\n -@@ sparse-index.c: void expand_to_pattern_list(struct index_state *istate,\n +@@ sparse-index.c: void expand_index(struct index_state *istate, struct pattern_list *pl)\n \tfull = xcalloc(1, sizeof(struct index_state));\n \tmemcpy(full, istate, sizeof(struct index_state));\n \n @@ sparse-index.c: void expand_to_pattern_list(struct index_state *istate,\n +\t * are only modifying the list of sparse directories. This hinges\n +\t * on whether we have a non-NULL pattern list.\n +\t */\n -+\tfull->sparse_index = pl ? PARTIALLY_SPARSE : COMPLETELY_FULL;\n ++\tfull->sparse_index = pl ? INDEX_PARTIALLY_SPARSE : INDEX_EXPANDED;\n +\n \t/* then change the necessary things */\n -\tfull->sparse_index = 0;\n \tfull->cache_alloc = (3 * istate->cache_alloc) / 2;\n \tfull->cache_nr = 0;\n \tALLOC_ARRAY(full->cache, full->cache_alloc);\n -@@ sparse-index.c: void expand_to_pattern_list(struct index_state *istate,\n +@@ sparse-index.c: void expand_index(struct index_state *istate, struct pattern_list *pl)\n \t\tstruct cache_entry *ce = istate->cache[i];\n \t\tstruct tree *tree;\n \t\tstruct pathspec ps;\n @@ sparse-index.c: void expand_to_pattern_list(struct index_state *istate,\n \t\tif (!(ce->ce_flags & CE_SKIP_WORKTREE))\n \t\t\twarning(_(\"index entry is a directory, but not sparse (%08x)\"),\n \t\t\t\tce->ce_flags);\n -@@ sparse-index.c: void expand_to_pattern_list(struct index_state *istate,\n +@@ sparse-index.c: void expand_index(struct index_state *istate, struct pattern_list *pl)\n \t/* Copy back into original index. */\n \tmemcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));\n \tmemcpy(&istate->dir_hash, &full->dir_hash, sizeof(full->dir_hash));\n -\tistate->sparse_index = 0;\n -+\tistate->sparse_index = pl ? PARTIALLY_SPARSE : COMPLETELY_FULL;\n ++\tistate->sparse_index = pl ? INDEX_PARTIALLY_SPARSE : INDEX_EXPANDED;\n \tfree(istate->cache);\n \tistate->cache = full->cache;\n \tistate->cache_nr = full->cache_nr;\n -@@ sparse-index.c: void expand_to_pattern_list(struct index_state *istate,\n - \n - \t/* Clear and recompute the cache-tree */\n - \tcache_tree_free(&istate->cache_tree);\n --\tcache_tree_update(istate, 0);\n -+\tcache_tree_update(istate, WRITE_TREE_MISSING_OK);\n - \n - \ttrace2_region_leave(\"index\",\n - \t\t\t pl ? \"expand_to_pattern_list\" : \"ensure_full_index\",\n 9: 089ab086f58 = 9: aa3bdcf705c p2000: add test for 'git sparse-checkout [add|set]'\n 10: ad9ed6973d5 ! 10: 11728619120 sparse-checkout: integrate with sparse index\n @@ unpack-trees.c: enum update_sparsity_result update_sparsity(struct unpack_trees_\n \t}\n \n +\t/* Expand sparse directories as needed */\n -+\texpand_to_pattern_list(o->src_index, o->pl);\n ++\texpand_index(o->src_index, o->pl);\n +\n \t/* Set NEW_SKIP_WORKTREE on existing entries. */\n \tmark_all_ce_unused(o->src_index);\n\n-- \ngitgitgadget\n"},{"id":"455772","messageId":"f2960747ed868d57bc2eccfbe49d284f5268aba4.1653313726.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v3.git.1653313726.gitgitgadget@gmail.com","subject":"[PATCH v3 01/10] t1092: refactor 'sparse-index contents' test","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-23T13:48:37Z","receivedAt":"2022-05-23T13:49:04Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nBefore expanding this test with more involved cases, first extract the\nrepeated logic into a new test_sparse_checkout_set helper. This helper\nchecks that 'git sparse-checkout set ...' succeeds and then verifies\nthat certain directories have sparse directory entries in the sparse\nindex. It also verifies that the in-cone directories are _not_ sparse\ndirectory entries in the sparse index.\n\nSigned-off-by: Derrick Stolee \n---\n t/t1092-sparse-checkout-compatibility.sh | 53 ++++++++++++++++--------\n 1 file changed, 35 insertions(+), 18 deletions(-)\n\ndiff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\nindex 93bcfd20bbc..e7c0ae9b953 100755\n--- a/t/t1092-sparse-checkout-compatibility.sh\n+++ b/t/t1092-sparse-checkout-compatibility.sh\n@@ -205,36 +205,53 @@ test_sparse_unstaged () {\n \tdone\n }\n \n-test_expect_success 'sparse-index contents' '\n-\tinit_repos &&\n-\n+# Usage: test_sprase_checkout_set \" ... \" \" ... \"\n+# Verifies that \"git sparse-checkout set ... \" succeeds and\n+# leaves the sparse index in a state where ... are sparse\n+# directories (and ... are not).\n+test_sparse_checkout_set () {\n+\tCONE_DIRS=$1 &&\n+\tSPARSE_DIRS=$2 &&\n+\tgit -C sparse-index sparse-checkout set $CONE_DIRS &&\n \tgit -C sparse-index ls-files --sparse --stage >cache &&\n-\tfor dir in folder1 folder2 x\n+\n+\t# Check that the directories outside of the sparse-checkout cone\n+\t# have sparse directory entries.\n+\tfor dir in $SPARSE_DIRS\n \tdo\n \t\tTREE=$(git -C sparse-index rev-parse HEAD:$dir) &&\n \t\tgrep \"040000 $TREE 0\t$dir/\" cache \\\n \t\t\t|| return 1\n \tdone &&\n \n-\tgit -C sparse-index sparse-checkout set folder1 &&\n-\n-\tgit -C sparse-index ls-files --sparse --stage >cache &&\n-\tfor dir in deep folder2 x\n+\t# Check that the directories in the sparse-checkout cone\n+\t# are not sparse directory entries.\n+\tfor dir in $CONE_DIRS\n \tdo\n \t\tTREE=$(git -C sparse-index rev-parse HEAD:$dir) &&\n-\t\tgrep \"040000 $TREE 0\t$dir/\" cache \\\n+\t\t! grep \"040000 $TREE 0\t$dir/\" cache \\\n \t\t\t|| return 1\n-\tdone &&\n+\tdone\n+}\n \n-\tgit -C sparse-index sparse-checkout set deep/deeper1 &&\n+test_expect_success 'sparse-index contents' '\n+\tinit_repos &&\n \n-\tgit -C sparse-index ls-files --sparse --stage >cache &&\n-\tfor dir in deep/deeper2 folder1 folder2 x\n-\tdo\n-\t\tTREE=$(git -C sparse-index rev-parse HEAD:$dir) &&\n-\t\tgrep \"040000 $TREE 0\t$dir/\" cache \\\n-\t\t\t|| return 1\n-\tdone &&\n+\t# Remove deep, add three other directories.\n+\ttest_sparse_checkout_set \\\n+\t\t\"folder1 folder2 x\" \\\n+\t\t\"before deep\" &&\n+\n+\t# Remove folder1, add deep\n+\ttest_sparse_checkout_set \\\n+\t\t\"deep folder2 x\" \\\n+\t\t\"before folder1\" &&\n+\n+\t# Replace deep with deep/deeper2 (dropping deep/deeper1)\n+\t# Add folder1\n+\ttest_sparse_checkout_set \\\n+\t\t\"deep/deeper2 folder1 folder2 x\" \\\n+\t\t\"before deep/deeper1\" &&\n \n \t# Disabling the sparse-index replaces tree entries with full ones\n \tgit -C sparse-index sparse-checkout init --no-sparse-index &&\n-- \ngitgitgadget\n\n"},{"id":"455773","messageId":"8a459d6c67d2cd2cb6f5e6a7d2ea1bff29adb883.1653313726.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v3.git.1653313726.gitgitgadget@gmail.com","subject":"[PATCH v3 04/10] sparse-index: introduce partially-sparse indexes","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-23T13:48:40Z","receivedAt":"2022-05-23T13:49:06Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nA future change will present a temporary, in-memory mode where the index\ncan both contain sparse directory entries but also not be completely\ncollapsed to the smallest possible sparse directories. This will be\nnecessary for modifying the sparse-checkout definition while using a\nsparse index.\n\nFor now, convert the single-bit member 'sparse_index' in 'struct\nindex_state' to be a an 'enum sparse_index_mode' with three modes:\n\n* INDEX_EXPANDED (0): No sparse directories exist. This is always the\n case for repositories that do not use cone-mode sparse-checkout.\n\n* INDEX_COLLAPSED: Sparse directories may exist. Files outside the\n sparse-checkout cone are reduced to sparse directory entries whenever\n possible.\n\n* INDEX_PARTIALLY_SPARSE: Sparse directories may exist. Some file\n entries outside the sparse-checkout cone may exist. Running\n convert_to_sparse() may further reduce those files to sparse directory\n entries.\n\nThe main reason to store this extra information is to allow\nconvert_to_sparse() to short-circuit when the index is already in\nINDEX_EXPANDED mode but to actually do the necessary work when in\nINDEX_PARTIALLY_SPARSE mode.\n\nThe INDEX_PARTIALLY_SPARSE mode will be used in an upcoming change.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/sparse-checkout.c | 2 +-\n cache.h | 33 +++++++++++++++++++++++++--------\n read-cache.c | 6 +++---\n sparse-index.c | 6 +++---\n 4 files changed, 32 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\nindex 0217d44c5b1..5b054400bf3 100644\n--- a/builtin/sparse-checkout.c\n+++ b/builtin/sparse-checkout.c\n@@ -128,7 +128,7 @@ static void clean_tracked_sparse_directories(struct repository *r)\n \t * sparse index will not delete directories that contain\n \t * conflicted entries or submodules.\n \t */\n-\tif (!r->index->sparse_index) {\n+\tif (r->index->sparse_index == INDEX_EXPANDED) {\n \t\t/*\n \t\t * If something, such as a merge conflict or other concern,\n \t\t * prevents us from converting to a sparse index, then do\ndiff --git a/cache.h b/cache.h\nindex 6226f6a8a53..e171ce882a2 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -310,6 +310,29 @@ struct untracked_cache;\n struct progress;\n struct pattern_list;\n \n+enum sparse_index_mode {\n+\t/*\n+\t * There are no sparse directories in the index at all.\n+\t *\n+\t * Repositories that don't use cone-mode sparse-checkout will\n+\t * always have their indexes in this mode.\n+\t */\n+\tINDEX_EXPANDED = 0,\n+\n+\t/*\n+\t * The index has already been collapsed to sparse directories\n+\t * whereever possible.\n+\t */\n+\tINDEX_COLLAPSED,\n+\n+\t/*\n+\t * The sparse directories that exist are outside the\n+\t * sparse-checkout boundary, but it is possible that some file\n+\t * entries could collapse to sparse directory entries.\n+\t */\n+\tINDEX_PARTIALLY_SPARSE,\n+};\n+\n struct index_state {\n \tstruct cache_entry **cache;\n \tunsigned int version;\n@@ -323,14 +346,8 @@ struct index_state {\n \t\t drop_cache_tree : 1,\n \t\t updated_workdir : 1,\n \t\t updated_skipworktree : 1,\n-\t\t fsmonitor_has_run_once : 1,\n-\n-\t\t /*\n-\t\t * sparse_index == 1 when sparse-directory\n-\t\t * entries exist. Requires sparse-checkout\n-\t\t * in cone mode.\n-\t\t */\n-\t\t sparse_index : 1;\n+\t\t fsmonitor_has_run_once : 1;\n+\tenum sparse_index_mode sparse_index;\n \tstruct hashmap name_hash;\n \tstruct hashmap dir_hash;\n \tstruct object_id oid;\ndiff --git a/read-cache.c b/read-cache.c\nindex 4df97e185e9..b236042eee1 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -112,7 +112,7 @@ static const char *alternate_index_output;\n static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)\n {\n \tif (S_ISSPARSEDIR(ce->ce_mode))\n-\t\tistate->sparse_index = 1;\n+\t\tistate->sparse_index = INDEX_COLLAPSED;\n \n \tistate->cache[nr] = ce;\n \tadd_name_hash(istate, ce);\n@@ -1856,7 +1856,7 @@ static int read_index_extension(struct index_state *istate,\n \t\tbreak;\n \tcase CACHE_EXT_SPARSE_DIRECTORIES:\n \t\t/* no content, only an indicator */\n-\t\tistate->sparse_index = 1;\n+\t\tistate->sparse_index = INDEX_COLLAPSED;\n \t\tbreak;\n \tdefault:\n \t\tif (*ext < 'A' || 'Z' < *ext)\n@@ -3149,7 +3149,7 @@ static int do_write_locked_index(struct index_state *istate, struct lock_file *l\n \t\t\t\t unsigned flags)\n {\n \tint ret;\n-\tint was_full = !istate->sparse_index;\n+\tint was_full = istate->sparse_index == INDEX_EXPANDED;\n \n \tret = convert_to_sparse(istate, 0);\n \ndiff --git a/sparse-index.c b/sparse-index.c\nindex a11b5cf1314..7848910c154 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -173,7 +173,7 @@ int convert_to_sparse(struct index_state *istate, int flags)\n \t * If the index is already sparse, empty, or otherwise\n \t * cannot be converted to sparse, do not convert.\n \t */\n-\tif (istate->sparse_index || !istate->cache_nr ||\n+\tif (istate->sparse_index == INDEX_COLLAPSED || !istate->cache_nr ||\n \t !is_sparse_index_allowed(istate, flags))\n \t\treturn 0;\n \n@@ -214,7 +214,7 @@ int convert_to_sparse(struct index_state *istate, int flags)\n \tFREE_AND_NULL(istate->fsmonitor_dirty);\n \tFREE_AND_NULL(istate->fsmonitor_last_update);\n \n-\tistate->sparse_index = 1;\n+\tistate->sparse_index = INDEX_COLLAPSED;\n \ttrace2_region_leave(\"index\", \"convert_to_sparse\", istate->repo);\n \treturn 0;\n }\n@@ -259,7 +259,7 @@ void expand_index(struct index_state *istate, struct pattern_list *pl)\n \t * If the index is already full, then keep it full. We will convert\n \t * it to a sparse index on write, if possible.\n \t */\n-\tif (!istate || !istate->sparse_index)\n+\tif (!istate || istate->sparse_index == INDEX_EXPANDED)\n \t\treturn;\n \n \t/*\n-- \ngitgitgadget\n\n"},{"id":"455774","messageId":"44b0549a2882df07a5b7c96a637c8f0d2e0d9798.1653313726.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v3.git.1653313726.gitgitgadget@gmail.com","subject":"[PATCH v3 03/10] sparse-index: create expand_index()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-23T13:48:39Z","receivedAt":"2022-05-23T13:49:08Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThis is the first change in a series to allow modifying the\nsparse-checkout pattern set without expanding a sparse index to a full\none in the process. Here, we focus on the problem of expanding the\npattern set through a command like 'git sparse-checkout add '\nwhich needs to create new index entries for the paths now being written\nto the worktree.\n\nTo achieve this, we need to be able to replace sparse directory entries\nwith their contained files and subdirectories. Once this is complete,\nother code paths can discover those cache entries and write the\ncorresponding files to disk before committing the index.\n\nWe already have logic in ensure_full_index() that expands the index\nentries, so we will use that as our base. Create a new method,\nexpand_index(), which takes a pattern list, but for now mostly ignores\nit. The current implementation is only correct when the pattern list is\nNULL as that does the same as ensure_full_index(). In fact,\nensure_full_index() is converted to a shim over expand_index().\n\nA future update will actually implement expand_index() to its full\ncapabilities. For now, it is created and documented.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 32 +++++++++++++++++++++++++++++---\n sparse-index.h | 13 +++++++++++++\n 2 files changed, 42 insertions(+), 3 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex 8636af72de5..a11b5cf1314 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -248,19 +248,40 @@ static int add_path_to_index(const struct object_id *oid,\n \treturn 0;\n }\n \n-void ensure_full_index(struct index_state *istate)\n+void expand_index(struct index_state *istate, struct pattern_list *pl)\n {\n \tint i;\n \tstruct index_state *full;\n \tstruct strbuf base = STRBUF_INIT;\n+\tconst char *tr_region;\n \n+\t/*\n+\t * If the index is already full, then keep it full. We will convert\n+\t * it to a sparse index on write, if possible.\n+\t */\n \tif (!istate || !istate->sparse_index)\n \t\treturn;\n \n+\t/*\n+\t * If our index is sparse, but our new pattern set does not use\n+\t * cone mode patterns, then we need to expand the index before we\n+\t * continue. A NULL pattern set indicates a full expansion to a\n+\t * full index.\n+\t */\n+\tif (pl && !pl->use_cone_patterns)\n+\t\tpl = NULL;\n+\n \tif (!istate->repo)\n \t\tistate->repo = the_repository;\n \n-\ttrace2_region_enter(\"index\", \"ensure_full_index\", istate->repo);\n+\t/*\n+\t * A NULL pattern set indicates we are expanding a full index, so\n+\t * we use a special region name that indicates the full expansion.\n+\t * This is used by test cases, but also helps to differentiate the\n+\t * two cases.\n+\t */\n+\ttr_region = pl ? \"expand_index\" : \"ensure_full_index\";\n+\ttrace2_region_enter(\"index\", tr_region, istate->repo);\n \n \t/* initialize basics of new index */\n \tfull = xcalloc(1, sizeof(struct index_state));\n@@ -322,7 +343,12 @@ void ensure_full_index(struct index_state *istate)\n \tcache_tree_free(&istate->cache_tree);\n \tcache_tree_update(istate, 0);\n \n-\ttrace2_region_leave(\"index\", \"ensure_full_index\", istate->repo);\n+\ttrace2_region_leave(\"index\", tr_region, istate->repo);\n+}\n+\n+void ensure_full_index(struct index_state *istate)\n+{\n+\texpand_index(istate, NULL);\n }\n \n void ensure_correct_sparsity(struct index_state *istate)\ndiff --git a/sparse-index.h b/sparse-index.h\nindex 633d4fb7e31..b1f2cdbb164 100644\n--- a/sparse-index.h\n+++ b/sparse-index.h\n@@ -23,4 +23,17 @@ void expand_to_path(struct index_state *istate,\n struct repository;\n int set_sparse_index_config(struct repository *repo, int enable);\n \n+struct pattern_list;\n+\n+/**\n+ * Scan the given index and compare its entries to the given pattern list.\n+ * If the index is sparse and the pattern list uses cone mode patterns,\n+ * then modify the index to contain the all of the file entries within that\n+ * new pattern list. This expands sparse directories only as far as needed.\n+ *\n+ * If the pattern list is NULL or does not use cone mode patterns, then the\n+ * index is expanded to a full index.\n+ */\n+void expand_index(struct index_state *istate, struct pattern_list *pl);\n+\n #endif\n-- \ngitgitgadget\n\n"},{"id":"455775","messageId":"5030eeecf4f8e2dd65bc055d6a720c7d67015b1e.1653313726.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v3.git.1653313726.gitgitgadget@gmail.com","subject":"[PATCH v3 02/10] t1092: stress test 'git sparse-checkout set'","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-23T13:48:38Z","receivedAt":"2022-05-23T13:49:11Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe 'sparse-index contents' test checks that the sparse index has the\ncorrect set of sparse directories in the index after modifying the cone\nmode patterns using 'git sparse-checkout set'. Add to the coverage here\nby adding more complicated scenarios that were not previously tested.\n\nIn order to check paths that do not exist at HEAD, we need to modify the\ntest_sparse_checkout_set helper slightly:\n\n1. Add the --skip-checks argument to the 'set' command to avoid failures\n when passing paths that do not exist at HEAD.\n\n2. When looking for the non-existence of sparse directories for the\n paths in $CONE_DIRS, allow the rev-list command to fail because the\n path does not exist at HEAD.\n\nThis allows us to add some interesting test cases.\n\nHelped-by: Victoria Dye \nSigned-off-by: Derrick Stolee \n---\n t/t1092-sparse-checkout-compatibility.sh | 19 +++++++++++++++++--\n 1 file changed, 17 insertions(+), 2 deletions(-)\n\ndiff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\nindex e7c0ae9b953..785820f9fd5 100755\n--- a/t/t1092-sparse-checkout-compatibility.sh\n+++ b/t/t1092-sparse-checkout-compatibility.sh\n@@ -212,7 +212,7 @@ test_sparse_unstaged () {\n test_sparse_checkout_set () {\n \tCONE_DIRS=$1 &&\n \tSPARSE_DIRS=$2 &&\n-\tgit -C sparse-index sparse-checkout set $CONE_DIRS &&\n+\tgit -C sparse-index sparse-checkout set --skip-checks $CONE_DIRS &&\n \tgit -C sparse-index ls-files --sparse --stage >cache &&\n \n \t# Check that the directories outside of the sparse-checkout cone\n@@ -228,7 +228,9 @@ test_sparse_checkout_set () {\n \t# are not sparse directory entries.\n \tfor dir in $CONE_DIRS\n \tdo\n-\t\tTREE=$(git -C sparse-index rev-parse HEAD:$dir) &&\n+\t\t# Allow TREE to not exist because\n+\t\t# $dir does not exist at HEAD.\n+\t\tTREE=$(git -C sparse-index rev-parse HEAD:$dir) ||\n \t\t! grep \"040000 $TREE 0\t$dir/\" cache \\\n \t\t\t|| return 1\n \tdone\n@@ -253,6 +255,19 @@ test_expect_success 'sparse-index contents' '\n \t\t\"deep/deeper2 folder1 folder2 x\" \\\n \t\t\"before deep/deeper1\" &&\n \n+\t# Replace deep/deeper2 with deep/deeper1\n+\t# Replace folder1 with folder1/0/0\n+\t# Replace folder2 with non-existent folder2/2/3\n+\t# Add non-existent \"bogus\"\n+\ttest_sparse_checkout_set \\\n+\t\t\"bogus deep/deeper1 folder1/0/0 folder2/2/3 x\" \\\n+\t\t\"before deep/deeper2 folder2/0\" &&\n+\n+\t# Drop down to only files at root\n+\ttest_sparse_checkout_set \\\n+\t\t\"\" \\\n+\t\t\"before deep folder1 folder2 x\" &&\n+\n \t# Disabling the sparse-index replaces tree entries with full ones\n \tgit -C sparse-index sparse-checkout init --no-sparse-index &&\n \ttest_sparse_match git ls-files --stage --sparse\n-- \ngitgitgadget\n\n"},{"id":"455776","messageId":"9103584ed75cdc3bb3c2afd87df53161e0eef9b1.1653313727.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v3.git.1653313726.gitgitgadget@gmail.com","subject":"[PATCH v3 05/10] cache-tree: implement cache_tree_find_path()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-23T13:48:41Z","receivedAt":"2022-05-23T13:49:14Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nGiven a 'struct cache_tree', it may be beneficial to navigate directly\nto a node within that corresponds to a given path name. Create\ncache_tree_find_path() for this function. It returns NULL when no such\npath exists.\n\nThe implementation is adapted from do_invalidate_path() which does a\nsimilar search but also modifies the nodes it finds along the way. The\nmethod could be implemented simply using tail-recursion, but this while\nloop does the same thing.\n\nThis new method is not currently used, but will be in an upcoming\nchange.\n\nHelped-by: Junio C Hamano \nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 27 +++++++++++++++++++++++++++\n cache-tree.h | 2 ++\n 2 files changed, 29 insertions(+)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 6752f69d515..f42db920d10 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -100,6 +100,33 @@ struct cache_tree_sub *cache_tree_sub(struct cache_tree *it, const char *path)\n \treturn find_subtree(it, path, pathlen, 1);\n }\n \n+struct cache_tree *cache_tree_find_path(struct cache_tree *it, const char *path)\n+{\n+\tconst char *slash;\n+\tint namelen;\n+\tstruct cache_tree_sub it_sub = {\n+\t\t.cache_tree = it,\n+\t};\n+\tstruct cache_tree_sub *down = &it_sub;\n+\n+\twhile (down) {\n+\t\tslash = strchrnul(path, '/');\n+\t\tnamelen = slash - path;\n+\t\tdown->cache_tree->entry_count = -1;\n+\t\tif (!*slash) {\n+\t\t\tint pos;\n+\t\t\tpos = cache_tree_subtree_pos(down->cache_tree, path, namelen);\n+\t\t\tif (0 <= pos)\n+\t\t\t\treturn down->cache_tree->down[pos]->cache_tree;\n+\t\t\treturn NULL;\n+\t\t}\n+\t\tdown = find_subtree(it, path, namelen, 0);\n+\t\tpath = slash + 1;\n+\t}\n+\n+\treturn NULL;\n+}\n+\n static int do_invalidate_path(struct cache_tree *it, const char *path)\n {\n \t/* a/b/c\ndiff --git a/cache-tree.h b/cache-tree.h\nindex 8efeccebfc9..f75f8e74dcd 100644\n--- a/cache-tree.h\n+++ b/cache-tree.h\n@@ -29,6 +29,8 @@ struct cache_tree_sub *cache_tree_sub(struct cache_tree *, const char *);\n \n int cache_tree_subtree_pos(struct cache_tree *it, const char *path, int pathlen);\n \n+struct cache_tree *cache_tree_find_path(struct cache_tree *it, const char *path);\n+\n void cache_tree_write(struct strbuf *, struct cache_tree *root);\n struct cache_tree *cache_tree_read(const char *buffer, unsigned long size);\n \n-- \ngitgitgadget\n\n"},{"id":"455777","messageId":"310e59d9f0e9cf6b88ced10c80e982606fe7632a.1653313727.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v3.git.1653313726.gitgitgadget@gmail.com","subject":"[PATCH v3 07/10] sparse-index: partially expand directories","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-23T13:48:43Z","receivedAt":"2022-05-23T13:49:16Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe expand_to_pattern_list() method expands sparse directory entries\nto their list of contained files when either the pattern list is NULL or\nthe directory is contained in the new pattern list's cone mode patterns.\n\nIt is possible that the pattern list has a recursive match with a\ndirectory 'A/B/C/' and so an existing sparse directory 'A/B/' would need\nto be expanded. If there exists a directory 'A/B/D/', then that\ndirectory should not be expanded and instead we can create a sparse\ndirectory.\n\nTo implement this, we plug into the add_path_to_index() callback for the\ncall to read_tree_at(). Since we now need access to both the index we\nare writing and the pattern list we are comparing, create a 'struct\nmodify_index_context' to use as a data transfer object. It is important\nthat we use the given pattern list since we will use this pattern list\nto change the sparse-checkout patterns and cannot use\nistate->sparse_checkout_patterns.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 57 +++++++++++++++++++++++++++++++++++++++++++-------\n 1 file changed, 50 insertions(+), 7 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex 7848910c154..a881f851810 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -9,6 +9,11 @@\n #include \"dir.h\"\n #include \"fsmonitor.h\"\n \n+struct modify_index_context {\n+\tstruct index_state *write;\n+\tstruct pattern_list *pl;\n+};\n+\n static struct cache_entry *construct_sparse_dir_entry(\n \t\t\t\tstruct index_state *istate,\n \t\t\t\tconst char *sparse_dir,\n@@ -231,18 +236,52 @@ static int add_path_to_index(const struct object_id *oid,\n \t\t\t struct strbuf *base, const char *path,\n \t\t\t unsigned int mode, void *context)\n {\n-\tstruct index_state *istate = (struct index_state *)context;\n+\tstruct modify_index_context *ctx = (struct modify_index_context *)context;\n \tstruct cache_entry *ce;\n \tsize_t len = base->len;\n \n-\tif (S_ISDIR(mode))\n-\t\treturn READ_TREE_RECURSIVE;\n+\tif (S_ISDIR(mode)) {\n+\t\tint dtype;\n+\t\tsize_t baselen = base->len;\n+\t\tif (!ctx->pl)\n+\t\t\treturn READ_TREE_RECURSIVE;\n \n-\tstrbuf_addstr(base, path);\n+\t\t/*\n+\t\t * Have we expanded to a point outside of the sparse-checkout?\n+\t\t *\n+\t\t * Artificially pad the path name with a slash \"/\" to\n+\t\t * indicate it as a directory, and add an arbitrary file\n+\t\t * name (\"-\") so we can consider base->buf as a file name\n+\t\t * to match against the cone-mode patterns.\n+\t\t *\n+\t\t * If we compared just \"path\", then we would expand more\n+\t\t * than we should. Since every file at root is always\n+\t\t * included, we would expand every directory at root at\n+\t\t * least one level deep instead of using sparse directory\n+\t\t * entries.\n+\t\t */\n+\t\tstrbuf_addstr(base, path);\n+\t\tstrbuf_add(base, \"/-\", 2);\n+\n+\t\tif (path_matches_pattern_list(base->buf, base->len,\n+\t\t\t\t\t NULL, &dtype,\n+\t\t\t\t\t ctx->pl, ctx->write)) {\n+\t\t\tstrbuf_setlen(base, baselen);\n+\t\t\treturn READ_TREE_RECURSIVE;\n+\t\t}\n \n-\tce = make_cache_entry(istate, mode, oid, base->buf, 0, 0);\n+\t\t/*\n+\t\t * The path \"{base}{path}/\" is a sparse directory. Create the correct\n+\t\t * name for inserting the entry into the index.\n+\t\t */\n+\t\tstrbuf_setlen(base, base->len - 1);\n+\t} else {\n+\t\tstrbuf_addstr(base, path);\n+\t}\n+\n+\tce = make_cache_entry(ctx->write, mode, oid, base->buf, 0, 0);\n \tce->ce_flags |= CE_SKIP_WORKTREE | CE_EXTENDED;\n-\tset_index_entry(istate, istate->cache_nr++, ce);\n+\tset_index_entry(ctx->write, ctx->write->cache_nr++, ce);\n \n \tstrbuf_setlen(base, len);\n \treturn 0;\n@@ -254,6 +293,7 @@ void expand_index(struct index_state *istate, struct pattern_list *pl)\n \tstruct index_state *full;\n \tstruct strbuf base = STRBUF_INIT;\n \tconst char *tr_region;\n+\tstruct modify_index_context ctx;\n \n \t/*\n \t * If the index is already full, then keep it full. We will convert\n@@ -293,6 +333,9 @@ void expand_index(struct index_state *istate, struct pattern_list *pl)\n \tfull->cache_nr = 0;\n \tALLOC_ARRAY(full->cache, full->cache_alloc);\n \n+\tctx.write = full;\n+\tctx.pl = pl;\n+\n \tfor (i = 0; i < istate->cache_nr; i++) {\n \t\tstruct cache_entry *ce = istate->cache[i];\n \t\tstruct tree *tree;\n@@ -318,7 +361,7 @@ void expand_index(struct index_state *istate, struct pattern_list *pl)\n \t\tstrbuf_add(&base, ce->name, strlen(ce->name));\n \n \t\tread_tree_at(istate->repo, tree, &base, &ps,\n-\t\t\t add_path_to_index, full);\n+\t\t\t add_path_to_index, &ctx);\n \n \t\t/* free directory entries. full entries are re-used */\n \t\tdiscard_cache_entry(ce);\n-- \ngitgitgadget\n\n"},{"id":"455778","messageId":"75ecb579a9f69c6dbe5d88ecec0d8e7e15c02efb.1653313727.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v3.git.1653313726.gitgitgadget@gmail.com","subject":"[PATCH v3 06/10] sparse-checkout: --no-sparse-index needs a full index","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-23T13:48:42Z","receivedAt":"2022-05-23T13:49:18Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nWhen the --no-sparse-index option is supplied, the sparse-checkout\nbuiltin should explicitly ask to expand a sparse index to a full one.\nThis is currently done implicitly due to the command_requires_full_index\nprotection, but that will be removed in an upcoming change.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/sparse-checkout.c | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\nindex 5b054400bf3..1db51c3fd72 100644\n--- a/builtin/sparse-checkout.c\n+++ b/builtin/sparse-checkout.c\n@@ -413,6 +413,9 @@ static int update_modes(int *cone_mode, int *sparse_index)\n \t\t/* force an index rewrite */\n \t\trepo_read_index(the_repository);\n \t\tthe_repository->index->updated_workdir = 1;\n+\n+\t\tif (!*sparse_index)\n+\t\t\tensure_full_index(the_repository->index);\n \t}\n \n \treturn 0;\n-- \ngitgitgadget\n\n"},{"id":"455779","messageId":"aa3bdcf705cc67565966076b09afa8219549771a.1653313727.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v3.git.1653313726.gitgitgadget@gmail.com","subject":"[PATCH v3 09/10] p2000: add test for 'git sparse-checkout [add|set]'","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-23T13:48:45Z","receivedAt":"2022-05-23T13:49:22Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe sparse-checkout builtin is almost completely integrated with the\nsparse index, allowing the sparse-checkout boundary to be modified\nwithout expanding a sparse index to a full one. Add a test to\np2000-sparse-operations.sh that adds a directory to the sparse-checkout\ndefinition, then removes it. Using both operations is important to\nensure that the operation is doing the same work in each repetition as\nwell as leaving the test repo in a good state for later tests.\n\nSigned-off-by: Derrick Stolee \n---\n t/perf/p2000-sparse-operations.sh | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/t/perf/p2000-sparse-operations.sh b/t/perf/p2000-sparse-operations.sh\nindex 382716cfca9..ce5cfac5714 100755\n--- a/t/perf/p2000-sparse-operations.sh\n+++ b/t/perf/p2000-sparse-operations.sh\n@@ -110,6 +110,7 @@ test_perf_on_all git add -A\n test_perf_on_all git add .\n test_perf_on_all git commit -a -m A\n test_perf_on_all git checkout -f -\n+test_perf_on_all \"git sparse-checkout add f2/f3/f1 && git sparse-checkout set $SPARSE_CONE\"\n test_perf_on_all git reset\n test_perf_on_all git reset --hard\n test_perf_on_all git reset -- does-not-exist\n-- \ngitgitgadget\n\n"},{"id":"455780","messageId":"b3cbfd3f136fffcf83c9bdf9b43fa8e4929c1052.1653313727.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v3.git.1653313726.gitgitgadget@gmail.com","subject":"[PATCH v3 08/10] sparse-index: complete partial expansion","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-23T13:48:44Z","receivedAt":"2022-05-23T13:49:23Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nTo complete the implementation of expand_to_pattern_list(), we need to\ndetect when a sparse directory entry should remain sparse. This avoids a\nfull expansion, so we now need to use the PARTIALLY_SPARSE mode to\nindicate this state.\n\nThere still are no callers to this method, but we will add one in the\nnext change.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 39 ++++++++++++++++++++++++++++++++++++---\n 1 file changed, 36 insertions(+), 3 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex a881f851810..2c0a18380f1 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -308,8 +308,24 @@ void expand_index(struct index_state *istate, struct pattern_list *pl)\n \t * continue. A NULL pattern set indicates a full expansion to a\n \t * full index.\n \t */\n-\tif (pl && !pl->use_cone_patterns)\n+\tif (pl && !pl->use_cone_patterns) {\n \t\tpl = NULL;\n+\t} else {\n+\t\t/*\n+\t\t * We might contract file entries into sparse-directory\n+\t\t * entries, and for that we will need the cache tree to\n+\t\t * be recomputed.\n+\t\t */\n+\t\tcache_tree_free(&istate->cache_tree);\n+\n+\t\t/*\n+\t\t * If there is a problem creating the cache tree, then we\n+\t\t * need to expand to a full index since we cannot satisfy\n+\t\t * the current request as a sparse index.\n+\t\t */\n+\t\tif (cache_tree_update(istate, 0))\n+\t\t\tpl = NULL;\n+\t}\n \n \tif (!istate->repo)\n \t\tistate->repo = the_repository;\n@@ -327,8 +343,14 @@ void expand_index(struct index_state *istate, struct pattern_list *pl)\n \tfull = xcalloc(1, sizeof(struct index_state));\n \tmemcpy(full, istate, sizeof(struct index_state));\n \n+\t/*\n+\t * This slightly-misnamed 'full' index might still be sparse if we\n+\t * are only modifying the list of sparse directories. This hinges\n+\t * on whether we have a non-NULL pattern list.\n+\t */\n+\tfull->sparse_index = pl ? INDEX_PARTIALLY_SPARSE : INDEX_EXPANDED;\n+\n \t/* then change the necessary things */\n-\tfull->sparse_index = 0;\n \tfull->cache_alloc = (3 * istate->cache_alloc) / 2;\n \tfull->cache_nr = 0;\n \tALLOC_ARRAY(full->cache, full->cache_alloc);\n@@ -340,11 +362,22 @@ void expand_index(struct index_state *istate, struct pattern_list *pl)\n \t\tstruct cache_entry *ce = istate->cache[i];\n \t\tstruct tree *tree;\n \t\tstruct pathspec ps;\n+\t\tint dtype;\n \n \t\tif (!S_ISSPARSEDIR(ce->ce_mode)) {\n \t\t\tset_index_entry(full, full->cache_nr++, ce);\n \t\t\tcontinue;\n \t\t}\n+\n+\t\t/* We now have a sparse directory entry. Should we expand? */\n+\t\tif (pl &&\n+\t\t path_matches_pattern_list(ce->name, ce->ce_namelen,\n+\t\t\t\t\t NULL, &dtype,\n+\t\t\t\t\t pl, istate) == NOT_MATCHED) {\n+\t\t\tset_index_entry(full, full->cache_nr++, ce);\n+\t\t\tcontinue;\n+\t\t}\n+\n \t\tif (!(ce->ce_flags & CE_SKIP_WORKTREE))\n \t\t\twarning(_(\"index entry is a directory, but not sparse (%08x)\"),\n \t\t\t\tce->ce_flags);\n@@ -370,7 +403,7 @@ void expand_index(struct index_state *istate, struct pattern_list *pl)\n \t/* Copy back into original index. */\n \tmemcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));\n \tmemcpy(&istate->dir_hash, &full->dir_hash, sizeof(full->dir_hash));\n-\tistate->sparse_index = 0;\n+\tistate->sparse_index = pl ? INDEX_PARTIALLY_SPARSE : INDEX_EXPANDED;\n \tfree(istate->cache);\n \tistate->cache = full->cache;\n \tistate->cache_nr = full->cache_nr;\n-- \ngitgitgadget\n\n"},{"id":"455781","messageId":"11728619120a2d616daab57c57c66e47052f5c89.1653313727.git.gitgitgadget@gmail.com","threadId":"57888","inReplyTo":"pull.1208.v3.git.1653313726.gitgitgadget@gmail.com","subject":"[PATCH v3 10/10] sparse-checkout: integrate with sparse index","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-05-23T13:48:46Z","receivedAt":"2022-05-23T13:49:27Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nWhen modifying the sparse-checkout definition, the sparse-checkout\nbuiltin calls update_sparsity() to modify the SKIP_WORKTREE bits of all\ncache entries in the index. Before, we needed the index to be fully\nexpanded in order to ensure we had the full list of files necessary that\nmatch the new patterns.\n\nInsert a call to reset_sparse_directories() that expands sparse\ndirectories that are within the new pattern list, but only far enough\nthat every necessary file path now exists as a cache entry. The\nremaining logic within update_sparsity() will modify the SKIP_WORKTREE\nbits appropriately.\n\nThis allows us to disable command_requires_full_index within the\nsparse-checkout builtin. Add tests that demonstrate that we are not\nexpanding to a full index unnecessarily.\n\nWe can see the improved performance in the p2000 test script:\n\nTest HEAD~1 HEAD\n------------------------------------------------------------------------\n2000.24: git ... (sparse-v3) 2.14(1.55+0.58) 1.57(1.03+0.53) -26.6%\n2000.25: git ... (sparse-v4) 2.20(1.62+0.57) 1.58(0.98+0.59) -28.2%\n\nThese reductions of 26-28% are small compared to most examples, but the\ntime is dominated by writing a new copy of the base repository to the\nworktree and then deleting it again. The fact that the previous index\nexpansion was such a large portion of the time is telling how important\nit is to complete this sparse index integration.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/sparse-checkout.c | 3 +++\n t/t1092-sparse-checkout-compatibility.sh | 25 ++++++++++++++++++++++++\n unpack-trees.c | 4 ++++\n 3 files changed, 32 insertions(+)\n\ndiff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\nindex 1db51c3fd72..67d1d146de5 100644\n--- a/builtin/sparse-checkout.c\n+++ b/builtin/sparse-checkout.c\n@@ -937,6 +937,9 @@ int cmd_sparse_checkout(int argc, const char **argv, const char *prefix)\n \n \tgit_config(git_default_config, NULL);\n \n+\tprepare_repo_settings(the_repository);\n+\tthe_repository->settings.command_requires_full_index = 0;\n+\n \tif (argc > 0) {\n \t\tif (!strcmp(argv[0], \"list\"))\n \t\t\treturn sparse_checkout_list(argc, argv);\ndiff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\nindex 785820f9fd5..73f4cf47314 100755\n--- a/t/t1092-sparse-checkout-compatibility.sh\n+++ b/t/t1092-sparse-checkout-compatibility.sh\n@@ -1584,6 +1584,31 @@ test_expect_success 'ls-files' '\n \tensure_not_expanded ls-files --sparse\n '\n \n+test_expect_success 'sparse index is not expanded: sparse-checkout' '\n+\tinit_repos &&\n+\n+\tensure_not_expanded sparse-checkout set deep/deeper2 &&\n+\tensure_not_expanded sparse-checkout set deep/deeper1 &&\n+\tensure_not_expanded sparse-checkout set deep &&\n+\tensure_not_expanded sparse-checkout add folder1 &&\n+\tensure_not_expanded sparse-checkout set deep/deeper1 &&\n+\tensure_not_expanded sparse-checkout set folder2 &&\n+\n+\t# Demonstrate that the checks that \"folder1/a\" is a file\n+\t# do not cause a sparse-index expansion (since it is in the\n+\t# sparse-checkout cone).\n+\techo >>sparse-index/folder2/a &&\n+\tgit -C sparse-index add folder2/a &&\n+\n+\tensure_not_expanded sparse-checkout add folder1 &&\n+\n+\t# Skip checks here, since deep/deeper1 is inside a sparse directory\n+\t# that must be expanded to check whether `deep/deeper1` is a file\n+\t# or not.\n+\tensure_not_expanded sparse-checkout set --skip-checks deep/deeper1 &&\n+\tensure_not_expanded sparse-checkout set\n+'\n+\n # NEEDSWORK: a sparse-checkout behaves differently from a full checkout\n # in this scenario, but it shouldn't.\n test_expect_success 'reset mixed and checkout orphan' '\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 7f528d35cc2..8908b27c03e 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -18,6 +18,7 @@\n #include \"promisor-remote.h\"\n #include \"entry.h\"\n #include \"parallel-checkout.h\"\n+#include \"sparse-index.h\"\n \n /*\n * Error messages expected by scripts out of plumbing commands such as\n@@ -2018,6 +2019,9 @@ enum update_sparsity_result update_sparsity(struct unpack_trees_options *o)\n \t\t\tgoto skip_sparse_checkout;\n \t}\n \n+\t/* Expand sparse directories as needed */\n+\texpand_index(o->src_index, o->pl);\n+\n \t/* Set NEW_SKIP_WORKTREE on existing entries. */\n \tmark_all_ce_unused(o->src_index);\n \tmark_new_skip_worktree(o->pl, o->src_index, 0,\n-- \ngitgitgadget\n"},{"id":"455797","messageId":"xmqqmtf8ruul.fsf@gitster.g","threadId":"57888","inReplyTo":"f9abea8d-5386-5275-4de2-27d443945c7a@github.com","subject":"Re: [PATCH v2 08/10] sparse-index: complete partial expansion","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-05-23T18:01:54Z","receivedAt":"2022-05-23T18:27:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> As I went to remove these from sparse-index.c, I found another that\n> exists, but for good reason. See 8a96b9d0a (sparse-index: use\n> WRITE_TREE_MISSING_OK, 2021-09-08), which explains that that instance\n> needs the flag because it could be used during 'git add'.\n\nHmph, re-reading that explanation, it appears to me that it is\nworking around a lack of another option that could be useful in such\na situation, namely, \"update the cache tree, and if a tree object is\nmissing then create one locally; do not bother asking any promisor\nremote\". I am reasonably sure that back when I invented missing-ok\nthere wasn't any such thing as \"promisor remote\" or \"lazy fetch\",\nand it sounds like those who added \"promissor remote\" broke the\ncache-tree subsystem by introducing calls to fetch from elsewhere?\n\nHow does a normal \"new object creation\" codepath work when promisor\nremotes exist? Does write_object_file() first ask if any promisor\nremote have that object and fetch before creating one locally? That\nsounds absurd (i.e. if we have data to create locally why ask others\nif they have one already?). Why should cache-tree behave any\ndifferently?\n\nAll of the above are mere observations on changes that have nothing\nto do with the change in this series, but cache_tree_update()\nknowing about promisor remotes feels serious breakage to me.\n\n> It still isn't necessary in the instances being added here, so I will\n> remove them.\n\nOK.\n"},{"id":"455858","messageId":"xmqqv8tvlvao.fsf@gitster.g","threadId":"57888","inReplyTo":"5909f466-c323-0874-b175-51fe5e93dc12@github.com","subject":"Re: [PATCH v2 08/10] sparse-index: complete partial expansion","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-05-23T22:48:47Z","receivedAt":"2022-05-23T22:48:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n>> I suspect that is a situation that is not so uncommon. Working\n>> inside a narrow cone of a wide tree, performing a merge would\n>> hopefully allow many subtrees that are outside of the cones of our\n>> interest merged without getting expanded at all (e.g. only the other\n>> side touched these subtrees we are not working on, so their version\n>> will become the merge result), while changes to some paths in the\n>> cone of our interest may result in true conflicts represented as\n>> cache entries at higher stages, needing conflict resolution\n>> concluded with \"git add\". Having to expand these subtrees that we\n>> managed to merge while still collapsed, only because we have\n>> conflicts in some other parts of the tree, feels somewhat sad.\n>\n> You are correct that conflicts outside of the sparse-checkout cone will\n> cause index expansion. That happens during the 'git merge' command, but\n> the index will continue to fail to collapse as long as those conflicts\n> still exist in the index.\n>\n> When there are conflicts like this during the merge, then the index\n> expansion is not as large of a portion of the command as normal, because\n> the conflict resolution also takes some time to compute. The commands\n> afterwards do take longer purely because of the expanded index.\n\nI was imagining a situation more like \"tech-writers only have\nDocumentation/ inside the cone of interest, attempt a pull from\nsomebody else, have conflicts inside Documentation/, but everything\nelse could be resolved cleanly without expanding the index\". If the\npuller's tree is based on the pristine upstream release tag, and the\npullee's tree is based on a slightly newer version of upstream\nsnapshot, everything that happened outside Documentation/ in their\ntrees would fast-forward, so such a merge wouldn't have to expand\ndirectories like \"builtin/\" or \"contrib/\" in the index and instead\ncan merge at the tree level, right?\n\nOn the other hand, ...\n\n> However, this state is also not as common as you might think. If a user\n> has a sparse-checkout cone specified, then they are unlikely to change\n> files outside of the sparse-checkout cone. They would not be the reason\n> that those files have a conflict. The conflicts would exist only if they\n> are merging branches that had conflicts outside of the cone. Typically,\n> any merge of external changes like this are of the form of \"git pull\" or\n> \"git rebase\", in which case the conflicts are still \"local\" to the\n> developer's changes.\n\n... you seem to be talking about the opposite case (e.g. in the\nabove paragraph), where a conflict happens outside the cone of\ninterest of the person who is making a merge. So, I am a bit\npuzzled.\n\n> You are right that there is additional work that could be done here,\n> specifically allowing the cache tree to partially succeed and use the\n> successfully generated trees to create sparse directory entries where\n> possible. This was not viable before because we lacked the \"partially\n> expanded\" index state. This series establishes the necessary vocabulary to\n> do such an improvement later.\n>> By the way, why are we passing the \"--missing-ok\" option to \"git\n>> write-tree\" here?\n>> \n>>> +\tcache_tree_update(istate, WRITE_TREE_MISSING_OK);\n>> \n>> The same question here. We didn't say \"missing trees are OK\". What\n>> made it OK in this change?\n> \n> Both of these additions of WRITE_TREE_MISSING_OK are not needed. I\n> think I added them in an earlier version, thinking they were needed\n> due to something in the Scalar functional tests. I confirmed just now\n> that they are not needed for that. I will remove them.\n>\n> Thanks,\n> -Stolee\n"},{"id":"456069","messageId":"f0327fd6-f2b3-64b6-3a34-2a7bbad20a01@github.com","threadId":"57888","inReplyTo":"xmqqv8tvlvao.fsf@gitster.g","subject":"Re: [PATCH v2 08/10] sparse-index: complete partial expansion","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-05-25T14:26:41Z","receivedAt":"2022-05-25T14:27:16Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/23/2022 6:48 PM, Junio C Hamano wrote:\n> Derrick Stolee writes:\n> \n>>> I suspect that is a situation that is not so uncommon. Working\n>>> inside a narrow cone of a wide tree, performing a merge would\n>>> hopefully allow many subtrees that are outside of the cones of our\n>>> interest merged without getting expanded at all (e.g. only the other\n>>> side touched these subtrees we are not working on, so their version\n>>> will become the merge result), while changes to some paths in the\n>>> cone of our interest may result in true conflicts represented as\n>>> cache entries at higher stages, needing conflict resolution\n>>> concluded with \"git add\". Having to expand these subtrees that we\n>>> managed to merge while still collapsed, only because we have\n>>> conflicts in some other parts of the tree, feels somewhat sad.\n>>\n>> You are correct that conflicts outside of the sparse-checkout cone will\n>> cause index expansion. That happens during the 'git merge' command, but\n>> the index will continue to fail to collapse as long as those conflicts\n>> still exist in the index.\n>>\n>> When there are conflicts like this during the merge, then the index\n>> expansion is not as large of a portion of the command as normal, because\n>> the conflict resolution also takes some time to compute. The commands\n>> afterwards do take longer purely because of the expanded index.\n> \n> I was imagining a situation more like \"tech-writers only have\n> Documentation/ inside the cone of interest, attempt a pull from\n> somebody else, have conflicts inside Documentation/, but everything\n> else could be resolved cleanly without expanding the index\". If the\n> puller's tree is based on the pristine upstream release tag, and the\n> pullee's tree is based on a slightly newer version of upstream\n> snapshot, everything that happened outside Documentation/ in their\n> trees would fast-forward, so such a merge wouldn't have to expand\n> directories like \"builtin/\" or \"contrib/\" in the index and instead\n> can merge at the tree level, right?\n> \n> On the other hand, ...\n> \n>> However, this state is also not as common as you might think. If a user\n>> has a sparse-checkout cone specified, then they are unlikely to change\n>> files outside of the sparse-checkout cone. They would not be the reason\n>> that those files have a conflict. The conflicts would exist only if they\n>> are merging branches that had conflicts outside of the cone. Typically,\n>> any merge of external changes like this are of the form of \"git pull\" or\n>> \"git rebase\", in which case the conflicts are still \"local\" to the\n>> developer's changes.\n> \n> ... you seem to be talking about the opposite case (e.g. in the\n> above paragraph), where a conflict happens outside the cone of\n> interest of the person who is making a merge. So, I am a bit\n> puzzled.\n\nHm. We must be getting mixed up with each other. Let me try again\nfrom the beginning.\n\nWhen the conflict happens inside of the sparse-checkout cone,\nthen the sparse index is not expanded. This is checked by the\ntest 'sparse-index is not expanded: merge conflict in cone' in\nt1092.\n\nMost merges get to \"fast forward\" changes that are outside of\nthe sparse-checkout cone because the only interesting changes\nthat could lead to a conflict are those created by the current\nuser (and hence within the sparse-checkout cone).\n\nSo, the typical case of a tech writer only editing \"Documentation/\"\nshould only see conflicts within \"Documentation/\".\n\nThe case where we would see conflicts outside of the cone include\ncases where long-lived branches are being merged by someone with\na small cone. I can imagine an automated process using an empty\nsparse-checkout cone to occasionally merge a \"deployed\" and a\n\"develop\" branch, and it gets conflicts when someone ships a\nhotfix directly to \"deployed\" without first going through \"develop\".\nAny conflict is likely to cause index expansion in this case.\n\nLet's re-introduce the patch section we are talking about:\n\n+\tif (pl && !pl->use_cone_patterns) {\n \t\tpl = NULL;\n+\t} else {\n+\t\t/*\n+\t\t * We might contract file entries into sparse-directory\n+\t\t * entries, and for that we will need the cache tree to\n+\t\t * be recomputed.\n+\t\t */\n+\t\tcache_tree_free(&istate->cache_tree);\n+\n+\t\t/*\n+\t\t * If there is a problem creating the cache tree, then we\n+\t\t * need to expand to a full index since we cannot satisfy\n+\t\t * the current request as a sparse index.\n+\t\t */\n+\t\tif (cache_tree_update(istate, WRITE_TREE_MISSING_OK))\n+\t\t\tpl = NULL;\n+\t}\n\nIf a user is in a conflict state and modifies their sparse-checkout\ncone, then we will hit this \"recompute the cache-tree\" state, fail,\nand cause full index expansion. I think that combination (have a\nconflict AND modify sparse-checkout cone) is rare enough to not\noptimize for (yet).\n\nDoes that make the situation more clear?\n\nThanks,\n-Stolee\n"},{"id":"456105","messageId":"xmqq35gxa7zc.fsf@gitster.g","threadId":"57888","inReplyTo":"f0327fd6-f2b3-64b6-3a34-2a7bbad20a01@github.com","subject":"Re: [PATCH v2 08/10] sparse-index: complete partial expansion","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-05-25T16:32:23Z","receivedAt":"2022-05-25T16:32:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> If a user is in a conflict state and modifies their sparse-checkout\n> cone, then we will hit this \"recompute the cache-tree\" state, fail,\n> and cause full index expansion. I think that combination (have a\n> conflict AND modify sparse-checkout cone) is rare enough to not\n> optimize for (yet).\n>\n> Does that make the situation more clear?\n\nYes. \"AND modify sparse-checkout cone\" part was what I was missing.\nI didn't see it because it wasn't there at all in the code that was\nremoved or added---it comes from the fact that the user is running\nthe \"sparse-checkout\" command in the first place, and that was what\nI missed.\n\nThanks.\n"}]}