Merge remote-tracking branch 'origin/master' into coerce-string

13 files changed, 389 insertions, 53 deletions

diff --git a/src/libutil/archive.cc b/src/libutil/archive.cc
index eda004756..30b471af5 100644
--- a/src/libutil/archive.cc
+++ b/src/libutil/archive.cc
@@ -64,11 +64,12 @@ static void dumpContents(const Path & path, off_t size,
 }
 
 
-static void dump(const Path & path, Sink & sink, PathFilter & filter)
+static time_t dump(const Path & path, Sink & sink, PathFilter & filter)
 {
     checkInterrupt();
 
     auto st = lstat(path);
+    time_t result = st.st_mtime;
 
     sink << "(";
 
@@ -103,7 +104,10 @@ static void dump(const Path & path, Sink & sink, PathFilter & filter)
         for (auto & i : unhacked)
             if (filter(path + "/" + i.first)) {
                 sink << "entry" << "(" << "name" << i.first << "node";
-                dump(path + "/" + i.second, sink, filter);
+                auto tmp_mtime = dump(path + "/" + i.second, sink, filter);
+                if (tmp_mtime > result) {
+                    result = tmp_mtime;
+                }
                 sink << ")";
             }
     }
@@ -114,13 +118,20 @@ static void dump(const Path & path, Sink & sink, PathFilter & filter)
     else throw Error("file '%1%' has an unsupported type", path);
 
     sink << ")";
+
+    return result;
 }
 
 
-void dumpPath(const Path & path, Sink & sink, PathFilter & filter)
+time_t dumpPathAndGetMtime(const Path & path, Sink & sink, PathFilter & filter)
 {
     sink << narVersionMagic1;
-    dump(path, sink, filter);
+    return dump(path, sink, filter);
+}
+
+void dumpPath(const Path & path, Sink & sink, PathFilter & filter)
+{
+    dumpPathAndGetMtime(path, sink, filter);
 }
 
 
