Implement a suggestions mechanism

Each `Error` class now includes a set of suggestions, and these are printed by
the top-level handler.

7 files changed, 191 insertions, 6 deletions

diff --git a/src/libcmd/installables.cc b/src/libcmd/installables.cc
index 3209456bf..888d863ff 100644
--- a/src/libcmd/installables.cc
+++ b/src/libcmd/installables.cc
@@ -610,17 +610,24 @@ std::pair<Value *, Pos> InstallableFlake::toValue(EvalState & state)
 
     auto emptyArgs = state.allocBindings(0);
 
+    Suggestions suggestions;
+
     for (auto & attrPath : getActualAttrPaths()) {
         try {
             auto [v, pos] = findAlongAttrPath(state, attrPath, *emptyArgs, *vOutputs);
             state.forceValue(*v, pos);
             return {v, pos};
         } catch (AttrPathNotFound & e) {
+            suggestions += e.info().suggestions;
         }
     }
 
-    throw Error("flake '%s' does not provide attribute %s",
-        flakeRef, showAttrPaths(getActualAttrPaths()));
+    throw Error(
+        suggestions,
+        "flake '%s' does not provide attribute %s",
+        flakeRef,
+        showAttrPaths(getActualAttrPaths())
+    );
 }
 
 std::vector<std::pair<std::shared_ptr<eval_cache::AttrCursor>, std::string>>
diff --git a/src/libexpr/attr-path.cc b/src/libexpr/attr-path.cc
index eb0e706c7..32deecfae 100644
--- a/src/libexpr/attr-path.cc
+++ b/src/libexpr/attr-path.cc
@@ -74,8 +74,14 @@ std::pair<Value *, Pos> findAlongAttrPath(EvalState & state, const std::string &
                 throw Error("empty attribute name in selection path '%1%'", attrPath);
 
             Bindings::iterator a = v->attrs->find(state.symbols.create(attr));
-            if (a == v->attrs->end())
-                throw AttrPathNotFound("attribute '%1%' in selection path '%2%' not found", attr, attrPath);
+            if (a == v->attrs->end()) {
+                std::set<std::string> attrNames;
+                for (auto & attr : *v->attrs)
+                    attrNames.insert(attr.name);
+
+                auto suggestions = Suggestions::bestMatches(attrNames, attr);
+                throw AttrPathNotFound(suggestions, "attribute '%1%' in selection path '%2%' not found", attr, attrPath);
+            }
             v = &*a->value;
             pos = *a->pos;
         }
diff --git a/src/libutil/args.cc b/src/libutil/args.cc
index f970c0e9e..69aa0d094 100644
--- a/src/libutil/args.cc
+++ b/src/libutil/args.cc
@@ -328,8 +328,13 @@ MultiCommand::MultiCommand(const Commands & commands_)
                         completions->add(name);
             }
             auto i = commands.find(s);
-            if (i == commands.end())
-                throw UsageError("'%s' is not a recognised command", s);
+            if (i == commands.end()) {
+                std::set<std::string> commandNames;
+                for (auto & [name, _] : commands)
+                    commandNames.insert(name);
+                auto suggestions = Suggestions::bestMatches(commandNames, s);
+                throw UsageError(suggestions, "'%s' is not a recognised command", s);
+            }
             command = {s, i->second()};
             command->second->parent = this;
         }}
diff --git a/src/libutil/error.cc b/src/libutil/error.cc
index dcd2f82a5..15ae7a759 100644
--- a/src/libutil/error.cc
+++ b/src/libutil/error.cc
@@ -282,6 +282,13 @@ std::ostream & showErrorInfo(std::ostream & out, const ErrorInfo & einfo, bool s
         }
     }
 
