[FYI PATCH] git wrapper: DWIM mistyped commands

This patch introduces a modified Damerau-Levenshtein algorithm into
Git's code base, and uses it with the following penalties to show some
similar commands when an unknown command was encountered:

	swap = 0, insertion = 1, substitution = 2, deletion = 4

A typical output would now look like this:

	$ git sm
	git: 'sm' is not a git-command. See 'git --help'.

	Did you mean one of these?
		am
		rm

The cut-off is at similarity rating 6, which was empirically determined
to give sensible results.

As a convenience, if there is only one candidate, Git continues under
the assumption that the user mistyped it.  Example:

	$ git reabse
	WARNING: You called a Git program named 'reabse', which does
	not exist.
	Continuing under the assumption that you meant 'rebase'
	[...]

Signed-off-by: Johannes Schindelin <redacted>
---

	So I mistyped 'reabse' for the hundred trillionth time, but I
	will never have to correct my mistakes again.

	Note: this patch is _not_ meant for inclusion.

 Makefile      |    2 +
 builtin.h     |    2 +-
 git.c         |    4 ++-
 help.c        |   61 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 levenshtein.c |   47 +++++++++++++++++++++++++++++++++++++++++++
 levenshtein.h |    8 +++++++
 6 files changed, 121 insertions(+), 3 deletions(-)
 create mode 100644 levenshtein.c
 create mode 100644 levenshtein.h

diff --git a/Makefile b/Makefile
index 19bdd03..7e114e0 100644
--- a/Makefile
+++ b/Makefile

@@ -347,6 +347,7 @@ LIB_H += git-compat-util.h
 LIB_H += graph.h
 LIB_H += grep.h
 LIB_H += hash.h
+LIB_H += levenshtein.h
 LIB_H += list-objects.h
 LIB_H += ll-merge.h
 LIB_H += log-tree.h

@@ -421,6 +422,7 @@ LIB_OBJS += hash.o
 LIB_OBJS += help.o
 LIB_OBJS += ident.o
 LIB_OBJS += interpolate.o
+LIB_OBJS += levenshtein.o
 LIB_OBJS += list-objects.o
 LIB_OBJS += ll-merge.o
 LIB_OBJS += lockfile.o

diff --git a/builtin.h b/builtin.h
index 0e605d4..fc5f108 100644
--- a/builtin.h
+++ b/builtin.h

@@ -11,7 +11,7 @@ extern const char git_usage_string[];
 extern const char git_more_info_string[];
 
 extern void list_common_cmds_help(void);
-extern void help_unknown_cmd(const char *cmd);
+extern const char *help_unknown_cmd(const char *cmd);
 extern void prune_packed_objects(int);
 extern int read_line_with_nul(char *buf, int size, FILE *file);
 extern int fmt_merge_msg(int merge_summary, struct strbuf *in,

diff --git a/git.c b/git.c
index 1bfd271..d7510ef 100644
--- a/git.c
+++ b/git.c

@@ -500,7 +500,9 @@ int main(int argc, const char **argv)
 				cmd, argv[0]);
 			exit(1);
 		}
