threads / patch / 32167

patchCompletion must sort before using uniq

Subject: [PATCH] Completion must sort before using uniq

## tl;dr

8 messages between Nov 22, 2012 and Nov 25, 2012. Diffs are folded; open one to read it.

replies: 7people: 4as markdown or json

Marc Khouzam· Nov 22, 2012, 04:16 UTC · lore

The uniq program only works with sorted input. The man page states "uniq prints the unique lines in a sorted file".

When __git_refs use the guess heuristic employed by checkout for tracking branches it wants to consider remote branches but only if the branch name is unique. To do that, it calls 'uniq -u'. However the input given to 'uniq -u' is not sorted.

For example if all available branches are:
  master
  remotes/GitHub/maint
  remotes/GitHub/master
  remotes/origin/maint
  remotes/origin/master
When performing completion on 'git checkout ma' the choices given are
  maint
  master
but when performing completion on 'git checkout mai', no choices
appear, which is obviously contradictory.
The reason is that, when dealing with 'git checkout ma',
"__git_refs '' 1" will find the following list:
  master
  maint
  master
  maint
  master
which, when passed to 'uniq -u' will remain the same.
But when dealing with 'git checkout mai', the list will be:
  maint
  maint
which happens to be sorted and will be emptied by 'uniq -u'.
The solution is to first call 'sort' and then 'uniq -u'.
Signed-off-by: Marc Khouzam <marc.khouzam@gmail.com>
---
I ran into this by fluke when testing the tcsh completion.
Thanks for considering the fix.
Marc
 contrib/completion/git-completion.bash | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
Show changes to contrib/completion/git-completion.bash +1 −2
diff --git a/contrib/completion/git-completion.bash
b/contrib/completion/git-completion.bash
index bc0657a..85ae419 100644
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash
@@ -321,7 +321,7 @@ __git_refs ()
                                if [[ "$ref" == "$cur"* ]]; then
                                        echo "$ref"
                                fi
-                       done | uniq -u
+                       done | sort | uniq -u
                fi
                return
        fi
--
1.8.0.1.g9fe2839
Joachim Schmitz· Nov 23, 2012, 08:09 UTC · re: Marc Khouzam · lore

Re: [PATCH] Completion must sort before using uniq

Marc Khouzam wrote:
> The uniq program only works with sorted input.  The man page states
> "uniq prints the unique lines in a sorted file".
...
Show 8 quoted lines
> --- a/contrib/completion/git-completion.bash
> +++ b/contrib/completion/git-completion.bash
> @@ -321,7 +321,7 @@ __git_refs ()
>                                if [[ "$ref" == "$cur"* ]]; then
>                                        echo "$ref"
>                                fi
> -                       done | uniq -u
> +                       done | sort | uniq -u

Is 'sort -u' not universally available and sufficient here? It is POSIX at least: http://pubs.opengroup.org/onlinepubs/9699919799/utilities/sort.html

Bye, Jojo
Felipe Contreras· Nov 23, 2012, 08:21 UTC · re: Marc Khouzam · lore

Re: [PATCH] Completion must sort before using uniq

On Thu, Nov 22, 2012 at 5:16 AM, Marc Khouzam <marc.khouzam@gmail.com> wrote:
Show 35 quoted lines
> The uniq program only works with sorted input.  The man page states
> "uniq prints the unique lines in a sorted file".
>
> When __git_refs use the guess heuristic employed by checkout for
> tracking branches it wants to consider remote branches but only if
> the branch name is unique.  To do that, it calls 'uniq -u'.  However
> the input given to 'uniq -u' is not sorted.
>
> For example if all available branches are:
>   master
>   remotes/GitHub/maint
>   remotes/GitHub/master
>   remotes/origin/maint
>   remotes/origin/master
>
> When performing completion on 'git checkout ma' the choices given are
>   maint
>   master
> but when performing completion on 'git checkout mai', no choices
> appear, which is obviously contradictory.
>
> The reason is that, when dealing with 'git checkout ma',
> "__git_refs '' 1" will find the following list:
>   master
>   maint
>   master
>   maint
>   master
> which, when passed to 'uniq -u' will remain the same.
> But when dealing with 'git checkout mai', the list will be:
>   maint
>   maint
> which happens to be sorted and will be emptied by 'uniq -u'.
>
> The solution is to first call 'sort' and then 'uniq -u'.

