[PATCH] Remove calculation of the longest command name from where it is not used

[PATCH] Remove calculation of the longest command name from where it is not used

[Alex Riesen, Alex Riesen]

Just calculate it where it is needed - it is cheap and trivial,
as all the lengths are already there (stored when creating the
command lists).

Signed-off-by: Alex Riesen <raa.lkml@gmail.com>
---

And it less code than before (it is even more deletions than
insertions).

BTW, the Johannesses typo-guesser conflicts heavily in recent master.
Pity. I'm going to rebase it and send out the rebased version.

 builtin-help.c  |    4 ++--
 builtin-merge.c |    8 ++++----
 help.c          |   34 +++++++++++++++-------------------
 help.h          |    6 +++---
 4 files changed, 24 insertions(+), 28 deletions(-)

diff --git a/builtin-help.c b/builtin-help.c
index 391f749..9225102 100644
--- a/builtin-help.c
+++ b/builtin-help.c
@@ -418,7 +418,7 @@ int cmd_help(int argc, const char **argv, const char *prefix)
 {
 	int nongit;
 	const char *alias;
-	unsigned int longest = load_command_list("git-", &main_cmds, &other_cmds);
+	load_command_list("git-", &main_cmds, &other_cmds);
 
 	setup_git_directory_gently(&nongit);
 	git_config(git_help_config, NULL);
@@ -428,7 +428,7 @@ int cmd_help(int argc, const char **argv, const char *prefix)
 
 	if (show_all) {
 		printf("usage: %s\n\n", git_usage_string);
-		list_commands("git commands", longest, &main_cmds, &other_cmds);
+		list_commands("git commands", &main_cmds, &other_cmds);
 		printf("%s\n", git_more_info_string);
 		return 0;
 	}
diff --git a/builtin-merge.c b/builtin-merge.c
index d6bcbec..dcd08f7 100644
--- a/builtin-merge.c
+++ b/builtin-merge.c
@@ -80,7 +80,7 @@ static struct strategy *get_strategy(const char *name)
 	int i;
 	struct strategy *ret;
 	static struct cmdnames main_cmds, other_cmds;
-	static int longest;
+	static int loaded;
 
 	if (!name)
 		return NULL;
@@ -89,14 +89,14 @@ static struct strategy *get_strategy(const char *name)
 		if (!strcmp(name, all_strategy[i].name))
 			return &all_strategy[i];
 
-	if (!longest) {
+	if (!loaded) {
 		struct cmdnames not_strategies;
+		loaded = 1;
 
 		memset(&main_cmds, 0, sizeof(struct cmdnames));
 		memset(&other_cmds, 0, sizeof(struct cmdnames));
 		memset(&not_strategies, 0, sizeof(struct cmdnames));
-		longest = load_command_list("git-merge-", &main_cmds,
-				&other_cmds);
+		load_command_list("git-merge-", &main_cmds, &other_cmds);
 		for (i = 0; i < main_cmds.cnt; i++) {
 			int j, found = 0;
 			struct cmdname *ent = main_cmds.names[i];
diff --git a/help.c b/help.c
index 1afbac0..a17a746 100644
--- a/help.c
+++ b/help.c
@@ -133,11 +133,10 @@ static int is_executable(const char *name)
 	return st.st_mode & S_IXUSR;
 }
 
-static unsigned int list_commands_in_dir(struct cmdnames *cmds,
+static void list_commands_in_dir(struct cmdnames *cmds,
 					 const char *path,
 					 const char *prefix)
 {
-	unsigned int longest = 0;
 	int prefix_len;
 	DIR *dir = opendir(path);
 	struct dirent *de;
@@ -145,7 +144,7 @@ static unsigned int list_commands_in_dir(struct cmdnames *cmds,
 	int len;
 
 	if (!dir)
-		return 0;
+		return;
 	if (!prefix)
 		prefix = "git-";
 	prefix_len = strlen(prefix);
@@ -168,29 +167,22 @@ static unsigned int list_commands_in_dir(struct cmdnames *cmds,
 		if (has_extension(de->d_name, ".exe"))
 			entlen -= 4;
 
-		if (longest < entlen)
-			longest = entlen;
-
 		add_cmdname(cmds, de->d_name + prefix_len, entlen);
 	}
 	closedir(dir);
 	strbuf_release(&buf);
-
-	return longest;
 }
 
-unsigned int load_command_list(const char *prefix,
+void load_command_list(const char *prefix,
 		struct cmdnames *main_cmds,
 		struct cmdnames *other_cmds)
 {
-	unsigned int longest = 0;
-	unsigned int len;
 	const char *env_path = getenv("PATH");
 	char *paths, *path, *colon;
 	const char *exec_path = git_exec_path();
 
 	if (exec_path)
-		longest = list_commands_in_dir(main_cmds, exec_path, prefix);
+		list_commands_in_dir(main_cmds, exec_path, prefix);
 
 	if (!env_path) {
 		fprintf(stderr, "PATH not set\n");
@@ -202,9 +194,7 @@ unsigned int load_command_list(const char *prefix,
 		if ((colon = strchr(path, PATH_SEP)))
 			*colon = 0;
 
-		len = list_commands_in_dir(other_cmds, path, prefix);
-		if (len > longest)
-			longest = len;
+		list_commands_in_dir(other_cmds, path, prefix);
 
 		if (!colon)
 			break;
@@ -220,14 +210,20 @@ unsigned int load_command_list(const char *prefix,
 	      sizeof(*other_cmds->names), cmdname_compare);
 	uniq(other_cmds);
 	exclude_cmds(other_cmds, main_cmds);
-
-	return longest;
 }
 
-void list_commands(const char *title, unsigned int longest,
-		struct cmdnames *main_cmds, struct cmdnames *other_cmds)
+void list_commands(const char *title, struct cmdnames *main_cmds,
+		   struct cmdnames *other_cmds)
 {
 	const char *exec_path = git_exec_path();
+	int i, longest = 0;
+
+	for (i = 0; i < main_cmds->cnt; i++)
+		if (longest < main_cmds->names[i]->len)
+			longest = main_cmds->names[i]->len;
+	for (i = 0; i < other_cmds->cnt; i++)
+		if (longest < other_cmds->names[i]->len)
+			longest = other_cmds->names[i]->len;
 
 	if (main_cmds->cnt) {
 		printf("available %s in '%s'\n", title, exec_path);
diff --git a/help.h b/help.h
index 3f1ae89..2733433 100644
--- a/help.h
+++ b/help.h
@@ -16,14 +16,14 @@ static inline void mput_char(char c, unsigned int num)
 		putchar(c);
 }
 
-unsigned int load_command_list(const char *prefix,
+void load_command_list(const char *prefix,
 		struct cmdnames *main_cmds,
 		struct cmdnames *other_cmds);
 void add_cmdname(struct cmdnames *cmds, const char *name, int len);
 /* Here we require that excludes is a sorted list. */
 void exclude_cmds(struct cmdnames *cmds, struct cmdnames *excludes);
 int is_in_cmdlist(struct cmdnames *c, const char *s);
-void list_commands(const char *title, unsigned int longest,
-		struct cmdnames *main_cmds, struct cmdnames *other_cmds);
+void list_commands(const char *title, struct cmdnames *main_cmds,
+		   struct cmdnames *other_cmds);
 
 #endif /* HELP_H */
-- 
1.6.0.1.150.g5966

[PATCH updated] git wrapper: DWIM mistyped commands

[Alex Riesen]

From: Johannes Schindelin <Johannes.Schindelin@gmx.de>

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 <johannes.schindelin@gmx.de>
Signed-off-by: Alex Riesen <raa.lkml@gmail.com>
---

Alex Riesen, Thu, Aug 28, 2008 19:15:33 +0200:
> 
> BTW, the Johannesses typo-guesser conflicts heavily in recent master.
> Pity. I'm going to rebase it and send out the rebased version.
> 

As promised. Johannes, I remember you talking about some problem with
that code (it should be the latest we talked about on the list), but I
am not sure I have updated the algorithm accordingly. Could you please
check?

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

diff --git a/Makefile b/Makefile
index bf400e6..3daa6dc 100644
--- a/Makefile
+++ b/Makefile
@@ -358,6 +358,7 @@ LIB_H += graph.h
 LIB_H += grep.h
 LIB_H += hash.h
 LIB_H += help.h
+LIB_H += levenshtein.h
 LIB_H += list-objects.h
 LIB_H += ll-merge.h
 LIB_H += log-tree.h
@@ -433,6 +434,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 f3502d3..e67cb20 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 37b1d76..54c5bfa 100644
--- a/git.c
+++ b/git.c
@@ -499,7 +499,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 1afbac0..981fb02 100644
--- a/help.c
+++ b/help.c
@@ -1,6 +1,7 @@
 #include "cache.h"
 #include "builtin.h"
 #include "exec_cmd.h"
+#include "levenshtein.h"
 #include "help.h"
 
 /* most GUI terminals set COLUMNS (although some don't export it) */
@@ -257,9 +258,70 @@ int is_in_cmdlist(struct cmdnames *c, const char *s)
 	return 0;
 }
 
-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];
+	static struct cmdnames main_cmds, other_cmds;
+
+	if (!getcwd(cwd, sizeof(cwd))) {
+		error("Could not get current working directory");
+		cwd[0] = '\0';
+	}
+
+	if (!main_cmds.cnt && !other_cmds.cnt)
+		load_command_list("git-", &main_cmds, &other_cmds);
+
+	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.106.g97c8

[PATCH] Add help.autocorrect to enable/disable autocorrecting

[Alex Riesen]

It is off(0) by default, to avoid scaring people unless they asked to.
If set to a non-0 value, wait for that amount of deciseconds before
running the corrected command.

Suggested by Junio, so he has a chance to hit Ctrl-C.

Signed-off-by: Alex Riesen <raa.lkml@gmail.com>
---
 Documentation/config.txt |    9 ++++++++
 help.c                   |   50 ++++++++++++++++++++++++++++++++++++++-------
 2 files changed, 51 insertions(+), 8 deletions(-)

diff --git a/Documentation/config.txt b/Documentation/config.txt
index af57d94..8c644ab 100644
--- a/Documentation/config.txt
+++ b/Documentation/config.txt
@@ -790,6 +790,15 @@ help.format::
 	Values 'man', 'info', 'web' and 'html' are supported. 'man' is
 	the default. 'web' and 'html' are the same.
 
+help.autocorrect::
+	Automatically correct and execute mistyped commands after
+	waiting for the given number of deciseconds (0.1 sec). If more
+	than one command can be deduced from the entered text, nothing
+	will be executed.  If the value of this option is negative,
+	the corrected command will be executed immediately. If the
+	value is 0 - the command will be just shown but not executed.
+	This is the default.
+
 http.proxy::
 	Override the HTTP proxy, normally configured using the 'http_proxy'
 	environment variable (see linkgit:curl[1]).  This can be overridden
diff --git a/help.c b/help.c
index 981fb02..7bfbbcd 100644
--- a/help.c
+++ b/help.c
@@ -38,6 +38,16 @@ void add_cmdname(struct cmdnames *cmds, const char *name, int len)
 	cmds->names[cmds->cnt++] = ent;
 }
 
+static void clean_cmdnames(struct cmdnames *cmds)
+{
+	int i;
+	for (i = 0; i < cmds->cnt; ++i)
+		free(cmds->names[i]);
+	free(cmds->names);
+	cmds->cnt = 0;
+	cmds->alloc = 0;
+}
+
 static int cmdname_compare(const void *a_, const void *b_)
 {
 	struct cmdname *a = *(struct cmdname **)a_;
@@ -258,6 +268,16 @@ int is_in_cmdlist(struct cmdnames *c, const char *s)
 	return 0;
 }
 
+static int autocorrect;
+
+static int git_unknown_cmd_config(const char *var, const char *value, void *cb)
+{
+	if (!strcmp(var, "help.autocorrect"))
+		autocorrect = git_config_int(var,value);
+
+	return git_default_config(var, value, cb);
+}
+
 static const char *levenshtein_cmd;
 static int similarity(const char *cmd) {
 	return levenshtein(levenshtein_cmd, cmd, 0, 2, 1, 4);
@@ -274,7 +294,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];
 	static struct cmdnames main_cmds, other_cmds;
 
@@ -283,6 +303,7 @@ const char *help_unknown_cmd(const char *cmd)
 		cwd[0] = '\0';
 	}
 
+	git_config(git_unknown_cmd_config, NULL);
 	if (!main_cmds.cnt && !other_cmds.cnt)
 		load_command_list("git-", &main_cmds, &other_cmds);
 
@@ -299,26 +320,39 @@ 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) {
+		const char *assumed;
 		if (!*cwd)
 			exit(1);
 		if (chdir(cwd))
 			die ("Could not change directory back to '%s'", cwd);
+		assumed = main_cmds.names[0]->name;
+		main_cmds.names[0] = NULL;
+		clean_cmdnames(&other_cmds);
+		clean_cmdnames(&main_cmds);
 		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;
+			cmd, assumed);
+		if (autocorrect > 0) {
+			fprintf(stderr, "in %0.1f seconds automatically...\n",
+				(float)autocorrect/10.0);
+			poll(NULL, 0, autocorrect * 100);
+		}
+		return assumed;
 	}
 
 	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.106.g97c8

Re: [PATCH] Add help.autocorrect to enable/disable autocorrecting

[Andreas Ericsson]

Alex Riesen wrote:
> It is off(0) by default, to avoid scaring people unless they asked to.
> If set to a non-0 value, wait for that amount of deciseconds before
> running the corrected command.
> 
> Suggested by Junio, so he has a chance to hit Ctrl-C.
> 

I'm just plain loving this :)

Liked-by: Andreas Ericsson <ae@op5.se>

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231

Re: [PATCH] Add help.autocorrect to enable/disable autocorrecting

[Junio C Hamano]

Alex Riesen <raa.lkml@gmail.com> writes:

> It is off(0) by default, to avoid scaring people unless they asked to.

I do not think this is off by default, by the way.  "off by default" means
that you would not waste extra cycles to compute the list of suggestions.

I am not suggesting that it should be "off" by default in that sense,
though.  I am just pointing out that it is not described correctly.

I also noticed that this does not seem to pay attention to mistyped
aliases.  Is it by design, oversight, or lazyness?

Re: [PATCH updated] git wrapper: DWIM mistyped commands

[Mikael Magnusson]

2008/8/28 Alex Riesen <raa.lkml@gmail.com>:
> From: Johannes Schindelin <Johannes.Schindelin@gmx.de>
>
> 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.

I merged the branch in pu into next, which I think should work, but I get
these segfaults for some commands... I tried running in gdb but even with
-g3 I only get nonsense backtraces, not sure why.

% git puhs
WARNING: You called a Git program named 'puhs', which does not exist.
Continuing under the assumption that you meant 'push'
in 2.0 seconds automatically...
zsh: segmentation fault  git puhs

% git ma
WARNING: You called a Git program named 'ma', which does not exist.
Continuing under the assumption that you meant 'am'
in 2.0 seconds automatically...
Nothing to do.

At this point I thought builtins crashed and scripts were fine, but...
% git ada
WARNING: You called a Git program named 'ada', which does not exist.
Continuing under the assumption that you meant 'add'
in 2.0 seconds automatically...
Nothing specified, nothing added.
Maybe you wanted to say 'git add .'?

However,
% git ada git.c
WARNING: You called a Git program named 'ada', which does not exist.
Continuing under the assumption that you meant 'add'
in 2.0 seconds automatically...
zsh: segmentation fault  git ada git.c

-- 
Mikael Magnusson

Re: [PATCH updated] git wrapper: DWIM mistyped commands

[Alex Riesen]

2008/8/29 Mikael Magnusson <mikachu@gmail.com>:
> I merged the branch in pu into next, which I think should work, but I get
> these segfaults for some commands... I tried running in gdb but even with

Can't reproduce in master, will try with next later, am busy right now, sorry.

> -g3 I only get nonsense backtraces, not sure why.

Remove -O2 from CFLAGS:

  $ make CFLAGS="-O0 -ggdb"

Re: [PATCH updated] git wrapper: DWIM mistyped commands

[Mikael Magnusson]

2008/8/30 Alex Riesen <raa.lkml@gmail.com>:
> 2008/8/29 Mikael Magnusson <mikachu@gmail.com>:
>> I merged the branch in pu into next, which I think should work, but I get
>> these segfaults for some commands... I tried running in gdb but even with
>
> Can't reproduce in master, will try with next later, am busy right now, sorry.
>
>> -g3 I only get nonsense backtraces, not sure why.
>
> Remove -O2 from CFLAGS:
>
>  $ make CFLAGS="-O0 -ggdb"

Hm, I only had CFLAGS set in the env, maybe that's not enough, or maybe it
was that I had it set to -gdwarf-2 -g3 instead of -ggdb3. At any rate, I got
this now:

% git fotch
Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0xa7ce56c0 (LWP 13043)]
0x41b61490 in ?? () from /lib/libc.so.6
(gdb) bt
#0  0x41b61490 in ?? () from /lib/libc.so.6
#1  0x41b634b0 in realloc () from /lib/libc.so.6
#2  0x41b62fdb in malloc () from /lib/libc.so.6
#3  0x080f63e6 in xmalloc (size=24) at wrapper.c:20
#4  0x080f6471 in xmemdupz (data=0x816a44f, len=23) at wrapper.c:45
#5  0x080f64e9 in xstrndup (str=0x816a44f "refs/remotes/origin/man",
len=23) at wrapper.c:54
#6  0x080dc05c in parse_refspec_internal (nr_refspec=6,
refspec=0x816a010, fetch=1, verify=0)
    at remote.c:505
#7  0x080dc3ca in parse_fetch_refspec (nr_refspec=6,
refspec=0x816a010) at remote.c:613
#8  0x080dc512 in remote_get (name=0x8169458 "origin") at remote.c:649
#9  0x0806cd4d in cmd_fetch (argc=0, argv=0xafc2d578, prefix=0x0) at
builtin-fetch.c:620
#10 0x0804bb3c in run_command (p=0x8123498, argc=1, argv=0xafc2d578)
at git.c:238
#11 0x0804bccc in handle_internal_command (argc=1, argv=0xafc2d578) at git.c:380
#12 0x0804bfea in main (argc=1, argv=0xafc2d578) at git.c:500
(gdb) bt full
#0  0x41b61490 in ?? () from /lib/libc.so.6
No symbol table info available.
#1  0x41b634b0 in realloc () from /lib/libc.so.6
No symbol table info available.
#2  0x41b62fdb in malloc () from /lib/libc.so.6
No symbol table info available.
#3  0x080f63e6 in xmalloc (size=24) at wrapper.c:20
	ret = (void *) 0x0
