[PATCH v3 0/7] completion: reorg and performance improvements

Hi,

I sent these some time ago for comments, but I think they are ready. Basically
some reorganization in order to achieve some performance improvements, also,
fix a few bugs.

Felipe Contreras (7):
  completion: trivial test improvement
  completion: get rid of empty COMPREPLY assignments
  completion: add new __gitcompadd helper
  completion: add __gitcomp_nl tests
  completion: get rid of compgen
  completion: get rid of __gitcomp_1
  completion: small optimization

 contrib/completion/git-completion.bash | 71 +++++++++++++---------------------
 t/t9902-completion.sh                  | 65 ++++++++++++++++++++++++++++++-
 2 files changed, 90 insertions(+), 46 deletions(-)

-- 
1.8.2.1

Instead of passing a dummy "", let's check if the last character is a
space, and then move the _cword accordingly.

Apparently we were passing "" all the way to compgen, which fortunately
expanded it to nothing.

Lets do the right thing though.

Signed-off-by: Felipe Contreras <redacted>
---
 t/t9902-completion.sh | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/t/t9902-completion.sh b/t/t9902-completion.sh
index adc1372..99d5c01 100755
--- a/t/t9902-completion.sh
+++ b/t/t9902-completion.sh

@@ -69,6 +69,7 @@ run_completion ()
 	local -a COMPREPLY _words
 	local _cword
 	_words=( $1 )
+	test "${1: -1}" == ' ' && _words+=('')
 	(( _cword = ${#_words[@]} - 1 ))
 	__git_wrap__git_main && print_comp
 }

@@ -148,7 +149,7 @@ test_expect_success '__gitcomp - suffix' '
 '
 
 test_expect_success 'basic' '
-	run_completion "git \"\"" &&
+	run_completion "git " &&
 	# built-in
 	grep -q "^add \$" out &&
 	# script

-- 
1.8.2.1

There's no functional reason for those, the only purpose they are
supposed to serve is to say "we don't provide any words here", but even
for that it's not used consitently.

Signed-off-by: Felipe Contreras <redacted>
---
 contrib/completion/git-completion.bash | 21 ---------------------
 1 file changed, 21 deletions(-)

diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash
index 93eba46..2c87fd8 100644
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash

@@ -208,7 +208,6 @@ __gitcomp ()
 
 	case "$cur_" in
 	--*=)
-		COMPREPLY=()
 		;;
 	*)
 		local IFS=$'\n'

@@ -614,7 +613,6 @@ __git_complete_remote_or_refspec ()
 			case "$cmd" in
 			push) no_complete_refspec=1 ;;
 			fetch)
-				COMPREPLY=()
 				return
 				;;
 			*) ;;

@@ -630,7 +628,6 @@ __git_complete_remote_or_refspec ()
 		return
 	fi
 	if [ $no_complete_refspec = 1 ]; then
-		COMPREPLY=()
 		return
 	fi
 	[ "$remote" = "." ] && remote=

@@ -951,7 +948,6 @@ _git_am ()
 			"
 		return
 	esac
-	COMPREPLY=()
 }
 
 _git_apply ()

@@ -971,7 +967,6 @@ _git_apply ()
 			"
 		return
 	esac
-	COMPREPLY=()
 }
 
 _git_add ()

@@ -1031,7 +1026,6 @@ _git_bisect ()
 		__gitcomp_nl "$(__git_refs)"
 		;;
 	*)
-		COMPREPLY=()
 		;;
 	esac
 }

@@ -1170,7 +1164,6 @@ _git_clone ()
 		return
 		;;
 	esac
-	COMPREPLY=()
 }
 
 _git_commit ()

@@ -1354,7 +1347,6 @@ _git_fsck ()
 		return
 		;;
 	esac
-	COMPREPLY=()
 }
 
 _git_gc ()

@@ -1365,7 +1357,6 @@ _git_gc ()
 		return
 		;;
 	esac
-	COMPREPLY=()
 }
 
 _git_gitk ()

@@ -1442,7 +1433,6 @@ _git_init ()
 		return
 		;;
 	esac
-	COMPREPLY=()
 }
 
 _git_ls_files ()

@@ -1578,7 +1568,6 @@ _git_mergetool ()
 		return
 		;;
 	esac
-	COMPREPLY=()
 }
 
 _git_merge_base ()

@@ -1891,7 +1880,6 @@ _git_config ()
 		return
 		;;
 	*.*)
