Add spelling suggestions for four cases:

1. For targets, when invoking ninja to build a target.
2. For targets, when doing a "query" command.
3. For command names.
4. For the subcommands of the "targets" command.

Also change CmdTargets() to call LookupNode() instead of GetNode() --
since the result was checked for NULL, that's probably what was intended
here originally.

10 files changed, 87 insertions, 8 deletions

diff --git a/src/edit_distance.cc b/src/edit_distance.cc
index fe05f64..22db4fe 100644
--- a/src/edit_distance.cc
+++ b/src/edit_distance.cc
@@ -16,8 +16,6 @@
 
 #include <vector>
 
-#include "string_piece.h"
-
 int EditDistance(const StringPiece& s1,
                  const StringPiece& s2,
                  bool allow_replacements,
diff --git a/src/edit_distance.h b/src/edit_distance.h
index 186a0d7..45ae4ae 100644
--- a/src/edit_distance.h
+++ b/src/edit_distance.h
@@ -15,7 +15,7 @@
 #ifndef NINJA_EDIT_DISTANCE_H_
 #define NINJA_EDIT_DISTANCE_H_
 
-struct StringPiece;
+#include "string_piece.h"
 
 int EditDistance(const StringPiece& s1,
                  const StringPiece& s2,
diff --git a/src/edit_distance_test.cc b/src/edit_distance_test.cc
index a4c0486..9dc0f82 100644
--- a/src/edit_distance_test.cc
+++ b/src/edit_distance_test.cc
@@ -14,7 +14,6 @@
 
 #include "edit_distance.h"
 
-#include "string_piece.h"
 #include "test.h"
 
 TEST(EditDistanceTest, TestEmpty) {
diff --git a/src/ninja.cc b/src/ninja.cc
index 47693d1..b2c8da0 100644
--- a/src/ninja.cc
+++ b/src/ninja.cc
@@ -36,6 +36,7 @@
 #include "build.h"
 #include "build_log.h"
 #include "clean.h"
+#include "edit_distance.h"
 #include "graph.h"
 #include "graphviz.h"
 #include "parsers.h"
@@ -170,6 +171,11 @@ bool CollectTargetsFromArgs(State* state, int argc, char* argv[],
         targets->push_back(node);
       } else {
         *err = "unknown target '" + path + "'";
+
+        Node* suggestion = state->SpellcheckNode(path);
+        if (suggestion) {
+          *err += ", did you mean '" + suggestion->file_->path_ + "'?";
+        }
         return false;
       }
     }
@@ -200,7 +206,7 @@ int CmdQuery(State* state, int argc, char* argv[]) {
     return 1;
   }
   for (int i = 0; i < argc; ++i) {
-    Node* node = state->GetNode(argv[i]);
+    Node* node = state->LookupNode(argv[i]);
     if (node) {
       printf("%s:\n", argv[i]);
       if (node->in_edge_) {
@@ -219,7 +225,13 @@ int CmdQuery(State* state, int argc, char* argv[]) {
         }
       }
     } else {
-      printf("%s unknown\n", argv[i]);
+      Node* suggestion = state->SpellcheckNode(argv[i]);
+      if (suggestion) {
+        printf("%s unknown, did you mean %s?\n",
+               argv[i], suggestion->file_->path_.c_str());
+      } else {
+        printf("%s unknown\n", argv[i]);
+      }
       return 1;
     }
   }
@@ -329,7 +341,14 @@ int CmdTargets(State* state, int argc, char* argv[]) {
     } else if (mode == "all") {
       return CmdTargetsList(state);
     } else {
-      Error("unknown target tool mode '%s'", mode.c_str());
+      const char* suggestion =
+          SpellcheckString(mode, "rule", "depth", "all", NULL);
+      if (suggestion) {
+        Error("unknown target tool mode '%s', did you mean '%s'?",
+              mode.c_str(), suggestion);
+      } else {
+        Error("unknown target tool mode '%s'", mode.c_str());
+      }
       return 1;
     }
   }
@@ -525,7 +544,14 @@ reload:
     // the tool, i.e. "clean".
     if (tool == "clean")
       return CmdClean(&state, argc+1, argv-1, config);
-    Error("unknown tool '%s'", tool.c_str());
+
+    const char* suggestion = SpellcheckString(tool,
+        "graph", "query", "browse", "targets", "rules", "commands", NULL);
+    if (suggestion) {
+      Error("unknown tool '%s', did you mean '%s'?", tool.c_str(), suggestion);
+    } else {
+      Error("unknown tool '%s'", tool.c_str());
+    }
   }
 
   BuildLog build_log;