#4  0x080f6471 in xmemdupz (data=0x816a44f, len=23) at wrapper.c:45
	p = 0x0
#5  0x080f64e9 in xstrndup (str=0x816a44f "refs/remotes/origin/man",
len=23) at wrapper.c:54
	p = 0x0
#6  0x080dc05c in parse_refspec_internal (nr_refspec=6,
refspec=0x816a010, fetch=1, verify=0)
    at remote.c:505
	rlen = 23
	llen = 0
	is_glob = 0
	lhs = 0x816a440 "refs/heads/man:refs/remotes/origin/man"
	rhs = 0x816a44f "refs/remotes/origin/man"
	i = 4
	st = 0
	rs = (struct refspec *) 0x8169d88
#7  0x080dc3ca in parse_fetch_refspec (nr_refspec=6,
refspec=0x816a010) at remote.c:613
No locals.
#8  0x080dc512 in remote_get (name=0x8169458 "origin") at remote.c:649
	ret = (struct remote *) 0x8169ef0
#9  0x0806cd4d in cmd_fetch (argc=0, argv=0xafc2d578, prefix=0x0) at
builtin-fetch.c:620
	remote = (struct remote *) 0x804b2d4
	i = 1
---Type <return> to continue, or q <return> to quit---
	ref_nr = 0
	exit_code = 0
	refs = (const char **) 0x0