-		help_unknown_cmd(cmd);
+		argv[0] = help_unknown_cmd(cmd);
+		handle_internal_command(argc, argv);
+		execv_dashed_external(argv);
 	}
 
 	fprintf(stderr, "Failed to run command '%s': %s\n",

diff --git a/help.c b/help.c
index bfc84ae..480befe 100644
--- a/help.c
+++ b/help.c

@@ -9,6 +9,7 @@
 #include "common-cmds.h"
 #include "parse-options.h"
 #include "run-command.h"
+#include "levenshtein.h"
 
 static struct man_viewer_list {
 	struct man_viewer_list *next;

@@ -666,9 +667,67 @@ static void show_html_page(const char *git_cmd)
 	open_html(page_path.buf);
 }
 
-void help_unknown_cmd(const char *cmd)
+static const char *levenshtein_cmd;
+static int similarity(const char *cmd) {
+	return levenshtein(levenshtein_cmd, cmd, 0, 2, 1, 4);
+}
+
+static int levenshtein_compare(const void *p1, const void *p2)
+{
+	const struct cmdname *const *c1 = p1, *const *c2 = p2;
+	const char *s1 = (*c1)->name, *s2 = (*c2)->name;
+	int l1 = similarity(s1);
+	int l2 = similarity(s2);
+	return l1 != l2 ? l1 - l2 : strcmp(s1, s2);
+}
+
+const char *help_unknown_cmd(const char *cmd)
 {
+	int i, best_similarity = 0;
+	char cwd[PATH_MAX];
+
+	if (!getcwd(cwd, sizeof(cwd))) {
+		error("Could not get current working directory");
+		cwd[0] = '\0';
+	}
+
+	load_command_list();
+	ALLOC_GROW(main_cmds.names, main_cmds.cnt + other_cmds.cnt,
+			main_cmds.alloc);
+	memcpy(main_cmds.names + main_cmds.cnt, other_cmds.names,
+		other_cmds.cnt * sizeof(other_cmds.names[0]));
+	main_cmds.cnt += other_cmds.cnt;
+
+	levenshtein_cmd = cmd;
+	qsort(main_cmds.names, main_cmds.cnt,
+	      sizeof(*main_cmds.names), levenshtein_compare);
+
+	if (!main_cmds.cnt)
+		die ("Uh oh.  Your system reports no Git commands at all.");
+	best_similarity = similarity(main_cmds.names[0]->name);
+	if (main_cmds.cnt < 2 || best_similarity <
+			similarity(main_cmds.names[1]->name)) {
+		if (!*cwd)
+			exit(1);
+		if (chdir(cwd))
+			die ("Could not change directory back to '%s'", cwd);
+		fprintf(stderr, "WARNING: You called a Git program named '%s', "
+			"which does not exist.\n"
+			"Continuing under the assumption that you meant '%s'\n",
+			cmd, main_cmds.names[0]->name);
+		return main_cmds.names[0]->name;
+	}
+
 	fprintf(stderr, "git: '%s' is not a git-command. See 'git --help'.\n", cmd);
+
+	if (best_similarity < 6) {
+		fprintf(stderr, "\nDid you mean one of these?\n");
+
+		for (i = 0; i < main_cmds.cnt && best_similarity ==
+				similarity(main_cmds.names[i]->name); i++)
+			fprintf(stderr, "\t%s\n", main_cmds.names[i]->name);
+	}
+
 	exit(1);
 }
 

diff --git a/levenshtein.c b/levenshtein.c
new file mode 100644
index 0000000..db52f2c
--- /dev/null
+++ b/levenshtein.c

@@ -0,0 +1,47 @@
+#include "cache.h"
+#include "levenshtein.h"
+
+int levenshtein(const char *string1, const char *string2,
+		int w, int s, int a, int d)
+{
+	int len1 = strlen(string1), len2 = strlen(string2);
+	int *row0 = xmalloc(sizeof(int) * (len2 + 1));
+	int *row1 = xmalloc(sizeof(int) * (len2 + 1));
+	int *row2 = xmalloc(sizeof(int) * (len2 + 1));
+	int i, j;
+
+	for (j = 0; j <= len2; j++)
+		row1[j] = j * a;
+	for (i = 0; i < len1; i++) {
+		int *dummy;
+
+		row2[0] = (i + 1) * d;
+		for (j = 0; j < len2; j++) {
+			/* substitution */
+			row2[j + 1] = row1[j] + s * (string1[i] != string2[j]);
+			/* swap */
+			if (i > 0 && j > 0 && string1[i - 1] == string2[j] &&
+					string1[i] == string2[j - 1] &&
+					row2[j + 1] > row0[j - 1] + w)
+				row2[j + 1] = row0[j - 1] + w;
+			/* deletion */
+			if (j + 1 < len2 && row2[j + 1] > row1[j + 1] + d)
+				row2[j + 1] = row1[j + 1] + d;
+			/* insertion */
+			if (row2[j + 1] > row2[j] + a)
+				row2[j + 1] = row2[j] + a;
+		}
+
+		dummy = row0;
+		row0 = row1;
+		row1 = row2;
+		row2 = dummy;
+	}
+
+	i = row1[len2];
+	free(row0);
+	free(row1);
+	free(row2);
+
+	return i;
+}

diff --git a/levenshtein.h b/levenshtein.h
new file mode 100644
index 0000000..0173abe
--- /dev/null
+++ b/levenshtein.h

@@ -0,0 +1,8 @@
+#ifndef LEVENSHTEIN_H
+#define LEVENSHTEIN_H
+
+int levenshtein(const char *string1, const char *string2,
+	int swap_penalty, int substition_penalty,
+	int insertion_penalty, int deletion_penalty);
+
+#endif

-- 
1.6.0.rc0.21.g91175

On Tue, Jul 22, 2008 at 08:01:29PM +0000, Johannes Schindelin wrote:

This patch introduces a modified Damerau-Levenshtein algorithm into
Git's code base, and uses it with the following penalties to show some
similar commands when an unknown command was encountered:

	swap = 0, insertion = 1, substitution = 2, deletion = 4

A typical output would now look like this:

	$ git sm
	git: 'sm' is not a git-command. See 'git --help'.

	Did you mean one of these?
		am
		rm

The cut-off is at similarity rating 6, which was empirically determined
to give sensible results.

As a convenience, if there is only one candidate, Git continues under
the assumption that the user mistyped it.  Example:

	$ git reabse
	WARNING: You called a Git program named 'reabse', which does
	not exist.
	Continuing under the assumption that you meant 'rebase'
	[...]

<SCNR>
    Or use a decent shell:

    When typing e.g.: git tsa<tab>, it yields:
    $ git status
    ---- corrections (errors 1)
    status        -- show working-tree's status
    tag           -- create tag object signed with GPG
    tar-tree      -- create tar archive of the files in the named tree
    ---- original
    tsa

    and it even works for non git commands ;)