The solution to what? This seems to be the right thing indeed, but you don't explain what is the actual problem that is being solved. What does the user experience? What would (s)he experience after the patch?

-- 
Felipe Contreras
Marc Khouzam· Nov 23, 2012, 11:17 UTC · re: Felipe Contreras · lore

[PATCH v2] Completion must sort before using uniq

The user can be presented with invalid completion results
when trying to complete a 'git checkout' command.  This can happen
when using a branch name prefix that matches multiple remote branches.
For example if available branches are:
  master
  remotes/GitHub/maint
  remotes/GitHub/master
  remotes/origin/maint
  remotes/origin/master
When performing completion on 'git checkout ma' the user will be
given the choices:
  maint
  master
However, 'git checkout maint' will fail in this case, although
completion previously said 'maint' was valid.
Furthermore, when performing completion on 'git checkout mai',
no choices will be suggested.  So, the user is first told that the
branch name 'maint' is valid, but when trying to complete 'mai'
into 'maint', that completion is no longer valid.

The completion results should never propose 'maint' as a valid branch name, since 'git checkout' will refuse it.

The reason for this bug is that the uniq program only works with sorted input. The man page states "uniq prints the unique lines in a sorted file".

When __git_refs uses the guess heuristic employed by checkout for tracking branches it wants to consider remote branches but only if the branch name is unique. To do that, it calls 'uniq -u'. However the input given to 'uniq -u' is not sorted.

Therefore, in the above example, when dealing with 'git checkout ma',
"__git_refs '' 1" will find the following list:
  master
  maint
  master
  maint
  master
which, when passed to 'uniq -u' will remain the same.  Therefore
'maint' will be wrongly suggested as a valid option.
When dealing with 'git checkout mai', the list will be:
  maint
  maint
which happens to be sorted and will be emptied by 'uniq -u',
properly ignoring 'maint'.

A solution for preventing the completion script from suggesting such invalid branch names is to first call 'sort' and then 'uniq -u'.

Signed-off-by: Marc Khouzam <marc.khouzam@gmail.com>
---
Show 5 quoted lines
>> The solution is to first call 'sort' and then 'uniq -u'.
>
> The solution to what? This seems to be the right thing indeed, but you
> don't explain what is the actual problem that is being solved. What
> does the user experience? What would (s)he experience after the patch?

I have re-worked the commit message to be more clear about the user impacts.

Thanks for the feedback.
Marc
 contrib/completion/git-completion.bash | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
Show changes to contrib/completion/git-completion.bash +1 −1
diff --git a/contrib/completion/git-completion.bash
b/contrib/completion/git-completion.bash
index bc0657a..85ae419 100644
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash
@@ -321,7 +321,7 @@ __git_refs ()
                                if [[ "$ref" == "$cur"* ]]; then
                                        echo "$ref"
                                fi
-                       done | uniq -u
+                       done | sort | uniq -u
                fi
                return
        fi

-- 
1.8.0.1.g9fe2839
Felipe Contreras· Nov 23, 2012, 11:34 UTC · re: Marc Khouzam · lore

Re: [PATCH v2] Completion must sort before using uniq