-		COMPREPLY=()
 		return
 		;;
 	esac

@@ -2272,7 +2260,6 @@ _git_remote ()
 		__gitcomp "$c"
 		;;
 	*)
-		COMPREPLY=()
 		;;
 	esac
 }

@@ -2388,8 +2375,6 @@ _git_stash ()
 		*)
 			if [ -z "$(__git_find_on_cmdline "$save_opts")" ]; then
 				__gitcomp "$subcommands"
-			else
-				COMPREPLY=()
 			fi
 			;;
 		esac

@@ -2402,14 +2387,12 @@ _git_stash ()
 			__gitcomp "--index --quiet"
 			;;
 		show,--*|drop,--*|branch,--*)
-			COMPREPLY=()
 			;;
 		show,*|apply,*|drop,*|pop,*|branch,*)
 			__gitcomp_nl "$(git --git-dir="$(__gitdir)" stash list \
 					| sed -n -e 's/:.*//p')"
 			;;
 		*)
-			COMPREPLY=()
 			;;
 		esac
 	fi

@@ -2526,7 +2509,6 @@ _git_svn ()
 			__gitcomp "--revision= --parent"
 			;;
 		*)
-			COMPREPLY=()
 			;;
 		esac
 	fi

@@ -2551,13 +2533,10 @@ _git_tag ()
 
 	case "$prev" in
 	-m|-F)
-		COMPREPLY=()
 		;;
 	-*|tag)
 		if [ $f = 1 ]; then
 			__gitcomp_nl "$(__git_tags)"
-		else
-			COMPREPLY=()
 		fi
 		;;
 	*)

-- 
1.8.2.1

The idea is to never touch the COMPREPLY variable directly.

This allows other completion systems (i.e. zsh) to override
__gitcompadd, and do something different instead.

Also, this allows further optimizations down the line.

There should be no functional changes.

Signed-off-by: Felipe Contreras <redacted>
---
 contrib/completion/git-completion.bash | 13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)

diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash
index 2c87fd8..90b54ab 100644
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash

@@ -195,6 +195,11 @@ _get_comp_words_by_ref ()
 }
 fi
 
+__gitcompadd ()
+{
+	COMPREPLY=($(compgen -W "$1" -P "$2" -S "$4" -- "$3"))
+}
+
 # Generates completion reply with compgen, appending a space to possible
 # completion words, if necessary.
 # It accepts 1 to 4 arguments:

@@ -211,9 +216,7 @@ __gitcomp ()
 		;;
 	*)
 		local IFS=$'\n'
-		COMPREPLY=($(compgen -P "${2-}" \
-			-W "$(__gitcomp_1 "${1-}" "${4-}")" \
-			-- "$cur_"))
+		__gitcompadd "$(__gitcomp_1 "${1-}" "${4-}")" "${2-}" "$cur_" ""
 		;;
 	esac
 }

@@ -230,7 +233,7 @@ __gitcomp ()
 __gitcomp_nl ()
 {
 	local IFS=$'\n'
-	COMPREPLY=($(compgen -P "${2-}" -S "${4- }" -W "$1" -- "${3-$cur}"))
+	__gitcompadd "$1" "${2-}" "${3-$cur}" "${4- }"
 }
 
 # Generates completion reply with compgen from newline-separated possible

@@ -1820,7 +1823,7 @@ _git_config ()
 		local remote="${prev#remote.}"
 		remote="${remote%.fetch}"
 		if [ -z "$cur" ]; then
-			COMPREPLY=("refs/heads/")
+			__gitcompadd "refs/heads/"
 			return
 		fi
 		__gitcomp_nl "$(__git_refs_remotes "$remote")"

-- 
1.8.2.1

Original patch by SZEDER Gábor.

Signed-off-by: Felipe Contreras <redacted>
---
 t/t9902-completion.sh | 60 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 60 insertions(+)

diff --git a/t/t9902-completion.sh b/t/t9902-completion.sh
index 99d5c01..b752f4d 100755
--- a/t/t9902-completion.sh
+++ b/t/t9902-completion.sh

@@ -105,6 +105,23 @@ test_gitcomp ()
 	test_cmp expected out
 }
 
