git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCHv2 08/14] completion: let 'for-each-ref' and 'ls-remote' filter matching refs

From
SZEDER Gábor <szeder.dev@gmail.com>
Date
Mar 23, 2017, 15:29 UTC
Message-ID
<20170323152924.23944-9-szeder.dev@gmail.com>
In-Reply-To
<20170323152924.23944-1-szeder.dev@gmail.com>

When completing refs, several __git_refs() code paths list all the refs from the refs/{heads,tags,remotes}/ hierarchy and then __gitcomp_nl() iterates over those refs in a shell loop to filter out refs not matching the current ref to be completed. This comes with a considerable performance penalty when a repository contains a lot of refs but the current ref can be uniquely completed or when only a handful of refs match the current ref.

Reduce the number of iterations in __gitcomp_nl() from the number of refs to the number of matching refs by specifying appropriate globbing patterns to 'git for-each-ref' and 'git ls-remote' to list only those refs that match the current ref to be completed. However, do so only when the ref to match is explicitly given as parameter, because the current word on the command line might contain a prefix like '--option=' or 'branch..'. The __git_complete_refs() and __git_complete_fetch_refspecs() helpers introduced previously in this patch series already call __git_refs() specifying this current ref parameter, so all their callsites, i.e. all places in the completion script doing refs completion, can benefit from this optimization.

Furthermore, list only those symbolic and pseudo refs that match the current ref to be completed. Though it doesn't matter at all in itself performance-wise, it will allow us further significant optimizations later in this series.

This speeds up refs completion considerably when there are a lot of non-matching refs to be filtered out. Uniquely completing a branch in a repository with 100k local branches, all packed, best of five:

  On Linux, before:
    $ time __git_complete_refs --cur=maste
    real    0m0.831s
    user    0m0.808s
    sys     0m0.028s
  After:
    real    0m0.119s
    user    0m0.104s
    sys     0m0.008s
  On Windows, before:
    real    0m1.480s
    user    0m1.031s
    sys     0m0.060s
  After:
    real    0m0.377s
    user    0m0.015s
    sys     0m0.030s
Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
---
 contrib/completion/git-completion.bash |  41 ++++++++---
 t/t9902-completion.sh                  | 124 +++++++++++++++++++++++++++++++++
 2 files changed, 154 insertions(+), 11 deletions(-)
diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash
index 5ee35d530..976f80598 100644
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash
@@ -355,7 +355,8 @@ __git_tags ()
 # 2: In addition to local refs, list unique branches from refs/remotes/ for
 #    'git checkout's tracking DWIMery (optional; ignored, if set but empty).
 # 3: Currently ignored.
-# 4: The current ref to be completed (optional).
+# 4: List only refs matching this word (optional; list all refs if unset or
+#    empty).
 #
 # Use __git_complete_refs() instead.
 __git_refs ()
@@ -364,6 +365,7 @@ __git_refs ()
 	local list_refs_from=path remote="${1-}"
 	local format refs pfx
 	local cur_="${4-$cur}"
+	local match="${4-}"
 
 	__git_find_repo_path
 	dir="$__git_repo_path"
@@ -390,23 +392,32 @@ __git_refs ()
 		if [[ "$cur_" == ^* ]]; then
 			pfx="^"
 			cur_=${cur_#^}
+			match=${match#^}
 		fi
 		case "$cur_" in
 		refs|refs/*)
 			format="refname"
-			refs="${cur_%/*}"
+			refs=("$match*" "$match*/**")
 			track=""
 			;;
 		*)
 			for i in HEAD FETCH_HEAD ORIG_HEAD MERGE_HEAD; do
-				if [ -e "$dir/$i" ]; then echo $pfx$i; fi
+				case "$i" in
+				$match*)
+					if [ -e "$dir/$i" ]; then
+						echo $pfx$i
+					fi
+					;;
+				esac
 			done
 			format="refname:strip=2"
-			refs="refs/tags refs/heads refs/remotes"
+			refs=("refs/tags/$match*" "refs/tags/$match*/**"
+				"refs/heads/$match*" "refs/heads/$match*/**"
+				"refs/remotes/$match*" "refs/remotes/$match*/**")
 			;;
 		esac
 		__git_dir="$dir" __git for-each-ref --format="$pfx%($format)" \
-			$refs
+			"${refs[@]}"
 		if [ -n "$track" ]; then
 			# employ the heuristic used by git checkout
 			# Try to find a remote branch that matches the completion word
@@ -417,7 +428,7 @@ __git_refs ()
 			while read -r entry; do
 				eval "$entry"
 				ref="${ref#*/}"