#10 0x0804bb3c in run_command (p=0x8123498, argc=1, argv=0xafc2d578)
at git.c:238
	status = -1346186104
	st = {st_dev = 582794214293012544, __pad1 = 0, __st_ino = 1103151906,
st_mode = 5,
  st_nlink = 0, st_uid = 0, st_gid = 135692352, st_rdev =
582794423264539853, __pad2 = 54328,
  st_size = 579290465871466043, st_blksize = 0, st_blocks =
577791495034295448, st_atim = {
    tv_sec = -1346180215, tv_nsec = 1103274272}, st_mtim = {tv_sec = 135692296,
    tv_nsec = 1103269876}, st_ctim = {tv_sec = 1090632864, tv_nsec = 0},
  st_ino = 580626572881613928}
	prefix = 0x0
#11 0x0804bccc in handle_internal_command (argc=1, argv=0xafc2d578) at git.c:380
	p = (struct cmd_struct *) 0x8123498
	cmd = 0x8169a3c "fetch"
	i = 26
	commands = {{cmd = 0x8104ebd "add", fn = 0x804c905 <cmd_add>, option = 5}, {
    cmd = 0x8104ec1 "annotate", fn = 0x804cc70 <cmd_annotate>, option = 1}, {
    cmd = 0x8104eca "apply", fn = 0x805362c <cmd_apply>, option = 0}, {
    cmd = 0x8104ed0 "archive", fn = 0x80542e5 <cmd_archive>, option = 0}, {
    cmd = 0x8104ed8 "blame", fn = 0x805889e <cmd_blame>, option = 1},
{cmd = 0x8104ede "branch",
    fn = 0x805a62f <cmd_branch>, option = 1}, {cmd = 0x8104ee5 "bundle",
    fn = 0x805adb8 <cmd_bundle>, option = 0}, {cmd = 0x8104eec "cat-file",
    fn = 0x805b6b1 <cmd_cat_file>, option = 1}, {cmd = 0x8104ef5 "checkout",
    fn = 0x805d865 <cmd_checkout>, option = 5}, {cmd = 0x8104efe
"checkout-index",
    fn = 0x805c123 <cmd_checkout_index>, option = 5}, {cmd = 0x8104f0d
"check-ref-format",
    fn = 0x805bb84 <cmd_check_ref_format>, option = 0}, {cmd =
0x8104f1e "check-attr",
    fn = 0x805b94c <cmd_check_attr>, option = 1}, {cmd = 0x8104f29 "cherry",
    fn = 0x8078c23 <cmd_cherry>, option = 1}, {cmd = 0x8104f30 "cherry-pick",
---Type <return> to continue, or q <return> to quit---
    fn = 0x8094c96 <cmd_cherry_pick>, option = 5}, {cmd = 0x8104f3c "clone",
    fn = 0x805ef85 <cmd_clone>, option = 0}, {cmd = 0x8104f42 "clean",
    fn = 0x805ddb3 <cmd_clean>, option = 5}, {cmd = 0x8104f48 "commit",
    fn = 0x8062115 <cmd_commit>, option = 5}, {cmd = 0x8104f4f "commit-tree",
    fn = 0x805fcbd <cmd_commit_tree>, option = 1}, {cmd = 0x8104f5b "config",
    fn = 0x80632c5 <cmd_config>, option = 0}, {cmd = 0x8104f62 "count-objects",
    fn = 0x8063f14 <cmd_count_objects>, option = 1}, {cmd = 0x8104f70
"describe",
    fn = 0x8064ce4 <cmd_describe>, option = 1}, {cmd = 0x8104f79 "diff",
    fn = 0x80663da <cmd_diff>, option = 0}, {cmd = 0x8104f7e "diff-files",
    fn = 0x80650d8 <cmd_diff_files>, option = 1}, {cmd = 0x8104f89
"diff-index",
    fn = 0x806530c <cmd_diff_index>, option = 1}, {cmd = 0x8104f94 "diff-tree",
    fn = 0x80657f0 <cmd_diff_tree>, option = 1}, {cmd = 0x8104f9e
"fast-export",
    fn = 0x8067c10 <cmd_fast_export>, option = 1}, {cmd = 0x8104faa "fetch",
    fn = 0x806ccb5 <cmd_fetch>, option = 1}, {cmd = 0x8104fb0 "fetch-pack",
    fn = 0x806adeb <cmd_fetch_pack>, option = 1}, {cmd = 0x8104fbb
"fetch--tool",
    fn = 0x80692be <cmd_fetch__tool>, option = 1}, {cmd = 0x8104fc7
"fmt-merge-msg",
    fn = 0x806defb <cmd_fmt_merge_msg>, option = 1}, {cmd = 0x8104fd5
"for-each-ref",
    fn = 0x806fc5b <cmd_for_each_ref>, option = 1}, {cmd = 0x8104fe2
"format-patch",
    fn = 0x8077b7e <cmd_format_patch>, option = 1}, {cmd = 0x8104fef "fsck",
    fn = 0x8071106 <cmd_fsck>, option = 1}, {cmd = 0x8104ff4 "fsck-objects",
    fn = 0x8071106 <cmd_fsck>, option = 1}, {cmd = 0x8105001 "gc", fn
= 0x80719b9 <cmd_gc>,
    option = 1}, {cmd = 0x8105004 "get-tar-commit-id", fn = 0x809be66
<cmd_get_tar_commit_id>,
    option = 0}, {cmd = 0x8105016 "grep", fn = 0x807308e <cmd_grep>,
option = 3}, {
    cmd = 0x810501b "help", fn = 0x8074bd2 <cmd_help>, option = 0}, {
    cmd = 0x8105020 "http-fetch", fn = 0x80a057c <cmd_http_fetch>,
option = 1}, {
    cmd = 0x810502b "init", fn = 0x8075a8d <cmd_init_db>, option = 0}, {
    cmd = 0x8105030 "init-db", fn = 0x8075a8d <cmd_init_db>, option = 0}, {
    cmd = 0x8105038 "log", fn = 0x8076c36 <cmd_log>, option = 3}, {cmd
= 0x810503c "ls-files",
    fn = 0x8079e63 <cmd_ls_files>, option = 1}, {cmd = 0x8105045 "ls-tree",
---Type <return> to continue, or q <return> to quit---
    fn = 0x807ae13 <cmd_ls_tree>, option = 1}, {cmd = 0x810504d "ls-remote",
    fn = 0x807a797 <cmd_ls_remote>, option = 0}, {cmd = 0x8105057 "mailinfo",
    fn = 0x807d1ef <cmd_mailinfo>, option = 0}, {cmd = 0x8105060 "mailsplit",
    fn = 0x807db6e <cmd_mailsplit>, option = 0}, {cmd = 0x810506a "merge",
    fn = 0x808016f <cmd_merge>, option = 5}, {cmd = 0x8105070 "merge-base",
    fn = 0x8080fe6 <cmd_merge_base>, option = 1}, {cmd = 0x810507b
"merge-file",
    fn = 0x80810f0 <cmd_merge_file>, option = 0}, {cmd = 0x8105086
"merge-ours",
    fn = 0x8081438 <cmd_merge_ours>, option = 1}, {cmd = 0x8105091
"merge-recursive",
    fn = 0x8084c44 <cmd_merge_recursive>, option = 5}, {cmd =
0x81050a1 "merge-subtree",
    fn = 0x8084c44 <cmd_merge_recursive>, option = 5}, {cmd = 0x81050af "mv",
    fn = 0x808509d <cmd_mv>, option = 5}, {cmd = 0x81050b2 "name-rev",
    fn = 0x8086090 <cmd_name_rev>, option = 1}, {cmd = 0x81050bb
"pack-objects",
    fn = 0x808aa1a <cmd_pack_objects>, option = 1}, {cmd = 0x81050c8
"peek-remote",
    fn = 0x807a797 <cmd_ls_remote>, option = 0}, {cmd = 0x81050d4 "pickaxe",
    fn = 0x805889e <cmd_blame>, option = 1}, {cmd = 0x81050dc "prune",
    fn = 0x808badd <cmd_prune>, option = 1}, {cmd = 0x81050e2 "prune-packed",
    fn = 0x808b60a <cmd_prune_packed>, option = 1}, {cmd = 0x81050ef "push",
    fn = 0x808bf9f <cmd_push>, option = 1}, {cmd = 0x81050f4 "read-tree",
    fn = 0x808c418 <cmd_read_tree>, option = 1}, {cmd = 0x81050fe "reflog",
    fn = 0x808e264 <cmd_reflog>, option = 1}, {cmd = 0x8105105 "remote",
    fn = 0x8090076 <cmd_remote>, option = 1}, {cmd = 0x810510c "repo-config",
    fn = 0x80632c5 <cmd_config>, option = 0}, {cmd = 0x8105118 "rerere",
    fn = 0x8090669 <cmd_rerere>, option = 1}, {cmd = 0x810511f "reset",
    fn = 0x8090e44 <cmd_reset>, option = 1}, {cmd = 0x8105125 "rev-list",
    fn = 0x8092096 <cmd_rev_list>, option = 1}, {cmd = 0x810512e "rev-parse",
    fn = 0x80932a0 <cmd_rev_parse>, option = 0}, {cmd = 0x8105138 "revert",
    fn = 0x8094c4e <cmd_revert>, option = 5}, {cmd = 0x810513f "rm",
fn = 0x80950b5 <cmd_rm>,
    option = 1}, {cmd = 0x8105142 "send-pack", fn = 0x8096982
<cmd_send_pack>, option = 1}, {
    cmd = 0x810514c "shortlog", fn = 0x809769a <cmd_shortlog>, option = 2}, {
---Type <return> to continue, or q <return> to quit---
    cmd = 0x8105155 "show-branch", fn = 0x8098c0c <cmd_show_branch>,
option = 1}, {
    cmd = 0x8105161 "show", fn = 0x80767e8 <cmd_show>, option = 3},
{cmd = 0x8105166 "status",
    fn = 0x8061d60 <cmd_status>, option = 5}, {cmd = 0x810516d "stripspace",
    fn = 0x809a78d <cmd_stripspace>, option = 0}, {cmd = 0x8105178
"symbolic-ref",
    fn = 0x809a8db <cmd_symbolic_ref>, option = 1}, {cmd = 0x8105185 "tag",
    fn = 0x809b51a <cmd_tag>, option = 1}, {cmd = 0x8105189 "tar-tree",
    fn = 0x809bca4 <cmd_tar_tree>, option = 0}, {cmd = 0x8105192
"unpack-objects",
    fn = 0x809d17c <cmd_unpack_objects>, option = 1}, {cmd = 0x81051a1
"update-index",
    fn = 0x809e85c <cmd_update_index>, option = 1}, {cmd = 0x81051ae
"update-ref",
    fn = 0x809f1d8 <cmd_update_ref>, option = 1}, {cmd = 0x81051b9
"upload-archive",
    fn = 0x809f7a8 <cmd_upload_archive>, option = 0}, {cmd = 0x81051c8
"verify-tag",
    fn = 0x80a0353 <cmd_verify_tag>, option = 1}, {cmd = 0x81051d3 "version",
    fn = 0x80c5376 <cmd_version>, option = 0}, {cmd = 0x81051db "whatchanged",
    fn = 0x80764c0 <cmd_whatchanged>, option = 3}, {cmd = 0x81051e7
"write-tree",
    fn = 0x80a0434 <cmd_write_tree>, option = 1}, {cmd = 0x81051f2
"verify-pack",
    fn = 0x809ff24 <cmd_verify_pack>, option = 0}, {cmd = 0x81051fe "show-ref",
    fn = 0x809a0cc <cmd_show_ref>, option = 1}, {cmd = 0x8105207 "pack-refs",
    fn = 0x808b2e8 <cmd_pack_refs>, option = 1}}
	ext = ""