+# Test __gitcomp_nl
+# Arguments are:
+# 1: current word (cur)
+# -: the rest are passed to __gitcomp_nl
+test_gitcomp_nl ()
+{
+	local -a COMPREPLY &&
+	sed -e 's/Z$//' >expected &&
+	cur="$1" &&
+	shift &&
+	__gitcomp_nl "$@" &&
+	print_comp &&
+	test_cmp expected out
+}
+
+invalid_variable_name='${foo.bar}'
+
 test_expect_success '__gitcomp - trailing space - options' '
 	test_gitcomp "--re" "--dry-run --reuse-message= --reedit-message=
 		--reset-author" <<-EOF

@@ -148,6 +165,49 @@ test_expect_success '__gitcomp - suffix' '
 	EOF
 '
 
+test_expect_failure '__gitcomp - doesnt fail because of invalid variable name' '
+	__gitcomp "$invalid_variable_name"
+'
+
+read -r -d "" refs <<-\EOF
+maint
+master
+next
+pu
+EOF
+
+test_expect_success '__gitcomp_nl - trailing space' '
+	test_gitcomp_nl "m" "$refs" <<-EOF
+	maint Z
+	master Z
+	EOF
+'
+
+test_expect_success '__gitcomp_nl - prefix' '
+	test_gitcomp_nl "--fixup=m" "$refs" "--fixup=" "m" <<-EOF
+	--fixup=maint Z
+	--fixup=master Z
+	EOF
+'
+
+test_expect_success '__gitcomp_nl - suffix' '
+	test_gitcomp_nl "branch.ma" "$refs" "branch." "ma" "." <<-\EOF
+	branch.maint.Z
+	branch.master.Z
+	EOF
+'
+
+test_expect_success '__gitcomp_nl - no suffix' '
+	test_gitcomp_nl "ma" "$refs" "" "ma" "" <<-\EOF
+	maintZ
+	masterZ
+	EOF
+'
+
+test_expect_failure '__gitcomp_nl - doesnt fail because of invalid variable name' '
+	__gitcomp_nl "$invalid_variable_name"
+'
+
 test_expect_success 'basic' '
 	run_completion "git " &&
 	# built-in

-- 
1.8.2.1

The functionality we use from compgen is not much, we can do the same
manually, with drastical improvements in speed, specially when dealing
with only a few words.

This patch also has the sideffect that brekage reported by Jeroen Meijer
and SZEDER Gábor gets fixed because we no longer expand the resulting
words.

Here are some numbers filtering N amount of words:

  == 1 ==
  original: 0.002s
  new: 0.000s
  == 10 ==
  original: 0.002s
  new: 0.000s
  == 100 ==
  original: 0.003s
  new: 0.002s
  == 1000 ==
  original: 0.012s
  new: 0.011s
  == 10000 ==
  original: 0.056s
  new: 0.066s
  == 100000 ==
  original: 2.669s
  new: 0.622s

If the results are not narrowed:

  == 1 ==
  original: 0.002s
  new: 0.000s
  == 10 ==
  original: 0.002s
  new: 0.001s
  == 100 ==
  original: 0.004s
  new: 0.004s
  == 1000 ==
  original: 0.020s
  new: 0.015s
  == 10000 ==
  original: 0.101s
  new: 0.355s
  == 100000 ==
  original: 2.850s
  new: 31.941s

So, unless 'git checkout <tab>' usually gives you more than 100000
results, you'll get an improvement :)

Other possible solutions perform better after 1000 words, but worst if
less than that:

  COMPREPLY=($(awk -v cur="$3" -v pre="$2" -v suf="$4"
	'$0 ~ cur { print pre$0suf }' <<< "$1" ))

  COMPREPLY=($(printf -- "$2%s$4\n" $1 | grep "^$2$3"))

Signed-off-by: Felipe Contreras <redacted>
---
 contrib/completion/git-completion.bash | 15 ++++++++++-----
 t/t9902-completion.sh                  |  6 +++---
 2 files changed, 13 insertions(+), 8 deletions(-)

diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash
index 90b54ab..d8009f5 100644
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash

@@ -197,11 +197,16 @@ fi
 
 __gitcompadd ()
 {
-	COMPREPLY=($(compgen -W "$1" -P "$2" -S "$4" -- "$3"))
+	local i=0
+	for x in $1; do
+		if [[ "$x" == "$3"* ]]; then
+			COMPREPLY[i++]="$2$x$4"
+		fi
+	done
 }
 
-# Generates completion reply with compgen, appending a space to possible
-# completion words, if necessary.
+# Generates completion reply, appending a space to possible completion words,
+# if necessary.
 # It accepts 1 to 4 arguments:
 # 1: List of possible completion words.
 # 2: A prefix to be added to each possible completion word (optional).