</SCNR>

Despite that, I really like your idea. **hint hint** One could even hook that
for long options into parse-options.

-- 
·O·  Pierre Habouzit
··O                                                madcoder@debian.org
OOO                                                http://www.madism.org

Hi,

On Tue, 22 Jul 2008, Pierre Habouzit wrote:

<SCNR>
    Or use a decent shell:

I tried that:

	git reab<tab><tab><TAB><TTAAABBB!>

Despite that, I really like your idea. **hint hint**

I said that _I_ did not mean it for inclusion.  **hint hint**

Ciao,
Dscho

On Tue, Jul 22, 2008 at 08:19:13PM +0000, Johannes Schindelin wrote:

Hi,

On Tue, 22 Jul 2008, Pierre Habouzit wrote:

quoted

<SCNR>
    Or use a decent shell:

I tried that:

	git reab<tab><tab><TAB><TTAAABBB!>

It yields the following here:

    $ git read-tree
    ---- corrections (errors 1)
    read-tree  -- read tree information into the directory index
    rebase     -- rebase local commits to new upstream head
    ---- original
    reab

and indeed, it should really suggest rebase first, I suppose I should reorder
my zsh completion error weights. but oh well...

quoted

Despite that, I really like your idea. **hint hint**

I said that _I_ did not mean it for inclusion.  **hint hint**

Damn...

-- 
·O·  Pierre Habouzit
··O                                                madcoder@debian.org
OOO                                                http://www.madism.org

Johannes Schindelin, Tue, Jul 22, 2008 22:01:29 +0200:

As a convenience, if there is only one candidate, Git continues under
the assumption that the user mistyped it.  Example:

	$ git reabse
	WARNING: You called a Git program named 'reabse', which does
	not exist.
	Continuing under the assumption that you meant 'rebase'
	[...]

Oh, that would make me suspicios (and I hit Ctrl-C fast when I get
suspicios about what happens to my precious data). Could it be
configurable? For example, BASH's cdspell is configurable and even off
by default.

P.S. I'm still using your first patch and am forced to like it every day :)

It is off by default, to avoid scaring people unless they asked to.

---

Alex Riesen, Tue, Jul 22, 2008 22:37:30 +0200:

Johannes Schindelin, Tue, Jul 22, 2008 22:01:29 +0200:

quoted

As a convenience, if there is only one candidate, Git continues under
the assumption that the user mistyped it.  Example:

	$ git reabse
	WARNING: You called a Git program named 'reabse', which does
	not exist.
	Continuing under the assumption that you meant 'rebase'
	[...]

