[PATCH v6 0/1] grep: integrate with sparse index

Integrate `git-grep` with sparse-index and test the performance improvement.

Changes since v5 ----------------

* Drop the `--sparse` option patch and edit corresponding tests. 
  We can wait until a better name is decided to replace `--sparse`.

* Modify the commit message, especially get rid of the `--sparse`
  occurences.

Changes since v4
----------------
* Reset the length of `struct strbuf name` back to `name_base_len`,
  instead of 0, after `grep_tree()` returns.

* Add test cases in t1092 for `grep` recursing into submodules.

* Add a few NEEDSWORK to explain the current problem with submodules.

Changes since v3
----------------
* Shorten the perf result tables in commit message.

* Update the commit message to reflect the changes in the commit.

* Update the commit message to indicate the performance improvement
  is dependent on the pathspec.

* Stop passing `ce_mode` through `check_attr`. Instead, set the
  `base_len` to 0 to make the code more reasonable and less abuse of
  `check_attr`.

* Remove another invention of `base`. Use the existing `name` as the
  argument for `grep_tree()`, and reset it back to `ce->name` after
  `grep_tree()` returns.

* Update the p2000 test to use a more general pathspec for better
  compatibility (i.e. do not use git repository specific pathspec).

* Add tests to t1092 'grep is not expanded' to verify the change
  brought by "builtin/grep.c: walking tree instead of expanding index
  with --sparse": the index *never* expands.

Changes since v2 ----------------

* Modify the commit message for "builtin/grep.c: integrate with sparse
  index" to make it obvious that the perf test results are not from
  p2000 tests, but from manual perf runs.

* Add tree-walking logic as an extra (the third) patch to improve the
  performance when --sparse is used. This resolved the left-over-bit
  in v2 [1].

[1] https://lore.kernel.org/git/20220829232843.183711-1-shaoxuan.yuan02@gmail.com/

Changes since v1 ----------------

* Rewrite the commit message for "builtin/grep.c: add --sparse option"
  to be clearer.

* Update the documentation (both in-code and man page) for --sparse.

* Add a few tests to test the new behavior (when _only_ --cached is
  supplied).

* Reformat the perf test results to not look like directly from p2000
  tests.

* Put the "command_requires_full_index" lines right after parse_options().

* Add a pathspec test in t1092, and reword a few test documentations.

Shaoxuan Yuan (1):
  builtin/grep.c: integrate with sparse index

 builtin/grep.c                           | 48 +++++++++++++++-
 t/perf/p2000-sparse-operations.sh        |  1 +
 t/t1092-sparse-checkout-compatibility.sh | 72 ++++++++++++++++++++++++
 3 files changed, 118 insertions(+), 3 deletions(-)

