help.autocorrect: do not run a command if the command given is junk
PATCH 1/1 help.autocorrect: do not run a command if the command given is junk
From: Johannes Sixt <[email protected]>
If a given command is not found, then help.c tries to guess which one the user could have meant. If help.autocorrect is 0 or unset, then a list of suggestions is given as long as the dissimilarity between the given command and the candidates is not excessively high. But if help.autocorrect was non-zero (i.e., a delay after which the command is run automatically), the latter restriction on dissimilarity was not obeyed.
In my case, this happened:
$ git ..daab02 WARNING: You called a Git command named '..daab02', which does not exist. Continuing under the assumption that you meant 'read-tree' in 4.0 seconds automatically...
The similarity limit that this patch introduces is already used a few lines later where the list of suggested commands is printed.
--- help.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-)
help.c +1 -1
@@ -331,7 +331,7 @@ const char *help_unknown_cmd(const char *cmd) n =1 ;while (n < main_cmds.cnt && best_similarity == main_cmds.names[n]->len) ++n; -if (autocorrect && n ==1 ) { +if (autocorrect && n ==1 && best_similarity <6 ) {const char *assumed = main_cmds.names[0 ]->name; main_cmds.names[0 ] =NULL ;clean_cmdnames (&main_cmds);
Signature · 1 line
1.6.6.rc1.46.g1635
Quoted 16 lines · Johannes Sixt
From: Johannes Sixt <[email protected]>
If a given command is not found, then
help.ctries to guess which one the user could have meant. If help.autocorrect is 0 or unset, then a list of suggestions is given as long as the dissimilarity between the given command and the candidates is not excessively high. But if help.autocorrect was non-zero (i.e., a delay after which the command is run automatically), the latter restriction on dissimilarity was not obeyed.In my case, this happened:
$ git ..daab02 WARNING: You called a Git command named '..daab02', which does not exist. Continuing under the assumption that you meant 'read-tree' in 4.0 seconds automatically...
Quoted 7 lines
The similarity limit that this patch introduces is already used a few lines later where the list of suggested commands is printed.
Signed-off-by Johannes Sixt <[email protected]>--- help.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-)
Thanks. Will apply to 'maint'.
But I am curious about and would prefer to see the story behind '6' someday.
This is not entirely a new problem that you are introducing, as the same comparison-with-six appears in a later part of the code, but this patch duplicates the magic number whose two instances need to match, so in that sense it makes it more necessary than before to document the choice of magic number somewhere in a comment in the code.
Did 8af84da (git wrapper: DWIM mistyped commands, 2008-08-31) made up just a random number out of thin-air? What bad things would happen if we used '600' (or '1') instead of '6'? What kind of correlation does the cut-off value we use here should have with some intrinsic numbers your git installation has (e.g. perhaps "must be at least 80% of average length of available commands" or something like that)?
In the meantime, I think squashing the following in would help us keep the two magic numbers in sync.
help.c +5 -2
@@ -297,6 +297,9 @@ static void add_cmd_list(struct cmdnames *cmds, struct cmdnames *old) old->names =NULL ; } +/* how did we decide this is a good cutoff??? */ +#define SIMILAR_ENOUGH (x) ((x) < 6) +const char *help_unknown_cmd (const char *cmd) {int i, n, best_similarity =0 ;
@@ -331,7 +334,7 @@ const char *help_unknown_cmd(const char *cmd) n =1 ;while (n < main_cmds.cnt && best_similarity == main_cmds.names[n]->len) ++n; -if (autocorrect && n ==1 && best_similarity <6 ) { +if (autocorrect && n ==1 &&SIMILAR_ENOUGH (best_similarity)) {const char *assumed = main_cmds.names[0 ]->name; main_cmds.names[0 ] =NULL ;clean_cmdnames (&main_cmds);
@@ -349,7 +352,7 @@ const char *help_unknown_cmd(const char *cmd)fprintf (stderr,"git: '%s' is not a git-command. See 'git --help'.\n" , cmd); -if (best_similarity <6 ) { +if (SIMILAR_ENOUGH (best_similarity)) {fprintf (stderr,"\nDid you mean %s?\n" , n <2 ?"this" :"one of these" );
Quoted 2 lines · Junio C Hamano
In the meantime, I think squashing the following in would help us keep the two magic numbers in sync.
I do not think that keeping the numbers in sync is necessary. For example, the similarity requirement for commands that run automatically could be stricter than for the list of suggestions. Then it would be possible that a unique best candidate is not good enough to be run automatically; there would only be a list of suggestions.
-- Hannes
Quoted 9 lines · Johannes Sixt
Quoted 2 lines · Junio C Hamano
In the meantime, I think squashing the following in would help us keep the two magic numbers in sync.
I do not think that keeping the numbers in sync is necessary. For example, the similarity requirement for commands that run automatically could be stricter than for the list of suggestions. Then it would be possible that a unique best candidate is not good enough to be run automatically; there would only be a list of suggestions.
Well thought out. Would you want to reroll a patch with two symbolic constants then?
Quoted 5 lines · Junio C Hamano
Quoted 3 lines · Johannes Sixt
Quoted 2 lines · Junio C Hamano
In the meantime, I think squashing the following in would help us keep the two magic numbers in sync.
Quoted 8 lines
Quoted 5 lines
I do not think that keeping the numbers in sync is necessary. For example, the similarity requirement for commands that run automatically could be stricter than for the list of suggestions. Then it would be possible that a unique best candidate is not good enough to be run automatically; there would only be a list of suggestions.
Well thought out. Would you want to reroll a patch with two symbolic constants then?
I briefly looked into it, but, no, I don't want to reroll the patch. Not only would the change be larger than I first thought, but I would also have to find a mis-typed command where a stricter limit makes a difference *and* where it makes sense that the guessed command is not run automatically. Moreover, I would also have to *find* a suitable new similarity limit. Not something I want to do now.
Please take my original patch and squash in your suggested changes. Here it is for your convenience with an updated commit message (only the last paragraph changed).
-- Hannes
--- 8< ---
From: Johannes Sixt <[email protected]>
Subject: [PATCH] help.autocorrect: do not run a command if the command given is junk
If a given command is not found, then help.c tries to guess which one the user could have meant. If help.autocorrect is 0 or unset, then a list of suggestions is given as long as the dissimilarity between the given command and the candidates is not excessively high. But if help.autocorrect was non-zero (i.e., a delay after which the command is run automatically), the latter restriction on dissimilarity was not obeyed.
In my case, this happened:
$ git ..daab02 WARNING: You called a Git command named '..daab02', which does not exist. Continuing under the assumption that you meant 'read-tree' in 4.0 seconds automatically...
The patch reuses the similarity limit that is also applied when the list of suggested commands is printed.
--- help.c | 7 +++++-- 1 files changed, 5 insertions(+), 2 deletions(-)
help.c +5 -2
@@ -297,6 +297,9 @@ static void add_cmd_list(struct cmdnames *cmds, struct cmdnames *old) old->names =NULL ; } +/* An empirically derived magic number */ +#define SIMILAR_ENOUGH (x) ((x) < 6) +const char *help_unknown_cmd (const char *cmd) {int i, n, best_similarity =0 ;
@@ -331,7 +334,7 @@ const char *help_unknown_cmd(const char *cmd) n =1 ;while (n < main_cmds.cnt && best_similarity == main_cmds.names[n]->len) ++n; -if (autocorrect && n ==1 ) { +if (autocorrect && n ==1 &&SIMILAR_ENOUGH (best_similarity)) {const char *assumed = main_cmds.names[0 ]->name; main_cmds.names[0 ] =NULL ;clean_cmdnames (&main_cmds);
@@ -349,7 +352,7 @@ const char *help_unknown_cmd(const char *cmd)fprintf (stderr,"git: '%s' is not a git-command. See 'git --help'.\n" , cmd); -if (best_similarity <6 ) { +if (SIMILAR_ENOUGH (best_similarity)) {fprintf (stderr,"\nDid you mean %s?\n" , n <2 ?"this" :"one of these" );
Signature · 1 line
1.6.6.rc1.46.g1635
Hi,
Quoted 1 line · Junio C Hamano
I am curious about and would prefer to see the story behind '6' someday.
The '6' as a cut-off to the levenshtein distances we list when autocorrecting was derived in a totally scientific manner:
1) first I implemented Levenshtein-Damerau with a configurable weight of neighbor flips ("switches"), substitutions, additions and deletions,
2) next I patched the code to sort the availablecommands by their distance to the mispelt command,
3) as this lists way too much, I implemented a cut-off that was configurable by an environment variable (without any safety checks, as I did not plan to release that code anyway),
4) now comes the totally, unbelievably cunningly scientific part: I did a self-experiment! I deliberately mispelt commands in a totally random manner!
5) then I changed the code to actually output the distances so I could determine a cut-off that makes sense with my type of tyops,
6) after about 15 tries of deliberate mistakes (mostly doing what I usually do, something like "git pull" and "git log" or something like that, but watching TV, chatting on the phone _and_ cleaning the dishes at the same time), I found that 5 was too low and 7 too large.
The number '6' happily coincided with the number of steps I needed to come up with the number. You see? The _perfect_ way to determine a completely arbitrary number.
Actually, you probably see that I just made up that number and tested a few times, and it seemed to work reasonably well.
FWIW almost the same procedure led to the weights 0, 2, 1 and 4 that you see in help.c. The weights are basically factors with which mistakes are
punished: if you just confuse two adjacent letters, such as "psuh" instead of "push" (which can be quite common if you use two hands, one on the left side, and one on the right side of the keyboard, with an en-US layout so many of us use, myself included) it costs 0.
If you write a different character than what you intended, the cost is 2. The idea behind it is that you're more likely to miss a key than to hit the wrong key. With the laptop I am typing this email on, it is particularly likely that I miss a key, because there are certain key combinations where only the first key triggers an input event, but the second only triggers an input event when it is _released_ after the first one. So when I type "er" real fast and happen to release the "e" key after the "r" key, no "r" appears on my screen.
Okay, so the weight for adding a character must be smaller than substituting a character, but why is the cost for deletion so high? Well, I really rarely type unnecessary characters (except when writing to the Git mailing list, arguably) so those costs must be substantially higher than for typing the wrong character.
My original plan was to log all my tyops into a log file and analyze those errors later, but then my initial 0, 2, 1, 4 and 6 constants worked well enough for me that I did not bother.
Satisfied?
Ciao,
Dscho
Quoted 1 line · Johannes Schindelin
Satisfied?
Very much.
FWIW almost the same procedure led to the weights 0, 2, 1 and 4 that you see in help.c. The weights are basically factors with which mistakes are
punished: if you just confuse two adjacent letters, such as "psuh" instead of "push" (which can be quite common if you use two hands, one on the left side, and one on the right side of the keyboard, with an en-US layout so many of us use, myself included) it costs 0.
If you write a different character than what you intended, the cost is 2. The idea behind it is that you're more likely to miss a key than to hit the wrong key. With the laptop I am typing this email on, it is particularly likely that I miss a key, because there are certain key combinations where only the first key triggers an input event, but the second only triggers an input event when it is _released_ after the first one. So when I type "er" real fast and happen to release the "e" key after the "r" key, no "r" appears on my screen.
Okay, so the weight for adding a character must be smaller than substituting a character, but why is the cost for deletion so high? Well, I really rarely type unnecessary characters (except when writing to the Git mailing list, arguably) so those costs must be substantially higher than for typing the wrong character.
These are actually very good justifications in the sense that people who might want to tweak the heuristics can see the reason behind the current choice and agree or disagree with it.
I somehow suspect that a good mathematician can come up with a rationale for 6 after the fact that sounds convincing, along the lines of "the average length of commands being N, and levenshtein penalties being <0,2,1,4>, you can insert X mistaken keystroke and/or omit Y mistaken keystroke per every correct keystroke without exceeding this value 6, and the percentage X and/or Y represents is not too low to be practical but low enough to reject false positives".
In any case, I'll further squash in the following. Thanks for an amusing explanation ;-).
help.c +1 -1
@@ -297,7 +297,7 @@ static void add_cmd_list(struct cmdnames *cmds, struct cmdnames *old) old->names =NULL ; } -/* how did we decide this is a good cutoff??? */ +/* An empirically derived magic number */ #define SIMILAR_ENOUGH (x) ((x) < 6)const char *help_unknown_cmd (const char *cmd)
Hi,
Quoted 7 lines · Junio C Hamano
I somehow suspect that a good mathematician can come up with a rationale for 6 after the fact that sounds convincing, along the lines of "the average length of commands being N, and levenshtein penalties being <0,2,1,4>, you can insert X mistaken keystroke and/or omit Y mistaken keystroke per every correct keystroke without exceeding this value 6, and the percentage X and/or Y represents is not too low to be practical but low enough to reject false positives".
Being a mathematician, I was tempted to invent such a reasoning in hindsight.
But I decided to be truthful instead,
Dscho
Quoted 11 lines · Johannes Sixt
From: Johannes Sixt <[email protected]>
If a given command is not found, then
help.ctries to guess which one the user could have meant. If help.autocorrect is 0 or unset, then a list of suggestions is given as long as the dissimilarity between the given command and the candidates is not excessively high. But if help.autocorrect was non-zero (i.e., a delay after which the command is run automatically), the latter restriction on dissimilarity was not obeyed.In my case, this happened:
Quoted 7 lines
$ git ..daab02 WARNING: You called a Git command named '..daab02', which does not exist. Continuing under the assumption that you meant 'read-tree' in 4.0 seconds automatically...The similarity limit that this patch introduces is already used a few lines later where the list of suggested commands is printed.
Yes, sure. We probably just missed that (I don't use autocorrect myself apart from the testing. I assume Johannes doesn't, too)
Hi,
Quoted 2 lines · Alex Riesen
I don't use autocorrect myself apart from the testing. I assume Johannes doesn't, too
As a matter of fact, I do. But my common mistakes are not in forgetting the subcommand, rather in mispelign them. So I never hit the problem.
Ciao,
Dscho
Hi,
Quoted 16 lines · Johannes Sixt
From: Johannes Sixt <[email protected]>
If a given command is not found, then
help.ctries to guess which one the user could have meant. If help.autocorrect is 0 or unset, then a list of suggestions is given as long as the dissimilarity between the given command and the candidates is not excessively high. But if help.autocorrect was non-zero (i.e., a delay after which the command is run automatically), the latter restriction on dissimilarity was not obeyed.In my case, this happened:
$ git ..daab02 WARNING: You called a Git command named '..daab02', which does not exist. Continuing under the assumption that you meant 'read-tree' in 4.0 seconds automatically...
Quoted 5 lines
The similarity limit that this patch introduces is already used a few lines later where the list of suggested commands is printed.
Signed-off-by Johannes Sixt <[email protected]>---
Obvious ACK from me.