-				if [[ "$ref" == "$cur_"* ]]; then
+				if [[ "$ref" == "$match"* ]]; then
 					echo "$ref"
 				fi
 			done | sort | uniq -u
@@ -426,7 +437,7 @@ __git_refs ()
 	fi
 	case "$cur_" in
 	refs|refs/*)
-		__git ls-remote "$remote" "$cur_*" | \
+		__git ls-remote "$remote" "$match*" | \
 		while read -r hash i; do
 			case "$i" in
 			*^{}) ;;
@@ -436,12 +447,20 @@ __git_refs ()
 		;;
 	*)
 		if [ "$list_refs_from" = remote ]; then
-			echo "HEAD"
+			case "HEAD" in
+			$match*)	echo "HEAD" ;;
+			esac
 			__git for-each-ref --format="%(refname:strip=2)" \
-				"refs/remotes/$remote/" | sed -e "s#^$remote/##"
+				"refs/remotes/$remote/$match*" \
+				"refs/remotes/$remote/$match*/**" | sed -e "s#^$remote/##"
 		else
-			__git ls-remote "$remote" HEAD \
-				"refs/tags/*" "refs/heads/*" "refs/remotes/*" |
+			local query_symref
+			case "HEAD" in
+			$match*)	query_symref="HEAD" ;;
+			esac
+			__git ls-remote "$remote" $query_symref \
+				"refs/tags/$match*" "refs/heads/$match*" \
+				"refs/remotes/$match*" |
 			while read -r hash i; do
 				case "$i" in
 				*^{})	;;
diff --git a/t/t9902-completion.sh b/t/t9902-completion.sh
index e2b45f625..cc9e741f9 100755
--- a/t/t9902-completion.sh
+++ b/t/t9902-completion.sh
@@ -555,6 +555,9 @@ test_expect_success '__git_refs - full refs' '
 	cat >expected <<-EOF &&
 	refs/heads/master
 	refs/heads/matching-branch
