[PATCH] Completion must sort before using uniq

[PATCH] Completion must sort before using uniq

[Marc Khouzam]

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(-)

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

Re: [PATCH] Completion must sort before using uniq

[Joachim Schmitz]

Marc Khouzam wrote:
> The uniq program only works with sorted input.  The man page states
> "uniq prints the unique lines in a sorted file".
...
> --- 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 

Re: [PATCH] Completion must sort before using uniq

[Felipe Contreras]

On Thu, Nov 22, 2012 at 5:16 AM, Marc Khouzam <marc.khouzam@gmail.com> wrote:
> 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

[PATCH v2] Completion must sort before using uniq

[Marc Khouzam]

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>
---

>> 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(-)

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

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

[Felipe Contreras]

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

>   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).

> 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.

> 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.

> 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

[PATCH v3] Completion must sort before using uniq

[Marc Khouzam]

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(-)

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

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

[Felipe Contreras]

On Fri, Nov 23, 2012 at 3:02 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.
>
> 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

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

[Junio C Hamano]

Marc Khouzam <marc.khouzam@gmail.com> writes:

> 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.

RE: [PATCH] Completion must sort before using uniq

[Joachim Schmitz]

Re-adding git@vger...

> From: Marc Khouzam [mailto:marc.khouzam@gmail.com]
> Sent: Friday, November 23, 2012 11:51 AM
> To: Joachim Schmitz
> Cc: szeder@ira.uka.de; felipe.contreras@gmail.com
> Subject: Re: [PATCH] Completion must sort before using uniq
> 
> On Fri, Nov 23, 2012 at 3:10 AM, Joachim Schmitz
> <jojo@schmitz-digital.de> wrote:
> > Marc Khouzam wrote:
> >> The uniq program only works with sorted input.  The man page states
> >> "uniq prints the unique lines in a sorted file".
> > ...
> >> --- 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
> 
> "-u Unique: suppress all but one in each set of lines having equal
> keys. If used with the -c option, check that there are no lines with
> duplicate keys, in addition to checking that the input file is
> sorted."
> 
> What the code aims to do is to only show lines that are not
> duplicated.  'sort -u' would still output one line for each duplicated
> one.  It seems 'sort -u' is the equivalent of 'sort | uniq' but won't
> replace 'sort | uniq -u'.

I can't see the difference and in fact don't understand uniq's -u option al all
Linux man pages say: "only print unique lines", but that is what uniq does by default anyway?!?

> Is 'sort | uniq -u' not POSIX?

It is. It is one process more though.

Bye, Jojo

Re: [PATCH] Completion must sort before using uniq

[Sascha Cunz]

> I can't see the difference and in fact don't understand uniq's -u option al
> all Linux man pages say: "only print unique lines", but that is what uniq
> does by default anyway?!?

>From the german translation of uniq's man-page, you can deduct that "only 
print unique lines" actually means: "print lines that are _not repeated_ in 
the input".

A short test confirms that. i.e.:

	printf "a\nb\nb\nc\n" | uniq -u

gives:
	a
	c

Sascha

RE: [PATCH] Completion must sort before using uniq

[Joachim Schmitz]

> From: Sascha Cunz [mailto:sascha-ml@babbelbox.org]
> Sent: Friday, November 23, 2012 1:26 PM
> To: Joachim Schmitz
> Cc: 'Marc Khouzam'; git@vger.kernel.org; szeder@ira.uka.de; felipe.contreras@gmail.com
> Subject: Re: [PATCH] Completion must sort before using uniq
> 
> > I can't see the difference and in fact don't understand uniq's -u option al
> > all Linux man pages say: "only print unique lines", but that is what uniq
> > does by default anyway?!?
> 
> From the german translation of uniq's man-page, you can deduct that "only
> print unique lines" actually means: "print lines that are _not repeated_ in
> the input".
> 
> A short test confirms that. i.e.:
> 
> 	printf "a\nb\nb\nc\n" | uniq -u
> 
> gives:
> 	a
> 	c

Ah, OK, then I rest my case. Sorry for the noise.