Oh, that would make me suspicios (and I hit Ctrl-C fast when I get
suspicios about what happens to my precious data). Could it be
configurable? For example, BASH's cdspell is configurable and even off
by default.

Like this, perhaps?

 help.c |    8 ++++++--
 1 files changed, 6 insertions(+), 2 deletions(-)

diff --git a/help.c b/help.c
index 480befe..f08eb9d 100644
--- a/help.c
+++ b/help.c

@@ -28,6 +28,7 @@ enum help_format {
 	HELP_FORMAT_WEB,
 };
 
+static int autocorrect;
 static int show_all = 0;
 static enum help_format help_format = HELP_FORMAT_MAN;
 static struct option builtin_help_options[] = {

@@ -269,6 +270,8 @@ static int git_help_config(const char *var, const char *value, void *cb)
 	}
 	if (!prefixcmp(var, "man."))
 		return add_man_viewer_info(var, value);
+	if (!strcmp(var, "help.autocorrect"))
+		autocorrect = git_config_bool(var,value);
 
 	return git_default_config(var, value, cb);
 }

@@ -704,9 +707,10 @@ const char *help_unknown_cmd(const char *cmd)
 
 	if (!main_cmds.cnt)
 		die ("Uh oh.  Your system reports no Git commands at all.");
+	git_config(git_help_config, NULL);
 	best_similarity = similarity(main_cmds.names[0]->name);