Range-diff against v5:
1:  1d00d23bf9 < -:  ---------- builtin/grep.c: add --sparse option
2:  926b8d2462 < -:  ---------- builtin/grep.c: integrate with sparse index
3:  18b65034fe ! 1:  8604111d74 builtin/grep.c: walking tree instead of expanding index with --sparse
    @@ Metadata
     Author: Shaoxuan Yuan <shaoxuan.yuan02@gmail.com>
     
      ## Commit message ##
    -    builtin/grep.c: walking tree instead of expanding index with --sparse
    +    builtin/grep.c: integrate with sparse index
     
    -    Before this patch, whenever --sparse is used, `git-grep` utilizes the
    -    ensure_full_index() method to expand the index and search all the
    -    entries. Because this method requires walking all the trees and
    -    constructing the index, it is the slow part within the whole command.
    +    Turn on sparse index and remove ensure_full_index().
    +
    +    Before this patch, `git-grep` utilizes the ensure_full_index() method to
    +    expand the index and search all the entries. Because this method
    +    requires walking all the trees and constructing the index, it is the
    +    slow part within the whole command.
     
         To achieve better performance, this patch uses grep_tree() to search the
         sparse directory entries and get rid of the ensure_full_index() method.
    @@ Commit message
            result of expanding the index.
     
         2) grep_tree() utilizes pathspecs to limit the scope of searching.
    -       ensure_full_index() always expands the index when --sparse is used,
    -       that means it will always walk all the trees and blobs in the repo
    -       without caring if the user only wants a subset of the content, i.e.
    -       using a pathspec. On the other hand, grep_tree() will only search
    -       the contents that match the pathspec, and thus possibly walking fewer
    -       trees.
    +       ensure_full_index() always expands the index, which means it will
    +       always walk all the trees and blobs in the repo without caring if
    +       the user only wants a subset of the content, i.e. using a pathspec.
    +       On the other hand, grep_tree() will only search the contents that
    +       match the pathspec, and thus possibly walking fewer trees.
     
         3) grep_tree() does not construct and copy back a new index, while
            ensure_full_index() does. This also saves some time.
    @@ Commit message
         - Summary:
     
         p2000 tests demonstrate a ~71% execution time reduction for
    -    `git grep --cached --sparse bogus -- "f2/f1/f1/*"` using tree-walking
    -    logic. However, notice that this result varies depending on the pathspec
    +    `git grep --cached bogus -- "f2/f1/f1/*"` using tree-walking logic.
    +    However, notice that this result varies depending on the pathspec
         given. See below "Command used for testing" for more details.
     
         Test                              HEAD~   HEAD
    @@ Commit message
     
         - Command used for testing:
     
    -            git grep --cached --sparse bogus -- "f2/f1/f1/*"
    +            git grep --cached bogus -- "f2/f1/f1/*"
     
         The reason for specifying a pathspec is that, if we don't specify a
         pathspec, then grep_tree() will walk all the trees and blobs to find the
    @@ Commit message
     
                 Command used:
     
    -                    git grep --cached --sparse bogus
    +                    git grep --cached bogus
     
                 Test                                HEAD~  HEAD
                 ---------------------------------------------------
    @@ Commit message
         Suggested-by: Derrick Stolee <derrickstolee@github.com>
         Helped-by: Derrick Stolee <derrickstolee@github.com>
         Helped-by: Victoria Dye <vdye@github.com>
    +    Helped-by: Elijah Newren <newren@gmail.com>
         Signed-off-by: Shaoxuan Yuan <shaoxuan.yuan02@gmail.com>
     
      ## builtin/grep.c ##
    @@ builtin/grep.c: static int grep_cache(struct grep_opt *opt,
      	if (repo_read_index(repo) < 0)
      		die(_("index file corrupt"));
      
    --	if (grep_sparse)
    --		ensure_full_index(repo->index);
    --
    +-	/* TODO: audit for interaction with sparse-index. */
    +-	ensure_full_index(repo->index);
      	for (nr = 0; nr < repo->index->cache_nr; nr++) {
      		const struct cache_entry *ce = repo->index->cache[nr];
      
    @@ builtin/grep.c: static int grep_cache(struct grep_opt *opt,
     +			struct tree_desc tree;
     +			void *data;
     +			unsigned long size;
    -+
    -+			data = read_object_file(&ce->oid, &type, &size);
    -+			init_tree_desc(&tree, data, size);
      
     -		if (S_ISREG(ce->ce_mode) &&
    ++			data = read_object_file(&ce->oid, &type, &size);
    ++			init_tree_desc(&tree, data, size);
    ++
     +			hit |= grep_tree(opt, pathspec, &tree, &name, 0, 0);
     +			strbuf_setlen(&name, name_base_len);
     +			strbuf_addstr(&name, ce->name);
    @@ builtin/grep.c: static int grep_cache(struct grep_opt *opt,
      		    match_pathspec(repo->index, pathspec, name.buf, name.len, 0, NULL,
      				   S_ISDIR(ce->ce_mode) ||
      				   S_ISGITLINK(ce->ce_mode))) {
    +@@ builtin/grep.c: int cmd_grep(int argc, const char **argv, const char *prefix)
    + 			     PARSE_OPT_KEEP_DASHDASH |
    + 			     PARSE_OPT_STOP_AT_NON_OPTION);
    + 
    ++	if (the_repository->gitdir) {
    ++		prepare_repo_settings(the_repository);
    ++		the_repository->settings.command_requires_full_index = 0;
    ++	}
    ++
    + 	if (use_index && !startup_info->have_repository) {
    + 		int fallback = 0;
    + 		git_config_get_bool("grep.fallbacktonoindex", &fallback);
     
      ## t/perf/p2000-sparse-operations.sh ##
     @@ t/perf/p2000-sparse-operations.sh: test_perf_on_all git read-tree -mu HEAD
    @@ t/t1092-sparse-checkout-compatibility.sh: init_repos () {
      run_on_sparse () {
      	(
      		cd sparse-checkout &&
    -@@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'grep is not expanded' '
    +@@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse index is not expanded: rm' '
    + 	ensure_not_expanded rm -r deep
    + '
      
    - 	# All files within the folder1/* pathspec are sparse,
    - 	# so this command does not find any matches
    --	ensure_not_expanded ! grep a -- folder1/*
    ++test_expect_success 'grep with and --cached' '
    ++	init_repos &&
    ++
    ++	test_all_match git grep --cached a &&
    ++	test_all_match git grep --cached a -- "folder1/*"
    ++'
    ++
    ++test_expect_success 'grep is not expanded' '
    ++	init_repos &&
    ++
    ++	ensure_not_expanded grep a &&
    ++	ensure_not_expanded grep a -- deep/* &&
    ++
    ++	# All files within the folder1/* pathspec are sparse,
    ++	# so this command does not find any matches
     +	ensure_not_expanded ! grep a -- folder1/* &&
     +
     +	# test out-of-cone pathspec with or without wildcard
    -+	ensure_not_expanded grep --sparse --cached a -- "folder1/a" &&
    -+	ensure_not_expanded grep --sparse --cached a -- "folder1/*" &&
    ++	ensure_not_expanded grep --cached a -- "folder1/a" &&
    ++	ensure_not_expanded grep --cached a -- "folder1/*" &&
     +
     +	# test in-cone pathspec with or without wildcard
    -+	ensure_not_expanded grep --sparse --cached a -- "deep/a" &&
    -+	ensure_not_expanded grep --sparse --cached a -- "deep/*"
    ++	ensure_not_expanded grep --cached a -- "deep/a" &&
    ++	ensure_not_expanded grep --cached a -- "deep/*"
     +'
     +
     +# NEEDSWORK: when running `grep` in the superproject with --recurse-submodules,
    @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'grep is not expan
     +	# do not use ensure_not_expanded() here, becasue `grep` should be
     +	# run in the superproject, not in "./sparse-index"
     +	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
    -+	git grep --sparse --cached --recurse-submodules a -- "*/folder1/*" &&
    ++	git grep --cached --recurse-submodules a -- "*/folder1/*" &&
     +	test_region ! index ensure_full_index trace2.txt
     +'
     +
    @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'grep is not expan
     +	sparse-checkout/folder1/a:a
     +	sparse-index/folder1/a:a
     +	EOF
    -+	git grep --sparse --cached --recurse-submodules a -- "*/folder1/*" >actual &&
    ++	git grep --cached --recurse-submodules a -- "*/folder1/*" >actual &&
     +	test_cmp actual expect
    - '
    - 
    ++'
    ++
      test_done

base-commit: 1b3d6e17fe83eb6f79ffbac2f2c61bbf1eaef5f8