diff --git a/src/stat_cache.cc b/src/stat_cache.cc
index 3309837..368f545 100644
--- a/src/stat_cache.cc
+++ b/src/stat_cache.cc
@@ -16,6 +16,7 @@
 
 #include <stdio.h>
 
+#include "edit_distance.h"
 #include "graph.h"
 
 FileStat* StatCache::GetFile(const std::string& path) {
@@ -27,6 +28,23 @@ FileStat* StatCache::GetFile(const std::string& path) {
   return file;
 }
 
+FileStat* StatCache::SpellcheckFile(const std::string& path) {
+  const bool kAllowReplacements = true;
+  const int kMaxValidEditDistance = 3;
+
+  int min_distance = kMaxValidEditDistance + 1;
+  FileStat* result = NULL;
+  for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i) {
+    int distance = EditDistance(
+        i->first, path, kAllowReplacements, kMaxValidEditDistance);
+    if (distance < min_distance && i->second->node_) {
+      min_distance = distance;
+      result = i->second;
+    }
+  }
+  return result;
+}
+
 void StatCache::Dump() {
   for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i) {
     FileStat* file = i->second;
diff --git a/src/stat_cache.h b/src/stat_cache.h
index f071e59..2a5b38b 100644
--- a/src/stat_cache.h
+++ b/src/stat_cache.h
@@ -26,6 +26,7 @@ struct FileStat;
 /// Mapping of path -> FileStat.
 struct StatCache {
   FileStat* GetFile(const std::string& path);
+  FileStat* SpellcheckFile(const std::string& path);
 
   /// Dump the mapping to stdout (useful for debugging).
   void Dump();
diff --git a/src/state.cc b/src/state.cc
index 87d824b..9519856 100644
--- a/src/state.cc
+++ b/src/state.cc
@@ -59,6 +59,13 @@ Node* State::LookupNode(const string& path) {
   return file->node_;
 }
 
+Node* State::SpellcheckNode(const string& path) {
+  FileStat* file = stat_cache_.SpellcheckFile(path);
+  if (!file || !file->node_)
+    return NULL;
+  return file->node_;
+}
+
 void State::AddIn(Edge* edge, const string& path) {
   Node* node = GetNode(path);
   edge->inputs_.push_back(node);
diff --git a/src/state.h b/src/state.h
index 7f30563..1e2cd30 100644
--- a/src/state.h
+++ b/src/state.h
@@ -41,6 +41,7 @@ struct State {
   Edge* AddEdge(const Rule* rule);
   Node* GetNode(const string& path);
   Node* LookupNode(const string& path);
+  Node* SpellcheckNode(const string& path);
   void AddIn(Edge* edge, const string& path);
   void AddOut(Edge* edge, const string& path);
   bool AddDefault(const string& path, string* error);
diff --git a/src/util.cc b/src/util.cc
index f386a8c..0bbcaf2 100644
--- a/src/util.cc
+++ b/src/util.cc
@@ -37,6 +37,8 @@
 #include <direct.h>  // _mkdir
 #endif
 
+#include "edit_distance.h"
+
 void Fatal(const char* msg, ...) {
   va_list ap;
   fprintf(stderr, "ninja: FATAL: ");
@@ -184,3 +186,26 @@ int64_t GetTimeMillis() {
   return ((int64_t)now.tv_sec * 1000) + (now.tv_usec / 1000);
 #endif
 }
+
+const char* SpellcheckString(const string& text, ...) {
+  const bool kAllowReplacements = true;
+  const int kMaxValidEditDistance = 3;
+
+  va_list ap;
+  va_start(ap, text);
+  const char* correct_spelling;
+
+  int min_distance = kMaxValidEditDistance + 1;
+  const char* result = NULL;
+  while ((correct_spelling = va_arg(ap, const char*))) {
+    int distance = EditDistance(
+        correct_spelling, text, kAllowReplacements, kMaxValidEditDistance);
+    if (distance < min_distance) {
+      min_distance = distance;
+      result = correct_spelling;
+    }
+  }
+
+  va_end(ap);
+  return result;
+}
diff --git a/src/util.h b/src/util.h
index d66bd84..40b519e 100644
--- a/src/util.h
+++ b/src/util.h
@@ -49,6 +49,10 @@ void SetCloseOnExec(int fd);
 /// time.
 int64_t GetTimeMillis();
 
+/// Given a misspelled string and a NULL-terminatd list of correct spellings,
+/// returns the closest match or NULL if there is no close enough match.
+const char* SpellcheckString(const string& text, ...);
+
 #ifdef _WIN32
 #define snprintf _snprintf
 #endif