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

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

---

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

index 391f749..9225102 100644
@@ -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;
 	}

index d6bcbec..dcd08f7 100644
@@ -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];

index 1afbac0..a17a746 100644
@@ -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);

index 3f1ae89..2733433 100644
@@ -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

From: Johannes Schindelin <[email protected]>

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'
	[...]

---

Alex Riesen, Thu, Aug 28, 2008 19:15:33 +0200:

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

index bf400e6..3daa6dc 100644
@@ -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

index f3502d3..e67cb20 100644
@@ -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,

index 37b1d76..54c5bfa 100644
@@ -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",

new file mode 100644
index 0000000..0173abe
@@ -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

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.

---
 Documentation/config.txt |    9 ++++++++
 help.c                   |   50 ++++++++++++++++++++++++++++++++++++++-------
 2 files changed, 51 insertions(+), 8 deletions(-)

index af57d94..8c644ab 100644
@@ -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

1.6.0.106.g97c8

I'm just plain loving this :)

Andreas Ericsson                   [email protected]
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231

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?

2008/8/28 Alex Riesen <[email protected]>:

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

2008/8/29 Mikael Magnusson <[email protected]>:

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

Remove -O2 from CFLAGS:

  $ make CFLAGS="-O0 -ggdb"

2008/8/30 Alex Riesen <[email protected]>:

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

Mikael Magnusson, Sat, Aug 30, 2008 12:33:26 +0200:

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

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

2008/8/30 Junio C Hamano <[email protected]>:

not only similarity, but strcmp as well.

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

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

To avoid doing that while sorting

---

Alex Riesen, Sat, Aug 30, 2008 18:44:15 +0200:

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

index 7bfbbcd..70d57a3 100644
@@ -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

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.

From: Johannes Schindelin <[email protected]>

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'
	[...]

---

Junio C Hamano, Sat, Aug 30, 2008 19:26:17 +0200:

Yes :)

I think I better reroll (now) both

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

index bf400e6..3daa6dc 100644
@@ -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

index f3502d3..e67cb20 100644
@@ -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,

index 37b1d76..54c5bfa 100644
@@ -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",

index 2733433..56bc154 100644
@@ -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;
 };

new file mode 100644
index 0000000..0173abe
@@ -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

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.

---
Alex Riesen, Sun, Aug 31, 2008 15:50:23 +0200:

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

index af57d94..8c644ab 100644
@@ -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

index aaba809..300cd38 100644
@@ -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

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

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?

2008/8/31 Alex Riesen <[email protected]>:

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

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

Felipe(from Brazil)