@@ -221,8 +226,8 @@ __gitcomp ()
 	esac
 }
 
-# Generates completion reply with compgen from newline-separated possible
-# completion words by appending a space to all of them.
+# Generates completion reply from newline-separated possible completion words
+# by appending a space to all of them.
 # It accepts 1 to 4 arguments:
 # 1: List of possible completion words, separated by a single newline.
 # 2: A prefix to be added to each possible completion word (optional).

diff --git a/t/t9902-completion.sh b/t/t9902-completion.sh
index b752f4d..6d9d141 100755
--- a/t/t9902-completion.sh
+++ b/t/t9902-completion.sh

@@ -165,7 +165,7 @@ test_expect_success '__gitcomp - suffix' '
 	EOF
 '
 
-test_expect_failure '__gitcomp - doesnt fail because of invalid variable name' '
+test_expect_success '__gitcomp - doesnt fail because of invalid variable name' '
 	__gitcomp "$invalid_variable_name"
 '
 

@@ -204,7 +204,7 @@ test_expect_success '__gitcomp_nl - no suffix' '
 	EOF
 '
 
-test_expect_failure '__gitcomp_nl - doesnt fail because of invalid variable name' '
+test_expect_success '__gitcomp_nl - doesnt fail because of invalid variable name' '
 	__gitcomp_nl "$invalid_variable_name"
 '
 

@@ -332,7 +332,7 @@ test_expect_success 'complete tree filename with spaces' '
 	EOF
 '
 
-test_expect_failure 'complete tree filename with metacharacters' '
+test_expect_success 'complete tree filename with metacharacters' '
 	echo content >"name with \${meta}" &&
 	git add . &&
 	git commit -m meta &&

-- 
1.8.2.1

There's no point in calling a separate function that is only used in one
place. Specially considering that there's no need to call compgen, and
we traverse the words ourselves both in __gitcompadd, and __gitcomp_1.

So lets squash the functions together, and traverse only once.

This improves performance. For N number of words:

  == 1 ==
  original: 0.002s
  new: 0.000s
  == 10 ==
  original: 0.005s
  new: 0.001s
  == 100 ==
  original: 0.009s
  new: 0.006s
  == 1000 ==
  original: 0.027s
  new: 0.019s
  == 10000 ==
  original: 0.163s
  new: 0.151s
  == 100000 ==
  original: 1.555s
  new: 1.497s

No functional changes.

Signed-off-by: Felipe Contreras <redacted>
---
 contrib/completion/git-completion.bash | 26 +++++++++++---------------
 1 file changed, 11 insertions(+), 15 deletions(-)

diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash
index d8009f5..301de15 100644
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash

@@ -53,19 +53,6 @@ __gitdir ()
 	fi
 }
 
-__gitcomp_1 ()
-{
-	local c IFS=$' \t\n'
-	for c in $1; do
-		c="$c$2"
-		case $c in
-		--*=*|*.) ;;
-		*) c="$c " ;;
-		esac
-		printf '%s\n' "$c"
-	done
-}
-
 # The following function is based on code from:
 #
 #   bash_completion - programmable completion functions for bash 3.2+

@@ -220,8 +207,17 @@ __gitcomp ()
 	--*=)
 		;;
 	*)
-		local IFS=$'\n'
-		__gitcompadd "$(__gitcomp_1 "${1-}" "${4-}")" "${2-}" "$cur_" ""
+		local c i=0 IFS=$' \t\n'
+		for c in $1; do
+			c="$c${4-}"
+			case $c in
+			--*=*|*.) ;;
+			*) c="$c " ;;
+			esac
+			if [[ $c == "$cur_"* ]]; then
+				COMPREPLY[i++]="${2-}$c"
+			fi
+		done
 		;;
 	esac
 }

-- 
1.8.2.1

No need to calculate a new $c with a space if we are not going to do
anything it with it.

There should be no functional changes, except that a word "foo " with no
suffixes can't be matched. But $cur cannot have a space at the end
anyway. So it's safe.

Based on the code from SZEDER Gábor.

Signed-off-by: Felipe Contreras <redacted>
---
 contrib/completion/git-completion.bash | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash
index 301de15..1666213 100644
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash

@@ -210,11 +210,11 @@ __gitcomp ()
 		local c i=0 IFS=$' \t\n'
 		for c in $1; do
 			c="$c${4-}"