+    auto suggestions = einfo.suggestions.trim();
+    if (! suggestions.suggestions.empty()){
+        oss << "Did you mean " <<
+            suggestions.trim().pretty_print() <<
+            "?" << std::endl;
+    }
+
     // traces
     if (showTrace && !einfo.traces.empty()) {
         for (auto iter = einfo.traces.rbegin(); iter != einfo.traces.rend(); ++iter) {
diff --git a/src/libutil/error.hh b/src/libutil/error.hh
index d55e1d701..600e94888 100644
--- a/src/libutil/error.hh
+++ b/src/libutil/error.hh
@@ -1,5 +1,6 @@
 #pragma once
 
+#include "suggestions.hh"
 #include "ref.hh"
 #include "types.hh"
 #include "fmt.hh"
@@ -112,6 +113,8 @@ struct ErrorInfo {
     std::optional<ErrPos> errPos;
     std::list<Trace> traces;
 
+    Suggestions suggestions;
+
     static std::optional<std::string> programName;
 };
 
@@ -141,6 +144,11 @@ public:
         : err { .level = lvlError, .msg = hintfmt(fs, args...) }
     { }
 
+    template<typename... Args>
+    BaseError(const Suggestions & sug, const Args & ... args)
+        : err { .level = lvlError, .msg = hintfmt(args...), .suggestions = sug }
+    { }
+
     BaseError(hintformat hint)
         : err { .level = lvlError, .msg = hint }
     { }
diff --git a/src/libutil/suggestions.cc b/src/libutil/suggestions.cc
new file mode 100644
index 000000000..96b48416b
--- /dev/null
+++ b/src/libutil/suggestions.cc
@@ -0,0 +1,111 @@
+#include "suggestions.hh"
+#include "ansicolor.hh"
+#include "util.hh"
+#include <algorithm>
+
+namespace nix {
+
+/**
+ * Return `some(distance)` where distance is an integer representing some
+ * notion of distance between both arguments.
+ *
+ * If the distance is too big, return none
+ */
+int distanceBetween(std::string_view first, std::string_view second)
+{
+    // Levenshtein distance.
+    // Implementation borrowed from
+    // https://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_with_two_matrix_rows
+
+    int m = first.size();
+    int n = second.size();
+
+    auto v0 = std::vector<int>(n+1);
+    auto v1 = std::vector<int>(n+1);
+
+    for (auto i = 0; i <= n; i++)
+        v0[i] = i;
+
+    for (auto i = 0; i < m; i++) {
+        v1[0] = i+1;
+
+        for (auto j = 0; j < n; j++) {
+            auto deletionCost = v0[j+1] + 1;
+            auto insertionCost = v1[j] + 1;
+            auto substitutionCost = first[i] == second[j] ? v0[j] : v0[j] + 1;
+            v1[j+1] = std::min({deletionCost, insertionCost, substitutionCost});
+        }
+
+        std::swap(v0, v1);
+    }
+
+    return v0[n];
+}
+
+Suggestions Suggestions::bestMatches (
+    std::set<std::string> allMatches,
+    std::string query)
+{
+    std::set<Suggestion> res;
+    for (const auto & possibleMatch : allMatches) {
+        res.insert(Suggestion {
+            .distance = distanceBetween(query, possibleMatch),
+            .suggestion = possibleMatch,
+        });
+    }
+    return Suggestions { res };
+}
+
+Suggestions Suggestions::trim(int limit, int maxDistance) const
+{
+    std::set<Suggestion> res;
+
+    int count = 0;
+
+    for (auto & elt : suggestions) {
+        if (count >= limit || elt.distance >= maxDistance)
+            break;
+        count++;
+        res.insert(elt);
+    }
+
+    return Suggestions{res};
+}
+
+std::string Suggestion::pretty_print() const
+{
+    return ANSI_WARNING + filterANSIEscapes(suggestion) + ANSI_NORMAL;
+}
+
+std::string Suggestions::pretty_print() const
+{
+    switch (suggestions.size()) {
+        case 0:
+            return "";
+        case 1:
+            return suggestions.begin()->pretty_print();
+        default: {
+            std::string res = "one of ";
+            auto iter = suggestions.begin();
+            res += iter->pretty_print(); // Iter can’t be end() because the container isn’t null
+            iter++;
+            auto last = suggestions.end(); last--;
+            for ( ; iter != suggestions.end() ; iter++) {
+                res += (iter == last) ? " or " : ", ";
+                res += iter->pretty_print();
+            }
+            return res;
+        }
+    }
+}
+
+Suggestions & Suggestions::operator+=(const Suggestions & other)
+{
+    suggestions.insert(
+            other.suggestions.begin(),
+            other.suggestions.end()
+    );
+    return *this;
+}
+
+}
diff --git a/src/libutil/suggestions.hh b/src/libutil/suggestions.hh
new file mode 100644
index 000000000..3caed487a
--- /dev/null
+++ b/src/libutil/suggestions.hh
@@ -0,0 +1,41 @@
+#pragma once
+
+#include "comparator.hh"
+#include "types.hh"
+#include <set>
+
+namespace nix {
+
+/**
+ * A potential suggestion for the cli interface.
+ */
+class Suggestion {
+public:
+    int distance; // The smaller the better
+    std::string suggestion;
+
+    std::string pretty_print() const;
+
+    GENERATE_CMP(Suggestion, me->distance, me->suggestion)
+};
+
+class Suggestions {
+public:
+    std::set<Suggestion> suggestions;
+
+    std::string pretty_print() const;
+
+    Suggestions trim(
+        int limit = 5,
+        int maxDistance = 2
+    ) const;
+
+    static Suggestions bestMatches (
+        std::set<std::string> allMatches,
+        std::string query
+    );
+
+    Suggestions& operator+=(const Suggestions & other);
+};
+
+}