-	if (main_cmds.cnt < 2 || best_similarity <
-			similarity(main_cmds.names[1]->name)) {
+	if (autocorrect && (main_cmds.cnt < 2 ||
+		best_similarity < similarity(main_cmds.names[1]->name))) {
 		if (!*cwd)
 			exit(1);
 		if (chdir(cwd))

-- 
1.6.0.rc0.48.g6dda.dirty

Hi,

On Tue, 22 Jul 2008, Alex Riesen wrote:

+	if (autocorrect && (main_cmds.cnt < 2 ||
+		best_similarity < similarity(main_cmds.names[1]->name))) {
 		if (!*cwd)
 			exit(1);
 		if (chdir(cwd))

In that case, you need to put in the "one of these" / "this" conditional 
again, which I ripped out because I do not need it any more.

Ciao,
Dscho

It is off by default, to avoid scaring people unless they asked to.
---
Johannes Schindelin, Tue, Jul 22, 2008 23:08:19 +0200:

On Tue, 22 Jul 2008, Alex Riesen wrote:

quoted

+	if (autocorrect && (main_cmds.cnt < 2 ||
+		best_similarity < similarity(main_cmds.names[1]->name))) {
 		if (!*cwd)
 			exit(1);
 		if (chdir(cwd))

In that case, you need to put in the "one of these" / "this" conditional 
again, which I ripped out because I do not need it any more.

Of course, missed it. Like this, then.

 help.c |   20 ++++++++++++++------
 1 files changed, 14 insertions(+), 6 deletions(-)

diff --git a/help.c b/help.c
index 480befe..cf6b459 100644
--- a/help.c
+++ b/help.c

@@ -28,6 +28,7 @@ enum help_format {
 	HELP_FORMAT_WEB,
 };
 
+static int autocorrect;
 static int show_all = 0;
 static enum help_format help_format = HELP_FORMAT_MAN;
 static struct option builtin_help_options[] = {

@@ -269,6 +270,8 @@ static int git_help_config(const char *var, const char *value, void *cb)
 	}
 	if (!prefixcmp(var, "man."))
 		return add_man_viewer_info(var, value);
+	if (!strcmp(var, "help.autocorrect"))
+		autocorrect = git_config_bool(var,value);
 
 	return git_default_config(var, value, cb);
 }

@@ -704,9 +707,10 @@ const char *help_unknown_cmd(const char *cmd)
 
 	if (!main_cmds.cnt)
 		die ("Uh oh.  Your system reports no Git commands at all.");
+	git_config(git_help_config, NULL);
 	best_similarity = similarity(main_cmds.names[0]->name);
-	if (main_cmds.cnt < 2 || best_similarity <
-			similarity(main_cmds.names[1]->name)) {
+	if (autocorrect && (main_cmds.cnt < 2 ||
+		best_similarity < similarity(main_cmds.names[1]->name))) {
 		if (!*cwd)
 			exit(1);
 		if (chdir(cwd))

@@ -721,10 +725,14 @@ 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) {
-		fprintf(stderr, "\nDid you mean one of these?\n");
-
-		for (i = 0; i < main_cmds.cnt && best_similarity ==
-				similarity(main_cmds.names[i]->name); i++)
+		int n = 0;
+		while (n < main_cmds.cnt &&
+			best_similarity == similarity(main_cmds.names[n]->name))
+			++n;
+		fprintf(stderr, "\nDid you mean %s?\n",
+			n < 2 ? "this": "one of these");
+
+		for (i = 0; i < n; i++)
 			fprintf(stderr, "\t%s\n", main_cmds.names[i]->name);
 	}
 

-- 
1.6.0.rc0.48.ga184

Hi,

On Tue, 22 Jul 2008, Alex Riesen wrote:

This "if" already checks if there is only one candidate.  So you should 
just add an inner "if (autocorrect) ... else single = 1;" or some such.

However, I think that the intention of this patch is too much DWIMery, 
which might be good for me (just like my "git add remote" patch), but not 
for the general audience.

Ciao,
Dscho

It is off by default, to avoid scaring people unless they asked to.
---

Johannes Schindelin, Tue, Jul 22, 2008 23:44:50 +0200:

On Tue, 22 Jul 2008, Alex Riesen wrote:

quoted

@@ -704,9 +707,10 @@ const char *help_unknown_cmd(const char *cmd)
 
 	if (!main_cmds.cnt)
 		die ("Uh oh.  Your system reports no Git commands at all.");
+	git_config(git_help_config, NULL);
 	best_similarity = similarity(main_cmds.names[0]->name);
-	if (main_cmds.cnt < 2 || best_similarity <
-			similarity(main_cmds.names[1]->name)) {
+	if (autocorrect && (main_cmds.cnt < 2 ||
+		best_similarity < similarity(main_cmds.names[1]->name))) {
 		if (!*cwd)
 			exit(1);
 		if (chdir(cwd))

This "if" already checks if there is only one candidate.  So you should 
just add an inner "if (autocorrect) ... else single = 1;" or some such.

Oh right, stupid me.

However, I think that the intention of this patch is too much DWIMery, 
which might be good for me (just like my "git add remote" patch), but not 
for the general audience.

Mustn't be good for all (for the "general audience" it is even common
practice to forget to thank. It may be even a sign of bad manners for
it). It is good for me though. And thanks for sharing.

Moved git_config before the calls where current directory is changed:
so that it has the same filesystem context as in normal case. Less
surprises.

 help.c |   19 +++++++++++++------
 1 files changed, 13 insertions(+), 6 deletions(-)

diff --git a/help.c b/help.c
index 480befe..8b25a55 100644
--- a/help.c
+++ b/help.c

@@ -28,6 +28,7 @@ enum help_format {
 	HELP_FORMAT_WEB,
 };
 
+static int autocorrect;
 static int show_all = 0;
 static enum help_format help_format = HELP_FORMAT_MAN;
 static struct option builtin_help_options[] = {

@@ -269,6 +270,8 @@ static int git_help_config(const char *var, const char *value, void *cb)
 	}
 	if (!prefixcmp(var, "man."))
 		return add_man_viewer_info(var, value);
+	if (!strcmp(var, "help.autocorrect"))
+		autocorrect = git_config_bool(var,value);
 
 	return git_default_config(var, value, cb);
 }

@@ -683,7 +686,7 @@ static int levenshtein_compare(const void *p1, const void *p2)
 
 const char *help_unknown_cmd(const char *cmd)
 {
-	int i, best_similarity = 0;
+	int i, best_similarity = 0, n;
 	char cwd[PATH_MAX];
 
 	if (!getcwd(cwd, sizeof(cwd))) {

@@ -691,6 +694,7 @@ const char *help_unknown_cmd(const char *cmd)
 		cwd[0] = '\0';
 	}
 
+	git_config(git_help_config, NULL);
 	load_command_list();
 	ALLOC_GROW(main_cmds.names, main_cmds.cnt + other_cmds.cnt,
 			main_cmds.alloc);

@@ -705,8 +709,11 @@ const char *help_unknown_cmd(const char *cmd)
 	if (!main_cmds.cnt)
 		die ("Uh oh.  Your system reports no Git commands at all.");
 	best_similarity = similarity(main_cmds.names[0]->name);
-	if (main_cmds.cnt < 2 || best_similarity <
-			similarity(main_cmds.names[1]->name)) {
+	n = 1;
+	while (n < main_cmds.cnt &&
+		best_similarity == similarity(main_cmds.names[n]->name))
+		++n;
+	if (autocorrect && n == 1) {
 		if (!*cwd)
 			exit(1);
 		if (chdir(cwd))

@@ -721,10 +728,10 @@ 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) {
-		fprintf(stderr, "\nDid you mean one of these?\n");
+		fprintf(stderr, "\nDid you mean %s?\n",
+			n < 2 ? "this": "one of these");
 
-		for (i = 0; i < main_cmds.cnt && best_similarity ==
-				similarity(main_cmds.names[i]->name); i++)
+		for (i = 0; i < n; i++)
 			fprintf(stderr, "\t%s\n", main_cmds.names[i]->name);
 	}
 

-- 
1.6.0.rc0.48.ga184

Hi,

On Wed, 23 Jul 2008, Alex Riesen wrote:

Johannes Schindelin, Tue, Jul 22, 2008 23:44:50 +0200:

quoted

However, I think that the intention of this patch is too much DWIMery, 
which might be good for me (just like my "git add remote" patch), but 
not for the general audience.

Mustn't be good for all

You meant "needn't"?  It is good for me ;-)

And thanks for sharing.

You're welcome.

+	n = 1;
+	while (n < main_cmds.cnt &&
+		best_similarity == similarity(main_cmds.names[n]->name))
+		++n;

Mini-nit: you never ask for the value of n, only if it is 1 or larger.  So 
you do not need to count...

Ciao,
Dscho

Johannes Schindelin, Wed, Jul 23, 2008 18:44:49 +0200:

quoted

+	n = 1;
+	while (n < main_cmds.cnt &&
+		best_similarity == similarity(main_cmds.names[n]->name))
+		++n;

Mini-nit: you never ask for the value of n, only if it is 1 or larger.  So 
you do not need to count...

But I do, don't I? AFAICS, I use 0, 1 and >1 (this-these).

Hi,

On Wed, 23 Jul 2008, Alex Riesen wrote:

Johannes Schindelin, Wed, Jul 23, 2008 18:44:49 +0200:

quoted

quoted

+	n = 1;
+	while (n < main_cmds.cnt &&
+		best_similarity == similarity(main_cmds.names[n]->name))
+		++n;

Mini-nit: you never ask for the value of n, only if it is 1 or larger.  So 
you do not need to count...

But I do, don't I? AFAICS, I use 0, 1 and >1 (this-these).

Yes.  So check cnt > 0 && best_similarity > 5 says if it is 0, and 
cnt > 1 && best_similarity < similarity(...[1]...) says if it is 1.

Ergo: no need to count,
Dscho

Hi,

On Wed, 23 Jul 2008, Johannes Schindelin wrote:

On Wed, 23 Jul 2008, Alex Riesen wrote:

quoted

Johannes Schindelin, Wed, Jul 23, 2008 18:44:49 +0200:

quoted

quoted

+	n = 1;
+	while (n < main_cmds.cnt &&
+		best_similarity == similarity(main_cmds.names[n]->name))
+		++n;

Mini-nit: you never ask for the value of n, only if it is 1 or larger.  So 
you do not need to count...

But I do, don't I? AFAICS, I use 0, 1 and >1 (this-these).

Yes.  So check cnt > 0 && best_similarity > 5 says if it is 0,

Oh, I just realized that my patch is bogus anyway.  It only checks for 
best_similarity > 5 in the case that the first two commands have equal 
similarity.  D'oh.

Ciao,
Dscho