-			case $c in
-			--*=*|*.) ;;
-			*) c="$c " ;;
-			esac
 			if [[ $c == "$cur_"* ]]; then
+				case $c in
+				--*=*|*.) ;;
+				*) c="$c " ;;
+				esac
 				COMPREPLY[i++]="${2-}$c"
 			fi
 		done

-- 
1.8.2.1

On Wed, Apr 10, 2013 at 2:57 AM, Felipe Contreras
[off-list ref] wrote:

There's no functional reason for those, the only purpose they are
supposed to serve is to say "we don't provide any words here", but even
for that it's not used consitently.

s/consitently/consistently/

Signed-off-by: Felipe Contreras <redacted>

On Wed, Apr 10, 2013 at 2:57 AM, Felipe Contreras
[off-list ref] wrote:

The functionality we use from compgen is not much, we can do the same
manually, with drastical improvements in speed, specially when dealing

s/drastical/drastic/
s/specially/especially/

with only a few words.

This patch also has the sideffect that brekage reported by Jeroen Meijer

s/sideffect/side effect/
s/brekage/breakage/

and SZEDER Gábor gets fixed because we no longer expand the resulting
words.

So, unless 'git checkout <tab>' usually gives you more than 100000
results, you'll get an improvement :)

Other possible solutions perform better after 1000 words, but worst if

s/worst/worse/

less than that:

  COMPREPLY=($(awk -v cur="$3" -v pre="$2" -v suf="$4"
        '$0 ~ cur { print pre$0suf }' <<< "$1" ))

  COMPREPLY=($(printf -- "$2%s$4\n" $1 | grep "^$2$3"))

Signed-off-by: Felipe Contreras <redacted>

On Wed, Apr 10, 2013 at 2:57 AM, Felipe Contreras
[off-list ref] wrote:

There's no point in calling a separate function that is only used in one
place. Specially considering that there's no need to call compgen, and

s/Specially/Especially/

we traverse the words ourselves both in __gitcompadd, and __gitcomp_1.

s/ourselves/ourself/

So lets squash the functions together, and traverse only once.

s/lets/let's/

This improves performance. For N number of words:

  == 1 ==
  original: 0.002s
  new: 0.000s
  == 10 ==
  original: 0.005s
  new: 0.001s
  == 100 ==
  original: 0.009s
  new: 0.006s
  == 1000 ==
  original: 0.027s
  new: 0.019s
  == 10000 ==
  original: 0.163s
  new: 0.151s
  == 100000 ==
  original: 1.555s
  new: 1.497s

No functional changes.

Signed-off-by: Felipe Contreras <redacted>

On Wed, Apr 10, 2013 at 5:10 AM, Eric Sunshine [off-list ref] wrote:

s/specially/especially/

http://www.merriam-webster.com/dictionary/specially

--
Felipe Contreras

On Wed, Apr 10, 2013 at 06:07:33AM -0500, Felipe Contreras wrote:

On Wed, Apr 10, 2013 at 5:10 AM, Eric Sunshine [off-list ref] wrote:

quoted

s/specially/especially/

http://www.merriam-webster.com/dictionary/specially

But see also:

    http://www.merriam-webster.com/dictionary/especially

which notes "in particular" as a synonym, which is what makes it more
natural in the case under discussion here.

On Wed, Apr 10, 2013 at 06:13:06AM -0400, Eric Sunshine wrote:

On Wed, Apr 10, 2013 at 2:57 AM, Felipe Contreras
[off-list ref] wrote:

quoted

we traverse the words ourselves both in __gitcompadd, and __gitcomp_1.

s/ourselves/ourself/

Huh?  "we traverse ... ourselves" is correct since "ourselves" is
associated with the "we".  I don't think "ourself" is ever correct in
normal usage - the dictionary notes that it applies only to the "royal
we".

On Wed, Apr 10, 2013 at 7:35 AM, John Keeping [off-list ref] wrote:

On Wed, Apr 10, 2013 at 06:13:06AM -0400, Eric Sunshine wrote:

quoted

On Wed, Apr 10, 2013 at 2:57 AM, Felipe Contreras
[off-list ref] wrote:

quoted

we traverse the words ourselves both in __gitcompadd, and __gitcomp_1.

s/ourselves/ourself/

Huh?  "we traverse ... ourselves" is correct since "ourselves" is
associated with the "we".  I don't think "ourself" is ever correct in
normal usage - the dictionary notes that it applies only to the "royal
we".

Late-night lapse. Thanks for the correction.