#12 0x0804bfea in main (argc=1, argv=0xafc2d578) at git.c:500
	cmd = 0xafc2eb89 "fotch"
	slash = 0xafc2eb85 "git"
	done_alias = 0

-- 
Mikael Magnusson

[PATCH] git wrapper: DWIM mistyped commands

[Alex Riesen]

From: Johannes Schindelin <Johannes.Schindelin@gmx.de>

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 <johannes.schindelin@gmx.de>
Signed-off-by: Alex Riesen <raa.lkml@gmail.com>
---

Junio C Hamano, Sat, Aug 30, 2008 19:26:17 +0200:
> I think you do not need the file-scope static levenshtein_cmd anymore with
> this change, if you make similarity() take two command names.  No?

Yes :)

> Please reroll the whole f66dd34 (git wrapper: DWIM mistyped commands,
> 2008-08-28), as it is not part of any solid integration branch yet.

I think I better reroll (now) both

> You might also want to update the commit log message to talk about the
> "len" reuse hack, but you already have in-code comment which might be
> sufficient.

I believe it is (and I added one against the member in the
declaration)

Mikael, this also might fix the crash you're seeing: the heap was
corrupted by clean_cmdnames(&other_cmds) names members of which were
moved to main_cmds.

 Makefile      |    2 +
 builtin.h     |    2 +-
 git.c         |    4 ++-
 help.c        |   72 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 help.h        |    2 +-
 levenshtein.c |   47 +++++++++++++++++++++++++++++++++++++
 levenshtein.h |    8 ++++++
 7 files changed, 133 insertions(+), 4 deletions(-)
 create mode 100644 levenshtein.c
 create mode 100644 levenshtein.h