+	refs/remotes/other/branch-in-other
+	refs/remotes/other/master-in-other
+	refs/tags/matching-tag
 	EOF
 	(
 		cur=refs/heads/ &&
@@ -620,6 +623,7 @@ test_expect_success '__git_refs - configured remote' '
 
 test_expect_success '__git_refs - configured remote - full refs' '
 	cat >expected <<-EOF &&
+	HEAD
 	refs/heads/branch-in-other
 	refs/heads/master-in-other
 	refs/tags/tag-in-other
@@ -648,6 +652,7 @@ test_expect_success '__git_refs - configured remote - repo given on the command
 
 test_expect_success '__git_refs - configured remote - full refs - repo given on the command line' '
 	cat >expected <<-EOF &&
+	HEAD
 	refs/heads/branch-in-other
 	refs/heads/master-in-other
 	refs/tags/tag-in-other
@@ -692,6 +697,7 @@ test_expect_success '__git_refs - URL remote' '
 
 test_expect_success '__git_refs - URL remote - full refs' '
 	cat >expected <<-EOF &&
+	HEAD
 	refs/heads/branch-in-other
 	refs/heads/master-in-other
 	refs/tags/tag-in-other
@@ -837,6 +843,124 @@ test_expect_success '__git refs - exluding full refs' '
 	test_cmp expected "$actual"
 '
 
+test_expect_success 'setup for filtering matching refs' '
+	git branch matching/branch &&
+	git tag matching/tag &&
+	git -C otherrepo branch matching/branch-in-other &&
+	git fetch --no-tags other &&
+	rm -f .git/FETCH_HEAD
+'
+
+test_expect_success '__git_refs - dont filter refs unless told so' '
+	cat >expected <<-EOF &&
+	HEAD
+	master
+	matching-branch
+	matching/branch
+	other/branch-in-other
+	other/master-in-other
+	other/matching/branch-in-other
+	matching-tag
+	matching/tag
+	EOF
+	(
+		cur=master &&
+		__git_refs >"$actual"
+	) &&
+	test_cmp expected "$actual"
+'
+
+test_expect_success '__git_refs - only matching refs' '
+	cat >expected <<-EOF &&
+	matching-branch
+	matching/branch
+	matching-tag
+	matching/tag
+	EOF
+	(
+		cur=mat &&
+		__git_refs "" "" "" "$cur" >"$actual"
+	) &&
+	test_cmp expected "$actual"
+'
+
+test_expect_success '__git_refs - only matching refs - full refs' '
+	cat >expected <<-EOF &&
+	refs/heads/matching-branch
+	refs/heads/matching/branch
+	EOF
+	(
+		cur=refs/heads/mat &&
+		__git_refs "" "" "" "$cur" >"$actual"
+	) &&
+	test_cmp expected "$actual"
+'
+
+test_expect_success '__git_refs - only matching refs - remote on local file system' '
+	cat >expected <<-EOF &&
+	master-in-other
+	matching/branch-in-other
+	EOF
+	(
+		cur=ma &&
+		__git_refs otherrepo "" "" "$cur" >"$actual"
+	) &&
+	test_cmp expected "$actual"
+'
+
+test_expect_success '__git_refs - only matching refs - configured remote' '
+	cat >expected <<-EOF &&
+	master-in-other
+	matching/branch-in-other
+	EOF
+	(
+		cur=ma &&
+		__git_refs other "" "" "$cur" >"$actual"
+	) &&
+	test_cmp expected "$actual"
+'
+
+test_expect_success '__git_refs - only matching refs - remote - full refs' '
+	cat >expected <<-EOF &&
+	refs/heads/master-in-other
+	refs/heads/matching/branch-in-other
+	EOF
+	(
+		cur=refs/heads/ma &&
+		__git_refs other "" "" "$cur" >"$actual"
+	) &&
+	test_cmp expected "$actual"
+'
+
+test_expect_success '__git_refs - only matching refs - checkout DWIMery' '
+	cat >expected <<-EOF &&
+	matching-branch
+	matching/branch
+	matching-tag
+	matching/tag
+	matching/branch-in-other
+	EOF
+	for remote_ref in refs/remotes/other/ambiguous \
+		refs/remotes/remote/ambiguous \
+		refs/remotes/remote/branch-in-remote
+	do
+		git update-ref $remote_ref master &&
+		test_when_finished "git update-ref -d $remote_ref"
+	done &&
+	(
+		cur=mat &&
+		__git_refs "" 1 "" "$cur" >"$actual"
+	) &&
+	test_cmp expected "$actual"
+'
+
+test_expect_success 'teardown after filtering matching refs' '
+	git branch -d matching/branch &&
+	git tag -d matching/tag &&
+	git update-ref -d refs/remotes/other/matching/branch-in-other &&
+	git -C otherrepo branch -D matching/branch-in-other
+'
+
 test_expect_success '__git_complete_refs - simple' '
 	sed -e "s/Z$//" >expected <<-EOF &&
 	HEAD Z

-- 
2.12.1.485.g1616aa492
Previous: SZEDER GáborNext: Jeff King
Message 8 of 22 in “[PATCHv2 00/14] completion: speed up refs completion”
  1. SZEDER GáborMar 23, 2017
  2. 01/14 completion: remove redundant __gitcomp_nl() options from _git_commit()SZEDER Gábor, Mar 23, 2017
  3. 05/14 completion: support excluding full refsSZEDER Gábor, Mar 23, 2017
  4. 04/14 completion: support completing fully qualified non-fast-forward refspecsSZEDER Gábor, Mar 23, 2017
  5. 07/14 completion: don't disambiguate short refsSZEDER Gábor, Mar 23, 2017
  6. Jeff KingMar 24, 2017
  7. 13/14 completion: fill COMPREPLY directly when completing fetch refspecsSZEDER Gábor, Mar 23, 2017
  8. 08/14 completion: let 'for-each-ref' and 'ls-remote' filter matching refsSZEDER Gábor, Mar 23, 2017
  9. Jeff KingMar 24, 2017
  10. SZEDER GáborMar 28, 2017
  11. 09/14 completion: let 'for-each-ref' strip the remote name from remote branchesSZEDER Gábor, Mar 23, 2017
  12. 10/14 completion: let 'for-each-ref' filter remote branches for 'checkout' DWIMerySZEDER Gábor, Mar 23, 2017
  13. 14/14 completion: speed up branch and tag completionSZEDER Gábor, Mar 23, 2017
  14. 12/14 completion: fill COMPREPLY directly when completing refsSZEDER Gábor, Mar 23, 2017
  15. 11/14 completion: let 'for-each-ref' sort remote branches for 'checkout' DWIMerySZEDER Gábor, Mar 23, 2017
  16. Jeff KingMar 24, 2017
  17. 03/14 completion: support completing full refs after '--option=refs/<TAB>'SZEDER Gábor, Mar 23, 2017
  18. 02/14 completion: wrap __git_refs() for better option parsingSZEDER Gábor, Mar 23, 2017
  19. 06/14 completion: don't disambiguate tags and branchesSZEDER Gábor, Mar 23, 2017
  20. SZEDER GáborMar 23, 2017
  21. Junio C HamanoMar 23, 2017
  22. Jeff KingMar 24, 2017

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.