{"thread":{"id":"21950","subject":"[PATCH] help.autocorrect: do not run a command if the command given is junk","startedAt":"2009-12-14T13:03:19Z","lastAt":"2009-12-15T07:57:18Z","messageCount":11,"participants":["Johannes Sixt","Alex Riesen","Johannes Schindelin","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"129869","messageId":"4B263797.5070808@viscovery.net","threadId":"21950","inReplyTo":null,"subject":"[PATCH] help.autocorrect: do not run a command if the command given is junk","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2009-12-14T13:03:19Z","receivedAt":"2009-12-14T13:03:19Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"From: Johannes Sixt \n\nIf a given command is not found, then help.c tries to guess which one the\nuser could have meant. If help.autocorrect is 0 or unset, then a list of\nsuggestions is given as long as the dissimilarity between the given command\nand the candidates is not excessively high. But if help.autocorrect was\nnon-zero (i.e., a delay after which the command is run automatically), the\nlatter restriction on dissimilarity was not obeyed.\n\nIn my case, this happened:\n\n $ git ..daab02\n WARNING: You called a Git command named '..daab02', which does not exist.\n Continuing under the assumption that you meant 'read-tree'\n in 4.0 seconds automatically...\n\nThe similarity limit that this patch introduces is already used a few lines\nlater where the list of suggested commands is printed.\n\nSigned-off-by: Johannes Sixt \n---\n help.c | 2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/help.c b/help.c\nindex e8db31f..db888cf 100644\n--- a/help.c\n+++ b/help.c\n@@ -331,7 +331,7 @@ const char *help_unknown_cmd(const char *cmd)\n \tn = 1;\n \twhile (n < main_cmds.cnt && best_similarity == main_cmds.names[n]->len)\n \t\t++n;\n-\tif (autocorrect && n == 1) {\n+\tif (autocorrect && n == 1 && best_similarity < 6) {\n \t\tconst char *assumed = main_cmds.names[0]->name;\n \t\tmain_cmds.names[0] = NULL;\n \t\tclean_cmdnames(&main_cmds);\n-- \n1.6.6.rc1.46.g1635\n"},{"id":"129874","messageId":"81b0412b0912140529w4a15418ewf304b9d6f4c1f007@mail.gmail.com","threadId":"21950","inReplyTo":"4B263797.5070808@viscovery.net","subject":"Re: [PATCH] help.autocorrect: do not run a command if the command given is junk","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2009-12-14T13:29:21Z","receivedAt":"2009-12-14T13:29:21Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On Mon, Dec 14, 2009 at 14:03, Johannes Sixt wrote:\n> From: Johannes Sixt \n>\n> If a given command is not found, then help.c tries to guess which one the\n> user could have meant. If help.autocorrect is 0 or unset, then a list of\n> suggestions is given as long as the dissimilarity between the given command\n> and the candidates is not excessively high. But if help.autocorrect was\n> non-zero (i.e., a delay after which the command is run automatically), the\n> latter restriction on dissimilarity was not obeyed.\n>\n> In my case, this happened:\n>\n>  $ git ..daab02\n>  WARNING: You called a Git command named '..daab02', which does not exist.\n>  Continuing under the assumption that you meant 'read-tree'\n>  in 4.0 seconds automatically...\n>\n> The similarity limit that this patch introduces is already used a few lines\n> later where the list of suggested commands is printed.\n\nYes, sure. We probably just missed that (I don't use autocorrect myself\napart from the testing. I assume Johannes doesn't, too)\n"},{"id":"129875","messageId":"alpine.DEB.1.00.0912141515430.4985@pacific.mpi-cbg.de","threadId":"21950","inReplyTo":"4B263797.5070808@viscovery.net","subject":"Re: [PATCH] help.autocorrect: do not run a command if the command given is junk","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-12-14T14:16:01Z","receivedAt":"2009-12-14T14:16:01Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 14 Dec 2009, Johannes Sixt wrote:\n\n> From: Johannes Sixt \n> \n> If a given command is not found, then help.c tries to guess which one the\n> user could have meant. If help.autocorrect is 0 or unset, then a list of\n> suggestions is given as long as the dissimilarity between the given command\n> and the candidates is not excessively high. But if help.autocorrect was\n> non-zero (i.e., a delay after which the command is run automatically), the\n> latter restriction on dissimilarity was not obeyed.\n> \n> In my case, this happened:\n> \n> $ git ..daab02\n> WARNING: You called a Git command named '..daab02', which does not exist.\n> Continuing under the assumption that you meant 'read-tree'\n> in 4.0 seconds automatically...\n> \n> The similarity limit that this patch introduces is already used a few lines\n> later where the list of suggested commands is printed.\n> \n> Signed-off-by: Johannes Sixt \n> ---\n\nObvious ACK from me.\n"},{"id":"129876","messageId":"alpine.DEB.1.00.0912141516180.4985@pacific.mpi-cbg.de","threadId":"21950","inReplyTo":"81b0412b0912140529w4a15418ewf304b9d6f4c1f007@mail.gmail.com","subject":"Re: [PATCH] help.autocorrect: do not run a command if the command given is junk","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-12-14T14:17:29Z","receivedAt":"2009-12-14T14:17:29Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 14 Dec 2009, Alex Riesen wrote:\n\n> I don't use autocorrect myself apart from the testing. I assume Johannes \n> doesn't, too\n\nAs a matter of fact, I do. But my common mistakes are not in forgetting \nthe subcommand, rather in mispelign them. So I never hit the problem.\n\nCiao,\nDscho\n"},{"id":"129894","messageId":"7v7hspjp3q.fsf@alter.siamese.dyndns.org","threadId":"21950","inReplyTo":"4B263797.5070808@viscovery.net","subject":"Re: [PATCH] help.autocorrect: do not run a command if the command given is junk","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-12-14T20:08:09Z","receivedAt":"2009-12-14T20:08:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Sixt writes:\n\n> From: Johannes Sixt \n>\n> If a given command is not found, then help.c tries to guess which one the\n> user could have meant. If help.autocorrect is 0 or unset, then a list of\n> suggestions is given as long as the dissimilarity between the given command\n> and the candidates is not excessively high. But if help.autocorrect was\n> non-zero (i.e., a delay after which the command is run automatically), the\n> latter restriction on dissimilarity was not obeyed.\n>\n> In my case, this happened:\n>\n> $ git ..daab02\n> WARNING: You called a Git command named '..daab02', which does not exist.\n> Continuing under the assumption that you meant 'read-tree'\n> in 4.0 seconds automatically...\n>\n> The similarity limit that this patch introduces is already used a few lines\n> later where the list of suggested commands is printed.\n>\n> Signed-off-by: Johannes Sixt \n> ---\n> help.c | 2 +-\n> 1 files changed, 1 insertions(+), 1 deletions(-)\n\nThanks. Will apply to 'maint'.\n\nBut I am curious about and would prefer to see the story behind '6'\nsomeday.\n\nThis is not entirely a new problem that you are introducing, as the same\ncomparison-with-six appears in a later part of the code, but this patch\nduplicates the magic number whose two instances need to match, so in that\nsense it makes it more necessary than before to document the choice of\nmagic number somewhere in a comment in the code.\n\nDid 8af84da (git wrapper: DWIM mistyped commands, 2008-08-31) made up just\na random number out of thin-air? What bad things would happen if we used\n'600' (or '1') instead of '6'? What kind of correlation does the cut-off\nvalue we use here should have with some intrinsic numbers your git\ninstallation has (e.g. perhaps \"must be at least 80% of average length of\navailable commands\" or something like that)?\n\nIn the meantime, I think squashing the following in would help us keep the\ntwo magic numbers in sync.\n\ndiff --git a/help.c b/help.c\nindex db888cf..fbf80d9 100644\n--- a/help.c\n+++ b/help.c\n@@ -297,6 +297,9 @@ static void add_cmd_list(struct cmdnames *cmds, struct cmdnames *old)\n \told->names = NULL;\n }\n \n+/* how did we decide this is a good cutoff??? */\n+#define SIMILAR_ENOUGH(x) ((x) < 6)\n+\n const char *help_unknown_cmd(const char *cmd)\n {\n \tint i, n, best_similarity = 0;\n@@ -331,7 +334,7 @@ const char *help_unknown_cmd(const char *cmd)\n \tn = 1;\n \twhile (n < main_cmds.cnt && best_similarity == main_cmds.names[n]->len)\n \t\t++n;\n-\tif (autocorrect && n == 1 && best_similarity < 6) {\n+\tif (autocorrect && n == 1 && SIMILAR_ENOUGH(best_similarity)) {\n \t\tconst char *assumed = main_cmds.names[0]->name;\n \t\tmain_cmds.names[0] = NULL;\n \t\tclean_cmdnames(&main_cmds);\n@@ -349,7 +352,7 @@ const char *help_unknown_cmd(const char *cmd)\n \n \tfprintf(stderr, \"git: '%s' is not a git-command. See 'git --help'.\\n\", cmd);\n \n-\tif (best_similarity < 6) {\n+\tif (SIMILAR_ENOUGH(best_similarity)) {\n \t\tfprintf(stderr, \"\\nDid you mean %s?\\n\",\n \t\t\tn < 2 ? \"this\": \"one of these\");\n \n"},{"id":"129904","messageId":"alpine.DEB.1.00.0912142146590.4985@pacific.mpi-cbg.de","threadId":"21950","inReplyTo":"7v7hspjp3q.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] help.autocorrect: do not run a command if the command given is junk","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-12-14T21:09:11Z","receivedAt":"2009-12-14T21:09:11Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 14 Dec 2009, Junio C Hamano wrote:\n\n> I am curious about and would prefer to see the story behind '6' someday.\n\nThe '6' as a cut-off to the levenshtein distances we list when \nautocorrecting was derived in a totally scientific manner:\n\n1) first I implemented Levenshtein-Damerau with a configurable weight of \n neighbor flips (\"switches\"), substitutions, additions and deletions,\n\n2) next I patched the code to sort the availablecommands by their distance \n to the mispelt command,\n\n3) as this lists way too much, I implemented a cut-off that was \n configurable by an environment variable (without any safety checks, as \n I did not plan to release that code anyway),\n\n4) now comes the totally, unbelievably cunningly scientific part: I did a \n self-experiment! I deliberately mispelt commands in a totally random \n manner!\n\n5) then I changed the code to actually output the distances so I could \n determine a cut-off that makes sense with my type of tyops,\n\n6) after about 15 tries of deliberate mistakes (mostly doing what I \n usually do, something like \"git pull\" and \"git log\" or something like \n that, but watching TV, chatting on the phone _and_ cleaning the dishes \n at the same time), I found that 5 was too low and 7 too large.\n\nThe number '6' happily coincided with the number of steps I needed to come \nup with the number. You see? The _perfect_ way to determine a completely \narbitrary number.\n\nActually, you probably see that I just made up that number and tested a \nfew times, and it seemed to work reasonably well.\n\nFWIW almost the same procedure led to the weights 0, 2, 1 and 4 that you \nsee in help.c. The weights are basically factors with which mistakes are \npunished: if you just confuse two adjacent letters, such as \"psuh\" instead \nof \"push\" (which can be quite common if you use two hands, one on the left \nside, and one on the right side of the keyboard, with an en-US layout so \nmany of us use, myself included) it costs 0.\n\nIf you write a different character than what you intended, the cost is 2. \nThe idea behind it is that you're more likely to miss a key than to hit \nthe wrong key. With the laptop I am typing this email on, it is \nparticularly likely that I miss a key, because there are certain \nkey combinations where only the first key triggers an input event, but the \nsecond only triggers an input event when it is _released_ after the first \none. So when I type \"er\" real fast and happen to release the \"e\" key \nafter the \"r\" key, no \"r\" appears on my screen.\n\nOkay, so the weight for adding a character must be smaller than \nsubstituting a character, but why is the cost for deletion so high? \nWell, I really rarely type unnecessary characters (except when writing to \nthe Git mailing list, arguably) so those costs must be substantially \nhigher than for typing the wrong character.\n\nMy original plan was to log all my tyops into a log file and analyze those \nerrors later, but then my initial 0, 2, 1, 4 and 6 constants worked well \nenough for me that I did not bother.\n\nSatisfied?\n\nCiao,\nDscho\n"},{"id":"129907","messageId":"7vocm1grdb.fsf@alter.siamese.dyndns.org","threadId":"21950","inReplyTo":"alpine.DEB.1.00.0912142146590.4985@pacific.mpi-cbg.de","subject":"Re: [PATCH] help.autocorrect: do not run a command if the command given is junk","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-12-14T21:47:28Z","receivedAt":"2009-12-14T21:47:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> Satisfied?\n\nVery much.\n\n FWIW almost the same procedure led to the weights 0, 2, 1 and 4 that you \n see in help.c. The weights are basically factors with which mistakes are \n punished: if you just confuse two adjacent letters, such as \"psuh\" instead \n of \"push\" (which can be quite common if you use two hands, one on the left \n side, and one on the right side of the keyboard, with an en-US layout so \n many of us use, myself included) it costs 0.\n\n If you write a different character than what you intended, the cost is 2. \n The idea behind it is that you're more likely to miss a key than to hit \n the wrong key. With the laptop I am typing this email on, it is \n particularly likely that I miss a key, because there are certain \n key combinations where only the first key triggers an input event, but the \n second only triggers an input event when it is _released_ after the first \n one. So when I type \"er\" real fast and happen to release the \"e\" key \n after the \"r\" key, no \"r\" appears on my screen.\n\n Okay, so the weight for adding a character must be smaller than \n substituting a character, but why is the cost for deletion so high? \n Well, I really rarely type unnecessary characters (except when writing to \n the Git mailing list, arguably) so those costs must be substantially \n higher than for typing the wrong character.\n\nThese are actually very good justifications in the sense that people who\nmight want to tweak the heuristics can see the reason behind the current\nchoice and agree or disagree with it.\n\nI somehow suspect that a good mathematician can come up with a rationale\nfor 6 after the fact that sounds convincing, along the lines of \"the\naverage length of commands being N, and levenshtein penalties being\n<0,2,1,4>, you can insert X mistaken keystroke and/or omit Y mistaken\nkeystroke per every correct keystroke without exceeding this value 6, and\nthe percentage X and/or Y represents is not too low to be practical but low\nenough to reject false positives\".\n\nIn any case, I'll further squash in the following. Thanks for an amusing\nexplanation ;-).\n\ndiff --git a/help.c b/help.c\nindex fbf80d9..de1e2ea 100644\n--- a/help.c\n+++ b/help.c\n@@ -297,7 +297,7 @@ static void add_cmd_list(struct cmdnames *cmds, struct cmdnames *old)\n \told->names = NULL;\n }\n \n-/* how did we decide this is a good cutoff??? */\n+/* An empirically derived magic number */\n #define SIMILAR_ENOUGH(x) ((x) < 6)\n \n const char *help_unknown_cmd(const char *cmd)\n"},{"id":"129912","messageId":"200912142255.36949.j.sixt@viscovery.net","threadId":"21950","inReplyTo":"7v7hspjp3q.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] help.autocorrect: do not run a command if the command given is junk","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2009-12-14T21:55:36Z","receivedAt":"2009-12-14T21:55:36Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"On Montag, 14. Dezember 2009, Junio C Hamano wrote:\n> In the meantime, I think squashing the following in would help us keep the\n> two magic numbers in sync.\n\nI do not think that keeping the numbers in sync is necessary. For example, the \nsimilarity requirement for commands that run automatically could be stricter \nthan for the list of suggestions. Then it would be possible that a unique \nbest candidate is not good enough to be run automatically; there would only \nbe a list of suggestions.\n\n-- Hannes\n"},{"id":"129909","messageId":"alpine.DEB.1.00.0912142303270.4985@pacific.mpi-cbg.de","threadId":"21950","inReplyTo":"7vocm1grdb.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] help.autocorrect: do not run a command if the command given is junk","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-12-14T22:04:29Z","receivedAt":"2009-12-14T22:04:29Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 14 Dec 2009, Junio C Hamano wrote:\n\n> I somehow suspect that a good mathematician can come up with a rationale \n> for 6 after the fact that sounds convincing, along the lines of \"the \n> average length of commands being N, and levenshtein penalties being \n> <0,2,1,4>, you can insert X mistaken keystroke and/or omit Y mistaken \n> keystroke per every correct keystroke without exceeding this value 6, \n> and the percentage X and/or Y represents is not too low to be practical \n> but low enough to reject false positives\".\n\nBeing a mathematician, I was tempted to invent such a reasoning in \nhindsight.\n\nBut I decided to be truthful instead,\nDscho\n"},{"id":"129918","messageId":"7vaaxlcehw.fsf@alter.siamese.dyndns.org","threadId":"21950","inReplyTo":"200912142255.36949.j.sixt@viscovery.net","subject":"Re: [PATCH] help.autocorrect: do not run a command if the command given is junk","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-12-14T23:39:07Z","receivedAt":"2009-12-14T23:39:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Sixt writes:\n\n> On Montag, 14. Dezember 2009, Junio C Hamano wrote:\n>> In the meantime, I think squashing the following in would help us keep the\n>> two magic numbers in sync.\n>\n> I do not think that keeping the numbers in sync is necessary. For example, the \n> similarity requirement for commands that run automatically could be stricter \n> than for the list of suggestions. Then it would be possible that a unique \n> best candidate is not good enough to be run automatically; there would only \n> be a list of suggestions.\n\nWell thought out. Would you want to reroll a patch with two symbolic\nconstants then?\n"},{"id":"129941","messageId":"4B27415E.1090107@viscovery.net","threadId":"21950","inReplyTo":"7vaaxlcehw.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] help.autocorrect: do not run a command if the command given is junk","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2009-12-15T07:57:18Z","receivedAt":"2009-12-15T07:57:18Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Junio C Hamano schrieb:\n> Johannes Sixt writes:\n> \n>> On Montag, 14. Dezember 2009, Junio C Hamano wrote:\n>>> In the meantime, I think squashing the following in would help us keep the\n>>> two magic numbers in sync.\n>> I do not think that keeping the numbers in sync is necessary. For example, the \n>> similarity requirement for commands that run automatically could be stricter \n>> than for the list of suggestions. Then it would be possible that a unique \n>> best candidate is not good enough to be run automatically; there would only \n>> be a list of suggestions.\n> \n> Well thought out. Would you want to reroll a patch with two symbolic\n> constants then?\n\nI briefly looked into it, but, no, I don't want to reroll the patch. Not\nonly would the change be larger than I first thought, but I would also\nhave to find a mis-typed command where a stricter limit makes a difference\n*and* where it makes sense that the guessed command is not run\nautomatically. Moreover, I would also have to *find* a suitable new\nsimilarity limit. Not something I want to do now.\n\nPlease take my original patch and squash in your suggested changes. Here\nit is for your convenience with an updated commit message (only the\nlast paragraph changed).\n\n-- Hannes\n\n--- 8< ---\nFrom: Johannes Sixt \nSubject: [PATCH] help.autocorrect: do not run a command if the command given is junk\n\nIf a given command is not found, then help.c tries to guess which one the\nuser could have meant. If help.autocorrect is 0 or unset, then a list of\nsuggestions is given as long as the dissimilarity between the given command\nand the candidates is not excessively high. But if help.autocorrect was\nnon-zero (i.e., a delay after which the command is run automatically), the\nlatter restriction on dissimilarity was not obeyed.\n\nIn my case, this happened:\n\n $ git ..daab02\n WARNING: You called a Git command named '..daab02', which does not exist.\n Continuing under the assumption that you meant 'read-tree'\n in 4.0 seconds automatically...\n\nThe patch reuses the similarity limit that is also applied when the list of\nsuggested commands is printed.\n\nSigned-off-by: Johannes Sixt \n---\n help.c | 7 +++++--\n 1 files changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/help.c b/help.c\nindex e8db31f..9da97d7 100644\n--- a/help.c\n+++ b/help.c\n@@ -297,6 +297,9 @@ static void add_cmd_list(struct cmdnames *cmds, struct cmdnames *old)\n \told->names = NULL;\n }\n\n+/* An empirically derived magic number */\n+#define SIMILAR_ENOUGH(x) ((x) < 6)\n+\n const char *help_unknown_cmd(const char *cmd)\n {\n \tint i, n, best_similarity = 0;\n@@ -331,7 +334,7 @@ const char *help_unknown_cmd(const char *cmd)\n \tn = 1;\n \twhile (n < main_cmds.cnt && best_similarity == main_cmds.names[n]->len)\n \t\t++n;\n-\tif (autocorrect && n == 1) {\n+\tif (autocorrect && n == 1 && SIMILAR_ENOUGH(best_similarity)) {\n \t\tconst char *assumed = main_cmds.names[0]->name;\n \t\tmain_cmds.names[0] = NULL;\n \t\tclean_cmdnames(&main_cmds);\n@@ -349,7 +352,7 @@ const char *help_unknown_cmd(const char *cmd)\n\n \tfprintf(stderr, \"git: '%s' is not a git-command. See 'git --help'.\\n\", cmd);\n\n-\tif (best_similarity < 6) {\n+\tif (SIMILAR_ENOUGH(best_similarity)) {\n \t\tfprintf(stderr, \"\\nDid you mean %s?\\n\",\n \t\t\tn < 2 ? \"this\": \"one of these\");\n\n-- \n1.6.6.rc1.46.g1635\n"}]}