diff --git a/Makefile b/Makefile
index bf400e6..3daa6dc 100644
--- a/Makefile
+++ b/Makefile
@@ -358,6 +358,7 @@ LIB_H += graph.h
 LIB_H += grep.h
 LIB_H += hash.h
 LIB_H += help.h
+LIB_H += levenshtein.h
 LIB_H += list-objects.h
 LIB_H += ll-merge.h
 LIB_H += log-tree.h
@@ -433,6 +434,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 f3502d3..e67cb20 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 37b1d76..54c5bfa 100644
--- a/git.c
+++ b/git.c
@@ -499,7 +499,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 b278257..aaba809 100644
--- a/help.c
+++ b/help.c
@@ -1,6 +1,7 @@
 #include "cache.h"
 #include "builtin.h"
 #include "exec_cmd.h"
+#include "levenshtein.h"
 #include "help.h"
 
 /* most GUI terminals set COLUMNS (although some don't export it) */
@@ -37,6 +38,16 @@ void add_cmdname(struct cmdnames *cmds, const char *name, int len)
 	cmds->names[cmds->cnt++] = ent;
 }
 
+static void clean_cmdnames(struct cmdnames *cmds)
+{
+	int i;
+	for (i = 0; i < cmds->cnt; ++i)
+		free(cmds->names[i]);
+	free(cmds->names);
+	cmds->cnt = 0;
+	cmds->alloc = 0;
+}
+
 static int cmdname_compare(const void *a_, const void *b_)
 {
 	struct cmdname *a = *(struct cmdname **)a_;
@@ -250,9 +261,68 @@ int is_in_cmdlist(struct cmdnames *c, const char *s)
 	return 0;
 }
 