Hi,
Mostly cosmetic suggestions, but it looks OK to me.
On Fri, Nov 23, 2012 at 12:17 PM, Marc Khouzam <marc.khouzam@gmail.com> wrote:
> The user can be presented with invalid completion results
> when trying to complete a 'git checkout' command.  This can happen
> when using a branch name prefix that matches multiple remote branches.
Space here.
> For example if available branches are:
For example; <- separation
Show 10 quoted lines
>   master
>   remotes/GitHub/maint
>   remotes/GitHub/master
>   remotes/origin/maint
>   remotes/origin/master
>
> When performing completion on 'git checkout ma' the user will be
> given the choices:
>   maint
>   master
Space.
> However, 'git checkout maint' will fail in this case, although
> completion previously said 'maint' was valid.
Space (or continue paragraph).
Show 7 quoted lines
> Furthermore, when performing completion on 'git checkout mai',
> no choices will be suggested.  So, the user is first told that the
> branch name 'maint' is valid, but when trying to complete 'mai'
> into 'maint', that completion is no longer valid.
>
> The completion results should never propose 'maint' as a valid
> branch name, since 'git checkout' will refuse it.
With this explanation the patch looks good to me.
Show 16 quoted lines
> The reason for this bug is that the uniq program only
> works with sorted input.  The man page states
> "uniq prints the unique lines in a sorted file".
>
> When __git_refs uses the guess heuristic employed by checkout for
> tracking branches it wants to consider remote branches but only if
> the branch name is unique.  To do that, it calls 'uniq -u'.  However
> the input given to 'uniq -u' is not sorted.
>
> Therefore, in the above example, when dealing with 'git checkout ma',
> "__git_refs '' 1" will find the following list:
>   master
>   maint
>   master
>   maint
>   master
Space.
> which, when passed to 'uniq -u' will remain the same.  Therefore
> 'maint' will be wrongly suggested as a valid option.
Space.
> When dealing with 'git checkout mai', the list will be:
>   maint
>   maint
Space.
Show 5 quoted lines
> which happens to be sorted and will be emptied by 'uniq -u',
> properly ignoring 'maint'.
>
> A solution for preventing the completion script from suggesting
> such invalid branch names is to first call 'sort' and then 'uniq -u'.
Cheers.
-- 
Felipe Contreras
Marc Khouzam· Nov 23, 2012, 14:02 UTC · re: Felipe Contreras · lore

[PATCH v3] Completion must sort before using uniq

The user can be presented with invalid completion results when trying to complete a 'git checkout' command. This can happen when using a branch name prefix that matches multiple remote branches.

For example, if available branches are:
  master
  remotes/GitHub/maint
  remotes/GitHub/master
  remotes/origin/maint
  remotes/origin/master
When performing completion on 'git checkout ma' the user will be
given the choices:
  maint
  master

However, 'git checkout maint' will fail in this case, although completion previously said 'maint' was valid. Furthermore, when performing completion on 'git checkout mai', no choices will be suggested. So, the user is first told that the branch name 'maint' is valid, but when trying to complete 'mai' into 'maint', that completion is no longer valid.

The completion results should never propose 'maint' as a valid branch name, since 'git checkout' will refuse it.

The reason for this bug is that the uniq program only works with sorted input. The man page states "uniq prints the unique lines in a sorted file".

When __git_refs uses the guess heuristic employed by checkout for tracking branches it wants to consider remote branches but only if the branch name is unique. To do that, it calls 'uniq -u'. However the input given to 'uniq -u' is not sorted.

Therefore, in the above example, when dealing with 'git checkout ma',
"__git_refs '' 1" will find the following list:
  master
  maint
  master
  maint
  master

which, when passed to 'uniq -u' will remain the same. Therefore 'maint' will be wrongly suggested as a valid option.

When dealing with 'git checkout mai', the list will be:
  maint
  maint

which happens to be sorted and will be emptied by 'uniq -u', properly ignoring 'maint'.

A solution for preventing the completion script from suggesting such invalid branch names is to first call 'sort' and then 'uniq -u'.

Signed-off-by: Marc Khouzam <marc.khouzam@gmail.com>
---
> Mostly cosmetic suggestions, but it looks OK to me.
Thanks for the suggestions, I updated the commit message.
> With this explanation the patch looks good to me.
Thanks for the quick review.
Marc
 contrib/completion/git-completion.bash | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