diff --git a/src/libutil/archive.hh b/src/libutil/archive.hh
index fca351605..79ce08df0 100644
--- a/src/libutil/archive.hh
+++ b/src/libutil/archive.hh
@@ -48,6 +48,10 @@ namespace nix {
 void dumpPath(const Path & path, Sink & sink,
     PathFilter & filter = defaultPathFilter);
 
+/* Same as `void dumpPath()`, but returns the last modified date of the path */
+time_t dumpPathAndGetMtime(const Path & path, Sink & sink,
+    PathFilter & filter = defaultPathFilter);
+
 void dumpString(std::string_view s, Sink & sink);
 
 /* FIXME: fix this API, it sucks. */
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 134b99893..ae0bbc06f 100644
--- a/src/libutil/error.cc
+++ b/src/libutil/error.cc
@@ -281,6 +281,13 @@ std::ostream & showErrorInfo(std::ostream & out, const ErrorInfo & einfo, bool s
         oss << "\n";
     }
 
+    auto suggestions = einfo.suggestions.trim();
+    if (! suggestions.suggestions.empty()){
+        oss << "Did you mean " <<
+            suggestions.trim() <<
+            "?" << std::endl;
+    }
+
     // traces
     if (!einfo.traces.empty()) {
         unsigned int count = 0;
diff --git a/src/libutil/error.hh b/src/libutil/error.hh
index ad29f8d2a..2bc3cd2d5 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"
@@ -53,6 +54,7 @@ typedef enum {
     lvlVomit
 } Verbosity;
 
+/* adjust Pos::origin bit width when adding stuff here */
 typedef enum {
     foFile,
     foStdin,
@@ -112,6 +114,8 @@ struct ErrorInfo {
     std::optional<ErrPos> errPos;
     std::list<Trace> traces;
 
+    Suggestions suggestions;
+
     static std::optional<std::string> programName;
 };
 
@@ -143,6 +147,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/finally.hh b/src/libutil/finally.hh
index 7760cfe9a..dee2e8d2f 100644
--- a/src/libutil/finally.hh
+++ b/src/libutil/finally.hh
@@ -1,14 +1,13 @@
 #pragma once
 
-#include <functional>
-
 /* A trivial class to run a function at the end of a scope. */
+template<typename Fn>
 class Finally
 {
 private:
-    std::function<void()> fun;
+    Fn fun;
 
 public:
-    Finally(std::function<void()> fun) : fun(fun) { }
+    Finally(Fn fun) : fun(std::move(fun)) { }
     ~Finally() { fun(); }
 };
diff --git a/src/libutil/logging.cc b/src/libutil/logging.cc
index 74ee2f063..cb2b15b41 100644
--- a/src/libutil/logging.cc
+++ b/src/libutil/logging.cc
@@ -266,51 +266,63 @@ static Logger::Fields getFields(nlohmann::json & json)
     return fields;
 }
 
-bool handleJSONLogMessage(const std::string & msg,
-    const Activity & act, std::map<ActivityId, Activity> & activities, bool trusted)
+std::optional<nlohmann::json> parseJSONMessage(const std::string & msg)
 {
-    if (!hasPrefix(msg, "@nix ")) return false;
-
+    if (!hasPrefix(msg, "@nix ")) return std::nullopt;
     try {
-        auto json = nlohmann::json::parse(std::string(msg, 5));
-
-        std::string action = json["action"];
-
-        if (action == "start") {
-            auto type = (ActivityType) json["type"];
-            if (trusted || type == actFileTransfer)
-                activities.emplace(std::piecewise_construct,
-                    std::forward_as_tuple(json["id"]),
-                    std::forward_as_tuple(*logger, (Verbosity) json["level"], type,
-                        json["text"], getFields(json["fields"]), act.id));
-        }
+        return nlohmann::json::parse(std::string(msg, 5));
+    } catch (std::exception & e) {
+        printError("bad JSON log message from builder: %s", e.what());
+    }
+    return std::nullopt;
+}
 
-        else if (action == "stop")
-            activities.erase((ActivityId) json["id"]);
+bool handleJSONLogMessage(nlohmann::json & json,
+    const Activity & act, std::map<ActivityId, Activity> & activities,
+    bool trusted)
+{
+    std::string action = json["action"];
+
+    if (action == "start") {
+        auto type = (ActivityType) json["type"];
+        if (trusted || type == actFileTransfer)
+            activities.emplace(std::piecewise_construct,
+                std::forward_as_tuple(json["id"]),
+                std::forward_as_tuple(*logger, (Verbosity) json["level"], type,
+                    json["text"], getFields(json["fields"]), act.id));
+    }
 
-        else if (action == "result") {
-            auto i = activities.find((ActivityId) json["id"]);
-            if (i != activities.end())
-                i->second.result((ResultType) json["type"], getFields(json["fields"]));
-        }
+    else if (action == "stop")
+        activities.erase((ActivityId) json["id"]);
 
-        else if (action == "setPhase") {
-            std::string phase = json["phase"];
-            act.result(resSetPhase, phase);
-        }
+    else if (action == "result") {
+        auto i = activities.find((ActivityId) json["id"]);
+        if (i != activities.end())
+            i->second.result((ResultType) json["type"], getFields(json["fields"]));
+    }
 
-        else if (action == "msg") {
-            std::string msg = json["msg"];
-            logger->log((Verbosity) json["level"], msg);
-        }
+    else if (action == "setPhase") {
+        std::string phase = json["phase"];
+        act.result(resSetPhase, phase);
+    }
 
-    } catch (std::exception & e) {
-        printError("bad JSON log message from builder: %s", e.what());
+    else if (action == "msg") {
+        std::string msg = json["msg"];
+        logger->log((Verbosity) json["level"], msg);
     }
 
     return true;
 }
 
+bool handleJSONLogMessage(const std::string & msg,
+    const Activity & act, std::map<ActivityId, Activity> & activities, bool trusted)
+{
+    auto json = parseJSONMessage(msg);
+    if (!json) return false;
+
+    return handleJSONLogMessage(*json, act, activities, trusted);
+}
+
 Activity::~Activity()
 {
     try {
diff --git a/src/libutil/logging.hh b/src/libutil/logging.hh
index bd28036ae..6f81b92de 100644
--- a/src/libutil/logging.hh
+++ b/src/libutil/logging.hh
@@ -4,6 +4,8 @@
 #include "error.hh"
 #include "config.hh"
 
+#include <nlohmann/json_fwd.hpp>
+
 namespace nix {
 
 typedef enum {
@@ -166,6 +168,12 @@ Logger * makeSimpleLogger(bool printBuildLogs = true);
 
 Logger * makeJSONLogger(Logger & prevLogger);
 
+std::optional<nlohmann::json> parseJSONMessage(const std::string & msg);
+
+bool handleJSONLogMessage(nlohmann::json & json,
+    const Activity & act, std::map<ActivityId, Activity> & activities,
+    bool trusted);
+
 bool handleJSONLogMessage(const std::string & msg,
     const Activity & act, std::map<ActivityId, Activity> & activities,
     bool trusted);
diff --git a/src/libutil/suggestions.cc b/src/libutil/suggestions.cc
new file mode 100644
index 000000000..9510a5f0c
--- /dev/null
+++ b/src/libutil/suggestions.cc
@@ -0,0 +1,114 @@
+#include "suggestions.hh"
+#include "ansicolor.hh"
+#include "util.hh"
+#include <algorithm>
+
+namespace nix {
+
+int levenshteinDistance(std::string_view first, std::string_view second)
+{
+    // 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 = levenshteinDistance(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::to_string() const
+{
+    return ANSI_WARNING + filterANSIEscapes(suggestion) + ANSI_NORMAL;
+}
+
+std::string Suggestions::to_string() const
+{
+    switch (suggestions.size()) {
+        case 0:
+            return "";
+        case 1:
+            return suggestions.begin()->to_string();
+        default: {
+            std::string res = "one of ";
+            auto iter = suggestions.begin();
+            res += iter->to_string(); // 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->to_string();
+            }
+            return res;
+        }
+    }
+}
+
+Suggestions & Suggestions::operator+=(const Suggestions & other)
+{
+    suggestions.insert(
+            other.suggestions.begin(),
+            other.suggestions.end()
+    );
+    return *this;
+}
+
+std::ostream & operator<<(std::ostream & str, const Suggestion & suggestion)
+{
+    return str << suggestion.to_string();
+}
+
+std::ostream & operator<<(std::ostream & str, const Suggestions & suggestions)
+{
+    return str << suggestions.to_string();
+}
+
+}
diff --git a/src/libutil/suggestions.hh b/src/libutil/suggestions.hh
new file mode 100644
index 000000000..d54dd8e31
--- /dev/null
+++ b/src/libutil/suggestions.hh
@@ -0,0 +1,102 @@
+#pragma once
+
+#include "comparator.hh"
+#include "types.hh"
+#include <set>
+
+namespace nix {
+
+int levenshteinDistance(std::string_view first, std::string_view second);
+
+/**
+ * A potential suggestion for the cli interface.
+ */
+class Suggestion {
+public:
+    int distance; // The smaller the better
+    std::string suggestion;
+
+    std::string to_string() const;
+
+    GENERATE_CMP(Suggestion, me->distance, me->suggestion)
+};
+
+class Suggestions {
+public:
+    std::set<Suggestion> suggestions;
+
+    std::string to_string() 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);
+};
+
+std::ostream & operator<<(std::ostream & str, const Suggestion &);
+std::ostream & operator<<(std::ostream & str, const Suggestions &);
+
+// Either a value of type `T`, or some suggestions
+template<typename T>
+class OrSuggestions {
+public:
+    using Raw = std::variant<T, Suggestions>;
+
+    Raw raw;
+
+    T* operator ->()
+    {
+        return &**this;
+    }
+
+    T& operator *()
+    {
+        return std::get<T>(raw);
+    }
+
+    operator bool() const noexcept
+    {
+        return std::holds_alternative<T>(raw);
+    }
+
+    OrSuggestions(T t)
+        : raw(t)
+    {
+    }
+
+    OrSuggestions()
+        : raw(Suggestions{})
+    {
+    }
+
+    static OrSuggestions<T> failed(const Suggestions & s)
+    {
+        auto res = OrSuggestions<T>();
+        res.raw = s;
+        return res;
+    }
+
+    static OrSuggestions<T> failed()
+    {
+        return OrSuggestions<T>::failed(Suggestions{});
+    }
+
+    const Suggestions & getSuggestions()
+    {
+        static Suggestions noSuggestions;
+        if (const auto & suggestions = std::get_if<Suggestions>(&raw))
+            return *suggestions;
+        else
+            return noSuggestions;
+    }
+
+};
+
+}
diff --git a/src/libutil/tests/logging.cc b/src/libutil/tests/logging.cc
index cef3bd481..2ffdc2e9b 100644
--- a/src/libutil/tests/logging.cc
+++ b/src/libutil/tests/logging.cc
@@ -359,7 +359,7 @@ namespace nix {
 
       // constructing without access violation.
       ErrPos ep(invalid);
-    
+
       // assignment without access violation.
       ep = invalid;
 
diff --git a/src/libutil/tests/suggestions.cc b/src/libutil/tests/suggestions.cc
new file mode 100644
index 000000000..279994abc
--- /dev/null
+++ b/src/libutil/tests/suggestions.cc
@@ -0,0 +1,43 @@
+#include "suggestions.hh"
+#include <gtest/gtest.h>
+
+namespace nix {
+
+    struct LevenshteinDistanceParam {
+        std::string s1, s2;
+        int distance;
+    };
+
+    class LevenshteinDistanceTest :
+        public testing::TestWithParam<LevenshteinDistanceParam> {
+    };
+
+    TEST_P(LevenshteinDistanceTest, CorrectlyComputed) {
+        auto params = GetParam();
+
+        ASSERT_EQ(levenshteinDistance(params.s1, params.s2), params.distance);
+        ASSERT_EQ(levenshteinDistance(params.s2, params.s1), params.distance);
+    }
+
+    INSTANTIATE_TEST_SUITE_P(LevenshteinDistance, LevenshteinDistanceTest,
+            testing::Values(
+                LevenshteinDistanceParam{"foo", "foo", 0},
+                LevenshteinDistanceParam{"foo", "", 3},
+                LevenshteinDistanceParam{"", "", 0},
+                LevenshteinDistanceParam{"foo", "fo", 1},
+                LevenshteinDistanceParam{"foo", "oo", 1},
+                LevenshteinDistanceParam{"foo", "fao", 1},
+                LevenshteinDistanceParam{"foo", "abc", 3}
+            )
+    );
+
+    TEST(Suggestions, Trim) {
+        auto suggestions = Suggestions::bestMatches({"foooo", "bar", "fo", "gao"}, "foo");
+        auto onlyOne = suggestions.trim(1);
+        ASSERT_EQ(onlyOne.suggestions.size(), 1);
+        ASSERT_TRUE(onlyOne.suggestions.begin()->suggestion == "fo");
+
+        auto closest = suggestions.trim(999, 2);
+        ASSERT_EQ(closest.suggestions.size(), 3);
+    }
+}
diff --git a/src/libutil/util.cc b/src/libutil/util.cc
index b833038a9..70eaf4f9c 100644
--- a/src/libutil/util.cc
+++ b/src/libutil/util.cc
@@ -406,8 +406,29 @@ static void _deletePath(int parentfd, const Path & path, uint64_t & bytesFreed)
         throw SysError("getting status of '%1%'", path);
     }
 
-    if (!S_ISDIR(st.st_mode) && st.st_nlink == 1)
-        bytesFreed += st.st_size;
+    if (!S_ISDIR(st.st_mode)) {
+        /* We are about to delete a file. Will it likely free space? */
+
+        switch (st.st_nlink) {
+            /* Yes: last link. */
+            case 1:
+                bytesFreed += st.st_size;
+                break;
+            /* Maybe: yes, if 'auto-optimise-store' or manual optimisation
+               was performed. Instead of checking for real let's assume
+               it's an optimised file and space will be freed.
+
+               In worst case we will double count on freed space for files
+               with exactly two hardlinks for unoptimised packages.
+             */
+            case 2:
+                bytesFreed += st.st_size;
+                break;
+            /* No: 3+ links. */
+            default:
+                break;
+        }
+    }
 
     if (S_ISDIR(st.st_mode)) {
         /* Make the directory accessible. */
@@ -682,7 +703,14 @@ std::string drainFD(int fd, bool block, const size_t reserveSize)
 
 void drainFD(int fd, Sink & sink, bool block)
 {
-    int saved;
+    // silence GCC maybe-uninitialized warning in finally
+    int saved = 0;
+
+    if (!block) {
+        saved = fcntl(fd, F_GETFL);
+        if (fcntl(fd, F_SETFL, saved | O_NONBLOCK) == -1)
+            throw SysError("making file descriptor non-blocking");
+    }
 
     Finally finally([&]() {
         if (!block) {
@@ -691,12 +719,6 @@ void drainFD(int fd, Sink & sink, bool block)
         }
     });
 
-    if (!block) {
-        saved = fcntl(fd, F_GETFL);
-        if (fcntl(fd, F_SETFL, saved | O_NONBLOCK) == -1)
-            throw SysError("making file descriptor non-blocking");
-    }
-
     std::vector<unsigned char> buf(64 * 1024);
     while (1) {
         checkInterrupt();