-void help_unknown_cmd(const char *cmd)
+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 = (*c1)->len;
+	int l2 = (*c2)->len;
+	return l1 != l2 ? l1 - l2 : strcmp(s1, s2);
+}
+
+const char *help_unknown_cmd(const char *cmd)
 {
+	int i, n, best_similarity = 0;
+	struct cmdnames main_cmds, other_cmds;
+
+	memset(&main_cmds, 0, sizeof(main_cmds));
+	memset(&other_cmds, 0, sizeof(main_cmds));
+
+	load_command_list("git-", &main_cmds, &other_cmds);
+
+	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;
+	free(other_cmds.names);
+
+	/* This reuses cmdname->len for similarity index */
+	for (i = 0; i < main_cmds.cnt; ++i)
+		main_cmds.names[i]->len =
+			levenshtein(cmd, main_cmds.names[i]->name, 0, 2, 1, 4);
+
+	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 = main_cmds.names[0]->len;
+	n = 1;
+	while (n < main_cmds.cnt && best_similarity == main_cmds.names[n]->len)
+		++n;
+	if (n == 1) {
+		const char *assumed = main_cmds.names[0]->name;
+		main_cmds.names[0] = NULL;
+		clean_cmdnames(&main_cmds);
+		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, assumed);
+		return assumed;
+	}
+
 	fprintf(stderr, "git: '%s' is not a git-command. See 'git --help'.\n", cmd);
+
+	if (best_similarity < 6) {
+		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);
+	}
+
 	exit(1);
 }
 
diff --git a/help.h b/help.h
index 2733433..56bc154 100644
--- a/help.h
+++ b/help.h
@@ -5,7 +5,7 @@ struct cmdnames {
 	int alloc;
 	int cnt;
 	struct cmdname {
-		size_t len;
+		size_t len; /* also used for similarity index in help.c */
 		char name[FLEX_ARRAY];
 	} **names;
 };
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.1.168.gdf6f0

[PATCH] Add help.autocorrect to enable/disable autocorrecting

[Alex Riesen]

It is off(0) by default, to avoid scaring people unless they asked to.
If set to a non-0 value, wait for that amount of deciseconds before
running the corrected command.

Suggested by Junio, so he has a chance to hit Ctrl-C.

Signed-off-by: Alex Riesen <raa.lkml@gmail.com>
---
Alex Riesen, Sun, Aug 31, 2008 15:50:23 +0200:
> Junio C Hamano, Sat, Aug 30, 2008 19:26:17 +0200:
> > Please reroll the whole f66dd34 (git wrapper: DWIM mistyped commands,
> > 2008-08-28), as it is not part of any solid integration branch yet.
> 
> I think I better reroll (now) both
> 

 Documentation/config.txt |    9 +++++++++
 help.c                   |   19 ++++++++++++++++++-
 2 files changed, 27 insertions(+), 1 deletions(-)