Show changes to contrib/completion/git-completion.bash +1 −2
diff --git a/contrib/completion/git-completion.bash
b/contrib/completion/git-completion.bash
index bc0657a..85ae419 100644
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash
@@ -321,7 +321,7 @@ __git_refs ()
                                if [[ "$ref" == "$cur"* ]]; then
                                        echo "$ref"
                                fi
-                       done | uniq -u
+                       done | sort | uniq -u
                fi
                return
        fi
--
1.8.0.1.g9fe2839
Felipe Contreras· Nov 23, 2012, 19:21 UTC · re: Marc Khouzam · lore

Re: [PATCH v3] Completion must sort before using uniq

On Fri, Nov 23, 2012 at 3:02 PM, Marc Khouzam <marc.khouzam@gmail.com> wrote:
Show 57 quoted lines
> The user can be presented with invalid completion results
> when trying to complete a 'git checkout' command.  This can happen
> when using a branch name prefix that matches multiple remote branches.
>
> For example, if available branches are:
>   master
>   remotes/GitHub/maint
>   remotes/GitHub/master
>   remotes/origin/maint
>   remotes/origin/master
>
> When performing completion on 'git checkout ma' the user will be
> given the choices:
>   maint
>   master
>
> However, 'git checkout maint' will fail in this case, although
> completion previously said 'maint' was valid.  Furthermore, when
> performing completion on 'git checkout mai', no choices will be
> suggested.  So, the user is first told that the branch name
> 'maint' is valid, but when trying to complete 'mai' into 'maint',
> that completion is no longer valid.
>
> The completion results should never propose 'maint' as a valid
> branch name, since 'git checkout' will refuse it.
>
> The reason for this bug is that the uniq program only
> works with sorted input.  The man page states
> "uniq prints the unique lines in a sorted file".
>
> When __git_refs uses the guess heuristic employed by checkout for
> tracking branches it wants to consider remote branches but only if
> the branch name is unique.  To do that, it calls 'uniq -u'.  However
> the input given to 'uniq -u' is not sorted.
>
> Therefore, in the above example, when dealing with 'git checkout ma',
> "__git_refs '' 1" will find the following list:
>   master
>   maint
>   master
>   maint
>   master
>
> which, when passed to 'uniq -u' will remain the same.  Therefore
> 'maint' will be wrongly suggested as a valid option.
>
> When dealing with 'git checkout mai', the list will be:
>   maint
>   maint
>
> which happens to be sorted and will be emptied by 'uniq -u',
> properly ignoring 'maint'.
>
> A solution for preventing the completion script from suggesting
> such invalid branch names is to first call 'sort' and then 'uniq -u'.
>
> Signed-off-by: Marc Khouzam <marc.khouzam@gmail.com>
Looks good. Reviewed-by: Felipe Contreras <felipe.contreras@gmail.com>
-- 
Felipe Contreras
Junio C Hamano· Nov 25, 2012, 06:32 UTC · re: Marc Khouzam · lore

Re: [PATCH v3] Completion must sort before using uniq

Marc Khouzam <marc.khouzam@gmail.com> writes:
Show 19 quoted lines
> The user can be presented with invalid completion results
> when trying to complete a 'git checkout' command.  This can happen
> when using a branch name prefix that matches multiple remote branches.
>
> For example, if available branches are:
>   master
>   remotes/GitHub/maint
>   remotes/GitHub/master
>   remotes/origin/maint
>   remotes/origin/master
>
> When performing completion on 'git checkout ma' the user will be
> given the choices:
>   maint
>   master
> ...
> When dealing with 'git checkout mai', the list will be:
>   maint
>   maint

Wow, the description feels a tad repetitive for a one liner (it describes "uniq -u" without pre-sort is wrong at least three times), it would be better than no log message ;-)

I originally thought "uniq -u" was a misspelled "sort -u" when I first saw your shorter version, but reading the code to see what is fed to the command made it immediately obvious "sort | uniq -u" is the right fix. With the above explanation, you do not even need to read the code to see what is fed to the command (it is explained ;-).

So, thanks for the fix.

← back to recent threads