diff --git a/Documentation/config.txt b/Documentation/config.txt
index af57d94..8c644ab 100644
--- a/Documentation/config.txt
+++ b/Documentation/config.txt
@@ -790,6 +790,15 @@ help.format::
 	Values 'man', 'info', 'web' and 'html' are supported. 'man' is
 	the default. 'web' and 'html' are the same.
 
+help.autocorrect::
+	Automatically correct and execute mistyped commands after
+	waiting for the given number of deciseconds (0.1 sec). If more
+	than one command can be deduced from the entered text, nothing
+	will be executed.  If the value of this option is negative,
+	the corrected command will be executed immediately. If the
+	value is 0 - the command will be just shown but not executed.
+	This is the default.
+
 http.proxy::
 	Override the HTTP proxy, normally configured using the 'http_proxy'
 	environment variable (see linkgit:curl[1]).  This can be overridden
diff --git a/help.c b/help.c
index aaba809..300cd38 100644
--- a/help.c
+++ b/help.c
@@ -261,6 +261,16 @@ int is_in_cmdlist(struct cmdnames *c, const char *s)
 	return 0;
 }
 
+static int autocorrect;
+
+static int git_unknown_cmd_config(const char *var, const char *value, void *cb)
+{
+	if (!strcmp(var, "help.autocorrect"))
+		autocorrect = git_config_int(var,value);
+
+	return git_default_config(var, value, cb);
+}
+
 static int levenshtein_compare(const void *p1, const void *p2)
 {
 	const struct cmdname *const *c1 = p1, *const *c2 = p2;
@@ -278,6 +288,8 @@ const char *help_unknown_cmd(const char *cmd)
 	memset(&main_cmds, 0, sizeof(main_cmds));
 	memset(&other_cmds, 0, sizeof(main_cmds));
 
+	git_config(git_unknown_cmd_config, NULL);
+
 	load_command_list("git-", &main_cmds, &other_cmds);
 
 	ALLOC_GROW(main_cmds.names, main_cmds.cnt + other_cmds.cnt,
@@ -302,7 +314,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 (n == 1) {
+	if (autocorrect && n == 1) {
 		const char *assumed = main_cmds.names[0]->name;
 		main_cmds.names[0] = NULL;
 		clean_cmdnames(&main_cmds);
@@ -310,6 +322,11 @@ const char *help_unknown_cmd(const char *cmd)
 			"which does not exist.\n"
 			"Continuing under the assumption that you meant '%s'\n",
 			cmd, assumed);
+		if (autocorrect > 0) {
+			fprintf(stderr, "in %0.1f seconds automatically...\n",
+				(float)autocorrect/10.0);
+			poll(NULL, 0, autocorrect * 100);
+		}
 		return assumed;
 	}
 
-- 
1.6.0.1.168.gdf6f0

Re: [PATCH] Add help.autocorrect to enable/disable autocorrecting

[Matthieu Moy]

Alex Riesen <raa.lkml@gmail.com> writes:

> It is off(0) by default, to avoid scaring people unless they asked to.
> If set to a non-0 value, wait for that amount of deciseconds before
> running the corrected command.

Perhaps off should be -1 (or, say, anything negative), so that the
value 0 can be used to mean "execute the corrected command without
waiting".

(not that I really care personnally, I'd probably keep it off anyway).

-- 
Matthieu

Re: [PATCH] Add help.autocorrect to enable/disable autocorrecting

[Junio C Hamano]

Matthieu Moy <Matthieu.Moy@imag.fr> writes:

> Alex Riesen <raa.lkml@gmail.com> writes:
>
>> It is off(0) by default, to avoid scaring people unless they asked to.
>> If set to a non-0 value, wait for that amount of deciseconds before
>> running the corrected command.
>
> Perhaps off should be -1 (or, say, anything negative), so that the
> value 0 can be used to mean "execute the corrected command without
> waiting".
>
> (not that I really care personnally, I'd probably keep it off anyway).

I do not want to suggest this because I do not think of a good way to
implement it myself, but it would be very nice if this feature can be
enabled by default for interactive session and disabled for scripts.

Well, actually I think I do ;-)

Perhaps have a bash alias that does:

	alias git="git --dwim"

only in interactive session (ensuring "only in interactive" is the
responsibility of the end user), with the global option similar to
the "--paginate" that "git" wrapper itself takes?

Re: [PATCH] git wrapper: DWIM mistyped commands

[Mikael Magnusson]

2008/8/31 Alex Riesen <raa.lkml@gmail.com>:
> From: Johannes Schindelin <Johannes.Schindelin@gmx.de>
>
> 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'
>        [...]

> Mikael, this also might fix the crash you're seeing: the heap was
> corrupted by clean_cmdnames(&other_cmds) names members of which were
> moved to main_cmds.

It doesn't crash now, but the cut-off appears ineffective:
% git aaaaaaaaaaaaaaa
WARNING: You called a Git program named 'aaaaaaaaaaaaaaa', which does not exist.
Continuing under the assumption that you meant 'add--interactive'
in 2.0 seconds automatically...

By my estimate, that should have a score above 6 :).

-- 
Mikael Magnusson

Re: [PATCH updated] git wrapper: DWIM mistyped commands

[Alex Riesen]

Mikael Magnusson, Sat, Aug 30, 2008 12:33:26 +0200:
> 2008/8/30 Alex Riesen <raa.lkml@gmail.com>:
> > 2008/8/29 Mikael Magnusson <mikachu@gmail.com>:
> >> I merged the branch in pu into next, which I think should work, but I get
> >> these segfaults for some commands... I tried running in gdb but even with
> >
> > Can't reproduce in master, will try with next later, am busy right now, sorry.
> >
> >> -g3 I only get nonsense backtraces, not sure why.
> >
> > Remove -O2 from CFLAGS:
> >
> >  $ make CFLAGS="-O0 -ggdb"
> 
> Hm, I only had CFLAGS set in the env, maybe that's not enough, or maybe it

The make variables set in Makefile take precedence over the variables
with same names in environment (see make(1), "-e" option).

> was that I had it set to -gdwarf-2 -g3 instead of -ggdb3. At any rate, I got
> this now:
> 
> % git fotch
> Program received signal SIGSEGV, Segmentation fault.
> [Switching to Thread 0xa7ce56c0 (LWP 13043)]
> 0x41b61490 in ?? () from /lib/libc.so.6
> (gdb) bt
> #0  0x41b61490 in ?? () from /lib/libc.so.6
> #1  0x41b634b0 in realloc () from /lib/libc.so.6
> #2  0x41b62fdb in malloc () from /lib/libc.so.6
> #3  0x080f63e6 in xmalloc (size=24) at wrapper.c:20
> #4  0x080f6471 in xmemdupz (data=0x816a44f, len=23) at wrapper.c:45
> #5  0x080f64e9 in xstrndup (str=0x816a44f "refs/remotes/origin/man",
> len=23) at wrapper.c:54
> #6  0x080dc05c in parse_refspec_internal (nr_refspec=6,
> refspec=0x816a010, fetch=1, verify=0)
>     at remote.c:505

Looks like heap corruption. See that patch I sent today.

Re: [PATCH updated] git wrapper: DWIM mistyped commands

[Junio C Hamano]

Alex Riesen <raa.lkml@gmail.com> writes:

> @@ -257,9 +258,70 @@ int is_in_cmdlist(struct cmdnames *c, const char *s)
> ...
> +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);
> +}
> ...
> +	levenshtein_cmd = cmd;
> +	qsort(main_cmds.names, main_cmds.cnt,
> +	      sizeof(*main_cmds.names), levenshtein_compare);

Isn't this awfully inefficient?

You have one mistyped command name to compute distance against, and want
to sort the available 100+ command names by that distance.  In qsort(),
levenshtein_compare() will be called O(N log N) times (depending on your
qsort implementation)?

I wonder if it makes sense to give an otherwise unused "score" member to
the "struct cmdname", compute the distance only once per each command, and
use that as the sort key (alternatively you can have a separate int[N]
array to store similarity values for each item in the cmdnames list, only
used inside this codepath).

Re: [PATCH updated] git wrapper: DWIM mistyped commands

[Alex Riesen]

2008/8/30 Junio C Hamano <gitster@pobox.com>:
>> +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);
>> +}
>> ...
>> +     levenshtein_cmd = cmd;
>> +     qsort(main_cmds.names, main_cmds.cnt,
>> +           sizeof(*main_cmds.names), levenshtein_compare);
>
> Isn't this awfully inefficient?
>
> You have one mistyped command name to compute distance against, and want
> to sort the available 100+ command names by that distance.  In qsort(),
> levenshtein_compare() will be called O(N log N) times (depending on your
> qsort implementation)?

not only similarity, but strcmp as well.

> I wonder if it makes sense to give an otherwise unused "score" member to

Hmm, it is a _non-existing_ member of cmdname, isn't it?

> the "struct cmdname", compute the distance only once per each command, and
> use that as the sort key (alternatively you can have a separate int[N]
> array to store similarity values for each item in the cmdnames list, only
> used inside this codepath).

I think I'll take the struct cmdname->len over.

[PATCH] Reuse cmdname->len to store pre-calculated similarity indexes

[Alex Riesen]

To avoid doing that while sorting

Signed-off-by: Alex Riesen <raa.lkml@gmail.com>
---

Alex Riesen, Sat, Aug 30, 2008 18:44:15 +0200:
> 2008/8/30 Junio C Hamano <gitster@pobox.com>:
> > I wonder if it makes sense to give an otherwise unused "score" member to
> 
> Hmm, it is a _non-existing_ member of cmdname, isn't it?
> 
> > the "struct cmdname", compute the distance only once per each command, and
> > use that as the sort key (alternatively you can have a separate int[N]
> > array to store similarity values for each item in the cmdnames list, only
> > used inside this codepath).
> 
> I think I'll take the struct cmdname->len over.

 help.c |   12 +++++++-----
 1 files changed, 7 insertions(+), 5 deletions(-)

diff --git a/help.c b/help.c
index 7bfbbcd..70d57a3 100644
--- a/help.c
+++ b/help.c
@@ -287,8 +287,8 @@ 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);
+	int l1 = (*c1)->len;
+	int l2 = (*c2)->len;
 	return l1 != l2 ? l1 - l2 : strcmp(s1, s2);
 }
 
@@ -312,6 +312,9 @@ const char *help_unknown_cmd(const char *cmd)
 	memcpy(main_cmds.names + main_cmds.cnt, other_cmds.names,
 		other_cmds.cnt * sizeof(other_cmds.names[0]));
 	main_cmds.cnt += other_cmds.cnt;
+	/* This reuses cmdname->len for similarity index */
+	for (i = 0; i < main_cmds.cnt; ++i)
+		main_cmds.names[i]->len = similarity(main_cmds.names[i]->name);
 
 	levenshtein_cmd = cmd;
 	qsort(main_cmds.names, main_cmds.cnt,
@@ -319,10 +322,9 @@ 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);
+	best_similarity = main_cmds.names[0]->len;
 	n = 1;
-	while (n < main_cmds.cnt &&
-		best_similarity == similarity(main_cmds.names[n]->name))
+	while (n < main_cmds.cnt && best_similarity == main_cmds.names[n]->len)
 		++n;
 	if (autocorrect && n == 1) {
 		const char *assumed;
-- 
1.6.0.1.149.g9ecb0

Re: [PATCH] Reuse cmdname->len to store pre-calculated similarity indexes

[Junio C Hamano]

Alex Riesen <raa.lkml@gmail.com> writes:

> To avoid doing that while sorting
>
> Signed-off-by: Alex Riesen <raa.lkml@gmail.com>
> ---
>
> Alex Riesen, Sat, Aug 30, 2008 18:44:15 +0200:
>> 2008/8/30 Junio C Hamano <gitster@pobox.com>:
>> > I wonder if it makes sense to give an otherwise unused "score" member to
>> 
>> Hmm, it is a _non-existing_ member of cmdname, isn't it?
>> 
>> > the "struct cmdname", compute the distance only once per each command, and
>> > use that as the sort key (alternatively you can have a separate int[N]
>> > array to store similarity values for each item in the cmdnames list, only
>> > used inside this codepath).
>> 
>> I think I'll take the struct cmdname->len over.

I think you do not need the file-scope static levenshtein_cmd anymore with
this change, if you make similarity() take two command names.  No?

Please reroll the whole f66dd34 (git wrapper: DWIM mistyped commands,
2008-08-28), as it is not part of any solid integration branch yet.

You might also want to update the commit log message to talk about the
"len" reuse hack, but you already have in-code comment which might be
sufficient.

Re: [PATCH updated] git wrapper: DWIM mistyped commands

[Felipe Carvalho Oliveira]

> From: Johannes Schindelin <Johannes.Schindelin@gmx.de>
>
> 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:

 Thanks so much by implement this. Few weeks ago I had thought about this.

  Felipe(from Brazil)